lang: Verify RIL packages

fb5beff8c704d4f621edc02bc34d7155f05bf23e02a255f1c439707c79426910
Decoded RIL is untrusted input, but nothing checked that a package is
well typed before it reaches code generation.

Add `std::lang::il::verify`, which checks the layouts, the data section,
and the control flow and slot types of every function in a decoded
package against configured capacities. A rejected package reports the
rule that failed. Add verifier unit tests and `make verify-test`, which
accepts or rejects the binary RIL of every compiler fixture as
`test/verify/expected` says.

Assisted-by: Codex:gpt-6
Assisted-by: Claude:opus-5.5
Alexis Sellier committed ago 1 parent fb2c0458
lib/std/lang/il.rad +1 -0
73 73
// TODO: Labels should have their own type.
74 74
// TODO: Blocks should have an instruction in `Instr`.
75 75
76 76
export mod printer;
77 77
export mod binary;
78 +
export mod verify;
78 79
79 80
use std::lang::alloc;
80 81
81 82
/// DeviceAccess flag bits that contain the byte width.
82 83
export constant DEVICE_WIDTH_MASK: u64 = 0xff;
lib/std/lang/il/verify.rad added +1249 -0
1 +
//! RIL verifier.
2 +
//!
3 +
//! Decides whether a decoded package is safe to compile to native code and run in a
4 +
//! domain, whatever produced it. Every RIL input is hostile. The checks keep the memory
5 +
//! of a domain type-stable: every object has a layout, the slots of a layout that hold
6 +
//! pointers, slices and function values are written only with values of their kind, and
7 +
//! every pointer that is accessed is non-null and valid by construction. Pointers are
8 +
//! never checked on access. Authority, termination and traps are outside its scope.
9 +
//!
10 +
//! Registers have one type, fixed at their single definition. A pointer register also
11 +
//! tracks a constant offset into its layout, and whether it is derived from a `reserve`
12 +
//! of the current function, a local pointer. Only a local pointer can hold non-owning
13 +
//! pointers, so they never outlive their frame.
14 +
//!
15 +
//! The decoder establishes the structure that the checks rely on: table indices are in
16 +
//! range, layouts are well formed (see [`layout`]), argument ranges lie within the pools
17 +
//! of their function, and branch targets are blocks of the function. [`verifyProgram`]
18 +
//! checks everything else, and [`verifyPackage`] adds the rules of a loadable package.
19 +
20 +
export mod layout;
21 +
export mod flow;
22 +
export mod data;
23 +
24 +
@test export mod tests;
25 +
26 +
use std::mem;
27 +
use std::collections::dict;
28 +
use std::lang::alloc;
29 +
use std::lang::il;
30 +
use std::lang::il::binary;
31 +
32 +
///////////////
33 +
// Constants //
34 +
///////////////
35 +
36 +
/// Rounding of dictionary storage: the table must be a power of two and at most half full.
37 +
constant DICT_MINIMUM: u32 = 2;
38 +
/// Largest alignment of an object in a frame, which is the alignment of the stack.
39 +
constant FRAME_ALIGNMENT: u32 = 16;
40 +
/// Largest symbol count that fits a dictionary table size in 32 bits.
41 +
constant SYMBOLS_MAX: u32 = 0x3fffffff;
42 +
43 +
///////////
44 +
// Types //
45 +
///////////
46 +
47 +
/// Limits and parameters of the verifier.
48 +
export record Config: Copy {
49 +
    /// Exclusive upper bound for register numbers in a function.
50 +
    registers: u32,
51 +
    /// Maximum number of blocks in a function.
52 +
    blocks: u32,
53 +
    /// Maximum size of a layout in bytes.
54 +
    layoutSize: u32,
55 +
    /// Maximum nesting of sub and array nodes in a layout.
56 +
    layoutDepth: u32,
57 +
    /// Maximum number of parameters of a function, signature or block, and of arguments
58 +
    /// of a call. Arguments beyond the registers go to the stack of the caller.
59 +
    params: u32,
60 +
    /// Size in bytes of the Env record that the kernel passes to the entry function.
61 +
    envSize: u32,
62 +
}
63 +
64 +
/// The rule that an error violates.
65 +
export union Rule: Copy {
66 +
    /// The scratch arena is full.
67 +
    Storage,
68 +
    /// A count or size exceeds a limit of the configuration.
69 +
    Limit,
70 +
    /// A symbol is empty, duplicated, or does not name a definition of the package.
71 +
    Symbol,
72 +
    /// The layout or signature table is malformed.
73 +
    Layout,
74 +
    /// Blocks, terminators or parameters are malformed.
75 +
    Structure,
76 +
    /// A register is out of range, defined twice, or used where its definition does not
77 +
    /// dominate the use.
78 +
    Register,
79 +
    /// An operand has the wrong kind: data where a pointer or function value is needed.
80 +
    Type,
81 +
    /// A nullable pointer or function value is used where a non-null one is needed.
82 +
    Null,
83 +
    /// An offset, index or region lies outside its layout.
84 +
    Bounds,
85 +
    /// A data access overlaps a slot, or a slot access is not at a slot of the right kind.
86 +
    Slot,
87 +
    /// A pointer is used as a pointer to a layout that it does not view.
88 +
    View,
89 +
    /// A pointer of the wrong class: a non-owning pointer where an owning one is needed or
90 +
    /// where it could outlive its frame.
91 +
    Class,
92 +
    /// A write through a pointer to read-only memory, or a read-only pointer used as writable.
93 +
    Mutability,
94 +
    /// The callee of a call, or its return type, is invalid.
95 +
    Call,
96 +
    /// The number of arguments does not match the parameters.
97 +
    Arity,
98 +
    /// A return type or returned value is invalid.
99 +
    Return,
100 +
    /// A data initializer is invalid.
101 +
    Data,
102 +
    /// A package-level rule is violated.
103 +
    Package,
104 +
}
105 +
106 +
/// Where an error was found.
107 +
export union Place: Copy {
108 +
    /// The package as a whole.
109 +
    Package,
110 +
    /// A layout, by index.
111 +
    Layout(u32),
112 +
    /// A signature, by index.
113 +
    Signature(u32),
114 +
    /// A data definition, by index.
115 +
    Data(u32),
116 +
    /// A function, by index.
117 +
    Fn(u32),
118 +
    /// An instruction of a function.
119 +
    Instr {
120 +
        /// Index of the function.
121 +
        func: u32,
122 +
        /// Index of the block.
123 +
        block: u32,
124 +
        /// Index of the instruction in the block.
125 +
        instr: u32,
126 +
    },
127 +
}
128 +
129 +
/// A rule violation and its location.
130 +
export record Error: Copy {
131 +
    /// The rule that is violated.
132 +
    rule: Rule,
133 +
    /// Where the violation is.
134 +
    place: Place,
135 +
}
136 +
137 +
/// Name of a rule.
138 +
export fn ruleName(rule: Rule) -> *[u8] {
139 +
    match rule {
140 +
        case Rule::Storage => return "Storage",
141 +
        case Rule::Limit => return "Limit",
142 +
        case Rule::Symbol => return "Symbol",
143 +
        case Rule::Layout => return "Layout",
144 +
        case Rule::Structure => return "Structure",
145 +
        case Rule::Register => return "Register",
146 +
        case Rule::Type => return "Type",
147 +
        case Rule::Null => return "Null",
148 +
        case Rule::Bounds => return "Bounds",
149 +
        case Rule::Slot => return "Slot",
150 +
        case Rule::View => return "View",
151 +
        case Rule::Class => return "Class",
152 +
        case Rule::Mutability => return "Mutability",
153 +
        case Rule::Call => return "Call",
154 +
        case Rule::Arity => return "Arity",
155 +
        case Rule::Return => return "Return",
156 +
        case Rule::Data => return "Data",
157 +
        case Rule::Package => return "Package",
158 +
    }
159 +
}
160 +
161 +
/// The error for a full scratch arena.
162 +
export constant STORAGE: Error = Error { rule: Rule::Storage, place: Place::Package };
163 +
164 +
/// Reference to the signature of a function value.
165 +
export union SigRef: Copy {
166 +
    /// An entry of the signature table of the program.
167 +
    Table(u32),
168 +
    /// The signature of a function of the program, by index.
169 +
    Func(u32),
170 +
}
171 +
172 +
/// Facts about a pointer register.
173 +
record PtrState: Copy {
174 +
    /// Layout that the pointer views.
175 +
    layout: u32,
176 +
    /// Constant byte offset of the pointer inside its layout.
177 +
    offset: u32,
178 +
    /// Whether the pointee lives as long as the domain.
179 +
    own: bool,
180 +
    /// Whether the pointee can be written.
181 +
    mutable: bool,
182 +
    /// Whether the pointer can be zero.
183 +
    nullable: bool,
184 +
    /// Whether the pointer is derived from a `reserve` of the current function.
185 +
    local: bool,
186 +
}
187 +
188 +
/// Facts about a function value register.
189 +
record FnState: Copy {
190 +
    /// Signature of the function value.
191 +
    sig: SigRef,
192 +
    /// Whether the value can be zero.
193 +
    nullable: bool,
194 +
}
195 +
196 +
/// Type of a register, fixed at its definition.
197 +
union RegState: Copy {
198 +
    /// Plain data.
199 +
    Data,
200 +
    /// A pointer.
201 +
    Ptr(PtrState),
202 +
    /// A function value.
203 +
    Fn(FnState),
204 +
}
205 +
206 +
/// Owner of a register slot that no function has defined.
207 +
constant NO_OWNER: u32 = 0xffffffff;
208 +
209 +
/// The definition of a register in the function that is checked.
210 +
record Def: Copy {
211 +
    /// Type of the register.
212 +
    state: RegState,
213 +
    /// Block that defines the register.
214 +
    block: u32,
215 +
    /// Index of the function that last defined the register. A slot that belongs to another
216 +
    /// function is free.
217 +
    owner: u32,
218 +
}
219 +
220 +
/// Fixed facts about the program under verification.
221 +
export record Context {
222 +
    /// The program.
223 +
    prog: il::Program,
224 +
    /// The limits.
225 +
    config: Config,
226 +
    /// The checked layout table.
227 +
    table: layout::Table,
228 +
    /// Index of each function by name.
229 +
    fnNames: dict::Dict,
230 +
    /// Index of each data definition by name.
231 +
    dataNames: dict::Dict,
232 +
}
233 +
234 +
/// State of the verification of one function.
235 +
record Verifier {
236 +
    /// Facts about the program.
237 +
    ctx: Context,
238 +
    /// Control flow tables of the function.
239 +
    flow: flow::Flow,
240 +
    /// Definition of each register number, shared by the functions in turn.
241 +
    defs: *mut [Def],
242 +
    /// The function that is checked.
243 +
    func: *il::Fn,
244 +
    /// Index of the function.
245 +
    fnIndex: u32,
246 +
    /// Index of the block that is checked.
247 +
    block: u32,
248 +
    /// Index of the instruction that is checked.
249 +
    instr: u32,
250 +
}
251 +
252 +
/// Sizes that the per-function tables must cover.
253 +
record Sizes: Copy {
254 +
    /// Number of registers.
255 +
    registers: u32,
256 +
    /// Number of blocks.
257 +
    blocks: u32,
258 +
    /// Number of control flow edges.
259 +
    edges: u32,
260 +
}
261 +
262 +
/// Role of a declared type, which selects the rules for it.
263 +
union Role: Copy {
264 +
    /// Type of a parameter.
265 +
    Param,
266 +
    /// Return type.
267 +
    Return,
268 +
}
269 +
270 +
////////////////
271 +
// Signatures //
272 +
////////////////
273 +
274 +
/// Number of parameters of a signature.
275 +
fn sigLen(c: &Context, s: SigRef) -> u32 {
276 +
    match s {
277 +
        case SigRef::Table(i) => return c.prog.signatures[i].params.len,
278 +
        case SigRef::Func(i) => return c.prog.fns[i].params.len,
279 +
    }
280 +
}
281 +
282 +
/// Type of parameter `k` of a signature.
283 +
fn sigParam(c: &Context, s: SigRef, k: u32) -> il::ValType {
284 +
    match s {
285 +
        case SigRef::Table(i) => return c.prog.signatures[i].params[k],
286 +
        case SigRef::Func(i) => return c.prog.fns[i].params[k].type,
287 +
    }
288 +
}
289 +
290 +
/// Return type of a signature.
291 +
fn sigRet(c: &Context, s: SigRef) -> il::ValType {
292 +
    match s {
293 +
        case SigRef::Table(i) => return c.prog.signatures[i].ret,
294 +
        case SigRef::Func(i) => return c.prog.fns[i].returnType,
295 +
    }
296 +
}
297 +
298 +
/// Whether two value types are equal. The width of data is not part of its type, and a
299 +
/// function value inside a signature is compared by its signature index.
300 +
fn typeEq(a: il::ValType, b: il::ValType) -> bool {
301 +
    match a {
302 +
        case il::ValType::Void => {
303 +
            if let case il::ValType::Void = b {
304 +
                return true;
305 +
            }
306 +
        },
307 +
        case il::ValType::Data(_) => {
308 +
            if let case il::ValType::Data(_) = b {
309 +
                return true;
310 +
            }
311 +
        },
312 +
        case il::ValType::Ptr(p) => {
313 +
            if let case il::ValType::Ptr(q) = b {
314 +
                return p.layout == q.layout and p.own == q.own and p.mutable == q.mutable
315 +
                    and p.nullable == q.nullable;
316 +
            }
317 +
        },
318 +
        case il::ValType::Fn(i) => {
319 +
            if let case il::ValType::Fn(j) = b {
320 +
                return i == j;
321 +
            }
322 +
        },
323 +
    }
324 +
    return false;
325 +
}
326 +
327 +
/// Whether two signatures are equal: the same parameters and result type.
328 +
export fn sigEq(c: &Context, a: SigRef, b: SigRef) -> bool {
329 +
    let n = sigLen(c, a);
330 +
    if n <> sigLen(c, b) or not typeEq(sigRet(c, a), sigRet(c, b)) {
331 +
        return false;
332 +
    }
333 +
    for k in 0..n {
334 +
        if not typeEq(sigParam(c, a, k), sigParam(c, b, k)) {
335 +
            return false;
336 +
        }
337 +
    }
338 +
    return true;
339 +
}
340 +
341 +
////////////////////////
342 +
// Declarations pass  //
343 +
////////////////////////
344 +
345 +
/// Build the error for a violation at function `index`.
346 +
fn failFn(index: u32, rule: Rule) -> Error {
347 +
    return Error { rule, place: Place::Fn(index) };
348 +
}
349 +
350 +
/// Check a declared type: a parameter or result of a function or signature, or a block
351 +
/// parameter. Pointers to objects with non-owning slots must not own their pointee, and a
352 +
/// function returns only owning pointers, because a non-owning pointer can point into
353 +
/// the frame that the return discards.
354 +
fn checkType(c: &Context, t: il::ValType, role: Role, place: Place) throws (Error) {
355 +
    match t {
356 +
        case il::ValType::Void => {
357 +
            if let case Role::Param = role {
358 +
                throw Error { rule: Rule::Type, place };
359 +
            }
360 +
        },
361 +
        case il::ValType::Ptr(p) => {
362 +
            if p.own and c.table.infos[p.layout].refs {
363 +
                throw Error { rule: Rule::Layout, place };
364 +
            }
365 +
            if let case Role::Return = role {
366 +
                if not p.own {
367 +
                    throw Error { rule: Rule::Return, place };
368 +
                }
369 +
            }
370 +
        },
371 +
        else => {},
372 +
    }
373 +
}
374 +
375 +
/// Check the signature table.
376 +
fn checkSignatures(c: &Context) throws (Error) {
377 +
    for i in 0..c.prog.signatures.len {
378 +
        let sig = c.prog.signatures[i];
379 +
        if sig.params.len > c.config.params {
380 +
            throw Error { rule: Rule::Limit, place: Place::Signature(i) };
381 +
        }
382 +
        for param in sig.params {
383 +
            try checkType(c, param, Role::Param, Place::Signature(i));
384 +
        }
385 +
        try checkType(c, sig.ret, Role::Return, Place::Signature(i));
386 +
    }
387 +
}
388 +
389 +
/// Check the declarations and the shape of every function, and measure the largest.
390 +
/// Registers are below the limit, every block ends with exactly one terminator, and
391 +
/// branch targets are blocks of the function.
392 +
fn measure(c: &Context) -> Sizes throws (Error) {
393 +
    let mut sizes = Sizes { registers: 0, blocks: 0, edges: 0 };
394 +
    for fi in 0..c.prog.fns.len {
395 +
        let func = c.prog.fns[fi];
396 +
        let mut regs: u32 = 0;
397 +
        let mut edges: u32 = 0;
398 +
        if func.params.len > c.config.params {
399 +
            throw failFn(fi, Rule::Limit);
400 +
        }
401 +
        for param in func.params {
402 +
            try checkType(c, param.type, Role::Param, Place::Fn(fi));
403 +
            set regs = try reserveReg(c, regs, param.value, Place::Fn(fi));
404 +
        }
405 +
        try checkType(c, func.returnType, Role::Return, Place::Fn(fi));
406 +
        if func.isExtern {
407 +
            if func.blocks.len > 0 {
408 +
                throw failFn(fi, Rule::Structure);
409 +
            }
410 +
            continue;
411 +
        }
412 +
        if func.blocks.len == 0 {
413 +
            throw failFn(fi, Rule::Structure);
414 +
        }
415 +
        if func.blocks.len > c.config.blocks {
416 +
            throw failFn(fi, Rule::Limit);
417 +
        }
418 +
        for b in 0..func.blocks.len {
419 +
            let block = func.blocks[b];
420 +
            let at = Place::Instr { func: fi, block: b, instr: 0 };
421 +
            if block.instrs.len == 0 or (b == 0 and block.params.len > 0) {
422 +
                throw Error { rule: Rule::Structure, place: at };
423 +
            }
424 +
            if block.params.len > c.config.params {
425 +
                throw Error { rule: Rule::Limit, place: at };
426 +
            }
427 +
            for param in block.params {
428 +
                try checkType(c, param.type, Role::Param, at);
429 +
                set regs = try reserveReg(c, regs, param.value, at);
430 +
            }
431 +
            for i in 0..block.instrs.len {
432 +
                let place = Place::Instr { func: fi, block: b, instr: i };
433 +
                if il::isTerminator(block.instrs[i]) <> (i == block.instrs.len - 1) {
434 +
                    throw Error { rule: Rule::Structure, place };
435 +
                }
436 +
                if let reg = il::instrDst(block.instrs[i]) {
437 +
                    set regs = try reserveReg(c, regs, reg, place);
438 +
                }
439 +
            }
440 +
            for k in 0..il::successorCount(func, b) {
441 +
                if il::successor(func, b, k) >= func.blocks.len {
442 +
                    throw Error { rule: Rule::Structure, place: at };
443 +
                }
444 +
            }
445 +
            set edges += il::successorCount(func, b);
446 +
        }
447 +
        set sizes.registers = regs if regs > sizes.registers else sizes.registers;
448 +
        set sizes.blocks = func.blocks.len if func.blocks.len > sizes.blocks else sizes.blocks;
449 +
        set sizes.edges = edges if edges > sizes.edges else sizes.edges;
450 +
    }
451 +
    return sizes;
452 +
}
453 +
454 +
/// Check that register `r` is below the limit. Return the number of registers needed to
455 +
/// hold it, given the `count` needed so far.
456 +
fn reserveReg(c: &Context, count: u32, r: il::Reg, place: Place) -> u32 throws (Error) {
457 +
    if r.n >= c.config.registers {
458 +
        throw Error { rule: Rule::Limit, place };
459 +
    }
460 +
    if r.n >= count {
461 +
        return r.n + 1;
462 +
    }
463 +
    return count;
464 +
}
465 +
466 +
/////////////////////
467 +
// Registers       //
468 +
/////////////////////
469 +
470 +
/// Build the error for a rule violation at the current instruction.
471 +
fn fail(v: &Verifier, rule: Rule) -> Error {
472 +
    return Error {
473 +
        rule, place: Place::Instr { func: v.fnIndex, block: v.block, instr: v.instr },
474 +
    };
475 +
}
476 +
477 +
/// The register state of a value of a declared type.
478 +
fn declared(t: il::ValType) -> RegState {
479 +
    match t {
480 +
        case il::ValType::Void, il::ValType::Data(_) => return RegState::Data,
481 +
        case il::ValType::Ptr(p) => return RegState::Ptr(PtrState {
482 +
            layout: p.layout, offset: 0, own: p.own, mutable: p.mutable, nullable: p.nullable,
483 +
            local: false,
484 +
        }),
485 +
        case il::ValType::Fn(sig) => return RegState::Fn(FnState {
486 +
            sig: SigRef::Table(sig), nullable: false,
487 +
        }),
488 +
    }
489 +
}
490 +
491 +
/// Define register `r` at the current block with state `s`. A register has one definition.
492 +
fn define(v: &mut Verifier, r: il::Reg, s: RegState) throws (Error) {
493 +
    if r.n >= v.defs.len or v.defs[r.n].owner == v.fnIndex {
494 +
        throw fail(v, Rule::Register);
495 +
    }
496 +
    set v.defs[r.n] = Def { state: s, block: v.block, owner: v.fnIndex };
497 +
}
498 +
499 +
/// The state of a register at its use. Its definition must dominate the use.
500 +
fn state(v: &Verifier, r: il::Reg) -> RegState throws (Error) {
501 +
    if r.n >= v.defs.len or v.defs[r.n].owner <> v.fnIndex
502 +
        or not flow::dominates(&v.flow, v.defs[r.n].block, v.block) {
503 +
        throw fail(v, Rule::Register);
504 +
    }
505 +
    return v.defs[r.n].state;
506 +
}
507 +
508 +
/// The state of a value, which must be defined. An address of a symbol is data. A function
509 +
/// symbol is also a function value. A caller that needs data only ignores the state.
510 +
fn operand(v: &Verifier, val: il::Val) -> RegState throws (Error) {
511 +
    match val {
512 +
        case il::Val::Reg(r) => return try state(v, r),
513 +
        case il::Val::Imm(_), il::Val::Undef => return RegState::Data,
514 +
        case il::Val::DataSym(name) => {
515 +
            if dict::get(&v.ctx.dataNames, name) == nil {
516 +
                throw fail(v, Rule::Symbol);
517 +
            }
518 +
            return RegState::Data;
519 +
        },
520 +
        case il::Val::FnAddr(name) => {
521 +
            let index = dict::get(&v.ctx.fnNames, name) else {
522 +
                throw fail(v, Rule::Symbol);
523 +
            };
524 +
            if v.ctx.prog.fns[index as u32].isExtern {
525 +
                throw fail(v, Rule::Symbol);
526 +
            }
527 +
            return RegState::Fn(FnState { sig: SigRef::Func(index as u32), nullable: false });
528 +
        },
529 +
    }
530 +
}
531 +
532 +
/// Whether a value is the immediate zero.
533 +
fn isZero(val: il::Val) -> bool {
534 +
    if let case il::Val::Imm(n) = val {
535 +
        return n == 0;
536 +
    }
537 +
    return false;
538 +
}
539 +
540 +
/// The state of a pointer register that can be dereferenced.
541 +
fn accessible(v: &Verifier, r: il::Reg) -> PtrState throws (Error) {
542 +
    let case RegState::Ptr(p) = try state(v, r) else {
543 +
        throw fail(v, Rule::Type);
544 +
    };
545 +
    if p.nullable {
546 +
        throw fail(v, Rule::Null);
547 +
    }
548 +
    return p;
549 +
}
550 +
551 +
/// The state of a pointer register that can be dereferenced and written.
552 +
fn writable(v: &Verifier, r: il::Reg) -> PtrState throws (Error) {
553 +
    let p = try accessible(v, r);
554 +
    if not p.mutable {
555 +
        throw fail(v, Rule::Mutability);
556 +
    }
557 +
    return p;
558 +
}
559 +
560 +
/// Check that `width` bytes at `delta` bytes from the pointer are inside its layout.
561 +
/// Return their offset in the layout. A region can end at the end of the layout.
562 +
fn extent(v: &Verifier, p: PtrState, delta: i64, width: u64) -> u64 throws (Error) {
563 +
    let o = p.offset as i64 + delta;
564 +
    if o < 0 or o as u64 + width > layout::size(&v.ctx.table, p.layout) {
565 +
        throw fail(v, Rule::Bounds);
566 +
    }
567 +
    return o as u64;
568 +
}
569 +
570 +
/// Check that a pointer of class `own` and mutability `mutable` may be used where the
571 +
/// pointer type `t` is declared.
572 +
fn rights(v: &Verifier, t: il::PtrType, own: bool, mutable: bool) throws (Error) {
573 +
    if t.own and not own {
574 +
        throw fail(v, Rule::Class);
575 +
    }
576 +
    if t.mutable and not mutable {
577 +
        throw fail(v, Rule::Mutability);
578 +
    }
579 +
}
580 +
581 +
/// Check that a pointer fits a declared pointer type.
582 +
fn fits(v: &Verifier, p: PtrState, t: il::PtrType) throws (Error) {
583 +
    if p.nullable and not t.nullable {
584 +
        throw fail(v, Rule::Null);
585 +
    }
586 +
    try rights(v, t, p.own, p.mutable);
587 +
    if not layout::view(&v.ctx.table, p.layout, p.offset as u64, t.layout) {
588 +
        throw fail(v, Rule::View);
589 +
    }
590 +
}
591 +
592 +
/// Check that a value can be used where a value of type `t` is declared.
593 +
fn assign(v: &Verifier, val: il::Val, t: il::ValType) throws (Error) {
594 +
    try assignState(v, val, try operand(v, val), t);
595 +
}
596 +
597 +
/// Check a value against its declared type, with the facts that hold at its use.
598 +
fn assignState(v: &Verifier, val: il::Val, s: RegState, t: il::ValType) throws (Error) {
599 +
    match t {
600 +
        case il::ValType::Void => throw fail(v, Rule::Type),
601 +
        case il::ValType::Data(_) => {},
602 +
        case il::ValType::Ptr(want) => {
603 +
            if let case RegState::Ptr(p) = s {
604 +
                try fits(v, p, want);
605 +
            } else if isZero(val) {
606 +
                if not want.nullable {
607 +
                    throw fail(v, Rule::Null);
608 +
                }
609 +
            } else {
610 +
                throw fail(v, Rule::Type);
611 +
            }
612 +
        },
613 +
        case il::ValType::Fn(sig) => {
614 +
            let case RegState::Fn(f) = s else {
615 +
                throw fail(v, Rule::Type);
616 +
            };
617 +
            if f.nullable {
618 +
                throw fail(v, Rule::Null);
619 +
            }
620 +
            if not sigEq(&v.ctx, f.sig, SigRef::Table(sig)) {
621 +
                throw fail(v, Rule::Type);
622 +
            }
623 +
        },
624 +
    }
625 +
}
626 +
627 +
/// Check that `width` bytes at `offset` from a writable pointer hold no slot.
628 +
fn writePlain(v: &Verifier, r: il::Reg, offset: i64, width: u64) throws (Error) {
629 +
    let p = try writable(v, r);
630 +
    let o = try extent(v, p, offset, width);
631 +
    if not layout::plain(&v.ctx.table, p.layout, o, o + width) {
632 +
        throw fail(v, Rule::Slot);
633 +
    }
634 +
}
635 +
636 +
/// Check that a pointer addresses `count` consecutive objects of layout `e`.
637 +
fn arrayOf(v: &Verifier, p: PtrState, e: u32, count: u32) throws (Error) {
638 +
    let t = &v.ctx.table;
639 +
    let o = try extent(v, p, 0, layout::size(t, e) * count as u64);
640 +
    if not layout::arrayView(t, p.layout, o, e, count) {
641 +
        throw fail(v, Rule::View);
642 +
    }
643 +
}
644 +
645 +
/// The slice slot that a pointer addresses, whose elements must be of layout `e`, or a plain
646 +
/// layout of the same size when `e` is plain.
647 +
fn sliceSlot(v: &Verifier, p: PtrState, e: u32) -> il::PtrType throws (Error) {
648 +
    let t = &v.ctx.table;
649 +
    let o = try extent(v, p, 0, 0);
650 +
    let case il::SlotKind::Slice(slot) = layout::slotAt(t, p.layout, o) else {
651 +
        throw fail(v, Rule::Slot);
652 +
    };
653 +
    let same = slot.layout == e or (layout::isPlain(t, slot.layout) and layout::isPlain(t, e)
654 +
        and layout::size(t, slot.layout) == layout::size(t, e));
655 +
    if not same {
656 +
        throw fail(v, Rule::View);
657 +
    }
658 +
    return slot;
659 +
}
660 +
661 +
/// A slice slot that the slice instructions write.
662 +
record SliceDest: Copy {
663 +
    /// Type of the slot.
664 +
    slot: il::PtrType,
665 +
    /// Whether the slot is in an object of the current frame.
666 +
    local: bool,
667 +
}
668 +
669 +
/// Check the destination of a slice instruction: a writable slice slot of elements `e`.
670 +
fn sliceDest(v: &Verifier, dst: il::Reg, e: u32) -> SliceDest throws (Error) {
671 +
    let d = try writable(v, dst);
672 +
    return SliceDest { slot: try sliceSlot(v, d, e), local: d.local };
673 +
}
674 +
675 +
/// Check that a slice slot can receive a slice over memory of class `own` and
676 +
/// mutability `mutable`. A slot that does not own its pointee keeps it only in the frame.
677 +
fn sliceFrom(v: &Verifier, d: SliceDest, own: bool, mutable: bool) throws (Error) {
678 +
    if not d.slot.own and not own and not d.local {
679 +
        throw fail(v, Rule::Class);
680 +
    }
681 +
    try rights(v, d.slot, own, mutable);
682 +
}
683 +
684 +
///////////////////
685 +
// Instructions  //
686 +
///////////////////
687 +
688 +
/// Check a store of a pointer or function value into a slot.
689 +
fn checkStorePtr(v: &Verifier, val: il::Val, dst: il::Reg, offset: i32) throws (Error) {
690 +
    let s = try operand(v, val);
691 +
    let p = try writable(v, dst);
692 +
    let o = try extent(v, p, offset as i64, 0);
693 +
    let slot = layout::slotAt(&v.ctx.table, p.layout, o) else {
694 +
        throw fail(v, Rule::Slot);
695 +
    };
696 +
    match slot {
697 +
        case il::SlotKind::Ptr(want) => {
698 +
            if let case RegState::Ptr(q) = s {
699 +
                // A slot that does not own its pointee is written only with owning
700 +
                // pointers, or in an object of the current frame.
701 +
                if not want.own and not q.own and not p.local {
702 +
                    throw fail(v, Rule::Class);
703 +
                }
704 +
                try fits(v, q, want);
705 +
            } else if not isZero(val) {
706 +
                throw fail(v, Rule::Type);
707 +
            }
708 +
        },
709 +
        case il::SlotKind::Fn(sig) => {
710 +
            if let case RegState::Fn(f) = s {
711 +
                if not sigEq(&v.ctx, f.sig, SigRef::Table(sig)) {
712 +
                    throw fail(v, Rule::Type);
713 +
                }
714 +
            } else if not isZero(val) {
715 +
                throw fail(v, Rule::Type);
716 +
            }
717 +
        },
718 +
        else => throw fail(v, Rule::Slot),
719 +
    }
720 +
}
721 +
722 +
/// Check a copy of an object of layout `l`. The source holds such an object. The destination
723 +
/// is a plain region, which takes any bytes, or holds such an object, and then a copy of
724 +
/// borrowed slots stays in the frame. Both regions are aligned for `l`.
725 +
fn checkBlit(v: &Verifier, dst: il::Reg, src: il::Reg, l: u32) throws (Error) {
726 +
    let t = &v.ctx.table;
727 +
    let d = try writable(v, dst);
728 +
    let s = try accessible(v, src);
729 +
    let size = layout::size(t, l);
730 +
    let od = try extent(v, d, 0, size);
731 +
    let os = try extent(v, s, 0, size);
732 +
    if not layout::view(t, s.layout, os, l) {
733 +
        throw fail(v, Rule::View);
734 +
    }
735 +
    if layout::plainRegion(t, d.layout, od, size, layout::alignment(t, l)) {
736 +
        return;
737 +
    }
738 +
    if not layout::view(t, d.layout, od, l) {
739 +
        throw fail(v, Rule::View);
740 +
    }
741 +
    if t.infos[l].refs and not d.local {
742 +
        throw fail(v, Rule::Class);
743 +
    }
744 +
}
745 +
746 +
/// Check a call, and define its result.
747 +
fn checkCall(
748 +
    v: &mut Verifier, retTy: il::ValType, dst: ?il::Reg, callee: il::Val, args: il::ArgRange
749 +
) throws (Error) {
750 +
    let case RegState::Fn(f) = try operand(v, callee) else {
751 +
        throw fail(v, Rule::Call);
752 +
    };
753 +
    if f.nullable {
754 +
        throw fail(v, Rule::Null);
755 +
    }
756 +
    if not typeEq(retTy, sigRet(&v.ctx, f.sig)) {
757 +
        throw fail(v, Rule::Call);
758 +
    }
759 +
    let values = il::argVals(v.func, args);
760 +
    if values.len <> sigLen(&v.ctx, f.sig) {
761 +
        throw fail(v, Rule::Arity);
762 +
    }
763 +
    for k in 0..values.len {
764 +
        try assign(v, values[k], sigParam(&v.ctx, f.sig, k));
765 +
    }
766 +
    if let reg = dst {
767 +
        if let case il::ValType::Void = retTy {
768 +
            throw fail(v, Rule::Call);
769 +
        }
770 +
        try define(v, reg, declared(retTy));
771 +
    }
772 +
}
773 +
774 +
/// Check the arguments that a branch passes to block `target`. A comparison with zero
775 +
/// can prove that `present` is non-null on this edge.
776 +
fn checkEdge(v: &Verifier, target: u32, args: il::ArgRange, present: ?il::Reg) throws (Error) {
777 +
    let params = v.func.blocks[target].params;
778 +
    let values = il::argVals(v.func, args);
779 +
    if values.len <> params.len {
780 +
        throw fail(v, Rule::Arity);
781 +
    }
782 +
    for k in 0..values.len {
783 +
        let mut s = try operand(v, values[k]);
784 +
        if let r = present {
785 +
            if values[k] == il::Val::Reg(r) {
786 +
                match &mut s {
787 +
                    case RegState::Ptr(p) => set p.nullable = false,
788 +
                    case RegState::Fn(f) => set f.nullable = false,
789 +
                    else => {},
790 +
                }
791 +
            }
792 +
        }
793 +
        try assignState(v, values[k], s, params[k].type);
794 +
    }
795 +
}
796 +
797 +
/// Check one instruction, and define its result.
798 +
fn checkInstr(v: &mut Verifier, instr: il::Instr) throws (Error) {
799 +
    match instr {
800 +
        case il::Instr::Reserve { dst, layout } => {
801 +
            if v.ctx.prog.layouts[layout].alignment > FRAME_ALIGNMENT {
802 +
                throw fail(v, Rule::Limit);
803 +
            }
804 +
            try define(v, dst, RegState::Ptr(PtrState {
805 +
                layout, offset: 0, own: false, mutable: true, nullable: false, local: true,
806 +
            }));
807 +
        },
808 +
        case il::Instr::Load { typ, dst, src, offset } => {
809 +
            let p = try accessible(v, src);
810 +
            try extent(v, p, offset as i64, il::typeSize(typ) as u64);
811 +
            try define(v, dst, RegState::Data);
812 +
        },
813 +
        case il::Instr::Sload { typ, dst, src, offset } => {
814 +
            let p = try accessible(v, src);
815 +
            try extent(v, p, offset as i64, il::typeSize(typ) as u64);
816 +
            try define(v, dst, RegState::Data);
817 +
        },
818 +
        case il::Instr::Store { typ, src, dst, offset } => {
819 +
            try operand(v, src);
820 +
            try writePlain(v, dst, offset as i64, il::typeSize(typ) as u64);
821 +
        },
822 +
        case il::Instr::Blit { dst, src, layout } => {
823 +
            try checkBlit(v, dst, src, layout);
824 +
        },
825 +
        case il::Instr::Copy { dst, val } => {
826 +
            if let case il::Val::DataSym(name) = val {
827 +
                let index = dict::get(&v.ctx.dataNames, name) else {
828 +
                    throw fail(v, Rule::Symbol);
829 +
                };
830 +
                let item = v.ctx.prog.data[index as u32];
831 +
                try define(v, dst, RegState::Ptr(PtrState {
832 +
                    layout: item.layout, offset: 0, own: true, mutable: not item.readOnly,
833 +
                    nullable: false, local: false,
834 +
                }));
835 +
            } else {
836 +
                try define(v, dst, try operand(v, val));
837 +
            }
838 +
        },
839 +
        case il::Instr::Field { dst, src, offset } => {
840 +
            let p = try accessible(v, src);
841 +
            let o = try extent(v, p, offset as i64, 0);
842 +
            let mut q = p;
843 +
            set q.offset = o as u32;
844 +
            try define(v, dst, RegState::Ptr(q));
845 +
        },
846 +
        case il::Instr::Elem { dst, base, index, layout: e, count } => {
847 +
            try operand(v, index);
848 +
            let p = try accessible(v, base);
849 +
            try arrayOf(v, p, e, count);
850 +
            try define(v, dst, RegState::Ptr(PtrState {
851 +
                layout: e, offset: 0, own: p.own, mutable: p.mutable, nullable: false,
852 +
                local: p.local,
853 +
            }));
854 +
        },
855 +
        case il::Instr::SliceElem { dst, slice, index, layout: e } => {
856 +
            try operand(v, index);
857 +
            let p = try accessible(v, slice);
858 +
            let slot = try sliceSlot(v, p, e);
859 +
            try define(v, dst, RegState::Ptr(PtrState {
860 +
                layout: e, offset: 0, own: slot.own, mutable: slot.mutable, nullable: false,
861 +
                local: false,
862 +
            }));
863 +
        },
864 +
        case il::Instr::SliceNew { dst, base, layout: e, count, start, end } => {
865 +
            let d = try sliceDest(v, dst, e);
866 +
            try operand(v, start);
867 +
            try operand(v, end);
868 +
            let s = try operand(v, base);
869 +
            // With no elements, nothing is reachable and the base can be any value.
870 +
            if count > 0 {
871 +
                let case RegState::Ptr(p) = s else {
872 +
                    throw fail(v, Rule::Type);
873 +
                };
874 +
                if p.nullable {
875 +
                    throw fail(v, Rule::Null);
876 +
                }
877 +
                try arrayOf(v, p, e, count);
878 +
                try sliceFrom(v, d, p.own, p.mutable);
879 +
            }
880 +
        },
881 +
        case il::Instr::SliceSub { dst, src, layout: e, start, end } => {
882 +
            let d = try sliceDest(v, dst, e);
883 +
            try operand(v, start);
884 +
            try operand(v, end);
885 +
            let from = try sliceSlot(v, try accessible(v, src), e);
886 +
            try sliceFrom(v, d, from.own, from.mutable);
887 +
        },
888 +
        case il::Instr::LoadPtr { dst, src, offset, nullable } => {
889 +
            let p = try accessible(v, src);
890 +
            let o = try extent(v, p, offset as i64, 0);
891 +
            let slot = layout::slotAt(&v.ctx.table, p.layout, o) else {
892 +
                throw fail(v, Rule::Slot);
893 +
            };
894 +
            match slot {
895 +
                case il::SlotKind::Ptr(t) => try define(v, dst, RegState::Ptr(PtrState {
896 +
                    layout: t.layout, offset: 0, own: t.own, mutable: t.mutable, nullable,
897 +
                    local: false,
898 +
                })),
899 +
                case il::SlotKind::Fn(sig) => try define(v, dst, RegState::Fn(FnState {
900 +
                    sig: SigRef::Table(sig), nullable,
901 +
                })),
902 +
                else => throw fail(v, Rule::Slot),
903 +
            }
904 +
        },
905 +
        case il::Instr::StorePtr { src, dst, offset } => {
906 +
            try checkStorePtr(v, src, dst, offset);
907 +
        },
908 +
        case il::Instr::BinOp { dst, a, b, .. } => {
909 +
            try operand(v, a);
910 +
            try operand(v, b);
911 +
            try define(v, dst, RegState::Data);
912 +
        },
913 +
        case il::Instr::UnOp { dst, a, .. } => {
914 +
            try operand(v, a);
915 +
            try define(v, dst, RegState::Data);
916 +
        },
917 +
        case il::Instr::Zext { dst, val, .. } => {
918 +
            try operand(v, val);
919 +
            try define(v, dst, RegState::Data);
920 +
        },
921 +
        case il::Instr::Sext { dst, val, .. } => {
922 +
            try operand(v, val);
923 +
            try define(v, dst, RegState::Data);
924 +
        },
925 +
        case il::Instr::Call { retTy, dst, func: callee, args } => {
926 +
            try checkCall(v, retTy, dst, callee, args);
927 +
        },
928 +
        case il::Instr::Ret { val } => {
929 +
            if let x = val {
930 +
                try assign(v, x, v.func.returnType);
931 +
            } else if not (v.func.returnType == il::ValType::Void) {
932 +
                throw fail(v, Rule::Return);
933 +
            }
934 +
        },
935 +
        case il::Instr::Jmp { target, args } => {
936 +
            try checkEdge(v, target, args, nil);
937 +
        },
938 +
        case il::Instr::Br { op, typ, a, b, thenTarget, thenArgs, elseTarget, elseArgs } => {
939 +
            try operand(v, a);
940 +
            try operand(v, b);
941 +
            let mut tested: ?il::Reg = nil;
942 +
            if typ == il::Type::W64 and (op == il::CmpOp::Eq or op == il::CmpOp::Ne) {
943 +
                if isZero(a) {
944 +
                    if let case il::Val::Reg(r) = b {
945 +
                        set tested = r;
946 +
                    }
947 +
                } else if isZero(b) {
948 +
                    if let case il::Val::Reg(r) = a {
949 +
                        set tested = r;
950 +
                    }
951 +
                }
952 +
            }
953 +
            let mut thenNonNull: ?il::Reg = nil;
954 +
            let mut elseNonNull: ?il::Reg = nil;
955 +
            if op == il::CmpOp::Ne {
956 +
                set thenNonNull = tested;
957 +
            } else if op == il::CmpOp::Eq {
958 +
                set elseNonNull = tested;
959 +
            }
960 +
            try checkEdge(v, thenTarget, thenArgs, thenNonNull);
961 +
            try checkEdge(v, elseTarget, elseArgs, elseNonNull);
962 +
        },
963 +
        case il::Instr::Switch { val, defaultTarget, defaultArgs, cases } => {
964 +
            try operand(v, val);
965 +
            try checkEdge(v, defaultTarget, defaultArgs, nil);
966 +
            for branch in il::switchCases(v.func, cases) {
967 +
                try checkEdge(v, branch.target, branch.args, nil);
968 +
            }
969 +
        },
970 +
        case il::Instr::Ecall { dst, num, a0, a1, a2, a3, buf } => {
971 +
            try operand(v, num);
972 +
            try operand(v, a0);
973 +
            try operand(v, a1);
974 +
            try operand(v, a2);
975 +
            try operand(v, a3);
976 +
            // The kernel writes the buffer, so it is plain memory of the caller.
977 +
            if let b = buf {
978 +
                try writePlain(v, b.ptr, 0, b.size as u64);
979 +
            }
980 +
            try define(v, dst, RegState::Data);
981 +
        },
982 +
        case il::Instr::PageSlice { err, slot, handle, write, layout: e } => {
983 +
            try operand(v, handle);
984 +
            let to = try sliceSlot(v, try writable(v, slot), e);
985 +
            // Page memory is shared and reachable by the kernel, so only plain elements live
986 +
            // in it, and the slice must own it with the rights of the access.
987 +
            if not to.own {
988 +
                throw fail(v, Rule::Class);
989 +
            }
990 +
            if to.mutable <> write {
991 +
                throw fail(v, Rule::Mutability);
992 +
            }
993 +
            if not layout::isPlain(&v.ctx.table, e) or layout::size(&v.ctx.table, e) == 0 {
994 +
                throw fail(v, Rule::View);
995 +
            }
996 +
            try define(v, err, RegState::Data);
997 +
        },
998 +
        case il::Instr::DeviceRead { dst, handle, offset, .. } => {
999 +
            try operand(v, handle);
1000 +
            try operand(v, offset);
1001 +
            try define(v, dst, RegState::Data);
1002 +
        },
1003 +
        case il::Instr::DeviceWrite { handle, offset, value, .. } => {
1004 +
            try operand(v, handle);
1005 +
            try operand(v, offset);
1006 +
            try operand(v, value);
1007 +
        },
1008 +
        case il::Instr::Unreachable, il::Instr::Ebreak, il::Instr::MemoryFence => {},
1009 +
    }
1010 +
}
1011 +
1012 +
////////////////
1013 +
// Functions  //
1014 +
////////////////
1015 +
1016 +
/// Check one function body. Blocks are checked in reverse postorder, so a definition that
1017 +
/// dominates a use is checked before it. Blocks that cannot be reached follow.
1018 +
fn checkFn(v: &mut Verifier) throws (Error) {
1019 +
    let func = v.func;
1020 +
    flow::compute(&mut v.flow, func);
1021 +
    set v.block = 0;
1022 +
    set v.instr = 0;
1023 +
    for param in func.params {
1024 +
        try define(v, param.value, declared(param.type));
1025 +
    }
1026 +
    for b in 0..func.blocks.len {
1027 +
        set v.block = b;
1028 +
        for param in func.blocks[b].params {
1029 +
            try define(v, param.value, declared(param.type));
1030 +
        }
1031 +
    }
1032 +
    for n in 0..func.blocks.len {
1033 +
        let b = v.flow.order[n];
1034 +
        set v.block = b;
1035 +
        let block = func.blocks[b];
1036 +
        for i in 0..block.instrs.len {
1037 +
            set v.instr = i;
1038 +
            try checkInstr(v, block.instrs[i]);
1039 +
        }
1040 +
    }
1041 +
}
1042 +
1043 +
//////////////////
1044 +
// Entry points //
1045 +
//////////////////
1046 +
1047 +
/// Create an empty name dictionary for `count` names.
1048 +
fn newDict(count: u32, a: &mut alloc::Arena) -> dict::Dict throws (Error) {
1049 +
    if count > SYMBOLS_MAX {
1050 +
        throw Error { rule: Rule::Limit, place: Place::Package };
1051 +
    }
1052 +
    let mut size = DICT_MINIMUM;
1053 +
    while size < count * 2 {
1054 +
        set size *= 2;
1055 +
    }
1056 +
    let mut entries: *mut [dict::Entry] = &mut [];
1057 +
    try entries.resize(size, dict::Entry { key: &[], value: 0 }, a) catch {
1058 +
        throw STORAGE;
1059 +
    };
1060 +
    return dict::fresh(entries);
1061 +
}
1062 +
1063 +
/// Check the tables of a program and index its symbols.
1064 +
fn prepare(program: &il::Program, config: Config, a: &mut alloc::Arena) -> Context throws (Error) {
1065 +
    let table = try layout::build(program.layouts, config, a);
1066 +
    let mut fnNames = try newDict(program.fns.len, a);
1067 +
    for i in 0..program.fns.len {
1068 +
        let name = program.fns[i].name;
1069 +
        if name.len == 0 or dict::get(&fnNames, name) <> nil {
1070 +
            throw failFn(i, Rule::Symbol);
1071 +
        }
1072 +
        try dict::insert(&mut fnNames, name, i as i32) catch {
1073 +
            throw STORAGE;
1074 +
        };
1075 +
    }
1076 +
    let mut dataNames = try newDict(program.data.len, a);
1077 +
    for i in 0..program.data.len {
1078 +
        let name = program.data[i].name;
1079 +
        let at = Place::Data(i);
1080 +
        if name.len == 0 or dict::get(&dataNames, name) <> nil or dict::get(&fnNames, name) <> nil {
1081 +
            throw Error { rule: Rule::Symbol, place: at };
1082 +
        }
1083 +
        try dict::insert(&mut dataNames, name, i as i32) catch {
1084 +
            throw STORAGE;
1085 +
        };
1086 +
    }
1087 +
    let c = Context { prog: *program, config, table, fnNames, dataNames };
1088 +
    try checkSignatures(&c);
1089 +
    return c;
1090 +
}
1091 +
1092 +
/// Check data, function declarations and function bodies.
1093 +
fn finish(c: Context, a: &mut alloc::Arena) throws (Error) {
1094 +
    for i in 0..c.prog.data.len {
1095 +
        try data::check(&c, i);
1096 +
    }
1097 +
    let sizes = try measure(&c);
1098 +
    if c.prog.fns.len == 0 {
1099 +
        return;
1100 +
    }
1101 +
    let mut defs: *mut [Def] = &mut [];
1102 +
    try defs.resize(
1103 +
        sizes.registers, Def { state: RegState::Data, block: 0, owner: NO_OWNER }, a
1104 +
    ) catch {
1105 +
        throw STORAGE;
1106 +
    };
1107 +
    let tables = try flow::new(sizes.blocks, sizes.edges, a);
1108 +
    let first = c.prog.fns[0];
1109 +
    let mut v = Verifier {
1110 +
        ctx: c, flow: tables, defs, func: first, fnIndex: 0, block: 0, instr: 0,
1111 +
    };
1112 +
    for fi in 0..v.ctx.prog.fns.len {
1113 +
        set v.func = v.ctx.prog.fns[fi];
1114 +
        if v.func.isExtern {
1115 +
            continue;
1116 +
        }
1117 +
        set v.fnIndex = fi;
1118 +
        try checkFn(&mut v);
1119 +
    }
1120 +
}
1121 +
1122 +
/// Verify the data, layouts and functions of a program. The scratch arena holds the
1123 +
/// working tables, and is not reclaimed.
1124 +
export fn verifyProgram(program: &il::Program, config: Config, scratch: &mut alloc::Arena)
1125 +
    throws (Error)
