ccl/cclfind.c

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