fix some warnings

[eclipsethinslicer.git] / Svelte / src / edu / berkeley / cs / bodik / svelte / plugin / cgview / CallGraphSlice.java

/*******************************************************************************
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html.
 * 
 * This file is a derivative of code released by the University of
 * California under the terms listed below.  
 *
 * Refinement Analysis Tools is Copyright ©2007 The Regents of the
 * University of California (Regents). Provided that this notice and
 * the following two paragraphs are included in any distribution of
 * Refinement Analysis Tools or its derivative work, Regents agrees
 * not to assert any of Regents' copyright rights in Refinement
 * Analysis Tools against recipient for recipient’s reproduction,
 * preparation of derivative works, public display, public
 * performance, distribution or sublicensing of Refinement Analysis
 * Tools and derivative works, in source code and object code form.
 * This agreement not to assert does not confer, by implication,
 * estoppel, or otherwise any license or rights in any intellectual
 * property of Regents, including, but not limited to, any patents
 * of Regents or Regents’ employees.
 * 
 * IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT,
 * INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
 * INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE
 * AND ITS DOCUMENTATION, EVEN IF REGENTS HAS BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *   
 * REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE AND FURTHER DISCLAIMS ANY STATUTORY
 * WARRANTY OF NON-INFRINGEMENT. THE SOFTWARE AND ACCOMPANYING
 * DOCUMENTATION, IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS
 * IS". REGENTS HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
 * UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 */
package edu.berkeley.cs.bodik.svelte.plugin.cgview;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;

import com.ibm.wala.ipa.callgraph.CGNode;
import com.ibm.wala.ipa.slicer.NormalReturnCallee;
import com.ibm.wala.ipa.slicer.NormalReturnCaller;
import com.ibm.wala.ipa.slicer.NormalStatement;
import com.ibm.wala.ipa.slicer.ParamCallee;
import com.ibm.wala.ipa.slicer.ParamCaller;
import com.ibm.wala.ipa.slicer.Statement;
import com.ibm.wala.types.TypeReference;
import com.ibm.wala.util.graph.Graph;

import edu.berkeley.cs.bodik.svelte.Slice;
import edu.berkeley.cs.bodik.svelte.StatementUtils;
import edu.berkeley.cs.bodik.svelte.plugin.SliceEnvironment;

public class CallGraphSlice {
        private Slice seed;
        // if you want to work on performance, you could try having using CGNode for this instead (need
        // another hash for string lookups)
        private Hashtable<String, Node> allnodes = null;

        // fakenewnodes are added to represent new X() calls which assign a default value of x.property.
        // for instance, if the function foo() contains the line "b = new Bar()", which causes
        // b.myObject to have a default
        // value of null, and b.myObject is used later in function hello(), we don't want to show foo()
        // having a direct edge to hello()
        // rather we want to show an edge from foo to a "fake new node", and from this to hello()
//      private Hashtable<TypeReference, FakeNewNode> fakenewnodes = null;
    // 2008-05-06: wasn't read so was giving a warning, taken out. I don't know why?
        
        // really a hash set
        private Hashtable<Edge, Edge> alledges = null;

        // a mapping from class -> unique index, 1,2,3,... in the order came upon by the BFS traversal
        // of the slice.
        Hashtable<String, Integer> classesToIndices;

        private Hashtable<Node, ArrayList<Edge>> predEdges = null;
        private int depth;

        public CallGraphSlice(Slice seed, int depth) {
                this.seed = seed;
                this.depth = depth;
        }

        class Node {
                boolean drawPredNodes = false;
        }

        class RegularNode extends Node {
                CGNode node;

                public RegularNode(CGNode node) {
                        this.node = node;
                }

                @Override
                public int hashCode() {
                        return node.getMethod().getSignature().hashCode();
                }

                @Override
                public boolean equals(Object xx) {
                        RegularNode x;
                        return (xx instanceof RegularNode) && ((x = (RegularNode) xx) != null)
                                        && x.node.getMethod().getSignature().equals(node.getMethod().getSignature());
                        // compare based on signature.
                }

