@hackage / rtk

Parser and rewrite facility generator from grammar specifications

Changelog

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

[Unreleased]

[0.11] - 2026-06-12

Highlights: RTK is now self-hosting by default — grammar files are parsed with the front end RTK generated from its own grammar description, test-grammars/grammar.pg is the authoritative definition of the grammar language, and the hand-written front end is a reference oracle selected by --use-handwritten. Errors are structured, positioned diagnostics rendered in GNU one-line style; generated ASTs carry equality-transparent source positions. A reworked test architecture — golden snapshots, dual-front-end equivalence, a compile gate over every snapshot — enforces all of it. Quasi-quoters gained a $$ escape and honest context errors; packaging gained PVP bounds; CI a pinned, cached toolchain.

Added
  • Early-warning CI job (ghc-latest): builds with -Werror and runs the cabal test suites once against the newest GHC series the CI runner image ships (currently 9.14), relaxing only rtk's own bounds on the GHC boot libraries. Warnings a new GHC promotes into -Wall (or turns on by default) now surface on every push instead of at the next toolchain bump; the pinned primary job stays authoritative. rtk's own code is kept warning-clean portably: pattern matches instead of head (9.8 warns on every head/tail use, -Wx-partial), and the no-op Typeable derivings dropped (9.14 promotes -Wderiving-typeable into -Wall; explicit Typeable deriving has been meaningless since GHC 7.10). The compiled-in generated snapshot gets a scoped, GHC-gated -Wno-x-partial (generated code is not edited to placate linters - the lexer generator emitting drop 1 instead of tail is tracked as follow-up work, since it churns every golden)
  • Provenance banner: every generated artifact (<Name>Lexer.x, <Name>Parser.y, <Name>QQ.hs) now opens with -- Generated by RTK from grammar '<Name>'. Do not edit by hand. The banner deliberately names the grammar rather than the grammar file (a path would make the output - and the golden snapshots - depend on where the grammar lives) and carries no rtk version (a version would couple every release bump to a full golden churn)
  • make test-compile-goldens, wired into CI after the cabal test suites: runs alex -g and happy --ghc over every checked-in golden <Name>Lexer.x/<Name>Parser.y pair and typechecks the result with ghc -fno-code. The golden suite diffs text only and sat green while the debug-test and t1 snapshots did not compile; the gate closes that test-architecture hole (QQ goldens join once the regex-posix dependency is dropped, task 8b)
  • Source positions in generated ASTs: every constructor that generated parsers build (except the quasi-quotation-only Anti_* splice constructors) now stores the position of its alternative's first symbol in a leading RtkPos field. RtkPos is transparent for equality and ordering (== always holds, compare is always EQ), so ASTs that differ only in source positions compare equal — in particular a quasi-quote parsed at compile time still matches the same construct parsed at run time, and quasi-quote patterns wildcard every position field while expressions may embed them. Payload-carrying %token bindings now bind the whole positioned token, with generated tkVal_* extractors recovering the payload in semantic actions; a generated RtkPosOf class projects the position of any symbol (tokens, nonterminals, lists, optionals). Generated code stays dependency-free. The self-hosted front end now maps the rule constructors' positions into getIRulePos (previously Nothing under --use-generated), so pipeline diagnostics carry real FILE:LINE:COL: positions with both front ends, and the dual-front-end AST equality suite compares positions too. The hand-written parser's position for the '.' id ':' … rule form moved from the identifier to the leading dot (a rule's position is where the rule starts), aligning it with first-symbol capture; no corpus grammar uses that form
  • --debug-rule RULENAME is back, this time with a real implementation (it was removed together with the other never-implemented placeholder flags): it traces one rule through the pipeline, printing only that rule's representation after each stage — its mentions in the token stream (with positions), the matching IRules after parsing and after string normalization (making literal-to-!tok_* rewrites visible), and the matching rule groups/lexical rules after clause normalization and constructor filling — instead of full-grammar dumps. --expand-rule shows a rule's final expanded form; this flag shows its evolution. When the rule is missing at a stage the trace says so and lists up to five case-insensitive near matches (normalization renames things — Rule_N, ListElem_*, tok_*); a rule found at no stage at all fails the run with exit code 1, so typos don't go unnoticed in scripts. Composes with --debug-stage (stop early) and works under --use-generated, where the token stage is internal to the generated front end and the trace starts after parsing
  • Self-hosting milestone (Prototype 2 closed): rtk --use-generated parses grammar files with the lexer/parser RTK generated from test-grammars/grammar.pg. The generated modules are compiled into rtk straight from the checked-in golden snapshot (test/golden/grammar/, the bootstrap stage produced by the previous rtk binary, kept current by make accept-golden), and src/generated/ASTAdapter.hs converts the generated AST to the hand-written InitialGrammar; everything after parsing is the same shared pipeline. The golden suite now runs every grammar in test-grammars/ through BOTH front ends and requires byte-identical artifacts, and the unit suite asserts AST equality (positions stripped) for every grammar. The fixed point holds: rtk --use-generated test-grammars/grammar.pg out/ regenerates test/golden/grammar/ exactly. Accepted divergences (documented in BOOTSTRAP.md): errors carry positions in the message text rather than structured diagnostics, getIRulePos is not captured (both converge in task 7b), no nested /* /* */ */ comments (#25), no concatenation of adjacent """…""" blocks. The harness also surfaced two constructs the hand-written parser accepts beyond grammar.pg's own definition of the language — empty alternatives (Gd = | ExpI ; in haskell.pg) and redundant parentheses kept as semantic grouping ((ImportStatement)* in java.pg, (A B) C in t1.pg) — so those three grammars are pinned in the test suites (frontEndDivergentGrammars) with a guard that fails once they stop diverging; resolving which front end defines the language is follow-up work
  • Generated parsers, lexers and quasi-quoters report errors with Either instead of throwing (the deferred "Stage G" of the diagnostics migration): generated parsers use %monad { Either String }, so parse<Name> :: [PosToken] -> Either String <AST> mirrors the shape of the hand-written grammar parser; generated lexers expose scanTokens :: String -> Either String [PosToken] (alexScanTokens stays as a throwing compatibility wrapper); and the generated quasi-quoters route lexer, parser and unknown-metavariable failures through fail in TH.Q, so a bad quasi-quote is now a positioned GHC compile error at the splice site instead of a runtime crash during Template Haskell expansion. Generated code stays dependency-free
  • Duplicate rule definitions are rejected: defining the same rule name twice in a grammar is now a normalization error carrying both source positions (e.g. g.pg:3:1: error: in rule 'Foo': rule 'Foo' is defined more than once (first definition at line 2, column 1)), instead of the definitions being silently merged into one rule group with extra alternatives (closes #20). test-grammars/debug-test.pg, the one grammar that relied on this, now defines IfStatement once with | alternatives
  • A $$ escape in quasi-quote bodies: $$name now produces the literal text $name instead of being rewritten as a metavariable (or rejected). Previously the generated quasi-quoter rewrote $ident everywhere in a quote body — including inside the quoted language's own string literals — mangling programs. Each $$ pair directly before a metavariable stands for one literal $ (so $$$x is a literal $ followed by the metavariable $x). The unknown-metavariable error now names the offending $name, lists the known shortcuts and points at the $$ escape (see docs/why-qq-limitations.md)
  • Hackage packaging hygiene: PVP version bounds on all dependencies and on the alex/happy build tools, Tested-With now lists GHC 9.4.7 and 9.6.4 (the versions actually exercised locally and in CI), and the packages required by RTK-generated code are documented in the README and the cabal description
  • Structured diagnostics: grammar errors are now Diagnostic values (message plus optional source position and context) threaded through Either, instead of being thrown with error. The grammar-processing pipeline functions (scanTokens, parse, normalizeTopLevelClauses, genX/genY/genAST/genQ) are total for user-caused failures
  • One-line GNU-style error reporting: rtk prints FILE:LINE:COL: error: MESSAGE to stderr and exits 1 for a bad grammar, with no Haskell exception or call stack (closes #23 and #31)
  • A lifted (,) clause under */+/? (e.g. Foo = ,Bar* ;) is now rejected with a clear error during normalization, instead of silently generating broken code
  • A reference to an unknown rule now names both the unknown rule and the type that references it
  • Source positions on tokens: the lexer now returns PosToken values (token plus line/column), both in the hand-written lexer and in all generated lexers
  • Parse errors report line, column and a human-readable description of the unexpected token (e.g. Parse error at line 2, column 1: unexpected identifier 'Foo'); generated parsers report positions too instead of dumping the remaining token list
  • Errors at end of input carry the position where the input ended, in both the hand-written and generated parsers
  • Grammar normalization errors name the offending rule and its source position (e.g. Grammar error in rule 'Foo' (at line 2, column 1): ...)
  • Lexer-generation errors name the lexical rule they occur in
Changed
  • RTK is now self-hosting by default — the headline of this release. Grammar files are parsed with the front end RTK generated from its own grammar description, and test-grammars/grammar.pg is the authoritative definition of the grammar language. The hand-written Lexer.x/Parser.y are demoted to a reference oracle selected with the new --use-handwritten flag (--use-generated remains accepted and is now a no-op); the equivalence harness keeps holding both front ends to identical artifacts and equal ASTs for every corpus grammar, and the bootstrap fixed point now holds for a default invocation: rtk test-grammars/grammar.pg out/ reproduces test/golden/grammar/ byte-for-byte. Changes to the grammar language land in grammar.pg (plus regenerated goldens) first; the hand-written files follow only to keep the harness green. See BOOTSTRAP.md
  • Front-end error parity (prerequisite of the default flip): generated lexers and parsers now encode failures as machine-splittable LINE:COL:message (previously prose like Parse error at line L, column C: …), the shared Diagnostics.diagnosticFromPositioned splits the encoding into a positioned diagnostic, and rtk renders the same GNU-style FILE:LINE:COL: error: … line under both front ends — for lexical errors the stderr line is identical character for character; for parse errors the position is identical and only the token wording differs (generated parsers render tokens generically). Generated quasi-quoters re-render the encoding human-readably (line L, column C: …) in their fail path, as do the standalone test drivers. Every golden <Name>Lexer.x/<Name>Parser.y changed uniformly with the new error templates
  • The two historic front-end divergences are resolved and the pinned-divergence list (TestSupport.frontEndDivergentGrammars) is empty: the hand-written reference parser now defines the same language as grammar.pg — it rejects empty alternatives (R = | X ;) and lifts redundant parenthesis groups exactly like grammar.pg's Clause5 = '(' ,Clause ')' (single-leaf groups collapse, pure-sequence groups merge at the head of a sequence, alternation groups merge as the first alternative); haskell.pg's Gd = | ExpI ; was rewritten as the equivalent Gd = ExpI? ;. java.pg, t1.pg and haskell.pg artifacts changed accordingly (fewer proxy sub-rules, e.g. java.pg's (ImportStatement)* now generates a plain list rule)
  • The core pipeline data types (InitialGrammar, IClause, NormalGrammar, …) moved from the footer of the hand-written Parser.y into the new front-end-agnostic Syntax module; a demoted parser no longer owns the project's core types. Pure move, no behavior change
  • --debug-tokens in the default (generated) front end now dumps the generated lexer's token stream (it previously printed nothing under --use-generated)
  • The Java grammar parses exactly ONE ModifierList per declaration. The class/interface/enum/@interface rules no longer begin with their own nullable list; TypeDeclRest (ex-NestedTypeDeclaration, now used at the top level too) carries everything after the modifiers, and the list lives on the enclosing rule: TypeDeclaration = OptDocComment ModifierList TypeDeclRest, FieldDeclaration = OptDocComment ModifierList (MemberDeclaration | TypeDeclRest | StaticInitializer) | ';'. The nested nullable lists used to produce 14 shift/reduce conflicts (after the outer list, every modifier/annotation token chose between extending it and epsilon-starting the inner one) whose shift resolution parsed public class A {} with public on the OUTER list and a confusing, always-empty inner list; that always-empty ModifierList field is gone from the class/interface/enum/annotation AST constructors, and the generated quasi-quoter renames nestedTypeDeclaration to typeDeclRest. Together with the restored dangling-else conflict (see Fixed) the generated JavaParser.y is down to 18 shift/reduce + 0 reduce/reduce conflicts (from 32 + 0), and java.pg now opens with a complete inventory of all 18 - each family with its automaton items and why the shift is the correct Java reading (dangling else; catch/finally attach to the nearest try; member id vs empty TypeParameters; greedy CompoundName .; bracket-list [ shifts; < commits to type arguments; the QQ bootstrap dummy bracket) - replacing the stale "~14"/"~13"/"32" conflict comments. The commons-lang corpus success sets are unchanged (14/16 main/tests files), so the parser blacklists stay as they are
  • The makefile test pipeline now runs alex with -g (the GHC backend), so generated lexers in test-out/ compile as compact string-encoded tables instead of ~half-a-million-line pattern matches. GHC's compile of the Java lexer drops from minutes to seconds with identical token streams (verified against the test-lex-java goldens). The library's own lexers already used -g via cabal's preprocessor; this closes the gap for the makefile-driven tests (#27)
  • The $Type:var splice alternative is now attached to a minimal set of rules of a shared-type group instead of to every rule. The normalizer builds the group's lift graph (rule A → rule B when B has an alternative that is exactly the single nonterminal A, ignoring nullable clauses) and greedily picks attach points whose unit-closure covers every rule the grammar demands from some position; a splice token reduces at an attach point and climbs the chain to the level its position requires. For java.pg's 18-rule Expression chain the single attach point is PrimaryNoPostfix, which removes the 806 reduce/reduce conflicts (of 883) the per-rule alternatives used to cause, along with the three "rule ... is unused" happy warnings, and makes the parse of a splice independent of conflict-resolution accidents. Types declared by a single rule are unaffected. A group whose demanded rules cannot be covered from one attach point gets several; if their closures overlap, the overlap can reintroduce reduce/reduce conflicts between the splice reductions (inherent to such grammars; normalization has no warning channel to report them)
Removed
  • The --debug-format option: its only honest format was the pretty default - compact merely stripped newlines into an unreadable single line (and the advertised json/tree formats had already been removed as never-implemented). Debug output is always pretty-printed now; DEBUG_OPTIONS.md and test-debug-options.sh follow
  • The orphan PrintGrammar module: a dead pretty-printing draft predating the current pipeline, listed in the cabal file but imported by nothing (pretty-printing returns properly as a tracked feature)
  • The makefile's Windows_NT branch: its dist/build/rtk/rtk.exe was the cabal-v1 path, dead for years - the makefile is Unix-only and now says so
  • The superseded textual bootstrap comparison: compare-bootstrap.sh, the make test-bootstrap target and its informational CI step. Behavioral equivalence of the two front ends is enforced by the golden/unit harness on every test run; textual identity of the generated .x/.y with the hand-written ones was never the goal
  • Unimplemented CLI options that were advertised in --help but had no effect: --debug-rule, --compare-stages, --memory-stats, --debug-output-dir, --debug-log, --interactive, the placeholder json/tree debug formats, and the --use-generated stub that only printed an error
Fixed
  • Generated quasi-quoters' quoteType/quoteDec no longer lie: they used to silently return dummies (TH.ListT / []), so a quote in a type or declaration context compiled into nonsense. Both now fail in TH.Q, making the misuse a GHC compile error at the splice site ("this quasi-quoter cannot be used in a type/declaration context")
  • Writing into a missing output directory no longer escapes as a raw IOException: rtk g.pg /tmp/does/not/exist now creates the directory and succeeds; IO failures that remain (no permission, a file where the directory should be) are rendered as the usual one-line GNU-style diagnostic and exit 1
  • A literal backslash inside a [...] character class is now emitted Alex-escaped (\ → \\) by the lexer generator; it used to pass through raw, where Alex set syntax reads it as an escape, forcing grammars onto the [\x5C] hex spelling (issue #95's smaller finding). The \n \t \r \f \v pairs that token post-processing preserves keep passing through bare. java.pg drops its hex workarounds for a backslash charset macro and a plain [^\"\\\n\r] negated class; generated Java token streams are byte-identical (the test-lex-java goldens are untouched). One grammar-lexer limitation remains, documented at the macro definition: a class ending in a backslash must also end its source line, because \] lexes as an escape pair
  • GenAST's unreachable backstop for lifted clauses claimed "lifted rules are not yet implemented" - a missing feature it is not; reworded to the Internal error (GenAST): … convention (Normalize rejects or filters every lifted position before AST generation)
  • A type declared only through rule annotations (Thing : Item = … with no rule named Thing) could not be referenced: a plain S = Thing ;, a list element Thing* ~ ',', or merely the QQ start wrapper (which references every public type by name) failed generation with reference to unknown rule 'Thing'. rtk now synthesizes the cover rule that grammar authors wrote by hand for this (java.pg's Expression : Expression = AssignmentExpression ;), in lifted form — Thing : Thing = ,Item1 | ,Item2 ; — so the type gets a nonterminal without an extra AST constructor. Synthesis is demand-driven (a grammar that never references the bare type is generated byte-identically) and happens on the parsed grammar before normalization, so the cover takes part in the splice attach-point machinery like a hand-written one: the $Thing:var alternative lands on one annotated rule and climbs to the type through the cover, and the covered type gets a top-level quoter. LALR conflicts of the synthesized cover are exactly those of its hand-written equivalent (overlapping FIRST sets among the annotated rules remain the grammar's own, and happy still reports them). The remaining unresolvable case — referencing a lexical rule's value type, which declares no syntax type — keeps a diagnostic that now explains the type-named-rule convention. New corpus grammar test-grammars/i14.pg pins all reference shapes in the golden suite and compile gate, and make test-i14-qq (wired into CI) exercises quoters and splices against the covered types (#14)
  • A grammar whose start rule is a repetition (Start = Item* ;) generated a parser that did not compile: the QQ start-wrapper alternatives extended the start group as a data declaration while the repetition typed the same nonterminal as the alias [Item] (plus a dummy-token shift/reduce conflict against the empty list). Such an alias start group now skips the QQ entry-point machinery entirely — no dummy tokens, wrapper alternatives or top-level quoters, since an alias has no constructor to project a quote through — while element-level $Type:var splices keep working. Groups merely referenced by a wrapper alternative (grammar.pg's RuleList = Rule*) were always well-typed and are unchanged. The debug-test golden, uncompilable until now, is regenerated (#34)
  • Repetition over a terminal silently generated uncompilable code: Foo = 'x'* ; emitted a degenerate self-recursive data Foo against list-building parser actions, and Foo = num* ; an invalid lowercase data num. Decided as by-design and rejected during normalization with a positioned diagnostic: a list element must be a syntax rule, because the element type hosts the list's splice constructor — wrap the terminal in a syntax rule and repeat that rule instead. A lifted (,X) element under */+ is rejected the same way instead of crashing the generator (#28)
  • The synthesized QQ start wrapper is now emitted directly adjacent to the rule it wraps: list-element proxy rules could separate the two same-named rule blocks in the generated .y, which happy rejects outright ("Multiple rules for 'A'", t1.pg's golden was affected)
  • A brace-less nested if parses again: IfStatement's then-branch was StatementWithoutIf, so valid Java like if (a) if (b) f(); else g(); was rejected with "unexpected 'if'". The then-branch is a full Statement and StatementWithoutIf is inlined away (Statement absorbs its alternatives; nothing else referenced it). This re-surfaces the classic dangling-else shift/reduce conflict, which happy resolves by shifting: else binds to the NEAREST if, exactly the JLS 14.5 rule (verified on the printed AST; regression coverage via test-grammars/java/test-nested-if.java / make test-java-nested-if and a quasi-quotation construction case). The exclusion never even avoided that conflict - it already existed through loop bodies in then-position, e.g. if (a) while (b) if (c) f(); else g(); - it only rejected the direct nested form
  • The Java grammar's last structural LALR ambiguity - deciding between a type and an expression after a CompoundName at statement start or after ( - is resolved JLS-style (happy now reports 0 reduce/reduce conflicts on the generated JavaParser.y, down from 2). Types and declarators take only empty bracket pairs (Dims/NonEmptyDims, anchored on the unreduced name so [ is a plain shift); only array creation takes sizing expressions; CastExpression uses the JLS trick ('(' Expression ')' UnaryExpressionNotPlusMinus for reference casts plus explicit primitive/generic/array alternatives); and array access is anchored on CompoundName in PrimaryNoPostfix. a[0] = 1;, x = (a);, x = (Foo) y;, x = (List<String>) y;, ((Map) c).get(k); and new int[3][]; now parse; JLS-invalid int[3] x; declarations are now rejected. Known residual limitation (shared by LALR Java parsers generally): (a < b) as a parenthesized primary mis-commits to a generic cast on < (conditions like if (a < b) are unaffected)
  • make test-p works again: the target had a hand-rolled recipe that compiled the driver with bare ghc outside the cabal package environment, failing with Could not find module 'Data.Generics' in clean environments. It now uses the generic make-test-rule like its sibling targets (cabal exec -- ghc --make -itest-out ...); the driver binary is consequently named test-out/p-main instead of test-out/p-rtk. The compile failure had masked a latent bug in the driver itself: p-main.hs's subst bound e1 = subst id e1 i etc., self-referential recursive lets that shadow the pattern variables and diverge (<<loop>>) on the first fold expression, and it had no base case. The lets now bind fresh names and a catch-all clause terminates the recursion, so the driver prints the substituted AST
  • '\f' and '\v' escapes in grammar string and [...] regex literals now reach the generated lexer as bare Alex escapes; previously token post-processing (unBackQuote) stripped them to the literal letters f/v even though GenX.isAlexEscape was ready to emit them, so the two escape sets disagreed. The preserved set (\n \t \r \f \v) is now pinned to isAlexEscape by a unit test
  • test-grammars/haskell.pg is self-consistent again: minimal Pat and QOp rules were added for the previously dangling references, so RTK generation no longer aborts on it (progress on issue #30; the grammar is still far from full Haskell). The haskell special cases in the test suites were dropped and golden snapshots added
  • A grammar whose first rule is lexical (or has a data-type annotation different from the rule name) no longer crashes with fromJust: Nothing; it reports that the first rule must be a syntax rule, or resolves the annotated type correctly
  • Internal fromJust calls in code generation replaced with descriptive internal-error messages
  • Invalid clauses in lexical-rule macros now abort generation with an error instead of writing the error text into the generated lexer
  • User-facing errors no longer print a GHC call stack
  • --debug-stage now exits with a success status after stopping at the requested stage instead of reporting failure via error
  • --profile-stages timings now force each stage's result to normal form, so per-stage durations are no longer skewed by lazy evaluation
Documentation
  • Replaced the README "Grammar Format" example, which used Happy-style semantic actions that RTK cannot parse, with a verified .pg example
  • Removed the stale Claude.MD (a case-colliding near-duplicate of CLAUDE.md; its Quick Reference table was folded into CLAUDE.md) and the stray root test-simple-return.java duplicate

[0.10] - 2025-12-03

Added
  • MIT license with generated code exemption
  • Full Java grammar support with comprehensive parsing tests
  • Quasi-quotation support for embedding parsed syntax in Haskell
  • Debug options for grammar development and troubleshooting
  • Bootstrap self-hosting capability (RTK can parse its own grammar format)
Fixed
  • Alex escape sequence generation in GenX.hs
  • Java grammar lexer patterns for complete test coverage

[0.9] - Initial Development

Added
  • Core grammar specification format (.pg files)
  • Alex lexer generation (GenX.hs)
  • Happy parser generation (GenY.hs)
  • AST generation (GenAST.hs)
  • Quasi-quotation generation (GenQ.hs)
  • Grammar normalization and transformation