1126 +
{
1127 +
    let c = try prepare(program, config, scratch);
1128 +
    try finish(c, scratch);
1129 +
}
1130 +
1131 +
/// Whether a type is data or void.
1132 +
fn isData(t: il::ValType) -> bool {
1133 +
    match t {
1134 +
        case il::ValType::Void, il::ValType::Data(_) => return true,
1135 +
        else => return false,
1136 +
    }
1137 +
}
1138 +
1139 +
/// Check the rules of a loadable package that [`verifyProgram`] does not cover.
1140 +
/// A package stands alone, so it has no dependencies and no extern functions. Its entry
1141 +
/// takes no parameter or one pointer to the plain Env record.
1142 +
fn checkPackage(package: &binary::Package, c: &Context) throws (Error) {
1143 +
    let bad = Error { rule: Rule::Package, place: Place::Package };
1144 +
    if package.dependencies.len > 0 {
1145 +
        throw bad;
1146 +
    }
1147 +
    for i in 0..package.program.fns.len {
1148 +
        if package.program.fns[i].isExtern {
1149 +
            throw failFn(i, Rule::Package);
1150 +
        }
1151 +
    }
1152 +
    if let name = package.entry {
1153 +
        let index = dict::get(&c.fnNames, name) else {
1154 +
            throw bad;
1155 +
        };
1156 +
        let func = package.program.fns[index as u32];
1157 +
        if func.params.len > 1 {
1158 +
            throw failFn(index as u32, Rule::Package);
1159 +
        }
1160 +
        for param in func.params {
1161 +
            let case il::ValType::Ptr(env) = param.type else {
1162 +
                throw failFn(index as u32, Rule::Package);
1163 +
            };
1164 +
            if not env.own or env.mutable or env.nullable or not layout::isPlain(&c.table,
1165 +
                env.layout)
1166 +
                or layout::size(&c.table, env.layout) > c.config.envSize as u64 {
1167 +
                throw failFn(index as u32, Rule::Package);
1168 +
            }
1169 +
        }
1170 +
    }
1171 +
    for item in package.exports {
1172 +
        match item.kind {
1173 +
            case binary::ExportKind::Function => {
1174 +
                if dict::get(&c.fnNames, item.name) == nil {
1175 +
                    throw bad;
1176 +
                }
1177 +
            },
1178 +
            case binary::ExportKind::Data => {
1179 +
                if dict::get(&c.dataNames, item.name) == nil {
1180 +
                    throw bad;
1181 +
                }
1182 +
            },
1183 +
        }
1184 +
    }
1185 +
}
1186 +
1187 +
/// Number of arguments that the kernel passes to a new context, in registers a0 and a1.
1188 +
/// The kernel defines no other argument, and a parameter past the argument registers would
1189 +
/// be read from above the fresh stack.
1190 +
constant START_ARGS: u32 = 2;
1191 +
1192 +
/// Whether a context may start at the exported function `name`: it is the entry, which
1193 +
/// receives the Env pointer, or takes at most `START_ARGS` data arguments and returns data,
1194 +
/// so that a context starts with plain arguments and no forged pointer.
1195 +
fn startable(package: &binary::Package, c: &Context, name: *[u8]) -> bool {
1196 +
    if let entry = package.entry {
1197 +
        if mem::eq(entry, name) {
1198 +
            return true;
1199 +
        }
1200 +
    }
1201 +
    let index = dict::get(&c.fnNames, name) else {
1202 +
        return false;
1203 +
    };
1204 +
    let func = package.program.fns[index as u32];
1205 +
    if func.params.len > START_ARGS or not isData(func.returnType) {
1206 +
        return false;
1207 +
    }
1208 +
    for param in func.params {
1209 +
        if not isData(param.type) {
1210 +
            return false;
1211 +
        }
1212 +
    }
1213 +
    return true;
1214 +
}
1215 +
1216 +
/// Narrow the exports of the package to its data and its startable functions, allocated
1217 +
/// from `keep`. A package that passes [`checkPackage`] has no dependents, so the other
1218 +
/// exports serve only to share code between its modules.
1219 +
fn narrowExports(package: &mut binary::Package, c: &Context, keep: &mut alloc::Arena)
1220 +
    throws (Error)
