Public Git Hosting - git/debian.git/blob

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 */

7 /* kwset.c - search for any of a set of keywords.

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.

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.

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/>. */

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. */

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. */

35 #include "cache.h"

37 #include "kwset.h"

38 #include "compat/obstack.h"

40 #define NCHAR (UCHAR_MAX 1)

41 /* adapter for `xmalloc()`, which takes `size_t`, not `long` */

static void *obstack_chunk_alloc(long size)

43 {

        if (size < 0)

                BUG("Cannot allocate a negative amount: %ld", size);

46 return xmalloc(size);

47 }

48 #define obstack_chunk_free free

50 #define U(c) ((unsigned char) (c))

52 /* Balanced tree of edges and labels leaving a given trie node. */

53 struct tree

54 {

55 struct tree *llink; /* Left link; MUST be first field. */

56 struct tree *rlink; /* Right link (to larger labels). */

57 struct trie *trie; /* Trie node pointed to by this edge. */

58 unsigned char label; /* Label on this edge. */

59 char balance; /* Difference in depths of subtrees. */

60 };

62 /* Node of a trie representing a set of reversed keywords. */

63 struct trie

64 {

65 unsigned int accepting; /* Word index of accepted word, or zero. */

66 struct tree *links; /* Tree of edges leaving this node. */

67 struct trie *parent; /* Parent of this node. */

68 struct trie *next; /* List of all trie nodes in level order. */

69 struct trie *fail; /* Aho-Corasick failure function. */

70 int depth; /* Depth of this node from the root. */

71 int shift; /* Shift function for search failures. */

72 int maxshift; /* Max shift of self and descendants. */

73 };

75 /* Structure returned opaquely to the caller, containing everything. */

76 struct kwset

77 {

78 struct obstack obstack; /* Obstack for node allocation. */

79 int words; /* Number of words in the trie. */

80 struct trie *trie; /* The trie itself. */

81 int mind; /* Minimum depth of an accepting node. */

82 int maxd; /* Maximum depth of any node. */

83 unsigned char delta[NCHAR]; /* Delta table for rapid search. */

  struct trie *next[NCHAR];     /* Table of children of the root. */

85 char *target; /* Target string if there's only one. */

86 int mind2; /* Used in Boyer-Moore search for one string. */

87 unsigned char const *trans; /* Character translation table. */

88 };

90 /* Allocate and initialize a keyword set object, returning an opaque

91 pointer to it. Return NULL if memory is not available. */

92 kwset_t

kwsalloc (unsigned char const *trans)

94 {

95 struct kwset *kwset;

  kwset = (struct kwset *) xmalloc(sizeof (struct kwset));

99 obstack_init(&kwset->obstack);

100 kwset->words = 0;

101 kwset->trie

    = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));

103 if (!kwset->trie)

104 {

105 kwsfree((kwset_t) kwset);

106 return NULL;

107 }

  kwset->trie->accepting = 0;

109 kwset->trie->links = NULL;

110 kwset->trie->parent = NULL;

111 kwset->trie->next = NULL;

112 kwset->trie->fail = NULL;

  kwset->trie->depth = 0;

  kwset->trie->shift = 0;

115 kwset->mind = INT_MAX;

116 kwset->maxd = -1;

117 kwset->target = NULL;

118 kwset->trans = trans;

119

120 return (kwset_t) kwset;

121 }

122

123 /* This upper bound is valid for CHAR_BIT >= 4 and

124 exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */

125 #define DEPTH_SIZE (CHAR_BIT CHAR_BIT/2)

126

127 /* Add the given string to the contents of the keyword set. Return NULL

128 for success, an error message otherwise. */

129 const char *

kwsincr (kwset_t kws, char const *text, size_t len)

