Resolving scope for variables inside a function's body

Sep 24, 2011

Unrealscript is pretty similar in design to OO languages like C++ and Java, in that you declare classes, and each class has several member variables, function declarations, structs, enums etc. Inside a function, only the following variables need to be accessible:

  1. Arguments passed to the function
  2. Variables declared inside the function
  3. Members of the class the function resides in
  4. Members of each super class of the current class

Now, I don’t know how exactly (magic?) but Xtext usually handles the first three pretty well. I’ve defined the grammar for my function declarations as follows:

FunctionBody:
    {FunctionBody} (LCBRACK)?
    ( ( ( localDeclarations += LocalDeclaration )*
    ( codeLines += CodeLine )* ) ( SEMICOLON )? )
    (RCBRACK)?;

LocalDeclaration:
    'local' varDeclaration=VarDeclaration SEMICOLON;

and references to variables are resolved as follows:

    DeclaredVariable: VarName | FunctionArg;

This works out fine for the most part. If I have code that looks like this:

struct Vector { int X, Y, Z; }
function Magnitude(Vector v) {
    return sqrt(v.X*v.X + v.Y*v.Y + v.Z*v.Z
}

It can correctly resolve both v as the function argument Vector v, and v.X as the int x inside struct Vector.

However, if I have two functions like so:

operator int -(int x, int y) {
    return x - y;
}
operator vector -(vector x, vector y) {
    vector result;
    result.x = x.X - y.X;
    //...
}

It resolves the x in the vector - operator to the int x in the int - operator, since the qualified names for functions are calculated based solely on their names, which are both -.

So, I figured I’d modify the QualifiedNameProvider to return a qualified name based on the return type, name, and type and number of arguments. Worked for a couple of hours to get this working, and then I found these two in Object.uc:

native(137) static final preoperator  byte ++ ( out byte A );
native(139) static final postoperator byte ++ ( out byte A );

One’s a preoperator, the other’s a postoperator, everything else is the same. Then there are operators in which everything is the same, but one’s argument is an “out”, the other one’s isn’t.

Now, my grammar treats preoperator, postoperator, out and other words as keywords. I could’ve treated them as special words and differentiated functions based on their presence/absence, but I needed to get scope resolution for variables inside functions to work as detailed at the beginning of this post, so I decided to just do that instead.

There are several blog posts on scope resolution written by the guys it Itemis, but most of them are conceptual posts which outline how the scope resolution works internally, and how it has changed from Xtext 1.0 to 2.0. There are none (that I could find) which tell you how to get it to work.

In order to resolve variables declared inside other variables (members of structs, members of classes etc.), I have a grammar rule called “QualifiedIdentifier” defined as follows:

QualifiedIdentifier:
    ( ( 'class' SQUOTE classRef=[ClassDecl] SQUOTE (DOT 'default')?
        ( {Selection.receiver=current} DOT (child=[DeclaredVariable|Word]) )* ) |
        ( ( (parent=[DeclaredVariable|Word]|parentFunctionCall=FunctionCall)
            (LSBRACK arrayIndex=Operand RSBRACK)? )
          ( {Selection.receiver=current} DOT
          ( (child=[DeclaredVariable|Word]|childFunctionCall=FunctionCall)
            (LSBRACK arrayIndex=Operand RSBRACK)? ) )* ));

Possible references for child are resolved as follows:

public class UnrealscriptScopeProvider extends AbstractDeclarativeScopeProvider {
    public IScope scope_Selection_child(Selection sel, EReference ref) {
        EObject parent = sel.getReceiver().getParent();
        if (parent != null) {
            if (parent instanceof DeclaredVariable) {
                DeclaredVariable dvar = (DeclaredVariable)parent;
                return getFieldScopeFor(dvar);
            }
        }
        else {
            System.out.println("Parent = " + parent);
        }
    }

    return IScope.NULLSCOPE;
}

Which works if parent is resolved to the correct reference. However, in the example with operator - for int and vector outlined above, I needed the parent to get resolved correctly. Tried declaring scope_Selection_parent, but it didn’t get called. Finally overrode

public IScope getScope(EObject context, EReference reference);

And ran a live debugging session to find out what context was an instance of and what its Container was. That let me know that context was an instance of QualifiedIdentifier, and the container was also QualifiedIdentifier. Hence, I ended up with

public IScope scope_QualifiedIdentifier_parent(QualifiedIdentifier context, EReference ref);

Now, I needed this function to return a LinkedScope, meaning it would return a scope which would first search in all local variable declarations, then in the function arguments, and finally in the global scope. Further complicating this were the requirements:

  1. Unrealscript is case-insensitive
  2. All super class members are inherited by a child class

For the first requirement, I would have to return a SimpleScope. The second requirement was already handled by my grammar since I use Imported Namespaces, but I had no idea how I would go about getting the imported scope inside my function. So, I put a breakpoint at the entry of this function, and checked where it was getting called from. Turns out it uses some form of delegates (Java is not really my strong suit, I haven’t written any big programs in it, I basically picked it up by knowing C/C++ and looking at existing Java code). The parent function is

public abstract class AbstractDeclarativeScopeProvider extends AbstractScopeProvider {
    public IScope getScope(EObject context, EReference reference) {
        IScope scope = polymorphicFindScopeForReferenceName(context, reference);
        if (scope == null) {
            scope = polymorphicFindScopeForClassName(context, reference);
            if (scope == null) {
                scope = delegateGetScope(context, reference);
            }
        }

        return scope;
    }
}

polymorphicFindScopeForReferenceName is the one that eventually calls my function, so on a hunch I tried calling polymorphicFindScopeForClassName with my context and reference, and what-do-you-know, I got my global imported scope! (it returns an ImportScope) So, my final working code looks like this:

public class UnrealscriptScopeProvider extends AbstractDeclarativeScopeProvider {
    public IScope getGlobalScope(EObject context, EReference reference) {
        EObject parent = context;
        IScope scope = IScope.NULLSCOPE;
        while (parent.eContainer() != null) {
            parent = parent.eContainer();
            if (parent instanceof Model) {
                scope = getScope(parent, reference);
            }
        }

        return scope;
    }

    public IScope scope_QualifiedIdentifier_parent(QualifiedIdentifier context, EReference ref) {
        EObject parent = context;
        IScope localScope = IScope.NULLSCOPE,
               argScope = IScope.NULLSCOPE,
               globalScope = IScope.NULLSCOPE;

        while (parent.eContainer() != null) {
            parent = parent.eContainer();
            if (parent instanceof FunctionBody) {
                FunctionBody fb = (FunctionBody)parent;
                List<LocalDeclaration> localDeclarations = fb.getLocalDeclarations();
                List<FunctionArg> functionArgs =
                    ((FunctionDeclaration)(fb.eContainer())).getFunctionArgList();
                List<VarName> localVarNames = new LinkedList<VarName>();

                for (LocalDeclaration ld: localDeclarations) {
                    localVarNames.addAll(ld.getVarDeclaration().getVarNames());
                }

                globalScope = getGlobalScope(context, ref);
                localScope = new SimpleScope(globalScope,
                                             Scopes.scopedElementsFor(localVarNames),
                                             true);
                argScope = new SimpleScope(localScope,
                                           Scopes.scopedElementsFor(functionArgs),
                                           true);
                break;
            }
        }

        return argScope;
    }
}

The important part here is:

globalScope = getGlobalScope(context, ref);
argScope = new SimpleScope(globalScope, Scopes.scopedElementsFor(functionArgs), true);
localScope = new SimpleScope(argScope, Scopes.scopedElementsFor(localVarNames), true);
//...
return localScope;

The first argument to the constructor of SimpleScope is the parent scope:

public SimpleScope(IScope parent, Iterable<IEObjectDescription> descriptions, boolean ignoreCase) {
    super(parent, ignoreCase);
    if (descriptions == null)
        throw new IllegalArgumentException("descriptions may not be null");

    this.descriptions = descriptions;
}

So the scope that is returned looks like: localScope -> argScope -> globalScope. While trying to resolve a particular reference, the linked will first look in the local scope, then look at the arguments, and then finally at the global scope. And this works perfectly :)

Here’s a video I made of scope resolution in action. The reason I made a video is because it’s hard to show something like “Jump to declaration” in screenshots. The most one could do is post a screenshot before the jump and one after the jump, which doesn’t really prove anything.