Support name binding

[oovm]

Motivation

Name-binding refers to the name of a node in the specified syntax tree, for example = in ANTLR, field in tree-sitter.

Very useful when the name is repeated, such as distinguishing the left and right nodes of an expression.

add = {lhs = expr ~ "+" ~ rhs = epxr}

Design

pest/pest/src/iterators/pairs.rs

Lines 34 to 39 in f0a85d1

	pub struct Pairs<'i, R> {
	queue: Rc<Vec<QueueableToken<R>>>,
	input: &'i str,
	start: usize,
	end: usize,
	}

pub struct Pairs<'i, R> {
    // ...others    
    mark: Option<&'i str>
}

Then you can use a very convenient interface to find the node you want.

pairs.find_first_mark(mark: &str) -> Option<&Self>
pairs.find_marks(mark: &str)-> Iter<&Self>

The current process is more cumbersome.

let mut count_expr = 0
for pair in paris { 
    if else if else if else... 
    count_expr += 1
}

---

Specific changes

pest/pest/src/parser_state.rs

Lines 77 to 86 in f0a85d1

	pub fn state<'i, R: RuleType, F>(input: &'i str, f: F) -> Result<pairs::Pairs<'i, R>, Error<R>>
	where
	F: FnOnce(Box<ParserState<'i, R>>) -> ParseResult<Box<ParserState<'i, R>>>,
	{
	let state = ParserState::new(input);
	match f(state) {
	Ok(state) => {
	let len = state.queue.len();
	Ok(pairs::new(Rc::new(state.queue), input, 0, len))

Here to extract the value from the state:

let len = state.queue.len(); 
let mark= std::mem::take(state.mark); 
Ok(pairs::new(Rc::new(state.queue), input, 0, len, mark)) 

And add a primitive operation here:

impl<'i, R: RuleType> ParserState<'i, R> {
    pub fn mark(mut self: Box<Self>, s: &str) -> ParseResult<Box<Self>> {
        self.mark = Some(s);
        Ok(Self)
    }
}

Ideally it should be able to correspond to such code:

add = {lhs = expr ~ "+" ~ rhs = epxr}

pub fn add(state: Box<pest::ParserState<Rule>>) -> pest::ParseResult<Box<pest::ParserState<Rule>>> {
    state.rule(Rule::add, |state| {
        state.sequence(|state| {
            state
                .and_then(|state| self::expr(state))
                .and_then(|state| state.mark("lhs"))
                .and_then(|state| super::hidden::skip(state))
                .and_then(|state| state.match_string("+"))
                .and_then(|state| super::hidden::skip(state))
                .and_then(|state| self::expr(state))
                .and_then(|state| state.mark("rhs"))
        })
    })
}

Compatibility

Does not break existing features.

[NoahTheDuke]

This is a very cool idea. Python's new PEG parser has the same feature, detailed here.

[oovm]

Similarly, we can also add the branch tag

expr = {
    "(" ~ expr ~ ")"                 // branch: None
  | term ~ ("/"|"*") ~ term  #Mul    // branch: Some("Mul")
  | term ~ ("+"|"-") ~ term  #Add    // branch: Some("Add")
}

which call after or_else

[NoahTheDuke]

How would this be used? Any examples?

[oovm]

Basically, I've add the doc test for tag_branch, and here's a real world usage see: ygg-bootstrap/parse.rs

[CAD97]

This seems reasonable to me! It's a nice middle-ground between pest's fully "untyped" parse tree and something more strongly typed like the pest-ast draft or the mythical pest@3.

[tomtau]

I was looking into reviving #552 and also looked into extending the meta grammar.
The original PR #552 is fine, but extending the meta grammar is a bit tricky: 1) it seems it can't be done in a way that does not break a semver (but that should be ok, as those meta enums are now documented with a warning that this may happen, given it happened in the past), 2) interactions with the optimizer may be strange... for example, the optimizer will rewrite "a" ~ "b" to "ab", but what if there're node tags on those terminals?

@oovm @CAD97 @NoahTheDuke have you looked into or thought about the meta grammar implementation? Given how the code is written, there are a few ways:

• adding a tag field to each Expr (and its follow-up near duplicate enums) variants (yuck?)
• rewriting those generator methods that operate on Expr (or other related enums) to use some wrapper struct (TaggedExpr) instead
• a bigger logical refactoring, e.g. to use something like https://github.com/guygastineau/rust-trees-that-grow
• adding a new Tag variant to Expr, propagating it to related enums and patching the generator to look for that

I tried the first one but it's likely a no-go... I'm thinking the last may be the path of least resistance, as the explicit variant may fix up the potential issues with the optimizer... anyway, any thoughts? or should this be left for a simpler v3 grammar/implementation?

[NoahTheDuke]

This change (however it's accomplished) is big enough that we should probably do a semver bump, so that feels okay to me. I left some comments in #832 about your implementation.