897e19f7904f617571ed593c814892e3f028790e
[idzebra-moved-to-github.git] / dfa / grepper.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2010 Index Data
3
4 Zebra is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include <stdio.h>
24 #include <ctype.h>
25 #include <assert.h>
26
27 #include <idzebra/util.h>
28 #include <yaz/yaz-util.h>
29 #include <dfa.h>
30 #include "imalloc.h"
31
32 char *prog;
33 static int show_line = 0;
34
35 typedef unsigned MatchWord;
36 #define WORD_BITS 32
37
38 typedef struct {
39     int n;           /* no of MatchWord needed */
40     int range;       /* max no. of errors */
41     MatchWord *Sc;   /* Mask Sc */
42 } MatchContext;
43
44 #define INFBUF_SIZE 16384
45
46 #define INLINE 
47
48 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
49 {
50     int off = state & (WORD_BITS-1);
51     int wno = state / WORD_BITS;
52
53     m[mc->n * ch + wno] |= 1<<off;
54 }
55
56 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
57                               int state)
58 {
59     int off = state & (WORD_BITS-1);
60     int wno = state / WORD_BITS;
61
62     m[mc->n * ch + wno] &= ~(1<<off);
63 }
64
65 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
66                                  int state)
67 {
68     int off = state & (WORD_BITS-1);
69     int wno = state / WORD_BITS;
70
71     return m[mc->n * ch + wno] & (1<<off);
72 }
73
74 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
75 {
76     MatchContext *mc = imalloc (sizeof(*mc));
77     int i;
78
79     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
80     mc->range = range;
81     mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
82     
83     for (i=0; i<dfa->no_states; i++)
84     {
85         int j;
86         struct DFA_state *state = dfa->states[i];
87
88         for (j=0; j<state->tran_no; j++)
89         {
90             int ch;
91             int ch0 = state->trans[j].ch[0];
92             int ch1 = state->trans[j].ch[1];
93             assert (ch0 >= 0 && ch1 >= 0);
94             
95             for (ch = ch0; ch <= ch1; ch++)
96                 set_bit (mc, mc->Sc, ch, i);
97         }
98     }
99     return mc;
100 }
101
102
103 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
104                         struct DFA *dfa, int ch)
105 {
106     int j, s = 0;
107     MatchWord *Rsrc_p = Rsrc, mask;
108
109     Rdst[0] = 1;
110     for (j = 1; j<mc->n; j++)
111         Rdst[j] = 0;
112     while (1)
113     {
114         mask = *Rsrc_p++;
115         for (j = 0; j<WORD_BITS/4; j++)
116         {
117             if (mask & 15)
118             {
119                 if (mask & 1)
120                 {
121                     struct DFA_state *state = dfa->states[s];
122                     int i = state->tran_no;
123                     while (--i >= 0)
124                         if (ch >= state->trans[i].ch[0] &&
125                             ch <= state->trans[i].ch[1])
126                             set_bit (mc, Rdst, 0, state->trans[i].to);
127                 }
128                 if (mask & 2)
129                 {
130                     struct DFA_state *state = dfa->states[s+1];
131                     int i = state->tran_no;
132                     while (--i >= 0)
133                         if (ch >= state->trans[i].ch[0] &&
134                             ch <= state->trans[i].ch[1])
135                             set_bit (mc, Rdst, 0, state->trans[i].to);
136                 }
137                 if (mask & 4)
138                 {
139                     struct DFA_state *state = dfa->states[s+2];
140                     int i = state->tran_no;
141                     while (--i >= 0)
142                         if (ch >= state->trans[i].ch[0] &&
143                             ch <= state->trans[i].ch[1])
144                             set_bit (mc, Rdst, 0, state->trans[i].to);
145                 }
146                 if (mask & 8)
147                 {
148                     struct DFA_state *state = dfa->states[s+3];
149                     int i = state->tran_no;
150                     while (--i >= 0)
151                         if (ch >= state->trans[i].ch[0] &&
152                             ch <= state->trans[i].ch[1])
153                             set_bit (mc, Rdst, 0, state->trans[i].to);
154                 }
155             }
156             s += 4;
157             if (s >= dfa->no_states)
158                 return;
159             mask >>= 4;
160         }
161     }
162 }
163
164 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
165                    struct DFA *dfa)
166 {
167     int j, s = 0;
168     MatchWord *Rsrc_p = Rsrc, mask;
169     for (j = 0; j<mc->n; j++)
170         Rdst[j] = 0;
171     while (1)
172     {
173         mask = *Rsrc_p++;
174         for (j = 0; j<WORD_BITS/4; j++)
175         {
176             if (mask & 15)
177             {
178                 if (mask & 1)
179                 {
180                     struct DFA_state *state = dfa->states[s];
181                     int i = state->tran_no;
182                     while (--i >= 0)
183                         set_bit (mc, Rdst, 0, state->trans[i].to);
184                 }
185                 if (mask & 2)
186                 {
187                     struct DFA_state *state = dfa->states[s+1];
188                     int i = state->tran_no;
189                     while (--i >= 0)
190                         set_bit (mc, Rdst, 0, state->trans[i].to);
191                 }
192                 if (mask & 4)
193                 {
194                     struct DFA_state *state = dfa->states[s+2];
195                     int i = state->tran_no;
196                     while (--i >= 0)
197                         set_bit (mc, Rdst, 0, state->trans[i].to);
198                 }
199                 if (mask & 8)
200                 {
201                     struct DFA_state *state = dfa->states[s+3];
202                     int i = state->tran_no;
203                     while (--i >= 0)
204                         set_bit (mc, Rdst, 0, state->trans[i].to);
205                 }
206             }
207             s += 4;
208             if (s >= dfa->no_states)
209                 return;
210             mask >>= 4;
211         }
212     }
213 }
214
215 static void or (MatchContext *mc, MatchWord *Rdst,
216                 MatchWord *Rsrc1, MatchWord *Rsrc2)
217 {
218     int i;
219     for (i = 0; i<mc->n; i++)
220         Rdst[i] = Rsrc1[i] | Rsrc2[i];
221 }
222
223
224 static int go (MatchContext *mc, struct DFA *dfa, FILE *inf)
225 {
226     MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
227     int s, d, ch;
228     int lineno = 1;
229     char *infbuf;
230     int inf_ptr = 1;
231     int no_match = 0;
232
233     infbuf = imalloc (INFBUF_SIZE);
234     infbuf[0] = '\n';
235     Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
236     Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
237     Rj_a = icalloc (mc->n * sizeof(*Rj));
238     Rj_b = icalloc (mc->n * sizeof(*Rj));
239     Rj_c = icalloc (mc->n * sizeof(*Rj));
240
241     set_bit (mc, Rj, 0, 0);
242     for (d = 1; d<=mc->range; d++)
243     {
244         int s;
245         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
246         for (s = 0; s<dfa->no_states; s++)
247         {
248             if (get_bit (mc, Rj, d-1, s))
249             {
250                 struct DFA_state *state = dfa->states[s];
251                 int i = state->tran_no;
252                 while (--i >= 0)
253                     set_bit (mc, Rj, d, state->trans[i].to);
254             }
255         }
256     }
257     while ((ch = getc (inf)) != EOF)
258     {
259         MatchWord *Rj_t;
260         
261         infbuf[inf_ptr] = ch;
262         if (ch == '\n')
263         {
264             if (no_match)
265             {
266                 int i = inf_ptr;
267                 if (show_line)
268                     printf ("%5d:", lineno);
269                 do
270                 {
271                     if (--i < 0)
272                         i = INFBUF_SIZE-1;
273                 } while (infbuf[i] != '\n');
274                 do
275                 {
276                     if (++i == INFBUF_SIZE)
277                         i = 0;
278                     putchar (infbuf[i]);
279                 } while (infbuf[i] != '\n');
280                 no_match = 0;
281             }
282             lineno++;
283         }
284         if (++inf_ptr == INFBUF_SIZE)
285             inf_ptr = 0;
286         mask_shift (mc, Rj1, Rj, dfa, ch);
287         for (d = 1; d <= mc->range; d++)
288         {
289             mask_shift (mc, Rj_b, Rj+d*mc->n, dfa, ch);    /* 1 */
290
291             or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
292
293             shift (mc, Rj_c, Rj_a, dfa);
294
295             or (mc, Rj_a, Rj_b, Rj_c);                      /* 1,2,3*/
296
297             or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n);     /* 1,2,3,4 */
298         }
299         for (s = 0; s<dfa->no_states; s++)
300         {
301             if (dfa->states[s]->rule_no)
302                 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
303                     no_match++;
304         }
305         for (d = 0; d <= mc->range; d++)
306             reset_bit (mc, Rj1+d*mc->n, 0, dfa->no_states);
307         Rj_t = Rj1;
308         Rj1 = Rj;
309         Rj = Rj_t;
310     }
311     ifree (Rj);
312     ifree (Rj1);
313     ifree (Rj_a);
314     ifree (Rj_b);
315     ifree (Rj_c);
316     ifree (infbuf);
317     return 0;
318 }
319
320 static int grep_file (struct DFA *dfa, const char *fname, int range)
321 {
322     FILE *inf;
323     MatchContext *mc;
324
325     if (fname)
326     {
327         inf = fopen (fname, "r");
328         if (!inf)
329         {
330             yaz_log (YLOG_FATAL|YLOG_ERRNO, "cannot open `%s'", fname);
331             exit (1);
332         }
333     }
334     else
335         inf = stdin;
336      
337     mc = mk_MatchContext (dfa, range);
338
339     go (mc, dfa, inf);
340
341     if (fname)
342         fclose (inf);
343     return 0;
344 }
345
346 int main (int argc, char **argv)
347 {
348     int ret;
349     int range = 0;
350     char *arg;
351     const char *pattern = NULL;
352     int no_files = 0;
353     struct DFA *dfa = dfa_init();
354
355     prog = argv[0];
356     while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
357     {
358         if (ret == 0)
359         {
360             if (!pattern)
361             {
362                 int i;
363                 pattern = arg;
364                 i = dfa_parse (dfa, &pattern);
365                 if (i || *pattern)
366                 {
367                     fprintf (stderr, "%s: illegal pattern\n", prog);
368                     return 1;
369                 }
370                 dfa_mkstate (dfa);
371             }
372             else
373             {
374                 no_files++;
375                 grep_file (dfa, arg, range);
376             }
377         }
378         else if (ret == 'v')
379         {
380             yaz_log_init (yaz_log_mask_str(arg), prog, NULL);
381         }
382         else if (ret == 's')
383         {
384             dfa_verbose = 1;
385         }
386         else if (ret == 'd')
387         {
388             debug_dfa_tran = 1;
389             debug_dfa_followpos = 1;
390             debug_dfa_trav = 1;
391         }
392         else if (ret == 'r')
393         {
394             range = atoi (arg);
395         }
396         else if (ret == 'n')
397         {
398             show_line = 1;
399         }
400         else
401         {
402             yaz_log (YLOG_FATAL, "Unknown option '-%s'", arg);
403             exit (1);
404         }
405     }
406     if (!pattern)
407     {
408         fprintf (stderr, "usage:\n "
409                  " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
410         exit (1);
411     }
412     else if (no_files == 0)
413     {
414         grep_file (dfa, NULL, range);
415     }
416     dfa_delete (&dfa);
417     return 0;
418 }
419 /*
420  * Local variables:
421  * c-basic-offset: 4
422  * c-file-style: "Stroustrup"
423  * indent-tabs-mode: nil
424  * End:
425  * vim: shiftwidth=4 tabstop=8 expandtab
426  */
427