5
$\begingroup$

I'm trying to find an algorithm/data structure behind type resolution without forward declaration. Something a little bit like this in Java:

class Test2 {      
  public static void main(String[] args) {    
    Test1 t1 = new Test1();       
  }
}    
class Test1 {}

While Test1 is not known when parsing Test2, it is somehow later recognized as valid.

I believe this is made in multiple passes:

  • Somehow build the scopes from the AST (given by parsing).
  • Go through all the declaration using user-defined types and check if they are available from the current scope.

But I'm looking for some explanation of the most common ways of solving this. I cannot find that much around this topic (maybe due to poor knowledge on the jargon) and I don't want to reinvent the wheel.

$\endgroup$
3
  • 2
    $\begingroup$ Are you looking at identifying types in particular, or name resolution in general? $\endgroup$ Commented Jul 5, 2023 at 5:19
  • $\begingroup$ mostly types for now, but name resolution might in fact come later. I'm interested in what you have around these topics. $\endgroup$ Commented Jul 5, 2023 at 5:22
  • 1
    $\begingroup$ "But I'm looking for some papers/blog/... explaining the most common ways of solving this." ─ requests for off-site resources are off-topic here. But this question would be on-topic if you just asked about how this can be implemented. $\endgroup$ Commented Jul 5, 2023 at 11:19

1 Answer 1

Reset to default
3
$\begingroup$

Implementing forward references does indeed require two passes: one to discover the set of available definitions, and another to resolve names to those definitions.

(Type names can typically be resolved in the same way as other names, and type checking is a separate problem entirely, so I will just talk about name resolution here. I will also stick to early binding and lexical scoping- sometimes forward references are actually implemented by runtime name lookup/late binding, but that seems unlikely to apply to this question about types.)

One direct approach is to build a tree of scopes, each represented as a map of names to definitions. The structure of this tree will typically match the structure of the syntax tree pretty closely, with (in Java, for example) a package-level root node, child nodes for classes, grandchild nodes for methods, etc.

These passes don't necessarily need to run on the entire program. Rather, the first pass only needs to process definitions that are in scope and thus may be needed by the second pass. So, another approach replaces the tree of scopes with a stack of scopes: collect all the definitions (or at least those can be used by forward reference) in a scope and push that onto the stack before descending into nested scopes; pop it off the stack when leaving the scope.

Resolving a reference involves walking up the tree or stack, starting from the referencing scope and going up to parents until a matching definition is found.

A few potential complications:

  • Qualified names involve multiple individual name lookups, often using different rules about how to walk the scope tree. (For example, you may not want Foo.Bar to find a Bar in some parent of Foo.)
  • Imports, and especially globs, can influence the walk as well. Sometimes this involves coming up with some rules around how to resolve, report, or avoid ambiguities and cycles.
  • Some language features can tangle up these two passes even further, when figuring out what a definition even means depends on some amount of name lookup. For example, macros that expand to definitions sometimes run into this.
$\endgroup$
1
  • $\begingroup$ I actually tried the stack of of maps model before, the problem though was that I didn't figure out the "walking up the tree" part. That makes more sense. For the imports, i recently noticed this. But I guess the imports can be parsed before all of the process you describe and the problem will be solved. What do you think? $\endgroup$ Commented Jul 6, 2023 at 1:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.