ccl/cclfind.c

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