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