131 {

132 struct kwset *kwset;

133 register struct trie *trie;

134 register unsigned char label;

135 register struct tree *link;

136 register int depth;

137 struct tree *links[DEPTH_SIZE];

  enum { L, R } dirs[DEPTH_SIZE];

  struct tree *t, *r, *l, *rl, *lr;

140

141 kwset = (struct kwset *) kws;

142 trie = kwset->trie;

143 text = len;

144

145 /* Descend the trie (built of reversed keywords) character-by-character,

146 installing new nodes when necessary. */

147 while (len--)

148 {

      label = kwset->trans ? kwset->trans[U(*--text)] : *--text;

150

151 /* Descend the tree of outgoing links for this trie node,

152 looking for the current character and keeping track

153 of the path followed. */

154 link = trie->links;

      links[0] = (struct tree *) &trie->links;

156 dirs[0] = L;

157 depth = 1;

158

      while (link && label != link->label)

160 {

161 links[depth] = link;

          if (label < link->label)

            dirs[depth  ] = L, link = link->llink;

164 else

            dirs[depth  ] = R, link = link->rlink;

166 }

167

168 /* The current character doesn't have an outgoing link at

169 this trie node, so build a new trie node and install

170 a link in the current trie node's tree. */

171 if (!link)

172 {

          link = (struct tree *) obstack_alloc(&kwset->obstack,

174 sizeof (struct tree));

175 if (!link)

176 return "memory exhausted";

177 link->llink = NULL;

178 link->rlink = NULL;

          link->trie = (struct trie *) obstack_alloc(&kwset->obstack,

180 sizeof (struct trie));

181 if (!link->trie)

182 {

              obstack_free(&kwset->obstack, link);

184 return "memory exhausted";

185 }

          link->trie->accepting = 0;

187 link->trie->links = NULL;

188 link->trie->parent = trie;

189 link->trie->next = NULL;

190 link->trie->fail = NULL;

          link->trie->depth = trie->depth   1;

          link->trie->shift = 0;

193 link->label = label;

194 link->balance = 0;

195

196 /* Install the new tree node in its parent. */

          if (dirs[--depth] == L)

198 links[depth]->llink = link;

199 else

200 links[depth]->rlink = link;

201

202 /* Back up the tree fixing the balance flags. */

          while (depth && !links[depth]->balance)

204 {

              if (dirs[depth] == L)

206 --links[depth]->balance;

207 else

208 links[depth]->balance;

209 --depth;

210 }

211

212 /* Rebalance the tree by pointer rotations if necessary. */

          if (depth && ((dirs[depth] == L && --links[depth]->balance)

                        || (dirs[depth] == R &&   links[depth]->balance)))

215 {

              switch (links[depth]->balance)

217 {

                case (char) -2:

                  switch (dirs[depth   1])

220 {

221 case L:

                      r = links[depth], t = r->llink, rl = t->rlink;

                      t->rlink = r, r->llink = rl;

                      t->balance = r->balance = 0;

225 break;

226 case R:

                      r = links[depth], l = r->llink, t = l->rlink;

                      rl = t->rlink, lr = t->llink;

                      t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;

                      l->balance = t->balance != 1 ? 0 : -1;

                      r->balance = t->balance != (char) -1 ? 0 : 1;

232 t->balance = 0;

233 break;

234 default:

235 abort ();

236 }

237 break;

238 case 2:

                  switch (dirs[depth   1])

240 {

241 case R:

                      l = links[depth], t = l->rlink, lr = t->llink;

                      t->llink = l, l->rlink = lr;

                      t->balance = l->balance = 0;

245 break;

246 case L:

                      l = links[depth], r = l->rlink, t = r->llink;

                      lr = t->llink, rl = t->rlink;

                      t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;

                      l->balance = t->balance != 1 ? 0 : -1;

                      r->balance = t->balance != (char) -1 ? 0 : 1;

252 t->balance = 0;

253 break;

254 default:

255 abort ();

256 }

257 break;

258 default:

259 abort ();

260 }

261

              if (dirs[depth - 1] == L)

                links[depth - 1]->llink = t;

264 else

                links[depth - 1]->rlink = t;

266 }

267 }

268

269 trie = link->trie;

270 }

271

272 /* Mark the node we finally reached as accepting, encoding the

273 index number of this word in the keyword set so far. */

274 if (!trie->accepting)

    trie->accepting = 1   2 * kwset->words;

276 kwset->words;

277

278 /* Keep track of the longest and shortest string of the keyword set. */

  if (trie->depth < kwset->mind)

280 kwset->mind = trie->depth;

  if (trie->depth > kwset->maxd)

282 kwset->maxd = trie->depth;

283

284 return NULL;

285 }

286

287 /* Enqueue the trie nodes referenced from the given tree in the

288 given queue. */

289 static void

enqueue (struct tree *tree, struct trie **last)

291 {

292 if (!tree)

293 return;

  enqueue(tree->llink, last);

  enqueue(tree->rlink, last);

  (*last) = (*last)->next = tree->trie;

297 }

298

299 /* Compute the Aho-Corasick failure function for the trie nodes referenced

300 from the given tree, given the failure function for their parent as

301 well as a last resort failure node. */

302 static void

treefails (register struct tree const *tree, struct trie const *fail,

304 struct trie *recourse)

