Graph.java

package us.brtm.cfg;

import org.objectweb.asm.tree.AbstractInsnNode;
import org.objectweb.asm.tree.LabelNode;
import org.objectweb.asm.tree.MethodNode;
import org.objectweb.asm.tree.analysis.*;
import us.brtm.cfg.generic.Node;

/**
 * Class that represents a Control Flow Graph constructed for a specified method.
 * Useful for static analysis of applications and/or compiler optimizations.
 *
 * @author Pedro Daia Cardoso
 */
public final class Graph {
    /**
     * The representation of the analyzed method.
     */
    private MethodNode method;
    /**
     * The analyzer instance of an analyzed method :P
     */
    private Analyzer analyzer;
    /**
     * All frames -- representing a block -- in the method.
     */
    private Frame[] frames;
    /**
     * The first or opening frame or node in the graph.
     */
    private Frame entryBlock;

    /**
     * @param owner  the internal name of the class to which the method belongs.
     * @param method the method to be analyzed.
     * @param debug  debug flag
     * @throws AnalyzerException if a problem occurs during the analysis.
     */
    public Graph(String owner, MethodNode method, boolean debug) throws AnalyzerException {
        if (debug) {
            System.out.println("Starting to build graph for " + owner + "." + method.name + "()");
        }
        this.method = method;
        this.analyzer = new Analyzer<BasicValue>(new BasicInterpreter()) {
            protected Frame<BasicValue> newFrame(int nLocals, int nStack) {
                return new Node(nLocals, nStack);
            }

            protected void newControlFlowEdge(int src, int dst) {
                Node s = (Node) getFrames()[src];
                s.getSuccessors().add((Node) getFrames()[dst]);
            }
        };
        analyzer.analyze(owner, method);
        int totalInsns = method.instructions.size();
        Frame entryBlock = locateEntryBlock();
        if (entryBlock == null && debug) {
            System.out.println("Entry block for the graph's null. Fail.");
        }
        this.entryBlock = entryBlock;
        optimizeMethod();
        if (debug) {
            System.out.println("Built graph for " + owner + "." + method.name + "().");
            System.out.println("Cyclomatic complexity: " + getCyclomaticComplexity());
            System.out.println("Optimized " + (totalInsns - method.instructions.size()) + " instructions.");
        }
    }

    public Frame locateEntryBlock() {
        for (Frame frame : frames) {
            if (((Node) frame).getSuccessors().size() > 0) {
                continue;
            }
            return frame;
        }
        return null;
    }

    /**
     * Optimizes the method by removing useless things and/or
     * simplifying the code.
     */
    public void optimizeMethod() {
        AbstractInsnNode[] instructions = method.instructions.toArray();
        for (int i = 0; i < frames.length; i++) {
            AbstractInsnNode instruction = instructions[i];
            if (frames[i] == null && !(instruction instanceof LabelNode)) {
                method.instructions.remove(instructions[i]);
            }
        }
    }

    /**
     * A simple method to calculate the cyclomatic complexity of a method. This metric is defined
     * as the number of edges in the control flow graph, minus the number of nodes, plus two.
     * The metric gives a good indication if the complexity of a method, which have a
     * relation with the average amount of bugs in the method.
     *
     * @return the cyclomatic complexity of this graph's method.
     */
    public int getCyclomaticComplexity() {
        int edges = 0;
        int nodes = 0;
        for (Frame frame : frames) {
            if (frame != null) {
                edges += ((Node) frame).getSuccessors().size();
                nodes += 1;
            }
        }
        return edges - nodes + 2;
    }

    /**
     * @return returns the analyzer instance
     */
    public Analyzer getAnalyzer() {
        return analyzer;
    }

    public Frame getEntryBlock() {
        return entryBlock;
    }
}