1use super::{
2 FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, TrustedStep,
3};
4use crate::ascii::Char as AsciiChar;
5use crate::mem;
6use crate::net::{Ipv4Addr, Ipv6Addr};
7use crate::num::NonZero;
8use crate::ops::{self, Try};
9
10macro_rules! unsafe_impl_trusted_step {
12 ($($type:ty)*) => {$(
13 #[unstable(feature = "trusted_step", issue = "85731")]
14 unsafe impl TrustedStep for $type {}
15 )*};
16}
17unsafe_impl_trusted_step![AsciiChar char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize Ipv4Addr Ipv6Addr];
18
19#[rustc_diagnostic_item = "range_step"]
24#[unstable(feature = "step_trait", issue = "42168")]
25pub trait Step: Clone + PartialOrd + Sized {
26 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>);
41
42 fn forward_checked(start: Self, count: usize) -> Option<Self>;
59
60 fn forward(start: Self, count: usize) -> Self {
84 Step::forward_checked(start, count).expect("overflow in `Step::forward`")
85 }
86
87 unsafe fn forward_unchecked(start: Self, count: usize) -> Self {
109 Step::forward(start, count)
110 }
111
112 fn backward_checked(start: Self, count: usize) -> Option<Self>;
129
130 fn backward(start: Self, count: usize) -> Self {
154 Step::backward_checked(start, count).expect("overflow in `Step::backward`")
155 }
156
157 unsafe fn backward_unchecked(start: Self, count: usize) -> Self {
179 Step::backward(start, count)
180 }
181}
182
183macro_rules! step_signed_methods {
186 ($unsigned: ty) => {
187 #[inline]
188 unsafe fn forward_unchecked(start: Self, n: usize) -> Self {
189 unsafe { start.checked_add_unsigned(n as $unsigned).unwrap_unchecked() }
191 }
192
193 #[inline]
194 unsafe fn backward_unchecked(start: Self, n: usize) -> Self {
195 unsafe { start.checked_sub_unsigned(n as $unsigned).unwrap_unchecked() }
197 }
198 };
199}
200
201macro_rules! step_unsigned_methods {
202 () => {
203 #[inline]
204 unsafe fn forward_unchecked(start: Self, n: usize) -> Self {
205 unsafe { start.unchecked_add(n as Self) }
207 }
208
209 #[inline]
210 unsafe fn backward_unchecked(start: Self, n: usize) -> Self {
211 unsafe { start.unchecked_sub(n as Self) }
213 }
214 };
215}
216
217macro_rules! step_identical_methods {
219 () => {
220 #[inline]
221 #[allow(arithmetic_overflow)]
222 #[rustc_inherit_overflow_checks]
223 fn forward(start: Self, n: usize) -> Self {
224 if Self::forward_checked(start, n).is_none() {
227 let _ = Self::MAX + 1;
228 }
229 start.wrapping_add(n as Self)
231 }
232
233 #[inline]
234 #[allow(arithmetic_overflow)]
235 #[rustc_inherit_overflow_checks]
236 fn backward(start: Self, n: usize) -> Self {
237 if Self::backward_checked(start, n).is_none() {
240 let _ = Self::MIN - 1;
241 }
242 start.wrapping_sub(n as Self)
244 }
245 };
246}
247
248macro_rules! step_integer_impls {
249 {
250 narrower than or same width as usize:
251 $( [ $u_narrower:ident $i_narrower:ident ] ),+;
252 wider than usize:
253 $( [ $u_wider:ident $i_wider:ident ] ),+;
254 } => {
255 $(
256 #[allow(unreachable_patterns)]
257 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
258 impl Step for $u_narrower {
259 step_identical_methods!();
260 step_unsigned_methods!();
261
262 #[inline]
263 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
264 if *start <= *end {
265 let steps = (*end - *start) as usize;
267 (steps, Some(steps))
268 } else {
269 (0, None)
270 }
271 }
272
273 #[inline]
274 fn forward_checked(start: Self, n: usize) -> Option<Self> {
275 match Self::try_from(n) {
276 Ok(n) => start.checked_add(n),
277 Err(_) => None, }
279 }
280
281 #[inline]
282 fn backward_checked(start: Self, n: usize) -> Option<Self> {
283 match Self::try_from(n) {
284 Ok(n) => start.checked_sub(n),
285 Err(_) => None, }
287 }
288 }
289
290 #[allow(unreachable_patterns)]
291 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
292 impl Step for $i_narrower {
293 step_identical_methods!();
294 step_signed_methods!($u_narrower);
295
296 #[inline]
297 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
298 if *start <= *end {
299 let steps = (*end as isize).wrapping_sub(*start as isize) as usize;
305 (steps, Some(steps))
306 } else {
307 (0, None)
308 }
309 }
310
311 #[inline]
312 fn forward_checked(start: Self, n: usize) -> Option<Self> {
313 match $u_narrower::try_from(n) {
314 Ok(n) => {
315 let wrapped = start.wrapping_add(n as Self);
319 if wrapped >= start {
320 Some(wrapped)
321 } else {
322 None }
324 }
325 Err(_) => None,
329 }
330 }
331
332 #[inline]
333 fn backward_checked(start: Self, n: usize) -> Option<Self> {
334 match $u_narrower::try_from(n) {
335 Ok(n) => {
336 let wrapped = start.wrapping_sub(n as Self);
340 if wrapped <= start {
341 Some(wrapped)
342 } else {
343 None }
345 }
346 Err(_) => None,
350 }
351 }
352 }
353 )+
354
355 $(
356 #[allow(unreachable_patterns)]
357 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
358 impl Step for $u_wider {
359 step_identical_methods!();
360 step_unsigned_methods!();
361
362 #[inline]
363 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
364 if *start <= *end {
365 if let Ok(steps) = usize::try_from(*end - *start) {
366 (steps, Some(steps))
367 } else {
368 (usize::MAX, None)
369 }
370 } else {
371 (0, None)
372 }
373 }
374
375 #[inline]
376 fn forward_checked(start: Self, n: usize) -> Option<Self> {
377 start.checked_add(n as Self)
378 }
379
380 #[inline]
381 fn backward_checked(start: Self, n: usize) -> Option<Self> {
382 start.checked_sub(n as Self)
383 }
384 }
385
386 #[allow(unreachable_patterns)]
387 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
388 impl Step for $i_wider {
389 step_identical_methods!();
390 step_signed_methods!($u_wider);
391
392 #[inline]
393 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
394 if *start <= *end {
395 match end.checked_sub(*start) {
396 Some(result) => {
397 if let Ok(steps) = usize::try_from(result) {
398 (steps, Some(steps))
399 } else {
400 (usize::MAX, None)
401 }
402 }
403 None => (usize::MAX, None),
406 }
407 } else {
408 (0, None)
409 }
410 }
411
412 #[inline]
413 fn forward_checked(start: Self, n: usize) -> Option<Self> {
414 start.checked_add(n as Self)
415 }
416
417 #[inline]
418 fn backward_checked(start: Self, n: usize) -> Option<Self> {
419 start.checked_sub(n as Self)
420 }
421 }
422 )+
423 };
424}
425
426#[cfg(target_pointer_width = "64")]
427step_integer_impls! {
428 narrower than or same width as usize: [u8 i8], [u16 i16], [u32 i32], [u64 i64], [usize isize];
429 wider than usize: [u128 i128];
430}
431
432#[cfg(target_pointer_width = "32")]
433step_integer_impls! {
434 narrower than or same width as usize: [u8 i8], [u16 i16], [u32 i32], [usize isize];
435 wider than usize: [u64 i64], [u128 i128];
436}
437
438#[cfg(target_pointer_width = "16")]
439step_integer_impls! {
440 narrower than or same width as usize: [u8 i8], [u16 i16], [usize isize];
441 wider than usize: [u32 i32], [u64 i64], [u128 i128];
442}
443
444#[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
445impl Step for char {
446 #[inline]
447 fn steps_between(&start: &char, &end: &char) -> (usize, Option<usize>) {
448 let start = start as u32;
449 let end = end as u32;
450 if start <= end {
451 let count = end - start;
452 if start < 0xD800 && 0xE000 <= end {
453 if let Ok(steps) = usize::try_from(count - 0x800) {
454 (steps, Some(steps))
455 } else {
456 (usize::MAX, None)
457 }
458 } else {
459 if let Ok(steps) = usize::try_from(count) {
460 (steps, Some(steps))
461 } else {
462 (usize::MAX, None)
463 }
464 }
465 } else {
466 (0, None)
467 }
468 }
469
470 #[inline]
471 fn forward_checked(start: char, count: usize) -> Option<char> {
472 let start = start as u32;
473 let mut res = Step::forward_checked(start, count)?;
474 if start < 0xD800 && 0xD800 <= res {
475 res = Step::forward_checked(res, 0x800)?;
476 }
477 if res <= char::MAX as u32 {
478 Some(unsafe { char::from_u32_unchecked(res) })
481 } else {
482 None
483 }
484 }
485
486 #[inline]
487 fn backward_checked(start: char, count: usize) -> Option<char> {
488 let start = start as u32;
489 let mut res = Step::backward_checked(start, count)?;
490 if start >= 0xE000 && 0xE000 > res {
491 res = Step::backward_checked(res, 0x800)?;
492 }
493 Some(unsafe { char::from_u32_unchecked(res) })
496 }
497
498 #[inline]
499 unsafe fn forward_unchecked(start: char, count: usize) -> char {
500 let start = start as u32;
501 let mut res = unsafe { Step::forward_unchecked(start, count) };
504 if start < 0xD800 && 0xD800 <= res {
505 res = unsafe { Step::forward_unchecked(res, 0x800) };
508 }
509 unsafe { char::from_u32_unchecked(res) }
512 }
513
514 #[inline]
515 unsafe fn backward_unchecked(start: char, count: usize) -> char {
516 let start = start as u32;
517 let mut res = unsafe { Step::backward_unchecked(start, count) };
520 if start >= 0xE000 && 0xE000 > res {
521 res = unsafe { Step::backward_unchecked(res, 0x800) };
524 }
525 unsafe { char::from_u32_unchecked(res) }
528 }
529}
530
531#[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
532impl Step for AsciiChar {
533 #[inline]
534 fn steps_between(&start: &AsciiChar, &end: &AsciiChar) -> (usize, Option<usize>) {
535 Step::steps_between(&start.to_u8(), &end.to_u8())
536 }
537
538 #[inline]
539 fn forward_checked(start: AsciiChar, count: usize) -> Option<AsciiChar> {
540 let end = Step::forward_checked(start.to_u8(), count)?;
541 AsciiChar::from_u8(end)
542 }
543
544 #[inline]
545 fn backward_checked(start: AsciiChar, count: usize) -> Option<AsciiChar> {
546 let end = Step::backward_checked(start.to_u8(), count)?;
547
548 Some(unsafe { AsciiChar::from_u8_unchecked(end) })
550 }
551
552 #[inline]
553 unsafe fn forward_unchecked(start: AsciiChar, count: usize) -> AsciiChar {
554 let end = unsafe { Step::forward_unchecked(start.to_u8(), count) };
557
558 unsafe { AsciiChar::from_u8_unchecked(end) }
560 }
561
562 #[inline]
563 unsafe fn backward_unchecked(start: AsciiChar, count: usize) -> AsciiChar {
564 let end = unsafe { Step::backward_unchecked(start.to_u8(), count) };
567
568 unsafe { AsciiChar::from_u8_unchecked(end) }
570 }
571}
572
573#[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
574impl Step for Ipv4Addr {
575 #[inline]
576 fn steps_between(&start: &Ipv4Addr, &end: &Ipv4Addr) -> (usize, Option<usize>) {
577 u32::steps_between(&start.to_bits(), &end.to_bits())
578 }
579
580 #[inline]
581 fn forward_checked(start: Ipv4Addr, count: usize) -> Option<Ipv4Addr> {
582 u32::forward_checked(start.to_bits(), count).map(Ipv4Addr::from_bits)
583 }
584
585 #[inline]
586 fn backward_checked(start: Ipv4Addr, count: usize) -> Option<Ipv4Addr> {
587 u32::backward_checked(start.to_bits(), count).map(Ipv4Addr::from_bits)
588 }
589
590 #[inline]
591 unsafe fn forward_unchecked(start: Ipv4Addr, count: usize) -> Ipv4Addr {
592 Ipv4Addr::from_bits(unsafe { u32::forward_unchecked(start.to_bits(), count) })
595 }
596
597 #[inline]
598 unsafe fn backward_unchecked(start: Ipv4Addr, count: usize) -> Ipv4Addr {
599 Ipv4Addr::from_bits(unsafe { u32::backward_unchecked(start.to_bits(), count) })
602 }
603}
604
605#[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
606impl Step for Ipv6Addr {
607 #[inline]
608 fn steps_between(&start: &Ipv6Addr, &end: &Ipv6Addr) -> (usize, Option<usize>) {
609 u128::steps_between(&start.to_bits(), &end.to_bits())
610 }
611
612 #[inline]
613 fn forward_checked(start: Ipv6Addr, count: usize) -> Option<Ipv6Addr> {
614 u128::forward_checked(start.to_bits(), count).map(Ipv6Addr::from_bits)
615 }
616
617 #[inline]
618 fn backward_checked(start: Ipv6Addr, count: usize) -> Option<Ipv6Addr> {
619 u128::backward_checked(start.to_bits(), count).map(Ipv6Addr::from_bits)
620 }
621
622 #[inline]
623 unsafe fn forward_unchecked(start: Ipv6Addr, count: usize) -> Ipv6Addr {
624 Ipv6Addr::from_bits(unsafe { u128::forward_unchecked(start.to_bits(), count) })
627 }
628
629 #[inline]
630 unsafe fn backward_unchecked(start: Ipv6Addr, count: usize) -> Ipv6Addr {
631 Ipv6Addr::from_bits(unsafe { u128::backward_unchecked(start.to_bits(), count) })
634 }
635}
636
637macro_rules! range_exact_iter_impl {
638 ($($t:ty)*) => ($(
639 #[stable(feature = "rust1", since = "1.0.0")]
640 impl ExactSizeIterator for ops::Range<$t> { }
641 )*)
642}
643
644macro_rules! unsafe_range_trusted_random_access_impl {
647 ($($t:ty)*) => ($(
648 #[doc(hidden)]
649 #[unstable(feature = "trusted_random_access", issue = "none")]
650 unsafe impl TrustedRandomAccess for ops::Range<$t> {}
651
652 #[doc(hidden)]
653 #[unstable(feature = "trusted_random_access", issue = "none")]
654 unsafe impl TrustedRandomAccessNoCoerce for ops::Range<$t> {
655 const MAY_HAVE_SIDE_EFFECT: bool = false;
656 }
657 )*)
658}
659
660macro_rules! range_incl_exact_iter_impl {
661 ($($t:ty)*) => ($(
662 #[stable(feature = "inclusive_range", since = "1.26.0")]
663 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
664 )*)
665}
666
667trait RangeIteratorImpl {
669 type Item;
670
671 fn spec_next(&mut self) -> Option<Self::Item>;
673 fn spec_nth(&mut self, n: usize) -> Option<Self::Item>;
674 fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>>;
675
676 fn spec_next_back(&mut self) -> Option<Self::Item>;
678 fn spec_nth_back(&mut self, n: usize) -> Option<Self::Item>;
679 fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>>;
680}
681
682impl<A: Step> RangeIteratorImpl for ops::Range<A> {
683 type Item = A;
684
685 #[inline]
686 default fn spec_next(&mut self) -> Option<A> {
687 if self.start < self.end {
688 let n =
689 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
690 Some(mem::replace(&mut self.start, n))
691 } else {
692 None
693 }
694 }
695
696 #[inline]
697 default fn spec_nth(&mut self, n: usize) -> Option<A> {
698 if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
699 if plus_n < self.end {
700 self.start =
701 Step::forward_checked(plus_n.clone(), 1).expect("`Step` invariants not upheld");
702 return Some(plus_n);
703 }
704 }
705
706 self.start = self.end.clone();
707 None
708 }
709
710 #[inline]
711 default fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
712 let steps = Step::steps_between(&self.start, &self.end);
713 let available = steps.1.unwrap_or(steps.0);
714
715 let taken = available.min(n);
716
717 self.start =
718 Step::forward_checked(self.start.clone(), taken).expect("`Step` invariants not upheld");
719
720 NonZero::new(n - taken).map_or(Ok(()), Err)
721 }
722
723 #[inline]
724 default fn spec_next_back(&mut self) -> Option<A> {
725 if self.start < self.end {
726 self.end =
727 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
728 Some(self.end.clone())
729 } else {
730 None
731 }
732 }
733
734 #[inline]
735 default fn spec_nth_back(&mut self, n: usize) -> Option<A> {
736 if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
737 if minus_n > self.start {
738 self.end =
739 Step::backward_checked(minus_n, 1).expect("`Step` invariants not upheld");
740 return Some(self.end.clone());
741 }
742 }
743
744 self.end = self.start.clone();
745 None
746 }
747
748 #[inline]
749 default fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
750 let steps = Step::steps_between(&self.start, &self.end);
751 let available = steps.1.unwrap_or(steps.0);
752
753 let taken = available.min(n);
754
755 self.end =
756 Step::backward_checked(self.end.clone(), taken).expect("`Step` invariants not upheld");
757
758 NonZero::new(n - taken).map_or(Ok(()), Err)
759 }
760}
761
762impl<T: TrustedStep> RangeIteratorImpl for ops::Range<T> {
763 #[inline]
764 fn spec_next(&mut self) -> Option<T> {
765 if self.start < self.end {
766 let old = self.start;
767 self.start = unsafe { Step::forward_unchecked(old, 1) };
769 Some(old)
770 } else {
771 None
772 }
773 }
774
775 #[inline]
776 fn spec_nth(&mut self, n: usize) -> Option<T> {
777 if let Some(plus_n) = Step::forward_checked(self.start, n) {
778 if plus_n < self.end {
779 self.start = unsafe { Step::forward_unchecked(plus_n, 1) };
781 return Some(plus_n);
782 }
783 }
784
785 self.start = self.end;
786 None
787 }
788
789 #[inline]
790 fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
791 let steps = Step::steps_between(&self.start, &self.end);
792 let available = steps.1.unwrap_or(steps.0);
793
794 let taken = available.min(n);
795
796 self.start = unsafe { Step::forward_unchecked(self.start, taken) };
801
802 NonZero::new(n - taken).map_or(Ok(()), Err)
803 }
804
805 #[inline]
806 fn spec_next_back(&mut self) -> Option<T> {
807 if self.start < self.end {
808 self.end = unsafe { Step::backward_unchecked(self.end, 1) };
810 Some(self.end)
811 } else {
812 None
813 }
814 }
815
816 #[inline]
817 fn spec_nth_back(&mut self, n: usize) -> Option<T> {
818 if let Some(minus_n) = Step::backward_checked(self.end, n) {
819 if minus_n > self.start {
820 self.end = unsafe { Step::backward_unchecked(minus_n, 1) };
822 return Some(self.end);
823 }
824 }
825
826 self.end = self.start;
827 None
828 }
829
830 #[inline]
831 fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
832 let steps = Step::steps_between(&self.start, &self.end);
833 let available = steps.1.unwrap_or(steps.0);
834
835 let taken = available.min(n);
836
837 self.end = unsafe { Step::backward_unchecked(self.end, taken) };
839
840 NonZero::new(n - taken).map_or(Ok(()), Err)
841 }
842}
843
844#[stable(feature = "rust1", since = "1.0.0")]
845impl<A: Step> Iterator for ops::Range<A> {
846 type Item = A;
847
848 #[inline]
849 fn next(&mut self) -> Option<A> {
850 self.spec_next()
851 }
852
853 #[inline]
854 fn size_hint(&self) -> (usize, Option<usize>) {
855 if self.start < self.end {
856 Step::steps_between(&self.start, &self.end)
857 } else {
858 (0, Some(0))
859 }
860 }
861
862 #[inline]
863 fn count(self) -> usize {
864 if self.start < self.end {
865 Step::steps_between(&self.start, &self.end).1.expect("count overflowed usize")
866 } else {
867 0
868 }
869 }
870
871 #[inline]
872 fn nth(&mut self, n: usize) -> Option<A> {
873 self.spec_nth(n)
874 }
875
876 #[inline]
877 fn last(mut self) -> Option<A> {
878 self.next_back()
879 }
880
881 #[inline]
882 fn min(mut self) -> Option<A>
883 where
884 A: Ord,
885 {
886 self.next()
887 }
888
889 #[inline]
890 fn max(mut self) -> Option<A>
891 where
892 A: Ord,
893 {
894 self.next_back()
895 }
896
897 #[inline]
898 fn is_sorted(self) -> bool {
899 true
900 }
901
902 #[inline]
903 fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
904 self.spec_advance_by(n)
905 }
906
907 #[inline]
908 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
909 where
910 Self: TrustedRandomAccessNoCoerce,
911 {
912 unsafe { Step::forward_unchecked(self.start.clone(), idx) }
917 }
918}
919
920range_exact_iter_impl! {
929 usize u8 u16
930 isize i8 i16
931
932 u32
937 i32
938}
939
940unsafe_range_trusted_random_access_impl! {
941 usize u8 u16
942 isize i8 i16
943}
944
945#[cfg(target_pointer_width = "32")]
946unsafe_range_trusted_random_access_impl! {
947 u32 i32
948}
949
950#[cfg(target_pointer_width = "64")]
951unsafe_range_trusted_random_access_impl! {
952 u32 i32
953 u64 i64
954}
955
956range_incl_exact_iter_impl! {
957 u8
958 i8
959
960 u16
965 i16
966}
967
968#[stable(feature = "rust1", since = "1.0.0")]
969impl<A: Step> DoubleEndedIterator for ops::Range<A> {
970 #[inline]
971 fn next_back(&mut self) -> Option<A> {
972 self.spec_next_back()
973 }
974
975 #[inline]
976 fn nth_back(&mut self, n: usize) -> Option<A> {
977 self.spec_nth_back(n)
978 }
979
980 #[inline]
981 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
982 self.spec_advance_back_by(n)
983 }
984}
985
986#[unstable(feature = "trusted_len", issue = "37572")]
1006unsafe impl<A: TrustedStep> TrustedLen for ops::Range<A> {}
1007
1008#[stable(feature = "fused", since = "1.26.0")]
1009impl<A: Step> FusedIterator for ops::Range<A> {}
1010
1011#[stable(feature = "rust1", since = "1.0.0")]
1012impl<A: Step> Iterator for ops::RangeFrom<A> {
1013 type Item = A;
1014
1015 #[inline]
1016 fn next(&mut self) -> Option<A> {
1017 let n = Step::forward(self.start.clone(), 1);
1018 Some(mem::replace(&mut self.start, n))
1019 }
1020
1021 #[inline]
1022 fn size_hint(&self) -> (usize, Option<usize>) {
1023 (usize::MAX, None)
1024 }
1025
1026 #[inline]
1027 fn nth(&mut self, n: usize) -> Option<A> {
1028 let plus_n = Step::forward(self.start.clone(), n);
1029 self.start = Step::forward(plus_n.clone(), 1);
1030 Some(plus_n)
1031 }
1032}
1033
1034#[unstable(feature = "trusted_len", issue = "37572")]
1036unsafe impl<A: TrustedStep> TrustedLen for ops::RangeFrom<A> {}
1037
1038#[stable(feature = "fused", since = "1.26.0")]
1039impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
1040
1041trait RangeInclusiveIteratorImpl {
1042 type Item;
1043
1044 fn spec_next(&mut self) -> Option<Self::Item>;
1046 fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
1047 where
1048 Self: Sized,
1049 F: FnMut(B, Self::Item) -> R,
1050 R: Try<Output = B>;
1051
1052 fn spec_next_back(&mut self) -> Option<Self::Item>;
1054 fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
1055 where
1056 Self: Sized,
1057 F: FnMut(B, Self::Item) -> R,
1058 R: Try<Output = B>;
1059}
1060
1061impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> {
1062 type Item = A;
1063
1064 #[inline]
1065 default fn spec_next(&mut self) -> Option<A> {
1066 if self.is_empty() {
1067 return None;
1068 }
1069 let is_iterating = self.start < self.end;
1070 Some(if is_iterating {
1071 let n =
1072 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
1073 mem::replace(&mut self.start, n)
1074 } else {
1075 self.exhausted = true;
1076 self.start.clone()
1077 })
1078 }
1079
1080 #[inline]
1081 default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1082 where
1083 Self: Sized,
1084 F: FnMut(B, A) -> R,
1085 R: Try<Output = B>,
1086 {
1087 if self.is_empty() {
1088 return try { init };
1089 }
1090
1091 let mut accum = init;
1092
1093 while self.start < self.end {
1094 let n =
1095 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
1096 let n = mem::replace(&mut self.start, n);
1097 accum = f(accum, n)?;
1098 }
1099
1100 self.exhausted = true;
1101
1102 if self.start == self.end {
1103 accum = f(accum, self.start.clone())?;
1104 }
1105
1106 try { accum }
1107 }
1108
1109 #[inline]
1110 default fn spec_next_back(&mut self) -> Option<A> {
1111 if self.is_empty() {
1112 return None;
1113 }
1114 let is_iterating = self.start < self.end;
1115 Some(if is_iterating {
1116 let n =
1117 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
1118 mem::replace(&mut self.end, n)
1119 } else {
1120 self.exhausted = true;
1121 self.end.clone()
1122 })
1123 }
1124
1125 #[inline]
1126 default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1127 where
1128 Self: Sized,
1129 F: FnMut(B, A) -> R,
1130 R: Try<Output = B>,
1131 {
1132 if self.is_empty() {
1133 return try { init };
1134 }
1135
1136 let mut accum = init;
1137
1138 while self.start < self.end {
1139 let n =
1140 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
1141 let n = mem::replace(&mut self.end, n);
1142 accum = f(accum, n)?;
1143 }
1144
1145 self.exhausted = true;
1146
1147 if self.start == self.end {
1148 accum = f(accum, self.start.clone())?;
1149 }
1150
1151 try { accum }
1152 }
1153}
1154
1155impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> {
1156 #[inline]
1157 fn spec_next(&mut self) -> Option<T> {
1158 if self.is_empty() {
1159 return None;
1160 }
1161 let is_iterating = self.start < self.end;
1162 Some(if is_iterating {
1163 let n = unsafe { Step::forward_unchecked(self.start, 1) };
1165 mem::replace(&mut self.start, n)
1166 } else {
1167 self.exhausted = true;
1168 self.start
1169 })
1170 }
1171
1172 #[inline]
1173 fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1174 where
1175 Self: Sized,
1176 F: FnMut(B, T) -> R,
1177 R: Try<Output = B>,
1178 {
1179 if self.is_empty() {
1180 return try { init };
1181 }
1182
1183 let mut accum = init;
1184
1185 while self.start < self.end {
1186 let n = unsafe { Step::forward_unchecked(self.start, 1) };
1188 let n = mem::replace(&mut self.start, n);
1189 accum = f(accum, n)?;
1190 }
1191
1192 self.exhausted = true;
1193
1194 if self.start == self.end {
1195 accum = f(accum, self.start)?;
1196 }
1197
1198 try { accum }
1199 }
1200
1201 #[inline]
1202 fn spec_next_back(&mut self) -> Option<T> {
1203 if self.is_empty() {
1204 return None;
1205 }
1206 let is_iterating = self.start < self.end;
1207 Some(if is_iterating {
1208 let n = unsafe { Step::backward_unchecked(self.end, 1) };
1210 mem::replace(&mut self.end, n)
1211 } else {
1212 self.exhausted = true;
1213 self.end
1214 })
1215 }
1216
1217 #[inline]
1218 fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1219 where
1220 Self: Sized,
1221 F: FnMut(B, T) -> R,
1222 R: Try<Output = B>,
1223 {
1224 if self.is_empty() {
1225 return try { init };
1226 }
1227
1228 let mut accum = init;
1229
1230 while self.start < self.end {
1231 let n = unsafe { Step::backward_unchecked(self.end, 1) };
1233 let n = mem::replace(&mut self.end, n);
1234 accum = f(accum, n)?;
1235 }
1236
1237 self.exhausted = true;
1238
1239 if self.start == self.end {
1240 accum = f(accum, self.start)?;
1241 }
1242
1243 try { accum }
1244 }
1245}
1246
1247#[stable(feature = "inclusive_range", since = "1.26.0")]
1248impl<A: Step> Iterator for ops::RangeInclusive<A> {
1249 type Item = A;
1250
1251 #[inline]
1252 fn next(&mut self) -> Option<A> {
1253 self.spec_next()
1254 }
1255
1256 #[inline]
1257 fn size_hint(&self) -> (usize, Option<usize>) {
1258 if self.is_empty() {
1259 return (0, Some(0));
1260 }
1261
1262 let hint = Step::steps_between(&self.start, &self.end);
1263 (hint.0.saturating_add(1), hint.1.and_then(|steps| steps.checked_add(1)))
1264 }
1265
1266 #[inline]
1267 fn count(self) -> usize {
1268 if self.is_empty() {
1269 return 0;
1270 }
1271
1272 Step::steps_between(&self.start, &self.end)
1273 .1
1274 .and_then(|steps| steps.checked_add(1))
1275 .expect("count overflowed usize")
1276 }
1277
1278 #[inline]
1279 fn nth(&mut self, n: usize) -> Option<A> {
1280 if self.is_empty() {
1281 return None;
1282 }
1283
1284 if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
1285 use crate::cmp::Ordering::*;
1286
1287 match plus_n.partial_cmp(&self.end) {
1288 Some(Less) => {
1289 self.start = Step::forward(plus_n.clone(), 1);
1290 return Some(plus_n);
1291 }
1292 Some(Equal) => {
1293 self.start = plus_n.clone();
1294 self.exhausted = true;
1295 return Some(plus_n);
1296 }
1297 _ => {}
1298 }
1299 }
1300
1301 self.start = self.end.clone();
1302 self.exhausted = true;
1303 None
1304 }
1305
1306 #[inline]
1307 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
1308 where
1309 Self: Sized,
1310 F: FnMut(B, Self::Item) -> R,
1311 R: Try<Output = B>,
1312 {
1313 self.spec_try_fold(init, f)
1314 }
1315
1316 impl_fold_via_try_fold! { fold -> try_fold }
1317
1318 #[inline]
1319 fn last(mut self) -> Option<A> {
1320 self.next_back()
1321 }
1322
1323 #[inline]
1324 fn min(mut self) -> Option<A>
1325 where
1326 A: Ord,
1327 {
1328 self.next()
1329 }
1330
1331 #[inline]
1332 fn max(mut self) -> Option<A>
1333 where
1334 A: Ord,
1335 {
1336 self.next_back()
1337 }
1338
1339 #[inline]
1340 fn is_sorted(self) -> bool {
1341 true
1342 }
1343}
1344
1345#[stable(feature = "inclusive_range", since = "1.26.0")]
1346impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
1347 #[inline]
1348 fn next_back(&mut self) -> Option<A> {
1349 self.spec_next_back()
1350 }
1351
1352 #[inline]
1353 fn nth_back(&mut self, n: usize) -> Option<A> {
1354 if self.is_empty() {
1355 return None;
1356 }
1357
1358 if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
1359 use crate::cmp::Ordering::*;
1360
1361 match minus_n.partial_cmp(&self.start) {
1362 Some(Greater) => {
1363 self.end = Step::backward(minus_n.clone(), 1);
1364 return Some(minus_n);
1365 }
1366 Some(Equal) => {
1367 self.end = minus_n.clone();
1368 self.exhausted = true;
1369 return Some(minus_n);
1370 }
1371 _ => {}
1372 }
1373 }
1374
1375 self.end = self.start.clone();
1376 self.exhausted = true;
1377 None
1378 }
1379
1380 #[inline]
1381 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
1382 where
1383 Self: Sized,
1384 F: FnMut(B, Self::Item) -> R,
1385 R: Try<Output = B>,
1386 {
1387 self.spec_try_rfold(init, f)
1388 }
1389
1390 impl_fold_via_try_fold! { rfold -> try_rfold }
1391}
1392
1393#[unstable(feature = "trusted_len", issue = "37572")]
1395unsafe impl<A: TrustedStep> TrustedLen for ops::RangeInclusive<A> {}
1396
1397#[stable(feature = "fused", since = "1.26.0")]
1398impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}