search

wincent / command-t

⌨️ Fast file navigation for Neovim and Vim
BSD 2-Clause "Simplified" License
2.74k stars 317 forks source link

Make use of memoization matrix to reconstruct matching characters for highlighting purposes #286

Closed wincent closed 2 years ago

Aster89 commented 2 years ago

To avoid duplicating the issues. Is the title referring to the behavior below? asciicast

wincent commented 2 years ago

Yes, that's right @Aster89. The way Command-T works (unless configured otherwise) is to recursively try all the possible ways of scoring a given match, and to use the highest-scoring one for each path (for the purposes of ranking the matches relative to each other). This is done using the "memoization matrix" mentioned in the title. So, if you search for "abc" and one of the paths is "apple/banana/abc", Command-T will calculate the scores for all of these ways of matching:

apple/banana/abc
^     ^        ^
apple/banana/abc
^             ^^
apple/banana/abc
       ^      ^^
apple/banana/abc
         ^    ^^
apple/banana/abc
           ^  ^^
apple/banana/abc
             ^^^

Now, the memoization matrix "knows" which match positions produced the highest score, but it is an implementation detail of the scoring algorithm; by the time the Vim-side code comes along to do the highlighting, it doesn't have access to the matrix or know anything about it — so it just does the dumbest/fastest thing and highlights the first possible match for each character, using a simple greedy algorithm, which is what you're seeing in your recording.

Aster89 commented 2 years ago

Thanks for the detailed explanation. I guess the code that would need to be changed in order for it to expose these details (well, since you do hightlight stuff, I guess it qualifies them as non-implementation details anymore, no?) is a Ruby code, right?

wincent commented 2 years ago

Right, the Ruby code which is highlighting the string is here. The memoization is happening in C-land (see memo in this file, which is what I am calling an "implementation detail").

wincent commented 2 years ago

Given the big rewrite for v6.0.x, I'm closing all older issues as there is unlikely to be anything significant happening on the 5-x-devel branch from here on[^patches]. Feedback issue for 6.0.x is here:

[^patches]: Patches and PRs would be welcome, but my personal efforts are going to be directed towards main.