/*
* colorings of characters
* This file is #included by regcomp.c.
*
* Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
*
* Development of this software was funded, in part, by Cray Research Inc.,
* UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
* Corporation, none of whom are responsible for the results. The author
* thanks all of them.
*
* Redistribution and use in source and binary forms -- with or without
* modification -- are permitted for any purpose, provided that
* redistributions in source form retain this entire copyright notice and
* indicate the origin and nature of any modifications.
*
* I'd appreciate being given credit for this package in the documentation
* of software which uses it, but that is not a requirement.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
* HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*
*
* Note that there are some incestuous relationships between this code and
* NFA arc maintenance, which perhaps ought to be cleaned up sometime.
*/
#define CISERR() VISERR(cm->v)
#define CERR(e) VERR(cm->v, (e))
/*
- initcm - set up new colormap
^ static VOID initcm(struct vars *, struct colormap *);
*/
static VOID
initcm(v, cm)
struct vars *v;
struct colormap *cm;
{
int i;
int j;
union tree *t;
union tree *nextt;
struct colordesc *cd;
cm->magic = CMMAGIC;
cm->v = v;
cm->ncds = NINLINECDS;
cm->cd = cm->cdspace;
cm->max = 0;
cm->free = 0;
cd = cm->cd; /* cm->cd[WHITE] */
cd->sub = NOSUB;
cd->arcs = NULL;
cd->flags = 0;
cd->nchrs = CHR_MAX - CHR_MIN + 1;
/* upper levels of tree */
for (t = &cm->tree[0], j = NBYTS-1; j > 0; t = nextt, j--) {
nextt = t + 1;
for (i = BYTTAB-1; i >= 0; i--)
t->tptr[i] = nextt;
}
/* bottom level is solid white */
t = &cm->tree[NBYTS-1];
for (i = BYTTAB-1; i >= 0; i--)
t->tcolor[i] = WHITE;
cd->block = t;
}
/*
- freecm - free dynamically-allocated things in a colormap
^ static VOID freecm(struct colormap *);
*/
static VOID
freecm(cm)
struct colormap *cm;
{
size_t i;
union tree *cb;
cm->magic = 0;
if (NBYTS > 1)
cmtreefree(cm, cm->tree, 0);
for (i = 1; i <= cm->max; i++) /* skip WHITE */
if (!UNUSEDCOLOR(&cm->cd[i])) {
cb = cm->cd[i].block;
if (cb != NULL)
FREE(cb);
}
if (cm->cd != cm->cdspace)
FREE(cm->cd);
}
/*
- cmtreefree - free a non-terminal part of a colormap tree
^ static VOID cmtreefree(struct colormap *, union tree *, int);
*/
static VOID
cmtreefree(cm, tree, level)
struct colormap *cm;
union tree *tree;
int level; /* level number (top == 0) of this block */
{
int i;
union tree *t;
union tree *fillt = &cm->tree[level+1];
union tree *cb;
assert(level < NBYTS-1); /* this level has pointers */
for (i = BYTTAB-1; i >= 0; i--) {
t = tree->tptr[i];
assert(t != NULL);
if (t != fillt) {
if (level < NBYTS-2) { /* more pointer blocks below */
cmtreefree(cm, t, level+1);
FREE(t);
} else { /* color block below */
cb = cm->cd[t->tcolor[0]].block;
if (t != cb) /* not a solid block */
FREE(t);
}
}
}
}
/*
- setcolor - set the color of a character in a colormap
^ static color setcolor(struct colormap *, pchr, pcolor);
*/
static color /* previous color */
setcolor(cm, c, co)
struct colormap *cm;
pchr c;
pcolor co;
{
uchr uc = c;
int shift;
int level;
int b;
int bottom;
union tree *t;
union tree *newt;
union tree *fillt;
union tree *lastt;
union tree *cb;
color prev;
assert(cm->magic == CMMAGIC);
if (CISERR() || co == COLORLESS)
return COLORLESS;
t = cm->tree;
for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
level++, shift -= BYTBITS) {
b = (uc >> shift) & BYTMASK;
lastt = t;
t = lastt->tptr[b];
assert(t != NULL);
fillt = &cm->tree[level+1];
bottom = (shift <= BYTBITS) ? 1 : 0;
cb = (bottom) ? cm->cd[t->tcolor[0]].block : fillt;
if (t == fillt || t == cb) { /* must allocate a new block */
newt = (union tree *)MALLOC((bottom) ?
sizeof(struct colors) : sizeof(struct ptrs));
if (newt == NULL) {
CERR(REG_ESPACE);
return COLORLESS;
}
if (bottom)
memcpy(VS(newt->tcolor), VS(t->tcolor),
BYTTAB*sizeof(color));
else
memcpy(VS(newt->tptr), VS(t->tptr),
BYTTAB*sizeof(union tree *));
t = newt;
lastt->tptr[b] = t;
}
}
b = uc & BYTMASK;
prev = t->tcolor[b];
t->tcolor[b] = (color)co;
return prev;
}
/*
- maxcolor - report largest color number in use
^ static color maxcolor(struct colormap *);
*/
static color
maxcolor(cm)
struct colormap *cm;
{
if (CISERR())
return COLORLESS;
return (color)cm->max;
}
/*
- newcolor - find a new color (must be subject of setcolor at once)
* Beware: may relocate the colordescs.
^ static color newcolor(struct colormap *);
*/
static color /* COLORLESS for error */
newcolor(cm)
struct colormap *cm;
{
struct colordesc *cd;
struct colordesc *new;
size_t n;
if (CISERR())
return COLORLESS;
if (cm->free != 0) {
assert(cm->free > 0);
assert((size_t)cm->free < cm->ncds);
cd = &cm->cd[cm->free];
assert(UNUSEDCOLOR(cd));
assert(cd->arcs == NULL);
cm->free = cd->sub;
} else if (cm->max < cm->ncds - 1) {
cm->max++;
cd = &cm->cd[cm->max];
} else {
/* oops, must allocate more */
n = cm->ncds * 2;
if (cm->cd == cm->cdspace) {
new = (struct colordesc *)MALLOC(n *
sizeof(struct colordesc));
if (new != NULL)
memcpy(VS(new), VS(cm->cdspace), cm->ncds *
sizeof(struct colordesc));
} else
new = (struct colordesc *)REALLOC(cm->cd,
n * sizeof(struct colordesc));
if (new == NULL) {
CERR(REG_ESPACE);
return COLORLESS;
}
cm->cd = new;
cm->ncds = n;
assert(cm->max < cm->ncds - 1);
cm->max++;
cd = &cm->cd[cm->max];
}
cd->nchrs = 0;
cd->sub = NOSUB;
cd->arcs = NULL;
cd->flags = 0;
cd->block = NULL;
return (color)(cd - cm->cd);
}
/*
- freecolor - free a color (must have no arcs or subcolor)
^ static VOID freecolor(struct colormap *, pcolor);
*/
static VOID
freecolor(cm, co)
struct colormap *cm;
pcolor co;
{
struct colordesc *cd = &cm->cd[co];
color pco, nco; /* for freelist scan */
assert(co >= 0);
if (co == WHITE)
return;
assert(cd->arcs == NULL);
assert(cd->sub == NOSUB);
assert(cd->nchrs == 0);
cd->flags = FREECOL;
if (cd->block != NULL) {
FREE(cd->block);
cd->block = NULL; /* just paranoia */
}
if ((size_t)co == cm->max) {
while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
cm->max--;
assert(cm->free >= 0);
while ((size_t)cm->free > cm->max)
cm->free = cm->cd[cm->free].sub;
if (cm->free > 0) {
assert(cm->free < cm->max);
pco = cm->free;
nco = cm->cd[pco].sub;
while (nco > 0)
if ((size_t)nco > cm->max) {
/* take this one out of freelist */
nco = cm->cd[nco].sub;
cm->cd[pco].sub = nco;
} else {
assert(nco < cm->max);
pco = nco;
nco = cm->cd[pco].sub;
}
}
} else {
cd->sub = cm->free;
cm->free = (color)(cd - cm->cd);
}
}
/*
- pseudocolor - allocate a false color, to be managed by other means
^ static color pseudocolor(struct colormap *);
*/
static color
pseudocolor(cm)
struct colormap *cm;
{
color co;
co = newcolor(cm);
if (CISERR())
return COLORLESS;
cm->cd[co].nchrs = 1;
cm->cd[co].flags = PSEUDO;
return co;
}
/*
- subcolor - allocate a new subcolor (if necessary) to this chr
^ static color subcolor(struct colormap *, pchr c);
*/
static color
subcolor(cm, c)
struct colormap *cm;
pchr c;
{
color co; /* current color of c */
color sco; /* new subcolor */
co = GETCOLOR(cm, c);
sco = newsub(cm, co);
if (CISERR())
return COLORLESS;
assert(sco != COLORLESS);
if (co == sco) /* already in an open subcolor */
return co; /* rest is redundant */
cm->cd[co].nchrs--;
cm->cd[sco].nchrs++;
setcolor(cm, c, sco);
return sco;
}
/*
- newsub - allocate a new subcolor (if necessary) for a color
^ static color newsub(struct colormap *, pcolor);
*/
static color
newsub(cm, co)
struct colormap *cm;
pcolor co;
{
color sco; /* new subcolor */
sco = cm->cd[co].sub;
if (sco == NOSUB) { /* color has no open subcolor */
if (cm->cd[co].nchrs == 1) /* optimization */
return co;
sco = newcolor(cm); /* must create subcolor */
if (sco == COLORLESS) {
assert(CISERR());
return COLORLESS;
}
cm->cd[co].sub = sco;
cm->cd[sco].sub = sco; /* open subcolor points to self */
}
assert(sco != NOSUB);
return sco;
}
/*
- subrange - allocate new subcolors to this range of chrs, fill in arcs
^ static VOID subrange(struct vars *, pchr, pchr, struct state *,
^ struct state *);
*/
static VOID
subrange(v, from, to, lp, rp)
struct vars *v;
pchr from;
pchr to;
struct state *lp;
struct state *rp;
{
uchr uf;
int i;
assert(from <= to);
/* first, align "from" on a tree-block boundary */
uf = (uchr)from;
i = (int)( ((uf + BYTTAB-1) & (uchr)~BYTMASK) - uf );
for (; from <= to && i > 0; i--, from++)
newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
if (from > to) /* didn't reach a boundary */
return;
/* deal with whole blocks */
for (; to - from >= BYTTAB; from += BYTTAB)
subblock(v, from, lp, rp);
/* clean up any remaining partial table */
for (; from <= to; from++)
newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
}
/*
- subblock - allocate new subcolors for one tree block of chrs, fill in arcs
^ static VOID subblock(struct vars *, pchr, struct state *, struct state *);
*/
static VOID
subblock(v, start, lp, rp)
struct vars *v;
pchr start; /* first of BYTTAB chrs */
struct state *lp;
struct state *rp;
{
uchr uc = start;
struct colormap *cm = v->cm;
int shift;
int level;
int i;
int b;
union tree *t;
union tree *cb;
union tree *fillt;
union tree *lastt;
int previ;
int ndone;
color co;
color sco;
assert((uc % BYTTAB) == 0);
/* find its color block, making new pointer blocks as needed */
t = cm->tree;
fillt = NULL;
for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
level++, shift -= BYTBITS) {
b = (uc >> shift) & BYTMASK;
lastt = t;
t = lastt->tptr[b];
assert(t != NULL);
fillt = &cm->tree[level+1];
if (t == fillt && shift > BYTBITS) { /* need new ptr block */
t = (union tree *)MALLOC(sizeof(struct ptrs));
if (t == NULL) {
CERR(REG_ESPACE);
return;
}
memcpy(VS(t->tptr), VS(fillt->tptr),
BYTTAB*sizeof(union tree *));
lastt->tptr[b] = t;
}
}
/* special cases: fill block or solid block */
co = t->tcolor[0];
cb = cm->cd[co].block;
if (t == fillt || t == cb) {
/* either way, we want a subcolor solid block */
sco = newsub(cm, co);
t = cm->cd[sco].block;
if (t == NULL) { /* must set it up */
t = (union tree *)MALLOC(sizeof(struct colors));
if (t == NULL) {
CERR(REG_ESPACE);
return;
}
for (i = 0; i < BYTTAB; i++)
t->tcolor[i] = sco;
cm->cd[sco].block = t;
}
/* find loop must have run at least once */
lastt->tptr[b] = t;
newarc(v->nfa, PLAIN, sco, lp, rp);
cm->cd[co].nchrs -= BYTTAB;
cm->cd[sco].nchrs += BYTTAB;
return;
}
/* general case, a mixed block to be altered */
i = 0;
while (i < BYTTAB) {
co = t->tcolor[i];
sco = newsub(cm, co);
newarc(v->nfa, PLAIN, sco, lp, rp);
previ = i;
do {
t->tcolor[i++] = sco;
} while (i < BYTTAB && t->tcolor[i] == co);
ndone = i - previ;
cm->cd[co].nchrs -= ndone;
cm->cd[sco].nchrs += ndone;
}
}
/*
- okcolors - promote subcolors to full colors
^ static VOID okcolors(struct nfa *, struct colormap *);
*/
static VOID
okcolors(nfa, cm)
struct nfa *nfa;
struct colormap *cm;
{
struct colordesc *cd;
struct colordesc *end = CDEND(cm);
struct colordesc *scd;
struct arc *a;
color co;
color sco;
for (cd = cm->cd, co = 0; cd < end; cd++, co++) {
sco = cd->sub;
if (UNUSEDCOLOR(cd) || sco == NOSUB) {
/* has no subcolor, no further action */
} else if (sco == co) {
/* is subcolor, let parent deal with it */
} else if (cd->nchrs == 0) {
/* parent empty, its arcs change color to subcolor */
cd->sub = NOSUB;
scd = &cm->cd[sco];
assert(scd->nchrs > 0);
assert(scd->sub == sco);
scd->sub = NOSUB;
while ((a = cd->arcs) != NULL) {
assert(a->co == co);
/* uncolorchain(cm, a); */
cd->arcs = a->colorchain;
a->co = sco;
/* colorchain(cm, a); */
a->colorchain = scd->arcs;
scd->arcs = a;
}
freecolor(cm, co);
} else {
/* parent's arcs must gain parallel subcolor arcs */
cd->sub = NOSUB;
scd = &cm->cd[sco];
assert(scd->nchrs > 0);
assert(scd->sub == sco);
scd->sub = NOSUB;
for (a = cd->arcs; a != NULL; a = a->colorchain) {
assert(a->co == co);
newarc(nfa, a->type, sco, a->from, a->to);
}
}
}
}
/*
- colorchain - add this arc to the color chain of its color
^ static VOID colorchain(struct colormap *, struct arc *);
*/
static VOID
colorchain(cm, a)
struct colormap *cm;
struct arc *a;
{
struct colordesc *cd = &cm->cd[a->co];
a->colorchain = cd->arcs;
cd->arcs = a;
}
/*
- uncolorchain - delete this arc from the color chain of its color
^ static VOID uncolorchain(struct colormap *, struct arc *);
*/
static VOID
uncolorchain(cm, a)
struct colormap *cm;
struct arc *a;
{
struct colordesc *cd = &cm->cd[a->co];
struct arc *aa;
aa = cd->arcs;
if (aa == a) /* easy case */
cd->arcs = a->colorchain;
else {
for (; aa != NULL && aa->colorchain != a; aa = aa->colorchain)
continue;
assert(aa != NULL);
aa->colorchain = a->colorchain;
}
a->colorchain = NULL; /* paranoia */
}
/*
- singleton - is this character in its own color?
^ static int singleton(struct colormap *, pchr c);
*/
static int /* predicate */
singleton(cm, c)
struct colormap *cm;
pchr c;
{
color co; /* color of c */
co = GETCOLOR(cm, c);
if (cm->cd[co].nchrs == 1 && cm->cd[co].sub == NOSUB)
return 1;
return 0;
}
/*
- rainbow - add arcs of all full colors (but one) between specified states
^ static VOID rainbow(struct nfa *, struct colormap *, int, pcolor,
^ struct state *, struct state *);
*/
static VOID
rainbow(nfa, cm, type, but, from, to)
struct nfa *nfa;
struct colormap *cm;
int type;
pcolor but; /* COLORLESS if no exceptions */
struct state *from;
struct state *to;
{
struct colordesc *cd;
struct colordesc *end = CDEND(cm);
color co;
for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
!(cd->flags&PSEUDO))
newarc(nfa, type, co, from, to);
}
/*
- colorcomplement - add arcs of complementary colors
* The calling sequence ought to be reconciled with cloneouts().
^ static VOID colorcomplement(struct nfa *, struct colormap *, int,
^ struct state *, struct state *, struct state *);
*/
static VOID
colorcomplement(nfa, cm, type, of, from, to)
struct nfa *nfa;
struct colormap *cm;
int type;
struct state *of; /* complements of this guy's PLAIN outarcs */
struct state *from;
struct state *to;
{
struct colordesc *cd;
struct colordesc *end = CDEND(cm);
color co;
assert(of != from);
for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
if (!UNUSEDCOLOR(cd) && !(cd->flags&PSEUDO))
if (findarc(of, PLAIN, co) == NULL)
newarc(nfa, type, co, from, to);
}
#ifdef REG_DEBUG
/*
^ #ifdef REG_DEBUG
*/
/*
- dumpcolors - debugging output
^ static VOID dumpcolors(struct colormap *, FILE *);
*/
static VOID
dumpcolors(cm, f)
struct colormap *cm;
FILE *f;
{
struct colordesc *cd;
struct colordesc *end;
color co;
chr c;
char *has;
fprintf(f, "max %ld\n", (long)cm->max);
if (NBYTS > 1)
fillcheck(cm, cm->tree, 0, f);
end = CDEND(cm);
for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
if (!UNUSEDCOLOR(cd)) {
assert(cd->nchrs > 0);
has = (cd->block != NULL) ? "#" : "";
if (cd->flags&PSEUDO)
fprintf(f, "#%2ld%s(ps): ", (long)co, has);
else
fprintf(f, "#%2ld%s(%2d): ", (long)co,
has, cd->nchrs);
/* it's hard to do this more efficiently */
for (c = CHR_MIN; c < CHR_MAX; c++)
if (GETCOLOR(cm, c) == co)
dumpchr(c, f);
assert(c == CHR_MAX);
if (GETCOLOR(cm, c) == co)
dumpchr(c, f);
fprintf(f, "\n");
}
}
/*
- fillcheck - check proper filling of a tree
^ static VOID fillcheck(struct colormap *, union tree *, int, FILE *);
*/
static VOID
fillcheck(cm, tree, level, f)
struct colormap *cm;
union tree *tree;
int level; /* level number (top == 0) of this block */
FILE *f;
{
int i;
union tree *t;
union tree *fillt = &cm->tree[level+1];
assert(level < NBYTS-1); /* this level has pointers */
for (i = BYTTAB-1; i >= 0; i--) {
t = tree->tptr[i];
if (t == NULL)
fprintf(f, "NULL found in filled tree!\n");
else if (t == fillt)
{}
else if (level < NBYTS-2) /* more pointer blocks below */
fillcheck(cm, t, level+1, f);
}
}
/*
- dumpchr - print a chr
* Kind of char-centric but works well enough for debug use.
^ static VOID dumpchr(pchr, FILE *);
*/
static VOID
dumpchr(c, f)
pchr c;
FILE *f;
{
if (c == '\\')
fprintf(f, "\\\\");
else if (c > ' ' && c <= '~')
putc((char)c, f);
else
fprintf(f, "\\u%04lx", (long)c);
}
/*
^ #endif
*/
#endif /* ifdef REG_DEBUG */