Skip to content

Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler #273

Open

Description

@humuhumu33

Child of #92 (stage 8 of #27): its "Self-hosting acceptance". Part of v0.4's objective: LexLean compiles itself.

Scope

Once every compiler part is certified LexLean source (the sibling issues, BS-01..BS-08, and #91's runtime):

  1. Stage 1: stage 0 (today's Rust compiler) compiles the .lex.tex compiler to a certified Rust package whose provenance binds the source, certificates A, B, E and the runtime.
  2. Stage 2: stage 1 compiles the same source.
  3. Fixed point: stage 2's package is byte-identical to stage 1's, and stage 1 equals stage 0 on every committed project, corpus, fixture, golden and the Atlas verification records.
  4. Only then are the Rust compiler modules removed from the normative tree (kept as the oracle under tests/ per [v0.4] #27 stage 8: the production compiler authored in .lex.tex and compiled by LexLean to production software #92), and just vv passes from a clean checkout.

Done when

Each part follows the standing R3 discipline of #15: register rows in model/ids.toml and SPEC §31, one scenario and one conformance_<id> test per row, positive and negative fixtures, a planted defect recorded in VERIFICATION.md, and the Rust module kept as the stage-0 oracle (differential to the byte) until the fixed point of #92 removes it.


Generated by Claude Code

Activity

  1. added this to the LexLean v0.4 milestone on Oct 22, 2026
  2. added
    enhancementNew feature or request
    self-hostingLexLean compiling itself: compiler in .lex.tex, certified, built by its own pipeline
    on Oct 22, 2026
  3. changed the title [-][v0.4] Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler[/-] [+]Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler[/+] on Oct 22, 2026
  4. removed this from the LexLean v0.4 milestone on Oct 22, 2026
  5. humuhumu33 commented on Nov 12, 2026

    @humuhumu33
    ContributorAuthor

    Proposal for #273: modular certification and the shape of stage 1

    A proposal for the owner and maintainer to decide, posted here as the 2026-10-22 ruling asks. No milestone, label or title is changed, and nothing is built or pushed. It came out of a read-only survey of what stands between release/v0.4 and stage 1. That survey found that porting is not the binding constraint: certifying a compiler-sized command root is.

    Base: release/v0.4 at aaf845507. Counted means measured on that tree. Estimated means extrapolated, and each estimate names its source.

    Decision asked

    Lower one program per project and target instead of one per root. Each function's certificate rows are then generated once, in shard modules cut along the call graph. Each root keeps a small certificate A, B and E of its own that cites the shards.

    The calculus, RustSemantics, and the library's sound, simulate and compose do not change. Every theorem a root has today keeps its statement except one thing: the entry is e_r instead of 0. This is the smallest change that lets a compiler-sized command root be certified. It also cuts the bootstrap's certificates about in half today.

    Three smaller decisions make stage 1 buildable:

    • The compiler's embedded language/ tree reaches the step through a new embedded host request, and the certified step checks its digest.
    • rust_renderer stays the recorded digest of the Rust renderer files until the removal.
    • Certificates of the self-compile are verified in CI and not committed as bytes.

    1. The problem, measured

    A root's certificates restate its whole closure. Certificate A's statement is RunConv P 0 … over the program P lowered for that root alone (§17.17, Statement). Its rows are __prog, the encoders, and __fits_k and __rel_k for each function of the closure. Certificate B has one fun<n> derivation per function of the same program. So a function that two roots call is lowered, related and derived twice.

    Counted on the 62 committed bootstrap roots (the program records bootstrap/expected/verify/preserve/program/R*.json and preservation.json; the script at the end, which identifies functions structurally up to renumbering):

    Measure Value
    Functions, summed over the roots' programs 4,698
    Distinct functions 2,221
    Program bytes, summed / distinct 9,219,677 / 4,722,869 (ratio 1.95)
    Certificates A + B + E 65,748,119 + 85,109,771 + 6,044,232 = 156,902,122 bytes
    Largest single certificate 5,320,581 bytes (lowerBodies, A), against max_file_bytes 6,291,456
    Certificate bytes per program byte about 17

    Projection to stage 1. This is estimated: it scales the bootstrap's distinct program, about 4.7 MB for about 14,900 Rust lines ported, to the compiler's about 150,000 lines.

    Today's scheme One project program, sharded
    Program about 47 MB about 47 MB
    Certificates in total about 800 MB, all in one root's A and B about 800 MB, spread over shards
    Largest file about 340 MB (A) and 440 MB (B); refused by the 6 MB cap the largest call-graph cycle's rows; today about 5.3 MB
    Bootstrap export (62 roots) 157 MB about 80 MB (the 1.95 ratio)

    2. Options

    Option What changes Verdict
    Status quo with raised limits max_file_bytes to about 512 MB Rejected. One Lean process would check a 340 MB module. Today a 9.2 GB Lean child on Atlas is already more than the 16 GB WSL host can hold.
    S: one program per project and target, sharded certificates lowering numbering; how certificates are cut into modules; package layout Recommended. It keeps every proof of the hand-written library.
    L: linked programs, true separate compilation the calculus gains cross-program calls; run, RustSemantics, sound and simulate gain an environment and a frame lemma Later, if S's Lean time is too high. It changes the trusted library's proofs, so it is a larger review.

    3. Design S

    3.1 Lowering (§17.14, production/lower.rs)

    • The program. One program per project and target: the union of the eligibility closures of every production root that declares that target. Instances are deduplicated by definition and type arguments, as within a root today.
    • Numbering. Roots go in report order, and functions in discovery order from each root in turn. An instance already numbered keeps its number. The layout gains an entry table, root to function.
    • Invariants. "The program is exactly the closure" becomes two checks: the program is exactly the union of the closures, and each root's closure is exactly the set reachable from its entry. Both remain LLI9001.
    • Limits. max_ir_nodes is charged per program, as now.

    3.2 Certificates (§17.17, production/certificate*)

    Module Rows Size depends on
    …P.Fn<s> (one per shard) one function constant __fn_k per function of the shard the shard
    …P __prog, the program as a lookup over the __fn_k constants (see risk R1) the number of functions
    …A.<s> (one per shard) __fits_k, __rel_k, the encoders first used there the shard
    …B.<target>.<s> fun<n> for each function of the shard the shard
    …B.<target> krate, flags, crate_ok, root (simulate) the number of functions
    …R<i> (one per root) denote, root : RunConv __prog e_i … the root's boundary
    …R<i>.Compose.<target> compose applied to R<i>.root and B.<target>.root at fnIdent e_i the root's boundary
    • Shards. A shard is a set of strongly connected components of the call graph, cut in topological order and filled up to a byte budget. A component is never split, because a mutual group's relation is one recursor. Each shard imports the shards of its callees.
    • Content. The rows are those of today's modules, unchanged. Today's rows are already independent of the root: __rel_k relates function k of P to its source definition, and fun<n> derives function n of the crate. Only P, the numbering and the module boundaries move.
    • The library. No proof of the library changes. The one statement that moves is certificate A's root, from function 0 to function e_i. E's boundary form already takes fnIdent e. To confirm in M1: whether compose assumes entry 0 anywhere.
    • Limits. The size limit (§17.17, Limits) applies per shard and per root module, so max_file_bytes bounds every file Lean opens. The early lower bounds are computed per component.
    • Records. preservation.json lists the shards, each with its module, byte length and SHA-256, and per root its entry, its A and E modules, and the target's B root module. This is a schema change (schemas/preservation.schema.json), so the language-1.2 compiler-semantics ID moves. Languages 1.0 and 1.1 are untouched, since production is 1.2 only.

    3.3 Packages (§17.16, §24.7, calculus/rust/package.rs)

    • The request. lexlean/production-request/1 is unchanged: one package per requested root.
    • A root's package. src/lib.rs is the project crate for the target (the one certificate B is about) plus that root's export wrapper. Cargo.toml and provenance.json are as now; the provenance also binds the crate digest that B states.
    • Trade-off. A consumer that ships one small root out of a large project now ships the whole project crate. A project that wants small packages splits into projects. For the downstream projects that use production today, this is no change in practice. Their projects are small; that is a reading of the corpora, not a measurement.
    • rustc. One crate per project instead of one per root. The conformance harnesses build it once per run and link the wrappers. Risk R2 covers the size of the compiler's crate.

    3.4 Verification (§22, verify/)

    The shards form a directed acyclic graph of imports. Verification stages and compiles them in that order through the existing pool (verify/pool.rs, whose output is width-independent by contract). This is also the parallel certificate stage the gate-speed hand-over asked for. Today 1,397 of the export's 1,966 s are certificates checked one at a time.

    3.5 What does not change

    • The trusted base and the kernel.
    • The statements a consumer relies on, apart from the entry index.
    • The 49 Corr rules.
    • The token audit and the axiom pins.

    4. The shape of stage 1

    Question Proposal Why
    Where is the command root? LexLeanBoot.Compiler.step in bootstrap/, with a committed production request for it alone Under S, the bootstrap project's program already is the compiler. A separate selfhost/ project would import bootstrap as a source package and certify every function a second time.
    How does stage 1 get its 36,119,142 bytes of language/ (counted; 32,670,965 of it the preservation library)? A 15th request, embedded (path : String), answered by Event.read. RB-24's printed driver serves it from an include_bytes! table, and the package gains an assets/ tree. The certified step computes the §11.5 tree digest of what it reads and refuses anything but its compiled-in compiler-semantics ID. It needs no effect. A literal costs about 27 bytes of certificate A per digit (§17.17 cost table), which is impossible here. Reading files beside the executable would change the release from one binary to a binary plus a data tree. With the digest check, the driver's table is trusted only to be there, not to be right.
    What is rust_renderer in provenance? Unchanged until the removal: the recorded digest of the nine Rust RENDERER_FILES. Stage 1 reads it from language/ as data, and it moves once, at FP-06. Stage 1 must write what stage 0 writes. If it framed bootstrap/src now, every slice landing would move the compiler-semantics ID. This is the maintainer's 2026-10-22 decision 4 ("at the fixed point").
    Are certificates committed? The self-compile's certificates are not committed. CI regenerates and verifies them, and preservation.json with its digests is committed. The bootstrap export as it is today stays committed until the maintainer decides otherwise. About 800 MB per regeneration (estimated) is not a git workload. bootstrap/expected is already 258,401,428 bytes for 62 packages (counted).
    Stack The RB-24 driver runs the step on a thread sized from PD-08's rows the PD-08 bounds and the Windows default stack (#164)

    5. Risks, and the measurement that decides them (M1)

    # Risk What M1 measures Fallback if it fails
    R1 The kernel evaluates program and crate lookups in every side condition. A list of about 22,000 functions (estimated: 2,221 distinct functions per 14,900 lines, scaled) makes each lookup about 22,000 reduction steps. B's check time on the bootstrap with __prog as a list and as a balanced tree Represent __prog and krate as a tree. A library lemma, proved once, equates the tree lookup with today's list lookup.
    R2 rustc on a crate of the whole compiler: about 36 MB of Rust (estimated from the bootstrap's crates, 7,036,588 bytes summed and ratio 1.95, scaled) the debug and release build time and peak memory of the bootstrap's project crate, and of a synthetic crate ten times its size Split the crate into files by shard (an RB-07 layout change)
    R3 A single call-graph cycle exceeds max_file_bytes the largest component's rows on the bootstrap Split the source definition. The rows of a cycle cannot be split.
    R4 Lean time for about 800 MB of shards the bootstrap export at width 1 and width 4, before and after S Option L

    M1 decision gate. M1 is a spike on a branch, never landed, run on CI rather than the laptop. It prototypes 3.1 and 3.2 on the bootstrap and reports:

    • the total certificate bytes (prediction: about 80 MB, against 157 MB);
    • the largest shard;
    • the export time at widths 1 and 4;
    • the time per side condition for R1;
    • the crate build for R2.

    S proceeds if the total is below today's, every shard is under the cap, and the export is no slower at width 4.

    6. Plan

    Every step follows R3: register rows and SPEC first, a failing case, plants, a VERIFICATION entry. All changes are in stage 0 (Rust and SPEC); the .lex.tex twins of the changed generator are track C's.

    PR Content Rows touched (to be confirmed against model/ids.toml)
    M1 The spike and its measurements, posted on #92 and #273 for the decision none
    M2 SPEC §17.14, §17.16, §17.17, §22, §24.7 text; schema; failing cases SP-02, SP-05, SP-14, SP-15, SP-16, RB-07, PD-08
    M3 Project program and entry table (production/lower.rs, layout) SP rows of lowering
    M4 Certificate A shards and root modules (certificate/data_a, certificate.rs) SP-15
    M5 Certificate B shards, crate_ok, root per target (certificate/data_b) SP-16
    M6 Certificate E per root; package equals project crate plus wrapper (package.rs, provenance) SP-14, RB-07
    M7 Shard staging through the pool (verify/mod.rs) VR rows of staging
    M8 The regeneration: every language-1.2 export, golden and record, with Atlas, through regenerate.yml. One identity move, landed with M3-M7 as one batch, as #480 landed BS-25..34. counts
    M9 The embedded request: PD-10 row, RB-24 driver arm, assets/ in the package layout PD-10, RB-24
    M10 The step root's first slice (track X) on top of M9 new BS row

    Size (estimated, from no measurement of this work). M2-M7 are 6 Rust PRs of about 500 to 2,000 changed lines each, plus one regeneration. With reviews, that is 2 to 4 weeks elapsed. M1 is 2 to 3 days.

    Effect on the writing tracks.

    • The BS cases' export comparison changes from per-root packages to a shared crate with wrappers. Every case's comparison step needs one mechanical edit at M6, done by M6 itself.
    • A slice written before M8 lands regenerates once more, as it would for any identity move.
    • Track C should port the kernel DAG and certificate B's derivations first. S leaves those per-function pieces intact, and moves only module boundaries and __prog.

    7. Questions for the maintainer

    1. S rather than L, subject to M1's gate?
    2. Program per project and target (recommended), or per production request? Per request gives smaller packages to consumers, but verify and production build would then certify different programs.
    3. The embedded request (one binary), or a data tree beside the binary?
    4. Keep rust_renderer as the recorded constant until FP-06?
    5. The self-compile's certificates verified in CI and not committed?
    6. Which lane: the maintainer's, or ours?

    Sources

    The measurement script (Python 3, standard library; run as python dedupe.py <dir>, with the 62 R*.json and preservation.json in that directory)
    """How much of the bootstrap's lowered programs is the same function restated by several roots.
    
    Functions and ADTs are numbered per program, so identity is structural: a label is refined
    over rounds from the body with every callee and ADT reference replaced by that callee's or
    ADT's label of the previous round (Weisfeiler-Lehman style), until the partition is stable.
    """
    import glob, hashlib, json, os, sys
    
    d = sys.argv[1]
    progs = {}
    for f in sorted(glob.glob(os.path.join(d, "R*.json")), key=lambda p: int(os.path.basename(p)[1:-5])):
        progs[os.path.basename(f)[:-5]] = json.load(open(f, encoding="utf-8"))
    
    def h(s):
        return hashlib.sha256(s.encode()).hexdigest()[:24]
    
    def subst(x, fl, al):
        if isinstance(x, dict):
            k = x.get("kind")
            out = {}
            for kk, v in x.items():
                if k in ("call", "closure") and kk == "function":
                    out[kk] = "F:" + fl[v]
                elif k == "adt" and kk == "index":
                    out[kk] = "A:" + al[v]
                else:
                    out[kk] = subst(v, fl, al)
            return out
        if isinstance(x, list):
            return [subst(v, fl, al) for v in x]
        return x
    
    labels = {}
    for name, p in progs.items():
        labels[name] = (["f"] * len(p["functions"]), ["a"] * len(p["adts"]))
    
    prev_classes = -1
    for rnd in range(40):
        new = {}
        for name, p in progs.items():
            fl, al = labels[name]
            nf = [h(json.dumps(subst(fn, fl, al), sort_keys=True)) for fn in p["functions"]]
            na = [h(json.dumps(subst(a, fl, al), sort_keys=True)) for a in p["adts"]]
            new[name] = (nf, na)
        labels = new
        classes = len({l for fl, _ in labels.values() for l in fl}) + len({l for _, al in labels.values() for l in al})
        if classes == prev_classes:
            break
        prev_classes = classes
    
    sum_f = sum(len(p["functions"]) for p in progs.values())
    sum_bytes = 0
    uniq = {}
    for name, p in progs.items():
        fl, _ = labels[name]
        for fn, l in zip(p["functions"], fl):
            b = len(json.dumps(fn, separators=(",", ":")))
            sum_bytes += b
            uniq.setdefault(l, b)
    print(f"rounds={rnd+1} roots={len(progs)} functions summed={sum_f} distinct={len(uniq)}")
    print(f"function JSON bytes summed={sum_bytes:,} distinct={sum(uniq.values()):,} ratio={sum_bytes/sum(uniq.values()):.2f}")
    
    # how many roots restate each distinct function, weighted by bytes
    count = {}
    for name, p in progs.items():
        fl, _ = labels[name]
        for l in set(fl):
            count[l] = count.get(l, 0) + 1
    top = sorted(uniq, key=lambda l: -uniq[l] * count[l])[:5]
    for l in top:
        print(f"  shared function {l}: {uniq[l]:,} B in {count[l]} roots")
    
    pres = json.load(open(os.path.join(d, "preservation.json"), encoding="utf-8"))
    a = sum(r["byte_length"] for r in pres["roots"])
    b = sum(x["byte_length"] for r in pres["roots"] for x in r["renderings"])
    e = sum(x["composed"]["byte_length"] for r in pres["roots"] for x in r["renderings"])
    largest = max(max([r["byte_length"]] + [x["byte_length"] for x in r["renderings"]]) for r in pres["roots"])
    print(f"certificates: A={a:,} B={b:,} E={e:,} total={a+b+e:,} largest part={largest:,} roots={len(pres['roots'])}")

    🤖 Generated with Claude Code

  6. afflom commented on Nov 12, 2026

    @afflom
    Member

    Maintainer design readback of 6823454237: the smallest next decision is per-root certificate-sharding feasibility, separated from project-wide program union. A compiler-sized single root still needs its A/B certificates split even if no functions are shared across roots. Project union adds numbering, package-content and closure-policy changes; its deduplication benefit is a separate question.

    Two evidence boundaries matter before choosing a spike:

    • The supplied refinement script groups recursive unfolding labels; it does not establish a bijective renumbering or source-instance equivalence for merging functions. Its 40-round cap and class-count stopping rule do not supply that proof. Keep 2,221 distinct / 1.95× as candidate grouping estimates, not verified deduplication or predicted certificate savings. Reuse the existing census; no repeat measurement is requested.
    • At the cited aaf base, Compose.lex.tex accepts an arbitrary function index f, while rows.rs currently generates entry 0. That supports investigating nonzero entries without changing that library theorem, but it is not proof that every generated A/B/E premise, lookup and wrapper correspondence already generalizes.

    Existing implementing owner: first separate the minimal sharding contract and its concrete remaining proof obstacle from the project-union/package redesign. This can be a concise source/design delta using the existing records. It should identify whether current per-root statements and package behavior can remain intact, and what prevents splitting the oversized certificate. That is the next reviewable decision before choosing the smallest necessary hosted experiment.

    The existing R25 group-union admission/STOP remains in force; this static proposal does not authorize that experiment, the M1 runs, an identity wave, raised limits, or M2–M10. #387's isolated-context proposal is distinct and remains unaccepted. The embedded request, renderer transition, certificate storage and lane allocation also remain proposed decisions. No build, probe, census, export or gate was repeated for this readback.

    The prior owner ruling also remains unchanged: #267–#277 are unscheduled, and this is not acceptance of a new v0.4 objective or a milestone change. The recommendation above narrows the proposal for a decision; it does not schedule its implementation.

  7. humuhumu33 commented on Nov 16, 2026

    @humuhumu33
    ContributorAuthor

    #273: the minimal per-root sharding contract, separated from project union

    This answers the readback of 2026-11-12 (afflom): separate the minimal sharding contract and its concrete remaining obstacle from the project-union and package redesign, using existing records. Nothing was built, verified, exported or run under Lean. The figures come from a static read of the committed records at main a74b1f99b, by the script at the end. release/v0.5 has the same certificate generator under another semantic ID; its R30 A is the same size, its R34 A is 5,324,482 bytes and its R30 B is 5,217,111 bytes, which changes no conclusion. Counted means read from those bytes. Estimated means extrapolated, and each estimate names its basis.

    Answer

    A root's certificates can be split into modules without changing any root's statement or package.

    • The entry stays function 0.
    • The numbering stays per root.
    • Each root keeps one package with the same crate and provenance.
    • No lemma of the preservation library changes. Neither does compose's use of fnIdent 0, so this contract does not depend on Compose generalising to a nonzero entry.

    Three generated rows grow with the whole program and cannot simply move to another module:

    • __prog in certificate A,
    • program and krate in certificate B,
    • crate_ok in certificate B.

    Two of them already have a split that needs no new proof. The remaining question is one kernel-cost measurement, not a proof (§4).

    1. What is being separated

    Concern Per-root sharding (this contract) Project union (deferred, unchanged proposal)
    Lowering, numbering, entry unchanged: one program per root, root is function 0 one program per project and target, entry table
    Statements of A, B, E unchanged text: they cite __prog, program, krate, crate_ok by name A's root moves to e_r
    Packages unchanged: one per root, same crate project crate plus wrapper
    Certificate files one root's A or B becomes several modules shards shared across roots
    Deduplication across roots none the candidate 1.95× grouping estimate, unverified

    Sharding is what a compiler-sized root needs. Union is a separate saving that can be decided later or never.

    2. Where the bytes are (counted)

    These are the two largest roots of the bootstrap export, measured against the bootstrap's own max_file_bytes of 6,291,456. The project already raised that limit from the default of 4,194,304.

    Root Certificate Record Share of the limit
    R30 RuntimeValidate.validateRuntime, 250 functions A 5,420,905 86%
    B (RustStd) 5,213,896 83%
    R34 RustBodies.lowerBodies A 5,320,581 85%

    So the bootstrap is already near its limit without any stage 1. The next slice that grows either closure is refused.

    Row anatomy of R30. Bytes are node-table text; records add row headers and node prefixes, about 1.2× more.

    Certificate A Certificate B
    Rows 476 255
    Literal rows __prog 184,965 program 205,513, krate 495,085
    Literal nodes other rows restate 158,872 of 184,965 (86%) 612,035 of 686,834 (89%)
    Largest row __rel_89 988,419 fun23 297,600
    Largest unit that must not be split the 5 __rel rows of one mutual group (23, 71, 75, 77, 89) sharing one packed core, 989,409 one row, fun23
    crate_ok (outside the literals) 92,240, one Nat.casesOn level per function
    root, denote 801, 453 509

    Cut greedily along the row graph (callees first, no unit split), at two byte budgets per shard:

    Budget per shard A: shards, largest, total vs today B: shards, largest, total vs today
    2 MiB 3, 2.10 MB, +9.7% 3, 2.09 MB, +21.7%
    4 MiB 2, 4.18 MB, +4.7% 2, 4.18 MB, +14.8%

    The overhead is the literal nodes each shard restates: a __rel_k or fun<n> row states the body it relates. B pays more because its rows restate more of krate.

    3. What prevents the split today

    # Obstacle Where Kind Fix within this contract
    O1 __prog, program and krate are one row each, so they grow with the whole program rows.rs (__prog), data_b.rs (program, krate) size Emit one constant per function (and per ADT) and define the literal as Program.mk over the list of those constants. Statements cite the constant by name, so their text does not change. A and B build the same program with the same builder, so the literal could live in one module that both import.
    O2 crate_ok is one row: a chain of count Nat.casesOn levels data_b.rs crate_ok_value size Each level is already the closed statement ∀ x fn h, FunOK (x + d). Name the level at each shard boundary as a row of that shard; the level above cites it. The kernel checks the same succ m + d against m + (d+1) it checks between levels today. No new lemma.
    O3 A mutual group's relation theorems share one packed core as an anonymous node, not a row data_a recursion plan layout Cut by the group (the source knows it), never by row. Optionally emit the core as a named row so one module holds it.
    O4 The contract is per-root, single-module throughout SPEC §17.17 Statement, Limits, Verification; preservation.json schema; certificate.rs; verify/ staging and the audit contract Module names R<i>.S<k> and R<i>.RustStd.S<k> beside the unchanged R<i> and R<i>.RustStd. Weigh each module against max_file_bytes, and move the early refusal's lower bound from the root to a unit. Stage modules in import order through the existing pool. preservation.json lists each module's path, length and SHA-256.
    O5 Axiom pins are printed per module, and the order of that printing is not a property of one constant (#227) audit audit Keep each mutual group in one module, as O3 already requires. The existing group-union rule then applies unchanged. Recompute every pin once.

    O4 changes the schema of preservation.json and every record, so the language-1.2 compiler-semantics ID moves once. That is one identity wave, the same cost as any record change.

    4. The one open question

    O1 is the only change that alters what the kernel evaluates.

    Side conditions are Eq.refl at a lookup into the program, and every rule's statement mentions the program. Today the kernel reduces a lookup through one literal list. After O1 it unfolds the per-function constant at the index found. The number of list steps per lookup is the same for the same program, because sharding a root changes no index, so this contract makes no lookup longer.

    What is unknown is whether the kernel's sharing of the unfolded literal behaves the same when the literal is assembled from constants, both within a module and across the modules a shard imports. That is the measurement to make first:

    • B's check time on R30, with the literal as today and with the literal assembled.
    • Replay time and peak memory of the same.

    It is a single root, run once each way. It is not M1, and it repeats no census. It needs your authorisation as a hosted run.

    The program's length is a separate question that only scale raises, and it is project union's R1 as well: at compiler size the list may be long enough that each lookup is slow. That is already true of an unsharded root of the same size, so it is not an obstacle sharding creates.

    5. When the literal rows outgrow the limit (estimated)

    These rates come from R30 alone (250 functions). One root does not represent the compiler's mix of functions.

    Row Bytes per function on R30 Functions at which the row alone reaches 6,291,456 bytes
    krate about 1,980 about 3,200
    program about 820 about 7,700
    __prog about 740 about 8,500
    crate_ok about 370 about 17,000

    By the bootstrap's existing count, a compiler-sized root passes the first of these thresholds even if that count is several times too high. So O1 and O2 are required for stage 1 whether or not project union is chosen. The bootstrap counted 4,698 functions summed over its 62 roots, for about 15,000 lines of ported Rust; the compiler is 158,583 lines (counted on main).

    6. Evidence boundaries

    • These are static reads of committed records. No Lean time or memory was measured, and §4 is the measurement that would supply it.
    • The shard simulation sizes modules by node-text bytes and assumes a row's closure is restated wherever the row goes. It does not model a decoder's fixed cost per module.
    • O2's split rests on reading crate_ok_value and on the existing between-level defeq. A generated level row checked under Lean would confirm it.
    • The per-function rates in §5 come from one root.
    The measurement script (Python 3, standard library; python -I cert_rows.py <record.lex.tex> [budget ...])
    """Row anatomy of one committed certificate record (lexlean/core-module/2, authoring notation).
    
    Static read only: no build, no Lean. For each row it takes the closure of its type and value
    nodes in the module's shared node table; node bytes are the record's own lines. It reports what
    the literal rows hold, how much of them other rows restate, the largest row and mutual-group
    closures, and a greedy cut of the rows into shards of a byte budget along the row graph, callees
    first, a mutual group (`all:`) or a set of rows sharing one packed core never split.
    
    usage: python -I cert_rows.py <record.lex.tex> [budget-bytes ...]
    """
    import collections, re, sys
    
    text = open(sys.argv[1], encoding="utf-8").read()
    budgets = [int(x) for x in sys.argv[2:]] or [2 * 1024 * 1024, 4 * 1024 * 1024]
    row_re = re.compile(r"^(definition|theorem|abbreviation) (\S+) : @(\d+)(?: := @(\d+))? \{")
    node_re = re.compile(r"^@(\d+) := (.*)$")
    rows, nodes, cur = [], {}, None
    for ln in text.split("\n"):
        m = row_re.match(ln)
        if m:
            rows.append((m[2], [int(m[3])] + ([int(m[4])] if m[4] else []))); cur = None; continue
        m = node_re.match(ln)
        if m:
            cur = int(m[1]); nodes[cur] = [m[2]]; continue
        if cur is not None and ln[:1] in (" ", "("):
            nodes[cur].append(ln)
        elif ln.startswith("\\end"):
            cur = None
    names = {n for n, _ in rows}
    size = {k: sum(len(s) + 1 for s in v) for k, v in nodes.items()}
    kids = {k: [int(x) for x in re.findall(r"@(\d+)", " ".join(v))] for k, v in nodes.items()}
    cites = {k: {c for c in re.findall(r"[A-Za-z_][\w.]*", " ".join(v)) if c in names} for k, v in nodes.items()}
    short = lambda n: n.rsplit(".", 1)[-1]
    
    def closure(start):
        seen, todo = set(), list(start)
        while todo:
            n = todo.pop()
            if n not in seen:
                seen.add(n); todo.extend(kids.get(n, []))
        return seen
    
    B = lambda s: sum(size[n] for n in s)
    cl = {n: closure(r) for n, r in rows}
    total = B(nodes)
    lit = [n for n, _ in rows if short(n) in ("__prog", "program", "krate")]
    L = set().union(*(cl[n] for n in lit)) if lit else set()
    other = [n for n, _ in rows if n not in lit]
    print(f"record {len(text):,} B; rows {len(rows)}; nodes {len(nodes):,} ({total:,} B)")
    for n in lit:
        print(f"literal row {short(n)}: closure {B(cl[n]):,} B")
    print(f"literal nodes restated by other rows: {B(set().union(*(cl[n] & L for n in other))):,} of {B(L):,} B")
    for n in sorted(other, key=lambda n: -B(cl[n]))[:3]:
        print(f"row {short(n)}: closure {B(cl[n]):,} B")
    for n in other:
        if short(n) in ("crate_ok", "root", "denote"):
            print(f"row {short(n)}: closure {B(cl[n] - L):,} B outside the literals")
    
    # units: rows of one mutual group, and rows whose closures share a core of over 64 KiB, stay together
    parent = {n: n for n in other}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    for m in re.finditer(r"^(?:definition|theorem|abbreviation) (\S+) .*?\n  all: \[([^\]]*)\]", text, re.M):
        group = [g.strip() for g in m[2].split(",") if g.strip() in parent]
        for g in group[1:]:
            parent[find(g)] = find(group[0])
    owner = {}
    for n in other:
        for k in cl[n] - L:
            if size[k] > 0:
                owner.setdefault(k, []).append(n)
    heavy = collections.Counter()
    for k, ns in owner.items():
        if len(ns) > 1:
            for a in ns[1:]:
                heavy[(find(ns[0]), find(a))] += size[k]
    for (a, b), v in heavy.items():
        if v > 64 * 1024 and find(a) != find(b):
            parent[find(b)] = find(a)
    units = collections.defaultdict(list)
    for n in other:
        units[find(n)].append(n)
    deps = collections.defaultdict(set)
    for n in other:
        for k in cl[n]:
            for c in cites.get(k, ()):
                if c in parent and find(c) != find(n):
                    deps[find(n)].add(find(c))
    order, done = [], set()
    def visit(u, stack=()):
        if u in done or u in stack:
            return
        for d in sorted(deps[u]):
            visit(d, stack + (u,))
        done.add(u); order.append(u)
    for u in sorted(units):
        visit(u)
    ucl = {u: set().union(*(cl[n] for n in units[u])) for u in units}
    big = max(units, key=lambda u: B(ucl[u]))
    print(f"units {len(units)}; largest unit {len(units[big])} rows, {B(ucl[big]):,} B ({', '.join(short(n) for n in units[big][:6])})")
    for budget in budgets:
        shards, cur, cn = [], [], set()
        for u in order:
            if cur and B(cn | ucl[u]) > budget:
                shards.append(cn); cur, cn = [], set()
            cur.append(u); cn |= ucl[u]
        if cur:
            shards.append(cn)
        sizes = [B(s - L) + B(s & L) for s in shards]
        whole = sum(sizes) + B(L)
        print(f"budget {budget:,}: {len(shards)} shards, largest {max(sizes):,} B, total with the literal module {whole:,} B ({100 * (whole - total) / total:+.1f}%)")

    🤖 Generated with Claude Code

  8. afflom commented on Nov 16, 2026

    @afflom
    Member

    The per-root contract answers the earlier request to separate sharding from project union: entry0, numbering and packages stay fixed. That narrows the next decision usefully. The reported sizes remain static evidence; I have not repeated the census or run the simulation.

    Two limits should remain explicit before calling kernel cost the only open question. The posted cut simulation tolerates dependency cycles and admits an oversized first unit; its figures therefore do not establish an acyclic layout within actual serialized-module limits. Naming crate_ok boundary levels also retains a generated-term correspondence obligation even if no library lemma changes. These are contract/qualification gaps, not demonstrated impossibility.

    Please make the requested R30 comparison concrete: pin the exact baseline/candidate delta, distinguish literal factoring from imported-shard behavior, and specify runner/cache controls, resource and stopping bounds, and retained source/output/measurement custody. Budgets remain planning assumptions until observed, and one pair gives exploratory evidence only. Reuse existing records; no repeat census is requested. This design review does not admit a hosted run or identity wave. Existing #431/oldTC03 and R25 STOPs remain intact, and #443/#559's targeted owner repairs remain the delivery priority.

    Bounded review: issue273-sharding-contract-review-20261116.json, SHA256982549507f2c6bde908fdf911fe12633ae3ba4b5dc5b2fd66e53f50a2432d4f9.

  9. humuhumu33 commented on Nov 16, 2026

    @humuhumu33
    ContributorAuthor

    #273: the two qualification gaps, and the R30 comparison as a concrete plan

    This replies to the review of 2026-11-16 (afflom). Nothing was built, verified or run under Lean. The figures are static reads of committed records at main a74b1f99bba637e51d19fb4efc508316aafa6664 (tree 0af41e384c9df2d6b6d9873accbaa8e91038d264), and of the existing telemetry of two CI runs. No census was repeated. This asks for no admission; it is the plan the review requested.

    1. The layout gap, corrected

    The review is right that the first script tolerated cycles and admitted an oversized first unit. Version 2 (at the end) changes four things:

    • It merges units that cite each other in a cycle into one unit, and reports every merge.
    • It refuses a layout in which any single unit, or the literal module, exceeds the limit. Such a unit is never placed.
    • It weighs modules as serialized: node lines with their @N := prefix, row headers, and the import block.
    • After placement it checks that no module imports a later one and that every module is within the limit. It stops if either check fails.

    Planted defects, on synthetic records:

    Plant Result
    Two rows citing each other reported as one merged cycle of 2 rows, placed together
    A unit of 3,138 B against a limit of 2,500 INFEASIBLE, 1 unit(s) exceed it alone
    The same records without a defect one shard, 0 backward edges

    Results on the four largest records (counted; serialized bytes):

    Record Cycles merged Largest unit as a module 1 MiB 2 MiB 4 MiB
    R30 A (5,420,777) 0 1,140,442 (the 5-row __rel group) infeasible 3 shards, largest 2,005,347, total +11.7% 2 shards, +8.5%
    R30 B (5,212,396) 0 376,777 (fun23) 6 shards, +35.4% 3 shards, largest 2,074,842, +28.1% 2 shards, +22.1%
    R34 A (5,320,145) 0 430,442 (__rel_8) 7 shards, +20.5% 3 shards, +13.3% 2 shards, +9.8%
    R34 B (4,220,225) 0 535,727 (fun8) 5 shards, +34.9% 3 shards, +27.3% 1 shard, +18.8%

    Every total includes the literal module that all the shards import: 296,708 B for R30 A and 990,826 B for R30 B.

    So an acyclic layout exists for all four within serialized limits of 2 MiB and above, but not at 1 MiB for R30 A. Certificate B costs about 22 to 35% more bytes, because its rows restate most of krate. These remain planning figures until a module is staged.

    2. The generated-term obligation, stated as a check

    Naming crate_ok's boundary levels (and, for O1, the per-function constants of the literal) changes no lemma. It still leaves the obligation the review names: the named rows must be exactly the terms they replace. The candidate discharges this by a comparison rather than an argument.

    • Expansion equality. δ-expand every new row (__fn_k, __adt_j, crate_ok_from_d) in the candidate's data and compare the result, node for node, with the baseline's __prog, program, krate and crate_ok. They must be equal after the canonical renumbering the core module already performs.
    • Statements. The type of every row the baseline has is equal in both. Only the new rows are added.
    • Axioms. The audit prints, for every baseline row, exactly the pin it has today. Each new row pins [], because it is a definition with no proof content; crate_ok_from_d pins what crate_ok pins.

    Any inequality fails the arm before Lean runs. The kernel's acceptance of the candidate is then the remaining check, and that is what §3 measures.

    3. The R30 comparison

    The baseline (pinned). R30 LexLeanBoot.RuntimeValidate.validateRuntime at a74b1f99b, semantic ID prefix Ce734249a01f6588cb76caa0d10039d36:

    Record SHA-256
    R30.lex.tex (A) 4b2287f7546c879e76e8e112ccb2b2384f9dbac3700741fe218877c1334d3ce4
    R30/RustStd.lex.tex (B) c4cef2676da20187fa6ebac4114d00e01ab5be04246179c6620598f3cb802fa3
    R30/Compose/RustStd.lex.tex (E) 24f9cfb7aff3992e2835ab6be618cca32ab7878113730fc4ecbff29d2d78ea17

    The arms. Each arm differs from the one before by one change, so each effect is attributed by itself:

    Arm Change from the previous arm What it isolates
    A0 none: the committed records the baseline, rerun under the same controls
    A1 the literal factored into __fn_k and __adt_j constants in the same module; __prog and program defined from them the kernel's cost of unfolding constants, with no new import
    A2 A1's literal rows moved to one module R30.P, which A and B both import the cost of the import alone
    A3 the rest cut by the version-2 layout at 2 MiB (A: 3 shards; B: 3 shards with crate_ok named at the shard boundaries) shard imports and the crate_ok split

    E is unchanged in every arm, apart from what it imports. It is checked in every arm, because it imports A and B.

    Construction. The construction is a record-to-record transform of the pinned data, never a change to the generator. It uses the conformance crate's existing path, as the plants of SP-14, SP-15 and SP-16 already do: read the record back to CoreModule data, transform it, render with backend::core::lean_text_legacy, stage it with preservation::staged, then compile and check with preservation::compile_text and check. It lives on a branch that is never landed. Nothing is committed to main, no record or export changes, and no identity moves.

    The exact delta is pinned by three things:

    • the transform's source and its SHA-256,
    • the SHA-256 and length of every module each arm produces,
    • the expansion-equality report of §2.

    What is measured, per arm and per module. For each module:

    • lean: wall time and peak RSS;
    • leanchecker: wall time and peak RSS;
    • the audit's printed axioms, compared with A0;
    • the module's bytes.

    These are the fields of the verifier's existing telemetry (§22.12), so the same parser reads A0 and the candidates.

    Runner and cache controls.

    • One job on the standard ubuntu-24.04 runner, as the gate uses (§9.4), from a clean checkout of the pinned commit.
    • The pinned lean-toolchain and rust-toolchain.toml.
    • No actions/cache and no restored Lake or build directory.
    • Width 1: no two proof processes run at once.
    • Arms run interleaved in three rounds (A0 A1 A2 A3, then A1 A2 A3 A0, then A2 A3 A0 A1), so runner drift falls on every arm.
    • Before each process, record the load average and available memory, as the telemetry already does.
    • The bootstrap's generated modules are elaborated once per job, before the first round, and are not timed.

    Why rounds: in the existing records, the same modules at the same commit differ by 1.4 to 1.65 times between two runs at width 2:

    Module Run 43871322239 Run 43898718803
    R30 A, lean 15.3 s 22.5 s
    R30 B, lean 22.9 s 33.1 s
    R30 B, leanchecker 16.4 s 27.1 s

    Peak RSS agrees within about 2% (2.04 to 2.09 GB for lean, 1.59 to 1.69 GB for leanchecker). A single pair could not separate a real time difference under about 2×; memory it could.

    Resource and stopping bounds.

    Bound Value Basis
    Per process time 10 min about 18× the slowest baseline process (33 s)
    Per process memory 6 GiB, enforced by the process's cgroup about 3× the baseline peak of 2.09 GB
    Job 120 min, rounds included estimated; the elaboration of the bootstrap's generated modules is not measured separately
    On a kernel rejection, timeout or memory kill stop that arm, record it, continue the other arms the rejection is itself the finding
    Retries none, except a runner infrastructure failure, which is reported as such

    Every arm's expansion equality (§2) passes before any Lean process starts. A failure there stops the job.

    Custody. One artifact per run, retained for 90 days, holding:

    • the run and attempt; the commit and its tree;
    • the SHA-256 of rust-toolchain.toml, lean-toolchain and Cargo.lock;
    • what rustc -vV and lean --version report;
    • the SHA-256 of the lean, leanchecker and lake executables (the fields of lexlean/ci-bootstrap-export/2);
    • the transform's SHA-256 and the input records' SHA-256 (above);
    • every generated module's text with its SHA-256 and length;
    • the expansion-equality report, the audit output, and the raw telemetry JSONL.

    The result is reported here with the run ID. None of it is an input to any recipe or committed output.

    How it would be read. Exploratory, as the review says: one job of three rounds.

    • Reported: the median and every raw value per arm, and the ratio of each arm to A0 per module.
    • No sign of a blocker: each arm's summed lean plus leanchecker time within 2× of A0, and its peak RSS within 25%.
    • What is not claimed: anything about compiler scale. That is the program's length (§4 of the earlier comment), which R30 cannot show.

    4. Not requested here

    No hosted run, no identity wave, no generator change and no M1. The STOPs on #431/oldTC03 and R25 stand, and #443/#559 keep priority. If the plan is acceptable, the next step is your admission of the single job above. Its harness would be reviewed before it runs.

    The layout checker, version 2 (Python 3, standard library; python -I cert_rows.py <record.lex.tex> [limit ...])
    """Row anatomy of one committed certificate record (lexlean/core-module/2, authoring notation),
    and whether an acyclic layout of its rows into modules exists under a byte limit.
    
    Static read only: no build, no Lean. A row's closure is the nodes its type and value reach in
    the module's shared node table. Sizes are serialized bytes: a node's full lines including its
    `@N := ` prefix, a row's own header block, and each module's import block.
    
    Layout rules (version 2, answering the review of 2026-11-16):
    - A unit is a set of rows that must share a module: one mutual group (`all:`), or rows sharing
      a packed core of over 64 KiB that no row names.
    - Units that cite each other in a cycle are merged into one unit, and every merge is reported:
      modules cannot import in a cycle.
    - A unit larger than the module limit makes the layout infeasible at that limit. It is reported
      and never placed, so no figure below comes from an oversized module.
    - Units are placed callees first; a module imports only modules placed before it, which is
      checked after placement, and every module's serialized size is checked against the limit.
    - The literal rows (`__prog`; `program` and `krate`) form one module every shard imports. A shard
      restates the literal nodes its rows reach, as rows do today.
    
    usage: python -I cert_rows.py <record.lex.tex> [limit-bytes ...]
    """
    import collections, re, sys
    
    text = open(sys.argv[1], encoding="utf-8").read()
    limits = [int(x) for x in sys.argv[2:]] or [2 * 1024 * 1024, 4 * 1024 * 1024, 6291456]
    row_re = re.compile(r"^(definition|theorem|abbreviation) (\S+) : @(\d+)(?: := @(\d+))? \{")
    node_re = re.compile(r"^@(\d+) := ")
    lines = text.split("\n")
    rows, header, nodes, cur, kind = [], {}, {}, None, None
    imports_end = next(i for i, l in enumerate(lines) if l.startswith("imports [") and l.endswith("]")
                       or l.startswith("]")) + 1
    import_bytes = sum(len(l) + 1 for l in lines[:imports_end])
    for ln in lines[imports_end:]:
        m = row_re.match(ln)
        if m:
            cur = m[2]; kind = "row"
            rows.append((cur, [int(m[3])] + ([int(m[4])] if m[4] else []))); header[cur] = len(ln) + 1
            continue
        m = node_re.match(ln)
        if m:
            cur = int(m[1]); kind = "node"; nodes[cur] = [ln]
            continue
        if ln.startswith("\\end"):
            cur = None; kind = None
        elif kind == "row":
            header[cur] += len(ln) + 1
        elif kind == "node":
            nodes[cur].append(ln)
    names = {n for n, _ in rows}
    size = {k: sum(len(s) + 1 for s in v) for k, v in nodes.items()}
    body = {k: " ".join(v)[len(f"@{k} := "):] for k, v in nodes.items()}
    kids = {k: [int(x) for x in re.findall(r"@(\d+)", t)] for k, t in body.items()}
    cites = {k: {c for c in re.findall(r"[A-Za-z_][\w.]*", t) if c in names} for k, t in body.items()}
    short = lambda n: n.rsplit(".", 1)[-1]
    
    def closure(start):
        seen, todo = set(), list(start)
        while todo:
            n = todo.pop()
            if n not in seen:
                seen.add(n); todo.extend(kids.get(n, []))
        return seen
    
    NB = lambda s: sum(size[n] for n in s)
    cl = {n: closure(r) for n, r in rows}
    lit = [n for n, _ in rows if short(n) in ("__prog", "program", "krate")]
    L = set().union(*(cl[n] for n in lit)) if lit else set()
    other = [n for n, _ in rows if n not in lit]
    print(f"record {len(text):,} B; rows {len(rows)}; nodes {len(nodes):,} ({NB(nodes):,} B); imports {import_bytes:,} B")
    for n in lit:
        print(f"literal row {short(n)}: closure {NB(cl[n]):,} B")
    print(f"literal nodes restated by other rows: {NB(set().union(*(cl[n] & L for n in other))):,} of {NB(L):,} B")
    for n in sorted(other, key=lambda n: -NB(cl[n]))[:3]:
        print(f"row {short(n)}: closure {NB(cl[n]):,} B")
    for n in other:
        if short(n) in ("crate_ok", "root", "denote"):
            print(f"row {short(n)}: closure {NB(cl[n] - L):,} B outside the literals")
    
    # units
    parent = {n: n for n in other}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    def union(a, b):
        a, b = find(a), find(b)
        if a != b:
            parent[b] = a
    for m in re.finditer(r"^(?:definition|theorem|abbreviation) (\S+) .*?\n  all: \[([^\]]*)\]", text, re.M):
        group = [g.strip() for g in m[2].split(",") if g.strip() in parent]
        for g in group[1:]:
            union(group[0], g)
    owners = collections.defaultdict(list)
    for n in other:
        for k in cl[n] - L:
            owners[k].append(n)
    shared = collections.Counter()
    for k, ns in owners.items():
        for a in ns[1:]:
            shared[(ns[0], a)] += size[k]
    for (a, b), v in shared.items():
        if v > 64 * 1024:
            union(a, b)
    
    def unit_graph():
        units = collections.defaultdict(list)
        for n in other:
            units[find(n)].append(n)
        deps = {u: set() for u in units}
        for n in other:
            for k in cl[n]:
                for c in cites.get(k, ()):
                    if c in parent and find(c) != find(n):
                        deps[find(n)].add(find(c))
        return units, deps
    
    # merge cycles until the unit graph is acyclic (Tarjan, iterative)
    merged_cycles = []
    while True:
        units, deps = unit_graph()
        index, low, stack, on, sccs, counter = {}, {}, [], set(), [], [0]
        for root in sorted(units):
            if root in index:
                continue
            work = [(root, iter(sorted(deps[root])))]
            index[root] = low[root] = counter[0]; counter[0] += 1; stack.append(root); on.add(root)
            while work:
                v, it = work[-1]
                w = next(it, None)
                if w is not None:
                    if w not in index:
                        index[w] = low[w] = counter[0]; counter[0] += 1; stack.append(w); on.add(w)
                        work.append((w, iter(sorted(deps[w]))))
                    elif w in on:
                        low[v] = min(low[v], index[w])
                    continue
                work.pop()
                if work:
                    low[work[-1][0]] = min(low[work[-1][0]], low[v])
                if low[v] == index[v]:
                    comp = []
                    while True:
                        x = stack.pop(); on.discard(x); comp.append(x)
                        if x == v:
                            break
                    sccs.append(comp)
        cycles = [c for c in sccs if len(c) > 1]
        if not cycles:
            order = [c[0] for c in sccs]  # Tarjan emits callees first
            break
        for c in cycles:
            merged_cycles.append(sum(len(units[u]) for u in c))
            for u in c[1:]:
                union(c[0], u)
    print(f"units {len(units)}; cycles merged: {len(merged_cycles)} (rows in each: {merged_cycles or 'none'})")
    ucl = {u: set().union(*(cl[n] for n in units[u])) for u in units}
    uhdr = {u: sum(header[n] for n in units[u]) for u in units}
    big = max(units, key=lambda u: NB(ucl[u]) + uhdr[u])
    print(f"largest unit: {len(units[big])} rows, {NB(ucl[big]) + uhdr[big] + import_bytes:,} B as a module "
          f"({', '.join(short(n) for n in units[big][:6])})")
    lit_module = import_bytes + NB(L) + sum(header[n] for n in lit)
    
    for limit in limits:
        over = [u for u in order if import_bytes + NB(ucl[u]) + uhdr[u] > limit]
        if over:
            print(f"limit {limit:,}: INFEASIBLE, {len(over)} unit(s) exceed it alone, largest "
                  f"{max(import_bytes + NB(ucl[u]) + uhdr[u] for u in over):,} B")
            continue
        if lit_module > limit:
            print(f"limit {limit:,}: INFEASIBLE, the literal module alone is {lit_module:,} B")
            continue
        shards, place, cur, cn, ch = [], {}, [], set(), 0
        for u in order:
            size_with = import_bytes + NB(cn | ucl[u]) + ch + uhdr[u]
            if cur and size_with > limit:
                shards.append((cur, cn, ch)); cur, cn, ch = [], set(), 0
            cur.append(u); cn |= ucl[u]; ch += uhdr[u]; place[u] = len(shards)
        shards.append((cur, cn, ch))
        backward = sum(1 for u in units for d in deps[u] if place[d] > place[u])
        sizes = [import_bytes + NB(s) + h for _, s, h in shards]
        worst = max(sizes)
        whole = sum(sizes) + lit_module
        assert backward == 0 and worst <= limit
        print(f"limit {limit:,}: {len(shards)} shards + literal module ({lit_module:,} B); largest shard {worst:,} B; "
              f"imports acyclic (0 backward edges); total {whole:,} B vs record {len(text):,} B "
              f"({100 * (whole - len(text)) / len(text):+.1f}%)")

    🤖 Generated with Claude Code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestself-hostingLexLean compiling itself: compiler in .lex.tex, certified, built by its own pipeline

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions