src/cclfind.c

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