vyre_libs/scan/substring/
substring.rs

1//! Brute-force substring search  -  each invocation checks whether the
2//! needle matches at its starting byte offset, writes `1` to the
3//! match bitmap at that offset on hit.
4//!
5//! Category A composition. Sufficient for short needles; long
6//! needles should compile to a DFA via the future `dfa_compile`
7//! function and use that as a prefilter.
8
9use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
10
11use crate::region::wrap_anonymous;
12
13/// Canonical scan op id.
14pub const SCAN_SUBSTRING_OP_ID: &str = "vyre-libs::scan::substring_search";
15/// Deprecated matching op id retained only by the matching compatibility path.
16pub(crate) const LEGACY_MATCHING_SUBSTRING_OP_ID: &str = "vyre-libs::matching::substring_search";
17
18/// Build a Program that writes `1` to `matches[i]` when `haystack[i..]`
19/// starts with `needle`, else `0`. Both buffers are u32 byte arrays
20/// packed one byte per u32 for simplicity (a future packed-u8 version
21/// is Category A over `DataType::U8`).
22#[must_use]
23pub fn substring_search(
24    haystack: &str,
25    needle: &str,
26    matches: &str,
27    haystack_len: u32,
28    needle_len: u32,
29) -> Program {
30    substring_search_with_op_id(
31        SCAN_SUBSTRING_OP_ID,
32        haystack,
33        needle,
34        matches,
35        haystack_len,
36        needle_len,
37    )
38}
39
40/// Build a substring Program with an explicit compatibility op id.
41#[must_use]
42pub(crate) fn substring_search_with_op_id(
43    op_id: &str,
44    haystack: &str,
45    needle: &str,
46    matches: &str,
47    haystack_len: u32,
48    needle_len: u32,
49) -> Program {
50    let counted_storage = |name: &str, binding, count| {
51        let decl = BufferDecl::storage(name, binding, BufferAccess::ReadOnly, DataType::U32);
52        if count == 0 {
53            decl
54        } else {
55            decl.with_count(count)
56        }
57    };
58    let output_count = haystack_len.max(1);
59    let visible_output_bytes = (haystack_len as usize).saturating_mul(4);
60    let output = BufferDecl::output(matches, 2, DataType::U32)
61        .with_count(output_count)
62        .with_output_byte_range(0..visible_output_bytes);
63
64    let i = Expr::var("i");
65    // ok accumulates AND of per-byte equality checks. Start at 1; each
66    // byte mismatch AND-s in 0 and latches the match bit off.
67    let mut check_body: Vec<Node> = vec![Node::let_bind("ok", Expr::u32(1))];
68    // Walk the needle one byte at a time. bytes are packed u32/byte for
69    // simplicity  -  a packed-u8 variant is Category A over DataType::U8.
70    check_body.push(Node::loop_for(
71        "k",
72        Expr::u32(0),
73        Expr::u32(needle_len),
74        vec![Node::assign(
75            "ok",
76            Expr::bitand(
77                Expr::var("ok"),
78                // Select turns the bool comparison into u32 {0,1} so
79                // the accumulator stays in integer arithmetic.
80                Expr::select(
81                    Expr::eq(
82                        Expr::load(haystack, Expr::add(i.clone(), Expr::var("k"))),
83                        Expr::load(needle, Expr::var("k")),
84                    ),
85                    Expr::u32(1),
86                    Expr::u32(0),
87                ),
88            ),
89        )],
90    ));
91    check_body.push(Node::Store {
92        buffer: matches.into(),
93        index: i.clone(),
94        value: Expr::var("ok"),
95    });
96
97    // Overflow-safe guard. The straight expression `i + needle_len <= buf_len`
98    // can wrap at i ≈ u32::MAX − needle_len, producing a false positive on the
99    // last few offsets. The correct invariant is `i <= buf_len - needle_len`;
100    // we rewrite it as a subtraction-free chain of comparisons by reasoning
101    // through `buf_len` only:
102    //
103    //   needle_len <= buf_len  ∧  i + needle_len <= buf_len
104    //
105    // Passing both conjuncts also handles the empty-haystack case (buf_len=0,
106    // needle_len=0, i=0 → both true → vacuous check_body).
107    // V7-CORR-006: the original guard `i + needle_len <= haystack_len`
108    // wraps when i is near u32::MAX (Expr::add is Expr::BinOp { Add,
109    // .. } which u32::wrapping_add). We rewrite as two separate
110    // non-wrapping comparisons: (1) needle_len <= haystack_len ensures
111    // the implicit subtraction in (2) is non-underflowing, and (2)
112    // `i <= haystack_len - needle_len` keeps the rhs a constant-folded
113    // expression from the builder so no wrap is possible. Since
114    // needle_len is a compile-time u32 and haystack_len is a runtime
115    // u32, the host-side `saturating_sub` pre-computes the cap value
116    // safely and lets Expr::le do the comparison without Expr::add.
117    let body = vec![
118        Node::let_bind("i", Expr::InvocationId { axis: 0 }),
119        Node::let_bind("haystack_len", Expr::buf_len(haystack)),
120        Node::if_then(
121            Expr::and(
122                Expr::le(Expr::u32(needle_len), Expr::var("haystack_len")),
123                Expr::le(
124                    i.clone(),
125                    // `haystack_len - needle_len` as a runtime Expr sub. If
126                    // the compile-time needle_len exceeds the runtime
127                    // haystack_len the first conjunct already short-
128                    // circuits, so this sub-expression is evaluated only
129                    // on the safe branch (eager vs lazy evaluation is
130                    // the job of the optimizer's short-circuit pass  -
131                    // here the conjunct ordering gives a safe guard).
132                    Expr::sub(Expr::var("haystack_len"), Expr::u32(needle_len)),
133                ),
134            ),
135            check_body,
136        ),
137    ];
138    Program::wrapped(
139        vec![
140            counted_storage(haystack, 0, haystack_len),
141            counted_storage(needle, 1, needle_len),
142            output,
143        ],
144        [64, 1, 1],
145        vec![wrap_anonymous(op_id, body)],
146    )
147}
148
149inventory::submit! {
150    crate::harness::OpEntry {
151        id: SCAN_SUBSTRING_OP_ID,
152        build: || substring_search("haystack", "needle", "matches", 8, 3),
153        test_inputs: Some(|| {
154            let to_u32_vec = |s: &str| s.bytes().map(u32::from).collect::<Vec<_>>();
155            vec![
156                vec![
157                    crate::test_support::byte_pack::u32_bytes(&to_u32_vec("abcabc++")),
158                    crate::test_support::byte_pack::u32_bytes(&to_u32_vec("abc")),
159                ],
160                vec![
161                    crate::test_support::byte_pack::u32_bytes(&to_u32_vec("xyzxyzxy")),
162                    crate::test_support::byte_pack::u32_bytes(&to_u32_vec("xyz")),
163                ]
164            ]
165        }),
166        expected_output: Some(|| {
167            // Case 0: haystack="abcabc++", needle="abc". Matches at
168            //   i ∈ {0, 3}. Positions i > haystack_len - needle_len
169            //   (5) stay at their zero init because the guard never
170            //   fires.
171            // Case 1: haystack="xyzxyzxy", needle="xyz". Matches at
172            //   i ∈ {0, 3}.
173            let case0 = crate::test_support::byte_pack::u32_bytes(&[1u32, 0, 0, 1, 0, 0, 0, 0]);
174            let case1 = crate::test_support::byte_pack::u32_bytes(&[1u32, 0, 0, 1, 0, 0, 0, 0]);
175            vec![vec![case0], vec![case1]]
176        }),
177        category: Some("scan"),
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    #[test]
186    fn canonical_scan_builder_uses_scan_op_id_not_matching_id() {
187        let program = substring_search("haystack", "needle", "matches", 8, 3);
188        let [Node::Region { generator, .. }] = program.entry() else {
189            panic!("expected substring search to emit one scan region");
190        };
191
192        assert_eq!(generator.as_str(), SCAN_SUBSTRING_OP_ID);
193        assert_ne!(generator.as_str(), LEGACY_MATCHING_SUBSTRING_OP_ID);
194    }
195
196    #[test]
197    fn explicit_compatibility_builder_preserves_legacy_op_id() {
198        let program = substring_search_with_op_id(
199            LEGACY_MATCHING_SUBSTRING_OP_ID,
200            "haystack",
201            "needle",
202            "matches",
203            8,
204            3,
205        );
206        let [Node::Region { generator, .. }] = program.entry() else {
207            panic!("expected substring compatibility search to emit one region");
208        };
209
210        assert_eq!(generator.as_str(), LEGACY_MATCHING_SUBSTRING_OP_ID);
211    }
212
213    #[test]
214    fn source_boundary_keeps_matching_identity_out_of_canonical_builder() {
215        let source = include_str!("substring.rs");
216        let canonical_builder = source
217            .split("pub fn substring_search(")
218            .nth(1)
219            .expect("Fix: canonical substring builder must exist")
220            .split("/// Build a substring Program with an explicit compatibility op id.")
221            .next()
222            .expect("Fix: compatibility builder must follow canonical substring builder");
223
224        assert!(canonical_builder.contains("SCAN_SUBSTRING_OP_ID"));
225        assert!(!canonical_builder.contains("LEGACY_MATCHING_SUBSTRING_OP_ID"));
226        assert!(!canonical_builder.contains("vyre-libs::matching::substring_search"));
227    }
228}
vyre_libs/scan/substring/substring.rs

vyre_libs/scan/substring/
substring.rs
