dict/lookgrep.c

   1 /*
   2  * Copyright (C) 1994-1998, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: lookgrep.c,v $
   7  * Revision 1.21  1998-06-24 12:16:12  adam
   8  * Support for relations on text operands. Open range support in
   9  * DFA module (i.e. [-j], [g-]).
  10  *
  11  * Revision 1.20  1997/10/27 14:33:03  adam
  12  * Moved towards generic character mapping depending on "structure"
  13  * field in abstract syntax file. Fixed a few memory leaks. Fixed
  14  * bug with negative integers when doing searches with relational
  15  * operators.
  16  *
  17  * Revision 1.19  1997/09/18 08:59:18  adam
  18  * Extra generic handle for the character mapping routines.
  19  *
  20  * Revision 1.18  1997/09/05 15:29:58  adam
  21  * Changed prototype for chr_map_input - added const.
  22  * Added support for C++, headers uses extern "C" for public definitions.
  23  *
  24  * Revision 1.17  1996/06/04 10:20:06  adam
  25  * Added support for character mapping.
  26  *
  27  * Revision 1.16  1996/05/24  14:46:04  adam
  28  * Added dict_grep_cmap function to define user-mapping in grep lookups.
  29  *
  30  * Revision 1.15  1996/03/20  09:35:18  adam
  31  * Function dict_lookup_grep got extra parameter, init_pos, which marks
  32  * from which position in pattern approximate pattern matching should occur.
  33  *
  34  * Revision 1.14  1996/02/02  13:43:51  adam
  35  * The public functions simply use char instead of Dict_char to represent
  36  * search strings. Dict_char is used internally only.
  37  *
  38  * Revision 1.13  1996/01/08  09:09:30  adam
  39  * Function dfa_parse got 'const' string argument.
  40  *
  41  * Revision 1.12  1995/12/11  09:04:48  adam
  42  * Bug fix: the lookup/scan/lookgrep didn't handle empty dictionary.
  43  *
  44  * Revision 1.11  1995/12/06  14:43:02  adam
  45  * New function: dict_delete.
  46  *
  47  * Revision 1.10  1995/11/16  17:00:44  adam
  48  * Changed stupid log.
  49  *
  50  * Revision 1.9  1995/10/27  13:58:09  adam
  51  * Makes 'Database unavailable' diagnostic.
  52  *
  53  * Revision 1.8  1995/10/19  14:57:21  adam
  54  * New feature: grep lookup saves length of longest prefix match.
  55  *
  56  * Revision 1.7  1995/10/17  18:01:22  adam
  57  * Userfunc may return non-zero in which case the the grepping stops
  58  * immediately.
  59  *
  60  * Revision 1.6  1995/10/09  16:18:32  adam
  61  * Function dict_lookup_grep got extra client data parameter.
  62  *
  63  * Revision 1.5  1995/09/14  11:52:59  adam
  64  * Grep handle function parameter info is const now.
  65  *
  66  * Revision 1.4  1995/01/24  16:01:02  adam
  67  * Added -ansi to CFLAGS.
  68  * Use new API of dfa module.
  69  *
  70  * Revision 1.3  1994/10/05  12:16:50  adam
  71  * Pagesize is a resource now.
  72  *
  73  * Revision 1.2  1994/10/04  12:08:07  adam
  74  * Some bug fixes and some optimizations.
  75  *
  76  * Revision 1.1  1994/10/03  17:23:04  adam
  77  * First version of dictionary lookup with regular expressions and errors.
  78  *
  79  */
  80
  81 #include <stdlib.h>
  82 #include <string.h>
  83 #include <stdio.h>
  84 #include <assert.h>
  85
  86 #include <dfa.h>
  87 #include <dict.h>
  88
  89 typedef unsigned MatchWord;
  90 #define WORD_BITS 32
  91 #define MAX_LENGTH 1024
  92
  93 typedef struct {
  94   int n;                 /* no of MatchWord needed */
  95   int range;             /* max no. of errors */
  96   int fact;              /* (range+1)*n */
  97   MatchWord *match_mask; /* match_mask */
  98 } MatchContext;
  99
 100 #define INLINE
 101
 102 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
 103 {
 104     int off = state & (WORD_BITS-1);
 105     int wno = state / WORD_BITS;
 106
 107     m[mc->n * ch + wno] |= 1<<off;
 108 }
 109
 110 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
 111                                  int state)
 112 {
 113     int off = state & (WORD_BITS-1);
 114     int wno = state / WORD_BITS;
 115
 116     return m[mc->n * ch + wno] & (1<<off);
 117 }
 118
 119 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
 120 {
 121     MatchContext *mc = xmalloc (sizeof(*mc));
 122     int s;
 123
 124     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
 125     mc->range = range;
 126     mc->fact = (range+1)*mc->n;
 127     mc->match_mask = xcalloc (mc->n, sizeof(*mc->match_mask));
 128
 129     for (s = 0; s<dfa->no_states; s++)
 130         if (dfa->states[s]->rule_no)
 131             set_bit (mc, mc->match_mask, 0, s);
 132     return mc;
 133 }
 134
 135 static void rm_MatchContext (MatchContext **mc)
 136 {
 137     xfree ((*mc)->match_mask);
 138     xfree (*mc);
 139     *mc = NULL;
 140 }
 141
 142 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 143                    struct DFA *dfa, int ch)
 144 {
 145     int j, s = 0;
 146     MatchWord *Rsrc_p = Rsrc, mask;
 147
 148     for (j = 0; j<mc->n; j++)
 149         Rdst[j] = 0;
 150     while (1)
 151     {
 152         mask = *Rsrc_p++;
 153         for (j = 0; j<WORD_BITS/4; j++)
 154         {
 155             if (mask & 15)
 156             {
 157                 if (mask & 1)
 158                 {
 159                     struct DFA_state *state = dfa->states[s];
 160                     int i = state->tran_no;
 161                     while (--i >= 0)
 162                         if (ch >= state->trans[i].ch[0] &&
 163                             ch <= state->trans[i].ch[1])
 164                             set_bit (mc, Rdst, 0, state->trans[i].to);
 165                 }
 166                 if (mask & 2)
 167                 {
 168                     struct DFA_state *state = dfa->states[s+1];
 169                     int i = state->tran_no;
 170                     while (--i >= 0)
 171                         if (ch >= state->trans[i].ch[0] &&
 172                             ch <= state->trans[i].ch[1])
 173                             set_bit (mc, Rdst, 0, state->trans[i].to);
 174                 }
 175                 if (mask & 4)
 176                 {
 177                     struct DFA_state *state = dfa->states[s+2];
 178                     int i = state->tran_no;
 179                     while (--i >= 0)
 180                         if (ch >= state->trans[i].ch[0] &&
 181                             ch <= state->trans[i].ch[1])
 182                             set_bit (mc, Rdst, 0, state->trans[i].to);
 183                 }
 184                 if (mask & 8)
 185                 {
 186                     struct DFA_state *state = dfa->states[s+3];
 187                     int i = state->tran_no;
 188                     while (--i >= 0)
 189                         if (ch >= state->trans[i].ch[0] &&
 190                             ch <= state->trans[i].ch[1])
 191                             set_bit (mc, Rdst, 0, state->trans[i].to);
 192                 }
 193             }
 194             s += 4;
 195             if (s >= dfa->no_states)
 196                 return;
 197             mask >>= 4;
 198         }
 199     }
 200 }
 201
 202 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 203                    struct DFA *dfa)
 204 {
 205     int j, s = 0;
 206     MatchWord *Rsrc_p = Rsrc, mask;
 207     for (j = 0; j<mc->n; j++)
 208         Rdst[j] = 0;
 209     while (1)
 210     {
 211         mask = *Rsrc_p++;
 212         for (j = 0; j<WORD_BITS/4; j++)
 213         {
 214             if (mask & 15)
 215             {
 216                 if (mask & 1)
 217                 {
 218                     struct DFA_state *state = dfa->states[s];
 219                     int i = state->tran_no;
 220                     while (--i >= 0)
 221                         set_bit (mc, Rdst, 0, state->trans[i].to);
 222                 }
 223                 if (mask & 2)
 224                 {
 225                     struct DFA_state *state = dfa->states[s+1];
 226                     int i = state->tran_no;
 227                     while (--i >= 0)
 228                         set_bit (mc, Rdst, 0, state->trans[i].to);
 229                 }
 230                 if (mask & 4)
 231                 {
 232                     struct DFA_state *state = dfa->states[s+2];
 233                     int i = state->tran_no;
 234                     while (--i >= 0)
 235                         set_bit (mc, Rdst, 0, state->trans[i].to);
 236                 }
 237                 if (mask & 8)
 238                 {
 239                     struct DFA_state *state = dfa->states[s+3];
 240                     int i = state->tran_no;
 241                     while (--i >= 0)
 242                         set_bit (mc, Rdst, 0, state->trans[i].to);
 243                 }
 244             }
 245             s += 4;
 246             if (s >= dfa->no_states)
 247                 return;
 248             mask >>= 4;
 249         }
 250     }
 251 }
 252
 253 static void or (MatchContext *mc, MatchWord *Rdst,
 254                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 255 {
 256     int i;
 257     for (i = 0; i<mc->n; i++)
 258         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 259 }
 260
 261 static INLINE int move (MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
 262                         Dict_char ch, struct DFA *dfa, MatchWord *Rtmp,
 263                         int range)
 264 {
 265     int d;
 266     MatchWord *Rtmp_2 = Rtmp + mc->n;
 267
 268     mask_shift (mc, Rj1, Rj, dfa, ch);
 269     for (d = 1; d <= mc->range; d++)
 270     {
 271         or (mc, Rtmp, Rj, Rj1);                         /* 2,3 */
 272
 273         shift (mc, Rtmp_2, Rtmp, dfa);
 274
 275         mask_shift (mc, Rtmp, Rj+mc->n, dfa, ch);      /* 1 */
 276
 277         or (mc, Rtmp, Rtmp_2, Rtmp);                    /* 1,2,3*/
 278
 279         Rj1 += mc->n;
 280
 281         or (mc, Rj1, Rtmp, Rj);                         /* 1,2,3,4 */
 282
 283         Rj += mc->n;
 284     }
 285     return 1;
 286
 287 }
 288
 289
 290 static int dict_grep (Dict dict, Dict_ptr ptr, MatchContext *mc,
 291                       MatchWord *Rj, int pos, void *client,
 292                       int (*userfunc)(char *, const char *, void *),
 293                       Dict_char *prefix, struct DFA *dfa,
 294                       int *max_pos, int init_pos)
 295 {
 296     int lo, hi, d;
 297     void *p;
 298     short *indxp;
 299     char *info;
 300
 301     dict_bf_readp (dict->dbf, ptr, &p);
 302     lo = 0;
 303     hi = DICT_nodir(p)-1;
 304     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
 305
 306     while (lo <= hi)
 307     {
 308         if (indxp[-lo] > 0)
 309         {
 310             /* string (Dict_char *) DICT_EOS terminated */
 311             /* unsigned char        length of information */
 312             /* char *               information */
 313             int j;
 314             int was_match = 0;
 315             info = (char*)p + indxp[-lo];
 316             for (j=0; ; j++)
 317             {
 318                 Dict_char ch;
 319                 MatchWord *Rj0 =    Rj + j    *mc->fact;
 320                 MatchWord *Rj1 =    Rj + (j+1)*mc->fact;
 321                 MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
 322                 int range;
 323
 324                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
 325                 prefix[pos+j] = ch;
 326                 if (pos+j > *max_pos)
 327                     *max_pos = pos+j;
 328                 if (ch == DICT_EOS)
 329                 {
 330                     if (was_match)
 331                         if ((*userfunc)((char*) prefix,
 332                                         info+(j+1)*sizeof(Dict_char), client))
 333                             return 1;
 334                     break;
 335                 }
 336                 if (pos+j >= init_pos)
 337                     range = mc->range;
 338                 else
 339                     range = 0;
 340                 move (mc, Rj1, Rj0, ch, dfa, Rj_tmp, range);
 341                 for (d = mc->n; --d >= 0; )
 342                     if (Rj1[range*mc->n + d])
 343                         break;
 344                 if (d < 0)
 345                     break;
 346                 was_match = 0;
 347                 for (d = mc->n; --d >= 0; )
 348                     if (Rj1[range*mc->n + d] & mc->match_mask[d])
 349                     {
 350                         was_match = 1;
 351                         break;
 352                     }
 353             }
 354         }
 355         else
 356         {
 357             MatchWord *Rj1 =    Rj+  mc->fact;
 358             MatchWord *Rj_tmp = Rj+2*mc->fact;
 359             Dict_char ch;
 360             int range;
 361
 362             /* Dict_ptr             subptr */
 363             /* Dict_char            sub char */
 364             /* unsigned char        length of information */
 365             /* char *               information */
 366             info = (char*)p - indxp[-lo];
 367             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
 368             prefix[pos] = ch;
 369
 370             if (pos > *max_pos)
 371                 *max_pos = pos;
 372             if (pos >= init_pos)
 373                 range = mc->range;
 374             else
 375                 range = 0;
 376             move (mc, Rj1, Rj, ch, dfa, Rj_tmp, range);
 377             for (d = mc->n; --d >= 0; )
 378                 if (Rj1[range*mc->n + d])
 379                     break;
 380             if (d >= 0)
 381             {
 382                 Dict_ptr subptr;
 383                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 384                 {
 385                     for (d = mc->n; --d >= 0; )
 386                         if (Rj1[range*mc->n + d] & mc->match_mask[d])
 387                         {
 388                             prefix[pos+1] = DICT_EOS;
 389                             if ((*userfunc)((char*) prefix,
 390                                             info+sizeof(Dict_ptr)+
 391                                             sizeof(Dict_char), client))
 392                                 return 1;
 393                             break;
 394                         }
 395                 }
 396                 memcpy (&subptr, info, sizeof(Dict_ptr));
 397                 if (subptr)
 398                 {
 399                     if (dict_grep (dict, subptr, mc, Rj1, pos+1,
 400                                    client, userfunc, prefix, dfa, max_pos,
 401                                    init_pos))
 402                         return 1;
 403                     dict_bf_readp (dict->dbf, ptr, &p);
 404                     indxp = (short*) ((char*) p+DICT_pagesize(dict)
 405                                       -sizeof(short));
 406                 }
 407             }
 408         }
 409         lo++;
 410     }
 411     return 0;
 412 }
 413
 414 int dict_lookup_grep (Dict dict, const char *pattern, int range, void *client,
 415                       int *max_pos, int init_pos,
 416                       int (*userfunc)(char *name, const char *info,
 417                                       void *client))
 418 {
 419     MatchWord *Rj;
 420     Dict_char prefix[MAX_LENGTH+1];
 421     const char *this_pattern = pattern;
 422     MatchContext *mc;
 423     struct DFA *dfa = dfa_init();
 424     int i, d;
 425
 426 #if 0
 427     debug_dfa_trav = 1;
 428     debug_dfa_tran = 1;
 429     debug_dfa_followpos = 1;
 430     dfa_verbose = 1;
 431 #endif
 432
 433     logf (LOG_DEBUG, "dict_lookup_grep range=%d", range);
 434     for (i = 0; pattern[i]; i++)
 435     {
 436         logf (LOG_DEBUG, " %3d  %c", pattern[i],
 437               (pattern[i] > ' ' && pattern[i] < 127) ? pattern[i] : '?');
 438     }
 439
 440     dfa_set_cmap (dfa, dict->grep_cmap_data, dict->grep_cmap);
 441
 442     i = dfa_parse (dfa, &this_pattern);
 443     if (i || *this_pattern)
 444     {
 445         dfa_delete (&dfa);
 446         return -1;
 447     }
 448     dfa_mkstate (dfa);
 449
 450     mc = mk_MatchContext (dfa, range);
 451
 452     Rj = xcalloc ((MAX_LENGTH+1) * mc->n, sizeof(*Rj));
 453
 454     set_bit (mc, Rj, 0, 0);
 455     for (d = 1; d<=mc->range; d++)
 456     {
 457         int s;
 458         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 459         for (s = 0; s<dfa->no_states; s++)
 460         {
 461             if (get_bit (mc, Rj, d-1, s))
 462             {
 463                 struct DFA_state *state = dfa->states[s];
 464                 int i = state->tran_no;
 465                 while (--i >= 0)
 466                     set_bit (mc, Rj, d, state->trans[i].to);
 467             }
 468         }
 469     }
 470     *max_pos = 0;
 471     if (dict->head.last > 1)
 472         i = dict_grep (dict, 1, mc, Rj, 0, client, userfunc, prefix,
 473                        dfa, max_pos, init_pos);
 474     else
 475         i = 0;
 476     logf (LOG_DEBUG, "max_pos = %d", *max_pos);
 477     dfa_delete (&dfa);
 478     xfree (Rj);
 479     rm_MatchContext (&mc);
 480     return i;
 481 }
 482
 483 void dict_grep_cmap (Dict dict, void *vp,
 484                      const char **(*cmap)(void *vp, const char **from, int len))
 485 {
 486     dict->grep_cmap = cmap;
 487     dict->grep_cmap_data = vp;
 488 }