1221 +
{
1222 +
    let mut kept: *mut [binary::Export] = &mut [];
1223 +
    try kept.reserve(package.exports.len, keep) catch {
1224 +
        throw STORAGE;
1225 +
    };
1226 +
    for item in package.exports {
1227 +
        if item.kind == binary::ExportKind::Function and not startable(package, c, item.name) {
1228 +
            continue;
1229 +
        }
1230 +
        try kept.append(item, keep) catch {
1231 +
            throw STORAGE;
1232 +
        };
1233 +
    }
1234 +
    set package.exports = &kept[..];
1235 +
}
1236 +
1237 +
/// Verify a package that the kernel loads: the rules of [`verifyProgram`] and those of a
1238 +
/// self-contained package with a safe entry. On success, the exports of the package are
1239 +
/// narrowed to the startable ones, in storage allocated from `keep`, which must outlive
1240 +
/// the package. Other exported functions stay callable within the package.
1241 +
export fn verifyPackage(
1242 +
    package: &mut binary::Package, config: Config, scratch: &mut alloc::Arena,
1243 +
        keep: &mut alloc::Arena
1244 +
) throws (Error) {
1245 +
    let c = try prepare(&package.program, config, scratch);
1246 +
    try checkPackage(package, &c);
1247 +
    try narrowExports(package, &c, keep);
1248 +
    try finish(c, scratch);
1249 +
}
lib/std/lang/il/verify/data.rad added +184 -0
1 +
//! Data initializer checks of the RIL verifier.
2 +
//!
3 +
//! Static memory starts as the initializer says, and every byte that the initializer
4 +
//! leaves out or marks undefined is zero. Pointer and function slots may start as zero
5 +
//! or hold the address of a symbol that fits the slot. Bytes outside slots are free.
6 +
7 +
use std::collections::dict;
8 +
use std::lang::il;
9 +
use std::lang::il::verify;
10 +
use std::lang::il::verify::layout;
11 +
use std::mem;
12 +
13 +
/// Offset of the length within a slice slot.
14 +
constant SLICE_LEN: u64 = 8;
15 +
16 +
/// The pointer of the last slice slot whose pointer holds a symbol.
17 +
record Pending: Copy {
18 +
    /// Byte offset of the slice slot.
19 +
    start: u64,
20 +
    /// Index of the data symbol that the slice points to.
21 +
    target: u32,
22 +
}
23 +
24 +
/// Build the error for a rule violation in data `index`.
25 +
fn fail(index: u32, rule: verify::Rule) -> verify::Error {
26 +
    return verify::Error { rule, place: verify::Place::Data(index) };
27 +
}
28 +
29 +
/// Width in bytes of one repetition of an item.
30 +
fn width(item: il::DataItem) -> u64 {
31 +
    match item {
32 +
        case il::DataItem::Val { typ, .. } => return il::typeSize(typ) as u64,
33 +
        case il::DataItem::Sym(_), il::DataItem::Fn(_) => return layout::WORD,
34 +
        case il::DataItem::Str(text) => return text.len as u64,
35 +
        case il::DataItem::Undef => return 1,
36 +
    }
37 +
}
38 +
39 +
/// Whether an item is zero. Undefined bytes are zero in the image.
40 +
fn isZero(item: il::DataItem) -> bool {
41 +
    match item {
42 +
        case il::DataItem::Val { val, .. } => return val == 0,
43 +
        case il::DataItem::Undef => return true,
44 +
        else => return false,
45 +
    }
46 +
}
47 +
48 +
/// Check one repetition of an item that starts at `pos` and may touch a slot. `symbol` is
49 +
/// the index of the data definition or function that a symbol item names.
50 +
fn atom(
51 +
    c: &verify::Context,
52 +
    index: u32,
53 +
    pos: u64,
54 +
    item: il::DataItem,
55 +
    symbol: u32,
56 +
    pending: &mut ?Pending
57 +
) throws (verify::Error) {
58 +
    let t = &c.table;
59 +
    let layoutIndex = c.prog.data[index].layout;
60 +
    let end = pos + width(item);
61 +
    let leaf = layout::leafAround(t, layoutIndex, pos) else {
62 +
        // The item starts in plain bytes, and must not run into a slot.
63 +
        if not layout::plain(t, layoutIndex, pos, end) {
64 +
            throw fail(index, verify::Rule::Data);
65 +
        }
66 +
        return;
67 +
    };
68 +
    if end > leaf.start + layout::slotWidth(t, leaf.kind) {
69 +
        throw fail(index, verify::Rule::Data);
70 +
    }
71 +
    if isZero(item) {
72 +
        return;
73 +
    }
74 +
    match leaf.kind {
75 +
        case il::SlotKind::Ptr(p) => {
76 +
            let case il::DataItem::Sym(_) = item else {
77 +
                throw fail(index, verify::Rule::Data);
78 +
            };
79 +
            let data = c.prog.data[symbol];
80 +
            if pos <> leaf.start or (p.mutable and data.readOnly)
81 +
                or not layout::view(t, data.layout, 0, p.layout) {
82 +
                throw fail(index, verify::Rule::Data);
83 +
            }
84 +
        },
85 +
        case il::SlotKind::Fn(sig) => {
86 +
            let case il::DataItem::Fn(_) = item else {
87 +
                throw fail(index, verify::Rule::Data);
88 +
            };
89 +
            if pos <> leaf.start or not verify::sigEq(c, verify::SigRef::Table(sig),
90 +
                verify::SigRef::Func(symbol)) {
91 +
                throw fail(index, verify::Rule::Data);
92 +
            }
93 +
        },
94 +
        case il::SlotKind::Slice(p) => {
95 +
            let offset = pos - leaf.start;
96 +
            if offset >= layout::SLICE_PROTECTED {
97 +
                return;
98 +
            }
99 +
            if offset == 0 {
100 +
                // The pointer of a slice, which the length that follows must fit.
101 +
                let case il::DataItem::Sym(_) = item else {
102 +
                    throw fail(index, verify::Rule::Data);
103 +
                };
104 +
                if p.mutable and c.prog.data[symbol].readOnly {
105 +
                    throw fail(index, verify::Rule::Data);
106 +
                }
107 +
                set *pending = Pending { start: leaf.start, target: symbol };
108 +
                return;
109 +
            }
110 +
            let case il::DataItem::Val { typ: il::Type::W32, val } = item else {
111 +
                throw fail(index, verify::Rule::Data);
112 +
            };
113 +
            if offset <> SLICE_LEN {
114 +
                throw fail(index, verify::Rule::Data);
115 +
            }
116 +
            // A length of zero needs no pointer.
117 +
            let len = val as u64 & mem::U32_MAX as u64;
118 +
            if len == 0 {
119 +
                return;
120 +
            }
121 +
            let live = *pending else {
122 +
                throw fail(index, verify::Rule::Data);
123 +
            };
124 +
            if live.start <> leaf.start {
125 +
                throw fail(index, verify::Rule::Data);
126 +
            }
127 +
            let data = c.prog.data[live.target];
128 +
            if not layout::arrayView(t, data.layout, 0, p.layout, len as u32) {
129 +
                throw fail(index, verify::Rule::Data);
130 +
            }
131 +
        },
132 +
        else => panic "atom: leaf slot is a nested object",
133 +
    }
134 +
}
135 +
136 +
/// Check the initializer of data `index` against its layout.
137 +
export fn check(c: &verify::Context, index: u32) throws (verify::Error) {
138 +
    let t = &c.table;
139 +
    let data = c.prog.data[index];
140 +
    let l = c.prog.layouts[data.layout];
141 +
    if data.size <> l.size or data.alignment <> l.alignment {
142 +
        throw fail(index, verify::Rule::Data);
143 +
    }
144 +
    if t.infos[data.layout].refs or (not data.readOnly and t.infos[data.layout].slices) {
145 +
        throw fail(index, verify::Rule::Data);
146 +
    }
147 +
    let mut pos: u64 = 0;
148 +
    let mut pending: ?Pending = nil;
149 +
    for value in data.values {
150 +
        // The index of the symbol that the item names. A function must have a body.
151 +
        let mut symbol: u32 = 0;
152 +
        match value.item {
153 +
            case il::DataItem::Sym(name) => {
154 +
                let target = dict::get(&c.dataNames, name) else {
155 +
                    throw fail(index, verify::Rule::Symbol);
156 +
                };
157 +
                set symbol = target as u32;
158 +
            },
159 +
            case il::DataItem::Fn(name) => {
160 +
                let target = dict::get(&c.fnNames, name) else {
161 +
                    throw fail(index, verify::Rule::Symbol);
162 +
                };
163 +
                if c.prog.fns[target as u32].isExtern {
164 +
                    throw fail(index, verify::Rule::Symbol);
165 +
                }
166 +
                set symbol = target as u32;
167 +
            },
168 +
            else => {},
169 +
        }
170 +
        let w = width(value.item);
171 +
        let total = w * value.count as u64;
172 +
        if pos + total > data.size as u64 {
173 +
            throw fail(index, verify::Rule::Data);
174 +
        }
175 +
        if w == 0 or layout::plain(t, data.layout, pos, pos + total) {
176 +
            set pos += total;
177 +
            continue;
178 +
        }
179 +
        for _ in 0..value.count {
180 +
            try atom(c, index, pos, value.item, symbol, &mut pending);
181 +
            set pos += w;
182 +
        }
183 +
    }
184 +
}
lib/std/lang/il/verify/flow.rad added +203 -0
1 +
//! Control flow analysis of the RIL verifier: reverse postorder, immediate dominators
2 +
//! and constant-time dominance queries for the blocks of one function.
3 +
//!
4 +
//! Dominators come from the algorithm of Cooper, Harvey and Kennedy. Dominance queries
5 +
//! use the interval numbering of the dominator tree: a block dominates the blocks whose
6 +
//! preorder number falls inside its subtree. Blocks that the entry block cannot reach have
7 +
//! no number, and dominate only themselves.
8 +
9 +
use std::lang::alloc;
10 +
use std::lang::il;
11 +
use std::lang::il::verify;
12 +
13 +
/// Number of a block that the entry block cannot reach.
14 +
export constant UNREACHABLE: u32 = 0xffffffff;
15 +
/// Mark of a block that the depth-first search has entered.
16 +
constant VISITED: u32 = 0xfffffffe;
17 +
/// Immediate dominator of a block that has none yet.
18 +
constant UNDEFINED: u32 = 0xffffffff;
19 +
20 +
/// Scratch tables of the analysis. The tables are sized for the largest function, and
21 +
/// [`compute`] fills the part that the current function uses.
22 +
export record Flow {
23 +
    /// Blocks in reverse postorder, followed by the unreachable blocks in index order.
24 +
    order: *mut [u32],
25 +
    /// Reverse postorder number of each block, or [`UNREACHABLE`].
26 +
    number: *mut [u32],
27 +
    /// Reverse postorder number of the immediate dominator, by reverse postorder number.
28 +
    idom: *mut [u32],
29 +
    /// Size of the dominator subtree, by reverse postorder number.
30 +
    size: *mut [u32],
31 +
    /// Preorder number in the dominator tree, by reverse postorder number.
32 +
    pre: *mut [u32],
33 +
    /// Search stack, and then the next free preorder number of each subtree.
34 +
    stack: *mut [u32],
35 +
    /// Index of the next successor to follow in the search, by block.
36 +
    cursor: *mut [u32],
37 +
    /// Start of the predecessor list of each block, by reverse postorder number.
38 +
    predStart: *mut [u32],
39 +
    /// Reverse postorder numbers of the predecessors of the blocks that are reachable.
40 +
    preds: *mut [u32],
41 +
}
42 +
43 +
/// Allocate a table of `n` entries.
44 +
fn table(n: u32, a: &mut alloc::Arena) -> *mut [u32] throws (verify::Error) {
45 +
    let mut t: *mut [u32] = &mut [];
46 +
    try t.resize(n, 0, a) catch {
47 +
        throw verify::STORAGE;
48 +
    };
49 +
    return t;
50 +
}
51 +
52 +
/// Allocate tables for functions of up to `blocks` blocks and `edges` control flow edges.
53 +
export fn new(blocks: u32, edges: u32, a: &mut alloc::Arena) -> Flow throws (verify::Error) {
54 +
    return Flow {
55 +
        order: try table(blocks, a), number: try table(blocks, a), idom: try table(blocks, a),
56 +
        size: try table(blocks, a), pre: try table(blocks, a), stack: try table(blocks, a),
57 +
        cursor: try table(blocks, a), predStart: try table(blocks + 1, a),
58 +
        preds: try table(edges, a),
59 +
    };
60 +
}
61 +
62 +
/// Analyze `func`, whose blocks all end with a terminator that targets a block of `func`.
63 +
export fn compute(f: &mut Flow, func: *il::Fn) {
64 +
    let n = func.blocks.len;
65 +
    for b in 0..n {
66 +
        set f.number[b] = UNREACHABLE;
67 +
        set f.cursor[b] = 0;
68 +
    }
69 +
    // Depth-first search from the entry block. Blocks leave the stack in postorder.
70 +
    let mut depth: u32 = 1;
71 +
    let mut reached: u32 = 0;
72 +
    set f.stack[0] = 0;
73 +
    set f.number[0] = VISITED;
74 +
    while depth > 0 {
75 +
        let b = f.stack[depth - 1];
76 +
        let k = f.cursor[b];
77 +
        if k < il::successorCount(func, b) {
78 +
            set f.cursor[b] = k + 1;
79 +
            let target = il::successor(func, b, k);
80 +
            if f.number[target] == UNREACHABLE {
81 +
                set f.number[target] = VISITED;
82 +
                set f.stack[depth] = target;
83 +
                set depth += 1;
84 +
            }
85 +
        } else {
86 +
            set f.order[reached] = b;
87 +
            set reached += 1;
88 +
            set depth -= 1;
89 +
        }
90 +
    }
91 +
    for i in 0..reached / 2 {
92 +
        let swap = f.order[i];
93 +
        set f.order[i] = f.order[reached - 1 - i];
94 +
        set f.order[reached - 1 - i] = swap;
95 +
    }
96 +
    for i in 0..reached {
97 +
        set f.number[f.order[i]] = i;
98 +
    }
99 +
    let mut next = reached;
100 +
    for b in 0..n {
101 +
        if f.number[b] == UNREACHABLE {
102 +
            set f.order[next] = b;
103 +
            set next += 1;
104 +
        }
105 +
    }
106 +
    predecessors(f, func, reached);
107 +
    dominators(f, reached);
108 +
}
109 +
110 +
/// Build the predecessor lists of the reachable blocks, by reverse postorder number.
111 +
fn predecessors(f: &mut Flow, func: *il::Fn, reached: u32) {
112 +
    for i in 0..reached + 1 {
113 +
        set f.predStart[i] = 0;
114 +
    }
115 +
    for i in 0..reached {
116 +
        let b = f.order[i];
117 +
        for k in 0..il::successorCount(func, b) {
118 +
            set f.predStart[f.number[il::successor(func, b, k)] + 1] += 1;
119 +
        }
120 +
    }
121 +
    for i in 0..reached {
122 +
        set f.predStart[i + 1] += f.predStart[i];
123 +
        set f.cursor[i] = 0;
124 +
    }
125 +
    for i in 0..reached {
126 +
        let b = f.order[i];
127 +
        for k in 0..il::successorCount(func, b) {
128 +
            let target = f.number[il::successor(func, b, k)];
129 +
            set f.preds[f.predStart[target] + f.cursor[target]] = i;
130 +
            set f.cursor[target] += 1;
131 +
        }
132 +
    }
133 +
}
134 +
135 +
/// Find the nearest common dominator of two blocks with the dominators found so far.
136 +
fn intersect(idom: &[u32], a: u32, b: u32) -> u32 {
137 +
    let mut x = a;
138 +
    let mut y = b;
139 +
    while x <> y {
140 +
        while x > y {
141 +
            set x = idom[x];
142 +
        }
143 +
        while y > x {
144 +
            set y = idom[y];
145 +
        }
146 +
    }
147 +
    return x;
148 +
}
149 +
150 +
/// Compute the immediate dominators of the `reached` reachable blocks, and number the
151 +
/// dominator tree.
152 +
fn dominators(f: &mut Flow, reached: u32) {
153 +
    for i in 0..reached {
154 +
        set f.idom[i] = UNDEFINED;
155 +
    }
156 +
    set f.idom[0] = 0;
157 +
    let mut changed = true;
158 +
    while changed {
159 +
        set changed = false;
160 +
        for i in 1..reached {
161 +
            let mut best = UNDEFINED;
162 +
            for j in f.predStart[i]..f.predStart[i + 1] {
163 +
                let p = f.preds[j];
164 +
                if f.idom[p] == UNDEFINED {
165 +
                    continue;
166 +
                }
167 +
                set best = p if best == UNDEFINED else intersect(&f.idom[..], best, p);
168 +
            }
169 +
            if f.idom[i] <> best {
170 +
                set f.idom[i] = best;
171 +
                set changed = true;
172 +
            }
173 +
        }
174 +
    }
175 +
    // A dominator comes before the blocks it dominates, so subtree sizes accumulate
176 +
    // from the last block back, and preorder numbers are handed out from the first.
177 +
    for i in 0..reached {
178 +
        set f.size[i] = 1;
179 +
    }
180 +
    let mut last = reached;
181 +
    while last > 1 {
182 +
        set last -= 1;
183 +
        set f.size[f.idom[last]] += f.size[last];
184 +
    }
185 +
    set f.pre[0] = 0;
186 +
    set f.stack[0] = 1;
187 +
    for i in 1..reached {
188 +
        let parent = f.idom[i];
189 +
        set f.pre[i] = f.stack[parent];
190 +
        set f.stack[parent] += f.size[i];
191 +
        set f.stack[i] = f.pre[i] + 1;
192 +
    }
193 +
}
194 +
195 +
/// Whether block `a` dominates block `b`.
196 +
export fn dominates(f: &Flow, a: u32, b: u32) -> bool {
197 +
    let x = f.number[a];
198 +
    let y = f.number[b];
199 +
    if x == UNREACHABLE or y == UNREACHABLE {
200 +
        return a == b;
201 +
    }
202 +
    return f.pre[x] <= f.pre[y] and f.pre[y] < f.pre[x] + f.size[x];
203 +
}
lib/std/lang/il/verify/layout.rad added +385 -0
1 +
//! Layout table checks and queries of the RIL verifier.
2 +
//!
3 +
//! A layout lists the slots of an object, the byte ranges that hold pointers,
4 +
//! slices and function values. All other bytes are plain data. The decoder
5 +
//! establishes that slots are sorted, aligned, disjoint and inside the size, and
6 +
//! that nested layouts have lower indices than the layouts that contain them.
7 +
//! The queries here rely on that, and on table indices that are in range.
8 +
//!
9 +
//! Descent through nested layouts is bounded by [`verify::Config::layoutDepth`],
10 +
//! which [`build`] checks, so no query recurses deeper than that.
11 +
12 +
use std::lang::alloc;
13 +
use std::lang::il;
14 +
use std::lang::il::verify;
15 +
16 +
/// Size in bytes of a pointer or function slot.
17 +
export constant WORD: u64 = 8;
18 +
/// Size in bytes of a slice slot: pointer, length and capacity.
19 +
constant SLICE: u64 = 16;
20 +
/// Bytes of a slice slot that only the slice instructions write: pointer and length.
21 +
/// The capacity that follows is plain data.
22 +
export constant SLICE_PROTECTED: u64 = 12;
23 +
24 +
/// Facts about a layout, computed once for the whole table.
25 +
export record Info: Copy {
26 +
    /// Nesting depth of sub and array nodes. A layout without such nodes has depth zero.
27 +
    depth: u32,
28 +
    /// Offset of the first byte that a pointer, slice or function slot protects, also in
29 +
    /// nested nodes, or nil when the layout is plain data.
30 +
    first: ?u64,
31 +
    /// Whether the layout has a non-owning pointer or slice slot, also in nested nodes.
32 +
    refs: bool,
33 +
    /// Whether the layout has a slice slot, also in nested nodes.
34 +
    slices: bool,
35 +
}
36 +
37 +
/// A checked layout table.
38 +
export record Table: Copy {
39 +
    /// The layouts of the program.
40 +
    layouts: *[il::Layout],
41 +
    /// Facts about each layout, in table order.
42 +
    infos: *[Info],
43 +
}
44 +
45 +
/// A leaf slot found by a query.
46 +
export record Leaf: Copy {
47 +
    /// Byte offset of the slot from the start of the queried layout.
48 +
    start: u64,
49 +
    /// What the slot holds. Never a sub or array.
50 +
    kind: il::SlotKind,
51 +
}
52 +
53 +
/// A position inside a layout.
54 +
record At: Copy {
55 +
    /// Layout index.
56 +
    layout: u32,
57 +
    /// Byte offset from the start of the layout.
58 +
    offset: u64,
59 +
}
60 +
61 +
/// Build the error for a rule violation at layout `index`.
62 +
fn fail(index: u32, rule: verify::Rule) -> verify::Error {
63 +
    return verify::Error { rule, place: verify::Place::Layout(index) };
64 +
}
65 +
66 +
/// Add the facts of a nested layout to those of its container.
67 +
fn absorb(info: &mut Info, child: Info) {
68 +
    if child.depth + 1 > info.depth {
69 +
        set info.depth = child.depth + 1;
70 +
    }
71 +
    set info.refs = info.refs or child.refs;
72 +
    set info.slices = info.slices or child.slices;
73 +
}
74 +
75 +
/// Check the layout table against the limits of `config` and compute the facts about each
76 +
/// layout. Owning pointers and slices must not point to layouts with non-owning slots.
77 +
export fn build(layouts: *[il::Layout], config: verify::Config, a: &mut alloc::Arena)
78 +
    -> Table throws (verify::Error)
