Lab 13: Tables (Milestone 9)

Background

You will build src/table.rs — the array part, the insertion-ordered hash part, key normalization, #, pairs, and ipairs — plus the seven table opcodes and the parser support for constructors, indexing, and method calls.

At the end, Ember has data structures.

Why This Lab Matters

This is the first heap object. Everything about identity, aliasing, and GC edges starts here, and Lab 15 will trace exactly what you build.
ADR-008 (insertion order) is a promise you cannot withdraw. Make it deliberately.
The array/hash split is what makes a single data structure viable. Without it, every list index is a hash probe.

Prerequisites

Section 3 complete; differential tests green.
Tables read.
The opcode reference, group 9 open.

Predict First

local a = {} local b = a b.x = 1 — what is a.x? What does that say about Value::Table?
{} == {} — and why?
t[1.0] = 5; return t[1] — what, and what must the implementation do?
t = {}; t[2]=2; t[3]=3; t[1]=1 — how many entries end up in the array part?
#{1, 2, nil, 4} — what does Lua give? What will Ember give, and is that a divergence?
local t = {b=1, a=2, c=3} then for k in pairs(t) — what order, and would it be the same on another machine?
t[0/0] = 1 — what happens, and why must it?

Step 1: The Table Type

Write src/table.rs per the concept chapter: array, entries, index, meta. Start with a HashMap<HashKey, u32> mapping keys to positions in entries.

#![allow(unused)]
fn main() {
/// A table key, hashable and exactly-comparable. Floats key by BITS for the
/// same reason constants do — except that `normalize` has already converted
/// integral floats to integers, so only genuinely fractional floats reach here.
#[derive(PartialEq, Eq, Hash)]
enum HashKey { Bool(bool), Int(i64), FloatBits(u64), Str(GcRef<EmberStr>), Obj(u64) }
}

Warning: HashKey::Obj is the stable object id assigned at allocation, not the heap slot index. A collection can free slot 7 and reuse it; if the id were the slot, a table key's hash would silently change and the entry would become unfindable. This is a bug that only appears after a GC, which means Lab 15, which means "it worked yesterday". Assign a monotonic u64 id in Heap::alloc and hash that.

Step 2: `get`, `set`, and the Fast Path

Write them per the concept chapter, in this order — and test after each:

Hash part only. Everything works, nothing is fast.
Add the array fast path in get.
Add array growth in set (append at len + 1).
Add migrate_from_hash.
Add trim_array on trailing nil assignment.

Step 4 is the one to write a test for before writing the code:

#![allow(unused)]
fn main() {
#[test]
fn out_of_order_fill_ends_up_in_the_array_part() {
    let mut t = Table::new();
    t.set(Value::Integer(2), Value::Integer(2)).unwrap();   // hash part
    t.set(Value::Integer(3), Value::Integer(3)).unwrap();   // hash part
    t.set(Value::Integer(1), Value::Integer(1)).unwrap();   // grows array, MIGRATES 2 and 3
    assert_eq!(t.array_len(), 3, "keys 2 and 3 must migrate when key 1 arrives");
    assert_eq!(t.hash_len(), 0);
}
}

Step 3: Key Rules

#![allow(unused)]
fn main() {
fn check_key(key: Value) -> Result<Value> {
    match key {
        Value::Nil => Err(rt("table index is nil")),
        // A NaN key could never be found again, because NaN != NaN. Lua rejects
        // it rather than leaking an unreachable entry.
        Value::Float(f) if f.is_nan() => Err(rt("table index is NaN")),
        k => Ok(normalize(k)),
    }
}
}

Verify both against the reference before you believe the messages:

lua -e 't = {}; t[nil] = 1'    # table index is nil
lua -e 't = {}; t[0/0] = 1'    # table index is NaN
lua -e 't = {}; t[1.0] = 5; print(t[1])'   # 5

