Jakob Degen

lifetimes: Brand the compiler IR and the bytecode Summary: The compiler's products - `ExprCompiled`, `StmtsCompiled`, `DefInfo`, the spans, and the `Bc` they compile to - held `FrozenValue`s, so everything the evaluator read out of bytecode was erased and re-typed at the read: `Def::at_brand`'s vtable compare per `CallFrozenDef`, the `FrozenValue::to_value` reads in the interpreter, and the erasures at the ends of `demote`. This diff puts the brand on the IR and the bytecode. The IR lives at `'fm`, the module frozen heap the `Compiler` allocates into (`ExprCompiled<'fm>`, `ResolvedIdent::Global(Value<'fm>)`, which ripples through `CstPayload<'fm>` into the scope resolver and the typechecker), and a `Bc<'v>` is at the brand of the heap it runs against. The two meet in one place: `eval_regular_top_level_stmt` rebrands the statement's `Bc<'fm>` to `Bc<'v>` through the module edge, once per top-level statement, and the module's `DefInfo` handle is rebranded once in `eval_module`. Everything downstream is plain reads. Where a compiler product has to be a heap value - `DefInfo`, `FrameSpan`, `InlinedFrame`, `FrozenFileSpan` - it is allocated as a `StarlarkAnyComplex<T<'f>>`, the `FrozenModuleData` idiom, with a hand `FreezeBranded` that is unreachable because these are only ever allocated in frozen heaps. `Def`'s fields move to its brand, `Def::at_brand` goes, and `post_freeze` gets its edge from `ModuleHeaps::seal_with`, which is the relocated mint: the closure gets the same edge `frozen_heap` hands out, for the same reason. `FrozenFileSpan` keeps its name only because `codemap::FileSpan` already has the good one. The bytecode needed one structural move. Opcodes dispatch by `TypeId`, so instruction types must stay `'static` while their operands now carry `'v`. Call instructions therefore take `'static` marker types (`FullArgs`, `PosArgs`, `AnyCallable`, `NativeCallable`) whose GAT names the branded operand; the instruction body is unchanged and dispatch does no more work than before. `BcNativeFunction<'v>` is at the bytecode's brand rather than immortal, since a native function value can live in any frozen heap the module references, not only in a static. Smaller things this forces or frees: - `LocalAsValue` placeholders were a process-wide singleton heap indexed by slot; they are now a per-`Compiler` cache in the module frozen heap, so `alloc_simple_typed_static` goes. - `BuiltinFn::frozen()` becomes `at()` over `HeapEdge::immortal()`: `Constants` is a static. - `TypecheckProfile` is keyed by `String`: the profile outlives the evaluation, and the def names it was keyed by are now at the brand. - `UnusedLoad` carries spans instead of CST nodes, since the CST is branded and the result outlives the heap scope. - `Module::get_slot_frozen`, `frozen_value`, `Arguments::frozen_to_v` (a transmute) and `FrozenAnyArray` are dead and go. `FrozenAnyValue`/`alloc_any_value` stay for buck2's `UserProviderCallable`, and `TypeCompiled::to_frozen` is branded with a `to_frozen_unbranded` next to it for the same consumers; both are 4-C's to delete. - `is_builtin`, `speculative_exec_safe` and `eq_is_ptr_eq` move from `FrozenValue` onto `Value`, where the compiler now calls them. No new `unsafe` beyond the `seal_with` mint; the tuple `ProvidesStaticType` impl is of the same kind as its neighbours. The pagable wire format is unchanged. Reviewed By: jtbraun Differential Revision: D118970674 fbshipit-source-id: 62668fb6d7cdd982e66918d4cc93fd02d2700f1c

