ccl/cclfind.c

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