ccl/cclfind.c

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