Values, Tables, Strings, and Garbage Collection

Keyboard shortcuts

×

?

Open this guide

Alt + B

Show or hide the lesson list

Alt + O

Show or fold the lesson outline

Alt + N

Open or close notes

Alt + H

Toggle semantic colours

Alt + D

Toggle page brightness

Alt + C

Toggle code brightness

← →

Move through a focused code trace

Home End

First or final step in a focused trace

Escape

Close this guide or an open panel

Reader shortcuts pause while you type in a text field.

Cheatsheet for Lesson 11.10Key ideas, reference and questions

A one-page summary of “Values, Tables, Strings, and Garbage Collection” you can keep beside your notes. Plain Markdown.

Lesson 11.10 — Values, Tables, Strings, and Garbage Collection: cheatsheet

• Remember: A tracing collector asks whether roots can reach an object; positive reference counts alone cannot show that a cycle is still useful.
• Also useful: Interning is a shared dictionary: repeated strings use the same entry ID instead of each keeping another identical copy.

Reading map

• Dynamic values still need a representation
• A Lua table combines array-like and map-like storage
• Reference counting handles sharing, not every cycle
• Roots answer “what is still reachable?”
• Questions to ask while reversing an embedded VM
• Further reading

Formulas and patterns

• after a = {} and b = {} table A: 1 (a) table B: 1 (b); after a.friend = b table A: 1 table B: 2 (b, A.friend); after b.friend = a table A: 2 (a, B.friend) table B: 2; a and b leave scope table A: 1 (B.friend) table B: 1 (A.friend)

Review

• Q: Why can plain strong reference counting leak two Lua tables that point to each other? A: Each keeps the other's count above zero
• Q: Why does each interpreter value carry a tag beside its payload? A: An operation reads the tag to learn the value's type first

Download cheatsheet (.md)

Download cheatsheet (.md)

Dynamic values still need a representation

The host often knows a value’s type at compile time. Lua decides many operations at run time. An interpreter therefore carries a tag with each value:

Optional: practise the named operations and their inputs with a few whole-token blanks.

enum Value {
    Nil,
    Boolean(bool),
    Integer(i64),
    Float(f64),
    String(StringId),
    Table(TableId),
    Function(FunctionId),
}

The IDs here are handles into VM-owned storage. That keeps interpreter objects under one memory manager instead of handing scripts raw native pointers.

Three stack slots show the idea. Each value carries its tag beside its payload, and an operation reads the tags before it touches any payload:

tagInteger

payload42

tagTable

payloadid 3

tagNil

payloadunused

Value::Integer(42)

Value::Table(TableId(3))

Value::Nil

+ checks both tags first. Two Integer tags let it add the payloads; an Integer beside a Table fails the check, and this VM raises a type error instead of adding a number to a handle (real Lua first looks for an __add metamethod). The Table payload is not a pointer: id 3 is looked up in storage the VM owns.

A Lua table combines array-like and map-like storage

Lua uses tables for sequences, records, dictionaries, objects, and module namespaces. An implementation can optimize common integer keys with an array part while keeping other keys in a hash-map part:

local palette = { "red", "green", "blue", name = "palette", selected = 2 }

1red

2green

3blue

namepalette

selected2

array part: keys 1 to 3, found by position

hash part: found by hashing the key

One table, two conceptual storage areas in Lua 5.4. The three dense integer keys fit the array-like part; named keys use the hash-like part. Exact allocated capacities are implementation details. palette[2] can use an array position; palette.name hashes the name to begin its lookup.

This is an implementation strategy, not two separate Lua values. The language still presents one table. It also explains why pairs promises no meaningful order: it walks the array part first and then the hash nodes in node order, and node order follows the keys’ hash values rather than the order they were written.

When the host converts a Vec to Lua, it writes keys 1, 2, and 3. When it converts a record, it writes named keys such as health and position. The script can use both forms, but the host should document which shape it promises.

Strings need ownership too

Repeated source names and table keys can create many duplicate strings. An interpreter may intern strings: store one canonical copy and let values carry a small ID or shared reference.

Alternative: Interning is a shared dictionary: repeated strings use the same entry ID instead of each keeping another identical copy.

Checking whether two interned strings are equal is then one integer comparison, 0 == 0, however long the text is. Interning makes equality fast, but it adds lifetime work. The interpreter must know when no live value, table key, closure, or compiled function still needs the string.

Reference counting handles sharing, not every cycle

Rc<T> counts strong owners. It frees the value when the count reaches zero. That works for many interpreter objects, but tables can form cycles:

local a = {}
local b = {}
a.friend = b
b.friend = a

If each table strongly owns the other, both counts stay above zero even after the script drops a and b. Follow the arithmetic:

after a = {} and b = {}      table A: 1 (a)             table B: 1 (b)
after a.friend = b           table A: 1                 table B: 2 (b, A.friend)
after b.friend = a           table A: 2 (a, B.friend)   table B: 2
a and b leave scope          table A: 1 (B.friend)      table B: 1 (A.friend)

