5. Resolve cross-references

This step takes place after generating the AST. The AST definition was created and you are able to parse input files. But the AST is not complete yet. It contains cross-references that are not resolved. Cross-references are used to reference other elements in your language.

Let’s illustrate the problem using the Hello-World example from the Yeoman generator:

person John
person Jane

Hello John!
Hello Jane!

The following syntax tree is generated by the Langium parser during the runtime. Mind the gaps with the question marks. These are the missing pieces you want to fill out in this step.

graph TB
  Model-->persons
  Model-->greetings
  
  persons-->P1[Person]
  P1 --> H1('person')
  P1 --> N1[name]
  N1 --> NL1('John')
  
  persons-->P2[Person]
  P2 --> H2('person')
  P2 --> N2[name]
  N2 --> NL2('Jane')

  greetings-->G1[Greeting]
  G1 --> KW1('hello')
  G1 --> PRef1[Ref]
  PRef1 -- $refText --> RT1('John')
  G1 --> EM1('!')
  PRef1 --> QM1{?}

  greetings-->G2[Greeting]
  G2 --> KW2('hello')
  G2 --> PRef2[Ref]
  PRef2 -- $refText --> RT2('Jane')
  G2 --> EM2('!')
  PRef2 --> QM2{?}

You normally can achieve the cross-reference resolution by implementing a so-called scope provider and a scope computation. When setup correctly given syntax tree will change to this:

graph TB
  Model-->persons
  Model-->greetings
  
  persons-->P1[Person]
  P1 --> H1('person')
  P1 --> N1[name]
  N1 --> NL1('John')
  
  persons-->P2[Person]
  P2 --> H2('person')
  P2 --> N2[name]
  N2 --> NL2('Jane')

  greetings-->G1[Greeting]
  G1 --> KW1('hello')
  G1 --> PRef1[Ref]
  PRef1 -- $refText --> RT1('John')
  G1 --> EM1('!')
  PRef1 -..-> P1

  greetings-->G2[Greeting]
  G2 --> KW2('hello')
  G2 --> PRef2[Ref]
  PRef2 -- $refText --> RT2('Jane')
  G2 --> EM2('!')
  PRef2 -..-> P2

As already hinted, you can implement a scope provider and a scope computation. Fortunately, Langium comes with default implementations for both. But eventually as your language grows, you might want to implement your own strategy because the default is not sufficient. In the following sections the interpretation of the involved interfaces will be sketched.

The scope provider is responsible for providing a scope for a given cross-reference represented by the ReferenceInfo type.

A scope is a collection of AST nodes that are represented by the AstNodeDescription type.

The description is like a (string) path through the AST of a document. It can be also seen as a tuple of document URI, JSON path, name and type of the AST node.

A reference info contains the concrete AST reference (which points to nothing yet). The info also has the parent AST node (a so-called container) of the reference and the property name under which you can find the reference under its container. In the form of this tuple (container, property, reference) Langium visits all cross-references using the scope provider’s getScope method.

export interface ScopeProvider {
    getScope(context: ReferenceInfo): Scope;
}

export interface ReferenceInfo {
    reference: Reference
    container: AstNode
    property: string
    index?: number
}

export interface Scope {
    getElement(name: string): AstNodeDescription | undefined;
    getAllElements(): Stream<AstNodeDescription>;
}

So, what is the purpose of the scope provider? As mentioned above: it visits each cross-reference and tries to find the corresponding AST nodes over the entire workspace that can be a candidate for the cross-reference’s place. It is important to understand that we do not decide here which of these nodes is the perfect match! That decision is part of the so-called linker of the Langium architecture.

Whether your cross-reference’s $refText contains the name Jane does not matter here. We need to provide all nodes that are possible at this position. So in the result, you would return Jane and John AST nodes - for both cross-references!

