dfa/grepper.c

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