Skip to main content

utf_types/
utf8.rs

1// Copyright Mozilla Foundation
2//
3// Licensed under the Apache License (Version 2.0), or the MIT license,
4// (the "Licenses") at your option. You may not use this file except in
5// compliance with one of the Licenses. You may obtain copies of the
6// Licenses at:
7//
8//    https://www.apache.org/licenses/LICENSE-2.0
9//    https://opensource.org/licenses/MIT
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the Licenses is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the Licenses for the specific language governing permissions and
15// limitations under the Licenses.
16
17//! Types for UTF-8 code unit sequences and their parts.
18
19/// A type for signaling UTF-8 errors.
20#[derive(Debug, PartialEq, Clone, Copy, Hash, Eq)]
21#[non_exhaustive]
22pub struct Utf8ByteError;
23
24impl core::fmt::Display for Utf8ByteError {
25    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> Result<(), core::fmt::Error> {
26        write!(f, "byte does not fit the requested position in UTF-8")
27    }
28}
29
30impl core::error::Error for Utf8ByteError {}
31
32#[repr(align(64))] // Align to cache lines
33struct Utf8Data {
34    table: [u8; 384],
35}
36
37impl Utf8Data {
38    /// The table lookup for backing prefix checks.
39    ///
40    /// # Safety-usable invariant
41    ///
42    /// The return value is 0 iff `first` and `second` form a prefix of a
43    /// well-formed multi-byte UTF-8 sequence (including a complete two-byte
44    /// sequence).
45    /// The lowest two bits are always 0.
46    #[inline(always)]
47    const fn lookup(&self, first: u8, second: u8) -> u8 {
48        self.table[second as usize] & self.table[first as usize + 0x80]
49    }
50}
51
52/// The first 256 entries are for looking up `second`.
53/// The rest are for looking up `first` on the assumption
54/// that `first` is not ASCII.
55///
56/// Lanes 0 and 1 are left unused to allow the tag
57/// bits of the third byte in a three-byte sequence
58/// to be shifted there for a single-branch comparison.
59static UTF8_DATA: Utf8Data = Utf8Data {
60    table: const {
61        let mut table = [0u8; 384];
62
63        // Trails
64        let mut i = 0u16;
65        while i < 0x100 {
66            let second = i as u8;
67            // If a `second` is valid given a lane, we leave a lane as zero.
68            // We put 1 on the lane if the `second` is invalid given a lane.
69            let mut combined = 1 << 2; // invalid lead
70            if second < 0x80 || second > 0xBF {
71                combined |= 1 << 3; // normal trail
72            }
73            if second < 0xA0 || second > 0xBF {
74                combined |= 1 << 4; // three-byte special lower bound
75            }
76            if second < 0x80 || second > 0x9F {
77                combined |= 1 << 5; // three-byte special upper bound
78            }
79            if second < 0x90 || second > 0xBF {
80                combined |= 1 << 6; // four-byte special lower bound
81            }
82            if second < 0x80 || second > 0x8F {
83                combined |= 1 << 7; // four-byte special upper bound
84            }
85            table[second as usize] = combined;
86            i += 1;
87        }
88
89        // Non-ASCII leads
90        i = 0x80;
91        while i < 0x100 {
92            let first = i as u8;
93            let lane = match first {
94                0xC2..=0xDF | 0xE1..=0xEC | 0xEE..=0xEF | 0xF1..=0xF3 => {
95                    1 << 3 // normal trail
96                }
97                0xE0 => {
98                    1 << 4 // three-byte special lower bound
99                }
100                0xED => {
101                    1 << 5 // three-byte special upper bound
102                }
103                0xF0 => {
104                    1 << 6 // four-byte special lower bound
105                }
106                0xF4 => {
107                    1 << 7 // four-byte special upper bound
108                }
109                _ => {
110                    // invalid lead
111                    1 << 2
112                }
113            };
114            table[0x80 + first as usize] = lane;
115            i += 1;
116        }
117
118        // We didn't explicitly generate table entries that are
119        // looked up when `first` is ASCII. However, from the construction
120        // of the entries for trails, the overlapping part ends up with
121        // suitable values. Let's verify that.
122        i = 0;
123        while i < 0x80 {
124            if table[0x80 + i as usize] & (1 << 2) == 0 {
125                panic!();
126            }
127            i += 1;
128        }
129
130        table
131    },
132};
133
134// `Ascii` and `NonAscii` benefit from `enum` representation, because it communicates
135// integer range information e.g. when they are used for table lookup.
136//
137// It's unclear if the other types benefit from communicating range information
138// to the optimizer, but they enable niches anyway.
139
140macro_rules! byte_methods {
141    ($type_specific_ident:ident,
142     $(#[$unchecked_meta:meta])*,
143     $(#[$checked_meta:meta])*,
144    ) => {
145        /// Whether `byte` is in range for this type.
146        ///
147        /// # Safety-usable invariant
148        ///
149        /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
150        /// is satisfied.
151        #[inline(always)]
152        pub const fn is(byte: u8) -> bool {
153            byte >= Self::MIN.to_u8() && byte <= Self::MAX.to_u8()
154        }
155
156        $(#[$unchecked_meta])*
157        #[inline(always)]
158        pub const unsafe fn new_unchecked($type_specific_ident: u8) -> Self {
159            debug_assert!(Self::is($type_specific_ident));
160            // SAFETY: Our `repr(u8)` matches argument `u8` size and the
161            // value range is this function's safety invariant.
162            unsafe { core::mem::transmute($type_specific_ident) }
163        }
164
165        $(#[$checked_meta])*
166        #[inline(always)]
167        pub const fn try_new(byte: u8) -> Result<Self, Utf8ByteError> {
168            if Self::is(byte) {
169                // SAFETY: We checked the safety invariant immediately above.
170                Ok(unsafe { Self::new_unchecked(byte) })
171            } else {
172                Err(Utf8ByteError)
173            }
174        }
175
176        /// Convert to plain byte
177        #[inline(always)]
178        pub const fn to_u8(self) -> u8 {
179            self as u8
180        }
181    };
182}
183
184macro_rules! to_non_ascii {
185    () => {
186        /// Convert to `NonAscii`
187        #[inline(always)]
188        pub const fn to_non_ascii(self) -> NonAscii {
189            match NonAscii::try_new(self.to_u8()) {
190                Ok(non_ascii) => non_ascii,
191                Err(_) => {
192                    // `Self` has a stricter `enum` value space
193                    // than the target type.
194                    unreachable!();
195                }
196            }
197        }
198    };
199}
200
201macro_rules! to_lead_for_multi_byte {
202    () => {
203        to_non_ascii!();
204
205        /// Convert to `LeadForMultiByte`
206        #[inline(always)]
207        pub const fn to_lead_for_multi_byte(self) -> LeadForMultiByte {
208            match LeadForMultiByte::try_new(self.to_u8()) {
209                Ok(lead) => lead,
210                Err(_) => {
211                    // `Self` has a stricter `enum` value space
212                    // than the target type.
213                    unreachable!();
214                }
215            }
216        }
217    };
218}
219
220macro_rules! byte_impls {
221    ($type:ident,
222     $type_specific_ident:ident,
223    ) => {
224        impl TryFrom<u8> for $type {
225            type Error = Utf8ByteError;
226
227            #[inline(always)]
228            fn try_from(byte: u8) -> Result<Self, Utf8ByteError> {
229                Self::try_new(byte)
230            }
231        }
232
233        impl From<$type> for u8 {
234            #[inline(always)]
235            fn from($type_specific_ident: $type) -> Self {
236                $type_specific_ident.to_u8()
237            }
238        }
239    };
240}
241
242macro_rules! non_ascii_impls {
243    ($type:ident,
244     $type_specific_ident:ident,
245    ) => {
246        impl TryFrom<NonAscii> for $type {
247            type Error = Utf8ByteError;
248
249            #[inline(always)]
250            fn try_from(non_ascii: NonAscii) -> Result<Self, Utf8ByteError> {
251                Self::try_new(non_ascii.to_u8())
252            }
253        }
254
255        impl From<$type> for NonAscii {
256            #[inline(always)]
257            fn from($type_specific_ident: $type) -> Self {
258                $type_specific_ident.to_non_ascii()
259            }
260        }
261    };
262}
263
264macro_rules! lead_impls {
265    ($type:ident,
266) => {
267        non_ascii_impls!($type, lead,);
268
269        impl TryFrom<LeadForMultiByte> for $type {
270            type Error = Utf8ByteError;
271
272            #[inline(always)]
273            fn try_from(lead: LeadForMultiByte) -> Result<Self, Utf8ByteError> {
274                Self::try_new(lead.to_u8())
275            }
276        }
277
278        impl From<$type> for LeadForMultiByte {
279            #[inline(always)]
280            fn from(lead: $type) -> Self {
281                lead.to_lead_for_multi_byte()
282            }
283        }
284    };
285}
286
287macro_rules! sequence_methods {
288    ($(#[$as_bytes_meta:meta])*,
289     $(#[$as_str_meta:meta])*,
290    ) => {
291        $(#[$as_bytes_meta])*
292        #[inline(always)]
293        pub const fn as_bytes(&self) -> &[u8; Self::LEN] {
294            if core::mem::size_of::<Self>() != Self::LEN {
295                panic!();
296            }
297            let ptr: *const Self = core::ptr::from_ref(self);
298            // SAFETY: The `repr` of `Self` guarantees that it
299            // is safe to view `Self` as a sequence of `u8`, that
300            // the `u8`s are in the right order, and that the
301            // size of `Self` matches the length in the return type.
302            unsafe {
303                &*ptr.cast()
304            }
305        }
306
307        $(#[$as_str_meta])*
308        #[inline(always)]
309        pub const fn as_str(&self) -> &str {
310            // SAFETY: The safety-usable invariant of `as_bytes()` satisfies
311            // the safety invariant of `from_utf8_unchecked()`.
312            unsafe { core::str::from_utf8_unchecked(self.as_bytes()) }
313        }
314    };
315}
316
317/// For making sure that reviewing this file is sufficient for
318/// reviewing the implementations of `Utf8ByteSequence`.
319trait Seal {}
320
321/// Marker trait for all four UTF-8 byte sequences
322#[allow(private_bounds)] // allow sealing
323pub trait Utf8ByteSequence: Seal + Copy + Clone + Into<char> + AsRef<str> {}
324
325macro_rules! sequence_impls {
326    ($type:ident,
327     $type_specific_ident:ident,
328    ) => {
329        impl Seal for $type {}
330
331        impl Utf8ByteSequence for $type {}
332
333        impl From<$type> for char {
334            #[inline(always)]
335            fn from($type_specific_ident: $type) -> Self {
336                $type_specific_ident.to_char()
337            }
338        }
339
340        impl AsRef<str> for $type {
341            #[inline(always)]
342            fn as_ref(&self) -> &str {
343                self.as_str()
344            }
345        }
346    };
347}
348
349/// A byte in the ASCII range (single-byte UTF-8 sequence).
350#[allow(missing_docs)]
351#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
352#[repr(u8)]
353pub enum Ascii {
354    B00 = 0x00,
355    B01 = 0x01,
356    B02 = 0x02,
357    B03 = 0x03,
358    B04 = 0x04,
359    B05 = 0x05,
360    B06 = 0x06,
361    B07 = 0x07,
362    B08 = 0x08,
363    B09 = 0x09,
364    B0a = 0x0a,
365    B0b = 0x0b,
366    B0c = 0x0c,
367    B0d = 0x0d,
368    B0e = 0x0e,
369    B0f = 0x0f,
370    B10 = 0x10,
371    B11 = 0x11,
372    B12 = 0x12,
373    B13 = 0x13,
374    B14 = 0x14,
375    B15 = 0x15,
376    B16 = 0x16,
377    B17 = 0x17,
378    B18 = 0x18,
379    B19 = 0x19,
380    B1a = 0x1a,
381    B1b = 0x1b,
382    B1c = 0x1c,
383    B1d = 0x1d,
384    B1e = 0x1e,
385    B1f = 0x1f,
386    B20 = 0x20,
387    B21 = 0x21,
388    B22 = 0x22,
389    B23 = 0x23,
390    B24 = 0x24,
391    B25 = 0x25,
392    B26 = 0x26,
393    B27 = 0x27,
394    B28 = 0x28,
395    B29 = 0x29,
396    B2a = 0x2a,
397    B2b = 0x2b,
398    B2c = 0x2c,
399    B2d = 0x2d,
400    B2e = 0x2e,
401    B2f = 0x2f,
402    B30 = 0x30,
403    B31 = 0x31,
404    B32 = 0x32,
405    B33 = 0x33,
406    B34 = 0x34,
407    B35 = 0x35,
408    B36 = 0x36,
409    B37 = 0x37,
410    B38 = 0x38,
411    B39 = 0x39,
412    B3a = 0x3a,
413    B3b = 0x3b,
414    B3c = 0x3c,
415    B3d = 0x3d,
416    B3e = 0x3e,
417    B3f = 0x3f,
418    B40 = 0x40,
419    B41 = 0x41,
420    B42 = 0x42,
421    B43 = 0x43,
422    B44 = 0x44,
423    B45 = 0x45,
424    B46 = 0x46,
425    B47 = 0x47,
426    B48 = 0x48,
427    B49 = 0x49,
428    B4a = 0x4a,
429    B4b = 0x4b,
430    B4c = 0x4c,
431    B4d = 0x4d,
432    B4e = 0x4e,
433    B4f = 0x4f,
434    B50 = 0x50,
435    B51 = 0x51,
436    B52 = 0x52,
437    B53 = 0x53,
438    B54 = 0x54,
439    B55 = 0x55,
440    B56 = 0x56,
441    B57 = 0x57,
442    B58 = 0x58,
443    B59 = 0x59,
444    B5a = 0x5a,
445    B5b = 0x5b,
446    B5c = 0x5c,
447    B5d = 0x5d,
448    B5e = 0x5e,
449    B5f = 0x5f,
450    B60 = 0x60,
451    B61 = 0x61,
452    B62 = 0x62,
453    B63 = 0x63,
454    B64 = 0x64,
455    B65 = 0x65,
456    B66 = 0x66,
457    B67 = 0x67,
458    B68 = 0x68,
459    B69 = 0x69,
460    B6a = 0x6a,
461    B6b = 0x6b,
462    B6c = 0x6c,
463    B6d = 0x6d,
464    B6e = 0x6e,
465    B6f = 0x6f,
466    B70 = 0x70,
467    B71 = 0x71,
468    B72 = 0x72,
469    B73 = 0x73,
470    B74 = 0x74,
471    B75 = 0x75,
472    B76 = 0x76,
473    B77 = 0x77,
474    B78 = 0x78,
475    B79 = 0x79,
476    B7a = 0x7a,
477    B7b = 0x7b,
478    B7c = 0x7c,
479    B7d = 0x7d,
480    B7e = 0x7e,
481    B7f = 0x7f,
482}
483
484impl Ascii {
485    /// Minimum possible value.
486    pub const MIN: Self = Self::B00;
487
488    /// Maximum possible value.
489    pub const MAX: Self = Self::B7f;
490
491    /// The number of bytes in this kind of UTF-8 sequence.
492    pub const LEN: usize = 1;
493
494    byte_methods!(
495        ascii,
496        /// Unchecked constructor
497        ///
498        /// # Safety
499        ///
500        /// `ascii` must be < 0x80.
501        ///
502        /// # Panics
503        ///
504        /// When debug assertions are enabled, panics if the safety invariant
505        /// is not upheld.
506        ,
507        /// Fallible constructor
508        ///
509        /// `Ok` if ASCII and `Err` otherwise.
510        ,
511    );
512
513    /// Convert to `char`
514    #[inline(always)]
515    pub const fn to_char(self) -> char {
516        self as u8 as char
517    }
518
519    sequence_methods!(
520        /// View as `&[u8; 1]`
521        ///
522        /// # Safety-usable invariant
523        ///
524        /// The slice contains a single ASCII byte.
525        ,
526        /// View as `&str`
527        ///
528        /// # Safety-usable invariant
529        ///
530        /// The string slice contains a single ASCII byte/character.
531        ,
532    );
533}
534
535byte_impls!(Ascii, ascii,);
536
537sequence_impls!(Ascii, ascii,);
538
539/// A byte in the non-ASCII range.
540#[allow(missing_docs)]
541#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
542#[repr(u8)]
543pub enum NonAscii {
544    B80 = 0x80,
545    B81 = 0x81,
546    B82 = 0x82,
547    B83 = 0x83,
548    B84 = 0x84,
549    B85 = 0x85,
550    B86 = 0x86,
551    B87 = 0x87,
552    B88 = 0x88,
553    B89 = 0x89,
554    B8a = 0x8a,
555    B8b = 0x8b,
556    B8c = 0x8c,
557    B8d = 0x8d,
558    B8e = 0x8e,
559    B8f = 0x8f,
560    B90 = 0x90,
561    B91 = 0x91,
562    B92 = 0x92,
563    B93 = 0x93,
564    B94 = 0x94,
565    B95 = 0x95,
566    B96 = 0x96,
567    B97 = 0x97,
568    B98 = 0x98,
569    B99 = 0x99,
570    B9a = 0x9a,
571    B9b = 0x9b,
572    B9c = 0x9c,
573    B9d = 0x9d,
574    B9e = 0x9e,
575    B9f = 0x9f,
576    Ba0 = 0xa0,
577    Ba1 = 0xa1,
578    Ba2 = 0xa2,
579    Ba3 = 0xa3,
580    Ba4 = 0xa4,
581    Ba5 = 0xa5,
582    Ba6 = 0xa6,
583    Ba7 = 0xa7,
584    Ba8 = 0xa8,
585    Ba9 = 0xa9,
586    Baa = 0xaa,
587    Bab = 0xab,
588    Bac = 0xac,
589    Bad = 0xad,
590    Bae = 0xae,
591    Baf = 0xaf,
592    Bb0 = 0xb0,
593    Bb1 = 0xb1,
594    Bb2 = 0xb2,
595    Bb3 = 0xb3,
596    Bb4 = 0xb4,
597    Bb5 = 0xb5,
598    Bb6 = 0xb6,
599    Bb7 = 0xb7,
600    Bb8 = 0xb8,
601    Bb9 = 0xb9,
602    Bba = 0xba,
603    Bbb = 0xbb,
604    Bbc = 0xbc,
605    Bbd = 0xbd,
606    Bbe = 0xbe,
607    Bbf = 0xbf,
608    Bc0 = 0xc0,
609    Bc1 = 0xc1,
610    Bc2 = 0xc2,
611    Bc3 = 0xc3,
612    Bc4 = 0xc4,
613    Bc5 = 0xc5,
614    Bc6 = 0xc6,
615    Bc7 = 0xc7,
616    Bc8 = 0xc8,
617    Bc9 = 0xc9,
618    Bca = 0xca,
619    Bcb = 0xcb,
620    Bcc = 0xcc,
621    Bcd = 0xcd,
622    Bce = 0xce,
623    Bcf = 0xcf,
624    Bd0 = 0xd0,
625    Bd1 = 0xd1,
626    Bd2 = 0xd2,
627    Bd3 = 0xd3,
628    Bd4 = 0xd4,
629    Bd5 = 0xd5,
630    Bd6 = 0xd6,
631    Bd7 = 0xd7,
632    Bd8 = 0xd8,
633    Bd9 = 0xd9,
634    Bda = 0xda,
635    Bdb = 0xdb,
636    Bdc = 0xdc,
637    Bdd = 0xdd,
638    Bde = 0xde,
639    Bdf = 0xdf,
640    Be0 = 0xe0,
641    Be1 = 0xe1,
642    Be2 = 0xe2,
643    Be3 = 0xe3,
644    Be4 = 0xe4,
645    Be5 = 0xe5,
646    Be6 = 0xe6,
647    Be7 = 0xe7,
648    Be8 = 0xe8,
649    Be9 = 0xe9,
650    Bea = 0xea,
651    Beb = 0xeb,
652    Bec = 0xec,
653    Bed = 0xed,
654    Bee = 0xee,
655    Bef = 0xef,
656    Bf0 = 0xf0,
657    Bf1 = 0xf1,
658    Bf2 = 0xf2,
659    Bf3 = 0xf3,
660    Bf4 = 0xf4,
661    Bf5 = 0xf5,
662    Bf6 = 0xf6,
663    Bf7 = 0xf7,
664    Bf8 = 0xf8,
665    Bf9 = 0xf9,
666    Bfa = 0xfa,
667    Bfb = 0xfb,
668    Bfc = 0xfc,
669    Bfd = 0xfd,
670    Bfe = 0xfe,
671    Bff = 0xff,
672}
673
674impl NonAscii {
675    /// Minimum possible value.
676    pub const MIN: Self = Self::B80;
677
678    /// Maximum possible value.
679    pub const MAX: Self = Self::Bff;
680
681    byte_methods!(
682        non_ascii,
683        /// Unchecked constructor
684        ///
685        /// # Safety
686        ///
687        /// `non_ascii` must be >= 0x80.
688        ///
689        /// # Panics
690        ///
691        /// When debug assertions are enabled, panics if the safety invariant
692        /// is not upheld.
693        ,
694        /// Fallible constructor
695        ///
696        /// `Ok` if non-ASCII and `Err` otherwise.
697        ,
698    );
699}
700
701byte_impls!(NonAscii, non_ascii,);
702
703/// An unconstrained UTF-8 continuation byte (0x80 to 0xBF, inclusive)
704///
705/// Any continuation byte is valid as this type, but this type is not
706/// sufficiently constrained to guarantee validity as the second byte
707/// of a three-byte or four-byte sequence whose lead byte is 0xE0, 0xED,
708/// 0xF0, or 0xF4.
709#[allow(missing_docs)]
710#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
711#[repr(u8)]
712pub enum UnconstrainedContinuation {
713    B80 = 0x80,
714    B81 = 0x81,
715    B82 = 0x82,
716    B83 = 0x83,
717    B84 = 0x84,
718    B85 = 0x85,
719    B86 = 0x86,
720    B87 = 0x87,
721    B88 = 0x88,
722    B89 = 0x89,
723    B8a = 0x8a,
724    B8b = 0x8b,
725    B8c = 0x8c,
726    B8d = 0x8d,
727    B8e = 0x8e,
728    B8f = 0x8f,
729    B90 = 0x90,
730    B91 = 0x91,
731    B92 = 0x92,
732    B93 = 0x93,
733    B94 = 0x94,
734    B95 = 0x95,
735    B96 = 0x96,
736    B97 = 0x97,
737    B98 = 0x98,
738    B99 = 0x99,
739    B9a = 0x9a,
740    B9b = 0x9b,
741    B9c = 0x9c,
742    B9d = 0x9d,
743    B9e = 0x9e,
744    B9f = 0x9f,
745    Ba0 = 0xa0,
746    Ba1 = 0xa1,
747    Ba2 = 0xa2,
748    Ba3 = 0xa3,
749    Ba4 = 0xa4,
750    Ba5 = 0xa5,
751    Ba6 = 0xa6,
752    Ba7 = 0xa7,
753    Ba8 = 0xa8,
754    Ba9 = 0xa9,
755    Baa = 0xaa,
756    Bab = 0xab,
757    Bac = 0xac,
758    Bad = 0xad,
759    Bae = 0xae,
760    Baf = 0xaf,
761    Bb0 = 0xb0,
762    Bb1 = 0xb1,
763    Bb2 = 0xb2,
764    Bb3 = 0xb3,
765    Bb4 = 0xb4,
766    Bb5 = 0xb5,
767    Bb6 = 0xb6,
768    Bb7 = 0xb7,
769    Bb8 = 0xb8,
770    Bb9 = 0xb9,
771    Bba = 0xba,
772    Bbb = 0xbb,
773    Bbc = 0xbc,
774    Bbd = 0xbd,
775    Bbe = 0xbe,
776    Bbf = 0xbf,
777}
778
779impl UnconstrainedContinuation {
780    /// Minimum possible value.
781    pub const MIN: Self = Self::B80;
782
783    /// Maximum possible value.
784    pub const MAX: Self = Self::Bbf;
785
786    byte_methods!(
787        continuation,
788        /// Unchecked constructor
789        ///
790        /// # Safety
791        ///
792        /// `continuation` must be in the range 0x80 to 0xBF, inclusive.
793        ///
794        /// # Panics
795        ///
796        /// When debug assertions are enabled, panics if the safety invariant
797        /// is not upheld.
798        ,
799        /// Fallible constructor
800        ///
801        /// `Ok` if in the range 0x80 to 0xBF, inclusive, and `Err` otherwise.
802        ,
803    );
804
805    to_non_ascii!();
806
807    /// Obtain the least-significant six bits (i.e. the non-tag bits).
808    ///
809    /// # Safety-usable invariant
810    ///
811    /// Only the least-significant six bits can have non-zero values.
812    #[inline(always)]
813    pub const fn low_six(self) -> u8 {
814        self.to_u8() & 0b111_111
815    }
816
817    /// Obtain the least-significant six bits (i.e. the non-tag bits) as `u32`.
818    ///
819    /// # Safety-usable invariant
820    ///
821    /// Only the least-significant six bits can have non-zero values.
822    #[inline(always)]
823    pub const fn low_six_u32(self) -> u32 {
824        self.low_six() as u32
825    }
826}
827
828byte_impls!(UnconstrainedContinuation, continuation,);
829
830non_ascii_impls!(UnconstrainedContinuation, continuation,);
831
832/// A lead byte for a multibyte sequence (two-byte, three-byte, or
833/// four-byte).
834#[allow(missing_docs)]
835#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
836#[repr(u8)]
837pub enum LeadForMultiByte {
838    Bc2 = 0xc2,
839    Bc3 = 0xc3,
840    Bc4 = 0xc4,
841    Bc5 = 0xc5,
842    Bc6 = 0xc6,
843    Bc7 = 0xc7,
844    Bc8 = 0xc8,
845    Bc9 = 0xc9,
846    Bca = 0xca,
847    Bcb = 0xcb,
848    Bcc = 0xcc,
849    Bcd = 0xcd,
850    Bce = 0xce,
851    Bcf = 0xcf,
852    Bd0 = 0xd0,
853    Bd1 = 0xd1,
854    Bd2 = 0xd2,
855    Bd3 = 0xd3,
856    Bd4 = 0xd4,
857    Bd5 = 0xd5,
858    Bd6 = 0xd6,
859    Bd7 = 0xd7,
860    Bd8 = 0xd8,
861    Bd9 = 0xd9,
862    Bda = 0xda,
863    Bdb = 0xdb,
864    Bdc = 0xdc,
865    Bdd = 0xdd,
866    Bde = 0xde,
867    Bdf = 0xdf,
868    Be0 = 0xe0,
869    Be1 = 0xe1,
870    Be2 = 0xe2,
871    Be3 = 0xe3,
872    Be4 = 0xe4,
873    Be5 = 0xe5,
874    Be6 = 0xe6,
875    Be7 = 0xe7,
876    Be8 = 0xe8,
877    Be9 = 0xe9,
878    Bea = 0xea,
879    Beb = 0xeb,
880    Bec = 0xec,
881    Bed = 0xed,
882    Bee = 0xee,
883    Bef = 0xef,
884    Bf0 = 0xf0,
885    Bf1 = 0xf1,
886    Bf2 = 0xf2,
887    Bf3 = 0xf3,
888    Bf4 = 0xf4,
889}
890
891impl LeadForMultiByte {
892    /// Minimum possible value.
893    pub const MIN: Self = Self::Bc2;
894
895    /// Maximum possible value.
896    pub const MAX: Self = Self::Bf4;
897
898    byte_methods!(
899        lead,
900        /// Unchecked constructor
901        ///
902        /// # Safety
903        ///
904        /// `lead` must be in the range 0xC2 to 0xF4, inclusive.
905        ///
906        /// # Panics
907        ///
908        /// When debug assertions are enabled, panics if the safety invariant
909        /// is not upheld.
910        ,
911        /// Fallible constructor
912        ///
913        /// `Ok` if in the range 0xC2 to 0xF4, inclusive, and `Err` otherwise.
914        ,
915    );
916
917    to_non_ascii!();
918}
919
920byte_impls!(LeadForMultiByte, lead,);
921
922non_ascii_impls!(LeadForMultiByte, lead,);
923
924/// A lead byte for a two-byte UTF-8 sequence (0xC2 to 0xDF, inclusive)
925#[allow(missing_docs)]
926#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
927#[repr(u8)]
928pub enum LeadForTwoByte {
929    Bc2 = 0xc2,
930    Bc3 = 0xc3,
931    Bc4 = 0xc4,
932    Bc5 = 0xc5,
933    Bc6 = 0xc6,
934    Bc7 = 0xc7,
935    Bc8 = 0xc8,
936    Bc9 = 0xc9,
937    Bca = 0xca,
938    Bcb = 0xcb,
939    Bcc = 0xcc,
940    Bcd = 0xcd,
941    Bce = 0xce,
942    Bcf = 0xcf,
943    Bd0 = 0xd0,
944    Bd1 = 0xd1,
945    Bd2 = 0xd2,
946    Bd3 = 0xd3,
947    Bd4 = 0xd4,
948    Bd5 = 0xd5,
949    Bd6 = 0xd6,
950    Bd7 = 0xd7,
951    Bd8 = 0xd8,
952    Bd9 = 0xd9,
953    Bda = 0xda,
954    Bdb = 0xdb,
955    Bdc = 0xdc,
956    Bdd = 0xdd,
957    Bde = 0xde,
958    Bdf = 0xdf,
959}
960
961impl LeadForTwoByte {
962    /// Minimum possible value.
963    pub const MIN: Self = Self::Bc2;
964
965    /// Maximum possible value.
966    pub const MAX: Self = Self::Bdf;
967
968    byte_methods!(
969        lead,
970        /// Unchecked constructor
971        ///
972        /// # Safety
973        ///
974        /// `lead` must be in the range 0xC2 to 0xDF, inclusive.
975        ///
976        /// # Panics
977        ///
978        /// When debug assertions are enabled, panics if the safety invariant
979        /// is not upheld.
980        ,
981        /// Fallible constructor
982        ///
983        /// `Ok` if in the range 0xC2 to 0xDF, inclusive, and `Err` otherwise.
984        ,
985    );
986
987    to_lead_for_multi_byte!();
988
989    /// Obtain the least-significant five bits (i.e. the non-tag bits).
990    ///
991    /// # Safety-usable invariant
992    ///
993    /// Only the least-significant five bits can have non-zero values.
994    #[inline(always)]
995    pub const fn low_five(self) -> u8 {
996        self.to_u8() & 0b11_111
997    }
998
999    /// Obtain the least-significant five bits (i.e. the non-tag bits) as `u32`.
1000    ///
1001    /// # Safety-usable invariant
1002    ///
1003    /// Only the least-significant five bits can have non-zero values.
1004    #[inline(always)]
1005    pub const fn low_five_u32(self) -> u32 {
1006        self.low_five() as u32
1007    }
1008}
1009
1010byte_impls!(LeadForTwoByte, lead,);
1011
1012lead_impls!(LeadForTwoByte,);
1013
1014/// A lead byte for a three-byte UTF-8 sequence (0xE0 to 0xEF, inclusive)
1015#[allow(missing_docs)]
1016#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
1017#[repr(u8)]
1018pub enum LeadForThreeByte {
1019    Be0 = 0xe0,
1020    Be1 = 0xe1,
1021    Be2 = 0xe2,
1022    Be3 = 0xe3,
1023    Be4 = 0xe4,
1024    Be5 = 0xe5,
1025    Be6 = 0xe6,
1026    Be7 = 0xe7,
1027    Be8 = 0xe8,
1028    Be9 = 0xe9,
1029    Bea = 0xea,
1030    Beb = 0xeb,
1031    Bec = 0xec,
1032    Bed = 0xed,
1033    Bee = 0xee,
1034    Bef = 0xef,
1035}
1036
1037impl LeadForThreeByte {
1038    /// Minimum possible value.
1039    pub const MIN: Self = Self::Be0;
1040
1041    /// Maximum possible value.
1042    pub const MAX: Self = Self::Bef;
1043
1044    byte_methods!(
1045        lead,
1046        /// Unchecked constructor
1047        ///
1048        /// # Safety
1049        ///
1050        /// `lead` must be in the range 0xE0 to 0xEF, inclusive.
1051        ///
1052        /// # Panics
1053        ///
1054        /// When debug assertions are enabled, panics if the safety invariant
1055        /// is not upheld.
1056        ,
1057        /// Fallible constructor
1058        ///
1059        /// `Ok` if in the range 0xE0 to 0xEF, inclusive, and `Err` otherwise.
1060        ,
1061    );
1062
1063    to_lead_for_multi_byte!();
1064
1065    /// Obtain the least-significant four bits (i.e. the non-tag bits).
1066    ///
1067    /// # Safety-usable invariant
1068    ///
1069    /// Only the least-significant four bits can have non-zero values.
1070    #[inline(always)]
1071    pub const fn low_four(self) -> u8 {
1072        self.to_u8() & 0b1111
1073    }
1074
1075    /// Obtain the least-significant four bits (i.e. the non-tag bits) as `u32`.
1076    ///
1077    /// # Safety-usable invariant
1078    ///
1079    /// Only the least-significant four bits can have non-zero values.
1080    #[inline(always)]
1081    pub const fn low_four_u32(self) -> u32 {
1082        self.low_four() as u32
1083    }
1084}
1085
1086byte_impls!(LeadForThreeByte, lead,);
1087
1088lead_impls!(LeadForThreeByte,);
1089
1090/// A lead byte for a four-byte UTF-8 sequence (0xF0 to 0xF4, inclusive)
1091#[allow(missing_docs)]
1092#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
1093#[repr(u8)]
1094pub enum LeadForFourByte {
1095    Bf0 = 0xf0,
1096    Bf1 = 0xf1,
1097    Bf2 = 0xf2,
1098    Bf3 = 0xf3,
1099    Bf4 = 0xf4,
1100}
1101
1102impl LeadForFourByte {
1103    /// Minimum possible value.
1104    pub const MIN: Self = Self::Bf0;
1105
1106    /// Maximum possible value.
1107    pub const MAX: Self = Self::Bf4;
1108
1109    byte_methods!(
1110        lead,
1111        /// Unchecked constructor
1112        ///
1113        /// # Safety
1114        ///
1115        /// `lead` must be in the range 0xF0 to 0xF4, inclusive.
1116        ///
1117        /// # Panics
1118        ///
1119        /// When debug assertions are enabled, panics if the safety invariant
1120        /// is not upheld.
1121        ,
1122        /// Fallible constructor
1123        ///
1124        /// `Ok` if in the range 0xF0 to 0xF4, inclusive, and `Err` otherwise.
1125        ,
1126    );
1127
1128    to_lead_for_multi_byte!();
1129
1130    /// Obtain the least-significant three bits (i.e. the non-tag bits).
1131    ///
1132    /// # Safety-usable invariant
1133    ///
1134    /// Only the least-significant three bits can have non-zero values.
1135    #[inline(always)]
1136    pub const fn low_three(self) -> u8 {
1137        self.to_u8() & 0b111
1138    }
1139
1140    /// Obtain the least-significant three bits (i.e. the non-tag bits) as `u32`.
1141    ///
1142    /// # Safety-usable invariant
1143    ///
1144    /// Only the least-significant three bits can have non-zero values.
1145    #[inline(always)]
1146    pub const fn low_three_u32(self) -> u32 {
1147        self.low_three() as u32
1148    }
1149}
1150
1151byte_impls!(LeadForFourByte, lead,);
1152
1153lead_impls!(LeadForFourByte,);
1154
1155/// Two-byte UTF-8 sequence
1156#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
1157#[repr(C)]
1158pub struct TwoByteSequence {
1159    first: LeadForTwoByte,
1160    second: UnconstrainedContinuation,
1161}
1162
1163impl TwoByteSequence {
1164    /// The number of bytes in this kind of UTF-8 sequence.
1165    pub const LEN: usize = 2;
1166
1167    /// Whether `prepared` forms a well-formed two-byte UTF-8 sequence
1168    ///
1169    /// # Safety-usable invariant
1170    ///
1171    /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
1172    /// is satisfied.
1173    #[inline(always)]
1174    pub const fn is_with_prepared(prepared: PreparedTwoBytes) -> bool {
1175        // The low two bits of `check` are always zero, so we can shift it right by two
1176        // without data loss.
1177        // For `first` to be a two-byte lead byte, its top 3 bits have to be 110.
1178        // For `second` to be a continuation, `check` has to be zero.
1179        // We can let the third bit from the top overlap: It has to be zero for
1180        // both checks, so when we OR the checks together, if both sides succeed,
1181        // and it can be 1 only if either side fails.
1182        ((prepared.first & 0b1110_0000) | (prepared.check >> 2)) == 0b1100_0000
1183    }
1184
1185    /// Checks whether the bytes form a well-formed two-byte UTF-8 sequence.
1186    ///
1187    /// # Safety-usable invariant
1188    ///
1189    /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
1190    /// is satisfied.
1191    #[inline(always)]
1192    pub const fn is(first: u8, second: u8) -> bool {
1193        LeadForTwoByte::is(first) && UnconstrainedContinuation::is(second)
1194    }
1195
1196    /// Typed constructor
1197    #[inline(always)]
1198    pub const fn new(first: LeadForTwoByte, second: UnconstrainedContinuation) -> Self {
1199        Self { first, second }
1200    }
1201
1202    /// Unchecked constructor
1203    ///
1204    /// # Safety
1205    ///
1206    /// `first` and `second` must form a two-byte UTF-8 sequence.
1207    ///
1208    /// # Panics
1209    ///
1210    /// When debug assertions are enabled, panics if the safety invariant
1211    /// is not upheld.
1212    #[inline(always)]
1213    pub const unsafe fn new_unchecked(first: u8, second: u8) -> Self {
1214        debug_assert!(Self::is(first, second));
1215        // SAFETY: `first` and `second` are in the right ranges per the
1216        // safety invariant of this method.
1217        unsafe {
1218            Self {
1219                first: LeadForTwoByte::new_unchecked(first),
1220                second: UnconstrainedContinuation::new_unchecked(second),
1221            }
1222        }
1223    }
1224
1225    /// Fallible constructor
1226    ///
1227    /// `Ok` if `first` and `second` form a two-byte UTF-8 sequence and `Err` otherwise.
1228    #[inline(always)]
1229    pub const fn try_new(first: u8, second: u8) -> Result<Self, Utf8ByteError> {
1230        if Self::is(first, second) {
1231            // SAFETY: We checked the safety invariant immediately above.
1232            Ok(unsafe { Self::new_unchecked(first, second) })
1233        } else {
1234            Err(Utf8ByteError)
1235        }
1236    }
1237
1238    /// Fallible constructor with prepared bytes
1239    ///
1240    /// `Ok` if the prepared bytes form a two-byte UTF-8 sequence and `Err` otherwise.
1241    #[inline(always)]
1242    pub const fn try_new_with_prepared(prepared: PreparedTwoBytes) -> Result<Self, Utf8ByteError> {
1243        if Self::is_with_prepared(prepared) {
1244            // SAFETY: We checked the safety invariant immediately above.
1245            Ok(unsafe { Self::new_unchecked(prepared.first, prepared.second) })
1246        } else {
1247            Err(Utf8ByteError)
1248        }
1249    }
1250
1251    /// Convert to typed byte tuple.
1252    #[inline(always)]
1253    pub const fn to_typed_bytes(self) -> (LeadForTwoByte, UnconstrainedContinuation) {
1254        (self.first, self.second)
1255    }
1256
1257    /// Convert to `char`
1258    #[inline(always)]
1259    pub const fn to_char(self) -> char {
1260        let scalar = (self.first.low_five_u32() << 6) | self.second.low_six_u32();
1261        if let Some(c) = char::from_u32(scalar) {
1262            c
1263        } else {
1264            // The optimizer can see from the `enum` ranges that we
1265            // never reach this.
1266            unreachable!()
1267        }
1268    }
1269
1270    sequence_methods!(
1271        /// View as `&[u8; 2]`
1272        ///
1273        /// # Safety-usable invariant
1274        ///
1275        /// The bytes form a single well-formed two-byte UTF-8 sequence.
1276        ,
1277        /// View as `&str`
1278        ///
1279        /// # Safety-usable invariant
1280        ///
1281        /// The string slice contains a single two-byte UTF-8 sequence.
1282        ,
1283    );
1284}
1285
1286sequence_impls!(TwoByteSequence, two_byte,);
1287
1288/// Three-byte UTF-8 sequence
1289#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
1290#[repr(C)]
1291pub struct ThreeByteSequence {
1292    first: LeadForThreeByte,
1293    /// # Safety invariant
1294    ///
1295    /// `second` must be in the correct range given the value of
1296    /// `first` so that `first`, `second`, and `third` form a
1297    /// well-formed UTF-8 sequence.
1298    second: UnconstrainedContinuation,
1299    third: UnconstrainedContinuation,
1300}
1301
1302impl ThreeByteSequence {
1303    /// The number of bytes in this kind of UTF-8 sequence.
1304    pub const LEN: usize = 3;
1305
1306    /// Whether `prepared` forms a well-formed three-byte UTF-8 sequence.
1307    ///
1308    /// # Safety-usable invariant
1309    ///
1310    /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
1311    /// is satisfied.
1312    #[inline(always)]
1313    pub const fn is_with_prepared(prepared: PreparedThreeBytes) -> bool {
1314        // The top four bits of `first` have to be 1110 for `first` to
1315        // be a valid three-byte lead byte.
1316        // `check` must be 0b10 for `second` and `third` to be
1317        // contextually valid continuations assuming that `first`
1318        // is a three-byte lead byte.
1319        // Shifting masked `first` by 4 instead of 8 results
1320        // in a number to compare with that fits in an immediate
1321        // on aarch64. This is one instruction shorter on aarch64
1322        // than shifting the other part left the way it's shifted
1323        // in the four-byte case.
1324        ((((prepared.first & 0b1111_0000) as u16) << 4) | (prepared.check as u16))
1325            == 0b1110_0000_0010
1326    }
1327
1328    /// Whether the bytes form a well-formed three-byte UTF-8 sequence.
1329    ///
1330    /// # Safety-usable invariant
1331    ///
1332    /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
1333    /// is satisfied.
1334    #[inline(always)]
1335    pub const fn is(first: u8, second: u8, third: u8) -> bool {
1336        Self::is_with_prepared(PreparedThreeBytes::new(first, second, third))
1337    }
1338
1339    /// Unchecked constructor
1340    ///
1341    /// # Safety
1342    ///
1343    /// `first`, `second`, and `third` must form a three-byte UTF-8 sequence.
1344    ///
1345    /// # Panics
1346    ///
1347    /// When debug assertions are enabled, panics if the safety invariant
1348    /// is not upheld.
1349    #[inline(always)]
1350    pub const unsafe fn new_unchecked(first: u8, second: u8, third: u8) -> Self {
1351        debug_assert!(Self::is(first, second, third));
1352        // SAFETY: `first`, `second`, and `third` have values in the correct ranges per
1353        // the safety invariant of this method.
1354        unsafe {
1355            Self {
1356                first: LeadForThreeByte::new_unchecked(first),
1357                // INVARIANT UPHELD: From the safety invariant of this method.
1358                second: UnconstrainedContinuation::new_unchecked(second),
1359                third: UnconstrainedContinuation::new_unchecked(third),
1360            }
1361        }
1362    }
1363
1364    /// Fallible constructor
1365    ///
1366    /// `Ok` if `first`, `second`, and `third` form a three-byte UTF-8 sequence and `Err` otherwise.
1367    #[inline(always)]
1368    pub const fn try_new(first: u8, second: u8, third: u8) -> Result<Self, Utf8ByteError> {
1369        if Self::is(first, second, third) {
1370            // SAFETY: We checked the safety invariant immediately above.
1371            Ok(unsafe { Self::new_unchecked(first, second, third) })
1372        } else {
1373            Err(Utf8ByteError)
1374        }
1375    }
1376
1377    /// Fallible constructor with prepared bytes
1378    ///
1379    /// `Ok` if the prepared bytes form a three-byte UTF-8 sequence and `Err` otherwise.
1380    #[inline(always)]
1381    pub const fn try_new_with_prepared(
1382        prepared: PreparedThreeBytes,
1383    ) -> Result<Self, Utf8ByteError> {
1384        if Self::is_with_prepared(prepared) {
1385            // SAFETY: We checked the safety invariant immediately above.
1386            Ok(unsafe { Self::new_unchecked(prepared.first, prepared.second, prepared.third) })
1387        } else {
1388            Err(Utf8ByteError)
1389        }
1390    }
1391
1392    /// Convert to typed byte tuple.
1393    ///
1394    /// # Safety-usable invariant
1395    ///
1396    /// The tuple represents a well-formed three-byte UTF-8 sequence. In particular,
1397    /// the value of the second tuple item is within the permissible range given the
1398    /// value of the first tuple item.
1399    #[inline(always)]
1400    pub const fn to_typed_bytes(
1401        self,
1402    ) -> (
1403        LeadForThreeByte,
1404        UnconstrainedContinuation,
1405        UnconstrainedContinuation,
1406    ) {
1407        (self.first, self.second, self.third)
1408    }
1409
1410    /// Convert to `char`
1411    #[inline(always)]
1412    pub const fn to_char(self) -> char {
1413        let scalar = (self.first.low_four_u32() << 12)
1414            | (self.second.low_six_u32() << 6)
1415            | self.third.low_six_u32();
1416        debug_assert!(char::from_u32(scalar).is_some());
1417        // SAFETY: We distribute the bits in a way that forms
1418        // a valid scalar on the assumption that the bytes represent
1419        // a well-formed three-byte UTF-8 byte sequence.
1420        unsafe { char::from_u32_unchecked(scalar) }
1421    }
1422
1423    sequence_methods!(
1424        /// View as `&[u8; 3]`
1425        ///
1426        /// # Safety-usable invariant
1427        ///
1428        /// The bytes form a single well-formed three-byte UTF-8 sequence.
1429        ,
1430        /// View as `&str`
1431        ///
1432        /// # Safety-usable invariant
1433        ///
1434        /// The string slice contains a single three-byte UTF-8 sequence.
1435        ,
1436    );
1437}
1438
1439sequence_impls!(ThreeByteSequence, three_byte,);
1440
1441/// Four-byte UTF-8 sequence
1442#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
1443#[repr(C)]
1444pub struct FourByteSequence {
1445    first: LeadForFourByte,
1446    /// # Safety invariant
1447    ///
1448    /// `second` must be in the correct range given the value of
1449    /// `first` so that `first`, `second`, `third`, and `fourth`
1450    /// form a well-formed UTF-8 sequence.
1451    second: UnconstrainedContinuation,
1452    third: UnconstrainedContinuation,
1453    fourth: UnconstrainedContinuation,
1454}
1455
1456impl FourByteSequence {
1457    /// The number of bytes in this kind of UTF-8 sequence.
1458    pub const LEN: usize = 4;
1459
1460    /// Whether `prepared` and `fourth` form a well-formed four-byte UTF-8 sequence.
1461    ///
1462    /// # Safety-usable invariant
1463    ///
1464    /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
1465    /// is satisfied.
1466    #[inline(always)]
1467    pub const fn is_with_prepared(prepared: PreparedThreeBytes, fourth: u8) -> bool {
1468        // The top five bits of `first` have to be 11110 for `first` to
1469        // be a valid four-byte lead byte.
1470        // `check` must be 0b10 for `second` and `third` to be
1471        // contextually valid continuations assuming that `first`
1472        // is a four-byte lead byte.
1473        // The top two bits of `fourth` must be 10 for `fourth` to
1474        // be a valid continuation.
1475        // We shift `check` left, instead of the other way round to
1476        // make the comparison constant fit in an immediate on aarch64.
1477        // When the top two bits of `fourth` are shifted to be the low
1478        // two bits, they don't overlap with the top five bits from
1479        // `first`.
1480        (((prepared.check as u16) << 8) | (((prepared.first & 0b1111_1000) | (fourth >> 6)) as u16))
1481            == 0b10_1111_0010
1482    }
1483
1484    /// Whether the bytes form a well-formed four-byte UTF-8 sequence.
1485    ///
1486    /// # Safety-usable invariant
1487    ///
1488    /// Iff this method returns `true`, the safety invariant of `new_unchecked()`
1489    /// is satisfied.
1490    #[inline(always)]
1491    pub const fn is(first: u8, second: u8, third: u8, fourth: u8) -> bool {
1492        Self::is_with_prepared(PreparedThreeBytes::new(first, second, third), fourth)
1493    }
1494
1495    /// Unchecked constructor
1496    ///
1497    /// # Safety
1498    ///
1499    /// `first`, `second`, `third`, and `fourth` must form a four-byte UTF-8 sequence.
1500    ///
1501    /// # Panics
1502    ///
1503    /// When debug assertions are enabled, panics if the safety invariant
1504    /// is not upheld.
1505    #[inline(always)]
1506    pub const unsafe fn new_unchecked(first: u8, second: u8, third: u8, fourth: u8) -> Self {
1507        debug_assert!(Self::is(first, second, third, fourth));
1508        // SAFETY: `first`, `second`, `third`, and `fourth` have values in the correct ranges per
1509        // the safety invariant of this method.
1510        unsafe {
1511            Self {
1512                first: LeadForFourByte::new_unchecked(first),
1513                // INVARIANT UPHELD: From the safety invariant of this method.
1514                second: UnconstrainedContinuation::new_unchecked(second),
1515                third: UnconstrainedContinuation::new_unchecked(third),
1516                fourth: UnconstrainedContinuation::new_unchecked(fourth),
1517            }
1518        }
1519    }
1520
1521    /// Fallible constructor
1522    ///
1523    /// `Ok` if `first`, `second`, `third`, and `fourth` form a four-byte UTF-8 sequence and `Err` otherwise.
1524    #[inline(always)]
1525    pub const fn try_new(
1526        first: u8,
1527        second: u8,
1528        third: u8,
1529        fourth: u8,
1530    ) -> Result<Self, Utf8ByteError> {
1531        if Self::is(first, second, third, fourth) {
1532            // SAFETY: We checked the safety invariant immediately above.
1533            Ok(unsafe { Self::new_unchecked(first, second, third, fourth) })
1534        } else {
1535            Err(Utf8ByteError)
1536        }
1537    }
1538
1539    /// Fallible constructor with prepared bytes
1540    ///
1541    /// `Ok` if the prepared bytes and `fourth` form a four-byte UTF-8 sequence and `Err` otherwise.
1542    #[inline(always)]
1543    pub const fn try_new_with_prepared(
1544        prepared: PreparedThreeBytes,
1545        fourth: u8,
1546    ) -> Result<Self, Utf8ByteError> {
1547        if Self::is_with_prepared(prepared, fourth) {
1548            // SAFETY: We checked the safety invariant immediately above.
1549            Ok(unsafe {
1550                Self::new_unchecked(prepared.first, prepared.second, prepared.third, fourth)
1551            })
1552        } else {
1553            Err(Utf8ByteError)
1554        }
1555    }
1556
1557    /// Convert to typed byte tuple.
1558    ///
1559    /// # Safety-usable invariant
1560    ///
1561    /// The tuple represents a well-formed four-byte UTF-8 sequence. In particular,
1562    /// the value of the second tuple item is within the permissible range given the
1563    /// value of the first tuple item.
1564    #[inline(always)]
1565    pub const fn to_typed_bytes(
1566        self,
1567    ) -> (
1568        LeadForFourByte,
1569        UnconstrainedContinuation,
1570        UnconstrainedContinuation,
1571        UnconstrainedContinuation,
1572    ) {
1573        (self.first, self.second, self.third, self.fourth)
1574    }
1575
1576    /// Convert to `char`
1577    #[inline(always)]
1578    pub const fn to_char(self) -> char {
1579        let scalar = (self.first.low_three_u32() << 18)
1580            | (self.second.low_six_u32() << 12)
1581            | (self.third.low_six_u32() << 6)
1582            | self.fourth.low_six_u32();
1583        debug_assert!(char::from_u32(scalar).is_some());
1584        // SAFETY: We distribute the bits in a way that forms
1585        // a valid scalar on the assumption that the bytes represent
1586        // a well-formed four-byte UTF-8 byte sequence.
1587        unsafe { char::from_u32_unchecked(scalar) }
1588    }
1589
1590    sequence_methods!(
1591        /// View as `&[u8; 4]`
1592        ///
1593        /// # Safety-usable invariant
1594        ///
1595        /// The bytes form a single well-formed four-byte UTF-8 sequence.
1596        ,
1597        /// View as `&str`
1598        ///
1599        /// # Safety-usable invariant
1600        ///
1601        /// The string slice contains a single four-byte UTF-8 sequence.
1602        ,
1603    );
1604}
1605
1606sequence_impls!(FourByteSequence, four_byte,);
1607
1608/// Wrapper for the first two bytes and a precomputed value.
1609#[derive(Debug, Clone, Copy, Eq, PartialEq)]
1610pub struct PreparedTwoBytes {
1611    first: u8,
1612    second: u8,
1613    /// # Safety invariant
1614    ///
1615    /// `check` is 0 iff `first` and `second` form a prefix
1616    /// of a well-formed multibyte UTF-8 sequence (including
1617    /// a complete two-byte sequence).
1618    /// The lowest 2 bits are always 0.
1619    check: u8,
1620}
1621
1622impl PreparedTwoBytes {
1623    /// Constructor
1624    ///
1625    /// `first` and `second` represent the first two bytes of a
1626    /// potential UTF-8 sequence for efficient checking for whether
1627    /// they actually form such a prefix.
1628    #[inline(always)]
1629    pub const fn new(first: u8, second: u8) -> Self {
1630        Self {
1631            first,
1632            second,
1633            // INVARIANT UPHELD: The safety-usable invariant of
1634            // `lookup()` satisfies the invariant of this field.
1635            check: UTF8_DATA.lookup(first, second),
1636        }
1637    }
1638
1639    /// `true` iff the two bytes form a prefix of a
1640    /// well-formed multi-byte UTF-8 sequence.
1641    ///
1642    /// # Safety-usable invariant
1643    ///
1644    /// Callers may depend on the above for safety.
1645    #[inline(always)]
1646    pub const fn sequence_prefix(self) -> bool {
1647        // Directly from the field invariant of `check`.
1648        // (The low two bits of `check` are zero in any case.
1649        // The high six bits are zero if this is a valid
1650        // prefix for any multibyte sequence.)
1651        self.check == 0
1652    }
1653}
1654
1655/// Wrapper for the first three bytes and a precomputed value.
1656#[derive(Debug, Clone, Copy, Eq, PartialEq)]
1657pub struct PreparedThreeBytes {
1658    first: u8,
1659    second: u8,
1660    third: u8,
1661    /// # Safety invariant
1662    ///
1663    /// If `first` is not a lead byte for a two-byte sequence,
1664    /// `check` is `0b10` iff `first`, `second`, and `third`
1665    /// form a well-formed three-byte UTF-8 sequence or a
1666    /// three-byte prefix of a four-byte UTF-8 sequence.
1667    /// (Establish that `first` is not a lead byte for a two-byte
1668    /// sequence when making use of `check`.)
1669    check: u8,
1670}
1671
1672impl PreparedThreeBytes {
1673    /// Constructor
1674    ///
1675    /// `first`, `second`, and `third` represent the first three bytes of a
1676    /// potential UTF-8 sequence for efficient checking for whether
1677    /// they actually form a prefix of a well-formed UTF-8 sequence.
1678    #[inline(always)]
1679    pub const fn new(first: u8, second: u8, third: u8) -> Self {
1680        Self::new_with_prepared(PreparedTwoBytes::new(first, second), third)
1681    }
1682
1683    /// Constructor with already-prepared first two bytes
1684    ///
1685    /// `prepared` and `third` represent the first three bytes of a
1686    /// potential UTF-8 sequence for efficient checking for whether
1687    /// they actually form a prefix of a well-formed UTF-8 sequence.
1688    #[inline(always)]
1689    pub const fn new_with_prepared(prepared: PreparedTwoBytes, third: u8) -> Self {
1690        Self {
1691            first: prepared.first,
1692            second: prepared.second,
1693            third,
1694            // INVARIANT UPHELD: The high two bits of `third` are 10 iff
1695            // it is a continuation byte. We put these in the low two bits
1696            // of `check`. We get the high six bits from `prepared.check`
1697            // whose field invariant guarantees that its low two bits are
1698            // always zero (and, therefore, don't conflict with our placement
1699            // of the new bits) and that the high six bits are zero iff
1700            // `first` and `second` are part of a well-formed prefix.
1701            check: prepared.check | (third >> 6),
1702        }
1703    }
1704
1705    /// Return `true` iff these three bytes represent a three-byte
1706    /// prefix of a well-formed four-byte UTF-8 sequence.
1707    ///
1708    /// # Safety-usable invariant
1709    ///
1710    /// The caller may rely on the result for safety.
1711    #[inline(always)]
1712    pub const fn prefix_of_four_byte(self) -> bool {
1713        // The top five bits of `first` have to be 11110 for `first` to
1714        // be a valid four-byte lead byte.
1715        // From the field invariant, `check` must be 0b10 for `second`
1716        // and `third` to be contextually valid continuations assuming that
1717        // `first` is a four-byte lead byte.
1718        // We shift `check` left to use the structure of the full
1719        // four-byte check.
1720        (((self.check as u16) << 8) | ((self.first & 0b1111_1000) as u16)) == 0b10_1111_0000
1721    }
1722}
1723
1724// Any copyright to the test code below this comment is dedicated to the
1725// Public Domain. http://creativecommons.org/publicdomain/zero/1.0/
1726
1727#[cfg(test)]
1728mod tests {
1729    use super::*;
1730
1731    /// `true` iff `bytes` is well-formed UTF-8 consisting of exactly one
1732    /// scalar value.
1733    fn single_scalar_reference(bytes: &[u8]) -> bool {
1734        core::str::from_utf8(bytes).is_ok_and(|s| s.chars().count() == 1)
1735    }
1736
1737    fn two_byte_prefix_reference(first: u8, second: u8) -> bool {
1738        if !super::LeadForMultiByte::is(first) {
1739            return false;
1740        }
1741        let (lower_bound, upper_bound) = match first {
1742            0xE0 => (0xA0, 0xBF),
1743            0xED => (0x80, 0x9F),
1744            0xF0 => (0x90, 0xBF),
1745            0xF4 => (0x80, 0x8F),
1746            _ => (0x80, 0xBF),
1747        };
1748        lower_bound <= second && second <= upper_bound
1749    }
1750
1751    fn prefix_of_four_byte_reference(first: u8, second: u8, third: u8) -> bool {
1752        if !super::LeadForFourByte::is(first) {
1753            return false;
1754        }
1755        if !super::UnconstrainedContinuation::is(third) {
1756            return false;
1757        }
1758        let (lower_bound, upper_bound) = match first {
1759            0xE0 => (0xA0, 0xBF),
1760            0xED => (0x80, 0x9F),
1761            0xF0 => (0x90, 0xBF),
1762            0xF4 => (0x80, 0x8F),
1763            _ => (0x80, 0xBF),
1764        };
1765        lower_bound <= second && second <= upper_bound
1766    }
1767
1768    #[test]
1769    fn test_bytes() {
1770        for first in 0..=0xFF {
1771            let b = first;
1772            macro_rules! check_range {
1773                ($type:ident, $range:expr) => {
1774                    let in_range = $range.contains(&b);
1775                    assert_eq!($type::is(b), in_range);
1776                    assert_eq!(
1777                        $type::try_new(b).map($type::to_u8),
1778                        in_range.then_some(b).ok_or(Utf8ByteError)
1779                    );
1780                };
1781            }
1782            check_range!(Ascii, 0x00..=0x7F);
1783            check_range!(NonAscii, 0x80..=0xFF);
1784            check_range!(UnconstrainedContinuation, 0x80..=0xBF);
1785            check_range!(LeadForMultiByte, 0xC2..=0xF4);
1786            check_range!(LeadForTwoByte, 0xC2..=0xDF);
1787            check_range!(LeadForThreeByte, 0xE0..=0xEF);
1788            check_range!(LeadForFourByte, 0xF0..=0xF4);
1789
1790            if let Ok(ascii) = Ascii::try_new(b) {
1791                assert_eq!(ascii.to_char() as u32, b as u32);
1792                assert_eq!(ascii.as_bytes(), &[b]);
1793                assert_eq!(ascii.as_str().as_bytes(), &[b]);
1794            }
1795            if let Ok(non_ascii) = NonAscii::try_new(b) {
1796                assert_eq!(
1797                    UnconstrainedContinuation::try_from(non_ascii).map(|c| c.to_non_ascii()),
1798                    UnconstrainedContinuation::try_new(b).map(|c| c.to_non_ascii())
1799                );
1800                assert_eq!(
1801                    LeadForMultiByte::try_from(non_ascii).map(|l| l.to_non_ascii()),
1802                    LeadForMultiByte::try_new(b).map(|l| l.to_non_ascii())
1803                );
1804            }
1805            if let Ok(continuation) = UnconstrainedContinuation::try_new(b) {
1806                assert_eq!(continuation.low_six(), b & 0x3F);
1807                assert_eq!(continuation.to_non_ascii().to_u8(), b);
1808            }
1809            if let Ok(lead) = LeadForMultiByte::try_new(b) {
1810                assert_eq!(
1811                    LeadForTwoByte::try_from(lead).map(|l| l.to_lead_for_multi_byte()),
1812                    LeadForTwoByte::try_new(b).map(|l| l.to_lead_for_multi_byte())
1813                );
1814                assert_eq!(
1815                    LeadForThreeByte::try_from(lead).map(|l| l.to_lead_for_multi_byte()),
1816                    LeadForThreeByte::try_new(b).map(|l| l.to_lead_for_multi_byte())
1817                );
1818                assert_eq!(
1819                    LeadForFourByte::try_from(lead).map(|l| l.to_lead_for_multi_byte()),
1820                    LeadForFourByte::try_new(b).map(|l| l.to_lead_for_multi_byte())
1821                );
1822            }
1823            if let Ok(lead) = LeadForTwoByte::try_new(b) {
1824                assert_eq!(lead.low_five(), b & 0x1F);
1825                assert_eq!(lead.to_non_ascii().to_u8(), b);
1826            }
1827            if let Ok(lead) = LeadForThreeByte::try_new(b) {
1828                assert_eq!(lead.low_four(), b & 0x0F);
1829                assert_eq!(lead.to_non_ascii().to_u8(), b);
1830            }
1831            if let Ok(lead) = LeadForFourByte::try_new(b) {
1832                assert_eq!(lead.low_three(), b & 0x07);
1833                assert_eq!(lead.to_non_ascii().to_u8(), b);
1834            }
1835
1836            for second in 0..=0xFF {
1837                let prepared_two = PreparedTwoBytes::new(first, second);
1838                assert_eq!(
1839                    prepared_two.sequence_prefix(),
1840                    two_byte_prefix_reference(first, second)
1841                );
1842                let expected = single_scalar_reference(&[first, second]);
1843                assert_eq!(TwoByteSequence::is(first, second), expected);
1844                assert_eq!(TwoByteSequence::is_with_prepared(prepared_two), expected);
1845
1846                for third in 0..=0xFF {
1847                    let prepared_three = PreparedThreeBytes::new(first, second, third);
1848                    assert_eq!(
1849                        prepared_three,
1850                        PreparedThreeBytes::new_with_prepared(prepared_two, third)
1851                    );
1852                    assert_eq!(
1853                        prepared_three.prefix_of_four_byte(),
1854                        prefix_of_four_byte_reference(first, second, third)
1855                    );
1856
1857                    let expected = single_scalar_reference(&[first, second, third]);
1858                    assert_eq!(ThreeByteSequence::is(first, second, third), expected);
1859                    assert_eq!(
1860                        ThreeByteSequence::try_new_with_prepared(prepared_three).is_ok(),
1861                        expected
1862                    );
1863
1864                    // Limited value space for fourth byte to limit the duration of the test.
1865                    for fourth in [
1866                        0x00, 0x3F, 0x40, 0x7F, 0x80, 0x8F, 0x90, 0x9F, 0xA0, 0xBF, 0xC0, 0xFF,
1867                    ] {
1868                        let expected = single_scalar_reference(&[first, second, third, fourth]);
1869                        assert_eq!(FourByteSequence::is(first, second, third, fourth), expected);
1870                        assert_eq!(
1871                            FourByteSequence::try_new_with_prepared(prepared_three, fourth).is_ok(),
1872                            expected
1873                        );
1874                    }
1875                }
1876            }
1877        }
1878    }
1879
1880    #[test]
1881    fn test_scalars() {
1882        let mut previous_two: Option<TwoByteSequence> = None;
1883        let mut previous_three: Option<ThreeByteSequence> = None;
1884        let mut previous_four: Option<FourByteSequence> = None;
1885        for c in '\u{0}'..=char::MAX {
1886            let mut buf = [0u8; 4];
1887            let s: &str = c.encode_utf8(&mut buf);
1888            let b = s.as_bytes();
1889            match *b {
1890                [first] => {
1891                    let ascii = Ascii::try_new(first).unwrap();
1892                    assert_eq!(ascii.to_char(), c);
1893                    assert_eq!(ascii.as_str(), s);
1894                    assert_eq!(ascii.as_bytes(), s.as_bytes());
1895                }
1896                [first, second] => {
1897                    let sequence = TwoByteSequence::try_new(first, second).unwrap();
1898                    assert_eq!(
1899                        TwoByteSequence::try_new_with_prepared(PreparedTwoBytes::new(
1900                            first, second
1901                        )),
1902                        Ok(sequence)
1903                    );
1904                    assert!(PreparedTwoBytes::new(first, second).sequence_prefix());
1905                    assert_eq!(sequence.to_char(), c);
1906                    assert_eq!(sequence.as_str(), s);
1907                    assert_eq!(sequence.as_bytes(), s.as_bytes());
1908                    let (lead, continuation) = sequence.to_typed_bytes();
1909                    assert_eq!([lead.to_u8(), continuation.to_u8()], [first, second]);
1910                    assert!(previous_two < Some(sequence));
1911                    previous_two = Some(sequence);
1912                }
1913                [first, second, third] => {
1914                    let sequence = ThreeByteSequence::try_new(first, second, third).unwrap();
1915                    assert_eq!(
1916                        ThreeByteSequence::try_new_with_prepared(PreparedThreeBytes::new(
1917                            first, second, third
1918                        )),
1919                        Ok(sequence)
1920                    );
1921                    assert_eq!(sequence.to_char(), c);
1922                    assert_eq!(sequence.as_str(), s);
1923                    assert_eq!(sequence.as_bytes(), s.as_bytes());
1924                    let (lead, c1, c2) = sequence.to_typed_bytes();
1925                    assert_eq!(
1926                        [lead.to_u8(), c1.to_u8(), c2.to_u8()],
1927                        [first, second, third]
1928                    );
1929                    assert!(previous_three < Some(sequence));
1930                    previous_three = Some(sequence);
1931                }
1932                [first, second, third, fourth] => {
1933                    let sequence = FourByteSequence::try_new(first, second, third, fourth).unwrap();
1934                    let prepared = PreparedThreeBytes::new(first, second, third);
1935                    assert!(prepared.prefix_of_four_byte());
1936                    assert_eq!(
1937                        FourByteSequence::try_new_with_prepared(prepared, fourth),
1938                        Ok(sequence)
1939                    );
1940                    assert_eq!(sequence.to_char(), c);
1941                    assert_eq!(sequence.as_str(), s);
1942                    assert_eq!(sequence.as_bytes(), s.as_bytes());
1943                    let (lead, c1, c2, c3) = sequence.to_typed_bytes();
1944                    assert_eq!(
1945                        [lead.to_u8(), c1.to_u8(), c2.to_u8(), c3.to_u8()],
1946                        [first, second, third, fourth]
1947                    );
1948                    assert!(previous_four < Some(sequence));
1949                    previous_four = Some(sequence);
1950                }
1951                _ => unreachable!(),
1952            }
1953        }
1954    }
1955
1956    #[test]
1957    fn test_niche() {
1958        assert_eq!(
1959            core::mem::size_of::<Option<Ascii>>(),
1960            core::mem::size_of::<Ascii>()
1961        );
1962        assert_eq!(
1963            core::mem::size_of::<Option<NonAscii>>(),
1964            core::mem::size_of::<NonAscii>()
1965        );
1966        assert_eq!(
1967            core::mem::size_of::<Option<UnconstrainedContinuation>>(),
1968            core::mem::size_of::<UnconstrainedContinuation>()
1969        );
1970        assert_eq!(
1971            core::mem::size_of::<Option<LeadForMultiByte>>(),
1972            core::mem::size_of::<LeadForMultiByte>()
1973        );
1974        assert_eq!(
1975            core::mem::size_of::<Option<LeadForTwoByte>>(),
1976            core::mem::size_of::<LeadForTwoByte>()
1977        );
1978        assert_eq!(
1979            core::mem::size_of::<Option<LeadForThreeByte>>(),
1980            core::mem::size_of::<LeadForThreeByte>()
1981        );
1982        assert_eq!(
1983            core::mem::size_of::<Option<LeadForFourByte>>(),
1984            core::mem::size_of::<LeadForFourByte>()
1985        );
1986        assert_eq!(
1987            core::mem::size_of::<Option<TwoByteSequence>>(),
1988            core::mem::size_of::<TwoByteSequence>()
1989        );
1990        assert_eq!(
1991            core::mem::size_of::<Option<ThreeByteSequence>>(),
1992            core::mem::size_of::<ThreeByteSequence>()
1993        );
1994        assert_eq!(
1995            core::mem::size_of::<Option<FourByteSequence>>(),
1996            core::mem::size_of::<FourByteSequence>()
1997        );
1998    }
1999}