ccl/cclfind.c

   1 /* CCL find (to rpn conversion)
   2  * Europagate, 1995
   3  *
   4  * $Log: cclfind.c,v $
   5  * Revision 1.11  1995/02/23 08:31:59  adam
   6  * Changed header.
   7  *
   8  * Revision 1.9  1995/02/16  13:20:06  adam
   9  * Spell fix.
  10  *
  11  * Revision 1.8  1995/02/14  19:59:42  adam
  12  * Removed a syntax error.
  13  *
  14  * Revision 1.7  1995/02/14  19:55:10  adam
  15  * Header files ccl.h/cclp.h are gone! They have been merged an
  16  * moved to ../include/ccl.h.
  17  * Node kind(s) in ccl_rpn_node have changed names.
  18  *
  19  * Revision 1.6  1995/02/14  16:20:55  adam
  20  * Qualifiers are read from a file now.
  21  *
  22  * Revision 1.5  1995/02/14  14:12:41  adam
  23  * Ranges for ordered qualfiers implemented (e.g. pd=1980-1990).
  24  *
  25  * Revision 1.4  1995/02/14  13:16:29  adam
  26  * Left and/or right truncation implemented.
  27  *
  28  * Revision 1.3  1995/02/14  10:25:56  adam
  29  * The constructions 'qualifier rel term ...' implemented.
  30  *
  31  * Revision 1.2  1995/02/13  15:15:07  adam
  32  * Added handling of qualifiers. Not finished yet.
  33  *
  34  * Revision 1.1  1995/02/13  12:35:20  adam
  35  * First version of CCL. Qualifiers aren't handled yet.
  36  *
  37  */
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <assert.h>
  42 #include <string.h>
  43
  44 #include <ccl.h>
  45
  46 static struct ccl_token *look_token;
  47 static int ccl_error;
  48 static CCL_bibset bibset;
  49
  50 #define KIND (look_token->kind)
  51 #define ADVANCE look_token = look_token->next
  52 #define ADVX(x) x=(x)->next
  53
  54 static struct ccl_rpn_attr *qual_val (struct ccl_rpn_attr *list, int type)
  55 {
  56     while (list)
  57     {
  58         if (list->type == type)
  59             return list;
  60         list = list->next;
  61     }
  62     return NULL;
  63 }
  64
  65 static int qual_val_type (struct ccl_rpn_attr *list, int type, int value)
  66 {
  67     while (list)
  68     {
  69         if (list->type == type && list->value == value)
  70             return 1;
  71         list = list->next;
  72     }
  73     return 0;
  74 }
  75
  76 static void strxcat (char *n, const char *src, int len)
  77 {
  78     while (*n)
  79         n++;
  80     while (--len >= 0)
  81         *n++ = *src++;
  82     *n = '\0';
  83 }
  84
  85 static char *copy_token_name (struct ccl_token *tp)
  86 {
  87     char *str = malloc (tp->len + 1);
  88     assert (str);
  89     memcpy (str, tp->name, tp->len);
  90     str[tp->len] = '\0';
  91     return str;
  92 }
  93
  94 static struct ccl_rpn_node *mk_node (enum rpn_node_kind kind)
  95 {
  96     struct ccl_rpn_node *p;
  97     p = malloc (sizeof(*p));
  98     assert (p);
  99     p->kind = kind;
 100     return p;
 101 }
 102
 103 void ccl_rpn_delete (struct ccl_rpn_node *rpn)
 104 {
 105     struct ccl_rpn_attr *attr, *attr1;
 106     if (!rpn)
 107         return;
 108     switch (rpn->kind)
 109     {
 110     case CCL_RPN_AND:
 111     case CCL_RPN_OR:
 112     case CCL_RPN_NOT:
 113         ccl_rpn_delete (rpn->u.p[0]);
 114         ccl_rpn_delete (rpn->u.p[1]);
 115         break;
 116     case CCL_RPN_TERM:
 117         free (rpn->u.t.term);
 118         for (attr = rpn->u.t.attr_list; attr; attr = attr1)
 119         {
 120             attr1 = attr->next;
 121             free (attr);
 122         }
 123         break;
 124     case CCL_RPN_SET:
 125         free (rpn->u.setname);
 126         break;
 127     case CCL_RPN_PROX:
 128         ccl_rpn_delete (rpn->u.p[0]);
 129         ccl_rpn_delete (rpn->u.p[1]);
 130         break;
 131     }
 132     free (rpn);
 133 }
 134
 135 static struct ccl_rpn_node *find_spec (struct ccl_rpn_attr **qa);
 136 static struct ccl_rpn_node *search_terms (struct ccl_rpn_attr **qa);
 137
 138 static void add_attr (struct ccl_rpn_node *p, int type, int value)
 139 {
 140     struct ccl_rpn_attr *n;
 141
 142     n = malloc (sizeof(*n));
 143     assert (n);
 144     n->type = type;
 145     n->value = value;
 146     n->next = p->u.t.attr_list;
 147     p->u.t.attr_list = n;
 148 }
 149
 150 static struct ccl_rpn_node *search_term (struct ccl_rpn_attr **qa)
 151 {
 152     struct ccl_rpn_node *p;
 153     struct ccl_rpn_attr *attr;
 154     struct ccl_token *lookahead = look_token;
 155     int len = 0;
 156     int no, i;
 157     int left_trunc = 0;
 158     int right_trunc = 0;
 159     int mid_trunc = 0;
 160
 161     if (KIND != CCL_TOK_TERM)
 162     {
 163         ccl_error = CCL_ERR_TERM_EXPECTED;
 164         return NULL;
 165     }
 166     for (no = 0; lookahead->kind == CCL_TOK_TERM; no++)
 167     {
 168         for (i = 0; i<lookahead->len; i++)
 169             if (lookahead->name[i] == '?')
 170             {
 171                 if (no == 0 && i == 0 && lookahead->len >= 1)
 172                     left_trunc = 1;
 173                 else if (lookahead->next->kind != CCL_TOK_TERM &&
 174                          i == lookahead->len-1 && i >= 1)
 175                     right_trunc = 1;
 176                 else
 177                     mid_trunc = 1;
 178             }
 179         len += 1+lookahead->len;
 180         lookahead = lookahead->next;
 181     }
 182     p = mk_node (CCL_RPN_TERM);
 183     p->u.t.term = malloc (len);
 184     assert (p->u.t.term);
 185     p->u.t.attr_list = NULL;
 186     p->u.t.term[0] = '\0';
 187     for (i = 0; i<no; i++)
 188     {
 189         const char *src_str = look_token->name;
 190         int src_len = look_token->len;
 191
 192         if (i == 0 && left_trunc)
 193         {
 194             src_len--;
 195             src_str++;
 196         }
 197         else if (i == no-1 && right_trunc)
 198             src_len--;
 199         if (i)
 200             strcat (p->u.t.term, " ");
 201         strxcat (p->u.t.term, src_str, src_len);
 202         ADVANCE;
 203     }
 204     if (qa)
 205     {
 206         int i;
 207         for (i=0; qa[i]; i++)
 208         {
 209             struct ccl_rpn_attr *attr;
 210
 211             for (attr = qa[i]; attr; attr = attr->next)
 212                 if (attr->value > 0)
 213                     add_attr (p, attr->type, attr->value);
 214         }
 215         attr = qa[0];
 216     }
 217     else
 218         attr = ccl_qual_search (bibset, "term", 4);
 219     if (attr && qual_val_type (attr, CCL_BIB1_STR, CCL_BIB1_STR_WP))
 220     {
 221         if (no == 1)
 222             add_attr (p, CCL_BIB1_STR, 2);
 223         else
 224             add_attr (p, CCL_BIB1_STR, 1);
 225     }
 226     if (left_trunc && right_trunc)
 227     {
 228         if (attr && !qual_val_type (attr, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_BOTH))
 229         {
 230             ccl_error = CCL_ERR_TRUNC_NOT_BOTH;
 231             if (qa)
 232                 free (qa);
 233             ccl_rpn_delete (p);
 234             return NULL;
 235         }
 236         add_attr (p, CCL_BIB1_TRU, 3);
 237     }
 238     else if (right_trunc)
 239     {
 240         if (attr && !qual_val_type (attr, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_RIGHT))
 241         {
 242             ccl_error = CCL_ERR_TRUNC_NOT_RIGHT;
 243             if (qa)
 244                 free (qa);
 245             ccl_rpn_delete (p);
 246             return NULL;
 247         }
 248         add_attr (p, CCL_BIB1_TRU, 1);
 249     }
 250     else if (left_trunc)
 251     {
 252         if (attr && !qual_val_type (attr, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_LEFT))
 253         {
 254             ccl_error = CCL_ERR_TRUNC_NOT_LEFT;
 255             if (qa)
 256                 free (qa);
 257             ccl_rpn_delete (p);
 258             return NULL;
 259         }
 260         add_attr (p, CCL_BIB1_TRU, 2);
 261     }
 262     else
 263     {
 264         if (attr && qual_val_type (attr, CCL_BIB1_TRU, CCL_BIB1_TRU_CAN_NONE))
 265             add_attr (p, CCL_BIB1_TRU, 100);
 266     }
 267     return p;
 268 }
 269
 270 static struct ccl_rpn_node *qualifiers (struct ccl_token *la,
 271                                         struct ccl_rpn_attr **qa)
 272 {
 273     struct ccl_token *lookahead = look_token;
 274     struct ccl_rpn_attr **ap;
 275     int no = 1;
 276     int i, rel;
 277     struct ccl_rpn_attr *attr;
 278
 279     if (qa)
 280     {
 281         ccl_error = CCL_ERR_DOUBLE_QUAL;
 282         return NULL;
 283     }
 284     for (lookahead = look_token; lookahead != la; lookahead=lookahead->next)
 285         no++;
 286     ap = malloc (no * sizeof(*ap));
 287     assert (ap);
 288     for (i=0; look_token != la; i++)
 289     {
 290         ap[i] = ccl_qual_search (bibset, look_token->name, look_token->len);
 291         if (!ap[i])
 292         {
 293             ccl_error = CCL_ERR_UNKNOWN_QUAL;
 294             free (ap);
 295             return NULL;
 296         }
 297         ADVANCE;
 298         if (KIND == CCL_TOK_COMMA)
 299             ADVANCE;
 300     }
 301     ap[i] = NULL;
 302     if (! (attr = qual_val (ap[0], CCL_BIB1_REL)) ||
 303         attr->value != CCL_BIB1_REL_ORDER)
 304     {
 305         /* unordered relation */
 306         struct ccl_rpn_node *p;
 307         if (KIND != CCL_TOK_EQ)
 308         {
 309             ccl_error = CCL_ERR_EQ_EXPECTED;
 310             free (ap);
 311             return NULL;
 312         }
 313         ADVANCE;
 314         if (KIND == CCL_TOK_LP)
 315         {
 316             ADVANCE;
 317             if (!(p = find_spec (ap)))
 318             {
 319                 free (ap);
 320                 return NULL;
 321             }
 322             if (KIND != CCL_TOK_RP)
 323             {
 324                 ccl_error = CCL_ERR_RP_EXPECTED;
 325                 ccl_rpn_delete (p);
 326                 free (ap);
 327                 return NULL;
 328             }
 329             ADVANCE;
 330         }
 331         else
 332             p = search_terms (ap);
 333         free (ap);
 334         return p;
 335     }
 336     rel = 0;
 337     if (look_token->len == 1)
 338     {
 339         if (look_token->name[0] == '<')
 340             rel = 1;
 341         else if (look_token->name[0] == '=')
 342             rel = 3;
 343         else if (look_token->name[0] == '>')
 344             rel = 5;
 345     }
 346     else if (look_token->len == 2)
 347     {
 348         if (!memcmp (look_token->name, "<=", 2))
 349             rel = 2;
 350         else if (!memcmp (look_token->name, ">=", 2))
 351             rel = 4;
 352         else if (!memcmp (look_token->name, "<>", 2))
 353             rel = 6;
 354     }
 355     if (!rel)
 356         ccl_error = CCL_ERR_BAD_RELATION;
 357     else
 358     {
 359         struct ccl_rpn_node *p;
 360
 361         ADVANCE;                      /* skip relation */
 362         if (KIND == CCL_TOK_TERM)
 363         {
 364             struct ccl_rpn_node *p1;
 365             p1 = search_term (ap);
 366             if (KIND == CCL_TOK_MINUS)
 367             {
 368                 ADVANCE;                   /* skip '-' */
 369                 if (KIND == CCL_TOK_TERM)  /* = term - term  ? */
 370                 {
 371                     struct ccl_rpn_node *p2;
 372
 373                     p2 = search_term (ap);
 374                     p = mk_node (CCL_RPN_AND);
 375                     p->u.p[0] = p1;
 376                     add_attr (p1, CCL_BIB1_REL, 4);
 377                     p->u.p[1] = p2;
 378                     add_attr (p2, CCL_BIB1_REL, 2);
 379                     free (ap);
 380                     return p;
 381                 }
 382                 else                       /* = term -    */
 383                 {
 384                     add_attr (p1, CCL_BIB1_REL, 4);
 385                     free (ap);
 386                     return p1;
 387                 }
 388             }
 389             else
 390             {
 391                 add_attr (p1, CCL_BIB1_REL, rel);
 392                 free (ap);
 393                 return p1;
 394             }
 395         }
 396         else if (KIND == CCL_TOK_MINUS)   /* = - term  ? */
 397         {
 398             ADVANCE;
 399             p = search_term (ap);
 400             add_attr (p, CCL_BIB1_REL, 2);
 401             free (ap);
 402             return p;
 403         }
 404         ccl_error = CCL_ERR_TERM_EXPECTED;
 405     }
 406     free (ap);
 407     return NULL;
 408 }
 409
 410 static struct ccl_rpn_node *search_terms (struct ccl_rpn_attr **qa)
 411 {
 412     struct ccl_rpn_node *p1, *p2, *pn;
 413     p1 = search_term (qa);
 414     if (!p1)
 415         return NULL;
 416     while (1)
 417     {
 418         if (KIND == CCL_TOK_PROX)
 419         {
 420             ADVANCE;
 421             p2 = search_term (qa);
 422             if (!p2)
 423             {
 424                 ccl_rpn_delete (p1);
 425                 return NULL;
 426             }
 427             pn = mk_node (CCL_RPN_PROX);
 428             pn->u.p[0] = p1;
 429             pn->u.p[1] = p2;
 430             p1 = pn;
 431         }
 432         else if (KIND == CCL_TOK_TERM)
 433         {
 434             p2 = search_term (qa);
 435             if (!p2)
 436             {
 437                 ccl_rpn_delete (p1);
 438                 return NULL;
 439             }
 440             pn = mk_node (CCL_RPN_PROX);
 441             pn->u.p[0] = p1;
 442             pn->u.p[1] = p2;
 443             p1 = pn;
 444         }
 445         else
 446             break;
 447     }
 448     return p1;
 449 }
 450
 451 static struct ccl_rpn_node *search_elements (struct ccl_rpn_attr **qa)
 452 {
 453     struct ccl_rpn_node *p1;
 454     struct ccl_token *lookahead;
 455     if (KIND == CCL_TOK_LP)
 456     {
 457         ADVANCE;
 458         p1 = find_spec (qa);
 459         if (!p1)
 460             return NULL;
 461         if (KIND != CCL_TOK_RP)
 462         {
 463             ccl_error = CCL_ERR_RP_EXPECTED;
 464             ccl_rpn_delete (p1);
 465             return NULL;
 466         }
 467         ADVANCE;
 468         return p1;
 469     }
 470     else if (KIND == CCL_TOK_SET)
 471     {
 472         ADVANCE;
 473         if (KIND == CCL_TOK_EQ)
 474             ADVANCE;
 475         if (KIND != CCL_TOK_TERM)
 476         {
 477             ccl_error = CCL_ERR_SETNAME_EXPECTED;
 478             return NULL;
 479         }
 480         p1 = mk_node (CCL_RPN_SET);
 481         p1->u.setname = copy_token_name (look_token);
 482         ADVANCE;
 483         return p1;
 484     }
 485     lookahead = look_token;
 486
 487     while (lookahead->kind==CCL_TOK_TERM || lookahead->kind==CCL_TOK_COMMA)
 488         lookahead = lookahead->next;
 489     if (lookahead->kind == CCL_TOK_REL || lookahead->kind == CCL_TOK_EQ)
 490         return qualifiers (lookahead, qa);
 491     return search_terms (qa);
 492 }
 493
 494 static struct ccl_rpn_node *find_spec (struct ccl_rpn_attr **qa)
 495 {
 496     struct ccl_rpn_node *p1, *p2, *pn;
 497     if (!(p1 = search_elements (qa)))
 498         return NULL;
 499     while (1)
 500     {
 501         switch (KIND)
 502         {
 503         case CCL_TOK_AND:
 504             ADVANCE;
 505             p2 = search_elements (qa);
 506             if (!p2)
 507             {
 508                 ccl_rpn_delete (p1);
 509                 return NULL;
 510             }
 511             pn = mk_node (CCL_RPN_AND);
 512             pn->u.p[0] = p1;
 513             pn->u.p[1] = p2;
 514             p1 = pn;
 515             continue;
 516         case CCL_TOK_OR:
 517             ADVANCE;
 518             p2 = search_elements (qa);
 519             if (!p2)
 520             {
 521                 ccl_rpn_delete (p1);
 522                 return NULL;
 523             }
 524             pn = mk_node (CCL_RPN_OR);
 525             pn->u.p[0] = p1;
 526             pn->u.p[1] = p2;
 527             p1 = pn;
 528             continue;
 529         case CCL_TOK_NOT:
 530             ADVANCE;
 531             p2 = search_elements (qa);
 532             if (!p2)
 533             {
 534                 ccl_rpn_delete (p1);
 535                 return NULL;
 536             }
 537             pn = mk_node (CCL_RPN_NOT);
 538             pn->u.p[0] = p1;
 539             pn->u.p[1] = p2;
 540             p1 = pn;
 541             continue;
 542         }
 543         break;
 544     }
 545     return p1;
 546 }
 547
 548 struct ccl_rpn_node *ccl_find (CCL_bibset abibset, struct ccl_token *list,
 549                                int *error, const char **pos)
 550 {
 551     struct ccl_rpn_node *p;
 552
 553     look_token = list;
 554     bibset = abibset;
 555     p = find_spec (NULL);
 556     if (p && KIND != CCL_TOK_EOL)
 557     {
 558         if (KIND == CCL_TOK_RP)
 559             ccl_error = CCL_ERR_BAD_RP;
 560         else
 561             ccl_error = CCL_ERR_OP_EXPECTED;
 562         ccl_rpn_delete (p);
 563         p = NULL;
 564     }
 565     *pos = look_token->name;
 566     if (p)
 567         *error = CCL_ERR_OK;
 568     else
 569         *error = ccl_error;
 570     return p;
 571 }
 572
 573 struct ccl_rpn_node *ccl_find_str (CCL_bibset bibset, const char *str,
 574                                    int *error, int *pos)
 575 {
 576     struct ccl_token *list, *li;
 577     struct ccl_rpn_node *rpn;
 578     const char *char_pos;
 579
 580     list = ccl_tokenize (str);
 581 #if 0
 582     for (li = list; li; li = li->next)
 583         printf ("kind=%d, str='%.*s'\n", li->kind, li->len, li->name);
 584 #endif
 585     rpn = ccl_find (bibset, list, error, &char_pos);
 586     if (*error)
 587         *pos = char_pos - str;
 588     return rpn;
 589 }