Input wanted: design and implement a proper API for code blocks

[zevv]

Here's a request to all NPeg users: I'm looking for some ideas and feedback for the proper design of the API for grammar code blocks. At this time the available functions feel ad hoc and scattered, and I don't dare to call this v1.0 before a better interface is in place.

Here is a list of things a code block capture can do, and how this works now:

• Access captures: when a code block executes, all closed captures that were made inside the rule, and the code block capture itself are available to the code block as the variable capture which is of type seq[Capture]. The Capture object has a few public members that can be used from the code block: s is the captured string and si is the index into the original subject where the capture was matched. The capture strings s are also accessible through a sugar macro that rewrites the code block as $n:

  • capture[0] or $0 is the total capture of the rule
  • capture[1..] or $1 are the explicit string captures inside the rule

• Force a rule to fail:

  • code blocks have access to a proc fail() which will cause the match to fail - this can be used to validate matches with Nim code, for example to check integer ranges, enum values, or symbols that were captured earlier.
  • code blocks have acecss to a proc validate(b: bool), which is nothing more then if not b: fail()

  For example:

uint8 <- >Digit[1..3]:                                                     
  let v = parseInt($a)                                                         
  validate v>=0 and v<=255                                                   

• Perform matching in Nim code: the internal match state is implicitly available to the code block capture, which can (ab)use that to do matching in Nim code: the code block can see and adjust the match index, and indicate success or failure, for example:

  let p = peg foo:
    foo <- "ba" * die * "da"
    die <- 0:
      if si < s.len-3 and if cast[string](s[si..si+2]) == "die":
        si += 3
      else:
        fail()

  echo p.match("badieda")

All of the above features were introduced in NPeg one at a time, growing the API lacking a proper design.

My question: does the above feel as kludgy as I think it is, or is it fine as it is now? Any ideas for improvement or what this should look like?

[sealmove]

I'd like a hook which allows code execution when a rule is looked up.
This way you can control when your code will be executed.

let p = peg foo:
  onLookUp:
    # (...)
  onMatch:
    # (...)

[zevv]

Yeah, this is one of my nitpicks as well. I usually solve this with always-match rules in the grammar like so:

foo <- fooStart * fooBody * fooEnd
fooStart <- 0:
  echo "start"
fooEnd:
  echo "done"

I do like your idea, but I'm afraid it will add a lot of noise for the cases where only the match code block is required. Maybe with some macro magic we can make it so that wihout explicit hook the block acts like the onMatch, keeping backwards compatibility, and only when there are hooks defined, they are used. Let me see how that would fit in.

[Varriount]

Suggestions:

• Rather than expose parser state as multiple variables, expose it as a single variable. This would be consistent with how the capture data is presented. Alternately, the parser state could be represented as a variable, and the capture would be a field in the parser state.
• For captures in code blocks, only create the captured string on demand.
• Use more descriptive names than s, si, etc. for variables and members.
• Allow the code block to optionally use return statements to indicate whether a match succeeded or failed. That being said, such a change might require that all code blocks have a return statement.

Note that I haven't really evaluated the feasibility for the above suggestions. It's been a while since I've looked at Npeg's implementation, and I wanted to get down these thoughts while they were fresh in my mind.

[zevv]

Quoting Varriount (2019-12-03 15:59:48)

- Rather than expose parser state as multiple variables, expose it as a single variable. This would be consistent with how the capture data is presented. Alternately, the parser state could be represented as a variable, and the capture would be a field in the parser state.

Yeah, I have moved stuff to and from that model a few times. The state itself is in an object, but everything is moved to local variables during the match for performance reasons. I'm also not sure how to expose the subject string in a different variable, as that would require a copy of the subject, which is potentially large. I shall do some tests with shallow() to see if that helps.

- Use more descriptive names than `s`, `si`, etc. for variables and members.

Sure, the current variables are bad but short because of the implementation. the also have a high chance of clashing with code in the blocks, this already happens to me too often.

- Allow the code block to optionally use return statements to indicate whether a match succeeded or failed. That being said, such a change might require that all code blocks have a return statement.

Nope, it will just return the default value for the type then. I did some tests with making the code blocks procs, but I can not find a way to keep the compiler happy with captures and closers and gc safety. I alreday do some nasty tricks with injects and identifiers to pass stuff around, and i was hoping someone who really understands this all better would one day point me out how to actually do that proper

Note that I haven't really evaluated the feasibility for the above suggestions. It's been a while since I've looked at Npeg's implementation, and I wanted to get down these thoughts while they were fresh in my mind.

No problem, any input is valuable. It will take me a few tries probably to get this right anyway, all of the above are good points. thanks!

…

-- :wq ^X^Cy^K^X^C^C^C^C

[Varriount]

