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