2 * colorings of characters
3 * This file is #included by regcomp.c.
5 * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
7 * Development of this software was funded, in part, by Cray Research Inc.,
8 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
9 * Corporation, none of whom are responsible for the results. The author
12 * Redistribution and use in source and binary forms -- with or without
13 * modification -- are permitted for any purpose, provided that
14 * redistributions in source form retain this entire copyright notice and
15 * indicate the origin and nature of any modifications.
17 * I'd appreciate being given credit for this package in the documentation
18 * of software which uses it, but that is not a requirement.
20 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
21 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
22 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 * Note that there are some incestuous relationships between this code and
34 * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
39 #define CISERR() VISERR(cm->v)
40 #define CERR(e) (void)VERR(cm->v, (e))
45 - initcm - set up new colormap
46 ^ static VOID initcm(struct vars *, struct colormap *);
62 cm
->ncds
= NINLINECDS
;
67 cd
= cm
->cd
; /* cm->cd[WHITE] */
71 cd
->nchrs
= CHR_MAX
- CHR_MIN
+ 1;
73 /* upper levels of tree */
74 for (t
= &cm
->tree
[0], j
= NBYTS
-1; j
> 0; t
= nextt
, j
--) {
76 for (i
= BYTTAB
-1; i
>= 0; i
--)
79 /* bottom level is solid white */
80 t
= &cm
->tree
[NBYTS
-1];
81 for (i
= BYTTAB
-1; i
>= 0; i
--)
87 - freecm - free dynamically-allocated things in a colormap
88 ^ static VOID freecm(struct colormap *);
99 cmtreefree(cm
, cm
->tree
, 0);
100 for (i
= 1; i
<= cm
->max
; i
++) /* skip WHITE */
101 if (!UNUSEDCOLOR(&cm
->cd
[i
])) {
102 cb
= cm
->cd
[i
].block
;
106 if (cm
->cd
!= cm
->cdspace
)
111 - cmtreefree - free a non-terminal part of a colormap tree
112 ^ static VOID cmtreefree(struct colormap *, union tree *, int);
115 cmtreefree(cm
, tree
, level
)
118 int level
; /* level number (top == 0) of this block */
122 union tree
*fillt
= &cm
->tree
[level
+1];
125 assert(level
< NBYTS
-1); /* this level has pointers */
126 for (i
= BYTTAB
-1; i
>= 0; i
--) {
130 if (level
< NBYTS
-2) { /* more pointer blocks below */
131 cmtreefree(cm
, t
, level
+1);
133 } else { /* color block below */
134 cb
= cm
->cd
[t
->tcolor
[0]].block
;
135 if (t
!= cb
) /* not a solid block */
143 - setcolor - set the color of a character in a colormap
144 ^ static color setcolor(struct colormap *, pchr, pcolor);
146 static color
/* previous color */
164 assert(cm
->magic
== CMMAGIC
);
165 if (CISERR() || co
== COLORLESS
)
169 for (level
= 0, shift
= BYTBITS
* (NBYTS
- 1); shift
> 0;
170 level
++, shift
-= BYTBITS
) {
171 b
= (uc
>> shift
) & BYTMASK
;
175 fillt
= &cm
->tree
[level
+1];
176 bottom
= (shift
<= BYTBITS
) ? 1 : 0;
177 cb
= (bottom
) ? cm
->cd
[t
->tcolor
[0]].block
: fillt
;
178 if (t
== fillt
|| t
== cb
) { /* must allocate a new block */
179 newt
= (union tree
*)MALLOC((bottom
) ?
180 sizeof(struct colors
) : sizeof(struct ptrs
));
186 memcpy(VS(newt
->tcolor
), VS(t
->tcolor
),
187 BYTTAB
*sizeof(color
));
189 memcpy(VS(newt
->tptr
), VS(t
->tptr
),
190 BYTTAB
*sizeof(union tree
*));
198 t
->tcolor
[b
] = (color
)co
;
203 - maxcolor - report largest color number in use
204 ^ static color maxcolor(struct colormap *);
213 return (color
)cm
->max
;
217 - newcolor - find a new color (must be subject of setcolor at once)
218 * Beware: may relocate the colordescs.
219 ^ static color newcolor(struct colormap *);
221 static color
/* COLORLESS for error */
225 struct colordesc
*cd
;
226 struct colordesc
*new;
233 assert(cm
->free
> 0);
234 assert((size_t)cm
->free
< cm
->ncds
);
235 cd
= &cm
->cd
[cm
->free
];
236 assert(UNUSEDCOLOR(cd
));
237 assert(cd
->arcs
== NULL
);
239 } else if (cm
->max
< cm
->ncds
- 1) {
241 cd
= &cm
->cd
[cm
->max
];
243 /* oops, must allocate more */
245 if (cm
->cd
== cm
->cdspace
) {
246 new = (struct colordesc
*)MALLOC(n
*
247 sizeof(struct colordesc
));
249 memcpy(VS(new), VS(cm
->cdspace
), cm
->ncds
*
250 sizeof(struct colordesc
));
252 new = (struct colordesc
*)REALLOC(cm
->cd
,
253 n
* sizeof(struct colordesc
));
260 assert(cm
->max
< cm
->ncds
- 1);
262 cd
= &cm
->cd
[cm
->max
];
271 return (color
)(cd
- cm
->cd
);
275 - freecolor - free a color (must have no arcs or subcolor)
276 ^ static VOID freecolor(struct colormap *, pcolor);
283 struct colordesc
*cd
= &cm
->cd
[co
];
284 color pco
, nco
; /* for freelist scan */
290 assert(cd
->arcs
== NULL
);
291 assert(cd
->sub
== NOSUB
);
292 assert(cd
->nchrs
== 0);
294 if (cd
->block
!= NULL
) {
296 cd
->block
= NULL
; /* just paranoia */
299 if ((size_t)co
== cm
->max
) {
300 while (cm
->max
> WHITE
&& UNUSEDCOLOR(&cm
->cd
[cm
->max
]))
302 assert(cm
->free
>= 0);
303 while ((size_t)cm
->free
> cm
->max
)
304 cm
->free
= cm
->cd
[cm
->free
].sub
;
306 assert(cm
->free
< cm
->max
);
308 nco
= cm
->cd
[pco
].sub
;
310 if ((size_t)nco
> cm
->max
) {
311 /* take this one out of freelist */
312 nco
= cm
->cd
[nco
].sub
;
313 cm
->cd
[pco
].sub
= nco
;
315 assert(nco
< cm
->max
);
317 nco
= cm
->cd
[pco
].sub
;
322 cm
->free
= (color
)(cd
- cm
->cd
);
327 - pseudocolor - allocate a false color, to be managed by other means
328 ^ static color pseudocolor(struct colormap *);
339 cm
->cd
[co
].nchrs
= 1;
340 cm
->cd
[co
].flags
= PSEUDO
;
345 - subcolor - allocate a new subcolor (if necessary) to this chr
346 ^ static color subcolor(struct colormap *, pchr c);
353 color co
; /* current color of c */
354 color sco
; /* new subcolor */
356 co
= GETCOLOR(cm
, c
);
357 sco
= newsub(cm
, co
);
360 assert(sco
!= COLORLESS
);
362 if (co
== sco
) /* already in an open subcolor */
363 return co
; /* rest is redundant */
366 setcolor(cm
, c
, sco
);
371 - newsub - allocate a new subcolor (if necessary) for a color
372 ^ static color newsub(struct colormap *, pcolor);
379 color sco
; /* new subcolor */
381 sco
= cm
->cd
[co
].sub
;
382 if (sco
== NOSUB
) { /* color has no open subcolor */
383 if (cm
->cd
[co
].nchrs
== 1) /* optimization */
385 sco
= newcolor(cm
); /* must create subcolor */
386 if (sco
== COLORLESS
) {
390 cm
->cd
[co
].sub
= sco
;
391 cm
->cd
[sco
].sub
= sco
; /* open subcolor points to self */
393 assert(sco
!= NOSUB
);
399 - subrange - allocate new subcolors to this range of chrs, fill in arcs
400 ^ static VOID subrange(struct vars *, pchr, pchr, struct state *,
404 subrange(v
, from
, to
, lp
, rp
)
416 /* first, align "from" on a tree-block boundary */
418 i
= (int)( ((uf
+ BYTTAB
-1) & (uchr
)~BYTMASK
) - uf
);
419 for (; from
<= to
&& i
> 0; i
--, from
++)
420 newarc(v
->nfa
, PLAIN
, subcolor(v
->cm
, from
), lp
, rp
);
421 if (from
> to
) /* didn't reach a boundary */
424 /* deal with whole blocks */
425 for (; to
- from
>= BYTTAB
; from
+= BYTTAB
)
426 subblock(v
, from
, lp
, rp
);
428 /* clean up any remaining partial table */
429 for (; from
<= to
; from
++)
430 newarc(v
->nfa
, PLAIN
, subcolor(v
->cm
, from
), lp
, rp
);
434 - subblock - allocate new subcolors for one tree block of chrs, fill in arcs
435 ^ static VOID subblock(struct vars *, pchr, struct state *, struct state *);
438 subblock(v
, start
, lp
, rp
)
440 pchr start
; /* first of BYTTAB chrs */
445 struct colormap
*cm
= v
->cm
;
453 union tree
*lastt
= NULL
;
459 assert((uc
% BYTTAB
) == 0);
461 /* find its color block, making new pointer blocks as needed */
464 for (level
= 0, shift
= BYTBITS
* (NBYTS
- 1); shift
> 0;
465 level
++, shift
-= BYTBITS
) {
466 b
= (uc
>> shift
) & BYTMASK
;
470 fillt
= &cm
->tree
[level
+1];
471 if (t
== fillt
&& shift
> BYTBITS
) { /* need new ptr block */
472 t
= (union tree
*)MALLOC(sizeof(struct ptrs
));
477 memcpy(VS(t
->tptr
), VS(fillt
->tptr
),
478 BYTTAB
*sizeof(union tree
*));
483 /* special cases: fill block or solid block */
485 cb
= cm
->cd
[co
].block
;
486 if (t
== fillt
|| t
== cb
) {
487 /* either way, we want a subcolor solid block */
488 sco
= newsub(cm
, co
);
489 t
= cm
->cd
[sco
].block
;
490 if (t
== NULL
) { /* must set it up */
491 t
= (union tree
*)MALLOC(sizeof(struct colors
));
496 for (i
= 0; i
< BYTTAB
; i
++)
498 cm
->cd
[sco
].block
= t
;
500 /* find loop must have run at least once */
502 newarc(v
->nfa
, PLAIN
, sco
, lp
, rp
);
503 cm
->cd
[co
].nchrs
-= BYTTAB
;
504 cm
->cd
[sco
].nchrs
+= BYTTAB
;
508 /* general case, a mixed block to be altered */
512 sco
= newsub(cm
, co
);
513 newarc(v
->nfa
, PLAIN
, sco
, lp
, rp
);
516 t
->tcolor
[i
++] = sco
;
517 } while (i
< BYTTAB
&& t
->tcolor
[i
] == co
);
519 cm
->cd
[co
].nchrs
-= ndone
;
520 cm
->cd
[sco
].nchrs
+= ndone
;
525 - okcolors - promote subcolors to full colors
526 ^ static VOID okcolors(struct nfa *, struct colormap *);
533 struct colordesc
*cd
;
534 struct colordesc
*end
= CDEND(cm
);
535 struct colordesc
*scd
;
540 for (cd
= cm
->cd
, co
= 0; cd
< end
; cd
++, co
++) {
542 if (UNUSEDCOLOR(cd
) || sco
== NOSUB
) {
543 /* has no subcolor, no further action */
544 } else if (sco
== co
) {
545 /* is subcolor, let parent deal with it */
546 } else if (cd
->nchrs
== 0) {
547 /* parent empty, its arcs change color to subcolor */
550 assert(scd
->nchrs
> 0);
551 assert(scd
->sub
== sco
);
553 while ((a
= cd
->arcs
) != NULL
) {
555 /* uncolorchain(cm, a); */
556 cd
->arcs
= a
->colorchain
;
558 /* colorchain(cm, a); */
559 a
->colorchain
= scd
->arcs
;
564 /* parent's arcs must gain parallel subcolor arcs */
567 assert(scd
->nchrs
> 0);
568 assert(scd
->sub
== sco
);
570 for (a
= cd
->arcs
; a
!= NULL
; a
= a
->colorchain
) {
572 newarc(nfa
, a
->type
, sco
, a
->from
, a
->to
);
579 - colorchain - add this arc to the color chain of its color
580 ^ static VOID colorchain(struct colormap *, struct arc *);
587 struct colordesc
*cd
= &cm
->cd
[a
->co
];
589 a
->colorchain
= cd
->arcs
;
594 - uncolorchain - delete this arc from the color chain of its color
595 ^ static VOID uncolorchain(struct colormap *, struct arc *);
602 struct colordesc
*cd
= &cm
->cd
[a
->co
];
606 if (aa
== a
) /* easy case */
607 cd
->arcs
= a
->colorchain
;
609 for (; aa
!= NULL
&& aa
->colorchain
!= a
; aa
= aa
->colorchain
)
612 aa
->colorchain
= a
->colorchain
;
614 a
->colorchain
= NULL
; /* paranoia */
618 - singleton - is this character in its own color?
619 ^ static int singleton(struct colormap *, pchr c);
621 static int /* predicate */
626 color co
; /* color of c */
628 co
= GETCOLOR(cm
, c
);
629 if (cm
->cd
[co
].nchrs
== 1 && cm
->cd
[co
].sub
== NOSUB
)
635 - rainbow - add arcs of all full colors (but one) between specified states
636 ^ static VOID rainbow(struct nfa *, struct colormap *, int, pcolor,
637 ^ struct state *, struct state *);
640 rainbow(nfa
, cm
, type
, but
, from
, to
)
644 pcolor but
; /* COLORLESS if no exceptions */
648 struct colordesc
*cd
;
649 struct colordesc
*end
= CDEND(cm
);
652 for (cd
= cm
->cd
, co
= 0; cd
< end
&& !CISERR(); cd
++, co
++)
653 if (!UNUSEDCOLOR(cd
) && cd
->sub
!= co
&& co
!= but
&&
655 newarc(nfa
, type
, co
, from
, to
);
659 - colorcomplement - add arcs of complementary colors
660 * The calling sequence ought to be reconciled with cloneouts().
661 ^ static VOID colorcomplement(struct nfa *, struct colormap *, int,
662 ^ struct state *, struct state *, struct state *);
665 colorcomplement(nfa
, cm
, type
, of
, from
, to
)
669 struct state
*of
; /* complements of this guy's PLAIN outarcs */
673 struct colordesc
*cd
;
674 struct colordesc
*end
= CDEND(cm
);
678 for (cd
= cm
->cd
, co
= 0; cd
< end
&& !CISERR(); cd
++, co
++)
679 if (!UNUSEDCOLOR(cd
) && !(cd
->flags
&PSEUDO
))
680 if (findarc(of
, PLAIN
, co
) == NULL
)
681 newarc(nfa
, type
, co
, from
, to
);
692 - dumpcolors - debugging output
693 ^ static VOID dumpcolors(struct colormap *, FILE *);
700 struct colordesc
*cd
;
701 struct colordesc
*end
;
706 fprintf(f
, "max %ld\n", (long)cm
->max
);
708 fillcheck(cm
, cm
->tree
, 0, f
);
710 for (cd
= cm
->cd
+ 1, co
= 1; cd
< end
; cd
++, co
++) /* skip 0 */
711 if (!UNUSEDCOLOR(cd
)) {
712 assert(cd
->nchrs
> 0);
713 has
= (cd
->block
!= NULL
) ? "#" : "";
714 if (cd
->flags
&PSEUDO
)
715 fprintf(f
, "#%2ld%s(ps): ", (long)co
, has
);
717 fprintf(f
, "#%2ld%s(%2d): ", (long)co
,
719 /* it's hard to do this more efficiently */
720 for (c
= CHR_MIN
; c
< CHR_MAX
; c
++)
721 if (GETCOLOR(cm
, c
) == co
)
723 assert(c
== CHR_MAX
);
724 if (GETCOLOR(cm
, c
) == co
)
731 - fillcheck - check proper filling of a tree
732 ^ static VOID fillcheck(struct colormap *, union tree *, int, FILE *);
735 fillcheck(cm
, tree
, level
, f
)
738 int level
; /* level number (top == 0) of this block */
743 union tree
*fillt
= &cm
->tree
[level
+1];
745 assert(level
< NBYTS
-1); /* this level has pointers */
746 for (i
= BYTTAB
-1; i
>= 0; i
--) {
749 fprintf(f
, "NULL found in filled tree!\n");
752 else if (level
< NBYTS
-2) /* more pointer blocks below */
753 fillcheck(cm
, t
, level
+1, f
);
758 - dumpchr - print a chr
759 * Kind of char-centric but works well enough for debug use.
760 ^ static VOID dumpchr(pchr, FILE *);
769 else if (c
> ' ' && c
<= '~')
772 fprintf(f
, "\\u%04lx", (long)c
);
778 #endif /* ifdef REG_DEBUG */