/rust/registry/src/index.crates.io-1949cf8c6b5b557f/fuzzy-matcher-0.3.7/src/clangd.rs

Source
///! The fuzzy matching algorithm used in clangd.
///! https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.cpp
///!
///! # Example:
///! ```edition2018
///! use fuzzy_matcher::FuzzyMatcher;
///! use fuzzy_matcher::clangd::ClangdMatcher;
///!
///! let matcher = ClangdMatcher::default();
///!
///! assert_eq!(None, matcher.fuzzy_match("abc", "abx"));
///! assert!(matcher.fuzzy_match("axbycz", "abc").is_some());
///! assert!(matcher.fuzzy_match("axbycz", "xyz").is_some());
///!
///! let (score, indices) = matcher.fuzzy_indices("axbycz", "abc").unwrap();
///! assert_eq!(indices, [0, 2, 4]);
///!
///! ```
///!
///! Algorithm modified from
///! https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.cpp
///! Also check: https://github.com/lewang/flx/issues/98
use crate::util::*;
use crate::{FuzzyMatcher, IndexType, ScoreType};
use std::cell::RefCell;
use std::cmp::max;
use thread_local::CachedThreadLocal;

#[derive(Eq, PartialEq, Debug, Copy, Clone)]
enum CaseMatching {
    Respect,
    Ignore,
    Smart,
}

pub struct ClangdMatcher {
    case: CaseMatching,

    use_cache: bool,

    c_cache: CachedThreadLocal<RefCell<Vec<char>>>, // vector to store the characters of choice
    p_cache: CachedThreadLocal<RefCell<Vec<char>>>, // vector to store the characters of pattern
}

impl Default for ClangdMatcher {
    fn default() -> Self {
        Self {
            case: CaseMatching::Ignore,
            use_cache: true,
            c_cache: CachedThreadLocal::new(),
            p_cache: CachedThreadLocal::new(),
        }
    }
}

impl ClangdMatcher {
    pub fn ignore_case(mut self) -> Self {
        self.case = CaseMatching::Ignore;
        self
    }

    pub fn smart_case(mut self) -> Self {
        self.case = CaseMatching::Smart;
        self
    }

    pub fn respect_case(mut self) -> Self {
        self.case = CaseMatching::Respect;
        self
    }

    pub fn use_cache(mut self, use_cache: bool) -> Self {
        self.use_cache = use_cache;
        self
    }

    fn contains_upper(&self, string: &str) -> bool {
        for ch in string.chars() {
            if ch.is_ascii_uppercase() {
                return true;
            }
        }

        false
    }

    fn is_case_sensitive(&self, pattern: &str) -> bool {
        match self.case {
            CaseMatching::Respect => true,
            CaseMatching::Ignore => false,
            CaseMatching::Smart => self.contains_upper(pattern),
        }
    }
}

impl FuzzyMatcher for ClangdMatcher {
    fn fuzzy_indices(&self, choice: &str, pattern: &str) -> Option<(ScoreType, Vec<IndexType>)> {
        let case_sensitive = self.is_case_sensitive(pattern);

        let mut choice_chars = self
            .c_cache
            .get_or(|| RefCell::new(Vec::new()))
            .borrow_mut();
        let mut pattern_chars = self
            .p_cache
            .get_or(|| RefCell::new(Vec::new()))
            .borrow_mut();

        choice_chars.clear();
        for char in choice.chars() {
            choice_chars.push(char);
        }

        pattern_chars.clear();
        for char in pattern.chars() {
            pattern_chars.push(char);
        }

        if cheap_matches(&choice_chars, &pattern_chars, case_sensitive).is_none() {
            return None;
        }

        let num_pattern_chars = pattern_chars.len();
        let num_choice_chars = choice_chars.len();

        let dp = build_graph(&choice_chars, &pattern_chars, false, case_sensitive);

        // search backwards for the matched indices
        let mut indices_reverse = Vec::with_capacity(num_pattern_chars);
        let cell = dp[num_pattern_chars][num_choice_chars];

        let (mut last_action, score) = if cell.match_score > cell.miss_score {
            (Action::Match, cell.match_score)
        } else {
            (Action::Miss, cell.miss_score)
        };

        let mut row = num_pattern_chars;
        let mut col = num_choice_chars;

        while row > 0 || col > 0 {
            if last_action == Action::Match {
                indices_reverse.push((col - 1) as IndexType);
            }

            let cell = &dp[row][col];
            if last_action == Action::Match {
                last_action = cell.last_action_match;
                row -= 1;
                col -= 1;
            } else {
                last_action = cell.last_action_miss;
                col -= 1;
            }
        }

        if !self.use_cache {
            // drop the allocated memory
            self.c_cache.get().map(|cell| cell.replace(vec![]));
            self.p_cache.get().map(|cell| cell.replace(vec![]));
        }

        indices_reverse.reverse();
        Some((adjust_score(score, num_choice_chars), indices_reverse))
    }

