gnu/usr.bin/grep/search.c

   1 /* search.c - searching subroutines using dfa, kwset and regex for grep.
   2    Copyright 1992, 1998, 2000 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 2, 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., 59 Temple Place - Suite 330, Boston, MA
  17    02111-1307, USA.  */
  18
  19 /* Written August 1992 by Mike Haertel. */
  20
  21 /* $FreeBSD$ */
  22
  23 #ifndef _GNU_SOURCE
  24 # define _GNU_SOURCE 1
  25 #endif
  26 #ifdef HAVE_CONFIG_H
  27 # include <config.h>
  28 #endif
  29 #include <assert.h>
  30 #include <sys/types.h>
  31 #if defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H && defined HAVE_MBRTOWC
  32 /* We can handle multibyte string.  */
  33 # define MBS_SUPPORT
  34 # include <wchar.h>
  35 # include <wctype.h>
  36 #endif
  37
  38 #include "system.h"
  39 #include "grep.h"
  40 #include "regex.h"
  41 #include "dfa.h"
  42 #include "kwset.h"
  43 #include "error.h"
  44 #include "xalloc.h"
  45 #ifdef HAVE_LIBPCRE
  46 # include <pcre.h>
  47 #endif
  48 #ifdef HAVE_LANGINFO_CODESET
  49 # include <langinfo.h>
  50 #endif
  51
  52 #define NCHAR (UCHAR_MAX + 1)
  53
  54 /* For -w, we also consider _ to be word constituent.  */
  55 #define WCHAR(C) (ISALNUM(C) || (C) == '_')
  56
  57 /* DFA compiled regexp. */
  58 static struct dfa dfa;
  59
  60 /* The Regex compiled patterns.  */
  61 static struct patterns
  62 {
  63   /* Regex compiled regexp. */
  64   struct re_pattern_buffer regexbuf;
  65   struct re_registers regs; /* This is here on account of a BRAIN-DEAD
  66                                Q@#%!# library interface in regex.c.  */
  67 } patterns0;
  68
  69 struct patterns *patterns;
  70 size_t pcount;
  71
  72 /* KWset compiled pattern.  For Ecompile and Gcompile, we compile
  73    a list of strings, at least one of which is known to occur in
  74    any string matching the regexp. */
  75 static kwset_t kwset;
  76
  77 /* Number of compiled fixed strings known to exactly match the regexp.
  78    If kwsexec returns < kwset_exact_matches, then we don't need to
  79    call the regexp matcher at all. */
  80 static int kwset_exact_matches;
  81
  82 /* UTF-8 encoding allows some optimizations that we can't otherwise
  83    assume in a multibyte encoding. */
  84 static int using_utf8;
  85
  86 static void kwsinit PARAMS ((void));
  87 static void kwsmusts PARAMS ((void));
  88 static void Gcompile PARAMS ((char const *, size_t));
  89 static void Ecompile PARAMS ((char const *, size_t));
  90 static size_t EGexecute PARAMS ((char const *, size_t, size_t *, int ));
  91 static void Fcompile PARAMS ((char const *, size_t));
  92 static size_t Fexecute PARAMS ((char const *, size_t, size_t *, int));
  93 static void Pcompile PARAMS ((char const *, size_t ));
  94 static size_t Pexecute PARAMS ((char const *, size_t, size_t *, int));
  95
  96 void
  97 check_utf8 (void)
  98 {
  99 #ifdef HAVE_LANGINFO_CODESET
 100   if (strcmp (nl_langinfo (CODESET), "UTF-8") == 0)
 101     using_utf8 = 1;
 102 #endif
 103 }
 104
 105 void
 106 dfaerror (char const *mesg)
 107 {
 108   error (2, 0, mesg);
 109 }
 110
 111 static void
 112 kwsinit (void)
 113 {
 114   static char trans[NCHAR];
 115   int i;
 116
 117   if (match_icase)
 118     for (i = 0; i < NCHAR; ++i)
 119       trans[i] = TOLOWER (i);
 120
 121   if (!(kwset = kwsalloc (match_icase ? trans : (char *) 0)))
 122     error (2, 0, _("memory exhausted"));
 123 }
 124
 125 /* If the DFA turns out to have some set of fixed strings one of
 126    which must occur in the match, then we build a kwset matcher
 127    to find those strings, and thus quickly filter out impossible
 128    matches. */
 129 static void
 130 kwsmusts (void)
 131 {
 132   struct dfamust const *dm;
 133   char const *err;
 134
 135   if (dfa.musts)
 136     {
 137       kwsinit ();
 138       /* First, we compile in the substrings known to be exact
 139          matches.  The kwset matcher will return the index
 140          of the matching string that it chooses. */
 141       for (dm = dfa.musts; dm; dm = dm->next)
 142         {
 143           if (!dm->exact)
 144             continue;
 145           ++kwset_exact_matches;
 146           if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != 0)
 147             error (2, 0, err);
 148         }
 149       /* Now, we compile the substrings that will require
 150          the use of the regexp matcher.  */
 151       for (dm = dfa.musts; dm; dm = dm->next)
 152         {
 153           if (dm->exact)
 154             continue;
 155           if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != 0)
 156             error (2, 0, err);
 157         }
 158       if ((err = kwsprep (kwset)) != 0)
 159         error (2, 0, err);
 160     }
 161 }
 162
 163 static void
 164 Gcompile (char const *pattern, size_t size)
 165 {
 166   const char *err;
 167   char const *sep;
 168   size_t total = size;
 169   char const *motif = pattern;
 170
 171   check_utf8 ();
 172   re_set_syntax (RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE | (match_icase ? RE_ICASE : 0));
 173   dfasyntax (RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE, match_icase, eolbyte);
 174
 175   /* For GNU regex compiler we have to pass the patterns separately to detect
 176      errors like "[\nallo\n]\n".  The patterns here are "[", "allo" and "]"
 177      GNU regex should have raise a syntax error.  The same for backref, where
 178      the backref should have been local to each pattern.  */
 179   do
 180     {
 181       size_t len;
 182       sep = memchr (motif, '\n', total);
 183       if (sep)
 184         {
 185           len = sep - motif;
 186           sep++;
 187           total -= (len + 1);
 188         }
 189       else
 190         {
 191           len = total;
 192           total = 0;
 193         }
 194
 195       patterns = realloc (patterns, (pcount + 1) * sizeof (*patterns));
 196       if (patterns == NULL)
 197         error (2, errno, _("memory exhausted"));
 198
 199       patterns[pcount] = patterns0;
 200
 201       if ((err = re_compile_pattern (motif, len,
 202                                     &(patterns[pcount].regexbuf))) != 0)
 203         error (2, 0, err);
 204       pcount++;
 205
 206       motif = sep;
 207     } while (sep && total != 0);
 208
 209   /* In the match_words and match_lines cases, we use a different pattern
 210      for the DFA matcher that will quickly throw out cases that won't work.
 211      Then if DFA succeeds we do some hairy stuff using the regex matcher
 212      to decide whether the match should really count. */
 213   if (match_words || match_lines)
 214     {
 215       /* In the whole-word case, we use the pattern:
 216          \(^\|[^[:alnum:]_]\)\(userpattern\)\([^[:alnum:]_]|$\).
 217          In the whole-line case, we use the pattern:
 218          ^\(userpattern\)$.  */
 219
 220       static char const line_beg[] = "^\\(";
 221       static char const line_end[] = "\\)$";
 222       static char const word_beg[] = "\\(^\\|[^[:alnum:]_]\\)\\(";
 223       static char const word_end[] = "\\)\\([^[:alnum:]_]\\|$\\)";
 224       char *n = xmalloc (sizeof word_beg - 1 + size + sizeof word_end);
 225       size_t i;
 226       strcpy (n, match_lines ? line_beg : word_beg);
 227       i = strlen (n);
 228       memcpy (n + i, pattern, size);
 229       i += size;
 230       strcpy (n + i, match_lines ? line_end : word_end);
 231       i += strlen (n + i);
 232       pattern = n;
 233       size = i;
 234     }
 235
 236   dfacomp (pattern, size, &dfa, 1);
 237   kwsmusts ();
 238 }
 239
 240 static void
 241 Ecompile (char const *pattern, size_t size)
 242 {
 243   const char *err;
 244   const char *sep;
 245   size_t total = size;
 246   char const *motif = pattern;
 247
 248   check_utf8 ();
 249   if (strcmp (matcher, "awk") == 0)
 250     {
 251       re_set_syntax (RE_SYNTAX_AWK | (match_icase ? RE_ICASE : 0));
 252       dfasyntax (RE_SYNTAX_AWK, match_icase, eolbyte);
 253     }
 254   else
 255     {
 256       re_set_syntax (RE_SYNTAX_POSIX_EGREP | (match_icase ? RE_ICASE : 0));
 257       dfasyntax (RE_SYNTAX_POSIX_EGREP, match_icase, eolbyte);
 258     }
 259
 260   /* For GNU regex compiler we have to pass the patterns separately to detect
 261      errors like "[\nallo\n]\n".  The patterns here are "[", "allo" and "]"
 262      GNU regex should have raise a syntax error.  The same for backref, where
 263      the backref should have been local to each pattern.  */
 264   do
 265     {
 266       size_t len;
 267       sep = memchr (motif, '\n', total);
 268       if (sep)
 269         {
 270           len = sep - motif;
 271           sep++;
 272           total -= (len + 1);
 273         }
 274       else
 275         {
 276           len = total;
 277           total = 0;
 278         }
 279
 280       patterns = realloc (patterns, (pcount + 1) * sizeof (*patterns));
 281       if (patterns == NULL)
 282         error (2, errno, _("memory exhausted"));
 283       patterns[pcount] = patterns0;
 284
 285       if ((err = re_compile_pattern (motif, len,
 286                                     &(patterns[pcount].regexbuf))) != 0)
 287         error (2, 0, err);
 288       pcount++;
 289
 290       motif = sep;
 291     } while (sep && total != 0);
 292
 293   /* In the match_words and match_lines cases, we use a different pattern
 294      for the DFA matcher that will quickly throw out cases that won't work.
 295      Then if DFA succeeds we do some hairy stuff using the regex matcher
 296      to decide whether the match should really count. */
 297   if (match_words || match_lines)
 298     {
 299       /* In the whole-word case, we use the pattern:
 300          (^|[^[:alnum:]_])(userpattern)([^[:alnum:]_]|$).
 301          In the whole-line case, we use the pattern:
 302          ^(userpattern)$.  */
 303
 304       static char const line_beg[] = "^(";
 305       static char const line_end[] = ")$";
 306       static char const word_beg[] = "(^|[^[:alnum:]_])(";
 307       static char const word_end[] = ")([^[:alnum:]_]|$)";
 308       char *n = xmalloc (sizeof word_beg - 1 + size + sizeof word_end);
 309       size_t i;
 310       strcpy (n, match_lines ? line_beg : word_beg);
 311       i = strlen(n);
 312       memcpy (n + i, pattern, size);
 313       i += size;
 314       strcpy (n + i, match_lines ? line_end : word_end);
 315       i += strlen (n + i);
 316       pattern = n;
 317       size = i;
 318     }
 319
 320   dfacomp (pattern, size, &dfa, 1);
 321   kwsmusts ();
 322 }
 323
 324 static size_t
 325 EGexecute (char const *buf, size_t size, size_t *match_size, int exact)
 326 {
 327   register char const *buflim, *beg, *end;
 328   char eol = eolbyte;
 329   int backref, start, len;
 330   struct kwsmatch kwsm;
 331   size_t i, ret_val;
 332   static int use_dfa;
 333   static int use_dfa_checked = 0;
 334 #ifdef MBS_SUPPORT
 335   const char *last_char = NULL;
 336   int mb_cur_max = MB_CUR_MAX;
 337   mbstate_t mbs;
 338   memset (&mbs, '\0', sizeof (mbstate_t));
 339 #endif /* MBS_SUPPORT */
 340
 341   if (!use_dfa_checked)
 342     {
 343       char *grep_use_dfa = getenv ("GREP_USE_DFA");
 344       if (!grep_use_dfa)
 345         {
 346 #ifdef MBS_SUPPORT
 347           /* Turn off DFA when processing multibyte input. */
 348           use_dfa = (MB_CUR_MAX == 1);
 349 #else
 350           use_dfa = 1;
 351 #endif /* MBS_SUPPORT */
 352         }
 353       else
 354         {
 355           use_dfa = atoi (grep_use_dfa);
 356         }
 357
 358       use_dfa_checked = 1;
 359     }
 360
 361   buflim = buf + size;
 362
 363   for (beg = end = buf; end < buflim; beg = end)
 364     {
 365       if (!exact)
 366         {
 367           if (kwset)
 368             {
 369               /* Find a possible match using the KWset matcher. */
 370 #ifdef MBS_SUPPORT
 371               size_t bytes_left = 0;
 372 #endif /* MBS_SUPPORT */
 373               size_t offset;
 374 #ifdef MBS_SUPPORT
 375               /* kwsexec doesn't work with match_icase and multibyte input. */
 376               if (match_icase && mb_cur_max > 1)
 377                 /* Avoid kwset */
 378                 offset = 0;
 379               else
 380 #endif /* MBS_SUPPORT */
 381               offset = kwsexec (kwset, beg, buflim - beg, &kwsm);
 382               if (offset == (size_t) -1)
 383                 goto failure;
 384 #ifdef MBS_SUPPORT
 385               if (mb_cur_max > 1 && !using_utf8)
 386                 {
 387                   bytes_left = offset;
 388                   while (bytes_left)
 389                     {
 390                       size_t mlen = mbrlen (beg, bytes_left, &mbs);
 391
 392                       last_char = beg;
 393                       if (mlen == (size_t) -1 || mlen == 0)
 394                         {
 395                           /* Incomplete character: treat as single-byte. */
 396                           memset (&mbs, '\0', sizeof (mbstate_t));
 397                           beg++;
 398                           bytes_left--;
 399                           continue;
 400                         }
 401
 402                       if (mlen == (size_t) -2)
 403                         /* Offset points inside multibyte character:
 404                          * no good. */
 405                         break;
 406
 407                       beg += mlen;
 408                       bytes_left -= mlen;
 409                     }
 410                 }
 411               else
 412 #endif /* MBS_SUPPORT */
 413               beg += offset;
 414               /* Narrow down to the line containing the candidate, and
 415                  run it through DFA. */
 416               end = memchr(beg, eol, buflim - beg);
 417               end++;
 418 #ifdef MBS_SUPPORT
 419               if (mb_cur_max > 1 && bytes_left)
 420                 continue;
 421 #endif /* MBS_SUPPORT */
 422               while (beg > buf && beg[-1] != eol)
 423                 --beg;
 424               if (
 425 #ifdef MBS_SUPPORT
 426                   !(match_icase && mb_cur_max > 1) &&
 427 #endif /* MBS_SUPPORT */
 428                   (kwsm.index < kwset_exact_matches))
 429                 goto success_in_beg_and_end;
 430               if (use_dfa &&
 431                   dfaexec (&dfa, beg, end - beg, &backref) == (size_t) -1)
 432                 continue;
 433             }
 434           else
 435             {
 436               /* No good fixed strings; start with DFA. */
 437 #ifdef MBS_SUPPORT
 438               size_t bytes_left = 0;
 439 #endif /* MBS_SUPPORT */
 440               size_t offset = 0;
 441               if (use_dfa)
 442                 offset = dfaexec (&dfa, beg, buflim - beg, &backref);
 443               if (offset == (size_t) -1)
 444                 break;
 445               /* Narrow down to the line we've found. */
 446 #ifdef MBS_SUPPORT
 447               if (mb_cur_max > 1 && !using_utf8)
 448                 {
 449                   bytes_left = offset;
 450                   while (bytes_left)
 451                     {
 452                       size_t mlen = mbrlen (beg, bytes_left, &mbs);
 453
 454                       last_char = beg;
 455                       if (mlen == (size_t) -1 || mlen == 0)
 456                         {
 457                           /* Incomplete character: treat as single-byte. */
 458                           memset (&mbs, '\0', sizeof (mbstate_t));
 459                           beg++;
 460                           bytes_left--;
 461                           continue;
 462                         }
 463
 464                       if (mlen == (size_t) -2)
 465                         /* Offset points inside multibyte character:
 466                          * no good. */
 467                         break;
 468
 469                       beg += mlen;
 470                       bytes_left -= mlen;
 471                     }
 472                 }
 473               else
 474 #endif /* MBS_SUPPORT */
 475               beg += offset;
 476               end = memchr (beg, eol, buflim - beg);
 477               end++;
 478 #ifdef MBS_SUPPORT
 479               if (mb_cur_max > 1 && bytes_left)
 480                 continue;
 481 #endif /* MBS_SUPPORT */
 482               while (beg > buf && beg[-1] != eol)
 483                 --beg;
 484             }
 485           /* Successful, no backreferences encountered! */
 486           if (use_dfa && !backref)
 487             goto success_in_beg_and_end;
 488         }
 489       else
 490         end = beg + size;
 491
 492       /* If we've made it to this point, this means DFA has seen
 493          a probable match, and we need to run it through Regex. */
 494       for (i = 0; i < pcount; i++)
 495         {
 496           patterns[i].regexbuf.not_eol = 0;
 497           if (0 <= (start = re_search (&(patterns[i].regexbuf), beg,
 498                                        end - beg - 1, 0,
 499                                        end - beg - 1, &(patterns[i].regs))))
 500             {
 501               len = patterns[i].regs.end[0] - start;
 502               if (exact && !match_words)
 503                 goto success_in_start_and_len;
 504               if ((!match_lines && !match_words)
 505                   || (match_lines && len == end - beg - 1))
 506                 goto success_in_beg_and_end;
 507               /* If -w, check if the match aligns with word boundaries.
 508                  We do this iteratively because:
 509                  (a) the line may contain more than one occurence of the
 510                  pattern, and
 511                  (b) Several alternatives in the pattern might be valid at a
 512                  given point, and we may need to consider a shorter one to
 513                  find a word boundary.  */
 514               if (match_words)
 515                 while (start >= 0)
 516                   {
 517                     int lword_match = 0;
 518                     if (start == 0)
 519                       lword_match = 1;
 520                     else
 521                       {
 522                         assert (start > 0);
 523 #ifdef MBS_SUPPORT
 524                         if (mb_cur_max > 1)
 525                           {
 526                             const char *s;
 527                             size_t mr;
 528                             wchar_t pwc;
 529
 530                             /* Locate the start of the multibyte character
 531                                before the match position (== beg + start).  */
 532                             if (using_utf8)
 533                               {
 534                                 /* UTF-8 is a special case: scan backwards
 535                                    until we find a 7-bit character or a
 536                                    lead byte.  */
 537                                 s = beg + start - 1;
 538                                 while (s > buf
 539                                        && (unsigned char) *s >= 0x80
 540                                        && (unsigned char) *s <= 0xbf)
 541                                   --s;
 542                               }
 543                             else
 544                               {
 545                                 /* Scan forwards to find the start of the
 546                                    last complete character before the
 547                                    match position.  */
 548                                 size_t bytes_left = start - 1;
 549                                 s = beg;
 550                                 while (bytes_left > 0)
 551                                   {
 552                                     mr = mbrlen (s, bytes_left, &mbs);
 553                                     if (mr == (size_t) -1 || mr == 0)
 554                                       {
 555                                         memset (&mbs, '\0', sizeof (mbs));
 556                                         s++;
 557                                         bytes_left--;
 558                                         continue;
 559                                       }
 560                                     if (mr == (size_t) -2)
 561                                       {
 562                                         memset (&mbs, '\0', sizeof (mbs));
 563                                         break;
 564                                       }
 565                                     s += mr;
 566                                     bytes_left -= mr;
 567                                   }
 568                               }
 569                             mr = mbrtowc (&pwc, s, beg + start - s, &mbs);
 570                             if (mr == (size_t) -2 || mr == (size_t) -1 ||
 571                                 mr == 0)
 572                               {
 573                                 memset (&mbs, '\0', sizeof (mbstate_t));
 574                                 lword_match = 1;
 575                               }
 576                             else if (!(iswalnum (pwc) || pwc == L'_')
 577                                      && mr == beg + start - s)
 578                               lword_match = 1;
 579                           }
 580                         else
 581 #endif /* MBS_SUPPORT */
 582                         if (!WCHAR ((unsigned char) beg[start - 1]))
 583                           lword_match = 1;
 584                       }
 585
 586                     if (lword_match)
 587                       {
 588                         int rword_match = 0;
 589                         if (start + len == end - beg - 1)
 590                           rword_match = 1;
 591                         else
 592                           {
 593 #ifdef MBS_SUPPORT
 594                             if (mb_cur_max > 1)
 595                               {
 596                                 wchar_t nwc;
 597                                 int mr;
 598
 599                                 mr = mbtowc (&nwc, beg + start + len,
 600                                              end - beg - start - len - 1);
 601                                 if (mr <= 0)
 602                                   {
 603                                     memset (&mbs, '\0', sizeof (mbstate_t));
 604                                     rword_match = 1;
 605                                   }
 606                                 else if (!iswalnum (nwc) && nwc != L'_')
 607                                   rword_match = 1;
 608                               }
 609                             else
 610 #endif /* MBS_SUPPORT */
 611                             if (!WCHAR ((unsigned char) beg[start + len]))
 612                               rword_match = 1;
 613                           }
 614
 615                         if (rword_match)
 616                           {
 617                             if (!exact)
 618                               /* Returns the whole line. */
 619                               goto success_in_beg_and_end;
 620                             else
 621                               /* Returns just this word match. */
 622                               goto success_in_start_and_len;
 623                           }
 624                       }
 625                     if (len > 0)
 626                       {
 627                         /* Try a shorter length anchored at the same place. */
 628                         --len;
 629                         patterns[i].regexbuf.not_eol = 1;
 630                         len = re_match (&(patterns[i].regexbuf), beg,
 631                                         start + len, start,
 632                                         &(patterns[i].regs));
 633                       }
 634                     if (len <= 0)
 635                       {
 636                         /* Try looking further on. */
 637                         if (start == end - beg - 1)
 638                           break;
 639                         ++start;
 640                         patterns[i].regexbuf.not_eol = 0;
 641                         start = re_search (&(patterns[i].regexbuf), beg,
 642                                            end - beg - 1,
 643                                            start, end - beg - 1 - start,
 644                                            &(patterns[i].regs));
 645                         len = patterns[i].regs.end[0] - start;
 646                       }
 647                   }
 648             }
 649         } /* for Regex patterns.  */
 650     } /* for (beg = end ..) */
 651
 652  failure:
 653   return (size_t) -1;
 654
 655  success_in_beg_and_end:
 656   len = end - beg;
 657   start = beg - buf;
 658   /* FALLTHROUGH */
 659
 660  success_in_start_and_len:
 661   *match_size = len;
 662   return start;
 663 }
 664
 665 #ifdef MBS_SUPPORT
 666 static int f_i_multibyte; /* whether we're using the new -Fi MB method */
 667 static struct
 668 {
 669   wchar_t **patterns;
 670   size_t count, maxlen;
 671   unsigned char *match;
 672 } Fimb;
 673 #endif
 674
 675 static void
 676 Fcompile (char const *pattern, size_t size)
 677 {
 678   int mb_cur_max = MB_CUR_MAX;
 679   char const *beg, *lim, *err;
 680
 681   check_utf8 ();
 682 #ifdef MBS_SUPPORT
 683   /* Support -F -i for UTF-8 input. */
 684   if (match_icase && mb_cur_max > 1)
 685     {
 686       mbstate_t mbs;
 687       wchar_t *wcpattern = xmalloc ((size + 1) * sizeof (wchar_t));
 688       const char *patternend = pattern;
 689       size_t wcsize;
 690       kwset_t fimb_kwset = NULL;
 691       char *starts = NULL;
 692       wchar_t *wcbeg, *wclim;
 693       size_t allocated = 0;
 694
 695       memset (&mbs, '\0', sizeof (mbs));
 696 # ifdef __GNU_LIBRARY__
 697       wcsize = mbsnrtowcs (wcpattern, &patternend, size, size, &mbs);
 698       if (patternend != pattern + size)
 699         wcsize = (size_t) -1;
 700 # else
 701       {
 702         char *patterncopy = xmalloc (size + 1);
 703
 704         memcpy (patterncopy, pattern, size);
 705         patterncopy[size] = '\0';
 706         patternend = patterncopy;
 707         wcsize = mbsrtowcs (wcpattern, &patternend, size, &mbs);
 708         if (patternend != patterncopy + size)
 709           wcsize = (size_t) -1;
 710         free (patterncopy);
 711       }
 712 # endif
 713       if (wcsize + 2 <= 2)
 714         {
 715 fimb_fail:
 716           free (wcpattern);
 717           free (starts);
 718           if (fimb_kwset)
 719             kwsfree (fimb_kwset);
 720           free (Fimb.patterns);
 721           Fimb.patterns = NULL;
 722         }
 723       else
 724         {
 725           if (!(fimb_kwset = kwsalloc (NULL)))
 726             error (2, 0, _("memory exhausted"));
 727
 728           starts = xmalloc (mb_cur_max * 3);
 729           wcbeg = wcpattern;
 730           do
 731             {
 732               int i;
 733               size_t wclen;
 734
 735               if (Fimb.count >= allocated)
 736                 {
 737                   if (allocated == 0)
 738                     allocated = 128;
 739                   else
 740                     allocated *= 2;
 741                   Fimb.patterns = xrealloc (Fimb.patterns,
 742                                             sizeof (wchar_t *) * allocated);
 743                 }
 744               Fimb.patterns[Fimb.count++] = wcbeg;
 745               for (wclim = wcbeg;
 746                    wclim < wcpattern + wcsize && *wclim != L'\n'; ++wclim)
 747                 *wclim = towlower (*wclim);
 748               *wclim = L'\0';
 749               wclen = wclim - wcbeg;
 750               if (wclen > Fimb.maxlen)
 751                 Fimb.maxlen = wclen;
 752               if (wclen > 3)
 753                 wclen = 3;
 754               if (wclen == 0)
 755                 {
 756                   if ((err = kwsincr (fimb_kwset, "", 0)) != 0)
 757                     error (2, 0, err);
 758                 }
 759               else
 760                 for (i = 0; i < (1 << wclen); i++)
 761                   {
 762                     char *p = starts;
 763                     int j, k;
 764
 765                     for (j = 0; j < wclen; ++j)
 766                       {
 767                         wchar_t wc = wcbeg[j];
 768                         if (i & (1 << j))
 769                           {
 770                             wc = towupper (wc);
 771                             if (wc == wcbeg[j])
 772                               continue;
 773                           }
 774                         k = wctomb (p, wc);
 775                         if (k <= 0)
 776                           goto fimb_fail;
 777                         p += k;
 778                       }
 779                     if ((err = kwsincr (fimb_kwset, starts, p - starts)) != 0)
 780                       error (2, 0, err);
 781                   }
 782               if (wclim < wcpattern + wcsize)
 783                 ++wclim;
 784               wcbeg = wclim;
 785             }
 786           while (wcbeg < wcpattern + wcsize);
 787           f_i_multibyte = 1;
 788           kwset = fimb_kwset;
 789           free (starts);
 790           Fimb.match = xmalloc (Fimb.count);
 791           if ((err = kwsprep (kwset)) != 0)
 792             error (2, 0, err);
 793           return;
 794         }
 795     }
 796 #endif /* MBS_SUPPORT */
 797
 798
 799   kwsinit ();
 800   beg = pattern;
 801   do
 802     {
 803       for (lim = beg; lim < pattern + size && *lim != '\n'; ++lim)
 804         ;
 805       if ((err = kwsincr (kwset, beg, lim - beg)) != 0)
 806         error (2, 0, err);
 807       if (lim < pattern + size)
 808         ++lim;
 809       beg = lim;
 810     }
 811   while (beg < pattern + size);
 812
 813   if ((err = kwsprep (kwset)) != 0)
 814     error (2, 0, err);
 815 }
 816
 817 #ifdef MBS_SUPPORT
 818 static int
 819 Fimbexec (const char *buf, size_t size, size_t *plen, int exact)
 820 {
 821   size_t len, letter, i;
 822   int ret = -1;
 823   mbstate_t mbs;
 824   wchar_t wc;
 825   int patterns_left;
 826
 827   assert (match_icase && f_i_multibyte == 1);
 828   assert (MB_CUR_MAX > 1);
 829
 830   memset (&mbs, '\0', sizeof (mbs));
 831   memset (Fimb.match, '\1', Fimb.count);
 832   letter = len = 0;
 833   patterns_left = 1;
 834   while (patterns_left && len <= size)
 835     {
 836       size_t c;
 837
 838       patterns_left = 0;
 839       if (len < size)
 840         {
 841           c = mbrtowc (&wc, buf + len, size - len, &mbs);
 842           if (c + 2 <= 2)
 843             return ret;
 844
 845           wc = towlower (wc);
 846         }
 847       else
 848         {
 849           c = 1;
 850           wc = L'\0';
 851         }
 852
 853       for (i = 0; i < Fimb.count; i++)
 854         {
 855           if (Fimb.match[i])
 856             {
 857               if (Fimb.patterns[i][letter] == L'\0')
 858                 {
 859                   /* Found a match. */
 860                   *plen = len;
 861                   if (!exact && !match_words)
 862                     return 0;
 863                   else
 864                     {
 865                       /* For -w or exact look for longest match.  */
 866                       ret = 0;
 867                       Fimb.match[i] = '\0';
 868                       continue;
 869                     }
 870                 }
 871
 872               if (Fimb.patterns[i][letter] == wc)
 873                 patterns_left = 1;
 874               else
 875                 Fimb.match[i] = '\0';
 876             }
 877         }
 878
 879       len += c;
 880       letter++;
 881     }
 882
 883   return ret;
 884 }
 885 #endif /* MBS_SUPPORT */
 886
 887 static size_t
 888 Fexecute (char const *buf, size_t size, size_t *match_size, int exact)
 889 {
 890   register char const *beg, *try, *end;
 891   register size_t len;
 892   char eol = eolbyte;
 893   struct kwsmatch kwsmatch;
 894   size_t ret_val;
 895 #ifdef MBS_SUPPORT
 896   int mb_cur_max = MB_CUR_MAX;
 897   mbstate_t mbs;
 898   memset (&mbs, '\0', sizeof (mbstate_t));
 899   const char *last_char = NULL;
 900 #endif /* MBS_SUPPORT */
 901
 902   for (beg = buf; beg <= buf + size; ++beg)
 903     {
 904       size_t offset;
 905       offset = kwsexec (kwset, beg, buf + size - beg, &kwsmatch);
 906
 907       if (offset == (size_t) -1)
 908         goto failure;
 909 #ifdef MBS_SUPPORT
 910       if (mb_cur_max > 1 && !using_utf8)
 911         {
 912           size_t bytes_left = offset;
 913           while (bytes_left)
 914             {
 915               size_t mlen = mbrlen (beg, bytes_left, &mbs);
 916
 917               last_char = beg;
 918               if (mlen == (size_t) -1 || mlen == 0)
 919                 {
 920                   /* Incomplete character: treat as single-byte. */
 921                   memset (&mbs, '\0', sizeof (mbstate_t));
 922                   beg++;
 923                   bytes_left--;
 924                   continue;
 925                 }
 926
 927               if (mlen == (size_t) -2)
 928                 /* Offset points inside multibyte character: no good. */
 929                 break;
 930
 931               beg += mlen;
 932               bytes_left -= mlen;
 933             }
 934
 935           if (bytes_left)
 936             continue;
 937         }
 938       else
 939 #endif /* MBS_SUPPORT */
 940       beg += offset;
 941 #ifdef MBS_SUPPORT
 942       /* For f_i_multibyte, the string at beg now matches first 3 chars of
 943          one of the search strings (less if there are shorter search strings).
 944          See if this is a real match.  */
 945       if (f_i_multibyte
 946           && Fimbexec (beg, buf + size - beg, &kwsmatch.size[0], exact))
 947         goto next_char;
 948 #endif /* MBS_SUPPORT */
 949       len = kwsmatch.size[0];
 950       if (exact && !match_words)
 951         goto success_in_beg_and_len;
 952       if (match_lines)
 953         {
 954           if (beg > buf && beg[-1] != eol)
 955             goto next_char;
 956           if (beg + len < buf + size && beg[len] != eol)
 957             goto next_char;
 958           goto success;
 959         }
 960       else if (match_words)
 961         {
 962           while (1)
 963             {
 964               int word_match = 0;
 965               if (beg > buf)
 966                 {
 967 #ifdef MBS_SUPPORT
 968                   if (mb_cur_max > 1)
 969                     {
 970                       const char *s;
 971                       int mr;
 972                       wchar_t pwc;
 973
 974                       if (using_utf8)
 975                         {
 976                           s = beg - 1;
 977                           while (s > buf
 978                                  && (unsigned char) *s >= 0x80
 979                                  && (unsigned char) *s <= 0xbf)
 980                             --s;
 981                         }
 982                       else
 983                         s = last_char;
 984                       mr = mbtowc (&pwc, s, beg - s);
 985                       if (mr <= 0)
 986                         memset (&mbs, '\0', sizeof (mbstate_t));
 987                       else if ((iswalnum (pwc) || pwc == L'_')
 988                                && mr == (int) (beg - s))
 989                         goto next_char;
 990                     }
 991                   else
 992 #endif /* MBS_SUPPORT */
 993                   if (WCHAR ((unsigned char) beg[-1]))
 994                     goto next_char;
 995                 }
 996 #ifdef MBS_SUPPORT
 997               if (mb_cur_max > 1)
 998                 {
 999                   wchar_t nwc;
1000                   int mr;
1001
1002                   mr = mbtowc (&nwc, beg + len, buf + size - beg - len);
1003                   if (mr <= 0)
1004                     {
1005                       memset (&mbs, '\0', sizeof (mbstate_t));
1006                       word_match = 1;
1007                     }
1008                   else if (!iswalnum (nwc) && nwc != L'_')
1009                     word_match = 1;
1010                 }
1011               else
1012 #endif /* MBS_SUPPORT */
1013                 if (beg + len >= buf + size || !WCHAR ((unsigned char) beg[len]))
1014                   word_match = 1;
1015               if (word_match)
1016                 {
1017                   if (!exact)
1018                     /* Returns the whole line now we know there's a word match. */
1019                     goto success;
1020                   else
1021                     /* Returns just this word match. */
1022                     goto success_in_beg_and_len;
1023                 }
1024               if (len > 0)
1025                 {
1026                   /* Try a shorter length anchored at the same place. */
1027                   --len;
1028                   offset = kwsexec (kwset, beg, len, &kwsmatch);
1029
1030                   if (offset == -1)
1031                     goto next_char; /* Try a different anchor. */
1032 #ifdef MBS_SUPPORT
1033                   if (mb_cur_max > 1 && !using_utf8)
1034                     {
1035                       size_t bytes_left = offset;
1036                       while (bytes_left)
1037                         {
1038                           size_t mlen = mbrlen (beg, bytes_left, &mbs);
1039
1040                           last_char = beg;
1041                           if (mlen == (size_t) -1 || mlen == 0)
1042                             {
1043                               /* Incomplete character: treat as single-byte. */
1044                               memset (&mbs, '\0', sizeof (mbstate_t));
1045                               beg++;
1046                               bytes_left--;
1047                               continue;
1048                             }
1049
1050                           if (mlen == (size_t) -2)
1051                             {
1052                               /* Offset points inside multibyte character:
1053                                * no good. */
1054                               break;
1055                             }
1056
1057                           beg += mlen;
1058                           bytes_left -= mlen;
1059                         }
1060
1061                       if (bytes_left)
1062                         {
1063                           memset (&mbs, '\0', sizeof (mbstate_t));
1064                           goto next_char; /* Try a different anchor. */
1065                         }
1066                     }
1067                   else
1068 #endif /* MBS_SUPPORT */
1069                   beg += offset;
1070 #ifdef MBS_SUPPORT
1071                   /* The string at beg now matches first 3 chars of one of
1072                      the search strings (less if there are shorter search
1073                      strings).  See if this is a real match.  */
1074                   if (f_i_multibyte
1075                       && Fimbexec (beg, len - offset, &kwsmatch.size[0],
1076                                    exact))
1077                     goto next_char;
1078 #endif /* MBS_SUPPORT */
1079                   len = kwsmatch.size[0];
1080                 }
1081             }
1082         }
1083       else
1084         goto success;
1085 next_char:;
1086 #ifdef MBS_SUPPORT
1087       /* Advance to next character.  For MB_CUR_MAX == 1 case this is handled
1088          by ++beg above.  */
1089       if (mb_cur_max > 1)
1090         {
1091           if (using_utf8)
1092             {
1093               unsigned char c = *beg;
1094               if (c >= 0xc2)
1095                 {
1096                   if (c < 0xe0)
1097                     ++beg;
1098                   else if (c < 0xf0)
1099                     beg += 2;
1100                   else if (c < 0xf8)
1101                     beg += 3;
1102                   else if (c < 0xfc)
1103                     beg += 4;
1104                   else if (c < 0xfe)
1105                     beg += 5;
1106                 }
1107             }
1108           else
1109             {
1110               size_t l = mbrlen (beg, buf + size - beg, &mbs);
1111
1112               last_char = beg;
1113               if (l + 2 >= 2)
1114                 beg += l - 1;
1115               else
1116                 memset (&mbs, '\0', sizeof (mbstate_t));
1117             }
1118         }
1119 #endif /* MBS_SUPPORT */
1120     }
1121
1122  failure:
1123   return -1;
1124
1125  success:
1126 #ifdef MBS_SUPPORT
1127   if (mb_cur_max > 1 && !using_utf8)
1128     {
1129       end = beg + len;
1130       while (end < buf + size)
1131         {
1132           size_t mlen = mbrlen (end, buf + size - end, &mbs);
1133           if (mlen == (size_t) -1 || mlen == (size_t) -2 || mlen == 0)
1134             {
1135               memset (&mbs, '\0', sizeof (mbstate_t));
1136               mlen = 1;
1137             }
1138           if (mlen == 1 && *end == eol)
1139             break;
1140
1141           end += mlen;
1142         }
1143     }
1144   else
1145 #endif /* MBS_SUPPORT */
1146   end = memchr (beg + len, eol, (buf + size) - (beg + len));
1147
1148   end++;
1149   while (buf < beg && beg[-1] != eol)
1150     --beg;
1151   len = end - beg;
1152   /* FALLTHROUGH */
1153
1154  success_in_beg_and_len:
1155   *match_size = len;
1156   return beg - buf;
1157 }
1158
1159 #if HAVE_LIBPCRE
1160 /* Compiled internal form of a Perl regular expression.  */
1161 static pcre *cre;
1162
1163 /* Additional information about the pattern.  */
1164 static pcre_extra *extra;
1165 #endif
1166
1167 static void
1168 Pcompile (char const *pattern, size_t size)
1169 {
1170 #if !HAVE_LIBPCRE
1171   error (2, 0, _("The -P option is not supported"));
1172 #else
1173   int e;
1174   char const *ep;
1175   char *re = xmalloc (4 * size + 7);
1176   int flags = PCRE_MULTILINE | (match_icase ? PCRE_CASELESS : 0);
1177   char const *patlim = pattern + size;
1178   char *n = re;
1179   char const *p;
1180   char const *pnul;
1181
1182   /* FIXME: Remove this restriction.  */
1183   if (eolbyte != '\n')
1184     error (2, 0, _("The -P and -z options cannot be combined"));
1185
1186   *n = '\0';
1187   if (match_lines)
1188     strcpy (n, "^(");
1189   if (match_words)
1190     strcpy (n, "\\b(");
1191   n += strlen (n);
1192
1193   /* The PCRE interface doesn't allow NUL bytes in the pattern, so
1194      replace each NUL byte in the pattern with the four characters
1195      "\000", removing a preceding backslash if there are an odd
1196      number of backslashes before the NUL.
1197
1198      FIXME: This method does not work with some multibyte character
1199      encodings, notably Shift-JIS, where a multibyte character can end
1200      in a backslash byte.  */
1201   for (p = pattern; (pnul = memchr (p, '\0', patlim - p)); p = pnul + 1)
1202     {
1203       memcpy (n, p, pnul - p);
1204       n += pnul - p;
1205       for (p = pnul; pattern < p && p[-1] == '\\'; p--)
1206         continue;
1207       n -= (pnul - p) & 1;
1208       strcpy (n, "\\000");
1209       n += 4;
1210     }
1211
1212   memcpy (n, p, patlim - p);
1213   n += patlim - p;
1214   *n = '\0';
1215   if (match_words)
1216     strcpy (n, ")\\b");
1217   if (match_lines)
1218     strcpy (n, ")$");
1219
1220   cre = pcre_compile (re, flags, &ep, &e, pcre_maketables ());
1221   if (!cre)
1222     error (2, 0, ep);
1223
1224   extra = pcre_study (cre, 0, &ep);
1225   if (ep)
1226     error (2, 0, ep);
1227
1228   free (re);
1229 #endif
1230 }
1231
1232 static size_t
1233 Pexecute (char const *buf, size_t size, size_t *match_size, int exact)
1234 {
1235 #if !HAVE_LIBPCRE
1236   abort ();
1237   return -1;
1238 #else
1239   /* This array must have at least two elements; everything after that
1240      is just for performance improvement in pcre_exec.  */
1241   int sub[300];
1242
1243   int e = pcre_exec (cre, extra, buf, size, 0, 0,
1244                      sub, sizeof sub / sizeof *sub);
1245
1246   if (e <= 0)
1247     {
1248       switch (e)
1249         {
1250         case PCRE_ERROR_NOMATCH:
1251           return -1;
1252
1253         case PCRE_ERROR_NOMEMORY:
1254           error (2, 0, _("Memory exhausted"));
1255
1256         default:
1257           abort ();
1258         }
1259     }
1260   else
1261     {
1262       /* Narrow down to the line we've found.  */
1263       char const *beg = buf + sub[0];
1264       char const *end = buf + sub[1];
1265       char const *buflim = buf + size;
1266       char eol = eolbyte;
1267       if (!exact)
1268         {
1269           end = memchr (end, eol, buflim - end);
1270           end++;
1271           while (buf < beg && beg[-1] != eol)
1272             --beg;
1273         }
1274
1275       *match_size = end - beg;
1276       return beg - buf;
1277     }
1278 #endif
1279 }
1280
1281 struct matcher const matchers[] = {
1282   { "default", Gcompile, EGexecute },
1283   { "grep", Gcompile, EGexecute },
1284   { "egrep", Ecompile, EGexecute },
1285   { "awk", Ecompile, EGexecute },
1286   { "fgrep", Fcompile, Fexecute },
1287   { "perl", Pcompile, Pexecute },
1288   { "", 0, 0 },
1289 };