1 | use crate::cmp; |
2 | use crate::fmt::{self, Debug}; |
3 | use crate::iter::{FusedIterator, TrustedFused}; |
4 | use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator}; |
5 | use crate::num::NonZero; |
6 | |
7 | /// An iterator that iterates two other iterators simultaneously. |
8 | /// |
9 | /// This `struct` is created by [`zip`] or [`Iterator::zip`]. |
10 | /// See their documentation for more. |
11 | #[derive (Clone)] |
12 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
13 | #[stable (feature = "rust1" , since = "1.0.0" )] |
14 | pub struct Zip<A, B> { |
15 | a: A, |
16 | b: B, |
17 | // index, len and a_len are only used by the specialized version of zip |
18 | index: usize, |
19 | len: usize, |
20 | a_len: usize, |
21 | } |
22 | impl<A: Iterator, B: Iterator> Zip<A, B> { |
23 | pub(in crate::iter) fn new(a: A, b: B) -> Zip<A, B> { |
24 | ZipImpl::new(a, b) |
25 | } |
26 | fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> { |
27 | while let Some(x: (::Item, <…>::Item)) = Iterator::next(self) { |
28 | if n == 0 { |
29 | return Some(x); |
30 | } |
31 | n -= 1; |
32 | } |
33 | None |
34 | } |
35 | } |
36 | |
37 | /// Converts the arguments to iterators and zips them. |
38 | /// |
39 | /// See the documentation of [`Iterator::zip`] for more. |
40 | /// |
41 | /// # Examples |
42 | /// |
43 | /// ``` |
44 | /// use std::iter::zip; |
45 | /// |
46 | /// let xs = [1, 2, 3]; |
47 | /// let ys = [4, 5, 6]; |
48 | /// |
49 | /// let mut iter = zip(xs, ys); |
50 | /// |
51 | /// assert_eq!(iter.next().unwrap(), (1, 4)); |
52 | /// assert_eq!(iter.next().unwrap(), (2, 5)); |
53 | /// assert_eq!(iter.next().unwrap(), (3, 6)); |
54 | /// assert!(iter.next().is_none()); |
55 | /// |
56 | /// // Nested zips are also possible: |
57 | /// let zs = [7, 8, 9]; |
58 | /// |
59 | /// let mut iter = zip(zip(xs, ys), zs); |
60 | /// |
61 | /// assert_eq!(iter.next().unwrap(), ((1, 4), 7)); |
62 | /// assert_eq!(iter.next().unwrap(), ((2, 5), 8)); |
63 | /// assert_eq!(iter.next().unwrap(), ((3, 6), 9)); |
64 | /// assert!(iter.next().is_none()); |
65 | /// ``` |
66 | #[stable (feature = "iter_zip" , since = "1.59.0" )] |
67 | pub fn zip<A, B>(a: A, b: B) -> Zip<A::IntoIter, B::IntoIter> |
68 | where |
69 | A: IntoIterator, |
70 | B: IntoIterator, |
71 | { |
72 | ZipImpl::new(a:a.into_iter(), b:b.into_iter()) |
73 | } |
74 | |
75 | #[stable (feature = "rust1" , since = "1.0.0" )] |
76 | impl<A, B> Iterator for Zip<A, B> |
77 | where |
78 | A: Iterator, |
79 | B: Iterator, |
80 | { |
81 | type Item = (A::Item, B::Item); |
82 | |
83 | #[inline ] |
84 | fn next(&mut self) -> Option<Self::Item> { |
85 | ZipImpl::next(self) |
86 | } |
87 | |
88 | #[inline ] |
89 | fn size_hint(&self) -> (usize, Option<usize>) { |
90 | ZipImpl::size_hint(self) |
91 | } |
92 | |
93 | #[inline ] |
94 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
95 | ZipImpl::nth(self, n) |
96 | } |
97 | |
98 | #[inline ] |
99 | fn fold<Acc, F>(self, init: Acc, f: F) -> Acc |
100 | where |
101 | F: FnMut(Acc, Self::Item) -> Acc, |
102 | { |
103 | ZipImpl::fold(self, init, f) |
104 | } |
105 | |
106 | #[inline ] |
107 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item |
108 | where |
109 | Self: TrustedRandomAccessNoCoerce, |
110 | { |
111 | // SAFETY: `ZipImpl::__iterator_get_unchecked` has same safety |
112 | // requirements as `Iterator::__iterator_get_unchecked`. |
113 | unsafe { ZipImpl::get_unchecked(self, idx) } |
114 | } |
115 | } |
116 | |
117 | #[stable (feature = "rust1" , since = "1.0.0" )] |
118 | impl<A, B> DoubleEndedIterator for Zip<A, B> |
119 | where |
120 | A: DoubleEndedIterator + ExactSizeIterator, |
121 | B: DoubleEndedIterator + ExactSizeIterator, |
122 | { |
123 | #[inline ] |
124 | fn next_back(&mut self) -> Option<(A::Item, B::Item)> { |
125 | ZipImpl::next_back(self) |
126 | } |
127 | } |
128 | |
129 | // Zip specialization trait |
130 | #[doc (hidden)] |
131 | trait ZipImpl<A, B> { |
132 | type Item; |
133 | fn new(a: A, b: B) -> Self; |
134 | fn next(&mut self) -> Option<Self::Item>; |
135 | fn size_hint(&self) -> (usize, Option<usize>); |
136 | fn nth(&mut self, n: usize) -> Option<Self::Item>; |
137 | fn next_back(&mut self) -> Option<Self::Item> |
138 | where |
139 | A: DoubleEndedIterator + ExactSizeIterator, |
140 | B: DoubleEndedIterator + ExactSizeIterator; |
141 | fn fold<Acc, F>(self, init: Acc, f: F) -> Acc |
142 | where |
143 | F: FnMut(Acc, Self::Item) -> Acc; |
144 | // This has the same safety requirements as `Iterator::__iterator_get_unchecked` |
145 | unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item |
146 | where |
147 | Self: Iterator + TrustedRandomAccessNoCoerce; |
148 | } |
149 | |
150 | // Work around limitations of specialization, requiring `default` impls to be repeated |
151 | // in intermediary impls. |
152 | macro_rules! zip_impl_general_defaults { |
153 | () => { |
154 | default fn new(a: A, b: B) -> Self { |
155 | Zip { |
156 | a, |
157 | b, |
158 | index: 0, // unused |
159 | len: 0, // unused |
160 | a_len: 0, // unused |
161 | } |
162 | } |
163 | |
164 | #[inline] |
165 | default fn next(&mut self) -> Option<(A::Item, B::Item)> { |
166 | let x = self.a.next()?; |
167 | let y = self.b.next()?; |
168 | Some((x, y)) |
169 | } |
170 | |
171 | #[inline] |
172 | default fn nth(&mut self, n: usize) -> Option<Self::Item> { |
173 | self.super_nth(n) |
174 | } |
175 | |
176 | #[inline] |
177 | default fn next_back(&mut self) -> Option<(A::Item, B::Item)> |
178 | where |
179 | A: DoubleEndedIterator + ExactSizeIterator, |
180 | B: DoubleEndedIterator + ExactSizeIterator, |
181 | { |
182 | // The function body below only uses `self.a/b.len()` and `self.a/b.next_back()` |
183 | // and doesn’t call `next_back` too often, so this implementation is safe in |
184 | // the `TrustedRandomAccessNoCoerce` specialization |
185 | |
186 | let a_sz = self.a.len(); |
187 | let b_sz = self.b.len(); |
188 | if a_sz != b_sz { |
189 | // Adjust a, b to equal length |
190 | if a_sz > b_sz { |
191 | for _ in 0..a_sz - b_sz { |
192 | self.a.next_back(); |
193 | } |
194 | } else { |
195 | for _ in 0..b_sz - a_sz { |
196 | self.b.next_back(); |
197 | } |
198 | } |
199 | } |
200 | match (self.a.next_back(), self.b.next_back()) { |
201 | (Some(x), Some(y)) => Some((x, y)), |
202 | (None, None) => None, |
203 | _ => unreachable!(), |
204 | } |
205 | } |
206 | }; |
207 | } |
208 | |
209 | // General Zip impl |
210 | #[doc (hidden)] |
211 | impl<A, B> ZipImpl<A, B> for Zip<A, B> |
212 | where |
213 | A: Iterator, |
214 | B: Iterator, |
215 | { |
216 | type Item = (A::Item, B::Item); |
217 | |
218 | zip_impl_general_defaults! {} |
219 | |
220 | #[inline ] |
221 | default fn size_hint(&self) -> (usize, Option<usize>) { |
222 | let (a_lower, a_upper) = self.a.size_hint(); |
223 | let (b_lower, b_upper) = self.b.size_hint(); |
224 | |
225 | let lower = cmp::min(a_lower, b_lower); |
226 | |
227 | let upper = match (a_upper, b_upper) { |
228 | (Some(x), Some(y)) => Some(cmp::min(x, y)), |
229 | (Some(x), None) => Some(x), |
230 | (None, Some(y)) => Some(y), |
231 | (None, None) => None, |
232 | }; |
233 | |
234 | (lower, upper) |
235 | } |
236 | |
237 | default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item |
238 | where |
239 | Self: TrustedRandomAccessNoCoerce, |
240 | { |
241 | unreachable!("Always specialized" ); |
242 | } |
243 | |
244 | #[inline ] |
245 | default fn fold<Acc, F>(self, init: Acc, f: F) -> Acc |
246 | where |
247 | F: FnMut(Acc, Self::Item) -> Acc, |
248 | { |
249 | SpecFold::spec_fold(self, init, f) |
250 | } |
251 | } |
252 | |
253 | #[doc (hidden)] |
254 | impl<A, B> ZipImpl<A, B> for Zip<A, B> |
255 | where |
256 | A: TrustedRandomAccessNoCoerce + Iterator, |
257 | B: TrustedRandomAccessNoCoerce + Iterator, |
258 | { |
259 | zip_impl_general_defaults! {} |
260 | |
261 | #[inline ] |
262 | default fn size_hint(&self) -> (usize, Option<usize>) { |
263 | let size = cmp::min(self.a.size(), self.b.size()); |
264 | (size, Some(size)) |
265 | } |
266 | |
267 | #[inline ] |
268 | unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item { |
269 | let idx = self.index + idx; |
270 | // SAFETY: the caller must uphold the contract for |
271 | // `Iterator::__iterator_get_unchecked`. |
272 | unsafe { (self.a.__iterator_get_unchecked(idx), self.b.__iterator_get_unchecked(idx)) } |
273 | } |
274 | |
275 | #[inline ] |
276 | fn fold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc |
277 | where |
278 | F: FnMut(Acc, Self::Item) -> Acc, |
279 | { |
280 | let mut accum = init; |
281 | let len = ZipImpl::size_hint(&self).0; |
282 | for i in 0..len { |
283 | // SAFETY: since Self: TrustedRandomAccessNoCoerce we can trust the size-hint to |
284 | // calculate the length and then use that to do unchecked iteration. |
285 | // fold consumes the iterator so we don't need to fixup any state. |
286 | unsafe { |
287 | accum = f(accum, self.get_unchecked(i)); |
288 | } |
289 | } |
290 | accum |
291 | } |
292 | } |
293 | |
294 | #[doc (hidden)] |
295 | impl<A, B> ZipImpl<A, B> for Zip<A, B> |
296 | where |
297 | A: TrustedRandomAccess + Iterator, |
298 | B: TrustedRandomAccess + Iterator, |
299 | { |
300 | fn new(a: A, b: B) -> Self { |
301 | let a_len = a.size(); |
302 | let len = cmp::min(a_len, b.size()); |
303 | Zip { a, b, index: 0, len, a_len } |
304 | } |
305 | |
306 | #[inline ] |
307 | fn next(&mut self) -> Option<(A::Item, B::Item)> { |
308 | if self.index < self.len { |
309 | let i = self.index; |
310 | // since get_unchecked executes code which can panic we increment the counters beforehand |
311 | // so that the same index won't be accessed twice, as required by TrustedRandomAccess |
312 | self.index += 1; |
313 | // SAFETY: `i` is smaller than `self.len`, thus smaller than `self.a.len()` and `self.b.len()` |
314 | unsafe { |
315 | Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i))) |
316 | } |
317 | } else if A::MAY_HAVE_SIDE_EFFECT && self.index < self.a_len { |
318 | let i = self.index; |
319 | // as above, increment before executing code that may panic |
320 | self.index += 1; |
321 | self.len += 1; |
322 | // match the base implementation's potential side effects |
323 | // SAFETY: we just checked that `i` < `self.a.len()` |
324 | unsafe { |
325 | self.a.__iterator_get_unchecked(i); |
326 | } |
327 | None |
328 | } else { |
329 | None |
330 | } |
331 | } |
332 | |
333 | #[inline ] |
334 | fn size_hint(&self) -> (usize, Option<usize>) { |
335 | let len = self.len - self.index; |
336 | (len, Some(len)) |
337 | } |
338 | |
339 | #[inline ] |
340 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
341 | let delta = cmp::min(n, self.len - self.index); |
342 | let end = self.index + delta; |
343 | while self.index < end { |
344 | let i = self.index; |
345 | // since get_unchecked executes code which can panic we increment the counters beforehand |
346 | // so that the same index won't be accessed twice, as required by TrustedRandomAccess |
347 | self.index += 1; |
348 | if A::MAY_HAVE_SIDE_EFFECT { |
349 | // SAFETY: the usage of `cmp::min` to calculate `delta` |
350 | // ensures that `end` is smaller than or equal to `self.len`, |
351 | // so `i` is also smaller than `self.len`. |
352 | unsafe { |
353 | self.a.__iterator_get_unchecked(i); |
354 | } |
355 | } |
356 | if B::MAY_HAVE_SIDE_EFFECT { |
357 | // SAFETY: same as above. |
358 | unsafe { |
359 | self.b.__iterator_get_unchecked(i); |
360 | } |
361 | } |
362 | } |
363 | |
364 | self.super_nth(n - delta) |
365 | } |
366 | |
367 | #[inline ] |
368 | fn next_back(&mut self) -> Option<(A::Item, B::Item)> |
369 | where |
370 | A: DoubleEndedIterator + ExactSizeIterator, |
371 | B: DoubleEndedIterator + ExactSizeIterator, |
372 | { |
373 | if A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT { |
374 | let sz_a = self.a.size(); |
375 | let sz_b = self.b.size(); |
376 | // Adjust a, b to equal length, make sure that only the first call |
377 | // of `next_back` does this, otherwise we will break the restriction |
378 | // on calls to `self.next_back()` after calling `get_unchecked()`. |
379 | if sz_a != sz_b { |
380 | let sz_a = self.a.size(); |
381 | if A::MAY_HAVE_SIDE_EFFECT && sz_a > self.len { |
382 | for _ in 0..sz_a - self.len { |
383 | // since next_back() may panic we increment the counters beforehand |
384 | // to keep Zip's state in sync with the underlying iterator source |
385 | self.a_len -= 1; |
386 | self.a.next_back(); |
387 | } |
388 | debug_assert_eq!(self.a_len, self.len); |
389 | } |
390 | let sz_b = self.b.size(); |
391 | if B::MAY_HAVE_SIDE_EFFECT && sz_b > self.len { |
392 | for _ in 0..sz_b - self.len { |
393 | self.b.next_back(); |
394 | } |
395 | } |
396 | } |
397 | } |
398 | if self.index < self.len { |
399 | // since get_unchecked executes code which can panic we increment the counters beforehand |
400 | // so that the same index won't be accessed twice, as required by TrustedRandomAccess |
401 | self.len -= 1; |
402 | self.a_len -= 1; |
403 | let i = self.len; |
404 | // SAFETY: `i` is smaller than the previous value of `self.len`, |
405 | // which is also smaller than or equal to `self.a.len()` and `self.b.len()` |
406 | unsafe { |
407 | Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i))) |
408 | } |
409 | } else { |
410 | None |
411 | } |
412 | } |
413 | } |
414 | |
415 | #[stable (feature = "rust1" , since = "1.0.0" )] |
416 | impl<A, B> ExactSizeIterator for Zip<A, B> |
417 | where |
418 | A: ExactSizeIterator, |
419 | B: ExactSizeIterator, |
420 | { |
421 | } |
422 | |
423 | #[doc (hidden)] |
424 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
425 | unsafe impl<A, B> TrustedRandomAccess for Zip<A, B> |
426 | where |
427 | A: TrustedRandomAccess, |
428 | B: TrustedRandomAccess, |
429 | { |
430 | } |
431 | |
432 | #[doc (hidden)] |
433 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
434 | unsafe impl<A, B> TrustedRandomAccessNoCoerce for Zip<A, B> |
435 | where |
436 | A: TrustedRandomAccessNoCoerce, |
437 | B: TrustedRandomAccessNoCoerce, |
438 | { |
439 | const MAY_HAVE_SIDE_EFFECT: bool = A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT; |
440 | } |
441 | |
442 | #[stable (feature = "fused" , since = "1.26.0" )] |
443 | impl<A, B> FusedIterator for Zip<A, B> |
444 | where |
445 | A: FusedIterator, |
446 | B: FusedIterator, |
447 | { |
448 | } |
449 | |
450 | #[unstable (issue = "none" , feature = "trusted_fused" )] |
451 | unsafe impl<A, B> TrustedFused for Zip<A, B> |
452 | where |
453 | A: TrustedFused, |
454 | B: TrustedFused, |
455 | { |
456 | } |
457 | |
458 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
459 | unsafe impl<A, B> TrustedLen for Zip<A, B> |
460 | where |
461 | A: TrustedLen, |
462 | B: TrustedLen, |
463 | { |
464 | } |
465 | |
466 | impl<A, B> UncheckedIterator for Zip<A, B> |
467 | where |
468 | A: UncheckedIterator, |
469 | B: UncheckedIterator, |
470 | { |
471 | } |
472 | |
473 | // Arbitrarily selects the left side of the zip iteration as extractable "source" |
474 | // it would require negative trait bounds to be able to try both |
475 | #[unstable (issue = "none" , feature = "inplace_iteration" )] |
476 | unsafe impl<A, B> SourceIter for Zip<A, B> |
477 | where |
478 | A: SourceIter, |
479 | { |
480 | type Source = A::Source; |
481 | |
482 | #[inline ] |
483 | unsafe fn as_inner(&mut self) -> &mut A::Source { |
484 | // SAFETY: unsafe function forwarding to unsafe function with the same requirements |
485 | unsafe { SourceIter::as_inner(&mut self.a) } |
486 | } |
487 | } |
488 | |
489 | // Since SourceIter forwards the left hand side we do the same here |
490 | #[unstable (issue = "none" , feature = "inplace_iteration" )] |
491 | unsafe impl<A: InPlaceIterable, B> InPlaceIterable for Zip<A, B> { |
492 | const EXPAND_BY: Option<NonZero<usize>> = A::EXPAND_BY; |
493 | const MERGE_BY: Option<NonZero<usize>> = A::MERGE_BY; |
494 | } |
495 | |
496 | #[stable (feature = "rust1" , since = "1.0.0" )] |
497 | impl<A: Debug, B: Debug> Debug for Zip<A, B> { |
498 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
499 | ZipFmt::fmt(self, f) |
500 | } |
501 | } |
502 | |
503 | trait ZipFmt<A, B> { |
504 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result; |
505 | } |
506 | |
507 | impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> { |
508 | default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
509 | f.debug_struct("Zip" ).field("a" , &self.a).field(name:"b" , &self.b).finish() |
510 | } |
511 | } |
512 | |
513 | impl<A: Debug + TrustedRandomAccessNoCoerce, B: Debug + TrustedRandomAccessNoCoerce> ZipFmt<A, B> |
514 | for Zip<A, B> |
515 | { |
516 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
517 | // It's *not safe* to call fmt on the contained iterators, since once |
518 | // we start iterating they're in strange, potentially unsafe, states. |
519 | f.debug_struct(name:"Zip" ).finish() |
520 | } |
521 | } |
522 | |
523 | /// An iterator whose items are random-accessible efficiently |
524 | /// |
525 | /// # Safety |
526 | /// |
527 | /// The iterator's `size_hint` must be exact and cheap to call. |
528 | /// |
529 | /// `TrustedRandomAccessNoCoerce::size` may not be overridden. |
530 | /// |
531 | /// All subtypes and all supertypes of `Self` must also implement `TrustedRandomAccess`. |
532 | /// In particular, this means that types with non-invariant parameters usually can not have |
533 | /// an impl for `TrustedRandomAccess` that depends on any trait bounds on such parameters, except |
534 | /// for bounds that come from the respective struct/enum definition itself, or bounds involving |
535 | /// traits that themselves come with a guarantee similar to this one. |
536 | /// |
537 | /// If `Self: ExactSizeIterator` then `self.len()` must always produce results consistent |
538 | /// with `self.size()`. |
539 | /// |
540 | /// If `Self: Iterator`, then `<Self as Iterator>::__iterator_get_unchecked(&mut self, idx)` |
541 | /// must be safe to call provided the following conditions are met. |
542 | /// |
543 | /// 1. `0 <= idx` and `idx < self.size()`. |
544 | /// 2. If `Self: !Clone`, then `self.__iterator_get_unchecked(idx)` is never called with the same |
545 | /// index on `self` more than once. |
546 | /// 3. After `self.__iterator_get_unchecked(idx)` has been called, then `self.next_back()` will |
547 | /// only be called at most `self.size() - idx - 1` times. If `Self: Clone` and `self` is cloned, |
548 | /// then this number is calculated for `self` and its clone individually, |
549 | /// but `self.next_back()` calls that happened before the cloning count for both `self` and the clone. |
550 | /// 4. After `self.__iterator_get_unchecked(idx)` has been called, then only the following methods |
551 | /// will be called on `self` or on any new clones of `self`: |
552 | /// * `std::clone::Clone::clone` |
553 | /// * `std::iter::Iterator::size_hint` |
554 | /// * `std::iter::DoubleEndedIterator::next_back` |
555 | /// * `std::iter::ExactSizeIterator::len` |
556 | /// * `std::iter::Iterator::__iterator_get_unchecked` |
557 | /// * `std::iter::TrustedRandomAccessNoCoerce::size` |
558 | /// 5. If `T` is a subtype of `Self`, then `self` is allowed to be coerced |
559 | /// to `T`. If `self` is coerced to `T` after `self.__iterator_get_unchecked(idx)` has already |
560 | /// been called, then no methods except for the ones listed under 4. are allowed to be called |
561 | /// on the resulting value of type `T`, either. Multiple such coercion steps are allowed. |
562 | /// Regarding 2. and 3., the number of times `__iterator_get_unchecked(idx)` or `next_back()` is |
563 | /// called on `self` and the resulting value of type `T` (and on further coercion results with |
564 | /// sub-subtypes) are added together and their sums must not exceed the specified bounds. |
565 | /// |
566 | /// Further, given that these conditions are met, it must guarantee that: |
567 | /// |
568 | /// * It does not change the value returned from `size_hint` |
569 | /// * It must be safe to call the methods listed above on `self` after calling |
570 | /// `self.__iterator_get_unchecked(idx)`, assuming that the required traits are implemented. |
571 | /// * It must also be safe to drop `self` after calling `self.__iterator_get_unchecked(idx)`. |
572 | /// * If `T` is a subtype of `Self`, then it must be safe to coerce `self` to `T`. |
573 | // |
574 | // FIXME: Clarify interaction with SourceIter/InPlaceIterable. Calling `SourceIter::as_inner` |
575 | // after `__iterator_get_unchecked` is supposed to be allowed. |
576 | #[doc (hidden)] |
577 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
578 | #[rustc_specialization_trait ] |
579 | pub unsafe trait TrustedRandomAccess: TrustedRandomAccessNoCoerce {} |
580 | |
581 | /// Like [`TrustedRandomAccess`] but without any of the requirements / guarantees around |
582 | /// coercions to subtypes after `__iterator_get_unchecked` (they aren’t allowed here!), and |
583 | /// without the requirement that subtypes / supertypes implement `TrustedRandomAccessNoCoerce`. |
584 | /// |
585 | /// This trait was created in PR #85874 to fix soundness issue #85873 without performance regressions. |
586 | /// It is subject to change as we might want to build a more generally useful (for performance |
587 | /// optimizations) and more sophisticated trait or trait hierarchy that replaces or extends |
588 | /// [`TrustedRandomAccess`] and `TrustedRandomAccessNoCoerce`. |
589 | #[doc (hidden)] |
590 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
591 | #[rustc_specialization_trait ] |
592 | pub unsafe trait TrustedRandomAccessNoCoerce: Sized { |
593 | // Convenience method. |
594 | fn size(&self) -> usize |
595 | where |
596 | Self: Iterator, |
597 | { |
598 | self.size_hint().0 |
599 | } |
600 | /// `true` if getting an iterator element may have side effects. |
601 | /// Remember to take inner iterators into account. |
602 | const MAY_HAVE_SIDE_EFFECT: bool; |
603 | } |
604 | |
605 | /// Like `Iterator::__iterator_get_unchecked`, but doesn't require the compiler to |
606 | /// know that `U: TrustedRandomAccess`. |
607 | /// |
608 | /// ## Safety |
609 | /// |
610 | /// Same requirements calling `get_unchecked` directly. |
611 | #[doc (hidden)] |
612 | #[inline ] |
613 | pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item |
614 | where |
615 | I: Iterator, |
616 | { |
617 | // SAFETY: the caller must uphold the contract for |
618 | // `Iterator::__iterator_get_unchecked`. |
619 | unsafe { it.try_get_unchecked(index:idx) } |
620 | } |
621 | |
622 | unsafe trait SpecTrustedRandomAccess: Iterator { |
623 | /// If `Self: TrustedRandomAccess`, it must be safe to call |
624 | /// `Iterator::__iterator_get_unchecked(self, index)`. |
625 | unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item; |
626 | } |
627 | |
628 | unsafe impl<I: Iterator> SpecTrustedRandomAccess for I { |
629 | default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item { |
630 | panic!("Should only be called on TrustedRandomAccess iterators" ); |
631 | } |
632 | } |
633 | |
634 | unsafe impl<I: Iterator + TrustedRandomAccessNoCoerce> SpecTrustedRandomAccess for I { |
635 | #[inline ] |
636 | unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item { |
637 | // SAFETY: the caller must uphold the contract for |
638 | // `Iterator::__iterator_get_unchecked`. |
639 | unsafe { self.__iterator_get_unchecked(_idx:index) } |
640 | } |
641 | } |
642 | |
643 | trait SpecFold: Iterator { |
644 | fn spec_fold<B, F>(self, init: B, f: F) -> B |
645 | where |
646 | Self: Sized, |
647 | F: FnMut(B, Self::Item) -> B; |
648 | } |
649 | |
650 | impl<A: Iterator, B: Iterator> SpecFold for Zip<A, B> { |
651 | // Adapted from default impl from the Iterator trait |
652 | #[inline ] |
653 | default fn spec_fold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc |
654 | where |
655 | F: FnMut(Acc, Self::Item) -> Acc, |
656 | { |
657 | let mut accum: Acc = init; |
658 | while let Some(x: (::Item, <…>::Item)) = ZipImpl::next(&mut self) { |
659 | accum = f(accum, x); |
660 | } |
661 | accum |
662 | } |
663 | } |
664 | |
665 | impl<A: TrustedLen, B: TrustedLen> SpecFold for Zip<A, B> { |
666 | #[inline ] |
667 | fn spec_fold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc |
668 | where |
669 | F: FnMut(Acc, Self::Item) -> Acc, |
670 | { |
671 | let mut accum = init; |
672 | loop { |
673 | let (upper, more) = if let Some(upper) = ZipImpl::size_hint(&self).1 { |
674 | (upper, false) |
675 | } else { |
676 | // Per TrustedLen contract a None upper bound means more than usize::MAX items |
677 | (usize::MAX, true) |
678 | }; |
679 | |
680 | for _ in 0..upper { |
681 | let pair = |
682 | // SAFETY: TrustedLen guarantees that at least `upper` many items are available |
683 | // therefore we know they can't be None |
684 | unsafe { (self.a.next().unwrap_unchecked(), self.b.next().unwrap_unchecked()) }; |
685 | accum = f(accum, pair); |
686 | } |
687 | |
688 | if !more { |
689 | break; |
690 | } |
691 | } |
692 | accum |
693 | } |
694 | } |
695 | |