| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
Our `Cursor::peek_prev` and `CursorMut::peek_prev` must agree
on how to behave when they are called on the "null element".
|
|
Make sure that some stdlib method signatures aren't accidental refinements
In the process of implementing https://rust-lang.github.io/rfcs/3245-refined-impls.html, I found a bunch of stdlib implementations that accidentally "refined" their method signatures by dropping (unnecessary) bounds.
This isn't currently a problem, but may become one if/when method signature refining is stabilized in the future. Shouldn't hurt to make these signatures a bit more accurate anyways.
NOTE (just to be clear lol): This does not affect behavior at all, since we don't actually take advantage of refined implementations yet!
|
|
|
|
|
|
Remove some unneeded imports / qualified paths
Continuation of #105537.
|
|
|
|
|
|
Implement Default for some alloc/core iterators
Add `Default` impls to the following collection iterators:
* slice::{Iter, IterMut}
* binary_heap::IntoIter
* btree::map::{Iter, IterMut, Keys, Values, Range, IntoIter, IntoKeys, IntoValues}
* btree::set::{Iter, IntoIter, Range}
* linked_list::IntoIter
* vec::IntoIter
and these adapters:
* adapters::{Chain, Cloned, Copied, Rev, Enumerate, Flatten, Fuse, Rev}
For iterators which are generic over allocators it only implements it for the global allocator because we can't conjure an allocator from nothing or would have to turn the allocator field into an `Option` just for this change.
These changes will be insta-stable.
ACP: https://github.com/rust-lang/libs-team/issues/77
|
|
|
|
Global implements Default so we can use that as bound for all allocators
|
|
|
|
This way one can `mem::take()` them out of structs or #[derive(Default)] on structs containing them.
These changes will be insta-stable.
|
|
|
|
This is a prerequisite for cursor support for `BTreeMap`.
|
|
|
|
Test leaking of BinaryHeap Drain iterators
Add test cases about forgetting the `BinaryHeap::Drain` iterator, and slightly fortifies some other test cases.
Consists of separate commits that I don't think are relevant on their own (but I'll happily turn these into more PRs if desired).
|
|
|
|
Bump bootstrap compiler to 1.66
This PR:
- Bumps version placeholders to release
- Bumps to latest beta
- cfg-steps code
r? `@pietroalbini`
|
|
|
|
|
|
|
|
Stabilize map_first_last
Stabilizes the following functions:
```Rust
impl<T> BTreeSet<T> {
pub fn first(&self) -> Option<&T> where T: Ord;
pub fn last(&self) -> Option<&T> where T: Ord;
pub fn pop_first(&mut self) -> Option<T> where T: Ord;
pub fn pop_last(&mut self) -> Option<T> where T: Ord;
}
impl<K, V> BTreeMap<K, V> {
pub fn first_key_value(&self) -> Option<(&K, &V)> where K: Ord;
pub fn last_key_value(&self) -> Option<(&K, &V)> where K: Ord;
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord;
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord;
pub fn pop_first(&mut self) -> Option<(K, V)> where K: Ord;
pub fn pop_last(&mut self) -> Option<(K, V)> where K: Ord;
}
```
Closes #62924
~~Blocked on the [FCP](https://github.com/rust-lang/rust/issues/62924#issuecomment-1179489929) finishing.~~ Edit: It finished!
|
|
|
|
|
|
|
|
|
|
Since `len` and `is_empty` are not const stable yet, this also
creates a new feature for them since they previously used the same
`const_btree_new` feature.
|
|
The doc link from `DedupSortedIter` to `BTreeMap::bulk_build_from_sorted_iter` was broken when building internal documentation,
|
|
BTree: evaluate static type-related check at compile time
`assert`s like the ones replaced here would only go off when you run the right test cases, if the code were ever incorrectly changed such that rhey would trigger. But [inspired on a nice forum question](https://users.rust-lang.org/t/compile-time-const-generic-parameter-check/69202), they can be checked at compile time.
|
|
|
|
closes #99408
|
|
|
|
|
|
|
|
|
|
|
|
Entry and_modify doc
This PR modifies the documentation for [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html#) and [BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#) by introducing examples for `and_modify`. `and_modify` is a function that tends to give more idiomatic rust code when dealing with these data structures -- yet it lacked examples and was hidden away. This PR adds that and addresses #98122.
I've made some choices which I tried to explain in my commits. This is my first time contributing to rust, so hopefully, I made the right choices.
|
|
Incorrectly wrote "1" twice when writing test.
|
|
Updated the btree's documentation to include two references to
add_modify.
The first is when the `Entry` API is mentioned at the beginning. With
the same reasoning as HashMap's documentation, I thought it would best
to keep `attack`, but show the `mana` example.
The second is with the `entry` function that is used for the `Entry`
API. The code example was a perfect use for `add_modify`, which is why
it was changed to reflect that.
|
|
|
|
|
|
BTree: tweak internal comments
|
|
|
|
|
|
|
|
Co-authored-by: lcnr <rust@lcnr.de>
|
|
As currently written, when a logic error occurs in a collection's trait
parameters, this allows *completely arbitrary* misbehavior, so long as
it does not cause undefined behavior in std. However, because the extent
of misbehavior is not specified, it is allowed for *any* code in std to
start misbehaving in arbitrary ways which are not formally UB; consider
the theoretical example of a global which gets set on an observed logic
error. Because the misbehavior is only bound by not resulting in UB from
safe APIs and the crate-level encapsulation boundary of all of std, this
makes writing user unsafe code that utilizes std theoretically
impossible, as it now relies on undocumented QOI that unrelated parts of
std cannot be caused to misbehave by a misuse of std::collections APIs.
In practice, this is a nonconcern, because std has reasonable QOI and an
implementation that takes advantage of this freedom is essentially a
malicious implementation and only compliant by the most langauage-lawyer
reading of the documentation.
To close this hole, we just add a small clause to the existing logic
error paragraph that ensures that any misbehavior is limited to the
collection which observed the logic error, making it more plausible to
prove the soundness of user unsafe code.
This is not meant to be formal; a formal refinement would likely need to
mention that values derived from the collection can also misbehave after a
logic error is observed, as well as define what it means to "observe" a
logic error in the first place. This fix errs on the side of informality
in order to close the hole without complicating a normal reading which
can assume a reasonable nonmalicious QOI.
See also [discussion on IRLO][1].
[1]: https://internals.rust-lang.org/t/using-std-collections-and-unsafe-anything-can-happen/16640
|
|
This accomplishes two main goals:
- Make it clear who is responsible for prefix-freedom, including how they should do it
- Make it feasible for a `Hasher` that *doesn't* care about Hash-DoS resistance to get better performance by not hashing lengths
This does not change rustc-hash, since that's in an external crate, but that could potentially use it in future.
|
|
|
