sparkles:parsing — Design Proposal

Abstract

sparkles:parsing is a proposed toolkit for writing parsers of the small languages Sparkles reads: version strings and version constraints, command-line tokens, filter expressions, and configuration. A parser is an ordinary D value, built from a handful of combinators and a precedence loop for operator grammars. It reads its input in place and returns slices of it rather than copies. A parser that only validates its input allocates nothing, so a grammar can run in code that must neither allocate from the garbage collector nor throw. Each parser decides when it is built whether to stop at the first error or to recover, returning a partial result together with every error it found.

Introduction

Sparkles parses several small languages by hand: the version strings of each package ecosystem's version scheme, command-line arguments, and terminal control sequences. Most of that code runs in contexts that forbid garbage-collected allocation and exceptions. Each parser is written from scratch over the zero-copy readers in sparkles:base, small functions that read an integer or a token from the front of a string slice and advance past it. Every parser therefore solves sequencing, alternatives, repetition, and error reporting again. A reusable layer would let the next grammars, such as a version constraint like >=1.2 <2.0 || ^3, a filter expression, or a configuration file, be stated rather than hand-rolled.

Existing libraries do not fill that role. The parsing survey locates the design center for an allocation-conscious parser in zero-copy recursive descent built from combinators, as in Rust's nom and winnow, and flatparse shows that such an API can validate input without allocating. The D ecosystem offers a compile-time PEG generator, Pegged, that depends on the garbage collector; hand-written parsers for D source itself; and a fast serialization stack for JSON-like data. It has no maintained combinator library that is allocation-free and zero-copy, and no parser that recovers from errors.

The toolkit is a thin policy layer over the existing readers, which supply the mechanism. Parsing is scannerless recursive descent: there is no separate lexer, the input slice itself is the cursor, and a parser advances it only when it succeeds. Combinators join parsers in sequence, repetition, and PEG ordered choice, where the first alternative that matches wins, so no input ever has two parses. A Pratt binding-power loop handles operator precedence without tables. Results use the Expected error vocabulary the readers already return. That vocabulary separates a failure, a miss that an enclosing alternative may recover from by trying its next branch, from an error, which ends the parse because it occurs after an explicit commit point that rules out the other branches. Combinators inherit their safety and allocation guarantees from the parsers they combine, so a grammar is exactly as allocation-free as its leaf parsers. A recovering parser also needs storage for the errors it collects.

This proposal covers the parser shape, the combinators, the precedence engine, and the choice between failing fast and recovering. Its first client is a version-constraint grammar whose accepted and rejected inputs must match those of the existing version parsers. It leaves out vectorized parsing, because Sparkles reads no inputs large enough to need it. It also leaves out incremental re-parsing, which earns its cost only under an editor that re-parses on every keystroke, and a compile-time grammar language. A lossless syntax tree that can print its input back waits for a client such as a formatter. The toolkit is not a general parsing framework and does not replace Phobos's argument parser or the libraries above.

Section 1 summarizes the survey's conclusions and §2 states the design decisions. Section 3 lists the existing code the toolkit builds on, §4 gives each non-goal with its reason, and §5 maps every decision to the prior art it borrows from. The delivery order lives in PLAN.md. The evidence lives in the parsing survey, its comparison, and the D-ecosystem landscape.

1. Why

Sparkles already hand-parses several small languages — version schemes, CLI arguments, terminal VT sequences — each @nogc/@safe, each hand-rolled from scratch over the sparkles.base.text readers. The parsing survey was written to answer whether a reusable parsing layer would serve those cases better, and what shape it should take. Its two load-bearing conclusions:

1. The cross-ecosystem design center for an allocation-conscious parser is zero-copy, scannerless recursive descent (nom/winnow) with zero-allocation validators (flatparse's proof), a Pratt expression loop, and Expected!(T, E) results — not SIMD (yyjson shows careful scalar wins), not incremental (that earns its keep only under an editor re-parse contract), not a table generator.
2. The D landscape has a gap exactly there. D has a compile-time PEG generator (Pegged — but GC-bound), a hand-written-RD tradition (dmd/libdparse/sdc — but D-specific), and a world-class @nogc/SIMD serialization stack (mir-ion/asdf) — but no maintained, @nogc, zero-copy ordered-choice combinator and no recovering parser.

sparkles:parsing fills that gap: a small combinator layer over the existing base.text readers, in the idiom the repo already uses.

2. What — the design center

Each decision below cites the prior-art page it reifies and the in-tree code it builds on. None of it contradicts the comparison's Sparkles-fit sketch — it operationalises it.

• Zero-copy, scannerless recursive descent over const(char)[]. No separate lexer, no generated tables; the input slice is the cursor. This is what nom/winnow do and what parseSemVerShaped already does in-tree. Parsers are values of the form ParseResult!T function(ref scope const(char)[]) (advance-on-success), composing directly with the base.text.readers primitives (readInteger, skipSpaces, tryConsume, readUntil).
• Ordered-choice combinators (a PEG-shaped internal DSL). seq, choice/alt (first match wins — PEG ordered choice, unambiguous by construction), many/many1, opt, sepBy, map, plus syntactic predicates (peek/notFollowedBy). Combinators are ordinary D values (embedded-combinator interface); attributes infer so @nogc/@safe/pure/nothrow propagate from the caller's leaf parsers.
• Zero-allocation by construction. A parser returning void/a slice must run with no heap allocation — the property flatparse proves a combinator API can have and the one most relevant to Sparkles (validating a version string, a CLI token). A Buffer replaces appender where accumulation is unavoidable; no packrat memoization by default (the space cost is the wrong default; reserve it for a measured hot spot).
• A Pratt expression engine. A table-free, O(n) binding-power loop for any operator/constraint grammar Sparkles needs (version constraints >=1.2 <2.0 || ^3, filter expressions). Drops into the recursive-descent shell exactly as the survey's pratt-precedence page describes.
• Expected!(T, ParseError, NoGcHook) results, failure-vs-error split. Reuse the existing errors.d vocabulary verbatim. The flatparse/nom failure (control-flow, backtrackable) vs error (unrecoverable, cut) distinction maps onto Expected: an ordinary parse miss is a recoverable err; a committed-path failure short- circuits. parseOk/parseErr are the constructors.
• Error posture chosen per use, up front. Fail-fast by default (validating a version string); opt-in chumsky-style recovery (a partial value + an error list) for the user-facing cases (config, a REPL) — an architecture decision made at parser-construction time, never retrofitted (comparison §4).

3. What it builds on (reuse, don't reinvent)

• sparkles.base.text.readers — the zero-copy cursor primitives are the leaf parsers; combinators are the glue. readers.d is documented as "mechanism, not policy" — this toolkit is the policy layer.
• sparkles.base.text.errors — ParseError/ParseErrorCode/ParseExpected/ parseOk/parseErr/NoGcHook already exist and are the result vocabulary.
• sparkles.base.buffer — the @nogc output range.
• The expected idiom — Expected!(T, E) chaining (map/andThen/orElse) is how parsers compose without exceptions.
• parseSemVerShaped — the existing scannerless-RD exemplar; the version schemes are the first real client and the migration test.

4. Non-goals (and why)

• No SIMD by default. yyjson reaches GB/s with careful scalar ANSI C and no SIMD; simdjson-class vectorization is a measured optimization for large, hot, structured inputs (megabytes of JSON), which Sparkles does not parse. If such a need appears, the mir stack (mir-ion/asdf) already exists — depend on it, don't rebuild it.
• No incremental / query machinery. tree-sitter/rust-analyzer/Roslyn/rustc/Lezer earn their persistent-tree + dependency-graph overhead only under an editor contract (re-parse on every keystroke). Sparkles' inputs are parse-once. The one borrowable idea is a red-green lossless view — and only if a future use wants a re-serializable CST (a formatter); a plain AST is lighter otherwise. See the incremental theory page.
• No CTFE grammar DSL (à la Pegged). A string-mixin grammar generator is powerful but GC-shaped and compile-time-heavy; the survey's evidence is that production parsers are hand-written RD (top-down, and D's own dmd/libdparse/sdc). Reach for a grammar DSL only on a measured need for a large external grammar.
• Not a replacement for std.getopt/mir/Pegged. This is a small @nogc toolkit for Sparkles' own small languages, not a general parsing framework.

5. Prior-art map

Where each design decision comes from in the survey (the evidence, not re-derived here):

Decision	Prior art (survey page)	What to borrow
Zero-copy scannerless RD over slices	nom · winnow	slice cursor, no allocator on the recognizer path
Ordered-choice combinators (unambiguous)	PEG/packrat · pest	ordered choice /, predicates; skip packrat default
Zero-allocation validators	flatparse	failure/error split; ()-returning parsers allocate nothing
Pratt expression engine	pratt-precedence	binding-power loop for constraints
Expected results, fail-fast vs recover	flatparse · chumsky	error posture as an up-front architecture choice
Table-free hand-written lexer (if needed)	Zig tokenizer	character-class state machine, zero-alloc
Stay batch (reject incremental)	incremental theory · comparison	the editor-contract boundary
Don't reach for SIMD	yyjson · simdjson	scalar-first; vectorize only measured hot paths

The milestones that build this — bottom-up, each reusing the base.text substrate — are in PLAN.md.