Patch: completion -vs- duplicates

Patch: completion -vs- duplicates

[Tom Tromey]

Right now the `complete' command can print duplicates.  readline seems
to filter these, so you don't see this using Tab in the CLI, but you
can see it in Insight or by using the complete command.

E.g., run gdb on itself and type "complete b captured_ma".
I see `b captured_main' and `b captured_main_args' repeated many
times.

This patch fixes completion to uniquify the result list.

Ok to commit?

Tom

Index: ChangeLog
from  Tom Tromey  <tromey@redhat.com>

	* completer.c (compare_strings): New function.
	(line_completion_function): Make result list have unique
	elements.

Index: completer.c
===================================================================
RCS file: /cvs/src/src/gdb/completer.c,v
retrieving revision 1.8
diff -u -r1.8 completer.c
--- completer.c 2001/07/15 18:57:06 1.8
+++ completer.c 2002/01/04 23:52:18
@@ -339,6 +339,15 @@
   return list;
 }
 
+/* String compare function for qsort.  */
+static int
+compare_strings (const void *arg1, const void *arg2)
+{
+  const char **s1 = (const char **) arg1;
+  const char **s2 = (const char **) arg2;
+  return strcmp (*s1, *s2);
+}
+
 /* Here are some useful test cases for completion.  FIXME: These should
    be put in the test suite.  They should be tested with both M-? and TAB.
 
@@ -620,6 +629,30 @@
 		  list = (*c->completer) (p, word);
 		}
 	    }
+	}
+
+      /* Make sure each item in the list is unique.  */
+      if (list)
+	{
+	  int src, dest, size;
+
+	  for (size = 0; list[size]; ++size)
+	    ;
+	  qsort (list, size, sizeof (char *), compare_strings);
+
+	  src = 0;
+	  dest = 0;
+	  while (src < size)
+	    {
+	      list[dest] = list[src++];
+	      while (src < size && ! strcmp (list[dest], list[src]))
+		{
+		  xfree (list[src]);
+		  ++src;
+		}
+	      ++dest;
+	    }
+	  list[dest] = NULL;
 	}
     }

Re: Patch: completion -vs- duplicates

[Eli Zaretskii]

> From: Tom Tromey <tromey@redhat.com>
> Date: 04 Jan 2002 17:07:51 -0700
> 
> Right now the `complete' command can print duplicates.  readline seems
> to filter these, so you don't see this using Tab in the CLI, but you
> can see it in Insight or by using the complete command.

Hm... shouldn't Insight do the same as readline?

In my mind, GDB doesn't do any completion at all.  Completion is a
feature of the UI; GDB just helps the UI by providing a function to
call to get all the completion candidates.  The rest--how to display
the candidates, whether to filter out duplicates, etc.--is up to the
UI's completion machinery.  So conceptually, in my mind, the
filtering doesn't belong in GDB.

Concepts aside, the change you suggest has also practical
disadvantages: filtering duplicates in GDB's completion function would
mean a performance hit in the CLI version, since readline will try to
filter again.

Re: Patch: completion -vs- duplicates

[Daniel Berlin]

On Sat, 5 Jan 2002, Eli Zaretskii wrote:

> > From: Tom Tromey <tromey@redhat.com>
> > Date: 04 Jan 2002 17:07:51 -0700
> > 
> > Right now the `complete' command can print duplicates.  readline seems
> > to filter these, so you don't see this using Tab in the CLI, but you
> > can see it in Insight or by using the complete command.
> 
> Hm... shouldn't Insight do the same as readline?
> 
> In my mind, GDB doesn't do any completion at all.  Completion is a
> feature of the UI; GDB just helps the UI by providing a function to
> call to get all the completion candidates.  The rest--how to display
> the candidates, whether to filter out duplicates, etc.--is up to the
> UI's completion machinery.  So conceptually, in my mind, the
> filtering doesn't belong in GDB.
> 
> Concepts aside, the change you suggest has also practical
> disadvantages: filtering duplicates in GDB's completion function would
> mean a performance hit in the CLI version, since readline will try to
> filter again.

Yes. I remember this was the huge lose that caused completion to take 
forever, which is why I removed the duplicate filtering.
I'm surprised you insight guys didn't notice then, actually.
--Dan

Re: Patch: completion -vs- duplicates

[Tom Tromey]

>>>>> "Daniel" == Daniel Berlin <dan@dberlin.org> writes:

Eli> The rest--how to display the candidates, whether to filter out
Eli> duplicates, etc.--is up to the UI's completion machinery.

It always makes sense to filter duplicates when doing textual
completion.  What value can there be in completing to the second of
two identical items?

Eli> Concepts aside, the change you suggest has also practical
Eli> disadvantages: filtering duplicates in GDB's completion function
Eli> would mean a performance hit in the CLI version, since readline
Eli> will try to filter again.

Daniel> Yes. I remember this was the huge lose that caused completion
Daniel> to take forever, which is why I removed the duplicate
Daniel> filtering.

I'm surprised it is that important.
I'll write an Insight patch instead.

Daniel> I'm surprised you insight guys didn't notice then, actually.

I probably did.  The bug has been around for a long time.  I submitted
an Insight PR way back, which yesterday Keith replied to with a note
saying that it was a gdb bug.

