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