Improve local Scope Computation with AstNodeDescriptionAlias

[ydaveluy]

Hello,

[edit: this change decreases the performances of the linking phase so DON'T DO THIS !]

For languages with qualified name scoping it is necessary to import the descriptions from the nested scopes to the local scope:

   private processContainer(
        container: CppProgram | Namespace, 
        scopes: PrecomputedScopes, 
        document: LangiumDocument
    ): AstNodeDescription[] {
        ...
                const nestedDescriptions = this.processContainer(element, scopes, document);
                for (const description of nestedDescriptions) {
                    // Add qualified names to the container
                    // This could also be a partial qualified name
                    const qualified = this.createQualifiedDescription(element, description, document);
                    localDescriptions.push(qualified);
                }
        ...
   }
   private createQualifiedDescription(
        container: Namespace, 
        description: AstNodeDescription, 
        document: LangiumDocument
    ): AstNodeDescription {
        // `getQualifiedName` has been implemented in the previous section
        const name = this.getQualifiedName(container.name, description.name);
        return this.descriptions.createDescription(description.node!, name, document);
    }

It involve a lot of calls to the AstNodeDescriptionProvider to re-create the description at each level.

This could be improved by creating an AstNodeDescriptionAlias from the existing AstNodeDescription. Xtext provides a similar mechanism.

I tested the following implementation:

interface AstNodeDescriptionAlias extends AstNodeDescription {
    alias: AstNodeDescription;
}
function isAstNodeDescriptionAlias(obj: any): obj is AstNodeDescriptionAlias {
    return 'alias' in obj;
}
class DefaultAstNodeDescriptionAlias implements AstNodeDescriptionAlias {
    alias: AstNodeDescription;
    alias_name:string;

    constructor(alias: AstNodeDescription, name:string) {
        this.alias = alias;
        this.alias_name = name
    }

    get node(): AstNode | undefined {
        return this.alias.node;
    }

    get nameSegment(): DocumentSegment | undefined {
        return this.alias.nameSegment;
    }

    get selectionSegment(): DocumentSegment | undefined {
        return this.alias.selectionSegment;
    }

    get type(): string {
        return this.alias.type;
    }

    get name(): string {
        return this.alias_name;
    }

    get documentUri(): URI {
        return this.alias.documentUri;
    }

    get path(): string {
        return this.alias.path;
    }
}

And changed the createQualifiedDescription function to:

   private createQualifiedDescription(
        container: Namespace, 
        description: AstNodeDescription, 
        document: LangiumDocument
    ): AstNodeDescription {
        // `getQualifiedName` has been implemented in the previous section
        const name = this.getQualifiedName(container.name, description.name);

        if(isAstNodeDescriptionAlias(description))
            return new DefaultAstNodeDescriptionAlias(description.alias, name)

        return new DefaultAstNodeDescriptionAlias(description, name)
    }

With my DSL, it improves performance by at least 50% to compute Local Scopes:

LOC	before	after
100 000	235ms	83ms
50 000	141ms	56ms
20 000	55ms	17ms
10 000	21ms	8ms
5 000	10ms	3.5ms

Is it something that could be integrated in the AstNodeDescriptionProvider ?

export interface AstNodeDescriptionProvider {

    /**
     * Create a description for the given AST node. This service method is typically used while indexing
     * the contents of a document and during scope computation.
     *
     * @param node An AST node.
     * @param name The name to be used to refer to the AST node. By default, this is determined by the
     *     `NameProvider` service, but alternative names may be provided according to the semantics
     *     of your language.
     * @param document The document containing the AST node. If omitted, it is taken from the root AST node.
     */
    createDescription(node: AstNode, name: string | undefined, document?: LangiumDocument): AstNodeDescription;

    /**
     * Create an alias  for the given description. This service method is typically used while indexing
     * the contents of a document and during scope computation.
     *
     * @param description An AST node description.
     * @param name The name to be used to refer to the AST node.
     */
    createAliasDescription(description: AstNodeDescription, name: string ): AstNodeDescription;



}

[msujew]

Hey @ydaveluy,

thanks for explaining a better solution to this problem! I'm wondering whether the performance improvements are noticeable for languages without qualified name scoping as well. Like for languages where renaming is possible (like in TypeScript/JavaScript imports) or "normal" languages without the ability to have an element available under two different names.

I'm generally hesitant to include features into the framework that only benefit very few languages. I know that Xtext was more lenient in that regard, but it also contained qualified name scoping as a default feature, so it kind of made sense. However, we aim to keep the framework small to ensure a minimal bundle size, which was never a concern for Xtext (see its 40mb minimum size language servers). Note that we do have some special handling for a few languages (like with the new indentation aware lexing), but these can be tree-shaken so they don't end up in languages that don't actually need them. It gets more difficult to tree-shake stuff when it's part of the default implementation or even in the interface of a core service.

What do you think about adding this as part of the respective guide? I'd be all-in for that.

[ydaveluy]

Yes I can update the guide in langium-website and make a PR ?

I simplified the code a little bit. I think that it can be profitable for languages with imports too, but not tested.

export function isAstNodeDescriptionAlias(obj: unknown): obj is AstNodeDescriptionAlias {
    return isAstNodeDescription(obj) && isAstNodeDescription(typeof (obj as AstNodeDescriptionAlias).alias);
}
export class AstNodeDescriptionAlias implements AstNodeDescriptionAlias {
    public readonly alias: AstNodeDescription;
    private readonly alias_name: string;

    constructor(description: AstNodeDescription, name: string) {
        this.alias = isAstNodeDescriptionAlias(description) ? description.alias : description;
        this.alias_name = name
    }
    get node(): AstNode | undefined { return this.alias.node; }
    get nameSegment(): DocumentSegment | undefined { return this.alias.nameSegment; }
    get selectionSegment(): DocumentSegment | undefined { return this.alias.selectionSegment; }
    get type(): string { return this.alias.type; }
    get name(): string { return this.alias_name; }
    get documentUri(): URI { return this.alias.documentUri; }
    get path(): string { return this.alias.path; }
}

[ydaveluy]

@msujew : I opened a PR

[ydaveluy]

After more benchmarks, it seems that this change decreases the performances of the linking phase and globally decreases the performances of the building process so DON'T DO THIS !