Tracking Issue for `vec::Drain{,Filter}::keep_rest`

[WaffleLapkin]

Feature gate: #![feature(drain_keep_rest)]

This is a tracking issue for vec::Drain::keep_rest, methods allowing to keep elements in a Vec after draining some of them.

Public API

// mod alloc::vec

impl<T, A: Allocator> Drain<'_, T, A> {
    pub fn keep_rest(self);
}

Steps / History

• Implementation: Add vec::Drain{,Filter}::keep_rest #95376
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• Just change the not-yet-stable Drop for DrainFilter to keep rest?
  • Advantage: usually what you want (??)
    • e.g. .drain_filter(f).take(N) works as expected
  • Disadvantage: inconsistent with stable Drop for Drain
  • If you want to remove rest (matching the current unstable behavior of drain_filter) then you'd need to write .foreach(drop) to explicitly drop all the rest of the range that matches the filter.
• &mut self instead of self?
  • If you're holding a Drain inside a struct and are operating on it from a &mut self method of the struct, keep_rest(self) is impossible to use. :(
    • You'd want something like mem::replace(&mut self.drain_filter, Vec::new().drain(..)).keep_rest() but the borrow checker won't like that.
    • Failing that, you'd need to change your Drain field to Option<Drain> and use self.drain_filter.take().unwrap().keep_rest() along with unwrap() everywhere else that the drain is used. Not good.
  • We'd need to define behavior of calling .next() after .keep_rest(). Presumably one of:
    • .next() returns None
    • this is considered incorrect usage and so .next() panic!s
    • .keep_rest() sets a flag inside the Drain which Drop will use to decide its behavior, and you're free to continue accessing iterator elements in between.
  • Another alternative: add a const EXHAUST_ON_DROP: bool = true const generic parameter
    • It's still impossible to set the flag without ownership
    • You can store &mut Drain<'a, T, A, false> from the beginning
    • Works better with iterator APIs, i.e.

      vec.drain_filter(f).keeping_rest().take(N).for_each(g);

      Instead of

      let mut iter = vec.drain_filter(f);
      iter.by_ref().take(N).for_each(g);
      iter.keep_rest()

Footnotes

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

[RustyYato]

Why was this closed? The feature is still in nightly according to the docs, https://doc.rust-lang.org/1.78.0/std/vec/struct.Drain.html#method.keep_rest

Is there a separate ticket for Drain specifically? If not, is there some way to stabilize keep_rest?

[RustyYato]

On one of the unresolved issues:

Just change the not-yet-stable Drop for DrainFilter to keep rest?

This is now no longer unresolved, as it was handled in #104455

Another alternative: add a const EXHAUST_ON_DROP: bool = true const generic parameter

It's still impossible to set the flag without ownership
You can store &mut Drain<'a, T, A, false> from the beginning
Works better with iterator APIs, i.e.

vec.drain_filter(f).keeping_rest().take(N).for_each(g);

I think this is the best option, since it will also work if iteration panics in some way. Setting the flag is equivalent to just having Either< Drain<.., true>, Drain<.., false> > so, I think this is also the most general solution of the bunch that handles panics.

&mut self instead of self?

This would require setting a flag, and also handles panics, but I don't see any reason to set the flag some time after construction. And it's quite easy to add a flag on top of a Drain<..., false> (even if a bit verbose). And could be wrapped in a crate.

struct Drain<'a, T> {
    should_drain_on_drop: bool,
    drain: std::vec::Drain<'a, T, false>, // << with const-generic param to control drop behavior
}

impl<'a, T> Drop for Drain<'a, T> {
    fn drop(&mut self) {
        if self.should_drain_on_drop {
            // optionally user a scope guard to guarantee that all items get dropped, but that's not to hard to add as well
            self.for_each(drop);
        }
    }
}
 
impl Iterator for Drain<'a, T> { /* forward to std::vec::Drain */ }

so this is also easy to do.

So all in all, I think the const-generics approach remains the most flexible, and correct even in the face of panics.

