src/nfa.c

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