The IRIterator class implements the Java Iterator interface plus some added functionality. The BreadthFirstIterator and DepthFirstIterator iterate over the IR in breadth-first and depth-first order, respectively. The FlatIterator simply iterates over an object’s children, and does not perform a “deep” traversal within the children. An IRIterator can be made to skip objects such that it only returns objects of certain types. It can also be made to prune parts of the traversal below objects of certain types.
IRIterators provide several versions of next that are explained in the examples below. The first example shows how to use the standard next:
/* BreadthFirst traversal over everything in a procedure. Assumes proc is a Procedure object. */
BreadthFirstIterator iter = new BreadthFirstIterator(proc);
while (iter.hasNext())
{
Object o = iter.next();
// Do something with the object
}
The next example shows how to locate a particular type of object:
/* Look for loops in a procedure. Assumes proc is a Procedure object. */
BreadthFirstIterator iter = new BreadthFirstIterator(proc);
try {
while (true)
{
Loop loop = (Loop)iter.next(Loop.class);
// Do something with the loop
}
} catch (NoSuchElementException e) {
}
Note the exception handling. next must throw an exception if it cannot find an element of the specified class, because the corresponding hasNext method cannot be implemented. The reason is the iterator would have to actually perform the iteration to determine if there was such a next element, and if true, would need to perform the iteration again to actually return the object. The standard hasNext does not have have this problem because it simply checks if it has reached the end of the list. We think it would be very strange for users if we provided a hasNext method that modified the iterator, and it would be awkward for us to write a hasNext that would look ahead and then undo its changes. Furthermore, that version of hasNext would no longer be a Θ(1) call, so we chose not to provide it.
Other versions of next will find an element of a set of classes, or an element that is not of a set of classes.
The next example shows how to use pruning:
/* Look for procedures in a program. Assumes prog is a Program object. */
BreadthFirstIterator iter = new BreadthFirstIterator(prog);
iter.pruneOn(Procedure.class);
try {
while (true)
{
Procedure proc = (Procedure)iter.next(Procedure.class);
// Do something with the procedure
}
} catch (NoSuchElementException e) {
}
Instead of obtaining one iterator on the Program object to look for TranslationUnits, and then obtaining another iterator on each TranslationUnit to look for Procedures, it is easier to do a breadth first search on the entire Program. However, it does not make much sense to look for Procedures inside other Procedures, since none of the languages supported by Cetus allow nested Procedures. Therefore, pruneOn tells the iterator to skip anything below a Procedure on the IR tree.