This commit converts the completion_tracker class to use std types,
while maintaining the existing functionality.
As part of this commit I have restructured how the completion tracker
works a little, the lowest common denominator is now calculated lazily
when we need it. The reason for this is not performance, but instead
to prepare the way for the next commit which will require the
completion track to support removing possible completions. If we
calculate the lowest common denominator as we add completions then
removing completions becomes much harder.
With the move to std types there is some ugliness relating to how
object ownership is managed that needs to be worked with. The
completions are delivered to the completion_tracker as managed strings
within a gdb::unique_xmalloc_ptr<char>, and in an ideal world we would
use these objects as the keys and values within the hash.
The problem is that when we try to remove the items from the hash in
order to pass them to readline; I don't believe there is any easy way
to get the gdb::unique_xmalloc_ptr<char> out of the hash without
having it delete the string it's managing without using C++17 language
features, specifically the std::unordered_map::extract method.
For now then I'm holding the raw 'char *' within the unordered_map,
and rely on the completion_tracker object to delete the data if
needed, or to ensure that the data is passed over to readline, which
will do the deletion for us.
One further ugliness of the new code is that the new unordered_map
actually holds 'const char *', this will make the next commit slightly
easier, but does mean some unfortunate casting in this commit.
There should be no user visible changes after this commit.
gdb/ChangeLog:
* completer.c (completion_tracker::completes_to_completion_word):
Update for changes in how lowest common denominator is managed.
(completion_tracker::completion_tracker): Now does nothing.
(completion_tracker::discard_completions): Update for changes to
lowest common denominator, and to m_entries_hash.
(completion_tracker::maybe_add_completion): Likewise.
(completion_tracker::~completion_tracker): Call
discard_completions.
(completion_tracker::recompute_lowest_common_denominator): Update
for changes to lowest common denominator, and to m_entries_hash.
(completion_tracker::build_completion_result): Likewise.
* completer.h: Add 'unordered_map' include.
(completion_tracker::have_completions): Use m_entries_hash.
(completion_tracker::completion_set): New typedef.
(completion_tracker::recompute_lowest_common_denominator): Update
signature.
(completion_tracker::m_entries_vec): Delete.
(completion_tracker::m_entries_hash): Change type.
(completion_tracker::m_lowest_common_denominator): Change type.
(completion_tracker::m_lowest_common_denominator_valid): New
member variable.
(completion_tracker::m_lowest_common_denominator_max_length): New
member variable.
Change-Id: Iac5166189103d84bac0a4181324f38ca14227c47
---
gdb/ChangeLog | 26 ++++++++++++
gdb/completer.c | 129 ++++++++++++++++++++++++++++++++------------------------
gdb/completer.h | 58 ++++++++++++++++---------
3 files changed, 138 insertions(+), 75 deletions(-)
@@ -407,9 +407,10 @@ 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;
+ const char *lcd = m_lowest_common_denominator.get ();
if (strncmp_iw (word, lcd, strlen (lcd)) == 0)
{
@@ -1512,9 +1513,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);
+ /* Nothing. */
}
/* See completer.h. */
@@ -1522,25 +1521,23 @@ completion_tracker::completion_tracker ()
void
completion_tracker::discard_completions ()
{
- xfree (m_lowest_common_denominator);
m_lowest_common_denominator = NULL;
-
m_lowest_common_denominator_unique = false;
+ m_lowest_common_denominator_valid = false;
- m_entries_vec.clear ();
-
- htab_delete (m_entries_hash);
- m_entries_hash = htab_create_alloc (INITIAL_COMPLETION_HTAB_SIZE,
- htab_hash_string, streq_hash,
- NULL, xcalloc, xfree);
+ for (const auto &p : m_entries_hash)
+ {
+ xfree ((char *) p.first);
+ xfree ((char *) p.second);
+ }
+ m_entries_hash.clear ();
}
/* See completer.h. */
completion_tracker::~completion_tracker ()
{
- xfree (m_lowest_common_denominator);
- htab_delete (m_entries_hash);
+ discard_completions ();
}
/* See completer.h. */
@@ -1551,17 +1548,15 @@ completion_tracker::maybe_add_completion
completion_match_for_lcd *match_for_lcd,
const char *text, const char *word)
{
- void **slot;
-
if (max_completions == 0)
return false;
- if (htab_elements (m_entries_hash) >= max_completions)
+ if (m_entries_hash.size () >= max_completions)
return false;
- slot = htab_find_slot (m_entries_hash, name.get (), INSERT);
- if (*slot == HTAB_EMPTY_ENTRY)
+ if (m_entries_hash.find (name.get ()) == m_entries_hash.end ())
{
+ /* Not already in the hash. Add it. */
const char *match_for_lcd_str = NULL;
if (match_for_lcd != NULL)
@@ -1573,10 +1568,13 @@ 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 ());
+ auto p = std::make_pair (name.release (), lcd.release ());
+ m_entries_hash.insert (std::move (p));
- *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,35 +1980,47 @@ 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_lowest_common_denominator ()
{
- if (m_lowest_common_denominator == NULL)
- {
- /* 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 ();
- m_lowest_common_denominator_unique = true;
- }
- else
- {
- /* 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 ();
+ /* We've already done this. */
+ if (m_lowest_common_denominator_valid)
+ return;
- for (i = 0;
- (new_match[i] != '\0'
- && new_match[i] == m_lowest_common_denominator[i]);
- i++)
- ;
- if (m_lowest_common_denominator[i] != new_match[i])
+ /* Resize the storage to ensure we have enough space, the plus one gives
+ us space for the trailing null terminator we will include. */
+ char *tmp = (char *) xrealloc (m_lowest_common_denominator.release (),
+ m_lowest_common_denominator_max_length + 1);
+ m_lowest_common_denominator.reset (tmp);
+
+ for (const auto &p : m_entries_hash)
+ {
+ if (!m_lowest_common_denominator_valid)
+ {
+ strcpy (m_lowest_common_denominator.get (), p.second);
+ m_lowest_common_denominator_unique = true;
+ m_lowest_common_denominator_valid = true;
+ }
+ else
{
- m_lowest_common_denominator[i] = '\0';
- m_lowest_common_denominator_unique = false;
+ /* 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 = p.second;
+
+ for (i = 0;
+ (new_match[i] != '\0'
+ && new_match[i] == m_lowest_common_denominator.get ()[i]);
+ i++)
+ ;
+ if (m_lowest_common_denominator.get ()[i] != new_match[i])
+ {
+ m_lowest_common_denominator.get ()[i] = '\0';
+ m_lowest_common_denominator_unique = false;
+ }
}
}
+ m_lowest_common_denominator_valid = true;
}
/* See completer.h. */
@@ -2092,19 +2102,17 @@ completion_result
completion_tracker::build_completion_result (const char *text,
int start, int end)
{
- completion_list &list = m_entries_vec; /* The completions. */
-
- if (list.empty ())
+ if (m_entries_hash.empty ())
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 + m_entries_hash.size () + 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);
+ m_lowest_common_denominator.get ());
if (m_lowest_common_denominator_unique)
{
@@ -2128,13 +2136,22 @@ completion_tracker::build_completion_result (const char *text,
}
else
{
- int ix;
+ int ix = 0;
- for (ix = 0; ix < list.size (); ++ix)
- match_list[ix + 1] = list[ix].release ();
+ for (const auto &ptr : m_entries_hash)
+ {
+ match_list[ix + 1] = (char *) ptr.first;
+ xfree ((char *) ptr.second);
+ ix++;
+ }
match_list[ix + 1] = NULL;
- return completion_result (match_list, list.size (), false);
+ /* We must clear the hash here as ownership of all the entries is
+ being passed over to readline, and we don't want to try and free
+ these pointers when we ourselves are destroyed. */
+ size_t hash_size = m_entries_hash.size ();
+ m_entries_hash.clear ();
+ return completion_result (match_list, hash_size, false);
}
}
@@ -20,6 +20,8 @@
#include "gdbsupport/gdb_vecs.h"
#include "command.h"
+#include <unordered_map>
+
/* Types of functions in struct match_list_displayer. */
struct match_list_displayer;
@@ -389,7 +391,7 @@ public:
/* True if we have any completion match recorded. */
bool have_completions () const
- { return !m_entries_vec.empty (); }
+ { return !m_entries_hash.empty (); }
/* Discard the current completion match list and the current
LCD. */
@@ -403,6 +405,15 @@ public:
private:
+ /* A map of completions. The key is the completion, and the value is the
+ string to be used to compute the lowest common denominator. Both the
+ key and the value are owned by the completion_tracker class while
+ being held in this map, as such completion_tracker must free these
+ strings when finished with them, or pass ownership to someone else who
+ will free them. */
+ typedef std::unordered_map<const char *, const char *, std::hash<std::string>,
+ std::equal_to<std::string>> completion_set;
+
/* 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 +421,11 @@ 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 ();
/* Completion match outputs returned by the symbol name matching
routines (see symbol_name_matcher_ftype). These results are only
@@ -430,16 +434,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;
+ completion_set m_entries_hash;
/* If non-zero, then this is the quote char that needs to be
appended after completion (iff we have a unique completion). We
@@ -472,8 +473,16 @@ private:
bool m_suppress_append_ws = false;
/* Our idea of lowest common denominator to hand over to readline.
- See intro. */
- char *m_lowest_common_denominator = NULL;
+ 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::". */
+ gdb::unique_xmalloc_ptr<char> m_lowest_common_denominator = nullptr;
/* If true, the LCD is unique. I.e., all completions had the same
MATCH_FOR_LCD substring, even if the completions were different.
@@ -483,6 +492,17 @@ 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;
+
+ /* We can avoid multiple calls to xrealloc in
+ RECOMPUTE_LOWEST_COMMON_DENOMINATOR, we track the maximum possible
+ size of 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