Module: FzyScore

Defined in:
lib/fzy_score.rb,
lib/fzy_score/match.rb,
lib/fzy_score/version.rb

Overview

FzyScore is a faithful, dependency-free Ruby port of the fzy fuzzy-matching scoring algorithm (the same family of algorithm used by fzf and fzf-for-js).

Unlike Ruby’s existing fuzzy gems (which do Levenshtein/Dice record linkage, or a boolean “does it match” filter), FzyScore returns BOTH a relevance score and the matched character positions — exactly what you need to build a command palette, quick-open, autocomplete, or CLI picker with highlighting.

Examples:

Quick scoring

FzyScore.score("amf", "app/models/foo.rb") # => Float

Ranking candidates

FzyScore.filter("srcmtch", ["src/match.rb", "spec/match_spec.rb", "README.md"])
# => [["src/match.rb", <score>, [0,1,2,4,5,6,7]], ...]   (best first)

Highlighting

m = FzyScore.match("mr", "app/models/user.rb", positions: true)
m.positions # => indices to highlight

Defined Under Namespace

Classes: Match

Constant Summary collapse

SCORE_GAP_LEADING =

Scoring constants, taken verbatim from fzy’s config.def.h so that ranking matches the reference implementation.

-0.005
SCORE_GAP_TRAILING = 
-0.005
SCORE_GAP_INNER = 
-0.01
SCORE_MATCH_CONSECUTIVE = 
1.0
SCORE_MATCH_SLASH = 
0.9
SCORE_MATCH_WORD = 
0.8
SCORE_MATCH_CAPITAL = 
0.7
SCORE_MATCH_DOT = 
0.6
SCORE_MAX = 
Float::INFINITY
SCORE_MIN = 
-Float::INFINITY
MATCH_MAX_LEN =

Candidates longer than this are not scored with the full DP (treated as SCORE_MIN), matching fzy’s behaviour of not penalising the rest of the UI for one unreasonably large entry.

1024
WORD_BREAK =

Bonus awarded to a character based on the character that precedes it. Mirrors fzy’s bonus_states table.

{ "-" => SCORE_MATCH_WORD, "_" => SCORE_MATCH_WORD, " " => SCORE_MATCH_WORD }.freeze
VERSION = 
"0.1.0"

Class Method Summary collapse

Class Method Details

.compute_bonus(last_ch, ch) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
# File 'lib/fzy_score.rb', line 160

def compute_bonus(last_ch, ch)
  # Bonus only applies to alphanumeric current characters.
  return 0.0 unless ch.match?(/[a-z0-9]/i)

  case last_ch
  when "/"
    SCORE_MATCH_SLASH
  when "-", "_", " "
    SCORE_MATCH_WORD
  when "."
    SCORE_MATCH_DOT
  else
    # camelCase: an uppercase current char after a lowercase previous char.
    if ch.match?(/[A-Z]/) && last_ch.match?(/[a-z]/)
      SCORE_MATCH_CAPITAL
    else
      0.0
    end
  end
end

.compute_score(needle, haystack, match_bonus, n, m) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Score-only DP. Two rolling rows (D and M), matching fzy’s match().



183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/fzy_score.rb', line 183

def compute_score(needle, haystack, match_bonus, n, m)
  d_last = Array.new(m, SCORE_MIN)
  m_last = Array.new(m, SCORE_MIN)
  d_curr = Array.new(m, SCORE_MIN)
  m_curr = Array.new(m, SCORE_MIN)

  n.times do |i|
    match_row(i, n, needle, haystack, match_bonus, m, d_curr, m_curr, d_last, m_last)
    d_curr, d_last = d_last, d_curr
    m_curr, m_last = m_last, m_curr
  end

  # After the swap, the last computed row is in *_last.
  m_last[m - 1]
end

.compute_with_positions(needle, haystack, match_bonus, n, m) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Full DP keeping every row so positions can be backtracked. Mirrors fzy’s match_positions().



202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/fzy_score.rb', line 202

def compute_with_positions(needle, haystack, match_bonus, n, m)
  d = Array.new(n) { Array.new(m, SCORE_MIN) }
  mm = Array.new(n) { Array.new(m, SCORE_MIN) }

  match_row(0, n, needle, haystack, match_bonus, m, d[0], mm[0], d[0], mm[0])
  (1...n).each do |i|
    match_row(i, n, needle, haystack, match_bonus, m, d[i], mm[i], d[i - 1], mm[i - 1])
  end

  positions = Array.new(n, 0)
  match_required = false
  j = m - 1
  i = n - 1
  while i >= 0
    while j >= 0
      if d[i][j] != SCORE_MIN && (match_required || d[i][j] == mm[i][j])
        match_required =
          i.positive? && j.positive? &&
          mm[i][j] == d[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE
        positions[i] = j
        j -= 1
        break
      end
      j -= 1
    end
    i -= 1
  end

  Match.new(mm[n - 1][m - 1], positions)
end

.do_match(needle, haystack, positions:) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/fzy_score.rb', line 120

def do_match(needle, haystack, positions:)
  return Match.new(SCORE_MIN, nil) if needle.nil? || needle.empty?
  return Match.new(SCORE_MIN, nil) unless match?(needle, haystack)

  n = needle.length
  m = haystack.length

  if m > MATCH_MAX_LEN || n > m
    return Match.new(SCORE_MIN, nil)
  elsif n == m
    # Same length AND it matched => identical (case-insensitive).
    return Match.new(SCORE_MAX, positions ? (0...n).to_a : nil)
  end

  lower_needle = needle.downcase
  lower_haystack = haystack.downcase
  match_bonus = precompute_bonus(haystack)

  if positions
    compute_with_positions(lower_needle, lower_haystack, match_bonus, n, m)
  else
    Match.new(compute_score(lower_needle, lower_haystack, match_bonus, n, m), nil)
  end
end

.filter(needle, candidates, positions: false, key: nil) ⇒ Array<Array>

Filter and rank a list of candidates against needle, best first.

Each returned row is [candidate, score, positions]. Candidates that do not match are dropped. Sorting is stable on ties (preserves input order), matching the intuition users expect from a picker.

Parameters:

  • needle (String)
  • candidates (Array<#to_s>)
  • positions (Boolean) (defaults to: false) —

    include matched positions in each row

  • key (Proc, nil) (defaults to: nil) —

    extract the string to match from each candidate

Returns:

  • (Array<Array>) —

    rows of [candidate, score, positions_or_nil]



103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/fzy_score.rb', line 103

def filter(needle, candidates, positions: false, key: nil)
  rows = []
  candidates.each_with_index do |candidate, idx|
    str = key ? key.call(candidate) : candidate.to_s
    next unless match?(needle, str)

    m = do_match(needle, str, positions: positions)
    rows << [candidate, m.score, m.positions, idx]
  end
  # Stable sort: higher score first, original index breaks ties.
  rows.sort_by! { |row| [-row[1], row[3]] }
  rows.map { |candidate, sc, pos, _| [candidate, sc, pos] }
end

.match(needle, haystack, positions: true) ⇒ FzyScore::Match

Score needle against haystack and (optionally) return the matched positions for highlighting.

Parameters:

  • needle (String)
  • haystack (String)
  • positions (Boolean) (defaults to: true) —

    also compute the matched indices (slightly more work)

Returns:



88
89
90
 
# File 'lib/fzy_score.rb', line 88

def match(needle, haystack, positions: true)
  do_match(needle, haystack, positions: positions)
end

.match?(needle, haystack) ⇒ Boolean

Does needle fuzzily match haystack at all (case-insensitive, in order)?

This is the cheap O(n) pre-filter; it does not compute a score.

Parameters:

  • needle (String)
  • haystack (String)

Returns:

  • (Boolean) 


58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/fzy_score.rb', line 58

def match?(needle, haystack)
  n = needle.downcase
  h = haystack.downcase
  j = 0
  n.each_char do |ch|
    j = h.index(ch, j)
    return false if j.nil?

    j += 1
  end
  true
end

.match_row(i, n, needle, haystack, match_bonus, m, d_curr, m_curr, d_last, m_last) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Compute one row of the DP. Faithful translation of fzy’s match_row().



235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
 
# File 'lib/fzy_score.rb', line 235

def match_row(i, n, needle, haystack, match_bonus, m, d_curr, m_curr, d_last, m_last)
  prev_score = SCORE_MIN
  gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER
  needle_ch = needle[i]

  j = 0
  while j < m
    if needle_ch == haystack[j]
      score = SCORE_MIN
      if i.zero?
        score = (j * SCORE_GAP_LEADING) + match_bonus[j]
      elsif j.positive?
        consecutive = d_last[j - 1] + SCORE_MATCH_CONSECUTIVE
        via_bonus = m_last[j - 1] + match_bonus[j]
        score = via_bonus > consecutive ? via_bonus : consecutive
      end
      d_curr[j] = score
      candidate = prev_score + gap_score
      m_curr[j] = prev_score = score > candidate ? score : candidate
    else
      d_curr[j] = SCORE_MIN
      m_curr[j] = prev_score = prev_score + gap_score
    end
    j += 1
  end
end

.precompute_bonus(haystack) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Per-position bonus based on the preceding character (word starts, slashes, dots, camelCase transitions). The first character is treated as if preceded by a slash, matching fzy.



149
150
151
152
153
154
155
156
157
 
# File 'lib/fzy_score.rb', line 149

def precompute_bonus(haystack)
  bonus = Array.new(haystack.length, 0.0)
  last_ch = "/"
  haystack.each_char.with_index do |ch, i|
    bonus[i] = compute_bonus(last_ch, ch)
    last_ch = ch
  end
  bonus
end

.score(needle, haystack) ⇒ Float

Score how well needle matches haystack. Returns SCORE_MIN when there is no match (so it sorts last). Higher is better.

Parameters:

  • needle (String)
  • haystack (String)

Returns:

  • (Float) 


77
78
79
 
# File 'lib/fzy_score.rb', line 77

def score(needle, haystack)
  do_match(needle, haystack, positions: false).score
end