[dexter] Fix DexLimitSteps when breakpoint can't be set at requested location

Using a DexLimitSteps command forces dexter to use the ConditionalController
debugger controller. At each breakpoint the ConditionalController needs to
understand which one has been hit. Prior to this patch, upon hitting a
breakpoint, dexter used the current source location to look up which requested
breakpoint had been hit.

A breakpoint may not get set at the exact location that the user (dexter)
requests. For example, if the requested breakpoint location doesn't exist
in the line table then then debuggers will (usually, AFAICT) set the breakpoint
at the next available valid breakpoint location.

This meant that, occasionally in unoptimised programs and frequently in
optimised programs, the ConditionalController was failing to determine which
breakpoint had been hit.

This is the fix:

Change the DebuggerBase breakpoint interface to use opaque breakpoint ids
instead of using source location to identify breakpoints, and update the
ConditionalController to track breakpoints instead of locations.

These now return a breakpoint id:

    add_breakpoint(self, file_, line)
    _add_breakpoint(self, file_, line)
    add_conditional_breakpoint(self, file_, line, condition)
    _add_conditional_breakpoint(self, file_, line, condition)

Replace:

    delete_conditional_breakpoint(self, file_, line, condition)
    _delete_conditional_breakpoint(self, file_, line, condition)

with:

    delete_breakpoint(self, id)

Add:

    get_triggered_breakpoint_ids(self)

A breakpoint id is guaranteed to be unique for each requested breakpoint, even
for duplicate breakpoint requests. Identifying breakpoints like this, instead
of by location, removes the possibility of mixing up requested and bound
breakpoints.

This closely matches the LLDB debugger interface so little work was required in
LLDB.py, but some extra bookkeeping is required in VisualStudio.py to maintain
the new breakpoint id semantics. No implementation work has been done in
dbgeng.py as DexLimitSteps doesn't seem to support dbgeng at the moment.

Testing
Added:
dexter/feature_tests/commands/perfect/limit_steps/limit_steps_line_mismatch.cpp

There were no unexpected failures running the full debuginfo-tests suite.

The regression tests use dbgeng on windows by default, and as mentioned above
dbgeng isn't supported yet, so I have also manually tested (i.e. without lit)
that this specific test works as expected with clang and Visual Studio 2017 on
Windows.

Reviewed By: TWeaver

Differential Revision: https://reviews.llvm.org/D98699

6 files changed, 211 insertions, 77 deletions

diff --git a/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py b/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py
index 37aaffe..5b97974 100644
--- a/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py
+++ b/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py
@@ -125,26 +125,46 @@ class DebuggerBase(object, metaclass=abc.ABCMeta):
         pass
 
     def add_breakpoint(self, file_, line):
+        """Returns a unique opaque breakpoint id.
+
+        The ID type depends on the debugger being used, but will probably be
+        an int.
+        """
         return self._add_breakpoint(self._external_to_debug_path(file_), line)
 
     @abc.abstractmethod
     def _add_breakpoint(self, file_, line):
+        """Returns a unique opaque breakpoint id.
+        """
         pass
 
     def add_conditional_breakpoint(self, file_, line, condition):
+        """Returns a unique opaque breakpoint id.
+
+        The ID type depends on the debugger being used, but will probably be
+        an int.
+        """
         return self._add_conditional_breakpoint(
             self._external_to_debug_path(file_), line, condition)
 
     @abc.abstractmethod
     def _add_conditional_breakpoint(self, file_, line, condition):
+        """Returns a unique opaque breakpoint id.
+        """
         pass
 
-    def delete_conditional_breakpoint(self, file_, line, condition):
-        return self._delete_conditional_breakpoint(
-            self._external_to_debug_path(file_), line, condition)
+    @abc.abstractmethod
+    def delete_breakpoint(self, id):
+        """Delete a breakpoint by id.
+
+        Raises a KeyError if no breakpoint with this id exists.
+        """
+        pass
 
     @abc.abstractmethod
-    def _delete_conditional_breakpoint(self, file_, line, condition):
+    def get_triggered_breakpoint_ids(self):
+        """Returns a set of opaque ids for just-triggered breakpoints.
+        """
         pass
 
     @abc.abstractmethod
