Yue Gan | af3c412 | 2016-12-05 14:36:02 +0000 | [diff] [blame] | 1 | // Copyright 2016 The Bazel Authors. All Rights Reserved. |
| 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
| 15 | package com.google.testing.coverage; |
| 16 | |
| 17 | import java.util.ArrayList; |
| 18 | import java.util.HashMap; |
| 19 | import java.util.List; |
| 20 | import java.util.Map; |
| 21 | import java.util.TreeMap; |
| 22 | import org.jacoco.core.internal.flow.IFrame; |
| 23 | import org.jacoco.core.internal.flow.Instruction; |
| 24 | import org.jacoco.core.internal.flow.LabelInfo; |
| 25 | import org.jacoco.core.internal.flow.MethodProbesVisitor; |
| 26 | import org.objectweb.asm.Handle; |
| 27 | import org.objectweb.asm.Label; |
| 28 | |
| 29 | /** |
| 30 | * The mapper is a probes visitor that will cache control flow information as well as keeping track |
| 31 | * of the probes as the main driver generates the probe ids. Upon finishing the method it uses the |
| 32 | * information collected to generate the mapping information between probes and the instructions. |
| 33 | */ |
| 34 | public class MethodProbesMapper extends MethodProbesVisitor { |
| 35 | /* |
| 36 | * The implementation roughly follows the same pattern of the Analyzer class of Jacoco. |
| 37 | * |
| 38 | * The mapper has a few states: |
| 39 | * |
| 40 | * - lineMappings: a mapping between line number and labels |
| 41 | * |
| 42 | * - a sequence of "instructions", where each instruction has one or more predecessors. The |
| 43 | * predecessor field has a sole purpose of propagating probe id. The 'merge' nodes in the CFG has |
| 44 | * no predecessors, since the branch stops at theses points. |
| 45 | * |
| 46 | * - The instructions each has states that keep track of the probes that are associated with the |
| 47 | * instruction. |
| 48 | * |
| 49 | * Initially the probe ids are assigned to the instructions that immediately precede the probe. At |
| 50 | * the end of visiting the methods, the probe ids are propagated through the predecessor chains. |
| 51 | */ |
| 52 | |
| 53 | // States |
| 54 | // |
| 55 | // These are state variables that needs to be updated in the visitor methods. |
| 56 | // The values usually changes as we traverse the byte code. |
| 57 | private Instruction lastInstruction = null; |
| 58 | private int currentLine = -1; |
| 59 | private List<Label> currentLabels = new ArrayList<>(); |
| 60 | |
| 61 | // Result |
| 62 | private Map<Integer, BranchExp> lineToBranchExp = new TreeMap(); |
| 63 | |
| 64 | public Map<Integer, BranchExp> result() { |
| 65 | return lineToBranchExp; |
| 66 | } |
| 67 | |
| 68 | // Intermediate results |
| 69 | // |
| 70 | // These values are built up during the visitor methods. They will be used to compute |
| 71 | // the final results. |
| 72 | private List<Instruction> instructions = new ArrayList<Instruction>(); |
| 73 | private List<Jump> jumps = new ArrayList<>(); |
| 74 | private Map<Integer, Instruction> probeToInsn = new TreeMap<>(); |
| 75 | |
| 76 | // A map which associates intructions with their coverage expressions. |
| 77 | private final Map<Instruction, CovExp> insnToCovExp = new HashMap(); |
| 78 | |
| 79 | // A map which associates a instruction to the branch index in its predecessor |
| 80 | // e.g., the instruction that follows a conditional jump instruction must exists in |
| 81 | // this map. |
| 82 | private final Map<Instruction, Integer> insnToIdx = new HashMap(); |
| 83 | |
| 84 | // Local cache |
| 85 | // |
| 86 | // These are maps corresponding to data structures available in JaCoCo in other form. |
| 87 | // We use local data structure to avoid need to change the JaCoCo internal code. |
| 88 | private Map<Instruction, Instruction> predecessors = new HashMap<>(); |
| 89 | private Map<Label, Instruction> labelToInsn = new HashMap<>(); |
| 90 | |
| 91 | /** Visitor method to append a new Instruction */ |
| 92 | private void visitInsn() { |
| 93 | Instruction instruction = new Instruction(currentLine); |
| 94 | instructions.add(instruction); |
| 95 | if (lastInstruction != null) { |
| 96 | instruction.setPredecessor(lastInstruction); // Update branch of lastInstruction |
| 97 | predecessors.put(instruction, lastInstruction); // Update local cache |
| 98 | } |
| 99 | |
| 100 | for (Label label : currentLabels) { |
| 101 | labelToInsn.put(label, instruction); |
| 102 | } |
| 103 | currentLabels.clear(); // Update states |
| 104 | lastInstruction = instruction; |
| 105 | } |
| 106 | |
| 107 | // Plain visitors: called from adapter when no probe is needed |
| 108 | @Override |
| 109 | public void visitInsn(int opcode) { |
| 110 | visitInsn(); |
| 111 | } |
| 112 | |
| 113 | @Override |
| 114 | public void visitIntInsn(int opcode, int operand) { |
| 115 | visitInsn(); |
| 116 | } |
| 117 | |
| 118 | @Override |
| 119 | public void visitVarInsn(int opcode, int variable) { |
| 120 | visitInsn(); |
| 121 | } |
| 122 | |
| 123 | @Override |
| 124 | public void visitTypeInsn(int opcode, String type) { |
| 125 | visitInsn(); |
| 126 | } |
| 127 | |
| 128 | @Override |
| 129 | public void visitFieldInsn(int opcode, String owner, String name, String desc) { |
| 130 | visitInsn(); |
| 131 | } |
| 132 | |
| 133 | @Override |
| 134 | public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) { |
| 135 | visitInsn(); |
| 136 | } |
| 137 | |
| 138 | @Override |
| 139 | public void visitInvokeDynamicInsn(String name, String desc, Handle handle, Object... args) { |
| 140 | visitInsn(); |
| 141 | } |
| 142 | |
| 143 | @Override |
| 144 | public void visitLdcInsn(Object cst) { |
| 145 | visitInsn(); |
| 146 | } |
| 147 | |
| 148 | @Override |
| 149 | public void visitIincInsn(int var, int inc) { |
| 150 | visitInsn(); |
| 151 | } |
| 152 | |
| 153 | @Override |
| 154 | public void visitMultiANewArrayInsn(String desc, int dims) { |
| 155 | visitInsn(); |
| 156 | } |
| 157 | |
| 158 | // Methods that need to update the states |
| 159 | @Override |
| 160 | public void visitJumpInsn(int opcode, Label label) { |
| 161 | visitInsn(); |
| 162 | jumps.add(new Jump(lastInstruction, label)); |
| 163 | } |
| 164 | |
| 165 | @Override |
| 166 | public void visitLabel(Label label) { |
| 167 | currentLabels.add(label); |
| 168 | if (!LabelInfo.isSuccessor(label)) { |
| 169 | lastInstruction = null; |
| 170 | } |
| 171 | } |
| 172 | |
| 173 | @Override |
| 174 | public void visitLineNumber(int line, Label start) { |
| 175 | currentLine = line; |
| 176 | } |
| 177 | |
| 178 | /** Visit a switch instruction with no probes */ |
| 179 | private void visitSwitchInsn(Label dflt, Label[] labels) { |
| 180 | visitInsn(); |
| 181 | |
| 182 | // Handle default transition |
| 183 | LabelInfo.resetDone(dflt); |
| 184 | jumps.add(new Jump(lastInstruction, dflt)); |
| 185 | LabelInfo.setDone(dflt); |
| 186 | |
| 187 | // Handle other transitions |
| 188 | LabelInfo.resetDone(labels); |
| 189 | for (Label label : labels) { |
| 190 | if (!LabelInfo.isDone(label)) { |
| 191 | jumps.add(new Jump(lastInstruction, label)); |
| 192 | LabelInfo.setDone(label); |
| 193 | } |
| 194 | } |
| 195 | } |
| 196 | |
| 197 | @Override |
| 198 | public void visitTableSwitchInsn(int min, int max, Label dflt, Label... labels) { |
| 199 | visitSwitchInsn(dflt, labels); |
| 200 | } |
| 201 | |
| 202 | @Override |
| 203 | public void visitLookupSwitchInsn(Label dflt, int[] keys, Label[] labels) { |
| 204 | visitSwitchInsn(dflt, labels); |
| 205 | } |
| 206 | |
| 207 | private void addProbe(int probeId) { |
| 208 | // We do not add probes to the flow graph, but we need to update |
| 209 | // the branch count of the predecessor of the probe |
| 210 | lastInstruction.addBranch(); |
| 211 | probeToInsn.put(probeId, lastInstruction); |
| 212 | } |
| 213 | |
| 214 | // Probe visit methods |
| 215 | @Override |
| 216 | public void visitProbe(int probeId) { |
| 217 | // This function is only called when visiting a merge node which |
| 218 | // is a successor. |
| 219 | // It adds an probe point to the last instruction |
| 220 | assert (lastInstruction != null); |
| 221 | |
| 222 | addProbe(probeId); |
| 223 | lastInstruction = null; // Merge point should have no predecessor. |
| 224 | } |
| 225 | |
| 226 | @Override |
| 227 | public void visitJumpInsnWithProbe(int opcode, Label label, int probeId, IFrame frame) { |
| 228 | visitInsn(); |
| 229 | addProbe(probeId); |
| 230 | } |
| 231 | |
| 232 | @Override |
| 233 | public void visitInsnWithProbe(int opcode, int probeId) { |
| 234 | visitInsn(); |
| 235 | addProbe(probeId); |
| 236 | } |
| 237 | |
| 238 | @Override |
| 239 | public void visitTableSwitchInsnWithProbes( |
| 240 | int min, int max, Label dflt, Label[] labels, IFrame frame) { |
| 241 | visitSwitchInsnWithProbes(dflt, labels); |
| 242 | } |
| 243 | |
| 244 | @Override |
| 245 | public void visitLookupSwitchInsnWithProbes( |
| 246 | Label dflt, int[] keys, Label[] labels, IFrame frame) { |
| 247 | visitSwitchInsnWithProbes(dflt, labels); |
| 248 | } |
| 249 | |
| 250 | private void visitSwitchInsnWithProbes(Label dflt, Label[] labels) { |
| 251 | visitInsn(); |
| 252 | LabelInfo.resetDone(dflt); |
| 253 | LabelInfo.resetDone(labels); |
| 254 | |
| 255 | visitTargetWithProbe(dflt); |
| 256 | for (Label l : labels) { |
| 257 | visitTargetWithProbe(l); |
| 258 | } |
| 259 | } |
| 260 | |
| 261 | private void visitTargetWithProbe(Label label) { |
| 262 | if (!LabelInfo.isDone(label)) { |
| 263 | int id = LabelInfo.getProbeId(label); |
| 264 | if (id == LabelInfo.NO_PROBE) { |
| 265 | jumps.add(new Jump(lastInstruction, label)); |
| 266 | } else { |
| 267 | // Note, in this case the instrumenter should insert intermediate labels |
| 268 | // for the probes. These probes will be added for the switch instruction. |
| 269 | // |
| 270 | // There is no direct jump between lastInstruction and the label either. |
| 271 | addProbe(id); |
| 272 | } |
| 273 | LabelInfo.setDone(label); |
| 274 | } |
| 275 | } |
| 276 | |
| 277 | // If a CovExp of pred is ProbeExp, create a single-branch BranchExp and put it in the map. |
| 278 | // Also update the index of insn. |
| 279 | private BranchExp getPredBranchExp(Instruction predecessor, Instruction insn) { |
| 280 | BranchExp result = null; |
| 281 | CovExp exp = insnToCovExp.get(predecessor); |
| 282 | if (exp instanceof ProbeExp) { |
| 283 | result = new BranchExp(exp); // Change ProbeExp to BranchExp |
| 284 | insnToCovExp.put(predecessor, result); |
| 285 | // This can only happen if the internal data of Jacoco is inconsistent: |
| 286 | // the instruction is the predecessor of more than one instructions, |
| 287 | // but its branch count is not > 1. |
| 288 | } else { |
| 289 | result = (BranchExp) exp; |
| 290 | } |
| 291 | return result; |
| 292 | } |
| 293 | |
| 294 | // Update a branch predecessor and returns whether the BranchExp of the predecessor is new. |
| 295 | private boolean updateBranchPredecessor(Instruction predecessor, Instruction insn, CovExp exp) { |
| 296 | CovExp predExp = insnToCovExp.get(predecessor); |
| 297 | if (predExp == null) { |
| 298 | BranchExp branchExp = new BranchExp(exp); |
| 299 | insnToCovExp.put(predecessor, branchExp); |
| 300 | insnToIdx.put(insn, 0); // current insn is the first branch |
| 301 | return true; |
| 302 | } |
| 303 | |
| 304 | BranchExp branchExp = getPredBranchExp(predecessor, insn); |
| 305 | Integer branchIdx = insnToIdx.get(insn); |
| 306 | if (branchIdx == null) { |
| 307 | // Keep track of the instructions in the branches that are already added |
| 308 | branchIdx = branchExp.add(exp); |
| 309 | insnToIdx.put(insn, branchIdx); |
| 310 | } |
| 311 | // If the branch where the instruction is on is already added, no need to do anything as |
| 312 | // branchExp has a reference to exp already. |
| 313 | return false; |
| 314 | } |
| 315 | |
| 316 | /** Finishing the method */ |
| 317 | @Override |
| 318 | public void visitEnd() { |
| 319 | |
| 320 | for (Jump jump : jumps) { |
| 321 | Instruction insn = labelToInsn.get(jump.target); |
| 322 | insn.setPredecessor(jump.source); |
| 323 | predecessors.put(insn, jump.source); |
| 324 | } |
| 325 | |
| 326 | // Compute CovExp for every instruction. |
| 327 | for (Map.Entry<Integer, Instruction> entry : probeToInsn.entrySet()) { |
| 328 | int probeId = entry.getKey(); |
| 329 | Instruction ins = entry.getValue(); |
| 330 | |
| 331 | Instruction insn = ins; |
| 332 | CovExp exp = new ProbeExp(probeId); |
| 333 | |
| 334 | // Compute CovExp for the probed instruction. |
| 335 | CovExp existingExp = insnToCovExp.get(insn); |
| 336 | if (existingExp != null) { |
| 337 | // The instruction already has a branch, add the probeExp as |
| 338 | // a new branch. |
| 339 | if (existingExp instanceof BranchExp) { |
| 340 | BranchExp branchExp = (BranchExp) existingExp; |
| 341 | branchExp.add(exp); |
| 342 | } else { |
| 343 | // This can only happen if the internal data is inconsistent. |
| 344 | // The instruction is a predecessor of another instruction and also |
| 345 | // has a probe, but the branch count is not > 1. |
| 346 | } |
| 347 | } else { |
| 348 | if (insn.getBranches() > 1) { |
| 349 | exp = new BranchExp(exp); |
| 350 | } |
| 351 | insnToCovExp.put(insn, exp); |
| 352 | } |
| 353 | |
| 354 | Instruction predecessor = predecessors.get(insn); |
| 355 | while (predecessor != null) { |
| 356 | if (predecessor.getBranches() > 1) { |
| 357 | boolean isNewBranch = updateBranchPredecessor(predecessor, insn, exp); |
| 358 | if (!isNewBranch) { |
| 359 | // If the branch already exists, no need to visit predecessors any more. |
| 360 | break; |
| 361 | } |
| 362 | } else { |
| 363 | // No branch at predecessor, use the same CovExp |
| 364 | insnToCovExp.put(predecessor, exp); |
| 365 | } |
| 366 | insn = predecessor; |
| 367 | exp = insnToCovExp.get(predecessor); |
| 368 | predecessor = predecessors.get(insn); |
| 369 | } |
| 370 | } |
| 371 | |
| 372 | // Merge branches in the instructions on the same line |
| 373 | for (Instruction insn : instructions) { |
| 374 | if (insn.getBranches() > 1) { |
| 375 | CovExp insnExp = insnToCovExp.get(insn); |
| 376 | if (insnExp != null && (insnExp instanceof BranchExp)) { |
| 377 | BranchExp exp = (BranchExp) insnExp; |
| 378 | BranchExp lineExp = lineToBranchExp.get(insn.getLine()); |
| 379 | if (lineExp == null) { |
| 380 | lineToBranchExp.put(insn.getLine(), exp); |
| 381 | } else { |
| 382 | lineExp.merge(exp); |
| 383 | } |
| 384 | } else { |
| 385 | // If we reach here, the internal data of the mapping is inconsistent, either |
| 386 | // 1) An instruction has branches but we do not create BranchExp for it. |
| 387 | // 2) An instruction has branches but it does not have an associated CovExp. |
| 388 | } |
| 389 | } |
| 390 | } |
| 391 | } |
| 392 | |
| 393 | /** Jumps between instructions and labels */ |
| 394 | class Jump { |
| 395 | public final Instruction source; |
| 396 | public final Label target; |
| 397 | |
| 398 | public Jump(Instruction i, Label l) { |
| 399 | source = i; |
| 400 | target = l; |
| 401 | } |
| 402 | } |
| 403 | } |