Line data Source code
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 : * src/backend/regex/regc_color.c
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 253 : initcm(struct vars *v,
50 : struct colormap *cm)
51 : {
52 : struct colordesc *cd;
53 :
54 253 : cm->magic = CMMAGIC;
55 253 : cm->v = v;
56 :
57 253 : cm->ncds = NINLINECDS;
58 253 : cm->cd = cm->cdspace;
59 253 : cm->max = 0;
60 253 : cm->free = 0;
61 :
62 253 : cd = cm->cd; /* cm->cd[WHITE] */
63 253 : cd->nschrs = MAX_SIMPLE_CHR - CHR_MIN + 1;
64 253 : cd->nuchrs = 1;
65 253 : cd->sub = NOSUB;
66 253 : cd->arcs = NULL;
67 253 : cd->firstchr = CHR_MIN;
68 253 : cd->flags = 0;
69 :
70 253 : cm->locolormap = (color *)
71 253 : MALLOC((MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
72 253 : if (cm->locolormap == NULL)
73 : {
74 0 : CERR(REG_ESPACE);
75 0 : cm->cmranges = NULL; /* prevent failure during freecm */
76 0 : cm->hicolormap = NULL;
77 0 : return;
78 : }
79 : /* this memset relies on WHITE being zero: */
80 253 : memset(cm->locolormap, WHITE,
81 : (MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
82 :
83 253 : memset(cm->classbits, 0, sizeof(cm->classbits));
84 253 : cm->numcmranges = 0;
85 253 : cm->cmranges = NULL;
86 253 : cm->maxarrayrows = 4; /* arbitrary initial allocation */
87 253 : cm->hiarrayrows = 1; /* but we have only one row/col initially */
88 253 : cm->hiarraycols = 1;
89 253 : cm->hicolormap = (color *) MALLOC(cm->maxarrayrows * sizeof(color));
90 253 : if (cm->hicolormap == NULL)
91 : {
92 0 : CERR(REG_ESPACE);
93 0 : return;
94 : }
95 : /* initialize the "all other characters" row to WHITE */
96 253 : cm->hicolormap[0] = WHITE;
97 : }
98 :
99 : /*
100 : * freecm - free dynamically-allocated things in a colormap
101 : */
102 : static void
103 32 : freecm(struct colormap *cm)
104 : {
105 32 : cm->magic = 0;
106 32 : if (cm->cd != cm->cdspace)
107 0 : FREE(cm->cd);
108 32 : if (cm->locolormap != NULL)
109 32 : FREE(cm->locolormap);
110 32 : if (cm->cmranges != NULL)
111 0 : FREE(cm->cmranges);
112 32 : if (cm->hicolormap != NULL)
113 32 : FREE(cm->hicolormap);
114 32 : }
115 :
116 : /*
117 : * pg_reg_getcolor - slow case of GETCOLOR()
118 : */
119 : color
120 0 : pg_reg_getcolor(struct colormap *cm, chr c)
121 : {
122 : int rownum,
123 : colnum,
124 : low,
125 : high;
126 :
127 : /* Should not be used for chrs in the locolormap */
128 0 : assert(c > MAX_SIMPLE_CHR);
129 :
130 : /*
131 : * Find which row it's in. The colormapranges are in order, so we can use
132 : * binary search.
133 : */
134 0 : rownum = 0; /* if no match, use array row zero */
135 0 : low = 0;
136 0 : high = cm->numcmranges;
137 0 : while (low < high)
138 : {
139 0 : int middle = low + (high - low) / 2;
140 0 : const colormaprange *cmr = &cm->cmranges[middle];
141 :
142 0 : if (c < cmr->cmin)
143 0 : high = middle;
144 0 : else if (c > cmr->cmax)
145 0 : low = middle + 1;
146 : else
147 : {
148 0 : rownum = cmr->rownum; /* found a match */
149 0 : break;
150 : }
151 : }
152 :
153 : /*
154 : * Find which column it's in --- this is all locale-dependent.
155 : */
156 0 : if (cm->hiarraycols > 1)
157 : {
158 0 : colnum = cclass_column_index(cm, c);
159 0 : return cm->hicolormap[rownum * cm->hiarraycols + colnum];
160 : }
161 : else
162 : {
163 : /* fast path if no relevant cclasses */
164 0 : return cm->hicolormap[rownum];
165 : }
166 : }
167 :
168 : /*
169 : * maxcolor - report largest color number in use
170 : */
171 : static color
172 1778 : maxcolor(struct colormap *cm)
173 : {
174 1778 : if (CISERR())
175 0 : return COLORLESS;
176 :
177 1778 : return (color) cm->max;
178 : }
179 :
180 : /*
181 : * newcolor - find a new color (must be assigned at once)
182 : * Beware: may relocate the colordescs.
183 : */
184 : static color /* COLORLESS for error */
185 2474 : newcolor(struct colormap *cm)
186 : {
187 : struct colordesc *cd;
188 : size_t n;
189 :
190 2474 : if (CISERR())
191 0 : return COLORLESS;
192 :
193 2474 : if (cm->free != 0)
194 : {
195 6 : assert(cm->free > 0);
196 6 : assert((size_t) cm->free < cm->ncds);
197 6 : cd = &cm->cd[cm->free];
198 6 : assert(UNUSEDCOLOR(cd));
199 6 : assert(cd->arcs == NULL);
200 6 : cm->free = cd->sub;
201 : }
202 2468 : else if (cm->max < cm->ncds - 1)
203 : {
204 2333 : cm->max++;
205 2333 : cd = &cm->cd[cm->max];
206 : }
207 : else
208 : {
209 : /* oops, must allocate more */
210 : struct colordesc *newCd;
211 :
212 135 : if (cm->max == MAX_COLOR)
213 : {
214 0 : CERR(REG_ECOLORS);
215 0 : return COLORLESS; /* too many colors */
216 : }
217 :
218 135 : n = cm->ncds * 2;
219 135 : if (n > MAX_COLOR + 1)
220 0 : n = MAX_COLOR + 1;
221 135 : if (cm->cd == cm->cdspace)
222 : {
223 135 : newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
224 135 : if (newCd != NULL)
225 135 : memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
226 : sizeof(struct colordesc));
227 : }
228 : else
229 0 : newCd = (struct colordesc *)
230 0 : REALLOC(cm->cd, n * sizeof(struct colordesc));
231 135 : if (newCd == NULL)
232 : {
233 0 : CERR(REG_ESPACE);
234 0 : return COLORLESS;
235 : }
236 135 : cm->cd = newCd;
237 135 : cm->ncds = n;
238 135 : assert(cm->max < cm->ncds - 1);
239 135 : cm->max++;
240 135 : cd = &cm->cd[cm->max];
241 : }
242 :
243 2474 : cd->nschrs = 0;
244 2474 : cd->nuchrs = 0;
245 2474 : cd->sub = NOSUB;
246 2474 : cd->arcs = NULL;
247 2474 : cd->firstchr = CHR_MIN; /* in case never set otherwise */
248 2474 : cd->flags = 0;
249 :
250 2474 : return (color) (cd - cm->cd);
251 : }
252 :
253 : /*
254 : * freecolor - free a color (must have no arcs or subcolor)
255 : */
256 : static void
257 9 : freecolor(struct colormap *cm,
258 : color co)
259 : {
260 9 : struct colordesc *cd = &cm->cd[co];
261 : color pco,
262 : nco; /* for freelist scan */
263 :
264 9 : assert(co >= 0);
265 9 : if (co == WHITE)
266 9 : return;
267 :
268 9 : assert(cd->arcs == NULL);
269 9 : assert(cd->sub == NOSUB);
270 9 : assert(cd->nschrs == 0);
271 9 : assert(cd->nuchrs == 0);
272 9 : cd->flags = FREECOL;
273 :
274 9 : if ((size_t) co == cm->max)
275 : {
276 7 : while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
277 3 : cm->max--;
278 2 : assert(cm->free >= 0);
279 5 : while ((size_t) cm->free > cm->max)
280 1 : cm->free = cm->cd[cm->free].sub;
281 2 : if (cm->free > 0)
282 : {
283 0 : assert(cm->free < cm->max);
284 0 : pco = cm->free;
285 0 : nco = cm->cd[pco].sub;
286 0 : while (nco > 0)
287 0 : if ((size_t) nco > cm->max)
288 : {
289 : /* take this one out of freelist */
290 0 : nco = cm->cd[nco].sub;
291 0 : cm->cd[pco].sub = nco;
292 : }
293 : else
294 : {
295 0 : assert(nco < cm->max);
296 0 : pco = nco;
297 0 : nco = cm->cd[pco].sub;
298 : }
299 : }
300 : }
301 : else
302 : {
303 7 : cd->sub = cm->free;
304 7 : cm->free = (color) (cd - cm->cd);
305 : }
306 : }
307 :
308 : /*
309 : * pseudocolor - allocate a false color, to be managed by other means
310 : */
311 : static color
312 992 : pseudocolor(struct colormap *cm)
313 : {
314 : color co;
315 : struct colordesc *cd;
316 :
317 992 : co = newcolor(cm);
318 992 : if (CISERR())
319 0 : return COLORLESS;
320 992 : cd = &cm->cd[co];
321 992 : cd->nschrs = 0;
322 992 : cd->nuchrs = 1; /* pretend it is in the upper map */
323 992 : cd->sub = NOSUB;
324 992 : cd->arcs = NULL;
325 992 : cd->firstchr = CHR_MIN;
326 992 : cd->flags = PSEUDO;
327 992 : return co;
328 : }
329 :
330 : /*
331 : * subcolor - allocate a new subcolor (if necessary) to this chr
332 : *
333 : * This works only for chrs that map into the low color map.
334 : */
335 : static color
336 19869 : subcolor(struct colormap *cm, chr c)
337 : {
338 : color co; /* current color of c */
339 : color sco; /* new subcolor */
340 :
341 19869 : assert(c <= MAX_SIMPLE_CHR);
342 :
343 19869 : co = cm->locolormap[c - CHR_MIN];
344 19869 : sco = newsub(cm, co);
345 19869 : if (CISERR())
346 0 : return COLORLESS;
347 19869 : assert(sco != COLORLESS);
348 :
349 19869 : if (co == sco) /* already in an open subcolor */
350 3577 : return co; /* rest is redundant */
351 16292 : cm->cd[co].nschrs--;
352 16292 : if (cm->cd[sco].nschrs == 0)
353 1482 : cm->cd[sco].firstchr = c;
354 16292 : cm->cd[sco].nschrs++;
355 16292 : cm->locolormap[c - CHR_MIN] = sco;
356 16292 : return sco;
357 : }
358 :
359 : /*
360 : * subcolorhi - allocate a new subcolor (if necessary) to this colormap entry
361 : *
362 : * This is the same processing as subcolor(), but for entries in the high
363 : * colormap, which do not necessarily correspond to exactly one chr code.
364 : */
365 : static color
366 18 : subcolorhi(struct colormap *cm, color *pco)
367 : {
368 : color co; /* current color of entry */
369 : color sco; /* new subcolor */
370 :
371 18 : co = *pco;
372 18 : sco = newsub(cm, co);
373 18 : if (CISERR())
374 0 : return COLORLESS;
375 18 : assert(sco != COLORLESS);
376 :
377 18 : if (co == sco) /* already in an open subcolor */
378 0 : return co; /* rest is redundant */
379 18 : cm->cd[co].nuchrs--;
380 18 : cm->cd[sco].nuchrs++;
381 18 : *pco = sco;
382 18 : return sco;
383 : }
384 :
385 : /*
386 : * newsub - allocate a new subcolor (if necessary) for a color
387 : */
388 : static color
389 19887 : newsub(struct colormap *cm,
390 : color co)
391 : {
392 : color sco; /* new subcolor */
393 :
394 19887 : sco = cm->cd[co].sub;
395 19887 : if (sco == NOSUB)
396 : { /* color has no open subcolor */
397 : /* optimization: singly-referenced color need not be subcolored */
398 5059 : if ((cm->cd[co].nschrs + cm->cd[co].nuchrs) == 1)
399 3577 : return co;
400 1482 : sco = newcolor(cm); /* must create subcolor */
401 1482 : if (sco == COLORLESS)
402 : {
403 0 : assert(CISERR());
404 0 : return COLORLESS;
405 : }
406 1482 : cm->cd[co].sub = sco;
407 1482 : cm->cd[sco].sub = sco; /* open subcolor points to self */
408 : }
409 16310 : assert(sco != NOSUB);
410 :
411 16310 : return sco;
412 : }
413 :
414 : /*
415 : * newhicolorrow - get a new row in the hicolormap, cloning it from oldrow
416 : *
417 : * Returns array index of new row. Note the array might move.
418 : */
419 : static int
420 0 : newhicolorrow(struct colormap *cm,
421 : int oldrow)
422 : {
423 0 : int newrow = cm->hiarrayrows;
424 : color *newrowptr;
425 : int i;
426 :
427 : /* Assign a fresh array row index, enlarging storage if needed */
428 0 : if (newrow >= cm->maxarrayrows)
429 : {
430 : color *newarray;
431 :
432 0 : if (cm->maxarrayrows >= INT_MAX / (cm->hiarraycols * 2))
433 : {
434 0 : CERR(REG_ESPACE);
435 0 : return 0;
436 : }
437 0 : newarray = (color *) REALLOC(cm->hicolormap,
438 : cm->maxarrayrows * 2 *
439 : cm->hiarraycols * sizeof(color));
440 0 : if (newarray == NULL)
441 : {
442 0 : CERR(REG_ESPACE);
443 0 : return 0;
444 : }
445 0 : cm->hicolormap = newarray;
446 0 : cm->maxarrayrows *= 2;
447 : }
448 0 : cm->hiarrayrows++;
449 :
450 : /* Copy old row data */
451 0 : newrowptr = &cm->hicolormap[newrow * cm->hiarraycols];
452 0 : memcpy(newrowptr,
453 0 : &cm->hicolormap[oldrow * cm->hiarraycols],
454 0 : cm->hiarraycols * sizeof(color));
455 :
456 : /* Increase color reference counts to reflect new colormap entries */
457 0 : for (i = 0; i < cm->hiarraycols; i++)
458 0 : cm->cd[newrowptr[i]].nuchrs++;
459 :
460 0 : return newrow;
461 : }
462 :
463 : /*
464 : * newhicolorcols - create a new set of columns in the high colormap
465 : *
466 : * Essentially, extends the 2-D array to the right with a copy of itself.
467 : */
468 : static void
469 15 : newhicolorcols(struct colormap *cm)
470 : {
471 : color *newarray;
472 : int r,
473 : c;
474 :
475 15 : if (cm->hiarraycols >= INT_MAX / (cm->maxarrayrows * 2))
476 : {
477 0 : CERR(REG_ESPACE);
478 0 : return;
479 : }
480 15 : newarray = (color *) REALLOC(cm->hicolormap,
481 : cm->maxarrayrows *
482 : cm->hiarraycols * 2 * sizeof(color));
483 15 : if (newarray == NULL)
484 : {
485 0 : CERR(REG_ESPACE);
486 0 : return;
487 : }
488 15 : cm->hicolormap = newarray;
489 :
490 : /* Duplicate existing columns to the right, and increase ref counts */
491 : /* Must work backwards in the array because we realloc'd in place */
492 30 : for (r = cm->hiarrayrows - 1; r >= 0; r--)
493 : {
494 15 : color *oldrowptr = &newarray[r * cm->hiarraycols];
495 15 : color *newrowptr = &newarray[r * cm->hiarraycols * 2];
496 15 : color *newrowptr2 = newrowptr + cm->hiarraycols;
497 :
498 30 : for (c = 0; c < cm->hiarraycols; c++)
499 : {
500 15 : color co = oldrowptr[c];
501 :
502 15 : newrowptr[c] = newrowptr2[c] = co;
503 15 : cm->cd[co].nuchrs++;
504 : }
505 : }
506 :
507 15 : cm->hiarraycols *= 2;
508 : }
509 :
510 : /*
511 : * subcolorcvec - allocate new subcolors to cvec members, fill in arcs
512 : *
513 : * For each chr "c" represented by the cvec, do the equivalent of
514 : * newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp);
515 : *
516 : * Note that in typical cases, many of the subcolors are the same.
517 : * While newarc() would discard duplicate arc requests, we can save
518 : * some cycles by not calling it repetitively to begin with. This is
519 : * mechanized with the "lastsubcolor" state variable.
520 : */
521 : static void
522 48 : subcolorcvec(struct vars *v,
523 : struct cvec *cv,
524 : struct state *lp,
525 : struct state *rp)
526 : {
527 48 : struct colormap *cm = v->cm;
528 48 : color lastsubcolor = COLORLESS;
529 : chr ch,
530 : from,
531 : to;
532 : const chr *p;
533 : int i;
534 :
535 : /* ordinary characters */
536 212 : for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--)
537 : {
538 164 : ch = *p;
539 164 : subcoloronechr(v, ch, lp, rp, &lastsubcolor);
540 164 : NOERR();
541 : }
542 :
543 : /* and the ranges */
544 380 : for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--)
545 : {
546 332 : from = *p;
547 332 : to = *(p + 1);
548 332 : if (from <= MAX_SIMPLE_CHR)
549 : {
550 : /* deal with simple chars one at a time */
551 332 : chr lim = (to <= MAX_SIMPLE_CHR) ? to : MAX_SIMPLE_CHR;
552 :
553 15381 : while (from <= lim)
554 : {
555 14717 : color sco = subcolor(cm, from);
556 :
557 14717 : NOERR();
558 14717 : if (sco != lastsubcolor)
559 : {
560 99 : newarc(v->nfa, PLAIN, sco, lp, rp);
561 99 : NOERR();
562 99 : lastsubcolor = sco;
563 : }
564 14717 : from++;
565 : }
566 : }
567 : /* deal with any part of the range that's above MAX_SIMPLE_CHR */
568 332 : if (from < to)
569 0 : subcoloronerange(v, from, to, lp, rp, &lastsubcolor);
570 332 : else if (from == to)
571 0 : subcoloronechr(v, from, lp, rp, &lastsubcolor);
572 332 : NOERR();
573 : }
574 :
575 : /* and deal with cclass if any */
576 48 : if (cv->cclasscode >= 0)
577 : {
578 : int classbit;
579 : color *pco;
580 : int r,
581 : c;
582 :
583 : /* Enlarge array if we don't have a column bit assignment for cclass */
584 18 : if (cm->classbits[cv->cclasscode] == 0)
585 : {
586 15 : cm->classbits[cv->cclasscode] = cm->hiarraycols;
587 15 : newhicolorcols(cm);
588 15 : NOERR();
589 : }
590 : /* Apply subcolorhi() and make arc for each entry in relevant cols */
591 18 : classbit = cm->classbits[cv->cclasscode];
592 18 : pco = cm->hicolormap;
593 36 : for (r = 0; r < cm->hiarrayrows; r++)
594 : {
595 54 : for (c = 0; c < cm->hiarraycols; c++)
596 : {
597 36 : if (c & classbit)
598 : {
599 18 : color sco = subcolorhi(cm, pco);
600 :
601 18 : NOERR();
602 : /* add the arc if needed */
603 18 : if (sco != lastsubcolor)
604 : {
605 0 : newarc(v->nfa, PLAIN, sco, lp, rp);
606 0 : NOERR();
607 0 : lastsubcolor = sco;
608 : }
609 : }
610 36 : pco++;
611 : }
612 : }
613 : }
614 : }
615 :
616 : /*
617 : * subcoloronechr - do subcolorcvec's work for a singleton chr
618 : *
619 : * We could just let subcoloronerange do this, but it's a bit more efficient
620 : * if we exploit the single-chr case. Also, callers find it useful for this
621 : * to be able to handle both low and high chr codes.
622 : */
623 : static void
624 5147 : subcoloronechr(struct vars *v,
625 : chr ch,
626 : struct state *lp,
627 : struct state *rp,
628 : color *lastsubcolor)
629 : {
630 5147 : struct colormap *cm = v->cm;
631 : colormaprange *newranges;
632 : int numnewranges;
633 : colormaprange *oldrange;
634 : int oldrangen;
635 : int newrow;
636 :
637 : /* Easy case for low chr codes */
638 5147 : if (ch <= MAX_SIMPLE_CHR)
639 : {
640 5147 : color sco = subcolor(cm, ch);
641 :
642 5147 : NOERR();
643 5147 : if (sco != *lastsubcolor)
644 : {
645 5012 : newarc(v->nfa, PLAIN, sco, lp, rp);
646 5012 : *lastsubcolor = sco;
647 : }
648 5147 : return;
649 : }
650 :
651 : /*
652 : * Potentially, we could need two more colormapranges than we have now, if
653 : * the given chr is in the middle of some existing range.
654 : */
655 0 : newranges = (colormaprange *)
656 0 : MALLOC((cm->numcmranges + 2) * sizeof(colormaprange));
657 0 : if (newranges == NULL)
658 : {
659 0 : CERR(REG_ESPACE);
660 0 : return;
661 : }
662 0 : numnewranges = 0;
663 :
664 : /* Ranges before target are unchanged */
665 0 : for (oldrange = cm->cmranges, oldrangen = 0;
666 0 : oldrangen < cm->numcmranges;
667 0 : oldrange++, oldrangen++)
668 : {
669 0 : if (oldrange->cmax >= ch)
670 0 : break;
671 0 : newranges[numnewranges++] = *oldrange;
672 : }
673 :
674 : /* Match target chr against current range */
675 0 : if (oldrangen >= cm->numcmranges || oldrange->cmin > ch)
676 : {
677 : /* chr does not belong to any existing range, make a new one */
678 0 : newranges[numnewranges].cmin = ch;
679 0 : newranges[numnewranges].cmax = ch;
680 : /* row state should be cloned from the "all others" row */
681 0 : newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
682 0 : numnewranges++;
683 : }
684 0 : else if (oldrange->cmin == oldrange->cmax)
685 : {
686 : /* we have an existing singleton range matching the chr */
687 0 : newranges[numnewranges++] = *oldrange;
688 0 : newrow = oldrange->rownum;
689 : /* we've now fully processed this old range */
690 0 : oldrange++, oldrangen++;
691 : }
692 : else
693 : {
694 : /* chr is a subset of this existing range, must split it */
695 0 : if (ch > oldrange->cmin)
696 : {
697 : /* emit portion of old range before chr */
698 0 : newranges[numnewranges].cmin = oldrange->cmin;
699 0 : newranges[numnewranges].cmax = ch - 1;
700 0 : newranges[numnewranges].rownum = oldrange->rownum;
701 0 : numnewranges++;
702 : }
703 : /* emit chr as singleton range, initially cloning from range */
704 0 : newranges[numnewranges].cmin = ch;
705 0 : newranges[numnewranges].cmax = ch;
706 0 : newranges[numnewranges].rownum = newrow =
707 0 : newhicolorrow(cm, oldrange->rownum);
708 0 : numnewranges++;
709 0 : if (ch < oldrange->cmax)
710 : {
711 : /* emit portion of old range after chr */
712 0 : newranges[numnewranges].cmin = ch + 1;
713 0 : newranges[numnewranges].cmax = oldrange->cmax;
714 : /* must clone the row if we are making two new ranges from old */
715 0 : newranges[numnewranges].rownum =
716 0 : (ch > oldrange->cmin) ? newhicolorrow(cm, oldrange->rownum) :
717 : oldrange->rownum;
718 0 : numnewranges++;
719 : }
720 : /* we've now fully processed this old range */
721 0 : oldrange++, oldrangen++;
722 : }
723 :
724 : /* Update colors in newrow and create arcs as needed */
725 0 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
726 :
727 : /* Ranges after target are unchanged */
728 0 : for (; oldrangen < cm->numcmranges; oldrange++, oldrangen++)
729 : {
730 0 : newranges[numnewranges++] = *oldrange;
731 : }
732 :
733 : /* Assert our original space estimate was adequate */
734 0 : assert(numnewranges <= (cm->numcmranges + 2));
735 :
736 : /* And finally, store back the updated list of ranges */
737 0 : if (cm->cmranges != NULL)
738 0 : FREE(cm->cmranges);
739 0 : cm->cmranges = newranges;
740 0 : cm->numcmranges = numnewranges;
741 : }
742 :
743 : /*
744 : * subcoloronerange - do subcolorcvec's work for a high range
745 : */
746 : static void
747 0 : subcoloronerange(struct vars *v,
748 : chr from,
749 : chr to,
750 : struct state *lp,
751 : struct state *rp,
752 : color *lastsubcolor)
753 : {
754 0 : struct colormap *cm = v->cm;
755 : colormaprange *newranges;
756 : int numnewranges;
757 : colormaprange *oldrange;
758 : int oldrangen;
759 : int newrow;
760 :
761 : /* Caller should take care of non-high-range cases */
762 0 : assert(from > MAX_SIMPLE_CHR);
763 0 : assert(from < to);
764 :
765 : /*
766 : * Potentially, if we have N non-adjacent ranges, we could need as many as
767 : * 2N+1 result ranges (consider case where new range spans 'em all).
768 : */
769 0 : newranges = (colormaprange *)
770 0 : MALLOC((cm->numcmranges * 2 + 1) * sizeof(colormaprange));
771 0 : if (newranges == NULL)
772 : {
773 0 : CERR(REG_ESPACE);
774 0 : return;
775 : }
776 0 : numnewranges = 0;
777 :
778 : /* Ranges before target are unchanged */
779 0 : for (oldrange = cm->cmranges, oldrangen = 0;
780 0 : oldrangen < cm->numcmranges;
781 0 : oldrange++, oldrangen++)
782 : {
783 0 : if (oldrange->cmax >= from)
784 0 : break;
785 0 : newranges[numnewranges++] = *oldrange;
786 : }
787 :
788 : /*
789 : * Deal with ranges that (partially) overlap the target. As we process
790 : * each such range, increase "from" to remove the dealt-with characters
791 : * from the target range.
792 : */
793 0 : while (oldrangen < cm->numcmranges && oldrange->cmin <= to)
794 : {
795 0 : if (from < oldrange->cmin)
796 : {
797 : /* Handle portion of new range that corresponds to no old range */
798 0 : newranges[numnewranges].cmin = from;
799 0 : newranges[numnewranges].cmax = oldrange->cmin - 1;
800 : /* row state should be cloned from the "all others" row */
801 0 : newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
802 0 : numnewranges++;
803 : /* Update colors in newrow and create arcs as needed */
804 0 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
805 : /* We've now fully processed the part of new range before old */
806 0 : from = oldrange->cmin;
807 : }
808 :
809 0 : if (from <= oldrange->cmin && to >= oldrange->cmax)
810 : {
811 : /* old range is fully contained in new, process it in-place */
812 0 : newranges[numnewranges++] = *oldrange;
813 0 : newrow = oldrange->rownum;
814 0 : from = oldrange->cmax + 1;
815 : }
816 : else
817 : {
818 : /* some part of old range does not overlap new range */
819 0 : if (from > oldrange->cmin)
820 : {
821 : /* emit portion of old range before new range */
822 0 : newranges[numnewranges].cmin = oldrange->cmin;
823 0 : newranges[numnewranges].cmax = from - 1;
824 0 : newranges[numnewranges].rownum = oldrange->rownum;
825 0 : numnewranges++;
826 : }
827 : /* emit common subrange, initially cloning from old range */
828 0 : newranges[numnewranges].cmin = from;
829 0 : newranges[numnewranges].cmax =
830 0 : (to < oldrange->cmax) ? to : oldrange->cmax;
831 0 : newranges[numnewranges].rownum = newrow =
832 0 : newhicolorrow(cm, oldrange->rownum);
833 0 : numnewranges++;
834 0 : if (to < oldrange->cmax)
835 : {
836 : /* emit portion of old range after new range */
837 0 : newranges[numnewranges].cmin = to + 1;
838 0 : newranges[numnewranges].cmax = oldrange->cmax;
839 : /* must clone the row if we are making two new ranges from old */
840 0 : newranges[numnewranges].rownum =
841 0 : (from > oldrange->cmin) ? newhicolorrow(cm, oldrange->rownum) :
842 : oldrange->rownum;
843 0 : numnewranges++;
844 : }
845 0 : from = oldrange->cmax + 1;
846 : }
847 : /* Update colors in newrow and create arcs as needed */
848 0 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
849 : /* we've now fully processed this old range */
850 0 : oldrange++, oldrangen++;
851 : }
852 :
853 0 : if (from <= to)
854 : {
855 : /* Handle portion of new range that corresponds to no old range */
856 0 : newranges[numnewranges].cmin = from;
857 0 : newranges[numnewranges].cmax = to;
858 : /* row state should be cloned from the "all others" row */
859 0 : newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
860 0 : numnewranges++;
861 : /* Update colors in newrow and create arcs as needed */
862 0 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
863 : }
864 :
865 : /* Ranges after target are unchanged */
866 0 : for (; oldrangen < cm->numcmranges; oldrange++, oldrangen++)
867 : {
868 0 : newranges[numnewranges++] = *oldrange;
869 : }
870 :
871 : /* Assert our original space estimate was adequate */
872 0 : assert(numnewranges <= (cm->numcmranges * 2 + 1));
873 :
874 : /* And finally, store back the updated list of ranges */
875 0 : if (cm->cmranges != NULL)
876 0 : FREE(cm->cmranges);
877 0 : cm->cmranges = newranges;
878 0 : cm->numcmranges = numnewranges;
879 : }
880 :
881 : /*
882 : * subcoloronerow - do subcolorcvec's work for one new row in the high colormap
883 : */
884 : static void
885 0 : subcoloronerow(struct vars *v,
886 : int rownum,
887 : struct state *lp,
888 : struct state *rp,
889 : color *lastsubcolor)
890 : {
891 0 : struct colormap *cm = v->cm;
892 : color *pco;
893 : int i;
894 :
895 : /* Apply subcolorhi() and make arc for each entry in row */
896 0 : pco = &cm->hicolormap[rownum * cm->hiarraycols];
897 0 : for (i = 0; i < cm->hiarraycols; pco++, i++)
898 : {
899 0 : color sco = subcolorhi(cm, pco);
900 :
901 0 : NOERR();
902 : /* make the arc if needed */
903 0 : if (sco != *lastsubcolor)
904 : {
905 0 : newarc(v->nfa, PLAIN, sco, lp, rp);
906 0 : NOERR();
907 0 : *lastsubcolor = sco;
908 : }
909 : }
910 : }
911 :
912 : /*
913 : * okcolors - promote subcolors to full colors
914 : */
915 : static void
916 5003 : okcolors(struct nfa *nfa,
917 : struct colormap *cm)
918 : {
919 : struct colordesc *cd;
920 5003 : struct colordesc *end = CDEND(cm);
921 : struct colordesc *scd;
922 : struct arc *a;
923 : color co;
924 : color sco;
925 :
926 30074 : for (cd = cm->cd, co = 0; cd < end; cd++, co++)
927 : {
928 25071 : sco = cd->sub;
929 25071 : if (UNUSEDCOLOR(cd) || sco == NOSUB)
930 : {
931 : /* has no subcolor, no further action */
932 : }
933 1486 : else if (sco == co)
934 : {
935 : /* is subcolor, let parent deal with it */
936 : }
937 1482 : else if (cd->nschrs == 0 && cd->nuchrs == 0)
938 : {
939 : /* parent empty, its arcs change color to subcolor */
940 9 : cd->sub = NOSUB;
941 9 : scd = &cm->cd[sco];
942 9 : assert(scd->nschrs > 0 || scd->nuchrs > 0);
943 9 : assert(scd->sub == sco);
944 9 : scd->sub = NOSUB;
945 56 : while ((a = cd->arcs) != NULL)
946 : {
947 38 : assert(a->co == co);
948 38 : uncolorchain(cm, a);
949 38 : a->co = sco;
950 38 : colorchain(cm, a);
951 : }
952 9 : freecolor(cm, co);
953 : }
954 : else
955 : {
956 : /* parent's arcs must gain parallel subcolor arcs */
957 1473 : cd->sub = NOSUB;
958 1473 : scd = &cm->cd[sco];
959 1473 : assert(scd->nschrs > 0 || scd->nuchrs > 0);
960 1473 : assert(scd->sub == sco);
961 1473 : scd->sub = NOSUB;
962 4468 : for (a = cd->arcs; a != NULL; a = a->colorchain)
963 : {
964 2995 : assert(a->co == co);
965 2995 : newarc(nfa, a->type, sco, a->from, a->to);
966 : }
967 : }
968 : }
969 5003 : }
970 :
971 : /*
972 : * colorchain - add this arc to the color chain of its color
973 : */
974 : static void
975 31367 : colorchain(struct colormap *cm,
976 : struct arc *a)
977 : {
978 31367 : struct colordesc *cd = &cm->cd[a->co];
979 :
980 31367 : if (cd->arcs != NULL)
981 28960 : cd->arcs->colorchainRev = a;
982 31367 : a->colorchain = cd->arcs;
983 31367 : a->colorchainRev = NULL;
984 31367 : cd->arcs = a;
985 31367 : }
986 :
987 : /*
988 : * uncolorchain - delete this arc from the color chain of its color
989 : */
990 : static void
991 22555 : uncolorchain(struct colormap *cm,
992 : struct arc *a)
993 : {
994 22555 : struct colordesc *cd = &cm->cd[a->co];
995 22555 : struct arc *aa = a->colorchainRev;
996 :
997 22555 : if (aa == NULL)
998 : {
999 5612 : assert(cd->arcs == a);
1000 5612 : cd->arcs = a->colorchain;
1001 : }
1002 : else
1003 : {
1004 16943 : assert(aa->colorchain == a);
1005 16943 : aa->colorchain = a->colorchain;
1006 : }
1007 22555 : if (a->colorchain != NULL)
1008 19325 : a->colorchain->colorchainRev = aa;
1009 22555 : a->colorchain = NULL; /* paranoia */
1010 22555 : a->colorchainRev = NULL;
1011 22555 : }
1012 :
1013 : /*
1014 : * rainbow - add arcs of all full colors (but one) between specified states
1015 : */
1016 : static void
1017 3680 : rainbow(struct nfa *nfa,
1018 : struct colormap *cm,
1019 : int type,
1020 : color but, /* COLORLESS if no exceptions */
1021 : struct state *from,
1022 : struct state *to)
1023 : {
1024 : struct colordesc *cd;
1025 3680 : struct colordesc *end = CDEND(cm);
1026 : color co;
1027 :
1028 38456 : for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
1029 69549 : if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
1030 34773 : !(cd->flags & PSEUDO))
1031 22185 : newarc(nfa, type, co, from, to);
1032 3680 : }
1033 :
1034 : /*
1035 : * colorcomplement - add arcs of complementary colors
1036 : *
1037 : * The calling sequence ought to be reconciled with cloneouts().
1038 : */
1039 : static void
1040 20 : colorcomplement(struct nfa *nfa,
1041 : struct colormap *cm,
1042 : int type,
1043 : struct state *of, /* complements of this guy's PLAIN outarcs */
1044 : struct state *from,
1045 : struct state *to)
1046 : {
1047 : struct colordesc *cd;
1048 20 : struct colordesc *end = CDEND(cm);
1049 : color co;
1050 :
1051 20 : assert(of != from);
1052 91 : for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
1053 71 : if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
1054 71 : if (findarc(of, PLAIN, co) == NULL)
1055 32 : newarc(nfa, type, co, from, to);
1056 20 : }
1057 :
1058 :
1059 : #ifdef REG_DEBUG
1060 :
1061 : /*
1062 : * dumpcolors - debugging output
1063 : */
1064 : static void
1065 : dumpcolors(struct colormap *cm,
1066 : FILE *f)
1067 : {
1068 : struct colordesc *cd;
1069 : struct colordesc *end;
1070 : color co;
1071 : chr c;
1072 :
1073 : fprintf(f, "max %ld\n", (long) cm->max);
1074 : end = CDEND(cm);
1075 : for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
1076 : {
1077 : if (!UNUSEDCOLOR(cd))
1078 : {
1079 : assert(cd->nschrs > 0 || cd->nuchrs > 0);
1080 : if (cd->flags & PSEUDO)
1081 : fprintf(f, "#%2ld(ps): ", (long) co);
1082 : else
1083 : fprintf(f, "#%2ld(%2d): ", (long) co, cd->nschrs + cd->nuchrs);
1084 :
1085 : /*
1086 : * Unfortunately, it's hard to do this next bit more efficiently.
1087 : */
1088 : for (c = CHR_MIN; c <= MAX_SIMPLE_CHR; c++)
1089 : if (GETCOLOR(cm, c) == co)
1090 : dumpchr(c, f);
1091 : fprintf(f, "\n");
1092 : }
1093 : }
1094 : /* dump the high colormap if it contains anything interesting */
1095 : if (cm->hiarrayrows > 1 || cm->hiarraycols > 1)
1096 : {
1097 : int r,
1098 : c;
1099 : const color *rowptr;
1100 :
1101 : fprintf(f, "other:\t");
1102 : for (c = 0; c < cm->hiarraycols; c++)
1103 : {
1104 : fprintf(f, "\t%ld", (long) cm->hicolormap[c]);
1105 : }
1106 : fprintf(f, "\n");
1107 : for (r = 0; r < cm->numcmranges; r++)
1108 : {
1109 : dumpchr(cm->cmranges[r].cmin, f);
1110 : fprintf(f, "..");
1111 : dumpchr(cm->cmranges[r].cmax, f);
1112 : fprintf(f, ":");
1113 : rowptr = &cm->hicolormap[cm->cmranges[r].rownum * cm->hiarraycols];
1114 : for (c = 0; c < cm->hiarraycols; c++)
1115 : {
1116 : fprintf(f, "\t%ld", (long) rowptr[c]);
1117 : }
1118 : fprintf(f, "\n");
1119 : }
1120 : }
1121 : }
1122 :
1123 : /*
1124 : * dumpchr - print a chr
1125 : *
1126 : * Kind of char-centric but works well enough for debug use.
1127 : */
1128 : static void
1129 : dumpchr(chr c,
1130 : FILE *f)
1131 : {
1132 : if (c == '\\')
1133 : fprintf(f, "\\\\");
1134 : else if (c > ' ' && c <= '~')
1135 : putc((char) c, f);
1136 : else
1137 : fprintf(f, "\\u%04lx", (long) c);
1138 : }
1139 :
1140 : #endif /* REG_DEBUG */
|
