common/recsel.c

   1 /* recsel.c - Record selection
   2  * Copyright (C) 2014, 2016 Werner Koch
   3  *
   4  * This file is part of GnuPG.
   5  *
   6  * This file is free software; you can redistribute it and/or modify
   7  * it under the terms of either
   8  *
   9  *   - the GNU Lesser General Public License as published by the Free
  10  *     Software Foundation; either version 3 of the License, or (at
  11  *     your option) any later version.
  12  *
  13  * or
  14  *
  15  *   - the GNU General Public License as published by the Free
  16  *     Software Foundation; either version 2 of the License, or (at
  17  *     your option) any later version.
  18  *
  19  * or both in parallel, as here.
  20  *
  21  * This file is distributed in the hope that it will be useful,
  22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24  * GNU General Public License for more details.
  25  *
  26  * You should have received a copy of the GNU General Public License
  27  * along with this program; if not, see <https://www.gnu.org/licenses/>.
  28  */
  29
  30 #include <config.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <unistd.h>
  35 #include <errno.h>
  36
  37 #include "util.h"
  38 #include "recsel.h"
  39
  40 /* Select operators.  */
  41 typedef enum
  42   {
  43     SELECT_SAME,
  44     SELECT_SUB,
  45     SELECT_NONEMPTY,
  46     SELECT_ISTRUE,
  47     SELECT_EQ, /* Numerically equal.  */
  48     SELECT_LE,
  49     SELECT_GE,
  50     SELECT_LT,
  51     SELECT_GT,
  52     SELECT_STRLE, /* String is less or equal.  */
  53     SELECT_STRGE,
  54     SELECT_STRLT,
  55     SELECT_STRGT
  56   } select_op_t;
  57
  58
  59 /* Definition for a select expression.  */
  60 struct recsel_expr_s
  61 {
  62   recsel_expr_t next;
  63   select_op_t op;       /* Operation code.  */
  64   unsigned int not:1;   /* Negate operators. */
  65   unsigned int disjun:1;/* Start of a disjunction.  */
  66   unsigned int xcase:1; /* String match is case sensitive.  */
  67   const char *value;    /* (Points into NAME.)  */
  68   long numvalue;        /* strtol of VALUE.  */
  69   char name[1];         /* Name of the property.  */
  70 };
  71
  72
  73 /* Helper */
  74 static inline gpg_error_t
  75 my_error_from_syserror (void)
  76 {
  77   return gpg_err_make (default_errsource, gpg_err_code_from_syserror ());
  78 }
  79
  80 /* Helper */
  81 static inline gpg_error_t
  82 my_error (gpg_err_code_t ec)
  83 {
  84   return gpg_err_make (default_errsource, ec);
  85 }
  86
  87
  88 /* This is a case-sensitive version of our memistr.  I wonder why no
  89  * standard function memstr exists but I better do not use the name
  90  * memstr to avoid future conflicts.
  91  *
  92  * FIXME: Move this to a stringhelp.c
  93  */
  94 static const char *
  95 my_memstr (const void *buffer, size_t buflen, const char *sub)
  96 {
  97   const unsigned char *buf = buffer;
  98   const unsigned char *t = (const unsigned char *)buf;
  99   const unsigned char *s = (const unsigned char *)sub;
 100   size_t n = buflen;
 101
 102   for ( ; n ; t++, n-- )
 103     {
 104       if (*t == *s)
 105         {
 106           for (buf = t++, buflen = n--, s++; n && *t ==*s; t++, s++, n--)
 107             ;
 108           if (!*s)
 109             return (const char*)buf;
 110           t = (const unsigned char *)buf;
 111           s = (const unsigned char *)sub ;
 112           n = buflen;
 113         }
 114     }
 115   return NULL;
 116 }
 117
 118
 119 /* Return a pointer to the next logical connection operator or NULL if
 120  * none.  */
 121 static char *
 122 find_next_lc (char *string)
 123 {
 124   char *p1, *p2;
 125
 126   p1 = strchr (string, '&');
 127   if (p1 && p1[1] != '&')
 128     p1 = NULL;
 129   p2 = strchr (string, '|');
 130   if (p2 && p2[1] != '|')
 131     p2 = NULL;
 132   if (p1 && !p2)
 133     return p1;
 134   if (!p1)
 135     return p2;
 136   return p1 < p2 ? p1 : p2;
 137 }
 138
 139
 140 /* Parse an expression.  The expression syntax is:
 141  *
 142  *   [<lc>] {{<flag>} PROPNAME <op> VALUE [<lc>]}
 143  *
 144  * A [] indicates an optional part, a {} a repetition.  PROPNAME and
 145  * VALUE may not be the empty string.  White space between the
 146  * elements is ignored.  Numerical values are computed as long int;
 147  * standard C notation applies.  <lc> is the logical connection
 148  * operator; either "&&" for a conjunction or "||" for a disjunction.
 149  * A conjunction is assumed at the begin of an expression and
 150  * conjunctions have higher precedence than disjunctions.  If VALUE
 151  * starts with one of the characters used in any <op> a space after
 152  * the <op> is required.  A VALUE is terminated by an <lc> unless the
 153  * "--" <flag> is used in which case the VALUE spans to the end of the
 154  * expression.  <op> may be any of
 155  *
 156  *   =~  Substring must match
 157  *   !~  Substring must not match
 158  *   =   The full string must match
 159  *   <>  The full string must not match
 160  *   ==  The numerical value must match
 161  *   !=  The numerical value must not match
 162  *   <=  The numerical value of the field must be LE than the value.
 163  *   <   The numerical value of the field must be LT than the value.
 164  *   >=  The numerical value of the field must be GT than the value.
 165  *   >=  The numerical value of the field must be GE than the value.
 166  *   -n  True if value is not empty (no VALUE parameter allowed).
 167  *   -z  True if value is empty (no VALUE parameter allowed).
 168  *   -t  Alias for "PROPNAME != 0" (no VALUE parameter allowed).
 169  *   -f  Alias for "PROPNAME == 0" (no VALUE parameter allowed).
 170  *
 171  * Values for <flag> must be space separated and any of:
 172  *
 173  *   --  VALUE spans to the end of the expression.
 174  *   -c  The string match in this part is done case-sensitive.
 175  *
 176  * For example four calls to recsel_parse_expr() with these values for
 177  * EXPR
 178  *
 179  *  "uid =~ Alfa"
 180  *  "&& uid !~ Test"
 181  *  "|| uid =~ Alpha"
 182  *  "uid !~ Test"
 183  *
 184  * or the equivalent expression
 185  *
 186  *  "uid =~ Alfa" && uid !~ Test" || uid =~ Alpha" && "uid !~ Test"
 187  *
 188  * are making a selector for records where the "uid" property contains
 189  * the strings "Alfa" or "Alpha" but not the String "test".
 190  *
 191  * The caller must pass the address of a selector variable to this
 192  * function and initialize the value of the function to NULL before
 193  * the first call.  recset_release needs to be called to free the
 194  * selector.
 195  */
 196 gpg_error_t
 197 recsel_parse_expr (recsel_expr_t *selector, const char *expression)
 198 {
 199   recsel_expr_t se_head = NULL;
 200   recsel_expr_t se, se2;
 201   char *expr_buffer;
 202   char *expr;
 203   char *s0, *s;
 204   int toend = 0;
 205   int xcase = 0;
 206   int disjun = 0;
 207   char *next_lc = NULL;
 208
 209   while (*expression == ' ' || *expression == '\t')
 210     expression++;
 211
 212   expr_buffer = xtrystrdup (expression);
 213   if (!expr_buffer)
 214     return my_error_from_syserror ();
 215   expr = expr_buffer;
 216
 217   if (*expr == '|' && expr[1] == '|')
 218     {
 219       disjun = 1;
 220       expr += 2;
 221     }
 222   else if (*expr == '&' && expr[1] == '&')
 223     expr += 2;
 224
 225  next_term:
 226   while (*expr == ' ' || *expr == '\t')
 227     expr++;
 228
 229   while (*expr == '-')
 230     {
 231       switch (*++expr)
 232         {
 233         case '-': toend = 1; break;
 234         case 'c': xcase = 1; break;
 235         default:
 236           log_error ("invalid flag '-%c' in expression\n", *expr);
 237           recsel_release (se_head);
 238           xfree (expr_buffer);
 239           return my_error (GPG_ERR_INV_FLAG);
 240         }
 241       expr++;
 242       while (*expr == ' ' || *expr == '\t')
 243         expr++;
 244     }
 245
 246   next_lc = toend? NULL : find_next_lc (expr);
 247   if (next_lc)
 248     *next_lc = 0;  /* Terminate this term.  */
 249
 250   se = xtrymalloc (sizeof *se + strlen (expr));
 251   if (!se)
 252     return my_error_from_syserror ();
 253   strcpy (se->name, expr);
 254   se->next = NULL;
 255   se->not = 0;
 256   se->disjun = disjun;
 257   se->xcase = xcase;
 258
 259   if (!se_head)
 260     se_head = se;
 261   else
 262     {
 263       for (se2 = se_head; se2->next; se2 = se2->next)
 264         ;
 265       se2->next = se;
 266     }
 267
 268
 269   s = strpbrk (expr, "=<>!~-");
 270   if (!s || s == expr )
 271     {
 272       log_error ("no field name given in expression\n");
 273       recsel_release (se_head);
 274       xfree (expr_buffer);
 275       return my_error (GPG_ERR_NO_NAME);
 276     }
 277   s0 = s;
 278
 279   if (!strncmp (s, "=~", 2))
 280     {
 281       se->op = SELECT_SUB;
 282       s += 2;
 283     }
 284   else if (!strncmp (s, "!~", 2))
 285     {
 286       se->op = SELECT_SUB;
 287       se->not = 1;
 288       s += 2;
 289     }
 290   else if (!strncmp (s, "<>", 2))
 291     {
 292       se->op = SELECT_SAME;
 293       se->not = 1;
 294       s += 2;
 295     }
 296   else if (!strncmp (s, "==", 2))
 297     {
 298       se->op = SELECT_EQ;
 299       s += 2;
 300     }
 301   else if (!strncmp (s, "!=", 2))
 302     {
 303       se->op = SELECT_EQ;
 304       se->not = 1;
 305       s += 2;
 306     }
 307   else if (!strncmp (s, "<=", 2))
 308     {
 309       se->op = SELECT_LE;
 310       s += 2;
 311     }
 312   else if (!strncmp (s, ">=", 2))
 313     {
 314       se->op = SELECT_GE;
 315       s += 2;
 316     }
 317   else if (!strncmp (s, "<", 1))
 318     {
 319       se->op = SELECT_LT;
 320       s += 1;
 321     }
 322   else if (!strncmp (s, ">", 1))
 323     {
 324       se->op = SELECT_GT;
 325       s += 1;
 326     }
 327   else if (!strncmp (s, "=", 1))
 328     {
 329       se->op = SELECT_SAME;
 330       s += 1;
 331     }
 332   else if (!strncmp (s, "-z", 2))
 333     {
 334       se->op = SELECT_NONEMPTY;
 335       se->not = 1;
 336       s += 2;
 337     }
 338   else if (!strncmp (s, "-n", 2))
 339     {
 340       se->op = SELECT_NONEMPTY;
 341       s += 2;
 342     }
 343   else if (!strncmp (s, "-f", 2))
 344     {
 345       se->op = SELECT_ISTRUE;
 346       se->not = 1;
 347       s += 2;
 348     }
 349   else if (!strncmp (s, "-t", 2))
 350     {
 351       se->op = SELECT_ISTRUE;
 352       s += 2;
 353     }
 354   else if (!strncmp (s, "-le", 3))
 355     {
 356       se->op = SELECT_STRLE;
 357       s += 3;
 358     }
 359   else if (!strncmp (s, "-ge", 3))
 360     {
 361       se->op = SELECT_STRGE;
 362       s += 3;
 363     }
 364   else if (!strncmp (s, "-lt", 3))
 365     {
 366       se->op = SELECT_STRLT;
 367       s += 3;
 368     }
 369   else if (!strncmp (s, "-gt", 3))
 370     {
 371       se->op = SELECT_STRGT;
 372       s += 3;
 373     }
 374   else
 375     {
 376       log_error ("invalid operator in expression\n");
 377       recsel_release (se_head);
 378       xfree (expr_buffer);
 379       return my_error (GPG_ERR_INV_OP);
 380     }
 381
 382   /* We require that a space is used if the value starts with any of
 383      the operator characters.  */
 384   if (se->op == SELECT_NONEMPTY || se->op == SELECT_ISTRUE)
 385     ;
 386   else if (strchr ("=<>!~", *s))
 387     {
 388       log_error ("invalid operator in expression\n");
 389       recsel_release (se_head);
 390       xfree (expr_buffer);
 391       return my_error (GPG_ERR_INV_OP);
 392     }
 393
 394   while (*s == ' ' || *s == '\t')
 395     s++;
 396
 397   if (se->op == SELECT_NONEMPTY || se->op == SELECT_ISTRUE)
 398     {
 399       if (*s)
 400         {
 401           log_error ("value given for -n or -z\n");
 402           recsel_release (se_head);
 403           xfree (expr_buffer);
 404           return my_error (GPG_ERR_SYNTAX);
 405         }
 406     }
 407   else
 408     {
 409       if (!*s)
 410         {
 411           log_error ("no value given in expression\n");
 412           recsel_release (se_head);
 413           xfree (expr_buffer);
 414           return my_error (GPG_ERR_MISSING_VALUE);
 415         }
 416     }
 417
 418   se->name[s0 - expr] = 0;
 419   trim_spaces (se->name);
 420   if (!se->name[0])
 421     {
 422       log_error ("no field name given in expression\n");
 423       recsel_release (se_head);
 424       xfree (expr_buffer);
 425       return my_error (GPG_ERR_NO_NAME);
 426     }
 427
 428   trim_spaces (se->name + (s - expr));
 429   se->value = se->name + (s - expr);
 430   if (!se->value[0] && !(se->op == SELECT_NONEMPTY || se->op == SELECT_ISTRUE))
 431     {
 432       log_error ("no value given in expression\n");
 433       recsel_release (se_head);
 434       xfree (expr_buffer);
 435       return my_error (GPG_ERR_MISSING_VALUE);
 436     }
 437
 438   se->numvalue = strtol (se->value, NULL, 0);
 439
 440   if (next_lc)
 441     {
 442       disjun = next_lc[1] == '|';
 443       expr = next_lc + 2;
 444       goto next_term;
 445     }
 446
 447   /* Read:y Append to passes last selector.  */
 448   if (!*selector)
 449     *selector = se_head;
 450   else
 451     {
 452       for (se2 = *selector; se2->next; se2 = se2->next)
 453         ;
 454       se2->next = se_head;
 455     }
 456
 457   xfree (expr_buffer);
 458   return 0;
 459 }
 460
 461
 462 void
 463 recsel_release (recsel_expr_t a)
 464 {
 465   while (a)
 466     {
 467       recsel_expr_t tmp = a->next;
 468       xfree (a);
 469       a = tmp;
 470     }
 471 }
 472
 473
 474 void
 475 recsel_dump (recsel_expr_t selector)
 476 {
 477   recsel_expr_t se;
 478
 479   log_debug ("--- Begin selectors ---\n");
 480   for (se = selector; se; se = se->next)
 481     {
 482       log_debug ("%s %s %s %s '%s'\n",
 483                  se==selector? "  ": (se->disjun? "||":"&&"),
 484                  se->xcase?  "-c":"  ",
 485                  se->name,
 486                  se->op == SELECT_SAME?    (se->not? "<>":"= "):
 487                  se->op == SELECT_SUB?     (se->not? "!~":"=~"):
 488                  se->op == SELECT_NONEMPTY?(se->not? "-z":"-n"):
 489                  se->op == SELECT_ISTRUE?  (se->not? "-f":"-t"):
 490                  se->op == SELECT_EQ?      (se->not? "!=":"=="):
 491                  se->op == SELECT_LT?      "< ":
 492                  se->op == SELECT_LE?      "<=":
 493                  se->op == SELECT_GT?      "> ":
 494                  se->op == SELECT_GE?      ">=":
 495                  se->op == SELECT_STRLT?   "-lt":
 496                  se->op == SELECT_STRLE?   "-le":
 497                  se->op == SELECT_STRGT?   "-gt":
 498                  se->op == SELECT_STRGE?   "-ge":
 499                  /**/                      "[oops]",
 500                  se->value);
 501     }
 502   log_debug ("--- End selectors ---\n");
 503 }
 504
 505
 506 /* Return true if the record RECORD has been selected.  The GETVAL
 507  * function is called with COOKIE and the NAME of a property used in
 508  * the expression.  */
 509 int
 510 recsel_select (recsel_expr_t selector,
 511                const char *(*getval)(void *cookie, const char *propname),
 512                void *cookie)
 513 {
 514   recsel_expr_t se;
 515   const char *value;
 516   size_t selen, valuelen;
 517   long numvalue;
 518   int result = 1;
 519
 520   se = selector;
 521   while (se)
 522     {
 523       value = getval? getval (cookie, se->name) : NULL;
 524       if (!value)
 525         value = "";
 526
 527       if (!*value)
 528         {
 529           /* Field is empty.  */
 530           result = 0;
 531         }
 532       else /* Field has a value.  */
 533         {
 534           valuelen = strlen (value);
 535           numvalue = strtol (value, NULL, 0);
 536           selen = strlen (se->value);
 537
 538           switch (se->op)
 539             {
 540             case SELECT_SAME:
 541               if (se->xcase)
 542                 result = (valuelen==selen && !memcmp (value,se->value,selen));
 543               else
 544                 result = (valuelen==selen && !memicmp (value,se->value,selen));
 545               break;
 546             case SELECT_SUB:
 547               if (se->xcase)
 548                 result = !!my_memstr (value, valuelen, se->value);
 549               else
 550                 result = !!memistr (value, valuelen, se->value);
 551               break;
 552             case SELECT_NONEMPTY:
 553               result = !!valuelen;
 554               break;
 555             case SELECT_ISTRUE:
 556               result = !!numvalue;
 557               break;
 558             case SELECT_EQ:
 559               result = (numvalue == se->numvalue);
 560               break;
 561             case SELECT_GT:
 562               result = (numvalue > se->numvalue);
 563               break;
 564             case SELECT_GE:
 565               result = (numvalue >= se->numvalue);
 566               break;
 567             case SELECT_LT:
 568               result = (numvalue < se->numvalue);
 569               break;
 570             case SELECT_LE:
 571               result = (numvalue <= se->numvalue);
 572               break;
 573             case SELECT_STRGT:
 574               if (se->xcase)
 575                 result = strcmp (value, se->value) > 0;
 576               else
 577                 result = strcasecmp (value, se->value) > 0;
 578               break;
 579             case SELECT_STRGE:
 580               if (se->xcase)
 581                 result = strcmp (value, se->value) >= 0;
 582               else
 583                 result = strcasecmp (value, se->value) >= 0;
 584               break;
 585             case SELECT_STRLT:
 586               if (se->xcase)
 587                 result = strcmp (value, se->value) < 0;
 588               else
 589                 result = strcasecmp (value, se->value) < 0;
 590               break;
 591             case SELECT_STRLE:
 592               if (se->xcase)
 593                 result = strcmp (value, se->value) <= 0;
 594               else
 595                 result = strcasecmp (value, se->value) <= 0;
 596               break;
 597             }
 598         }
 599
 600       if (se->not)
 601         result = !result;
 602
 603       if (result)
 604         {
 605           /* This expression evaluated to true.  See wether there are
 606              remaining expressions in this conjunction.  */
 607           if (!se->next || se->next->disjun)
 608             break; /* All expressions are true.  Return True.  */
 609           se = se->next;  /* Test the next.  */
 610         }
 611       else
 612         {
 613           /* This expression evaluated to false and thus the
 614            * conjunction evaluates to false.  We skip over the
 615            * remaining expressions of this conjunction and continue
 616            * with the next disjunction if any.  */
 617           do
 618             se = se->next;
 619           while (se && !se->disjun);
 620         }
 621     }
 622
 623   return result;
 624 }