Note: Reading t[nil] is not an error — it returns nil. Only assigning is. That asymmetry is deliberate in Lua (a lookup with a nil key is a common intermediate result; storing one is always a bug) and it needs its own test.

Step 4: The Opcodes

Implement NEW_TABLE, GET_INDEX, SET_INDEX, GET_FIELD, SET_FIELD, SET_LIST, and SELF_FIELD per the reference.

SELF_FIELD is the one with a subtlety. t:m(a) must evaluate t once:

#![allow(unused)]
fn main() {
// t:m(a)  compiles to:   <t>  SELF_FIELD k(m)  <a>  CALL 2, 1
// SELF_FIELD replaces [t] with [t.m, t], so the receiver is the first argument
// and `t` was evaluated exactly once — which matters when `t` is `f()`.
Op::SelfField(k) => {
    let recv = self.pop();
    let name = self.chunk().constants[k as usize];
    let method = self.index(recv, name, span)?;     // goes through __index in Lab 18
    self.push(method);
    self.push(recv);
}
}

Step 5: Parser and Compiler Support

Table constructors, indexing, and method calls in suffixed_expr — the suffix loop stubbed out in Lab 7:

#![allow(unused)]
fn main() {
TokenKind::Dot => {
    self.advance();
    let name = self.name()?;
    // DESUGARED: t.k becomes Index { key: Str("k") }, with the STR node's span
    // pointing at `k` — not at the whole expression. That is what makes the
    // caret land correctly in Lab 24's diagnostics.
    Expr::Index { object: Box::new(e), key: Box::new(Expr::Str { .. }), span }
}
}

The constructor mixes three field forms and the array-vs-hash decision is syntactic:

{ 10, 20, x = 1, [k] = v, 30 }
--  ^   ^         ^   ^     ^
--  positional    named  computed   positional continues at 3

#![allow(unused)]
fn main() {
// Positional fields accumulate on the stack and flush with SET_LIST every 50,
// so a 10,000-element literal does not need 10,000 stack slots at once.
const FIELDS_PER_FLUSH: u16 = 50;
}

Checkpoint question. In {f()} the call is last, so it contributes all its values. In {f(), 1} it is not. Which function decides that, and where did you write it?

Step 6: `#`, `pairs`, and `ipairs`

#![allow(unused)]
fn main() {
/// Ember's `#`: the array length after trailing nils are trimmed.
/// DIVERGENCE from Lua, which permits ANY border on a table with holes.
/// Ours is deterministic; Lua's is not. Documented in lua-differences.md.
pub fn len(&self) -> i64 { self.array.len() as i64 }
}

ipairs stops at the first nil; pairs walks the array part then entries in insertion order, skipping tombstones. Generic for needs no new opcodes — it lowers to a call, a nil test, and jumps:

   for k, v in pairs(t) do BODY end

   <pairs(t)>            → iterator, state, control
   loop:
     <call iterator(state, control)>       CALL 2, 2
     GET_LOCAL k ; LOAD_NIL ; EQ           is the first result nil?
     JUMP_IF_FALSE body
     JUMP exit
   body:
     ...
     JUMP loop
   exit:

Write that lowering out by hand once, then check it with ember disassemble.

The Trace

$ ember disassemble -e 'local t = {10, 20, name = "x"} return t.name'

constants: [0] "name"   [1] "x"
0000     1  NEW_TABLE
0001     |  LOAD_INT     10
0002     |  LOAD_INT     20
0003     |  SET_LIST     2 0                ; t[1..2]
0004     |  LOAD_CONST   1          ; "x"
0005     |  SET_FIELD    0          ; "name"
0006     |  GET_LOCAL    0          ; t
0007     |  GET_FIELD    0          ; "name"
0008     |  RETURN       1

Now the representation itself:

$ ember run --trace-tables -e 'local t = {} t[2]=2 t[3]=3 t[1]=1 t.x="s" return #t'

