50. Strings and heap objects

A value that won’t fit

Every slot on the VM’s stack has to be the same size, so the VM can find slot 7 without measuring slots 0 to 6. A number fits: 64 bits, always. Now try these:

let a = "";
let b = "the quick brown fox";
let c = b + b + b + b;

a is zero characters, c is 76, and a loop could build one of a million. There is no slot size that fits them all. So strings can’t live in the slot. They live somewhere else, and the slot holds the way to find them.

Heap objects

The fourth tag from chapter 49, obj, is that ticket. Its payload is a reference to an object that the VM allocates on the heap. Here is the string object in the companion VM’s vm/object.ts, slightly trimmed:

interface ObjHeader {
  isMarked: boolean;
  next: Obj | null;
}

interface ObjString extends ObjHeader {
  type: 'string';
  chars: string;
  hash: number;
}

Strings aren’t alone. Functions, closures, classes and instances will all be heap objects, and they all extend the same header:

type Obj =
  | ObjString | ObjFunction | ObjNative
  | ObjUpvalue | ObjClosure | ObjClass
  | ObjInstance | ObjBoundMethod;

That is a discriminated union on type (chapter 14). Telling an object from the other values, and a string from the other objects, takes two small checks:

const isObj = (v: Value): v is Obj =>
  typeof v === 'object' && v !== null;
const isString = (v: Value) =>
  isObj(v) && v.type === 'string';

v !== null matters because typeof null is 'object' in JavaScript, and null is how this VM spells nil.

Two values can share one object: let t = s; copies the reference, not the characters. That’s aliasing again (chapter 4), and it is safe for strings because nothing in Drip can change a string’s characters.

Where strings come from

The strings a Drip program works with come from two places. (The compiler also makes string objects for names, such as a global’s name, which chapter 53 puts to use.)

Literals, at compile time. When the single-pass compiler meets a string token, it cuts the quotes off the lexeme, makes the object, and puts it in the constant pool:

const string = () => emitConstant(
  heap.copyString(
    previous.lexeme.slice(1, -1)));

By the time the program runs, "tea" is already an object, waiting in the chunk.

Concatenation, at runtime. OP_ADD now does two jobs. Two numbers are added. Two strings are joined into a new object:

case OP.ADD: {
  const b = peek(0);
  const a = peek(1);
  if (isString(a) && isString(b)) {
    const s = heap.copyString(
      a.chars + b.chars);
    pop(); pop(); push(s);
  } else if (typeof a === 'number'
      && typeof b === 'number') {
    sp -= 2; push(a + b);
  } else {
    runtimeError('Operands must be ' +
      'two numbers or two strings.');
  }
  break;
}

Look at the order: the operands are only peeked at while the new string is made, and popped afterwards. Allocating may start the garbage collector (chapter 58), and the collector treats whatever is on the stack as in use. Popping first could leave a and b reachable from nowhere, at the exact moment the collector looks.

The name copyString comes from C, where building a string object means copying its characters into fresh memory, as clox does^[1]. Here chars is a JavaScript string, which is immutable, so nothing is copied: the object simply holds it.

let s = "tea" + "pot";
print s;
let t = s;
print t + "s";
print "1" + 2;

The object list

Every object is created by one method, allocate, in vm/heap.ts. Here it is, with the collector’s part left for chapter 58:

private allocate<T extends Obj>(o: T) {
  this.bytesAllocated += SIZE[o.type];
  // (chapter 58: maybe collect here)
  o.next = this.objects;
  this.objects = o;
  return o;
}

SIZE is a rough byte count per kind of object, so the VM can tell when it has allocated enough to be worth a collection. The last three lines are the interesting part. heap.objects points at the newest object, its next points at the one before, and so on back to the very first. Adding to the front of a linked list costs the same however long the list is: no walking.

let s = "x";
for (let i = 0; i < 3; i = i + 1) {
  s = s + "a";
}
print s;

That last step is the point. "xa" and "xaa" are garbage: no variable, no stack slot and no constant can reach them. In C, memory nobody can reach is memory nobody can free, a leak. The list is the VM’s guarantee that it can always find every object it ever made.

Your turn

class Heap {
  constructor() {
    this.objects = null;
  }
  allocate(o) {
    return o;
  }
  newString(chars) {
    return this.allocate({
      type: 'string', chars, next: null,
    });
  }
  live() {
    return 0;
  }
}

function unlink(heap, dead) {
  // remove dead from heap.objects
}

What you learned

• A string can be any length, so it is a heap object: the stack slot holds a reference, and the object lives on the heap.
• Every object shares a header (isMarked, next), then a type tag, then its own fields. Obj is a discriminated union on type.
• String objects come from literals (made by the compiler, stored in the constant pool) and from concatenation (OP_ADD, at runtime).
• The object list links every allocation through next, newest first, so the VM can always find every object, garbage included.

Next: the hash field. Before the VM can look up a variable by name, it needs a fast way to find a string in a table.