Line data Source code
1 : // Copyright 2026 The Authors.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // https://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : // Traversal structure ported from `spm_precompiled`
16 : // (https://github.com/huggingface/spm_precompiled, Apache-2.0):
17 : // `DoubleArray::common_prefix_search`, `Precompiled::transform`, and
18 : // `Precompiled::normalize_string`'s grapheme-then-char fallback strategy. See
19 : // the repo-root `NOTICE` file for the full attribution.
20 :
21 : import 'dart:convert';
22 : import 'dart:typed_data';
23 :
24 : import 'package:characters/characters.dart';
25 :
26 : /// Parses and applies a SentencePiece/HuggingFace `precompiled_charsmap`
27 : /// normalizer: a "Darts" double-array trie (as used by the `darts-clone`
28 : /// C++ library, https://github.com/s-yata/darts-clone) mapping UTF-8 byte
29 : /// sequences to replacement strings.
30 : ///
31 : /// `precompiled_charsmap` is the binary payload of HuggingFace
32 : /// `tokenizer.json`'s `Precompiled` normalizer entry
33 : /// (`normalizer.normalizers[].precompiled_charsmap`, base64-encoded). It
34 : /// implements the NFKC-like text substitution SentencePiece bakes into its
35 : /// trained models — e.g. fullwidth-to-ASCII folding and ellipsis/ligature
36 : /// expansion — as a static lookup table rather than a general Unicode
37 : /// normalization algorithm. It is **not** plain NFKC.
38 : ///
39 : /// ## Binary layout
40 : ///
41 : /// Confirmed against `google/sentencepiece`'s `normalizer.cc`
42 : /// (`DecodePrecompiledCharsMap`/`EncodePrecompiledCharsMap`) and
43 : /// independently against the Rust `spm_precompiled` crate's `parse()`:
44 : ///
45 : /// ```text
46 : /// [0..4) little-endian uint32: byte length of the trie blob that follows
47 : /// [4..4+n) the trie blob itself: `n` bytes, always a multiple of 4,
48 : /// interpreted as `n/4` little-endian uint32 "units" of a
49 : /// darts-clone double-array trie
50 : /// [4+n..) the "normalized" string table: a single buffer of UTF-8 bytes
51 : /// holding every replacement string back-to-back, each terminated
52 : /// by a NUL (0x00) byte. A trie leaf's value is a byte offset into
53 : /// this table; the replacement text is read from that offset up to
54 : /// (excluding) the next NUL byte.
55 : /// ```
56 : ///
57 : /// Each 32-bit darts-clone unit (`include/darts.h`,
58 : /// `Details::DoubleArrayUnit`) packs:
59 : ///
60 : /// - `hasLeaf`: bit 8 (`(unit >> 8) & 1`)
61 : /// - `value`: low 31 bits (`unit & ((1 << 31) - 1)`) — valid only when
62 : /// reading the *leaf* unit reached via `offset` below
63 : /// - `label`: MSB + low byte (`unit & ((1 << 31) | 0xFF)`) — the transition
64 : /// byte (or, with the MSB set, "no valid label", which is how leaf units
65 : /// make `label` never collide with a real 0..255 byte value)
66 : /// - `offset`: `(unit >> 10) << ((unit & (1 << 9)) >> 6)` — an XOR-linked
67 : /// offset to the unit's child units (the "double array" scheme; see
68 : /// darts-clone's README)
69 : ///
70 : /// ## Traversal algorithm
71 : ///
72 : /// SentencePiece's own C++ (`Normalizer::NormalizePrefix`) does a flat
73 : /// byte-position scan over the trie, picking the longest match. That is
74 : /// **not** what actually produces byte-exact HuggingFace `AutoTokenizer`
75 : /// output: `tokenizer.json`-based tokenizers (via the `tokenizers` Rust
76 : /// crate) go through `spm_precompiled`'s `Precompiled::normalize_string`
77 : /// instead, which:
78 : ///
79 : /// 1. Splits the input into Unicode extended grapheme clusters (UAX #29),
80 : /// not a flat byte stream.
81 : /// 2. For each cluster whose UTF-8 encoding is under 6 bytes, looks up the
82 : /// *whole cluster* in the trie first (see [transform]).
83 : /// 3. On no match (or a cluster ≥ 6 bytes), falls back to looking up each
84 : /// individual Unicode scalar value (char) within the cluster on its own;
85 : /// unmatched characters pass through unchanged.
86 : ///
87 : /// [normalize] implements this grapheme-then-char algorithm — matching the
88 : /// real oracle, not a literal reading of SentencePiece's C++ source.
89 : class CharsmapTrie {
90 2 : CharsmapTrie._(this._units, this._normalized);
91 :
92 : /// Parses a raw (already base64-decoded) `precompiled_charsmap` blob.
93 : ///
94 : /// Throws [FormatException] if [blob] is too short to contain a valid
95 : /// length header, or if the declared trie length is not a multiple of 4
96 : /// bytes or overruns the blob — both are unambiguous signs of truncated or
97 : /// corrupt input, and are rejected here rather than left to fail
98 : /// unpredictably during a later [normalize] call.
99 2 : factory CharsmapTrie.parse(Uint8List blob) {
100 4 : if (blob.length < 4) {
101 : throw const FormatException(
102 : 'precompiled_charsmap blob too short: must be at least 4 bytes '
103 : '(the little-endian trie-length header).',
104 : );
105 : }
106 2 : final data = ByteData.sublistView(blob);
107 2 : final trieByteLength = data.getUint32(0, Endian.little);
108 10 : if (trieByteLength % 4 != 0 || 4 + trieByteLength > blob.length) {
109 2 : throw FormatException(
110 : 'precompiled_charsmap trie length $trieByteLength is not a '
111 1 : 'multiple of 4, or overruns the blob (blob length ${blob.length}). '
112 : 'This indicates truncated or corrupt charsmap bytes.',
113 : );
114 : }
115 2 : final unitCount = trieByteLength ~/ 4;
116 2 : final units = Uint32List(unitCount);
117 4 : for (var i = 0; i < unitCount; i++) {
118 8 : units[i] = data.getUint32(4 + i * 4, Endian.little);
119 : }
120 4 : final normalized = blob.sublist(4 + trieByteLength);
121 2 : return CharsmapTrie._(units, normalized);
122 : }
123 :
124 : /// The darts-clone double-array "units" — one 32-bit int per trie node.
125 : final Uint32List _units;
126 :
127 : /// The NUL-delimited table of UTF-8 replacement strings that trie leaf
128 : /// values are byte offsets into.
129 : final Uint8List _normalized;
130 :
131 8 : static bool _hasLeaf(int unit) => ((unit >> 8) & 1) == 1;
132 8 : static int _value(int unit) => unit & ((1 << 31) - 1);
133 8 : static int _label(int unit) => unit & ((1 << 31) | 0xFF);
134 12 : static int _offset(int unit) => (unit >> 10) << ((unit & (1 << 9)) >> 6);
135 :
136 : /// Walks the trie over every byte of [key], returning the leaf `value()`
137 : /// of *every* node along the walk that has a leaf child (not just the
138 : /// final one) — mirroring `spm_precompiled`'s
139 : /// `DoubleArray::common_prefix_search`, including its choice to keep
140 : /// walking past the first leaf rather than stopping there.
141 : ///
142 : /// Defensive against corrupt trie data: an out-of-range node index (which
143 : /// a hand-crafted or bit-flipped trie could produce even though
144 : /// [CharsmapTrie.parse]'s own header checks passed) ends the walk and
145 : /// returns whatever leaves were already found, rather than throwing
146 : /// [RangeError] — malformed *lookup* data degrades to "no further match"
147 : /// instead of crashing the caller.
148 2 : List<int> _commonPrefixSearch(List<int> key) {
149 : var nodePos = 0;
150 2 : final results = <int>[];
151 4 : var unit = _units[nodePos];
152 4 : nodePos ^= _offset(unit);
153 4 : for (final c in key) {
154 2 : if (c == 0) break;
155 2 : final candidate = nodePos ^ c;
156 8 : if (candidate < 0 || candidate >= _units.length) return results;
157 : nodePos = candidate;
158 4 : unit = _units[nodePos];
159 4 : if (_label(unit) != c) return results;
160 4 : final childPos = nodePos ^ _offset(unit);
161 8 : if (childPos < 0 || childPos >= _units.length) return results;
162 : nodePos = childPos;
163 2 : if (_hasLeaf(unit)) {
164 8 : results.add(_value(_units[nodePos]));
165 : }
166 : }
167 : return results;
168 : }
169 :
170 : /// Looks up [chunk] (a single grapheme cluster or a single character) as a
171 : /// whole key. Returns the replacement text if the trie has an entry for
172 : /// it, or `null` if there is no match.
173 : ///
174 : /// **Longest-, not shortest-, leaf match is required — do not "fix" this
175 : /// back based on a literal reading of `spm_precompiled`'s source.** A
176 : /// literal reading of `spm_precompiled::Precompiled::transform`'s Rust
177 : /// source takes `results[0]` (the *shortest* matched prefix — leaves are
178 : /// appended to the results vector in the order the byte-walk encounters
179 : /// them, which is shortest-to-longest). That is empirically wrong: NFD
180 : /// `"Việt"`'s `e` + combining dot-below (U+0323) + combining circumflex
181 : /// (U+0302) — one extended grapheme cluster — has *two* leaves along its
182 : /// byte path: a shorter one for `e`+dot-below alone (mapping to the
183 : /// partially-composed `ẹ`) and a longer one for the full three-codepoint
184 : /// sequence (mapping to the fully composed `ệ`). Taking the shortest
185 : /// match yields `ẹ`, silently dropping the circumflex, and diverges from
186 : /// real HuggingFace `AutoTokenizer` output. Taking the **longest** match
187 : /// (`results.last`, matching SentencePiece C++'s own `NormalizePrefix`
188 : /// longest-match rule in `normalizer.cc`) yields `ệ` and reproduces the
189 : /// real oracle exactly. See `test/charsmap_trie_test.dart` for the
190 : /// regression test this gotcha is pinned down by.
191 2 : String? transform(String chunk) {
192 2 : final keyBytes = utf8.encode(chunk);
193 2 : final results = _commonPrefixSearch(keyBytes);
194 2 : if (results.isEmpty) return null;
195 2 : final start = results.last;
196 : var end = start;
197 12 : while (end < _normalized.length && _normalized[end] != 0) {
198 2 : end++;
199 : }
200 6 : return utf8.decode(_normalized.sublist(start, end));
201 : }
202 :
203 : /// Applies the charsmap substitution to [original].
204 : ///
205 : /// Follows `spm_precompiled::Precompiled::normalize_string`'s
206 : /// grapheme-cluster-first, falling-back-to-single-char algorithm: for each
207 : /// extended grapheme cluster, try a whole-cluster replacement first (only
208 : /// attempted when the cluster's UTF-8 encoding is under 6 bytes, matching
209 : /// the reference implementation's own threshold), then fall back to
210 : /// looking up each character in the cluster individually, keeping
211 : /// unmatched characters unchanged.
212 : ///
213 : /// Deliberately does **not** perform SentencePiece's
214 : /// whitespace-collapsing, dummy-prefix, or Metaspace-escaping steps —
215 : /// those are the caller's responsibility (see [XlmRobertaTokenizer] in
216 : /// `xlmr_tokenizer.dart`, which applies them immediately after this
217 : /// substitution and before handing the result to
218 : /// `dart_sentencepiece_tokenizer`'s own tokenizer).
219 2 : String normalize(String original) {
220 2 : final buffer = StringBuffer();
221 4 : for (final grapheme in original.characters) {
222 4 : final graphemeUtf8Length = utf8.encode(grapheme).length;
223 2 : if (graphemeUtf8Length < 6) {
224 2 : final whole = transform(grapheme);
225 : if (whole != null) {
226 2 : buffer.write(whole);
227 : continue;
228 : }
229 : }
230 : // Fall back to per-character (per Unicode scalar value) lookup within
231 : // the grapheme cluster.
232 4 : for (final rune in grapheme.runes) {
233 2 : final char = String.fromCharCode(rune);
234 2 : final replacement = transform(char);
235 2 : buffer.write(replacement ?? char);
236 : }
237 : }
238 2 : return buffer.toString();
239 : }
240 : }
|
