Index: stable/9/usr.bin/grep/grep.c =================================================================== --- stable/9/usr.bin/grep/grep.c (revision 303882) +++ stable/9/usr.bin/grep/grep.c (revision 303883) @@ -1,747 +1,748 @@ /* $NetBSD: grep.c,v 1.6 2011/04/18 03:48:23 joerg Exp $ */ /* $FreeBSD$ */ /* $OpenBSD: grep.c,v 1.42 2010/07/02 22:18:03 tedu Exp $ */ /*- * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav * Copyright (C) 2008-2009 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include #include #define _WITH_GETLINE #include #include #include #include #include "fastmatch.h" #include "grep.h" #ifndef WITHOUT_NLS #include nl_catd catalog; #endif /* * Default messags to use when NLS is disabled or no catalogue * is found. */ const char *errstr[] = { "", /* 1*/ "(standard input)", /* 2*/ "cannot read bzip2 compressed file", /* 3*/ "unknown %s option", /* 4*/ "usage: %s [-abcDEFGHhIiJLlmnOoPqRSsUVvwxZ] [-A num] [-B num] [-C[num]]\n", /* 5*/ "\t[-e pattern] [-f file] [--binary-files=value] [--color=when]\n", /* 6*/ "\t[--context[=num]] [--directories=action] [--label] [--line-buffered]\n", /* 7*/ "\t[--null] [pattern] [file ...]\n", /* 8*/ "Binary file %s matches\n", /* 9*/ "%s (BSD grep) %s\n", }; /* Flags passed to regcomp() and regexec() */ int cflags = REG_NOSUB; int eflags = REG_STARTEND; /* Shortcut for matching all cases like empty regex */ bool matchall; /* Searching patterns */ -unsigned int patterns, pattern_sz; +unsigned int patterns; +static unsigned int pattern_sz; struct pat *pattern; regex_t *r_pattern; fastmatch_t *fg_pattern; /* Filename exclusion/inclusion patterns */ -unsigned int fpatterns, fpattern_sz; -unsigned int dpatterns, dpattern_sz; +unsigned int fpatterns, dpatterns; +static unsigned int fpattern_sz, dpattern_sz; struct epat *dpattern, *fpattern; /* For regex errors */ char re_error[RE_ERROR_BUF + 1]; /* Command-line flags */ unsigned long long Aflag; /* -A x: print x lines trailing each match */ unsigned long long Bflag; /* -B x: print x lines leading each match */ bool Hflag; /* -H: always print file name */ bool Lflag; /* -L: only show names of files with no matches */ bool bflag; /* -b: show block numbers for each match */ bool cflag; /* -c: only show a count of matching lines */ bool hflag; /* -h: don't print filename headers */ bool iflag; /* -i: ignore case */ bool lflag; /* -l: only show names of files with matches */ bool mflag; /* -m x: stop reading the files after x matches */ long long mcount; /* count for -m */ long long mlimit; /* requested value for -m */ bool nflag; /* -n: show line numbers in front of matching lines */ bool oflag; /* -o: print only matching part */ bool qflag; /* -q: quiet mode (don't output anything) */ bool sflag; /* -s: silent mode (ignore errors) */ bool vflag; /* -v: only show non-matching lines */ bool wflag; /* -w: pattern must start and end on word boundaries */ bool xflag; /* -x: pattern must match entire line */ bool lbflag; /* --line-buffered */ bool nullflag; /* --null */ char *label; /* --label */ const char *color; /* --color */ int grepbehave = GREP_BASIC; /* -EFGP: type of the regex */ int binbehave = BINFILE_BIN; /* -aIU: handling of binary files */ int filebehave = FILE_STDIO; /* -JZ: normal, gzip or bzip2 file */ int devbehave = DEV_READ; /* -D: handling of devices */ int dirbehave = DIR_READ; /* -dRr: handling of directories */ int linkbehave = LINK_READ; /* -OpS: handling of symlinks */ bool dexclude, dinclude; /* --exclude-dir and --include-dir */ bool fexclude, finclude; /* --exclude and --include */ enum { BIN_OPT = CHAR_MAX + 1, COLOR_OPT, HELP_OPT, MMAP_OPT, LINEBUF_OPT, LABEL_OPT, NULL_OPT, R_EXCLUDE_OPT, R_INCLUDE_OPT, R_DEXCLUDE_OPT, R_DINCLUDE_OPT }; static inline const char *init_color(const char *); /* Housekeeping */ bool first = true; /* flag whether we are processing the first match */ bool prev; /* flag whether or not the previous line matched */ int tail; /* lines left to print */ bool file_err; /* file reading error */ /* * Prints usage information and returns 2. */ static void usage(void) { fprintf(stderr, getstr(4), getprogname()); fprintf(stderr, "%s", getstr(5)); fprintf(stderr, "%s", getstr(6)); fprintf(stderr, "%s", getstr(7)); exit(2); } static const char *optstr = "0123456789A:B:C:D:EFGHIJMLOPSRUVZabcd:e:f:hilm:nopqrsuvwxXy"; -struct option long_options[] = +static const struct option long_options[] = { {"binary-files", required_argument, NULL, BIN_OPT}, {"help", no_argument, NULL, HELP_OPT}, {"mmap", no_argument, NULL, MMAP_OPT}, {"line-buffered", no_argument, NULL, LINEBUF_OPT}, {"label", required_argument, NULL, LABEL_OPT}, {"null", no_argument, NULL, NULL_OPT}, {"color", optional_argument, NULL, COLOR_OPT}, {"colour", optional_argument, NULL, COLOR_OPT}, {"exclude", required_argument, NULL, R_EXCLUDE_OPT}, {"include", required_argument, NULL, R_INCLUDE_OPT}, {"exclude-dir", required_argument, NULL, R_DEXCLUDE_OPT}, {"include-dir", required_argument, NULL, R_DINCLUDE_OPT}, {"after-context", required_argument, NULL, 'A'}, {"text", no_argument, NULL, 'a'}, {"before-context", required_argument, NULL, 'B'}, {"byte-offset", no_argument, NULL, 'b'}, {"context", optional_argument, NULL, 'C'}, {"count", no_argument, NULL, 'c'}, {"devices", required_argument, NULL, 'D'}, {"directories", required_argument, NULL, 'd'}, {"extended-regexp", no_argument, NULL, 'E'}, {"regexp", required_argument, NULL, 'e'}, {"fixed-strings", no_argument, NULL, 'F'}, {"file", required_argument, NULL, 'f'}, {"basic-regexp", no_argument, NULL, 'G'}, {"no-filename", no_argument, NULL, 'h'}, {"with-filename", no_argument, NULL, 'H'}, {"ignore-case", no_argument, NULL, 'i'}, {"bz2decompress", no_argument, NULL, 'J'}, {"files-with-matches", no_argument, NULL, 'l'}, {"files-without-match", no_argument, NULL, 'L'}, {"max-count", required_argument, NULL, 'm'}, {"lzma", no_argument, NULL, 'M'}, {"line-number", no_argument, NULL, 'n'}, {"only-matching", no_argument, NULL, 'o'}, {"quiet", no_argument, NULL, 'q'}, {"silent", no_argument, NULL, 'q'}, {"recursive", no_argument, NULL, 'r'}, {"no-messages", no_argument, NULL, 's'}, {"binary", no_argument, NULL, 'U'}, {"unix-byte-offsets", no_argument, NULL, 'u'}, {"invert-match", no_argument, NULL, 'v'}, {"version", no_argument, NULL, 'V'}, {"word-regexp", no_argument, NULL, 'w'}, {"line-regexp", no_argument, NULL, 'x'}, {"xz", no_argument, NULL, 'X'}, {"decompress", no_argument, NULL, 'Z'}, {NULL, no_argument, NULL, 0} }; /* * Adds a searching pattern to the internal array. */ static void add_pattern(char *pat, size_t len) { /* Do not add further pattern is we already match everything */ if (matchall) return; /* Check if we can do a shortcut */ if (len == 0) { matchall = true; for (unsigned int i = 0; i < patterns; i++) { free(pattern[i].pat); } pattern = grep_realloc(pattern, sizeof(struct pat)); pattern[0].pat = NULL; pattern[0].len = 0; patterns = 1; return; } /* Increase size if necessary */ if (patterns == pattern_sz) { pattern_sz *= 2; pattern = grep_realloc(pattern, ++pattern_sz * sizeof(struct pat)); } if (len > 0 && pat[len - 1] == '\n') --len; /* pat may not be NUL-terminated */ pattern[patterns].pat = grep_malloc(len + 1); memcpy(pattern[patterns].pat, pat, len); pattern[patterns].len = len; pattern[patterns].pat[len] = '\0'; ++patterns; } /* * Adds a file include/exclude pattern to the internal array. */ static void add_fpattern(const char *pat, int mode) { /* Increase size if necessary */ if (fpatterns == fpattern_sz) { fpattern_sz *= 2; fpattern = grep_realloc(fpattern, ++fpattern_sz * sizeof(struct epat)); } fpattern[fpatterns].pat = grep_strdup(pat); fpattern[fpatterns].mode = mode; ++fpatterns; } /* * Adds a directory include/exclude pattern to the internal array. */ static void add_dpattern(const char *pat, int mode) { /* Increase size if necessary */ if (dpatterns == dpattern_sz) { dpattern_sz *= 2; dpattern = grep_realloc(dpattern, ++dpattern_sz * sizeof(struct epat)); } dpattern[dpatterns].pat = grep_strdup(pat); dpattern[dpatterns].mode = mode; ++dpatterns; } /* * Reads searching patterns from a file and adds them with add_pattern(). */ static void read_patterns(const char *fn) { struct stat st; FILE *f; char *line; size_t len; ssize_t rlen; if ((f = fopen(fn, "r")) == NULL) err(2, "%s", fn); if ((fstat(fileno(f), &st) == -1) || (S_ISDIR(st.st_mode))) { fclose(f); return; } len = 0; line = NULL; while ((rlen = getline(&line, &len, f)) != -1) add_pattern(line, line[0] == '\n' ? 0 : (size_t)rlen); free(line); if (ferror(f)) err(2, "%s", fn); fclose(f); } static inline const char * init_color(const char *d) { char *c; c = getenv("GREP_COLOR"); return (c != NULL && c[0] != '\0' ? c : d); } int main(int argc, char *argv[]) { char **aargv, **eargv, *eopts; char *ep; const char *pn; unsigned long long l; unsigned int aargc, eargc, i; int c, lastc, needpattern, newarg, prevoptind; setlocale(LC_ALL, ""); #ifndef WITHOUT_NLS catalog = catopen("grep", NL_CAT_LOCALE); #endif /* Check what is the program name of the binary. In this way we can have all the funcionalities in one binary without the need of scripting and using ugly hacks. */ pn = getprogname(); if (pn[0] == 'b' && pn[1] == 'z') { filebehave = FILE_BZIP; pn += 2; } else if (pn[0] == 'x' && pn[1] == 'z') { filebehave = FILE_XZ; pn += 2; } else if (pn[0] == 'l' && pn[1] == 'z') { filebehave = FILE_LZMA; pn += 2; } else if (pn[0] == 'z') { filebehave = FILE_GZIP; pn += 1; } switch (pn[0]) { case 'e': grepbehave = GREP_EXTENDED; break; case 'f': grepbehave = GREP_FIXED; break; } lastc = '\0'; newarg = 1; prevoptind = 1; needpattern = 1; eopts = getenv("GREP_OPTIONS"); /* support for extra arguments in GREP_OPTIONS */ eargc = 0; if (eopts != NULL && eopts[0] != '\0') { char *str; /* make an estimation of how many extra arguments we have */ for (unsigned int j = 0; j < strlen(eopts); j++) if (eopts[j] == ' ') eargc++; eargv = (char **)grep_malloc(sizeof(char *) * (eargc + 1)); eargc = 0; /* parse extra arguments */ while ((str = strsep(&eopts, " ")) != NULL) if (str[0] != '\0') eargv[eargc++] = grep_strdup(str); aargv = (char **)grep_calloc(eargc + argc + 1, sizeof(char *)); aargv[0] = argv[0]; for (i = 0; i < eargc; i++) aargv[i + 1] = eargv[i]; for (int j = 1; j < argc; j++, i++) aargv[i + 1] = argv[j]; aargc = eargc + argc; } else { aargv = argv; aargc = argc; } while (((c = getopt_long(aargc, aargv, optstr, long_options, NULL)) != -1)) { switch (c) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if (newarg || !isdigit(lastc)) Aflag = 0; else if (Aflag > LLONG_MAX / 10) { errno = ERANGE; err(2, NULL); } Aflag = Bflag = (Aflag * 10) + (c - '0'); break; case 'C': if (optarg == NULL) { Aflag = Bflag = 2; break; } /* FALLTHROUGH */ case 'A': /* FALLTHROUGH */ case 'B': errno = 0; l = strtoull(optarg, &ep, 10); if (((errno == ERANGE) && (l == ULLONG_MAX)) || ((errno == EINVAL) && (l == 0))) err(2, NULL); else if (ep[0] != '\0') { errno = EINVAL; err(2, NULL); } if (c == 'A') Aflag = l; else if (c == 'B') Bflag = l; else Aflag = Bflag = l; break; case 'a': binbehave = BINFILE_TEXT; break; case 'b': bflag = true; break; case 'c': cflag = true; break; case 'D': if (strcasecmp(optarg, "skip") == 0) devbehave = DEV_SKIP; else if (strcasecmp(optarg, "read") == 0) devbehave = DEV_READ; else errx(2, getstr(3), "--devices"); break; case 'd': if (strcasecmp("recurse", optarg) == 0) { Hflag = true; dirbehave = DIR_RECURSE; } else if (strcasecmp("skip", optarg) == 0) dirbehave = DIR_SKIP; else if (strcasecmp("read", optarg) == 0) dirbehave = DIR_READ; else errx(2, getstr(3), "--directories"); break; case 'E': grepbehave = GREP_EXTENDED; break; case 'e': { char *token; char *string = optarg; while ((token = strsep(&string, "\n")) != NULL) add_pattern(token, strlen(token)); } needpattern = 0; break; case 'F': grepbehave = GREP_FIXED; break; case 'f': read_patterns(optarg); needpattern = 0; break; case 'G': grepbehave = GREP_BASIC; break; case 'H': Hflag = true; break; case 'h': Hflag = false; hflag = true; break; case 'I': binbehave = BINFILE_SKIP; break; case 'i': case 'y': iflag = true; cflags |= REG_ICASE; break; case 'J': #ifdef WITHOUT_BZIP2 errno = EOPNOTSUPP; err(2, "bzip2 support was disabled at compile-time"); #endif filebehave = FILE_BZIP; break; case 'L': lflag = false; Lflag = true; break; case 'l': Lflag = false; lflag = true; break; case 'm': mflag = true; errno = 0; mlimit = mcount = strtoll(optarg, &ep, 10); if (((errno == ERANGE) && (mcount == LLONG_MAX)) || ((errno == EINVAL) && (mcount == 0))) err(2, NULL); else if (ep[0] != '\0') { errno = EINVAL; err(2, NULL); } break; case 'M': filebehave = FILE_LZMA; break; case 'n': nflag = true; break; case 'O': linkbehave = LINK_EXPLICIT; break; case 'o': oflag = true; cflags &= ~REG_NOSUB; break; case 'p': linkbehave = LINK_SKIP; break; case 'q': qflag = true; break; case 'S': linkbehave = LINK_READ; break; case 'R': case 'r': dirbehave = DIR_RECURSE; Hflag = true; break; case 's': sflag = true; break; case 'U': binbehave = BINFILE_BIN; break; case 'u': case MMAP_OPT: filebehave = FILE_MMAP; break; case 'V': printf(getstr(9), getprogname(), VERSION); exit(0); case 'v': vflag = true; break; case 'w': wflag = true; cflags &= ~REG_NOSUB; break; case 'x': xflag = true; cflags &= ~REG_NOSUB; break; case 'X': filebehave = FILE_XZ; break; case 'Z': filebehave = FILE_GZIP; break; case BIN_OPT: if (strcasecmp("binary", optarg) == 0) binbehave = BINFILE_BIN; else if (strcasecmp("without-match", optarg) == 0) binbehave = BINFILE_SKIP; else if (strcasecmp("text", optarg) == 0) binbehave = BINFILE_TEXT; else errx(2, getstr(3), "--binary-files"); break; case COLOR_OPT: color = NULL; if (optarg == NULL || strcasecmp("auto", optarg) == 0 || strcasecmp("tty", optarg) == 0 || strcasecmp("if-tty", optarg) == 0) { char *term; term = getenv("TERM"); if (isatty(STDOUT_FILENO) && term != NULL && strcasecmp(term, "dumb") != 0) color = init_color("01;31"); } else if (strcasecmp("always", optarg) == 0 || strcasecmp("yes", optarg) == 0 || strcasecmp("force", optarg) == 0) { color = init_color("01;31"); } else if (strcasecmp("never", optarg) != 0 && strcasecmp("none", optarg) != 0 && strcasecmp("no", optarg) != 0) errx(2, getstr(3), "--color"); cflags &= ~REG_NOSUB; break; case LABEL_OPT: label = optarg; break; case LINEBUF_OPT: lbflag = true; break; case NULL_OPT: nullflag = true; break; case R_INCLUDE_OPT: finclude = true; add_fpattern(optarg, INCL_PAT); break; case R_EXCLUDE_OPT: fexclude = true; add_fpattern(optarg, EXCL_PAT); break; case R_DINCLUDE_OPT: dinclude = true; add_dpattern(optarg, INCL_PAT); break; case R_DEXCLUDE_OPT: dexclude = true; add_dpattern(optarg, EXCL_PAT); break; case HELP_OPT: default: usage(); } lastc = c; newarg = optind != prevoptind; prevoptind = optind; } aargc -= optind; aargv += optind; /* Empty pattern file matches nothing */ if (!needpattern && (patterns == 0)) exit(1); /* Fail if we don't have any pattern */ if (aargc == 0 && needpattern) usage(); /* Process patterns from command line */ if (aargc != 0 && needpattern) { char *token; char *string = *aargv; while ((token = strsep(&string, "\n")) != NULL) add_pattern(token, strlen(token)); --aargc; ++aargv; } switch (grepbehave) { case GREP_BASIC: break; case GREP_FIXED: /* XXX: header mess, REG_LITERAL not defined in gnu/regex.h */ cflags |= 0020; break; case GREP_EXTENDED: cflags |= REG_EXTENDED; break; default: /* NOTREACHED */ usage(); } fg_pattern = grep_calloc(patterns, sizeof(*fg_pattern)); r_pattern = grep_calloc(patterns, sizeof(*r_pattern)); /* Check if cheating is allowed (always is for fgrep). */ for (i = 0; i < patterns; ++i) { if (fastncomp(&fg_pattern[i], pattern[i].pat, pattern[i].len, cflags) != 0) { /* Fall back to full regex library */ c = regcomp(&r_pattern[i], pattern[i].pat, cflags); if (c != 0) { regerror(c, &r_pattern[i], re_error, RE_ERROR_BUF); errx(2, "%s", re_error); } } } if (lbflag) setlinebuf(stdout); if ((aargc == 0 || aargc == 1) && !Hflag) hflag = true; if (aargc == 0) exit(!procfile("-")); if (dirbehave == DIR_RECURSE) c = grep_tree(aargv); else for (c = 0; aargc--; ++aargv) { if ((finclude || fexclude) && !file_matching(*aargv)) continue; c+= procfile(*aargv); } #ifndef WITHOUT_NLS catclose(catalog); #endif /* Find out the correct return value according to the results and the command line option. */ exit(c ? (file_err ? (qflag ? 0 : 2) : 0) : (file_err ? 2 : 1)); } Index: stable/9/usr.bin/grep/regex/glue.h =================================================================== --- stable/9/usr.bin/grep/regex/glue.h (revision 303882) +++ stable/9/usr.bin/grep/regex/glue.h (revision 303883) @@ -1,67 +1,67 @@ /* $FreeBSD$ */ #ifndef GLUE_H #define GLUE_H #include #undef RE_DUP_MAX #include #include #include #define TRE_WCHAR 1 #define TRE_MULTIBYTE 1 #define HAVE_MBSTATE_T 1 #define TRE_CHAR(n) L##n #define CHF "%lc" #define tre_char_t wchar_t #define tre_mbrtowc(pwc, s, n, ps) (mbrtowc((pwc), (s), (n), (ps))) #define tre_strlen wcslen #define tre_isspace iswspace #define tre_isalnum iswalnum #define REG_OK 0 #define REG_LITERAL 0020 #define REG_WORD 0100 #define REG_GNU 0400 #define TRE_MB_CUR_MAX MB_CUR_MAX #ifndef _GREP_DEBUG #define DPRINT(msg) #else #define DPRINT(msg) do {printf msg; fflush(stdout);} while(/*CONSTCOND*/0) #endif #define MIN(a,b) ((a > b) ? (b) : (a)) #define MAX(a,b) ((a > b) ? (a) : (b)) typedef enum { STR_WIDE, STR_BYTE, STR_MBS, STR_USER } tre_str_type_t; #define CALL_WITH_OFFSET(fn) \ do \ { \ size_t slen = (size_t)(pmatch[0].rm_eo - pmatch[0].rm_so); \ size_t offset = pmatch[0].rm_so; \ int ret; \ \ if ((long long)pmatch[0].rm_eo - pmatch[0].rm_so < 0) \ return REG_NOMATCH; \ ret = fn; \ - for (unsigned i = 0; (!(eflags & REG_NOSUB) && (i < nmatch)); i++)\ + for (unsigned i = 0; (!preg->nosub && (i < nmatch)); i++) \ { \ pmatch[i].rm_so += offset; \ pmatch[i].rm_eo += offset; \ } \ return ret; \ } while (0 /*CONSTCOND*/) int tre_convert_pattern(const char *regex, size_t n, tre_char_t **w, size_t *wn); void tre_free_pattern(tre_char_t *wregex); #endif Index: stable/9/usr.bin/grep/regex/tre-fastmatch.c =================================================================== --- stable/9/usr.bin/grep/regex/tre-fastmatch.c (revision 303882) +++ stable/9/usr.bin/grep/regex/tre-fastmatch.c (revision 303883) @@ -1,1042 +1,1042 @@ /* $FreeBSD$ */ /*- * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav * Copyright (C) 2008-2011 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include "glue.h" #include #include #include #include #include #include #ifdef TRE_WCHAR #include #include #endif #include "hashtable.h" #include "tre-fastmatch.h" #include "xmalloc.h" static int fastcmp(const fastmatch_t *fg, const void *data, tre_str_type_t type); /* * Clean up if pattern compilation fails. */ #define FAIL_COMP(errcode) \ { \ if (fg->pattern) \ xfree(fg->pattern); \ if (fg->wpattern) \ xfree(fg->wpattern); \ if (fg->qsBc_table) \ hashtable_free(fg->qsBc_table); \ fg = NULL; \ return errcode; \ } /* * Skips n characters in the input string and assigns the start * address to startptr. Note: as per IEEE Std 1003.1-2008 * matching is based on bit pattern not character representations * so we can handle MB strings as byte sequences just like * SB strings. */ #define SKIP_CHARS(n) \ switch (type) \ { \ case STR_WIDE: \ startptr = str_wide + n; \ break; \ default: \ startptr = str_byte + n; \ } /* * Converts the wide string pattern to SB/MB string and stores * it in fg->pattern. Sets fg->len to the byte length of the * converted string. */ #define STORE_MBS_PAT \ { \ size_t siz; \ \ siz = wcstombs(NULL, fg->wpattern, 0); \ if (siz == (size_t)-1) \ return REG_BADPAT; \ fg->len = siz; \ fg->pattern = xmalloc(siz + 1); \ if (fg->pattern == NULL) \ return REG_ESPACE; \ wcstombs(fg->pattern, fg->wpattern, siz); \ fg->pattern[siz] = '\0'; \ } \ #define IS_OUT_OF_BOUNDS \ ((!fg->reversed \ ? ((type == STR_WIDE) ? ((j + fg->wlen) > len) \ : ((j + fg->len) > len)) \ : (j < 0))) /* * Checks whether the new position after shifting in the input string * is out of the bounds and break out from the loop if so. */ #define CHECKBOUNDS \ if (IS_OUT_OF_BOUNDS) \ break; \ /* * Shifts in the input string after a mismatch. The position of the * mismatch is stored in the mismatch variable. */ #define SHIFT \ CHECKBOUNDS; \ \ { \ int r = -1; \ unsigned int bc = 0, gs = 0, ts; \ \ switch (type) \ { \ case STR_WIDE: \ if (!fg->hasdot) \ { \ if (u != 0 && (unsigned)mismatch == fg->wlen - 1 - shift) \ mismatch -= u; \ v = fg->wlen - 1 - mismatch; \ r = hashtable_get(fg->qsBc_table, \ &str_wide[!fg->reversed ? (size_t)j + fg->wlen \ : (size_t)j - 1], &bc); \ gs = fg->bmGs[mismatch]; \ } \ bc = (r == HASH_OK) ? bc : fg->defBc; \ DPRINT(("tre_fast_match: mismatch on character" CHF ", " \ "BC %d, GS %d\n", \ ((const tre_char_t *)startptr)[mismatch + 1], \ bc, gs)); \ break; \ default: \ if (!fg->hasdot) \ { \ if (u != 0 && (unsigned)mismatch == fg->len - 1 - shift) \ mismatch -= u; \ v = fg->len - 1 - mismatch; \ gs = fg->sbmGs[mismatch]; \ } \ bc = fg->qsBc[((const unsigned char *)str_byte) \ [!fg->reversed ? (size_t)j + fg->len \ : (size_t)j - 1]]; \ DPRINT(("tre_fast_match: mismatch on character %c, " \ "BC %d, GS %d\n", \ ((const unsigned char *)startptr)[mismatch + 1], \ bc, gs)); \ } \ if (fg->hasdot) \ shift = bc; \ else \ { \ ts = (u >= v) ? (u - v) : 0; \ shift = MAX(ts, bc); \ shift = MAX(shift, gs); \ if (shift == gs) \ u = MIN((type == STR_WIDE ? fg->wlen : fg->len) - shift, v); \ else \ { \ if (ts < bc) \ shift = MAX(shift, u + 1); \ u = 0; \ } \ } \ DPRINT(("tre_fast_match: shifting %u characters\n", shift)); \ j = !fg->reversed ? j + shift : j - shift; \ } /* * Normal Quick Search would require a shift based on the position the * next character after the comparison is within the pattern. With * wildcards, the position of the last dot effects the maximum shift * distance. * The closer to the end the wild card is the slower the search. * * Examples: * Pattern Max shift * ------- --------- * this 5 * .his 4 * t.is 3 * th.s 2 * thi. 1 */ /* * Fills in the bad character shift array for SB/MB strings. */ #define FILL_QSBC \ if (fg->reversed) \ { \ _FILL_QSBC_REVERSED \ } \ else \ { \ _FILL_QSBC \ } #define _FILL_QSBC \ for (unsigned int i = 0; i <= UCHAR_MAX; i++) \ fg->qsBc[i] = fg->len - hasdot; \ for (unsigned int i = hasdot + 1; i < fg->len; i++) \ { \ fg->qsBc[(unsigned char)fg->pattern[i]] = fg->len - i; \ DPRINT(("BC shift for char %c is %zu\n", fg->pattern[i], \ fg->len - i)); \ if (fg->icase) \ { \ char c = islower((unsigned char)fg->pattern[i]) ? \ toupper((unsigned char)fg->pattern[i]) : \ tolower((unsigned char)fg->pattern[i]); \ fg->qsBc[(unsigned char)c] = fg->len - i; \ DPRINT(("BC shift for char %c is %zu\n", c, fg->len - i)); \ } \ } #define _FILL_QSBC_REVERSED \ for (unsigned int i = 0; i <= UCHAR_MAX; i++) \ fg->qsBc[i] = firstdot + 1; \ for (int i = firstdot - 1; i >= 0; i--) \ { \ fg->qsBc[(unsigned char)fg->pattern[i]] = i + 1; \ DPRINT(("Reverse BC shift for char %c is %d\n", fg->pattern[i], \ i + 1)); \ if (fg->icase) \ { \ char c = islower((unsigned char)fg->pattern[i]) ? \ toupper((unsigned char)fg->pattern[i]) : \ tolower((unsigned char)fg->pattern[i]); \ fg->qsBc[(unsigned char)c] = i + 1; \ DPRINT(("Reverse BC shift for char %c is %d\n", c, i + 1)); \ } \ } /* * Fills in the bad character shifts into a hastable for wide strings. * With wide characters it is not possible any more to use a normal * array because there are too many characters and we could not * provide enough memory. Fortunately, we only have to store distinct * values for so many characters as the number of distinct characters * in the pattern, so we can store them in a hashtable and store a * default shift value for the rest. */ #define FILL_QSBC_WIDE \ if (fg->reversed) \ { \ _FILL_QSBC_WIDE_REVERSED \ } \ else \ { \ _FILL_QSBC_WIDE \ } #define _FILL_QSBC_WIDE \ /* Adjust the shift based on location of the last dot ('.'). */ \ fg->defBc = fg->wlen - whasdot; \ \ /* Preprocess pattern. */ \ fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \ sizeof(tre_char_t), sizeof(int)); \ if (!fg->qsBc_table) \ FAIL_COMP(REG_ESPACE); \ for (unsigned int i = whasdot + 1; i < fg->wlen; i++) \ { \ int k = fg->wlen - i; \ int r; \ \ r = hashtable_put(fg->qsBc_table, &fg->wpattern[i], &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("BC shift for wide char " CHF " is %d\n", fg->wpattern[i],\ k)); \ if (fg->icase) \ { \ tre_char_t wc = iswlower(fg->wpattern[i]) ? \ towupper(fg->wpattern[i]) : towlower(fg->wpattern[i]); \ r = hashtable_put(fg->qsBc_table, &wc, &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("BC shift for wide char " CHF " is %d\n", wc, k)); \ } \ } #define _FILL_QSBC_WIDE_REVERSED \ /* Adjust the shift based on location of the last dot ('.'). */ \ fg->defBc = (size_t)wfirstdot; \ \ /* Preprocess pattern. */ \ fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \ sizeof(tre_char_t), sizeof(int)); \ if (!fg->qsBc_table) \ FAIL_COMP(REG_ESPACE); \ for (int i = wfirstdot - 1; i >= 0; i--) \ { \ int k = i + 1; \ int r; \ \ r = hashtable_put(fg->qsBc_table, &fg->wpattern[i], &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("Reverse BC shift for wide char " CHF " is %d\n", \ fg->wpattern[i], k)); \ if (fg->icase) \ { \ tre_char_t wc = iswlower(fg->wpattern[i]) ? \ towupper(fg->wpattern[i]) : towlower(fg->wpattern[i]); \ r = hashtable_put(fg->qsBc_table, &wc, &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("Reverse BC shift for wide char " CHF " is %d\n", wc, \ k)); \ } \ } #ifdef _GREP_DEBUG #define DPRINT_BMGS(len, fmt_str, sh) \ for (unsigned int i = 0; i < len; i++) \ DPRINT((fmt_str, i, sh[i])); #else #define DPRINT_BMGS(len, fmt_str, sh) \ do { } while(/*CONSTCOND*/0) #endif /* * Fills in the good suffix table for SB/MB strings. */ #define FILL_BMGS \ if (!fg->hasdot) \ { \ fg->sbmGs = xmalloc(fg->len * sizeof(int)); \ if (!fg->sbmGs) \ return REG_ESPACE; \ if (fg->len == 1) \ fg->sbmGs[0] = 1; \ else \ _FILL_BMGS(fg->sbmGs, fg->pattern, fg->len, false); \ DPRINT_BMGS(fg->len, "GS shift for pos %d is %d\n", fg->sbmGs); \ } /* * Fills in the good suffix table for wide strings. */ #define FILL_BMGS_WIDE \ if (!fg->hasdot) \ { \ fg->bmGs = xmalloc(fg->wlen * sizeof(int)); \ if (!fg->bmGs) \ return REG_ESPACE; \ if (fg->wlen == 1) \ fg->bmGs[0] = 1; \ else \ _FILL_BMGS(fg->bmGs, fg->wpattern, fg->wlen, true); \ DPRINT_BMGS(fg->wlen, "GS shift (wide) for pos %d is %d\n", \ fg->bmGs); \ } #define _FILL_BMGS(arr, pat, plen, wide) \ { \ char *p; \ tre_char_t *wp; \ \ if (wide) \ { \ if (fg->icase) \ { \ wp = xmalloc(plen * sizeof(tre_char_t)); \ if (wp == NULL) \ return REG_ESPACE; \ for (unsigned int i = 0; i < plen; i++) \ wp[i] = towlower(pat[i]); \ _CALC_BMGS(arr, wp, plen); \ xfree(wp); \ } \ else \ _CALC_BMGS(arr, pat, plen); \ } \ else \ { \ if (fg->icase) \ { \ p = xmalloc(plen); \ if (p == NULL) \ return REG_ESPACE; \ for (unsigned int i = 0; i < plen; i++) \ p[i] = tolower((unsigned char)pat[i]); \ _CALC_BMGS(arr, p, plen); \ xfree(p); \ } \ else \ _CALC_BMGS(arr, pat, plen); \ } \ } #define _CALC_BMGS(arr, pat, plen) \ { \ int f = 0, g; \ \ int *suff = xmalloc(plen * sizeof(int)); \ if (suff == NULL) \ return REG_ESPACE; \ \ suff[plen - 1] = plen; \ g = plen - 1; \ for (int i = plen - 2; i >= 0; i--) \ { \ if (i > g && suff[i + plen - 1 - f] < i - g) \ suff[i] = suff[i + plen - 1 - f]; \ else \ { \ if (i < g) \ g = i; \ f = i; \ while (g >= 0 && pat[g] == pat[g + plen - 1 - f]) \ g--; \ suff[i] = f - g; \ } \ } \ \ for (unsigned int i = 0; i < plen; i++) \ arr[i] = plen; \ g = 0; \ for (int i = plen - 1; i >= 0; i--) \ if (suff[i] == i + 1) \ for(; (unsigned long)g < plen - 1 - i; g++) \ if (arr[g] == plen) \ arr[g] = plen - 1 - i; \ for (unsigned int i = 0; i <= plen - 2; i++) \ arr[plen - 1 - suff[i]] = plen - 1 - i; \ \ xfree(suff); \ } /* * Copies the pattern pat having length n to p and stores * the size in l. */ #define SAVE_PATTERN(src, srclen, dst, dstlen) \ dstlen = srclen; \ dst = xmalloc((dstlen + 1) * sizeof(tre_char_t)); \ if (dst == NULL) \ return REG_ESPACE; \ if (dstlen > 0) \ memcpy(dst, src, dstlen * sizeof(tre_char_t)); \ dst[dstlen] = TRE_CHAR('\0'); /* * Initializes pattern compiling. */ #define INIT_COMP \ /* Initialize. */ \ memset(fg, 0, sizeof(*fg)); \ fg->icase = (cflags & REG_ICASE); \ fg->word = (cflags & REG_WORD); \ fg->newline = (cflags & REG_NEWLINE); \ fg->nosub = (cflags & REG_NOSUB); \ \ /* Cannot handle REG_ICASE with MB string */ \ if (fg->icase && (TRE_MB_CUR_MAX > 1) && n > 0) \ { \ DPRINT(("Cannot use fast matcher for MBS with REG_ICASE\n")); \ return REG_BADPAT; \ } /* * Checks whether we have a 0-length pattern that will match * anything. If literal is set to false, the EOL anchor is also * taken into account. */ #define CHECK_MATCHALL(literal) \ if (!literal && n == 1 && pat[0] == TRE_CHAR('$')) \ { \ n--; \ fg->eol = true; \ } \ \ if (n == 0) \ { \ fg->matchall = true; \ fg->pattern = xmalloc(sizeof(char)); \ if (!fg->pattern) \ FAIL_COMP(REG_ESPACE); \ fg->pattern[0] = '\0'; \ fg->wpattern = xmalloc(sizeof(tre_char_t)); \ if (!fg->wpattern) \ FAIL_COMP(REG_ESPACE); \ fg->wpattern[0] = TRE_CHAR('\0'); \ DPRINT(("Matching every input\n")); \ return REG_OK; \ } /* * Returns: REG_OK on success, error code otherwise */ int tre_compile_literal(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) { size_t hasdot = 0, whasdot = 0; ssize_t firstdot = -1, wfirstdot = -1; INIT_COMP; CHECK_MATCHALL(true); /* Cannot handle word boundaries with MB string */ if (fg->word && (TRE_MB_CUR_MAX > 1)) return REG_BADPAT; #ifdef TRE_WCHAR SAVE_PATTERN(pat, n, fg->wpattern, fg->wlen); STORE_MBS_PAT; #else SAVE_PATTERN(pat, n, fg->pattern, fg->len); #endif DPRINT(("tre_compile_literal: pattern: %s, len %zu, icase: %c, word: %c, " "newline %c\n", fg->pattern, fg->len, fg->icase ? 'y' : 'n', fg->word ? 'y' : 'n', fg->newline ? 'y' : 'n')); FILL_QSBC; FILL_BMGS; #ifdef TRE_WCHAR FILL_QSBC_WIDE; FILL_BMGS_WIDE; #endif return REG_OK; } /* * Returns: REG_OK on success, error code otherwise */ int tre_compile_fast(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) { tre_char_t *tmp; size_t pos = 0, hasdot = 0, whasdot = 0; ssize_t firstdot = -1, wfirstdot = -1; bool escaped = false; bool *_escmap = NULL; INIT_COMP; /* Remove beginning-of-line character ('^'). */ if (pat[0] == TRE_CHAR('^')) { fg->bol = true; n--; pat++; } CHECK_MATCHALL(false); /* Handle word-boundary matching when GNU extensions are enabled */ if ((cflags & REG_GNU) && (n >= 14) && (memcmp(pat, TRE_CHAR("[[:<:]]"), 7 * sizeof(tre_char_t)) == 0) && (memcmp(pat + n - 7, TRE_CHAR("[[:>:]]"), 7 * sizeof(tre_char_t)) == 0)) { n -= 14; pat += 7; fg->word = true; } /* Cannot handle word boundaries with MB string */ if (fg->word && (TRE_MB_CUR_MAX > 1)) return REG_BADPAT; tmp = xmalloc((n + 1) * sizeof(tre_char_t)); if (tmp == NULL) return REG_ESPACE; /* Copies the char into the stored pattern and skips to the next char. */ #define STORE_CHAR \ do \ { \ tmp[pos++] = pat[i]; \ escaped = false; \ continue; \ } while (0) /* Traverse the input pattern for processing */ for (unsigned int i = 0; i < n; i++) { switch (pat[i]) { case TRE_CHAR('\\'): if (escaped) STORE_CHAR; else if (i == n - 1) goto badpat; else escaped = true; continue; case TRE_CHAR('['): if (escaped) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('*'): if (escaped || (!(cflags & REG_EXTENDED) && (i == 0))) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('+'): case TRE_CHAR('?'): if ((cflags & REG_EXTENDED) && (i == 0)) - continue; + goto badpat; else if ((cflags & REG_EXTENDED) ^ !escaped) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('.'): if (escaped) { if (!_escmap) _escmap = xmalloc(n * sizeof(bool)); if (!_escmap) { xfree(tmp); return REG_ESPACE; } _escmap[i] = true; STORE_CHAR; } else { whasdot = i; if (wfirstdot == -1) wfirstdot = i; STORE_CHAR; } continue; case TRE_CHAR('^'): STORE_CHAR; continue; case TRE_CHAR('$'): if (!escaped && (i == n - 1)) fg->eol = true; else STORE_CHAR; continue; case TRE_CHAR('('): if ((cflags & REG_EXTENDED) ^ escaped) goto badpat; else STORE_CHAR; continue; case TRE_CHAR('{'): if (!(cflags & REG_EXTENDED) ^ escaped) STORE_CHAR; else if (!(cflags & REG_EXTENDED) && (i == 0)) STORE_CHAR; else if ((cflags & REG_EXTENDED) && (i == 0)) continue; else goto badpat; continue; case TRE_CHAR('|'): if ((cflags & REG_EXTENDED) ^ escaped) goto badpat; else STORE_CHAR; continue; default: if (escaped) goto badpat; else STORE_CHAR; continue; } continue; badpat: xfree(tmp); DPRINT(("tre_compile_fast: compilation of pattern failed, falling" "back to NFA\n")); return REG_BADPAT; } fg->hasdot = wfirstdot > -1; /* * The pattern has been processed and copied to tmp as a literal string * with escapes, anchors (^$) and the word boundary match character * classes stripped out. */ #ifdef TRE_WCHAR SAVE_PATTERN(tmp, pos, fg->wpattern, fg->wlen); fg->wescmap = _escmap; STORE_MBS_PAT; /* * The position of dots and escaped dots is different in the MB string * than in to the wide string so traverse the converted string, as well, * to store these positions. */ if (fg->hasdot || (fg->wescmap != NULL)) { if (fg->wescmap != NULL) { fg->escmap = xmalloc(fg->len * sizeof(bool)); if (!fg->escmap) { tre_free_fast(fg); return REG_ESPACE; } } escaped = false; for (unsigned int i = 0; i < fg->len; i++) if (fg->pattern[i] == '\\') escaped = !escaped; else if (fg->pattern[i] == '.' && fg->escmap && escaped) { fg->escmap[i] = true; escaped = false; } else if (fg->pattern[i] == '.' && !escaped) { hasdot = i; if (firstdot == -1) firstdot = i; } else escaped = false; } #else SAVE_PATTERN(tmp, pos, fg->pattern, fg->len); fg->escmap = _escmap; #endif xfree(tmp); DPRINT(("tre_compile_fast: pattern: %s, len %zu, bol %c, eol %c, " "icase: %c, word: %c, newline %c\n", fg->pattern, fg->len, fg->bol ? 'y' : 'n', fg->eol ? 'y' : 'n', fg->icase ? 'y' : 'n', fg->word ? 'y' : 'n', fg->newline ? 'y' : 'n')); /* Check whether reverse QS algorithm is more efficient */ if ((wfirstdot > -1) && (fg->wlen - whasdot + 1 < (size_t)wfirstdot) && fg->nosub) { fg->reversed = true; DPRINT(("tre_compile_fast: using reverse QS algorithm\n")); } FILL_QSBC; FILL_BMGS; #ifdef TRE_WCHAR FILL_QSBC_WIDE; FILL_BMGS_WIDE; #endif return REG_OK; } #define _SHIFT_ONE \ { \ shift = 1; \ j = !fg->reversed ? j + shift : j - shift; \ continue; \ } #define _BBOUND_COND \ ((type == STR_WIDE) ? \ ((j == 0) || !(tre_isalnum(str_wide[j - 1]) || \ (str_wide[j - 1] == TRE_CHAR('_')))) : \ ((j == 0) || !(tre_isalnum(str_byte[j - 1]) || \ (str_byte[j - 1] == '_')))) #define _EBOUND_COND \ ((type == STR_WIDE) ? \ ((j + fg->wlen == len) || !(tre_isalnum(str_wide[j + fg->wlen]) || \ (str_wide[j + fg->wlen] == TRE_CHAR('_')))) : \ ((j + fg->len == len) || !(tre_isalnum(str_byte[j + fg->len]) || \ (str_byte[j + fg->len] == '_')))) /* * Condition to check whether the match on position j is on a * word boundary. */ #define IS_ON_WORD_BOUNDARY \ (_BBOUND_COND && _EBOUND_COND) /* * Checks word boundary and shifts one if match is not on a * boundary. */ #define CHECK_WORD_BOUNDARY \ if (!IS_ON_WORD_BOUNDARY) \ _SHIFT_ONE; #define _BOL_COND \ ((j == 0) || ((type == STR_WIDE) ? (str_wide[j - 1] == TRE_CHAR('\n'))\ : (str_byte[j - 1] == '\n'))) /* * Checks BOL anchor and shifts one if match is not on a * boundary. */ #define CHECK_BOL_ANCHOR \ if (!_BOL_COND) \ _SHIFT_ONE; #define _EOL_COND \ ((type == STR_WIDE) \ ? ((j + fg->wlen == len) || \ (str_wide[j + fg->wlen] == TRE_CHAR('\n'))) \ : ((j + fg->len == len) || (str_byte[j + fg->wlen] == '\n'))) /* * Checks EOL anchor and shifts one if match is not on a * boundary. */ #define CHECK_EOL_ANCHOR \ if (!_EOL_COND) \ _SHIFT_ONE; /* * Executes matching of the precompiled pattern on the input string. * Returns REG_OK or REG_NOMATCH depending on if we find a match or not. */ int tre_match_fast(const fastmatch_t *fg, const void *data, size_t len, tre_str_type_t type, int nmatch, regmatch_t pmatch[], int eflags) { unsigned int shift, u = 0, v = 0; ssize_t j = 0; int ret = REG_NOMATCH; int mismatch; const char *str_byte = data; const void *startptr = NULL; const tre_char_t *str_wide = data; /* Calculate length if unspecified. */ if (len == (size_t)-1) switch (type) { case STR_WIDE: len = tre_strlen(str_wide); break; default: len = strlen(str_byte); break; } /* Shortcut for empty pattern */ if (fg->matchall) { if (!fg->nosub && nmatch >= 1) { pmatch[0].rm_so = 0; pmatch[0].rm_eo = len; } if (fg->bol && fg->eol) return (len == 0) ? REG_OK : REG_NOMATCH; else return REG_OK; } /* No point in going farther if we do not have enough data. */ switch (type) { case STR_WIDE: if (len < fg->wlen) return ret; shift = fg->wlen; break; default: if (len < fg->len) return ret; shift = fg->len; } /* * REG_NOTBOL means not anchoring ^ to the beginning of the line, so we * can shift one because there can't be a match at the beginning. */ if (fg->bol && (eflags & REG_NOTBOL)) j = 1; /* * Like above, we cannot have a match at the very end when anchoring to * the end and REG_NOTEOL is specified. */ if (fg->eol && (eflags & REG_NOTEOL)) len--; if (fg->reversed) j = len - (type == STR_WIDE ? fg->wlen : fg->len); /* Only try once at the beginning or ending of the line. */ if ((fg->bol || fg->eol) && !fg->newline && !(eflags & REG_NOTBOL) && !(eflags & REG_NOTEOL)) { /* Simple text comparison. */ if (!((fg->bol && fg->eol) && (type == STR_WIDE ? (len != fg->wlen) : (len != fg->len)))) { /* Determine where in data to start search at. */ j = fg->eol ? len - (type == STR_WIDE ? fg->wlen : fg->len) : 0; SKIP_CHARS(j); mismatch = fastcmp(fg, startptr, type); if (mismatch == REG_OK) { if (fg->word && !IS_ON_WORD_BOUNDARY) return ret; if (!fg->nosub && nmatch >= 1) { pmatch[0].rm_so = j; pmatch[0].rm_eo = j + (type == STR_WIDE ? fg->wlen : fg->len); } return REG_OK; } } } else { /* Quick Search / Turbo Boyer-Moore algorithm. */ do { SKIP_CHARS(j); mismatch = fastcmp(fg, startptr, type); if (mismatch == REG_OK) { if (fg->word) CHECK_WORD_BOUNDARY; if (fg->bol) CHECK_BOL_ANCHOR; if (fg->eol) CHECK_EOL_ANCHOR; if (!fg->nosub && nmatch >= 1) { pmatch[0].rm_so = j; pmatch[0].rm_eo = j + ((type == STR_WIDE) ? fg->wlen : fg->len); } return REG_OK; } else if (mismatch > 0) return mismatch; mismatch = -mismatch - 1; SHIFT; } while (!IS_OUT_OF_BOUNDS); } return ret; } /* * Frees the resources that were allocated when the pattern was compiled. */ void tre_free_fast(fastmatch_t *fg) { DPRINT(("tre_fast_free: freeing structures for pattern %s\n", fg->pattern)); #ifdef TRE_WCHAR hashtable_free(fg->qsBc_table); if (!fg->hasdot) xfree(fg->bmGs); if (fg->wescmap) xfree(fg->wescmap); xfree(fg->wpattern); #endif if (!fg->hasdot) xfree(fg->sbmGs); if (fg->escmap) xfree(fg->escmap); xfree(fg->pattern); } /* * Returns: -(i + 1) on failure (position that it failed with minus sign) * error code on error * REG_OK on success */ static inline int fastcmp(const fastmatch_t *fg, const void *data, tre_str_type_t type) { const char *str_byte = data; const char *pat_byte = fg->pattern; const tre_char_t *str_wide = data; const tre_char_t *pat_wide = fg->wpattern; const bool *escmap = (type == STR_WIDE) ? fg->wescmap : fg->escmap; size_t len = (type == STR_WIDE) ? fg->wlen : fg->len; int ret = REG_OK; /* Compare the pattern and the input char-by-char from the last position. */ for (int i = len - 1; i >= 0; i--) { switch (type) { case STR_WIDE: /* Check dot */ if (fg->hasdot && pat_wide[i] == TRE_CHAR('.') && (!escmap || !escmap[i]) && (!fg->newline || (str_wide[i] != TRE_CHAR('\n')))) continue; /* Compare */ if (fg->icase ? (towlower(pat_wide[i]) == towlower(str_wide[i])) : (pat_wide[i] == str_wide[i])) continue; break; default: /* Check dot */ if (fg->hasdot && pat_byte[i] == '.' && (!escmap || !escmap[i]) && (!fg->newline || (str_byte[i] != '\n'))) continue; /* Compare */ if (fg->icase ? (tolower((unsigned char)pat_byte[i]) == tolower((unsigned char)str_byte[i])) : (pat_byte[i] == str_byte[i])) continue; } DPRINT(("fastcmp: mismatch at position %d\n", i)); ret = -(i + 1); break; } return ret; } Index: stable/9/usr.bin/grep/regex/xmalloc.c =================================================================== --- stable/9/usr.bin/grep/regex/xmalloc.c (revision 303882) +++ stable/9/usr.bin/grep/regex/xmalloc.c (revision 303883) @@ -1,349 +1,349 @@ /* $FreeBSD$ */ /* xmalloc.c - Simple malloc debugging library implementation This software is released under a BSD-style license. See the file LICENSE for details and copyright. */ /* TODO: - red zones - group dumps by source location */ #include #include #include #define XMALLOC_INTERNAL 1 #include "xmalloc.h" /* Internal stuff. */ typedef struct hashTableItemRec { void *ptr; int bytes; const char *file; int line; const char *func; struct hashTableItemRec *next; } hashTableItem; typedef struct { hashTableItem **table; } hashTable; static int xmalloc_peak; -int xmalloc_current; +static int xmalloc_current; static int xmalloc_peak_blocks; -int xmalloc_current_blocks; +static int xmalloc_current_blocks; static int xmalloc_fail_after; #define TABLE_BITS 8 #define TABLE_MASK ((1 << TABLE_BITS) - 1) #define TABLE_SIZE (1 << TABLE_BITS) static hashTable * hash_table_new(void) { hashTable *tbl; tbl = malloc(sizeof(*tbl)); if (tbl != NULL) { tbl->table = calloc(TABLE_SIZE, sizeof(*tbl->table)); if (tbl->table == NULL) { free(tbl); return NULL; } } return tbl; } static int hash_void_ptr(void *ptr) { int hash; int i; /* I took this hash function just off the top of my head, I have no idea whether it is bad or very bad. */ hash = 0; for (i = 0; i < (int)sizeof(ptr)*8 / TABLE_BITS; i++) { hash ^= (unsigned long)ptr >> i*8; hash += i * 17; hash &= TABLE_MASK; } return hash; } static void hash_table_add(hashTable *tbl, void *ptr, int bytes, const char *file, int line, const char *func) { int i; hashTableItem *item, *new; i = hash_void_ptr(ptr); item = tbl->table[i]; if (item != NULL) while (item->next != NULL) item = item->next; new = malloc(sizeof(*new)); assert(new != NULL); new->ptr = ptr; new->bytes = bytes; new->file = file; new->line = line; new->func = func; new->next = NULL; if (item != NULL) item->next = new; else tbl->table[i] = new; xmalloc_current += bytes; if (xmalloc_current > xmalloc_peak) xmalloc_peak = xmalloc_current; xmalloc_current_blocks++; if (xmalloc_current_blocks > xmalloc_peak_blocks) xmalloc_peak_blocks = xmalloc_current_blocks; } static void hash_table_del(hashTable *tbl, void *ptr) { int i; hashTableItem *item, *prev; i = hash_void_ptr(ptr); item = tbl->table[i]; if (item == NULL) { printf("xfree: invalid ptr %p\n", ptr); abort(); } prev = NULL; while (item->ptr != ptr) { prev = item; item = item->next; } if (item->ptr != ptr) { printf("xfree: invalid ptr %p\n", ptr); abort(); } xmalloc_current -= item->bytes; xmalloc_current_blocks--; if (prev != NULL) { prev->next = item->next; free(item); } else { tbl->table[i] = item->next; free(item); } } static hashTable *xmalloc_table = NULL; static void xmalloc_init(void) { if (xmalloc_table == NULL) { xmalloc_table = hash_table_new(); xmalloc_peak = 0; xmalloc_peak_blocks = 0; xmalloc_current = 0; xmalloc_current_blocks = 0; xmalloc_fail_after = -1; } assert(xmalloc_table != NULL); assert(xmalloc_table->table != NULL); } /* Public API. */ void xmalloc_configure(int fail_after) { xmalloc_init(); xmalloc_fail_after = fail_after; } int xmalloc_dump_leaks(void) { int i; int num_leaks = 0; int leaked_bytes = 0; hashTableItem *item; xmalloc_init(); for (i = 0; i < TABLE_SIZE; i++) { item = xmalloc_table->table[i]; while (item != NULL) { printf("%s:%d: %s: %d bytes at %p not freed\n", item->file, item->line, item->func, item->bytes, item->ptr); num_leaks++; leaked_bytes += item->bytes; item = item->next; } } if (num_leaks == 0) printf("No memory leaks.\n"); else printf("%d unfreed memory chuncks, total %d unfreed bytes.\n", num_leaks, leaked_bytes); printf("Peak memory consumption %d bytes (%.1f kB, %.1f MB) in %d blocks ", xmalloc_peak, (double)xmalloc_peak / 1024, (double)xmalloc_peak / (1024*1024), xmalloc_peak_blocks); printf("(average "); if (xmalloc_peak_blocks) printf("%d", ((xmalloc_peak + xmalloc_peak_blocks / 2) / xmalloc_peak_blocks)); else printf("N/A"); printf(" bytes per block).\n"); return num_leaks; } void * xmalloc_impl(size_t size, const char *file, int line, const char *func) { void *ptr; xmalloc_init(); assert(size > 0); if (xmalloc_fail_after == 0) { xmalloc_fail_after = -2; #if 0 printf("xmalloc: forced failure %s:%d: %s\n", file, line, func); #endif return NULL; } else if (xmalloc_fail_after == -2) { printf("xmalloc: called after failure from %s:%d: %s\n", file, line, func); assert(0); } else if (xmalloc_fail_after > 0) xmalloc_fail_after--; ptr = malloc(size); if (ptr != NULL) hash_table_add(xmalloc_table, ptr, (int)size, file, line, func); return ptr; } void * xcalloc_impl(size_t nmemb, size_t size, const char *file, int line, const char *func) { void *ptr; xmalloc_init(); assert(size > 0); if (xmalloc_fail_after == 0) { xmalloc_fail_after = -2; #if 0 printf("xcalloc: forced failure %s:%d: %s\n", file, line, func); #endif return NULL; } else if (xmalloc_fail_after == -2) { printf("xcalloc: called after failure from %s:%d: %s\n", file, line, func); assert(0); } else if (xmalloc_fail_after > 0) xmalloc_fail_after--; ptr = calloc(nmemb, size); if (ptr != NULL) hash_table_add(xmalloc_table, ptr, (int)(nmemb * size), file, line, func); return ptr; } void xfree_impl(void *ptr, const char *file, int line, const char *func) { /*LINTED*/(void)&file; /*LINTED*/(void)&line; /*LINTED*/(void)&func; xmalloc_init(); if (ptr != NULL) hash_table_del(xmalloc_table, ptr); free(ptr); } void * xrealloc_impl(void *ptr, size_t new_size, const char *file, int line, const char *func) { void *new_ptr; xmalloc_init(); assert(ptr != NULL); assert(new_size > 0); if (xmalloc_fail_after == 0) { xmalloc_fail_after = -2; return NULL; } else if (xmalloc_fail_after == -2) { printf("xrealloc: called after failure from %s:%d: %s\n", file, line, func); assert(0); } else if (xmalloc_fail_after > 0) xmalloc_fail_after--; new_ptr = realloc(ptr, new_size); if (new_ptr != NULL) { hash_table_del(xmalloc_table, ptr); hash_table_add(xmalloc_table, new_ptr, (int)new_size, file, line, func); } return new_ptr; } /* EOF */ Index: stable/9/usr.bin/grep/util.c =================================================================== --- stable/9/usr.bin/grep/util.c (revision 303882) +++ stable/9/usr.bin/grep/util.c (revision 303883) @@ -1,492 +1,492 @@ /* $NetBSD: util.c,v 1.9 2011/02/27 17:33:37 joerg Exp $ */ /* $FreeBSD$ */ /* $OpenBSD: util.c,v 1.39 2010/07/02 22:18:03 tedu Exp $ */ /*- * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav * Copyright (C) 2008-2010 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "fastmatch.h" #include "grep.h" static int linesqueued; static int procline(struct str *l, int); bool file_matching(const char *fname) { char *fname_base; bool ret; ret = finclude ? false : true; fname_base = basename(fname); for (unsigned int i = 0; i < fpatterns; ++i) { if (fnmatch(fpattern[i].pat, fname, 0) == 0 || fnmatch(fpattern[i].pat, fname_base, 0) == 0) { if (fpattern[i].mode == EXCL_PAT) return (false); else ret = true; } } return (ret); } static inline bool dir_matching(const char *dname) { bool ret; ret = dinclude ? false : true; for (unsigned int i = 0; i < dpatterns; ++i) { if (dname != NULL && fnmatch(dpattern[i].pat, dname, 0) == 0) { if (dpattern[i].mode == EXCL_PAT) return (false); else ret = true; } } return (ret); } /* * Processes a directory when a recursive search is performed with * the -R option. Each appropriate file is passed to procfile(). */ int grep_tree(char **argv) { FTS *fts; FTSENT *p; int c, fts_flags; bool ok; c = fts_flags = 0; switch(linkbehave) { case LINK_EXPLICIT: fts_flags = FTS_COMFOLLOW; break; case LINK_SKIP: fts_flags = FTS_PHYSICAL; break; default: fts_flags = FTS_LOGICAL; } fts_flags |= FTS_NOSTAT | FTS_NOCHDIR; if (!(fts = fts_open(argv, fts_flags, NULL))) err(2, "fts_open"); while ((p = fts_read(fts)) != NULL) { switch (p->fts_info) { case FTS_DNR: /* FALLTHROUGH */ case FTS_ERR: file_err = true; if(!sflag) warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); break; case FTS_D: /* FALLTHROUGH */ case FTS_DP: if (dexclude || dinclude) if (!dir_matching(p->fts_name) || !dir_matching(p->fts_path)) fts_set(fts, p, FTS_SKIP); break; case FTS_DC: /* Print a warning for recursive directory loop */ warnx("warning: %s: recursive directory loop", p->fts_path); break; default: /* Check for file exclusion/inclusion */ ok = true; if (fexclude || finclude) ok &= file_matching(p->fts_path); if (ok) c += procfile(p->fts_path); break; } } fts_close(fts); return (c); } /* * Opens a file and processes it. Each file is processed line-by-line * passing the lines to procline(). */ int procfile(const char *fn) { struct file *f; struct stat sb; struct str ln; mode_t s; int c, t; mcount = mlimit; if (strcmp(fn, "-") == 0) { fn = label != NULL ? label : getstr(1); f = grep_open(NULL); } else { if (!stat(fn, &sb)) { /* Check if we need to process the file */ s = sb.st_mode & S_IFMT; if (s == S_IFDIR && dirbehave == DIR_SKIP) return (0); if ((s == S_IFIFO || s == S_IFCHR || s == S_IFBLK || s == S_IFSOCK) && devbehave == DEV_SKIP) return (0); } f = grep_open(fn); } if (f == NULL) { file_err = true; if (!sflag) warn("%s", fn); return (0); } ln.file = grep_malloc(strlen(fn) + 1); strcpy(ln.file, fn); ln.line_no = 0; ln.len = 0; linesqueued = 0; tail = 0; ln.off = -1; for (c = 0; c == 0 || !(lflag || qflag); ) { ln.off += ln.len + 1; if ((ln.dat = grep_fgetln(f, &ln.len)) == NULL || ln.len == 0) { if (ln.line_no == 0 && matchall) exit(0); else break; } if (ln.len > 0 && ln.dat[ln.len - 1] == '\n') --ln.len; ln.line_no++; /* Return if we need to skip a binary file */ if (f->binary && binbehave == BINFILE_SKIP) { grep_close(f); free(ln.file); free(f); return (0); } /* Process the file line-by-line */ if ((t = procline(&ln, f->binary)) == 0 && Bflag > 0) { enqueue(&ln); linesqueued++; } c += t; if (mflag && mcount <= 0) break; } if (Bflag > 0) clearqueue(); grep_close(f); if (cflag) { if (!hflag) printf("%s:", ln.file); printf("%u\n", c); } if (lflag && !qflag && c != 0) printf("%s%c", fn, nullflag ? 0 : '\n'); if (Lflag && !qflag && c == 0) printf("%s%c", fn, nullflag ? 0 : '\n'); if (c && !cflag && !lflag && !Lflag && binbehave == BINFILE_BIN && f->binary && !qflag) printf(getstr(8), fn); free(ln.file); free(f); return (c); } #define iswword(x) (iswalnum((x)) || (x) == L'_') /* * Processes a line comparing it with the specified patterns. Each pattern * is looped to be compared along with the full string, saving each and every * match, which is necessary to colorize the output and to count the * matches. The matching lines are passed to printline() to display the * appropriate output. */ static int procline(struct str *l, int nottext) { regmatch_t matches[MAX_LINE_MATCHES]; regmatch_t pmatch; size_t st = 0; unsigned int i; int c = 0, m = 0, r = 0; /* Loop to process the whole line */ while (st <= l->len) { pmatch.rm_so = st; pmatch.rm_eo = l->len; /* Loop to compare with all the patterns */ for (i = 0; i < patterns; i++) { if (fg_pattern[i].pattern) r = fastexec(&fg_pattern[i], l->dat, 1, &pmatch, eflags); else r = regexec(&r_pattern[i], l->dat, 1, &pmatch, eflags); r = (r == 0) ? 0 : REG_NOMATCH; st = (cflags & REG_NOSUB) ? (size_t)l->len : (size_t)pmatch.rm_eo; if (r == REG_NOMATCH) continue; /* Check for full match */ if (r == 0 && xflag) if (pmatch.rm_so != 0 || (size_t)pmatch.rm_eo != l->len) r = REG_NOMATCH; /* Check for whole word match */ if (r == 0 && (wflag || fg_pattern[i].word)) { wchar_t wbegin, wend; wbegin = wend = L' '; if (pmatch.rm_so != 0 && sscanf(&l->dat[pmatch.rm_so - 1], "%lc", &wbegin) != 1) r = REG_NOMATCH; else if ((size_t)pmatch.rm_eo != l->len && sscanf(&l->dat[pmatch.rm_eo], "%lc", &wend) != 1) r = REG_NOMATCH; else if (iswword(wbegin) || iswword(wend)) r = REG_NOMATCH; } if (r == 0) { if (m == 0) c++; if (m < MAX_LINE_MATCHES) matches[m++] = pmatch; /* matches - skip further patterns */ if ((color == NULL && !oflag) || qflag || lflag) break; } } if (vflag) { c = !c; break; } /* One pass if we are not recording matches */ - if (!wflag && ((color == NULL && !oflag) || qflag || lflag)) + if (!wflag && ((color == NULL && !oflag) || qflag || lflag || Lflag)) break; if (st == (size_t)pmatch.rm_so) break; /* No matches */ } /* Count the matches if we have a match limit */ if (mflag) mcount -= c; if (c && binbehave == BINFILE_BIN && nottext) return (c); /* Binary file */ /* Dealing with the context */ if ((tail || c) && !cflag && !qflag && !lflag && !Lflag) { if (c) { if (!first && !prev && !tail && Aflag) printf("--\n"); tail = Aflag; if (Bflag > 0) { if (!first && !prev) printf("--\n"); printqueue(); } linesqueued = 0; printline(l, ':', matches, m); } else { printline(l, '-', matches, m); tail--; } } if (c) { prev = true; first = false; } else prev = false; return (c); } /* * Safe malloc() for internal use. */ void * grep_malloc(size_t size) { void *ptr; if ((ptr = malloc(size)) == NULL) err(2, "malloc"); return (ptr); } /* * Safe calloc() for internal use. */ void * grep_calloc(size_t nmemb, size_t size) { void *ptr; if ((ptr = calloc(nmemb, size)) == NULL) err(2, "calloc"); return (ptr); } /* * Safe realloc() for internal use. */ void * grep_realloc(void *ptr, size_t size) { if ((ptr = realloc(ptr, size)) == NULL) err(2, "realloc"); return (ptr); } /* * Safe strdup() for internal use. */ char * grep_strdup(const char *str) { char *ret; if ((ret = strdup(str)) == NULL) err(2, "strdup"); return (ret); } /* * Prints a matching line according to the command line options. */ void printline(struct str *line, int sep, regmatch_t *matches, int m) { size_t a = 0; int i, n = 0; if (!hflag) { if (!nullflag) { fputs(line->file, stdout); ++n; } else { printf("%s", line->file); putchar(0); } } if (nflag) { if (n > 0) putchar(sep); printf("%d", line->line_no); ++n; } if (bflag) { if (n > 0) putchar(sep); printf("%lld", (long long)line->off); ++n; } if (n) putchar(sep); /* --color and -o */ if ((oflag || color) && m > 0) { for (i = 0; i < m; i++) { if (!oflag) fwrite(line->dat + a, matches[i].rm_so - a, 1, stdout); if (color) fprintf(stdout, "\33[%sm\33[K", color); fwrite(line->dat + matches[i].rm_so, matches[i].rm_eo - matches[i].rm_so, 1, stdout); if (color) fprintf(stdout, "\33[m\33[K"); a = matches[i].rm_eo; if (oflag) putchar('\n'); } if (!oflag) { if (line->len - a > 0) fwrite(line->dat + a, line->len - a, 1, stdout); putchar('\n'); } } else { fwrite(line->dat, line->len, 1, stdout); putchar('\n'); } } Index: stable/9/usr.bin/grep =================================================================== --- stable/9/usr.bin/grep (revision 303882) +++ stable/9/usr.bin/grep (revision 303883) Property changes on: stable/9/usr.bin/grep ___________________________________________________________________ Modified: svn:mergeinfo ## -0,0 +0,1 ## Merged /head/usr.bin/grep:r228395,241737,270132,296799,303676