/** * CHOICE COST — the shape of an ordered choice, and what that shape costs. * ======================================================================== * * READ THIS FIRST: THIS MEASURES THE INTERPRETER, NOT THE SHIPPED PARSER. * ---------------------------------------------------------------------- * The interpreter's `firstMatch` loop (src/combinators/choice.ts:149-165) enters every * alternative unconditionally. The EMITTED engine does not: `src/table/emit-assembly.ts` * hoists a per-choice candidate mask and emits a per-arm first-CHARACTER guard, so an arm * whose first set excludes the character at the current position is never entered. * First-set gating is this project's single largest parse lever — 25-48% across all * four jess parsers — and a naive interpreted profile is blind to every byte of it. * * So `profileWastedWork` reports TWO columns and derives neither from the other: * `attempts`/`wastedBytes` (interpreted) and `gatedAttempts`/`gatedWastedBytes` * (modelling codegen's guard — see `compiledFirstCharGate`). Rankings use the compiled * column. The DELTA is itself a result: an arm expensive interpreted and cheap gated is * ALREADY SOLVED by codegen, and reordering it is unpaid work. * * WHAT THE GATE ACTUALLY REMOVES — measured, not assumed. * Over jess's four dialect grammars (637 kB of CSS, 212 kB of Less): * * dialect arms whose GATED BYTES differ arm entries removed by the gate * css 0 of 158 331,313 of 435,767 (76%) * less 0 of 199 413,737 of 562,852 (74%) * scss 0 of 200 617,735 of 777,356 (79%) * jess 0 of 158 325,655 of 388,263 (84%) * * The gate removes ATTEMPTS, not rescanned BYTES — and the byte columns are identical * to the byte in all four. That is structural, not a coincidence of these corpora: the * guard is derived from the arm's first SET, which over-approximates what the arm can * start with, so whenever the guard rejects, the arm's own leading terminal would have * rejected at the same position having consumed nothing. * * The practical consequence, and the reason this warning is at the top: any claim of * the form "this arm is entered on every X and fails N% of the time" is a statement * about the INTERPRETER and is usually false of the shipped parser. A byte ranking * survives the correction; a failure-RATE or attempt-count claim does not. Measured on * jess's CSS `Value` choice, arm 0 `Percentage` reads as 25,939 entries at 97% failure * interpreted, and 7,455 at 90% gated — the same arm, a fifth as important. Arm 4 * `IdentBlock` is 100% failure in BOTH columns and carries 27,131 bytes; it is the real * finding, and only the gated column makes that legible. * * KNOWN LIMIT OF THE MODEL. On the compose/linkable path a named-rule arm gets a * DEFERRED guard (an `@FS:name@` placeholder) that fuse time rewrites with the winning rule's * first set — or with `true`, always-try, if it cannot be resolved. This model always * resolves, so for cross-artifact ref arms `gatedAttempts` is a LOWER bound: the * shipped artifact may enter such an arm more often than modelled. Where a compiled * measurement disagrees with this report on an arm that is a bare rule reference, the * compiled measurement is right. * * A PEG `choice` is ordered: arm `i` is only reached once arms `0..i-1` have been * TRIED AND FAILED, and every one of those failures re-scanned input that the * winning arm then scans again. So each additional alternative, and each earlier * alternative, has a time cost — and that cost is invisible in the grammar source, * which is why grammar shape drifts without anything going red. * * This module makes it visible, in two halves that answer two different questions. * * STATIC — `analyzeChoiceInventory()` * Which choice sites have alternatives that share a leading term, and for each: * did the compiler LEFT-FACTOR it, or did it decline, and why? `detectSharedPrefix` * (src/combinators/choice.ts) already computes this to decide whether to emit the * `sharedPrefix` strategy, but it is ALL-OR-NOTHING (every arm must share) and it * returns `null` on the first arm that does not qualify — silently, with no record * of how close the site came or which arm blocked it. The inventory reports the * declines, with the blocking arm and the reason. That set is the refactor backlog, * GENERATED rather than noticed by a human reading grammar source. * * It is complete, not sampled: every `choice` reachable from the rule map appears, * including the ones with nothing to report (`groups: []`). * * DYNAMIC — `profileWastedWork()` * How many BYTES were re-scanned because an alternative was tried and failed, * attributed per choice site and per arm, over a real corpus. Ordering pathologies * fall out of the ranking for free: an arm that fails 98% of the time while sitting * first is exactly the top entry. * * The static half can only see shape. It cannot know that one declined site is on * the hot path of every stylesheet and another is reached twice a year. The dynamic * half supplies that weight. Neither is sufficient alone. * * WHY BYTES, AND WHY THIS IS GATEABLE * ----------------------------------- * The metric is a COUNT of input bytes, not a timing. It is a pure function of * (grammar, corpus): the same grammar over the same corpus yields the same number on * an idle machine and on a machine at load 10. There is no noise floor to argue about * and no rebaseline needed for a hardware change. That is what makes it usable as a * deterministic gate rather than a benchmark. * * INTERPRETED MODE ONLY * --------------------- * Nothing here is emitted into a compiled parser and nothing here costs codegen a * single byte or a single millisecond. The profiler does not add an instrumentation * flag to the hot combinators either — `src/combinators/choice.ts` is UNTOUCHED by * this file. Instrumentation is installed by temporarily substituting arm slots and * terminal `parse` methods on the combinator tree, and removed in a `finally`. When * you are not profiling, the cost is exactly zero because the shipping code contains * no profiling branch to skip. * * (For contrast: `run({ profile })` — the node/slot-count profiler — was compiled-path * only, was never implemented in the interpreter, and now throws rather than reporting * zeros. See src/functional/run.ts. This is a different measurement and a new build, * not a port of that one.) * * WHAT THIS INSTRUMENT CANNOT SEE * ------------------------------- * Stated up front, because a diagnostic whose blind spots are undocumented gets read * as complete: * * 0. It measures the INTERPRETER. See the top of this header — this is the blind spot * that reorders results rather than merely shifting them, which is why it is not * in this list but above it. The `gated*` columns model it; they do not remove it. * 1. Only `firstMatch` and `sharedPrefix` choices are instrumented. Those are the * two strategies that try arms in order and can fail one. A `disjoint` choice * dispatches on the first character and tries exactly one arm; `greedyClassify` * runs one regex; `literalsLongestFirst` captures its sorted arm array at * construction, so slot substitution cannot reach it. Their sites still appear * in the static inventory, with zero dynamic cost recorded and `instrumented: * false` so the zero is not mistaken for a measurement. * 2. Backtracking that is not a choice arm — a failed `many` element, a failed * `optional`, a rolled-back `attempt` — is not attributed. Those bytes are real * but they are not an ORDERING decision, which is what this instrument exists to * rank. * 3. An arm that SUCCEEDS and is then rejected by the `autoNot` check is recorded as * a success, because the rejection happens inside the choice loop after the arm * has returned. Its rescan is invisible here. * 4. `wastedBytes` is input bytes re-scanned, not CPU. An arm that fails after one * byte but allocated on the way is cheap by this metric and not by the clock. * This ranks ORDERING, and is deliberately not a profiler. * * SET EXPECTATIONS ACCORDINGLY, because this has been measured. A jess lane acted * on a finding from this report and cut rescanned bytes at one route from 27,678 * to 8,367 — a 69.8% reduction, exactly as this instrument predicts — for ZERO * measurable wall-clock change. A large byte win that produces no time win is the * expected outcome, not a failure of the fix: re-scanning is cheap per byte, and * what makes a grammar slow is usually allocation and node construction, which * this metric cannot see. Use it to find and rank ORDERING defects and to prove a * restructure did what it claimed. Do not use it to predict a speedup, and do not * let a flat benchmark be read as evidence the finding was wrong. * 5. Reach is measured by the furthest position at which a TERMINAL was attempted * (`literal`/`regex`/`keywords`/`scanTo`). A combinator that consumes without * going through one of those would under-report; none exists today. */ import type { Combinator } from '../types.ts'; import type { ChoiceStrategyTag } from './gating.ts'; import type { FirstSet } from '../types.ts'; /** A combinator's location in the grammar: owning rule plus structural path. */ export type ChoiceSite = { /** Nearest enclosing `_ruleName`, or the rule-map key it was reached under. */ rule: string; /** Structural path inside that rule, e.g. `seq[2] › node(AtRule) › choice[0]`. */ path: string; }; /** The stable identity of a site. Used as the sort key and the baseline key, so it * must be derived only from grammar structure — never from a file path or a run. */ export declare const choiceSiteKey: (s: ChoiceSite) => string; /** Why one ARM contributed no shareable leading term. */ export type ArmDeclineReason = /** The arm is not a (wrapper-peeled) `sequence` — e.g. a bare ref, a nested * `choice`, an `optional`. `leadingTermOfArm` peels only node/grammar/transform/ * label, because those are the wrappers that consume nothing before the sequence. */ 'not-a-sequence' /** A `sequence` of one term: there is no residual to factor out from. */ | 'sequence-shorter-than-2' /** The leading term is a case-INSENSITIVE literal. Excluded deliberately: the * matched text differs from the literal's own value, so a replayed leaf would * carry the wrong string. */ | 'lead-case-insensitive-literal' /** The leading term is not a bare literal/regex — a ref, a node, a label, a * transform, another choice. Factoring through it would change the value or * capture shape of the arm. */ | 'lead-not-concrete-terminal'; /** Why the SITE as a whole was not left-factored. */ export type SiteDeclineReason = /** First-char dispatch already selects exactly one arm; there is nothing to factor. * Not a backlog entry — this is the good state. */ 'disjoint-dispatch' /** At least one arm carries a runtime gate; per-arm predicates are incompatible * with the factoring strategies. */ | 'gated-arms' /** `greedyClassify` or `literalsLongestFirst` matched first. Both are stronger than * `sharedPrefix` (neither backtracks), so this is also not a backlog entry. */ | 'strategy-preempted' /** Fewer than two arms. */ | 'fewer-than-two-arms' /** At least one arm produced no shareable leading term. See `armDeclines` for which * arm and why. THIS is the backlog: a subset of arms may still share a prefix that * the all-or-nothing detector never records. */ | 'arms-not-factorable' /** Every arm produced a leading term, but they are not all the same term. Also the * backlog: two arms out of nine sharing `@` is real, repeated work. */ | 'leads-differ'; /** A maximal set of arms at one site sharing an identical concrete leading term. */ export type PrefixGroup = { /** Structural key of the shared term. Injective by construction (JSON-encoded), so * two structurally different regexes can never collide onto one group. */ key: string; /** Human rendering, e.g. `"@"` or `/[-\w]+/`. */ render: string; /** Arm indices, ascending. */ members: readonly number[]; }; export type ChoiceInventoryEntry = { site: ChoiceSite; siteKey: string; arity: number; strategy: ChoiceStrategyTag; disjoint: boolean; gated: boolean; /** Every group of >= 2 arms sharing a concrete leading term, ordered by member * count descending then key. Empty when no two arms share one. */ groups: readonly PrefixGroup[]; /** Per-arm reasons, ascending by arm index. Only arms that produced no key. */ armDeclines: readonly { arm: number; reason: ArmDeclineReason; detail: string; }[]; factored: boolean; /** Present iff `factored` is false. */ declineReason?: SiteDeclineReason; /** Arms that sit in some group but whose site was NOT factored — the count of * alternatives currently re-scanning a prefix a sibling already scanned. */ unfactoredArms: number; }; export type ChoiceInventoryReport = { readonly schema: 'parseman.choice-inventory/1'; rules: number; /** Distinct `choice` combinator instances reachable from the rule map. */ choiceSites: number; factoredSites: number; /** Sites with >= 1 prefix group that were NOT factored. The backlog. */ backlogSites: number; backlogArms: number; /** * Rule-map entries that are unresolvable references — a `g.X` hole that only * `compose()` binds. Their subtrees were NOT walked, so this report is partial by * exactly this much. Ascending. Empty is the only value that means "complete". */ unresolvedRoots: readonly string[]; /** Ascending by `siteKey`. Complete — every reachable choice, including the ones * with nothing to report. */ entries: readonly ChoiceInventoryEntry[]; }; export type WastedWorkArm = { siteKey: string; site: ChoiceSite; arm: number; /** Short rendering of the arm's head, so the ranked list reads without opening * the grammar. */ label: string; /** INTERPRETED: every entry, because the interpreter's firstMatch loop gates nothing. */ attempts: number; failures: number; /** INTERPRETED: input bytes re-scanned by this arm's FAILED attempts, summed over the * corpus. For one attempt: (furthest position a terminal was tried) - (entry position). */ wastedBytes: number; /** True when codegen emits a first-char guard for this arm, i.e. the shipped parser * enters it less often than the interpreter does. */ firstCharGated: boolean; /** COMPILED MODEL: entries that survive codegen's first-char guard. This is the * number the shipped parser actually pays. Equals `attempts` when `firstCharGated` * is false. */ gatedAttempts: number; gatedFailures: number; /** COMPILED MODEL: the ranking column. Bytes re-scanned by failed attempts that * codegen's guard would NOT have skipped. */ gatedWastedBytes: number; }; export type WastedWorkSite = { siteKey: string; site: ChoiceSite; strategy: ChoiceStrategyTag; arity: number; /** False when the strategy cannot be instrumented; then `wastedBytes` is 0 because * nothing was measured, NOT because nothing was wasted. */ instrumented: boolean; attempts: number; failures: number; wastedBytes: number; gatedAttempts: number; gatedFailures: number; gatedWastedBytes: number; }; export type WastedWorkReport = { readonly schema: 'parseman.wasted-work/1'; corpusFiles: number; corpusBytes: number; parsedOk: number; parsedFailed: number; /** Sites the profiler installed instrumentation on. */ instrumentedSites: number; /** Reachable choice sites whose strategy cannot be instrumented (see the module * header, blind spot 1). Reported so a low total is not read as a clean grammar. */ uninstrumentableSites: number; /** Rule-map entries that are unresolvable references; their subtrees carry no * instrumentation, so the total below is a LOWER BOUND by exactly this much. */ unresolvedRoots: readonly string[]; /** INTERPRETED total. Read `totalGatedWastedBytes` for what the shipped parser pays. */ totalWastedBytes: number; /** COMPILED MODEL total — the headline number, and the one a gate should use. */ totalGatedWastedBytes: number; /** Descending by `gatedWastedBytes`, then `wastedBytes`, then `siteKey`, then `arm`. */ arms: readonly WastedWorkArm[]; /** * ORDERING INVERSIONS: arms that were attempted at least `inversionMinAttempts` * times and failed EVERY time, while a later arm at the same site matched. * * A second ranking, because bytes alone answer the wrong question for the clearest * class of defect. Measured on jess's CSS grammar: `StylesheetAtRule › dispatch[3]` * has arm 0 failing 19 of 19 attempts while arm 1 matches — an unambiguous ordering * bug — yet it is only the 14th largest site by bytes, because the prelude it * re-scans is short. Bytes rank what costs most; this ranks what is most obviously * WRONG. Both are in the report and neither is derived from the other. * * Computed from the GATED columns, so an arm codegen already skips is not reported * as an inversion in a parser that never enters it. * * Descending by `gatedAttempts` — NOT by bytes. An arm can fail 100% of its attempts * and re-scan zero bytes, because it fails on its own first terminal; jess's `Value` * arm 8 `CustomPropertyValue` does exactly that, 925 times, and is the one ungated arm * at that site. Ranked by bytes it is invisible; ranked by attempts it is a finding. */ inversions: readonly WastedWorkArm[]; /** Descending by `wastedBytes`, then ascending by `siteKey`. */ sites: readonly WastedWorkSite[]; }; /** A short, deterministic rendering of an arm's head, for the ranked list. */ export declare function armLabel(arm: Combinator): string; /** * Every `choice` reachable from `ruleMap`, with its shared-prefix groups and whether * the compiler factored the site. * * Complete by construction: the walk visits every reachable combinator instance and * emits an entry for each `choice`, whether or not it has anything to report. A site * missing from this report is a site the walk could not reach, never a site that was * judged uninteresting. */ export declare function analyzeChoiceInventory(ruleMap: ReadonlyArray]>): ChoiceInventoryReport; /** Exposed so the fidelity test can compare the model against emitted guards. */ export declare function modelledFirstCharGate(p: Combinator): FirstSet | null; export type WastedWorkCorpusEntry = { /** Stable identifier. Use a repo-relative path, never an absolute one — it appears * in the report, and an absolute path would make the report machine-dependent. */ id: string; text: string; }; export type ProfileWastedWorkOptions = { /** The combinator rule map, for site naming and instrumentation. */ rules: ReadonlyArray]>; /** The rule to start each parse at. A key of `rules`, or a combinator. */ entry: string | Combinator; corpus: ReadonlyArray; /** Passed through to `run()`. Must not contain anything machine-dependent. */ runOptions?: Record; /** * How to parse one corpus entry. Defaults to `run()` in interpreted mode. * * Overridable because a grammar can need a driver of its own — jess's Less dialect, * for instance, requires `state: { source: input }` because its reducers read it — * and because a caller who has already built a driver should not have to duplicate * it here. It must be a plain interpreted parse; anything compiled defeats the * instrumentation silently, since a compiled artifact never reads `def.parsers`. */ runner?: (entry: Combinator, input: string, options: Record) => { ok: boolean; }; /** Minimum attempts before an always-failing arm counts as an ordering inversion. * Default 4 — below that, "failed every time" is a sample size, not a finding. */ inversionMinAttempts?: number; }; /** * Parse `corpus` with `rules` in INTERPRETED mode, counting input bytes re-scanned * by failed choice alternatives. * * Fails closed on every way of measuring nothing: an empty rule map, an unknown entry * rule, an empty corpus, an empty corpus file, or a grammar in which no instrumentable * choice site exists. Each of those would otherwise produce a report of zero wasted * bytes, which reads as a clean grammar. */ export declare function profileWastedWork(opts: ProfileWastedWorkOptions): WastedWorkReport; //# sourceMappingURL=choice-cost.d.ts.map