<p>I'm trying to find an algorithm/data structure behind type resolution without forward declaration. Something a little bit like this in Java:</p>
<pre class="lang-java prettyprint-override"><code>class Test2 {      
  public static void main(String[] args) {    
    Test1 t1 = new Test1();       
  }
}    
class Test1 {}
</code></pre>
<p>While <code>Test1</code> is not known when parsing <code>Test2</code>, it is somehow later recognized as valid.</p>
<p>I believe this is made in multiple passes:</p>
<ul>
<li>Somehow build the scopes from the AST (given by parsing).</li>
<li>Go through all the declaration using user-defined types and check if they are available from the current scope.</li>
</ul>
<p>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.</p>

<semantics><type-checker>
Algorithm for type resolution without forward declaration
CC BY-SA 4.0
2023-07-05T05:19:28.973Z
Are you looking at identifying *types* in particular, or name resolution in general?
Michael Homer
CC BY-SA 4.0
2023-07-05T05:22:07.893Z
mostly types for now, but name resolution might in fact come later. I'm interested in what you have around these topics.
Clément Jean
CC BY-SA 4.0
2023-07-05T11:19:20.813Z
*"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](https://langdev.meta.stackexchange.com/q/261/89). But this question would be on-topic if you just asked about how this can be implemented.
kaya3
<p>Implementing forward references does indeed require two passes: one to discover the set of available definitions, and another to resolve names to those definitions.</p>
<p>(Type names can typically be resolved in the same way as other names, and type <em>checking</em> 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.)</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>A few potential complications:</p>
<ul>
<li>Qualified names involve multiple individual name lookups, often using different rules about how to walk the scope tree. (For example, you may not want <code>Foo.Bar</code> to find a <code>Bar</code> in some parent of <code>Foo</code>.)</li>
<li>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.</li>
<li>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.</li>
</ul>

CC BY-SA 4.0
2023-07-05T23:00:28.210Z
2023-07-05T23:00:28.210Z
rpjohnst
CC BY-SA 4.0
2023-07-06T01:39:43.397Z
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?
Clément Jean
# Algorithm for type resolution without forward declaration
Posted by: username_0 on 2023-07-05
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.
**Tags:** semantics type-checker
> **Comments:**
> **username_1**: Are you looking at identifying *types* in particular, or name resolution in general?  
> **username_0**: mostly types for now, but name resolution might in fact come later. I'm interested in what you have around these topics.  
> **username_2**: *"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](https://langdev.meta.stackexchange.com/q/261/89). But this question would be on-topic if you just asked about how this can be implemented.  
---
## 1 answers
### Answer by username_3 on 2023-07-05. Score: 3 | Accepted answer
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.
> **Comments:**
> **username_0** (2023-07-06): 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?  
---
