VecDeque: collecting an exhausted vec::IntoIter yields head == capacity, later failing wrap_index's debug assertion

[jrey8343]

Collecting an exhausted vec::IntoIter into a VecDeque goes through vec::IntoIter::into_vecdeque, which passes initialized = ptr.offset_from_unsigned(buf)..end.offset_from_unsigned(buf) to VecDeque::from_contiguous_raw_parts_in. When the original Vec had capacity() == len() (e.g. vec![1, 2, 3]) and every element was consumed, that range is capacity..capacity, so the resulting deque has head == capacity (with len == 0). The field documentation on VecDeque says

// `head < buf.capacity()`, unless `buf.capacity() == 0` when `head == 0`.
head: usize,

so this is a state outside the documented invariant. It is mostly harmless because wrap_index maps head + i with head == capacity onto i, but once the deque is filled back up to len == capacity without reallocating, any path that computes to_physical_idx(len) evaluates wrap_index(2 * capacity, capacity), whose debug_assert! requires logical_index - capacity < capacity. With a standard library built with debug assertions this panics; in release builds wrap_index returns capacity and the callers I looked at handle it (e.g. write_iter_wrapping gets head_room == 0 and writes nothing).

Reproducer

use std::collections::VecDeque;

fn main() {
    let v: Vec<i32> = vec![1, 2, 3]; // capacity == len
    let mut it = v.into_iter();
    it.by_ref().for_each(drop); // exhaust it: ptr == end == buf + capacity
    let mut d: VecDeque<i32> = it.collect(); // head == 3 == capacity, len == 0
    d.push_back(1);
    d.push_back(2);
    d.push_back(3); // full, no reallocation
    d.extend(std::iter::empty::<i32>()); // to_physical_idx(3) == wrap_index(6, 3)
    println!("{d:?}");
}

Run with a debug-assertions std, e.g.

$ cat Cargo.toml
...
[profile.dev]
debug-assertions = true
$ cargo +nightly run -Zbuild-std --target aarch64-apple-darwin
thread 'main' panicked at .../library/alloc/src/collections/vec_deque/mod.rs:3472:5:
assertion failed: (logical_index == 0 && capacity == 0) || logical_index < capacity ||
    (logical_index - capacity) < capacity

Expected: no panic (the deque is simply empty at that point and the extend adds nothing).

Meta

rustc 1.93.0-nightly (01867557c 2025-11-12) on aarch64-apple-darwin; the relevant code is unchanged on current master (into_iter.rs into_vecdeque, vec_deque/mod.rs wrap_index / from_contiguous_raw_parts_in).

Possible fix

Normalize the head in from_contiguous_raw_parts_in when the initialized range is empty (or specifically when initialized.start == capacity), e.g. head: if initialized.start == initialized.end { 0 } else { initialized.start }, which restores the documented invariant; alternatively teach into_vecdeque to pass 0..0 for an exhausted iterator (it already does so for ZSTs).

Found while writing Kani proofs for VecDeque in model-checking#681.

[maxdexh]

Thanks for finding this!

This is a violation of the internal invariants of VecDeque. I'm not sure it actually leads to memory corruption right now, but it is unsound in the sense that new code could. It does, see comment below.

Here's a fun way to see the fields without building the standard library.

use std::collections::VecDeque;

fn main() {
    let print_parts = |d: &_| {
        // don't do this in real code, this is library UB ^^
        let parts = unsafe {
            const PARTS: usize = size_of::<VecDeque<i32>>() / size_of::<usize>();
            std::mem::transmute_copy::<_, [usize; PARTS]>(d)
        };
        eprintln!("{:?}", parts)
    };

    let v: Vec<i32> = vec![1, 2, 3]; // capacity == len
    let mut it = v.into_iter();
    it.by_ref().for_each(drop); // exhaust it: ptr == end == buf + capacity
    let mut d: VecDeque<i32> = it.collect(); // head == 3 == capacity, len == 0

    print_parts(&d); // [3, 102488265907664, 3, 0]

    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    print_parts(&d); // [3, 102488265907664, 3, 3]

    d.make_contiguous();

    eprintln!("{d:?}");
}

@rustbot label A-collections I-unsound T-libs C-bug

[maxdexh]

Here's an example that segfaults:

use std::collections::VecDeque;

fn main() {
    for n in 1..200 {
        let v = vec![vec![vec![1]]; n];

        let mut it = v.into_iter();
        for _ in &mut it {}

        let mut d: VecDeque<_> = it.collect(); // head = n, cap = n, len = 0

        d.push_back(vec![]); // head = n, cap = n, len = 1

        // Reads from one-past-the-end of buffer (run with miri to see this)
        let wat = d.pop_front();

        eprintln!("{n}: {wat:?}");
    }
}

[maxdexh]

@rustbot claim

[jrey8343]

Thanks for the quick triage and the segfaulting example. For what it's worth, pop_front is the direct culprit on the read side: it does buffer_read(old_head) with the unwrapped self.head, so head == capacity reads slot capacity. On the verification side (model-checking#681) from_contiguous_raw_parts_in now carries the precondition initialized.start < capacity || initialized.start == 0 (and ensures head < capacity unless the capacity is 0), which is the condition into_vecdeque needs to satisfy; normalizing an empty range to 0..0 in either function satisfies it.

[maxdexh]

Yeah, the VecDeque code is as much of a mess as I remember it. It has gotten slightly better with the introduction of WrappedIndex, except that the safety invariants are still not documented and handled as strictly as they probably should be.

I'll probably add safety requirements to from_contiguous_raw_parts_in and refactor into_vecdeque

[rustbot]

Assigning P-high (discussion on Zulip).