public inbox for gdb-patches@sourceware.org
 help / color / mirror / Atom feed
From: Tom Tromey <tromey@adacore.com>
To: gdb-patches@sourceware.org
Cc: Tom Tromey <tromey@adacore.com>
Subject: [PATCH v2] Fix comparator bug in cooked index
Date: Mon, 30 Jan 2023 07:56:17 -0700	[thread overview]
Message-ID: <20230130145617.1619439-1-tromey@adacore.com> (raw)

Simon pointed out that the cooked index template-matching patch
introduced a failure in libstdc++ debug mode.  In particular, the new
code violates the assumption of std::lower_bound and std::upper_bound
that the range is sorted with respect to the comparison.

When I first debugged this, I thought the problem was unfixable as-is
and that a second layer of filtering would have to be done.  However,
on irc, Simon pointed out that it could perhaps be solved if the
comparison function were assured that one operand always came from the
index, with the other always being the search string.

This patch implements this idea.

First, a new mode is introduced: a sorting mode for
cooked_index_entry::compare.  In this mode, strings are compared
case-insensitively, but we're careful to always sort '<' before any
other printable character.  This way, two names like "func" and
"func<param>" will be sorted next to each other -- i.e., "func1" will
not be seen between them.  This is important when searching.

Second, the compare function is changed to work in a strcmp-like way.
This makes it easier to test and (IMO) understand.

Third, the compare function is modified so that in non-sorting modes,
the index entry is always the first argument.  This allows consistency
in compares.

I regression tested this in libstdc++ debug mode on x86-64 Fedora 36.
It fixes the crash that Simon saw.

This is v2.  I believe it addresses the review comments, except for
the 'enum class' change, as I mentioned in email on the list.
---
 gdb/dwarf2/cooked-index.c | 167 ++++++++++++++++++++------------------
 gdb/dwarf2/cooked-index.h |  50 ++++++++++--
 2 files changed, 132 insertions(+), 85 deletions(-)

diff --git a/gdb/dwarf2/cooked-index.c b/gdb/dwarf2/cooked-index.c
index 1a568e6aae7..9829f6f2b1f 100644
--- a/gdb/dwarf2/cooked-index.c
+++ b/gdb/dwarf2/cooked-index.c
@@ -30,56 +30,43 @@
 
 /* See cooked-index.h.  */
 
-bool
+int
 cooked_index_entry::compare (const char *stra, const char *strb,
-			     bool completing)
+			     comparison_mode mode)
 {
-  /* If we've ever matched "<" in both strings, then we disable the
-     special template parameter handling.  */
-  bool seen_lt = false;
+  auto munge = [] (char c) -> unsigned char
+    {
+      /* We want to sort '<' before any other printable character.
+	 So, rewrite '<' to something just before ' '.  */
+      if (c == '<')
+	return '\x1f';
+      return TOLOWER ((unsigned char) c);
+    };
 
   while (*stra != '\0'
 	 && *strb != '\0'
-	 && (TOLOWER ((unsigned char) *stra)
-	     == TOLOWER ((unsigned char ) *strb)))
+	 && (munge (*stra) == munge (*strb)))
     {
-      if (*stra == '<')
-	seen_lt = true;
       ++stra;
       ++strb;
     }
 
-  unsigned c1 = TOLOWER ((unsigned char) *stra);
-  unsigned c2 = TOLOWER ((unsigned char) *strb);
+  unsigned char c1 = munge (*stra);
+  unsigned char c2 = munge (*strb);
 
-  if (completing)
-    {
-      /* When completing, if one string ends earlier than the other,
-	 consider them as equal.  Also, completion mode ignores the
-	 special '<' handling.  */
-      if (c1 == '\0' || c2 == '\0')
-	return false;
-      /* Fall through to the generic case.  */
-    }
-  else if (seen_lt)
-    {
-      /* Fall through to the generic case.  */
-    }
-  else if (c1 == '\0' || c1 == '<')
-    {
-      /* Maybe they both end at the same spot.  */
-      if (c2 == '\0' || c2 == '<')
-	return false;
-      /* First string ended earlier.  */
-      return true;
-    }
-  else if (c2 == '\0' || c2 == '<')
+  if (c1 == c2)
+    return 0;
+
+  /* When completing, if STRB ends earlier than STRA, consider them as
+     equal.  When comparing, if STRB ends earlier and STRA ends with
+     '<', consider them as equal.  */
+  if (mode == COMPLETE || (mode == MATCH && c1 == munge ('<')))
     {
-      /* Second string ended earlier.  */
-      return false;
+      if (c2 == '\0')
+	return 0;
     }
 
-  return c1 < c2;
+  return c1 < c2 ? -1 : 1;
 }
 
 #if GDB_SELF_TEST
