semver/
identifier.rs

1// This module implements Identifier, a short-optimized string allowed to
2// contain only the ASCII characters hyphen, dot, 0-9, A-Z, a-z.
3//
4// As of mid-2021, the distribution of pre-release lengths on crates.io is:
5//
6//     length  count         length  count         length  count
7//        0  355929            11      81            24       2
8//        1     208            12      48            25       6
9//        2     236            13      55            26      10
10//        3    1909            14      25            27       4
11//        4    1284            15      15            28       1
12//        5    1742            16      35            30       1
13//        6    3440            17       9            31       5
14//        7    5624            18       6            32       1
15//        8    1321            19      12            36       2
16//        9     179            20       2            37     379
17//       10      65            23      11
18//
19// and the distribution of build metadata lengths is:
20//
21//     length  count         length  count         length  count
22//        0  364445             8    7725            18       1
23//        1      72             9      16            19       1
24//        2       7            10      85            20       1
25//        3      28            11      17            22       4
26//        4       9            12      10            26       1
27//        5      68            13       9            27       1
28//        6      73            14      10            40       5
29//        7      53            15       6
30//
31// Therefore it really behooves us to be able to use the entire 8 bytes of a
32// pointer for inline storage. For both pre-release and build metadata there are
33// vastly more strings with length exactly 8 bytes than the sum over all lengths
34// longer than 8 bytes.
35//
36// To differentiate the inline representation from the heap allocated long
37// representation, we'll allocate heap pointers with 2-byte alignment so that
38// they are guaranteed to have an unset least significant bit. Then in the repr
39// we store for pointers, we rotate a 1 into the most significant bit of the
40// most significant byte, which is never set for an ASCII byte.
41//
42// Inline repr:
43//
44//     0xxxxxxx 0xxxxxxx 0xxxxxxx 0xxxxxxx 0xxxxxxx 0xxxxxxx 0xxxxxxx 0xxxxxxx
45//
46// Heap allocated repr:
47//
48//     1ppppppp pppppppp pppppppp pppppppp pppppppp pppppppp pppppppp pppppppp 0
49//     ^ most significant bit   least significant bit of orig ptr, rotated out ^
50//
51// Since the most significant bit doubles as a sign bit for the similarly sized
52// signed integer type, the CPU has an efficient instruction for inspecting it,
53// meaning we can differentiate between an inline repr and a heap allocated repr
54// in one instruction. Effectively an inline repr always looks like a positive
55// i64 while a heap allocated repr always looks like a negative i64.
56//
57// For the inline repr, we store \0 padding on the end of the stored characters,
58// and thus the string length is readily determined efficiently by a cttz (count
59// trailing zeros) or bsf (bit scan forward) instruction.
60//
61// For the heap allocated repr, the length is encoded as a base-128 varint at
62// the head of the allocation.
63//
64// Empty strings are stored as an all-1 bit pattern, corresponding to -1i64.
65// Consequently the all-0 bit pattern is never a legal representation in any
66// repr, leaving it available as a niche for downstream code. For example this
67// allows size_of::<Version>() == size_of::<Option<Version>>().
68
69use crate::alloc::alloc::{alloc, dealloc, handle_alloc_error, Layout};
70use core::mem;
71use core::num::{NonZeroU64, NonZeroUsize};
72use core::ptr::{self, NonNull};
73use core::slice;
74use core::str;
75
76const PTR_BYTES: usize = mem::size_of::<NonNull<u8>>();
77
78// If pointers are already 8 bytes or bigger, then 0. If pointers are smaller
79// than 8 bytes, then Identifier will contain a byte array to raise its size up
80// to 8 bytes total.
81const TAIL_BYTES: usize = 8 * (PTR_BYTES < 8) as usize - PTR_BYTES * (PTR_BYTES < 8) as usize;
82
83#[repr(C, align(8))]
84pub(crate) struct Identifier {
85    head: NonNull<u8>,
86    tail: [u8; TAIL_BYTES],
87}
88
89impl Identifier {
90    pub(crate) const fn empty() -> Self {
91        // This is a separate constant because unsafe function calls are not
92        // allowed in a const fn body, only in a const, until later rustc than
93        // what we support.
94        const HEAD: NonNull<u8> = unsafe { NonNull::new_unchecked(!0 as *mut u8) };
95
96        // `mov rax, -1`
97        Identifier {
98            head: HEAD,
99            tail: [!0; TAIL_BYTES],
100        }
101    }
102
103    // SAFETY: string must be ASCII and not contain \0 bytes.
104    pub(crate) unsafe fn new_unchecked(string: &str) -> Self {
105        let len = string.len();
106        debug_assert!(len <= isize::MAX as usize);
107        match len as u64 {
108            0 => Self::empty(),
109            1..=8 => {
110                let mut bytes = [0u8; mem::size_of::<Identifier>()];
111                // SAFETY: string is big enough to read len bytes, bytes is big
112                // enough to write len bytes, and they do not overlap.
113                unsafe { ptr::copy_nonoverlapping(string.as_ptr(), bytes.as_mut_ptr(), len) };
114                // SAFETY: the head field is nonzero because the input string
115                // was at least 1 byte of ASCII and did not contain \0.
116                unsafe { mem::transmute::<[u8; mem::size_of::<Identifier>()], Identifier>(bytes) }
117            }
118            9..=0xff_ffff_ffff_ffff => {
119                // SAFETY: len is in a range that does not contain 0.
120                let size = bytes_for_varint(unsafe { NonZeroUsize::new_unchecked(len) }) + len;
121                let align = 2;
122                // On 32-bit and 16-bit architecture, check for size overflowing
123                // isize::MAX. Making an allocation request bigger than this to
124                // the allocator is considered UB. All allocations (including
125                // static ones) are limited to isize::MAX so we're guaranteed
126                // len <= isize::MAX, and we know bytes_for_varint(len) <= 5
127                // because 128**5 > isize::MAX, which means the only problem
128                // that can arise is when isize::MAX - 5 <= len <= isize::MAX.
129                // This is pretty much guaranteed to be malicious input so we
130                // don't need to care about returning a good error message.
131                if mem::size_of::<usize>() < 8 {
132                    let max_alloc = usize::MAX / 2 - align;
133                    assert!(size <= max_alloc);
134                }
135                // SAFETY: align is not zero, align is a power of two, and
136                // rounding size up to align does not overflow isize::MAX.
137                let layout = unsafe { Layout::from_size_align_unchecked(size, align) };
138                // SAFETY: layout's size is nonzero.
139                let ptr = unsafe { alloc(layout) };
140                if ptr.is_null() {
141                    handle_alloc_error(layout);
142                }
143                let mut write = ptr;
144                let mut varint_remaining = len;
145                while varint_remaining > 0 {
146                    // SAFETY: size is bytes_for_varint(len) bytes + len bytes.
147                    // This is writing the first bytes_for_varint(len) bytes.
148                    unsafe { ptr::write(write, varint_remaining as u8 | 0x80) };
149                    varint_remaining >>= 7;
150                    // SAFETY: still in bounds of the same allocation.
151                    write = unsafe { write.add(1) };
152                }
153                // SAFETY: size is bytes_for_varint(len) bytes + len bytes. This
154                // is writing to the last len bytes.
155                unsafe { ptr::copy_nonoverlapping(string.as_ptr(), write, len) };
156                Identifier {
157                    head: ptr_to_repr(ptr),
158                    tail: [0; TAIL_BYTES],
159                }
160            }
161            0x100_0000_0000_0000..=0xffff_ffff_ffff_ffff => {
162                unreachable!("please refrain from storing >64 petabytes of text in semver version");
163            }
164        }
165    }
166
167    pub(crate) fn is_empty(&self) -> bool {
168        // `cmp rdi, -1` -- basically: `repr as i64 == -1`
169        let empty = Self::empty();
170        let is_empty = self.head == empty.head && self.tail == empty.tail;
171        // The empty representation does nothing on Drop. We can't let this one
172        // drop normally because `impl Drop for Identifier` calls is_empty; that
173        // would be an infinite recursion.
174        mem::forget(empty);
175        is_empty
176    }
177
178    fn is_inline(&self) -> bool {
179        // `test rdi, rdi` -- basically: `repr as i64 >= 0`
180        self.head.as_ptr() as usize >> (PTR_BYTES * 8 - 1) == 0
181    }
182
183    fn is_empty_or_inline(&self) -> bool {
184        // `cmp rdi, -2` -- basically: `repr as i64 > -2`
185        self.is_empty() || self.is_inline()
186    }
187
188    pub(crate) fn as_str(&self) -> &str {
189        if self.is_empty() {
190            ""
191        } else if self.is_inline() {
192            // SAFETY: repr is in the inline representation.
193            unsafe { inline_as_str(self) }
194        } else {
195            // SAFETY: repr is in the heap allocated representation.
196            unsafe { ptr_as_str(&self.head) }
197        }
198    }
199
200    pub(crate) fn ptr_eq(&self, rhs: &Self) -> bool {
201        self.head == rhs.head && self.tail == rhs.tail
202    }
203}
204
205impl Clone for Identifier {
206    fn clone(&self) -> Self {
207        if self.is_empty_or_inline() {
208            Identifier {
209                head: self.head,
210                tail: self.tail,
211            }
212        } else {
213            let ptr = repr_to_ptr(self.head);
214            // SAFETY: ptr is one of our own heap allocations.
215            let len = unsafe { decode_len(ptr) };
216            let size = bytes_for_varint(len) + len.get();
217            let align = 2;
218            // SAFETY: align is not zero, align is a power of two, and rounding
219            // size up to align does not overflow isize::MAX. This is just
220            // duplicating a previous allocation where all of these guarantees
221            // were already made.
222            let layout = unsafe { Layout::from_size_align_unchecked(size, align) };
223            // SAFETY: layout's size is nonzero.
224            let clone = unsafe { alloc(layout) };
225            if clone.is_null() {
226                handle_alloc_error(layout);
227            }
228            // SAFETY: new allocation cannot overlap the previous one (this was
229            // not a realloc). The argument ptrs are readable/writeable
230            // respectively for size bytes.
231            unsafe { ptr::copy_nonoverlapping(ptr, clone, size) }
232            Identifier {
233                head: ptr_to_repr(clone),
234                tail: [0; TAIL_BYTES],
235            }
236        }
237    }
238}
239
240impl Drop for Identifier {
241    fn drop(&mut self) {
242        if self.is_empty_or_inline() {
243            return;
244        }
245        let ptr = repr_to_ptr_mut(self.head);
246        // SAFETY: ptr is one of our own heap allocations.
247        let len = unsafe { decode_len(ptr) };
248        let size = bytes_for_varint(len) + len.get();
249        let align = 2;
250        // SAFETY: align is not zero, align is a power of two, and rounding
251        // size up to align does not overflow isize::MAX. These guarantees were
252        // made when originally allocating this memory.
253        let layout = unsafe { Layout::from_size_align_unchecked(size, align) };
254        // SAFETY: ptr was previously allocated by the same allocator with the
255        // same layout.
256        unsafe { dealloc(ptr, layout) }
257    }
258}
259
260impl PartialEq for Identifier {
261    fn eq(&self, rhs: &Self) -> bool {
262        if self.ptr_eq(rhs) {
263            // Fast path (most common)
264            true
265        } else if self.is_empty_or_inline() || rhs.is_empty_or_inline() {
266            false
267        } else {
268            // SAFETY: both reprs are in the heap allocated representation.
269            unsafe { ptr_as_str(&self.head) == ptr_as_str(&rhs.head) }
270        }
271    }
272}
273
274unsafe impl Send for Identifier {}
275unsafe impl Sync for Identifier {}
276
277// We use heap pointers that are 2-byte aligned, meaning they have an
278// insignificant 0 in the least significant bit. We take advantage of that
279// unneeded bit to rotate a 1 into the most significant bit to make the repr
280// distinguishable from ASCII bytes.
281fn ptr_to_repr(original: *mut u8) -> NonNull<u8> {
282    // `mov eax, 1`
283    // `shld rax, rdi, 63`
284    let modified = (original as usize | 1).rotate_right(1);
285
286    // `original + (modified - original)`, but being mindful of provenance.
287    let diff = modified.wrapping_sub(original as usize);
288    let modified = original.wrapping_add(diff);
289
290    // SAFETY: the most significant bit of repr is known to be set, so the value
291    // is not zero.
292    unsafe { NonNull::new_unchecked(modified) }
293}
294
295// Shift out the 1 previously placed into the most significant bit of the least
296// significant byte. Shift in a low 0 bit to reconstruct the original 2-byte
297// aligned pointer.
298fn repr_to_ptr(modified: NonNull<u8>) -> *const u8 {
299    // `lea rax, [rdi + rdi]`
300    let modified = modified.as_ptr();
301    let original = (modified as usize) << 1;
302
303    // `modified + (original - modified)`, but being mindful of provenance.
304    let diff = original.wrapping_sub(modified as usize);
305    modified.wrapping_add(diff)
306}
307
308fn repr_to_ptr_mut(repr: NonNull<u8>) -> *mut u8 {
309    repr_to_ptr(repr) as *mut u8
310}
311
312// Compute the length of the inline string, assuming the argument is in short
313// string representation. Short strings are stored as 1 to 8 nonzero ASCII
314// bytes, followed by \0 padding for the remaining bytes.
315//
316// SAFETY: the identifier must indeed be in the inline representation.
317unsafe fn inline_len(repr: &Identifier) -> NonZeroUsize {
318    // SAFETY: Identifier's layout is align(8) and at least size 8. We're doing
319    // an aligned read of the first 8 bytes from it. The bytes are not all zero
320    // because inline strings are at least 1 byte long and cannot contain \0.
321    let repr = unsafe { ptr::read(repr as *const Identifier as *const NonZeroU64) };
322
323    #[cfg(target_endian = "little")]
324    let zero_bits_on_string_end = repr.leading_zeros();
325    #[cfg(target_endian = "big")]
326    let zero_bits_on_string_end = repr.trailing_zeros();
327
328    let nonzero_bytes = 8 - zero_bits_on_string_end as usize / 8;
329
330    // SAFETY: repr is nonzero, so it has at most 63 zero bits on either end,
331    // thus at least one nonzero byte.
332    unsafe { NonZeroUsize::new_unchecked(nonzero_bytes) }
333}
334
335// SAFETY: repr must be in the inline representation, i.e. at least 1 and at
336// most 8 nonzero ASCII bytes padded on the end with \0 bytes.
337unsafe fn inline_as_str(repr: &Identifier) -> &str {
338    let ptr = repr as *const Identifier as *const u8;
339    let len = unsafe { inline_len(repr) }.get();
340    // SAFETY: we are viewing the nonzero ASCII prefix of the inline repr's
341    // contents as a slice of bytes. Input/output lifetimes are correctly
342    // associated.
343    let slice = unsafe { slice::from_raw_parts(ptr, len) };
344    // SAFETY: the string contents are known to be only ASCII bytes, which are
345    // always valid UTF-8.
346    unsafe { str::from_utf8_unchecked(slice) }
347}
348
349// Decode varint. Varints consist of between one and eight base-128 digits, each
350// of which is stored in a byte with most significant bit set. Adjacent to the
351// varint in memory there is guaranteed to be at least 9 ASCII bytes, each of
352// which has an unset most significant bit.
353//
354// SAFETY: ptr must be one of our own heap allocations, with the varint header
355// already written.
356unsafe fn decode_len(ptr: *const u8) -> NonZeroUsize {
357    // SAFETY: There is at least one byte of varint followed by at least 9 bytes
358    // of string content, which is at least 10 bytes total for the allocation,
359    // so reading the first two is no problem.
360    let [first, second] = unsafe { ptr::read(ptr as *const [u8; 2]) };
361    if second < 0x80 {
362        // SAFETY: the length of this heap allocated string has been encoded as
363        // one base-128 digit, so the length is at least 9 and at most 127. It
364        // cannot be zero.
365        unsafe { NonZeroUsize::new_unchecked((first & 0x7f) as usize) }
366    } else {
367        return unsafe { decode_len_cold(ptr) };
368
369        // Identifiers 128 bytes or longer. This is not exercised by any crate
370        // version currently published to crates.io.
371        #[cold]
372        #[inline(never)]
373        unsafe fn decode_len_cold(mut ptr: *const u8) -> NonZeroUsize {
374            let mut len = 0;
375            let mut shift = 0;
376            loop {
377                // SAFETY: varint continues while there are bytes having the
378                // most significant bit set, i.e. until we start hitting the
379                // ASCII string content with msb unset.
380                let byte = unsafe { *ptr };
381                if byte < 0x80 {
382                    // SAFETY: the string length is known to be 128 bytes or
383                    // longer.
384                    return unsafe { NonZeroUsize::new_unchecked(len) };
385                }
386                // SAFETY: still in bounds of the same allocation.
387                ptr = unsafe { ptr.add(1) };
388                len += ((byte & 0x7f) as usize) << shift;
389                shift += 7;
390            }
391        }
392    }
393}
394
395// SAFETY: repr must be in the heap allocated representation, with varint header
396// and string contents already written.
397unsafe fn ptr_as_str(repr: &NonNull<u8>) -> &str {
398    let ptr = repr_to_ptr(*repr);
399    let len = unsafe { decode_len(ptr) };
400    let header = bytes_for_varint(len);
401    let slice = unsafe { slice::from_raw_parts(ptr.add(header), len.get()) };
402    // SAFETY: all identifier contents are ASCII bytes, which are always valid
403    // UTF-8.
404    unsafe { str::from_utf8_unchecked(slice) }
405}
406
407// Number of base-128 digits required for the varint representation of a length.
408fn bytes_for_varint(len: NonZeroUsize) -> usize {
409    let usize_bits = mem::size_of::<usize>() * 8;
410    let len_bits = usize_bits - len.leading_zeros() as usize;
411    (len_bits + 6) / 7
412}