Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
unicode_data_table.py
Go to the documentation of this file.
1#!/usr/bin/env python3
2"""Generate the normalization and label validity tables from UnicodeData.txt,
3CompositionExclusions.txt and DerivedJoiningType.txt, and pack them into
4src/table_blob.inc.
5
6Use the same Unicode version as the mapping table (scripts/idna_table.py).
7
8 python3 scripts/unicode_data_table.py # print a summary
9 python3 scripts/unicode_data_table.py --write # update src/table_blob.inc
10
11Sections
12--------
13Normalization (src/normalization.cpp). Each table is indexed by cp >> 8 into
14rows of 256 entries; blocks without data share one all-zero row.
15
16 decomposition_index/block/data
17 Row entry = (offset << 2) | flags. The decomposition of cp is
18 data[entry(cp) >> 2 .. entry(cp + 1) >> 2), so rows have 257 columns.
19 The data holds the full (recursive) canonical decomposition, or the full
20 compatibility decomposition when only that exists. Flags: 1 = the
21 decomposition is compatibility-only; 2 = canonical, but the full
22 compatibility decomposition differs. data[0] is unused. Hangul syllables
23 are decomposed algorithmically and have no entries.
24 ccc_index/block
25 Canonical_Combining_Class.
26 composition_index/block/data
27 Row entry = index into data, which holds (second, composite) pairs
28 sorted by second for each first code point; [entry(cp), entry(cp + 1))
29 are the pairs starting with cp. Only primary composites (canonical
30 decompositions of length two, not Full_Composition_Exclusion) appear.
31 data[0] is unused.
32
33Validity (src/validity.cpp).
34
35 combining_flat
36 General_Category Mn, Mc or Me ranges: a label must not begin with a mark.
37 dir_start/dir_final/dir_value
38 Bidi_Class ranges of assigned code points for the RFC 5893 Bidi rule.
39 Unassigned code points are rejected by the mapping table first and look
40 up as NONE.
41 joining_start/joining_final/joining_value
42 Joining_Type ranges for the RFC 5892 ContextJ rule for U+200C. Code
43 points without a range are U (Non_Joining). The rule's Virama test
44 uses Canonical_Combining_Class 9 from the ccc tables.
45"""
46from __future__ import annotations
47
48import os
49import re
50import sys
51import urllib.request
52from collections import defaultdict
53
54UNICODE_VERSION = "18.0.0"
55UCD_URL = "https://www.unicode.org/Public/{version}/ucd/{name}"
56
57MAX_CODE_POINT = 0x10FFFF
58BLOCK_COUNT = (MAX_CODE_POINT + 1) >> 8
59
60HANGUL_SBASE = 0xAC00
61HANGUL_SCOUNT = 11172
62
63COMBINING_CATEGORIES = {"Mn", "Mc", "Me"}
64
65# Must match `enum direction` in src/validity.cpp (0 is NONE).
66BIDI_CLASSES = [
67 "NONE", "BN", "CS", "ES", "ON", "EN", "L", "R", "NSM", "AL", "AN", "ET",
68 "WS", "RLO", "LRO", "PDF", "RLE", "RLI", "FSI", "PDI", "LRI", "B", "S",
69 "LRE",
70]
71
72# Must match `enum class joining_type` in src/validity.cpp (0 is U).
73JOINING_TYPES = ["U", "C", "D", "L", "R", "T"]
74
75
76def get_ucd_file(name: str, version: str = UNICODE_VERSION) -> str:
77 """Return a UCD file, downloading it once into the working directory."""
78 stem, ext = os.path.splitext(os.path.basename(name))
79 cached = f"{stem}-{version}{ext}"
80 if not os.path.exists(cached):
81 url = UCD_URL.format(version=version, name=name)
82 with urllib.request.urlopen(url) as response:
83 data = response.read()
84 with open(cached, "wb") as f:
85 f.write(data)
86 with open(cached, encoding="utf-8") as f:
87 return f.read()
88
89
91 """The UnicodeData.txt fields used here, keyed by code point."""
92
93 def __init__(self, text: str):
94 self.category: dict[int, str] = {}
95 self.ccc: dict[int, int] = {}
96 self.bidi: dict[int, str] = {}
97 self.canonical: dict[int, list[int]] = {}
98 self.compatibility: dict[int, list[int]] = {}
99 range_first = None
100 for line in text.splitlines():
101 if not line:
102 continue
103 fields = line.split(";")
104 cp = int(fields[0], 16)
105 name = fields[1]
106 if name.endswith(", First>"):
107 range_first = cp
108 continue
109 first = cp
110 if name.endswith(", Last>"):
111 first, range_first = range_first, None
112 for c in range(first, cp + 1):
113 self.category[c] = fields[2]
114 self.ccc[c] = int(fields[3])
115 self.bidi[c] = fields[4]
116 decomposition = fields[5].split()
117 if decomposition and decomposition[0].startswith("<"):
118 mapping = [int(x, 16) for x in decomposition[1:]]
119 self.compatibility[cp] = mapping
120 elif decomposition:
121 self.canonical[cp] = [int(x, 16) for x in decomposition]
122
123 def full_decomposition(self, cp: int, compatibility: bool) -> list[int]:
124 mapping = self.canonical.get(cp)
125 if mapping is None and compatibility:
126 mapping = self.compatibility.get(cp)
127 if mapping is None:
128 return [cp]
129 return [
130 x
131 for c in mapping
132 for x in self.full_decomposition(c, compatibility)
133 ]
134
135
136def parse_composition_exclusions(text: str) -> set[int]:
137 excluded: set[int] = set()
138 for line in text.splitlines():
139 line = line.split("#", 1)[0].strip()
140 if not line:
141 continue
142 first, _, last = line.partition("..")
143 excluded.update(range(int(first, 16), int(last or first, 16) + 1))
144 return excluded
145
146
147def parse_joining_types(text: str) -> dict[int, int]:
148 """Map code points to JOINING_TYPES indexes; U is left out."""
149 types: dict[int, int] = {}
150 for line in text.splitlines():
151 line = line.split("#", 1)[0].strip()
152 if not line:
153 continue
154 code_points, _, value = (x.strip() for x in line.partition(";"))
155 if value not in JOINING_TYPES:
156 raise SystemExit(f"unknown Joining_Type value {value}")
157 if value == "U":
158 continue
159 first, _, last = code_points.partition("..")
160 for cp in range(int(first, 16), int(last or first, 16) + 1):
161 types[cp] = JOINING_TYPES.index(value)
162 return types
163
164
166 entries: list[int], cols: int, block_is_empty: list[bool]
167) -> tuple[list[int], list[int]]:
168 """Split per-code-point entries into an index and deduplicated rows.
169
170 Row b covers entries[b * 256 : b * 256 + cols]. Empty blocks get a zero
171 row.
172 """
173 index: list[int] = []
174 rows: list[int] = []
175 row_ids: dict[tuple[int, ...], int] = {}
176 for block in range(BLOCK_COUNT):
177 if block_is_empty[block]:
178 row = (0,) * cols
179 else:
180 row = tuple(entries[block << 8 : (block << 8) + cols])
181 if row not in row_ids:
182 row_ids[row] = len(row_ids)
183 rows.extend(row)
184 index.append(row_ids[row])
185 if len(row_ids) > 256:
186 raise SystemExit(f"{len(row_ids)} rows do not fit a uint8_t index")
187 return index, rows
188
189
190def build_decomposition(ucd: UnicodeData) -> dict[str, list[int]]:
191 data = [0]
192 entries = [0] * (MAX_CODE_POINT + 2)
193 has_data = [False] * BLOCK_COUNT
194 for cp in range(MAX_CODE_POINT + 1):
195 flags = 0
196 decomposition: list[int] = []
197 if HANGUL_SBASE <= cp < HANGUL_SBASE + HANGUL_SCOUNT:
198 pass
199 elif cp in ucd.canonical:
200 decomposition = ucd.full_decomposition(cp, compatibility=False)
201 if ucd.full_decomposition(cp, compatibility=True) != decomposition:
202 flags = 2
203 elif cp in ucd.compatibility:
204 decomposition = ucd.full_decomposition(cp, compatibility=True)
205 flags = 1
206 entries[cp] = (len(data) << 2) | flags
207 if decomposition:
208 data.extend(decomposition)
209 has_data[cp >> 8] = True
210 entries[MAX_CODE_POINT + 1] = len(data) << 2
211 if len(data) >= 1 << 14:
212 raise SystemExit("decomposition data does not fit 14-bit offsets")
213 index, block = build_multistage(entries, 257, [not x for x in has_data])
214 return {
215 "decomposition_index": index,
216 "decomposition_block": block,
217 "decomposition_data": data,
218 }
219
220
221def build_ccc(ucd: UnicodeData) -> dict[str, list[int]]:
222 entries = [ucd.ccc.get(cp, 0) for cp in range(MAX_CODE_POINT + 1)]
223 is_empty = [
224 not any(entries[block << 8 : (block + 1) << 8])
225 for block in range(BLOCK_COUNT)
226 ]
227 index, block = build_multistage(entries, 256, is_empty)
228 return {"ccc_index": index, "ccc_block": block}
229
230
232 ucd: UnicodeData, exclusions: set[int]
233) -> dict[str, list[int]]:
234 pairs: dict[int, list[tuple[int, int]]] = defaultdict(list)
235 for cp, mapping in ucd.canonical.items():
236 if (
237 len(mapping) != 2
238 or cp in exclusions
239 or ucd.ccc.get(cp, 0) != 0
240 or ucd.ccc.get(mapping[0], 0) != 0
241 ):
242 continue
243 pairs[mapping[0]].append((mapping[1], cp))
244 data = [0]
245 entries = [0] * (MAX_CODE_POINT + 2)
246 has_data = [False] * BLOCK_COUNT
247 for cp in range(MAX_CODE_POINT + 1):
248 entries[cp] = len(data)
249 for second, composite in sorted(pairs.get(cp, ())):
250 data.extend((second, composite))
251 has_data[cp >> 8] = True
252 entries[MAX_CODE_POINT + 1] = len(data)
253 if len(data) > 0xFFFF:
254 raise SystemExit("composition data does not fit 16-bit indexes")
255 index, block = build_multistage(entries, 257, [not x for x in has_data])
256 return {
257 "composition_index": index,
258 "composition_block": block,
259 "composition_data": data,
260 }
261
262
263def build_ranges(values: dict[int, int]) -> list[tuple[int, int, int]]:
264 """Merge code points with equal values into (first, last, value) ranges."""
265 ranges: list[tuple[int, int, int]] = []
266 for cp in sorted(values):
267 value = values[cp]
268 if ranges and ranges[-1][2] == value and ranges[-1][1] + 1 == cp:
269 ranges[-1] = (ranges[-1][0], cp, value)
270 else:
271 ranges.append((cp, cp, value))
272 return ranges
273
274
276 ucd: UnicodeData, joining_types: dict[int, int]
277) -> dict[str, list[int]]:
278 marks = {
279 cp: 1 for cp, gc in ucd.category.items() if gc in COMBINING_CATEGORIES
280 }
281 combining = build_ranges(marks)
282 unknown = set(ucd.bidi.values()) - set(BIDI_CLASSES[1:])
283 if unknown:
284 raise SystemExit(f"unknown Bidi_Class values {sorted(unknown)}")
285 directions = build_ranges(
286 {cp: BIDI_CLASSES.index(bidi) for cp, bidi in ucd.bidi.items()}
287 )
288 joining = build_ranges(joining_types)
289 return {
290 "combining_flat": [cp for r in combining for cp in r[:2]],
291 "dir_start": [first for first, _, _ in directions],
292 "dir_final": [last for _, last, _ in directions],
293 "dir_value": [value for _, _, value in directions],
294 "joining_start": [first for first, _, _ in joining],
295 "joining_final": [last for _, last, _ in joining],
296 "joining_value": [value for _, _, value in joining],
297 }
298
299
301 unicode_data_text: str,
302 composition_exclusions_text: str,
303 joining_type_text: str,
304) -> dict[str, list[int]]:
305 ucd = UnicodeData(unicode_data_text)
306 exclusions = parse_composition_exclusions(composition_exclusions_text)
307 joining_types = parse_joining_types(joining_type_text)
308 sections: dict[str, list[int]] = {}
309 sections.update(build_decomposition(ucd))
310 sections.update(build_ccc(ucd))
311 sections.update(build_composition(ucd, exclusions))
312 sections.update(build_validity(ucd, joining_types))
313 return sections
314
315
316def get_versioned_ucd_file(name: str, version: str) -> str:
317 """Return a UCD file whose '# Name-version.txt' header matches version."""
318 text = get_ucd_file(name, version)
319 stem = os.path.splitext(os.path.basename(name))[0]
320 m = re.search(rf"# {stem}-(\S+)\.txt", text)
321 if not m or m.group(1) != version:
322 raise SystemExit(f"{name} is not version {version}")
323 return text
324
325
326def generate(version: str = UNICODE_VERSION) -> dict[str, list[int]]:
327 return build_sections(
328 get_ucd_file("UnicodeData.txt", version),
329 get_versioned_ucd_file("CompositionExclusions.txt", version),
330 get_versioned_ucd_file("extracted/DerivedJoiningType.txt", version),
331 )
332
333
334def update_in_blob(generated: dict[str, list[int]]) -> None:
335 script_dir = os.path.dirname(os.path.abspath(__file__))
336 if script_dir not in sys.path:
337 sys.path.insert(0, script_dir)
338 import pack_tables
339
341 sections.update(generated)
342 pack_tables.write_blob(sections)
343
344
345def main(argv: list[str]) -> int:
346 if argv in (["-h"], ["--help"]):
347 print(__doc__)
348 return 0
349 if argv not in ([], ["--write"], ["-w"]):
350 print(__doc__)
351 return 1
352 generated = generate()
353 g = generated
354 print(f"Unicode {UNICODE_VERSION}")
355 print(f" decomposition: {len(g['decomposition_block']) // 257} rows, "
356 f"{len(g['decomposition_data'])} code points")
357 print(f" ccc: {len(g['ccc_block']) // 256} rows")
358 print(f" composition: {len(g['composition_block']) // 257} rows, "
359 f"{(len(g['composition_data']) - 1) // 2} pairs")
360 print(f" combining: {len(g['combining_flat']) // 2} ranges")
361 print(f" directions: {len(g['dir_start'])} ranges")
362 print(f" joining types: {len(g['joining_start'])} ranges")
363 if argv:
364 update_in_blob(generated)
365 print("Normalization and validity tables packed into table_blob.inc")
366 return 0
367
368
369if __name__ == "__main__":
370 raise SystemExit(main(sys.argv[1:]))
list[int] full_decomposition(self, int cp, bool compatibility)
None write_blob(dict[str, Any] sections, Path path=BLOB_PATH)
dict[str, list[int]] load_blob_sections(Path path=BLOB_PATH)
dict[str, list[int]] build_validity(UnicodeData ucd, dict[int, int] joining_types)
set[int] parse_composition_exclusions(str text)
dict[str, list[int]] generate(str version=UNICODE_VERSION)
dict[str, list[int]] build_composition(UnicodeData ucd, set[int] exclusions)
list[tuple[int, int, int]] build_ranges(dict[int, int] values)
str get_ucd_file(str name, str version=UNICODE_VERSION)
int main(list[str] argv)
str get_versioned_ucd_file(str name, str version)
dict[str, list[int]] build_decomposition(UnicodeData ucd)
tuple[list[int], list[int]] build_multistage(list[int] entries, int cols, list[bool] block_is_empty)
None update_in_blob(dict[str, list[int]] generated)
dict[str, list[int]] build_sections(str unicode_data_text, str composition_exclusions_text, str joining_type_text)
dict[int, int] parse_joining_types(str text)
dict[str, list[int]] build_ccc(UnicodeData ucd)