blob: 6900a37f71e416bca66f86dee27739d305f3e0b5 [file] [log] [blame]
Yue Ganaf3c4122016-12-05 14:36:02 +00001// 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
15package com.google.testing.coverage;
16
17import java.util.ArrayList;
18import java.util.HashMap;
19import java.util.List;
20import java.util.Map;
21import java.util.TreeMap;
22import org.jacoco.core.internal.flow.IFrame;
23import org.jacoco.core.internal.flow.Instruction;
24import org.jacoco.core.internal.flow.LabelInfo;
25import org.jacoco.core.internal.flow.MethodProbesVisitor;
26import org.objectweb.asm.Handle;
27import 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 */
34public 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}