Bug fix: result sets with ranked operands weren't sorted.
[idzebra-moved-to-github.git] / dfa / grepper.c
1 /*
2  * Copyright (C) 1994, Index Data I/S 
3  * All rights reserved.
4  * Sebastian Hammer, Adam Dickmeiss
5  *
6  * $Log: grepper.c,v $
7  * Revision 1.6  1996-01-08 09:09:20  adam
8  * Function dfa_parse got 'const' string argument.
9  * New functions to define char mappings made public.
10  *
11  * Revision 1.5  1995/09/04  12:33:26  adam
12  * Various cleanup. YAZ util used instead.
13  *
14  * Revision 1.4  1995/01/24  16:00:21  adam
15  * Added -ansi to CFLAGS.
16  * Some changes to the dfa module.
17  *
18  * Revision 1.3  1994/10/04  17:46:43  adam
19  * Function options now returns arg with error option.
20  *
21  * Revision 1.2  1994/10/03  17:22:18  adam
22  * Optimization of grepper.
23  *
24  * Revision 1.1  1994/09/27  16:31:18  adam
25  * First version of grepper: grep with error correction.
26  *
27  */
28 #include <stdlib.h>
29 #include <string.h>
30 #include <stdio.h>
31 #include <ctype.h>
32 #include <assert.h>
33
34 #include <alexutil.h>
35 #include <dfa.h>
36 #include "imalloc.h"
37
38 char *prog;
39 static int show_line = 0;
40
41 typedef unsigned MatchWord;
42 #define WORD_BITS 32
43
44 typedef struct {
45     int n;           /* no of MatchWord needed */
46     int range;       /* max no. of errors */
47     MatchWord *Sc;   /* Mask Sc */
48 } MatchContext;
49
50 #define INFBUF_SIZE 16384
51
52 #define INLINE 
53
54 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
55 {
56     int off = state & (WORD_BITS-1);
57     int wno = state / WORD_BITS;
58
59     m[mc->n * ch + wno] |= 1<<off;
60 }
61
62 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
63                               int state)
64 {
65     int off = state & (WORD_BITS-1);
66     int wno = state / WORD_BITS;
67
68     m[mc->n * ch + wno] &= ~(1<<off);
69 }
70
71 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
72                                  int state)
73 {
74     int off = state & (WORD_BITS-1);
75     int wno = state / WORD_BITS;
76
77     return m[mc->n * ch + wno] & (1<<off);
78 }
79
80 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
81 {
82     MatchContext *mc = imalloc (sizeof(*mc));
83     int i;
84
85     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
86     mc->range = range;
87     mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
88     
89     for (i=0; i<dfa->no_states; i++)
90     {
91         int j;
92         struct DFA_state *state = dfa->states[i];
93
94         for (j=0; j<state->tran_no; j++)
95         {
96             int ch;
97             int ch0 = state->trans[j].ch[0];
98             int ch1 = state->trans[j].ch[1];
99             assert (ch0 >= 0 && ch1 >= 0);
100             
101             for (ch = ch0; ch <= ch1; ch++)
102                 set_bit (mc, mc->Sc, ch, i);
103         }
104     }
105     return mc;
106 }
107
108
109 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
110                         struct DFA *dfa, int ch)
111 {
112     int j, s = 0;
113     MatchWord *Rsrc_p = Rsrc, mask;
114
115     Rdst[0] = 1;
116     for (j = 1; j<mc->n; j++)
117         Rdst[j] = 0;
118     while (1)
119     {
120         mask = *Rsrc_p++;
121         for (j = 0; j<WORD_BITS/4; j++)
122         {
123             if (mask & 15)
124             {
125                 if (mask & 1)
126                 {
127                     struct DFA_state *state = dfa->states[s];
128                     int i = state->tran_no;
129                     while (--i >= 0)
130                         if (ch >= state->trans[i].ch[0] &&
131                             ch <= state->trans[i].ch[1])
132                             set_bit (mc, Rdst, 0, state->trans[i].to);
133                 }
134                 if (mask & 2)
135                 {
136                     struct DFA_state *state = dfa->states[s+1];
137                     int i = state->tran_no;
138                     while (--i >= 0)
139                         if (ch >= state->trans[i].ch[0] &&
140                             ch <= state->trans[i].ch[1])
141                             set_bit (mc, Rdst, 0, state->trans[i].to);
142                 }
143                 if (mask & 4)
144                 {
145                     struct DFA_state *state = dfa->states[s+2];
146                     int i = state->tran_no;
147                     while (--i >= 0)
148                         if (ch >= state->trans[i].ch[0] &&
149                             ch <= state->trans[i].ch[1])
150                             set_bit (mc, Rdst, 0, state->trans[i].to);
151                 }
152                 if (mask & 8)
153                 {
154                     struct DFA_state *state = dfa->states[s+3];
155                     int i = state->tran_no;
156                     while (--i >= 0)
157                         if (ch >= state->trans[i].ch[0] &&
158                             ch <= state->trans[i].ch[1])
159                             set_bit (mc, Rdst, 0, state->trans[i].to);
160                 }
161             }
162             s += 4;
163             if (s >= dfa->no_states)
164                 return;
165             mask >>= 4;
166         }
167     }
168 }
169
170 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
171                    struct DFA *dfa)
172 {
173     int j, s = 0;
174     MatchWord *Rsrc_p = Rsrc, mask;
175     for (j = 0; j<mc->n; j++)
176         Rdst[j] = 0;
177     while (1)
178     {
179         mask = *Rsrc_p++;
180         for (j = 0; j<WORD_BITS/4; j++)
181         {
182             if (mask & 15)
183             {
184                 if (mask & 1)
185                 {
186                     struct DFA_state *state = dfa->states[s];
187                     int i = state->tran_no;
188                     while (--i >= 0)
189                         set_bit (mc, Rdst, 0, state->trans[i].to);
190                 }
191                 if (mask & 2)
192                 {
193                     struct DFA_state *state = dfa->states[s+1];
194                     int i = state->tran_no;
195                     while (--i >= 0)
196                         set_bit (mc, Rdst, 0, state->trans[i].to);
197                 }
198                 if (mask & 4)
199                 {
200                     struct DFA_state *state = dfa->states[s+2];
201                     int i = state->tran_no;
202                     while (--i >= 0)
203                         set_bit (mc, Rdst, 0, state->trans[i].to);
204                 }
205                 if (mask & 8)
206                 {
207                     struct DFA_state *state = dfa->states[s+3];
208                     int i = state->tran_no;
209                     while (--i >= 0)
210                         set_bit (mc, Rdst, 0, state->trans[i].to);
211                 }
212             }
213             s += 4;
214             if (s >= dfa->no_states)
215                 return;
216             mask >>= 4;
217         }
218     }
219 }
220
221 static void or (MatchContext *mc, MatchWord *Rdst,
222                 MatchWord *Rsrc1, MatchWord *Rsrc2)
223 {
224     int i;
225     for (i = 0; i<mc->n; i++)
226         Rdst[i] = Rsrc1[i] | Rsrc2[i];
227 }
228
229
230 static int go (MatchContext *mc, struct DFA *dfa, FILE *inf)
231 {
232     MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
233     int s, d, ch;
234     int lineno = 1;
235     char *infbuf;
236     int inf_ptr = 1;
237     int no_match = 0;
238
239     infbuf = imalloc (INFBUF_SIZE);
240     infbuf[0] = '\n';
241     Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
242     Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
243     Rj_a = icalloc (mc->n * sizeof(*Rj));
244     Rj_b = icalloc (mc->n * sizeof(*Rj));
245     Rj_c = icalloc (mc->n * sizeof(*Rj));
246
247     set_bit (mc, Rj, 0, 0);
248     for (d = 1; d<=mc->range; d++)
249     {
250         int s;
251         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
252         for (s = 0; s<dfa->no_states; s++)
253         {
254             if (get_bit (mc, Rj, d-1, s))
255             {
256                 struct DFA_state *state = dfa->states[s];
257                 int i = state->tran_no;
258                 while (--i >= 0)
259                     set_bit (mc, Rj, d, state->trans[i].to);
260             }
261         }
262     }
263     while ((ch = getc (inf)) != EOF)
264     {
265         MatchWord *Rj_t;
266         
267         infbuf[inf_ptr] = ch;
268         if (ch == '\n')
269         {
270             if (no_match)
271             {
272                 int i = inf_ptr;
273                 if (show_line)
274                     printf ("%5d:", lineno);
275                 do
276                 {
277                     if (--i < 0)
278                         i = INFBUF_SIZE-1;
279                 } while (infbuf[i] != '\n');
280                 do
281                 {
282                     if (++i == INFBUF_SIZE)
283                         i = 0;
284                     putchar (infbuf[i]);
285                 } while (infbuf[i] != '\n');
286                 no_match = 0;
287             }
288             lineno++;
289         }
290         if (++inf_ptr == INFBUF_SIZE)
291             inf_ptr = 0;
292         mask_shift (mc, Rj1, Rj, dfa, ch);
293         for (d = 1; d <= mc->range; d++)
294         {
295             mask_shift (mc, Rj_b, Rj+d*mc->n, dfa, ch);    /* 1 */
296
297             or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
298
299             shift (mc, Rj_c, Rj_a, dfa);
300
301             or (mc, Rj_a, Rj_b, Rj_c);                      /* 1,2,3*/
302
303             or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n);     /* 1,2,3,4 */
304         }
305         for (s = 0; s<dfa->no_states; s++)
306         {
307             if (dfa->states[s]->rule_no)
308                 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
309                     no_match++;
310         }
311         for (d = 0; d <= mc->range; d++)
312             reset_bit (mc, Rj1+d*mc->n, 0, dfa->no_states);
313         Rj_t = Rj1;
314         Rj1 = Rj;
315         Rj = Rj_t;
316     }
317     ifree (Rj);
318     ifree (Rj1);
319     ifree (Rj_a);
320     ifree (Rj_b);
321     ifree (Rj_c);
322     ifree (infbuf);
323     return 0;
324 }
325
326 static int grep_file (struct DFA *dfa, const char *fname, int range)
327 {
328     FILE *inf;
329     MatchContext *mc;
330
331     if (fname)
332     {
333         inf = fopen (fname, "r");
334         if (!inf)
335         {
336             logf (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
337             exit (1);
338         }
339     }
340     else
341         inf = stdin;
342      
343     mc = mk_MatchContext (dfa, range);
344
345     go (mc, dfa, inf);
346
347     if (fname)
348         fclose (inf);
349     return 0;
350 }
351
352 int main (int argc, char **argv)
353 {
354     int ret;
355     int range = 0;
356     char *arg;
357     const char *pattern = NULL;
358     int no_files = 0;
359     struct DFA *dfa = dfa_init();
360
361     prog = argv[0];
362     while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
363     {
364         if (ret == 0)
365         {
366             if (!pattern)
367             {
368                 int i;
369                 pattern = arg;
370                 i = dfa_parse (dfa, &pattern);
371                 if (i || *pattern)
372                 {
373                     fprintf (stderr, "%s: illegal pattern\n", prog);
374                     return 1;
375                 }
376                 dfa_mkstate (dfa);
377             }
378             else
379             {
380                 no_files++;
381                 grep_file (dfa, arg, range);
382             }
383         }
384         else if (ret == 'v')
385         {
386             log_init (log_mask_str(arg), prog, NULL);
387         }
388         else if (ret == 's')
389         {
390             dfa_verbose = 1;
391         }
392         else if (ret == 'd')
393         {
394             debug_dfa_tran = 1;
395             debug_dfa_followpos = 1;
396             debug_dfa_trav = 1;
397         }
398         else if (ret == 'r')
399         {
400             range = atoi (arg);
401         }
402         else if (ret == 'n')
403         {
404             show_line = 1;
405         }
406         else
407         {
408             logf (LOG_FATAL, "Unknown option '-%s'", arg);
409             exit (1);
410         }
411     }
412     if (!pattern)
413     {
414         fprintf (stderr, "usage:\n "
415                  " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
416         exit (1);
417     }
418     else if (no_files == 0)
419     {
420         grep_file (dfa, NULL, range);
421     }
422     dfa_delete (&dfa);
423     return 0;
424 }