2 * Copyright (c) 1980, 1993
3 * The Regents of the University of California. All rights reserved.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 4. Neither the name of the University nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD$");
36 static const char copyright[] =
37 "@(#) Copyright (c) 1980, 1993\n\
38 The Regents of the University of California. All rights reserved.\n";
42 static const char sccsid[] = "@(#)regexp.c 8.1 (Berkeley) 6/6/93";
55 static void expconv(void);
57 boolean _escaped; /* true if we are currently _escaped */
58 char *s_start; /* start of string */
59 boolean l_onecase; /* true if upper and lower equivalent */
61 #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
63 /* STRNCMP - like strncmp except that we convert the
64 * first string to lower case before comparing
65 * if l_onecase is set.
70 register char *s1,*s2;
75 if (*s2 - makelower(*s1))
76 return (*s2 - makelower(*s1));
95 /* The following routine converts an irregular expression to
98 * Either meta symbols (\a \d or \p) or character strings or
99 * operations ( alternation or perenthesizing ) can be
100 * specified. Each starts with a descriptor byte. The descriptor
101 * byte has STR set for strings, META set for meta symbols
102 * and OPER set for operations.
103 * The descriptor byte can also have the OPT bit set if the object
104 * defined is optional. Also ALT can be set to indicate an alternation.
106 * For metasymbols the byte following the descriptor byte identities
107 * the meta symbol (containing an ascii 'a', 'd', 'p', '|', or '('). For
108 * strings the byte after the descriptor is a character count for
111 * meta symbols := descriptor
114 * strings := descriptor
118 * operatins := descriptor
124 * handy macros for accessing parts of match blocks
126 #define MSYM(A) (*(A+1)) /* symbol in a meta symbol block */
127 #define MNEXT(A) (A+2) /* character following a metasymbol block */
129 #define OSYM(A) (*(A+1)) /* symbol in an operation block */
130 #define OCNT(A) (*(A+2)) /* character count */
131 #define ONEXT(A) (A+3) /* next character after the operation */
132 #define OPTR(A) (A+*(A+2)) /* place pointed to by the operator */
134 #define SCNT(A) (*(A+1)) /* byte count of a string */
135 #define SSTR(A) (A+2) /* address of the string */
136 #define SNEXT(A) (A+2+*(A+1)) /* character following the string */
139 * bit flags in the descriptor
147 static char *ccre; /* pointer to current position in converted exp*/
148 static char *ure; /* pointer current position in unconverted exp */
152 char *re; /* unconverted irregular expression */
154 register char *cre; /* pointer to converted regular expression */
156 /* allocate room for the converted expression */
161 cre = malloc (4 * strlen(re) + 3);
165 /* start the conversion with a \a */
170 /* start the conversion (its recursive) */
179 register char *cs; /* pointer to current symbol in converted exp */
180 register char c; /* character being processed */
181 register char *acs; /* pinter to last alternate */
184 /* let the conversion begin */
187 while (*ure != NIL) {
188 switch (c = *ure++) {
191 switch (c = *ure++) {
193 /* escaped characters are just characters */
195 if (cs == NIL || (*cs & STR) == 0) {
205 /* normal(?) metacharacters */
210 if (acs != NIL && acs != cs) {
213 OCNT(acs) = ccre - acs;
226 /* just put the symbol in */
229 if (acs != NIL && acs != cs) {
232 OCNT(acs) = ccre - acs;
243 /* mark the last match sequence as optional */
249 /* recurse and define a subexpression */
251 if (acs != NIL && acs != cs) {
254 OCNT(acs) = ccre - acs;
264 OCNT(cs) = ccre - cs; /* offset to next symbol */
267 /* return from a recursion */
272 OCNT(acs) = ccre - acs;
283 /* mark the last match sequence as having an alternate */
284 /* the third byte will contain an offset to jump over the */
285 /* alternate match in case the first did not fail */
287 if (acs != NIL && acs != cs)
288 OCNT(ccre) = ccre - acs; /* make a back pointer */
296 acs = cs; /* remember that the pointer is to be filles */
299 /* if its not a metasymbol just build a scharacter string */
301 if (cs == NIL || (*cs & STR) == 0) {
315 OCNT(acs) = ccre - acs;
322 /* end of convertre */
326 * The following routine recognises an irregular expresion
327 * with the following special characters:
329 * \? - means last match was optional
330 * \a - matches any number of characters
331 * \d - matches any number of spaces and tabs
332 * \p - matches any number of alphanumeric
334 * characters matched will be copied into
335 * the area pointed to by 'name'.
337 * \( \) - grouping used mostly for alternation and
340 * The irregular expression must be translated to internal form
341 * prior to calling this routine
343 * The value returned is the pointer to the first non \a
348 expmatch (s, re, mstring)
349 register char *s; /* string to check for a match in */
350 register char *re; /* a converted irregular expression */
351 register char *mstring; /* where to put whatever matches a \p */
353 register char *cs; /* the current symbol */
354 register char *ptr,*s1; /* temporary pointer */
355 boolean matched; /* a temporary boolean */
357 /* initial conditions */
363 /* loop till expression string is exhausted (or at least pretty tired) */
365 switch (*cs & (OPER | STR | META)) {
367 /* try to match a string */
369 matched = !STRNCMP (s, SSTR(cs), SCNT(cs));
372 /* hoorah it matches */
375 } else if (*cs & ALT) {
377 /* alternation, skip to next expression */
379 } else if (*cs & OPT) {
381 /* the match is optional */
383 matched = 1; /* indicate a successful match */
386 /* no match, error return */
391 /* an operator, do something fancy */
395 /* this is an alternation */
399 /* last thing in the alternation was a match, skip ahead */
403 /* no match, keep trying */
407 /* this is a grouping, recurse */
409 ptr = expmatch (s, ONEXT(cs), mstring);
412 /* the subexpression matched */
415 } else if (*cs & ALT) {
417 /* alternation, skip to next expression */
419 } else if (*cs & OPT) {
421 /* the match is optional */
422 matched = 1; /* indicate a successful match */
425 /* no match, error return */
433 /* try to match a metasymbol */
437 /* try to match anything and remember what was matched */
440 * This is really the same as trying the match the
441 * remaining parts of the expression to any subset
446 ptr = expmatch (s1, MNEXT(cs), mstring);
447 if (ptr != NIL && s1 != s) {
449 /* we have a match, remember the match */
450 strncpy (mstring, s, s1 - s);
451 mstring[s1 - s] = '\0';
453 } else if (ptr != NIL && (*cs & OPT)) {
455 /* it was aoptional so no match is ok */
457 } else if (ptr != NIL) {
459 /* not optional and we still matched */
462 if (!(isalnum(*s1) || *s1 == '_' ||
465 /* C++ scope operator */
466 (strlen(s1) > 1 && *s1 == ':' && s1[1] == ':' &&
470 _escaped = _escaped ? FALSE : TRUE;
476 /* try to match anything */
479 * This is really the same as trying the match the
480 * remaining parts of the expression to any subset
485 ptr = expmatch (s1, MNEXT(cs), mstring);
486 if (ptr != NIL && s1 != s) {
488 /* we have a match */
490 } else if (ptr != NIL && (*cs & OPT)) {
492 /* it was aoptional so no match is ok */
494 } else if (ptr != NIL) {
496 /* not optional and we still matched */
500 _escaped = _escaped ? FALSE : TRUE;
506 /* fail if we are currently _escaped */
513 /* match any number of tabs and spaces */
516 while (*s == ' ' || *s == '\t')
518 if (s != ptr || s == s_start) {
520 /* match, be happy */
523 } else if (*s == '\n' || *s == '\0') {
525 /* match, be happy */
528 } else if (*cs & ALT) {
530 /* try the next part */
533 } else if (*cs & OPT) {
540 /* no match, error return */
544 /* check for end of line */
546 if (*s == '\0' || *s == '\n') {
548 /* match, be happy */
552 } else if (*cs & ALT) {
554 /* try the next part */
557 } else if (*cs & OPT) {
564 /* no match, error return */
568 /* check for start of line */
572 /* match, be happy */
575 } else if (*cs & ALT) {
577 /* try the next part */
580 } else if (*cs & OPT) {
587 /* no match, error return */
591 /* end of a subexpression, return success */