Merge branch 'bl/userdiff-octave'
[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, 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. */
47 struct 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. */
57 struct 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. */
70 struct 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. */
86 kwset_t
87 kwsalloc (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. */
123 const char *
124 kwsincr (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. */
283 static void
284 enqueue (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. */
296 static void
297 treefails (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. */
331 static void
332 treedelta (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. */
345 static int
346 hasevery (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. */
364 static void
365 treenext (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. */
376 const char *
377 kwsprep (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. */
492 static size_t
493 bmexec (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. */
578 static size_t
579 cwexec (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. */
740 size_t
741 kwsexec (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. */
761 void
762 kwsfree (kwset_t kws)
763 {
764   struct kwset *kwset;
765
766   kwset = (struct kwset *) kws;
767   obstack_free(&kwset->obstack, NULL);
768   free(kws);
769 }