collate.c revision bc09504ff1ed70f84c9713b732281f14a9ef49b2
/*
* This file and its contents are supplied under the terms of the
* Common Development and Distribution License ("CDDL"), version 1.0.
* You may only use this file in accordance with the terms of version
* 1.0 of the CDDL.
*
* A full copy of the text of the CDDL should have accompanied this
* source. A copy of the CDDL is also available via the Internet at
*/
/*
* Copyright 2010 Nexenta Systems, Inc. All rights reserved.
*/
/*
* LC_COLLATE database generation routines for localedef.
*/
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <string.h>
#include <unistd.h>
#include <wchar.h>
#include <widec.h>
#include <limits.h>
#include "localedef.h"
#include "parser.tab.h"
#include "collatefile.h"
/*
* Design notes.
*
* It will be extremely helpful to the reader if they have access to
* the localedef and locale file format specifications available.
* Latest versions of these are available from www.opengroup.org.
*
* The design for the collation code is a bit complex. The goal is a
* single collation database as described in collate.h (in
*
* a) The substitution entries are now a directly indexable array. A
* priority elsewhere in the table is taken as an index into the
* substitution table if it has a high bit (COLLATE_SUBST_PRIORITY)
* set. (The bit is cleared and the result is the index into the
* table.
*
* b) We eliminate duplicate entries into the substitution table.
* This saves a lot of space.
*
* c) The priorities for each level are "compressed", so that each
* sorting level has consecutively numbered priorities starting at 1.
* (O is reserved for the ignore priority.) This means sort levels
* which only have a few distinct priorities can represent the
* priority level in fewer bits, which makes the strxfrm output
* smaller.
*
* d) We record the total number of priorities so that strxfrm can
* figure out how many bytes to expand a numeric priority into.
*
* e) For the UNDEFINED pass (the last pass), we record the maximum
* number of bits needed to uniquely prioritize these entries, so that
* the last pass can also use smaller strxfrm output when possible.
*
* f) Priorities with the sign bit set are verboten. This works out
* because no active character set needs that bit to carry significant
* information once the character is in wide form.
*
* To process the entire data to make the database, we actually run
* multiple passes over the data.
*
* The first pass, which is done at parse time, identifies elements,
* substitutions, and such, and records them in priority order. As
* some priorities can refer to other priorities, using forward
* references, we use a table of references indicating whether the
* priority's value has been resolved, or whether it is still a
* reference.
*
* The second pass walks over all the items in priority order, noting
* that they are used directly, and not just an indirect reference.
* This is done by creating a "weight" structure for the item. The
* weights are stashed in an AVL tree sorted by relative "priority".
*
* The third pass walks over all the weight structures, in priority
* order, and assigns a new monotonically increasing (per sort level)
* weight value to them. These are the values that will actually be
* written to the file.
*
* The fourth pass just writes the data out.
*/
/*
* In order to resolve the priorities, we create a table of priorities.
* Entries in the table can be in one of three states.
*
* UNKNOWN is for newly allocated entries, and indicates that nothing
* is known about the priority. (For example, when new entries are created
* for collating-symbols, this is the value assigned for them until the
* collating symbol's order has been determined.
*
* RESOLVED is used for an entry where the priority indicates the final
* numeric weight.
*
* REFER is used for entries that reference other entries. Typically
* this is used for forward references. A collating-symbol can never
* have this value.
*
* The "pass" field is used during final resolution to aid in detection
* of referencing loops. (For example <A> depends on <B>, but <B> has its
* priority dependent on <A>.)
*/
typedef enum {
UNKNOWN, /* priority is totally unknown */
RESOLVED, /* priority value fully resolved */
REFER /* priority is a reference (index) */
} res_t;
typedef struct weight {
int opt;
} weight_t;
typedef struct priority {
int pass;
int lineno;
} collpri_t;
/*
* These are the abstract collating symbols, which are just a symbolic
* way to reference a priority.
*/
struct collsym {
char *name;
};
/*
* These are also abstract collating symbols, but we allow them to have
* different priorities at different levels.
*/
typedef struct collundef {
char *name;
} collundef_t;
/*
* These are called "chains" in libc. This records the fact that two
* more characters should be treated as a single collating entity when
* they appear together. For example, in Spanish <C><h> gets collated
* as a character between <C> and <D>.
*/
struct collelem {
char *symbol;
};
/*
* Individual characters have a sequence of weights as well.
*/
typedef struct collchar {
} collchar_t;
/*
* Substitution entries. The key is itself a priority. Note that
* when we create one of these, we *automatically* wind up with a
* fully resolved priority for the key, because creation of
* substitutions creates a resolved priority at the same time.
*/
typedef struct {
} subst_t;
static avl_tree_t collsyms;
static avl_tree_t collundefs;
static avl_tree_t elem_by_symbol;
static avl_tree_t elem_by_expand;
static avl_tree_t collchars;
/*
* This is state tracking for the ellipsis token. Note that we start
* the initial values so that the ellipsis logic will think we got a
* magic starting value of NUL. It starts at minus one because the
* starting point is exclusive -- i.e. the starting point is not
* itself handled by the ellipsis code.
*/
static collelem_t *currelem;
static collchar_t *currchar;
static collundef_t *currundef;
static wchar_t ellipsis_start = 0;
/*
* We keep a running tally of weights.
*/
static int nextpri = 1;
static int nextsubst[COLL_WEIGHTS_MAX] = { 0 };
/*
* This array collects up the weights for each level.
*/
static int curr_weight = 0;
static int curr_subst = 0;
/*
* Some initial priority values.
*/
static int32_t pri_ignore;
static collate_info_t collinfo;
static int numpri = 0;
static int maxpri = 0;
static void start_order(int);
static int32_t
new_pri(void)
{
int i;
errf(_("out of memory"));
return (-1);
}
}
}
return (numpri++);
}
static collpri_t *
{
return (NULL);
}
}
static void
{
}
/* Resolve self references */
v = nextpri;
}
warn(_("repeated item in order list (first on %d)"),
return;
}
}
static int32_t
{
pass++;
/* report a line with the circular symbol */
errf(_("circular reference in order list"));
return (-1);
}
return (-1);
}
}
return (-1);
}
}
static int
{
}
static int
{
int rv;
}
static int
{
int rv;
}
static int
{
int rv;
}
static int
{
int rv;
}
static int
{
}
static int
{
}
static int
{
int rv;
}
void
init_collate(void)
{
int i;
for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
nweight[i] = 1;
}
/* allocate some initial priorities */
pri_ignore = new_pri();
for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
pri_undefined[i] = new_pri();
/* we will override this later */
}
}
void
define_collsym(char *name)
{
errf(_("out of memory"));
return;
}
/*
* This should never happen because we are only called
* for undefined symbols.
*/
return;
}
}
lookup_collsym(char *name)
{
}
lookup_collelem(char *symbol)
{
}
static collundef_t *
get_collundef(char *name)
{
int i;
errf(_("out of memory"));
return (NULL);
}
for (i = 0; i < NUM_WT; i++) {
}
}
return (ud);
}
static collchar_t *
{
collchar_t *cc;
int i;
errf(_("out of memory"));
return (NULL);
}
for (i = 0; i < NUM_WT; i++) {
}
}
return (cc);
}
void
{
/* update the weight */
nextpri++;
}
void
end_order(void)
{
int i;
collpri_t *p;
switch (currorder) {
case T_CHAR:
for (i = 0; i < NUM_WT; i++) {
if (((ref = order_weights[i]) < 0) ||
(p->pri == -1)) {
/* unspecified weight is a self reference */
} else {
}
order_weights[i] = -1;
}
/* leave a cookie trail in case next symbol is ellipsis */
break;
case T_ELLIPSIS:
/* save off the weights were we can find them */
for (i = 0; i < NUM_WT; i++) {
ellipsis_weights[i] = order_weights[i];
order_weights[i] = -1;
}
break;
case T_COLLELEM:
} else {
for (i = 0; i < NUM_WT; i++) {
if (((ref = order_weights[i]) < 0) ||
(p->pri == -1)) {
RESOLVED);
} else {
}
order_weights[i] = -1;
}
}
break;
case T_UNDEFINED:
for (i = 0; i < NUM_WT; i++) {
if (((ref = order_weights[i]) < 0) ||
(p->pri == -1)) {
} else {
}
order_weights[i] = -1;
}
break;
case T_SYMBOL:
for (i = 0; i < NUM_WT; i++) {
if (((ref = order_weights[i]) < 0) ||
(p->pri == -1)) {
} else {
}
order_weights[i] = -1;
}
break;
default:
}
nextpri++;
}
static void
start_order(int type)
{
int i;
/* this is used to protect ELLIPSIS processing */
errf(_("character value expected"));
}
for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
order_weights[i] = -1;
}
curr_weight = 0;
}
void
start_order_undefined(void)
{
}
void
start_order_symbol(char *name)
{
}
void
{
collchar_t *cc;
/*
* If we last saw an ellipsis, then we need to close the range.
* Handle that here. Note that we have to be careful because the
* items *inside* the range are treated exclusiveley to the items
* outside of the range. The ends of the range can have quite
* different weights than the range members.
*/
if (lastorder == T_ELLIPSIS) {
int i;
if (wc < ellipsis_start) {
errf(_("malformed range!"));
return;
}
while (ellipsis_start < wc) {
/*
* pick all of the saved weights for the
* ellipsis. note that -1 encodes for the
* ellipsis itself, which means to take the
* current relative priority.
*/
return;
}
for (i = 0; i < NUM_WT; i++) {
collpri_t *p;
(p->pri == -1)) {
} else {
}
ellipsis_weights[i] = 0;
}
nextpri++;
}
}
}
void
{
currelem = e;
}
void
start_order_ellipsis(void)
{
int i;
errf(_("illegal starting point for range"));
return;
}
for (i = 0; i < NUM_WT; i++) {
ellipsis_weights[i] = order_weights[i];
}
}
void
{
collelem_t *e;
int i;
errf(_("expanded collation element too long"));
return;
}
errf(_("out of memory"));
return;
}
/*
* This is executed before the order statement, so we don't
* know how many priorities we *really* need. We allocate one
* for each possible weight. Not a big deal, as collating-elements
* prove to be quite rare.
*/
for (i = 0; i < COLL_WEIGHTS_MAX; i++) {
}
/* A character sequence can only reduce to one element. */
errf(_("duplicate collating element definition"));
return;
}
}
void
add_order_bit(int kw)
{
switch (kw) {
case T_FORWARD:
break;
case T_BACKWARD:
break;
case T_POSITION:
break;
default:
break;
}
}
void
add_order_directive(void)
{
}
}
static void
{
if (curr_weight >= NUM_WT) {
return;
}
curr_weight++;
}
void
{
add_order_pri(s->ref);
}
void
{
collchar_t *cc;
return;
}
}
void
{
}
void
add_order_ignore(void)
{
}
void
add_order_symbol(char *sym)
{
collundef_t *c;
return;
}
}
void
add_order_ellipsis(void)
{
/* special 0 value indicates self reference */
add_order_pri(0);
}
void
add_order_subst(void)
{
subst_t *s;
int i;
for (i = 0; i < curr_subst; i++) {
subst_weights[i] = 0;
}
if (s == NULL) {
errf(_("out of memory"));
return;
}
/*
* We use a self reference for our key, but we set a
* high bit to indicate that this is a substitution
* reference. This will expedite table lookups later,
* and prevent table lookups for situations that don't
* require it. (In short, its a big win, because we
* can skip a lot of binary searching.)
*/
RESOLVED);
for (i = 0; i < curr_subst; i++) {
}
return;
}
}
curr_subst = 0;
/*
* We are using the current (unique) priority as a search key
* in the substitution table.
*/
add_order_pri(s->key);
}
static void
{
if (curr_subst >= COLLATE_STR_LEN) {
errf(_("substitution string is too long"));
return;
}
curr_subst++;
}
void
{
collchar_t *cc;
return;
}
/* we take the weight for the character at that position */
}
void
{
}
void
{
add_subst_pri(s->ref);
}
void
add_subst_symbol(char *ptr)
{
}
}
void
{
weight_t *w;
/* No translation of ignores */
return;
/* Substitution priorities are not weights */
return;
return;
errf(_("out of memory"));
return;
}
}
void
{
int i;
for (i = 0; i < NUM_WT; i++) {
add_weight(refs[i], i);
}
}
{
weight_t *w;
if (pri & COLLATE_SUBST_PRIORITY) {
return (pri);
}
if (pri <= 0) {
return (pri);
}
return (-1);
}
return (w->opt);
}
void
dump_collate(void)
{
FILE *f;
int i, j, n;
collelem_t *ce;
collchar_t *cc;
char vers[COLLATE_STR_LEN];
/*
* We have to run throught a preliminary pass to identify all the
* weights that we use for each sorting level.
*/
for (i = 0; i < NUM_WT; i++) {
add_weight(pri_ignore, i);
}
for (i = 0; i < NUM_WT; i++) {
}
}
}
}
}
/*
* Now we walk the entire set of weights, removing the gaps
* in the weights. This gives us optimum usage. The walk
* occurs in priority.
*/
for (i = 0; i < NUM_WT; i++) {
weight_t *w;
nweight[i] += 1;
}
}
/*
* We need to make sure we arrange for the UNDEFINED field
* to show up. Also, set the total weight counts.
*/
for (i = 0; i < NUM_WT; i++) {
/* they collate at the end of everything else */
}
}
/*
* Ordinary character priorities
*/
for (i = 0; i <= UCHAR_MAX; i++) {
for (j = 0; j < NUM_WT; j++) {
}
} else {
for (j = 0; j < NUM_WT; j++) {
get_weight(pri_undefined[j], j);
}
/*
* Per POSIX, for undefined characters, we
* also have to add a last item, which is the
* character code.
*/
}
}
/*
* Substitution tables
*/
for (i = 0; i < NUM_WT; i++) {
errf(_("out of memory"));
return;
}
n = 0;
/* by definition these resolve! */
}
}
}
n++;
}
if (n != collinfo.subst_count[i])
}
/*
* Chains, i.e. collating elements
*/
errf(_("out of memory"));
return;
}
for (i = 0; i < NUM_WT; i++) {
}
}
if (n != collinfo.chain_count)
/*
* Large (> UCHAR_MAX) character priorities
*/
errf(_("out of memory"));
return;
}
i = 0;
int undef = 0;
/* we already gathered those */
continue;
for (j = 0; j < NUM_WT; j++) {
undef = 1;
}
/* if undefined, then all priorities are */
} else {
}
}
if (!undef) {
collinfo.large_count = i++;
}
}
if ((f = open_category()) == NULL) {
return;
}
/* Time to write the entire data set out */
return;
}
for (i = 0; i < NUM_WT; i++) {
return;
}
}
return;
}
return;
}
close_category(f);
}