Fuzzy matching in tab completion

Last weekend while on the road home, I worked on adding fuzzy matching to Complete::Util‘s complete_array_elem(). This enables fuzzy matching (typo correction) in many tab completion routines and utilities that uses the Complete::* modules family. For example, in cpanm (install and activate App::ShellCompleter::cpanm first):

% cpanm --miror[Tab]
% cpanm --mirror_

% cpanm Compess[Tab]
% cpanm Compress_

Or mpv (install and activate App::ShellCompleter::mpv first):

% mpv --video-zom[Tab]
% mpv --video-zoom _

% mpv json[Tab]
% mpv Jason\ Chen\ _
% mpv Jason\ Chen\ -\ ihate[Tab]
% mpv Jason\ Chen\ -\ I\ Hate\ Sorry\ Lyrics\ on\ Screen-D95JzZ7ID4U.mp4 _

As well as all CLI scripts using the Perinci::CmdLine::Lite or Perinci::CmdLine::Classic framework, for example lcpan and pause:

% lcpan modole[Tab]
% lcpan modules _

% pause listmods[Tab]
% pause list-mods _

% pause sl[Tab]  ; # hoping to be autocorrected to 'ls'
% pause cleanup _

Whoops, okay, so the fuzzy matching still needs some tuning up to do. But generally it works pretty well in my experience so far.

If you don’t have Text::Levenshtein::XS (it’s a recommends/optional prereq), fuzzy matching is rather slow. This starts to becomes noticeable when you have thousands of entries to match. For example when using progless from App-ProgUtils:

% progless pogles[Tab]
% progless progless _

That took almost 1s for complete_array_elem() to fuzzy match out of almost 5000 items (all programs in my PATH). However, note that fuzzy matching is only used when exact matching fails to produce a match. So if you do:

% progless prog[Tab][Tab]
progcat   progedit  progless  progman   progpath  
% progless progle[Tab]
% progless progless _

Those completion all complete quickly because no fuzzy matching is done. And course, you can just install Text::Levenshtein::XS to speed things up.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s