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

[Orlando]

Summary

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.

[jmorse]

To my mind, the two attribute names, _conditional_bp_ranges and _conditional_bps are quite similar -- but AFAICT the former is a on-initialization record of where conditional bps should be placed, while the latter is a "live" record of conditional bp handles, is that right? IMO, better to have an indication of this distinction in the name, may I suggest _conditional_bp_handles?

Otherwise LGTM

[Orlando]

In D98699#2634449, @jmorse wrote:

To my mind, the two attribute names, _conditional_bp_ranges and _conditional_bps are quite similar -- but AFAICT the former is a on-initialization record of where conditional bps should be placed, while the latter is a "live" record of conditional bp handles, is that right? IMO, better to have an indication of this distinction in the name, may I suggest _conditional_bp_handles?

Yeah that's right, and I agree. Done! Thanks for taking a look.

[chrisjackson]

One small suggestion, otherwise LGTM.

debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py

99

_pause_between_steps seems odd. Maybe 'time_between_steps_ms' is more decriptive. I realise that variable wasn't introduced in this patch

[Orlando]

debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py

99

I agree that the name could be better. It looks like the name is used elsewhere too though. In ConditionalController.__init__ we have
self._pause_between_steps = context.options.pause_between_steps. I think it makes sense to keep the name the same as other uses, and I'm not sure updating the name elsewhere should be in the scope of this patch. So I don't think it's worth changing here. Wdyt?

[TWeaver]

Hey Orlando! thanks for this. A really nice, solid reimplementation and improvement of the original work. Great code comments too.

thanks again, LGTM.

[Orlando]

In D98699#2644229, @TWeaver wrote:

Hey Orlando! thanks for this. A really nice, solid reimplementation and improvement of the original work. Great code comments too.

thanks again, LGTM.

Thanks @TWeaver! And thank you everyone for the reviews.

debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py

99

I landed this just now, and in coming back to comment realise that we didn't resolve our conversation @chrisjackson, sorry! Happy to follow up with a quick patch to address this if you still think it should be changed?

debuginfo-tests/dexter/dex/debugger/DebuggerBase.py

class DebuggerBase(object, metaclass=abc.ABCMeta):
     def version(self):
         pass
 
     @abc.abstractmethod
     def clear_breakpoints(self):
         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
     def launch(self):
         pass
 
     @abc.abstractmethod
     def step(self):

debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py

def get_conditional_expression_list(self):
             conditional_list.append(conditional_expression)
         return conditional_list
 
 
 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:
                 conditional_bp = ConditionalBpRange(
                   lc.expression,
                   lc.path,
                   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():
             valueIR = self.debugger.evaluate_expression(cond_expr)
             if valueIR.type_name == 'bool' and valueIR.value == 'true':
                 return True
         return False
 
     def _run_debugger_custom(self):
         # TODO: Add conditional and unconditional breakpoint support to dbgeng.
         if self.debugger.get_name() == 'dbgeng':
             raise DebuggerException('DexLimitSteps commands are not supported by dbgeng')
 
         self.step_collection.clear_steps()
         self._set_conditional_bps()
 
         for command_obj in chain.from_iterable(self.step_collection.commands.values()):
             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
 
             step_info = self.debugger.get_step_info(self._watches, self._step_index)
             if step_info.current_frame:
                 self._step_index += 1
                 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:
-
-                    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='')
+            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.
+                    # 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.
+                        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)
 
-            # 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)

debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py

def _add_breakpoint(self, file_, line):
         # TODO: this method is called in the DefaultController but has no effect.
         pass
 
     def _add_conditional_breakpoint(self, file_, line, condition):
         # breakpoint setting/deleting is not supported by dbgeng at this moment
         # 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')
 
     def launch(self):
         # We are, by this point, already launched.
         self.step_info = probe_process.probe_state(self.client)
 

debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py

def version(self):
             return self._interface.SBDebugger_GetVersionString()
         except AttributeError:
             return None
 
     def clear_breakpoints(self):
         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)
         if bp:
             bp.SetCondition(condition)
         else:
             raise DebuggerException(
                   'could not add breakpoint [{}:{}]'.format(file_, line))
+        return bp.GetID()
 
-    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
+    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
 
     def launch(self):
         self._process = self._target.LaunchSimple(None, None, os.getcwd())
         if not self._process or self._process.GetNumThreads() == 0:
             raise DebuggerException('could not launch process')
         if self._process.GetNumThreads() != 1:
             raise DebuggerException('multiple threads not supported')
         self._thread = self._process.GetThreadAtIndex(0)

debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py

 # DExTer : Debugging Experience Tester
 # ~~~~~~   ~         ~~         ~   ~~
 #
 # Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 # See https://llvm.org/LICENSE.txt for license information.
 # SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 """Interface for communicating with the Visual Studio debugger via DTE."""
 
 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
 from dex.dextIR import StackFrame, SourceLocation, ProgramState
 from dex.utils.Exceptions import Error, LoadDebuggerException
 from dex.utils.ReturnCode import ReturnCode
 
 
 def _load_com_module():
     try:
         module_info = imp.find_module(
             'ComInterface',
             [os.path.join(os.path.dirname(__file__), 'windows')])
         return imp.load_module('ComInterface', *module_info)
     except ImportError as e:
         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
     # (https://msdn.microsoft.com/en-us/library/envdte.debugger.currentmode.aspx)
     dbgDesignMode = 1
     dbgBreakMode = 2
     dbgRunMode = 3
 
     def __init__(self, *args):
         self.com_module = None
         self._debugger = None
         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):
         try:
             self._debugger = self._interface.Debugger
             self._debugger.HexDisplayMode = False
 
             self._interface.MainWindow.Visible = (
def version(self):
         try:
             return self._interface.Version
         except AttributeError:
             return None
 
     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:
 
     def launch(self):
         self._fn_go()
 
     def step(self):
         self._fn_step()
 
     def go(self) -> ReturnCode:

debuginfo-tests/dexter/feature_tests/commands/perfect/limit_steps/limit_steps_line_mismatch.cpp

+// 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')