86. Type and shape inference

Two facts nobody wrote down

To give a field a Float64Array column, Viscosity needs two facts that no JavaScript program states:

1. every element has the same fields, so there is one set of columns;
2. a field only ever holds numbers, so a typed array can store it.

A Float64Array silently turns a string like 'far' into NaN, so getting the second one wrong changes what the program prints. Viscosity can’t ask, and it doesn’t trust TypeScript annotations either: it strips them before analysis, and they never change what runs^[1]. It has to deduce both facts from the code itself.

Rules for one value

Each IR value gets a fact from a small rule. Simplified, from packages/core/src/analysis.ts:

switch (i.op) {
  case 'const':
    return typeof i.value === 'number';
  case 'binop':
    return ARITH.has(i.operator)
      && n(i.args[0]) && n(i.args[1]);
  case 'phi':
    return i.args.every(n);
  case 'loadBinding':
    return bindingNumeric.get(i.binding);
  case 'param': // every caller passes one
    return sites.every((s) =>
      n(s.args[i.index + 1]));
  case 'field.get':
    return colNumeric.get(column(i));
  default:
    return false;
}

n(v) reads the current fact for v. Notice that + counts only when both sides are numbers, since 1 + '1' is '11'. The param rule only works for the known functions of the last chapter, whose every call site is visible. Anything unfamiliar falls to default: not a number.

The loop problem

The rules refer to each other. A loop counter’s phi depends on the addition at the bottom of the loop, which depends on the phi. Where do you start? Step through both answers:

let v = 0;
for (let i = 0; i < 100; i++) {
  ps.push({ x: v });
  v = v + 0.5;
}

This is the lattice and fixpoint machinery from chapter 79, with a two-level lattice: number above maybe not. Viscosity starts the values that can sit on cycles (phis, variable loads, field reads and parameters) at the optimistic top, then recomputes every value, variable and column until a whole round changes nothing:

for (const v of m.values)
  num.set(v.id, cyclic(v) || compute(v));
for (let changed = true; changed; ) {
  changed = false;
  for (const v of m.values) {
    const nv = compute(v);
    if (num.get(v.id) !== nv) {
      num.set(v.id, nv);
      changed = true;
    }
  }
  // then variables and columns
}

A fact can only fall, from number to maybe not, and there are finitely many facts, so the loop must end. As a guard, the real code also stops after 1000 rounds, and if it hasn’t settled by then it gives up on every guess (fails closed) rather than keep an unproven one.

Watching facts spread

Here is viscosity explain on three versions of one program. Records are pushed as add(i, 0) in a loop, then once more as add(5, 'far'):

// the loop does ps[i].x *= 2
· typed Float64Array columns for x;
  plain array columns for y
  (may hold non-numbers)

// the loop does ps[i].x += ps[i].y
· no field is provably numeric, so
  there are no typed columns to gain

// the call is add(5, 0) instead
· typed Float64Array columns for all
  2 fields

The second one is the interesting one. Only y ever receives a string, but x += y stores x + y back into x, and that might be a string, so x falls too. One string poisoned two columns. A field that may hold non-numbers is not a reason to give up, though: it gets a plain array column, while the numeric fields still get typed ones. Try it:

Shapes from object literals

The other fact is the shape. Viscosity only accepts records made by object literals, in push({...}) or in an array literal. Each becomes a record.new instruction carrying its field list, and every list must match the first, order included:

if (c.fields.length === 0)
  c.fields = [...r.fields];
else if (JSON.stringify(c.fields)
         !== JSON.stringify(r.fields))
  c.bailouts.push('records with ' +
    'different fields or field order');

That is the simplest possible way to unify shapes: they must be equal. (An earlier version compared join(',') strings, so a field named 'a,b' matched the two fields a and b. Comparing the lists exactly fixed it.) Two small programs show both ways to fail:

· unsafe: line 3: records with different
  fields or field order
  ({x, y} vs {x, y, z})

· unsafe: line 4: records with different
  fields or field order
  ({x, y} vs {y, x})

Why should order matter, when {x, y} and {y, x} hold the same data? Partly for Viscosity itself: it reads the value for column x from a fixed position in each record.new. And partly because order is part of JavaScript. You saw in chapter 63 that shapes grow one property at a time, and the language itself can tell the two apart:

const a = { x: 1, y: 2 };
const b = { y: 2, x: 1 };
console.log(Object.keys(a));
console.log(Object.keys(b));
console.log(JSON.stringify(a));
console.log(JSON.stringify(b));
// Same data, different text:
console.log(
  JSON.stringify(a) ===
  JSON.stringify(b));

Your turn

function unifyShapes(lits) {
  // your code here
}

console.log(unifyShapes([
  ['x', 'y'], ['x', 'y'],
]));
console.log(unifyShapes([
  ['x', 'y'], ['y', 'x'],
]));

function inferNumeric(defs) {
  const num = {};
  // your code here
  return num;
}

console.log(inferNumeric({
  v0: { op: 'const', value: 0 },
  c: { op: 'const', value: 0.5 },
  v1: { op: 'phi', args: ['v0', 'v2'] },
  v2: { op: 'add', args: ['v1', 'c'] },
}));

What you learned

• Type inference deduces types from how values are made and used. Viscosity asks one question per value: provably a number?
• Rules combine facts: constants, arithmetic on two numbers, phis whose inputs all agree, variables, columns, and parameters of known functions.
• Loops make the rules circular. An optimistic fixpoint starts at “number” and knocks guesses down. A pessimistic one can’t prove a loop.
• Facts spread: one string in y can make x non-numeric through x += y. Such fields get plain array columns.
• Shape inference takes the field lists of the object literals. In Viscosity they must match exactly, order included.