vendor/rustc-rayon/src/split_producer.rs

   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 {
  18     fn length(&self) -> usize;
  19     fn midpoint(&self, end: usize) -> usize;
  20     fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize>;
  21     fn rfind(&self, separator: &P, end: usize) -> Option<usize>;
  22     fn split_once(self, index: usize) -> (Self, Self);
  23     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 {
  33     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.
  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
  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
 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 }