Automate dependency tracking, Part 1

Design an information model for automatically discovering dependencies in interactive object-oriented applications

In any interactive application, dependency tracking is one of the most significant problems you must solve. Usually, you apply some manual mechanism to update user interface (UI) components when the information model changes. For example, you might use the Observer pattern to notify registered objects of changes to a given subject. Or you might use the Publish/Subscribe pattern to broadcast changes to all listeners. Or you can route update messages with appropriate hints to all views. All these mechanisms work, but they all require effort by a person -- and that person will be you, the overworked programmer.

An automatic dependency tracking mechanism can handle most of that work for you. Using the automatic mechanism resembles programming with a spreadsheet; you simply enter formulas, and the computer figures out when to calculate them. The major difference is that the automatic mechanism is object-oriented and speaks Java.

The choice to track dependencies automatically is not based on laziness -- well, not entirely. By relieving the programmer from manually tracking dependencies, an automatic dependency mechanism removes a potential bug source. It also reduces the work needed to add features to the program. With a manual dependency mechanism, a program addition usually requires you to revisit prior dependencies to keep the user interface in sync with the model. However, when dependency is tracked automatically, the program discovers new dependencies on its own at runtime, with no programmer intervention. Of course, setting up such a mechanism takes some preparation.

In this series, you will learn what it takes to create an interactive application using automatic dependency tracking. Automatic dependency tracking separates the information model (IM) from the UI so that the UI discovers dependencies upon the IM and automatically updates itself. In this first installment, you will find out how to construct the IM for a dependency-tracking application. In Part 2, you will see how to build the UI on top of the IM. In Part 3, you will use dependency to solve some common application problems. Part 1 lays the groundwork for automatic dependency tracking. You won't actually see automatic dependency tracking in action until Part 2, but your patience will be rewarded.

Throughout the series we will develop Nebula, a drag-and-drop application for visually designing computer networks. With this application, network designers can model a physical network, determine addressing, and run simulations to discover problems. Admittedly, this is a complex example, but as you will see by the end of the series, automatic dependency tracking makes even complex problems quite manageable.

Read the whole series on automatic dependency tracking:

Let's start at the beginning: a properly designed information model.

Design the information model

An information model is a system of software objects that models a set of problems in a given domain. Because our problem domain is network design, our IM consists of objects such as computers, routers, cables, and hubs. An IM's client is a person or software system that understands the problem domain. The IM interface (public class methods) should be designed specifically for someone knowledgeable in that domain. In other words, a network designer with the Nebula IM, a Java compiler, and a working knowledge of programming should be able to construct a network simulation straight from the source code. The UML diagram in Figure 1 depicts the information model for Nebula.

Figure 1. The Nebula information model

Like any good software system, an information model is designed to accomplish specific tasks. Particularly, an IM must provide means for performing three activities:

  1. Build: The client must be able to construct a model to the required degree of complexity to represent the problem.
  2. Traverse: The client must be able to browse or search a given model to identify objects of interest, discover their information, and make required changes.
  3. Apply: The client must be able to solve problems using the model, usually by evoking its predictive abilities. Nebula, for example, can predict the path a packet will take through a network, identifying every device it reaches along the way.

Notice that an information model is not specifically designed for any given user interface. An IM has no presentation knowledge and doesn't create its own UI components such as visual proxies. This decision reduces coupling between the IM and UI, making the application design more maintainable; IM changes have little impact on UI code, just as UI changes have little impact on the IM.

When designing the information model for an automatic dependency tracking application, observe three guidelines:

  1. Clearly define ownership
  2. Rely on object relationships to store information
  3. Favor abstract data types over native types

Clearly define object ownership

Every object has exactly one owner, and ownership is not transferable. An object's owner is responsible for its creation and destruction. With clearly defined ownership, each object's responsibilities become more apparent. The owner provides means for building and traversing the objects under its control. (The owned objects themselves provide the third activity -- apply.)

In Nebula, the Network object forms the root of the ownership tree. The Network owns all the Devices as well as the Cables that connect them. Devices in turn own Ports. Different kinds of devices -- Hubs, Computers, and Routers -- own different kinds of ports. The Network provides a method for creating each device and methods for traversing the collection of devices. Whether port, device, or cable, each object has exactly one owner; at the top of the ownership hierarchy is the Network.

Object relationships store information

The second guideline to follow when designing the IM is to rely on object relationships to store information. The alternative, storing identifying attributes, leads to unnecessary searching and potential referential errors. Object relationships offer a much richer traversal mechanism than searches, perform better, and ensure data integrity. They also greatly simplify the UI's job, as you will see in Part 2.

In Nebula, a network interface card (NIC) has a default gateway, which tells it where to forward packets destined for addresses outside the local subnet. When configuring a single computer, you identify the default gateway by IP address. An IP address represents identity in the real network; it uniquely identifies a network node. However, in Nebula we can take advantage of true object identity. The Nebula information model already includes an object -- Hop -- that represents a packet's target. Therefore, a reference to a Hop object, not an IP address, identifies the default gateway.

