src/nfa.c

   1 /*  Copyright (C) 2006, Index Data ApS
   2  *  See the file LICENSE for details.
   3  *
   4  *  $Id: nfa.c,v 1.6 2006-05-05 09:14:42 heikki 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 typedef enum {
  79     conv_none,
  80     conv_string,
  81     conv_backref
  82 } yaz_nfa_converter_type;
  83
  84 struct yaz_nfa_converter {
  85     yaz_nfa_converter *next;
  86     yaz_nfa_converter_type type;
  87     yaz_nfa_char *string;
  88     size_t strlen;
  89     int backref_no;
  90     int char_diff;
  91 };
  92
  93
  94 /* * * * * * *
  95  * Initializing and destroying whole nfa's
  96  * * * * * * */
  97
  98 yaz_nfa *yaz_nfa_init() {
  99     NMEM my_nmem = nmem_create();
 100     yaz_nfa *n = nmem_malloc(my_nmem, sizeof(yaz_nfa));
 101     n->nmem = my_nmem;
 102     n->nstates = 0;
 103     n->laststate = 0;
 104     n->firststate = 0;
 105     n->nbackrefs = 0;
 106     n->curr_backrefs = 0;
 107     n->best_backrefs = 0;
 108     n->lastmatch = YAZ_NFA_NOMATCH;
 109     return n;
 110 }
 111
 112 void yaz_nfa_destroy(yaz_nfa *n) {
 113     nmem_destroy(n->nmem);
 114 }
 115
 116
 117 /* * * * * *
 118  * Low-level interface to building the NFA
 119  * * * * * */
 120
 121 yaz_nfa_state *yaz_nfa_add_state(yaz_nfa *n) {
 122     yaz_nfa_state *s = nmem_malloc(n->nmem, sizeof(yaz_nfa_state));
 123     s->num = (n->nstates)++;
 124     s->result = 0;
 125     s->lasttrans = 0;
 126     s->backref_start = 0;
 127     s->backref_end = 0;
 128     if (n->laststate) {
 129         s->next = n->laststate->next;
 130         n->laststate->next = s;
 131         n->laststate = s;
 132     } else { /* first state */
 133         n->laststate = s;
 134         n->firststate = s;
 135         s->next = s;
 136     }
 137     return s;
 138 }
 139
 140 int yaz_nfa_set_result(yaz_nfa *n, yaz_nfa_state *s, void *result) {
 141     if ((s->result)&&result)
 142         return 1;
 143     s->result = result;
 144     return 0;
 145 }
 146
 147 void *yaz_nfa_get_result(yaz_nfa *n, yaz_nfa_state *s) {
 148     if (!s)
 149         return 0;
 150     return s->result;
 151 }
 152
 153 int yaz_nfa_set_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 154            int backref_number,
 155            int is_start ){
 156     if (is_start) {
 157         if (s->backref_start)
 158             return 1;
 159         s->backref_start = backref_number;
 160         if (n->nbackrefs<=backref_number) {
 161             n->nbackrefs = backref_number+1;
 162             n->curr_backrefs = 0;
 163             n->best_backrefs = 0;
 164             /* clear them just in case we have already matched on */
 165             /* with this nfa, and created a too small backref table */
 166             /* we will reallocate when matching. */
 167         }
 168     } else {
 169         if (s->backref_end)
 170             return 1;
 171         if (n->nbackrefs<backref_number)
 172             return 2; /* can't end a backref that has not been started */
 173         s->backref_end = backref_number;
 174     }
 175     return 0; /* ok */
 176 }
 177
 178 int yaz_nfa_get_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 179                 int is_start ) {
 180     if (!s)
 181         return 0;
 182     if (is_start)
 183         return s->backref_start;
 184     else
 185         return s->backref_end;
 186 }
 187
 188 void yaz_nfa_add_transition(yaz_nfa *n,
 189         yaz_nfa_state *from_state,
 190         yaz_nfa_state *to_state,
 191         yaz_nfa_char range_start,
 192         yaz_nfa_char range_end) {
 193     yaz_nfa_transition *t = nmem_malloc(n->nmem, sizeof(yaz_nfa_transition));
 194     if (!from_state)
 195         from_state = n->firststate;
 196     t->range_start = range_start;
 197     t->range_end = range_end;
 198     t->to_state = to_state;
 199     if (from_state->lasttrans) {
 200         t->next= from_state->lasttrans->next;
 201         from_state->lasttrans->next = t;
 202         from_state->lasttrans = t;
 203     } else { /* first trans */
 204         from_state->lasttrans = t;
 205         t->next = t;
 206     }
 207 }
 208
 209 void yaz_nfa_add_empty_transition( yaz_nfa *n,
 210         yaz_nfa_state *from_state,
 211         yaz_nfa_state *to_state) {
 212     yaz_nfa_add_transition(n, from_state, to_state,
 213               EMPTY_START, EMPTY_END);
 214 }
 215
 216 /* * * * * * * *
 217  * Medium-level interface
 218  * * * * * * * */
 219
 220 /* Finds a transition from s where the range is exactly c..c */
 221 /* There should only be one such transition */
 222 static yaz_nfa_state *find_single_trans(
 223           yaz_nfa_state *s,
 224           yaz_nfa_char range_start,
 225           yaz_nfa_char range_end) {
 226     yaz_nfa_transition *t = s->lasttrans;
 227     if (!t)
 228         return 0;
 229     do {
 230         t = t->next;
 231         if ( ( t->range_start == range_start ) && ( t->range_end == range_end) )
 232             return t->to_state;
 233     } while (t != s->lasttrans );
 234     return 0;
 235 }
 236
 237
 238 yaz_nfa_state *yaz_nfa_add_range(yaz_nfa *n,
 239         yaz_nfa_state *s,
 240         yaz_nfa_char range_start,
 241         yaz_nfa_char range_end) {
 242     yaz_nfa_state *nextstate;
 243     if (!s) /* default to top-level of the nfa */
 244         s = n->firststate;
 245     nextstate = find_single_trans(s, range_start, range_end);
 246     if (!nextstate) {
 247         nextstate = yaz_nfa_add_state(n);
 248         yaz_nfa_add_transition(n, s, nextstate, range_start, range_end);
 249     }
 250     return nextstate;
 251 }
 252
 253 yaz_nfa_state *yaz_nfa_add_sequence(yaz_nfa *n,
 254         yaz_nfa_state *s,
 255         yaz_nfa_char *seq ){
 256     yaz_nfa_state *nextstate;
 257     if (!s) /* default to top-level of the nfa */
 258         s = n->firststate;
 259     nextstate = find_single_trans(s, *seq, *seq);
 260     if (nextstate) {
 261         seq++;
 262         if (!*seq) /* whole sequence matched */
 263             return nextstate;
 264         else
 265             return yaz_nfa_add_sequence(n, nextstate, seq);
 266     } else { /* no next state, build the rest */
 267         while (*seq) {
 268             s = yaz_nfa_add_range(n, s, *seq, *seq);
 269             seq++;
 270         }
 271         return s;
 272     }
 273     return 0; /* compiler shut up, we return somewhere above */
 274 }
 275
 276
 277
 278 /* * * * * * *
 279  * Searching the NFA
 280  * * * * * * */
 281
 282 struct matcher {
 283     yaz_nfa *n;
 284     yaz_nfa_char *longest;
 285     int bestnode;
 286     void *result;
 287     int errorcode;
 288     int empties; /* count how many consecutive empty transitions */
 289 };
 290
 291 /* Finds the longest match. In case of ties, chooses the one with the
 292  * lowest numbered state. Keep track of the back references. Recursively
 293  * traverses the NFA. Keeps track of the best hit it has found. */
 294
 295 static void match_state(
 296               yaz_nfa_state *s,
 297               yaz_nfa_char *inchar,
 298               size_t incharsleft,
 299               struct matcher *m ) {
 300     yaz_nfa_transition *t = s->lasttrans;
 301     if (s->backref_start)
 302         m->n->curr_backrefs[s->backref_start].start = inchar;
 303     if (s->backref_end)
 304         m->n->curr_backrefs[s->backref_end].end = inchar;
 305     if (t) {
 306         if (incharsleft) {
 307             do {
 308                 t = t->next;
 309                 if ( (( t->range_start <= *inchar ) && ( t->range_end >= *inchar )) ){
 310                     m->empties = 0;
 311                     if (t->range_start!=t->range_end){
 312                         /* backref 0 is special: the last range operation */
 313                         m->n->curr_backrefs[0].start = inchar;
 314                         m->n->curr_backrefs[0].end = inchar;
 315                     }
 316                     match_state(t->to_state, inchar+1, incharsleft-1, m);
 317                     /* yes, descent to all matching nodes, even if overrun, */
 318                     /* since we can find a better one later */
 319                 } else if (( t->range_start==EMPTY_START) && (t->range_end==EMPTY_END)) {
 320                     if ( m->empties++ > LOOP_LIMIT )
 321                         m->errorcode= YAZ_NFA_LOOP;
 322                     else
 323                         match_state(t->to_state, inchar, incharsleft, m);
 324                 }
 325             } while (t != s->lasttrans );
 326         } else {
 327             m->errorcode = YAZ_NFA_OVERRUN;
 328         }
 329     }
 330     if (s->result) { /* terminal node */
 331         if ( (m->longest < inchar) ||  /* longer result */
 332              ((m->longest == inchar)&&(m->bestnode<s->num)) ){
 333               /* or as long, but with lower node number. Still better */
 334            int i;
 335            m->longest = inchar;
 336            m->bestnode = s->num;
 337            m->result = s->result;
 338            if (m->n->curr_backrefs)
 339                for (i = 0; i<m->n->nbackrefs; i++)  {
 340                    m->n->best_backrefs[i]=m->n->curr_backrefs[i];
 341                }
 342         }
 343     }
 344     if (s->backref_start)
 345         m->n->curr_backrefs[s->backref_start].start = 0;
 346     if (s->backref_end)
 347         m->n->curr_backrefs[s->backref_end].end = 0;
 348     m->n->curr_backrefs[0].start = 0;
 349     m->n->curr_backrefs[0].end = 0;
 350 } /* match_state */
 351
 352 int yaz_nfa_match(yaz_nfa *n,
 353            yaz_nfa_char **inbuff,
 354            size_t *incharsleft,
 355            void **result ){
 356     struct matcher m;
 357     int sz;
 358     int i;
 359     if (!n->firststate) {
 360         n->lastmatch = YAZ_NFA_NOMATCH;
 361         return n->lastmatch;
 362     }
 363     m.n = n;
 364     m.longest=*inbuff;
 365     m.bestnode = n->nstates;
 366     m.result = 0;
 367     m.errorcode = 0;
 368     m.empties = 0;
 369     sz = sizeof( struct yaz_nfa_backref_info) * n->nbackrefs;
 370     if (!n->curr_backrefs) {
 371         n->curr_backrefs = nmem_malloc( n->nmem, sz);
 372         n->best_backrefs = nmem_malloc( n->nmem, sz);
 373     }
 374     for (i = 0; i<n->nbackrefs; i++) {
 375         n->curr_backrefs[i].start = 0;
 376         n->curr_backrefs[i].end = 0;
 377         n->best_backrefs[i].start = 0;
 378         n->best_backrefs[i].end = 0;
 379     }
 380
 381     match_state(n->firststate, *inbuff, *incharsleft, &m);
 382     if (m.result) {
 383         *incharsleft -= (m.longest-*inbuff);
 384         *result = m.result;
 385         *inbuff = m.longest;
 386         if (m.errorcode)
 387             n->lastmatch = m.errorcode;
 388         else
 389             n->lastmatch= YAZ_NFA_SUCCESS;
 390         return n->lastmatch;
 391     }
 392     n->lastmatch = YAZ_NFA_NOMATCH;
 393     return n->lastmatch;
 394 }
 395
 396
 397 int yaz_nfa_get_backref( yaz_nfa *n,
 398                 int backref_no,
 399                 yaz_nfa_char **start,
 400                 yaz_nfa_char **end) {
 401     if (backref_no>=n->nbackrefs)
 402         return 2;
 403     if (backref_no<0)
 404         return 2;
 405     if (n->lastmatch== YAZ_NFA_NOMATCH)
 406         return 1;  /* accept other errors, they return partial matches*/
 407
 408     *start = n->best_backrefs[backref_no].start;
 409     *end = n->best_backrefs[backref_no].end;
 410     return 0;
 411 }
 412
 413 /* * * * * * * * * * * * * *
 414  * Converters
 415  * * * * * * * * * * * * * */
 416
 417 static yaz_nfa_converter *create_null_converter ( yaz_nfa *n) {
 418     yaz_nfa_converter *c;
 419     c=nmem_malloc(n->nmem, sizeof(yaz_nfa_converter));
 420     c->next=0;
 421     c->type=conv_none;
 422     c->string=0;
 423     c->strlen=0;
 424     c->backref_no=0;
 425     c->char_diff=0;
 426     return c;
 427 }
 428
 429 yaz_nfa_converter *yaz_nfa_create_string_converter (
 430                 yaz_nfa *n,
 431                 yaz_nfa_char *string,
 432                 size_t length){
 433     yaz_nfa_converter *c;
 434     int i;
 435     c=create_null_converter(n);
 436     c->type=conv_string;
 437     c->string=nmem_malloc(n->nmem, length*sizeof(yaz_nfa_char));
 438     for (i=0;i<length;i++)
 439         c->string[i]=string[i];
 440     c->strlen=length;
 441     return c;
 442 }
 443
 444 yaz_nfa_converter *yaz_nfa_create_backref_converter (
 445                    yaz_nfa *n, int backref_no ) {
 446     yaz_nfa_converter *c;
 447     c=create_null_converter(n);
 448     c->type=conv_backref;
 449     c->backref_no=backref_no;
 450     return c;
 451 }
 452
 453
 454 void yaz_nfa_append_converter (
 455                 yaz_nfa *n,
 456                 yaz_nfa_converter *startpoint,
 457                 yaz_nfa_converter *newconverter) {
 458     while (startpoint->next)
 459         startpoint=startpoint->next;
 460     startpoint->next=newconverter;
 461 }
 462
 463 static int string_convert (
 464                 yaz_nfa *n,
 465                 yaz_nfa_converter *c,
 466                 yaz_nfa_char **outbuff,
 467                 size_t *outcharsleft){
 468     size_t sz=c->strlen;
 469     yaz_nfa_char *p=c->string;
 470     while (sz--) {
 471         if ((*outcharsleft)-- <= 0)
 472             return 2;
 473         **outbuff=*p++;
 474         (*outbuff)++;
 475     }
 476     return 0;
 477 }
 478 static int backref_convert (
 479                 yaz_nfa *n,
 480                 yaz_nfa_converter *c,
 481                 yaz_nfa_char **outbuff,
 482                 size_t *outcharsleft){
 483     yaz_nfa_char *cp1,*cp2;
 484     int i;
 485     i=yaz_nfa_get_backref(n,c->backref_no, &cp1, &cp2);
 486     if (i==2) /* no backref, produce no output, that's ok */
 487         return 0;
 488     if (i==1) /* no match in dfa */
 489         return 1; /* should not happen */
 490     while (cp2>cp1) {
 491         if ((*outcharsleft)-- <= 0)
 492             return 2;
 493         **outbuff=*cp1++;
 494         (*outbuff)++;
 495     }
 496     return 0;
 497 }
 498
 499
 500 int yaz_nfa_run_converters(
 501                 yaz_nfa *n,
 502                 yaz_nfa_converter *c,
 503                 yaz_nfa_char **outbuff,
 504                 size_t *outcharsleft){
 505     int rc=0;
 506     // yaz_nfa_char *bufstart=*outbuff;
 507     while (c && !rc) {
 508         switch(c->type) {
 509             case conv_string:
 510                 rc=string_convert(n,c,outbuff,outcharsleft);
 511                 break;
 512             case conv_backref:
 513                 rc=backref_convert(n,c,outbuff,outcharsleft);
 514                 break;
 515             default:
 516                 rc=3; /* internal error */
 517         }
 518         c=c->next;
 519     }
 520     return rc;
 521 }
 522
 523 /* * * * * * * * *
 524  * Debug routines
 525  * * * * * * */
 526
 527 yaz_nfa_state *yaz_nfa_get_first(yaz_nfa *n){
 528     if (!n)
 529         return 0;
 530     return n->firststate;
 531 }
 532
 533 yaz_nfa_state *yaz_nfa_get_next(yaz_nfa *n, yaz_nfa_state *s){
 534     if (n && s) {
 535         if (s==n->laststate)
 536             return 0;
 537         return s->next;
 538     }
 539     return 0;
 540 }
 541
 542
 543 static void dump_trans(FILE *F, yaz_nfa_transition *t ) {
 544     char c1;
 545     char c2;
 546     char *e;
 547     c1 = t->range_start;
 548     c2 = t->range_end;
 549     e = "";
 550     if ( (t->range_start <= ' ') || (t->range_start>'z'))
 551         c1 = '?';
 552     if ( (t->range_end <= ' ') || (t->range_end>'z'))
 553         c2 = '?';
 554     if ((t->range_start==EMPTY_START) && (t->range_end==EMPTY_END)) {
 555         e = "(empty)";
 556     }
 557     fprintf(F, "    -> [%d]  %s '%c' %x - '%c' %x \n",
 558             t->to_state->num, e,
 559             c1, t->range_start,
 560             c2, t->range_end );
 561 }
 562
 563 static void dump_state(FILE *F, yaz_nfa_state *s,
 564             char *(*strfunc)(void *) ) {
 565     yaz_nfa_transition *t;
 566     char *resultstring = "";
 567     if (s->result) {
 568         if (strfunc)  {
 569             resultstring = (*strfunc)(s->result);
 570         }
 571         else
 572             resultstring = s->result;
 573     }
 574     fprintf(F, "  state [%d] %s %s",
 575             s->num, s->result?"(FINAL)":"", resultstring );
 576     if (s->backref_start) {
 577         fprintf(F, " start-%d", s->backref_start);
 578     }
 579     if (s->backref_end) {
 580         fprintf(F, " end-%d", s->backref_end);
 581     }
 582     fprintf(F, "\n");
 583     t = s->lasttrans;
 584     if (!t) {
 585         fprintf(F, "    (no transitions)\n");
 586     } else {
 587         do {
 588             t = t->next;
 589             dump_trans(F, t);
 590         } while (t != s->lasttrans);
 591     }
 592
 593 }
 594
 595 void yaz_nfa_dump(FILE *F, yaz_nfa *n,
 596             char *(*strfunc)(void *) ) {
 597     yaz_nfa_state *s;
 598     if (!F)   /* lazy programmers can just pass 0 for F */
 599         F = stdout;
 600     fprintf(F, "The NFA has %d states and %d backrefs\n",
 601             n->nstates, n->nbackrefs);
 602     s = n->laststate;
 603     if (s) {
 604         do {
 605             s = s->next;
 606             dump_state(F, s, strfunc);
 607         } while (s != n->laststate);
 608     }
 609 }
 610
 611
 612 /*
 613  * Local variables:
 614  * c-basic-offset: 4
 615  * indent-tabs-mode: nil
 616  * End:
 617  * vim: shiftwidth=4 tabstop=8 expandtab
 618  */