Skip to main content

Evaluating pointer expressions

Expression evaluation is a bit more interesting than reading raw region data, but, still, performing this evaluation becomes relatively straightforward if variable and region references are pre-evaluated.

Two sorts of value​

The schema defines every expression to evaluate to one of two sorts of value: an integer, which has a numeric value but no width, or bytes, which have a definite width. The distinction matters because $keccak256 and $concat produce results that depend on the widths of their operands, so the schema requires those operands to be bytes. A bare integer (a JSON number, $wordsize, an arithmetic result, or a lookup) must first be given a width with $sized<N> or $wordsized; the resize forms are the only bridge from an integer to bytes.

This reference implementation represents the two sorts as a tagged union:

/**
 * The result of evaluating an expression: one of two sorts of value.
 *
 * An **integer** is an unbounded non-negative integer with no width; it
 * is produced by JSON-number literals, `$wordsize`, lookups, arithmetic,
 * and odd-digit hex literals.
 *
 * **Bytes** are a byte sequence with a definite width; they are produced
 * by even-digit hex literals, `$read`, and the resize forms.
 *
 * Variables carry the sort of the expression that defined them.
 */
export type Value = Value.Integer | Value.Bytes;

The accompanying Value namespace provides constructors, type guards, and the two conversions the rest of the implementation needs: toInteger(), for positions where the schema expects an integer (bytes are read as the non-negative integer they encode big-endian), and toData(), for storing a value as a concrete region's slot, offset, or length:

export namespace Value {
  export interface Integer {
    sort: "integer";
    value: bigint;
  }

  export interface Bytes {
    sort: "bytes";
    data: Data;
  }

  export const integer = (value: bigint): Integer => ({
    sort: "integer",
    value,
  });

  export const bytes = (data: Data): Bytes => ({ sort: "bytes", data });

  export const isInteger = (value: Value): value is Integer =>
    value.sort === "integer";

  export const isBytes = (value: Value): value is Bytes =>
    value.sort === "bytes";

  /**
   * Coerce to an integer, for positions where an integer is expected
   * (arithmetic operands, list counts, segment slot/offset/length). Bytes
   * are read as the non-negative integer they encode big-endian.
   */
  export const toInteger = (value: Value): bigint =>
    isInteger(value) ? value.value : value.data.asUint();

  /**
   * Represent as `Data` for storage on a concrete `Cursor.Region`. Bytes
   * keep their width; an integer is encoded as its minimal big-endian
   * bytes (a region's slot/offset/length are integers, so this width is
   * not significant).
   */
  export const toData = (value: Value): Data =>
    isBytes(value) ? value.data : Data.fromUint(value.value);
}

Evaluation options​

Variables carry the sort of the expression that defined them, so the variables map holds Values, while the regions map holds pre-evaluated concrete regions:

export interface EvaluateOptions {
  state: Machine.State;
  regions: {
    [identifier: string]: Cursor.Region;
  };
  variables: {
    [identifier: string]: Value;
  };
}

The main evaluate() function uses type guards to dispatch to the appropriate specific logic based on the kind of expression:

Source code of evaluate(expression: Pointer.Expression, options: EvaluateOptions)
export async function evaluate(
  expression: Pointer.Expression,
  options: EvaluateOptions,
): Promise<Value> {
  if (Pointer.Expression.isLiteral(expression)) {
    return evaluateLiteral(expression);
  }

  if (Pointer.Expression.isConstant(expression)) {
    return evaluateConstant(expression);
  }

  if (Pointer.Expression.isVariable(expression)) {
    return evaluateVariable(expression, options);
  }

  if (Pointer.Expression.isArithmetic(expression)) {
    return evaluateArithmetic(expression, options);
  }

  if (Pointer.Expression.isKeccak256(expression)) {
    return evaluateKeccak256(expression, options);
  }

  if (Pointer.Expression.isConcat(expression)) {
    return evaluateConcat(expression, options);
  }

  if (Pointer.Expression.isResize(expression)) {
    return evaluateResize(expression, options);
  }

  if (Pointer.Expression.isLookup(expression)) {
    if (Pointer.Expression.Lookup.isOffset(expression)) {
      return evaluateLookup(".offset", expression, options);
    }

    if (Pointer.Expression.Lookup.isLength(expression)) {
      return evaluateLookup(".length", expression, options);
    }

    if (Pointer.Expression.Lookup.isSlot(expression)) {
      return evaluateLookup(".slot", expression, options);
    }
  }

  if (Pointer.Expression.isRead(expression)) {
    return evaluateRead(expression, options);
  }

  throw new Error(
    `Unexpected runtime failure to recognize kind of expression: ${JSON.stringify(
      expression,
    )}`,
  );
}

Evaluating constants, literals, and variables​

Evaluating constant expressions is quite straightforward; $wordsize is the integer 32:

