I'm currently writing a compiler for a new language and I'm struggling with the linking aspect of new Types when there exists a circular reference.
I've created a dependency tree so that I can compile the Types in the order of their dependencies which seemed to have fixed my problem… that is until I hit circular references like an example below (posted in c#):
public class A
{
public A() { var b = new B(); }
}
public class B
{
public B() { var a = new A(); }
}
My limitation is that I can only create 1 Type at a time, and in the case of circular references, either A needs to be created first, or B needs to be created first, both of which poses the problem that I can't create either unless it's dependencies are first created!
How do compilers overcome this?
Best Answer
In general, you create A and add it to the scope. When you get to resolve B, you go and build B. When that gets to resolving A, it finds a (partially) constructed type and grabs that reference. Then you return back to building A.
There are other situations that are more problematic (like cyclical inheritence, dll references, recursive type declarations) that often require placeholder types or are simply not viable given other design constraints. In general, keeping each compilation phase thin helps prevent issues. For example, you can only do the partial type trick if nothing needs to know the members of A in B.