Dependency graph of Java-like imports and aliases

Compilers
1

Terminology

My scripting language’s execution consists of three phases: parsing, verification and evaluation, much like ActionScript.

The verifier ensures the program is correct at compile-time. For example, it checks if a lexical reference resolves to a known variable or if a binary expression has operands of compatible types.

The verifier ends up solving symbols and thus extracting compile-time information from the program.

“Frames” or lexical frames, are simply scopes. For example, an activation frame, package frame, a class frame or an ordinary frame.

The Problem

I’ve done verifiers for my language before. In the first phase I typically partially define the symbol of original definitions such as classes, interfaces, enums and function definitions.

Partially defining them is like creating a stub symbol with no extends clause resolved, without the inner block resolved and more. Then, in next phases the definitions are further resolved, including the extends clause of a class definition.

So, right now, I know what to do in the first phase: partial definitions for original items like classes, like I said before. Next, I need to resolve alias and import items, that is:

  • type definitions (aka. type aliases),
  • namespace alias definitions,
  • import directives and
  • use namespace directives.

Basically, for activations (aka. function scopes) and anonymous blocks, these items are currently resolved in sequence order, pretty simple! But in package-fragmented context, I need to analyze these items structurally to derive a dependency graph and finally resolve them in the right order.

I’m already collecting a list of all of these import and alias items. I’m also attaching their surrounding frame to their nodes.

For example, that is how these items are resolved in activations and anonymous blocks:

That is currently what I’ve for the verification of the program-fragmented import/alias items:

A lexical reference or member expression escapes from an “alias” symbol: violetc/expressions.cs at master · violetscript/violetc · GitHub

That’s an example program illustrating what I need to solve:

package q.a
{
    public type Ta = q.b.Tb; // type 'Tb' is undefined at this point
}
package q.b
{
    public type Tb = (a:Number) => void;
}

You can see that Ta is defined before Tb is defined. I need to gather a dependency graph from the collection mentioned earlier and resolve the items in the right order. I’m saying this because it’s not possible to partially create the “alias” symbol and anyway the reference expressions automatically escape out of any alias symbol.

Anyone has a good algorithm?

Complexity

About type aliases: There are not many type expressions, so type A = B;'s right operand is not very complex.

About namespace aliases and use namespace: There are many expressions and namespace Na = Nb; has an expression as its right operand and use namespace N; too has an expression operand. However, the expression these items use is a constant expression, usually just a lexical reference or a series of member expressions (like namespace Na = q.f.No;). So these items are much simpler than type definitions.

About import: simple to analyze.

2

Hm, I came with a better idea. Instead of re-arranging these items with a dependency graph I’ll simply attempt to resolve them multiple times. The limit of attempts will be, say, 10. Beyond 9, I’ll report any diagnostics.

1 Like
3

The standard solution is to use a topological sort on the dependency graph.
The topological order is the order in which you want to process things.
If you have cycles, then you need to process all the elements in the cycle at the same time.

1 Like
4

Though it happens that I need to build the dependency graph anyway. So not just a topological sort is needed, but also structural analysis (visiting nodes deep in each import/alias).

1 Like