2.2 Object Flow Graph

25

eLib example

The body of the second if statement of method borrowDocument (class Library of the eLib program, lines 60-62) is represented as the following abstract lines of code:

Conditional and return statements have been skipped, and only allocations, assignments and invocations have been maintained (actually, one allocation, one invocation, and no assignment). Variable names are expanded to fully scoped names (no packages are used in this application). In the method call (second line above), the method name is prefixed by the class name. The implicit target object (this) is made explicit, and prefixed according to the rules for the program locations.

Return values are represented by an explicit location, which we call return and which is prefixed by the fully scoped method name. Thus, the values returned by getUser (line 42) and getDocument (line 43) inside method addLoan of class Library and assigned respectively to the local variables user and doc are abstractly represented as:

Unique names are assumed for all program entities. This is the reason why in the abstract grammar, package, class, method, and variable identifiers (<pid>, <cid>, <mid>, <vid>) are indicated instead of their names. Given the source of a Java program, it is always possible to transform it so as to make its names unique [30]. Names of overloaded methods belonging to the same class can be augmented with an incremented integer suffix, to make them unique. The same can be done for methods of different classes with the same name. Calling statements are transformed correspondingly. The called method(s) can be resolved with all statically type-compatible possibilities.

2.2 Object Flow Graph

The Object Flow Graph (OFG) is a pair (N, E), comprising of a set of nodes N and a set of edges E. A node is added to the OFG for each program location

26 2 The Object Flow Graph

(i.e., local variable, attribute or formal parameter, according to the definition in Fig. 2.1).

eLib example

The OFG for the class Library of the eLib program contains, for example, a node associated with the class attribute loans (line 6), labeled:

Two nodes are associated with the formal parameters of method borrowDocument (line 56):

The local variable loan (line 60) is associated with node:

The current object inside method borrowDocument is also associated with an OFG node:

Fig. 2.2. OFG edges induced by each abstract Java statement.

Edges are added to the OFG according to the rules specified in Fig. 2.2 (right). They represent the data flows occurring in the analyzed program. The set of OFG edges E contains all and only the pairs that result from at least one rule in Fig. 2.2.

When a constructor or a method are invoked (statements (5) and (7), resp.), edges are built which connect each actual parameter to the respective formal parameter In case of constructor invocation, the newly created object, referenced by cs.this (with cs the constructor called by new

is paired with the left hand side of the related assignment (see statement

2.3 Containers

27

(5)). In case of method invocation, the target object becomes inside the called method, generating the edge and the value returned by method (if any) flows to the left hand side (pair

eLib example

The following invocations, taken from class Library (lines 60, 61):

generate the following OFG edges:

Plain assignments (statement (6) in Fig. 2.2) generate an edge that connects the right hand side to the left hand side. Thus, the following abstract statements, taken from the constructor of class Loan (lines 137-138):

generate the following edges:

2.3 Containers

Edges in the OFG account for all data flows occurring in a program. While some of them are associated with specific Java instructions, such as the assignment or the method call, others may be related to the usage of library classes. Each time a library class introduces a data flow from a variable to a variable an edge must be included in the OFG.

A category of library classes that introduces additional, external data flows is represented by containers. In Java, an example is any class implementing the interface Collection, such as the classes Vector, LinkedList, HashSet,

28 2 The Object Flow Graph

and TreeSet. Another example is the interface Map, implemented by classes

Hashtable, HashMap, and TreeMap.

Classes implementing the Collection interface provide public methods to insert objects into a container and to extract objects from it. One such insertion method is add, while extraction can be achieved by requesting an Iterator object, that is successively used to sequentially access all objects in the container (method next in interface Iterator).

Classes implementing the Map interface offer similar facilities, with the difference that contained objects are accessed by key. Thus, method put can be used to insert an object and associate it to a given key, while method get can be used to retrieve the object associated to a given key.

Abstractly, container objects provide two basic operations that alter the data flows in a program: insert, to add an object to a container, and extract, to access an object previously inserted into a container. Thus, for a program with containers, the two basic cases that have to be handled in OFG construction are the following:

(1)

(2)

where is a container and is an object. In the first case there is a data flow from the object to the container while in the second case the data flow is reversed. Correspondingly, the following edges are introduced in the OFG:

(1)

(2)

The same edges would be introduced in the OFG in presence of the following assignments:

(1)

(2)

For this reason, in the abstract program representation we have adopted, insertion and extraction methods associated with container objects are accounted for by transforming the related statements into assignment statements, such as those given above.

eLib example

Examples of containers used in the eLib program are the attributes documents, users, and loans of the class Library (lines 4, 5, 6). The attribute loans, of type Collection, is initialized with a LinkedList object. Its method addLoan contains the following statement (line 44) :

2.3 Containers

29

where loan is the formal parameter of the method. Its abstract syntax representation is therefore:

The invocation of the insertion method add on the container loans is transformed into an assignment that captures the data flow from the inserted object (loan) to the container.

An example of extraction from a container is available from the same class, method printAllLoans (lines 120-122), where the following loop is used to access the Loan objects previously inserted into the loans container:

The related abstract representation, which preserves the data flows between container and contained objects is:

The first assignment accounts for the data flow from the container (loans) to the iterator (i). The second assignment accounts for the access to a contained object by means of the iterator (invocation of method next), and the assignment of this object to the local variable loan.

Another example available from the Library class is the attribute users, of type Map, initialized by a HashMap. Methods addUser (line 8) and getUser (line 21) contain respectively insertion and extraction instructions. Specifically, a User object is inserted into the container users by means of the following statement, taken from method addUser (line 10):

which is transformed into the following abstract statement:

Symmetrically, the following extraction statement, taken from method getUser (line 22):

is transformed into: