Refactor BreakpointResolver::SetSCMatchesByLine() to make it easier to

read/understand/maintain.

As a side-effect, this should also improve the performance by avoiding
costly vector element removals and switching from a std::map to a
SmallDenseSet.

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

git-svn-id: https://llvm.org/svn/llvm-project/lldb/trunk@340994 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 101 insertions, 115 deletions

diff --git a/include/lldb/Breakpoint/BreakpointResolver.h b/include/lldb/Breakpoint/BreakpointResolver.h
index 944741308..08326c380 100644
--- a/include/lldb/Breakpoint/BreakpointResolver.h
+++ b/include/lldb/Breakpoint/BreakpointResolver.h
@@ -237,6 +237,10 @@ protected:
                             // breakpoints we set.
 
 private:
+  /// Helper for \p SetSCMatchesByLine.
+  void AddLocation(SearchFilter &filter, const SymbolContext &sc,
+                   bool skip_prologue, llvm::StringRef log_ident);
+
   // Subclass identifier (for llvm isa/dyn_cast)
   const unsigned char SubclassID;
   DISALLOW_COPY_AND_ASSIGN(BreakpointResolver);
diff --git a/source/Breakpoint/BreakpointResolver.cpp b/source/Breakpoint/BreakpointResolver.cpp
index 6ab578dd8..a8a3c820d 100644
--- a/source/Breakpoint/BreakpointResolver.cpp
+++ b/source/Breakpoint/BreakpointResolver.cpp
@@ -180,129 +180,110 @@ void BreakpointResolver::SetSCMatchesByLine(SearchFilter &filter,
                                             SymbolContextList &sc_list,
                                             bool skip_prologue,
                                             llvm::StringRef log_ident) {
-  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_BREAKPOINTS));
-
-  while (sc_list.GetSize() > 0) {
-    SymbolContextList tmp_sc_list;
-    unsigned current_idx = 0;
-    SymbolContext sc;
-    bool first_entry = true;
-
-    FileSpec match_file_spec;
-    FileSpec match_original_file_spec;
-    uint32_t closest_line_number = UINT32_MAX;
-
-    // Pull out the first entry, and all the others that match its file spec,
-    // and stuff them in the tmp list.
-    while (current_idx < sc_list.GetSize()) {
-      bool matches;
-
-      sc_list.GetContextAtIndex(current_idx, sc);
-      if (first_entry) {
-        match_file_spec = sc.line_entry.file;
-        match_original_file_spec = sc.line_entry.original_file;
-        matches = true;
-        first_entry = false;
-      } else
-        matches = ((sc.line_entry.file == match_file_spec) ||
-                   (sc.line_entry.original_file == match_original_file_spec));
-
-      if (matches) {
-        tmp_sc_list.Append(sc);
-        sc_list.RemoveContextAtIndex(current_idx);
-
-        // ResolveSymbolContext will always return a number that is >= the line
-        // number you pass in. So the smaller line number is always better.
-        if (sc.line_entry.line < closest_line_number)
-          closest_line_number = sc.line_entry.line;
-      } else
-        current_idx++;
+  llvm::SmallVector<SymbolContext, 16> all_scs;
+  for (uint32_t i = 0; i < sc_list.GetSize(); ++i)
+    all_scs.push_back(sc_list[i]);
+
+  while (all_scs.size()) {
+    // ResolveSymbolContext will always return a number that is >= the
+    // line number you pass in. So the smaller line number is always
+    // better.
+    uint32_t closest_line = UINT32_MAX;
+
+    // Move all the elements with a matching file spec to the end.
+    auto &match = all_scs[0];
+    auto worklist_begin = std::partition(
+        all_scs.begin(), all_scs.end(), [&](const SymbolContext &sc) {
+          if (sc.line_entry.file == match.line_entry.file ||
+              sc.line_entry.original_file == match.line_entry.original_file) {
+            // When a match is found, keep track of the smallest line number.
+            closest_line = std::min(closest_line, sc.line_entry.line);
+            return false;
+          }
+          return true;
+        });
+    
+    // Within, remove all entries with a larger line number.
+    auto worklist_end = std::remove_if(
+        worklist_begin, all_scs.end(), [&](const SymbolContext &sc) {
+          return closest_line != sc.line_entry.line;
+        });
+
+    // Sort by file address.
+    std::sort(worklist_begin, worklist_end,
+              [](const SymbolContext &a, const SymbolContext &b) {
+                return a.line_entry.range.GetBaseAddress().GetFileAddress() <
+                       b.line_entry.range.GetBaseAddress().GetFileAddress();
+              });
+
+    // Go through and see if there are line table entries that are
+    // contiguous, and if so keep only the first of the contiguous range.
+    // We do this by picking the first location in each lexical block.
+    llvm::SmallDenseSet<Block *, 8> blocks_with_breakpoints;
+    for (auto first = worklist_begin; first != worklist_end; ++first) {
+      assert(!blocks_with_breakpoints.count(first->block));
+      blocks_with_breakpoints.insert(first->block);
+      worklist_end =
+          std::remove_if(std::next(first), worklist_end,
+                         [&](const SymbolContext &sc) {
+                           return blocks_with_breakpoints.count(sc.block);
+                         });
     }
 
-    // Okay, we've found the closest line number match, now throw away all the
-    // others:
+    // Make breakpoints out of the closest line number match.
+    for (auto &sc : llvm::make_range(worklist_begin, worklist_end))
+      AddLocation(filter, sc, skip_prologue, log_ident);
 
-    current_idx = 0;
-    while (current_idx < tmp_sc_list.GetSize()) {
-      if (tmp_sc_list.GetContextAtIndex(current_idx, sc)) {
-        if (sc.line_entry.line != closest_line_number)
-          tmp_sc_list.RemoveContextAtIndex(current_idx);
-        else
-          current_idx++;
-      }
-    }
+    // Remove all contexts processed by this iteration.
+    all_scs.erase(worklist_begin, all_scs.end());
+  }
+}
 
-    // Next go through and see if there are line table entries that are
-    // contiguous, and if so keep only the first of the contiguous range:
-
-    current_idx = 0;
-    std::map<Block *, lldb::addr_t> blocks_with_breakpoints;
-
-    while (current_idx < tmp_sc_list.GetSize()) {
-      if (tmp_sc_list.GetContextAtIndex(current_idx, sc)) {
-        if (blocks_with_breakpoints.find(sc.block) !=
-            blocks_with_breakpoints.end())
-          tmp_sc_list.RemoveContextAtIndex(current_idx);
-        else {
-          blocks_with_breakpoints.insert(std::pair<Block *, lldb::addr_t>(
-              sc.block, sc.line_entry.range.GetBaseAddress().GetFileAddress()));
-          current_idx++;
-        }
-      }
-    }
+void BreakpointResolver::AddLocation(SearchFilter &filter,
+                                     const SymbolContext &sc,
+                                     bool skip_prologue,
+                                     llvm::StringRef log_ident) {
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_BREAKPOINTS));
+  Address line_start = sc.line_entry.range.GetBaseAddress();
+  if (!line_start.IsValid()) {
+    if (log)
+      log->Printf("error: Unable to set breakpoint %s at file address "
+                  "0x%" PRIx64 "\n",
+                  log_ident.str().c_str(), line_start.GetFileAddress());
+    return;
+  }
 