There are many advantages to such a representation. For instance, we know for certain that a reference identifies an existing Hop object. If we relied upon an IP address, we would have to perform a search to validate the information. Second, each IP address is stored in only one place, the Hop object that it identifies. The network designer can easily change the address strategy without compromising the information's integrity. Third, we have direct access to the object that we wish to identify. We can use object references to traverse the network and immediately make requests of its various devices -- for example, to accept a packet.

Favor abstract data types

The IM's goal, remember, is to permit a client knowledgeable in the problem domain to access the information. To that end, you must expose information from the IM with access and mutate methods. The task for which it was designed demands it: build implies mutate; traverse implies access. However, you should not expose your classes' inner workings, as that would violate one of the fundamental rules of object-oriented design: information hiding. The trick is to hide the classes' inner workings while exposing information meaningful in the problem domain. Abstract data types (ADTs) do that well.

An ADT provides a set of values and the operations that can be performed over that value set. An ADT might be restrictive, represented only by a small set of values (such as an enumeration), or it may be quite general, with a large or infinite set of values (like a stack). An ADT represents its values and operations in the most appropriate form for the desired application. Most likely the set of values and operations defined by int or double don't exactly match your desired problem domain. An ADT lets you be more precise.

The ADT IP represents both IP addresses and subnets in Nebula. The IP ADT defines the set of 32-bit IP addresses with subnet masks. It includes a few utility operations, such as conversion to and from a string, and a few application-specific operations, such as testing for an address's inclusion in a given subnet. The information appropriate to the problem domain is available, as the client can obtain any Hop's IP address. But information is also hidden, in that you cannot see from the interface how an IP is actually represented.

Clearly defined ownership, reliance on object relationships, and preference for ADTs govern the IM's design. Committing that design to code requires an additional set of disciplines.

Code the information model

When constructing the information model for an automatic dependency tracking application, apply three coding patterns:

  1. Distinguish between definitive and dynamic state
  2. Accept visitors to discover derived class type
  3. Treat object relationships as identities and ADTs as values

Definitive versus dynamic state

Dynamic state is state that can change. It is typically modified in a mutate method and retrieved by an access method. Definitive state, on the other hand, does not change at any point during an object's lifetime. It is typically passed in as a constructor parameter and either used internally or exposed via an access method.

For automatic dependency tracking to work, you must tell the dependency system when a dynamic attribute is accessed or mutated. To accomplish that, create a dynamic sentry, an object of type Dynamic that rides alongside the actual dynamic attribute. Whenever the dynamic attribute is accessed, you must invoke the dynamic sentry's onGet() method. Whenever the dynamic attribute mutates, invoke the dynamic sentry's onSet() method.

However, definitive state requires no such sentry. Because definitive state does not change during an object's lifetime, it will never mutate. Dependence upon definitive state resembles dependence upon a constant: since you know it will never change, you don't need to track it. Therefore, you don't waste any effort tracking dependencies on definitive state.

In Nebula, a Hop's IP address is dynamic. The Hop class has a mutate method setAddress(), which changes the address attribute, and an access method getAddress(), which retrieves it. Therefore, each method invokes a dynamic sentry. The Hop class appears below, complete with access and mutate methods:

abstract public class Hop extends Port
{
    public Hop()
    {
    }
    public IP getAddress()
    {
        m_dynAddress.onGet();
        return m_address;
    }
    public void setAddress( IP address )
    {
        if ( !m_address.equals(address) )
        {
            m_dynAddress.onSet();
            m_address = address;
        }
    }
    // Dynamic data
    private IP m_address = new IP();
    // Dynamic sentries
    private Dynamic m_dynAddress = new Dynamic();
}

Note that the above mutate method performs some redundancy checking. It only invokes onSet() if the attribute actually changes. This optimization saves some update time if an attribute's value is simply reasserted.

Collections can also be dynamic. For instance, the device collection in the Network is dynamic because the collection itself can change. The methods that add and remove devices are mutators, while the one that retrieves the device iterator is an accessor. These methods, too, invoke a dynamic sentry, as shown below:

public class Network
{
    public Network()
    {
    }
    // Device access
    public Hub createHub()
    {
        // Add a new hub to the device collection.
        m_dynDevices.onSet();
        Hub pNew = new Hub();
        m_lDevices.add( pNew );
        return pNew;
    }
    ...
    public void deleteDevice( Device victim )
    {
        // Remove a device from the device collection.
        if ( m_lDevices.remove(victim) )
        {
            m_dynDevices.onSet();
        }
    }
    public Device.ConstantIterator getDeviceIterator()
    {
        // Traverse the device collection.
        m_dynDevices.onGet();
        return new Device.ConstantIterator( m_lDevices.iterator() );
    }
    // Data values
    private List m_lDevices = new LinkedList(); // of Devices
    ...
    // Dynamic sentries
    private Dynamic m_dynDevices = new Dynamic();
    ...
}

The code snippet above illustrates the use of a dynamic sentry to track a dynamic attribute's mutation and access. Sentries are necessary to track dependence upon dynamic state. However, the ports that a cable connects represent definitive state. The cable is simply a connector object; it exists only to connect two objects. Therefore, the cable is created with the knowledge of the two objects it connects and continues to connect those two objects until it is destroyed. Because the cable's ports are definitive, their access methods do not invoke a dynamic sentry. The Cable constructor and access methods are as follows:

