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