2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 1980, 1993
5 * The Regents of the University of California. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
38 static const char copyright[] =
39 "@(#) Copyright (c) 1980, 1993\n\
40 The Regents of the University of California. All rights reserved.\n";
44 static const char sccsid[] = "@(#)regexp.c 8.1 (Berkeley) 6/6/93";
54 static void expconv(void);
56 bool _escaped; /* true if we are currently x_escaped */
57 char *s_start; /* start of string */
58 bool l_onecase; /* true if upper and lower equivalent */
60 #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
62 /* STRNCMP - like strncmp except that we convert the
63 * first string to lower case before comparing
64 * if l_onecase is set.
68 STRNCMP(register char *s1, register char *s2, register int len)
72 if (*s2 - makelower(*s1))
73 return (*s2 - makelower(*s1));
92 /* The following routine converts an irregular expression to
95 * Either meta symbols (\a \d or \p) or character strings or
96 * operations ( alternation or parenthesizing ) can be
97 * specified. Each starts with a descriptor byte. The descriptor
98 * byte has STR set for strings, META set for meta symbols
99 * and OPER set for operations.
100 * The descriptor byte can also have the OPT bit set if the object
101 * defined is optional. Also ALT can be set to indicate an alternation.
103 * For metasymbols the byte following the descriptor byte identities
104 * the meta symbol (containing an ascii 'a', 'd', 'p', '|', or '('). For
105 * strings the byte after the descriptor is a character count for
108 * meta symbols := descriptor
111 * strings := descriptor
115 * operations := descriptor
121 * handy macros for accessing parts of match blocks
123 #define MSYM(A) (*(A+1)) /* symbol in a meta symbol block */
124 #define MNEXT(A) (A+2) /* character following a metasymbol block */
126 #define OSYM(A) (*(A+1)) /* symbol in an operation block */
127 #define OCNT(A) (*(A+2)) /* character count */
128 #define ONEXT(A) (A+3) /* next character after the operation */
129 #define OPTR(A) (A+*(A+2)) /* place pointed to by the operator */
131 #define SCNT(A) (*(A+1)) /* byte count of a string */
132 #define SSTR(A) (A+2) /* address of the string */
133 #define SNEXT(A) (A+2+*(A+1)) /* character following the string */
136 * bit flags in the descriptor
144 static char *ccre; /* pointer to current position in converted exp*/
145 static char *ure; /* pointer current position in unconverted exp */
147 /* re: unconverted irregular expression */
151 register char *cre; /* pointer to converted regular expression */
153 /* allocate room for the converted expression */
158 cre = malloc(4 * strlen(re) + 3);
162 /* start the conversion with a \a */
167 /* start the conversion (its recursive) */
176 register char *cs; /* pointer to current symbol in converted exp */
177 register char c; /* character being processed */
178 register char *acs; /* pinter to last alternate */
181 /* let the conversion begin */
185 switch (c = *ure++) {
188 switch (c = *ure++) {
190 /* escaped characters are just characters */
192 if (cs == NULL || (*cs & STR) == 0) {
202 /* normal(?) metacharacters */
207 if (acs != NULL && acs != cs) {
210 OCNT(acs) = ccre - acs;
223 /* just put the symbol in */
226 if (acs != NULL && acs != cs) {
229 OCNT(acs) = ccre - acs;
240 /* mark the last match sequence as optional */
246 /* recurse and define a subexpression */
248 if (acs != NULL && acs != cs) {
251 OCNT(acs) = ccre - acs;
261 OCNT(cs) = ccre - cs; /* offset to next symbol */
264 /* return from a recursion */
269 OCNT(acs) = ccre - acs;
280 /* mark the last match sequence as having an alternate */
281 /* the third byte will contain an offset to jump over the */
282 /* alternate match in case the first did not fail */
284 if (acs != NULL && acs != cs)
285 OCNT(ccre) = ccre - acs; /* make a back pointer */
293 acs = cs; /* remember that the pointer is to be filles */
296 /* if its not a metasymbol just build a scharacter string */
298 if (cs == NULL || (*cs & STR) == 0) {
312 OCNT(acs) = ccre - acs;
319 /* end of convertre */
323 * The following routine recognises an irregular expression
324 * with the following special characters:
326 * \? - means last match was optional
327 * \a - matches any number of characters
328 * \d - matches any number of spaces and tabs
329 * \p - matches any number of alphanumeric
331 * characters matched will be copied into
332 * the area pointed to by 'name'.
334 * \( \) - grouping used mostly for alternation and
337 * The irregular expression must be translated to internal form
338 * prior to calling this routine
340 * The value returned is the pointer to the first non \a
345 * s: string to check for a match in
346 * re: a converted irregular expression
347 * mstring: where to put whatever matches a \p
350 expmatch (register char *s, register char *re, register char *mstring)
352 register char *cs; /* the current symbol */
353 register char *ptr,*s1; /* temporary pointer */
354 bool matched; /* a temporary bool */
356 /* initial conditions */
362 /* loop till expression string is exhausted (or at least pretty tired) */
364 switch (*cs & (OPER | STR | META)) {
366 /* try to match a string */
368 matched = !STRNCMP (s, SSTR(cs), SCNT(cs));
371 /* hoorah it matches */
374 } else if (*cs & ALT) {
376 /* alternation, skip to next expression */
378 } else if (*cs & OPT) {
380 /* the match is optional */
382 matched = 1; /* indicate a successful match */
385 /* no match, error return */
390 /* an operator, do something fancy */
394 /* this is an alternation */
398 /* last thing in the alternation was a match, skip ahead */
402 /* no match, keep trying */
406 /* this is a grouping, recurse */
408 ptr = expmatch(s, ONEXT(cs), mstring);
411 /* the subexpression matched */
414 } else if (*cs & ALT) {
416 /* alternation, skip to next expression */
418 } else if (*cs & OPT) {
420 /* the match is optional */
421 matched = 1; /* indicate a successful match */
424 /* no match, error return */
432 /* try to match a metasymbol */
436 /* try to match anything and remember what was matched */
439 * This is really the same as trying the match the
440 * remaining parts of the expression to any subset
445 ptr = expmatch(s1, MNEXT(cs), mstring);
446 if (ptr != NULL && s1 != s) {
448 /* we have a match, remember the match */
449 strncpy (mstring, s, s1 - s);
450 mstring[s1 - s] = '\0';
452 } else if (ptr != NULL && (*cs & OPT)) {
454 /* it was aoptional so no match is ok */
456 } else if (ptr != NULL) {
458 /* not optional and we still matched */
461 if (!(isalnum(*s1) || *s1 == '_' ||
464 /* C++ scope operator */
465 (strlen(s1) > 1 && *s1 == ':' && s1[1] == ':' &&
469 _escaped = _escaped ? false : true;
475 /* try to match anything */
478 * This is really the same as trying the match the
479 * remaining parts of the expression to any subset
484 ptr = expmatch(s1, MNEXT(cs), mstring);
485 if (ptr != NULL && s1 != s) {
487 /* we have a match */
489 } else if (ptr != NULL && (*cs & OPT)) {
491 /* it was aoptional so no match is ok */
493 } else if (ptr != NULL) {
495 /* not optional and we still matched */
499 _escaped = _escaped ? false : true;
505 /* fail if we are currently _escaped */
512 /* match any number of tabs and spaces */
515 while (*s == ' ' || *s == '\t')
517 if (s != ptr || s == s_start) {
519 /* match, be happy */
522 } else if (*s == '\n' || *s == '\0') {
524 /* match, be happy */
527 } else if (*cs & ALT) {
529 /* try the next part */
532 } else if (*cs & OPT) {
539 /* no match, error return */
543 /* check for end of line */
545 if (*s == '\0' || *s == '\n') {
547 /* match, be happy */
551 } else if (*cs & ALT) {
553 /* try the next part */
556 } else if (*cs & OPT) {
563 /* no match, error return */
567 /* check for start of line */
571 /* match, be happy */
574 } else if (*cs & ALT) {
576 /* try the next part */
579 } else if (*cs & OPT) {
586 /* no match, error return */
590 /* end of a subexpression, return success */