Commit | Line | Data |
---|---|---|
d37acbdf RN |
1 | /* |
2 | * colorings of characters | |
3 | * This file is #included by regcomp.c. | |
4 | * | |
5 | * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. | |
6 | * | |
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 | |
10 | * thanks all of them. | |
11 | * | |
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. | |
16 | * | |
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. | |
19 | * | |
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. | |
30 | * | |
31 | * $Header$ | |
32 | * | |
33 | * | |
34 | * Note that there are some incestuous relationships between this code and | |
35 | * NFA arc maintenance, which perhaps ought to be cleaned up sometime. | |
36 | */ | |
37 | ||
38 | ||
39 | ||
40 | #define CISERR() VISERR(cm->v) | |
41 | #define CERR(e) VERR(cm->v, (e)) | |
42 | ||
43 | ||
44 | ||
45 | /* | |
46 | * initcm - set up new colormap | |
47 | */ | |
48 | static void | |
49 | initcm(struct vars * v, | |
50 | struct colormap * cm) | |
51 | { | |
52 | int i; | |
53 | int j; | |
54 | union tree *t; | |
55 | union tree *nextt; | |
56 | struct colordesc *cd; | |
57 | ||
58 | cm->magic = CMMAGIC; | |
59 | cm->v = v; | |
60 | ||
61 | cm->ncds = NINLINECDS; | |
62 | cm->cd = cm->cdspace; | |
63 | cm->max = 0; | |
64 | cm->free = 0; | |
65 | ||
66 | cd = cm->cd; /* cm->cd[WHITE] */ | |
67 | cd->sub = NOSUB; | |
68 | cd->arcs = NULL; | |
69 | cd->flags = 0; | |
70 | cd->nchrs = CHR_MAX - CHR_MIN + 1; | |
71 | ||
72 | /* upper levels of tree */ | |
73 | for (t = &cm->tree[0], j = NBYTS - 1; j > 0; t = nextt, j--) | |
74 | { | |
75 | nextt = t + 1; | |
76 | for (i = BYTTAB - 1; i >= 0; i--) | |
77 | t->tptr[i] = nextt; | |
78 | } | |
79 | /* bottom level is solid white */ | |
80 | t = &cm->tree[NBYTS - 1]; | |
81 | for (i = BYTTAB - 1; i >= 0; i--) | |
82 | t->tcolor[i] = WHITE; | |
83 | cd->block = t; | |
84 | } | |
85 | ||
86 | /* | |
87 | * freecm - free dynamically-allocated things in a colormap | |
88 | */ | |
89 | static void | |
90 | freecm(struct colormap * cm) | |
91 | { | |
92 | size_t i; | |
93 | union tree *cb; | |
94 | ||
95 | cm->magic = 0; | |
96 | if (NBYTS > 1) | |
97 | cmtreefree(cm, cm->tree, 0); | |
98 | for (i = 1; i <= cm->max; i++) /* skip WHITE */ | |
99 | if (!UNUSEDCOLOR(&cm->cd[i])) | |
100 | { | |
101 | cb = cm->cd[i].block; | |
102 | if (cb != NULL) | |
103 | FREE(cb); | |
104 | } | |
105 | if (cm->cd != cm->cdspace) | |
106 | FREE(cm->cd); | |
107 | } | |
108 | ||
109 | /* | |
110 | * cmtreefree - free a non-terminal part of a colormap tree | |
111 | */ | |
112 | static void | |
113 | cmtreefree(struct colormap * cm, | |
114 | union tree * tree, | |
115 | int level) /* level number (top == 0) of this block */ | |
116 | { | |
117 | int i; | |
118 | union tree *t; | |
119 | union tree *fillt = &cm->tree[level + 1]; | |
120 | union tree *cb; | |
121 | ||
122 | assert(level < NBYTS - 1); /* this level has pointers */ | |
123 | for (i = BYTTAB - 1; i >= 0; i--) | |
124 | { | |
125 | t = tree->tptr[i]; | |
126 | assert(t != NULL); | |
127 | if (t != fillt) | |
128 | { | |
129 | if (level < NBYTS - 2) | |
130 | { /* more pointer blocks below */ | |
131 | cmtreefree(cm, t, level + 1); | |
132 | FREE(t); | |
133 | } | |
134 | else | |
135 | { /* color block below */ | |
136 | cb = cm->cd[t->tcolor[0]].block; | |
137 | if (t != cb) /* not a solid block */ | |
138 | FREE(t); | |
139 | } | |
140 | } | |
141 | } | |
142 | } | |
143 | ||
144 | /* | |
145 | * setcolor - set the color of a character in a colormap | |
146 | */ | |
147 | static color /* previous color */ | |
148 | setcolor(struct colormap * cm, | |
149 | chr c, | |
150 | pcolor co) | |
151 | { | |
152 | uchr uc = c; | |
153 | int shift; | |
154 | int level; | |
155 | int b; | |
156 | int bottom; | |
157 | union tree *t; | |
158 | union tree *newt; | |
159 | union tree *fillt; | |
160 | union tree *lastt; | |
161 | union tree *cb; | |
162 | color prev; | |
163 | ||
164 | assert(cm->magic == CMMAGIC); | |
165 | if (CISERR() || co == COLORLESS) | |
166 | return COLORLESS; | |
167 | ||
168 | t = cm->tree; | |
169 | for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0; | |
170 | level++, shift -= BYTBITS) | |
171 | { | |
172 | b = (uc >> shift) & BYTMASK; | |
173 | lastt = t; | |
174 | t = lastt->tptr[b]; | |
175 | assert(t != NULL); | |
176 | fillt = &cm->tree[level + 1]; | |
177 | bottom = (shift <= BYTBITS) ? 1 : 0; | |
178 | cb = (bottom) ? cm->cd[t->tcolor[0]].block : fillt; | |
179 | if (t == fillt || t == cb) | |
180 | { /* must allocate a new block */ | |
181 | newt = (union tree *) MALLOC((bottom) ? | |
182 | sizeof(struct colors) : sizeof(struct ptrs)); | |
183 | if (newt == NULL) | |
184 | { | |
185 | CERR(REG_ESPACE); | |
186 | return COLORLESS; | |
187 | } | |
188 | if (bottom) | |
189 | memcpy(VS(newt->tcolor), VS(t->tcolor), | |
190 | BYTTAB * sizeof(color)); | |
191 | else | |
192 | memcpy(VS(newt->tptr), VS(t->tptr), | |
193 | BYTTAB * sizeof(union tree *)); | |
194 | t = newt; | |
195 | lastt->tptr[b] = t; | |
196 | } | |
197 | } | |
198 | ||
199 | b = uc & BYTMASK; | |
200 | prev = t->tcolor[b]; | |
201 | t->tcolor[b] = (color) co; | |
202 | return prev; | |
203 | } | |
204 | ||
205 | /* | |
206 | * maxcolor - report largest color number in use | |
207 | */ | |
208 | static color | |
209 | maxcolor(struct colormap * cm) | |
210 | { | |
211 | if (CISERR()) | |
212 | return COLORLESS; | |
213 | ||
214 | return (color) cm->max; | |
215 | } | |
216 | ||
217 | /* | |
218 | * newcolor - find a new color (must be subject of setcolor at once) | |
219 | * Beware: may relocate the colordescs. | |
220 | */ | |
221 | static color /* COLORLESS for error */ | |
222 | newcolor(struct colormap * cm) | |
223 | { | |
224 | struct colordesc *cd; | |
225 | struct colordesc *new; | |
226 | size_t n; | |
227 | ||
228 | if (CISERR()) | |
229 | return COLORLESS; | |
230 | ||
231 | if (cm->free != 0) | |
232 | { | |
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); | |
238 | cm->free = cd->sub; | |
239 | } | |
240 | else if (cm->max < cm->ncds - 1) | |
241 | { | |
242 | cm->max++; | |
243 | cd = &cm->cd[cm->max]; | |
244 | } | |
245 | else | |
246 | { | |
247 | /* oops, must allocate more */ | |
248 | n = cm->ncds * 2; | |
249 | if (cm->cd == cm->cdspace) | |
250 | { | |
251 | new = (struct colordesc *) MALLOC(n * | |
252 | sizeof(struct colordesc)); | |
253 | if (new != NULL) | |
254 | memcpy(VS(new), VS(cm->cdspace), cm->ncds * | |
255 | sizeof(struct colordesc)); | |
256 | } | |
257 | else | |
258 | new = (struct colordesc *) REALLOC(cm->cd, | |
259 | n * sizeof(struct colordesc)); | |
260 | if (new == NULL) | |
261 | { | |
262 | CERR(REG_ESPACE); | |
263 | return COLORLESS; | |
264 | } | |
265 | cm->cd = new; | |
266 | cm->ncds = n; | |
267 | assert(cm->max < cm->ncds - 1); | |
268 | cm->max++; | |
269 | cd = &cm->cd[cm->max]; | |
270 | } | |
271 | ||
272 | cd->nchrs = 0; | |
273 | cd->sub = NOSUB; | |
274 | cd->arcs = NULL; | |
275 | cd->flags = 0; | |
276 | cd->block = NULL; | |
277 | ||
278 | return (color) (cd - cm->cd); | |
279 | } | |
280 | ||
281 | /* | |
282 | * freecolor - free a color (must have no arcs or subcolor) | |
283 | */ | |
284 | static void | |
285 | freecolor(struct colormap * cm, | |
286 | pcolor co) | |
287 | { | |
288 | struct colordesc *cd = &cm->cd[co]; | |
289 | color pco, | |
290 | nco; /* for freelist scan */ | |
291 | ||
292 | assert(co >= 0); | |
293 | if (co == WHITE) | |
294 | return; | |
295 | ||
296 | assert(cd->arcs == NULL); | |
297 | assert(cd->sub == NOSUB); | |
298 | assert(cd->nchrs == 0); | |
299 | cd->flags = FREECOL; | |
300 | if (cd->block != NULL) | |
301 | { | |
302 | FREE(cd->block); | |
303 | cd->block = NULL; /* just paranoia */ | |
304 | } | |
305 | ||
306 | if ((size_t) co == cm->max) | |
307 | { | |
308 | while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max])) | |
309 | cm->max--; | |
310 | assert(cm->free >= 0); | |
311 | while ((size_t) cm->free > cm->max) | |
312 | cm->free = cm->cd[cm->free].sub; | |
313 | if (cm->free > 0) | |
314 | { | |
315 | assert(cm->free < cm->max); | |
316 | pco = cm->free; | |
317 | nco = cm->cd[pco].sub; | |
318 | while (nco > 0) | |
319 | if ((size_t) nco > cm->max) | |
320 | { | |
321 | /* take this one out of freelist */ | |
322 | nco = cm->cd[nco].sub; | |
323 | cm->cd[pco].sub = nco; | |
324 | } | |
325 | else | |
326 | { | |
327 | assert(nco < cm->max); | |
328 | pco = nco; | |
329 | nco = cm->cd[pco].sub; | |
330 | } | |
331 | } | |
332 | } | |
333 | else | |
334 | { | |
335 | cd->sub = cm->free; | |
336 | cm->free = (color) (cd - cm->cd); | |
337 | } | |
338 | } | |
339 | ||
340 | /* | |
341 | * pseudocolor - allocate a false color, to be managed by other means | |
342 | */ | |
343 | static color | |
344 | pseudocolor(struct colormap * cm) | |
345 | { | |
346 | color co; | |
347 | ||
348 | co = newcolor(cm); | |
349 | if (CISERR()) | |
350 | return COLORLESS; | |
351 | cm->cd[co].nchrs = 1; | |
352 | cm->cd[co].flags = PSEUDO; | |
353 | return co; | |
354 | } | |
355 | ||
356 | /* | |
357 | * subcolor - allocate a new subcolor (if necessary) to this chr | |
358 | */ | |
359 | static color | |
360 | subcolor(struct colormap * cm, chr c) | |
361 | { | |
362 | color co; /* current color of c */ | |
363 | color sco; /* new subcolor */ | |
364 | ||
365 | co = GETCOLOR(cm, c); | |
366 | sco = newsub(cm, co); | |
367 | if (CISERR()) | |
368 | return COLORLESS; | |
369 | assert(sco != COLORLESS); | |
370 | ||
371 | if (co == sco) /* already in an open subcolor */ | |
372 | return co; /* rest is redundant */ | |
373 | cm->cd[co].nchrs--; | |
374 | cm->cd[sco].nchrs++; | |
375 | setcolor(cm, c, sco); | |
376 | return sco; | |
377 | } | |
378 | ||
379 | /* | |
380 | * newsub - allocate a new subcolor (if necessary) for a color | |
381 | */ | |
382 | static color | |
383 | newsub(struct colormap * cm, | |
384 | pcolor co) | |
385 | { | |
386 | color sco; /* new subcolor */ | |
387 | ||
388 | sco = cm->cd[co].sub; | |
389 | if (sco == NOSUB) | |
390 | { /* color has no open subcolor */ | |
391 | if (cm->cd[co].nchrs == 1) /* optimization */ | |
392 | return co; | |
393 | sco = newcolor(cm); /* must create subcolor */ | |
394 | if (sco == COLORLESS) | |
395 | { | |
396 | assert(CISERR()); | |
397 | return COLORLESS; | |
398 | } | |
399 | cm->cd[co].sub = sco; | |
400 | cm->cd[sco].sub = sco; /* open subcolor points to self */ | |
401 | } | |
402 | assert(sco != NOSUB); | |
403 | ||
404 | return sco; | |
405 | } | |
406 | ||
407 | /* | |
408 | * subrange - allocate new subcolors to this range of chrs, fill in arcs | |
409 | */ | |
410 | static void | |
411 | subrange(struct vars * v, | |
412 | chr from, | |
413 | chr to, | |
414 | struct state * lp, | |
415 | struct state * rp) | |
416 | { | |
417 | uchr uf; | |
418 | int i; | |
419 | ||
420 | assert(from <= to); | |
421 | ||
422 | /* first, align "from" on a tree-block boundary */ | |
423 | uf = (uchr) from; | |
424 | i = (int) (((uf + BYTTAB - 1) & (uchr) ~BYTMASK) - uf); | |
425 | for (; from <= to && i > 0; i--, from++) | |
426 | newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp); | |
427 | if (from > to) /* didn't reach a boundary */ | |
428 | return; | |
429 | ||
430 | /* deal with whole blocks */ | |
431 | for (; to - from >= BYTTAB; from += BYTTAB) | |
432 | subblock(v, from, lp, rp); | |
433 | ||
434 | /* clean up any remaining partial table */ | |
435 | for (; from <= to; from++) | |
436 | newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp); | |
437 | } | |
438 | ||
439 | /* | |
440 | * subblock - allocate new subcolors for one tree block of chrs, fill in arcs | |
441 | */ | |
442 | static void | |
443 | subblock(struct vars * v, | |
444 | chr start, /* first of BYTTAB chrs */ | |
445 | struct state * lp, | |
446 | struct state * rp) | |
447 | { | |
448 | uchr uc = start; | |
449 | struct colormap *cm = v->cm; | |
450 | int shift; | |
451 | int level; | |
452 | int i; | |
453 | int b; | |
454 | union tree *t; | |
455 | union tree *cb; | |
456 | union tree *fillt; | |
457 | union tree *lastt; | |
458 | int previ; | |
459 | int ndone; | |
460 | color co; | |
461 | color sco; | |
462 | ||
463 | assert((uc % BYTTAB) == 0); | |
464 | ||
465 | /* find its color block, making new pointer blocks as needed */ | |
466 | t = cm->tree; | |
467 | fillt = NULL; | |
468 | for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0; | |
469 | level++, shift -= BYTBITS) | |
470 | { | |
471 | b = (uc >> shift) & BYTMASK; | |
472 | lastt = t; | |
473 | t = lastt->tptr[b]; | |
474 | assert(t != NULL); | |
475 | fillt = &cm->tree[level + 1]; | |
476 | if (t == fillt && shift > BYTBITS) | |
477 | { /* need new ptr block */ | |
478 | t = (union tree *) MALLOC(sizeof(struct ptrs)); | |
479 | if (t == NULL) | |
480 | { | |
481 | CERR(REG_ESPACE); | |
482 | return; | |
483 | } | |
484 | memcpy(VS(t->tptr), VS(fillt->tptr), | |
485 | BYTTAB * sizeof(union tree *)); | |
486 | lastt->tptr[b] = t; | |
487 | } | |
488 | } | |
489 | ||
490 | /* special cases: fill block or solid block */ | |
491 | co = t->tcolor[0]; | |
492 | cb = cm->cd[co].block; | |
493 | if (t == fillt || t == cb) | |
494 | { | |
495 | /* either way, we want a subcolor solid block */ | |
496 | sco = newsub(cm, co); | |
497 | t = cm->cd[sco].block; | |
498 | if (t == NULL) | |
499 | { /* must set it up */ | |
500 | t = (union tree *) MALLOC(sizeof(struct colors)); | |
501 | if (t == NULL) | |
502 | { | |
503 | CERR(REG_ESPACE); | |
504 | return; | |
505 | } | |
506 | for (i = 0; i < BYTTAB; i++) | |
507 | t->tcolor[i] = sco; | |
508 | cm->cd[sco].block = t; | |
509 | } | |
510 | /* find loop must have run at least once */ | |
511 | lastt->tptr[b] = t; | |
512 | newarc(v->nfa, PLAIN, sco, lp, rp); | |
513 | cm->cd[co].nchrs -= BYTTAB; | |
514 | cm->cd[sco].nchrs += BYTTAB; | |
515 | return; | |
516 | } | |
517 | ||
518 | /* general case, a mixed block to be altered */ | |
519 | i = 0; | |
520 | while (i < BYTTAB) | |
521 | { | |
522 | co = t->tcolor[i]; | |
523 | sco = newsub(cm, co); | |
524 | newarc(v->nfa, PLAIN, sco, lp, rp); | |
525 | previ = i; | |
526 | do | |
527 | { | |
528 | t->tcolor[i++] = sco; | |
529 | } while (i < BYTTAB && t->tcolor[i] == co); | |
530 | ndone = i - previ; | |
531 | cm->cd[co].nchrs -= ndone; | |
532 | cm->cd[sco].nchrs += ndone; | |
533 | } | |
534 | } | |
535 | ||
536 | /* | |
537 | * okcolors - promote subcolors to full colors | |
538 | */ | |
539 | static void | |
540 | okcolors(struct nfa * nfa, | |
541 | struct colormap * cm) | |
542 | { | |
543 | struct colordesc *cd; | |
544 | struct colordesc *end = CDEND(cm); | |
545 | struct colordesc *scd; | |
546 | struct arc *a; | |
547 | color co; | |
548 | color sco; | |
549 | ||
550 | for (cd = cm->cd, co = 0; cd < end; cd++, co++) | |
551 | { | |
552 | sco = cd->sub; | |
553 | if (UNUSEDCOLOR(cd) || sco == NOSUB) | |
554 | { | |
555 | /* has no subcolor, no further action */ | |
556 | } | |
557 | else if (sco == co) | |
558 | { | |
559 | /* is subcolor, let parent deal with it */ | |
560 | } | |
561 | else if (cd->nchrs == 0) | |
562 | { | |
563 | /* parent empty, its arcs change color to subcolor */ | |
564 | cd->sub = NOSUB; | |
565 | scd = &cm->cd[sco]; | |
566 | assert(scd->nchrs > 0); | |
567 | assert(scd->sub == sco); | |
568 | scd->sub = NOSUB; | |
569 | while ((a = cd->arcs) != NULL) | |
570 | { | |
571 | assert(a->co == co); | |
572 | /* uncolorchain(cm, a); */ | |
573 | cd->arcs = a->colorchain; | |
574 | a->co = sco; | |
575 | /* colorchain(cm, a); */ | |
576 | a->colorchain = scd->arcs; | |
577 | scd->arcs = a; | |
578 | } | |
579 | freecolor(cm, co); | |
580 | } | |
581 | else | |
582 | { | |
583 | /* parent's arcs must gain parallel subcolor arcs */ | |
584 | cd->sub = NOSUB; | |
585 | scd = &cm->cd[sco]; | |
586 | assert(scd->nchrs > 0); | |
587 | assert(scd->sub == sco); | |
588 | scd->sub = NOSUB; | |
589 | for (a = cd->arcs; a != NULL; a = a->colorchain) | |
590 | { | |
591 | assert(a->co == co); | |
592 | newarc(nfa, a->type, sco, a->from, a->to); | |
593 | } | |
594 | } | |
595 | } | |
596 | } | |
597 | ||
598 | /* | |
599 | * colorchain - add this arc to the color chain of its color | |
600 | */ | |
601 | static void | |
602 | colorchain(struct colormap * cm, | |
603 | struct arc * a) | |
604 | { | |
605 | struct colordesc *cd = &cm->cd[a->co]; | |
606 | ||
607 | a->colorchain = cd->arcs; | |
608 | cd->arcs = a; | |
609 | } | |
610 | ||
611 | /* | |
612 | * uncolorchain - delete this arc from the color chain of its color | |
613 | */ | |
614 | static void | |
615 | uncolorchain(struct colormap * cm, | |
616 | struct arc * a) | |
617 | { | |
618 | struct colordesc *cd = &cm->cd[a->co]; | |
619 | struct arc *aa; | |
620 | ||
621 | aa = cd->arcs; | |
622 | if (aa == a) /* easy case */ | |
623 | cd->arcs = a->colorchain; | |
624 | else | |
625 | { | |
626 | for (; aa != NULL && aa->colorchain != a; aa = aa->colorchain) | |
627 | continue; | |
628 | assert(aa != NULL); | |
629 | aa->colorchain = a->colorchain; | |
630 | } | |
631 | a->colorchain = NULL; /* paranoia */ | |
632 | } | |
633 | ||
634 | /* | |
635 | * singleton - is this character in its own color? | |
636 | */ | |
637 | static int /* predicate */ | |
638 | singleton(struct colormap * cm, | |
639 | chr c) | |
640 | { | |
641 | color co; /* color of c */ | |
642 | ||
643 | co = GETCOLOR(cm, c); | |
644 | if (cm->cd[co].nchrs == 1 && cm->cd[co].sub == NOSUB) | |
645 | return 1; | |
646 | return 0; | |
647 | } | |
648 | ||
649 | /* | |
650 | * rainbow - add arcs of all full colors (but one) between specified states | |
651 | */ | |
652 | static void | |
653 | rainbow(struct nfa * nfa, | |
654 | struct colormap * cm, | |
655 | int type, | |
656 | pcolor but, /* COLORLESS if no exceptions */ | |
657 | struct state * from, | |
658 | struct state * to) | |
659 | { | |
660 | struct colordesc *cd; | |
661 | struct colordesc *end = CDEND(cm); | |
662 | color co; | |
663 | ||
664 | for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++) | |
665 | if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but && | |
666 | !(cd->flags & PSEUDO)) | |
667 | newarc(nfa, type, co, from, to); | |
668 | } | |
669 | ||
670 | /* | |
671 | * colorcomplement - add arcs of complementary colors | |
672 | * | |
673 | * The calling sequence ought to be reconciled with cloneouts(). | |
674 | */ | |
675 | static void | |
676 | colorcomplement(struct nfa * nfa, | |
677 | struct colormap * cm, | |
678 | int type, | |
679 | struct state * of, /* complements of this guy's PLAIN | |
680 | * outarcs */ | |
681 | struct state * from, | |
682 | struct state * to) | |
683 | { | |
684 | struct colordesc *cd; | |
685 | struct colordesc *end = CDEND(cm); | |
686 | color co; | |
687 | ||
688 | assert(of != from); | |
689 | for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++) | |
690 | if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO)) | |
691 | if (findarc(of, PLAIN, co) == NULL) | |
692 | newarc(nfa, type, co, from, to); | |
693 | } | |
694 | ||
695 | ||
696 | #ifdef REG_DEBUG | |
697 | ||
698 | /* | |
699 | * dumpcolors - debugging output | |
700 | */ | |
701 | static void | |
702 | dumpcolors(struct colormap * cm, | |
703 | FILE *f) | |
704 | { | |
705 | struct colordesc *cd; | |
706 | struct colordesc *end; | |
707 | color co; | |
708 | chr c; | |
709 | char *has; | |
710 | ||
711 | fprintf(f, "max %ld\n", (long) cm->max); | |
712 | if (NBYTS > 1) | |
713 | fillcheck(cm, cm->tree, 0, f); | |
714 | end = CDEND(cm); | |
715 | for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */ | |
716 | if (!UNUSEDCOLOR(cd)) | |
717 | { | |
718 | assert(cd->nchrs > 0); | |
719 | has = (cd->block != NULL) ? "#" : ""; | |
720 | if (cd->flags & PSEUDO) | |
721 | fprintf(f, "#%2ld%s(ps): ", (long) co, has); | |
722 | else | |
723 | fprintf(f, "#%2ld%s(%2d): ", (long) co, | |
724 | has, cd->nchrs); | |
725 | /* it's hard to do this more efficiently */ | |
726 | for (c = CHR_MIN; c < CHR_MAX; c++) | |
727 | if (GETCOLOR(cm, c) == co) | |
728 | dumpchr(c, f); | |
729 | assert(c == CHR_MAX); | |
730 | if (GETCOLOR(cm, c) == co) | |
731 | dumpchr(c, f); | |
732 | fprintf(f, "\n"); | |
733 | } | |
734 | } | |
735 | ||
736 | /* | |
737 | * fillcheck - check proper filling of a tree | |
738 | */ | |
739 | static void | |
740 | fillcheck(struct colormap * cm, | |
741 | union tree * tree, | |
742 | int level, /* level number (top == 0) of this block */ | |
743 | FILE *f) | |
744 | { | |
745 | int i; | |
746 | union tree *t; | |
747 | union tree *fillt = &cm->tree[level + 1]; | |
748 | ||
749 | assert(level < NBYTS - 1); /* this level has pointers */ | |
750 | for (i = BYTTAB - 1; i >= 0; i--) | |
751 | { | |
752 | t = tree->tptr[i]; | |
753 | if (t == NULL) | |
754 | fprintf(f, "NULL found in filled tree!\n"); | |
755 | else if (t == fillt) | |
756 | { | |
757 | } | |
758 | else if (level < NBYTS - 2) /* more pointer blocks below */ | |
759 | fillcheck(cm, t, level + 1, f); | |
760 | } | |
761 | } | |
762 | ||
763 | /* | |
764 | * dumpchr - print a chr | |
765 | * | |
766 | * Kind of char-centric but works well enough for debug use. | |
767 | */ | |
768 | static void | |
769 | dumpchr(chr c, | |
770 | FILE *f) | |
771 | { | |
772 | if (c == '\\') | |
773 | fprintf(f, "\\\\"); | |
774 | else if (c > ' ' && c <= '~') | |
775 | putc((char) c, f); | |
776 | else | |
777 | fprintf(f, "\\u%04lx", (long) c); | |
778 | } | |
779 | ||
780 | #endif /* REG_DEBUG */ |