Generating regions on the fly

The dereference() function internally creates an AsyncIterator to produce an asynchronous list of regions.

The process to produce this list uses a stack of processing requests (which it calls "memos"), consuming one memo at a time from the top of the stack and handling it based on what kind of memo it is.

This is defined by the generateRegions() function (defined in conjunction with GenerateRegionsOptions):

generateRegions() and GenerateRegionsOptions

/**
 * Upfront information needed for generating the concrete Cursor.Regions
 * for a particular pointer at runtime.
 */
export interface GenerateRegionsOptions {
  state: Machine.State;
  initialStackLength: bigint;
}

/**
 * Generator function that yields Cursor.Regions for a given Pointer.
 *
 * This function maintains an internal stack of memos to evaluate,
 * initially populating this stack with a single entry for evaluating the
 * given pointer.
 */
export async function* generateRegions(
  pointer: Pointer,
  generateRegionsOptions: GenerateRegionsOptions
): AsyncIterable<Cursor.Region> {
  const options = await initializeProcessOptions(generateRegionsOptions);

  // extract records for mutation
  const {
    regions,
    variables
  } = options;

  const stack: Memo[] = [Memo.dereferencePointer(pointer)];
  while (stack.length > 0) {
    const memo: Memo = stack.pop() as Memo;

    let memos: Memo[] = [];
    switch (memo.kind) {
      case "dereference-pointer": {
        memos = yield* processPointer(memo.pointer, options);
        break;
      }
      case "save-regions": {
        Object.assign(regions, memo.regions);
        break;
      }
      case "save-variables": {
        Object.assign(variables, memo.variables);
        break;
      }
    }

    // add new memos to the stack in reverse order
    for (let index = memos.length - 1; index >= 0; index--) {
      stack.push(memos[index]);
    }
  }
}

Notice how this function initializes two mutable records collections: one for all the current named regions, and one for all the current variables. As this function's while() loop operates on the stack, memos for saving new named regions or updating variable values may appear and then get handled appropriately.

For reference, see the memo.ts module for type definitions for each of the three types of memo and their corresponding helper constructor functions.

See the memo.ts module

src/dereference/memo.ts

import type { Pointer } from "../pointer.js";
import type { Cursor } from "../cursor.js";
import type { Data } from "../data.js";

/**
 * A single state transition for processing on a stack
 */
export type Memo =
  | Memo.DereferencePointer
  | Memo.SaveRegions
  | Memo.SaveVariables;

export namespace Memo {
  /**
   * A request to dereference a pointer
   */
  export interface DereferencePointer {
    kind: "dereference-pointer";
    pointer: Pointer;
  }

  /**
   * Initialize a DereferencePointer memo
   */
  export const dereferencePointer =
    (pointer: Pointer): DereferencePointer => ({
      kind: "dereference-pointer",
      pointer
    });

  /**
   * A request to modify the stateful map of regions by name with a
   * particular set of new entries.
   *
   * This does not indicate that any change should be made to region names not
   * included in this memo.
   */
  export interface SaveRegions {
    kind: "save-regions";
    regions: Record<string, Cursor.Region>;
  }

  /**
   * Initialize a SaveRegions memo
   */
  export const saveRegions =
    (regions: Record<string, Cursor.Region>): SaveRegions => ({
      kind: "save-regions",
      regions
    });

  /**
   * A request to modify the stateful map of variable values with a
   * particular set of new entries.
   *
   * This does not indicate that any change should be made to variables not
   * included in this memo.
   */
  export interface SaveVariables {
    kind: "save-variables";
    variables: Record<string, Data>;
  }

  /**
   * Initialize a SaveVariables memo
   */
  export const saveVariables =
    (variables: Record<string, Data>): SaveVariables => ({
      kind: "save-variables",
      variables
    });
}

The real bulk of what generateRegions() does, however, is hidden inside the call yield* processPointer().

Processing a pointer

To handle a DereferencePointer memo from the stack inside generateRegions(), it defers to the processPointer() generator function.

The signature of this function and associated types are as follows:

/**
 * Process a pointer into a yielded list of concrete, evaluated Cursor.Regions
 * and return a list of new memos to add to the stack for processing next
 */
declare async function processPointer(
    pointer: Pointer, 
    options: ProcessOptions
): Process;

The ProcessOptions interface captures the runtime data at a particular point in the region generation process:

/**
 * Contextual information for use within a pointer dereference process
 */
export interface ProcessOptions {
  state: Machine.State;
  stackLengthChange: bigint;
  regions: Record<string, Cursor.Region>;
  variables: Record<string, Data>;
}

The Process type alias provides a short type alias for functions like processPointer to use:

/**
 * an generator that yields Cursor regions and returns a list of new memos
 * to add to the stack
 */
export type Process = AsyncGenerator<Cursor.Region, Memo[]>;

Effectively, by returning a Process, the processPointer() has two different mechanisms of data return:

• By being a JavaScript AsyncGenerator, it produces Cursor.Region objects one at a time, emitted as a side effect of execution (via JavaScript yield)
• Upon completion of exection, the return value is a list of memos to be added to the stack.

