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, write to the Free Software 22 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 23 02110-1301, USA. */ 24 25/* Written August 1989 by Mike Haertel. 26 The author may be reached (Email) at the address mike@ai.mit.edu, 27 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 28 29/* The algorithm implemented by these routines bears a startling resemblance 30 to one discovered by Beate Commentz-Walter, although it is not identical. 31 See "A String Matching Algorithm Fast on the Average," Technical Report, 32 IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900 33 Heidelberg, Germany. See also Aho, A.V., and M. Corasick, "Efficient 34 String Matching: An Aid to Bibliographic Search," CACM June 1975, 35 Vol. 18, No. 6, which describes the failure function used below. */ 36 37#include "cache.h" 38 39#include "kwset.h" 40#include "compat/obstack.h" 41 42#define NCHAR (UCHAR_MAX + 1) 43#define obstack_chunk_alloc xmalloc 44#define obstack_chunk_free free 45 46#define U(c) ((unsigned char) (c)) 47 48/* Balanced tree of edges and labels leaving a given trie node. */ 49struct tree 50{ 51 struct tree *llink; /* Left link; MUST be first field. */ 52 struct tree *rlink; /* Right link (to larger labels). */ 53 struct trie *trie; /* Trie node pointed to by this edge. */ 54 unsigned char label; /* Label on this edge. */ 55 char balance; /* Difference in depths of subtrees. */ 56}; 57 58/* Node of a trie representing a set of reversed keywords. */ 59struct trie 60{ 61 unsigned int accepting; /* Word index of accepted word, or zero. */ 62 struct tree *links; /* Tree of edges leaving this node. */ 63 struct trie *parent; /* Parent of this node. */ 64 struct trie *next; /* List of all trie nodes in level order. */ 65 struct trie *fail; /* Aho-Corasick failure function. */ 66 int depth; /* Depth of this node from the root. */ 67 int shift; /* Shift function for search failures. */ 68 int maxshift; /* Max shift of self and descendants. */ 69}; 70 71/* Structure returned opaquely to the caller, containing everything. */ 72struct kwset 73{ 74 struct obstack obstack; /* Obstack for node allocation. */ 75 int words; /* Number of words in the trie. */ 76 struct trie *trie; /* The trie itself. */ 77 int mind; /* Minimum depth of an accepting node. */ 78 int maxd; /* Maximum depth of any node. */ 79 unsigned char delta[NCHAR]; /* Delta table for rapid search. */ 80 struct trie *next[NCHAR]; /* Table of children of the root. */ 81 char *target; /* Target string if there's only one. */ 82 int mind2; /* Used in Boyer-Moore search for one string. */ 83 unsigned char const *trans; /* Character translation table. */ 84}; 85 86/* Allocate and initialize a keyword set object, returning an opaque 87 pointer to it. Return NULL if memory is not available. */ 88kwset_t 89kwsalloc (unsigned char const *trans) 90{ 91 struct kwset *kwset; 92 93 kwset = (struct kwset *) xmalloc(sizeof (struct kwset)); 94 95 obstack_init(&kwset->obstack); 96 kwset->words = 0; 97 kwset->trie 98 = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie)); 99 if (!kwset->trie) 100 { 101 kwsfree((kwset_t) kwset); 102 return NULL; 103 } 104 kwset->trie->accepting = 0; 105 kwset->trie->links = NULL; 106 kwset->trie->parent = NULL; 107 kwset->trie->next = NULL; 108 kwset->trie->fail = NULL; 109 kwset->trie->depth = 0; 110 kwset->trie->shift = 0; 111 kwset->mind = INT_MAX; 112 kwset->maxd = -1; 113 kwset->target = NULL; 114 kwset->trans = trans; 115 116 return (kwset_t) kwset; 117} 118 119/* This upper bound is valid for CHAR_BIT >= 4 and 120 exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */ 121#define DEPTH_SIZE (CHAR_BIT + CHAR_BIT/2) 122 123/* Add the given string to the contents of the keyword set. Return NULL 124 for success, an error message otherwise. */ 125const char * 126kwsincr (kwset_t kws, char const *text, size_t len) 127{ 128 struct kwset *kwset; 129 register struct trie *trie; 130 register unsigned char label; 131 register struct tree *link; 132 register int depth; 133 struct tree *links[DEPTH_SIZE]; 134 enum { L, R } dirs[DEPTH_SIZE]; 135 struct tree *t, *r, *l, *rl, *lr; 136 137 kwset = (struct kwset *) kws; 138 trie = kwset->trie; 139 text += len; 140 141 /* Descend the trie (built of reversed keywords) character-by-character, 142 installing new nodes when necessary. */ 143 while (len--) 144 { 145 label = kwset->trans ? kwset->trans[U(*--text)] : *--text; 146 147 /* Descend the tree of outgoing links for this trie node, 148 looking for the current character and keeping track 149 of the path followed. */ 150 link = trie->links; 151 links[0] = (struct tree *) &trie->links; 152 dirs[0] = L; 153 depth = 1; 154 155 while (link && label != link->label) 156 { 157 links[depth] = link; 158 if (label < link->label) 159 dirs[depth++] = L, link = link->llink; 160 else 161 dirs[depth++] = R, link = link->rlink; 162 } 163 164 /* The current character doesn't have an outgoing link at 165 this trie node, so build a new trie node and install 166 a link in the current trie node's tree. */ 167 if (!link) 168 { 169 link = (struct tree *) obstack_alloc(&kwset->obstack, 170 sizeof (struct tree)); 171 if (!link) 172 return "memory exhausted"; 173 link->llink = NULL; 174 link->rlink = NULL; 175 link->trie = (struct trie *) obstack_alloc(&kwset->obstack, 176 sizeof (struct trie)); 177 if (!link->trie) 178 { 179 obstack_free(&kwset->obstack, link); 180 return "memory exhausted"; 181 } 182 link->trie->accepting = 0; 183 link->trie->links = NULL; 184 link->trie->parent = trie; 185 link->trie->next = NULL; 186 link->trie->fail = NULL; 187 link->trie->depth = trie->depth + 1; 188 link->trie->shift = 0; 189 link->label = label; 190 link->balance = 0; 191 192 /* Install the new tree node in its parent. */ 193 if (dirs[--depth] == L) 194 links[depth]->llink = link; 195 else 196 links[depth]->rlink = link; 197 198 /* Back up the tree fixing the balance flags. */ 199 while (depth && !links[depth]->balance) 200 { 201 if (dirs[depth] == L) 202 --links[depth]->balance; 203 else 204 ++links[depth]->balance; 205 --depth; 206 } 207 208 /* Rebalance the tree by pointer rotations if necessary. */ 209 if (depth && ((dirs[depth] == L && --links[depth]->balance) 210 || (dirs[depth] == R && ++links[depth]->balance))) 211 { 212 switch (links[depth]->balance) 213 { 214 case (char) -2: 215 switch (dirs[depth + 1]) 216 { 217 case L: 218 r = links[depth], t = r->llink, rl = t->rlink; 219 t->rlink = r, r->llink = rl; 220 t->balance = r->balance = 0; 221 break; 222 case R: 223 r = links[depth], l = r->llink, t = l->rlink; 224 rl = t->rlink, lr = t->llink; 225 t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl; 226 l->balance = t->balance != 1 ? 0 : -1; 227 r->balance = t->balance != (char) -1 ? 0 : 1; 228 t->balance = 0; 229 break; 230 default: 231 abort (); 232 } 233 break; 234 case 2: 235 switch (dirs[depth + 1]) 236 { 237 case R: 238 l = links[depth], t = l->rlink, lr = t->llink; 239 t->llink = l, l->rlink = lr; 240 t->balance = l->balance = 0; 241 break; 242 case L: 243 l = links[depth], r = l->rlink, t = r->llink; 244 lr = t->llink, rl = t->rlink; 245 t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl; 246 l->balance = t->balance != 1 ? 0 : -1; 247 r->balance = t->balance != (char) -1 ? 0 : 1; 248 t->balance = 0; 249 break; 250 default: 251 abort (); 252 } 253 break; 254 default: 255 abort (); 256 } 257 258 if (dirs[depth - 1] == L) 259 links[depth - 1]->llink = t; 260 else 261 links[depth - 1]->rlink = t; 262 } 263 } 264 265 trie = link->trie; 266 } 267 268 /* Mark the node we finally reached as accepting, encoding the 269 index number of this word in the keyword set so far. */ 270 if (!trie->accepting) 271 trie->accepting = 1 + 2 * kwset->words; 272 ++kwset->words; 273 274 /* Keep track of the longest and shortest string of the keyword set. */ 275 if (trie->depth < kwset->mind) 276 kwset->mind = trie->depth; 277 if (trie->depth > kwset->maxd) 278 kwset->maxd = trie->depth; 279 280 return NULL; 281} 282 283/* Enqueue the trie nodes referenced from the given tree in the 284 given queue. */ 285static void 286enqueue (struct tree *tree, struct trie **last) 287{ 288 if (!tree) 289 return; 290 enqueue(tree->llink, last); 291 enqueue(tree->rlink, last); 292 (*last) = (*last)->next = tree->trie; 293} 294 295/* Compute the Aho-Corasick failure function for the trie nodes referenced 296 from the given tree, given the failure function for their parent as 297 well as a last resort failure node. */ 298static void 299treefails (register struct tree const *tree, struct trie const *fail, 300 struct trie *recourse) 301{ 302 register struct tree *link; 303 304 if (!tree) 305 return; 306 307 treefails(tree->llink, fail, recourse); 308 treefails(tree->rlink, fail, recourse); 309 310 /* Find, in the chain of fails going back to the root, the first 311 node that has a descendant on the current label. */ 312 while (fail) 313 { 314 link = fail->links; 315 while (link && tree->label != link->label) 316 if (tree->label < link->label) 317 link = link->llink; 318 else 319 link = link->rlink; 320 if (link) 321 { 322 tree->trie->fail = link->trie; 323 return; 324 } 325 fail = fail->fail; 326 } 327 328 tree->trie->fail = recourse; 329} 330 331/* Set delta entries for the links of the given tree such that 332 the preexisting delta value is larger than the current depth. */ 333static void 334treedelta (register struct tree const *tree, 335 register unsigned int depth, 336 unsigned char delta[]) 337{ 338 if (!tree) 339 return; 340 treedelta(tree->llink, depth, delta); 341 treedelta(tree->rlink, depth, delta); 342 if (depth < delta[tree->label]) 343 delta[tree->label] = depth; 344} 345 346/* Return true if A has every label in B. */ 347static int 348hasevery (register struct tree const *a, register struct tree const *b) 349{ 350 if (!b) 351 return 1; 352 if (!hasevery(a, b->llink)) 353 return 0; 354 if (!hasevery(a, b->rlink)) 355 return 0; 356 while (a && b->label != a->label) 357 if (b->label < a->label) 358 a = a->llink; 359 else 360 a = a->rlink; 361 return !!a; 362} 363 364/* Compute a vector, indexed by character code, of the trie nodes 365 referenced from the given tree. */ 366static void 367treenext (struct tree const *tree, struct trie *next[]) 368{ 369 if (!tree) 370 return; 371 treenext(tree->llink, next); 372 treenext(tree->rlink, next); 373 next[tree->label] = tree->trie; 374} 375 376/* Compute the shift for each trie node, as well as the delta 377 table and next cache for the given keyword set. */ 378const char * 379kwsprep (kwset_t kws) 380{ 381 register struct kwset *kwset; 382 register int i; 383 register struct trie *curr; 384 register unsigned char const *trans; 385 unsigned char delta[NCHAR]; 386 387 kwset = (struct kwset *) kws; 388 389 /* Initial values for the delta table; will be changed later. The 390 delta entry for a given character is the smallest depth of any 391 node at which an outgoing edge is labeled by that character. */ 392 memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR); 393 394 /* Check if we can use the simple boyer-moore algorithm, instead 395 of the hairy commentz-walter algorithm. */ 396 if (kwset->words == 1 && kwset->trans == NULL) 397 { 398 char c; 399 400 /* Looking for just one string. Extract it from the trie. */ 401 kwset->target = obstack_alloc(&kwset->obstack, kwset->mind); 402 if (!kwset->target) 403 return "memory exhausted"; 404 for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i) 405 { 406 kwset->target[i] = curr->links->label; 407 curr = curr->links->trie; 408 } 409 /* Build the Boyer Moore delta. Boy that's easy compared to CW. */ 410 for (i = 0; i < kwset->mind; ++i) 411 delta[U(kwset->target[i])] = kwset->mind - (i + 1); 412 /* Find the minimal delta2 shift that we might make after 413 a backwards match has failed. */ 414 c = kwset->target[kwset->mind - 1]; 415 for (i = kwset->mind - 2; i >= 0; --i) 416 if (kwset->target[i] == c) 417 break; 418 kwset->mind2 = kwset->mind - (i + 1); 419 } 420 else 421 { 422 register struct trie *fail; 423 struct trie *last, *next[NCHAR]; 424 425 /* Traverse the nodes of the trie in level order, simultaneously 426 computing the delta table, failure function, and shift function. */ 427 for (curr = last = kwset->trie; curr; curr = curr->next) 428 { 429 /* Enqueue the immediate descendants in the level order queue. */ 430 enqueue(curr->links, &last); 431 432 curr->shift = kwset->mind; 433 curr->maxshift = kwset->mind; 434 435 /* Update the delta table for the descendants of this node. */ 436 treedelta(curr->links, curr->depth, delta); 437 438 /* Compute the failure function for the descendants of this node. */ 439 treefails(curr->links, curr->fail, kwset->trie); 440 441 /* Update the shifts at each node in the current node's chain 442 of fails back to the root. */ 443 for (fail = curr->fail; fail; fail = fail->fail) 444 { 445 /* If the current node has some outgoing edge that the fail 446 doesn't, then the shift at the fail should be no larger 447 than the difference of their depths. */ 448 if (!hasevery(fail->links, curr->links)) 449 if (curr->depth - fail->depth < fail->shift) 450 fail->shift = curr->depth - fail->depth; 451 452 /* If the current node is accepting then the shift at the 453 fail and its descendants should be no larger than the 454 difference of their depths. */ 455 if (curr->accepting && fail->maxshift > curr->depth - fail->depth) 456 fail->maxshift = curr->depth - fail->depth; 457 } 458 } 459 460 /* Traverse the trie in level order again, fixing up all nodes whose 461 shift exceeds their inherited maxshift. */ 462 for (curr = kwset->trie->next; curr; curr = curr->next) 463 { 464 if (curr->maxshift > curr->parent->maxshift) 465 curr->maxshift = curr->parent->maxshift; 466 if (curr->shift > curr->maxshift) 467 curr->shift = curr->maxshift; 468 } 469 470 /* Create a vector, indexed by character code, of the outgoing links 471 from the root node. */ 472 for (i = 0; i < NCHAR; ++i) 473 next[i] = NULL; 474 treenext(kwset->trie->links, next); 475 476 if ((trans = kwset->trans) != NULL) 477 for (i = 0; i < NCHAR; ++i) 478 kwset->next[i] = next[U(trans[i])]; 479 else 480 memcpy(kwset->next, next, NCHAR * sizeof(struct trie *)); 481 } 482 483 /* Fix things up for any translation table. */ 484 if ((trans = kwset->trans) != NULL) 485 for (i = 0; i < NCHAR; ++i) 486 kwset->delta[i] = delta[U(trans[i])]; 487 else 488 memcpy(kwset->delta, delta, NCHAR); 489 490 return NULL; 491} 492 493/* Fast boyer-moore search. */ 494static size_t 495bmexec (kwset_t kws, char const *text, size_t size) 496{ 497 struct kwset const *kwset; 498 register unsigned char const *d1; 499 register char const *ep, *sp, *tp; 500 register int d, gc, i, len, md2; 501 502 kwset = (struct kwset const *) kws; 503 len = kwset->mind; 504 505 if (len == 0) 506 return 0; 507 if (len > size) 508 return -1; 509 if (len == 1) 510 { 511 tp = memchr (text, kwset->target[0], size); 512 return tp ? tp - text : -1; 513 } 514 515 d1 = kwset->delta; 516 sp = kwset->target + len; 517 gc = U(sp[-2]); 518 md2 = kwset->mind2; 519 tp = text + len; 520 521 /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */ 522 if (size > 12 * len) 523 /* 11 is not a bug, the initial offset happens only once. */ 524 for (ep = text + size - 11 * len;;) 525 { 526 while (tp <= ep) 527 { 528 d = d1[U(tp[-1])], tp += d; 529 d = d1[U(tp[-1])], tp += d; 530 if (d == 0) 531 goto found; 532 d = d1[U(tp[-1])], tp += d; 533 d = d1[U(tp[-1])], tp += d; 534 d = d1[U(tp[-1])], tp += d; 535 if (d == 0) 536 goto found; 537 d = d1[U(tp[-1])], tp += d; 538 d = d1[U(tp[-1])], tp += d; 539 d = d1[U(tp[-1])], tp += d; 540 if (d == 0) 541 goto found; 542 d = d1[U(tp[-1])], tp += d; 543 d = d1[U(tp[-1])], tp += d; 544 } 545 break; 546 found: 547 if (U(tp[-2]) == gc) 548 { 549 for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i) 550 ; 551 if (i > len) 552 return tp - len - text; 553 } 554 tp += md2; 555 } 556 557 /* Now we have only a few characters left to search. We 558 carefully avoid ever producing an out-of-bounds pointer. */ 559 ep = text + size; 560 d = d1[U(tp[-1])]; 561 while (d <= ep - tp) 562 { 563 d = d1[U((tp += d)[-1])]; 564 if (d != 0) 565 continue; 566 if (U(tp[-2]) == gc) 567 { 568 for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i) 569 ; 570 if (i > len) 571 return tp - len - text; 572 } 573 d = md2; 574 } 575 576 return -1; 577} 578 579/* Hairy multiple string search. */ 580static size_t 581cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch) 582{ 583 struct kwset const *kwset; 584 struct trie * const *next; 585 struct trie const *trie; 586 struct trie const *accept; 587 char const *beg, *lim, *mch, *lmch; 588 register unsigned char c; 589 register unsigned char const *delta; 590 register int d; 591 register char const *end, *qlim; 592 register struct tree const *tree; 593 register unsigned char const *trans; 594 595 accept = NULL; 596 597 /* Initialize register copies and look for easy ways out. */ 598 kwset = (struct kwset *) kws; 599 if (len < kwset->mind) 600 return -1; 601 next = kwset->next; 602 delta = kwset->delta; 603 trans = kwset->trans; 604 lim = text + len; 605 end = text; 606 if ((d = kwset->mind) != 0) 607 mch = NULL; 608 else 609 { 610 mch = text, accept = kwset->trie; 611 goto match; 612 } 613 614 if (len >= 4 * kwset->mind) 615 qlim = lim - 4 * kwset->mind; 616 else 617 qlim = NULL; 618 619 while (lim - end >= d) 620 { 621 if (qlim && end <= qlim) 622 { 623 end += d - 1; 624 while ((d = delta[c = *end]) && end < qlim) 625 { 626 end += d; 627 end += delta[U(*end)]; 628 end += delta[U(*end)]; 629 } 630 ++end; 631 } 632 else 633 d = delta[c = (end += d)[-1]]; 634 if (d) 635 continue; 636 beg = end - 1; 637 trie = next[c]; 638 if (trie->accepting) 639 { 640 mch = beg; 641 accept = trie; 642 } 643 d = trie->shift; 644 while (beg > text) 645 { 646 c = trans ? trans[U(*--beg)] : *--beg; 647 tree = trie->links; 648 while (tree && c != tree->label) 649 if (c < tree->label) 650 tree = tree->llink; 651 else 652 tree = tree->rlink; 653 if (tree) 654 { 655 trie = tree->trie; 656 if (trie->accepting) 657 { 658 mch = beg; 659 accept = trie; 660 } 661 } 662 else 663 break; 664 d = trie->shift; 665 } 666 if (mch) 667 goto match; 668 } 669 return -1; 670 671 match: 672 /* Given a known match, find the longest possible match anchored 673 at or before its starting point. This is nearly a verbatim 674 copy of the preceding main search loops. */ 675 if (lim - mch > kwset->maxd) 676 lim = mch + kwset->maxd; 677 lmch = NULL; 678 d = 1; 679 while (lim - end >= d) 680 { 681 if ((d = delta[c = (end += d)[-1]]) != 0) 682 continue; 683 beg = end - 1; 684 if (!(trie = next[c])) 685 { 686 d = 1; 687 continue; 688 } 689 if (trie->accepting && beg <= mch) 690 { 691 lmch = beg; 692 accept = trie; 693 } 694 d = trie->shift; 695 while (beg > text) 696 { 697 c = trans ? trans[U(*--beg)] : *--beg; 698 tree = trie->links; 699 while (tree && c != tree->label) 700 if (c < tree->label) 701 tree = tree->llink; 702 else 703 tree = tree->rlink; 704 if (tree) 705 { 706 trie = tree->trie; 707 if (trie->accepting && beg <= mch) 708 { 709 lmch = beg; 710 accept = trie; 711 } 712 } 713 else 714 break; 715 d = trie->shift; 716 } 717 if (lmch) 718 { 719 mch = lmch; 720 goto match; 721 } 722 if (!d) 723 d = 1; 724 } 725 726 if (kwsmatch) 727 { 728 kwsmatch->index = accept->accepting / 2; 729 kwsmatch->offset[0] = mch - text; 730 kwsmatch->size[0] = accept->depth; 731 } 732 return mch - text; 733} 734 735/* Search through the given text for a match of any member of the 736 given keyword set. Return a pointer to the first character of 737 the matching substring, or NULL if no match is found. If FOUNDLEN 738 is non-NULL store in the referenced location the length of the 739 matching substring. Similarly, if FOUNDIDX is non-NULL, store 740 in the referenced location the index number of the particular 741 keyword matched. */ 742size_t 743kwsexec (kwset_t kws, char const *text, size_t size, 744 struct kwsmatch *kwsmatch) 745{ 746 struct kwset const *kwset = (struct kwset *) kws; 747 if (kwset->words == 1 && kwset->trans == NULL) 748 { 749 size_t ret = bmexec (kws, text, size); 750 if (kwsmatch != NULL && ret != (size_t) -1) 751 { 752 kwsmatch->index = 0; 753 kwsmatch->offset[0] = ret; 754 kwsmatch->size[0] = kwset->mind; 755 } 756 return ret; 757 } 758 else 759 return cwexec(kws, text, size, kwsmatch); 760} 761 762/* Free the components of the given keyword set. */ 763void 764kwsfree (kwset_t kws) 765{ 766 struct kwset *kwset; 767 768 kwset = (struct kwset *) kws; 769 obstack_free(&kwset->obstack, NULL); 770 free(kws); 771}