    fn fuzzy_match(&self, choice: &str, pattern: &str) -> Option<ScoreType> {
        let case_sensitive = self.is_case_sensitive(pattern);

        let mut choice_chars = self
            .c_cache
            .get_or(|| RefCell::new(Vec::new()))
            .borrow_mut();
        let mut pattern_chars = self
            .p_cache
            .get_or(|| RefCell::new(Vec::new()))
            .borrow_mut();

        choice_chars.clear();
        for char in choice.chars() {
            choice_chars.push(char);
        }

        pattern_chars.clear();
        for char in pattern.chars() {
            pattern_chars.push(char);
        }

        if cheap_matches(&choice_chars, &pattern_chars, case_sensitive).is_none() {
            return None;
        }

        let num_pattern_chars = pattern_chars.len();
        let num_choice_chars = choice_chars.len();

        let dp = build_graph(&choice_chars, &pattern_chars, true, case_sensitive);

        let cell = dp[num_pattern_chars & 1][num_choice_chars];
        let score = max(cell.match_score, cell.miss_score);

        if !self.use_cache {
            // drop the allocated memory
            self.c_cache.get().map(|cell| cell.replace(vec![]));
            self.p_cache.get().map(|cell| cell.replace(vec![]));
        }

        Some(adjust_score(score, num_choice_chars))
    }
}

/// fuzzy match `line` with `pattern`, returning the score and indices of matches
pub fn fuzzy_indices(line: &str, pattern: &str) -> Option<(ScoreType, Vec<IndexType>)> {
    ClangdMatcher::default()
        .ignore_case()
        .fuzzy_indices(line, pattern)
}

/// fuzzy match `line` with `pattern`, returning the score(the larger the better) on match
pub fn fuzzy_match(line: &str, pattern: &str) -> Option<ScoreType> {
    ClangdMatcher::default()
        .ignore_case()
        .fuzzy_match(line, pattern)
}

// checkout https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.cpp
// for the description
fn build_graph(
    line: &[char],
    pattern: &[char],
    compressed: bool,
    case_sensitive: bool,
) -> Vec<Vec<Score>> {
    let num_line_chars = line.len();
    let num_pattern_chars = pattern.len();
    let max_rows = if compressed { 2 } else { num_pattern_chars + 1 };

    let mut dp: Vec<Vec<Score>> = Vec::with_capacity(max_rows);

    for _ in 0..max_rows {
        dp.push(vec![Score::default(); num_line_chars + 1]);
    }

    dp[0][0].miss_score = 0;

    // first line
    for (idx, &ch) in line.iter().enumerate() {
        dp[0][idx + 1] = Score {
            miss_score: dp[0][idx].miss_score - skip_penalty(idx, ch, Action::Miss),
            last_action_miss: Action::Miss,
            match_score: AWFUL_SCORE,
            last_action_match: Action::Miss,
        };
    }

    // build the matrix
    let mut pat_prev_ch = '\0';
    for (pat_idx, &pat_ch) in pattern.iter().enumerate() {
        let current_row_idx = if compressed {
            (pat_idx + 1) & 1
        } else {
            pat_idx + 1
        };
        let prev_row_idx = if compressed { pat_idx & 1 } else { pat_idx };

        let mut line_prev_ch = '\0';
        for (line_idx, &line_ch) in line.iter().enumerate() {
            if line_idx < pat_idx {
                line_prev_ch = line_ch;
                continue;
            }

            // what if we skip current line character?
            // we need to calculate the cases where the pre line character is matched/missed
            let pre_miss = &dp[current_row_idx][line_idx];
            let mut match_miss_score = pre_miss.match_score;
            let mut miss_miss_score = pre_miss.miss_score;
            if pat_idx < num_pattern_chars - 1 {
                match_miss_score -= skip_penalty(line_idx, line_ch, Action::Match);
                miss_miss_score -= skip_penalty(line_idx, line_ch, Action::Miss);
            }

            let (miss_score, last_action_miss) = if match_miss_score > miss_miss_score {
                (match_miss_score, Action::Match)
            } else {
                (miss_miss_score, Action::Miss)
            };

            // what if we want to match current line character?
            // so we need to calculate the cases where the pre pattern character is matched/missed
            let pre_match = &dp[prev_row_idx][line_idx];
            let match_match_score = if allow_match(pat_ch, line_ch, case_sensitive) {
                pre_match.match_score
                    + match_bonus(
                        pat_idx,
                        pat_ch,
                        pat_prev_ch,
                        line_idx,
                        line_ch,
                        line_prev_ch,
                        Action::Match,
                    )
            } else {
                AWFUL_SCORE
            };

            let miss_match_score = if allow_match(pat_ch, line_ch, case_sensitive) {
                pre_match.miss_score
                    + match_bonus(
                        pat_idx,
                        pat_ch,
                        pat_prev_ch,
                        line_idx,
                        line_ch,
                        line_prev_ch,
                        Action::Match,
                    )
            } else {
                AWFUL_SCORE
            };

            let (match_score, last_action_match) = if match_match_score > miss_match_score {
                (match_match_score, Action::Match)
            } else {
                (miss_match_score, Action::Miss)
            };

            dp[current_row_idx][line_idx + 1] = Score {
                miss_score,
                last_action_miss,
                match_score,
                last_action_match,
            };

            line_prev_ch = line_ch;
        }

        pat_prev_ch = pat_ch;
    }

    dp
}

fn adjust_score(score: ScoreType, num_line_chars: usize) -> ScoreType {
    // line width will affect 10 scores
    score - (((num_line_chars + 1) as f64).ln().floor() as ScoreType)
}

const AWFUL_SCORE: ScoreType = -(1 << 30);

#[derive(Debug, PartialEq, Clone, Copy)]
enum Action {
    Miss,
    Match,
}

#[derive(Debug, Clone, Copy)]
struct Score {
    pub last_action_miss: Action,
    pub last_action_match: Action,
    pub miss_score: ScoreType,
    pub match_score: ScoreType,
}

impl Default for Score {
    fn default() -> Self {
        Self {
            last_action_miss: Action::Miss,
            last_action_match: Action::Miss,
            miss_score: AWFUL_SCORE,
            match_score: AWFUL_SCORE,
        }
    }
}

fn skip_penalty(_ch_idx: usize, ch: char, last_action: Action) -> ScoreType {
    let mut score = 1;
    if last_action == Action::Match {
        // Non-consecutive match.
        score += 3;
    }

    if char_type_of(ch) == CharType::NonWord {
        // skip separator
        score += 6;
    }

    score
}

fn allow_match(pat_ch: char, line_ch: char, case_sensitive: bool) -> bool {
    char_equal(pat_ch, line_ch, case_sensitive)
}