diff --git a/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py b/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py
index 4e4327b..e225a48 100644
--- a/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py
+++ b/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py
@@ -42,17 +42,18 @@ class ConditionalController(DebuggerControllerBase):
     def __init__(self, context, step_collection):
       self.context = context
       self.step_collection = step_collection
-      self._conditional_bps = None
+      self._conditional_bp_ranges = None
+      self._build_conditional_bp_ranges()
       self._watches = set()
       self._step_index = 0
-      self._build_conditional_bps()
-      self._path_and_line_to_conditional_bp = defaultdict(list)
       self._pause_between_steps = context.options.pause_between_steps
       self._max_steps = context.options.max_steps
+      # Map {id: ConditionalBpRange}
+      self._conditional_bp_handles = {}
 
-    def _build_conditional_bps(self):
+    def _build_conditional_bp_ranges(self):
         commands = self.step_collection.commands
-        self._conditional_bps = []
+        self._conditional_bp_ranges = []
         try:
             limit_commands = commands['DexLimitSteps']
             for lc in limit_commands:
@@ -62,22 +63,19 @@ class ConditionalController(DebuggerControllerBase):
                   lc.from_line,
                   lc.to_line,
                   lc.values)
-                self._conditional_bps.append(conditional_bp)
+                self._conditional_bp_ranges.append(conditional_bp)
         except KeyError:
             raise DebuggerException('Missing DexLimitSteps commands, cannot conditionally step.')
 
     def _set_conditional_bps(self):
-        # When we break in the debugger we need a quick and easy way to look up
-        # which conditional bp we've breaked on.
-        for cbp in self._conditional_bps:
-            conditional_bp_list = self._path_and_line_to_conditional_bp[(cbp.path, cbp.range_from)]
-            conditional_bp_list.append(cbp)
-
-        # Set break points only on the first line of any conditional range, we'll set
-        # more break points for a range when the condition is satisfied.
-        for cbp in self._conditional_bps:
+        # Set a conditional breakpoint for each ConditionalBpRange and build a
+        # map of {id: ConditionalBpRange}.
+        for cbp in self._conditional_bp_ranges:
             for cond_expr in cbp.get_conditional_expression_list():
-                self.debugger.add_conditional_breakpoint(cbp.path, cbp.range_from, cond_expr)
+                id = self.debugger.add_conditional_breakpoint(cbp.path,
+                                                              cbp.range_from,
+                                                              cond_expr)
+                self._conditional_bp_handles[id] = cbp
 
     def _conditional_met(self, cbp):
         for cond_expr in cbp.get_conditional_expression_list():
@@ -98,7 +96,7 @@ class ConditionalController(DebuggerControllerBase):
             self._watches.update(command_obj.get_watches())
 
         self.debugger.launch()
-        time.sleep(self._pause_between_steps) 
+        time.sleep(self._pause_between_steps)
         while not self.debugger.is_finished:
             while self.debugger.is_running:
                 pass
@@ -109,19 +107,28 @@ class ConditionalController(DebuggerControllerBase):
                 update_step_watches(step_info, self._watches, self.step_collection.commands)
                 self.step_collection.new_step(self.context, step_info)
 
-                loc = step_info.current_location
-                conditional_bp_key = (loc.path, loc.lineno)
-                if conditional_bp_key in self._path_and_line_to_conditional_bp:
+            bp_to_delete = []
+            for bp_id in self.debugger.get_triggered_breakpoint_ids():
+                try:
+                    # See if this is one of our conditional breakpoints.
+                    cbp = self._conditional_bp_handles[bp_id]
+                except KeyError:
+                    # This is an unconditional bp. Mark it for removal.
+                    bp_to_delete.append(bp_id)
+                    continue
+                # We have triggered a breakpoint with a condition. Check that
+                # the condition has been met.
+                if self._conditional_met(cbp):
+                    # Add a range of unconditional breakpoints covering the
+                    # lines requested in the DexLimitSteps command. Ignore
+                    # first line as that's the conditional bp we just hit and
+                    # include the final line.
+                    for line in range(cbp.range_from + 1, cbp.range_to + 1):
+                        self.debugger.add_breakpoint(cbp.path, line)
+
+            # Remove any unconditional breakpoints we just hit.
+            for bp_id in bp_to_delete:
+                self.debugger.delete_breakpoint(bp_id)
 