[Amanieu]

We briefly discussed this in the libs-api meeting today. We would like to defer stabilizing this until extract_if is stabilized so that we can get a better picture of whether this is still needed. extract_if already has the behavior of preserving all remaining elements if the iterator is dropped.

[WaffleLapkin]

There is also BinaryHeap::drain_sorted, with the same on drop behavior as drain. Should we replace it by "extract_sorted"?

[Amanieu]

IMO drain_sorted should be changed to just clear the heap directly to avoid calling user code (via Ord) during drop. This avoids any issues with double drops.

[steffahn]

I’d like to make one observation here, so it isn’t possibly missed in the future: (I haven’t seen it mentioned anywhere around here yet)

For vec::Drain, we cannot soundly have both a keep_rest and an as_mut_slice method :-)

The relevant context:

• there was a comment when vec::Drain::as_slice was introduced: Add as_slice() to slice::IterMut and vec::Drain #58924 (comment)
  that stated

  FWIW, these could both support as_mut_slice() too, but I have no immediate use for that. I'm willing to add that for completeness if desired.

• vec::Drain<'a, T[, A]> is covariant in T (compare Make vec::Drain and binary_heap::Drain covariant #34951)
• and of course, vec::Drain::keep_rest is tracked in this issue

So stabilizing keep_rest precludes any future addition of as_mut_slice.

(Either method on its own is fine though; as_mut_slice can work on covariant types, as long as the contained values are fully owned.)

[WaffleLapkin]

@Amanieu even if double drop is not an issue, it can still be desirable to only remove some elements.

[chris-morgan]

I only just learned about Drain::keep_rest, and I want to note a mild concern about it: it breaks longstanding expectations in a way that could allow existing libraries to be broken by unreasonable users. I would expect approximately every place where the concrete type Drain has been used in libraries in the past to have the understanding that the values ceded would not return; but this allows them to return in a way that, at first blush, feels wrong to me.

As a specific example I’ve just been dealing with (but I’ve hit other situations before): in Wayland, graphics tablet tools send a burst of events for a hardware change, so in handling it you can wish to collect the pending events, then when the frame event comes in, you flush the batch.

• If the library gives consumers &[Event], they can’t move certain things out of the events, so that’s not ideal.
• If it gives Vec<Event> (e.g. via std::mem::take(self.pending_frame_events)), allocation efficiency suffers.
• The obvious choice is to use Drain<Event> in some way. The easiest way is to use the concrete type: it tends to only feel like mildly exposing an implementation detail, especially if the alternative you considered was exposing Vec<Event>.
• If you want to encapsulate it, you can use impl Iterator<Item = Event>, but then you’ll want to add something like + DoubleEndedIterator + ExactSizeIterator + FusedIterator + TrustedLen + Send + Sync + AsRef<[Event]> + Debug (and sorry, you lost your nice .as_slice() method) and it gets kinda unwieldy, but if you omit any of it, you’re damaging capabilities.
• Of course, the ultimate future-compatibility-safest way is to wrap Drain and duplicate all its surface area. In the past, that meant literally all—there was nothing you wouldn’t want. And sorry, you’ll need to use unsafe in order to get TrustedLen there.
  But all things considered, just exposing Drain<Event> was often the most practical thing to do.

But now, if you do that, consumers can put items back.

So now I feel that I want to newtype drain and repeat every single thing of its surface area… except keep_rest. And the also-unstable allocator, I guess.

It’s not a big deal, I think, and anyone that actually uses keep_rest when given a Drain of this sort is crazy and emphatically asking for trouble, but it does feel like an important semantic change. It has become possible to misuse such things, where it wasn’t before.

It’s like the drain part of a kitchen sink, which you thought was just a drain that things could flow out of, can pull a plunger out of nowhere, suck stuff back up into the sink, and slide a hidden plug into place to keep it there against your will. (At least it’s not full-on backflow, a sewage nightmare!)

I just wanted to record this mild discomfort that I have about this method. It feels a little bit wrong to me.