ccl/cclfind.c

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