79 +
{
80 +
    let mut infos: *mut [Info] = &mut [];
81 +
    try infos.reserve(layouts.len, a) catch {
82 +
        throw verify::STORAGE;
83 +
    };
84 +
    for i in 0..layouts.len {
85 +
        let layout = layouts[i];
86 +
        if layout.size > config.layoutSize {
87 +
            throw fail(i, verify::Rule::Limit);
88 +
        }
89 +
        let mut info = Info { depth: 0, first: nil, refs: false, slices: false };
90 +
        for slot in layout.slots {
91 +
            match slot.kind {
92 +
                case il::SlotKind::Ptr(p) => {
93 +
                    set info.refs = info.refs or not p.own;
94 +
                },
95 +
                case il::SlotKind::Slice(p) => {
96 +
                    set info.slices = true;
97 +
                    set info.refs = info.refs or not p.own;
98 +
                },
99 +
                case il::SlotKind::Fn(_) => {},
100 +
                case il::SlotKind::Sub(child) => {
101 +
                    if child >= i {
102 +
                        throw fail(i, verify::Rule::Layout);
103 +
                    }
104 +
                    absorb(&mut info, infos[child]);
105 +
                },
106 +
                case il::SlotKind::Array { layout: child, count } => {
107 +
                    if child >= i {
108 +
                        throw fail(i, verify::Rule::Layout);
109 +
                    }
110 +
                    // An empty array holds nothing, but it still nests.
111 +
                    if count > 0 {
112 +
                        absorb(&mut info, infos[child]);
113 +
                    }
114 +
                },
115 +
            }
116 +
        }
117 +
        if info.depth > config.layoutDepth {
118 +
            throw fail(i, verify::Rule::Limit);
119 +
        }
120 +
        set info.first = firstOfSlots(&infos[..], &layout.slots[..]);
121 +
        try infos.append(info, a) catch {
122 +
            throw verify::STORAGE;
123 +
        };
124 +
    }
125 +
    // Pointer pointees can have any index, so their facts are known only now.
126 +
    for i in 0..layouts.len {
127 +
        for slot in layouts[i].slots {
128 +
            match slot.kind {
129 +
                case il::SlotKind::Ptr(p) => {
130 +
                    if p.own and infos[p.layout].refs {
131 +
                        throw fail(i, verify::Rule::Layout);
132 +
                    }
133 +
                },
134 +
                case il::SlotKind::Slice(p) => {
135 +
                    if p.own and infos[p.layout].refs {
136 +
                        throw fail(i, verify::Rule::Layout);
137 +
                    }
138 +
                },
139 +
                else => {},
140 +
            }
141 +
        }
142 +
    }
143 +
    return Table { layouts, infos: &infos[..] };
144 +
}
145 +
146 +
/// Size in bytes of layout `l`.
147 +
export fn size(t: &Table, l: u32) -> u64 {
148 +
    return t.layouts[l].size as u64;
149 +
}
150 +
151 +
/// Whether layout `l` is plain data, without any slot.
152 +
export fn isPlain(t: &Table, l: u32) -> bool {
153 +
    return t.infos[l].first == nil;
154 +
}
155 +
156 +
/// Number of bytes that a slot of kind `kind` covers.
157 +
export fn slotWidth(t: &Table, kind: il::SlotKind) -> u64 {
158 +
    match kind {
159 +
        case il::SlotKind::Ptr(_), il::SlotKind::Fn(_) => return WORD,
160 +
        case il::SlotKind::Slice(_) => return SLICE,
161 +
        case il::SlotKind::Sub(child) => return size(t, child),
162 +
        case il::SlotKind::Array { layout, count } => return size(t, layout) * count as u64,
163 +
    }
164 +
}
165 +
166 +
/// Index of the first slot in `slots` that ends after byte `o`. Slots are sorted and do not
167 +
/// overlap, so their ends increase.
168 +
fn firstEndingAfter(t: &Table, slots: *[il::Slot], o: u64) -> u32 {
169 +
    let mut low: u32 = 0;
170 +
    let mut high: u32 = slots.len;
171 +
    while low < high {
172 +
        let mid = low + (high - low) / 2;
173 +
        if slots[mid].offset as u64 + slotWidth(t, slots[mid].kind) > o {
174 +
            set high = mid;
175 +
        } else {
176 +
            set low = mid + 1;
177 +
        }
178 +
    }
179 +
    return low;
180 +
}
181 +
182 +
/// Find the slot of layout `l` that covers byte `o`, if any.
183 +
fn covering(t: &Table, l: u32, o: u64) -> ?il::Slot {
184 +
    let slots = t.layouts[l].slots;
185 +
    let i = firstEndingAfter(t, slots, o);
186 +
    if i < slots.len and slots[i].offset as u64 <= o {
187 +
        return slots[i];
188 +
    }
189 +
    return nil;
190 +
}
191 +
192 +
/// Step into the nested object or array element that covers `at`, if any.
193 +
fn inner(t: &Table, at: At) -> ?At {
194 +
    let slot = covering(t, at.layout, at.offset) else {
195 +
        return nil;
196 +
    };
197 +
    return enter(t, slot, at.offset);
198 +
}
199 +
200 +
/// Enter the nested object or array element of `slot` that covers offset `o` of its layout.
201 +
/// A leaf slot has no inside.
202 +
fn enter(t: &Table, slot: il::Slot, o: u64) -> ?At {
203 +
    match slot.kind {
204 +
        case il::SlotKind::Sub(child) =>
205 +
            return At { layout: child, offset: o - slot.offset as u64 },
206 +
        case il::SlotKind::Array { layout, .. } =>
207 +
            // The slot covers a byte, so the element size is not zero.
208 +
            return At { layout, offset: (o - slot.offset as u64) % size(t, layout) },
209 +
        else => return nil,
210 +
    }
211 +
}
212 +
213 +
/// Find the leaf slot that covers byte `o` of layout `l`, looking through nested objects.
214 +
export fn leafAround(t: &Table, l: u32, o: u64) -> ?Leaf {
215 +
    let mut at = At { layout: l, offset: o };
216 +
    loop {
217 +
        let slot = covering(t, at.layout, at.offset) else {
218 +
            return nil;
219 +
        };
220 +
        if let next = enter(t, slot, at.offset) {
221 +
            set at = next;
222 +
            continue;
223 +
        }
224 +
        return Leaf { start: o - at.offset + slot.offset as u64, kind: slot.kind };
225 +
    }
226 +
}
227 +
228 +
/// Find the leaf slot that starts exactly at byte `o` of layout `l`.
229 +
export fn slotAt(t: &Table, l: u32, o: u64) -> ?il::SlotKind {
230 +
    if let leaf = leafAround(t, l, o) {
231 +
        if leaf.start == o {
232 +
            return leaf.kind;
233 +
        }
234 +
    }
235 +
    return nil;
236 +
}
237 +
238 +
/// Offset of the first protected byte of a slot of kind `kind`, from the start of the slot,
239 +
/// or nil when the slot protects none. `infos` has the facts about the nested layouts.
240 +
fn protectedStart(infos: &[Info], kind: il::SlotKind) -> ?u64 {
241 +
    match kind {
242 +
        case il::SlotKind::Ptr(_), il::SlotKind::Fn(_), il::SlotKind::Slice(_) => return 0,
243 +
        case il::SlotKind::Sub(child) => return infos[child].first,
244 +
        case il::SlotKind::Array { layout, count } => {
245 +
            if count == 0 {
246 +
                return nil;
247 +
            }
248 +
            return infos[layout].first;
249 +
        },
250 +
    }
251 +
}
252 +
253 +
/// Offset of the first protected byte of a layout with the sorted `slots`, or nil when the
254 +
/// slots protect none. `infos` has the facts about the layouts that the slots nest.
255 +
fn firstOfSlots(infos: &[Info], slots: &[il::Slot]) -> ?u64 {
256 +
    for slot in slots {
257 +
        if let f = protectedStart(infos, slot.kind) {
258 +
            return slot.offset as u64 + f;
259 +
        }
260 +
    }
261 +
    return nil;
262 +
}
263 +
264 +
/// Offset of the first protected byte of `slot` at or after byte `rel` of the slot, from the
265 +
/// start of the slot, or nil when there is none. The byte `rel` must lie inside the slot.
266 +
fn protectedFrom(t: &Table, slot: il::Slot, rel: u64) -> ?u64 {
267 +
    match slot.kind {
268 +
        case il::SlotKind::Ptr(_), il::SlotKind::Fn(_) => return rel,
269 +
        case il::SlotKind::Slice(_) => {
270 +
            // The capacity of a slice is plain.
271 +
            if rel < SLICE_PROTECTED {
272 +
                return rel;
273 +
            }
274 +
            return nil;
275 +
        },
276 +
        case il::SlotKind::Sub(child) => return firstProtected(t, child, rel),
277 +
        case il::SlotKind::Array { layout, count } => {
278 +
            // The slot covers a byte, so the element size is not zero.
279 +
            let element = size(t, layout);
280 +
            let index = rel / element;
281 +
            if let f = firstProtected(t, layout, rel % element) {
282 +
                return index * element + f;
283 +
            }
284 +
            // The element has no protected byte left, so the next one decides.
285 +
            if index + 1 < count as u64 {
286 +
                if let f = t.infos[layout].first {
287 +
                    return (index + 1) * element + f;
288 +
                }
289 +
            }
290 +
            return nil;
291 +
        },
292 +
    }
293 +
}
294 +
295 +
/// Offset of the first protected byte of layout `l` at or after byte `lo`, or nil when there
296 +
/// is none. It descends one path through the nested layouts: only the slot that covers `lo`
297 +
/// is searched, and the slots after it are answered by the facts of the table.
298 +
fn firstProtected(t: &Table, l: u32, lo: u64) -> ?u64 {
299 +
    let slots = t.layouts[l].slots;
300 +
    let mut i = firstEndingAfter(t, slots, lo);
301 +
    if i < slots.len and slots[i].offset as u64 <= lo {
302 +
        let start = slots[i].offset as u64;
303 +
        if let f = protectedFrom(t, slots[i], lo - start) {
304 +
            return start + f;
305 +
        }
306 +
        set i += 1;
307 +
    }
308 +
    return firstOfSlots(&t.infos[..], &slots[i..]);
309 +
}
310 +
311 +
/// Whether bytes `lo..hi` of layout `l` hold no protected byte. The capacity of a slice is
312 +
/// plain. The cost is linear in the nesting depth of the layout.
313 +
export fn plain(t: &Table, l: u32, lo: u64, hi: u64) -> bool {
314 +
    if hi <= lo {
315 +
        return true;
316 +
    }
317 +
    let first = firstProtected(t, l, lo) else {
318 +
        return true;
319 +
    };
320 +
    return first >= hi;
321 +
}
322 +
323 +
/// Alignment in bytes of layout `l`.
324 +
export fn alignment(t: &Table, l: u32) -> u64 {
325 +
    return t.layouts[l].alignment as u64;
326 +
}
327 +
328 +
/// Whether the `width` bytes at byte `o` of layout `l` are a plain region that an object of
329 +
/// `boundary` bytes of alignment can occupy. The object of `l` is aligned to its alignment, so `o`
330 +
/// must be a multiple of `boundary`, and `l` must be at least as aligned.
331 +
export fn plainRegion(t: &Table, l: u32, o: u64, width: u64, boundary: u64) -> bool {
332 +
    return o + width <= size(t, l) and plain(t, l, o, o + width) and o % boundary == 0
333 +
        and boundary <= alignment(t, l);
334 +
}
335 +
336 +
/// Whether a pointer to layout `l` at byte `o` can be used as a pointer to layout `m`.
337 +
/// A plain `m` fits any plain region of `l` that is inside it and aligned for `m`. Any other
338 +
/// `m` must be `l` itself, or a nested object or array element that starts at `o`, which the
339 +
/// layout checks of the decoder align.
340 +
export fn view(t: &Table, l: u32, o: u64, m: u32) -> bool {
341 +
    if isPlain(t, m) {
342 +
        return plainRegion(t, l, o, size(t, m), alignment(t, m));
343 +
    }
344 +
    let mut at = At { layout: l, offset: o };
345 +
    while not (at.offset == 0 and at.layout == m) {
346 +
        let next = inner(t, at) else {
347 +
            return false;
348 +
        };
349 +
        set at = next;
350 +
    }
351 +
    return true;
352 +
}
353 +
354 +
/// Whether a pointer to layout `l` at byte `o` can be used as a pointer to `count` consecutive
355 +
/// objects of layout `e`. A plain `e` needs a plain region that is inside `l`. Any other
356 +
/// `e` needs an array node of `e` with that count, or a single object that is a view.
357 +
export fn arrayView(t: &Table, l: u32, o: u64, e: u32, count: u32) -> bool {
358 +
    let total = size(t, e) * count as u64;
359 +
    if o + total > size(t, l) {
360 +
        return false;
361 +
    }
362 +
    if isPlain(t, e) {
363 +
        return plainRegion(t, l, o, total, alignment(t, e));
364 +
    }
365 +
    if count == 1 {
366 +
        return view(t, l, o, e);
367 +
    }
368 +
    let mut at = At { layout: l, offset: o };
369 +
    loop {
370 +
        let slot = covering(t, at.layout, at.offset) else {
371 +
            return false;
372 +
        };
373 +
        if slot.offset as u64 == at.offset {
374 +
            if let case il::SlotKind::Array { layout, count: n } = slot.kind {
375 +
                if layout == e and n == count {
376 +
                    return true;
377 +
                }
378 +
            }
379 +
        }
380 +
        let next = enter(t, slot, at.offset) else {
381 +
            return false;
382 +
        };
383 +
        set at = next;
384 +
    }
385 +
}
lib/std/lang/il/verify/tests.rad added +1888 -0
1 +
//! Tests for the RIL verifier.
2 +
//!
3 +
//! A test builds a small program with [`Builder`], and checks that the verifier accepts it
4 +
//! or rejects it with a given rule. Every program starts with the layouts and signatures
5 +
//! named by the constants below.
6 +
7 +
use std::testing;
8 +
use std::lang::alloc;
9 +
use std::lang::il;
10 +
use std::lang::il::binary;
11 +
use std::lang::il::verify;
12 +
use std::lang::il::verify::layout;
13 +
14 +
///////////////
15 +
// Constants //
16 +
///////////////
17 +
18 +
/// Plain layout of one byte.
19 +
constant P1: u32 = 0;
20 +
/// Plain layout of four bytes.
21 +
constant P4: u32 = 1;
22 +
/// Plain layout of eight bytes.
23 +
constant P8: u32 = 2;
24 +
/// Plain layout of sixteen bytes.
25 +
constant P16: u32 = 3;
26 +
/// Eight bytes: a pointer that owns a writable `P4` at offset 0.
27 +
constant CELL: u32 = 4;
28 +
/// Eight bytes: a pointer that owns a read-only `P4` at offset 0.
29 +
constant CELLC: u32 = 5;
30 +
/// Eight bytes: a pointer that borrows a writable `P4` at offset 0.
31 +
constant LOCAL: u32 = 6;
32 +
/// Sixteen bytes: a slice of owned writable bytes at offset 0.
33 +
constant SLICE: u32 = 7;
34 +
/// Sixteen bytes: a slice of owned read-only bytes at offset 0.
35 +
constant SLICEC: u32 = 8;
36 +
/// Eight bytes: a function value of signature 0 at offset 0.
37 +
constant FNCELL: u32 = 9;
38 +
/// Thirty-two bytes: a `CELL` at offset 8 and a `SLICE` at offset 16.
39 +
constant PAIR: u32 = 10;
40 +
/// Twenty-four bytes: an array of three `CELL` at offset 0.
41 +
constant CELLS: u32 = 11;
42 +
/// Sixteen bytes: a slice of borrowed writable bytes at offset 0.
43 +
constant BORROW: u32 = 12;
44 +
/// Eight bytes: a function value of signature 1 at offset 0.
45 +
constant FNCELL1: u32 = 13;
46 +
/// Plain layout of three bytes.
47 +
constant P3: u32 = 14;
48 +
/// Plain layout of eight bytes with the alignment of a byte.
49 +
constant B8: u32 = 15;
50 +
51 +
/// Signature of a function from data to data.
52 +
constant SIG_DATA: u32 = 0;
53 +
/// Signature of a function without parameters or result.
54 +
constant SIG_VOID: u32 = 1;
55 +
56 +
/// Limits of the tests.
57 +
constant CONFIG: verify::Config = verify::Config {
58 +
    registers: 64, blocks: 16, layoutSize: 4096, layoutDepth: 4, params: 8, envSize: 32,
59 +
};
60 +
61 +
/// Storage for the program under test.
62 +
static BUILD: [u8; 65536] = [0; 65536];
63 +
/// Working storage of the verifier.
64 +
static SCRATCH: [u8; 65536] = [0; 65536];
65 +
/// Storage for the narrowed exports.
66 +
static KEEP: [u8; 4096] = [0; 4096];
67 +
68 +
///////////////////
69 +
// Program Build //
70 +
///////////////////
71 +
72 +
/// A program under construction. All its slices live in `arena`.
73 +
record Builder {
74 +
    /// Storage of the program.
75 +
    arena: alloc::Arena,
76 +
    /// Layout table.
77 +
    layouts: *mut [il::Layout],
78 +
    /// Signature table.
79 +
    signatures: *mut [il::Signature],
80 +
    /// Data definitions.
81 +
    data: *mut [il::Data],
82 +
    /// Functions.
83 +
    fns: *mut [*il::Fn],
84 +
    /// Argument pool shared by the functions.
85 +
    vals: *mut [il::Val],
86 +
    /// Switch case pool shared by the functions.
87 +
    cases: *mut [il::SwitchCase],
88 +
}
89 +
90 +
/// Plain data of eight bytes.
91 +
fn dataType() -> il::ValType {
92 +
    return il::ValType::Data(il::Type::W64);
93 +
}
94 +
95 +
/// Type of a pointer to a layout.
96 +
fn ptrType(layout: u32, own: bool, mutable: bool, nullable: bool) -> il::ValType {
97 +
    return il::ValType::Ptr(il::PtrType { layout, own, mutable, nullable });
98 +
}
99 +
100 +
/// A parameter in register `n`.
101 +
fn param(n: u32, type: il::ValType) -> il::Param {
102 +
    return il::Param { value: il::Reg { n }, type };
103 +
}
104 +
105 +
/// Register `n` as a value.
106 +
fn reg(n: u32) -> il::Val {
107 +
    return il::Val::Reg(il::Reg { n });
108 +
}
109 +
110 +
/// An immediate value.
111 +
fn imm(n: i64) -> il::Val {
112 +
    return il::Val::Imm(n);
113 +
}
114 +
115 +
/// A pointer slot at `offset`.
116 +
fn ptrSlot(offset: u32, layout: u32, own: bool, mutable: bool) -> il::Slot {
117 +
    return il::Slot { offset, kind: il::SlotKind::Ptr(il::PtrType {
118 +
        layout, own, mutable, nullable: true,
119 +
    }) };
120 +
}
121 +
122 +
/// A slice slot at `offset`.
123 +
fn sliceSlot(offset: u32, layout: u32, own: bool, mutable: bool) -> il::Slot {
124 +
    return il::Slot { offset, kind: il::SlotKind::Slice(il::PtrType {
125 +
        layout, own, mutable, nullable: true,
126 +
    }) };
127 +
}
128 +
129 +
/// A nested object at `offset`.
130 +
fn subSlot(offset: u32, layout: u32) -> il::Slot {
131 +
    return il::Slot { offset, kind: il::SlotKind::Sub(layout) };
132 +
}
133 +
134 +
/// Add a layout, and return its index.
135 +
fn addLayout(b: &mut Builder, size: u32, alignment: u32, slots: &[il::Slot]) -> u32 {
136 +
    let index = b.layouts.len;
137 +
    let mut copy: *mut [il::Slot] = &mut [];
138 +
    try! copy.extend(slots, &mut b.arena);
139 +
    try! b.layouts.append(il::Layout { size, alignment, slots: &copy[..] }, &mut b.arena);
140 +
    return index;
141 +
}
142 +
143 +
/// Add a signature, and return its index.
144 +
fn addSignature(b: &mut Builder, params: &[il::ValType], ret: il::ValType) -> u32 {
145 +
    let index = b.signatures.len;
146 +
    let mut copy: *mut [il::ValType] = &mut [];
147 +
    try! copy.extend(params, &mut b.arena);
148 +
    try! b.signatures.append(il::Signature { params: &copy[..], ret }, &mut b.arena);
149 +
    return index;
150 +
}
151 +
152 +
/// Add the argument values of a branch or call, and return their range.
153 +
fn args(b: &mut Builder, values: &[il::Val]) -> il::ArgRange {
154 +
    let start = b.vals.len;
155 +
    try! b.vals.extend(values, &mut b.arena);
156 +
    return il::ArgRange { start, len: values.len };
157 +
}
158 +
159 +
/// Add a switch case, and return the range that holds it.
160 +
fn addCase(b: &mut Builder, value: i64, target: u32, values: il::ArgRange) -> il::CaseRange {
161 +
    let start = b.cases.len;
162 +
    try! b.cases.append(il::SwitchCase { value, target, args: values }, &mut b.arena);
163 +
    return il::CaseRange { start, len: 1 };
164 +
}
165 +
166 +
/// Create a builder whose tables start with the layouts and signatures named above.
167 +
unsafe fn newBuilder() -> Builder {
168 +
    let mut b = Builder {
169 +
        arena: alloc::new(&mut BUILD[..]),
170 +
        layouts: &mut [], signatures: &mut [], data: &mut [], fns: &mut [], vals: &mut [],
171 +
        cases: &mut [],
172 +
    };
173 +
    addLayout(&mut b, 1, 1, &[]);
174 +
    addLayout(&mut b, 4, 4, &[]);
175 +
    addLayout(&mut b, 8, 8, &[]);
176 +
    addLayout(&mut b, 16, 8, &[]);
177 +
    addLayout(&mut b, 8, 8, &[ptrSlot(0, P4, true, true)]);
178 +
    addLayout(&mut b, 8, 8, &[ptrSlot(0, P4, true, false)]);
179 +
    addLayout(&mut b, 8, 8, &[ptrSlot(0, P4, false, true)]);
180 +
    addLayout(&mut b, 16, 8, &[sliceSlot(0, P1, true, true)]);
181 +
    addLayout(&mut b, 16, 8, &[sliceSlot(0, P1, true, false)]);
182 +
    addLayout(&mut b, 8, 8, &[il::Slot { offset: 0, kind: il::SlotKind::Fn(SIG_DATA) }]);
183 +
    addLayout(&mut b, 32, 8, &[subSlot(8, CELL), subSlot(16, SLICE)]);
184 +
    addLayout(&mut b, 24, 8, &[il::Slot { offset: 0, kind: il::SlotKind::Array {
185 +
        layout: CELL, count: 3,
186 +
    } }]);
187 +
    addLayout(&mut b, 16, 8, &[sliceSlot(0, P1, false, true)]);
188 +
    addLayout(&mut b, 8, 8, &[il::Slot { offset: 0, kind: il::SlotKind::Fn(SIG_VOID) }]);
189 +
    addLayout(&mut b, 3, 1, &[]);
190 +
    addLayout(&mut b, 8, 1, &[]);
191 +
    addSignature(&mut b, &[dataType()], dataType());
192 +
    addSignature(&mut b, &[], il::ValType::Void);
193 +
    return b;
194 +
}
195 +
196 +
/// A block with the given parameters and instructions.
197 +
fn block(b: &mut Builder, params: &[il::Param], instrs: &[il::Instr]) -> il::Block {
198 +
    let mut ownParams: *mut [il::Param] = &mut [];
199 +
    try! ownParams.extend(params, &mut b.arena);
200 +
    let mut ownInstrs: *mut [il::Instr] = &mut [];
201 +
    try! ownInstrs.extend(instrs, &mut b.arena);
202 +
    return il::Block {
203 +
        label: il::BlockLabel { base: "b", suffix: nil }, params: &ownParams[..],
204 +
        instrs: &ownInstrs[..], locs: &[], preds: &[], loopDepth: 0,
205 +
    };
206 +
}
207 +
208 +
/// Add a function of several blocks, and return its index.
209 +
fn addBlocks(
210 +
    b: &mut Builder, name: *[u8], params: &[il::Param], ret: il::ValType, blocks: &[il::Block]
211 +
) -> u32 {
212 +
    let index = b.fns.len;
213 +
    let mut copyParams: *mut [il::Param] = &mut [];
214 +
    try! copyParams.extend(params, &mut b.arena);
215 +
    let mut copyBlocks: *mut [il::Block] = &mut [];
216 +
    try! copyBlocks.extend(blocks, &mut b.arena);
217 +
    let mut pool: *mut [il::Val] = &mut [];
218 +
    try! pool.extend(&b.vals[..], &mut b.arena);
219 +
    let mut caseList: *mut [il::SwitchCase] = &mut [];
220 +
    try! caseList.extend(&b.cases[..], &mut b.arena);
221 +
    let mut copy: *mut [il::Fn] = &mut [];
222 +
    try! copy.append(il::Fn {
223 +
        name, params: &copyParams[..], returnType: ret, isExtern: false, isLeaf: false,
224 +
        blocks: &copyBlocks[..], vals: &pool[..], cases: &caseList[..],
225 +
    }, &mut b.arena);
226 +
    try! b.fns.append(&copy[0], &mut b.arena);
227 +
    return index;
228 +
}
229 +
230 +
/// Add a function of one block, and return its index.
231 +
fn addFn(
232 +
    b: &mut Builder, name: *[u8], params: &[il::Param], ret: il::ValType, instrs: &[il::Instr]
233 +
) -> u32 {
234 +
    let one = block(b, &[], instrs);
235 +
    return addBlocks(b, name, params, ret, &[one]);
236 +
}
237 +
238 +
/// Add an extern function, and return its index.
239 +
fn addExtern(b: &mut Builder, name: *[u8], params: &[il::Param], ret: il::ValType) -> u32 {
240 +
    let index = b.fns.len;
241 +
    let mut ownParams: *mut [il::Param] = &mut [];
242 +
    try! ownParams.extend(params, &mut b.arena);
243 +
    let mut copy: *mut [il::Fn] = &mut [];
244 +
    try! copy.append(il::Fn {
245 +
        name, params: &ownParams[..], returnType: ret, isExtern: true, isLeaf: true, blocks: &[],
246 +
        vals: &[],
247 +
        cases: &[],
248 +
    }, &mut b.arena);
249 +
    try! b.fns.append(&copy[0], &mut b.arena);
250 +
    return index;
251 +
}
252 +
253 +
/// Add a data definition of the layout, and return its index.
254 +
fn addData(b: &mut Builder, name: *[u8], layout: u32, readOnly: bool, values: &[il::DataValue])
255 +
    -> u32
256 +
{
257 +
    let index = b.data.len;
258 +
    let l = b.layouts[layout];
259 +
    let mut copy: *mut [il::DataValue] = &mut [];
260 +
    try! copy.extend(values, &mut b.arena);
261 +
    try! b.data.append(il::Data {
262 +
        name, size: l.size, alignment: l.alignment, layout, readOnly, isZeroInit: false,
263 +
        values: &copy[..],
264 +
    }, &mut b.arena);
265 +
    return index;
266 +
}
267 +
268 +
/// The program built so far, which leaves the builder empty.
269 +
fn program(b: &mut Builder) -> il::Program {
270 +
    let data = b.data.take();
271 +
    let fns = b.fns.take();
272 +
    let layouts = b.layouts.take();
273 +
    let signatures = b.signatures.take();
274 +
    return il::Program {
275 +
        data: &data[..], fns: &fns[..], layouts: &layouts[..], signatures: &signatures[..],
276 +
    };
277 +
}
278 +
279 +
/////////////////
280 +
// Instruction //
281 +
/////////////////
282 +
283 +
fn reserve(dst: u32, layout: u32) -> il::Instr {
284 +
    return il::Instr::Reserve { dst: il::Reg { n: dst }, layout };
285 +
}
286 +
287 +
fn load(dst: u32, src: u32, offset: i32) -> il::Instr {
288 +
    return il::Instr::Load {
289 +
        typ: il::Type::W32, dst: il::Reg { n: dst }, src: il::Reg { n: src }, offset,
290 +
    };
291 +
}
292 +
293 +
fn load64(dst: u32, src: u32, offset: i32) -> il::Instr {
294 +
    return il::Instr::Load {
295 +
        typ: il::Type::W64, dst: il::Reg { n: dst }, src: il::Reg { n: src }, offset,
296 +
    };
297 +
}
298 +
299 +
fn store(src: il::Val, dst: u32, offset: i32) -> il::Instr {
300 +
    return il::Instr::Store { typ: il::Type::W32, src, dst: il::Reg { n: dst }, offset };
301 +
}
302 +
303 +
fn store64(src: il::Val, dst: u32, offset: i32) -> il::Instr {
304 +
    return il::Instr::Store { typ: il::Type::W64, src, dst: il::Reg { n: dst }, offset };
305 +
}
306 +
307 +
fn loadPtr(dst: u32, src: u32, offset: i32) -> il::Instr {
308 +
    return il::Instr::LoadPtr { dst: il::Reg { n: dst }, src: il::Reg { n: src }, offset,
309 +
        nullable: false };
310 +
}
311 +
312 +
fn storePtr(src: il::Val, dst: u32, offset: i32) -> il::Instr {
313 +
    return il::Instr::StorePtr { src, dst: il::Reg { n: dst }, offset };
314 +
}
315 +
316 +
/// Load a pointer or function value that can be zero.
317 +
fn loadNullablePtr(dst: u32, src: u32, offset: i32) -> il::Instr {
318 +
    return il::Instr::LoadPtr { dst: il::Reg { n: dst }, src: il::Reg { n: src }, offset,
319 +
        nullable: true };
320 +
}
321 +
322 +
fn field(dst: u32, src: u32, offset: u32) -> il::Instr {
323 +
    return il::Instr::Field { dst: il::Reg { n: dst }, src: il::Reg { n: src }, offset };
324 +
}
325 +
326 +
fn elem(dst: u32, base: u32, index: il::Val, layout: u32, count: u32) -> il::Instr {
327 +
    return il::Instr::Elem {
328 +
        dst: il::Reg { n: dst }, base: il::Reg { n: base }, index, layout, count,
329 +
    };
330 +
}
331 +
332 +
fn sliceElem(dst: u32, slice: u32, index: il::Val, layout: u32) -> il::Instr {
333 +
    return il::Instr::SliceElem {
334 +
        dst: il::Reg { n: dst }, slice: il::Reg { n: slice }, index, layout,
335 +
    };
336 +
}
337 +
338 +
fn sliceNew(dst: u32, base: il::Val, layout: u32, count: u32) -> il::Instr {
339 +
    return il::Instr::SliceNew {
340 +
        dst: il::Reg { n: dst }, base, layout, count, start: imm(0), end: imm(count as i64),
341 +
    };
342 +
}
343 +
344 +
fn sliceSub(dst: u32, src: u32, layout: u32) -> il::Instr {
345 +
    return il::Instr::SliceSub {
346 +
        dst: il::Reg { n: dst }, src: il::Reg { n: src }, layout, start: imm(0), end: imm(0),
347 +
    };
348 +
}
349 +
350 +
fn blit(dst: u32, src: u32, layout: u32) -> il::Instr {
351 +
    return il::Instr::Blit { dst: il::Reg { n: dst }, src: il::Reg { n: src }, layout };
352 +
}
353 +
354 +
fn copy(dst: u32, val: il::Val) -> il::Instr {
355 +
    return il::Instr::Copy { dst: il::Reg { n: dst }, val };
356 +
}
357 +
358 +
fn ret(val: il::Val) -> il::Instr {
359 +
    return il::Instr::Ret { val };
360 +
}
361 +
362 +
fn retVoid() -> il::Instr {
363 +
    return il::Instr::Ret { val: nil };
364 +
}
365 +
366 +
fn call(dst: ?u32, retTy: il::ValType, callee: il::Val, values: il::ArgRange) -> il::Instr {
367 +
    let mut result: ?il::Reg = nil;
368 +
    if let n = dst {
369 +
        set result = il::Reg { n };
370 +
    }
371 +
    return il::Instr::Call { retTy, dst: result, func: callee, args: values };
372 +
}
373 +
374 +
fn add(dst: u32, a: il::Val, c: il::Val) -> il::Instr {
375 +
    return il::Instr::BinOp {
376 +
        op: il::BinOp::Add, typ: il::Type::W64, dst: il::Reg { n: dst }, a, b: c,
377 +
    };
378 +
}
379 +
380 +
fn jmp(target: u32, values: il::ArgRange) -> il::Instr {
381 +
    return il::Instr::Jmp { target, args: values };
382 +
}
383 +
384 +
////////////
385 +
// Checks //
386 +
////////////
387 +
388 +
/// Verify the program, and return the error if there is one.
389 +
unsafe fn verdict(b: &mut Builder) -> ?verify::Error {
390 +
    let prog = program(b);
391 +
    let mut scratch = alloc::new(&mut SCRATCH[..]);
392 +
    try verify::verifyProgram(&prog, CONFIG, &mut scratch) catch err {
393 +
        return err;
394 +
    };
395 +
    return nil;
396 +
}
397 +
398 +
/// Check that the program is accepted.
399 +
unsafe fn accepted(b: &mut Builder) throws (testing::TestError) {
400 +
    if let _ = verdict(b) {
401 +
        throw testing::TestError::Failed;
402 +
    }
403 +
}
404 +
405 +
/// Check that the program is rejected for violating `rule`.
406 +
unsafe fn rejected(b: &mut Builder, rule: verify::Rule) throws (testing::TestError) {
407 +
    let err = verdict(b) else {
408 +
        throw testing::TestError::Failed;
409 +
    };
410 +
    try testing::expect(err.rule == rule);
411 +
}
412 +
413 +
/// Check that the program is accepted when `rule` is nil, or rejected for violating `rule`.
414 +
unsafe fn expect(b: &mut Builder, rule: ?verify::Rule) throws (testing::TestError) {
415 +
    if let want = rule {
416 +
        try rejected(b, want);
417 +
    } else {
418 +
        try accepted(b);
419 +
    }
420 +
}
421 +
422 +
/// Add `main`, a function of one block with parameters and instructions, to the program of
423 +
/// `b`, and check it as [`expect`] does.
424 +
unsafe fn checkIn(
425 +
    b: &mut Builder, params: &[il::Param], ret: il::ValType, instrs: &[il::Instr],
426 +
    rule: ?verify::Rule
427 +
) throws (testing::TestError) {
428 +
    addFn(b, "main", params, ret, instrs);
429 +
    try expect(b, rule);
430 +
}
431 +
432 +
/// Check the program that holds only `main`, as for [`checkIn`].
433 +
unsafe fn checkBody(
434 +
    params: &[il::Param], ret: il::ValType, instrs: &[il::Instr], rule: ?verify::Rule
435 +
) throws (testing::TestError) {
436 +
    let mut b = newBuilder();
437 +
    try checkIn(&mut b, params, ret, instrs, rule);
438 +
}
439 +
440 +
/// Check the program that holds only `main`, a function without result whose body is `instrs`
441 +
/// followed by a return, as for [`checkIn`].
442 +
unsafe fn check(params: &[il::Param], instrs: &[il::Instr], rule: ?verify::Rule)
443 +
    throws (testing::TestError)