                @Override
                public String toString() {
                        return node.getMethod().getSignature();
                }
        }

        class FakeNewNode extends Node {
                TypeReference typref; // reference to the constructor function

                public FakeNewNode(TypeReference newInstType) {
                        this.typref = newInstType;
                }

                @Override
                public int hashCode() {
                        return typref.toString().hashCode();
                }

                @Override
                public boolean equals(Object xx) {
                        FakeNewNode x;
                        return (xx instanceof FakeNewNode) && ((x = (FakeNewNode) xx) != null)
                                        && x.typref.toString().equals(typref.toString());
                        // compare based on signature.
                }

                @Override
                public String toString() {
                        return typref.toString();
                }
        }

        class Edge {
                public static final int TYPE_THRU_PARAM = 1;
                public static final int TYPE_THRU_RETVAL = 2;
                public static final int TYPE_THRU_ALIASING = 3;

                public int type;
                public int duplicity;
                public Node from;
                public Node to;

                public Edge(int type, Node from, Node to) {
                        this.type = type;
                        this.duplicity = 1;
                        this.from = from;
                        this.to = to;
                }

                @Override
                public int hashCode() {
                        return from.hashCode() + to.hashCode() + type;
                }

                @Override
                public boolean equals(Object xx) {
                        Edge x;
                        return (xx instanceof Edge) && ((x = (Edge) xx) != null) && from.equals(x.from)
                                        && to.equals(x.to) && type == x.type;
                }

        }

        private Node getNodeFromCGNode(CGNode cgn) {
                assert (allnodes != null);
                Node node = allnodes.get(cgn.getMethod().getSignature());
                if (node == null) {
                        node = new RegularNode(cgn);
                        allnodes.put(cgn.getMethod().getSignature(), node);

                        // if this class not listed in classesToColor, add this class.
                        String sig = node.toString();
                        int lastdot = sig.lastIndexOf('.');
                        String classname = sig.substring(0, lastdot);
                        if (classesToIndices.get(classname) == null)
                                classesToIndices.put(classname, new Integer(classesToIndices.size() + 1));
                }
                return node;
        }

        /**
         * Add edge to alledges and tosPredEdges. If it is already in (check all edges but should be in
         * both in), just increments the duplicity (if the second arg is true)
         * 
         * @param edgeToAdd
         */
        private void addEdge(Edge edgeToAdd, boolean ignoreIfAlreadyIn) {
                if (edgeToAdd != null) {
                        Edge alreadyIn = alledges.get(edgeToAdd);
                        if (alreadyIn == null) {
                                alledges.put(edgeToAdd, edgeToAdd);

                                ArrayList<Edge> tosPredEdges = predEdges.get(edgeToAdd.to);
                                if (tosPredEdges == null) {
                                        tosPredEdges = new ArrayList<Edge>();
                                        predEdges.put(edgeToAdd.to, tosPredEdges);
                                }
                                tosPredEdges.add(edgeToAdd);
                        } else {
                                if (!ignoreIfAlreadyIn)
                                        alreadyIn.duplicity += 1;
                        }
                }
        }

        private Node getOrMakeFakeNewNode(TypeReference newInstType) {
                assert (allnodes != null);
                Node node = allnodes.get(newInstType.toString());
                if (node == null) {
                        node = new FakeNewNode(newInstType);
                        allnodes.put(newInstType.toString(), node);

                        // if this class not listed in classesToColor, add this class.
                        String classname = newInstType.getClass().toString();
                        System.out.println("DEBUG fakenewnode class = " + classname);
                        if (classesToIndices.get(classname) == null)
                                classesToIndices.put(classname, new Integer(classesToIndices.size() + 1));
                }
                return node;
        }

