[Dexter] Optimize breakpoint deletion in Visual Studio

[StephenTozer]

Summary

Breakpoint deletion in visual studio is currently implemented by iterating over the Dexter-assigned IDs of the breakpoints we want to delete, for each of which we iterate over the complete set of breakpoints in the debugger instance until we find the one we wish to delete. Ideally we would resolve this by directly deleting each breakpoint by some ID rather than searching through the full breakpoint list for them, but in the absence of such a feature in VS we can instead invert the loop to improve performance.

This patch changes breakpoint deletion to iterate over the complete list of breakpoints, deleting breakpoints that match the breakpoints we expect to delete by checking set membership. This represents a worst-case improvement from O(nm) to O(n), for 'm' breakpoints being deleted out of 'n' total. In practise this is almost exactly 'm'-times faster, as when we delete multiple breakpoints they are typically adjacent in the full breakpoint list.

[Orlando]

LGTM

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

class DebuggerBase(object, metaclass=abc.ABCMeta):
 
     @abc.abstractmethod
     def _add_conditional_breakpoint(self, file_, line, condition):
         """Returns a unique opaque breakpoint id.
         """
         pass
 
     @abc.abstractmethod
-    def delete_breakpoint(self, id):
-        """Delete a breakpoint by id.
+    def delete_breakpoints(self, ids):
+        """Delete a set of breakpoints by ids.
 
-        Raises a KeyError if no breakpoint with this id exists.
+        Raises a KeyError if, for any id, no breakpoint with that id exists.
         """
         pass
 
     @abc.abstractmethod
     def get_triggered_breakpoint_ids(self):
         """Returns a set of opaque ids for just-triggered breakpoints.
         """
         pass

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

def _run_debugger_custom(self, cmdline):
                 # Add a range of trailing breakpoints covering the lines
                 # requested in the DexLimitSteps command. Ignore first line as
                 # that's covered by the leading bp we just hit and include the
                 # final line.
                 for line in range(bpr.range_from + 1, bpr.range_to + 1):
                     self.debugger.add_breakpoint(bpr.path, line)
 
             # Remove any trailing or expired leading breakpoints we just hit.
-            for bp_id in bp_to_delete:
-                self.debugger.delete_breakpoint(bp_id)
+            self.debugger.delete_breakpoints(bp_to_delete)
 
             if exit_desired:
                 break
             self.debugger.go()
             time.sleep(self._pause_between_steps)

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

class DbgEng(DebuggerBase):
     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 get_triggered_breakpoint_ids(self):
       raise NotImplementedError('get_triggered_breakpoint_ids is not yet implemented by dbgeng')
 
-    def delete_breakpoint(self, id):
+    def delete_breakpoints(self, ids):
         # 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, cmdline):
         assert len(cmdline) == 0, "Command lines unimplemented for dbgeng right now"
         # We are, by this point, already launched.
         self.step_info = probe_process.probe_state(self.client)

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

def get_triggered_breakpoint_ids(self):
         # Breakpoints have two data parts: Breakpoint ID, Location ID. We're
         # only interested in the Breakpoint ID so we skip every other item.
         for i in range(0, self._thread.GetStopReasonDataCount(), 2):
             id = self._thread.GetStopReasonDataAtIndex(i)
             if self._evaulate_breakpoint_condition(id):
                 breakpoint_ids.add(id)
         return breakpoint_ids
 
-    def delete_breakpoint(self, id):
+    def delete_breakpoints(self, ids):
+        for id in ids:
             bp = self._target.FindBreakpointByID(id)
             if not bp:
                 # The ID is not valid.
                 raise KeyError
             try:
                 del self._breakpoint_conditions[id]
             except KeyError:
                 # This must be an unconditional breakpoint.
                 pass
             self._target.BreakpointDelete(id)
 
     def launch(self, cmdline):
         self._process = self._target.LaunchSimple(cmdline, 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)

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

def get_triggered_breakpoint_ids(self):
             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.
+    def delete_breakpoints(self, ids):
+        """Delete breakpoints by their ids.
 
         Raises a KeyError if no breakpoint with this id exists.
         """
+        vsbp_set = set()
+        for id in ids:
             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
+                continue
             # Otherwise find and delete it.
+            vsbp_set.add(vsbp)
+
+        vsbp_to_del_count = len(vsbp_set)
+
         for bp in self._debugger.Breakpoints:
-            # We're looking at the user-set breakpoints so there shouild be no
+            # We're looking at the user-set breakpoints so there should be no
             # Parent.
             assert bp.Parent == None
             this_vsbp = VSBreakpoint(PurePath(bp.File), bp.FileLine,
                                      bp.FileColumn, bp.Condition)
-            if vsbp == this_vsbp:
+            if this_vsbp in vsbp_set:
                 bp.Delete()
+                vsbp_to_del_count -= 1
+                if vsbp_to_del_count == 0:
                     break
+        if vsbp_to_del_count:
+            raise KeyError('did not find breakpoint to be deleted')
 
     def _fetch_property(self, props, name):
         num_props = props.Count
         result = None
         for x in range(1, num_props+1):
             item = props.Item(x)
             if item.Name == name:
                 return item