The background for this behavior is that this mechanism can be used for two things: the cross-reference resolution and the code completion. The code completion needs to know all possible candidates for a given cross-reference. The resolution of the cross-reference is done by the linker: Given a scope for a certain cross-reference, the linker decides which of the candidates is the right one - for example the first candidate with the same name.

The scope computation is responsible for defining per document file…

1. which AST nodes are getting exported to the global scope. These nodes will be collected by the so-called index manager.
2. which AST nodes (as descriptions) are available in the local scope of a certain AST node. This is meant as a cache computation for the scope provider.

The index manager is keeping in mind the global symbols of your language. It can be used by the scope provider to find the right candidates for a cross-reference.

export interface ScopeComputation {
  computeExports(document: LangiumDocument, cancelToken?: CancellationToken): Promise<AstNodeDescription[]>;
  computeLocalScopes(document: LangiumDocument, cancelToken?: CancellationToken): Promise<PrecomputedScopes>;
}

So, while the scope computation is defining what symbols are globally exported (like using the export keyword in Typescript), the scope provider is the place to implement the import of these symbols using the index manager and the semantics of your import logic.

1. The AST gets generated by the parser for each document in the workspace.
2. The scope computation is called for each document in the workspace. All exported AST nodes are collected by the index manager.
3. The scope computation is called for each document in the workspace, again. All local scopes get computed and attached to the document.
4. The linker and the scope provider are called for each cross-reference in the workspace. The scope provider uses the index manager to find candidates for each cross-reference. The linker decides which candidate is the right one for each cross-reference.

For the Hello-World example, you can implement a scope provider and a scope computation like this (keep in mind that this is a alternative solution to the default implementation of Langium, which already works for most cases):

import { ReferenceInfo, Scope, ScopeProvider, AstUtils, LangiumCoreServices, AstNodeDescriptionProvider, MapScope, EMPTY_SCOPE } from "langium";
import { isGreeting, isModel } from "./generated/ast.js";

export class HelloWorldScopeProvider implements ScopeProvider {
    private astNodeDescriptionProvider: AstNodeDescriptionProvider;
    constructor(services: LangiumCoreServices) {
        //get some helper services
        this.astNodeDescriptionProvider = services.workspace.AstNodeDescriptionProvider;
    }
    getScope(context: ReferenceInfo): Scope {
        //make sure which cross-reference you are handling right now
        if(isGreeting(context.container) && context.property === 'person') {
            //Success! We are handling the cross-reference of a greeting to a person!

            //get the root node of the document
            const model = AstUtils.getContainerOfType(context.container, isModel)!;
            //select all persons from this document
            const persons = model.persons;
            //transform them into node descriptions
            const descriptions = persons.map(p => this.astNodeDescriptionProvider.createDescription(p, p.name));
            //create the scope
            return new MapScope(descriptions);
        }
        return EMPTY_SCOPE;
    }
}

Please make sure to override the default scope provider in your language module file like this:

//...
export const HelloWorldModule: Module<HelloWorldServices, PartialLangiumServices & HelloWorldAddedServices> = {
    //validation: ...
    references: {
        ScopeProvider: (services) => new HelloWorldScopeProvider(services)
    }
};
//...

You can test the linking by comparing the resolved references with the expected references. Here is the example from the last step.

import { createHelloWorldServices } from "./your-project//hello-world-module.js";
import { EmptyFileSystem } from "langium";
import { parseHelper } from "langium/test";
import { Model } from "../../src/language/generated/ast.js";

//arrange
const services = createHelloWorldServices(EmptyFileSystem);
const parse = parseHelper<Model>(services.HelloWorld);

//act
const document = await parse(`
    person John
    person Jane
    
    Hello John!
    Hello Jane!
`);

//assert
const model = document.parseResult.value;
expect(model.persons).toHaveLength(2);
expect(model.greetings).toHaveLength(2);
expect(model.greetings[0].person.ref).toBe(model.persons[0]);
expect(model.greetings[1].person.ref).toBe(model.persons[1]);

The expect function can be any assertion library you like. The Hello world example uses Vitest.