CST location information

[bd82]

Released in 4.7.0
See: https://sap.github.io/chevrotain/docs/guide/concrete_syntax_tree.html#cstnodes-location

---

A CstNode currently contains all the data needed to compute it's location information as each terminal (IToken) contains it's own location information.

However the "aggregated" information is not available on the CstNode itself.
For example if we want to know what is the startOffset of a specific CstNode we must:

• first traverse all it's children
• Filter out only the Terminal children.
• Find the smallest startOffset of the Terminal Children.

Perhaps Chevrotain could provide a toggle-able feature to perform this location collection on the fly.

export interface CstNode {
    readonly name: string
    readonly children: CstChildrenDictionary
    readonly recoveredNode?: boolean
    /**
     * Only relevant for [in-lined](http://sap.github.io/chevrotain/docs/guide/concrete_syntax_tree.html#in-lined-rules) rules.
     * the fullName will **also** include the name of the top level rule containing this nested rule.
     */
    readonly fullName?: string
    readonly location: { 
          startOffset:number,
          startLine:number,
          // ...
      }
}

Elements to Consider:

• Performance impact both when the feature is enabled and disabled.
• Should the location information collected match the Lexer positionTracking option?

[kristianmandrup]

Awesome!! I'll gladly help implement or try out this feature shortly :)

[kristianmandrup]

I would think the design could be something like this:

class Parser {
    // ...
    constructor(
        tokenVocabulary: TokenVocabulary,
        config: IParserConfig = DEFAULT_PARSER_CONFIG
    ) {
        const that: MixedInParser = this as any
        that.initErrorHandler(config)
        that.initLexerAdapter()
        that.initLooksAhead(config)
        that.initRecognizerEngine(tokenVocabulary, config)
        that.initRecoverable(config)
        that.initTreeBuilder(config)
        that.initContentAssist()

        // location info trait (returns immediately if locationInfo is NONE)
        that.initLocationInfoDecorator()

        this.ignoredIssues = has(config, "ignoredIssues")
            ? config.ignoredIssues
            : DEFAULT_PARSER_CONFIG.ignoredIssues
    }
  // ...
}

enum LocationInfo = {
  NONE,
  FULL
}

export interface IParserConfig {
  // ...
  locationInfo: LocationInfo
}

export class LocationInfoDecorator {

    initLocationInfoDecorator(this: MixedInParser, config: IParserConfig) {
      if (config.locationInfo === LocationInfo.NONE) return

      // initialize
    }

     public computeLocationInfo() {
       // ... smart compute
       // using memoized (cached) locations to achieve linear visits O(n) and thus good performance
     }
}

[bd82]

https://gist.github.com/kristianmandrup/afbd8382e7a172aa8945b6023e3b3e8e

[bd82]

I don't think we need a new trait to compute the location info.
We can introduce this code in the cstPostTerminal method.
https://github.com/SAP/chevrotain/blob/master/packages/chevrotain/src/parse/parser/traits/tree_builder.ts#L83-L91

because we can access the current CstNode being build there.

• https://github.com/SAP/chevrotain/blob/master/packages/chevrotain/src/parse/parser/traits/tree_builder.ts#L83-L91

Note:

• We should only do this computation when the nodes location feature is enabled.
  • See how we "assemble" the parser with the relevant methods to avoid conditionals in "hot spots" in the code when certain features are disabled.
• We may want to enable this feature by default depending on its performance impact.
• We need to make sure it does not get "broken" when error recovery is active.
  • SingleTokenInsertion heuristic could insert a virtual token with location information that is "NaN"

[kristianmandrup]

Thanks. I will have another go next week using your suggestions, unless you beat me to it. Was is your estimate on how complicated/time it would be to add this? 2-3 working days?

[bd82]

Was is your estimate on how complicated/time it would be to add this? 2-3 working days?

I think the base logic is pretty simple, but there would be some work around
performance and documentation.

[bd82]

Released in 4.7.0
See: https://sap.github.io/chevrotain/docs/guide/concrete_syntax_tree.html#cstnodes-location