First code bits of record retrieval code
[yaz-moved-to-github.git] / 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  */