Skip to main content

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 {
  templates: Pointer.Templates;
  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;

  // Stack of rename mappings for template references with yields
  const renameStack: Array<Record<string, string>> = [];

  // Stack of template definitions for inline templates
  const templatesStack: Array<Pointer.Templates> = [];

  // Names of the enclosing named collections (and named list indexes)
  const path: Cursor.Path = [];

  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": {
        // Merge inline templates with base templates (inline takes precedence)
        const currentTemplates = templatesStack.reduce(
          (acc, templates) => ({ ...acc, ...templates }),
          options.templates,
        );

        // Process the pointer, intercepting yielded regions to apply renames
        const process = processPointer(memo.pointer, {
          ...options,
          templates: currentTemplates,
        });
        let result = await process.next();
        while (!result.done) {
          let region = result.value;

          // Apply every active rename, innermost template first, so that
          // nested yields compose
          if (region.name) {
            const name = renameStack.reduceRight(
              (name, mapping) => (hasOwn(mapping, name) ? mapping[name] : name),
              region.name,
            );
            if (name !== region.name) {
              region = { ...region, name };
            }
          }

          if (path.length > 0) {
            region = { ...region, path: [...path] };
          }

          yield region;
          result = await process.next();
        }
        memos = result.value;
        break;
      }
      case "save-regions": {
        for (const [name, region] of Object.entries(memo.regions)) {
          // Save under original name for internal reference resolution
          regions[name] = region;
        }
        break;
      }
      case "save-variables": {
        Object.assign(variables, memo.variables);
        break;
      }
      case "restore-variables": {
        for (const name of Object.keys(variables)) {
          delete variables[name];
        }
        Object.assign(variables, memo.variables);
        break;
      }
      case "push-region-renames": {
        renameStack.push(memo.mapping);
        break;
      }
      case "pop-region-renames": {
        // Apply renames when exiting the context: add mappings from
        // original names to new names for external reference resolution
        const mapping = renameStack.pop();
        if (mapping) {
          for (const [originalName, newName] of Object.entries(mapping)) {
            if (originalName in regions && newName !== originalName) {
              regions[newName] = { ...regions[originalName], name: newName };
            }
          }
        }
        break;
      }
      case "push-templates": {
        templatesStack.push(memo.templates);
        break;
      }
      case "pop-templates": {
        templatesStack.pop();
        break;
      }
      case "push-path": {
        path.push(memo.segment);
        break;
      }
      case "pop-path": {
        path.pop();
        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 kind of memo and its corresponding helper constructor function.

See the memo.ts module
src/dereference/memo.ts
import type { Pointer } from "@ethdebug/format";
import type { Cursor } from "#cursor";
import type { Value } from "#evaluate";

/**
 * A single state transition for processing on a stack
 */
export type Memo =
  | Memo.DereferencePointer
  | Memo.SaveRegions
  | Memo.SaveVariables
  | Memo.RestoreVariables
  | Memo.PushRegionRenames
  | Memo.PopRegionRenames
  | Memo.PushTemplates
  | Memo.PopTemplates
  | Memo.PushPath
  | Memo.PopPath;

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, Value>;
  }

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

  /**
   * A request to replace the stateful map of variable values with a
   * snapshot taken earlier, discarding every variable saved since.
   */
  export interface RestoreVariables {
    kind: "restore-variables";
    variables: Record<string, Value>;
  }

  /**
   * Initialize a RestoreVariables memo
   */
  export const restoreVariables = (
    variables: Record<string, Value>,
  ): RestoreVariables => ({
    kind: "restore-variables",
    variables,
  });

  /**
   * A request to push a region rename mapping onto the context stack.
   * While active, regions with names in the mapping will be saved under
   * both their original name (for internal references) and their new name
   * (for external references after the template).
   */
  export interface PushRegionRenames {
    kind: "push-region-renames";
    mapping: Record<string, string>;
  }

  /**
   * Initialize a PushRegionRenames memo
   */
  export const pushRegionRenames = (
    mapping: Record<string, string>,
  ): PushRegionRenames => ({
    kind: "push-region-renames",
    mapping,
  });

  /**
   * A request to pop the current region rename mapping from the context stack.
   */
  export interface PopRegionRenames {
    kind: "pop-region-renames";
  }

  /**
   * Initialize a PopRegionRenames memo
   */
  export const popRegionRenames = (): PopRegionRenames => ({
    kind: "pop-region-renames",
  });

  /**
   * A request to push template definitions onto the context stack.
   * While active, these templates are available for use by reference
   * collections.
   */
  export interface PushTemplates {
    kind: "push-templates";
    templates: Pointer.Templates;
  }

  /**
   * Initialize a PushTemplates memo
   */
  export const pushTemplates = (
    templates: Pointer.Templates,
  ): PushTemplates => ({
    kind: "push-templates",
    templates,
  });

  /**
   * A request to pop the current template definitions from the context stack.
   */
  export interface PopTemplates {
    kind: "pop-templates";
  }

  /**
   * Initialize a PopTemplates memo
   */
  export const popTemplates = (): PopTemplates => ({
    kind: "pop-templates",
  });

  /**
   * A request to push a segment onto the path that output regions carry:
   * a collection name, or the index of an element of a named list
   */
  export interface PushPath {
    kind: "push-path";
    segment: string | number;
  }

  /**
   * Initialize a PushPath memo
   */
  export const pushPath = (segment: string | number): PushPath => ({
    kind: "push-path",
    segment,
  });

  /**
   * A request to pop the last segment from the path
   */
  export interface PopPath {
    kind: "pop-path";
  }

  /**
   * Initialize a PopPath memo
   */
  export const popPath = (): PopPath => ({
    kind: "pop-path",
  });
}

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 {
  templates: Pointer.Templates;
  state: Machine.State;
  stackLengthChange: bigint;
  regions: Record<string, Cursor.Region>;
  variables: Record<string, Value>;
}

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;
  const memos = yield* processCollection(collection, options);

  // a collection's name scopes the regions inside it in the output
  if (typeof collection.name === "string") {
    return [Memo.pushPath(collection.name), ...memos, Memo.popPath()];
  }

  return memos;
}

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 { name, list } = collection;
  const { count: countExpression, each, is } = list;

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

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

    // a named list scopes each element apart by its index
    if (typeof name === "string") {
      memos.push(
        Memo.pushPath(Number(index)),
        Memo.dereferencePointer(is),
        Memo.popPath(),
      );
    } else {
      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_ = Value.toInteger(await evaluate(ifExpression, options));

  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.

JSON objects are unordered, so the members of a define may use each other in any order. processScope evaluates each member after the members it uses. Like the fields of a region that refer to each other with ~this, it queues the members and retries one that uses a member not evaluated yet. Each member sees the other members by name, but its own name means the variable of the enclosing scope. If every remaining member fails in turn, they form a cycle.

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

  const newVariables: { [identifier: string]: Value } = Object.create(null);
  const isMember = (name: PropertyKey): name is string =>
    Object.prototype.hasOwnProperty.call(variableExpressions, name);

  // the variables one member sees: a name of another member means that
  // member, so it must be evaluated first; any other name, the member's
  // own included, means a variable of the enclosing scope
  const variablesFor = (identifier: string) =>
    new Proxy(options.variables, {
      get(target, name) {
        if (name === identifier || !isMember(name)) {
          return target[name as string];
        }
        if (name in newVariables) {
          return newVariables[name];
        }
        throw new Error(`Variable not evaluated yet: ${name}`);
      },
    });

  // evaluate members in dependency order, independent of member order.
  // retry a member that uses one not evaluated yet; when every remaining
  // member has failed since the last success, they form a cycle
  const queue = Object.keys(variableExpressions);
  let failures = 0;
  while (queue.length > 0) {
    const identifier = queue.shift()!;
    try {
      newVariables[identifier] = await evaluate(
        variableExpressions[identifier],
        { ...options, variables: variablesFor(identifier) },
      );
      failures = 0;
    } catch (error) {
      if (
        !(error instanceof Error) ||
        !error.message.startsWith("Variable not evaluated yet: ")
      ) {
        throw error;
      }
      if (++failures > queue.length) {
        throw new Error(`Circular reference detected: ${identifier}`);
      }
      queue.push(identifier);
    }
  }

  // variables defined here are visible only within `in`
  return [
    Memo.saveVariables(newVariables),
    Memo.dereferencePointer(in_),
    Memo.restoreVariables(
      Object.assign(Object.create(null), options.variables),
    ),
  ];
}

Collection names​

processPointer() handles a collection's name for every kind of collection at once: it surrounds the collection's memos with a PushPath memo for the name and a PopPath memo after them. generateRegions() keeps the current path and copies it onto each region it yields, when the path is not empty. A named list also surrounds each element with a PushPath memo for the element's index (see processList() above). Paths never reach the saved regions or variables, so expressions do not see collection names.