99. Proving it safe

The promise

Viscosity is a source-to-source compiler, and it makes one promise: the program it writes prints exactly what yours printed. The struct of arrays it builds stores the same numbers. But a JavaScript program can notice much more than numbers. It can notice how its data is stored:

ps[1] === ps[2];   // is it one object?
console.log(ps[3]); // print the object
const keep = ps[0]; // a second name
ps.sort(byX);       // move the objects
for (const k in ps[0]) {} // its keys

After the rewrite there are no element objects at all, only columns. If any line like these survived, the program could tell, and the promise would be broken.

Here is the whole decision; the rest of the chapter looks at each check.

What the array may do

Starting from every load of the array, Viscosity walks the uses (the same worklist as chapter 85). Four kinds are allowed. Simplified, from packages/core/src/analysis.ts:

for (const u of usesOf(ref)) {
  const i = u.inst;
  if (isLength(i)) continue;
  if (isPush(i)) {
    // one argument, a fresh literal:
    // setShape (chapter 97)
    continue;
  }
  if (isIndexGet(i)) {
    elements.push(i); // check later
    continue;
  }
  if (isKnownCall(i)) {
    work.push(param); // follow it
    continue;
  }
  bailouts.push('the array is ' +
    describeUse(u));
}

Everything else ends at describeUse, which names what happened. Real messages for ps.reverse(), console.log(ps) and return ps:

· unsafe: line 10: uses .reverse on the
  array (only .length and .push are
  supported)
· unsafe: the array is passed to a
  method call at line 4
· unsafe: returned or branched on in
  make()

The first two can appear together: ps.reverse() both reads a property other than length and passes ps as the receiver of a method call. Each element ps[i] is then checked the same way, with an even shorter list: read a field of the shape, or write one. The safe uses are what fills the access table of chapter 98.

Following a collection into a function

Most real code doesn’t loop over an array where it was made. It passes the array to a function. A call is normally an escape, because the callee could do anything. But if Viscosity can see every call of the function, the parameter is just another name for the collection.

// Known functions: declared once, and
// every reference is a direct call.
for (const f of m.functions) {
  if (storesOf(f).length !== 1) continue;
  let ok = true;
  const sites = [];
  for (const use of refsTo(f))
    if (isDirectCall(use)) sites.push(use);
    else ok = false;
  if (ok) callSites.set(f, sites);
}

When ps is passed to a known function at position k, Viscosity checks that all its call sites pass ps at k. If they do, the parameter joins the worklist, and its uses inside the function are checked like uses of ps. If some call passes something else, it bails out. Two corpus files show both outcomes:

// interproc_ok.js: drift(bodies, 0.5)
// and drift(bodies, -0.25)
bodies (line 2) {x, y, m} → struct of
  arrays

// interproc_mixed.js: total(a), total(b)
a (line 2) {x} → kept as array of objects
  · unsafe: line 10: passed to total(),
    which is also called with other
    values

The rule is points-to analysis on a small scale: the parameter may point to exactly one collection. Two collections would need two versions of total, and Viscosity doesn’t make copies of functions. An exported function is not known either: code in another module could call it with anything. Passing ps to one gives “passed to a function call”.

Every index must be a number

ps[i] is only an element if i is a number. Bracket access with a string asks for a property, and some strings happen to name elements:

const ps = [{ x: 1 }, { x: 2 }];
for (const k of [1, '1', 'length']) {
  console.log(k, ps[k]);
}
// '1' finds an element, but 'length'
// finds a property. With only a
// string in hand, Viscosity can't
// tell which you meant.

After the rewrite, ps[k] becomes ps.x[k] and friends, which would answer ps['length'] completely differently. So Viscosity requires every index to be provably a number. “Provably a number” is a fact from the numeric fixpoint (chapter 86), so this check waits until the fixpoint has finished:

for (const { c, i } of indexChecks)
  if (!isNumber(i.args[1]))
    c.bailouts.push(`line ${line(i)}: ` +
      'indexes the array with something' +
      ' that may not be a number');

The fixpoint follows parameters of known functions, too. With function get(k) { return ps[k].x; }, the calls get(3) and get(4) are fine, while one call get('4') makes k “maybe not a number” and the whole collection bails out.

From reasons to explain

Viscosity never stops at the first problem. All the reasons are kept, duplicates removed, and handed to the planner, which makes this the very first question it asks. From plan.ts:

if (c.bailouts.length) {
  out.push(keep(...c.bailouts.map(
    (b) => `unsafe: ${b}`)));
  continue;
}

keep means “array of objects”. No cost is weighed for an unsafe collection. Try it on the program below. It is accepted as it stands. Then make one change at a time and watch the reasons appear: add ps.reverse(); before the last line, print ps[3] instead of ps[3].x, add a call step([{ x: 0, vx: 1 }]);, or index with const k = '3';.

Your turn

function firstBailout(fields, uses) {
  // your code here
  return null;
}

console.log(firstBailout(['x'], [
  { on: 'array', op: 'length',
    line: 3 },
  { on: 'array', op: 'sort',
    line: 4 },
]));

function followParam(fn, k, name) {
  // your code here
}

console.log(followParam({
  stores: 1,
  refs: [{ call: true, args: ['ps'] }],
}, 0, 'ps'));

What you learned

• Safety analysis proves that no code can observe the layout change. Viscosity uses an allow-list: anything it can’t rewrite is a bailout reason.
• The array may be used for .length, push of one fresh literal, ps[i], and as an argument to a known function. Elements may only have fields of the shape read or written.
• A known function is declared once and only called directly. Its parameter is followed if every call site passes the same collection; exported functions are never known.
• Every index must be provably a number, which is checked after the numeric fixpoint.
• All reasons are collected; any reason makes the planner keep the array of objects and print unsafe: reasons.