riffdb_types/
long_pattern.rs

1//! ADR-0174 long-value exact wildcard semantics.
2
3use sha2::{Digest, Sha256};
4
5/// Maximum authoritative UTF-8 source bytes admitted by `long_pattern_v1`.
6pub const MAX_LONG_PATTERN_SOURCE_BYTES_V1: usize = 8_000;
7/// Frozen maximum expansion of an 8,000-byte source under `unicode_fold_v1`.
8pub const MAX_LONG_PATTERN_MATCHED_BYTES_V1: usize = 144_000;
9/// Maximum submitted pattern bytes.
10pub const MAX_LONG_PATTERN_QUERY_BYTES_V1: usize = 8_000;
11/// Maximum wildcard atoms after profile transformation.
12pub const MAX_LONG_PATTERN_ATOMS_V1: usize = 144_000;
13/// Maximum compiler-declared provider rows in one partition.
14pub const MAX_LONG_PATTERN_ROWS_PER_PARTITION_V1: u32 = 65_535;
15
16/// Complete independent resource bounds shared by contracts, providers and query plans.
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
18pub struct LongPatternBoundsV1 {
19    source_bytes: u32,
20    matched_bytes: u32,
21    rows: u32,
22    total_matched_bytes: u64,
23    distinct_grams: u32,
24    postings: u64,
25    postings_bytes: u64,
26    grams_per_row: u32,
27    pattern_bytes: u32,
28    wildcard_atoms: u32,
29    literal_runs: u32,
30    candidates: u32,
31    verification_bytes: u64,
32    results: u32,
33}
34
35impl LongPatternBoundsV1 {
36    /// Constructs one fully checked bound set.
37    #[allow(clippy::too_many_arguments)]
38    pub fn new(
39        source_bytes: u32,
40        matched_bytes: u32,
41        rows: u32,
42        total_matched_bytes: u64,
43        distinct_grams: u32,
44        postings: u64,
45        postings_bytes: u64,
46        grams_per_row: u32,
47        pattern_bytes: u32,
48        wildcard_atoms: u32,
49        literal_runs: u32,
50        candidates: u32,
51        verification_bytes: u64,
52        results: u32,
53    ) -> Result<Self, LongPatternBoundsErrorV1> {
54        let bounds = Self {
55            source_bytes,
56            matched_bytes,
57            rows,
58            total_matched_bytes,
59            distinct_grams,
60            postings,
61            postings_bytes,
62            grams_per_row,
63            pattern_bytes,
64            wildcard_atoms,
65            literal_runs,
66            candidates,
67            verification_bytes,
68            results,
69        };
70        if source_bytes == 0
71            || source_bytes as usize > MAX_LONG_PATTERN_SOURCE_BYTES_V1
72            || matched_bytes == 0
73            || matched_bytes as usize > MAX_LONG_PATTERN_MATCHED_BYTES_V1
74            || rows == 0
75            || rows > MAX_LONG_PATTERN_ROWS_PER_PARTITION_V1
76            || total_matched_bytes == 0
77            || distinct_grams == 0
78            || postings == 0
79            || postings_bytes == 0
80            || grams_per_row == 0
81            || pattern_bytes == 0
82            || pattern_bytes as usize > MAX_LONG_PATTERN_QUERY_BYTES_V1
83            || wildcard_atoms == 0
84            || wildcard_atoms as usize > MAX_LONG_PATTERN_ATOMS_V1
85            || literal_runs == 0
86            || candidates == 0
87            || candidates > rows
88            || verification_bytes == 0
89            || results == 0
90            || results > candidates
91        {
92            return Err(LongPatternBoundsErrorV1);
93        }
94        Ok(bounds)
95    }
96    /// Maximum source bytes.
97    #[must_use]
98    pub const fn source_bytes(self) -> u32 {
99        self.source_bytes
100    }
101    /// Maximum matched bytes per row.
102    #[must_use]
103    pub const fn matched_bytes(self) -> u32 {
104        self.matched_bytes
105    }
106    /// Maximum rows per partition.
107    #[must_use]
108    pub const fn rows(self) -> u32 {
109        self.rows
110    }
111    /// Maximum total retained matched bytes.
112    #[must_use]
113    pub const fn total_matched_bytes(self) -> u64 {
114        self.total_matched_bytes
115    }
116    /// Maximum distinct grams.
117    #[must_use]
118    pub const fn distinct_grams(self) -> u32 {
119        self.distinct_grams
120    }
121    /// Maximum posting entries.
122    #[must_use]
123    pub const fn postings(self) -> u64 {
124        self.postings
125    }
126    /// Maximum encoded posting bytes.
127    #[must_use]
128    pub const fn postings_bytes(self) -> u64 {
129        self.postings_bytes
130    }
131    /// Maximum grams retained per row.
132    #[must_use]
133    pub const fn grams_per_row(self) -> u32 {
134        self.grams_per_row
135    }
136    /// Maximum submitted pattern bytes.
137    #[must_use]
138    pub const fn pattern_bytes(self) -> u32 {
139        self.pattern_bytes
140    }
141    /// Maximum transformed wildcard atoms.
142    #[must_use]
143    pub const fn wildcard_atoms(self) -> u32 {
144        self.wildcard_atoms
145    }
146    /// Maximum literal runs in one wildcard pattern.
147    #[must_use]
148    pub const fn literal_runs(self) -> u32 {
149        self.literal_runs
150    }
151    /// Maximum candidates verified by one query.
152    #[must_use]
153    pub const fn candidates(self) -> u32 {
154        self.candidates
155    }
156    /// Maximum matched bytes verified by one query.
157    #[must_use]
158    pub const fn verification_bytes(self) -> u64 {
159        self.verification_bytes
160    }
161    /// Maximum released results.
162    #[must_use]
163    pub const fn results(self) -> u32 {
164        self.results
165    }
166}
167
168/// A bound set was zero, inconsistent, or above a fixed ceiling.
169#[derive(Clone, Copy, Debug, Eq, PartialEq)]
170pub struct LongPatternBoundsErrorV1;
171
172/// Frozen matching profile.
173#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
174#[repr(u8)]
175pub enum LongPatternProfileV1 {
176    /// Compare canonical UTF-8 directly.
177    BinaryUtf8V1 = 1,
178    /// Apply the frozen Unicode fold before comparison.
179    UnicodeFoldV1 = 2,
180}
181
182impl LongPatternProfileV1 {
183    /// Decodes a stable profile discriminant.
184    #[must_use]
185    pub const fn from_discriminant(value: u8) -> Option<Self> {
186        match value {
187            1 => Some(Self::BinaryUtf8V1),
188            2 => Some(Self::UnicodeFoldV1),
189            _ => None,
190        }
191    }
192
193    /// Produces the exact retained matched form.
194    #[must_use]
195    pub fn matched_form(self, value: &str) -> String {
196        match self {
197            Self::BinaryUtf8V1 => value.to_owned(),
198            Self::UnicodeFoldV1 => crate::unicode_fold_v1(value),
199        }
200    }
201}
202
203/// Closed public operator inventory.
204#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
205#[repr(u8)]
206pub enum LongPatternOperatorV1 {
207    /// Whole-value equality under the declared profile.
208    Equals = 1,
209    /// Literal prefix under the declared profile.
210    StartsWith = 2,
211    /// Literal suffix under the declared profile.
212    EndsWith = 3,
213    /// Literal substring under the declared profile.
214    Contains = 4,
215    /// SQL-like `%` and `_` matching under binary UTF-8.
216    Like = 5,
217    /// SQL-like matching under `unicode_fold_v1`.
218    ILike = 6,
219    /// Authorized-universe difference against `Like`.
220    NotLike = 7,
221    /// Authorized-universe difference against `ILike`.
222    NotILike = 8,
223}
224
225impl LongPatternOperatorV1 {
226    /// Decodes a stable operator discriminant.
227    #[must_use]
228    pub const fn from_discriminant(value: u8) -> Option<Self> {
229        match value {
230            1 => Some(Self::Equals),
231            2 => Some(Self::StartsWith),
232            3 => Some(Self::EndsWith),
233            4 => Some(Self::Contains),
234            5 => Some(Self::Like),
235            6 => Some(Self::ILike),
236            7 => Some(Self::NotLike),
237            8 => Some(Self::NotILike),
238            _ => None,
239        }
240    }
241
242    /// Whether the operator interprets wildcard syntax.
243    #[must_use]
244    pub const fn is_wildcard(self) -> bool {
245        matches!(
246            self,
247            Self::Like | Self::ILike | Self::NotLike | Self::NotILike
248        )
249    }
250
251    /// Whether matching uses the Unicode-fold profile regardless of storage profile.
252    #[must_use]
253    pub const fn is_case_insensitive(self) -> bool {
254        matches!(self, Self::ILike | Self::NotILike)
255    }
256
257    /// Whether result formation is an authorized positive-universe difference.
258    #[must_use]
259    pub const fn is_negated(self) -> bool {
260        matches!(self, Self::NotLike | Self::NotILike)
261    }
262}
263
264/// One compiled wildcard atom. This is process-local semantic state, not a durable codec.
265#[derive(Clone, Copy, Debug, Eq, PartialEq)]
266enum PatternAtomV1 {
267    Literal(char),
268    One,
269    Many,
270}
271
272/// Checked pattern with bounded transformed atoms and mandatory gram hints.
273#[derive(Clone, Debug, Eq, PartialEq)]
274pub struct CompiledLongPatternV1 {
275    operator: LongPatternOperatorV1,
276    profile: LongPatternProfileV1,
277    literal: Option<String>,
278    atoms: Vec<PatternAtomV1>,
279    mandatory_grams: Vec<[u8; 3]>,
280}
281
282impl CompiledLongPatternV1 {
283    /// Compiles one bounded literal or wildcard pattern.
284    pub fn compile(
285        operator: LongPatternOperatorV1,
286        declared_profile: LongPatternProfileV1,
287        source: &str,
288    ) -> Result<Self, LongPatternErrorV1> {
289        Self::compile_with_limits(
290            operator,
291            declared_profile,
292            source,
293            MAX_LONG_PATTERN_QUERY_BYTES_V1,
294            MAX_LONG_PATTERN_MATCHED_BYTES_V1,
295            MAX_LONG_PATTERN_ATOMS_V1,
296            MAX_LONG_PATTERN_ATOMS_V1,
297        )
298    }
299
300    /// Compiles against the exact immutable bounds declared by one provider.
301    pub fn compile_bounded(
302        operator: LongPatternOperatorV1,
303        declared_profile: LongPatternProfileV1,
304        source: &str,
305        bounds: LongPatternBoundsV1,
306    ) -> Result<Self, LongPatternErrorV1> {
307        Self::compile_with_limits(
308            operator,
309            declared_profile,
310            source,
311            bounds.pattern_bytes() as usize,
312            bounds.matched_bytes() as usize,
313            bounds.wildcard_atoms() as usize,
314            bounds.literal_runs() as usize,
315        )
316    }
317
318    fn compile_with_limits(
319        operator: LongPatternOperatorV1,
320        declared_profile: LongPatternProfileV1,
321        source: &str,
322        pattern_bytes: usize,
323        matched_bytes: usize,
324        wildcard_atoms: usize,
325        literal_runs: usize,
326    ) -> Result<Self, LongPatternErrorV1> {
327        if source.is_empty() || source.len() > pattern_bytes {
328            return Err(LongPatternErrorV1::PatternBytes);
329        }
330        let profile = if operator.is_case_insensitive() {
331            LongPatternProfileV1::UnicodeFoldV1
332        } else {
333            declared_profile
334        };
335        if !operator.is_wildcard() {
336            let literal = profile.matched_form(source);
337            if literal.len() > matched_bytes {
338                return Err(LongPatternErrorV1::MatchedBytes);
339            }
340            let mandatory_grams = distinct_grams(literal.as_bytes());
341            return Ok(Self {
342                operator,
343                profile,
344                literal: Some(literal),
345                atoms: Vec::new(),
346                mandatory_grams,
347            });
348        }
349
350        let runs = parse_wildcard_runs(source)?;
351        if runs.len() > literal_runs {
352            return Err(LongPatternErrorV1::PatternAtoms);
353        }
354        let mut atoms = Vec::new();
355        let mut mandatory_grams = Vec::new();
356        for run in runs {
357            match run {
358                PatternRunV1::Literal(value) => {
359                    let matched = profile.matched_form(&value);
360                    mandatory_grams.extend(distinct_grams(matched.as_bytes()));
361                    atoms.extend(matched.chars().map(PatternAtomV1::Literal));
362                }
363                PatternRunV1::One => atoms.push(PatternAtomV1::One),
364                PatternRunV1::Many => {
365                    if !matches!(atoms.last(), Some(PatternAtomV1::Many)) {
366                        atoms.push(PatternAtomV1::Many);
367                    }
368                }
369            }
370            if atoms.len() > wildcard_atoms {
371                return Err(LongPatternErrorV1::PatternAtoms);
372            }
373        }
374        mandatory_grams.sort_unstable();
375        mandatory_grams.dedup();
376        Ok(Self {
377            operator,
378            profile,
379            literal: None,
380            atoms,
381            mandatory_grams,
382        })
383    }
384
385    /// Exact operator selected by the compiled query.
386    #[must_use]
387    pub const fn operator(&self) -> LongPatternOperatorV1 {
388        self.operator
389    }
390
391    /// Effective matching profile.
392    #[must_use]
393    pub const fn profile(&self) -> LongPatternProfileV1 {
394        self.profile
395    }
396
397    /// Ordered distinct mandatory literal grams. Empty means bounded provider scan.
398    #[must_use]
399    pub fn mandatory_grams(&self) -> &[[u8; 3]] {
400        &self.mandatory_grams
401    }
402
403    /// Verifies one already-profiled retained value exactly.
404    #[must_use]
405    pub fn matches_matched(&self, matched: &str) -> bool {
406        let positive = match (self.operator, self.literal.as_deref()) {
407            (LongPatternOperatorV1::Equals, Some(literal)) => matched == literal,
408            (LongPatternOperatorV1::StartsWith, Some(literal)) => matched.starts_with(literal),
409            (LongPatternOperatorV1::EndsWith, Some(literal)) => matched.ends_with(literal),
410            (LongPatternOperatorV1::Contains, Some(literal)) => matched.contains(literal),
411            _ => wildcard_matches(&self.atoms, matched),
412        };
413        if self.operator.is_negated() {
414            !positive
415        } else {
416            positive
417        }
418    }
419
420    /// Applies the effective profile and verifies one source value.
421    #[must_use]
422    pub fn matches_source(&self, source: &str) -> bool {
423        self.matches_matched(&self.profile.matched_form(source))
424    }
425}
426
427#[derive(Clone, Debug, Eq, PartialEq)]
428enum PatternRunV1 {
429    Literal(String),
430    One,
431    Many,
432}
433
434fn parse_wildcard_runs(source: &str) -> Result<Vec<PatternRunV1>, LongPatternErrorV1> {
435    let mut runs = Vec::new();
436    let mut literal = String::new();
437    let mut chars = source.chars();
438    while let Some(character) = chars.next() {
439        match character {
440            '\\' => {
441                let escaped = chars.next().ok_or(LongPatternErrorV1::InvalidEscape)?;
442                if !matches!(escaped, '%' | '_' | '\\') {
443                    return Err(LongPatternErrorV1::InvalidEscape);
444                }
445                literal.push(escaped);
446            }
447            '%' | '_' => {
448                if !literal.is_empty() {
449                    runs.push(PatternRunV1::Literal(std::mem::take(&mut literal)));
450                }
451                runs.push(if character == '%' {
452                    PatternRunV1::Many
453                } else {
454                    PatternRunV1::One
455                });
456            }
457            _ => literal.push(character),
458        }
459    }
460    if !literal.is_empty() {
461        runs.push(PatternRunV1::Literal(literal));
462    }
463    Ok(runs)
464}
465
466fn wildcard_matches(atoms: &[PatternAtomV1], matched: &str) -> bool {
467    let value = matched.chars().collect::<Vec<_>>();
468    let (mut atom, mut scalar) = (0_usize, 0_usize);
469    let (mut star, mut star_scalar) = (None, 0_usize);
470    while scalar < value.len() {
471        match atoms.get(atom) {
472            Some(PatternAtomV1::Literal(expected)) if *expected == value[scalar] => {
473                atom += 1;
474                scalar += 1;
475            }
476            Some(PatternAtomV1::One) => {
477                atom += 1;
478                scalar += 1;
479            }
480            Some(PatternAtomV1::Many) => {
481                star = Some(atom);
482                atom += 1;
483                star_scalar = scalar;
484            }
485            _ => {
486                let Some(star_atom) = star else {
487                    return false;
488                };
489                star_scalar += 1;
490                scalar = star_scalar;
491                atom = star_atom + 1;
492            }
493        }
494    }
495    while matches!(atoms.get(atom), Some(PatternAtomV1::Many)) {
496        atom += 1;
497    }
498    atom == atoms.len()
499}
500
501/// Returns ordered distinct three-byte windows without enumerating substrings.
502#[must_use]
503pub fn long_pattern_grams_v1(matched: &str) -> Vec<[u8; 3]> {
504    distinct_grams(matched.as_bytes())
505}
506
507fn distinct_grams(bytes: &[u8]) -> Vec<[u8; 3]> {
508    let mut grams = bytes
509        .windows(3)
510        .map(|window| [window[0], window[1], window[2]])
511        .collect::<Vec<_>>();
512    grams.sort_unstable();
513    grams.dedup();
514    grams
515}
516
517/// Collision-resistant digest used only as a candidate filter; callers still verify bytes.
518#[must_use]
519pub fn long_pattern_digest_v1(matched: &str) -> [u8; 32] {
520    let mut digest = Sha256::new();
521    digest.update(b"RIFFDB-LONG-PATTERN-VALUE-V1\0");
522    digest.update((matched.len() as u64).to_be_bytes());
523    digest.update(matched.as_bytes());
524    digest.finalize().into()
525}
526
527/// Closed pattern compilation refusal.
528#[derive(Clone, Copy, Debug, Eq, PartialEq)]
529pub enum LongPatternErrorV1 {
530    /// Source query pattern is empty or exceeds its byte maximum.
531    PatternBytes,
532    /// Profile expansion exceeded the matched-value maximum.
533    MatchedBytes,
534    /// Transformed wildcard atom count exceeded its maximum.
535    PatternAtoms,
536    /// Backslash did not escape exactly `%`, `_`, or backslash.
537    InvalidEscape,
538}
539
540// Exhaustive non-durable ownership inventories for exact-provider admission.
541crate::inspect_owned_capacity_copy_v1!(LongPatternOperatorV1);
542
543crate::inspect_owned_capacity_copy_v1!(LongPatternProfileV1);
544
545crate::inspect_owned_capacity_copy_v1!(LongPatternBoundsV1);
546
547#[cfg(test)]
548mod tests {
549    use super::*;
550
551    #[test]
552    fn wildcard_semantics_cover_scalars_escaping_folding_and_negation() {
553        let like = CompiledLongPatternV1::compile(
554            LongPatternOperatorV1::Like,
555            LongPatternProfileV1::BinaryUtf8V1,
556            r"ab%_\%",
557        )
558        .expect("pattern");
559        assert!(like.matches_source("abλ-tail%"));
560        assert!(!like.matches_source("ab%"));
561
562        let ilike = CompiledLongPatternV1::compile(
563            LongPatternOperatorV1::ILike,
564            LongPatternProfileV1::BinaryUtf8V1,
565            "strasse%",
566        )
567        .expect("folded pattern");
568        assert!(ilike.matches_source("STRAßE-tail"));
569
570        let not_like = CompiledLongPatternV1::compile(
571            LongPatternOperatorV1::NotLike,
572            LongPatternProfileV1::BinaryUtf8V1,
573            "%secret%",
574        )
575        .expect("negated pattern");
576        assert!(not_like.matches_source("public"));
577        assert!(!not_like.matches_source("a secret value"));
578    }
579
580    #[test]
581    fn invalid_escapes_and_pattern_bytes_fail_closed() {
582        for pattern in [r"trailing\", r"bad\x"] {
583            assert_eq!(
584                CompiledLongPatternV1::compile(
585                    LongPatternOperatorV1::Like,
586                    LongPatternProfileV1::BinaryUtf8V1,
587                    pattern,
588                ),
589                Err(LongPatternErrorV1::InvalidEscape)
590            );
591        }
592        assert_eq!(
593            CompiledLongPatternV1::compile(
594                LongPatternOperatorV1::Contains,
595                LongPatternProfileV1::BinaryUtf8V1,
596                "",
597            ),
598            Err(LongPatternErrorV1::PatternBytes)
599        );
600    }
601
602    #[test]
603    fn grams_are_distinct_ordered_and_only_acceleration_hints() {
604        assert_eq!(long_pattern_grams_v1("ababa"), vec![*b"aba", *b"bab"]);
605        let wildcard = CompiledLongPatternV1::compile(
606            LongPatternOperatorV1::Like,
607            LongPatternProfileV1::BinaryUtf8V1,
608            "%ab%",
609        )
610        .expect("short literal");
611        assert!(wildcard.mandatory_grams().is_empty());
612        assert!(wildcard.matches_source("zzabzz"));
613    }
614}
riffdb_types/long_pattern.rs

riffdb_types/
long_pattern.rs
