Skip to content

undefined behavior after calling VecDeque::shrink_to #108453

Closed
@trinity-1686a

Description

@trinity-1686a

I tried this code:

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::with_capacity(10);
    
    deque.push_back(1u8);
    deque.push_back(2);
    deque.push_back(3);

    deque.push_front(10);
    deque.push_front(9);
    
    deque.shrink_to(9);
    
    assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![9, 10, 1, 2, 3]);
}

I expected to see this happen: no error

Instead, this happened:

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[9, 1, 2, 3, 0]`,
 right: `[9, 10, 1, 2, 3]`', src/main.rs:15:5

note: no zero was pushed, this is reading an undefined byte.

Meta

rustc --version --verbose:

rustc 1.67.0 (fc594f156 2023-01-24)
binary: rustc
commit-hash: fc594f15669680fa70d255faec3ca3fb507c3405
commit-date: 2023-01-24
host: x86_64-unknown-linux-gnu
release: 1.67.0
LLVM version: 15.0.6

Additional information

I believe this happens because the following case is not handled in shrink_to

//  H := head
//  L := last element
//  start:
//        L       H
//   [1 2 3 . . . 9 10 ]
//  expected (tail shifted):
//        L     H
//   [1 2 3 . . 9 10 ]
//  actual result (tail truncated):
//          L     H
//   [1 2 3 . . . 9 ]

In this case, self.head < target_cap, so two of the "cases of interest" are not a match, and tail_outside == false, so the last case isn't matched either.

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessT-libsRelevant to the library team, which will review and decide on the PR/issue.regression-from-stable-to-stablePerformance or correctness regression from one stable version to another.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions