typed-peg-0.4.0.0: CHANGELOG.md
# Changelog
## Unreleased
### Breaking. A non-terminal is a key, and `pegGrammar` declares the key type
`PExp` and `Grammar` are indexed by the type of the grammar's non-terminal
keys, `nt :: Type -> Type`, instead of by a type-level environment:
```haskell
data PExp (s :: Type) (nt :: Type -> Type) (a :: Type)
data Grammar (s :: Type) (nt :: Type -> Type) (a :: Type)
NT :: nt a -> PExp s nt a
```
`pegGrammar` in declaration position now declares a GADT with one constructor
per rule, its `Tabulate` instance, and one binding per rule whose signature is
the rule's annotation:
```haskell
data ArithEnv s a where
ArithEnv_expr :: ArithEnv s Exp
ArithEnv_term :: ArithEnv s Exp
instance Tabulate (ArithEnv s)
arith'expr :: Stream s => PExp s (ArithEnv s) Exp
arith :: Stream s => Grammar s (ArithEnv s) Exp -- = Keyed rules start
```
A grammar written that way needs no change beyond `{-# LANGUAGE GADTs #-}`,
which the splice asks for by name when it is missing: `%env` still names the
generated type and `Grammar s (ArithEnv s) Exp` is still its signature.
A type-level environment is still supported, through the key `InEnv env`, a
membership proof into it. `nt @"expr"`, `ntw`, `pegRules`, `RCons` and
`pegGrammar` in expression position all go through it, and so does a
hand-written environment, whose signatures gain an `InEnv`:
```haskell
calc :: Stream s => Grammar s (InEnv (CalcEnv s)) Expr -- was Grammar s (CalcEnv s) Expr
```
A combinator over expressions, `PExp s env a -> PExp s env a`, works unchanged
over either kind of key. `PEG.Syntax.NTW` is gone (`ntw` remains, as
`NT . InEnv`), and `nt` no longer asks for `KnownSymbol`.
**Why.** Removing the FIRST sets from the environment left a cost that grew
faster than the grammar, and it was the proof itself. A reference into a list
carries `There (There ... Here)`, and GHC's evidence for it is proportional to
the rule's depth times the size of what is left of the list. Handing GHC the
proof instead of having it search saved a constant; the proof still had to be
checked. Through `pegGrammar` a 128-rule grammar needed 2.2 GB of heap, and a
256-rule one did not fit in 8 GB. A constructor's type does not depend on the
rest of the grammar (`ghc -fno-code`, `bench-compile/`):
| rules | before | key type |
|---|---|---|
| 64 | 1.16 s, 385 MiB | 0.44 s, 49 MiB |
| 128 | 5.70 s, 2 180 MiB | 0.50 s, 51 MiB |
| 256 | exhausts 8 GB | 0.57 s, 80 MiB |
| 512 | — | 0.70 s, 98 MiB |
| 1024 | — | 1.17 s, 159 MiB |
The per-rule bindings also cut what the simplifier does with a grammar:
MiniPython at `-O1` went from 2.4 s and 177 MiB to 1.5 s and 111 MiB.
Parsing is unaffected: the allocation benchmark agrees with the previous
commit on every row, to within 0.1 byte per input byte on three of the
smallest inputs, and MiniPython over its key type allocates what it does over
an environment.
### Added
- `PEG.Key`: `Tabulate`, `Table` and `InEnv`.
- `Keyed`, the `Grammar` constructor for a key type.
- `%param name :: Type` in `pegGrammar`: the grammar and every rule take an
argument in scope in every semantic action, which is what a grammar that
used to be written in expression position to capture a variable needs.
Repeatable.
- `examples/MiniPython.hs`, the 27-rule grammar of the MiniPython language of
the compilers course at UFOP, and a `minipython` mode in `bench-compile/`.
- `bench-compile/run.sh` reports GHC's peak heap, and has `qq-grammar-expr`
(a grammar over a list, through `pegGrammar`) and `lookup-key` (the keys
with no library) modes.
### Shared prefixes of alternatives are parsed once
The quasi-quoters translate consecutive alternatives that begin with the same
items as the common prefix followed by a choice of the remainders:
`A B / A C` becomes `A (B / C)`, recursively, with each remainder's action
still seeing the prefix under its own labels. In a PEG the two accept the
same inputs with the same results, since `A` would parse exactly the same
thing the second time.
Without it, a precedence level written `e:or_expr ws "if" ... / e:or_expr`
parses its operand twice, and the cost is exponential in how deeply the
*input* nests. On MiniPython, `print(str(mdc(f(g(x)))))` took 348 ms, eight
times as long per level; a 13.6 KB file of the course's examples took 965 ms.
Both now take under 15 ms. The copy of the library the course's reference
compiler used to vendor escaped this only by accident: its grammar was static
combinator code, and GHC's CSE shared the repeated call. Compiled with
`-O0` it took 6.9 s on the same expression.
Only consecutive alternatives are grouped, and an alternative that is not a
sequence is left alone. `PEG.QQ.Syntax`'s `PExpr`, `Item` and `RelS` now
derive `Eq`.
### Fixed
- The library builds with GHC 9.6 again, as `tested-with` and the
`template-haskell >= 2.19` bound said it did: `PEG.Parse` no longer needs
`TypeAbstractions`, the binders `pegGrammar` generates go through
`PEG.QQ.Compat` rather than naming `BndrReq`, which template-haskell 2.21
introduced, and the analysis test-suite no longer relies on `foldl'` being
in the Prelude.
### The analysis is linear
`PEG.Analysis` ran on every splice and computed every rule's FIRST set by
Kleene iteration over whole sets, rebuilding and comparing all of them on
each pass. A precedence ladder of `N` rules has FIRST sets of `N^2/2` names,
and on 1024 rules that was 49 of the 58 seconds a keyed grammar took to
compile. The diagnostics need none of it: nullability is a fixpoint over
booleans, left recursion is a cyclic strongly connected component of the
direct-head graph, and the cycle reported is a shortest one, found breadth
first. The FIRST sets in the environment `analyse` returns are that graph's
closure, built only when the environment is inspected — 0.5 s at 1024 rules
when they are. `typed-peg` now depends on `containers`.
### Breaking. The environment no longer carries FIRST sets
An entry of a grammar's environment was a rule's nullability, its FIRST set
and its result type. It is now the result type:
```haskell
type CalcEnv =
'[ '("expr" , 'EnvEntry Expr) -- was 'EnvEntry ('MkTy 'False '["atom", "term", "unary"]) Expr
, '("term" , 'EnvEntry Expr)
, '("atom" , 'EnvEntry Expr)
]
```
`PExp` loses its `ty` index and is now `PExp s env a`; `Grammar` is
`Grammar s env a`. `PEG.Type.Ty`, `Nullable`, `First`, `TyOf`,
`PEG.Syntax.SeqTy`, `ChoiceTy`, `NTTy`, `NTGo`, `PEG.Grammar.Acyclic` and the
sorted-set families in `PEG.TyLevel` — `Union`, `Elem`, `ConsIfAbsent`, `If`,
`And`, `Or`, `SymEq` — are gone. A grammar written with `pegGrammar` needs no
change; one that writes its environment by hand needs the `'MkTy` component
deleted from each entry and the `ty` argument deleted from its signatures.
**Why.** The FIRST sets in the environment were the entire cost of compiling
a large grammar, and the measurement that says so is that *not computing them
was worth nothing*. A mode that kept the large environment but handed GHC
every rule's index as a literal, so that `SeqTy`, `ChoiceTy` and `Union` were
never reduced, ran no faster than one that reduced them all. What cost was
the environment being `O(N^2)` type nodes and each of the `2N` reference
constraints being solved against it: in the micro-benchmark, giving each entry
a payload that no type family ever reads takes `N = 64` from 0.77 s to 11.8 s
and exhausts 8 GB at `N = 96`.
**What it bought**, on a grammar of `N` mutually referring rules
(`bench-compile/`, `ghc -fno-code`):
| N | before | after | |
|---|---|---|---|
| 64, environment by hand | 15.15 s | 1.99 s | 7.6x |
| 64, through `pegGrammar` | 7.23 s | 1.19 s | 6.1x |
| 128, through `pegGrammar` | — | 5.28 s | |
The curve changed and not only the constant: doubling the grammar from 32 to
64 rules used to cost about 8x and now costs 3.3x, so what was cubic in the
number of rules is closer to quadratic. A 128-rule grammar through
`pegGrammar` now costs less than a 64-rule one did.
Two shapes that used to differ by 4.9x — a rule beginning with a non-terminal
against one beginning with a terminal — are now indistinguishable, which is
the check that the cost is gone rather than moved.
**Leaving the environment to inference now works.** `Grammar s _ a` with a
wildcard environment used to be unusable: GHC inferred entries full of
unreduced type-family applications and was past 24 GB of heap at `N = 16`.
There are none left to leave unreduced, and it is now within noise of writing
the environment out — 2.25 s at `N = 64`. A hand-written rule set need not
declare an environment at all.
**What this gives up.** Left recursion was a type error, checked on every
compilation by `Acyclic`. It is now checked once, by `PEG.Analysis`, when
`pegRules` or `pegGrammar` splices the grammar — which is where it was already
reported, with the rule and its cycle named, and which is the message you
actually saw. What is no longer checked at all:
- A `Rules` chain assembled by hand from `RCons`, with no quasi-quoter
involved. A rule that begins with itself compiles and loops.
- Left recursion that closes *across* two `pegRules` blocks spliced together.
A block is analysed open-world, since `RCons` lets two be combined, and
`Acyclic` used to be the backstop. Writing the grammar as a single
`pegGrammar` closes the gap: it is closed-world.
`Star` no longer demands a non-nullable operand, for the same reason; a
nullable repetition is reported by `PEG.Analysis`, and by nothing at all if
the `Star` is built by hand.
**What this makes simpler.** A combinator over expressions is now an ordinary
polymorphic function. What had to be written
```haskell
lexeme :: PExp s env ty a -> PExp s env (SeqTy ty ('MkTy 'True '[])) a
```
is `PExp s env a -> PExp s env a`, and composes without the caller having to
get a nesting of type families right. `examples/Patterns.hs` is where that
shows.
**And what now keeps the analysis honest.** While the FIRST sets were also in
the types, `PEG.Analysis` could not be quietly wrong: `Grammar` demands
`Rules s env env`, so GHC recomputed everything and rejected an environment
that did not match. It no longer does. The `typed-peg-analysis` test-suite
therefore checks the analysis against a separate statement of what its results
mean — nullability as a least fixpoint, and a FIRST set as the transitive
closure of the one-step head relation — over every grammar in `examples/` and
over 400 generated ones, and asserts that the generated corpus keeps
containing both left-recursive and left-recursion-free grammars so the
agreement cannot go vacuous.
### Grammar checking at splice time
The environment a grammar declares is no longer something only GHC can
compute. `PEG.Analysis` runs the same nullability and FIRST-set fixpoint in
ordinary Haskell, over the quasi-quoter's syntax tree.
*(Superseded above: the environment no longer states either, and
`PEG.Analysis` is the only thing that computes them.)*
Measurement first, because it redirected the work. On a synthetic grammar of
`N` rules with `2N` non-terminal occurrences (`bench-compile/`, `ghc -fno-code
-freduction-depth=0`):
| N | environment written by hand | same, FIRST sets emptied | same, indices handed to GHC as literals |
|---|---|---|---|
| 16 | 0.59 s | 0.55 s | 0.52 s |
| 32 | 1.80 s | 1.09 s | 1.43 s |
| 48 | 6.39 s | 1.97 s | 5.19 s |
| 64 | 18.25 s | 3.75 s | 14.99 s |
Left to inference, the same grammar runs out of memory rather than time: at
`N = 16` GHC was past 24 GB of heap and still climbing. It does derive
exactly the environment the examples write by hand — the entries it derives
are just full of unreduced type-family applications.
And, isolating the environment search alone — `N` entries, `2N` references:
| N | `Lookup` + `KnownMember` | witness, equality kept | witness, no equality |
|---|---|---|---|
| 32 | 0.55 s | 0.20 s | 0.18 s |
| 64 | 3.37 s | 0.86 s | 0.56 s |
Three quarters of it is the instance chain, and that quarter-to-three-quarters
split is the useful part: supplying the proof while keeping the `Lookup`
equality — so the reference still cannot name the wrong rule — collects most
of the win. On the real library, on the grammar above, it is worth **2.6x**
at `N = 64`: 16.60 s becomes 6.27 s.
So the cost that remains after the 0.2 work is mostly **not** the FIRST-set
arithmetic: computing it in advance and handing GHC the answer is worth 1.2x.
It is the environment — searched once per occurrence of every non-terminal,
over entries whose size is dominated by the FIRST sets they carry. Those are
two independent levers that compose: 2.6x for how a reference is resolved
(taken below) and 4.9x for what the entries carry (taken above — and the
1.2x turned out to be the whole of the arithmetic, so what the entries carry
cost nothing to compute and everything to have). `PEG.Analysis` computes the
whole environment for the 64-rule grammar in 6 ms.
### Added
- `PEG.Analysis`: nullability, FIRST sets and well-formedness computed at
splice time. It was then the value-level twin of `PEG.TyLevel`, which was
the specification; it is now the only implementation, and what checks it is
the `typed-peg-analysis` test-suite.
- `pegRules` now reports left recursion, a nullable repetition and a duplicate
rule **from the splice**, naming the rule and, for left recursion, the chain
of head references that closes the cycle. A block is analysed open-world,
since `RCons` lets two blocks be combined, so an unknown name is treated as
opaque rather than reported; `Acyclic` was then the backstop, and is now
gone, so a cycle closing across two blocks is caught by nothing. Write the
grammar as one `pegGrammar` to close that gap.
- `PEG.QQ.Syntax`: the DSL's syntax tree and parser, split out of `PEG.QQ` so
that the analysis and the translation can both consume it.
- **`pegGrammar`**, a quasi-quoter for a whole grammar. In expression
position it produces the `Grammar` value; in declaration position it also
declares the environment and the signature, so that a grammar of `n` rules
is `n` lines and nothing else:
```haskell
[pegGrammar|
%name arith
%start expr
expr :: Exp <- t:term ts:(o:[+-] u:term)* { foldl addOp t ts }
...
|]
```
Because it owns the whole grammar it knows each rule's position, so it emits
`ntw` and the membership proof rather than `nt` and a search — **2.1x** on the
64-rule grammar above. It also knows that a name no rule defines is an
error rather than a reference to somewhere else, so it says so at the
splice.
A rule's result type is the one thing the grammar does not determine, which
is what the `:: T` annotations are for. They are claims, not assertions:
`Grammar` demands `Rules s env env`, so GHC checks each against what the
rule body actually returns. *(At the time this also meant GHC recomputed
the FIRST sets and so could not be lied to about them; the entry above is
what changed that.)*
`examples/Arith.hs` and `examples/Layout.hs` are written this way now and
declare no environment at all. `pegRules` is unchanged and still the way to
write a rule set that is only part of a grammar; `examples/Compat.hs` and
`examples/Patterns.hs` keep using it.
- `PEG.Syntax.NTW` and `ntw`: a non-terminal reference that carries its own
`Member` proof instead of having `KnownMember` search for it. The `Lookup`
equality is kept, so `ty` and `a` still come from the environment and a
proof that names the wrong rule does not compile — this is not a weaker
claim than `NT`, only a cheaper one. Worth **2.6x** on a 64-rule grammar.
A splice knows each rule's position and can write the proof down; a
hand-written grammar has nothing to gain and should keep using `nt`.
- `bench-compile/`: a generator and a sweep script for the numbers above.
- A test-suite, `typed-peg-analysis`, that reads `examples/` and requires the
computed environment of each grammar to equal the one written there.
### Compile time of large grammars
Checking a grammar was **exponential in the size of its FIRST sets**. On a
chain of `n` mutually referring rules, GHC needed 0.7 s at `n = 8`, 12 s at
`n = 12`, and more than five minutes at `n = 15`; anything the size of a real
language front end never finished. The same grammars now check in
milliseconds-to-seconds and the curve is polynomial: `n = 12` takes 0.5 s,
`n = 30` 1.7 s, `n = 60` 14 s.
One limit is new rather than fixed: the union of two FIRST sets nests one
type-family reduction per element of the result, so a FIRST set of more than
about a hundred non-terminals now reports `Reduction stack overflow` instead
of being slow. `-freduction-depth=0` lifts it, and a union of two 128-element
sets then takes about 0.3 s.
### Fixed
- **`Union` and `ConsIfAbsent` were exponential.** `ConsIfAbsent x xs`
expanded to `If (Elem x xs) xs (x ': xs)`, naming `xs` three times. In
`Union (x ': xs) ys = ConsIfAbsent x (Union xs ys)` that `xs` is an
unreduced `Union`, so each step left GHC three copies of the pending
computation to reduce and each of those tripled again: `3^n` reductions for
a union of two `n`-element sets. Both families now dispatch on an
already-computed `Ordering` in a helper whose every right-hand side names
each argument — and in particular the recursive call — exactly once.
- **`Lookup` threaded the whole environment through its recursion** so that
the not-found case could list the available non-terminals. An environment
of `n` rules is `O(n^2)` type nodes, because every entry carries a FIRST
set, and there is one lookup per occurrence of every non-terminal. The
search now carries only the tail it has still to scan; the environment is
named once, in the branch that reports the error.
- **`Lookup` matched through `CmpSymbol` and a dispatch family**, two
type-family reductions per entry scanned. It now matches on a non-linear
pattern — the name appears twice in the clause — so GHC decides each entry
by syntactic equality and apartness, in one reduction. The trick is
`Data.Type.Map`'s, from `type-level-sets`. Worth 1.4x-1.6x on a large
grammar, since the search runs once per occurrence of every non-terminal.
- **`nt` and `PExp`'s `NT` made GHC search the environment several times per
occurrence.** Their constraint was
`KnownMember n env (TyOf (Lookup n env)) (ResOf (Lookup n env))`, and
resolving `KnownMember` walks `env` one instance at a time, re-normalising
every index at each step. Both now name the entry once, through a
`Lookup n env ~ 'EnvEntry ty a` equality, and pass the resulting rigid
types to `KnownMember`.
### Changed
- **Breaking. A FIRST set is now written in alphabetical order**, and a
declared environment that lists one in any other order is a type error
naming the first position that disagrees. Sortedness is what makes a set
have a single spelling, which is what lets `Union` be one merge pass.
Migration is mechanical: sort each `'[...]` in your `Env`, so
`'["term", "factor", "number"]` becomes `'["factor", "number", "term"]`.
- **Breaking.** `Member` and `KnownMember` lose their `Ty` index:
`Member s env a` and `KnownMember s env a`. Every index of a class is
carried along and re-normalised at each step of the instance chain that
walks the environment, and a `Ty` carries a FIRST set — so an index for it
made each step cost `O(|env|)`. Nothing needed it; `Here` binds the
entry's `ty` existentially, which is enough to pull a rule out of a rule
table.
- `PEG.Syntax` exports `NTGo`, the `Ty` of a reference to a non-terminal
whose own `Ty` is already known. `NTTy n env` is now defined as
`NTGo n (TyOf (Lookup n env))` and keeps working in signatures.
`SeqTy` and `ChoiceTy` are deliberately **unchanged**. They duplicate their
operands across their right-hand sides too, but measurement says that costs
nothing here, and writing them as type synonyms is what makes them reduce to a
`'MkTy` head while their operands are still abstract — which is what lets a
polymorphic combinator such as `lexeme` compose without its caller having to
get the nesting of `SeqTy` exactly right.
## 0.2.0.0 — 2026-09-04
This release is **not source-compatible with 0.1.0.0**: `PExp`, `Rules`,
`Grammar`, `Result` and `PState` all gain a leading stream type parameter, and
a rule whose result is a character-class repetition changes result type. See
*Changed* below for the migration.
### Added — parsing any stream, not just `String`
`PEG.Stream` introduces a `Stream` class, with instances for `String`, strict
and lazy `Data.Text.Text`, and strict and lazy `Data.ByteString.ByteString`.
A grammar written once runs over any of them.
The genericity reaches the *results*, not just the input: a character-class
repetition such as `cs:[a-zA-Z0-9_]+` now produces a **chunk of the input
stream** — a real `Text` slice — instead of unpacking into a `[Char]`. Two new
`PExp` constructors, `Span` and `Span1`, carry this; the quasi-quoter emits
them for `[...]*`, `[...]+`, `'c'*`, `'c'+`, `.*` and `.+`.
`ByteString` is read as Latin-1, exactly as `Data.ByteString.Char8` does: fast,
correct for ASCII, and wrong for multi-byte UTF-8. `PEG.Stream`'s Haddock
states this as a law rather than a footnote.
Only `unconsS` has no default, so a user instance is one method. It returns an
unboxed sum rather than `Maybe (Char, s)` on purpose — behind a class
dictionary the boxed version would allocate a `Just` and a pair for every
character, losing the zero-allocation terminal path.
### Changed
- **Breaking.** `PExp`, `Rules` and `Grammar` take a leading stream parameter:
`PExp s env ty a`, `Rules s env defs`, `Grammar s env ty a`. `Result` and
`PState` likewise: `Result s a`, `PState s`.
- **Breaking.** A rule whose result is a character-class repetition now has
result type `s`, so its `Env` synonym takes a parameter. Semantic actions
that fed such a result to something expecting a `String` need
`chunkToString`: `number <- ds:[0-9]+ { Lit (read (chunkToString ds)) }`.
- **Breaking.** The symbol variable in `PExp`'s `NT`, in `nt`, and in
`Rules`'s `RCons` is now named `n`; `s` is the stream. `nt @"name"` is
unaffected — the name is deliberately still the first quantified variable.
- `PEG.Semantics.Simple`'s unrelated `Stream` class is renamed
`SimpleStream`, to leave the name to `PEG.Stream`.
- `PState`'s input field is now strict.
A `Grammar` is monomorphic in its stream. Reusing one across stream types
needs a `forall s. Stream s => Grammar s env ty a` signature, which turns the
value into a function of a dictionary and so stops the compiled parser being
shared between calls. Give parsers a monomorphic top-level binding where that
matters; `PEG.Parse`'s Haddock spells this out.
### Performance
Measured on the benchmark suite, bytes allocated per input byte, against the
previous release of the evaluator:
| grammar | before (String) | String | Text | ByteString | megaparsec |
|---|---|---|---|---|---|
| arith | 990 | 943 | 1127 | 969 | 1239 |
| csv | 834 | 787 | 951 | 805 | 1035 |
| json | 459 | 404 | 583 | 452 | 782 |
| nested | 265 | 312 | 481 | 336 | 1283 |
| quoted `(!'"' .)*` | 162 | 209 | 320 | 250 | 128 |
`ByteString` is the cheapest column on five of the seven grammars and beats
megaparsec on six. `Text` costs more than `String` throughout — the same
result the earlier study found for megaparsec, and worth knowing before
reaching for it.
Two grammars regressed on `String` (`nested` +18%, the `(!'"' .)*` idiom
+29%). Both are dominated by single-character steps rather than bulk scans,
where `unconsS` is one indirect call that the previous direct cons-cell match
did not need. The five grammars that do any bulk scanning improved by 5-12%.
The `idents` and `quoted [^"]*` groups are not in the table because their
grammars changed: `ident` moved from `c:[a-zA-Z_] cs:[a-zA-Z0-9_]*` to
`&[a-zA-Z_] cs:[a-zA-Z0-9_]+` so that it returns a chunk rather than consing a
character onto one, and `Bench.Mega`'s `identP` moved to `takeWhile1P` to keep
the comparison like-for-like. On the new grammars typed-peg allocates 100
B/byte over `String` and 84 over `ByteString`, against megaparsec's 179.
### Performance
The evaluator was rewritten twice: once around a compilation step, once around
an unboxed step result. On the benchmark suite in `bench/` (see `cabal bench`),
measured against megaparsec 9.8 in the same run, typed-peg went from taking
2.1x-58x the time megaparsec takes to taking 0.95x-1.17x of it — and it now
allocates less than megaparsec on six of the seven grammars. The one grammar
where it still loses is the `(!'"' .)*` idiom, which scans every character
twice by construction; written as `[^"]*` it costs 1.23x-1.35x.
- A compiled step returns an unboxed sum, `(# (# #) | (# a, PState #) #)`,
rather than `Maybe (a, PState)`. The two are isomorphic, but the unboxed
sum travels in registers, so a step that succeeds no longer allocates a
`Just` *and* a pair on top of the new state, and a step that fails
allocates nothing at all. This makes `Seq` and `Map` — the two
constructors the quasi-quoter emits for every grammar item — completely
allocation-free, and cuts total allocation by a further 9–53%.
- String literals match in a single loop that builds one `PState`, rather
than one per character, whenever the grammar does not use layout.
- `PEG.Parse` now *compiles* a `Grammar` into a closure once, instead of
walking the `PExp` GADT and the rule list on every step. Resolving a
non-terminal is now one indirect call rather than a linear scan of the rule
environment. `parseWith opts g` is written so that partially applying it
yields the compiled parser; bind it to a name to reuse it.
- Character classes compile to a single `Sat` node holding a `PEG.CharSet`
(a 256-bit bitmap), instead of expanding into a chain of ordered choices.
Matching one character of `[a-zA-Z0-9_]` used to cost 63 parser steps.
- String literals compile to a single `Str` node instead of a chain of
`Seq`/`Map`/`Term`.
- The parser no longer builds a `[(Char, Int)]` copy of the input; the column
of the current character is carried in the state and updated incrementally.
- Terminals take a fast path that skips all interval arithmetic when the
ambient column relation is total (`anyR`), which is the case for every
grammar that does not use layout. The new `rdTotal` field of `RelD` records
this.
- `parse` returns the unconsumed suffix in `O(1)` instead of recomputing it
with two `length` calls and a `drop`.
- `Star` no longer builds a chain of selector thunks.
### Added
- Negated character classes in the quasi-quoter: `[^"]` matches any character
other than a quote. Previously the only way to write this was
`(!'"' .)`, which scans every character twice — once for the lookahead and
once for the dot. On the `quoted` benchmark the class form halves the
allocation.
- `PEG.CharSet`: compact character sets, re-exported from `PEG`.
- `PEG.Syntax.Sat` / `PEG.Syntax.Str` constructors, and the `sat`,
`charClass` and `notCharClass` smart constructors.
- `PEG.Parse.compileGrammar` and the `Step` and `Res` types, for callers that
want the compiled parser directly.
- `PEG.Indent.rdTotal`.
- A criterion benchmark suite comparing typed-peg with megaparsec
(`bench/`, run with `cabal bench`).
- `examples/Compat.hs`: a differential battery used to check that the
optimisation work did not change any observable behaviour.
### Changed
- **Breaking.** `PState` now holds the remaining input as a `String` plus the
current column and offset (`stInput`, `stCol`, `stOff`), rather than a
precomputed `[(Char, Int)]`. `PEG.Parse.Input`, `PEG.Parse.columns` and
`PEG.Parse.eval` are gone; use `compileGrammar` instead of `eval`.
- **Breaking.** `RelD` has a new `rdTotal` field.
- **Breaking.** `PEG.Parse.Step` now returns the unboxed sum `Res a` instead
of `Maybe (a, PState)`. This only affects code that called
`compileGrammar` directly; `parse` and `parseWith` are unchanged.
- **Breaking.** In a quasi-quoted grammar, a `^` immediately after `[` now
negates the class instead of standing for itself; write `[\^]` for a class
containing a caret.
- The `template-haskell` upper bound now admits the version shipped with
GHC 9.10 (`< 2.24`).
## 0.1.0.0 — 2026-08-28
### Added
- Initial release.
- Type-safe PEG parser combinators with compile-time left-recursion detection
via type families (`PEG.Grammar`).
- FIRST-set and nullability information tracked at the type level (`PEG.Type`,
`PEG.TyLevel`).
- Indentation-sensitive parsing primitives (`PEG.Indent`).
- Quasi-quoter `pegRules` for writing grammars in a concrete DSL (`PEG.QQ`).
- Simple semantics interpreter (`PEG.Semantics.Simple`).