444 +
{
445 +
    let mut b = newBuilder();
446 +
    let mut body: *mut [il::Instr] = &mut [];
447 +
    try! body.extend(instrs, &mut b.arena);
448 +
    try! body.append(retVoid(), &mut b.arena);
449 +
    try checkIn(&mut b, params, il::ValType::Void, &body[..], rule);
450 +
}
451 +
452 +
fn br(a: il::Val, thenTarget: u32, elseTarget: u32) -> il::Instr {
453 +
    return il::Instr::Br {
454 +
        op: il::CmpOp::Eq, typ: il::Type::W64, a, b: imm(0), thenTarget,
455 +
        thenArgs: il::ArgRange { start: 0, len: 0 }, elseTarget,
456 +
        elseArgs: il::ArgRange { start: 0, len: 0 },
457 +
    };
458 +
}
459 +
460 +
/// An empty range of arguments.
461 +
fn none() -> il::ArgRange {
462 +
    return il::ArgRange { start: 0, len: 0 };
463 +
}
464 +
465 +
/// The data type, as a list of one parameter.
466 +
fn oneData() -> il::Param {
467 +
    return param(0, dataType());
468 +
}
469 +
470 +
////////////////////////
471 +
// Registers and flow //
472 +
////////////////////////
473 +
474 +
/// A trivial function is accepted.
475 +
@test unsafe fn trivial() throws (testing::TestError) {
476 +
    try checkBody(&[], il::ValType::Void, &[retVoid()], nil);
477 +
}
478 +
479 +
/// A register must be defined before its use.
480 +
@test unsafe fn useBeforeDefinition() throws (testing::TestError) {
481 +
    try check(&[], &[add(1, reg(2), imm(1)), copy(2, imm(0))], verify::Rule::Register);
482 +
    try check(&[], &[copy(2, imm(0)), add(1, reg(2), imm(1))], nil);
483 +
}
484 +
485 +
/// A register has one definition, also across a parameter and an instruction.
486 +
@test unsafe fn definedTwice() throws (testing::TestError) {
487 +
    try check(&[], &[copy(1, imm(0)), copy(1, imm(1))], verify::Rule::Register);
488 +
    try check(&[oneData()], &[copy(0, imm(1))], verify::Rule::Register);
489 +
    try checkBody(&[oneData(), oneData()], il::ValType::Void, &[retVoid()], verify::Rule::Register);
490 +
}
491 +
492 +
/// A register belongs to the function that defines it: another function can use the number
493 +
/// for its own register, but cannot read the definition.
494 +
@test unsafe fn registersAreLocal() throws (testing::TestError) {
495 +
    let mut ok = newBuilder();
496 +
    addFn(&mut ok, "f", &[], il::ValType::Void, &[copy(1, imm(0)), retVoid()]);
497 +
    try checkIn(&mut ok, &[], il::ValType::Void, &[copy(1, imm(0)), retVoid()], nil);
498 +
    let mut bad = newBuilder();
499 +
    addFn(&mut bad, "f", &[], il::ValType::Void, &[copy(1, imm(0)), retVoid()]);
500 +
    try checkIn(&mut bad, &[], il::ValType::Void, &[add(2, reg(1), imm(1)), retVoid()],
501 +
        verify::Rule::Register);
502 +
    let mut param = newBuilder();
503 +
    addFn(&mut param, "f", &[oneData()], il::ValType::Void, &[retVoid()]);
504 +
    try checkIn(&mut param, &[], il::ValType::Void, &[add(2, reg(0), imm(1)), retVoid()],
505 +
        verify::Rule::Register);
506 +
}
507 +
508 +
/// Register numbers stay below the limit.
509 +
@test unsafe fn registerLimit() throws (testing::TestError) {
510 +
    try check(&[], &[copy(64, imm(0))], verify::Rule::Limit);
511 +
    try check(&[], &[copy(63, imm(0))], nil);
512 +
}
513 +
514 +
/// A definition on one path does not dominate the merge.
515 +
@test unsafe fn definitionDoesNotDominate() throws (testing::TestError) {
516 +
    let mut b = newBuilder();
517 +
    let blocks = [
518 +
        block(&mut b, &[], &[br(reg(0), 1, 2)]),
519 +
        block(&mut b, &[], &[copy(1, imm(5)), jmp(3, none())]),
520 +
        block(&mut b, &[], &[jmp(3, none())]),
521 +
        block(&mut b, &[], &[add(2, reg(1), imm(0)), retVoid()]),
522 +
    ];
523 +
    addBlocks(&mut b, "main", &[oneData()], il::ValType::Void, &blocks[..]);
524 +
    try rejected(&mut b, verify::Rule::Register);
525 +
}
526 +
527 +
/// The merge of two paths receives the value as a block argument.
528 +
@test unsafe fn blockArgumentMerges() throws (testing::TestError) {
529 +
    let mut b = newBuilder();
530 +
    let five = args(&mut b, &[imm(5)]);
531 +
    let six = args(&mut b, &[imm(6)]);
532 +
    let blocks = [
533 +
        block(&mut b, &[], &[br(reg(0), 1, 2)]),
534 +
        block(&mut b, &[], &[jmp(3, five)]),
535 +
        block(&mut b, &[], &[jmp(3, six)]),
536 +
        block(&mut b, &[param(1, dataType())], &[add(2, reg(1), imm(0)), retVoid()]),
537 +
    ];
538 +
    addBlocks(&mut b, "main", &[oneData()], il::ValType::Void, &blocks[..]);
539 +
    try accepted(&mut b);
540 +
}
541 +
542 +
/// A loop carries a value around the back edge. A register defined in the body does
543 +
/// not reach the header.
544 +
@test unsafe fn loops() throws (testing::TestError) {
545 +
    let mut b = newBuilder();
546 +
    let zero = args(&mut b, &[imm(0)]);
547 +
    let next = args(&mut b, &[reg(2)]);
548 +
    let blocks = [
549 +
        block(&mut b, &[], &[jmp(1, zero)]),
550 +
        block(&mut b, &[param(1, dataType())], &[add(2, reg(1), imm(1)), br(reg(2), 2, 3)]),
551 +
        block(&mut b, &[], &[jmp(1, next)]),
552 +
        block(&mut b, &[], &[retVoid()]),
553 +
    ];
554 +
    addBlocks(&mut b, "main", &[], il::ValType::Void, &blocks[..]);
555 +
    try accepted(&mut b);
556 +
557 +
    let mut bad = newBuilder();
558 +
    let back = args(&mut bad, &[reg(2)]);
559 +
    let again = [
560 +
        block(&mut bad, &[], &[jmp(1, back)]),
561 +
        block(&mut bad, &[param(1, dataType())], &[add(2, reg(1), imm(1)), br(reg(2), 2, 3)]),
562 +
        block(&mut bad, &[], &[jmp(1, back)]),
563 +
        block(&mut bad, &[], &[retVoid()]),
564 +
    ];
565 +
    addBlocks(&mut bad, "main", &[], il::ValType::Void, &again[..]);
566 +
    try rejected(&mut bad, verify::Rule::Register);
567 +
}
568 +
569 +
/// A block that nothing reaches is checked, and may use only its own definitions.
570 +
@test unsafe fn unreachableBlock() throws (testing::TestError) {
571 +
    let mut b = newBuilder();
572 +
    let blocks = [
573 +
        block(&mut b, &[], &[copy(1, imm(0)), retVoid()]),
574 +
        block(&mut b, &[], &[copy(2, imm(0)), add(3, reg(2), imm(1)), retVoid()]),
575 +
    ];
576 +
    addBlocks(&mut b, "main", &[], il::ValType::Void, &blocks[..]);
577 +
    try accepted(&mut b);
578 +
579 +
    let mut bad = newBuilder();
580 +
    let again = [
581 +
        block(&mut bad, &[], &[copy(1, imm(0)), retVoid()]),
582 +
        block(&mut bad, &[], &[add(3, reg(1), imm(1)), retVoid()]),
583 +
    ];
584 +
    addBlocks(&mut bad, "main", &[], il::ValType::Void, &again[..]);
585 +
    try rejected(&mut bad, verify::Rule::Register);
586 +
}
587 +
588 +
/// Every block ends with exactly one terminator.
589 +
@test unsafe fn terminators() throws (testing::TestError) {
590 +
    try checkBody(&[], il::ValType::Void, &[copy(1, imm(0))], verify::Rule::Structure);
591 +
    try checkBody(&[], il::ValType::Void, &[], verify::Rule::Structure);
592 +
    try check(&[], &[retVoid()], verify::Rule::Structure);
593 +
    try checkBody(&[], il::ValType::Void, &[jmp(5, none())], verify::Rule::Structure);
594 +
}
595 +
596 +
/// The entry block takes no parameters, and a function has blocks within the limit.
597 +
@test unsafe fn entryBlock() throws (testing::TestError) {
598 +
    let mut b = newBuilder();
599 +
    let entry = block(&mut b, &[param(1, dataType())], &[retVoid()]);
600 +
    addBlocks(&mut b, "main", &[], il::ValType::Void, &[entry]);
601 +
    try rejected(&mut b, verify::Rule::Structure);
602 +
603 +
    let mut empty = newBuilder();
604 +
    addBlocks(&mut empty, "main", &[], il::ValType::Void, &[]);
605 +
    try rejected(&mut empty, verify::Rule::Structure);
606 +
607 +
    let mut many = newBuilder();
608 +
    let mut blocks: [il::Block; 17] = [block(&mut many, &[], &[retVoid()]); 17];
609 +
    addBlocks(&mut many, "main", &[], il::ValType::Void, &blocks[..]);
610 +
    try rejected(&mut many, verify::Rule::Limit);
611 +
}
612 +
613 +
/// A branch passes as many arguments as the block has parameters, of matching types.
614 +
@test unsafe fn branchArguments() throws (testing::TestError) {
615 +
    let mut count = newBuilder();
616 +
    let blocks = [
617 +
        block(&mut count, &[], &[jmp(1, none())]),
618 +
        block(&mut count, &[param(1, dataType())], &[retVoid()]),
619 +
    ];
620 +
    addBlocks(&mut count, "main", &[], il::ValType::Void, &blocks[..]);
621 +
    try rejected(&mut count, verify::Rule::Arity);
622 +
623 +
    let mut kind = newBuilder();
624 +
    let one = args(&mut kind, &[imm(1)]);
625 +
    let more = [
626 +
        block(&mut kind, &[], &[jmp(1, one)]),
627 +
        block(&mut kind, &[param(1, ptrType(P4, true, true, false))], &[retVoid()]),
628 +
    ];
629 +
    addBlocks(&mut kind, "main", &[], il::ValType::Void, &more[..]);
630 +
    try rejected(&mut kind, verify::Rule::Type);
631 +
}
632 +
633 +
/// Parameters and arguments are limited in number.
634 +
@test unsafe fn parameterLimit() throws (testing::TestError) {
635 +
    let mut b = newBuilder();
636 +
    let mut params: [il::Param; 9] = [oneData(); 9];
637 +
    for i in 0..9 {
638 +
        set params[i] = param(i, dataType());
639 +
    }
640 +
    addFn(&mut b, "main", &params[..], il::ValType::Void, &[retVoid()]);
641 +
    try rejected(&mut b, verify::Rule::Limit);
642 +
    let mut ok = newBuilder();
643 +
    addFn(&mut ok, "main", &params[..8], il::ValType::Void, &[retVoid()]);
644 +
    try accepted(&mut ok);
645 +
}
646 +
647 +
///////////////////////
648 +
// Loads and stores  //
649 +
///////////////////////
650 +
651 +
/// An access stays inside the layout of the pointer.
652 +
@test unsafe fn accessBounds() throws (testing::TestError) {
653 +
    try check(&[], &[reserve(0, P8), store(imm(1), 0, 4), load(1, 0, 4)], nil);
654 +
    try check(&[], &[reserve(0, P4), load(1, 0, 4)], verify::Rule::Bounds);
655 +
    try check(&[], &[reserve(0, P4), load(1, 0, -4)], verify::Rule::Bounds);
656 +
    try check(&[], &[reserve(0, P4), load64(1, 0, 0)], verify::Rule::Bounds);
657 +
    try check(&[], &[reserve(0, P4), store(imm(1), 0, 1)], verify::Rule::Bounds);
658 +
}
659 +
660 +
/// Data never becomes a pointer.
661 +
@test unsafe fn forgedPointer() throws (testing::TestError) {
662 +
    try check(&[oneData()], &[load(1, 0, 0)], verify::Rule::Type);
663 +
    try check(&[], &[reserve(0, P8), load64(1, 0, 0), load(2, 1, 0)], verify::Rule::Type);
664 +
    try check(&[], &[copy(1, imm(8)), store(imm(1), 1, 0)], verify::Rule::Type);
665 +
    try check(&[oneData()], &[reserve(1, P8), add(2, reg(1), imm(0)), load(3, 2, 0)],
666 +
        verify::Rule::Type);
667 +
}
668 +
669 +
/// A pointer that can be null needs a proof before memory access.
670 +
@test unsafe fn nullablePointer() throws (testing::TestError) {
671 +
    let maybe = [param(0, ptrType(P4, true, false, true))];
672 +
    try check(&maybe[..], &[load(1, 0, 0)], verify::Rule::Null);
673 +
    try check(&maybe[..], &[field(1, 0, 0)], verify::Rule::Null);
674 +
}
675 +
676 +
/// Only the tested pointer on the nonzero edge of a full-width equality test is refined.
677 +
@test unsafe fn branchNonNull() throws (testing::TestError) {
678 +
    for typ in [il::Type::W8, il::Type::W32, il::Type::W64] {
679 +
        for op in [il::CmpOp::Eq, il::CmpOp::Ne, il::CmpOp::Ult] {
680 +
            for swapped in [false, true] {
681 +
                for thenNonNull in [false, true] {
682 +
                    for passed in [reg(0), reg(1)] {
683 +
                        let mut b = newBuilder();
684 +
                        let value = args(&mut b, &[passed]);
685 +
                        let blocks = [
686 +
                            block(&mut b, &[], &[il::Instr::Br {
687 +
                                op, typ, a: imm(0) if swapped else reg(0),
688 +
                                b: reg(0) if swapped else imm(0),
689 +
                                thenTarget: 1 if thenNonNull else 2,
690 +
                                thenArgs: value if thenNonNull else none(),
691 +
                                elseTarget: 2 if thenNonNull else 1,
692 +
                                elseArgs: none() if thenNonNull else value,
693 +
                            }]),
694 +
                            block(&mut b, &[param(2, ptrType(P4, true, false, false))],
695 +
                                &[load(3, 2, 0), retVoid()]),
696 +
                            block(&mut b, &[], &[retVoid()]),
697 +
                        ];
698 +
                        let params = [
699 +
                            param(0, ptrType(P4, true, false, true)),
700 +
                            param(1, ptrType(P4, true, false, true)),
701 +
                        ];
702 +
                        addBlocks(&mut b, "main", &params[..], il::ValType::Void, &blocks[..]);
703 +
                        let proven = typ == il::Type::W64 and passed == reg(0)
704 +
                            and ((op == il::CmpOp::Ne and thenNonNull)
705 +
                                or (op == il::CmpOp::Eq and not thenNonNull));
706 +
                        if proven {
707 +
                            try accepted(&mut b);
708 +
                        } else {
709 +
                            try rejected(&mut b, verify::Rule::Null);
710 +
                        }
711 +
                    }
712 +
                }
713 +
            }
714 +
        }
715 +
    }
716 +
}
717 +
718 +
/// A null test preserves pointer rights and checks both edges when their target is shared.
719 +
@test unsafe fn branchNonNullRights() throws (testing::TestError) {
720 +
    for want in [ptrType(P4, true, true, false), ptrType(P4, false, true, false),
721 +
        ptrType(P8, false, false, false), ptrType(P4, false, false, false)] {
722 +
        for shared in [false, true] {
723 +
            let mut b = newBuilder();
724 +
            let value = args(&mut b, &[reg(0)]);
725 +
            let blocks = [
726 +
                block(&mut b, &[], &[il::Instr::Br {
727 +
                    op: il::CmpOp::Ne, typ: il::Type::W64, a: reg(0), b: imm(0),
728 +
                    thenTarget: 1, thenArgs: value,
729 +
                    elseTarget: 1 if shared else 2, elseArgs: value if shared else none(),
730 +
                }]),
731 +
                block(&mut b, &[param(1, want)], &[retVoid()]),
732 +
                block(&mut b, &[], &[retVoid()]),
733 +
            ];
734 +
            let params = [param(0, ptrType(P4, false, false, true))];
735 +
            addBlocks(&mut b, "main", &params[..], il::ValType::Void, &blocks[..]);
736 +
            if shared and want == ptrType(P4, false, false, false) {
737 +
                try rejected(&mut b, verify::Rule::Null);
738 +
            } else if want == ptrType(P4, true, true, false) {
739 +
                try rejected(&mut b, verify::Rule::Class);
740 +
            } else if want == ptrType(P4, false, true, false) {
741 +
                try rejected(&mut b, verify::Rule::Mutability);
742 +
            } else if want == ptrType(P8, false, false, false) {
743 +
                try rejected(&mut b, verify::Rule::View);
744 +
            } else {
745 +
                try accepted(&mut b);
746 +
            }
747 +
        }
748 +
    }
749 +
    let mut data = newBuilder();
750 +
    let value = args(&mut data, &[reg(0)]);
751 +
    let blocks = [
752 +
        block(&mut data, &[], &[il::Instr::Br {
753 +
            op: il::CmpOp::Ne, typ: il::Type::W64, a: reg(0), b: imm(0),
754 +
            thenTarget: 1, thenArgs: value, elseTarget: 2, elseArgs: none(),
755 +
        }]),
756 +
        block(&mut data, &[param(1, ptrType(P4, false, false, false))], &[retVoid()]),
757 +
        block(&mut data, &[], &[retVoid()]),
758 +
    ];
759 +
    addBlocks(&mut data, "main", &[oneData()], il::ValType::Void, &blocks[..]);
760 +
    try rejected(&mut data, verify::Rule::Type);
761 +
}
762 +
763 +
/// A write needs a pointer to writable memory.
764 +
@test unsafe fn writeThroughConstant() throws (testing::TestError) {
765 +
    let fixed = [param(0, ptrType(P4, true, false, false))];
766 +
    try check(&fixed[..], &[store(imm(1), 0, 0)], verify::Rule::Mutability);
767 +
    try check(&fixed[..], &[load(1, 0, 0)], nil);
768 +
}
769 +
770 +
/// Pointers are loaded only from their slots.
771 +
@test unsafe fn pointerLoad() throws (testing::TestError) {
772 +
    try check(&[], &[reserve(0, P8), loadPtr(1, 0, 0)], verify::Rule::Slot);
773 +
    try check(&[], &[reserve(0, CELL), loadPtr(2, 0, 0), store(imm(1), 2, 0)], nil);
774 +
    try check(&[], &[reserve(0, CELL), loadNullablePtr(1, 0, 0), store(imm(1), 1, 0)],
775 +
        verify::Rule::Null);
776 +
    try check(&[], &[reserve(0, CELLC), loadPtr(2, 0, 0), store(imm(1), 2, 0)],
777 +
        verify::Rule::Mutability);
778 +
    try check(&[], &[reserve(0, CELL), loadPtr(1, 0, 4)], verify::Rule::Slot);
779 +
    try check(&[], &[reserve(0, SLICE), loadPtr(1, 0, 0)], verify::Rule::Slot);
780 +
    try check(&[oneData()], &[loadPtr(1, 0, 0)], verify::Rule::Type);
781 +
}
782 +
783 +
/// A data store cannot overwrite a pointer, or the pointer or length of a slice.
784 +
@test unsafe fn dataOverSlot() throws (testing::TestError) {
785 +
    try check(&[], &[reserve(0, CELL), store64(imm(5), 0, 0)], verify::Rule::Slot);
786 +
    try check(&[], &[reserve(0, CELL), store(imm(5), 0, 4)], verify::Rule::Slot);
787 +
    try check(&[], &[reserve(0, SLICE), store64(imm(5), 0, 0)], verify::Rule::Slot);
788 +
    try check(&[], &[reserve(0, SLICE), store(imm(5), 0, 8)], verify::Rule::Slot);
789 +
    try check(&[], &[reserve(0, SLICE), store(imm(5), 0, 12)], nil);
790 +
    try check(&[], &[reserve(0, PAIR), store64(imm(5), 0, 8)], verify::Rule::Slot);
791 +
    try check(&[], &[reserve(0, PAIR), store64(imm(5), 0, 0), store64(imm(5), 0, 24)],
792 +
        verify::Rule::Slot);
793 +
    try check(&[], &[reserve(0, PAIR), store64(imm(5), 0, 0), store(imm(5), 0, 28)], nil);
794 +
    try check(&[], &[reserve(0, CELLS), store64(imm(5), 0, 8)], verify::Rule::Slot);
795 +
}
796 +
797 +
/// A pointer is stored into a slot of its kind, with at most the rights of the slot.
798 +
@test unsafe fn pointerStore() throws (testing::TestError) {
799 +
    let own = param(1, ptrType(P4, true, true, false));
800 +
    let cell = param(0, ptrType(CELL, false, true, false));
801 +
    try check(&[cell, own], &[storePtr(reg(1), 0, 0)], nil);
802 +
    try check(&[cell], &[reserve(1, P4), storePtr(reg(1), 0, 0)], verify::Rule::Class);
803 +
    try check(&[cell, param(1, ptrType(P4, true, false, false))], &[storePtr(reg(1), 0, 0)],
804 +
        verify::Rule::Mutability);
805 +
    try check(&[cell, param(1, ptrType(P4, true, true, true))], &[storePtr(reg(1), 0, 0)], nil);
806 +
    try check(&[cell, param(1, ptrType(CELL, true, true, false))], &[storePtr(reg(1), 0, 0)],
807 +
        verify::Rule::View);
808 +
    try check(&[cell, param(1, ptrType(P8, true, true, false))], &[storePtr(reg(1), 0, 0)], nil);
809 +
    try check(&[param(0, ptrType(P8, false, true, false)), own], &[storePtr(reg(1), 0, 0)],
810 +
        verify::Rule::Slot);
811 +
    try check(&[param(0, ptrType(CELL, false, false, false)), own], &[storePtr(reg(1), 0, 0)],
812 +
        verify::Rule::Mutability);
813 +
}
814 +
815 +
/// A reference stays in a container of the frame that it lives in.
816 +
@test unsafe fn referenceStore() throws (testing::TestError) {
817 +
    let borrowed = param(1, ptrType(P4, false, true, false));
818 +
    let owned = param(1, ptrType(P4, true, true, false));
819 +
    let outer = param(0, ptrType(LOCAL, false, true, false));
820 +
    try check(&[outer, borrowed], &[storePtr(reg(1), 0, 0)], verify::Rule::Class);
821 +
    try check(&[borrowed], &[reserve(0, LOCAL), storePtr(reg(1), 0, 0)], nil);
822 +
    try check(&[outer], &[reserve(1, P4), storePtr(reg(1), 0, 0)], verify::Rule::Class);
823 +
    try check(&[borrowed], &[reserve(0, PAIR), field(2, 0, 8), storePtr(reg(1), 2, 0)],
824 +
        verify::Rule::Class);
825 +
    try check(&[outer, owned], &[storePtr(reg(1), 0, 0)], nil);
826 +
    try check(&[outer], &[loadPtr(2, 0, 0), storePtr(reg(2), 0, 0)],
827 +
        verify::Rule::Class);
828 +
}
829 +
830 +
/// Only zero is a pointer that is not a register.
831 +
@test unsafe fn pointerStoreValues() throws (testing::TestError) {
832 +
    let cell = param(0, ptrType(CELL, false, true, false));
833 +
    try check(&[cell], &[storePtr(imm(0), 0, 0)], nil);
834 +
    try check(&[cell], &[storePtr(imm(1), 0, 0)], verify::Rule::Type);
835 +
    try check(&[cell], &[storePtr(il::Val::Undef, 0, 0)], verify::Rule::Type);
836 +
    try check(&[cell, param(1, dataType())], &[storePtr(reg(1), 0, 0)], verify::Rule::Type);
837 +
}
838 +
839 +
/// A field is a pointer into a layout at a constant offset.
840 +
@test unsafe fn fieldOffsets() throws (testing::TestError) {
841 +
    let own = param(9, ptrType(P4, true, true, false));
842 +
    try check(&[own], &[reserve(0, PAIR), field(1, 0, 8), storePtr(reg(9), 1, 0)], nil);
843 +
    try check(&[], &[reserve(0, PAIR), field(1, 0, 32)], nil);
844 +
    try check(&[], &[reserve(0, PAIR), field(1, 0, 33)], verify::Rule::Bounds);
845 +
    try check(&[], &[reserve(0, PAIR), field(1, 0, 32), load(2, 1, 0)], verify::Rule::Bounds);
846 +
    try check(&[], &[reserve(0, PAIR), field(1, 0, 8), field(2, 1, 25)], verify::Rule::Bounds);
847 +
    try check(&[], &[reserve(0, PAIR), field(1, 0, 8), load(2, 1, -12)], verify::Rule::Bounds);
848 +
    try check(&[own], &[reserve(0, PAIR), field(1, 0, 4), storePtr(reg(9), 1, 0)],
849 +
        verify::Rule::Slot);
850 +
}
851 +
852 +
/// An element address needs an array of the element layout and count.
853 +
@test unsafe fn elementAddress() throws (testing::TestError) {
854 +
    try check(&[oneData()], &[reserve(1, P16), elem(2, 1, reg(0), P4, 4), store(imm(1), 2, 0)],
855 +
        nil);
856 +
    try check(&[], &[reserve(0, P16), elem(1, 0, imm(0), P4, 5)], verify::Rule::Bounds);
857 +
    try check(&[], &[reserve(0, CELLS), elem(1, 0, imm(1), CELL, 3), loadPtr(2, 1, 0)], nil);
858 +
    try check(&[], &[reserve(0, CELLS), elem(1, 0, imm(1), CELL, 2)], verify::Rule::View);
859 +
    try check(&[], &[reserve(0, CELLS), elem(1, 0, imm(1), CELL, 4)], verify::Rule::Bounds);
860 +
    try check(&[], &[reserve(0, P16), elem(1, 0, imm(0), CELL, 2)], verify::Rule::View);
861 +
    try checkBody(&[], il::ValType::Void, &[reserve(0, PAIR), field(1, 0, 8),
862 +
        elem(2, 1, imm(0), CELL, 1), loadPtr(3, 2, 0), retVoid()], nil);
863 +
    try check(&[], &[reserve(0, PAIR), elem(1, 0, imm(0), P8, 2)], verify::Rule::View);
864 +
    try check(&[oneData()], &[elem(1, 0, imm(0), P4, 1)], verify::Rule::Type);
865 +
}
866 +
867 +
/// Plain array elements must have the alignment of their layout.
868 +
@test unsafe fn elementAlignment() throws (testing::TestError) {
869 +
    try check(&[], &[reserve(0, P16), field(1, 0, 4), elem(2, 1, imm(0), P4, 2)], nil);
870 +
    try check(
871 +
        &[], &[reserve(0, P16), field(1, 0, 2), elem(2, 1, imm(0), P4, 2)], verify::Rule::View
872 +
    );
873 +
    try check(&[], &[reserve(0, B8), elem(1, 0, imm(0), P4, 2)], verify::Rule::View);
874 +
}
875 +
876 +
////////////
877 +
// Slices //
878 +
////////////
879 +
880 +
/// A slice is built over an array that is large enough, with the rights of the slot.
881 +
@test unsafe fn sliceNewBase() throws (testing::TestError) {
882 +
    try check(&[], &[reserve(0, P16), reserve(1, SLICE), sliceNew(1, reg(0), P1, 16)],
883 +
        verify::Rule::Class);
884 +
    let own = param(0, ptrType(P16, true, true, false));
885 +
    try check(&[own], &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 16)], nil);
