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