Tables

Three concepts: the table as the only data structure, the hybrid array/hash representation, and identity and iteration order.

Lua has one aggregate type. Arrays, dictionaries, objects, classes, modules, sets, queues, and namespaces are all tables. Understanding why that works — and what it costs — is most of understanding Lua.

Concept 1: One Data Structure

1. Concept

A table is a mutable mapping from any value (except nil and NaN) to any value. t.name is sugar for t["name"]. There is nothing else.

2. Problem

Every language needs aggregates, and most provide several: arrays, hashes, records, objects, modules. Each one is a concept to learn, a syntax to remember, and an implementation to maintain. For a language designed to be embedded and taught to non-programmers, that is a large budget.

3. Mental model

A table is a hash map with a fast path for consecutive integer keys. Everything else — the object system, the module system, the standard library's namespaces — is a convention layered on top by metatables, not a language feature.

local array  = {10, 20, 30}          -- keys 1, 2, 3
local record = {name = "a", age = 3} -- keys "name", "age"
local mixed  = {10, 20, x = 1}       -- both, in ONE object
local set    = {[obj] = true}        -- any value as a key
local module = {}                    -- a namespace
function module.f() end              -- module["f"] = function...

4. Implementation

#![allow(unused)]
fn main() {
// src/table.rs
pub struct Table {
    /// Dense integer keys 1..=array.len(). array[i] holds t[i+1].
    /// A `nil` inside is a HOLE, not a terminator — see the `#` discussion.
    array: Vec<Value>,
    /// Everything else, in INSERTION ORDER. See Concept 3 and ADR-008.
    entries: Vec<Option<(Value, Value)>>,
    index: HashMap<HashKey, u32>,     // key → position in `entries`
    /// Set by setmetatable(); traced by the GC; see the metatables chapter.
    meta: Option<GcRef<Table>>,
}
}

The public API is two operations, and every syntactic form funnels into them:

#![allow(unused)]
fn main() {
impl Table {
    pub fn get(&self, key: Value) -> Value;                    // missing → Nil
    pub fn set(&mut self, key: Value, v: Value) -> Result<()>; // v == Nil → remove
}
}

t.name, t["name"], t:m(), and t[expr] are all get/set. The compiler emits GET_FIELD/GET_INDEX/SELF_FIELD — different opcodes, because a constant key allows a faster path and, later, an inline cache — but they land in the same two functions. If your implementation has two lookup code paths, they will diverge, and the divergence will be a metatable bug in Lab 18.

Two keys are errors, not silent successes:

#![allow(unused)]
fn main() {
match key {
    Value::Nil => return Err(rt("table index is nil")),
    // NaN != NaN, so a NaN key could never be found again. Lua rejects it
    // rather than leaking an unreachable entry. Verify:
    //   lua -e 't = {} t[0/0] = 1'  →  "table index is NaN"
    Value::Float(f) if f.is_nan() => return Err(rt("table index is NaN")),
    _ => {}
}
}

And one key must be normalized:

#![allow(unused)]
fn main() {
/// Lua 5.4 §3.4.7: a float key with an exact integer value is CONVERTED to an
/// integer. Without this, t[1] and t[1.0] are two entries that print identically
/// and neither can find the other's value.
fn normalize(key: Value) -> Value {
    if let Value::Float(f) = key {
        if f.floor() == f && f >= -(2f64.powi(63)) && f < 2f64.powi(63) {
            return Value::Integer(f as i64);
        }
    }
    key
}
}

Verify both against the reference: lua -e 't={} t[1.0]=5 print(t[1])' prints 5.

5. Alternatives

Option D is what a fast dynamic language does, and it is worth knowing the shape: V8 gives every object a hidden class describing its layout, and adding a property transitions the object to a new hidden class. Field access then becomes "check the class, load at a fixed offset", which inline caches exploit. Ember gets a taste of this in Section 7 without the transition machinery.

6. Decision

A. Ember is Lua-like; this is the defining decision of the language it imitates, and copying it is the point. The array part is what makes A tolerable — without it, t[1] would be a string- free hash lookup and every loop over a list would pay for it.

