40 2 The Object Flow Graph

and the allocation’s left hand side variable, Library.borrowDocument.loan (Fig. 2.8 center, edge labeled 60).

An example of a method call with a return value is provided by the first abstract statement (after the declaration) of method Library. addLoan (see Fig. 2.7 top, line 42). The left hand side location (Library.addLoan.user) is the target of an edge outgoing from Loan.getUser.return, the location associated with the value returned by the method call (see Fig. 2.8 bottom, edge labeled 42).

Container operations are also responsible for some edges in the OFG of Fig. 2.8. For example, the body of User.addLoan contains just an insertion statement (line 315). The container User.loans, into which a Loan object is inserted, becomes the target of an edge starting at the inserted object location, User .addLoan. loan (Fig. 2.8 center, edge labeled 44). This indicates an object flow from the parameter loan of method addLoan into the container

User .loans.

The OFG constructed for the code in Fig. 2.6 and 2.7 shows the data flows through which objects are propagated from location to location. Thus, the parameter user of method borrowDocument becomes the current object (this) inside numberOfLoans, while it is the parameter user inside method authorizedLoan and it is the parameter usr inside the constructor of class Loan, as depicted at the top of Fig 2.8. Similarly, the other parameter of borrowDocument, doc, flows into isAvailable and authorizedLoan as this, and into the constructor of class Loan as the parameter doc. The object of class Document returned by Loan.getDocument (bottom-right of Fig. 2.8) flows into the local variable doc of Library. addLoan, and then becomes the current object (this) inside Document. addLoan.

2.7 Related Work

The OFG and the related flow propagation algorithms are based on research conducted on pointer analysis [3, 21, 47, 49, 60, 68, 81, 86]. The aim of pointer analysis is to obtain a static approximation of any points-to relationship that may hold at run-time between pointers and program locations. Similarly, when Object-Oriented programs are considered, the relationship between reference variables and objects is analyzed.

Pointer analysis algorithms can be divided into flow/context sensitive [21, 47, 60] and flow/context insensitive [3, 81]. Flow/context sensitive algorithms produce fine grained and accurate results, in that a points-to relationship is determined that holds at every program statement. Moreover, different invocation contexts can be distinguished. However, the computational complexity involved in these approaches is high, and in practice their performance does not scale to large software systems. Flow/context insensitive algorithms have lower complexity and scale well. On the other side, they produce results that hold for the whole program, and the points-to relationships they derive cannot

2.7 Related Work

41

be distinguished by statement or invocation context. Flow/context sensitive analyses are defined with reference to the control flow graph [2] of a program, while flow/context insensitive algorithms define the analysis semantics at the statement level.

The algorithm most similar to ours is [3]. Originally described for the C language, it has been recently extended to Java [49, 68]. Differently from the approach followed in this book, no explicit data structure, such as the OFG, is used in [3] as a support for the flow propagation: data flows are represented as set-inclusion constraints.

The improvement of a control flow insensitive pointer analysis obtained by introducing object sensitivity was proposed in [57], where the possibility of parameterizing the degree of object sensitivity is also discussed.

This page intentionally left blank