Module: Clack::Core::FuzzyMatcher

Defined in:
lib/clack/core/fuzzy_matcher.rb

Overview

Simple scored fuzzy matcher for autocomplete prompts.

Matches query characters in order within the target string, scoring higher for consecutive matches and matches at word boundaries. Dependency-free alternative to Levenshtein distance that’s fast enough for interactive use.

Examples:

Basic matching

FuzzyMatcher.match?("fb", "foobar")  # => true
FuzzyMatcher.match?("zz", "foobar")  # => false

Scoring

FuzzyMatcher.score("fb", "foobar")  # => 2 (non-consecutive)
FuzzyMatcher.score("foo", "foobar") # => 9 (consecutive + start)

Filtering and sorting options

FuzzyMatcher.filter(options, "fb") # => sorted by relevance

Constant Summary collapse

START_BONUS =

Bonus for match at the very start of the string

3
CONSECUTIVE_BONUS =

Bonus for each consecutive character matched

2
BOUNDARY_BONUS =

Bonus for match at a word boundary (after space, _, -)

2
BASE_SCORE =

Base score per matched character

1

Class Method Summary collapse

Class Method Details

.filter(options, query) ⇒ Array<Hash>

Filter and sort option hashes by fuzzy relevance.

Matches against label, value (as string), and hint fields. Returns options sorted by best match score (descending).

Parameters:

  • options (Array<Hash>) —

    normalized option hashes

  • query (String) —

    the search query

Returns:

  • (Array<Hash>) —

    matching options sorted by relevance



91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/clack/core/fuzzy_matcher.rb', line 91

def filter(options, query)
  return options if query.empty?

  q_down = query.downcase

  scored = options.filter_map do |opt|
    s = best_score(opt, query, q_down)
    [opt, s] if s.positive?
  end

  scored.sort_by { |_, s| -s }.map(&:first)
end

.match?(query, target) ⇒ Boolean

Check if query fuzzy-matches the target string.

Parameters:

  • query (String) —

    the search query

  • target (String) —

    the string to match against

Returns:

  • (Boolean) —

    true if all query chars appear in order in target



38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/clack/core/fuzzy_matcher.rb', line 38

def match?(query, target)
  return true if query.empty?

  qi = 0
  q_chars = query.downcase
  t_chars = target.downcase

  t_chars.each_char do |tc|
    qi += 1 if tc == q_chars[qi]
    return true if qi >= q_chars.length
  end

  false
end

.score(query, target, q_down: nil) ⇒ Integer

Score a fuzzy match. Higher is better. Returns 0 if no match.

Parameters:

  • query (String) —

    the search query

  • target (String) —

    the string to score against

  • q_down (String, nil) (defaults to: nil) —

    pre-downcased query (optimization for batch use)

Returns:

  • (Integer) —

    match score (0 = no match)



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/clack/core/fuzzy_matcher.rb', line 59

def score(query, target, q_down: nil)
  return 0 if query.empty?

  q_down ||= query.downcase
  t_down = target.downcase
  qi = 0
  total = 0
  prev_match_idx = -2 # -2 so first match at 0 isn't consecutive

  t_down.each_char.with_index do |tc, ti|
    next unless qi < q_down.length && tc == q_down[qi]

    total += BASE_SCORE
    total += START_BONUS if ti.zero?
    total += CONSECUTIVE_BONUS if ti == prev_match_idx + 1
    total += BOUNDARY_BONUS if ti.positive? && boundary?(t_down[ti - 1])

    prev_match_idx = ti
    qi += 1
  end

  (qi >= q_down.length) ? total : 0
end