Index: stable/9/gnu/usr.bin/grep/dfa.c =================================================================== --- stable/9/gnu/usr.bin/grep/dfa.c (revision 250821) +++ stable/9/gnu/usr.bin/grep/dfa.c (revision 250822) @@ -1,3586 +1,3585 @@ /* dfa.c - deterministic extended regexp routines for GNU Copyright 1988, 1998, 2000 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ /* Written June, 1988 by Mike Haertel Modified July, 1988 by Arthur David Olson to assist BMG speedups */ /* $FreeBSD$ */ #ifdef HAVE_CONFIG_H #include #endif #include #include #include #include #ifdef STDC_HEADERS #include #else extern char *calloc(), *malloc(), *realloc(); extern void free(); #endif #if defined(HAVE_STRING_H) || defined(STDC_HEADERS) #include #else #include #endif #if HAVE_SETLOCALE # include #endif #if defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H && defined HAVE_MBRTOWC /* We can handle multibyte string. */ # define MBS_SUPPORT #endif #ifdef MBS_SUPPORT # include # include #endif #ifndef DEBUG /* use the same approach as regex.c */ #undef assert #define assert(e) #endif /* DEBUG */ #ifndef isgraph #define isgraph(C) (isprint(C) && !isspace(C)) #endif #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII)) #define ISALPHA(C) isalpha(C) #define ISUPPER(C) isupper(C) #define ISLOWER(C) islower(C) #define ISDIGIT(C) isdigit(C) #define ISXDIGIT(C) isxdigit(C) #define ISSPACE(C) isspace(C) #define ISPUNCT(C) ispunct(C) #define ISALNUM(C) isalnum(C) #define ISPRINT(C) isprint(C) #define ISGRAPH(C) isgraph(C) #define ISCNTRL(C) iscntrl(C) #else #define ISALPHA(C) (isascii(C) && isalpha(C)) #define ISUPPER(C) (isascii(C) && isupper(C)) #define ISLOWER(C) (isascii(C) && islower(C)) #define ISDIGIT(C) (isascii(C) && isdigit(C)) #define ISXDIGIT(C) (isascii(C) && isxdigit(C)) #define ISSPACE(C) (isascii(C) && isspace(C)) #define ISPUNCT(C) (isascii(C) && ispunct(C)) #define ISALNUM(C) (isascii(C) && isalnum(C)) #define ISPRINT(C) (isascii(C) && isprint(C)) #define ISGRAPH(C) (isascii(C) && isgraph(C)) #define ISCNTRL(C) (isascii(C) && iscntrl(C)) #endif /* ISASCIIDIGIT differs from ISDIGIT, as follows: - Its arg may be any int or unsigned int; it need not be an unsigned char. - It's guaranteed to evaluate its argument exactly once. - It's typically faster. Posix 1003.2-1992 section 2.5.2.1 page 50 lines 1556-1558 says that only '0' through '9' are digits. Prefer ISASCIIDIGIT to ISDIGIT unless it's important to use the locale's definition of `digit' even when the host does not conform to Posix. */ #define ISASCIIDIGIT(c) ((unsigned) (c) - '0' <= 9) /* If we (don't) have I18N. */ /* glibc defines _ */ #ifndef _ # ifdef HAVE_LIBINTL_H # include # ifndef _ # define _(Str) gettext (Str) # endif # else # define _(Str) (Str) # endif #endif #include "regex.h" #include "dfa.h" #include "hard-locale.h" /* HPUX, define those as macros in sys/param.h */ #ifdef setbit # undef setbit #endif #ifdef clrbit # undef clrbit #endif static void dfamust PARAMS ((struct dfa *dfa)); static void regexp PARAMS ((int toplevel)); static ptr_t xcalloc (size_t n, size_t s) { ptr_t r = calloc(n, s); if (!r) dfaerror(_("Memory exhausted")); return r; } static ptr_t xmalloc (size_t n) { ptr_t r = malloc(n); assert(n != 0); if (!r) dfaerror(_("Memory exhausted")); return r; } static ptr_t xrealloc (ptr_t p, size_t n) { ptr_t r = realloc(p, n); assert(n != 0); if (!r) dfaerror(_("Memory exhausted")); return r; } #define CALLOC(p, t, n) ((p) = (t *) xcalloc((size_t)(n), sizeof (t))) #define MALLOC(p, t, n) ((p) = (t *) xmalloc((n) * sizeof (t))) #define REALLOC(p, t, n) ((p) = (t *) xrealloc((ptr_t) (p), (n) * sizeof (t))) /* Reallocate an array of type t if nalloc is too small for index. */ #define REALLOC_IF_NECESSARY(p, t, nalloc, index) \ if ((index) >= (nalloc)) \ { \ do \ (nalloc) *= 2; \ while ((index) >= (nalloc)); \ REALLOC(p, t, nalloc); \ } #ifdef DEBUG static void prtok (token t) { char const *s; if (t < 0) fprintf(stderr, "END"); else if (t < NOTCHAR) fprintf(stderr, "%c", t); else { switch (t) { case EMPTY: s = "EMPTY"; break; case BACKREF: s = "BACKREF"; break; case BEGLINE: s = "BEGLINE"; break; case ENDLINE: s = "ENDLINE"; break; case BEGWORD: s = "BEGWORD"; break; case ENDWORD: s = "ENDWORD"; break; case LIMWORD: s = "LIMWORD"; break; case NOTLIMWORD: s = "NOTLIMWORD"; break; case QMARK: s = "QMARK"; break; case STAR: s = "STAR"; break; case PLUS: s = "PLUS"; break; case CAT: s = "CAT"; break; case OR: s = "OR"; break; case ORTOP: s = "ORTOP"; break; case LPAREN: s = "LPAREN"; break; case RPAREN: s = "RPAREN"; break; case CRANGE: s = "CRANGE"; break; #ifdef MBS_SUPPORT case ANYCHAR: s = "ANYCHAR"; break; case MBCSET: s = "MBCSET"; break; #endif /* MBS_SUPPORT */ default: s = "CSET"; break; } fprintf(stderr, "%s", s); } } #endif /* DEBUG */ /* Stuff pertaining to charclasses. */ static int tstbit (unsigned b, charclass c) { return c[b / INTBITS] & 1 << b % INTBITS; } static void setbit (unsigned b, charclass c) { c[b / INTBITS] |= 1 << b % INTBITS; } static void clrbit (unsigned b, charclass c) { c[b / INTBITS] &= ~(1 << b % INTBITS); } static void copyset (charclass src, charclass dst) { memcpy (dst, src, sizeof (charclass)); } static void zeroset (charclass s) { memset (s, 0, sizeof (charclass)); } static void notset (charclass s) { int i; for (i = 0; i < CHARCLASS_INTS; ++i) s[i] = ~s[i]; } static int equal (charclass s1, charclass s2) { return memcmp (s1, s2, sizeof (charclass)) == 0; } /* A pointer to the current dfa is kept here during parsing. */ static struct dfa *dfa; /* Find the index of charclass s in dfa->charclasses, or allocate a new charclass. */ static int charclass_index (charclass s) { int i; for (i = 0; i < dfa->cindex; ++i) if (equal(s, dfa->charclasses[i])) return i; REALLOC_IF_NECESSARY(dfa->charclasses, charclass, dfa->calloc, dfa->cindex); ++dfa->cindex; copyset(s, dfa->charclasses[i]); return i; } /* Syntax bits controlling the behavior of the lexical analyzer. */ static reg_syntax_t syntax_bits, syntax_bits_set; /* Flag for case-folding letters into sets. */ static int case_fold; /* End-of-line byte in data. */ static unsigned char eolbyte; /* Entry point to set syntax options. */ void dfasyntax (reg_syntax_t bits, int fold, unsigned char eol) { syntax_bits_set = 1; syntax_bits = bits; case_fold = fold; eolbyte = eol; } /* Like setbit, but if case is folded, set both cases of a letter. */ static void setbit_case_fold (unsigned b, charclass c) { setbit (b, c); if (case_fold) { if (ISUPPER (b)) setbit (tolower (b), c); else if (ISLOWER (b)) setbit (toupper (b), c); } } /* Lexical analyzer. All the dross that deals with the obnoxious GNU Regex syntax bits is located here. The poor, suffering reader is referred to the GNU Regex documentation for the meaning of the @#%!@#%^!@ syntax bits. */ static char const *lexstart; /* Pointer to beginning of input string. */ static char const *lexptr; /* Pointer to next input character. */ static int lexleft; /* Number of characters remaining. */ static token lasttok; /* Previous token returned; initially END. */ static int laststart; /* True if we're separated from beginning or (, | only by zero-width characters. */ static int parens; /* Count of outstanding left parens. */ static int minrep, maxrep; /* Repeat counts for {m,n}. */ static int hard_LC_COLLATE; /* Nonzero if LC_COLLATE is hard. */ #ifdef MBS_SUPPORT /* These variables are used only if (MB_CUR_MAX > 1). */ static mbstate_t mbs; /* Mbstate for mbrlen(). */ -static ssize_t cur_mb_len; /* Byte length of the current scanning - multibyte character. Must also handle - negative result from mbrlen(). */ -static ssize_t cur_mb_index; /* Byte index of the current scanning multibyte +static int cur_mb_len; /* Byte length of the current scanning + multibyte character. */ +static int cur_mb_index; /* Byte index of the current scanning multibyte character. singlebyte character : cur_mb_index = 0 multibyte character 1st byte : cur_mb_index = 1 2nd byte : cur_mb_index = 2 ... nth byte : cur_mb_index = n */ static unsigned char *mblen_buf;/* Correspond to the input buffer in dfaexec(). Each element store the amount of remain byte of corresponding multibyte character in the input string. A element's value is 0 if corresponding character is a singlebyte chracter. e.g. input : 'a', , , mblen_buf : 0, 3, 2, 1 */ static wchar_t *inputwcs; /* Wide character representation of input string in dfaexec(). The length of this array is same as the length of input string(char array). inputstring[i] is a single-byte char, or 1st byte of a multibyte char. And inputwcs[i] is the codepoint. */ static unsigned char const *buf_begin;/* refference to begin in dfaexec(). */ static unsigned char const *buf_end; /* refference to end in dfaexec(). */ #endif /* MBS_SUPPORT */ #ifdef MBS_SUPPORT /* This function update cur_mb_len, and cur_mb_index. p points current lexptr, len is the remaining buffer length. */ static void -update_mb_len_index (unsigned char const *p, size_t len) +update_mb_len_index (unsigned char const *p, int len) { /* If last character is a part of a multibyte character, we update cur_mb_index. */ if (cur_mb_index) cur_mb_index = (cur_mb_index >= cur_mb_len)? 0 : cur_mb_index + 1; /* If last character is a single byte character, or the last portion of a multibyte character, we check whether next character is a multibyte character or not. */ if (! cur_mb_index) { cur_mb_len = mbrlen(p, len, &mbs); if (cur_mb_len > 1) /* It is a multibyte character. cur_mb_len was already set by mbrlen(). */ cur_mb_index = 1; else if (cur_mb_len < 1) /* Invalid sequence. We treat it as a singlebyte character. cur_mb_index is aleady 0. */ cur_mb_len = 1; /* Otherwise, cur_mb_len == 1, it is a singlebyte character. cur_mb_index is aleady 0. */ } } #endif /* MBS_SUPPORT */ #ifdef MBS_SUPPORT /* Note that characters become unsigned here. */ # define FETCH(c, eoferr) \ { \ if (! lexleft) \ { \ if (eoferr != 0) \ dfaerror (eoferr); \ else \ return lasttok = END; \ } \ if (MB_CUR_MAX > 1) \ update_mb_len_index(lexptr, lexleft); \ (c) = (unsigned char) *lexptr++; \ --lexleft; \ } /* This function fetch a wide character, and update cur_mb_len, used only if the current locale is a multibyte environment. */ static wint_t fetch_wc (char const *eoferr) { wchar_t wc; if (! lexleft) { if (eoferr != 0) dfaerror (eoferr); else return WEOF; } cur_mb_len = mbrtowc(&wc, lexptr, lexleft, &mbs); if (cur_mb_len <= 0) { cur_mb_len = 1; wc = *lexptr; } lexptr += cur_mb_len; lexleft -= cur_mb_len; return wc; } #else /* Note that characters become unsigned here. */ # define FETCH(c, eoferr) \ { \ if (! lexleft) \ { \ if (eoferr != 0) \ dfaerror (eoferr); \ else \ return lasttok = END; \ } \ (c) = (unsigned char) *lexptr++; \ --lexleft; \ } #endif /* MBS_SUPPORT */ #ifdef MBS_SUPPORT /* Multibyte character handling sub-routin for lex. This function parse a bracket expression and build a struct mb_char_classes. */ static void parse_bracket_exp_mb () { wint_t wc, wc1, wc2; /* Work area to build a mb_char_classes. */ struct mb_char_classes *work_mbc; int chars_al, range_sts_al, range_ends_al, ch_classes_al, equivs_al, coll_elems_al; REALLOC_IF_NECESSARY(dfa->mbcsets, struct mb_char_classes, dfa->mbcsets_alloc, dfa->nmbcsets + 1); /* dfa->multibyte_prop[] hold the index of dfa->mbcsets. We will update dfa->multibyte_prop in addtok(), because we can't decide the index in dfa->tokens[]. */ /* Initialize work are */ work_mbc = &(dfa->mbcsets[dfa->nmbcsets++]); chars_al = 1; range_sts_al = range_ends_al = 0; ch_classes_al = equivs_al = coll_elems_al = 0; MALLOC(work_mbc->chars, wchar_t, chars_al); work_mbc->nchars = work_mbc->nranges = work_mbc->nch_classes = 0; work_mbc->nequivs = work_mbc->ncoll_elems = 0; work_mbc->chars = work_mbc->ch_classes = NULL; work_mbc->range_sts = work_mbc->range_ends = NULL; work_mbc->equivs = work_mbc->coll_elems = NULL; wc = fetch_wc(_("Unbalanced [")); if (wc == L'^') { wc = fetch_wc(_("Unbalanced [")); work_mbc->invert = 1; } else work_mbc->invert = 0; do { wc1 = WEOF; /* mark wc1 is not initialized". */ /* Note that if we're looking at some other [:...:] construct, we just treat it as a bunch of ordinary characters. We can do this because we assume regex has checked for syntax errors before dfa is ever called. */ if (wc == L'[' && (syntax_bits & RE_CHAR_CLASSES)) { #define BRACKET_BUFFER_SIZE 128 char str[BRACKET_BUFFER_SIZE]; wc1 = wc; wc = fetch_wc(_("Unbalanced [")); /* If pattern contains `[[:', `[[.', or `[[='. */ if (cur_mb_len == 1 && (wc == L':' || wc == L'.' || wc == L'=')) { unsigned char c; unsigned char delim = (unsigned char)wc; int len = 0; for (;;) { if (! lexleft) dfaerror (_("Unbalanced [")); c = (unsigned char) *lexptr++; --lexleft; if ((c == delim && *lexptr == ']') || lexleft == 0) break; if (len < BRACKET_BUFFER_SIZE) str[len++] = c; else /* This is in any case an invalid class name. */ str[0] = '\0'; } str[len] = '\0'; if (lexleft == 0) { REALLOC_IF_NECESSARY(work_mbc->chars, wchar_t, chars_al, work_mbc->nchars + 2); work_mbc->chars[work_mbc->nchars++] = L'['; work_mbc->chars[work_mbc->nchars++] = delim; break; } if (--lexleft, *lexptr++ != ']') dfaerror (_("Unbalanced [")); if (delim == ':') /* build character class. */ { wctype_t wt; /* Query the character class as wctype_t. */ wt = wctype (str); if (ch_classes_al == 0) MALLOC(work_mbc->ch_classes, wchar_t, ++ch_classes_al); REALLOC_IF_NECESSARY(work_mbc->ch_classes, wctype_t, ch_classes_al, work_mbc->nch_classes + 1); work_mbc->ch_classes[work_mbc->nch_classes++] = wt; } else if (delim == '=' || delim == '.') { char *elem; MALLOC(elem, char, len + 1); strncpy(elem, str, len + 1); if (delim == '=') /* build equivalent class. */ { if (equivs_al == 0) MALLOC(work_mbc->equivs, char*, ++equivs_al); REALLOC_IF_NECESSARY(work_mbc->equivs, char*, equivs_al, work_mbc->nequivs + 1); work_mbc->equivs[work_mbc->nequivs++] = elem; } if (delim == '.') /* build collating element. */ { if (coll_elems_al == 0) MALLOC(work_mbc->coll_elems, char*, ++coll_elems_al); REALLOC_IF_NECESSARY(work_mbc->coll_elems, char*, coll_elems_al, work_mbc->ncoll_elems + 1); work_mbc->coll_elems[work_mbc->ncoll_elems++] = elem; } } wc1 = wc = WEOF; } else /* We treat '[' as a normal character here. */ { wc2 = wc1; wc1 = wc; wc = wc2; /* swap */ } } else { if (wc == L'\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) wc = fetch_wc(("Unbalanced [")); } if (wc1 == WEOF) wc1 = fetch_wc(_("Unbalanced [")); if (wc1 == L'-') /* build range characters. */ { wc2 = fetch_wc(_("Unbalanced [")); if (wc2 == L']') { /* In the case [x-], the - is an ordinary hyphen, which is left in c1, the lookahead character. */ lexptr -= cur_mb_len; lexleft += cur_mb_len; wc2 = wc; } else { if (wc2 == L'\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) wc2 = fetch_wc(_("Unbalanced [")); wc1 = fetch_wc(_("Unbalanced [")); } if (range_sts_al == 0) { MALLOC(work_mbc->range_sts, wchar_t, ++range_sts_al); MALLOC(work_mbc->range_ends, wchar_t, ++range_ends_al); } REALLOC_IF_NECESSARY(work_mbc->range_sts, wchar_t, range_sts_al, work_mbc->nranges + 1); work_mbc->range_sts[work_mbc->nranges] = (wchar_t)wc; REALLOC_IF_NECESSARY(work_mbc->range_ends, wchar_t, range_ends_al, work_mbc->nranges + 1); work_mbc->range_ends[work_mbc->nranges++] = (wchar_t)wc2; } else if (wc != WEOF) /* build normal characters. */ { REALLOC_IF_NECESSARY(work_mbc->chars, wchar_t, chars_al, work_mbc->nchars + 1); work_mbc->chars[work_mbc->nchars++] = (wchar_t)wc; } } while ((wc = wc1) != L']'); } #endif /* MBS_SUPPORT */ #ifdef __STDC__ #define FUNC(F, P) static int F(int c) { return P(c); } #else #define FUNC(F, P) static int F(c) int c; { return P(c); } #endif FUNC(is_alpha, ISALPHA) FUNC(is_upper, ISUPPER) FUNC(is_lower, ISLOWER) FUNC(is_digit, ISDIGIT) FUNC(is_xdigit, ISXDIGIT) FUNC(is_space, ISSPACE) FUNC(is_punct, ISPUNCT) FUNC(is_alnum, ISALNUM) FUNC(is_print, ISPRINT) FUNC(is_graph, ISGRAPH) FUNC(is_cntrl, ISCNTRL) static int is_blank (int c) { return (c == ' ' || c == '\t'); } /* The following list maps the names of the Posix named character classes to predicate functions that determine whether a given character is in the class. The leading [ has already been eaten by the lexical analyzer. */ static struct { const char *name; int (*pred) PARAMS ((int)); } const prednames[] = { { ":alpha:]", is_alpha }, { ":upper:]", is_upper }, { ":lower:]", is_lower }, { ":digit:]", is_digit }, { ":xdigit:]", is_xdigit }, { ":space:]", is_space }, { ":punct:]", is_punct }, { ":alnum:]", is_alnum }, { ":print:]", is_print }, { ":graph:]", is_graph }, { ":cntrl:]", is_cntrl }, { ":blank:]", is_blank }, { 0 } }; /* Return non-zero if C is a `word-constituent' byte; zero otherwise. */ #define IS_WORD_CONSTITUENT(C) (ISALNUM(C) || (C) == '_') static int looking_at (char const *s) { size_t len; len = strlen(s); if (lexleft < len) return 0; return strncmp(s, lexptr, len) == 0; } static token lex (void) { unsigned c, c1, c2; int backslash = 0, invert; charclass ccl; int i; /* Basic plan: We fetch a character. If it's a backslash, we set the backslash flag and go through the loop again. On the plus side, this avoids having a duplicate of the main switch inside the backslash case. On the minus side, it means that just about every case begins with "if (backslash) ...". */ for (i = 0; i < 2; ++i) { FETCH(c, 0); #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1 && cur_mb_index) /* If this is a part of a multi-byte character, we must treat this byte data as a normal character. e.g. In case of SJIS encoding, some character contains '\', but they must not be backslash. */ goto normal_char; #endif /* MBS_SUPPORT */ switch (c) { case '\\': if (backslash) goto normal_char; if (lexleft == 0) dfaerror(_("Unfinished \\ escape")); backslash = 1; break; case '^': if (backslash) goto normal_char; if (syntax_bits & RE_CONTEXT_INDEP_ANCHORS || lasttok == END || lasttok == LPAREN || lasttok == OR) return lasttok = BEGLINE; goto normal_char; case '$': if (backslash) goto normal_char; if (syntax_bits & RE_CONTEXT_INDEP_ANCHORS || lexleft == 0 || (syntax_bits & RE_NO_BK_PARENS ? lexleft > 0 && *lexptr == ')' : lexleft > 1 && lexptr[0] == '\\' && lexptr[1] == ')') || (syntax_bits & RE_NO_BK_VBAR ? lexleft > 0 && *lexptr == '|' : lexleft > 1 && lexptr[0] == '\\' && lexptr[1] == '|') || ((syntax_bits & RE_NEWLINE_ALT) && lexleft > 0 && *lexptr == '\n')) return lasttok = ENDLINE; goto normal_char; case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if (backslash && !(syntax_bits & RE_NO_BK_REFS)) { laststart = 0; return lasttok = BACKREF; } goto normal_char; case '`': if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) return lasttok = BEGLINE; /* FIXME: should be beginning of string */ goto normal_char; case '\'': if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) return lasttok = ENDLINE; /* FIXME: should be end of string */ goto normal_char; case '<': if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) return lasttok = BEGWORD; goto normal_char; case '>': if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) return lasttok = ENDWORD; goto normal_char; case 'b': if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) return lasttok = LIMWORD; goto normal_char; case 'B': if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) return lasttok = NOTLIMWORD; goto normal_char; case '?': if (syntax_bits & RE_LIMITED_OPS) goto normal_char; if (backslash != ((syntax_bits & RE_BK_PLUS_QM) != 0)) goto normal_char; if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) goto normal_char; return lasttok = QMARK; case '*': if (backslash) goto normal_char; if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) goto normal_char; return lasttok = STAR; case '+': if (syntax_bits & RE_LIMITED_OPS) goto normal_char; if (backslash != ((syntax_bits & RE_BK_PLUS_QM) != 0)) goto normal_char; if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) goto normal_char; return lasttok = PLUS; case '{': if (!(syntax_bits & RE_INTERVALS)) goto normal_char; if (backslash != ((syntax_bits & RE_NO_BK_BRACES) == 0)) goto normal_char; if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) goto normal_char; if (syntax_bits & RE_NO_BK_BRACES) { /* Scan ahead for a valid interval; if it's not valid, treat it as a literal '{'. */ int lo = -1, hi = -1; char const *p = lexptr; char const *lim = p + lexleft; for (; p != lim && ISASCIIDIGIT (*p); p++) lo = (lo < 0 ? 0 : lo * 10) + *p - '0'; if (p != lim && *p == ',') while (++p != lim && ISASCIIDIGIT (*p)) hi = (hi < 0 ? 0 : hi * 10) + *p - '0'; else hi = lo; if (p == lim || *p != '}' || lo < 0 || RE_DUP_MAX < hi || (0 <= hi && hi < lo)) goto normal_char; } minrep = 0; /* Cases: {M} - exact count {M,} - minimum count, maximum is infinity {M,N} - M through N */ FETCH(c, _("unfinished repeat count")); if (ISASCIIDIGIT (c)) { minrep = c - '0'; for (;;) { FETCH(c, _("unfinished repeat count")); if (! ISASCIIDIGIT (c)) break; minrep = 10 * minrep + c - '0'; } } else dfaerror(_("malformed repeat count")); if (c == ',') { FETCH (c, _("unfinished repeat count")); if (! ISASCIIDIGIT (c)) maxrep = -1; else { maxrep = c - '0'; for (;;) { FETCH (c, _("unfinished repeat count")); if (! ISASCIIDIGIT (c)) break; maxrep = 10 * maxrep + c - '0'; } if (0 <= maxrep && maxrep < minrep) dfaerror (_("malformed repeat count")); } } else maxrep = minrep; if (!(syntax_bits & RE_NO_BK_BRACES)) { if (c != '\\') dfaerror(_("malformed repeat count")); FETCH(c, _("unfinished repeat count")); } if (c != '}') dfaerror(_("malformed repeat count")); laststart = 0; return lasttok = REPMN; case '|': if (syntax_bits & RE_LIMITED_OPS) goto normal_char; if (backslash != ((syntax_bits & RE_NO_BK_VBAR) == 0)) goto normal_char; laststart = 1; return lasttok = OR; case '\n': if (syntax_bits & RE_LIMITED_OPS || backslash || !(syntax_bits & RE_NEWLINE_ALT)) goto normal_char; laststart = 1; return lasttok = OR; case '(': if (backslash != ((syntax_bits & RE_NO_BK_PARENS) == 0)) goto normal_char; ++parens; laststart = 1; return lasttok = LPAREN; case ')': if (backslash != ((syntax_bits & RE_NO_BK_PARENS) == 0)) goto normal_char; if (parens == 0 && syntax_bits & RE_UNMATCHED_RIGHT_PAREN_ORD) goto normal_char; --parens; laststart = 0; return lasttok = RPAREN; case '.': if (backslash) goto normal_char; #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { /* In multibyte environment period must match with a single character not a byte. So we use ANYCHAR. */ laststart = 0; return lasttok = ANYCHAR; } #endif /* MBS_SUPPORT */ zeroset(ccl); notset(ccl); if (!(syntax_bits & RE_DOT_NEWLINE)) clrbit(eolbyte, ccl); if (syntax_bits & RE_DOT_NOT_NULL) clrbit('\0', ccl); laststart = 0; return lasttok = CSET + charclass_index(ccl); case 'w': case 'W': if (!backslash || (syntax_bits & RE_NO_GNU_OPS)) goto normal_char; zeroset(ccl); for (c2 = 0; c2 < NOTCHAR; ++c2) if (IS_WORD_CONSTITUENT(c2)) setbit(c2, ccl); if (c == 'W') notset(ccl); laststart = 0; return lasttok = CSET + charclass_index(ccl); case '[': if (backslash) goto normal_char; laststart = 0; #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { /* In multibyte environment a bracket expression may contain multibyte characters, which must be treated as characters (not bytes). So we parse it by parse_bracket_exp_mb(). */ parse_bracket_exp_mb(); return lasttok = MBCSET; } #endif zeroset(ccl); FETCH(c, _("Unbalanced [")); if (c == '^') { FETCH(c, _("Unbalanced [")); invert = 1; } else invert = 0; do { /* Nobody ever said this had to be fast. :-) Note that if we're looking at some other [:...:] construct, we just treat it as a bunch of ordinary characters. We can do this because we assume regex has checked for syntax errors before dfa is ever called. */ if (c == '[' && (syntax_bits & RE_CHAR_CLASSES)) for (c1 = 0; prednames[c1].name; ++c1) if (looking_at(prednames[c1].name)) { int (*pred) PARAMS ((int)) = prednames[c1].pred; for (c2 = 0; c2 < NOTCHAR; ++c2) if ((*pred)(c2)) setbit_case_fold (c2, ccl); lexptr += strlen(prednames[c1].name); lexleft -= strlen(prednames[c1].name); FETCH(c1, _("Unbalanced [")); goto skip; } if (c == '\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) FETCH(c, _("Unbalanced [")); FETCH(c1, _("Unbalanced [")); if (c1 == '-') { FETCH(c2, _("Unbalanced [")); if (c2 == ']') { /* In the case [x-], the - is an ordinary hyphen, which is left in c1, the lookahead character. */ --lexptr; ++lexleft; } else { if (c2 == '\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) FETCH(c2, _("Unbalanced [")); FETCH(c1, _("Unbalanced [")); if (!hard_LC_COLLATE) { for (; c <= c2; c++) setbit_case_fold (c, ccl); } else { /* POSIX locales are painful - leave the decision to libc */ char expr[6] = { '[', c, '-', c2, ']', '\0' }; regex_t re; if (regcomp (&re, expr, case_fold ? REG_ICASE : 0) == REG_NOERROR) { for (c = 0; c < NOTCHAR; ++c) { char buf[2] = { c, '\0' }; regmatch_t mat; if (regexec (&re, buf, 1, &mat, 0) == REG_NOERROR && mat.rm_so == 0 && mat.rm_eo == 1) setbit_case_fold (c, ccl); } regfree (&re); } } continue; } } setbit_case_fold (c, ccl); skip: ; } while ((c = c1) != ']'); if (invert) { notset(ccl); if (syntax_bits & RE_HAT_LISTS_NOT_NEWLINE) clrbit(eolbyte, ccl); } return lasttok = CSET + charclass_index(ccl); default: normal_char: laststart = 0; if (case_fold && ISALPHA(c)) { zeroset(ccl); setbit_case_fold (c, ccl); return lasttok = CSET + charclass_index(ccl); } return c; } } /* The above loop should consume at most a backslash and some other character. */ abort(); return END; /* keeps pedantic compilers happy. */ } /* Recursive descent parser for regular expressions. */ static token tok; /* Lookahead token. */ static int depth; /* Current depth of a hypothetical stack holding deferred productions. This is used to determine the depth that will be required of the real stack later on in dfaanalyze(). */ /* Add the given token to the parse tree, maintaining the depth count and updating the maximum depth if necessary. */ static void addtok (token t) { #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { REALLOC_IF_NECESSARY(dfa->multibyte_prop, int, dfa->nmultibyte_prop, dfa->tindex); /* Set dfa->multibyte_prop. See struct dfa in dfa.h. */ if (t == MBCSET) dfa->multibyte_prop[dfa->tindex] = ((dfa->nmbcsets - 1) << 2) + 3; else if (t < NOTCHAR) dfa->multibyte_prop[dfa->tindex] = (cur_mb_len == 1)? 3 /* single-byte char */ : (((cur_mb_index == 1)? 1 : 0) /* 1st-byte of multibyte char */ + ((cur_mb_index == cur_mb_len)? 2 : 0)); /* last-byte */ else /* It may be unnecesssary, but it is safer to treat other symbols as singlebyte characters. */ dfa->multibyte_prop[dfa->tindex] = 3; } #endif REALLOC_IF_NECESSARY(dfa->tokens, token, dfa->talloc, dfa->tindex); dfa->tokens[dfa->tindex++] = t; switch (t) { case QMARK: case STAR: case PLUS: break; case CAT: case OR: case ORTOP: --depth; break; default: ++dfa->nleaves; case EMPTY: ++depth; break; } if (depth > dfa->depth) dfa->depth = depth; } /* The grammar understood by the parser is as follows. regexp: regexp OR branch branch branch: branch closure closure closure: closure QMARK closure STAR closure PLUS closure REPMN atom atom: ANYCHAR MBCSET CSET BACKREF BEGLINE ENDLINE BEGWORD ENDWORD LIMWORD NOTLIMWORD CRANGE LPAREN regexp RPAREN The parser builds a parse tree in postfix form in an array of tokens. */ static void atom (void) { if ((tok >= 0 && tok < NOTCHAR) || tok >= CSET || tok == BACKREF || tok == BEGLINE || tok == ENDLINE || tok == BEGWORD #ifdef MBS_SUPPORT || tok == ANYCHAR || tok == MBCSET /* MB_CUR_MAX > 1 */ #endif /* MBS_SUPPORT */ || tok == ENDWORD || tok == LIMWORD || tok == NOTLIMWORD) { addtok(tok); tok = lex(); #ifdef MBS_SUPPORT /* We treat a multibyte character as a single atom, so that DFA can treat a multibyte character as a single expression. e.g. We construct following tree from "". */ if (MB_CUR_MAX > 1) { while (cur_mb_index > 1 && tok >= 0 && tok < NOTCHAR) { addtok(tok); addtok(CAT); tok = lex(); } } #endif /* MBS_SUPPORT */ } else if (tok == CRANGE) { /* A character range like "[a-z]" in a locale other than "C" or "POSIX". This range might any sequence of one or more characters. Unfortunately the POSIX locale primitives give us no practical way to find what character sequences might be matched. Treat this approximately like "(.\1)" -- i.e. match one character, and then punt to the full matcher. */ charclass ccl; zeroset (ccl); notset (ccl); addtok (CSET + charclass_index (ccl)); addtok (BACKREF); addtok (CAT); tok = lex (); } else if (tok == LPAREN) { tok = lex(); regexp(0); if (tok != RPAREN) dfaerror(_("Unbalanced (")); tok = lex(); } else addtok(EMPTY); } /* Return the number of tokens in the given subexpression. */ static int nsubtoks (int tindex) { int ntoks1; switch (dfa->tokens[tindex - 1]) { default: return 1; case QMARK: case STAR: case PLUS: return 1 + nsubtoks(tindex - 1); case CAT: case OR: case ORTOP: ntoks1 = nsubtoks(tindex - 1); return 1 + ntoks1 + nsubtoks(tindex - 1 - ntoks1); } } /* Copy the given subexpression to the top of the tree. */ static void copytoks (int tindex, int ntokens) { int i; for (i = 0; i < ntokens; ++i) addtok(dfa->tokens[tindex + i]); } static void closure (void) { int tindex, ntokens, i; atom(); while (tok == QMARK || tok == STAR || tok == PLUS || tok == REPMN) if (tok == REPMN) { ntokens = nsubtoks(dfa->tindex); tindex = dfa->tindex - ntokens; if (maxrep < 0) addtok(PLUS); if (minrep == 0) addtok(QMARK); for (i = 1; i < minrep; ++i) { copytoks(tindex, ntokens); addtok(CAT); } for (; i < maxrep; ++i) { copytoks(tindex, ntokens); addtok(QMARK); addtok(CAT); } tok = lex(); } else { addtok(tok); tok = lex(); } } static void branch (void) { closure(); while (tok != RPAREN && tok != OR && tok >= 0) { closure(); addtok(CAT); } } static void regexp (int toplevel) { branch(); while (tok == OR) { tok = lex(); branch(); if (toplevel) addtok(ORTOP); else addtok(OR); } } /* Main entry point for the parser. S is a string to be parsed, len is the length of the string, so s can include NUL characters. D is a pointer to the struct dfa to parse into. */ void dfaparse (char const *s, size_t len, struct dfa *d) { dfa = d; lexstart = lexptr = s; lexleft = len; lasttok = END; laststart = 1; parens = 0; hard_LC_COLLATE = hard_locale (LC_COLLATE); #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { cur_mb_index = 0; cur_mb_len = 0; memset(&mbs, 0, sizeof(mbstate_t)); } #endif /* MBS_SUPPORT */ if (! syntax_bits_set) dfaerror(_("No syntax specified")); tok = lex(); depth = d->depth; regexp(1); if (tok != END) dfaerror(_("Unbalanced )")); addtok(END - d->nregexps); addtok(CAT); if (d->nregexps) addtok(ORTOP); ++d->nregexps; } /* Some primitives for operating on sets of positions. */ /* Copy one set to another; the destination must be large enough. */ static void copy (position_set const *src, position_set *dst) { int i; for (i = 0; i < src->nelem; ++i) dst->elems[i] = src->elems[i]; dst->nelem = src->nelem; } /* Insert a position in a set. Position sets are maintained in sorted order according to index. If position already exists in the set with the same index then their constraints are logically or'd together. S->elems must point to an array large enough to hold the resulting set. */ static void insert (position p, position_set *s) { int i; position t1, t2; for (i = 0; i < s->nelem && p.index < s->elems[i].index; ++i) continue; if (i < s->nelem && p.index == s->elems[i].index) s->elems[i].constraint |= p.constraint; else { t1 = p; ++s->nelem; while (i < s->nelem) { t2 = s->elems[i]; s->elems[i++] = t1; t1 = t2; } } } /* Merge two sets of positions into a third. The result is exactly as if the positions of both sets were inserted into an initially empty set. */ static void merge (position_set const *s1, position_set const *s2, position_set *m) { int i = 0, j = 0; m->nelem = 0; while (i < s1->nelem && j < s2->nelem) if (s1->elems[i].index > s2->elems[j].index) m->elems[m->nelem++] = s1->elems[i++]; else if (s1->elems[i].index < s2->elems[j].index) m->elems[m->nelem++] = s2->elems[j++]; else { m->elems[m->nelem] = s1->elems[i++]; m->elems[m->nelem++].constraint |= s2->elems[j++].constraint; } while (i < s1->nelem) m->elems[m->nelem++] = s1->elems[i++]; while (j < s2->nelem) m->elems[m->nelem++] = s2->elems[j++]; } /* Delete a position from a set. */ static void delete (position p, position_set *s) { int i; for (i = 0; i < s->nelem; ++i) if (p.index == s->elems[i].index) break; if (i < s->nelem) for (--s->nelem; i < s->nelem; ++i) s->elems[i] = s->elems[i + 1]; } /* Find the index of the state corresponding to the given position set with the given preceding context, or create a new state if there is no such state. Newline and letter tell whether we got here on a newline or letter, respectively. */ static int state_index (struct dfa *d, position_set const *s, int newline, int letter) { int hash = 0; int constraint; int i, j; newline = newline ? 1 : 0; letter = letter ? 1 : 0; for (i = 0; i < s->nelem; ++i) hash ^= s->elems[i].index + s->elems[i].constraint; /* Try to find a state that exactly matches the proposed one. */ for (i = 0; i < d->sindex; ++i) { if (hash != d->states[i].hash || s->nelem != d->states[i].elems.nelem || newline != d->states[i].newline || letter != d->states[i].letter) continue; for (j = 0; j < s->nelem; ++j) if (s->elems[j].constraint != d->states[i].elems.elems[j].constraint || s->elems[j].index != d->states[i].elems.elems[j].index) break; if (j == s->nelem) return i; } /* We'll have to create a new state. */ REALLOC_IF_NECESSARY(d->states, dfa_state, d->salloc, d->sindex); d->states[i].hash = hash; MALLOC(d->states[i].elems.elems, position, s->nelem); copy(s, &d->states[i].elems); d->states[i].newline = newline; d->states[i].letter = letter; d->states[i].backref = 0; d->states[i].constraint = 0; d->states[i].first_end = 0; #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) d->states[i].mbps.nelem = 0; #endif for (j = 0; j < s->nelem; ++j) if (d->tokens[s->elems[j].index] < 0) { constraint = s->elems[j].constraint; if (SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 0) || SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 1) || SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 0) || SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 1)) d->states[i].constraint |= constraint; if (! d->states[i].first_end) d->states[i].first_end = d->tokens[s->elems[j].index]; } else if (d->tokens[s->elems[j].index] == BACKREF) { d->states[i].constraint = NO_CONSTRAINT; d->states[i].backref = 1; } ++d->sindex; return i; } /* Find the epsilon closure of a set of positions. If any position of the set contains a symbol that matches the empty string in some context, replace that position with the elements of its follow labeled with an appropriate constraint. Repeat exhaustively until no funny positions are left. S->elems must be large enough to hold the result. */ static void epsclosure (position_set *s, struct dfa const *d) { int i, j; int *visited; position p, old; MALLOC(visited, int, d->tindex); for (i = 0; i < d->tindex; ++i) visited[i] = 0; for (i = 0; i < s->nelem; ++i) if (d->tokens[s->elems[i].index] >= NOTCHAR && d->tokens[s->elems[i].index] != BACKREF #ifdef MBS_SUPPORT && d->tokens[s->elems[i].index] != ANYCHAR && d->tokens[s->elems[i].index] != MBCSET #endif && d->tokens[s->elems[i].index] < CSET) { old = s->elems[i]; p.constraint = old.constraint; delete(s->elems[i], s); if (visited[old.index]) { --i; continue; } visited[old.index] = 1; switch (d->tokens[old.index]) { case BEGLINE: p.constraint &= BEGLINE_CONSTRAINT; break; case ENDLINE: p.constraint &= ENDLINE_CONSTRAINT; break; case BEGWORD: p.constraint &= BEGWORD_CONSTRAINT; break; case ENDWORD: p.constraint &= ENDWORD_CONSTRAINT; break; case LIMWORD: p.constraint &= LIMWORD_CONSTRAINT; break; case NOTLIMWORD: p.constraint &= NOTLIMWORD_CONSTRAINT; break; default: break; } for (j = 0; j < d->follows[old.index].nelem; ++j) { p.index = d->follows[old.index].elems[j].index; insert(p, s); } /* Force rescan to start at the beginning. */ i = -1; } free(visited); } /* Perform bottom-up analysis on the parse tree, computing various functions. Note that at this point, we're pretending constructs like \< are real characters rather than constraints on what can follow them. Nullable: A node is nullable if it is at the root of a regexp that can match the empty string. * EMPTY leaves are nullable. * No other leaf is nullable. * A QMARK or STAR node is nullable. * A PLUS node is nullable if its argument is nullable. * A CAT node is nullable if both its arguments are nullable. * An OR node is nullable if either argument is nullable. Firstpos: The firstpos of a node is the set of positions (nonempty leaves) that could correspond to the first character of a string matching the regexp rooted at the given node. * EMPTY leaves have empty firstpos. * The firstpos of a nonempty leaf is that leaf itself. * The firstpos of a QMARK, STAR, or PLUS node is the firstpos of its argument. * The firstpos of a CAT node is the firstpos of the left argument, union the firstpos of the right if the left argument is nullable. * The firstpos of an OR node is the union of firstpos of each argument. Lastpos: The lastpos of a node is the set of positions that could correspond to the last character of a string matching the regexp at the given node. * EMPTY leaves have empty lastpos. * The lastpos of a nonempty leaf is that leaf itself. * The lastpos of a QMARK, STAR, or PLUS node is the lastpos of its argument. * The lastpos of a CAT node is the lastpos of its right argument, union the lastpos of the left if the right argument is nullable. * The lastpos of an OR node is the union of the lastpos of each argument. Follow: The follow of a position is the set of positions that could correspond to the character following a character matching the node in a string matching the regexp. At this point we consider special symbols that match the empty string in some context to be just normal characters. Later, if we find that a special symbol is in a follow set, we will replace it with the elements of its follow, labeled with an appropriate constraint. * Every node in the firstpos of the argument of a STAR or PLUS node is in the follow of every node in the lastpos. * Every node in the firstpos of the second argument of a CAT node is in the follow of every node in the lastpos of the first argument. Because of the postfix representation of the parse tree, the depth-first analysis is conveniently done by a linear scan with the aid of a stack. Sets are stored as arrays of the elements, obeying a stack-like allocation scheme; the number of elements in each set deeper in the stack can be used to determine the address of a particular set's array. */ void dfaanalyze (struct dfa *d, int searchflag) { int *nullable; /* Nullable stack. */ int *nfirstpos; /* Element count stack for firstpos sets. */ position *firstpos; /* Array where firstpos elements are stored. */ int *nlastpos; /* Element count stack for lastpos sets. */ position *lastpos; /* Array where lastpos elements are stored. */ int *nalloc; /* Sizes of arrays allocated to follow sets. */ position_set tmp; /* Temporary set for merging sets. */ position_set merged; /* Result of merging sets. */ int wants_newline; /* True if some position wants newline info. */ int *o_nullable; int *o_nfirst, *o_nlast; position *o_firstpos, *o_lastpos; int i, j; position *pos; #ifdef DEBUG fprintf(stderr, "dfaanalyze:\n"); for (i = 0; i < d->tindex; ++i) { fprintf(stderr, " %d:", i); prtok(d->tokens[i]); } putc('\n', stderr); #endif d->searchflag = searchflag; MALLOC(nullable, int, d->depth); o_nullable = nullable; MALLOC(nfirstpos, int, d->depth); o_nfirst = nfirstpos; MALLOC(firstpos, position, d->nleaves); o_firstpos = firstpos, firstpos += d->nleaves; MALLOC(nlastpos, int, d->depth); o_nlast = nlastpos; MALLOC(lastpos, position, d->nleaves); o_lastpos = lastpos, lastpos += d->nleaves; MALLOC(nalloc, int, d->tindex); for (i = 0; i < d->tindex; ++i) nalloc[i] = 0; MALLOC(merged.elems, position, d->nleaves); CALLOC(d->follows, position_set, d->tindex); for (i = 0; i < d->tindex; ++i) #ifdef DEBUG { /* Nonsyntactic #ifdef goo... */ #endif switch (d->tokens[i]) { case EMPTY: /* The empty set is nullable. */ *nullable++ = 1; /* The firstpos and lastpos of the empty leaf are both empty. */ *nfirstpos++ = *nlastpos++ = 0; break; case STAR: case PLUS: /* Every element in the firstpos of the argument is in the follow of every element in the lastpos. */ tmp.nelem = nfirstpos[-1]; tmp.elems = firstpos; pos = lastpos; for (j = 0; j < nlastpos[-1]; ++j) { merge(&tmp, &d->follows[pos[j].index], &merged); REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems, position, nalloc[pos[j].index], merged.nelem - 1); copy(&merged, &d->follows[pos[j].index]); } case QMARK: /* A QMARK or STAR node is automatically nullable. */ if (d->tokens[i] != PLUS) nullable[-1] = 1; break; case CAT: /* Every element in the firstpos of the second argument is in the follow of every element in the lastpos of the first argument. */ tmp.nelem = nfirstpos[-1]; tmp.elems = firstpos; pos = lastpos + nlastpos[-1]; for (j = 0; j < nlastpos[-2]; ++j) { merge(&tmp, &d->follows[pos[j].index], &merged); REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems, position, nalloc[pos[j].index], merged.nelem - 1); copy(&merged, &d->follows[pos[j].index]); } /* The firstpos of a CAT node is the firstpos of the first argument, union that of the second argument if the first is nullable. */ if (nullable[-2]) nfirstpos[-2] += nfirstpos[-1]; else firstpos += nfirstpos[-1]; --nfirstpos; /* The lastpos of a CAT node is the lastpos of the second argument, union that of the first argument if the second is nullable. */ if (nullable[-1]) nlastpos[-2] += nlastpos[-1]; else { pos = lastpos + nlastpos[-2]; for (j = nlastpos[-1] - 1; j >= 0; --j) pos[j] = lastpos[j]; lastpos += nlastpos[-2]; nlastpos[-2] = nlastpos[-1]; } --nlastpos; /* A CAT node is nullable if both arguments are nullable. */ nullable[-2] = nullable[-1] && nullable[-2]; --nullable; break; case OR: case ORTOP: /* The firstpos is the union of the firstpos of each argument. */ nfirstpos[-2] += nfirstpos[-1]; --nfirstpos; /* The lastpos is the union of the lastpos of each argument. */ nlastpos[-2] += nlastpos[-1]; --nlastpos; /* An OR node is nullable if either argument is nullable. */ nullable[-2] = nullable[-1] || nullable[-2]; --nullable; break; default: /* Anything else is a nonempty position. (Note that special constructs like \< are treated as nonempty strings here; an "epsilon closure" effectively makes them nullable later. Backreferences have to get a real position so we can detect transitions on them later. But they are nullable. */ *nullable++ = d->tokens[i] == BACKREF; /* This position is in its own firstpos and lastpos. */ *nfirstpos++ = *nlastpos++ = 1; --firstpos, --lastpos; firstpos->index = lastpos->index = i; firstpos->constraint = lastpos->constraint = NO_CONSTRAINT; /* Allocate the follow set for this position. */ nalloc[i] = 1; MALLOC(d->follows[i].elems, position, nalloc[i]); break; } #ifdef DEBUG /* ... balance the above nonsyntactic #ifdef goo... */ fprintf(stderr, "node %d:", i); prtok(d->tokens[i]); putc('\n', stderr); fprintf(stderr, nullable[-1] ? " nullable: yes\n" : " nullable: no\n"); fprintf(stderr, " firstpos:"); for (j = nfirstpos[-1] - 1; j >= 0; --j) { fprintf(stderr, " %d:", firstpos[j].index); prtok(d->tokens[firstpos[j].index]); } fprintf(stderr, "\n lastpos:"); for (j = nlastpos[-1] - 1; j >= 0; --j) { fprintf(stderr, " %d:", lastpos[j].index); prtok(d->tokens[lastpos[j].index]); } putc('\n', stderr); } #endif /* For each follow set that is the follow set of a real position, replace it with its epsilon closure. */ for (i = 0; i < d->tindex; ++i) if (d->tokens[i] < NOTCHAR || d->tokens[i] == BACKREF #ifdef MBS_SUPPORT || d->tokens[i] == ANYCHAR || d->tokens[i] == MBCSET #endif || d->tokens[i] >= CSET) { #ifdef DEBUG fprintf(stderr, "follows(%d:", i); prtok(d->tokens[i]); fprintf(stderr, "):"); for (j = d->follows[i].nelem - 1; j >= 0; --j) { fprintf(stderr, " %d:", d->follows[i].elems[j].index); prtok(d->tokens[d->follows[i].elems[j].index]); } putc('\n', stderr); #endif copy(&d->follows[i], &merged); epsclosure(&merged, d); if (d->follows[i].nelem < merged.nelem) REALLOC(d->follows[i].elems, position, merged.nelem); copy(&merged, &d->follows[i]); } /* Get the epsilon closure of the firstpos of the regexp. The result will be the set of positions of state 0. */ merged.nelem = 0; for (i = 0; i < nfirstpos[-1]; ++i) insert(firstpos[i], &merged); epsclosure(&merged, d); /* Check if any of the positions of state 0 will want newline context. */ wants_newline = 0; for (i = 0; i < merged.nelem; ++i) if (PREV_NEWLINE_DEPENDENT(merged.elems[i].constraint)) wants_newline = 1; /* Build the initial state. */ d->salloc = 1; d->sindex = 0; MALLOC(d->states, dfa_state, d->salloc); state_index(d, &merged, wants_newline, 0); free(o_nullable); free(o_nfirst); free(o_firstpos); free(o_nlast); free(o_lastpos); free(nalloc); free(merged.elems); } /* Find, for each character, the transition out of state s of d, and store it in the appropriate slot of trans. We divide the positions of s into groups (positions can appear in more than one group). Each group is labeled with a set of characters that every position in the group matches (taking into account, if necessary, preceding context information of s). For each group, find the union of the its elements' follows. This set is the set of positions of the new state. For each character in the group's label, set the transition on this character to be to a state corresponding to the set's positions, and its associated backward context information, if necessary. If we are building a searching matcher, we include the positions of state 0 in every state. The collection of groups is constructed by building an equivalence-class partition of the positions of s. For each position, find the set of characters C that it matches. Eliminate any characters from C that fail on grounds of backward context. Search through the groups, looking for a group whose label L has nonempty intersection with C. If L - C is nonempty, create a new group labeled L - C and having the same positions as the current group, and set L to the intersection of L and C. Insert the position in this group, set C = C - L, and resume scanning. If after comparing with every group there are characters remaining in C, create a new group labeled with the characters of C and insert this position in that group. */ void dfastate (int s, struct dfa *d, int trans[]) { position_set grps[NOTCHAR]; /* As many as will ever be needed. */ charclass labels[NOTCHAR]; /* Labels corresponding to the groups. */ int ngrps = 0; /* Number of groups actually used. */ position pos; /* Current position being considered. */ charclass matches; /* Set of matching characters. */ int matchesf; /* True if matches is nonempty. */ charclass intersect; /* Intersection with some label set. */ int intersectf; /* True if intersect is nonempty. */ charclass leftovers; /* Stuff in the label that didn't match. */ int leftoversf; /* True if leftovers is nonempty. */ static charclass letters; /* Set of characters considered letters. */ static charclass newline; /* Set of characters that aren't newline. */ position_set follows; /* Union of the follows of some group. */ position_set tmp; /* Temporary space for merging sets. */ int state; /* New state. */ int wants_newline; /* New state wants to know newline context. */ int state_newline; /* New state on a newline transition. */ int wants_letter; /* New state wants to know letter context. */ int state_letter; /* New state on a letter transition. */ static int initialized; /* Flag for static initialization. */ #ifdef MBS_SUPPORT int next_isnt_1st_byte = 0; /* Flag If we can't add state0. */ #endif int i, j, k; /* Initialize the set of letters, if necessary. */ if (! initialized) { initialized = 1; for (i = 0; i < NOTCHAR; ++i) if (IS_WORD_CONSTITUENT(i)) setbit(i, letters); setbit(eolbyte, newline); } zeroset(matches); for (i = 0; i < d->states[s].elems.nelem; ++i) { pos = d->states[s].elems.elems[i]; if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR) setbit(d->tokens[pos.index], matches); else if (d->tokens[pos.index] >= CSET) copyset(d->charclasses[d->tokens[pos.index] - CSET], matches); #ifdef MBS_SUPPORT else if (d->tokens[pos.index] == ANYCHAR || d->tokens[pos.index] == MBCSET) /* MB_CUR_MAX > 1 */ { /* ANYCHAR and MBCSET must match with a single character, so we must put it to d->states[s].mbps, which contains the positions which can match with a single character not a byte. */ if (d->states[s].mbps.nelem == 0) { MALLOC(d->states[s].mbps.elems, position, d->states[s].elems.nelem); } insert(pos, &(d->states[s].mbps)); continue; } #endif /* MBS_SUPPORT */ else continue; /* Some characters may need to be eliminated from matches because they fail in the current context. */ if (pos.constraint != 0xFF) { if (! MATCHES_NEWLINE_CONTEXT(pos.constraint, d->states[s].newline, 1)) clrbit(eolbyte, matches); if (! MATCHES_NEWLINE_CONTEXT(pos.constraint, d->states[s].newline, 0)) for (j = 0; j < CHARCLASS_INTS; ++j) matches[j] &= newline[j]; if (! MATCHES_LETTER_CONTEXT(pos.constraint, d->states[s].letter, 1)) for (j = 0; j < CHARCLASS_INTS; ++j) matches[j] &= ~letters[j]; if (! MATCHES_LETTER_CONTEXT(pos.constraint, d->states[s].letter, 0)) for (j = 0; j < CHARCLASS_INTS; ++j) matches[j] &= letters[j]; /* If there are no characters left, there's no point in going on. */ for (j = 0; j < CHARCLASS_INTS && !matches[j]; ++j) continue; if (j == CHARCLASS_INTS) continue; } for (j = 0; j < ngrps; ++j) { /* If matches contains a single character only, and the current group's label doesn't contain that character, go on to the next group. */ if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR && !tstbit(d->tokens[pos.index], labels[j])) continue; /* Check if this group's label has a nonempty intersection with matches. */ intersectf = 0; for (k = 0; k < CHARCLASS_INTS; ++k) (intersect[k] = matches[k] & labels[j][k]) ? (intersectf = 1) : 0; if (! intersectf) continue; /* It does; now find the set differences both ways. */ leftoversf = matchesf = 0; for (k = 0; k < CHARCLASS_INTS; ++k) { /* Even an optimizing compiler can't know this for sure. */ int match = matches[k], label = labels[j][k]; (leftovers[k] = ~match & label) ? (leftoversf = 1) : 0; (matches[k] = match & ~label) ? (matchesf = 1) : 0; } /* If there were leftovers, create a new group labeled with them. */ if (leftoversf) { copyset(leftovers, labels[ngrps]); copyset(intersect, labels[j]); MALLOC(grps[ngrps].elems, position, d->nleaves); copy(&grps[j], &grps[ngrps]); ++ngrps; } /* Put the position in the current group. Note that there is no reason to call insert() here. */ grps[j].elems[grps[j].nelem++] = pos; /* If every character matching the current position has been accounted for, we're done. */ if (! matchesf) break; } /* If we've passed the last group, and there are still characters unaccounted for, then we'll have to create a new group. */ if (j == ngrps) { copyset(matches, labels[ngrps]); zeroset(matches); MALLOC(grps[ngrps].elems, position, d->nleaves); grps[ngrps].nelem = 1; grps[ngrps].elems[0] = pos; ++ngrps; } } MALLOC(follows.elems, position, d->nleaves); MALLOC(tmp.elems, position, d->nleaves); /* If we are a searching matcher, the default transition is to a state containing the positions of state 0, otherwise the default transition is to fail miserably. */ if (d->searchflag) { wants_newline = 0; wants_letter = 0; for (i = 0; i < d->states[0].elems.nelem; ++i) { if (PREV_NEWLINE_DEPENDENT(d->states[0].elems.elems[i].constraint)) wants_newline = 1; if (PREV_LETTER_DEPENDENT(d->states[0].elems.elems[i].constraint)) wants_letter = 1; } copy(&d->states[0].elems, &follows); state = state_index(d, &follows, 0, 0); if (wants_newline) state_newline = state_index(d, &follows, 1, 0); else state_newline = state; if (wants_letter) state_letter = state_index(d, &follows, 0, 1); else state_letter = state; for (i = 0; i < NOTCHAR; ++i) trans[i] = (IS_WORD_CONSTITUENT(i)) ? state_letter : state; trans[eolbyte] = state_newline; } else for (i = 0; i < NOTCHAR; ++i) trans[i] = -1; for (i = 0; i < ngrps; ++i) { follows.nelem = 0; /* Find the union of the follows of the positions of the group. This is a hideously inefficient loop. Fix it someday. */ for (j = 0; j < grps[i].nelem; ++j) for (k = 0; k < d->follows[grps[i].elems[j].index].nelem; ++k) insert(d->follows[grps[i].elems[j].index].elems[k], &follows); #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { /* If a token in follows.elems is not 1st byte of a multibyte character, or the states of follows must accept the bytes which are not 1st byte of the multibyte character. Then, if a state of follows encounter a byte, it must not be a 1st byte of a multibyte character nor singlebyte character. We cansel to add state[0].follows to next state, because state[0] must accept 1st-byte For example, we assume is a certain singlebyte character, is a certain multibyte character, and the codepoint of equals the 2nd byte of the codepoint of . When state[0] accepts , state[i] transit to state[i+1] by accepting accepts 1st byte of , and state[i+1] accepts 2nd byte of , if state[i+1] encounter the codepoint of , it must not be but 2nd byte of , so we can not add state[0]. */ next_isnt_1st_byte = 0; for (j = 0; j < follows.nelem; ++j) { if (!(d->multibyte_prop[follows.elems[j].index] & 1)) { next_isnt_1st_byte = 1; break; } } } #endif /* If we are building a searching matcher, throw in the positions of state 0 as well. */ #ifdef MBS_SUPPORT if (d->searchflag && (MB_CUR_MAX == 1 || !next_isnt_1st_byte)) #else if (d->searchflag) #endif for (j = 0; j < d->states[0].elems.nelem; ++j) insert(d->states[0].elems.elems[j], &follows); /* Find out if the new state will want any context information. */ wants_newline = 0; if (tstbit(eolbyte, labels[i])) for (j = 0; j < follows.nelem; ++j) if (PREV_NEWLINE_DEPENDENT(follows.elems[j].constraint)) wants_newline = 1; wants_letter = 0; for (j = 0; j < CHARCLASS_INTS; ++j) if (labels[i][j] & letters[j]) break; if (j < CHARCLASS_INTS) for (j = 0; j < follows.nelem; ++j) if (PREV_LETTER_DEPENDENT(follows.elems[j].constraint)) wants_letter = 1; /* Find the state(s) corresponding to the union of the follows. */ state = state_index(d, &follows, 0, 0); if (wants_newline) state_newline = state_index(d, &follows, 1, 0); else state_newline = state; if (wants_letter) state_letter = state_index(d, &follows, 0, 1); else state_letter = state; /* Set the transitions for each character in the current label. */ for (j = 0; j < CHARCLASS_INTS; ++j) for (k = 0; k < INTBITS; ++k) if (labels[i][j] & 1 << k) { int c = j * INTBITS + k; if (c == eolbyte) trans[c] = state_newline; else if (IS_WORD_CONSTITUENT(c)) trans[c] = state_letter; else if (c < NOTCHAR) trans[c] = state; } } for (i = 0; i < ngrps; ++i) free(grps[i].elems); free(follows.elems); free(tmp.elems); } /* Some routines for manipulating a compiled dfa's transition tables. Each state may or may not have a transition table; if it does, and it is a non-accepting state, then d->trans[state] points to its table. If it is an accepting state then d->fails[state] points to its table. If it has no table at all, then d->trans[state] is NULL. TODO: Improve this comment, get rid of the unnecessary redundancy. */ static void build_state (int s, struct dfa *d) { int *trans; /* The new transition table. */ int i; /* Set an upper limit on the number of transition tables that will ever exist at once. 1024 is arbitrary. The idea is that the frequently used transition tables will be quickly rebuilt, whereas the ones that were only needed once or twice will be cleared away. */ if (d->trcount >= 1024) { for (i = 0; i < d->tralloc; ++i) if (d->trans[i]) { free((ptr_t) d->trans[i]); d->trans[i] = NULL; } else if (d->fails[i]) { free((ptr_t) d->fails[i]); d->fails[i] = NULL; } d->trcount = 0; } ++d->trcount; /* Set up the success bits for this state. */ d->success[s] = 0; if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 1, d->states[s].letter, 0, s, *d)) d->success[s] |= 4; if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 0, d->states[s].letter, 1, s, *d)) d->success[s] |= 2; if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 0, d->states[s].letter, 0, s, *d)) d->success[s] |= 1; MALLOC(trans, int, NOTCHAR); dfastate(s, d, trans); /* Now go through the new transition table, and make sure that the trans and fail arrays are allocated large enough to hold a pointer for the largest state mentioned in the table. */ for (i = 0; i < NOTCHAR; ++i) if (trans[i] >= d->tralloc) { int oldalloc = d->tralloc; while (trans[i] >= d->tralloc) d->tralloc *= 2; REALLOC(d->realtrans, int *, d->tralloc + 1); d->trans = d->realtrans + 1; REALLOC(d->fails, int *, d->tralloc); REALLOC(d->success, int, d->tralloc); while (oldalloc < d->tralloc) { d->trans[oldalloc] = NULL; d->fails[oldalloc++] = NULL; } } /* Newline is a sentinel. */ trans[eolbyte] = -1; if (ACCEPTING(s, *d)) d->fails[s] = trans; else d->trans[s] = trans; } static void build_state_zero (struct dfa *d) { d->tralloc = 1; d->trcount = 0; CALLOC(d->realtrans, int *, d->tralloc + 1); d->trans = d->realtrans + 1; CALLOC(d->fails, int *, d->tralloc); MALLOC(d->success, int, d->tralloc); build_state(0, d); } #ifdef MBS_SUPPORT /* Multibyte character handling sub-routins for dfaexec. */ /* Initial state may encounter the byte which is not a singlebyte character nor 1st byte of a multibyte character. But it is incorrect for initial state to accept such a byte. For example, in sjis encoding the regular expression like "\\" accepts the codepoint 0x5c, but should not accept the 2nd byte of the codepoint 0x815c. Then Initial state must skip the bytes which are not a singlebyte character nor 1st byte of a multibyte character. */ #define SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p) \ if (s == 0) \ { \ while (inputwcs[p - buf_begin] == 0 \ && mblen_buf[p - buf_begin] > 0 \ && p < buf_end) \ ++p; \ if (p >= end) \ { \ free(mblen_buf); \ free(inputwcs); \ return (size_t) -1; \ } \ } static void realloc_trans_if_necessary(struct dfa *d, int new_state) { /* Make sure that the trans and fail arrays are allocated large enough to hold a pointer for the new state. */ if (new_state >= d->tralloc) { int oldalloc = d->tralloc; while (new_state >= d->tralloc) d->tralloc *= 2; REALLOC(d->realtrans, int *, d->tralloc + 1); d->trans = d->realtrans + 1; REALLOC(d->fails, int *, d->tralloc); REALLOC(d->success, int, d->tralloc); while (oldalloc < d->tralloc) { d->trans[oldalloc] = NULL; d->fails[oldalloc++] = NULL; } } } /* Return values of transit_state_singlebyte(), and transit_state_consume_1char. */ typedef enum { TRANSIT_STATE_IN_PROGRESS, /* State transition has not finished. */ TRANSIT_STATE_DONE, /* State transition has finished. */ TRANSIT_STATE_END_BUFFER /* Reach the end of the buffer. */ } status_transit_state; /* Consume a single byte and transit state from 's' to '*next_state'. This function is almost same as the state transition routin in dfaexec(). But state transition is done just once, otherwise matching succeed or reach the end of the buffer. */ static status_transit_state transit_state_singlebyte (struct dfa *d, int s, unsigned char const *p, int *next_state) { int *t; int works = s; status_transit_state rval = TRANSIT_STATE_IN_PROGRESS; while (rval == TRANSIT_STATE_IN_PROGRESS) { if ((t = d->trans[works]) != NULL) { works = t[*p]; rval = TRANSIT_STATE_DONE; if (works < 0) works = 0; } else if (works < 0) { if (p == buf_end) /* At the moment, it must not happen. */ return TRANSIT_STATE_END_BUFFER; works = 0; } else if (d->fails[works]) { works = d->fails[works][*p]; rval = TRANSIT_STATE_DONE; } else { build_state(works, d); } } *next_state = works; return rval; } /* Check whether period can match or not in the current context. If it can, return the amount of the bytes with which period can match, otherwise return 0. `pos' is the position of the period. `index' is the index from the buf_begin, and it is the current position in the buffer. */ static int match_anychar (struct dfa *d, int s, position pos, int index) { int newline = 0; int letter = 0; wchar_t wc; int mbclen; wc = inputwcs[index]; mbclen = (mblen_buf[index] == 0)? 1 : mblen_buf[index]; /* Check context. */ if (wc == (wchar_t)eolbyte) { if (!(syntax_bits & RE_DOT_NEWLINE)) return 0; newline = 1; } else if (wc == (wchar_t)'\0') { if (syntax_bits & RE_DOT_NOT_NULL) return 0; newline = 1; } if (iswalnum(wc) || wc == L'_') letter = 1; if (!SUCCEEDS_IN_CONTEXT(pos.constraint, d->states[s].newline, newline, d->states[s].letter, letter)) return 0; return mbclen; } /* Check whether bracket expression can match or not in the current context. If it can, return the amount of the bytes with which expression can match, otherwise return 0. `pos' is the position of the bracket expression. `index' is the index from the buf_begin, and it is the current position in the buffer. */ int match_mb_charset (struct dfa *d, int s, position pos, int index) { int i; int match; /* Flag which represent that matching succeed. */ int match_len; /* Length of the character (or collating element) with which this operator match. */ - size_t op_len; /* Length of the operator. */ + int op_len; /* Length of the operator. */ char buffer[128]; wchar_t wcbuf[6]; /* Pointer to the structure to which we are currently reffering. */ struct mb_char_classes *work_mbc; int newline = 0; int letter = 0; wchar_t wc; /* Current reffering character. */ wc = inputwcs[index]; /* Check context. */ if (wc == (wchar_t)eolbyte) { if (!(syntax_bits & RE_DOT_NEWLINE)) return 0; newline = 1; } else if (wc == (wchar_t)'\0') { if (syntax_bits & RE_DOT_NOT_NULL) return 0; newline = 1; } if (iswalnum(wc) || wc == L'_') letter = 1; if (!SUCCEEDS_IN_CONTEXT(pos.constraint, d->states[s].newline, newline, d->states[s].letter, letter)) return 0; /* Assign the current reffering operator to work_mbc. */ work_mbc = &(d->mbcsets[(d->multibyte_prop[pos.index]) >> 2]); match = !work_mbc->invert; match_len = (mblen_buf[index] == 0)? 1 : mblen_buf[index]; /* match with a character class? */ for (i = 0; inch_classes; i++) { if (iswctype((wint_t)wc, work_mbc->ch_classes[i])) goto charset_matched; } strncpy(buffer, buf_begin + index, match_len); buffer[match_len] = '\0'; /* match with an equivalent class? */ for (i = 0; inequivs; i++) { op_len = strlen(work_mbc->equivs[i]); strncpy(buffer, buf_begin + index, op_len); buffer[op_len] = '\0'; if (strcoll(work_mbc->equivs[i], buffer) == 0) { match_len = op_len; goto charset_matched; } } /* match with a collating element? */ for (i = 0; incoll_elems; i++) { op_len = strlen(work_mbc->coll_elems[i]); strncpy(buffer, buf_begin + index, op_len); buffer[op_len] = '\0'; if (strcoll(work_mbc->coll_elems[i], buffer) == 0) { match_len = op_len; goto charset_matched; } } wcbuf[0] = wc; wcbuf[1] = wcbuf[3] = wcbuf[5] = '\0'; /* match with a range? */ for (i = 0; inranges; i++) { wcbuf[2] = work_mbc->range_sts[i]; wcbuf[4] = work_mbc->range_ends[i]; if (wcscoll(wcbuf, wcbuf+2) >= 0 && wcscoll(wcbuf+4, wcbuf) >= 0) goto charset_matched; } /* match with a character? */ if (case_fold) wc = towlower (wc); for (i = 0; inchars; i++) { if (wc == work_mbc->chars[i]) goto charset_matched; } match = !match; charset_matched: return match ? match_len : 0; } /* Check each of `d->states[s].mbps.elem' can match or not. Then return the array which corresponds to `d->states[s].mbps.elem' and each element of the array contains the amount of the bytes with which the element can match. `index' is the index from the buf_begin, and it is the current position in the buffer. Caller MUST free the array which this function return. */ static int* check_matching_with_multibyte_ops (struct dfa *d, int s, int index) { int i; int* rarray; MALLOC(rarray, int, d->states[s].mbps.nelem); for (i = 0; i < d->states[s].mbps.nelem; ++i) { position pos = d->states[s].mbps.elems[i]; switch(d->tokens[pos.index]) { case ANYCHAR: rarray[i] = match_anychar(d, s, pos, index); break; case MBCSET: rarray[i] = match_mb_charset(d, s, pos, index); break; default: break; /* can not happen. */ } } return rarray; } /* Consume a single character and enumerate all of the positions which can be next position from the state `s'. `match_lens' is the input. It can be NULL, but it can also be the output of check_matching_with_multibyte_ops() for optimization. `mbclen' and `pps' are the output. `mbclen' is the length of the character consumed, and `pps' is the set this function enumerate. */ static status_transit_state transit_state_consume_1char (struct dfa *d, int s, unsigned char const **pp, int *match_lens, int *mbclen, position_set *pps) { int i, j; int s1, s2; int* work_mbls; status_transit_state rs = TRANSIT_STATE_DONE; /* Calculate the length of the (single/multi byte) character to which p points. */ *mbclen = (mblen_buf[*pp - buf_begin] == 0)? 1 : mblen_buf[*pp - buf_begin]; /* Calculate the state which can be reached from the state `s' by consuming `*mbclen' single bytes from the buffer. */ s1 = s; for (i = 0; i < *mbclen; i++) { s2 = s1; rs = transit_state_singlebyte(d, s2, (*pp)++, &s1); } /* Copy the positions contained by `s1' to the set `pps'. */ copy(&(d->states[s1].elems), pps); /* Check (inputed)match_lens, and initialize if it is NULL. */ if (match_lens == NULL && d->states[s].mbps.nelem != 0) work_mbls = check_matching_with_multibyte_ops(d, s, *pp - buf_begin); else work_mbls = match_lens; /* Add all of the positions which can be reached from `s' by consuming a single character. */ for (i = 0; i < d->states[s].mbps.nelem ; i++) { if (work_mbls[i] == *mbclen) for (j = 0; j < d->follows[d->states[s].mbps.elems[i].index].nelem; j++) insert(d->follows[d->states[s].mbps.elems[i].index].elems[j], pps); } if (match_lens == NULL && work_mbls != NULL) free(work_mbls); return rs; } /* Transit state from s, then return new state and update the pointer of the buffer. This function is for some operator which can match with a multi- byte character or a collating element(which may be multi characters). */ static int transit_state (struct dfa *d, int s, unsigned char const **pp) { int s1; int mbclen; /* The length of current input multibyte character. */ int maxlen = 0; int i, j; int *match_lens = NULL; int nelem = d->states[s].mbps.nelem; /* Just a alias. */ position_set follows; unsigned char const *p1 = *pp; status_transit_state rs; wchar_t wc; if (nelem > 0) /* This state has (a) multibyte operator(s). We check whether each of them can match or not. */ { /* Note: caller must free the return value of this function. */ match_lens = check_matching_with_multibyte_ops(d, s, *pp - buf_begin); for (i = 0; i < nelem; i++) /* Search the operator which match the longest string, in this state. */ { if (match_lens[i] > maxlen) maxlen = match_lens[i]; } } if (nelem == 0 || maxlen == 0) /* This state has no multibyte operator which can match. We need to check only one singlebyte character. */ { status_transit_state rs; rs = transit_state_singlebyte(d, s, *pp, &s1); /* We must update the pointer if state transition succeeded. */ if (rs == TRANSIT_STATE_DONE) ++*pp; if (match_lens != NULL) free(match_lens); return s1; } /* This state has some operators which can match a multibyte character. */ follows.nelem = 0; MALLOC(follows.elems, position, d->nleaves); /* `maxlen' may be longer than the length of a character, because it may not be a character but a (multi character) collating element. We enumerate all of the positions which `s' can reach by consuming `maxlen' bytes. */ rs = transit_state_consume_1char(d, s, pp, match_lens, &mbclen, &follows); wc = inputwcs[*pp - mbclen - buf_begin]; s1 = state_index(d, &follows, wc == L'\n', iswalnum(wc)); realloc_trans_if_necessary(d, s1); while (*pp - p1 < maxlen) { follows.nelem = 0; rs = transit_state_consume_1char(d, s1, pp, NULL, &mbclen, &follows); for (i = 0; i < nelem ; i++) { if (match_lens[i] == *pp - p1) for (j = 0; j < d->follows[d->states[s1].mbps.elems[i].index].nelem; j++) insert(d->follows[d->states[s1].mbps.elems[i].index].elems[j], &follows); } wc = inputwcs[*pp - mbclen - buf_begin]; s1 = state_index(d, &follows, wc == L'\n', iswalnum(wc)); realloc_trans_if_necessary(d, s1); } free(match_lens); free(follows.elems); return s1; } #endif /* Search through a buffer looking for a match to the given struct dfa. Find the first occurrence of a string matching the regexp in the buffer, and the shortest possible version thereof. Return the offset of the first character after the match, or (size_t) -1 if none is found. BEGIN points to the beginning of the buffer, and SIZE is the size of the buffer. If SIZE is nonzero, BEGIN[SIZE - 1] must be a newline. BACKREF points to a place where we're supposed to store a 1 if backreferencing happened and the match needs to be verified by a backtracking matcher. Otherwise we store a 0 in *backref. */ size_t dfaexec (struct dfa *d, char const *begin, size_t size, int *backref) { register int s; /* Current state. */ register unsigned char const *p; /* Current input character. */ register unsigned char const *end; /* One past the last input character. */ register int **trans, *t; /* Copy of d->trans so it can be optimized into a register. */ register unsigned char eol = eolbyte; /* Likewise for eolbyte. */ static int sbit[NOTCHAR]; /* Table for anding with d->success. */ static int sbit_init; if (! sbit_init) { int i; sbit_init = 1; for (i = 0; i < NOTCHAR; ++i) sbit[i] = (IS_WORD_CONSTITUENT(i)) ? 2 : 1; sbit[eol] = 4; } if (! d->tralloc) build_state_zero(d); s = 0; p = (unsigned char const *) begin; end = p + size; trans = d->trans; #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { int remain_bytes, i; buf_begin = begin; buf_end = end; /* initialize mblen_buf, and inputwcs. */ MALLOC(mblen_buf, unsigned char, end - (unsigned char const *)begin + 2); MALLOC(inputwcs, wchar_t, end - (unsigned char const *)begin + 2); memset(&mbs, 0, sizeof(mbstate_t)); remain_bytes = 0; for (i = 0; i < end - (unsigned char const *)begin + 1; i++) { if (remain_bytes == 0) { remain_bytes = mbrtowc(inputwcs + i, begin + i, end - (unsigned char const *)begin - i + 1, &mbs); if (remain_bytes <= 1) { remain_bytes = 0; inputwcs[i] = (wchar_t)begin[i]; mblen_buf[i] = 0; } else { mblen_buf[i] = remain_bytes; remain_bytes--; } } else { mblen_buf[i] = remain_bytes; inputwcs[i] = 0; remain_bytes--; } } mblen_buf[i] = 0; inputwcs[i] = 0; /* sentinel */ } #endif /* MBS_SUPPORT */ for (;;) { #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) while ((t = trans[s])) { if (d->states[s].mbps.nelem != 0) { /* Can match with a multibyte character( and multi character collating element). */ unsigned char const *nextp; SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p); nextp = p; s = transit_state(d, s, &nextp); p = nextp; /* Trans table might be updated. */ trans = d->trans; } else { SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p); s = t[*p++]; } } else #endif /* MBS_SUPPORT */ while ((t = trans[s])) s = t[*p++]; if (s < 0) { if (p == end) { #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { free(mblen_buf); free(inputwcs); } #endif /* MBS_SUPPORT */ return (size_t) -1; } s = 0; } else if ((t = d->fails[s])) { if (d->success[s] & sbit[*p]) { if (backref) *backref = (d->states[s].backref != 0); #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { free(mblen_buf); free(inputwcs); } #endif /* MBS_SUPPORT */ return (char const *) p - begin; } #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p); if (d->states[s].mbps.nelem != 0) { /* Can match with a multibyte character( and multi character collating element). */ unsigned char const *nextp; nextp = p; s = transit_state(d, s, &nextp); p = nextp; /* Trans table might be updated. */ trans = d->trans; } else s = t[*p++]; } else #endif /* MBS_SUPPORT */ s = t[*p++]; } else { build_state(s, d); trans = d->trans; } } } /* Initialize the components of a dfa that the other routines don't initialize for themselves. */ void dfainit (struct dfa *d) { d->calloc = 1; MALLOC(d->charclasses, charclass, d->calloc); d->cindex = 0; d->talloc = 1; MALLOC(d->tokens, token, d->talloc); d->tindex = d->depth = d->nleaves = d->nregexps = 0; #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { d->nmultibyte_prop = 1; MALLOC(d->multibyte_prop, int, d->nmultibyte_prop); d->nmbcsets = 0; d->mbcsets_alloc = 1; MALLOC(d->mbcsets, struct mb_char_classes, d->mbcsets_alloc); } #endif d->searchflag = 0; d->tralloc = 0; d->musts = 0; } /* Parse and analyze a single string of the given length. */ void dfacomp (char const *s, size_t len, struct dfa *d, int searchflag) { if (case_fold) /* dummy folding in service of dfamust() */ { char *lcopy; int i; lcopy = malloc(len); if (!lcopy) dfaerror(_("out of memory")); /* This is a kludge. */ case_fold = 0; for (i = 0; i < len; ++i) if (ISUPPER ((unsigned char) s[i])) lcopy[i] = tolower ((unsigned char) s[i]); else lcopy[i] = s[i]; dfainit(d); dfaparse(lcopy, len, d); free(lcopy); dfamust(d); d->cindex = d->tindex = d->depth = d->nleaves = d->nregexps = 0; case_fold = 1; dfaparse(s, len, d); dfaanalyze(d, searchflag); } else { dfainit(d); dfaparse(s, len, d); dfamust(d); dfaanalyze(d, searchflag); } } /* Free the storage held by the components of a dfa. */ void dfafree (struct dfa *d) { int i; struct dfamust *dm, *ndm; free((ptr_t) d->charclasses); free((ptr_t) d->tokens); #ifdef MBS_SUPPORT if (MB_CUR_MAX > 1) { free((ptr_t) d->multibyte_prop); for (i = 0; i < d->nmbcsets; ++i) { int j; struct mb_char_classes *p = &(d->mbcsets[i]); if (p->chars != NULL) free(p->chars); if (p->ch_classes != NULL) free(p->ch_classes); if (p->range_sts != NULL) free(p->range_sts); if (p->range_ends != NULL) free(p->range_ends); for (j = 0; j < p->nequivs; ++j) free(p->equivs[j]); if (p->equivs != NULL) free(p->equivs); for (j = 0; j < p->ncoll_elems; ++j) free(p->coll_elems[j]); if (p->coll_elems != NULL) free(p->coll_elems); } free((ptr_t) d->mbcsets); } #endif /* MBS_SUPPORT */ for (i = 0; i < d->sindex; ++i) free((ptr_t) d->states[i].elems.elems); free((ptr_t) d->states); for (i = 0; i < d->tindex; ++i) if (d->follows[i].elems) free((ptr_t) d->follows[i].elems); free((ptr_t) d->follows); for (i = 0; i < d->tralloc; ++i) if (d->trans[i]) free((ptr_t) d->trans[i]); else if (d->fails[i]) free((ptr_t) d->fails[i]); if (d->realtrans) free((ptr_t) d->realtrans); if (d->fails) free((ptr_t) d->fails); if (d->success) free((ptr_t) d->success); for (dm = d->musts; dm; dm = ndm) { ndm = dm->next; free(dm->must); free((ptr_t) dm); } } /* Having found the postfix representation of the regular expression, try to find a long sequence of characters that must appear in any line containing the r.e. Finding a "longest" sequence is beyond the scope here; we take an easy way out and hope for the best. (Take "(ab|a)b"--please.) We do a bottom-up calculation of sequences of characters that must appear in matches of r.e.'s represented by trees rooted at the nodes of the postfix representation: sequences that must appear at the left of the match ("left") sequences that must appear at the right of the match ("right") lists of sequences that must appear somewhere in the match ("in") sequences that must constitute the match ("is") When we get to the root of the tree, we use one of the longest of its calculated "in" sequences as our answer. The sequence we find is returned in d->must (where "d" is the single argument passed to "dfamust"); the length of the sequence is returned in d->mustn. The sequences calculated for the various types of node (in pseudo ANSI c) are shown below. "p" is the operand of unary operators (and the left-hand operand of binary operators); "q" is the right-hand operand of binary operators. "ZERO" means "a zero-length sequence" below. Type left right is in ---- ---- ----- -- -- char c # c # c # c # c ANYCHAR ZERO ZERO ZERO ZERO MBCSET ZERO ZERO ZERO ZERO CSET ZERO ZERO ZERO ZERO STAR ZERO ZERO ZERO ZERO QMARK ZERO ZERO ZERO ZERO PLUS p->left p->right ZERO p->in CAT (p->is==ZERO)? (q->is==ZERO)? (p->is!=ZERO && p->in plus p->left : q->right : q->is!=ZERO) ? q->in plus p->is##q->left p->right##q->is p->is##q->is : p->right##q->left ZERO OR longest common longest common (do p->is and substrings common to leading trailing q->is have same p->in and q->in (sub)sequence (sub)sequence length and of p->left of p->right content) ? and q->left and q->right p->is : NULL If there's anything else we recognize in the tree, all four sequences get set to zero-length sequences. If there's something we don't recognize in the tree, we just return a zero-length sequence. Break ties in favor of infrequent letters (choosing 'zzz' in preference to 'aaa')? And. . .is it here or someplace that we might ponder "optimizations" such as egrep 'psi|epsilon' -> egrep 'psi' egrep 'pepsi|epsilon' -> egrep 'epsi' (Yes, we now find "epsi" as a "string that must occur", but we might also simplify the *entire* r.e. being sought) grep '[c]' -> grep 'c' grep '(ab|a)b' -> grep 'ab' grep 'ab*' -> grep 'a' grep 'a*b' -> grep 'b' There are several issues: Is optimization easy (enough)? Does optimization actually accomplish anything, or is the automaton you get from "psi|epsilon" (for example) the same as the one you get from "psi" (for example)? Are optimizable r.e.'s likely to be used in real-life situations (something like 'ab*' is probably unlikely; something like is 'psi|epsilon' is likelier)? */ static char * icatalloc (char *old, char *new) { char *result; size_t oldsize, newsize; newsize = (new == NULL) ? 0 : strlen(new); if (old == NULL) oldsize = 0; else if (newsize == 0) return old; else oldsize = strlen(old); if (old == NULL) result = (char *) malloc(newsize + 1); else result = (char *) realloc((void *) old, oldsize + newsize + 1); if (result != NULL && new != NULL) (void) strcpy(result + oldsize, new); return result; } static char * icpyalloc (char *string) { return icatalloc((char *) NULL, string); } static char * istrstr (char *lookin, char *lookfor) { char *cp; size_t len; len = strlen(lookfor); for (cp = lookin; *cp != '\0'; ++cp) if (strncmp(cp, lookfor, len) == 0) return cp; return NULL; } static void ifree (char *cp) { if (cp != NULL) free(cp); } static void freelist (char **cpp) { int i; if (cpp == NULL) return; for (i = 0; cpp[i] != NULL; ++i) { free(cpp[i]); cpp[i] = NULL; } } static char ** enlist (char **cpp, char *new, size_t len) { int i, j; if (cpp == NULL) return NULL; if ((new = icpyalloc(new)) == NULL) { freelist(cpp); return NULL; } new[len] = '\0'; /* Is there already something in the list that's new (or longer)? */ for (i = 0; cpp[i] != NULL; ++i) if (istrstr(cpp[i], new) != NULL) { free(new); return cpp; } /* Eliminate any obsoleted strings. */ j = 0; while (cpp[j] != NULL) if (istrstr(new, cpp[j]) == NULL) ++j; else { free(cpp[j]); if (--i == j) break; cpp[j] = cpp[i]; cpp[i] = NULL; } /* Add the new string. */ cpp = (char **) realloc((char *) cpp, (i + 2) * sizeof *cpp); if (cpp == NULL) return NULL; cpp[i] = new; cpp[i + 1] = NULL; return cpp; } /* Given pointers to two strings, return a pointer to an allocated list of their distinct common substrings. Return NULL if something seems wild. */ static char ** comsubs (char *left, char *right) { char **cpp; char *lcp; char *rcp; size_t i, len; if (left == NULL || right == NULL) return NULL; cpp = (char **) malloc(sizeof *cpp); if (cpp == NULL) return NULL; cpp[0] = NULL; for (lcp = left; *lcp != '\0'; ++lcp) { len = 0; rcp = strchr (right, *lcp); while (rcp != NULL) { for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i) continue; if (i > len) len = i; rcp = strchr (rcp + 1, *lcp); } if (len == 0) continue; if ((cpp = enlist(cpp, lcp, len)) == NULL) break; } return cpp; } static char ** addlists (char **old, char **new) { int i; if (old == NULL || new == NULL) return NULL; for (i = 0; new[i] != NULL; ++i) { old = enlist(old, new[i], strlen(new[i])); if (old == NULL) break; } return old; } /* Given two lists of substrings, return a new list giving substrings common to both. */ static char ** inboth (char **left, char **right) { char **both; char **temp; int lnum, rnum; if (left == NULL || right == NULL) return NULL; both = (char **) malloc(sizeof *both); if (both == NULL) return NULL; both[0] = NULL; for (lnum = 0; left[lnum] != NULL; ++lnum) { for (rnum = 0; right[rnum] != NULL; ++rnum) { temp = comsubs(left[lnum], right[rnum]); if (temp == NULL) { freelist(both); return NULL; } both = addlists(both, temp); freelist(temp); free(temp); if (both == NULL) return NULL; } } return both; } typedef struct { char **in; char *left; char *right; char *is; } must; static void resetmust (must *mp) { mp->left[0] = mp->right[0] = mp->is[0] = '\0'; freelist(mp->in); } static void dfamust (struct dfa *dfa) { must *musts; must *mp; char *result; int ri; int i; int exact; token t; static must must0; struct dfamust *dm; static char empty_string[] = ""; result = empty_string; exact = 0; musts = (must *) malloc((dfa->tindex + 1) * sizeof *musts); if (musts == NULL) return; mp = musts; for (i = 0; i <= dfa->tindex; ++i) mp[i] = must0; for (i = 0; i <= dfa->tindex; ++i) { mp[i].in = (char **) malloc(sizeof *mp[i].in); mp[i].left = malloc(2); mp[i].right = malloc(2); mp[i].is = malloc(2); if (mp[i].in == NULL || mp[i].left == NULL || mp[i].right == NULL || mp[i].is == NULL) goto done; mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0'; mp[i].in[0] = NULL; } #ifdef DEBUG fprintf(stderr, "dfamust:\n"); for (i = 0; i < dfa->tindex; ++i) { fprintf(stderr, " %d:", i); prtok(dfa->tokens[i]); } putc('\n', stderr); #endif for (ri = 0; ri < dfa->tindex; ++ri) { switch (t = dfa->tokens[ri]) { case LPAREN: case RPAREN: goto done; /* "cannot happen" */ case EMPTY: case BEGLINE: case ENDLINE: case BEGWORD: case ENDWORD: case LIMWORD: case NOTLIMWORD: case BACKREF: resetmust(mp); break; case STAR: case QMARK: if (mp <= musts) goto done; /* "cannot happen" */ --mp; resetmust(mp); break; case OR: case ORTOP: if (mp < &musts[2]) goto done; /* "cannot happen" */ { char **new; must *lmp; must *rmp; int j, ln, rn, n; rmp = --mp; lmp = --mp; /* Guaranteed to be. Unlikely, but. . . */ if (strcmp(lmp->is, rmp->is) != 0) lmp->is[0] = '\0'; /* Left side--easy */ i = 0; while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i]) ++i; lmp->left[i] = '\0'; /* Right side */ ln = strlen(lmp->right); rn = strlen(rmp->right); n = ln; if (n > rn) n = rn; for (i = 0; i < n; ++i) if (lmp->right[ln - i - 1] != rmp->right[rn - i - 1]) break; for (j = 0; j < i; ++j) lmp->right[j] = lmp->right[(ln - i) + j]; lmp->right[j] = '\0'; new = inboth(lmp->in, rmp->in); if (new == NULL) goto done; freelist(lmp->in); free((char *) lmp->in); lmp->in = new; } break; case PLUS: if (mp <= musts) goto done; /* "cannot happen" */ --mp; mp->is[0] = '\0'; break; case END: if (mp != &musts[1]) goto done; /* "cannot happen" */ for (i = 0; musts[0].in[i] != NULL; ++i) if (strlen(musts[0].in[i]) > strlen(result)) result = musts[0].in[i]; if (strcmp(result, musts[0].is) == 0) exact = 1; goto done; case CAT: if (mp < &musts[2]) goto done; /* "cannot happen" */ { must *lmp; must *rmp; rmp = --mp; lmp = --mp; /* In. Everything in left, plus everything in right, plus catenation of left's right and right's left. */ lmp->in = addlists(lmp->in, rmp->in); if (lmp->in == NULL) goto done; if (lmp->right[0] != '\0' && rmp->left[0] != '\0') { char *tp; tp = icpyalloc(lmp->right); if (tp == NULL) goto done; tp = icatalloc(tp, rmp->left); if (tp == NULL) goto done; lmp->in = enlist(lmp->in, tp, strlen(tp)); free(tp); if (lmp->in == NULL) goto done; } /* Left-hand */ if (lmp->is[0] != '\0') { lmp->left = icatalloc(lmp->left, rmp->left); if (lmp->left == NULL) goto done; } /* Right-hand */ if (rmp->is[0] == '\0') lmp->right[0] = '\0'; lmp->right = icatalloc(lmp->right, rmp->right); if (lmp->right == NULL) goto done; /* Guaranteed to be */ if (lmp->is[0] != '\0' && rmp->is[0] != '\0') { lmp->is = icatalloc(lmp->is, rmp->is); if (lmp->is == NULL) goto done; } else lmp->is[0] = '\0'; } break; default: if (t < END) { /* "cannot happen" */ goto done; } else if (t == '\0') { /* not on *my* shift */ goto done; } else if (t >= CSET #ifdef MBS_SUPPORT || t == ANYCHAR || t == MBCSET #endif /* MBS_SUPPORT */ ) { /* easy enough */ resetmust(mp); } else { /* plain character */ resetmust(mp); mp->is[0] = mp->left[0] = mp->right[0] = t; mp->is[1] = mp->left[1] = mp->right[1] = '\0'; mp->in = enlist(mp->in, mp->is, (size_t)1); if (mp->in == NULL) goto done; } break; } #ifdef DEBUG fprintf(stderr, " node: %d:", ri); prtok(dfa->tokens[ri]); fprintf(stderr, "\n in:"); for (i = 0; mp->in[i]; ++i) fprintf(stderr, " \"%s\"", mp->in[i]); fprintf(stderr, "\n is: \"%s\"\n", mp->is); fprintf(stderr, " left: \"%s\"\n", mp->left); fprintf(stderr, " right: \"%s\"\n", mp->right); #endif ++mp; } done: if (strlen(result)) { dm = (struct dfamust *) malloc(sizeof (struct dfamust)); dm->exact = exact; dm->must = malloc(strlen(result) + 1); strcpy(dm->must, result); dm->next = dfa->musts; dfa->musts = dm; } mp = musts; for (i = 0; i <= dfa->tindex; ++i) { freelist(mp[i].in); ifree((char *) mp[i].in); ifree(mp[i].left); ifree(mp[i].right); ifree(mp[i].is); } free((char *) mp); } /* vim:set shiftwidth=2: */ Index: stable/9/gnu/usr.bin/grep/grep.c =================================================================== --- stable/9/gnu/usr.bin/grep/grep.c (revision 250821) +++ stable/9/gnu/usr.bin/grep/grep.c (revision 250822) @@ -1,1861 +1,1861 @@ /* grep.c - main driver file for grep. Copyright 1992, 1997-1999, 2000 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /* Written July 1992 by Mike Haertel. */ /* Builtin decompression 1997 by Wolfram Schneider . */ /* $FreeBSD$ */ #ifdef HAVE_CONFIG_H # include #endif #include #include #if defined(HAVE_MMAP) # include #endif #if defined(HAVE_SETRLIMIT) # include # include #endif #if defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H && defined HAVE_MBRTOWC /* We can handle multibyte string. */ # define MBS_SUPPORT # include # include #endif #include #include "system.h" #include "getopt.h" #include "getpagesize.h" #include "grep.h" #include "savedir.h" #include "xstrtol.h" #include "xalloc.h" #include "error.h" #include "exclude.h" #include "closeout.h" #undef MAX #define MAX(A,B) ((A) > (B) ? (A) : (B)) struct stats { struct stats const *parent; struct stat stat; }; /* base of chain of stat buffers, used to detect directory loops */ static struct stats stats_base; /* if non-zero, display usage information and exit */ static int show_help; /* If non-zero, print the version on standard output and exit. */ static int show_version; /* If nonzero, suppress diagnostics for nonexistent or unreadable files. */ static int suppress_errors; /* If nonzero, use mmap if possible. */ static int mmap_option; /* If zero, output nulls after filenames. */ static int filename_mask; /* If nonzero, use grep_color marker. */ static int color_option; /* If nonzero, show only the part of a line matching the expression. */ static int only_matching; /* The color string used. The user can overwrite it using the environment variable GREP_COLOR. The default is to print red. */ static const char *grep_color = "01;31"; static struct exclude *excluded_patterns; static struct exclude *included_patterns; /* Short options. */ static char const short_options[] = "0123456789A:B:C:D:EFGHIJPUVX:abcd:e:f:hiKLlm:noqRrsuvwxyZz"; /* Non-boolean long options that have no corresponding short equivalents. */ enum { BINARY_FILES_OPTION = CHAR_MAX + 1, COLOR_OPTION, INCLUDE_OPTION, EXCLUDE_OPTION, EXCLUDE_FROM_OPTION, LINE_BUFFERED_OPTION, LABEL_OPTION }; /* Long options equivalences. */ static struct option const long_options[] = { {"after-context", required_argument, NULL, 'A'}, {"basic-regexp", no_argument, NULL, 'G'}, {"before-context", required_argument, NULL, 'B'}, {"binary-files", required_argument, NULL, BINARY_FILES_OPTION}, {"byte-offset", no_argument, NULL, 'b'}, {"context", required_argument, NULL, 'C'}, {"color", optional_argument, NULL, COLOR_OPTION}, {"colour", optional_argument, NULL, COLOR_OPTION}, {"count", no_argument, NULL, 'c'}, {"devices", required_argument, NULL, 'D'}, {"directories", required_argument, NULL, 'd'}, {"extended-regexp", no_argument, NULL, 'E'}, {"exclude", required_argument, NULL, EXCLUDE_OPTION}, {"exclude-from", required_argument, NULL, EXCLUDE_FROM_OPTION}, {"file", required_argument, NULL, 'f'}, {"files-with-matches", no_argument, NULL, 'l'}, {"files-without-match", no_argument, NULL, 'L'}, {"fixed-regexp", no_argument, NULL, 'F'}, {"fixed-strings", no_argument, NULL, 'F'}, {"help", no_argument, &show_help, 1}, {"include", required_argument, NULL, INCLUDE_OPTION}, {"ignore-case", no_argument, NULL, 'i'}, {"label", required_argument, NULL, LABEL_OPTION}, {"line-buffered", no_argument, NULL, LINE_BUFFERED_OPTION}, {"line-number", no_argument, NULL, 'n'}, {"line-regexp", no_argument, NULL, 'x'}, {"max-count", required_argument, NULL, 'm'}, {"mmap", no_argument, &mmap_option, 1}, {"no-filename", no_argument, NULL, 'h'}, {"no-messages", no_argument, NULL, 's'}, {"bz2decompress", no_argument, NULL, 'J'}, #if HAVE_LIBZ > 0 {"decompress", no_argument, NULL, 'Z'}, {"null", no_argument, &filename_mask, 0}, #else {"null", no_argument, NULL, 'Z'}, #endif {"null-data", no_argument, NULL, 'z'}, {"only-matching", no_argument, NULL, 'o'}, {"perl-regexp", no_argument, NULL, 'P'}, {"quiet", no_argument, NULL, 'q'}, {"recursive", no_argument, NULL, 'r'}, {"recursive", no_argument, NULL, 'R'}, {"regexp", required_argument, NULL, 'e'}, {"invert-match", no_argument, NULL, 'v'}, {"silent", no_argument, NULL, 'q'}, {"text", no_argument, NULL, 'a'}, {"binary", no_argument, NULL, 'U'}, {"unix-byte-offsets", no_argument, NULL, 'u'}, {"version", no_argument, NULL, 'V'}, {"with-filename", no_argument, NULL, 'H'}, {"word-regexp", no_argument, NULL, 'w'}, {0, 0, 0, 0} }; /* Define flags declared in grep.h. */ int match_icase; int match_words; int match_lines; unsigned char eolbyte; /* For error messages. */ /* The name the program was run with, stripped of any leading path. */ char *program_name; static char const *filename; static int errseen; /* How to handle directories. */ static enum { READ_DIRECTORIES, RECURSE_DIRECTORIES, SKIP_DIRECTORIES } directories = READ_DIRECTORIES; /* How to handle devices. */ static enum { READ_DEVICES, SKIP_DEVICES } devices = READ_DEVICES; static int grepdir PARAMS ((char const *, struct stats const *)); #if defined(HAVE_DOS_FILE_CONTENTS) static inline int undossify_input PARAMS ((register char *, size_t)); #endif /* Functions we'll use to search. */ static void (*compile) PARAMS ((char const *, size_t)); static size_t (*execute) PARAMS ((char const *, size_t, size_t *, int)); /* Like error, but suppress the diagnostic if requested. */ static void suppressible_error (char const *mesg, int errnum) { if (! suppress_errors) error (0, errnum, "%s", mesg); errseen = 1; } /* Convert STR to a positive integer, storing the result in *OUT. STR must be a valid context length argument; report an error if it isn't. */ static void context_length_arg (char const *str, int *out) { uintmax_t value; if (! (xstrtoumax (str, 0, 10, &value, "") == LONGINT_OK && 0 <= (*out = value) && *out == value)) { error (2, 0, "%s: %s\n", str, _("invalid context length argument")); } } /* Hairy buffering mechanism for grep. The intent is to keep all reads aligned on a page boundary and multiples of the page size, unless a read yields a partial page. */ static char *buffer; /* Base of buffer. */ static size_t bufalloc; /* Allocated buffer size, counting slop. */ #define INITIAL_BUFSIZE 32768 /* Initial buffer size, not counting slop. */ static int bufdesc; /* File descriptor. */ static char *bufbeg; /* Beginning of user-visible stuff. */ static char *buflim; /* Limit of user-visible stuff. */ static size_t pagesize; /* alignment of memory pages */ static off_t bufoffset; /* Read offset; defined on regular files. */ static off_t after_last_match; /* Pointer after last matching line that would have been output if we were outputting characters. */ #if defined(HAVE_MMAP) static int bufmapped; /* True if buffer is memory-mapped. */ static off_t initial_bufoffset; /* Initial value of bufoffset. */ #else # define bufmapped 0 #endif #include static BZFILE* bzbufdesc; /* libbz2 file handle. */ static int BZflag; /* uncompress before searching. */ #if HAVE_LIBZ > 0 #include static gzFile gzbufdesc; /* zlib file descriptor. */ static int Zflag; /* uncompress before searching. */ #endif /* Return VAL aligned to the next multiple of ALIGNMENT. VAL can be an integer or a pointer. Both args must be free of side effects. */ #define ALIGN_TO(val, alignment) \ ((size_t) (val) % (alignment) == 0 \ ? (val) \ : (val) + ((alignment) - (size_t) (val) % (alignment))) /* Reset the buffer for a new file, returning zero if we should skip it. Initialize on the first time through. */ static int reset (int fd, char const *file, struct stats *stats) { if (! pagesize) { pagesize = getpagesize (); if (pagesize == 0 || 2 * pagesize + 1 <= pagesize) abort (); bufalloc = ALIGN_TO (INITIAL_BUFSIZE, pagesize) + pagesize + 1; buffer = xmalloc (bufalloc); } if (BZflag) { bzbufdesc = BZ2_bzdopen(fd, "r"); if (bzbufdesc == NULL) error(2, 0, _("memory exhausted")); } #if HAVE_LIBZ > 0 if (Zflag) { gzbufdesc = gzdopen(fd, "r"); if (gzbufdesc == NULL) error(2, 0, _("memory exhausted")); } #endif bufbeg = buflim = ALIGN_TO (buffer + 1, pagesize); bufbeg[-1] = eolbyte; bufdesc = fd; if (fstat (fd, &stats->stat) != 0) { error (0, errno, "fstat"); return 0; } if (directories == SKIP_DIRECTORIES && S_ISDIR (stats->stat.st_mode)) return 0; #ifndef DJGPP if (devices == SKIP_DEVICES && (S_ISCHR(stats->stat.st_mode) || S_ISBLK(stats->stat.st_mode) || S_ISSOCK(stats->stat.st_mode))) #else if (devices == SKIP_DEVICES && (S_ISCHR(stats->stat.st_mode) || S_ISBLK(stats->stat.st_mode))) #endif return 0; if ( BZflag || #if HAVE_LIBZ > 0 Zflag || #endif S_ISREG (stats->stat.st_mode)) { if (file) bufoffset = 0; else { bufoffset = lseek (fd, 0, SEEK_CUR); if (bufoffset < 0) { error (0, errno, "lseek"); return 0; } } #if defined(HAVE_MMAP) initial_bufoffset = bufoffset; bufmapped = mmap_option && bufoffset % pagesize == 0; #endif } else { #if defined(HAVE_MMAP) bufmapped = 0; #endif } return 1; } /* Read new stuff into the buffer, saving the specified amount of old stuff. When we're done, 'bufbeg' points to the beginning of the buffer contents, and 'buflim' points just after the end. Return zero if there's an error. */ static int fillbuf (size_t save, struct stats const *stats) { size_t fillsize = 0; int cc = 1; char *readbuf; size_t readsize; /* Offset from start of buffer to start of old stuff that we want to save. */ size_t saved_offset = buflim - save - buffer; if (pagesize <= buffer + bufalloc - buflim) { readbuf = buflim; bufbeg = buflim - save; } else { size_t minsize = save + pagesize; size_t newsize; size_t newalloc; char *newbuf; /* Grow newsize until it is at least as great as minsize. */ for (newsize = bufalloc - pagesize - 1; newsize < minsize; newsize *= 2) if (newsize * 2 < newsize || newsize * 2 + pagesize + 1 < newsize * 2) xalloc_die (); /* Try not to allocate more memory than the file size indicates, as that might cause unnecessary memory exhaustion if the file is large. However, do not use the original file size as a heuristic if we've already read past the file end, as most likely the file is growing. */ if (S_ISREG (stats->stat.st_mode)) { off_t to_be_read = stats->stat.st_size - bufoffset; off_t maxsize_off = save + to_be_read; if (0 <= to_be_read && to_be_read <= maxsize_off && maxsize_off == (size_t) maxsize_off && minsize <= (size_t) maxsize_off && (size_t) maxsize_off < newsize) newsize = maxsize_off; } /* Add enough room so that the buffer is aligned and has room for byte sentinels fore and aft. */ newalloc = newsize + pagesize + 1; newbuf = bufalloc < newalloc ? xmalloc (bufalloc = newalloc) : buffer; readbuf = ALIGN_TO (newbuf + 1 + save, pagesize); bufbeg = readbuf - save; memmove (bufbeg, buffer + saved_offset, save); bufbeg[-1] = eolbyte; if (newbuf != buffer) { free (buffer); buffer = newbuf; } } readsize = buffer + bufalloc - readbuf; readsize -= readsize % pagesize; #if defined(HAVE_MMAP) if (bufmapped) { size_t mmapsize = readsize; /* Don't mmap past the end of the file; some hosts don't allow this. Use `read' on the last page. */ if (stats->stat.st_size - bufoffset < mmapsize) { mmapsize = stats->stat.st_size - bufoffset; mmapsize -= mmapsize % pagesize; } if (mmapsize && (mmap ((caddr_t) readbuf, mmapsize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_FIXED, bufdesc, bufoffset) != (caddr_t) -1)) { /* Do not bother to use madvise with MADV_SEQUENTIAL or MADV_WILLNEED on the mmapped memory. One might think it would help, but it slows us down about 30% on SunOS 4.1. */ fillsize = mmapsize; } else { /* Stop using mmap on this file. Synchronize the file offset. Do not warn about mmap failures. On some hosts (e.g. Solaris 2.5) mmap can fail merely because some other process has an advisory read lock on the file. There's no point alarming the user about this misfeature. */ bufmapped = 0; if (bufoffset != initial_bufoffset && lseek (bufdesc, bufoffset, SEEK_SET) < 0) { error (0, errno, "lseek"); cc = 0; } } } #endif /*HAVE_MMAP*/ if (! fillsize) { ssize_t bytesread; do if (BZflag && bzbufdesc) { int bzerr; bytesread = BZ2_bzRead (&bzerr, bzbufdesc, readbuf, readsize); switch (bzerr) { case BZ_OK: case BZ_STREAM_END: /* ok */ break; case BZ_DATA_ERROR_MAGIC: BZ2_bzReadClose (&bzerr, bzbufdesc); bzbufdesc = NULL; lseek (bufdesc, 0, SEEK_SET); bytesread = read (bufdesc, readbuf, readsize); break; default: bytesread = 0; break; } } else #if HAVE_LIBZ > 0 if (Zflag) bytesread = gzread (gzbufdesc, readbuf, readsize); else #endif bytesread = read (bufdesc, readbuf, readsize); while (bytesread < 0 && errno == EINTR); if (bytesread < 0) cc = 0; else fillsize = bytesread; } bufoffset += fillsize; #if defined(HAVE_DOS_FILE_CONTENTS) if (fillsize) fillsize = undossify_input (readbuf, fillsize); #endif buflim = readbuf + fillsize; return cc; } /* Flags controlling the style of output. */ static enum { BINARY_BINARY_FILES, TEXT_BINARY_FILES, WITHOUT_MATCH_BINARY_FILES } binary_files; /* How to handle binary files. */ static int filename_mask; /* If zero, output nulls after filenames. */ static int out_quiet; /* Suppress all normal output. */ static int out_invert; /* Print nonmatching stuff. */ static int out_file; /* Print filenames. */ static int out_line; /* Print line numbers. */ static int out_byte; /* Print byte offsets. */ static int out_before; /* Lines of leading context. */ static int out_after; /* Lines of trailing context. */ static int count_matches; /* Count matching lines. */ static int list_files; /* List matching files. */ static int no_filenames; /* Suppress file names. */ static off_t max_count; /* Stop after outputting this many lines from an input file. */ static int line_buffered; /* If nonzero, use line buffering, i.e. fflush everyline out. */ static char *label = NULL; /* Fake filename for stdin */ /* Internal variables to keep track of byte count, context, etc. */ static uintmax_t totalcc; /* Total character count before bufbeg. */ static char const *lastnl; /* Pointer after last newline counted. */ static char const *lastout; /* Pointer after last character output; NULL if no character has been output or if it's conceptually before bufbeg. */ static uintmax_t totalnl; /* Total newline count before lastnl. */ static off_t outleft; /* Maximum number of lines to be output. */ static int pending; /* Pending lines of output. Always kept 0 if out_quiet is true. */ static int done_on_match; /* Stop scanning file on first match. */ static int exit_on_match; /* Exit on first match. */ #if defined(HAVE_DOS_FILE_CONTENTS) # include "dosbuf.c" #endif /* Add two numbers that count input bytes or lines, and report an error if the addition overflows. */ static uintmax_t add_count (uintmax_t a, uintmax_t b) { uintmax_t sum = a + b; if (sum < a) error (2, 0, _("input is too large to count")); return sum; } static void nlscan (char const *lim) { size_t newlines = 0; char const *beg; for (beg = lastnl; beg != lim; beg = memchr (beg, eolbyte, lim - beg), beg++) newlines++; totalnl = add_count (totalnl, newlines); lastnl = lim; } /* Print a byte offset, followed by a character separator. */ static void print_offset_sep (uintmax_t pos, char sep) { /* Do not rely on printf to print pos, since uintmax_t may be longer than long, and long long is not portable. */ char buf[sizeof pos * CHAR_BIT]; char *p = buf + sizeof buf - 1; *p = sep; do *--p = '0' + pos % 10; while ((pos /= 10) != 0); fwrite (p, 1, buf + sizeof buf - p, stdout); } static void prline (char const *beg, char const *lim, int sep) { if (out_file) printf ("%s%c", filename, sep & filename_mask); if (out_line) { nlscan (beg); totalnl = add_count (totalnl, 1); print_offset_sep (totalnl, sep); lastnl = lim; } if (out_byte) { uintmax_t pos = add_count (totalcc, beg - bufbeg); #if defined(HAVE_DOS_FILE_CONTENTS) pos = dossified_pos (pos); #endif print_offset_sep (pos, sep); } if (only_matching) { size_t match_size; size_t match_offset; while ((match_offset = (*execute) (beg, lim - beg, &match_size, 1)) != (size_t) -1) { char const *b = beg + match_offset; if (b == lim) break; if (match_size == 0) break; if(color_option) printf("\33[%sm", grep_color); fwrite(b, sizeof (char), match_size, stdout); if(color_option) fputs("\33[00m", stdout); fputs("\n", stdout); beg = b + match_size; } lastout = lim; if(line_buffered) fflush(stdout); return; } if (color_option) { size_t match_size; size_t match_offset; while (lim-beg && (match_offset = (*execute) (beg, lim - beg, &match_size, 1)) != (size_t) -1) { char const *b = beg + match_offset; /* Avoid matching the empty line at the end of the buffer. */ if (b == lim) break; /* Avoid hanging on grep --color "" foo */ if (match_size == 0) break; fwrite (beg, sizeof (char), match_offset, stdout); printf ("\33[%sm", grep_color); fwrite (b, sizeof (char), match_size, stdout); fputs ("\33[00m", stdout); beg = b + match_size; } fputs ("\33[K", stdout); } fwrite (beg, 1, lim - beg, stdout); if (ferror (stdout)) error (0, errno, _("writing output")); lastout = lim; if (line_buffered) fflush (stdout); } /* Print pending lines of trailing context prior to LIM. Trailing context ends at the next matching line when OUTLEFT is 0. */ static void prpending (char const *lim) { if (!lastout) lastout = bufbeg; while (pending > 0 && lastout < lim) { char const *nl = memchr (lastout, eolbyte, lim - lastout); size_t match_size; --pending; if (outleft || (((*execute) (lastout, nl - lastout, &match_size, 0) == (size_t) -1) == !out_invert)) prline (lastout, nl + 1, '-'); else pending = 0; } } /* Print the lines between BEG and LIM. Deal with context crap. If NLINESP is non-null, store a count of lines between BEG and LIM. */ static void prtext (char const *beg, char const *lim, int *nlinesp) { static int used; /* avoid printing "--" before any output */ char const *bp, *p; char eol = eolbyte; int i, n; if (!out_quiet && pending > 0) prpending (beg); p = beg; if (!out_quiet) { /* Deal with leading context crap. */ bp = lastout ? lastout : bufbeg; for (i = 0; i < out_before; ++i) if (p > bp) do --p; while (p[-1] != eol); /* We only print the "--" separator if our output is discontiguous from the last output in the file. */ if ((out_before || out_after) && used && p != lastout) puts ("--"); while (p < beg) { char const *nl = memchr (p, eol, beg - p); nl++; prline (p, nl, '-'); p = nl; } } if (nlinesp) { /* Caller wants a line count. */ for (n = 0; p < lim && n < outleft; n++) { char const *nl = memchr (p, eol, lim - p); nl++; if (!out_quiet) prline (p, nl, ':'); p = nl; } *nlinesp = n; /* relying on it that this function is never called when outleft = 0. */ after_last_match = bufoffset - (buflim - p); } else if (!out_quiet) prline (beg, lim, ':'); pending = out_quiet ? 0 : out_after; used = 1; } /* Scan the specified portion of the buffer, matching lines (or between matching lines if OUT_INVERT is true). Return a count of lines printed. */ static int grepbuf (char const *beg, char const *lim) { int nlines, n; register char const *p; size_t match_offset; size_t match_size; nlines = 0; p = beg; while ((match_offset = (*execute) (p, lim - p, &match_size, 0)) != (size_t) -1) { char const *b = p + match_offset; char const *endp = b + match_size; /* Avoid matching the empty line at the end of the buffer. */ if (b == lim) break; if (!out_invert) { prtext (b, endp, (int *) 0); nlines++; outleft--; if (!outleft || done_on_match) { if (exit_on_match) exit (0); after_last_match = bufoffset - (buflim - endp); return nlines; } } else if (p < b) { prtext (p, b, &n); nlines += n; outleft -= n; if (!outleft) return nlines; } p = endp; } if (out_invert && p < lim) { prtext (p, lim, &n); nlines += n; outleft -= n; } return nlines; } /* Search a given file. Normally, return a count of lines printed; but if the file is a directory and we search it recursively, then return -2 if there was a match, and -1 otherwise. */ static int grep (int fd, char const *file, struct stats *stats) { int nlines, i; int not_text; size_t residue, save; char oldc; char *beg; char *lim; char eol = eolbyte; if (!reset (fd, file, stats)) return 0; if (file && directories == RECURSE_DIRECTORIES && S_ISDIR (stats->stat.st_mode)) { /* Close fd now, so that we don't open a lot of file descriptors when we recurse deeply. */ if (BZflag && bzbufdesc) BZ2_bzclose(bzbufdesc); else #if HAVE_LIBZ > 0 if (Zflag) gzclose(gzbufdesc); else #endif if (close (fd) != 0) error (0, errno, "%s", file); return grepdir (file, stats) - 2; } totalcc = 0; lastout = 0; totalnl = 0; outleft = max_count; after_last_match = 0; pending = 0; nlines = 0; residue = 0; save = 0; if (! fillbuf (save, stats)) { if (! is_EISDIR (errno, file)) suppressible_error (filename, errno); return 0; } not_text = (((binary_files == BINARY_BINARY_FILES && !out_quiet) || binary_files == WITHOUT_MATCH_BINARY_FILES) && memchr (bufbeg, eol ? '\0' : '\200', buflim - bufbeg)); if (not_text && binary_files == WITHOUT_MATCH_BINARY_FILES) return 0; done_on_match += not_text; out_quiet += not_text; for (;;) { lastnl = bufbeg; if (lastout) lastout = bufbeg; beg = bufbeg + save; /* no more data to scan (eof) except for maybe a residue -> break */ if (beg == buflim) break; /* Determine new residue (the length of an incomplete line at the end of the buffer, 0 means there is no incomplete last line). */ oldc = beg[-1]; beg[-1] = eol; for (lim = buflim; lim[-1] != eol; lim--) continue; beg[-1] = oldc; if (lim == beg) lim = beg - residue; beg -= residue; residue = buflim - lim; if (beg < lim) { if (outleft) nlines += grepbuf (beg, lim); if (pending) prpending (lim); if((!outleft && !pending) || (nlines && done_on_match && !out_invert)) goto finish_grep; } /* The last OUT_BEFORE lines at the end of the buffer will be needed as leading context if there is a matching line at the begin of the next data. Make beg point to their begin. */ i = 0; beg = lim; while (i < out_before && beg > bufbeg && beg != lastout) { ++i; do --beg; while (beg[-1] != eol); } /* detect if leading context is discontinuous from last printed line. */ if (beg != lastout) lastout = 0; /* Handle some details and read more data to scan. */ save = residue + lim - beg; if (out_byte) totalcc = add_count (totalcc, buflim - bufbeg - save); if (out_line) nlscan (beg); if (! fillbuf (save, stats)) { if (! is_EISDIR (errno, file)) suppressible_error (filename, errno); goto finish_grep; } } if (residue) { *buflim++ = eol; if (outleft) nlines += grepbuf (bufbeg + save - residue, buflim); if (pending) prpending (buflim); } finish_grep: done_on_match -= not_text; out_quiet -= not_text; if ((not_text & ~out_quiet) && nlines != 0) printf (_("Binary file %s matches\n"), filename); return nlines; } static int grepfile (char const *file, struct stats *stats) { int desc; int count; int status; if (! file) { desc = 0; filename = label ? label : _("(standard input)"); } else { while ((desc = open (file, O_RDONLY)) < 0 && errno == EINTR) continue; if (desc < 0) { int e = errno; if (is_EISDIR (e, file) && directories == RECURSE_DIRECTORIES) { if (stat (file, &stats->stat) != 0) { error (0, errno, "%s", file); return 1; } return grepdir (file, stats); } if (!suppress_errors) { if (directories == SKIP_DIRECTORIES) switch (e) { #if defined(EISDIR) case EISDIR: return 1; #endif case EACCES: /* When skipping directories, don't worry about directories that can't be opened. */ if (isdir (file)) return 1; break; } } suppressible_error (file, e); return 1; } filename = file; } #if defined(SET_BINARY) /* Set input to binary mode. Pipes are simulated with files on DOS, so this includes the case of "foo | grep bar". */ if (!isatty (desc)) SET_BINARY (desc); #endif count = grep (desc, file, stats); if (count < 0) status = count + 2; else { if (count_matches) { if (out_file) printf ("%s%c", filename, ':' & filename_mask); printf ("%d\n", count); } status = !count; if (list_files == 1 - 2 * status) printf ("%s%c", filename, '\n' & filename_mask); if (BZflag && bzbufdesc) BZ2_bzclose(bzbufdesc); else #if HAVE_LIBZ > 0 if (Zflag) gzclose(gzbufdesc); else #endif if (! file) { off_t required_offset = outleft ? bufoffset : after_last_match; if ((bufmapped || required_offset != bufoffset) && lseek (desc, required_offset, SEEK_SET) < 0 && S_ISREG (stats->stat.st_mode)) error (0, errno, "%s", filename); } else while (close (desc) != 0) if (errno != EINTR) { error (0, errno, "%s", file); break; } } return status; } static int grepdir (char const *dir, struct stats const *stats) { int status = 1; struct stats const *ancestor; char *name_space; /* Mingw32 does not support st_ino. No known working hosts use zero for st_ino, so assume that the Mingw32 bug applies if it's zero. */ if (stats->stat.st_ino) for (ancestor = stats; (ancestor = ancestor->parent) != 0; ) if (ancestor->stat.st_ino == stats->stat.st_ino && ancestor->stat.st_dev == stats->stat.st_dev) { if (!suppress_errors) error (0, 0, _("warning: %s: %s"), dir, _("recursive directory loop")); return 1; } name_space = savedir (dir, stats->stat.st_size, included_patterns, excluded_patterns); if (! name_space) { if (errno) suppressible_error (dir, errno); else xalloc_die (); } else { size_t dirlen = strlen (dir); int needs_slash = ! (dirlen == FILESYSTEM_PREFIX_LEN (dir) || IS_SLASH (dir[dirlen - 1])); char *file = NULL; char const *namep = name_space; struct stats child; child.parent = stats; out_file += !no_filenames; while (*namep) { size_t namelen = strlen (namep); file = xrealloc (file, dirlen + 1 + namelen + 1); strcpy (file, dir); file[dirlen] = '/'; strcpy (file + dirlen + needs_slash, namep); namep += namelen + 1; status &= grepfile (file, &child); } out_file -= !no_filenames; if (file) free (file); free (name_space); } return status; } static void usage (int status) { if (status != 0) { fprintf (stderr, _("Usage: %s [OPTION]... PATTERN [FILE]...\n"), program_name); fprintf (stderr, _("Try `%s --help' for more information.\n"), program_name); } else { printf (_("Usage: %s [OPTION]... PATTERN [FILE] ...\n"), program_name); printf (_("\ Search for PATTERN in each FILE or standard input.\n\ Example: %s -i 'hello world' menu.h main.c\n\ \n\ Regexp selection and interpretation:\n"), program_name); printf (_("\ -E, --extended-regexp PATTERN is an extended regular expression\n\ -F, --fixed-strings PATTERN is a set of newline-separated strings\n\ -G, --basic-regexp PATTERN is a basic regular expression\n\ -P, --perl-regexp PATTERN is a Perl regular expression\n")); printf (_("\ -e, --regexp=PATTERN use PATTERN as a regular expression\n\ -f, --file=FILE obtain PATTERN from FILE\n\ -i, --ignore-case ignore case distinctions\n\ -w, --word-regexp force PATTERN to match only whole words\n\ -x, --line-regexp force PATTERN to match only whole lines\n\ -z, --null-data a data line ends in 0 byte, not newline\n")); printf (_("\ \n\ Miscellaneous:\n\ -s, --no-messages suppress error messages\n\ -v, --invert-match select non-matching lines\n\ -V, --version print version information and exit\n\ --help display this help and exit\n\ -J, --bz2decompress decompress bzip2'ed input before searching\n\ -Z, --decompress decompress input before searching (HAVE_LIBZ=1)\n\ --mmap use memory-mapped input if possible\n")); printf (_("\ \n\ Output control:\n\ -m, --max-count=NUM stop after NUM matches\n\ -b, --byte-offset print the byte offset with output lines\n\ -n, --line-number print line number with output lines\n\ --line-buffered flush output on every line\n\ -H, --with-filename print the filename for each match\n\ -h, --no-filename suppress the prefixing filename on output\n\ --label=LABEL print LABEL as filename for standard input\n\ -o, --only-matching show only the part of a line matching PATTERN\n\ -q, --quiet, --silent suppress all normal output\n\ --binary-files=TYPE assume that binary files are TYPE\n\ TYPE is 'binary', 'text', or 'without-match'\n\ -a, --text equivalent to --binary-files=text\n\ -I equivalent to --binary-files=without-match\n\ -d, --directories=ACTION how to handle directories\n\ ACTION is 'read', 'recurse', or 'skip'\n\ -D, --devices=ACTION how to handle devices, FIFOs and sockets\n\ ACTION is 'read' or 'skip'\n\ -R, -r, --recursive equivalent to --directories=recurse\n\ --include=PATTERN files that match PATTERN will be examined\n\ --exclude=PATTERN files that match PATTERN will be skipped.\n\ --exclude-from=FILE files that match PATTERN in FILE will be skipped.\n\ -L, --files-without-match only print FILE names containing no match\n\ -l, --files-with-matches only print FILE names containing matches\n\ -c, --count only print a count of matching lines per FILE\n\ --null print 0 byte after FILE name\n")); printf (_("\ \n\ Context control:\n\ -B, --before-context=NUM print NUM lines of leading context\n\ -A, --after-context=NUM print NUM lines of trailing context\n\ -C, --context=NUM print NUM lines of output context\n\ -NUM same as --context=NUM\n\ --color[=WHEN],\n\ --colour[=WHEN] use markers to distinguish the matching string\n\ WHEN may be `always', `never' or `auto'.\n\ -U, --binary do not strip CR characters at EOL (MSDOS)\n\ -u, --unix-byte-offsets report offsets as if CRs were not there (MSDOS)\n\ \n\ `egrep' means `grep -E'. `fgrep' means `grep -F'.\n\ With no FILE, or when FILE is -, read standard input. If less than\n\ two FILEs given, assume -h. Exit status is 0 if match, 1 if no match,\n\ and 2 if trouble.\n")); printf (_("\nReport bugs to .\n")); } exit (status); } /* Set the matcher to M, reporting any conflicts. */ static void setmatcher (char const *m) { if (matcher && strcmp (matcher, m) != 0) error (2, 0, _("conflicting matchers specified")); matcher = m; } /* Go through the matchers vector and look for the specified matcher. If we find it, install it in compile and execute, and return 1. */ static int install_matcher (char const *name) { int i; #if defined(HAVE_SETRLIMIT) struct rlimit rlim; #endif for (i = 0; matchers[i].compile; i++) if (strcmp (name, matchers[i].name) == 0) { compile = matchers[i].compile; execute = matchers[i].execute; #if defined(HAVE_SETRLIMIT) && defined(RLIMIT_STACK) /* I think every platform needs to do this, so that regex.c doesn't oveflow the stack. The default value of `re_max_failures' is too large for some platforms: it needs more than 3MB-large stack. The test for HAVE_SETRLIMIT should go into `configure'. */ if (!getrlimit (RLIMIT_STACK, &rlim)) { long newlim; extern long int re_max_failures; /* from regex.c */ /* Approximate the amount regex.c needs, plus some more. */ newlim = re_max_failures * 2 * 20 * sizeof (char *); if (newlim > rlim.rlim_max) { newlim = rlim.rlim_max; re_max_failures = newlim / (2 * 20 * sizeof (char *)); } if (rlim.rlim_cur < newlim) { rlim.rlim_cur = newlim; setrlimit (RLIMIT_STACK, &rlim); } } #endif return 1; } return 0; } /* Find the white-space-separated options specified by OPTIONS, and using BUF to store copies of these options, set ARGV[0], ARGV[1], etc. to the option copies. Return the number N of options found. Do not set ARGV[N] to NULL. If ARGV is NULL, do not store ARGV[0] etc. Backslash can be used to escape whitespace (and backslashes). */ static int prepend_args (char const *options, char *buf, char **argv) { char const *o = options; char *b = buf; int n = 0; for (;;) { while (ISSPACE ((unsigned char) *o)) o++; if (!*o) return n; if (argv) argv[n] = b; n++; do if ((*b++ = *o++) == '\\' && *o) b[-1] = *o++; while (*o && ! ISSPACE ((unsigned char) *o)); *b++ = '\0'; } } /* Prepend the whitespace-separated options in OPTIONS to the argument vector of a main program with argument count *PARGC and argument vector *PARGV. */ static void prepend_default_options (char const *options, int *pargc, char ***pargv) { if (options) { char *buf = xmalloc (strlen (options) + 1); int prepended = prepend_args (options, buf, (char **) NULL); int argc = *pargc; char * const *argv = *pargv; char **pp = (char **) xmalloc ((prepended + argc + 1) * sizeof *pp); *pargc = prepended + argc; *pargv = pp; *pp++ = *argv++; pp += prepend_args (options, buf, pp); while ((*pp++ = *argv++)) continue; } } /* Get the next non-digit option from ARGC and ARGV. Return -1 if there are no more options. Process any digit options that were encountered on the way, and store the resulting integer into *DEFAULT_CONTEXT. */ static int get_nondigit_option (int argc, char *const *argv, int *default_context) { int opt; char buf[sizeof (uintmax_t) * CHAR_BIT + 4]; char *p = buf; /* Set buf[0] to anything but '0', for the leading-zero test below. */ buf[0] = '\0'; while (opt = getopt_long (argc, argv, short_options, long_options, NULL), '0' <= opt && opt <= '9') { /* Suppress trivial leading zeros, to avoid incorrect diagnostic on strings like 00000000000. */ p -= buf[0] == '0'; *p++ = opt; if (p == buf + sizeof buf - 4) { /* Too many digits. Append "..." to make context_length_arg complain about "X...", where X contains the digits seen so far. */ strcpy (p, "..."); p += 3; break; } } if (p != buf) { *p = '\0'; context_length_arg (buf, default_context); } return opt; } int main (int argc, char **argv) { char *keys; - size_t cc, keycc, oldcc, keyalloc; + size_t keycc, oldcc, keyalloc; int with_filenames; - int opt, status; + int opt, cc, status; int default_context; FILE *fp; extern char *optarg; extern int optind; initialize_main (&argc, &argv); program_name = argv[0]; if (program_name && strrchr (program_name, '/')) program_name = strrchr (program_name, '/') + 1; if (program_name[0] == 'b' && program_name[1] == 'z') { BZflag = 1; program_name += 2; } #if HAVE_LIBZ > 0 else if (program_name[0] == 'z') { Zflag = 1; ++program_name; } #endif #if defined(__MSDOS__) || defined(_WIN32) /* DOS and MS-Windows use backslashes as directory separators, and usually have an .exe suffix. They also have case-insensitive filesystems. */ if (program_name) { char *p = program_name; char *bslash = strrchr (argv[0], '\\'); if (bslash && bslash >= program_name) /* for mixed forward/backslash case */ program_name = bslash + 1; else if (program_name == argv[0] && argv[0][0] && argv[0][1] == ':') /* "c:progname" */ program_name = argv[0] + 2; /* Collapse the letter-case, so `strcmp' could be used hence. */ for ( ; *p; p++) if (*p >= 'A' && *p <= 'Z') *p += 'a' - 'A'; /* Remove the .exe extension, if any. */ if ((p = strrchr (program_name, '.')) && strcmp (p, ".exe") == 0) *p = '\0'; } #endif keys = NULL; keycc = 0; with_filenames = 0; eolbyte = '\n'; filename_mask = ~0; max_count = TYPE_MAXIMUM (off_t); /* The value -1 means to use DEFAULT_CONTEXT. */ out_after = out_before = -1; /* Default before/after context: chaged by -C/-NUM options */ default_context = 0; /* Changed by -o option */ only_matching = 0; /* Internationalization. */ #if defined(HAVE_SETLOCALE) setlocale (LC_ALL, ""); #endif #if defined(ENABLE_NLS) bindtextdomain (PACKAGE, LOCALEDIR); textdomain (PACKAGE); #endif atexit (close_stdout); prepend_default_options (getenv ("GREP_OPTIONS"), &argc, &argv); while ((opt = get_nondigit_option (argc, argv, &default_context)) != -1) switch (opt) { case 'A': context_length_arg (optarg, &out_after); break; case 'B': context_length_arg (optarg, &out_before); break; case 'C': /* Set output match context, but let any explicit leading or trailing amount specified with -A or -B stand. */ context_length_arg (optarg, &default_context); break; case 'D': if (strcmp (optarg, "read") == 0) devices = READ_DEVICES; else if (strcmp (optarg, "skip") == 0) devices = SKIP_DEVICES; else error (2, 0, _("unknown devices method")); break; case 'E': setmatcher ("egrep"); break; case 'F': setmatcher ("fgrep"); break; case 'P': setmatcher ("perl"); break; case 'G': setmatcher ("grep"); break; case 'H': with_filenames = 1; break; case 'I': binary_files = WITHOUT_MATCH_BINARY_FILES; break; case 'J': if (Zflag) { printf (_("Cannot mix -Z and -J.\n")); usage (2); } BZflag = 1; break; case 'U': #if defined(HAVE_DOS_FILE_CONTENTS) dos_use_file_type = DOS_BINARY; #endif break; case 'u': #if defined(HAVE_DOS_FILE_CONTENTS) dos_report_unix_offset = 1; #endif break; case 'V': show_version = 1; break; case 'X': setmatcher (optarg); break; case 'a': binary_files = TEXT_BINARY_FILES; break; case 'b': out_byte = 1; break; case 'c': count_matches = 1; break; case 'd': if (strcmp (optarg, "read") == 0) directories = READ_DIRECTORIES; else if (strcmp (optarg, "skip") == 0) directories = SKIP_DIRECTORIES; else if (strcmp (optarg, "recurse") == 0) directories = RECURSE_DIRECTORIES; else error (2, 0, _("unknown directories method")); break; case 'e': cc = strlen (optarg); keys = xrealloc (keys, keycc + cc + 1); strcpy (&keys[keycc], optarg); keycc += cc; keys[keycc++] = '\n'; break; case 'f': fp = strcmp (optarg, "-") != 0 ? fopen (optarg, "r") : stdin; if (!fp) error (2, errno, "%s", optarg); for (keyalloc = 1; keyalloc <= keycc + 1; keyalloc *= 2) ; keys = xrealloc (keys, keyalloc); oldcc = keycc; while (!feof (fp) && (cc = fread (keys + keycc, 1, keyalloc - 1 - keycc, fp)) > 0) { keycc += cc; if (keycc == keyalloc - 1) keys = xrealloc (keys, keyalloc *= 2); } if (fp != stdin) fclose(fp); /* Append final newline if file ended in non-newline. */ if (oldcc != keycc && keys[keycc - 1] != '\n') keys[keycc++] = '\n'; break; case 'h': no_filenames = 1; break; case 'i': case 'y': /* For old-timers . . . */ match_icase = 1; break; case 'L': /* Like -l, except list files that don't contain matches. Inspired by the same option in Hume's gre. */ list_files = -1; break; case 'l': list_files = 1; break; case 'm': { uintmax_t value; switch (xstrtoumax (optarg, 0, 10, &value, "")) { case LONGINT_OK: max_count = value; if (0 <= max_count && max_count == value) break; /* Fall through. */ case LONGINT_OVERFLOW: max_count = TYPE_MAXIMUM (off_t); break; default: error (2, 0, _("invalid max count")); } } break; case 'n': out_line = 1; break; case 'o': only_matching = 1; break; case 'q': exit_on_match = 1; close_stdout_set_status(0); break; case 'R': case 'r': directories = RECURSE_DIRECTORIES; break; case 's': suppress_errors = 1; break; case 'v': out_invert = 1; break; case 'w': match_words = 1; break; case 'x': match_lines = 1; break; case 'Z': #if HAVE_LIBZ > 0 if (BZflag) { printf (_("Cannot mix -J and -Z.\n")); usage (2); } Zflag = 1; #else filename_mask = 0; #endif break; case 'z': eolbyte = '\0'; break; case BINARY_FILES_OPTION: if (strcmp (optarg, "binary") == 0) binary_files = BINARY_BINARY_FILES; else if (strcmp (optarg, "text") == 0) binary_files = TEXT_BINARY_FILES; else if (strcmp (optarg, "without-match") == 0) binary_files = WITHOUT_MATCH_BINARY_FILES; else error (2, 0, _("unknown binary-files type")); break; case COLOR_OPTION: if(optarg) { if(!strcasecmp(optarg, "always") || !strcasecmp(optarg, "yes") || !strcasecmp(optarg, "force")) color_option = 1; else if(!strcasecmp(optarg, "never") || !strcasecmp(optarg, "no") || !strcasecmp(optarg, "none")) color_option = 0; else if(!strcasecmp(optarg, "auto") || !strcasecmp(optarg, "tty") || !strcasecmp(optarg, "if-tty")) color_option = 2; else show_help = 1; } else color_option = 2; if(color_option == 2) { if(isatty(STDOUT_FILENO) && getenv("TERM") && strcmp(getenv("TERM"), "dumb")) color_option = 1; else color_option = 0; } break; case EXCLUDE_OPTION: if (!excluded_patterns) excluded_patterns = new_exclude (); add_exclude (excluded_patterns, optarg); break; case EXCLUDE_FROM_OPTION: if (!excluded_patterns) excluded_patterns = new_exclude (); if (add_exclude_file (add_exclude, excluded_patterns, optarg, '\n') != 0) { error (2, errno, "%s", optarg); } break; case INCLUDE_OPTION: if (!included_patterns) included_patterns = new_exclude (); add_exclude (included_patterns, optarg); break; case LINE_BUFFERED_OPTION: line_buffered = 1; break; case LABEL_OPTION: label = optarg; break; case 0: /* long options */ break; default: usage (2); break; } /* POSIX.2 says that -q overrides -l, which in turn overrides the other output options. */ if (exit_on_match) list_files = 0; if (exit_on_match | list_files) { count_matches = 0; done_on_match = 1; } out_quiet = count_matches | done_on_match; if (out_after < 0) out_after = default_context; if (out_before < 0) out_before = default_context; if (color_option) { char *userval = getenv ("GREP_COLOR"); if (userval != NULL && *userval != '\0') grep_color = userval; } if (! matcher) matcher = program_name; if (show_version) { printf (_("%s (GNU grep) %s\n"), matcher, VERSION); printf ("\n"); printf (_("\ Copyright 1988, 1992-1999, 2000, 2001 Free Software Foundation, Inc.\n")); printf (_("\ This is free software; see the source for copying conditions. There is NO\n\ warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n")); printf ("\n"); exit (0); } if (show_help) usage (0); if (keys) { if (keycc == 0) { /* No keys were specified (e.g. -f /dev/null). Match nothing. */ out_invert ^= 1; match_lines = match_words = 0; } else /* Strip trailing newline. */ --keycc; } else if (optind < argc) { keys = argv[optind++]; keycc = strlen (keys); } else usage (2); if (!install_matcher (matcher) && !install_matcher ("default")) abort (); #ifdef MBS_SUPPORT if (MB_CUR_MAX != 1 && match_icase) { wchar_t wc; mbstate_t cur_state, prev_state; int i, len = strlen(keys); memset(&cur_state, 0, sizeof(mbstate_t)); for (i = 0; i <= len ;) { size_t mbclen; mbclen = mbrtowc(&wc, keys + i, len - i, &cur_state); if (mbclen == (size_t) -1 || mbclen == (size_t) -2 || mbclen == 0) { /* An invalid sequence, or a truncated multibyte character. We treat it as a singlebyte character. */ mbclen = 1; } else { if (iswupper((wint_t)wc)) { wc = towlower((wint_t)wc); wcrtomb(keys + i, wc, &cur_state); } } i += mbclen; } } #endif /* MBS_SUPPORT */ (*compile)(keys, keycc); if ((argc - optind > 1 && !no_filenames) || with_filenames) out_file = 1; #ifdef SET_BINARY /* Output is set to binary mode because we shouldn't convert NL to CR-LF pairs, especially when grepping binary files. */ if (!isatty (1)) SET_BINARY (1); #endif if (max_count == 0) exit (1); if (optind < argc) { status = 1; do { char *file = argv[optind]; if ((included_patterns || excluded_patterns) && !isdir (file)) { if (included_patterns && ! excluded_filename (included_patterns, file, 0)) continue; if (excluded_patterns && excluded_filename (excluded_patterns, file, 0)) continue; } status &= grepfile (strcmp (file, "-") == 0 ? (char *) NULL : file, &stats_base); } while ( ++optind < argc); } else status = grepfile ((char *) NULL, &stats_base); /* We register via atexit() to test stdout. */ exit (errseen ? 2 : status); } /* vim:set shiftwidth=2: */ Index: stable/9/gnu/usr.bin/grep/search.c =================================================================== --- stable/9/gnu/usr.bin/grep/search.c (revision 250821) +++ stable/9/gnu/usr.bin/grep/search.c (revision 250822) @@ -1,1290 +1,1289 @@ /* search.c - searching subroutines using dfa, kwset and regex for grep. Copyright 1992, 1998, 2000 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /* Written August 1992 by Mike Haertel. */ /* $FreeBSD$ */ #ifndef _GNU_SOURCE # define _GNU_SOURCE 1 #endif #ifdef HAVE_CONFIG_H # include #endif #include #include #if defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H && defined HAVE_MBRTOWC /* We can handle multibyte string. */ # define MBS_SUPPORT # include # include #endif #include "system.h" #include "grep.h" #include "regex.h" #include "dfa.h" #include "kwset.h" #include "error.h" #include "xalloc.h" #ifdef HAVE_LIBPCRE # include #endif #ifdef HAVE_LANGINFO_CODESET # include #endif #define NCHAR (UCHAR_MAX + 1) /* For -w, we also consider _ to be word constituent. */ #define WCHAR(C) (ISALNUM(C) || (C) == '_') /* DFA compiled regexp. */ static struct dfa dfa; /* The Regex compiled patterns. */ static struct patterns { /* Regex compiled regexp. */ struct re_pattern_buffer regexbuf; struct re_registers regs; /* This is here on account of a BRAIN-DEAD Q@#%!# library interface in regex.c. */ } patterns0; struct patterns *patterns; size_t pcount; /* KWset compiled pattern. For Ecompile and Gcompile, we compile a list of strings, at least one of which is known to occur in any string matching the regexp. */ static kwset_t kwset; /* Number of compiled fixed strings known to exactly match the regexp. If kwsexec returns < kwset_exact_matches, then we don't need to call the regexp matcher at all. */ static int kwset_exact_matches; /* UTF-8 encoding allows some optimizations that we can't otherwise assume in a multibyte encoding. */ static int using_utf8; static void kwsinit PARAMS ((void)); static void kwsmusts PARAMS ((void)); static void Gcompile PARAMS ((char const *, size_t)); static void Ecompile PARAMS ((char const *, size_t)); static size_t EGexecute PARAMS ((char const *, size_t, size_t *, int )); static void Fcompile PARAMS ((char const *, size_t)); static size_t Fexecute PARAMS ((char const *, size_t, size_t *, int)); static void Pcompile PARAMS ((char const *, size_t )); static size_t Pexecute PARAMS ((char const *, size_t, size_t *, int)); void check_utf8 (void) { #ifdef HAVE_LANGINFO_CODESET if (strcmp (nl_langinfo (CODESET), "UTF-8") == 0) using_utf8 = 1; #endif } void dfaerror (char const *mesg) { error (2, 0, mesg); } static void kwsinit (void) { static char trans[NCHAR]; - size_t i; + int i; if (match_icase) for (i = 0; i < NCHAR; ++i) trans[i] = TOLOWER (i); if (!(kwset = kwsalloc (match_icase ? trans : (char *) 0))) error (2, 0, _("memory exhausted")); } /* If the DFA turns out to have some set of fixed strings one of which must occur in the match, then we build a kwset matcher to find those strings, and thus quickly filter out impossible matches. */ static void kwsmusts (void) { struct dfamust const *dm; char const *err; if (dfa.musts) { kwsinit (); /* First, we compile in the substrings known to be exact matches. The kwset matcher will return the index of the matching string that it chooses. */ for (dm = dfa.musts; dm; dm = dm->next) { if (!dm->exact) continue; ++kwset_exact_matches; if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != 0) error (2, 0, err); } /* Now, we compile the substrings that will require the use of the regexp matcher. */ for (dm = dfa.musts; dm; dm = dm->next) { if (dm->exact) continue; if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != 0) error (2, 0, err); } if ((err = kwsprep (kwset)) != 0) error (2, 0, err); } } static void Gcompile (char const *pattern, size_t size) { const char *err; char const *sep; size_t total = size; char const *motif = pattern; check_utf8 (); re_set_syntax (RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE | (match_icase ? RE_ICASE : 0)); dfasyntax (RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE, match_icase, eolbyte); /* For GNU regex compiler we have to pass the patterns separately to detect errors like "[\nallo\n]\n". The patterns here are "[", "allo" and "]" GNU regex should have raise a syntax error. The same for backref, where the backref should have been local to each pattern. */ do { size_t len; sep = memchr (motif, '\n', total); if (sep) { len = sep - motif; sep++; total -= (len + 1); } else { len = total; total = 0; } patterns = realloc (patterns, (pcount + 1) * sizeof (*patterns)); if (patterns == NULL) error (2, errno, _("memory exhausted")); patterns[pcount] = patterns0; if ((err = re_compile_pattern (motif, len, &(patterns[pcount].regexbuf))) != 0) error (2, 0, err); pcount++; motif = sep; } while (sep && total != 0); /* In the match_words and match_lines cases, we use a different pattern for the DFA matcher that will quickly throw out cases that won't work. Then if DFA succeeds we do some hairy stuff using the regex matcher to decide whether the match should really count. */ if (match_words || match_lines) { /* In the whole-word case, we use the pattern: \(^\|[^[:alnum:]_]\)\(userpattern\)\([^[:alnum:]_]|$\). In the whole-line case, we use the pattern: ^\(userpattern\)$. */ static char const line_beg[] = "^\\("; static char const line_end[] = "\\)$"; static char const word_beg[] = "\\(^\\|[^[:alnum:]_]\\)\\("; static char const word_end[] = "\\)\\([^[:alnum:]_]\\|$\\)"; char *n = xmalloc (sizeof word_beg - 1 + size + sizeof word_end); size_t i; strcpy (n, match_lines ? line_beg : word_beg); i = strlen (n); memcpy (n + i, pattern, size); i += size; strcpy (n + i, match_lines ? line_end : word_end); i += strlen (n + i); pattern = n; size = i; } dfacomp (pattern, size, &dfa, 1); kwsmusts (); } static void Ecompile (char const *pattern, size_t size) { const char *err; const char *sep; size_t total = size; char const *motif = pattern; check_utf8 (); if (strcmp (matcher, "awk") == 0) { re_set_syntax (RE_SYNTAX_AWK | (match_icase ? RE_ICASE : 0)); dfasyntax (RE_SYNTAX_AWK, match_icase, eolbyte); } else { re_set_syntax (RE_SYNTAX_POSIX_EGREP | (match_icase ? RE_ICASE : 0)); dfasyntax (RE_SYNTAX_POSIX_EGREP, match_icase, eolbyte); } /* For GNU regex compiler we have to pass the patterns separately to detect errors like "[\nallo\n]\n". The patterns here are "[", "allo" and "]" GNU regex should have raise a syntax error. The same for backref, where the backref should have been local to each pattern. */ do { size_t len; sep = memchr (motif, '\n', total); if (sep) { len = sep - motif; sep++; total -= (len + 1); } else { len = total; total = 0; } patterns = realloc (patterns, (pcount + 1) * sizeof (*patterns)); if (patterns == NULL) error (2, errno, _("memory exhausted")); patterns[pcount] = patterns0; if ((err = re_compile_pattern (motif, len, &(patterns[pcount].regexbuf))) != 0) error (2, 0, err); pcount++; motif = sep; } while (sep && total != 0); /* In the match_words and match_lines cases, we use a different pattern for the DFA matcher that will quickly throw out cases that won't work. Then if DFA succeeds we do some hairy stuff using the regex matcher to decide whether the match should really count. */ if (match_words || match_lines) { /* In the whole-word case, we use the pattern: (^|[^[:alnum:]_])(userpattern)([^[:alnum:]_]|$). In the whole-line case, we use the pattern: ^(userpattern)$. */ static char const line_beg[] = "^("; static char const line_end[] = ")$"; static char const word_beg[] = "(^|[^[:alnum:]_])("; static char const word_end[] = ")([^[:alnum:]_]|$)"; char *n = xmalloc (sizeof word_beg - 1 + size + sizeof word_end); size_t i; strcpy (n, match_lines ? line_beg : word_beg); i = strlen(n); memcpy (n + i, pattern, size); i += size; strcpy (n + i, match_lines ? line_end : word_end); i += strlen (n + i); pattern = n; size = i; } dfacomp (pattern, size, &dfa, 1); kwsmusts (); } static size_t EGexecute (char const *buf, size_t size, size_t *match_size, int exact) { register char const *buflim, *beg, *end; char eol = eolbyte; - int backref; - ptrdiff_t start, len; + int backref, start, len; struct kwsmatch kwsm; size_t i, ret_val; static int use_dfa; static int use_dfa_checked = 0; #ifdef MBS_SUPPORT const char *last_char = NULL; int mb_cur_max = MB_CUR_MAX; mbstate_t mbs; memset (&mbs, '\0', sizeof (mbstate_t)); #endif /* MBS_SUPPORT */ if (!use_dfa_checked) { char *grep_use_dfa = getenv ("GREP_USE_DFA"); if (!grep_use_dfa) { #ifdef MBS_SUPPORT /* Turn off DFA when processing multibyte input. */ use_dfa = (MB_CUR_MAX == 1); #else use_dfa = 1; #endif /* MBS_SUPPORT */ } else { use_dfa = atoi (grep_use_dfa); } use_dfa_checked = 1; } buflim = buf + size; for (beg = end = buf; end < buflim; beg = end) { if (!exact) { if (kwset) { /* Find a possible match using the KWset matcher. */ #ifdef MBS_SUPPORT size_t bytes_left = 0; #endif /* MBS_SUPPORT */ size_t offset; #ifdef MBS_SUPPORT /* kwsexec doesn't work with match_icase and multibyte input. */ if (match_icase && mb_cur_max > 1) /* Avoid kwset */ offset = 0; else #endif /* MBS_SUPPORT */ offset = kwsexec (kwset, beg, buflim - beg, &kwsm); if (offset == (size_t) -1) goto failure; #ifdef MBS_SUPPORT if (mb_cur_max > 1 && !using_utf8) { bytes_left = offset; while (bytes_left) { size_t mlen = mbrlen (beg, bytes_left, &mbs); last_char = beg; if (mlen == (size_t) -1 || mlen == 0) { /* Incomplete character: treat as single-byte. */ memset (&mbs, '\0', sizeof (mbstate_t)); beg++; bytes_left--; continue; } if (mlen == (size_t) -2) /* Offset points inside multibyte character: * no good. */ break; beg += mlen; bytes_left -= mlen; } } else #endif /* MBS_SUPPORT */ beg += offset; /* Narrow down to the line containing the candidate, and run it through DFA. */ end = memchr(beg, eol, buflim - beg); end++; #ifdef MBS_SUPPORT if (mb_cur_max > 1 && bytes_left) continue; #endif /* MBS_SUPPORT */ while (beg > buf && beg[-1] != eol) --beg; if ( #ifdef MBS_SUPPORT !(match_icase && mb_cur_max > 1) && #endif /* MBS_SUPPORT */ (kwsm.index < kwset_exact_matches)) goto success_in_beg_and_end; if (use_dfa && dfaexec (&dfa, beg, end - beg, &backref) == (size_t) -1) continue; } else { /* No good fixed strings; start with DFA. */ #ifdef MBS_SUPPORT size_t bytes_left = 0; #endif /* MBS_SUPPORT */ size_t offset = 0; if (use_dfa) offset = dfaexec (&dfa, beg, buflim - beg, &backref); if (offset == (size_t) -1) break; /* Narrow down to the line we've found. */ #ifdef MBS_SUPPORT if (mb_cur_max > 1 && !using_utf8) { bytes_left = offset; while (bytes_left) { size_t mlen = mbrlen (beg, bytes_left, &mbs); last_char = beg; if (mlen == (size_t) -1 || mlen == 0) { /* Incomplete character: treat as single-byte. */ memset (&mbs, '\0', sizeof (mbstate_t)); beg++; bytes_left--; continue; } if (mlen == (size_t) -2) /* Offset points inside multibyte character: * no good. */ break; beg += mlen; bytes_left -= mlen; } } else #endif /* MBS_SUPPORT */ beg += offset; end = memchr (beg, eol, buflim - beg); end++; #ifdef MBS_SUPPORT if (mb_cur_max > 1 && bytes_left) continue; #endif /* MBS_SUPPORT */ while (beg > buf && beg[-1] != eol) --beg; } /* Successful, no backreferences encountered! */ if (use_dfa && !backref) goto success_in_beg_and_end; } else end = beg + size; /* If we've made it to this point, this means DFA has seen a probable match, and we need to run it through Regex. */ for (i = 0; i < pcount; i++) { patterns[i].regexbuf.not_eol = 0; if (0 <= (start = re_search (&(patterns[i].regexbuf), beg, end - beg - 1, 0, end - beg - 1, &(patterns[i].regs)))) { len = patterns[i].regs.end[0] - start; if (exact && !match_words) goto success_in_start_and_len; if ((!match_lines && !match_words) || (match_lines && len == end - beg - 1)) goto success_in_beg_and_end; /* If -w, check if the match aligns with word boundaries. We do this iteratively because: (a) the line may contain more than one occurence of the pattern, and (b) Several alternatives in the pattern might be valid at a given point, and we may need to consider a shorter one to find a word boundary. */ if (match_words) while (start >= 0) { int lword_match = 0; if (start == 0) lword_match = 1; else { assert (start > 0); #ifdef MBS_SUPPORT if (mb_cur_max > 1) { const char *s; size_t mr; wchar_t pwc; /* Locate the start of the multibyte character before the match position (== beg + start). */ if (using_utf8) { /* UTF-8 is a special case: scan backwards until we find a 7-bit character or a lead byte. */ s = beg + start - 1; while (s > buf && (unsigned char) *s >= 0x80 && (unsigned char) *s <= 0xbf) --s; } else { /* Scan forwards to find the start of the last complete character before the match position. */ size_t bytes_left = start - 1; s = beg; while (bytes_left > 0) { mr = mbrlen (s, bytes_left, &mbs); if (mr == (size_t) -1 || mr == 0) { memset (&mbs, '\0', sizeof (mbs)); s++; bytes_left--; continue; } if (mr == (size_t) -2) { memset (&mbs, '\0', sizeof (mbs)); break; } s += mr; bytes_left -= mr; } } mr = mbrtowc (&pwc, s, beg + start - s, &mbs); if (mr == (size_t) -2 || mr == (size_t) -1 || mr == 0) { memset (&mbs, '\0', sizeof (mbstate_t)); lword_match = 1; } else if (!(iswalnum (pwc) || pwc == L'_') && mr == beg + start - s) lword_match = 1; } else #endif /* MBS_SUPPORT */ if (!WCHAR ((unsigned char) beg[start - 1])) lword_match = 1; } if (lword_match) { int rword_match = 0; if (start + len == end - beg - 1) rword_match = 1; else { #ifdef MBS_SUPPORT if (mb_cur_max > 1) { wchar_t nwc; int mr; mr = mbtowc (&nwc, beg + start + len, end - beg - start - len - 1); if (mr <= 0) { memset (&mbs, '\0', sizeof (mbstate_t)); rword_match = 1; } else if (!iswalnum (nwc) && nwc != L'_') rword_match = 1; } else #endif /* MBS_SUPPORT */ if (!WCHAR ((unsigned char) beg[start + len])) rword_match = 1; } if (rword_match) { if (!exact) /* Returns the whole line. */ goto success_in_beg_and_end; else /* Returns just this word match. */ goto success_in_start_and_len; } } if (len > 0) { /* Try a shorter length anchored at the same place. */ --len; patterns[i].regexbuf.not_eol = 1; len = re_match (&(patterns[i].regexbuf), beg, start + len, start, &(patterns[i].regs)); } if (len <= 0) { /* Try looking further on. */ if (start == end - beg - 1) break; ++start; patterns[i].regexbuf.not_eol = 0; start = re_search (&(patterns[i].regexbuf), beg, end - beg - 1, start, end - beg - 1 - start, &(patterns[i].regs)); len = patterns[i].regs.end[0] - start; } } } } /* for Regex patterns. */ } /* for (beg = end ..) */ failure: return (size_t) -1; success_in_beg_and_end: len = end - beg; start = beg - buf; /* FALLTHROUGH */ success_in_start_and_len: *match_size = len; return start; } #ifdef MBS_SUPPORT static int f_i_multibyte; /* whether we're using the new -Fi MB method */ static struct { wchar_t **patterns; size_t count, maxlen; unsigned char *match; } Fimb; #endif static void Fcompile (char const *pattern, size_t size) { int mb_cur_max = MB_CUR_MAX; char const *beg, *lim, *err; check_utf8 (); #ifdef MBS_SUPPORT /* Support -F -i for UTF-8 input. */ if (match_icase && mb_cur_max > 1) { mbstate_t mbs; wchar_t *wcpattern = xmalloc ((size + 1) * sizeof (wchar_t)); const char *patternend = pattern; size_t wcsize; kwset_t fimb_kwset = NULL; char *starts = NULL; wchar_t *wcbeg, *wclim; size_t allocated = 0; memset (&mbs, '\0', sizeof (mbs)); # ifdef __GNU_LIBRARY__ wcsize = mbsnrtowcs (wcpattern, &patternend, size, size, &mbs); if (patternend != pattern + size) wcsize = (size_t) -1; # else { char *patterncopy = xmalloc (size + 1); memcpy (patterncopy, pattern, size); patterncopy[size] = '\0'; patternend = patterncopy; wcsize = mbsrtowcs (wcpattern, &patternend, size, &mbs); if (patternend != patterncopy + size) wcsize = (size_t) -1; free (patterncopy); } # endif if (wcsize + 2 <= 2) { fimb_fail: free (wcpattern); free (starts); if (fimb_kwset) kwsfree (fimb_kwset); free (Fimb.patterns); Fimb.patterns = NULL; } else { if (!(fimb_kwset = kwsalloc (NULL))) error (2, 0, _("memory exhausted")); starts = xmalloc (mb_cur_max * 3); wcbeg = wcpattern; do { int i; size_t wclen; if (Fimb.count >= allocated) { if (allocated == 0) allocated = 128; else allocated *= 2; Fimb.patterns = xrealloc (Fimb.patterns, sizeof (wchar_t *) * allocated); } Fimb.patterns[Fimb.count++] = wcbeg; for (wclim = wcbeg; wclim < wcpattern + wcsize && *wclim != L'\n'; ++wclim) *wclim = towlower (*wclim); *wclim = L'\0'; wclen = wclim - wcbeg; if (wclen > Fimb.maxlen) Fimb.maxlen = wclen; if (wclen > 3) wclen = 3; if (wclen == 0) { if ((err = kwsincr (fimb_kwset, "", 0)) != 0) error (2, 0, err); } else for (i = 0; i < (1 << wclen); i++) { char *p = starts; int j, k; for (j = 0; j < wclen; ++j) { wchar_t wc = wcbeg[j]; if (i & (1 << j)) { wc = towupper (wc); if (wc == wcbeg[j]) continue; } k = wctomb (p, wc); if (k <= 0) goto fimb_fail; p += k; } if ((err = kwsincr (fimb_kwset, starts, p - starts)) != 0) error (2, 0, err); } if (wclim < wcpattern + wcsize) ++wclim; wcbeg = wclim; } while (wcbeg < wcpattern + wcsize); f_i_multibyte = 1; kwset = fimb_kwset; free (starts); Fimb.match = xmalloc (Fimb.count); if ((err = kwsprep (kwset)) != 0) error (2, 0, err); return; } } #endif /* MBS_SUPPORT */ kwsinit (); beg = pattern; do { for (lim = beg; lim < pattern + size && *lim != '\n'; ++lim) ; if ((err = kwsincr (kwset, beg, lim - beg)) != 0) error (2, 0, err); if (lim < pattern + size) ++lim; beg = lim; } while (beg < pattern + size); if ((err = kwsprep (kwset)) != 0) error (2, 0, err); } #ifdef MBS_SUPPORT static int Fimbexec (const char *buf, size_t size, size_t *plen, int exact) { size_t len, letter, i; int ret = -1; mbstate_t mbs; wchar_t wc; int patterns_left; assert (match_icase && f_i_multibyte == 1); assert (MB_CUR_MAX > 1); memset (&mbs, '\0', sizeof (mbs)); memset (Fimb.match, '\1', Fimb.count); letter = len = 0; patterns_left = 1; while (patterns_left && len <= size) { size_t c; patterns_left = 0; if (len < size) { c = mbrtowc (&wc, buf + len, size - len, &mbs); if (c + 2 <= 2) return ret; wc = towlower (wc); } else { c = 1; wc = L'\0'; } for (i = 0; i < Fimb.count; i++) { if (Fimb.match[i]) { if (Fimb.patterns[i][letter] == L'\0') { /* Found a match. */ *plen = len; if (!exact && !match_words) return 0; else { /* For -w or exact look for longest match. */ ret = 0; Fimb.match[i] = '\0'; continue; } } if (Fimb.patterns[i][letter] == wc) patterns_left = 1; else Fimb.match[i] = '\0'; } } len += c; letter++; } return ret; } #endif /* MBS_SUPPORT */ static size_t Fexecute (char const *buf, size_t size, size_t *match_size, int exact) { register char const *beg, *try, *end; register size_t len; char eol = eolbyte; struct kwsmatch kwsmatch; size_t ret_val; #ifdef MBS_SUPPORT int mb_cur_max = MB_CUR_MAX; mbstate_t mbs; memset (&mbs, '\0', sizeof (mbstate_t)); const char *last_char = NULL; #endif /* MBS_SUPPORT */ for (beg = buf; beg <= buf + size; ++beg) { size_t offset; offset = kwsexec (kwset, beg, buf + size - beg, &kwsmatch); if (offset == (size_t) -1) goto failure; #ifdef MBS_SUPPORT if (mb_cur_max > 1 && !using_utf8) { size_t bytes_left = offset; while (bytes_left) { size_t mlen = mbrlen (beg, bytes_left, &mbs); last_char = beg; if (mlen == (size_t) -1 || mlen == 0) { /* Incomplete character: treat as single-byte. */ memset (&mbs, '\0', sizeof (mbstate_t)); beg++; bytes_left--; continue; } if (mlen == (size_t) -2) /* Offset points inside multibyte character: no good. */ break; beg += mlen; bytes_left -= mlen; } if (bytes_left) continue; } else #endif /* MBS_SUPPORT */ beg += offset; #ifdef MBS_SUPPORT /* For f_i_multibyte, the string at beg now matches first 3 chars of one of the search strings (less if there are shorter search strings). See if this is a real match. */ if (f_i_multibyte && Fimbexec (beg, buf + size - beg, &kwsmatch.size[0], exact)) goto next_char; #endif /* MBS_SUPPORT */ len = kwsmatch.size[0]; if (exact && !match_words) goto success_in_beg_and_len; if (match_lines) { if (beg > buf && beg[-1] != eol) goto next_char; if (beg + len < buf + size && beg[len] != eol) goto next_char; goto success; } else if (match_words) { while (1) { int word_match = 0; if (beg > buf) { #ifdef MBS_SUPPORT if (mb_cur_max > 1) { const char *s; int mr; wchar_t pwc; if (using_utf8) { s = beg - 1; while (s > buf && (unsigned char) *s >= 0x80 && (unsigned char) *s <= 0xbf) --s; } else s = last_char; mr = mbtowc (&pwc, s, beg - s); if (mr <= 0) memset (&mbs, '\0', sizeof (mbstate_t)); else if ((iswalnum (pwc) || pwc == L'_') && mr == (int) (beg - s)) goto next_char; } else #endif /* MBS_SUPPORT */ if (WCHAR ((unsigned char) beg[-1])) goto next_char; } #ifdef MBS_SUPPORT if (mb_cur_max > 1) { wchar_t nwc; int mr; mr = mbtowc (&nwc, beg + len, buf + size - beg - len); if (mr <= 0) { memset (&mbs, '\0', sizeof (mbstate_t)); word_match = 1; } else if (!iswalnum (nwc) && nwc != L'_') word_match = 1; } else #endif /* MBS_SUPPORT */ if (beg + len >= buf + size || !WCHAR ((unsigned char) beg[len])) word_match = 1; if (word_match) { if (!exact) /* Returns the whole line now we know there's a word match. */ goto success; else /* Returns just this word match. */ goto success_in_beg_and_len; } if (len > 0) { /* Try a shorter length anchored at the same place. */ --len; offset = kwsexec (kwset, beg, len, &kwsmatch); if (offset == -1) goto next_char; /* Try a different anchor. */ #ifdef MBS_SUPPORT if (mb_cur_max > 1 && !using_utf8) { size_t bytes_left = offset; while (bytes_left) { size_t mlen = mbrlen (beg, bytes_left, &mbs); last_char = beg; if (mlen == (size_t) -1 || mlen == 0) { /* Incomplete character: treat as single-byte. */ memset (&mbs, '\0', sizeof (mbstate_t)); beg++; bytes_left--; continue; } if (mlen == (size_t) -2) { /* Offset points inside multibyte character: * no good. */ break; } beg += mlen; bytes_left -= mlen; } if (bytes_left) { memset (&mbs, '\0', sizeof (mbstate_t)); goto next_char; /* Try a different anchor. */ } } else #endif /* MBS_SUPPORT */ beg += offset; #ifdef MBS_SUPPORT /* The string at beg now matches first 3 chars of one of the search strings (less if there are shorter search strings). See if this is a real match. */ if (f_i_multibyte && Fimbexec (beg, len - offset, &kwsmatch.size[0], exact)) goto next_char; #endif /* MBS_SUPPORT */ len = kwsmatch.size[0]; } } } else goto success; next_char:; #ifdef MBS_SUPPORT /* Advance to next character. For MB_CUR_MAX == 1 case this is handled by ++beg above. */ if (mb_cur_max > 1) { if (using_utf8) { unsigned char c = *beg; if (c >= 0xc2) { if (c < 0xe0) ++beg; else if (c < 0xf0) beg += 2; else if (c < 0xf8) beg += 3; else if (c < 0xfc) beg += 4; else if (c < 0xfe) beg += 5; } } else { size_t l = mbrlen (beg, buf + size - beg, &mbs); last_char = beg; if (l + 2 >= 2) beg += l - 1; else memset (&mbs, '\0', sizeof (mbstate_t)); } } #endif /* MBS_SUPPORT */ } failure: return -1; success: #ifdef MBS_SUPPORT if (mb_cur_max > 1 && !using_utf8) { end = beg + len; while (end < buf + size) { size_t mlen = mbrlen (end, buf + size - end, &mbs); if (mlen == (size_t) -1 || mlen == (size_t) -2 || mlen == 0) { memset (&mbs, '\0', sizeof (mbstate_t)); mlen = 1; } if (mlen == 1 && *end == eol) break; end += mlen; } } else #endif /* MBS_SUPPORT */ end = memchr (beg + len, eol, (buf + size) - (beg + len)); end++; while (buf < beg && beg[-1] != eol) --beg; len = end - beg; /* FALLTHROUGH */ success_in_beg_and_len: *match_size = len; return beg - buf; } #if HAVE_LIBPCRE /* Compiled internal form of a Perl regular expression. */ static pcre *cre; /* Additional information about the pattern. */ static pcre_extra *extra; #endif static void Pcompile (char const *pattern, size_t size) { #if !HAVE_LIBPCRE error (2, 0, _("The -P option is not supported")); #else int e; char const *ep; char *re = xmalloc (4 * size + 7); int flags = PCRE_MULTILINE | (match_icase ? PCRE_CASELESS : 0); char const *patlim = pattern + size; char *n = re; char const *p; char const *pnul; /* FIXME: Remove this restriction. */ if (eolbyte != '\n') error (2, 0, _("The -P and -z options cannot be combined")); *n = '\0'; if (match_lines) strcpy (n, "^("); if (match_words) strcpy (n, "\\b("); n += strlen (n); /* The PCRE interface doesn't allow NUL bytes in the pattern, so replace each NUL byte in the pattern with the four characters "\000", removing a preceding backslash if there are an odd number of backslashes before the NUL. FIXME: This method does not work with some multibyte character encodings, notably Shift-JIS, where a multibyte character can end in a backslash byte. */ for (p = pattern; (pnul = memchr (p, '\0', patlim - p)); p = pnul + 1) { memcpy (n, p, pnul - p); n += pnul - p; for (p = pnul; pattern < p && p[-1] == '\\'; p--) continue; n -= (pnul - p) & 1; strcpy (n, "\\000"); n += 4; } memcpy (n, p, patlim - p); n += patlim - p; *n = '\0'; if (match_words) strcpy (n, ")\\b"); if (match_lines) strcpy (n, ")$"); cre = pcre_compile (re, flags, &ep, &e, pcre_maketables ()); if (!cre) error (2, 0, ep); extra = pcre_study (cre, 0, &ep); if (ep) error (2, 0, ep); free (re); #endif } static size_t Pexecute (char const *buf, size_t size, size_t *match_size, int exact) { #if !HAVE_LIBPCRE abort (); return -1; #else /* This array must have at least two elements; everything after that is just for performance improvement in pcre_exec. */ int sub[300]; int e = pcre_exec (cre, extra, buf, size, 0, 0, sub, sizeof sub / sizeof *sub); if (e <= 0) { switch (e) { case PCRE_ERROR_NOMATCH: return -1; case PCRE_ERROR_NOMEMORY: error (2, 0, _("Memory exhausted")); default: abort (); } } else { /* Narrow down to the line we've found. */ char const *beg = buf + sub[0]; char const *end = buf + sub[1]; char const *buflim = buf + size; char eol = eolbyte; if (!exact) { end = memchr (end, eol, buflim - end); end++; while (buf < beg && beg[-1] != eol) --beg; } *match_size = end - beg; return beg - buf; } #endif } struct matcher const matchers[] = { { "default", Gcompile, EGexecute }, { "grep", Gcompile, EGexecute }, { "egrep", Ecompile, EGexecute }, { "awk", Ecompile, EGexecute }, { "fgrep", Fcompile, Fexecute }, { "perl", Pcompile, Pexecute }, { "", 0, 0 }, };