ccl/cclfind.c

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