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