A brief introduction to PCESjava (by Rob LeGrand)

Important references

Two packages to import

PCESGraph creates and manipulates graphs and trees
Clazzer reads, writes, modifies Java class files

The Role pattern

What to do when you need similar but different kinds of objects?

Graph, Tree, Vertex and Edge objects can have Roles attached to them.  Example:

How to add a Role

vertex.addRole("PCESGraph.TreeVertex");

to test:  vertex.hasRole("PCESGraph.TreeVertex");

to remove:  vertex.removeRole("PCESGraph.TreeVertex");

Roles and vertices: an example

Working with graphs

create a raw undirected graph:
Graph graph = GraphFactory.createGraph();

create a directed graph from an undirected graph:
DirectedGraph directedGraph = (DirectedGraph) graph.addRole(DirectedGraph.graphProperties.graphType);

create a DFST for a directed graph:
DFST dfst = (DFST) directedGraph.addRole(DFST.graphProperties.graphType);

create a CFG from a Method object:
InstructionGraph instructionGraph = method.getInstructionGraph();
ControlFlowGraph cfg = (ControlFlowGraph) instructionGraph.addRole(ControlFlowGraph.graphProperties.graphType);
cfg.makeCFG(method);

Hydra example

Graph graph = GraphFactory.createGraph();
graph.addEdge("1", "2");
graph.addEdge("1", "3");
graph.addEdge("2", "3");
graph.addEdge("2", "4");
graph.addEdge("2", "11");
graph.addEdge("3", "4");
graph.addEdge("3", "9");
graph.addEdge("4", "5");
graph.addEdge("4", "8");
graph.addEdge("5", "3");
graph.addEdge("5", "6");
graph.addEdge("6", "5");
graph.addEdge("6", "7");
graph.addEdge("8", "6");
graph.addEdge("9", "8");
graph.addEdge("9", "10");
graph.addEdge("10", "6");
graph.addEdge("11", "12");
graph.addEdge("11", "13");
graph.addEdge("12", "7");
graph.addEdge("12", "11");
graph.addEdge("13", "12");
graph.setRoot("1");
graph.setName("Hydra");
System.out.println(graph);

DirectedGraph dgraph = (DirectedGraph) graph.addRole(DirectedGraph.graphProperties.graphType);
dgraph.setName("DirectedGraph");
System.out.println(dgraph);

DFST dfst = (DFST) graph.addRole(DFST.graphProperties.graphType);
dfst.setName("dfst");
System.out.println(dfst);

DomTree domTree = (DomTree) graph.addRole(DomTree.graphProperties.graphType);
domTree.setName("domTree");
System.out.println(domTree);

Working with DFSTs

iterate over DFST vertices:
dfst.forwardDiscovery() returns a VertexIterator of vertices in increasing depth-first numbering
dfst.backwardDiscovery() returns a VertexIterator of vertices in decreasing depth-first numbering
dfst.topOrder() returns a VertexIterator of vertices in topological order (right-to-left preorder)
dfst.topOrder(i) returns the Vertex that's ith in topological order
dfst.reverseTopOrder() returns a VertexIterator of vertices in reverse topological order
dfst.reverseTopOrder(i) returns the Vertex that's ith in reverse topological order

How to load methods from a class file

classFile = new ClassFile(new FileInputStream("foo.class"));
Iterator iter = classFile.getMethods();
if (iter.hasNext()) {
   Method method = (Method) iter.next();
   InstructionGraph instructionGraph = method.getInstructionGraph();
   ControlFlowGraph cfg =
      (ControlFlowGraph) instructionGraph.addRole(ControlFlowGraph.graphProperties.graphType);
   cfg.makeCFG(method);
   // cfg is now that method's CFG
}

More on depth-first numberings

Some students have noticed that depth-first numbers generated by the PCESjava software are sometimes greater than the number of vertices in the CFG.  The software does depth-first numbers a bit differently from the way presented in class.  The output for the simple three-vertex graph in CSE531DomTree.genMyGraph() includes something like

        VERTEX 1 3195425 dfn:0/5
        VERTEX 2 21722195 dfn:1/2
        VERTEX 3 12719253 dfn:3/4
The 0/5 means that the depth-first "discovery" number for that vertex is 0 and its "finishing" number is 5.  These two numbers are assigned during the depth-first traversal.  (Numbering this way allows us to compute the number of the vertex's progeny according to the DFST as ("finishing" - "discovery" - 1) / 2.)  The reason that no vertex has discovery number 2 in that small DFST is that discovery and finishing numbers don't overlap.  In that tree, vertex 1 was given discovery number 0 before exploring its successors.  Vertex 2 is seen first and given discovery number 1.  It has no successors, so it's given finishing number 2 and we go to vertex 1's next successor, vertex 3, which is given discovery number 3 and then finishing number 4.  Then vertex 1 gets finishing number 5.

The discovery numbering of the DFST and the depth-first numbering presented in class are always ordinally equivalent.  Really, what's important is that now you can traverse over the graph in different orders.  When you want to access vertices one by one, I recommend using one of the above DFST methods to generate an iterator over the vertices in the order you want.  Then, for each vertex v, use getLocalDom(v) (NB: not getDomVertex(v), which seems to be broken) to get its DomVertex role or DirectedGraph.getDirectedVertex(v) to get its DirectedVertex role.  Then you can call the appropriate methods on the appropriate object.  For example, say you want to iterate over the vertices in increasing dfn order and get the predecessors for each.  Remember, a vertex has predecessors in the CFG and a parent in the DFST.  So you can do something like

VertexIterator vIter = dfst.forwardDiscovery();
while (vIter.hasNext()) {
   VertexIterator predIter = DirectedGraph.getDirectedVertex(vIter.nextVertex()).getPredecessors();
   // now predIter is another iterator over that vertex's predecessors
}
This way you never have to convert the DFST to a CFG; you just use each vertex in the order that you need.

On the other hand, sometimes you have a DomVertex or some other kind of vertex and you need its depth-first number.  If your DomVertex is called domV, then its depth-first ("discovery") number is dfst.numberOf(domV.getContents()).

When you're stumped on how to do something

  1. Look to see how it's done in current PCESGraph code,
  2. check the API, then
  3. ask us for help.

Recommendation:  After updating an object with roles, call update() on each of its roles to have the changes appropriately reflected.  (Probably not needed for Lab 1.)