Module: Charming::Components::FuzzyMatcher

Defined in:
lib/charming/presentation/components/fuzzy_matcher.rb

Overview

FuzzyMatcher implements fzf-style subsequence matching with contiguity and word-boundary scoring. Used by CommandPalette (and available to any component that filters labels against typed input).

FuzzyMatcher.score("opl", "Open palette")  # => positive score
FuzzyMatcher.score("xyz", "Open palette")  # => nil (not a subsequence)
FuzzyMatcher.filter("op", commands, &:label)

Constant Summary collapse

CHAR_SCORE =

Score bonuses: base per matched char, consecutive-run bonus, word-start bonus. The run bonus outweighs the word-start bonus so a literal substring match (“pal” in “Open palette”) beats the same letters scattered across word starts.

1
CONSECUTIVE_BONUS = 
4
WORD_START_BONUS = 
3

Class Method Summary collapse

Class Method Details

.best_alignment(q, qi, c, ci, consecutive_at_ci, memo) ⇒ Object

Finds the best-scoring alignment of q within c. consecutive_at_ci is true when the previous query char matched at ci - 1 (enabling the run bonus for a match exactly at ci). Returns nil when no alignment exists.



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/charming/presentation/components/fuzzy_matcher.rb', line 38

def best_alignment(q, qi, c, ci, consecutive_at_ci, memo)
  return 0 if qi == q.length

  key = [qi, ci, consecutive_at_ci]
  return memo[key] if memo.key?(key)

  best = nil
  index = ci
  while (index = c.index(q[qi], index))
    points = CHAR_SCORE
    points += CONSECUTIVE_BONUS if consecutive_at_ci && index == ci
    points += WORD_START_BONUS if word_start?(c, index)
    rest = best_alignment(q, qi + 1, c, index + 1, true, memo)
    if rest
      total = points + rest
      best = total if best.nil? || total > best
    end
    index += 1
  end

  memo[key] = best
end

.filter(query, candidates, &label) ⇒ Object

Filters candidates to those matching query, ordered best-score first (original order breaks ties). The optional block extracts the searchable label from each candidate (defaults to to_s).



64
65
66
67
68
69
70
71
72
 
# File 'lib/charming/presentation/components/fuzzy_matcher.rb', line 64

def filter(query, candidates, &label)
  scored = candidates.each_with_index.filter_map do |candidate, index|
    text = label ? yield(candidate) : candidate.to_s
    candidate_score = score(query, text)
    [candidate_score, index, candidate] if candidate_score
  end

  scored.sort_by { |candidate_score, index, _| [-candidate_score, index] }.map(&:last)
end

.score(query, candidate) ⇒ Object

Returns a relevance score when every character of query appears in order within candidate (case-insensitive), nil otherwise. Higher is better: contiguous runs and matches at word starts score above scattered matches. All alignments are considered (memoized), so “pal” finds the contiguous run in “Open palette” rather than the scattered greedy match.



27
28
29
30
31
32
33
 
# File 'lib/charming/presentation/components/fuzzy_matcher.rb', line 27

def score(query, candidate)
  q = query.to_s.downcase
  c = candidate.to_s.downcase
  return 0 if q.empty?

  best_alignment(q, 0, c, 0, false, {})
end

.word_start?(text, index) ⇒ Boolean

True when the character at index starts a word: position 0 or preceded by a separator (space, underscore, hyphen, slash, dot, colon).

Returns:

  • (Boolean) 


76
77
78
79
80
 
# File 'lib/charming/presentation/components/fuzzy_matcher.rb', line 76

def word_start?(text, index)
  return true if index.zero?

  text[index - 1].match?(%r{[\s_\-/.:]})
end