async function evaluateConstant(
  constant: Pointer.Expression.Constant,
): Promise<Value> {
  switch (constant) {
    case "$wordsize":
      return Value.integer(32n);
  }
}

Literals follow the schema's sorting rule: a JSON number is an integer, a hex string with an even number of digits is bytes of that width, and a hex string with an odd number of digits (which has no whole-byte width) is an integer:

async function evaluateLiteral(
  literal: Pointer.Expression.Literal,
): Promise<Value> {
  switch (typeof literal) {
    case "string": {
      const digits = literal.slice(2);

      // an odd number of digits has no whole-byte width
      if (digits.length % 2 === 1) {
        return Value.integer(BigInt(literal));
      }

      return Value.bytes(Data.fromHex(literal));
    }
    case "number":
      return Value.integer(BigInt(literal));
  }
}

Variable lookups, of course, require consulting the variables map passed in EvaluateOptions, yielding whichever sort of value the variable was defined with:

async function evaluateVariable(
  identifier: Pointer.Expression.Variable,
  { variables }: EvaluateOptions,
): Promise<Value> {
  const value = variables[identifier];
  if (typeof value === "undefined") {
    throw new Error(`Unknown variable with identifier ${identifier}`);
  }

  return value;
}

Evaluating arithmetic operations​

Arithmetic is ordinary integer arithmetic: each operand is evaluated and taken as an integer (a bytes operand is read as the non-negative integer its bytes encode), and the result is an integer with no width. A small helper performs this coercion wherever the schema expects an integer:

/**
 * Evaluate an expression where an integer is expected, coercing bytes
 */
async function evaluateInteger(
  expression: Pointer.Expression,
  options: EvaluateOptions,
): Promise<bigint> {
  return Value.toInteger(await evaluate(expression, options));
}

With operands as integers, the five operations differ only in how they combine them. Note that sums and products accept any number of operands, while differences, quotients, and remainders take exactly two:

async function evaluateArithmetic(
  expression: Pointer.Expression.Arithmetic,
  options: EvaluateOptions,
): Promise<Value> {
  const [[operation, operandExpressions]] = Object.entries(expression) as [
    string,
    Pointer.Expression[],
  ][];

  const operands = await Promise.all(
    operandExpressions.map((operand) => evaluateInteger(operand, options)),
  );

  switch (operation) {
    case "$sum":
      return Value.integer(operands.reduce((sum, value) => sum + value, 0n));
    case "$difference": {
      const [a, b] = operands;
      return Value.integer(a > b ? a - b : 0n);
    }
    case "$product":
      return Value.integer(
        operands.reduce((product, value) => product * value, 1n),
      );
    case "$quotient": {
      const [a, b] = operands;
      return Value.integer(a / b);
    }
    case "$remainder": {
      const [a, b] = operands;
      return Value.integer(a % b);
    }
  }

  throw new Error(`Unknown arithmetic operation ${operation}`);
}

Note how $difference operates on unsigned values only by bounding the result below at 0, and how $quotient uses integer division only.

Evaluating resize expressions​

This schema provides the { "$sized<N>": <expression> } and { "$wordsized": <expression> } constructs to allow explicitly resizing a subexpression. A resize always produces bytes of the requested width, and so is the way to give an integer a width; this implementation encodes an integer as its minimal big-endian bytes and then uses the Data.prototype.resizeTo() method for both sorts.

async function evaluateResize(
  expression: Pointer.Expression.Resize,
  options: EvaluateOptions,
): Promise<Value> {
  const [[operation, subexpression]] = Object.entries(expression);

  const newLength = Pointer.Expression.Resize.isToNumber(expression)
    ? Number(operation.match(/^\$sized([1-9]+[0-9]*)$/)![1])
    : 32;

  const value = await evaluate(subexpression, options);

  return Value.bytes(Value.toData(value).resizeTo(newLength));
}

Evaluating keccak256 hashes​

Many data types in storage are addressed by way of keccak256 hashing. This process is somewhat non-trivial because the bytes width of the inputs and the process for concatenating them must match compiler behavior exactly.

See Solidity's Layout of State Variables in Storage documentation for an example of how one high-level EVM language makes heavy use of hashing to allocate persistent data.

Because the hash is taken over the operands' concatenated bytes, each operand must evaluate to bytes. This helper evaluates the operands of a width-sensitive operation and rejects a bare integer with an error that names the offending operand and suggests the fix:

/**
 * Evaluate the operands of a width-sensitive operation (`$concat`,
 * `$keccak256`), each of which must evaluate to bytes
 */
