Skip to content

How Parséman works inside ​

A map of the code for someone who has never read it. It says what each stage does, where it lives and why it is shaped that way, and points at the file that holds the detail. Owner rulings that constrain all of this (no runtime code generation outside compile(), the 5× size budget, no speed regressions) are in the runtime and size contract; where this page and that one disagree, that one is right.

The pipeline ​

combinators ──► rule map ──► encode ──► TableProgram ──► wire form ──► resolve ──► assemble ──► run()
 (src/combinators)   (rules)    (table/encode.ts)  (table/program.ts)   (CompactProgram)    (resolveTable)  (assemble.ts / emit-assembly.ts)

There are three ways a grammar runs. The two table modes follow this whole pipeline; the interpreter stops at the first box.

modewhat runs the parsebuilt whenentry
interpretereach combinator's own .parse()never: the combinator graph is the parserparse() (combinators/grammar.ts), run() (functional/run.ts), runtime compose()
runtime compile()the table, linked into generated functions (new Function), or into closures under a CSPat the first parse of each option setcompile() (table/compile.ts)
macro buildthe table, linked into closures, plus generated code for the hottest sites, chosen within a byte budgetin the bundlerparseman/plugin (plugin/index.ts)

A macro-built module imports only parseman/table (src/table/index.ts): tableRules, the shared driver. A table grammar contributes data (the program) and its author callbacks; all recognition logic is in the runtime, once.

1. Combinators ​

src/combinators/*. Each constructor (literal, regex, sequence, choice, dispatch, many, sepBy, node, field, scanTo, …) returns a Combinator (src/types.ts):

  • _def: what it is, a tagged ParserDef. Every later stage reads this, never the closure.
  • _meta: what it knows about itself: first set, nullability, trivia, value usage.
  • parse(input, pos, ctx): the interpreter.

First sets (combinators/first-set.ts, regex/first-set.ts for regex bodies) decide whether a choice can dispatch on one character; first-char gating is the author-facing rule. compiler/value-usage.ts marks results nobody reads, so the encoder can drop their tuples (SEQV, REPV). compiler/build-arity.ts and compiler/fields.ts describe what a node() builder receives.

rules(opts, g => ({ … })) (combinators/parser.ts) makes a rule map: named rules, referenced lazily as g.Name, with grammar-wide trivia and scanSkip.

2. Linking and composition ​

compose([pieceA, pieceB]) merges rule maps; a later piece's rule wins everywhere, including inside the earlier piece (open recursion).

  • At run time it only links (compiler/linker.ts, linkRules in combinators/parser.ts): no table, no code, no mutation of a shared rule. The result runs on the interpreter.
  • At build time the macro re-lowers each piece from its carried IR (below) and encodes the merged map once.

compiler/borrowed-rules.ts rejects a rule map that reaches a rule it does not own.

3. Encoding: combinators to a TableProgram ​

table/encode.ts (encodeTable, encodeTableProgram) walks the rule map once and writes a flat array of integers, code, plus side pools. Settings (TableSettings) choose the contents of the table, not a runtime branch:

  • trackLines selects the *_TRACK opcodes;
  • hostMode ('ast' or 'cst') selects how nodes are built;
  • coverage adds COV counter rows.

So two option sets are two tables, and the driver never asks which one it is running.

What the encoder decides while writing rows:

  • Dispatch. A choice whose arms have disjoint first sets gets a dispatch table (disp): one character picks the arm.
  • Shared ends (table/factor-choice.ts). Arms that differ in one term become one sequence around a choice of that term.
  • Gates. These are the rows that let a failing attempt fail on one character instead of opening frames. Where each one is computed is listed under Gates.
  • Fail-clean sites (table/fail-clean.ts). Rows whose failure writes nothing, so their callers skip the rollback mark.
  • Held gaps (table/hold-gap.ts). A lookahead after trivia keeps the scanned gap for the next term instead of rescanning it.
  • Lexical bodies (table/lex-body.ts, table/lex-program.ts, planned by compiler/token-alphabet.ts and token-capability.ts). A token-shaped subtree with no children becomes one recognizer row (LEX_BODY, LEX_PROGRAM) instead of a tree of rows.

table/compile.ts (compile()) and table/compile-rule-map.ts (compileRuleMap(), the macro's entry) wrap the encoder with source capture, refusals and emission.

Gates ​

rowasksbeforecomputed in
GATE cc cis the next character in class cc?entering cencode.ts (lookaheadGate)
CHOICE dispatch tablewhich arm can start with this character?trying arms in orderencode.ts
REP item class / separator sentinelcan another item (or separator) start here?entering the itemencode.ts (sepBy, many cases)
ARMGATE f c edoes the author's state predicate hold?entering one armencode.ts
GUARD f edoes gate(predicate) hold? (zero-width)the next termencode.ts
RGATEcan the character after the token dispatch() already read continue this arm?entering a routed armencode.ts

4. Rows and the wire form ​

The instruction format (every opcode's operands) is documented on each constant in table/ops.ts; Opcodes below lists them. table/child-slots.ts is the single statement of which operands are child offsets; table/inspect.ts (reachableOps, opHistogram) walks only reachable rows, because operands collide with opcode numbers.

TableProgram (table/program.ts) holds:

fieldwire keywhat
codecthe instruction stream
kkconstant pool: strings, sticky RegExps, names
ccxcharacter classes, referenced by gates
fxeexpected sets for error messages
dispdchoice dispatch tables
dsppdispatch() key tables
rulesrrule name → entry offset
fnsfauthor callbacks: builders, transforms, predicates
linesl1 when built for trackLines
lex, lexProgramslx, lplexical-body and lexical-program specs
labels, classifiedlb, rctrivia labels, and whether the trivia is classified
triviaSpecstvtrivia scanners, rebuilt at load as data
scansscscanTo/balanced/lines specs (OP_SCAN)
scanSkip, scanSkipOfss, soper-rule ambient skip sets
hostModehthe host mode it was built for
recrvalways 1: recovery operands are laid down in every table
covcvcoverage counter definitions
asmabuild-time compiled assemblies (PrecompiledAssembly), keyed by cfgKey(RunCfg)

table/emit.ts (emitTableModule, emitTableExpression) prints a program under the short keys, expandCompact reads them back, and resolveTable turns the pools into runtime objects (ResolvedTable). foldPrograms / tableVariants (program.ts, table/fold.ts) carry several option-set variants as one base table plus row deltas.

5. The engines ​

All engines implement the same row semantics and share the protocol in table/cell.ts: one process-wide FAIL symbol and one per-assembly end-position cell. table/stamp.ts is the envelope around them (entry metadata, host-mode stamps, scanSkip, failure → ParseResult).

enginefileships?role
closure assemblertable/assemble.tsyes: tableRuleslinks each reachable row once into a closure with its operands captured as constants and its children as direct references. No opcode is read at parse time.
emitted assemblytable/emit-assembly.ts (+ scan-shapes.ts, plugin/entry-supercompiler.ts)yes, as textthe same sites printed as JavaScript: whole-grammar under runtime compile(), selected hot sites in a macro build
reference drivertable/exec.ts (execRules)noa switch over rows. Kept as an independent oracle; nothing in src/ imports it
interpretersrc/combinators/*yesthe combinators themselves

Why closures and not the switch: the switch was one basic block with ~30 merge edges that TurboFan deoptimized repeatedly. Each closure has one shape at its call sites, so V8 can inline them (assemble.ts header).

assemble() is one large function on purpose: every piece captures per-assembly constants, so they cannot be lifted to module scope without changing what V8 sees.

Option sets. RunCfg (assemble.ts) holds the per-parse options: hostCst, trackLines, tolerant, coverage, probe and hostReadsChildren. AssemblyCache.forCtx keys assemblies by cfgKey(RunCfg) and builds each set's assembly on first use, reaching only the rows that set needs. table/site-labels.ts labels sites so per-term checks (trivia, CST capture) are decided at assembly, not per parse.

Emitted vs closure, per site. In a hybrid assembly, emitted sites call closure sites and back, through the shared FAIL and end cell. An emitter that cannot lower a construct throws Unemittable. The closure engine then runs that assembly, and Assembly.emitRefusal records why. Under a strict CSP, compile() catches EvalError and uses closures.

Shared helpers and the hot path. Pure helpers that touch no assembly state are shared (table/run-support.ts, table/trivia-gap.ts, table/scalar-terminal.ts). Emitted code shares a helper only when it takes no piece as an argument (emit-assembly.ts header). Routing the mark/undo paths through shared helpers was measured 13–25% slower and reverted.

Tree objects are built by constructors. Leaves, spans, default and CST-host nodes, field captures and CST capture buffers are new calls on the constructors in src/cst/plain.js (plain.d.ts), never object literals. V8 decides per literal allocation site whether to allocate straight into old space, and that choice flips between identical processes whenever the bundle layout changes; a new call has no such site. The constructors exist once per process: the build emits one shared dist/cst/plain.js that every tree-building entry imports, so one shape has one hidden class. The emitted engine receives them as factory parameters (_SP, _LF, _ND, _FC, _BUF in EMITTED_PARAMS). perf:pretenure (below) guards this.

The reference driver keeps its own copies of protocol logic (line tracking, rollback, recovery sentinels) on purpose: a bug in a shared copy would be invisible to the identity sweep that compares it with the shipped engines.

6. Selection: which sites a macro build emits ​

Generated code is fast, but its bytes load in every process, so a macro build emits only a budget's worth.

  • Budget (plugin/index.ts, DEFAULT_ASSEMBLY_BUDGET = 0.5): assembly bytes per module may not exceed 0.5 × the module's code, not counting comments or whitespace (assemblyBudget option). Only the AST, no-line-tracking table carries an assembly; the other variants run on closures. A module with two AST grammars spends the budget in order, so a larger budget can buy the first a big site and leave the second fewer; Jess has one AST grammar per module.
  • Ranking (table/select-hot.ts). Every rule entry starts at weight 1; a repeat multiplies its body by LOOP (8); a choice or dispatch splits its weight across its arms. Weights propagate ROUNDS (60) times, with recursive cycles capped at CAP. Sites are then taken greedily by weight per emitted byte. With assemblyProfile (a corpus), measured site visits (countSiteVisits in assemble.ts) replace the estimate.
  • Fitting (compile-rule-map.ts, selectAssembly). A selection is always a prefix of the ranking: the sites are taken in rank order and stop at the first that does not fit, and the emitted source is then measured for real, allowing 5% for the supercompiler, dropping the last site until it fits. So a larger budget keeps every site a smaller one selected (test/unit/table-selective-assembly.test.ts), and a comment cannot move a site in or out (test/bench/assembly-selection-stability.test.ts).

7. Trivia, CST capture, lines ​

  • Trivia. trivia() and classifiedTrivia() (combinators/map.ts) are scanned by combinators/trivia-skip.ts, which compiles regex arms into character-loop scanners. cst/trivia-charscan.ts is the labelled variant.
  • CST capture. Capture writes into sinks (cst/capture-buffer.ts) that a failed attempt rolls back to a mark; cst/host-mode.ts is the artifact/host contract.
  • Lines. With trackLines, the *_TRACK rows record line starts (table/line-scan.ts, combinators/lines.ts). Without it, no row pays for lines.

See the trivia guide.

8. Recovery and completions ​

Recovery operands (follow-set classes, item expected sets) are in every table (rec: 1). They are used only when a parse runs tolerant, which selects a different assembly, so a strict parse never reaches a recovery piece. The resync logic is src/recovery/scan.ts, shared by every engine. Completions run a probe assembly (combinators/probe.ts).

9. The macro plugin ​

src/plugin/index.ts (unplugin: Vite, Rollup, esbuild, …), for import … from 'parseman' with { type: 'macro' }:

  1. Evaluate. It finds declarations whose right-hand side is a combinator expression and evaluates them at build time (plugin/evaluator.ts, reducer-resolver.ts, free-identifiers.ts), capturing each callback's source.
  2. Compile. compileRuleMap() encodes the table, and selectAssembly picks the emitted sites (section 6).
  3. Splice. It replaces the declaration with the printed table and prepends import { tableRules } from 'parseman/table'.
  4. Carry IR. A composable piece also carries its combinator IR (compiler/ir-serialize.ts, re-evaluated by plugin/ir-eval.ts), so a downstream build can re-lower it. Under a Rollup-family bundler that IR goes into a <chunk>.parseman.json sidecar instead of the artifact; nothing at run time reads it.

Artifacts are stamped with the Parséman version (src/version.ts); nothing reads the stamp back yet. A printed assembly factory does check the runtime that calls it: it throws, naming the version that printed it, when the runtime passes any other number of helpers than it was printed with (FACTORY_ARITY_GUARD in table/emit.ts). The runtime checks the other way before calling one: each printed assembly record carries arity, the helper count its factory was printed against, and the runtime refuses a record whose arity is missing (printed before 0.60.0) or is not the number of helpers it passes (assertFactoryArity in table/assemble.ts). It reads the printed number, not factory.length, which a minifier lowers.

10. Gates that keep this honest ​

gatecommandcatches
identity sweeptest/unit/table-identity.test.ts (bench/table-lowering-identity.ts)an engine whose output differs from the interpreter's
invariantspnpm check:invariants (doc)source rules no type sees: unreachable modules, unread options, duplicated bodies, renamed engine exports, …
differentialspnpm check:differentials (doc)a harness that cannot fail: each one must catch a defect planted in src/
coveragepnpm test:coverage && pnpm coverage:guarduntested new code
sizepnpm size:guard, pnpm size:guard:jessany artifact growth; Jess grammars over 5× their source
duplicate functionspnpm dupfn:guard (doc)a function printed twice in the emitted or printed output
call countpnpm callcount:guard (doc)more function calls or branch tests per parse than the previous release
perfsee belowslower parsing

How performance is measured ​

Performance gates is the method of record. In short:

  • perf:guard (pre-commit): two tiny CSS microbenchmarks, in µs.
  • perf:xproc:gate (CI, the verdict): every case of bench/grammar-density/ (speculative-rollback density and expected-set width) and of bench/workloads/ (Less, CSS, GraphQL, JSON), timed in fresh processes, one parser per process, against the previous release. --peak (CI, alongside it) runs only the workloads, against the fastest release on record (peak in bench/workloads/config.json). Both are configured in bench/xproc-gate.json.
  • perf:guard:grammars, perf:workloads (local only): the same cases A/B in one process. They say where a cost is; they do not give the verdict.
  • bench:macro-optimize (CI, advisory): Jess's CSS and Less grammars, macro-built in a pinned Jess checkout. It is the only CI speed check on a Jess grammar, and it covers neither SCSS nor .jess. (size-gate runs size:guard:jess over all four.)
  • perf:pretenure (local, about 6 minutes; run it on Node 24 and Node 26): pads dist/index.js with never-called code and counts each fresh process's mark-compacts. It fails if a tree object is built by an object literal again, which V8 may pretenure per process (bench/pretenure-check.ts; --plant=<site> shows it fail).
  • Jess's own harness (marginal instructions per parse with and without the JIT, on all four grammars) is described in the Jess repository's docs/perf/BENCHMARKS.md.

Which features each bench exercises. Parséman's own workloads run through runtime compile(), which emits the whole grammar as generated code. Jess's grammars are macro builds, which emit only the selected sites and run the rest on closures. So a change to the closure engine, or to selection, can move Jess and not move Parséman's benches.

The rows a workload executes also decide what it can see. These are site visits per parse, measured with countSiteVisits over encodeTable of each workload grammar, at 4a5d0341:

workloadinputrows visitedRGATEARMGATEDISPATCHLEX_BODY/LEX_PROGRAMSCANGATENOT
less/stylesheet52 KB199,5570000015,61526,061
less/mixins59 KB212,2840000016,30828,092
css/stylesheet64 KB89,3290000 / 2,2747009,8200
graphql/document49 KB40,378000003,3600
json/document59 KB46,3930000000

None of them reaches the routed-arm gate, per-arm state gates or dispatch(). Work on those rows (most of the 0.58 Less/SCSS work) is measured only on Jess's grammars, and for SCSS and .jess only by Jess's harness. bench/workloads/less.ts is a hand-written Less grammar, not Jess's.

Glossary ​

  • row / site: one instruction in code, identified by its offset (ip).
  • piece: the closure (or emitted function) a site is linked into.
  • assembly: all pieces for one table and one RunCfg.
  • variant: one option set's table (AST/CST × lines/no lines). Jess builds four per grammar.
  • fold: several variants as one base table plus deltas.
  • host mode: who builds nodes, the grammar ('ast') or a CST host ('cst').
  • carried IR: the combinator expression a composable artifact carries for downstream builds.
  • G4, G5, G14, G19, U4 in comments: rows of Jess's design ledger (jess/docs/architecture/core/DESIGN-DECISIONS.md) that drove this design. G5 is "link the table at run start" (the closure assembler), G4 the variant fold, U4 the emitted assembly. G14 is the predictive token-cursor direction and G19 the ruling that it always has a builder. The dormant compiler/token-scanner.ts and the test-only half of compiler/token-alphabet.ts are that groundwork, kept on purpose.

Opcodes ​

Operands follow the opcode in code. Full layouts and the reasons behind each are on the constants in src/table/ops.ts. test/unit/internals-doc.test.ts fails if an opcode is missing here.

#opcodeoperandsmeaning
1LITk fxmatch the constant string k; fx the expected set on failure
2RXk fxmatch the sticky regex k
3SEQn c1…cn f1…fnchildren in order; value is their tuple. f are recovery follow classes
4SEQVas SEQSEQ whose value is unused: no tuple
5CHOICEd n fx c1…cn e1…enordered choice; d a dispatch table or −1; fx/e expected sets
6REPc min max sep flags fx cls [gate]repeat or separated list, 8 or 9 words; cls the item/separator class that gates continuation. flags &8: a 9th word, the separator gate class; &16: the item's derived set is empty
7REPVas REPREP whose value is unused
8OPTcchild, or null
9XFORMf ctransform(): call fns[f](value, span)
10NODEb c flags proj type tagsnode(): open a frame, run c, build
11RULErcall rule r
12GATEcc c fxfirst-character gate, then c
13NOTc fxnegative lookahead
14PEEKc fxpositive lookahead
15LEAFf cleaf(): reduce, record one spanned leaf
16EMPTYmatch the empty string
17LIT_TRACKas LITline-tracking twin
18RX_TRACKas RXline-tracking twin
19NODE_TRACKas NODEline-tracking twin
20SCOPEk c policyparser({ trivia }) scope with a policy
21EXPECTc eexpect(): never fails; yields a ParseError value
22SEQXf n c1…cn f1…fntransform() over a sequence(), fused; f < 0 is a direct projection
23SCANsscanTo / balanced / lines / columns, spec s
24FIELDk cfield(name, c)
25DISPATCHsel d other otherRouted n a1…andispatch(): read once, route by value
26ROUTEDfallbackrouted(): the token dispatch() read
27LIT_CIk fxcase-insensitive literal
28LIT_CI_TRACKk fxline-tracking twin
29TOKENctoken(): no trivia inside, one leaf for the match
30SCOPE_CAPk c policySCOPE that also captures trivia
31WITHCTXk cwithCtx(): save/replace/restore ctx.state
32GUARDf egate(predicate), zero-width
33ADJneg kinds fxadjacent() / notAdjacent() boundary test
34GREEDYsup n w1 a1…identifier-vs-keyword classify choice
35REJECTc n t1 o1…choice arm with its autoNot checks
36ARMGATEf c echoice arm behind a state predicate
37LIVEfrun a hand-written combinator's own .parse
38ATTEMPTc kattempt(); k = { contain: true }
39LABELc fxlabel(): replaces the child's expected set
40COVc id ongrammar-coverage counter (coverage tables only)
41SCOPE_PLAINk cambient trivia scope with no policy
42LEX_BODYbody fx suffixFx lineFlagsone-row lexical recognizer
43LEX_PROGRAMpcomposite lexical program
44SOURCE_LEAFf csourceLeaf(): reduce, keep source text
45RGATEcls child fxrouted arm gated on the character after the routed token
46GAPGATEc p cls otheroptional repeat item opening with a gap; transparent, read by its repeat
47RGATE2cls child fx first secondRGATE that also tests the second character after the routed token
48STRICTstrict tolerantone construct encoded for a strict parse and for recovery; an assembly resolves it to one child
49CONTcorner wrapper taila collapse node whose corner always publishes one node and whose tail can take nothing: run the corner in the parent's collector, then open wrapper only if tail can start at the next token; recovery, a probe and the reference driver run wrapper as written
50SEEDcornerthe corner CONT holds, published as the first child of the frame it opened late; where no decision was made, corner itself

Which engine handles which: assemble.ts and exec.ts handle all of them. emit-assembly.ts lowers all but GUARD, GREEDY, REJECT, LIVE and COV, and refuses those (the closure engine runs that assembly). It follows RULE as an alias of its child and inlines ADJ into its sequence.

Released under the MIT License. Commercial support available on request.