1 use crate::intrinsics; 2 use crate::iter::adapters::zip::try_get_unchecked; 3 use crate::iter::{ 4 DoubleEndedIterator, ExactSizeIterator, FusedIterator, TrustedLen, TrustedRandomAccess, 5 TrustedRandomAccessNoCoerce, 6 }; 7 use crate::ops::Try; 8 9 /// An iterator that yields `None` forever after the underlying iterator 10 /// yields `None` once. 11 /// 12 /// This `struct` is created by [`Iterator::fuse`]. See its documentation 13 /// for more. 14 #[derive(Clone, Debug)] 15 #[must_use = "iterators are lazy and do nothing unless consumed"] 16 #[stable(feature = "rust1", since = "1.0.0")] 17 pub struct Fuse<I> { 18 // NOTE: for `I: FusedIterator`, we never bother setting `None`, but 19 // we still have to be prepared for that state due to variance. 20 // See rust-lang/rust#85863 21 iter: Option<I>, 22 } 23 impl<I> Fuse<I> { new(iter: I) -> Fuse<I>24 pub(in crate::iter) fn new(iter: I) -> Fuse<I> { 25 Fuse { iter: Some(iter) } 26 } 27 } 28 29 #[stable(feature = "fused", since = "1.26.0")] 30 impl<I> FusedIterator for Fuse<I> where I: Iterator {} 31 32 /// Fuse the iterator if the expression is `None`. 33 macro_rules! fuse { 34 ($self:ident . iter . $($call:tt)+) => { 35 match $self.iter { 36 Some(ref mut iter) => match iter.$($call)+ { 37 None => { 38 $self.iter = None; 39 None 40 } 41 item => item, 42 }, 43 None => None, 44 } 45 }; 46 } 47 48 /// Specialized macro that doesn't check if the expression is `None`. 49 /// (We trust that a `FusedIterator` will fuse itself.) 50 macro_rules! spec { 51 ($self:ident . iter . $($call:tt)+) => { 52 match $self.iter { 53 Some(ref mut iter) => iter.$($call)+, 54 None => None, 55 } 56 }; 57 } 58 59 // Any specialized implementation here is made internal 60 // to avoid exposing default fns outside this trait. 61 #[stable(feature = "rust1", since = "1.0.0")] 62 impl<I> Iterator for Fuse<I> 63 where 64 I: Iterator, 65 { 66 type Item = <I as Iterator>::Item; 67 68 #[inline] next(&mut self) -> Option<Self::Item>69 fn next(&mut self) -> Option<Self::Item> { 70 FuseImpl::next(self) 71 } 72 73 #[inline] nth(&mut self, n: usize) -> Option<I::Item>74 fn nth(&mut self, n: usize) -> Option<I::Item> { 75 FuseImpl::nth(self, n) 76 } 77 78 #[inline] last(self) -> Option<Self::Item>79 fn last(self) -> Option<Self::Item> { 80 match self.iter { 81 Some(iter) => iter.last(), 82 None => None, 83 } 84 } 85 86 #[inline] count(self) -> usize87 fn count(self) -> usize { 88 match self.iter { 89 Some(iter) => iter.count(), 90 None => 0, 91 } 92 } 93 94 #[inline] size_hint(&self) -> (usize, Option<usize>)95 fn size_hint(&self) -> (usize, Option<usize>) { 96 match self.iter { 97 Some(ref iter) => iter.size_hint(), 98 None => (0, Some(0)), 99 } 100 } 101 102 #[inline] try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>,103 fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R 104 where 105 Self: Sized, 106 Fold: FnMut(Acc, Self::Item) -> R, 107 R: Try<Output = Acc>, 108 { 109 FuseImpl::try_fold(self, acc, fold) 110 } 111 112 #[inline] fold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc,113 fn fold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc 114 where 115 Fold: FnMut(Acc, Self::Item) -> Acc, 116 { 117 if let Some(iter) = self.iter { 118 acc = iter.fold(acc, fold); 119 } 120 acc 121 } 122 123 #[inline] find<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool,124 fn find<P>(&mut self, predicate: P) -> Option<Self::Item> 125 where 126 P: FnMut(&Self::Item) -> bool, 127 { 128 FuseImpl::find(self, predicate) 129 } 130 131 #[inline] 132 #[doc(hidden)] __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item where Self: TrustedRandomAccessNoCoerce,133 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item 134 where 135 Self: TrustedRandomAccessNoCoerce, 136 { 137 match self.iter { 138 // SAFETY: the caller must uphold the contract for 139 // `Iterator::__iterator_get_unchecked`. 140 Some(ref mut iter) => unsafe { try_get_unchecked(iter, idx) }, 141 // SAFETY: the caller asserts there is an item at `i`, so we're not exhausted. 142 None => unsafe { intrinsics::unreachable() }, 143 } 144 } 145 } 146 147 #[stable(feature = "rust1", since = "1.0.0")] 148 impl<I> DoubleEndedIterator for Fuse<I> 149 where 150 I: DoubleEndedIterator, 151 { 152 #[inline] next_back(&mut self) -> Option<<I as Iterator>::Item>153 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { 154 FuseImpl::next_back(self) 155 } 156 157 #[inline] nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>158 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> { 159 FuseImpl::nth_back(self, n) 160 } 161 162 #[inline] try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>,163 fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R 164 where 165 Self: Sized, 166 Fold: FnMut(Acc, Self::Item) -> R, 167 R: Try<Output = Acc>, 168 { 169 FuseImpl::try_rfold(self, acc, fold) 170 } 171 172 #[inline] rfold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc,173 fn rfold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc 174 where 175 Fold: FnMut(Acc, Self::Item) -> Acc, 176 { 177 if let Some(iter) = self.iter { 178 acc = iter.rfold(acc, fold); 179 } 180 acc 181 } 182 183 #[inline] rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool,184 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> 185 where 186 P: FnMut(&Self::Item) -> bool, 187 { 188 FuseImpl::rfind(self, predicate) 189 } 190 } 191 192 #[stable(feature = "rust1", since = "1.0.0")] 193 impl<I> ExactSizeIterator for Fuse<I> 194 where 195 I: ExactSizeIterator, 196 { len(&self) -> usize197 fn len(&self) -> usize { 198 match self.iter { 199 Some(ref iter) => iter.len(), 200 None => 0, 201 } 202 } 203 is_empty(&self) -> bool204 fn is_empty(&self) -> bool { 205 match self.iter { 206 Some(ref iter) => iter.is_empty(), 207 None => true, 208 } 209 } 210 } 211 212 #[unstable(feature = "trusted_len", issue = "37572")] 213 // SAFETY: `TrustedLen` requires that an accurate length is reported via `size_hint()`. As `Fuse` 214 // is just forwarding this to the wrapped iterator `I` this property is preserved and it is safe to 215 // implement `TrustedLen` here. 216 unsafe impl<I> TrustedLen for Fuse<I> where I: TrustedLen {} 217 218 #[doc(hidden)] 219 #[unstable(feature = "trusted_random_access", issue = "none")] 220 // SAFETY: `TrustedRandomAccess` requires that `size_hint()` must be exact and cheap to call, and 221 // `Iterator::__iterator_get_unchecked()` must be implemented accordingly. 222 // 223 // This is safe to implement as `Fuse` is just forwarding these to the wrapped iterator `I`, which 224 // preserves these properties. 225 unsafe impl<I> TrustedRandomAccess for Fuse<I> where I: TrustedRandomAccess {} 226 227 #[doc(hidden)] 228 #[unstable(feature = "trusted_random_access", issue = "none")] 229 unsafe impl<I> TrustedRandomAccessNoCoerce for Fuse<I> 230 where 231 I: TrustedRandomAccessNoCoerce, 232 { 233 const MAY_HAVE_SIDE_EFFECT: bool = I::MAY_HAVE_SIDE_EFFECT; 234 } 235 236 /// Fuse specialization trait 237 /// 238 /// We only need to worry about `&mut self` methods, which 239 /// may exhaust the iterator without consuming it. 240 #[doc(hidden)] 241 trait FuseImpl<I> { 242 type Item; 243 244 // Functions specific to any normal Iterators next(&mut self) -> Option<Self::Item>245 fn next(&mut self) -> Option<Self::Item>; nth(&mut self, n: usize) -> Option<Self::Item>246 fn nth(&mut self, n: usize) -> Option<Self::Item>; try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>247 fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R 248 where 249 Self: Sized, 250 Fold: FnMut(Acc, Self::Item) -> R, 251 R: Try<Output = Acc>; find<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool252 fn find<P>(&mut self, predicate: P) -> Option<Self::Item> 253 where 254 P: FnMut(&Self::Item) -> bool; 255 256 // Functions specific to DoubleEndedIterators next_back(&mut self) -> Option<Self::Item> where I: DoubleEndedIterator257 fn next_back(&mut self) -> Option<Self::Item> 258 where 259 I: DoubleEndedIterator; nth_back(&mut self, n: usize) -> Option<Self::Item> where I: DoubleEndedIterator260 fn nth_back(&mut self, n: usize) -> Option<Self::Item> 261 where 262 I: DoubleEndedIterator; try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>, I: DoubleEndedIterator263 fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R 264 where 265 Self: Sized, 266 Fold: FnMut(Acc, Self::Item) -> R, 267 R: Try<Output = Acc>, 268 I: DoubleEndedIterator; rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool, I: DoubleEndedIterator269 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> 270 where 271 P: FnMut(&Self::Item) -> bool, 272 I: DoubleEndedIterator; 273 } 274 275 /// General `Fuse` impl which sets `iter = None` when exhausted. 276 #[doc(hidden)] 277 impl<I> FuseImpl<I> for Fuse<I> 278 where 279 I: Iterator, 280 { 281 type Item = <I as Iterator>::Item; 282 283 #[inline] next(&mut self) -> Option<<I as Iterator>::Item>284 default fn next(&mut self) -> Option<<I as Iterator>::Item> { 285 fuse!(self.iter.next()) 286 } 287 288 #[inline] nth(&mut self, n: usize) -> Option<I::Item>289 default fn nth(&mut self, n: usize) -> Option<I::Item> { 290 fuse!(self.iter.nth(n)) 291 } 292 293 #[inline] try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>,294 default fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R 295 where 296 Self: Sized, 297 Fold: FnMut(Acc, Self::Item) -> R, 298 R: Try<Output = Acc>, 299 { 300 if let Some(ref mut iter) = self.iter { 301 acc = iter.try_fold(acc, fold)?; 302 self.iter = None; 303 } 304 try { acc } 305 } 306 307 #[inline] find<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool,308 default fn find<P>(&mut self, predicate: P) -> Option<Self::Item> 309 where 310 P: FnMut(&Self::Item) -> bool, 311 { 312 fuse!(self.iter.find(predicate)) 313 } 314 315 #[inline] next_back(&mut self) -> Option<<I as Iterator>::Item> where I: DoubleEndedIterator,316 default fn next_back(&mut self) -> Option<<I as Iterator>::Item> 317 where 318 I: DoubleEndedIterator, 319 { 320 fuse!(self.iter.next_back()) 321 } 322 323 #[inline] nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> where I: DoubleEndedIterator,324 default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> 325 where 326 I: DoubleEndedIterator, 327 { 328 fuse!(self.iter.nth_back(n)) 329 } 330 331 #[inline] try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>, I: DoubleEndedIterator,332 default fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R 333 where 334 Self: Sized, 335 Fold: FnMut(Acc, Self::Item) -> R, 336 R: Try<Output = Acc>, 337 I: DoubleEndedIterator, 338 { 339 if let Some(ref mut iter) = self.iter { 340 acc = iter.try_rfold(acc, fold)?; 341 self.iter = None; 342 } 343 try { acc } 344 } 345 346 #[inline] rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool, I: DoubleEndedIterator,347 default fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> 348 where 349 P: FnMut(&Self::Item) -> bool, 350 I: DoubleEndedIterator, 351 { 352 fuse!(self.iter.rfind(predicate)) 353 } 354 } 355 356 /// Specialized `Fuse` impl which doesn't bother clearing `iter` when exhausted. 357 /// However, we must still be prepared for the possibility that it was already cleared! 358 #[doc(hidden)] 359 impl<I> FuseImpl<I> for Fuse<I> 360 where 361 I: FusedIterator, 362 { 363 #[inline] next(&mut self) -> Option<<I as Iterator>::Item>364 fn next(&mut self) -> Option<<I as Iterator>::Item> { 365 spec!(self.iter.next()) 366 } 367 368 #[inline] nth(&mut self, n: usize) -> Option<I::Item>369 fn nth(&mut self, n: usize) -> Option<I::Item> { 370 spec!(self.iter.nth(n)) 371 } 372 373 #[inline] try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>,374 fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R 375 where 376 Self: Sized, 377 Fold: FnMut(Acc, Self::Item) -> R, 378 R: Try<Output = Acc>, 379 { 380 if let Some(ref mut iter) = self.iter { 381 acc = iter.try_fold(acc, fold)?; 382 } 383 try { acc } 384 } 385 386 #[inline] find<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool,387 fn find<P>(&mut self, predicate: P) -> Option<Self::Item> 388 where 389 P: FnMut(&Self::Item) -> bool, 390 { 391 spec!(self.iter.find(predicate)) 392 } 393 394 #[inline] next_back(&mut self) -> Option<<I as Iterator>::Item> where I: DoubleEndedIterator,395 fn next_back(&mut self) -> Option<<I as Iterator>::Item> 396 where 397 I: DoubleEndedIterator, 398 { 399 spec!(self.iter.next_back()) 400 } 401 402 #[inline] nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> where I: DoubleEndedIterator,403 fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> 404 where 405 I: DoubleEndedIterator, 406 { 407 spec!(self.iter.nth_back(n)) 408 } 409 410 #[inline] try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>, I: DoubleEndedIterator,411 fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R 412 where 413 Self: Sized, 414 Fold: FnMut(Acc, Self::Item) -> R, 415 R: Try<Output = Acc>, 416 I: DoubleEndedIterator, 417 { 418 if let Some(ref mut iter) = self.iter { 419 acc = iter.try_rfold(acc, fold)?; 420 } 421 try { acc } 422 } 423 424 #[inline] rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool, I: DoubleEndedIterator,425 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> 426 where 427 P: FnMut(&Self::Item) -> bool, 428 I: DoubleEndedIterator, 429 { 430 spec!(self.iter.rfind(predicate)) 431 } 432 } 433