typedflake/
encoding.rs

1//! Compact text form of IDs in a configurable alphabet.
2//!
3//! Everything here is pure, and decoding ends in the same validation as every
4//! other constructor.
5
6use core::fmt;
7use core::ops::Deref;
8
9use crate::id::{self, Id, InvalidId, Repr};
10
11/// Characters an alphabet may use: printable ASCII without the space.
12const FIRST_CHAR: u8 = b'!';
13const LAST_CHAR: u8 = b'~';
14const MAX_CHARS: usize = (LAST_CHAR - FIRST_CHAR) as usize + 1;
15
16/// Marks a byte that is not in the alphabet.
17const NO_DIGIT: u8 = u8::MAX;
18
19/// Longest encoding: a 64-bit value in a two-character alphabet.
20const MAX_ENCODED_LEN: usize = 64;
21
22/// The characters an ID is written with, one per digit.
23///
24/// The number of characters is the base: [`BASE62`](Self::BASE62) writes IDs
25/// in base 62. Give an ID type an alphabet with the `alphabet` option of
26/// [`#[typedflake]`](macro@crate::typedflake) to get `encode` and `decode`:
27///
28/// ```
29/// use typedflake::{Alphabet, typedflake};
30///
31/// // Digits and lowercase letters, without the easily confused `0`, `1`, `i`, `l`, and `o`.
32/// pub const FRIENDLY: Alphabet = Alphabet::new("23456789abcdefghjkmnpqrstuvwxyz");
33///
34/// #[typedflake(epoch = "2025-01-01", alphabet = FRIENDLY)]
35/// pub struct InviteId(i64);
36///
37/// let id = InviteId::try_from(232_900_560_974_681_078_i64)?;
38/// let text = id.encode();
39///
40/// assert_eq!(text.as_str(), "2b76swcw35egs");
41/// assert_eq!(InviteId::decode(&text)?, id);
42/// # Ok::<(), Box<dyn std::error::Error>>(())
43/// ```
44///
45/// Every ID of a type encodes to the same number of characters. When the
46/// alphabet lists its characters in ascending ASCII order, as the presets do,
47/// encoded IDs sort the same way the IDs do.
48#[derive(Clone, Copy, PartialEq, Eq)]
49pub struct Alphabet {
50    chars: [u8; MAX_CHARS],
51    base: u8,
52    /// Digit of each ASCII byte, or `NO_DIGIT`.
53    digits: [u8; 128],
54}
55
56impl Alphabet {
57    /// Digits, then lowercase letters.
58    pub const BASE36: Self = Self::new("0123456789abcdefghijklmnopqrstuvwxyz");
59
60    /// The Bitcoin alphabet: no `0`, `O`, `I`, or `l`.
61    pub const BASE58: Self =
62        Self::new("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz");
63
64    /// Digits, uppercase letters, then lowercase letters.
65    pub const BASE62: Self =
66        Self::new("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
67
68    /// The 64 URL-safe characters of base64url, in ascending ASCII order so
69    /// that encoded IDs stay sortable.
70    ///
71    /// This is not the base64 encoding of the ID's bytes, and a base64 decoder
72    /// will not read it. Its zero digit is `-`, so encoded IDs can start with
73    /// a hyphen.
74    pub const BASE64_URL: Self =
75        Self::new("-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz");
76
77    /// Creates an alphabet from its characters, in digit order: the first
78    /// character is zero.
79    ///
80    /// # Panics
81    ///
82    /// Panics unless `chars` holds between 2 and 94 distinct printable ASCII
83    /// characters, without spaces. In a const context this is a compile-time
84    /// error.
85    pub const fn new(chars: &str) -> Self {
86        let bytes = chars.as_bytes();
87        assert!(bytes.len() >= 2, "an alphabet needs at least 2 characters");
88        assert!(
89            bytes.len() <= MAX_CHARS,
90            "an alphabet holds at most 94 characters"
91        );
92
93        let mut alphabet = Self {
94            chars: [0; MAX_CHARS],
95            base: bytes.len() as u8,
96            digits: [NO_DIGIT; 128],
97        };
98        let mut digit = 0;
99        while digit < bytes.len() {
100            let byte = bytes[digit];
101            assert!(
102                byte >= FIRST_CHAR && byte <= LAST_CHAR,
103                "alphabet characters must be printable ASCII, without spaces"
104            );
105            assert!(
106                alphabet.digits[byte as usize] == NO_DIGIT,
107                "alphabet characters must not repeat"
108            );
109            alphabet.chars[digit] = byte;
110            alphabet.digits[byte as usize] = digit as u8;
111            digit += 1;
112        }
113        alphabet
114    }
115
116    /// The characters, in digit order.
117    pub fn as_str(&self) -> &str {
118        ascii_str(&self.chars[..usize::from(self.base)])
119    }
120
121    /// Number of characters needed to write any value up to `max`.
122    #[doc(hidden)]
123    pub const fn __encoded_len(&self, max: u64) -> usize {
124        let base = self.base as u64;
125        let mut len = 1;
126        let mut rest = max / base;
127        while rest > 0 {
128            len += 1;
129            rest /= base;
130        }
131        len
132    }
133
134    /// `base` is passed separately from `self` so a caller that knows it at
135    /// compile time gets its divisions compiled as multiplications or shifts.
136    #[inline]
137    fn encode(&self, base: u64, len: usize, mut value: u64) -> Encoded {
138        let mut bytes = [0; MAX_ENCODED_LEN];
139        for byte in bytes[..len].iter_mut().rev() {
140            *byte = self.chars[(value % base) as usize];
141            value /= base;
142        }
143        debug_assert_eq!(value, 0);
144        Encoded {
145            bytes,
146            len: len as u8,
147        }
148    }
149
150    #[inline]
151    fn decode(&self, base: u64, len: usize, text: &str) -> Result<u64, DecodeIdError> {
152        if text.len() != len {
153            return Err(DecodeIdError::Length {
154                expected: len,
155                found: text.len(),
156            });
157        }
158
159        let mut value: u64 = 0;
160        for (index, byte) in text.bytes().enumerate() {
161            let digit = match self.digits.get(usize::from(byte)) {
162                Some(&digit) if digit != NO_DIGIT => u64::from(digit),
163                _ => return Err(DecodeIdError::Character { index }),
164            };
165            value = value
166                .checked_mul(base)
167                .and_then(|value| value.checked_add(digit))
168                .ok_or(DecodeIdError::Overflow)?;
169        }
170        Ok(value)
171    }
172}
173
174impl fmt::Debug for Alphabet {
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        f.debug_tuple("Alphabet").field(&self.as_str()).finish()
177    }
178}
179
180/// Alphabets and encodings only ever hold ASCII bytes.
181fn ascii_str(bytes: &[u8]) -> &str {
182    debug_assert!(bytes.is_ascii());
183    core::str::from_utf8(bytes).unwrap_or_default()
184}
185
186/// An ID type with an alphabet, declared with the `alphabet` option of
187/// [`#[typedflake]`](macro@crate::typedflake).
188///
189/// Its methods are also generated as inherent methods, so the trait only needs
190/// importing for code that is generic over ID types.
191#[diagnostic::on_unimplemented(
192    message = "`{Self}` has no alphabet",
193    label = "this ID type cannot be encoded",
194    note = "add `alphabet = ...` to its `#[typedflake(...)]` attribute"
195)]
196pub trait EncodedId: Id {
197    /// Alphabet this ID type is written with.
198    const ALPHABET: Alphabet;
199
200    #[doc(hidden)]
201    const __ENCODED_LEN: usize = Self::ALPHABET.__encoded_len(Self::__LAYOUT.raw_max);
202
203    #[doc(hidden)]
204    const __BASE: u64 = Self::ALPHABET.base as u64;
205
206    /// Writes the ID in its alphabet, without allocating.
207    ///
208    /// Every ID of the type has the same length: shorter values are padded
209    /// with the alphabet's first character.
210    fn encode(self) -> Encoded {
211        const { &Self::ALPHABET }.encode(Self::__BASE, Self::__ENCODED_LEN, self.get().__bits())
212    }
213
214    /// Reads an ID written by [`encode`](Self::encode).
215    ///
216    /// Only that exact form is accepted, so each ID has a single encoding.
217    fn decode(text: &str) -> Result<Self, DecodeIdError> {
218        let raw = const { &Self::ALPHABET }.decode(Self::__BASE, Self::__ENCODED_LEN, text)?;
219        Ok(id::from_u64(raw)?)
220    }
221}
222
223/// An ID written in its alphabet. Returned by `encode`.
224///
225/// It lives on the stack and reads as a `&str`.
226#[derive(Clone, Copy, PartialEq, Eq, Hash)]
227pub struct Encoded {
228    bytes: [u8; MAX_ENCODED_LEN],
229    len: u8,
230}
231
232impl Encoded {
233    /// The encoded ID.
234    pub fn as_str(&self) -> &str {
235        ascii_str(&self.bytes[..usize::from(self.len)])
236    }
237}
238
239impl Deref for Encoded {
240    type Target = str;
241
242    fn deref(&self) -> &str {
243        self.as_str()
244    }
245}
246
247impl AsRef<str> for Encoded {
248    fn as_ref(&self) -> &str {
249        self.as_str()
250    }
251}
252
253impl fmt::Display for Encoded {
254    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
255        f.write_str(self.as_str())
256    }
257}
258
259impl fmt::Debug for Encoded {
260    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
261        fmt::Debug::fmt(self.as_str(), f)
262    }
263}
264
265/// A string could not be decoded as an ID.
266#[derive(Debug, Clone, Copy, PartialEq, Eq)]
267#[non_exhaustive]
268pub enum DecodeIdError {
269    /// The string does not have the length every encoded ID of this type has.
270    Length {
271        /// Length of an encoded ID, in bytes.
272        expected: usize,
273        /// Length of the string that was supplied, in bytes.
274        found: usize,
275    },
276    /// The string has a character that is not in the alphabet.
277    Character {
278        /// Byte position of the character.
279        index: usize,
280    },
281    /// The string encodes a number that does not fit in 64 bits.
282    Overflow,
283    /// The decoded integer is not a valid ID for the format.
284    Invalid(InvalidId),
285}
286
287impl fmt::Display for DecodeIdError {
288    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
289        match *self {
290            Self::Length { expected, found } => write!(
291                f,
292                "encoded ID has {found} characters; this ID type uses {expected}"
293            ),
294            Self::Character { index } => write!(
295                f,
296                "character at position {index} is not in the ID's alphabet"
297            ),
298            Self::Overflow => f.write_str("encoded ID does not fit in 64 bits"),
299            Self::Invalid(_) => f.write_str("decoded integer is not a valid ID"),
300        }
301    }
302}
303
304impl std::error::Error for DecodeIdError {
305    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
306        match self {
307            Self::Invalid(error) => Some(error),
308            _ => None,
309        }
310    }
311}
312
313impl From<InvalidId> for DecodeIdError {
314    fn from(error: InvalidId) -> Self {
315        Self::Invalid(error)
316    }
317}
318
319#[cfg(test)]
320mod tests {
321    use super::*;
322
323    #[test]
324    fn presets_have_their_base_and_ascending_characters() {
325        for (alphabet, base) in [
326            (Alphabet::BASE36, 36),
327            (Alphabet::BASE58, 58),
328            (Alphabet::BASE62, 62),
329            (Alphabet::BASE64_URL, 64),
330        ] {
331            assert_eq!(alphabet.as_str().len(), base);
332            assert!(alphabet.as_str().as_bytes().is_sorted());
333        }
334    }
335
336    #[test]
337    fn encoded_length_covers_the_largest_value() {
338        let binary = Alphabet::new("01");
339        assert_eq!(binary.__encoded_len(0), 1);
340        assert_eq!(binary.__encoded_len(1), 1);
341        assert_eq!(binary.__encoded_len(2), 2);
342        assert_eq!(binary.__encoded_len(u64::MAX), 64);
343
344        assert_eq!(Alphabet::BASE62.__encoded_len(61), 1);
345        assert_eq!(Alphabet::BASE62.__encoded_len(62), 2);
346        assert_eq!(Alphabet::BASE62.__encoded_len(i64::MAX as u64), 11);
347        assert_eq!(Alphabet::BASE62.__encoded_len(u64::MAX), 11);
348        assert_eq!(Alphabet::BASE64_URL.__encoded_len(u64::MAX), 11);
349        assert_eq!(Alphabet::BASE64_URL.__encoded_len((1 << 60) - 1), 10);
350    }
351
352    #[test]
353    fn values_round_trip_at_the_edges_of_every_width() {
354        let widest = Alphabet::new(
355            "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
356        );
357        for alphabet in [Alphabet::new("01"), Alphabet::BASE62, widest] {
358            for max in [1, 61, 62, 4095, i64::MAX as u64, u64::MAX] {
359                let len = alphabet.__encoded_len(max);
360                for value in [0, 1, max / 2, max - 1, max] {
361                    let text = alphabet.encode(u64::from(alphabet.base), len, value);
362                    assert_eq!(text.len(), len);
363                    assert_eq!(
364                        alphabet.decode(u64::from(alphabet.base), len, &text),
365                        Ok(value)
366                    );
367                }
368            }
369        }
370    }
371
372    #[test]
373    fn decoding_rejects_anything_encode_does_not_write() {
374        let alphabet = Alphabet::BASE62;
375
376        assert_eq!(
377            alphabet.decode(62, 3, "0A"),
378            Err(DecodeIdError::Length {
379                expected: 3,
380                found: 2
381            })
382        );
383        assert_eq!(
384            alphabet.decode(62, 3, "0-A"),
385            Err(DecodeIdError::Character { index: 1 })
386        );
387        // Two bytes, so the length already matches a different string.
388        assert_eq!(
389            alphabet.decode(62, 3, "0é"),
390            Err(DecodeIdError::Character { index: 1 })
391        );
392        assert_eq!(
393            alphabet.decode(62, 11, "zzzzzzzzzzz"),
394            Err(DecodeIdError::Overflow)
395        );
396    }
397
398    #[test]
399    #[should_panic(expected = "must not repeat")]
400    fn repeated_characters_are_rejected() {
401        let _ = Alphabet::new("abca");
402    }
403
404    #[test]
405    #[should_panic(expected = "printable ASCII")]
406    fn spaces_are_rejected() {
407        let _ = Alphabet::new("a b");
408    }
409
410    #[test]
411    #[should_panic(expected = "at least 2")]
412    fn a_single_character_is_rejected() {
413        let _ = Alphabet::new("a");
414    }
415}
typedflake/encoding.rs

typedflake/
encoding.rs
