1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
// SPDX-License-Identifier: CC0-1.0

//! A simplified `Copy` version of `arrayvec::ArrayVec`.

use core::fmt;

pub use safety_boundary::ArrayVec;

/// Limits the scope of `unsafe` auditing.
// New trait impls and fns that don't need to access internals should go below the module, not
// inside it!
mod safety_boundary {
    use core::mem::MaybeUninit;

    use crate::const_tools::cond_const;

    /// A growable contiguous collection backed by array.
    #[derive(Copy)]
    pub struct ArrayVec<T: Copy, const CAP: usize> {
        len: usize,
        data: [MaybeUninit<T>; CAP],
    }

    impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
        /// Creates an empty `ArrayVec`.
        pub const fn new() -> Self { Self { len: 0, data: [MaybeUninit::uninit(); CAP] } }

        /// Creates an `ArrayVec` initialized with the contets of `slice`.
        ///
        /// # Panics
        ///
        /// If the slice is longer than `CAP`.
        pub const fn from_slice(slice: &[T]) -> Self {
            assert!(slice.len() <= CAP);
            let mut data = [MaybeUninit::uninit(); CAP];
            let mut i = 0;
            // can't use mutable references and operators in const
            while i < slice.len() {
                data[i] = MaybeUninit::new(slice[i]);
                i += 1;
            }

            Self { len: slice.len(), data }
        }

        // from_raw_parts is const-unstable until 1.64
        cond_const! {
            /// Returns a reference to the underlying data.
            pub const(in 1.64) fn as_slice(&self) -> &[T] {
                let ptr = &self.data as *const _ as *const T;
                unsafe { core::slice::from_raw_parts(ptr, self.len) }
            }
        }

        /// Returns a mutable reference to the underlying data.
        pub fn as_mut_slice(&mut self) -> &mut [T] {
            unsafe { &mut *(&mut self.data[..self.len] as *mut _ as *mut [T]) }
        }

        /// Adds an element into `self`.
        ///
        /// # Panics
        ///
        /// If the length would increase past CAP.
        pub fn push(&mut self, element: T) {
            assert!(self.len < CAP);
            self.data[self.len] = MaybeUninit::new(element);
            self.len += 1;
        }

        /// Copies and appends all elements from `slice` into `self`.
        ///
        /// # Panics
        ///
        /// If the length would increase past CAP.
        pub fn extend_from_slice(&mut self, slice: &[T]) {
            let new_len = self.len.checked_add(slice.len()).expect("integer/buffer overflow");
            assert!(new_len <= CAP, "buffer overflow");
            // SAFETY: MaybeUninit<T> has the same layout as T
            let slice = unsafe { &*(slice as *const _ as *const [MaybeUninit<T>]) };
            self.data[self.len..new_len].copy_from_slice(slice);
            self.len = new_len;
        }
    }
}

impl<T: Copy, const CAP: usize> Default for ArrayVec<T, CAP> {
    fn default() -> Self { Self::new() }
}

/// Clones the value *faster* than using `Copy`.
///
/// Because we avoid copying the uninitialized part of the array this copies the value faster than
/// memcpy.
#[allow(clippy::non_canonical_clone_impl)]
impl<T: Copy, const CAP: usize> Clone for ArrayVec<T, CAP> {
    fn clone(&self) -> Self { Self::from_slice(self) }
}

impl<T: Copy, const CAP: usize> core::ops::Deref for ArrayVec<T, CAP> {
    type Target = [T];

    fn deref(&self) -> &Self::Target { self.as_slice() }
}

impl<T: Copy, const CAP: usize> core::ops::DerefMut for ArrayVec<T, CAP> {
    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
}

impl<T: Copy + Eq, const CAP: usize> Eq for ArrayVec<T, CAP> {}

impl<T: Copy + PartialEq, const CAP1: usize, const CAP2: usize> PartialEq<ArrayVec<T, CAP2>>
    for ArrayVec<T, CAP1>
{
    fn eq(&self, other: &ArrayVec<T, CAP2>) -> bool { **self == **other }
}

impl<T: Copy + PartialEq, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> {
    fn eq(&self, other: &[T]) -> bool { **self == *other }
}

impl<T: Copy + PartialEq, const CAP: usize> PartialEq<ArrayVec<T, CAP>> for [T] {
    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
}

impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<[T; LEN]>
    for ArrayVec<T, CAP>
{
    fn eq(&self, other: &[T; LEN]) -> bool { **self == *other }
}

impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<ArrayVec<T, CAP>>
    for [T; LEN]
{
    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
}

impl<T: Copy + Ord, const CAP: usize> Ord for ArrayVec<T, CAP> {
    fn cmp(&self, other: &ArrayVec<T, CAP>) -> core::cmp::Ordering { (**self).cmp(&**other) }
}

impl<T: Copy + PartialOrd, const CAP1: usize, const CAP2: usize> PartialOrd<ArrayVec<T, CAP2>>
    for ArrayVec<T, CAP1>
{
    fn partial_cmp(&self, other: &ArrayVec<T, CAP2>) -> Option<core::cmp::Ordering> {
        (**self).partial_cmp(&**other)
    }
}

impl<T: Copy + fmt::Debug, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Debug::fmt(&**self, f) }
}

impl<T: Copy + core::hash::Hash, const CAP: usize> core::hash::Hash for ArrayVec<T, CAP> {
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) { core::hash::Hash::hash(&**self, state) }
}

#[cfg(test)]
mod tests {
    use super::ArrayVec;

    #[test]
    fn arrayvec_ops() {
        let mut av = ArrayVec::<_, 1>::new();
        assert!(av.is_empty());
        av.push(42);
        assert_eq!(av.len(), 1);
        assert_eq!(av, [42]);
    }

    #[test]
    #[should_panic]
    fn overflow_push() {
        let mut av = ArrayVec::<_, 0>::new();
        av.push(42);
    }

    #[test]
    #[should_panic]
    fn overflow_extend() {
        let mut av = ArrayVec::<_, 0>::new();
        av.extend_from_slice(&[42]);
    }

    #[test]
    fn extend_from_slice() {
        let mut av = ArrayVec::<u8, 8>::new();
        av.extend_from_slice(b"abc");
    }
}