10 #if ( defined BB_GREP || defined BB_FIND )
12 /* This also tries to find a needle in a haystack, but uses
13 * real regular expressions.... The fake regular expression
14 * version of find_match lives in utility.c. Using this version
15 * will add 3.9k to busybox...
18 extern int find_match(char *haystack, char *needle, int ignoreCase)
22 re = regcomp( needle);
23 status = regexec(re, haystack, FALSE, ignoreCase);
29 /* code swiped from elvis-tiny 1.4 (a clone of vi) and adjusted to
30 * suit the needs of busybox by Erik Andersen.
33 * "Elvis is freely redistributable, in either source form or executable form.
34 * There are no restrictions on how you may use it".
35 * Elvis was written by Steve Kirkendall <kirkenda@cs.pdx.edu>
38 * This file contains the code that compiles regular expressions and executes
39 * them. It supports the same syntax and features as vi's regular expression
40 * code. Specifically, the meta characters are:
41 * ^ matches the beginning of a line
42 * $ matches the end of a line
43 * \< matches the beginning of a word
44 * \> matches the end of a word
45 * . matches any single character
46 * [] matches any character in a character class
47 * \( delimits the start of a subexpression
48 * \) delimits the end of a subexpression
49 * * repeats the preceding 0 or more times
50 * NOTE: You cannot follow a \) with a *.
52 * The physical structure of a compiled RE is as follows:
53 * - First, there is a one-byte value that says how many character classes
54 * are used in this regular expression
55 * - Next, each character class is stored as a bitmap that is 256 bits
57 * - A mixture of literal characters and compiled meta characters follows.
58 * This begins with M_BEGIN(0) and ends with M_END(0). All meta chars
59 * are stored as a \n followed by a one-byte code, so they take up two
60 * bytes apiece. Literal characters take up one byte apiece. \n can't
61 * be used as a literal character.
67 static char *previous; /* the previous regexp, used when null regexp is given */
68 static char *previous1; /* a copy of the text from the previous substitution for regsub()*/
71 /* These are used to classify or recognize meta-characters */
73 #define BASE_META(m) ((m) - 256)
74 #define INT_META(c) ((c) + 256)
75 #define IS_META(m) ((m) >= 256)
76 #define IS_CLASS(m) ((m) >= M_CLASS(0) && (m) <= M_CLASS(9))
77 #define IS_START(m) ((m) >= M_START(0) && (m) <= M_START(9))
78 #define IS_END(m) ((m) >= M_END(0) && (m) <= M_END(9))
79 #define IS_CLOSURE(m) ((m) >= M_SPLAT && (m) <= M_QMARK)
80 #define ADD_META(s,m) (*(s)++ = META, *(s)++ = BASE_META(m))
81 #define GET_META(s) (*(s) == META ? INT_META(*++(s)) : *s)
83 /* These are the internal codes used for each type of meta-character */
84 #define M_BEGLINE 256 /* internal code for ^ */
85 #define M_ENDLINE 257 /* internal code for $ */
86 #define M_BEGWORD 258 /* internal code for \< */
87 #define M_ENDWORD 259 /* internal code for \> */
88 #define M_ANY 260 /* internal code for . */
89 #define M_SPLAT 261 /* internal code for * */
90 #define M_PLUS 262 /* internal code for \+ */
91 #define M_QMARK 263 /* internal code for \? */
92 #define M_CLASS(n) (264+(n)) /* internal code for [] */
93 #define M_START(n) (274+(n)) /* internal code for \( */
94 #define M_END(n) (284+(n)) /* internal code for \) */
96 /* These are used during compilation */
97 static int class_cnt; /* used to assign class IDs */
98 static int start_cnt; /* used to assign start IDs */
99 static int end_stk[NSUBEXP];/* used to assign end IDs */
101 static char *retext; /* points to the text being compiled */
103 /* error-handling stuff */
104 jmp_buf errorhandler;
105 #define FAIL(why) fprintf(stderr, why); longjmp(errorhandler, 1)
110 /* This function builds a bitmap for a particular class */
111 /* text -- start of the class */
112 /* bmap -- the bitmap */
113 static char *makeclass(char* text, char* bmap)
119 /* zero the bitmap */
120 for (i = 0; bmap && i < 32; i++)
125 /* see if we're going to complement this class */
132 /* add in the characters */
133 while (*text && *text != ']')
135 /* is this a span of characters? */
136 if (text[1] == '-' && text[2])
138 /* spans can't be backwards */
139 if (text[0] > text[2])
141 FAIL("Backwards span in []");
144 /* add each character in the span to the bitmap */
145 for (i = text[0]; bmap && i <= text[2]; i++)
147 bmap[i >> 3] |= (1 << (i & 7));
150 /* move past this span */
155 /* add this single character to the span */
159 bmap[i >> 3] |= (1 << (i & 7));
164 /* make sure the closing ] is missing */
170 /* if we're supposed to complement this class, then do so */
171 if (complement && bmap)
173 for (i = 0; i < 32; i++)
185 /* This function gets the next character or meta character from a string.
186 * The pointer is incremented by 1, or by 2 for \-quoted characters. For [],
187 * a bitmap is generated via makeclass() (if re is given), and the
188 * character-class text is skipped.
190 static int gettoken(sptr, re)
211 if (start_cnt >= NSUBEXP)
213 FAIL("Too many \\(s");
215 end_stk[end_sp++] = start_cnt;
216 return M_START(start_cnt++);
221 FAIL("Mismatched \\)");
223 return M_END(end_stk[--end_sp]);
245 if (*sptr == retext + 1)
265 /* make sure we don't have too many classes */
268 FAIL("Too many []s");
271 /* process the character list for this class */
274 /* generate the bitmap for this class */
275 *sptr = makeclass(*sptr, re->program + 1 + 32 * class_cnt);
279 /* skip to end of the class */
280 *sptr = makeclass(*sptr, (char *)0);
282 return M_CLASS(class_cnt++);
294 /* This function calculates the number of bytes that will be needed for a
295 * compiled RE. Its argument is the uncompiled version. It is not clever
296 * about catching syntax errors; that is done in a later pass.
298 static unsigned calcsize(text)
309 while ((token = gettoken(&text, (regexp *)0)) != 0)
315 else if (IS_META(token))
330 /*---------------------------------------------------------------------------*/
333 /* This function checks for a match between a character and a token which is
334 * known to represent a single character. It returns 0 if they match, or
337 static int match1(regexp* re, char ch, int token, int ignoreCase)
341 /* the end of a line can't match any RE of width 1 */
348 else if (IS_CLASS(token))
350 if (re->program[1 + 32 * (token - M_CLASS(0)) + (ch >> 3)] & (1 << (ch & 7)))
354 || (ignoreCase==TRUE && isupper(ch) && tolower(ch) == token))
363 /* This function checks characters up to and including the next closure, at
364 * which point it does a recursive call to check the rest of it. This function
365 * returns 0 if everything matches, or 1 if something doesn't match.
367 /* re -- the regular expression */
368 /* str -- the string */
369 /* prog -- a portion of re->program, an compiled RE */
370 /* here -- a portion of str, the string to compare it to */
371 static int match(regexp* re, char* str, char* prog, char* here, int ignoreCase)
377 for (token = GET_META(prog); !IS_CLOSURE(token); prog++, token = GET_META(prog))
381 /*case M_BEGLINE: can't happen; re->bol is used instead */
390 (isascii(here[-1]) && isalnum(here[-1]))))
395 if ((here[0] == '_' || isascii(here[0])) && isalnum(here[0]))
409 re->startp[token - M_START(0)] = (char *)here;
422 re->endp[token - M_END(0)] = (char *)here;
423 if (token == M_END(0))
429 default: /* literal, M_CLASS(n), or M_ANY */
430 if (match1(re, *here, token, ignoreCase) != 0)
438 /* step 1: see what we have to match against, and move "prog" to point
439 * the the remainder of the compiled RE.
442 prog++, token = GET_META(prog);
445 /* step 2: see how many times we can match that token against the string */
447 (closure != M_QMARK || nmatched < 1) && *here && match1(re, *here, token, ignoreCase) == 0;
452 /* step 3: try to match the remainder, and back off if it doesn't */
453 while (nmatched >= 0 && match(re, str, prog, here, ignoreCase) != 0)
459 /* so how did it work out? */
460 if (nmatched >= ((closure == M_PLUS) ? 1 : 0))
466 /* This function compiles a regexp. */
467 extern regexp *regcomp(char* text)
477 /* prepare for error handling */
479 if (setjmp(errorhandler))
488 /* if an empty regexp string was given, use the previous one */
493 FAIL("No previous RE");
497 else /* non-empty regexp given, so remember it */
501 previous = (char *)malloc((unsigned)(strlen(text) + 1));
503 strcpy(previous, text);
506 /* allocate memory */
511 size = calcsize(text) + sizeof(regexp);
512 re = (regexp *)malloc((unsigned)size);
516 FAIL("Not enough memory for this RE");
520 build = &re->program[1 + 32 * class_cnt];
521 re->program[0] = class_cnt;
522 for (token = 0; token < NSUBEXP; token++)
524 re->startp[token] = re->endp[token] = (char *)0;
534 for (token = M_START(0), peek = gettoken(&text, re);
536 token = peek, peek = gettoken(&text, re))
538 /* special processing for the closure operator */
539 if (IS_CLOSURE(peek))
541 /* detect misuse of closure operator */
544 FAIL("* or \\+ or \\? follows nothing");
546 else if (IS_META(token) && token != M_ANY && !IS_CLASS(token))
548 FAIL("* or \\+ or \\? can only follow a normal character or . or []");
551 /* it is okay -- make it prefix instead of postfix */
552 ADD_META(build, peek);
554 /* take care of "needfirst" - is this the first char? */
555 if (needfirst && peek == M_PLUS && !IS_META(token))
561 /* we used "peek" -- need to refill it */
562 peek = gettoken(&text, re);
563 if (IS_CLOSURE(peek))
565 FAIL("* or \\+ or \\? doubled up");
568 else if (!IS_META(token))
570 /* normal char is NOT argument of closure */
578 else if (token == M_ANY || IS_CLASS(token))
580 /* . or [] is NOT argument of closure */
585 /* the "token" character is not closure -- process it normally */
586 if (token == M_BEGLINE)
588 /* set the BOL flag instead of storing M_BEGLINE */
591 else if (IS_META(token))
593 ADD_META(build, token);
601 /* end it with a \) which MUST MATCH the opening \( */
602 ADD_META(build, M_END(0));
605 FAIL("Not enough \\)s");
614 /* This function searches through a string for text that matches an RE. */
615 /* re -- the compiled regexp to search for */
616 /* str -- the string to search through */
617 /* bol -- does str start at the beginning of a line? (boolean) */
618 /* ignoreCase -- ignoreCase or not */
619 extern int regexec(struct regexp* re, char* str, int bol, int ignoreCase)
621 char *prog; /* the entry point of re->program */
622 int len; /* length of the string */
625 /* if must start at the beginning of a line, and this isn't, then fail */
626 if (re->bol && bol==TRUE)
632 prog = re->program + 1 + 32 * re->program[0];
634 /* search for the RE in the string */
637 /* must occur at BOL */
639 && match1(re, *(char *)str, re->first, ignoreCase))/* wrong first letter? */
640 || len < re->minlen /* not long enough? */
641 || match(re, (char *)str, prog, str, ignoreCase)) /* doesn't match? */
642 return FALSE; /* THEN FAIL! */
644 else if (ignoreCase == FALSE)
646 /* can occur anywhere in the line, noignorecase */
647 for (here = (char *)str;
648 (re->first && re->first != *here)
649 || match(re, (char *)str, prog, here, ignoreCase);
652 if (len < re->minlen)
658 /* can occur anywhere in the line, ignorecase */
659 for (here = (char *)str;
660 (re->first && match1(re, *here, (int)re->first, ignoreCase))
661 || match(re, (char *)str, prog, here, ignoreCase);
664 if (len < re->minlen)
669 /* if we didn't fail, then we must have succeeded */
677 /* This performs substitutions after a regexp match has been found. */
678 extern void regsub(regexp* re, char* src, char* dst)
689 while ((c = *src++) != '\0')
691 /* recognize any meta characters */
701 end = cpy + strlen(cpy);
719 /* \0 thru \9 mean "copy subexpression" */
721 cpy = re->startp[(int)c];
722 end = re->endp[(int)c];
728 /* \U and \L mean "convert to upper/lowercase" */
734 /* \E ends the \U or \L */
738 /* "\&" means "original text" */
743 /* "\~" means "previous text, if any" */
747 /* ordinary char preceded by backslash */
754 /* ordinary character, so just copy it */
759 /* Note: to reach this point in the code, we must have evaded
760 * all "continue" statements. To do that, we must have hit
761 * a metacharacter that involves copying.
764 /* if there is nothing to copy, loop */
768 /* copy over a portion of the original */
775 /* convert to uppercase */
776 if (isascii(*cpy) && islower(*cpy))
778 *dst++ = toupper(*cpy);
789 /* convert to lowercase */
790 if (isascii(*cpy) && isupper(*cpy))
792 *dst++ = tolower(*cpy);
802 /* copy without any conversion */
806 /* \u and \l end automatically after the first char */
807 if (mod && (mod == 'u' || mod == 'l'))
815 /* remember what text we inserted this time */
818 previous1 = (char *)malloc((unsigned)(strlen(start) + 1));
820 strcpy(previous1, start);
824 #endif /* BB_REGEXP */