Questions about indentation-aware parsing for YAML

[martin-fleck-at]

Hi everyone,

First, thank you for the fantastic work you're doing! I have experience using Xtext in multiple projects and have recently started applying Langium, and I'm really impressed with its architecture and codebase. I really appreciate it.

In one of those projects, CrossModel, we use Langium as the foundation for a model management server handling YAML-based models. For this, we developed a basic indentation-based YAML lexer that ignores list item markers (- ), treating them as part of the whitespace for indentation.

I was happy to see the latest master branch includes an indentation-aware lexer that's more in line with Langium’s architecture and offers customization options. I attempted to apply it to our grammar using the following custom class to handle the indentation regex while ignoring the '- ' character:

export class CrossModelTokenBuilder extends IndentationAwareTokenBuilder {
    protected readonly indentRegExp = /([ \t]+(- )?)/y;

    constructor(options?: Partial<IndentationTokenBuilderOptions>) {
        super(options);

        (this as any).indentTokenType = createToken({
            name: this.options.indentTokenName,
            pattern: this.indentMatcher,
            line_breaks: false,
        });
    }

    protected override indentMatcher: CustomPatternMatcherFunc = (text, offset, tokens, _groups) => {
        const { indentTokenName } = this.options;

        if (!this.isStartOfLine(text, offset)) {
            return null;
        }

        this.indentRegExp.lastIndex = offset;
        const match = this.indentRegExp.exec(text);
        const currIndentLevel = match?.[0].length ?? 0;
        const prevIndentLevel = this.indentationStack.at(-1)!;

        if (currIndentLevel <= prevIndentLevel) {
            return null;
        }

        this.indentationStack.push(currIndentLevel);

        const indentToken = this.createIndentationTokenInstance(
            this.indentTokenType,
            text,
            match?.[0] ?? indentTokenName,
            offset,
        );
        tokens.push(indentToken);

        return null;
    };
}

However, I encountered an error: "unexpected character: ->\n<- at offset: 7, skipped 1 characters." for example for this file:

This error breaks syntax highlighting. Interestingly, when I test it with a simplified version of the grammar in indentation-aware.test.ts, the error does not appear.

Given this, I have several questions:

1. Is this approach the right way to customize the lexer in this scenario, or is there a simpler method? If customization is needed, I’d be happy to propose a PR to make this easier.

2. Why might syntax highlighting be broken? Could it be related to the parsing error?

3. Any insights on why the "unexpected character" error occurs or suggestions for debugging this effectively? Are there any visualization tools available that could help here?

4. Is there a nightly build of Langium? I didn't find one on npm under the next tag, so I manually copied the indentation-aware.ts file. Could missing other updates cause these issues?

5. It seems that whitespaceTokenName overrides the token with a token defined by whitespaceRegExp. Does this conflict with existing WS rules?

6. Does Langium discourage PRs for typos? I noticed a typo in ignoreIndentationDelimeters (should be ignoreIndentationDelimiters). I'm aware of backward compatibility concerns once the new release is out with the type, so I'd like to contribute a fix but wasn't sure as some projects do not like that.

Any help or insight (even on a single question) would be greatly appreciated! If YAML is an interesting use case for Langium, we're also open to contributing this work via a PR.

Thanks in advance!

[msujew]

cc @aabounegm Since you've worked quite a bit in this area, can you help? :)

[aabounegm]

Yes sure, sorry for the delay, writing a reply now

[aabounegm]

Hi @martin-fleck-at, let me try to answer the questions one by one:

1. Generally, this is the right way to override/extend the functionality of the lexer, but in this specific case it would be much simpler to just override the whitespaceRegExp property with your RegEx that matches whitespace and -s. Just make sure not to forget the y flag. If the RegEx is not flexible enough, you can override the matchWhitespace method instead.
2. The syntax highlighting is most likely broken due to the use of this_string_does_not_matter_spaces#$%^&*(( as the terminal pattern. The TextMate generator uses the source Langium file and not the overridden token definitions as the source for the generated grammar. As can be seen in textmate-generator.ts:L77, it uses GrammarUtils.isCommentTerminal, which defines a comment terminal as any hidden terminal that is not whitespace. The string you used satisfies this condition, and though I'm not sure what RegExpUtils.getTerminalParts would return here (need to test it myself), I'm suspecting this is the source of the problem. You should use token definitions that resemble actual SPACES and NEWLINEs, and note in a comment that it actually doesn't matter (for the actual parser).
   This should not be related to the parse error, which is the next point:
3. I noticed in your terminals.langium:L31 that you wrote the NEWLINE terminal definition doesn't matter, but actually this is not a token that gets overridden by the IndentationAwareTokenBuilder. The definition actually matters for this token. I use /[\r\n]+/ for it. I don't know about visualization tools, but when debugging the token builder I personally add something like console.log('tokens', result.tokens.map(tk => [tk.tokenType.name, tk.image])) to the tokenize function of the lexer just to check what tokens are lexed.
4. I'm generally not part of the release process, so @msujew could probably help more here, but I know there is a 3.2.0-next release on npm. Also, you can install the package using GitHub URL to get the version on GitHub rather than npm.
5. The reason we override this token is to ensure that it does not include new lines (because most users are probably used to just writing \s+ for the WS token, which would break the indentation matching. I'm not sure if the choice of reusing this. whitespaceRegExp is better than hard-coding [ \t]+, perhaps your use case would better clarify this.
6. Again, I'm just a contributor myself, but I assume such PRs are welcome as I have personally submitted one to the langium-website repo previously :). Since v3.2.0 is not released yet as stable, I believe it is a good idea to fix the typo before it gets released.

Hope this helps, let me know if you have any follow-up questions!

[msujew]

The completion only takes token up to the cursor position into account - all other tokens are ignored. Therefore, the } token simply isn't visible to the completion. This is the issue with the synthetic dedent tokens - they're technically "after" the cursor position and therefore mess with the completion calculation.

[aabounegm]

Got it. Could the problem be mitigated by adding a filter to this line:

langium/packages/langium/src/lsp/completion/completion-provider.ts

Line 224 in f60cfeb

const leftoverTokens = [...tokens].splice(parserResult.tokenIndex);

like this:

const leftoverTokens = [...tokens].splice(parserResult.tokenIndex).filter(token => token.startOffset < offset);

?
(or perhaps a more efficient variant of filter that starts from the end and stops with the first matching element, since order is guaranteed to be monotonically increasing)

[martin-fleck-at]

I'll try this out. I'm working currently on a PR for the diagnostics and will then check whether we can fix the auto-completion provider in a better way. My alternative approach to this would have been to allow an additional option to the tokenize method of the lexer that tells us whether we parse a full or partial document. But if we can make the filter more clever, maybe this is a better idea.

[martin-fleck-at]

I just tested this and it does not work. In my case, let's assume this is the full document:

entity:
    id: CalcAge
    name: "CalcAge"
    attributes:
      - id: BirthDate
        name: "BirthDate"
        datatype: "Integer"

And I put the cursor before the dataType, the following text is considered for completion parsing:

entity:
    id: CalcAge
    name: "CalcAge"
    attributes:
      - id: BirthDate
        name: "BirthDate"
        <cursor positition at offset 122>

As offset I get 122 (the cursor position) but the tokens of dedent are still in the way to properly detect the next feature, unfortunately.

[martin-fleck-at]

I opened #1669 as an option to properly distinguish between the two modes.

[aabounegm]

@msujew About the LeafCstNode exposing the token type, it seems straightforward to me to change it to store the whole token (unless I'm missing something obvious), I can prepare a PR for that. However, I still don't quite understand how to easily access the LeafCstNode of a token.
For example, let's say we're using the Hello World language that generates this AST:

interface Person extends AstNode {
    $type: 'Person';
    name: string;
}

then, let's say in my hover provider, I have:

if (isPerson(node)) {
    const range = ?? // How can I extract the range of just the `name` property, not the whole node? 
    return { contents: `A human named ${node.name}`, range };
}

I would like the hover range to be only on the name, how can I get this information easily? It would be great if there was an associated nameToken: IToken in the Person interface.

[martin-fleck-at]

I really can't help with this, but the only thing I noticed while looking at the diagnostics report: We need to ensure that the IToken can be properly serialized/deserialized as part of the hydration process that is used for async parsing.

[aabounegm]

That's a good point. Looking at the Chevrotain IToken docs, it seems that all properties have primitive types except for tokenType (which is already handled in the hydrator), and the payload which can have any type, but I think it's safe to assume that it would very rarely (if ever) be used with a non-serializable type.

[msujew]

I don't think that storing the whole token instance is necessary. We can already perfectly find the range for any property/keyword using:

langium/packages/langium/src/utils/grammar-utils.ts

Lines 111 to 134 in 51d99a6

	/**
	* Find a single CST node within the given node that contributes to the specified property.
	*
	* @param node A CST node in which to look for property assignments. If this is undefined, the result is `undefined`.
	* @param property A property name of the constructed AST node. If this is undefined, the result is `undefined`.
	* @param index If no index is specified or the index is less than zero, the first found node is returned. If the
	* specified index exceeds the number of assignments to the property, the last found node is returned. Otherwise,
	* the node with the specified index is returned.
	*/
	export function findNodeForProperty(node: CstNode | undefined, property: string | undefined, index?: number): CstNode | undefined {
	if (!node || !property) {
	return undefined;
	}
	const nodes = findNodesForPropertyInternal(node, property, node.astNode, true);
	if (nodes.length === 0) {
	return undefined;
	}
	if (index !== undefined) {
	index = Math.max(0, Math.min(index, nodes.length - 1));
	} else {
	index = 0;
	}
	return nodes[index];
	}

That's how we do all the LSP stuff, like identifying where the name of an element is stored in a document or where to apply diagnostics given an AstNode and the name of a property.

[aabounegm]

Oh, I see, I should have read the source code more closely 😅. I think it would help if the documentation had an "API reference" section, perhaps generated from the JSDoc