Re: [PATCH v2 4/4] Fix parameter-less template regression in new DWARF reader

[Andrew Burgess <aburgess@redhat.com>]

Simon Marchi via Gdb-patches <gdb-patches@sourceware.org> writes:

> On 1/17/23 14:39, Tom Tromey wrote:
>>>>>>> "Simon" == Simon Marchi <simark@simark.ca> writes:
>> 
>> Simon> Starting with this patch, I get (using _GLIBCXX_DEBUG):
>> [...]
>> 
>> Ugh, sorry about that.
>> I've reproduce it and I'm working on a fix.
>> 
>> Tom
>
> I started to look into this, using that other patch I sent that dumps
> the contents of the cooked index.  You probably already know this, as
> you have been looking at the problem already, but it can perhaps help
> pothers.  The specific instance I look at is:
>
>   $ ./gdb -nx -q --data-directory=data-directory testsuite/outputs/gdb.cp/cpexprs/cpexprs -ex start -ex "print policy1::function" -batch
>
> When searching in the cooked index, the search string (canonicalized
> version of the input, I think) is:
>
>   "policy<int, operation_1<void*> >::function"
>
> The problem is that the lower bound function used in
> cooked_index::find (cooked_index_entry::compare) is invalid for these
> two consecutive entries:
>
>     [365] ((cooked_index_entry *) 0x621000115080)
>     name:       policy
>     canonical:  policy
>     DWARF tag:  DW_TAG_subprogram
>     flags:      0x0 []
>     DIE offset: 0x3951
>     parent:     ((cooked_index_entry *) 0x6210001137a0) [policy<int, operation_2<void*> >]
>
>     [366] ((cooked_index_entry *) 0x621000113740)
>     name:       policy<int, operation_1<void*> >
>     canonical:  policy<int, operation_1<void*> >
>     DWARF tag:  DW_TAG_class_type
>     flags:      0x0 []
>     DIE offset: 0x22a3
>     parent:     ((cooked_index_entry *) 0)
>
> It returns that [365] greater or equal to our search string, but also
> that [366] is less than our search string.  This is a contradiction,
> because elements are supposed to be sorted according to the comparison
> function.

I've been carrying a patch to work around this issue since the issue was
introduced.  I've included the patch below, but I don't see it as a
permanent fix, though it might help some folk in the short term as a
work around.

The underlying problem is that we use a different sort predicate for the
std::lower_bound and std::upper_bound calls (in some cases) than when we
sorted this list.  I'm not sure this can ever work correctly.

The patch below replaces the lower/upper bound calls with a linear walk
of the cooked_index, but this is pretty slow, so much so I had to extend
a timeout in one test to avoid it timing out.

I also started looking into this more seriously yesterday as I was
getting fed up having to port this patch to all my dev branches.

Thanks,
Andrew

---

commit 8094b570486c6a9af4b3223ac7dc42227064cd10
Author: Andrew Burgess <aburgess@redhat.com>
Date:   Thu Jan 19 18:16:07 2023 +0000

    [wip] gdb: temporary fix for the cooked index issue
    
    Issue introduced in commit:
    
      commit ac37b79cc440e37fc704d425a6e450afb3c7ee89
      Date:   Wed Dec 14 14:37:41 2022 -0700
    
          Fix parameter-less template regression in new DWARF reader
    
    Problem is a use of std::lower_bound with a comparison function that
    is different to the one used to sort the vector.
    
    This changes seems to slow down GDB a fair bit though, this can be
    seen by the need to adjust gdb.gdb/python-helper.exp.

diff --git a/gdb/dwarf2/cooked-index.c b/gdb/dwarf2/cooked-index.c
index 09b3fd70b26..48f58f70b0f 100644
--- a/gdb/dwarf2/cooked-index.c
+++ b/gdb/dwarf2/cooked-index.c
@@ -30,7 +30,7 @@
 
 /* See cooked-index.h.  */
 
-bool
+int
 cooked_index_entry::compare (const char *stra, const char *strb,
 			     bool completing)
 {
@@ -58,7 +58,7 @@ cooked_index_entry::compare (const char *stra, const char *strb,
 	 consider them as equal.  Also, completion mode ignores the
 	 special '<' handling.  */
       if (c1 == '\0' || c2 == '\0')
-	return false;
+	return 0;
       /* Fall through to the generic case.  */
     }
   else if (seen_lt)
@@ -69,17 +69,31 @@ cooked_index_entry::compare (const char *stra, const char *strb,
     {
       /* Maybe they both end at the same spot.  */
       if (c2 == '\0' || c2 == '<')
-	return false;
+	return 0;
       /* First string ended earlier.  */
-      return true;
+      return -1;
     }
   else if (c2 == '\0' || c2 == '<')
     {
       /* Second string ended earlier.  */
-      return false;
+      return 1;
     }
 
-  return c1 < c2;
+  if (c1 < c2)
+    return -1;
+  else if (c1 == c2)
+    return 0;
+  else
+    return 1;
+}
+
+/* See cooked-index.h.  */
+
+bool
+cooked_index_entry::is_equal (const char *stra, const char *strb,
+			      bool completing)
+{
+  return compare (stra, strb, completing) == 0;
 }
 
 #if GDB_SELF_TEST
@@ -89,45 +103,45 @@ namespace {
 void
 test_compare ()
 {
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false));
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false));
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true));
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true));
-
-  SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", false));
-  SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", false));
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "ABCDE", true));
-  SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", true));
-
-  SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", false));
-  SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", false));
-  SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", true));
-  SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", true));
-
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", false));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", false));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", true));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<ag>", true));
-
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>",
-					    "name<arg<more>>", false));
-
-  SELF_CHECK (!cooked_index_entry::compare ("name", "name<arg<more>>", false));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name", false));
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", true) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", true) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", false) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd", false) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", true) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd", true) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name", "name<>", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<>", "name", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name", "name<>", true) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<>", "name", true) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>", true) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<ag>", true) > 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>",
+					    "name<arg<more>>", false) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name", "name<arg<more>>", false) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name", false) == 0);
   SELF_CHECK (cooked_index_entry::compare ("name<arg<", "name<arg<more>>",
-					   false));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg<",
-					    "name<arg<more>>",
-					    true));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
-					    false));
-  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
-					    true));
-
-  SELF_CHECK (cooked_index_entry::compare ("", "abcd", false));
-  SELF_CHECK (!cooked_index_entry::compare ("", "abcd", true));
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "", false));
-  SELF_CHECK (!cooked_index_entry::compare ("abcd", "", true));
+					   false) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<",
+					   "name<arg<more>>",
+					   true) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
+					   false) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
+					   true) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("", "abcd", false) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("", "abcd", true) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "", false) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "", true) == 0);
 }
 
 } /* anonymous namespace */
@@ -352,32 +366,6 @@ cooked_index::do_finalize ()
 	     });
 }
 
-/* See cooked-index.h.  */
-
-cooked_index::range
-cooked_index::find (const std::string &name, bool completing)
-{
-  wait ();
-
-  auto lower = std::lower_bound (m_entries.begin (), m_entries.end (), name,
-				 [=] (const cooked_index_entry *entry,
-				      const std::string &n)
-  {
-    return cooked_index_entry::compare (entry->canonical, n.c_str (),
-					completing);
-  });
-
-  auto upper = std::upper_bound (m_entries.begin (), m_entries.end (), name,
-				 [=] (const std::string &n,
-				      const cooked_index_entry *entry)
-  {
-    return cooked_index_entry::compare (n.c_str (), entry->canonical,
-					completing);
-  });
-
-  return range (lower, upper);
-}
-
 cooked_index_vector::cooked_index_vector (vec_type &&vec)
   : m_vector (std::move (vec))
 {
@@ -417,8 +405,31 @@ cooked_index_vector::find (const std::string &name, bool completing)
 {
   std::vector<cooked_index::range> result_range;
   result_range.reserve (m_vector.size ());
-  for (auto &entry : m_vector)
-    result_range.push_back (entry->find (name, completing));
+
+  for (auto &cooked_index : m_vector)
+    {
+      auto entry_range = cooked_index->all_entries ();
+      for (auto it = entry_range.begin ();
+	   it < entry_range.end ();
+	   ++it)
+	{
+	  auto start_it = it;
+	  while (it < entry_range.end ()
+		 && cooked_index_entry::is_equal ((*it)->canonical,
+						  name.c_str (),
+						  completing))
+	    ++it;
+
+	  if (start_it != it)
+	    {
+	      cooked_index::range r { start_it, it };
+	      result_range.push_back (r);
+	    }
+
+	  if (it == entry_range.end ())
+	    break;
+	}
+    }
   return range (std::move (result_range));
 }
 
diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h
index 55eaf9955ab..b1e4859f6aa 100644
--- a/gdb/dwarf2/cooked-index.h
+++ b/gdb/dwarf2/cooked-index.h
@@ -143,16 +143,25 @@ struct cooked_index_entry : public allocate_on_obstack
      STORAGE.  */
   const char *full_name (struct obstack *storage) const;
 
+  /* Compare two strings, case-insensitively.  Return -1 if STRA is
+     less than STRB, 0 if STRA equals STRB, and 1 if STRA is greater than
+     STRB.
+
+     If one string has template parameters, but the other does not, then
+     they are considered to be equal; so for example "t<x>" == "t<x>",
+     "t<x>" < "t<y>", but "t" == "t<x>".  */
+  static int compare (const char *stra, const char *strb, bool completing);
+
   /* Compare two strings, case-insensitively.  Return true if STRA is
-     less than STRB.  If one string has template parameters, but the
+     equal to STRB.  If one string has template parameters, but the
      other does not, then they are considered to be equal; so for
      example "t<x>" == "t<x>", "t<x>" < "t<y>", but "t" == "t<x>".  */
-  static bool compare (const char *stra, const char *strb, bool completing);
+  static bool is_equal (const char *stra, const char *strb, bool completing);
 
   /* Compare two entries by canonical name.  */
   bool operator< (const cooked_index_entry &other) const
   {
-    return compare (canonical, other.canonical, false);
+    return compare (canonical, other.canonical, false) < 0;
   }
 
   /* The name as it appears in DWARF.  This always points into one of
@@ -234,11 +243,6 @@ class cooked_index
     return { m_entries.begin (), m_entries.end () };
   }
 
-  /* Look up an entry by name.  Returns a range of all matching
-     results.  If COMPLETING is true, then a larger range, suitable
-     for completion, will be returned.  */
-  range find (const std::string &name, bool completing);
-
 private:
 
   /* Return the entry that is believed to represent the program's
diff --git a/gdb/testsuite/gdb.gdb/python-helper.exp b/gdb/testsuite/gdb.gdb/python-helper.exp
index 98f03ef456f..186ae4eed56 100644
--- a/gdb/testsuite/gdb.gdb/python-helper.exp
+++ b/gdb/testsuite/gdb.gdb/python-helper.exp
@@ -211,5 +211,7 @@ proc test_python_helper {} {
     return 0
 }
 
-# Use the self-test framework to run the test.
-do_self_tests captured_main test_python_helper
+with_timeout_factor 3 {
+    # Use the self-test framework to run the test.
+    do_self_tests captured_main test_python_helper
+}