Struct TokenTree

pub struct TokenTree { /* private fields */ }

A tree of token streams generated from a GLSL source string.

The tree represents all conditional compilation branches. Call the root(), evaluate() or with_key() method to parse an abstract syntax tree with the selected conditional branches into a ParseResult.

Examples

For a fully detailed example on how to use this struct to create an AST, see the documentation for the parse_from_str() function.

Why is this necessary?

Conditional compilation is implemented through the preprocessor, which sets no rules as to where conditional branching can take place, (apart from the fact that a preprocessor directive must exist on its own line). This means that a conditional branch could, for example, completely change the signature of a program:

 1│ void foo() {
 2│
 3│     int i = 5;
 4│
 5│     #ifdef TOGGLE
 6│     }
 7│     void bar() {
 8│     #endif
 9│
10│     int p = 0;
11│ }

In the example above, if TOGGLE is not defined, we have a function foo who’s scope ends on line 11 and includes two variable definitions i and p. However, if TOGGLE is defined, the function foo ends on line 6 instead and only contains the variable i, and we have a completely new function bar which has the variable p.

This technically can be representable in the AST, it’s just that it would look something like this:

Root(
    Either(
        (
            Function(
                name="foo"
                start=1
                end=11
                contents(
                    Variable(name="i" value=5)
                    Variable(name="p" value=0)
                )
            )
        ),
        (
            Function(
                name="foo"
                start=1
                end=6
                contents(
                    Variable(name="i" value=5)
                )
            ),
            Function(
                name="bar"
                start=7
                end=11
                contents(
                    Variable(name="p" value=0)
                )
            ),
        )
    )
)

Notice how this AST is effectively Either(AST_with_condition_false, AST_with_condition_true). This is because the function foo could potentially be split in the middle, but an AST node cannot have multiple end points, which means that we can’t include both permutations within the function node; we need separate function nodes instead. And since we have two separate possibilities for foo, we need to branch in the node above foo, which in this example is effectively the root node.

It is arguable whether such a representation would be better than the current solution. On one hand all possibilities are within the single AST, but on the other hand such an AST would quickly become confusing to work with, manipulate, and analyse in the scenario of complex conditional branching.

The main reason this option wasn’t chosen is because it would immensely complicate the parsing logic, and in turn the maintainability of this project. As with all recursive-descent parsers, the individual parsing functions hold onto any temporary state. In this case, the function for parsing functions holds information such as the name, the starting position, the parameters, etc. If we would encounter the conditional branching within this parsing function, we would somehow need to know ahead-of-time whether this conditional branch will affect the function node, and if so, be able to return up the call stack to split the parser whilst also somehow not losing the temporary state. This would require abandoning the recursive-descent approach, which would greatly complicate the parser and make writing & maintaining the parsing logic itself a convoluted mess, and that is not a trade-off I’m willing to take.

This complication occurs because the preprocessor is a separate pass ran before the main compiler and does not follow the GLSL grammar rules, which means that preprocessor directives and macros can be included literally anywhere and the file may still be valid after expansion. In comparison, some newer languages include conditional compilation as part of the language grammar itself. In Rust for example, conditional compilation is applied via attributes to entire expressions/statements, which means that you can’t run into this mess where a conditional branch could split a function mid-way through parsing. GLSL unfortunately uses the C preprocessor, which results in the approach taken by this crate being necessary to achieve 100% specification-compliant behaviour.

Note that macros can actually be correctly expanded within the same pass as the main parser without introducing too much complexity, it’s just that conditional compilation can’t.

Implementations

impl TokenTree

pub fn root(&self, syntax_highlight_entire_source: bool) -> ParseResult

Parses the root token stream; no conditional branches are included.

Whilst this is guaranteed to succeed, if the entire source string is wrapped within a conditional block this will return an empty AST.

Syntax highlighting

The syntax_highlight_entire_source parameter controls whether to produce syntax tokens for the entire source string, rather than just for the root tokens. This involves parsing all conditional branches in order to produce all the syntax highlighting information. Whilst the implementation of this functionality uses the smallest possible number of permutations that cover the entire source string, if there are a lot of conditional branches that can result in the token tree being parsed many times which may have performance implications.

