1 /* vi: set sw=4 ts=4: */
12 typedef struct regexp {
13 char *startp[NSUBEXP];
15 int minlen; /* length of shortest possible match */
16 char first; /* first character, if known; else \0 */
17 char bol; /* boolean: must start at beginning of line? */
18 char program[1]; /* Unwarranted chumminess with compiler. */
22 static regexp *regcomp(char* text);
23 static int regexec(struct regexp* re, char* str, int bol, int ignoreCase);
24 static void regsub(struct regexp* re, char* src, char* dst);
26 #if ( defined BB_GREP || defined BB_SED)
28 /* This also tries to find a needle in a haystack, but uses
29 * real regular expressions.... The fake regular expression
30 * version of find_match lives in utility.c. Using this version
31 * will add 3.9k to busybox...
34 extern int find_match(char *haystack, char *needle, int ignoreCase)
40 status = regexec(re, haystack, FALSE, ignoreCase);
46 /* This performs substitutions after a regexp match has been found.
47 * The new string is returned. It is malloc'ed, and do must be freed. */
48 extern int replace_match(char *haystack, char *needle, char *newNeedle,
53 char *s, buf[BUF_SIZE], *d = buf;
56 status = regexec(re, haystack, FALSE, ignoreCase);
61 /* copy stuff from before the match */
62 while (s < re->startp[0])
64 /* substitute for the matched part */
65 regsub(re, newNeedle, d);
68 } while (regexec(re, s, FALSE, ignoreCase) == TRUE);
69 /* copy stuff from after the match */
70 while ((*d++ = *s++)) {
73 strcpy(haystack, buf);
81 /* code swiped from elvis-tiny 1.4 (a clone of vi) and adjusted to
82 * suit the needs of busybox by Erik Andersen.
85 * "Elvis is freely redistributable, in either source form or executable form.
86 * There are no restrictions on how you may use it".
87 * Elvis was written by Steve Kirkendall <kirkenda@cs.pdx.edu>
90 * This file contains the code that compiles regular expressions and executes
91 * them. It supports the same syntax and features as vi's regular expression
92 * code. Specifically, the meta characters are:
93 * ^ matches the beginning of a line
94 * $ matches the end of a line
95 * \< matches the beginning of a word
96 * \> matches the end of a word
97 * . matches any single character
98 * [] matches any character in a character class
99 * \( delimits the start of a subexpression
100 * \) delimits the end of a subexpression
101 * * repeats the preceding 0 or more times
102 * NOTE: You cannot follow a \) with a *.
104 * The physical structure of a compiled RE is as follows:
105 * - First, there is a one-byte value that says how many character classes
106 * are used in this regular expression
107 * - Next, each character class is stored as a bitmap that is 256 bits
109 * - A mixture of literal characters and compiled meta characters follows.
110 * This begins with M_BEGIN(0) and ends with M_END(0). All meta chars
111 * are stored as a \n followed by a one-byte code, so they take up two
112 * bytes apiece. Literal characters take up one byte apiece. \n can't
113 * be used as a literal character.
119 static char *previous; /* the previous regexp, used when null regexp is given */
122 static char *previous1; /* a copy of the text from the previous substitution for regsub() */
126 /* These are used to classify or recognize meta-characters */
128 #define BASE_META(m) ((m) - 256)
129 #define INT_META(c) ((c) + 256)
130 #define IS_META(m) ((m) >= 256)
131 #define IS_CLASS(m) ((m) >= M_CLASS(0) && (m) <= M_CLASS(9))
132 #define IS_START(m) ((m) >= M_START(0) && (m) <= M_START(9))
133 #define IS_END(m) ((m) >= M_END(0) && (m) <= M_END(9))
134 #define IS_CLOSURE(m) ((m) >= M_SPLAT && (m) <= M_QMARK)
135 #define ADD_META(s,m) (*(s)++ = META, *(s)++ = BASE_META(m))
136 #define GET_META(s) (*(s) == META ? INT_META(*++(s)) : *s)
138 /* These are the internal codes used for each type of meta-character */
139 #define M_BEGLINE 256 /* internal code for ^ */
140 #define M_ENDLINE 257 /* internal code for $ */
141 #define M_BEGWORD 258 /* internal code for \< */
142 #define M_ENDWORD 259 /* internal code for \> */
143 #define M_ANY 260 /* internal code for . */
144 #define M_SPLAT 261 /* internal code for * */
145 #define M_PLUS 262 /* internal code for \+ */
146 #define M_QMARK 263 /* internal code for \? */
147 #define M_CLASS(n) (264+(n)) /* internal code for [] */
148 #define M_START(n) (274+(n)) /* internal code for \( */
149 #define M_END(n) (284+(n)) /* internal code for \) */
151 /* These are used during compilation */
152 static int class_cnt; /* used to assign class IDs */
153 static int start_cnt; /* used to assign start IDs */
154 static int end_stk[NSUBEXP]; /* used to assign end IDs */
156 static char *retext; /* points to the text being compiled */
158 /* error-handling stuff */
159 jmp_buf errorhandler;
161 #define FAIL(why) do {fprintf(stderr, why); longjmp(errorhandler, 1);} while (0)
166 /* This function builds a bitmap for a particular class */
167 /* text -- start of the class */
168 /* bmap -- the bitmap */
169 static char *makeclass(char *text, char *bmap)
175 /* zero the bitmap */
176 for (i = 0; bmap && i < 32; i++) {
180 /* see if we're going to complement this class */
186 /* add in the characters */
187 while (*text && *text != ']') {
188 /* is this a span of characters? */
189 if (text[1] == '-' && text[2]) {
190 /* spans can't be backwards */
191 if (text[0] > text[2]) {
192 FAIL("Backwards span in []");
195 /* add each character in the span to the bitmap */
196 for (i = text[0]; bmap && i <= text[2]; i++) {
197 bmap[i >> 3] |= (1 << (i & 7));
200 /* move past this span */
203 /* add this single character to the span */
206 bmap[i >> 3] |= (1 << (i & 7));
211 /* make sure the closing ] is missing */
212 if (*text++ != ']') {
216 /* if we're supposed to complement this class, then do so */
217 if (complement && bmap) {
218 for (i = 0; i < 32; i++) {
229 /* This function gets the next character or meta character from a string.
230 * The pointer is incremented by 1, or by 2 for \-quoted characters. For [],
231 * a bitmap is generated via makeclass() (if re is given), and the
232 * character-class text is skipped.
234 static int gettoken(sptr, re)
253 if (start_cnt >= NSUBEXP) {
254 FAIL("Too many \\(s");
256 end_stk[end_sp++] = start_cnt;
257 return M_START(start_cnt++);
261 FAIL("Mismatched \\)");
263 return M_END(end_stk[--end_sp]);
283 if (*sptr == retext + 1) {
301 /* make sure we don't have too many classes */
302 if (class_cnt >= 10) {
303 FAIL("Too many []s");
306 /* process the character list for this class */
308 /* generate the bitmap for this class */
309 *sptr = makeclass(*sptr, re->program + 1 + 32 * class_cnt);
311 /* skip to end of the class */
312 *sptr = makeclass(*sptr, (char *) 0);
314 return M_CLASS(class_cnt++);
325 /* This function calculates the number of bytes that will be needed for a
326 * compiled RE. Its argument is the uncompiled version. It is not clever
327 * about catching syntax errors; that is done in a later pass.
329 static unsigned calcsize(text)
340 while ((token = gettoken(&text, (regexp *) 0)) != 0) {
341 if (IS_CLASS(token)) {
343 } else if (IS_META(token)) {
355 /*---------------------------------------------------------------------------*/
358 /* This function checks for a match between a character and a token which is
359 * known to represent a single character. It returns 0 if they match, or
362 static int match1(regexp * re, char ch, int token, int ignoreCase)
365 /* the end of a line can't match any RE of width 1 */
368 if (token == M_ANY) {
370 } else if (IS_CLASS(token)) {
371 if (re->program[1 + 32 * (token - M_CLASS(0)) + (ch >> 3)] & (1 << (ch & 7)))
374 //fprintf(stderr, "match1: ch='%c' token='%c': ", ch, token);
375 if (ch == token || (ignoreCase == TRUE && tolower(ch) == tolower(token))) {
376 //fprintf(stderr, "match\n");
379 //fprintf(stderr, "no match\n");
385 /* This function checks characters up to and including the next closure, at
386 * which point it does a recursive call to check the rest of it. This function
387 * returns 0 if everything matches, or 1 if something doesn't match.
389 /* re -- the regular expression */
390 /* str -- the string */
391 /* prog -- a portion of re->program, an compiled RE */
392 /* here -- a portion of str, the string to compare it to */
393 static int match(regexp * re, char *str, char *prog, char *here,
400 for (token = GET_META(prog); !IS_CLOSURE(token);
401 prog++, token = GET_META(prog)) {
403 /*case M_BEGLINE: can't happen; re->bol is used instead */
412 (isascii(here[-1]) && isalnum(here[-1])))) return 1;
416 if ((here[0] == '_' || isascii(here[0])) && isalnum(here[0]))
430 re->startp[token - M_START(0)] = (char *) here;
443 re->endp[token - M_END(0)] = (char *) here;
444 if (token == M_END(0)) {
449 default: /* literal, M_CLASS(n), or M_ANY */
450 if (match1(re, *here, token, ignoreCase) != 0)
458 /* step 1: see what we have to match against, and move "prog" to point
459 * the the remainder of the compiled RE.
462 prog++, token = GET_META(prog);
465 /* step 2: see how many times we can match that token against the string */
467 (closure != M_QMARK || nmatched < 1) && *here
468 && match1(re, *here, token, ignoreCase) == 0; nmatched++, here++) {
471 /* step 3: try to match the remainder, and back off if it doesn't */
472 while (nmatched >= 0 && match(re, str, prog, here, ignoreCase) != 0) {
477 /* so how did it work out? */
478 if (nmatched >= ((closure == M_PLUS) ? 1 : 0))
484 /* This function compiles a regexp. */
485 static regexp *regcomp(char *text)
495 /* prepare for error handling */
497 if (setjmp(errorhandler)) {
504 /* if an empty regexp string was given, use the previous one */
507 FAIL("No previous RE");
510 } else { /* non-empty regexp given, so remember it */
514 previous = (char *) malloc((unsigned) (strlen(text) + 1));
516 strcpy(previous, text);
519 /* allocate memory */
524 size = calcsize(text) + sizeof(regexp);
525 re = (regexp *) malloc((unsigned) size);
528 FAIL("Not enough memory for this RE");
532 build = &re->program[1 + 32 * class_cnt];
533 re->program[0] = class_cnt;
534 for (token = 0; token < NSUBEXP; token++) {
535 re->startp[token] = re->endp[token] = (char *) 0;
545 for (token = M_START(0), peek = gettoken(&text, re);
546 token; token = peek, peek = gettoken(&text, re)) {
548 /* special processing for the closure operator */
549 if (IS_CLOSURE(peek)) {
551 /* detect misuse of closure operator */
552 if (IS_START(token)) {
553 FAIL("* or \\+ or \\? follows nothing");
554 } else if (IS_META(token) && token != M_ANY && !IS_CLASS(token)) {
555 FAIL("* or \\+ or \\? can only follow a normal character or . or []");
558 /* it is okay -- make it prefix instead of postfix */
559 ADD_META(build, peek);
561 /* take care of "needfirst" - is this the first char? */
562 if (needfirst && peek == M_PLUS && !IS_META(token)) {
567 /* we used "peek" -- need to refill it */
568 peek = gettoken(&text, re);
569 if (IS_CLOSURE(peek)) {
570 FAIL("* or \\+ or \\? doubled up");
572 } else if (!IS_META(token)) {
573 /* normal char is NOT argument of closure */
579 } 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) {
587 /* set the BOL flag instead of storing M_BEGLINE */
589 } else if (IS_META(token)) {
590 ADD_META(build, token);
596 /* end it with a \) which MUST MATCH the opening \( */
597 ADD_META(build, M_END(0));
599 FAIL("Not enough \\)s");
608 /* This function searches through a string for text that matches an RE. */
609 /* re -- the compiled regexp to search for */
610 /* str -- the string to search through */
611 /* bol -- does str start at the beginning of a line? (boolean) */
612 /* ignoreCase -- ignoreCase or not */
613 static int regexec(struct regexp *re, char *str, int bol, int ignoreCase)
615 char *prog; /* the entry point of re->program */
616 int len; /* length of the string */
619 /* if must start at the beginning of a line, and this isn't, then fail */
620 if (re->bol && bol == TRUE) {
625 prog = re->program + 1 + 32 * re->program[0];
627 /* search for the RE in the string */
629 /* must occur at BOL */
630 if ((re->first && match1(re, *(char *) str, re->first, ignoreCase)) /* wrong first letter? */
631 ||len < re->minlen /* not long enough? */
632 || match(re, (char *) str, prog, str, ignoreCase)) /* doesn't match? */
633 return FALSE; /* THEN FAIL! */
634 } else if (ignoreCase == FALSE) {
635 /* can occur anywhere in the line, noignorecase */
636 for (here = (char *) str; (re->first && re->first != *here)
637 || match(re, (char *) str, prog, here, ignoreCase);
639 if (len < re->minlen)
643 /* can occur anywhere in the line, ignorecase */
644 for (here = (char *) str;
645 (re->first && match1(re, *here, (int) re->first, ignoreCase))
646 || match(re, (char *) str, prog, here, ignoreCase);
648 if (len < re->minlen)
653 /* if we didn't fail, then we must have succeeded */
661 /* This performs substitutions after a regexp match has been found. */
662 static void regsub(regexp * re, char *src, char *dst)
673 while ((c = *src++) != '\0') {
674 /* recognize any meta characters */
678 } else if (c == '~') {
681 end = cpy + strlen(cpy);
682 } else if (c == '\\') {
695 /* \0 thru \9 mean "copy subexpression" */
697 cpy = re->startp[(int) c];
698 end = re->endp[(int) c];
704 /* \U and \L mean "convert to upper/lowercase" */
710 /* \E ends the \U or \L */
714 /* "\&" means "original text" */
719 /* "\~" means "previous text, if any" */
723 /* ordinary char preceded by backslash */
728 /* ordinary character, so just copy it */
733 /* Note: to reach this point in the code, we must have evaded
734 * all "continue" statements. To do that, we must have hit
735 * a metacharacter that involves copying.
738 /* if there is nothing to copy, loop */
742 /* copy over a portion of the original */
747 /* convert to uppercase */
748 if (isascii(*cpy) && islower(*cpy)) {
749 *dst++ = toupper(*cpy);
758 /* convert to lowercase */
759 if (isascii(*cpy) && isupper(*cpy)) {
760 *dst++ = tolower(*cpy);
768 /* copy without any conversion */
772 /* \u and \l end automatically after the first char */
773 if (mod && (mod == 'u' || mod == 'l')) {
780 /* remember what text we inserted this time */
783 previous1 = (char *) malloc((unsigned) (strlen(start) + 1));
785 strcpy(previous1, start);
789 #endif /* BB_REGEXP */