gdb: Restructure the completion_tracker class

In this commit I rewrite how the completion tracker tracks the
completions, and builds its lowest common denominator (LCD) string.
The LCD string is now built lazily when required, and we only track
the completions in one place, the hash table, rather than maintaining
a separate vector of completions.

The motivation for these changes is that the next commit will add the
ability to remove completions from the list, removing a completion
will invalidate the LCD string, so we need to keep hold of enough
information to recompute the LCD string as needed.

Additionally, keeping the completions in a vector makes removing a
completion expensive, so better to only keep the completions in the
hash table.

This commit doesn't add any new functionality itself, and there should
be no user visible changes after this commit.

For testing, I ran the testsuite as usual, but I also ran some manual
completion tests under valgrind, and didn't get any reports about
leaked memory.

gdb/ChangeLog:

	* completer.c (completion_tracker::completion_hash_entry): Define
	new class.
	(advance_to_filename_complete_word_point): Call
	recompute_lowest_common_denominator.
	(completion_tracker::completion_tracker): Call discard_completions
	to setup the hash table.
	(completion_tracker::discard_completions): Allow for being called
	from the constructor, pass new equal function, and element deleter
	when constructing the hash table.  Initialise new class member
	variables.
	(completion_tracker::maybe_add_completion): Remove use of
	m_entries_vec, and store more information into m_entries_hash.
	(completion_tracker::recompute_lcd_visitor): New function, most
	content taken from...
	(completion_tracker::recompute_lowest_common_denominator):
	...here, this now just visits each item in the hash calling the
	above visitor.
	(completion_tracker::build_completion_result): Remove use of
	m_entries_vec, call recompute_lowest_common_denominator.
	* completer.h (completion_tracker::have_completions): Remove use
	of m_entries_vec.
	(completion_tracker::completion_hash_entry): Declare new class.
	(completion_tracker::recompute_lowest_common_denominator): Change
	function signature.
	(completion_tracker::recompute_lcd_visitor): Declare new function.
	(completion_tracker::m_entries_vec): Delete.
	(completion_tracker::m_entries_hash): Initialize to NULL.
	(completion_tracker::m_lowest_common_denominator_valid): New
	member variable.
	(completion_tracker::m_lowest_common_denominator_max_length): New
	member variable.

Change-Id: I9d1db52c489ca0041b8959ca0d53b7d3af8aea72

3 files changed, 222 insertions, 48 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 84964dc..bc927d4 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,37 @@
+2020-03-19  Andrew Burgess  <andrew.burgess@embecosm.com>
+
+	* completer.c (completion_tracker::completion_hash_entry): Define
+	new class.
+	(advance_to_filename_complete_word_point): Call
+	recompute_lowest_common_denominator.
+	(completion_tracker::completion_tracker): Call discard_completions
+	to setup the hash table.
+	(completion_tracker::discard_completions): Allow for being called
+	from the constructor, pass new equal function, and element deleter
+	when constructing the hash table.  Initialise new class member
+	variables.
+	(completion_tracker::maybe_add_completion): Remove use of
+	m_entries_vec, and store more information into m_entries_hash.
+	(completion_tracker::recompute_lcd_visitor): New function, most
+	content taken from...
+	(completion_tracker::recompute_lowest_common_denominator):
+	...here, this now just visits each item in the hash calling the
+	above visitor.
+	(completion_tracker::build_completion_result): Remove use of
+	m_entries_vec, call recompute_lowest_common_denominator.
+	* completer.h (completion_tracker::have_completions): Remove use
+	of m_entries_vec.
+	(completion_tracker::completion_hash_entry): Declare new class.
+	(completion_tracker::recompute_lowest_common_denominator): Change
+	function signature.
+	(completion_tracker::recompute_lcd_visitor): Declare new function.
+	(completion_tracker::m_entries_vec): Delete.
+	(completion_tracker::m_entries_hash): Initialize to NULL.
+	(completion_tracker::m_lowest_common_denominator_valid): New
+	member variable.
+	(completion_tracker::m_lowest_common_denominator_max_length): New
+	member variable.
+
 2020-03-17  Kamil Rytarowski  <n54@gmx.com>
 
 	* regformats/regdef.h: Put reg in gdb namespace.
diff --git a/gdb/completer.c b/gdb/completer.c
index 619fb8a..14c7a57 100644
--- a/gdb/completer.c
+++ b/gdb/completer.c
@@ -45,6 +45,60 @@
 
 #include "completer.h"
 
