Trait SyntaxSession 

pub trait SyntaxSession<'code>: TokenCursor<'code, Token = <Self::Node as Node>::Token> {
    type Node: Node;

    // Required methods
    fn descend(&mut self, rule: NodeRule) -> NodeRef;
    fn enter(&mut self, rule: NodeRule) -> NodeRef;
    fn leave(&mut self, node: Self::Node) -> NodeRef;
    fn lift(&mut self, node_ref: &NodeRef);
    fn node_ref(&self) -> NodeRef;
    fn parent_ref(&self) -> NodeRef;
    fn failure(&mut self, error: SyntaxError) -> ErrorRef;
}

A communication channel of the syntax tree parsing process.

Lady Deirdre distinguishes two independent sides of the syntax parsing process:

• The parsing environment side (e.g., Document) that manages the parsing input (tokens), and manages the parsing output (syntax tree).

• The parsing algorithm implementation side (via the Node::parse function).

Both sides unaware of each other, and they use SyntaxSession for intercommunication.

1. Whenever the parsing environment side wants to parse a particular node of the syntax tree, it gives control flow to the parser by providing it’s own implementation of the SyntaxSession to the Node::parse function.

2. The parse function reads particular tokens of the token input stream and advances the token cursor using SyntaxSession’s functions.

3. If the parse algorithm needs to further descend into the syntax tree, it calls SyntaxSession::descend function returning control flow back to the parsing environment side.

4. The parsing environment side decides whether to give control flow to the Node’s parse function again, continuing recursive descending, or returning a result from its own cache.

Since both sides of the parsing process are isolated from each other, it opens up a lot of implementation configurations.

As the user of the SyntaxSession instances, you can

• Implement a custom parser that inherently suit the needs of both one-time parsing of the entire file and the incremental reparsing process.

• Adopt a 3rd party parsing library to Lady Deirdre by adopting its interface to the SyntaxSession interface.

• Implement a parsing algorithm of almost any programming language as long as its grammar does not surpass a class of the context free grammars with unlimited lookahead.

In particular, the Node derive macro implements Node’s parse function for LL(1) grammars, but you are free to implement your own parsers and alternative recursive-descending parsing libraries utilizing the SyntaxSession interface.

As the author of the SyntaxSession implementations

You have control over arbitrary programming language parser steps without the need to know the details of the language’s grammar.

Therefore, you can implement a wide set of the parsing environments with different capabilities.

In particular, Lady Deirdre provides the following parsing environments through custom implementations of the SyntaxSession trait:

• The immutable Document and the ImmutableSyntaxTree objects provide one-time parsing capabilities, always returning control-flow back to the Node’s parse function when the function is trying to descend. The performance characteristics of this approach are close to ordinary non-incremental parsers.

• The mutable Document and the MutableUnit have their own reusable caches of the syntax tree nodes that they utilize during incremental reparsing by returning previously parsed node cache whenever possible when the Node’s parse function is trying to descend.

• Node::debug function under the hood uses special implementation of the SyntaxSession trait that does not store any nodes in the syntax tree but instead just prints parser’s actions to the terminal for debugging purposes.

• ParseTree tracks parser’s interactions with the SyntaxSession to reconstruct concrete parsing trees.

Parsing algorithm considerations

When implementing the Node::parse function, several considerations should be taken into account:

1. The parsing algorithm should handle a context-free grammar. Each rule of the grammar should be parseable from any arbitrary token sequence, and the algorithm should not rely on parsing rules applied previously.

2. The Node::parse function must be infallible regardless of the input token sequence or the rule parameter. If the token sequence provided to the parser by the SyntaxSession does not fit the parsing rule at any step (including the first step) of the rule’s algorithm, the algorithm must attempt to recover from syntax errors by skipping or ignoring parts of the input tokens and by reporting syntax errors using the SyntaxSession::failure function.

3. In the end, the Node::parse function must advance the SyntaxSession token cursor by consuming at least one token from the input sequence, and it must return an instance of the Node that corresponds to the requested rule.

Parse rules

Both Node::parse and the SyntaxSession::descend functions have a rule parameter of the NodeRule type, which is an arbitrary number used to distinguish between concrete parsing rules.

In the context of parsing rules:

1. Rule 0 (ROOT_RULE), denoting the root node of the syntax tree, should be used only once per the entire parsing process, as there can only be one root in the syntax tree. Therefore, the Node::parse function itself should never call descend or enter functions with the rule 0.

2. Rule u16::MAX (NON_RULE) is a reserved rule that denotes an invalid rule, indicating a rule that does not parse anything. Therefore, it should never be supplied to either the Node::parse function or any of the SyntaxSession functions that accept a NodeRule type.

3. Any other rule number in a range of 1..u16::MAX is a valid rule uniquely denotes a parsing rule of a particular syntax tree node.

4. The SyntaxSession trait is unaware of the mapping between these numbers and the node types upfront. They are determined by each implementer of the programming language parsers. However, the SyntaxSession can rely on the fact that passing the same rule number to the Node::parse function would produce a node of the same type.

Cache control

