| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
The previous commit updated `rustfmt.toml` appropriately. This commit is
the outcome of running `x fmt --all` with the new formatting options.
|
|
Many tiny changes to stdlib doc comments to make them consistent (for example
"Returns foo", rather than "Return foo", per RFC1574), adding missing periods, paragraph
breaks, backticks for monospace style, and other minor nits.
https://github.com/rust-lang/rfcs/blob/master/text/1574-more-api-documentation-conventions.md#appendix-a-full-conventions-text
|
|
|
|
warning: casting raw pointers to the same type and constness is unnecessary (`*mut V` -> `*mut V`)
--> library\alloc\src\collections\btree\map\entry.rs:357:31
|
357 | let val_ptr = root.borrow_mut().push(self.key, value) as *mut V;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `root.borrow_mut().push
(self.key, value)`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting to the same type is unnecessary (`usize` -> `usize`)
--> library\alloc\src\ffi\c_str.rs:411:56
|
411 | let slice = slice::from_raw_parts_mut(ptr, len as usize);
| ^^^^^^^^^^^^ help: try: `len`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting raw pointers to the same type and constness is unnecessary (`*mut T` -> `*mut T`)
--> library\alloc\src\slice.rs:516:25
|
516 | (buf.as_mut_ptr() as *mut T).add(buf.len()),
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `buf.as_mut_ptr()`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting raw pointers to the same type and constness is unnecessary (`*mut T` -> `*mut T`)
--> library\alloc\src\slice.rs:537:21
|
537 | (buf.as_mut_ptr() as *mut T).add(buf.len()),
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `buf.as_mut_ptr()`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting raw pointers to the same type and constness is unnecessary (`*const ()` -> `*const ()`)
--> library\alloc\src\task.rs:151:13
|
151 | waker as *const (),
| ^^^^^^^^^^^^^^^^^^ help: try: `waker`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting raw pointers to the same type and constness is unnecessary (`*const ()` -> `*const ()`)
--> library\alloc\src\task.rs:323:13
|
323 | waker as *const (),
| ^^^^^^^^^^^^^^^^^^ help: try: `waker`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting to the same type is unnecessary (`usize` -> `usize`)
--> library\std\src\sys_common\net.rs:110:21
|
110 | assert!(len as usize >= mem::size_of::<c::sockaddr_in>());
| ^^^^^^^^^^^^ help: try: `len`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
warning: casting to the same type is unnecessary (`usize` -> `usize`)
--> library\std\src\sys_common\net.rs:116:21
|
116 | assert!(len as usize >= mem::size_of::<c::sockaddr_in6>());
| ^^^^^^^^^^^^ help: try: `len`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
|
|
Help with common API confusion, like asking for `push` when the data structure really has `append`.
```
error[E0599]: no method named `size` found for struct `Vec<{integer}>` in the current scope
--> $DIR/rustc_confusables_std_cases.rs:17:7
|
LL | x.size();
| ^^^^
|
help: you might have meant to use `len`
|
LL | x.len();
| ~~~
help: there is a method with a similar name
|
LL | x.resize();
| ~~~~~~
```
#59450
|
|
Rewrite the BTreeMap cursor API using gaps
Tracking issue: #107540
Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use.
This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning.
The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation.
API summary:
```rust
impl<K, V> BTreeMap<K, V> {
fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
}
struct Cursor<'a, K: 'a, V: 'a>;
impl<'a, K, V> Cursor<'a, K, V> {
fn next(&mut self) -> Option<(&'a K, &'a V)>;
fn prev(&mut self) -> Option<(&'a K, &'a V)>;
fn peek_next(&self) -> Option<(&'a K, &'a V)>;
fn peek_prev(&self) -> Option<(&'a K, &'a V)>;
}
struct CursorMut<'a, K: 'a, V: 'a>;
impl<'a, K, V> CursorMut<'a, K, V> {
fn next(&mut self) -> Option<(&K, &mut V)>;
fn prev(&mut self) -> Option<(&K, &mut V)>;
fn peek_next(&mut self) -> Option<(&K, &mut V)>;
fn peek_prev(&mut self) -> Option<(&K, &mut V)>;
unsafe fn insert_after_unchecked(&mut self, key: K, value: V);
unsafe fn insert_before_unchecked(&mut self, key: K, value: V);
fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>;
fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>;
fn remove_next(&mut self) -> Option<(K, V)>;
fn remove_prev(&mut self) -> Option<(K, V)>;
fn as_cursor(&self) -> Cursor<'_, K, V>;
unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>;
}
struct CursorMutKey<'a, K: 'a, V: 'a>;
impl<'a, K, V> CursorMut<'a, K, V> {
fn next(&mut self) -> Option<(&mut K, &mut V)>;
fn prev(&mut self) -> Option<(&mut K, &mut V)>;
fn peek_next(&mut self) -> Option<(&mut K, &mut V)>;
fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>;
unsafe fn insert_after_unchecked(&mut self, key: K, value: V);
unsafe fn insert_before_unchecked(&mut self, key: K, value: V);
fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>;
fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>;
fn remove_next(&mut self) -> Option<(K, V)>;
fn remove_prev(&mut self) -> Option<(K, V)>;
fn as_cursor(&self) -> Cursor<'_, K, V>;
unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>;
}
struct UnorderedKeyError;
```
|
|
detects redundant imports that can be eliminated.
for #117772 :
In order to facilitate review and modification, split the checking code and
removing redundant imports code into two PR.
|
|
|
|
Tracking issue: #107540
Currently, a `Cursor` points to a single element in the tree, and allows
moving to the next or previous element while mutating the tree. However
this was found to be confusing and hard to use.
This PR completely refactors cursors to instead point to a gap between
two elements in the tree. This eliminates the need for a "ghost" element
that exists after the last element and before the first one.
Additionally, `upper_bound` and `lower_bound` now have a much clearer
meaning.
The ability to mutate keys is also factored out into a separate
`CursorMutKey` type which is unsafe to create. This makes the API easier
to use since it avoids duplicated versions of each method with and
without key mutation.
API summary:
```rust
impl<K, V> BTreeMap<K, V> {
fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord;
}
struct Cursor<'a, K: 'a, V: 'a>;
impl<'a, K, V> Cursor<'a, K, V> {
fn next(&mut self) -> Option<(&'a K, &'a V)>;
fn prev(&mut self) -> Option<(&'a K, &'a V)>;
fn peek_next(&self) -> Option<(&'a K, &'a V)>;
fn peek_prev(&self) -> Option<(&'a K, &'a V)>;
}
struct CursorMut<'a, K: 'a, V: 'a>;
impl<'a, K, V> CursorMut<'a, K, V> {
fn next(&mut self) -> Option<(&K, &mut V)>;
fn prev(&mut self) -> Option<(&K, &mut V)>;
fn peek_next(&mut self) -> Option<(&K, &mut V)>;
fn peek_prev(&mut self) -> Option<(&K, &mut V)>;
unsafe fn insert_after_unchecked(&mut self, key: K, value: V);
unsafe fn insert_before_unchecked(&mut self, key: K, value: V);
fn insert_after(&mut self, key: K, value: V);
fn insert_before(&mut self, key: K, value: V);
fn remove_next(&mut self) -> Option<(K, V)>;
fn remove_prev(&mut self) -> Option<(K, V)>;
fn as_cursor(&self) -> Cursor<'_, K, V>;
unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>;
}
struct CursorMutKey<'a, K: 'a, V: 'a>;
impl<'a, K, V> CursorMut<'a, K, V> {
fn next(&mut self) -> Option<(&mut K, &mut V)>;
fn prev(&mut self) -> Option<(&mut K, &mut V)>;
fn peek_next(&mut self) -> Option<(&mut K, &mut V)>;
fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>;
unsafe fn insert_after_unchecked(&mut self, key: K, value: V);
unsafe fn insert_before_unchecked(&mut self, key: K, value: V);
fn insert_after(&mut self, key: K, value: V);
fn insert_before(&mut self, key: K, value: V);
fn remove_next(&mut self) -> Option<(K, V)>;
fn remove_prev(&mut self) -> Option<(K, V)>;
fn as_cursor(&self) -> Cursor<'_, K, V>;
unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>;
}
```
|
|
|
|
#[must_use]
|
|
|
|
Our `Cursor::peek_prev` and `CursorMut::peek_prev` must agree
on how to behave when they are called on the "null element".
|
|
Remove some unneeded imports / qualified paths
Continuation of #105537.
|
|
|
|
|
|
|
|
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).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
BTreeMap::entry: Avoid allocating if no insertion
This PR allows the `VacantEntry` to borrow from an empty tree with no root, and to lazily allocate a new root node when the user calls `.insert(value)`.
|
|
This updates the standard library's documentation to use the new syntax. The
documentation is worthwhile to update as it should be more idiomatic
(particularly for features like this, which are nice for users to get acquainted
with). The general codebase is likely more hassle than benefit to update: it'll
hurt git blame, and generally updates can be done by folks updating the code if
(and when) that makes things more readable with the new format.
A few places in the compiler and library code are updated (mostly just due to
already having been done when this commit was first authored).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
BTree: toughen panicky test of clone()
Test did not cover the second half of `clone_subtree` and why this clones key & value first.
|
|
|
|
|
|
|
|
Stabilize `impl From<[(K, V); N]> for HashMap` (and friends)
In addition to allowing HashMap to participate in Into/From conversion, this adds the long-requested ability to use constructor-like syntax for initializing a HashMap:
```rust
let map = HashMap::from([
(1, 2),
(3, 4),
(5, 6)
]);
```
This addition is highly motivated by existing precedence, e.g. it is already possible to similarly construct a Vec from a fixed-size array:
```rust
let vec = Vec::from([1, 2, 3]);
```
...and it is already possible to collect a Vec of tuples into a HashMap (and vice-versa):
```rust
let vec = Vec::from([(1, 2)]);
let map: HashMap<_, _> = vec.into_iter().collect();
let vec: Vec<(_, _)> = map.into_iter().collect();
```
...and of course it is likewise possible to collect a fixed-size array of tuples into a HashMap ([but not vice-versa just yet](https://github.com/rust-lang/rust/issues/81615)):
```rust
let arr = [(1, 2)];
let map: HashMap<_, _> = std::array::IntoIter::new(arr).collect();
```
Therefore this addition seems like a no-brainer.
As for any impl, this would be insta-stable.
|
|
|
|
|
|
|
|
Add {BTreeMap,HashMap}::try_insert
`{BTreeMap,HashMap}::insert(key, new_val)` returns `Some(old_val)` if the key was already in the map. It's often useful to assert no duplicate values are inserted.
We experimented with `map.insert(key, val).unwrap_none()` (https://github.com/rust-lang/rust/issues/62633), but decided that that's not the kind of method we'd like to have on `Option`s.
`insert` always succeeds because it replaces the old value if it exists. One could argue that `insert()` is never the right method for panicking on duplicates, since already handles that case by replacing the value, only allowing you to panic after that already happened.
This PR adds a `try_insert` method that instead returns a `Result::Err` when the key already exists. This error contains both the `OccupiedEntry` and the value that was supposed to be inserted. This means that unwrapping that result gives more context:
```rust
map.insert(10, "world").unwrap_none();
// thread 'main' panicked at 'called `Option::unwrap_none()` on a `Some` value: "hello"', src/main.rs:8:29
```
```rust
map.try_insert(10, "world").unwrap();
// thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value:
// OccupiedError { key: 10, old_value: "hello", new_value: "world" }', src/main.rs:6:33
```
It also allows handling the failure in any other way, as you have full access to the `OccupiedEntry` and the value.
`try_insert` returns a reference to the value in case of success, making it an alternative to `.entry(key).or_insert(value)`.
r? ```@Amanieu```
Fixes https://github.com/rust-lang/rfcs/issues/3092
|
