Optionals and Nullable Types

This page describes the current SSA builder and backend implementation. Its unversioned esp examples are compatibility snapshots, still accepted by the reader. Start with the new text walkthrough for esper 1 syntax and the roadmap for the library-first migration boundary.

An optional is a type with one more inhabitant than the type it wraps: every value T can hold, plus one that says there is no value. Esper has no optional type, and a frontend does not want one, because the whole question is which representation to use and each answer costs something different at every use site.

There are three, and a frontend usually picks per type rather than once:

The tagged pair is the only one that works for every T. The other two are free at construction and cost a word less everywhere, but each needs something to be true about T before it can be used at all.

The unions guide covers the general tagged-variant machinery; this page is about the choice and about the check at the use site.

The null pointer

For a T that is already a pointer, address zero is not a valid object, so it can stand for the empty case at no cost. Construction is the identity function: Some(p) is p. Reading is a compare against zero.

eqz is the compare to reach for, since it takes one operand and no constant. The two arms are the value and the panic path.

func unwrap(opt: Optional<*Int32>) -> Int32 {
    guard let p = opt else { panic(.nullUnwrap) }
    return p.pointee
}

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef panic_params[1] = {ESP_TYPE_I32};
  esper_func_declare(unit, "rt_panic_null", panic_params, 1, NULL, 0, true);

  EsperTypeRef params[1] = {ESP_TYPE_PTR};
  EsperTypeRef rets[1] = {ESP_TYPE_I32};
  EsperBuilder *b = esper_build_begin(unit, "unwrap", params, 1, rets, 1);

  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId some = esper_build_block(b, "some");
  EsperBlockId none = esper_build_block(b, "none");

  esper_build_bind(b, entry);
  EsperVal opt = esper_build_param(b, 0);
  EsperVal is_none = esper_build_unary(b, ESP_OP_EQZ, ESP_TYPE_I32, opt);
  esper_build_jmp_if(b, is_none, none, some);

  esper_build_bind(b, some);
  EsperVal value = esper_build_load(b, ESP_OP_LOAD, ESP_TYPE_I32, opt);
  esper_build_ret(b, &value, 1);

  // The message lives in the runtime; what crosses the boundary is its index.
  esper_build_bind(b, none);
  EsperVal site = esper_build_ldi(b, ESP_TYPE_I32, 7);
  esper_build_call(b, ESP_TYPE_VOID, "rt_panic_null", &site, 1);
  esper_build_unreachable(b);

  if (!esper_build_end(b))
    fprintf(stderr, "unwrap: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}

func extern $rt_panic_null(i32)
func $unwrap(%0 ptr) -> i32 {
entry:
  %1 = eqz i32 %0
  jmp.if %1 none some

some:
  %3 = load i32 %0
  ret i32 %3

none:
  %5 = ldi i32 7
  call $rt_panic_null, %5
  unreachable
}

eqz yields i32 rather than a distinct boolean type, so the result is an ordinary value that jmp.if reads as zero or non-zero. Note that the panic handler takes an integer rather than a message: Esper has no string constant, so what identifies the failure is an index into the frontend’s own table. Embedding covers the symbols the frontend supplies and how they resolve under the interpreter as well as the linker.

The limit of this representation is that it only exists for pointers. There is no Optional<Optional<*T>>: nesting collapses, because the inner and outer empty cases are the same bit pattern.

The tagged pair

The general answer is a flag beside the payload. It works for every T, including another optional, and it is the representation a frontend falls back to when nothing better applies.

Declaring it as a struct in the unit’s type table rather than as raw memory is worth doing: the members keep their names in the printed IR, the backend picks the layout, and SROA can take the aggregate apart again when the producer and the consumer end up in the same function.

struct OptI32 { var hasValue: Int32; var value: Int32 }

func some(_ v: Int32) -> OptI32 { OptI32(hasValue: 1, value: v) }
func unwrapOr(_ o: OptI32, _ fallback: Int32) -> Int32 { ... }

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef members[2] = {ESP_TYPE_I32, ESP_TYPE_I32};
  const char *names[2] = {"has_value", "value"};
  uint32_t opt = esper_unit_add_struct(unit, "OptI32", members, names, 2, false);

  // A table index is not a type; esper_tref_agg turns it into one.
  EsperTypeRef opt_ty = esper_tref_agg(opt);

  EsperTypeRef some_params[1] = {ESP_TYPE_I32};
  EsperTypeRef some_rets[1] = {opt_ty};
  EsperBuilder *b = esper_build_begin(unit, "some", some_params, 1, some_rets, 1);

  esper_build_bind(b, esper_build_block(b, "entry"));
  EsperVal one = esper_build_ldi(b, ESP_TYPE_I32, 1);
  EsperVal fields[2] = {one, esper_build_param(b, 0)};
  EsperVal box = esper_build_struct_new(b, opt, fields, 2);
  esper_build_ret(b, &box, 1);
  esper_build_end(b);
  esper_builder_free(b);

  EsperTypeRef unwrap_params[2] = {opt_ty, ESP_TYPE_I32};
  EsperTypeRef unwrap_rets[1] = {ESP_TYPE_I32};
  b = esper_build_begin(unit, "unwrap_or", unwrap_params, 2, unwrap_rets, 1);

  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId present = esper_build_block(b, "present");
  EsperBlockId absent = esper_build_block(b, "absent");

  esper_build_bind(b, entry);
  EsperVal tag = esper_build_field(b, ESP_TYPE_I32, esper_build_param(b, 0), 0);
  esper_build_jmp_if(b, tag, present, absent);

  esper_build_bind(b, present);
  EsperVal held = esper_build_field(b, ESP_TYPE_I32, esper_build_param(b, 0), 1);
  esper_build_ret(b, &held, 1);

  esper_build_bind(b, absent);
  EsperVal fallback = esper_build_param(b, 1);
  esper_build_ret(b, &fallback, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "unwrap_or: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}

type OptI32 = struct {
  i32 has_value,
  i32 value,
}

func $some(%0 i32) -> OptI32 {
entry:
  %1 = ldi i32 1
  %2 = struct.new OptI32 %1, %0
  ret OptI32 %2
}

func $unwrap_or(%0 OptI32, %1 i32) -> i32 {
entry:
  %2 = field i32 %0, 0
  jmp.if %2 present absent

present:
  %4 = field i32 %0, 1
  ret i32 %4

absent:
  ret i32 %1
}

Two things in the C are worth pointing out. esper_unit_add_struct returns an index into the type table rather than a type, so the index goes through esper_tref_agg to become one. And the tag feeds jmp.if directly rather than through a comparison, because a non-zero flag is already the condition.

The payload does not have to be meaningful in the empty case. Nothing reads it, so None can leave it whatever struct.new was handed, and a frontend that wants a canonical None writes a zero there for the sake of comparison and hashing rather than for correctness.

The extra word is only paid where the optional survives as a value. When the construction and the read end up in one function, scalar replacement of aggregates rewrites each field to the operand struct.new was handed, and the branch then folds on the constant tag. A wrapped value unwrapped in place costs nothing at all:

func $use(%0 i32) -> i32 {
entry:
  %1 = ldi i32 1
  %2 = struct.new OptI32 %1, %0
  %3 = field i32 %2, 0
  %4 = field i32 %2, 1
  jmp.if %3 present absent

present:
  ret i32 %4

absent:
  %7 = ldi i32 0
  ret i32 %7
}

With opt_sroa, opt_cf_opt and opt_dce enabled, that becomes:

func $use(%0 i32) -> i32 {
entry:
  nop
  nop
  nop
  nop
  nop

present:
  ret i32 %0
}

The niche

When T provably cannot hold some bit pattern, that pattern is the empty case and the optional is the same width as T. A Unicode scalar never exceeds 0x10FFFF, an enum with seven cases never exceeds six, a length is never negative. Each of those leaves room for a sentinel.

Construction is again the identity function. Reading is a compare against the sentinel, and the only difference from the null-pointer form is that the compare needs a constant.

This example ends the empty path with trap rather than a call, which is the other way to end a panic path: it costs one instruction and says nothing.

func unwrapChar(_ c: Optional<Unicode.Scalar>) -> Unicode.Scalar {
    guard c != .none else { trap() }   // .none is encoded as ~0
    return c
}

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef params[1] = {ESP_TYPE_I32};
  EsperTypeRef rets[1] = {ESP_TYPE_I32};
  EsperBuilder *b = esper_build_begin(unit, "unwrap_char", params, 1, rets, 1);

  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId present = esper_build_block(b, "present");
  EsperBlockId absent = esper_build_block(b, "absent");

  esper_build_bind(b, entry);
  EsperVal code = esper_build_param(b, 0);
  EsperVal niche = esper_build_ldi(b, ESP_TYPE_I32, -1);
  EsperVal is_none = esper_build_binary(b, ESP_OP_EQ, ESP_TYPE_I32, code, niche);
  esper_build_jmp_if(b, is_none, absent, present);

  esper_build_bind(b, present);
  esper_build_ret(b, &code, 1);

  esper_build_bind(b, absent);
  esper_build_trap(b);

  if (!esper_build_end(b))
    fprintf(stderr, "unwrap_char: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}

func $unwrap_char(%0 i32) -> i32 {
entry:
  %1 = ldi i32 -1
  %2 = eq i32 %0, %1
  jmp.if %2 absent present

present:
  ret i32 %0

absent:
  trap
}

A niche is a claim about T that the IR cannot check. Nothing stops a caller from passing -1 as an ordinary scalar, and the result is that a present value reads as absent. The frontend owns that invariant, and the place to enforce it is wherever a value of T enters from outside: a cast, a decode, a foreign call.

The reason niches are worth the bookkeeping is that they compose. An Optional<Optional<Unicode.Scalar>> can use 0x110000 and 0x110001 as two distinct empty cases and stay one word wide, where two nested tagged pairs would be four.

What the check costs after optimization

The unwrap check is written at every use site because the frontend does not generally know whether the value is present. Where it does know, the check should disappear, and it does: the comparison is ordinary arithmetic on ordinary values, so constant folding evaluates it and control-flow simplification deletes the arm that cannot be taken.

Here is a frontend that has just constructed a present value and immediately unwrapped it, emitting the check exactly as it would anywhere else. The empty arm is a bare unreachable, which is the frontend asserting that this path cannot be entered.

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef rets[1] = {ESP_TYPE_I32};
  EsperBuilder *b = esper_build_begin(unit, "answer", NULL, 0, rets, 1);

  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId present = esper_build_block(b, "present");
  EsperBlockId absent = esper_build_block(b, "absent");

  esper_build_bind(b, entry);
  EsperVal code = esper_build_ldi(b, ESP_TYPE_I32, 42);
  EsperVal niche = esper_build_ldi(b, ESP_TYPE_I32, -1);
  EsperVal is_none = esper_build_binary(b, ESP_OP_EQ, ESP_TYPE_I32, code, niche);
  esper_build_jmp_if(b, is_none, absent, present);

  esper_build_bind(b, present);
  esper_build_ret(b, &code, 1);

  esper_build_bind(b, absent);
  esper_build_unreachable(b);

  if (!esper_build_end(b))
    fprintf(stderr, "answer: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}

func $answer() -> i32 {
entry:
  %0 = ldi i32 42
  %1 = ldi i32 -1
  %2 = eq i32 %0, %1
  jmp.if %2 absent present

present:
  ret i32 %0

absent:
  unreachable
}

Under -O1 the whole check goes, and the empty block with it:

func $answer() -> i32 {
entry:
  %0 = ldi i32 42
  nop
  nop
  nop

present:
  ret i32 %0
}

The nops are the holes the deleted instructions left, since an SSA id is a position and nothing renumbers. A backend emits nothing for them.

Two limits are worth knowing before relying on this.

The fold only happens when the arm is a bare unreachable. Ending the empty path with a call to a panic handler, or with trap, keeps the branch, because both are observable effects and deleting the branch would delete them. That is the right answer rather than a missed optimization, and Embedding sets out the difference between the three endings. So the frontend chooses: unreachable where the language guarantees the case cannot happen and the check should cost nothing, a call or a trap where reaching it is a real outcome.

The fold also needs the value to be a literal. Nothing in the IR says that an allocation returns a non-null pointer, so a null check on a pointer the frontend allocated one instruction earlier survives every pass:

entry:
  %0 = ldi i32 4
  %1 = salloc %0
  %2 = eqz i32 %1        // not folded: salloc has no known value
  jmp.if %2 empty present

A frontend that knows the pointer is non-null should not emit the check, rather than emitting it and expecting it to be removed.