Forward Reference Validation

[snarkipus]

Tag: @msujew

• Example Repo

I'm working through the Forward Reference validation portion in this book since I'll need that functionality for my implementation.

For reference, the following are examples of illegal forward references that are otherwise valid.

// Illegal forward reference
var i = j + 1
var j = 0

// Illegal mutual dependency
var i = j + 1
var j = i + 1

The validator requires a utility class (ExpressionsModelUtil) that checks for prior variable declarations before a reference occurs. As such, I'm trying to build an analog of this class using the Langium framework and TypeScript, hopefully using features in the generated ast.ts file. This author seems to LOVE the dynamic dispatch and extension methods features of Xtend, which I find somewhat non-intuitive as a newcomer.

Here is the reference Xtext/Xtend implementation.

package org.example.expressions

import org.example.expressions.expressions.VariableRef
import org.example.expressions.expressions.Expression
import org.example.expressions.expressions.AbstractElement
import org.example.expressions.expressions.ExpressionsModel
import org.example.expressions.expressions.Variable

import static extension org.eclipse.xtext.EcoreUtil2.*

class ExpressionsModelUtil {
	def isVariableDefinedBefore(VariableRef varRef) {
		varRef.variablesDefinedBefore.contains(varRef.variable)
	}
	
	def variablesDefinedBefore(Expression e) {
		e.getContainerOfType(AbstractElement).variablesDefinedBefore
	}
	
	def variablesDefinedBefore(AbstractElement containingElement) {
		val allElements = (containingElement.eContainer as ExpressionsModel).elements
		
		allElements.subList(0, allElements.indexOf(containingElement)).typeSelect(Variable).toSet
	}
	
}

Here is what I've got so far ... which seems to be pretty close ... but I'm somewhat stuck. Before I spend a massive amount of time trying to fix it, I just wanted to make sure this approach was even sound or idiomatic. There's a couple of assumptions regarding Xtext/ECore equivalence I made which may not be valid (i.e. AbstractElement.eContainer() is the same as AbstractElement.$container, getContainerOfType() implementation, etc.).

import { AstNode } from "langium";
import { VariableRef, Expression, AbstractElement, ExpressionsModel, ExpressionsAstType } from "../language-server/generated/ast";
import { isExpression, isVariable, isAbstractElement, reflection } from "../language-server/generated/ast";

export class ExpressionsModelUtil {

    public isVariableDefinedBefore(varRef: VariableRef): boolean {
        this.variablesDefinedBefore(varRef).has(varRef.variable);
        return true;
    }

    public variablesDefinedBefore(e: Expression | AbstractElement)  {
        // traverse the AST 
        if (isExpression(e)) {
            this.variablesDefinedBefore(getContainerOfType(e, AbstractElement) as Expression | AbstractElement);
        } 
        // collect the variables
        else if (isAbstractElement(e)) {
            const allElements = (e.$container as ExpressionsModel).elements;
            return new Set(allElements
                .slice(0, allElements.indexOf(e))
                .filter(e => isVariable(e)));
        }
    }
}

function getContainerOfType(ele: AstNode, type: ExpressionsAstType ): any {
    for (let e = ele; e !== null; e = e.$container as AstNode) {
        if (reflection.isInstance(e, type)) {
            return e;
        }
        return null;
    }
}

Grammar (partial)

grammar Expressions

entry ExpressionsModel:
	elements += AbstractElement*
;

AbstractElement:
	Variable | EvalExpression
;

Variable:
	'var' name=ID '=' expression=Expression
;

EvalExpression:
	'eval' expression=Expression
;
...

[msujew]

Hey @snarkipus,

multiple thoughts on this:

1. We actually implement a getContainerOfType function in Langium, which is typed a bit better than yours. You can use it like this:

const abstractElement = getContainerOfType(e, isAbstractElement); // Through typescript magic, `abstractElement` is automatically typed as `AbstractElement | undefined`

2. Your getContainerOfType function actually uses null. We don't use null usually in Langium, but undefined instead. They have different semantic meanings (usually), and also behave differently in equality checks or typeof checks. See also this.
3. I believe this relatively simplistic way of finding previous variables stops working once you start working on multiple block levels and can become progressively complicated when you try to deal with those. Going at this problem from another perspective might be better: Instead of finding all elements that precede the current variable and see whether it contains the reference (which is also relatively computationally expensive), we can use the CST to do the job. Something like this should suffice:

export function isDefinedBefore(from: AstNode, to: AstNode): boolean {
  const fromDocument = getDocument(from);
  const toDocument = getDocument(to);
  // In case a variable from another document is referenced (might be illegal?)
  if (fromDocument !== toDocument) {
     return false;
  }
  if (!from.$cstNode || !to.$cstNode) {
    return false;
  }
  const fromPosition = from.$cstNode.offset;
  const toPosition = to.$cstNode.offset;
  return fromPosition < toPosition;
}

You can call that function using your expression in which the reference appears as from and the referenced variable as to.

[msujew]

There has been a breaking change in order to support web based Langium server. You can take a look at our examples on how to resolve it. Basically, what kind of object we pass into our internal DI functions changed a bit.

[snarkipus]

Interesting, the resolution for the breaking change must not have been incorporated (yet) into the yeoman template for the hello-world default project. It works as described using the example projects linked against local langium packages.

[snarkipus]

@msujew I'm not smart enough to figure it out I suppose - the hello-world example works just fine if I run it inside the main langium project (i.e. in the examples directory). Trying to do the same thing outside of it results in the error I showed earlier. Not a huge deal, but I do wish I understood why it's dying. I can't see that it's related to the change you linked necessarily.

[msujew]

Actually, I didn't properly read your message (we currently have a week-long team event at TypeFox, little time to actually work). The issue is that we updated the vscode-languageserver library to 8.0.1, which isn't compatible with the old version (7.0). I created a small patch for you to apply to your langium-expressions repo: patch.zip

[snarkipus]

No worries @msujew - thank you very much for the patch, I'll give it a shot. In the meantime, since it's a relatively small example language, I just created a dev branch and recreated the project inside the workspace (here). That will have to do for now until I can figure out a more elegant solution.

Ideally, I'd be able to keep them separate since this approach breaks some of the dev tooling (i.e. Wallaby.js).