Re: Emacs needs truely useful flex matching

[Le Wang <l26wang@gmail.com>]

On Fri, Mar 22, 2013 at 7:58 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>>> The sorting algorithm is roughly this for a query: "abcd"
>>>
>>> 1. Get all matches for "a.*b.*c.*c"
>>> 2. Calculate score of each match
>>> - contiguous matched chars gets a boost
>>> - matches at word and camelCase boundaries (abbreviation) get a boost
>>> - matches with smallest starting index gets a boost
>>> 2. Sort list according to score.
>
> I think that if you turn "abcd" into a regexp of the form
> "\\(\\<\\)?a\\([^b]*\\)\\(\\<\\)?b\\([^c]*\\)\\(\\<\\)?c\\([^d]*\\)\\(\\<\\)?d"
> the regexp matching should be fairly efficient and you should be able to
> compute the score efficiently as well (at least if
> you ignore the camelCase boundaries).

I hadn't thought of this, and I'll try it soon.

> Have you tried such an approach and it really was too slow?
> I'd welcome a new completion-style using the above flex matching.

You're right that in generally that my claim of "emacs-lisp would be
too slow" needs to be verified.

>> IIUC the vim plugin you mention depends on a pre-built list of files.
>
> Indeed when searching for a file in a file hierarchy, you'd need
> a pre-built list of files, otherwise the time taken to find the files
> would dwarf the flex-matching time in any case.

"git ls-files" is very fast on a solid state drive, and the list can
also be cached.  But let's assume we already have the list of strings.


-- 
Le