table#1 new            array=[]           hash={}
table#1 set 2          array=[]           hash={2}          ← not contiguous yet
table#1 set 3          array=[]           hash={2,3}
table#1 set 1          array=[1]          hash={2,3}        ← grew by one...
table#1   migrate 2    array=[1,2]        hash={3}          ← ...then MIGRATED
table#1   migrate 3    array=[1,2,3]      hash={}
table#1 set "x"        array=[1,2,3]      hash={"x"}
3

The two migrate lines are the lab. Without them, t[2] stays a hash probe forever, and a program that fills a result table in a non-sequential order pays for it on every read.

And the determinism check — run it ten times, and on a second machine if you have one:

$ for i in $(seq 10); do
    ember run -e 'local t={} t.b=1 t.a=2 t.c=3 local s="" for k in pairs(t) do s=s..k end return s'
  done
bac
bac
... (ten identical lines)

$ for i in $(seq 3); do lua -e 't={} t.b=1 t.a=2 t.c=3 s="" for k in pairs(t) do s=s..k end print(s)'; done

Lua's may or may not vary between runs depending on its build and the string hash seed. That difference is ADR-008, observed. Put both outputs in docs/learning/08-tables.md.

Expected Output

$ ember run -e 'local a={} local b=a b.x=1 return a.x'
1
$ ember run -e 'return ({}) == ({})'
false
$ ember run -e 'local t={} t[1.0]=5 return t[1]'
5
$ ember run -e 'local t={} t[0/0]=1'
<argv>:1:14: error: table index is NaN
$ ember run -e 'local t={} return t[nil]'
nil
$ ember run -e 'local Account={} Account.__index=Account
                function Account.new(b) return setmetatable({balance=b},Account) end
                function Account:deposit(n) self.balance=self.balance+n end
                local a=Account.new(100) a:deposit(50) return a.balance'
150

That last one needs Lab 18's __index; until then it errors. Keep it in the corpus as a !pending case so it turns green when Lab 18 lands.

Debugging Steps

`t[1]` and `t[1.0]` are different entries

normalize is missing or runs after hashing.

The array part never grows on an out-of-order fill

migrate_from_hash is missing. See the Step 2 test.

`pairs` order changes between runs

You are iterating the HashMap rather than entries. The HashMap is only an index into entries; iteration must go through the Vec.

A table used as a key stops being findable after a GC

You hashed the heap slot index instead of a stable object id. See the Step 1 warning.

`#t` disagrees with Lua

Expected — Ember's is deterministic and Lua's is any border. Confirm it is your documented behavior, then add the divergence entry.

`{f()}` gets one value instead of all of them

compile_exprlist is not being used for constructor fields, or Want::All is not passed for the final positional field.

`t:m()` evaluates `t` twice

You desugared to t.m(t, ...) in the parser instead of emitting SELF_FIELD. Visible when the receiver is a call: f():m() calls f twice.

Experiment

CLAIM. The array part is not a micro-optimization; it changes the complexity class of ordinary list code.

METHOD. Benchmark for i = 1, 100000 do sum = sum + t[i] end with (a) the array fast path enabled and (b) get/set forced down the hash path with a feature flag. Then benchmark a sparse table (t[i*1000]) under both.

PREDICTION. What ratio for the dense case? For the sparse case, which should be identical — and if yours is not, what does that tell you?

RESULT. Record both in docs/learning/08-tables.md. The sparse case is the control; if it moves, your "fast path" is doing work on tables it does not apply to.

Test

