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
new_pri(void)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 *
get_pri(int32_t ref)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
set_pri(int32_t ref,int32_t v,res_t res)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
resolve_pri(int32_t ref)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
weight_compare(const void * n1,const void * n2)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
collsym_compare(const void * n1,const void * n2)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
collundef_compare(const void * n1,const void * n2)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
element_compare_symbol(const void * n1,const void * n2)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
element_compare_expand(const void * n1,const void * n2)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
collchar_compare(const void * n1,const void * n2)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
subst_compare(const void * n1,const void * n2)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
subst_compare_ref(const void * n1,const void * n2)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
init_collate(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
define_collsym(char * name)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 *
lookup_collsym(char * name)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 *
lookup_collelem(char * symbol)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 *
get_collundef(char * name)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 *
get_collchar(wchar_t wc,int create)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
end_order_collsym(collsym_t * sym)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
end_order(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
start_order(int type)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
start_order_undefined(void)701 start_order_undefined(void)
702 {
703 start_order(T_UNDEFINED);
704 }
705
706 void
start_order_symbol(char * name)707 start_order_symbol(char *name)
708 {
709 currundef = get_collundef(name);
710 start_order(T_SYMBOL);
711 }
712
713 void
start_order_char(wchar_t wc)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
start_order_collelem(collelem_t * e)766 start_order_collelem(collelem_t *e)
767 {
768 start_order(T_COLLELEM);
769 currelem = e;
770 }
771
772 void
start_order_ellipsis(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
define_collelem(char * name,wchar_t * wcs)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
add_order_bit(int kw)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
add_order_directive(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
add_order_pri(int32_t ref)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
add_order_collsym(collsym_t * s)870 add_order_collsym(collsym_t *s)
871 {
872 add_order_pri(s->ref);
873 }
874
875 void
add_order_char(wchar_t wc)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
add_order_collelem(collelem_t * e)889 add_order_collelem(collelem_t *e)
890 {
891 add_order_pri(e->ref[curr_weight]);
892 }
893
894 void
add_order_ignore(void)895 add_order_ignore(void)
896 {
897 add_order_pri(pri_ignore);
898 }
899
900 void
add_order_symbol(char * sym)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
add_order_ellipsis(void)912 add_order_ellipsis(void)
913 {
914 /* special NULL value indicates self reference */
915 add_order_pri(0);
916 }
917
918 void
add_order_subst(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
add_subst_pri(int32_t ref)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
add_subst_char(wchar_t wc)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
add_subst_collelem(collelem_t * e)1001 add_subst_collelem(collelem_t *e)
1002 {
1003 add_subst_pri(e->ref[curr_weight]);
1004 }
1005
1006 void
add_subst_collsym(collsym_t * s)1007 add_subst_collsym(collsym_t *s)
1008 {
1009 add_subst_pri(s->ref);
1010 }
1011
1012 void
add_subst_symbol(char * ptr)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
add_weight(int32_t ref,int pass)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
add_weights(int32_t * refs)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
get_weight(int32_t ref,int pass)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 *
wsncpy(wchar_t * s1,const wchar_t * s2,size_t n)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
dump_collate(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 }
1317