fn match_bonus(
    pat_idx: usize,
    pat_ch: char,
    pat_prev_ch: char,
    line_idx: usize,
    line_ch: char,
    line_prev_ch: char,
    last_action: Action,
) -> ScoreType {
    let mut score = 10;
    let pat_role = char_role(pat_prev_ch, pat_ch);
    let line_role = char_role(line_prev_ch, line_ch);

    // Bonus: pattern so far is a (case-insensitive) prefix of the word.
    if pat_idx == line_idx {
        score += 10;
    }

    // Bonus: case match
    if pat_ch == line_ch {
        score += 8;
    }

    // Bonus: match header
    if line_role == CharRole::Head {
        score += 9;
    }

    // Bonus: a Head in the pattern aligns with one in the word.
    if pat_role == CharRole::Head && line_role == CharRole::Head {
        score += 10;
    }

    // Penalty: matching inside a segment (and previous char wasn't matched).
    if line_role == CharRole::Tail && pat_idx > 0 && last_action == Action::Miss {
        score -= 30;
    }

    // Penalty: a Head in the pattern matches in the middle of a word segment.
    if pat_role == CharRole::Head && line_role == CharRole::Tail {
        score -= 10;
    }

    // Penalty: matching the first pattern character in the middle of a segment.
    if pat_idx == 0 && line_role == CharRole::Tail {
        score -= 40;
    }

    score
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::util::{assert_order, wrap_matches};

    fn wrap_fuzzy_match(line: &str, pattern: &str) -> Option<String> {
        let (_score, indices) = fuzzy_indices(line, pattern)?;
        Some(wrap_matches(line, &indices))
    }

    #[test]
    fn test_match_or_not() {
        assert_eq!(None, fuzzy_match("abcdefaghi", "中"));
        assert_eq!(None, fuzzy_match("abc", "abx"));
        assert!(fuzzy_match("axbycz", "abc").is_some());
        assert!(fuzzy_match("axbycz", "xyz").is_some());

        assert_eq!("[a]x[b]y[c]z", &wrap_fuzzy_match("axbycz", "abc").unwrap());
        assert_eq!("a[x]b[y]c[z]", &wrap_fuzzy_match("axbycz", "xyz").unwrap());
        assert_eq!(
            "[H]ello, [世]界",
            &wrap_fuzzy_match("Hello, 世界", "H世").unwrap()
        );
    }

    #[test]
    fn test_match_quality() {
        let matcher = ClangdMatcher::default();
        // case
        assert_order(&matcher, "monad", &["monad", "Monad", "mONAD"]);

        // initials
        assert_order(&matcher, "ab", &["ab", "aoo_boo", "acb"]);
        assert_order(&matcher, "CC", &["CamelCase", "camelCase", "camelcase"]);
        assert_order(&matcher, "cC", &["camelCase", "CamelCase", "camelcase"]);
        assert_order(
            &matcher,
            "cc",
            &[
                "camel case",
                "camelCase",
                "camelcase",
                "CamelCase",
                "camel ace",
            ],
        );
        assert_order(
            &matcher,
            "Da.Te",
            &["Data.Text", "Data.Text.Lazy", "Data.Aeson.Encoding.text"],
        );
        assert_order(&matcher, "foobar.h", &["foobar.h", "foo/bar.h"]);
        // prefix
        assert_order(&matcher, "is", &["isIEEE", "inSuf"]);
        // shorter
        assert_order(&matcher, "ma", &["map", "many", "maximum"]);
        assert_order(&matcher, "print", &["printf", "sprintf"]);
        // score(PRINT) = kMinScore
        assert_order(&matcher, "ast", &["ast", "AST", "INT_FAST16_MAX"]);
        // score(PRINT) > kMinScore
        assert_order(&matcher, "Int", &["int", "INT", "PRINT"]);
    }
}

#[allow(dead_code)]
fn print_dp(line: &str, pattern: &str, dp: &[Vec<Score>]) {
    let num_line_chars = line.chars().count();
    let num_pattern_chars = pattern.chars().count();

    print!("\t");
    for (idx, ch) in line.chars().enumerate() {
        print!("\t\t{}/{}", idx + 1, ch);
    }

    for (row_num, row) in dp.iter().enumerate().take(num_pattern_chars + 1) {
        print!("\n{}\t", row_num);
        for cell in row.iter().take(num_line_chars + 1) {
            print!(
                "({},{})/({},{})\t",
                cell.miss_score,
                if cell.last_action_miss == Action::Miss {
                    'X'
                } else {
                    'O'
                },
                cell.match_score,
                if cell.last_action_match == Action::Miss {
                    'X'
                } else {
                    'O'
                }
            );
        }
    }
}

Coverage Report

Created: 2026-08-14 08:14

