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/avl.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 AVL 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 avl_node_t avl; 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 avl_node_t avl; 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 avl_node_t avl; 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 avl_node_t avl_bysymbol; 185 avl_node_t avl_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 avl_node_t avl; 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 { 204 int32_t key; 205 int32_t ref[COLLATE_STR_LEN]; 206 avl_node_t avl; 207 avl_node_t avl_ref; 208 } subst_t; 209 210 static avl_tree_t collsyms; 211 static avl_tree_t collundefs; 212 static avl_tree_t elem_by_symbol; 213 static avl_tree_t elem_by_expand; 214 static avl_tree_t collchars; 215 static avl_tree_t substs[COLL_WEIGHTS_MAX]; 216 static avl_tree_t substs_ref[COLL_WEIGHTS_MAX]; 217 static avl_tree_t 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 static int 363 collsym_compare(const void *n1, const void *n2) 364 { 365 const collsym_t *c1 = n1; 366 const collsym_t *c2 = n2; 367 int rv; 368 369 rv = strcmp(c1->name, c2->name); 370 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 371 } 372 373 static int 374 collundef_compare(const void *n1, const void *n2) 375 { 376 const collundef_t *c1 = n1; 377 const collundef_t *c2 = n2; 378 int rv; 379 380 rv = strcmp(c1->name, c2->name); 381 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 382 } 383 384 static int 385 element_compare_symbol(const void *n1, const void *n2) 386 { 387 const collelem_t *c1 = n1; 388 const collelem_t *c2 = n2; 389 int rv; 390 391 rv = strcmp(c1->symbol, c2->symbol); 392 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 393 } 394 395 static int 396 element_compare_expand(const void *n1, const void *n2) 397 { 398 const collelem_t *c1 = n1; 399 const collelem_t *c2 = n2; 400 int rv; 401 402 rv = wcscmp(c1->expand, c2->expand); 403 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 404 } 405 406 static int 407 collchar_compare(const void *n1, const void *n2) 408 { 409 wchar_t k1 = ((const collchar_t *)n1)->wc; 410 wchar_t k2 = ((const collchar_t *)n2)->wc; 411 412 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 413 } 414 415 static int 416 subst_compare(const void *n1, const void *n2) 417 { 418 int32_t k1 = ((const subst_t *)n1)->key; 419 int32_t k2 = ((const subst_t *)n2)->key; 420 421 return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0); 422 } 423 424 #pragma GCC diagnostic push 425 #pragma GCC diagnostic ignored "-Wcast-qual" 426 427 static int 428 subst_compare_ref(const void *n1, const void *n2) 429 { 430 int32_t *c1 = ((subst_t *)n1)->ref; 431 int32_t *c2 = ((subst_t *)n2)->ref; 432 int rv; 433 434 rv = wcscmp((wchar_t *)c1, (wchar_t *)c2); 435 return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0); 436 } 437 438 #pragma GCC diagnostic pop 439 440 void 441 init_collate(void) 442 { 443 int i; 444 445 avl_create(&collsyms, collsym_compare, sizeof (collsym_t), 446 offsetof(collsym_t, avl)); 447 448 avl_create(&collundefs, collundef_compare, sizeof (collsym_t), 449 offsetof(collundef_t, avl)); 450 451 avl_create(&elem_by_symbol, element_compare_symbol, sizeof (collelem_t), 452 offsetof(collelem_t, avl_bysymbol)); 453 avl_create(&elem_by_expand, element_compare_expand, sizeof (collelem_t), 454 offsetof(collelem_t, avl_byexpand)); 455 456 avl_create(&collchars, collchar_compare, sizeof (collchar_t), 457 offsetof(collchar_t, avl)); 458 459 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 460 avl_create(&substs[i], subst_compare, sizeof (subst_t), 461 offsetof(subst_t, avl)); 462 avl_create(&substs_ref[i], subst_compare_ref, 463 sizeof (subst_t), offsetof(subst_t, avl_ref)); 464 avl_create(&weights[i], weight_compare, sizeof (weight_t), 465 offsetof(weight_t, avl)); 466 nweight[i] = 1; 467 } 468 469 (void) memset(&collinfo, 0, sizeof (collinfo)); 470 471 /* allocate some initial priorities */ 472 pri_ignore = new_pri(); 473 474 set_pri(pri_ignore, 0, RESOLVED); 475 476 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 477 pri_undefined[i] = new_pri(); 478 479 /* we will override this later */ 480 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN); 481 } 482 } 483 484 void 485 define_collsym(char *name) 486 { 487 collsym_t *sym; 488 avl_index_t where; 489 490 if ((sym = calloc(sizeof (*sym), 1)) == NULL) { 491 fprintf(stderr,"out of memory"); 492 return; 493 } 494 sym->name = name; 495 sym->ref = new_pri(); 496 497 if (avl_find(&collsyms, sym, &where) != NULL) { 498 /* 499 * This should never happen because we are only called 500 * for undefined symbols. 501 */ 502 INTERR; 503 return; 504 } 505 avl_insert(&collsyms, sym, where); 506 } 507 508 collsym_t * 509 lookup_collsym(char *name) 510 { 511 collsym_t srch; 512 513 srch.name = name; 514 return (avl_find(&collsyms, &srch, NULL)); 515 } 516 517 collelem_t * 518 lookup_collelem(char *symbol) 519 { 520 collelem_t srch; 521 522 srch.symbol = symbol; 523 return (avl_find(&elem_by_symbol, &srch, NULL)); 524 } 525 526 static collundef_t * 527 get_collundef(char *name) 528 { 529 collundef_t srch; 530 collundef_t *ud; 531 avl_index_t where; 532 int i; 533 534 srch.name = name; 535 if ((ud = avl_find(&collundefs, &srch, &where)) == NULL) { 536 if (((ud = calloc(sizeof (*ud), 1)) == NULL) || 537 ((ud->name = strdup(name)) == NULL)) { 538 fprintf(stderr,"out of memory"); 539 return (NULL); 540 } 541 for (i = 0; i < NUM_WT; i++) { 542 ud->ref[i] = new_pri(); 543 } 544 avl_insert(&collundefs, ud, where); 545 } 546 add_charmap_undefined(name); 547 return (ud); 548 } 549 550 static collchar_t * 551 get_collchar(wchar_t wc, int create) 552 { 553 collchar_t srch; 554 collchar_t *cc; 555 avl_index_t where; 556 int i; 557 558 srch.wc = wc; 559 cc = avl_find(&collchars, &srch, &where); 560 if ((cc == NULL) && create) { 561 if ((cc = calloc(sizeof (*cc), 1)) == NULL) { 562 fprintf(stderr, "out of memory"); 563 return (NULL); 564 } 565 for (i = 0; i < NUM_WT; i++) { 566 cc->ref[i] = new_pri(); 567 } 568 cc->wc = wc; 569 avl_insert(&collchars, cc, where); 570 } 571 return (cc); 572 } 573 574 void 575 end_order_collsym(collsym_t *sym) 576 { 577 start_order(T_COLLSYM); 578 /* update the weight */ 579 580 set_pri(sym->ref, nextpri, RESOLVED); 581 nextpri++; 582 } 583 584 void 585 end_order(void) 586 { 587 int i; 588 int32_t pri; 589 int32_t ref; 590 collpri_t *p; 591 592 /* advance the priority/weight */ 593 pri = nextpri; 594 595 switch (currorder) { 596 case T_CHAR: 597 for (i = 0; i < NUM_WT; i++) { 598 if (((ref = order_weights[i]) < 0) || 599 ((p = get_pri(ref)) == NULL) || 600 (p->pri == -1)) { 601 /* unspecified weight is a self reference */ 602 set_pri(currchar->ref[i], pri, RESOLVED); 603 } else { 604 set_pri(currchar->ref[i], ref, REFER); 605 } 606 order_weights[i] = -1; 607 } 608 609 /* leave a cookie trail in case next symbol is ellipsis */ 610 ellipsis_start = currchar->wc + 1; 611 currchar = NULL; 612 break; 613 614 case T_ELLIPSIS: 615 /* save off the weights were we can find them */ 616 for (i = 0; i < NUM_WT; i++) { 617 ellipsis_weights[i] = order_weights[i]; 618 order_weights[i] = -1; 619 } 620 break; 621 622 case T_COLLELEM: 623 if (currelem == NULL) { 624 INTERR; 625 } else { 626 for (i = 0; i < NUM_WT; i++) { 627 628 if (((ref = order_weights[i]) < 0) || 629 ((p = get_pri(ref)) == NULL) || 630 (p->pri == -1)) { 631 set_pri(currelem->ref[i], pri, 632 RESOLVED); 633 } else { 634 set_pri(currelem->ref[i], ref, REFER); 635 } 636 order_weights[i] = -1; 637 } 638 } 639 break; 640 641 case T_UNDEFINED: 642 for (i = 0; i < NUM_WT; i++) { 643 if (((ref = order_weights[i]) < 0) || 644 ((p = get_pri(ref)) == NULL) || 645 (p->pri == -1)) { 646 set_pri(pri_undefined[i], -1, RESOLVED); 647 } else { 648 set_pri(pri_undefined[i], ref, REFER); 649 } 650 order_weights[i] = -1; 651 } 652 break; 653 654 case T_SYMBOL: 655 for (i = 0; i < NUM_WT; i++) { 656 if (((ref = order_weights[i]) < 0) || 657 ((p = get_pri(ref)) == NULL) || 658 (p->pri == -1)) { 659 set_pri(currundef->ref[i], pri, RESOLVED); 660 } else { 661 set_pri(currundef->ref[i], ref, REFER); 662 } 663 order_weights[i] = -1; 664 } 665 break; 666 667 default: 668 INTERR; 669 } 670 671 nextpri++; 672 } 673 674 static void 675 start_order(int type) 676 { 677 int i; 678 679 lastorder = currorder; 680 currorder = type; 681 682 /* this is used to protect ELLIPSIS processing */ 683 if ((lastorder == T_ELLIPSIS) && (type != T_CHAR)) { 684 fprintf(stderr, "character value expected"); 685 } 686 687 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 688 order_weights[i] = -1; 689 } 690 curr_weight = 0; 691 } 692 693 void 694 start_order_undefined(void) 695 { 696 start_order(T_UNDEFINED); 697 } 698 699 void 700 start_order_symbol(char *name) 701 { 702 currundef = get_collundef(name); 703 start_order(T_SYMBOL); 704 } 705 706 void 707 start_order_char(wchar_t wc) 708 { 709 collchar_t *cc; 710 int32_t ref; 711 712 start_order(T_CHAR); 713 714 /* 715 * If we last saw an ellipsis, then we need to close the range. 716 * Handle that here. Note that we have to be careful because the 717 * items *inside* the range are treated exclusiveley to the items 718 * outside of the range. The ends of the range can have quite 719 * different weights than the range members. 720 */ 721 if (lastorder == T_ELLIPSIS) { 722 int i; 723 724 if (wc < ellipsis_start) { 725 fprintf(stderr, "malformed range!"); 726 return; 727 } 728 while (ellipsis_start < wc) { 729 /* 730 * pick all of the saved weights for the 731 * ellipsis. note that -1 encodes for the 732 * ellipsis itself, which means to take the 733 * current relative priority. 734 */ 735 if ((cc = get_collchar(ellipsis_start, 1)) == NULL) { 736 INTERR; 737 return; 738 } 739 for (i = 0; i < NUM_WT; i++) { 740 collpri_t *p; 741 if (((ref = ellipsis_weights[i]) == -1) || 742 ((p = get_pri(ref)) == NULL) || 743 (p->pri == -1)) { 744 set_pri(cc->ref[i], nextpri, RESOLVED); 745 } else { 746 set_pri(cc->ref[i], ref, REFER); 747 } 748 ellipsis_weights[i] = 0; 749 } 750 ellipsis_start++; 751 nextpri++; 752 } 753 } 754 755 currchar = get_collchar(wc, 1); 756 } 757 758 void 759 start_order_collelem(collelem_t *e) 760 { 761 start_order(T_COLLELEM); 762 currelem = e; 763 } 764 765 void 766 start_order_ellipsis(void) 767 { 768 int i; 769 770 start_order(T_ELLIPSIS); 771 772 if (lastorder != T_CHAR) { 773 fprintf(stderr, "illegal starting point for range"); 774 return; 775 } 776 777 for (i = 0; i < NUM_WT; i++) { 778 ellipsis_weights[i] = order_weights[i]; 779 } 780 } 781 782 void 783 define_collelem(char *name, wchar_t *wcs) 784 { 785 collelem_t *e; 786 avl_index_t where1; 787 avl_index_t where2; 788 int i; 789 790 if (wcslen(wcs) >= COLLATE_STR_LEN) { 791 fprintf(stderr,"expanded collation element too long"); 792 return; 793 } 794 795 if ((e = calloc(sizeof (*e), 1)) == NULL) { 796 fprintf(stderr, "out of memory"); 797 return; 798 } 799 e->expand = wcs; 800 e->symbol = name; 801 802 /* 803 * This is executed before the order statement, so we don't 804 * know how many priorities we *really* need. We allocate one 805 * for each possible weight. Not a big deal, as collating-elements 806 * prove to be quite rare. 807 */ 808 for (i = 0; i < COLL_WEIGHTS_MAX; i++) { 809 e->ref[i] = new_pri(); 810 } 811 812 /* A character sequence can only reduce to one element. */ 813 if ((avl_find(&elem_by_symbol, e, &where1) != NULL) || 814 (avl_find(&elem_by_expand, e, &where2) != NULL)) { 815 fprintf(stderr, "duplicate collating element definition"); 816 return; 817 } 818 avl_insert(&elem_by_symbol, e, where1); 819 avl_insert(&elem_by_expand, e, where2); 820 } 821 822 void 823 add_order_bit(int kw) 824 { 825 uint8_t bit = DIRECTIVE_UNDEF; 826 827 switch (kw) { 828 case T_FORWARD: 829 bit = DIRECTIVE_FORWARD; 830 break; 831 case T_BACKWARD: 832 bit = DIRECTIVE_BACKWARD; 833 break; 834 case T_POSITION: 835 bit = DIRECTIVE_POSITION; 836 break; 837 default: 838 INTERR; 839 break; 840 } 841 collinfo.directive[collinfo.directive_count] |= bit; 842 } 843 844 void 845 add_order_directive(void) 846 { 847 if (collinfo.directive_count >= COLL_WEIGHTS_MAX) { 848 fprintf(stderr,"too many directives (max %d)", COLL_WEIGHTS_MAX); 849 } 850 collinfo.directive_count++; 851 } 852 853 static void 854 add_order_pri(int32_t ref) 855 { 856 if (curr_weight >= NUM_WT) { 857 fprintf(stderr,"too many weights (max %d)", NUM_WT); 858 return; 859 } 860 order_weights[curr_weight] = ref; 861 curr_weight++; 862 } 863 864 void 865 add_order_collsym(collsym_t *s) 866 { 867 add_order_pri(s->ref); 868 } 869 870 void 871 add_order_char(wchar_t wc) 872 { 873 collchar_t *cc; 874 875 if ((cc = get_collchar(wc, 1)) == NULL) { 876 INTERR; 877 return; 878 } 879 880 add_order_pri(cc->ref[curr_weight]); 881 } 882 883 void 884 add_order_collelem(collelem_t *e) 885 { 886 add_order_pri(e->ref[curr_weight]); 887 } 888 889 void 890 add_order_ignore(void) 891 { 892 add_order_pri(pri_ignore); 893 } 894 895 void 896 add_order_symbol(char *sym) 897 { 898 collundef_t *c; 899 if ((c = get_collundef(sym)) == NULL) { 900 INTERR; 901 return; 902 } 903 add_order_pri(c->ref[curr_weight]); 904 } 905 906 void 907 add_order_ellipsis(void) 908 { 909 /* special NULL value indicates self reference */ 910 add_order_pri(0); 911 } 912 913 void 914 add_order_subst(void) 915 { 916 subst_t srch; 917 subst_t *s; 918 avl_index_t where; 919 int i; 920 921 (void) memset(&srch, 0, sizeof (srch)); 922 for (i = 0; i < curr_subst; i++) { 923 srch.ref[i] = subst_weights[i]; 924 subst_weights[i] = 0; 925 } 926 s = avl_find(&substs_ref[curr_weight], &srch, &where); 927 928 if (s == NULL) { 929 if ((s = calloc(sizeof (*s), 1)) == NULL) { 930 fprintf(stderr,"out of memory"); 931 return; 932 } 933 s->key = new_pri(); 934 935 /* 936 * We use a self reference for our key, but we set a 937 * high bit to indicate that this is a substitution 938 * reference. This will expedite table lookups later, 939 * and prevent table lookups for situations that don't 940 * require it. (In short, its a big win, because we 941 * can skip a lot of binary searching.) 942 */ 943 set_pri(s->key, 944 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY), 945 RESOLVED); 946 nextsubst[curr_weight] += 1; 947 948 for (i = 0; i < curr_subst; i++) { 949 s->ref[i] = srch.ref[i]; 950 } 951 952 avl_insert(&substs_ref[curr_weight], s, where); 953 954 if (avl_find(&substs[curr_weight], s, &where) != NULL) { 955 INTERR; 956 return; 957 } 958 avl_insert(&substs[curr_weight], s, where); 959 } 960 curr_subst = 0; 961 962 963 /* 964 * We are using the current (unique) priority as a search key 965 * in the substitution table. 966 */ 967 add_order_pri(s->key); 968 } 969 970 static void 971 add_subst_pri(int32_t ref) 972 { 973 if (curr_subst >= COLLATE_STR_LEN) { 974 fprintf(stderr,"substitution string is too long"); 975 return; 976 } 977 subst_weights[curr_subst] = ref; 978 curr_subst++; 979 } 980 981 void 982 add_subst_char(wchar_t wc) 983 { 984 collchar_t *cc; 985 986 987 if (((cc = get_collchar(wc, 1)) == NULL) || 988 (cc->wc != wc)) { 989 INTERR; 990 return; 991 } 992 /* we take the weight for the character at that position */ 993 add_subst_pri(cc->ref[curr_weight]); 994 } 995 996 void 997 add_subst_collelem(collelem_t *e) 998 { 999 add_subst_pri(e->ref[curr_weight]); 1000 } 1001 1002 void 1003 add_subst_collsym(collsym_t *s) 1004 { 1005 add_subst_pri(s->ref); 1006 } 1007 1008 void 1009 add_subst_symbol(char *ptr) 1010 { 1011 collundef_t *cu; 1012 1013 if ((cu = get_collundef(ptr)) != NULL) { 1014 add_subst_pri(cu->ref[curr_weight]); 1015 } 1016 } 1017 1018 void 1019 add_weight(int32_t ref, int pass) 1020 { 1021 weight_t srch; 1022 weight_t *w; 1023 avl_index_t where; 1024 1025 srch.pri = resolve_pri(ref); 1026 1027 /* No translation of ignores */ 1028 if (srch.pri == 0) 1029 return; 1030 1031 /* Substitution priorities are not weights */ 1032 if (srch.pri & COLLATE_SUBST_PRIORITY) 1033 return; 1034 1035 if (avl_find(&weights[pass], &srch, &where) != NULL) 1036 return; 1037 1038 if ((w = calloc(sizeof (*w), 1)) == NULL) { 1039 fprintf(stderr, "out of memory"); 1040 return; 1041 } 1042 w->pri = srch.pri; 1043 avl_insert(&weights[pass], w, where); 1044 } 1045 1046 void 1047 add_weights(int32_t *refs) 1048 { 1049 int i; 1050 for (i = 0; i < NUM_WT; i++) { 1051 add_weight(refs[i], i); 1052 } 1053 } 1054 1055 int32_t 1056 get_weight(int32_t ref, int pass) 1057 { 1058 weight_t srch; 1059 weight_t *w; 1060 int32_t pri; 1061 1062 pri = resolve_pri(ref); 1063 if (pri & COLLATE_SUBST_PRIORITY) { 1064 return (pri); 1065 } 1066 if (pri <= 0) { 1067 return (pri); 1068 } 1069 srch.pri = pri; 1070 if ((w = avl_find(&weights[pass], &srch, NULL)) == NULL) { 1071 INTERR; 1072 return (-1); 1073 } 1074 return (w->opt); 1075 } 1076 1077 wchar_t * 1078 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n) 1079 { 1080 wchar_t *os1 = s1; 1081 1082 n++; 1083 while (--n > 0 && (*s1++ = *s2++) != 0) 1084 continue; 1085 if (n > 0) 1086 while (--n > 0) 1087 *s1++ = 0; 1088 return (os1); 1089 } 1090 1091 void 1092 dump_collate(void) 1093 { 1094 FILE *f; 1095 int i, j, n; 1096 size_t sz; 1097 int32_t pri; 1098 collelem_t *ce; 1099 collchar_t *cc; 1100 subst_t *sb; 1101 char vers[COLLATE_STR_LEN]; 1102 collate_char_t chars[UCHAR_MAX + 1]; 1103 collate_large_t *large; 1104 collate_subst_t *subst[COLL_WEIGHTS_MAX]; 1105 collate_chain_t *chain; 1106 1107 /* 1108 * We have to run throught a preliminary pass to identify all the 1109 * weights that we use for each sorting level. 1110 */ 1111 for (i = 0; i < NUM_WT; i++) { 1112 add_weight(pri_ignore, i); 1113 } 1114 for (i = 0; i < NUM_WT; i++) { 1115 for (sb = avl_first(&substs[i]); sb; 1116 sb = AVL_NEXT(&substs[i], sb)) { 1117 for (j = 0; sb->ref[j]; j++) { 1118 add_weight(sb->ref[j], i); 1119 } 1120 } 1121 } 1122 for (ce = avl_first(&elem_by_expand); 1123 ce != NULL; 1124 ce = AVL_NEXT(&elem_by_expand, ce)) { 1125 add_weights(ce->ref); 1126 } 1127 for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) { 1128 add_weights(cc->ref); 1129 } 1130 1131 /* 1132 * Now we walk the entire set of weights, removing the gaps 1133 * in the weights. This gives us optimum usage. The walk 1134 * occurs in priority. 1135 */ 1136 for (i = 0; i < NUM_WT; i++) { 1137 weight_t *w; 1138 for (w = avl_first(&weights[i]); w; 1139 w = AVL_NEXT(&weights[i], w)) { 1140 w->opt = nweight[i]; 1141 nweight[i] += 1; 1142 } 1143 } 1144 1145 (void) memset(&chars, 0, sizeof (chars)); 1146 (void) memset(vers, 0, COLLATE_STR_LEN); 1147 (void) strlcpy(vers, COLLATE_VERSION, sizeof (vers)); 1148 1149 /* 1150 * We need to make sure we arrange for the UNDEFINED field 1151 * to show up. Also, set the total weight counts. 1152 */ 1153 for (i = 0; i < NUM_WT; i++) { 1154 if (resolve_pri(pri_undefined[i]) == -1) { 1155 set_pri(pri_undefined[i], -1, RESOLVED); 1156 /* they collate at the end of everything else */ 1157 collinfo.undef_pri[i] = COLLATE_MAX_PRIORITY; 1158 } 1159 collinfo.pri_count[i] = nweight[i]; 1160 } 1161 1162 collinfo.pri_count[NUM_WT] = max_wide(); 1163 collinfo.undef_pri[NUM_WT] = COLLATE_MAX_PRIORITY; 1164 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED; 1165 1166 /* 1167 * Ordinary character priorities 1168 */ 1169 for (i = 0; i <= UCHAR_MAX; i++) { 1170 if ((cc = get_collchar(i, 0)) != NULL) { 1171 for (j = 0; j < NUM_WT; j++) { 1172 chars[i].pri[j] = get_weight(cc->ref[j], j); 1173 } 1174 } else { 1175 for (j = 0; j < NUM_WT; j++) { 1176 chars[i].pri[j] = 1177 get_weight(pri_undefined[j], j); 1178 } 1179 /* 1180 * Per POSIX, for undefined characters, we 1181 * also have to add a last item, which is the 1182 * character code. 1183 */ 1184 chars[i].pri[NUM_WT] = i; 1185 } 1186 } 1187 1188 /* 1189 * Substitution tables 1190 */ 1191 for (i = 0; i < NUM_WT; i++) { 1192 collate_subst_t *st = NULL; 1193 n = collinfo.subst_count[i] = avl_numnodes(&substs[i]); 1194 if ((st = calloc(sizeof (collate_subst_t) * n, 1)) == NULL) { 1195 fprintf(stderr, "out of memory"); 1196 return; 1197 } 1198 n = 0; 1199 for (sb = avl_first(&substs[i]); sb; 1200 sb = AVL_NEXT(&substs[i], sb)) { 1201 if ((st[n].key = resolve_pri(sb->key)) < 0) { 1202 /* by definition these resolve! */ 1203 INTERR; 1204 } 1205 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) { 1206 INTERR; 1207 } 1208 for (j = 0; sb->ref[j]; j++) { 1209 st[n].pri[j] = get_weight(sb->ref[j], i); 1210 } 1211 n++; 1212 } 1213 if (n != collinfo.subst_count[i]) 1214 INTERR; 1215 subst[i] = st; 1216 } 1217 1218 1219 /* 1220 * Chains, i.e. collating elements 1221 */ 1222 collinfo.chain_count = avl_numnodes(&elem_by_expand); 1223 chain = calloc(sizeof (collate_chain_t), collinfo.chain_count); 1224 if (chain == NULL) { 1225 fprintf(stderr, "out of memory"); 1226 return; 1227 } 1228 for (n = 0, ce = avl_first(&elem_by_expand); 1229 ce != NULL; 1230 ce = AVL_NEXT(&elem_by_expand, ce), n++) { 1231 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN); 1232 for (i = 0; i < NUM_WT; i++) { 1233 chain[n].pri[i] = get_weight(ce->ref[i], i); 1234 } 1235 } 1236 if (n != collinfo.chain_count) 1237 INTERR; 1238 1239 /* 1240 * Large (> UCHAR_MAX) character priorities 1241 */ 1242 large = calloc(sizeof (collate_large_t) * avl_numnodes(&collchars), 1); 1243 if (large == NULL) { 1244 fprintf(stderr, "out of memory"); 1245 return; 1246 } 1247 1248 i = 0; 1249 for (cc = avl_first(&collchars); cc; cc = AVL_NEXT(&collchars, cc)) { 1250 int undef = 0; 1251 /* we already gathered those */ 1252 if (cc->wc <= UCHAR_MAX) 1253 continue; 1254 for (j = 0; j < NUM_WT; j++) { 1255 if ((pri = get_weight(cc->ref[j], j)) < 0) { 1256 undef = 1; 1257 } 1258 if (undef && (pri >= 0)) { 1259 /* if undefined, then all priorities are */ 1260 INTERR; 1261 } else { 1262 large[i].pri.pri[j] = pri; 1263 } 1264 } 1265 if (!undef) { 1266 large[i].val = cc->wc; 1267 collinfo.large_count = i++; 1268 } 1269 } 1270 1271 if ((f = open_category()) == NULL) { 1272 return; 1273 } 1274 1275 /* Time to write the entire data set out */ 1276 1277 if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) || 1278 (wr_category(&collinfo, sizeof (collinfo), f) < 0) || 1279 (wr_category(&chars, sizeof (chars), f) < 0)) { 1280 return; 1281 } 1282 1283 for (i = 0; i < NUM_WT; i++) { 1284 sz = sizeof (collate_subst_t) * collinfo.subst_count[i]; 1285 if (wr_category(subst[i], sz, f) < 0) { 1286 return; 1287 } 1288 } 1289 sz = sizeof (collate_chain_t) * collinfo.chain_count; 1290 if (wr_category(chain, sz, f) < 0) { 1291 return; 1292 } 1293 sz = sizeof (collate_large_t) * collinfo.large_count; 1294 if (wr_category(large, sz, f) < 0) { 1295 return; 1296 } 1297 1298 close_category(f); 1299 } 1300