usr.bin/localedef/collate.c

   1 /*-
   2  * Copyright 2018 Nexenta Systems, Inc.
   3  * Copyright 2015 John Marino <draco@marino.st>
   4  *
   5  * This source code is derived from the illumos localedef command, and
   6  * provided under BSD-style license terms by Nexenta Systems, Inc.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /*
  32  * LC_COLLATE database generation routines for localedef.
  33  */
  34 #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 static int32_t subst_count[COLL_WEIGHTS_MAX];
 257 static int32_t chain_count;
 258 static int32_t large_count;
 259
 260 static collpri_t        *prilist = NULL;
 261 static int              numpri = 0;
 262 static int              maxpri = 0;
 263
 264 static void start_order(int);
 265
 266 static int32_t
 267 new_pri(void)
 268 {
 269         int i;
 270
 271         if (numpri >= maxpri) {
 272                 maxpri = maxpri ? maxpri * 2 : 1024;
 273                 prilist = realloc(prilist, sizeof (collpri_t) * maxpri);
 274                 if (prilist == NULL) {
 275                         fprintf(stderr,"out of memory");
 276                         return (-1);
 277                 }
 278                 for (i = numpri; i < maxpri; i++) {
 279                         prilist[i].res = UNKNOWN;
 280                         prilist[i].pri = 0;
 281                         prilist[i].pass = 0;
 282                 }
 283         }
 284         return (numpri++);
 285 }
 286
 287 static collpri_t *
 288 get_pri(int32_t ref)
 289 {
 290         if ((ref < 0) || (ref > numpri)) {
 291                 INTERR;
 292                 return (NULL);
 293         }
 294         return (&prilist[ref]);
 295 }
 296
 297 static void
 298 set_pri(int32_t ref, int32_t v, res_t res)
 299 {
 300         collpri_t       *pri;
 301
 302         pri = get_pri(ref);
 303
 304         if ((res == REFER) && ((v < 0) || (v >= numpri))) {
 305                 INTERR;
 306         }
 307
 308         /* Resolve self references */
 309         if ((res == REFER) && (ref == v)) {
 310                 v = nextpri;
 311                 res = RESOLVED;
 312         }
 313
 314         if (pri->res != UNKNOWN) {
 315                 warn("repeated item in order list (first on %d)",
 316                     pri->lineno);
 317                 return;
 318         }
 319         pri->lineno = lineno;
 320         pri->pri = v;
 321         pri->res = res;
 322 }
 323
 324 static int32_t
 325 resolve_pri(int32_t ref)
 326 {
 327         collpri_t       *pri;
 328         static int32_t  pass = 0;
 329
 330         pri = get_pri(ref);
 331         pass++;
 332         while (pri->res == REFER) {
 333                 if (pri->pass == pass) {
 334                         /* report a line with the circular symbol */
 335                         lineno = pri->lineno;
 336                         fprintf(stderr,"circular reference in order list");
 337                         return (-1);
 338                 }
 339                 if ((pri->pri < 0) || (pri->pri >= numpri)) {
 340                         INTERR;
 341                         return (-1);
 342                 }
 343                 pri->pass = pass;
 344                 pri = &prilist[pri->pri];
 345         }
 346
 347         if (pri->res == UNKNOWN) {
 348                 return (-1);
 349         }
 350         if (pri->res != RESOLVED)
 351                 INTERR;
 352
 353         return (pri->pri);
 354 }
 355
 356 static int
 357 weight_compare(const void *n1, const void *n2)
 358 {
 359         int32_t k1 = ((const weight_t *)n1)->pri;
 360         int32_t k2 = ((const weight_t *)n2)->pri;
 361
 362         return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
 363 }
 364
 365 RB_GENERATE_STATIC(weights, weight, entry, weight_compare);
 366
 367 static int
 368 collsym_compare(const void *n1, const void *n2)
 369 {
 370         const collsym_t *c1 = n1;
 371         const collsym_t *c2 = n2;
 372         int rv;
 373
 374         rv = strcmp(c1->name, c2->name);
 375         return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
 376 }
 377
 378 RB_GENERATE_STATIC(collsyms, collsym, entry, collsym_compare);
 379
 380 static int
 381 collundef_compare(const void *n1, const void *n2)
 382 {
 383         const collundef_t *c1 = n1;
 384         const collundef_t *c2 = n2;
 385         int rv;
 386
 387         rv = strcmp(c1->name, c2->name);
 388         return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
 389 }
 390
 391 RB_GENERATE_STATIC(collundefs, collundef, entry, collundef_compare);
 392
 393 static int
 394 element_compare_symbol(const void *n1, const void *n2)
 395 {
 396         const collelem_t *c1 = n1;
 397         const collelem_t *c2 = n2;
 398         int rv;
 399
 400         rv = strcmp(c1->symbol, c2->symbol);
 401         return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
 402 }
 403
 404 RB_GENERATE_STATIC(elem_by_symbol, collelem, rb_bysymbol, element_compare_symbol);
 405
 406 static int
 407 element_compare_expand(const void *n1, const void *n2)
 408 {
 409         const collelem_t *c1 = n1;
 410         const collelem_t *c2 = n2;
 411         int rv;
 412
 413         rv = wcscmp(c1->expand, c2->expand);
 414         return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
 415 }
 416
 417 RB_GENERATE_STATIC(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_GENERATE_STATIC(collchars, collchar, entry, collchar_compare);
 429
 430 static int
 431 subst_compare(const void *n1, const void *n2)
 432 {
 433         int32_t k1 = ((const subst_t *)n1)->key;
 434         int32_t k2 = ((const subst_t *)n2)->key;
 435
 436         return (k1 < k2 ? -1 : k1 > k2 ? 1 : 0);
 437 }
 438
 439 RB_GENERATE_STATIC(substs, subst, entry, subst_compare);
 440
 441 static int
 442 subst_compare_ref(const void *n1, const void *n2)
 443 {
 444         const wchar_t *c1 = ((const subst_t *)n1)->ref;
 445         const wchar_t *c2 = ((const subst_t *)n2)->ref;
 446         int rv;
 447
 448         rv = wcscmp(c1, c2);
 449         return ((rv < 0) ? -1 : (rv > 0) ? 1 : 0);
 450 }
 451
 452 RB_GENERATE_STATIC(substs_ref, subst, entry_ref, subst_compare_ref);
 453
 454 void
 455 init_collate(void)
 456 {
 457         int i;
 458
 459         RB_INIT(&collsyms);
 460
 461         RB_INIT(&collundefs);
 462
 463         RB_INIT(&elem_by_symbol);
 464
 465         RB_INIT(&elem_by_expand);
 466
 467         RB_INIT(&collchars);
 468
 469         for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
 470                 RB_INIT(&substs[i]);
 471                 RB_INIT(&substs_ref[i]);
 472                 RB_INIT(&weights[i]);
 473                 nweight[i] = 1;
 474         }
 475
 476         (void) memset(&collinfo, 0, sizeof (collinfo));
 477
 478         /* allocate some initial priorities */
 479         pri_ignore = new_pri();
 480
 481         set_pri(pri_ignore, 0, RESOLVED);
 482
 483         for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
 484                 pri_undefined[i] = new_pri();
 485
 486                 /* we will override this later */
 487                 set_pri(pri_undefined[i], COLLATE_MAX_PRIORITY, UNKNOWN);
 488         }
 489 }
 490
 491 void
 492 define_collsym(char *name)
 493 {
 494         collsym_t       *sym;
 495
 496         if ((sym = calloc(1, sizeof(*sym))) == NULL) {
 497                 fprintf(stderr,"out of memory");
 498                 return;
 499         }
 500         sym->name = name;
 501         sym->ref = new_pri();
 502
 503         if (RB_FIND(collsyms, &collsyms, sym) != NULL) {
 504                 /*
 505                  * This should never happen because we are only called
 506                  * for undefined symbols.
 507                  */
 508                 free(sym);
 509                 INTERR;
 510                 return;
 511         }
 512         RB_INSERT(collsyms, &collsyms, sym);
 513 }
 514
 515 collsym_t *
 516 lookup_collsym(char *name)
 517 {
 518         collsym_t       srch;
 519
 520         srch.name = name;
 521         return (RB_FIND(collsyms, &collsyms, &srch));
 522 }
 523
 524 collelem_t *
 525 lookup_collelem(char *symbol)
 526 {
 527         collelem_t      srch;
 528
 529         srch.symbol = symbol;
 530         return (RB_FIND(elem_by_symbol, &elem_by_symbol, &srch));
 531 }
 532
 533 static collundef_t *
 534 get_collundef(char *name)
 535 {
 536         collundef_t     srch;
 537         collundef_t     *ud;
 538         int             i;
 539
 540         srch.name = name;
 541         if ((ud = RB_FIND(collundefs, &collundefs, &srch)) == NULL) {
 542                 if (((ud = calloc(1, sizeof(*ud))) == NULL) ||
 543                     ((ud->name = strdup(name)) == NULL)) {
 544                         fprintf(stderr,"out of memory");
 545                         free(ud);
 546                         return (NULL);
 547                 }
 548                 for (i = 0; i < NUM_WT; i++) {
 549                         ud->ref[i] = new_pri();
 550                 }
 551                 RB_INSERT(collundefs, &collundefs, ud);
 552         }
 553         add_charmap_undefined(name);
 554         return (ud);
 555 }
 556
 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(1, sizeof(*cc))) == 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(1, sizeof(*e))) == 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                 free(e);
 821                 return;
 822         }
 823         RB_INSERT(elem_by_symbol, &elem_by_symbol, e);
 824         RB_INSERT(elem_by_expand, &elem_by_expand, e);
 825 }
 826
 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(1, sizeof(*s))) == 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(1, sizeof(*w))) == 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++ = htote(*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 through 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] = htote(COLLATE_MAX_PRIORITY);
