src/nfa.c

   1 /*  Copyright (C) 2006, Index Data ApS
   2  *  See the file LICENSE for details.
   3  *
   4  *  $Id: nfa.c,v 1.1 2006-05-03 09:04:33 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     return n;
  85 }
  86
  87 void yaz_nfa_destroy(yaz_nfa *n) {
  88     nmem_destroy(n->nmem);
  89 }
  90
  91
  92 /* * * * * *
  93  * Low-level interface to building the NFA
  94  * * * * * */
  95
  96 yaz_nfa_state *yaz_nfa_add_state(yaz_nfa *n) {
  97     yaz_nfa_state *s = nmem_malloc(n->nmem,sizeof(yaz_nfa_state));
  98     s->num = (n->nstates)++;
  99     s->result=0;
 100     s->lasttrans=0;
 101     s->backref_start=0;
 102     s->backref_end=0;
 103     if (n->laststate) {
 104         s->next=n->laststate->next;
 105         n->laststate->next=s;
 106         n->laststate=s;
 107     } else { /* first state */
 108         n->laststate=s;
 109         n->firststate=s;
 110         s->next=s;
 111     }
 112     return s;
 113 }
 114
 115 int yaz_nfa_set_result(yaz_nfa *n, yaz_nfa_state *s,void *result) {
 116     if ((s->result)&&result)
 117         return 1;
 118     s->result=result;
 119     return 0;
 120 }
 121
 122 void *yaz_nfa_get_result(yaz_nfa *n, yaz_nfa_state *s) {
 123     if (!s)
 124         return 0;
 125     return s->result;
 126 }
 127
 128 int yaz_nfa_set_backref(yaz_nfa *n, yaz_nfa_state *s,
 129            int backref_number,
 130            int is_start ){
 131     if (is_start) {
 132         if (s->backref_start)
 133             return 1;
 134         s->backref_start=backref_number;
 135         if (n->nbackrefs<backref_number)
 136             n->nbackrefs=backref_number;
 137     } else {
 138         if (s->backref_end)
 139             return 1;
 140         s->backref_end=backref_number;
 141     }
 142     return 0; /* ok */
 143 }
 144
 145 int yaz_nfa_get_backref(yaz_nfa *n, yaz_nfa_state *s,
 146                 int is_start ) {
 147     if (!s)
 148         return 0;
 149     if (is_start)
 150         return s->backref_start;
 151     else
 152         return s->backref_end;
 153 }
 154
 155 void yaz_nfa_add_transition(yaz_nfa *n,
 156         yaz_nfa_state *from_state,
 157         yaz_nfa_state *to_state,
 158         yaz_nfa_char range_start,
 159         yaz_nfa_char range_end) {
 160     yaz_nfa_transition *t=nmem_malloc(n->nmem,sizeof(yaz_nfa_transition));
 161     t->range_start=range_start;
 162     t->range_end=range_end;
 163     t->to_state=to_state;
 164     if (from_state->lasttrans) {
 165         t->next= from_state->lasttrans->next;
 166         from_state->lasttrans->next=t;
 167         from_state->lasttrans=t;
 168     } else { /* first trans */
 169         from_state->lasttrans=t;
 170         t->next=t;
 171     }
 172 }
 173
 174 void yaz_nfa_add_empty_transition( yaz_nfa *n,
 175         yaz_nfa_state *from_state,
 176         yaz_nfa_state *to_state) {
 177     yaz_nfa_add_transition(n,from_state,to_state,
 178               EMPTY_START,EMPTY_END);
 179 }
 180
 181 /* * * * * * * *
 182  * Medium-level interface
 183  * * * * * * * */
 184
 185 /* Finds a transition from s where the range is exactly c..c */
 186 /* There should only be one such transition */
 187 static yaz_nfa_state *find_single_trans(
 188           yaz_nfa_state *s,
 189           yaz_nfa_char range_start,
 190           yaz_nfa_char range_end) {
 191     yaz_nfa_transition *t=s->lasttrans;
 192     if (!t)
 193         return 0;
 194     do {
 195         t=t->next;
 196         if ( ( t->range_start == range_start ) && ( t->range_end == range_end) )
 197             return t->to_state;
 198     } while (t != s->lasttrans );
 199     return 0;
 200 }
 201
 202
 203 yaz_nfa_state *yaz_nfa_add_range(yaz_nfa *n,
 204         yaz_nfa_state *s,
 205         yaz_nfa_char range_start,
 206         yaz_nfa_char range_end) {
 207     yaz_nfa_state *nextstate;
 208     if (!s) /* default to top-level of the nfa */
 209         s=n->firststate;
 210     nextstate=find_single_trans(s,range_start,range_end);
 211     if (!nextstate) {
 212         nextstate = yaz_nfa_add_state(n);
 213         yaz_nfa_add_transition(n, s, nextstate, range_start, range_end);
 214     }
 215     return nextstate;
 216 }
 217
 218 yaz_nfa_state *yaz_nfa_add_sequence(yaz_nfa *n,
 219         yaz_nfa_state *s,
 220         yaz_nfa_char *seq ){
 221     yaz_nfa_state *nextstate;
 222     if (!s) /* default to top-level of the nfa */
 223         s=n->firststate;
 224     nextstate=find_single_trans(s,*seq,*seq);
 225     if (nextstate) {
 226         seq++;
 227         if (!*seq) /* whole sequence matched */
 228             return nextstate;
 229         else
 230             return yaz_nfa_add_sequence(n, nextstate, seq);
 231     } else { /* no next state, build the rest */
 232         while (*seq) {
 233             s=yaz_nfa_add_range(n,s, *seq, *seq);
 234             seq++;
 235         }
 236         return s;
 237     }
 238     return 0; /* compiler shut up, we return somewhere above */
 239 }
 240
 241
 242
 243 /* * * * * * *
 244  * Searching the NFA
 245  * * * * * * */
 246
 247 struct matcher {
 248     yaz_nfa_char *longest;
 249     int bestnode;
 250     void *result;
 251     int errorcode;
 252     int empties; /* count how many consecutive empty transitions */
 253 };
 254
 255 /* Finds the longest match. In case of ties, chooses the one with the
 256  * lowest numbered state */
 257 static void match_state(yaz_nfa_state *s,
 258               yaz_nfa_char *inchar,
 259               size_t incharsleft,
 260               struct matcher *m ) {
 261     yaz_nfa_transition *t=s->lasttrans;
 262
 263     if (t) {
 264         if (incharsleft) {
 265             do {
 266                 t=t->next;
 267                 if ( (( t->range_start <= *inchar ) && ( t->range_end >= *inchar )) ){
 268                     m->empties=0;
 269                     match_state(t->to_state, inchar+1,incharsleft-1,m);
 270                     /* yes, descent to all matching nodes, even if overrun, */
 271                     /* since we can find a better one later */
 272                 } else if (( t->range_start==EMPTY_START) && (t->range_end==EMPTY_END)) {
 273                     if ( m->empties++ > LOOP_LIMIT )
 274                         m->errorcode= YAZ_NFA_LOOP;
 275                     else
 276                         match_state(t->to_state, inchar,incharsleft,m);
 277                 }
 278             } while (t != s->lasttrans );
 279         } else {
 280             m->errorcode=YAZ_NFA_OVERRUN;
 281         }
 282     }
 283     if (s->result) { /* terminal node */
 284         if ( (m->longest < inchar) ||  /* longer result */
 285              ((m->longest == inchar)&&(m->bestnode<s->num)) ){
 286               /* or as long, but with lower node number. Still better */
 287            m->longest=inchar;
 288            m->bestnode=s->num;
 289            m->result=s->result;
 290         }
 291     }
 292 } /* match_state */
 293
 294 int yaz_nfa_match(yaz_nfa *n,
 295            yaz_nfa_char **inbuff,
 296            size_t incharsleft,
 297            void **result ){
 298     struct matcher m;
 299     if (!n->firststate)
 300         return YAZ_NFA_NOMATCH;
 301     m.longest=*inbuff;
 302     m.bestnode=n->nstates;
 303     m.result=0;
 304     m.errorcode=0;
 305     if (!n->curr_backrefs) {
 306         int sz=sizeof( struct yaz_nfa_backref_info);
 307         n->curr_backrefs=nmem_malloc( n->nmem, n->nbackrefs* sz);
 308         n->best_backrefs=nmem_malloc( n->nmem, n->nbackrefs* sz);
 309     }
 310
 311
 312     match_state(n->firststate, *inbuff, incharsleft, &m);
 313     if (m.result) {
 314         *result=m.result;
 315         *inbuff=m.longest;
 316         if (m.errorcode)
 317             return m.errorcode;
 318         else
 319             return YAZ_NFA_SUCCESS;
 320     }
 321     return YAZ_NFA_NOMATCH;
 322 }
 323
 324
 325
 326
 327 /* * * * * * * * *
 328  * Debug routines
 329  * * * * * * */
 330
 331 yaz_nfa_state *yaz_nfa_get_first(yaz_nfa *n){
 332     if (!n)
 333         return 0;
 334     return n->firststate;
 335 }
 336
 337 yaz_nfa_state *yaz_nfa_get_next(yaz_nfa *n, yaz_nfa_state *s){
 338     if (n && s) {
 339         if (s==n->laststate)
 340             return 0;
 341         return s->next;
 342     }
 343     return 0;
 344 }
 345
 346
 347 static void dump_trans(FILE *F, yaz_nfa_transition *t ) {
 348     char c1;
 349     char c2;
 350     c1=t->range_start;
 351     c2=t->range_end;
 352     char *e="";
 353     if ( (t->range_start <= ' ') || (t->range_start>'z'))
 354         c1='?';
 355     if ( (t->range_end <= ' ') || (t->range_end>'z'))
 356         c2='?';
 357     if ((t->range_start==EMPTY_START) && (t->range_end==EMPTY_END)) {
 358         e="(empty)";
 359     }
 360     fprintf(F,"    -> [%d]  %s '%c' %x - '%c' %x \n",
 361             t->to_state->num, e,
 362             c1, t->range_start,
 363             c2, t->range_end );
 364 }
 365
 366 static void dump_state(FILE *F, yaz_nfa_state *s,
 367             char *(*strfunc)(void *) ) {
 368     yaz_nfa_transition *t;
 369     char *resultstring="";
 370     if (s->result) {
 371         if (strfunc)  {
 372             resultstring=(*strfunc)(s->result);
 373         }
 374         else
 375             resultstring=s->result;
 376     }
 377     fprintf(F,"  state [%d] %s %s",
 378             s->num, s->result?"(FINAL)":"",resultstring );
 379     if (s->backref_start) {
 380         fprintf(F," start-%d",s->backref_start);
 381     }
 382     if (s->backref_end) {
 383         fprintf(F," end-%d",s->backref_end);
 384     }
 385     fprintf(F,"\n");
 386     t=s->lasttrans;
 387     if (!t) {
 388         fprintf(F,"    (no transitions)\n");
 389     } else {
 390         do {
 391             t=t->next;
 392             dump_trans(F,t);
 393         } while (t != s->lasttrans);
 394     }
 395
 396 }
 397
 398 void yaz_nfa_dump(FILE *F, yaz_nfa *n,
 399             char *(*strfunc)(void *) ) {
 400     yaz_nfa_state *s;
 401     if (!F)   /* lazy programmers can just pass 0 for F */
 402         F=stdout;
 403     fprintf(F,"The NFA has %d states \n",n->nstates);
 404     s=n->laststate;
 405     if (s) {
 406         do {
 407             s=s->next;
 408             dump_state(F,s, strfunc);
 409         } while (s != n->laststate);
 410     }
 411 }
 412
 413
 414
 415 /*
 416  * Local variables:
 417  * c-basic-offset: 4
 418  * indent-tabs-mode: nil
 419  * End:
 420  * vim: shiftwidth=4 tabstop=8 expandtab
 421  */