1 #![cfg(feature = "pattern")]
2 #![feature(pattern)]
3 #![allow(dead_code)]
4 
5 extern crate twoway;
6 
7 extern crate quickcheck;
8 extern crate itertools as it;
9 extern crate odds;
10 #[macro_use] extern crate macro_attr;
11 #[macro_use] extern crate newtype_derive;
12 
13 mod quickchecks {
14 
15 use twoway::{Str, StrSearcher};
16 use twoway::{
17     find_str,
18     rfind_str,
19 };
20 use it::{Itertools, unfold};
21 
22 use std::str::pattern::{Pattern, Searcher, ReverseSearcher, SearchStep};
23 use std::str::pattern::SearchStep::{Match, Reject, Done};
24 
25 use std::ops::Deref;
26 
27 use odds::string::StrExt;
28 
29 use quickcheck as qc;
30 use quickcheck::TestResult;
31 use quickcheck::Arbitrary;
32 use quickcheck::quickcheck;
33 
34 #[derive(Copy, Clone, Debug)]
35 /// quickcheck Arbitrary adaptor - half the size of `T` on average
36 struct Short<T>(T);
37 
38 impl<T> Deref for Short<T> {
39     type Target = T;
deref(&self) -> &T40     fn deref(&self) -> &T { &self.0 }
41 }
42 
43 impl<T> Arbitrary for Short<T>
44     where T: Arbitrary
45 {
arbitrary<G: qc::Gen>(g: &mut G) -> Self46     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
47         let sz = g.size() / 2;
48         Short(T::arbitrary(&mut qc::StdGen::new(g, sz)))
49     }
50 
shrink(&self) -> Box<Iterator<Item=Self>>51     fn shrink(&self) -> Box<Iterator<Item=Self>> {
52         Box::new((**self).shrink().map(Short))
53     }
54 }
55 
56 macro_attr! {
57     #[derive(Clone, Debug, NewtypeDeref!)]
58     struct Text(String);
59 }
60 
61 static ALPHABET: &'static str = "abñòαβ\u{3c72}";
62 static SIMPLEALPHABET: &'static str = "ab";
63 
64 impl Arbitrary for Text {
arbitrary<G: qc::Gen>(g: &mut G) -> Self65     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
66         let len = u16::arbitrary(g);
67         let mut s = String::with_capacity(len as usize);
68         let alpha_len = ALPHABET.chars().count();
69         for _ in 0..len {
70             let i = usize::arbitrary(g);
71             let i = i % alpha_len;
72             s.push(ALPHABET.chars().nth(i).unwrap());
73         }
74         Text(s)
75     }
shrink(&self) -> Box<Iterator<Item=Self>>76     fn shrink(&self) -> Box<Iterator<Item=Self>> {
77         Box::new(self.0.shrink().map(Text))
78     }
79 }
80 
81 /// Text from an alphabet of only two letters
82 macro_attr! {
83     #[derive(Clone, Debug, NewtypeDeref!)]
84     struct SimpleText(String);
85 }
86 
87 impl Arbitrary for SimpleText {
arbitrary<G: qc::Gen>(g: &mut G) -> Self88     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
89         let len = u16::arbitrary(g);
90         let mut s = String::with_capacity(len as usize);
91         let alpha_len = SIMPLEALPHABET.chars().count();
92         for _ in 0..len {
93             let i = usize::arbitrary(g);
94             let i = i % alpha_len;
95             s.push(SIMPLEALPHABET.chars().nth(i).unwrap());
96         }
97         SimpleText(s)
98     }
shrink(&self) -> Box<Iterator<Item=Self>>99     fn shrink(&self) -> Box<Iterator<Item=Self>> {
100         Box::new(self.0.shrink().map(SimpleText))
101     }
102 }
103 
104 #[derive(Clone, Debug)]
105 struct ShortText(String);
106 // Half the length of Text on average
107 impl Arbitrary for ShortText {
arbitrary<G: qc::Gen>(g: &mut G) -> Self108     fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
109         let len = u16::arbitrary(g) / 2;
110         let mut s = String::with_capacity(len as usize);
111         let alpha_len = ALPHABET.chars().count();
112         for _ in 0..len {
113             let i = usize::arbitrary(g);
114             let i = i % alpha_len;
115             s.push(ALPHABET.chars().nth(i).unwrap());
116         }
117         ShortText(s)
118     }
shrink(&self) -> Box<Iterator<Item=Self>>119     fn shrink(&self) -> Box<Iterator<Item=Self>> {
120         Box::new(self.0.shrink().map(ShortText))
121     }
122 }
123 
contains(hay: &str, n: &str) -> bool124 pub fn contains(hay: &str, n: &str) -> bool {
125     Str(n).is_contained_in(hay)
126 }
127 
find(hay: &str, n: &str) -> Option<usize>128 pub fn find(hay: &str, n: &str) -> Option<usize> {
129     Str(n).into_searcher(hay).next_match().map(|(a, _)| a)
130 }
131 
contains_rev(hay: &str, n: &str) -> bool132 pub fn contains_rev(hay: &str, n: &str) -> bool {
133     let mut tws = StrSearcher::new(hay, n);
134     loop {
135         match tws.next_back() {
136             SearchStep::Done => return false,
137             SearchStep::Match(..) => return true,
138             _ => { }
139         }
140     }
141 }
142 
rfind(hay: &str, n: &str) -> Option<usize>143 pub fn rfind(hay: &str, n: &str) -> Option<usize> {
144     Str(n).into_searcher(hay).next_match_back().map(|(a, _)| a)
145 }
146 
147 #[test]
test_contains()148 fn test_contains() {
149     fn prop(a: Text, b: Short<Text>) -> TestResult {
150         let a = &a.0;
151         let b = &b[..];
152         let truth = a.contains(b);
153         TestResult::from_bool(contains(&a, &b) == truth)
154     }
155     quickcheck(prop as fn(_, _) -> _);
156 }
157 
158 #[test]
test_contains_rev()159 fn test_contains_rev() {
160     fn prop(a: Text, b: Short<Text>) -> TestResult {
161         let a = &a.0;
162         let b = &b[..];
163         let truth = a.contains(b);
164         TestResult::from_bool(contains_rev(&a, &b) == truth)
165     }
166     quickcheck(prop as fn(_, _) -> _);
167 }
168 
169 #[test]
test_find_str()170 fn test_find_str() {
171     fn prop(a: Text, b: Short<Text>) -> TestResult {
172         let a = &a.0;
173         let b = &b[..];
174         let truth = a.find(b);
175         TestResult::from_bool(find_str(&a, &b) == truth)
176     }
177     quickcheck(prop as fn(_, _) -> _);
178 }
179 
180 #[test]
test_rfind_str()181 fn test_rfind_str() {
182     fn prop(a: Text, b: Short<Text>) -> TestResult {
183         let a = &a.0;
184         let b = &b[..];
185         let truth = a.rfind(b);
186         TestResult::from_bool(rfind_str(&a, &b) == truth)
187     }
188     quickcheck(prop as fn(_, _) -> _);
189 }
190 
191 #[test]
test_contains_plus()192 fn test_contains_plus() {
193     fn prop(a: Text, b: Short<Text>) -> TestResult {
194         let a = &a.0;
195         let b = &b[..];
196         //let b = &b.0;
197         if b.len() == 0 { return TestResult::discard() }
198         let truth = a.contains(b);
199         TestResult::from_bool(contains(&a, &b) == truth &&
200             (!truth || b.substrings().all(|sub| contains(&a, sub))))
201     }
202     quickcheck(prop as fn(_, _) -> _);
203 }
204 
205 #[test]
test_contains_rev_plus()206 fn test_contains_rev_plus() {
207     fn prop(a: Text, b: Short<Text>) -> TestResult {
208         let a = &a.0;
209         let b = &b[..];
210         if b.len() == 0 { return TestResult::discard() }
211         let truth = a.contains(b);
212         TestResult::from_bool(contains_rev(&a, &b) == truth &&
213             (!truth || b.substrings().all(|sub| contains_rev(&a, sub))))
214     }
215     quickcheck(prop as fn(_, _) -> _);
216 }
217 
218 #[test]
test_starts_with()219 fn test_starts_with() {
220     fn prop(a: Text, b: Short<Text>) -> TestResult {
221         let a = &a.0;
222         let b = &b[..];
223         let truth = a.starts_with(b);
224         TestResult::from_bool(Str(b).is_prefix_of(a) == truth)
225     }
226     quickcheck(prop as fn(_, _) -> _);
227 }
228 
229 #[test]
test_ends_with()230 fn test_ends_with() {
231     fn prop(a: Text, b: Short<Text>) -> TestResult {
232         let a = &a.0;
233         let b = &b[..];
234         let truth = a.ends_with(b);
235         TestResult::from_bool(Str(b).is_suffix_of(a) == truth)
236     }
237     quickcheck(prop as fn(_, _) -> _);
238 }
239 
240 #[test]
test_next_reject()241 fn test_next_reject() {
242     fn prop(a: Text, b: Short<Text>) -> TestResult {
243         let a = &a.0;
244         let b = &b[..];
245         let truth = b.into_searcher(a).next_reject().map(|(a, _)| a);
246         TestResult::from_bool(Str(b).into_searcher(a).next_reject().map(|(a, _)| a) == truth)
247     }
248     quickcheck(prop as fn(_, _) -> _);
249 }
250 
251 #[test]
test_next_reject_back()252 fn test_next_reject_back() {
253     fn prop(a: Text, b: Short<Text>) -> TestResult {
254         let a = &a.0;
255         let b = &b[..];
256         let truth = b.into_searcher(a).next_reject_back().map(|(_, b)| b);
257         TestResult::from_bool(Str(b).into_searcher(a).next_reject_back().map(|(_, b)| b) == truth)
258     }
259     quickcheck(prop as fn(_, _) -> _);
260 }
261 
coalesce_rejects(a: SearchStep, b: SearchStep) -> Result<SearchStep, (SearchStep, SearchStep)>262 fn coalesce_rejects(a: SearchStep, b: SearchStep)
263     -> Result<SearchStep, (SearchStep, SearchStep)>
264 {
265     match (a, b) {
266         (SearchStep::Reject(a, b), SearchStep::Reject(c, d)) => {
267             assert_eq!(b, c);
268             Ok(SearchStep::Reject(a, d))
269         }
270         otherwise => Err(otherwise),
271     }
272 }
273 
coalesce_intervals(a: Option<(usize, usize)>, b: Option<(usize, usize)> ) -> Result<Option<(usize, usize)>, (Option<(usize, usize)>, Option<(usize, usize)>)>274 fn coalesce_intervals(a: Option<(usize, usize)>, b: Option<(usize, usize)> )
275     -> Result<Option<(usize, usize)>, (Option<(usize, usize)>, Option<(usize, usize)>)>
276 {
277     match (a, b) {
278         (Some((x, y)), Some((w, z))) => {
279             assert_eq!(y, w);
280             Ok(Some((x, z)))
281         }
282         otherwise => Err(otherwise),
283     }
284 }
285 
286 // Test that all search steps are contiguous
287 #[test]
test_search_steps()288 fn test_search_steps() {
289     fn prop(a: Text, b: Text) -> bool {
290         let hay = &a.0;
291         let n = &b.0;
292         let tws = StrSearcher::new(hay, n);
293         // Make sure it covers the whole string
294         let mut search_steps = unfold(tws, |tws| {
295             match tws.next() {
296                 SearchStep::Done => None,
297                 otherwise => Some(otherwise),
298             }
299         }).map(|step| match step {
300             SearchStep::Match(a, b) | SearchStep::Reject(a, b) => Some((a, b)),
301             SearchStep::Done => None,
302         }).coalesce(coalesce_intervals);
303         match search_steps.next() {
304             None => hay.len() == 0,
305             Some(None) => true,
306             Some(Some((a, b))) => {
307                 //println!("Next step would be: {:?}", search_steps.next());
308                 assert_eq!((a, b), (0, hay.len()));
309                 true
310             }
311         }
312         //assert_eq!(search_steps.next(), Some(SearchStep::Match(0, a.len())));
313         //true
314         //search_steps.next() == Some(SearchStep::Match(0, a.len()))    }
315     }
316     quickcheck(prop as fn(_, _) -> _);
317 }
318 
319 #[test]
test_search_steps_rev()320 fn test_search_steps_rev() {
321     fn prop(a: Text, b: Text) -> bool {
322         let hay = &a.0;
323         let n = &b.0;
324         let tws = StrSearcher::new(hay, n);
325         // Make sure it covers the whole string
326         let mut search_steps = unfold(tws, |tws| {
327             match tws.next_back() {
328                 SearchStep::Done => None,
329                 otherwise => Some(otherwise),
330             }
331         }).map(|step| match step {
332             SearchStep::Match(a, b) | SearchStep::Reject(a, b) => Some((a, b)),
333             SearchStep::Done => None,
334         }).coalesce(|a, b| match coalesce_intervals(b, a) {
335             // adaption for reverse order
336             Ok(c) => Ok(c),
337             Err((d, e)) => Err((e, d)),
338         });
339         match search_steps.next() {
340             None => hay.len() == 0,
341             Some(None) => true,
342             Some(Some((a, b))) => {
343                 //println!("Next step would be: {:?}", search_steps.next());
344                 assert_eq!((a, b), (0, hay.len()));
345                 true
346             }
347         }
348         //assert_eq!(search_steps.next(), Some(SearchStep::Match(0, a.len())));
349         //true
350         //search_steps.next() == Some(SearchStep::Match(0, a.len()))    }
351     }
352     quickcheck(prop as fn(_, _) -> _);
353 }
354 
355 // Test that all search steps are well formed
356 #[test]
test_search_steps_wf()357 fn test_search_steps_wf() {
358     fn prop(a: Text, b: Text) -> bool {
359         let hay = &a.0;
360         let n = &b.0;
361         let mut tws = StrSearcher::new(hay, n);
362         let mut rejects_seen = 0; // n rejects seen since last match
363         let test_single_rejects = false;
364         let test_utf8_boundaries = true;
365         loop {
366             match tws.next() {
367                 Reject(a, b) => {
368                     assert!(!test_single_rejects || rejects_seen == 0);
369                     assert!(!test_utf8_boundaries || (hay.is_char_boundary(a) && hay.is_char_boundary(b)));
370                     rejects_seen += 1;
371                     assert!(a != b, "Reject({}, {}) is zero size", a, b);
372                 }
373                 Match(a, b) => {
374                     assert_eq!(b - a, n.len());
375                     assert!(!test_single_rejects || rejects_seen <= 1, "rejects_seen={}", rejects_seen);
376                     rejects_seen = 0;
377                 }
378                 Done => {
379                     assert!(!test_single_rejects || rejects_seen <= 1, "rejects_seen={}", rejects_seen);
380                     break;
381                 }
382             }
383         }
384         true
385     }
386     quickcheck(prop as fn(_, _) -> _);
387 }
388 
389 // Test that all search steps are well formed
390 #[test]
test_search_steps_wf_rev()391 fn test_search_steps_wf_rev() {
392     fn prop(a: Text, b: Text) -> bool {
393         let hay = &a.0;
394         let n = &b.0;
395         let mut tws = StrSearcher::new(hay, n);
396         let mut rejects_seen = 0; // n rejects seen since last match
397         let test_single_rejects = false;
398         let test_utf8_boundaries = true;
399         loop {
400             match tws.next_back() {
401                 Reject(a, b) => {
402                     assert!(!test_utf8_boundaries || (hay.is_char_boundary(a) && hay.is_char_boundary(b)));
403                     assert!(!test_single_rejects || rejects_seen == 0);
404                     rejects_seen += 1;
405                     assert!(a != b, "Reject({}, {}) is zero size", a, b);
406                 }
407                 Match(a, b) => {
408                     assert_eq!(b - a, n.len());
409                     assert!(!test_single_rejects || rejects_seen <= 1, "rejects_seen={}", rejects_seen);
410                     rejects_seen = 0;
411                 }
412                 Done => {
413                     assert!(!test_single_rejects || rejects_seen <= 1, "rejects_seen={}", rejects_seen);
414                     break;
415                 }
416             }
417         }
418         true
419     }
420     quickcheck(prop as fn(_, _) -> _);
421 }
422 
423 #[test]
test_contains_substrings()424 fn test_contains_substrings() {
425     fn prop(s: (char, char, char, char)) -> bool {
426         let mut ss = String::new();
427         ss.push(s.0);
428         ss.push(s.1);
429         ss.push(s.2);
430         ss.push(s.3);
431         let a = &ss;
432         for sub in a.substrings() {
433             assert!(a.contains(sub));
434             if !contains(a, sub) {
435                 return false;
436             }
437         }
438         true
439     }
440     quickcheck(prop as fn(_) -> _);
441 }
442 
443 #[test]
test_contains_substrings_rev()444 fn test_contains_substrings_rev() {
445     fn prop(s: (char, char, char, char)) -> bool {
446         let mut ss = String::new();
447         ss.push(s.0);
448         ss.push(s.1);
449         ss.push(s.2);
450         ss.push(s.3);
451         let a = &ss;
452         for sub in a.substrings() {
453             assert!(a.contains(sub));
454             if !contains_rev(a, sub) {
455                 return false;
456             }
457         }
458         true
459     }
460     quickcheck(prop as fn(_) -> _);
461 }
462 
463 #[test]
test_find_period()464 fn test_find_period() {
465     fn prop(a: SimpleText, b: Short<SimpleText>) -> TestResult {
466         let a = &a.0;
467         let b = &b[..];
468         let pat = [b, b].concat();
469         let truth = a.find(&pat);
470         TestResult::from_bool(find(a, &pat) == truth)
471     }
472     quickcheck(prop as fn(_, _) -> _);
473 }
474 
475 #[test]
test_find_rev_period()476 fn test_find_rev_period() {
477     fn prop(a: SimpleText, b: Short<SimpleText>) -> TestResult {
478         let a = &a.0;
479         let b = &b[..];
480         let pat = [b, b].concat();
481         let truth = a.rfind(&pat);
482         TestResult::from_bool(rfind(a, &pat) == truth)
483     }
484     quickcheck(prop as fn(_, _) -> _);
485 }
486 
487 
488 }
489