public class Cable
{
    ...
    public Cable( Port portFrom, Port portTo )
    {
        m_portFrom = portFrom;
        m_portTo = portTo;
        m_portFrom.attach( this );
        m_portTo.attach( this );
    }
    public Port getFrom()
    {
        return m_portFrom;
    }
    public Port getTo()
    {
        return m_portTo;
    }
    ...
    // Definitive data
    private Port m_portFrom;
    private Port m_portTo;
    ...
}

Add visitors

The second coding pattern that appears in the information model is the Visitor pattern. Often, IM design calls for collections and relationships by base class so that the model can be specialized and extended. However, recall that the IM must support traversal. To support traversal, include a mechanism for discovery of derived class type: the Visitor pattern.

In Nebula, the Network object owns a collection of Devices, though it has no knowledge of the specific types of devices in that collection. To support traversal, the Network object exposes the getDeviceIterator() method, which returns an iterator of Device objects. When a client traverses the Devices list, it asks each object to accept a visitor -- an object that implements the IDeviceVisitor interface. That visitor will receive a call back for the specific kind of device that it visits. The Visitor pattern's various pieces -- the visitor interface IDeviceVisitor, the abstract subject Device, and the concrete subject Computer -- appear below:

public interface IDeviceVisitor
{
    public void visitHub( Hub hub );
    public void visitComputer( Computer computer );
    public void visitRouter( Router router );
}
abstract public class Device
{
    ...
    abstract public void accept( IDeviceVisitor visitor );
}
public class Computer extends Device
{
    ...
    public void accept(IDeviceVisitor visitor)
    {
        visitor.visitComputer( this );
    }
    ...
}

You will see the Visitor pattern put to use next month when we build the user interface, but we'll put the infrastructure in place now in anticipation of a client.

Object relationships and ADTs

The third code pattern to apply when constructing an automatic dependency tracking application is the treatment of object relationships as identities and ADTs as values. Wherever an ADT represents information, the access and mutate methods get and set instances of that ADT. An ADT's value is important, not its identity. You therefore compare ADTs based on value and, if necessary, make copies to protect their identities. Conversely, where information is represented as object relationships, object identity -- not value -- takes priority. In such cases, access and mutate methods compare and exchange object references.

Above, you saw the code for getAddress() and setAddress(), the access and mutate methods for a Hop's IP address. Notice that setAddress() uses the equals() method to compare values, rather than the equality operator (==) to compare identity. Furthermore, all data in the IP class is definitive. Once created, an IP's value cannot change. If it weren't for that fact, getAddress() and setAddress() would have to take the extra precaution of copying the data to avoid any unprotected modifications based on shared identity.

However, an NIC's default gateway proves a different story. That attribute represents an object relationship, so we wish to record the identity, not the value. As such, we use the equality operator (==) for comparisons and manipulate object references directly without making copies, as demonstrated in the following access and mutate methods:

public class NIC extends Hop
{
    ...
    public Hop getDefaultGateway()
    {
        m_dynDefaultGateway.onGet();
        return m_defaultGateway;
    }
    public void setDefaultGateway( Hop defaultGateway )
    {
        if ( m_defaultGateway != defaultGateway )
        {
            m_dynDefaultGateway.onSet();
            m_defaultGateway = defaultGateway;
        }
    }
    ...
    // Dynamic data
    private Hop m_defaultGateway = null;
    ...
    // Dynamic sentries
    private Dynamic m_dynDefaultGateway = new Dynamic();
    ...
}

These three code patterns, replicated over the entire design, complete the information model.

Apply the information model

We have constructed an information model useful to a client knowledgeable in the problem domain. Given a compiler and this IM, a network designer can build, traverse, and apply the model. The IMTest class does just that. Its main() method builds a WAN (wide area network) and routes a packet from a workstation to a remote server. The network model that it constructs appears in Figure 2.

Figure 2. The network model built in IMTest

Although we intend to use the IM as a foundation for a UI, a client should be able to use the IM directly. Doing so validates the fact that the IM focuses on the problem domain, not on the UI's ultimate goal. Nevertheless, we have added hooks for dependency tracking. So if the client knowledgeable in the problem domain happens to be a UI that uses dependent sentries, we would automatically track their dependency upon the IM and update them as things change. In Part 2, we will construct just such a user interface, and you'll see how automatic dependency tracking makes programming easier.

Michael L. Perry has been a professional Windows developer for more than seven years and maintains expertise in COM (Component Object Model), Java, XML, SOAP (Simple Object Access Protocol), .Net, and other technologies. He formed Mallard Software Designs in 1998, where he applies the mathematical rigor of proof -- establishing the correctness of a solution before implementing it -- to software design. Michael applies a cohesive set of rules to all his software models, one of which -- dependency -- is the foundation for automatic dependency tracking.

Learn more about this topic

Join the discussion
Be the first to comment on this article. Our Commenting Policies