-                    conditional_bps = self._path_and_line_to_conditional_bp[conditional_bp_key]
-                    for cbp in conditional_bps:
-                        if self._conditional_met(cbp):
-                            # Unconditional range should ignore first line as that's the
-                            # conditional bp we just hit and should be inclusive of final line
-                            for line in range(cbp.range_from + 1, cbp.range_to + 1):
-                                self.debugger.add_conditional_breakpoint(cbp.path, line, condition='')
-
-            # Clear any uncondtional break points at this loc.
-            self.debugger.delete_conditional_breakpoint(file_=loc.path, line=loc.lineno, condition='')
             self.debugger.go()
             time.sleep(self._pause_between_steps)
diff --git a/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py b/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py
index 5105b4a..c95aa54 100644
--- a/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py
+++ b/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py
@@ -87,7 +87,10 @@ class DbgEng(DebuggerBase):
         # but is something that should be considered in the future.
         raise NotImplementedError('add_conditional_breakpoint is not yet implemented by dbgeng')
 
-    def _delete_conditional_breakpoint(self, file_, line, condition):
+    def get_triggered_breakpoint_ids(self):
+      raise NotImplementedError('get_triggered_breakpoint_ids is not yet implemented by dbgeng')
+
+    def delete_breakpoint(self, id):
         # breakpoint setting/deleting is not supported by dbgeng at this moment
         # but is something that should be considered in the future.
         raise NotImplementedError('delete_conditional_breakpoint is not yet implemented by dbgeng')
diff --git a/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py b/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py
index 5fc8fd3..324467d 100644
--- a/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py
+++ b/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py
@@ -104,9 +104,11 @@ class LLDB(DebuggerBase):
         self._target.DeleteAllBreakpoints()
 
     def _add_breakpoint(self, file_, line):
-        if not self._target.BreakpointCreateByLocation(file_, line):
+        bp = self._target.BreakpointCreateByLocation(file_, line)
+        if not bp:
             raise DebuggerException(
                 'could not add breakpoint [{}:{}]'.format(file_, line))
+        return bp.GetID()
 
     def _add_conditional_breakpoint(self, file_, line, condition):
         bp = self._target.BreakpointCreateByLocation(file_, line)
@@ -115,37 +117,24 @@ class LLDB(DebuggerBase):
         else:
             raise DebuggerException(
                   'could not add breakpoint [{}:{}]'.format(file_, line))
-
-    def _delete_conditional_breakpoint(self, file_, line, condition):
-        bp_count = self._target.GetNumBreakpoints()
-        bps = [self._target.GetBreakpointAtIndex(ix) for ix in range(0, bp_count)]
-
-        for bp in bps:
-            bp_cond = bp.GetCondition()
-            bp_cond = bp_cond if bp_cond is not None else ''
-
-            if bp_cond != condition:
-                continue
-
-            # If one of the bound bp locations for this bp is bound to the same
-            # line in file_ above, then delete the entire parent bp and all
-            # bp locs.
-            # https://lldb.llvm.org/python_reference/lldb.SBBreakpoint-class.html
-            for breakpoint_location in bp:
-                sb_address = breakpoint_location.GetAddress()
-
-                sb_line_entry = sb_address.GetLineEntry()
-                bl_line = sb_line_entry.GetLine()
-
-                sb_file_entry = sb_line_entry.GetFileSpec()
-                bl_dir = sb_file_entry.GetDirectory()
-                bl_file_name = sb_file_entry.GetFilename()
-
-                bl_file_path = os.path.join(bl_dir, bl_file_name)
-
-                if bl_file_path == file_ and bl_line == line:
-                    self._target.BreakpointDelete(bp.GetID())
-                    break
+        return bp.GetID()
+
+    def get_triggered_breakpoint_ids(self):
+        # Breakpoints can only have been triggered if we've hit one.
+        stop_reason = self._translate_stop_reason(self._thread.GetStopReason())
+        if stop_reason != StopReason.BREAKPOINT:
+            return []
+        # Breakpoints have two data parts: Breakpoint ID, Location ID. We're
+        # only interested in the Breakpoint ID so we skip every other item.
+        return set([self._thread.GetStopReasonDataAtIndex(i)
+                    for i in range(0, self._thread.GetStopReasonDataCount(), 2)])
+
+    def delete_breakpoint(self, id):
+        bp = self._target.FindBreakpointByID(id)
+        if not bp:
+            # The ID is not valid.
+            raise KeyError
+        self._target.BreakpointDelete(bp.GetID())
 
     def launch(self):
         self._process = self._target.LaunchSimple(None, None, os.getcwd())