+/* See completer.h.  */
+
+class completion_tracker::completion_hash_entry
+{
+public:
+  /* Constructor.  */
+  completion_hash_entry (gdb::unique_xmalloc_ptr<char> name,
+			 gdb::unique_xmalloc_ptr<char> lcd)
+    : m_name (std::move (name)),
+      m_lcd (std::move (lcd))
+  {
+    /* Nothing.  */
+  }
+
+  /* Returns a pointer to the lowest common denominator string.  This
+     string will only be valid while this hash entry is still valid as the
+     string continues to be owned by this hash entry and will be released
+     when this entry is deleted.  */
+  char *get_lcd () const
+  {
+    return m_lcd.get ();
+  }
+
+  /* Get, and release the name field from this hash entry.  This can only
+     be called once, after which the name field is no longer valid.  This
+     should be used to pass ownership of the name to someone else.  */
+  char *release_name ()
+  {
+    return m_name.release ();
+  }
+
+  /* Return true of the name in this hash entry is STR.  */
+  bool is_name_eq (const char *str) const
+  {
+    return strcmp (m_name.get (), str) == 0;
+  }
+
+  /* A static function that can be passed to the htab hash system to be
+     used as a callback that deletes an item from the hash.  */
+  static void deleter (void *arg)
+  {
+    completion_hash_entry *entry = (completion_hash_entry *) arg;
+    delete entry;
+  }
+
+private:
+
+  /* The symbol name stored in this hash entry.  */
+  gdb::unique_xmalloc_ptr<char> m_name;
+
+  /* The lowest common denominator string computed for this hash entry.  */
+  gdb::unique_xmalloc_ptr<char> m_lcd;
+};
+
 /* Misc state that needs to be tracked across several different
    readline completer entry point calls, all related to a single
    completion invocation.  */
