port of fzy/fzy.js to vimscript

fzy.vim

let s:score_min = float2nr(-1/0.0) + 0.0
let s:score_max = float2nr(1/0.0) + 0.0
let s:score_gap_trailing = -0.005
let s:score_gap_leading = -0.005
let s:score_gap_inner = -0.01

let s:score_match_consecutive = 1.0
let s:score_match_slash = 0.9
let s:score_match_word = 0.8
let s:score_match_capital = 0.7
let s:score_match_dot = 0.6

function! s:islower(string)
  return tolower(a:string) is# a:string
endfunction

function! s:isupper(string)
  return toupper(a:string) is# a:string
endfunction

function! s:fmax(x, y)
  if a:x < a:y | return a:y | endif
  return a:x
endfunction

function! s:precompute(haystack)
  " Which positions are beginning of words
  let bonus = []
  let last = '/'
  for l:ch in split(a:haystack, '\zs')
    if last is# '/'
      eval add(bonus, s:score_match_slash)
    elseif last is# '.'
      eval add(bonus, s:score_match_dot)
    elseif count(['-', '_', ' '], last)
      eval add(bonus, s:score_match_word)
    elseif s:islower(last) && s:isupper(ch)
      eval add(bonus, s:score_match_capital)
    else
      eval add(bonus, 0.0)
    endif
    let last = l:ch
  endfor
  return bonus
endfunction


"D[][] stores the best score for this position ending with a match
"M[][] Stores the best possible score at this position
function! s:compute(needle, haystack)
  let D = []
  let M = []
  const haystack_length = len(a:haystack)
  const needle_length = len(a:needle)
  const lower_haystack = tolower(a:haystack)
  const lower_needle = tolower(a:needle)
  const bonus = s:precompute(a:haystack)
  for idx in range(needle_length)
    let d = []
    let m = []
    let previous = s:score_min
    let gap = idx is needle_length - 1 ? s:score_gap_trailing : s:score_gap_inner
    for jdx in range(haystack_length)
      if lower_needle[idx] is# lower_haystack[jdx]
        let score = s:score_min
        if !idx
          let score = jdx * s:score_gap_leading + bonus[jdx]
        elseif jdx
          let score = s:fmax(
                \ M[idx - 1][jdx - 1] + bonus[jdx],
                \ D[idx - 1][jdx - 1] + s:score_match_consecutive)
        endif
        let previous = s:fmax(score, previous + gap)
        eval add(d, score)
      else
        let previous = l:previous + l:gap
        eval add(d, s:score_min)
      endif
      eval add(m, previous)
    endfor
    eval add(D, d)
    eval add(M, m)
  endfor
  return [D, M]
endfunction

function! s:contains(needle, haystack)
  let haystack = split(tolower(a:haystack), '\zs')
  let needle = split(tolower(a:needle), '\zs')
  let idx = 0
  for char in needle
    let idx = index(haystack, char, idx) + 1
    if idx is 0 | return v:false | endif
  endfor
  return v:true
endfunction

function! s:score(needle, haystack)
  if type(a:haystack) isnot v:t_string | throw "fzy: Invalid type for haystack" | endif
  if type(a:needle) isnot v:t_string | throw "fzy: Invalid type for needle" | endif
  if empty(a:needle) || empty(a:haystack) | return s:score_min | endif
  if a:needle is# a:haystack | return s:score_max | endif
  if len(a:haystack) > 1024 | return s:score_min | endif
  let [D, M] = s:compute(a:needle, a:haystack)
  return M[len(a:needle) - 1][len(a:haystack) - 1]
endfunction

function! s:positions(needle, haystack)
  if type(a:haystack) isnot v:t_string | throw "fzy: Invalid type for haystack" | endif
  if type(a:needle) isnot v:t_string | throw "fzy: Invalid type for needle" | endif
  if empty(a:needle) || empty(a:haystack) | return [] | endif
  if a:needle is# a:haystack | return range(len(a:needle)) | endif
  if len(a:haystack) > 1024 | return [] | endif

  let [D, M] = s:compute(a:needle, a:haystack)


  let positions = split(repeat(0, len(a:needle)), '\zs')

  let required = v:false
  for idx in reverse(range(len(a:needle) - 1))
    for jdx in reverse(range(len(a:haystack) - 1))
      let d = D[idx][jdx]
      let m = M[idx][jdx]
      if d is s:score_min | continue | endif
      if d is l:m || required
        let required = idx && jdx && l:m is (D[idx - 1][jdx - 1] + s:score_match_consecutive)
        let positions[idx] = jdx
      endif
    endfor
  endfor
  return positions
endfunction

function! s:compare(query, lhs, rhs)
  let lhs = -s:score(a:query, a:lhs) 
  let rhs = -s:score(a:query, a:rhs)
  if lhs is rhs | return 0 | endif
  if lhs > rhs | return 1 | endif
  return -1
endfunction

function! s:pad(string, amount)
  return a:string .. repeat(' ', a:amount - len(a:string))
endfunction

" s:list must be your data to searc
" s:query is what a user might type in
let s:list = getbufinfo(#{buflisted: v:true})->map({_, val -> val.name })
let s:query = '#'
let s:regex = split(s:query, '\zs')
      \ ->map({ _, val -> val !~# '[[:alnum:]]' ? '\' .. val : val })
      \ ->join('.*')
let s:list = s:list->filter({_, val -> match(val, '\v' .. s:regex) isnot -1})
echo s:list->sort(function('s:compare', [s:query]))
for entry in s:list
  let padded = ""
  let pos = s:positions(s:query, entry)
  for idx in range(len(s:query))
    let padded = s:pad(padded, pos[idx]) .. s:query[idx]
  endfor
  echomsg entry
  echomsg padded
endfor