usr.bin/localedef/collate.c

   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 #pragma GCC diagnostic push
 439 #pragma GCC diagnostic ignored "-Wcast-qual"
 440
 441 static int
 442 subst_compare_ref(const void *n1, const void *n2)
 443 {
 444         int32_t *c1 = ((subst_t *)n1)->ref;
 445         int32_t *c2 = ((subst_t *)n2)->ref;
 446         int rv;
 447
 448         rv = wcscmp((wchar_t *)c1, (wchar_t *)c2);
 449         return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
 450 }
 451
 452 RB_GENERATE_STATIC(substs_ref, subst, entry_ref, subst_compare_ref);
 453
 454 #pragma GCC diagnostic pop
 455
 456 void
 457 init_collate(void)
 458 {
 459         int i;
 460
 461         RB_INIT(&collsyms);
 462
 463         RB_INIT(&collundefs);
 464
 465         RB_INIT(&elem_by_symbol);
 466
 467         RB_INIT(&elem_by_expand);
 468
 469         RB_INIT(&collchars);
 470
 471         for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
 472                 RB_INIT(&substs[i]);
 473                 RB_INIT(&substs_ref[i]);
 474                 RB_INIT(&weights[i]);
 475                 nweight[i] = 1;
 476         }
 477
 478         (void) memset(&collinfo, 0, sizeof (collinfo));
 479
 480         /* allocate some initial priorities */
 481         pri_ignore = new_pri();
 482
 483         set_pri(pri_ignore, 0, RESOLVED);
 484
 485         for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
 486                 pri_undefined[i] = new_pri();
 487
 488                 /* we will override this later */
 489                 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN);
 490         }
 491 }
 492
 493 void
 494 define_collsym(char *name)
 495 {
 496         collsym_t       *sym;
 497
 498         if ((sym = calloc(sizeof (*sym), 1)) == NULL) {
 499                 fprintf(stderr,"out of memory");
 500                 return;
 501         }
 502         sym->name = name;
 503         sym->ref = new_pri();
 504
 505         if (RB_FIND(collsyms, &collsyms, sym) != NULL) {
 506                 /*
 507                  * This should never happen because we are only called
 508                  * for undefined symbols.
 509                  */
 510                 INTERR;
 511                 return;
 512         }
 513         RB_INSERT(collsyms, &collsyms, sym);
 514 }
 515
 516 collsym_t *
 517 lookup_collsym(char *name)
 518 {
 519         collsym_t       srch;
 520
 521         srch.name = name;
 522         return (RB_FIND(collsyms, &collsyms, &srch));
 523 }
 524
 525 collelem_t *
 526 lookup_collelem(char *symbol)
 527 {
 528         collelem_t      srch;
 529
 530         srch.symbol = symbol;
 531         return (RB_FIND(elem_by_symbol, &elem_by_symbol, &srch));
 532 }
 533
 534 static collundef_t *
 535 get_collundef(char *name)
 536 {
 537         collundef_t     srch;
 538         collundef_t     *ud;
 539         int             i;
 540
 541         srch.name = name;
 542         if ((ud = RB_FIND(collundefs, &collundefs, &srch)) == NULL) {
 543                 if (((ud = calloc(sizeof (*ud), 1)) == NULL) ||
 544                     ((ud->name = strdup(name)) == NULL)) {
 545                         fprintf(stderr,"out of memory");
 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
 557 static collchar_t *
 558 get_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(sizeof (*cc), 1)) == NULL) {
 568                         fprintf(stderr, "out of memory");
 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
 580 void
 581 end_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
 590 void
 591 end_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
 680 static void
 681 start_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");
 691         }
 692
 693         for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
 694                 order_weights[i] = -1;
 695         }
 696         curr_weight = 0;
 697 }
 698
 699 void
 700 start_order_undefined(void)
 701 {
 702         start_order(T_UNDEFINED);
 703 }
 704
 705 void
 706 start_order_symbol(char *name)
 707 {
 708         currundef = get_collundef(name);
 709         start_order(T_SYMBOL);
 710 }
 711
 712 void
 713 start_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!");
 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
 764 void
 765 start_order_collelem(collelem_t *e)
 766 {
 767         start_order(T_COLLELEM);
 768         currelem = e;
 769 }
 770
 771 void
 772 start_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");
 780                 return;
 781         }
 782
 783         for (i = 0; i < NUM_WT; i++) {
 784                 ellipsis_weights[i] = order_weights[i];
 785         }
 786 }
 787
 788 void
 789 define_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");
 796                 return;
 797         }
 798
 799         if ((e = calloc(sizeof (*e), 1)) == NULL) {
 800                 fprintf(stderr, "out of memory");
 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");
 820                 return;
 821         }
 822         RB_INSERT(elem_by_symbol, &elem_by_symbol, e);
 823         RB_INSERT(elem_by_expand, &elem_by_expand, e);
 824 }
 825
 826 void
 827 add_order_bit(int kw)
 828 {
 829         uint8_t bit = DIRECTIVE_UNDEF;
 830
 831         switch (kw) {
 832         case T_FORWARD:
 833                 bit = DIRECTIVE_FORWARD;
 834                 break;
 835         case T_BACKWARD:
 836                 bit = DIRECTIVE_BACKWARD;
 837                 break;
 838         case T_POSITION:
 839                 bit = DIRECTIVE_POSITION;
 840                 break;
 841         default:
 842                 INTERR;
 843                 break;
 844         }
 845         collinfo.directive[collinfo.directive_count] |= bit;
 846 }
 847
 848 void
 849 add_order_directive(void)
 850 {
 851         if (collinfo.directive_count >= COLL_WEIGHTS_MAX) {
 852                 fprintf(stderr,"too many directives (max %d)", COLL_WEIGHTS_MAX);
 853         }
 854         collinfo.directive_count++;
 855 }
 856
 857 static void
 858 add_order_pri(int32_t ref)
 859 {
 860         if (curr_weight >= NUM_WT) {
 861                 fprintf(stderr,"too many weights (max %d)", NUM_WT);
 862                 return;
 863         }
 864         order_weights[curr_weight] = ref;
 865         curr_weight++;
 866 }
 867
 868 void
 869 add_order_collsym(collsym_t *s)
 870 {
 871         add_order_pri(s->ref);
 872 }
 873
 874 void
 875 add_order_char(wchar_t wc)
 876 {
 877         collchar_t *cc;
 878
 879         if ((cc = get_collchar(wc, 1)) == NULL) {
 880                 INTERR;
 881                 return;
 882         }
 883
 884         add_order_pri(cc->ref[curr_weight]);
 885 }
 886
 887 void
 888 add_order_collelem(collelem_t *e)
 889 {
 890         add_order_pri(e->ref[curr_weight]);
 891 }
 892
 893 void
 894 add_order_ignore(void)
 895 {
 896         add_order_pri(pri_ignore);
 897 }
 898
 899 void
 900 add_order_symbol(char *sym)
 901 {
 902         collundef_t *c;
 903         if ((c = get_collundef(sym)) == NULL) {
 904                 INTERR;
 905                 return;
 906         }
 907         add_order_pri(c->ref[curr_weight]);
 908 }
 909
 910 void
 911 add_order_ellipsis(void)
 912 {
 913         /* special NULL value indicates self reference */
 914         add_order_pri(0);
 915 }
 916
 917 void
 918 add_order_subst(void)
 919 {
 920         subst_t srch;
 921         subst_t *s;
 922         int i;
 923
 924         (void) memset(&srch, 0, sizeof (srch));
 925         for (i = 0; i < curr_subst; i++) {
 926                 srch.ref[i] = subst_weights[i];
 927                 subst_weights[i] = 0;
 928         }
 929         s = RB_FIND(substs_ref, &substs_ref[curr_weight], &srch);
 930
 931         if (s == NULL) {
 932                 if ((s = calloc(sizeof (*s), 1)) == NULL) {
 933                         fprintf(stderr,"out of memory");
 934                         return;
 935                 }
 936                 s->key = new_pri();
 937
 938                 /*
 939                  * We use a self reference for our key, but we set a
 940                  * high bit to indicate that this is a substitution
 941                  * reference.  This will expedite table lookups later,
 942                  * and prevent table lookups for situations that don't
 943                  * require it.  (In short, its a big win, because we
 944                  * can skip a lot of binary searching.)
 945                  */
 946                 set_pri(s->key,
 947                     (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY),
 948                     RESOLVED);
 949                 nextsubst[curr_weight] += 1;
 950
 951                 for (i = 0; i < curr_subst; i++) {
 952                         s->ref[i] = srch.ref[i];
 953                 }
 954
 955                 RB_INSERT(substs_ref, &substs_ref[curr_weight], s);
 956
 957                 if (RB_FIND(substs, &substs[curr_weight], s) != NULL) {
 958                         INTERR;
 959                         return;
 960                 }
 961                 RB_INSERT(substs, &substs[curr_weight], s);
 962         }
 963         curr_subst = 0;
 964
 965
 966         /*
 967          * We are using the current (unique) priority as a search key
 968          * in the substitution table.
 969          */
 970         add_order_pri(s->key);
 971 }
 972
 973 static void
 974 add_subst_pri(int32_t ref)
 975 {
 976         if (curr_subst >= COLLATE_STR_LEN) {
 977                 fprintf(stderr,"substitution string is too long");
 978                 return;
 979         }
 980         subst_weights[curr_subst] = ref;
 981         curr_subst++;
 982 }
 983
 984 void
 985 add_subst_char(wchar_t wc)
 986 {
 987         collchar_t *cc;
 988
 989
 990         if (((cc = get_collchar(wc, 1)) == NULL) ||
 991             (cc->wc != wc)) {
 992                 INTERR;
 993                 return;
 994         }
 995         /* we take the weight for the character at that position */
 996         add_subst_pri(cc->ref[curr_weight]);
 997 }
 998
 999 void
