metrale_grammar/grammar/functor/
char_range.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// UTF-8 character-range FSM helpers — port of `CodepointToPackedUTF8`,
4// `AddSameLengthCharacterRange` and `GrammarFSMBuilderImpl::AddCharacterRange`
5// from `cpp/grammar_functor.cc`.
6//
7// A character class `[lo-hi]` over unicode codepoints is realized as a
8// byte-level FSM: each codepoint expands to its UTF-8 byte sequence and
9// a range of codepoints becomes a set of byte-range edges.
10
11use crate::fsm::FsmWithStartEnd;
12
13/// Largest 1-byte UTF-8 value.
14pub const MAX_1B: u32 = 0x7F;
15/// Smallest packed 2-byte UTF-8 value.
16pub const MIN_2B: u32 = 0xC080;
17/// Largest packed 2-byte UTF-8 value.
18pub const MAX_2B: u32 = 0xDFBF;
19/// Smallest packed 3-byte UTF-8 value.
20pub const MIN_3B: u32 = 0xE08080;
21/// Largest packed 3-byte UTF-8 value.
22pub const MAX_3B: u32 = 0xEFBFBF;
23/// Smallest packed 4-byte UTF-8 value.
24pub const MIN_4B: u32 = 0xF0808080;
25/// Largest packed 4-byte UTF-8 value.
26pub const MAX_4B: u32 = 0xF7BFBFBF;
27
28/// Pack a unicode codepoint into the big-endian UTF-8 representation
29/// used by [`add_character_range`].
30pub fn codepoint_to_packed_utf8(cp: u32) -> u32 {
31    if cp <= 0x7F {
32        cp
33    } else if cp <= 0x7FF {
34        let b0 = 0xC0 | ((cp >> 6) & 0x1F);
35        let b1 = 0x80 | (cp & 0x3F);
36        (b0 << 8) | b1
37    } else if cp <= 0xFFFF {
38        let b0 = 0xE0 | ((cp >> 12) & 0x0F);
39        let b1 = 0x80 | ((cp >> 6) & 0x3F);
40        let b2 = 0x80 | (cp & 0x3F);
41        (b0 << 16) | (b1 << 8) | b2
42    } else {
43        let b0 = 0xF0 | ((cp >> 18) & 0x07);
44        let b1 = 0x80 | ((cp >> 12) & 0x3F);
45        let b2 = 0x80 | ((cp >> 6) & 0x3F);
46        let b3 = 0x80 | (cp & 0x3F);
47        (b0 << 24) | (b1 << 16) | (b2 << 8) | b3
48    }
49}
50#[path = "char_range_same_len.rs"]
51mod char_range_same_len;
52pub use char_range_same_len::add_same_length_range;
53
54/// Add a `[min, max]` range of packed UTF-8 codepoints to `fsm`,
55/// splitting the range at byte-length boundaries.
56pub fn add_character_range(
57    fsm: &mut FsmWithStartEnd,
58    from: usize,
59    to: usize,
60    mut min: u32,
61    mut max: u32,
62) {
63    assert!(min <= max, "invalid character range: min > max");
64    // Clamp max/min to valid packed-UTF-8 values.
65    if max > MAX_4B {
66        max = MAX_4B;
67    } else if max > MAX_3B {
68        if max < MIN_4B {
69            max = MAX_3B;
70        }
71    } else if max > MAX_2B {
72        if max < MIN_3B {
73            max = MAX_2B;
74        }
75    } else if max < MIN_2B && max > MAX_1B {
76        max = MAX_1B;
77    }
78    if min > MAX_4B {
79        min = MAX_4B;
80    } else if min > MAX_3B {
81        if min < MIN_4B {
82            min = MIN_4B;
83        }
84    } else if min > MAX_2B {
85        if min < MIN_3B {
86            min = MIN_3B;
87        }
88    } else if min < MIN_2B && min > MAX_1B {
89        min = MIN_2B;
90    }
91
92    if max <= MAX_1B {
93        add_same_length_range(fsm, from, to, min, max);
94        return;
95    }
96    if max <= MAX_2B {
97        if min >= MIN_2B {
98            add_same_length_range(fsm, from, to, min, max);
99        } else {
100            add_same_length_range(fsm, from, to, min, MAX_1B);
101            add_same_length_range(fsm, from, to, MIN_2B, max);
102        }
103        return;
104    }
105    if max <= MAX_3B {
106        if min >= MIN_3B {
107            add_same_length_range(fsm, from, to, min, max);
108        } else if min >= MIN_2B {
109            add_same_length_range(fsm, from, to, min, MAX_2B);
110            add_same_length_range(fsm, from, to, MIN_3B, max);
111        } else {
112            add_same_length_range(fsm, from, to, min, MAX_1B);
113            add_same_length_range(fsm, from, to, MIN_2B, MAX_2B);
114            add_same_length_range(fsm, from, to, MIN_3B, max);
115        }
116        return;
117    }
118    assert!(max <= MAX_4B);
119    if min >= MIN_4B {
120        add_same_length_range(fsm, from, to, min, max);
121    } else if min >= MIN_3B {
122        add_same_length_range(fsm, from, to, min, MAX_3B);
123        add_same_length_range(fsm, from, to, MIN_4B, max);
124    } else if min >= MIN_2B {
125        add_same_length_range(fsm, from, to, min, MAX_2B);
126        add_same_length_range(fsm, from, to, MIN_3B, MAX_3B);
127        add_same_length_range(fsm, from, to, MIN_4B, max);
128    } else {
129        add_same_length_range(fsm, from, to, min, MAX_1B);
130        add_same_length_range(fsm, from, to, MIN_2B, MAX_2B);
131        add_same_length_range(fsm, from, to, MIN_3B, MAX_3B);
132        add_same_length_range(fsm, from, to, MIN_4B, max);
133    }
134}
135
136#[cfg(test)]
137#[path = "char_range_tests.rs"]
138mod tests;
metrale_grammar/grammar/functor/char_range.rs

metrale_grammar/grammar/functor/
char_range.rs
