about summary refs log tree commit diff
path: root/src/libcore/iter
AgeCommit message (Collapse)AuthorLines
2020-07-27mv std libs to library/mark-10472/+0
2020-07-24Rollup merge of #74669 - Homarechan:fix_typo, r=lcnrYuki Okushi-1/+1
Fix typo
2020-07-23Fix typokanimum-1/+1
2020-07-23Rollup merge of #74141 - euclio:typos, r=steveklabnikManish Goregaokar-1/+1
libstd/libcore: fix various typos
2020-07-17Rollup merge of #74428 - tshepang:better-filter-map-doc, r=jonas-schievinkManish Goregaokar-4/+2
docs: better demonstrate that None values are skipped as many times a… …s needed
2020-07-17Remove code span for implLzu Tao-3/+3
Because the old one is harder to read and confuse typing checkers.
2020-07-17Link Some(item)Lzu Tao-2/+3
2020-07-17Remove unneeded link for OptionLzu Tao-1/+0
2020-07-17Intra-doc for iter Sum and Product traitsLzu Tao-6/+6
2020-07-17Intra-doc for DoubleEndIteratorLzu Tao-4/+2
2020-07-17Intra doc for iter marker traitsLzu Tao-6/+4
2020-07-17Use intra-doc link on Iterator pageLzu Tao-56/+21
2020-07-17docs: better demonstrate that None values are skipped as many times as neededTshepang Lekhonkhobe-4/+2
2020-07-16Revert "Remove spotlight usage"Manish Goregaokar-0/+1
This reverts commit 13c6d5819aae3c0de6a90e7f17ea967bf4487cbb.
2020-07-14Auto merge of #73490 - CAD97:range-unchecked-stepping, r=Amanieubors-12/+12
Use step_unchecked more liberally in range iter impls Without these `_unchecked`, these operations on iterators of `char` fail to optimize out the unreachable panicking condition on overflow. cc @cuviper https://github.com/rayon-rs/rayon/pull/771 where this was discovered.
2020-07-09libstd/libcore: fix various typosAndy Russell-1/+1
2020-07-05Fix spacing in Iterator fold docIvan Tham-2/+2
2020-06-30Deny unsafe ops in unsafe fns, part 6LeSeulArtichaut-1/+0
And final part!!!
2020-06-30Deny unsafe ops in unsafe fns, part 2LeSeulArtichaut-16/+38
2020-06-19Refactor `try_find` a littleJosh Stone-11/+18
The `E` type parameter was unnecessary, so it's now removed. The folding closure now has reduced parametricity on just `T = Self::Item`, rather than the whole `Self` iterator type. There's otherwise no functional change in this.
2020-06-18Use step_unchecked more liberallyCAD97-12/+12
2020-06-14Fix iterator copied() documentation example codeSteve Heindel-2/+2
2020-05-30Rollup merge of #72368 - CAD97:rangeto, r=dtolnayRalf Jung-9/+1
Resolve overflow behavior for RangeFrom This specifies a documented unspecified implementation detail of `RangeFrom` and makes it consistently implement the specified behavior. Specifically, `(u8::MAX).next()` is defined to cause an overflow, and resolve that overflow in the same manner as the `Step::forward` implementation. The inconsistency that has existed is `<RangeFrom as Iterator>::nth`. The existing behavior should be plain to see after #69659: the skipping part previously always panicked if it caused an overflow, but the final step (to set up the state for further iteration) has always been debug-checked. The inconsistency, then, is that `RangeFrom::nth` does not implement the same behavior as the naive (and default) implementation of just calling `next` multiple times. This PR aligns `RangeFrom::nth` to have identical behavior to the naive implementation. It also lines up with the standard behavior of primitive math in Rust everywhere else in the language: debug checked overflow. cc @Amanieu --- Followup to #69659. Closes #25708 (by documenting the panic as intended). The documentation wording is preliminary and can probably be improved. This will probably need an FCP, as it changes observable stable behavior.
2020-05-30Rollup merge of #72162 - cuviper:extend_one, r=Mark-SimulacrumYuki Okushi-5/+26
Add Extend::{extend_one,extend_reserve} This adds new optional methods on `Extend`: `extend_one` add a single element to the collection, and `extend_reserve` pre-allocates space for the predicted number of incoming elements. These are used in `Iterator` for `partition` and `unzip` as they shuffle elements one-at-a-time into their respective collections.
2020-05-29Add extend_one tracking issue 72631Josh Stone-2/+2
2020-05-29Use a canonical name for extend_reserve(additional)Josh Stone-1/+3
Co-authored-by: David Tolnay <dtolnay@gmail.com>
2020-05-29Add Extend::{extend_one,extend_reserve}Josh Stone-5/+24
This adds new optional methods on `Extend`: `extend_one` add a single element to the collection, and `extend_reserve` pre-allocates space for the predicted number of incoming elements. These are used in `Iterator` for `partition` and `unzip` as they shuffle elements one-at-a-time into their respective collections.
2020-05-29Auto merge of #72756 - RalfJung:rollup-tbjmtx2, r=RalfJungbors-1/+73
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-29Rollup merge of #72413 - CAD97:char-range, r=dtolnayRalf Jung-1/+73
impl Step for char (make Range*<char> iterable) [[irlo thread]](https://internals.rust-lang.org/t/mini-rfc-make-range-char-work/12392?u=cad97) [[godbolt asm example]](https://rust.godbolt.org/z/fdveKo) Add an implementation of the `Step` trait for `char`, which has the effect of making `RangeInclusive<char>` (and the other range types) iterable. I've used the surrogate range magic numbers as magic numbers here rather than e.g. a `const SURROGATE_RANGE = 0xD800..0xE000` because these numbers appear to be used as magic numbers elsewhere and there doesn't exist constants for them yet. These files definitely aren't where surrogate range constants should live. `ExactSizeIterator` is not implemented because `0x10FFFF` is bigger than fits in a `usize == u16`. However, given we already provide some `ExactSizeIterator` that are not correct on 16 bit targets, we might still want to consider providing it for `Range`[`Inclusive`]`<char>`, as it is definitely _very_ convenient. (At the very least, we want to make sure `.count()` doesn't bother iterating the range.) The second commit in this PR changes a call to `Step::forward` to use `Step::forward_unchecked` in `RangeInclusive::next`. This is because without this patch, iteration over all codepoints (`'\0'..=char::MAX`) does not successfully optimize out the panicking branch. This was mentioned in the PR that updated `Step` to its current design, but was deemed not yet necessary as it did not impact codegen for integral types. More of `Range*`'s implementations' calls to `Step` methods will probably want to see if they can use the `_unchecked` version as (if) we open up `Step` to being implemented on more types. --- cc @rust-lang/libs, this is insta-stable and a fairly significant addition to `Range*`'s capabilities; this is the first instance of a noncontinuous domain being iterable with `Range` (or, well, anything other than primitive integers). I don't think this needs a full RFC, but it should definitely get some decent eyes on it.
2020-05-29Rollup merge of #72310 - jyn514:peekable-next-if, r=dtolnayDylan DPC-0/+63
Add Peekable::next_if 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| self.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) Possible extensions: A specialization of `next_if` to using `Eq::eq`. The only difficulty here is the naming - maybe `next_if_eq`? Alternatives: - Instead of `func: impl FnOnce(&I::Item) -> bool`, use `func: impl FnOnce(I::Item) -> Option<I::Item>`. This has the advantage that `func` can move the value if necessary, but means that there is no guarantee `func` will return the same value it was given. - Instead of `fn next_if(...) -> Option<I::Item>`, use `fn next_if(...) -> bool`. This makes the common case of `iter.next_if(f).is_some()` easier, but makes the unusual case impossible. Bikeshedding on naming: - `next_if` could be renamed to `consume_if` (to match `eat`, but a little more formally) - `next_if_eq` could be renamed to `consume`. This is more concise but less self-explanatory if you haven't written a lot of parsers. - Both of the above, but with `consume` replaced by `eat`.
2020-05-29Clarify the documentation of takeAlexis Bourget-0/+11
2020-05-28FIx off-by-one in char::steps_betweenCAD97-1/+1
2020-05-26Add Peekable::next_ifJoshua Nelson-0/+63
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-26Add remark regarding DoubleEndedIteratorphilipp-0/+26
2020-05-21Add safety annotations in iter::rangeCAD97-0/+4
2020-05-21Use Step::forward_unchecked in RangeInclusive::nextCAD97-1/+5
2020-05-21impl Step for charCAD97-0/+64
Enables Range<char> to be iterable Note: https://rust.godbolt.org/z/fdveKo An iteration over all char ('\0'..=char::MAX) includes unreachable panic code currently. Updating RangeInclusive::next to call Step::forward_unchecked (which is safe to do but not done yet becuase it wasn't necessary) successfully removes the panic from this iteration.
2020-05-19Resolve overflow behavior for RangeFromCAD97-9/+1
2020-05-18Add some more `rfold` implementations.Nicholas Nethercote-0/+68
2020-05-18Tweak `partition`, `unzip`, `try_find`.Nicholas Nethercote-7/+7
Many default iterator methods use `try_fold` or `fold`, and these ones can too.
2020-05-18Make `fold` standalone.Nicholas Nethercote-13/+124
`fold` is currently implemented via `try_fold`, but implementing it directly results in slightly less LLVM IR being generated, speeding up compilation of some benchmarks. (And likewise for `rfold`.) The commit adds `fold` implementations to all the iterators that lack one but do have a `try_fold` implementation. Most of these just call the `try_fold` implementation directly.
2020-05-16Rollup merge of #72166 - nnethercote:simpler-slice-Iterator-methods, r=cuviperDylan DPC-1/+1
Simpler slice `Iterator` methods These reduce the amount of LLVM IR generated, helping compile times. r? @cuviper
2020-05-15Auto merge of #69659 - CAD97:step-rework-take-3, r=Amanieubors-171/+411
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-05-14improve step_integer_impls macroCAD97-29/+6
2020-05-13Improve Step::forward/backward for optimizationCAD97-14/+12
The previous definition did not optimize down to a single add operation, but this version does appear to.
2020-05-13Improve comments in iter::StepCAD97-3/+3
2020-05-13Change `Iterator::nth` to use `self.next()` in a `while` loop.Nicholas Nethercote-1/+1
Currently it uses `for x in self`, which seems dubious within an iterator method. Furthermore, `self.next()` is used in all the other iterator methods.
2020-04-26Use min_specialization in liballocMatthew Jasper-0/+2
- Remove a type parameter from `[A]RcFromIter`. - Remove an implementation of `[A]RcFromIter` that didn't actually specialize anything. - Remove unused implementation of `IsZero` for `Option<&mut T>`. - Change specializations of `[A]RcEqIdent` to use a marker trait version of `Eq`. - Remove `BTreeClone`. I couldn't find a way to make this work with `min_specialization`. - Add `rustc_unsafe_specialization_marker` to `Copy` and `TrustedLen`.
2020-04-25Bump rustfmt to most recently shippedMark Rousskov-1/+1
2020-04-24Rollup merge of #71492 - LeSeulArtichaut:document-unsafe-2, r=Mark-SimulacrumDylan DPC-2/+8
Document unsafety in core::{panicking, alloc::layout, hint, iter::adapters::zip} Helps with #66219. r? @Mark-Simulacrum do you want to continue reading safety comments? :D
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-01-12 15:31:07 +0000