A packrat parser-combinator library driven by Ruby's experimental `for ... then` comprehension

packrat_parser_notes.md

I built a small PEG/packrat parser-combinator gem (packrat_parser) whose grammar rules can be written with a Scala-style for-comprehension. The comprehension is a feature of an experimental Ruby fork: for x in p, y in q then ... end desugars (at parse time) to p.flat_map { |x| q.map { |y| ... } }. Along the way I hit a subtle bug caused by the comprehension's loop variables leaking into the enclosing method scope. This writeup is mostly about that bug.

The comprehension is only recognized by the fork's legacy parser, so everything below runs with ruby --parser=parse.y. The default (Prism) parser rejects for ... then.

The API

You subclass PackratParser and define each grammar rule as a method that returns a parser. The combinator type supports the four monadic operations the comprehension desugars to — flat_map, map, filter (plus pure) — and an ordered-choice operator |.

class SimpleCalcParser < PackratParser
  start_symbol :additive

  def additive
    (for x in multitive, _ in term("+"), y in additive then x + y end) |
      (for x in multitive, _ in term("-"), y in additive then x - y end) |
      multitive
  end

  def multitive
    (for x in primary, _ in term("*"), y in multitive then x * y end) |
      (for x in primary, _ in term("/"), y in multitive then x / y end) |
      primary
  end

  def primary
    (for _l in term("("), x in additive, _r in term(")") then x end) |
      number
  end

  def number
    for s in term(/\d+/) then s.to_i end
  end
end

SimpleCalcParser.parse("1+2*3")   # => 7
SimpleCalcParser.parse("(1+2)*3") # => 9

The comprehension's desugaring, for reference:

for x in p, y in q when y > 0 then x + y end
# == p.flat_map { |x| q.filter { |y| y > 0 }.map { |y| x + y } }

A non-final generator becomes flat_map, the final one becomes map, and a when guard becomes filter.

Two things that make this non-trivial

1. Rules must be lazy

A comprehension evaluates its generator receivers eagerly in order to call flat_map /map on them. If a rule method ran its body on every reference, a self-referential rule like additive (which mentions additive on its right-hand side) would recurse forever while the combinator graph is being built.

The fix: every method defined in a PackratParser subclass is rewritten (via method_added) to return a lazy, memoizing Rule object instead of building its combinator immediately. The Rule only builds/runs at parse time, and it memoizes its result per (rule, position) — that's the packrat property, and it's what keeps parsing linear.

2. The comprehension's loop variables leak — and that breaks naive memoization

This is the interesting one.

In the fork, the comprehension's loop variables are not block-local: they leak into the enclosing rule-method's scope, exactly like the legacy for loop does. So in:

def additive
  (for x in multitive, _ in term("+"), y in additive then x + y end) | multitive
end
# desugars to:
# multitive.flat_map { |x| term("+").flat_map { |_| additive.map { |y| x + y } } }

x and y are slots in additive's method scope, shared by every closure built from that scope.

My first implementation built each rule's combinator once and cached it (@built ||= ...). That seems harmless, but with leaked variables it is not: when additive recurses, the inner activation reuses the same cached closure, i.e. the same x/y slots, and clobbers the outer activation's values.

Concrete failure

With the caching implementation, parsing 1+2*3 gives 18, and 2*3+4 gives 8:

input	correct	buggy (cached combinator)
1+2*3	7	18
1+2+3	6	9
2*3+4	10	8

Tracing 1+2*3 (the rule scope's x/y are shared across all activations):

1. additive@0: x = multitive@0 = 1.
2. term("+") matches; recurse into additive@2 — same closure, same x/y slots.
3. Inside additive@2, evaluating multitive@2 (which has the same leak problem) produces 2*3 as 3*3 = 9, and in the process the shared x slot is overwritten to 9.
4. additive@2's result, 9, is bound to the outer y.
5. But the outer x was already trampled to 9 in step 3, so the final map { |y| x + y } computes 9 + 9 = 18 instead of 1 + 6.

The outer x (= 1) is destroyed by the inner recursive call before it is read.

The fix

Rebuild the combinator on every (memo-missed) rule entry instead of caching it:

def call(input, pos)
  memo = @owner.__memo
  key = [@name, pos]
  return memo[key] if memo.key?(key)
  combinator = @body.bind(@owner).call   # fresh closure -> fresh leaked-var scope
  memo[key] = combinator.call(input, pos)
end

Each rule activation now runs the method body afresh, so additive@0 and additive@2 get separate method-invocation scopes and their x/y no longer alias. Result memoization on (rule, pos) is unchanged, so parsing stays linear; only the cheap graph-build is repeated, and at most once per (rule, pos).

When it triggers

Only when a rule is (self- or mutually) recursive and a leaked variable bound before the recursive sub-call is read after it returns. Non-recursive, single-generator rules (e.g. term(/\d+/).map { ... }) are unaffected.

Takeaway

If the fork makes the comprehension's loop variables block-local (instead of leaking like the legacy for), this whole class of aliasing bugs disappears and the per-entry rebuild can revert to a one-time cache. Leaking loop variables is the kind of legacy for wart that a brand-new construct probably shouldn't inherit — deferred/recursive execution of the desugared blocks is exactly where it bites.