RFA/symtab: Let search_symbols find exact matches

RFA/symtab: Let search_symbols find exact matches

[Daniel Jacobowitz]

This patch renames search_symbols to search_symbols_aux, and lets it take an
argument that specified regex or exact (well, strcmp_iw) matching.  Then
search_symbols becomes a wrapper.

The new function is used by make_symbol_overload_list, which shaves 50% time
off of some tests in the C++ directory if your system libc has debugging
symbols; it removes the bogusity where all psymtabs were converted to
symtabs during overload resolution.  Whew.  This cuts memory for
namespace.exp from 70MB to 7MB, allowing some of my hardware to actually run
the test without crashing.

Hopefully at some point I can extend search_symbols_aux to also do prefix
matching and use it to speed up make_symbol_completion_list, but there are
some subtleties - like, in that context we don't need to read in psymbols. 
And the sorting requirements are different.

Symtab maintainers, is this OK?

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

2003-02-10  Daniel Jacobowitz  <drow@mvista.com>

	* symtab.c (enum sym_match_kind): New.
	(symbol_matches_kind, symbol_matches_pattern): New functions.
	(search_symbols_aux): Renamed from search_symbols.  Accept an
	enum sym_match_kind argument.  Use symbol_matches_kind and
	symbol_matches_pattern.  Move file_matches call out of the
	per-symbol loop.
	(search_symbols): New function, calling search_symbols_aux.
	(make_symbol_overload_list): Use search_symbols_aux.

Index: symtab.c
===================================================================
RCS file: /big/fsf/rsync/src-cvs/src/gdb/symtab.c,v
retrieving revision 1.87
diff -u -p -r1.87 symtab.c
--- symtab.c	4 Feb 2003 18:07:01 -0000	1.87
+++ symtab.c	10 Feb 2003 15:53:22 -0000
@@ -2787,8 +2787,77 @@ sort_search_symbols (struct symbol_searc
   return symp;
 }
 
