[lldb/Symbol] Fix column breakpoint `move_to_nearest_code` match

[mib]

Summary

This patch fixes the column symbol resolution when creating a breakpoint
with the move_to_nearest_code flag set.

In order to achieve this, the patch adds column information handling in
the LineTable's LineEntry finder. After experimenting a little, it
turns out the most natural approach in case of an inaccurate column match,
is to move backward and match the previous LineEntry rather than going
forward like we do with simple line breakpoints.

The patch also reflows the function to reduce code duplication.

Finally, it updates the BreakpointResolver heuristic to align it with
the LineTable method.

rdar://73218201

Signed-off-by: Med Ismail Bennani <[e-mail]>

[JDevlieghere]

lldb/include/lldb/Symbol/LineTable.h

344

It seems like this method is only using m_entries, so I would turn this into a static (non-member) function in the cpp file and pass m_entries as an argument.

370–372

nit: reflow

377

I know you're just moving the code but maybe a good opportunity to simplify the else-after-continue and else-after-return below.

lldb/source/Breakpoint/BreakpointResolver.cpp

230–234

Do these comments need to be updated?

[mib]

lldb/include/lldb/Symbol/LineTable.h

344

Besides m_entries, the function also calls LineTable::ConvertEntryAtIndexToLineEntry which is declared protected. Making the function "static" makes it more convoluted, IMO. I'd rather leave it in the header file.

377

As discussed, I'll simplify these in a follow-up patch.

[mib]

Address @JDevlieghere comments.

[JDevlieghere]

LGTM

lldb/include/lldb/Symbol/LineTable.h

public:
   /// \see CompileUnit::GetSupportFiles()
   /// \see FileSpecList::FindFileIndex (uint32_t, const FileSpec &) const
   uint32_t
   FindLineEntryIndexByFileIndex(uint32_t start_idx, uint32_t file_idx,
                                 const SourceLocationSpec &src_location_spec,
                                 LineEntry *line_entry_ptr);
 
   uint32_t FindLineEntryIndexByFileIndex(
-      uint32_t start_idx, const std::vector<uint32_t> &file_indexes,
+      uint32_t start_idx, const std::vector<uint32_t> &file_idx,
       const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr);
 
   size_t FineLineEntriesForFileIndex(uint32_t file_idx, bool append,
                                      SymbolContextList &sc_list);
 
   /// Get the line entry from the line table at index \a idx.
   ///
   /// \param[in] idx
entry_collection
         m_entries; ///< The collection of line entries in this sequence.
   };
 
   bool ConvertEntryAtIndexToLineEntry(uint32_t idx, LineEntry &line_entry);
 
 private:
   LineTable(const LineTable &) = delete;
   const LineTable &operator=(const LineTable &) = delete;
