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