1 //! Common splitter for strings and slices
2 //!
3 //! This module is private, so these items are effectively `pub(super)`
4 
5 use iter::plumbing::{UnindexedProducer, Folder};
6 
7 /// Common producer for splitting on a predicate.
8 pub struct SplitProducer<'p, P: 'p, V> {
9     data: V,
10     separator: &'p P,
11 
12     /// Marks the endpoint beyond which we've already found no separators.
13     tail: usize,
14 }
15 
16 /// Helper trait so `&str`, `&[T]`, and `&mut [T]` can share `SplitProducer`.
17 pub trait Fissile<P>: Sized {
length(&self) -> usize18     fn length(&self) -> usize;
midpoint(&self, end: usize) -> usize19     fn midpoint(&self, end: usize) -> usize;
find(&self, separator: &P, start: usize, end: usize) -> Option<usize>20     fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize>;
rfind(&self, separator: &P, end: usize) -> Option<usize>21     fn rfind(&self, separator: &P, end: usize) -> Option<usize>;
split_once(self, index: usize) -> (Self, Self)22     fn split_once(self, index: usize) -> (Self, Self);
fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F where F: Folder<Self>, Self: Send23     fn fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F
24         where F: Folder<Self>, Self: Send;
25 }
26 
27 impl<'p, P, V> SplitProducer<'p, P, V>
28     where V: Fissile<P> + Send
29 {
new(data: V, separator: &'p P) -> Self30     pub fn new(data: V, separator: &'p P) -> Self {
31         SplitProducer {
32             tail: data.length(),
33             data: data,
34             separator: separator,
35         }
36     }
37 
38     /// Common `fold_with` implementation, integrating `SplitTerminator`'s
39     /// need to sometimes skip its final empty item.
fold_with<F>(self, folder: F, skip_last: bool) -> F where F: Folder<V>40     pub fn fold_with<F>(self, folder: F, skip_last: bool) -> F
41         where F: Folder<V>
42     {
43         let SplitProducer { data, separator, tail } = self;
44 
45         if tail == data.length() {
46             // No tail section, so just let `fold_splits` handle it.
47             data.fold_splits(separator, folder, skip_last)
48 
49         } else if let Some(index) = data.rfind(separator, tail) {
50             // We found the last separator to complete the tail, so
51             // end with that slice after `fold_splits` finds the rest.
52             let (left, right) = data.split_once(index);
53             let folder = left.fold_splits(separator, folder, false);
54             if skip_last || folder.full() {
55                 folder
56             } else {
57                 folder.consume(right)
58             }
59 
60         } else {
61             // We know there are no separators at all.  Return our whole data.
62             if skip_last {
63                 folder
64             } else {
65                 folder.consume(data)
66             }
67         }
68     }
69 }
70 
71 impl<'p, P, V> UnindexedProducer for SplitProducer<'p, P, V>
72     where V: Fissile<P> + Send,
73           P: Sync,
74 {
75     type Item = V;
76 
split(self) -> (Self, Option<Self>)77     fn split(self) -> (Self, Option<Self>) {
78         // Look forward for the separator, and failing that look backward.
79         let mid = self.data.midpoint(self.tail);
80         let index = self.data.find(self.separator, mid, self.tail)
81             .map(|i| mid + i)
82             .or_else(|| self.data.rfind(self.separator, mid));
83 
84         if let Some(index) = index {
85             let len = self.data.length();
86             let (left, right) = self.data.split_once(index);
87 
88             let (left_tail, right_tail) = if index < mid {
89                 // If we scanned backwards to find the separator, everything in
90                 // the right side is exhausted, with no separators left to find.
91                 (index, 0)
92             } else {
93                 let right_index = len - right.length();
94                 (mid, self.tail - right_index)
95             };
96 
97             // Create the left split before the separator.
98             let left = SplitProducer {
99                 data: left,
100                 tail: left_tail,
101                 ..self
102             };
103 
104             // Create the right split following the separator.
105             let right = SplitProducer {
106                 data: right,
107                 tail: right_tail,
108                 ..self
109             };
110 
111             (left, Some(right))
112 
113         } else {
114             // The search is exhausted, no more separators...
115             (SplitProducer { tail: 0, ..self }, None)
116         }
117     }
118 
fold_with<F>(self, folder: F) -> F where F: Folder<Self::Item>119     fn fold_with<F>(self, folder: F) -> F
120         where F: Folder<Self::Item>
121     {
122         self.fold_with(folder, false)
123     }
124 }
125