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
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 _Static_assert(COLL_WEIGHTS_MAX == 10, "This code assumes a value of 10");
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
new_pri(void)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\n");
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 *
get_pri(int32_t ref)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
set_pri(int32_t ref,int32_t v,res_t res)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
resolve_pri(int32_t ref)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\n");
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
weight_compare(const void * n1,const void * n2)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
collsym_compare(const void * n1,const void * n2)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
collundef_compare(const void * n1,const void * n2)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
element_compare_symbol(const void * n1,const void * n2)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
element_compare_expand(const void * n1,const void * n2)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
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 (wchar_cmp(k1, k2));
426 }
427
428 RB_GENERATE_STATIC(collchars, collchar, entry, collchar_compare);
429
430 static int
subst_compare(const void * n1,const void * n2)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
subst_compare_ref(const void * n1,const void * n2)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
init_collate(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
define_collsym(char * name)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\n");
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 *
lookup_collsym(char * name)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 *
lookup_collelem(char * symbol)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 *
get_collundef(char * name)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\n");
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 *
get_collchar(wchar_t wc,int create)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\n");
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
end_order_collsym(collsym_t * sym)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
end_order(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
start_order(int type)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\n");
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
start_order_undefined(void)700 start_order_undefined(void)
701 {
702 start_order(T_UNDEFINED);
703 }
704
705 void
start_order_symbol(char * name)706 start_order_symbol(char *name)
707 {
708 currundef = get_collundef(name);
709 start_order(T_SYMBOL);
710 }
711
712 void
start_order_char(wchar_t wc)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!\n");
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
start_order_collelem(collelem_t * e)765 start_order_collelem(collelem_t *e)
766 {
767 start_order(T_COLLELEM);
768 currelem = e;
769 }
770
771 void
start_order_ellipsis(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\n");
780 return;
781 }
782
783 for (i = 0; i < NUM_WT; i++) {
784 ellipsis_weights[i] = order_weights[i];
785 }
786 }
787
788 void
define_collelem(char * name,wchar_t * wcs)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\n");
796 return;
797 }
798
799 if ((e = calloc(1, sizeof(*e))) == NULL) {
800 fprintf(stderr, "out of memory\n");
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\n");
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
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)\n", COLL_WEIGHTS_MAX);
854 return;
855 }
856 collinfo.directive_count++;
857 }
858
859 static void
add_order_pri(int32_t ref)860 add_order_pri(int32_t ref)
861 {
862 if (curr_weight >= NUM_WT) {
863 fprintf(stderr, "too many weights (max %d)\n", NUM_WT);
864 return;
865 }
866 order_weights[curr_weight] = ref;
867 curr_weight++;
868 }
869
870 void
add_order_collsym(collsym_t * s)871 add_order_collsym(collsym_t *s)
872 {
873 add_order_pri(s->ref);
874 }
875
876 void
add_order_char(wchar_t wc)877 add_order_char(wchar_t wc)
878 {
879 collchar_t *cc;
880
881 if ((cc = get_collchar(wc, 1)) == NULL) {
882 INTERR;
883 return;
884 }
885
886 add_order_pri(cc->ref[curr_weight]);
887 }
888
889 void
add_order_collelem(collelem_t * e)890 add_order_collelem(collelem_t *e)
891 {
892 add_order_pri(e->ref[curr_weight]);
893 }
894
895 void
add_order_ignore(void)896 add_order_ignore(void)
897 {
898 add_order_pri(pri_ignore);
899 }
900
901 void
add_order_symbol(char * sym)902 add_order_symbol(char *sym)
903 {
904 collundef_t *c;
905 if ((c = get_collundef(sym)) == NULL) {
906 INTERR;
907 return;
908 }
909 add_order_pri(c->ref[curr_weight]);
910 }
911
912 void
add_order_ellipsis(void)913 add_order_ellipsis(void)
914 {
915 /* special NULL value indicates self reference */
916 add_order_pri(0);
917 }
918
919 void
add_order_subst(void)920 add_order_subst(void)
921 {
922 subst_t srch;
923 subst_t *s;
924 int i;
925
926 (void) memset(&srch, 0, sizeof (srch));
927 for (i = 0; i < curr_subst; i++) {
928 srch.ref[i] = subst_weights[i];
929 subst_weights[i] = 0;
930 }
931 s = RB_FIND(substs_ref, &substs_ref[curr_weight], &srch);
932
933 if (s == NULL) {
934 if ((s = calloc(1, sizeof(*s))) == NULL) {
935 fprintf(stderr,"out of memory\n");
936 return;
937 }
938 s->key = new_pri();
939
940 /*
941 * We use a self reference for our key, but we set a
942 * high bit to indicate that this is a substitution
943 * reference. This will expedite table lookups later,
944 * and prevent table lookups for situations that don't
945 * require it. (In short, its a big win, because we
946 * can skip a lot of binary searching.)
947 */
948 set_pri(s->key,
949 (nextsubst[curr_weight] | COLLATE_SUBST_PRIORITY),
950 RESOLVED);
951 nextsubst[curr_weight] += 1;
952
953 for (i = 0; i < curr_subst; i++) {
954 s->ref[i] = srch.ref[i];
955 }
956
957 RB_INSERT(substs_ref, &substs_ref[curr_weight], s);
958
959 if (RB_FIND(substs, &substs[curr_weight], s) != NULL) {
960 INTERR;
961 return;
962 }
963 RB_INSERT(substs, &substs[curr_weight], s);
964 }
965 curr_subst = 0;
966
967
968 /*
969 * We are using the current (unique) priority as a search key
970 * in the substitution table.
971 */
972 add_order_pri(s->key);
973 }
974
975 static void
add_subst_pri(int32_t ref)976 add_subst_pri(int32_t ref)
977 {
978 if (curr_subst >= COLLATE_STR_LEN) {
979 fprintf(stderr,"substitution string is too long\n");
980 return;
981 }
982 subst_weights[curr_subst] = ref;
983 curr_subst++;
984 }
985
986 void
add_subst_char(wchar_t wc)987 add_subst_char(wchar_t wc)
988 {
989 collchar_t *cc;
990
991
992 if (((cc = get_collchar(wc, 1)) == NULL) ||
993 (cc->wc != wc)) {
994 INTERR;
995 return;
996 }
997 /* we take the weight for the character at that position */
998 add_subst_pri(cc->ref[curr_weight]);
999 }
1000
1001 void
add_subst_collelem(collelem_t * e)1002 add_subst_collelem(collelem_t *e)
1003 {
1004 add_subst_pri(e->ref[curr_weight]);
1005 }
1006
1007 void
add_subst_collsym(collsym_t * s)1008 add_subst_collsym(collsym_t *s)
1009 {
1010 add_subst_pri(s->ref);
1011 }
1012
1013 void
add_subst_symbol(char * ptr)1014 add_subst_symbol(char *ptr)
1015 {
1016 collundef_t *cu;
1017
1018 if ((cu = get_collundef(ptr)) != NULL) {
1019 add_subst_pri(cu->ref[curr_weight]);
1020 }
1021 }
1022
1023 void
add_weight(int32_t ref,int pass)1024 add_weight(int32_t ref, int pass)
1025 {
1026 weight_t srch;
1027 weight_t *w;
1028
1029 srch.pri = resolve_pri(ref);
1030
1031 /* No translation of ignores */
1032 if (srch.pri == 0)
1033 return;
1034
1035 /* Substitution priorities are not weights */
1036 if (srch.pri & COLLATE_SUBST_PRIORITY)
1037 return;
1038
1039 if (RB_FIND(weights, &weights[pass], &srch) != NULL)
1040 return;
1041
1042 if ((w = calloc(1, sizeof(*w))) == NULL) {
1043 fprintf(stderr, "out of memory\n");
1044 return;
1045 }
1046 w->pri = srch.pri;
1047 RB_INSERT(weights, &weights[pass], w);
1048 }
1049
1050 void
add_weights(int32_t * refs)1051 add_weights(int32_t *refs)
1052 {
1053 int i;
1054 for (i = 0; i < NUM_WT; i++) {
1055 add_weight(refs[i], i);
1056 }
1057 }
1058
1059 int32_t
get_weight(int32_t ref,int pass)1060 get_weight(int32_t ref, int pass)
1061 {
1062 weight_t srch;
1063 weight_t *w;
1064 int32_t pri;
1065
1066 pri = resolve_pri(ref);
1067 if (pri & COLLATE_SUBST_PRIORITY) {
1068 return (pri);
1069 }
1070 if (pri <= 0) {
1071 return (pri);
1072 }
1073 srch.pri = pri;
1074 if ((w = RB_FIND(weights, &weights[pass], &srch)) == NULL) {
1075 INTERR;
1076 return (-1);
1077 }
1078 return (w->opt);
1079 }
1080
1081 wchar_t *
wsncpy(wchar_t * s1,const wchar_t * s2,size_t n)1082 wsncpy(wchar_t *s1, const wchar_t *s2, size_t n)
1083 {
1084 wchar_t *os1 = s1;
1085
1086 n++;
1087 while (--n > 0 && (*s1++ = htote(*s2++)) != 0)
1088 continue;
1089 if (n > 0)
1090 while (--n > 0)
1091 *s1++ = 0;
1092 return (os1);
1093 }
1094
1095 #define RB_COUNT(x, name, head, cnt) do { \
1096 (cnt) = 0; \
1097 RB_FOREACH(x, name, (head)) { \
1098 (cnt)++; \
1099 } \
1100 } while (0)
1101
1102 #define RB_NUMNODES(type, name, head, cnt) do { \
1103 type *t; \
1104 cnt = 0; \
1105 RB_FOREACH(t, name, head) { \
1106 cnt++; \
1107 } \
1108 } while (0)
1109
1110 void
dump_collate(void)1111 dump_collate(void)
1112 {
1113 FILE *f;
1114 int i, j, n;
1115 size_t sz;
1116 int32_t pri;
1117 collelem_t *ce;
1118 collchar_t *cc;
1119 subst_t *sb;
1120 char fmt_version[COLLATE_FMT_VERSION_LEN];
1121 char def_version[XLOCALE_DEF_VERSION_LEN];
1122 collate_char_t chars[UCHAR_MAX + 1];
1123 collate_large_t *large;
1124 collate_subst_t *subst[COLL_WEIGHTS_MAX];
1125 collate_chain_t *chain;
1126
1127 /*
1128 * We have to run through a preliminary pass to identify all the
1129 * weights that we use for each sorting level.
1130 */
1131 for (i = 0; i < NUM_WT; i++) {
1132 add_weight(pri_ignore, i);
1133 }
1134 for (i = 0; i < NUM_WT; i++) {
1135 RB_FOREACH(sb, substs, &substs[i]) {
1136 for (j = 0; sb->ref[j]; j++) {
1137 add_weight(sb->ref[j], i);
1138 }
1139 }
1140 }
1141 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1142 add_weights(ce->ref);
1143 }
1144 RB_FOREACH(cc, collchars, &collchars) {
1145 add_weights(cc->ref);
1146 }
1147
1148 /*
1149 * Now we walk the entire set of weights, removing the gaps
1150 * in the weights. This gives us optimum usage. The walk
1151 * occurs in priority.
1152 */
1153 for (i = 0; i < NUM_WT; i++) {
1154 weight_t *w;
1155 RB_FOREACH(w, weights, &weights[i]) {
1156 w->opt = nweight[i];
1157 nweight[i] += 1;
1158 }
1159 }
1160
1161 (void) memset(&chars, 0, sizeof (chars));
1162 (void) memset(fmt_version, 0, COLLATE_FMT_VERSION_LEN);
1163 (void) strlcpy(fmt_version, COLLATE_FMT_VERSION, sizeof (fmt_version));
1164 (void) memset(def_version, 0, XLOCALE_DEF_VERSION_LEN);
1165 if (version)
1166 (void) strlcpy(def_version, version, sizeof (def_version));
1167
1168 /*
1169 * We need to make sure we arrange for the UNDEFINED field
1170 * to show up. Also, set the total weight counts.
1171 */
1172 for (i = 0; i < NUM_WT; i++) {
1173 if (resolve_pri(pri_undefined[i]) == -1) {
1174 set_pri(pri_undefined[i], -1, RESOLVED);
1175 /* they collate at the end of everything else */
1176 collinfo.undef_pri[i] = htote(COLLATE_MAX_PRIORITY);
1177 }
1178 collinfo.pri_count[i] = htote(nweight[i]);
1179 }
1180
1181 collinfo.pri_count[NUM_WT] = htote(max_wide());
1182 collinfo.undef_pri[NUM_WT] = htote(COLLATE_MAX_PRIORITY);
1183 collinfo.directive[NUM_WT] = DIRECTIVE_UNDEFINED;
1184
1185 /*
1186 * Ordinary character priorities
1187 */
1188 for (i = 0; i <= UCHAR_MAX; i++) {
1189 if ((cc = get_collchar(i, 0)) != NULL) {
1190 for (j = 0; j < NUM_WT; j++) {
1191 chars[i].pri[j] =
1192 htote(get_weight(cc->ref[j], j));
1193 }
1194 } else {
1195 for (j = 0; j < NUM_WT; j++) {
1196 chars[i].pri[j] =
1197 htote(get_weight(pri_undefined[j], j));
1198 }
1199 /*
1200 * Per POSIX, for undefined characters, we
1201 * also have to add a last item, which is the
1202 * character code.
1203 */
1204 chars[i].pri[NUM_WT] = htote(i);
1205 }
1206 }
1207
1208 /*
1209 * Substitution tables
1210 */
1211 for (i = 0; i < NUM_WT; i++) {
1212 collate_subst_t *st = NULL;
1213 subst_t *temp;
1214 RB_COUNT(temp, substs, &substs[i], n);
1215 subst_count[i] = n;
1216 if ((st = calloc(n, sizeof(collate_subst_t))) == NULL) {
1217 fprintf(stderr, "out of memory\n");
1218 return;
1219 }
1220 n = 0;
1221 RB_FOREACH(sb, substs, &substs[i]) {
1222 if ((st[n].key = resolve_pri(sb->key)) < 0) {
1223 /* by definition these resolve! */
1224 INTERR;
1225 }
1226 if (st[n].key != (n | COLLATE_SUBST_PRIORITY)) {
1227 INTERR;
1228 }
1229 st[n].key = htote(st[n].key);
1230 for (j = 0; sb->ref[j]; j++) {
1231 st[n].pri[j] = htote(get_weight(sb->ref[j],
1232 i));
1233 }
1234 n++;
1235 }
1236 if (n != subst_count[i])
1237 INTERR;
1238 subst[i] = st;
1239 }
1240
1241
1242 /*
1243 * Chains, i.e. collating elements
1244 */
1245 RB_NUMNODES(collelem_t, elem_by_expand, &elem_by_expand, chain_count);
1246 chain = calloc(chain_count, sizeof(collate_chain_t));
1247 if (chain == NULL) {
1248 fprintf(stderr, "out of memory\n");
1249 return;
1250 }
1251 n = 0;
1252 RB_FOREACH(ce, elem_by_expand, &elem_by_expand) {
1253 (void) wsncpy(chain[n].str, ce->expand, COLLATE_STR_LEN);
1254 for (i = 0; i < NUM_WT; i++) {
1255 chain[n].pri[i] = htote(get_weight(ce->ref[i], i));
1256 }
1257 n++;
1258 }
1259 if (n != chain_count)
1260 INTERR;
1261
1262 /*
1263 * Large (> UCHAR_MAX) character priorities
1264 */
1265 RB_NUMNODES(collchar_t, collchars, &collchars, n);
1266 large = calloc(n, sizeof(collate_large_t));
1267 if (large == NULL) {
1268 fprintf(stderr, "out of memory\n");
1269 return;
1270 }
1271
1272 i = 0;
1273 RB_FOREACH(cc, collchars, &collchars) {
1274 int undef = 0;
1275 /* we already gathered those */
1276 if ((uint32_t)cc->wc <= UCHAR_MAX)
1277 continue;
1278 for (j = 0; j < NUM_WT; j++) {
1279 if ((pri = get_weight(cc->ref[j], j)) < 0) {
1280 undef = 1;
1281 }
1282 if (undef && (pri >= 0)) {
1283 /* if undefined, then all priorities are */
1284 INTERR;
1285 } else {
1286 large[i].pri.pri[j] = htote(pri);
1287 }
1288 }
1289 if (!undef) {
1290 large[i].val = htote(cc->wc);
1291 large_count = i++;
1292 }
1293 }
1294
1295 if ((f = open_category()) == NULL) {
1296 return;
1297 }
1298
1299 /* Time to write the entire data set out */
1300
1301 for (i = 0; i < NUM_WT; i++)
1302 collinfo.subst_count[i] = htote(subst_count[i]);
1303 collinfo.chain_count = htote(chain_count);
1304 collinfo.large_count = htote(large_count);
1305
1306 if ((wr_category(fmt_version, COLLATE_FMT_VERSION_LEN, f) < 0) ||
1307 (wr_category(def_version, XLOCALE_DEF_VERSION_LEN, f) < 0) ||
1308 (wr_category(&collinfo, sizeof (collinfo), f) < 0) ||
1309 (wr_category(&chars, sizeof (chars), f) < 0)) {
1310 return;
1311 }
1312
1313 for (i = 0; i < NUM_WT; i++) {
1314 sz = sizeof (collate_subst_t) * subst_count[i];
1315 if (wr_category(subst[i], sz, f) < 0) {
1316 return;
1317 }
1318 }
1319 sz = sizeof (collate_chain_t) * chain_count;
1320 if (wr_category(chain, sz, f) < 0) {
1321 return;
1322 }
1323 sz = sizeof (collate_large_t) * large_count;
1324 if (wr_category(large, sz, f) < 0) {
1325 return;
1326 }
1327
1328 close_category(f);
1329 }
1330