Re: Autocompletion

[Jon Trowbridge <trow ximian com>]

On Sat, 2002-10-05 at 20:12, Jody Goldberg wrote:
> 2) If memory serves, Jon Trowbridge did alot of work to support
>    different types of completion for email addresses in evolution.
>    I'd like to get his thoughts on this.

Yes, I did work on these sorts of issues for Evolution.  I'm sorry for
being a bit late in getting into this discussion: I was on the road last
week, and didn't get a good block of time for looking at
the code until now.

IMO, the three main properties a non-sucking completion implementation
should have are:

(1) Total model/view split.

(2) Completions generated by objects implementing a "completion-soure"
    interface.

(3) Support for fully asynchronous completion generation.  (My
    canonical example here would be completions generated by querying
    for name or email matches against a sluggish LDAP server across the
    network.)

The proposed code seems to mostly satisfy these three requirements,
which is one reason for the delay in my response... I didn't see
anything horrifying that motivated me to act quickly. :)

Below are some comments, questions and random assertions that came to
mind when I read over the egg-autocompletion*.[ch] for the first time.

-JT


On EggAutocompletionSource
--------------------------

I'm a bit confused about the semantics of the eas_set_basic_key and
eas_foreach methods.  Presumably set_basic_key means "start computing
completions for this string", but the foreach method also takes a
basic_key string as an argument.

Q: Does this mean that multiple queries are allowed simultaneously? i.e.
    is something like

   EggAutocompletionSource *my_source = blah_blah_blah;

   eas_set_basic_key (my_source, "foo");
   eas_set_basic_key (my_source, "bar");

   ... time for completions to generate ...

   eas_foreach (my_source, "foo", gather_foo_completions, foofoo);
   eas_foreach (my_source, "bar", gather_bar_completions, barbar);

    supposed to be valid?  IMO the API suggests that it is allowed,
    but I suspect that it actually isn't... and requiring such behavior
    would complicate implementations.

subQ: If multiple simultaneous searches are allowed, shouldn't
      the data_changed signal allow per-basic_key notification.

Q: Shouldn't we also support a method of cancelling the current query?
   This could be important for 'slow' completion generators that involve
   (for example) queries across the network.

Q: Also, maybe there should be a way for a source to send up
   notification that the current list of matches is complete?  There
   should be some way for users to know that the drop-down of matches
   they are looking at is fully populated and isn't still waiting for
   more results from some slow server across the network.


On EggAutocompletionMatch
-------------------------

The EggAutocompletion object acts as an aggregator of
EggAutocompletionSources, and exposes the results of a query as
EggAutocompletionMatch structs.  The EggAutocompletion is responsible
for
memory-managing the EggAutocompletionMatches.

However, the EggAutocompletionMatches are built up by the
EggAutocompletion.
The EggAutocompletionSource-implementers just pass up three pieces of
data:

  (1) An 'item' string
  (2) A 'title' string
  (3) A numerical score.

This scheme makes it impossible (or at least unwieldy) for an
EggAutocompletionSource to pass any extra data about the match.  IMHO it
would
make more sense for the EggAutocompletionSourceForeachFunc to be
typedefed
as

typedef void (* EggA..ForeachFunc) (EggAutocompletionSource *source,
	                            EggAutocompletionMatch  *match,
                                    gpointer                 user_data);

EggAutocompletionMatches should be extensible by struct-nesting and
(maybe) should be reference-counted to avoid memory-management
hassles.  Allowing nesting would allow more complex entry widgets
build on the stock completion framework while still getting access to
extra meta-data that they generate at completion-time.

So the definition of EggAutocompletionMatch would move to
egg-autocompletion-source.h and would probably look something like this:

struct _EggAutocompletionMatch {
  int refs;
  void (*destroy) (struct _EggAutocompletionMatch *);
  
  gchar *match;
  gchar *title;
  gint32 score;

  guint  offset; /* This seems like an implementation detail of
                    EggAutocompletion that we are needlessly exposing,
                    but I didn't really look at the code carefully
                    enough to understand exactly what it was doing... */
};

with associated functions:

EggAu..Match *egg_autocompletion_match_ref   (EggAutocompletionMatch *);
void          egg_autocompletion_match_unref (EggAutocompletionMatch *);


Sorting and Scores
------------------

Complex sorting schemes might be difficult to implement using just a
numerical score.  The two main issues I see are:

(1) If we have special sorting requirements and start spitting out
    solutions before the entire query is complete, how do we handle
    scoring?  It is important that any 'views' on the EggAutocompletion
    not assume that scores are constant -- in some cases we would
    definitely need to re-score every match whenever new solutions are
    found (or lazily, before every eas_foreach call when there have
    been changes.)

(2) How do we compare scores between matches that come from multiple
    EggAutocompletionSources?  Or more specifically: are such
    comparisons necessarily meaningful?  I can think of some cases where
    weirdness could definitely ensue.

One approach might be to allow users to register a sort function with
an EggAutocompletion: the sort function would then be used in lieu of
(or somehow in conjunction with) the match's score.