src/nfa.c

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