src/nfa.c

   1 /*  Copyright (C) 2006, Index Data ApS
   2  *  See the file LICENSE for details.
   3  *
   4  *  $Id: nfa.c,v 1.5 2006-05-04 18:58:54 adam Exp $
   5  */
   6
   7 /**
   8  * \file nfa.c
   9  * \brief NFA for character set normalizing
  10  *
  11  *  This is a simple NFA-based system for character set normalizing
  12  *  in yaz and zebra. Unlike standard NFA's, this operates on ranges of
  13  *  characters at a time, so as to keep the size small.
  14  *
  15  *  All characters are internally handled as unsigned 32-bit ints, so
  16  *  this works well with unicode. Translating to and from utf-8 is trivial, if
  17  *  need be.
  18  *
  19  *  The NFA stores a translation-thing in the terminal nodes. It does not
  20  *  concern itself with what that thing is, for us it is juts a void*
  21  *
  22  *  The module consists of two parts: Building the NFA, and translating
  23  *  strings with it.
  24  */
  25
  26 #include <stdio.h>
  27 #include <yaz/nfa.h>
  28 #include <yaz/nmem.h>
  29
  30 /* * * * * * * * * *
  31  * Data structures
  32  * * * * * * * * * */
  33
  34 typedef struct yaz_nfa_backref_info yaz_backref_info;
  35
  36 struct yaz_nfa_backref_info {
  37     yaz_nfa_char *start;
  38     yaz_nfa_char *end;
  39 };
  40
  41 struct yaz_nfa {
  42     NMEM nmem;
  43     int nstates;   /* how many states do we have */
  44     int nbackrefs;  /* how many backrefs do we have */
  45     yaz_nfa_state *laststate; /* points to the last in the circular list */
  46     yaz_nfa_state *firststate; /* the initial state */
  47     yaz_backref_info *curr_backrefs; /* the backrefs we are matching */
  48     yaz_backref_info *best_backrefs; /* backrefs of the best match so far*/
  49     int lastmatch; /* the result of last match */
  50 };
  51
  52 struct yaz_nfa_state {
  53     int num; /* state number. used for resoving ambiguities, and for dumping */
  54     void *result; /* signals a terminal state, and gives the result */
  55     yaz_nfa_transition *lasttrans; /* circular list of transitions */
  56     yaz_nfa_state *next; /* Circular linked list */
  57     int backref_start; /* which backreference starts here. 0 if none */
  58     int backref_end; /* which backreference ends here. 0 if none */
  59 } ;
  60
  61 struct yaz_nfa_transition {
  62       yaz_nfa_state *to_state;  /* where to */
  63       yaz_nfa_char range_start;
  64       yaz_nfa_char range_end;
  65       yaz_nfa_transition *next; /* a linked list of them */
  66 } ;
  67
  68 /* a range from 1 down to 0 is impossible, and is used to denote an */
  69 /* empty (epsilon) transition */
  70 #define EMPTY_START 1
  71 #define EMPTY_END   0
  72
  73 /* a limit for the number of empty transitions we can have in a row before */
  74 /* we declare this a loop */
  75 #define LOOP_LIMIT 100
  76
  77
  78
  79
  80 /* * * * * * *
  81  * Initializing and destroying whole nfa's
  82  * * * * * * */
  83
  84 yaz_nfa *yaz_nfa_init() {
  85     NMEM my_nmem = nmem_create();
  86     yaz_nfa *n = nmem_malloc(my_nmem, sizeof(yaz_nfa));
  87     n->nmem = my_nmem;
  88     n->nstates = 0;
  89     n->laststate = 0;
  90     n->firststate = 0;
  91     n->nbackrefs = 0;
  92     n->curr_backrefs = 0;
  93     n->best_backrefs = 0;
  94     n->lastmatch = YAZ_NFA_NOMATCH;
  95     return n;
  96 }
  97
  98 void yaz_nfa_destroy(yaz_nfa *n) {
  99     nmem_destroy(n->nmem);
 100 }
 101
 102
 103 /* * * * * *
 104  * Low-level interface to building the NFA
 105  * * * * * */
 106
 107 yaz_nfa_state *yaz_nfa_add_state(yaz_nfa *n) {
 108     yaz_nfa_state *s = nmem_malloc(n->nmem, sizeof(yaz_nfa_state));
 109     s->num = (n->nstates)++;
 110     s->result = 0;
 111     s->lasttrans = 0;
 112     s->backref_start = 0;
 113     s->backref_end = 0;
 114     if (n->laststate) {
 115         s->next = n->laststate->next;
 116         n->laststate->next = s;
 117         n->laststate = s;
 118     } else { /* first state */
 119         n->laststate = s;
 120         n->firststate = s;
 121         s->next = s;
 122     }
 123     return s;
 124 }
 125
 126 int yaz_nfa_set_result(yaz_nfa *n, yaz_nfa_state *s, void *result) {
 127     if ((s->result)&&result)
 128         return 1;
 129     s->result = result;
 130     return 0;
 131 }
 132
 133 void *yaz_nfa_get_result(yaz_nfa *n, yaz_nfa_state *s) {
 134     if (!s)
 135         return 0;
 136     return s->result;
 137 }
 138
 139 int yaz_nfa_set_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 140            int backref_number,
 141            int is_start ){
 142     if (is_start) {
 143         if (s->backref_start)
 144             return 1;
 145         s->backref_start = backref_number;
 146         if (n->nbackrefs<=backref_number) {
 147             n->nbackrefs = backref_number+1;
 148             n->curr_backrefs = 0;
 149             n->best_backrefs = 0;
 150             /* clear them just in case we have already matched on */
 151             /* with this nfa, and created a too small backref table */
 152             /* we will reallocate when matching. */
 153         }
 154     } else {
 155         if (s->backref_end)
 156             return 1;
 157         if (n->nbackrefs<backref_number)
 158             return 2; /* can't end a backref that has not been started */
 159         s->backref_end = backref_number;
 160     }
 161     return 0; /* ok */
 162 }
 163
 164 int yaz_nfa_get_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 165                 int is_start ) {
 166     if (!s)
 167         return 0;
 168     if (is_start)
 169         return s->backref_start;
 170     else
 171         return s->backref_end;
 172 }
 173
 174 void yaz_nfa_add_transition(yaz_nfa *n,
 175         yaz_nfa_state *from_state,
 176         yaz_nfa_state *to_state,
 177         yaz_nfa_char range_start,
 178         yaz_nfa_char range_end) {
 179     yaz_nfa_transition *t = nmem_malloc(n->nmem, sizeof(yaz_nfa_transition));
 180     t->range_start = range_start;
 181     t->range_end = range_end;
 182     t->to_state = to_state;
 183     if (from_state->lasttrans) {
 184         t->next= from_state->lasttrans->next;
 185         from_state->lasttrans->next = t;
 186         from_state->lasttrans = t;
 187     } else { /* first trans */
 188         from_state->lasttrans = t;
 189         t->next = t;
 190     }
 191 }
 192
 193 void yaz_nfa_add_empty_transition( yaz_nfa *n,
 194         yaz_nfa_state *from_state,
 195         yaz_nfa_state *to_state) {
 196     yaz_nfa_add_transition(n, from_state, to_state,
 197               EMPTY_START, EMPTY_END);
 198 }
 199
 200 /* * * * * * * *
 201  * Medium-level interface
 202  * * * * * * * */
 203
 204 /* Finds a transition from s where the range is exactly c..c */
 205 /* There should only be one such transition */
 206 static yaz_nfa_state *find_single_trans(
 207           yaz_nfa_state *s,
 208           yaz_nfa_char range_start,
 209           yaz_nfa_char range_end) {
 210     yaz_nfa_transition *t = s->lasttrans;
 211     if (!t)
 212         return 0;
 213     do {
 214         t = t->next;
 215         if ( ( t->range_start == range_start ) && ( t->range_end == range_end) )
 216             return t->to_state;
 217     } while (t != s->lasttrans );
 218     return 0;
 219 }
 220
 221
 222 yaz_nfa_state *yaz_nfa_add_range(yaz_nfa *n,
 223         yaz_nfa_state *s,
 224         yaz_nfa_char range_start,
 225         yaz_nfa_char range_end) {
 226     yaz_nfa_state *nextstate;
 227     if (!s) /* default to top-level of the nfa */
 228         s = n->firststate;
 229     nextstate = find_single_trans(s, range_start, range_end);
 230     if (!nextstate) {
 231         nextstate = yaz_nfa_add_state(n);
 232         yaz_nfa_add_transition(n, s, nextstate, range_start, range_end);
 233     }
 234     return nextstate;
 235 }
 236
 237 yaz_nfa_state *yaz_nfa_add_sequence(yaz_nfa *n,
 238         yaz_nfa_state *s,
 239         yaz_nfa_char *seq ){
 240     yaz_nfa_state *nextstate;
 241     if (!s) /* default to top-level of the nfa */
 242         s = n->firststate;
 243     nextstate = find_single_trans(s, *seq, *seq);
 244     if (nextstate) {
 245         seq++;
 246         if (!*seq) /* whole sequence matched */
 247             return nextstate;
 248         else
 249             return yaz_nfa_add_sequence(n, nextstate, seq);
 250     } else { /* no next state, build the rest */
 251         while (*seq) {
 252             s = yaz_nfa_add_range(n, s, *seq, *seq);
 253             seq++;
 254         }
 255         return s;
 256     }
 257     return 0; /* compiler shut up, we return somewhere above */
 258 }
 259
 260
 261
 262 /* * * * * * *
 263  * Searching the NFA
 264  * * * * * * */
 265
 266 struct matcher {
 267     yaz_nfa *n;
 268     yaz_nfa_char *longest;
 269     int bestnode;
 270     void *result;
 271     int errorcode;
 272     int empties; /* count how many consecutive empty transitions */
 273 };
 274
 275 /* Finds the longest match. In case of ties, chooses the one with the
 276  * lowest numbered state. Keep track of the back references. Recursively
 277  * traverses the NFA. Keeps track of the best hit it has found. */
 278
 279 static void match_state(
 280               yaz_nfa_state *s,
 281               yaz_nfa_char *inchar,
 282               size_t incharsleft,
 283               struct matcher *m ) {
 284     yaz_nfa_transition *t = s->lasttrans;
 285     if (s->backref_start)
 286         m->n->curr_backrefs[s->backref_start].start = inchar;
 287     if (s->backref_end)
 288         m->n->curr_backrefs[s->backref_end].end = inchar;
 289     if (t) {
 290         if (incharsleft) {
 291             do {
 292                 t = t->next;
 293                 if ( (( t->range_start <= *inchar ) && ( t->range_end >= *inchar )) ){
 294                     m->empties = 0;
 295                     if (t->range_start!=t->range_end){
 296                         /* backref 0 is special: the last range operation */
 297                         m->n->curr_backrefs[0].start = inchar;
 298                         m->n->curr_backrefs[0].end = inchar;
 299                     }
 300                     match_state(t->to_state, inchar+1, incharsleft-1, m);
 301                     /* yes, descent to all matching nodes, even if overrun, */
 302                     /* since we can find a better one later */
 303                 } else if (( t->range_start==EMPTY_START) && (t->range_end==EMPTY_END)) {
 304                     if ( m->empties++ > LOOP_LIMIT )
 305                         m->errorcode= YAZ_NFA_LOOP;
 306                     else
 307                         match_state(t->to_state, inchar, incharsleft, m);
 308                 }
 309             } while (t != s->lasttrans );
 310         } else {
 311             m->errorcode = YAZ_NFA_OVERRUN;
 312         }
 313     }
 314     if (s->result) { /* terminal node */
 315         if ( (m->longest < inchar) ||  /* longer result */
 316              ((m->longest == inchar)&&(m->bestnode<s->num)) ){
 317               /* or as long, but with lower node number. Still better */
 318            int i;
 319            m->longest = inchar;
 320            m->bestnode = s->num;
 321            m->result = s->result;
 322            if (m->n->curr_backrefs)
 323                for (i = 0; i<m->n->nbackrefs; i++)  {
 324                    m->n->best_backrefs[i]=m->n->curr_backrefs[i];
 325                }
 326         }
 327     }
 328     if (s->backref_start)
 329         m->n->curr_backrefs[s->backref_start].start = 0;
 330     if (s->backref_end)
 331         m->n->curr_backrefs[s->backref_end].end = 0;
 332     m->n->curr_backrefs[0].start = 0;
 333     m->n->curr_backrefs[0].end = 0;
 334 } /* match_state */
 335
 336 int yaz_nfa_match(yaz_nfa *n,
 337            yaz_nfa_char **inbuff,
 338            size_t incharsleft,
 339            void **result ){
 340     struct matcher m;
 341     int sz;
 342     int i;
 343     if (!n->firststate) {
 344         n->lastmatch = YAZ_NFA_NOMATCH;
 345         return n->lastmatch;
 346     }
 347     m.n = n;
 348     m.longest=*inbuff;
 349     m.bestnode = n->nstates;
 350     m.result = 0;
 351     m.errorcode = 0;
 352     sz = sizeof( struct yaz_nfa_backref_info) * n->nbackrefs;
 353     if (!n->curr_backrefs) {
 354         n->curr_backrefs = nmem_malloc( n->nmem, sz);
 355         n->best_backrefs = nmem_malloc( n->nmem, sz);
 356     }
 357     for (i = 0; i<n->nbackrefs; i++) {
 358         n->curr_backrefs[i].start = 0;
 359         n->curr_backrefs[i].end = 0;
 360         n->best_backrefs[i].start = 0;
 361         n->best_backrefs[i].end = 0;
 362     }
 363
 364     match_state(n->firststate, *inbuff, incharsleft, &m);
 365     if (m.result) {
 366         *result = m.result;
 367         *inbuff = m.longest;
 368         if (m.errorcode)
 369             n->lastmatch = m.errorcode;
 370         else
 371             n->lastmatch= YAZ_NFA_SUCCESS;
 372         return n->lastmatch;
 373     }
 374     n->lastmatch = YAZ_NFA_NOMATCH;
 375     return n->lastmatch;
 376 }
 377
 378
 379 int yaz_nfa_get_backref( yaz_nfa *n,
 380                 int backref_no,
 381                 yaz_nfa_char **start,
 382                 yaz_nfa_char **end) {
 383     if (backref_no>=n->nbackrefs)
 384         return 2;
 385     if (backref_no<0)
 386         return 2;
 387     if (n->lastmatch== YAZ_NFA_NOMATCH)
 388         return 1;  /* accept other errors, they return partial matches*/
 389
 390     *start = n->best_backrefs[backref_no].start;
 391     *end = n->best_backrefs[backref_no].end;
 392     return 0;
 393 }
 394
 395
 396 /* * * * * * * * *
 397  * Debug routines
 398  * * * * * * */
 399
 400 yaz_nfa_state *yaz_nfa_get_first(yaz_nfa *n){
 401     if (!n)
 402         return 0;
 403     return n->firststate;
 404 }
 405
 406 yaz_nfa_state *yaz_nfa_get_next(yaz_nfa *n, yaz_nfa_state *s){
 407     if (n && s) {
 408         if (s==n->laststate)
 409             return 0;
 410         return s->next;
 411     }
 412     return 0;
 413 }
 414
 415
 416 static void dump_trans(FILE *F, yaz_nfa_transition *t ) {
 417     char c1;
 418     char c2;
 419     char *e;
 420     c1 = t->range_start;
 421     c2 = t->range_end;
 422     e = "";
 423     if ( (t->range_start <= ' ') || (t->range_start>'z'))
 424         c1 = '?';
 425     if ( (t->range_end <= ' ') || (t->range_end>'z'))
 426         c2 = '?';
 427     if ((t->range_start==EMPTY_START) && (t->range_end==EMPTY_END)) {
 428         e = "(empty)";
 429     }
 430     fprintf(F, "    -> [%d]  %s '%c' %x - '%c' %x \n",
 431             t->to_state->num, e,
 432             c1, t->range_start,
 433             c2, t->range_end );
 434 }
 435
 436 static void dump_state(FILE *F, yaz_nfa_state *s,
 437             char *(*strfunc)(void *) ) {
 438     yaz_nfa_transition *t;
 439     char *resultstring = "";
 440     if (s->result) {
 441         if (strfunc)  {
 442             resultstring = (*strfunc)(s->result);
 443         }
 444         else
 445             resultstring = s->result;
 446     }
 447     fprintf(F, "  state [%d] %s %s",
 448             s->num, s->result?"(FINAL)":"", resultstring );
 449     if (s->backref_start) {
 450         fprintf(F, " start-%d", s->backref_start);
 451     }
 452     if (s->backref_end) {
 453         fprintf(F, " end-%d", s->backref_end);
 454     }
 455     fprintf(F, "\n");
 456     t = s->lasttrans;
 457     if (!t) {
 458         fprintf(F, "    (no transitions)\n");
 459     } else {
 460         do {
 461             t = t->next;
 462             dump_trans(F, t);
 463         } while (t != s->lasttrans);
 464     }
 465
 466 }
 467
 468 void yaz_nfa_dump(FILE *F, yaz_nfa *n,
 469             char *(*strfunc)(void *) ) {
 470     yaz_nfa_state *s;
 471     if (!F)   /* lazy programmers can just pass 0 for F */
 472         F = stdout;
 473     fprintf(F, "The NFA has %d states and %d backrefs\n",
 474             n->nstates, n->nbackrefs);
 475     s = n->laststate;
 476     if (s) {
 477         do {
 478             s = s->next;
 479             dump_state(F, s, strfunc);
 480         } while (s != n->laststate);
 481     }
 482 }
 483
 484
 485 /*
 486  * Local variables:
 487  * c-basic-offset: 4
 488  * indent-tabs-mode: nil
 489  * End:
 490  * vim: shiftwidth=4 tabstop=8 expandtab
 491  */