#![allow(unused)]
fn main() {
#[test]
fn tables_have_reference_identity() {
    assert_eq!(run("local a={} local b=a b.x=1 return a.x"), "1");
    assert_eq!(run("return tostring(({}) == ({}))"), "false");
}

#[test]
fn float_keys_normalize_to_integers() {
    assert_eq!(run("local t={} t[1.0]=5 return t[1]"), "5");
    assert_eq!(run("local t={} t[1]=5 return t[1.0]"), "5");
    // ...but a FRACTIONAL float stays a float key.
    assert_eq!(run("local t={} t[1.5]=5 return tostring(t[1])"), "nil");
}

#[test]
fn nil_and_nan_keys_are_assignment_errors_but_not_lookup_errors() {
    assert_eq!(err("local t={} t[nil]=1").kind, ErrorKind::Runtime);
    assert_eq!(err("local t={} t[0/0]=1").kind, ErrorKind::Runtime);
    assert_eq!(run("local t={} return tostring(t[nil])"), "nil");   // lookup is FINE
}

#[test]
fn pairs_order_is_insertion_order_and_deterministic() {
    // ADR-008. This test would FAIL under a randomly-seeded hash iteration,
    // which is exactly the property it exists to pin.
    let src = "local t={} t.b=1 t.a=2 t.c=3 local s='' for k in pairs(t) do s=s..k end return s";
    let first = run(src);
    for _ in 0..20 { assert_eq!(run(src), first, "pairs order must be stable"); }
    assert_eq!(first, "bac");
}

#[test]
fn array_part_absorbs_out_of_order_integer_keys() {
    let t = build("local t={} t[2]=2 t[3]=3 t[1]=1 return t");
    assert_eq!(t.array_len(), 3);
    assert_eq!(t.hash_len(), 0);
}

#[test]
fn table_keys_survive_a_collection() {
    // The stable-object-id test. Fails if HashKey::Obj uses the slot index.
    assert_eq!(run("local k={} local t={} t[k]=1 collectgarbage() return t[k]"), "1");
}

#[test]
fn method_calls_evaluate_the_receiver_once() {
    assert_eq!(run("local n=0
                    local function f() n=n+1 return {m=function() return 1 end} end
                    f():m() return n"), "1");
}
}

Challenge Extensions

Lua's rehash counting. Implement computesizes: histogram the integer keys by power-of-two bucket and choose the array size n such that more than n/2 of 1..n are present. Compare against Ember's grow-on-append on a descending fill (t[1000] down to t[1]), which Ember's design never migrates.
Open addressing. Replace the Vec + HashMap with a single open-addressed table that keeps insertion order via a linked list through the entries — the design indexmap uses. Measure memory and lookup time.
Tombstone compaction. Compact entries when tombstones exceed half. Prove it cannot run during an active next, and write the test that would have caught it if it could.
# on a table with holes. Implement Lua's binary-search border finder and compare with Ember's trimmed-array answer on twenty random hole patterns. Which is more useful? Which is more surprising?
Weak-key tables. Requires collector support; do it after Lab 15 and note what it costs the marking phase.

Deliverables

Table with an array part, an insertion-ordered hash part, and a meta field (unused until Lab 18).
normalize, check_key; nil/NaN assignment errors, nil lookup returns nil.
Out-of-order integer fills migrate into the array part.
All seven table opcodes; SELF_FIELD evaluates the receiver once.
Constructors with positional, named, and computed fields; SET_LIST flushing.
#, pairs, ipairs; generic for lowered with no new opcodes.
pairs order stable across 20 runs and documented as ADR-008.
Table keys hash a stable object id, with a post-collection test.
--trace-tables shows array/hash transitions and migrations.
The array-part experiment recorded, including the sparse control.
docs/adr/ADR-008-deterministic-iteration.md and docs/learning/08-tables.md written.
Differential tests still green.

Validation / Self-check

Why does t[1.0] find t[1]? Where in set does that happen?
Why is assigning a nil key an error but reading one not?
What does migrate_from_hash fix? Give the three-line program.
Why must table keys hash a stable object id rather than the heap slot?
Why does generic for need no new opcodes, and what does it lower to?
Why does t:m() need SELF_FIELD rather than a parser desugaring? Give the program that shows the difference.
State ADR-008, and describe the experiment that shows Lua behaving differently.
In the array-part benchmark, why is the sparse case the control?

Next: Lab 14 — Closures and Upvalues.

Open-Source Engineer & Contributor