7. Tradeoffs

8. Production concerns

• nil values delete. t.x = nil removes the key. That means "present with value nil" is inexpressible, which is why Lua has no has_key distinct from get ~= nil, and why sentinel values (FALSE_SENTINEL) show up in real Lua libraries. Document it.
• #t is a border, not a count. For a table with holes, Lua explicitly allows any border. Run lua -e 'print(#{1,2,nil,4})', then decide what Ember does and write it down. Ember's choice: #t is array.len() after trailing nils are trimmed — deterministic, documented, and divergent from Lua's "any border" licence. That divergence is safer than Lua's, which is a fine reason for it, but it still goes in appendix/lua-differences.md.
• A table is a denial-of-service surface. for i = 1, 1e9 do t[i] = i end allocates until the process dies. The memory budget in Section 5 is what stops it, and the accounting hook lives in Table::set and Heap::alloc.
• Hash-collision attacks. If a host lets untrusted input become table keys, an attacker who can predict your hash function can force every key into one bucket and turn O(1) into O(n). This is the hashDoS class of vulnerability that hit PHP, Python, Ruby, and Java in 2011. Rust's default SipHash is collision-resistant and randomly seeded — which is exactly why swapping it for a faster hasher in Section 7 is a security decision, not just a performance one, and must be recorded as such.

9. References

rg -n 'luaH_get|luaH_getint|luaH_getshortstr|luaH_newkey' ltable.c
rg -n 'MAXTAGLOOP|luaV_finishget' lvm.c