hypermodern: Add dice_core Summary: The core state of `docs/incrementality.md` as its own crate: keys, revisions and untracked-input revisions as opaque identities, branches and versions, one claim per key and branch pinning its witnessing certificate, assertion histories for injected keys, exact per-branch rdep maps, and the four operations `commit`, `fork`, `lookup` and `write`, plus `take` for today's `unstable_take`. Nothing in dice uses it yet; the next diff replaces `core/graph` with it. It is a separate crate because we will want the algorithm usable outside dice eventually, and drawing the line now is what keeps it pure: everything environment-specific comes in through one `Env` trait with three associated types, the dependency payload of a certificate (dice's series-parallel deps), data per claim (dice's invalidation paths) and data per assertion (dice's invalidation priority). The core stores these and hands them back. The one thing it does with them itself is compare payloads, since whether two certificates are the same one is a question about their traces, not about which allocation holds them; environments hand back the allocation they were given, so the comparison is by address almost always. A key that is both asserted and certified is a hard panic on both paths, in release too; dice's public API only allows that through test mocks. The one-word `triomphe` `Arc` dice uses moves in here, because certificates are shared between the core's claims and the environment's candidates; dice re-exports it and so depends on the crate already. Lookups that cannot answer offer a candidate for the environment to re-establish only if it was stamped with the version's untracked-input revision; one that was not can never cover the version. `nearest_certificate` is there for environments that want that certificate's value regardless, as dice does for its equality cutoff. ## Where the code departs from the doc - Seqs are 1-based (`NonZeroU32`), so that `Option<Version>` is free and the root's first commit is seq 2, matching the version numbers dice's tests already use. - Fork builds the child's rdep map from the certificates of the attached set instead of copying the parent's and supplementing it. With exact maps that is the same set of edges, and it lets the checker assert Invariant 3 as an equality rather than a superset. - The install policy for a branch that already has a claim is "replace iff the new window reaches further" (§5.2 leaves it as a policy). One visible consequence, pinned by a test: a branch's own attach replaces a closed copy it inherited for earlier seqs, so those seqs fall back from `Valid` to `Unknown` with a candidate. - §5.2 step 2.4, the same certificate still covering the child's fork seq, turns out to be unreachable through `write` under one-window-per-slot semantics (a re-issue after a close always restarts the window at or after the close). The arm is kept; the test that expected it documents what happens instead, a re-home. ## Testing Three layers, all in the crate. Unit tests, one module per part of the doc: resolution rules 1 to 3, commit and its BFS, write and coverage including non-contiguous covers of returning injected premises, each cascade rule of §5.2 step 2, fork including the round-6 counterexample and the support worklist, the untracked-input semantics ported from `check_that_force_dirty_*`, retention, and the constructions that shaped the design (the certificate island and cyclic writes of Appendix C, the fork worklist's revision check, a grandchild below a shadow, dirties on both sides of a fork, a re-homed claim's ε history, the G4 chain, fill-in from a closed parent window, the displaced-claim precision loss, certificates written after `take`). Every mutating call in a test re-checks the invariants. `check_invariants` is a full scan of everything the state promises about itself: the branch tree, history ordering, Invariants 1 to 3, `closed_index` exactness, and no key both asserted and certified. The master invariant is not a property of the state alone, so it is left to the oracle. The fuzzer runs random operation sequences against an oracle that computes §3.2's judgment by brute force over the recorded history. Two generators: arbitrary certificates, random keys, revisions, premises and ε, for which soundness must still hold because the theorem is unconditional; and an honest environment with fixed dep graphs and a deterministic value function, driven the way dice's worker drives the core, which additionally checks from-scratch consistency, that a write at a head attaches, and that a commit closes nothing outside the changed keys' support. Failing cases shrink by deleting operations and print with their seed. To check the harness has teeth I planted bugs one at a time. A first round of five (BFS skipping inherited claims, no cascade, closed covers installed open, stale edges kept, no support filter at fork) was caught within 200 cases, every time by the invariant checker. A second round of five aimed past the checker (off-by-ones in `History::at` and `Window::covers`, a child resolving at its parent's head instead of the fork point, inherited injected cover denied, no-op asserts decided against the parent's view) was caught by the unit tests and both fuzz modes; the last one only by the oracle, so it is a unit test now too. Reviewed By: christolliday Differential Revision: D118978185 fbshipit-source-id: f81aef9a831e5cd6edbb0e4dd9afbb4f625334de

mem: Add mini_vec crate and type Summary: `MiniVec` is a `Vec` but is a single pointer on the stack; the length and capacity are bitpacked into the *top* bits of the pointer if they're small, otherwise allocated in the heap. This does introduce high-bit pointer packing to buck2 which we have not had so far. Claude assures me that modern kernels do not hand out high addresses without a user explicitly asking for them and no one complained when I asked, so I guess the team is on board with this. I'll use this in a couple places, but the first thing we'll be able to do is replace all the `ThinBoxSlice` Reviewed By: jtbraun Differential Revision: D105465807 fbshipit-source-id: 65663fb277c1301be55a3b1e94ef831ae80d4f78