I still think having the `complete' command print duplicates is not
optimal.  Suppose you're writing a GUI that wraps gdb.  In this case
you're sending 100x more data over the connection than is necessary.
Pruning duplicates in the `complete' command is probably appropriate.

Tom

Re: Patch: completion -vs- duplicates

[Andrew Cagney]

> "Daniel" == Daniel Berlin <dan@dberlin.org> writes:
> 
> 
> Eli> The rest--how to display the candidates, whether to filter out
> Eli> duplicates, etc.--is up to the UI's completion machinery.
> 
> It always makes sense to filter duplicates when doing textual
> completion.  What value can there be in completing to the second of
> two identical items?


Ha, that code.

I suspect you're both right. 2c worth. The underlying code should be 
using the most efficient mechanism available to complete things. 
However the ``(gdb) complete'' command should be stripping duplicates.

Tom, what exactly does Insight need?  Probably should do the right thing 
and MI the interface.

Andrew

Re: Patch: completion -vs- duplicates

[Tom Tromey]

>>>>> "Andrew" == Andrew Cagney <ac131313@cygnus.com> writes:

Andrew> Tom, what exactly does Insight need?  Probably should do the
Andrew> right thing and MI the interface.

Right now Insight just runs the gdb `complete' command and uses its
output.  I looked at the implementation of `complete' a bit.  Making
that work looks ugly.  One approach would be to introduce a new
function which would return the whole array for use, and then have
both `complete' and line_completion_function() be clients of this new
function.

I basically don't know anything about MI.  I don't think Insight
really uses it, does it?

Tom

Re: Patch: completion -vs- duplicates

[Daniel Jacobowitz]

On Sat, Jan 05, 2002 at 10:43:57AM -0500, Daniel Berlin wrote:
> On Sat, 5 Jan 2002, Eli Zaretskii wrote:
> 
> > > From: Tom Tromey <tromey@redhat.com>
> > > Date: 04 Jan 2002 17:07:51 -0700
> > > 
> > > Right now the `complete' command can print duplicates.  readline seems
> > > to filter these, so you don't see this using Tab in the CLI, but you
> > > can see it in Insight or by using the complete command.
> > 
> > Hm... shouldn't Insight do the same as readline?
> > 
> > In my mind, GDB doesn't do any completion at all.  Completion is a
> > feature of the UI; GDB just helps the UI by providing a function to
> > call to get all the completion candidates.  The rest--how to display
> > the candidates, whether to filter out duplicates, etc.--is up to the
> > UI's completion machinery.  So conceptually, in my mind, the
> > filtering doesn't belong in GDB.
> > 
> > Concepts aside, the change you suggest has also practical
> > disadvantages: filtering duplicates in GDB's completion function would
> > mean a performance hit in the CLI version, since readline will try to
> > filter again.
> 
> Yes. I remember this was the huge lose that caused completion to take 
> forever, which is why I removed the duplicate filtering.
> I'm surprised you insight guys didn't notice then, actually.
> --Dan

Is it possible to turn this off in readline?  I'd rather do it once
than in every frontend!  And from what I recall, readline is not
terribly efficient about it.

-- 
Daniel Jacobowitz                           Carnegie Mellon University
MontaVista Software                         Debian GNU/Linux Developer

Re: Patch: completion -vs- duplicates

[Daniel Berlin]

On Sat, 5 Jan 2002, Daniel Jacobowitz wrote:

> On Sat, Jan 05, 2002 at 10:43:57AM -0500, Daniel Berlin wrote:
> > On Sat, 5 Jan 2002, Eli Zaretskii wrote:
> > 
> > > > From: Tom Tromey <tromey@redhat.com>
> > > > Date: 04 Jan 2002 17:07:51 -0700
> > > > 
> > > > Right now the `complete' command can print duplicates.  readline seems
> > > > to filter these, so you don't see this using Tab in the CLI, but you
> > > > can see it in Insight or by using the complete command.
> > > 
> > > Hm... shouldn't Insight do the same as readline?
> > > 
> > > In my mind, GDB doesn't do any completion at all.  Completion is a
> > > feature of the UI; GDB just helps the UI by providing a function to
> > > call to get all the completion candidates.  The rest--how to display
> > > the candidates, whether to filter out duplicates, etc.--is up to the
> > > UI's completion machinery.  So conceptually, in my mind, the
> > > filtering doesn't belong in GDB.
> > > 
> > > Concepts aside, the change you suggest has also practical
> > > disadvantages: filtering duplicates in GDB's completion function would
> > > mean a performance hit in the CLI version, since readline will try to
> > > filter again.
> > 
> > Yes. I remember this was the huge lose that caused completion to take 
> > forever, which is why I removed the duplicate filtering.
> > I'm surprised you insight guys didn't notice then, actually.
> > --Dan
> 
> Is it possible to turn this off in readline?  I'd rather do it once
> than in every frontend!  And from what I recall, readline is not
> terribly efficient about it.
Nor were we.
IIRC, we did it as each thing was added to the list (I could be wrong 
here), which gives you horrible complexity.
If this is the case, doing it once at the end would be fine by me.

> 
>