Both counts settle at one, each held up solely by the other. Nothing in the running program can reach either table any more, yet neither will ever be freed. That is the shape of every reference-counting leak: the objects have become unreachable without becoming unreferenced, and counting alone cannot tell those two conditions apart.

A tracing garbage collector can start from roots—globals, active stacks, and live closures—mark reachable objects, then reclaim unmarked cycles.

Do not assume Rc by itself is a complete Lua garbage collector. A small non-cyclic interpreter can use it while learning, but a general implementation needs a cycle strategy.

Roots answer “what is still reachable?”

Typical roots include:

• the global environment;
• each active function frame;
• values on VM stacks or registers;
• open upvalues captured by closures;
• host references intentionally kept alive.

A tracing collector reclaims an unreachable cycleTable P is held by a global and holds the string s and the closure f. Tables A and B hold only each other. Every reference count is 1.

1. 1 Mark: follow references from the roots

   Heap objects

   Pmarked

   smarked

   fmarked

   Anot reached

   Bnot reached

   From the global the collector reaches P, then s and f. Nothing reachable leads to A or B.

2. 2 Sweep: free every unmarked object

   Heap objects

   Pkept

   skept

   fkept

   Afreed

   Bfreed

   A and B are reclaimed together, although each still had a count of 1.

Table P is held by a global and holds the string s and the closure f. Tables A and B hold only each other. Every reference count is 1.

The cycle keeps both reference counts above zero, but no root reaches either table. A tracing collector can tell the difference because it asks about reachability, not just owner counts.

TL;DR: A tracing collector asks whether roots can reach an object; positive reference counts alone cannot show that a cycle is still useful.

A host API that retains a Lua table may accidentally keep a large graph alive. Resource limits should measure actual interpreter memory, not merely the size of the source file.

Narration: Holding one Lua table in the host can keep everything reachable from it alive. Small source files can still retain large object graphs.

A cycle can keep counts positive without a root. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

root -> A; A -> B; B -> A
count strong references to each table
optionally remove the external root
count references again
trace reachable objects starting from roots
compare reachability with reference counts

Result: both counts are 1, yet neither table is reachable. A tracing collector can reclaim this unreachable cycle.

Final values: root = removed; refs_A = 1; refs_B = 1; reachable_A = false; reachable_B = false; external_roots = 0; reclaimable_by_tracing = true.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.

   root = removed.

2. Step 2, line 2. A has a root reference plus B’s reference; B has A’s reference.

   root = removed; refs_A = 2; refs_B = 1; reachable_A = true; reachable_B = true.

3. Step 3, line 3. Remove only the external reference; the cycle remains.

   root = removed; refs_A = 2; refs_B = 1; reachable_A = true; reachable_B = true; external_roots = 0.

4. Step 4, line 4. Neither cycle edge disappears when the root is removed.

   root = removed; refs_A = 1; refs_B = 1; reachable_A = true; reachable_B = true; external_roots = 0.

5. Step 5, line 5. No root reaches either table.

   root = removed; refs_A = 1; refs_B = 1; reachable_A = false; reachable_B = false; external_roots = 0.

6. Step 6, line 6. Result: both counts are 1, yet neither table is reachable. A tracing collector can reclaim this unreachable cycle.

   root = removed; refs_A = 1; refs_B = 1; reachable_A = false; reachable_B = false; external_roots = 0; reclaimable_by_tracing = true.

Tables are capability containers

In our embedded host, the game table contains only selected callbacks. This is more than neat organization:

game.snapshot()
game.distance(a, b)
game.log("ready")

If game.open_process, game.read_any_address, or os.execute never enters the environment, ordinary scripts cannot call it. Table construction becomes part of the security boundary.

Questions to ask while reversing an embedded VM

In a debug build, look for:

• a tagged-value dispatch that checks type before an operation;
• one central table lookup routine;
• a VM instruction pointer separate from the CPU instruction pointer;
• arrays of constants or bytecodes owned by compiled functions;
• root enumeration during garbage collection;
• native host callbacks registered under readable names.

Use these structures to explain tagged values, object reachability, table lookup, and callback dispatch in the scripting system.

Further reading

The Lua 5.4 reference manual is the source of truth for language behavior. Build a Lua Interpreter in Rust provides an extended implementation path through strings, tables, expressions, control structures, functions, and closures. Use both to understand the model, then write and test your own representation for the subset you intend to support.

🧩

Knowledge check

Find the lifetime problem

Why can plain strong reference counting leak two Lua tables that point to each other?

1Each keeps the other's count above zero2Tables cannot hold other tables inside them3Reference counts can only be kept for strings4Lua never frees a value once it is created

Check answer

Finished Lesson 11.10?

Mark it done and the lesson list shows a ✓ beside it. A chapter whose lessons are all done is marked done too. Progress is saved in this browser only.

Mark lesson doneLesson done. Mark it not done

Chapter 11: 11 lessons

📝 Notes