Improving performance of a VS Code extension targeting a pre-existing language (caching, scope computation, built in functions etc.)

[BjAlvestad]

Summary

Linking errors triggering update in document, and their performance impact

In a workspace where you have many errors where reference cannot be resolved (due to scoping for some scenarios not being handled yet). Is it expected that a change in a healthy file where there are no cross references between it and the faulty ones will trigger an update where scoping get recomputed for all the files with error references as well?
I.e. It is not worth looking into caching for improving performance, before I first have expand my scope provider to cover all scenarios, and add built in libraries. So that it should then greatly improve the performance before I even implement any caching.

Bundling built in libraries

Regarding bundling built in libraries. Would the best option to just make some "fake" DSL files which describes the interface for the built in functions that are available, and just inject these via loadAdditionalDocuments in WorkspaceManager?

Caching

At its most basic level, would this just be to initialize an instance of DocumentCache<string, VariableDeclaration[]>, where an array of VariableDeclaration is what the scope gets created from in the end. And then check if key exists inside this, if so, return from it, otherwise calculate and store in cache and then after that return the values for scope?

We need to provide URI to the DocumentCache in addition to the key when accessing it. Is the way to go about this to just walk along the containers until we reach the root, and then get the URI from that? E.g.

    private getTopLevelContainer(node: AstNode) {
        let container = node.$container as AstNode;
        while(container?.$container)
        {
            container = container.$container;
        }

        return container;
    }

Some more background information

I have now a working extension that gives me cross reference for several parts (local variables, structs, and UDTs definer in other files). But I have not yet fixed cross reference for global variables and built in functions. The program is in a state where I could actually start using it were it not for performance is abysmal for very large projects (~25MB) so was originally planning to implement caching before continuing with fixing scoping for the remaining parts, since I assumed more cross references resolved would decrease the performance even further. But then I noticed something that made me question this assumption.

When I save a file with no external cross references, it seems that scope function gets called also on other files with broke cross references, but not if I remove the broken references. Is this the expected behavior that broken links will run every time any file changes?
If so, I guess I should look into fixing scoping for those before continuing with caching.
I note that under Modifications of a document section on Document Lifecycle page it is stated that:

All other documents that may have been affected as a result of the modification get their references unlinked and their state is modified such that they run through the linking phase again.

So the system does not really know if the broken references are affected or not, by virtue of them being broken, and therefore will always trigger an update of these as well?

Also in that spirit. There are several built in functions in the language, that will not be able to find its cross reference in the workspace the user opens.
What would be the best way to build this into my program? Reading from additional target language code files, which I bundle with langium, that define these interfaces? Or to code them directly into langium? Or something else entirely?
Currently leaning towards the first one, and then just blend these bundled library files via loadAdditionalDocuments in WorkspaceManager.

[msujew]

Hey @BjAlvestad,

Would the best option to just make some "fake" DSL files which describes the interface for the built in functions that are available, and just inject these via loadAdditionalDocuments in WorkspaceManager?

Generally yes. That's often times the approach we're going for when offering built-in functions.

And then check if key exists inside this, if so, return from it, otherwise calculate and store in cache and then after that return the values for scope?

I would recommend you to use the get-with-provider methods available in the caches:

langium/packages/langium/src/utils/caching.ts

Lines 49 to 62 in b2c40e3

	get(key: K): V | undefined;
	get(key: K, provider: () => V): V;
	get(key: K, provider?: () => V): V | undefined {
	this.throwIfDisposed();
	if (this.cache.has(key)) {
	return this.cache.get(key);
	} else if (provider) {
	const value = provider();
	this.cache.set(key, value);
	return value;
	} else {
	return undefined;
	}
	}

Supplying a provider makes the code a bit more readable.

We need to provide URI to the DocumentCache in addition to the key when accessing it. Is the way to go about this to just walk along the containers until we reach the root, and then get the URI from that? E.g.

Yes, that's usually the way to go about this. We have a utility function available in the AstUtils exactly for that:

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

Lines 84 to 92 in b2c40e3

	/**
	* Returns the root node of the given AST node by following the `$container` references.
	*/
	export function findRootNode(node: AstNode): AstNode {
	while (node.$container) {
	node = node.$container;
	}
	return node;
	}

