| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
|
|
BTree: move blocks around in node.rs
Without changing any names or implementation, reorder some members:
- Move down the ones defined long ago on the demised `struct Root`, to below the definition of their current host `struct NodeRef`.
- Move up some defined on `struct NodeRef` that are interspersed with those defined on `struct Handle`.
- Move up the `correct_…` methods squeezed between the two flavours of `push`.
- Move the unchecked static downcasts (`cast_to_…`) after the upcasts (`forget_`) and the (weirdly named) dynamic downcasts (`force`).
r? ````@Mark-Simulacrum````
|
|
r=Mark-Simulacrum
BTree: no longer search arrays twice to check Ord
A possible addition to / partial replacement of #83147: no longer linearly search the upper bound of a range in the initial portion of the keys we already know are below the lower bound.
- Should be faster: fewer key comparisons at the cost of some instructions dealing with offsets
- Makes code a little more complicated.
- No longer detects ill-defined `Ord` implementations, but that wasn't a publicised feature, and was quite incomplete, and was only done in the `range` and `range_mut` methods.
r? `@Mark-Simulacrum`
|
|
|
|
Clarify BTree `range_search` comments
These comments were added by #81169. However, the soundness issue [might not be exploitable here](https://github.com/rust-lang/rust/pull/81169#issuecomment-765271717), so the comments should be updated.
cc `@ssomers`
|
|
Add more links between hash and btree collections
- Link from `core::hash` to `HashMap` and `HashSet`
- Link from HashMap and HashSet to the module-level documentation on
when to use the collection
- Link from several collections to Wikipedia articles on the general
concept
See also https://github.com/rust-lang/rust/pull/81989#issuecomment-783920840.
|
|
|
|
|
|
|
|
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
|
|
Implement NOOP_METHOD_CALL lint
Implements the beginnings of https://github.com/rust-lang/lang-team/issues/67 - a lint for detecting noop method calls (e.g, calling `<&T as Clone>::clone()` when `T: !Clone`).
This PR does not fully realize the vision and has a few limitations that need to be addressed either before merging or in subsequent PRs:
* [ ] No UFCS support
* [ ] The warning message is pretty plain
* [ ] Doesn't work for `ToOwned`
The implementation uses [`Instance::resolve`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/instance/struct.Instance.html#method.resolve) which is normally later in the compiler. It seems that there are some invariants that this function relies on that we try our best to respect. For instance, it expects substitutions to have happened, which haven't yet performed, but we check first for `needs_subst` to ensure we're dealing with a monomorphic type.
Thank you to ```@davidtwco,``` ```@Aaron1011,``` and ```@wesleywiser``` for helping me at various points through out this PR ❤️.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
BTree: fix untrue safety
Fix needless and missing `unsafe` tags.
r? ````@Mark-Simulacrum````
|
|
Add some diagnostic items for Clippy
|
|
BTreeMap: correct node size test case for choices of B
r? `@Mark-Simulacrum`
|
|
|
|
BTree: no longer define impossible casts
Casts to leaf to internal only make sense when the original has a chance of being the thing it's cast to.
r? `@Mark-Simulacrum`
|
|
BTreeMap: split up range_search into two stages
`range_search` expects the caller to pass the same root twice and starts searching a node for both bounds of a range. It's not very clear that in the early iterations, it searches twice in the same node. This PR splits that search up in an initial `find_leaf_edges_spanning_range` that postpones aliasing until the last second, and a second phase for continuing the search for the range in the each subtree independently (`find_lower_bound_edge` & `find_upper_bound_edge`), which greatly helps for use in #81075. It also moves those functions over to the search module.
r? `@Mark-Simulacrum`
|
|
Almost all safety comments are of the form `// SAFETY:`,
so normalize the rest and fix a few of them that should
have been a `/// # Safety` section instead.
Furthermore, make `tidy` only allow the uppercase form. While
currently `tidy` only checks `core`, it is a good idea to prevent
`core` from drifting to non-uppercase comments, so that later
we can start checking `alloc` etc. too.
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
|
|
|
|
|
|
|
|
- Link from `core::hash` to `HashMap` and `HashSet`
- Link from HashMap and HashSet to the module-level documentation on
when to use the collection
- Link from several collections to Wikipedia articles on the general
concept
|
|
BTree: move more shared iterator code into navigate.rs
The functions in navigate.rs only exist to support iterators, and these look easier on my eyes if there is a shared `struct` with the recurring pair of handles.
r? `@Mark-Simulacrum`
|
|
BTreeMap: gather and decompose reusable tree fixing functions
This is kind of pushing it as a standalone refactor, probably only useful for #81075 (or similar).
r? `@Mark-Simulacrum`
|
|
|
|
BTree: share panicky test code & test panic during clear, clone
Bases almost all tests of panic on the same, richer definition, and extends it to cloning to test panic during clone.
r? ```@Mark-Simulacrum```
|
|
Fix typos in BTreeSet::{first, last} docs
map -> set
|
|
|
|
BTreeMap: fix internal comments
Salvaged from #81372
r? `@Mark-Simulacrum`
|
|
BTree: remove outdated traces of coercions
The introduction of `marker::ValMut` (#75200) meant iterators no longer see mutable keys but their code still pretends it does. And settle on the majority style `Some(unsafe {…})` over `unsafe { Some(…) }`.
r? `@Mark-Simulacrum`
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
BTreeMap: lightly refactor the split_off implementation
r? `@Mark-Simulacrum`
|
|
BTree: remove Ord bound where it is absent elsewhere
Some btree methods don't really need an Ord bound and don't have one, while some methods that more obviously don't need it, do have one.
An example of the former is `iter`, even though it explicitly exposes the work of the Ord implementation (["sorted by key"](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.iter) - but I'm not suggesting it should have the Ord bound). An example of the latter is `new`, which doesn't involve any keys whatsoever.
|
|
btree: use Option's unwrap_unchecked()
Now that https://github.com/rust-lang/rust/issues/81383 is available, start using it.
|
|
BTree: fix documentation of unstable public members
As rightfully requested in #62924 & #70530.
r? `@Mark-Simulacrum`
|
