dfa/grepper.c

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