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   size_t 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;
 330   ptrdiff_t start, len;
 331   struct kwsmatch kwsm;
 332   size_t i, ret_val;
 333   static int use_dfa;
 334   static int use_dfa_checked = 0;
 335 #ifdef MBS_SUPPORT
 336   const char *last_char = NULL;
 337   int mb_cur_max = MB_CUR_MAX;
 338   mbstate_t mbs;
 339   memset (&mbs, '\0', sizeof (mbstate_t));
 340 #endif /* MBS_SUPPORT */
 341
 342   if (!use_dfa_checked)
 343     {
 344       char *grep_use_dfa = getenv ("GREP_USE_DFA");
 345       if (!grep_use_dfa)
 346         {
 347 #ifdef MBS_SUPPORT
 348           /* Turn off DFA when processing multibyte input. */
 349           use_dfa = (MB_CUR_MAX == 1);
 350 #else
 351           use_dfa = 1;
 352 #endif /* MBS_SUPPORT */
 353         }
 354       else
 355         {
 356           use_dfa = atoi (grep_use_dfa);
 357         }
 358
 359       use_dfa_checked = 1;
 360     }
 361
 362   buflim = buf + size;
 363
 364   for (beg = end = buf; end < buflim; beg = end)
 365     {
 366       if (!exact)
 367         {
 368           if (kwset)
 369             {
 370               /* Find a possible match using the KWset matcher. */
 371 #ifdef MBS_SUPPORT
 372               size_t bytes_left = 0;
 373 #endif /* MBS_SUPPORT */
 374               size_t offset;
 375 #ifdef MBS_SUPPORT
 376               /* kwsexec doesn't work with match_icase and multibyte input. */
 377               if (match_icase && mb_cur_max > 1)
 378                 /* Avoid kwset */
 379                 offset = 0;
 380               else
 381 #endif /* MBS_SUPPORT */
 382               offset = kwsexec (kwset, beg, buflim - beg, &kwsm);
 383               if (offset == (size_t) -1)
 384                 goto failure;
 385 #ifdef MBS_SUPPORT
 386               if (mb_cur_max > 1 && !using_utf8)
 387                 {
 388                   bytes_left = offset;
 389                   while (bytes_left)
 390                     {
 391                       size_t mlen = mbrlen (beg, bytes_left, &mbs);
 392
 393                       last_char = beg;
 394                       if (mlen == (size_t) -1 || mlen == 0)
 395                         {
 396                           /* Incomplete character: treat as single-byte. */
 397                           memset (&mbs, '\0', sizeof (mbstate_t));
 398                           beg++;
 399                           bytes_left--;
 400                           continue;
 401                         }
 402
 403                       if (mlen == (size_t) -2)
 404                         {
 405                           /* Offset points inside multibyte character:
 406                            * no good. */
 407                           memset (&mbs, '\0', sizeof (mbstate_t));
 408                           break;
 409                         }
 410
 411                       beg += mlen;
 412                       bytes_left -= mlen;
 413                     }
 414                 }
 415               else
 416 #endif /* MBS_SUPPORT */
 417               beg += offset;
 418               /* Narrow down to the line containing the candidate, and
 419                  run it through DFA. */
 420               end = memchr(beg, eol, buflim - beg);
 421               end++;
 422 #ifdef MBS_SUPPORT
 423               if (mb_cur_max > 1 && bytes_left)
 424                 continue;
 425 #endif /* MBS_SUPPORT */
 426               while (beg > buf && beg[-1] != eol)
 427                 --beg;
 428               if (
 429 #ifdef MBS_SUPPORT
 430                   !(match_icase && mb_cur_max > 1) &&
 431 #endif /* MBS_SUPPORT */
 432                   (kwsm.index < kwset_exact_matches))
 433                 goto success_in_beg_and_end;
 434               if (use_dfa &&
 435                   dfaexec (&dfa, beg, end - beg, &backref) == (size_t) -1)
 436                 continue;
 437             }
 438           else
 439             {
 440               /* No good fixed strings; start with DFA. */
 441 #ifdef MBS_SUPPORT
 442               size_t bytes_left = 0;
 443 #endif /* MBS_SUPPORT */
 444               size_t offset = 0;
 445               if (use_dfa)
 446                 offset = dfaexec (&dfa, beg, buflim - beg, &backref);
 447               if (offset == (size_t) -1)
 448                 break;
 449               /* Narrow down to the line we've found. */
 450 #ifdef MBS_SUPPORT
 451               if (mb_cur_max > 1 && !using_utf8)
 452                 {
 453                   bytes_left = offset;
 454                   while (bytes_left)
 455                     {
 456                       size_t mlen = mbrlen (beg, bytes_left, &mbs);
 457
 458                       last_char = beg;
 459                       if (mlen == (size_t) -1 || mlen == 0)
 460                         {
 461                           /* Incomplete character: treat as single-byte. */
 462                           memset (&mbs, '\0', sizeof (mbstate_t));
 463                           beg++;
 464                           bytes_left--;
 465                           continue;
 466                         }
 467
 468                       if (mlen == (size_t) -2)
 469                         {
 470                           /* Offset points inside multibyte character:
 471                            * no good. */
 472                           memset (&mbs, '\0', sizeof (mbstate_t));
 473                           break;
 474                         }
 475
 476                       beg += mlen;
 477                       bytes_left -= mlen;
 478                     }
 479                 }
 480               else
 481 #endif /* MBS_SUPPORT */
 482               beg += offset;
 483               end = memchr (beg, eol, buflim - beg);
 484               end++;
 485 #ifdef MBS_SUPPORT
 486               if (mb_cur_max > 1 && bytes_left)
 487                 continue;
 488 #endif /* MBS_SUPPORT */
 489               while (beg > buf && beg[-1] != eol)
 490                 --beg;
 491             }
 492           /* Successful, no backreferences encountered! */
 493           if (use_dfa && !backref)
 494             goto success_in_beg_and_end;
 495         }
 496       else
 497         end = beg + size;
 498
 499       /* If we've made it to this point, this means DFA has seen
 500          a probable match, and we need to run it through Regex. */
 501       for (i = 0; i < pcount; i++)
 502         {
 503           patterns[i].regexbuf.not_eol = 0;
 504           if (0 <= (start = re_search (&(patterns[i].regexbuf), beg,
 505                                        end - beg - 1, 0,
 506                                        end - beg - 1, &(patterns[i].regs))))
 507             {
 508               len = patterns[i].regs.end[0] - start;
 509               if (exact && !match_words)
 510                 goto success_in_start_and_len;
 511               if ((!match_lines && !match_words)
 512                   || (match_lines && len == end - beg - 1))
 513                 goto success_in_beg_and_end;
 514               /* If -w, check if the match aligns with word boundaries.
 515                  We do this iteratively because:
 516                  (a) the line may contain more than one occurence of the
 517                  pattern, and
 518                  (b) Several alternatives in the pattern might be valid at a
 519                  given point, and we may need to consider a shorter one to
 520                  find a word boundary.  */
 521               if (match_words)
 522                 while (start >= 0)
 523                   {
 524                     int lword_match = 0;
 525                     if (start == 0)
 526                       lword_match = 1;
 527                     else
 528                       {
 529                         assert (start > 0);
 530 #ifdef MBS_SUPPORT
 531                         if (mb_cur_max > 1)
 532                           {
 533                             const char *s;
 534                             size_t mr;
 535                             wchar_t pwc;
 536
 537                             /* Locate the start of the multibyte character
 538                                before the match position (== beg + start).  */
 539                             if (using_utf8)
 540                               {
 541                                 /* UTF-8 is a special case: scan backwards
 542                                    until we find a 7-bit character or a
 543                                    lead byte.  */
 544                                 s = beg + start - 1;
 545                                 while (s > buf
 546                                        && (unsigned char) *s >= 0x80
 547                                        && (unsigned char) *s <= 0xbf)
 548                                   --s;
 549                               }
 550                             else
 551                               {
 552                                 /* Scan forwards to find the start of the
 553                                    last complete character before the
 554                                    match position.  */
 555                                 size_t bytes_left = start - 1;
 556                                 s = beg;
 557                                 while (bytes_left > 0)
 558                                   {
 559                                     mr = mbrlen (s, bytes_left, &mbs);
 560                                     if (mr == (size_t) -1 || mr == 0)
 561                                       {
 562                                         memset (&mbs, '\0', sizeof (mbs));
 563                                         s++;
 564                                         bytes_left--;
 565                                         continue;
 566                                       }
 567                                     if (mr == (size_t) -2)
 568                                       {
 569                                         memset (&mbs, '\0', sizeof (mbs));
 570                                         break;
 571                                       }
 572                                     s += mr;
 573                                     bytes_left -= mr;
 574                                   }
 575                               }
 576                             mr = mbrtowc (&pwc, s, beg + start - s, &mbs);
 577                             if (mr == (size_t) -2 || mr == (size_t) -1 ||
 578                                 mr == 0)
 579                               {
 580                                 memset (&mbs, '\0', sizeof (mbstate_t));
 581                                 lword_match = 1;
 582                               }
 583                             else if (!(iswalnum (pwc) || pwc == L'_')
 584                                      && mr == beg + start - s)
 585                               lword_match = 1;
 586                           }
 587                         else
 588 #endif /* MBS_SUPPORT */
 589                         if (!WCHAR ((unsigned char) beg[start - 1]))
 590                           lword_match = 1;
 591                       }
 592
 593                     if (lword_match)
 594                       {
 595                         int rword_match = 0;
 596                         if (start + len == end - beg - 1)
 597                           rword_match = 1;
 598                         else
 599                           {
 600 #ifdef MBS_SUPPORT
 601                             if (mb_cur_max > 1)
 602                               {
 603                                 wchar_t nwc;
 604                                 int mr;
 605
 606                                 mr = mbtowc (&nwc, beg + start + len,
 607                                              end - beg - start - len - 1);
 608                                 if (mr <= 0)
 609                                   {
 610                                     memset (&mbs, '\0', sizeof (mbstate_t));
 611                                     rword_match = 1;
 612                                   }
 613                                 else if (!iswalnum (nwc) && nwc != L'_')
 614                                   rword_match = 1;
 615                               }
 616                             else
 617 #endif /* MBS_SUPPORT */
 618                             if (!WCHAR ((unsigned char) beg[start + len]))
 619                               rword_match = 1;
 620                           }
 621
 622                         if (rword_match)
 623                           {
 624                             if (!exact)
 625                               /* Returns the whole line. */
 626                               goto success_in_beg_and_end;
 627                             else
 628                               /* Returns just this word match. */
 629                               goto success_in_start_and_len;
 630                           }
 631                       }
 632                     if (len > 0)
 633                       {
 634                         /* Try a shorter length anchored at the same place. */
 635                         --len;
 636                         patterns[i].regexbuf.not_eol = 1;
 637                         len = re_match (&(patterns[i].regexbuf), beg,
 638                                         start + len, start,
 639                                         &(patterns[i].regs));
 640                       }
 641                     if (len <= 0)
 642                       {
 643                         /* Try looking further on. */
 644                         if (start == end - beg - 1)
 645                           break;
 646                         ++start;
 647                         patterns[i].regexbuf.not_eol = 0;
 648                         start = re_search (&(patterns[i].regexbuf), beg,
 649                                            end - beg - 1,
 650                                            start, end - beg - 1 - start,
 651                                            &(patterns[i].regs));
 652                         len = patterns[i].regs.end[0] - start;
 653                       }
 654                   }
 655             }
 656         } /* for Regex patterns.  */
 657     } /* for (beg = end ..) */
 658
 659  failure:
 660   return (size_t) -1;
 661
 662  success_in_beg_and_end:
 663   len = end - beg;
 664   start = beg - buf;
 665   /* FALLTHROUGH */
 666
 667  success_in_start_and_len:
 668   *match_size = len;
 669   return start;
 670 }
 671
 672 #ifdef MBS_SUPPORT
 673 static int f_i_multibyte; /* whether we're using the new -Fi MB method */
 674 static struct
 675 {
 676   wchar_t **patterns;
 677   size_t count, maxlen;
 678   unsigned char *match;
 679 } Fimb;
 680 #endif
 681
 682 static void
 683 Fcompile (char const *pattern, size_t size)
 684 {
 685   int mb_cur_max = MB_CUR_MAX;
 686   char const *beg, *lim, *err;
 687
 688   check_utf8 ();
 689 #ifdef MBS_SUPPORT
 690   /* Support -F -i for UTF-8 input. */
 691   if (match_icase && mb_cur_max > 1)
 692     {
 693       mbstate_t mbs;
 694       wchar_t *wcpattern = xmalloc ((size + 1) * sizeof (wchar_t));
 695       const char *patternend = pattern;
 696       size_t wcsize;
 697       kwset_t fimb_kwset = NULL;
 698       char *starts = NULL;
 699       wchar_t *wcbeg, *wclim;
 700       size_t allocated = 0;
 701
 702       memset (&mbs, '\0', sizeof (mbs));
 703 # ifdef __GNU_LIBRARY__
 704       wcsize = mbsnrtowcs (wcpattern, &patternend, size, size, &mbs);
 705       if (patternend != pattern + size)
 706         wcsize = (size_t) -1;
 707 # else
 708       {
 709         char *patterncopy = xmalloc (size + 1);
 710
 711         memcpy (patterncopy, pattern, size);
 712         patterncopy[size] = '\0';
 713         patternend = patterncopy;
 714         wcsize = mbsrtowcs (wcpattern, &patternend, size, &mbs);
 715         if (patternend != patterncopy + size)
 716           wcsize = (size_t) -1;
 717         free (patterncopy);
 718       }
 719 # endif
 720       if (wcsize + 2 <= 2)
 721         {
 722 fimb_fail:
 723           free (wcpattern);
 724           free (starts);
 725           if (fimb_kwset)
 726             kwsfree (fimb_kwset);
 727           free (Fimb.patterns);
 728           Fimb.patterns = NULL;
 729         }
 730       else
 731         {
 732           if (!(fimb_kwset = kwsalloc (NULL)))
 733             error (2, 0, _("memory exhausted"));
 734
 735           starts = xmalloc (mb_cur_max * 3);
 736           wcbeg = wcpattern;
 737           do
 738             {
 739               int i;
 740               size_t wclen;
 741
 742               if (Fimb.count >= allocated)
 743                 {
 744                   if (allocated == 0)
 745                     allocated = 128;
 746                   else
 747                     allocated *= 2;
 748                   Fimb.patterns = xrealloc (Fimb.patterns,
 749                                             sizeof (wchar_t *) * allocated);
 750                 }
 751               Fimb.patterns[Fimb.count++] = wcbeg;
 752               for (wclim = wcbeg;
 753                    wclim < wcpattern + wcsize && *wclim != L'\n'; ++wclim)
 754                 *wclim = towlower (*wclim);
 755               *wclim = L'\0';
 756               wclen = wclim - wcbeg;
 757               if (wclen > Fimb.maxlen)
 758                 Fimb.maxlen = wclen;
 759               if (wclen > 3)
 760                 wclen = 3;
 761               if (wclen == 0)
 762                 {
 763                   if ((err = kwsincr (fimb_kwset, "", 0)) != 0)
 764                     error (2, 0, err);
 765                 }
 766               else
 767                 for (i = 0; i < (1 << wclen); i++)
 768                   {
 769                     char *p = starts;
 770                     int j, k;
 771
 772                     for (j = 0; j < wclen; ++j)
 773                       {
 774                         wchar_t wc = wcbeg[j];
 775                         if (i & (1 << j))
 776                           {
 777                             wc = towupper (wc);
 778                             if (wc == wcbeg[j])
 779                               continue;
 780                           }
 781                         k = wctomb (p, wc);
 782                         if (k <= 0)
 783                           goto fimb_fail;
 784                         p += k;
 785                       }
 786                     if ((err = kwsincr (fimb_kwset, starts, p - starts)) != 0)
 787                       error (2, 0, err);
 788                   }
 789               if (wclim < wcpattern + wcsize)
 790                 ++wclim;
 791               wcbeg = wclim;
 792             }
 793           while (wcbeg < wcpattern + wcsize);
 794           f_i_multibyte = 1;
 795           kwset = fimb_kwset;
 796           free (starts);
 797           Fimb.match = xmalloc (Fimb.count);
 798           if ((err = kwsprep (kwset)) != 0)
 799             error (2, 0, err);
 800           return;
 801         }
 802     }
 803 #endif /* MBS_SUPPORT */
 804
 805
 806   kwsinit ();
 807   beg = pattern;
 808   do
 809     {
 810       for (lim = beg; lim < pattern + size && *lim != '\n'; ++lim)
 811         ;
 812       if ((err = kwsincr (kwset, beg, lim - beg)) != 0)
 813         error (2, 0, err);
 814       if (lim < pattern + size)
 815         ++lim;
 816       beg = lim;
 817     }
 818   while (beg < pattern + size);
 819
 820   if ((err = kwsprep (kwset)) != 0)
 821     error (2, 0, err);
 822 }
 823
 824 #ifdef MBS_SUPPORT
 825 static int
 826 Fimbexec (const char *buf, size_t size, size_t *plen, int exact)
 827 {
 828   size_t len, letter, i;
 829   int ret = -1;
 830   mbstate_t mbs;
 831   wchar_t wc;
 832   int patterns_left;
 833
 834   assert (match_icase && f_i_multibyte == 1);
 835   assert (MB_CUR_MAX > 1);
 836
 837   memset (&mbs, '\0', sizeof (mbs));
 838   memset (Fimb.match, '\1', Fimb.count);
 839   letter = len = 0;
 840   patterns_left = 1;
 841   while (patterns_left && len <= size)
 842     {
 843       size_t c;
 844
 845       patterns_left = 0;
 846       if (len < size)
 847         {
 848           c = mbrtowc (&wc, buf + len, size - len, &mbs);
 849           if (c + 2 <= 2)
 850             return ret;
 851
 852           wc = towlower (wc);
 853         }
 854       else
 855         {
 856           c = 1;
 857           wc = L'\0';
 858         }
 859
 860       for (i = 0; i < Fimb.count; i++)
 861         {
 862           if (Fimb.match[i])
 863             {
 864               if (Fimb.patterns[i][letter] == L'\0')
 865                 {
 866                   /* Found a match. */
 867                   *plen = len;
 868                   if (!exact && !match_words)
 869                     return 0;
 870                   else
 871                     {
 872                       /* For -w or exact look for longest match.  */
 873                       ret = 0;
 874                       Fimb.match[i] = '\0';
 875                       continue;
 876                     }
 877                 }
 878
 879               if (Fimb.patterns[i][letter] == wc)
 880                 patterns_left = 1;
 881               else
 882                 Fimb.match[i] = '\0';
 883             }
 884         }
 885
 886       len += c;
 887       letter++;
 888     }
 889
 890   return ret;
 891 }
 892 #endif /* MBS_SUPPORT */
 893
 894 static size_t
 895 Fexecute (char const *buf, size_t size, size_t *match_size, int exact)
 896 {
 897   register char const *beg, *try, *end;
 898   register size_t len;
 899   char eol = eolbyte;
 900   struct kwsmatch kwsmatch;
 901   size_t ret_val;
 902 #ifdef MBS_SUPPORT
 903   int mb_cur_max = MB_CUR_MAX;
 904   mbstate_t mbs;
 905   memset (&mbs, '\0', sizeof (mbstate_t));
 906   const char *last_char = NULL;
 907 #endif /* MBS_SUPPORT */
 908
 909   for (beg = buf; beg <= buf + size; ++beg)
 910     {
 911       size_t offset;
 912       offset = kwsexec (kwset, beg, buf + size - beg, &kwsmatch);
 913
 914       if (offset == (size_t) -1)
 915         goto failure;
 916 #ifdef MBS_SUPPORT
 917       if (mb_cur_max > 1 && !using_utf8)
 918         {
 919           size_t bytes_left = offset;
 920           while (bytes_left)
 921             {
 922               size_t mlen = mbrlen (beg, bytes_left, &mbs);
 923
 924               last_char = beg;
 925               if (mlen == (size_t) -1 || mlen == 0)
 926                 {
 927                   /* Incomplete character: treat as single-byte. */
 928                   memset (&mbs, '\0', sizeof (mbstate_t));
 929                   beg++;
 930                   bytes_left--;
 931                   continue;
 932                 }
 933
 934               if (mlen == (size_t) -2)
 935                 {
 936                   /* Offset points inside multibyte character: no good. */
 937                   memset (&mbs, '\0', sizeof (mbstate_t));
 938                   break;
 939                 }
 940
 941               beg += mlen;
 942               bytes_left -= mlen;
 943             }
 944
 945           if (bytes_left)
 946             {
 947               beg += bytes_left;
 948               continue;
 949             }
 950         }
 951       else
 952 #endif /* MBS_SUPPORT */
 953       beg += offset;
 954 #ifdef MBS_SUPPORT
 955       /* For f_i_multibyte, the string at beg now matches first 3 chars of
 956          one of the search strings (less if there are shorter search strings).
 957          See if this is a real match.  */
 958       if (f_i_multibyte
 959           && Fimbexec (beg, buf + size - beg, &kwsmatch.size[0], exact))
 960         goto next_char;
 961 #endif /* MBS_SUPPORT */
 962       len = kwsmatch.size[0];
 963       if (exact && !match_words)
 964         goto success_in_beg_and_len;
 965       if (match_lines)
 966         {
 967           if (beg > buf && beg[-1] != eol)
 968             goto next_char;
 969           if (beg + len < buf + size && beg[len] != eol)
 970             goto next_char;
 971           goto success;
 972         }
 973       else if (match_words)
 974         {
 975           while (1)
 976             {
 977               int word_match = 0;
 978               if (beg > buf)
 979                 {
 980 #ifdef MBS_SUPPORT
 981                   if (mb_cur_max > 1)
 982                     {
 983                       const char *s;
 984                       int mr;
 985                       wchar_t pwc;
 986
 987                       if (using_utf8)
 988                         {
 989                           s = beg - 1;
 990                           while (s > buf
 991                                  && (unsigned char) *s >= 0x80
 992                                  && (unsigned char) *s <= 0xbf)
 993                             --s;
 994                         }
 995                       else
 996                         s = last_char;
 997                       mr = mbtowc (&pwc, s, beg - s);
 998                       if (mr <= 0)
 999                         memset (&mbs, '\0', sizeof (mbstate_t));
1000                       else if ((iswalnum (pwc) || pwc == L'_')
1001                                && mr == (int) (beg - s))
1002                         goto next_char;
1003                     }
1004                   else
1005 #endif /* MBS_SUPPORT */
1006                   if (WCHAR ((unsigned char) beg[-1]))
1007                     goto next_char;
1008                 }
1009 #ifdef MBS_SUPPORT
1010               if (mb_cur_max > 1)
1011                 {
1012                   wchar_t nwc;
1013                   int mr;
1014
1015                   mr = mbtowc (&nwc, beg + len, buf + size - beg - len);
1016                   if (mr <= 0)
1017                     {
1018                       memset (&mbs, '\0', sizeof (mbstate_t));
1019                       word_match = 1;
1020                     }
1021                   else if (!iswalnum (nwc) && nwc != L'_')
1022                     word_match = 1;
1023                 }
1024               else
1025 #endif /* MBS_SUPPORT */
1026                 if (beg + len >= buf + size || !WCHAR ((unsigned char) beg[len]))
1027                   word_match = 1;
1028               if (word_match)
1029                 {
1030                   if (!exact)
1031                     /* Returns the whole line now we know there's a word match. */
1032                     goto success;
1033                   else
1034                     /* Returns just this word match. */
1035                     goto success_in_beg_and_len;
1036                 }
1037               if (len > 0)
1038                 {
1039                   /* Try a shorter length anchored at the same place. */
1040                   --len;
1041                   offset = kwsexec (kwset, beg, len, &kwsmatch);
1042
1043                   if (offset == -1)
1044                     goto next_char; /* Try a different anchor. */
1045 #ifdef MBS_SUPPORT
1046                   if (mb_cur_max > 1 && !using_utf8)
1047                     {
1048                       size_t bytes_left = offset;
1049                       while (bytes_left)
1050                         {
1051                           size_t mlen = mbrlen (beg, bytes_left, &mbs);
1052
1053                           last_char = beg;
1054                           if (mlen == (size_t) -1 || mlen == 0)
1055                             {
1056                               /* Incomplete character: treat as single-byte. */
1057                               memset (&mbs, '\0', sizeof (mbstate_t));
1058                               beg++;
1059                               bytes_left--;
1060                               continue;
1061                             }
1062
1063                           if (mlen == (size_t) -2)
1064                             {
1065                               /* Offset points inside multibyte character:
1066                                * no good. */
1067                               memset (&mbs, '\0', sizeof (mbstate_t));
1068                               break;
1069                             }
1070
1071                           beg += mlen;
1072                           bytes_left -= mlen;
1073                         }
1074
1075                       if (bytes_left)
1076                         {
1077                           memset (&mbs, '\0', sizeof (mbstate_t));
1078                           goto next_char; /* Try a different anchor. */
1079                         }
1080                     }
1081                   else
1082 #endif /* MBS_SUPPORT */
1083                   beg += offset;
1084 #ifdef MBS_SUPPORT
1085                   /* The string at beg now matches first 3 chars of one of
1086                      the search strings (less if there are shorter search
1087                      strings).  See if this is a real match.  */
1088                   if (f_i_multibyte
1089                       && Fimbexec (beg, len - offset, &kwsmatch.size[0],
1090                                    exact))
1091                     goto next_char;
1092 #endif /* MBS_SUPPORT */
1093                   len = kwsmatch.size[0];
1094                 }
1095             }
1096         }
1097       else
1098         goto success;
1099 next_char:;
1100 #ifdef MBS_SUPPORT
1101       /* Advance to next character.  For MB_CUR_MAX == 1 case this is handled
1102          by ++beg above.  */
1103       if (mb_cur_max > 1)
1104         {
1105           if (using_utf8)
1106             {
1107               unsigned char c = *beg;
1108               if (c >= 0xc2)
1109                 {
1110                   if (c < 0xe0)
1111                     ++beg;
1112                   else if (c < 0xf0)
1113                     beg += 2;
1114                   else if (c < 0xf8)
1115                     beg += 3;
1116                   else if (c < 0xfc)
1117                     beg += 4;
1118                   else if (c < 0xfe)
1119                     beg += 5;
1120                 }
1121             }
1122           else
1123             {
1124               size_t l = mbrlen (beg, buf + size - beg, &mbs);
1125
1126               last_char = beg;
1127               if (l + 2 >= 2)
1128                 beg += l - 1;
1129               else
1130                 memset (&mbs, '\0', sizeof (mbstate_t));
1131             }
1132         }
1133 #endif /* MBS_SUPPORT */
1134     }
1135
1136  failure:
1137   return -1;
1138
1139  success:
1140 #ifdef MBS_SUPPORT
1141   if (mb_cur_max > 1 && !using_utf8)
1142     {
1143       end = beg + len;
1144       while (end < buf + size)
1145         {
1146           size_t mlen = mbrlen (end, buf + size - end, &mbs);
1147           if (mlen == (size_t) -1 || mlen == (size_t) -2 || mlen == 0)
1148             {
1149               memset (&mbs, '\0', sizeof (mbstate_t));
1150               mlen = 1;
1151             }
1152           if (mlen == 1 && *end == eol)
1153             break;
1154
1155           end += mlen;
1156         }
1157     }
1158   else
1159 #endif /* MBS_SUPPORT */
1160   end = memchr (beg + len, eol, (buf + size) - (beg + len));
1161
1162   end++;
1163   while (buf < beg && beg[-1] != eol)
1164     --beg;
1165   len = end - beg;
1166   /* FALLTHROUGH */
1167
1168  success_in_beg_and_len:
1169   *match_size = len;
1170   return beg - buf;
1171 }
1172
1173 #if HAVE_LIBPCRE
1174 /* Compiled internal form of a Perl regular expression.  */
1175 static pcre *cre;
1176
1177 /* Additional information about the pattern.  */
1178 static pcre_extra *extra;
1179 #endif
1180
1181 static void
1182 Pcompile (char const *pattern, size_t size)
1183 {
1184 #if !HAVE_LIBPCRE
1185   error (2, 0, _("The -P option is not supported"));
1186 #else
1187   int e;
1188   char const *ep;
1189   char *re = xmalloc (4 * size + 7);
1190   int flags = PCRE_MULTILINE | (match_icase ? PCRE_CASELESS : 0);
1191   char const *patlim = pattern + size;
1192   char *n = re;
1193   char const *p;
1194   char const *pnul;
1195
1196   /* FIXME: Remove this restriction.  */
1197   if (eolbyte != '\n')
1198     error (2, 0, _("The -P and -z options cannot be combined"));
1199
1200   *n = '\0';
1201   if (match_lines)
1202     strcpy (n, "^(");
1203   if (match_words)
1204     strcpy (n, "\\b(");
1205   n += strlen (n);
1206
1207   /* The PCRE interface doesn't allow NUL bytes in the pattern, so
1208      replace each NUL byte in the pattern with the four characters
1209      "\000", removing a preceding backslash if there are an odd
1210      number of backslashes before the NUL.
1211
1212      FIXME: This method does not work with some multibyte character
1213      encodings, notably Shift-JIS, where a multibyte character can end
1214      in a backslash byte.  */
1215   for (p = pattern; (pnul = memchr (p, '\0', patlim - p)); p = pnul + 1)
1216     {
1217       memcpy (n, p, pnul - p);
1218       n += pnul - p;
1219       for (p = pnul; pattern < p && p[-1] == '\\'; p--)
1220         continue;
1221       n -= (pnul - p) & 1;
1222       strcpy (n, "\\000");
1223       n += 4;
1224     }
1225
1226   memcpy (n, p, patlim - p);
1227   n += patlim - p;
1228   *n = '\0';
1229   if (match_words)
1230     strcpy (n, ")\\b");
1231   if (match_lines)
1232     strcpy (n, ")$");
1233
1234   cre = pcre_compile (re, flags, &ep, &e, pcre_maketables ());
1235   if (!cre)
1236     error (2, 0, ep);
1237
1238   extra = pcre_study (cre, 0, &ep);
1239   if (ep)
1240     error (2, 0, ep);
1241
1242   free (re);
1243 #endif
1244 }
1245
1246 static size_t
1247 Pexecute (char const *buf, size_t size, size_t *match_size, int exact)
1248 {
1249 #if !HAVE_LIBPCRE
1250   abort ();
1251   return -1;
1252 #else
1253   /* This array must have at least two elements; everything after that
1254      is just for performance improvement in pcre_exec.  */
1255   int sub[300];
1256
1257   int e = pcre_exec (cre, extra, buf, size, 0, 0,
1258                      sub, sizeof sub / sizeof *sub);
1259
1260   if (e <= 0)
1261     {
1262       switch (e)
1263         {
1264         case PCRE_ERROR_NOMATCH:
1265           return -1;
1266
1267         case PCRE_ERROR_NOMEMORY:
1268           error (2, 0, _("Memory exhausted"));
1269
1270         default:
1271           abort ();
1272         }
1273     }
1274   else
1275     {
1276       /* Narrow down to the line we've found.  */
1277       char const *beg = buf + sub[0];
1278       char const *end = buf + sub[1];
1279       char const *buflim = buf + size;
1280       char eol = eolbyte;
1281       if (!exact)
1282         {
1283           end = memchr (end, eol, buflim - end);
1284           end++;
1285           while (buf < beg && beg[-1] != eol)
1286             --beg;
1287         }
1288
1289       *match_size = end - beg;
1290       return beg - buf;
1291     }
1292 #endif
1293 }
1294
1295 struct matcher const matchers[] = {
1296   { "default", Gcompile, EGexecute },
1297   { "grep", Gcompile, EGexecute },
1298   { "egrep", Ecompile, EGexecute },
1299   { "awk", Ecompile, EGexecute },
1300   { "fgrep", Fcompile, Fexecute },
1301   { "perl", Pcompile, Pexecute },
1302   { "", 0, 0 },
1303 };