unsafe: Split `heap_type.rs` into a module per heap Summary: The file held the unfrozen heap and its garbage collector, the frozen heap builder, the sealed heap with its paging wire format and diagnostics, the heap names, and the `OwnedFrozen` family: 2500 lines, five unrelated safety arguments. The `OwnedFrozen` invariant (the value is kept alive by the heap in `heap_ref`) is protected by field privacy, and that privacy extended over all of it. Now each heap is a module and the privacy boundaries coincide with the safety boundaries: - `unfrozen.rs`: `Heap`, `Tracer`, GC - `frozen.rs`: `OwnedFrozenHeap`, `FrozenHeap`, the shared reference set - `sealed.rs`: `FrozenFrozenHeap`, `FrozenHeapArc`, paging, diagnostics - `name.rs`: heap names - `owned_frozen.rs`: `OwnedFrozen`, `OwnedFrozenRef`, `OwnedFrozenReconstructor`, and only the impls that touch the pairing; the conveniences that were in `owned_frozen.rs` move to `owned_frozen_ext.rs` so that they stay unable to reach the fields `HeapKind` goes to `arena.rs`, next to the walk that takes it. Two accessors on `FrozenHeapArc` (`new_sealed`, `is_empty`) replace the field accesses that crossed the new boundaries. Code moves otherwise. Reviewed By: jtbraun Differential Revision: D121315380 fbshipit-source-id: 17d01833ffe78d2721c0fbdda38232cd5591f23e

