ccl/cclfind.c

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