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