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