-    // and make breakpoints out of the closest line number match.
-
-    uint32_t tmp_sc_list_size = tmp_sc_list.GetSize();
-
-    for (uint32_t i = 0; i < tmp_sc_list_size; i++) {
-      if (tmp_sc_list.GetContextAtIndex(i, sc)) {
-        Address line_start = sc.line_entry.range.GetBaseAddress();
-        if (line_start.IsValid()) {
-          if (filter.AddressPasses(line_start)) {
-            // If the line number is before the prologue end, move it there...
-            bool skipped_prologue = false;
-            if (skip_prologue) {
-              if (sc.function) {
-                Address prologue_addr(
-                    sc.function->GetAddressRange().GetBaseAddress());
-                if (prologue_addr.IsValid() && (line_start == prologue_addr)) {
-                  const uint32_t prologue_byte_size =
-                      sc.function->GetPrologueByteSize();
-                  if (prologue_byte_size) {
-                    prologue_addr.Slide(prologue_byte_size);
-
-                    if (filter.AddressPasses(prologue_addr)) {
-                      skipped_prologue = true;
-                      line_start = prologue_addr;
-                    }
-                  }
-                }
-              }
-            }
-
-            BreakpointLocationSP bp_loc_sp(AddLocation(line_start));
-            if (log && bp_loc_sp && !m_breakpoint->IsInternal()) {
-              StreamString s;
-              bp_loc_sp->GetDescription(&s, lldb::eDescriptionLevelVerbose);
-              log->Printf("Added location (skipped prologue: %s): %s \n",
-                          skipped_prologue ? "yes" : "no", s.GetData());
-            }
-          } else if (log) {
-            log->Printf("Breakpoint %s at file address 0x%" PRIx64
-                        " didn't pass the filter.\n",
-                        log_ident.str().c_str(), line_start.GetFileAddress());
-          }
-        } else {
-          if (log)
-            log->Printf(
-                "error: Unable to set breakpoint %s at file address 0x%" PRIx64
-                "\n",
-                log_ident.str().c_str(), line_start.GetFileAddress());
+  if (!filter.AddressPasses(line_start)) {
+    if (log)
+      log->Printf("Breakpoint %s at file address 0x%" PRIx64
+                  " didn't pass the filter.\n",
+                  log_ident.str().c_str(), line_start.GetFileAddress());
+  }
+
+  // If the line number is before the prologue end, move it there...
+  bool skipped_prologue = false;
+  if (skip_prologue && sc.function) {
+    Address prologue_addr(sc.function->GetAddressRange().GetBaseAddress());
+    if (prologue_addr.IsValid() && (line_start == prologue_addr)) {
+      const uint32_t prologue_byte_size = sc.function->GetPrologueByteSize();
+      if (prologue_byte_size) {
+        prologue_addr.Slide(prologue_byte_size);
+
+        if (filter.AddressPasses(prologue_addr)) {
+          skipped_prologue = true;
+          line_start = prologue_addr;
         }
       }
     }
   }
+
+  BreakpointLocationSP bp_loc_sp(AddLocation(line_start));
+  if (log && bp_loc_sp && !m_breakpoint->IsInternal()) {
+    StreamString s;
+    bp_loc_sp->GetDescription(&s, lldb::eDescriptionLevelVerbose);
+    log->Printf("Added location (skipped prologue: %s): %s \n",
+                skipped_prologue ? "yes" : "no", s.GetData());
+  }
 }
 
 BreakpointLocationSP BreakpointResolver::AddLocation(Address loc_addr,
@@ -315,7 +296,8 @@ void BreakpointResolver::SetOffset(lldb::addr_t offset) {
   // There may already be an offset, so we are actually adjusting location
   // addresses by the difference.
   // lldb::addr_t slide = offset - m_offset;
-  // FIXME: We should go fix up all the already set locations for the new slide.
+  // FIXME: We should go fix up all the already set locations for the new
+  // slide.
 
   m_offset = offset;
 }