src/cclfind.c

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