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