Xtext relies on EMF for the in-memory representation of a parsed program, thus, it is necessary to understand how cross-references are represented in EMF.

In EMF, when a feature is not a datatype (string, integer, and so on), it is a reference, that is, an instance of EReference. A containment reference defines a stronger type of association. The association is stronger regarding the lifecycle. The referenced object is contained in the referring object, called the container. In particular, an object can have only one container. If you delete the container, all its contents are also automatically deleted. For non-containment references, the referenced object is stored somewhere else, for example, in another object of the same resource or even in a different resource. A cross-reference is implemented as a non-containment reference.

Let's recall the SmallJava DSL rule for a class definition:

SJClass: 'class' name=ID ('extends' superclass=[SJClass])? '{'
      members += SJMember*
'}' ;

An SJMember member is contained in an SJClass class, that is, members is a multi-value containment reference. On the contrary, superclass is a single-value cross-reference.

Scoping deals with cross-references, that is, references with the boolean attribute containment set to false.

The Xtext index stores information about all the objects in every resource. This mechanism is the base for cross-reference resolution. For technical reasons (mainly efficiency and memory overhead), the index stores the IEObjectDescription elements instead of the actual objects. An IEObjectDescription element is an abstract description of an EObject. This description contains the name of the object and the EMF URI of the object. The EMF URI is a path that includes the resource of the object and a unique identifier in the resource. The URI provides a means to locate and load the actual object when needed. The description also contains the EClass of the object, which is useful to filter descriptions by type.

The set of resources handled by the index depends on the context of execution. In the IDE, Xtext indexes all the resources in all the Xtext projects. The index is kept up-to-date in an incremental way using the incremental building mechanism of Eclipse, thus keeping the overhead minimal.

In a plain runtime context, where there is no workspace, the index is based on the EMF ResourceSet. We will see what this implies when we write JUnit tests and when we implement a standalone compiler.

In both contexts, the index is global. Visibility across resources is handled by using containers as shown later in the The index and the containers section.

The default implementation of the index uses a mechanism based on names. The computation of names is delegated to IQualifiedNameProvider. The default implementation of the name provider is based on the string attribute name. This is why we always defined elements that we want to refer to with a feature name in the grammar.

Using only the simple name will soon raise problems due to duplicates, even in a simple program. Most Java-like languages use namespaces to allow for elements with the same name in different namespaces. Thus, for example, two different methods are allowed to have local variables with the same name, two different classes are allowed to have fields with the same name, two different packages are allowed to have classes with the same name, and so on. For this reason, the default implementation of the name provider computes a qualified name. It concatenates the name of an element with the qualified name of its container recursively; elements without a name are simply skipped. By default, all segments of a qualified name are separated by a dot, which is a common notation for expressing qualified names like in Java.

For example, consider the following SmallJava program (the type of declarations is not important here, thus, we use the class A that we assume as defined in the program):

class C {
  A f;
  A m(A p) {
    A v = null;
    return null;
  }
}

The containment relations are shown in the following tree figure:

The qualified names of the elements of the preceding SmallJava class are shown in the following table:

Note that SJMethodBody does not participate in the computation of the qualified name of the contained variable declaration, since it does not have a name feature.

To understand the mechanism behind scoping, it is useful to learn how to access the index. Accessing the index will also be useful for performing additional checks as shown later in this chapter. We show how to get all the object descriptions of the current resource.

The indexed object descriptions of a resource are stored in IResourceDescription, which is an abstract description of a resource. The index is implemented by IResourceDescriptions (plural form) and can be obtained through an injected ResourceDescriptionsProvider using the getResourceDescriptions(Resource) method.

Different resource descriptions are returned depending on the context they are retrieved. For example, there are resource descriptions of the files as they are on disk. However, while typing in the editor, a different resource description will be retrieved, which reflects the unsaved changes and that will shadow the resource description of the corresponding file saved on the disk. The ResourceSet records in which context it was created, that is why it is used as a parameter in the ResourceDescriptionsProvider.

Once we have the index, we get the IResourceDescription of a resource by specifying its URI. Once we have the IResourceDescription, we get the list of all the IEObjectDescription elements of the resource that are externally visible, that is, globally exported, using the method getExportedObjects. We can also filter exported elements by type:

We implement all the index-related operations in a separate class, SmallJavaIndex, in the package scoping:

class SmallJavaIndex {
  @Inject ResourceDescriptionsProvider rdp

  def getResourceDescription(EObject o) {
    val index = rdp.getResourceDescriptions(o.eResource)
    index.getResourceDescription(o.eResource.URI)
  }

  def getExportedEObjectDescriptions(EObject o) {
    o.getResourceDescription.getExportedObjects
  }

  def getExportedClassesEObjectDescriptions(EObject o) {
    o.getResourceDescription.
      getExportedObjectsByType(SmallJavaPackage.eINSTANCE.SJClass)
  }
}

We then write a learning test (see Chapter 7, Testing) listing the qualified names of the exported object descriptions:

