3

Let's say, hypothetically, I'm writing a Java compiler. And we assume that in my case a class can't be fully compiled until all signatures of dependencies (imports and other used classes) are known. Because I don't want to keep the source code and AST of all classes in memory at the same time, I'll need an algorithm to manage those dependencies and process them all in the right order.

What would be a good algorithm for ordering all dependencies? That:

  • is not recursive
  • does not keep all source code and/or ast nodes in memory
  • is linear in both space and time
  • can handle cyclical dependencies

Or maybe more general, how is this normally done?

My approach looks like the following:

abstract class Compiler {

    TypeSystem ts;


    Type compile(String className) {

        if (ts.containsType(className)) {
            return ts.getType(className);
        }

        // Create skeleton type for this class:
        Type type = ts.createType(className);

        // Parse the class file:
        Node ast = parse(className);

        // Create signature:
        for (Node attribute : ast.findAll("AttributeDeclaration")) {

            // Get the text value of the name of the attribute:
            String attributeName = attribute.find("Identifier").text();

            // Get the text value of the type of the attribute:
            String attributeTypeName = attribute.find("Type").text();

            // Call compile recursive!
            Type attributeType = compile(attributeTypeName);

            type.createAttribute(attributeName, attributeType);
        }

        return type;
    }

    abstract Node parse(String className); // This method can find the file by class name.
}                

For sake of simplicity, does this code only process attributes and simple structs. Note that this algorithm is recursive!

  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Sep 21 '15 at 19:22
  • 2
    You might read about dependency graphs. – Caleb Sep 21 '15 at 19:29
  • @Caleb Is that normally used for dependency ordering in compilers, by your knowledge? – Tim Sep 21 '15 at 19:30
  • You don't need a full AST of dependencies, you need only the signatures of accessible elements. – Andy Dalton Sep 21 '15 at 19:34
  • 3
    Not 2 parses, 2 passes. The second pass can be of an in-memory representation of the file. If there isn't an existing class file for class B and class A has a dependency on class B, the compiler can translate B first, generate the class file, then translate A; the translation of A can use B.class (or the compiler can keep info about B in memory). If A and B are interdependent, it may load the full AST for both at the same time. – Andy Dalton Sep 21 '15 at 20:10
5

To compile a source file, you do not need to have compiled all dependencies before it. However, you do need something to link against: a kind of interface or header. In languages like Java, this is fairly simple since all user defined types have reference semantics. The structure and implementation of a type do not matter, only that it is named. Therefore, you can hoist all type names that occur in a compilation unit and its dependencies to the “top”.

E.g. assume that I have two classes in two separate files:

Foo:

class Foo {
  public void frobnicate(Bar b) {
    if (rand) b.frobnicate(this);
  }
}

Bar:

class Bar {
  public void frobnicate(Foo f) {
    if (rand) f.frobnicate(this);
  }
}

The type and definition of frobnicate is mutually recursive. This can be compiled by doing an initial pass that extracts the interface of these classes. The interface is then referenced when compiling the actual implementations in a second pass. Although this strategy does multiple passes, it's still linear, and it need not keep the whole AST in memory – only the type signatures.

Header:

// predeclare type names
class Foo;
class Bar;

// predeclare available operations
class Foo {
  public void frobnicate(Bar); // type Bar is known
}
class Bar {
  public void frobnicate(Foo); // type Foo is known
}

Foo:

#include Header
// implement the pre-declared function
void Foo::frobnicate(Bar b) {
  if (rand) b.frobnicate(this); // method Bar::frobnicate(Foo) is known
}

Bar:

#include Header
void Bar::frobnicate(Foo f) {
  if (rand) f.frobnicate(this);  // method Foo::frobnicate(Bar) is known
}

In languages such as C or C++, these dependencies have to be resolved manually using such predeclarations. C was specifically designed around space-efficient single-pass compilation, though this trades in compilation speed since all header dependencies will be re-parsed again for each compilation unit.

This pre-declaration strategy only works for user-defined types that have reference semantics. If a type has value semantics, it must be completely defined before it can be used. Switching to C++, this pre-declared Incomplete type can be used in a Complete type since the size of a pointer is known:

struct Incomplete;

struct Complete {
  Incomplete* thing;
};

However, embedding an incomplete type without a pointer would not work; the embedded type would have to be completely defined first.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.