179. Shape inference in Rust

One field or two?

This is comma_field_name.js, a program in the reference’s corpus:

const ps = [];
for (let i = 0; i < 100; i++) {
  ps.push({ 'a,b': i });
  ps.push({ a: i, b: 2 });
}

(Rewrapped: the real file has the loop on one line.) The first record has one field, named a,b. The second has two. They are different shapes, so ps must stay an array of objects. Both engines now say so (real output of the Rust CLI, wrapped):

ps (line 3) {a, b} → kept as array of
  objects
  · unsafe: line 4: records with
    different fields or field order
    ({a,b} vs {a, b})

The reference used to get it wrong. It compared shapes by their field names joined into one string, and ["a,b"] and ["a", "b"] join to the same thing. It is bug 3 in the port’s README, found during porting, now fixed in both engines and pinned by that corpus program. Notice the message still prints the one field without quotes: {a,b}.

set_shape

The Rust version, trimmed:

fn set_shape(&mut self, ci: usize,
        r: ValueId, location: &str) {
    let Op::RecordNew { fields } =
        &self.inst(r).op
    else { unreachable!() };
    let aliased =
        self.uses.of(r).len() != 1;
    let at = self.inst(r).src;
    let c = &mut self.collections[ci];
    if c.fields.is_empty() {
        c.fields = fields.clone();
    } else if c.fields != *fields {
        // bail: "records with different
        // fields or field order (...)"
    }
    if aliased {
        // bail: "...could be aliased"
    }
}

c.fields != *fields compares two Vec<String>s: same length, then each name in order. Nothing gets joined, so no name can run into another. The fixed TypeScript compares JSON.stringify of both arrays, which quotes every name. Two engines, two spellings, one answer, and the parity fixtures check that it stays one answer.

The second check is chapter 96’s: the new record must have exactly one use, the push. A second use, such as r.x = 500, would still expect an object r after the rewrite.

Holding the fields, changing the collection

fields is borrowed from an instruction, and two lines later the function takes &mut self.collections[ci]. That only compiles because of chapter 178’s 'm: inst returns &'m Inst, a borrow of the module, which self merely points to. Give the accessor the elided lifetime, tied to &self, and rustc 1.97 says (a small copy, trimmed and rewrapped):

error[E0502]: cannot borrow `self.cols`
  as mutable because it is also
  borrowed as immutable
  | let fields = self.rec(r);
  |              ---- immutable borrow
  | let c = &mut self.cols[ci];
  |         ^^^^^^^^^ mutable borrow
  |     c.fields = fields.clone();
  |                ------ immutable
  |                borrow later used

The runnable copy has the 'm in place. Delete it and see; it also prints what joining does to ["a,b"] and ["a", "b"]:

struct Module {
    records: Vec<Vec<String>>,
}

struct Col {
    fields: Vec<String>,
    bails: Vec<String>,
}

struct An<'m> {
    m: &'m Module,
    cols: Vec<Col>,
}

impl<'m> An<'m> {
    // Try: -> &Vec<String> (no 'm).
    fn rec(
        &self,
        r: usize,
    ) -> &'m Vec<String> {
        &self.m.records[r]
    }
    fn set_shape(
        &mut self,
        ci: usize,
        r: usize,
    ) {
        let fields = self.rec(r);
        let c = &mut self.cols[ci];
        if c.fields.is_empty() {
            c.fields = fields.clone();
        } else if c.fields != *fields {
            let m = "different fields";
            c.bails.push(m.into());
        }
    }
}

fn main() {
    let s = |x: &str| x.to_string();
    let one = vec![s("a,b")];
    let two = vec![s("a"), s("b")];
    println!(
        "joined equal: {}",
        one.join(",") == two.join(",")
    );
    let m = Module {
        records: vec![two, one],
    };
    let col = Col {
        fields: vec![],
        bails: vec![],
    };
    let mut an = An {
        m: &m,
        cols: vec![col],
    };
    an.set_shape(0, 0);
    an.set_shape(0, 1);
    println!("{:?}", an.cols[0].bails);
}

