Age Owner Branch data TLA 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
2489 tgl@sss.pgh.pa.us 49 :CBC 3610 : initcm(struct vars *v,
50 : : struct colormap *cm)
51 : : {
52 : : struct colordesc *cd;
53 : :
7739 54 : 3610 : cm->magic = CMMAGIC;
55 : 3610 : cm->v = v;
56 : :
57 : 3610 : cm->ncds = NINLINECDS;
58 : 3610 : cm->cd = cm->cdspace;
59 : 3610 : cm->max = 0;
60 : 3610 : cm->free = 0;
61 : :
7559 bruce@momjian.us 62 : 3610 : cd = cm->cd; /* cm->cd[WHITE] */
2778 tgl@sss.pgh.pa.us 63 : 3610 : cd->nschrs = MAX_SIMPLE_CHR - CHR_MIN + 1;
64 : 3610 : cd->nuchrs = 1;
7739 65 : 3610 : cd->sub = NOSUB;
66 : 3610 : cd->arcs = NULL;
4296 67 : 3610 : cd->firstchr = CHR_MIN;
68 : 3610 : cd->flags = 0;
69 : :
2778 70 : 3610 : cm->locolormap = (color *)
71 : 3610 : MALLOC((MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
72 [ - + ]: 3610 : if (cm->locolormap == NULL)
73 : : {
2778 tgl@sss.pgh.pa.us 74 [ # # ]:UBC 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: */
2778 tgl@sss.pgh.pa.us 80 :CBC 3610 : memset(cm->locolormap, WHITE,
81 : : (MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
82 : :
83 : 3610 : memset(cm->classbits, 0, sizeof(cm->classbits));
84 : 3610 : cm->numcmranges = 0;
85 : 3610 : cm->cmranges = NULL;
86 : 3610 : cm->maxarrayrows = 4; /* arbitrary initial allocation */
87 : 3610 : cm->hiarrayrows = 1; /* but we have only one row/col initially */
88 : 3610 : cm->hiarraycols = 1;
89 : 3610 : cm->hicolormap = (color *) MALLOC(cm->maxarrayrows * sizeof(color));
90 [ - + ]: 3610 : if (cm->hicolormap == NULL)
91 : : {
2778 tgl@sss.pgh.pa.us 92 [ # # ]:UBC 0 : CERR(REG_ESPACE);
93 : 0 : return;
94 : : }
95 : : /* initialize the "all other characters" row to WHITE */
2778 tgl@sss.pgh.pa.us 96 :CBC 3610 : cm->hicolormap[0] = WHITE;
97 : : }
98 : :
99 : : /*
100 : : * freecm - free dynamically-allocated things in a colormap
101 : : */
102 : : static void
2489 103 : 770 : freecm(struct colormap *cm)
104 : : {
7739 105 : 770 : cm->magic = 0;
106 [ + + ]: 770 : if (cm->cd != cm->cdspace)
107 : 60 : FREE(cm->cd);
2778 108 [ + - ]: 770 : if (cm->locolormap != NULL)
109 : 770 : FREE(cm->locolormap);
110 [ + + ]: 770 : if (cm->cmranges != NULL)
111 : 8 : FREE(cm->cmranges);
112 [ + - ]: 770 : if (cm->hicolormap != NULL)
113 : 770 : FREE(cm->hicolormap);
7739 114 : 770 : }
115 : :
116 : : /*
117 : : * pg_reg_getcolor - slow case of GETCOLOR()
118 : : */
119 : : color
2489 120 : 58 : 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 */
2778 128 [ - + ]: 58 : 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 : 58 : rownum = 0; /* if no match, use array row zero */
135 : 58 : low = 0;
136 : 58 : high = cm->numcmranges;
137 [ + + ]: 91 : while (low < high)
138 : : {
139 : 56 : int middle = low + (high - low) / 2;
140 : 56 : const colormaprange *cmr = &cm->cmranges[middle];
141 : :
142 [ + + ]: 56 : if (c < cmr->cmin)
143 : 28 : high = middle;
144 [ + + ]: 28 : else if (c > cmr->cmax)
145 : 5 : low = middle + 1;
146 : : else
147 : : {
2489 148 : 23 : rownum = cmr->rownum; /* found a match */
2778 149 : 23 : break;
150 : : }
151 : : }
152 : :
153 : : /*
154 : : * Find which column it's in --- this is all locale-dependent.
155 : : */
156 [ + + ]: 58 : if (cm->hiarraycols > 1)
157 : : {
158 : 35 : colnum = cclass_column_index(cm, c);
159 : 35 : return cm->hicolormap[rownum * cm->hiarraycols + colnum];
160 : : }
161 : : else
162 : : {
163 : : /* fast path if no relevant cclasses */
164 : 23 : return cm->hicolormap[rownum];
165 : : }
166 : : }
167 : :
168 : : /*
169 : : * maxcolor - report largest color number in use
170 : : */
171 : : static color
2489 172 : 8883 : maxcolor(struct colormap *cm)
173 : : {
7739 174 [ - + ]: 8883 : if (CISERR())
7739 tgl@sss.pgh.pa.us 175 :UBC 0 : return COLORLESS;
176 : :
7559 bruce@momjian.us 177 :CBC 8883 : 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 */
2489 tgl@sss.pgh.pa.us 185 : 34965 : newcolor(struct colormap *cm)
186 : : {
187 : : struct colordesc *cd;
188 : : size_t n;
189 : :
7739 190 [ + + ]: 34965 : if (CISERR())
191 : 2 : return COLORLESS;
192 : :
7559 bruce@momjian.us 193 [ + + ]: 34963 : if (cm->free != 0)
194 : : {
7739 tgl@sss.pgh.pa.us 195 [ - + ]: 157 : assert(cm->free > 0);
7559 bruce@momjian.us 196 [ - + ]: 157 : assert((size_t) cm->free < cm->ncds);
7739 tgl@sss.pgh.pa.us 197 : 157 : cd = &cm->cd[cm->free];
198 [ - + ]: 157 : assert(UNUSEDCOLOR(cd));
199 [ - + ]: 157 : assert(cd->arcs == NULL);
200 : 157 : cm->free = cd->sub;
201 : : }
7559 bruce@momjian.us 202 [ + + ]: 34806 : else if (cm->max < cm->ncds - 1)
203 : : {
7739 tgl@sss.pgh.pa.us 204 : 32954 : cm->max++;
205 : 32954 : cd = &cm->cd[cm->max];
206 : : }
207 : : else
208 : : {
209 : : /* oops, must allocate more */
210 : : struct colordesc *newCd;
211 : :
4028 heikki.linnakangas@i 212 [ - + ]: 1852 : if (cm->max == MAX_COLOR)
213 : : {
4028 heikki.linnakangas@i 214 [ # # ]:UBC 0 : CERR(REG_ECOLORS);
215 : 0 : return COLORLESS; /* too many colors */
216 : : }
217 : :
7739 tgl@sss.pgh.pa.us 218 :CBC 1852 : n = cm->ncds * 2;
4028 heikki.linnakangas@i 219 [ - + ]: 1852 : if (n > MAX_COLOR + 1)
4028 heikki.linnakangas@i 220 :UBC 0 : n = MAX_COLOR + 1;
7559 bruce@momjian.us 221 [ + + ]:CBC 1852 : if (cm->cd == cm->cdspace)
222 : : {
5904 tgl@sss.pgh.pa.us 223 : 1804 : newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
224 [ + - ]: 1804 : if (newCd != NULL)
225 : 1804 : memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
226 : : sizeof(struct colordesc));
227 : : }
228 : : else
229 : : newCd = (struct colordesc *)
230 : 48 : REALLOC(cm->cd, n * sizeof(struct colordesc));
231 [ - + ]: 1852 : if (newCd == NULL)
232 : : {
7739 tgl@sss.pgh.pa.us 233 [ # # ]:UBC 0 : CERR(REG_ESPACE);
234 : 0 : return COLORLESS;
235 : : }
5904 tgl@sss.pgh.pa.us 236 :CBC 1852 : cm->cd = newCd;
7739 237 : 1852 : cm->ncds = n;
238 [ - + ]: 1852 : assert(cm->max < cm->ncds - 1);
239 : 1852 : cm->max++;
240 : 1852 : cd = &cm->cd[cm->max];
241 : : }
242 : :
2778 243 : 34963 : cd->nschrs = 0;
244 : 34963 : cd->nuchrs = 0;
7739 245 : 34963 : cd->sub = NOSUB;
246 : 34963 : cd->arcs = NULL;
4296 247 : 34963 : cd->firstchr = CHR_MIN; /* in case never set otherwise */
7739 248 : 34963 : cd->flags = 0;
249 : :
7559 bruce@momjian.us 250 : 34963 : return (color) (cd - cm->cd);
251 : : }
252 : :
253 : : /*
254 : : * freecolor - free a color (must have no arcs or subcolor)
255 : : */
256 : : static void
2489 tgl@sss.pgh.pa.us 257 : 198 : freecolor(struct colormap *cm,
258 : : color co)
259 : : {
7739 260 : 198 : struct colordesc *cd = &cm->cd[co];
261 : : color pco,
262 : : nco; /* for freelist scan */
263 : :
264 [ - + ]: 198 : assert(co >= 0);
265 [ - + ]: 198 : if (co == WHITE)
7739 tgl@sss.pgh.pa.us 266 :UBC 0 : return;
267 : :
7739 tgl@sss.pgh.pa.us 268 [ - + ]:CBC 198 : assert(cd->arcs == NULL);
269 [ - + ]: 198 : assert(cd->sub == NOSUB);
2778 270 [ - + ]: 198 : assert(cd->nschrs == 0);
271 [ - + ]: 198 : assert(cd->nuchrs == 0);
7739 272 : 198 : cd->flags = FREECOL;
273 : :
7559 bruce@momjian.us 274 [ + + ]: 198 : if ((size_t) co == cm->max)
275 : : {
7739 tgl@sss.pgh.pa.us 276 [ + - + + ]: 80 : while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
277 : 41 : cm->max--;
278 [ - + ]: 39 : assert(cm->free >= 0);
7559 bruce@momjian.us 279 [ + + ]: 41 : while ((size_t) cm->free > cm->max)
7739 tgl@sss.pgh.pa.us 280 : 2 : cm->free = cm->cd[cm->free].sub;
7559 bruce@momjian.us 281 [ + + ]: 39 : if (cm->free > 0)
282 : : {
7739 tgl@sss.pgh.pa.us 283 [ - + ]: 3 : assert(cm->free < cm->max);
284 : 3 : pco = cm->free;
285 : 3 : nco = cm->cd[pco].sub;
286 [ - + ]: 3 : while (nco > 0)
7559 bruce@momjian.us 287 [ # # ]:UBC 0 : if ((size_t) nco > cm->max)
288 : : {
289 : : /* take this one out of freelist */
7739 tgl@sss.pgh.pa.us 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 : : {
7739 tgl@sss.pgh.pa.us 303 :CBC 159 : cd->sub = cm->free;
7559 bruce@momjian.us 304 : 159 : 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
2489 tgl@sss.pgh.pa.us 312 : 13964 : pseudocolor(struct colormap *cm)
313 : : {
314 : : color co;
315 : : struct colordesc *cd;
316 : :
7739 317 : 13964 : co = newcolor(cm);
318 [ - + ]: 13964 : if (CISERR())
7739 tgl@sss.pgh.pa.us 319 :UBC 0 : return COLORLESS;
2778 tgl@sss.pgh.pa.us 320 :CBC 13964 : cd = &cm->cd[co];
321 : 13964 : cd->nschrs = 0;
322 : 13964 : cd->nuchrs = 1; /* pretend it is in the upper map */
323 : 13964 : cd->sub = NOSUB;
324 : 13964 : cd->arcs = NULL;
325 : 13964 : cd->firstchr = CHR_MIN;
326 : 13964 : cd->flags = PSEUDO;
7739 327 : 13964 : 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
2489 336 : 283981 : subcolor(struct colormap *cm, chr c)
337 : : {
338 : : color co; /* current color of c */
339 : : color sco; /* new subcolor */
340 : :
2778 341 [ - + ]: 283981 : assert(c <= MAX_SIMPLE_CHR);
342 : :
343 : 283981 : co = cm->locolormap[c - CHR_MIN];
7739 344 : 283981 : sco = newsub(cm, co);
345 [ + + ]: 283981 : if (CISERR())
346 : 2 : return COLORLESS;
347 [ - + ]: 283979 : assert(sco != COLORLESS);
348 : :
7559 bruce@momjian.us 349 [ + + ]: 283979 : if (co == sco) /* already in an open subcolor */
350 : 18592 : return co; /* rest is redundant */
2778 tgl@sss.pgh.pa.us 351 : 265387 : cm->cd[co].nschrs--;
352 [ + + ]: 265387 : if (cm->cd[sco].nschrs == 0)
4296 353 : 20953 : cm->cd[sco].firstchr = c;
2778 354 : 265387 : cm->cd[sco].nschrs++;
355 : 265387 : cm->locolormap[c - CHR_MIN] = sco;
356 : 265387 : 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
2489 366 : 876 : subcolorhi(struct colormap *cm, color *pco)
367 : : {
368 : : color co; /* current color of entry */
369 : : color sco; /* new subcolor */
370 : :
2778 371 : 876 : co = *pco;
372 : 876 : sco = newsub(cm, co);
373 [ - + ]: 876 : if (CISERR())
2778 tgl@sss.pgh.pa.us 374 :UBC 0 : return COLORLESS;
2778 tgl@sss.pgh.pa.us 375 [ - + ]:CBC 876 : assert(sco != COLORLESS);
376 : :
377 [ + + ]: 876 : if (co == sco) /* already in an open subcolor */
378 : 10 : return co; /* rest is redundant */
379 : 866 : cm->cd[co].nuchrs--;
380 : 866 : cm->cd[sco].nuchrs++;
381 : 866 : *pco = sco;
7739 382 : 866 : return sco;
383 : : }
384 : :
385 : : /*
386 : : * newsub - allocate a new subcolor (if necessary) for a color
387 : : */
388 : : static color
2489 389 : 284857 : newsub(struct colormap *cm,
390 : : color co)
391 : : {
392 : : color sco; /* new subcolor */
393 : :
7739 394 : 284857 : sco = cm->cd[co].sub;
7559 bruce@momjian.us 395 [ + + ]: 284857 : if (sco == NOSUB)
396 : : { /* color has no open subcolor */
397 : : /* optimization: singly-referenced color need not be subcolored */
2778 tgl@sss.pgh.pa.us 398 [ + + ]: 39600 : if ((cm->cd[co].nschrs + cm->cd[co].nuchrs) == 1)
7739 399 : 18599 : return co;
7559 bruce@momjian.us 400 : 21001 : sco = newcolor(cm); /* must create subcolor */
401 [ + + ]: 21001 : if (sco == COLORLESS)
402 : : {
7739 tgl@sss.pgh.pa.us 403 [ - + ]: 2 : assert(CISERR());
404 : 2 : return COLORLESS;
405 : : }
406 : 20999 : cm->cd[co].sub = sco;
407 : 20999 : cm->cd[sco].sub = sco; /* open subcolor points to self */
408 : : }
409 [ - + ]: 266256 : assert(sco != NOSUB);
410 : :
411 : 266256 : 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
2489 420 : 146 : newhicolorrow(struct colormap *cm,
421 : : int oldrow)
422 : : {
2778 423 : 146 : int newrow = cm->hiarrayrows;
424 : : color *newrowptr;
425 : : int i;
426 : :
427 : : /* Assign a fresh array row index, enlarging storage if needed */
428 [ + + ]: 146 : if (newrow >= cm->maxarrayrows)
429 : : {
430 : : color *newarray;
431 : :
432 [ - + ]: 7 : if (cm->maxarrayrows >= INT_MAX / (cm->hiarraycols * 2))
433 : : {
2778 tgl@sss.pgh.pa.us 434 [ # # ]:UBC 0 : CERR(REG_ESPACE);
435 : 0 : return 0;
436 : : }
2778 tgl@sss.pgh.pa.us 437 :CBC 7 : newarray = (color *) REALLOC(cm->hicolormap,
438 : : cm->maxarrayrows * 2 *
439 : : cm->hiarraycols * sizeof(color));
440 [ - + ]: 7 : if (newarray == NULL)
441 : : {
2778 tgl@sss.pgh.pa.us 442 [ # # ]:UBC 0 : CERR(REG_ESPACE);
443 : 0 : return 0;
444 : : }
2778 tgl@sss.pgh.pa.us 445 :CBC 7 : cm->hicolormap = newarray;
446 : 7 : cm->maxarrayrows *= 2;
447 : : }
448 : 146 : cm->hiarrayrows++;
449 : :
450 : : /* Copy old row data */
451 : 146 : newrowptr = &cm->hicolormap[newrow * cm->hiarraycols];
452 : 146 : memcpy(newrowptr,
453 : 146 : &cm->hicolormap[oldrow * cm->hiarraycols],
454 : 146 : cm->hiarraycols * sizeof(color));
455 : :
456 : : /* Increase color reference counts to reflect new colormap entries */
457 [ + + ]: 691 : for (i = 0; i < cm->hiarraycols; i++)
458 : 545 : cm->cd[newrowptr[i]].nuchrs++;
459 : :
460 : 146 : 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
2489 469 : 301 : newhicolorcols(struct colormap *cm)
470 : : {
471 : : color *newarray;
472 : : int r,
473 : : c;
474 : :
2778 475 [ - + ]: 301 : if (cm->hiarraycols >= INT_MAX / (cm->maxarrayrows * 2))
476 : : {
2778 tgl@sss.pgh.pa.us 477 [ # # ]:UBC 0 : CERR(REG_ESPACE);
7739 478 : 0 : return;
479 : : }
2778 tgl@sss.pgh.pa.us 480 :CBC 301 : newarray = (color *) REALLOC(cm->hicolormap,
481 : : cm->maxarrayrows *
482 : : cm->hiarraycols * 2 * sizeof(color));
483 [ - + ]: 301 : if (newarray == NULL)
484 : : {
2778 tgl@sss.pgh.pa.us 485 [ # # ]:UBC 0 : CERR(REG_ESPACE);
486 : 0 : return;
487 : : }
2778 tgl@sss.pgh.pa.us 488 :CBC 301 : 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 [ + + ]: 602 : for (r = cm->hiarrayrows - 1; r >= 0; r--)
493 : : {
494 : 301 : color *oldrowptr = &newarray[r * cm->hiarraycols];
495 : 301 : color *newrowptr = &newarray[r * cm->hiarraycols * 2];
496 : 301 : color *newrowptr2 = newrowptr + cm->hiarraycols;
497 : :
498 [ + + ]: 614 : for (c = 0; c < cm->hiarraycols; c++)
499 : : {
500 : 313 : color co = oldrowptr[c];
501 : :
502 : 313 : newrowptr[c] = newrowptr2[c] = co;
503 : 313 : cm->cd[co].nuchrs++;
504 : : }
505 : : }
506 : :
507 : 301 : 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
2489 522 : 1487 : subcolorcvec(struct vars *v,
523 : : struct cvec *cv,
524 : : struct state *lp,
525 : : struct state *rp)
526 : : {
7739 527 : 1487 : struct colormap *cm = v->cm;
2778 528 : 1487 : color lastsubcolor = COLORLESS;
529 : : chr ch,
530 : : from,
531 : : to;
532 : : const chr *p;
533 : : int i;
534 : :
535 : : /* ordinary characters */
536 [ + + ]: 8966 : for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--)
537 : : {
538 : 7479 : ch = *p;
539 : 7479 : subcoloronechr(v, ch, lp, rp, &lastsubcolor);
540 [ - + ]: 7479 : NOERR();
541 : : }
542 : :
543 : : /* and the ranges */
544 [ + + ]: 7346 : for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--)
545 : : {
546 : 5859 : from = *p;
547 : 5859 : to = *(p + 1);
548 [ + + ]: 5859 : if (from <= MAX_SIMPLE_CHR)
549 : : {
550 : : /* deal with simple chars one at a time */
551 : 5851 : chr lim = (to <= MAX_SIMPLE_CHR) ? to : MAX_SIMPLE_CHR;
552 : :
553 [ + + ]: 245503 : while (from <= lim)
554 : : {
555 : 239652 : color sco = subcolor(cm, from);
556 : :
557 [ - + ]: 239652 : NOERR();
558 [ + + ]: 239652 : if (sco != lastsubcolor)
559 : : {
560 : 1918 : newarc(v->nfa, PLAIN, sco, lp, rp);
561 [ - + ]: 1918 : NOERR();
562 : 1918 : lastsubcolor = sco;
563 : : }
564 : 239652 : from++;
565 : : }
566 : : }
567 : : /* deal with any part of the range that's above MAX_SIMPLE_CHR */
568 [ + + ]: 5859 : if (from < to)
569 : 8 : subcoloronerange(v, from, to, lp, rp, &lastsubcolor);
570 [ - + ]: 5851 : else if (from == to)
2778 tgl@sss.pgh.pa.us 571 :UBC 0 : subcoloronechr(v, from, lp, rp, &lastsubcolor);
2778 tgl@sss.pgh.pa.us 572 [ - + ]:CBC 5859 : NOERR();
573 : : }
574 : :
575 : : /* and deal with cclass if any */
576 [ + + ]: 1487 : 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 [ + + ]: 330 : if (cm->classbits[cv->cclasscode] == 0)
585 : : {
586 : 301 : cm->classbits[cv->cclasscode] = cm->hiarraycols;
587 : 301 : newhicolorcols(cm);
588 [ - + ]: 301 : NOERR();
589 : : }
590 : : /* Apply subcolorhi() and make arc for each entry in relevant cols */
591 : 330 : classbit = cm->classbits[cv->cclasscode];
592 : 330 : pco = cm->hicolormap;
593 [ + + ]: 660 : for (r = 0; r < cm->hiarrayrows; r++)
594 : : {
595 [ + + ]: 1014 : for (c = 0; c < cm->hiarraycols; c++)
596 : : {
597 [ + + ]: 684 : if (c & classbit)
598 : : {
599 : 342 : color sco = subcolorhi(cm, pco);
600 : :
601 [ - + ]: 342 : NOERR();
602 : : /* add the arc if needed */
603 [ + + ]: 342 : if (sco != lastsubcolor)
604 : : {
605 : 35 : newarc(v->nfa, PLAIN, sco, lp, rp);
606 [ - + ]: 35 : NOERR();
607 : 35 : lastsubcolor = sco;
608 : : }
609 : : }
610 : 684 : 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
2489 624 : 44190 : subcoloronechr(struct vars *v,
625 : : chr ch,
626 : : struct state *lp,
627 : : struct state *rp,
628 : : color *lastsubcolor)
629 : : {
2778 630 : 44190 : 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 [ + + ]: 44190 : if (ch <= MAX_SIMPLE_CHR)
639 : : {
640 : 44057 : color sco = subcolor(cm, ch);
641 : :
642 [ + + ]: 44057 : NOERR();
643 [ + + ]: 44055 : if (sco != *lastsubcolor)
644 : : {
645 : 37816 : newarc(v->nfa, PLAIN, sco, lp, rp);
646 : 37816 : *lastsubcolor = sco;
647 : : }
648 : 44055 : 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 : : newranges = (colormaprange *)
656 : 133 : MALLOC((cm->numcmranges + 2) * sizeof(colormaprange));
657 [ - + ]: 133 : if (newranges == NULL)
658 : : {
2778 tgl@sss.pgh.pa.us 659 [ # # ]:UBC 0 : CERR(REG_ESPACE);
7739 660 : 0 : return;
661 : : }
2778 tgl@sss.pgh.pa.us 662 :CBC 133 : numnewranges = 0;
663 : :
664 : : /* Ranges before target are unchanged */
665 : 133 : for (oldrange = cm->cmranges, oldrangen = 0;
666 [ + + ]: 7400 : oldrangen < cm->numcmranges;
667 : 7267 : oldrange++, oldrangen++)
668 : : {
669 [ + + ]: 7276 : if (oldrange->cmax >= ch)
670 : 9 : break;
671 : 7267 : newranges[numnewranges++] = *oldrange;
672 : : }
673 : :
674 : : /* Match target chr against current range */
675 [ + + + + ]: 133 : if (oldrangen >= cm->numcmranges || oldrange->cmin > ch)
676 : : {
677 : : /* chr does not belong to any existing range, make a new one */
678 : 128 : newranges[numnewranges].cmin = ch;
679 : 128 : newranges[numnewranges].cmax = ch;
680 : : /* row state should be cloned from the "all others" row */
681 : 128 : newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
682 : 128 : numnewranges++;
683 : : }
684 [ + + ]: 5 : else if (oldrange->cmin == oldrange->cmax)
685 : : {
686 : : /* we have an existing singleton range matching the chr */
687 : 1 : newranges[numnewranges++] = *oldrange;
688 : 1 : newrow = oldrange->rownum;
689 : : /* we've now fully processed this old range */
690 : 1 : oldrange++, oldrangen++;
691 : : }
692 : : else
693 : : {
694 : : /* chr is a subset of this existing range, must split it */
695 [ + - ]: 4 : if (ch > oldrange->cmin)
696 : : {
697 : : /* emit portion of old range before chr */
698 : 4 : newranges[numnewranges].cmin = oldrange->cmin;
699 : 4 : newranges[numnewranges].cmax = ch - 1;
700 : 4 : newranges[numnewranges].rownum = oldrange->rownum;
701 : 4 : numnewranges++;
702 : : }
703 : : /* emit chr as singleton range, initially cloning from range */
704 : 4 : newranges[numnewranges].cmin = ch;
705 : 4 : newranges[numnewranges].cmax = ch;
706 : 4 : newranges[numnewranges].rownum = newrow =
707 : 4 : newhicolorrow(cm, oldrange->rownum);
708 : 4 : numnewranges++;
709 [ + - ]: 4 : if (ch < oldrange->cmax)
710 : : {
711 : : /* emit portion of old range after chr */
712 : 4 : newranges[numnewranges].cmin = ch + 1;
713 : 4 : newranges[numnewranges].cmax = oldrange->cmax;
714 : : /* must clone the row if we are making two new ranges from old */
715 : 4 : newranges[numnewranges].rownum =
716 [ + - ]: 4 : (ch > oldrange->cmin) ? newhicolorrow(cm, oldrange->rownum) :
717 : : oldrange->rownum;
718 : 4 : numnewranges++;
719 : : }
720 : : /* we've now fully processed this old range */
721 : 4 : oldrange++, oldrangen++;
722 : : }
723 : :
724 : : /* Update colors in newrow and create arcs as needed */
725 : 133 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
726 : :
727 : : /* Ranges after target are unchanged */
728 [ + + ]: 630 : for (; oldrangen < cm->numcmranges; oldrange++, oldrangen++)
729 : : {
730 : 497 : newranges[numnewranges++] = *oldrange;
731 : : }
732 : :
733 : : /* Assert our original space estimate was adequate */
734 [ - + ]: 133 : assert(numnewranges <= (cm->numcmranges + 2));
735 : :
736 : : /* And finally, store back the updated list of ranges */
737 [ + + ]: 133 : if (cm->cmranges != NULL)
738 : 128 : FREE(cm->cmranges);
739 : 133 : cm->cmranges = newranges;
740 : 133 : cm->numcmranges = numnewranges;
741 : : }
742 : :
743 : : /*
744 : : * subcoloronerange - do subcolorcvec's work for a high range
745 : : */
746 : : static void
2489 747 : 8 : subcoloronerange(struct vars *v,
748 : : chr from,
749 : : chr to,
750 : : struct state *lp,
751 : : struct state *rp,
752 : : color *lastsubcolor)
753 : : {
2778 754 : 8 : 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 [ - + ]: 8 : assert(from > MAX_SIMPLE_CHR);
763 [ - + ]: 8 : 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 : : newranges = (colormaprange *)
770 : 8 : MALLOC((cm->numcmranges * 2 + 1) * sizeof(colormaprange));
771 [ - + ]: 8 : if (newranges == NULL)
772 : : {
2778 tgl@sss.pgh.pa.us 773 [ # # ]:UBC 0 : CERR(REG_ESPACE);
774 : 0 : return;
775 : : }
2778 tgl@sss.pgh.pa.us 776 :CBC 8 : numnewranges = 0;
777 : :
778 : : /* Ranges before target are unchanged */
779 : 8 : for (oldrange = cm->cmranges, oldrangen = 0;
780 [ + + ]: 14 : oldrangen < cm->numcmranges;
781 : 6 : oldrange++, oldrangen++)
782 : : {
783 [ + + ]: 10 : if (oldrange->cmax >= from)
784 : 4 : break;
785 : 6 : 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 [ + + + + ]: 11 : while (oldrangen < cm->numcmranges && oldrange->cmin <= to)
794 : : {
795 [ + + ]: 3 : if (from < oldrange->cmin)
796 : : {
797 : : /* Handle portion of new range that corresponds to no old range */
798 : 1 : newranges[numnewranges].cmin = from;
799 : 1 : newranges[numnewranges].cmax = oldrange->cmin - 1;
800 : : /* row state should be cloned from the "all others" row */
801 : 1 : newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
802 : 1 : numnewranges++;
803 : : /* Update colors in newrow and create arcs as needed */
804 : 1 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
805 : : /* We've now fully processed the part of new range before old */
806 : 1 : from = oldrange->cmin;
807 : : }
808 : :
809 [ + + + + ]: 3 : if (from <= oldrange->cmin && to >= oldrange->cmax)
810 : : {
811 : : /* old range is fully contained in new, process it in-place */
812 : 1 : newranges[numnewranges++] = *oldrange;
813 : 1 : newrow = oldrange->rownum;
814 : 1 : from = oldrange->cmax + 1;
815 : : }
816 : : else
817 : : {
818 : : /* some part of old range does not overlap new range */
819 [ + + ]: 2 : if (from > oldrange->cmin)
820 : : {
821 : : /* emit portion of old range before new range */
822 : 1 : newranges[numnewranges].cmin = oldrange->cmin;
823 : 1 : newranges[numnewranges].cmax = from - 1;
824 : 1 : newranges[numnewranges].rownum = oldrange->rownum;
825 : 1 : numnewranges++;
826 : : }
827 : : /* emit common subrange, initially cloning from old range */
828 : 2 : newranges[numnewranges].cmin = from;
829 : 2 : newranges[numnewranges].cmax =
830 : 2 : (to < oldrange->cmax) ? to : oldrange->cmax;
831 : 2 : newranges[numnewranges].rownum = newrow =
832 : 2 : newhicolorrow(cm, oldrange->rownum);
833 : 2 : numnewranges++;
834 [ + + ]: 2 : if (to < oldrange->cmax)
835 : : {
836 : : /* emit portion of old range after new range */
837 : 1 : newranges[numnewranges].cmin = to + 1;
838 : 1 : newranges[numnewranges].cmax = oldrange->cmax;
839 : : /* must clone the row if we are making two new ranges from old */
840 : 1 : newranges[numnewranges].rownum =
841 [ - + ]: 1 : (from > oldrange->cmin) ? newhicolorrow(cm, oldrange->rownum) :
842 : : oldrange->rownum;
843 : 1 : numnewranges++;
844 : : }
845 : 2 : from = oldrange->cmax + 1;
846 : : }
847 : : /* Update colors in newrow and create arcs as needed */
848 : 3 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
849 : : /* we've now fully processed this old range */
850 : 3 : oldrange++, oldrangen++;
851 : : }
852 : :
853 [ + + ]: 8 : if (from <= to)
854 : : {
855 : : /* Handle portion of new range that corresponds to no old range */
856 : 7 : newranges[numnewranges].cmin = from;
857 : 7 : newranges[numnewranges].cmax = to;
858 : : /* row state should be cloned from the "all others" row */
859 : 7 : newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
860 : 7 : numnewranges++;
861 : : /* Update colors in newrow and create arcs as needed */
862 : 7 : subcoloronerow(v, newrow, lp, rp, lastsubcolor);
863 : : }
864 : :
865 : : /* Ranges after target are unchanged */
866 [ + + ]: 135 : for (; oldrangen < cm->numcmranges; oldrange++, oldrangen++)
867 : : {
868 : 127 : newranges[numnewranges++] = *oldrange;
869 : : }
870 : :
871 : : /* Assert our original space estimate was adequate */
872 [ - + ]: 8 : assert(numnewranges <= (cm->numcmranges * 2 + 1));
873 : :
874 : : /* And finally, store back the updated list of ranges */
875 [ + + ]: 8 : if (cm->cmranges != NULL)
876 : 5 : FREE(cm->cmranges);
877 : 8 : cm->cmranges = newranges;
878 : 8 : cm->numcmranges = numnewranges;
879 : : }
880 : :
881 : : /*
882 : : * subcoloronerow - do subcolorcvec's work for one new row in the high colormap
883 : : */
884 : : static void
2489 885 : 144 : subcoloronerow(struct vars *v,
886 : : int rownum,
887 : : struct state *lp,
888 : : struct state *rp,
889 : : color *lastsubcolor)
890 : : {
2778 891 : 144 : struct colormap *cm = v->cm;
892 : : color *pco;
893 : : int i;
894 : :
895 : : /* Apply subcolorhi() and make arc for each entry in row */
896 : 144 : pco = &cm->hicolormap[rownum * cm->hiarraycols];
897 [ + + ]: 678 : for (i = 0; i < cm->hiarraycols; pco++, i++)
898 : : {
899 : 534 : color sco = subcolorhi(cm, pco);
900 : :
901 [ - + ]: 534 : NOERR();
902 : : /* make the arc if needed */
903 [ + - ]: 534 : if (sco != *lastsubcolor)
904 : : {
905 : 534 : newarc(v->nfa, PLAIN, sco, lp, rp);
906 [ - + ]: 534 : NOERR();
907 : 534 : *lastsubcolor = sco;
908 : : }
909 : : }
910 : : }
911 : :
912 : : /*
913 : : * okcolors - promote subcolors to full colors
914 : : */
915 : : static void
2489 916 : 38199 : okcolors(struct nfa *nfa,
917 : : struct colormap *cm)
918 : : {
919 : : struct colordesc *cd;
7739 920 : 38199 : struct colordesc *end = CDEND(cm);
921 : : struct colordesc *scd;
922 : : struct arc *a;
923 : : color co;
924 : : color sco;
925 : :
7559 bruce@momjian.us 926 [ + + ]: 306443 : for (cd = cm->cd, co = 0; cd < end; cd++, co++)
927 : : {
7739 tgl@sss.pgh.pa.us 928 : 268244 : sco = cd->sub;
7559 bruce@momjian.us 929 [ + + + + ]: 268244 : if (UNUSEDCOLOR(cd) || sco == NOSUB)
930 : : {
931 : : /* has no subcolor, no further action */
932 : : }
933 [ + + ]: 21055 : else if (sco == co)
934 : : {
935 : : /* is subcolor, let parent deal with it */
936 : : }
2778 tgl@sss.pgh.pa.us 937 [ + + + + ]: 20999 : else if (cd->nschrs == 0 && cd->nuchrs == 0)
938 : : {
939 : : /*
940 : : * Parent is now empty, so just change all its arcs to the
941 : : * subcolor, then free the parent.
942 : : *
943 : : * It is not obvious that simply relabeling the arcs like this is
944 : : * OK; it appears to risk creating duplicate arcs. We are
945 : : * basically relying on the assumption that processing of a
946 : : * bracket expression can't create arcs of both a color and its
947 : : * subcolor between the bracket's endpoints.
948 : : */
7739 949 : 198 : cd->sub = NOSUB;
950 : 198 : scd = &cm->cd[sco];
2778 951 [ - + - - ]: 198 : assert(scd->nschrs > 0 || scd->nuchrs > 0);
7739 952 [ - + ]: 198 : assert(scd->sub == sco);
953 : 198 : scd->sub = NOSUB;
7559 bruce@momjian.us 954 [ + + ]: 1384 : while ((a = cd->arcs) != NULL)
955 : : {
7739 tgl@sss.pgh.pa.us 956 [ - + ]: 1186 : assert(a->co == co);
5946 957 : 1186 : uncolorchain(cm, a);
7739 958 : 1186 : a->co = sco;
5946 959 : 1186 : colorchain(cm, a);
960 : : }
7739 961 : 198 : freecolor(cm, co);
962 : : }
963 : : else
964 : : {
965 : : /* parent's arcs must gain parallel subcolor arcs */
966 : 20801 : cd->sub = NOSUB;
967 : 20801 : scd = &cm->cd[sco];
2778 968 [ + + - + ]: 20801 : assert(scd->nschrs > 0 || scd->nuchrs > 0);
7739 969 [ - + ]: 20801 : assert(scd->sub == sco);
970 : 20801 : scd->sub = NOSUB;
7559 bruce@momjian.us 971 [ + + ]: 21309 : for (a = cd->arcs; a != NULL; a = a->colorchain)
972 : : {
7739 tgl@sss.pgh.pa.us 973 [ - + ]: 508 : assert(a->co == co);
974 : 508 : newarc(nfa, a->type, sco, a->from, a->to);
975 : : }
976 : : }
977 : : }
978 : 38199 : }
979 : :
980 : : /*
981 : : * colorchain - add this arc to the color chain of its color
982 : : */
983 : : static void
2489 984 : 790136 : colorchain(struct colormap *cm,
985 : : struct arc *a)
986 : : {
7739 987 : 790136 : struct colordesc *cd = &cm->cd[a->co];
988 : :
1149 989 [ - + ]: 790136 : assert(a->co >= 0);
5946 990 [ + + ]: 790136 : if (cd->arcs != NULL)
991 : 758885 : cd->arcs->colorchainRev = a;
7739 992 : 790136 : a->colorchain = cd->arcs;
5946 993 : 790136 : a->colorchainRev = NULL;
7739 994 : 790136 : cd->arcs = a;
995 : 790136 : }
996 : :
997 : : /*
998 : : * uncolorchain - delete this arc from the color chain of its color
999 : : */
1000 : : static void
2489 1001 : 365463 : uncolorchain(struct colormap *cm,
1002 : : struct arc *a)
1003 : : {
7739 1004 : 365463 : struct colordesc *cd = &cm->cd[a->co];
5946 1005 : 365463 : struct arc *aa = a->colorchainRev;
1006 : :
1149 1007 [ - + ]: 365463 : assert(a->co >= 0);
5946 1008 [ + + ]: 365463 : if (aa == NULL)
1009 : : {
1010 [ - + ]: 90419 : assert(cd->arcs == a);
7739 1011 : 90419 : cd->arcs = a->colorchain;
1012 : : }
1013 : : else
1014 : : {
5946 1015 [ - + ]: 275044 : assert(aa->colorchain == a);
7739 1016 : 275044 : aa->colorchain = a->colorchain;
1017 : : }
5946 1018 [ + + ]: 365463 : if (a->colorchain != NULL)
1019 : 340360 : a->colorchain->colorchainRev = aa;
7559 bruce@momjian.us 1020 : 365463 : a->colorchain = NULL; /* paranoia */
5946 tgl@sss.pgh.pa.us 1021 : 365463 : a->colorchainRev = NULL;
7739 1022 : 365463 : }
1023 : :
1024 : : /*
1025 : : * rainbow - add arcs of all full colors (but one) between specified states
1026 : : *
1027 : : * If there isn't an exception color, we now generate just a single arc
1028 : : * labeled RAINBOW, saving lots of arc-munging later on.
1029 : : */
1030 : : static void
2489 1031 : 20962 : rainbow(struct nfa *nfa,
1032 : : struct colormap *cm,
1033 : : int type,
1034 : : color but, /* COLORLESS if no exceptions */
1035 : : struct state *from,
1036 : : struct state *to)
1037 : : {
1038 : : struct colordesc *cd;
7739 1039 : 20962 : struct colordesc *end = CDEND(cm);
1040 : : color co;
1041 : :
1149 1042 [ + + ]: 20962 : if (but == COLORLESS)
1043 : : {
1044 : 20763 : newarc(nfa, type, RAINBOW, from, to);
1045 : 20763 : return;
1046 : : }
1047 : :
1048 : : /* Gotta do it the hard way. Skip subcolors, pseudocolors, and "but" */
7739 1049 [ + + + - ]: 1471 : for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
1050 [ + - + - : 1272 : if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
+ + ]
7559 bruce@momjian.us 1051 [ + - ]: 1073 : !(cd->flags & PSEUDO))
7739 tgl@sss.pgh.pa.us 1052 : 1073 : newarc(nfa, type, co, from, to);
1053 : : }
1054 : :
1055 : : /*
1056 : : * colorcomplement - add arcs of complementary colors
1057 : : *
1058 : : * We add arcs of all colors that are not pseudocolors and do not match
1059 : : * any of the "of" state's PLAIN outarcs.
1060 : : *
1061 : : * The calling sequence ought to be reconciled with cloneouts().
1062 : : */
1063 : : static void
2489 1064 : 286 : colorcomplement(struct nfa *nfa,
1065 : : struct colormap *cm,
1066 : : int type,
1067 : : struct state *of,
1068 : : struct state *from,
1069 : : struct state *to)
1070 : : {
1071 : : struct colordesc *cd;
7739 1072 : 286 : struct colordesc *end = CDEND(cm);
1073 : : color co;
1074 : : struct arc *a;
1075 : :
1076 [ - + ]: 286 : assert(of != from);
1077 : :
1078 : : /* A RAINBOW arc matches all colors, making the complement empty */
1149 1079 [ + + ]: 286 : if (findarc(of, PLAIN, RAINBOW) != NULL)
1080 : 1 : return;
1081 : :
1082 : : /* Otherwise, transiently mark the colors that appear in of's out-arcs */
1144 1083 [ + + ]: 844 : for (a = of->outs; a != NULL; a = a->outchain)
1084 : : {
1085 [ + - ]: 559 : if (a->type == PLAIN)
1086 : : {
1087 [ - + ]: 559 : assert(a->co >= 0);
1088 : 559 : cd = &cm->cd[a->co];
1089 [ - + ]: 559 : assert(!UNUSEDCOLOR(cd));
1090 : 559 : cd->flags |= COLMARK;
1091 : : }
1092 : : }
1093 : :
1094 : : /* Scan colors, clear transient marks, add arcs for unmarked colors */
7739 1095 [ + + + - ]: 1378 : for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
1096 : : {
1144 1097 [ + + ]: 1093 : if (cd->flags & COLMARK)
1098 : 559 : cd->flags &= ~COLMARK;
1099 [ + + + - ]: 534 : else if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
1100 : 524 : newarc(nfa, type, co, from, to);
1101 : : }
1102 : : }
1103 : :
1104 : :
1105 : : #ifdef REG_DEBUG
1106 : :
1107 : : /*
1108 : : * dumpcolors - debugging output
1109 : : */
1110 : : static void
1111 : : dumpcolors(struct colormap *cm,
1112 : : FILE *f)
1113 : : {
1114 : : struct colordesc *cd;
1115 : : struct colordesc *end;
1116 : : color co;
1117 : : chr c;
1118 : :
1119 : : fprintf(f, "max %ld\n", (long) cm->max);
1120 : : end = CDEND(cm);
1121 : : for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
1122 : : {
1123 : : if (!UNUSEDCOLOR(cd))
1124 : : {
1125 : : assert(cd->nschrs > 0 || cd->nuchrs > 0);
1126 : : if (cd->flags & PSEUDO)
1127 : : fprintf(f, "#%2ld(ps): ", (long) co);
1128 : : else
1129 : : fprintf(f, "#%2ld(%2d): ", (long) co, cd->nschrs + cd->nuchrs);
1130 : :
1131 : : /*
1132 : : * Unfortunately, it's hard to do this next bit more efficiently.
1133 : : */
1134 : : for (c = CHR_MIN; c <= MAX_SIMPLE_CHR; c++)
1135 : : if (GETCOLOR(cm, c) == co)
1136 : : dumpchr(c, f);
1137 : : fprintf(f, "\n");
1138 : : }
1139 : : }
1140 : : /* dump the high colormap if it contains anything interesting */
1141 : : if (cm->hiarrayrows > 1 || cm->hiarraycols > 1)
1142 : : {
1143 : : int r,
1144 : : c;
1145 : : const color *rowptr;
1146 : :
1147 : : fprintf(f, "other:\t");
1148 : : for (c = 0; c < cm->hiarraycols; c++)
1149 : : {
1150 : : fprintf(f, "\t%ld", (long) cm->hicolormap[c]);
1151 : : }
1152 : : fprintf(f, "\n");
1153 : : for (r = 0; r < cm->numcmranges; r++)
1154 : : {
1155 : : dumpchr(cm->cmranges[r].cmin, f);
1156 : : fprintf(f, "..");
1157 : : dumpchr(cm->cmranges[r].cmax, f);
1158 : : fprintf(f, ":");
1159 : : rowptr = &cm->hicolormap[cm->cmranges[r].rownum * cm->hiarraycols];
1160 : : for (c = 0; c < cm->hiarraycols; c++)
1161 : : {
1162 : : fprintf(f, "\t%ld", (long) rowptr[c]);
1163 : : }
1164 : : fprintf(f, "\n");
1165 : : }
1166 : : }
1167 : : }
1168 : :
1169 : : /*
1170 : : * dumpchr - print a chr
1171 : : *
1172 : : * Kind of char-centric but works well enough for debug use.
1173 : : */
1174 : : static void
1175 : : dumpchr(chr c,
1176 : : FILE *f)
1177 : : {
1178 : : if (c == '\\')
1179 : : fprintf(f, "\\\\");
1180 : : else if (c > ' ' && c <= '~')
1181 : : putc((char) c, f);
1182 : : else
1183 : : fprintf(f, "\\u%04lx", (long) c);
1184 : : }
1185 : :
1186 : : #endif /* REG_DEBUG */
|