diff --git a/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py b/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py
index 6585a49..b4558e2 100644
--- a/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py
+++ b/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py
@@ -10,6 +10,9 @@ import abc
 import imp
 import os
 import sys
+from pathlib import PurePath
+from collections import namedtuple
+from collections import defaultdict
 
 from dex.debugger.DebuggerBase import DebuggerBase
 from dex.dextIR import FrameIR, LocIR, StepIR, StopReason, ValueIR
@@ -28,6 +31,11 @@ def _load_com_module():
         raise LoadDebuggerException(e, sys.exc_info())
 
 
+# VSBreakpoint(path: PurePath, line: int, col: int, cond: str).  This is enough
+# info to identify breakpoint equivalence in visual studio based on the
+# properties we set through dexter currently.
+VSBreakpoint = namedtuple('VSBreakpoint', 'path, line, col, cond')
+
 class VisualStudio(DebuggerBase, metaclass=abc.ABCMeta):  # pylint: disable=abstract-method
 
     # Constants for results of Debugger.CurrentMode
@@ -42,6 +50,21 @@ class VisualStudio(DebuggerBase, metaclass=abc.ABCMeta):  # pylint: disable=abst
         self._solution = None
         self._fn_step = None
         self._fn_go = None
+        # The next available unique breakpoint id. Use self._get_next_id().
+        self._next_bp_id = 0
+        # VisualStudio appears to common identical breakpoints. That is, if you
+        # ask for a breakpoint that already exists the Breakpoints list will
+        # not grow. DebuggerBase requires all breakpoints have a unique id,
+        # even for duplicates, so we'll need to do some bookkeeping.  Map
+        # {VSBreakpoint: list(id)} where id is the unique dexter-side id for
+        # the requested breakpoint.
+        self._vs_to_dex_ids = defaultdict(list)
+        # Map {id: VSBreakpoint} where id is unique and VSBreakpoint identifies
+        # a breakpoint in Visual Studio. There may be many ids mapped to a
+        # single VSBreakpoint. Use self._vs_to_dex_ids to find (dexter)
+        # breakpoints mapped to the same visual studio breakpoint.
+        self._dex_id_to_vs = {}
+
         super(VisualStudio, self).__init__(*args)
 
     def _custom_init(self):
@@ -110,21 +133,88 @@ class VisualStudio(DebuggerBase, metaclass=abc.ABCMeta):  # pylint: disable=abst
     def clear_breakpoints(self):
         for bp in self._debugger.Breakpoints:
             bp.Delete()
+        self._vs_to_dex_ids.clear()
+        self._dex_id_to_vs.clear()
 
     def _add_breakpoint(self, file_, line):
-        self._debugger.Breakpoints.Add('', file_, line)
+        return self._add_conditional_breakpoint(file_, line, '')
 
-    def _add_conditional_breakpoint(self, file_, line, condition):
-        column = 1
-        self._debugger.Breakpoints.Add('', file_, line, column, condition)
+    def _get_next_id(self):
+        # "Generate" a new unique id for the breakpoint.
+        id = self._next_bp_id
+        self._next_bp_id += 1
+        return id
 
