Compiler Linking: How to handle circular references?

Question

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?

Answer 1

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.

Answer 2

I think you're trying to solve in the compiler something that should be resolved by the linker. Both A and B should compile to whatever intermediate code they use (traditionally an object file) and just list the other type as an external symbol. When you generate the executable form, you go through the symbol table for each object file and resolve the external references. See this for a good introduction to traditional linkers.

Answer 3

How do compilers overcome this?

Some languages (C++, Objective-C) allow forward declarations which introduce the type but don't define it. It'd go something like:

public class B;  // now the compiler knows that B is a class that will be defined later

public class A
{
  public A() {  var b = new B(); }
}

public class B
{
  public B() { var a = new A(); }
}

That said, even a forward declaration won't solve the circular problem in your example: Creating a new A will create a new B, which in turn will create another A, which will create another B, and so on. If you want one A and one B that point to each other, you'll need to create constructors that take a reference to an existing object, like:

public class A
{
  public A(B _b) { var b = _b; }
  public A()     { var b = new B(this); }  // 'this' is a C++-style pointer to the current object
}