Tracing does not work on back references (version 1.3.0-dev)

There has been an experimental backref feature that implements what we think is a reasonable PEG definition of a back-reference (which is common in regex implementations).

In the development branch, in code that will become version 1.3.0, are 3 notable things:

  1. a restriction that the target pattern (e.g. foo in backref:foo) must be a pattern in the current package (which is an unfortunate consequence of the current implementation, not a part of the design of this feature);
  2. a bug fix that prevented back-references from work correctly across RPL packages; and
  3. some (scant) documentation of the backref: macro for the first time, marked as experimental.

We noticed in testing that the trace feature of Rosie does not work properly with back-references because the implementation of trace attempts to match the pattern one element at a time, which means that it will try to match the back-reference part of the pattern independently of having already matched the target pattern.

This causes the back-reference to fail to find a prior capture with the expected name (because there are no prior captures in the situation in which the back-reference is attempted).

There is no easy fix, except perhaps to forbid trace from working on patterns that have back-references.

To close this issue, we should either implement a better solution than that (such as maintaining capture history -- a tree containing a marker of the "current position"? -- across executions of the elements of a sequence), or we accept this limitation until a future time when we can rebase Rosie on top of libpexl. That future step will remove other limitations of trace as well, most notably that today a grammar looks like a single atomic pattern when tracing. That is, trace cannot today step through the rules of a grammar. But libpexl will support that.

The specific error is:


~/Projects/rosie-pattern-language/dev$ ./rosie version
1.3.0-dev
~/Projects/rosie-pattern-language/dev$ cat /tmp/g.rpl
package g

grammar
   a = "a"
in
   A = a
end

-- test A includes A.a "a"

AA = {A backref:A}

-- test AA rejects "a"
-- test AA includes A.a "aa"

~/Projects/rosie-pattern-language/dev$ ./rosie -f /tmp/g.rpl --rpl 'import g; x=g.AA' match -o jsonpp x <<< "aa"
{"data": "aa", 
 "type": "x", 
 "subs": 
   [{"data": "a", 
     "type": "A", 
     "subs": 
       [{"data": "a", 
         "type": "A.a", 
         "e": 2, 
         "s": 1}], 
     "s": 1, 
     "e": 2}], 
 "s": 1, 
 "e": 3}
~/Projects/rosie-pattern-language/dev$ ./rosie -f /tmp/g.rpl --rpl 'import g; x=g.AA' trace x <<< "aa"
...gs/Projects/rosie-pattern-language/dev/src/lua/trace.lua:303: sequence non-match differs from expected
~/Projects/rosie-pattern-language/dev$