        // this also calculates the colors (via getNodeFromCGNode)
        public void recalculateGraph() {
                // clear nodes & edges
                allnodes = new Hashtable<String, Node>();
//              fakenewnodes = new Hashtable<TypeReference, FakeNewNode>();
                alledges = new Hashtable<Edge, Edge>();
                predEdges = new Hashtable<Node, ArrayList<Edge>>();
                classesToIndices = new Hashtable<String, Integer>();

                // do the cgview stuff and generate the dot code

                // NEVER fix method seed statements here. They should have already been fixed in the seed.

                Graph<Statement> depGraph = SliceEnvironment.getDepGraph();

                ArrayList<Statement> worklist = new ArrayList<Statement>();
                HashSet<Statement> serviced = new HashSet<Statement>();
                // BFS time, baby
                worklist.addAll(seed.getStatements());

                int level = 0;
                int nextlevelindex = worklist.size();

                int index = -1;
                while ((index + 1) < worklist.size()) {
                        index++;
                        if (index == nextlevelindex) {
                                nextlevelindex = worklist.size();
                                level++;
                                if (level > depth)
                                        break;
                        }
                        Statement s = worklist.get(index);

                        // service it
                        if (serviced.contains(s))
                                continue;
                        serviced.add(s);

                        // look thru the succ nodes, if theres any 'return val' ones or something, build the
                        // bridge.
                        Iterator<? extends Statement> succNodes = depGraph.getSuccNodes(s);
                        Statement ss;
                        while (succNodes.hasNext()) {
                                ss = succNodes.next();

                                Node fromnode = null, tonode = null;

                                if (s instanceof ParamCallee && ss instanceof ParamCaller) {
                                        // node of ss calls node of s, passing in the data as a parameter
                                        tonode = getNodeFromCGNode(((ParamCallee) s).getNode());
                                        fromnode = getNodeFromCGNode(((ParamCaller) ss).getNode());
                                        addEdge(new Edge(Edge.TYPE_THRU_PARAM, fromnode, tonode), false);
                                } else if (s instanceof NormalReturnCaller && ss instanceof NormalReturnCallee) {
                                        // node of s calls node of ss, gets data from node of ss as a return value
                                        tonode = getNodeFromCGNode(((NormalReturnCaller) s).getNode());
                                        fromnode = getNodeFromCGNode(((NormalReturnCallee) ss).getNode());
                                        addEdge(new Edge(Edge.TYPE_THRU_RETVAL, fromnode, tonode), false);
                                } else if (s instanceof NormalStatement && ss instanceof NormalStatement
                                                && ((NormalStatement) s).getNode() != ((NormalStatement) ss).getNode()) {
                                        // ss writes to some pointerkey which s reads from, thereby passing data
                                        // (possibly)

                                        tonode = getNodeFromCGNode(((NormalStatement) s).getNode());
                                        fromnode = getNodeFromCGNode(((NormalStatement) ss).getNode());

                                        TypeReference newInstType = StatementUtils.getNewInstructionDeclaredType(ss);
                                        if (newInstType != null) { // if it's a SSANewInstruction
                                                // System.out.println("fakenewnode from " + ss + " --to-- " + s);
                                                Node fakenewnode = getOrMakeFakeNewNode(newInstType);
                                                addEdge(new Edge(Edge.TYPE_THRU_ALIASING, fakenewnode, tonode), true); // don't
                                                // count
                                                // duplicity
                                                // for
                                                // this
                                                // edge
                                                addEdge(new Edge(Edge.TYPE_THRU_PARAM, fromnode, fakenewnode), false);
                                        } else
                                                addEdge(new Edge(Edge.TYPE_THRU_ALIASING, fromnode, tonode), false);
                                }

                                // add succ nodes to worklist if not already serviced.
                                if (!serviced.contains(ss))
                                        worklist.add(ss);
                        }
                }

                System.out.println("! total # of nodes: " + allnodes.size());
                System.out.println("! total # of edges: " + alledges.size());
                System.out.println("! total # of statements: " + index);

        }

        public void toggleCollapsed(String nodename) {
                if (allnodes != null) {
                        Node node = allnodes.get(nodename);
                        if (node != null) {
                                node.drawPredNodes = !node.drawPredNodes;
                        } else {
                                System.err.println("can't find node " + nodename + "!");
                        }
                }
        }

