5d7f821448d4772098be300afd5de7f32975e98f
[yaz-moved-to-github.git] / src / cclfind.c
1 /* This file is part of the YAZ toolkit.
2  * Copyright (C) Index Data
3  * See the file LICENSE for details.
4  */
5 /**
6  * \file cclfind.c
7  * \brief Implements parsing of a CCL FIND query.
8  *
9  * This source file implements parsing of a CCL Query (ISO8777).
10  * The parser uses predictive parsing, but it does several tokens
11  * of lookahead in the handling of relational operations.. So
12  * it's not really pure.
13  */
14 #if HAVE_CONFIG_H
15 #include <config.h>
16 #endif
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <assert.h>
21
22 #include "cclp.h"
23
24 /* returns type of current lookahead */
25 #define KIND (cclp->look_token->kind)
26
27 /* move one token forward */
28 #define ADVANCE cclp->look_token = cclp->look_token->next
29
30 /**
31  * qual_val_type: test for existance of attribute type/value pair.
32  * qa:     Attribute array
33  * type:   Type of attribute to search for
34  * value:  Value of attribute to seach for
35  * return: 1 if found; 0 otherwise.
36  */
37 static int qual_val_type(ccl_qualifier_t *qa, int type, int value,
38                          char **attset)
39 {
40     int i;
41
42     if (!qa)
43         return 0;
44     for (i = 0; qa[i]; i++)
45     {
46         struct ccl_rpn_attr *q = ccl_qual_get_attr(qa[i]);
47         while (q)
48         {
49             if (q->type == type && q->kind == CCL_RPN_ATTR_NUMERIC &&
50                 q->value.numeric == value)
51             {
52                 if (attset)
53                     *attset = q->set;
54                 return 1;
55             }
56             q = q->next;
57         }
58     }
59     return 0;
60 }
61
62 /**
63  * strxcat: concatenate strings.
64  * n:      Null-terminated Destination string
65  * src:    Source string to be appended (not null-terminated)
66  * len:    Length of source string.
67  */
68 static void strxcat(char *n, const char *src, int len)
69 {
70     while (*n)
71         n++;
72     while (--len >= 0)
73         *n++ = *src++;
74     *n = '\0';
75 }
76
77 /**
78  * copy_token_name: Return copy of CCL token name
79  * tp:      Pointer to token info.
80  * return:  malloc(3) allocated copy of token name.
81  */
82 static char *copy_token_name(struct ccl_token *tp)
83 {
84     char *str = (char *)xmalloc(tp->len + 1);
85     ccl_assert(str);
86     memcpy(str, tp->name, tp->len);
87     str[tp->len] = '\0';
88     return str;
89 }
90
91 /**
92  * mk_node: Create RPN node.
93  * kind:   Type of node.
94  * return: pointer to allocated node.
95  */
96 struct ccl_rpn_node *ccl_rpn_node_create(enum ccl_rpn_kind kind)
97 {
98     struct ccl_rpn_node *p;
99     p = (struct ccl_rpn_node *)xmalloc(sizeof(*p));
100     ccl_assert(p);
101     p->kind = kind;
102
103     switch (kind)
104     {
105     case CCL_RPN_TERM:
106         p->u.t.attr_list = 0;
107         p->u.t.term = 0;
108         p->u.t.qual = 0;
109         break;
110     default:
111         break;
112     }
113     return p;
114 }
115
116 /**
117  * ccl_rpn_delete: Delete RPN tree.
118  * rpn:   Pointer to tree.
119  */
120 void ccl_rpn_delete(struct ccl_rpn_node *rpn)
121 {
122     struct ccl_rpn_attr *attr, *attr1;
123     if (!rpn)
124         return;
125     switch (rpn->kind)
126     {
127     case CCL_RPN_AND:
128     case CCL_RPN_OR:
129     case CCL_RPN_NOT:
130         ccl_rpn_delete(rpn->u.p[0]);
131         ccl_rpn_delete(rpn->u.p[1]);
132         break;
133     case CCL_RPN_TERM:
134         xfree(rpn->u.t.term);
135         xfree(rpn->u.t.qual);
136         for (attr = rpn->u.t.attr_list; attr; attr = attr1)
137         {
138             attr1 = attr->next;
139             if (attr->kind == CCL_RPN_ATTR_STRING)
140                 xfree(attr->value.str);
141             if (attr->set)
142                 xfree(attr->set);
143             xfree(attr);
144         }
145         break;
146     case CCL_RPN_SET:
147         xfree(rpn->u.setname);
148         break;
149     case CCL_RPN_PROX:
150         ccl_rpn_delete(rpn->u.p[0]);
151         ccl_rpn_delete(rpn->u.p[1]);
152         ccl_rpn_delete(rpn->u.p[2]);
153         break;
154     }
155     xfree(rpn);
156 }
157
158 static struct ccl_rpn_node *find_spec(CCL_parser cclp, ccl_qualifier_t *qa);
159
160 static int is_term_ok(int look, int *list)
161 {
162     for (; *list >= 0; list++)
163         if (look == *list)
164             return 1;
165     return 0;
166 }
167
168 static struct ccl_rpn_node *search_terms(CCL_parser cclp, ccl_qualifier_t *qa);
169
170 static struct ccl_rpn_attr *add_attr_node(struct ccl_rpn_node *p,
171                                            const char *set, int type)
172 {
173     struct ccl_rpn_attr *n = (struct ccl_rpn_attr *) xmalloc(sizeof(*n));
174     ccl_assert(n);
175     if (set)
176         n->set = xstrdup(set);
177     else
178         n->set = 0;
179     n->type = type;
180     n->next = p->u.t.attr_list;
181     p->u.t.attr_list = n;
182     return n;
183 }
184
185 /**
186  * add_attr_numeric: Add attribute (type/value) to RPN term node.
187  * p:     RPN node of type term.
188  * type:  Type of attribute
189  * value: Value of attribute
190  * set: Attribute set name
191  */
192 void ccl_add_attr_numeric(struct ccl_rpn_node *p, const char *set,
193                           int type, int value)
194 {
195     struct ccl_rpn_attr *n = add_attr_node(p, set, type);
196     n->kind = CCL_RPN_ATTR_NUMERIC;
197     n->value.numeric = value;
198 }
199
200 void ccl_add_attr_string(struct ccl_rpn_node *p, const char *set,
201                          int type, char *value)
202 {
203     struct ccl_rpn_attr *n = add_attr_node(p, set, type);
204     n->kind = CCL_RPN_ATTR_STRING;
205     n->value.str = xstrdup(value);
206 }
207
208 static size_t cmp_operator(const char **aliases, const char *input)
209 {
210     for (; *aliases; aliases++)
211     {
212         const char *cp = *aliases;
213         size_t i;
214         for (i = 0; *cp && *cp == input[i]; i++, cp++)
215             ;
216         if (*cp == '\0')
217             return i;
218     }
219     return 0;
220 }
221
222
223 #define REGEX_CHARS "^[]{}()|.*+?!$"
224 #define CCL_CHARS "#?\\"
225
226 static int has_ccl_masking(const char *src_str,
227                            size_t src_len,
228                            const char **truncation_aliases,
229                            const char **mask_aliases)
230 {
231     size_t j;
232     int quote_mode = 0;
233
234     for (j = 0; j < src_len; j++)
235     {
236         size_t op_size;
237         if (j > 0 && src_str[j-1] == '\\')
238             ;
239         else if (src_str[j] == '"')
240             quote_mode = !quote_mode;
241         else if (!quote_mode &&
242                  (op_size = cmp_operator(truncation_aliases,
243                                          src_str + j)))
244             return 1;
245         else if (!quote_mode &&
246                  (op_size = cmp_operator(mask_aliases,
247                                           src_str + j)))
248             return 1;
249     }
250     return 0;
251 }
252
253 static int append_term(CCL_parser cclp, const char *src_str, size_t src_len,
254                        char *dst_term, int regex_trunc, int z3958_trunc,
255                        const char **truncation_aliases,
256                        const char **mask_aliases,
257                        int is_first, int is_last,
258                        int *left_trunc, int *right_trunc)
259 {
260     size_t j;
261     int quote_mode = 0;
262
263     for (j = 0; j < src_len; j++)
264     {
265         size_t op_size;
266         if (j > 0 && src_str[j-1] == '\\')
267         {
268             if (regex_trunc && strchr(REGEX_CHARS "\\", src_str[j]))
269                 strcat(dst_term, "\\");
270             else if (z3958_trunc && strchr(CCL_CHARS "\\", src_str[j]))
271                 strcat(dst_term, "\\");
272             strxcat(dst_term, src_str + j, 1);
273         }
274         else if (src_str[j] == '"')
275             quote_mode = !quote_mode;
276         else if (!quote_mode &&
277                  (op_size = cmp_operator(truncation_aliases,
278                                          src_str + j))
279             )
280         {
281             j += (op_size - 1);  /* j++ in for loop */
282             if (regex_trunc)
283                 strcat(dst_term, ".*");
284             else if (z3958_trunc)
285                 strcat(dst_term, "?");
286             else if (is_first && j == 0)
287                 *left_trunc = 1;
288             else if (is_last && j == src_len - 1)
289                 *right_trunc = 1;
290             else
291             {
292                 cclp->error_code = CCL_ERR_TRUNC_NOT_EMBED;
293                 return -1;
294             }
295         }
296         else if (!quote_mode &&
297                  (op_size = cmp_operator(mask_aliases, src_str + j)))
298         {
299             j += (op_size - 1);  /* j++ in for loop */
300             if (regex_trunc)
301                 strcat(dst_term, ".");
302             else if (z3958_trunc)
303                 strcat(dst_term, "#");
304             else
305             {
306                 cclp->error_code = CCL_ERR_TRUNC_NOT_SINGLE;
307                 return -1;
308             }
309         }
310         else if (src_str[j] != '\\')
311         {
312             if (regex_trunc && strchr(REGEX_CHARS, src_str[j]))
313                 strcat(dst_term, "\\");
314             else if (z3958_trunc && strchr(CCL_CHARS, src_str[j]))
315                 strcat(dst_term, "\\");
316             strxcat(dst_term, src_str + j, 1);
317         }
318     }
319     return 0;
320 }
321
322
323 static struct ccl_rpn_node *ccl_term_one_use(CCL_parser cclp,
324                                              struct ccl_rpn_attr *attr_use,
325                                              ccl_qualifier_t *qa,
326                                              size_t no, int term_len,
327                                              int is_phrase,
328                                              int auto_group)
329 {
330     struct ccl_rpn_node *p;
331     size_t i;
332     int relation_value = -1;
333     int position_value = -1;
334     int structure_value = -1;
335     int truncation_value = -1;
336     int completeness_value = -1;
337
338     int left_trunc = 0;
339     int right_trunc = 0;
340     int regex_trunc = 0;
341     int z3958_trunc = 0;
342     int is_ccl_masked = 0;
343     char *attset;
344     struct ccl_token *lookahead = cclp->look_token;
345     const char **truncation_aliases;
346     const char *t_default[2];
347     const char **mask_aliases;
348     const char *m_default[2];
349
350     truncation_aliases =
351         ccl_qual_search_special(cclp->bibset, "truncation");
352     if (!truncation_aliases)
353     {
354         truncation_aliases = t_default;
355         t_default[0] = "?";
356         t_default[1] = 0;
357     }
358     mask_aliases =
359         ccl_qual_search_special(cclp->bibset, "mask");
360     if (!mask_aliases)
361     {
362         mask_aliases = m_default;
363         m_default[0] = "#";
364         m_default[1] = 0;
365     }
366     for (i = 0; i < no; i++)
367     {
368         if (has_ccl_masking(lookahead->name, lookahead->len,
369                             truncation_aliases,
370                             mask_aliases))
371             is_ccl_masked = 1;
372         lookahead = lookahead->next;
373     }
374     lookahead = cclp->look_token;
375
376     p = ccl_rpn_node_create(CCL_RPN_TERM);
377     p->u.t.attr_list = NULL;
378     p->u.t.term = NULL;
379     if (qa && qa[0])
380     {
381         const char *n = ccl_qual_get_name(qa[0]);
382         if (n)
383             p->u.t.qual = xstrdup(n);
384     }
385     /* go through all attributes and add them to the attribute list */
386     for (i = 0; qa && qa[i]; i++)
387     {
388         struct ccl_rpn_attr *attr;
389         for (attr = ccl_qual_get_attr(qa[i]); attr; attr = attr->next)
390             if (attr->type != 1 || attr == attr_use)
391             {
392                 switch (attr->kind)
393                 {
394                 case CCL_RPN_ATTR_STRING:
395                     ccl_add_attr_string(p, attr->set, attr->type,
396                                         attr->value.str);
397                     break;
398                 case CCL_RPN_ATTR_NUMERIC:
399                     if (attr->value.numeric > 0)
400                     {   /* deal only with REAL attributes (positive) */
401                         switch (attr->type)
402                         {
403                         case CCL_BIB1_REL:
404                             if (relation_value != -1)
405                                 continue;
406                             relation_value = attr->value.numeric;
407                             break;
408                         case CCL_BIB1_POS:
409                             if (position_value != -1)
410                                 continue;
411                             position_value = attr->value.numeric;
412                             break;
413                         case CCL_BIB1_STR:
414                             if (structure_value != -1)
415                                 continue;
416                             structure_value = attr->value.numeric;
417                             break;
418                         case CCL_BIB1_TRU:
419                             if (truncation_value != -1)
420                                 continue;
421                             truncation_value = attr->value.numeric;
422                             break;
423                         case CCL_BIB1_COM:
424                             if (completeness_value != -1)
425                                 continue;
426                             completeness_value = attr->value.numeric;
427                             break;
428                         }
429                         ccl_add_attr_numeric(p, attr->set, attr->type,
430                                              attr->value.numeric);
431                     }
432                 }
433             }
434     }
435     attset = 0;
436     if (structure_value == -1 && (
437             auto_group ||
438             qual_val_type(qa, CCL_BIB1_STR, CCL_BIB1_STR_WP, &attset))
439         )
440     {
441         if (!is_phrase)
442             ccl_add_attr_numeric(p, attset, CCL_BIB1_STR, 2);
443         else
444             ccl_add_attr_numeric(p, attset, CCL_BIB1_STR, 1);
445     }
446     if (qual_val_type(qa, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_REGEX,
447                       &attset))
448     {
449         if (is_ccl_masked)
450             regex_trunc = 1; /* regex trunc (102) allowed */
451     }
452     else if (qual_val_type(qa, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_Z3958,
453                            &attset))
454     {
455         if (is_ccl_masked)
456             z3958_trunc = 1; /* Z39.58 trunc (CCL) trunc allowed */
457     }
458     /* make the RPN token */
459     p->u.t.term = (char *)xmalloc(term_len * 2 + 2);
460     ccl_assert(p->u.t.term);
461     p->u.t.term[0] = '\0';
462
463     for (i = 0; i < no; i++)
464     {
465         const char *src_str = lookahead->name;
466         size_t src_len = lookahead->len;
467
468         if (p->u.t.term[0] && lookahead->ws_prefix_len)
469         {
470             strxcat(p->u.t.term, lookahead->ws_prefix_buf,
471                     lookahead->ws_prefix_len);
472         }
473         if (append_term(cclp, src_str, src_len, p->u.t.term, regex_trunc,
474                         z3958_trunc, truncation_aliases, mask_aliases,
475                         i == 0, i == no - 1,
476                         &left_trunc, &right_trunc))
477         {
478             ccl_rpn_delete(p);
479             return NULL;
480         }
481         lookahead = lookahead->next;
482     }
483     if (left_trunc && right_trunc)
484     {
485         if (!qual_val_type(qa, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_BOTH,
486                            &attset))
487         {
488             cclp->error_code = CCL_ERR_TRUNC_NOT_BOTH;
489             ccl_rpn_delete(p);
490             return NULL;
491         }
492         ccl_add_attr_numeric(p, attset, CCL_BIB1_TRU, 3);
493     }
494     else if (right_trunc)
495     {
496         if (!qual_val_type(qa, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_RIGHT,
497                            &attset))
498         {
499             cclp->error_code = CCL_ERR_TRUNC_NOT_RIGHT;
500             ccl_rpn_delete(p);
501             return NULL;
502         }
503         ccl_add_attr_numeric(p, attset, CCL_BIB1_TRU, 1);
504     }
505     else if (left_trunc)
506     {
507         if (!qual_val_type(qa, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_LEFT,
508                            &attset))
509         {
510             cclp->error_code = CCL_ERR_TRUNC_NOT_LEFT;
511             ccl_rpn_delete(p);
512             return NULL;
513         }
514         ccl_add_attr_numeric(p, attset, CCL_BIB1_TRU, 2);
515     }
516     else if (regex_trunc)
517     {
518         ccl_add_attr_numeric(p, attset, CCL_BIB1_TRU, 102);
519     }
520     else if (z3958_trunc)
521     {
522         ccl_add_attr_numeric(p, attset, CCL_BIB1_TRU, 104);
523     }
524     else
525     {
526         if (qual_val_type(qa, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_NONE,
527                           &attset))
528             ccl_add_attr_numeric(p, attset, CCL_BIB1_TRU, 100);
529     }
530     return p;
531 }
532
533 /**
534  * search_term: Parse CCL search term.
535  * cclp:   CCL Parser
536  * qa:     Qualifier attributes already applied.
537  * term_list: tokens we accept as terms in context
538  * multi:  whether we accept "multiple" tokens
539  * return: pointer to node(s); NULL on error.
540  */
541 static struct ccl_rpn_node *search_term_x(CCL_parser cclp,
542                                           ccl_qualifier_t *qa,
543                                           int *term_list, int multi)
544 {
545     struct ccl_rpn_node *p_top = 0;
546     struct ccl_token *lookahead = cclp->look_token;
547     int and_list = 0;
548     int auto_group = 0;
549     int or_list = 0;
550
551     if (qual_val_type(qa, CCL_BIB1_STR, CCL_BIB1_STR_AND_LIST, 0))
552         and_list = 1;
553     if (qual_val_type(qa, CCL_BIB1_STR, CCL_BIB1_STR_AUTO_GROUP, 0))
554         auto_group = 1;
555     if (qual_val_type(qa, CCL_BIB1_STR, CCL_BIB1_STR_OR_LIST, 0))
556         or_list = 1;
557     while (1)
558     {
559         struct ccl_rpn_node *p = 0;
560         size_t no, i;
561         int len = 0;
562         int is_phrase = 0;
563         size_t max = 200;
564         if (and_list || or_list || !multi)
565             max = 1;
566
567         /* ignore commas when dealing with and-lists .. */
568         if (and_list && lookahead && lookahead->kind == CCL_TOK_COMMA)
569         {
570             lookahead = lookahead->next;
571             ADVANCE;
572             continue;
573         }
574         for (no = 0; no < max && is_term_ok(lookahead->kind, term_list); no++)
575         {
576             int this_is_phrase = 0;
577             for (i = 0; i<lookahead->len; i++)
578                 if (lookahead->name[i] == ' ')
579                     this_is_phrase = 1;
580             if (auto_group)
581             {
582                 if (no > 0 && (is_phrase || is_phrase != this_is_phrase))
583                     break;
584                 is_phrase = this_is_phrase;
585             }
586             else if (this_is_phrase || no > 0)
587                 is_phrase = 1;
588             len += 1+lookahead->len+lookahead->ws_prefix_len;
589             lookahead = lookahead->next;
590         }
591
592         if (len == 0)
593             break;      /* no more terms . stop . */
594
595         /* go through all attributes and add them to the attribute list */
596         for (i = 0; qa && qa[i]; i++)
597         {
598             struct ccl_rpn_attr *attr;
599
600             for (attr = ccl_qual_get_attr(qa[i]); attr; attr = attr->next)
601                 if (attr->type == 1)
602                 {
603                     struct ccl_rpn_node *tmp2;
604                     tmp2 = ccl_term_one_use(cclp, attr, qa, no, len,
605                                             is_phrase, auto_group);
606                     if (!tmp2)
607                     {
608                         ccl_rpn_delete(p);
609                         return 0;
610                     }
611                     if (!p)
612                         p = tmp2;
613                     else
614                     {
615                         struct ccl_rpn_node *tmp1;
616                         tmp1 = ccl_rpn_node_create(CCL_RPN_OR);
617                         tmp1->u.p[0] = p;
618                         tmp1->u.p[1] = tmp2;
619                         p = tmp1;
620                     }
621                 }
622         }
623         if (!p)
624             p = ccl_term_one_use(cclp, 0 /* attr: no use */, qa, no, len,
625                                  is_phrase, auto_group);
626         for (i = 0; i < no; i++)
627             ADVANCE;
628         if (!p)
629             return 0;
630         /* make the top node point to us.. */
631         if (p_top)
632         {
633             struct ccl_rpn_node *tmp;
634
635             if (or_list)
636                 tmp = ccl_rpn_node_create(CCL_RPN_OR);
637             else if (and_list)
638                 tmp = ccl_rpn_node_create(CCL_RPN_AND);
639             else
640                 tmp = ccl_rpn_node_create(CCL_RPN_AND);
641             tmp->u.p[0] = p_top;
642             tmp->u.p[1] = p;
643
644             p_top = tmp;
645         }
646         else
647             p_top = p;
648
649         if (!multi)
650             break;
651     }
652     if (!p_top)
653         cclp->error_code = CCL_ERR_TERM_EXPECTED;
654     return p_top;
655 }
656
657 static struct ccl_rpn_node *search_term(CCL_parser cclp, ccl_qualifier_t *qa)
658 {
659     static int list[] = {CCL_TOK_TERM, CCL_TOK_COMMA, -1};
660     return search_term_x(cclp, qa, list, 0);
661 }
662
663
664 static struct ccl_rpn_node *search_terms2(CCL_parser cclp,
665                                           ccl_qualifier_t *qa)
666 {
667     if (KIND == CCL_TOK_LP)
668     {
669         struct ccl_rpn_node *p;
670         ADVANCE;
671         if (!(p = find_spec(cclp, qa)))
672             return NULL;
673         if (KIND != CCL_TOK_RP)
674         {
675             cclp->error_code = CCL_ERR_RP_EXPECTED;
676             ccl_rpn_delete(p);
677             return NULL;
678         }
679         ADVANCE;
680         return p;
681     }
682     else
683     {
684         static int list[] = {
685             CCL_TOK_TERM, CCL_TOK_COMMA,CCL_TOK_EQ,
686             CCL_TOK_REL, CCL_TOK_SET, -1};
687
688         return search_term_x(cclp, qa, list, 1);
689     }
690 }
691
692
693 static
694 struct ccl_rpn_node *qualifiers_order(CCL_parser cclp,
695                                       ccl_qualifier_t *ap, char *attset)
696 {
697     int rel = 0;
698     struct ccl_rpn_node *p;
699
700     if (cclp->look_token->len == 1)
701     {
702         if (cclp->look_token->name[0] == '<')
703             rel = 1;
704         else if (cclp->look_token->name[0] == '=')
705             rel = 3;
706         else if (cclp->look_token->name[0] == '>')
707             rel = 5;
708     }
709     else if (cclp->look_token->len == 2)
710     {
711         if (!memcmp(cclp->look_token->name, "<=", 2))
712             rel = 2;
713         else if (!memcmp(cclp->look_token->name, ">=", 2))
714             rel = 4;
715         else if (!memcmp(cclp->look_token->name, "<>", 2))
716             rel = 6;
717     }
718     if (!rel)
719     {
720         cclp->error_code = CCL_ERR_BAD_RELATION;
721         return NULL;
722     }
723     ADVANCE;  /* skip relation */
724     if (rel == 3 &&
725         qual_val_type(ap, CCL_BIB1_REL, CCL_BIB1_REL_PORDER, 0))
726     {
727         /* allow - inside term and treat it as range _always_ */
728         /* relation is =. Extract "embedded" - to separate terms */
729         if (KIND == CCL_TOK_TERM)
730         {
731             size_t i;
732             int quote_mode = 0;
733             for (i = 0; i<cclp->look_token->len; i++)
734             {
735                 if (i > 0 && cclp->look_token->name[i] == '\\')
736                     ;
737                 else if (cclp->look_token->name[i] == '"')
738                     quote_mode = !quote_mode;
739                 else if (cclp->look_token->name[i] == '-' && !quote_mode)
740                     break;
741             }
742
743             if (cclp->look_token->len > 1 && i == 0)
744             {   /*  -xx*/
745                 struct ccl_token *ntoken = ccl_token_add(cclp->look_token);
746
747                 ntoken->kind = CCL_TOK_TERM;
748                 ntoken->name = cclp->look_token->name + 1;
749                 ntoken->len = cclp->look_token->len - 1;
750
751                 cclp->look_token->len = 1;
752                 cclp->look_token->name = "-";
753             }
754             else if (cclp->look_token->len > 1 && i == cclp->look_token->len-1)
755             {   /* xx- */
756                 struct ccl_token *ntoken = ccl_token_add(cclp->look_token);
757
758                 ntoken->kind = CCL_TOK_TERM;
759                 ntoken->name = "-";
760                 ntoken->len = 1;
761
762                 (cclp->look_token->len)--;
763             }
764             else if (cclp->look_token->len > 2 && i < cclp->look_token->len)
765             {   /* xx-yy */
766                 struct ccl_token *ntoken1 = ccl_token_add(cclp->look_token);
767                 struct ccl_token *ntoken2 = ccl_token_add(ntoken1);
768
769                 ntoken1->kind = CCL_TOK_TERM;  /* generate - */
770                 ntoken1->name = "-";
771                 ntoken1->len = 1;
772
773                 ntoken2->kind = CCL_TOK_TERM;  /* generate yy */
774                 ntoken2->name = cclp->look_token->name + (i+1);
775                 ntoken2->len = cclp->look_token->len - (i+1);
776
777                 cclp->look_token->len = i;     /* adjust xx */
778             }
779             else if (i == cclp->look_token->len &&
780                      cclp->look_token->next &&
781                      cclp->look_token->next->kind == CCL_TOK_TERM &&
782                      cclp->look_token->next->len > 1 &&
783                      cclp->look_token->next->name[0] == '-')
784
785             {   /* xx -yy */
786                 /* we _know_ that xx does not have - in it */
787                 struct ccl_token *ntoken = ccl_token_add(cclp->look_token);
788
789                 ntoken->kind = CCL_TOK_TERM;    /* generate - */
790                 ntoken->name = "-";
791                 ntoken->len = 1;
792
793                 (ntoken->next->name)++;        /* adjust yy */
794                 (ntoken->next->len)--;
795             }
796         }
797     }
798
799     if (rel == 3 &&
800         KIND == CCL_TOK_TERM &&
801         cclp->look_token->next && cclp->look_token->next->len == 1 &&
802         cclp->look_token->next->name[0] == '-')
803     {
804         struct ccl_rpn_node *p1;
805         if (!(p1 = search_term(cclp, ap)))
806             return NULL;
807         ADVANCE;                   /* skip '-' */
808         if (KIND == CCL_TOK_TERM)  /* = term - term  ? */
809         {
810             struct ccl_rpn_node *p2;
811
812             if (!(p2 = search_term(cclp, ap)))
813             {
814                 ccl_rpn_delete(p1);
815                 return NULL;
816             }
817             p = ccl_rpn_node_create(CCL_RPN_AND);
818             p->u.p[0] = p1;
819             ccl_add_attr_numeric(p1, attset, CCL_BIB1_REL, 4);
820             p->u.p[1] = p2;
821             ccl_add_attr_numeric(p2, attset, CCL_BIB1_REL, 2);
822             return p;
823         }
824         else                       /* = term -    */
825         {
826             ccl_add_attr_numeric(p1, attset, CCL_BIB1_REL, 4);
827             return p1;
828         }
829     }
830     else if (rel == 3 &&
831              cclp->look_token->len == 1 &&
832              cclp->look_token->name[0] == '-')   /* = - term  ? */
833     {
834         ADVANCE;
835         if (!(p = search_term(cclp, ap)))
836             return NULL;
837         ccl_add_attr_numeric(p, attset, CCL_BIB1_REL, 2);
838         return p;
839     }
840     else
841     {
842         if (!(p = search_terms(cclp, ap)))
843             return NULL;
844         if (rel != 3 ||
845             !qual_val_type(ap, CCL_BIB1_REL, CCL_BIB1_REL_OMIT_EQUALS, 0))
846             ccl_add_attr_numeric(p, attset, CCL_BIB1_REL, rel);
847         return p;
848     }
849     return NULL;
850 }
851
852 static
853 struct ccl_rpn_node *qualifier_relation(CCL_parser cclp, ccl_qualifier_t *ap)
854 {
855     char *attset;
856
857     if (qual_val_type(ap, CCL_BIB1_REL, CCL_BIB1_REL_ORDER, &attset)
858         || qual_val_type(ap, CCL_BIB1_REL, CCL_BIB1_REL_PORDER, &attset))
859         return qualifiers_order(cclp, ap, attset);
860
861     /* unordered relation */
862     if (KIND != CCL_TOK_EQ)
863     {
864         cclp->error_code = CCL_ERR_EQ_EXPECTED;
865         return NULL;
866     }
867     ADVANCE;
868     return search_terms(cclp, ap);
869 }
870
871 /**
872  * qualifier_list: Parse CCL qualifiers and search terms.
873  * cclp:   CCL Parser
874  * la:     Token pointer to RELATION token.
875  * qa:     Qualifier attributes already applied.
876  * return: pointer to node(s); NULL on error.
877  */
878 static struct ccl_rpn_node *qualifier_list(CCL_parser cclp,
879                                            struct ccl_token *la,
880                                            ccl_qualifier_t *qa)
881 {
882     struct ccl_token *lookahead = cclp->look_token;
883     struct ccl_token *look_start = cclp->look_token;
884     ccl_qualifier_t *ap;
885     struct ccl_rpn_node *node = 0;
886     const char **field_str;
887     int no = 0;
888     int seq = 0;
889     int i;
890     int mode_merge = 1;
891 #if 0
892     if (qa)
893     {
894         cclp->error_code = CCL_ERR_DOUBLE_QUAL;
895         return NULL;
896     }
897 #endif
898     for (lookahead = cclp->look_token; lookahead != la;
899          lookahead=lookahead->next)
900         no++;
901     if (qa)
902         for (i=0; qa[i]; i++)
903             no++;
904     ap = (ccl_qualifier_t *)xmalloc((no ? (no+1) : 2) * sizeof(*ap));
905     ccl_assert(ap);
906
907     field_str = ccl_qual_search_special(cclp->bibset, "field");
908     if (field_str)
909     {
910         if (!strcmp(field_str[0], "or"))
911             mode_merge = 0;
912         else if (!strcmp(field_str[0], "merge"))
913             mode_merge = 1;
914     }
915     if (!mode_merge)
916     {
917         /* consider each field separately and OR */
918         lookahead = look_start;
919         while (lookahead != la)
920         {
921             ap[1] = 0;
922             seq = 0;
923             while ((ap[0] = ccl_qual_search(cclp, lookahead->name,
924                                             lookahead->len, seq)) != 0)
925             {
926                 struct ccl_rpn_node *node_sub;
927                 cclp->look_token = la;
928
929                 node_sub = qualifier_relation(cclp, ap);
930                 if (!node_sub)
931                 {
932                     ccl_rpn_delete(node);
933                     xfree(ap);
934                     return 0;
935                 }
936                 if (node)
937                 {
938                     struct ccl_rpn_node *node_this =
939                         ccl_rpn_node_create(CCL_RPN_OR);
940                     node_this->u.p[0] = node;
941                     node_this->u.p[1] = node_sub;
942                     node = node_this;
943                 }
944                 else
945                     node = node_sub;
946                 seq++;
947             }
948             if (seq == 0)
949             {
950                 cclp->look_token = lookahead;
951                 cclp->error_code = CCL_ERR_UNKNOWN_QUAL;
952                 xfree(ap);
953                 return NULL;
954             }
955             lookahead = lookahead->next;
956             if (lookahead->kind == CCL_TOK_COMMA)
957                 lookahead = lookahead->next;
958         }
959     }
960     else
961     {
962         /* merge attributes from ALL fields - including inherited ones */
963         while (1)
964         {
965             struct ccl_rpn_node *node_sub;
966             int found = 0;
967             lookahead = look_start;
968             for (i = 0; lookahead != la; i++)
969             {
970                 ap[i] = ccl_qual_search(cclp, lookahead->name,
971                                          lookahead->len, seq);
972                 if (ap[i])
973                     found++;
974                 if (!ap[i] && seq > 0)
975                     ap[i] = ccl_qual_search(cclp, lookahead->name,
976                                              lookahead->len, 0);
977                 if (!ap[i])
978                 {
979                     cclp->look_token = lookahead;
980                     cclp->error_code = CCL_ERR_UNKNOWN_QUAL;
981                     xfree(ap);
982                     return NULL;
983                 }
984                 lookahead = lookahead->next;
985                 if (lookahead->kind == CCL_TOK_COMMA)
986                     lookahead = lookahead->next;
987             }
988             if (qa)
989             {
990                 ccl_qualifier_t *qa0 = qa;
991
992                 while (*qa0)
993                     ap[i++] = *qa0++;
994             }
995             ap[i] = NULL;
996
997             if (!found)
998                 break;
999
1000             cclp->look_token = lookahead;
1001
1002             node_sub = qualifier_relation(cclp, ap);
1003             if (!node_sub)
1004             {
1005                 ccl_rpn_delete(node);
1006                 break;
1007             }
1008             if (node)
1009             {
1010                 struct ccl_rpn_node *node_this =
1011                     ccl_rpn_node_create(CCL_RPN_OR);
1012                 node_this->u.p[0] = node;
1013                 node_this->u.p[1] = node_sub;
1014                 node = node_this;
1015             }
1016             else
1017                 node = node_sub;
1018             seq++;
1019         }
1020     }
1021     xfree(ap);
1022     return node;
1023 }
1024
1025
1026 /**
1027  * search_terms: Parse CCL search terms - including proximity.
1028  * cclp:   CCL Parser
1029  * qa:     Qualifier attributes already applied.
1030  * return: pointer to node(s); NULL on error.
1031  */
1032 static struct ccl_rpn_node *search_terms(CCL_parser cclp, ccl_qualifier_t *qa)
1033 {
1034     static int list[] = {
1035         CCL_TOK_TERM, CCL_TOK_COMMA,CCL_TOK_EQ,
1036         CCL_TOK_REL, CCL_TOK_SET, -1};
1037     struct ccl_rpn_node *p1, *p2, *pn;
1038     p1 = search_terms2(cclp, qa);
1039     if (!p1)
1040         return NULL;
1041     while (1)
1042     {
1043         if (KIND == CCL_TOK_PROX)
1044         {
1045             struct ccl_rpn_node *p_prox = 0;
1046             /* ! word order specified */
1047             /* % word order not specified */
1048             p_prox = ccl_rpn_node_create(CCL_RPN_TERM);
1049             p_prox->u.t.term = (char *) xmalloc(1 + cclp->look_token->len);
1050             memcpy(p_prox->u.t.term, cclp->look_token->name,
1051                    cclp->look_token->len);
1052             p_prox->u.t.term[cclp->look_token->len] = 0;
1053             p_prox->u.t.attr_list = 0;
1054
1055             ADVANCE;
1056             p2 = search_terms2(cclp, qa);
1057             if (!p2)
1058             {
1059                 ccl_rpn_delete(p1);
1060                 return NULL;
1061             }
1062             pn = ccl_rpn_node_create(CCL_RPN_PROX);
1063             pn->u.p[0] = p1;
1064             pn->u.p[1] = p2;
1065             pn->u.p[2] = p_prox;
1066             p1 = pn;
1067         }
1068         else if (is_term_ok(KIND, list))
1069         {
1070             p2 = search_terms2(cclp, qa);
1071             if (!p2)
1072             {
1073                 ccl_rpn_delete(p1);
1074                 return NULL;
1075             }
1076             pn = ccl_rpn_node_create(CCL_RPN_PROX);
1077             pn->u.p[0] = p1;
1078             pn->u.p[1] = p2;
1079             pn->u.p[2] = 0;
1080             p1 = pn;
1081         }
1082         else
1083             break;
1084     }
1085     return p1;
1086 }
1087
1088 /**
1089  * search_elements: Parse CCL search elements
1090  * cclp:   CCL Parser
1091  * qa:     Qualifier attributes already applied.
1092  * return: pointer to node(s); NULL on error.
1093  */
1094 static struct ccl_rpn_node *search_elements(CCL_parser cclp,
1095                                             ccl_qualifier_t *qa)
1096 {
1097     struct ccl_rpn_node *p1;
1098     struct ccl_token *lookahead;
1099     if (KIND == CCL_TOK_SET)
1100     {
1101         ADVANCE;
1102         if (KIND == CCL_TOK_EQ)
1103             ADVANCE;
1104         if (KIND != CCL_TOK_TERM)
1105         {
1106             cclp->error_code = CCL_ERR_SETNAME_EXPECTED;
1107             return NULL;
1108         }
1109         p1 = ccl_rpn_node_create(CCL_RPN_SET);
1110         p1->u.setname = copy_token_name(cclp->look_token);
1111         ADVANCE;
1112         return p1;
1113     }
1114     lookahead = cclp->look_token;
1115
1116     while (lookahead->kind==CCL_TOK_TERM)
1117     {
1118         lookahead = lookahead->next;
1119         if (lookahead->kind == CCL_TOK_REL || lookahead->kind == CCL_TOK_EQ)
1120             return qualifier_list(cclp, lookahead, qa);
1121         if (lookahead->kind != CCL_TOK_COMMA)
1122             break;
1123         lookahead = lookahead->next;
1124     }
1125     if (qa || lookahead->kind == CCL_TOK_LP)
1126         return search_terms(cclp, qa);
1127     else
1128     {
1129         ccl_qualifier_t qa[2];
1130         struct ccl_rpn_node *node = 0;
1131         int seq;
1132         lookahead = cclp->look_token;
1133
1134         qa[1] = 0;
1135         for(seq = 0; ;seq++)
1136         {
1137             struct ccl_rpn_node *node_sub;
1138             qa[0] = ccl_qual_search(cclp, "term", 4, seq);
1139             if (!qa[0])
1140                 break;
1141
1142             cclp->look_token = lookahead;
1143
1144             node_sub = search_terms(cclp, qa);
1145             if (!node_sub)
1146             {
1147                 ccl_rpn_delete(node);
1148                 return 0;
1149             }
1150             if (node)
1151             {
1152                 struct ccl_rpn_node *node_this =
1153                     ccl_rpn_node_create(CCL_RPN_OR);
1154                 node_this->u.p[0] = node;
1155                 node_this->u.p[1] = node_sub;
1156                 node_this->u.p[2] = 0;
1157                 node = node_this;
1158             }
1159             else
1160                 node = node_sub;
1161         }
1162         if (!node)
1163             node = search_terms(cclp, 0);
1164         return node;
1165     }
1166 }
1167
1168 /**
1169  * find_spec: Parse CCL find specification
1170  * cclp:   CCL Parser
1171  * qa:     Qualifier attributes already applied.
1172  * return: pointer to node(s); NULL on error.
1173  */
1174 static struct ccl_rpn_node *find_spec(CCL_parser cclp, ccl_qualifier_t *qa)
1175 {
1176     struct ccl_rpn_node *p1, *p2, *pn;
1177     if (!(p1 = search_elements(cclp, qa)))
1178         return NULL;
1179     while (1)
1180     {
1181         switch (KIND)
1182         {
1183         case CCL_TOK_AND:
1184             ADVANCE;
1185             p2 = search_elements(cclp, qa);
1186             if (!p2)
1187             {
1188                 ccl_rpn_delete(p1);
1189                 return NULL;
1190             }
1191             pn = ccl_rpn_node_create(CCL_RPN_AND);
1192             pn->u.p[0] = p1;
1193             pn->u.p[1] = p2;
1194             pn->u.p[2] = 0;
1195             p1 = pn;
1196             continue;
1197         case CCL_TOK_OR:
1198             ADVANCE;
1199             p2 = search_elements(cclp, qa);
1200             if (!p2)
1201             {
1202                 ccl_rpn_delete(p1);
1203                 return NULL;
1204             }
1205             pn = ccl_rpn_node_create(CCL_RPN_OR);
1206             pn->u.p[0] = p1;
1207             pn->u.p[1] = p2;
1208             pn->u.p[2] = 0;
1209             p1 = pn;
1210             continue;
1211         case CCL_TOK_NOT:
1212             ADVANCE;
1213             p2 = search_elements(cclp, qa);
1214             if (!p2)
1215             {
1216                 ccl_rpn_delete(p1);
1217                 return NULL;
1218             }
1219             pn = ccl_rpn_node_create(CCL_RPN_NOT);
1220             pn->u.p[0] = p1;
1221             pn->u.p[1] = p2;
1222             pn->u.p[2] = 0;
1223             p1 = pn;
1224             continue;
1225         }
1226         break;
1227     }
1228     return p1;
1229 }
1230
1231 struct ccl_rpn_node *ccl_parser_find_str(CCL_parser cclp, const char *str)
1232 {
1233     struct ccl_rpn_node *p;
1234     struct ccl_token *list = ccl_parser_tokenize(cclp, str);
1235     p = ccl_parser_find_token(cclp, list);
1236     ccl_token_del(list);
1237     return p;
1238 }
1239
1240 struct ccl_rpn_node *ccl_parser_find_token(CCL_parser cclp,
1241                                            struct ccl_token *list)
1242 {
1243     struct ccl_rpn_node *p;
1244
1245     cclp->look_token = list;
1246     p = find_spec(cclp, NULL);
1247     if (p && KIND != CCL_TOK_EOL)
1248     {
1249         if (KIND == CCL_TOK_RP)
1250             cclp->error_code = CCL_ERR_BAD_RP;
1251         else
1252             cclp->error_code = CCL_ERR_OP_EXPECTED;
1253         ccl_rpn_delete(p);
1254         p = NULL;
1255     }
1256     cclp->error_pos = cclp->look_token->name;
1257     if (p)
1258         cclp->error_code = CCL_ERR_OK;
1259     else
1260         cclp->error_code = cclp->error_code;
1261     return p;
1262 }
1263
1264 /**
1265  * ccl_find_str: Parse CCL find - string representation
1266  * bibset:  Bibset to be used for the parsing
1267  * str:     String to be parsed
1268  * error:   Pointer to integer. Holds error no. on completion.
1269  * pos:     Pointer to char position. Holds approximate error position.
1270  * return:  RPN tree on successful completion; NULL otherwise.
1271  */
1272 struct ccl_rpn_node *ccl_find_str(CCL_bibset bibset, const char *str,
1273                                   int *error, int *pos)
1274 {
1275     CCL_parser cclp = ccl_parser_create(bibset);
1276     struct ccl_token *list;
1277     struct ccl_rpn_node *p;
1278
1279     list = ccl_parser_tokenize(cclp, str);
1280     p = ccl_parser_find_token(cclp, list);
1281
1282     *error = cclp->error_code;
1283     if (*error)
1284         *pos = cclp->error_pos - str;
1285     ccl_parser_destroy(cclp);
1286     ccl_token_del(list);
1287     return p;
1288 }
1289
1290 /*
1291  * Local variables:
1292  * c-basic-offset: 4
1293  * c-file-style: "Stroustrup"
1294  * indent-tabs-mode: nil
1295  * End:
1296  * vim: shiftwidth=4 tabstop=8 expandtab
1297  */
1298