1 /* 2 * Copyright 2010 Nexenta Systems, Inc. All rights reserved. 3 * Copyright 2015 John Marino <draco@marino.st> 4 * 5 * This source code is derived from the illumos localedef command, and 6 * provided under BSD-style license terms by Nexenta Systems, Inc. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28 * POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 /* 32 * LC_COLLATE database generation routines for localedef. 33 */ 34 35 #include <sys/types.h> 36 #include <sys/tree.h> 37 38 #include <stdio.h> 39 #include <stddef.h> 40 #include <stdlib.h> 41 #include <errno.h> 42 #include <string.h> 43 #include <unistd.h> 44 #include <wchar.h> 45 #include <limits.h> 46 #include "localedef.h" 47 #include "parser.h" 48 #include "collate.h" 49 50 /* 51 * Design notes. 52 * 53 * It will be extremely helpful to the reader if they have access to 54 * the localedef and locale file format specifications available. 55 * Latest versions of these are available from www.opengroup.org. 56 * 57 * The design for the collation code is a bit complex. The goal is a 58 * single collation database as described in collate.h (in 59 * libc/port/locale). However, there are some other tidbits: 60 * 61 * a) The substitution entries are now a directly indexable array. A 62 * priority elsewhere in the table is taken as an index into the 63 * substitution table if it has a high bit (COLLATE_SUBST_PRIORITY) 64 * set. (The bit is cleared and the result is the index into the 65 * table. 66 * 67 * b) We eliminate duplicate entries into the substitution table. 68 * This saves a lot of space. 69 * 70 * c) The priorities for each level are "compressed", so that each 71 * sorting level has consecutively numbered priorities starting at 1. 72 * (O is reserved for the ignore priority.) This means sort levels 73 * which only have a few distinct priorities can represent the 74 * priority level in fewer bits, which makes the strxfrm output 75 * smaller. 76 * 77 * d) We record the total number of priorities so that strxfrm can 78 * figure out how many bytes to expand a numeric priority into. 79 * 80 * e) For the UNDEFINED pass (the last pass), we record the maximum 81 * number of bits needed to uniquely prioritize these entries, so that 82 * the last pass can also use smaller strxfrm output when possible. 83 * 84 * f) Priorities with the sign bit set are verboten. This works out 85 * because no active character set needs that bit to carry significant 86 * information once the character is in wide form. 87 * 88 * To process the entire data to make the database, we actually run 89 * multiple passes over the data. 90 * 91 * The first pass, which is done at parse time, identifies elements, 92 * substitutions, and such, and records them in priority order. As 93 * some priorities can refer to other priorities, using forward 94 * references, we use a table of references indicating whether the 95 * priority's value has been resolved, or whether it is still a 96 * reference. 97 * 98 * The second pass walks over all the items in priority order, noting 99 * that they are used directly, and not just an indirect reference. 100 * This is done by creating a "weight" structure for the item. The 101 * weights are stashed in an RB tree sorted by relative "priority". 102 * 103 * The third pass walks over all the weight structures, in priority 104 * order, and assigns a new monotonically increasing (per sort level) 105 * weight value to them. These are the values that will actually be 106 * written to the file. 107 * 108 * The fourth pass just writes the data out. 109 */ 110 111 /* 112 * In order to resolve the priorities, we create a table of priorities. 113 * Entries in the table can be in one of three states. 114 * 115 * UNKNOWN is for newly allocated entries, and indicates that nothing 116 * is known about the priority. (For example, when new entries are created 117 * for collating-symbols, this is the value assigned for them until the 118 * collating symbol's order has been determined. 119 * 120 * RESOLVED is used for an entry where the priority indicates the final 121 * numeric weight. 122 * 123 * REFER is used for entries that reference other entries. Typically 124 * this is used for forward references. A collating-symbol can never 125 * have this value. 126 * 127 * The "pass" field is used during final resolution to aid in detection 128 * of referencing loops. (For example <A> depends on <B>, but <B> has its 129 * priority dependent on <A>.) 130 */ 131 typedef enum { 132 UNKNOWN, /* priority is totally unknown */ 133 RESOLVED, /* priority value fully resolved */ 134 REFER /* priority is a reference (index) */ 135 } res_t; 136 137 typedef struct weight { 138 int32_t pri; 139 int opt; 140 RB_ENTRY(weight) entry; 141 } weight_t; 142 143 typedef struct priority { 144 res_t res; 145 int32_t pri; 146 int pass; 147 int lineno; 148 } collpri_t; 149 150 #define NUM_WT collinfo.directive_count 151 152 /* 153 * These are the abstract collating symbols, which are just a symbolic 154 * way to reference a priority. 155 */ 156 struct collsym { 157 char *name; 158 int32_t ref; 159 RB_ENTRY(collsym) entry; 160 }; 161 162 /* 163 * These are also abstract collating symbols, but we allow them to have 164 * different priorities at different levels. 165 */ 166 typedef struct collundef { 167 char *name; 168 int32_t ref[COLL_WEIGHTS_MAX]; 169 RB_ENTRY(collundef) entry; 170 } collundef_t; 171 172 /* 173 * These are called "chains" in libc. This records the fact that two 174 * more characters should be treated as a single collating entity when 175 * they appear together. For example, in Spanish <C><h> gets collated 176 * as a character between <C> and <D>. 177 */ 178 struct collelem { 179 char *symbol; 180 wchar_t *expand; 181 int32_t ref[COLL_WEIGHTS_MAX]; 182 RB_ENTRY(collelem) rb_bysymbol; 183 RB_ENTRY(collelem) rb_byexpand; 184 }; 185 186 /* 187 * Individual characters have a sequence of weights as well. 188 */ 189 typedef struct collchar { 190 wchar_t wc; 191 int32_t ref[COLL_WEIGHTS_MAX]; 192 RB_ENTRY(collchar) entry; 193 } collchar_t; 194 195 /* 196 * Substitution entries. The key is itself a priority. Note that 197 * when we create one of these, we *automatically* wind up with a 198 * fully resolved priority for the key, because creation of 199 * substitutions creates a resolved priority at the same time. 200 */ 201 typedef struct subst{ 202 int32_t key; 203 int32_t ref[COLLATE_STR_LEN]; 204 RB_ENTRY(subst) entry; 205 RB_ENTRY(subst) entry_ref; 206 } subst_t; 207 208 static RB_HEAD(collsyms, collsym) collsyms; 209 static RB_HEAD(collundefs, collundef) collundefs; 210 static RB_HEAD(elem_by_symbol, collelem) elem_by_symbol; 211 static RB_HEAD(elem_by_expand, collelem) elem_by_expand; 212 static RB_HEAD(collchars, collchar) collchars; 213 static RB_HEAD(substs, subst) substs[COLL_WEIGHTS_MAX]; 214 static RB_HEAD(substs_ref, subst) substs_ref[COLL_WEIGHTS_MAX]; 215 static RB_HEAD(weights, weight) weights[COLL_WEIGHTS_MAX]; 216 static int32_t nweight[COLL_WEIGHTS_MAX]; 217 218 /* 219 * This is state tracking for the ellipsis token. Note that we start 220 * the initial values so that the ellipsis logic will think we got a 221 * magic starting value of NUL. It starts at minus one because the 222 * starting point is exclusive -- i.e. the starting point is not 223 * itself handled by the ellipsis code. 224 */ 225 static int currorder = EOF; 226 static int lastorder = EOF; 227 static collelem_t *currelem; 228 static collchar_t *currchar; 229 static collundef_t *currundef; 230 static wchar_t ellipsis_start = 0; 231 static int32_t ellipsis_weights[COLL_WEIGHTS_MAX]; 232 233 /* 234 * We keep a running tally of weights. 235 */ 236 static int nextpri = 1; 237 static int nextsubst[COLL_WEIGHTS_MAX] = { 0 }; 238 239 /* 240 * This array collects up the weights for each level. 241 */ 242 static int32_t order_weights[COLL_WEIGHTS_MAX]; 243 static int curr_weight = 0; 244 static int32_t subst_weights[COLLATE_STR_LEN]; 245 static int curr_subst = 0; 246 247 /* 248 * Some initial priority values. 249 */ 250 static int32_t pri_undefined[COLL_WEIGHTS_MAX]; 251 static int32_t pri_ignore; 252 253 static collate_info_t collinfo; 254 255 static collpri_t *prilist = NULL; 256 static int numpri = 0; 257 static int maxpri = 0; 258 259 static void start_order(int); 260 261 static int32_t 262 new_pri(void) 263 { 264 int i; 265 266 if (numpri >= maxpri) { 267 maxpri = maxpri ? maxpri * 2 : 1024; 268 prilist = realloc(prilist, sizeof (collpri_t) * maxpri); 269 if (prilist == NULL) { 270 fprintf(stderr,"out of memory"); 271 return (-1); 272 } 273 for (i = numpri; i < maxpri; i++) { 274 prilist[i].res = UNKNOWN; 275 prilist[i].pri = 0; 276 prilist[i].pass = 0; 277 } 278 } 279 return (numpri++); 280 } 281 282 static collpri_t * 283 get_pri(int32_t ref) 284 { 285 if ((ref < 0) || (ref > numpri)) { 286 INTERR; 287 return (NULL); 288 } 289 return (&prilist[ref]); 290 } 291 292 static void 293 set_pri(int32_t ref, int32_t v, res_t res) 294 { 295 collpri_t *pri; 296 297 pri = get_pri(ref); 298 299 if ((res == REFER) && ((v < 0) || (v >= numpri))) { 300 INTERR; 301 } 302 303 /* Resolve self references */ 304 if ((res == REFER) && (ref == v)) { 305 v = nextpri; 306 res = RESOLVED; 307 } 308 309 if (pri->res != UNKNOWN) { 310 warn("repeated item in order list (first on %d)", 311 pri->lineno); 312 return; 313 } 314 pri->lineno = lineno; 315 pri->pri = v; 316 pri->res = res; 317 } 318 319 static int32_t 320 resolve_pri(int32_t ref) 321 { 322 collpri_t *pri; 323 static int32_t pass = 0; 324 325 pri = get_pri(ref); 326 pass++; 327 while (pri->res == REFER) { 328 if (pri->pass == pass) { 329 /* report a line with the circular symbol */ 330 lineno = pri->lineno; 331 fprintf(stderr,"circular reference in order list"); 332 return (-1); 333 } 334 if ((pri->pri < 0) || (pri->pri >= numpri)) { 335 INTERR; 336 return (-1); 337 } 338 pri->pass = pass; 339 pri = &prilist[pri->pri]; 340 } 341 342 if (pri->res == UNKNOWN) { 343 return (-1); 344 } 345 if (pri->res != RESOLVED) 346 INTERR; 347 348 return (pri->pri); 349 } 350 351 static int 352 weight_compare(const void *n1, const void *n2) 353 { 354 int32_t k1 = ((const weight_t *)n1)->pri; 355 int32_t k2 = ((const weight_t *)n2)->pri; 356 357 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 358 } 359 360 RB_PROTOTYPE_STATIC(weights, weight, entry, weight_compare); 361 RB_GENERATE(weights, weight, entry, weight_compare); 362 363 static int 364 collsym_compare(const void *n1, const void *n2) 365 { 366 const collsym_t *c1 = n1; 367 const collsym_t *c2 = n2; 368 int rv; 369 370 rv = strcmp(c1->name, c2->name); 371 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 372 } 373 374 RB_PROTOTYPE_STATIC(collsyms, collsym, entry, collsym_compare); 375 RB_GENERATE(collsyms, collsym, entry, collsym_compare); 376 377 static int 378 collundef_compare(const void *n1, const void *n2) 379 { 380 const collundef_t *c1 = n1; 381 const collundef_t *c2 = n2; 382 int rv; 383 384 rv = strcmp(c1->name, c2->name); 385 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 386 } 387 388 RB_PROTOTYPE_STATIC(collundefs, collundef, entry, collundef_compare); 389 RB_GENERATE(collundefs, collundef, entry, collundef_compare); 390 391 static int 392 element_compare_symbol(const void *n1, const void *n2) 393 { 394 const collelem_t *c1 = n1; 395 const collelem_t *c2 = n2; 396 int rv; 397 398 rv = strcmp(c1->symbol, c2->symbol); 399 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 400 } 401 402 RB_PROTOTYPE_STATIC(elem_by_symbol, collelem, rb_bysymbol, element_compare_symbol); 403 RB_GENERATE(elem_by_symbol, collelem, rb_bysymbol, element_compare_symbol); 404 405 static int 406 element_compare_expand(const void *n1, const void *n2) 407 { 408 const collelem_t *c1 = n1; 409 const collelem_t *c2 = n2; 410 int rv; 411 412 rv = wcscmp(c1->expand, c2->expand); 413 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 414 } 415 416 RB_PROTOTYPE_STATIC(elem_by_expand, collelem, rb_byexpand, element_compare_expand); 417 RB_GENERATE(elem_by_expand, collelem, rb_byexpand, element_compare_expand); 418 419 static int 420 collchar_compare(const void *n1, const void *n2) 421 { 422 wchar_t k1 = ((const collchar_t *)n1)->wc; 423 wchar_t k2 = ((const collchar_t *)n2)->wc; 424 425 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 426 } 427 428 RB_PROTOTYPE_STATIC(collchars, collchar, entry, collchar_compare); 429 RB_GENERATE(collchars, collchar, entry, collchar_compare); 430 431 static int 432 subst_compare(const void *n1, const void *n2) 433 { 434 int32_t k1 = ((const subst_t *)n1)->key; 435 int32_t k2 = ((const subst_t *)n2)->key; 436 437 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 438 } 439 440 RB_PROTOTYPE_STATIC(substs, subst, entry, subst_compare); 441 RB_GENERATE(substs, subst, entry, subst_compare); 442 443 static int 444 subst_compare_ref(const void *n1, const void *n2) 445 { 446 const wchar_t *c1 = ((const subst_t *)n1)->ref; 447 const wchar_t *c2 = ((const subst_t *)n2)->ref; 448 int rv; 449 450 rv = wcscmp(c1, c2); 451 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 452 } 453 454 RB_PROTOTYPE_STATIC(substs_ref, subst, entry_ref, subst_compare_ref); 455 RB_GENERATE(substs_ref, subst, entry_ref, subst_compare_ref); 456 457 void 458 init_collate(void) 459 { 460 int i; 461 462 RB_INIT(&collsyms); 463 464 RB_INIT(&collundefs); 465 466 RB_INIT(&elem_by_symbol); 467 468 RB_INIT(&elem_by_expand); 469 470 RB_INIT(&collchars); 471 472 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 473 RB_INIT(&substs[i]); 474 RB_INIT(&substs_ref[i]); 475 RB_INIT(&weights[i]); 476 nweight[i] = 1; 477 } 478 479 (void) memset(&collinfo, 0, sizeof (collinfo)); 480 481 /* allocate some initial priorities */ 482 pri_ignore = new_pri(); 483 484 set_pri(pri_ignore, 0, RESOLVED); 485 486 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 487 pri_undefined[i] = new_pri(); 488 489 /* we will override this later */ 490 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN); 491 } 492 } 493 494 void 495 define_collsym(char *name) 496 { 497 collsym_t *sym; 498 499 if ((sym = calloc(sizeof (*sym), 1)) == NULL) { 500 fprintf(stderr,"out of memory"); 501 return; 502 } 503 sym->name = name; 504 sym->ref = new_pri(); 505 506 if (RB_FIND(collsyms, &collsyms, sym) != NULL) { 507 /* 508 * This should never happen because we are only called 509 * for undefined symbols. 510 */ 511 INTERR; 512 return; 513 } 514 RB_INSERT(collsyms, &collsyms, sym); 515 } 516 517 collsym_t * 518 lookup_collsym(char *name) 519 { 520 collsym_t srch; 521 522 srch.name = name; 523 return (RB_FIND(collsyms, &collsyms, &srch)); 524 } 525 526 collelem_t * 527 lookup_collelem(char *symbol) 528 { 529 collelem_t srch; 530 531 srch.symbol = symbol; 532 return (RB_FIND(elem_by_symbol, &elem_by_symbol, &srch)); 533 } 534 535 static collundef_t * 536 get_collundef(char *name) 537 { 538 collundef_t srch; 539 collundef_t *ud; 540 int i; 541 542 srch.name = name; 543 if ((ud = RB_FIND(collundefs, &collundefs, &srch)) == NULL) { 544 if (((ud = calloc(sizeof (*ud), 1)) == NULL) || 545 ((ud->name = strdup(name)) == NULL)) { 546 fprintf(stderr,"out of memory"); 547 return (NULL); 548 } 549 for (i = 0; i < NUM_WT; i++) { 550 ud->ref[i] = new_pri(); 551 } 552 RB_INSERT(collundefs, &collundefs, ud); 553 } 554 add_charmap_undefined(name); 555 return (ud); 556 } 557 558 static collchar_t * 559 get_collchar(wchar_t wc, int create) 560 { 561 collchar_t srch; 562 collchar_t *cc; 563 int i; 564 565 srch.wc = wc; 566 cc = RB_FIND(collchars, &collchars, &srch); 567 if ((cc == NULL) && create) { 568 if ((cc = calloc(sizeof (*cc), 1)) == NULL) { 569 fprintf(stderr, "out of memory"); 570 return (NULL); 571 } 572 for (i = 0; i < NUM_WT; i++) { 573 cc->ref[i] = new_pri(); 574 } 575 cc->wc = wc; 576 RB_INSERT(collchars, &collchars, cc); 577 } 578 return (cc); 579 } 580 581 void 582 end_order_collsym(collsym_t *sym) 583 { 584 start_order(T_COLLSYM); 585 /* update the weight */ 586 587 set_pri(sym->ref, nextpri, RESOLVED); 588 nextpri++; 589 } 590 591 void 592 end_order(void) 593 { 594 int i; 595 int32_t pri; 596 int32_t ref; 597 collpri_t *p; 598 599 /* advance the priority/weight */ 600 pri = nextpri; 601 602 switch (currorder) { 603 case T_CHAR: 604 for (i = 0; i < NUM_WT; i++) { 605 if (((ref = order_weights[i]) < 0) || 606 ((p = get_pri(ref)) == NULL) || 607 (p->pri == -1)) { 608 /* unspecified weight is a self reference */ 609 set_pri(currchar->ref[i], pri, RESOLVED); 610 } else { 611 set_pri(currchar->ref[i], ref, REFER); 612 } 613 order_weights[i] = -1; 614 } 615 616 /* leave a cookie trail in case next symbol is ellipsis */ 617 ellipsis_start = currchar->wc + 1; 618 currchar = NULL; 619 break; 620 621 case T_ELLIPSIS: 622 /* save off the weights were we can find them */ 623 for (i = 0; i < NUM_WT; i++) { 624 ellipsis_weights[i] = order_weights[i]; 625 order_weights[i] = -1; 626 } 627 break; 628 629 case T_COLLELEM: 630 if (currelem == NULL) { 631 INTERR; 632 } else { 633 for (i = 0; i < NUM_WT; i++) { 634 635 if (((ref = order_weights[i]) < 0) || 636 ((p = get_pri(ref)) == NULL) || 637 (p->pri == -1)) { 638 set_pri(currelem->ref[i], pri, 639 RESOLVED); 640 } else { 641 set_pri(currelem->ref[i], ref, REFER); 642 } 643 order_weights[i] = -1; 644 } 645 } 646 break; 647 648 case T_UNDEFINED: 649 for (i = 0; i < NUM_WT; i++) { 650 if (((ref = order_weights[i]) < 0) || 651 ((p = get_pri(ref)) == NULL) || 652 (p->pri == -1)) { 653 set_pri(pri_undefined[i], -1, RESOLVED); 654 } else { 655 set_pri(pri_undefined[i], ref, REFER); 656 } 657 order_weights[i] = -1; 658 } 659 break; 660 661 case T_SYMBOL: 662 for (i = 0; i < NUM_WT; i++) { 663 if (((ref = order_weights[i]) < 0) || 664 ((p = get_pri(ref)) == NULL) || 665 (p->pri == -1)) { 666 set_pri(currundef->ref[i], pri, RESOLVED); 667 } else { 668 set_pri(currundef->ref[i], ref, REFER); 669 } 670 order_weights[i] = -1; 671 } 672 break; 673 674 default: 675 INTERR; 676 } 677 678 nextpri++; 679 } 680 681 static void 682 start_order(int type) 683 { 684 int i; 685 686 lastorder = currorder; 687 currorder = type; 688 689 /* this is used to protect ELLIPSIS processing */ 690 if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) { 691 fprintf(stderr, "character value expected"); 692 } 693 694 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 695 order_weights[i] = -1; 696 } 697 curr_weight = 0; 698 } 699 700 void 701 start_order_undefined(void) 702 { 703 start_order(T_UNDEFINED); 704 } 705 706 void 707 start_order_symbol(char *name) 708 { 709 currundef = get_collundef(name); 710 start_order(T_SYMBOL); 711 } 712 713 void 714 start_order_char(wchar_t wc) 715 { 716 collchar_t *cc; 717 int32_t ref; 718 719 start_order(T_CHAR); 720 721 /* 722 * If we last saw an ellipsis, then we need to close the range. 723 * Handle that here. Note that we have to be careful because the 724 * items *inside* the range are treated exclusiveley to the items 725 * outside of the range. The ends of the range can have quite 726 * different weights than the range members. 727 */ 728 if (lastorder == T_ELLIPSIS) { 729 int i; 730 731 if (wc < ellipsis_start) { 732 fprintf(stderr, "malformed range!"); 733 return; 734 } 735 while (ellipsis_start < wc) { 736 /* 737 * pick all of the saved weights for the 738 * ellipsis. note that -1 encodes for the 739 * ellipsis itself, which means to take the 740 * current relative priority. 741 */ 742 if ((cc = get_collchar(ellipsis_start, 1)) == NULL) { 743 INTERR; 744 return; 745 } 746 for (i = 0; i < NUM_WT; i++) { 747 collpri_t *p; 748 if (((ref = ellipsis_weights[i]) == -1) || 749 ((p = get_pri(ref)) == NULL) || 750 (p->pri == -1)) { 751 set_pri(cc->ref[i], nextpri, RESOLVED); 752 } else { 753 set_pri(cc->ref[i], ref, REFER); 754 } 755 ellipsis_weights[i] = 0; 756 } 757 ellipsis_start++; 758 nextpri++; 759 } 760 } 761 762 currchar = get_collchar(wc, 1); 763 } 764 765 void 766 start_order_collelem(collelem_t *e) 767 { 768 start_order(T_COLLELEM); 769 currelem = e; 770 } 771 772 void 773 start_order_ellipsis(void) 774 { 775 int i; 776 777 start_order(T_ELLIPSIS); 778 779 if (lastorder != T_CHAR) { 780 fprintf(stderr, "illegal starting point for range"); 781 return; 782 } 783 784 for (i = 0; i < NUM_WT; i++) { 785 ellipsis_weights[i] = order_weights[i]; 786 } 787 } 788 789 void 790 define_collelem(char *name, wchar_t *wcs) 791 { 792 collelem_t *e; 793 int i; 794 795 if (wcslen(wcs) >= COLLATE_STR_LEN) { 796 fprintf(stderr,"expanded collation element too long"); 797 return; 798 } 799 800 if ((e = calloc(sizeof (*e), 1)) == NULL) { 801 fprintf(stderr, "out of memory"); 802 return; 803 } 804 e->expand = wcs; 805 e->symbol = name; 806 807 /* 808 * This is executed before the order statement, so we don't 809 * know how many priorities we *really* need. We allocate one 810 * for each possible weight. Not a big deal, as collating-elements 811 * prove to be quite rare. 812 */ 813 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 814 e->ref[i] = new_pri(); 815 } 816 817 /* A character sequence can only reduce to one element. */ 818 if ((RB_FIND(elem_by_symbol, &elem_by_symbol, e) != NULL) || 819 (RB_FIND(elem_by_expand, &elem_by_expand, e) != NULL)) { 820 fprintf(stderr, "duplicate collating element definition"); 821 return; 822 } 823 RB_INSERT(elem_by_symbol, &elem_by_symbol, e); 824 RB_INSERT(elem_by_expand, &elem_by_expand, e); 825 } 826 827 void 828 add_order_bit(int kw) 829 { 830 uint8_t bit = DIRECTIVE_UNDEF; 831 832 switch (kw) { 833 case T_FORWARD: 834 bit = DIRECTIVE_FORWARD; 835 break; 836 case T_BACKWARD: 837 bit = DIRECTIVE_BACKWARD; 838 break; 839 case T_POSITION: 840 bit = DIRECTIVE_POSITION; 841 break; 842 default: 843 INTERR; 844 break; 845 } 846 collinfo.directive[collinfo.directive_count] |= bit; 847 } 848 849 void 850 add_order_directive(void) 851 { 852 if (collinfo.directive_count >= COLL_WEIGHTS_MAX) { 853 fprintf(stderr,"too many directives (max %d)", COLL_WEIGHTS_MAX); 854 } 855 collinfo.directive_count++; 856 } 857 858 static void 859 add_order_pri(int32_t ref) 860 { 861 if (curr_weight >= NUM_WT) { 862 fprintf(stderr,"too many weights (max %d)", NUM_WT); 863 return; 864 } 865 order_weights[curr_weight] = ref; 866 curr_weight++; 867 } 868 869 void 870 add_order_collsym(collsym_t *s) 871 { 872 add_order_pri(s->ref); 873 } 874 875 void 876 add_order_char(wchar_t wc) 877 { 878 collchar_t *cc; 879 880 if ((cc = get_collchar(wc, 1)) == NULL) { 881 INTERR; 882 return; 883 } 884 885 add_order_pri(cc->ref[curr_weight]); 886 } 887 888 void 889 add_order_collelem(collelem_t *e) 890 { 891 add_order_pri(e->ref[curr_weight]); 892 } 893 894 void 895 add_order_ignore(void) 896 { 897 add_order_pri(pri_ignore); 898 } 899 900 void 901 add_order_symbol(char *sym) 902 { 903 collundef_t *c; 904 if ((c = get_collundef(sym)) == NULL) { 905 INTERR; 906 return; 907 } 908 add_order_pri(c->ref[curr_weight]); 909 } 910 911 void 912 add_order_ellipsis(void) 913 { 914 /* special NULL value indicates self reference */ 915 add_order_pri(0); 916 } 917 918 void 919 add_order_subst(void) 920 { 921 subst_t srch; 922 subst_t *s; 923 int i; 924 925 (void) memset(&srch, 0, sizeof (srch)); 926 for (i = 0; i < curr_subst; i++) { 927 srch.ref[i] = subst_weights[i]; 928 subst_weights[i] = 0; 929 } 930 s = RB_FIND(substs_ref, &substs_ref[curr_weight], &srch); 931 932 if (s == NULL) { 933 if ((s = calloc(sizeof (*s), 1)) == NULL) { 934 fprintf(stderr,"out of memory"); 935 return; 936 } 937 s->key = new_pri(); 938 939 /* 940 * We use a self reference for our key, but we set a 941 * high bit to indicate that this is a substitution 942 * reference. This will expedite table lookups later, 943 * and prevent table lookups for situations that don't 944 * require it. (In short, its a big win, because we 945 * can skip a lot of binary searching.) 946 */ 947 set_pri(s->key, 948 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY), 949 RESOLVED); 950 nextsubst[curr_weight] += 1; 951 952 for (i = 0; i < curr_subst; i++) { 953 s->ref[i] = srch.ref[i]; 954 } 955 956 RB_INSERT(substs_ref, &substs_ref[curr_weight], s); 957 958 if (RB_FIND(substs, &substs[curr_weight], s) != NULL) { 959 INTERR; 960 return; 961 } 962 RB_INSERT(substs, &substs[curr_weight], s); 963 } 964 curr_subst = 0; 965 966 967 /* 968 * We are using the current (unique) priority as a search key 969 * in the substitution table. 970 */ 971 add_order_pri(s->key); 972 } 973 974 static void 975 add_subst_pri(int32_t ref) 976 { 977 if (curr_subst >= COLLATE_STR_LEN) { 978 fprintf(stderr,"substitution string is too long"); 979 return; 980 } 981 subst_weights[curr_subst] = ref; 982 curr_subst++; 983 } 984 985 void 986 add_subst_char(wchar_t wc) 987 { 988 collchar_t *cc; 989 990 991 if (((cc = get_collchar(wc, 1)) == NULL) || 992 (cc->wc != wc)) { 993 INTERR; 994 return; 995 } 996 /* we take the weight for the character at that position */ 997 add_subst_pri(cc->ref[curr_weight]); 998 } 999 1000 void 1001 add_subst_collelem(collelem_t *e) 1002 { 1003 add_subst_pri(e->ref[curr_weight]); 1004 } 1005 1006 void 1007 add_subst_collsym(collsym_t *s) 1008 { 1009 add_subst_pri(s->ref); 1010 } 1011 1012 void 1013 add_subst_symbol(char *ptr) 1014 { 1015 collundef_t *cu; 1016 1017 if ((cu = get_collundef(ptr)) != NULL) { 1018 add_subst_pri(cu->ref[curr_weight]); 1019 } 1020 } 1021 1022 void 1023 add_weight(int32_t ref, int pass) 1024 { 1025 weight_t srch; 1026 weight_t *w; 1027 1028 srch.pri = resolve_pri(ref); 1029 1030 /* No translation of ignores */ 1031 if (srch.pri == 0) 1032 return; 1033 1034 /* Substitution priorities are not weights */ 1035 if (srch.pri & COLLATE_SUBST_PRIORITY) 1036 return; 1037 1038 if (RB_FIND(weights, &weights[pass], &srch) != NULL) 1039 return; 1040 1041 if ((w = calloc(sizeof (*w), 1)) == NULL) { 1042 fprintf(stderr, "out of memory"); 1043 return; 1044 } 1045 w->pri = srch.pri; 1046 RB_INSERT(weights, &weights[pass], w); 1047 } 1048 1049 void 1050 add_weights(int32_t *refs) 1051 { 1052 int i; 1053 for (i = 0; i < NUM_WT; i++) { 1054 add_weight(refs[i], i); 1055 } 1056 } 1057 1058 int32_t 1059 get_weight(int32_t ref, int pass) 1060 { 1061 weight_t srch; 1062 weight_t *w; 1063 int32_t pri; 1064 1065 pri = resolve_pri(ref); 1066 if (pri & COLLATE_SUBST_PRIORITY) { 1067 return (pri); 1068 } 1069 if (pri <= 0) { 1070 return (pri); 1071 } 1072 srch.pri = pri; 1073 if ((w = RB_FIND(weights, &weights[pass], &srch)) == NULL) { 1074 INTERR; 1075 return (-1); 1076 } 1077 return (w->opt); 1078 } 1079 1080 wchar_t * 1081 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n) 1082 { 1083 wchar_t *os1 = s1; 1084 1085 n++; 1086 while (--n > 0 && (*s1++ = *s2++) != 0) 1087 continue; 1088 if (n > 0) 1089 while (--n > 0) 1090 *s1++ = 0; 1091 return (os1); 1092 } 1093 1094 #define RB_COUNT(x, name, head, cnt) do { \ 1095 (cnt) = 0; \ 1096 RB_FOREACH(x, name, (head)) { \ 1097 (cnt)++; \ 1098 } \ 1099 } while (0) 1100 1101 #define RB_NUMNODES(type, name, head, cnt) do { \ 1102 type *t; \ 1103 cnt = 0; \ 1104 RB_FOREACH(t, name, head) { \ 1105 cnt++; \ 1106 } \ 1107 } while (0) 1108 1109 void 1110 dump_collate(void) 1111 { 1112 FILE *f; 1113 int i, j, n; 1114 size_t sz; 1115 int32_t pri; 1116 collelem_t *ce; 1117 collchar_t *cc; 1118 subst_t *sb; 1119 char vers[COLLATE_STR_LEN]; 1120 collate_char_t chars[UCHAR_MAX + 1]; 1121 collate_large_t *large; 1122 collate_subst_t *subst[COLL_WEIGHTS_MAX]; 1123 collate_chain_t *chain; 1124 1125 /* 1126 * We have to run throught a preliminary pass to identify all the 1127 * weights that we use for each sorting level. 1128 */ 1129 for (i = 0; i < NUM_WT; i++) { 1130 add_weight(pri_ignore, i); 1131 } 1132 for (i = 0; i < NUM_WT; i++) { 1133 RB_FOREACH(sb, substs, &substs[i]) { 1134 for (j = 0; sb->ref[j]; j++) { 1135 add_weight(sb->ref[j], i); 1136 } 1137 } 1138 } 1139 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) { 1140 add_weights(ce->ref); 1141 } 1142 RB_FOREACH(cc, collchars, &collchars) { 1143 add_weights(cc->ref); 1144 } 1145 1146 /* 1147 * Now we walk the entire set of weights, removing the gaps 1148 * in the weights. This gives us optimum usage. The walk 1149 * occurs in priority. 1150 */ 1151 for (i = 0; i < NUM_WT; i++) { 1152 weight_t *w; 1153 RB_FOREACH(w, weights, &weights[i]) { 1154 w->opt = nweight[i]; 1155 nweight[i] += 1; 1156 } 1157 } 1158 1159 (void) memset(&chars, 0, sizeof (chars)); 1160 (void) memset(vers, 0, COLLATE_STR_LEN); 1161 (void) strlcpy(vers, COLLATE_VERSION, sizeof (vers)); 1162 1163 /* 1164 * We need to make sure we arrange for the UNDEFINED field 1165 * to show up. Also, set the total weight counts. 1166 */ 1167 for (i = 0; i < NUM_WT; i++) { 1168 if (resolve_pri(pri_undefined[i]) == -1) { 1169 set_pri(pri_undefined[i], -1, RESOLVED); 1170 /* they collate at the end of everything else */ 1171 collinfo.undef_pri[i] = COLLATE_MAX_PRIORITY; 1172 } 1173 collinfo.pri_count[i] = nweight[i]; 1174 } 1175 1176 collinfo.pri_count[NUM_WT] = max_wide(); 1177 collinfo.undef_pri[NUM_WT] = COLLATE_MAX_PRIORITY; 1178 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED; 1179 1180 /* 1181 * Ordinary character priorities 1182 */ 1183 for (i = 0; i <= UCHAR_MAX; i++) { 1184 if ((cc = get_collchar(i, 0)) != NULL) { 1185 for (j = 0; j < NUM_WT; j++) { 1186 chars[i].pri[j] = get_weight(cc->ref[j], j); 1187 } 1188 } else { 1189 for (j = 0; j < NUM_WT; j++) { 1190 chars[i].pri[j] = 1191 get_weight(pri_undefined[j], j); 1192 } 1193 /* 1194 * Per POSIX, for undefined characters, we 1195 * also have to add a last item, which is the 1196 * character code. 1197 */ 1198 chars[i].pri[NUM_WT] = i; 1199 } 1200 } 1201 1202 /* 1203 * Substitution tables 1204 */ 1205 for (i = 0; i < NUM_WT; i++) { 1206 collate_subst_t *st = NULL; 1207 subst_t *temp; 1208 RB_COUNT(temp, substs, &substs[i], n); 1209 collinfo.subst_count[i] = n; 1210 if ((st = calloc(sizeof (collate_subst_t) * n, 1)) == NULL) { 1211 fprintf(stderr, "out of memory"); 1212 return; 1213 } 1214 n = 0; 1215 RB_FOREACH(sb, substs, &substs[i]) { 1216 if ((st[n].key = resolve_pri(sb->key)) < 0) { 1217 /* by definition these resolve! */ 1218 INTERR; 1219 } 1220 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) { 1221 INTERR; 1222 } 1223 for (j = 0; sb->ref[j]; j++) { 1224 st[n].pri[j] = get_weight(sb->ref[j], i); 1225 } 1226 n++; 1227 } 1228 if (n != collinfo.subst_count[i]) 1229 INTERR; 1230 subst[i] = st; 1231 } 1232 1233 1234 /* 1235 * Chains, i.e. collating elements 1236 */ 1237 RB_NUMNODES(collelem_t, elem_by_expand, &elem_by_expand, 1238 collinfo.chain_count); 1239 chain = calloc(sizeof (collate_chain_t), collinfo.chain_count); 1240 if (chain == NULL) { 1241 fprintf(stderr, "out of memory"); 1242 return; 1243 } 1244 n = 0; 1245 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) { 1246 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN); 1247 for (i = 0; i < NUM_WT; i++) { 1248 chain[n].pri[i] = get_weight(ce->ref[i], i); 1249 } 1250 n++; 1251 } 1252 if (n != collinfo.chain_count) 1253 INTERR; 1254 1255 /* 1256 * Large (> UCHAR_MAX) character priorities 1257 */ 1258 RB_NUMNODES(collchar_t, collchars, &collchars, n); 1259 large = calloc(n, sizeof (collate_large_t)); 1260 if (large == NULL) { 1261 fprintf(stderr, "out of memory"); 1262 return; 1263 } 1264 1265 i = 0; 1266 RB_FOREACH(cc, collchars, &collchars) { 1267 int undef = 0; 1268 /* we already gathered those */ 1269 if (cc->wc <= UCHAR_MAX) 1270 continue; 1271 for (j = 0; j < NUM_WT; j++) { 1272 if ((pri = get_weight(cc->ref[j], j)) < 0) { 1273 undef = 1; 1274 } 1275 if (undef && (pri >= 0)) { 1276 /* if undefined, then all priorities are */ 1277 INTERR; 1278 } else { 1279 large[i].pri.pri[j] = pri; 1280 } 1281 } 1282 if (!undef) { 1283 large[i].val = cc->wc; 1284 collinfo.large_count = i++; 1285 } 1286 } 1287 1288 if ((f = open_category()) == NULL) { 1289 return; 1290 } 1291 1292 /* Time to write the entire data set out */ 1293 1294 if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) || 1295 (wr_category(&collinfo, sizeof (collinfo), f) < 0) || 1296 (wr_category(&chars, sizeof (chars), f) < 0)) { 1297 return; 1298 } 1299 1300 for (i = 0; i < NUM_WT; i++) { 1301 sz = sizeof (collate_subst_t) * collinfo.subst_count[i]; 1302 if (wr_category(subst[i], sz, f) < 0) { 1303 return; 1304 } 1305 } 1306 sz = sizeof (collate_chain_t) * collinfo.chain_count; 1307 if (wr_category(chain, sz, f) < 0) { 1308 return; 1309 } 1310 sz = sizeof (collate_large_t) * collinfo.large_count; 1311 if (wr_category(large, sz, f) < 0) { 1312 return; 1313 } 1314 1315 close_category(f); 1316 } 1317