lex_unicode.c (17062B)
1 #include "internal.h" 2 #include "unicode_props.h" 3 4 static int scalar_range_cmp(const void* a, const void* b) { 5 const ScalarRange* x = a; 6 const ScalarRange* y = b; 7 if (x->lo != y->lo) return x->lo < y->lo ? -1 : 1; 8 if (x->hi != y->hi) return x->hi < y->hi ? -1 : 1; 9 return 0; 10 } 11 12 static int unicode_is_scalar_value(uint32_t cp) { 13 return cp <= UNICODE_MAX_SCALAR && 14 !(cp >= UNICODE_SURROGATE_FIRST && cp <= UNICODE_SURROGATE_LAST); 15 } 16 17 static uint64_t scalar_set_cache_hash(const char* tag, const char* s, 18 size_t n) { 19 uint64_t h = 1469598103934665603ull; 20 for (size_t i = 0; tag[i]; i++) { 21 h ^= (unsigned char)tag[i]; 22 h *= 1099511628211ull; 23 } 24 h ^= 0xffu; 25 h *= 1099511628211ull; 26 for (size_t i = 0; i < n; i++) { 27 h ^= (unsigned char)s[i]; 28 h *= 1099511628211ull; 29 } 30 h ^= n; 31 h *= 1099511628211ull; 32 return h; 33 } 34 35 static char* scalar_set_cache_key(GramgenContext* ctx, const char* tag, 36 const char* s, size_t n, size_t* len_out) { 37 size_t tag_len = strlen(tag); 38 char* key = xmalloc(ctx, tag_len + 1 + n + 1); 39 memcpy(key, tag, tag_len); 40 key[tag_len] = ':'; 41 if (n) memcpy(key + tag_len + 1, s, n); 42 key[tag_len + 1 + n] = '\0'; 43 *len_out = tag_len + 1 + n; 44 return key; 45 } 46 47 static int scalar_set_cache_get(GramgenContext* ctx, const char* tag, 48 const char* s, size_t n, ScalarSet* out) { 49 uint64_t hash = scalar_set_cache_hash(tag, s, n); 50 size_t key_len = strlen(tag) + 1 + n; 51 for (ScalarSetCacheEntry* entry = ctx->scalar_set_cache; entry; 52 entry = entry->next) { 53 if (entry->hash == hash && entry->key_len == key_len && 54 memcmp(entry->key, tag, strlen(tag)) == 0 && 55 entry->key[strlen(tag)] == ':' && 56 memcmp(entry->key + strlen(tag) + 1, s, n) == 0) { 57 *out = entry->set; 58 return 1; 59 } 60 } 61 return 0; 62 } 63 64 static ScalarSet scalar_set_cache_put(GramgenContext* ctx, const char* tag, 65 const char* s, size_t n, ScalarSet set) { 66 size_t key_len = 0; 67 ScalarSetCacheEntry* entry = xmalloc(ctx, sizeof *entry); 68 entry->key = scalar_set_cache_key(ctx, tag, s, n, &key_len); 69 entry->key_len = key_len; 70 entry->hash = scalar_set_cache_hash(tag, s, n); 71 entry->set = set; 72 entry->next = ctx->scalar_set_cache; 73 ctx->scalar_set_cache = entry; 74 return set; 75 } 76 77 static void scalar_set_append_raw(ScalarSet* set, uint32_t lo, uint32_t hi) { 78 if (lo > hi) return; 79 if (set->n == set->cap) { 80 set->cap = set->cap ? set->cap * 2 : 8; 81 set->v = xrealloc(set->ctx, set->v, set->cap * sizeof *set->v); 82 } 83 set->v[set->n++] = (ScalarRange){lo, hi}; 84 } 85 86 static void scalar_set_append_merged(ScalarSet* set, uint32_t lo, uint32_t hi) { 87 if (lo > hi) return; 88 if (set->n && lo <= set->v[set->n - 1].hi + 1) { 89 if (hi > set->v[set->n - 1].hi) set->v[set->n - 1].hi = hi; 90 } else { 91 scalar_set_append_raw(set, lo, hi); 92 } 93 } 94 95 static void scalar_set_append_scalar_range(ScalarSet* set, uint32_t lo, 96 uint32_t hi) { 97 if (lo > hi || lo > UNICODE_MAX_SCALAR) return; 98 if (hi > UNICODE_MAX_SCALAR) hi = UNICODE_MAX_SCALAR; 99 if (lo <= UNICODE_SURROGATE_LAST && hi >= UNICODE_SURROGATE_FIRST) { 100 if (lo < UNICODE_SURROGATE_FIRST) 101 scalar_set_append_merged(set, lo, UNICODE_SURROGATE_FIRST - 1); 102 if (hi > UNICODE_SURROGATE_LAST) 103 scalar_set_append_merged(set, UNICODE_SURROGATE_LAST + 1, hi); 104 } else { 105 scalar_set_append_merged(set, lo, hi); 106 } 107 } 108 109 static ScalarSet scalar_set_normalized(GramgenContext* ctx, ScalarRange* ranges, 110 size_t n) { 111 ScalarSet tmp = {.ctx = ctx}; 112 for (size_t i = 0; i < n; i++) { 113 uint32_t lo = ranges[i].lo; 114 uint32_t hi = ranges[i].hi; 115 if (lo > hi || lo > UNICODE_MAX_SCALAR) continue; 116 if (hi > UNICODE_MAX_SCALAR) hi = UNICODE_MAX_SCALAR; 117 if (lo <= UNICODE_SURROGATE_LAST && hi >= UNICODE_SURROGATE_FIRST) { 118 if (lo < UNICODE_SURROGATE_FIRST) 119 scalar_set_append_raw(&tmp, lo, UNICODE_SURROGATE_FIRST - 1); 120 if (hi > UNICODE_SURROGATE_LAST) 121 scalar_set_append_raw(&tmp, UNICODE_SURROGATE_LAST + 1, hi); 122 } else { 123 scalar_set_append_raw(&tmp, lo, hi); 124 } 125 } 126 if (tmp.n > 1) qsort(tmp.v, tmp.n, sizeof *tmp.v, scalar_range_cmp); 127 ScalarSet out = {.ctx = ctx}; 128 for (size_t i = 0; i < tmp.n; i++) { 129 ScalarRange r = tmp.v[i]; 130 scalar_set_append_merged(&out, r.lo, r.hi); 131 } 132 return out; 133 } 134 135 static ScalarSet scalar_set_single(GramgenContext* ctx, uint32_t cp, Loc loc) { 136 if (!unicode_is_scalar_value(cp)) 137 kit_gram_error(ctx, loc, "invalid Unicode scalar U+%04X", (unsigned)cp); 138 ScalarSet out = {.ctx = ctx}; 139 scalar_set_append_raw(&out, cp, cp); 140 return out; 141 } 142 143 ScalarSet kit_gram_scalar_set_universe(GramgenContext* ctx) { 144 ScalarSet cached = {0}; 145 if (scalar_set_cache_get(ctx, "universe", "", 0, &cached)) return cached; 146 ScalarSet out = {.ctx = ctx}; 147 scalar_set_append_raw(&out, 0, UNICODE_SURROGATE_FIRST - 1); 148 scalar_set_append_raw(&out, UNICODE_SURROGATE_LAST + 1, UNICODE_MAX_SCALAR); 149 return scalar_set_cache_put(ctx, "universe", "", 0, out); 150 } 151 152 static ScalarSet scalar_set_union(GramgenContext* ctx, const ScalarSet* a, 153 const ScalarSet* b) { 154 ScalarSet out = {.ctx = ctx}; 155 size_t i = 0, j = 0; 156 while (i < a->n || j < b->n) { 157 ScalarRange r; 158 if (j == b->n || (i < a->n && a->v[i].lo <= b->v[j].lo)) 159 r = a->v[i++]; 160 else 161 r = b->v[j++]; 162 scalar_set_append_merged(&out, r.lo, r.hi); 163 } 164 return out; 165 } 166 167 static ScalarSet scalar_set_intersect(GramgenContext* ctx, const ScalarSet* a, 168 const ScalarSet* b) { 169 ScalarSet out = {.ctx = ctx}; 170 size_t i = 0, j = 0; 171 while (i < a->n && j < b->n) { 172 uint32_t lo = a->v[i].lo > b->v[j].lo ? a->v[i].lo : b->v[j].lo; 173 uint32_t hi = a->v[i].hi < b->v[j].hi ? a->v[i].hi : b->v[j].hi; 174 if (lo <= hi) scalar_set_append_merged(&out, lo, hi); 175 if (a->v[i].hi < b->v[j].hi) 176 i++; 177 else 178 j++; 179 } 180 return out; 181 } 182 183 static ScalarSet scalar_set_difference(GramgenContext* ctx, const ScalarSet* a, 184 const ScalarSet* b) { 185 ScalarSet out = {.ctx = ctx}; 186 size_t j = 0; 187 for (size_t i = 0; i < a->n; i++) { 188 uint32_t cur = a->v[i].lo; 189 uint32_t hi = a->v[i].hi; 190 while (j < b->n && b->v[j].hi < cur) j++; 191 size_t k = j; 192 while (k < b->n && b->v[k].lo <= hi) { 193 if (b->v[k].lo > cur) scalar_set_append_merged(&out, cur, b->v[k].lo - 1); 194 if (b->v[k].hi == UINT32_MAX) { 195 cur = UINT32_MAX; 196 break; 197 } 198 cur = b->v[k].hi + 1; 199 if (cur > hi) break; 200 k++; 201 } 202 if (cur <= hi) scalar_set_append_merged(&out, cur, hi); 203 } 204 return out; 205 } 206 207 static ScalarSet scalar_set_complement(GramgenContext* ctx, 208 const ScalarSet* set) { 209 ScalarSet universe = kit_gram_scalar_set_universe(ctx); 210 return scalar_set_difference(ctx, &universe, set); 211 } 212 213 static ScalarSet scalar_set_from_unicode_set(GramgenContext* ctx, 214 const KitGramUnicodeSet* set) { 215 ScalarSet out = {.ctx = ctx}; 216 for (size_t i = 0; i < set->count; i++) { 217 scalar_set_append_scalar_range(&out, set->ranges[i].first, 218 set->ranges[i].last); 219 } 220 return out; 221 } 222 223 static ScalarSet resolve_unicode_property_set(GramgenContext* ctx, 224 const char* spec, Loc loc) { 225 ScalarSet cached = {0}; 226 if (scalar_set_cache_get(ctx, "property", spec, strlen(spec), &cached)) 227 return cached; 228 KitGramUnicodeSet raw = {0}; 229 KitGramUnicodePropStatus st = kit_gram_unicode_resolve_property_spec(spec, &raw); 230 if (st == KIT_GRAM_UNICODE_PROP_UNKNOWN_PROPERTY) 231 kit_gram_error(ctx, loc, "unknown Unicode property %s", spec); 232 if (st == KIT_GRAM_UNICODE_PROP_UNKNOWN_VALUE) 233 kit_gram_error(ctx, loc, "unknown Unicode property value in %s", spec); 234 ScalarSet out = scalar_set_from_unicode_set(ctx, &raw); 235 return scalar_set_cache_put(ctx, "property", spec, strlen(spec), out); 236 } 237 238 typedef struct { 239 GramgenContext* ctx; 240 Str raw; 241 Loc loc; 242 size_t i; 243 } UClassParser; 244 245 static int uc_peek(UClassParser* p, size_t n) { 246 size_t j = p->i + n; 247 return j < p->raw.len ? (unsigned char)p->raw.s[j] : 0; 248 } 249 250 static int uc_advance(UClassParser* p) { 251 int c = uc_peek(p, 0); 252 if (c) p->i++; 253 return c; 254 } 255 256 static uint32_t uc_read_hex(UClassParser* p, int n, const char* what) { 257 uint32_t value = 0; 258 for (int i = 0; i < n; i++) { 259 int c = uc_peek(p, 0); 260 if (!c) kit_gram_error(p->ctx, p->loc, "short %s escape", what); 261 int digit = hex_val(c); 262 if (digit < 0) kit_gram_error(p->ctx, p->loc, "bad %s escape", what); 263 uc_advance(p); 264 value = (value << 4) | (uint32_t)digit; 265 } 266 return value; 267 } 268 269 static uint32_t uc_read_braced_hex(UClassParser* p) { 270 if (uc_peek(p, 0) != '{') kit_gram_error(p->ctx, p->loc, "bad Unicode escape"); 271 uc_advance(p); 272 uint32_t value = 0; 273 size_t ndigits = 0; 274 while (1) { 275 int c = uc_peek(p, 0); 276 if (!c) kit_gram_error(p->ctx, p->loc, "unterminated Unicode escape"); 277 if (c == '}') { 278 uc_advance(p); 279 if (!ndigits) kit_gram_error(p->ctx, p->loc, "empty Unicode escape"); 280 return value; 281 } 282 int digit = hex_val(c); 283 if (digit < 0) kit_gram_error(p->ctx, p->loc, "bad Unicode escape"); 284 uc_advance(p); 285 value = (value << 4) | (uint32_t)digit; 286 ndigits++; 287 if (value > UNICODE_MAX_SCALAR) 288 kit_gram_error(p->ctx, p->loc, "invalid Unicode scalar U+%04X", 289 (unsigned)value); 290 } 291 } 292 293 static uint32_t uc_validate_scalar(UClassParser* p, uint32_t cp) { 294 if (!unicode_is_scalar_value(cp)) 295 kit_gram_error(p->ctx, p->loc, "invalid Unicode scalar U+%04X", 296 (unsigned)cp); 297 return cp; 298 } 299 300 static ScalarSet uc_parse_class(UClassParser* p); 301 302 static ScalarSet uc_property_escape(UClassParser* p) { 303 uc_advance(p); 304 int kind = uc_advance(p); 305 if (uc_advance(p) != '{') 306 kit_gram_error(p->ctx, p->loc, "malformed Unicode property escape"); 307 size_t start = p->i; 308 while (uc_peek(p, 0) && uc_peek(p, 0) != '}') uc_advance(p); 309 if (uc_peek(p, 0) != '}') 310 kit_gram_error(p->ctx, p->loc, "unterminated Unicode property escape"); 311 size_t len = p->i - start; 312 if (!len) kit_gram_error(p->ctx, p->loc, "empty Unicode property escape"); 313 char* spec = xstrndup(p->ctx, p->raw.s + start, len); 314 uc_advance(p); 315 ScalarSet out = resolve_unicode_property_set(p->ctx, spec, p->loc); 316 if (kind == 'P') out = scalar_set_complement(p->ctx, &out); 317 return out; 318 } 319 320 static uint32_t uc_scalar_escape(UClassParser* p) { 321 uc_advance(p); 322 int e = uc_peek(p, 0); 323 if (!e) kit_gram_error(p->ctx, p->loc, "unterminated character class"); 324 uc_advance(p); 325 switch (e) { 326 case 'n': 327 return '\n'; 328 case 'r': 329 return '\r'; 330 case 't': 331 return '\t'; 332 case '0': 333 return 0; 334 case 'x': 335 return uc_read_hex(p, 2, "hex"); 336 case 'u': 337 if (uc_peek(p, 0) == '{') 338 return uc_validate_scalar(p, uc_read_braced_hex(p)); 339 return uc_validate_scalar(p, uc_read_hex(p, 4, "Unicode")); 340 case 'U': 341 return uc_validate_scalar(p, uc_read_hex(p, 8, "Unicode")); 342 default: 343 return uc_validate_scalar(p, (uint32_t)e); 344 } 345 } 346 347 /* ASCII shorthand set for \d \w \s (and uppercase complements). ASCII even in 348 * utf8 mode, matching the byte path; reach for \p{...} for Unicode classes. */ 349 static ScalarSet uc_shorthand_set(UClassParser* p, int sh) { 350 ScalarRange r[4]; 351 size_t n = 0; 352 int lower = (sh >= 'A' && sh <= 'Z') ? sh + 32 : sh; 353 if (lower == 'd') { 354 r[n++] = (ScalarRange){'0', '9'}; 355 } else if (lower == 'w') { 356 r[n++] = (ScalarRange){'0', '9'}; 357 r[n++] = (ScalarRange){'A', 'Z'}; 358 r[n++] = (ScalarRange){'a', 'z'}; 359 r[n++] = (ScalarRange){'_', '_'}; 360 } else { /* 's': \t \n \v \f \r and space */ 361 r[n++] = (ScalarRange){0x09, 0x0D}; 362 r[n++] = (ScalarRange){0x20, 0x20}; 363 } 364 ScalarSet out = scalar_set_normalized(p->ctx, r, n); 365 if (sh >= 'A' && sh <= 'Z') out = scalar_set_complement(p->ctx, &out); 366 return out; 367 } 368 369 static ScalarSet uc_atom(UClassParser* p) { 370 int c = uc_peek(p, 0); 371 if (!c) kit_gram_error(p->ctx, p->loc, "unterminated character class"); 372 if (c == '[') return uc_parse_class(p); 373 if (c == '\\') { 374 if ((uc_peek(p, 1) == 'p' || uc_peek(p, 1) == 'P') && uc_peek(p, 2) == '{') 375 return uc_property_escape(p); 376 int sh = uc_peek(p, 1); 377 if (sh == 'd' || sh == 'D' || sh == 'w' || sh == 'W' || sh == 's' || 378 sh == 'S') { 379 uc_advance(p); 380 uc_advance(p); 381 return uc_shorthand_set(p, sh); 382 } 383 return scalar_set_single(p->ctx, uc_scalar_escape(p), p->loc); 384 } 385 if (c == ']' || c == '-' || c == '^') 386 kit_gram_error(p->ctx, p->loc, 387 "literal '%c' must be escaped in character class", c); 388 uint32_t cp = 0; 389 size_t nbytes = 0; 390 KitGramUtf8Status st = kit_gram_utf8_decode_one( 391 (const unsigned char*)p->raw.s + p->i, p->raw.len - p->i, &cp, &nbytes); 392 if (st != KIT_GRAM_UTF8_OK) 393 kit_gram_error(p->ctx, p->loc, "invalid UTF-8 in Unicode character class"); 394 p->i += nbytes; 395 return scalar_set_single(p->ctx, cp, p->loc); 396 } 397 398 static ScalarSet uc_range_or_atom(UClassParser* p) { 399 ScalarSet left = uc_atom(p); 400 if (uc_peek(p, 0) == '-' && uc_peek(p, 1) != '-') { 401 uc_advance(p); 402 if (!uc_peek(p, 0) || uc_peek(p, 0) == ']') 403 kit_gram_error(p->ctx, p->loc, 404 "literal '-' must be escaped in character class"); 405 ScalarSet right = uc_atom(p); 406 if (left.n != 1 || left.v[0].lo != left.v[0].hi || right.n != 1 || 407 right.v[0].lo != right.v[0].hi) 408 kit_gram_error(p->ctx, p->loc, 409 "range endpoints must be single scalar values"); 410 uint32_t lo = left.v[0].lo; 411 uint32_t hi = right.v[0].lo; 412 if (lo > hi) 413 kit_gram_error(p->ctx, p->loc, "reversed range in character class"); 414 ScalarRange r = {lo, hi}; 415 ScalarSet out = scalar_set_normalized(p->ctx, &r, 1); 416 kit_gram_scalar_set_require_nonempty(p->ctx, &out, p->loc); 417 return out; 418 } 419 return left; 420 } 421 422 static ScalarSet uc_union_expr(UClassParser* p) { 423 ScalarSet out = {.ctx = p->ctx}; 424 int saw = 0; 425 while (1) { 426 int c = uc_peek(p, 0); 427 if (!c || c == ']') break; 428 if (c == '&' && uc_peek(p, 1) == '&') break; 429 if (c == '-' && uc_peek(p, 1) == '-') break; 430 ScalarSet item = uc_range_or_atom(p); 431 out = saw ? scalar_set_union(p->ctx, &out, &item) : item; 432 saw = 1; 433 } 434 if (!saw) kit_gram_error(p->ctx, p->loc, "empty Unicode character class"); 435 return out; 436 } 437 438 static ScalarSet uc_expr(UClassParser* p) { 439 ScalarSet out = uc_union_expr(p); 440 while (1) { 441 if (uc_peek(p, 0) == '&' && uc_peek(p, 1) == '&') { 442 p->i += 2; 443 ScalarSet rhs = uc_union_expr(p); 444 out = scalar_set_intersect(p->ctx, &out, &rhs); 445 } else if (uc_peek(p, 0) == '-' && uc_peek(p, 1) == '-') { 446 p->i += 2; 447 ScalarSet rhs = uc_union_expr(p); 448 out = scalar_set_difference(p->ctx, &out, &rhs); 449 } else { 450 break; 451 } 452 } 453 return out; 454 } 455 456 static ScalarSet uc_parse_class(UClassParser* p) { 457 if (uc_advance(p) != '[') 458 kit_gram_error(p->ctx, p->loc, "expected character class"); 459 int negate = 0; 460 if (uc_peek(p, 0) == '^') { 461 negate = 1; 462 uc_advance(p); 463 } 464 ScalarSet out = uc_expr(p); 465 if (uc_peek(p, 0) != ']') 466 kit_gram_error(p->ctx, p->loc, "unterminated character class"); 467 uc_advance(p); 468 if (negate) out = scalar_set_complement(p->ctx, &out); 469 kit_gram_scalar_set_require_nonempty(p->ctx, &out, p->loc); 470 return out; 471 } 472 473 ScalarSet kit_gram_unicode_char_class_set(GramgenContext* ctx, Str raw, 474 Loc loc) { 475 ScalarSet cached = {0}; 476 if (scalar_set_cache_get(ctx, "class", raw.s, raw.len, &cached)) 477 return cached; 478 UClassParser p = {.ctx = ctx, .raw = raw, .loc = loc}; 479 ScalarSet out = uc_parse_class(&p); 480 if (p.i != raw.len) 481 kit_gram_error(ctx, loc, "trailing input in Unicode character class"); 482 kit_gram_scalar_set_require_nonempty(ctx, &out, loc); 483 return scalar_set_cache_put(ctx, "class", raw.s, raw.len, out); 484 } 485 486 ScalarSet kit_gram_unicode_prop_atom_set(GramgenContext* ctx, Str raw, Loc loc) { 487 ScalarSet cached = {0}; 488 if (scalar_set_cache_get(ctx, "prop_atom", raw.s, raw.len, &cached)) 489 return cached; 490 if (raw.len < 4 || raw.s[0] != '\\' || (raw.s[1] != 'p' && raw.s[1] != 'P') || 491 raw.s[2] != '{' || raw.s[raw.len - 1] != '}') 492 kit_gram_error(ctx, loc, "malformed Unicode property escape"); 493 char* spec = xstrndup(ctx, raw.s + 3, raw.len - 4); 494 if (!spec[0]) kit_gram_error(ctx, loc, "empty Unicode property escape"); 495 ScalarSet out = resolve_unicode_property_set(ctx, spec, loc); 496 if (raw.s[1] == 'P') out = scalar_set_complement(ctx, &out); 497 kit_gram_scalar_set_require_nonempty(ctx, &out, loc); 498 return scalar_set_cache_put(ctx, "prop_atom", raw.s, raw.len, out); 499 }