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