        public StringBuffer generateDot() {
                if (predEdges == null)
                        recalculateGraph();

                // do a BFS of the CG slice graph and find which nodes and edges to draw.
                HashSet<Node> nodesToDraw = new HashSet<Node>();
                // HashSet<Edge> edgesToDraw = new HashSet<Edge>();

                ArrayList<Node> orderedNodesToDraw = new ArrayList<Node>(); // preserver order of BFS to not
                // surprise users when they
                // expand/collapse things
                ArrayList<Edge> orderedEdgesToDraw = new ArrayList<Edge>();

                ArrayList<Node> worklist = new ArrayList<Node>();
                // BFS time, baby

                // start at the seed, as always
                for (Statement s : seed) {
                        if (s instanceof NormalStatement) {
                                worklist.add(getNodeFromCGNode(((NormalStatement) s).getNode()));
                        }
                }

                int index = -1;
                while ((index + 1) < worklist.size()) {
                        index++;
                        Node n = worklist.get(index);

                        // service it
                        if (nodesToDraw.contains(n))
                                continue;
                        nodesToDraw.add(n);
                        orderedNodesToDraw.add(n);

                        // look thru the nodes pointing to it and add them
                        if (n.drawPredNodes) {
                                ArrayList<Edge> nsPredEdges = predEdges.get(n);
                                if (nsPredEdges != null) {
                                        for (Edge e : nsPredEdges) {
                                                worklist.add(e.from);
                                                // edgesToDraw.add(e);
                                                orderedEdgesToDraw.add(e);
                                        }
                                }
                        }
                }
                return generateDot(orderedNodesToDraw, orderedEdgesToDraw);
        }

        public StringBuffer generateDot(Collection<Node> nodes, Collection<Edge> edges) {
                StringBuffer buf = new StringBuffer();

                // general stuff
                buf.append("digraph callgraphslice {\n");
                buf.append("rankdir=RL;\n");
                buf
                                .append("node [shape=rect,height=0,width=0,fontsize=12,fillcolor=mediumaquamarine,style=filled]\n");

                // nodes (need URL property)

                String[] colors = { "greenyellow", "aliceblue", "salmon", "lightskyblue", "lightslateblue",
                                "peru" };

                for (Node n : nodes) {
                        String sig = n.toString();
                        String label = sig;
                        Integer colorindex = null;
                        try {
                                int lastdot = sig.lastIndexOf('.');
                                String classname = sig.substring(0, lastdot);
                                String methodname = sig.substring(lastdot + 1, sig.length());
                                lastdot = classname.lastIndexOf('.');
                                String classclassname = classname.substring(lastdot + 1, classname.length());

                                label = methodname + " -- " + classclassname;
                                colorindex = classesToIndices.get(classname);
                        } catch (Exception e) {

                        }
                        String color = "lightgrey";
                        if (colorindex != null)
                                color = colors[colorindex.intValue() % colors.length];

                        buf.append(String.format(
                                        "\"%s\" [URL=\"%s\",fillcolor=\"%s\",label=\"%s\",color=\"%s\"]\n", n, n,
                                        color, label, ((!n.drawPredNodes) && predEdges.get(n) != null) ? "black"
                                                        : color));
                }

                // edges
                for (Edge e : edges) {
                        String s = String.format("\"%s\" -> \"%s\" [", e.from, e.to);
                        if (e.duplicity > 1)
                                s += String.format("label=\"x%2d\",", e.duplicity);

                        if (e.type == Edge.TYPE_THRU_PARAM)
                                s += "color=blue";
                        else if (e.type == Edge.TYPE_THRU_RETVAL)
                                s += "color=red,arrowhead=inv";
                        else if (e.type == Edge.TYPE_THRU_ALIASING)
                                s += "style=dashed";

                        s += "]\n";
                        buf.append(s);
                }

                buf.append("}\n");
                return buf;

        }

}