Merge branch 'fc/macos-x-clipped-write' into maint
[git] / 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, 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. */
49 struct 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. */
59 struct 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 descendents. */
69 };
70
71 /* Structure returned opaquely to the caller, containing everything. */
72 struct 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   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. */
88 kwset_t
89 kwsalloc (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. */
125 const char *
126 kwsincr (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. */
285 static void
286 enqueue (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. */
298 static void
299 treefails (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 descendent 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. */
333 static void
334 treedelta (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. */
347 static int
348 hasevery (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. */
366 static void
367 treenext (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. */
378 const char *
379 kwsprep (kwset_t kws)
380 {
381   register struct kwset *kwset;
382   register int i;
383   register struct trie *curr;
384   register 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 descendents 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 descendents 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 descendents 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. */
494 static size_t
495 bmexec (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. */
580 static size_t
581 cwexec (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 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. */
742 size_t
743 kwsexec (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. */
763 void
764 kwsfree (kwset_t kws)
765 {
766   struct kwset *kwset;
767
768   kwset = (struct kwset *) kws;
769   obstack_free(&kwset->obstack, NULL);
770   free(kws);
771 }