Yeah, I have moved stuff to and from that model a few times. The state itself is in an object, but everything is moved to local variables during the match for performance reasons. I'm also not sure how to expose the subject string in a different variable, as that would require a copy of the subject, which is potentially large. I shall do some tests with shallow() to see if that helps.

Could a "subject" procedure be made for the capture object, allocates the captured string when accessed? Due to UFCS, it would still look like attribute access:

let s = capture.subject

Nope, it will just return the default value for the type then. I did some tests with making the code blocks procs, but I can not find a way to keep the compiler happy with captures and closers and gc safety.

What about passing in the parser state and capture object as parameters, and marking the function as both inline and giving it a regular calling convention?

proc match(s: string) =
  proc inner(parser: Parser, capture: Capture): bool {.inline, nimcall.} =
    discard

You might be able to get rid of the inline pragma, since compilers are usually pretty good about inlining small functions anyway.

[zevv]

What about passing in the parser state and capture object as parameters, and marking the function as both inline and giving it a regular calling convention?

Seems like a sane approach, I'll give it another try. Thanks for pointing that out!

…

-- :wq ^X^Cy^K^X^C^C^C^C

[shumy]

I suggest to use the return of the code block to pass a parsed value to the upper rule/capture.
Add a compiler flag to avoid code blocks to execute when they fail.

This is essential for anyone to construct a custom AST without using hacks to catch the proper tree context. Without this, code blocks are useless when trying to construct an AST.

Use a tree structure to cache captures (instead of the list you are using), so you can easily remove entire failed branches and detect the tree context. Execute code blocks when the full match is completed and ok.

[shumy]

A better alternative to the compiler flag can be: pass a object to the code block where you can set two callback functions.

1. validate: executed on every match like now. And where you can use fail() and validate().
2. commit: executed on commit, when the full match is done. You can set the result value to pass a parsed object to the upper rule, like a custom object, instead of using push() with limited strings.

And, add an option in the parser to disable backtracing for languages that don't require it. You can execute both callbacks in the same pass in this option.

[zevv]

I suggest to use the return of the code block to pass a parsed value to the upper rule/capture.

Do you mean when captures are nested? Because apart from that there is no apparent upper/lower or parent/child relationship between rules at this time.

Add a compiler flag to avoid code blocks to execute when they fail.

But what if we want to use a code block to do the validation and pass/fail from it's result?

This is essential for anyone to construct a custom AST without using hacks to catch the proper tree context. Without this, code blocks are useless when trying to construct an AST.

Let's call it "suboptimal", not useless - see the examples with perfectly functional parsers.

Use a tree structure to cache captures (instead of the list you are using), so you can easily remove entire failed branches and detect the tree context.

But what would dictate the tree structure? The input is just a linear stream, where do the relationships come from?

Execute code blocks when the full match is completed and ok.

See above: code blocks have multiple uses, one of those is using Nim code to do manual parsing and let the parser fail or succeed from there.

I feel you are looking for a way to let NPeg have a sense of AST in its parser internally, but at this time the parsing is just sequential: seq-of-chars go in, seq-of-captures comes out. Structure is added by the user of NPeg by building AST in captures. Note that NPeg did have this kind of functionality in the past (see below), but I decided to deprecate this - it proved not flexible enough because the order of nodes in the stream often does not match the order of the nodes as they should end up in the AST tree, thus the user ends up with a generic tree where things are dangling in the wrong place.

Documentation of deprecated AST (Abstract Syntax Tree) captures

Note: AST captures is an experimental feature, the implementation or API might
change in the future.

NPeg has a simple mechanism for storing captures in a tree data structure,
allowing building of abstract syntax trees straight from the parser.

The basic AST node has the following layout:

ASTNode* = ref object                                                       
  id*: string           # user assigned AST node ID 
  val*: string          # string capture                                  
  kids*: seq[ASTNode]   # child nodes                                      

To parse a subject and capture strings into a tree of ASTNodes, use the
A(id, p) operator:

• The A(id, p) operator creates a new ASTNode with the given identifier
• The first string capture (>) inside pattern p will be assigned to the
  val field of the AST node
• All nested ASTnodes in pattern p will be added to the nodes kids seq.

The following snippet shows an example of creating an AST from arithmetic
expressions while properly handling operator precedence;

type Kind* = enum kInt, kAdd, kSub, kMul, kDiv

let s = peg "line":
  line     <- exp * !1
  number   <- A(kInt, >+Digit)
  add      <- A(kAdd, term * '+' * exp)
  sub      <- A(kSub, term * '-' * exp)
  mul      <- A(kMul, factor * '*' * term)
  divi     <- A(kDiv, factor * '/' * term)
  exp      <- add | sub | term
  term     <- mul | divi | factor
  factor   <- number | '(' * exp * ')'

