The Execution Structure of Object-Oriented Programs:
Ownership Object Graph Case Studies

by Marwan Abi-Antoun and Jonathan Aldrich

Summary

         "An object-oriented program's run-time structure often bears little resemblance to its code structure. The code structure is frozen at compile-time; it consists of classes in fixed inheritance relationships. A program's run-time structure consists of rapidly changing networks of communicating objects. In fact, the two structures are largely independent. Trying to understand one from the other is like trying to understand the dynamism of living ecosystems from the static taxonomy of plants and animals, and vice versa."  E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1994. (pp. 22-23).

For many code modification tasks, developers often need to understand both the code structure and the execution structure of object-oriented programs. But current tools provide little insight into the execution structure at compile-time. Class diagrams extracted from source code are often sufficient to understand the code structure. However, existing static or dynamic analyses that produce an execution structure consisting of raw graphs of objects and relations between them, do not convey design intent or readily scale to large programs.

The code structure is often referred to using the term static structure. The execution structure is often referred to using the terms dynamic structure, runtime structure or even execution architecture. In the following discussion, we use the terms dynamic and static to denote whether the analysis is dynamic (requires running the program) or static (happens at compile-time). We use code structure and execution structure to qualify the design structure we are talking about. We avoid using the term architecture.

Imposing an ownership hierarchy on the execution structure through source code ownership domain annotations provides an intuitive and appealing mechanism to: a) provide stronger encapsulation properties than visibility mechanisms; b) express and enforce design intent regarding object encapsulation and communication; and c) obtain a sound hierarchical execution structure of the system, the Ownership Object Graph -- at compile-time.

To evaluate our approach, we implemented a set of tools and conducted case studies on two real Java programs, each consisting of 15,000 lines of code. One of the subject systems was developed by experts in object-oriented design and the other by undergraduates. In both cases, the automatically generated Ownership Object Graph fit on one page, helped us refine the annotations, and gave us insights into the implementations. These insights would be otherwise hard to obtain by looking at the original code without annotations, at existing class diagrams, or at unreadable visualizations of the runtime object graph produced by existing compile-time approaches.

Example: CourSys

We give the intuition behind the Ownership Object Graph (OOG) execution structure by example. CourSys is a simple course registration system to keep track of courses, students, and register students for courses, implemented following a three-tiered architectural style.

The UML class diagram might mislead the reader into thinking that the same ArrayList object is shared between Data, Course, and Student objects, when at runtime, there are distinct ArrayList instances: (a) the list of all available Courses; (b) the list of Students registered in a Course; (c) the list of Courses for which a Student has registered; and (d) the list of Courses a Student has previously completed.

The Ownership Object Graph shows explicitly object objClient in a user tier, object objLogic in a logic tier, object objData in a data tier, and objects of type Student,  and lists thereof in a state tier. Furthermore, it shows that objects log and lock are owned by objLogic. The solid edges show field references and the dashed edges show domain links from domain user to domain logic, and from domain logic to domain data.

Ownership hierarchy is different from the hierarchy found in class diagrams that use packages to organize related classes. Placing the Logic and the Logging classes in a coursys.logic package indicates that they belong to the same layer in the code structure. The execution structure may want to indicate that an instance of Logging is owned by an instance of Logic, i.e., hidden in its representation and inaccessible to other objects in the system, although both are in the same architectural tier at runtime.

Case Study: JHotDraw

Original Code without Annotations

Code with Ownership Domains Annotations

Case Study: HillClimber

Original Code without Annotations

Code with Ownership Domains Annotations

References

  1. Abi-Antoun, M. and Aldrich,  J. Ownership Domains in the Real World. In International Workshop on Aliasing, Confinement and Ownership in object-oriented programming (IWACO), in conjunction with the European Conference on Object-Oriented Programming (ECOOP), 2007.
  2. Abi-Antoun, M. and Aldrich,  J. Compile-Time Views of Execution Structure Based on Ownership. In International Workshop on Aliasing, Confinement and Ownership in object-oriented programming (IWACO), in conjunction with the European Conference on Object-Oriented Programming (ECOOP), 2007.
  3. Abi-Antoun, M. and Aldrich, J. JavaD: Bringing Ownership Domains to Mainstream Java. Carnegie Mellon University Technical Report CMU-ISRI-06-110, 2006. [Report (PDF)].
  4. Abi-Antoun, M. and Aldrich, J. Bringing Ownership Domains to Mainstream Java (Demonstration). In Conference Companion of Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 2006.  [Paper (PDF)] [Presentation (PDF)]
  5. Aldrich, J. and Chambers, C. Ownership Domains: Separating Aliasing Policy from Mechanism. In Proc. European Conference on Object-Oriented Programming (ECOOP),  2004.
  6. Jackson, D. and Waingold, A. Lightweight Extraction of Object Models from Bytecode. IEEE Transactions on Software Engineering. 27, 2 (Feb. 2001), 156-169, 2001.
  7. Spiegel, A. Automatic Distribution of Object-Oriented Programs. PhD Thesis. FU Berlin, FB Mathematik und Informatik, December 2002.