]> git.saurik.com Git - wxWidgets.git/blob - src/regex/regc_color.c
Fixed toolbar crash for MinGW/Cygwin
[wxWidgets.git] / src / regex / regc_color.c
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 */