Repository: bluss/arrayvec
Pull request #177 (2021-03-24 17:25:57)

Use u32 for the length field in arrayvec
Store the length as u32 internally. This is to shrink the size of the
ArrayVec value (when possible, depending on element type).

Inline storage vectors larger than u32::MAX are very unlikely to be
useful - for these cases, prefer using Vec instead.

It's not possible to have the CAP type parameter be of type u32 (missing
features in const evaluation/const generics). We also have to panic at
runtime instead of having a static assertion for capacity, for similar
reasons.

bluss: cc @clarfonthey since it's related to the `size_of::<ArrayVec<T, CAP>>`
clarfonthey: I think, personally, it's fine to just keep it at `usize` and then change it to something more reasonable once const eval in generics becomes stable.

Most of the time these arrays are going to be stored on the stack anyway, so it seems unlikely it'll make a huge difference.
bluss: I see. I think it's important to do a good job for arrayvecs inline in other structs too, and I don't really see any downsides to this present change to use u32.

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 5166fbf..434deb1 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -10,7 +10,11 @@ Recent Changes (arrayvec)
 
   The New type syntax is `ArrayVec<T, CAP>` where `CAP` is the arrayvec capacity.
   For arraystring the syntax is `ArrayString<CAP>`.
-  Change by @bluss.
+
+  Length is stored internally as u32; this limits the maximum capacity. The size
+  of the `ArrayVec` or `ArrayString` structs for the same capacity may grow
+  slightly compared with the previous version (depending on padding requirements
+  for the element type). Change by @bluss.
 
 - Arrayvec's `.extend()` and `FromIterator`/`.collect()` to arrayvec now
   **panic** if the capacity of the arrayvec is exceeded. Change by @bluss.
diff --git a/src/array_string.rs b/src/array_string.rs
index c642e2b..076544f 100644
--- a/src/array_string.rs
+++ b/src/array_string.rs
@@ -12,15 +12,20 @@ use std::str::FromStr;
 use std::str::Utf8Error;
 
 use crate::CapacityError;
+use crate::LenUint;
 use crate::char::encode_utf8;
 
 #[cfg(feature="serde")]
 use serde::{Serialize, Deserialize, Serializer, Deserializer};
 
+
 /// A string with a fixed capacity.
 ///
 /// The `ArrayString` is a string backed by a fixed size array. It keeps track
-/// of its length.
+/// of its length, and is parameterized by `CAP` for the maximum capacity.
+///
+/// `CAP` is of type `usize` but is range limited to `u32::MAX`; attempting to create larger
+/// arrayvecs with larger capacity will panic.
 ///
 /// The string is a contiguous value that you can store directly on the stack
 /// if needed.
@@ -28,7 +33,7 @@ use serde::{Serialize, Deserialize, Serializer, Deserializer};
 pub struct ArrayString<const CAP: usize> {
     // the `len` first elements of the array are initialized
     xs: [MaybeUninit<u8>; CAP],
-    len: usize,
+    len: LenUint,
 }
 
 impl<const CAP: usize> Default for ArrayString<CAP>
