| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Implement some trivial size_hints for various iterators
This also implements ExactSizeIterator where applicable.
Addresses most of the Iterator traits mentioned in #23708.
I intend to do more, but I don't want to make the PR too large.
|
|
portability lint
https://github.com/rust-lang/rust/pull/49305#issuecomment-376293243
|
|
The comment "the value passed on to the next iteration" confused me since it sounded more like what Haskell's [scanl](http://hackage.haskell.org/package/base-4.11.0.0/docs/Prelude.html#v:scanl) does where the closure's return value serves as both the "yielded value" *and* the new value of the "state".
I tried changing the example to make it clear that the closure's return value is decoupled from the state argument.
|
|
|
|
This also implements ExactSizeIterator where applicable.
Addresses most of the Iterator traits mentioned in #23708.
|
|
lifetimes)
|
|
Rollup of 17 pull requests
- Successful merges: #48706, #48875, #48892, #48922, #48957, #48959, #48961, #48965, #49007, #49024, #49042, #49050, #48853, #48990, #49037, #49049, #48972
- Failed merges:
|
|
|
|
Stabilize std::ops::RangeInclusive and std::ops::RangeInclusiveTo.
|
|
Stabilize FusedIterator
FusedIterator is a marker trait that promises that the implementing
iterator continues to return `None` from `.next()` once it has returned
`None` once (and/or `.next_back()`, if implemented).
The effects of FusedIterator are already widely available through
`.fuse()`, but with stable `FusedIterator`, stable Rust users can
implement this trait for their iterators when appropriate.
Closes #35602
|
|
doc: no need for the reference
Also, we are well within line length limit
|
|
|
|
FusedIterator is a marker trait that promises that the implementing
iterator continues to return `None` from `.next()` once it has returned
`None` once (and/or `.next_back()`, if implemented).
The effects of FusedIterator are already widely available through
`.fuse()`, but with stable `FusedIterator`, stable Rust users can
implement this trait for their iterators when appropriate.
|
|
|
|
Makes the bench asked about on URLO 58x faster :)
|
|
Also:
- apply some rustfmt love
- fix output of one example
|
|
|
|
Add Iterator::flatten
This adds the trait method `.flatten()` on `Iterator` which flattens one level of nesting from an iterator or (into)iterators. The method `.flat_fmap(f)` is then redefined as `.map(f).flatten()`. The implementation of `Flatten` is essentially that of what it was for `FlatMap` but removing the call to `f` at various places.
Hopefully the type alias approach should be OK as was indicated / alluded to by @bluss and @eddyb in https://github.com/rust-lang/rfcs/pull/2306#issuecomment-361391370.
cc @scottmcm
|
|
Add Iterator::try_for_each
The fallible version of `for_each` aka the stateless version of `try_fold`. Inspired by @cuviper's comment in https://github.com/rust-lang/rust/pull/45379#issuecomment-338370020 as a more direct and obvious solution than `.map(f).collect::<Result<(), _>>()`.
Like `for_each`, no need for an `r` version thanks to overrides in `Rev`.
`iterator_try_fold` tracking issue: https://github.com/rust-lang/rust/issues/45594
|
|
per @clarcharr's review
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#37653 support `default impl` for specialization
this commit implements the second part of the `default impl` feature:
> - a `default impl` need not include all items from the trait
> - a `default impl` alone does not mean that a type implements the trait
The first point allows rustc to compile and run something like this:
```
trait Foo {
fn foo_one(&self) -> &'static str;
fn foo_two(&self) -> &'static str;
}
default impl<T> Foo for T {
fn foo_one(&self) -> &'static str {
"generic"
}
}
struct MyStruct;
fn main() {
assert!(MyStruct.foo_one() == "generic");
}
```
but it shows a proper error if trying to call `MyStruct.foo_two()`
The second point allows a `default impl` to be considered as not implementing the `Trait` if it doesn't implement all the trait items.
The tests provided (in the compile-fail section) should cover all the possible trait resolutions.
Let me know if some tests is missed.
See [referenced ](https://github.com/rust-lang/rust/issues/37653) issue for further info
r? @nikomatsakis
|
|
|
|
Add std/core::iter::repeat_with
Adds an iterator primitive `repeat_with` which is the "lazy" version of `repeat` but also more flexible since you can build up state with the `FnMut`. The design is mostly taken from `repeat`.
r? @rust-lang/libs
cc @withoutboats, @scottmcm
|
|
Add Range[Inclusive]::is_empty
During https://github.com/rust-lang/rfcs/pull/1980, it was discussed that figuring out whether a range is empty was subtle, and thus there should be a clear and obvious way to do it. It can't just be ExactSizeIterator::is_empty (also unstable) because not all ranges are ExactSize -- such as `Range<i64>` and `RangeInclusive<usize>`.
Things to ponder:
- Unless this is stabilized first, this makes stabilizing ExactSizeIterator::is_empty more icky, since this hides that.
- This is only on `Range` and `RangeInclusive`, as those are the only ones where it's interesting. But one could argue that it should be on more for consistency, or on RangeArgument instead.
- The bound on this is PartialOrd, since that works ok (see tests for float examples) and is consistent with `contains`. But ranges like `NAN..=NAN`_are_ kinda weird.
- [x] ~~There's not a real issue number on this yet~~
|
|
|
|
|
|
|
|
The fallible version of for_each and the stateless version of try_fold.
|
|
|
|
|
|
|
|
|
|
Document the behaviour of infinite iterators on potentially-computable methods
It’s not entirely clear from the current documentation what behaviour
calling a method such as `min` on an infinite iterator like `RangeFrom`
is. One might expect this to terminate, but in fact, for infinite
iterators, `min` is always nonterminating (at least in the standard
library). This adds a quick note about this behaviour for clarification.
|
|
During the RFC, it was discussed that figuring out whether a range is empty was subtle, and thus there should be a clear and obvious way to do it. It can't just be ExactSizeIterator::is_empty (also unstable) because not all ranges are ExactSize -- not even Range<i32> or RangeInclusive<usize>.
|
|
Simplify RangeInclusive::next[_back]
`match`ing on an `Option<Ordering>` seems cause some confusion for LLVM; switching to just using comparison operators removes a few jumps from the simple `for` loops I was trying.
cc https://github.com/rust-lang/rust/issues/45222 https://github.com/rust-lang/rust/issues/28237#issuecomment-363706510
Example:
```rust
#[no_mangle]
pub fn coresum(x: std::ops::RangeInclusive<u64>) -> u64 {
let mut sum = 0;
for i in x {
sum += i ^ (i-1);
}
sum
}
```
Today:
```asm
coresum:
xor r8d, r8d
mov r9, -1
xor eax, eax
jmp .LBB0_1
.LBB0_4:
lea rcx, [rdi - 1]
xor rcx, rdi
add rax, rcx
mov rsi, rdx
mov rdi, r10
.LBB0_1:
cmp rdi, rsi
mov ecx, 1
cmovb rcx, r9
cmove rcx, r8
test rcx, rcx
mov edx, 0
mov r10d, 1
je .LBB0_4 // 1
cmp rcx, -1
jne .LBB0_5 // 2
lea r10, [rdi + 1]
mov rdx, rsi
jmp .LBB0_4 // 3
.LBB0_5:
ret
```
With this PR:
```asm
coresum:
cmp rcx, rdx
jbe .LBB0_2
xor eax, eax
ret
.LBB0_2:
xor r8d, r8d
mov r9d, 1
xor eax, eax
.p2align 4, 0x90
.LBB0_3:
lea r10, [rcx + 1]
cmp rcx, rdx
cmovae rdx, r8
cmovae r10, r9
lea r11, [rcx - 1]
xor r11, rcx
add rax, r11
mov rcx, r10
cmp r10, rdx
jbe .LBB0_3 // Just this
ret
```
<details><summary>Though using internal iteration (`.map(|i| i ^ (i-1)).sum()`) is still shorter to type, and lets the compiler unroll it</summary>
```asm
coresum_inner:
.Lcfi0:
.seh_proc coresum_inner
sub rsp, 168
.Lcfi1:
.seh_stackalloc 168
vmovdqa xmmword ptr [rsp + 144], xmm15
.Lcfi2:
.seh_savexmm 15, 144
vmovdqa xmmword ptr [rsp + 128], xmm14
.Lcfi3:
.seh_savexmm 14, 128
vmovdqa xmmword ptr [rsp + 112], xmm13
.Lcfi4:
.seh_savexmm 13, 112
vmovdqa xmmword ptr [rsp + 96], xmm12
.Lcfi5:
.seh_savexmm 12, 96
vmovdqa xmmword ptr [rsp + 80], xmm11
.Lcfi6:
.seh_savexmm 11, 80
vmovdqa xmmword ptr [rsp + 64], xmm10
.Lcfi7:
.seh_savexmm 10, 64
vmovdqa xmmword ptr [rsp + 48], xmm9
.Lcfi8:
.seh_savexmm 9, 48
vmovdqa xmmword ptr [rsp + 32], xmm8
.Lcfi9:
.seh_savexmm 8, 32
vmovdqa xmmword ptr [rsp + 16], xmm7
.Lcfi10:
.seh_savexmm 7, 16
vmovdqa xmmword ptr [rsp], xmm6
.Lcfi11:
.seh_savexmm 6, 0
.Lcfi12:
.seh_endprologue
cmp rdx, rcx
jae .LBB1_2
xor eax, eax
jmp .LBB1_13
.LBB1_2:
mov r8, rdx
sub r8, rcx
jbe .LBB1_3
cmp r8, 7
jbe .LBB1_5
mov rax, r8
and rax, -8
mov r9, r8
and r9, -8
je .LBB1_5
add rax, rcx
vmovq xmm0, rcx
vpshufd xmm0, xmm0, 68
mov ecx, 1
vmovq xmm1, rcx
vpslldq xmm1, xmm1, 8
vpaddq xmm1, xmm0, xmm1
vpxor xmm0, xmm0, xmm0
vpcmpeqd xmm11, xmm11, xmm11
vmovdqa xmm12, xmmword ptr [rip + __xmm@00000000000000010000000000000001]
vmovdqa xmm13, xmmword ptr [rip + __xmm@00000000000000030000000000000003]
vmovdqa xmm14, xmmword ptr [rip + __xmm@00000000000000050000000000000005]
vmovdqa xmm15, xmmword ptr [rip + __xmm@00000000000000080000000000000008]
mov rcx, r9
vpxor xmm4, xmm4, xmm4
vpxor xmm5, xmm5, xmm5
vpxor xmm6, xmm6, xmm6
.p2align 4, 0x90
.LBB1_9:
vpaddq xmm7, xmm1, xmmword ptr [rip + __xmm@00000000000000020000000000000002]
vpaddq xmm9, xmm1, xmmword ptr [rip + __xmm@00000000000000040000000000000004]
vpaddq xmm10, xmm1, xmmword ptr [rip + __xmm@00000000000000060000000000000006]
vpaddq xmm8, xmm1, xmm12
vpxor xmm7, xmm8, xmm7
vpaddq xmm2, xmm1, xmm13
vpxor xmm8, xmm2, xmm9
vpaddq xmm3, xmm1, xmm14
vpxor xmm3, xmm3, xmm10
vpaddq xmm2, xmm1, xmm11
vpxor xmm2, xmm2, xmm1
vpaddq xmm0, xmm2, xmm0
vpaddq xmm4, xmm7, xmm4
vpaddq xmm5, xmm8, xmm5
vpaddq xmm6, xmm3, xmm6
vpaddq xmm1, xmm1, xmm15
add rcx, -8
jne .LBB1_9
vpaddq xmm0, xmm4, xmm0
vpaddq xmm0, xmm5, xmm0
vpaddq xmm0, xmm6, xmm0
vpshufd xmm1, xmm0, 78
vpaddq xmm0, xmm0, xmm1
vmovq r10, xmm0
cmp r8, r9
jne .LBB1_6
jmp .LBB1_11
.LBB1_3:
xor r10d, r10d
jmp .LBB1_12
.LBB1_5:
xor r10d, r10d
mov rax, rcx
.p2align 4, 0x90
.LBB1_6:
lea rcx, [rax - 1]
xor rcx, rax
inc rax
add r10, rcx
cmp rdx, rax
jne .LBB1_6
.LBB1_11:
mov rcx, rdx
.LBB1_12:
lea rax, [rcx - 1]
xor rax, rcx
add rax, r10
.LBB1_13:
vmovaps xmm6, xmmword ptr [rsp]
vmovaps xmm7, xmmword ptr [rsp + 16]
vmovaps xmm8, xmmword ptr [rsp + 32]
vmovaps xmm9, xmmword ptr [rsp + 48]
vmovaps xmm10, xmmword ptr [rsp + 64]
vmovaps xmm11, xmmword ptr [rsp + 80]
vmovaps xmm12, xmmword ptr [rsp + 96]
vmovaps xmm13, xmmword ptr [rsp + 112]
vmovaps xmm14, xmmword ptr [rsp + 128]
vmovaps xmm15, xmmword ptr [rsp + 144]
add rsp, 168
ret
.seh_handlerdata
.section .text,"xr",one_only,coresum_inner
.Lcfi13:
.seh_endproc
```
</details>
|
|
`match`ing on an `Option<Ordering>` seems cause some confusion for LLVM; switching to just using comparison operators removes a few jumps from the simple `for` loops I was trying.
|
|
Implement TrustedLen for Take<Repeat> and Take<RangeFrom>
This will allow optimization of simple `repeat(x).take(n).collect()` iterators, which are currently not vectorized and have capacity checks.
This will only support a few aggregates on `Repeat` and `RangeFrom`, which might be enough for simple cases, but doesn't optimize more complex ones. Namely, Cycle, StepBy, Filter, FilterMap, Peekable, SkipWhile, Skip, FlatMap, Fuse and Inspect are not marked `TrustedLen` when the inner iterator is infinite.
Previous discussion can be found in #47082
r? @alexcrichton
|
|
Add filtering options to `rustc_on_unimplemented`
- Add filtering options to `rustc_on_unimplemented` for local traits, filtering on `Self` and type arguments.
- Add a way to provide custom notes.
- Tweak binops text.
- Add filter to detect wether `Self` is local or belongs to another crate.
- Add filter to `Iterator` diagnostic for `&str`.
Partly addresses #44755 with a different syntax, as a first approach. Fixes #46216, fixes #37522, CC #34297, #46806.
|
|
Override try_[r]fold for RangeInclusive
Because the last item needs special handling, it seems that LLVM has trouble canonicalizing the loops in external iteration. With the override, it becomes obvious that the start==end case exits the loop (as opposed to the one *after* that exiting the loop in external iteration).
Demo adapted from https://github.com/rust-lang/rust/issues/45222
```rust
#[no_mangle]
pub fn foo3r(n: u64) -> u64 {
let mut count = 0;
(0..n).for_each(|_| {
(0 ..= n).rev().for_each(|j| {
count += j;
})
});
count
}
```
<details>
<summary>Current nightly ASM, 100 lines (https://play.rust-lang.org/?gist=f5674c702c6e2045c3aab5d03763e5f6&version=nightly&mode=release)</summary>
```asm
foo3r:
pushq %rbx
.Lcfi0:
.Lcfi1:
testq %rdi, %rdi
je .LBB0_1
testb $1, %dil
jne .LBB0_4
xorl %eax, %eax
xorl %r8d, %r8d
cmpq $1, %rdi
jne .LBB0_11
jmp .LBB0_23
.LBB0_1:
xorl %eax, %eax
popq %rbx
retq
.LBB0_4:
xorl %r8d, %r8d
movq $-1, %r9
xorl %eax, %eax
movq %rdi, %r11
xorl %r10d, %r10d
jmp .LBB0_5
.LBB0_8:
addq %r11, %rax
movq %rsi, %r11
movq %rdx, %r10
.LBB0_5:
cmpq %r11, %r10
movl $1, %ecx
cmovbq %r9, %rcx
cmoveq %r8, %rcx
testq %rcx, %rcx
movl $0, %esi
movl $1, %edx
je .LBB0_8
cmpq $-1, %rcx
jne .LBB0_9
leaq -1(%r11), %rsi
movq %r10, %rdx
jmp .LBB0_8
.LBB0_9:
movl $1, %r8d
cmpq $1, %rdi
je .LBB0_23
.LBB0_11:
xorl %r9d, %r9d
movq $-1, %r10
.LBB0_12:
movq %rdi, %rsi
xorl %r11d, %r11d
jmp .LBB0_13
.LBB0_16:
addq %rsi, %rax
movq %rcx, %rsi
movq %rbx, %r11
.LBB0_13:
cmpq %rsi, %r11
movl $1, %edx
cmovbq %r10, %rdx
cmoveq %r9, %rdx
testq %rdx, %rdx
movl $0, %ecx
movl $1, %ebx
je .LBB0_16
cmpq $-1, %rdx
jne .LBB0_17
leaq -1(%rsi), %rcx
movq %r11, %rbx
jmp .LBB0_16
.LBB0_17:
movq %rdi, %rcx
xorl %r11d, %r11d
jmp .LBB0_18
.LBB0_21:
addq %rcx, %rax
movq %rsi, %rcx
movq %rbx, %r11
.LBB0_18:
cmpq %rcx, %r11
movl $1, %edx
cmovbq %r10, %rdx
cmoveq %r9, %rdx
testq %rdx, %rdx
movl $0, %esi
movl $1, %ebx
je .LBB0_21
cmpq $-1, %rdx
jne .LBB0_22
leaq -1(%rcx), %rsi
movq %r11, %rbx
jmp .LBB0_21
.LBB0_22:
addq $2, %r8
cmpq %rdi, %r8
jne .LBB0_12
.LBB0_23:
popq %rbx
retq
.Lfunc_end0:
```
</details><br>
With this PR:
```asm
foo3r:
test rcx, rcx
je .LBB3_1
lea r8, [rcx - 1]
lea rdx, [rcx - 2]
mov rax, r8
mul rdx
shld rdx, rax, 63
imul r8, r8
add r8, rcx
sub r8, rdx
imul r8, rcx
mov rax, r8
ret
.LBB3_1:
xor r8d, r8d
mov rax, r8
ret
```
|
|
Because the last item needs special handling, it seems that LLVM has trouble canonicalizing the loops in external iteration. With the override, it becomes obvious that the start==end case exits the loop (as opposed to the one *after* that exiting the loop in external iteration).
|
|
|
|
|
|
|
|
|
