ccl/cclfind.c

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