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