]> git.saurik.com Git - apple/libc.git/blob - regex.subproj/regcomp.c
projects / apple / libc.git / blob
? search:


e2e0bf371efe9abd298595ada764eeadcad9a1f7
[apple/libc.git] / regex.subproj / regcomp.c
1 /*
2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
11 *
12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
19 *
20 * @APPLE_LICENSE_HEADER_END@
21 */
22 /*
23 * Copyright (c) 1992, 1993, 1994
24 * The Regents of the University of California. All rights reserved.
25 *
26 * This code is derived from software contributed to Berkeley by
27 * Henry Spencer.
28 *
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
31 * are met:
32 * 1. Redistributions of source code must retain the above copyright
33 * notice, this list of conditions and the following disclaimer.
34 * 2. Redistributions in binary form must reproduce the above copyright
35 * notice, this list of conditions and the following disclaimer in the
36 * documentation and/or other materials provided with the distribution.
37 * 3. All advertising materials mentioning features or use of this software
38 * must display the following acknowledgement:
39 * This product includes software developed by the University of
40 * California, Berkeley and its contributors.
41 * 4. Neither the name of the University nor the names of its contributors
42 * may be used to endorse or promote products derived from this software
43 * without specific prior written permission.
44 *
45 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
46 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
47 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
48 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
49 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
51 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
52 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
53 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
54 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
55 * SUCH DAMAGE.
56 */
57
58 #include <sys/types.h>
59 #include <stdio.h>
60 #include <string.h>
61 #include <ctype.h>
62 #include <limits.h>
63 #include <stdlib.h>
64 #include <regex.h>
65
66 #include "utils.h"
67 #include "regex2.h"
68
69 #include "cclass.h"
70 #include "cname.h"
71
72 /*
73 * parse structure, passed up and down to avoid global variables and
74 * other clumsinesses
75 */
76 struct parse {
77 char *next; /* next character in RE */
78 char *end; /* end of string (-> NUL normally) */
79 int error; /* has an error been seen? */
80 sop *strip; /* malloced strip */
81 sopno ssize; /* malloced strip size (allocated) */
82 sopno slen; /* malloced strip length (used) */
83 int ncsalloc; /* number of csets allocated */
84 struct re_guts *g;
85 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
86 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
87 sopno pend[NPAREN]; /* -> ) ([0] unused) */
88 };
89
90 /* ========= begin header generated by ./mkh ========= */
91 #ifdef __cplusplus
92 extern "C" {
93 #endif
94
95 /* === regcomp.c === */
96 static void p_ere __P((struct parse *p, int stop));
97 static void p_ere_exp __P((struct parse *p));
98 static void p_str __P((struct parse *p));
99 static void p_bre __P((struct parse *p, int end1, int end2));
100 static int p_simp_re __P((struct parse *p, int starordinary));
101 static int p_count __P((struct parse *p));
102 static void p_bracket __P((struct parse *p));
103 static void p_b_term __P((struct parse *p, cset *cs));
104 static void p_b_cclass __P((struct parse *p, cset *cs));
105 static void p_b_eclass __P((struct parse *p, cset *cs));
106 static char p_b_symbol __P((struct parse *p));
107 static char p_b_coll_elem __P((struct parse *p, int endc));
108 static char othercase __P((int ch));
109 static void bothcases __P((struct parse *p, int ch));
110 static void ordinary __P((struct parse *p, int ch));
111 static void nonnewline __P((struct parse *p));
112 static void repeat __P((struct parse *p, sopno start, int from, int to));
113 static int seterr __P((struct parse *p, int e));
114 static cset *allocset __P((struct parse *p));
115 static void freeset __P((struct parse *p, cset *cs));
116 static int freezeset __P((struct parse *p, cset *cs));
117 static int firstch __P((struct parse *p, cset *cs));
118 static int nch __P((struct parse *p, cset *cs));
119 static void mcadd __P((struct parse *p, cset *cs, char *cp));
120 static void mcsub __P((cset *cs, char *cp));
121 static int mcin __P((cset *cs, char *cp));
122 static char *mcfind __P((cset *cs, char *cp));
123 static void mcinvert __P((struct parse *p, cset *cs));
124 static void mccase __P((struct parse *p, cset *cs));
125 static int isinsets __P((struct re_guts *g, int c));
126 static int samesets __P((struct re_guts *g, int c1, int c2));
127 static void categorize __P((struct parse *p, struct re_guts *g));
128 static sopno dupl __P((struct parse *p, sopno start, sopno finish));
129 static void doemit __P((struct parse *p, sop op, size_t opnd));
130 static void doinsert __P((struct parse *p, sop op, size_t opnd, sopno pos));
131 static void dofwd __P((struct parse *p, sopno pos, sop value));
132 static void enlarge __P((struct parse *p, sopno size));
133 static void stripsnug __P((struct parse *p, struct re_guts *g));
134 static void findmust __P((struct parse *p, struct re_guts *g));
135 static sopno pluscount __P((struct parse *p, struct re_guts *g));
136
137 #ifdef __cplusplus
138 }
139 #endif
140 /* ========= end header generated by ./mkh ========= */
141
142 static char nuls[10]; /* place to point scanner in event of error */
143
144 /*
145 * macros for use with parse structure
146 * BEWARE: these know that the parse structure is named `p' !!!
147 */
148 #define PEEK() (*p->next)
149 #define PEEK2() (*(p->next+1))
150 #define MORE() (p->next < p->end)
151 #define MORE2() (p->next+1 < p->end)
152 #define SEE(c) (MORE() && PEEK() == (c))
153 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
154 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
155 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
156 #define NEXT() (p->next++)
157 #define NEXT2() (p->next += 2)
158 #define NEXTn(n) (p->next += (n))
159 #define GETNEXT() (*p->next++)
160 #define SETERROR(e) seterr(p, (e))
161 #define REQUIRE(co, e) ((co) || SETERROR(e))
162 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
163 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
164 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
165 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
166 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
167 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
168 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
169 #define HERE() (p->slen)
170 #define THERE() (p->slen - 1)
171 #define THERETHERE() (p->slen - 2)
172 #define DROP(n) (p->slen -= (n))
173
174 #ifndef NDEBUG
175 static int never = 0; /* for use in asserts; shuts lint up */
176 #else
177 #define never 0 /* some <assert.h>s have bugs too */
178 #endif
179
180 /*
181 - regcomp - interface for parser and compilation
182 = extern int regcomp(regex_t *, const char *, int);
183 = #define REG_BASIC 0000
184 = #define REG_EXTENDED 0001
185 = #define REG_ICASE 0002
186 = #define REG_NOSUB 0004
187 = #define REG_NEWLINE 0010
188 = #define REG_NOSPEC 0020
189 = #define REG_PEND 0040
190 = #define REG_DUMP 0200
191 */
192 int /* 0 success, otherwise REG_something */
193 regcomp(preg, pattern, cflags)
194 regex_t *preg;
195 const char *pattern;
196 int cflags;
197 {
198 struct parse pa;
199 register struct re_guts *g;
200 register struct parse *p = &pa;
201 register int i;
202 register size_t len;
203 #ifdef REDEBUG
204 # define GOODFLAGS(f) (f)
205 #else
206 # define GOODFLAGS(f) ((f)&~REG_DUMP)
207 #endif
208
209 cflags = GOODFLAGS(cflags);
210 if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
211 return(REG_INVARG);
212
213 if (cflags&REG_PEND) {
214 if (preg->re_endp < pattern)
215 return(REG_INVARG);
216 len = preg->re_endp - pattern;
217 } else
218 len = strlen((char *)pattern);
219
220 /* do the mallocs early so failure handling is easy */
221 g = (struct re_guts *)malloc(sizeof(struct re_guts) +
222 (NC-1)*sizeof(cat_t));
223 if (g == NULL)
224 return(REG_ESPACE);
225 p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
226 p->strip = (sop *)malloc(p->ssize * sizeof(sop));
227 p->slen = 0;
228 if (p->strip == NULL) {
229 free((char *)g);
230 return(REG_ESPACE);
231 }
232
233 /* set things up */
234 p->g = g;
235 p->next = (char *)pattern; /* convenience; we do not modify it */
236 p->end = p->next + len;
237 p->error = 0;
238 p->ncsalloc = 0;
239 for (i = 0; i < NPAREN; i++) {
240 p->pbegin[i] = 0;
241 p->pend[i] = 0;
242 }
243 g->csetsize = NC;
244 g->sets = NULL;
245 g->setbits = NULL;
246 g->ncsets = 0;
247 g->cflags = cflags;
248 g->iflags = 0;
249 g->nbol = 0;
250 g->neol = 0;
251 g->must = NULL;
252 g->mlen = 0;
253 g->nsub = 0;
254 g->ncategories = 1; /* category 0 is "everything else" */
255 g->categories = &g->catspace[-(CHAR_MIN)];
256 (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
257 g->backrefs = 0;
258
259 /* do it */
260 EMIT(OEND, 0);
261 g->firststate = THERE();
262 if (cflags&REG_EXTENDED)
263 p_ere(p, OUT);
264 else if (cflags&REG_NOSPEC)
265 p_str(p);
266 else
267 p_bre(p, OUT, OUT);
268 EMIT(OEND, 0);
269 g->laststate = THERE();
270
271 /* tidy up loose ends and fill things in */
272 categorize(p, g);
273 stripsnug(p, g);
274 findmust(p, g);
275 g->nplus = pluscount(p, g);
276 g->magic = MAGIC2;
277 preg->re_nsub = g->nsub;
278 preg->re_g = g;
279 preg->re_magic = MAGIC1;
280 #ifndef REDEBUG
281 /* not debugging, so can't rely on the assert() in regexec() */
282 if (g->iflags&BAD)
283 SETERROR(REG_ASSERT);
284 #endif
285
286 /* win or lose, we're done */
287 if (p->error != 0) /* lose */
288 regfree(preg);
289 return(p->error);
290 }
291
292 /*
293 - p_ere - ERE parser top level, concatenation and alternation
294 == static void p_ere(register struct parse *p, int stop);
295 */
296 static void
297 p_ere(p, stop)
298 register struct parse *p;
299 int stop; /* character this ERE should end at */
300 {
301 register char c;
302 register sopno prevback;
303 register sopno prevfwd;
304 register sopno conc;
305 register int first = 1; /* is this the first alternative? */
306
307 for (;;) {
308 /* do a bunch of concatenated expressions */
309 conc = HERE();
310 while (MORE() && (c = PEEK()) != '|' && c != stop)
311 p_ere_exp(p);
312 REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */
313
314 if (!EAT('|'))
315 break; /* NOTE BREAK OUT */
316
317 if (first) {
318 INSERT(OCH_, conc); /* offset is wrong */
319 prevfwd = conc;
320 prevback = conc;
321 first = 0;
322 }
323 ASTERN(OOR1, prevback);
324 prevback = THERE();
325 AHEAD(prevfwd); /* fix previous offset */
326 prevfwd = HERE();
327 EMIT(OOR2, 0); /* offset is very wrong */
328 }
329
330 if (!first) { /* tail-end fixups */
331 AHEAD(prevfwd);
332 ASTERN(O_CH, prevback);
333 }
334
335 assert(!MORE() || SEE(stop));
336 }
337
338 /*
339 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
340 == static void p_ere_exp(register struct parse *p);
341 */
342 static void
343 p_ere_exp(p)
344 register struct parse *p;
345 {
346 register char c;
347 register sopno pos;
348 register int count;
349 register int count2;
350 register sopno subno;
351 int wascaret = 0;
352
353 assert(MORE()); /* caller should have ensured this */
354 c = GETNEXT();
355
356 pos = HERE();
357 switch (c) {
358 case '(':
359 REQUIRE(MORE(), REG_EPAREN);
360 p->g->nsub++;
361 subno = p->g->nsub;
362 if (subno < NPAREN)
363 p->pbegin[subno] = HERE();
364 EMIT(OLPAREN, subno);
365 if (!SEE(')'))
366 p_ere(p, ')');
367 if (subno < NPAREN) {
368 p->pend[subno] = HERE();
369 assert(p->pend[subno] != 0);
370 }
371 EMIT(ORPAREN, subno);
372 MUSTEAT(')', REG_EPAREN);
373 break;
374 #ifndef POSIX_MISTAKE
375 case ')': /* happens only if no current unmatched ( */
376 /*
377 * You may ask, why the ifndef? Because I didn't notice
378 * this until slightly too late for 1003.2, and none of the
379 * other 1003.2 regular-expression reviewers noticed it at
380 * all. So an unmatched ) is legal POSIX, at least until
381 * we can get it fixed.
382 */
383 SETERROR(REG_EPAREN);
384 break;
385 #endif
386 case '^':
387 EMIT(OBOL, 0);
388 p->g->iflags |= USEBOL;
389 p->g->nbol++;
390 wascaret = 1;
391 break;
392 case '$':
393 EMIT(OEOL, 0);
394 p->g->iflags |= USEEOL;
395 p->g->neol++;
396 break;
397 case '|':
398 SETERROR(REG_EMPTY);
399 break;
400 case '*':
401 case '+':
402 case '?':
403 SETERROR(REG_BADRPT);
404 break;
405 case '.':
406 if (p->g->cflags&REG_NEWLINE)
407 nonnewline(p);
408 else
409 EMIT(OANY, 0);
410 break;
411 case '[':
412 p_bracket(p);
413 break;
414 case '\\':
415 REQUIRE(MORE(), REG_EESCAPE);
416 c = GETNEXT();
417 ordinary(p, c);
418 break;
419 case '{': /* okay as ordinary except if digit follows */
420 REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT);
421 /* FALLTHROUGH */
422 default:
423 ordinary(p, c);
424 break;
425 }
426
427 if (!MORE())
428 return;
429 c = PEEK();
430 /* we call { a repetition if followed by a digit */
431 if (!( c == '*' || c == '+' || c == '?' ||
432 (c == '{' && MORE2() && isdigit(PEEK2())) ))
433 return; /* no repetition, we're done */
434 NEXT();
435
436 REQUIRE(!wascaret, REG_BADRPT);
437 switch (c) {
438 case '*': /* implemented as +? */
439 /* this case does not require the (y|) trick, noKLUDGE */
440 INSERT(OPLUS_, pos);
441 ASTERN(O_PLUS, pos);
442 INSERT(OQUEST_, pos);
443 ASTERN(O_QUEST, pos);
444 break;
445 case '+':
446 INSERT(OPLUS_, pos);
447 ASTERN(O_PLUS, pos);
448 break;
449 case '?':
450 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
451 INSERT(OCH_, pos); /* offset slightly wrong */
452 ASTERN(OOR1, pos); /* this one's right */
453 AHEAD(pos); /* fix the OCH_ */
454 EMIT(OOR2, 0); /* offset very wrong... */
455 AHEAD(THERE()); /* ...so fix it */
456 ASTERN(O_CH, THERETHERE());
457 break;
458 case '{':
459 count = p_count(p);
460 if (EAT(',')) {
461 if (isdigit(PEEK())) {
462 count2 = p_count(p);
463 REQUIRE(count <= count2, REG_BADBR);
464 } else /* single number with comma */
465 count2 = INFINITY;
466 } else /* just a single number */
467 count2 = count;
468 repeat(p, pos, count, count2);
469 if (!EAT('}')) { /* error heuristics */
470 while (MORE() && PEEK() != '}')
471 NEXT();
472 REQUIRE(MORE(), REG_EBRACE);
473 SETERROR(REG_BADBR);
474 }
475 break;
476 }
477
478 if (!MORE())
479 return;
480 c = PEEK();
481 if (!( c == '*' || c == '+' || c == '?' ||
482 (c == '{' && MORE2() && isdigit(PEEK2())) ) )
483 return;
484 SETERROR(REG_BADRPT);
485 }
486
487 /*
488 - p_str - string (no metacharacters) "parser"
489 == static void p_str(register struct parse *p);
490 */
491 static void
492 p_str(p)
493 register struct parse *p;
494 {
495 REQUIRE(MORE(), REG_EMPTY);
496 while (MORE())
497 ordinary(p, GETNEXT());
498 }
499
500 /*
501 - p_bre - BRE parser top level, anchoring and concatenation
502 == static void p_bre(register struct parse *p, register int end1, \
503 == register int end2);
504 * Giving end1 as OUT essentially eliminates the end1/end2 check.
505 *
506 * This implementation is a bit of a kludge, in that a trailing $ is first
507 * taken as an ordinary character and then revised to be an anchor. The
508 * only undesirable side effect is that '$' gets included as a character
509 * category in such cases. This is fairly harmless; not worth fixing.
510 * The amount of lookahead needed to avoid this kludge is excessive.
511 */
512 static void
513 p_bre(p, end1, end2)
514 register struct parse *p;
515 register int end1; /* first terminating character */
516 register int end2; /* second terminating character */
517 {
518 register sopno start = HERE();
519 register int first = 1; /* first subexpression? */
520 register int wasdollar = 0;
521
522 if (EAT('^')) {
523 EMIT(OBOL, 0);
524 p->g->iflags |= USEBOL;
525 p->g->nbol++;
526 }
527 while (MORE() && !SEETWO(end1, end2)) {
528 wasdollar = p_simp_re(p, first);
529 first = 0;
530 }
531 if (wasdollar) { /* oops, that was a trailing anchor */
532 DROP(1);
533 EMIT(OEOL, 0);
534 p->g->iflags |= USEEOL;
535 p->g->neol++;
536 }
537
538 REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */
539 }
540
541 /*
542 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
543 == static int p_simp_re(register struct parse *p, int starordinary);
544 */
545 static int /* was the simple RE an unbackslashed $? */
546 p_simp_re(p, starordinary)
547 register struct parse *p;
548 int starordinary; /* is a leading * an ordinary character? */
549 {
550 register int c;
551 register int count;
552 register int count2;
553 register sopno pos;
554 register int i;
555 register sopno subno;
556 # define BACKSL (1<<CHAR_BIT)
557
558 pos = HERE(); /* repetion op, if any, covers from here */
559
560 assert(MORE()); /* caller should have ensured this */
561 c = GETNEXT();
562 if (c == '\\') {
563 REQUIRE(MORE(), REG_EESCAPE);
564 c = BACKSL | (unsigned char)GETNEXT();
565 }
566 switch (c) {
567 case '.':
568 if (p->g->cflags&REG_NEWLINE)
569 nonnewline(p);
570 else
571 EMIT(OANY, 0);
572 break;
573 case '[':
574 p_bracket(p);
575 break;
576 case BACKSL|'{':
577 SETERROR(REG_BADRPT);
578 break;
579 case BACKSL|'(':
580 p->g->nsub++;
581 subno = p->g->nsub;
582 if (subno < NPAREN)
583 p->pbegin[subno] = HERE();
584 EMIT(OLPAREN, subno);
585 /* the MORE here is an error heuristic */
586 if (MORE() && !SEETWO('\\', ')'))
587 p_bre(p, '\\', ')');
588 if (subno < NPAREN) {
589 p->pend[subno] = HERE();
590 assert(p->pend[subno] != 0);
591 }
592 EMIT(ORPAREN, subno);
593 REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
594 break;
595 case BACKSL|')': /* should not get here -- must be user */
596 case BACKSL|'}':
597 SETERROR(REG_EPAREN);
598 break;
599 case BACKSL|'1':
600 case BACKSL|'2':
601 case BACKSL|'3':
602 case BACKSL|'4':
603 case BACKSL|'5':
604 case BACKSL|'6':
605 case BACKSL|'7':
606 case BACKSL|'8':
607 case BACKSL|'9':
608 i = (c&~BACKSL) - '0';
609 assert(i < NPAREN);
610 if (p->pend[i] != 0) {
611 assert(i <= p->g->nsub);
612 EMIT(OBACK_, i);
613 assert(p->pbegin[i] != 0);
614 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
615 assert(OP(p->strip[p->pend[i]]) == ORPAREN);
616 (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
617 EMIT(O_BACK, i);
618 } else
619 SETERROR(REG_ESUBREG);
620 p->g->backrefs = 1;
621 break;
622 case '*':
623 REQUIRE(starordinary, REG_BADRPT);
624 /* FALLTHROUGH */
625 default:
626 ordinary(p, c &~ BACKSL);
627 break;
628 }
629
630 if (EAT('*')) { /* implemented as +? */
631 /* this case does not require the (y|) trick, noKLUDGE */
632 INSERT(OPLUS_, pos);
633 ASTERN(O_PLUS, pos);
634 INSERT(OQUEST_, pos);
635 ASTERN(O_QUEST, pos);
636 } else if (EATTWO('\\', '{')) {
637 count = p_count(p);
638 if (EAT(',')) {
639 if (MORE() && isdigit(PEEK())) {
640 count2 = p_count(p);
641 REQUIRE(count <= count2, REG_BADBR);
642 } else /* single number with comma */
643 count2 = INFINITY;
644 } else /* just a single number */
645 count2 = count;
646 repeat(p, pos, count, count2);
647 if (!EATTWO('\\', '}')) { /* error heuristics */
648 while (MORE() && !SEETWO('\\', '}'))
649 NEXT();
650 REQUIRE(MORE(), REG_EBRACE);
651 SETERROR(REG_BADBR);
652 }
653 } else if (c == (unsigned char)'$') /* $ (but not \$) ends it */
654 return(1);
655
656 return(0);
657 }
658
659 /*
660 - p_count - parse a repetition count
661 == static int p_count(register struct parse *p);
662 */
663 static int /* the value */
664 p_count(p)
665 register struct parse *p;
666 {
667 register int count = 0;
668 register int ndigits = 0;
669
670 while (MORE() && isdigit(PEEK()) && count <= DUPMAX) {
671 count = count*10 + (GETNEXT() - '0');
672 ndigits++;
673 }
674
675 REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
676 return(count);
677 }
678
679 /*
680 - p_bracket - parse a bracketed character list
681 == static void p_bracket(register struct parse *p);
682 *
683 * Note a significant property of this code: if the allocset() did SETERROR,
684 * no set operations are done.
685 */
686 static void
687 p_bracket(p)
688 register struct parse *p;
689 {
690 register char c;
691 register cset *cs = allocset(p);
692 register int invert = 0;
693
694 /* Dept of Truly Sickening Special-Case Kludges */
695 if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
696 EMIT(OBOW, 0);
697 NEXTn(6);
698 return;
699 }
700 if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
701 EMIT(OEOW, 0);
702 NEXTn(6);
703 return;
704 }
705
706 if (EAT('^'))
707 invert++; /* make note to invert set at end */
708 if (EAT(']'))
709 CHadd(cs, ']');
710 else if (EAT('-'))
711 CHadd(cs, '-');
712 while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
713 p_b_term(p, cs);
714 if (EAT('-'))
715 CHadd(cs, '-');
716 MUSTEAT(']', REG_EBRACK);
717
718 if (p->error != 0) /* don't mess things up further */
719 return;
720
721 if (p->g->cflags&REG_ICASE) {
722 register int i;
723 register int ci;
724
725 for (i = p->g->csetsize - 1; i >= 0; i--)
726 if (CHIN(cs, i) && isalpha(i)) {
727 ci = othercase(i);
728 if (ci != i)
729 CHadd(cs, ci);
730 }
731 if (cs->multis != NULL)
732 mccase(p, cs);
733 }
734 if (invert) {
735 register int i;
736
737 for (i = p->g->csetsize - 1; i >= 0; i--)
738 if (CHIN(cs, i))
739 CHsub(cs, i);
740 else
741 CHadd(cs, i);
742 if (p->g->cflags&REG_NEWLINE)
743 CHsub(cs, '\n');
744 if (cs->multis != NULL)
745 mcinvert(p, cs);
746 }
747
748 assert(cs->multis == NULL); /* xxx */
749
750 if (nch(p, cs) == 1) { /* optimize singleton sets */
751 ordinary(p, firstch(p, cs));
752 freeset(p, cs);
753 } else
754 EMIT(OANYOF, freezeset(p, cs));
755 }
756
757 /*
758 - p_b_term - parse one term of a bracketed character list
759 == static void p_b_term(register struct parse *p, register cset *cs);
760 */
761 static void
762 p_b_term(p, cs)
763 register struct parse *p;
764 register cset *cs;
765 {
766 register char c;
767 register char start, finish;
768 register int i;
769
770 /* classify what we've got */
771 switch ((MORE()) ? PEEK() : '\0') {
772 case '[':
773 c = (MORE2()) ? PEEK2() : '\0';
774 break;
775 case '-':
776 SETERROR(REG_ERANGE);
777 return; /* NOTE RETURN */
778 break;
779 default:
780 c = '\0';
781 break;
782 }
783
784 switch (c) {
785 case ':': /* character class */
786 NEXT2();
787 REQUIRE(MORE(), REG_EBRACK);
788 c = PEEK();
789 REQUIRE(c != '-' && c != ']', REG_ECTYPE);
790 p_b_cclass(p, cs);
791 REQUIRE(MORE(), REG_EBRACK);
792 REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
793 break;
794 case '=': /* equivalence class */
795 NEXT2();
796 REQUIRE(MORE(), REG_EBRACK);
797 c = PEEK();
798 REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
799 p_b_eclass(p, cs);
800 REQUIRE(MORE(), REG_EBRACK);
801 REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
802 break;
803 default: /* symbol, ordinary character, or range */
804 /* xxx revision needed for multichar stuff */
805 start = p_b_symbol(p);
806 if (SEE('-') && MORE2() && PEEK2() != ']') {
807 /* range */
808 NEXT();
809 if (EAT('-'))
810 finish = '-';
811 else
812 finish = p_b_symbol(p);
813 } else
814 finish = start;
815 /* xxx what about signed chars here... */
816 REQUIRE(start <= finish, REG_ERANGE);
817 for (i = start; i <= finish; i++)
818 CHadd(cs, i);
819 break;
820 }
821 }
822
823 /*
824 - p_b_cclass - parse a character-class name and deal with it
825 == static void p_b_cclass(register struct parse *p, register cset *cs);
826 */
827 static void
828 p_b_cclass(p, cs)
829 register struct parse *p;
830 register cset *cs;
831 {
832 register char *sp = p->next;
833 register struct cclass *cp;
834 register size_t len;
835 register char *u;
836 register char c;
837
838 while (MORE() && isalpha(PEEK()))
839 NEXT();
840 len = p->next - sp;
841 for (cp = cclasses; cp->name != NULL; cp++)
842 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
843 break;
844 if (cp->name == NULL) {
845 /* oops, didn't find it */
846 SETERROR(REG_ECTYPE);
847 return;
848 }
849
850 u = cp->chars;
851 while ((c = *u++) != '\0')
852 CHadd(cs, c);
853 for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
854 MCadd(p, cs, u);
855 }
856
857 /*
858 - p_b_eclass - parse an equivalence-class name and deal with it
859 == static void p_b_eclass(register struct parse *p, register cset *cs);
860 *
861 * This implementation is incomplete. xxx
862 */
863 static void
864 p_b_eclass(p, cs)
865 register struct parse *p;
866 register cset *cs;
867 {
868 register char c;
869
870 c = p_b_coll_elem(p, '=');
871 CHadd(cs, c);
872 }
873
874 /*
875 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
876 == static char p_b_symbol(register struct parse *p);
877 */
878 static char /* value of symbol */
879 p_b_symbol(p)
880 register struct parse *p;
881 {
882 register char value;
883
884 REQUIRE(MORE(), REG_EBRACK);
885 if (!EATTWO('[', '.'))
886 return(GETNEXT());
887
888 /* collating symbol */
889 value = p_b_coll_elem(p, '.');
890 REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
891 return(value);
892 }
893
894 /*
895 - p_b_coll_elem - parse a collating-element name and look it up
896 == static char p_b_coll_elem(register struct parse *p, int endc);
897 */
898 static char /* value of collating element */
899 p_b_coll_elem(p, endc)
900 register struct parse *p;
901 int endc; /* name ended by endc,']' */
902 {
903 register char *sp = p->next;
904 register struct cname *cp;
905 register int len;
906 register char c;
907
908 while (MORE() && !SEETWO(endc, ']'))
909 NEXT();
910 if (!MORE()) {
911 SETERROR(REG_EBRACK);
912 return(0);
913 }
914 len = p->next - sp;
915 for (cp = cnames; cp->name != NULL; cp++)
916 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
917 return(cp->code); /* known name */
918 if (len == 1)
919 return(*sp); /* single character */
920 SETERROR(REG_ECOLLATE); /* neither */
921 return(0);
922 }
923
924 /*
925 - othercase - return the case counterpart of an alphabetic
926 == static char othercase(int ch);
927 */
928 static char /* if no counterpart, return ch */
929 othercase(ch)
930 int ch;
931 {
932 assert(isalpha(ch));
933 if (isupper(ch))
934 return(tolower(ch));
935 else if (islower(ch))
936 return(toupper(ch));
937 else /* peculiar, but could happen */
938 return(ch);
939 }
940
941 /*
942 - bothcases - emit a dualcase version of a two-case character
943 == static void bothcases(register struct parse *p, int ch);
944 *
945 * Boy, is this implementation ever a kludge...
946 */
947 static void
948 bothcases(p, ch)
949 register struct parse *p;
950 int ch;
951 {
952 register char *oldnext = p->next;
953 register char *oldend = p->end;
954 char bracket[3];
955
956 assert(othercase(ch) != ch); /* p_bracket() would recurse */
957 p->next = bracket;
958 p->end = bracket+2;
959 bracket[0] = ch;
960 bracket[1] = ']';
961 bracket[2] = '\0';
962 p_bracket(p);
963 assert(p->next == bracket+2);
964 p->next = oldnext;
965 p->end = oldend;
966 }
967
968 /*
969 - ordinary - emit an ordinary character
970 == static void ordinary(register struct parse *p, register int ch);
971 */
972 static void
973 ordinary(p, ch)
974 register struct parse *p;
975 register int ch;
976 {
977 register cat_t *cap = p->g->categories;
978
979 if ((p->g->cflags&REG_ICASE) && isalpha(ch) && othercase(ch) != ch)
980 bothcases(p, ch);
981 else {
982 EMIT(OCHAR, (unsigned char)ch);
983 if (cap[ch] == 0)
984 cap[ch] = p->g->ncategories++;
985 }
986 }
987
988 /*
989 - nonnewline - emit REG_NEWLINE version of OANY
990 == static void nonnewline(register struct parse *p);
991 *
992 * Boy, is this implementation ever a kludge...
993 */
994 static void
995 nonnewline(p)
996 register struct parse *p;
997 {
998 register char *oldnext = p->next;
999 register char *oldend = p->end;
1000 char bracket[4];
1001
1002 p->next = bracket;
1003 p->end = bracket+3;
1004 bracket[0] = '^';
1005 bracket[1] = '\n';
1006 bracket[2] = ']';
1007 bracket[3] = '\0';
1008 p_bracket(p);
1009 assert(p->next == bracket+3);
1010 p->next = oldnext;
1011 p->end = oldend;
1012 }
1013
1014 /*
1015 - repeat - generate code for a bounded repetition, recursively if needed
1016 == static void repeat(register struct parse *p, sopno start, int from, int to);
1017 */
1018 static void
1019 repeat(p, start, from, to)
1020 register struct parse *p;
1021 sopno start; /* operand from here to end of strip */
1022 int from; /* repeated from this number */
1023 int to; /* to this number of times (maybe INFINITY) */
1024 {
1025 register sopno finish = HERE();
1026 # define N 2
1027 # define INF 3
1028 # define REP(f, t) ((f)*8 + (t))
1029 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1030 register sopno copy;
1031
1032 if (p->error != 0) /* head off possible runaway recursion */
1033 return;
1034
1035 assert(from <= to);
1036
1037 switch (REP(MAP(from), MAP(to))) {
1038 case REP(0, 0): /* must be user doing this */
1039 DROP(finish-start); /* drop the operand */
1040 break;
1041 case REP(0, 1): /* as x{1,1}? */
1042 case REP(0, N): /* as x{1,n}? */
1043 case REP(0, INF): /* as x{1,}? */
1044 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1045 INSERT(OCH_, start); /* offset is wrong... */
1046 repeat(p, start+1, 1, to);
1047 ASTERN(OOR1, start);
1048 AHEAD(start); /* ... fix it */
1049 EMIT(OOR2, 0);
1050 AHEAD(THERE());
1051 ASTERN(O_CH, THERETHERE());
1052 break;
1053 case REP(1, 1): /* trivial case */
1054 /* done */
1055 break;
1056 case REP(1, N): /* as x?x{1,n-1} */
1057 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1058 INSERT(OCH_, start);
1059 ASTERN(OOR1, start);
1060 AHEAD(start);
1061 EMIT(OOR2, 0); /* offset very wrong... */
1062 AHEAD(THERE()); /* ...so fix it */
1063 ASTERN(O_CH, THERETHERE());
1064 copy = dupl(p, start+1, finish+1);
1065 assert(copy == finish+4);
1066 repeat(p, copy, 1, to-1);
1067 break;
1068 case REP(1, INF): /* as x+ */
1069 INSERT(OPLUS_, start);
1070 ASTERN(O_PLUS, start);
1071 break;
1072 case REP(N, N): /* as xx{m-1,n-1} */
1073 copy = dupl(p, start, finish);
1074 repeat(p, copy, from-1, to-1);
1075 break;
1076 case REP(N, INF): /* as xx{n-1,INF} */
1077 copy = dupl(p, start, finish);
1078 repeat(p, copy, from-1, to);
1079 break;
1080 default: /* "can't happen" */
1081 SETERROR(REG_ASSERT); /* just in case */
1082 break;
1083 }
1084 }
1085
1086 /*
1087 - seterr - set an error condition
1088 == static int seterr(register struct parse *p, int e);
1089 */
1090 static int /* useless but makes type checking happy */
1091 seterr(p, e)
1092 register struct parse *p;
1093 int e;
1094 {
1095 if (p->error == 0) /* keep earliest error condition */
1096 p->error = e;
1097 p->next = nuls; /* try to bring things to a halt */
1098 p->end = nuls;
1099 return(0); /* make the return value well-defined */
1100 }
1101
1102 /*
1103 - allocset - allocate a set of characters for []
1104 == static cset *allocset(register struct parse *p);
1105 */
1106 static cset *
1107 allocset(p)
1108 register struct parse *p;
1109 {
1110 register int no = p->g->ncsets++;
1111 register size_t nc;
1112 register size_t nbytes;
1113 register cset *cs;
1114 register size_t css = (size_t)p->g->csetsize;
1115 register int i;
1116
1117 if (no >= p->ncsalloc) { /* need another column of space */
1118 p->ncsalloc += CHAR_BIT;
1119 nc = p->ncsalloc;
1120 assert(nc % CHAR_BIT == 0);
1121 nbytes = nc / CHAR_BIT * css;
1122 if (p->g->sets == NULL)
1123 p->g->sets = (cset *)malloc(nc * sizeof(cset));
1124 else
1125 p->g->sets = (cset *)realloc((char *)p->g->sets,
1126 nc * sizeof(cset));
1127 if (p->g->setbits == NULL)
1128 p->g->setbits = (uch *)malloc(nbytes);
1129 else {
1130 p->g->setbits = (uch *)realloc((char *)p->g->setbits,
1131 nbytes);
1132 /* xxx this isn't right if setbits is now NULL */
1133 for (i = 0; i < no; i++)
1134 p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
1135 }
1136 if (p->g->sets != NULL && p->g->setbits != NULL)
1137 (void) memset((char *)p->g->setbits + (nbytes - css),
1138 0, css);
1139 else {
1140 no = 0;
1141 SETERROR(REG_ESPACE);
1142 /* caller's responsibility not to do set ops */
1143 }
1144 }
1145
1146 assert(p->g->sets != NULL); /* xxx */
1147 cs = &p->g->sets[no];
1148 cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
1149 cs->mask = 1 << ((no) % CHAR_BIT);
1150 cs->hash = 0;
1151 cs->smultis = 0;
1152 cs->multis = NULL;
1153
1154 return(cs);
1155 }
1156
1157 /*
1158 - freeset - free a now-unused set
1159 == static void freeset(register struct parse *p, register cset *cs);
1160 */
1161 static void
1162 freeset(p, cs)
1163 register struct parse *p;
1164 register cset *cs;
1165 {
1166 register int i;
1167 register cset *top = &p->g->sets[p->g->ncsets];
1168 register size_t css = (size_t)p->g->csetsize;
1169
1170 for (i = 0; i < css; i++)
1171 CHsub(cs, i);
1172 if (cs == top-1) /* recover only the easy case */
1173 p->g->ncsets--;
1174 }
1175
1176 /*
1177 - freezeset - final processing on a set of characters
1178 == static int freezeset(register struct parse *p, register cset *cs);
1179 *
1180 * The main task here is merging identical sets. This is usually a waste
1181 * of time (although the hash code minimizes the overhead), but can win
1182 * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
1183 * is done using addition rather than xor -- all ASCII [aA] sets xor to
1184 * the same value!
1185 */
1186 static int /* set number */
1187 freezeset(p, cs)
1188 register struct parse *p;
1189 register cset *cs;
1190 {
1191 register uch h = cs->hash;
1192 register int i;
1193 register cset *top = &p->g->sets[p->g->ncsets];
1194 register cset *cs2;
1195 register size_t css = (size_t)p->g->csetsize;
1196
1197 /* look for an earlier one which is the same */
1198 for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
1199 if (cs2->hash == h && cs2 != cs) {
1200 /* maybe */
1201 for (i = 0; i < css; i++)
1202 if (!!CHIN(cs2, i) != !!CHIN(cs, i))
1203 break; /* no */
1204 if (i == css)
1205 break; /* yes */
1206 }
1207
1208 if (cs2 < top) { /* found one */
1209 freeset(p, cs);
1210 cs = cs2;
1211 }
1212
1213 return((int)(cs - p->g->sets));
1214 }
1215
1216 /*
1217 - firstch - return first character in a set (which must have at least one)
1218 == static int firstch(register struct parse *p, register cset *cs);
1219 */
1220 static int /* character; there is no "none" value */
1221 firstch(p, cs)
1222 register struct parse *p;
1223 register cset *cs;
1224 {
1225 register int i;
1226 register size_t css = (size_t)p->g->csetsize;
1227
1228 for (i = 0; i < css; i++)
1229 if (CHIN(cs, i))
1230 return((char)i);
1231 assert(never);
1232 return(0); /* arbitrary */
1233 }
1234
1235 /*
1236 - nch - number of characters in a set
1237 == static int nch(register struct parse *p, register cset *cs);
1238 */
1239 static int
1240 nch(p, cs)
1241 register struct parse *p;
1242 register cset *cs;
1243 {
1244 register int i;
1245 register size_t css = (size_t)p->g->csetsize;
1246 register int n = 0;
1247
1248 for (i = 0; i < css; i++)
1249 if (CHIN(cs, i))
1250 n++;
1251 return(n);
1252 }
1253
1254 /*
1255 - mcadd - add a collating element to a cset
1256 == static void mcadd(register struct parse *p, register cset *cs, \
1257 == register char *cp);
1258 */
1259 static void
1260 mcadd(p, cs, cp)
1261 register struct parse *p;
1262 register cset *cs;
1263 register char *cp;
1264 {
1265 register size_t oldend = cs->smultis;
1266
1267 cs->smultis += strlen(cp) + 1;
1268 if (cs->multis == NULL)
1269 cs->multis = malloc(cs->smultis);
1270 else
1271 cs->multis = realloc(cs->multis, cs->smultis);
1272 if (cs->multis == NULL) {
1273 SETERROR(REG_ESPACE);
1274 return;
1275 }
1276
1277 (void) strcpy(cs->multis + oldend - 1, cp);
1278 cs->multis[cs->smultis - 1] = '\0';
1279 }
1280
1281 /*
1282 - mcsub - subtract a collating element from a cset
1283 == static void mcsub(register cset *cs, register char *cp);
1284 */
1285 static void
1286 mcsub(cs, cp)
1287 register cset *cs;
1288 register char *cp;
1289 {
1290 register char *fp = mcfind(cs, cp);
1291 register size_t len = strlen(fp);
1292
1293 assert(fp != NULL);
1294 (void) memmove(fp, fp + len + 1,
1295 cs->smultis - (fp + len + 1 - cs->multis));
1296 cs->smultis -= len;
1297
1298 if (cs->smultis == 0) {
1299 free(cs->multis);
1300 cs->multis = NULL;
1301 return;
1302 }
1303
1304 cs->multis = realloc(cs->multis, cs->smultis);
1305 assert(cs->multis != NULL);
1306 }
1307
1308 /*
1309 - mcin - is a collating element in a cset?
1310 == static int mcin(register cset *cs, register char *cp);
1311 */
1312 static int
1313 mcin(cs, cp)
1314 register cset *cs;
1315 register char *cp;
1316 {
1317 return(mcfind(cs, cp) != NULL);
1318 }
1319
1320 /*
1321 - mcfind - find a collating element in a cset
1322 == static char *mcfind(register cset *cs, register char *cp);
1323 */
1324 static char *
1325 mcfind(cs, cp)
1326 register cset *cs;
1327 register char *cp;
1328 {
1329 register char *p;
1330
1331 if (cs->multis == NULL)
1332 return(NULL);
1333 for (p = cs->multis; *p != '\0'; p += strlen(p) + 1)
1334 if (strcmp(cp, p) == 0)
1335 return(p);
1336 return(NULL);
1337 }
1338
1339 /*
1340 - mcinvert - invert the list of collating elements in a cset
1341 == static void mcinvert(register struct parse *p, register cset *cs);
1342 *
1343 * This would have to know the set of possibilities. Implementation
1344 * is deferred.
1345 */
1346 static void
1347 mcinvert(p, cs)
1348 register struct parse *p;
1349 register cset *cs;
1350 {
1351 assert(cs->multis == NULL); /* xxx */
1352 }
1353
1354 /*
1355 - mccase - add case counterparts of the list of collating elements in a cset
1356 == static void mccase(register struct parse *p, register cset *cs);
1357 *
1358 * This would have to know the set of possibilities. Implementation
1359 * is deferred.
1360 */
1361 static void
1362 mccase(p, cs)
1363 register struct parse *p;
1364 register cset *cs;
1365 {
1366 assert(cs->multis == NULL); /* xxx */
1367 }
1368
1369 /*
1370 - isinsets - is this character in any sets?
1371 == static int isinsets(register struct re_guts *g, int c);
1372 */
1373 static int /* predicate */
1374 isinsets(g, c)
1375 register struct re_guts *g;
1376 int c;
1377 {
1378 register uch *col;
1379 register int i;
1380 register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1381 register unsigned uc = (unsigned char)c;
1382
1383 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1384 if (col[uc] != 0)
1385 return(1);
1386 return(0);
1387 }
1388
1389 /*
1390 - samesets - are these two characters in exactly the same sets?
1391 == static int samesets(register struct re_guts *g, int c1, int c2);
1392 */
1393 static int /* predicate */
1394 samesets(g, c1, c2)
1395 register struct re_guts *g;
1396 int c1;
1397 int c2;
1398 {
1399 register uch *col;
1400 register int i;
1401 register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1402 register unsigned uc1 = (unsigned char)c1;
1403 register unsigned uc2 = (unsigned char)c2;
1404
1405 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1406 if (col[uc1] != col[uc2])
1407 return(0);
1408 return(1);
1409 }
1410
1411 /*
1412 - categorize - sort out character categories
1413 == static void categorize(struct parse *p, register struct re_guts *g);
1414 */
1415 static void
1416 categorize(p, g)
1417 struct parse *p;
1418 register struct re_guts *g;
1419 {
1420 register cat_t *cats = g->categories;
1421 register int c;
1422 register int c2;
1423 register cat_t cat;
1424
1425 /* avoid making error situations worse */
1426 if (p->error != 0)
1427 return;
1428
1429 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
1430 if (cats[c] == 0 && isinsets(g, c)) {
1431 cat = g->ncategories++;
1432 cats[c] = cat;
1433 for (c2 = c+1; c2 <= CHAR_MAX; c2++)
1434 if (cats[c2] == 0 && samesets(g, c, c2))
1435 cats[c2] = cat;
1436 }
1437 }
1438
1439 /*
1440 - dupl - emit a duplicate of a bunch of sops
1441 == static sopno dupl(register struct parse *p, sopno start, sopno finish);
1442 */
1443 static sopno /* start of duplicate */
1444 dupl(p, start, finish)
1445 register struct parse *p;
1446 sopno start; /* from here */
1447 sopno finish; /* to this less one */
1448 {
1449 register sopno ret = HERE();
1450 register sopno len = finish - start;
1451
1452 assert(finish >= start);
1453 if (len == 0)
1454 return(ret);
1455 enlarge(p, p->ssize + len); /* this many unexpected additions */
1456 assert(p->ssize >= p->slen + len);
1457 (void) memcpy((char *)(p->strip + p->slen),
1458 (char *)(p->strip + start), (size_t)len*sizeof(sop));
1459 p->slen += len;
1460 return(ret);
1461 }
1462
1463 /*
1464 - doemit - emit a strip operator
1465 == static void doemit(register struct parse *p, sop op, size_t opnd);
1466 *
1467 * It might seem better to implement this as a macro with a function as
1468 * hard-case backup, but it's just too big and messy unless there are
1469 * some changes to the data structures. Maybe later.
1470 */
1471 static void
1472 doemit(p, op, opnd)
1473 register struct parse *p;
1474 sop op;
1475 size_t opnd;
1476 {
1477 /* avoid making error situations worse */
1478 if (p->error != 0)
1479 return;
1480
1481 /* deal with oversize operands ("can't happen", more or less) */
1482 assert(opnd < 1<<OPSHIFT);
1483
1484 /* deal with undersized strip */
1485 if (p->slen >= p->ssize)
1486 enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */
1487 assert(p->slen < p->ssize);
1488
1489 /* finally, it's all reduced to the easy case */
1490 p->strip[p->slen++] = SOP(op, opnd);
1491 }
1492
1493 /*
1494 - doinsert - insert a sop into the strip
1495 == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos);
1496 */
1497 static void
1498 doinsert(p, op, opnd, pos)
1499 register struct parse *p;
1500 sop op;
1501 size_t opnd;
1502 sopno pos;
1503 {
1504 register sopno sn;
1505 register sop s;
1506 register int i;
1507
1508 /* avoid making error situations worse */
1509 if (p->error != 0)
1510 return;
1511
1512 sn = HERE();
1513 EMIT(op, opnd); /* do checks, ensure space */
1514 assert(HERE() == sn+1);
1515 s = p->strip[sn];
1516
1517 /* adjust paren pointers */
1518 assert(pos > 0);
1519 for (i = 1; i < NPAREN; i++) {
1520 if (p->pbegin[i] >= pos) {
1521 p->pbegin[i]++;
1522 }
1523 if (p->pend[i] >= pos) {
1524 p->pend[i]++;
1525 }
1526 }
1527
1528 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1529 (HERE()-pos-1)*sizeof(sop));
1530 p->strip[pos] = s;
1531 }
1532
1533 /*
1534 - dofwd - complete a forward reference
1535 == static void dofwd(register struct parse *p, sopno pos, sop value);
1536 */
1537 static void
1538 dofwd(p, pos, value)
1539 register struct parse *p;
1540 register sopno pos;
1541 sop value;
1542 {
1543 /* avoid making error situations worse */
1544 if (p->error != 0)
1545 return;
1546
1547 assert(value < 1<<OPSHIFT);
1548 p->strip[pos] = OP(p->strip[pos]) | value;
1549 }
1550
1551 /*
1552 - enlarge - enlarge the strip
1553 == static void enlarge(register struct parse *p, sopno size);
1554 */
1555 static void
1556 enlarge(p, size)
1557 register struct parse *p;
1558 register sopno size;
1559 {
1560 register sop *sp;
1561
1562 if (p->ssize >= size)
1563 return;
1564
1565 sp = (sop *)realloc(p->strip, size*sizeof(sop));
1566 if (sp == NULL) {
1567 SETERROR(REG_ESPACE);
1568 return;
1569 }
1570 p->strip = sp;
1571 p->ssize = size;
1572 }
1573
1574 /*
1575 - stripsnug - compact the strip
1576 == static void stripsnug(register struct parse *p, register struct re_guts *g);
1577 */
1578 static void
1579 stripsnug(p, g)
1580 register struct parse *p;
1581 register struct re_guts *g;
1582 {
1583 g->nstates = p->slen;
1584 g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
1585 if (g->strip == NULL) {
1586 SETERROR(REG_ESPACE);
1587 g->strip = p->strip;
1588 }
1589 }
1590
1591 /*
1592 - findmust - fill in must and mlen with longest mandatory literal string
1593 == static void findmust(register struct parse *p, register struct re_guts *g);
1594 *
1595 * This algorithm could do fancy things like analyzing the operands of |
1596 * for common subsequences. Someday. This code is simple and finds most
1597 * of the interesting cases.
1598 *
1599 * Note that must and mlen got initialized during setup.
1600 */
1601 static void
1602 findmust(p, g)
1603 struct parse *p;
1604 register struct re_guts *g;
1605 {
1606 register sop *scan;
1607 sop *start;
1608 register sop *newstart;
1609 register sopno newlen;
1610 register sop s;
1611 register char *cp;
1612 register sopno i;
1613
1614 /* avoid making error situations worse */
1615 if (p->error != 0)
1616 return;
1617
1618 /* find the longest OCHAR sequence in strip */
1619 newlen = 0;
1620 scan = g->strip + 1;
1621 do {
1622 s = *scan++;
1623 switch (OP(s)) {
1624 case OCHAR: /* sequence member */
1625 if (newlen == 0) /* new sequence */
1626 newstart = scan - 1;
1627 newlen++;
1628 break;
1629 case OPLUS_: /* things that don't break one */
1630 case OLPAREN:
1631 case ORPAREN:
1632 break;
1633 case OQUEST_: /* things that must be skipped */
1634 case OCH_:
1635 scan--;
1636 do {
1637 scan += OPND(s);
1638 s = *scan;
1639 /* assert() interferes w debug printouts */
1640 if (OP(s) != O_QUEST && OP(s) != O_CH &&
1641 OP(s) != OOR2) {
1642 g->iflags |= BAD;
1643 return;
1644 }
1645 } while (OP(s) != O_QUEST && OP(s) != O_CH);
1646 /* fallthrough */
1647 default: /* things that break a sequence */
1648 if (newlen > g->mlen) { /* ends one */
1649 start = newstart;
1650 g->mlen = newlen;
1651 }
1652 newlen = 0;
1653 break;
1654 }
1655 } while (OP(s) != OEND);
1656
1657 if (g->mlen == 0) /* there isn't one */
1658 return;
1659
1660 /* turn it into a character string */
1661 g->must = malloc((size_t)g->mlen + 1);
1662 if (g->must == NULL) { /* argh; just forget it */
1663 g->mlen = 0;
1664 return;
1665 }
1666 cp = g->must;
1667 scan = start;
1668 for (i = g->mlen; i > 0; i--) {
1669 while (OP(s = *scan++) != OCHAR)
1670 continue;
1671 assert(cp < g->must + g->mlen);
1672 *cp++ = (char)OPND(s);
1673 }
1674 assert(cp == g->must + g->mlen);
1675 *cp++ = '\0'; /* just on general principles */
1676 }
1677
1678 /*
1679 - pluscount - count + nesting
1680 == static sopno pluscount(register struct parse *p, register struct re_guts *g);
1681 */
1682 static sopno /* nesting depth */
1683 pluscount(p, g)
1684 struct parse *p;
1685 register struct re_guts *g;
1686 {
1687 register sop *scan;
1688 register sop s;
1689 register sopno plusnest = 0;
1690 register sopno maxnest = 0;
1691
1692 if (p->error != 0)
1693 return(0); /* there may not be an OEND */
1694
1695 scan = g->strip + 1;
1696 do {
1697 s = *scan++;
1698 switch (OP(s)) {
1699 case OPLUS_:
1700 plusnest++;
1701 break;
1702 case O_PLUS:
1703 if (plusnest > maxnest)
1704 maxnest = plusnest;
1705 plusnest--;
1706 break;
1707 }
1708 } while (OP(s) != OEND);
1709 if (plusnest != 0)
1710 g->iflags |= BAD;
1711 return(maxnest);
1712 }
mirror of libc