<p>In my language that is similiar to Java, one <code>type</code> from a program's package block can rely on the <code>type</code> of another program's package block. Other things also mix on, such as <code>import</code>, <code>namespace</code> aliases and <code>use namespace</code> directives.</p>
<p>E.g. this can be resolved in one pass:</p>
<pre><code>package q.b {
    public type N = Number
}
package {
    import q.b.N
}
</code></pre>
<p>But one package block can rely on the other in different ways:</p>
<pre><code>package q.b {
    public namespace N1 = q.b.N2
    public namespace N2 {
    }
}
</code></pre>
<p>The problem here is that <code>N2</code> is defined after <code>N1</code> is assigned as an alias of <code>N2</code>, where <code>N2</code> does not even exist yet. Clearly more than one verification pass is necessary. What strategy can I use?</p>
<p>Also worthy noting <code>type</code> can have a complex right-hand side, like a function type. <code>import</code> can be an alias, e.g., <code>import y = q.x</code> and <code>use namespace</code> can have a constant expression. Although for <code>use namespace</code> the expression is generally simple.</p>

<symbol-solving>
Compile-time reference resolution across Java-like packages
<p>In the <a href="https://link.springer.com/chapter/10.1007/978-3-662-46669-8_9" rel="nofollow noreferrer">A Theory of Name Resolution</a> paper late Eelco Visser developed a Scope Graphs model that encompasses almost all name binding semantics from programming languages, including <code>let</code>, <code>let rec</code>, function parameters and <code>import</code>s.</p>
<p>Purely descriptive model of Scope Graphs is augmented with a declarative constraint-based language to specify the name resolution rules. As long as the language is pure and declarative, it admits optimized search strategies with lazy caching and parallel execution, see recent papers from TU Delft <a href="http://pl.ewi.tudelft.nl/publications/" rel="nofollow noreferrer">PL Group</a>.</p>
<p>As a fun aside, for the &quot;Go to definition&quot; feature GitHub implemented <a href="https://github.blog/2021-12-09-introducing-stack-graphs/" rel="nofollow noreferrer">Stack Graphs</a> based on Visser's Scope Graphs. :)</p>

CC BY-SA 4.0
2023-05-27T09:23:20.250Z
2023-05-27T09:23:20.250Z
Alex Chichigin
<p>In my compiler, I simply collected what could not be resolved in one pass and resolved in multiple times until a limit.</p>
<p>E.g. regarding <code>type</code>:</p>
<ul>
<li>First pass:
<ul>
<li>If the right-hand side produces a diagnostic, e.g., a VerifyError, collect the <code>type</code> definition and defer its resolution.</li>
</ul>
</li>
<li>Another pass (repeats until no unresolved item is remaining or until a limit)
<ul>
<li>If the right-hand side does not produce a diagnostic, remove the <code>type</code> definition from the collection of unresolved definitions.</li>
</ul>
</li>
<li>Visit all unresolved definitions and resolve them by the last time.</li>
</ul>
<p>This is also done similiarly to <code>import</code>, <code>namespace</code> and <code>use namespace</code>.</p>
<p>Note that things like classes, enums and interfaces are resolved partially across passes, so they aren't resolved similiarly to these items above.</p>

