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::{Folder, UnindexedProducer}; 6 7 /// Common producer for splitting on a predicate. 8 pub(super) 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(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 = self 88 .data 89 .find(self.separator, mid, self.tail) 90 .map(|i| mid + i) 91 .or_else(|| self.data.rfind(self.separator, mid)); 92 93 if let Some(index) = index { 94 let len = self.data.length(); 95 let (left, right) = self.data.split_once(index); 96 97 let (left_tail, right_tail) = if index < mid { 98 // If we scanned backwards to find the separator, everything in 99 // the right side is exhausted, with no separators left to find. 100 (index, 0) 101 } else { 102 let right_index = len - right.length(); 103 (mid, self.tail - right_index) 104 }; 105 106 // Create the left split before the separator. 107 let left = SplitProducer { 108 data: left, 109 tail: left_tail, 110 ..self 111 }; 112 113 // Create the right split following the separator. 114 let right = SplitProducer { 115 data: right, 116 tail: right_tail, 117 ..self 118 }; 119 120 (left, Some(right)) 121 } else { 122 // The search is exhausted, no more separators... 123 (SplitProducer { tail: 0, ..self }, None) 124 } 125 } 126 fold_with<F>(self, folder: F) -> F where F: Folder<Self::Item>,127 fn fold_with<F>(self, folder: F) -> F 128 where 129 F: Folder<Self::Item>, 130 { 131 self.fold_with(folder, false) 132 } 133 } 134