Applications of Traversal Strategies

6/13/02

The traversal theory that we developed for the Demeter system is applicable to both adaptive programming as well as aspect-oriented programming, as shown in this paper. While in Aspect-Oriented Concepts in Demeter we describe several applications of the basic AOP idea in Demeter, here we describe how an important part of Demeter can be applied to further Aspect-Oriented Programming.

The traversal theory relies on three layers of graphs: top, middle and bottom (see Table 1). The bottom layer consists of graphs that we want to traverse or ask questions about whether certain traversals can possibly exist. Each bottom layer graph has a graph from the middle layer associated with it that contains meta-information about the bottom layer graph. The meta-information expresses that certain edges must or may exist. Each middle layer graph is associated with at least one top layer graph. The top layer graph is basically a sub graph of the transitive closure of the middle layer graph, decorated with additional information attached to the edges. The purpose of the top layer graph is to

1. define sub graphs of the bottom layer graph. In other words, when the bottom layer graph is traversed, the top layer graph tells us at each node which outgoing edges to traverse.

2. find all occurrences of the top layer graph in the bottom layer graph.

The union of all occurrences of the top layer graph defines a sub graph of the bottom layer graph. The purpose of the middle layer graph is to act as an abstraction barrier between the top and bottom layers. At the middle layer we program the specification given by the top layer and we use the middle layer to reduce the search space.

The top layer graphs are an abstraction A of the associated middle layer graphs and the middle layer graphs are an abstraction B of the associated bottom layer graphs. The abstractions A and B, however, are different. Abstraction A involves the transitive closure and abstraction B involves compatibility rules where relations at the middle layer imply relations at the bottom layer.

In the following we use static and dynamic call graphs.

Static call graph: It is derived from the program source as follows. The nodes correspond to methods and the edges to method invocation expressions (e.g. a.foo(b,c) contained in the methods). There are two types of methods: concrete and abstract. A concrete method has an outgoing edge for every method the method calls or might call. Some of the outgoing edges are marked required and others are marked optional. The required edges are to calls of other methods that are reached unconditionally while optional edges correspond to calls that are reached conditionally (some conditional statement might prevent the execution of the call; e.g. an if, loop or switch statement). An abstract method has several outgoing edges marked as virtual edges. Each leads to one of the method calls that might happen as a result of the virtual method call. A static call graph has the shape of a class graph as shown by the correspondences in the following table:

	static call graph	class graph
nodes	concrete	concrete
	abstract	abstract
edges	required/optional	part-of(required/optional)
	virtual	subclass (reversed inheritance)

Dynamic call graph: It is a tree conforming to a static call graph. The nodes are calls of methods and the edges represent immediate method call nesting. Conformance means that

1. the dynamic call graph can only contain instances of call sites appearing in the static call graph.

2. the dynamic call graph can only contain edges prescribed by the static call graph.

3. if in the static call graph a required edge exits a call site then the edge must be in the dynamic call graph.

4. a call of a virtual method is not shown in the dynamic call graph; instead it shows the normal method that actually gets called.

A dynamic call graph has the shape of an object graph where call nodes correspond to object nodes and immediately nested calls correspond to immediately nested objects.

Make a figure for an expression traversal program. Show source, static and dynamic call graphs.

layer	object graph application	call graph application
top	strategy graph	pattern graph
middle	class graph	static call graph
bottom	object graph	dynamic call graph

Table 1: AOP applications of top-middle-bottom layers

2 abstractions, but details differ.

In the object graph application the intent of the top layer graph is to define a set of collaborating introductions and to define a pointcut for the join points that are created during the execution of the introductions. In the call graph application the intent of the top layer graph is to define a set of join points in the in an already defined dynamic call graph. The call graph application lacks the code defining qualities of the object graph application.

In aspect-oriented programming with a dynamic join point model, the join points are points in the dynamic call graph of the base program. The static call graph determines the overall shape of the dynamic call graph. For example, if in the static call graph method f does not call method g, then in the dynamic call graph f will never call g and if in the static call graph method f calls method g, then in the dynamic call graph, f may call g (there could be a condition involved that prevents the call of g at run-time).

The object graph application defines a pointcut traversal(s): all join points of the object graph traversal defined by s. The call graph application defines a pointcut reachable(s): all join points defined by s for a given dynamic call graph.

John Sung has implemented the object graph application in the DAJ tool.

The call graph application is introduced in this paper. We start with a comparison to AspectJ and show why the cflow construct of AspectJ is not sufficient to simulate the call graph application. AspectJ has a cflow pointcut that can be used together with the set operations to define useful sets of join points in a structure-shy way. For example, cflow can be used to propagate variables from one method to another method disregarding the number of intermediate method calls.

All method calls that might happen between a call to f and a call to g. For each of those method calls we would like to print some information about the join point and we would like to know how the join points are related. In other words, we want to know the structure of the dynamic call graph between calls to f and calls to g. We would like to describe this slice of the dynamic call graph as “from jp1 to jp2”, where jp1 = call(* f(*)) and jp2 = call(* g(*)). Both f and g may return any type and both may have one argument of any type.

In AspectJ we cannot conveniently express such subgraphs of the dynamic call graph. We could try cflow(jp1) && jp2 but this gives only a subset of the calls of g.

Consider the situation where we use AspectJ for testing architectural rules. We would like to ensure that between a call to f and call to g there is a call to x. In other words, there should be no path “from jp1 bypassing jp3 to jp2”, where jp3 corresponds to a call to x. Can do this with cflow: cflow(jp1) && jp2 ???