kwset.c

   1 /*
   2  * This file has been copied from commit e7ac713d^ in the GNU grep git
   3  * repository. A few small changes have been made to adapt the code to
   4  * Git.
   5  */
   6
   7 /* kwset.c - search for any of a set of keywords.
   8    Copyright 1989, 1998, 2000, 2005 Free Software Foundation, Inc.
   9
  10    This program is free software; you can redistribute it and/or modify
  11    it under the terms of the GNU General Public License as published by
  12    the Free Software Foundation; either version 2, or (at your option)
  13    any later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18    GNU General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, see <https://www.gnu.org/licenses/>. */
  22
  23 /* Written August 1989 by Mike Haertel.
  24    The author may be reached (Email) at the address mike@ai.mit.edu,
  25    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  26
  27 /* The algorithm implemented by these routines bears a startling resemblance
  28    to one discovered by Beate Commentz-Walter, although it is not identical.
  29    See "A String Matching Algorithm Fast on the Average," Technical Report,
  30    IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
  31    Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
  32    String Matching:  An Aid to Bibliographic Search," CACM June 1975,
  33    Vol. 18, No. 6, which describes the failure function used below. */
  34
  35 #include "git-compat-util.h"
  36
  37 #include "kwset.h"
  38 #include "compat/obstack.h"
  39
  40 #define NCHAR (UCHAR_MAX + 1)
  41 /* adapter for `xmalloc()`, which takes `size_t`, not `long` */
  42 static void *obstack_chunk_alloc(long size)
  43 {
  44         if (size < 0)
  45                 BUG("Cannot allocate a negative amount: %ld", size);
  46         return xmalloc(size);
  47 }
  48 #define obstack_chunk_free free
  49
  50 #define U(c) ((unsigned char) (c))
  51
  52 /* For case-insensitive kwset */
  53 const unsigned char tolower_trans_tbl[256] = {
  54         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  55         0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
  56         0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
  57         0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
  58          ' ',  '!',  '"',  '#',  '$',  '%',  '&', 0x27,
  59          '(',  ')',  '*',  '+',  ',',  '-',  '.',  '/',
  60          '0',  '1',  '2',  '3',  '4',  '5',  '6',  '7',
  61          '8',  '9',  ':',  ';',  '<',  '=',  '>',  '?',
  62          '@',  'a',  'b',  'c',  'd',  'e',  'f',  'g',
  63          'h',  'i',  'j',  'k',  'l',  'm',  'n',  'o',
  64          'p',  'q',  'r',  's',  't',  'u',  'v',  'w',
  65          'x',  'y',  'z',  '[', 0x5c,  ']',  '^',  '_',
  66          '`',  'a',  'b',  'c',  'd',  'e',  'f',  'g',
  67          'h',  'i',  'j',  'k',  'l',  'm',  'n',  'o',
  68          'p',  'q',  'r',  's',  't',  'u',  'v',  'w',
  69          'x',  'y',  'z',  '{',  '|',  '}',  '~', 0x7f,
  70         0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
  71         0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
  72         0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
  73         0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
  74         0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
  75         0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
  76         0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
  77         0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
  78         0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
  79         0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
  80         0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
  81         0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
  82         0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
  83         0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
  84         0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
  85         0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
  86 };
  87
  88 /* Balanced tree of edges and labels leaving a given trie node. */
  89 struct tree
  90 {
  91   struct tree *llink;           /* Left link; MUST be first field. */
  92   struct tree *rlink;           /* Right link (to larger labels). */
  93   struct trie *trie;            /* Trie node pointed to by this edge. */
  94   unsigned char label;          /* Label on this edge. */
  95   char balance;                 /* Difference in depths of subtrees. */
  96 };
  97
  98 /* Node of a trie representing a set of reversed keywords. */
  99 struct trie
 100 {
 101   unsigned int accepting;       /* Word index of accepted word, or zero. */
 102   struct tree *links;           /* Tree of edges leaving this node. */
 103   struct trie *parent;          /* Parent of this node. */
 104   struct trie *next;            /* List of all trie nodes in level order. */
 105   struct trie *fail;            /* Aho-Corasick failure function. */
 106   int depth;                    /* Depth of this node from the root. */
 107   int shift;                    /* Shift function for search failures. */
 108   int maxshift;                 /* Max shift of self and descendants. */
 109 };
 110
 111 /* Structure returned opaquely to the caller, containing everything. */
 112 struct kwset
 113 {
 114   struct obstack obstack;       /* Obstack for node allocation. */
 115   int words;                    /* Number of words in the trie. */
 116   struct trie *trie;            /* The trie itself. */
 117   int mind;                     /* Minimum depth of an accepting node. */
 118   int maxd;                     /* Maximum depth of any node. */
 119   unsigned char delta[NCHAR];   /* Delta table for rapid search. */
 120   struct trie *next[NCHAR];     /* Table of children of the root. */
 121   char *target;                 /* Target string if there's only one. */
 122   int mind2;                    /* Used in Boyer-Moore search for one string. */
 123   unsigned char const *trans;  /* Character translation table. */
 124 };
 125
 126 /* Allocate and initialize a keyword set object, returning an opaque
 127    pointer to it.  Return NULL if memory is not available. */
 128 kwset_t
 129 kwsalloc (unsigned char const *trans)
 130 {
 131   struct kwset *kwset;
 132
 133   kwset = (struct kwset *) xmalloc(sizeof (struct kwset));
 134
 135   obstack_init(&kwset->obstack);
 136   kwset->words = 0;
 137   kwset->trie
 138     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
 139   if (!kwset->trie)
 140     {
 141       kwsfree((kwset_t) kwset);
 142       return NULL;
 143     }
 144   kwset->trie->accepting = 0;
 145   kwset->trie->links = NULL;
 146   kwset->trie->parent = NULL;
 147   kwset->trie->next = NULL;
 148   kwset->trie->fail = NULL;
 149   kwset->trie->depth = 0;
 150   kwset->trie->shift = 0;
 151   kwset->mind = INT_MAX;
 152   kwset->maxd = -1;
 153   kwset->target = NULL;
 154   kwset->trans = trans;
 155
 156   return (kwset_t) kwset;
 157 }
 158
 159 /* This upper bound is valid for CHAR_BIT >= 4 and
 160    exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */
 161 #define DEPTH_SIZE (CHAR_BIT + CHAR_BIT/2)
 162
 163 /* Add the given string to the contents of the keyword set.  Return NULL
 164    for success, an error message otherwise. */
 165 const char *
 166 kwsincr (kwset_t kws, char const *text, size_t len)
 167 {
 168   struct kwset *kwset;
 169   register struct trie *trie;
 170   register unsigned char label;
 171   register struct tree *link;
 172   register int depth;
 173   struct tree *links[DEPTH_SIZE];
 174   enum { L, R } dirs[DEPTH_SIZE];
 175   struct tree *t, *r, *l, *rl, *lr;
 176
 177   kwset = (struct kwset *) kws;
 178   trie = kwset->trie;
 179   text += len;
 180
 181   /* Descend the trie (built of reversed keywords) character-by-character,
 182      installing new nodes when necessary. */
 183   while (len--)
 184     {
 185       label = kwset->trans ? kwset->trans[U(*--text)] : *--text;
 186
 187       /* Descend the tree of outgoing links for this trie node,
 188          looking for the current character and keeping track
 189          of the path followed. */
 190       link = trie->links;
 191       links[0] = (struct tree *) &trie->links;
 192       dirs[0] = L;
 193       depth = 1;
 194
 195       while (link && label != link->label)
 196         {
 197           links[depth] = link;
 198           if (label < link->label)
 199             dirs[depth++] = L, link = link->llink;
 200           else
 201             dirs[depth++] = R, link = link->rlink;
 202         }
 203
 204       /* The current character doesn't have an outgoing link at
 205          this trie node, so build a new trie node and install
 206          a link in the current trie node's tree. */
 207       if (!link)
 208         {
 209           link = (struct tree *) obstack_alloc(&kwset->obstack,
 210                                                sizeof (struct tree));
 211           if (!link)
 212             return "memory exhausted";
 213           link->llink = NULL;
 214           link->rlink = NULL;
 215           link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
 216                                                      sizeof (struct trie));
 217           if (!link->trie)
 218             {
 219               obstack_free(&kwset->obstack, link);
 220               return "memory exhausted";
 221             }
 222           link->trie->accepting = 0;
 223           link->trie->links = NULL;
 224           link->trie->parent = trie;
 225           link->trie->next = NULL;
 226           link->trie->fail = NULL;
 227           link->trie->depth = trie->depth + 1;
 228           link->trie->shift = 0;
 229           link->label = label;
 230           link->balance = 0;
 231
 232           /* Install the new tree node in its parent. */
 233           if (dirs[--depth] == L)
 234             links[depth]->llink = link;
 235           else
 236             links[depth]->rlink = link;
 237
 238           /* Back up the tree fixing the balance flags. */
 239           while (depth && !links[depth]->balance)
 240             {
 241               if (dirs[depth] == L)
 242                 --links[depth]->balance;
 243               else
 244                 ++links[depth]->balance;
 245               --depth;
 246             }
 247
 248           /* Rebalance the tree by pointer rotations if necessary. */
 249           if (depth && ((dirs[depth] == L && --links[depth]->balance)
 250                         || (dirs[depth] == R && ++links[depth]->balance)))
 251             {
 252               switch (links[depth]->balance)
 253                 {
 254                 case (char) -2:
 255                   switch (dirs[depth + 1])
 256                     {
 257                     case L:
 258                       r = links[depth], t = r->llink, rl = t->rlink;
 259                       t->rlink = r, r->llink = rl;
 260                       t->balance = r->balance = 0;
 261                       break;
 262                     case R:
 263                       r = links[depth], l = r->llink, t = l->rlink;
 264                       rl = t->rlink, lr = t->llink;
 265                       t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
 266                       l->balance = t->balance != 1 ? 0 : -1;
 267                       r->balance = t->balance != (char) -1 ? 0 : 1;
 268                       t->balance = 0;
 269                       break;
 270                     default:
 271                       abort ();
 272                     }
 273                   break;
 274                 case 2:
 275                   switch (dirs[depth + 1])
 276                     {
 277                     case R:
 278                       l = links[depth], t = l->rlink, lr = t->llink;
 279                       t->llink = l, l->rlink = lr;
 280                       t->balance = l->balance = 0;
 281                       break;
 282                     case L:
 283                       l = links[depth], r = l->rlink, t = r->llink;
 284                       lr = t->llink, rl = t->rlink;
 285                       t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
 286                       l->balance = t->balance != 1 ? 0 : -1;
 287                       r->balance = t->balance != (char) -1 ? 0 : 1;
 288                       t->balance = 0;
 289                       break;
 290                     default:
 291                       abort ();
 292                     }
 293                   break;
 294                 default:
 295                   abort ();
 296                 }
 297
 298               if (dirs[depth - 1] == L)
 299                 links[depth - 1]->llink = t;
 300               else
 301                 links[depth - 1]->rlink = t;
 302             }
 303         }
 304
 305       trie = link->trie;
 306     }
 307
 308   /* Mark the node we finally reached as accepting, encoding the
 309      index number of this word in the keyword set so far. */
 310   if (!trie->accepting)
 311     trie->accepting = 1 + 2 * kwset->words;
 312   ++kwset->words;
 313
 314   /* Keep track of the longest and shortest string of the keyword set. */
 315   if (trie->depth < kwset->mind)
 316     kwset->mind = trie->depth;
 317   if (trie->depth > kwset->maxd)
 318     kwset->maxd = trie->depth;
 319
 320   return NULL;
 321 }
 322
 323 /* Enqueue the trie nodes referenced from the given tree in the
 324    given queue. */
 325 static void
 326 enqueue (struct tree *tree, struct trie **last)
 327 {
 328   if (!tree)
 329     return;
 330   enqueue(tree->llink, last);
 331   enqueue(tree->rlink, last);
 332   (*last) = (*last)->next = tree->trie;
 333 }
 334
 335 /* Compute the Aho-Corasick failure function for the trie nodes referenced
 336    from the given tree, given the failure function for their parent as
 337    well as a last resort failure node. */
 338 static void
 339 treefails (register struct tree const *tree, struct trie const *fail,
 340            struct trie *recourse)
 341 {
 342   register struct tree *link;
 343
 344   if (!tree)
 345     return;
 346
 347   treefails(tree->llink, fail, recourse);
 348   treefails(tree->rlink, fail, recourse);
 349
 350   /* Find, in the chain of fails going back to the root, the first
 351      node that has a descendant on the current label. */
 352   while (fail)
 353     {
 354       link = fail->links;
 355       while (link && tree->label != link->label)
 356         if (tree->label < link->label)
 357           link = link->llink;
 358         else
 359           link = link->rlink;
 360       if (link)
 361         {
 362           tree->trie->fail = link->trie;
 363           return;
 364         }
 365       fail = fail->fail;
 366     }
 367
 368   tree->trie->fail = recourse;
 369 }
 370
 371 /* Set delta entries for the links of the given tree such that
 372    the preexisting delta value is larger than the current depth. */
 373 static void
 374 treedelta (register struct tree const *tree,
 375            register unsigned int depth,
 376            unsigned char delta[])
 377 {
 378   if (!tree)
 379     return;
 380   treedelta(tree->llink, depth, delta);
 381   treedelta(tree->rlink, depth, delta);
 382   if (depth < delta[tree->label])
 383     delta[tree->label] = depth;
 384 }
 385
 386 /* Return true if A has every label in B. */
 387 static int
 388 hasevery (register struct tree const *a, register struct tree const *b)
 389 {
 390   if (!b)
 391     return 1;
 392   if (!hasevery(a, b->llink))
 393     return 0;
 394   if (!hasevery(a, b->rlink))
 395     return 0;
 396   while (a && b->label != a->label)
 397     if (b->label < a->label)
 398       a = a->llink;
 399     else
 400       a = a->rlink;
 401   return !!a;
 402 }
 403
 404 /* Compute a vector, indexed by character code, of the trie nodes
 405    referenced from the given tree. */
 406 static void
 407 treenext (struct tree const *tree, struct trie *next[])
 408 {
 409   if (!tree)
 410     return;
 411   treenext(tree->llink, next);
 412   treenext(tree->rlink, next);
 413   next[tree->label] = tree->trie;
 414 }
 415
 416 /* Compute the shift for each trie node, as well as the delta
 417    table and next cache for the given keyword set. */
 418 const char *
 419 kwsprep (kwset_t kws)
 420 {
 421   register struct kwset *kwset;
 422   register int i;
 423   register struct trie *curr;
 424   register unsigned char const *trans;
 425   unsigned char delta[NCHAR];
 426
 427   kwset = (struct kwset *) kws;
 428
 429   /* Initial values for the delta table; will be changed later.  The
 430      delta entry for a given character is the smallest depth of any
 431      node at which an outgoing edge is labeled by that character. */
 432   memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);
 433
 434   /* Check if we can use the simple boyer-moore algorithm, instead
 435      of the hairy commentz-walter algorithm. */
 436   if (kwset->words == 1 && kwset->trans == NULL)
 437     {
 438       char c;
 439
 440       /* Looking for just one string.  Extract it from the trie. */
 441       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
 442       if (!kwset->target)
 443         return "memory exhausted";
 444       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
 445         {
 446           kwset->target[i] = curr->links->label;
 447           curr = curr->links->trie;
 448         }
 449       /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
 450       for (i = 0; i < kwset->mind; ++i)
 451         delta[U(kwset->target[i])] = kwset->mind - (i + 1);
 452       /* Find the minimal delta2 shift that we might make after
 453          a backwards match has failed. */
 454       c = kwset->target[kwset->mind - 1];
 455       for (i = kwset->mind - 2; i >= 0; --i)
 456         if (kwset->target[i] == c)
 457           break;
 458       kwset->mind2 = kwset->mind - (i + 1);
 459     }
 460   else
 461     {
 462       register struct trie *fail;
 463       struct trie *last, *next[NCHAR];
 464
 465       /* Traverse the nodes of the trie in level order, simultaneously
 466          computing the delta table, failure function, and shift function. */
 467       for (curr = last = kwset->trie; curr; curr = curr->next)
 468         {
 469           /* Enqueue the immediate descendants in the level order queue. */
 470           enqueue(curr->links, &last);
 471
 472           curr->shift = kwset->mind;
 473           curr->maxshift = kwset->mind;
 474
 475           /* Update the delta table for the descendants of this node. */
 476           treedelta(curr->links, curr->depth, delta);
 477
 478           /* Compute the failure function for the descendants of this node. */
 479           treefails(curr->links, curr->fail, kwset->trie);
 480
 481           /* Update the shifts at each node in the current node's chain
 482              of fails back to the root. */
 483           for (fail = curr->fail; fail; fail = fail->fail)
 484             {
 485               /* If the current node has some outgoing edge that the fail
 486                  doesn't, then the shift at the fail should be no larger
 487                  than the difference of their depths. */
 488               if (!hasevery(fail->links, curr->links))
 489                 if (curr->depth - fail->depth < fail->shift)
 490                   fail->shift = curr->depth - fail->depth;
 491
 492               /* If the current node is accepting then the shift at the
 493                  fail and its descendants should be no larger than the
 494                  difference of their depths. */
 495               if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
 496                 fail->maxshift = curr->depth - fail->depth;
 497             }
 498         }
 499
 500       /* Traverse the trie in level order again, fixing up all nodes whose
 501          shift exceeds their inherited maxshift. */
 502       for (curr = kwset->trie->next; curr; curr = curr->next)
 503         {
 504           if (curr->maxshift > curr->parent->maxshift)
 505             curr->maxshift = curr->parent->maxshift;
 506           if (curr->shift > curr->maxshift)
 507             curr->shift = curr->maxshift;
 508         }
 509
 510       /* Create a vector, indexed by character code, of the outgoing links
 511          from the root node. */
 512       for (i = 0; i < NCHAR; ++i)
 513         next[i] = NULL;
 514       treenext(kwset->trie->links, next);
 515
 516       if ((trans = kwset->trans))
 517         for (i = 0; i < NCHAR; ++i)
 518           kwset->next[i] = next[U(trans[i])];
 519       else
 520         COPY_ARRAY(kwset->next, next, NCHAR);
 521     }
 522
 523   /* Fix things up for any translation table. */
 524   if ((trans = kwset->trans))
 525     for (i = 0; i < NCHAR; ++i)
 526       kwset->delta[i] = delta[U(trans[i])];
 527   else
 528     memcpy(kwset->delta, delta, NCHAR);
 529
 530   return NULL;
 531 }
 532
 533 /* Fast boyer-moore search. */
 534 static size_t
 535 bmexec (kwset_t kws, char const *text, size_t size)
 536 {
 537   struct kwset const *kwset;
 538   register unsigned char const *d1;
 539   register char const *ep, *sp, *tp;
 540   register int d, gc, i, len, md2;
 541
 542   kwset = (struct kwset const *) kws;
 543   len = kwset->mind;
 544
 545   if (len == 0)
 546     return 0;
 547   if (len > size)
 548     return -1;
 549   if (len == 1)
 550     {
 551       tp = memchr (text, kwset->target[0], size);
 552       return tp ? tp - text : -1;
 553     }
 554
 555   d1 = kwset->delta;
 556   sp = kwset->target + len;
 557   gc = U(sp[-2]);
 558   md2 = kwset->mind2;
 559   tp = text + len;
 560
 561   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
 562   if (size > 12 * len)
 563     /* 11 is not a bug, the initial offset happens only once. */
 564     for (ep = text + size - 11 * len;;)
 565       {
 566         while (tp <= ep)
 567           {
 568             d = d1[U(tp[-1])], tp += d;
 569             d = d1[U(tp[-1])], tp += d;
 570             if (d == 0)
 571               goto found;
 572             d = d1[U(tp[-1])], tp += d;
 573             d = d1[U(tp[-1])], tp += d;
 574             d = d1[U(tp[-1])], tp += d;
 575             if (d == 0)
 576               goto found;
 577             d = d1[U(tp[-1])], tp += d;
 578             d = d1[U(tp[-1])], tp += d;
 579             d = d1[U(tp[-1])], tp += d;
 580             if (d == 0)
 581               goto found;
 582             d = d1[U(tp[-1])], tp += d;
 583             d = d1[U(tp[-1])], tp += d;
 584           }
 585         break;
 586       found:
 587         if (U(tp[-2]) == gc)
 588           {
 589             for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
 590               ;
 591             if (i > len)
 592               return tp - len - text;
 593           }
 594         tp += md2;
 595       }
 596
 597   /* Now we have only a few characters left to search.  We
 598      carefully avoid ever producing an out-of-bounds pointer. */
 599   ep = text + size;
 600   d = d1[U(tp[-1])];
 601   while (d <= ep - tp)
 602     {
 603       d = d1[U((tp += d)[-1])];
 604       if (d != 0)
 605         continue;
 606       if (U(tp[-2]) == gc)
 607         {
 608           for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
 609             ;
 610           if (i > len)
 611             return tp - len - text;
 612         }
 613       d = md2;
 614     }
 615
 616   return -1;
 617 }
 618
 619 /* Hairy multiple string search. */
 620 static size_t
 621 cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
 622 {
 623   struct kwset const *kwset;
 624   struct trie * const *next;
 625   struct trie const *trie;
 626   struct trie const *accept;
 627   char const *beg, *lim, *mch, *lmch;
 628   register unsigned char c;
 629   register unsigned char const *delta;
 630   register int d;
 631   register char const *end, *qlim;
 632   register struct tree const *tree;
 633   register unsigned char const *trans;
 634
 635   accept = NULL;
 636
 637   /* Initialize register copies and look for easy ways out. */
 638   kwset = (struct kwset *) kws;
 639   if (len < kwset->mind)
 640     return -1;
 641   next = kwset->next;
 642   delta = kwset->delta;
 643   trans = kwset->trans;
 644   lim = text + len;
 645   end = text;
 646   if ((d = kwset->mind) != 0)
 647     mch = NULL;
 648   else
 649     {
 650       mch = text, accept = kwset->trie;
 651       goto match;
 652     }
 653
 654   if (len >= 4 * kwset->mind)
 655     qlim = lim - 4 * kwset->mind;
 656   else
 657     qlim = NULL;
 658
 659   while (lim - end >= d)
 660     {
 661       if (qlim && end <= qlim)
 662         {
 663           end += d - 1;
 664           while ((d = delta[c = *end]) && end < qlim)
 665             {
 666               end += d;
 667               end += delta[U(*end)];
 668               end += delta[U(*end)];
 669             }
 670           ++end;
 671         }
 672       else
 673         d = delta[c = (end += d)[-1]];
 674       if (d)
 675         continue;
 676       beg = end - 1;
 677       trie = next[c];
 678       if (trie->accepting)
 679         {
 680           mch = beg;
 681           accept = trie;
 682         }
 683       d = trie->shift;
 684       while (beg > text)
 685         {
 686           c = trans ? trans[U(*--beg)] : *--beg;
 687           tree = trie->links;
 688           while (tree && c != tree->label)
 689             if (c < tree->label)
 690               tree = tree->llink;
 691             else
 692               tree = tree->rlink;
 693           if (tree)
 694             {
 695               trie = tree->trie;
 696               if (trie->accepting)
 697                 {
 698                   mch = beg;
 699                   accept = trie;
 700                 }
 701             }
 702           else
 703             break;
 704           d = trie->shift;
 705         }
 706       if (mch)
 707         goto match;
 708     }
 709   return -1;
 710
 711  match:
 712   /* Given a known match, find the longest possible match anchored
 713      at or before its starting point.  This is nearly a verbatim
 714      copy of the preceding main search loops. */
 715   if (lim - mch > kwset->maxd)
 716     lim = mch + kwset->maxd;
 717   lmch = NULL;
 718   d = 1;
 719   while (lim - end >= d)
 720     {
 721       if ((d = delta[c = (end += d)[-1]]) != 0)
 722         continue;
 723       beg = end - 1;
 724       if (!(trie = next[c]))
 725         {
 726           d = 1;
 727           continue;
 728         }
 729       if (trie->accepting && beg <= mch)
 730         {
 731           lmch = beg;
 732           accept = trie;
 733         }
 734       d = trie->shift;
 735       while (beg > text)
 736         {
 737           c = trans ? trans[U(*--beg)] : *--beg;
 738           tree = trie->links;
 739           while (tree && c != tree->label)
 740             if (c < tree->label)
 741               tree = tree->llink;
 742             else
 743               tree = tree->rlink;
 744           if (tree)
 745             {
 746               trie = tree->trie;
 747               if (trie->accepting && beg <= mch)
 748                 {
 749                   lmch = beg;
 750                   accept = trie;
 751                 }
 752             }
 753           else
 754             break;
 755           d = trie->shift;
 756         }
 757       if (lmch)
 758         {
 759           mch = lmch;
 760           goto match;
 761         }
 762       if (!d)
 763         d = 1;
 764     }
 765
 766   if (kwsmatch)
 767     {
 768       kwsmatch->index = accept->accepting / 2;
 769       kwsmatch->offset[0] = mch - text;
 770       kwsmatch->size[0] = accept->depth;
 771     }
 772   return mch - text;
 773 }
 774
 775 /* Search through the given text for a match of any member of the
 776    given keyword set.  Return a pointer to the first character of
 777    the matching substring, or NULL if no match is found.  If FOUNDLEN
 778    is non-NULL store in the referenced location the length of the
 779    matching substring.  Similarly, if FOUNDIDX is non-NULL, store
 780    in the referenced location the index number of the particular
 781    keyword matched. */
 782 size_t
 783 kwsexec (kwset_t kws, char const *text, size_t size,
 784          struct kwsmatch *kwsmatch)
 785 {
 786   struct kwset const *kwset = (struct kwset *) kws;
 787   if (kwset->words == 1 && kwset->trans == NULL)
 788     {
 789       size_t ret = bmexec (kws, text, size);
 790       if (kwsmatch != NULL && ret != (size_t) -1)
 791         {
 792           kwsmatch->index = 0;
 793           kwsmatch->offset[0] = ret;
 794           kwsmatch->size[0] = kwset->mind;
 795         }
 796       return ret;
 797     }
 798   else
 799     return cwexec(kws, text, size, kwsmatch);
 800 }
 801
 802 /* Free the components of the given keyword set. */
 803 void
 804 kwsfree (kwset_t kws)
 805 {
 806   struct kwset *kwset;
 807
 808   kwset = (struct kwset *) kws;
 809   obstack_free(&kwset->obstack, NULL);
 810   free(kws);
 811 }