CS:2820 Notes, Lecture 38

As a result of documenting the inter-class dependencies in the makefile for the traffic simulator, we ended up triggering some warning messages from make:

[dwjones@fastx02 ~/project]$ make
javac Error.java
javac MyScanner.java
javac Simulator.java
make: Circular Intersection.class <- Road.class dependency dropped.
make: Circular NoStop.class <- Intersection.class dependency dropped.
make: Circular NoStop.class <- Road.class dependency dropped.
javac NoStop.java
javac Source.java
make: Circular Sink.class <- Intersection.class dependency dropped.
make: Circular Sink.class <- Road.class dependency dropped.
make: Circular StopLight.class <- Intersection.class dependency dropped.
make: Circular StopLight.class <- Road.class dependency dropped.
javac Road.java
javac RoadNetwork.java
[dwjones@fastx02 ~/project]$

It seems that make is not really happy with makefiles containing circular dependencies. In our case, we have circular dependencies between classes Road and Intersection, and we have circular dependencies between class Intersection and its subclasses.

The Java language itself is not particularly bothered by circular dependencies, but these cause problems in some other object-oriented programming languages. C++, for one, is less tolerant of circular dependencies.

A strategy for Eliminating Circular Dependencies

Consider the following skeleton describing one circular dependency in our road-network simulator:

Each class above contains instance variables that refer to objects of the other classes, and class Intersection contains methods that take parameters of the other class or return instances of the other class.

The key, in Java, to eliminating circularity, is to add some layers of either interfaces or abstract classes. For each cycle, at least one class in the cycle must be broken into two. So if class A and B are in a circular relationship, we can make class AA depend on class B which depends on interface or abstract class A. For the road-network example, we can break up class road as follows:

interface Road {
    ... public method interfaces ...
}

class Intersection {
    private final LinkedList  outgoing = new LinkedList 
    protected final LinkedList  incoming = new LinkedList 

    public abstract void addIncoming( Road r, int q );
    public void addOutgoing( Road r ) { ... deleted code ... }
    public Road pickOutgoing() { ... deleted code ... }

    ... other methods ...
}

class RoadImp implements Road {
    private final Intersection destination;
    private final Intersection source;

    ... public method implementations ...
}

In the above, class RoadImp depends on class Intersection and on class Road, and class Intersection depends only on class Road.

We could not easily split class Intersection because class Road turns relies on the static method Intersection.lookup(), and it uses the addOutgoing(), addIncoming() and enter() methods of Intersection instances, and it also directly accesses the name field. What we can do, however, is split both Road and Intersection:

interface Road {
    ... public method interfaces ...
}

interface Intersection {
    public void addIncoming( Road r, int q );
    public void addOutgoing( Road r );
    public Road pickOutgoing();

    ... other public methods interfaces ...
}

class RoadImp implements Road {
    private final Intersection destination;
    private final Intersection source;

    ... various methods ...
}

class IntersectionImp implements Intersection {
    private final LinkedList  outgoing = new LinkedList 
    protected final LinkedList  incoming = new LinkedList 

    // public abstract void addIncoming( Road r, int q );
    public void addOutgoing( Road r ) { ... deleted code ... }
    public Road pickOutgoing() { ... deleted code ... }

    ... other methods ...
}

Assessment

Does this work? The code distributed with these lecture notes compiles and runs correctly, but unfortunately, it still contains some circular dependencies between the interfaces. Consider the following bits and pieces: Java gives you the choice of using interfaces or classes. This choice does not always work the same in other languages. Some languages only have class hierarchies, while others use vastly different models for what Java calls an interface and the corresponding category of class hierarchy.

public interface Road {
    public void enter( double time, Vehicle v );
}

public interface Intersection {
    void setIncoming( Road r );
    void arrive( double time, Vehicle v, int dir );
}

public interface Vehicle {
    Road pickOutgoing( Intersection i, ArrayList<Road> r );
}

Here, very clearly, the three interfaces Road, Intersection and Vehicle each contain references to the other, creating a circular dependency.

There is one useful thing to notice about this dependency: It is an extremely minimal one. In the definition of each of the three classes, really interfaces, all we need to know is that the other classes exist. There are no references in any of these interfaces to any methods of the other, only references to the names of the other, as class names.

This kind of lightweight circularity is far easier for a compiler to deal with than the kind of heavyweight circularity you get when each interface or class needs to know about public details of the other.

This is as far as we can go in eliminating circular dependencies in Java, and we can't always get this far without significant redesign. One big problem occurs when constructors that contain circular references, because constructors cannot be included in interfaces.

Another problem came to the surface when trying to split the core classes of the road network simulator: The Intersection name was declared as a public field of each Intersection object. When Intersection was converted to an interface, the name field had to be moved to class IntersectionImp, potentially forcing every user of Intersetion to use IntersectionImp for access to that field.

We avoided this by adding a public getter method for the name in Intersection, and making a global change from i.name to i.name() in all references to the name field outside of class IntersectionImp.

The influence of C++

C++, the language that inspired Java, has a radically different model for interfaces and both Make and the C++ compiler are generally less forgiving of circular dependencies.

This leads to a general prohibition of circular dependencies in many programming style guidelines, forcing those working with problems where circularities are natural to struggle a bit. Fortunately, the C and C++ model for dealing with interfaces, while weaker than Java's, also tolerates circularity.

In C and C++, each source file marked with the suffix .c for C files or .cpp for C++ files typically has an associated "header" file with the same name but marked with the suffix .h. Header files contain the interface specifications for the functions classes and methods defined in the source files. C and C++ programmers are generally accustomed to the convention that every source file (excepting, perhaps, the main program) has an associated header file.

something.o: something.c something.h otherthing.h yetanother.h
        cc -C something.c

That is, the object file (compiler output) for something.o depends on the source file something.c and on a list of header files ending with .h. The code inside the source file for something.c typically directly imports those header files, using what C and C++ call an #include directive for each header file.

Header files give the public interface to whatever is implemented in each source file, but in C and C++, so long as you know that something is a pointer or an object handle, you can freely mention it in the parameter and data structure definitions in a header file without telling the compiler anything else. That is, merely mentioning a class name or data structure name in a header file does not create a dependency between the header files.

38. Almost Eliminating Circular Dependency

Circularity

A strategy for Eliminating Circular Dependencies

Assessment

The influence of C++