[PATCHv2 2/3] gdb: Restructure the completion_tracker class
Luis Machado
luis.machado@linaro.org
Fri Apr 3 23:00:27 GMT 2020
Hi Andrew,
Just a heads-up that this has caused a regression for aarch64-linux in
gdb.base/completion.exp.
FAIL: gdb.base/completion.exp: complete 'info registers '
For some reason the completion code is printing "info registers pc"
twice. It may be a quirk in the target, but i thought I'd let you know
before i investigate this further, in case you have any ideas.
Luis
On 1/27/20 9:36 PM, Andrew Burgess wrote:
> 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
> ---
> gdb/ChangeLog | 34 ++++++++++
> gdb/completer.c | 195 +++++++++++++++++++++++++++++++++++++++++++++++---------
> gdb/completer.h | 41 +++++++-----
> 3 files changed, 222 insertions(+), 48 deletions(-)
>
> diff --git a/gdb/completer.c b/gdb/completer.c
> index 619fb8a0285..14c7a579970 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'
> @@ -2015,6 +2091,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)
> {
> @@ -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 703a5768d11..7bfe0d58142 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
>
More information about the Gdb-patches
mailing list