So the system does not really know if the broken references are affected or not, by virtue of them being broken, and therefore will always trigger an update of these as well?

Exactly. Essentially, any change in a document, might result in a broken reference being fixed. This is why relinking is performed on files with broken references after any change. Note that this behavior can be adjusted in the IndexManager. The default is just there to work well with how the default global scoping works. In case your global scope works differently (like most languages actually, which are often based on some import functionality), it makes sense to adjust the behavior to take the differences in scope behavior into account.

What would be the best way to build this into my program? Reading from additional target language code files, which I bundle with langium, that define these interfaces? Or to code them directly into langium? Or something else entirely?

It depends on the use case. For example, if the builtins only evolve with the language, we sometimes just put the builtins into a TypeScript file as a string. That way, they are always available for the language server to process. See also our guide on this topic. If you want to read the builtins from the filesystem, that's also completely valid. IIRC TypeScript does something like this. Note that this doesn't work as easily if you want your language server to run in the browser, where you would potentially need to fetch the builtins from a remote server.

A general note from me: Once you start working on large workspaces with your language, optimization will always be a core part of your work. We have projects where 90% of our work is essentially just profiling a language and implementing optimizations for it. This isn't only about Langium (or Xtext), but most language projects.

[BjAlvestad]

Thank you very much for your reply, which was very helpful, as always. I do however have a few follow-up and adjacent questions:

In summary my questions are:

• What is the correct way to override IndexManager?
• How can we test (via unit tests) linking between multiple documents?

More detailed question/info below:

Regarding overriding of IndexManager:
Is this supposed to be done in the same Module where ScopeProvider and HoverProvider gets overridden?
Or should this be done somewhere else?
In the default-module.ts the IndexManager is located in createDefaultSharedCoreModule() and not createDefaultCoreModule().
It seems to be available in the module for override under shared: { workspace: { IndexManager ... }}, at the same place we override ScopeProvider etc. But when I try do do so it seems to break everything (as in server will not start).

Regarding writing UnitTests for linking between multiple documents:
I have some linking tests for linking internally in a document, but would like to write some tests for testing across multiple documents.
Any pointes as to how this should be done?
I have tried parsing two documents with two spearate await parse( statements, and can actually see that both documents exists with services.shared.workspace.LangiumDocuments.all.toArray(), but if I try to access a ref by going directly to parseResult on one document, it does not seem to have linked.
Testing these two same documents in VS Code, it links correctly.

I will probably have some more questions as I progress with this (e.g. regarding some current confusion with regards to global scope for [NamedElement:DOUBLE_QUOTE_STRING] vs. [SclBlock:DOUBLE_QUOTE_STRING] when type NamedElement = VariableDeclaration | SclBlock;. And also things like global vs getScope use case, and cashing of "global" refs. that should only update if "title" of a document changes). Would it be ok to continue to use this Q&A for questions like that, or is it preferable that I instead mark it as answered now since my original questions have been answered?

[msujew]

Is this supposed to be done in the same Module where ScopeProvider and HoverProvider gets overridden?

No, services that are cross-language have their own shared service container. See for an example:

langium/packages/langium-vscode/src/language-server/main.ts

Lines 17 to 21 in 48e67d6

	export const LangiumGrammarSharedModule: Module<LangiumSharedServices, PartialLangiumSharedServices> = {
	workspace: {
	WorkspaceManager: (services) => new LangiumGrammarWorkspaceManager(services)
	}
	};

It seems to be available in the module for override under shared: { workspace: { IndexManager ... }}, at the same place we override ScopeProvider etc. But when I try do do so it seems to break everything (as in server will not start).

Yeah, we should probably make all elements of services readonly (on an API and object level) - manually changing fields in the service container will break a bunch of stuff.

I have tried parsing two documents with two spearate await parse( statements, and can actually see that both documents exists with services.shared.workspace.LangiumDocuments.all.toArray(), but if I try to access a ref by going directly to parseResult on one document, it does not seem to have linked.

Can you give a reproducible example? I can't really imagine why this would happen. Generally, assuming it works in VS Code, it should work the same in your test environment.

Would it be ok to continue to use this Q&A for questions like that, or is it preferable that I instead mark it as answered now since my original questions have been answered?

That's fine, since it's still very much in the spirit of the original question :)

[BjAlvestad]

Once again, thank you very much :)

