ccl/cclfind.c

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