Completion heuristics (was Re: bug in _rpm?)

["Bart Schaefer" <schaefer@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sep 17, 10:45am, Sven Wischnowsky wrote:
} Subject: Re: bug in _rpm?
}
} >   % rpm -ihv /usr/src/redhat/RPMS/i386/<TAB>
} >   % rpm -ihv /usr/src/redhat/RPMS/i386/--
} >   zsh: do you wish to see all 28 possibilities? 
} > 
} > Where did that `--' come from?
} 
} Do you have many files in that directory, all of the form `*-*-*'

He must.  That's what RPM file names look like.

} If so, it's the unambiguous string that was inserted (with a somewhat
} weird cursor placement -- but we are currently thinking about ways to
} improve that, see 7831 and follow-ups; any help appreciated).

In this situation the amount of information and typing assistance that
is provided by inserting any ambiguous string at all is so small as to
be merely confusing.  The whole point of ambigous string insertion is
that the human is supposed to be better than zsh at resolving the
ambiguity, which ceases to be true below a certain information-content
threshold.

Better cursor placement would only help a little, and I think in this
example not at all.

One approach would be to figure out some heuristic for determining that
the ambiguous string "looks enough like" an element of the set of possible
matches, and not insert it at all if it looks "too different."

A wild guess at such a heuristic:

1.  There's exactly one choice for cursor placement to resolve the
    ambiguity; OR

2.  The ambiguous string shares a common (non-empty) prefix with ALL
    of the possible matches; OR

3.  The ambiguous string is at least half as long as the difference
    between the lengths of the shortest match and the longest and at
    least one-fourth as long as the length of the shortest.

Number (3) is obviously the wildest of the guesses.  I'd probably go with
just the first two, but I don't rely on intra-word match-specs all that
often, so I don't know exactly how to predict what's useful there.

As for cursor placement:  Put it wherever the addition of a character
would make the greatest difference in the number of matches; another
way to say this is, place the cursor at the implicit * that matches the
greatest number of alternatives.  This may be beyond our ability to
determine ... but the whole point of completion is to help the user
reduce the set of alternatives from N to 1 as quickly as possible, so
wherever will help throw out the most alternatives is the right place
to ask for more input.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com