Can you give a reproducible example? I can't really imagine why this would happen. Generally, assuming it works in VS Code, it should work the same in your test environment.

As for this issue, turns out I had been parsing the documents in the wrong order. Once I parsed the document we are referencing first (as well as fixing some other silly mistakes with accessing elements at the wrong place), then it started working.

Expand toggle if you wish to see my current linking tests across documents

import { afterEach, beforeAll, describe, expect, test } from "vitest";
import { EmptyFileSystem, type LangiumDocument } from "langium";
import { expandToString as s } from "langium/generate";
import { clearDocuments, parseHelper } from "langium/test";
import { createSclServices } from "../../src/language/scl-module.js";
import { DbProgramElement, MemberCall, Model, isModel } from "../../src/language/generated/ast.js";

let services: ReturnType<typeof createSclServices>;
let parse:    ReturnType<typeof parseHelper<Model>>;
let document: LangiumDocument<Model> | undefined;
let otherDocument: LangiumDocument<Model> | undefined;

beforeAll(async () => {
    services = createSclServices(EmptyFileSystem);
    parse = parseHelper<Model>(services.Scl);

    // activate the following if your linking test requires elements from a built-in library, for example
    // await services.shared.workspace.WorkspaceManager.initializeWorkspace([]);
});

afterEach(async () => {
    document && clearDocuments(services.shared, [ document ]);
    otherDocument && clearDocuments(services.shared, [ otherDocument ]);
});

describe('Linking cross document tests', () => {

    test('linking to element in type used for DB of type, from DB initialization', async () => {
        otherDocument = await parse(`
            TYPE "U_Status"
            VERSION : 0.1
            STRUCT
                good : Bool;
                warning : Bool;
                fault : Bool;
                critical : Bool;
            END_STRUCT;

            END_TYPE
        `, {documentUri: "file:///U_Status.scl"});

        document = await parse(`
            DATA_BLOCK "MyDbOfType"
            NON_RETAIN

            "U_Status"

            BEGIN

            critical;

            END_DATA_BLOCK
        `, {documentUri: "file:///MyDbOfType.scl"});

        const element0 = document?.parseResult.value.elements[0] as DbProgramElement;
        expect(
            checkDocumentValid(document) || s`
                refText:
                    ${element0.element?.element.$refText}
                ref.name:
                    ${element0.element?.element.ref?.name}
            `
        ).toBe(s`
            refText:
                critical
            ref.name:
                critical
        `);
    });

    test('linking to element in local variable of UDT, from FB', async () => {
        otherDocument = await parse(`
            TYPE "U_Status"
            VERSION : 0.1
            STRUCT
                good : Bool;
                warning : Bool;
                fault : Bool;
                critical : Bool;
            END_STRUCT;

            END_TYPE
        `, {documentUri: "file:///U_Status.scl"});

        document = await parse(`
            FUNCTION_BLOCK "FB_MyFB"
            VERSION : 0.1
            
            VAR 
                myStatus : "U_Status";
            END_VAR

            BEGIN

            #myStatus.good;

            END_FUNCTION_BLOCK
        `, {documentUri: "file:///FB_MyFB.scl"});

        const element0 = document?.parseResult.value.elements[0] as MemberCall;
        expect(
            checkDocumentValid(document) || s`
                refText:
                    ${element0.element?.$refText}
                ref.name:
                    ${element0.element?.ref?.name}
            `
        ).toBe(s`
            refText:
                good
            ref.name:
                good
        `);
    });

    test('linking to element in global DB from FB', async () => {
        otherDocument = await parse(`
            DATA_BLOCK "gb_MyGlobalDb"
            NON_RETAIN

            VAR 
                myOtherVar : DINT;
            END_VAR

            BEGIN

            END_DATA_BLOCK
        `, {documentUri: "file:///gb_MyGlobalDb.scl"});

        document = await parse(`
            FUNCTION_BLOCK "FB_MyFB"
            VERSION : 0.1
            
            VAR 
                myLocalVar : DINT;
            END_VAR

            BEGIN

            myLocalVar;
            "gb_MyGlobalDb".myOtherVar;

            END_FUNCTION_BLOCK
        `, {documentUri: "file:///FB_MyFB.scl"});

        const fbDockDirectParseResults = document?.parseResult.value;
        const element0 = fbDockDirectParseResults.elements[0] as MemberCall;
        const element1 = fbDockDirectParseResults.elements[1] as MemberCall;
        expect(
            checkDocumentValid(document) || s`
                refText:
                    ${element0.element?.$refText}
                    ${element1.element?.$refText}
                ref.name:
                    ${element0.element?.ref?.name}
                    ${element1.element?.ref?.name}
            `
        ).toBe(s`
            refText:
                myLocalVar
                myOtherVar
            ref.name:
                myLocalVar
                myOtherVar
        `);
    });

});

