1/*- 2 * Copyright 2018 Nexenta Systems, Inc. 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_Static_assert(COLL_WEIGHTS_MAX == 10, "This code assumes a value of 10"); 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 */ 133typedef enum { 134 UNKNOWN, /* priority is totally unknown */ 135 RESOLVED, /* priority value fully resolved */ 136 REFER /* priority is a reference (index) */ 137} res_t; 138 139typedef struct weight { 140 int32_t pri; 141 int opt; 142 RB_ENTRY(weight) entry; 143} weight_t; 144 145typedef 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 */ 158struct 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 */ 168typedef 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 */ 180struct 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 */ 191typedef 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 */ 203typedef 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 210static RB_HEAD(collsyms, collsym) collsyms; 211static RB_HEAD(collundefs, collundef) collundefs; 212static RB_HEAD(elem_by_symbol, collelem) elem_by_symbol; 213static RB_HEAD(elem_by_expand, collelem) elem_by_expand; 214static RB_HEAD(collchars, collchar) collchars; 215static RB_HEAD(substs, subst) substs[COLL_WEIGHTS_MAX]; 216static RB_HEAD(substs_ref, subst) substs_ref[COLL_WEIGHTS_MAX]; 217static RB_HEAD(weights, weight) weights[COLL_WEIGHTS_MAX]; 218static 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 */ 227static int currorder = EOF; 228static int lastorder = EOF; 229static collelem_t *currelem; 230static collchar_t *currchar; 231static collundef_t *currundef; 232static wchar_t ellipsis_start = 0; 233static int32_t ellipsis_weights[COLL_WEIGHTS_MAX]; 234 235/* 236 * We keep a running tally of weights. 237 */ 238static int nextpri = 1; 239static int nextsubst[COLL_WEIGHTS_MAX] = { 0 }; 240 241/* 242 * This array collects up the weights for each level. 243 */ 244static int32_t order_weights[COLL_WEIGHTS_MAX]; 245static int curr_weight = 0; 246static int32_t subst_weights[COLLATE_STR_LEN]; 247static int curr_subst = 0; 248 249/* 250 * Some initial priority values. 251 */ 252static int32_t pri_undefined[COLL_WEIGHTS_MAX]; 253static int32_t pri_ignore; 254 255static collate_info_t collinfo; 256static int32_t subst_count[COLL_WEIGHTS_MAX]; 257static int32_t chain_count; 258static int32_t large_count; 259 260static collpri_t *prilist = NULL; 261static int numpri = 0; 262static int maxpri = 0; 263 264static void start_order(int); 265 266static int32_t 267new_pri(void) 268{ 269 int i; 270 271 if (numpri >= maxpri) { 272 maxpri = maxpri ? maxpri * 2 : 1024; 273 prilist = realloc(prilist, sizeof (collpri_t) * maxpri); 274 if (prilist == NULL) { 275 fprintf(stderr,"out of memory\n"); 276 return (-1); 277 } 278 for (i = numpri; i < maxpri; i++) { 279 prilist[i].res = UNKNOWN; 280 prilist[i].pri = 0; 281 prilist[i].pass = 0; 282 } 283 } 284 return (numpri++); 285} 286 287static collpri_t * 288get_pri(int32_t ref) 289{ 290 if ((ref < 0) || (ref > numpri)) { 291 INTERR; 292 return (NULL); 293 } 294 return (&prilist[ref]); 295} 296 297static void 298set_pri(int32_t ref, int32_t v, res_t res) 299{ 300 collpri_t *pri; 301 302 pri = get_pri(ref); 303 304 if ((res == REFER) && ((v < 0) || (v >= numpri))) { 305 INTERR; 306 } 307 308 /* Resolve self references */ 309 if ((res == REFER) && (ref == v)) { 310 v = nextpri; 311 res = RESOLVED; 312 } 313 314 if (pri->res != UNKNOWN) { 315 warn("repeated item in order list (first on %d)", 316 pri->lineno); 317 return; 318 } 319 pri->lineno = lineno; 320 pri->pri = v; 321 pri->res = res; 322} 323 324static int32_t 325resolve_pri(int32_t ref) 326{ 327 collpri_t *pri; 328 static int32_t pass = 0; 329 330 pri = get_pri(ref); 331 pass++; 332 while (pri->res == REFER) { 333 if (pri->pass == pass) { 334 /* report a line with the circular symbol */ 335 lineno = pri->lineno; 336 fprintf(stderr,"circular reference in order list\n"); 337 return (-1); 338 } 339 if ((pri->pri < 0) || (pri->pri >= numpri)) { 340 INTERR; 341 return (-1); 342 } 343 pri->pass = pass; 344 pri = &prilist[pri->pri]; 345 } 346 347 if (pri->res == UNKNOWN) { 348 return (-1); 349 } 350 if (pri->res != RESOLVED) 351 INTERR; 352 353 return (pri->pri); 354} 355 356static int 357weight_compare(const void *n1, const void *n2) 358{ 359 int32_t k1 = ((const weight_t *)n1)->pri; 360 int32_t k2 = ((const weight_t *)n2)->pri; 361 362 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 363} 364 365RB_GENERATE_STATIC(weights, weight, entry, weight_compare); 366 367static int 368collsym_compare(const void *n1, const void *n2) 369{ 370 const collsym_t *c1 = n1; 371 const collsym_t *c2 = n2; 372 int rv; 373 374 rv = strcmp(c1->name, c2->name); 375 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 376} 377 378RB_GENERATE_STATIC(collsyms, collsym, entry, collsym_compare); 379 380static int 381collundef_compare(const void *n1, const void *n2) 382{ 383 const collundef_t *c1 = n1; 384 const collundef_t *c2 = n2; 385 int rv; 386 387 rv = strcmp(c1->name, c2->name); 388 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 389} 390 391RB_GENERATE_STATIC(collundefs, collundef, entry, collundef_compare); 392 393static int 394element_compare_symbol(const void *n1, const void *n2) 395{ 396 const collelem_t *c1 = n1; 397 const collelem_t *c2 = n2; 398 int rv; 399 400 rv = strcmp(c1->symbol, c2->symbol); 401 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 402} 403 404RB_GENERATE_STATIC(elem_by_symbol, collelem, rb_bysymbol, element_compare_symbol); 405 406static int 407element_compare_expand(const void *n1, const void *n2) 408{ 409 const collelem_t *c1 = n1; 410 const collelem_t *c2 = n2; 411 int rv; 412 413 rv = wcscmp(c1->expand, c2->expand); 414 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 415} 416 417RB_GENERATE_STATIC(elem_by_expand, collelem, rb_byexpand, element_compare_expand); 418 419static int 420collchar_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 428RB_GENERATE_STATIC(collchars, collchar, entry, collchar_compare); 429 430static int 431subst_compare(const void *n1, const void *n2) 432{ 433 int32_t k1 = ((const subst_t *)n1)->key; 434 int32_t k2 = ((const subst_t *)n2)->key; 435 436 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 437} 438 439RB_GENERATE_STATIC(substs, subst, entry, subst_compare); 440 441static int 442subst_compare_ref(const void *n1, const void *n2) 443{ 444 const wchar_t *c1 = ((const subst_t *)n1)->ref; 445 const wchar_t *c2 = ((const subst_t *)n2)->ref; 446 int rv; 447 448 rv = wcscmp(c1, c2); 449 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 450} 451 452RB_GENERATE_STATIC(substs_ref, subst, entry_ref, subst_compare_ref); 453 454void 455init_collate(void) 456{ 457 int i; 458 459 RB_INIT(&collsyms); 460 461 RB_INIT(&collundefs); 462 463 RB_INIT(&elem_by_symbol); 464 465 RB_INIT(&elem_by_expand); 466 467 RB_INIT(&collchars); 468 469 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 470 RB_INIT(&substs[i]); 471 RB_INIT(&substs_ref[i]); 472 RB_INIT(&weights[i]); 473 nweight[i] = 1; 474 } 475 476 (void) memset(&collinfo, 0, sizeof (collinfo)); 477 478 /* allocate some initial priorities */ 479 pri_ignore = new_pri(); 480 481 set_pri(pri_ignore, 0, RESOLVED); 482 483 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 484 pri_undefined[i] = new_pri(); 485 486 /* we will override this later */ 487 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN); 488 } 489} 490 491void 492define_collsym(char *name) 493{ 494 collsym_t *sym; 495 496 if ((sym = calloc(1, sizeof(*sym))) == NULL) { 497 fprintf(stderr,"out of memory\n"); 498 return; 499 } 500 sym->name = name; 501 sym->ref = new_pri(); 502 503 if (RB_FIND(collsyms, &collsyms, sym) != NULL) { 504 /* 505 * This should never happen because we are only called 506 * for undefined symbols. 507 */ 508 free(sym); 509 INTERR; 510 return; 511 } 512 RB_INSERT(collsyms, &collsyms, sym); 513} 514 515collsym_t * 516lookup_collsym(char *name) 517{ 518 collsym_t srch; 519 520 srch.name = name; 521 return (RB_FIND(collsyms, &collsyms, &srch)); 522} 523 524collelem_t * 525lookup_collelem(char *symbol) 526{ 527 collelem_t srch; 528 529 srch.symbol = symbol; 530 return (RB_FIND(elem_by_symbol, &elem_by_symbol, &srch)); 531} 532 533static collundef_t * 534get_collundef(char *name) 535{ 536 collundef_t srch; 537 collundef_t *ud; 538 int i; 539 540 srch.name = name; 541 if ((ud = RB_FIND(collundefs, &collundefs, &srch)) == NULL) { 542 if (((ud = calloc(1, sizeof(*ud))) == NULL) || 543 ((ud->name = strdup(name)) == NULL)) { 544 fprintf(stderr,"out of memory\n"); 545 free(ud); 546 return (NULL); 547 } 548 for (i = 0; i < NUM_WT; i++) { 549 ud->ref[i] = new_pri(); 550 } 551 RB_INSERT(collundefs, &collundefs, ud); 552 } 553 add_charmap_undefined(name); 554 return (ud); 555} 556 557static collchar_t * 558get_collchar(wchar_t wc, int create) 559{ 560 collchar_t srch; 561 collchar_t *cc; 562 int i; 563 564 srch.wc = wc; 565 cc = RB_FIND(collchars, &collchars, &srch); 566 if ((cc == NULL) && create) { 567 if ((cc = calloc(1, sizeof(*cc))) == NULL) { 568 fprintf(stderr, "out of memory\n"); 569 return (NULL); 570 } 571 for (i = 0; i < NUM_WT; i++) { 572 cc->ref[i] = new_pri(); 573 } 574 cc->wc = wc; 575 RB_INSERT(collchars, &collchars, cc); 576 } 577 return (cc); 578} 579 580void 581end_order_collsym(collsym_t *sym) 582{ 583 start_order(T_COLLSYM); 584 /* update the weight */ 585 586 set_pri(sym->ref, nextpri, RESOLVED); 587 nextpri++; 588} 589 590void 591end_order(void) 592{ 593 int i; 594 int32_t pri; 595 int32_t ref; 596 collpri_t *p; 597 598 /* advance the priority/weight */ 599 pri = nextpri; 600 601 switch (currorder) { 602 case T_CHAR: 603 for (i = 0; i < NUM_WT; i++) { 604 if (((ref = order_weights[i]) < 0) || 605 ((p = get_pri(ref)) == NULL) || 606 (p->pri == -1)) { 607 /* unspecified weight is a self reference */ 608 set_pri(currchar->ref[i], pri, RESOLVED); 609 } else { 610 set_pri(currchar->ref[i], ref, REFER); 611 } 612 order_weights[i] = -1; 613 } 614 615 /* leave a cookie trail in case next symbol is ellipsis */ 616 ellipsis_start = currchar->wc + 1; 617 currchar = NULL; 618 break; 619 620 case T_ELLIPSIS: 621 /* save off the weights were we can find them */ 622 for (i = 0; i < NUM_WT; i++) { 623 ellipsis_weights[i] = order_weights[i]; 624 order_weights[i] = -1; 625 } 626 break; 627 628 case T_COLLELEM: 629 if (currelem == NULL) { 630 INTERR; 631 } else { 632 for (i = 0; i < NUM_WT; i++) { 633 634 if (((ref = order_weights[i]) < 0) || 635 ((p = get_pri(ref)) == NULL) || 636 (p->pri == -1)) { 637 set_pri(currelem->ref[i], pri, 638 RESOLVED); 639 } else { 640 set_pri(currelem->ref[i], ref, REFER); 641 } 642 order_weights[i] = -1; 643 } 644 } 645 break; 646 647 case T_UNDEFINED: 648 for (i = 0; i < NUM_WT; i++) { 649 if (((ref = order_weights[i]) < 0) || 650 ((p = get_pri(ref)) == NULL) || 651 (p->pri == -1)) { 652 set_pri(pri_undefined[i], -1, RESOLVED); 653 } else { 654 set_pri(pri_undefined[i], ref, REFER); 655 } 656 order_weights[i] = -1; 657 } 658 break; 659 660 case T_SYMBOL: 661 for (i = 0; i < NUM_WT; i++) { 662 if (((ref = order_weights[i]) < 0) || 663 ((p = get_pri(ref)) == NULL) || 664 (p->pri == -1)) { 665 set_pri(currundef->ref[i], pri, RESOLVED); 666 } else { 667 set_pri(currundef->ref[i], ref, REFER); 668 } 669 order_weights[i] = -1; 670 } 671 break; 672 673 default: 674 INTERR; 675 } 676 677 nextpri++; 678} 679 680static void 681start_order(int type) 682{ 683 int i; 684 685 lastorder = currorder; 686 currorder = type; 687 688 /* this is used to protect ELLIPSIS processing */ 689 if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) { 690 fprintf(stderr, "character value expected\n"); 691 } 692 693 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 694 order_weights[i] = -1; 695 } 696 curr_weight = 0; 697} 698 699void 700start_order_undefined(void) 701{ 702 start_order(T_UNDEFINED); 703} 704 705void 706start_order_symbol(char *name) 707{ 708 currundef = get_collundef(name); 709 start_order(T_SYMBOL); 710} 711 712void 713start_order_char(wchar_t wc) 714{ 715 collchar_t *cc; 716 int32_t ref; 717 718 start_order(T_CHAR); 719 720 /* 721 * If we last saw an ellipsis, then we need to close the range. 722 * Handle that here. Note that we have to be careful because the 723 * items *inside* the range are treated exclusiveley to the items 724 * outside of the range. The ends of the range can have quite 725 * different weights than the range members. 726 */ 727 if (lastorder == T_ELLIPSIS) { 728 int i; 729 730 if (wc < ellipsis_start) { 731 fprintf(stderr, "malformed range!\n"); 732 return; 733 } 734 while (ellipsis_start < wc) { 735 /* 736 * pick all of the saved weights for the 737 * ellipsis. note that -1 encodes for the 738 * ellipsis itself, which means to take the 739 * current relative priority. 740 */ 741 if ((cc = get_collchar(ellipsis_start, 1)) == NULL) { 742 INTERR; 743 return; 744 } 745 for (i = 0; i < NUM_WT; i++) { 746 collpri_t *p; 747 if (((ref = ellipsis_weights[i]) == -1) || 748 ((p = get_pri(ref)) == NULL) || 749 (p->pri == -1)) { 750 set_pri(cc->ref[i], nextpri, RESOLVED); 751 } else { 752 set_pri(cc->ref[i], ref, REFER); 753 } 754 ellipsis_weights[i] = 0; 755 } 756 ellipsis_start++; 757 nextpri++; 758 } 759 } 760 761 currchar = get_collchar(wc, 1); 762} 763 764void 765start_order_collelem(collelem_t *e) 766{ 767 start_order(T_COLLELEM); 768 currelem = e; 769} 770 771void 772start_order_ellipsis(void) 773{ 774 int i; 775 776 start_order(T_ELLIPSIS); 777 778 if (lastorder != T_CHAR) { 779 fprintf(stderr, "illegal starting point for range\n"); 780 return; 781 } 782 783 for (i = 0; i < NUM_WT; i++) { 784 ellipsis_weights[i] = order_weights[i]; 785 } 786} 787 788void 789define_collelem(char *name, wchar_t *wcs) 790{ 791 collelem_t *e; 792 int i; 793 794 if (wcslen(wcs) >= COLLATE_STR_LEN) { 795 fprintf(stderr,"expanded collation element too long\n"); 796 return; 797 } 798 799 if ((e = calloc(1, sizeof(*e))) == NULL) { 800 fprintf(stderr, "out of memory\n"); 801 return; 802 } 803 e->expand = wcs; 804 e->symbol = name; 805 806 /* 807 * This is executed before the order statement, so we don't 808 * know how many priorities we *really* need. We allocate one 809 * for each possible weight. Not a big deal, as collating-elements 810 * prove to be quite rare. 811 */ 812 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 813 e->ref[i] = new_pri(); 814 } 815 816 /* A character sequence can only reduce to one element. */ 817 if ((RB_FIND(elem_by_symbol, &elem_by_symbol, e) != NULL) || 818 (RB_FIND(elem_by_expand, &elem_by_expand, e) != NULL)) { 819 fprintf(stderr, "duplicate collating element definition\n"); 820 free(e); 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 827void 828add_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 849void 850add_order_directive(void) 851{ 852 if (collinfo.directive_count >= COLL_WEIGHTS_MAX) { 853 fprintf(stderr, "too many directives (max %d)\n", COLL_WEIGHTS_MAX); 854 return; 855 } 856 collinfo.directive_count++; 857} 858 859static void 860add_order_pri(int32_t ref) 861{ 862 if (curr_weight >= NUM_WT) { 863 fprintf(stderr, "too many weights (max %d)\n", NUM_WT); 864 return; 865 } 866 order_weights[curr_weight] = ref; 867 curr_weight++; 868} 869 870void 871add_order_collsym(collsym_t *s) 872{ 873 add_order_pri(s->ref); 874} 875 876void 877add_order_char(wchar_t wc) 878{ 879 collchar_t *cc; 880 881 if ((cc = get_collchar(wc, 1)) == NULL) { 882 INTERR; 883 return; 884 } 885 886 add_order_pri(cc->ref[curr_weight]); 887} 888 889void 890add_order_collelem(collelem_t *e) 891{ 892 add_order_pri(e->ref[curr_weight]); 893} 894 895void 896add_order_ignore(void) 897{ 898 add_order_pri(pri_ignore); 899} 900 901void 902add_order_symbol(char *sym) 903{ 904 collundef_t *c; 905 if ((c = get_collundef(sym)) == NULL) { 906 INTERR; 907 return; 908 } 909 add_order_pri(c->ref[curr_weight]); 910} 911 912void 913add_order_ellipsis(void) 914{ 915 /* special NULL value indicates self reference */ 916 add_order_pri(0); 917} 918 919void 920add_order_subst(void) 921{ 922 subst_t srch; 923 subst_t *s; 924 int i; 925 926 (void) memset(&srch, 0, sizeof (srch)); 927 for (i = 0; i < curr_subst; i++) { 928 srch.ref[i] = subst_weights[i]; 929 subst_weights[i] = 0; 930 } 931 s = RB_FIND(substs_ref, &substs_ref[curr_weight], &srch); 932 933 if (s == NULL) { 934 if ((s = calloc(1, sizeof(*s))) == NULL) { 935 fprintf(stderr,"out of memory\n"); 936 return; 937 } 938 s->key = new_pri(); 939 940 /* 941 * We use a self reference for our key, but we set a 942 * high bit to indicate that this is a substitution 943 * reference. This will expedite table lookups later, 944 * and prevent table lookups for situations that don't 945 * require it. (In short, its a big win, because we 946 * can skip a lot of binary searching.) 947 */ 948 set_pri(s->key, 949 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY), 950 RESOLVED); 951 nextsubst[curr_weight] += 1; 952 953 for (i = 0; i < curr_subst; i++) { 954 s->ref[i] = srch.ref[i]; 955 } 956 957 RB_INSERT(substs_ref, &substs_ref[curr_weight], s); 958 959 if (RB_FIND(substs, &substs[curr_weight], s) != NULL) { 960 INTERR; 961 return; 962 } 963 RB_INSERT(substs, &substs[curr_weight], s); 964 } 965 curr_subst = 0; 966 967 968 /* 969 * We are using the current (unique) priority as a search key 970 * in the substitution table. 971 */ 972 add_order_pri(s->key); 973} 974 975static void 976add_subst_pri(int32_t ref) 977{ 978 if (curr_subst >= COLLATE_STR_LEN) { 979 fprintf(stderr,"substitution string is too long\n"); 980 return; 981 } 982 subst_weights[curr_subst] = ref; 983 curr_subst++; 984} 985 986void 987add_subst_char(wchar_t wc) 988{ 989 collchar_t *cc; 990 991 992 if (((cc = get_collchar(wc, 1)) == NULL) || 993 (cc->wc != wc)) { 994 INTERR; 995 return; 996 } 997 /* we take the weight for the character at that position */ 998 add_subst_pri(cc->ref[curr_weight]); 999} 1000 1001void 1002add_subst_collelem(collelem_t *e) 1003{ 1004 add_subst_pri(e->ref[curr_weight]); 1005} 1006 1007void 1008add_subst_collsym(collsym_t *s) 1009{ 1010 add_subst_pri(s->ref); 1011} 1012 1013void 1014add_subst_symbol(char *ptr) 1015{ 1016 collundef_t *cu; 1017 1018 if ((cu = get_collundef(ptr)) != NULL) { 1019 add_subst_pri(cu->ref[curr_weight]); 1020 } 1021} 1022 1023void 1024add_weight(int32_t ref, int pass) 1025{ 1026 weight_t srch; 1027 weight_t *w; 1028 1029 srch.pri = resolve_pri(ref); 1030 1031 /* No translation of ignores */ 1032 if (srch.pri == 0) 1033 return; 1034 1035 /* Substitution priorities are not weights */ 1036 if (srch.pri & COLLATE_SUBST_PRIORITY) 1037 return; 1038 1039 if (RB_FIND(weights, &weights[pass], &srch) != NULL) 1040 return; 1041 1042 if ((w = calloc(1, sizeof(*w))) == NULL) { 1043 fprintf(stderr, "out of memory\n"); 1044 return; 1045 } 1046 w->pri = srch.pri; 1047 RB_INSERT(weights, &weights[pass], w); 1048} 1049 1050void 1051add_weights(int32_t *refs) 1052{ 1053 int i; 1054 for (i = 0; i < NUM_WT; i++) { 1055 add_weight(refs[i], i); 1056 } 1057} 1058 1059int32_t 1060get_weight(int32_t ref, int pass) 1061{ 1062 weight_t srch; 1063 weight_t *w; 1064 int32_t pri; 1065 1066 pri = resolve_pri(ref); 1067 if (pri & COLLATE_SUBST_PRIORITY) { 1068 return (pri); 1069 } 1070 if (pri <= 0) { 1071 return (pri); 1072 } 1073 srch.pri = pri; 1074 if ((w = RB_FIND(weights, &weights[pass], &srch)) == NULL) { 1075 INTERR; 1076 return (-1); 1077 } 1078 return (w->opt); 1079} 1080 1081wchar_t * 1082wsncpy(wchar_t *s1, const wchar_t *s2, size_t n) 1083{ 1084 wchar_t *os1 = s1; 1085 1086 n++; 1087 while (--n > 0 && (*s1++ = htote(*s2++)) != 0) 1088 continue; 1089 if (n > 0) 1090 while (--n > 0) 1091 *s1++ = 0; 1092 return (os1); 1093} 1094 1095#define RB_COUNT(x, name, head, cnt) do { \ 1096 (cnt) = 0; \ 1097 RB_FOREACH(x, name, (head)) { \ 1098 (cnt)++; \ 1099 } \ 1100} while (0) 1101 1102#define RB_NUMNODES(type, name, head, cnt) do { \ 1103 type *t; \ 1104 cnt = 0; \ 1105 RB_FOREACH(t, name, head) { \ 1106 cnt++; \ 1107 } \ 1108} while (0) 1109 1110void 1111dump_collate(void) 1112{ 1113 FILE *f; 1114 int i, j, n; 1115 size_t sz; 1116 int32_t pri; 1117 collelem_t *ce; 1118 collchar_t *cc; 1119 subst_t *sb; 1120 char fmt_version[COLLATE_FMT_VERSION_LEN]; 1121 char def_version[XLOCALE_DEF_VERSION_LEN]; 1122 collate_char_t chars[UCHAR_MAX + 1]; 1123 collate_large_t *large; 1124 collate_subst_t *subst[COLL_WEIGHTS_MAX]; 1125 collate_chain_t *chain; 1126 1127 /* 1128 * We have to run through a preliminary pass to identify all the 1129 * weights that we use for each sorting level. 1130 */ 1131 for (i = 0; i < NUM_WT; i++) { 1132 add_weight(pri_ignore, i); 1133 } 1134 for (i = 0; i < NUM_WT; i++) { 1135 RB_FOREACH(sb, substs, &substs[i]) { 1136 for (j = 0; sb->ref[j]; j++) { 1137 add_weight(sb->ref[j], i); 1138 } 1139 } 1140 } 1141 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) { 1142 add_weights(ce->ref); 1143 } 1144 RB_FOREACH(cc, collchars, &collchars) { 1145 add_weights(cc->ref); 1146 } 1147 1148 /* 1149 * Now we walk the entire set of weights, removing the gaps 1150 * in the weights. This gives us optimum usage. The walk 1151 * occurs in priority. 1152 */ 1153 for (i = 0; i < NUM_WT; i++) { 1154 weight_t *w; 1155 RB_FOREACH(w, weights, &weights[i]) { 1156 w->opt = nweight[i]; 1157 nweight[i] += 1; 1158 } 1159 } 1160 1161 (void) memset(&chars, 0, sizeof (chars)); 1162 (void) memset(fmt_version, 0, COLLATE_FMT_VERSION_LEN); 1163 (void) strlcpy(fmt_version, COLLATE_FMT_VERSION, sizeof (fmt_version)); 1164 (void) memset(def_version, 0, XLOCALE_DEF_VERSION_LEN); 1165 if (version) 1166 (void) strlcpy(def_version, version, sizeof (def_version)); 1167 1168 /* 1169 * We need to make sure we arrange for the UNDEFINED field 1170 * to show up. Also, set the total weight counts. 1171 */ 1172 for (i = 0; i < NUM_WT; i++) { 1173 if (resolve_pri(pri_undefined[i]) == -1) { 1174 set_pri(pri_undefined[i], -1, RESOLVED); 1175 /* they collate at the end of everything else */ 1176 collinfo.undef_pri[i] = htote(COLLATE_MAX_PRIORITY); 1177 } 1178 collinfo.pri_count[i] = htote(nweight[i]); 1179 } 1180 1181 collinfo.pri_count[NUM_WT] = htote(max_wide()); 1182 collinfo.undef_pri[NUM_WT] = htote(COLLATE_MAX_PRIORITY); 1183 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED; 1184 1185 /* 1186 * Ordinary character priorities 1187 */ 1188 for (i = 0; i <= UCHAR_MAX; i++) { 1189 if ((cc = get_collchar(i, 0)) != NULL) { 1190 for (j = 0; j < NUM_WT; j++) { 1191 chars[i].pri[j] = 1192 htote(get_weight(cc->ref[j], j)); 1193 } 1194 } else { 1195 for (j = 0; j < NUM_WT; j++) { 1196 chars[i].pri[j] = 1197 htote(get_weight(pri_undefined[j], j)); 1198 } 1199 /* 1200 * Per POSIX, for undefined characters, we 1201 * also have to add a last item, which is the 1202 * character code. 1203 */ 1204 chars[i].pri[NUM_WT] = htote(i); 1205 } 1206 } 1207 1208 /* 1209 * Substitution tables 1210 */ 1211 for (i = 0; i < NUM_WT; i++) { 1212 collate_subst_t *st = NULL; 1213 subst_t *temp; 1214 RB_COUNT(temp, substs, &substs[i], n); 1215 subst_count[i] = n; 1216 if ((st = calloc(n, sizeof(collate_subst_t))) == NULL) { 1217 fprintf(stderr, "out of memory\n"); 1218 return; 1219 } 1220 n = 0; 1221 RB_FOREACH(sb, substs, &substs[i]) { 1222 if ((st[n].key = resolve_pri(sb->key)) < 0) { 1223 /* by definition these resolve! */ 1224 INTERR; 1225 } 1226 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) { 1227 INTERR; 1228 } 1229 st[n].key = htote(st[n].key); 1230 for (j = 0; sb->ref[j]; j++) { 1231 st[n].pri[j] = htote(get_weight(sb->ref[j], 1232 i)); 1233 } 1234 n++; 1235 } 1236 if (n != subst_count[i]) 1237 INTERR; 1238 subst[i] = st; 1239 } 1240 1241 1242 /* 1243 * Chains, i.e. collating elements 1244 */ 1245 RB_NUMNODES(collelem_t, elem_by_expand, &elem_by_expand, chain_count); 1246 chain = calloc(chain_count, sizeof(collate_chain_t)); 1247 if (chain == NULL) { 1248 fprintf(stderr, "out of memory\n"); 1249 return; 1250 } 1251 n = 0; 1252 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) { 1253 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN); 1254 for (i = 0; i < NUM_WT; i++) { 1255 chain[n].pri[i] = htote(get_weight(ce->ref[i], i)); 1256 } 1257 n++; 1258 } 1259 if (n != chain_count) 1260 INTERR; 1261 1262 /* 1263 * Large (> UCHAR_MAX) character priorities 1264 */ 1265 RB_NUMNODES(collchar_t, collchars, &collchars, n); 1266 large = calloc(n, sizeof(collate_large_t)); 1267 if (large == NULL) { 1268 fprintf(stderr, "out of memory\n"); 1269 return; 1270 } 1271 1272 i = 0; 1273 RB_FOREACH(cc, collchars, &collchars) { 1274 int undef = 0; 1275 /* we already gathered those */ 1276 if (cc->wc <= UCHAR_MAX) 1277 continue; 1278 for (j = 0; j < NUM_WT; j++) { 1279 if ((pri = get_weight(cc->ref[j], j)) < 0) { 1280 undef = 1; 1281 } 1282 if (undef && (pri >= 0)) { 1283 /* if undefined, then all priorities are */ 1284 INTERR; 1285 } else { 1286 large[i].pri.pri[j] = htote(pri); 1287 } 1288 } 1289 if (!undef) { 1290 large[i].val = htote(cc->wc); 1291 large_count = i++; 1292 } 1293 } 1294 1295 if ((f = open_category()) == NULL) { 1296 return; 1297 } 1298 1299 /* Time to write the entire data set out */ 1300 1301 for (i = 0; i < NUM_WT; i++) 1302 collinfo.subst_count[i] = htote(subst_count[i]); 1303 collinfo.chain_count = htote(chain_count); 1304 collinfo.large_count = htote(large_count); 1305 1306 if ((wr_category(fmt_version, COLLATE_FMT_VERSION_LEN, f) < 0) || 1307 (wr_category(def_version, XLOCALE_DEF_VERSION_LEN, f) < 0) || 1308 (wr_category(&collinfo, sizeof (collinfo), f) < 0) || 1309 (wr_category(&chars, sizeof (chars), f) < 0)) { 1310 return; 1311 } 1312 1313 for (i = 0; i < NUM_WT; i++) { 1314 sz = sizeof (collate_subst_t) * subst_count[i]; 1315 if (wr_category(subst[i], sz, f) < 0) { 1316 return; 1317 } 1318 } 1319 sz = sizeof (collate_chain_t) * chain_count; 1320 if (wr_category(chain, sz, f) < 0) { 1321 return; 1322 } 1323 sz = sizeof (collate_large_t) * large_count; 1324 if (wr_category(large, sz, f) < 0) { 1325 return; 1326 } 1327 1328 close_category(f); 1329} 1330