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