function checkDocumentValid(document: LangiumDocument): string | undefined {
    return document.parseResult.parserErrors.length && s`
        Parser errors:
          ${document.parseResult.parserErrors.map(e => e.message).join('\n  ')}
    `
        || document.parseResult.value === undefined && `ParseResult is 'undefined'.`
        || !isModel(document.parseResult.value) && `Root AST object is a ${document.parseResult.value.$type}, expected a '${Model}'.`
        || undefined;
}

[BjAlvestad]

Avoid linking error on built-ins I have not defined yet

In summary:

Info on types in the language:
In my language, datatypes are either keywords, built-ins, (which are ID terminals /[_a-zA-Z][\w_]*/) or user defined. If they are user defined, they are enclosed in double quotes. Thus it is possible to separate between a built-in or something that has been user defined.

Question:
What would be the best way to prevent linking error for built-ins that has not been added yet (but still keeping linking for those that has)?
Currently it bloats the "Problems" section, and unnecessarily reduce performance due to recalculating all these broken references to built-ins.
User defined types (enclosed in double quotes) should still give linking error in this case.

More detailed question/info

This section may get updated with more notes as I investigate further.

Notes.

• Members are accessed with . notation using Class Member Scoping.
• Function calls are specified with formal parameters. E.g. MAX(IN1 := -123, IN2 := 32).
• Can also be called via members of local variables.

Currently, assuming I have not added a built-in for MAX, I would have linking errors from MAX, IN1 and IN2, which is what I hope to avoid.

So I am trying to see if I could override something in DefaultLinker code, so that if it is a normal ID, and it fails. Instead of creating an error object with createLinkingError that I somehow instead could simply make it behave as if there should be no cross-reference (or make the jump to go to a "generic built-in" that say that this built-in has not been added yet.
But I am unsure where would be the right place to attack this.
Or am I even at the right stage? Should I instead be looking into the IndexManager, or something else entirely?

[msujew]

Hey @BjAlvestad,

Instead of creating an error object with createLinkingError that I somehow instead could simply make it behave as if there should be no cross-reference (or make the jump to go to a "generic built-in" that say that this built-in has not been added yet.

Yes, linking to a "generic built-in" item is probably the way to go here. However, instead of attempting to do this in the createLinkingError method (which is already too late, since we don't want to create a linking error in the first place), you should likely do this in the getLinkedNode method:

langium/packages/langium/src/references/linker.ts

Lines 193 to 220 in dc18342

	protected getLinkedNode(refInfo: ReferenceInfo): { node?: AstNode, descr?: AstNodeDescription, error?: LinkingError } {
	try {
	const description = this.getCandidate(refInfo);
	if (isLinkingError(description)) {
	return { error: description };
	}
	const linkedNode = this.loadAstNode(description);
	if (linkedNode) {
	return { node: linkedNode, descr: description };
	}
	else {
	return {
	descr: description,
	error:
	this.createLinkingError(refInfo, description)
	};
	}
	} catch (err) {
	console.error(`An error occurred while resolving reference to '${refInfo.reference.$refText}':`, err);
	const errorMessage = (err as Error).message ?? String(err);
	return {
	error: {
	...refInfo,
	message: `An error occurred while resolving reference to '${refInfo.reference.$refText}': ${errorMessage}`
	}
	};
	}
	}

In there you can then just point the reference to some (maybe even synthetic) AST node.