1/* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Eclipse Public License, Version 1.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.eclipse.org/org/documents/epl-v10.php 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16package com.android.tools.lint.checks; 17 18import com.android.annotations.NonNull; 19import com.android.annotations.Nullable; 20import com.google.common.collect.Maps; 21 22import org.objectweb.asm.tree.AbstractInsnNode; 23import org.objectweb.asm.tree.ClassNode; 24import org.objectweb.asm.tree.FrameNode; 25import org.objectweb.asm.tree.InsnList; 26import org.objectweb.asm.tree.LabelNode; 27import org.objectweb.asm.tree.LineNumberNode; 28import org.objectweb.asm.tree.MethodInsnNode; 29import org.objectweb.asm.tree.MethodNode; 30import org.objectweb.asm.tree.TryCatchBlockNode; 31import org.objectweb.asm.tree.analysis.Analyzer; 32import org.objectweb.asm.tree.analysis.AnalyzerException; 33import org.objectweb.asm.tree.analysis.BasicInterpreter; 34 35import java.lang.reflect.Field; 36import java.util.ArrayList; 37import java.util.List; 38import java.util.Map; 39 40/** 41 * A {@linkplain ControlFlowGraph} is a graph containing a node for each 42 * instruction in a method, and an edge for each possible control flow; usually 43 * just "next" for the instruction following the current instruction, but in the 44 * case of a branch such as an "if", multiple edges to each successive location, 45 * or with a "goto", a single edge to the jumped-to instruction. 46 * <p> 47 * It also adds edges for abnormal control flow, such as the possibility of a 48 * method call throwing a runtime exception. 49 */ 50public class ControlFlowGraph { 51 /** Map from instructions to nodes */ 52 private Map<AbstractInsnNode, Node> mNodeMap; 53 54 /** 55 * Creates a new {@link ControlFlowGraph} and populates it with the flow 56 * control for the given method. If the optional {@code initial} parameter is 57 * provided with an existing graph, then the graph is simply populated, not 58 * created. This allows subclassing of the graph instance, if necessary. 59 * 60 * @param initial usually null, but can point to an existing instance of a 61 * {@link ControlFlowGraph} in which that graph is reused (but 62 * populated with new edges) 63 * @param classNode the class containing the method to be analyzed 64 * @param method the method to be analyzed 65 * @return a {@link ControlFlowGraph} with nodes for the control flow in the 66 * given method 67 * @throws AnalyzerException if the underlying bytecode library is unable to 68 * analyze the method bytecode 69 */ 70 @NonNull 71 public static ControlFlowGraph create( 72 @Nullable ControlFlowGraph initial, 73 @NonNull ClassNode classNode, 74 @NonNull MethodNode method) throws AnalyzerException { 75 final ControlFlowGraph graph = initial != null ? initial : new ControlFlowGraph(); 76 final InsnList instructions = method.instructions; 77 graph.mNodeMap = Maps.newHashMapWithExpectedSize(instructions.size()); 78 79 // Create a flow control graph using ASM4's analyzer. According to the ASM 4 guide 80 // (download.forge.objectweb.org/asm/asm4-guide.pdf) there are faster ways to construct 81 // it, but those require a lot more code. 82 Analyzer analyzer = new Analyzer(new BasicInterpreter()) { 83 @Override 84 protected void newControlFlowEdge(int insn, int successor) { 85 // Update the information as of whether the this object has been 86 // initialized at the given instruction. 87 AbstractInsnNode from = instructions.get(insn); 88 AbstractInsnNode to = instructions.get(successor); 89 graph.add(from, to); 90 } 91 92 @Override 93 protected boolean newControlFlowExceptionEdge(int insn, TryCatchBlockNode tcb) { 94 AbstractInsnNode from = instructions.get(insn); 95 graph.exception(from, tcb); 96 return super.newControlFlowExceptionEdge(insn, tcb); 97 } 98 99 @Override 100 protected boolean newControlFlowExceptionEdge(int insn, int successor) { 101 AbstractInsnNode from = instructions.get(insn); 102 AbstractInsnNode to = instructions.get(successor); 103 graph.exception(from, to); 104 return super.newControlFlowExceptionEdge(insn, successor); 105 } 106 }; 107 108 analyzer.analyze(classNode.name, method); 109 return graph; 110 } 111 112 /** A {@link Node} is a node in the control flow graph for a method, pointing to 113 * the instruction and its possible successors */ 114 public static class Node { 115 /** The instruction */ 116 public final AbstractInsnNode instruction; 117 /** Any normal successors (e.g. following instruction, or goto or conditional flow) */ 118 public final List<Node> successors = new ArrayList<Node>(2); 119 /** Any abnormal successors (e.g. the handler to go to following an exception) */ 120 public final List<Node> exceptions = new ArrayList<Node>(1); 121 122 /** A tag for use during depth-first-search iteration of the graph etc */ 123 public int visit; 124 125 /** 126 * Constructs a new control graph node 127 * 128 * @param instruction the instruction to associate with this node 129 */ 130 public Node(@NonNull AbstractInsnNode instruction) { 131 this.instruction = instruction; 132 } 133 134 void addSuccessor(@NonNull Node node) { 135 if (!successors.contains(node)) { 136 successors.add(node); 137 } 138 } 139 140 void addExceptionPath(@NonNull Node node) { 141 if (!exceptions.contains(node)) { 142 exceptions.add(node); 143 } 144 } 145 146 /** 147 * Represents this instruction as a string, for debugging purposes 148 * 149 * @param includeAdjacent whether it should include a display of 150 * adjacent nodes as well 151 * @return a string representation 152 */ 153 @NonNull 154 public String toString(boolean includeAdjacent) { 155 StringBuilder sb = new StringBuilder(); 156 157 sb.append(getId(instruction)); 158 sb.append(':'); 159 160 if (instruction instanceof LabelNode) { 161 //LabelNode l = (LabelNode) instruction; 162 //sb.append('L' + l.getLabel().getOffset() + ":"); 163 //sb.append('L' + l.getLabel().info + ":"); 164 sb.append("LABEL"); 165 } else if (instruction instanceof LineNumberNode) { 166 sb.append("LINENUMBER " + ((LineNumberNode) instruction).line); 167 } else if (instruction instanceof FrameNode) { 168 sb.append("FRAME"); 169 } else { 170 int opcode = instruction.getOpcode(); 171 // AbstractVisitor isn't available unless debug/util is included, 172 boolean printed = false; 173 try { 174 Class<?> c = Class.forName("org.objectweb.asm.util"); //$NON-NLS-1$ 175 Field field = c.getField("OPCODES"); 176 String[] OPCODES = (String[]) field.get(null); 177 printed = true; 178 if (opcode > 0 && opcode <= OPCODES.length) { 179 sb.append(OPCODES[opcode]); 180 if (instruction.getType() == AbstractInsnNode.METHOD_INSN) { 181 sb.append("(" + ((MethodInsnNode)instruction).name + ")"); 182 } 183 } 184 } catch (Throwable t) { 185 // debug not installed: just do toString() on the instructions 186 } 187 if (!printed) { 188 sb.append(instruction.toString()); 189 } 190 } 191 192 if (includeAdjacent) { 193 if (successors != null && !successors.isEmpty()) { 194 sb.append(" Next:"); 195 for (Node s : successors) { 196 sb.append(' '); 197 sb.append(s.toString(false)); 198 } 199 } 200 201 if (exceptions != null && !exceptions.isEmpty()) { 202 sb.append(" Exceptions:"); 203 for (Node s : exceptions) { 204 sb.append(' '); 205 sb.append(s.toString(false)); 206 } 207 } 208 sb.append('\n'); 209 } 210 211 return sb.toString(); 212 } 213 } 214 215 /** Adds an exception flow to this graph */ 216 protected void add(@NonNull AbstractInsnNode from, @NonNull AbstractInsnNode to) { 217 getNode(from).addSuccessor(getNode(to)); 218 } 219 220 /** Adds an exception flow to this graph */ 221 protected void exception(@NonNull AbstractInsnNode from, @NonNull AbstractInsnNode to) { 222 // For now, these edges appear useless; we also get more specific 223 // information via the TryCatchBlockNode which we use instead. 224 //getNode(from).addExceptionPath(getNode(to)); 225 } 226 227 /** Adds an exception try block node to this graph */ 228 protected void exception(@NonNull AbstractInsnNode from, @NonNull TryCatchBlockNode tcb) { 229 // Add tcb's to all instructions in the range 230 LabelNode start = tcb.start; 231 LabelNode end = tcb.end; // exclusive 232 233 // Add exception edges for all method calls in the range 234 AbstractInsnNode curr = start; 235 Node handlerNode = getNode(tcb.handler); 236 while (curr != end && curr != null) { 237 if (curr.getType() == AbstractInsnNode.METHOD_INSN) { 238 // Method call; add exception edge to handler 239 if (tcb.type == null) { 240 // finally block: not an exception path 241 getNode(curr).addSuccessor(handlerNode); 242 } else { 243 getNode(curr).addExceptionPath(handlerNode); 244 } 245 } 246 curr = curr.getNext(); 247 } 248 } 249 250 /** 251 * Looks up (and if necessary) creates a graph node for the given instruction 252 * 253 * @param instruction the instruction 254 * @return the control flow graph node corresponding to the given 255 * instruction 256 */ 257 @NonNull 258 public Node getNode(@NonNull AbstractInsnNode instruction) { 259 Node node = mNodeMap.get(instruction); 260 if (node == null) { 261 node = new Node(instruction); 262 mNodeMap.put(instruction, node); 263 } 264 265 return node; 266 } 267 268 /** 269 * Creates a human readable version of the graph 270 * 271 * @param start the starting instruction, or null if not known or to use the 272 * first instruction 273 * @return a string version of the graph 274 */ 275 @NonNull 276 public String toString(@Nullable Node start) { 277 StringBuilder sb = new StringBuilder(); 278 279 AbstractInsnNode curr = null; 280 if (start != null) { 281 curr = start.instruction; 282 } else { 283 if (mNodeMap.isEmpty()) { 284 return "<empty>"; 285 } else { 286 curr = mNodeMap.keySet().iterator().next(); 287 while (curr.getPrevious() != null) { 288 curr = curr.getPrevious(); 289 } 290 } 291 } 292 293 while (curr != null) { 294 Node n = mNodeMap.get(curr); 295 if (n != null) { 296 sb.append(n.toString(true)); 297 } 298 curr = curr.getNext(); 299 } 300 301 return sb.toString(); 302 } 303 304 @Override 305 public String toString() { 306 return toString(null); 307 } 308 309 // ---- For debugging only ---- 310 311 private static Map<Object, String> sIds = null; 312 private static int sNextId = 1; 313 private static String getId(Object object) { 314 if (sIds == null) { 315 sIds = Maps.newHashMap(); 316 } 317 String id = sIds.get(object); 318 if (id == null) { 319 id = Integer.toString(sNextId++); 320 sIds.put(object, id); 321 } 322 return id; 323 } 324} 325 326