1000 add_subst_collelem(collelem_t *e)
1001 {
1002         add_subst_pri(e->ref[curr_weight]);
1003 }
1004
1005 void
1006 add_subst_collsym(collsym_t *s)
1007 {
1008         add_subst_pri(s->ref);
1009 }
1010
1011 void
1012 add_subst_symbol(char *ptr)
1013 {
1014         collundef_t *cu;
1015
1016         if ((cu = get_collundef(ptr)) != NULL) {
1017                 add_subst_pri(cu->ref[curr_weight]);
1018         }
1019 }
1020
1021 void
1022 add_weight(int32_t ref, int pass)
1023 {
1024         weight_t srch;
1025         weight_t *w;
1026
1027         srch.pri = resolve_pri(ref);
1028
1029         /* No translation of ignores */
1030         if (srch.pri == 0)
1031                 return;
1032
1033         /* Substitution priorities are not weights */
1034         if (srch.pri & COLLATE_SUBST_PRIORITY)
1035                 return;
1036
1037         if (RB_FIND(weights, &weights[pass], &srch) != NULL)
1038                 return;
1039
1040         if ((w = calloc(sizeof (*w), 1)) == NULL) {
1041                 fprintf(stderr, "out of memory");
1042                 return;
1043         }
1044         w->pri = srch.pri;
1045         RB_INSERT(weights, &weights[pass], w);
1046 }
1047
1048 void
1049 add_weights(int32_t *refs)
1050 {
1051         int i;
1052         for (i = 0; i < NUM_WT; i++) {
1053                 add_weight(refs[i], i);
1054         }
1055 }
1056
1057 int32_t
1058 get_weight(int32_t ref, int pass)
1059 {
1060         weight_t        srch;
1061         weight_t        *w;
1062         int32_t         pri;
1063
1064         pri = resolve_pri(ref);
1065         if (pri & COLLATE_SUBST_PRIORITY) {
1066                 return (pri);
1067         }
1068         if (pri <= 0) {
1069                 return (pri);
1070         }
1071         srch.pri = pri;
1072         if ((w = RB_FIND(weights, &weights[pass], &srch)) == NULL) {
1073                 INTERR;
1074                 return (-1);
1075         }
1076         return (w->opt);
1077 }
1078
1079 wchar_t *
1080 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n)
1081 {
1082         wchar_t *os1 = s1;
1083
1084         n++;
1085         while (--n > 0 && (*s1++ = *s2++) != 0)
1086                 continue;
1087         if (n > 0)
1088                 while (--n > 0)
1089                         *s1++ = 0;
1090         return (os1);
1091 }
1092
1093 #define RB_COUNT(x, name, head, cnt) do { \
1094         (cnt) = 0; \
1095         RB_FOREACH(x, name, (head)) { \
1096                 (cnt)++; \
1097         } \
1098 } while (0)
1099
1100 #define RB_NUMNODES(type, name, head, cnt) do { \
1101         type *t; \
1102         cnt = 0; \
1103         RB_FOREACH(t, name, head) { \
1104                 cnt++; \
1105         } \
1106 } while (0)
1107
1108 void
1109 dump_collate(void)
1110 {
1111         FILE                    *f;
1112         int                     i, j, n;
1113         size_t                  sz;
1114         int32_t                 pri;
1115         collelem_t              *ce;
1116         collchar_t              *cc;
1117         subst_t                 *sb;
1118         char                    vers[COLLATE_STR_LEN];
1119         collate_char_t          chars[UCHAR_MAX + 1];
1120         collate_large_t         *large;
1121         collate_subst_t         *subst[COLL_WEIGHTS_MAX];
1122         collate_chain_t         *chain;
1123
1124         /*
1125          * We have to run throught a preliminary pass to identify all the
1126          * weights that we use for each sorting level.
1127          */
1128         for (i = 0; i < NUM_WT; i++) {
1129                 add_weight(pri_ignore, i);
1130         }
1131         for (i = 0; i < NUM_WT; i++) {
1132                 RB_FOREACH(sb, substs, &substs[i]) {
1133                         for (j = 0; sb->ref[j]; j++) {
1134                                 add_weight(sb->ref[j], i);
1135                         }
1136                 }
1137         }
1138         RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1139                 add_weights(ce->ref);
1140         }
1141         RB_FOREACH(cc, collchars, &collchars) {
1142                 add_weights(cc->ref);
1143         }
1144
1145         /*
1146          * Now we walk the entire set of weights, removing the gaps
1147          * in the weights.  This gives us optimum usage.  The walk
1148          * occurs in priority.
1149          */
1150         for (i = 0; i < NUM_WT; i++) {
1151                 weight_t *w;
1152                 RB_FOREACH(w, weights, &weights[i]) {
1153                         w->opt = nweight[i];
1154                         nweight[i] += 1;
1155                 }
1156         }
1157
1158         (void) memset(&chars, 0, sizeof (chars));
1159         (void) memset(vers, 0, COLLATE_STR_LEN);
1160         (void) strlcpy(vers, COLLATE_VERSION, sizeof (vers));
1161
1162         /*
1163          * We need to make sure we arrange for the UNDEFINED field
1164          * to show up.  Also, set the total weight counts.
1165          */
1166         for (i = 0; i < NUM_WT; i++) {
1167                 if (resolve_pri(pri_undefined[i]) == -1) {
1168                         set_pri(pri_undefined[i], -1, RESOLVED);
1169                         /* they collate at the end of everything else */
1170                         collinfo.undef_pri[i] = COLLATE_MAX_PRIORITY;
1171                 }
1172                 collinfo.pri_count[i] = nweight[i];
1173         }
1174
1175         collinfo.pri_count[NUM_WT] = max_wide();
1176         collinfo.undef_pri[NUM_WT] = COLLATE_MAX_PRIORITY;
1177         collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED;
1178
1179         /*
1180          * Ordinary character priorities
1181          */
1182         for (i = 0; i <= UCHAR_MAX; i++) {
1183                 if ((cc = get_collchar(i, 0)) != NULL) {
1184                         for (j = 0; j < NUM_WT; j++) {
1185                                 chars[i].pri[j] = get_weight(cc->ref[j], j);
1186                         }
1187                 } else {
1188                         for (j = 0; j < NUM_WT; j++) {
1189                                 chars[i].pri[j] =
1190                                     get_weight(pri_undefined[j], j);
1191                         }
1192                         /*
1193                          * Per POSIX, for undefined characters, we
1194                          * also have to add a last item, which is the
1195                          * character code.
1196                          */
1197                         chars[i].pri[NUM_WT] = i;
1198                 }
1199         }
1200
1201         /*
1202          * Substitution tables
1203          */
1204         for (i = 0; i < NUM_WT; i++) {
1205                 collate_subst_t *st = NULL;
1206                 subst_t *temp;
1207                 RB_COUNT(temp, substs, &substs[i], n);
1208                 collinfo.subst_count[i] = n;
1209                 if ((st = calloc(sizeof (collate_subst_t) * n, 1)) == NULL) {
1210                         fprintf(stderr, "out of memory");
1211                         return;
1212                 }
1213                 n = 0;
1214                 RB_FOREACH(sb, substs, &substs[i]) {
1215                         if ((st[n].key = resolve_pri(sb->key)) < 0) {
1216                                 /* by definition these resolve! */
1217                                 INTERR;
1218                         }
1219                         if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) {
1220                                 INTERR;
1221                         }
1222                         for (j = 0; sb->ref[j]; j++) {
1223                                 st[n].pri[j] = get_weight(sb->ref[j], i);
1224                         }
1225                         n++;
1226                 }
1227                 if (n != collinfo.subst_count[i])
1228                         INTERR;
1229                 subst[i] = st;
1230         }
1231
1232
1233         /*
1234          * Chains, i.e. collating elements
1235          */
1236         RB_NUMNODES(collelem_t, elem_by_expand, &elem_by_expand,
1237             collinfo.chain_count);
1238         chain = calloc(sizeof (collate_chain_t), collinfo.chain_count);
1239         if (chain == NULL) {
1240                 fprintf(stderr, "out of memory");
1241                 return;
1242         }
1243         n = 0;
1244         RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1245                 n++;
1246                 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
1247                 for (i = 0; i < NUM_WT; i++) {
1248                         chain[n].pri[i] = get_weight(ce->ref[i], i);
1249                 }
1250         }
1251         if (n != collinfo.chain_count)
1252                 INTERR;
1253
1254         /*
1255          * Large (> UCHAR_MAX) character priorities
1256          */
1257         RB_NUMNODES(collchar_t, collchars, &collchars, n);
1258         large = malloc(sizeof (collate_large_t) * n);
1259         if (large == NULL) {
1260                 fprintf(stderr, "out of memory");
1261                 return;
1262         }
1263         memset(large, 0, sizeof (collate_large_t) * n);
1264
1265         i = 0;
1266         RB_FOREACH(cc, collchars, &collchars) {
1267                 int     undef = 0;
1268                 /* we already gathered those */
1269                 if (cc->wc <= UCHAR_MAX)
1270                         continue;
1271                 for (j = 0; j < NUM_WT; j++) {
1272                         if ((pri = get_weight(cc->ref[j], j)) < 0) {
1273                                 undef = 1;
1274                         }
1275                         if (undef && (pri >= 0)) {
1276                                 /* if undefined, then all priorities are */
1277                                 INTERR;
1278                         } else {
1279                                 large[i].pri.pri[j] = pri;
1280                         }
1281                 }
1282                 if (!undef) {
1283                         large[i].val = cc->wc;
1284                         collinfo.large_count = i++;
1285                 }
1286         }
1287
1288         if ((f = open_category()) == NULL) {
1289                 return;
1290         }
1291
1292         /* Time to write the entire data set out */
1293
1294         if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) ||
1295             (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
1296             (wr_category(&chars, sizeof (chars), f) < 0)) {
1297                 return;
1298         }
1299
1300         for (i = 0; i < NUM_WT; i++) {
1301                 sz =  sizeof (collate_subst_t) * collinfo.subst_count[i];
1302                 if (wr_category(subst[i], sz, f) < 0) {
1303                         return;
1304                 }
1305         }
1306         sz = sizeof (collate_chain_t) * collinfo.chain_count;
1307         if (wr_category(chain, sz, f) < 0) {
1308                 return;
1309         }
1310         sz = sizeof (collate_large_t) * collinfo.large_count;
1311         if (wr_category(large, sz, f) < 0) {
1312                 return;
1313         }
1314
1315         close_category(f);
1316 }