CC BY-SA 4.0
2023-05-26T21:20:08.880Z
2023-05-26T22:19:06.073Z
2023-05-26T22:19:06.073Z
Hydroper
<p>One elegant solution would involve making the compilation process asynchronous. Whenever the compilation routine encounters a name that has to be resolved, it awaits the resolution result. Under the hood, that results in the task suspending its execution and giving way to other compilation tasks, while perodically being woken up by the scheduler, checking if the expected object has become available, and if not, going to sleep again. On the other hand, whenever the compilation has to process an unordered scope (i.e. the body of a file, a namespace or a class - anything but a function, pretty much), instead of going over the contained elements in order, it introduces the containing object and then spawns new compilation tasks for every contained element and awaits them in total ('gather'). If at some point a complete deadlock is encountered (i.e. all tasks are awaiting some definitions), you give a compilation error about a bad recursive reference. (This won't happen for allowable recursion as long as you introduce a 'partial' definition for every element prior to processing all of its subelements. For instance, to process a function call you don't need its contents, so an incomplete function definition should exist before its body is handled). When there are no tasks left, you're done.</p>
<p>(Note that asynchronousness here has nothing to do with threads and parallelism. It's just a way to express segmentable tasks with complicated dependencies).</p>
<p>I'm not sure if this approach has been implemented before, and there might be caveats I haven't considered, but it seems like it would work quite well</p>

CC BY-SA 4.0
2023-05-27T16:20:27.217Z
2023-05-27T17:01:56.933Z
2023-05-27T17:01:56.933Z
abel1502
# Compile-time reference resolution across Java-like packages
Posted by: username_0 on 2023-05-26
In my language that is similiar to Java, one type from a program's package block can rely on the type of another program's package block. Other things also mix on, such as import, namespace aliases and use namespace directives.
E.g. this can be resolved in one pass:
package q.b {
    public type N = Number
}
package {
    import q.b.N
}

But one package block can rely on the other in different ways:
package q.b {
    public namespace N1 = q.b.N2
    public namespace N2 {
    }
}

The problem here is that N2 is defined after N1 is assigned as an alias of N2, where N2 does not even exist yet. Clearly more than one verification pass is necessary. What strategy can I use?
Also worthy noting type can have a complex right-hand side, like a function type. import can be an alias, e.g., import y = q.x and use namespace can have a constant expression. Although for use namespace the expression is generally simple.
**Tags:** symbol-solving
---
## 3 answers
### Answer by username_0 on 2023-05-26. Score: 5
In my compiler, I simply collected what could not be resolved in one pass and resolved in multiple times until a limit.

E.g. regarding `type`:

* First pass:
  + If the right-hand side produces a diagnostic, e.g., a VerifyError, collect the `type` definition and defer its resolution.
* Another pass (repeats until no unresolved item is remaining or until a limit)
  + If the right-hand side does not produce a diagnostic, remove the `type` definition from the collection of unresolved definitions.
* Visit all unresolved definitions and resolve them by the last time.

This is also done similiarly to `import`, `namespace` and `use namespace`.

Note that things like classes, enums and interfaces are resolved partially across passes, so they aren't resolved similiarly to these items above.
---
### Answer by username_2 on 2023-05-27. Score: 4
One elegant solution would involve making the compilation process asynchronous. Whenever the compilation routine encounters a name that has to be resolved, it awaits the resolution result. Under the hood, that results in the task suspending its execution and giving way to other compilation tasks, while perodically being woken up by the scheduler, checking if the expected object has become available, and if not, going to sleep again. On the other hand, whenever the compilation has to process an unordered scope (i.e. the body of a file, a namespace or a class - anything but a function, pretty much), instead of going over the contained elements in order, it introduces the containing object and then spawns new compilation tasks for every contained element and awaits them in total ('gather'). If at some point a complete deadlock is encountered (i.e. all tasks are awaiting some definitions), you give a compilation error about a bad recursive reference. (This won't happen for allowable recursion as long as you introduce a 'partial' definition for every element prior to processing all of its subelements. For instance, to process a function call you don't need its contents, so an incomplete function definition should exist before its body is handled). When there are no tasks left, you're done.

(Note that asynchronousness here has nothing to do with threads and parallelism. It's just a way to express segmentable tasks with complicated dependencies).

I'm not sure if this approach has been implemented before, and there might be caveats I haven't considered, but it seems like it would work quite well
---
### Answer by username_1 on 2023-05-27. Score: 3
In the [A Theory of Name Resolution](https://link.springer.com/chapter/10.1007/978-3-662-46669-8_9) paper late Eelco Visser developed a Scope Graphs model that encompasses almost all name binding semantics from programming languages, including `let`, `let rec`, function parameters and `import`s.

Purely descriptive model of Scope Graphs is augmented with a declarative constraint-based language to specify the name resolution rules. As long as the language is pure and declarative, it admits optimized search strategies with lazy caching and parallel execution, see recent papers from TU Delft [PL Group](http://pl.ewi.tudelft.nl/publications/).

As a fun aside, for the "Go to definition" feature GitHub implemented [Stack Graphs](https://github.blog/2021-12-09-introducing-stack-graphs/) based on Visser's Scope Graphs. :)
---
