regcomp.c revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
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 */
56struct 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
70static void p_ere(struct parse *, int);
71static void p_ere_exp(struct parse *);
72static void p_str(struct parse *);
73static void p_bre(struct parse *, int, int);
74static int p_simp_re(struct parse *, int);
75static int p_count(struct parse *);
76static void p_bracket(struct parse *);
77static void p_b_term(struct parse *, cset *);
78static void p_b_cclass(struct parse *, cset *);
79static void p_b_eclass(struct parse *, cset *);
80static char p_b_symbol(struct parse *);
81static char p_b_coll_elem(struct parse *, int);
82static char othercase(int);
83static void bothcases(struct parse *, int);
84static void ordinary(struct parse *, int);
85static void nonnewline(struct parse *);
86static void repeat(struct parse *, sopno, int, int);
87static int seterr(struct parse *, int);
88static cset *allocset(struct parse *);
89static void freeset(struct parse *, cset *);
90static int freezeset(struct parse *, cset *);
91static int firstch(struct parse *, cset *);
92static int nch(struct parse *, cset *);
93static void mcadd(struct parse *, cset *, const char *);
94static void mcinvert(struct parse *, cset *);
95static void mccase(struct parse *, cset *);
96static int isinsets(struct re_guts *, int);
97static int samesets(struct re_guts *, int, int);
98static void categorize(struct parse *, struct re_guts *);
99static sopno dupl(struct parse *, sopno, sopno);
100static void doemit(struct parse *, sop, size_t);
101static void doinsert(struct parse *, sop, size_t, sopno);
102static void dofwd(struct parse *, sopno, sop);
103static void enlarge(struct parse *, sopno);
104static void stripsnug(struct parse *, struct re_guts *);
105static void findmust(struct parse *, struct re_guts *);
106static sopno pluscount(struct parse *, struct re_guts *);
107
108static 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
148static 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 */
156int				/* 0 success, otherwise REG_something */
157llvm_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 */
256static void
257p_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 */
299static void
300p_ere_exp(struct parse *p)
301{
302	char c;
303	sopno pos;
304	int count;
305	int count2;
306	int backrefnum;
307	sopno subno;
308	int wascaret = 0;
309
310	assert(MORE());		/* caller should have ensured this */
311	c = GETNEXT();
312
313	pos = HERE();
314	switch (c) {
315	case '(':
316		REQUIRE(MORE(), REG_EPAREN);
317		p->g->nsub++;
318		subno = p->g->nsub;
319		if (subno < NPAREN)
320			p->pbegin[subno] = HERE();
321		EMIT(OLPAREN, subno);
322		if (!SEE(')'))
323			p_ere(p, ')');
324		if (subno < NPAREN) {
325			p->pend[subno] = HERE();
326			assert(p->pend[subno] != 0);
327		}
328		EMIT(ORPAREN, subno);
329		MUSTEAT(')', REG_EPAREN);
330		break;
331#ifndef POSIX_MISTAKE
332	case ')':		/* happens only if no current unmatched ( */
333		/*
334		 * You may ask, why the ifndef?  Because I didn't notice
335		 * this until slightly too late for 1003.2, and none of the
336		 * other 1003.2 regular-expression reviewers noticed it at
337		 * all.  So an unmatched ) is legal POSIX, at least until
338		 * we can get it fixed.
339		 */
340		SETERROR(REG_EPAREN);
341		break;
342#endif
343	case '^':
344		EMIT(OBOL, 0);
345		p->g->iflags |= USEBOL;
346		p->g->nbol++;
347		wascaret = 1;
348		break;
349	case '$':
350		EMIT(OEOL, 0);
351		p->g->iflags |= USEEOL;
352		p->g->neol++;
353		break;
354	case '|':
355		SETERROR(REG_EMPTY);
356		break;
357	case '*':
358	case '+':
359	case '?':
360		SETERROR(REG_BADRPT);
361		break;
362	case '.':
363		if (p->g->cflags&REG_NEWLINE)
364			nonnewline(p);
365		else
366			EMIT(OANY, 0);
367		break;
368	case '[':
369		p_bracket(p);
370		break;
371	case '\\':
372		REQUIRE(MORE(), REG_EESCAPE);
373		c = GETNEXT();
374		if (c >= '1' && c <= '9') {
375			/* \[0-9] is taken to be a back-reference to a previously specified
376			 * matching group. backrefnum will hold the number. The matching
377			 * group must exist (i.e. if \4 is found there must have been at
378			 * least 4 matching groups specified in the pattern previously).
379			 */
380			backrefnum = c - '0';
381			if (p->pend[backrefnum] == 0) {
382				SETERROR(REG_ESUBREG);
383				break;
384			}
385
386			/* Make sure everything checks out and emit the sequence
387			 * that marks a back-reference to the parse structure.
388			 */
389			assert(backrefnum <= p->g->nsub);
390			EMIT(OBACK_, backrefnum);
391			assert(p->pbegin[backrefnum] != 0);
392			assert(OP(p->strip[p->pbegin[backrefnum]]) != OLPAREN);
393			assert(OP(p->strip[p->pend[backrefnum]]) != ORPAREN);
394			(void) dupl(p, p->pbegin[backrefnum]+1, p->pend[backrefnum]);
395			EMIT(O_BACK, backrefnum);
396			p->g->backrefs = 1;
397		} else {
398			/* Other chars are simply themselves when escaped with a backslash.
399			 */
400			ordinary(p, c);
401		}
402		break;
403	case '{':		/* okay as ordinary except if digit follows */
404		REQUIRE(!MORE() || !isdigit((uch)PEEK()), REG_BADRPT);
405		/* FALLTHROUGH */
406	default:
407		ordinary(p, c);
408		break;
409	}
410
411	if (!MORE())
412		return;
413	c = PEEK();
414	/* we call { a repetition if followed by a digit */
415	if (!( c == '*' || c == '+' || c == '?' ||
416				(c == '{' && MORE2() && isdigit((uch)PEEK2())) ))
417		return;		/* no repetition, we're done */
418	NEXT();
419
420	REQUIRE(!wascaret, REG_BADRPT);
421	switch (c) {
422	case '*':	/* implemented as +? */
423		/* this case does not require the (y|) trick, noKLUDGE */
424		INSERT(OPLUS_, pos);
425		ASTERN(O_PLUS, pos);
426		INSERT(OQUEST_, pos);
427		ASTERN(O_QUEST, pos);
428		break;
429	case '+':
430		INSERT(OPLUS_, pos);
431		ASTERN(O_PLUS, pos);
432		break;
433	case '?':
434		/* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
435		INSERT(OCH_, pos);		/* offset slightly wrong */
436		ASTERN(OOR1, pos);		/* this one's right */
437		AHEAD(pos);			/* fix the OCH_ */
438		EMIT(OOR2, 0);			/* offset very wrong... */
439		AHEAD(THERE());			/* ...so fix it */
440		ASTERN(O_CH, THERETHERE());
441		break;
442	case '{':
443		count = p_count(p);
444		if (EAT(',')) {
445			if (isdigit((uch)PEEK())) {
446				count2 = p_count(p);
447				REQUIRE(count <= count2, REG_BADBR);
448			} else		/* single number with comma */
449				count2 = INFINITY;
450		} else		/* just a single number */
451			count2 = count;
452		repeat(p, pos, count, count2);
453		if (!EAT('}')) {	/* error heuristics */
454			while (MORE() && PEEK() != '}')
455				NEXT();
456			REQUIRE(MORE(), REG_EBRACE);
457			SETERROR(REG_BADBR);
458		}
459		break;
460	}
461
462	if (!MORE())
463		return;
464	c = PEEK();
465	if (!( c == '*' || c == '+' || c == '?' ||
466				(c == '{' && MORE2() && isdigit((uch)PEEK2())) ) )
467		return;
468	SETERROR(REG_BADRPT);
469}
470
471/*
472 - p_str - string (no metacharacters) "parser"
473 */
474static void
475p_str(struct parse *p)
476{
477	REQUIRE(MORE(), REG_EMPTY);
478	while (MORE())
479		ordinary(p, GETNEXT());
480}
481
482/*
483 - p_bre - BRE parser top level, anchoring and concatenation
484 * Giving end1 as OUT essentially eliminates the end1/end2 check.
485 *
486 * This implementation is a bit of a kludge, in that a trailing $ is first
487 * taken as an ordinary character and then revised to be an anchor.  The
488 * only undesirable side effect is that '$' gets included as a character
489 * category in such cases.  This is fairly harmless; not worth fixing.
490 * The amount of lookahead needed to avoid this kludge is excessive.
491 */
492static void
493p_bre(struct parse *p,
494    int end1,		/* first terminating character */
495    int end2)		/* second terminating character */
496{
497	sopno start = HERE();
498	int first = 1;			/* first subexpression? */
499	int wasdollar = 0;
500
501	if (EAT('^')) {
502		EMIT(OBOL, 0);
503		p->g->iflags |= USEBOL;
504		p->g->nbol++;
505	}
506	while (MORE() && !SEETWO(end1, end2)) {
507		wasdollar = p_simp_re(p, first);
508		first = 0;
509	}
510	if (wasdollar) {	/* oops, that was a trailing anchor */
511		DROP(1);
512		EMIT(OEOL, 0);
513		p->g->iflags |= USEEOL;
514		p->g->neol++;
515	}
516
517	REQUIRE(HERE() != start, REG_EMPTY);	/* require nonempty */
518}
519
520/*
521 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
522 */
523static int			/* was the simple RE an unbackslashed $? */
524p_simp_re(struct parse *p,
525    int starordinary)		/* is a leading * an ordinary character? */
526{
527	int c;
528	int count;
529	int count2;
530	sopno pos;
531	int i;
532	sopno subno;
533#	define	BACKSL	(1<<CHAR_BIT)
534
535        pos = HERE(); /* repetition op, if any, covers from here */
536
537        assert(MORE()); /* caller should have ensured this */
538        c = GETNEXT();
539	if (c == '\\') {
540		REQUIRE(MORE(), REG_EESCAPE);
541		c = BACKSL | GETNEXT();
542	}
543	switch (c) {
544	case '.':
545		if (p->g->cflags&REG_NEWLINE)
546			nonnewline(p);
547		else
548			EMIT(OANY, 0);
549		break;
550	case '[':
551		p_bracket(p);
552		break;
553	case BACKSL|'{':
554		SETERROR(REG_BADRPT);
555		break;
556	case BACKSL|'(':
557		p->g->nsub++;
558		subno = p->g->nsub;
559		if (subno < NPAREN)
560			p->pbegin[subno] = HERE();
561		EMIT(OLPAREN, subno);
562		/* the MORE here is an error heuristic */
563		if (MORE() && !SEETWO('\\', ')'))
564			p_bre(p, '\\', ')');
565		if (subno < NPAREN) {
566			p->pend[subno] = HERE();
567			assert(p->pend[subno] != 0);
568		}
569		EMIT(ORPAREN, subno);
570		REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
571		break;
572	case BACKSL|')':	/* should not get here -- must be user */
573	case BACKSL|'}':
574		SETERROR(REG_EPAREN);
575		break;
576	case BACKSL|'1':
577	case BACKSL|'2':
578	case BACKSL|'3':
579	case BACKSL|'4':
580	case BACKSL|'5':
581	case BACKSL|'6':
582	case BACKSL|'7':
583	case BACKSL|'8':
584	case BACKSL|'9':
585		i = (c&~BACKSL) - '0';
586		assert(i < NPAREN);
587		if (p->pend[i] != 0) {
588			assert(i <= p->g->nsub);
589			EMIT(OBACK_, i);
590			assert(p->pbegin[i] != 0);
591			assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
592			assert(OP(p->strip[p->pend[i]]) == ORPAREN);
593			(void) dupl(p, p->pbegin[i]+1, p->pend[i]);
594			EMIT(O_BACK, i);
595		} else
596			SETERROR(REG_ESUBREG);
597		p->g->backrefs = 1;
598		break;
599	case '*':
600		REQUIRE(starordinary, REG_BADRPT);
601		/* FALLTHROUGH */
602	default:
603		ordinary(p, (char)c);
604		break;
605	}
606
607	if (EAT('*')) {		/* implemented as +? */
608		/* this case does not require the (y|) trick, noKLUDGE */
609		INSERT(OPLUS_, pos);
610		ASTERN(O_PLUS, pos);
611		INSERT(OQUEST_, pos);
612		ASTERN(O_QUEST, pos);
613	} else if (EATTWO('\\', '{')) {
614		count = p_count(p);
615		if (EAT(',')) {
616			if (MORE() && isdigit((uch)PEEK())) {
617				count2 = p_count(p);
618				REQUIRE(count <= count2, REG_BADBR);
619			} else		/* single number with comma */
620				count2 = INFINITY;
621		} else		/* just a single number */
622			count2 = count;
623		repeat(p, pos, count, count2);
624		if (!EATTWO('\\', '}')) {	/* error heuristics */
625			while (MORE() && !SEETWO('\\', '}'))
626				NEXT();
627			REQUIRE(MORE(), REG_EBRACE);
628			SETERROR(REG_BADBR);
629		}
630	} else if (c == '$')	/* $ (but not \$) ends it */
631		return(1);
632
633	return(0);
634}
635
636/*
637 - p_count - parse a repetition count
638 */
639static int			/* the value */
640p_count(struct parse *p)
641{
642	int count = 0;
643	int ndigits = 0;
644
645	while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {
646		count = count*10 + (GETNEXT() - '0');
647		ndigits++;
648	}
649
650	REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
651	return(count);
652}
653
654/*
655 - p_bracket - parse a bracketed character list
656 *
657 * Note a significant property of this code:  if the allocset() did SETERROR,
658 * no set operations are done.
659 */
660static void
661p_bracket(struct parse *p)
662{
663	cset *cs;
664	int invert = 0;
665
666	/* Dept of Truly Sickening Special-Case Kludges */
667	if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
668		EMIT(OBOW, 0);
669		NEXTn(6);
670		return;
671	}
672	if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
673		EMIT(OEOW, 0);
674		NEXTn(6);
675		return;
676	}
677
678	if ((cs = allocset(p)) == NULL) {
679		/* allocset did set error status in p */
680		return;
681	}
682
683	if (EAT('^'))
684		invert++;	/* make note to invert set at end */
685	if (EAT(']'))
686		CHadd(cs, ']');
687	else if (EAT('-'))
688		CHadd(cs, '-');
689	while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
690		p_b_term(p, cs);
691	if (EAT('-'))
692		CHadd(cs, '-');
693	MUSTEAT(']', REG_EBRACK);
694
695	if (p->error != 0) {	/* don't mess things up further */
696		freeset(p, cs);
697		return;
698	}
699
700	if (p->g->cflags&REG_ICASE) {
701		int i;
702		int ci;
703
704		for (i = p->g->csetsize - 1; i >= 0; i--)
705			if (CHIN(cs, i) && isalpha(i)) {
706				ci = othercase(i);
707				if (ci != i)
708					CHadd(cs, ci);
709			}
710		if (cs->multis != NULL)
711			mccase(p, cs);
712	}
713	if (invert) {
714		int i;
715
716		for (i = p->g->csetsize - 1; i >= 0; i--)
717			if (CHIN(cs, i))
718				CHsub(cs, i);
719			else
720				CHadd(cs, i);
721		if (p->g->cflags&REG_NEWLINE)
722			CHsub(cs, '\n');
723		if (cs->multis != NULL)
724			mcinvert(p, cs);
725	}
726
727	assert(cs->multis == NULL);		/* xxx */
728
729	if (nch(p, cs) == 1) {		/* optimize singleton sets */
730		ordinary(p, firstch(p, cs));
731		freeset(p, cs);
732	} else
733		EMIT(OANYOF, freezeset(p, cs));
734}
735
736/*
737 - p_b_term - parse one term of a bracketed character list
738 */
739static void
740p_b_term(struct parse *p, cset *cs)
741{
742	char c;
743	char start, finish;
744	int i;
745
746	/* classify what we've got */
747	switch ((MORE()) ? PEEK() : '\0') {
748	case '[':
749		c = (MORE2()) ? PEEK2() : '\0';
750		break;
751	case '-':
752		SETERROR(REG_ERANGE);
753		return;			/* NOTE RETURN */
754		break;
755	default:
756		c = '\0';
757		break;
758	}
759
760	switch (c) {
761	case ':':		/* character class */
762		NEXT2();
763		REQUIRE(MORE(), REG_EBRACK);
764		c = PEEK();
765		REQUIRE(c != '-' && c != ']', REG_ECTYPE);
766		p_b_cclass(p, cs);
767		REQUIRE(MORE(), REG_EBRACK);
768		REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
769		break;
770	case '=':		/* equivalence class */
771		NEXT2();
772		REQUIRE(MORE(), REG_EBRACK);
773		c = PEEK();
774		REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
775		p_b_eclass(p, cs);
776		REQUIRE(MORE(), REG_EBRACK);
777		REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
778		break;
779	default:		/* symbol, ordinary character, or range */
780/* xxx revision needed for multichar stuff */
781		start = p_b_symbol(p);
782		if (SEE('-') && MORE2() && PEEK2() != ']') {
783			/* range */
784			NEXT();
785			if (EAT('-'))
786				finish = '-';
787			else
788				finish = p_b_symbol(p);
789		} else
790			finish = start;
791/* xxx what about signed chars here... */
792		REQUIRE(start <= finish, REG_ERANGE);
793		for (i = start; i <= finish; i++)
794			CHadd(cs, i);
795		break;
796	}
797}
798
799/*
800 - p_b_cclass - parse a character-class name and deal with it
801 */
802static void
803p_b_cclass(struct parse *p, cset *cs)
804{
805	char *sp = p->next;
806	struct cclass *cp;
807	size_t len;
808	const char *u;
809	char c;
810
811	while (MORE() && isalpha((uch)PEEK()))
812		NEXT();
813	len = p->next - sp;
814	for (cp = cclasses; cp->name != NULL; cp++)
815		if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
816			break;
817	if (cp->name == NULL) {
818		/* oops, didn't find it */
819		SETERROR(REG_ECTYPE);
820		return;
821	}
822
823	u = cp->chars;
824	while ((c = *u++) != '\0')
825		CHadd(cs, c);
826	for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
827		MCadd(p, cs, u);
828}
829
830/*
831 - p_b_eclass - parse an equivalence-class name and deal with it
832 *
833 * This implementation is incomplete. xxx
834 */
835static void
836p_b_eclass(struct parse *p, cset *cs)
837{
838	char c;
839
840	c = p_b_coll_elem(p, '=');
841	CHadd(cs, c);
842}
843
844/*
845 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
846 */
847static char			/* value of symbol */
848p_b_symbol(struct parse *p)
849{
850	char value;
851
852	REQUIRE(MORE(), REG_EBRACK);
853	if (!EATTWO('[', '.'))
854		return(GETNEXT());
855
856	/* collating symbol */
857	value = p_b_coll_elem(p, '.');
858	REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
859	return(value);
860}
861
862/*
863 - p_b_coll_elem - parse a collating-element name and look it up
864 */
865static char			/* value of collating element */
866p_b_coll_elem(struct parse *p,
867    int endc)			/* name ended by endc,']' */
868{
869	char *sp = p->next;
870	struct cname *cp;
871	int len;
872
873	while (MORE() && !SEETWO(endc, ']'))
874		NEXT();
875	if (!MORE()) {
876		SETERROR(REG_EBRACK);
877		return(0);
878	}
879	len = p->next - sp;
880	for (cp = cnames; cp->name != NULL; cp++)
881		if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
882			return(cp->code);	/* known name */
883	if (len == 1)
884		return(*sp);	/* single character */
885	SETERROR(REG_ECOLLATE);			/* neither */
886	return(0);
887}
888
889/*
890 - othercase - return the case counterpart of an alphabetic
891 */
892static char			/* if no counterpart, return ch */
893othercase(int ch)
894{
895	ch = (uch)ch;
896	assert(isalpha(ch));
897	if (isupper(ch))
898		return ((uch)tolower(ch));
899	else if (islower(ch))
900		return ((uch)toupper(ch));
901	else			/* peculiar, but could happen */
902		return(ch);
903}
904
905/*
906 - bothcases - emit a dualcase version of a two-case character
907 *
908 * Boy, is this implementation ever a kludge...
909 */
910static void
911bothcases(struct parse *p, int ch)
912{
913	char *oldnext = p->next;
914	char *oldend = p->end;
915	char bracket[3];
916
917	ch = (uch)ch;
918	assert(othercase(ch) != ch);	/* p_bracket() would recurse */
919	p->next = bracket;
920	p->end = bracket+2;
921	bracket[0] = ch;
922	bracket[1] = ']';
923	bracket[2] = '\0';
924	p_bracket(p);
925	assert(p->next == bracket+2);
926	p->next = oldnext;
927	p->end = oldend;
928}
929
930/*
931 - ordinary - emit an ordinary character
932 */
933static void
934ordinary(struct parse *p, int ch)
935{
936	cat_t *cap = p->g->categories;
937
938	if ((p->g->cflags&REG_ICASE) && isalpha((uch)ch) && othercase(ch) != ch)
939		bothcases(p, ch);
940	else {
941		EMIT(OCHAR, (uch)ch);
942		if (cap[ch] == 0)
943			cap[ch] = p->g->ncategories++;
944	}
945}
946
947/*
948 - nonnewline - emit REG_NEWLINE version of OANY
949 *
950 * Boy, is this implementation ever a kludge...
951 */
952static void
953nonnewline(struct parse *p)
954{
955	char *oldnext = p->next;
956	char *oldend = p->end;
957	char bracket[4];
958
959	p->next = bracket;
960	p->end = bracket+3;
961	bracket[0] = '^';
962	bracket[1] = '\n';
963	bracket[2] = ']';
964	bracket[3] = '\0';
965	p_bracket(p);
966	assert(p->next == bracket+3);
967	p->next = oldnext;
968	p->end = oldend;
969}
970
971/*
972 - repeat - generate code for a bounded repetition, recursively if needed
973 */
974static void
975repeat(struct parse *p,
976    sopno start,		/* operand from here to end of strip */
977    int from,			/* repeated from this number */
978    int to)			/* to this number of times (maybe INFINITY) */
979{
980	sopno finish = HERE();
981#	define	N	2
982#	define	INF	3
983#	define	REP(f, t)	((f)*8 + (t))
984#	define	MAP(n)	(((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
985	sopno copy;
986
987	if (p->error != 0)	/* head off possible runaway recursion */
988		return;
989
990	assert(from <= to);
991
992	switch (REP(MAP(from), MAP(to))) {
993	case REP(0, 0):			/* must be user doing this */
994		DROP(finish-start);	/* drop the operand */
995		break;
996	case REP(0, 1):			/* as x{1,1}? */
997	case REP(0, N):			/* as x{1,n}? */
998	case REP(0, INF):		/* as x{1,}? */
999		/* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1000		INSERT(OCH_, start);		/* offset is wrong... */
1001		repeat(p, start+1, 1, to);
1002		ASTERN(OOR1, start);
1003		AHEAD(start);			/* ... fix it */
1004		EMIT(OOR2, 0);
1005		AHEAD(THERE());
1006		ASTERN(O_CH, THERETHERE());
1007		break;
1008	case REP(1, 1):			/* trivial case */
1009		/* done */
1010		break;
1011	case REP(1, N):			/* as x?x{1,n-1} */
1012		/* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1013		INSERT(OCH_, start);
1014		ASTERN(OOR1, start);
1015		AHEAD(start);
1016		EMIT(OOR2, 0);			/* offset very wrong... */
1017		AHEAD(THERE());			/* ...so fix it */
1018		ASTERN(O_CH, THERETHERE());
1019		copy = dupl(p, start+1, finish+1);
1020		assert(copy == finish+4);
1021		repeat(p, copy, 1, to-1);
1022		break;
1023	case REP(1, INF):		/* as x+ */
1024		INSERT(OPLUS_, start);
1025		ASTERN(O_PLUS, start);
1026		break;
1027	case REP(N, N):			/* as xx{m-1,n-1} */
1028		copy = dupl(p, start, finish);
1029		repeat(p, copy, from-1, to-1);
1030		break;
1031	case REP(N, INF):		/* as xx{n-1,INF} */
1032		copy = dupl(p, start, finish);
1033		repeat(p, copy, from-1, to);
1034		break;
1035	default:			/* "can't happen" */
1036		SETERROR(REG_ASSERT);	/* just in case */
1037		break;
1038	}
1039}
1040
1041/*
1042 - seterr - set an error condition
1043 */
1044static int			/* useless but makes type checking happy */
1045seterr(struct parse *p, int e)
1046{
1047	if (p->error == 0)	/* keep earliest error condition */
1048		p->error = e;
1049	p->next = nuls;		/* try to bring things to a halt */
1050	p->end = nuls;
1051	return(0);		/* make the return value well-defined */
1052}
1053
1054/*
1055 - allocset - allocate a set of characters for []
1056 */
1057static cset *
1058allocset(struct parse *p)
1059{
1060	int no = p->g->ncsets++;
1061	size_t nc;
1062	size_t nbytes;
1063	cset *cs;
1064	size_t css = (size_t)p->g->csetsize;
1065	int i;
1066
1067	if (no >= p->ncsalloc) {	/* need another column of space */
1068		void *ptr;
1069
1070		p->ncsalloc += CHAR_BIT;
1071		nc = p->ncsalloc;
1072		assert(nc % CHAR_BIT == 0);
1073		nbytes = nc / CHAR_BIT * css;
1074
1075		ptr = (cset *)realloc((char *)p->g->sets, nc * sizeof(cset));
1076		if (ptr == NULL)
1077			goto nomem;
1078		p->g->sets = ptr;
1079
1080		ptr = (uch *)realloc((char *)p->g->setbits, nbytes);
1081		if (ptr == NULL)
1082			goto nomem;
1083		p->g->setbits = ptr;
1084
1085		for (i = 0; i < no; i++)
1086			p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
1087
1088		(void) memset((char *)p->g->setbits + (nbytes - css), 0, css);
1089	}
1090	/* XXX should not happen */
1091	if (p->g->sets == NULL || p->g->setbits == NULL)
1092		goto nomem;
1093
1094	cs = &p->g->sets[no];
1095	cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
1096	cs->mask = 1 << ((no) % CHAR_BIT);
1097	cs->hash = 0;
1098	cs->smultis = 0;
1099	cs->multis = NULL;
1100
1101	return(cs);
1102nomem:
1103	free(p->g->sets);
1104	p->g->sets = NULL;
1105	free(p->g->setbits);
1106	p->g->setbits = NULL;
1107
1108	SETERROR(REG_ESPACE);
1109	/* caller's responsibility not to do set ops */
1110	return(NULL);
1111}
1112
1113/*
1114 - freeset - free a now-unused set
1115 */
1116static void
1117freeset(struct parse *p, cset *cs)
1118{
1119	size_t i;
1120	cset *top = &p->g->sets[p->g->ncsets];
1121	size_t css = (size_t)p->g->csetsize;
1122
1123	for (i = 0; i < css; i++)
1124		CHsub(cs, i);
1125	if (cs == top-1)	/* recover only the easy case */
1126		p->g->ncsets--;
1127}
1128
1129/*
1130 - freezeset - final processing on a set of characters
1131 *
1132 * The main task here is merging identical sets.  This is usually a waste
1133 * of time (although the hash code minimizes the overhead), but can win
1134 * big if REG_ICASE is being used.  REG_ICASE, by the way, is why the hash
1135 * is done using addition rather than xor -- all ASCII [aA] sets xor to
1136 * the same value!
1137 */
1138static int			/* set number */
1139freezeset(struct parse *p, cset *cs)
1140{
1141	uch h = cs->hash;
1142	size_t i;
1143	cset *top = &p->g->sets[p->g->ncsets];
1144	cset *cs2;
1145	size_t css = (size_t)p->g->csetsize;
1146
1147	/* look for an earlier one which is the same */
1148	for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
1149		if (cs2->hash == h && cs2 != cs) {
1150			/* maybe */
1151			for (i = 0; i < css; i++)
1152				if (!!CHIN(cs2, i) != !!CHIN(cs, i))
1153					break;		/* no */
1154			if (i == css)
1155				break;			/* yes */
1156		}
1157
1158	if (cs2 < top) {	/* found one */
1159		freeset(p, cs);
1160		cs = cs2;
1161	}
1162
1163	return((int)(cs - p->g->sets));
1164}
1165
1166/*
1167 - firstch - return first character in a set (which must have at least one)
1168 */
1169static int			/* character; there is no "none" value */
1170firstch(struct parse *p, cset *cs)
1171{
1172	size_t i;
1173	size_t css = (size_t)p->g->csetsize;
1174
1175	for (i = 0; i < css; i++)
1176		if (CHIN(cs, i))
1177			return((char)i);
1178	assert(never);
1179	return(0);		/* arbitrary */
1180}
1181
1182/*
1183 - nch - number of characters in a set
1184 */
1185static int
1186nch(struct parse *p, cset *cs)
1187{
1188	size_t i;
1189	size_t css = (size_t)p->g->csetsize;
1190	int n = 0;
1191
1192	for (i = 0; i < css; i++)
1193		if (CHIN(cs, i))
1194			n++;
1195	return(n);
1196}
1197
1198/*
1199 - mcadd - add a collating element to a cset
1200 */
1201static void
1202mcadd( struct parse *p, cset *cs, const char *cp)
1203{
1204	size_t oldend = cs->smultis;
1205	void *np;
1206
1207	cs->smultis += strlen(cp) + 1;
1208	np = realloc(cs->multis, cs->smultis);
1209	if (np == NULL) {
1210		if (cs->multis)
1211			free(cs->multis);
1212		cs->multis = NULL;
1213		SETERROR(REG_ESPACE);
1214		return;
1215	}
1216	cs->multis = np;
1217
1218	llvm_strlcpy(cs->multis + oldend - 1, cp, cs->smultis - oldend + 1);
1219}
1220
1221/*
1222 - mcinvert - invert the list of collating elements in a cset
1223 *
1224 * This would have to know the set of possibilities.  Implementation
1225 * is deferred.
1226 */
1227/* ARGSUSED */
1228static void
1229mcinvert(struct parse *p, cset *cs)
1230{
1231	assert(cs->multis == NULL);	/* xxx */
1232}
1233
1234/*
1235 - mccase - add case counterparts of the list of collating elements in a cset
1236 *
1237 * This would have to know the set of possibilities.  Implementation
1238 * is deferred.
1239 */
1240/* ARGSUSED */
1241static void
1242mccase(struct parse *p, cset *cs)
1243{
1244	assert(cs->multis == NULL);	/* xxx */
1245}
1246
1247/*
1248 - isinsets - is this character in any sets?
1249 */
1250static int			/* predicate */
1251isinsets(struct re_guts *g, int c)
1252{
1253	uch *col;
1254	int i;
1255	int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1256	unsigned uc = (uch)c;
1257
1258	for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1259		if (col[uc] != 0)
1260			return(1);
1261	return(0);
1262}
1263
1264/*
1265 - samesets - are these two characters in exactly the same sets?
1266 */
1267static int			/* predicate */
1268samesets(struct re_guts *g, int c1, int c2)
1269{
1270	uch *col;
1271	int i;
1272	int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1273	unsigned uc1 = (uch)c1;
1274	unsigned uc2 = (uch)c2;
1275
1276	for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1277		if (col[uc1] != col[uc2])
1278			return(0);
1279	return(1);
1280}
1281
1282/*
1283 - categorize - sort out character categories
1284 */
1285static void
1286categorize(struct parse *p, struct re_guts *g)
1287{
1288	cat_t *cats = g->categories;
1289	int c;
1290	int c2;
1291	cat_t cat;
1292
1293	/* avoid making error situations worse */
1294	if (p->error != 0)
1295		return;
1296
1297	for (c = CHAR_MIN; c <= CHAR_MAX; c++)
1298		if (cats[c] == 0 && isinsets(g, c)) {
1299			cat = g->ncategories++;
1300			cats[c] = cat;
1301			for (c2 = c+1; c2 <= CHAR_MAX; c2++)
1302				if (cats[c2] == 0 && samesets(g, c, c2))
1303					cats[c2] = cat;
1304		}
1305}
1306
1307/*
1308 - dupl - emit a duplicate of a bunch of sops
1309 */
1310static sopno			/* start of duplicate */
1311dupl(struct parse *p,
1312    sopno start,		/* from here */
1313    sopno finish)		/* to this less one */
1314{
1315	sopno ret = HERE();
1316	sopno len = finish - start;
1317
1318	assert(finish >= start);
1319	if (len == 0)
1320		return(ret);
1321	enlarge(p, p->ssize + len);	/* this many unexpected additions */
1322	assert(p->ssize >= p->slen + len);
1323	(void) memmove((char *)(p->strip + p->slen),
1324		(char *)(p->strip + start), (size_t)len*sizeof(sop));
1325	p->slen += len;
1326	return(ret);
1327}
1328
1329/*
1330 - doemit - emit a strip operator
1331 *
1332 * It might seem better to implement this as a macro with a function as
1333 * hard-case backup, but it's just too big and messy unless there are
1334 * some changes to the data structures.  Maybe later.
1335 */
1336static void
1337doemit(struct parse *p, sop op, size_t opnd)
1338{
1339	/* avoid making error situations worse */
1340	if (p->error != 0)
1341		return;
1342
1343	/* deal with oversize operands ("can't happen", more or less) */
1344	assert(opnd < 1<<OPSHIFT);
1345
1346	/* deal with undersized strip */
1347	if (p->slen >= p->ssize)
1348		enlarge(p, (p->ssize+1) / 2 * 3);	/* +50% */
1349	assert(p->slen < p->ssize);
1350
1351	/* finally, it's all reduced to the easy case */
1352	p->strip[p->slen++] = SOP(op, opnd);
1353}
1354
1355/*
1356 - doinsert - insert a sop into the strip
1357 */
1358static void
1359doinsert(struct parse *p, sop op, size_t opnd, sopno pos)
1360{
1361	sopno sn;
1362	sop s;
1363	int i;
1364
1365	/* avoid making error situations worse */
1366	if (p->error != 0)
1367		return;
1368
1369	sn = HERE();
1370	EMIT(op, opnd);		/* do checks, ensure space */
1371	assert(HERE() == sn+1);
1372	s = p->strip[sn];
1373
1374	/* adjust paren pointers */
1375	assert(pos > 0);
1376	for (i = 1; i < NPAREN; i++) {
1377		if (p->pbegin[i] >= pos) {
1378			p->pbegin[i]++;
1379		}
1380		if (p->pend[i] >= pos) {
1381			p->pend[i]++;
1382		}
1383	}
1384
1385	memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1386						(HERE()-pos-1)*sizeof(sop));
1387	p->strip[pos] = s;
1388}
1389
1390/*
1391 - dofwd - complete a forward reference
1392 */
1393static void
1394dofwd(struct parse *p, sopno pos, sop value)
1395{
1396	/* avoid making error situations worse */
1397	if (p->error != 0)
1398		return;
1399
1400	assert(value < 1<<OPSHIFT);
1401	p->strip[pos] = OP(p->strip[pos]) | value;
1402}
1403
1404/*
1405 - enlarge - enlarge the strip
1406 */
1407static void
1408enlarge(struct parse *p, sopno size)
1409{
1410	sop *sp;
1411
1412	if (p->ssize >= size)
1413		return;
1414
1415	sp = (sop *)realloc(p->strip, size*sizeof(sop));
1416	if (sp == NULL) {
1417		SETERROR(REG_ESPACE);
1418		return;
1419	}
1420	p->strip = sp;
1421	p->ssize = size;
1422}
1423
1424/*
1425 - stripsnug - compact the strip
1426 */
1427static void
1428stripsnug(struct parse *p, struct re_guts *g)
1429{
1430	g->nstates = p->slen;
1431	g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
1432	if (g->strip == NULL) {
1433		SETERROR(REG_ESPACE);
1434		g->strip = p->strip;
1435	}
1436}
1437
1438/*
1439 - findmust - fill in must and mlen with longest mandatory literal string
1440 *
1441 * This algorithm could do fancy things like analyzing the operands of |
1442 * for common subsequences.  Someday.  This code is simple and finds most
1443 * of the interesting cases.
1444 *
1445 * Note that must and mlen got initialized during setup.
1446 */
1447static void
1448findmust(struct parse *p, struct re_guts *g)
1449{
1450	sop *scan;
1451	sop *start = 0; /* start initialized in the default case, after that */
1452	sop *newstart = 0; /* newstart was initialized in the OCHAR case */
1453	sopno newlen;
1454	sop s;
1455	char *cp;
1456	sopno i;
1457
1458	/* avoid making error situations worse */
1459	if (p->error != 0)
1460		return;
1461
1462	/* find the longest OCHAR sequence in strip */
1463	newlen = 0;
1464	scan = g->strip + 1;
1465	do {
1466		s = *scan++;
1467		switch (OP(s)) {
1468		case OCHAR:		/* sequence member */
1469			if (newlen == 0)		/* new sequence */
1470				newstart = scan - 1;
1471			newlen++;
1472			break;
1473		case OPLUS_:		/* things that don't break one */
1474		case OLPAREN:
1475		case ORPAREN:
1476			break;
1477		case OQUEST_:		/* things that must be skipped */
1478		case OCH_:
1479			scan--;
1480			do {
1481				scan += OPND(s);
1482				s = *scan;
1483				/* assert() interferes w debug printouts */
1484				if (OP(s) != O_QUEST && OP(s) != O_CH &&
1485							OP(s) != OOR2) {
1486					g->iflags |= REGEX_BAD;
1487					return;
1488				}
1489			} while (OP(s) != O_QUEST && OP(s) != O_CH);
1490			/* fallthrough */
1491		default:		/* things that break a sequence */
1492			if (newlen > g->mlen) {		/* ends one */
1493				start = newstart;
1494				g->mlen = newlen;
1495			}
1496			newlen = 0;
1497			break;
1498		}
1499	} while (OP(s) != OEND);
1500
1501	if (g->mlen == 0)		/* there isn't one */
1502		return;
1503
1504	/* turn it into a character string */
1505	g->must = malloc((size_t)g->mlen + 1);
1506	if (g->must == NULL) {		/* argh; just forget it */
1507		g->mlen = 0;
1508		return;
1509	}
1510	cp = g->must;
1511	scan = start;
1512	for (i = g->mlen; i > 0; i--) {
1513		while (OP(s = *scan++) != OCHAR)
1514			continue;
1515		assert(cp < g->must + g->mlen);
1516		*cp++ = (char)OPND(s);
1517	}
1518	assert(cp == g->must + g->mlen);
1519	*cp++ = '\0';		/* just on general principles */
1520}
1521
1522/*
1523 - pluscount - count + nesting
1524 */
1525static sopno			/* nesting depth */
1526pluscount(struct parse *p, struct re_guts *g)
1527{
1528	sop *scan;
1529	sop s;
1530	sopno plusnest = 0;
1531	sopno maxnest = 0;
1532
1533	if (p->error != 0)
1534		return(0);	/* there may not be an OEND */
1535
1536	scan = g->strip + 1;
1537	do {
1538		s = *scan++;
1539		switch (OP(s)) {
1540		case OPLUS_:
1541			plusnest++;
1542			break;
1543		case O_PLUS:
1544			if (plusnest > maxnest)
1545				maxnest = plusnest;
1546			plusnest--;
1547			break;
1548		}
1549	} while (OP(s) != OEND);
1550	if (plusnest != 0)
1551		g->iflags |= REGEX_BAD;
1552	return(maxnest);
1553}
1554