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