305 {

306 register struct tree *link;

307

308 if (!tree)

309 return;

310

  treefails(tree->llink, fail, recourse);

  treefails(tree->rlink, fail, recourse);

313

314 /* Find, in the chain of fails going back to the root, the first

315 node that has a descendant on the current label. */

316 while (fail)

317 {

318 link = fail->links;

      while (link && tree->label != link->label)

        if (tree->label < link->label)

321 link = link->llink;

322 else

323 link = link->rlink;

324 if (link)

325 {

          tree->trie->fail = link->trie;

327 return;

328 }

329 fail = fail->fail;

330 }

331

332 tree->trie->fail = recourse;

333 }

334

335 /* Set delta entries for the links of the given tree such that

336 the preexisting delta value is larger than the current depth. */

337 static void

treedelta (register struct tree const *tree,

339 register unsigned int depth,

340 unsigned char delta[])

341 {

342 if (!tree)

343 return;

  treedelta(tree->llink, depth, delta);

  treedelta(tree->rlink, depth, delta);

  if (depth < delta[tree->label])

347 delta[tree->label] = depth;

348 }

349

350 /* Return true if A has every label in B. */

351 static int

hasevery (register struct tree const *a, register struct tree const *b)

353 {

354 if (!b)

355 return 1;

  if (!hasevery(a, b->llink))

357 return 0;

  if (!hasevery(a, b->rlink))

359 return 0;

  while (a && b->label != a->label)

    if (b->label < a->label)

362 a = a->llink;

363 else

364 a = a->rlink;

365 return !!a;

366 }

367

368 /* Compute a vector, indexed by character code, of the trie nodes

369 referenced from the given tree. */

370 static void

treenext (struct tree const *tree, struct trie *next[])

372 {

373 if (!tree)

374 return;

  treenext(tree->llink, next);

  treenext(tree->rlink, next);

  next[tree->label] = tree->trie;

378 }

379

380 /* Compute the shift for each trie node, as well as the delta

381 table and next cache for the given keyword set. */

382 const char *

383 kwsprep (kwset_t kws)

384 {

385 register struct kwset *kwset;

386 register int i;

387 register struct trie *curr;

388 register unsigned char const *trans;

389 unsigned char delta[NCHAR];

390

391 kwset = (struct kwset *) kws;

392

393 /* Initial values for the delta table; will be changed later. The

394 delta entry for a given character is the smallest depth of any

395 node at which an outgoing edge is labeled by that character. */

  memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);

397

398 /* Check if we can use the simple boyer-moore algorithm, instead

399 of the hairy commentz-walter algorithm. */

  if (kwset->words == 1 && kwset->trans == NULL)

401 {

402 char c;

403

404 /* Looking for just one string. Extract it from the trie. */

      kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);

406 if (!kwset->target)

407 return "memory exhausted";

      for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)

409 {

          kwset->target[i] = curr->links->label;

411 curr = curr->links->trie;

412 }

413 /* Build the Boyer Moore delta. Boy that's easy compared to CW. */

      for (i = 0; i < kwset->mind;   i)

        delta[U(kwset->target[i])] = kwset->mind - (i   1);

416 /* Find the minimal delta2 shift that we might make after

417 a backwards match has failed. */

      c = kwset->target[kwset->mind - 1];

      for (i = kwset->mind - 2; i >= 0; --i)

        if (kwset->target[i] == c)

421 break;

      kwset->mind2 = kwset->mind - (i   1);

423 }

424 else

