orderable_bytes/
variable.rs

1//! Canonical, order-preserving variable-length byte encodings for
2//! `str`, `String`, `[u8]` and `Vec<u8>`.
3//!
4//! The encoding is the value's own bytes, borrowed: a string encodes to
5//! its UTF-8 bytes, and a byte string to itself. No copy is made, so no
6//! second copy of the plaintext is left in memory.
7//!
8//! Byte-wise lexicographic order is already the order these types
9//! define, with a value sorting before any longer value it is a prefix
10//! of (`"ab"` < `"abc"`). For `str` this is Unicode code-point order,
11//! because UTF-8 preserves it. Byte equality is value equality.
12//!
13//! # No normalisation
14//!
15//! A string is encoded exactly as given. Two strings that Unicode
16//! considers the same text but that use different code points (`é` as
17//! U+00E9, or as `e` followed by U+0301) encode differently, and sort
18//! by code point rather than by any language's collation. Callers that
19//! need canonical equivalence, case folding or accent folding must
20//! normalise before encoding.
21//!
22//! # Never pad, never concatenate
23//!
24//! These encodings do not mark where they end. A consumer must keep
25//! each value's length and compare by length when one value is a prefix
26//! of the other, as a variable-length scheme does. Two misuses break
27//! the guarantees:
28//!
29//! - **Zero-padding** to a fixed block size makes `"a"` and `"a\0"`
30//!   encode identically.
31//! - **Concatenating** two values loses the boundary between them, so
32//!   `("ab", "c")` and `("a", "bc")` encode identically.
33//!
34//! Fixed-length encodings (see [`crate::FixedOrderableBytes`]) are safe
35//! to zero-extend; these are not. That is why these types implement
36//! [`crate::VariableOrderableBytes`] and not
37//! [`crate::FixedOrderableBytes`]: code that pads must bound on the
38//! latter, and then rejects these types at compile time.
39
40use crate::{private::Sealed, OrderableBytes, VariableOrderableBytes};
41
42impl Sealed for str {}
43impl VariableOrderableBytes for str {}
44
45impl OrderableBytes for str {
46    type Bytes<'a> = &'a [u8];
47
48    fn to_orderable_bytes(&self) -> &[u8] {
49        self.as_bytes()
50    }
51}
52
53impl Sealed for String {}
54impl VariableOrderableBytes for String {}
55
56impl OrderableBytes for String {
57    type Bytes<'a> = &'a [u8];
58
59    fn to_orderable_bytes(&self) -> &[u8] {
60        self.as_bytes()
61    }
62}
63
64impl Sealed for [u8] {}
65impl VariableOrderableBytes for [u8] {}
66
67impl OrderableBytes for [u8] {
68    type Bytes<'a> = &'a [u8];
69
70    fn to_orderable_bytes(&self) -> &[u8] {
71        self
72    }
73}
74
75impl Sealed for Vec<u8> {}
76impl VariableOrderableBytes for Vec<u8> {}
77
78impl OrderableBytes for Vec<u8> {
79    type Bytes<'a> = &'a [u8];
80
81    fn to_orderable_bytes(&self) -> &[u8] {
82        self
83    }
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    #[test]
91    fn variable_length_types_implement_variable_orderable_bytes() {
92        fn is_variable<T: VariableOrderableBytes + ?Sized>() {}
93        is_variable::<str>();
94        is_variable::<String>();
95        is_variable::<[u8]>();
96        is_variable::<Vec<u8>>();
97    }
98
99    #[test]
100    fn str_encodes_to_its_utf8_bytes() {
101        assert_eq!("".to_orderable_bytes(), b"");
102        assert_eq!("a".to_orderable_bytes(), b"a");
103        assert_eq!("\u{e9}".to_orderable_bytes(), [0xc3, 0xa9]);
104        assert_eq!("e\u{301}".to_orderable_bytes(), [0x65, 0xcc, 0x81]);
105    }
106
107    #[test]
108    fn encoding_borrows_rather_than_copies() {
109        let s = String::from("borrowed");
110        assert_eq!(s.to_orderable_bytes().as_ptr(), s.as_ptr());
111        let v = vec![1u8, 2, 3];
112        assert_eq!(v.to_orderable_bytes().as_ptr(), v.as_ptr());
113    }
114
115    #[test]
116    fn a_prefix_sorts_before_the_longer_value() {
117        let ascending = ["", "a", "a\0", "ab", "abc", "b", "\u{e9}", "\u{10ffff}"];
118        for window in ascending.windows(2) {
119            assert!(
120                window[0].to_orderable_bytes() < window[1].to_orderable_bytes(),
121                "{:?} < {:?} failed",
122                window[0],
123                window[1]
124            );
125        }
126    }
127
128    #[test]
129    fn no_normalisation_is_applied() {
130        // Precomposed and decomposed é are the same text to Unicode but
131        // different strings to Rust, and they encode differently.
132        assert_ne!(
133            "\u{e9}".to_orderable_bytes(),
134            "e\u{301}".to_orderable_bytes()
135        );
136    }
137
138    quickcheck! {
139        fn string_byte_order_matches_string_order(a: String, b: String) -> bool {
140            a.to_orderable_bytes().cmp(b.to_orderable_bytes()) == a.cmp(&b)
141        }
142
143        fn string_byte_equality_matches_string_equality(a: String, b: String) -> bool {
144            (a.to_orderable_bytes() == b.to_orderable_bytes()) == (a == b)
145        }
146
147        fn bytes_byte_order_matches_bytes_order(a: Vec<u8>, b: Vec<u8>) -> bool {
148            a.to_orderable_bytes().cmp(b.to_orderable_bytes()) == a.cmp(&b)
149        }
150
151        fn str_and_string_encode_identically(a: String) -> bool {
152            a.as_str().to_orderable_bytes() == a.to_orderable_bytes()
153        }
154    }
155}
orderable_bytes/variable.rs

orderable_bytes/
variable.rs
