dyntext/
tre.rs

1//! Safe Rust wrapper around `tre-sys`.
2//!
3//! This module is the single entry point dyntext callers use
4//! to do approximate-regex matching. It provides:
5//!
6//! * [`TreCompiledPattern`], an owning handle to a compiled
7//!   TRE pattern that frees its native resources on drop.
8//! * [`TreMatchOpts`], a builder for the per-call cost weights
9//!   and edit-budget caps.
10//! * [`TreMatch`], the result of a successful approximate
11//!   match.
12//! * [`TreError`], a typed error returned by [`TreCompiledPattern::compile`].
13//!
14//! The wrapper is intentionally narrow: it exposes only what
15//! the dyntext index needs, and it does **not** leak any
16//! `unsafe` API. All `unsafe` lives in the `tre-sys` crate;
17//! see the module-level safety section there for the contract
18//! enforced here.
19//!
20//! # Example
21//!
22//! ```
23//! use dyntext::tre::{TreCompiledPattern, TreMatchOpts};
24//!
25//! let opts = TreMatchOpts {
26//!     max_errors: 1,
27//!     ..TreMatchOpts::default()
28//! };
29//! let pat = TreCompiledPattern::compile(br"errno: \w+ refused", opts)
30//!     .expect("compile");
31//! assert!(pat.is_match(b"errno: connection refused"));
32//! assert!(pat.is_match(b"errno: cnnection refused"));
33//! assert!(!pat.is_match(b"errno cnntion rfsed"));
34//! ```
35//!
36//! # Thread safety
37//!
38//! [`TreCompiledPattern`] is intentionally `!Send` and `!Sync`.
39//! TRE's compiled `regex_t` owns mutable state (the TNFA), and
40//! the matcher is not internally synchronised. Callers that
41//! want concurrent matching should compile one pattern per
42//! thread.
43
44use std::marker::PhantomData;
45use std::os::raw::c_int;
46
47use thiserror::Error;
48use tre_sys::{
49    compile as compile_raw, default_regaparams, safe_reganexec, safe_regerror, ExecOutcome,
50    OwnedRegex, REG_EXTENDED, REG_ICASE,
51};
52
53/// Errors returned by [`TreCompiledPattern::compile`].
54#[derive(Debug, Error)]
55pub enum TreError {
56    /// The pattern bytes failed to compile.
57    #[error("tre compile failed: {0}")]
58    Compile(String),
59    /// A configuration choice in [`TreMatchOpts`] is
60    /// inconsistent (for example, `max_errors > 0` with all
61    /// edit costs at zero).
62    #[error("invalid pattern options: {0}")]
63    InvalidOptions(String),
64    /// TRE returned a code not covered by the public API.
65    #[error("internal tre error: {0}")]
66    Internal(String),
67}
68
69/// Per-pattern matching configuration.
70///
71/// `max_errors` is the headline knob: it bounds the number of
72/// edit operations tolerated in a match. `cost_*` weight each
73/// edit kind; if all weights are 1 the cost equals the edit
74/// distance. `max_cost` bounds the cumulative cost; setting it
75/// to 0 with `max_errors > 0` is rejected because it forces
76/// exact match no matter what edits are allowed.
77///
78/// `case_insensitive` toggles TRE's `REG_ICASE` flag.
79#[derive(Clone, Copy, Debug)]
80pub struct TreMatchOpts {
81    /// Maximum number of edit operations (insert + delete +
82    /// substitute) permitted in a match.
83    pub max_errors: u16,
84    /// Cost of inserting one byte. Defaults to 1.
85    pub cost_ins: u16,
86    /// Cost of deleting one byte. Defaults to 1.
87    pub cost_del: u16,
88    /// Cost of substituting one byte. Defaults to 1.
89    pub cost_subst: u16,
90    /// Cumulative cost ceiling. Zero means "use
91    /// `max_errors * max(cost_*)` as the implicit ceiling".
92    pub max_cost: u16,
93    /// Match case-insensitively.
94    pub case_insensitive: bool,
95}
96
97impl Default for TreMatchOpts {
98    fn default() -> Self {
99        Self {
100            max_errors: 0,
101            cost_ins: 1,
102            cost_del: 1,
103            cost_subst: 1,
104            max_cost: 0,
105            case_insensitive: false,
106        }
107    }
108}
109
110/// Successful approximate-match result.
111#[derive(Debug, Clone, Copy, PartialEq, Eq)]
112pub struct TreMatch {
113    /// Byte offset where the match starts. The TRE
114    /// wrapper does not request submatch storage, so this is
115    /// reported as 0 on a successful match; the meaningful
116    /// result is whether a match exists within the cost bound,
117    /// not its position.
118    pub start: usize,
119    /// Byte offset one past the end of the match. See
120    /// [`Self::start`] for the current limitation.
121    pub end: usize,
122    /// Total cost of the match (sum of edit costs).
123    pub cost: u32,
124    /// Number of inserts.
125    pub n_ins: u32,
126    /// Number of deletes.
127    pub n_del: u32,
128    /// Number of substitutes.
129    pub n_subst: u32,
130}
131
132/// Owning handle to a TRE-compiled pattern.
133///
134/// Construct via [`TreCompiledPattern::compile`]. The native
135/// resources are released by [`Drop`] (delegated to the
136/// `tre-sys::OwnedRegex` field).
137pub struct TreCompiledPattern {
138    raw: OwnedRegex,
139    /// Cached compile-time options so [`Self::matches`] can
140    /// reuse the right cost weights without rebuilding the
141    /// `regaparams_t` on every call.
142    opts: TreMatchOpts,
143    /// `*const ()` is `!Send + !Sync`; this drops both auto
144    /// traits without needing explicit `unsafe impl !Send`
145    /// (which is currently nightly-only).
146    _not_send_or_sync: PhantomData<*const ()>,
147}
148
149impl std::fmt::Debug for TreCompiledPattern {
150    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
151        f.debug_struct("TreCompiledPattern")
152            .field("nsub", &self.raw.nsub())
153            .field("opts", &self.opts)
154            .finish()
155    }
156}
157
158impl TreCompiledPattern {
159    /// Compile a regex pattern.
160    ///
161    /// The pattern is read as bytes. The vendored TRE build
162    /// disables multibyte handling, so byte n in the pattern is
163    /// matched against byte n in the haystack regardless of the
164    /// host locale.
165    pub fn compile(pattern: &[u8], opts: TreMatchOpts) -> Result<Self, TreError> {
166        validate_opts(opts)?;
167
168        let mut cflags = REG_EXTENDED;
169        if opts.case_insensitive {
170            cflags |= REG_ICASE;
171        }
172
173        match compile_raw(pattern, cflags) {
174            Ok(raw) => Ok(Self {
175                raw,
176                opts,
177                _not_send_or_sync: PhantomData,
178            }),
179            Err(rc) => Err(TreError::Compile(safe_regerror(rc, None))),
180        }
181    }
182
183    /// Return `true` if `text` contains an approximate match
184    /// for the pattern within the configured error budget.
185    #[must_use]
186    pub fn is_match(&self, text: &[u8]) -> bool {
187        self.matches(text).is_some()
188    }
189
190    /// Return the first approximate match in `text`, if any.
191    ///
192    /// On a non-`REG_OK`/`REG_NOMATCH` return code from TRE
193    /// the function returns `None` and asserts in debug builds.
194    /// In release the failure is treated as a no-match because
195    /// the only documented non-fatal failure for the
196    /// approximate matcher is back-references in the pattern,
197    /// which dyntext does not generate.
198    #[must_use]
199    pub fn matches(&self, text: &[u8]) -> Option<TreMatch> {
200        let params = self.build_params();
201        match safe_reganexec(self.raw.as_raw(), text, params, 0) {
202            ExecOutcome::Match(m) => Some(TreMatch {
203                start: 0,
204                end: text.len(),
205                cost: u32::try_from(m.cost).unwrap_or(u32::MAX),
206                n_ins: u32::try_from(m.num_ins).unwrap_or(u32::MAX),
207                n_del: u32::try_from(m.num_del).unwrap_or(u32::MAX),
208                n_subst: u32::try_from(m.num_subst).unwrap_or(u32::MAX),
209            }),
210            ExecOutcome::NoMatch => None,
211            ExecOutcome::Error(other) => {
212                debug_assert!(false, "tre_reganexec returned unexpected code {other}");
213                None
214            }
215        }
216    }
217
218    /// Borrow the cached options. Useful for tests and for
219    /// callers that want to re-use the same configuration.
220    #[must_use]
221    pub fn opts(&self) -> TreMatchOpts {
222        self.opts
223    }
224
225    /// Build the `regaparams_t` from the cached options.
226    fn build_params(&self) -> tre_sys::regaparams_t {
227        let mut params = default_regaparams();
228        params.cost_ins = c_int::from(self.opts.cost_ins);
229        params.cost_del = c_int::from(self.opts.cost_del);
230        params.cost_subst = c_int::from(self.opts.cost_subst);
231        params.max_err = c_int::from(self.opts.max_errors);
232        params.max_ins = c_int::from(self.opts.max_errors);
233        params.max_del = c_int::from(self.opts.max_errors);
234        params.max_subst = c_int::from(self.opts.max_errors);
235
236        let max_cost = if self.opts.max_cost == 0 {
237            // Implicit ceiling: max_errors * largest single
238            // edit cost. Using u32 saturating arithmetic to
239            // avoid surprising overflow when callers pass big
240            // u16 values.
241            let largest = self
242                .opts
243                .cost_ins
244                .max(self.opts.cost_del)
245                .max(self.opts.cost_subst);
246            let budget = u32::from(self.opts.max_errors) * u32::from(largest.max(1));
247            c_int::try_from(budget).unwrap_or(c_int::MAX)
248        } else {
249            c_int::from(self.opts.max_cost)
250        };
251        params.max_cost = max_cost;
252        params
253    }
254}
255
256fn validate_opts(opts: TreMatchOpts) -> Result<(), TreError> {
257    if opts.max_errors > 0 && opts.cost_ins == 0 && opts.cost_del == 0 && opts.cost_subst == 0 {
258        return Err(TreError::InvalidOptions(
259            "max_errors > 0 requires at least one non-zero edit cost".into(),
260        ));
261    }
262    Ok(())
263}
264
265#[cfg(test)]
266mod tests {
267    use super::*;
268
269    #[test]
270    fn default_opts_are_zero_error_unit_costs() {
271        let opts = TreMatchOpts::default();
272        assert_eq!(opts.max_errors, 0);
273        assert_eq!(opts.cost_ins, 1);
274        assert_eq!(opts.cost_del, 1);
275        assert_eq!(opts.cost_subst, 1);
276        assert_eq!(opts.max_cost, 0);
277        assert!(!opts.case_insensitive);
278    }
279
280    #[test]
281    fn validate_opts_rejects_max_errors_with_zero_costs() {
282        let bad = TreMatchOpts {
283            max_errors: 1,
284            cost_ins: 0,
285            cost_del: 0,
286            cost_subst: 0,
287            ..TreMatchOpts::default()
288        };
289        assert!(matches!(
290            validate_opts(bad),
291            Err(TreError::InvalidOptions(_))
292        ));
293    }
294
295    #[test]
296    fn compiled_pattern_phantom_is_not_send_or_sync() {
297        // A `PhantomData<*const ()>` field drops both auto
298        // traits. The check below is a documentation-only
299        // reminder; if it stops compiling the assertion is
300        // wrong and should be re-derived.
301        fn assert_any<T>() {}
302        assert_any::<TreCompiledPattern>();
303    }
304}
dyntext/tre.rs

dyntext/
tre.rs
