Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
idna_table.py
Go to the documentation of this file.
1import os.path
2import requests
3import re
4import sys
5if sys.version_info[0] < 3:
6 print('You need to run this with Python 3')
7 sys.exit(1)
8
9# ─── Configuration ────────────────────────────────────────────────────────────
10BLOCK_BITS = 6 # block size = 2^BLOCK_BITS = 64 code points
11BLOCK_SIZE = 1 << BLOCK_BITS
12BLOCK_MASK = BLOCK_SIZE - 1
13BOOL_FLAG = 0x8000 # set in stage1 when entry points to a bool-block
14# stage2 sentinel values (must not overlap with valid mapping-table indices)
15SENTINEL_VALID = 0xFFFF
16SENTINEL_DISALLOWED = 0xFFFE
17# stage2 value 0 is reserved for "ignored" (empty mapping, index 0 in utf8 table)
18IGNORED_IDX = 0
19
20# ─── Download / cache IDNA mapping table ─────────────────────────────────────
21# Keep in step with the Unicode version of the other generators
22# (scripts/derived_table.py); Public/idna/latest moves to each new release.
23UNICODE_VERSION = "18.0.0"
24url = f"https://www.unicode.org/Public/{UNICODE_VERSION}/idna/IdnaMappingTable.txt"
25filename = f"IdnaMappingTable-{UNICODE_VERSION}.txt"
26
28 if not os.path.exists(filename):
29 tablefile = requests.get(url)
30 tablefile.raise_for_status()
31 with open(filename, 'wb') as f:
32 f.write(tablefile.content)
33 with open(filename, 'r') as f:
34 table_data = f.read()
35 version = get_version(table_data)
36 if version != UNICODE_VERSION:
37 raise SystemExit(f"{filename} is version {version}, expected "
38 f"{UNICODE_VERSION}; delete it to download again")
39 return table_data
40
41def get_version(table_data):
42 return re.search(r"# Version: (.*)", table_data).group(1)
43
44# ─── UTF-8 helpers ────────────────────────────────────────────────────────────
46 """Return UTF-8 encoding of a Unicode code point as bytes."""
47 if cp <= 0x7F:
48 return bytes([cp])
49 elif cp <= 0x7FF:
50 return bytes([0xC0 | (cp >> 6),
51 0x80 | (cp & 0x3F)])
52 elif cp <= 0xFFFF:
53 return bytes([0xE0 | (cp >> 12),
54 0x80 | ((cp >> 6) & 0x3F),
55 0x80 | (cp & 0x3F)])
56 else:
57 return bytes([0xF0 | (cp >> 18),
58 0x80 | ((cp >> 12) & 0x3F),
59 0x80 | ((cp >> 6) & 0x3F),
60 0x80 | (cp & 0x3F)])
61
62# ─── Parse raw IDNA table ─────────────────────────────────────────────────────
63def parse_idna(table_data):
64 """
65 Returns a list of (cp_start, cp_end_inclusive, code, mapped_seq) where
66 code = 0 ignored | 1 valid | 2 disallowed | 3 mapped
67 mapped_seq = tuple of uint32 code points (only when code==3)
68 """
69 mapping = {"ignored": 0, "valid": 1, "disallowed": 2, "mapped": 3}
70 entries = []
71 for line in table_data.split('\n'):
72 if line.startswith('#') or ';' not in line:
73 continue
74 line = line[:line.index('#')]
75 parts = [p.strip() for p in line.split(';') if p.strip()]
76 if not parts:
77 continue
78 status = parts[1]
79 # IDNA2003 compatibility: treat STD3 as non-STD3, deviation as valid
80 if status.startswith('disallowed_STD3_'):
81 status = status[16:]
82 if status == 'deviation':
83 status = 'valid'
84 code = mapping.get(status)
85 if code is None:
86 continue
87 cp_range = [int(x, 16) for x in parts[0].split('..')]
88 cp_start = cp_range[0]
89 cp_end = cp_range[-1]
90 mapped_seq = ()
91 if code == 3:
92 mapped_seq = tuple(int(x, 16) for x in parts[2].split())
93 entries.append((cp_start, cp_end, code, mapped_seq))
94 return entries
95
96# ─── Determine table layout from actual data ──────────────────────────────────
98 """
99 Find the ignored code point range above U+E0000.
100 Returns (start, end_exclusive) or (None, None) if not found.
101 """
102 high_ignored = [(s, e) for s, e, c, m in entries if c == 0 and s >= 0xE0000]
103 if not high_ignored:
104 return None, None
105 start = min(s for s, e in high_ignored)
106 end = max(e for s, e in high_ignored) + 1 # exclusive
107 return start, end
108
109def compute_low_range_end(entries, high_ignored_start):
110 """
111 Find the first block boundary that covers all non-disallowed code points
112 below the high-ignored range. This dynamically captures the full active
113 range (including CJK Extension I/J and similar future additions) without
114 requiring any hardcoded boundaries.
115 """
116 max_active_cp = 0
117 for cp_start, cp_end, code, seq in entries:
118 # Exclude code points in/above the high ignored range and pure
119 # disallowed entries.
120 if cp_start >= high_ignored_start:
121 continue
122 if code != 2: # non-disallowed (valid, ignored, mapped)
123 max_active_cp = max(max_active_cp, cp_end)
124
125 # Round up to the next block boundary so that max_active_cp is
126 # fully contained within the table.
127 return ((max_active_cp >> BLOCK_BITS) + 1) << BLOCK_BITS
128
129# ─── Build flat per-code-point array + UTF-8 mapping table ───────────────────
130def build_flat_and_mappings(entries, low_range_end):
131 """
132 Returns (flat, utf8_table, seq_to_idx) where
133 flat[cp] = SENTINEL_VALID | SENTINEL_DISALLOWED | utf8_byte_offset
134 utf8_table = bytearray of null-terminated UTF-8 mapping strings
135 seq_to_idx = dict mapping tuple of codepoints -> byte offset in utf8_table
136 """
137 flat = [SENTINEL_DISALLOWED] * low_range_end
138
139 # Build UTF-8 mapping table.
140 # Index 0 is always the empty string (for "ignored" code points).
141 utf8_table = bytearray([0]) # byte 0: null terminator (empty mapping)
142 seq_to_idx = {(): IGNORED_IDX}
143
144 # Pre-populate all unique mapping sequences
145 for cp_start, cp_end, code, seq in entries:
146 if code == 3 and seq not in seq_to_idx:
147 offset = len(utf8_table)
148 seq_to_idx[seq] = offset
149 for cp in seq:
150 utf8_table.extend(encode_utf8(cp))
151 utf8_table.append(0) # null terminator
152
153 # Fill flat array
154 for cp_start, cp_end, code, seq in entries:
155 lo = max(cp_start, 0)
156 hi = min(cp_end + 1, low_range_end)
157 if lo >= hi:
158 continue
159 if code == 0: # ignored -> empty mapping
160 val = IGNORED_IDX
161 elif code == 1: # valid
162 val = SENTINEL_VALID
163 elif code == 2: # disallowed
164 val = SENTINEL_DISALLOWED
165 else: # mapped
166 val = seq_to_idx[seq]
167 for cp in range(lo, hi):
168 flat[cp] = val
169
170 return flat, utf8_table, seq_to_idx
171
172# ─── Build two-level compressed table ────────────────────────────────────────
174 """
175 Returns (stage1, mixed_data, bool_words) where
176 stage1[i] = index for block i
177 bit 15 set -> bool block: lower 15 bits = bool_block_idx
178 bit 15 clear -> mixed block: value = base offset into mixed_data[]
179 mixed_data = flat uint16_t array (all mixed blocks concatenated)
180 bool_words = list of uint64_t bitwords; bit k=1 ↔ code point is VALID
181 """
182 block_size = BLOCK_SIZE
183 n_blocks = (len(flat) + block_size - 1) // block_size
184 stage1 = []
185 mixed_data = []
186 bool_words = []
187 mixed_map = {} # tuple(block) -> base offset in mixed_data
188 bool_map = {} # int (bitword) -> index in bool_words
189
190 for bi in range(n_blocks):
191 start = bi * block_size
192 end = start + block_size
193 block = flat[start:end]
194 if len(block) < block_size:
195 block = block + [SENTINEL_DISALLOWED] * (block_size - len(block))
196
197 # Check if block only contains VALID / DISALLOWED (boolean block)
198 is_bool = all(v in (SENTINEL_VALID, SENTINEL_DISALLOWED) for v in block)
199
200 if is_bool:
201 bits = 0
202 for i, v in enumerate(block):
203 if v == SENTINEL_VALID:
204 bits |= (1 << i)
205 if bits not in bool_map:
206 bool_map[bits] = len(bool_words)
207 bool_words.append(bits)
208 stage1.append(BOOL_FLAG | bool_map[bits])
209 else:
210 key = tuple(block)
211 if key not in mixed_map:
212 base = len(mixed_data)
213 mixed_map[key] = base
214 mixed_data.extend(block)
215 stage1.append(mixed_map[key])
216
217 return stage1, mixed_data, bool_words
218
219# ─── C++ output helpers ───────────────────────────────────────────────────────
220def hex2(v): return f'0x{v:02X}'
221def hex4(v): return f'0x{v:04X}'
222def hex8(v): return f'0x{v:08X}'
223def hex16(v): return f'0x{v:016X}ULL'
224
225def emit_array_uint8(name, data, cols=16):
226 lines = [f'const uint8_t {name}[{len(data)}] = {{']
227 row = []
228 for i, v in enumerate(data):
229 row.append(hex2(v))
230 if len(row) == cols:
231 lines.append('\t' + ', '.join(row) + ',')
232 row = []
233 if row:
234 lines.append('\t' + ', '.join(row))
235 lines.append('};')
236 return '\n'.join(lines)
237
238def emit_array_uint16(name, data, cols=12):
239 lines = [f'const uint16_t {name}[{len(data)}] = {{']
240 row = []
241 for i, v in enumerate(data):
242 row.append(hex4(v))
243 if len(row) == cols:
244 lines.append('\t' + ', '.join(row) + ',')
245 row = []
246 if row:
247 lines.append('\t' + ', '.join(row))
248 lines.append('};')
249 return '\n'.join(lines)
250
251def emit_array_uint64(name, data, cols=4):
252 lines = [f'const uint64_t {name}[{len(data)}] = {{']
253 row = []
254 for i, v in enumerate(data):
255 row.append(hex16(v))
256 if len(row) == cols:
257 lines.append('\t' + ', '.join(row) + ',')
258 row = []
259 if row:
260 lines.append('\t' + ', '.join(row))
261 lines.append('};')
262 return '\n'.join(lines)
263
264# ─── Main ─────────────────────────────────────────────────────────────────────
266 """Build mapping tables from IdnaMappingTable.txt.
267
268 Returns a dict with constants and array payloads suitable for packing.
269 """
270 table_data = get_table()
271 version = get_version(table_data)
272 entries = parse_idna(table_data)
273
274 # Derive layout constants from the actual table data.
275 high_ignored_start, high_ignored_end = find_high_ignored_range(entries)
276 if high_ignored_start is None:
277 # No isolated high-ignored range; nothing special needed above LOW_RANGE_END.
278 high_ignored_start = 0x110000
279 high_ignored_end = 0x110000
280
281 low_range_end = compute_low_range_end(entries, high_ignored_start)
282
283 flat, utf8_table, seq_to_idx = build_flat_and_mappings(entries, low_range_end)
284 stage1, mixed_data, bool_words = build_two_level(flat)
285
286 # Validate utf8 table entries will fit in uint16_t sentinels
287 assert len(utf8_table) < 0xFFFD, \
288 f"UTF-8 table too large: {len(utf8_table)} bytes, max 0xFFFD"
289 assert len(stage1) <= 0x8000, \
290 f"stage1 too large: {len(stage1)} entries"
291
292 return {
293 "version": version,
294 "block_bits": BLOCK_BITS,
295 "block_size": BLOCK_SIZE,
296 "block_mask": BLOCK_MASK,
297 "sentinel_valid": SENTINEL_VALID,
298 "sentinel_disallowed": SENTINEL_DISALLOWED,
299 "ignored_idx": IGNORED_IDX,
300 "bool_flag": BOOL_FLAG,
301 "low_range_end": low_range_end,
302 "high_ignored_start": high_ignored_start,
303 "high_ignored_end": high_ignored_end,
304 "stage1": stage1,
305 "mixed_data": mixed_data,
306 "bool_words": bool_words,
307 "utf8_table": list(utf8_table),
308 }
309
310
312 """Print expanded C++ arrays to stdout (debug / legacy)."""
313 data = generate_idna()
314 version = data["version"]
315 stage1 = data["stage1"]
316 mixed_data = data["mixed_data"]
317 bool_words = data["bool_words"]
318 utf8_table = data["utf8_table"]
319 n_stage1 = len(stage1)
320 n_mixed = len(mixed_data)
321 n_bool = len(bool_words)
322 n_utf8 = len(utf8_table)
323 total_bytes = (n_stage1 * 2) + (n_mixed * 2) + (n_bool * 8) + n_utf8
324 low_range_end = data["low_range_end"]
325 high_ignored_start = data["high_ignored_start"]
326 high_ignored_end = data["high_ignored_end"]
327
328 print(f"// IDNA {version}")
329 print(f"// Two-level compressed mapping table.")
330 print(f"// All constants are derived from the table data; no hardcoded boundaries.")
331 print(f"// Total binary size: {total_bytes} bytes ({total_bytes/1024:.1f} KB)")
332 print(f"// stage1: {n_stage1*2:6} bytes ({n_stage1} uint16_t entries)")
333 print(f"// stage2: {n_mixed*2:6} bytes ({len(mixed_data)//BLOCK_SIZE} mixed blocks x {BLOCK_SIZE})")
334 print(f"// bool_blocks: {n_bool*8:6} bytes ({n_bool} uint64_t words)")
335 print(f"// utf8 maps: {n_utf8:6} bytes")
336 print()
337 print("// clang-format off")
338 print("#ifndef ADA_IDNA_MAPPING_TABLE_H")
339 print("#define ADA_IDNA_MAPPING_TABLE_H")
340 print("#include <cstdint>")
341 print()
342 print("namespace ada::idna {")
343 print()
344
345 # ── Constants (all derived from the actual table, not hardcoded) ───────────
346 print(f"// Block size for two-level table (2^{BLOCK_BITS} = {BLOCK_SIZE} code points per block).")
347 print(f"constexpr uint32_t IDNA_BLOCK_BITS = {BLOCK_BITS}u;")
348 print(f"constexpr uint32_t IDNA_BLOCK_SIZE = {BLOCK_SIZE}u;")
349 print(f"constexpr uint32_t IDNA_BLOCK_MASK = {BLOCK_MASK}u;")
350 print()
351 print(f"// Sentinel values stored in stage2 / returned by lookup.")
352 print(f"constexpr uint16_t IDNA_VALID = {hex4(SENTINEL_VALID)}; // code point is valid as-is")
353 print(f"constexpr uint16_t IDNA_DISALLOWED = {hex4(SENTINEL_DISALLOWED)}; // code point is disallowed")
354 print(f"constexpr uint16_t IDNA_IGNORED = {hex4(IGNORED_IDX)}; // ignored (index into empty UTF-8 entry)")
355 print()
356 print(f"// Bit 15 of a stage1 entry: set = boolean block, clear = mixed block.")
357 print(f"constexpr uint16_t IDNA_BOOL_FLAG = {hex4(BOOL_FLAG)};")
358 print()
359 print(f"// Two-level table covers code points [0, IDNA_LOW_RANGE_END).")
360 print(f"// Derived from the highest non-disallowed code point below the high-ignored range,")
361 print(f"// rounded up to the next {BLOCK_SIZE}-code-point block boundary.")
362 print(f"constexpr uint32_t IDNA_LOW_RANGE_END = {hex8(low_range_end)};")
363 print()
364 print(f"// Variation selectors supplement: U+{high_ignored_start:04X}..U+{high_ignored_end-1:04X} are all ignored.")
365 print(f"// These are handled with a simple range check; everything else above")
366 print(f"// IDNA_LOW_RANGE_END is disallowed.")
367 print(f"constexpr uint32_t IDNA_HIGH_IGNORED_START = {hex8(high_ignored_start)};")
368 print(f"constexpr uint32_t IDNA_HIGH_IGNORED_END = {hex8(high_ignored_end)}; // exclusive")
369 print()
370
371 # ── stage1 ─────────────────────────────────────────────────────────────────
372 print(f"// idna_stage1[cp >> {BLOCK_BITS}]: one entry per {BLOCK_SIZE}-code-point block.")
373 print(f"// Bit 15 set -> lower 15 bits = index into idna_bool_blocks[].")
374 print(f"// Bit 15 clear -> value = base offset into idna_stage2[] for this block.")
375 print(emit_array_uint16(f"idna_stage1", stage1))
376 print()
377
378 # ── stage2 (mixed blocks) ──────────────────────────────────────────────────
379 print(f"// idna_stage2[]: mixed blocks. Each entry is IDNA_VALID, IDNA_DISALLOWED,")
380 print(f"// IDNA_IGNORED, or a byte offset into idna_utf8_mappings[].")
381 print(emit_array_uint16(f"idna_stage2", mixed_data))
382 print()
383
384 # ── boolean blocks ──────────────────────────────────────────────────────────
385 print(f"// idna_bool_blocks[]: one uint64_t per boolean block.")
386 print(f"// Bit k (0 = LSB) = 1 -> (block_start + k) is VALID; 0 -> DISALLOWED.")
387 print(emit_array_uint64(f"idna_bool_blocks", bool_words))
388 print()
389
390 # ── UTF-8 mapping table ────────────────────────────────────────────────────
391 print(f"// idna_utf8_mappings[]: null-terminated UTF-8 mapping strings.")
392 print(f"// Byte offset 0 is the empty string (for ignored code points).")
393 print(emit_array_uint8(f"idna_utf8_mappings", utf8_table))
394 print()
395
396 print("} // namespace ada::idna")
397 print("#endif // ADA_IDNA_MAPPING_TABLE_H")
398
399
401 """Write constants to src/mapping_tables.cpp and update table_blob.inc."""
402 # Allow `python3 scripts/idna_table.py --write` from any cwd.
403 script_dir = os.path.dirname(os.path.abspath(__file__))
404 if script_dir not in sys.path:
405 sys.path.insert(0, script_dir)
406 import pack_tables
407
408 data = generate_idna()
410 version=data["version"],
411 block_bits=data["block_bits"],
412 block_size=data["block_size"],
413 block_mask=data["block_mask"],
414 sentinel_valid=data["sentinel_valid"],
415 sentinel_disallowed=data["sentinel_disallowed"],
416 ignored_idx=data["ignored_idx"],
417 bool_flag=data["bool_flag"],
418 low_range_end=data["low_range_end"],
419 high_ignored_start=data["high_ignored_start"],
420 high_ignored_end=data["high_ignored_end"],
421 stage1=data["stage1"],
422 mixed_data=data["mixed_data"],
423 bool_words=data["bool_words"],
424 utf8_table=data["utf8_table"],
425 )
427 data["stage1"],
428 data["mixed_data"],
429 data["bool_words"],
430 data["utf8_table"],
431 )
432 print("Mapping tables regenerated and packed into table_blob.inc")
433
434
435if __name__ == "__main__":
436 if len(sys.argv) > 1 and sys.argv[1] in ("--write", "-w"):
437 write_idna()
438 elif len(sys.argv) > 1 and sys.argv[1] in ("-h", "--help"):
439 print("Usage: python3 scripts/idna_table.py [--write]")
440 print(" (default) Print expanded C++ mapping tables to stdout")
441 print(" --write Write constants + update src/table_blob.inc")
442 else:
443 print_idna()
compute_low_range_end(entries, high_ignored_start)
emit_array_uint64(name, data, cols=4)
emit_array_uint8(name, data, cols=16)
find_high_ignored_range(entries)
Definition idna_table.py:97
emit_array_uint16(name, data, cols=12)
parse_idna(table_data)
Definition idna_table.py:63
build_two_level(flat)
encode_utf8(cp)
Definition idna_table.py:45
get_version(table_data)
Definition idna_table.py:41
build_flat_and_mappings(entries, low_range_end)
None write_mapping_constants(*, str version, int block_bits, int block_size, int block_mask, int sentinel_valid, int sentinel_disallowed, int ignored_idx, int bool_flag, int low_range_end, int high_ignored_start, int high_ignored_end, list[int] stage1, list[int] mixed_data, list[int] bool_words, list[int] utf8_table, Path path=MAPPING_CPP)
None update_mapping_in_blob(list[int] stage1, list[int] mixed_data, list[int] bool_words, list[int] utf8_table)