183. SoA code generation in Rust

A write that ran too early

write_rhs_first.js is in the corpus because a fuzzer wrote a program like it. Its middle part (wrapped):

try {
  for (let i = 0; i <= ps.length; i++)
    ps[i].x = ps[i].y;
} catch (e) {
  console.log('caught', e.message);
}
let t = 0;
try {
  ps[100].x = (t = 5);
} catch (e) {
  console.log('caught', e.message, t);
}

ps has 100 elements, so both writes go out of bounds. Here is what node prints for the original, and for the emitter’s output before the fix (reproduced on a copy of engine/rust with the new branch turned off):

original:
  caught Cannot read properties of
    undefined (reading 'y')
  caught Cannot set properties of
    undefined (setting 'x') 5
before the fix:
  caught Cannot set properties of
    undefined (setting 'x')
  caught Cannot set properties of
    undefined (setting 'x') 0

The compiled program failed at the wrong moment: before the right-hand side ran. Before we see why, here is the rest of what emit.rs writes.

Classes and columns that never clash

For each collection planned as SoA, container_class builds the class of chapter 103 with format! and join. Its name is __Vsc_ plus the collection’s name. Two collections can share a name in different functions, so the emitter numbers them, as __Vsc_ps and __Vsc_ps_2 in same_name_collections.js:

let mut cls = format!("__Vsc_{}", c.name);
let mut k = 2;
while class_names.contains(&cls) {
    cls = format!("__Vsc_{}_{k}", c.name);
    k += 1;
}
class_names.insert(cls.clone());

Columns are properties of that class, so a field called length or push would overwrite the container’s own members. column_name keeps a field name only if it is a plain ASCII identifier and not in a RESERVED list (length, push, grow, of, constructor, prototype, get, cap, data). Otherwise field number i becomes f{i}_. Then column_names makes the names unique: a renamed column gets _ appended until it differs from every kept field name and every earlier column. renamed_column_clash.js has fields length and f0_, and its constructor (reformatted) shows both rules:

constructor(cap = 16) {
  this.length = 0; this.cap = cap;
  this.f0__ = new Float64Array(cap);
  this.f0_ = new Float64Array(cap);
}

length became f0_, which a real field already uses, so f0__.

Two orders of evaluation

An access that wasn’t proven in bounds goes through __vsc_bc (chapter 104), which returns the index or throws the original’s TypeError. For reads that is enough. For writes, JavaScript’s order matters. For a = b, the specification evaluates the left-hand side to a reference, then the right-hand side, then stores with PutValue, and only PutValue fails on an undefined base^[1]. So in the original, ps[100].x = (t = 5) runs t = 5 before it throws.

The rewritten left-hand side ps.x[__vsc_bc(ps, 100, 'x', true)] is evaluated first. That fetches the column and runs the check, so the check threw before t = 5. The same order caused a second bug: if the right-hand side pushes and the container grows, grow() replaces the typed column, and the store goes into the old one. Step through it:

Rust wouldn’t let you write the old emitter’s order. Holding a column while growing its owner is two mutable borrows^[2]:

struct Soa {
    x: Vec<f64>,
}

impl Soa {
    // May move x to a bigger buffer.
    fn push(&mut self, v: f64) {
        self.x.push(v);
    }
}

fn main() {
    let x = vec![4.0; 4];
    let mut ps = Soa { x };
    // The old emitter's order for
    // ps[3].x = (more(), 77): take the
    // column, run the rhs, then store.
    let col = &mut ps.x;
    ps.push(0.0);
    col[3] = 77.0;
    println!("{}", ps.x[3]);
}

JavaScript runs it, and loses the write.

Storing late

The fix starts in the analysis. For each field write, it records what the rest of the assignment can do, as an RhsEffect: Inert, MayThrow (an unproven element read, say) or Effects (a call, an assignment). The emitter then picks the late form only when the order can be observed (adapted):

// ok: proven, or --bounds assume
let typed = cp.layout == Layout::Aosoa
    || c.numeric_fields.contains(&a.field);
let late = write
    && ((op == "=" && !ok
        && a.rhs != RhsEffect::Inert)
        || (typed
          && a.rhs == RhsEffect::Effects));

An unproven write whose right side may throw or act needs the check after it. A typed column (or AoSoA’s data) can be replaced by grow() only if the right side runs code. A plain column is an ordinary array that is never replaced, and inert right sides keep the cheap col[i] = rhs. The helpers (wrapped):

function __vsc_bk(c, i) {
  return i >>> 0 === i && i < c.length
    ? i : NaN;
}
function __vsc_set(c, col, i, v, f) {
  if (i !== i) throw new TypeError(
    `Cannot set properties of undefined`
    + ` (setting '${f}')`);
  c[col][i] = v;
  return v;
}

__vsc_bk decides the bounds question before the right side runs, but answers NaN instead of throwing. __vsc_set throws after it, and fetches c[col] only then. __vsc_seta does the same for AoSoA’s data. The loop above now compiles to (wrapped):

__vsc_set(ps, 'x', __vsc_bk(ps, i),
  ps.y[__vsc_bc(ps, i, 'y', false)],
  'x');

and prints exactly what the original prints. A compound += reads first in the original, so it keeps __vsc_bc with false (“reading”) and saves the index in a scratch variable, __vsc_k:

__vsc_set(ps, 'x',
  __vsc_k = __vsc_bc(ps, 4, 'x', false),
  ps.x[__vsc_k] + ((more(), 1)), 'x');

That line is from write_rhs_grows.js, which also grows an AoSoA collection inside = and ||= (through __vsc_seta). Its two output lines, from node:

original, and after the fix:
  130 77 6
  335 9 4 4
before the fix:
  130 4 6
  335 5 4 0

Your turn

use std::collections::HashSet;

const RESERVED: &[&str] = &[
    "length", "push", "grow", "of",
    "constructor", "prototype", "get",
    "cap", "data",
];

// Field i's column: its own name if
// that is a plain identifier and not
// reserved, else f{i}_.
fn column_name(
    f: &str,
    i: usize,
) -> String {
    let hd = |c: char| {
        c.is_ascii_alphabetic()
            || c == '_'
            || c == '$'
    };
    let rest = |c: char| {
        c.is_ascii_alphanumeric()
            || c == '_'
            || c == '$'
    };
    let mut cs = f.chars();
    let a = cs.next().is_some_and(hd);
    let ok = a && cs.all(rest);
    if ok && !RESERVED.contains(&f) {
        f.to_string()
    } else {
        format!("f{i}_")
    }
}

fn column_names(
    fields: &[String],
) -> Vec<String> {
    todo!()
}

What you learned

• Container classes are numbered (__Vsc_ps_2) when names repeat.
• Columns keep the field name unless it is reserved or not a plain identifier, then become f{i}_, extended with _ until unique.
• JavaScript evaluates a write’s left reference first, then the right-hand side, then stores.
• The analysis classifies each write’s RhsEffect. Observable orders are stored late: __vsc_bk before, __vsc_set after.