Optimize indexing slices and strs with inclusive ranges
Instead of separately checking for `end == usize::MAX` and `end + 1 > slice.len()`, we can check for `end >= slice.len()`. Also consolidate all the str indexing related panic functions into a single function which reports the correct error depending on the arguments, as the slice indexing code already does.
The downside of all this is that the panic message is slightly less specific when trying to index with `[..=usize::MAX]`: instead of saying "attempted to index str up to maximum usize" it just says "end byte index {end} out of bounds". But this is a rare enough case that I think it is acceptable
The panic message when slicing a string with a negative length range (eg
`"abcdef"[4..3]`) is confusing: it gives the condition that failed to hold,
whilst all the other panic messages give the condition that did hold.
Before:
begin <= end (4 <= 3) when slicing `abcdef`
After:
begin > end (4 > 3) when slicing `abcdef`
Replace `self.end() == usize::MAX` and `self.end() + 1 > slice.len()`
with `self.end() >= slice.len()`. Same reasoning as previous commit.
Also consolidate the str panicking functions into function.
remove `#[deprecated]` from unstable & internal `SipHasher13` and `24` types
These types are unstable and `doc(hidden)` (under the internal feature `hashmap_internals`). Deprecating them only adds noise (`#[allow(deprecated)]`) to all places where they are used, so this PR removes the deprecation attributes from them.
It also includes a few other small cleanups in separate commits, including one I overlooked in rust-lang/rust#151228.
Use `rand` crate more idiomatically
Small cleanup, found while working on something else.
We were using `rand` un-idiomatically in a couple of places, and it was bugging me...
`Vec::push` in consts MVP
Example:
```rust
const X: &'static [u32] = {
let mut v = Vec::with_capacity(6);
let mut x = 1;
while x < 42 {
v.push(x);
x *= 2;
}
assert!(v.len() == 6);
v.const_make_global()
};
assert_eq!([1, 2, 4, 8, 16, 32], X);
```
Oh this is fun...
* We split out the implementation of `Global` such that it calls `intrinsics::const_allocate` and `intrinsics::const_deallocate` during compile time. This is achieved using `const_eval_select`
* This allows us to `impl const Allocator for Global`
* We then constify everything necessary for `Vec::with_capacity` and `Vec::push`.
* Added `Vec::const_make_global` to leak and intern the final value via `intrinsics::const_make_global`. If we see any pointer in the final value of a `const` that did not call `const_make_global`, we error as implemented in rust-lang/rust#143595.
r? `@rust-lang/wg-const-eval`
To-do for me:
* [x] Assess the rustdoc impact of additional bounds in the method
* [x] ~~Increase test coverage~~ I think this is enough for an unstable feature.
This commit consolidates all changes, including the core logic fix for IntoIter::nth_back and the addition of the Miri regression test in `library/alloctests/tests/vec.rs`, to prevent Undefined Behavior (UB) when dealing with highly-aligned Zero-Sized Types.
In `BTreeMap::eq`, do not compare the elements if the sizes are different.
Reverts rust-lang/rust#147101 in library/alloc/src/btree/
rust-lang/rust#147101 replaced some instances of code like `a.len() == b.len() && a.iter().eq(&b)` with just `a.iter().eq(&b)`, but the optimization that PR introduced only applies for `TrustedLen` iterators, and `BTreeMap`'s itertors are not `TrustedLen`, so this theoretically regressed perf for comparing large `BTreeMap`/`BTreeSet`s with unequal lengths but equal prefixes, (and also made it so that comparing two different-length `BTreeMap`/`BTreeSet`s with elements whose `PartialEq` impls that can panic now can panic, though this is not a "promised" behaviour either way (cc rust-lang/rust#149122))
Given that `TrustedLen` is an unsafe trait, I opted to not implement it for `BTreeMap`'s iterators, and instead just revert the change. If someone else wants to audit `BTreeMap`'s iterators to make sure they always return the right number of items (even in the face of incorrect user `Ord` impls) and then implement `TrustedLen` for them so that the optimization works for them, then this can be closed in favor of that (or if the perf regression is deemed too theoretical, this can be closed outright).
Example of theoretical perf regression: https://play.rust-lang.org/?version=beta&mode=release&edition=2024&gist=a37e3d61e6bf02669b251315c9a44fe2 (very rough estimates, using `Instant::elapsed`).
In release mode on stable the comparison takes ~23.68µs.
In release mode on beta/nightly the comparison takes ~48.351057ms.
alloc: fix `Debug` implementation of `ExtractIf`
I noticed this while reviewing rust-lang/rust#141032. Calling `get` on the inner `Vec` never returns `Some` as the `Vec`'s length is temporarily set to zero while the `ExtractIf` exists.
Turn `Cow::is_borrowed,is_owned` into associated functions.
This is done because `Cow` implements `Deref`. Therefore, to avoid conflicts with an inner type having a method of the same name, we use an associated method, like `Box::into_raw`.
Tracking issue: #65143
