1 /*!
2 This module defines tests and test helpers for substring implementations.
3 */
4 
5 use alloc::{
6     boxed::Box,
7     format,
8     string::{String, ToString},
9 };
10 
11 pub(crate) mod naive;
12 #[macro_use]
13 pub(crate) mod prop;
14 
15 const SEEDS: &'static [Seed] = &[
16     Seed::new("", "", Some(0), Some(0)),
17     Seed::new("", "a", Some(0), Some(1)),
18     Seed::new("", "ab", Some(0), Some(2)),
19     Seed::new("", "abc", Some(0), Some(3)),
20     Seed::new("a", "", None, None),
21     Seed::new("a", "a", Some(0), Some(0)),
22     Seed::new("a", "aa", Some(0), Some(1)),
23     Seed::new("a", "ba", Some(1), Some(1)),
24     Seed::new("a", "bba", Some(2), Some(2)),
25     Seed::new("a", "bbba", Some(3), Some(3)),
26     Seed::new("a", "bbbab", Some(3), Some(3)),
27     Seed::new("a", "bbbabb", Some(3), Some(3)),
28     Seed::new("a", "bbbabbb", Some(3), Some(3)),
29     Seed::new("a", "bbbbbb", None, None),
30     Seed::new("ab", "", None, None),
31     Seed::new("ab", "a", None, None),
32     Seed::new("ab", "b", None, None),
33     Seed::new("ab", "ab", Some(0), Some(0)),
34     Seed::new("ab", "aab", Some(1), Some(1)),
35     Seed::new("ab", "aaab", Some(2), Some(2)),
36     Seed::new("ab", "abaab", Some(0), Some(3)),
37     Seed::new("ab", "baaab", Some(3), Some(3)),
38     Seed::new("ab", "acb", None, None),
39     Seed::new("ab", "abba", Some(0), Some(0)),
40     Seed::new("abc", "ab", None, None),
41     Seed::new("abc", "abc", Some(0), Some(0)),
42     Seed::new("abc", "abcz", Some(0), Some(0)),
43     Seed::new("abc", "abczz", Some(0), Some(0)),
44     Seed::new("abc", "zabc", Some(1), Some(1)),
45     Seed::new("abc", "zzabc", Some(2), Some(2)),
46     Seed::new("abc", "azbc", None, None),
47     Seed::new("abc", "abzc", None, None),
48     Seed::new("abczdef", "abczdefzzzzzzzzzzzzzzzzzzzz", Some(0), Some(0)),
49     Seed::new("abczdef", "zzzzzzzzzzzzzzzzzzzzabczdef", Some(20), Some(20)),
50     Seed::new(
51         "xyz",
52         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxyz",
53         Some(32),
54         Some(32),
55     ),
56     Seed::new("\u{0}\u{15}", "\u{0}\u{15}\u{15}\u{0}", Some(0), Some(0)),
57     Seed::new("\u{0}\u{1e}", "\u{1e}\u{0}", None, None),
58 ];
59 
60 /// Runs a host of substring search tests.
61 ///
62 /// This has support for "partial" substring search implementations only work
63 /// for a subset of needles/haystacks. For example, the "packed pair" substring
64 /// search implementation only works for haystacks of some minimum length based
65 /// of the pair of bytes selected and the size of the vector used.
66 pub(crate) struct Runner {
67     fwd: Option<
68         Box<dyn FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static>,
69     >,
70     rev: Option<
71         Box<dyn FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static>,
72     >,
73 }
74 
75 impl Runner {
76     /// Create a new test runner for forward and reverse substring search
77     /// implementations.
new() -> Runner78     pub(crate) fn new() -> Runner {
79         Runner { fwd: None, rev: None }
80     }
81 
82     /// Run all tests. This panics on the first failure.
83     ///
84     /// If the implementation being tested returns `None` for a particular
85     /// haystack/needle combination, then that test is skipped.
86     ///
87     /// This runs tests on both the forward and reverse implementations given.
88     /// If either (or both) are missing, then tests for that implementation are
89     /// skipped.
run(self)90     pub(crate) fn run(self) {
91         if let Some(mut fwd) = self.fwd {
92             for seed in SEEDS.iter() {
93                 for t in seed.generate() {
94                     match fwd(t.haystack.as_bytes(), t.needle.as_bytes()) {
95                         None => continue,
96                         Some(result) => {
97                             assert_eq!(
98                                 t.fwd, result,
99                                 "FORWARD, needle: {:?}, haystack: {:?}",
100                                 t.needle, t.haystack,
101                             );
102                         }
103                     }
104                 }
105             }
106         }
107         if let Some(mut rev) = self.rev {
108             for seed in SEEDS.iter() {
109                 for t in seed.generate() {
110                     match rev(t.haystack.as_bytes(), t.needle.as_bytes()) {
111                         None => continue,
112                         Some(result) => {
113                             assert_eq!(
114                                 t.rev, result,
115                                 "REVERSE, needle: {:?}, haystack: {:?}",
116                                 t.needle, t.haystack,
117                             );
118                         }
119                     }
120                 }
121             }
122         }
123     }
124 
125     /// Set the implementation for forward substring search.
126     ///
127     /// If the closure returns `None`, then it is assumed that the given
128     /// test cannot be applied to the particular implementation and it is
129     /// skipped. For example, if a particular implementation only supports
130     /// needles or haystacks for some minimum length.
131     ///
132     /// If this is not set, then forward substring search is not tested.
fwd( mut self, search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static, ) -> Runner133     pub(crate) fn fwd(
134         mut self,
135         search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static,
136     ) -> Runner {
137         self.fwd = Some(Box::new(search));
138         self
139     }
140 
141     /// Set the implementation for reverse substring search.
142     ///
143     /// If the closure returns `None`, then it is assumed that the given
144     /// test cannot be applied to the particular implementation and it is
145     /// skipped. For example, if a particular implementation only supports
146     /// needles or haystacks for some minimum length.
147     ///
148     /// If this is not set, then reverse substring search is not tested.
rev( mut self, search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static, ) -> Runner149     pub(crate) fn rev(
150         mut self,
151         search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static,
152     ) -> Runner {
153         self.rev = Some(Box::new(search));
154         self
155     }
156 }
157 
158 /// A single substring test for forward and reverse searches.
159 #[derive(Clone, Debug)]
160 struct Test {
161     needle: String,
162     haystack: String,
163     fwd: Option<usize>,
164     rev: Option<usize>,
165 }
166 
167 /// A single substring test for forward and reverse searches.
168 ///
169 /// Each seed is valid on its own, but it also serves as a starting point
170 /// to generate more tests. Namely, we pad out the haystacks with other
171 /// characters so that we get more complete coverage. This is especially useful
172 /// for testing vector algorithms that tend to have weird special cases for
173 /// alignment and loop unrolling.
174 ///
175 /// Padding works by assuming certain characters never otherwise appear in a
176 /// needle or a haystack. Neither should contain a `#` character.
177 #[derive(Clone, Copy, Debug)]
178 struct Seed {
179     needle: &'static str,
180     haystack: &'static str,
181     fwd: Option<usize>,
182     rev: Option<usize>,
183 }
184 
185 impl Seed {
186     const MAX_PAD: usize = 34;
187 
new( needle: &'static str, haystack: &'static str, fwd: Option<usize>, rev: Option<usize>, ) -> Seed188     const fn new(
189         needle: &'static str,
190         haystack: &'static str,
191         fwd: Option<usize>,
192         rev: Option<usize>,
193     ) -> Seed {
194         Seed { needle, haystack, fwd, rev }
195     }
196 
generate(self) -> impl Iterator<Item = Test>197     fn generate(self) -> impl Iterator<Item = Test> {
198         assert!(!self.needle.contains('#'), "needle must not contain '#'");
199         assert!(!self.haystack.contains('#'), "haystack must not contain '#'");
200         (0..=Seed::MAX_PAD)
201             // Generate tests for padding at the beginning of haystack.
202             .map(move |pad| {
203                 let needle = self.needle.to_string();
204                 let prefix = "#".repeat(pad);
205                 let haystack = format!("{}{}", prefix, self.haystack);
206                 let fwd = if needle.is_empty() {
207                     Some(0)
208                 } else {
209                     self.fwd.map(|i| pad + i)
210                 };
211                 let rev = if needle.is_empty() {
212                     Some(haystack.len())
213                 } else {
214                     self.rev.map(|i| pad + i)
215                 };
216                 Test { needle, haystack, fwd, rev }
217             })
218             // Generate tests for padding at the end of haystack.
219             .chain((1..=Seed::MAX_PAD).map(move |pad| {
220                 let needle = self.needle.to_string();
221                 let suffix = "#".repeat(pad);
222                 let haystack = format!("{}{}", self.haystack, suffix);
223                 let fwd = if needle.is_empty() { Some(0) } else { self.fwd };
224                 let rev = if needle.is_empty() {
225                     Some(haystack.len())
226                 } else {
227                     self.rev
228                 };
229                 Test { needle, haystack, fwd, rev }
230             }))
231     }
232 }
233