+
+  template <typename T>
+  uint32_t FindLineEntryIndexByFileIndexImpl(
+      uint32_t start_idx, T file_idx,
+      const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr,
+      std::function<bool(T, uint16_t)> file_idx_matcher) {
+    const size_t count = m_entries.size();
+    size_t best_match = UINT32_MAX;
+
+    if (!line_entry_ptr)
+      return best_match;
+
+    const uint32_t line = src_location_spec.GetLine().getValueOr(0);
+    const uint16_t column =
+        src_location_spec.GetColumn().getValueOr(LLDB_INVALID_COLUMN_NUMBER);
+    const bool exact_match = src_location_spec.GetExactMatch();
+
+    for (size_t idx = start_idx; idx < count; ++idx) {
+      // Skip line table rows that terminate the previous row (is_terminal_entry
+      // is non-zero)
+      if (m_entries[idx].is_terminal_entry)
+        continue;
+
+      if (!file_idx_matcher(file_idx, m_entries[idx].file_idx))
+        continue;
+
+      // Exact match always wins.  Otherwise try to find the closest line > the
+      // desired line.
+      // FIXME: Maybe want to find the line closest before and the line closest
+      // after and if they're not in the same function, don't return a match.
+
+      if (column == LLDB_INVALID_COLUMN_NUMBER) {
+        if (m_entries[idx].line < line) {
+          continue;
+        } else if (m_entries[idx].line == line) {
+          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
+          return idx;
+        } else if (!exact_match) {
+          if (best_match == UINT32_MAX ||
+              m_entries[idx].line < m_entries[best_match].line)
+            best_match = idx;
+        }
+      } else {
+        if (m_entries[idx].line < line) {
+          continue;
+        } else if (m_entries[idx].line == line &&
+                   m_entries[idx].column == column) {
+          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
+          return idx;
+        } else if (!exact_match) {
+          if (best_match == UINT32_MAX)
+            best_match = idx;
+          else if (m_entries[idx].line < m_entries[best_match].line)
+            best_match = idx;
+          else if (m_entries[idx].line == m_entries[best_match].line)
+            if (m_entries[idx].column &&
+                m_entries[idx].column < m_entries[best_match].column)
+              best_match = idx;
+        }
+      }
+    }
+
+    if (best_match != UINT32_MAX) {
+      if (line_entry_ptr)
+        ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
+      return best_match;
+    }
+    return UINT32_MAX;
+  }
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_SYMBOL_LINETABLE_H

lldb/source/Breakpoint/BreakpointResolver.cpp

auto worklist_begin = std::partition(
           }
           return true;
         });
 
     // (worklist_begin, worklist_end) now contains all entries for one filespec.
     auto worklist_end = all_scs.end();
 
     if (column) {
       // If a column was requested, do a more precise match and only
-      // return the first location that comes after or at the
+      // return the first location that comes before or at the
       // requested location.
       SourceLoc requested(line, *column);
       // First, filter out all entries left of the requested column.
       worklist_end = std::remove_if(
           worklist_begin, worklist_end,
-          [&](const SymbolContext &sc) { return SourceLoc(sc) < requested; });
+          [&](const SymbolContext &sc) { return requested < SourceLoc(sc); });
       // Sort the remaining entries by (line, column).
       llvm::sort(worklist_begin, worklist_end,
                  [](const SymbolContext &a, const SymbolContext &b) {
                    return SourceLoc(a) < SourceLoc(b);
                  });
 
       // Filter out all locations with a source location after the closest match.
       if (worklist_begin != worklist_end)

lldb/source/Symbol/LineTable.cpp

bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx,
   line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;
   line_entry.is_prologue_end = entry.is_prologue_end;
   line_entry.is_epilogue_begin = entry.is_epilogue_begin;
   line_entry.is_terminal_entry = entry.is_terminal_entry;
   return true;
 }
 
 uint32_t LineTable::FindLineEntryIndexByFileIndex(
-    uint32_t start_idx, const std::vector<uint32_t> &file_indexes,
+    uint32_t start_idx, uint32_t file_idx,
     const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
+  auto file_idx_matcher = [](uint32_t file_index, uint16_t entry_file_idx) {
+    return file_index == entry_file_idx;
+  };
+  return FindLineEntryIndexByFileIndexImpl<uint32_t>(
 
-  const size_t count = m_entries.size();
-  size_t best_match = UINT32_MAX;
-
-  for (size_t idx = start_idx; idx < count; ++idx) {
-    // Skip line table rows that terminate the previous row (is_terminal_entry
-    // is non-zero)
-    if (m_entries[idx].is_terminal_entry)
-      continue;
-
-    if (!llvm::is_contained(file_indexes, m_entries[idx].file_idx))
-      continue;
-
-    // Exact match always wins.  Otherwise try to find the closest line > the
-    // desired line.
-    // FIXME: Maybe want to find the line closest before and the line closest
-    // after and
-    // if they're not in the same function, don't return a match.
-
-    uint32_t line = src_location_spec.GetLine().getValueOr(0);
-
-    if (m_entries[idx].line < line) {
-      continue;
-    } else if (m_entries[idx].line == line) {
-      if (line_entry_ptr)
-        ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
-      return idx;
-    } else if (!src_location_spec.GetExactMatch()) {
-      if (best_match == UINT32_MAX)
-        best_match = idx;
-      else if (m_entries[idx].line < m_entries[best_match].line)
-        best_match = idx;
-    }
-  }
-
-  if (best_match != UINT32_MAX) {
-    if (line_entry_ptr)
-      ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
-    return best_match;
-  }
-  return UINT32_MAX;
+      start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
 }
 
 uint32_t LineTable::FindLineEntryIndexByFileIndex(
-    uint32_t start_idx, uint32_t file_idx,
+    uint32_t start_idx, const std::vector<uint32_t> &file_idx,
     const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
-  const size_t count = m_entries.size();
-  size_t best_match = UINT32_MAX;
-
-  for (size_t idx = start_idx; idx < count; ++idx) {
-    // Skip line table rows that terminate the previous row (is_terminal_entry
-    // is non-zero)
-    if (m_entries[idx].is_terminal_entry)
-      continue;
-
-    if (m_entries[idx].file_idx != file_idx)
-      continue;
+  auto file_idx_matcher = [](const std::vector<uint32_t> &file_indexes,
+                             uint16_t entry_file_idx) {
+    return llvm::is_contained(file_indexes, entry_file_idx);
+  };
 
-    // Exact match always wins.  Otherwise try to find the closest line > the
-    // desired line.
-    // FIXME: Maybe want to find the line closest before and the line closest
-    // after and
-    // if they're not in the same function, don't return a match.
-
-    uint32_t line = src_location_spec.GetLine().getValueOr(0);
-
-    if (m_entries[idx].line < line) {
-      continue;
-    } else if (m_entries[idx].line == line) {
-      if (line_entry_ptr)
-        ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
-      return idx;
-    } else if (!src_location_spec.GetExactMatch()) {
-      if (best_match == UINT32_MAX)
-        best_match = idx;
-      else if (m_entries[idx].line < m_entries[best_match].line)
-        best_match = idx;
-    }
-  }
-
-  if (best_match != UINT32_MAX) {
-    if (line_entry_ptr)
-      ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
-    return best_match;
-  }
-  return UINT32_MAX;
+  return FindLineEntryIndexByFileIndexImpl<std::vector<uint32_t>>(
+      start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
 }
 
 size_t LineTable::FineLineEntriesForFileIndex(uint32_t file_idx, bool append,
                                               SymbolContextList &sc_list) {
 
   if (!append)
     sc_list.Clear();
 

lldb/test/API/functionalities/breakpoint/breakpoint_by_line_and_column/Makefile

-C_SOURCES := main.c
-CFLAGS_EXTRAS := -std=c99 -gcolumn-info
+CXX_SOURCES := main.cpp
+CXXFLAGS_EXTRAS := -std=c++14 -gcolumn-info
 
 include Makefile.rules

lldb/test/API/functionalities/breakpoint/breakpoint_by_line_and_column/TestBreakpointByLineAndColumn.py

 """
 Test setting a breakpoint by line and column.
 """
 
-
-
+import re
 import lldb
 from lldbsuite.test.decorators import *
 from lldbsuite.test.lldbtest import *
 from lldbsuite.test import lldbutil
 
 
 class BreakpointByLineAndColumnTestCase(TestBase):
 
     mydir = TestBase.compute_mydir(__file__)
 
     ## Skip gcc version less 7.1 since it doesn't support -gcolumn-info
     @skipIf(compiler="gcc", compiler_version=['<', '7.1'])
     def testBreakpointByLineAndColumn(self):
         self.build()
-        main_c = lldb.SBFileSpec("main.c")
+        src_file = lldb.SBFileSpec("main.cpp")
+        line = line_number("main.cpp",
+                           "At the beginning of a function name (col:50)") + 1 # Next line after comment
         _, _, _, breakpoint = lldbutil.run_to_line_breakpoint(self,
-                                                              main_c, 11, 50)
+                                                              src_file, line, 50)
         self.expect("fr v did_call", substrs=['1'])
         in_then = False
         for i in range(breakpoint.GetNumLocations()):
             b_loc = breakpoint.GetLocationAtIndex(i).GetAddress().GetLineEntry()
-            self.assertEqual(b_loc.GetLine(), 11)
+            self.assertEqual(b_loc.GetLine(), line)
             in_then |= b_loc.GetColumn() == 50
         self.assertTrue(in_then)
 
     ## Skip gcc version less 7.1 since it doesn't support -gcolumn-info
     @skipIf(compiler="gcc", compiler_version=['<', '7.1'])
     def testBreakpointByLine(self):
         self.build()
-        main_c = lldb.SBFileSpec("main.c")
-        _, _, _, breakpoint = lldbutil.run_to_line_breakpoint(self, main_c, 11)
+        src_file = lldb.SBFileSpec("main.cpp")
+        line = line_number("main.cpp",
+                           "At the beginning of a function name (col:50)") + 1 # Next line after comment
+        _, _, _, breakpoint = lldbutil.run_to_line_breakpoint(self, src_file,
+                                                              line)
         self.expect("fr v did_call", substrs=['0'])
         in_condition = False
         for i in range(breakpoint.GetNumLocations()):
             b_loc = breakpoint.GetLocationAtIndex(i).GetAddress().GetLineEntry()
-            self.assertEqual(b_loc.GetLine(), 11)
+            self.assertEqual(b_loc.GetLine(), line)
             in_condition |= b_loc.GetColumn() < 30
         self.assertTrue(in_condition)
 
     ## Skip gcc version less 7.1 since it doesn't support -gcolumn-info
     @skipIf(compiler="gcc", compiler_version=['<', '7.1'])
     def testBreakpointByLineAndColumnNearestCode(self):
         self.build()
         exe = self.getBuildArtifact("a.out")
 
-        main_c = lldb.SBFileSpec("main.c")
-        line = line_number("main.c", "// Line 20.")
-        column = len("// Line 20") # should stop at the period.
-        indent = 2
-        module_list = lldb.SBFileSpecList()
+        patterns = [
+            "In the middle of a function name (col:42)",
+            "In the middle of the lambda declaration argument (col:23)",
+            "Inside the lambda (col:26)"
+        ]
+
+        source_loc = []
+
+        for pattern in patterns:
+            line = line_number("main.cpp", pattern) + 1
+            column = int(re.search('\(col:([0-9]+)\)', pattern).group(1))
+            source_loc.append({'line':line, 'column':column})
 
         # Create a target from the debugger.
         target = self.dbg.CreateTarget(exe)
         self.assertTrue(target, VALID_TARGET)
 
-        valid_bpt = target.BreakpointCreateByLocation(main_c, line, column,
-                                                      indent, module_list, True)
-        self.assertTrue(valid_bpt, VALID_BREAKPOINT)
-        self.assertEqual(valid_bpt.GetNumLocations(), 1)
 
-        invalid_bpt = target.BreakpointCreateByLocation(main_c, line, column,
+        for loc in source_loc:
+            src_file = lldb.SBFileSpec("main.cpp")
+            line = loc['line']
+            column = loc['column']
+            indent = 0
+            module_list = lldb.SBFileSpecList()
+
+            valid_bpkt = target.BreakpointCreateByLocation(src_file, line,
+                                                          column, indent,
+                                                          module_list, True)
+            self.assertTrue(valid_bpkt, VALID_BREAKPOINT)
+            self.assertEqual(valid_bpkt.GetNumLocations(), 1)
+
+        process = target.LaunchSimple(
+                            None, None, self.get_process_working_directory())
+        self.assertTrue(process, PROCESS_IS_VALID)
+
+        nearest_column = [7, 17, 26]
+
+        for idx,loc in enumerate(source_loc):
+            bpkt = target.GetBreakpointAtIndex(idx)
+            bpkt_loc = bpkt.GetLocationAtIndex(0)
+            self.assertEqual(bpkt_loc.GetHitCount(), 1)
+            self.assertSuccess(process.Continue())
+            bpkt_loc_desc = lldb.SBStream()
+            self.assertTrue(bpkt_loc.GetDescription(bpkt_loc_desc, lldb.eDescriptionLevelVerbose))
+            self.assertIn("main.cpp:{}:{}".format(loc['line'], nearest_column[idx]),
+                          bpkt_loc_desc.GetData())
+            bpkt_loc_addr = bpkt_loc.GetAddress()
+            self.assertTrue(bpkt_loc_addr)
+
+            list = target.FindCompileUnits(lldb.SBFileSpec("main.cpp", False))
+            # Executable has been built just from one source file 'main.cpp',
+            # so we may check only the first element of list.
+            compile_unit = list[0].GetCompileUnit()
+
+            found = False
+            for line_entry in compile_unit:
+                if line_entry.GetStartAddress() == bpkt_loc_addr:
+                    self.assertEqual(line_entry.GetFileSpec().GetFilename(),
+                                    "main.cpp")
+                    self.assertEqual(line_entry.GetLine(), loc['line'])
+                    self.assertEqual(line_entry.GetColumn(), nearest_column[idx])
+                    found = True
+                    break
+
+            self.assertTrue(found)
+
+        line = line_number("main.cpp", "// This is a random comment.")
+        column = len("// This is a random comment.")
+        indent = 2
+        invalid_bpkt = target.BreakpointCreateByLocation(src_file, line, column,
                                                       indent, module_list, False)
-        self.assertTrue(invalid_bpt, VALID_BREAKPOINT)
-        self.assertEqual(invalid_bpt.GetNumLocations(), 0)
+        self.assertTrue(invalid_bpkt, VALID_BREAKPOINT)
+        self.assertEqual(invalid_bpkt.GetNumLocations(), 0)
 

lldb/test/API/functionalities/breakpoint/breakpoint_by_line_and_column/main.c

-int square(int x)
-{
-  return x * x;
-}
-
-int main (int argc, char const *argv[])
-{
-  int did_call = 0;
-
-  // Line 20.                                    v Column 50.
-  if(square(argc+1) != 0) { did_call = 1; return square(argc); }
-  //                                             ^
-  return square(0);
-}

lldb/test/API/functionalities/breakpoint/breakpoint_by_line_and_column/main.cpp

+static int this_is_a_very_long_function_with_a_bunch_of_arguments(
+    int first, int second, int third, int fourth, int fifth) {
+  int result = first + second + third + fourth + fifth;
+  return result;
+}
+
+int square(int x) { return x * x; }
+
+int main(int argc, char const *argv[]) {
+  // This is a random comment.
+  int did_call = 0;
+
+  int first = 1;
+  int second = 2;
+  int third = 3;
+  int fourth = 4;
+  int fifth = 5;
+
+  //                                    v In the middle of a function name (col:42)
+  int result = this_is_a_very_long_function_with_a_bunch_of_arguments(
+      first, second, third, fourth, fifth);
+
+  //                  v In the middle of the lambda declaration argument (col:23)
+  auto lambda = [&](int n) {
+  //                     v Inside the lambda (col:26)
+    return first + third * n;
+  };
+
+  result = lambda(3);
+
+  //                                             v At the beginning of a function name (col:50)
+  if(square(argc+1) != 0) { did_call = 1; return square(argc); }
+
+  return square(0);
+}