nucleo_matcher/lib.rs
1/*!
2`nucleo_matcher` is a low level crate that contains the matcher implementation
3used by the high level `nucleo` crate.
4
5**NOTE**: If you are building an fzf-like interactive fuzzy finder that is
6meant to match a reasonably large number of items (> 100) using the high level
7`nucleo` crate is highly recommended. Using `nucleo-matcher` directly in you ui
8loop will be very slow. Implementing this logic yourself is very complex.
9
10The matcher is hightly optimized and can significantly outperform `fzf` and
11`skim` (the `fuzzy-matcher` crate). However some of these optimizations require
12a slightly less convenient API. Be sure to carefully read the documentation of
13the [`Matcher`] to avoid unexpected behaviour.
14# Examples
15
16For almost all usecases the [`pattern`] API should be used instead of calling
17the matcher methods directly. [`Pattern::parse`](pattern::Pattern::parse) will
18construct a single Atom (a single match operation) for each word. The pattern
19can contain special characters to control what kind of match is performed (see
20[`AtomKind`](crate::pattern::AtomKind)).
21
22```
23# use nucleo_matcher::{Matcher, Config};
24# use nucleo_matcher::pattern::{Pattern, Normalization, CaseMatching};
25let paths = ["foo/bar", "bar/foo", "foobar"];
26let mut matcher = Matcher::new(Config::DEFAULT.match_paths());
27let matches = Pattern::parse("foo bar", CaseMatching::Ignore, Normalization::Smart).match_list(paths, &mut matcher);
28assert_eq!(matches, vec![("foo/bar", 168), ("bar/foo", 168), ("foobar", 140)]);
29let matches = Pattern::parse("^foo bar", CaseMatching::Ignore, Normalization::Smart).match_list(paths, &mut matcher);
30assert_eq!(matches, vec![("foo/bar", 168), ("foobar", 140)]);
31```
32
33If the pattern should be matched literally (without this special parsing)
34[`Pattern::new`](pattern::Pattern::new) can be used instead.
35
36```
37# use nucleo_matcher::{Matcher, Config};
38# use nucleo_matcher::pattern::{Pattern, CaseMatching, AtomKind, Normalization};
39let paths = ["foo/bar", "bar/foo", "foobar"];
40let mut matcher = Matcher::new(Config::DEFAULT.match_paths());
41let matches = Pattern::new("foo bar", CaseMatching::Ignore, Normalization::Smart, AtomKind::Fuzzy).match_list(paths, &mut matcher);
42assert_eq!(matches, vec![("foo/bar", 168), ("bar/foo", 168), ("foobar", 140)]);
43let paths = ["^foo/bar", "bar/^foo", "foobar"];
44let matches = Pattern::new("^foo bar", CaseMatching::Ignore, Normalization::Smart, AtomKind::Fuzzy).match_list(paths, &mut matcher);
45assert_eq!(matches, vec![("^foo/bar", 188), ("bar/^foo", 188)]);
46```
47
48Word segmentation is performed automatically on any unescaped character for which [`is_whitespace`](char::is_whitespace) returns true.
49This is relevant, for instance, with non-english keyboard input.
50
51```
52# use nucleo_matcher::pattern::{Atom, Pattern, Normalization, CaseMatching};
53assert_eq!(
54 // double-width 'Ideographic Space', i.e. `'\u{3000}'`
55 Pattern::parse("ほげ ふが", CaseMatching::Smart, Normalization::Smart).atoms,
56 vec![
57 Atom::parse("ほげ", CaseMatching::Smart, Normalization::Smart),
58 Atom::parse("ふが", CaseMatching::Smart, Normalization::Smart),
59 ],
60);
61```
62
63If word segmentation is also not desired, a single `Atom` can be constructed directly.
64
65```
66# use nucleo_matcher::{Matcher, Config};
67# use nucleo_matcher::pattern::{Pattern, Atom, CaseMatching, Normalization, AtomKind};
68let paths = ["foobar", "foo bar"];
69let mut matcher = Matcher::new(Config::DEFAULT);
70let matches = Atom::new("foo bar", CaseMatching::Ignore, Normalization::Smart, AtomKind::Fuzzy, false).match_list(paths, &mut matcher);
71assert_eq!(matches, vec![("foo bar", 192)]);
72```
73
74
75# Status
76
77Nucleo is used in the helix-editor and therefore has a large user base with lots or real world testing. The core matcher implementation is considered complete and is unlikely to see major changes. The `nucleo-matcher` crate is finished and ready for widespread use, breaking changes should be very rare (a 1.0 release should not be far away).
78
79*/
80
81// sadly ranges don't optmimzie well
82#![allow(clippy::manual_range_contains)]
83#![warn(missing_docs)]
84
85pub mod chars;
86mod config;
87#[cfg(test)]
88mod debug;
89mod exact;
90mod fuzzy_greedy;
91mod fuzzy_optimal;
92mod matrix;
93pub mod pattern;
94mod prefilter;
95mod score;
96mod utf32_str;
97
98#[cfg(test)]
99mod tests;
100
101pub use crate::config::Config;
102pub use crate::utf32_str::{Utf32Str, Utf32String};
103
104use crate::chars::{AsciiChar, Char};
105use crate::matrix::MatrixSlab;
106
107/// A matcher engine that can execute (fuzzy) matches.
108///
109/// A matches contains **heap allocated** scratch memory that is reused during
110/// matching. This scratch memory allows the matcher to guarantee that it will
111/// **never allocate** during matching (with the exception of pushing to the
112/// `indices` vector if there isn't enough capacity). However this scratch
113/// memory is fairly large (around 135KB) so creating a matcher is expensive.
114///
115/// All `.._match` functions will not compute the indices of the matched
116/// characters. These should be used to prefilter to filter and rank all
117/// matches. All `.._indices` functions will also compute the indices of the
118/// matched characters but are slower compared to the `..match` variant. These
119/// should be used when rendering the best N matches. Note that the `indices`
120/// argument is **never cleared**. This allows running multiple different
121/// matches on the same haystack and merging the indices by sorting and
122/// deduplicating the vector.
123///
124/// The `needle` argument for each function must always be normalized by the
125/// caller (unicode normalization and case folding). Otherwise, the matcher
126/// may fail to produce a match. The [`pattern`] modules provides utilities
127/// to preprocess needles and **should usually be preferred over invoking the
128/// matcher directly**. Additionally it's recommend to perform separate matches
129/// for each word in the needle. Consider the folloling example:
130///
131/// If `foo bar` is used as the needle it matches both `foo test baaar` and
132/// `foo hello-world bar`. However, `foo test baaar` will receive a higher
133/// score than `foo hello-world bar`. `baaar` contains a 2 character gap which
134/// will receive a penalty and therefore the user will likely expect it to rank
135/// lower. However, if `foo bar` is matched as a single query `hello-world` and
136/// `test` are both considered gaps too. As `hello-world` is a much longer gap
137/// then `test` the extra penalty for `baaar` is canceled out. If both words
138/// are matched individually the interspersed words do not receive a penalty and
139/// `foo hello-world bar` ranks higher.
140///
141/// In general nucleo is a **substring matching tool** (except for the prefix/
142/// postfix matching modes) with no penalty assigned to matches that start
143/// later within the same pattern (which enables matching words individually
144/// as shown above). If patterns show a large variety in length and the syntax
145/// described above is not used it may be preferable to give preference to
146/// matches closer to the start of a haystack. To accommodate that usecase the
147/// [`prefer_prefix`](Config::prefer_prefix) option can be set to true.
148///
149/// Matching is limited to 2^32-1 codepoints, if the haystack is longer than
150/// that the matcher **will panic**. The caller must decide whether it wants to
151/// filter out long haystacks or truncate them.
152pub struct Matcher {
153 #[allow(missing_docs)]
154 pub config: Config,
155 slab: MatrixSlab,
156}
157
158// this is just here for convenience not sure if we should implement this
159impl Clone for Matcher {
160 fn clone(&self) -> Self {
161 Matcher {
162 config: self.config.clone(),
163 slab: MatrixSlab::new(),
164 }
165 }
166}
167
168impl std::fmt::Debug for Matcher {
169 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
170 f.debug_struct("Matcher")
171 .field("config", &self.config)
172 .finish_non_exhaustive()
173 }
174}
175
176impl Default for Matcher {
177 fn default() -> Self {
178 Matcher {
179 config: Config::DEFAULT,
180 slab: MatrixSlab::new(),
181 }
182 }
183}
184
185impl Matcher {
186 /// Creates a new matcher instance, note that this will eagerly allocate a
187 /// fairly large chunk of heap memory (around 135KB currently but subject to
188 /// change) so matchers should be reused if called often (like in a loop).
189 pub fn new(config: Config) -> Self {
190 Self {
191 config,
192 slab: MatrixSlab::new(),
193 }
194 }
195
196 /// Find the fuzzy match with the highest score in the `haystack`.
197 ///
198 /// This functions has `O(mn)` time complexity for short inputs.
199 /// To avoid slowdowns it automatically falls back to
200 /// [greedy matching](crate::Matcher::fuzzy_match_greedy) for large
201 /// needles and haystacks.
202 ///
203 /// See the [matcher documentation](crate::Matcher) for more details.
204 pub fn fuzzy_match(&mut self, haystack: Utf32Str<'_>, needle: Utf32Str<'_>) -> Option<u16> {
205 assert!(haystack.len() <= u32::MAX as usize);
206 self.fuzzy_matcher_impl::<false>(haystack, needle, &mut Vec::new())
207 }
208
209 /// Find the fuzzy match with the highest score in the `haystack` and
210 /// compute its indices.
211 ///
212 /// This functions has `O(mn)` time complexity for short inputs. To
213 /// avoid slowdowns it automatically falls back to
214 /// [greedy matching](crate::Matcher::fuzzy_match_greedy) for large needles
215 /// and haystacks
216 ///
217 /// See the [matcher documentation](crate::Matcher) for more details.
218 pub fn fuzzy_indices(
219 &mut self,
220 haystack: Utf32Str<'_>,
221 needle: Utf32Str<'_>,
222 indices: &mut Vec<u32>,
223 ) -> Option<u16> {
224 assert!(haystack.len() <= u32::MAX as usize);
225 self.fuzzy_matcher_impl::<true>(haystack, needle, indices)
226 }
227
228 fn fuzzy_matcher_impl<const INDICES: bool>(
229 &mut self,
230 haystack_: Utf32Str<'_>,
231 needle_: Utf32Str<'_>,
232 indices: &mut Vec<u32>,
233 ) -> Option<u16> {
234 if needle_.len() > haystack_.len() {
235 return None;
236 }
237 if needle_.is_empty() {
238 return Some(0);
239 }
240 if needle_.len() == haystack_.len() {
241 return self.exact_match_impl::<INDICES>(
242 haystack_,
243 needle_,
244 0,
245 haystack_.len(),
246 indices,
247 );
248 }
249 assert!(
250 haystack_.len() <= u32::MAX as usize,
251 "fuzzy matching is only support for up to 2^32-1 codepoints"
252 );
253 match (haystack_, needle_) {
254 (Utf32Str::Ascii(haystack), Utf32Str::Ascii(needle)) => {
255 if let &[needle] = needle {
256 return self.substring_match_1_ascii::<INDICES>(haystack, needle, indices);
257 }
258 let (start, greedy_end, end) = self.prefilter_ascii(haystack, needle, false)?;
259 if needle_.len() == end - start {
260 return Some(self.calculate_score::<INDICES, _, _>(
261 AsciiChar::cast(haystack),
262 AsciiChar::cast(needle),
263 start,
264 greedy_end,
265 indices,
266 ));
267 }
268 self.fuzzy_match_optimal::<INDICES, AsciiChar, AsciiChar>(
269 AsciiChar::cast(haystack),
270 AsciiChar::cast(needle),
271 start,
272 greedy_end,
273 end,
274 indices,
275 )
276 }
277 (Utf32Str::Ascii(_), Utf32Str::Unicode(_)) => {
278 // a purely ascii haystack can never be transformed to match
279 // a needle that contains non-ascii chars since we don't allow gaps
280 None
281 }
282 (Utf32Str::Unicode(haystack), Utf32Str::Ascii(needle)) => {
283 if let &[needle] = needle {
284 let (start, _) = self.prefilter_non_ascii(haystack, needle_, true)?;
285 let res = self.substring_match_1_non_ascii::<INDICES>(
286 haystack,
287 needle as char,
288 start,
289 indices,
290 );
291 return Some(res);
292 }
293 let (start, end) = self.prefilter_non_ascii(haystack, needle_, false)?;
294 if needle_.len() == end - start {
295 return self
296 .exact_match_impl::<INDICES>(haystack_, needle_, start, end, indices);
297 }
298 self.fuzzy_match_optimal::<INDICES, char, AsciiChar>(
299 haystack,
300 AsciiChar::cast(needle),
301 start,
302 start + 1,
303 end,
304 indices,
305 )
306 }
307 (Utf32Str::Unicode(haystack), Utf32Str::Unicode(needle)) => {
308 if let &[needle] = needle {
309 let (start, _) = self.prefilter_non_ascii(haystack, needle_, true)?;
310 let res = self
311 .substring_match_1_non_ascii::<INDICES>(haystack, needle, start, indices);
312 return Some(res);
313 }
314 let (start, end) = self.prefilter_non_ascii(haystack, needle_, false)?;
315 if needle_.len() == end - start {
316 return self
317 .exact_match_impl::<INDICES>(haystack_, needle_, start, end, indices);
318 }
319 self.fuzzy_match_optimal::<INDICES, char, char>(
320 haystack,
321 needle,
322 start,
323 start + 1,
324 end,
325 indices,
326 )
327 }
328 }
329 }
330
331 /// Greedly find a fuzzy match in the `haystack`.
332 ///
333 /// This functions has `O(n)` time complexity but may provide unintutive (non-optimal)
334 /// indices and scores. Usually [fuzzy_match](crate::Matcher::fuzzy_match) should
335 /// be preferred.
336 ///
337 /// See the [matcher documentation](crate::Matcher) for more details.
338 pub fn fuzzy_match_greedy(
339 &mut self,
340 haystack: Utf32Str<'_>,
341 needle: Utf32Str<'_>,
342 ) -> Option<u16> {
343 assert!(haystack.len() <= u32::MAX as usize);
344 self.fuzzy_match_greedy_impl::<false>(haystack, needle, &mut Vec::new())
345 }
346
347 /// Greedly find a fuzzy match in the `haystack` and compute its indices.
348 ///
349 /// This functions has `O(n)` time complexity but may provide unintuitive (non-optimal)
350 /// indices and scores. Usually [fuzzy_indices](crate::Matcher::fuzzy_indices) should
351 /// be preferred.
352 ///
353 /// See the [matcher documentation](crate::Matcher) for more details.
354 pub fn fuzzy_indices_greedy(
355 &mut self,
356 haystack: Utf32Str<'_>,
357 needle: Utf32Str<'_>,
358 indices: &mut Vec<u32>,
359 ) -> Option<u16> {
360 assert!(haystack.len() <= u32::MAX as usize);
361 self.fuzzy_match_greedy_impl::<true>(haystack, needle, indices)
362 }
363
364 fn fuzzy_match_greedy_impl<const INDICES: bool>(
365 &mut self,
366 haystack: Utf32Str<'_>,
367 needle_: Utf32Str<'_>,
368 indices: &mut Vec<u32>,
369 ) -> Option<u16> {
370 if needle_.len() > haystack.len() {
371 return None;
372 }
373 if needle_.is_empty() {
374 return Some(0);
375 }
376 if needle_.len() == haystack.len() {
377 return self.exact_match_impl::<INDICES>(haystack, needle_, 0, haystack.len(), indices);
378 }
379 assert!(
380 haystack.len() <= u32::MAX as usize,
381 "matching is only support for up to 2^32-1 codepoints"
382 );
383 match (haystack, needle_) {
384 (Utf32Str::Ascii(haystack), Utf32Str::Ascii(needle)) => {
385 let (start, greedy_end, _) = self.prefilter_ascii(haystack, needle, true)?;
386 if needle_.len() == greedy_end - start {
387 return Some(self.calculate_score::<INDICES, _, _>(
388 AsciiChar::cast(haystack),
389 AsciiChar::cast(needle),
390 start,
391 greedy_end,
392 indices,
393 ));
394 }
395 self.fuzzy_match_greedy_::<INDICES, AsciiChar, AsciiChar>(
396 AsciiChar::cast(haystack),
397 AsciiChar::cast(needle),
398 start,
399 greedy_end,
400 indices,
401 )
402 }
403 (Utf32Str::Ascii(_), Utf32Str::Unicode(_)) => {
404 // a purely ascii haystack can never be transformed to match
405 // a needle that contains non-ascii chars since we don't allow gaps
406 None
407 }
408 (Utf32Str::Unicode(haystack), Utf32Str::Ascii(needle)) => {
409 let (start, _) = self.prefilter_non_ascii(haystack, needle_, true)?;
410 self.fuzzy_match_greedy_::<INDICES, char, AsciiChar>(
411 haystack,
412 AsciiChar::cast(needle),
413 start,
414 start + 1,
415 indices,
416 )
417 }
418 (Utf32Str::Unicode(haystack), Utf32Str::Unicode(needle)) => {
419 let (start, _) = self.prefilter_non_ascii(haystack, needle_, true)?;
420 self.fuzzy_match_greedy_::<INDICES, char, char>(
421 haystack,
422 needle,
423 start,
424 start + 1,
425 indices,
426 )
427 }
428 }
429 }
430
431 /// Finds the substring match with the highest score in the `haystack`.
432 ///
433 /// This functions has `O(nm)` time complexity. However many cases can
434 /// be significantly accelerated using prefilters so it's usually very fast
435 /// in practice.
436 ///
437 /// See the [matcher documentation](crate::Matcher) for more details.
438 pub fn substring_match(
439 &mut self,
440 haystack: Utf32Str<'_>,
441 needle_: Utf32Str<'_>,
442 ) -> Option<u16> {
443 self.substring_match_impl::<false>(haystack, needle_, &mut Vec::new())
444 }
445
446 /// Finds the substring match with the highest score in the `haystack` and
447 /// compute its indices.
448 ///
449 /// This functions has `O(nm)` time complexity. However many cases can
450 /// be significantly accelerated using prefilters so it's usually fast
451 /// in practice.
452 ///
453 /// See the [matcher documentation](crate::Matcher) for more details.
454 pub fn substring_indices(
455 &mut self,
456 haystack: Utf32Str<'_>,
457 needle_: Utf32Str<'_>,
458 indices: &mut Vec<u32>,
459 ) -> Option<u16> {
460 self.substring_match_impl::<true>(haystack, needle_, indices)
461 }
462
463 fn substring_match_impl<const INDICES: bool>(
464 &mut self,
465 haystack: Utf32Str<'_>,
466 needle_: Utf32Str<'_>,
467 indices: &mut Vec<u32>,
468 ) -> Option<u16> {
469 if needle_.len() > haystack.len() {
470 return None;
471 }
472 if needle_.is_empty() {
473 return Some(0);
474 }
475 if needle_.len() == haystack.len() {
476 return self.exact_match_impl::<INDICES>(haystack, needle_, 0, haystack.len(), indices);
477 }
478 assert!(
479 haystack.len() <= u32::MAX as usize,
480 "matching is only support for up to 2^32-1 codepoints"
481 );
482 match (haystack, needle_) {
483 (Utf32Str::Ascii(haystack), Utf32Str::Ascii(needle)) => {
484 if let &[needle] = needle {
485 return self.substring_match_1_ascii::<INDICES>(haystack, needle, indices);
486 }
487 self.substring_match_ascii::<INDICES>(haystack, needle, indices)
488 }
489 (Utf32Str::Ascii(_), Utf32Str::Unicode(_)) => {
490 // a purely ascii haystack can never be transformed to match
491 // a needle that contains non-ascii chars since we don't allow gaps
492 None
493 }
494 (Utf32Str::Unicode(haystack), Utf32Str::Ascii(needle)) => {
495 if let &[needle] = needle {
496 let (start, _) = self.prefilter_non_ascii(haystack, needle_, true)?;
497 let res = self.substring_match_1_non_ascii::<INDICES>(
498 haystack,
499 needle as char,
500 start,
501 indices,
502 );
503 return Some(res);
504 }
505 let (start, _) = self.prefilter_non_ascii(haystack, needle_, false)?;
506 self.substring_match_non_ascii::<INDICES, _>(
507 haystack,
508 AsciiChar::cast(needle),
509 start,
510 indices,
511 )
512 }
513 (Utf32Str::Unicode(haystack), Utf32Str::Unicode(needle)) => {
514 if let &[needle] = needle {
515 let (start, _) = self.prefilter_non_ascii(haystack, needle_, true)?;
516 let res = self
517 .substring_match_1_non_ascii::<INDICES>(haystack, needle, start, indices);
518 return Some(res);
519 }
520 let (start, _) = self.prefilter_non_ascii(haystack, needle_, false)?;
521 self.substring_match_non_ascii::<INDICES, _>(haystack, needle, start, indices)
522 }
523 }
524 }
525
526 /// Checks whether needle and haystack match exactly.
527 ///
528 /// This functions has `O(n)` time complexity.
529 ///
530 /// See the [matcher documentation](crate::Matcher) for more details.
531 pub fn exact_match(&mut self, haystack: Utf32Str<'_>, needle: Utf32Str<'_>) -> Option<u16> {
532 if needle.is_empty() {
533 return Some(0);
534 }
535 let mut leading_space = 0;
536 let mut trailing_space = 0;
537 if !needle.first().is_whitespace() {
538 leading_space = haystack.leading_white_space()
539 }
540 if !needle.last().is_whitespace() {
541 trailing_space = haystack.trailing_white_space()
542 }
543 // avoid wraparound in size check
544 if trailing_space == haystack.len() {
545 return None;
546 }
547 self.exact_match_impl::<false>(
548 haystack,
549 needle,
550 leading_space,
551 haystack.len() - trailing_space,
552 &mut Vec::new(),
553 )
554 }
555
556 /// Checks whether needle and haystack match exactly and compute the matches indices.
557 ///
558 /// This functions has `O(n)` time complexity.
559 ///
560 /// See the [matcher documentation](crate::Matcher) for more details.
561 pub fn exact_indices(
562 &mut self,
563 haystack: Utf32Str<'_>,
564 needle: Utf32Str<'_>,
565 indices: &mut Vec<u32>,
566 ) -> Option<u16> {
567 if needle.is_empty() {
568 return Some(0);
569 }
570 let mut leading_space = 0;
571 let mut trailing_space = 0;
572 if !needle.first().is_whitespace() {
573 leading_space = haystack.leading_white_space()
574 }
575 if !needle.last().is_whitespace() {
576 trailing_space = haystack.trailing_white_space()
577 }
578 // avoid wraparound in size check
579 if trailing_space == haystack.len() {
580 return None;
581 }
582 self.exact_match_impl::<true>(
583 haystack,
584 needle,
585 leading_space,
586 haystack.len() - trailing_space,
587 indices,
588 )
589 }
590
591 /// Checks whether needle is a prefix of the haystack.
592 ///
593 /// This functions has `O(n)` time complexity.
594 ///
595 /// See the [matcher documentation](crate::Matcher) for more details.
596 pub fn prefix_match(&mut self, haystack: Utf32Str<'_>, needle: Utf32Str<'_>) -> Option<u16> {
597 if needle.is_empty() {
598 return Some(0);
599 }
600 let mut leading_space = 0;
601 if !needle.first().is_whitespace() {
602 leading_space = haystack.leading_white_space()
603 }
604 if haystack.len() - leading_space < needle.len() {
605 None
606 } else {
607 self.exact_match_impl::<false>(
608 haystack,
609 needle,
610 leading_space,
611 needle.len() + leading_space,
612 &mut Vec::new(),
613 )
614 }
615 }
616
617 /// Checks whether needle is a prefix of the haystack and compute the matches indices.
618 ///
619 /// This functions has `O(n)` time complexity.
620 ///
621 /// See the [matcher documentation](crate::Matcher) for more details.
622 pub fn prefix_indices(
623 &mut self,
624 haystack: Utf32Str<'_>,
625 needle: Utf32Str<'_>,
626 indices: &mut Vec<u32>,
627 ) -> Option<u16> {
628 if needle.is_empty() {
629 return Some(0);
630 }
631 let mut leading_space = 0;
632 if !needle.first().is_whitespace() {
633 leading_space = haystack.leading_white_space()
634 }
635 if haystack.len() - leading_space < needle.len() {
636 None
637 } else {
638 self.exact_match_impl::<true>(
639 haystack,
640 needle,
641 leading_space,
642 needle.len() + leading_space,
643 indices,
644 )
645 }
646 }
647
648 /// Checks whether needle is a postfix of the haystack.
649 ///
650 /// This functions has `O(n)` time complexity.
651 ///
652 /// See the [matcher documentation](crate::Matcher) for more details.
653 pub fn postfix_match(&mut self, haystack: Utf32Str<'_>, needle: Utf32Str<'_>) -> Option<u16> {
654 if needle.is_empty() {
655 return Some(0);
656 }
657 let mut trailing_spaces = 0;
658 if !needle.last().is_whitespace() {
659 trailing_spaces = haystack.trailing_white_space()
660 }
661 if haystack.len() - trailing_spaces < needle.len() {
662 None
663 } else {
664 self.exact_match_impl::<false>(
665 haystack,
666 needle,
667 haystack.len() - needle.len() - trailing_spaces,
668 haystack.len() - trailing_spaces,
669 &mut Vec::new(),
670 )
671 }
672 }
673
674 /// Checks whether needle is a postfix of the haystack and compute the matches indices.
675 ///
676 /// This functions has `O(n)` time complexity.
677 ///
678 /// See the [matcher documentation](crate::Matcher) for more details.
679 pub fn postfix_indices(
680 &mut self,
681 haystack: Utf32Str<'_>,
682 needle: Utf32Str<'_>,
683 indices: &mut Vec<u32>,
684 ) -> Option<u16> {
685 if needle.is_empty() {
686 return Some(0);
687 }
688 let mut trailing_spaces = 0;
689 if !needle.last().is_whitespace() {
690 trailing_spaces = haystack.trailing_white_space()
691 }
692 if haystack.len() - trailing_spaces < needle.len() {
693 None
694 } else {
695 self.exact_match_impl::<true>(
696 haystack,
697 needle,
698 haystack.len() - needle.len() - trailing_spaces,
699 haystack.len() - trailing_spaces,
700 indices,
701 )
702 }
703 }
704
705 fn exact_match_impl<const INDICES: bool>(
706 &mut self,
707 haystack: Utf32Str<'_>,
708 needle_: Utf32Str<'_>,
709 start: usize,
710 end: usize,
711 indices: &mut Vec<u32>,
712 ) -> Option<u16> {
713 if needle_.len() != end - start {
714 return None;
715 }
716 assert!(
717 haystack.len() <= u32::MAX as usize,
718 "matching is only support for up to 2^32-1 codepoints"
719 );
720 let score = match (haystack, needle_) {
721 (Utf32Str::Ascii(haystack), Utf32Str::Ascii(needle)) => {
722 let matched = if self.config.ignore_case {
723 AsciiChar::cast(haystack)[start..end]
724 .iter()
725 .map(|c| c.normalize(&self.config))
726 .eq(AsciiChar::cast(needle)
727 .iter()
728 .map(|c| c.normalize(&self.config)))
729 } else {
730 &haystack[start..end] == needle
731 };
732 if !matched {
733 return None;
734 }
735 self.calculate_score::<INDICES, _, _>(
736 AsciiChar::cast(haystack),
737 AsciiChar::cast(needle),
738 start,
739 end,
740 indices,
741 )
742 }
743 (Utf32Str::Ascii(_), Utf32Str::Unicode(_)) => {
744 // a purely ascii haystack can never be transformed to match
745 // a needle that contains non-ascii chars since we don't allow gaps
746 return None;
747 }
748 (Utf32Str::Unicode(haystack), Utf32Str::Ascii(needle)) => {
749 let matched = haystack[start..end]
750 .iter()
751 .map(|c| c.normalize(&self.config))
752 .eq(AsciiChar::cast(needle)
753 .iter()
754 .map(|c| c.normalize(&self.config)));
755 if !matched {
756 return None;
757 }
758
759 self.calculate_score::<INDICES, _, _>(
760 haystack,
761 AsciiChar::cast(needle),
762 start,
763 end,
764 indices,
765 )
766 }
767 (Utf32Str::Unicode(haystack), Utf32Str::Unicode(needle)) => {
768 let matched = haystack[start..end]
769 .iter()
770 .map(|c| c.normalize(&self.config))
771 .eq(needle.iter().map(|c| c.normalize(&self.config)));
772 if !matched {
773 return None;
774 }
775 self.calculate_score::<INDICES, _, _>(haystack, needle, start, end, indices)
776 }
777 };
778 Some(score)
779 }
780}