about summary refs log tree commit diff
path: root/src/libcore/tests/iter.rs
AgeCommit message (Collapse)AuthorLines
2020-07-27mv std libs to library/mark-3127/+0
2020-05-31Miri tests: skip parts of test_char_rangeRalf Jung-2/+5
2020-05-29Auto merge of #72756 - RalfJung:rollup-tbjmtx2, r=RalfJungbors-0/+12
Rollup of 9 pull requests Successful merges: - #67460 (Tweak impl signature mismatch errors involving `RegionKind::ReVar` lifetimes) - #71095 (impl From<[T; N]> for Box<[T]>) - #71500 (Make pointer offset methods/intrinsics const) - #71804 (linker: Support `-static-pie` and `-static -shared`) - #71862 (Implement RFC 2585: unsafe blocks in unsafe fn) - #72103 (borrowck `DefId` -> `LocalDefId`) - #72407 (Various minor improvements to Ipv6Addr::Display) - #72413 (impl Step for char (make Range*<char> iterable)) - #72439 (NVPTX support for new asm!) Failed merges: r? @ghost
2020-05-28FIx off-by-one in char::steps_betweenCAD97-0/+2
2020-05-26Add Peekable::next_ifJoshua Nelson-0/+24
Prior art: `rust_analyzer` uses [`Parser::eat`](https://github.com/rust-analyzer/rust-analyzer/blob/50f4ae798b7c54d417ee88455b87fd0477473150/crates/ra_parser/src/parser.rs#L94), which is `next_if` specialized to `|y| next_if(|x| x == y)`. Basically every other parser I've run into in Rust has an equivalent of Parser::eat; see for example - [cranelift](https://github.com/bytecodealliance/wasmtime/blob/94190d57244b26baf36629c88104b0ba516510cf/cranelift/reader/src/parser.rs#L498) - [rcc](https://github.com/jyn514/rcc/blob/a8159c3904a0c950fbba817bf9109023fad69033/src/parse/mod.rs#L231) - [crunch](https://github.com/Kixiron/crunch-lang/blob/8521874fab8a7d62bfa7dea8bd1da94b63e31be8/crates/crunch-parser/src/parser/mod.rs#L213-L241)
2020-05-21Add a test for char rangesCAD97-0/+10
2020-05-15Auto merge of #69659 - CAD97:step-rework-take-3, r=Amanieubors-27/+94
Rework the std::iter::Step trait Previous attempts: #43127 #62886 #68807 Tracking issue: #42168 This PR reworks the `Step` trait to be phrased in terms of the *successor* and *predecessor* operations. With this, `Step` hopefully has a consistent identity that can have a path towards stabilization. The proposed trait: ```rust /// Objects that have a notion of *successor* and *predecessor* operations. /// /// The *successor* operation moves towards values that compare greater. /// The *predecessor* operation moves towards values that compare lesser. /// /// # Safety /// /// This trait is `unsafe` because its implementation must be correct for /// the safety of `unsafe trait TrustedLen` implementations, and the results /// of using this trait can otherwise be trusted by `unsafe` code to be correct /// and fulful the listed obligations. pub unsafe trait Step: Clone + PartialOrd + Sized { /// Returns the number of *successor* steps required to get from `start` to `end`. /// /// Returns `None` if the number of steps would overflow `usize` /// (or is infinite, or if `end` would never be reached). /// /// # Invariants /// /// For any `a`, `b`, and `n`: /// /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::forward(&a, n) == Some(b)` /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::backward(&a, n) == Some(a)` /// * `steps_between(&a, &b) == Some(n)` only if `a <= b` /// * Corollary: `steps_between(&a, &b) == Some(0)` if and only if `a == b` /// * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`; /// this is the case wheen it would require more than `usize::MAX` steps to get to `b` /// * `steps_between(&a, &b) == None` if `a > b` fn steps_between(start: &Self, end: &Self) -> Option<usize>; /// Returns the value that would be obtained by taking the *successor* /// of `self` `count` times. /// /// If this would overflow the range of values supported by `Self`, returns `None`. /// /// # Invariants /// /// For any `a`, `n`, and `m`: /// /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, m).and_then(|x| Step::forward_checked(x, n))` /// /// For any `a`, `n`, and `m` where `n + m` does not overflow: /// /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, n + m)` /// /// For any `a` and `n`: /// /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))` /// * Corollary: `Step::forward_checked(&a, 0) == Some(a)` fn forward_checked(start: Self, count: usize) -> Option<Self>; /// Returns the value that would be obtained by taking the *successor* /// of `self` `count` times. /// /// If this would overflow the range of values supported by `Self`, /// this function is allowed to panic, wrap, or saturate. /// The suggested behavior is to panic when debug assertions are enabled, /// and to wrap or saturate otherwise. /// /// Unsafe code should not rely on the correctness of behavior after overflow. /// /// # Invariants /// /// For any `a`, `n`, and `m`, where no overflow occurs: /// /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)` /// /// For any `a` and `n`, where no overflow occurs: /// /// * `Step::forward_checked(a, n) == Some(Step::forward(a, n))` /// * `Step::forward(a, n) == (0..n).fold(a, |x, _| Step::forward(x, 1))` /// * Corollary: `Step::forward(a, 0) == a` /// * `Step::forward(a, n) >= a` /// * `Step::backward(Step::forward(a, n), n) == a` fn forward(start: Self, count: usize) -> Self { Step::forward_checked(start, count).expect("overflow in `Step::forward`") } /// Returns the value that would be obtained by taking the *successor* /// of `self` `count` times. /// /// # Safety /// /// It is undefined behavior for this operation to overflow the /// range of values supported by `Self`. If you cannot guarantee that this /// will not overflow, use `forward` or `forward_checked` instead. /// /// # Invariants /// /// For any `a`: /// /// * if there exists `b` such that `b > a`, it is safe to call `Step::forward_unchecked(a, 1)` /// * if there exists `b`, `n` such that `steps_between(&a, &b) == Some(n)`, /// it is safe to call `Step::forward_unchecked(a, m)` for any `m <= n`. /// /// For any `a` and `n`, where no overflow occurs: /// /// * `Step::forward_unchecked(a, n)` is equivalent to `Step::forward(a, n)` #[unstable(feature = "unchecked_math", reason = "niche optimization path", issue = "none")] unsafe fn forward_unchecked(start: Self, count: usize) -> Self { Step::forward(start, count) } /// Returns the value that would be obtained by taking the *successor* /// of `self` `count` times. /// /// If this would overflow the range of values supported by `Self`, returns `None`. /// /// # Invariants /// /// For any `a`, `n`, and `m`: /// /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == n.checked_add(m).and_then(|x| Step::backward_checked(a, x))` /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == try { Step::backward_checked(a, n.checked_add(m)?) }` /// /// For any `a` and `n`: /// /// * `Step::backward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::backward_checked(&x, 1))` /// * Corollary: `Step::backward_checked(&a, 0) == Some(a)` fn backward_checked(start: Self, count: usize) -> Option<Self>; /// Returns the value that would be obtained by taking the *predecessor* /// of `self` `count` times. /// /// If this would overflow the range of values supported by `Self`, /// this function is allowed to panic, wrap, or saturate. /// The suggested behavior is to panic when debug assertions are enabled, /// and to wrap or saturate otherwise. /// /// Unsafe code should not rely on the correctness of behavior after overflow. /// /// # Invariants /// /// For any `a`, `n`, and `m`, where no overflow occurs: /// /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)` /// /// For any `a` and `n`, where no overflow occurs: /// /// * `Step::backward_checked(a, n) == Some(Step::backward(a, n))` /// * `Step::backward(a, n) == (0..n).fold(a, |x, _| Step::backward(x, 1))` /// * Corollary: `Step::backward(a, 0) == a` /// * `Step::backward(a, n) <= a` /// * `Step::forward(Step::backward(a, n), n) == a` fn backward(start: Self, count: usize) -> Self { Step::backward_checked(start, count).expect("overflow in `Step::backward`") } /// Returns the value that would be obtained by taking the *predecessor* /// of `self` `count` times. /// /// # Safety /// /// It is undefined behavior for this operation to overflow the /// range of values supported by `Self`. If you cannot guarantee that this /// will not overflow, use `backward` or `backward_checked` instead. /// /// # Invariants /// /// For any `a`: /// /// * if there exists `b` such that `b < a`, it is safe to call `Step::backward_unchecked(a, 1)` /// * if there exists `b`, `n` such that `steps_between(&b, &a) == Some(n)`, /// it is safe to call `Step::backward_unchecked(a, m)` for any `m <= n`. /// /// For any `a` and `n`, where no overflow occurs: /// /// * `Step::backward_unchecked(a, n)` is equivalent to `Step::backward(a, n)` #[unstable(feature = "unchecked_math", reason = "niche optimization path", issue = "none")] unsafe fn backward_unchecked(start: Self, count: usize) -> Self { Step::backward(start, count) } } ``` Note that all of these are associated functions and not callable via method syntax; the calling syntax is always `Step::forward(start, n)`. This version of the trait additionally changes the stepping functions to talk their arguments by value. As opposed to previous attempts which provided a "step by one" method directly, this version of the trait only exposes "step by n". There are a few reasons for this: - `Range*`, the primary consumer of `Step`, assumes that the "step by n" operation is cheap. If a single step function is provided, it will be a lot more enticing to implement "step by n" as n repeated calls to "step by one". While this is not strictly incorrect, this behavior would be surprising for anyone used to using `Range<{primitive integer}>`. - With a trivial default impl, this can be easily added backwards-compatibly later. - The debug-wrapping "step by n" needs to exist for `RangeFrom` to be consistent between "step by n" and "step by one" operation. (Note: the behavior is not changed by this PR, but making the behavior consistent is made tenable by this PR.) Three "kinds" of step are provided: `_checked`, which returns an `Option` indicating attempted overflow; (unsuffixed), which provides "safe overflow" behavior (is allowed to panic, wrap, or saturate, depending on what is most convenient for a given type); and `_unchecked`, which is a version which assumes overflow does not happen. Review is appreciated to check that: - The invariants as described on the `Step` functions are enough to specify the "common sense" consistency for successor/predecessor. - Implementation of `Step` functions is correct in the face of overflow and the edges of representable integers. - Added tests of `Step` functions are asserting the correct behavior (and not just the implemented behavior).
2020-04-21Don't fuse Chain in its second iteratorJosh Stone-25/+39
Only the "first" iterator is actually set `None` when exhausted, depending on whether you iterate forward or backward. This restores behavior similar to the former `ChainState`, where it would transition from `Both` to `Front`/`Back` and only continue from that side. However, if you mix directions, then this may still set both sides to `None`, totally fusing the iterator.
2020-04-08Adjust Step::forward_checked docs for large typesCAD97-10/+2
Co-Authored-By: Nadrieril Feneanar <nadrieril@users.noreply.github.com>
2020-04-08Redesign the Step traitCAD97-29/+104
2020-04-06Use assoc float consts in libcoreLinus Färnstrand-2/+1
2020-04-05Stop importing int/float modules in libcoreLinus Färnstrand-28/+22
2020-03-17Add testsTim Vermeulen-0/+72
2020-02-08Auto merge of #68358 - matthewjasper:spec-fix, r=nikomatsakisbors-0/+16
Remove some unsound specializations This removes the unsound and exploitable specializations in the standard library * The `PartialEq` and `Hash` implementations for `RangeInclusive` are changed to avoid specialization. * The `PartialOrd` specialization for slices now specializes on a limited set of concrete types. * Added some tests for the soundness problems.
2020-02-01Remove some unsound specializationsMatthew Jasper-0/+16
2020-01-28Add `Iterator::map_while` method and corresponding `MapWhile` adapterWaffle-0/+2
2020-01-02Add Iterator::try_findMOZGIII-0/+40
2019-12-22Format the worldMark Rousskov-137/+167
2019-09-09Rollup merge of #64121 - timvermeulen:iter_step_by_internal, r=scottmcmMazdak Farrokhzad-0/+35
Override `StepBy::{try_fold, try_rfold}` Previous PR: https://github.com/rust-lang/rust/pull/51435 The previous PR was closed in favor of https://github.com/rust-lang/rust/pull/51601, which was later reverted. I don't think these implementations will make it harder to specialize `StepBy<Range<_>>` later, so we should be able to land this without any consequences. This should fix https://github.com/rust-lang/rust/issues/57517 – in my benchmarks `iter` and `iter.step_by(1)` now perform equally well, provided internal iteration is used.
2019-09-06Add Iterator comparison methods that take a comparison functionTim Vermeulen-0/+56
2019-09-04Override `StepBy::{try_fold, try_rfold}`Tim Vermeulen-0/+35
2019-08-30Rev::rposition counts from the wrong endXiang Fan-0/+6
Because of a compiler bug that adding `Self: ExactSizeIterator` makes the compiler forget `Self::Item` is `<I as Iterator>::Item`, we remove this specialization for now.
2019-08-18Fix bug in iter::Chain::size_hintTim Vermeulen-0/+48
2019-08-17Rollup merge of #62737 - timvermeulen:cycle_try_fold, r=scottmcmMazdak Farrokhzad-0/+12
Override Cycle::try_fold It's not very pretty, but I believe this is the simplest way to correctly implement `Cycle::try_fold`. The following may seem correct: ```rust loop { acc = self.iter.try_fold(acc, &mut f)?; self.iter = self.orig.clone(); } ``` ...but this loops infinitely in case `self.orig` is empty, as opposed to returning `acc`. So we first have to fully iterate `self.orig` to check whether it is empty or not, and before _that_, we have to iterate the remaining elements of `self.iter`. This should always call `self.orig.clone()` the same amount of times as repeated `next()` calls would. r? @scottmcm
2019-08-16Rollup merge of #60492 - acrrd:issues/54054_chain, r=SimonSapinMazdak Farrokhzad-0/+16
Add custom nth_back for Chain Implementation of nth_back for Chain. Part of #54054
2019-08-06Rollup merge of #62459 - timvermeulen:result_sum_internal_iteration, r=scottmcmMazdak Farrokhzad-0/+17
Use internal iteration in the Sum and Product impls of Result and Option This PR adds internal iteration to the `ResultShunt` iterator type underlying the `Sum` and `Product` impls of `Result`. I had to change `ResultShunt` to hold a mutable reference to an error instead, similar to `itertools::ProcessResults`, in order to be able to pass the `ResultShunt` itself by value (which is necessary for internal iteration). `ResultShunt::process` can unfortunately no longer be an associated function because that would make it generic over the lifetime of the error reference, which wouldn't work, so I turned it into the free function `process_results`. I removed the `OptionShunt` type and forwarded the `Sum` and `Product` impls of `Option` to their respective impls of `Result` instead, to avoid having to repeat the internal iteration logic.
2019-08-06Rollup merge of #61457 - timvermeulen:double_ended_iters, r=scottmcmMazdak Farrokhzad-13/+179
Implement DoubleEndedIterator for iter::{StepBy, Peekable, Take} Now that `DoubleEndedIterator::nth_back` has landed, `StepBy` and `Take` can have an efficient `DoubleEndedIterator` implementation. I don't know if there was any particular reason for `Peekable` not having a `DoubleEndedIterator` implementation, but it's quite trivial and I don't see any drawbacks to having it. I'm not very happy about the implementation of `Peekable::try_rfold`, but I didn't see another way to only take the value out of `self.peeked` in case `self.iter.try_rfold` didn't exit early. I only added `Peekable::rfold` (in addition to `try_rfold`) because its `Iterator` implementation has both `fold` and `try_fold` (and for similar reasons I added `Take::try_rfold` but not `Take::rfold`). Do we have any guidelines on whether we want both? If we do want both, maybe we should investigate which iterator adaptors override `try_fold` but not `fold` and add the missing implementations. At the moment I think that it's better to always have iterator adaptors implement both, because some iterators have a simpler `fold` implementation than their `try_fold` implementation. The tests that I added may not be sufficient because they're all just existing tests where `next`/`nth`/`fold`/`try_fold` are replaced by their DEI counterparts, but I do think all paths are covered. Is there anything in particular that I should probably also test?
2019-07-29Use internal iteration in the Sum and Product impls of Result and OptionTim Vermeulen-0/+17
2019-07-17Override Cycle::try_foldTim Vermeulen-0/+12
2019-07-09Implement DoubleEndedIterator for iter::{StepBy, Peekable, Take}Tim Vermeulen-13/+179
2019-07-09Unit test Iterator::partition_in_place and is_partitionedJosh Stone-0/+36
2019-06-20Rollup merge of #60454 - acrrd:issues/54054_skip, r=scottmcmMazdak Farrokhzad-0/+34
Add custom nth_back to Skip Implementation of nth_back for Skip. Part of #54054
2019-06-09implement nth_back for RangeInclusiveAdrian Friedli-0/+20
2019-06-08implement nth_back for RangeAdrian Friedli-0/+17
2019-05-29Add custom nth_back for SkipAndrea Corradi-0/+34
2019-05-29Rollup merge of #58975 - jtdowney:iter_arith_traits_option, r=dtolnayMazdak Farrokhzad-0/+16
Implement `iter::Sum` and `iter::Product` for `Option` This is similar to the existing implementation for `Result`. It will take each item into the accumulator unless a `None` is returned. I based a lot of this on #38580. From that discussion it didn't seem like this addition would be too controversial or difficult. One thing I still don't understand is picking the values for the `stable` attribute. This is my first non-documentation PR for rust so I am open to any feedback on improvements.
2019-05-03Add custom nth_back for ChainAndrea Corradi-0/+16
2019-04-20Deny rust_2018_idioms in libcore testsPhilipp Hansch-2/+2
2019-04-16implement nth_back for EnumerateAdrian Friedli-0/+18
2019-03-26Test the size_hint of empty ranges tooJosh Stone-0/+12
2019-03-26Implement useful steps_between for all integersJosh Stone-0/+49
We can use `usize::try_from` to convert steps from any size of integer. This enables a meaningful `size_hint()` for larger ranges, rather than always just `(0, None)`. Now they return the true `(len, Some(len))` when it fits, otherwise `(usize::MAX, None)` for overflow.
2019-03-16Rollup merge of #59072 - RalfJung:miri-alloc-tests, r=kennytmkennytm-2/+0
we can now skip should_panic tests with the libtest harness
2019-03-12Add tests to ensure that Iterator::min and Iterator::max are stableTim Vermeulen-0/+28
2019-03-10we can now skip should_panic tests with the libtest harnessRalf Jung-2/+0
2019-03-06Implement `iter::Sum` and `iter::Product` for `Option`John Downey-0/+16
This is similar to the existing implementation for `Result`. It will take each item into the accumulator unless a `None` is returned.
2019-02-23Rollup merge of #58122 - matthieu-m:range_incl_perf, r=dtolnayMazdak Farrokhzad-3/+21
RangeInclusive internal iteration performance improvement. Specialize `Iterator::try_fold` and `DoubleEndedIterator::try_rfold` to improve code generation in all internal iteration scenarios. This changes brings the performance of internal iteration with `RangeInclusive` on par with the performance of iteration with `Range`: - Single conditional jump in hot loop, - Unrolling and vectorization, - And even Closed Form substitution. Unfortunately, it only applies to internal iteration. Despite various attempts at stream-lining the implementation of `next` and `next_back`, LLVM has stubbornly refused to optimize external iteration appropriately, leaving me with a choice between: - The current implementation, for which Closed Form substitution is performed, but which uses 2 conditional jumps in the hot loop when optimization fail. - An implementation using a `is_done` boolean, which uses 1 conditional jump in the hot loop when optimization fail, allowing unrolling and vectorization, but for which Closed Form substitution fails. In the absence of any conclusive evidence as to which usecase matters most, and with no assurance that the lack of Closed Form substitution is not indicative of other optimizations being foiled, there is no way to pick one implementation over the other, and thus I defer to the statu quo as far as `next` and `next_back` are concerned.
2019-02-13review or fix remaining miri failures in libcoreRalf Jung-2/+0
2019-02-13review or fix miri failures in iter, slice, cell, timeRalf Jung-6/+2
2019-02-13mark failures expected due to panicsRalf Jung-2/+2
2019-02-10libs: doc commentsAlexander Regueiro-2/+2
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-01 00:30:31 +0000