async function evaluateBytesOperands(
  operation: "$concat" | "$keccak256",
  operands: Pointer.Expression[],
  options: EvaluateOptions,
): Promise<Data[]> {
  return await Promise.all(
    operands.map(async (operand, index) => {
      const value = await evaluate(operand, options);

      if (Value.isInteger(value)) {
        throw new Error(
          [
            `Operand ${index} of ${operation} (${JSON.stringify(operand)}) `,
            `evaluates to the integer ${value.value}, which has no byte `,
            `width; give it a width with $wordsized or $sizedN`,
          ].join(""),
        );
      }

      return value.data;
    }),
  );
}

With every operand's width guaranteed, hashing is a matter of concatenating and applying the hash function:

async function evaluateKeccak256(
  expression: Pointer.Expression.Keccak256,
  options: EvaluateOptions,
): Promise<Value> {
  const operands = await evaluateBytesOperands(
    "$keccak256",
    expression.$keccak256,
    options,
  );

  const preimage = Data.zero().concat(...operands);

  return Value.bytes(Data.fromBytes(keccak256(preimage)));
}

Evaluating concatenation​

Byte concatenation reuses the same operand helper: evaluate the operands, requiring each to be bytes, and join them together, preserving the byte width of each operand.

async function evaluateConcat(
  expression: Pointer.Expression.Concat,
  options: EvaluateOptions,
): Promise<Value> {
  const operands = await evaluateBytesOperands(
    "$concat",
    expression.$concat,
    options,
  );

  return Value.bytes(Data.zero().concat(...operands));
}

Evaluating property lookups​

Pointer expressions can compose values taken from the properties of other, named regions. This not only provides a convenient way to avoid duplication when writing pointer expressions, but also it is necessary for types with particularly complex data allocations.

Currently, the specification defines lookup operations for three properties: offset, length, and slot. Runtime checks are required to prevent accessing properties that aren't available on the target region (e.g. memory regions do not contain a slot property).

A region's slot, offset, and length are positions and counts, so a lookup evaluates to an integer. Since all of these lookups function in the same way, this reference implementation needs only a single evaluateLookup<O extends "slot" | "offset" | "length"> function:

async function evaluateLookup<O extends Pointer.Expression.Lookup.Operation>(
  operation: O,
  lookup: Pointer.Expression.Lookup.ForOperation<O>,
  options: EvaluateOptions,
): Promise<Value> {
  const { regions } = options;

  const identifier = lookup[operation];
  const region = regions[identifier];
  if (!region) {
    throw new Error(`Region not found: ${identifier}`);
  }

  const property = Pointer.Expression.Lookup.propertyFrom(operation);

  const data = region[property as keyof typeof region] as Data | undefined;

  if (typeof data === "undefined") {
    throw new Error(
      `Region named ${identifier} does not have ${property} needed by lookup`,
    );
  }

  return Value.integer(data.asUint());
}

(The use of generic types here serves mostly to appease the type-checker; the minimal type safety it affords is insignificant compared to runtime data consistency concerns, which hopefully the implementation makes clear via its use of runtime definedness checks.)

Evaluating machine state reads​

Finally, the last kind of expression defined by this specification is for reading raw data from the machine state. A Pointer.Expression.Read should evaluate to the raw bytes stored at runtime in the region identified by a particular name; naturally, its result is bytes, whose width is the length of the region read.

Thanks to evaluate()'s requirement that its input regions-by-name map contains only concrete Cursor.Region objects, and by leveraging the existing read() functionality, this function presents no surprises:

async function evaluateRead(
  expression: Pointer.Expression.Read,
  options: EvaluateOptions,
): Promise<Value> {
  const { state: _state, regions } = options;

  const identifier = expression.$read;
  const region = regions[identifier];
  if (!region) {
    throw new Error(`Region not found: ${identifier}`);
  }

  return Value.bytes(await read(region, options));
}

Note on "$this" region lookups​

Astute readers might notice that these docs contain no mention until now about how to implement support for expressions that reference the region in which they are defined, a mechanism the schema permits via the special region name identifier "$this".

Performing read operations against "$this" region is meaningless since this schema does not afford any mechanism for defining regions recursively down to a base case (or similar composition). Thus, the only syntactic construct for self-referential reads resembles, e.g., defining a storage region whose slot is { $read: "$this" }. Evaluating this slot would require knowing the slot before knowing where to read, and knowing the slow requires knowing the machine value, ad nauseum.

Property lookup expressions, on the other hand, are completely acceptable—provided they do not include circular references of any cycle length.

Since the evaluate<.*>() functions here are written to accept only one expression at a time, this reference implementation relegates this concern to a higher-level module; proper use of evaluate() here requires its options.regions map to include a pre-evaluated (albeit partial) "$this" region.

The logic for creating "$this" regions and calling evaluate() correctly is described in the section pertaining to that area of the code. Be forewarned that this reference implementation takes a naïve trial-and-error approach for determining property evaluation order; implementations requiring a more robust strategy will need to do some amount of pre-processing.