886 +
    try check(&[own], &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 17)], verify::Rule::Bounds);
887 +
    try check(&[own], &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 8)], nil);
888 +
    try check(&[own], &[reserve(1, SLICE), sliceNew(1, reg(0), P4, 4)], verify::Rule::View);
889 +
    try check(&[param(0, ptrType(P16, true, true, true))],
890 +
        &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 16)], verify::Rule::Null);
891 +
    try check(&[oneData()], &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 16)], verify::Rule::Type);
892 +
    try check(&[param(0, ptrType(CELLS, true, true, false))],
893 +
        &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 24)], verify::Rule::View);
894 +
}
895 +
896 +
/// A slice of no elements needs no base.
897 +
@test unsafe fn emptySlice() throws (testing::TestError) {
898 +
    try check(&[], &[reserve(0, SLICE), sliceNew(0, imm(4), P1, 0)], nil);
899 +
    try check(&[], &[reserve(0, SLICE), sliceNew(0, il::Val::Undef, P1, 0)], nil);
900 +
}
901 +
902 +
/// A writable slice needs writable memory.
903 +
@test unsafe fn sliceMutability() throws (testing::TestError) {
904 +
    let fixed = [param(0, ptrType(P16, true, false, false))];
905 +
    try check(&fixed[..], &[reserve(1, SLICE), sliceNew(1, reg(0), P1, 16)],
906 +
        verify::Rule::Mutability);
907 +
    try check(&fixed[..], &[reserve(1, SLICEC), sliceNew(1, reg(0), P1, 16)], nil);
908 +
    try check(&[param(0, ptrType(P16, true, true, false)),
909 +
        param(1, ptrType(SLICEC, false, false, false))], &[sliceNew(1, reg(0), P1, 16)],
910 +
        verify::Rule::Mutability);
911 +
}
912 +
913 +
/// A slice that does not own its elements is built in the frame of its base.
914 +
@test unsafe fn sliceClasses() throws (testing::TestError) {
915 +
    let borrowed = param(1, ptrType(BORROW, false, true, false));
916 +
    let own = param(0, ptrType(P16, true, true, false));
917 +
    try check(&[], &[reserve(0, P16), reserve(1, BORROW), sliceNew(1, reg(0), P1, 16)], nil);
918 +
    try check(&[param(0, ptrType(P16, false, true, false)), borrowed],
919 +
        &[sliceNew(1, reg(0), P1, 16)], verify::Rule::Class);
920 +
    try check(&[own, borrowed], &[sliceNew(1, reg(0), P1, 16)], nil);
921 +
    try check(&[own], &[reserve(1, P16), sliceNew(1, reg(0), P1, 16)], verify::Rule::Slot);
922 +
}
923 +
924 +
/// A slice element is checked at run time, and the result has the rights of the slice.
925 +
@test unsafe fn sliceElement() throws (testing::TestError) {
926 +
    try check(&[oneData()], &[reserve(1, SLICE), sliceElem(2, 1, reg(0), P1), load(3, 2, 0)],
927 +
        verify::Rule::Bounds);
928 +
    try check(&[oneData()], &[reserve(1, SLICE), sliceElem(2, 1, reg(0), P1)], nil);
929 +
    try check(&[oneData()], &[reserve(1, SLICE), sliceElem(2, 1, reg(0), P4)], verify::Rule::View);
930 +
    try check(&[oneData()], &[reserve(1, P16), sliceElem(2, 1, reg(0), P1)], verify::Rule::Slot);
931 +
    try check(&[oneData()], &[reserve(1, SLICEC), sliceElem(2, 1, reg(0), P1), store(imm(1), 2, 0)],
932 +
        verify::Rule::Mutability);
933 +
}
934 +
935 +
/// A sub-slice has the rights of the slice that it is taken from.
936 +
@test unsafe fn subSlice() throws (testing::TestError) {
937 +
    try check(&[], &[reserve(0, SLICE), reserve(1, SLICE), sliceSub(1, 0, P1)], nil);
938 +
    try check(&[], &[reserve(0, SLICEC), reserve(1, SLICE), sliceSub(1, 0, P1)],
939 +
        verify::Rule::Mutability);
940 +
    try check(&[], &[reserve(0, SLICE), reserve(1, BORROW), sliceSub(1, 0, P1)], nil);
941 +
    try check(&[], &[reserve(0, BORROW), reserve(1, SLICE), sliceSub(1, 0, P1)],
942 +
        verify::Rule::Class);
943 +
    try check(&[param(1, ptrType(BORROW, false, true, false))],
944 +
        &[reserve(0, BORROW), sliceSub(1, 0, P1)], verify::Rule::Class);
945 +
    try check(&[], &[reserve(0, P16), reserve(1, SLICE), sliceSub(1, 0, P1)], verify::Rule::Slot);
946 +
}
947 +
948 +
////////////
949 +
// Blits  //
950 +
////////////
951 +
952 +
/// The source holds the copied object. The destination holds it too, or is a plain region.
953 +
@test unsafe fn blitLayouts() throws (testing::TestError) {
954 +
    try check(&[], &[reserve(0, P16), reserve(1, P16), blit(1, 0, P16)], nil);
955 +
    try check(&[], &[reserve(0, P16), reserve(1, P16), blit(1, 0, P8)], nil);
956 +
    try check(&[], &[reserve(0, CELL), reserve(1, CELL), blit(1, 0, CELL)], nil);
957 +
    try check(&[], &[reserve(0, LOCAL), reserve(1, CELL), blit(1, 0, CELL)], verify::Rule::View);
958 +
    try check(&[], &[reserve(0, CELL), reserve(1, P8), blit(1, 0, CELL)], nil);
959 +
    try check(&[], &[reserve(0, CELL), reserve(1, P8), blit(1, 0, P8)], verify::Rule::View);
960 +
    try check(&[], &[reserve(0, P8), reserve(1, CELL), blit(1, 0, CELL)], verify::Rule::View);
961 +
    try check(&[], &[reserve(0, P8), reserve(1, CELL), blit(1, 0, P8)], verify::Rule::View);
962 +
    try check(&[], &[reserve(0, P16), reserve(1, SLICE), blit(1, 0, P8)], verify::Rule::View);
963 +
    try checkBody(&[], il::ValType::Void, &[reserve(0, PAIR), reserve(1, PAIR), field(2, 0, 8),
964 +
        field(3, 1, 8), blit(3, 2, CELL), retVoid()], nil);
965 +
    try checkBody(&[], il::ValType::Void, &[reserve(0, PAIR), reserve(1, PAIR), field(2, 0, 8),
966 +
        field(3, 1, 8), blit(3, 2, SLICE), retVoid()], verify::Rule::View);
967 +
    try check(&[], &[reserve(0, PAIR), reserve(1, PAIR), blit(1, 0, PAIR)], nil);
968 +
    try check(&[param(0, ptrType(P16, true, false, false))], &[reserve(1, P16), blit(0, 1, P16)],
969 +
        verify::Rule::Mutability);
970 +
}
971 +
972 +
/// The copied layout must fit in both regions.
973 +
@test unsafe fn blitBounds() throws (testing::TestError) {
974 +
    try check(&[], &[reserve(0, P8), reserve(1, P16), blit(1, 0, P16)], verify::Rule::Bounds);
975 +
    try check(&[], &[reserve(0, P16), reserve(1, P8), blit(1, 0, P16)], verify::Rule::Bounds);
976 +
    try checkBody(&[], il::ValType::Void, &[reserve(0, P16), reserve(1, P16), field(2, 0, 8),
977 +
        blit(1, 2, P16), retVoid()], verify::Rule::Bounds);
978 +
    try checkBody(&[], il::ValType::Void, &[reserve(0, P16), reserve(1, P16), field(2, 1, 8),
979 +
        blit(2, 0, P8), retVoid()], nil);
980 +
}
981 +
982 +
/// Check a copy of layout `l` from `src` at offset `os` to `dst` at offset `od`.
983 +
unsafe fn blitAt(dst: u32, od: u32, src: u32, os: u32, l: u32, expected: ?verify::Rule)
984 +
    throws (testing::TestError) {
985 +
    try checkBody(&[], il::ValType::Void, &[reserve(0, src), reserve(1, dst),
986 +
        field(2, 0, os), field(3, 1, od), blit(3, 2, l), retVoid()], expected);
987 +
}
988 +
989 +
/// A copy of a plain layout starts at an offset that its alignment divides, in an object that
990 +
/// is at least as aligned.
991 +
@test unsafe fn blitAlignment() throws (testing::TestError) {
992 +
    try blitAt(P16, 8, P16, 8, P8, nil);
993 +
    try blitAt(P16, 4, P16, 4, P4, nil);
994 +
    try blitAt(P16, 4, P16, 4, P8, verify::Rule::View);
995 +
    try blitAt(P16, 4, P16, 8, P8, verify::Rule::View);
996 +
    try blitAt(P16, 8, P16, 4, P8, verify::Rule::View);
997 +
    try blitAt(P16, 2, P16, 2, P4, verify::Rule::View);
998 +
    try blitAt(P16, 1, P16, 3, P1, nil);
999 +
    try blitAt(P16, 1, P16, 1, P3, nil);
1000 +
    // An object of byte alignment holds no aligned layout.
1001 +
    try blitAt(B8, 0, B8, 0, B8, nil);
1002 +
    try blitAt(B8, 0, B8, 0, P1, nil);
1003 +
    try blitAt(B8, 0, B8, 0, P4, verify::Rule::View);
1004 +
    try blitAt(B8, 0, P8, 0, P8, verify::Rule::View);
1005 +
    try blitAt(P8, 0, B8, 0, P8, verify::Rule::View);
1006 +
    try blitAt(B8, 4, B8, 4, P4, verify::Rule::View);
1007 +
    // Slots are copied into a plain region only where an object of the layout can be.
1008 +
    try blitAt(P16, 8, CELL, 0, CELL, nil);
1009 +
    try blitAt(P16, 4, CELL, 0, CELL, verify::Rule::View);
1010 +
    try blitAt(B8, 0, CELL, 0, CELL, verify::Rule::View);
1011 +
}
1012 +
1013 +
/// A pointer to a plain layout views a region of a larger object only at an aligned offset, and
1014 +
/// only when the object is aligned at least as much.
1015 +
@test unsafe fn viewAlignment() throws (testing::TestError) {
1016 +
    let b = newBuilder();
1017 +
    let mut scratch = alloc::new(&mut SCRATCH[..]);
1018 +
    let t = try layout::build(&b.layouts[..], CONFIG, &mut scratch) catch {
1019 +
        throw testing::TestError::Failed;
1020 +
    };
1021 +
    try testing::expect(layout::view(&t, P16, 0, P8) and layout::view(&t, P16, 8, P8));
1022 +
    try testing::expect(not layout::view(&t, P16, 4, P8) and not layout::view(&t, P16, 12, P8));
1023 +
    try testing::expect(layout::view(&t, P16, 12, P4) and not layout::view(&t, P16, 10, P4));
1024 +
    try testing::expect(layout::view(&t, P16, 15, P1) and layout::view(&t, P16, 13, P3));
1025 +
    try testing::expect(layout::view(&t, B8, 0, P1) and layout::view(&t, B8, 7, P1));
1026 +
    try testing::expect(not layout::view(&t, B8, 0, P4) and not layout::view(&t, B8, 0, P8));
1027 +
    try testing::expect(layout::view(&t, B8, 0, B8) and layout::view(&t, P8, 0, P8));
1028 +
}
1029 +
1030 +
/// A copy of borrowed slots stays in the frame.
1031 +
@test unsafe fn blitReferences() throws (testing::TestError) {
1032 +
    try check(&[], &[reserve(0, LOCAL), reserve(1, LOCAL), blit(1, 0, LOCAL)], nil);
1033 +
    try check(&[param(0, ptrType(LOCAL, false, true, false))],
1034 +
        &[reserve(1, LOCAL), blit(0, 1, LOCAL)], verify::Rule::Class);
1035 +
    try check(&[param(0, ptrType(CELL, false, true, false))], &[reserve(1, CELL), blit(0, 1, CELL)],
1036 +
        nil);
1037 +
    // Plain bytes hold no pointer, so a destination of plain bytes can be anywhere.
1038 +
    try check(&[param(0, ptrType(P8, false, true, false))], &[reserve(1, LOCAL), blit(0, 1, LOCAL)],
1039 +
        nil);
1040 +
}
1041 +
1042 +
////////////////////
1043 +
// Copy and Calls //
1044 +
////////////////////
1045 +
1046 +
/// A data symbol is a pointer to its data, writable unless the data is read-only.
1047 +
@test unsafe fn dataSymbol() throws (testing::TestError) {
1048 +
    let mut writable = newBuilder();
1049 +
    addData(&mut writable, "d", P4, false, &[]);
1050 +
1051 +
    try checkIn(&mut writable, &[], il::ValType::Void,
1052 +
        &[copy(0, il::Val::DataSym("d")), store(imm(1), 0, 0), copy(1, reg(0)), load(2, 1, 0),
1053 +
            retVoid()], nil);
1054 +
    let mut readOnly = newBuilder();
1055 +
    addData(&mut readOnly, "d", P4, true, &[]);
1056 +
1057 +
    try checkIn(&mut readOnly, &[], il::ValType::Void,
1058 +
        &[copy(0, il::Val::DataSym("d")), store(imm(1), 0, 0), retVoid()],
1059 +
        verify::Rule::Mutability);
1060 +
    try check(&[], &[copy(0, il::Val::DataSym("d"))], verify::Rule::Symbol);
1061 +
    let mut asData = newBuilder();
1062 +
    addData(&mut asData, "d", P4, false, &[]);
1063 +
1064 +
    try checkIn(&mut asData, &[], il::ValType::Void,
1065 +
        &[add(0, il::Val::DataSym("d"), imm(1)), load(1, 0, 0), retVoid()], verify::Rule::Type);
1066 +
    let mut passed = newBuilder();
1067 +
    addData(&mut passed, "d", P4, false, &[]);
1068 +
1069 +
    addFn(&mut passed, "f", &[param(0, ptrType(P4, true, true, false))], il::ValType::Void,
1070 +
        &[retVoid()]);
1071 +
    let values = args(&mut passed, &[il::Val::DataSym("d")]);
1072 +
    try checkIn(&mut passed, &[], il::ValType::Void,
1073 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("f"), values), retVoid()],
1074 +
        verify::Rule::Type);
1075 +
}
1076 +
1077 +
/// Check a call from `main`, which has parameters `params`, to `f`, which has parameters
1078 +
/// `callee` and passes `values`.
1079 +
unsafe fn callCase(
1080 +
    callee: &[il::Param], params: &[il::Param], values: &[il::Val], rule: ?verify::Rule
1081 +
) throws (testing::TestError) {
1082 +
    let mut b = newBuilder();
1083 +
    addFn(&mut b, "f", callee, il::ValType::Void, &[retVoid()]);
1084 +
    let passed = args(&mut b, values);
1085 +
    try checkIn(&mut b, params, il::ValType::Void,
1086 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("f"), passed), retVoid()], rule);
1087 +
}
1088 +
1089 +
/// Arguments match the parameters of the callee.
1090 +
@test unsafe fn callArguments() throws (testing::TestError) {
1091 +
    let owned = param(0, ptrType(P4, true, true, false));
1092 +
    let callee = [owned];
1093 +
    try callCase(&callee[..], &[owned], &[reg(0)], nil);
1094 +
    try callCase(&callee[..], &[param(0, ptrType(P4, false, true, false))], &[reg(0)],
1095 +
        verify::Rule::Class);
1096 +
    try callCase(&callee[..], &[param(0, ptrType(P4, true, false, false))], &[reg(0)],
1097 +
        verify::Rule::Mutability);
1098 +
    try callCase(&callee[..], &[param(0, ptrType(P4, true, true, true))], &[reg(0)],
1099 +
        verify::Rule::Null);
1100 +
    try callCase(&callee[..], &[], &[imm(0)], verify::Rule::Null);
1101 +
    try callCase(&callee[..], &[], &[il::Val::Undef], verify::Rule::Type);
1102 +
    try callCase(&[param(0, ptrType(P4, true, true, true))], &[], &[imm(0)], nil);
1103 +
    try callCase(&callee[..], &[param(0, ptrType(CELL, true, true, false))], &[reg(0)],
1104 +
        verify::Rule::View);
1105 +
    try callCase(&callee[..], &[owned], &[reg(0), reg(0)], verify::Rule::Arity);
1106 +
    try callCase(&[param(0, dataType())], &[owned], &[reg(0)], nil);
1107 +
}
1108 +
1109 +
/// The callee is a function of the program, and the result has its type.
1110 +
@test unsafe fn callTargets() throws (testing::TestError) {
1111 +
    try check(&[], &[call(nil, il::ValType::Void, il::Val::FnAddr("missing"), none())],
1112 +
        verify::Rule::Symbol);
1113 +
    let mut external = newBuilder();
1114 +
    addExtern(&mut external, "e", &[], il::ValType::Void);
1115 +
    try checkIn(&mut external, &[], il::ValType::Void,
1116 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("e"), none()), retVoid()],
1117 +
        verify::Rule::Symbol);
1118 +
    try check(&[], &[call(nil, il::ValType::Void, imm(8), none())], verify::Rule::Call);
1119 +
    try check(&[oneData()], &[call(nil, il::ValType::Void, reg(0), none())], verify::Rule::Call);
1120 +
    let mut result = newBuilder();
1121 +
    addFn(&mut result, "f", &[], dataType(), &[ret(imm(1))]);
1122 +
    try checkIn(&mut result, &[], il::ValType::Void,
1123 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("f"), none()), retVoid()],
1124 +
        verify::Rule::Call);
1125 +
    let mut void = newBuilder();
1126 +
    addFn(&mut void, "f", &[], il::ValType::Void, &[retVoid()]);
1127 +
    try checkIn(&mut void, &[], il::ValType::Void,
1128 +
        &[call(1, il::ValType::Void, il::Val::FnAddr("f"), none()), retVoid()],
1129 +
        verify::Rule::Call);
1130 +
    let mut value = newBuilder();
1131 +
    addFn(&mut value, "f", &[], dataType(), &[ret(imm(1))]);
1132 +
    try checkIn(&mut value, &[], il::ValType::Void,
1133 +
        &[call(1, dataType(), il::Val::FnAddr("f"), none()), add(2, reg(1), imm(1)), retVoid()],
1134 +
        nil);
1135 +
    let mut discarded = newBuilder();
1136 +
    addFn(&mut discarded, "f", &[], dataType(), &[ret(imm(1))]);
1137 +
    try checkIn(&mut discarded, &[], il::ValType::Void,
1138 +
        &[call(nil, dataType(), il::Val::FnAddr("f"), none()), retVoid()], nil);
1139 +
}
1140 +
1141 +
/// A call returns a pointer of the declared type.
1142 +
@test unsafe fn callResult() throws (testing::TestError) {
1143 +
    let pointer = ptrType(P4, true, true, false);
1144 +
    let mut ok = newBuilder();
1145 +
    addFn(&mut ok, "f", &[param(0, pointer)], pointer, &[ret(reg(0))]);
1146 +
    let one = args(&mut ok, &[reg(0)]);
1147 +
    try checkIn(&mut ok, &[param(0, pointer)], il::ValType::Void,
1148 +
        &[call(1, pointer, il::Val::FnAddr("f"), one), load(2, 1, 0), retVoid()], nil);
1149 +
    let mut maybe = newBuilder();
1150 +
    addFn(&mut maybe, "f", &[param(0, pointer)], ptrType(P4, true, true, true), &[ret(reg(0))]);
1151 +
    let two = args(&mut maybe, &[reg(0)]);
1152 +
    try checkIn(&mut maybe, &[param(0, pointer)], il::ValType::Void,
1153 +
        &[call(1, ptrType(P4, true, true, true), il::Val::FnAddr("f"), two), load(2, 1, 0),
1154 +
            retVoid()], verify::Rule::Null);
1155 +
}
1156 +
1157 +
//////////////
1158 +
// Returns  //
1159 +
//////////////
1160 +
1161 +
/// A function returns the value of its return type, and only owned pointers.
1162 +
@test unsafe fn returns() throws (testing::TestError) {
1163 +
    let pointer = ptrType(P4, true, true, false);
1164 +
    try checkBody(&[param(0, pointer)], pointer, &[ret(reg(0))], nil);
1165 +
    try checkBody(&[], pointer, &[reserve(0, P4), ret(reg(0))], verify::Rule::Class);
1166 +
    try checkBody(&[param(0, ptrType(P4, false, true, false))], ptrType(P4, false, true, false),
1167 +
        &[ret(reg(0))], verify::Rule::Return);
1168 +
    try checkBody(&[param(0, ptrType(P4, true, true, true))], pointer, &[ret(reg(0))],
1169 +
        verify::Rule::Null);
1170 +
    try checkBody(&[], dataType(), &[retVoid()], verify::Rule::Return);
1171 +
    try checkBody(&[], il::ValType::Void, &[ret(imm(1))], verify::Rule::Type);
1172 +
    try checkBody(&[param(0, pointer)], dataType(), &[ret(reg(0))], nil);
1173 +
    try checkBody(&[oneData()], pointer, &[ret(reg(0))], verify::Rule::Type);
1174 +
    try checkBody(&[], ptrType(P4, true, true, true), &[ret(imm(0))], nil);
1175 +
}
1176 +
1177 +
/// Pointers to objects with borrowed slots are not owned.
1178 +
@test unsafe fn ownedLayouts() throws (testing::TestError) {
1179 +
    let mut viaParam = newBuilder();
1180 +
    addFn(&mut viaParam, "f", &[param(0, ptrType(LOCAL, true, true, false))],
1181 +
        il::ValType::Void, &[retVoid()]);
1182 +
    try rejected(&mut viaParam, verify::Rule::Layout);
1183 +
    let mut borrowed = newBuilder();
1184 +
    addFn(&mut borrowed, "f", &[param(0, ptrType(LOCAL, false, true, false))],
1185 +
        il::ValType::Void, &[retVoid()]);
1186 +
    try accepted(&mut borrowed);
1187 +
    let mut slot = newBuilder();
1188 +
    addLayout(&mut slot, 8, 8, &[ptrSlot(0, LOCAL, true, true)]);
1189 +
    try rejected(&mut slot, verify::Rule::Layout);
1190 +
    let mut nested = newBuilder();
1191 +
    let inner = addLayout(&mut nested, 8, 8, &[subSlot(0, LOCAL)]);
1192 +
    addLayout(&mut nested, 8, 8, &[ptrSlot(0, inner, true, true)]);
1193 +
    try rejected(&mut nested, verify::Rule::Layout);
1194 +
    let mut signature = newBuilder();
1195 +
    addSignature(&mut signature, &[ptrType(LOCAL, true, true, false)], il::ValType::Void);
1196 +
    try rejected(&mut signature, verify::Rule::Layout);
1197 +
}
1198 +
1199 +
/////////////////////
1200 +
// Function values //
1201 +
/////////////////////
1202 +
1203 +
/// Add the functions that the function value tests refer to: `f` takes and returns data,
1204 +
/// and `g` takes and returns nothing.
1205 +
unsafe fn addTargets(b: &mut Builder) {
1206 +
    addFn(b, "f", &[oneData()], dataType(), &[ret(reg(0))]);
1207 +
    addFn(b, "g", &[], il::ValType::Void, &[retVoid()]);
1208 +
}
1209 +
1210 +
/// A function value is called through a register that is not null, with the types of
1211 +
/// its signature.
1212 +
@test unsafe fn indirectCall() throws (testing::TestError) {
1213 +
    let mut ok = newBuilder();
1214 +
    addTargets(&mut ok);
1215 +
    let one1 = args(&mut ok, &[imm(1)]);
1216 +
    try checkIn(&mut ok, &[], il::ValType::Void,
1217 +
        &[reserve(0, FNCELL), copy(1, il::Val::FnAddr("f")), storePtr(reg(1), 0, 0),
1218 +
            loadPtr(3, 0, 0), call(4, dataType(), reg(3), one1), retVoid()], nil);
1219 +
1220 +
    let mut unchecked = newBuilder();
1221 +
    addTargets(&mut unchecked);
1222 +
    let one2 = args(&mut unchecked, &[imm(1)]);
1223 +
    try checkIn(&mut unchecked, &[], il::ValType::Void,
1224 +
        &[reserve(0, FNCELL), loadNullablePtr(2, 0, 0), call(4, dataType(), reg(2), one2),
1225 +
            retVoid()],
1226 +
        verify::Rule::Null);
1227 +
1228 +
    let mut wrongSlot = newBuilder();
1229 +
    addTargets(&mut wrongSlot);
1230 +
    try checkIn(&mut wrongSlot, &[], il::ValType::Void,
1231 +
        &[reserve(0, FNCELL), copy(1, il::Val::FnAddr("g")), storePtr(reg(1), 0, 0), retVoid()],
1232 +
        verify::Rule::Type);
1233 +
1234 +
    let mut stored = newBuilder();
1235 +
    addTargets(&mut stored);
1236 +
    try checkIn(&mut stored, &[], il::ValType::Void,
1237 +
        &[reserve(0, FNCELL1), copy(1, il::Val::FnAddr("g")), storePtr(reg(1), 0, 0), retVoid()],
1238 +
        nil);
1239 +
1240 +
    let mut direct = newBuilder();
1241 +
    addTargets(&mut direct);
1242 +
    try checkIn(&mut direct, &[], il::ValType::Void,
1243 +
        &[reserve(0, FNCELL1), storePtr(il::Val::FnAddr("g"), 0, 0), retVoid()], nil);
1244 +
1245 +
    let mut zero = newBuilder();
1246 +
    addTargets(&mut zero);
1247 +
    try checkIn(&mut zero, &[], il::ValType::Void,
1248 +
        &[reserve(0, FNCELL1), storePtr(imm(0), 0, 0), retVoid()], nil);
1249 +
1250 +
    let mut result = newBuilder();
1251 +
    addTargets(&mut result);
1252 +
    let one3 = args(&mut result, &[imm(1)]);
1253 +
    try checkIn(&mut result, &[], il::ValType::Void,
1254 +
        &[reserve(0, FNCELL), copy(1, il::Val::FnAddr("f")), storePtr(reg(1), 0, 0),
1255 +
            loadPtr(3, 0, 0), call(4, il::ValType::Void, reg(3), one3), retVoid()],
1256 +
        verify::Rule::Call);
1257 +
1258 +
    let mut count = newBuilder();
1259 +
    addTargets(&mut count);
1260 +
    try checkIn(&mut count, &[], il::ValType::Void,
1261 +
        &[reserve(0, FNCELL), copy(1, il::Val::FnAddr("f")), storePtr(reg(1), 0, 0),
1262 +
            loadPtr(3, 0, 0), call(4, dataType(), reg(3), none()), retVoid()],
1263 +
        verify::Rule::Arity);
1264 +
1265 +
    let mut forged = newBuilder();
1266 +
    addTargets(&mut forged);
1267 +
    let one4 = args(&mut forged, &[imm(1)]);
1268 +
    try checkIn(&mut forged, &[], il::ValType::Void,
1269 +
        &[reserve(0, P8), loadPtr(1, 0, 0), retVoid()], verify::Rule::Slot);
1270 +
    let _ = one4;
1271 +
}
1272 +
1273 +
/// A function value parameter has the signature of the function that is passed.
1274 +
@test unsafe fn functionArgument() throws (testing::TestError) {
1275 +
    let mut ok = newBuilder();
1276 +
    addTargets(&mut ok);
1277 +
    addFn(&mut ok, "h", &[param(0, il::ValType::Fn(SIG_DATA))], il::ValType::Void, &[retVoid()]);
1278 +
    let f = args(&mut ok, &[il::Val::FnAddr("f")]);
1279 +
    try checkIn(&mut ok, &[], il::ValType::Void,
1280 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("h"), f), retVoid()], nil);
1281 +
1282 +
    let mut wrong = newBuilder();