The actual syntax highlighting results are based off the chosen permutations which cannot be controlled. If you require more control, you must manually parse the relevant permutations and collect the tokens yourself.

If there are no conditional branches, this parameter does nothing.

Examples

For a fully detailed example on how to use this method to create an abstract syntax tree, see the documentation for the parse_from_str() function.

pub fn evaluate( &self, syntax_highlight_entire_source: bool, ) -> (ParseResult, Vec<usize>)

Parses the token tree by including conditional branches if they evaluate to true.

Whilst this is guaranteed to succeed, if the entire source string is wrapped within a conditional branch that fails evaluation this will return an empty AST. This method also returns the evaluated key.

Syntax highlighting

The syntax_highlight_entire_source parameter controls whether to produce syntax tokens for the entire source string, rather than just for the included conditional branches. This involves parsing all conditional branches in order to produce all the syntax highlighting information. Whilst the implementation of this functionality uses the smallest possible number of permutations that cover the entire source string, if there are a lot of conditional branches that can result in the token tree being parsed many times which may have performance implications.

The actual syntax highlighting results are based off the chosen permutations which cannot be controlled. If you require more control, you must manually parse the relevant permutations and collect the tokens yourself.

If there are no conditional branches, or the only conditional branches that exist are also evaluated as true and included in the running of the parser, this parameter does nothing.

Examples

For a fully detailed example on how to use this method to create an abstract syntax tree, see the documentation for the parse_from_str() function.

pub fn with_key( &self, key: impl AsRef<[usize]>, syntax_highlight_entire_source: bool, ) -> Result<ParseResult, ParseErr>

Parses a token tree by including conditional branches if they are part of the provided key.

This method can return an Err in the following cases:

• The key has a number which doesn’t map to a controlling conditional directive.
• The key has a number which depends on another number that is missing.

Syntax highlighting

The syntax_highlight_entire_source parameter controls whether to produce syntax tokens for the entire source string, rather than just for the selected conditional branches. This involves parsing all conditional branches in order to produce all the syntax highlighting information. Whilst the implementation of this functionality uses the smallest possible number of permutations that cover the entire source string, if there are a lot of conditional branches that can result in the token tree being parsed many times which may have performance implications.

The actual syntax highlighting results are based off the chosen permutations which cannot be controlled. If you require more control, you must manually parse the relevant permutations and collect the tokens yourself.

If there are no conditional branches, this parameter does nothing.

Examples

For a fully detailed example on how to use this method to create an abstract syntax tree, see the documentation for the parse_from_str() function.

pub fn get_all_controlling_conditional_directives( &self, ) -> Vec<(Conditional, Span)>

Returns a vector of all controlling conditional directives in the tree.

The return value consists of:

• 0 - The conditional directive type. This cannot be Conditional::End.
• 1 - Span of the directive.

Note that the first controlling conditional directive (index of 1) is at the beginning of this vector (index 0), so an offset must be performed.

pub fn create_key(&self, chosen_conditional_directive: usize) -> Vec<usize>

Creates a new key to access the specified controlling conditional directive.

This method takes the index (of the chronological appearance) of the controlling conditional directive (#if/#ifdef/#ifndef/#elif/#else), and returns a key that reaches that conditional branch. The new key contains the minimal number of prerequisite branches necessary to reach the chosen directive.

pub fn add_selection_to_key( &self, existing_key: &Vec<usize>, chosen_conditional_directive: usize, ) -> Vec<usize>

Modifies an existing key to access the specified controlling conditional directive.

This method keeps all existing conditional branches as long as they don’t conflict with the newly chosen branch.

pub fn remove_selection_from_key( &self, existing_key: &Vec<usize>, removed_conditional_directive: usize, ) -> Vec<usize>

Modifies an existing key to remove access to the specified controlling conditional directive.

This method keeps all existing conditional branches as long as they don’t depend on the specified to-remove branch.

pub fn contains_conditional_directives(&self) -> bool

Returns whether the source string contains any conditional directives.