425 {

426 register struct trie *fail;

      struct trie *last, *next[NCHAR];

428

429 /* Traverse the nodes of the trie in level order, simultaneously

430 computing the delta table, failure function, and shift function. */

      for (curr = last = kwset->trie; curr; curr = curr->next)

432 {

433 /* Enqueue the immediate descendants in the level order queue. */

          enqueue(curr->links, &last);

435

436 curr->shift = kwset->mind;

437 curr->maxshift = kwset->mind;

438

439 /* Update the delta table for the descendants of this node. */

          treedelta(curr->links, curr->depth, delta);

441

442 /* Compute the failure function for the descendants of this node. */

          treefails(curr->links, curr->fail, kwset->trie);

444

445 /* Update the shifts at each node in the current node's chain

446 of fails back to the root. */

          for (fail = curr->fail; fail; fail = fail->fail)

448 {

449 /* If the current node has some outgoing edge that the fail

450 doesn't, then the shift at the fail should be no larger

451 than the difference of their depths. */

              if (!hasevery(fail->links, curr->links))

                if (curr->depth - fail->depth < fail->shift)

                  fail->shift = curr->depth - fail->depth;

455

456 /* If the current node is accepting then the shift at the

457 fail and its descendants should be no larger than the

458 difference of their depths. */

              if (curr->accepting && fail->maxshift > curr->depth - fail->depth)

                fail->maxshift = curr->depth - fail->depth;

461 }

462 }

463

464 /* Traverse the trie in level order again, fixing up all nodes whose

465 shift exceeds their inherited maxshift. */

      for (curr = kwset->trie->next; curr; curr = curr->next)

467 {

          if (curr->maxshift > curr->parent->maxshift)

            curr->maxshift = curr->parent->maxshift;

          if (curr->shift > curr->maxshift)

471 curr->shift = curr->maxshift;

472 }

473

474 /* Create a vector, indexed by character code, of the outgoing links

475 from the root node. */

      for (i = 0; i < NCHAR;   i)

477 next[i] = NULL;

      treenext(kwset->trie->links, next);

479

      if ((trans = kwset->trans))

        for (i = 0; i < NCHAR;   i)

          kwset->next[i] = next[U(trans[i])];

483 else

        COPY_ARRAY(kwset->next, next, NCHAR);

485 }

486

487 /* Fix things up for any translation table. */

  if ((trans = kwset->trans))

    for (i = 0; i < NCHAR;   i)

      kwset->delta[i] = delta[U(trans[i])];

491 else

    memcpy(kwset->delta, delta, NCHAR);

493

494 return NULL;

495 }

496

497 /* Fast boyer-moore search. */

498 static size_t

bmexec (kwset_t kws, char const *text, size_t size)

500 {

501 struct kwset const *kwset;

502 register unsigned char const *d1;

  register char const *ep, *sp, *tp;

  register int d, gc, i, len, md2;

505

  kwset = (struct kwset const *) kws;

507 len = kwset->mind;

508

  if (len == 0)

510 return 0;

511 if (len > size)

512 return -1;

  if (len == 1)

514 {

      tp = memchr (text, kwset->target[0], size);

      return tp ? tp - text : -1;

517 }

518

519 d1 = kwset->delta;

520 sp = kwset->target len;

  gc = U(sp[-2]);

522 md2 = kwset->mind2;

523 tp = text len;

524

525 /* Significance of 12: 1 (initial offset) 10 (skip loop) 1 (md2). */

  if (size > 12 * len)

527 /* 11 is not a bug, the initial offset happens only once. */

    for (ep = text   size - 11 * len;;)

529 {

530 while (tp <= ep)

531 {

            d = d1[U(tp[-1])], tp  = d;

            d = d1[U(tp[-1])], tp  = d;

            if (d == 0)

535 goto found;

            d = d1[U(tp[-1])], tp  = d;

            d = d1[U(tp[-1])], tp  = d;

            d = d1[U(tp[-1])], tp  = d;

            if (d == 0)

540 goto found;

            d = d1[U(tp[-1])], tp  = d;

            d = d1[U(tp[-1])], tp  = d;

            d = d1[U(tp[-1])], tp  = d;

            if (d == 0)

545 goto found;

            d = d1[U(tp[-1])], tp  = d;

            d = d1[U(tp[-1])], tp  = d;

548 }

549 break;

550 found:

        if (U(tp[-2]) == gc)

552 {

            for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]);   i)

554 ;

555 if (i > len)

556 return tp - len - text;

557 }

558 tp = md2;

559 }

560

561 /* Now we have only a few characters left to search. We

562 carefully avoid ever producing an out-of-bounds pointer. */

563 ep = text size;

  d = d1[U(tp[-1])];

  while (d <= ep - tp)

566 {

      d = d1[U((tp  = d)[-1])];

      if (d != 0)

569 continue;

      if (U(tp[-2]) == gc)

571 {

          for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]);   i)

573 ;

574 if (i > len)

575 return tp - len - text;

576 }

577 d = md2;

578 }

579

580 return -1;

581 }

582

583 /* Hairy multiple string search. */

584 static size_t

cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)

