ccl/cclfind.c

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