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