586 {

587 struct kwset const *kwset;

  struct trie * const *next;

589 struct trie const *trie;

590 struct trie const *accept;

  char const *beg, *lim, *mch, *lmch;

592 register unsigned char c;

593 register unsigned char const *delta;

863 register int d;

  register char const *end, *qlim;

  register struct tree const *tree;

597 register unsigned char const *trans;

598

599 accept = NULL;

600

601 /* Initialize register copies and look for easy ways out. */

602 kwset = (struct kwset *) kws;

  if (len < kwset->mind)

604 return -1;

605 next = kwset->next;

606 delta = kwset->delta;

607 trans = kwset->trans;

608 lim = text len;

609 end = text;

  if ((d = kwset->mind) != 0)

611 mch = NULL;

612 else

613 {

      mch = text, accept = kwset->trie;

615 goto match;

616 }

617

  if (len >= 4 * kwset->mind)

    qlim = lim - 4 * kwset->mind;

620 else

621 qlim = NULL;

622

  while (lim - end >= d)

624 {

      if (qlim && end <= qlim)

626 {

627 end = d - 1;

          while ((d = delta[c = *end]) && end < qlim)

629 {

630 end = d;

              end  = delta[U(*end)];

              end  = delta[U(*end)];

633 }

634 end;

635 }

636 else

        d = delta[c = (end  = d)[-1]];

638 if (d)

639 continue;

640 beg = end - 1;

641 trie = next[c];

642 if (trie->accepting)

643 {

644 mch = beg;

645 accept = trie;

646 }

647 d = trie->shift;

648 while (beg > text)

649 {

          c = trans ? trans[U(*--beg)] : *--beg;

651 tree = trie->links;

          while (tree && c != tree->label)

            if (c < tree->label)

654 tree = tree->llink;

655 else

656 tree = tree->rlink;

657 if (tree)

658 {

659 trie = tree->trie;

660 if (trie->accepting)

661 {

662 mch = beg;

663 accept = trie;

664 }

665 }

666 else

667 break;

668 d = trie->shift;

669 }

670 if (mch)

671 goto match;

672 }

673 return -1;

674

675 match:

676 /* Given a known match, find the longest possible match anchored

677 at or before its starting point. This is nearly a verbatim

678 copy of the preceding main search loops. */

  if (lim - mch > kwset->maxd)

680 lim = mch kwset->maxd;

681 lmch = NULL;

682 d = 1;

  while (lim - end >= d)

684 {

      if ((d = delta[c = (end  = d)[-1]]) != 0)

686 continue;

687 beg = end - 1;

      if (!(trie = next[c]))

689 {

690 d = 1;

691 continue;

692 }

      if (trie->accepting && beg <= mch)

694 {

695 lmch = beg;

696 accept = trie;

697 }

698 d = trie->shift;

699 while (beg > text)

700 {

          c = trans ? trans[U(*--beg)] : *--beg;

702 tree = trie->links;

          while (tree && c != tree->label)

            if (c < tree->label)

705 tree = tree->llink;

706 else

707 tree = tree->rlink;

708 if (tree)

709 {

710 trie = tree->trie;

              if (trie->accepting && beg <= mch)

712 {

713 lmch = beg;

714 accept = trie;

715 }

716 }

717 else

718 break;

719 d = trie->shift;

720 }

721 if (lmch)

722 {

723 mch = lmch;

724 goto match;

725 }

726 if (!d)

727 d = 1;

728 }

729

730 if (kwsmatch)

731 {

      kwsmatch->index = accept->accepting / 2;

      kwsmatch->offset[0] = mch - text;

      kwsmatch->size[0] = accept->depth;

735 }

736 return mch - text;

737 }

738

739 /* Search through the given text for a match of any member of the

740 given keyword set. Return a pointer to the first character of

741 the matching substring, or NULL if no match is found. If FOUNDLEN

742 is non-NULL store in the referenced location the length of the

743 matching substring. Similarly, if FOUNDIDX is non-NULL, store

744 in the referenced location the index number of the particular

745 keyword matched. */

746 size_t

kwsexec (kwset_t kws, char const *text, size_t size,

748 struct kwsmatch *kwsmatch)

749 {

  struct kwset const *kwset = (struct kwset *) kws;

  if (kwset->words == 1 && kwset->trans == NULL)

752 {

      size_t ret = bmexec (kws, text, size);

      if (kwsmatch != NULL && ret != (size_t) -1)

755 {

756 kwsmatch->index = 0;

          kwsmatch->offset[0] = ret;

          kwsmatch->size[0] = kwset->mind;

759 }

760 return ret;

761 }

762 else

    return cwexec(kws, text, size, kwsmatch);

764 }

765

766 /* Free the components of the given keyword set. */

767 void

768 kwsfree (kwset_t kws)

769 {

770 struct kwset *kwset;

771

772 kwset = (struct kwset *) kws;

  obstack_free(&kwset->obstack, NULL);

774 free(kws);

775 }