1172                 }
1173                 collinfo.pri_count[i] = htote(nweight[i]);
1174         }
1175
1176         collinfo.pri_count[NUM_WT] = htote(max_wide());
1177         collinfo.undef_pri[NUM_WT] = htote(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] =
1187                                     htote(get_weight(cc->ref[j], j));
1188                         }
1189                 } else {
1190                         for (j = 0; j < NUM_WT; j++) {
1191                                 chars[i].pri[j] =
1192                                     htote(get_weight(pri_undefined[j], j));
1193                         }
1194                         /*
1195                          * Per POSIX, for undefined characters, we
1196                          * also have to add a last item, which is the
1197                          * character code.
1198                          */
1199                         chars[i].pri[NUM_WT] = htote(i);
1200                 }
1201         }
1202
1203         /*
1204          * Substitution tables
1205          */
1206         for (i = 0; i < NUM_WT; i++) {
1207                 collate_subst_t *st = NULL;
1208                 subst_t *temp;
1209                 RB_COUNT(temp, substs, &substs[i], n);
1210                 subst_count[i] = n;
1211                 if ((st = calloc(n, sizeof(collate_subst_t))) == NULL) {
1212                         fprintf(stderr, "out of memory");
1213                         return;
1214                 }
1215                 n = 0;
1216                 RB_FOREACH(sb, substs, &substs[i]) {
1217                         if ((st[n].key = resolve_pri(sb->key)) < 0) {
1218                                 /* by definition these resolve! */
1219                                 INTERR;
1220                         }
1221                         if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) {
1222                                 INTERR;
1223                         }
1224                         st[n].key = htote(st[n].key);
1225                         for (j = 0; sb->ref[j]; j++) {
1226                                 st[n].pri[j] = htote(get_weight(sb->ref[j],
1227                                     i));
1228                         }
1229                         n++;
1230                 }
1231                 if (n != subst_count[i])
1232                         INTERR;
1233                 subst[i] = st;
1234         }
1235
1236
1237         /*
1238          * Chains, i.e. collating elements
1239          */
1240         RB_NUMNODES(collelem_t, elem_by_expand, &elem_by_expand, chain_count);
1241         chain = calloc(chain_count, sizeof(collate_chain_t));
1242         if (chain == NULL) {
1243                 fprintf(stderr, "out of memory");
1244                 return;
1245         }
1246         n = 0;
1247         RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1248                 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
1249                 for (i = 0; i < NUM_WT; i++) {
1250                         chain[n].pri[i] = htote(get_weight(ce->ref[i], i));
1251                 }
1252                 n++;
1253         }
1254         if (n != chain_count)
1255                 INTERR;
1256
1257         /*
1258          * Large (> UCHAR_MAX) character priorities
1259          */
1260         RB_NUMNODES(collchar_t, collchars, &collchars, n);
1261         large = calloc(n, sizeof(collate_large_t));
1262         if (large == NULL) {
1263                 fprintf(stderr, "out of memory");
1264                 return;
1265         }
1266
1267         i = 0;
1268         RB_FOREACH(cc, collchars, &collchars) {
1269                 int     undef = 0;
1270                 /* we already gathered those */
1271                 if (cc->wc <= UCHAR_MAX)
1272                         continue;
1273                 for (j = 0; j < NUM_WT; j++) {
1274                         if ((pri = get_weight(cc->ref[j], j)) < 0) {
1275                                 undef = 1;
1276                         }
1277                         if (undef && (pri >= 0)) {
1278                                 /* if undefined, then all priorities are */
1279                                 INTERR;
1280                         } else {
1281                                 large[i].pri.pri[j] = htote(pri);
1282                         }
1283                 }
1284                 if (!undef) {
1285                         large[i].val = htote(cc->wc);
1286                         large_count = i++;
1287                 }
1288         }
1289
1290         if ((f = open_category()) == NULL) {
1291                 return;
1292         }
1293
1294         /* Time to write the entire data set out */
1295
1296         for (i = 0; i < NUM_WT; i++)
1297                 collinfo.subst_count[i] = htote(subst_count[i]);
1298         collinfo.chain_count = htote(chain_count);
1299         collinfo.large_count = htote(large_count);
1300
1301         if ((wr_category(vers, COLLATE_STR_LEN, f) < 0) ||
1302             (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
1303             (wr_category(&chars, sizeof (chars), f) < 0)) {
1304                 return;
1305         }
1306
1307         for (i = 0; i < NUM_WT; i++) {
1308                 sz = sizeof (collate_subst_t) * subst_count[i];
1309                 if (wr_category(subst[i], sz, f) < 0) {
1310                         return;
1311                 }
1312         }
1313         sz = sizeof (collate_chain_t) * chain_count;
1314         if (wr_category(chain, sz, f) < 0) {
1315                 return;
1316         }
1317         sz = sizeof (collate_large_t) * large_count;
1318         if (wr_category(large, sz, f) < 0) {
1319                 return;
1320         }
1321
1322         close_category(f);
1323 }