lifetimes: Brand the frozen heap Summary: `FrozenHeap` becomes a `Copy` handle `FrozenHeap<'fh>` onto an `OwnedFrozenHeap`, the way `Heap<'v>` is a handle onto its owned heap: `OwnedFrozenHeap::with` opens a scope with a fresh brand, `seal` turns the builder into the `OwnedFrozen<()>` owner, `FrozenHeap::temp` is the scratch form, and `OwnedFrozen::build` converges on the `temp` shape (closure returns at the heap's own brand; the `'fv`/`'h` split and its "foreign `FrozenValue`" clause are gone). Every allocator on the handle returns at the brand, and `AllocFrozenValue<'fv>` takes the handle and returns `Value<'fv>`. One diff because there is no compiling seam: once `&FrozenHeap` stops being a type, everything that held one has to move at once, and app/ has to come along for the same reason. The two `AllocFrozenValue` impls outside buck2 - metalos's `starlark_util.rs` and skycastle's `text_match.rs` - are in this diff for the same reason: the signature change forces them. They change signature only; `alloc_simple` does the same allocation it did before. ## The module's frozen heap `Module::frozen_heap` (and `Evaluator::frozen_heap`, same name so a legacy caller fails at the call site rather than compiling to something else) is now closure-scoped: `|fh: FrozenHeap<'fm>, edge: HeapEdge<'v, 'fm>|`. The module's frozen heap cannot share `'v` - values of the value heap could then be allocated into a heap that outlives it - so it gets its own brand, and the edge is how its allocations reach `'v`. That relocates the one `HeapEdge::unchecked_new` from `Evaluator::frozen_heap_edge` (deleted); the keep-alive that comment hand-waved is now structural: `freeze_impl` gives the value heap a reference to the sealed heap. The SAFETY comment names the remaining gap honestly (a module dropped without freezing), which predates this diff. `eval_module` compiles and executes in one such scope; the `Compiler` carries the handle, and `OptCtxEval` is implemented for `Compiler` (instead of `Evaluator`) and `OptimizeOnFreezeContext`, both of which know their frozen heap's brand. ## What stays `FrozenValue` The compiler IR and bytecode, and the frozen list/tuple storage. They reach the branded heap through crate-private, greppable erasures on the handle - `alloc_frozen` and `alloc_str_intern` - or an explicit `unpack_frozen()` where a branded value has to be stored erased. That census is the worklist for retiring `FrozenValue`. `alloc_simple_typed_static` survives crate-privately for the `'static` typed handles (`FrozenAnyValue`, the native method tables), now with a checked downcast instead of the `&'static FrozenHeap` casts, which are gone. Two smaller API notes: the frozen `alloc_simple` bound is now `AValueSimpleBound<'fh>` like `alloc_simple_typed`, since a `Send + Sync + 'static` bound cannot be met by branded values that live in the heap (the `HeapSendable`/`HeapSyncable` supertraits carry the same guarantee for `'static` types); and `Value<'fv>: AllocFrozenValue<'fv>`, the twin of `Value<'v>: AllocValue<'v>`. `OwnedFrozen::build` erases the brand before sealing rather than through `unchecked_new` afterwards, because the closure's result is branded with the borrow of the heap that `seal` consumes; the transmute moved into a shared `erase_brand`, no new unsafe operation. The pagable tests keep feeding `FrozenValue`s to the ser/de plumbing through a small `ErasingHeap` test wrapper rather than restructuring eighty tests around closures; they get rewritten when `FrozenValue` goes. Reviewed By: jtbraun Differential Revision: D118970647 fbshipit-source-id: c6993b65ed87685d7bdad224504617fdb7ed1081

hypermodern: Replace the core state with dice_core Summary: The interim core under `core/graph` (version ranges, `ForceDirtyHistory`, `LazyDepsSet`, the maybe-overwrite dance in `on_computed`) goes away. `core/graph.rs` is now the value layer of `docs/incrementality.md` Appendix A on top of `dice_core`: per-key revision tables holding `MaybeResident` values with the page-out lifecycle they had, interning by certificate identity, then `Key::equality`, then a fresh mint, injected values interned against everything retained, and retention by "some claim names this revision" after every write. The actor in `core/internals.rs` composes it with the unchanged `VersionTracker`. Values stay in their own map beside the core's slots; co-locating them was considered and dropped. `VersionNumber` and `DiceKey` become aliases of the crate's `Version` and `Key`; `Revision` and `EpsilonToken` are re-exported. `Version` displays as `v{seq}` on the root branch, so the `dice_version` event field and the version literals in tests are unchanged, and the root's first commit is still version 2. `SeriesParallelDeps` becomes generic over its edges' revision type. A compute records `Option<Revision>`, `None` for a transient dep, which makes the value itself transient and so never written; `certify()` turns a valid value's deps into a certificate's premises at the write boundary, and the core never sees an optional revision. Two dep lists are equal when they are the same trace, which is what interning step 1 compares. ## What is deliberately kept from today - The `VersionEpoch` check on the write path: a write from a transaction whose `SharedCache` was dropped, or that predates an `unstable_take`, answers cancelled and installs nothing. Commits never touch epochs, so a write racing a commit installs over whatever it still covers. - `unstable_take` drains claims, edges and computed values and keeps injected histories and per-key revision counters; it does not start a new branch. Cutting the watchers over to branch APIs is a later step. - Writes still carry the transaction's version, for that check and for a debug assertion that the ε they stamped is the version's; the algorithm does not read it. - The worker is untouched except for the shape of `Candidate`, which now holds the certificate itself, re-issued as that same `Arc` on revalidation, and says whether it is revalidatable: the core offers a candidate only under the version's ε, and dice fetches the nearest certificate separately so that a recompute can still be compared against its value. ## What changes for callers - `changed_to` on a computed key is an assertion like any other: the key is injected from then on, and certifying or dirtying it afterwards panics, in release too. buck2 only does this through test mocks that never compute the mocked key; the four app test crates that use them pass. `dice_tests::linear_recompute` overrode a computed key after computing it and now injects a leaf instead. - Two `check_dependencies` tests injected computed keys to seed stored values and then dirtied them; they now record edge revisions that the fresh computes cannot match, which is the property they were after. - Invalidation paths: a path node from another branch reads as `Unknown`, which no current consumer can observe. - One claim per key and branch. A revalidation racing a newer compute of the same key installs nothing, and an old-version reader gets a candidate instead of a `Match`; `core/graph/tests.rs` pins that. The deep `fuzzy_dice` run found the other face of it: a query below the head whose write covers the head again (an injected input changed and changed back) attaches there and displaces the closed claim that served the versions in between, so a later query at one of those recomputes. Values are unaffected; the old core kept both ranges. `permit_recompute` names that shape (`DisplacedEval`), and stays as tight as before whenever queries run at the head. ## Testing The interning and paging behaviours the notes asked to keep are pinned in `core/graph/tests.rs` (certificate-identity reuse without equality and over a paged-out value, equal recompute re-finding its revision, injected values re-finding theirs, revalidation keeping its revision when superseded and keeping a paged-out value paged out, stale candidates after a dirty, the page-out index across page-out, page-in, non-pageable marking and take, revision counters surviving take), each call re-checking values against index and core. The rest of the coverage is the crate's. Reviewed By: christolliday Differential Revision: D118978186 fbshipit-source-id: 7a9f05be94ce73582102b9a706ac8d098d1319cf

mem: Change how `DiceTransaction` -> `DiceComputation` works Summary: We want to have `&'c mut DiceComputations<'d>` return `&'d Value`s. Right now, it can't do that because `DiceTransaction` derefs to `DiceComputations<'static>` and obviously we can't get back `'static` things. We instead need a conversion like `&'d DiceTransaction -> DiceComputations<'d>` and this diff does that. We remove the deref impl (since the signature is no longer right), add `.ctx() -> DiceComputations<'d>` instead, and then go and fix all the compiler errors. As a part of that, we can actually change the representation of `BaseComputeCtx` to just directly hold a `CoreCtx`, which makes a bit more sense. I'll do some renames towards the end of this stack to help justify why things are the way they are (note also that the use of `ModernComputeCtx::Parallel` is fine here and actually has nothing to do with `Parallel` specifically) Reviewed By: NavidQar Differential Revision: D110626399 fbshipit-source-id: 4ba0db607a88e3456ccb7b091b6c2bf5402566c7

lifetimes: The freezer carries its source brand Summary: `Freezer::freeze` was generic over the brand of its argument, so a `FreezeBranded` impl could hand it a value from any owner it could borrow one from, and the already-frozen fast path returned that pointer at the target brand on the strength of a contract on `Freezer::new` rather than an edge. That was the one brand change left in the `branding` module's "trusted rather than proven" list. The freezer now has the source brand in its type, `Freezer<'v, 'fv>`, and holds the `SealEdge<'fv, 'v>` that `ModuleHeaps::seal_with` already minted beside it; `freeze` takes a `Value<'v>` and its fast path is `SealEdge::rebrand`. That puts the brand on the trait too, `FreezeBranded<'v>` in the shape of `Trace<'v>`: a type branded by `'v` implements `FreezeBranded<'v>`, a type that holds no values implements it at every brand. `Value::rebrand_frozen_unchecked` is left with `SealEdge::rebrand` as its one caller, and the "trusted" section says nothing remains beyond the allocation contract the module opens with. The derive infers the brand: the type's single lifetime parameter, or a fresh `'v` for a type without one. Every derive site, in-tree and out, has zero or one lifetime, so there is no attribute to pick one; a type with two gets a compile error asking for a hand impl. The vtable's `heap_freeze` erases the source brand the way `heap_copy` erases the `Tracer`'s: the entry is higher-ranked over both brands and `AValueVTable::new` transmutes the freezer to `T`'s `'v`, next to the tracer transmute and under one SAFETY comment. The tests that need a freezer build it from a `ModuleHeaps` (`Freezer::testing_temp`), so nothing mints an edge by hand any more. The trait change has no compiling seam, so the fallout is folded in: - buck2: the hand impls, `try_freeze_directly` and `DynamicLambdaParamsStorage::freeze` gain the brand; two local helpers that took `Value<'_>` name it. - promptlark (`fbcode/ai_productivity/promptlark`): the four hand impls (`Action` and the treesitter node, parser, query cursor and tree cursor) gain the brand, one line each; the three derives re-expand. - skycastle (`fbcode/sandcastle/skycastle-rust/workflow-parser`): seven derives re-expand, no source change. Nothing changes at runtime: the brand is a type parameter, and the fast path was already the frozen-bit check and pointer copy that `SealEdge::rebrand` is. landed-with-radar-review Reviewed By: jtbraun Differential Revision: D119449630 fbshipit-source-id: 6f2108518a2687d4cde13eda1a4bf5fcf8496a18

hypermodern: Check dependencies by revision equality Summary: Each dep edge in `SeriesParallelDeps` now records the revision its compute observed, and revalidation compares the dep's current revision against it, replacing the containment check against the previously verified version. Revisions are per-key identities minted by interning at write time in the core state: storing a value `Key::equality`-equal to the current one re-finds its revision, anything else mints fresh (`docs/incrementality.md` §2.1 and Appendix A). They ride on `DiceComputedValue`, `None` for transients, which never enter the graph and have no identity to name; an edge to a transient never revalidates. Everything the old check accepted is accepted here, since a dep unchanged since the previously verified version re-found its revision, and the new acceptances, a dep whose value returned to a retained identity, rest on the same determinism assumption the equality cutoff already does. A reuse-write (equal value, same dep set) has to refresh the stored edges to the revisions it observed, or the dependent's edges stay pinned at dep revisions that have since moved and every later check recomputes it; the oracle found that one. Projections record their base's revision as their one edge, which `OpaqueValue` carries for them. `SeriesParallelDeps` equality stays structure and keys, because its callers ask whether the dep set changed shape, and folding revisions in would defeat equality-based reuse exactly where cutoff matters. Reviewed By: christolliday Differential Revision: D118978178 fbshipit-source-id: 6eb0da931f1576c8aaa27abd37fc467a0a41f2a4

lifetimes: Brand the deserialize context Summary: `StarlarkDeserializeContext<'de, 'fv>` hands out `Value<'fv>`, and `StarlarkDeserialize<'fv>` is implemented at the brand, in the `Trace<'v>` shape: `impl<'v> StarlarkDeserialize<'v> for Foo<'v>`, and `impl<'fv> StarlarkDeserialize<'fv> for Bar` for a type that holds no values. The framework introduces the brand: `StarlarkDeserializerImpl::recover_from_pagable` is closure-shaped and mints one brand per value it materializes (and one per root for `OwnedFrozen` and `Globals`); the argument for why the brand is honest — a value serialized from a heap points only into that heap or into heaps it references — is written on it. The `AValue` vtable slot is `for<'de, 'fv>`, as `heap_freeze` already is; `AValueSimpleBound<'v>` reaches the impl through the new `StarlarkDeserializeAt<'v, 'fv>` (`Reinfect<'fv>: StarlarkDeserialize<'fv>`), which is how the registered `'static` instantiation deserializes at whichever brand it is asked for. This closes D5: the `Value` bridge is `ctx.deserialize_value()` with no `restore_brand`, and the framework-only contract that used to sit on `deserialize_value` is gone. What remains is the framework's own residue: `ensure_initialized` hands out pointers it wrote itself, the `AValue` impls write the `'fv` value into the heap's `'v`-typed memory (the erasure `OwnedFrozen` does), and the two root readers pair the value with its owner through `unchecked_new`. The derives pick the brand from the type's lifetime parameters: one is the brand, none means every brand, several need `#[starlark_pagable(brand = 'x)]` (no user in tree; the census found no type with two). Their auto-bounds are per trait now, and `bound = ""` opts out where a parameter's own trait already implies both (`ArgSymbol`). Two things the erased contract let through and the brand rejects, fixed rather than worked around. `TyRecordData`, which is `Arc`-shared between heaps, held a `ParametersSpec<Value<'static>>` that had no defaults; it holds the `ParametersSpecPrototype` now and instantiates the spec at the call's brand (one `Arc` clone per record-constructor call). And an `Arc<T>` payload is shared by every holder across heaps, so `T` has to deserialize at every brand and cannot hold a value; the pagable tests that put a `Value` inside `Arc<ArcBlanketInner>` lose that field, and with it the deferred-Arc scope-repair check, whose scenario no longer exists (the serialize-side scope plumbing it exercised looks dead now; follow-up). The other test value types that stored erased values are branded and built at the heap's brand. App: the eleven `deserialize_with` helpers and the `SmallMapKeyDeserialize` impls gain the brand, and bxl's hand-written `ProvidesStaticType` for `StarlarkTargetSet` gets the `IsStaticType` half the derive would have produced. Wire format unchanged: the same `SerializedFrozenValue` encoding is written and read. landed-with-radar-review Reviewed By: jtbraun Differential Revision: D118970710 fbshipit-source-id: 34d09c0692009eba51bd334fd06c0216bd60df18