1283 +
    addTargets(&mut wrong);
1284 +
    addFn(&mut wrong, "h", &[param(0, il::ValType::Fn(SIG_DATA))], il::ValType::Void, &[retVoid()]);
1285 +
    let g = args(&mut wrong, &[il::Val::FnAddr("g")]);
1286 +
    try checkIn(&mut wrong, &[], il::ValType::Void,
1287 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("h"), g), retVoid()], verify::Rule::Type);
1288 +
1289 +
    let mut loaded = newBuilder();
1290 +
    addTargets(&mut loaded);
1291 +
    addFn(&mut loaded, "h", &[param(0, il::ValType::Fn(SIG_DATA))], il::ValType::Void,
1292 +
        &[retVoid()]);
1293 +
    let value = args(&mut loaded, &[reg(2)]);
1294 +
    try checkIn(&mut loaded, &[], il::ValType::Void,
1295 +
        &[reserve(0, FNCELL), loadNullablePtr(2, 0, 0),
1296 +
            call(nil, il::ValType::Void, il::Val::FnAddr("h"), value), retVoid()],
1297 +
        verify::Rule::Null);
1298 +
1299 +
    let mut number = newBuilder();
1300 +
    addTargets(&mut number);
1301 +
    addFn(&mut number, "h", &[param(0, il::ValType::Fn(SIG_DATA))], il::ValType::Void,
1302 +
        &[retVoid()]);
1303 +
    let zero = args(&mut number, &[imm(0)]);
1304 +
    try checkIn(&mut number, &[], il::ValType::Void,
1305 +
        &[call(nil, il::ValType::Void, il::Val::FnAddr("h"), zero), retVoid()], verify::Rule::Type);
1306 +
}
1307 +
1308 +
////////////
1309 +
// Symbols //
1310 +
////////////
1311 +
1312 +
/// Symbols are non-empty and unique across functions and data.
1313 +
@test unsafe fn symbolNames() throws (testing::TestError) {
1314 +
    let mut twice = newBuilder();
1315 +
    addFn(&mut twice, "f", &[], il::ValType::Void, &[retVoid()]);
1316 +
    addFn(&mut twice, "f", &[], il::ValType::Void, &[retVoid()]);
1317 +
    try rejected(&mut twice, verify::Rule::Symbol);
1318 +
    let mut empty = newBuilder();
1319 +
    addFn(&mut empty, "", &[], il::ValType::Void, &[retVoid()]);
1320 +
    try rejected(&mut empty, verify::Rule::Symbol);
1321 +
    let mut shared = newBuilder();
1322 +
    addFn(&mut shared, "f", &[], il::ValType::Void, &[retVoid()]);
1323 +
    addData(&mut shared, "f", P4, true, &[]);
1324 +
    try rejected(&mut shared, verify::Rule::Symbol);
1325 +
    let mut dataTwice = newBuilder();
1326 +
    addData(&mut dataTwice, "d", P4, true, &[]);
1327 +
    addData(&mut dataTwice, "d", P4, true, &[]);
1328 +
1329 +
    try rejected(&mut dataTwice, verify::Rule::Symbol);
1330 +
    let mut ok = newBuilder();
1331 +
    addFn(&mut ok, "f", &[], il::ValType::Void, &[retVoid()]);
1332 +
    addData(&mut ok, "d", P4, true, &[]);
1333 +
    try accepted(&mut ok);
1334 +
}
1335 +
1336 +
/// A function that is declared extern has no body, and no call or address refers to it.
1337 +
@test unsafe fn externFunctions() throws (testing::TestError) {
1338 +
    let mut ok = newBuilder();
1339 +
    addExtern(&mut ok, "e", &[oneData()], dataType());
1340 +
    try accepted(&mut ok);
1341 +
    let mut address = newBuilder();
1342 +
    addExtern(&mut address, "e", &[], il::ValType::Void);
1343 +
    try checkIn(&mut address, &[], il::ValType::Void,
1344 +
        &[copy(0, il::Val::FnAddr("e")), retVoid()], verify::Rule::Symbol);
1345 +
}
1346 +
1347 +
////////////////////////
1348 +
// Control flow edges //
1349 +
////////////////////////
1350 +
1351 +
/// A switch passes arguments to every target.
1352 +
@test unsafe fn switchArguments() throws (testing::TestError) {
1353 +
    let mut b = newBuilder();
1354 +
    let one = args(&mut b, &[imm(1)]);
1355 +
    let two = args(&mut b, &[imm(2)]);
1356 +
    let sw = il::Instr::Switch {
1357 +
        val: reg(0), defaultTarget: 1, defaultArgs: one, cases: addCase(&mut b, 3, 2, two),
1358 +
    };
1359 +
    let blocks = [
1360 +
        block(&mut b, &[], &[sw]),
1361 +
        block(&mut b, &[param(1, dataType())], &[retVoid()]),
1362 +
        block(&mut b, &[param(2, dataType())], &[retVoid()]),
1363 +
    ];
1364 +
    addBlocks(&mut b, "main", &[oneData()], il::ValType::Void, &blocks[..]);
1365 +
    try accepted(&mut b);
1366 +
1367 +
    let mut bad = newBuilder();
1368 +
    let first = args(&mut bad, &[imm(1)]);
1369 +
    let swBad = il::Instr::Switch {
1370 +
        val: reg(0), defaultTarget: 1, defaultArgs: first, cases: addCase(&mut bad, 3, 2, none()),
1371 +
    };
1372 +
    let blocksBad = [
1373 +
        block(&mut bad, &[], &[swBad]),
1374 +
        block(&mut bad, &[param(1, dataType())], &[retVoid()]),
1375 +
        block(&mut bad, &[param(2, dataType())], &[retVoid()]),
1376 +
    ];
1377 +
    addBlocks(&mut bad, "main", &[oneData()], il::ValType::Void, &blocksBad[..]);
1378 +
    try rejected(&mut bad, verify::Rule::Arity);
1379 +
}
1380 +
1381 +
/////////////////
1382 +
// Data        //
1383 +
/////////////////
1384 +
1385 +
/// A data item of a typed number.
1386 +
fn number(typ: il::Type, val: i64) -> il::DataValue {
1387 +
    return il::DataValue { item: il::DataItem::Val { typ, val }, count: 1 };
1388 +
}
1389 +
1390 +
/// A data item of the address of a symbol.
1391 +
fn symbol(name: *[u8]) -> il::DataValue {
1392 +
    return il::DataValue { item: il::DataItem::Sym(name), count: 1 };
1393 +
}
1394 +
1395 +
/// A data item of the address of a function.
1396 +
fn function(name: *[u8]) -> il::DataValue {
1397 +
    return il::DataValue { item: il::DataItem::Fn(name), count: 1 };
1398 +
}
1399 +
1400 +
/// A data item repeated `count` times.
1401 +
fn repeat(item: il::DataItem, count: u32) -> il::DataValue {
1402 +
    return il::DataValue { item, count };
1403 +
}
1404 +
1405 +
/// Check the program that holds only the data "d" of `layout` with the initializer `values`:
1406 +
/// it is accepted when `rule` is nil, or rejected for violating `rule`.
1407 +
unsafe fn dataCase(layout: u32, readOnly: bool, values: &[il::DataValue], rule: ?verify::Rule)
1408 +
    throws (testing::TestError)
1409 +
{
1410 +
    let mut b = newBuilder();
1411 +
    addData(&mut b, "d", layout, readOnly, values);
1412 +
    try expect(&mut b, rule);
1413 +
}
1414 +
1415 +
/// Check as [`dataCase`] the program in which data `target` of layout `targetLayout` precedes
1416 +
/// "d". The data `target` is read-only when `targetReadOnly` is set.
1417 +
unsafe fn dataCaseAfter(
1418 +
    target: *[u8], targetLayout: u32, targetReadOnly: bool, layout: u32, readOnly: bool,
1419 +
    values: &[il::DataValue], rule: ?verify::Rule
1420 +
) throws (testing::TestError) {
1421 +
    let mut b = newBuilder();
1422 +
    addData(&mut b, target, targetLayout, targetReadOnly, &[]);
1423 +
    addData(&mut b, "d", layout, readOnly, values);
1424 +
    try expect(&mut b, rule);
1425 +
}
1426 +
1427 +
/// A slice slot that is initialized to point to `target` with a length.
1428 +
@test unsafe fn sliceData() throws (testing::TestError) {
1429 +
    try dataCaseAfter("bytes", P16, true, SLICEC, true,
1430 +
        &[symbol("bytes"), number(il::Type::W32, 4), number(il::Type::W32, 16)], nil);
1431 +
    try dataCaseAfter("bytes", P16, true, SLICEC, true,
1432 +
        &[symbol("bytes"), number(il::Type::W32, 16), number(il::Type::W32, 16)], nil);
1433 +
    try dataCaseAfter("bytes", P16, true, SLICEC, true,
1434 +
        &[symbol("bytes"), number(il::Type::W32, 17), number(il::Type::W32, 17)],
1435 +
        verify::Rule::Data);
1436 +
    try dataCase(SLICEC, true, &[number(il::Type::W64, 0), number(il::Type::W32, 4)],
1437 +
        verify::Rule::Data);
1438 +
    try dataCase(SLICEC, true, &[number(il::Type::W64, 0), number(il::Type::W64, 0)], nil);
1439 +
    try dataCase(SLICEC, true, &[number(il::Type::W64, 4), number(il::Type::W64, 0)],
1440 +
        verify::Rule::Data);
1441 +
    try dataCaseAfter("bytes", P16, true, SLICEC, true,
1442 +
        &[symbol("bytes"), number(il::Type::W64, 4)], verify::Rule::Data);
1443 +
    try dataCaseAfter("bytes", P16, true, SLICE, true,
1444 +
        &[symbol("bytes"), number(il::Type::W32, 4), number(il::Type::W32, 4)], verify::Rule::Data);
1445 +
    try dataCaseAfter("bytes", P16, false, SLICE, true,
1446 +
        &[symbol("bytes"), number(il::Type::W32, 4), number(il::Type::W32, 4)], nil);
1447 +
}
1448 +
1449 +
/// Writable data holds no slices, because a slice is two words that another context
1450 +
/// can overwrite one at a time. Read-only data holds no borrowed slots.
1451 +
@test unsafe fn dataSlots() throws (testing::TestError) {
1452 +
    try dataCase(SLICE, false, &[], verify::Rule::Data);
1453 +
    try dataCase(CELL, false, &[], nil);
1454 +
    try dataCase(LOCAL, true, &[], verify::Rule::Data);
1455 +
    try dataCase(FNCELL, false, &[], nil);
1456 +
    try dataCase(PAIR, false, &[], verify::Rule::Data);
1457 +
}
1458 +
1459 +
/// A pointer slot starts as zero, or as the address of data that has its layout.
1460 +
@test unsafe fn pointerData() throws (testing::TestError) {
1461 +
    try dataCaseAfter("t", P4, true, CELLC, true, &[symbol("t")], nil);
1462 +
    try dataCaseAfter("t", P4, true, CELL, false, &[symbol("t")], verify::Rule::Data);
1463 +
    try dataCaseAfter("t", P4, false, CELL, false, &[symbol("t")], nil);
1464 +
    try dataCaseAfter("t", CELL, true, CELLC, true, &[symbol("t")], verify::Rule::Data);
1465 +
    try dataCase(CELLC, true, &[symbol("t")], verify::Rule::Symbol);
1466 +
    try dataCase(CELLC, true, &[number(il::Type::W64, 5)], verify::Rule::Data);
1467 +
    try dataCase(CELLC, true, &[number(il::Type::W8, 1), repeat(il::DataItem::Undef, 7)],
1468 +
        verify::Rule::Data);
1469 +
    try dataCase(CELLC, true, &[number(il::Type::W32, 0), number(il::Type::W32, 0)], nil);
1470 +
    try dataCase(CELLC, true, &[repeat(il::DataItem::Undef, 8)], nil);
1471 +
    try dataCaseAfter("t", P4, true, CELLC, true, &[number(il::Type::W32, 0), symbol("t")],
1472 +
        verify::Rule::Data);
1473 +
    let mut callable = newBuilder();
1474 +
    addFn(&mut callable, "f", &[], il::ValType::Void, &[retVoid()]);
1475 +
    addData(&mut callable, "d", CELLC, true, &[function("f")]);
1476 +
    try rejected(&mut callable, verify::Rule::Data);
1477 +
}
1478 +
1479 +
/// Items outside slots are free, but no item runs from plain bytes into a slot.
1480 +
@test unsafe fn dataAroundSlots() throws (testing::TestError) {
1481 +
    try dataCaseAfter("t", P4, false, PAIR, true,
1482 +
        &[number(il::Type::W64, 5), symbol("t"), number(il::Type::W64, 0),
1483 +
            number(il::Type::W32, 0), number(il::Type::W32, 7)], nil);
1484 +
    try dataCase(PAIR, true, &[number(il::Type::W32, 0), number(il::Type::W64, 5)],
1485 +
        verify::Rule::Data);
1486 +
    try dataCase(P3, true, &[il::DataValue { item: il::DataItem::Str("abcd"), count: 1 }],
1487 +
        verify::Rule::Data);
1488 +
    try dataCase(P3, true, &[il::DataValue { item: il::DataItem::Str("abc"), count: 1 }], nil);
1489 +
    try dataCase(PAIR, true, &[
1490 +
        il::DataValue { item: il::DataItem::Str("abc"), count: 1 }, repeat(il::DataItem::Undef, 5),
1491 +
        il::DataValue { item: il::DataItem::Str("abcdefgh"), count: 1 },
1492 +
    ], verify::Rule::Data);
1493 +
    try dataCase(CELLS, true, &[repeat(il::DataItem::Val { typ: il::Type::W64, val: 0 }, 3)], nil);
1494 +
    try dataCase(CELLS, true, &[number(il::Type::W64, 0), number(il::Type::W64, 9)],
1495 +
        verify::Rule::Data);
1496 +
    try dataCase(P8, true, &[symbol("missing")], verify::Rule::Symbol);
1497 +
    try dataCaseAfter("t", P4, true, P8, true, &[symbol("t")], nil);
1498 +
    let mut size = newBuilder();
1499 +
    addData(&mut size, "d", P8, true, &[]);
1500 +
    set size.data[0].size = 9;
1501 +
    try rejected(&mut size, verify::Rule::Data);
1502 +
}
1503 +
1504 +
/// A function slot starts as zero, or as a function with the signature of the slot.
1505 +
@test unsafe fn functionData() throws (testing::TestError) {
1506 +
    let mut ok = newBuilder();
1507 +
    addTargets(&mut ok);
1508 +
    addData(&mut ok, "d", FNCELL, true, &[function("f")]);
1509 +
    try accepted(&mut ok);
1510 +
    let mut wrong = newBuilder();
1511 +
    addTargets(&mut wrong);
1512 +
    addData(&mut wrong, "d", FNCELL, true, &[function("g")]);
1513 +
    try rejected(&mut wrong, verify::Rule::Data);
1514 +
    try dataCase(FNCELL, true, &[function("f")], verify::Rule::Symbol);
1515 +
    let mut external = newBuilder();
1516 +
    addExtern(&mut external, "e", &[oneData()], dataType());
1517 +
    addData(&mut external, "d", FNCELL, true, &[function("e")]);
1518 +
    try rejected(&mut external, verify::Rule::Symbol);
1519 +
    try dataCase(FNCELL, true, &[number(il::Type::W64, 0)], nil);
1520 +
    try dataCase(FNCELL, true, &[number(il::Type::W64, 8)], verify::Rule::Data);
1521 +
}
1522 +
1523 +
////////////////////
1524 +
// Layout tables  //
1525 +
////////////////////
1526 +
1527 +
/// Layouts stay within the limits of nesting and size.
1528 +
@test unsafe fn layoutLimits() throws (testing::TestError) {
1529 +
    let mut deep = newBuilder();
1530 +
    let mut inner = CELL;
1531 +
    for _ in 0..4 {
1532 +
        set inner = addLayout(&mut deep, 8, 8, &[subSlot(0, inner)]);
1533 +
    }
1534 +
    try accepted(&mut deep);
1535 +
    let mut deeper = newBuilder();
1536 +
    let mut outer = CELL;
1537 +
    for _ in 0..5 {
1538 +
        set outer = addLayout(&mut deeper, 8, 8, &[subSlot(0, outer)]);
1539 +
    }
1540 +
    try rejected(&mut deeper, verify::Rule::Limit);
1541 +
    let mut large = newBuilder();
1542 +
    addLayout(&mut large, 4096, 8, &[]);
1543 +
    try accepted(&mut large);
1544 +
    let mut larger = newBuilder();
1545 +
    addLayout(&mut larger, 4097, 8, &[]);
1546 +
    try rejected(&mut larger, verify::Rule::Limit);
1547 +
    let mut forward = newBuilder();
1548 +
    addLayout(&mut forward, 8, 8, &[subSlot(0, 99)]);
1549 +
    try rejected(&mut forward, verify::Rule::Layout);
1550 +
}
1551 +
1552 +
/// An object in a frame has the alignment of the stack at most.
1553 +
@test unsafe fn reserveAlignment() throws (testing::TestError) {
1554 +
    let mut ok = newBuilder();
1555 +
    let wide = addLayout(&mut ok, 16, 16, &[]);
1556 +
    try checkIn(&mut ok, &[], il::ValType::Void, &[reserve(0, wide), retVoid()], nil);
1557 +
    let mut over = newBuilder();
1558 +
    let wider = addLayout(&mut over, 16, 32, &[]);
1559 +
    try checkIn(&mut over, &[], il::ValType::Void, &[reserve(0, wider), retVoid()],
1560 +
        verify::Rule::Limit);
1561 +
}
1562 +
1563 +
//////////////
1564 +
// Packages //
1565 +
//////////////
1566 +
1567 +
/// Verify the program as a package.
1568 +
unsafe fn packageVerdict(
1569 +
    b: &mut Builder, dependencies: *[*[u8]], entry: ?*[u8], exports: &[binary::Export]
1570 +
) -> ?verify::Error {
1571 +
    let mut owned: *mut [binary::Export] = &mut [];
1572 +
    try! owned.extend(exports, &mut b.arena);
1573 +
    let mut package = binary::Package {
1574 +
        symbols: &[], name: "p", dependencies, exports: &owned[..], entry, program: program(b),
1575 +
    };
1576 +
    let mut scratch = alloc::new(&mut SCRATCH[..]);
1577 +
    let mut keep = alloc::new(&mut KEEP[..]);
1578 +
    try verify::verifyPackage(&mut package, CONFIG, &mut scratch, &mut keep) catch err {
1579 +
        return err;
1580 +
    };
1581 +
    set EXPORTED = package.exports.len;
1582 +
    return nil;
1583 +
}
1584 +
1585 +
/// Number of exports that the last accepted package kept.
1586 +
static EXPORTED: u32 = 0;
1587 +
1588 +
/// Check that the package is rejected for violating the package rules.
1589 +
unsafe fn packageRejected(
1590 +
    b: &mut Builder, dependencies: *[*[u8]], entry: ?*[u8], exports: &[binary::Export]
1591 +
) throws (testing::TestError) {
1592 +
    let err = packageVerdict(b, dependencies, entry, exports) else {
1593 +
        throw testing::TestError::Failed;
1594 +
    };
1595 +
    try testing::expect(err.rule == verify::Rule::Package);
1596 +
}
1597 +
1598 +
/// A package has no dependencies, and no extern functions.
1599 +
@test unsafe fn packageIsSelfContained() throws (testing::TestError) {
1600 +
    let mut ok = newBuilder();
1601 +
    addFn(&mut ok, "f", &[], il::ValType::Void, &[retVoid()]);
1602 +
    try testing::expect(packageVerdict(&mut ok, &[], nil, &[]) == nil);
1603 +
    let mut dependent = newBuilder();
1604 +
    addFn(&mut dependent, "f", &[], il::ValType::Void, &[retVoid()]);
1605 +
    try packageRejected(&mut dependent, &["std"], nil, &[]);
1606 +
    let mut external = newBuilder();
1607 +
    addExtern(&mut external, "e", &[], il::ValType::Void);
1608 +
    try packageRejected(&mut external, &[], nil, &[]);
1609 +
}
1610 +
1611 +
/// Check as a package the program with the entry function "entry", which takes `params`. The
1612 +
/// package is accepted when `rule` is nil, and otherwise rejected.
1613 +
unsafe fn entryCase(b: &mut Builder, params: &[il::Param], rule: ?verify::Rule)
1614 +
    throws (testing::TestError)