-    def _delete_conditional_breakpoint(self, file_, line, condition):
+    def _add_conditional_breakpoint(self, file_, line, condition):
+        col = 1
+        vsbp = VSBreakpoint(PurePath(file_), line, col, condition)
+        new_id = self._get_next_id()
+
+        # Do we have an exact matching breakpoint already?
+        if vsbp in self._vs_to_dex_ids:
+            self._vs_to_dex_ids[vsbp].append(new_id)
+            self._dex_id_to_vs[new_id] = vsbp
+            return new_id
+
+        # Breakpoint doesn't exist already. Add it now.
+        count_before = self._debugger.Breakpoints.Count
+        self._debugger.Breakpoints.Add('', file_, line, col, condition)
+        # Our internal representation of VS says that the breakpoint doesn't
+        # already exist so we do not expect this operation to fail here.
+        assert count_before < self._debugger.Breakpoints.Count
+        # We've added a new breakpoint, record its id.
+        self._vs_to_dex_ids[vsbp].append(new_id)
+        self._dex_id_to_vs[new_id] = vsbp
+        return new_id
+
+    def get_triggered_breakpoint_ids(self):
+        """Returns a set of opaque ids for just-triggered breakpoints.
+        """
+        bps_hit = self._debugger.AllBreakpointsLastHit
+        bp_id_list = []
+        # Intuitively, AllBreakpointsLastHit breakpoints are the last hit
+        # _bound_ breakpoints. A bound breakpoint's parent holds the info of
+        # the breakpoint the user requested. Our internal state tracks the user
+        # requested breakpoints so we look at the Parent of these triggered
+        # breakpoints to determine which have been hit.
+        for bp in bps_hit:
+            # All bound breakpoints should have the user-defined breakpoint as
+            # a parent.
+            assert bp.Parent
+            vsbp = VSBreakpoint(PurePath(bp.Parent.File), bp.Parent.FileLine,
+                                bp.Parent.FileColumn, bp.Parent.Condition)
+            try:
+                ids = self._vs_to_dex_ids[vsbp]
+            except KeyError:
+                pass
+            else:
+                bp_id_list += ids
+        return set(bp_id_list)
+
+    def delete_breakpoint(self, id):
+        """Delete a breakpoint by id.
+
+        Raises a KeyError if no breakpoint with this id exists.
+        """
+        vsbp = self._dex_id_to_vs[id]
+
+        # Remove our id from the associated list of dex ids.
+        self._vs_to_dex_ids[vsbp].remove(id)
+        del self._dex_id_to_vs[id]
+
+        # Bail if there are other uses of this vsbp.
+        if len(self._vs_to_dex_ids[vsbp]) > 0:
+            return
+        # Otherwise find and delete it.
         for bp in self._debugger.Breakpoints:
-            for bound_bp in bp.Children:
-                if (bound_bp.File == file_ and bound_bp.FileLine == line and
-                    bound_bp.Condition == condition):
-                    bp.Delete()
-                    break
+            # We're looking at the user-set breakpoints so there shouild be no
+            # Parent.
+            assert bp.Parent == None
+            this_vsbp = VSBreakpoint(PurePath(bp.File), bp.FileLine,
+                                     bp.FileColumn, bp.Condition)
+            if vsbp == this_vsbp:
+                bp.Delete()
+                break
 
     def launch(self):
         self._fn_go()
diff --git a/debuginfo-tests/dexter/feature_tests/commands/perfect/limit_steps/limit_steps_line_mismatch.cpp b/debuginfo-tests/dexter/feature_tests/commands/perfect/limit_steps/limit_steps_line_mismatch.cpp
new file mode 100644
index 0000000..68ae476
--- /dev/null
+++ b/debuginfo-tests/dexter/feature_tests/commands/perfect/limit_steps/limit_steps_line_mismatch.cpp
@@ -0,0 +1,25 @@
+// Purpose:
+//      Check that \DexLimitSteps works even if the opening breakpoint line
+//      doesn't exist. This can happen due to optimisations or label is on an
+//      empty line.
+//
+// FIXME: Windows regression tests run with dbgeng. \DexLimitSteps isn't yet
+// supported with dbgeng.
+//
+// REQUIRES: system-linux
+//
+// RUN: %dexter_regression_test -- %s | FileCheck %s
+// CHECK: limit_steps_line_mismatch.cpp
+
+int main() {
+  int i = 0;
+  for (; i < 2; i++) {
+    // DexLabel('from')
+    int x = i;
+  }
+  int ret = 0;
+  return ret; // DexLabel('to')
+}
+
+// DexLimitSteps('1', '1', from_line='from', to_line='to')
+// DexExpectWatchValue('i', 0, 1, 2, from_line='from', to_line='to')