diff options
31 files changed, 362 insertions, 66 deletions
@@ -176,6 +176,8 @@ functions are declared like C, return type first: `int f(int x)`, `node*.u make( array types put the element type first. `T[n]` has its size in the type and lives in place. `T[]` also lives in place; its length is inferred from an initializer such as `int[] a = {1, 2, 3};` and cannot grow. `T[?]` can also be initialized in a function with a list, such as `int[?] a = {1, 2};`. it is a growable array: a small handle object that owns its items, made with `rt.new(T[?])` or `rt.new(T[?], n)`, indexed with a bounds check, and changed with `push(a, x)`, `pop(a)` and `resize(a, n)`. `len(a)` works on both (for `T[n]` it's the constant) and `cap(a)` gives the room before the next grow. `fixed T[?]` is a `T[?]` that can't change size: `rt.new(fixed T[?], n)` needs the length, and `push`, `pop` and `resize` on it are compile errors. a `fixed T[?]` can't be passed where a `T[?]` is expected, the other way round is fine, and a constant index outside a `T[n]` is caught at compile time. the items belong to the array, so freeing it frees them, and objects stored into a `T*[?]` are its children like any container's. +**bounds checks.** every index is checked at run time unless you say otherwise. a `T[?]` is checked against its length, a `T[n]` with a variable index against `n` (`i | (n - 1 - i)` is negative exactly when `i` is outside, so it is a subtract, an or and a compare inline), and a pointer against the payload of the heap block it starts, through the `rt.bnd` enhancement and `rt.bchk` to report. a pointer into the middle of a block, a frame array, a global or memory managed by hand has no known length and is not checked, and a heap block's length is its buddy capacity (`rt.new(4)` holds 11 words), so a pointer check catches running off the block, not off the size you asked for. a constant index 0 or one the analyzer knows is inside the allocation, and an index that a loop test `i < k` with constant `k` has already compared are not checked again. a failed check prints `zy: index I out of range (length N)` and the backtrace, and stops. `unbounded` turns the checks off, used like `unchecked`: `unbounded fn f()`, `unbounded { ... }`, `unbounded stmt;` and `unbounded;` for the rest of the unit. o3 implies it. the runtime, the core, the compiler, the language server, `run.zc` and `build.zc` start with `unbounded;` (zc0 accepts the word and ignores it, so the genome's first stage is unchanged). + the array intrinsics also accept receiver syntax: `a.len()`, `a.cap()`, `a.push(x)`, `a.pop()` and `a.resize(n)`. fixed arrays provide `len()` and `cap()` but reject `push()`, `pop()` and `resize()`. [the learning example](examples/learn/19-growable.zc) shows both receiver forms. `fixed const T[n]` and `const fixed T[n]` both make the array cells and aliases read-only. element writes, increments, compound assignments, and rebinding a `const fixed T[?]` handle are rejected even when `typecheck off;` is active. a read-only array reference cannot become a mutable reference. a formal parameter such as `const fixed int[2] values` accepts either read-only or mutable arrays. element values can still be copied into ordinary mutable scalars. [the learning example](examples/learn/33-const-fixed.zc) shows both qualifier orders and a read-only formal parameter. @@ -419,7 +421,7 @@ fn main() { what it gives up, as asked: variables declared in o3 code must be typed (`let` and untyped parameters are errors), they have no address (`&x` and naming one from `asm` are errors), an untyped `rt.new(n)` in o3 code is `new_oz` (no type stamp, and the words asked for are zero), and an o3 function skips the frame stack check in its prologue. typed `rt.new(T)` and `rt.new(T, n)` stamp the header and zero the payload, in o3 the same as outside it. what it gets: the compiler hands each o3 function body and each o3 block to the core as a region (install kind 2: the range of vm words plus its typed scalar variables' frame slots, each with a register), and the core compiles the region right away. the cpu has 7 registers for variables. a variable takes the one most recently freed by a scope that closed, or the next unused one, so loop counters in sibling loops share a register, and a variable declared when all 7 are busy stays in memory. a register shared by several slots gets written back to all of them when the region exits, and they never hold different live values, since their scopes don't overlap. -inside the core, a region is cut into basic blocks at jump targets, branch fallthroughs and call return points. an empty jump is then folded into its target, a block with one predecessor is pasted onto that predecessor, and a straight loop is rotated so one iteration is a single block that branches to itself. a call, a return, a value left on the stack, or a second branch stays where it is, and an entry is never pasted over. each block is lifted to ssa the way enhancements are: the vm stack becomes values, and only what's still on it at the end of the block is written to memory. the frame pointer and the promoted slots become variables that live in registers across the whole region, so `i++` on an o3 int is one add. enhancements are spliced into the block, so `/`, `%` and `<<` become one instruction or a magic-number sequence. a call to `ld8`, `st8`, `ld16`, `st16`, `ld32` or `st32` from o3 code emits opcodes 612..617, and the region lifts those instead of calling out. every block then goes through the same optimizer (folding, algebra, cse, dce, division by constants). in o3 code `a[i]` on a `T[?]` is compiled inline with its bounds check (`outside(i, len)`, one enhancement), and `len(a)` is a load. a `fixed T[?]` in an o3 variable does better: its items pointer and length can't change, so the compiler gives it two hidden o3 variables holding them. they're loaded when the region starts and whenever the array variable is assigned, so indexing is a compare against a register and an indexed load, with no loads through the handle. +inside the core, a region is cut into basic blocks at jump targets, branch fallthroughs and call return points. an empty jump is then folded into its target, a block with one predecessor is pasted onto that predecessor, and a straight loop is rotated so one iteration is a single block that branches to itself. a call, a return, a value left on the stack, or a second branch stays where it is, and an entry is never pasted over. each block is lifted to ssa the way enhancements are: the vm stack becomes values, and only what's still on it at the end of the block is written to memory. the frame pointer and the promoted slots become variables that live in registers across the whole region, so `i++` on an o3 int is one add. enhancements are spliced into the block, so `/`, `%` and `<<` become one instruction or a magic-number sequence. a call to `ld8`, `st8`, `ld16`, `st16`, `ld32` or `st32` from o3 code emits opcodes 612..617, and the region lifts those instead of calling out. every block then goes through the same optimizer (folding, algebra, cse, dce, division by constants). o3 code is unbounded, so `a[i]` on a `T[?]` there is compiled inline as an address with no bounds check, and `len(a)` is a load. a `fixed T[?]` in an o3 variable does better: its items pointer and length can't change, so the compiler gives it two hidden o3 variables holding them. they're loaded when the region starts and whenever the array variable is assigned, so indexing is an indexed load, with no loads through the handle. the backends: on arm64 the region becomes one piece of native code. variables sit in w0..w7, block values in w8..w14 and w26..w28, constants are folded into instructions where they fit, loads from a fixed address are one `ldr`, and blocks branch to each other directly with no dispatch and no stack checks. on the llvm build the region becomes one function, with the variables in allocas that mem2reg turns into ssa across blocks, and it goes through llvm's O3 pipeline. on the plain interpreter, a small region interpreter runs the optimized blocks with the variables in locals. @@ -378,6 +378,33 @@ of the open list. scratchpad `base/`, not in the zip); `make parity`. the 35% fixed-array cost is worth a look before merging (hoist checks out of loops whose bound is the array length, extend `proven`). + resumed on work/bounds (ported onto main f75ce6a, conflicts in base, decl + and expr; the context save is 50 words, `fbnd` at 49 after `dfr_base`). + done: o3call's main is `unbounded`; `o3_bounds` and `bounds_hi` now expect + no check (o3 implies unbounded); new boundsrules, bounds_fixed, bounds_heap, + zc0unbounded (also a run-only image) with test.sh lines; bounds_fixed and + bounds_heap are in parity.known; docs in README ("bounds checks"), SPEC + 2.6.1, 3.7.4, 3.13.4, 4.10.1, new 4.15, 5.1.1 and the keyword table, the + server's `kwtext` and `iskeyword`, the vscode grammar. genome 395477 to + 399590 words (+4113, +1.0%); the self-compile takes about 1.1 to 1.2 s + before and after. the fixed-array cost: the `for (i < K)` proof never fired + (the loop shape needed a local on the right of `<`), fixed now, so a + constant-bound loop costs nothing; the inline check is now plain ops + (`i | (n - 1 - i)` < 0) instead of the `outside` enhancement, which the + x86-64 jit calls rather than inlines. best of 3, ms, main / port / final: + hash-index kernel jit 37 / 72 / 44, interpreter 412 / 504 / 542; loop with a + variable bound jit 55 / 113 / 69, interpreter 741 / 907 / 865; loop with a + constant bound jit 46 / 100 / 53, interpreter 663 / 822 / 690. the plain-op + check is slightly slower than the enhancement on the interpreter for an + unprovable index, and probably on arm64, where enhancements are inlined (not + measured here). still open: pointers, jit 52 to 279 ms and interpreter 710 + to 1141 ms on a 256-word sweep (`rt.bnd` is an enhancement call on x86-64); + a variable loop bound is not hoisted (needs a loop-entry test of `n <= N`, or + of the heap block's payload for a pointer, and a flag the body tests). + inlining enhancements in the x86-64 jit would help both. also fixed here: + four conformance expectations on main lacked the backtrace line that line + tables print (3-expressions/dyn_array_*), and test.sh's run-only gc sed + still looked for `f >= 990`. - spec conformance (`agents/spec-conformance`, last 808886b; the first, interrupted attempt is `agents/spec-conformance-first-attempt`, already folded in). done: sections 1 source (114 programs, zy 103 ok), 2 types @@ -487,14 +514,14 @@ brief someone without re-reading the code. - [ ] continue removing `unchecked` from the runtime. a reverted trial showed: `copy_w`/`fill_w` pass the analyzer when their gate stores go through `syscall(SYS_COPY, ...)`, `dgrow` with `own(w, it)` instead of `w[-2] = it`, `dpush` with `own` before the store, `dnew` as is; but the checked versions changed behavior (7 program checks failed, `tests/programs/share.zc` hung with a checked `cons`), so checked code inserts cleanup these functions can't afford. each needs its contract taught to the analyzer. `free`, `recycle`, `recycle_leaf`, `gc` are the allocator and collector the analyzer's own cleanup calls: document them as the irreducible escapes. `src/lib/actor.zc` has about 20 more. - [ ] revise diagnostics, comments and learning/reference prose using professional compiler documentation guidance, preserving lowercase and adding message regressions. touches messages everywhere, so do it when few other compiler changes are in flight. - [ ] (partly done, see "agent work at the end of the session") test blocks: `test "name" { ... }` with `expect(cond)`, compiled only by `zy --test file.zc`, which runs each block and prints one line per test with the position of the first failed `expect`; skipped at parse time otherwise. build it as a library through `run.syntax` and `run.statement_hook`, like `src/lib/actor.zc`. -- [ ] (partly done, see "agent work at the end of the session") bounds checking on by default, `unbounded` to turn it off (function prefix, block, top-level `unbounded;`, mirroring `unchecked`), implied by `o3`. architecture: indexing is compiled in the postfix `[` handling of the expressions part; growable arrays already check (`dat`, `range_jz`, the `outside` enhancement, `proven()` removing checks a loop test already did). fixed arrays `T[n]` with a variable index get the same inline check against the constant `n`. pointers get a runtime call (for example `rt.bchk(p, i)`) that checks only when `p` is the start of a live heap block (header check word `p ^ MAGIC`, `paylen`), skipping constant index 0 and sizes the analyzer knows (`lnsz`). reports go through `oob`. the runtime, core, compiler parts, server, `run.zc` and `build.zc` start with `unbounded;`, which zc0 accepts and ignores (genome bytes unchanged). keep std, icon and actor checked unless a function touches raw memory on purpose. measure interpreter time before and after. +- [x] (done on work/bounds, see "agent work at the end of the session") bounds checking on by default, `unbounded` to turn it off (function prefix, block, top-level `unbounded;`, mirroring `unchecked`), implied by `o3`. architecture: indexing is compiled in the postfix `[` handling of the expressions part; growable arrays already check (`dat`, `range_jz`, the `outside` enhancement, `proven()` removing checks a loop test already did). fixed arrays `T[n]` with a variable index get the same inline check against the constant `n`. pointers get a runtime call (for example `rt.bchk(p, i)`) that checks only when `p` is the start of a live heap block (header check word `p ^ MAGIC`, `paylen`), skipping constant index 0 and sizes the analyzer knows (`lnsz`). reports go through `oob`. the runtime, core, compiler parts, server, `run.zc` and `build.zc` start with `unbounded;`, which zc0 accepts and ignores (genome bytes unchanged). keep std, icon and actor checked unless a function touches raw memory on purpose. measure interpreter time before and after. - [ ] after the fuzzing work, add more general functionality to the standard library. - [ ] (partly done, see "agent work at the end of the session") struct destructors: a struct may declare `fn drop()`, called wherever the compiler frees an owned value of that type, before the memory is released. architecture: the compiler frees owned locals in `freevar` (analyzer part), called from `exit_vars`, reassignment and explicit `rt.free`/`rt.recycle` calls (`s_free`, `s_recycle` handling in the call code); when the local's static type is a pointer to a struct with a `Name.drop` method, emit a call to it first. objects freed by the collector or inside unchecked code do not run `drop`: document that. first users: file descriptors in `std.Host`, processes in `actor.zc`. - [x] (done on work/line-tables, see "agent work at the end of the session") runtime source positions. architecture: at each statement start (`stmt()`) record (code address `here`, line); per function a permanent data block [entry, end, name, file, count, pairs...] linked into a runtime list (`rt.line_blocks`), or appended to run-only images by `build_image` like the symbol blob. `lines on;`/`lines off;` like `docs on;`; on for user programs, off for the genome unless the growth is small. a new syscall op returns the return-stack pointer (the return stack is in vm memory, 0x1A4100..0x1B40FF, growing up); implement it in `src/core/core.c`, `src/micro/micro.c`, `src/js/tinyvm.ts` and the wasm port. `rt.trace()` walks the return stack, printing ` at file:line in function` for words inside a known function range. the runtime's fatal reports (`oob`, bad heap pointer, double free, out of memory, frame overflow) print the trace after their unchanged first line. check mode skips all of it. - [ ] borrow returns tied to an argument. inference already works for a callee defined before the call: `char* skip(char* s) { ...; return s + i; }` makes `let r = skip(t); rt.free(t); r[0]` an error. the gap: when the call comes before the callee's definition, nothing is reported and the program reads freed memory. extend the deferred effect requirements (`effect_require`, `effect_finish` at unit end) so a forward-called function whose return turns out to alias a parameter produces the same error. for bodyless declarations, externs and function types, add an unobtrusive spelling, for example a `borrows s` clause after the parameter list (`char* skip(char* s) borrows s;`), checked against the body when one exists. - [ ] variadic arguments and `std.print`. design: a pack is passed as one hidden argument, a caller-built read-only growable-array handle (`fixed T[?]` view: [len, cap, items, element size] in the caller's frame, so `len(a)` and `a[i]` work unchanged and nothing is allocated). `...int a` is a typed pack; several packs per function when their element types differ (`void f(...int a, ...char b)`): each extra argument goes to the pack whose element type matches its static type, an ambiguous match is an error, packs come after the fixed parameters. `...any args` packs each value with a kind code (int, float, char, string, bstr, pointer, ...) and its type record: `any` is a small built-in record { kind, value, type }. `...*any args` makes the call comma-free: after the fixed arguments, the parser reads unary expressions until `)`, commas optional, so `std.print("x = " name ", age " age "\n");` works and binary expressions must be parenthesized. `std.print(...*any args)` prints each argument by its kind (`put_n`, the float printer, `put_s`, `put_bs`, a character for `char`, hex for pointers). - [ ] x86-64 jit phase 2: compile o3 regions to x86-64 (port `rcompile` and the region register allocation; regions now run on the region interpreter and are 2 to 4 times slower than their plain versions on this jit) and inline enhancements (lower the optimized micro-ops to x86 registers as the arm64 path does, instead of calling `xrun`). validate with `tests/drivers/jit_x64_test.sh` and `tests/bench/bench.sh`, which now has an x86-64 jit column. add the driver to `tests/test.sh` on x86-64 linux. -- [ ] `memdebug`'s `obj_base` searches only 64 words back for a block header, so under `memdebug on` an interior access more than 64 words into a block (`buf[255]` on a 256-word block) reports "bad heap pointer". find the header from the buddy allocator's size classes instead of a bounded scan, with a regression program. +- [x] `memdebug`'s `obj_base` used to search only 64 words back for a block header, so `buf[255]` on a 256-word block reported "bad heap pointer". it now rounds the pointer down to each size class's alignment (largest first) and takes the first header whose check word, size and class agree and whose payload holds the pointer, so interiors at any depth work, a deep pointer into a freed block reports use after free, and header words and free space still report "bad heap pointer". regression: `tests/programs/memdebug_interior.zc` (in `tests/test.sh` beside the other memdebug checks). note that a stray pointer that lands inside another live block is accepted, since memdebug cannot know which block it came from. - [ ] (partly done, see "agent work at the end of the session") `defer` follow-ups (small): accept `defer if (...) ...;` and other single statements besides an expression; decide whether deferred code may name an owner declared after the `defer` (now rejected by the lexical rule; one line in `defer_one`). - [ ] build the llvm core by default when `llvm-config` is available (the makefile falls back to the interpreter otherwise), so x86 hosts get a native tier and the language server stops being interpreted; keep `ZYNOLLVM=1` and `-DZYINTERP` as the opt-outs. - [ ] stack-effect checking: every function and `asm` block declares or is inferred to have a fixed data-stack effect, and the compiler reports a block whose paths leave the stack unbalanced. the first step of a proving scaffold. diff --git a/docs/SPEC.md b/docs/SPEC.md index 5618a5e..6df55f6 100644 --- a/docs/SPEC.md +++ b/docs/SPEC.md @@ -60,6 +60,7 @@ a name that looks like `x.y` where `x` is not a known module is the three tokens | `memdebug` | S | T | | 4.11 | | `hints` | S | T | | 4.12 | | `unchecked` | S | | | 4.9, 5.1 | +| `unbounded` | S | | | 4.15, 5.1 | | `o3` | S | | | 4.10 | | `asm` | S | | E | raw vm words (4.13) | | `run.method` | S | T | | register a receiver method (7.7) | @@ -190,7 +191,7 @@ u32 z = 0; z--; // z is 4294967295 ### 2.6 arrays -2.6.1 `T[n]`: `n` is a constant expression (3.14) and the array lives in place: in a frame, a global, or inside a struct. its value is its address. `sizeof(T[n])` is the words the elements take (packed for sized types). there is no run-time bound check; a constant index outside `0..n-1` is error: the index is out of range for this array. +2.6.1 `T[n]`: `n` is a constant expression (3.14) and the array lives in place: in a frame, a global, or inside a struct. its value is its address. `sizeof(T[n])` is the words the elements take (packed for sized types). a variable index is checked at run time against `n` (3.7.4) unless the code is unbounded (4.15); a constant index outside `0..n-1` is error: the index is out of range for this array. 2.6.2 `T[]` is an in-place array whose length comes from its initializer: `int[] a = {1, 2, 3};` has length 3. without an initializer, error: T[] needs an initializer to determine its length. @@ -426,7 +427,7 @@ pn((int)(p + 1) - (int)p); // 1: p + 1 moves one word 3.7.3 `&x` is the address of a variable, field or element. it applies to a local (which then lives in memory and cannot be an o3 variable), a global, a field and an element of a non-packed array. an element of a packed array has no address (2.3.3). -3.7.4 indexing a new object (`rt.new(int)[0]`) is error: index a new object only after binding it to a name. indexing a `T[?]` is bounds checked (3.13). indexing a `T[n]` or a pointer is not checked at run time. +3.7.4 indexing a new object (`rt.new(int)[0]`) is error: index a new object only after binding it to a name. indexing is bounds checked at run time unless the function, block, statement or unit is unbounded or the code is o3 (4.15). a `T[?]` is checked against its length (3.13), a `T[n]` against `n`, and a pointer only when it points at the first word of a live heap block, against that block's payload (a buddy block rounds the payload up: `rt.new(4)` has 11 words). a pointer into the middle of a block, a frame array, a global or memory managed by hand is not checked. a constant index 0, and an index a loop test `i < k` with constant `k` (or `i < len(a)`) has already proved, are not checked again. a failed check prints `zy: index I out of range (length N)` and stops, as in 3.13.4. 3.7.5 an index must be a number (typecheck on). @@ -480,7 +481,7 @@ pn((int)(p + 1) - (int)p); // 1: p + 1 moves one word 3.13.3 `push(a, x)` appends and grows; `pop(a)` removes and returns the last element; `resize(a, n)` sets the length, zero-filling new elements and dropping the rest (freeing owned elements). `push` and `pop` on aggregate element types are errors (push takes scalar or reference elements; use resize for aggregates). `push`, `pop`, `resize` on a `fixed` array: error: a fixed array can't grow or shrink. -3.13.4 indexing: `a[i]` with `i < 0` or `i >= len(a)` prints `zy: index I out of range (length N)` on the output and stops the program (`rt.halt`, exit status 0). `pop` on an empty array reports the same with index -1. a constant index known to be out of range also produces a compile-time warning: `zc: line N: warning: out-of-bounds access: index 2 is outside length 2 (storage declared or allocated on line N)`, and the program still runs. +3.13.4 indexing (outside unbounded and o3 code, 4.15): `a[i]` with `i < 0` or `i >= len(a)` prints `zy: index I out of range (length N)` on the output and stops the program (`rt.halt`, exit status 0). `pop` on an empty array reports the same with index -1. a constant index known to be out of range also produces a compile-time warning: `zc: line N: warning: out-of-bounds access: index 2 is outside length 2 (storage declared or allocated on line N)`, and the program still runs. ``` int[?] a = {1, 2}; push(a, 3); a.push(4); @@ -611,7 +612,7 @@ switch (s) { case circle(r): pn(r); case rect(w, h): pn(w * h); case dot: ps("do ### 4.10 o3 -4.10.1 `o3 { ... }` marks a block, `o3 T x = e;` one variable, and `o3 T f(...) { ... }` / `o3 fn f(...)` a function, for the optimising tier. o3 changes speed, not meaning, subject to these restrictions on code in an o3 region: +4.10.1 `o3 { ... }` marks a block, `o3 T x = e;` one variable, and `o3 T f(...) { ... }` / `o3 fn f(...)` a function, for the optimising tier. o3 changes speed, not meaning, except that o3 code is unbounded (4.15), subject to these restrictions on code in an o3 region: - every variable and parameter must be typed (errors: o3 variables need a type, o3 parameters need a type). - no address-of on an o3 variable and no naming one in `asm` (errors: an o3 variable has no address, asm can't reach an o3 variable). - no closures (3.15.3). @@ -655,11 +656,17 @@ int y = 7; asm { y @ 1 + y ! } // y is 8 4.14.8 defer works in `unchecked` code: the analyzer's cleanup is off there, but the deferred code runs. a defer keeps the checked or unchecked mode it was written in. a function that falls off its end runs its function-level defers before returning 0. +### 4.15 unbounded + +4.15.1 `unbounded stmt` (a block or a single statement) compiles the statement without index bounds checks (3.7.4). `unbounded;` at top level does it for the rest of the unit. `unbounded fn f() {}` (also `unbounded T f(...)`, a method or a closure) makes one function unbounded; the prefix combines with `unchecked`, `immediate` and `o3` in any order. o3 code is unbounded. `unbounded` changes no result of a program whose indexes are in range. + +4.15.2 the runtime, the core, the compiler, the language server, `run.zc` and `build.zc` are unbounded; std, icon and actor are checked except where a function reads headers on purpose. + ## 5. declarations at the top level ### 5.1 items -5.1.1 a unit is a sequence of items. an item is: a function definition or prototype, a global variable, `const`, `struct`, `type`, `enum`, `include`, `embed`, `namespace`, `typecheck`, `docs`, `lines`, `memdebug`, `hints`, `enhance`, `extern`, `unchecked;`, or a use of a top-level parse word (7.2). +5.1.1 a unit is a sequence of items. an item is: a function definition or prototype, a global variable, `const`, `struct`, `type`, `enum`, `include`, `embed`, `namespace`, `typecheck`, `docs`, `lines`, `memdebug`, `hints`, `enhance`, `extern`, `unchecked;`, `unbounded;`, or a use of a top-level parse word (7.2). 5.1.2 `struct`, `type`, `typecheck`, `docs`, `lines`, `namespace`, `enhance` and `extern` are valid only at the top level. `enum`, `embed`, `memdebug`, `hints` and `const` also appear as statements in functions. `include` is top-level only (5.12.7). diff --git a/editors/vscode/syntaxes/zc.tmLanguage.json b/editors/vscode/syntaxes/zc.tmLanguage.json index fab026b..3869418 100644 --- a/editors/vscode/syntaxes/zc.tmLanguage.json +++ b/editors/vscode/syntaxes/zc.tmLanguage.json @@ -91,7 +91,7 @@ }, { "name": "keyword.other.zc", - "match": "\\b(as|unchecked|asm|quote|sizeof|typeof|len|cap|push|pop|resize|o3|include|embed|memdebug|fixed|typecheck)\\b" + "match": "\\b(as|unchecked|unbounded|asm|quote|sizeof|typeof|len|cap|push|pop|resize|o3|include|embed|memdebug|fixed|typecheck)\\b" }, { "name": "keyword.operator.memory.zc", diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc index 8c63bdf..89713ff 100644 --- a/src/compiler/analyzer.zc +++ b/src/compiler/analyzer.zc @@ -500,6 +500,26 @@ int proven(int a, int ix) { } return 0; } +// i >= 0 and i < n for a fixed array of n elements, proved by a loop test +// against a constant of at most n and a step of +1 (kw_for records the +// constant as the array field, minus two, with -1 for the bound local) +int proven_n(int ix, int n) { + int k = lsp, w; + while (k > loopbase) { + k--; + w = lpfact[k]; + if (w >= 0 && p_iv(w) == ix && p_bd(w) == -1 && 0 - p_ar(w) - 2 <= n) return 1; + } + return 0; +} +// is the constant index xcval known to be inside the allocation f? the same +// facts af_index warns from, so a possible failure is never called definite. +int af_inrange(word f) { + int lower = 0; word base; + if (!f || !xconst || f[1] == 2 || f[0] < 0) return 0; + if (f[6]) { base = af_base(f); if (base[1] == 0 || base[10] < 0) return 0; if (f[14]) lower = f[13]; } + return xcval >= lower && xcval < f[0]; +} // follow child links up to the local that really owns the object int lroot(int i) { while (lstate[i] == S_CHILD) i = lowner[i]; diff --git a/src/compiler/base.zc b/src/compiler/base.zc index 2f802b9..8c13201 100644 --- a/src/compiler/base.zc +++ b/src/compiler/base.zc @@ -1,6 +1,9 @@ namespace run; include rt; +// the compiler pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // ============================================================================ // compiler.zc: the resident zc compiler. it lives in the genome next to the // runtime, compiles source straight to vm words in memory, and is visible to @@ -213,6 +216,7 @@ char* module_name; word module_imports; int nbin, nun, nasg, nkop, seqtop; char* mnem = "q@!$_~cjzr,?.+-*&|^><%"; int check_on = 1; // set to 0 to switch the analyzer off for what follows +int bound_on = 1; // set to 0 by unbounded; to switch index bounds checks off for what follows int tk; word tv; int tglue, tline, line = 1, ch, chkind; word chptr, chbase; int qdone, isp = -1, pendot; // where the current token sits in its source (chars from the start, -1 for a token list), how long it is, and where the one before it ended int toff = -1, toklen, tpend = -1, tpline; @@ -240,7 +244,7 @@ int pk_tk, pk_tv, pq_n; word[4] pq_tk; word[4] pq_tv; word[4] pq_gl; word[4] pq_ int here, hdelta, hlimit, ptop; int code_chunk = rt.CODE_END; word image_buffer, image_words; int image_active, image_org, image_capacity, image_size; -int nloc, lbase, fdepth, fslots, fchk, fret, live, bxdepth, epichain, fframe, infn; +int nloc, lbase, fdepth, fslots, fchk, fbnd, bnxt, fret, live, bxdepth, epichain, fframe, infn; // a global that borrows a local owner through g = m*x. each entry is the global's // symbol, the local, and the block depth of the store; the lend ends when the same // global is assigned again in that block, and is an error if the block can end first. @@ -271,7 +275,7 @@ int lv, lvk, lvi, kw_expr, xcls, fty; int s_lp, s_rp, s_lb, s_rb, s_lk, s_rk, s_comma, s_semi, s_eq, s_arrow, s_inc, s_dec; int s_star, s_slash, s_amp, s_colon, s_hash, s_minus, s_andand, s_oror; -int s_dot, s_fn, s_var, s_const, s_else, s_as, s_unchecked, s_immediate, s_m, s_d, s_u; +int s_dot, s_fn, s_var, s_const, s_else, s_as, s_unchecked, s_unbounded, s_immediate, s_m, s_d, s_u; int s_q, s_case, s_default, s_fovf, s_start, s_main, s_free, s_recycle, s_own, s_qnew, s_enhance, s_micro, s_vm; int s_frame_floor, s_frame_top, s_frame_node, s_frame_busy, s_frame_guard, s_frame_grow, s_frame_leave; int s_copy_w; @@ -310,7 +314,7 @@ word readonly_types; int dty, dtag; // result of dtype() int s_typedef; int s_lt, s_gt, s_shr, s_le, s_ge, s_eqeq, s_ne, s_plus, s_struct, s_type, s_typecheck, s_docs, s_lines, s_small, s_std, s_icon, s_on, s_off, s_new, s_new_t; -int s_o3, s_lfa, s_outside, s_new_raw, s_new_oz, s_oob; +int s_o3, s_lfa, s_outside, s_new_raw, s_new_oz, s_oob, s_bchk, s_bnd; int s_ld8, s_st8, s_ld16, s_st16, s_ld32, s_st32; // ---- o3 region state ---- @@ -320,7 +324,7 @@ int o3on, o3nxt, o3one; word[32] o3sl; word[32] o3rg; int no3sl; word[O3_REGIONS word[8] o3free; int no3free, o3nreg; word[NL] o3cache_initial; word o3cache = o3cache_initial; int argloc, s_hitems, s_hlen, s_fatten; // operator names used by numeric type checks. word[12] numops; int nnumops, s_fixed, s_dlen, s_dcap, s_dnew, s_dat, s_dpush, s_dpop, s_dresize, xconst, xcval; -int xlenloc, arrloc, fortest, forstep, ft_iv, ft_bd, ft_ir, ft_nops, fs_ok, xstamp; +int xlenloc, arrloc, fortest, forstep, ft_iv, ft_bd, ft_ir, ft_ck, ft_nops, fs_ok, xstamp; // local lower bound / len(array); one proof record per live loop int nfact, factcap = RANGE_FACTS; word[RANGE_FACTS] floc_initial, flo_initial, flen_initial; word floc = floc_initial, flo = flo_initial, flen = flen_initial; int s_len_s, s_at_s, s_slice_s, s_cat_s, s_eq_s, s_lt_s, s_le_s, s_put_bs, s_put_s, s_n_to_s, s_new_s; diff --git a/src/compiler/builtins.zc b/src/compiler/builtins.zc index d6a58fb..214d493 100644 --- a/src/compiler/builtins.zc +++ b/src/compiler/builtins.zc @@ -1191,6 +1191,7 @@ int types_init() { s_outside = intern("rt.outside"); s_new_raw = intern("rt.new_raw"); s_oob = intern("rt.oob"); + s_bchk = intern("rt.bchk"); s_bnd = intern("rt.bnd"); s_new_oz = intern("rt.new_oz"); s_ld8 = intern("rt.ld8"); s_st8 = intern("rt.st8"); s_ld16 = intern("rt.ld16"); s_st16 = intern("rt.st16"); s_ld32 = intern("rt.ld32"); s_st32 = intern("rt.st32"); diff --git a/src/compiler/check.zc b/src/compiler/check.zc index f3374b1..945b800 100644 --- a/src/compiler/check.zc +++ b/src/compiler/check.zc @@ -32,7 +32,7 @@ int chk_reset() { defer_drop(0); dfr_base = 0; dfr_on = 0; fdepth = 0; fslots = 0; - fchk = 0; + fchk = 0; fbnd = 0; bnxt = 0; fret = 0; live = 0; bxdepth = 0; @@ -41,7 +41,7 @@ int chk_reset() { xbor = 0 - 1; xaf = 0; argfact = 0; xvk = 0; if (svkind) rt.fill_w(svkind, 0, symcap); mdbg = 0; mdbg_flags = 0; lv = 0; lvk = 0; lvi = 0; kw_expr = 0; xcls = 0; fty = 0; - check_on = 1; tc_on = ifstrict; dry = 0; ntp = 0; tvauto = 0; ngbind = 0; xgive = 0; xconst = 0; + check_on = 1; bound_on = 1; tc_on = ifstrict; dry = 0; ntp = 0; tvauto = 0; ngbind = 0; xgive = 0; xconst = 0; o3on = 0; o3nxt = 0; no3pend = 0; no3sl = 0; no3free = 0; o3nreg = 0; o3na = 0; o3fn0 = 0; nfact = 0; fortest = 0; forstep = 0; argloc = 0; arrloc = 0; njps = 0; extop = 0; nnumops = 0; nenh = 0; panic = 0; nerr = 0; dgprev = 0; nclo = 0; newsz = 0 - 1; nomagic = 0; callpos = 0; diff --git a/src/compiler/decl.zc b/src/compiler/decl.zc index 2c8d13e..371e8e8 100644 --- a/src/compiler/decl.zc +++ b/src/compiler/decl.zc @@ -153,7 +153,7 @@ int unit_stdin() { // that a nested compile would otherwise clobber (locals, depth, frame size, // loop stack position, the expression-state globals). closures use the same // pair. -const int CTX_WORDS = 49; +const int CTX_WORDS = 50; int ctx_push() { af_forget(); word f; @@ -164,7 +164,7 @@ int ctx_push() { f[13] = lv; f[14] = lvk; f[15] = lvi; f[16] = kw_expr; f[17] = xcls; f[18] = snaptop; f[19] = fty; f[20] = ntp; f[21] = xty; rt.copy_w(f + 22, tpn, 8); f[30] = finsym; f[31] = finfer; f[32] = ifcur; f[33] = ifcall; f[34] = effect_current; f[35] = borrow_slots; f[36] = borrow_pending; f[37] = borrow_depth; f[38] = borrow_jump; f[39] = borrow_entry; f[40] = capture_enabled; f[41] = effect_value; f[42] = xprojection; f[43] = effect_floor; f[44] = module_name; f[45] = module_imports; - f[46] = fn_return_type; f[47] = if_value; f[48] = dfr_base; + f[46] = fn_return_type; f[47] = if_value; f[48] = dfr_base; f[49] = fbnd; return 0; } // pop the innermost function context. @@ -186,7 +186,7 @@ int ctx_pop() { lv = f[13]; lvk = f[14]; lvi = f[15]; kw_expr = f[16]; xcls = f[17]; snaptop = f[18]; fty = f[19]; ntp = f[20]; xty = f[21]; rt.copy_w(tpn, f + 22, 8); finsym = f[30]; finfer = f[31]; ifcur = f[32]; ifcall = f[33]; effect_current = f[34]; borrow_slots = f[35]; borrow_pending = f[36]; borrow_depth = f[37]; borrow_jump = f[38]; borrow_entry = f[39]; capture_enabled = f[40]; effect_value = f[41]; xprojection = f[42]; effect_floor = f[43]; module_name = f[44]; module_imports = f[45]; xvk = 0; - fn_return_type = f[46]; if_value = f[47]; + fn_return_type = f[46]; if_value = f[47]; fbnd = f[49]; return 0; } @@ -206,10 +206,12 @@ int fn_begin(int chk, int ret) { if (cmode && svkind && !dry) rt.fill_w(svkind, 0, nsym); xvk = 0; lend_drop(1 << 30, nloc); dfr_base = ndfr; - lbase = nloc; fdepth = 1; fslots = 0; fchk = chk && check_on; fret = ret; fty = 0; finfer = 0; fn_return_type = 0; + lbase = nloc; fdepth = 1; fslots = 0; fchk = chk && check_on; fbnd = !bnxt && bound_on; bnxt = 0; fret = ret; fty = 0; finfer = 0; fn_return_type = 0; live = 1; bxdepth = 0; epichain = 0; infn = 1; loopbase = lsp; lv = 0; lvk = LV_NONE; xbor = -1; return 0; } +// the bounds flag of the function that was being compiled when the innermost context was pushed +int ctx_bnd() { return R_CTX[(ctxsp - 1) * CTX_WORDS + 49]; } // allocate the frame, retaining the caller's pointer until any growth finishes. int prologue() { int k, busy, done, helper = !nclo && (sname[finsym] == s_frame_grow || sname[finsym] == s_frame_leave); @@ -578,7 +580,7 @@ int topsync() { if (is_op(s_lb)) depth++; else if (is_op(s_rb)) { depth--; if (depth < 0) depth = 0; } else if (!depth && tk == T_ID && (tv == s_fn || tv == s_var || tv == s_const || tv == s_struct || tv == s_type || tv == s_typedef - || tv == s_enhance || tv == s_typecheck || tv == s_docs || tv == s_lines || tv == s_unchecked || tv == s_immediate || tv == s_o3 + || tv == s_enhance || tv == s_typecheck || tv == s_docs || tv == s_lines || tv == s_unchecked || tv == s_unbounded || tv == s_immediate || tv == s_o3 || tv == s_memdebug || tv == s_enum || tv == s_include)) break; next(); } @@ -655,14 +657,20 @@ int topitem0() { int topitem1() { int chk = 1, imm = 0, s, k, n; if (panic) return topsync(); - if (is_id(s_unchecked)) { - next(); - if (accept(s_semi)) { check_on = 0; return 0; } // unchecked; switches the analyzer off from here on - chk = 0; + o3nxt = 0; bnxt = 0; + while (1) { // the prefixes, in any order + if (is_id(s_unchecked)) { + next(); + if (accept(s_semi)) { check_on = 0; return 0; } // unchecked; switches the analyzer off from here on + chk = 0; + } else if (is_id(s_unbounded)) { + next(); + if (accept(s_semi)) { bound_on = 0; return 0; } // unbounded; switches the index bounds checks off from here on + bnxt = 1; + } else if (is_id(s_immediate)) { next(); imm = 1; } + else if (is_id(s_o3)) { next(); o3nxt = 1; } + else break; } - if (is_id(s_immediate)) { next(); imm = 1; } - o3nxt = 0; - if (is_id(s_o3)) { next(); o3nxt = 1; } ntp = 0; ifkk = 0; if (is_id(s_fn)) { peek(); @@ -677,7 +685,7 @@ int topitem1() { return fndone(fndef(chk, 0, 0, n), imm); } } - if (!chk || imm || o3nxt) { // has to be a function, with a return type + if (!chk || imm || o3nxt || bnxt) { // has to be a function, with a return type ifkp = tpack(); ifkk = 0 - 1; if (is_op(s_dot)) ifkk = 2; if (isp != 0) ifkk = 0; rettype(); n = name(); if (ginst) n = ginsn; genparams(); diff --git a/src/compiler/expr.zc b/src/compiler/expr.zc index 95ce67b..230a2d3 100644 --- a/src/compiler/expr.zc +++ b/src/compiler/expr.zc @@ -678,7 +678,7 @@ int closure() { nclo++; hop = hole(); op(O_JMP); entry = here; - fn_begin(1, 0); + fn_begin(1, 0); fbnd = ctx_bnd(); lt = lt_begin(entry, "<closure>", lfl); if (declared) fty = declared; prologue(); borrow_prologue(); @@ -1321,17 +1321,49 @@ int range_jz(int ix, int src, int fld) { setlit(k, here); return 0; } +// the inline check of a fixed array T[n]: the index is on top of the stack and +// stays there. i is outside 0..n-1 exactly when i | (n - 1 - i) is negative: +// one subtract, one or and one compare, then a branch to the oob report. no +// enhancement: the x86-64 jit calls one rather than inlining it. +int fixed_chk(int n) { + int j; + lit(0); op(O_PICK); lit(n - 1); op(O_SWAP); op(O_SUB); + lit(1); op(O_PICK); op(17); + lit(0); op(O_LT); + j = hole(); op(O_JZ); + lit(n); callname(s_oob); + setlit(j, here); + return 0; +} +// the check of a pointer index: base and index are on the stack and stay there. +// the runtime knows a size only for a pointer to the start of a live heap block +// and returns at once for any other pointer. sz is the element size in words, or +// minus the element size in bytes for packed elements. +int ptr_chk(int sz) { + int k = lookup(s_bnd), j; + if (k >= 0 && skind[k] == K_ENH) { // the test is one enhancement; the call only runs to report + lit(1); op(O_PICK); lit(1); op(O_PICK); + if (sz > 0) { lit(sz); lit(1); } else { lit(0 - sz); lit(8); } + op(XOP0 + sval[k]); + j = hole(); op(O_JZ); + } + lit(1); op(O_PICK); lit(1); op(O_PICK); lit(sz); callname(s_bchk); op(O_DROP); + if (k >= 0 && skind[k] == K_ENH) setlit(j, here); + return 0; +} // suffixes after a primary, in a loop: e as T, [index], .field, ->field, // (call through a value), ++ and --. the index case is the long one. a byte -// string takes an index or a slice. a growable array is checked: through dat() -// normally, but inline when the compiler can prove or cheaply test the bound -// (o3 code with the cache variables, or an index the loop test already -// compared with the length). a plain pointer or fixed array is just base + -// index * size, and a constant index against a known length is checked at -// compile time. +// string takes an index or a slice. every index is bounds checked unless the +// function, block or unit is unbounded or the code is o3. a growable array is +// checked through dat() normally, but inline when the compiler can prove or +// cheaply test the bound (o3 code with the cache variables, or an index the +// loop test already compared with the length). a fixed array T[n] is checked +// inline against n (at compile time for a constant index, not at all when a +// loop test against a constant already proved it). a plain pointer goes +// through rt.bchk, which only knows the size of a heap block's first word. int postfix() { return postfix_tail(primary()); } int postfix_tail(int c) { - int b, n, t, et; word ft; word[8] bs; int k, ci, was, al, ix, enh, cz, cj, place, offset, temporary, call_owner, readonly; word storage, storage_mask, call_origins; + int b, n, t, et; word ft; word[8] bs; int k, ci, was, al, ix, enh, cz, cj, place, offset, temporary, call_owner, readonly, ub, bl, ic, inr; word storage, storage_mask, call_origins; while (1) { if (tk == T_ID && tv == s_as) { // e as T: same bits, another type next(); t = ptype(); rval(); if (!xaf || xaf[2] != 5) xaf = 0; vf_coerce(t, 0); @@ -1350,6 +1382,8 @@ int postfix_tail(int c) { ci = 0; if (lv && lvk == LV_LOCAL) lptr[lvi] = 1; if (o3on && lv && lvk == LV_LOCAL && o3cache[lvi]) ci = o3cache[lvi]; + ub = !fbnd || o3on || (lv && lvk == LV_LOCAL && (ltag[lvi] & 16)); // unbounded, or o3 code + bl = -1; if (lv && lvk == LV_LOCAL) bl = lvi; next(); rval(); if (was) { @@ -1377,7 +1411,11 @@ int postfix_tail(int c) { if (xconst) offset = xcval; af_index(storage, place); tcneed(isnum(xty) || xty == tword, "an index has to be a number", xty); expect(s_rk); - callname(intern("datb")); + if (ub) { // the byte address of the element, with no check + op(O_SWAP); lit(2); op(O_ADD); op(O_LD); lit(8); op(15); op(O_SWAP); + if (tbytes(et) != 1) { lit(tbytes(et)); op(15); } + op(O_ADD); + } else callname(intern("datb")); et = tpk(et); } else if (xty[0] == TY_DYN) { // a growable array: bounds-checked, through the runtime et = xty[4]; @@ -1393,7 +1431,10 @@ int postfix_tail(int c) { expect(s_rk); k = lookup(s_outside); enh = k >= 0 && skind[k] == K_ENH; - if (!mdbg && ix >= 0 && al >= 0 && proven(al, ix)) { // the loop test already compared this index with the length + if (ub) { // unbounded, or o3: just the address + if (ci && !mdbg && lookup(s_outside) >= 0) { vaddr(ci); op(O_LD); op(O_SWAP); mulsz(et); op(O_ADD); } + else addr_stk(et); + } else if (!mdbg && ix >= 0 && al >= 0 && proven(al, ix)) { // the loop test already compared this index with the length if (ci) { vaddr(ci); op(O_LD); op(O_SWAP); mulsz(et); op(O_ADD); } else addr_stk(et); } else if (ci && !mdbg && enh && ix >= 0) { @@ -1433,13 +1474,26 @@ int postfix_tail(int c) { et = telem(xty); n = 0 - 1; if (xty[0] == TY_ARR && xty[3] > 0) n = xty[3]; xconst = 0; - c = expr(); rval(); plainuse(c); + c = expr(); + ix = -1; + if (lv && lvk == LV_LOCAL) ix = lvi; + rval(); plainuse(c); + ic = xconst; if (xconst) offset = xcval; if (n < 0) af_index(storage, place); if (n >= 0 && xconst && (xcval < 0 || xcval >= n)) { serr("the index is out of range for this array"); } + inr = 0; // no check needed: the index is 0, or the analyzer knows it is inside the allocation + if (ic && xcval == 0) inr = 1; + if (ic && n < 0 && !tbytes(et) && tsz(et) == 1 && af_inrange(storage)) inr = 1; + if (bl >= 0 && n < 0 && larr[bl]) inr = 1; // an array in a frame has no heap header to read tcneed(isnum(xty) || xty == tword, "an index has to be a number", xty); expect(s_rk); + if (!ub && !inr) { + if (n >= 0) { if (!ic && !(ix >= 0 && proven_n(ix, n))) fixed_chk(n); } + else if (tbytes(et)) ptr_chk(0 - tbytes(et)); + else ptr_chk(tsz(et)); + } if (tbytes(et)) { // packed: byte address = base * 8 + index * bytes if (tbytes(et) != 1) { lit(tbytes(et)); op(15); } op(O_SWAP); lit(8); op(15); op(O_ADD); @@ -1671,6 +1725,7 @@ int bin(int minp) { if (c >= C_VAR && tracked(c - C_VAR)) rb = lroot(c - C_VAR); else rb = xbor; if (top) { ft_ir = -1; if (lv && lvk == LV_LOCAL) ft_ir = lvi; } rval(); plainuse(c); + if (top) { ft_ck = -1; if (xconst && xcval >= 0) ft_ck = xcval; } if (cmode && bname[b] == s_star && xconst && xcval >= 2 && !(xcval & (xcval - 1)) && !lf) { shifthint(opp, xcval); } @@ -1706,7 +1761,7 @@ int bin(int minp) { if (top) { ft_nops++; if (ft_nops > 1) ft_iv = -1; - else if (bname[b] == s_lt && blen[b] > 0 && il >= 0 && ft_ir >= 0 && !lf && !rf && !ls && !rs) { ft_iv = il; ft_bd = ft_ir; } + else if (bname[b] == s_lt && blen[b] > 0 && il >= 0 && (ft_ir >= 0 || ft_ck >= 0) && !lf && !rf && !ls && !rs) { ft_iv = il; ft_bd = ft_ir; } } lv = 0; lvk = LV_NONE; c = C_PLAIN; xzero = 0; xconst = 0; xlenloc = -1; xstamp = 0; xaf = 0; xvk = 0; effect_value = 0; if (isptr(xty) || xty == tword) effect_value = left_mask | right_mask; diff --git a/src/compiler/setup.zc b/src/compiler/setup.zc index 9ed938b..26a18e0 100644 --- a/src/compiler/setup.zc +++ b/src/compiler/setup.zc @@ -46,7 +46,7 @@ int zc_init() { s_andand = intern("&&"); s_oror = intern("||"); s_fn = intern("fn"); s_var = intern("let"); s_const = intern("const"); s_else = intern("else"); - s_as = intern("as"); s_unchecked = intern("unchecked"); s_immediate = intern("immediate"); + s_as = intern("as"); s_unchecked = intern("unchecked"); s_unbounded = intern("unbounded"); s_immediate = intern("immediate"); s_m = intern("m"); s_d = intern("d"); s_u = intern("u"); s_static = intern("static"); s_start = intern("run.start"); s_main = intern("main"); @@ -113,6 +113,7 @@ int zc_tables() { add_kw("defer", kw_defer, F_STMT); add_kw("return", kw_return, F_STMT); add_kw("unchecked", kw_unchecked, F_STMT); + add_kw("unbounded", kw_unbounded, F_STMT); add_kw("asm", kw_asm, F_STMT | F_EXPR); add_kw("quote", kw_quote, F_EXPR); add_kw("sizeof", kw_sizeof, F_EXPR); diff --git a/src/compiler/stmt.zc b/src/compiler/stmt.zc index 3ecb81b..a67b931 100644 --- a/src/compiler/stmt.zc +++ b/src/compiler/stmt.zc @@ -323,7 +323,7 @@ int kw_for() { borrow_cleanup_since(borrow_mark); s0 = snap_push(); c0 = here; - ft_iv = -1; fs_ok = 0; fortest = 1; + ft_iv = -1; ft_ck = -1; fs_ok = 0; fortest = 1; if (!is_op(s_semi)) { if (tk == T_NUM && tv) { peek(); if (pk_tk == T_OP && pk_tv == s_semi) inf = 1; } c = borrow_condition(); @@ -344,6 +344,8 @@ int kw_for() { loop_push(st, s0); if (ft_iv >= 0 && ft_bd >= 0 && fs_ok && getlo(ft_iv) >= 0 && getln(ft_bd) >= 0) { lpfact[lsp - 1] = pfact(ft_iv, ft_bd, getln(ft_bd)); + } else if (ft_iv >= 0 && ft_ck >= 0 && fs_ok && getlo(ft_iv) >= 0) { // i < constant: proves a fixed array that long + lpfact[lsp - 1] = pfact(ft_iv, -1, 0 - ft_ck - 2); } substmt(); backedge(s0); @@ -724,6 +726,17 @@ int kw_unchecked() { return 0; } +// unbounded turns the index bounds checks off for one statement +int kw_unbounded() { + int old = fbnd; + stmtonly(); + next(); + fbnd = 0; + substmt(); + fbnd = old; + return 0; +} + // ---- asm blocks: raw vm words, one per token ---- // numbers push, -n pushes a negative number, #n emits a raw word, one-char diff --git a/src/compiler/types.zc b/src/compiler/types.zc index 6dda110..ca31248 100644 --- a/src/compiler/types.zc +++ b/src/compiler/types.zc @@ -567,7 +567,7 @@ int kw_struct() { if (tk == T_EOF) { die("missing }"); break; } stat = 0; if (struct_const_start()) { struct_const(n); continue; } - if (is_id(s_unchecked)) { next(); stat = 2; } + while (is_id(s_unchecked) || is_id(s_unbounded)) { if (is_id(s_unchecked)) stat = stat | 2; else stat = stat | 4; next(); } if (is_id(s_static)) { // static fn name(params) { body }, or static T name(params) { body }: a function of the struct, called as Struct.name(args), with no this next(); stat = stat | 1; @@ -746,7 +746,7 @@ int tkput(word r, int k, int kind, int val, int pl) { } // compile a struct method once the struct is complete. int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) { - int n = q[0]; word r; int i, k = 0, lnp, unchecked_method = stat & 2; + int n = q[0]; word r; int i, k = 0, lnp, unchecked_method = stat & 2, unbounded_method = stat & 4, pc = (stat & 2) / 2 + (stat & 4) / 4; stat = stat & 1; if (!n) { rt.free(q); return 0; } if (!stat) { @@ -759,6 +759,7 @@ int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) r = rt.new((n + 8 + mdg * 4) * 3 + 1); lnp = q[3]; if (unchecked_method) k = tkput(r, k, T_ID, s_unchecked, lnp); + if (unbounded_method) k = tkput(r, k, T_ID, s_unbounded, lnp); k = tkput(r, k, T_ID, s_fn, lnp); r[1 + k * 3] = T_ID; r[2 + k * 3] = methname(sn, mn); r[3 + k * 3] = lnp; k++; if (mdg) { // a method of a generic struct is a generic function over the struct's parameters: fn S.m<K, V>(S<K, V>* this, ...) @@ -806,7 +807,7 @@ int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) rt.free(q); if (typed && mdg) { // retain a typed generic method as ordinary typed function tokens. - int mode = rt.outmode, length = rt.outn, capacity = rt.outcap, prefix = unchecked_method != 0; + int mode = rt.outmode, length = rt.outn, capacity = rt.outcap, prefix = pc; word output = rt.outbuf, grow = rt.outgrow, buffer = rt.new(4096), return_tokens, joined; rt.outmode = 2; rt.outbuf = m*buffer; rt.outn = 0; rt.outcap = 4095; rt.outgrow = 0; tprint(rty); if (rtag) rt.put_s(".u"); buffer[rt.outn] = 0; @@ -824,7 +825,7 @@ int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) } joined = rt.new((r[0] + return_tokens[0]) * 3 + 1); joined[0] = r[0] - 1 + return_tokens[0]; - if (prefix) rt.copy_w(joined + 1, r + 1, 3); + if (prefix) rt.copy_w(joined + 1, r + 1, prefix * 3); rt.copy_w(joined + 1 + prefix * 3, return_tokens + 1, return_tokens[0] * 3); rt.copy_w(joined + 1 + (prefix + return_tokens[0]) * 3, r + 1 + (prefix + 1) * 3, (r[0] - prefix - 1) * 3); rt.free(r); r = joined; rt.free(return_tokens); rt.free(buffer); diff --git a/src/core/core.zc b/src/core/core.zc index 61ecd1c..e730946 100644 --- a/src/core/core.zc +++ b/src/core/core.zc @@ -1,6 +1,9 @@ namespace core; include rt; +// the core pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // calls the host gate with an operation and three machine-word arguments. // returns the host result; negative values indicate a failed operation. int syscall(int operation, word a, word b, word c) { diff --git a/src/lib/actor.zc b/src/lib/actor.zc index 29fd600..a129f7f 100644 --- a/src/lib/actor.zc +++ b/src/lib/actor.zc @@ -53,11 +53,11 @@ unchecked int encode(word data, word refs, word address, word type) { } if (kind == 13) { n = rt.len_s(pointer); append(data, n); while (i < n) { append(data, rt.at_s(pointer, i)); i++; } return 0; } if (kind == 7) { - element = pointer[-1]; n = pointer[-5] - rt.HDR; + unbounded { element = pointer[-1]; n = pointer[-5] - rt.HDR; } // the object's header, on purpose append(data, n); append(data, element); encode(data, refs, pointer, element); return 0; } element = type[4]; bytes = packed(element); - if (rt.isobj(pointer)) n = pointer[-5] - rt.HDR; + if (rt.isobj(pointer)) { unbounded n = pointer[-5] - rt.HDR; } else if (element[0] == 2) n = rt.len_w(pointer) + 1; else n = size(element); append(data, n); diff --git a/src/lsp/server.zc b/src/lsp/server.zc index c3f9f4f..52e5e9a 100644 --- a/src/lsp/server.zc +++ b/src/lsp/server.zc @@ -1,6 +1,9 @@ namespace lsp; include rt, run; +// the server pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // ============================================================================ // server.zc: the language server. it is appended to the genome after the // compiler (the files of src/compiler/parts in order, then this one, read as one stream), so it does not @@ -388,7 +391,7 @@ int isopc(int c) { // is the name n one of the words the highlighter shows as keywords even when the // compiler has no record for it. int iskeyword(int n) { - return n == run.s_fn || n == run.s_var || n == run.s_const || n == run.s_else || n == run.s_as || n == run.s_unchecked || n == run.s_immediate + return n == run.s_fn || n == run.s_var || n == run.s_const || n == run.s_else || n == run.s_as || n == run.s_unchecked || n == run.s_unbounded || n == run.s_immediate || n == run.s_case || n == run.s_default || n == run.s_do || n == run.s_while || n == run.s_enum || n == run.s_include || n == run.s_memdebug || n == run.s_enhance || n == run.s_micro || n == run.s_vm || n == run.s_struct || n == run.s_type || n == run.s_typedef || n == run.s_typecheck || n == run.s_static; } @@ -1680,6 +1683,7 @@ char* kwtext() { if (hname_is("const")) return "const [type] NAME = e / const fixed T[N] name~declares a compile-time constant or read-only storage. fixed and const may appear in either order; read-only storage cannot be modified or converted to a mutable reference."; if (hname_is("else")) return "else~the other branch of an if. after an enhance's body, else names the fallback function that runs where the enhancement can't."; if (hname_is("as")) return "e as T~changes the type of an expression without changing its bits."; + if (hname_is("unbounded")) return "unbounded fn f() { } / unbounded { } / unbounded;~turns index bounds checks off for a function, a block, a statement, or the rest of the unit. o3 code is unbounded too."; if (hname_is("unchecked")) return "unchecked fn f() { } / unchecked { } / unchecked;~turns the lifetime analyzer off for a function, a block, or the rest of the unit. the code is not checked, so the analyzer's rules don't apply to it."; if (hname_is("immediate")) return "immediate fn name() { }~a parse word. it runs during compilation whenever its name shows up as a statement, inside an expression or at the top level."; if (hname_is("case")) return "case v:~a label in a switch. each case ends where the next one begins, so cases don't fall through."; diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc index 7018915..a181387 100644 --- a/src/runtime/rt.zc +++ b/src/runtime/rt.zc @@ -1,6 +1,9 @@ namespace rt; include run; +// the runtime pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // ============================================================================ // rt.zc: the runtime half of the genome. memory map, i/o, arithmetic helpers, // the heap (size-class free lists) and the mark-sweep collector. @@ -84,6 +87,13 @@ enhance ishl(a, b) micro "a = shl a b"; enhance lfa(k) micro "r1 = ld 589824; k = add r1 k"; // 1 when i is outside 0..n-1 (the unsigned compare also catches negative i), else 0. enhance outside(i, n) micro "i = ltu i n; i = xor i 1"; +// the index check of a pointer, as one instruction: 1 when p is the start of a heap +// block (its check word p[-3] is p ^ MAGIC) and the byte or word offset i * m is not +// inside the block's payload (q units per word: 1 for word elements, 8 for packed +// ones), else 0. a load outside memory reads 0, so any p is safe to ask about. the +// payload is paylen (p[-5] - HDR words, at most the size an o3 raw block was asked for, +// which is the complement of its type word p[-1] when that is negative). see bchk. +enhance bnd(p, i, m, q) micro "r6 = sub p 3; r6 = ld r6; r7 = xor p 0x2B7E1516; r6 = eq r6 r7; r7 = sub p 5; r7 = ld r7; r7 = sub r7 5; r8 = sub p 1; r8 = ld r8; r8 = not r8; r7 = minu r7 r8; r7 = mul r7 q; r8 = mul i m; r8 = ltu r8 r7; r8 = xor r8 1; r0 = and r6 r8"; // ---- bit operations and float conversions ---- // these use single machine instructions where the cpu has them. @@ -1101,6 +1111,27 @@ word dat(word h, int i) { if (i < 0 || i >= h[0]) oob(i, h[0]); return h[2] + i * h[3]; } +// the bounds check of p[i] on a pointer (or an untyped word), emitted by the compiler +// in front of the access. a pointer has no length, but a pointer to the start of +// a heap block does have one: the words the block holds (paylen). for any +// other pointer (the middle of a block, a frame, a global, memory managed by hand) +// nothing is known and this returns at once. sz is the element size in words, or +// minus the element size in bytes for packed elements. the length is the block's +// payload, which a buddy block rounds up to a power of two; an o3 raw block is exact. +int bchk(word p, int i, int sz) { + int n; + if (p < HEAP_LO + HDR || p >= hbump || p[-3] != (p ^ MAGIC)) return 0; + n = paylen(p); + if (sz > 0) { + if (i >= 0 && i < n && i * sz < n) return 0; + oob(i, (n + sz - 1) / sz); + return 0; + } + sz = 0 - sz; n = n * 8; + if (i >= 0 && i < n && i * sz < n) return 0; + oob(i, (n + sz - 1) / sz); + return 0; +} // add x to the end of a growable array h, growing its items when they are full. the // array owns the items, so x is handed to it (tagged d). unchecked int dpush(word h, .d x) { @@ -1316,7 +1347,7 @@ int scrub() { // dbg bits: 1 header checks and allocation sites, 2 poison the payload on free // (the word 57005, which is 0xDEAD), 4 interior pointers keep a quarantined -// block (the mark walks back at most 64 words to a real header). off unless +// block (obj_base finds its header from the size classes). off unless // a program requests. sites are p ^ MAGIC so the collector does not treat them as pointers. const int NSITE = 64; @@ -1325,17 +1356,26 @@ int site_drop; word[64] site_p; word[64] site_line; // true when p is a freed block still held in quarantine. word quar(word p) { return p >= HEAP_LO + HDR && p < hbump && p[-3] == (p ^ MAGIC) && !(p[-4] & 1); } -// the object whose payload contains w, or 0. exact pointers and interiors. +// the object whose payload contains w, or 0. exact pointers and interiors, at any +// depth. every block of class k starts at HEAP_LO plus a multiple of 2^k words, so +// the block holding w, if any, starts at w rounded down to one of those. the +// candidates are tried from the largest class down: a header counts only when its +// check word, size and class agree with k, and the first that holds w in its +// payload is the block. a merge clears the upper half's header and a split rewrites +// the header at the same address, so a stale header can only sit inside the +// payload of the real block, which is found first. word obj_base(int w) { - int i = 0; word p; int n; + int k = 31, off, sz; word b, p; if (w < HEAP_LO + HDR || w >= hbump) return 0; - while (i <= 64) { - p = w - i; - if (p >= HEAP_LO + HDR && p < hbump && p[-3] == (p ^ MAGIC)) { - n = p[-5] - HDR; - if (w >= p && w < p + n) return p; + off = w - HEAP_LO; + while (k >= 3) { + sz = pow2[k]; + b = HEAP_LO + off - off % sz; + p = b + HDR; + if (sz <= hbump - HEAP_LO && p < hbump && b[0] == sz && p[-3] == (p ^ MAGIC) && bclass(b) == k) { + if (w >= p && w < b + sz) return p; } - i++; + k--; } return 0; } diff --git a/src/runtime/run.zc b/src/runtime/run.zc index 19a5234..69fc30c 100644 --- a/src/runtime/run.zc +++ b/src/runtime/run.zc @@ -1,6 +1,9 @@ namespace run; include rt; +// the run-only runtime pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // run-only image: the runtime, a collector root set, and start. there is no // resident compiler and none of its tables. put this between rt.zc and a // program that defines main. zc0 accepts the bootstrap subset; build.zc uses diff --git a/src/tools/build.zc b/src/tools/build.zc index b628a33..b2f838f 100644 --- a/src/tools/build.zc +++ b/src/tools/build.zc @@ -1,6 +1,9 @@ namespace; include rt, run; +// the build tool pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // compiles the rest of stdin (after the backtick) as a genome image at GORG // and writes it to stdout as little-endian 64-bit words. diff --git a/src/tools/zc0.c b/src/tools/zc0.c index e673eee..81561ce 100644 --- a/src/tools/zc0.c +++ b/src/tools/zc0.c @@ -476,7 +476,7 @@ static int notatype(void) static const char *w[] = { "return", "if", "else", "while", "for", "do", "break", "continue", "let", "var", "fn", "const", "enhance", "struct", "enum", "asm", "switch", "case", "default", "immediate", "type", "include", "as", "in", "new", "sizeof", "typeof", - "o3", "unchecked", 0 }; + "o3", "unchecked", "unbounded", 0 }; int i; if (tk != T_ID) return 0; for (i = 0; w[i]; i++) if (!strcmp(ts, w[i])) return 1; @@ -782,7 +782,7 @@ static void stmt(void) expect(";"); return; } } - if (accept("unchecked")) { stmt(); return; } + if (accept("unchecked") || accept("unbounded")) { stmt(); return; } if (accept("if")) { expect("("); expr(); rval(); ftest(); expect(")"); a = here; lit(0); op(O_JZ); stmt(); @@ -1027,6 +1027,7 @@ static void top1(void) } if (accept("embed")) { embeddecl(0); return; } { + if (accept("unbounded")) { if (accept(";")) return; top1(); return; } if (accept("unchecked")) { top1(); return; } if (accept("fn")) { fndef(0, 0); return; } if (accept("const")) { optype(); do { char *n = ident(); if (dsn && !dnm[0]) strcpy(dnm, n); expect("="); add(n, K_CONST, cexpr()); } while (accept(",")); expect(";"); return; } diff --git a/tests/parity.known b/tests/parity.known index 0a73eb3..6892499 100644 --- a/tests/parity.known +++ b/tests/parity.known @@ -13,3 +13,6 @@ tests/programs/uaf_in.zc # memdebug on: only the self-hosted compiler emits the examples/lists.zc # ownership: the block's owner frees at its end, zc0 never frees # the next program reads a local it never sets when stdin is empty, so it prints stack garbage tests/programs/bench_strings.zc # reads the repeat count from stdin; with none, acc is uninitialized +# zc0 reads unbounded and ignores it, and emits no index checks at all +tests/programs/bounds_fixed.zc # bounds checks: only the self-hosted compiler checks a fixed array index +tests/programs/bounds_heap.zc # bounds checks: only the self-hosted compiler checks a pointer into a heap block diff --git a/tests/programs/bounds_fixed.zc b/tests/programs/bounds_fixed.zc new file mode 100644 index 0000000..0b3f476 --- /dev/null +++ b/tests/programs/bounds_fixed.zc @@ -0,0 +1,17 @@ +namespace; +include rt; + +// a fixed array T[n] with a variable index is checked against n. a loop whose +// test is the constant n proves the index and drops the check; a constant +// index is checked when it is compiled. +int main() { + int[6] t; int i, s = 0, k = 6; + for (i = 0; i < 6; i++) t[i] = i * i; + for (i = 0; i < 6; i++) s = s + t[i]; + rt.put_n(s); rt.put_c(10); + i = 2; rt.put_n(t[i] + t[5]); rt.put_c(10); + i = 0; + while (i <= k) { s = t[i]; i++; } + rt.put_s("not reached\n"); + return 0; +} diff --git a/tests/programs/bounds_heap.zc b/tests/programs/bounds_heap.zc new file mode 100644 index 0000000..d0bd318 --- /dev/null +++ b/tests/programs/bounds_heap.zc @@ -0,0 +1,16 @@ +namespace; +include rt; + +// a pointer to the start of a live heap block is checked against the block's +// payload, which a buddy block rounds up: rt.new(4) holds 11 words. a pointer +// into the middle of a block, or to memory that is not a heap block, is not +// checked. a char is a word, so a char* counts words. +int main() { + int* p = rt.new(4); int* q; char* c = rt.new(2); int i = 10; + p[i] = 3; rt.put_n(p[i]); rt.put_c(10); + q = p + 1; i = 10; rt.put_n(q[i - 1] - 3); rt.put_c(10); + i = 2; c[i] = 'x'; rt.put_c(c[i]); rt.put_c(10); + i = 11; + rt.put_n(p[i]); rt.put_c(10); + return 0; +} diff --git a/tests/programs/bounds_hi.zc b/tests/programs/bounds_hi.zc index 49639c5..5475764 100644 --- a/tests/programs/bounds_hi.zc +++ b/tests/programs/bounds_hi.zc @@ -1,7 +1,8 @@ namespace; include rt; -// the index is not the induction variable. i + 1 walks off the end. +// the index is not the induction variable. i + 1 walks off the end, but o3 +// implies unbounded: nothing checks it, and the write lands in the block's slack o3 fn main() { fixed int[?] f = rt.new(fixed int[?], 4); int n = len(f), i; diff --git a/tests/programs/boundsrules.zc b/tests/programs/boundsrules.zc new file mode 100644 index 0000000..1ae6a56 --- /dev/null +++ b/tests/programs/boundsrules.zc @@ -0,0 +1,24 @@ +namespace; +include rt; + +// unbounded turns the checks off: as a function prefix (in any order with +// unchecked), as a block, for one statement. o3 implies it. the last read is +// checked and stops the program. +int[8] pad; +int[4] a; + +unbounded int pre(int i) { return a[i] * 0 + 1; } +unchecked unbounded int both(int i) { return a[i] * 0 + 1; } +o3 int fast(int i) { return a[i] * 0 + 1; } +int blk(int i) { int r = 0; unbounded { r = a[i] * 0 + 1; } return r; } +int one(int i) { int r = 0; unbounded r = a[i] * 0 + 1; return r; } +int checked(int i) { return a[i]; } + +int main() { + int i = 5; + a[3] = 7; + rt.put_n(pre(i) + both(i) + fast(i) + blk(i) + one(i)); rt.put_c(10); + rt.put_n(checked(3)); rt.put_c(10); + rt.put_n(checked(i)); rt.put_c(10); + return 0; +} diff --git a/tests/programs/memdebug_interior.expected b/tests/programs/memdebug_interior.expected new file mode 100644 index 0000000..580692a --- /dev/null +++ b/tests/programs/memdebug_interior.expected @@ -0,0 +1 @@ +7 3 2 diff --git a/tests/programs/memdebug_interior.zc b/tests/programs/memdebug_interior.zc new file mode 100644 index 0000000..8464f2c --- /dev/null +++ b/tests/programs/memdebug_interior.zc @@ -0,0 +1,18 @@ +namespace; +include rt; + +// memdebug finds the block of an interior pointer however deep it is: buf[255] +// of a 256-word block is 255 words past its header, beyond the old 64-word scan. +memdebug on; +fn main() { + let buf = rt.new(256), small = rt.new(4); + buf[255] = 7; + buf[100] = 3; + small[3] = 2; + rt.put_n(buf[255]); rt.put_c(32); + rt.put_n(buf[100]); rt.put_c(32); + rt.put_n(small[3]); rt.put_c(10); + rt.free(small); + rt.free(buf); + return 0; +} diff --git a/tests/programs/o3_bounds.zc b/tests/programs/o3_bounds.zc index eaf92eb..cd65548 100644 --- a/tests/programs/o3_bounds.zc +++ b/tests/programs/o3_bounds.zc @@ -1,5 +1,6 @@ namespace; include rt; -// an index outside a T[?] inside o3 code: caught by the inline check +// an index outside a T[?] inside o3 code: o3 implies unbounded, so nothing checks it +// (the write lands in the slack of the buddy block) and the program ends normally fn main() { int[?] a = rt.new(int[?], 5); o3 { int i = 7; a[i] = 1; } rt.free(d*a); return 0; } diff --git a/tests/programs/o3call.zc b/tests/programs/o3call.zc index d2292ad..3ad977b 100644 --- a/tests/programs/o3call.zc +++ b/tests/programs/o3call.zc @@ -19,7 +19,7 @@ unchecked o3 int nest(int n) { if (n == 0) return 0; return n + nest(n - 1); } -unchecked fn main() { +unchecked unbounded fn main() { // reads p[-1], the type word, on purpose node* n = leaf(4); int* p = n; rt.put_n(p[-1] < 0); rt.put_c(' '); diff --git a/tests/programs/zc0unbounded.zc b/tests/programs/zc0unbounded.zc new file mode 100644 index 0000000..67c3ae0 --- /dev/null +++ b/tests/programs/zc0unbounded.zc @@ -0,0 +1,16 @@ +namespace; +include rt; + +// unbounded in all three places zc0 accepts it (and ignores): the unit, a +// function prefix and a statement. both compilers print the same. +unbounded; +int[4] a; +unbounded int get(int i) { return a[i]; } +int main() { + int i = 2, r = 0; + a[2] = 40; + unbounded r = get(i) + 2; + unbounded { r = r + a[i - 2]; } + rt.put_n(r); rt.put_c(10); + return 0; +} diff --git a/tests/test.sh b/tests/test.sh index 37fa71c..7a80c3c 100755 --- a/tests/test.sh +++ b/tests/test.sh @@ -188,6 +188,7 @@ ABC" "$l o3 lifts byte loads and stores" chk "$($vm < tests/programs/strings.zc)" "hi! 3 3 104 i! 1 1 1 -42 42 -42 11 1 -9223372036854775808 0 1 3 10 1 1 1 W ab" "$l byte strings" chk "$($vm < tests/programs/share.zc)" "1 2 1 4 1 1 1 1 42 1 1 1 6 0" "$l shared cons cells" chk "$($vm < tests/programs/share_dbg.zc)" "7 1" "$l memdebug accepts a shared cell" + chk "$($vm < tests/programs/memdebug_interior.zc | md5sum)" "$(md5sum < tests/programs/memdebug_interior.expected)" "$l memdebug finds the block of a deep interior pointer" chk "$($vm < tests/programs/global_transfer.zc)" "5 9" "$l an m or u owner stored in a global is transferred" chk "$($vm < tests/programs/closure_result.zc)" "8 1.500000" "$l a closure with a declared result type" chk "$($vm < examples/strings.zc)" "hello, zc @@ -219,10 +220,14 @@ ABC" "$l o3 lifts byte loads and stores" chk "$($vm < tests/programs/o3licm.zc)" "3184200 7950 315 50 260 -56" "$l o3 hoists loop invariants and shares values between blocks" chk "$($vm < tests/programs/o3deep.zc)" "30000" "$l o3 recursion thirty thousand deep" chk "$($vm < tests/programs/o3deep_over.zc 2>&1)" "100000" "$l o3 recursion grows past the original stack" - chk "$($vm < tests/programs/o3_bounds.zc 2>&1 | head -1)" "zy: index 7 out of range (length 5)" "$l o3 bounds check" + chk "$($vm < tests/programs/o3_bounds.zc 2>&1; echo "rc=$?")" "rc=0" "$l o3 implies unbounded: no check on a T[?] index" chk "$($vm < tests/programs/bounds.zc)" "55 55 8" "$l a proved +1 loop skips the bounds check" chk "$($vm < tests/programs/bounds_lo.zc 2>&1 | head -1)" "zy: index -1 out of range (length 4)" "$l a negative loop index is still checked" - chk "$($vm < tests/programs/bounds_hi.zc 2>&1 | head -1)" "zy: index 4 out of range (length 4)" "$l an index that is not the induction variable is still checked" + chk "$($vm < tests/programs/bounds_hi.zc 2>&1; echo "rc=$?")" "rc=0" "$l o3 implies unbounded: an index that is not the induction variable is not checked" + chk "$($vm < tests/programs/boundsrules.zc 2>&1 | head -3)" $'5\n7\nzy: index 5 out of range (length 4)' "$l unbounded as prefix, block and statement, o3 implies it; checked code reports" + chk "$($vm < tests/programs/bounds_fixed.zc 2>&1 | head -3)" $'55\n29\nzy: index 6 out of range (length 6)' "$l a fixed array with a variable index is checked against its length" + chk "$($vm < tests/programs/bounds_heap.zc 2>&1 | head -4)" $'3\n0\nx\nzy: index 11 out of range (length 11)' "$l a pointer to a heap block is checked against its payload" + chk "$($vm < tests/programs/zc0unbounded.zc)" "42" "$l unbounded in the unit, a prefix and a statement" local r; r=$(bash tests/runerr.sh "$vm" tests/errors | tail -1) chk "$r" "rejected: $(ls tests/errors/*.zc | wc -l | tr -d ' ') passed, 0 failed" "$l analyzer rejects every bad program" r=$(bash tests/runerr.sh "$vm" tests/typeerrors | tail -1) @@ -356,7 +361,7 @@ s_runonly() { runonly() { # $1 label, $2 source. the program is already in the image, so it reads no source. # the map is sized to the program: src/tools/automap.sh lays it out for the image's own length local a b d=$T/run-$1 input=$2 - if [ "$1" = gc ]; then input=$T/collector-progress.zc; sed 's/f >= 990/f > 0/' "$2" > "$input"; fi + if [ "$1" = gc ]; then input=$T/collector-progress.zc; sed 's/f >= 950/f > 0/' "$2" > "$input"; fi GENMAP=$T/genmap bash src/tools/automap.sh run $d src/runtime/run.zc "$input" >/dev/null || { chk 0 1 "run $1 builds"; return; } cp src/micro/micro.c src/micro/micro_port.h src/micro/port_linux.c src/micro/port_stub.c src/core/fops.h src/core/bops.h src/core/stack.h src/core/genome.h $d/ $CC -pthread -DZY_THREADS -O2 -w -fwrapv $d/micro.c $d/port_linux.c -o $T/zymr || { chk 0 1 "run $1 links"; return; } @@ -369,6 +374,7 @@ s_runonly() { runonly wide tests/programs/wide.zc runonly selfpatch examples/selfpatch.zc runonly gc tests/programs/gc.zc + runonly zc0unbounded tests/programs/zc0unbounded.zc # zc0 accepts unbounded in all three places and ignores it runonly voidmain tests/programs/void_main.zc runonly trace tests/programs/trace_run.zc # the image carries line tables: a fault and rt.trace() print the same backtrace as the resident compiler's runonly float tests/programs/float.zc |