@@ -407,6 +461,7 @@ advance_to_filename_complete_word_point (completion_tracker &tracker,
 bool
 completion_tracker::completes_to_completion_word (const char *word)
 {
+  recompute_lowest_common_denominator ();
   if (m_lowest_common_denominator_unique)
     {
       const char *lcd = m_lowest_common_denominator;
@@ -1512,9 +1567,7 @@ int max_completions = 200;
 
 completion_tracker::completion_tracker ()
 {
-  m_entries_hash = htab_create_alloc (INITIAL_COMPLETION_HTAB_SIZE,
-				      htab_hash_string, streq_hash,
-				      NULL, xcalloc, xfree);
+  discard_completions ();
 }
 
 /* See completer.h.  */
@@ -1526,13 +1579,33 @@ completion_tracker::discard_completions ()
   m_lowest_common_denominator = NULL;
 
   m_lowest_common_denominator_unique = false;
+  m_lowest_common_denominator_valid = false;
+
+  /* A null check here allows this function to be used from the
+     constructor.  */
+  if (m_entries_hash != NULL)
+    htab_delete (m_entries_hash);
+
+  /* A callback used by the hash table to compare new entries with existing
+     entries.  We can't use the standard streq_hash function here as the
+     key to our hash is just a single string, while the values we store in
+     the hash are a struct containing multiple strings.  */
+  static auto entry_eq_func
+    = [] (const void *first, const void *second) -> int
+      {
+	/* The FIRST argument is the entry already in the hash table, and
+	   the SECOND argument is the new item being inserted.  */
+	const completion_hash_entry *entry
+	  = (const completion_hash_entry *) first;
+	const char *name_str = (const char *) second;
 
-  m_entries_vec.clear ();
+	return entry->is_name_eq (name_str);
+      };
 
-  htab_delete (m_entries_hash);
   m_entries_hash = htab_create_alloc (INITIAL_COMPLETION_HTAB_SIZE,
-				      htab_hash_string, streq_hash,
-				      NULL, xcalloc, xfree);
+				      htab_hash_string, entry_eq_func,
+				      completion_hash_entry::deleter,
+				      xcalloc, xfree);
 }
 
 /* See completer.h.  */
@@ -1559,7 +1632,8 @@ completion_tracker::maybe_add_completion
   if (htab_elements (m_entries_hash) >= max_completions)
     return false;
 
-  slot = htab_find_slot (m_entries_hash, name.get (), INSERT);
+  hashval_t hash = htab_hash_string (name.get ());
+  slot = htab_find_slot_with_hash (m_entries_hash, name.get (), hash, INSERT);
   if (*slot == HTAB_EMPTY_ENTRY)
     {
       const char *match_for_lcd_str = NULL;
@@ -1573,10 +1647,12 @@ completion_tracker::maybe_add_completion
       gdb::unique_xmalloc_ptr<char> lcd
 	= make_completion_match_str (match_for_lcd_str, text, word);
 
-      recompute_lowest_common_denominator (std::move (lcd));
+      size_t lcd_len = strlen (lcd.get ());
+      *slot = new completion_hash_entry (std::move (name), std::move (lcd));
 
-      *slot = name.get ();
-      m_entries_vec.push_back (std::move (name));
+      m_lowest_common_denominator_valid = false;
+      m_lowest_common_denominator_max_length
+	= std::max (m_lowest_common_denominator_max_length, lcd_len);
     }
 
   return true;
@@ -1982,23 +2058,23 @@ completion_find_completion_word (completion_tracker &tracker, const char *text,
 /* See completer.h.  */
 
 void
-completion_tracker::recompute_lowest_common_denominator
-  (gdb::unique_xmalloc_ptr<char> &&new_match_up)
+completion_tracker::recompute_lcd_visitor (completion_hash_entry *entry)
 {
-  if (m_lowest_common_denominator == NULL)
+  if (!m_lowest_common_denominator_valid)
     {
-      /* We don't have a lowest common denominator yet, so simply take
-	 the whole NEW_MATCH_UP as being it.  */
-      m_lowest_common_denominator = new_match_up.release ();
+      /* This is the first lowest common denominator that we are
+	 considering, just copy it in.  */
+      strcpy (m_lowest_common_denominator, entry->get_lcd ());
       m_lowest_common_denominator_unique = true;
+      m_lowest_common_denominator_valid = true;
     }
   else
     {
-      /* Find the common denominator between the currently-known
-	 lowest common denominator and NEW_MATCH_UP.  That becomes the
-	 new lowest common denominator.  */
+      /* Find the common denominator between the currently-known lowest
+	 common denominator and NEW_MATCH_UP.  That becomes the new lowest
+	 common denominator.  */
       size_t i;
-      const char *new_match = new_match_up.get ();
+      const char *new_match = entry->get_lcd ();
 
       for (i = 0;
 	   (new_match[i] != '\0'
@@ -2016,6 +2092,35 @@ completion_tracker::recompute_lowest_common_denominator
 /* See completer.h.  */
 
 void
+completion_tracker::recompute_lowest_common_denominator ()
+{
+  /* We've already done this.  */
+  if (m_lowest_common_denominator_valid)
+    return;
+
+  /* Resize the storage to ensure we have enough space, the plus one gives
+     us space for the trailing null terminator we will include.  */
+  m_lowest_common_denominator
+    = (char *) xrealloc (m_lowest_common_denominator,
+			 m_lowest_common_denominator_max_length + 1);
+
+  /* Callback used to visit each entry in the m_entries_hash.  */
+  auto visitor_func
+    = [] (void **slot, void *info) -> int
+      {
+	completion_tracker *obj = (completion_tracker *) info;
+	completion_hash_entry *entry = (completion_hash_entry *) *slot;
+	obj->recompute_lcd_visitor (entry);
+	return 1;
+      };
+
+  htab_traverse (m_entries_hash, visitor_func, this);
+  m_lowest_common_denominator_valid = true;
+}
+
+/* See completer.h.  */
+
+void
 completion_tracker::advance_custom_word_point_by (int len)
 {
   m_custom_word_point += len;
@@ -2092,16 +2197,17 @@ completion_result
 completion_tracker::build_completion_result (const char *text,
 					     int start, int end)
 {
-  completion_list &list = m_entries_vec;	/* The completions.  */
+  size_t element_count = htab_elements (m_entries_hash);
 
-  if (list.empty ())
+  if (element_count == 0)
     return {};
 
   /* +1 for the LCD, and +1 for NULL termination.  */
-  char **match_list = XNEWVEC (char *, 1 + list.size () + 1);
+  char **match_list = XNEWVEC (char *, 1 + element_count + 1);
 
   /* Build replacement word, based on the LCD.  */
 
+  recompute_lowest_common_denominator ();
   match_list[0]
     = expand_preserving_ws (text, end - start,
 			    m_lowest_common_denominator);
@@ -2128,13 +2234,40 @@ completion_tracker::build_completion_result (const char *text,
     }
   else
     {
-      int ix;
-
-      for (ix = 0; ix < list.size (); ++ix)
-	match_list[ix + 1] = list[ix].release ();
-      match_list[ix + 1] = NULL;
-
-      return completion_result (match_list, list.size (), false);
+      /* State object used while building the completion list.  */
+      struct list_builder
+      {
+	list_builder (char **ml)
+	  : match_list (ml),
+	    index (1)
+	{ /* Nothing.  */ }
+
+	/* The list we are filling.  */
+	char **match_list;
+
+	/* The next index in the list to write to.  */
+	int index;
+      };
+      list_builder builder (match_list);
+
+      /* Visit each entry in m_entries_hash and add it to the completion
+	 list, updating the builder state object.  */
+      auto func
+	= [] (void **slot, void *info) -> int
+	  {
+	    completion_hash_entry *entry = (completion_hash_entry *) *slot;
+	    list_builder *state = (list_builder *) info;
+
+	    state->match_list[state->index] = entry->release_name ();
+	    state->index++;
+	    return 1;
+	  };
+
+      /* Build the completion list and add a null at the end.  */
+      htab_traverse_noresize (m_entries_hash, func, &builder);
+      match_list[builder.index] = NULL;
+
+      return completion_result (match_list, builder.index - 1, false);
     }
 }
 
diff --git a/gdb/completer.h b/gdb/completer.h
index 703a576..7bfe0d5 100644
--- a/gdb/completer.h
+++ b/gdb/completer.h
@@ -389,7 +389,7 @@ public:
 
   /* True if we have any completion match recorded.  */
   bool have_completions () const
-  { return !m_entries_vec.empty (); }
+  { return htab_elements (m_entries_hash) > 0; }
 
   /* Discard the current completion match list and the current
      LCD.  */
@@ -403,6 +403,9 @@ public:
 
 private:
 
+  /* The type that we place into the m_entries_hash hash table.  */
+  class completion_hash_entry;
+
   /* Add the completion NAME to the list of generated completions if
      it is not there already.  If false is returned, too many
      completions were found.  */
@@ -410,18 +413,15 @@ private:
 			     completion_match_for_lcd *match_for_lcd,
 			     const char *text, const char *word);
 
-  /* Given a new match, recompute the lowest common denominator (LCD)
-     to hand over to readline.  Normally readline computes this itself
-     based on the whole set of completion matches.  However, some
-     completers want to override readline, in order to be able to
-     provide a LCD that is not really a prefix of the matches, but the
-     lowest common denominator of some relevant substring of each
-     match.  E.g., "b push_ba" completes to
-     "std::vector<..>::push_back", "std::string::push_back", etc., and
-     in this case we want the lowest common denominator to be
-     "push_back" instead of "std::".  */
-  void recompute_lowest_common_denominator
-    (gdb::unique_xmalloc_ptr<char> &&new_match);
+  /* Ensure that the lowest common denominator held in the member variable
+     M_LOWEST_COMMON_DENOMINATOR is valid.  This method must be called if
+     there is any chance that new completions have been added to the
+     tracker before the lowest common denominator is read.  */
+  void recompute_lowest_common_denominator ();
+
+  /* Callback used from recompute_lowest_common_denominator, called for
+     every entry in m_entries_hash.  */
+  void recompute_lcd_visitor (completion_hash_entry *entry);
 
   /* Completion match outputs returned by the symbol name matching
      routines (see symbol_name_matcher_ftype).  These results are only
@@ -430,16 +430,13 @@ private:
      symbol name matching routines.  */
   completion_match_result m_completion_match_result;
 
-  /* The completion matches found so far, in a vector.  */
-  completion_list m_entries_vec;
-
   /* The completion matches found so far, in a hash table, for
      duplicate elimination as entries are added.  Otherwise the user
      is left scratching his/her head: readline and complete_command
      will remove duplicates, and if removal of duplicates there brings
      the total under max_completions the user may think gdb quit
      searching too early.  */
-  htab_t m_entries_hash;
+  htab_t m_entries_hash = NULL;
 
   /* If non-zero, then this is the quote char that needs to be
      appended after completion (iff we have a unique completion).  We
@@ -483,6 +480,16 @@ private:
      "function()", instead of showing all the possible
      completions.  */
   bool m_lowest_common_denominator_unique = false;
+
+  /* True if the value in M_LOWEST_COMMON_DENOMINATOR is correct.  This is
+     set to true each time RECOMPUTE_LOWEST_COMMON_DENOMINATOR is called,
+     and reset to false whenever a new completion is added.  */
+  bool m_lowest_common_denominator_valid = false;
+
+  /* To avoid calls to xrealloc in RECOMPUTE_LOWEST_COMMON_DENOMINATOR, we
+     track the maximum possible size of the lowest common denominator,
+     which we know as each completion is added.  */
+  size_t m_lowest_common_denominator_max_length = 0;
 };
 
 /* Return a string to hand off to readline as a completion match