142 lines
8.9 KiB
Markdown
142 lines
8.9 KiB
Markdown
# The core model
|
|
|
|
This file is the spec for how the compiler gives a type to every value of a JS program, and how it represents those values in C. The code must agree with it. A difference between the code and this file is a bug in one of them.
|
|
|
|
Everything comes from four simple things and how they act on each other:
|
|
|
|
1. **the types**, an enum, and the rules that join two of them (section 2)
|
|
2. **objects**, which are types that every holder shares (section 3)
|
|
3. **`walk_fn`**, which walks one fn with the types of its args, and gives the type of each of its values (section 4)
|
|
4. **the type cache**, which keeps one walk for each fn and each list of arg types that the program reaches (section 4)
|
|
|
|
## 1. Semantics
|
|
|
|
The C code must keep these JS semantics.
|
|
|
|
- **A value** is one of: undefined, null, a bool, a number, a string, an object. A value cannot change. An assignment, an arg, a return and a field write each copy the value. An object value is a reference to the object, so a copy of it refers to the same object.
|
|
- **An object** has identity, own fields, and a prototype (an object or null). A read of a field that the object lacks goes on to the prototype, and at the end of the chain it gives undefined. A field that is absent and a field that holds undefined are different.
|
|
- **A binding** is the storage of a variable. A closure captures bindings, not values: a write to a captured binding, by its owner or by any closure, is seen by all of them. Each iteration of a loop body has its own bindings.
|
|
- **A function** is an object that also has code, and the bindings that it captured.
|
|
|
|
## 2. Types
|
|
|
|
A type tells which values a place can hold at runtime. It is one of these:
|
|
|
|
| type | values |
|
|
|---|---|
|
|
| `Unknown` | none: no value has reached the place yet |
|
|
| `Undefined` | undefined |
|
|
| `Null` | null |
|
|
| `Bool(v)` | a bool. `v` is the value, if it is known |
|
|
| `Int` | an int32 (provisional: the number type is not decided) |
|
|
| `Float` | a number |
|
|
| `Str(v)` | a string. `v` is the value, if it is known |
|
|
| `Obj(cell)` | an object, described by a cell (section 3) |
|
|
| `Sum(…)` | one of a list of the types above |
|
|
| `Any` | any value. No rule gives it now |
|
|
|
|
**Join** gives the type of a place that gets the values of two types:
|
|
|
|
```
|
|
Unknown * T = T
|
|
Any * T = Any
|
|
T * T = T
|
|
Bool(a) * Bool(b) = Bool, the value not known. The same for Str
|
|
Int * Float = Float
|
|
T * U = T | U
|
|
```
|
|
|
|
A sum has at most one member of each kind, except objects: it has one `Obj` for each cell. Two `Obj` types are the same type only if they have the same cell.
|
|
|
|
## 3. Objects
|
|
|
|
**The type of an object is a cell:** a description of the object that every holder of the object shares. In the compiler it is `Obj(Rc<RefCell<…>>)`. The cell holds:
|
|
|
|
- the type of each field, and whether every object of the cell has the field from the start (else it can be absent)
|
|
- what the object is: a plain object, a fn (with its code), or an array (with the type of its elements)
|
|
|
|
**A copy of the value copies the `Rc`,** so all holders have the same cell. Everything about aliasing comes from this:
|
|
|
|
- **A write** `o.f = v` joins the type of `v` into the cell's field `f`. Every holder of the object sees it at once: through calls, returns, other objects' fields, closures and array elements.
|
|
- **A read** `o.f` gives the cell's field `f`. If the field can be absent, it also gives the read on the prototype. At the end of the chain, it gives `Undefined`.
|
|
- **A cell can hold itself,** for example as the type of the field `next` in a list. So an object that reaches itself needs nothing more.
|
|
|
|
**An array** is a cell whose elements have one type `T`, the join of every value written to an element. `a[i]` gives `T | Undefined`, because an index can be a hole or past the end. `a.length` is an `Int`.
|
|
|
|
**A captured binding is a box:** a cell with one field, which holds the binding's value. The fn that owns the binding makes the box when it is entered, and again for each iteration of a loop body. The owner and every closure that captured the binding read and write the box's field. A closure is a fn cell whose fields hold its boxes.
|
|
|
|
## 4. Inference
|
|
|
|
**`walk_fn`** walks one fn with one list of arg types.
|
|
|
|
- It starts with `val_types = vec![Type::Unknown; n_val]`, and puts the arg types into the args' values.
|
|
- It walks the instrs. Each instr gives a type from the types of its operands, and that type is joined into its dst. An instr whose operand is still `Unknown` waits.
|
|
- It walks again until nothing changes. The result is the type of each value, and the return type.
|
|
|
|
**The cells of a walk.** When a walk reaches an instr that makes an object, the first time, it makes a new cell for that instr. On every later pass, it uses the same cell again. So the objects that a walk makes belong to that walk: a fn walked with `Int` and with `Str` makes different cells.
|
|
|
|
**The type cache** is a map from a fn and a list of arg types to the walk of that fn with those types.
|
|
|
|
- A call looks up its callee with the types of its args. If there is no walk yet, it walks the callee. The call gives the walk's return type.
|
|
- **Only what the program reaches is walked,** as in Rust: there is one walk for each list of arg types that a call really passes.
|
|
- **In the key, an object is its cell.** Known values are dropped (`Bool(true)` is `Bool`), so a literal does not make a new walk.
|
|
|
|
**Rounds.** A walk can depend on cells and returns that other walks are still adding to. So infer walks the whole program again, from the entry, until a round changes no cell, no return and no proto, and makes no new walk or cell. A recursive call gives what its walk returned in the round before.
|
|
|
|
**The open problem: infer does not always end.** A walk makes cells, and a key holds cells. So when a cell that a walk made gets into the key of a later call, that call gets a new walk, which makes new cells, which can make another new key. Rust does not have this problem, because every type in a Rust key is written in the program (a struct and its type args), and a call cannot change the type of its args. These programs end at once in node, but infer does not end on them:
|
|
|
|
```js
|
|
// 1. `this` holds the list of nodes. The arrow fn never reads `this`, but it
|
|
// is in the key, and each new walk of it leads to a new node
|
|
let list = null;
|
|
function add(f) { list = { f: f, next: list }; }
|
|
add(() => add(() => 0));
|
|
list.f();
|
|
|
|
// 2. A cell is one type for the object's whole life: the call sees the type
|
|
// of `o.v` after the write, so each round sees one cell more
|
|
const o = { v: 1 };
|
|
function f(x) { o.v = { inner: x }; }
|
|
f(o.v);
|
|
|
|
// 3. A new object goes into a recursive call. The exact types are
|
|
// `{next: Int}`, `{next: {next: Int}}`, ...: as many as `n`, which only the
|
|
// runtime knows. Rust rejects this program too
|
|
function g(n, x) { if (n > 0) g(n - 1, { next: x }); }
|
|
g(3, 0);
|
|
```
|
|
|
|
The same thing happens on a large scale with partial types. Inside a walk, a call first sees the types of an early pass, then wider ones. Each key gets its own walk, and its cells stay in the types for good. The stdlib's promises reach thousands of walks from a 7-line program. The same loops without fns (`for (…) x = { next: x }`) end, because one instr in one walk is one cell.
|
|
|
|
## 5. Representation in C
|
|
|
|
The C type of a value comes from its type only. A type with one member is that member's C type:
|
|
|
|
| member | C |
|
|
|---|---|
|
|
| `Undefined`, `Null` | `undefined_t`, `null_t`: unit types |
|
|
| `Bool` | `bool` |
|
|
| `Int` | `int32_t` |
|
|
| `Float` | `double` |
|
|
| `Str` | `string_t` |
|
|
| `Native` | `native_t`: the native's index |
|
|
| `Obj` | a pointer to the struct of the object's class |
|
|
|
|
A type with several members is a `jsrt_value`: a tag, which says the kind, and the value. A number in a `jsrt_value` is always a double, and an object's tag also says its class. `Unknown` means that the code cannot run.
|
|
|
|
- **The C of an op** is a macro of the runtime (lib/rt/core.h), which picks its code by the C types of its operands. A plain C value becomes a `jsrt_value` with a constant tag, so the C compiler removes the tag and keeps only the code for that kind.
|
|
- **A field that can be absent** has a `has_` flag beside it. Getting it calls a lookup, which goes along the prototype chain.
|
|
- **An op that depends on an object's class**, such as getting a field or calling a closure, tests the tag of a `jsrt_value` with a `switch`, and has code for each class.
|
|
- **An array's struct** has `length`, `cap` and `items`. An element holds undefined for a hole.
|
|
|
|
## 6. Not in this model yet
|
|
|
|
- a bound on the walks: infer must end on every program (section 4)
|
|
- definite initialization: a field that a constructor writes before `this` goes anywhere is never absent
|
|
- narrowing in branches (`if (x !== null)`)
|
|
- objects as struct values, and objects on the stack (escape analysis)
|
|
- fields with computed names (`o[k]` on an object that is not an array), `delete`, `in`
|
|
- typed arrays, `ArrayBuffer`, `DataView`, and iterators
|
|
- `throw`, `try`, `catch`, `finally`, and the TDZ
|
|
- getters and setters
|