| 1 | /* dfasearch.c - searching subroutines using dfa and regex for grep.
|
|---|
| 2 | Copyright 1992, 1998, 2000, 2007, 2009-2012 Free Software Foundation, Inc.
|
|---|
| 3 |
|
|---|
| 4 | This program is free software; you can redistribute it and/or modify
|
|---|
| 5 | it under the terms of the GNU General Public License as published by
|
|---|
| 6 | the Free Software Foundation; either version 3, or (at your option)
|
|---|
| 7 | any later version.
|
|---|
| 8 |
|
|---|
| 9 | This program is distributed in the hope that it will be useful,
|
|---|
| 10 | but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|---|
| 12 | GNU General Public License for more details.
|
|---|
| 13 |
|
|---|
| 14 | You should have received a copy of the GNU General Public License
|
|---|
| 15 | along with this program; if not, write to the Free Software
|
|---|
| 16 | Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
|
|---|
| 17 | 02110-1301, USA. */
|
|---|
| 18 |
|
|---|
| 19 | /* Written August 1992 by Mike Haertel. */
|
|---|
| 20 |
|
|---|
| 21 | #include <config.h>
|
|---|
| 22 | #include "intprops.h"
|
|---|
| 23 | #include "search.h"
|
|---|
| 24 | #include "dfa.h"
|
|---|
| 25 |
|
|---|
| 26 | /* For -w, we also consider _ to be word constituent. */
|
|---|
| 27 | #define WCHAR(C) (isalnum (C) || (C) == '_')
|
|---|
| 28 |
|
|---|
| 29 | /* KWset compiled pattern. For Ecompile and Gcompile, we compile
|
|---|
| 30 | a list of strings, at least one of which is known to occur in
|
|---|
| 31 | any string matching the regexp. */
|
|---|
| 32 | static kwset_t kwset;
|
|---|
| 33 |
|
|---|
| 34 | /* DFA compiled regexp. */
|
|---|
| 35 | static struct dfa *dfa;
|
|---|
| 36 |
|
|---|
| 37 | /* The Regex compiled patterns. */
|
|---|
| 38 | static struct patterns
|
|---|
| 39 | {
|
|---|
| 40 | /* Regex compiled regexp. */
|
|---|
| 41 | struct re_pattern_buffer regexbuf;
|
|---|
| 42 | struct re_registers regs; /* This is here on account of a BRAIN-DEAD
|
|---|
| 43 | Q@#%!# library interface in regex.c. */
|
|---|
| 44 | } patterns0;
|
|---|
| 45 |
|
|---|
| 46 | static struct patterns *patterns;
|
|---|
| 47 | static size_t pcount;
|
|---|
| 48 |
|
|---|
| 49 | void
|
|---|
| 50 | dfaerror (char const *mesg)
|
|---|
| 51 | {
|
|---|
| 52 | error (EXIT_TROUBLE, 0, "%s", mesg);
|
|---|
| 53 |
|
|---|
| 54 | /* notreached */
|
|---|
| 55 | /* Tell static analyzers that this function does not return. */
|
|---|
| 56 | abort ();
|
|---|
| 57 | }
|
|---|
| 58 |
|
|---|
| 59 | /* For now, the sole dfawarn-eliciting condition (use of a regexp
|
|---|
| 60 | like '[:lower:]') is unequivocally an error, so treat it as such,
|
|---|
| 61 | when possible. */
|
|---|
| 62 | void
|
|---|
| 63 | dfawarn (char const *mesg)
|
|---|
| 64 | {
|
|---|
| 65 | static enum { DW_NONE = 0, DW_POSIX, DW_GNU } mode;
|
|---|
| 66 | if (mode == DW_NONE)
|
|---|
| 67 | mode = (getenv ("POSIXLY_CORRECT") ? DW_POSIX : DW_GNU);
|
|---|
| 68 | if (mode == DW_GNU)
|
|---|
| 69 | dfaerror (mesg);
|
|---|
| 70 | }
|
|---|
| 71 |
|
|---|
| 72 | /* Number of compiled fixed strings known to exactly match the regexp.
|
|---|
| 73 | If kwsexec returns < kwset_exact_matches, then we don't need to
|
|---|
| 74 | call the regexp matcher at all. */
|
|---|
| 75 | static size_t kwset_exact_matches;
|
|---|
| 76 |
|
|---|
| 77 | static char const *
|
|---|
| 78 | kwsincr_case (const char *must)
|
|---|
| 79 | {
|
|---|
| 80 | size_t n = strlen (must);
|
|---|
| 81 | const char *buf = (match_icase && MB_CUR_MAX > 1
|
|---|
| 82 | ? mbtolower (must, &n)
|
|---|
| 83 | : must);
|
|---|
| 84 | return kwsincr (kwset, buf, n);
|
|---|
| 85 | }
|
|---|
| 86 |
|
|---|
| 87 | /* If the DFA turns out to have some set of fixed strings one of
|
|---|
| 88 | which must occur in the match, then we build a kwset matcher
|
|---|
| 89 | to find those strings, and thus quickly filter out impossible
|
|---|
| 90 | matches. */
|
|---|
| 91 | static void
|
|---|
| 92 | kwsmusts (void)
|
|---|
| 93 | {
|
|---|
| 94 | struct dfamust const *dm;
|
|---|
| 95 | char const *err;
|
|---|
| 96 |
|
|---|
| 97 | dm = dfamusts (dfa);
|
|---|
| 98 | if (dm)
|
|---|
| 99 | {
|
|---|
| 100 | kwsinit (&kwset);
|
|---|
| 101 | /* First, we compile in the substrings known to be exact
|
|---|
| 102 | matches. The kwset matcher will return the index
|
|---|
| 103 | of the matching string that it chooses. */
|
|---|
| 104 | for (; dm; dm = dm->next)
|
|---|
| 105 | {
|
|---|
| 106 | if (!dm->exact)
|
|---|
| 107 | continue;
|
|---|
| 108 | ++kwset_exact_matches;
|
|---|
| 109 | if ((err = kwsincr_case (dm->must)) != NULL)
|
|---|
| 110 | error (EXIT_TROUBLE, 0, "%s", err);
|
|---|
| 111 | }
|
|---|
| 112 | /* Now, we compile the substrings that will require
|
|---|
| 113 | the use of the regexp matcher. */
|
|---|
| 114 | for (dm = dfamusts (dfa); dm; dm = dm->next)
|
|---|
| 115 | {
|
|---|
| 116 | if (dm->exact)
|
|---|
| 117 | continue;
|
|---|
| 118 | if ((err = kwsincr_case (dm->must)) != NULL)
|
|---|
| 119 | error (EXIT_TROUBLE, 0, "%s", err);
|
|---|
| 120 | }
|
|---|
| 121 | if ((err = kwsprep (kwset)) != NULL)
|
|---|
| 122 | error (EXIT_TROUBLE, 0, "%s", err);
|
|---|
| 123 | }
|
|---|
| 124 | }
|
|---|
| 125 |
|
|---|
| 126 | void
|
|---|
| 127 | GEAcompile (char const *pattern, size_t size, reg_syntax_t syntax_bits)
|
|---|
| 128 | {
|
|---|
| 129 | const char *err;
|
|---|
| 130 | const char *p, *sep;
|
|---|
| 131 | size_t total = size;
|
|---|
| 132 | char *motif;
|
|---|
| 133 |
|
|---|
| 134 | if (match_icase)
|
|---|
| 135 | syntax_bits |= RE_ICASE;
|
|---|
| 136 | re_set_syntax (syntax_bits);
|
|---|
| 137 | dfasyntax (syntax_bits, match_icase, eolbyte);
|
|---|
| 138 |
|
|---|
| 139 | /* For GNU regex compiler we have to pass the patterns separately to detect
|
|---|
| 140 | errors like "[\nallo\n]\n". The patterns here are "[", "allo" and "]"
|
|---|
| 141 | GNU regex should have raise a syntax error. The same for backref, where
|
|---|
| 142 | the backref should have been local to each pattern. */
|
|---|
| 143 | p = pattern;
|
|---|
| 144 | do
|
|---|
| 145 | {
|
|---|
| 146 | size_t len;
|
|---|
| 147 | sep = memchr (p, '\n', total);
|
|---|
| 148 | if (sep)
|
|---|
| 149 | {
|
|---|
| 150 | len = sep - p;
|
|---|
| 151 | sep++;
|
|---|
| 152 | total -= (len + 1);
|
|---|
| 153 | }
|
|---|
| 154 | else
|
|---|
| 155 | {
|
|---|
| 156 | len = total;
|
|---|
| 157 | total = 0;
|
|---|
| 158 | }
|
|---|
| 159 |
|
|---|
| 160 | patterns = xnrealloc (patterns, pcount + 1, sizeof *patterns);
|
|---|
| 161 | patterns[pcount] = patterns0;
|
|---|
| 162 |
|
|---|
| 163 | if ((err = re_compile_pattern (p, len,
|
|---|
| 164 | &(patterns[pcount].regexbuf))) != NULL)
|
|---|
| 165 | error (EXIT_TROUBLE, 0, "%s", err);
|
|---|
| 166 | pcount++;
|
|---|
| 167 |
|
|---|
| 168 | p = sep;
|
|---|
| 169 | } while (sep && total != 0);
|
|---|
| 170 |
|
|---|
| 171 | /* In the match_words and match_lines cases, we use a different pattern
|
|---|
| 172 | for the DFA matcher that will quickly throw out cases that won't work.
|
|---|
| 173 | Then if DFA succeeds we do some hairy stuff using the regex matcher
|
|---|
| 174 | to decide whether the match should really count. */
|
|---|
| 175 | if (match_words || match_lines)
|
|---|
| 176 | {
|
|---|
| 177 | static char const line_beg_no_bk[] = "^(";
|
|---|
| 178 | static char const line_end_no_bk[] = ")$";
|
|---|
| 179 | static char const word_beg_no_bk[] = "(^|[^[:alnum:]_])(";
|
|---|
| 180 | static char const word_end_no_bk[] = ")([^[:alnum:]_]|$)";
|
|---|
| 181 | static char const line_beg_bk[] = "^\\(";
|
|---|
| 182 | static char const line_end_bk[] = "\\)$";
|
|---|
| 183 | static char const word_beg_bk[] = "\\(^\\|[^[:alnum:]_]\\)\\(";
|
|---|
| 184 | static char const word_end_bk[] = "\\)\\([^[:alnum:]_]\\|$\\)";
|
|---|
| 185 | int bk = !(syntax_bits & RE_NO_BK_PARENS);
|
|---|
| 186 | char *n = xmalloc (sizeof word_beg_bk - 1 + size + sizeof word_end_bk);
|
|---|
| 187 |
|
|---|
| 188 | strcpy (n, match_lines ? (bk ? line_beg_bk : line_beg_no_bk)
|
|---|
| 189 | : (bk ? word_beg_bk : word_beg_no_bk));
|
|---|
| 190 | total = strlen(n);
|
|---|
| 191 | memcpy (n + total, pattern, size);
|
|---|
| 192 | total += size;
|
|---|
| 193 | strcpy (n + total, match_lines ? (bk ? line_end_bk : line_end_no_bk)
|
|---|
| 194 | : (bk ? word_end_bk : word_end_no_bk));
|
|---|
| 195 | total += strlen (n + total);
|
|---|
| 196 | pattern = motif = n;
|
|---|
| 197 | size = total;
|
|---|
| 198 | }
|
|---|
| 199 | else
|
|---|
| 200 | motif = NULL;
|
|---|
| 201 |
|
|---|
| 202 | dfa = dfaalloc ();
|
|---|
| 203 | dfacomp (pattern, size, dfa, 1);
|
|---|
| 204 | kwsmusts ();
|
|---|
| 205 |
|
|---|
| 206 | free(motif);
|
|---|
| 207 | }
|
|---|
| 208 |
|
|---|
| 209 | size_t
|
|---|
| 210 | EGexecute (char const *buf, size_t size, size_t *match_size,
|
|---|
| 211 | char const *start_ptr)
|
|---|
| 212 | {
|
|---|
| 213 | char const *buflim, *beg, *end, *match, *best_match, *mb_start;
|
|---|
| 214 | char eol = eolbyte;
|
|---|
| 215 | int backref;
|
|---|
| 216 | regoff_t start;
|
|---|
| 217 | ptrdiff_t len, best_len;
|
|---|
| 218 | struct kwsmatch kwsm;
|
|---|
| 219 | size_t i, ret_val;
|
|---|
| 220 | if (MB_CUR_MAX > 1)
|
|---|
| 221 | {
|
|---|
| 222 | if (match_icase)
|
|---|
| 223 | {
|
|---|
| 224 | /* mbtolower adds a NUL byte at the end. That will provide
|
|---|
| 225 | space for the sentinel byte dfaexec may add. */
|
|---|
| 226 | char *case_buf = mbtolower (buf, &size);
|
|---|
| 227 | if (start_ptr)
|
|---|
| 228 | start_ptr = case_buf + (start_ptr - buf);
|
|---|
| 229 | buf = case_buf;
|
|---|
| 230 | }
|
|---|
| 231 | }
|
|---|
| 232 |
|
|---|
| 233 | mb_start = buf;
|
|---|
| 234 | buflim = buf + size;
|
|---|
| 235 |
|
|---|
| 236 | for (beg = end = buf; end < buflim; beg = end)
|
|---|
| 237 | {
|
|---|
| 238 | if (!start_ptr)
|
|---|
| 239 | {
|
|---|
| 240 | /* We don't care about an exact match. */
|
|---|
| 241 | if (kwset)
|
|---|
| 242 | {
|
|---|
| 243 | /* Find a possible match using the KWset matcher. */
|
|---|
| 244 | size_t offset = kwsexec (kwset, beg, buflim - beg, &kwsm);
|
|---|
| 245 | if (offset == (size_t) -1)
|
|---|
| 246 | goto failure;
|
|---|
| 247 | beg += offset;
|
|---|
| 248 | /* Narrow down to the line containing the candidate, and
|
|---|
| 249 | run it through DFA. */
|
|---|
| 250 | if ((end = memchr(beg, eol, buflim - beg)) != NULL)
|
|---|
| 251 | end++;
|
|---|
| 252 | else
|
|---|
| 253 | end = buflim;
|
|---|
| 254 | match = beg;
|
|---|
| 255 | while (beg > buf && beg[-1] != eol)
|
|---|
| 256 | --beg;
|
|---|
| 257 | if (kwsm.index < kwset_exact_matches)
|
|---|
| 258 | {
|
|---|
| 259 | if (!MBS_SUPPORT)
|
|---|
| 260 | goto success;
|
|---|
| 261 |
|
|---|
| 262 | if (mb_start < beg)
|
|---|
| 263 | mb_start = beg;
|
|---|
| 264 | if (MB_CUR_MAX == 1
|
|---|
| 265 | || !is_mb_middle (&mb_start, match, buflim,
|
|---|
| 266 | kwsm.size[0]))
|
|---|
| 267 | goto success;
|
|---|
| 268 | }
|
|---|
| 269 | if (dfaexec (dfa, beg, (char *) end, 0, NULL, &backref) == NULL)
|
|---|
| 270 | continue;
|
|---|
| 271 | }
|
|---|
| 272 | else
|
|---|
| 273 | {
|
|---|
| 274 | /* No good fixed strings; start with DFA. */
|
|---|
| 275 | char const *next_beg = dfaexec (dfa, beg, (char *) buflim,
|
|---|
| 276 | 0, NULL, &backref);
|
|---|
| 277 | if (next_beg == NULL)
|
|---|
| 278 | break;
|
|---|
| 279 | /* Narrow down to the line we've found. */
|
|---|
| 280 | beg = next_beg;
|
|---|
| 281 | if ((end = memchr(beg, eol, buflim - beg)) != NULL)
|
|---|
| 282 | end++;
|
|---|
| 283 | else
|
|---|
| 284 | end = buflim;
|
|---|
| 285 | while (beg > buf && beg[-1] != eol)
|
|---|
| 286 | --beg;
|
|---|
| 287 | }
|
|---|
| 288 | /* Successful, no backreferences encountered! */
|
|---|
| 289 | if (!backref)
|
|---|
| 290 | goto success;
|
|---|
| 291 | }
|
|---|
| 292 | else
|
|---|
| 293 | {
|
|---|
| 294 | /* We are looking for the leftmost (then longest) exact match.
|
|---|
| 295 | We will go through the outer loop only once. */
|
|---|
| 296 | beg = start_ptr;
|
|---|
| 297 | end = buflim;
|
|---|
| 298 | }
|
|---|
| 299 |
|
|---|
| 300 | /* If the "line" is longer than the maximum regexp offset,
|
|---|
| 301 | die as if we've run out of memory. */
|
|---|
| 302 | if (TYPE_MAXIMUM (regoff_t) < end - buf - 1)
|
|---|
| 303 | xalloc_die ();
|
|---|
| 304 |
|
|---|
| 305 | /* If we've made it to this point, this means DFA has seen
|
|---|
| 306 | a probable match, and we need to run it through Regex. */
|
|---|
| 307 | best_match = end;
|
|---|
| 308 | best_len = 0;
|
|---|
| 309 | for (i = 0; i < pcount; i++)
|
|---|
| 310 | {
|
|---|
| 311 | patterns[i].regexbuf.not_eol = 0;
|
|---|
| 312 | start = re_search (&(patterns[i].regexbuf),
|
|---|
| 313 | buf, end - buf - 1,
|
|---|
| 314 | beg - buf, end - beg - 1,
|
|---|
| 315 | &(patterns[i].regs));
|
|---|
| 316 | if (start < -1)
|
|---|
| 317 | xalloc_die ();
|
|---|
| 318 | else if (0 <= start)
|
|---|
| 319 | {
|
|---|
| 320 | len = patterns[i].regs.end[0] - start;
|
|---|
| 321 | match = buf + start;
|
|---|
| 322 | if (match > best_match)
|
|---|
| 323 | continue;
|
|---|
| 324 | if (start_ptr && !match_words)
|
|---|
| 325 | goto assess_pattern_match;
|
|---|
| 326 | if ((!match_lines && !match_words)
|
|---|
| 327 | || (match_lines && len == end - beg - 1))
|
|---|
| 328 | {
|
|---|
| 329 | match = beg;
|
|---|
| 330 | len = end - beg;
|
|---|
| 331 | goto assess_pattern_match;
|
|---|
| 332 | }
|
|---|
| 333 | /* If -w, check if the match aligns with word boundaries.
|
|---|
| 334 | We do this iteratively because:
|
|---|
| 335 | (a) the line may contain more than one occurrence of the
|
|---|
| 336 | pattern, and
|
|---|
| 337 | (b) Several alternatives in the pattern might be valid at a
|
|---|
| 338 | given point, and we may need to consider a shorter one to
|
|---|
| 339 | find a word boundary. */
|
|---|
| 340 | if (match_words)
|
|---|
| 341 | while (match <= best_match)
|
|---|
| 342 | {
|
|---|
| 343 | if ((match == buf || !WCHAR ((unsigned char) match[-1]))
|
|---|
| 344 | && (start + len == end - buf - 1
|
|---|
| 345 | || !WCHAR ((unsigned char) match[len])))
|
|---|
| 346 | goto assess_pattern_match;
|
|---|
| 347 | if (len > 0)
|
|---|
| 348 | {
|
|---|
| 349 | /* Try a shorter length anchored at the same place. */
|
|---|
| 350 | --len;
|
|---|
| 351 | patterns[i].regexbuf.not_eol = 1;
|
|---|
| 352 | len = re_match (&(patterns[i].regexbuf),
|
|---|
| 353 | buf, match + len - beg, match - buf,
|
|---|
| 354 | &(patterns[i].regs));
|
|---|
| 355 | if (len < -1)
|
|---|
| 356 | xalloc_die ();
|
|---|
| 357 | }
|
|---|
| 358 | if (len <= 0)
|
|---|
| 359 | {
|
|---|
| 360 | /* Try looking further on. */
|
|---|
| 361 | if (match == end - 1)
|
|---|
| 362 | break;
|
|---|
| 363 | match++;
|
|---|
| 364 | patterns[i].regexbuf.not_eol = 0;
|
|---|
| 365 | start = re_search (&(patterns[i].regexbuf),
|
|---|
| 366 | buf, end - buf - 1,
|
|---|
| 367 | match - buf, end - match - 1,
|
|---|
| 368 | &(patterns[i].regs));
|
|---|
| 369 | if (start < 0)
|
|---|
| 370 | {
|
|---|
| 371 | if (start < -1)
|
|---|
| 372 | xalloc_die ();
|
|---|
| 373 | break;
|
|---|
| 374 | }
|
|---|
| 375 | len = patterns[i].regs.end[0] - start;
|
|---|
| 376 | match = buf + start;
|
|---|
| 377 | }
|
|---|
| 378 | } /* while (match <= best_match) */
|
|---|
| 379 | continue;
|
|---|
| 380 | assess_pattern_match:
|
|---|
| 381 | if (!start_ptr)
|
|---|
| 382 | {
|
|---|
| 383 | /* Good enough for a non-exact match.
|
|---|
| 384 | No need to look at further patterns, if any. */
|
|---|
| 385 | goto success;
|
|---|
| 386 | }
|
|---|
| 387 | if (match < best_match || (match == best_match && len > best_len))
|
|---|
| 388 | {
|
|---|
| 389 | /* Best exact match: leftmost, then longest. */
|
|---|
| 390 | best_match = match;
|
|---|
| 391 | best_len = len;
|
|---|
| 392 | }
|
|---|
| 393 | } /* if re_search >= 0 */
|
|---|
| 394 | } /* for Regex patterns. */
|
|---|
| 395 | if (best_match < end)
|
|---|
| 396 | {
|
|---|
| 397 | /* We have found an exact match. We were just
|
|---|
| 398 | waiting for the best one (leftmost then longest). */
|
|---|
| 399 | beg = best_match;
|
|---|
| 400 | len = best_len;
|
|---|
| 401 | goto success_in_len;
|
|---|
| 402 | }
|
|---|
| 403 | } /* for (beg = end ..) */
|
|---|
| 404 |
|
|---|
| 405 | failure:
|
|---|
| 406 | ret_val = -1;
|
|---|
| 407 | goto out;
|
|---|
| 408 |
|
|---|
| 409 | success:
|
|---|
| 410 | len = end - beg;
|
|---|
| 411 | success_in_len:
|
|---|
| 412 | *match_size = len;
|
|---|
| 413 | ret_val = beg - buf;
|
|---|
| 414 | out:
|
|---|
| 415 | return ret_val;
|
|---|
| 416 | }
|
|---|