rushdb_types/
value_match.rs

1//! Matching a search text against stored values: `contains`,
2//! `prefix`, `exact` and `similar` (near spellings), and dates written in
3//! another layout. The wire form is `rushdb_protocol::ValueSearch`; this is
4//! the engine's side of it, shared by the value dictionaries, the facet
5//! scan and the cross-property value search.
6//!
7//! A string matches as stored; a number, boolean or datetime matches as the
8//! records response renders it; an array matches when any element does. A
9//! text that reads as a date (year first, at least a month: `1993-11-12`,
10//! `1993/11/12`, `2010/2/22`, `2013-06`) also matches values holding that
11//! date in another layout (`1993-11-12T00:00:00Z`, `1993.11.12`,
12//! `19931112`, `201306`), at the text's precision.
13
14use std::borrow::Cow;
15use std::collections::BTreeSet;
16
17use serde_json::Value as Json;
18
19/// How the search text must match a value.
20#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
21pub enum TextMatch {
22    /// The value contains the text.
23    #[default]
24    Contains,
25    /// The value starts with the text.
26    Prefix,
27    /// The value equals the text.
28    Exact,
29    /// The value is spelled like the text (see [`similarity`]).
30    Similar,
31}
32
33/// A search text prepared for matching many values.
34#[derive(Debug, Clone)]
35pub struct ValueMatcher {
36    text: String,
37    needle: String,
38    matching: TextMatch,
39    case_sensitive: bool,
40    min_similarity: f64,
41    date: Option<DateText>,
42}
43
44impl ValueMatcher {
45    /// The least similarity a `similar` match needs when none is given.
46    pub const DEFAULT_MIN_SIMILARITY: f64 = 0.6;
47
48    /// Prepares `text` for matching (case-insensitive unless
49    /// `case_sensitive`); `min_similarity` applies to `similar` only.
50    #[must_use]
51    pub fn new(
52        text: &str,
53        matching: TextMatch,
54        case_sensitive: bool,
55        min_similarity: Option<f64>,
56    ) -> Self {
57        Self {
58            text: text.to_string(),
59            needle: if case_sensitive {
60                text.to_string()
61            } else {
62                text.to_lowercase()
63            },
64            matching,
65            case_sensitive,
66            min_similarity: min_similarity.unwrap_or(Self::DEFAULT_MIN_SIMILARITY),
67            date: parse_date_text(text, false),
68        }
69    }
70
71    /// How the text must match.
72    #[must_use]
73    pub fn matching(&self) -> TextMatch {
74        self.matching
75    }
76
77    /// Whether `value` matches.
78    #[must_use]
79    pub fn matches(&self, value: &Json) -> bool {
80        let text = match value {
81            Json::String(text) => return self.matches_text(text),
82            Json::Number(number) => Cow::Owned(number.to_string()),
83            Json::Bool(flag) => Cow::Owned(flag.to_string()),
84            Json::Array(items) => return items.iter().any(|item| self.matches(item)),
85            Json::Null | Json::Object(_) => return false,
86        };
87        self.matches_text(&text)
88    }
89
90    /// Whether a text value matches, as [`Self::matches`] does for the
91    /// string `text`, without building the JSON value.
92    #[must_use]
93    pub fn matches_text(&self, text: &str) -> bool {
94        let text = Cow::Borrowed(text);
95        // ASCII text lowercases byte for byte, so it is compared in place
96        // instead of copying a lowercased value (a long text is read once).
97        let in_place = !self.case_sensitive
98            && self.matching != TextMatch::Similar
99            && self.needle.is_ascii()
100            && text.is_ascii();
101        let text = if self.case_sensitive || in_place {
102            text
103        } else {
104            Cow::Owned(text.to_lowercase())
105        };
106        let textual = if in_place {
107            ascii_match_ignoring_case(text.as_bytes(), self.needle.as_bytes(), self.matching)
108        } else {
109            match self.matching {
110                TextMatch::Contains => text.contains(self.needle.as_str()),
111                TextMatch::Prefix => text.starts_with(self.needle.as_str()),
112                TextMatch::Exact => *text == *self.needle,
113                TextMatch::Similar => similarity(&self.text, &text) >= self.min_similarity,
114            }
115        };
116        textual
117            || self.date.is_some_and(|wanted| {
118                parse_date_text(&text, true)
119                    .is_some_and(|held| wanted.matches(held, self.matching == TextMatch::Exact))
120            })
121    }
122
123    /// Whether a value of `ty` can match: false only when no rendering of
124    /// that type can contain the text, so a caller may skip the type's
125    /// values without changing the result. Numbers render with digits,
126    /// `.`, `-`, `+` and `e`; booleans as `true`/`false`; datetimes as a
127    /// year-first date with an optional `T…Z` time. `similar` and a text
128    /// that reads as a date can match any type.
129    #[must_use]
130    pub fn may_match(&self, ty: crate::model::LogicalType) -> bool {
131        use crate::model::LogicalType;
132        if self.matching == TextMatch::Similar || self.date.is_some() {
133            return true;
134        }
135        let only = |allowed: &dyn Fn(char) -> bool| self.needle.chars().all(allowed);
136        match ty {
137            LogicalType::Utf8 => true,
138            LogicalType::Int64 | LogicalType::Float64 => {
139                only(&|c| c.is_ascii_digit() || matches!(c, '.' | '-' | '+' | 'e' | 'E'))
140            }
141            LogicalType::Boolean => "true".contains(&self.needle) || "false".contains(&self.needle),
142            LogicalType::DateTime => only(&|c| {
143                c.is_ascii_digit() || matches!(c, '-' | ':' | '.' | '+' | 'T' | 'Z' | 't' | 'z')
144            }),
145        }
146    }
147
148    /// How close `value` is to the text, from 0 to 1 (see [`similarity`]);
149    /// arrays score their closest element.
150    #[must_use]
151    pub fn similarity(&self, value: &Json) -> f64 {
152        match value {
153            Json::String(text) => similarity(&self.text, text),
154            Json::Number(number) => similarity(&self.text, &number.to_string()),
155            Json::Bool(flag) => similarity(&self.text, &flag.to_string()),
156            Json::Array(items) => items
157                .iter()
158                .map(|item| self.similarity(item))
159                .fold(0.0, f64::max),
160            Json::Null | Json::Object(_) => 0.0,
161        }
162    }
163}
164
165/// Lowercase alphanumeric words of `text`; everything else separates them.
166fn similarity_words(text: &str) -> Vec<String> {
167    text.to_lowercase()
168        .split(|c: char| !c.is_alphanumeric())
169        .filter(|word| !word.is_empty())
170        .map(str::to_owned)
171        .collect()
172}
173
174/// Character trigrams of each word, padded so short words still have some.
175fn trigrams(words: &[String]) -> BTreeSet<[char; 3]> {
176    let mut out = BTreeSet::new();
177    for word in words {
178        let padded: Vec<char> = std::iter::once(' ')
179            .chain(std::iter::once(' '))
180            .chain(word.chars())
181            .chain(std::iter::once(' '))
182            .collect();
183        for window in padded.windows(3) {
184            out.insert([window[0], window[1], window[2]]);
185        }
186    }
187    out
188}
189
190/// How closely `stored` spells `text`, from 0 to 1. Exactly 1 when some run
191/// of whole words of `stored` spells `text` once case, punctuation and
192/// spacing are ignored ("Spider-Man" for "spiderman"); otherwise the share
193/// of the text's character trigrams that occur in `stored` (a typo keeps
194/// most of them, an unrelated word few).
195#[must_use]
196pub fn similarity(text: &str, stored: &str) -> f64 {
197    let wanted = similarity_words(text);
198    if wanted.is_empty() {
199        return 0.0;
200    }
201    let held = similarity_words(stored);
202    // Whole words only: a run of consecutive stored words that spells the
203    // text once joined ("spider man" for "spiderman", "orange county" for
204    // "Orange County,"), never a word fragment ("male" in "female").
205    let joined = wanted.concat();
206    let spelled = (0..held.len()).any(|start| {
207        let mut run = String::new();
208        held[start..].iter().any(|word| {
209            run.push_str(word);
210            run == joined
211        })
212    });
213    if spelled {
214        return 1.0;
215    }
216    let wanted = trigrams(&wanted);
217    let held = trigrams(&held);
218    #[expect(
219        clippy::cast_precision_loss,
220        reason = "trigram counts are small; the ratio is a score"
221    )]
222    let score = wanted.intersection(&held).count() as f64 / wanted.len() as f64;
223    score
224}
225
226/// A calendar date read from text, to the precision written: year and month,
227/// optionally the day.
228#[derive(Debug, Clone, Copy, PartialEq, Eq)]
229struct DateText {
230    year: u32,
231    month: u32,
232    day: Option<u32>,
233}
234
235impl DateText {
236    /// Whether `held` falls in this date (same year and month, and the same
237    /// day when this one has a day). `exact` also requires equal precision.
238    fn matches(self, held: Self, exact: bool) -> bool {
239        self.year == held.year
240            && self.month == held.month
241            && match self.day {
242                Some(day) => held.day == Some(day),
243                None => !exact || held.day.is_none(),
244            }
245    }
246}
247
248/// Reads a year-first date: `Y-M[-D]` with `-`, `/` or `.` separators (month
249/// and day may be unpadded), and, when `stored`, also a compact `YYYYMM[DD]`
250/// and a trailing time (`T…` or ` …`, either case). Day-first and
251/// month-first layouts are ambiguous and not read.
252/// `text` against a lowercase ASCII `needle`, ignoring ASCII case.
253fn ascii_match_ignoring_case(text: &[u8], needle: &[u8], matching: TextMatch) -> bool {
254    match matching {
255        TextMatch::Exact => text.eq_ignore_ascii_case(needle),
256        TextMatch::Prefix => text
257            .get(..needle.len())
258            .is_some_and(|head| head.eq_ignore_ascii_case(needle)),
259        TextMatch::Contains | TextMatch::Similar => {
260            let Some((&first, _)) = needle.split_first() else {
261                return true;
262            };
263            text.len() >= needle.len()
264                && (0..=text.len() - needle.len()).any(|at| {
265                    text[at].to_ascii_lowercase() == first
266                        && text[at..at + needle.len()].eq_ignore_ascii_case(needle)
267                })
268        }
269    }
270}
271
272fn parse_date_text(text: &str, stored: bool) -> Option<DateText> {
273    let text = text.trim();
274    let date = if stored {
275        text.split(['T', 't', ' ']).next().unwrap_or(text)
276    } else {
277        text
278    };
279    let valid = |year: u32, month: u32, day: Option<u32>| {
280        ((1..=9999).contains(&year)
281            && (1..=12).contains(&month)
282            && day.is_none_or(|day| (1..=31).contains(&day)))
283        .then_some(DateText { year, month, day })
284    };
285    let number = |part: &str, max_len: usize| {
286        (!part.is_empty() && part.len() <= max_len && part.bytes().all(|b| b.is_ascii_digit()))
287            .then(|| part.parse::<u32>().ok())
288            .flatten()
289    };
290    for separator in ['-', '/', '.'] {
291        let parts: Vec<&str> = date.split(separator).collect();
292        if parts.len() < 2 || parts.len() > 3 || parts[0].len() != 4 {
293            continue;
294        }
295        let year = number(parts[0], 4)?;
296        let month = number(parts[1], 2)?;
297        let day = match parts.get(2) {
298            Some(part) => Some(number(part, 2)?),
299            None => None,
300        };
301        return valid(year, month, day);
302    }
303    if stored && (date.len() == 6 || date.len() == 8) && date.bytes().all(|b| b.is_ascii_digit()) {
304        let year = number(&date[..4], 4)?;
305        let month = number(&date[4..6], 2)?;
306        let day = if date.len() == 8 {
307            Some(number(&date[6..], 2)?)
308        } else {
309            None
310        };
311        return valid(year, month, day);
312    }
313    None
314}
315
316#[cfg(test)]
317mod tests {
318    use super::{parse_date_text, similarity, TextMatch, ValueMatcher};
319    use serde_json::json;
320
321    fn search(text: &str, matching: TextMatch) -> ValueMatcher {
322        ValueMatcher::new(text, matching, false, None)
323    }
324
325    #[test]
326    fn may_match_skips_only_types_that_cannot_render_the_text() {
327        use crate::model::LogicalType as T;
328        let contains = |text: &str| ValueMatcher::new(text, TextMatch::Contains, false, None);
329        let word = contains("Withdrawal");
330        assert!(word.may_match(T::Utf8));
331        for ty in [T::Int64, T::Float64, T::Boolean, T::DateTime] {
332            assert!(!word.may_match(ty), "{ty}");
333        }
334        for ty in [T::Int64, T::Float64, T::DateTime, T::Utf8] {
335            assert!(contains("-12.5").may_match(ty), "{ty}");
336        }
337        assert!(!contains("-12.5").may_match(T::Boolean));
338        assert!(contains("1e-7").may_match(T::Float64));
339        assert!(contains("RU").may_match(T::Boolean));
340        assert!(contains("T10:00").may_match(T::DateTime));
341        assert!(!contains("T10:00").may_match(T::Int64));
342        // An empty text, a date text and `similar` can match anything.
343        for matcher in [
344            contains(""),
345            contains("1993/3/22"),
346            ValueMatcher::new("attack", TextMatch::Similar, false, None),
347        ] {
348            for ty in [T::Int64, T::Float64, T::Boolean, T::DateTime, T::Utf8] {
349                assert!(matcher.may_match(ty), "{ty}");
350            }
351        }
352        // Each skip agrees with `matches` on rendered values of the type.
353        let rendered = [
354            (T::Int64, json!(1_234_567)),
355            (T::Float64, json!(-0.000_000_1)),
356            (T::Float64, json!(1.5e300)),
357            (T::Boolean, json!(true)),
358            (T::Boolean, json!(false)),
359            (T::DateTime, json!("1993-11-12")),
360            (T::DateTime, json!("2024-01-02T10:00:00.000Z")),
361        ];
362        for text in [
363            "attack", "Ajax", "e", "E", "true", "al", "12", "-0", "t1", "z",
364        ] {
365            for matching in [TextMatch::Contains, TextMatch::Prefix, TextMatch::Exact] {
366                let matcher = ValueMatcher::new(text, matching, false, None);
367                for (ty, value) in &rendered {
368                    if matcher.matches(value) {
369                        assert!(matcher.may_match(*ty), "{text} {ty} {value}");
370                    }
371                }
372            }
373        }
374    }
375
376    #[test]
377    fn matches_dates_across_layouts() {
378        let day = search("1993/11/12", TextMatch::Contains);
379        for held in [
380            "1993-11-12",
381            "1993-11-12T00:00:00.000Z",
382            "1993.11.12",
383            "1993/11/12 08:30",
384            "19931112",
385        ] {
386            assert!(day.matches(&json!(held)), "{held}");
387        }
388        assert!(day.matches(&json!(19_931_112)));
389        assert!(!day.matches(&json!("1993-11-13")));
390        assert!(!day.matches(&json!("1993-11")));
391        // Unpadded month and day.
392        assert!(search("2010/2/22", TextMatch::Contains).matches(&json!("2010-02-22")));
393        // A month matches every day in it, and a compact year-month.
394        let month = search("2013-06", TextMatch::Contains);
395        assert!(month.matches(&json!(201_306)));
396        assert!(month.matches(&json!("2013-06-30T23:00:00Z")));
397        assert!(!month.matches(&json!("2013-07-01")));
398        // Exact also requires the same precision.
399        let exact = search("2013/06", TextMatch::Exact);
400        assert!(exact.matches(&json!("2013-06")));
401        assert!(!exact.matches(&json!("2013-06-01")));
402    }
403
404    #[test]
405    fn reads_only_year_first_dates() {
406        // Not dates: day-first, a bare year, compact text in the search,
407        // an invalid month, and a word that splits on a separator.
408        for text in ["12/11/1993", "1993", "19931112", "1993-13", "self-interest"] {
409            assert!(parse_date_text(text, false).is_none(), "{text}");
410        }
411        assert!(!search("1993", TextMatch::Exact).matches(&json!("1993-01-01")));
412        assert!(parse_date_text("199313", true).is_none());
413        assert!(parse_date_text("2024-01-02t10:00:00z", true).is_some());
414    }
415
416    #[test]
417    fn ascii_text_matches_as_its_lowercase_copy_would() {
418        let texts = [
419            "",
420            "a",
421            "Joanne",
422            "JOANNE",
423            "<goal><value>Belgian Jupiler League</value></goal>",
424            "jo",
425            "xJoA",
426            "Ünïcode Joanne",
427            "\u{212A}elvin",
428        ];
429        let needles = ["", "jo", "JOA", "joanne", "league</", "e", "kelvin", "ü"];
430        for matching in [TextMatch::Contains, TextMatch::Prefix, TextMatch::Exact] {
431            for needle in needles {
432                let fast = search(needle, matching);
433                for text in texts {
434                    let lower = text.to_lowercase();
435                    let needle = needle.to_lowercase();
436                    let expected = match matching {
437                        TextMatch::Contains => lower.contains(&needle),
438                        TextMatch::Prefix => lower.starts_with(&needle),
439                        _ => lower == needle,
440                    };
441                    assert_eq!(
442                        fast.matches(&json!(text)),
443                        expected,
444                        "{matching:?} {needle:?} in {text:?}"
445                    );
446                }
447            }
448        }
449    }
450
451    #[test]
452    fn matches_text_case_insensitively_unless_asked() {
453        assert!(search("ann", TextMatch::Contains).matches(&json!("Joanne")));
454        assert!(search("JO", TextMatch::Prefix).matches(&json!("Joanne")));
455        assert!(search("joanne", TextMatch::Exact).matches(&json!("Joanne")));
456        assert!(
457            !ValueMatcher::new("joanne", TextMatch::Exact, true, None).matches(&json!("Joanne"))
458        );
459        assert!(search("4", TextMatch::Contains).matches(&json!([1, 42])));
460        assert!(!search("x", TextMatch::Contains).matches(&json!(null)));
461    }
462
463    #[test]
464    fn similar_spellings_score_high_and_unrelated_words_low() {
465        assert!((similarity("spiderman", "Spider-Man") - 1.0).abs() < f64::EPSILON);
466        assert!(similarity("male", "female") < 1.0);
467        assert!(similarity("Califronia", "California") >= 0.6);
468        assert!(similarity("Texas", "California") < 0.3);
469        let near = search("Orange County", TextMatch::Similar);
470        assert!(near.matches(&json!("orange county,")));
471        assert!(near.similarity(&json!(["Texas", "Orange County"])) > 0.99);
472    }
473}
rushdb_types/value_match.rs

rushdb_types/
value_match.rs
