path: root/users/tazjin/german-string/src/lib.rs

use std::alloc::Layout;
use std::cmp::Ordering;
use std::fmt::{Debug, Formatter};

#[derive(Clone, Copy)]
#[repr(C)]
struct GSSmall {
    len: u32,
    data: [u8; 12],
}

#[derive(Clone, Copy)]
#[repr(transparent)]
struct StorageClassPtr(usize);

impl StorageClassPtr {
    fn transient(ptr: *const u8) -> Self {
        debug_assert!(
            (ptr as usize & 0b1) == 0,
            "pointer must be at least 2-byte aligned"
        );
        Self(ptr as usize)
    }

    fn persistent(ptr: *const u8) -> Self {
        debug_assert!(
            (ptr as usize & 0b1) == 0,
            "pointer must be at least 2-byte aligned"
        );
        Self((ptr as usize) | 0b1)
    }

    fn as_ptr(&self) -> *const u8 {
        (self.0 & !0b1) as *const u8
    }

    unsafe fn as_mut_ptr(&self) -> *mut u8 {
        (self.0 & !0b1) as *mut u8
    }

    fn is_transient(&self) -> bool {
        (self.0 & 0b1) == 0
    }
}

#[derive(Clone, Copy)]
#[repr(C)]
struct GSLarge {
    len: u32,
    prefix: [u8; 4],
    data: StorageClassPtr,
}

const _ASSERT_VARIANTS_SIZE: () = assert!(
    std::mem::size_of::<GSSmall>() == std::mem::size_of::<GSLarge>(),
    "German String variants must have the same size"
);

union GSRepr {
    small: GSSmall,
    large: GSLarge,
}

#[repr(transparent)]
pub struct GermanString(GSRepr);

const _ASSERT_GSTRING_SIZE: () = assert!(
    std::mem::size_of::<GermanString>() == 16,
    "German String should be 16 bytes in size",
);

impl GermanString {
    /// Creates a new transient German String from the given slice, copying the
    /// data in the process.
    pub fn transient(bytes: &[u8]) -> GermanString {
        if bytes.len() > u32::MAX as usize {
            panic!("GermanString maximum length is {} bytes", u32::MAX);
        }

        if bytes.len() <= 12 {
            let mut s = GSSmall {
                len: bytes.len() as u32,
                data: [0u8; 12],
            };
            s.data[..bytes.len()].copy_from_slice(bytes);
            GermanString(GSRepr { small: s })
        } else {
            let layout = Layout::array::<u8>(bytes.len()).unwrap();
            let mut large = GSLarge {
                len: bytes.len() as u32,
                prefix: [0u8; 4],
                data: unsafe {
                    let ptr = std::alloc::alloc(layout);
                    if ptr.is_null() {
                        std::alloc::handle_alloc_error(layout);
                    }
                    std::ptr::copy_nonoverlapping(bytes.as_ptr(), ptr, bytes.len());
                    StorageClassPtr::transient(ptr)
                },
            };

            large.prefix.copy_from_slice(&bytes[..4]);

            GermanString(GSRepr { large })
        }
    }

    /// Creates a new transient German String from the given owned bytes. Short
    /// strings will be copied into the string representation, long strings will
    /// be moved out of the given vector without additional allocations.
    pub fn transient_from_owned(bytes: Vec<u8>) -> GermanString {
        if bytes.len() > u32::MAX as usize {
            panic!("GermanString maximum length is {} bytes", u32::MAX);
        }

        if bytes.len() <= 12 {
            let mut s = GSSmall {
                len: bytes.len() as u32,
                data: [0u8; 12],
            };

            s.data[..bytes.len()].copy_from_slice(&bytes);
            GermanString(GSRepr { small: s })
        } else {
            let md = std::mem::ManuallyDrop::new(bytes);
            let mut large = GSLarge {
                len: md.len() as u32,
                prefix: [0u8; 4],
                data: StorageClassPtr::transient(md.as_ptr()),
            };

            large.prefix.copy_from_slice(&md[..4]);
            GermanString(GSRepr { large })
        }
    }

