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