Applying Program Analysis to Code Retrieval - Finding Source Code on the Web for Remix and Reuse - page 212

Require: Queue todo contains the seed declarations
Ensure: todo is empty and slice contains the complete dependency slice

1: slice ⇐ new Slice()

2: while todo not empty do
3:

⇐

todo .dequeue()
4: if next has not been considered yet then
5: Add next to slice
6: Add next .getContainingDeclaration() to todo
7: for all method such that next calls method do
8: Add method to todo
9: end for
10: for all field such that next accesses field do
11: Add field to todo
12: end for
13: for all type such that next references type do
14: Add type to todo
15: end for
16: end if
17: end while
18: return slice

next

Algorithm 1: Basic slice

Once the algorithm has determined that readToByteArray has never been ex-
amined, the next step is to add its parent class to the queue, as seen in line 6. This is
done because in Java, at least, it is not possible to have a method without a contain-
ing class.
Next, the loop on line 7 adds every method called by readToByteArray to the
queue. This includes the close method mentioned earlier, as well as the write
method and the constructor for ByteArrayOutputStream , among others. Each of
methods is clearly requires for readToByteArray to function.
The loop in line 10 adds every field accessed by the declaration to the queue. As
no fields are accessed in our example, this loop would not add anything.
The loops on lines 7 and 10 in Algorithm 1 do not apply to all declaration types,
as not all declaration types call methods or access fields. Only those declarations that
directly contain executable statements can do so. For example, these loops apply to
method and initializer declarations, but not to class or interface declarations.
The loop on line 13 adds every referenced type to the queue. In our example, this
includes the types InputStream , ByteArrayOutputStream and IOException .A
type reference is simply any mention of a type's simple or fully qualified name.
The algorithm concludes once every declaration identified as required has been
examined once. The result is that the slice contains the seed declarations and all of
their transitive dependencies.