    /// Creates a persistent German String from a static data buffer.
    pub fn persistent(bytes: &'static [u8]) -> GermanString {
        if bytes.len() > u32::MAX as usize {
            panic!("GermanString maximum length is {} bytes", u32::MAX);
        }

        if bytes.len() <= 12 {
            let mut s = GSSmall {
                len: bytes.len() as u32,
                data: [0u8; 12],
            };

            s.data[..bytes.len()].copy_from_slice(&bytes);
            GermanString(GSRepr { small: s })
        } else {
            let mut large = GSLarge {
                len: bytes.len() as u32,
                prefix: [0u8; 4],
                data: StorageClassPtr::persistent(bytes.as_ptr()),
            };

            large.prefix.copy_from_slice(&bytes[..4]);
            GermanString(GSRepr { large })
        }
    }

    /// Creates a persistent German String by leaking the provided data.
    pub fn persistent_leak(bytes: Vec<u8>) -> GermanString {
        if bytes.len() > u32::MAX as usize {
            panic!("GermanString maximum length is {} bytes", u32::MAX);
        }

        if bytes.len() <= 12 {
            let mut s = GSSmall {
                len: bytes.len() as u32,
                data: [0u8; 12],
            };

            s.data[..bytes.len()].copy_from_slice(&bytes);
            GermanString(GSRepr { small: s })
        } else {
            let md = std::mem::ManuallyDrop::new(bytes);
            let mut large = GSLarge {
                len: md.len() as u32,
                prefix: [0u8; 4],
                data: StorageClassPtr::persistent(md.as_ptr()),
            };

            large.prefix.copy_from_slice(&md[..4]);
            GermanString(GSRepr { large })
        }
    }

    /// Creates a persistent German String from a static data buffer.
    pub fn persistent_from_str(s: &'static str) -> GermanString {
        GermanString::persistent(s.as_bytes())
    }

    pub fn len(&self) -> usize {
        // SAFETY: The length field is located in the same location for both
        // variants, reading it from either is safe.
        unsafe { self.0.small.len as usize }
    }

    pub fn as_bytes(&self) -> &[u8] {
        if self.len() > 12 {
            unsafe { std::slice::from_raw_parts(self.0.large.data.as_ptr(), self.len()) }
        } else {
            unsafe { &self.0.small.data.as_ref()[..self.len()] }
        }
    }

    pub fn as_str(&self) -> Result<&str, std::str::Utf8Error> {
        std::str::from_utf8(self.as_bytes())
    }
}

impl Drop for GermanString {
    fn drop(&mut self) {
        unsafe {
            if self.len() > 12 && self.0.large.data.is_transient() {
                let layout = Layout::array::<u8>(self.len()).unwrap();
                std::alloc::dealloc(self.0.large.data.as_mut_ptr(), layout);
            }
        }
    }
}

impl PartialEq for GermanString {
    fn eq(&self, other: &GermanString) -> bool {
        if self.len() != other.len() {
            return false;
        }

        unsafe {
            if self.len() <= 12 {
                return self.0.small.data[..self.len()] == other.0.small.data[..other.len()];
            }
            return self.0.large.data.as_ptr() == other.0.large.data.as_ptr()
                || (self.0.large.prefix == other.0.large.prefix
                    && self.as_bytes() == other.as_bytes());
        }
    }
}

impl Eq for GermanString {}

impl Ord for GermanString {
    fn cmp(&self, other: &GermanString) -> Ordering {
        match (self.len().cmp(&12), other.len().cmp(&12)) {
            // two small strings
            (Ordering::Less | Ordering::Equal, Ordering::Less | Ordering::Equal) => unsafe {
                self.0.small.data[..self.len()].cmp(&other.0.small.data[..other.len()])
            },
            // two large strings
            (Ordering::Greater, Ordering::Greater) => unsafe {
                match self.0.large.prefix.cmp(&other.0.large.prefix) {
                    Ordering::Equal => self.as_bytes().cmp(other.as_bytes()),
                    ordering => ordering,
                }
            },

            // LHS large, RHS small
            (Ordering::Greater, _) => {
                let prefix_ordering =
                    unsafe { self.0.large.prefix.as_slice().cmp(&other.0.small.data[..4]) };

                if prefix_ordering != Ordering::Equal {
                    return prefix_ordering;
                }

                self.as_bytes().cmp(other.as_bytes())
            }

            // LHS small, RHS large
            (_, Ordering::Greater) => {
                let prefix_ordering =
                    unsafe { self.0.small.data[..4].cmp(other.0.large.prefix.as_slice()) };

                if prefix_ordering != Ordering::Equal {
                    return prefix_ordering;
                }

                self.as_bytes().cmp(other.as_bytes())
            }
        }
    }
}