@@ -89,45 +76,65 @@ 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 ("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));
+  /* Convenience aliases.  */
+  const auto mode_compare = cooked_index_entry::MATCH;
+  const auto mode_sort = cooked_index_entry::SORT;
+  const auto mode_complete = cooked_index_entry::COMPLETE;
+
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd",
+					   mode_compare) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd",
+					   mode_complete) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE",
+					   mode_compare) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd",
+					   mode_compare) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE",
+					   mode_complete) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd",
+					   mode_complete) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name", "name<>",
+					   mode_compare) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<>", "name",
+					   mode_compare) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name", "name<>",
+					   mode_complete) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<>", "name",
+					   mode_complete) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>",
+					   mode_compare) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<ag>",
+					   mode_compare) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>",
+					   mode_complete) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<ag>",
+					   mode_complete) > 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>",
+					   "name<arg<more>>",
+					   mode_compare) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("name", "name<arg<more>>",
+					   mode_compare) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name",
+					   mode_compare) == 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
+					   mode_compare) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
+					   mode_complete) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("", "abcd", mode_compare) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("", "abcd", mode_complete) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "", mode_compare) > 0);
+  SELF_CHECK (cooked_index_entry::compare ("abcd", "", mode_complete) == 0);
+
+  SELF_CHECK (cooked_index_entry::compare ("func", "func<type>",
+					   mode_sort) < 0);
+  SELF_CHECK (cooked_index_entry::compare ("func<type>", "func1",
+					   mode_sort) < 0);
 }
 
 } /* anonymous namespace */
@@ -359,20 +366,22 @@ cooked_index::find (const std::string &name, bool completing) const
 {
   wait ();
 
+  cooked_index_entry::comparison_mode mode = (completing
+					      ? cooked_index_entry::COMPLETE
+					      : cooked_index_entry::MATCH);
+
   auto lower = std::lower_bound (m_entries.cbegin (), m_entries.cend (), name,
 				 [=] (const cooked_index_entry *entry,
 				      const std::string &n)
   {
-    return cooked_index_entry::compare (entry->canonical, n.c_str (),
-					completing);
+    return cooked_index_entry::compare (entry->canonical, n.c_str (), mode) < 0;
   });
 
   auto upper = std::upper_bound (m_entries.cbegin (), m_entries.cend (), name,
 				 [=] (const std::string &n,
 				      const cooked_index_entry *entry)
   {
-    return cooked_index_entry::compare (n.c_str (), entry->canonical,
-					completing);
+    return cooked_index_entry::compare (entry->canonical, n.c_str (), mode) > 0;
   });
 
   return range (lower, upper);
diff --git a/gdb/dwarf2/cooked-index.h b/gdb/dwarf2/cooked-index.h
index e12376cdf98..76e571795fa 100644
--- a/gdb/dwarf2/cooked-index.h
+++ b/gdb/dwarf2/cooked-index.h
@@ -143,16 +143,54 @@ struct cooked_index_entry : public allocate_on_obstack
      STORAGE.  */
   const char *full_name (struct obstack *storage) const;
 
-  /* Compare two strings, case-insensitively.  Return true if STRA is
-     less 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 bool compare (const char *stra, const char *strb, bool completing);
+  /* Comparison modes for the 'compare' function.  See the function
+     for a description.  */
+  enum comparison_mode
+  {
+    MATCH,
+    SORT,
+    COMPLETE,
+  };
+
+  /* Compare two strings, case-insensitively.  Return -1 if STRA is
+     less than STRB, 0 if they are equal, and 1 if STRA is greater.
+
+     When comparing, '<' is considered to be less than all other
+     printable characters.  This ensures that "t<x>" sorts before
+     "t1", which is necessary when looking up "t".  This '<' handling
+     is to ensure that certain C++ lookups work correctly.  It is
+     inexact, and applied regardless of the search language, but this
+     is ok because callers of this code do more precise filtering
+     according to their needs.  This is also why using a
+     case-insensitive comparison works even for languages that are
+     case sensitive.
+
+     MODE controls how the comparison proceeds.
+
+     MODE==SORT is used when sorting and the only special '<' handling
+     that it does is to ensure that '<' sorts before all other
+     printable characters.  This ensures that the resulting ordering
+     will be binary-searchable.
+
+     MODE==MATCH is used when searching for a symbol.  In this case,
+     STRB must always be the search name, and STRA must be the name in
+     the index that is under consideration.  In compare mode, early
+     termination of STRB may match STRA -- for example, "t<int>" and
+     "t" will be considered to be equal.  (However, if A=="t" and
+     B=="t<int>", then this will not consider them as equal.)
+
+     MODE==COMPLETE is used when searching for a symbol for
+     completion.  In this case, STRB must always be the search name,
+     and STRA must be the name in the index that is under
+     consideration.  In completion mode, early termination of STRB
+     always results in a match.  */
+  static int compare (const char *stra, const char *strb,
+		      comparison_mode mode);
 
   /* 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, SORT) < 0;
   }
 
   /* The name as it appears in DWARF.  This always points into one of
-- 
2.38.1


             reply	other threads:[~2023-01-30 14:56 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-01-30 14:56 Tom Tromey [this message]
2023-01-30 15:15 ` Simon Marchi
2023-01-30 17:46   ` Tom Tromey

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20230130145617.1619439-1-tromey@adacore.com \
    --to=tromey@adacore.com \
    --cc=gdb-patches@sourceware.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).