Note that the expected behavior for this implementation is that the returned list of memos should be pushed onto the stack in reverse order, so that earlier memos in the list will be processed before later ones.

See the full definition of processPointer()

/**
 * Process a pointer into a yielded list of concrete, evaluated Cursor.Regions
 * and return a list of new memos to add to the stack for processing next
 */
export async function* processPointer(
  pointer: Pointer,
  options: ProcessOptions
): Process {
  if (Pointer.isRegion(pointer)) {
    const region = pointer;

    return yield* processRegion(region, options);
  }

  const collection = pointer;

  if (Pointer.Collection.isGroup(collection)) {
    return yield* processGroup(collection, options);
  }

  if (Pointer.Collection.isList(collection)) {
    return yield* processList(collection, options);
  }

  if (Pointer.Collection.isConditional(collection)) {
    return yield* processConditional(collection, options);
  }

  if (Pointer.Collection.isScope(collection)) {
    return yield* processScope(collection, options);
  }

  console.error("%s", JSON.stringify(pointer, undefined, 2));
  throw new Error("Unexpected unknown kind of pointer");
}

Processing a region

The simplest kind of pointer is just a single region. (Remember that pointers are either regions or collections of other pointers.)

There is complexity hidden by function calls here, but nonetheless first consider the implementation of the processRegion() function as a base case:

async function* processRegion(
  region: Pointer.Region,
  { stackLengthChange, ...options}: ProcessOptions
): Process {
  const evaluatedRegion = await evaluateRegion(
    adjustStackLength(region, stackLengthChange),
    options
  );

  yield evaluatedRegion;

  if (typeof region.name !== "undefined") {
    return [Memo.saveRegions({ [region.name]: evaluatedRegion })];
  }

  return [];
}

Effectively, this function converts a Pointer.Region into a fully-evaluated, concrete Cursor.Region, emits this concrete region as the next yielded value in the asynchronous list of regions, and possibly issues a request to save this region to process state by its name.

This pointer evaluation process will be described later.

Processing collections

The recursive cases are fairly straightforward following this architecture.

Groups

The simplest collection, a group of other pointers, yields no regions of its own, but instead pushes each of its child pointers for evaluation later:

async function* processGroup(
  collection: Pointer.Collection.Group,
  options: ProcessOptions
): Process {
  const { group } = collection;
  return group.map(Memo.dereferencePointer);
}

It's essential that each of the child pointers get evaluated in the order they appear in the list, since later pointers may reference regions named earlier, etc.

Lists

List collections are more complex because they dynamically generate a number of composed pointers based on a runtime count value and introducing a variable identifier for use inside the dynamic composed pointer evaluation.

async function* processList(
  collection: Pointer.Collection.List,
  options: ProcessOptions
): Process {
  const { list } = collection;
  const { count: countExpression, each, is } = list;

  const count = (await evaluate(countExpression, options)).asUint();

  const memos: Memo[] = [];
  for (let index = 0n; index < count; index++) {
    memos.push(Memo.saveVariables({
      [each]: Data.fromUint(index)
    }));

    memos.push(Memo.dereferencePointer(is));
  }

  return memos;
}

Note how, because each dynamic child pointer is evaluated based on the next incremented index value, the memos for updating this variable and evaluation the child pointer must be interspersed.

Conditionals

Conditional pointers evaluate to a child pointer given that some runtime condition evaluates to a nonzero value, optionally evaluating to a different pointer when that conditional fails.

Evaluating a conditional thus becomes a simple matter of evaluating the "if" clause and issuing a memo for dereferencing the "then" pointer or the "else" pointer if it is specified:

async function* processConditional(
  collection: Pointer.Collection.Conditional,
  options: ProcessOptions
): Process {
  const { if: ifExpression, then: then_, else: else_ } = collection;

  const if_ = (await evaluate(ifExpression, options)).asUint();

  if (if_) {
    return [Memo.dereferencePointer(then_)];
  }

  // otherwise, return the else clause if it exists (it is optional)
  return else_
    ? [Memo.dereferencePointer(else_)]
    : [];
}

Scopes

Finally, the last kind of collection defined by this schema is for defining a scope of variables by identifier by specifying the expression values for each of those variables.

Since this schema takes advantage of how JSON objects are ordered lists of key/value pairs, variables specified later may reference variables specified earlier. The only trickiness in implementing processScope is ensuring that variable values are available immediately.

async function* processScope(
  collection: Pointer.Collection.Scope,
  options: ProcessOptions
): Process {
  const { define: variableExpressions, in: in_ } = collection;

  const allVariables = {
    ...options.variables
  };
  const newVariables: { [identifier: string]: Data } = {};
  for (const [identifier, expression] of Object.entries(variableExpressions)) {
    const data = await evaluate(expression, {
      ...options,
      variables: allVariables
    });

    allVariables[identifier] = data;
    newVariables[identifier] = data;
  }

  return [
    Memo.saveVariables(newVariables),
    Memo.dereferencePointer(in_)
  ];
}