Line	Count	Source
1		///! The fuzzy matching algorithm used in clangd.
2		///! https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.cpp
3		///!
4		///! # Example:
5		///! ```edition2018
6		///! use fuzzy_matcher::FuzzyMatcher;
7		///! use fuzzy_matcher::clangd::ClangdMatcher;
8		///!
9		///! let matcher = ClangdMatcher::default();
10		///!
11		///! assert_eq!(None, matcher.fuzzy_match("abc", "abx"));
12		///! assert!(matcher.fuzzy_match("axbycz", "abc").is_some());
13		///! assert!(matcher.fuzzy_match("axbycz", "xyz").is_some());
14		///!
15		///! let (score, indices) = matcher.fuzzy_indices("axbycz", "abc").unwrap();
16		///! assert_eq!(indices, [0, 2, 4]);
17		///!
18		///! ```
19		///!
20		///! Algorithm modified from
21		///! https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.cpp
22		///! Also check: https://github.com/lewang/flx/issues/98
23		use crate::util::*;
24		use crate::{FuzzyMatcher, IndexType, ScoreType};
25		use std::cell::RefCell;
26		use std::cmp::max;
27		use thread_local::CachedThreadLocal;
28
29		#[derive(Eq, PartialEq, Debug, Copy, Clone)]
30		enum CaseMatching {
31		Respect,
32		Ignore,
33		Smart,
34		}
35
36		pub struct ClangdMatcher {
37		case: CaseMatching,
38
39		use_cache: bool,
40
41		c_cache: CachedThreadLocal<RefCell<Vec<char>>>, // vector to store the characters of choice
42		p_cache: CachedThreadLocal<RefCell<Vec<char>>>, // vector to store the characters of pattern
43		}
44
45		impl Default for ClangdMatcher {
46	0	fn default() -> Self {
47	0	Self {
48	0	case: CaseMatching::Ignore,
49	0	use_cache: true,
50	0	c_cache: CachedThreadLocal::new(),
51	0	p_cache: CachedThreadLocal::new(),
52	0	}
53	0	}
54		}
55
56		impl ClangdMatcher {
57	0	pub fn ignore_case(mut self) -> Self {
58	0	self.case = CaseMatching::Ignore;
59	0	self
60	0	}
61
62	0	pub fn smart_case(mut self) -> Self {
63	0	self.case = CaseMatching::Smart;
64	0	self
65	0	}
66
67	0	pub fn respect_case(mut self) -> Self {
68	0	self.case = CaseMatching::Respect;
69	0	self
70	0	}
71
72	0	pub fn use_cache(mut self, use_cache: bool) -> Self {
73	0	self.use_cache = use_cache;
74	0	self
75	0	}
76
77	0	fn contains_upper(&self, string: &str) -> bool {
78	0	for ch in string.chars() {
79	0	if ch.is_ascii_uppercase() {
80	0	return true;
81	0	}
82		}
83
84	0	false
85	0	}
86
87	0	fn is_case_sensitive(&self, pattern: &str) -> bool {
88	0	match self.case {
89	0	CaseMatching::Respect => true,
90	0	CaseMatching::Ignore => false,
91	0	CaseMatching::Smart => self.contains_upper(pattern),
92		}
93	0	}
94		}
95
96		impl FuzzyMatcher for ClangdMatcher {
97	0	fn fuzzy_indices(&self, choice: &str, pattern: &str) -> Option<(ScoreType, Vec<IndexType>)> {
98	0	let case_sensitive = self.is_case_sensitive(pattern);
99
100	0	let mut choice_chars = self
101	0	.c_cache
102	0	.get_or(\|\| RefCell::new(Vec::new()))
103	0	.borrow_mut();
104	0	let mut pattern_chars = self
105	0	.p_cache
106	0	.get_or(\|\| RefCell::new(Vec::new()))
107	0	.borrow_mut();
108
109	0	choice_chars.clear();
110	0	for char in choice.chars() {
111	0	choice_chars.push(char);
112	0	}
113
114	0	pattern_chars.clear();
115	0	for char in pattern.chars() {
116	0	pattern_chars.push(char);
117	0	}
118
119	0	if cheap_matches(&choice_chars, &pattern_chars, case_sensitive).is_none() {
120	0	return None;
121	0	}
122
123	0	let num_pattern_chars = pattern_chars.len();
124	0	let num_choice_chars = choice_chars.len();
125
126	0	let dp = build_graph(&choice_chars, &pattern_chars, false, case_sensitive);
127
128		// search backwards for the matched indices
129	0	let mut indices_reverse = Vec::with_capacity(num_pattern_chars);
130	0	let cell = dp[num_pattern_chars][num_choice_chars];
131
132	0	let (mut last_action, score) = if cell.match_score > cell.miss_score {
133	0	(Action::Match, cell.match_score)
134		} else {
135	0	(Action::Miss, cell.miss_score)
136		};
137
138	0	let mut row = num_pattern_chars;
139	0	let mut col = num_choice_chars;
140
141	0	while row > 0 \|\| col > 0 {
142	0	if last_action == Action::Match {
143	0	indices_reverse.push((col - 1) as IndexType);
144	0	}
145
146	0	let cell = &dp[row][col];
147	0	if last_action == Action::Match {
148	0	last_action = cell.last_action_match;
149	0	row -= 1;
150	0	col -= 1;
151	0	} else {
152	0	last_action = cell.last_action_miss;
153	0	col -= 1;
154	0	}
155		}
156
157	0	if !self.use_cache {
158		// drop the allocated memory
159	0	self.c_cache.get().map(\|cell\| cell.replace(vec![]));
160	0	self.p_cache.get().map(\|cell\| cell.replace(vec![]));
161	0	}
162
163	0	indices_reverse.reverse();
164	0	Some((adjust_score(score, num_choice_chars), indices_reverse))
165	0	}
166
167	0	fn fuzzy_match(&self, choice: &str, pattern: &str) -> Option<ScoreType> {
168	0	let case_sensitive = self.is_case_sensitive(pattern);
169
170	0	let mut choice_chars = self
171	0	.c_cache
172	0	.get_or(\|\| RefCell::new(Vec::new()))
173	0	.borrow_mut();
174	0	let mut pattern_chars = self
175	0	.p_cache
176	0	.get_or(\|\| RefCell::new(Vec::new()))
177	0	.borrow_mut();
178
179	0	choice_chars.clear();
180	0	for char in choice.chars() {
181	0	choice_chars.push(char);
182	0	}
183
184	0	pattern_chars.clear();
185	0	for char in pattern.chars() {
186	0	pattern_chars.push(char);
187	0	}
188
189	0	if cheap_matches(&choice_chars, &pattern_chars, case_sensitive).is_none() {
190	0	return None;
191	0	}
192
193	0	let num_pattern_chars = pattern_chars.len();
194	0	let num_choice_chars = choice_chars.len();
195
196	0	let dp = build_graph(&choice_chars, &pattern_chars, true, case_sensitive);
197
198	0	let cell = dp[num_pattern_chars & 1][num_choice_chars];
199	0	let score = max(cell.match_score, cell.miss_score);
200
201	0	if !self.use_cache {
202		// drop the allocated memory
203	0	self.c_cache.get().map(\|cell\| cell.replace(vec![]));
204	0	self.p_cache.get().map(\|cell\| cell.replace(vec![]));
205	0	}
206
207	0	Some(adjust_score(score, num_choice_chars))
208	0	}
209		}
210
211		/// fuzzy match `line` with `pattern`, returning the score and indices of matches
212	0	pub fn fuzzy_indices(line: &str, pattern: &str) -> Option<(ScoreType, Vec<IndexType>)> {
213	0	ClangdMatcher::default()
214	0	.ignore_case()
215	0	.fuzzy_indices(line, pattern)
216	0	}
217
218		/// fuzzy match `line` with `pattern`, returning the score(the larger the better) on match
219	0	pub fn fuzzy_match(line: &str, pattern: &str) -> Option<ScoreType> {
220	0	ClangdMatcher::default()
221	0	.ignore_case()
222	0	.fuzzy_match(line, pattern)
223	0	}
224
225		// checkout https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.cpp
226		// for the description
227	0	fn build_graph(
228	0	line: &[char],
229	0	pattern: &[char],
230	0	compressed: bool,
231	0	case_sensitive: bool,
232	0	) -> Vec<Vec<Score>> {
233	0	let num_line_chars = line.len();
234	0	let num_pattern_chars = pattern.len();
235	0	let max_rows = if compressed { 2 } else { num_pattern_chars + 1 };
236
237	0	let mut dp: Vec<Vec<Score>> = Vec::with_capacity(max_rows);
238
239	0	for _ in 0..max_rows {
240	0	dp.push(vec![Score::default(); num_line_chars + 1]);
241	0	}
242
243	0	dp[0][0].miss_score = 0;
244
245		// first line
246	0	for (idx, &ch) in line.iter().enumerate() {
247	0	dp[0][idx + 1] = Score {
248	0	miss_score: dp[0][idx].miss_score - skip_penalty(idx, ch, Action::Miss),
249	0	last_action_miss: Action::Miss,
250	0	match_score: AWFUL_SCORE,
251	0	last_action_match: Action::Miss,
252	0	};
253	0	}
254
255		// build the matrix
256	0	let mut pat_prev_ch = '\0';
257	0	for (pat_idx, &pat_ch) in pattern.iter().enumerate() {
258	0	let current_row_idx = if compressed {
259	0	(pat_idx + 1) & 1
260		} else {
261	0	pat_idx + 1
262		};
263	0	let prev_row_idx = if compressed { pat_idx & 1 } else { pat_idx };
264
265	0	let mut line_prev_ch = '\0';
266	0	for (line_idx, &line_ch) in line.iter().enumerate() {
267	0	if line_idx < pat_idx {
268	0	line_prev_ch = line_ch;
269	0	continue;
270	0	}
271
272		// what if we skip current line character?
273		// we need to calculate the cases where the pre line character is matched/missed
274	0	let pre_miss = &dp[current_row_idx][line_idx];
275	0	let mut match_miss_score = pre_miss.match_score;
276	0	let mut miss_miss_score = pre_miss.miss_score;
277	0	if pat_idx < num_pattern_chars - 1 {
278	0	match_miss_score -= skip_penalty(line_idx, line_ch, Action::Match);
279	0	miss_miss_score -= skip_penalty(line_idx, line_ch, Action::Miss);
280	0	}
281
282	0	let (miss_score, last_action_miss) = if match_miss_score > miss_miss_score {
283	0	(match_miss_score, Action::Match)
284		} else {
285	0	(miss_miss_score, Action::Miss)
286		};
287
288		// what if we want to match current line character?
289		// so we need to calculate the cases where the pre pattern character is matched/missed
290	0	let pre_match = &dp[prev_row_idx][line_idx];
291	0	let match_match_score = if allow_match(pat_ch, line_ch, case_sensitive) {
292	0	pre_match.match_score
293	0	+ match_bonus(
294	0	pat_idx,
295	0	pat_ch,
296	0	pat_prev_ch,
297	0	line_idx,
298	0	line_ch,
299	0	line_prev_ch,
300	0	Action::Match,
301	0	)
302		} else {
303	0	AWFUL_SCORE
304		};
305
306	0	let miss_match_score = if allow_match(pat_ch, line_ch, case_sensitive) {
307	0	pre_match.miss_score
308	0	+ match_bonus(
309	0	pat_idx,
310	0	pat_ch,
311	0	pat_prev_ch,
312	0	line_idx,
313	0	line_ch,
314	0	line_prev_ch,
315	0	Action::Match,
316	0	)
317		} else {
318	0	AWFUL_SCORE
319		};
320
321	0	let (match_score, last_action_match) = if match_match_score > miss_match_score {
322	0	(match_match_score, Action::Match)
323		} else {
324	0	(miss_match_score, Action::Miss)
325		};
326
327	0	dp[current_row_idx][line_idx + 1] = Score {
328	0	miss_score,
329	0	last_action_miss,
330	0	match_score,
331	0	last_action_match,
332	0	};
333
334	0	line_prev_ch = line_ch;
335		}
336
337	0	pat_prev_ch = pat_ch;
338		}
339
340	0	dp
341	0	}
342
343	0	fn adjust_score(score: ScoreType, num_line_chars: usize) -> ScoreType {
344		// line width will affect 10 scores
345	0	score - (((num_line_chars + 1) as f64).ln().floor() as ScoreType)
346	0	}
347
348		const AWFUL_SCORE: ScoreType = -(1 << 30);
349
350		#[derive(Debug, PartialEq, Clone, Copy)]
351		enum Action {
352		Miss,
353		Match,
354		}
355
356		#[derive(Debug, Clone, Copy)]
357		struct Score {
358		pub last_action_miss: Action,
359		pub last_action_match: Action,
360		pub miss_score: ScoreType,
361		pub match_score: ScoreType,
362		}
363
364		impl Default for Score {
365	0	fn default() -> Self {
366	0	Self {
367	0	last_action_miss: Action::Miss,
368	0	last_action_match: Action::Miss,
369	0	miss_score: AWFUL_SCORE,
370	0	match_score: AWFUL_SCORE,
371	0	}
372	0	}
373		}
374
375	0	fn skip_penalty(_ch_idx: usize, ch: char, last_action: Action) -> ScoreType {
376	0	let mut score = 1;
377	0	if last_action == Action::Match {
378	0	// Non-consecutive match.
379	0	score += 3;
380	0	}
381
382	0	if char_type_of(ch) == CharType::NonWord {
383	0	// skip separator
384	0	score += 6;
385	0	}
386
387	0	score
388	0	}
389
390	0	fn allow_match(pat_ch: char, line_ch: char, case_sensitive: bool) -> bool {
391	0	char_equal(pat_ch, line_ch, case_sensitive)
392	0	}
393
394	0	fn match_bonus(
395	0	pat_idx: usize,
396	0	pat_ch: char,
397	0	pat_prev_ch: char,
398	0	line_idx: usize,
399	0	line_ch: char,
400	0	line_prev_ch: char,
401	0	last_action: Action,
402	0	) -> ScoreType {
403	0	let mut score = 10;
404	0	let pat_role = char_role(pat_prev_ch, pat_ch);
405	0	let line_role = char_role(line_prev_ch, line_ch);
406
407		// Bonus: pattern so far is a (case-insensitive) prefix of the word.
408	0	if pat_idx == line_idx {
409	0	score += 10;
410	0	}
411
412		// Bonus: case match
413	0	if pat_ch == line_ch {
414	0	score += 8;
415	0	}
416
417		// Bonus: match header
418	0	if line_role == CharRole::Head {
419	0	score += 9;
420	0	}
421
422		// Bonus: a Head in the pattern aligns with one in the word.
423	0	if pat_role == CharRole::Head && line_role == CharRole::Head {
424	0	score += 10;
425	0	}
426
427		// Penalty: matching inside a segment (and previous char wasn't matched).
428	0	if line_role == CharRole::Tail && pat_idx > 0 && last_action == Action::Miss {
429	0	score -= 30;
430	0	}
431
432		// Penalty: a Head in the pattern matches in the middle of a word segment.
433	0	if pat_role == CharRole::Head && line_role == CharRole::Tail {
434	0	score -= 10;
435	0	}
436
437		// Penalty: matching the first pattern character in the middle of a segment.
438	0	if pat_idx == 0 && line_role == CharRole::Tail {
439	0	score -= 40;
440	0	}
441
442	0	score
443	0	}
444
445		#[cfg(test)]
446		mod tests {
447		use super::*;
448		use crate::util::{assert_order, wrap_matches};
449
450		fn wrap_fuzzy_match(line: &str, pattern: &str) -> Option<String> {
451		let (_score, indices) = fuzzy_indices(line, pattern)?;
452		Some(wrap_matches(line, &indices))
453		}
454
455		#[test]
456		fn test_match_or_not() {
457		assert_eq!(None, fuzzy_match("abcdefaghi", "中"));
458		assert_eq!(None, fuzzy_match("abc", "abx"));
459		assert!(fuzzy_match("axbycz", "abc").is_some());
460		assert!(fuzzy_match("axbycz", "xyz").is_some());
461
462		assert_eq!("[a]x[b]y[c]z", &wrap_fuzzy_match("axbycz", "abc").unwrap());
463		assert_eq!("a[x]b[y]c[z]", &wrap_fuzzy_match("axbycz", "xyz").unwrap());
464		assert_eq!(
465		"[H]ello, [世]界",
466		&wrap_fuzzy_match("Hello, 世界", "H世").unwrap()
467		);
468		}
469
470		#[test]
471		fn test_match_quality() {
472		let matcher = ClangdMatcher::default();
473		// case
474		assert_order(&matcher, "monad", &["monad", "Monad", "mONAD"]);
475
476		// initials
477		assert_order(&matcher, "ab", &["ab", "aoo_boo", "acb"]);
478		assert_order(&matcher, "CC", &["CamelCase", "camelCase", "camelcase"]);
479		assert_order(&matcher, "cC", &["camelCase", "CamelCase", "camelcase"]);
480		assert_order(
481		&matcher,
482		"cc",
483		&[
484		"camel case",
485		"camelCase",
486		"camelcase",
487		"CamelCase",
488		"camel ace",
489		],
490		);
491		assert_order(
492		&matcher,
493		"Da.Te",
494		&["Data.Text", "Data.Text.Lazy", "Data.Aeson.Encoding.text"],
495		);
496		assert_order(&matcher, "foobar.h", &["foobar.h", "foo/bar.h"]);
497		// prefix
498		assert_order(&matcher, "is", &["isIEEE", "inSuf"]);
499		// shorter
500		assert_order(&matcher, "ma", &["map", "many", "maximum"]);
501		assert_order(&matcher, "print", &["printf", "sprintf"]);
502		// score(PRINT) = kMinScore
503		assert_order(&matcher, "ast", &["ast", "AST", "INT_FAST16_MAX"]);
504		// score(PRINT) > kMinScore
505		assert_order(&matcher, "Int", &["int", "INT", "PRINT"]);
506		}
507		}
508
509		#[allow(dead_code)]
510	0	fn print_dp(line: &str, pattern: &str, dp: &[Vec<Score>]) {
511	0	let num_line_chars = line.chars().count();
512	0	let num_pattern_chars = pattern.chars().count();
513
514	0	print!("\t");
515	0	for (idx, ch) in line.chars().enumerate() {
516	0	print!("\t\t{}/{}", idx + 1, ch);
517	0	}
518
519	0	for (row_num, row) in dp.iter().enumerate().take(num_pattern_chars + 1) {
520	0	print!("\n{}\t", row_num);
521	0	for cell in row.iter().take(num_line_chars + 1) {
522	0	print!(
523		"({},{})/({},{})\t",
524		cell.miss_score,
525	0	if cell.last_action_miss == Action::Miss {
526	0	'X'
527		} else {
528	0	'O'
529		},
530		cell.match_score,
531	0	if cell.last_action_match == Action::Miss {
532	0	'X'
533		} else {
534	0	'O'
535		}
536		);
537		}
538		}
539	0	}