Fixed bug #1114: scan within set may use excessive CPU.
[idzebra-moved-to-github.git] / index / rpnscan.c
1 /* $Id: rpnscan.c,v 1.11 2007-05-09 07:07:18 adam Exp $
2    Copyright (C) 1995-2007
3    Index Data ApS
4
5 This file is part of the Zebra server.
6
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20
21 */
22
23 #include <stdio.h>
24 #include <assert.h>
25 #ifdef WIN32
26 #include <io.h>
27 #endif
28 #if HAVE_UNISTD_H
29 #include <unistd.h>
30 #endif
31 #include <ctype.h>
32
33 #include <yaz/diagbib1.h>
34 #include "index.h"
35 #include <zebra_xpath.h>
36 #include <yaz/wrbuf.h>
37 #include <attrfind.h>
38 #include <charmap.h>
39 #include <rset.h>
40 #include <yaz/oid_db.h>
41
42 #define RPN_MAX_ORDS 32
43
44 int log_scan = YLOG_LOG;
45
46 /* convert APT SCAN term to internal cmap */
47 static ZEBRA_RES trans_scan_term(ZebraHandle zh, Z_AttributesPlusTerm *zapt,
48                                  char *termz, int reg_type)
49 {
50     char termz0[IT_MAX_WORD];
51
52     if (zapt_term_to_utf8(zh, zapt, termz0) == ZEBRA_FAIL)
53         return ZEBRA_FAIL;    /* error */
54     else
55     {
56         const char **map;
57         const char *cp = (const char *) termz0;
58         const char *cp_end = cp + strlen(cp);
59         const char *src;
60         int i = 0;
61         const char *space_map = NULL;
62         int len;
63             
64         while ((len = (cp_end - cp)) > 0)
65         {
66             map = zebra_maps_input(zh->reg->zebra_maps, reg_type, &cp, len, 0);
67             if (**map == *CHR_SPACE)
68                 space_map = *map;
69             else
70             {
71                 if (i && space_map)
72                     for (src = space_map; *src; src++)
73                         termz[i++] = *src;
74                 space_map = NULL;
75                 for (src = *map; *src; src++)
76                     termz[i++] = *src;
77             }
78         }
79         termz[i] = '\0';
80     }
81     return ZEBRA_OK;
82 }
83
84 static void count_set(ZebraHandle zh, RSET rset, zint *count)
85 {
86     zint psysno = 0;
87     struct it_key key;
88     RSFD rfd;
89
90     yaz_log(YLOG_DEBUG, "count_set");
91
92     rset->hits_limit = zh->approx_limit;
93
94     *count = 0;
95     rfd = rset_open(rset, RSETF_READ);
96     while (rset_read(rfd, &key,0 /* never mind terms */))
97     {
98         if (key.mem[0] != psysno)
99         {
100             psysno = key.mem[0];
101             if (rfd->counted_items >= rset->hits_limit)
102                 break;
103         }
104     }
105     rset_close (rfd);
106     *count = rset->hits_count;
107 }
108
109 struct scan2_info_entry {
110     WRBUF term;
111     char prefix[20];
112     ISAM_P isam_p;
113     int pos_to_save;
114 };
115
116 static int scan_handle2(char *name, const char *info, int pos, void *client)
117 {
118     int len_prefix;
119     struct scan2_info_entry *scan_info = (struct scan2_info_entry *) client;
120
121     if (scan_info->pos_to_save != pos)
122         return 0;
123
124     len_prefix = strlen(scan_info->prefix);
125     if (memcmp (name, scan_info->prefix, len_prefix))
126         return 1;
127
128     /* skip special terms such as first-in-field specials */
129     if (name[len_prefix] < CHR_BASE_CHAR)
130         return 1;
131
132     wrbuf_rewind(scan_info->term);
133     wrbuf_puts(scan_info->term, name+len_prefix);
134
135     assert (*info == sizeof(ISAM_P));
136     memcpy (&scan_info->isam_p, info+1, sizeof(ISAM_P));
137     return 0;
138 }
139
140
141 static int scan_save_set(ZebraHandle zh, ODR stream, NMEM nmem,
142                          struct rset_key_control *kc,
143                          Z_AttributesPlusTerm *zapt,
144                          RSET limit_set,
145                          const char *term, 
146                          int index_type,
147                          struct scan2_info_entry *ar, int ord_no,
148                          ZebraScanEntry *glist, int pos)
149 {
150     int i;
151     RSET rset = 0;
152     for (i = 0; i < ord_no; i++)
153     {
154         if (ar[i].isam_p && strcmp(wrbuf_cstr(ar[i].term), term) == 0)
155         {
156             RSET rset_t = rset_trunc(
157                     zh, &ar[i].isam_p, 1,
158                     wrbuf_buf(ar[i].term), wrbuf_len(ar[i].term),
159                     NULL, 0, zapt->term->which, nmem, 
160                     kc, kc->scope, 0, index_type, 
161                     0 /* hits_limit */,
162                     0 /* term_ref_id_str */);
163             if (!rset)
164                 rset = rset_t;
165             else
166             {
167                 RSET rsets[2];
168                 
169                 rsets[0] = rset;
170                 rsets[1] = rset_t;
171                 rset = rset_create_or(nmem, kc, kc->scope, 0 /* termid */,
172                                       2, rsets);
173             }
174             ar[i].isam_p = 0;
175         }
176     }
177     if (rset)
178     {
179         zint count;
180         /* merge with limit_set if given */
181         if (limit_set)
182         {
183             RSET rsets[2];
184             rsets[0] = rset;
185             rsets[1] = rset_dup(limit_set);
186             
187             rset = rset_create_and(nmem, kc, kc->scope, 2, rsets);
188         }
189         /* count it */
190         count_set(zh, rset, &count);
191         rset_delete(rset);
192         if (count > 0)
193         {
194             if (pos != -1)
195             {
196                 zebra_term_untrans_iconv(zh, stream->mem, index_type,
197                                          &glist[pos].term, term);
198                 glist[pos].occurrences = count;
199             }
200             return 1;
201         }
202     }
203     return 0;
204 }
205         
206 static ZEBRA_RES rpn_scan_ver2(ZebraHandle zh, ODR stream, NMEM nmem,
207                                struct rset_key_control *kc,
208                                Z_AttributesPlusTerm *zapt,
209                                int *position, int *num_entries, 
210                                ZebraScanEntry **list,
211                                int *is_partial, RSET limit_set,
212                                int index_type, int ord_no, int *ords)
213 {
214     struct scan2_info_entry *ar = nmem_malloc(nmem, sizeof(*ar) * ord_no);
215     struct rpn_char_map_info rcmi;
216     int i, dif;
217     int after_pos;
218     int pos = 0;
219
220     ZebraScanEntry *glist = (ZebraScanEntry *)
221         odr_malloc(stream, *num_entries * sizeof(*glist));
222
223     *is_partial = 0;
224     if (*position > *num_entries+1)
225     {
226         *is_partial = 1;
227         *position = 1;
228         *num_entries = 0;
229         return ZEBRA_OK;
230     }
231     rpn_char_map_prepare (zh->reg, index_type, &rcmi);
232
233     for (i = 0; i < ord_no; i++)
234         ar[i].term = wrbuf_alloc();
235
236     for (i = 0; i < ord_no; i++)
237     {
238         char termz[IT_MAX_WORD+20];
239         int prefix_len = 0;
240         
241         prefix_len = key_SU_encode (ords[i], termz);
242         termz[prefix_len] = 0;
243         strcpy(ar[i].prefix, termz);
244         
245         if (trans_scan_term(zh, zapt, termz+prefix_len, index_type) == 
246             ZEBRA_FAIL)
247         {
248             for (i = 0; i < ord_no; i++)
249                 wrbuf_destroy(ar[i].term);
250             return ZEBRA_FAIL;
251         }
252         wrbuf_rewind(ar[i].term);
253         wrbuf_puts(ar[i].term, termz + prefix_len);
254         ar[i].isam_p = 0;
255     }
256     /** deal with terms before position .. */
257     /* the glist index starts at zero (unlike scan positions */
258     for (pos = *position-2; pos >= 0; )
259     {
260         const char *hi = 0;
261
262         /* scan on all maximum terms */
263         for (i = 0; i < ord_no; i++)
264         {
265             if (ar[i].isam_p == 0)
266             {
267                 char termz[IT_MAX_WORD+20];
268                 int before = 1;
269                 int after = 0;
270
271                 ar[i].pos_to_save = -1;
272
273                 strcpy(termz, ar[i].prefix);
274                 strcat(termz, wrbuf_cstr(ar[i].term));
275                 dict_scan(zh->reg->dict, termz, &before, &after,
276                           ar+i, scan_handle2);
277             }
278         }
279         /* get maximum after scan */
280         for (i = 0; i < ord_no; i++)
281         {
282             if (ar[i].isam_p 
283                 && (hi == 0 || strcmp(wrbuf_cstr(ar[i].term), hi) > 0))
284                 hi = wrbuf_cstr(ar[i].term);
285         }
286         if (!hi)
287             break;
288         if (scan_save_set(zh, stream, nmem, kc, zapt, limit_set, hi,
289                           index_type, ar, ord_no, glist,
290                           (pos >= 0 && pos < *num_entries) ? pos : -1))
291             --pos;
292     }
293     /* see if we got all terms before.. */
294     dif = 1 + pos;
295     if (dif > 0)
296     {
297         /* did not get all terms; adjust the real position and reduce
298            number of entries */
299         yaz_log(YLOG_LOG, "before terms dif=%d", dif);
300         glist = glist + dif;
301         *num_entries -= dif;
302         *position -= dif;
303         *is_partial = 1;
304     }
305     for (i = 0; i < ord_no; i++)
306     {
307         char termz[IT_MAX_WORD+20];
308         int prefix_len = 0;
309         
310         prefix_len = key_SU_encode (ords[i], termz);
311         termz[prefix_len] = 0;
312         strcpy(ar[i].prefix, termz);
313         
314         if (trans_scan_term(zh, zapt, termz+prefix_len, index_type) == 
315             ZEBRA_FAIL)
316             return ZEBRA_FAIL;
317         wrbuf_rewind(ar[i].term);
318         wrbuf_puts(ar[i].term, termz + prefix_len);
319         ar[i].isam_p = 0;
320     }
321
322     after_pos = 1;  /* immediate term first.. */
323     for (pos = *position-1; pos < *num_entries; )
324     {
325         const char *lo = 0;
326
327         /* scan on all minimum terms */
328         for (i = 0; i < ord_no; i++)
329         {
330             if (ar[i].isam_p == 0)
331             {
332                 char termz[IT_MAX_WORD+20];
333                 int before = 0;
334                 int after = after_pos;
335
336                 ar[i].pos_to_save = 1;
337
338                 strcpy(termz, ar[i].prefix);
339                 strcat(termz, wrbuf_cstr(ar[i].term));
340                 dict_scan(zh->reg->dict, termz, &before, &after,
341                           ar+i, scan_handle2);
342             }
343         }
344         after_pos = 2;  /* next round we grab following term */
345
346         /* get minimum after scan */
347         for (i = 0; i < ord_no; i++)
348         {
349             if (ar[i].isam_p 
350                 && (lo == 0 || strcmp(wrbuf_cstr(ar[i].term), lo) < 0))
351                 lo = wrbuf_cstr(ar[i].term);
352         }
353         if (!lo)
354             break;
355         if (scan_save_set(zh, stream, nmem, kc, zapt, limit_set, lo,
356                           index_type, ar, ord_no, glist,
357                           (pos >= 0 && pos < *num_entries) ? pos : -1))
358             pos++;
359
360     }
361     if (pos != *num_entries)
362     {
363         if (pos >= 0)
364             *num_entries = pos;
365         else
366             *num_entries = 0;
367         *is_partial = 1;
368     }
369
370     *list = glist;
371
372     for (i = 0; i < ord_no; i++)
373         wrbuf_destroy(ar[i].term);
374
375     return ZEBRA_OK;
376 }
377
378 struct scan1_info_entry {
379     char *term;
380     ISAM_P isam_p;
381 };
382
383 struct scan_info {
384     struct scan1_info_entry *list;
385     ODR odr;
386     int before, after;
387     char prefix[20];
388 };
389
390 ZEBRA_RES rpn_scan(ZebraHandle zh, ODR stream, Z_AttributesPlusTerm *zapt,
391                    const Odr_oid *attributeset,
392                    int num_bases, char **basenames,
393                    int *position, int *num_entries, ZebraScanEntry **list,
394                    int *is_partial, RSET limit_set)
395 {
396     int base_no;
397     int ords[RPN_MAX_ORDS], ord_no = 0;
398
399     unsigned index_type;
400     char *search_type = NULL;
401     char rank_type[128];
402     int complete_flag;
403     int sort_flag;
404     NMEM nmem;
405     ZEBRA_RES res;
406     struct rset_key_control *kc = 0;
407
408     *list = 0;
409     *is_partial = 0;
410
411     if (!attributeset)
412         attributeset = yaz_oid_attset_bib_1;
413
414     if (!limit_set) /* no limit set given already */
415     {
416         /* see if there is a @attr 8=set */
417         AttrType termset;
418         int termset_value_numeric;
419         const char *termset_value_string;
420         attr_init_APT(&termset, zapt, 8);
421         termset_value_numeric =
422             attr_find_ex(&termset, NULL, &termset_value_string);
423         if (termset_value_numeric != -1)
424         {
425             char resname[32];
426             const char *termset_name = 0;
427             
428             if (termset_value_numeric != -2)
429             {
430                 sprintf(resname, "%d", termset_value_numeric);
431                 termset_name = resname;
432             }
433             else
434                 termset_name = termset_value_string;
435             
436             limit_set = resultSetRef (zh, termset_name);
437
438             if (!limit_set)
439             {
440                 zebra_setError(zh, 
441                                YAZ_BIB1_SPECIFIED_RESULT_SET_DOES_NOT_EXIST,
442                                termset_name);
443                 return ZEBRA_FAIL;
444             }
445         }
446     }
447         
448     yaz_log(YLOG_DEBUG, "position = %d, num = %d",
449             *position, *num_entries);
450         
451     if (zebra_maps_attr(zh->reg->zebra_maps, zapt, &index_type, &search_type,
452                         rank_type, &complete_flag, &sort_flag))
453     {
454         *num_entries = 0;
455         zebra_setError(zh, YAZ_BIB1_UNSUPP_ATTRIBUTE_TYPE, 0);
456         return ZEBRA_FAIL;
457     }
458     if (num_bases > RPN_MAX_ORDS)
459     {
460         zebra_setError(zh, YAZ_BIB1_TOO_MANY_DATABASES_SPECIFIED, 0);
461         return ZEBRA_FAIL;
462     }
463
464     for (base_no = 0; base_no < num_bases; base_no++)
465     {
466         int ord;
467
468         if (zebraExplain_curDatabase (zh->reg->zei, basenames[base_no]))
469         {
470             zebra_setError(zh, YAZ_BIB1_DATABASE_UNAVAILABLE,
471                            basenames[base_no]);
472             *num_entries = 0;
473             return ZEBRA_FAIL;
474         }
475         if (zebra_apt_get_ord(zh, zapt, index_type, 0, attributeset, &ord) 
476             != ZEBRA_OK)
477             continue;
478         ords[ord_no++] = ord;
479     }
480     if (ord_no == 0)
481     {
482         *num_entries = 0; /* zebra_apt_get_ord should set error reason */
483         return ZEBRA_FAIL;
484     }
485     if (*num_entries < 1)
486     {
487         *num_entries = 0;
488         return ZEBRA_OK;
489     }
490     nmem = nmem_create();
491     kc = zebra_key_control_create(zh);
492
493     res = rpn_scan_ver2(zh, stream, nmem, kc, zapt, position, num_entries,
494                         list,
495                         is_partial, limit_set, index_type, ord_no, ords);
496     nmem_destroy(nmem);
497     (*kc->dec)(kc);
498     return res;
499 }
500
501 /*
502  * Local variables:
503  * c-basic-offset: 4
504  * indent-tabs-mode: nil
505  * End:
506  * vim: shiftwidth=4 tabstop=8 expandtab
507  */
508