Merge from vendor branch BINUTILS:
[dragonfly.git] / gnu / usr.bin / grep / search.c
1 /* search.c - searching subroutines using dfa, kwset and regex for grep.
2    Copyright (C) 1992, 1998 Free Software Foundation, Inc.
3
4    This program is free software; you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation; either version 2, or (at your option)
7    any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software
16    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
17    02111-1307, USA.  */
18
19 /* Written August 1992 by Mike Haertel. */
20
21 /* $FreeBSD: src/gnu/usr.bin/grep/search.c,v 1.10 2000/01/31 13:28:57 ru Exp $ */
22 /* $DragonFly: src/gnu/usr.bin/grep/search.c,v 1.2 2003/06/17 04:25:45 dillon Exp $ */
23
24 #ifdef HAVE_CONFIG_H
25 # include <config.h>
26 #endif
27 #include <sys/types.h>
28 #include "system.h"
29 #include "grep.h"
30 #ifdef __FreeBSD__
31 #include <gnuregex.h>
32 #else
33 #include "regex.h"
34 #endif
35 #include "dfa.h"
36 #include "kwset.h"
37
38 #define NCHAR (UCHAR_MAX + 1)
39
40 static void Gcompile PARAMS((char *, size_t));
41 static void Ecompile PARAMS((char *, size_t));
42 static char *EGexecute PARAMS((char *, size_t, char **));
43 static void Fcompile PARAMS((char *, size_t));
44 static char *Fexecute PARAMS((char *, size_t, char **));
45 static void kwsinit PARAMS((void));
46
47 /* Here is the matchers vector for the main program. */
48 struct matcher matchers[] = {
49   { "default", Gcompile, EGexecute },
50   { "grep", Gcompile, EGexecute },
51   { "egrep", Ecompile, EGexecute },
52   { "awk", Ecompile, EGexecute },
53   { "fgrep", Fcompile, Fexecute },
54   { 0, 0, 0 },
55 };
56
57 /* For -w, we also consider _ to be word constituent.  */
58 #define WCHAR(C) (ISALNUM(C) || (C) == '_')
59
60 /* DFA compiled regexp. */
61 static struct dfa dfa;
62
63 /* Regex compiled regexp. */
64 static struct re_pattern_buffer regexbuf;
65
66 /* KWset compiled pattern.  For Ecompile and Gcompile, we compile
67    a list of strings, at least one of which is known to occur in
68    any string matching the regexp. */
69 static kwset_t kwset;
70
71 /* Last compiled fixed string known to exactly match the regexp.
72    If kwsexec() returns < lastexact, then we don't need to
73    call the regexp matcher at all. */
74 static int lastexact;
75
76 void
77 dfaerror (char const *mesg)
78 {
79   fatal(mesg, 0);
80 }
81
82 static void
83 kwsinit (void)
84 {
85   static char trans[NCHAR];
86   int i;
87
88   if (match_icase)
89     for (i = 0; i < NCHAR; ++i)
90       trans[i] = TOLOWER(i);
91
92   if (!(kwset = kwsalloc(match_icase ? trans : (char *) 0)))
93     fatal("memory exhausted", 0);
94 }
95
96 /* If the DFA turns out to have some set of fixed strings one of
97    which must occur in the match, then we build a kwset matcher
98    to find those strings, and thus quickly filter out impossible
99    matches. */
100 static void
101 kwsmusts (void)
102 {
103   struct dfamust *dm;
104   char *err;
105
106   if (dfa.musts)
107     {
108       kwsinit();
109       /* First, we compile in the substrings known to be exact
110          matches.  The kwset matcher will return the index
111          of the matching string that it chooses. */
112       for (dm = dfa.musts; dm; dm = dm->next)
113         {
114           if (!dm->exact)
115             continue;
116           ++lastexact;
117           if ((err = kwsincr(kwset, dm->must, strlen(dm->must))) != 0)
118             fatal(err, 0);
119         }
120       /* Now, we compile the substrings that will require
121          the use of the regexp matcher.  */
122       for (dm = dfa.musts; dm; dm = dm->next)
123         {
124           if (dm->exact)
125             continue;
126           if ((err = kwsincr(kwset, dm->must, strlen(dm->must))) != 0)
127             fatal(err, 0);
128         }
129       if ((err = kwsprep(kwset)) != 0)
130         fatal(err, 0);
131     }
132 }
133
134 static void
135 Gcompile (char *pattern, size_t size)
136 {
137   const char *err;
138
139   re_set_syntax(RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE);
140   dfasyntax(RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE, match_icase, eolbyte);
141
142   if ((err = re_compile_pattern(pattern, size, &regexbuf)) != 0)
143     fatal(err, 0);
144
145   /* In the match_words and match_lines cases, we use a different pattern
146      for the DFA matcher that will quickly throw out cases that won't work.
147      Then if DFA succeeds we do some hairy stuff using the regex matcher
148      to decide whether the match should really count. */
149   if (match_words || match_lines)
150     {
151       /* In the whole-word case, we use the pattern:
152          (^|[^A-Za-z_])(userpattern)([^A-Za-z_]|$).
153          In the whole-line case, we use the pattern:
154          ^(userpattern)$.
155          BUG: Using [A-Za-z_] is locale-dependent!
156          So will use [:alnum:] */
157
158       char *n = malloc(size + 50);
159       int i = 0;
160
161       strcpy(n, "");
162
163       if (match_lines)
164         strcpy(n, "^\\(");
165       if (match_words)
166         strcpy(n, "\\(^\\|[^[:alnum:]_]\\)\\(");
167
168       i = strlen(n);
169       memcpy(n + i, pattern, size);
170       i += size;
171
172       if (match_words)
173         strcpy(n + i, "\\)\\([^[:alnum:]_]\\|$\\)");
174       if (match_lines)
175         strcpy(n + i, "\\)$");
176
177       i += strlen(n + i);
178       dfacomp(n, i, &dfa, 1);
179     }
180   else
181     dfacomp(pattern, size, &dfa, 1);
182
183   kwsmusts();
184 }
185
186 static void
187 Ecompile (char *pattern, size_t size)
188 {
189   const char *err;
190
191   if (strcmp(matcher, "awk") == 0)
192     {
193       re_set_syntax(RE_SYNTAX_AWK);
194       dfasyntax(RE_SYNTAX_AWK, match_icase, eolbyte);
195     }
196   else
197     {
198       re_set_syntax (RE_SYNTAX_POSIX_EGREP);
199       dfasyntax (RE_SYNTAX_POSIX_EGREP, match_icase, eolbyte);
200     }
201
202   if ((err = re_compile_pattern(pattern, size, &regexbuf)) != 0)
203     fatal(err, 0);
204
205   /* In the match_words and match_lines cases, we use a different pattern
206      for the DFA matcher that will quickly throw out cases that won't work.
207      Then if DFA succeeds we do some hairy stuff using the regex matcher
208      to decide whether the match should really count. */
209   if (match_words || match_lines)
210     {
211       /* In the whole-word case, we use the pattern:
212          (^|[^A-Za-z_])(userpattern)([^A-Za-z_]|$).
213          In the whole-line case, we use the pattern:
214          ^(userpattern)$.
215          BUG: Using [A-Za-z_] is locale-dependent!
216          so will use the char class */
217
218       char *n = malloc(size + 50);
219       int i = 0;
220
221       strcpy(n, "");
222
223       if (match_lines)
224         strcpy(n, "^(");
225       if (match_words)
226         strcpy(n, "(^|[^[:alnum:]_])(");
227
228       i = strlen(n);
229       memcpy(n + i, pattern, size);
230       i += size;
231
232       if (match_words)
233         strcpy(n + i, ")([^[:alnum:]_]|$)");
234       if (match_lines)
235         strcpy(n + i, ")$");
236
237       i += strlen(n + i);
238       dfacomp(n, i, &dfa, 1);
239     }
240   else
241     dfacomp(pattern, size, &dfa, 1);
242
243   kwsmusts();
244 }
245
246 static char *
247 EGexecute (char *buf, size_t size, char **endp)
248 {
249   register char *buflim, *beg, *end, save;
250   char eol = eolbyte;
251   int backref, start, len;
252   struct kwsmatch kwsm;
253   static struct re_registers regs; /* This is static on account of a BRAIN-DEAD
254                                     Q@#%!# library interface in regex.c.  */
255
256   buflim = buf + size;
257
258   for (beg = end = buf; end < buflim; beg = end + 1)
259     {
260       if (kwset)
261         {
262           /* Find a possible match using the KWset matcher. */
263           beg = kwsexec(kwset, beg, buflim - beg, &kwsm);
264           if (!beg)
265             goto failure;
266           /* Narrow down to the line containing the candidate, and
267              run it through DFA. */
268           end = memchr(beg, eol, buflim - beg);
269           if (!end)
270             end = buflim;
271           while (beg > buf && beg[-1] != eol)
272             --beg;
273           save = *end;
274           if (kwsm.index < lastexact)
275             goto success;
276           if (!dfaexec(&dfa, beg, end, 0, (int *) 0, &backref))
277             {
278               *end = save;
279               continue;
280             }
281           *end = save;
282           /* Successful, no backreferences encountered. */
283           if (!backref)
284             goto success;
285         }
286       else
287         {
288           /* No good fixed strings; start with DFA. */
289           save = *buflim;
290           beg = dfaexec(&dfa, beg, buflim, 0, (int *) 0, &backref);
291           *buflim = save;
292           if (!beg)
293             goto failure;
294           /* Narrow down to the line we've found. */
295           end = memchr(beg, eol, buflim - beg);
296           if (!end)
297             end = buflim;
298           while (beg > buf && beg[-1] != eol)
299             --beg;
300           /* Successful, no backreferences encountered! */
301           if (!backref)
302             goto success;
303         }
304       /* If we've made it to this point, this means DFA has seen
305          a probable match, and we need to run it through Regex. */
306       regexbuf.not_eol = 0;
307       if ((start = re_search(&regexbuf, beg, end - beg, 0, end - beg, &regs)) >= 0)
308         {
309           len = regs.end[0] - start;
310           if ((!match_lines && !match_words)
311               || (match_lines && len == end - beg))
312             goto success;
313           /* If -w, check if the match aligns with word boundaries.
314              We do this iteratively because:
315              (a) the line may contain more than one occurence of the pattern, and
316              (b) Several alternatives in the pattern might be valid at a given
317              point, and we may need to consider a shorter one to find a word
318              boundary. */
319           if (match_words)
320             while (start >= 0)
321               {
322                 if ((start == 0 || !WCHAR ((unsigned char) beg[start - 1]))
323                     && (len == end - beg
324                         || !WCHAR ((unsigned char) beg[start + len])))
325                   goto success;
326                 if (len > 0)
327                   {
328                     /* Try a shorter length anchored at the same place. */
329                     --len;
330                     regexbuf.not_eol = 1;
331                     len = re_match(&regexbuf, beg, start + len, start, &regs);
332                   }
333                 if (len <= 0)
334                   {
335                     /* Try looking further on. */
336                     if (start == end - beg)
337                       break;
338                     ++start;
339                     regexbuf.not_eol = 0;
340                     start = re_search(&regexbuf, beg, end - beg,
341                                       start, end - beg - start, &regs);
342                     len = regs.end[0] - start;
343                   }
344               }
345         }
346     }
347
348  failure:
349   return 0;
350
351  success:
352   *endp = end < buflim ? end + 1 : end;
353   return beg;
354 }
355
356 static void
357 Fcompile (char *pattern, size_t size)
358 {
359   char *beg, *lim, *err;
360
361   kwsinit();
362   beg = pattern;
363   do
364     {
365       for (lim = beg; lim < pattern + size && *lim != '\n'; ++lim)
366         ;
367       if ((err = kwsincr(kwset, beg, lim - beg)) != 0)
368         fatal(err, 0);
369       if (lim < pattern + size)
370         ++lim;
371       beg = lim;
372     }
373   while (beg < pattern + size);
374
375   if ((err = kwsprep(kwset)) != 0)
376     fatal(err, 0);
377 }
378
379 static char *
380 Fexecute (char *buf, size_t size, char **endp)
381 {
382   register char *beg, *try, *end;
383   register size_t len;
384   char eol = eolbyte;
385   struct kwsmatch kwsmatch;
386
387   for (beg = buf; beg <= buf + size; ++beg)
388     {
389       if (!(beg = kwsexec(kwset, beg, buf + size - beg, &kwsmatch)))
390         return 0;
391       len = kwsmatch.size[0];
392       if (match_lines)
393         {
394           if (beg > buf && beg[-1] != eol)
395             continue;
396           if (beg + len < buf + size && beg[len] != eol)
397             continue;
398           goto success;
399         }
400       else if (match_words)
401         for (try = beg; len && try;)
402           {
403             if (try > buf && WCHAR((unsigned char) try[-1]))
404               break;
405             if (try + len < buf + size && WCHAR((unsigned char) try[len]))
406               {
407                 try = kwsexec(kwset, beg, --len, &kwsmatch);
408                 len = kwsmatch.size[0];
409               }
410             else
411               goto success;
412           }
413       else
414         goto success;
415     }
416
417   return 0;
418
419  success:
420   if ((end = memchr(beg + len, eol, (buf + size) - (beg + len))) != 0)
421     ++end;
422   else
423     end = buf + size;
424   *endp = end;
425   while (beg > buf && beg[-1] != '\n')
426     --beg;
427   return beg;
428 }