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