truncate_front API for VecDeque that is O(1) for trivial drop types

[vkrivopalov]

Proposal

Problem statement

VecDeque is designed as a symmetric data structure with API available for operations on both ends of a double-ended queue.
Currently, VecDeque supports the truncate() method that can be used to reduce the size of a container by dropping elements at its end and provides a O(1) guarantee for trivial drop types, but does not provide a counterpart for doing the same by dropping elements at the beginning.

Motivating examples or use cases

Today, it is possible to implement a O(log N) solution for a sorted VecDeque<u32> that drops all elements larger than x by combining binary_search() and truncate() functions. However, it is not possible to do so to drop all elements smaller than x except by popping then one-by-one which is O(N):

use std::collections::VecDeque;

fn drop_all_less_than(deque: &mut VecDeque<u32>, value: u32) {
   let pos = match deque.binary_search(&value) {
       Ok(pos) => pos,
       Err(pos) => pos,
   };
   
   for _ in 0..pos {
       deque.pop_front();
   }
}

fn main() {
    let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    drop_all_less_than(&mut deque, 4);
    assert_eq!(deque, [5, 8, 13, 21, 34, 55]);
}

Implementing truncate_front() API with same runtime guarantees as truncate() would close this gap and maintain consistency in VecDeque symmetric programming interface.

Solution sketch

The implementation can look very similar to truncate() but operate on slices in the opposite order:

  pub fn truncate_front(&mut self, len: usize) {
      /// Runs the destructor for all items in the slice when it gets dropped (normally or
      /// during unwinding).
      struct Dropper<'a, T>(&'a mut [T]);

      impl<'a, T> Drop for Dropper<'a, T> {
          fn drop(&mut self) {
              unsafe {
                  ptr::drop_in_place(self.0);
              }
          }
      }

      unsafe {
          if len >= self.len {
              // No action is taken
              return;
          }

          let (front, back) = self.as_mut_slices();
          if len > back.len() {
              // The 'back' slice remains unchanged.
              // front.len() + back.len() == self.len, so 'end' is non-negative
              // and end < front.len()
              let end = front.len() - (len - back.len());
              let drop_front = front.get_unchecked_mut(..end) as *mut _;
              self.head += end;
              self.len = len;
              ptr::drop_in_place(drop_front);
          } else {
              let drop_front = front as *mut _;
              // 'end' is non-negative by the condition above
              let end = back.len() - len;
              let drop_back = back.get_unchecked_mut(..end) as *mut _;
              self.head = self.to_physical_idx(self.len - len);
              self.len = len;

              // Make sure the second half is dropped even when a destructor
              // in the first one panics.
              let _back_dropper = Dropper(&mut *drop_back);
              ptr::drop_in_place(drop_front);
          }
      }
  }

The common code for safely dropping the drop_back slice in the second branch is the same as in truncate() and can be factored out into a separate helper.

Alternatives

1. It is possible to use drain() to get an iterator over elements that need to be dropped in the front and drop it instantly:

   let pos = drop_all_elements_before_this_position(&deque); // usize
   deque.drain(0..pos);

This seems to accomplish the goal but is arguably less intuitive and more complex internally.

2. A VecDeque can be split in two with split_off():

let deque = deque.split_off(pos);

but that would incur an extra allocation,

3. A VecDeque can be rotated with rotate_left() and then truncated with truncate():

   deque.rotate_left(pos);
   deque.truncate(deque.len() - pos);

but that still has linear complexity: O(min(n, len() - n))

Links and related work

The need for truncate_front() has been expressed by a number of Rust developers and discussed in the following GitHub issues:
rust-lang/rust#62408
rust-lang/rust#92547

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[joshtriplett]

We discussed this in today's @rust-lang/libs-api meeting. We had a consensus to accept this with the proposed name truncate_front.

The documentation should make it clear that the argument is the number of elements to keep, not the number of elements to remove. (That's the same as truncate.)