Updates for call graph slice view (latest is click constructor fix) and

[eclipsethinslicer.git] / Svelte / src / edu / berkeley / cs / bodik / svelte / CGNodeUtils.java

package edu.berkeley.cs.bodik.svelte;

import java.io.IOException;
import java.io.InputStream;
import java.net.URL;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

import com.ibm.wala.cast.java.loader.JavaSourceLoaderImpl.ConcreteJavaMethod;
import com.ibm.wala.cast.tree.CAstSourcePositionMap.Position;
import com.ibm.wala.classLoader.IMethod;
import com.ibm.wala.classLoader.ShrikeBTMethod;
import com.ibm.wala.ipa.callgraph.CGNode;
import com.ibm.wala.ipa.slicer.NormalStatement;
import com.ibm.wala.ipa.slicer.Statement;
import com.ibm.wala.shrikeCT.InvalidClassFileException;
import com.ibm.wala.ssa.IR;
import com.ibm.wala.ssa.SSAInstruction;
import com.ibm.wala.ssa.SSAInvokeInstruction;
import com.ibm.wala.util.collections.HashSetFactory;
import com.ibm.wala.util.debug.Assertions;
import com.ibm.wala.util.intset.IntSet;

/**
 * Utilities dealing with Call Graph Nodes (which are essentially methods)
 * These would be handy in the CGNode itself.
 * Most of these are only useful for methods coming from a real .java
 * or .class file we are analyzing.
 * 
 * @author evan
 *
 */
public class CGNodeUtils {

        /**
         * Do a brute-force search thru the statements of the Call Graph and find
         * the lexically first statement which calls a method called <code>methodName</code>
         * 
         * @param n
         * The method with code to search through.
         * @param methodName
         * The method name, irrespective of class it is defined in, whether it is static, etc. 
         * @return
         * The statement found (i.e. an invokestatic or invokevirtual statement), or null if none found.
         */
        public static Statement findCallTo(CGNode n, String methodName) {
                IR ir = n.getIR();
                for (Iterator<SSAInstruction> it = ir.iterateAllInstructions(); it.hasNext();) {
                        SSAInstruction s = it.next();
                        if (s instanceof SSAInvokeInstruction) {
                                SSAInvokeInstruction call = (SSAInvokeInstruction) s;
                                if (call.getCallSite().getDeclaredTarget().getName().toString().equals(methodName)) {
                                        IntSet indices = ir.getCallInstructionIndices(((SSAInvokeInstruction) s).getCallSite());
                                        Assertions.productionAssertion(indices.size() == 1, "expected 1 but got " + indices.size());
                                        return new NormalStatement(n, indices.intIterator().next());
                                }
                        }
                }
                Assertions.UNREACHABLE("failed to find call to " + methodName + " in " + n);
                return null;
        }

        /**
         * Find a particular SSA instruction in the method's instructions (by a simple brute force search),
         * and create a NormalStatement from this. A NormalStatement contains the CGNode and the
         * index of the instruction in the method's instructions.
         * 
         * @param node
         * @param instr
         * @return
         * A NormalStatement representing the instruction, or <code>null</code> if the
         * instruction was not found in the method.  
         */
        public static NormalStatement findStatementFromSSAInstruction(CGNode node, SSAInstruction instr) {
                SSAInstruction instrs[] = node.getIR().getInstructions();
                for ( int i = 0; i < instrs.length; i++ ) {
                        if ( instrs[i] == instr )
                                return new NormalStatement(node, i);
                }
                return null;
        }
        
        /**
         * Given a CGNode and a line number, does a brute force search for statements in the CGNode
         * which have that line number in the given source code. There's probably a better way to do this.
         * If not, this should at least be a binary search. Note that you have to have the CGNode for the
         * method to do this first off. Returns the FIRST statement only (until I can figure out how
         * to use Set) 
         * 
         * @param node
         * The method containing statements to look thru.
         * 
         * @param linenumber
         * The original source line number to look for. 
         */
        public static Statement getStatementFromLineNumber(CGNode node, int linenumber) {
                SSAInstruction[] instrs = node.getIR().getInstructions();
                for ( int i = 0; i < instrs.length; i++ ) {
                        if (((ConcreteJavaMethod) node.getMethod()).getLineNumber(i) == linenumber)
                                return new NormalStatement(node, i);
                }
                return null;
        }

        /**
         * Given a CGNode and a line number, does a brute force search for statements in the CGNode
         * which have that line number in the given source code. There's probably a better way to do this.
         * If not, this should at least be a binary search. Note that you have to have the CGNode for the
         * method to do this first off. Returns all statements.
         * 
         * @param node
         * The method containing statements to look thru.
         * 
         * @param linenumber
         * The original source line number to look for. 
         */     
        public static ArrayList<Statement> getStatementsFromLineNumber(CGNode node, int linenumber) {
                ArrayList<Statement> result = new ArrayList<Statement>(); 
                SSAInstruction[] instrs = node.getIR().getInstructions();

                
                for ( int i = 0; i < instrs.length; i++ ) {
                        SourcePosition pos;
                        
                        // FIXME: may fail for Shrike instrs on multiple lines
//                      if (instrs[i] != null && ((pos = getSourcePositionOfInstructionIndex(node,i)) != null)) 
//                              System.out.println("looking for "+linenumber+" it's not " +pos.lineStart);
//                      else if (instrs[i] != null)
//                              System.out.println("couldn't get pos!");

                        if (instrs[i] != null && ((pos = getSourcePositionOfInstructionIndex(node,i)) != null) && linenumber == pos.lineStart ) {
                                // FIXME: instructions like conditional branches, switches, and gotos seem to encompass many lines, ... adding seeds we don't really want.
                                // for a conditional, we probably want the first line. for other things, this may not work as well.... analyze elements, not statements?
                                // linenumber >= pos.lineStart && linenumber <= pos.lineEnd
                                result.add(new NormalStatement(node, i));

                                // NOTE: instrs[i] could be null if the instrcution
                                // has been optimized out. this could be useful later on.
                                
                        }
                }
                return result;
        }

        
        
        
        // used only to represent start and end lines for a Shrike method.
        private static class ShrikeBTMethodPosition implements Position {
                private int firstline;
                private int lastline;

                public ShrikeBTMethodPosition(int firstline, int lastline) {
                        this.firstline = firstline;
                        this.lastline = lastline;
                }

                @Override
                public int getFirstCol() {
                        return -1;
                }

                @Override
                public int getFirstLine() {
                        return firstline;
                }

                @Override
                public InputStream getInputStream() throws IOException {
                        return null;
                }

                @Override
                public int getLastCol() {
                        return -1;
                }

                @Override
                public int getLastLine() {
                        return lastline;
                }

                @Override
                public URL getURL() {
                        return null;
                }

                @Override
                public int compareTo(Object o) {
                        return 0;
                }

                @Override
                public int getFirstOffset() {
                        return -1;
                }

                @Override
                public int getLastOffset() {
                        return -1;
                }
        }
        
        /**
         * Find lexically first and last instruction in the method and return a Position
         * with their line numbers.
         */
        public static Position getSourcePosition(ShrikeBTMethod met) {
                try {
                        int firstline = met.getLineNumber(met.getBytecodeIndex(0));
                        int lastinstr = met.getInstructions().length - 1;
                        int lastline = met.getLineNumber(met.getBytecodeIndex(lastinstr));
                        return new ShrikeBTMethodPosition(firstline,lastline);
                } catch (InvalidClassFileException e) {
                        e.printStackTrace();
                }
                return null;
        }
        
        /**
         * Return a Position representing the position of the method in the original source file.
         * In the case of Shrike methods, these will be the line numbers of the first and last
         * instruction that show up in the IR of the method.
         *  
         * @param cgn
         * The CGNode of the method.
         * @return
         * The position, or <code>null</code> it the method is neither a ConcreteJavaMethod or ShrikeBTMethod. 
         */
        public static Position getSourcePosition(CGNode cgn) {
                IMethod met = cgn.getMethod();
                if ( met instanceof ConcreteJavaMethod ) {
                        return ((ConcreteJavaMethod) met).getSourcePosition();
                } else if ( met instanceof ShrikeBTMethod ) {
                        return getSourcePosition((ShrikeBTMethod)met);
                } else
                        return null;
        }
        
        /**
         * Gets as much information as possible about where in the original source a
         * particular IR instruction is in the method. For a method originating from CAst,
         * this will be start line and column information, as well as an absolute path.
         * For a method originating from Shrike, this will be a line number (first line and
         * last line are equal), and the name of the class (the filename must then be looked
         * up from the class.)
         *  
         * @param cgn
         * @param instructionIndex
         * @return
         */
        public static SourcePosition getSourcePositionOfInstructionIndex(CGNode cgn, int instructionIndex) {
                IMethod met = cgn.getMethod();
                if ( met instanceof ConcreteJavaMethod ) {
                        Position pos = ((ConcreteJavaMethod) met).getSourcePosition(instructionIndex);
                        return new SourcePosition(pos.getFirstLine(),pos.getLastLine(),
                                        pos.getFirstOffset(),pos.getLastOffset(),
                                        met.getDeclaringClass().getSourceFileName(),
                                        met.getDeclaringClass().getName().toString() );
                } else if ( met instanceof ShrikeBTMethod ) {
                        try {
                                int bcIndex = ((ShrikeBTMethod) met).getBytecodeIndex(instructionIndex);
                                int linenum = met.getLineNumber(bcIndex);
                                return new SourcePosition ( linenum, linenum, -1, -1,
                                                met.getDeclaringClass().getSourceFileName(), // this will probably be null so pass in the classname
                                                met.getDeclaringClass().getName().toString());
                        } catch (InvalidClassFileException e) {
                                e.printStackTrace();
                        }
                } 
                return null;
        }

}