• Lua's ltable.c — 800 lines for the whole thing. Read mainposition and luaH_newkey first.
• Lua 5.4 Reference Manual §3.4.7 (the # operator) — read the exact wording about borders.
• V8's "hidden classes" / Map design documents, for option D.

Concept 2: The Hybrid Array/Hash Representation

1. Concept

Every table has two parts: a Vec for dense integer keys starting at 1, and a hash map for everything else. One object, one identity, two storage strategies.

2. Problem

If t[1] were a hash lookup, then for i = 1, #t do sum = sum + t[i] end — the most common loop in any program — would hash an integer, probe a table, and chase a pointer on every iteration. Lists are the majority use of tables, and treating them as generic maps wastes most of the machine.

3. Mental model

t[3] is array[2] when it can be, and a hash probe when it cannot. The table decides which, by itself, on rehash. Neither the language nor the user ever sees the difference — except in performance and in #.

   local t = {10, 20, 30, name = "x", [100] = "sparse"}

   ┌─ Table ───────────────────────────────────────────────────────┐
   │  array: [10, 20, 30]              t[1] t[2] t[3]  → O(1) index │
   │  entries: [("name","x"), (100,"sparse")]   ← insertion order   │
   │  index:   {"name"→0, 100→1}                → O(1) hash probe   │
   │  meta:    None                                                 │
   └────────────────────────────────────────────────────────────────┘

4. Implementation

#![allow(unused)]
fn main() {
impl Table {
    pub fn get(&self, key: Value) -> Value {
        // The FAST PATH, first, with no hashing at all.
        if let Value::Integer(i) = normalize(key) {
            if i >= 1 && (i as usize) <= self.array.len() {
                return self.array[i as usize - 1];
            }
        }
        match self.index.get(&HashKey::of(key)) {
            Some(&pos) => self.entries[pos as usize].as_ref().map_or(Value::Nil, |e| e.1),
            None => Value::Nil,
        }
    }

    pub fn set(&mut self, key: Value, v: Value) -> Result<()> {
        let key = normalize(check_key(key)?);
        if let Value::Integer(i) = key {
            if i >= 1 && (i as usize) <= self.array.len() {
                self.array[i as usize - 1] = v;
                if v == Value::Nil && i as usize == self.array.len() { self.trim_array(); }
                return Ok(());
            }
            // Appending exactly at the end GROWS the array part, and may
            // migrate keys n+1, n+2, ... that were sitting in the hash part.
            if i as usize == self.array.len() + 1 && v != Value::Nil {
                self.array.push(v);
                self.migrate_from_hash();
                return Ok(());
            }
        }
        self.hash_set(key, v)
    }

    /// After growing the array by one, pull any now-contiguous integer keys
    /// out of the hash part. `t[2]=b; t[3]=c; t[1]=a` must end with all three
    /// in the array — the order the user writes them cannot matter.
    fn migrate_from_hash(&mut self) {
        while let Some(&pos) = self.index.get(&HashKey::int(self.array.len() as i64 + 1)) {
            let (_, v) = self.entries[pos as usize].take().unwrap();
            self.index.remove(&HashKey::int(self.array.len() as i64 + 1));
            self.array.push(v);
        }
    }
}
}

migrate_from_hash is the step people omit, and the test that catches it is t[2]=2; t[3]=3; t[1]=1 — written out of order, which real code does constantly (think of filling a result table from a sparse source). Without migration those stay in the hash part forever and every subsequent t[2] is a hash probe.

5. Alternatives

Lua's approach (B) is genuinely clever and worth reading: rehash in ltable.c builds a histogram of integer keys, then chooses the largest power of two n such that more than n/2 of the keys in 1..n are present. That guarantees the array part is never less than half full — a real space bound, computed in one pass.

6. Decision

A now; B is a challenge extension in Lab 13.

A gets the common cases (literal constructors, sequential appends, out-of-order fills) with twenty lines. B handles the case A does not — a table filled at t[1000] down to t[1] never grows its array under A, because no single set ever lands exactly at len+1 first — and getting there is a good exercise once you have a benchmark that shows it matters.

7. Tradeoffs

8. Production concerns

• A hole in the array part is a nil, not a terminator. t = {1,2,3}; t[2] = nil leaves [1, nil, 3]. get must return Nil, not skip; ipairs must stop at the first nil; # must do whatever you documented. Three different behaviors for one representation state — test all three.
• Shrinking is a policy. Ember trims trailing nils on assignment and never otherwise shrinks. Lua shrinks only on rehash. Neither returns memory promptly, which matters for a long-lived table used as a queue — a real pattern, and a real leak. Document it; a challenge fixes it.
• The array part is not a GC exception. Every Value in array and in entries — keys as well as values — is an edge the collector must trace. Forgetting keys is the classic missing-edge bug and it only shows up when a key is a table or a computed string.

9. References

• Lua's ltable.c: rehash, computesizes, numusearray, numusehash. The counting algorithm is ~60 lines and the comments explain the invariant.
• The Implementation of Lua 5.0, §4 ("Tables") — the design rationale from the authors, in two pages.
• Lua's collision strategy is worth a separate look: mainposition plus Brent's variation, where a colliding node is moved into a free slot and chained, so a table is one or two allocations total rather than one per entry. Compare with Rust's HashMap (SwissTable), which is also open-addressed but with a very different probe sequence.

Concept 3: Identity and Iteration Order

1. Concept

Tables have reference identity: {} ~= {}, and assigning a table copies the handle, not the contents. And iteration has an order, which is either specified or it is not.

2. Problem

local a = {1, 2, 3}
local b = a
b[1] = 99
print(a[1])       -- 99. Same table.

That is aliasing, and it is the first time in the curriculum that two names denote one object. Meanwhile:

for k, v in pairs(t) do io.write(k) end

What order? Lua's manual says unspecified. That is fine for a scripting language and unacceptable for a policy engine that must produce the same ranking on two replicas.

3. Mental model

Identity is the handle. Two Value::Table values are the same table if and only if their GcRef indices match — which is why == on tables compares handles, not contents, and why __eq exists for the cases where you want otherwise.

Order is a choice. Ember chooses insertion order, and pays for it.

4. Implementation

#![allow(unused)]
fn main() {
/// `entries` is a Vec, so iteration is insertion order. `index` maps a key to a
/// POSITION in that Vec. Deleting leaves a `None` tombstone rather than shifting,
/// so positions stay stable and iteration during modification is well-defined.
pub fn next(&self, after: Option<Value>) -> Option<(Value, Value)> {
    // array part first, in index order; then `entries`, skipping tombstones.
}
}

Deletion leaves a tombstone. That is the cost of insertion order, and it means a table churned heavily (insert/delete in a loop) grows entries without bound until a compaction. Ember compacts when tombstones exceed half of entries; do that during a rehash, not during iteration, or you invalidate a live next.

5. Alternatives

Go's choice is instructive in the opposite direction: Go deliberately randomizes map iteration order so that programs cannot accidentally depend on it. That is a defensible position — it turns a latent bug into an immediate one — and it is exactly wrong for Ember, whose whole purpose is reproducible output.

6. Decision

ADR-008: insertion order. Diverges from Lua, documented in appendix/lua-differences.md.

Two reasons, and the second is the one people underestimate:

1. Product. A ranking policy that iterates a table must produce the same ranking on every replica, every run, forever. Non-determinism here is a bug that reproduces once a month.
2. Testability. Differential testing compares printed output between two backends. If iteration order were unspecified, every test involving pairs would be flaky, and flaky tests get ignored. Determinism is a testability property before it is a feature — the same argument that settled the recursion limit and the execution budget.

7. Tradeoffs

That last row is the real cost. Once you specify iteration order, users depend on it and you can never change it. Python made this promise in 3.7 after it fell out of an unrelated optimization, and it is now permanent. Make it deliberately, in an ADR, or not at all.

8. Production concerns

• Modifying a table while iterating it. Lua says: assigning to an existing field is fine, adding a new one is undefined. Ember's tombstone design lets it do better — new entries append, so a next in progress will simply reach them — but "better" here means "a behavior users will depend on", so decide and document. The safe specification is Lua's: define assignment and deletion of existing keys, leave addition unspecified, and test what yours actually does.
• Table identity as a key. t[other_table] = true hashes the handle. If the handle were the heap index, then a collection that reused slot 7 would silently change a key's hash. Ember hashes a stable monotonic object id assigned at allocation, never the slot index. This is a determinism requirement and a correctness one, and it is easy to get wrong by reaching for the handy number.
• __eq and identity. Metamethod equality is only consulted when both operands are tables and raw identity fails. Getting that order wrong makes t == t call a metamethod, which is both slow and surprising.

9. References

• Lua 5.4 Reference Manual §3.4.4 (equality) and the next function in §6.1, including the exact wording about modification during traversal.
• The indexmap crate's documentation on its two-vector design — Ember's hash part is that design.
• Raymond Hettinger's "compact dict" presentation (Python 3.6), which is where the insertion-ordered dict came from and why it saved memory as a side effect.
• Go's runtime mapiterinit, and the commit message explaining the deliberate randomization.

Things to Notice

• One data structure plus metatables produces an object system. That is a language-design lesson, not just an implementation one: mechanism beats policy when your users are not programmers.
• The array part is the difference between "a hash map" and "a usable list". Every hybrid implementation exists for the same reason.
• nil deletes, so "present but nil" is inexpressible. Every Lua codebase eventually invents a sentinel.
• Keys are edges too. The most common missing-edge GC bug is a table's keys.
• Hashing object identity by heap slot is a bug waiting for a collection. Use a stable id.
• Specifying iteration order is a promise you cannot withdraw. Determinism is worth it here, and it is worth it for testability before it is worth it for the product.

Validation / Self-check

1. Name six things a Lua table is used as, and say which of them the language knows about.
2. Why are nil and NaN rejected as keys? What would go wrong for each if they were allowed?
3. What does normalize do, and what is the symptom of omitting it?
4. Draw the two parts of {10, 20, x = 1, [100] = "s"}.
5. What is migrate_from_hash for? Give the three-line program that fails without it.
6. Describe Lua's rehash counting rule and the invariant it guarantees.
7. t = {1,2,3}; t[2] = nil. What do get(2), ipairs, and #t each do, and are they consistent?
8. State ADR-008, its two justifications, and the cost that can never be undone.
9. Why must table identity hash a stable object id rather than the heap slot index?
10. Why is swapping Rust's default hasher for a faster one a security decision?

Next: Closures.