1615 +
{
1616 +
    addFn(b, "entry", params, il::ValType::Void, &[retVoid()]);
1617 +
    if let _ = rule {
1618 +
        try packageRejected(b, &[], "entry", &[]);
1619 +
    } else {
1620 +
        try testing::expect(packageVerdict(b, &[], "entry", &[]) == nil);
1621 +
    }
1622 +
}
1623 +
1624 +
/// The entry takes the Env record by a pointer that cannot be written or null.
1625 +
@test unsafe fn packageEntry() throws (testing::TestError) {
1626 +
    let env = param(0, ptrType(P16, true, false, false));
1627 +
    let mut ok = newBuilder();
1628 +
    try entryCase(&mut ok, &[env], nil);
1629 +
    let mut missing = newBuilder();
1630 +
    addFn(&mut missing, "entry", &[env], il::ValType::Void, &[retVoid()]);
1631 +
    try packageRejected(&mut missing, &[], "other", &[]);
1632 +
    let rule = verify::Rule::Package;
1633 +
    let mut none = newBuilder();
1634 +
    try entryCase(&mut none, &[], nil);
1635 +
    let mut two = newBuilder();
1636 +
    try entryCase(&mut two, &[env, param(1, ptrType(P16, true, false, false))], rule);
1637 +
    let mut data = newBuilder();
1638 +
    try entryCase(&mut data, &[oneData()], rule);
1639 +
    let mut writable = newBuilder();
1640 +
    try entryCase(&mut writable, &[param(0, ptrType(P16, true, true, false))], rule);
1641 +
    let mut nullable = newBuilder();
1642 +
    try entryCase(&mut nullable, &[param(0, ptrType(P16, true, false, true))], rule);
1643 +
    let mut borrowed = newBuilder();
1644 +
    try entryCase(&mut borrowed, &[param(0, ptrType(P16, false, false, false))], rule);
1645 +
    let mut slots = newBuilder();
1646 +
    try entryCase(&mut slots, &[param(0, ptrType(CELL, true, false, false))], rule);
1647 +
    let mut large = newBuilder();
1648 +
    let big = addLayout(&mut large, 33, 1, &[]);
1649 +
    try entryCase(&mut large, &[param(0, ptrType(big, true, false, false))], rule);
1650 +
    let mut exact = newBuilder();
1651 +
    let fits = addLayout(&mut exact, 32, 1, &[]);
1652 +
    try entryCase(&mut exact, &[param(0, ptrType(fits, true, false, false))], nil);
1653 +
}
1654 +
1655 +
/// Only a function that takes at most two data arguments and returns data stays exported, so
1656 +
/// that a context starts at it with plain arguments. Other exported functions are accepted, and
1657 +
/// dropped from the exports.
1658 +
@test unsafe fn packageExports() throws (testing::TestError) {
1659 +
    let function = binary::Export { name: "f", kind: binary::ExportKind::Function };
1660 +
    let mut ok = newBuilder();
1661 +
    addFn(&mut ok, "f", &[oneData()], dataType(), &[ret(reg(0))]);
1662 +
    try testing::expect(packageVerdict(&mut ok, &[], nil, &[function]) == nil);
1663 +
    try testing::expect(EXPORTED == 1);
1664 +
    let mut two = newBuilder();
1665 +
    addFn(&mut two, "f", &[oneData(), param(1, dataType())], dataType(), &[ret(reg(0))]);
1666 +
    try testing::expect(packageVerdict(&mut two, &[], nil, &[function]) == nil);
1667 +
    try testing::expect(EXPORTED == 1);
1668 +
    let mut three = newBuilder();
1669 +
    addFn(&mut three, "f", &[oneData(), param(1, dataType()), param(2, dataType())], dataType(),
1670 +
        &[ret(reg(0))]);
1671 +
    try testing::expect(packageVerdict(&mut three, &[], nil, &[function]) == nil);
1672 +
    try testing::expect(EXPORTED == 0);
1673 +
    let mut pointer = newBuilder();
1674 +
    addFn(&mut pointer, "f", &[param(0, ptrType(P4, true, true, false))], il::ValType::Void,
1675 +
        &[retVoid()]);
1676 +
    try testing::expect(packageVerdict(&mut pointer, &[], nil, &[function]) == nil);
1677 +
    try testing::expect(EXPORTED == 0);
1678 +
    let mut result = newBuilder();
1679 +
    addFn(&mut result, "f", &[param(0, ptrType(P4, true, true, false))],
1680 +
        ptrType(P4, true, true, false), &[ret(reg(0))]);
1681 +
    try testing::expect(packageVerdict(&mut result, &[], nil, &[function]) == nil);
1682 +
    try testing::expect(EXPORTED == 0);
1683 +
    let mut callback = newBuilder();
1684 +
    addFn(&mut callback, "f", &[param(0, il::ValType::Fn(SIG_DATA))], il::ValType::Void,
1685 +
        &[retVoid()]);
1686 +
    try testing::expect(packageVerdict(&mut callback, &[], nil, &[function]) == nil);
1687 +
    try testing::expect(EXPORTED == 0);
1688 +
    let mut missing = newBuilder();
1689 +
    try packageRejected(&mut missing, &[], nil, &[function]);
1690 +
    let env = param(0, ptrType(P16, true, false, false));
1691 +
    let entry = binary::Export { name: "entry", kind: binary::ExportKind::Function };
1692 +
    let mut exportedEntry = newBuilder();
1693 +
    addFn(&mut exportedEntry, "entry", &[env], il::ValType::Void, &[retVoid()]);
1694 +
    try testing::expect(packageVerdict(&mut exportedEntry, &[], "entry", &[entry]) == nil);
1695 +
    try testing::expect(EXPORTED == 1);
1696 +
    let mut data = newBuilder();
1697 +
    addData(&mut data, "d", P4, true, &[]);
1698 +
1699 +
    let item = binary::Export { name: "d", kind: binary::ExportKind::Data };
1700 +
    try testing::expect(packageVerdict(&mut data, &[], nil, &[item]) == nil);
1701 +
    let mut absent = newBuilder();
1702 +
    try packageRejected(&mut absent, &[], nil, &[item]);
1703 +
}
1704 +
1705 +
/// Plain queries on arrays nested to the depth limit. Each level holds two elements of the
1706 +
/// level below, which has a pointer at its upper half, so that every query is answered along
1707 +
/// one path of the table.
1708 +
@test unsafe fn plainBytesInNestedArrays() throws (testing::TestError) {
1709 +
    let depth: u32 = 16;
1710 +
    let config = verify::Config {
1711 +
        registers: 64, blocks: 16, layoutSize: 1048576, layoutDepth: depth, params: 8, envSize: 32,
1712 +
    };
1713 +
    let mut b = newBuilder();
1714 +
    // 16 bytes: plain, then a pointer at offset 8.
1715 +
    let leaf = addLayout(&mut b, 16, 8, &[ptrSlot(8, P4, true, true)]);
1716 +
    let mut top = leaf;
1717 +
    let mut width: u32 = 16;
1718 +
    for _ in 0..depth {
1719 +
        set width *= 2;
1720 +
        set top = addLayout(&mut b, width, 8, &[il::Slot { offset: 0,
1721 +
            kind: il::SlotKind::Array { layout: top, count: 2 } }]);
1722 +
    }
1723 +
    let mut scratch = alloc::new(&mut SCRATCH[..]);
1724 +
    let t = try layout::build(&b.layouts[..], config, &mut scratch) catch {
1725 +
        throw testing::TestError::Failed;
1726 +
    };
1727 +
    let total = layout::size(&t, top);
1728 +
    try testing::expect(total == 1048576);
1729 +
    try testing::expect(layout::plain(&t, top, 0, 8));
1730 +
    try testing::expect(not layout::plain(&t, top, 0, 9));
1731 +
    try testing::expect(not layout::plain(&t, top, 8, 16));
1732 +
    try testing::expect(layout::plain(&t, top, 16, 24));
1733 +
    try testing::expect(not layout::plain(&t, top, 15, 24));
1734 +
    try testing::expect(layout::plain(&t, top, total - 16, total - 8));
1735 +
    try testing::expect(not layout::plain(&t, top, total - 16, total - 7));
1736 +
    try testing::expect(not layout::plain(&t, top, 0, total));
1737 +
    try testing::expect(layout::plain(&t, top, 5, 5));
1738 +
    try testing::expect(layout::plain(&t, top, total, total + 8));
1739 +
    // A range that spans elements ends at the first pointer.
1740 +
    try testing::expect(layout::plain(&t, top, 16 * 1000, 16 * 1000 + 8));
1741 +
    try testing::expect(not layout::plain(&t, top, 16 * 1000, 16 * 1001));
1742 +
}
1743 +
1744 +
/// The capacity of a slice is plain, also inside an array of slices.
1745 +
@test unsafe fn plainBytesOfSlices() throws (testing::TestError) {
1746 +
    let mut b = newBuilder();
1747 +
    let pair = addLayout(&mut b, 32, 8, &[il::Slot { offset: 0,
1748 +
        kind: il::SlotKind::Array { layout: SLICE, count: 2 } }]);
1749 +
    let mut scratch = alloc::new(&mut SCRATCH[..]);
1750 +
    let t = try layout::build(&b.layouts[..], CONFIG, &mut scratch) catch {
1751 +
        throw testing::TestError::Failed;
1752 +
    };
1753 +
    try testing::expect(layout::plain(&t, pair, 12, 16));
1754 +
    try testing::expect(not layout::plain(&t, pair, 11, 16));
1755 +
    try testing::expect(not layout::plain(&t, pair, 12, 17));
1756 +
    try testing::expect(layout::plain(&t, pair, 28, 32));
1757 +
    try testing::expect(layout::plain(&t, SLICE, 12, 16));
1758 +
}
1759 +
1760 +
/////////////
1761 +
// Errors  //
1762 +
/////////////
1763 +
1764 +
/// An error names the function, block and instruction.
1765 +
@test unsafe fn errorPlace() throws (testing::TestError) {
1766 +
    let mut b = newBuilder();
1767 +
    addFn(&mut b, "f", &[], il::ValType::Void, &[retVoid()]);
1768 +
    let blocks = [
1769 +
        block(&mut b, &[], &[jmp(1, none())]),
1770 +
        block(&mut b, &[], &[copy(0, imm(1)), load(1, 0, 0), retVoid()]),
1771 +
    ];
1772 +
    addBlocks(&mut b, "g", &[], il::ValType::Void, &blocks[..]);
1773 +
    let err = verdict(&mut b) else {
1774 +
        throw testing::TestError::Failed;
1775 +
    };
1776 +
    try testing::expect(err.rule == verify::Rule::Type);
1777 +
    let case verify::Place::Instr { func, block, instr } = err.place else {
1778 +
        throw testing::TestError::Failed;
1779 +
    };
1780 +
    try testing::expect(func == 1 and block == 1 and instr == 1);
1781 +
}
1782 +
1783 +
/// A scratch arena that is too small is reported, and not a panic.
1784 +
@test unsafe fn scratchExhausted() throws (testing::TestError) {
1785 +
    let mut b = newBuilder();
1786 +
    addFn(&mut b, "f", &[], il::ValType::Void, &[retVoid()]);
1787 +
    let prog = program(&mut b);
1788 +
    for size in 0..64 {
1789 +
        let mut scratch = alloc::new(&mut SCRATCH[..size]);
1790 +
        try verify::verifyProgram(&prog, CONFIG, &mut scratch) catch err {
1791 +
            try testing::expect(err.rule == verify::Rule::Storage);
1792 +
            continue;
1793 +
        };
1794 +
        // The program fits, and so does any larger arena.
1795 +
        try testing::expect(size >= 32);
1796 +
        return;
1797 +
    }
1798 +
}
1799 +
1800 +
////////////////////////////
1801 +
// Ecall buffer, page.slice //
1802 +
////////////////////////////
1803 +
1804 +
/// An environment call of operation 1 with the given buffer.
1805 +
fn ecall(dst: u32, buf: ?il::EcallBuf) -> il::Instr {
1806 +
    return il::Instr::Ecall {
1807 +
        dst: il::Reg { n: dst }, num: imm(1), a0: imm(0), a1: imm(0), a2: imm(0), a3: imm(0), buf,
1808 +
    };
1809 +
}
1810 +
1811 +
/// A buffer of `size` bytes at register `n`.
1812 +
fn buffer(n: u32, size: u32) -> ?il::EcallBuf {
1813 +
    return il::EcallBuf { ptr: il::Reg { n }, size };
1814 +
}
1815 +
1816 +
/// A page access of the handle in register 0, into the slice slot at register `slot`.
1817 +
fn pageSlice(err: u32, slot: u32, write: bool, layout: u32) -> il::Instr {
1818 +
    return il::Instr::PageSlice {
1819 +
        err: il::Reg { n: err }, slot: il::Reg { n: slot }, handle: reg(0), write, layout,
1820 +
    };
1821 +
}
1822 +
1823 +
/// The kernel writes only the buffer, which is plain writable memory of the caller.
1824 +
@test unsafe fn ecallBuffer() throws (testing::TestError) {
1825 +
    try check(&[], &[ecall(0, nil)], nil);
1826 +
    try check(&[], &[reserve(0, P16), ecall(1, buffer(0, 16))], nil);
1827 +
    try check(&[], &[reserve(0, PAIR), field(1, 0, 0), ecall(2, buffer(1, 8))], nil);
1828 +
    try check(&[param(0, ptrType(P16, true, false, false))], &[ecall(1, buffer(0, 16))],
1829 +
        verify::Rule::Mutability);
1830 +
    try check(&[], &[reserve(0, CELL), ecall(1, buffer(0, 8))], verify::Rule::Slot);
1831 +
    try check(&[], &[reserve(0, SLICE), ecall(1, buffer(0, 12))], verify::Rule::Slot);
1832 +
    try check(&[], &[reserve(0, SLICE), field(1, 0, 12), ecall(2, buffer(1, 4))], nil);
1833 +
    try check(&[], &[reserve(0, P16), ecall(1, buffer(0, 17))], verify::Rule::Bounds);
1834 +
    try check(&[param(0, ptrType(P16, true, true, true))], &[ecall(1, buffer(0, 16))],
1835 +
        verify::Rule::Null);
1836 +
    try check(&[oneData()], &[ecall(1, buffer(0, 16))], verify::Rule::Type);
1837 +
}
1838 +
1839 +
/// A page access fills an owned slice slot of plain elements.
1840 +
@test unsafe fn pageSliceSlots() throws (testing::TestError) {
1841 +
    let handle = [oneData()];
1842 +
    try check(&handle[..], &[reserve(1, SLICE), pageSlice(2, 1, true, P1)], nil);
1843 +
    try check(&handle[..], &[reserve(1, SLICEC), pageSlice(2, 1, false, P1)], nil);
1844 +
    try check(&handle[..], &[reserve(1, SLICEC), pageSlice(2, 1, true, P1)],
1845 +
        verify::Rule::Mutability);
1846 +
    try check(&handle[..], &[reserve(1, SLICE), pageSlice(2, 1, false, P1)],
1847 +
        verify::Rule::Mutability);
1848 +
    try check(&handle[..], &[reserve(1, BORROW), pageSlice(2, 1, true, P1)], verify::Rule::Class);
1849 +
    try check(&handle[..], &[reserve(1, P16), pageSlice(2, 1, true, P1)], verify::Rule::Slot);
1850 +
    try check(&handle[..], &[reserve(1, SLICE), pageSlice(2, 1, true, P4)], verify::Rule::View);
1851 +
    let mut readOnlyDestination = newBuilder();
1852 +
    try checkIn(&mut readOnlyDestination,
1853 +
        &[oneData(), param(1, ptrType(SLICE, false, false, false))], il::ValType::Void,
1854 +
        &[pageSlice(2, 1, true, P1), retVoid()], verify::Rule::Mutability);
1855 +
    try check(&handle[..], &[pageSlice(2, 0, true, P1)], verify::Rule::Type);
1856 +
}
1857 +
1858 +
/// The elements of a page are plain data: a pointer cannot be put in page memory.
1859 +
@test unsafe fn pageSliceElements() throws (testing::TestError) {
1860 +
    let handle = [oneData()];
1861 +
    let slotted = [param(0, dataType())];
1862 +
    let mut b = newBuilder();
1863 +
    let cells = addLayout(&mut b, 16, 8, &[sliceSlot(0, CELL, true, true)]);
1864 +
    try checkIn(&mut b, &slotted[..], il::ValType::Void,
1865 +
        &[reserve(1, cells), pageSlice(2, 1, true, CELL), retVoid()], verify::Rule::View);
1866 +
    let mut empty = newBuilder();
1867 +
    let zero = addLayout(&mut empty, 0, 1, &[]);
1868 +
    let sliceOfZero = addLayout(&mut empty, 16, 8, &[sliceSlot(0, zero, true, true)]);
1869 +
    try checkIn(&mut empty, &handle[..], il::ValType::Void,
1870 +
        &[reserve(1, sliceOfZero), pageSlice(2, 1, true, zero), retVoid()], verify::Rule::View);
1871 +
    try check(&handle[..], &[reserve(1, SLICE), pageSlice(2, 1, true, P1), add(3, reg(2), imm(1))],
1872 +
        nil);
1873 +
}
1874 +
1875 +
/// Block order in the file is free: a block can come before the blocks that dominate it.
1876 +
/// The backend must not depend on it.
1877 +
@test unsafe fn layoutBeforeDominator() throws (testing::TestError) {
1878 +
    let mut b = newBuilder();
1879 +
    let entry = block(&mut b, &[], &[jmp(2, none())]);
1880 +
    let reader = block(&mut b, &[], &[
1881 +
        copy(3, imm(0x1000)), load64(4, 1, 0), add(5, reg(4), reg(3)), ret(reg(5)),
1882 +
    ]);
1883 +
    let writer = block(&mut b, &[], &[
1884 +
        copy(0, imm(5)), reserve(1, P8), add(2, reg(0), reg(0)), jmp(1, none()),
1885 +
    ]);
1886 +
    addBlocks(&mut b, "main", &[], dataType(), &[entry, reader, writer]);
1887 +
    try accepted(&mut b);
1888 +
}
std.lib +4 -0
36 36
lib/std/lang/il/binary/writer.rad
37 37
lib/std/lang/il/binary/reader.rad
38 38
lib/std/lang/il/binary/program.rad
39 39
lib/std/lang/il/binary/collect.rad
40 40
lib/std/lang/il/binary/cfg.rad
41 +
lib/std/lang/il/verify.rad
42 +
lib/std/lang/il/verify/layout.rad
43 +
lib/std/lang/il/verify/flow.rad
44 +
lib/std/lang/il/verify/data.rad
41 45
lib/std/lang/resolver.rad
42 46
lib/std/lang/resolver/printer.rad
43 47
lib/std/lang/lower.rad
44 48
lib/std/lang/module.rad
45 49
lib/std/lang/module/printer.rad
std.lib.test +1 -0
17 17
lib/std/lang/resolver/tests/safety.rad
18 18
lib/std/lang/resolver/tests/opacity.rad
19 19
lib/std/lang/gen/bitset/tests.rad
20 20
lib/std/lang/il/binary/tests.rad
21 21
lib/std/lang/il/binary/tests/decode.rad
22 +
lib/std/lang/il/verify/tests.rad
22 23
lib/std/arch/rv64/image/tests.rad
23 24
lib/std/arch/rv64/tests/bounds.rad
24 25
lib/std/arch/rv64/tests/atomics.rad
test/Makefile +9 -2
1 1
# Compiler and standard library test suites. Run from the repository root.
2 2
# JOBS controls workers inside test scripts.
3 3
JOBS ?= 1
4 4
export JOBS
5 -
TESTS := seed-test std-test bin-test module-test native-test
5 +
TESTS := seed-test std-test bin-test module-test \
6 +
    native-test verify-test
6 7
7 8
test: $(TESTS)
8 9
.PHONY: test $(TESTS) smp-test cycles-test clean-std-test clean-bin-test
9 10
10 11
# Hosted test tools share one compiler recipe.
11 12
# Runner binary: the lowering IL checker.
12 -
TEST_TOOL_SRC := test/runner.rad test/native/build.rad
13 +
TEST_TOOL_SRC := test/runner.rad test/native/build.rad \
14 +
    test/verify/check.rad
13 15
TEST_TOOLS := $(TEST_TOOL_SRC:.rad=.rv64)
14 16
15 17
$(TEST_TOOLS): %.rv64: %.rad $(STD_LIB) $(RAD_BIN) test/Makefile
16 18
	@$(RADIANCE) $(STD) -pkg tool -mod $< -entry tool -o $@
17 19
89 91
	@rm -f $(TEST_TOOLS) $(BIN_TEST_BIN) test/compiler/discovery.rv64 \
90 92
	    $(wildcard test/tests/*.rv64.debug test/tests/*.rv64.s) \
91 93
	    $(TEST_TOOLS:.rv64=.rv64.debug) $(TEST_TOOLS:.rv64=.rv64.s) \
92 94
	    $(TEST_TOOLS:.rv64=.rv64.o)
93 95
96 +
# The verifier accepts or rejects the binary RIL of each fixture as
97 +
# test/verify/expected says.
98 +
verify-test: test/verify/check.rv64
99 +
	@sh test/verify/run
100 +
94 101
# Exercise the production test discovery module with bounded storage.
95 102
test/compiler/discovery.rv64: test/compiler/discovery.rad \
96 103
    compiler/radiance/testgen.rad $(STD_LIB) $(RAD_BIN) test/Makefile
97 104
	@$(RADIANCE) $(STD) -pkg testgen -mod compiler/radiance/testgen.rad \
98 105
	    -pkg checks -mod test/compiler/discovery.rad -entry checks -o $@
test/verify/check.rad added +121 -0
1 +
//! Verify the programs of binary RIL packages and report the outcome of each.
2 +
//!
3 +
//! Each argument is the path of a package file. The tool prints one line per file:
4 +
//! the path, then `ok`, or the violated rule and its location.
5 +
6 +
use std::io;
7 +
use std::mem;
8 +
use std::sys;
9 +
use std::sys::unix;
10 +
use std::lang::alloc;
11 +
use std::lang::il;
12 +
use std::lang::il::binary;
13 +
use std::lang::il::binary::program;
14 +
use std::lang::il::verify;
15 +
16 +
/// Number of elements reserved for keep storage.
17 +
constant KEEP_CAPACITY: u32 = 16777216;
18 +
19 +
/// Largest package file.
20 +
constant IMAGE_SIZE: u32 = 8388608;
21 +
/// Decode arena capacity.
22 +
constant DECODE_SIZE: u32 = 100663296;
23 +
/// Verifier scratch capacity.
24 +
constant SCRATCH_SIZE: u32 = 33554432;
25 +
/// Package file storage.
26 +
static IMAGE: [u8; IMAGE_SIZE] = [0; IMAGE_SIZE];
27 +
/// Decoded package storage.
28 +
static DECODED: [u8; DECODE_SIZE] = [0; DECODE_SIZE];
29 +
/// Storage for the narrowed exports of a package.
30 +
static KEEP: [u8; KEEP_CAPACITY] = [0; KEEP_CAPACITY];
31 +
/// Verifier working storage.
32 +
static SCRATCH: [u8; SCRATCH_SIZE] = [0; SCRATCH_SIZE];
33 +
34 +
/// Limits of the verifier for the fixtures.
35 +
constant CONFIG: verify::Config = verify::Config {
36 +
    registers: 1048576, blocks: 65536, layoutSize: 0x7fffffff, layoutDepth: 32, params: 16,
37 +
    envSize: 4096,
38 +
};
39 +
40 +
/// Print the location of an error.
41 +
fn printPlace(program: &il::Program, place: verify::Place) {
42 +
    match place {
43 +
        case verify::Place::Package => io::print("package"),
44 +
        case verify::Place::Layout(i) => {
45 +
            io::print("layout ");
46 +
            io::printU32(i);
47 +
        },
48 +
        case verify::Place::Signature(i) => {
49 +
            io::print("signature ");
50 +
            io::printU32(i);
51 +
        },
52 +
        case verify::Place::Data(i) => {
53 +
            io::print("data ");
54 +
            io::print(program.data[i].name);
55 +
        },
56 +
        case verify::Place::Fn(i) => {
57 +
            io::print("fn ");
58 +
            io::print(program.fns[i].name);
59 +
        },
60 +
        case verify::Place::Instr { func, block, instr } => {
61 +
            io::print("fn ");
62 +
            io::print(program.fns[func].name);
63 +
            io::print(" block ");
64 +
            io::printU32(block);
65 +
            io::print(" instr ");
66 +
            io::printU32(instr);
67 +
        },
68 +
    }
69 +
}
70 +
71 +
/// Verify the package as a loadable one or as a program.
72 +
unsafe fn verifyAs(package: &mut binary::Package, loadable: bool, scratch: &mut alloc::Arena,
73 +
    keep: &mut alloc::Arena) throws (verify::Error)
74 +
{
75 +
    if loadable {
76 +
        try verify::verifyPackage(package, CONFIG, scratch, keep);
77 +
    } else {
78 +
        try verify::verifyProgram(&package.program, CONFIG, scratch);
79 +
    }
80 +
}
81 +
82 +
/// Verify the package in the file at `path`, as a loadable package when `loadable` is set,
83 +
/// and print the result.
84 +
unsafe fn check(path: *[u8], loadable: bool) {
85 +
    io::print(path);
86 +
    io::print(": ");
87 +
    let length = unix::readFile(path, &mut IMAGE[..]) else {
88 +
        io::print("unreadable\n");
89 +
        return;
90 +
    };
91 +
    let mut arena = alloc::new(&mut DECODED[..]);
92 +
    let mut package = try program::decode(&IMAGE[..length], &mut arena,
93 +
        binary::Limits { registers: CONFIG.registers, blocks: CONFIG.blocks }) catch {
94 +
        io::print("undecodable\n");
95 +
        return;
96 +
    };
97 +
    let mut scratch = alloc::new(&mut SCRATCH[..]);
98 +
    let mut keep = alloc::new(&mut KEEP[..]);
99 +
    try verifyAs(&mut package, loadable, &mut scratch, &mut keep) catch err {
100 +
        io::print(verify::ruleName(err.rule));
101 +
        io::print(" ");
102 +
        printPlace(&package.program, err.place);
103 +
        io::print("\n");
104 +
        return;
105 +
    };
106 +
    io::print("ok\n");
107 +
}
108 +
109 +
/// Verify each package named on the command line.
110 +
@default unsafe fn main(env: *sys::Env) -> i32 {
111 +
    let mut first: u32 = 1;
112 +
    let mut loadable = false;
113 +
    if env.args.len > 1 and mem::eq(env.args[1], "-package") {
114 +
        set loadable = true;
115 +
        set first = 2;
116 +
    }
117 +
    for i in first..env.args.len {
118 +
        check(env.args[i], loadable);
119 +
    }
120 +
    return 0;
121 +
}
test/verify/expected added +134 -0
1 +
alloc.arena.trait Type
2 +
array.pointer Type
3 +
array.repeat.loop Mutability
4 +
array.slice.gen.index Type
5 +
array.slice Type
6 +
bool.comparison.slice.record.gen Slot
7 +
bool.comparison.slice Slot
8 +
bool.comparison.slice.union.gen Slot
9 +
borrow.index.disjoint Symbol
10 +
builtin.sliceof.mut Type
11 +
builtin.sliceof Type
12 +
call.clobber Type
13 +
call.stack.args.method Type
14 +
cast.basic View
15 +
cond.match.guard.regalloc View
16 +
data.optional.nil Data
17 +
data.optional.value Data
18 +
ecall.i64 Slot
19 +
edge.cases.4 Type
20 +
edge.cases.6 Data
21 +
entry.storage.dict Data
22 +
entry.storage.record Data
23 +
entry.storage.slices Data
24 +
entry.storage.slices.index Data
25 +
entry.storage.slices.lower Data
26 +
entry.storage.slices.range Data
27 +
entry.storage.split Data
28 +
entry.storage Symbol
29 +
error.slice.bounds Type
30 +
fn.callback.nested Type
31 +
fn.unsafe.callbacks Type
32 +
index.u8 Type
33 +
layout.union Slot
34 +
linear.unsafe Type
35 +
match.alternatives.subject Type
36 +
match.mutref.push Type
37 +
match.nested.deref Type
38 +
match.nested.enum.byref Type
39 +
match.nested.guard.field Type
40 +
match.variant.fields.bind Slot
41 +
match.variant.fields.deref Type
42 +
method.chain Return
43 +
method.eight.params.throws Type
44 +
method.eight.params Type
45 +
method.multiple Type
46 +
method.return Return
47 +
method.with.trait Type
48 +
mutref.call.result Type
49 +
mutref.loop Type
50 +
opt.slice.npo Type
51 +
pointer.arithmetic.unsafe Type
52 +
pointer.borrow.unsafe Type
53 +
pointer.cast.unsafe View
54 +
pointer.copy.edge.case Type
55 +
pointer.slice.index Type
56 +
pointer.slice.store Data
57 +
pointer.stack.unsafe Type
58 +
prog.dijkstra Type
59 +
prog.huffman Type
60 +
prog.lzw Type
61 +
prog.mersenne Type
62 +
prog.nqueens Type
63 +
prog.rbtree Type
64 +
prog.regex Type
65 +
prog.sieve Type
66 +
prog.symtab Type
67 +
prog.tokenizer Type
68 +
prog.vm Type
69 +
range.arithmetic Type
70 +
record.scalar Class
71 +
ref.local.slice.release Type
72 +
ref.mut.ptr Type
73 +
return.never.catch Bounds
74 +
slice.alloc.loop Type
75 +
slice.alloc.trait Type
76 +
slice.append.errors Type
77 +
slice.append.failure Type
78 +
slice.append.trait Type
79 +
slice.append Type
80 +
slice.append.values Type
81 +
slice.assign Type
82 +
slice.basic Slot
83 +
slice.cap Type
84 +
slice.construct.unsafe Slot
85 +
slice.delete Type
86 +
slice.empty.nonnull Data
87 +
slice.extend.borrowed Type
88 +
slice.extend.bytes Type
89 +
slice.extend.copy Type
90 +
slice.extend.overflow Type
91 +
slice.extend.overflow.words Type
92 +
slice.failure Type
93 +
slice.grow Type
94 +
slice.header.unsafe Slot
95 +
slice.of Type
96 +
slice.ptr.unsafe Slot
97 +
slice.range.capacity Type
98 +
slice.range.dynamic Type
99 +
slice.reserve.result Type
100 +
slice.reserve Type
101 +
slice.resize.extend Type
102 +
slice.resize.fill.snapshot Type
103 +
slice.sizes Type
104 +
slice.subslice Type
105 +
slice.take.sizes Type
106 +
slice.take Type
107 +
slice.zero-sized Slot
108 +
static.empty.slice.optional Data
109 +
static.slice.empty Data
110 +
static.slice.empty.record.table Data
111 +
static.slice.empty.table Data
112 +
static.slice.offset Data
113 +
static.zero.bss Data
114 +
static.zero.record.repeat Data
115 +
trait.aggregate.ret Type
116 +
trait.array.optional Type
117 +
trait.basic Type
118 +
trait.control.flow Type
119 +
trait.dispatch Type
120 +
trait.fn.param Type
121 +
trait.multiple.methods Type
122 +
trait.multiple.traits Type
123 +
trait.multiple.types Type
124 +
trait.object Type
125 +
trait.param.names.shared Type
126 +
trait.supertrait.forward Type
127 +
trait.supertrait Type
128 +
trait.throws Type
129 +
trait.writer Type
130 +
undefined.merge.pointer Type
131 +
union.edge.case.3 Type
132 +
union.payload.mutref Type
133 +
union-tag Type
134 +
unsafe.block Type
test/verify/run added +59 -0
1 +
#!/bin/sh
2 +
# Verify source-only binary RIL fixtures against test/verify/expected.
3 +
# Usage: run [checker]
4 +
# Compile errors, crashes, timeouts, and missing output fail the run.
5 +
set -eu
6 +
7 +
hosted=$(cd "$(dirname "$0")/../.." && pwd)/scripts/hosted
8 +
9 +
# Compare one checker report with the complete package list and expected rules.
10 +
checkResults() {
11 +
    work=$1
12 +
    checker=$2
13 +
    set -- "$work"/*/test.ril
14 +
    printf '%s\n' "$@" | sort > "$work/packages"
15 +
    "$hosted" "$checker" -- "$@" > "$work/checks"
16 +
    sed 's/: .*//' "$work/checks" | sort > "$work/reported"
17 +
    if ! diff -u "$work/packages" "$work/reported"; then
18 +
        printf 'verify: checker must report each package exactly once\n' >&2
19 +
        exit 1
20 +
    fi
21 +
    sed 's#^.*/\([^/]*\)/test.ril: \([A-Za-z]*\).*$#\1 \2#' \
22 +
        "$work/checks" > "$work/outcome"
23 +
    grep -v ' ok$' "$work/outcome" | sort > "$work/rejected"
24 +
    sort test/verify/expected > "$work/expected"
25 +
    printf 'verify: %s fixtures, %s accepted, %s rejected\n' \
26 +
        "$(wc -l < "$work/outcome")" "$(grep -c ' ok$' "$work/outcome")" \
27 +
        "$(wc -l < "$work/rejected")"
28 +
    if ! diff -u "$work/expected" "$work/rejected"; then
29 +
        printf 'verify: outcome differs from test/verify/expected\n' >&2
30 +
        exit 1
31 +
    fi
32 +
}
33 +
34 +
# Report-only mode lets failure tests use packages without compiling sources.
35 +
if [ "${1:-}" = --check ]; then
36 +
    checkResults "$2" "$3"
37 +
    exit 0
38 +
fi
39 +
40 +
work=$(mktemp -d)
41 +
trap 'rm -rf "$work"' EXIT HUP INT TERM
42 +
43 +
# Native assembly inputs cannot be emitted as binary RIL.
44 +
for source in test/tests/*.rad; do
45 +
    base=${source%.rad}
46 +
    if [ ! -f "$base.ras" ] && [ ! -f "$base.start.ras" ]; then
47 +
        printf '%s\n' "$source"
48 +
    fi
49 +
done > "$work/fixtures"
50 +
if ! xargs -P "${JOBS:-1}" -I{} sh -c '
51 +
    source=$1
52 +
    name=${source##*/}
53 +
    sh test/compile "$source" "$2/${name%.rad}"
54 +
' sh {} "$work" < "$work/fixtures" > "$work/compile.log" 2>&1; then
55 +
    cat "$work/compile.log" >&2
56 +
    exit 1
57 +
fi
58 +
59 +
checkResults "$work" "${1:-test/verify/check.rv64}"