Happy new year
[idzebra-moved-to-github.git] / dict / lookgrep.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2009 Index Data
3
4 Zebra is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20
21
22 #include <stdlib.h>
23 #include <string.h>
24 #include <stdio.h>
25 #include <assert.h>
26
27 #include <dfa.h>
28 #include "dict-p.h"
29
30 typedef unsigned MatchWord;
31 #define WORD_BITS 32
32 #define MAX_LENGTH 1024
33
34 /* This code is based 
35  * Sun Wu and Udi Manber: Fast Text Searching Allowing Errors.
36  *      Communications of the ACM, pp. 83-91, Vol. 35, No. 10, Oct. 1992, USA.
37  *      PostScript version of the paper in its submitted form: agrep1.ps)
38  *      recommended reading to understand AGREP ! 
39  *
40  * http://www.tgries.de/agrep/#AGREP1PS
41  * http://www.tgries.de/agrep/doc/agrep1ps.zip
42  */
43
44 typedef struct {
45   int n;                 /* no of MatchWord needed */
46   int range;             /* max no. of errors */
47   int fact;              /* (range+1)*n */
48   MatchWord *match_mask; /* match_mask */
49 } MatchContext;
50
51 #define INLINE 
52
53 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
54 {
55     int off = state & (WORD_BITS-1);
56     int wno = state / WORD_BITS;
57   
58     m[mc->n * ch + wno] |= 1<<off;
59 }
60
61 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
62                                  int state)
63 {
64     int off = state & (WORD_BITS-1);
65     int wno = state / WORD_BITS;
66
67     return m[mc->n * ch + wno] & (1<<off);
68 }
69
70 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
71 {
72     MatchContext *mc = (MatchContext *) xmalloc (sizeof(*mc));
73     int s;
74
75     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
76     mc->range = range;
77     mc->fact = (range+1)*mc->n;
78     mc->match_mask = (MatchWord *) xcalloc (mc->n, sizeof(*mc->match_mask));
79
80     for (s = 0; s<dfa->no_states; s++)
81         if (dfa->states[s]->rule_no)
82             set_bit (mc, mc->match_mask, 0, s);
83     return mc;
84 }
85
86 static void rm_MatchContext (MatchContext **mc)
87 {
88     xfree ((*mc)->match_mask);
89     xfree (*mc);
90     *mc = NULL;
91 }
92
93 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
94                    struct DFA *dfa, int ch)
95 {
96     int j, s = 0;
97     MatchWord *Rsrc_p = Rsrc, mask;
98
99     for (j = 0; j<mc->n; j++)
100         Rdst[j] = 0;
101     while (1)
102     {
103         mask = *Rsrc_p++;
104         for (j = 0; j<WORD_BITS/4; j++)
105         {
106             if (mask & 15)
107             {
108                 if (mask & 1)
109                 {
110                     struct DFA_state *state = dfa->states[s];
111                     int i = state->tran_no;
112                     while (--i >= 0)
113                         if (ch >= state->trans[i].ch[0] &&
114                             ch <= state->trans[i].ch[1])
115                             set_bit (mc, Rdst, 0, state->trans[i].to);
116                 }
117                 if (mask & 2)
118                 {
119                     struct DFA_state *state = dfa->states[s+1];
120                     int i = state->tran_no;
121                     while (--i >= 0)
122                         if (ch >= state->trans[i].ch[0] &&
123                             ch <= state->trans[i].ch[1])
124                             set_bit (mc, Rdst, 0, state->trans[i].to);
125                 }
126                 if (mask & 4)
127                 {
128                     struct DFA_state *state = dfa->states[s+2];
129                     int i = state->tran_no;
130                     while (--i >= 0)
131                         if (ch >= state->trans[i].ch[0] &&
132                             ch <= state->trans[i].ch[1])
133                             set_bit (mc, Rdst, 0, state->trans[i].to);
134                 }
135                 if (mask & 8)
136                 {
137                     struct DFA_state *state = dfa->states[s+3];
138                     int i = state->tran_no;
139                     while (--i >= 0)
140                         if (ch >= state->trans[i].ch[0] &&
141                             ch <= state->trans[i].ch[1])
142                             set_bit (mc, Rdst, 0, state->trans[i].to);
143                 }
144             }
145             s += 4;
146             if (s >= dfa->no_states)
147                 return;
148             mask >>= 4;
149         }
150     }
151 }
152
153 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
154                    struct DFA *dfa)
155 {
156     int j, s = 0;
157     MatchWord *Rsrc_p = Rsrc, mask;
158     for (j = 0; j<mc->n; j++)
159         Rdst[j] = 0;
160     while (1)
161     {
162         mask = *Rsrc_p++;
163         for (j = 0; j<WORD_BITS/4; j++)
164         {
165             if (mask & 15)
166             {
167                 if (mask & 1)
168                 {
169                     struct DFA_state *state = dfa->states[s];
170                     int i = state->tran_no;
171                     while (--i >= 0)
172                         set_bit (mc, Rdst, 0, state->trans[i].to);
173                 }
174                 if (mask & 2)
175                 {
176                     struct DFA_state *state = dfa->states[s+1];
177                     int i = state->tran_no;
178                     while (--i >= 0)
179                         set_bit (mc, Rdst, 0, state->trans[i].to);
180                 }
181                 if (mask & 4)
182                 {
183                     struct DFA_state *state = dfa->states[s+2];
184                     int i = state->tran_no;
185                     while (--i >= 0)
186                         set_bit (mc, Rdst, 0, state->trans[i].to);
187                 }
188                 if (mask & 8)
189                 {
190                     struct DFA_state *state = dfa->states[s+3];
191                     int i = state->tran_no;
192                     while (--i >= 0)
193                         set_bit (mc, Rdst, 0, state->trans[i].to);
194                 }
195             }
196             s += 4;
197             if (s >= dfa->no_states)
198                 return;
199             mask >>= 4;
200         }
201     }
202 }
203
204 static void or (MatchContext *mc, MatchWord *Rdst,
205                 MatchWord *Rsrc1, MatchWord *Rsrc2)
206 {
207     int i;
208     for (i = 0; i<mc->n; i++)
209         Rdst[i] = Rsrc1[i] | Rsrc2[i];
210 }
211
212 static INLINE int move (MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
213                         Dict_char ch, struct DFA *dfa, MatchWord *Rtmp,
214                         int range)
215 {
216     int d;
217     MatchWord *Rtmp_2 = Rtmp + mc->n;
218
219     mask_shift (mc, Rj1, Rj, dfa, ch);
220     for (d = 1; d <= mc->range; d++)
221     {
222         or (mc, Rtmp, Rj, Rj1);                         /* 2,3 */
223         
224         shift (mc, Rtmp_2, Rtmp, dfa);
225
226         mask_shift (mc, Rtmp, Rj+mc->n, dfa, ch);       /* 1 */
227                 
228         or (mc, Rtmp, Rtmp_2, Rtmp);                    /* 1,2,3*/
229
230         Rj1 += mc->n;
231         
232         or (mc, Rj1, Rtmp, Rj);                         /* 1,2,3,4 */
233
234         Rj += mc->n;
235     }
236     return 1;
237
238 }
239
240
241 static int grep(Dict dict, Dict_ptr ptr, MatchContext *mc,
242                 MatchWord *Rj, int pos, void *client,
243                 int (*userfunc)(char *, const char *, void *),
244                 Dict_char *prefix, struct DFA *dfa,
245                 int *max_pos, int init_pos)
246 {
247     int lo, hi, d;
248     void *p;
249     short *indxp;
250     char *info;
251
252     dict_bf_readp (dict->dbf, ptr, &p);
253     lo = 0;
254     hi = DICT_nodir(p)-1;
255     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
256
257     while (lo <= hi)
258     {
259         if (indxp[-lo] > 0)
260         {
261             /* string (Dict_char *) DICT_EOS terminated */
262             /* unsigned char        length of information */
263             /* char *               information */
264             int j;
265             int was_match = 0;
266             info = (char*)p + indxp[-lo];
267             for (j=0; ; j++)
268             {
269                 Dict_char ch;
270                 MatchWord *Rj0 =    Rj + j    *mc->fact;
271                 MatchWord *Rj1 =    Rj + (j+1)*mc->fact;
272                 MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
273                 int range;
274
275                 memcpy(&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
276                 prefix[pos+j] = ch;
277                 if (pos+j > *max_pos)
278                     *max_pos = pos+j;
279                 if (ch == DICT_EOS)
280                 {
281                     if (was_match)
282                     {
283                         int ret = userfunc((char*) prefix, 
284                                        info+(j+1)*sizeof(Dict_char), client);
285                         if (ret)
286                             return ret;
287                     }
288                     break;
289                 }
290                 if (pos+j >= init_pos)
291                     range = mc->range;
292                 else
293                     range = 0;
294                 move (mc, Rj1, Rj0, ch, dfa, Rj_tmp, range);
295                 for (d = mc->n; --d >= 0; )
296                     if (Rj1[range*mc->n + d])
297                         break;
298                 if (d < 0)
299                     break;
300                 was_match = 0;
301                 for (d = mc->n; --d >= 0; )
302                     if (Rj1[range*mc->n + d] & mc->match_mask[d])
303                     {
304                         was_match = 1;
305                         break;
306                     }
307             }
308         }
309         else
310         {
311             MatchWord *Rj1 =    Rj+  mc->fact;
312             MatchWord *Rj_tmp = Rj+2*mc->fact;
313             Dict_char ch;
314             int range;
315
316             /* Dict_ptr             subptr */
317             /* Dict_char            sub char */
318             /* unsigned char        length of information */
319             /* char *               information */
320             info = (char*)p - indxp[-lo];
321             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
322             prefix[pos] = ch;
323             
324             if (pos > *max_pos)
325                 *max_pos = pos;
326             if (pos >= init_pos)
327                 range = mc->range;
328             else
329                 range = 0;
330             move (mc, Rj1, Rj, ch, dfa, Rj_tmp, range);
331             for (d = mc->n; --d >= 0; )
332                 if (Rj1[range*mc->n + d])
333                     break;
334             if (d >= 0)
335             {
336                 Dict_ptr subptr;
337                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
338                 {
339                     for (d = mc->n; --d >= 0; )
340                         if (Rj1[range*mc->n + d] & mc->match_mask[d])
341                         {
342                             int ret;
343                             prefix[pos+1] = DICT_EOS;
344                             ret = userfunc((char*) prefix,
345                                            info+sizeof(Dict_ptr)+
346                                            sizeof(Dict_char), client);
347                             if (ret)
348                                 return ret;
349                             break;
350                         }
351                 }
352                 memcpy (&subptr, info, sizeof(Dict_ptr));
353                 if (subptr)
354                 {
355                     int ret = grep(dict, subptr, mc, Rj1, pos+1,
356                                    client, userfunc, prefix, dfa, max_pos,
357                                    init_pos);
358                     if (ret)
359                         return ret;
360
361                     dict_bf_readp (dict->dbf, ptr, &p);
362                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
363                 }
364             }
365         }
366         lo++;
367     }
368     return 0;
369 }
370
371 int dict_lookup_grep(Dict dict, const char *pattern, int range, void *client,
372                      int *max_pos, int init_pos,
373                      int (*userfunc)(char *name, const char *info,
374                                      void *client))
375 {
376     MatchWord *Rj;
377     Dict_char prefix[MAX_LENGTH+1];
378     const char *this_pattern = pattern;
379     MatchContext *mc;
380     struct DFA *dfa = dfa_init();
381     int i, d, ret = 0;
382
383 #if 0
384     debug_dfa_trav = 1;
385     debug_dfa_tran = 1;
386     debug_dfa_followpos = 1;
387     dfa_verbose = 1;
388 #endif
389
390     dfa_anyset_includes_nl(dfa);
391
392     yaz_log(YLOG_DEBUG, "dict_lookup_grep range=%d", range);
393     for (i = 0; pattern[i]; i++)
394     {
395         yaz_log(YLOG_DEBUG, " %2d %3d  %c", i, pattern[i],
396               (pattern[i] > ' ' && pattern[i] < 127) ? pattern[i] : '?');
397     }
398    
399     dfa_set_cmap (dfa, dict->grep_cmap_data, dict->grep_cmap);
400
401     i = dfa_parse (dfa, &this_pattern);
402     if (i || *this_pattern)
403     {
404         yaz_log(YLOG_WARN, "dfa_parse fail=%d", i);
405         dfa_delete (&dfa);
406         return -1;
407     }
408     dfa_mkstate (dfa);
409
410     mc = mk_MatchContext (dfa, range);
411
412     Rj = (MatchWord *) xcalloc((MAX_LENGTH+1) * mc->n, sizeof(*Rj));
413
414     set_bit (mc, Rj, 0, 0);
415     for (d = 1; d<=mc->range; d++)
416     {
417         int s;
418         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
419         for (s = 0; s < dfa->no_states; s++)
420         {
421             if (get_bit (mc, Rj, d-1, s))
422             {
423                 struct DFA_state *state = dfa->states[s];
424                 int i = state->tran_no;
425                 while (--i >= 0)
426                     set_bit (mc, Rj, d, state->trans[i].to);
427             }
428         }
429     }
430     *max_pos = 0;
431     if (dict->head.root)
432         ret = grep(dict, dict->head.root, mc, Rj, 0, client,
433                    userfunc, prefix,
434                    dfa, max_pos, init_pos);
435     yaz_log(YLOG_DEBUG, "max_pos = %d", *max_pos);
436     dfa_delete(&dfa);
437     xfree(Rj);
438     rm_MatchContext (&mc);
439     return ret;
440 }
441
442 void dict_grep_cmap (Dict dict, void *vp,
443                      const char **(*cmap)(void *vp, const char **from, int len))
444 {
445     dict->grep_cmap = cmap;
446     dict->grep_cmap_data = vp;
447 }
448 /*
449  * Local variables:
450  * c-basic-offset: 4
451  * indent-tabs-mode: nil
452  * End:
453  * vim: shiftwidth=4 tabstop=8 expandtab
454  */
455