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 }