ccl/cclfind.c

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