Rule failure can leave detritus on the capture stack

[jshprentz]

Summary

When a grammar rule invokes a function before recognizing any input, the subsequent failure of the rule does not restore the capture stack to its state before the rule was attempted.

Example

This example grammar recognizes lines of digits and returns a (reversed) list of the sums of digits.

• Digit adds the integer value of a digit to the sum on the capture stack.
• Line initializes a line's sum on the capture stack and recognizes one or more digits followed by a newline.
• Sums recognizes one or more lines.

import Xpeg

parser =
  peg Sums, dump_graph: true do
    Digit <- int({'0'..'9'}) * fn [digit, sum | stack] -> [digit + sum | stack] end

    Line <- fn stack -> [0 | stack] end * +Digit * '\n'

    Sums <- +Line
  end

The parser builds as expected.

Digit o──{"0".."9"}─»─fn()──o         
                                      
Line o──fn()─»─┬─[Digit]─┬─»─~c"\n"──o
               ╰────«────╯            
                                      
Sums o──┬─[Line]─┬──o                 
        ╰────«───╯                    

The parser recognizes sample input and computes digit sums correctly, leaving them on the capture stack.

Problem: The capture stack includes an extra 0, apparently from the final, failed attempt to try rule Line.

input = """
1234
56
7
"""

match(parser, input)

%{time: 0.0, result: :ok, rest: [], captures: [0, 7, 11, 10], userdata: nil, match_len: 10}

Environment and Versions

Tested in Livebook running on Windows 11.

• Xpeg was retrieved from GitHub at 2023-12-03 17:39Z: {:xpeg, git: "https://github.com/zevv/xpeg"}
• Elixir v1.15.7
• Livebook v0.11.4