What a field may hold

A shape is the field names plus what each field may hold (chapter 97). The second half comes from chapter 177’s fixpoint. Each field of each collection is a node, starting optimistic. field_stays_numeric keeps it only if every record added puts a provable number in that position and every field.set on an element writes one. Fields that survive go into numeric_fields and get Float64Array columns; the rest get plain arrays.

In JavaScript every number is a double, so the arithmetic rule is short: an operator from ARITH is a number if both sides are. Python is different.

Python: ints are not floats

A Python column becomes array('d'), an array of C doubles that only holds floats^[1]. An int goes in, but a float comes out. With Python 3.13.18, here:

a = array('d', [0.0])
a[0] = 1
print(a[0], type(a[0]).__name__)
print(7 / 2, 6 / 2, 7 // 2)
print(2 ** 3, 2 ** -1, 2.0 ** 3)
print((-1.0) ** 0.5)

1.0 float
3.5 3.0 3
8 0.5 8.0
(6.123233995736766e-17+1j)

So in Python “numeric” must mean “provably a float”, or a program that printed 1 would print 1.0. Ints get their own fact (compute_int), because they still matter: an int times a float is a float. True division always gives a float^[2]. And ** is treacherous: an int to an int power can be an int or a float, and a float to a float power can be complex. The float rule for a binary operator, trimmed from compute:

match operator.as_str() {
    "/" => n_or_i(a) && n_or_i(b),
    // (-1.0) ** 0.5 is 1j
    "**" => n(a) && self.i(b),
    "+" | "-" | "*" | "%" | "//" =>
        (n(a) && n_or_i(b))
            || (self.i(a) && n(b)),
    _ => false,
}

n is “a float”, i is “an int”. The analyzer decides which rules apply once, py: m.language == "python", as the reference does. Watch them type a real corpus program, ints_stay_ints.py:

%6  = phi %4, %14        # i
%10 = binop / %6, %9     # i / 2
%11 = record {count, weight} %6, %10
%22 = field.get %21 .count
%24 = binop + %22, %23   # + 1
      field.set %21, %24 .count
%28 = field.get %27 .weight
%30 = binop * %28, %29   # * 2
      field.set %27, %30 .weight

Your turn

// What the fixpoint knows about a
// Python value: provably a float,
// provably an int, or neither.
#[derive(Clone, Copy, PartialEq, Debug)]
pub struct K {
    pub float: bool,
    pub int: bool,
}

// Is it a number of either kind?
fn num(k: K) -> bool {
    k.float || k.int
}

pub fn py_binop(
    op: &str,
    a: K,
    b: K,
) -> K {
    todo!()
}

pub struct Col {
    pub fields: Vec<String>,
    pub bails: Vec<String>,
}

fn list(fs: &[String]) -> String {
    format!("{{{}}}", fs.join(", "))
}

// A record with fields fs and n uses
// joins collection c.
pub fn set_shape(
    c: &mut Col,
    fs: &[String],
    n: usize,
) {
    let differs =
        todo!();
    if c.fields.is_empty() {
        c.fields = fs.to_vec();
    } else if differs {
        let m = format!(
            "different: {} vs {}",
            list(fs),
            list(&c.fields)
        );
        c.bails.push(m);
    }
    if n != 1 {
        c.bails.push("aliased".into());
    }
}

What you learned

• The shape pass in Rust: set_shape compares field lists as Vec<String>s, exactly. Comparing joined names let {'a,b'} pass for {a, b}; the port found it.
• The record must have exactly one use, or it could be aliased.
• inst returns &'m Inst, so set_shape can hold the fields while it changes self.collections (E0502 otherwise).
• A field is typed if every value stored in it is a number. In Python that means a float: / always gives one, ** only for a float base and an int exponent, and an int anywhere else keeps a list column.