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 recursivedoes not keep all source code and/or ast nodes in memoryis linear in both space and timecan 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!
Dependency ordering algorithm of a compiler
java;algorithms;compiler;graph;dependencies
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 namesclass Foo;class Bar;// predeclare available operationsclass 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 functionvoid Foo::frobnicate(Bar b) {  if (rand) b.frobnicate(this); // method Bar::frobnicate(Foo) is known}Bar:#include Headervoid 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.