The parser algorithm typically descends into the sub-rules of the currently parsed rule by calling the SyntaxSession::descend function, which gives control flow to the SyntaxSession and leaves the decision about the node’s caching to the SyntaxSession implementation.

The nodes computed this way are called primary nodes.

Alternatively, the algorithm could compute a sub-rule in place, without returning control flow back to the SyntaxSession.

These nodes are called secondary nodes. As the secondary nodes are computed in places, they cannot be cached by the SyntaxSession.

Whenever the parser starts in-place parsing of the secondary node it should call the SyntaxSession::enter function specifying the node’s parsing rule.

When the the parsing finishes, the parser should call the SyntaxSession::leave function specifying an instance of the Node as a product of this sub-rule.

Nodes and rules nesting

The SyntaxSession tracks rules and their products (Nodes) nesting.

It is the parser’s implementor responsibility to balance the enter and leave functions properly when parsing the secondary nodes in place, always leaving the nodes entered before.

When the algorithm uses the descend function, the nesting process is controlled by the SyntaxSession implementation.

SyntaxSession::node_ref returns a NodeRef of the node currently being parsed. Using this function, you can fetch the node’s reference while it is being parsed.

SyntaxSession::parent_ref returns a NodeRef reference of the parent rule’s node.

The parsing algorithm cannot access either of the syntax tree node instances during the parsing process, but it can use these NodeRef references to set up the parent_ref and the node_ref values of the resulting node instance.

These values of the Node instance establish back references from the child nodes to their parents and are useful for the resulting syntax tree ascending traverse.

Left recursion

To handle left recursion, the parser could utilize either lookahead capabilities of the SyntaxSession or to use the node lifting feature.

For example, to parse infix expressions such as a + b, a * b, or just a, where the binary operator is not known upfront or could absent, you can descend into the operand parsing rule first, receiving its NodeRef reference.

Then, if the parser encounters an operator token, you can enter the corresponding binary operation rule and immediately call the lift function, providing the operand’s NodeRef. Then, parse the rest of the expression normally.

The lift function would “transplant” the operand’s node parsed outside of the operator’s rule to the context of the operator’s rule, rearranging operand’s node nesting.

Tokens access

The SyntaxSession trait is a super-trait of the TokenCursor trait.

Functions of the TokenCursor grant access to the current state of the token sequence being parsed.

The TokenCursor::advance and the TokenCursor::skip functions advance the SyntaxSession parsing cursor, consuming corresponding tokens.

The access functions of the TokenCursor grant potentially unlimited lookahead capabilities.

The SyntaxSession could track the lookahead distance used by the parsing algorithm. The lookahead distance could limit the underlying parsing environment caching capabilities.

Therefore, the parser’s implementor should prefer to limit the lookahead whenever possible.

Safety and Panic

The SyntaxSession trait and all of it’s functions are safe.

Violations of the above specification are not undefined behavior, but the failure to follow the specified contract could lead to bugs and panics depending on the implementation.

Required Associated Types

type Node: Node

Specifies a type of the Node that is currently being parsed.

Required Methods

fn descend(&mut self, rule: NodeRule) -> NodeRef

Instructs the parsing environment to parse the parsing rule denoted by the rule parameter starting from the current token.

The valid values of the rule are any values within the NodeRule range except the ROOT_RULE and the NON_RULE.

Returns a NodeRef reference of the node inside the SyntaxTree that would be parsed by this rule and consumes the sequence of tokens required to apply the rule.

fn enter(&mut self, rule: NodeRule) -> NodeRef

Begins parsing of the parsing rule denoted by the rule parameter from the current token.

The valid values of the rule are any values within the NodeRule range except the ROOT_RULE and the NON_RULE.

Returns a NodeRef reference of the node inside the SyntaxTree that will be placed to the syntax tree when the rule parsing finishes.

Each enter function must be paired with the leave function that finises the rule.

After entering into the rule parser, the parsing algorithm must consume at least one token directly or indirectly by entering another sub-rule.

fn leave(&mut self, node: Self::Node) -> NodeRef

Completes parsing of the rule started previously by the enter function.

The node parameter specifies rule’s parsing result.

Returns a NodeRef reference of the node inside the SyntaxTree.

fn lift(&mut self, node_ref: &NodeRef)

Reinterprets the previously parsed sibling node of the current node as the current node’s child.

See the Left recursion section of the parsing process specification for details.

fn node_ref(&self) -> NodeRef

Returns the NodeRef reference of the node inside the SyntaxTree being parsed by the current parsing rule.

fn parent_ref(&self) -> NodeRef

Returns the NodeRef reference of the node inside the SyntaxTree being parsed by the parental parsing rule.

If the current rule is the root, this function returns NodeRef::nil.

fn failure(&mut self, error: SyntaxError) -> ErrorRef

Reports a syntax error occur during the syntax recovery.

Returns an ErrorRef reference of the error object inside the SyntaxTree.

The SyntaxSession implementation may decide to ignore the provided error object. In this case, the failure function returns ErrorRef::nil.

Dyn Compatibility

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors