Features

• Fixed Capacity: Type-level capacity using generic-array, all elements live on the stack
• No Heap Allocation: Perfect for embedded systems and no_std environments
• Double-Ended: Efficient push/pop from both ends of the queue
• Efficient Iteration: Support for various iterator types including drain and extract_if
• Rich API: Similar interface to std::collections::VecDeque but with fixed capacity
• Serde Support: Optional serialization/deserialization support
• I/O Support: Read and Write trait implementations (with std feature)

Testing & Memory Safety

This crate is rigorously tested for memory safety and correctness using multiple tools:

• Miri (Tree Borrows): All tests pass under Miri with the Tree Borrows aliasing model
• Miri (Stack Borrows): All tests pass under Miri with the Stack Borrows aliasing model
• Sanitizers: Tested with AddressSanitizer, MemorySanitizer, and ThreadSanitizer
• Valgrind: Memory leak and error detection validated with Valgrind

These extensive checks ensure that all unsafe code is sound and that memory is managed correctly, making this crate safe for use in production environments, including safety-critical systems.

Implementation Notes

Most of the code in this crate is adapted from Rust's standard library VecDeque, modified to work with:

• Fixed-capacity storage using generic-array instead of heap allocation
• const contexts where possible, enabling compile-time initialization and evaluation
• no_std environments without requiring an allocator

The API closely mirrors std::collections::VecDeque to provide familiarity, while the implementation is optimized for stack-allocated, fixed-size use cases.

Why Type-Level Capacity Instead of Const Generics?

While Rust's const generics (const N: usize) might seem like a natural choice for specifying capacity, GenericArrayDeque uses type-level numbers from the typenum crate instead. This design choice enables powerful compile-time patterns that aren't possible with const generics, particularly in trait definitions.

Real-World Example: Syntax Error Tracking

Consider a trait that defines syntax elements with compile-time known component counts:

use generic_arraydeque::{GenericArrayDeque, typenum::{U2, U3}};

trait Syntax {
    type Component;
    type ComponentCount: generic_arraydeque::ArrayLength;

    // Each implementation can specify a different capacity at the type level
    fn possible_components() -> &'static GenericArrayDeque<Self::Component, Self::ComponentCount>;
}

// An if-statement has 3 components
struct IfStatement;
impl Syntax for IfStatement {
    type Component = &'static str;
    type ComponentCount = U3;  // Type-level 3

    fn possible_components() -> &'static GenericArrayDeque<Self::Component, U3> {
        // Can be initialized in const context
        static COMPONENTS: GenericArrayDeque<&'static str, U3> = {
            let mut deque = GenericArrayDeque::new();
            // In a const context, populate the deque...
            deque
        };
        &COMPONENTS
    }
}

// A while-loop has 2 components
struct WhileLoop;
impl Syntax for WhileLoop {
    type Component = &'static str;
    type ComponentCount = U2;  // Type-level 2

    fn possible_components() -> &'static GenericArrayDeque<Self::Component, U2> {
        static COMPONENTS: GenericArrayDeque<&'static str, U2> = {
            let mut deque = GenericArrayDeque::new();
            deque
        };
        &COMPONENTS
    }
}

Why This Requires Type-Level Capacity:

1. Trait-Level Abstraction: Each implementor of Syntax needs a different capacity, but the capacity must be part of the type system. With const N: usize, you can't easily express "each implementation has its own compile-time capacity" in the trait.

2. Const Context Initialization: The deques need to be initialized in const or static contexts. Type-level numbers work seamlessly with const fn and generic contexts where the capacity is part of the type.

3. Zero Runtime Overhead: The capacity is resolved entirely at compile time as part of type checking. There's no runtime representation of the capacity value.

4. Future-Proof: As Rust's const generics mature, there may be migration paths, but for now, type-level numbers provide the necessary expressiveness for these patterns.

This pattern is used in production code for parsing error tracking, where syntax definitions need fixed-capacity collections initialized at compile time with different sizes per syntax element.

Installation

[dependencies]
generic-arraydeque = "0.1"

Feature Flags

• std (default): Enable standard library support, including Vec conversions and I/O traits
• alloc: Enable allocator support for Vec conversions without full std
• serde: Enable Serde serialization/deserialization support
• unstable: Enable unstable features (requires nightly Rust):
  • pop_front_if - Conditionally pop from front based on predicate
  • pop_back_if - Conditionally pop from back based on predicate
  • push_back_mut - Push to back and return mutable reference
  • push_front_mut - Push to front and return mutable reference
  • truncate_front - Truncate elements from the front
  • insert_mut - Insert element and return mutable reference
  • extend_from_within - Clone and extend from a range within the deque (requires T: Clone)
  • prepend_from_within - Clone and prepend from a range within the deque (requires T: Clone)
  • extract_if - Iterator that extracts elements matching a predicate
• zeroize: Enable Zeroize support for secure memory clearing
• faster-hex: Enable faster hex encoding/decoding

Why Use GenericArrayDeque?

• Embedded Systems: No heap allocation required, perfect for memory-constrained environments
• Real-Time Systems: Predictable performance without allocator overhead
• Fixed-Size Buffers: When you know the maximum capacity at compile-time
• Type Safety: Capacity is part of the type, catching errors at compile-time
• Performance: Stack allocation is faster than heap allocation

Usage

Basic Example

use generic_arraydeque::{GenericArrayDeque, typenum::U8};

// Create a deque with capacity of 8 elements
let mut deque = GenericArrayDeque::<u32, U8>::new();

// Push elements to the back
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);

// Push elements to the front
deque.push_front(0);

// Pop from both ends
assert_eq!(deque.pop_front(), Some(0));
assert_eq!(deque.pop_back(), Some(3));

assert_eq!(deque.len(), 2);

Working with Capacity

use generic_arraydeque::{GenericArrayDeque, typenum::U4};

let mut deque = GenericArrayDeque::<i32, U4>::new();

// Try to push - returns overflow value if full
assert_eq!(deque.push_back(1), None);
assert_eq!(deque.push_back(2), None);
assert_eq!(deque.push_back(3), None);
assert_eq!(deque.push_back(4), None);

// Deque is full
assert_eq!(deque.push_back(5), Some(5)); // Returns the value that couldn't be pushed

// Check capacity
assert_eq!(deque.capacity(), 4);
assert_eq!(deque.len(), 4);
assert_eq!(deque.remaining_capacity(), 0);
assert!(deque.is_full());

Creating from Iterators

use generic_arraydeque::{GenericArrayDeque, typenum::U4};

// From an array
let deque = GenericArrayDeque::<u32, U4>::try_from_array([1, 2, 3, 4]).unwrap();
assert_eq!(deque.len(), 4);

// From an iterator
let deque = GenericArrayDeque::<u32, U4>::try_from_iter(0..3).unwrap();
assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![0, 1, 2]);

// From an exact size iterator
let deque = GenericArrayDeque::<u32, U4>::try_from_exact_iter(0..4).unwrap();
assert_eq!(deque.len(), 4);

Iteration

use generic_arraydeque::{GenericArrayDeque, typenum::U4};

let mut deque = GenericArrayDeque::<u32, U4>::try_from_iter(1..=4).unwrap();

// Iterate by reference
for value in &deque {
    println!("{}", value);
}

// Iterate mutably
for value in &mut deque {
    *value *= 2;
}

// Consume into iterator
for value in deque {
    println!("{}", value);
}

Accessing Elements

use generic_arraydeque::{GenericArrayDeque, typenum::U4};

let mut deque = GenericArrayDeque::<u32, U4>::try_from_iter(10..14).unwrap();

// Index access
assert_eq!(deque[0], 10);
assert_eq!(deque[3], 13);

// Get element
assert_eq!(deque.get(1), Some(&11));
assert_eq!(deque.get(10), None);

// Get front and back
assert_eq!(deque.front(), Some(&10));
assert_eq!(deque.back(), Some(&13));

// Get slices (may be split into two contiguous slices)
let (first, second) = deque.as_slices();

License

generic-arraydeque is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.

Copyright (c) 2025 Al Liu

Copyright (c) 2010 The Rust Project Developers