@RunWith(XtextRunner)
@InjectWith(SmallJavaInjectorProvider)
class SmallJavaIndexTest {
  @Inject extension ParseHelper<SJProgram>
  @Inject extension SmallJavaIndex
  @Test def void testExportedEObjectDescriptions() {
    '''
    class C {
      A f;
      A m(A p) {
        A v = null;
        return null;
      }
    }
    class A {}
    '''.parse.assertExportedEObjectDescriptions
          ("C, C.f, C.m, C.m.p, C.m.v, A")
     // this will have to be adapted at the end of the chapter
  }
  def
 private assertExportedEObjectDescriptions(EObject o,
                    CharSequence expected) {
   expected.toString.assertEquals(
    o.getExportedEObjectDescriptions.map[qualifiedName].join(", ")
   )
  }
}

The actual cross-reference resolution, that is, the linking, is performed by LinkingService. Usually, you do not need to customize the linking service, since the default implementation relies on IScopeProvider, which is the component you would customize instead. The default linking service relies on the scope obtained for a specific context in the model, and chooses an object whose name matches the textual representation of the reference in the program.

Thus, a scope provides information about:

You can think of a scope as a symbol table (or a map), where the keys are the names and the values are instances of IEObjectDescription. The Java interface for scopes is IScope.

The overall process of cross-reference resolution, that is, the interaction between the linker and the scope provider, can be simplified as follows:

The IScopeProvider entry point is a single method:

IScope getScope(EObject context, EReference reference)

Since the program is stored in an EMF model, the context is an EObject and the reference is an EReference. Note that cross-references in an Xtext grammar specify the type of the referred elements. Thus, the scope provider must also take the types of objects for that specific reference into consideration when building the scope. The type information is retrieved from EReference that is passed to getScope.

Both scopes and the index deal with object descriptions. The crucial difference is that a scope also specifies the actual string with which you can refer to an object. The actual string does not have to be equal to the object description's qualified name in the index. Thus, the same object can be referred to with different strings in different program contexts.

To put it in another way, the index provides all the qualified names of the visible objects of a resource so that all these objects can be referred to using their qualified names. The scope provides further information, that is, in a given program context, some objects can be referred to even using simple names or using qualified names with less segments.

If in our DSL we can only use IDs to refer to objects, and objects are visible only by their fully qualified names, then we will not be able to refer to any object. Thus, being able to refer to an object by a simple name is essential.

Another important aspect of scopes is that they can be nested. Usually, a scope is part of a chain of scopes so that a scope can have an outer scope, also known as the parent scope. If a matching string cannot be found in a scope, it is recursively searched in the outer scope. If a matching string is found in a scope, the outer scope is not consulted. This strategy allows Xtext to implement typical situations in programming languages. For example, in a code block, you can refer to variables declared in the containing block. Similarly, declarations in a block usually shadow possible declarations with the same name in the outer context.

The default implementation of IScopeProvider reflects the nested nature of scopes using the containment relations of the EMF model. For a given program context, it builds a scope where all objects in the container of the context are visible by their simple name. The outer scope is obtained by recursively applying the same strategy on the container of the context.

Let's go back to our previous SmallJava example:

class C {
  A f;
  A m(A p) {
    A v = null;
    return null; // assume this is the context
  }
}

Let's assume that the context is the expression of the return statement; in that context, the SJMember elements will be visible by simple names and by qualified names:

f, m, C.f, C.m

In the same context, the SJSymbol elements will be visible by the following names:

p, v, m.p, m.v, C.m.p, C.m.v

This is because p and v are contained in m, which in turn is contained in C. Note that they are also visible by simpler qualified names, that is, qualified names with less segments, m.p and m.v, respectively.

In the SmallJava grammar, we can refer to members and symbols only by their simple name using an ID, not by a qualified name. Without a scope, we would not be able to refer to any of such elements, since they would be visible only by their qualified names.

A learning test that invokes the method getScope can help understand the default scope provider implementation (note how we specify EReference using SmallJavaPackage):

@RunWith(XtextRunner)
@InjectWith(SmallJavaInjectorProvider)
class SmallJavaScopeProviderTest {
  @Inject extension ParseHelper<SJProgram>
  @Inject extension SmallJavaModelUtil

  @Inject extension IScopeProvider
  @Test def void testScopeProvider() {
    '''
    class C {
      A f;
      A m(A p) {
        A v = null;
        return null; // return's expression is the context
      }
    }
    class A {}
    '''.parse.classes.head.
        methods.last.returnStatement.expression => [
          // THIS WILL FAIL when we customize scoping in the next sections
          assertScope
          (SmallJavaPackage.eINSTANCE.SJMemberSelection_Member,
            "f, m, C.f, C.m")
          assertScope
          (SmallJavaPackage.eINSTANCE.SJSymbolRef_Symbol,
            "p, v, m.p, m.v, C.m.p, C.m.v")
        ]
    }

  def private assertScope(EObject context,
                 EReference reference, CharSequence expected) {

    expected.toString.assertEquals(
      context.getScope(reference).
        allElements.map[name].join(", "))
  }
}

In the next diagram, we show the interaction between the linker and the scope provider for the resolution of the member in a member selection expression:

Summarizing, the default implementation of the scope provider fits most DSLs; in fact, for the Entities DSL, the cross-reference resolution worked out of the box.

Before getting into scope customization, we conclude this section by summarizing, in a simplified way, how all of the preceding mechanisms are executed internally by Xtext's builder:

This workflow is fixed. Consequently, we cannot rely on resolved cross-references during indexing. We need to keep that into consideration if we modify the indexing process, as we will see later in the section, What to put in the index?