Tracking Issue for get_many_mut

[Mark-Simulacrum]

Feature gate: #![feature(get_many_mut)]

This is a tracking issue for get_many_mut and get_many_unchecked_mut, which provide &mut T access to multiple distinct slice elements.

Public API

impl [T] {
    pub unsafe fn get_many_unchecked_mut<const N: usize>(&mut self, indices: [usize; N]) -> [&mut T; N];
    pub fn get_many_mut<const N: usize>(&mut self, indices: [usize; N]) -> Result<[&mut T; N], GetManyMutError<N>>;
}

pub struct GetManyMutError<const N: usize> { /* private */ }

Steps / History

• Implementation:
  • Initial implementation in Add slice methods for indexing via an array of indices. #83608, also received extensive discussion
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• What should the error type / return type look like?
  • See Add slice methods for indexing via an array of indices. #83608 (comment), Add slice methods for indexing via an array of indices. #83608 (comment), and other comments on that PR
• Should the interface support non-usize indices (e.g., get_many_mut([0..3, 4..6]))?
• What are the requirements for the interface? Do we sort the passed array, and then check distinctness, or check in O(n^2) time?

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[shepmaster]

Is there a reason that core::slice::GetManyMutError isn't re-exported as std::slice::GetManyMutError?

[orlp]

Since N is a compile-time constant anyway I would suggest adding a check in get_many_check_valid that switches to sort_unstable for, say, N > 10. This code gets optimized out entirely for N <= 10, and vice versa.

fn get_many_check_valid<const N: usize>(indices: &[usize; N], len: usize) -> bool {
    let mut valid = true;
    if N <= 10 {
        // NB: The optimzer should inline the loops into a sequence
        // of instructions without additional branching.
        for (i, &idx) in indices.iter().enumerate() {
            valid &= idx < len;
            for &idx2 in &indices[..i] {
                valid &= idx != idx2;
            }
        }
    } else {
        let mut sorted = *indices;
        sorted.sort_unstable();
        for i in 1..N {
            valid &= sorted[i-1] < sorted[i];
        }
        valid &= sorted[N-1] < len;
    }

    valid
}

On another note, perhaps we should have a DisjointIndices<const N: usize> type where DisjointIndices::new calls get_many_check_valid. Then indexing with DisjointIndices does not need to repeat the check, allowing you to amortize the cost of checking disjointness over many operations without needing unsafe code. This type could also have a DisjointIndices::new_sorted constructor that allows the user to make the disjoint check faster if they know their input indices are sorted.

[ajwock]

I also like the idea of DisjointedIndices for this. And since a pair of indices is likely a common use case for this, perhaps something that could be available would be something like disjoint_pair(lhs: usize, rhs: usize) -> DisjointIndices<2> (panics if lhs == rhs).

[pervognsen]

I've tried to use this a few times now. The fact that the current placeholder error type doesn't distinguish out-of-bounds vs duplicate indices makes it hard to even test in something resembling a real use case. For example, if you wanted to implement slice::swap via slice::get_many_mut (not saying you should), you'd want the duplicate index case to be a nop, but you'd still want the out-of-bounds case to panic. A lot of my hypothetical use cases for get_many_mut have this "multi-object transaction" flavor to them.

Related: Would it make sense to have an implementation of IndexMut for [usize; N] that panics in the duplicates case? The duplicate indices issue seems like it falls into the same bucket of dynamic borrow conflicts you have with RefCell::borrow/borrow_mut (which panics unlike try_borrow/try_borrow_mut), so it seems like a reasonable behavior when you have an upstream invariant that is expected to guarantee uniqueness but you still need the dynamic check for safety.

