Change all http://www.gnu.org in license notices to https://
[gnupg.git] / 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 }