-/* Search the symbol table for matches to the regular expression REGEXP,
-   returning the results in *MATCHES.
+/* Possible match styles for search_symbols_aux.  */
+
+enum sym_match_method {
+  sym_match_regex,
+  sym_match_exact
+};
+
+static inline int
+symbol_matches_kind (enum address_class aclass, namespace_enum kind)
+{
+  /* If the address class does not match the requested namespace, return 0.  */
+  switch (kind)
+    {
+    case VARIABLES_NAMESPACE:
+      if (aclass == LOC_TYPEDEF || aclass == LOC_BLOCK || aclass == LOC_CONST)
+	return 0;
+      break;
+
+    case FUNCTIONS_NAMESPACE:
+      if (aclass != LOC_BLOCK)
+	return 0;
+      break;
+
+    case TYPES_NAMESPACE:
+      if (aclass != LOC_TYPEDEF)
+	return 0;
+      break;
+
+    case METHODS_NAMESPACE:
+      if (aclass != LOC_BLOCK)
+	return 0;
+      break;
+
+    default:
+      internal_error (__FILE__, __LINE__,
+		      "Invalid kind passed to symbol_matches_pattern");
+    }
+
+  return 1;
+}
+
+static inline int
+symbol_matches_pattern (const char *sym_name, const char *sym_demangled_name,
+			const char *pattern, enum sym_match_method how)
+{
+  if (pattern == NULL)
+    return 1;
+
+  switch (how)
+    {
+    case sym_match_regex:
+      if (re_exec (sym_name)
+	  || (sym_demangled_name && re_exec (sym_demangled_name)))
+	return 1;
+      break;
+
+    case sym_match_exact:
+      if (strcmp_iw (sym_name, pattern) == 0
+	  || (sym_demangled_name
+	      && strcmp_iw (sym_demangled_name, pattern) == 0))
+	return 1;
+      break;
+    }
+
+  return 0;
+}
+
+/* Search the symbol table for matches to the pattern PATTERN,
+   returning the results in *MATCHES.  If HOW is sym_match_regex,
+   PATTERN is a regular expression; if HOW is sym_match_exact, PATTERN
+   is an exact string (almost: strcmp_iw is used).
 
    Only symbols of KIND are searched:
    FUNCTIONS_NAMESPACE - search all functions
@@ -2800,11 +2869,12 @@ sort_search_symbols (struct symbol_searc
    free_search_symbols should be called when *MATCHES is no longer needed.
 
    The results are sorted locally; each symtab's global and static blocks are
-   separately alphabetized.
- */
-void
-search_symbols (char *regexp, namespace_enum kind, int nfiles, char *files[],
-		struct symbol_search **matches)
+   separately alphabetized.  */
+
+static void
+search_symbols_aux (char *pattern, namespace_enum kind, int nfiles,
+		    char *files[], struct symbol_search **matches,
+		    enum sym_match_method how)
 {
   register struct symtab *s;
   register struct partial_symtab *ps;
@@ -2851,14 +2921,14 @@ search_symbols (char *regexp, namespace_
   sr = *matches = NULL;
   tail = NULL;
 
-  if (regexp != NULL)
+  if (pattern != NULL)
     {
       /* Make sure spacing is right for C++ operators.
          This is just a courtesy to make the matching less sensitive
          to how many spaces the user leaves between 'operator'
          and <TYPENAME> or <OPERATOR>. */
       char *opend;
-      char *opname = operator_chars (regexp, &opend);
+      char *opname = operator_chars (pattern, &opend);
       if (*opname)
 	{
 	  int fix = -1;		/* -1 means ok; otherwise number of spaces needed. */
@@ -2879,16 +2949,17 @@ search_symbols (char *regexp, namespace_
 	    {
 	      char *tmp = (char *) alloca (8 + fix + strlen (opname) + 1);
 	      sprintf (tmp, "operator%.*s%s", fix, " ", opname);
-	      regexp = tmp;
+	      pattern = tmp;
 	    }
 	}
 
-      if (0 != (val = re_comp (regexp)))
-	error ("Invalid regexp (%s): %s", val, regexp);
+      if (how == sym_match_regex)
+	if (0 != (val = re_comp (pattern)))
+	  error ("Invalid regexp (%s): %s", val, pattern);
     }
 
   /* Search through the partial symtabs *first* for all symbols
-     matching the regexp.  That way we don't have to reproduce all of
+     matching the pattern.  That way we don't have to reproduce all of
      the machinery below. */
 
   ALL_PSYMTABS (objfile, ps)
@@ -2899,6 +2970,9 @@ search_symbols (char *regexp, namespace_
     if (ps->readin)
       continue;
 
+    if (! file_matches (ps->filename, files, nfiles))
+      continue;
+
     gbound = objfile->global_psymbols.list + ps->globals_offset + ps->n_global_syms;
     sbound = objfile->static_psymbols.list + ps->statics_offset + ps->n_static_syms;
     bound = gbound;
@@ -2925,13 +2999,10 @@ search_symbols (char *regexp, namespace_
 
 	    /* If it would match (logic taken from loop below)
 	       load the file and go on to the next one */
-	    if (file_matches (ps->filename, files, nfiles)
-		&& ((regexp == NULL || SYMBOL_MATCHES_REGEXP (*psym))
-		    && ((kind == VARIABLES_NAMESPACE && SYMBOL_CLASS (*psym) != LOC_TYPEDEF
-			 && SYMBOL_CLASS (*psym) != LOC_BLOCK)
-			|| (kind == FUNCTIONS_NAMESPACE && SYMBOL_CLASS (*psym) == LOC_BLOCK)
-			|| (kind == TYPES_NAMESPACE && SYMBOL_CLASS (*psym) == LOC_TYPEDEF)
-			|| (kind == METHODS_NAMESPACE && SYMBOL_CLASS (*psym) == LOC_BLOCK))))
+	    if (symbol_matches_kind (SYMBOL_CLASS (*psym), kind)
+		&& symbol_matches_pattern (SYMBOL_NAME (*psym),
+					   SYMBOL_DEMANGLED_NAME (*psym),
+					   pattern, how))
 	      {
 		PSYMTAB_TO_SYMTAB (ps);
 		keep_going = 0;
@@ -2963,7 +3034,9 @@ search_symbols (char *regexp, namespace_
 	    MSYMBOL_TYPE (msymbol) == ourtype3 ||
 	    MSYMBOL_TYPE (msymbol) == ourtype4)
 	  {
-	    if (regexp == NULL || SYMBOL_MATCHES_REGEXP (msymbol))
+	    if (symbol_matches_pattern (SYMBOL_NAME (msymbol),
+					SYMBOL_DEMANGLED_NAME (msymbol),
+					pattern, how))
 	      {
 		if (0 == find_pc_symtab (SYMBOL_VALUE_ADDRESS (msymbol)))
 		  {
@@ -3000,6 +3073,9 @@ search_symbols (char *regexp, namespace_
 
   ALL_SYMTABS (objfile, s)
   {
+    if (! file_matches (s->filename, files, nfiles))
+      continue;
+
     bv = BLOCKVECTOR (s);
     /* Often many files share a blockvector.
        Scan each blockvector only once so that
@@ -3015,14 +3091,10 @@ search_symbols (char *regexp, namespace_
 	  ALL_BLOCK_SYMBOLS (b, j, sym)
 	    {
 	      QUIT;
-	      if (file_matches (s->filename, files, nfiles)
-		  && ((regexp == NULL || SYMBOL_MATCHES_REGEXP (sym))
-		      && ((kind == VARIABLES_NAMESPACE && SYMBOL_CLASS (sym) != LOC_TYPEDEF
-			   && SYMBOL_CLASS (sym) != LOC_BLOCK
-			   && SYMBOL_CLASS (sym) != LOC_CONST)
-			  || (kind == FUNCTIONS_NAMESPACE && SYMBOL_CLASS (sym) == LOC_BLOCK)
-			  || (kind == TYPES_NAMESPACE && SYMBOL_CLASS (sym) == LOC_TYPEDEF)
-			  || (kind == METHODS_NAMESPACE && SYMBOL_CLASS (sym) == LOC_BLOCK))))
+	      if (symbol_matches_kind (SYMBOL_CLASS (sym), kind)
+		  && symbol_matches_pattern (SYMBOL_NAME (sym),
+					     SYMBOL_DEMANGLED_NAME (sym),
+					     pattern, how))
 		{
 		  /* match */
 		  psr = (struct symbol_search *) xmalloc (sizeof (struct symbol_search));
@@ -3070,7 +3142,9 @@ search_symbols (char *regexp, namespace_
 	    MSYMBOL_TYPE (msymbol) == ourtype3 ||
 	    MSYMBOL_TYPE (msymbol) == ourtype4)
 	  {
-	    if (regexp == NULL || SYMBOL_MATCHES_REGEXP (msymbol))
+	    if (symbol_matches_pattern (SYMBOL_NAME (msymbol),
+					SYMBOL_DEMANGLED_NAME (msymbol),
+					pattern, how))
 	      {
 		/* Functions:  Look up by address. */
 		if (kind != FUNCTIONS_NAMESPACE ||
@@ -3108,6 +3182,16 @@ search_symbols (char *regexp, namespace_
     discard_cleanups (old_chain);
 }
 
+/* A wrapper for search_symbols_aux, above, which treats PATTERN as a
+   regular expression.  */
+
+void
+search_symbols (char *pattern, namespace_enum kind, int nfiles,
+		char *files[], struct symbol_search **matches)
+{
+  search_symbols_aux (pattern, kind, nfiles, files, matches, sym_match_regex);
+}
+
 /* Helper function for symtab_symbol_info, this function uses
    the data returned from search_symbols() to print information
    regarding the match to gdb_stdout.
@@ -4005,6 +4089,8 @@ overload_list_add_symbol (struct symbol 
 struct symbol **
 make_symbol_overload_list (struct symbol *fsym)
 {
+  struct symbol_search *matches, *matchp;
+
   register struct symbol *sym;
   register struct symtab *s;
   register struct partial_symtab *ps;
@@ -4035,88 +4121,20 @@ make_symbol_overload_list (struct symbol
   sym_return_val = (struct symbol **) xmalloc ((sym_return_val_size + 1) * sizeof (struct symbol *));
   sym_return_val[0] = NULL;
 
-  /* Look through the partial symtabs for all symbols which begin
-     by matching OLOAD_NAME.  Make sure we read that symbol table in. */
-
-  ALL_PSYMTABS (objfile, ps)
-  {
-    struct partial_symbol **psym;
+  search_symbols_aux (oload_name, FUNCTIONS_NAMESPACE, 0, NULL, &matches,
+		      sym_match_exact);
 
-    /* If the psymtab's been read in we'll get it when we search
-       through the blockvector.  */
-    if (ps->readin)
-      continue;
-
-    for (psym = objfile->global_psymbols.list + ps->globals_offset;
-	 psym < (objfile->global_psymbols.list + ps->globals_offset
-		 + ps->n_global_syms);
-	 psym++)
-      {
-	/* If interrupted, then quit. */
-	QUIT;
-        /* This will cause the symbol table to be read if it has not yet been */
-        s = PSYMTAB_TO_SYMTAB (ps);
-      }
-
-    for (psym = objfile->static_psymbols.list + ps->statics_offset;
-	 psym < (objfile->static_psymbols.list + ps->statics_offset
-		 + ps->n_static_syms);
-	 psym++)
-      {
-	QUIT;
-        /* This will cause the symbol table to be read if it has not yet been */
-        s = PSYMTAB_TO_SYMTAB (ps);
-      }
-  }
-
-  /* Search upwards from currently selected frame (so that we can
-     complete on local vars.  */
-
-  for (b = get_selected_block (0); b != NULL; b = BLOCK_SUPERBLOCK (b))
+  matchp = matches;
+  while (matchp)
     {
-      if (!BLOCK_SUPERBLOCK (b))
-	{
-	  surrounding_static_block = b;		/* For elimination of dups */
-	}
-
-      /* Also catch fields of types defined in this places which match our
-         text string.  Only complete on types visible from current context. */
-
-      ALL_BLOCK_SYMBOLS (b, i, sym)
-	{
-	  overload_list_add_symbol (sym, oload_name);
-	}
+      if (matchp->symbol)
+	overload_list_add_symbol (matchp->symbol, oload_name);
+      matchp = matchp->next;
     }
 
-  /* Go through the symtabs and check the externs and statics for
-     symbols which match.  */
-
-  ALL_SYMTABS (objfile, s)
-  {
-    QUIT;
-    b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
-    ALL_BLOCK_SYMBOLS (b, i, sym)
-      {
-	overload_list_add_symbol (sym, oload_name);
-      }
-  }
-
-  ALL_SYMTABS (objfile, s)
-  {
-    QUIT;
-    b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
-    /* Don't do this block twice.  */
-    if (b == surrounding_static_block)
-      continue;
-    ALL_BLOCK_SYMBOLS (b, i, sym)
-      {
-	overload_list_add_symbol (sym, oload_name);
-      }
-  }
-
   xfree (oload_name);
-
-  return (sym_return_val);
+  free_search_symbols (matches);
+  return sym_return_val;
 }
 
 /* End of overload resolution functions */

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On Mon, 10 Feb 2003 11:01:07 -0500, Daniel Jacobowitz <drow@mvista.com> said:

> This patch renames search_symbols to search_symbols_aux, and lets it
> take an argument that specified regex or exact (well, strcmp_iw)
> matching.  Then search_symbols becomes a wrapper.

> The new function is used by make_symbol_overload_list, which shaves
> 50% time off of some tests in the C++ directory if your system libc
> has debugging symbols; it removes the bogusity where all psymtabs
> were converted to symtabs during overload resolution.  Whew.  This
> cuts memory for namespace.exp from 70MB to 7MB, allowing some of my
> hardware to actually run the test without crashing.

I love combining functions, but your patch makes me a bit nervous:
search_symbols and make_symbol_overload_list are fairly different
beasts.  If all you want to do is get rid of the aforementioned
bogosity, how about the much more modest patch that I've included at
the end of this message?

Benefits:

* It's more or less the minimal patch necessary to avoid converting
  unnecessary symtabs.

* It should be faster: it uses the fact that global psymbols are
  sorted.

Drawbacks:

* I'm to busy to spend too much time today thinking about whether or
  not lookup_partial_symbol really works well enough for this patch to
  work.  It certainly depends on partial symbols being demangled, but
  they are now.  My guess is that lookup_partial_symbol still doesn't
  work quite right (both because of improper use of
  SYMBOL_SOURCE_NAME, and because of improper use of strcmp instead of
  strcmp_iw).  The former shouldn't be a big deal; the latter might be
  a big deal in some situations but probably shouldn't affect
  lookup_partial_symbol (I _think_).  The correct fix there is to fix
  lookup_partial_symbol, though, rather than avoiding its use.  (I
  have run the patch through the testsuite; it passes, but that means
  almost nothing, given how little the testsuite exercises partial
  symbols.)

Could be either:

* If you really want some of the extra stuff that search_symbols does
  and that make_symbol_overload_list doesn't (e.g. look at minimal
  symbols), then of course your patch is a better idea.  But if you
  don't, then probably you should avoid using search_symbols.

Anyways, give it a run on your platform to see if it works.  Compared
to unpatched GDB, I'm getting a 3x memory improvement and a 2x speed
improvement when running namespace.exp.

(If anybody else out there wants a laugh, just try to figure out what
the part of lookup_partial_symbols that this patch removes actually
does.  It's rather different from what the comment claims...)

David Carlton
carlton@math.stanford.edu

2003-02-10  David Carlton  <carlton@math.stanford.edu>

	* symtab.c (make_symbol_overload_list): Only read in partial
	symtabs containing a matching partial symbol.

Index: symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.87
diff -u -p -r1.87 symtab.c
--- symtab.c	4 Feb 2003 18:07:01 -0000	1.87
+++ symtab.c	10 Feb 2003 19:35:36 -0000
@@ -4035,8 +4022,8 @@ make_symbol_overload_list (struct symbol
   sym_return_val = (struct symbol **) xmalloc ((sym_return_val_size + 1) * sizeof (struct symbol *));
   sym_return_val[0] = NULL;
 
-  /* Look through the partial symtabs for all symbols which begin
-     by matching OLOAD_NAME.  Make sure we read that symbol table in. */
+  /* Read in all partial symtabs containing a partial symbol named
+     OLOAD_NAME.  */
 
   ALL_PSYMTABS (objfile, ps)
   {
@@ -4047,26 +4034,9 @@ make_symbol_overload_list (struct symbol
     if (ps->readin)
       continue;
 
-    for (psym = objfile->global_psymbols.list + ps->globals_offset;
-	 psym < (objfile->global_psymbols.list + ps->globals_offset
-		 + ps->n_global_syms);
-	 psym++)
-      {
-	/* If interrupted, then quit. */
-	QUIT;
-        /* This will cause the symbol table to be read if it has not yet been */
-        s = PSYMTAB_TO_SYMTAB (ps);
-      }
-
-    for (psym = objfile->static_psymbols.list + ps->statics_offset;
-	 psym < (objfile->static_psymbols.list + ps->statics_offset
-		 + ps->n_static_syms);
-	 psym++)
-      {
-	QUIT;
-        /* This will cause the symbol table to be read if it has not yet been */
-        s = PSYMTAB_TO_SYMTAB (ps);
-      }
+    if ((lookup_partial_symbol (ps, oload_name, 1, VAR_NAMESPACE) != NULL)
+	|| (lookup_partial_symbol (ps, oload_name, 0, VAR_NAMESPACE) != NULL))
+      PSYMTAB_TO_SYMTAB (ps);
   }
 
   /* Search upwards from currently selected frame (so that we can

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On 10 Feb 2003 12:10:50 -0800, David Carlton <carlton@math.Stanford.EDU> said:

>   strcmp_iw).  The former shouldn't be a big deal; the latter might be
>   a big deal in some situations but probably shouldn't affect
>   lookup_partial_symbol (I _think_).

Should say "probably shouldn't affect make_symbol_overload_list (I
_think_)."

David Carlton
carlton@math.stanford.edu

Re: RFA/symtab: Let search_symbols find exact matches

[Daniel Jacobowitz]

On Mon, Feb 10, 2003 at 12:10:50PM -0800, David Carlton wrote:
> On Mon, 10 Feb 2003 11:01:07 -0500, Daniel Jacobowitz <drow@mvista.com> said:
> 
> > This patch renames search_symbols to search_symbols_aux, and lets it
> > take an argument that specified regex or exact (well, strcmp_iw)
> > matching.  Then search_symbols becomes a wrapper.
> 
> > The new function is used by make_symbol_overload_list, which shaves
> > 50% time off of some tests in the C++ directory if your system libc
> > has debugging symbols; it removes the bogusity where all psymtabs
> > were converted to symtabs during overload resolution.  Whew.  This
> > cuts memory for namespace.exp from 70MB to 7MB, allowing some of my
> > hardware to actually run the test without crashing.
> 
> I love combining functions, but your patch makes me a bit nervous:
> search_symbols and make_symbol_overload_list are fairly different
> beasts.  If all you want to do is get rid of the aforementioned
> bogosity, how about the much more modest patch that I've included at
> the end of this message?
> 
> Benefits:
> 
> * It's more or less the minimal patch necessary to avoid converting
>   unnecessary symtabs.
> 
> * It should be faster: it uses the fact that global psymbols are
>   sorted.

[Bah, we should hash them.  We hash everything else.]

> Drawbacks:
> 
> * I'm to busy to spend too much time today thinking about whether or
>   not lookup_partial_symbol really works well enough for this patch to
>   work.  It certainly depends on partial symbols being demangled, but
>   they are now.  My guess is that lookup_partial_symbol still doesn't
>   work quite right (both because of improper use of
>   SYMBOL_SOURCE_NAME, and because of improper use of strcmp instead of
>   strcmp_iw).  The former shouldn't be a big deal; the latter might be
>   a big deal in some situations but probably shouldn't affect
>   lookup_partial_symbol (I _think_).  The correct fix there is to fix
>   lookup_partial_symbol, though, rather than avoiding its use.  (I
>   have run the patch through the testsuite; it passes, but that means
>   almost nothing, given how little the testsuite exercises partial
>   symbols.)
> 
> Could be either:
> 
> * If you really want some of the extra stuff that search_symbols does
>   and that make_symbol_overload_list doesn't (e.g. look at minimal
>   symbols), then of course your patch is a better idea.  But if you
>   don't, then probably you should avoid using search_symbols.
> 
> Anyways, give it a run on your platform to see if it works.  Compared
> to unpatched GDB, I'm getting a 3x memory improvement and a 2x speed
> improvement when running namespace.exp.
> 
> (If anybody else out there wants a laugh, just try to figure out what
> the part of lookup_partial_symbols that this patch removes actually
> does.  It's rather different from what the comment claims...)

There are like a million ways in GDB to find a list of symbols.  Me, I
think that's a recipe for suffering.  They're all subtly different.  I
want the same set of symbols considered for overload resolution and tab
completion, and there's no reason that this should be different from
the results of "break".  I intend some day to condense them all.

I imagine your patch will work; I'd still rather centralize the logic. 
I'm open to other opinions, though.

You had a good point about the sorted-list thing, since we really only
want "does at least one partial symbol in this psymtab match".  That
can be done as a follow-up patch to search_symbols_aux.  Really doing
this properly requires symbol functions which can return lists, and
we'll have that someday.  Then the logic would look like:
  ALL_SYMTABS
    get all matching functions in this symtab
  ALL_PSYMTABS
    if readin continue
    find a matching function in this psymtab
    if there is one
      read in
      get all matching functions in the new symtab

--  
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On Mon, 10 Feb 2003 15:25:06 -0500, Daniel Jacobowitz <drow@mvista.com> said:

> There are like a million ways in GDB to find a list of symbols.  Me,
> I think that's a recipe for suffering.  They're all subtly
> different.  I want the same set of symbols considered for overload
> resolution and tab completion, and there's no reason that this
> should be different from the results of "break".  I intend some day
> to condense them all.

Yup.  I'm just nervous about this for a couple of reasons:

1) If functions try to handle too many situations, they get ugly; I'm
   still in recovery from trying to deal with find_overload_match, for
   example.  On the other hand, duplicated code is ugly, too.  And
   we're programming in C, which limits our options.  I don't know how
   to best resolve this tension in this particular case; I doubt I'll
   be thrilled with whatever outcome we end up with.  (Unless cleaning
   this mess takes long enough that we end up porting GDB to C++
   first, though even that would only go so far in this instance.)

2) I don't understand search_symbols yet; it's a lot messier than
   make_symbol_overload_list.  Based on some reading of the code and
   on my experience with cleaning up lookup_symbol_aux, I expect that
   much of that messiness doesn't need to be there.  I'd be happier if
   somebody (you, me, some other foolhardy person who wants to be
   initiated into the mysteries of GDB's symbol-management "logic")
   cleaned up search_symbols first.  That way, we could have an
   informed opinion about the differences between search_symbols and
   make_symbol_overload_list before merging them.  (And I suspect that
   the differences would shrink over the course of that cleanup,
   making the merge easier.)

But, of course, this is just a reflection of my programming style;
different people could reasonably come to a different conclusion on
this matter.

David Carlton
carlton@math.stanford.edu

Re: RFA/symtab: Let search_symbols find exact matches

[Daniel Jacobowitz]

On Mon, Feb 10, 2003 at 01:15:21PM -0800, David Carlton wrote:
> On Mon, 10 Feb 2003 15:25:06 -0500, Daniel Jacobowitz <drow@mvista.com> said:
> 
> > There are like a million ways in GDB to find a list of symbols.  Me,
> > I think that's a recipe for suffering.  They're all subtly
> > different.  I want the same set of symbols considered for overload
> > resolution and tab completion, and there's no reason that this
> > should be different from the results of "break".  I intend some day
> > to condense them all.
> 
> Yup.  I'm just nervous about this for a couple of reasons:
> 
> 1) If functions try to handle too many situations, they get ugly; I'm
>    still in recovery from trying to deal with find_overload_match, for
>    example.  On the other hand, duplicated code is ugly, too.  And
>    we're programming in C, which limits our options.  I don't know how
>    to best resolve this tension in this particular case; I doubt I'll
>    be thrilled with whatever outcome we end up with.  (Unless cleaning
>    this mess takes long enough that we end up porting GDB to C++
>    first, though even that would only go so far in this instance.)

I am seriously considering raising the C++ issue again.

> 2) I don't understand search_symbols yet; it's a lot messier than
>    make_symbol_overload_list.  Based on some reading of the code and
>    on my experience with cleaning up lookup_symbol_aux, I expect that
>    much of that messiness doesn't need to be there.  I'd be happier if
>    somebody (you, me, some other foolhardy person who wants to be
>    initiated into the mysteries of GDB's symbol-management "logic")
>    cleaned up search_symbols first.  That way, we could have an
>    informed opinion about the differences between search_symbols and
>    make_symbol_overload_list before merging them.  (And I suspect that
>    the differences would shrink over the course of that cleanup,
>    making the merge easier.)

Some of that messiness definitely is going to go away, it's on my hit
list.  But I don't feel like doing it right this moment :)

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On Mon, 10 Feb 2003 11:01:07 -0500, Daniel Jacobowitz <drow@mvista.com> said:

> This patch renames search_symbols to search_symbols_aux, and lets it take an
> argument that specified regex or exact (well, strcmp_iw) matching.  Then
> search_symbols becomes a wrapper.

> The new function is used by make_symbol_overload_list, which shaves 50% time
> off of some tests in the C++ directory if your system libc has debugging
> symbols; it removes the bogusity where all psymtabs were converted to
> symtabs during overload resolution.  Whew.  This cuts memory for
> namespace.exp from 70MB to 7MB, allowing some of my hardware to actually run
> the test without crashing.

Here's take two on my comments on this.  First, I should say that I
totally agree that the aforementioned bogusity in
make_symbol_overload_list should go; as discussed in
<http://sources.redhat.com/ml/gdb-patches/2003-02/msg00261.html>,
though, there are ways of doing that that involve much less drastic
changes.

So the question is: do search_symbols and make_symbol_overload_list
have enough of a common core such that extracting that common core
into a single function would clean up the code, reducing maintenance
overhead, or would that common code be artificial, increasing
maintenance overhead?

Here's an analysis of the two functions.  It may well be incorrect; I
understand GDB's symbol mechanisms pretty well (better than I'd like,
I sometimes think...), and I understand make_symbol_overload_list
pretty well, but I haven't spent too much time with search_symbols
yet.


Loosely speaking, this is what search_symbols does:

1) If the regexp is non-NULL, it cleans it up a bit and compiles it.

2) It looks at every partial symtab; in each one, it looks at every
   partial symbol until it finds one that matches, at which point it
   reads in that partial symtab.

3) It (usually) looks at every single minimal symbol, to see if thre's
   a corresponding symbol.

4) It then looks at every single global and static symbol, to find the
   ones that match.

5) If there were minimal symbols without corresponding symbols, then
   it looks at every single minimal symbol again.

Here, on the other hand, is what make_symbol_overload_list does.

1) It looks at every partial symtab, and reads them all in (in an
   amusingly verbose fashion).  (My e-mail referenced above contains a
   patch fixing this.)

2) It looks at local variables, to find the ones that match.

3) It looks at every single global and static symbol, to find the ones
   that match.


So: what's the same, what's different.

Things that only search_symbols does:

* It does some regexp-related stuff at the beginning.

* It looks at every single minimal symbol at least once, possibly
  twice.

Things that only make_symbol_overload_list does:

* It looks at local variables.

Things that both functions do:

* Determine which psymtabs to read in.

* Look at every single global and static symbol, to find the ones that
  match.


So already I'm suspicious: those differences seem potentially
significant to me.  Some of them may well be due to accidents in the
way the two functions were written (which would be exactly the sort of
accidents that patches like Daniel's would help prevent!); but I think
that, at the least, we need more analysis to see if that's the case.
When doing this sort of refactoring, I think the proper order is to
first minimize the differences and only then to combine them.
(Shrinking the functions first will help, too: see below.)

But even the similarities aren't as close as they seem.  In both
cases, make_symbol_overload_list can potentially use a much faster
algorithm than search_symbols can, one that avoids looking at the vast
majority of partial or regular symbols.  For the psymtab case, it can
just do one call to lookup_partial_symbol per psymtab, rather than
look at (almost) every partial symbol.  For the symbols, all the
matching symbols will be inside the same hash bucket, so we could
conceivably just look in one bucket per symtab (well, two, one for the
globals and one for the statics), instead of looking at every symbol.
(We don't currently have an appropriate iterator to do that; I do have
one in my branch, that I plan to try to move to mainline in a few
weeks.)


So.  I like the basic idea of combining the functions as a longer-term
goal, but I'm pretty sure it's not a good idea right now.  I think a
better thing to do would be to get a good handle on the difference
between search_symbol and make_symbol_overload_list.  (And
make_symbol_completion_list: it may well be easier to combine
make_symbol_overload_list and make_symbol_completion_list as a first
step.)

One possible concrete recommendation as a step towards this
refactoring would be to extract the body of search_symbol into 5
separate functions along the lines of my analysis above, to extract
the body of make_symbol_overload_list into 3 separate functions along
the lines of my analysis above, and similarly with
make_symbol_completion_list.  (This is like what I did with
lookup_symbol_aux.)  That will enable us to do two things:

* By looking at the resulting much shorter versions of those
  functions, it'll be much clearer what each one does in broad terms.
  We can then think about whether the differences between them are
  important or not.

* When an extracted function from, say, make_symbol_overload_list is
  playing a similar role to an extracted function from, say,
  make_symbol_completion_list, then examine those functions to see if
  they can be profitably unified into a single function.

That may sound like a lot of work, but having gone through it a few
times, it's really not so bad.  And it's a great way to understand and
clean up functions.  It doesn't interact well with GDB's approval
process, though; I have some ideas about that, too, but I don't think
this is the place for them.

David Carlton
carlton@math.stanford.edu

Re: RFA/symtab: Let search_symbols find exact matches

[Daniel Jacobowitz]

On Thu, Feb 20, 2003 at 02:41:18PM -0800, David Carlton wrote:
> On Mon, 10 Feb 2003 11:01:07 -0500, Daniel Jacobowitz <drow@mvista.com> said:
> 
> > This patch renames search_symbols to search_symbols_aux, and lets it take an
> > argument that specified regex or exact (well, strcmp_iw) matching.  Then
> > search_symbols becomes a wrapper.
> 
> > The new function is used by make_symbol_overload_list, which shaves 50% time
> > off of some tests in the C++ directory if your system libc has debugging
> > symbols; it removes the bogusity where all psymtabs were converted to
> > symtabs during overload resolution.  Whew.  This cuts memory for
> > namespace.exp from 70MB to 7MB, allowing some of my hardware to actually run
> > the test without crashing.
> 
> Here's take two on my comments on this.  First, I should say that I
> totally agree that the aforementioned bogusity in
> make_symbol_overload_list should go; as discussed in
> <http://sources.redhat.com/ml/gdb-patches/2003-02/msg00261.html>,
> though, there are ways of doing that that involve much less drastic
> changes.

Good enough for me.  This patch is withdrawn.  David, are you convinced
that lookup_partial_symbol is close enough to what we want for the
patch above?  You expressed some concerns earlier.  If you're happy
with it, I'll approve the patch.


-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: RFA/symtab: Let search_symbols find exact matches

[Elena Zannoni]

Daniel Jacobowitz writes:
 > On Thu, Feb 20, 2003 at 02:41:18PM -0800, David Carlton wrote:
 > > On Mon, 10 Feb 2003 11:01:07 -0500, Daniel Jacobowitz <drow@mvista.com> said:
 > > 
 > > > This patch renames search_symbols to search_symbols_aux, and lets it take an
 > > > argument that specified regex or exact (well, strcmp_iw) matching.  Then
 > > > search_symbols becomes a wrapper.
 > > 
 > > > The new function is used by make_symbol_overload_list, which shaves 50% time
 > > > off of some tests in the C++ directory if your system libc has debugging
 > > > symbols; it removes the bogusity where all psymtabs were converted to
 > > > symtabs during overload resolution.  Whew.  This cuts memory for
 > > > namespace.exp from 70MB to 7MB, allowing some of my hardware to actually run
 > > > the test without crashing.
 > > 
 > > Here's take two on my comments on this.  First, I should say that I
 > > totally agree that the aforementioned bogusity in
 > > make_symbol_overload_list should go; as discussed in
 > > <http://sources.redhat.com/ml/gdb-patches/2003-02/msg00261.html>,
 > > though, there are ways of doing that that involve much less drastic
 > > changes.
 > 
 > Good enough for me.  This patch is withdrawn.  David, are you convinced
 > that lookup_partial_symbol is close enough to what we want for the
 > patch above?  You expressed some concerns earlier.  If you're happy
 > with it, I'll approve the patch.
 > 

As a matter of fact, could these c++ specific functions be moved to
cp-support.c? So you guys are free to do whatever you want with them.

If the patch is withdrawn please close the pr.


 > 
 > -- 
 > Daniel Jacobowitz
 > MontaVista Software                         Debian GNU/Linux Developer

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On Fri, 21 Feb 2003 09:09:25 -0500, Daniel Jacobowitz <drow@mvista.com> said:

> David, are you convinced that lookup_partial_symbol is close enough
> to what we want for the patch above?

It's close enough; on the other hand, since I'll submit a patch today
or Monday to get lookup_partial_symbol even closer to what we want, we
might as well wait until after that patch goes in before applying my
make_symbol_overload_list patch.  I'll apply them both once that gets
fixed up.

David Carlton
carlton@math.stanford.edu

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On Fri, 21 Feb 2003 10:31:53 -0500, Elena Zannoni <ezannoni@redhat.com> said:

> As a matter of fact, could these c++ specific functions be moved to
> cp-support.c? So you guys are free to do whatever you want with
> them.

Makes sense to me; honestly, I don't care too much one way or another,
but symtab.c is large while cp-support.c is small, so it might as well
go in the latter. :-)

(I think that I have some useful thoughts about how to tweak GDB's
maintenance process to work around these sorts of issues, but I don't
think I want to start a thread about that on a Friday; Monday,
though.)

David Carlton
carlton@math.stanford.edu

Re: RFA/symtab: Let search_symbols find exact matches

[Elena Zannoni]

David Carlton writes:
 > On Mon, 10 Feb 2003 11:01:07 -0500, Daniel Jacobowitz <drow@mvista.com> said:
 > 
 > > This patch renames search_symbols to search_symbols_aux, and lets it take an
 > > argument that specified regex or exact (well, strcmp_iw) matching.  Then
 > > search_symbols becomes a wrapper.
 > 
 > > The new function is used by make_symbol_overload_list, which shaves 50% time
 > > off of some tests in the C++ directory if your system libc has debugging
 > > symbols; it removes the bogusity where all psymtabs were converted to
 > > symtabs during overload resolution.  Whew.  This cuts memory for
 > > namespace.exp from 70MB to 7MB, allowing some of my hardware to actually run
 > > the test without crashing.
 > 
 > Here's take two on my comments on this.  First, I should say that I
 > totally agree that the aforementioned bogusity in
 > make_symbol_overload_list should go; as discussed in
 > <http://sources.redhat.com/ml/gdb-patches/2003-02/msg00261.html>,
 > though, there are ways of doing that that involve much less drastic
 > changes.
 > 
 > So the question is: do search_symbols and make_symbol_overload_list
 > have enough of a common core such that extracting that common core
 > into a single function would clean up the code, reducing maintenance
 > overhead, or would that common code be artificial, increasing
 > maintenance overhead?
 > 
 > Here's an analysis of the two functions.  It may well be incorrect; I
 > understand GDB's symbol mechanisms pretty well (better than I'd like,
 > I sometimes think...), and I understand make_symbol_overload_list
 > pretty well, but I haven't spent too much time with search_symbols
 > yet.
 > 

<archeology>

BTW, make_symbol_overload_list came in via the HP merge.  Roughly at
the same time (in parallel) the search_symbols function was
introduced. I.e. HP didn't have search_symbols available.  Actually
the same functionality of search_symbol was provided by another
function called list_symbols. I suspect that list_symbols was broken
down into several functions, to be used in gdbtk, when search_symbols
was introduced.

</archeology>

So, if you change search_symbols we should make sure gdbtk still
works.

I agree it could be a good idea to clean up search_symbols, but keep
the history above in mind.

elena


 > 
 > Loosely speaking, this is what search_symbols does:
 > 
 > 1) If the regexp is non-NULL, it cleans it up a bit and compiles it.
 > 
 > 2) It looks at every partial symtab; in each one, it looks at every
 >    partial symbol until it finds one that matches, at which point it
 >    reads in that partial symtab.
 > 
 > 3) It (usually) looks at every single minimal symbol, to see if thre's
 >    a corresponding symbol.
 > 
 > 4) It then looks at every single global and static symbol, to find the
 >    ones that match.
 > 
 > 5) If there were minimal symbols without corresponding symbols, then
 >    it looks at every single minimal symbol again.
 > 
 > Here, on the other hand, is what make_symbol_overload_list does.
 > 
 > 1) It looks at every partial symtab, and reads them all in (in an
 >    amusingly verbose fashion).  (My e-mail referenced above contains a
 >    patch fixing this.)
 > 
 > 2) It looks at local variables, to find the ones that match.
 > 
 > 3) It looks at every single global and static symbol, to find the ones
 >    that match.
 > 
 > 
 > So: what's the same, what's different.
 > 
 > Things that only search_symbols does:
 > 
 > * It does some regexp-related stuff at the beginning.
 > 
 > * It looks at every single minimal symbol at least once, possibly
 >   twice.
 > 
 > Things that only make_symbol_overload_list does:
 > 
 > * It looks at local variables.
 > 
 > Things that both functions do:
 > 
 > * Determine which psymtabs to read in.
 > 
 > * Look at every single global and static symbol, to find the ones that
 >   match.
 > 
 > 
 > So already I'm suspicious: those differences seem potentially
 > significant to me.  Some of them may well be due to accidents in the
 > way the two functions were written (which would be exactly the sort of
 > accidents that patches like Daniel's would help prevent!); but I think
 > that, at the least, we need more analysis to see if that's the case.
 > When doing this sort of refactoring, I think the proper order is to
 > first minimize the differences and only then to combine them.
 > (Shrinking the functions first will help, too: see below.)
 > 
 > But even the similarities aren't as close as they seem.  In both
 > cases, make_symbol_overload_list can potentially use a much faster
 > algorithm than search_symbols can, one that avoids looking at the vast
 > majority of partial or regular symbols.  For the psymtab case, it can
 > just do one call to lookup_partial_symbol per psymtab, rather than
 > look at (almost) every partial symbol.  For the symbols, all the
 > matching symbols will be inside the same hash bucket, so we could
 > conceivably just look in one bucket per symtab (well, two, one for the
 > globals and one for the statics), instead of looking at every symbol.
 > (We don't currently have an appropriate iterator to do that; I do have
 > one in my branch, that I plan to try to move to mainline in a few
 > weeks.)
 > 
 > 
 > So.  I like the basic idea of combining the functions as a longer-term
 > goal, but I'm pretty sure it's not a good idea right now.  I think a
 > better thing to do would be to get a good handle on the difference
 > between search_symbol and make_symbol_overload_list.  (And
 > make_symbol_completion_list: it may well be easier to combine
 > make_symbol_overload_list and make_symbol_completion_list as a first
 > step.)
 > 
 > One possible concrete recommendation as a step towards this
 > refactoring would be to extract the body of search_symbol into 5
 > separate functions along the lines of my analysis above, to extract
 > the body of make_symbol_overload_list into 3 separate functions along
 > the lines of my analysis above, and similarly with
 > make_symbol_completion_list.  (This is like what I did with
 > lookup_symbol_aux.)  That will enable us to do two things:
 > 
 > * By looking at the resulting much shorter versions of those
 >   functions, it'll be much clearer what each one does in broad terms.
 >   We can then think about whether the differences between them are
 >   important or not.
 > 
 > * When an extracted function from, say, make_symbol_overload_list is
 >   playing a similar role to an extracted function from, say,
 >   make_symbol_completion_list, then examine those functions to see if
 >   they can be profitably unified into a single function.
 > 
 > That may sound like a lot of work, but having gone through it a few
 > times, it's really not so bad.  And it's a great way to understand and
 > clean up functions.  It doesn't interact well with GDB's approval
 > process, though; I have some ideas about that, too, but I don't think
 > this is the place for them.
 > 
 > David Carlton
 > carlton@math.stanford.edu

Re: RFA/symtab: Let search_symbols find exact matches

[David Carlton]

On 21 Feb 2003 09:09:18 -0800, David Carlton <carlton@math.Stanford.EDU> said:
> On Fri, 21 Feb 2003 09:09:25 -0500, Daniel Jacobowitz <drow@mvista.com> said:

>> David, are you convinced that lookup_partial_symbol is close enough
>> to what we want for the patch above?

> It's close enough; on the other hand, since I'll submit a patch today
> or Monday to get lookup_partial_symbol even closer to what we want, we
> might as well wait until after that patch goes in before applying my
> make_symbol_overload_list patch.  I'll apply them both once that gets
> fixed up.

I've committed this now.

David Carlton
carlton@math.stanford.edu