How to be notified of backtracking?

[samhocevar]

I have trouble understanding the mechanism to handle backtracking when it cannot be avoided.

For instance, in examples/lua53_parse.cc I defined the following simple action to list unary operators:

template<typename R> struct action : pegtl::nothing<R> {};

template<> struct action<lua53::unary_operators>
{
    static void apply(pegtl::action_input const &in)
    {
        std::cout << "found unary operator \"" << in.string() << "\" at "
                  << in.line() << ':' << in.byte_in_line() << std::endl;
    }
};

Then parse this simple Lua snippet:

x = #l; f(#l)

… with this code:

pegtl::parse_string<lua53::grammar, action>("x = #l; f(#l)", "");

And the result is:

found unary operator "#" at 1:4
found unary operator "#" at 1:10
found unary operator "#" at 1:10

It appears that one action is executed twice because of backtracking when parsing f(#l). Is this the expected behaviour? What mechanism might the PEGTL provide to allow me to be notified that the second call to action<lua53::unary_operators>::apply() should be rolled back (and how much)?

[ColinH]

That might be a bug in our Lua grammar, the idea was to eliminate all "major" backtracking while doing the conversion from CFG to PEG, but we might not have caught all places that need to be changed.

In general, the PEGTL currently takes a "hands off" approach regarding actions and backtracking, that is, the grammar and actions have to take care of it themselves, either by not performing actions when backtracking is possible, or taking precautions to undo the actions when backtracking occurs.

The general idea is that, for performance reasons, it would always be better to design the grammar and actions in a way that minimises backtracking, and eliminates it where actions are involved. If you would find some backtracking "undo"-notification useful we could look into the possibilities...

[samhocevar]

Thanks for the explanation; if it is indeed a bug in the grammar, I will look into it and try to provide an improvement. In general I am fine with the grammar having to be carefully designed so as to prevent excessive backtracking.

I am using a modified version of that grammar in a personal project and it has proved very useful so far, thank you (actually I’m very pleased with the PEGTL in general). For now since performance is not really an issue, my local quick and dirty workaround will be to replace any problematic foo rule with pegtl::seq<pegtl::at<foo>, foo>.

[ColinH]

It is an "interference" between the rules for assignments and function calls.

The first time the unary operator is found is when f(#l) is parsed as the start of an assignment like f(#l)[foo]=42, which manages to parse the f(#l) and fails later.

The second time is when the statement is correctly parsed as a complete function call.

In other words, it was not enough that I worked across the expression rules to prevent backtracking, I also need to work across some of the statements...

[groxxda]

I'm currently working on a grammar where backtracking cannot be avoided entirely (without the lookahead hack @samhocevar posted of course) and a way to hook in notifications would be nice.
My current approach is:
I define a rule for backtracking:

struct perform_cleanup : pegtl::success {};
struct backtrack : pegtl::seq<perform_cleanup, pegtl::failure> {};

which I use where backtracking is possible like this:

struct bad1 : pegtl::sor<[real rule], backtrack> {};

I have an action for the cleanup:

template<> struct action<perform_cleanup> { 
  template<typename Input> static void apply(const Input& in, state& state) {
    state.cleanup();
  }
};

and (not needed) activate the tracer for debugging:

template<> struct control<backtrack> : pegtl::tracer<backtrack> {};

While this seems to work, there is probably room for improvement.
@ColinH do you think this could be optimized?

[ColinH]

Would it be possible to see your grammar (and have some indication as to what the actions are doing)?

[groxxda]

The grammar is here: https://github.com/groxxda/nixexpr/blob/master/expr.hh
Since it is quite long, I'll try to sum it up a bit.
The grammar should parse the nix language, here's the current flex lexer and bison parser.

Nix allows function definitions with the following syntax (among others):

• variable: <function body>

At the same time, nix allows variable references like this:

• variable

Here's the rule that matches identifiers and the action that simply converts them to an ast node.

When the parser encounters the expression var + 1, it does the following:

• Try to match a function declaration
  • Match var as an identifier and save ast::name into state.value
  • Cannot match : so this is no function definition
  • Backtrack: Clear state.value
• Try to match an arithmetic sum
  • Match var as an identifier and save ast::name into state.value
  • Match + and push a new state2 for the sum expression
  • Match 1 and save ast::number into state2.value
  • Finish the sum expression and construct ast::add into state.value like this: state.value = ast::sum(state.value, state2.value)

The reason to perform the cleanup when backtracking happens is to make this assertion happy.

This is further complicated by the fact that:

• var:xyz is not a function declaration, but an URI.
• var:[1] is not an URI but a function returning an array.

[ColinH]

This is actually rather similar to the issue with the Lua grammar, perhaps unsurprisingly so: Two different kinds of statements or expressions that start with the same rules and are disambiguated only later.

The general idea to get rid of this is to push the decision as far down as possible:

From sor< seq< A, B >, seq< A, C > > to seq< A, sor< B, C > >.

Looking at what you write this might be easy in your case - both of the possibilities you outline not only start with the same rule, they also do the same thing - "save ast::name into state.value".

However looking at the details, it all looks a bit more complicated. What you are doing with the PEGTL and in general also looks rather impressive! Do you think you can use this idea to defer the decision until you know enough?

Or does this not work well with the way you have organised everything with the ast and next types of your parsing rules?

But the initial question of this issue was "how to be notified of backtracking".

The first solution that comes to mind is to let actions to alternatively define an undo() or backtrack() method that is called whenever a rule does not match. In the simplified example here you would have action< A >::apply() do your stuff, and action< seq< A, B > >::undo() do the cleaning up when B doesn't match (and before you attempt to match seq< A, C >.

Of course this spreads the work out a bit, but the alternative would make the library more complicated:

Let action< A >::undo() do the cleaning up for action< A >::apply() by having the PEGTL call undo() on the actions [that have this method] for all sub-rules of a failed rule.

Any other ideas or suggestions?

[groxxda]

Thanks for the response, here are a few quick off-topic thoughts:

Or does this not work well with the way you have organised everything with the ast and next types of your parsing rules?

I noticed that the next type is not needed everywhere (I have a few rules with next = pegtl::success now that prove this). So I'll eventually replace the occurences of struct X : A { using next = B; }; with struct X : seq<A, B>
Also I'm not really happy with having the rule annotated with the resulting ast type, so I'll likely remove the ast sub types and introduce a trait class to determine the resulting ast type.

Do you think you can use this idea to defer the decision until you know enough?

Although I think it is possible to do this, it's likely not worth the effort (partly because of unary prefix operators).

The naive approach would be:

expression = sor<function, binary>
function = seq <name, ':', expression>
unary = seq<opt<'!'>, name>
binary = seq<unary, opt<operator, unary>>

Gets:

expression = sor<seq<name, sor<function_end, binary_end>>, seq<unary, binary_end>>
function_end = seq<':', expression>
unary = seq<opt<'!'>, name>>
binary_end = opt<operator, unary>

which means quite some code duplication..

I could use change_action to get circumvent the duplication, but it looks like a huge effort..

[groxxda]

Back to topic:

But the initial question of this issue was "how to be notified of backtracking".

I think your first suggested solution is too limited in it's usefulness to make it worth implementing.
Consider R = action<seq<A,B,C>> where action<A> and action<B> both execute state.value++ (increase an integer by one).

Now when R fails, action<seq<A,B,C>>::undo is lost, because it can't possibly know whether it should decrease state.value once or twice.

So I'd strongly prefer alternative two, where I define cleanup actions for A and B separately and PEGTL decides for me what cleanup actions should be called.

I'm not sure if PEGTL really needs support for this, because the approach I mentioned initially (make a dummy rule and associate it with an appropriate action) is a simple solution that already works.

[d-frey]

I just discussed this with Colin and I think the "simple" solution might work like this:

sor< seq< A, B >, seq< A, C > >

will apply A, then B fails and you need to revert whatever A has done. In order to do this, you would then do this in

action< B >::undo();

This might not be the most efficient solution, but it will clearly work as when B fails you already know that A succeeded.

Do you think this approach will also work for your use-cases?

[groxxda]

@d-frey:
This will not work for seq<star<A>, B> where action<A>::apply() { state.value++ }

I think to implement this cleanly, PEGTL has to call the undo function for the action whose apply function caused the state change (as many times as the apply function was called)..

[d-frey]

How about

struct store_state : success {};

and

seq< store_state, star< A >, B >

for the first part, where

action< store_state >::apply();

saves the current value of state (or just state.value),

action< B >::apply();

"commits" the transaction (discarding the saved state from store_state) and

action< B >::undo();

uses the information from the saved state to restore the previous value.

I know this is all a bit manual and lacks the convenience one would wish for. OTOH it is straight forward, fits nicely into our design space and it is very general.

[ColinH]

We are also looking into giving the whole thing a more transactional feeling, the action class could allow for three functions, begin(), success() or commit and failure() or rollback; in your example with seq<star<A>, B> you could use action<seq<star<A>, B>>::begin() to save the old counter value, action< A >::success() for the increment, and action< B >::failure() (or action<seq<star<A>, B>>:failure()?) to restore the old value...

[groxxda]

If one wants to go with saving the state, I think the better approach is a state change for the (possibly failing) intermediate steps.
This already allows rollbacks and does not clutter the state with another variable and copying (part of) the state for rollback may be more expensive than the state change.

In my opinion an actions undo function is mostly useful if it undoes that same action, especially for cases like opt<A> or even star<A>, where it would be executed the appropriate amount of times.

For now I'm quite satisfied with the solution I described above which works similar to @d-frey s suggestion and also uses a dummy success rule.

That said, I want to emphasize that PEGTL already provides perfectly good ways to achieve what I need 👍

[d-frey]

It probably depends on the state change, but yes, sometimes this is more convenient.

Going back to undo(), you can always simulate the undo() with something like:

template<typename> struct on_fail : success {};
template<typename T> struct failable : sor<T,seq<on_fail<T>,failure>> {};

using in your grammar:

failable<X>

instead of plain X and specializing for both cases:

action<X>::apply() { ... } // X succeeded
action<on_fail<X>>::apply() { ... } // X failed

This is not too bad I guess, but of course it works in a very simple way. The PEGTL is still meant to be mean and lean, so a lot of things are possible but sometimes not very convenient. We are, however, always looking for generic, powerful yet simple ways to extend the library (time being our most sparse resource). What do you think about the above helpers and the way of adding undo() in a non-intrusive way? Is it worth adding this to contrib/?

[ColinH]

Actually the additional hooks necessary for backtracking already exist, however they are called on the control class, not on the action. I have just extended examples/csv1.cc to show how this works.

Given that approach, and the work-arounds in the grammar discussed here, I will now close this issue, but feel free to continue the discussion or re-open if appropriate!