impl PartialOrd for GermanString {
    fn partial_cmp(&self, other: &GermanString) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Debug for GermanString {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
        String::from_utf8_lossy(self.as_bytes()).fmt(f)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use proptest::prelude::*;

    impl Arbitrary for GermanString {
        type Parameters = <String as Arbitrary>::Parameters;
        type Strategy = BoxedStrategy<Self>;

        fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
            any_with::<String>(args)
                .prop_map(|s| GermanString::transient(s.as_bytes()))
                .boxed()
        }
    }

    #[test]
    fn test_empty_string() {
        let empty = GermanString::transient(b"");

        assert_eq!(empty.len(), 0, "empty string should be empty");
        assert_eq!(empty.as_bytes(), b"", "empty string should contain nothing");
        assert_eq!(
            empty.as_str().expect("empty string is valid UTF-8"),
            "",
            "empty string should contain empty string"
        );
    }

    #[test]
    fn test_short_string() {
        let short = GermanString::transient(b"meow");

        assert_eq!(short.len(), 4, "'meow' is four characters");
        assert_eq!(
            short.as_bytes(),
            b"meow",
            "short string returns correct bytes"
        );
        assert_eq!(
            short.as_str().expect("'meow' is valid UTF-8"),
            "meow",
            "short string returns correct string"
        );
    }

    #[test]
    fn test_long_string() {
        let input: &str = "This code was written at https://signal.live";
        let long = GermanString::transient(input.as_bytes());

        assert_eq!(long.len(), 44, "long string has correct length");
        assert_eq!(
            long.as_bytes(),
            input.as_bytes(),
            "long string returns correct bytes"
        );

        assert_eq!(
            long.as_str().expect("input is valid UTF-8"),
            input,
            "long string returns correct string"
        );
    }

    proptest! {
        #[test]
        fn test_roundtrip_vec(input: Vec<u8>) {
            let gs = GermanString::transient_from_owned(input.clone());
            assert_eq!(input.len(), gs.len(), "length should match");

            let out = gs.as_bytes().to_owned();
            assert_eq!(input, out, "roundtrip should yield same bytes");
        }

        #[test]
        fn test_roundtrip_string(input: String) {
            let gs = GermanString::transient_from_owned(input.clone().into_bytes());
            assert_eq!(input.len(), gs.len(), "length should match");

            let out = String::from_utf8(gs.as_bytes().to_owned())
              .expect("string should be valid after roundtrip");

            assert_eq!(input, out, "roundtrip should yield same string");
        }

        // Test [`Eq`] implementation.
        #[test]
        fn test_eq(lhs: Vec<u8>, rhs: Vec<u8>) {
            let lhs_gs = GermanString::transient(lhs.as_slice());
            let rhs_gs = GermanString::transient(rhs.as_slice());

            assert_eq!(
                (lhs == rhs),
                (lhs_gs == rhs_gs),
                "Eq should match between std::String and GermanString ({:?} == {:?})",
                lhs, rhs,
            );
        }

        #[test]
        fn test_reflexivity(x: GermanString) {
            prop_assert!(x == x);
        }

        #[test]
        fn test_symmetry(x: GermanString, y: GermanString) {
            prop_assert_eq!(x == y, y == x);
        }

        #[test]
        fn test_transitivity(x: GermanString, y: GermanString, z: GermanString) {
            if x == y && y == z {
                assert!(x == z);
            }
        }
    }
}