1// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4package com.android.tools.r8.graph;
5
6import com.android.tools.r8.dex.Constants;
7import com.android.tools.r8.graph.DexDebugEvent.StartLocal;
8import com.android.tools.r8.ir.code.Argument;
9import com.android.tools.r8.ir.code.DebugLocalsChange;
10import com.android.tools.r8.ir.code.DebugPosition;
11import com.android.tools.r8.ir.code.Instruction;
12import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
13import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
14import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
15import it.unimi.dsi.fastutil.ints.Int2ReferenceMaps;
16import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
17import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
18import java.util.ArrayList;
19import java.util.List;
20
21/**
22 * Builder for constructing a list of debug events suitable for DexDebugInfo.
23 *
24 * This builder is intended to be very pedantic and ensure a well-formed structure of the resulting
25 * event stream.
26 */
27public class DexDebugEventBuilder {
28
29  private static final int NO_PC_INFO = -1;
30  private static final int NO_LINE_INFO = -1;
31
32  private final DexEncodedMethod method;
33  private final DexItemFactory factory;
34
35  // In order list of non-this argument locals.
36  private ArrayList<DebugLocalInfo> arguments;
37
38  // Mapping from register to the last known local in that register (See DBG_RESTART_LOCAL).
39  private Int2ReferenceMap<DebugLocalInfo> lastKnownLocals;
40
41  // Mapping from register to local for currently open/visible locals.
42  private Int2ReferenceMap<DebugLocalInfo> pendingLocals = null;
43
44  // Conservative pending-state of locals to avoid some equality checks on locals.
45  // pendingLocalChanges == true ==> localsEqual(emittedLocals, pendingLocals).
46  private boolean pendingLocalChanges = false;
47
48  // State of pc, line, file and locals in the emitted event stream.
49  private int emittedPc = NO_PC_INFO;
50  private int emittedLine = NO_LINE_INFO;
51  private DexString emittedFile = null;
52  private Int2ReferenceMap<DebugLocalInfo> emittedLocals;
53
54  // If lastMoveInstructionPc != NO_PC_INFO, then the last pc-advancing instruction was a
55  // move-exception at lastMoveInstructionPc. This is needed to maintain the art/dx specific
56  // behaviour that the move-exception pc is associated with the catch-declaration line.
57  // See debug.ExceptionTest.testStepOnCatch().
58  private int lastMoveInstructionPc = NO_PC_INFO;
59
60  // Emitted events.
61  private final List<DexDebugEvent> events = new ArrayList<>();
62
63  // Initial known line for the method.
64  private int startLine = NO_LINE_INFO;
65
66  public DexDebugEventBuilder(DexEncodedMethod method, DexItemFactory factory) {
67    this.method = method;
68    this.factory = factory;
69  }
70
71  // Public method for the DebugStripper.
72  public void setPosition(int pc, int line) {
73    emitDebugPosition(pc, line, null);
74  }
75
76  /** Add events at pc for instruction. */
77  public void add(int pc, Instruction instruction) {
78    // Initialize locals state on block entry.
79    if (instruction.getBlock().entry() == instruction) {
80      updateBlockEntry(instruction);
81    }
82    assert pendingLocals != null;
83
84    // If this is a position emit and exit as it always emits events.
85    if (instruction.isDebugPosition()) {
86      emitDebugPosition(pc, instruction.asDebugPosition());
87      return;
88    }
89
90    if (instruction.isArgument()) {
91      startArgument(instruction.asArgument());
92    } else if (instruction.isDebugLocalsChange()) {
93      updateLocals(instruction.asDebugLocalsChange());
94    } else if (instruction.getBlock().exit() == instruction) {
95      // If this is the end of the block clear out the pending state and exit.
96      pendingLocals = null;
97      pendingLocalChanges = false;
98      return;
99    } else if (instruction.isMoveException()) {
100      lastMoveInstructionPc = pc;
101    } else {
102      // For non-exit / pc-advancing instructions emit any pending changes.
103      emitLocalChanges(pc);
104    }
105  }
106
107  /** Build the resulting DexDebugInfo object. */
108  public DexDebugInfo build() {
109    assert pendingLocals == null;
110    assert !pendingLocalChanges;
111    if (startLine == NO_LINE_INFO) {
112      return null;
113    }
114    DexString[] params = new DexString[method.method.proto.parameters.values.length];
115    if (arguments != null) {
116      assert params.length == arguments.size();
117      for (int i = 0; i < arguments.size(); i++) {
118        DebugLocalInfo local = arguments.get(i);
119        params[i] = (local == null || local.signature != null) ? null : local.name;
120      }
121    }
122    return new DexDebugInfo(startLine, params, events.toArray(new DexDebugEvent[events.size()]));
123  }
124
125  private void updateBlockEntry(Instruction instruction) {
126    assert pendingLocals == null;
127    assert !pendingLocalChanges;
128    Int2ReferenceMap<DebugLocalInfo> locals = instruction.getBlock().getLocalsAtEntry();
129    if (locals == null) {
130      pendingLocals = Int2ReferenceMaps.emptyMap();
131    } else {
132      pendingLocals = new Int2ReferenceOpenHashMap<>(locals);
133      pendingLocalChanges = true;
134    }
135    if (emittedLocals == null) {
136      initialize(locals);
137    }
138  }
139
140  private void initialize(Int2ReferenceMap<DebugLocalInfo> locals) {
141    assert arguments == null;
142    assert emittedLocals == null;
143    assert lastKnownLocals == null;
144    assert startLine == NO_LINE_INFO;
145    if (locals == null) {
146      emittedLocals = Int2ReferenceMaps.emptyMap();
147      lastKnownLocals = Int2ReferenceMaps.emptyMap();
148      return;
149    }
150    // Implicitly open all unparameterized arguments.
151    emittedLocals = new Int2ReferenceOpenHashMap<>();
152    for (Entry<DebugLocalInfo> entry : locals.int2ReferenceEntrySet()) {
153      if (entry.getValue().signature == null) {
154        emittedLocals.put(entry.getIntKey(), entry.getValue());
155      }
156    }
157    lastKnownLocals = new Int2ReferenceOpenHashMap<>(emittedLocals);
158  }
159
160  private void startArgument(Argument argument) {
161    if (arguments == null) {
162      arguments = new ArrayList<>(method.method.proto.parameters.values.length);
163    }
164    if (!argument.outValue().isThis()) {
165      arguments.add(argument.getLocalInfo());
166    }
167  }
168
169  private void updateLocals(DebugLocalsChange change) {
170    pendingLocalChanges = true;
171    for (Entry<DebugLocalInfo> end : change.getEnding().int2ReferenceEntrySet()) {
172      assert pendingLocals.get(end.getIntKey()) == end.getValue();
173      pendingLocals.remove(end.getIntKey());
174    }
175    for (Entry<DebugLocalInfo> start : change.getStarting().int2ReferenceEntrySet()) {
176      assert !pendingLocals.containsKey(start.getIntKey());
177      pendingLocals.put(start.getIntKey(), start.getValue());
178    }
179  }
180
181  private boolean localsChanged() {
182    if (!pendingLocalChanges) {
183      return false;
184    }
185    pendingLocalChanges = !localsEqual(emittedLocals, pendingLocals);
186    return pendingLocalChanges;
187  }
188
189  private void emitDebugPosition(int pc, DebugPosition position) {
190    emitDebugPosition(pc, position.line, position.file);
191  }
192
193  private void emitDebugPosition(int pc, int line, DexString file) {
194    int emitPc = lastMoveInstructionPc != NO_PC_INFO ? lastMoveInstructionPc : pc;
195    lastMoveInstructionPc = NO_PC_INFO;
196    // The position requires a pc change event and possible events for line, file and local changes.
197    // Verify that we do not ever produce two subsequent positions at the same pc.
198    assert emittedPc != emitPc;
199    if (startLine == NO_LINE_INFO) {
200      assert emittedLine == NO_LINE_INFO;
201      startLine = line;
202      emittedLine = line;
203    }
204    emitAdvancementEvents(emittedPc, emittedLine, emittedFile, emitPc, line, file, events, factory);
205    emittedPc = emitPc;
206    emittedLine = line;
207    emittedFile = file;
208    if (localsChanged()) {
209      emitLocalChangeEvents(emittedLocals, pendingLocals, lastKnownLocals, events, factory);
210      assert localsEqual(emittedLocals, pendingLocals);
211    }
212    pendingLocalChanges = false;
213  }
214
215  private void emitLocalChanges(int pc) {
216    // If pc advanced since the locals changed and locals indeed have changed, emit the changes.
217    if (localsChanged()) {
218      int emitPc = lastMoveInstructionPc != NO_PC_INFO ? lastMoveInstructionPc : pc;
219      lastMoveInstructionPc = NO_PC_INFO;
220      emitAdvancementEvents(
221          emittedPc, emittedLine, emittedFile, emitPc, emittedLine, emittedFile, events, factory);
222      emittedPc = emitPc;
223      emitLocalChangeEvents(emittedLocals, pendingLocals, lastKnownLocals, events, factory);
224      pendingLocalChanges = false;
225      assert localsEqual(emittedLocals, pendingLocals);
226    }
227  }
228
229  private static void emitAdvancementEvents(
230      int previousPc,
231      int previousLine,
232      DexString previousFile,
233      int nextPc,
234      int nextLine,
235      DexString nextFile,
236      List<DexDebugEvent> events,
237      DexItemFactory factory) {
238    int pcDelta = previousPc == NO_PC_INFO ? nextPc : nextPc - previousPc;
239    int lineDelta = nextLine == NO_LINE_INFO ? 0 : nextLine - previousLine;
240    assert pcDelta >= 0;
241    if (nextFile != previousFile) {
242      events.add(factory.createSetFile(nextFile));
243    }
244    if (lineDelta < Constants.DBG_LINE_BASE
245        || lineDelta - Constants.DBG_LINE_BASE >= Constants.DBG_LINE_RANGE) {
246      events.add(factory.createAdvanceLine(lineDelta));
247      // TODO(herhut): To be super clever, encode only the part that is above limit.
248      lineDelta = 0;
249    }
250    if (pcDelta >= Constants.DBG_ADDRESS_RANGE) {
251      events.add(factory.createAdvancePC(pcDelta));
252      pcDelta = 0;
253    }
254    // TODO(herhut): Maybe only write this one if needed (would differ from DEX).
255    int specialOpcode =
256        0x0a + (lineDelta - Constants.DBG_LINE_BASE) + Constants.DBG_LINE_RANGE * pcDelta;
257    assert specialOpcode >= 0x0a;
258    assert specialOpcode <= 0xff;
259    events.add(factory.createDefault(specialOpcode));
260  }
261
262  public static void emitLocalChangeEvents(
263      Int2ReferenceMap<DebugLocalInfo> previousLocals,
264      Int2ReferenceMap<DebugLocalInfo> nextLocals,
265      Int2ReferenceMap<DebugLocalInfo> lastKnownLocals,
266      List<DexDebugEvent> events,
267      DexItemFactory factory) {
268    Int2ReferenceSortedMap<DebugLocalInfo> ending = new Int2ReferenceAVLTreeMap<>();
269    Int2ReferenceSortedMap<DebugLocalInfo> starting = new Int2ReferenceAVLTreeMap<>();
270    for (Entry<DebugLocalInfo> entry : previousLocals.int2ReferenceEntrySet()) {
271      int register = entry.getIntKey();
272      DebugLocalInfo local = entry.getValue();
273      if (nextLocals.get(register) != local) {
274        ending.put(register, local);
275      }
276    }
277    for (Entry<DebugLocalInfo> entry : nextLocals.int2ReferenceEntrySet()) {
278      int register = entry.getIntKey();
279      DebugLocalInfo local = entry.getValue();
280      if (previousLocals.get(register) != local) {
281        starting.put(register, local);
282      }
283    }
284    assert !ending.isEmpty() || !starting.isEmpty();
285    for (Entry<DebugLocalInfo> end : ending.int2ReferenceEntrySet()) {
286      int register = end.getIntKey();
287      if (!starting.containsKey(register)) {
288        previousLocals.remove(register);
289        events.add(factory.createEndLocal(register));
290      }
291    }
292    for (Entry<DebugLocalInfo> start : starting.int2ReferenceEntrySet()) {
293      int register = start.getIntKey();
294      DebugLocalInfo local = start.getValue();
295      previousLocals.put(register, local);
296      if (lastKnownLocals.get(register) == local) {
297        events.add(factory.createRestartLocal(register));
298      } else {
299        events.add(new StartLocal(register, local));
300        lastKnownLocals.put(register, local);
301      }
302    }
303  }
304
305  private static boolean localsEqual(
306      Int2ReferenceMap<DebugLocalInfo> locals1, Int2ReferenceMap<DebugLocalInfo> locals2) {
307    if (locals1 == locals2) {
308      return true;
309    }
310    if (locals1.size() != locals2.size()) {
311      return false;
312    }
313    for (Int2ReferenceMap.Entry<DebugLocalInfo> entry : locals1.int2ReferenceEntrySet()) {
314      if (locals2.get(entry.getIntKey()) != entry.getValue()) {
315        return false;
316      }
317    }
318    return true;
319  }
320}
321