@@ -55,6 +60,7 @@ impl<const CAP: usize> ArrayString<CAP>
     /// ```
     #[cfg(not(feature="unstable-const-fn"))]
     pub fn new() -> ArrayString<CAP> {
+        assert_capacity_limit!(CAP);
         unsafe {
             ArrayString { xs: MaybeUninit::uninit().assume_init(), len: 0 }
         }
@@ -62,6 +68,7 @@ impl<const CAP: usize> ArrayString<CAP>
 
     #[cfg(feature="unstable-const-fn")]
     pub const fn new() -> ArrayString<CAP> {
+        assert_capacity_limit!(CAP);
         unsafe {
             ArrayString { xs: MaybeUninit::uninit().assume_init(), len: 0 }
         }
@@ -69,7 +76,7 @@ impl<const CAP: usize> ArrayString<CAP>
 
     /// Return the length of the string.
     #[inline]
-    pub fn len(&self) -> usize { self.len }
+    pub fn len(&self) -> usize { self.len as usize }
 
     /// Returns whether the string is empty.
     #[inline]
@@ -347,8 +354,9 @@ impl<const CAP: usize> ArrayString<CAP>
     /// This method uses *debug assertions* to check the validity of `length`
     /// and may use other debug assertions.
     pub unsafe fn set_len(&mut self, length: usize) {
+        // type invariant that capacity always fits in LenUint
         debug_assert!(length <= self.capacity());
-        self.len = length;
+        self.len = length as LenUint;
     }
 
     /// Return a string slice of the whole `ArrayString`.
@@ -371,7 +379,7 @@ impl<const CAP: usize> Deref for ArrayString<CAP>
     #[inline]
     fn deref(&self) -> &str {
         unsafe {
-            let sl = slice::from_raw_parts(self.as_ptr(), self.len);
+            let sl = slice::from_raw_parts(self.as_ptr(), self.len());
             str::from_utf8_unchecked(sl)
         }
     }
@@ -382,7 +390,8 @@ impl<const CAP: usize> DerefMut for ArrayString<CAP>
     #[inline]
     fn deref_mut(&mut self) -> &mut str {
         unsafe {
-            let sl = slice::from_raw_parts_mut(self.as_mut_ptr(), self.len);
+            let len = self.len();
+            let sl = slice::from_raw_parts_mut(self.as_mut_ptr(), len);
             str::from_utf8_unchecked_mut(sl)
         }
     }
diff --git a/src/arrayvec.rs b/src/arrayvec.rs
index d1fa24a..2ab9b0d 100644
--- a/src/arrayvec.rs
+++ b/src/arrayvec.rs
@@ -20,6 +20,7 @@ use std::mem::MaybeUninit;
 #[cfg(feature="serde")]
 use serde::{Serialize, Deserialize, Serializer, Deserializer};
 
+use crate::LenUint;
 use crate::errors::CapacityError;
 use crate::arrayvec_impl::ArrayVecImpl;
 
@@ -29,17 +30,18 @@ use crate::arrayvec_impl::ArrayVecImpl;
 /// the number of initialized elements. The `ArrayVec<T, CAP>` is parameterized
 /// by `T` for the element type and `CAP` for the maximum capacity.
 ///
+/// `CAP` is of type `usize` but is range limited to `u32::MAX`; attempting to create larger
+/// arrayvecs with larger capacity will panic.
+///
 /// The vector is a contiguous value (storing the elements inline) that you can store directly on
 /// the stack if needed.
 ///
-/// It offers a simple API but also dereferences to a slice, so
-/// that the full slice API is available.
-///
-/// ArrayVec can be converted into a by value iterator.
+/// It offers a simple API but also dereferences to a slice, so that the full slice API is
+/// available. The ArrayVec can be converted into a by value iterator.
 pub struct ArrayVec<T, const CAP: usize> {
     // the `len` first elements of the array are initialized
     xs: [MaybeUninit<T>; CAP],
-    len: usize,
+    len: LenUint,
 }
 
 impl<T, const CAP: usize> Drop for ArrayVec<T, CAP> {
@@ -76,6 +78,7 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
     /// ```
     #[cfg(not(feature="unstable-const-fn"))]
     pub fn new() -> ArrayVec<T, CAP> {
+        assert_capacity_limit!(CAP);
         unsafe {
             ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 }
         }
@@ -83,6 +86,7 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
 
     #[cfg(feature="unstable-const-fn")]
     pub const fn new() -> ArrayVec<T, CAP> {
+        assert_capacity_limit!(CAP);
         unsafe {
             ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 }
         }
@@ -97,7 +101,7 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
     /// array.pop();
     /// assert_eq!(array.len(), 2);
     /// ```
-    #[inline]
+    #[inline(always)]
     pub fn len(&self) -> usize { self.len as usize }
 
     /// Returns whether the `ArrayVec` is empty.
@@ -475,8 +479,9 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
     /// This method uses *debug assertions* to check that `length` is
     /// not greater than the capacity.
     pub unsafe fn set_len(&mut self, length: usize) {
+        // type invariant that capacity always fits in LenUint
         debug_assert!(length <= self.capacity());
-        self.len = length;
+        self.len = length as LenUint;
     }
 
     /// Copy all elements from the slice and append to the `ArrayVec`.
@@ -569,7 +574,7 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
 
         // Calling `set_len` creates a fresh and thus unique mutable references, making all
         // older aliases we created invalid. So we cannot call that function.
-        self.len = start;
+        self.len = start as LenUint;
 
         unsafe {
             Drain {
@@ -626,7 +631,7 @@ impl<T, const CAP: usize> ArrayVecImpl for ArrayVec<T, CAP> {
 
     unsafe fn set_len(&mut self, length: usize) {
         debug_assert!(length <= CAP);
-        self.len = length;
+        self.len = length as LenUint;
     }
 
     fn as_ptr(&self) -> *const Self::Item {
@@ -769,7 +774,7 @@ impl<T, const CAP: usize> Iterator for IntoIter<T, CAP> {
     type Item = T;
 
     fn next(&mut self) -> Option<Self::Item> {
-        if self.index == self.v.len {
+        if self.index == self.v.len() {
             None
         } else {
             unsafe {
@@ -788,7 +793,7 @@ impl<T, const CAP: usize> Iterator for IntoIter<T, CAP> {
 
 impl<T, const CAP: usize> DoubleEndedIterator for IntoIter<T, CAP> {
     fn next_back(&mut self) -> Option<Self::Item> {
-        if self.index == self.v.len {
+        if self.index == self.v.len() {
             None
         } else {
             unsafe {
@@ -963,7 +968,7 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
             value: &mut self.len,
             data: len,
             f: move |&len, self_len| {
-                **self_len = len;
+                **self_len = len as LenUint;
             }
         };
         let mut iter = iterable.into_iter();
diff --git a/src/lib.rs b/src/lib.rs
index e0a5817..b927015 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,4 +1,4 @@
-//! **arrayvec** provides the types `ArrayVec` and `ArrayString`: 
+//! **arrayvec** provides the types [`ArrayVec`] and [`ArrayString`]: 
 //! array-backed vector and string types, which store their contents inline.
 //!
 //! The arrayvec package has the following cargo features:
@@ -21,9 +21,9 @@
 //!
 //! This version of arrayvec requires Rust 1.51 or later.
 //!
-#![doc(html_root_url="https://docs.rs/arrayvec/0.5/")]
+#![doc(html_root_url="https://docs.rs/arrayvec/0.6/")]
 #![cfg_attr(not(feature="std"), no_std)]
-#![cfg_attr(feature="unstable-const-fn", feature(const_fn, const_maybe_uninit_assume_init))]
+#![cfg_attr(feature="unstable-const-fn", feature(const_fn, const_maybe_uninit_assume_init, const_panic))]
 
 #[cfg(feature="serde")]
 extern crate serde;
@@ -31,6 +31,18 @@ extern crate serde;
 #[cfg(not(feature="std"))]
 extern crate core as std;
 
+pub(crate) type LenUint = u32;
+
+macro_rules! assert_capacity_limit {
+    ($cap:expr) => {
+        if std::mem::size_of::<usize>() > std::mem::size_of::<LenUint>() {
+            if CAP > LenUint::MAX as usize {
+                panic!("ArrayVec: largest supported capacity is u32::MAX")
+            }
+        }
+    }
+}
+
 mod arrayvec_impl;
 mod arrayvec;
 mod array_string;


Test patch:
diff --git a/tests/tests.rs b/tests/tests.rs
index b89529e..f4698e0 100644
--- a/tests/tests.rs
+++ b/tests/tests.rs
@@ -295,17 +295,17 @@ fn test_compact_size() {
     // 4 bytes + padding + length
     type ByteArray = ArrayVec<u8,  4>;
     println!("{}", mem::size_of::<ByteArray>());
-    assert!(mem::size_of::<ByteArray>() <= 2 * mem::size_of::<usize>());
+    assert!(mem::size_of::<ByteArray>() <= 2 * mem::size_of::<u32>());
 
     // just length
     type EmptyArray = ArrayVec<u8,  0>;
     println!("{}", mem::size_of::<EmptyArray>());
-    assert!(mem::size_of::<EmptyArray>() <= mem::size_of::<usize>());
+    assert!(mem::size_of::<EmptyArray>() <= mem::size_of::<u32>());
 
     // 3 elements + padding + length
     type QuadArray = ArrayVec<u32,  3>;
     println!("{}", mem::size_of::<QuadArray>());
-    assert!(mem::size_of::<QuadArray>() <= 4 * 4 + mem::size_of::<usize>());
+    assert!(mem::size_of::<QuadArray>() <= 4 * 4 + mem::size_of::<u32>());
 }
 
 #[test]
@@ -711,3 +711,19 @@ fn test_try_from_argument() {
     let v = ArrayString::<16>::try_from(format_args!("Hello {}", 123)).unwrap();
     assert_eq!(&v, "Hello 123");
 }
+
+#[test]
+fn allow_max_capacity_arrayvec_type() {
+    // this type is allowed to be used (but can't be constructed)
+    let _v: ArrayVec<(), {usize::MAX}>;
+}
+
+#[should_panic(expected="ArrayVec: largest supported")]
+#[test]
+fn deny_max_capacity_arrayvec_value() {
+    if mem::size_of::<usize>() <= mem::size_of::<u32>() {
+        panic!("This test does not work on this platform. 'ArrayVec: largest supported'");
+    }
+    // this type is allowed to be used (but can't be constructed)
+    let _v: ArrayVec<(), {usize::MAX}> = ArrayVec::new();
+}