libc/regex/regcomp.c

13  * This code is derived from software contributed to Berkeley by
25  *    may be used to endorse or promote products derived from this software
62  * Branching context, used to keep track of branch state for all of the branch-
63  * aware functions. In addition to keeping track of branch positions for the
64  * p_branch_* functions, we use this to simplify some clumsiness in BREs for
80  * parse structure, passed up and down to avoid global variables and
93 #	define	NPAREN	10	/* we need to remember () 1-9 for back refs */
138 static void repeat(struct parse *p, sopno start, int from, int to);
164 static char nuls[10];		/* place to point scanner in event of error */
235 	 * Limit the pattern space to avoid a 32-bit overflow on buffer
240 	 * generically (who are we to stop people from using ~715MB+
521 			/* Don't proceed to the POSIX bits if we've already handled it */
656  * bogus 'next' offset, since we still have more to parse
678  * This is to correct the bogus placeholder offset that we use.
692  * Signal to the parser that an empty branch has been encountered; this will,
693  * in the future, be used to allow for more permissive behavior with empty
709  * delimiters until we either run out of pattern or need to parse more pattern.
752 	/* Expression is terminating due to EOL token */
767  * taken as an ordinary character and then revised to be an anchor.
768  * The amount of lookahead needed to avoid this kludge is excessive.
1322 	 * Build a whitelist of characters that may be escaped to produce an
1325 	 * ordinary character yields undefined results according to
1327 	 * advantage of this and use escaped ordinary characters to provide
1416 		 * Kludge: character is too big to fit into an OCHAR operand.
1453  == static void repeat(struct parse *p, sopno start, int from, int to);
1457 	sopno start,		/* operand from here to end of strip */
1459 	int to)			/* to this number of times (maybe INFINITY) */
1471 	assert(from <= to);
1473 	switch (REP(MAP(from), MAP(to))) {
1482 		repeat(p, start+1, 1, to);
1502 		repeat(p, copy, 1, to-1);
1510 		repeat(p, copy, from-1, to-1);
1514 		repeat(p, copy, from-1, to);
1555 	p->next = nuls;		/* try to bring things to a halt */
1607 	/* Exclude the complicated cases we don't want to deal with */
1637  - CHadd - add character to character set.
1665  - CHaddrange - add all characters in the range [min,max] to a character set.
1689  - CHaddtype - add all characters of a certain type to a character set.
1717 	sopno finish)		/* to this less one */
1737  * It might seem better to implement this as a macro with a function as
1739  * some changes to the data structures.  Maybe later.
1756 	/* finally, it's all reduced to the easy case */
1877 	 * It's not generally safe to do a ``char'' substring search on
1985 			 * to calculate the offset -- so we give up;
2070 			/* We must skip to the next position, or we'll
2110  * A char jump is the number of characters one needs to jump based on
2130 	 * is equal to the number of characters in the pattern.
2136 	 * take us to the last character in the pattern equal to it
2137 	 * (notice that we match right to left, so that last character
2152  * A match jump is the number of characters one needs to advance based
2163 	int* pmatches;		/* pmatches[k] points to the next i
2207 	/* Compute the matchjump up to the last substring found to jump
2208 	 * to the beginning of the largest must pattern prefix matching