Splitting the duplicate checking via a DisjointIndices type seems to help with some of these issues as well. In the case of get_many_mut, it means you only have one type of error (out of bounds) as with the plain get method. And if we eventually end up with all these related APIs (e.g. Index and IndexMut can be implemented for DisjointIndices), the stage separation of disjoint index handling helps to eliminate redundancy in both the implementation and interfaces (e.g. error types). And in the aforementioned case where you have upstream invariants that guarantee uniqueness, it means you can propagate that invariant using a DisjointIndices value as a proof witness. (The proof witness idea also works for bounds checking. It doesn't make much sense for a singular index with a known bound since that known bound must still be checked against the slice length, but once you have multiple indices packaged together with a known bound it means you can get away with only one bounds check against the slice length instead of one for each index.)

[kupiakos]

For embedded use cases, I'd strongly prefer we limit the number of panics added by this feature, limiting it only to out-of-bounds as it is today.

Would it make sense to have an implementation of IndexMut for [usize; N] that panics in the duplicates case?

There's not really a way to implement IndexMut for multiple indices - what would be the Output type? If the Output type is [&mut T] then you would need some place to store it for index_mut to return &mut Self::Output.

The same applies to .get_mut - it would be awesome to write let [e0, e10] = foo.get_mut(DisjointIndices::new([1,2]).unwrap()) but there's no way to do it. If we'd had GATs from the beginning then Index could've been type Output<'a>; and indexing would be far more powerful.

[mcmah309]

There is also this crate that introduces some macros and methods for retrieving multiple mutable indices from a mutable slice https://crates.io/crates/indices . It uses insertion sort so more optimized towards a small number of indices and near sorted indices. It also has macros that assume the input is already sorted, requiring no sorting at all.

[tgross35]

If there isn't any specific reason not to do this, I think we should change to an interface based on SliceIndex. This is consistent with get{,_mut} and should make ranges work. It should also be more compatible with using smaller integer types to index into slices, if we ever get that to work.

fn get_many_mut<I, const N: usize>(
    &mut self,
    indices: [I; N],
) -> Result<[&mut <I as SliceIndex<[T]>>::Output; N], GetManyMutError<N>>
where
    // If we switch to using `DisjointIndices` as suggested above, `Ord` is not
    // needed here.
    I: SliceIndex<[T]> + Ord
{ /* ... */ }

Cc @ChayimFriedman2 since you have a stabilization PR up.

[scottmcm]

If it's going to go through a trait, should it perhaps be indices: I?

That would leave space open to also allow things like get_many_mut((..4, 4, 5..)) in future, should we decide to allow it.

[tguichaoua]

That would leave space open to also allow things like get_many_mut((..4, 4, 5..)) in future, should we decide to allow it.

I make a POC to experiment with this idea.

[Amanieu]

We discussed this in the libs-api meeting yesterday and concluded that we are mostly happy with the shape that the API has today. We would like it to be extended to support any index that implements SliceIndex. We are deferring on tuple support for now.

[scottmcm]

• What are the requirements for the interface? Do we sort the passed array, and then check distinctness, or check in O(n^2) time?

Attempting to answer this based on what I half-remember from the meeting:

The 99% case here is 2 (or maybe 3) indices. As such, there's should not be a requirement that they're sorted, and there's no need to do optimizations for many-index cases. Someone looking to use a more complicated scenario -- which wants to pre-check disjointness or sortedness of indices, say -- is expected to make their own wrapper around get_many_unchecked_mut, which of course doesn't do any O(n²) checks.

[ChayimFriedman2]

@Amanieu Is the team interested in adding range support now, or deferring it? Also, it may cause inference problems later if we make it generic.

[Amanieu]

Yes, we would like to add range support now.

[ChayimFriedman2]

@Amanieu Implementing this with SliceIndex will make adding support for tuples a breaking change, since users will be able to pass an opaque type that is SliceIndex into get_many_mut(). Nevermind, I found a way around this.

[ChayimFriedman2]

@Amanieu Did you discuss whether the error should include more details?

[Amanieu]

Did you discuss whether the error should include more details?

I'll nominate that for discussion in our next meeting.

[joshtriplett]

We discussed this in today's @rust-lang/libs-api meeting.

We'd like to stabilize this, using the signature that accepts an array of SliceIndex types.

The error should be a two-variant enum (one variant for overlaps and one variant for out-of-bounds) that doesn't carry any data and doesn't have a generic parameter.

@rfcbot merge

[rfcbot]

Team member @joshtriplett has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se

Concerns:

• "many" (Tracking Issue for get_many_mut #104642 (comment))

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[the8472]

We'd like to stabilize this, using the signature that accepts an array of SliceIndex types.

Ah, I thought we were talking about a many_mut(T) where T: ManyIdx here where ManyIdx would be implemented for arrays of ranges and arrays of usizes. Not an many_mut([T;N]) where T: ManyIdx or such.

[rfcbot]

@Amanieu proposal cancelled.

[Amanieu]

@rfcbot merge

[rfcbot]

Team member @Amanieu has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se

Concerns:

• Consider get_disjoint_mut as the name. (Tracking Issue for get_many_mut #104642 (comment))

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[Amanieu]

The error should be a two-variant enum (one variant for overlaps and one variant for out-of-bounds) that doesn't carry any data and doesn't have a generic parameter.

Also note that the error type still needs to be changed as we decided in a previous meeting.

[cuviper]

We discussed this in the libs-api meeting today and decided to change the name to get_multi_mut, which was the least controversial choice.

Was something like get_array_mut considered? Since we are in fact returning an array...

[orlp]

In slotmap this functionality is called get_disjoint_mut to emphasize that the keys must be disjoint. I think this is also an appropriate choice here, the indices must be disjoint.

[m-ou-se]

@rfcbot concern Consider get_disjoint_mut as the name.

[Amanieu]

We discussed this in the libs-api meeting and most of the team preferred get_disjoint_mut for both slices and HashMap. Restarting the FCP again!

@rfcbot cancel

[rfcbot]

@Amanieu proposal cancelled.

[Amanieu]

@rfcbot merge

[rfcbot]

Team member @Amanieu has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.