let r = s.match("1+2*(3+4+9)+5*6")
let ast = r.capturesAST()
echo ast

This will generate an AST tree with the following layout:

       +
      / \
     1   + 
        / \
       /   \
      /     *
     *     / \
    / \   5   6
   2   +
      / \
     3   +
        / \
       4   9

[zevv]

A better alternative to the compiler flag can be: pass a object to the code block where you can set two callback functions.
1. validate: executed on every match like now. And where you can use fail() and validate().

2. commit: executed on commit, when the full match is done. 

That's not a bad idea, and with a bit of syntactic sugar this could be nicely wrapped up in some blocks instead of explicit callbacks. Something like:

import npeg

let p = peg "flop":

  flop <- one * two | one * three

  one <- '1':
    match:
      echo "one?"
    commit:
      echo "one!"

  two <- '2':
    echo "two"

  three <- '3':
    echo "three"

And, add an option in the parser to disable backtracing for languages that don't require it. You can execute both callbacks in the same pass in this option.

You can set the result value to pass a parsed object to the upper rule, like a custom object, instead of using push() with limited strings.

This is still a bit of a mismatch with how NPeg works at this time: there is no concept of an "upper rule" - all rules are sequential and there is no tree representation. In the message above you can see this could work by making the tree explicit in the syntax, but in practice this proves of limited use because the generated AST can only mirror the exact order of the input stream.

[shumy-tools]

I didn't know about the A operator, but I don't believe it's a good solution because it doesn't allow for arbitrary code execution and for custom ASTs.

After analyzing the NPeg code I believe I have a more concrete proposal with no impact on the current spec. But you have to fill and check the details.

1. First, remove capStack and CapFrame. You need a stack at the rule level instead, with ruleStack and RuleFrame. fixCaptures and collectCaptures are code hacks because you're squishing a square into a circle. The RuleFrame stores a sequence of captures: seq[Capture] and the context capture ctx: Capture. It also has error: string and ok: bool fields for error handling.

2. You need something like opRuleOpen and opRuleClose to replace those opCapOpen and opCapClose. And just have a opCapture to replace the execution of a captured rule.

3. I propose a set of context functions with the signatures:

template fail(msg = "")
template check(expr: bool, msg = "")
template capture[T](`s`: T)

Deprecate the old ones, but they should still work.

• fail sets the RuleFrame.error and RuleFrame.ok.
• check conditionally sets the RuleFrame.error and RuleFrame.ok.
• capture sets the RuleFrame.ctx.

4. The Capture can accept values for T or seq[T].

5. Expose captured parameters with internal casts, ex: %x or something else.

6. Expose a new method ast() for the parser that returns the top level capture (T or seq[T]) .

Note that, the ruleStack is somehow redundant, since its boundaries map to rule calls, so we could use the program stack instead. However, since there are inlined rules, it's better to have it.

Grabbing the doc example:

type MyNode* = object                                                       
  key*: string
  val*: int

let parser = peg("pairs"):
  pairs <- >pair * *(',' * >pair) * !1:
    # do something with the captured result. Ideally it should be of type seq[MyNode]
  word <- +Alpha
  number <- +Digit
  pair <- >word * '=' * >number:
    let node = MyNode(key: %1, val: parseInt(%2))
    capture(node)

The algorithm execution goes like:

1. At opRuleOpen push a RuleFrame to ruleStack
2. In each opCapture in the rule frame, grab the captured result (evaluated from the rule) and add it to the RuleFrame.captures. Only if the rule has not failed.
3. At opRuleClose execute the code block where %x vars are mapped to RuleFrame.captures. Pop the RuleFrame and return RuleFrame.ctx. If ctx has no value, return the RuleFrame.captures. If the rule has no captures, it's considered a PEG leaf, return the respective string value.

Improvements:

• It's compatible with current API.
• Failed rules will be automatically discarded. The final custom AST is correct.
• Outputs a validated and custom AST model.
• Seamless mapping between PEG grammar and internal structures. No fixCaptures and collectCaptures code hacks. You just pass the captures as it is. I expect performance improvements, since fixCaptures looks like an expensive execution.

Challenges:

• Providing the correct cast type for %x parameters may be challenging. Ideally it should return the expected type, but may not be possible.
• Ideally, a rule of "ordered choices" should return an enum with the expected types, but may not be possible.
• I propose a first version where casts have to be done by the user.

[zevv]

Thanks for giving this a good think. I'll have to go through this a few times and properly digest it, I'll probably be back with questions.

[Varriount]

@shumy-tools One thing I would like to point out is that what one might consider the optimal layout/ruleset for a grammar (in terms such as readability, performance, etc.) may not match up with their AST (also, there are uses for NPeg other than AST building). I don't imagine this to be too common an occurrence, but it is possible.