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
my_error_from_syserror(void)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
my_error(gpg_err_code_t ec)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 *
my_memstr(const void * buffer,size_t buflen,const char * sub)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 *
find_next_lc(char * string)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 * -t Do not trim leading and trailing spaces from VALUE.
176 * Note that a space after <op> is here required.
177 *
178 * For example four calls to recsel_parse_expr() with these values for
179 * EXPR
180 *
181 * "uid =~ Alfa"
182 * "&& uid !~ Test"
183 * "|| uid =~ Alpha"
184 * "uid !~ Test"
185 *
186 * or the equivalent expression
187 *
188 * "uid =~ Alfa" && uid !~ Test" || uid =~ Alpha" && "uid !~ Test"
189 *
190 * are making a selector for records where the "uid" property contains
191 * the strings "Alfa" or "Alpha" but not the String "test".
192 *
193 * The caller must pass the address of a selector variable to this
194 * function and initialize the value of the function to NULL before
195 * the first call. recset_release needs to be called to free the
196 * selector.
197 */
198 gpg_error_t
recsel_parse_expr(recsel_expr_t * selector,const char * expression)199 recsel_parse_expr (recsel_expr_t *selector, const char *expression)
200 {
201 recsel_expr_t se_head = NULL;
202 recsel_expr_t se, se2;
203 char *expr_buffer;
204 char *expr;
205 char *s0, *s;
206 int toend = 0;
207 int xcase = 0;
208 int notrim = 0;
209 int disjun = 0;
210 char *next_lc = NULL;
211
212 while (*expression == ' ' || *expression == '\t')
213 expression++;
214
215 expr_buffer = xtrystrdup (expression);
216 if (!expr_buffer)
217 return my_error_from_syserror ();
218 expr = expr_buffer;
219
220 if (*expr == '|' && expr[1] == '|')
221 {
222 disjun = 1;
223 expr += 2;
224 }
225 else if (*expr == '&' && expr[1] == '&')
226 expr += 2;
227
228 next_term:
229 while (*expr == ' ' || *expr == '\t')
230 expr++;
231
232 while (*expr == '-')
233 {
234 switch (*++expr)
235 {
236 case '-': toend = 1; break;
237 case 'c': xcase = 1; break;
238 case 't': notrim = 1; break;
239 default:
240 log_error ("invalid flag '-%c' in expression\n", *expr);
241 recsel_release (se_head);
242 xfree (expr_buffer);
243 return my_error (GPG_ERR_INV_FLAG);
244 }
245 expr++;
246 while (*expr == ' ' || *expr == '\t')
247 expr++;
248 }
249
250 next_lc = toend? NULL : find_next_lc (expr);
251 if (next_lc)
252 *next_lc = 0; /* Terminate this term. */
253
254 se = xtrymalloc (sizeof *se + strlen (expr));
255 if (!se)
256 {
257 gpg_error_t err = my_error_from_syserror ();
258
259 recsel_release (se_head);
260 xfree (expr_buffer);
261 return err;
262 }
263 strcpy (se->name, expr);
264 se->next = NULL;
265 se->not = 0;
266 se->disjun = disjun;
267 se->xcase = xcase;
268
269 if (!se_head)
270 se_head = se;
271 else
272 {
273 for (se2 = se_head; se2->next; se2 = se2->next)
274 ;
275 se2->next = se;
276 }
277
278
279 s = strpbrk (expr, "=<>!~-");
280 if (!s || s == expr )
281 {
282 log_error ("no field name given in expression\n");
283 recsel_release (se_head);
284 xfree (expr_buffer);
285 return my_error (GPG_ERR_NO_NAME);
286 }
287 s0 = s;
288
289 if (!strncmp (s, "=~", 2))
290 {
291 se->op = SELECT_SUB;
292 s += 2;
293 }
294 else if (!strncmp (s, "!~", 2))
295 {
296 se->op = SELECT_SUB;
297 se->not = 1;
298 s += 2;
299 }
300 else if (!strncmp (s, "<>", 2))
301 {
302 se->op = SELECT_SAME;
303 se->not = 1;
304 s += 2;
305 }
306 else if (!strncmp (s, "==", 2))
307 {
308 se->op = SELECT_EQ;
309 s += 2;
310 }
311 else if (!strncmp (s, "!=", 2))
312 {
313 se->op = SELECT_EQ;
314 se->not = 1;
315 s += 2;
316 }
317 else if (!strncmp (s, "<=", 2))
318 {
319 se->op = SELECT_LE;
320 s += 2;
321 }
322 else if (!strncmp (s, ">=", 2))
323 {
324 se->op = SELECT_GE;
325 s += 2;
326 }
327 else if (!strncmp (s, "<", 1))
328 {
329 se->op = SELECT_LT;
330 s += 1;
331 }
332 else if (!strncmp (s, ">", 1))
333 {
334 se->op = SELECT_GT;
335 s += 1;
336 }
337 else if (!strncmp (s, "=", 1))
338 {
339 se->op = SELECT_SAME;
340 s += 1;
341 }
342 else if (!strncmp (s, "-z", 2))
343 {
344 se->op = SELECT_NONEMPTY;
345 se->not = 1;
346 s += 2;
347 }
348 else if (!strncmp (s, "-n", 2))
349 {
350 se->op = SELECT_NONEMPTY;
351 s += 2;
352 }
353 else if (!strncmp (s, "-f", 2))
354 {
355 se->op = SELECT_ISTRUE;
356 se->not = 1;
357 s += 2;
358 }
359 else if (!strncmp (s, "-t", 2))
360 {
361 se->op = SELECT_ISTRUE;
362 s += 2;
363 }
364 else if (!strncmp (s, "-le", 3))
365 {
366 se->op = SELECT_STRLE;
367 s += 3;
368 }
369 else if (!strncmp (s, "-ge", 3))
370 {
371 se->op = SELECT_STRGE;
372 s += 3;
373 }
374 else if (!strncmp (s, "-lt", 3))
375 {
376 se->op = SELECT_STRLT;
377 s += 3;
378 }
379 else if (!strncmp (s, "-gt", 3))
380 {
381 se->op = SELECT_STRGT;
382 s += 3;
383 }
384 else
385 {
386 log_error ("invalid operator in expression\n");
387 recsel_release (se_head);
388 xfree (expr_buffer);
389 return my_error (GPG_ERR_INV_OP);
390 }
391
392 /* We require that a space is used if the value starts with any of
393 the operator characters. */
394 if (se->op == SELECT_NONEMPTY || se->op == SELECT_ISTRUE)
395 ;
396 else if (strchr ("=<>!~", *s))
397 {
398 log_error ("invalid operator in expression\n");
399 recsel_release (se_head);
400 xfree (expr_buffer);
401 return my_error (GPG_ERR_INV_OP);
402 }
403
404 if (*s == ' ' || *s == '\t')
405 s++;
406 if (!notrim)
407 while (*s == ' ' || *s == '\t')
408 s++;
409
410 if (se->op == SELECT_NONEMPTY || se->op == SELECT_ISTRUE)
411 {
412 if (*s)
413 {
414 log_error ("value given for -n or -z\n");
415 recsel_release (se_head);
416 xfree (expr_buffer);
417 return my_error (GPG_ERR_SYNTAX);
418 }
419 }
420 else
421 {
422 if (!*s)
423 {
424 log_error ("no value given in expression\n");
425 recsel_release (se_head);
426 xfree (expr_buffer);
427 return my_error (GPG_ERR_MISSING_VALUE);
428 }
429 }
430
431 se->name[s0 - expr] = 0;
432 trim_spaces (se->name);
433 if (!se->name[0])
434 {
435 log_error ("no field name given in expression\n");
436 recsel_release (se_head);
437 xfree (expr_buffer);
438 return my_error (GPG_ERR_NO_NAME);
439 }
440
441 if (!notrim)
442 trim_spaces (se->name + (s - expr));
443 se->value = se->name + (s - expr);
444 if (!se->value[0] && !(se->op == SELECT_NONEMPTY || se->op == SELECT_ISTRUE))
445 {
446 log_error ("no value given in expression\n");
447 recsel_release (se_head);
448 xfree (expr_buffer);
449 return my_error (GPG_ERR_MISSING_VALUE);
450 }
451
452 se->numvalue = strtol (se->value, NULL, 0);
453
454 if (next_lc)
455 {
456 disjun = next_lc[1] == '|';
457 expr = next_lc + 2;
458 goto next_term;
459 }
460
461 /* Read:y Append to passes last selector. */
462 if (!*selector)
463 *selector = se_head;
464 else
465 {
466 for (se2 = *selector; se2->next; se2 = se2->next)
467 ;
468 se2->next = se_head;
469 }
470
471 xfree (expr_buffer);
472 return 0;
473 }
474
475
476 void
recsel_release(recsel_expr_t a)477 recsel_release (recsel_expr_t a)
478 {
479 while (a)
480 {
481 recsel_expr_t tmp = a->next;
482 xfree (a);
483 a = tmp;
484 }
485 }
486
487
488 void
recsel_dump(recsel_expr_t selector)489 recsel_dump (recsel_expr_t selector)
490 {
491 recsel_expr_t se;
492
493 log_debug ("--- Begin selectors ---\n");
494 for (se = selector; se; se = se->next)
495 {
496 log_debug ("%s %s %s %s '%s'\n",
497 se==selector? " ": (se->disjun? "||":"&&"),
498 se->xcase? "-c":" ",
499 se->name,
500 se->op == SELECT_SAME? (se->not? "<>":"= "):
501 se->op == SELECT_SUB? (se->not? "!~":"=~"):
502 se->op == SELECT_NONEMPTY?(se->not? "-z":"-n"):
503 se->op == SELECT_ISTRUE? (se->not? "-f":"-t"):
504 se->op == SELECT_EQ? (se->not? "!=":"=="):
505 se->op == SELECT_LT? "< ":
506 se->op == SELECT_LE? "<=":
507 se->op == SELECT_GT? "> ":
508 se->op == SELECT_GE? ">=":
509 se->op == SELECT_STRLT? "-lt":
510 se->op == SELECT_STRLE? "-le":
511 se->op == SELECT_STRGT? "-gt":
512 se->op == SELECT_STRGE? "-ge":
513 /**/ "[oops]",
514 se->value);
515 }
516 log_debug ("--- End selectors ---\n");
517 }
518
519
520 /* Return true if the record RECORD has been selected. The GETVAL
521 * function is called with COOKIE and the NAME of a property used in
522 * the expression. */
523 int
recsel_select(recsel_expr_t selector,const char * (* getval)(void * cookie,const char * propname),void * cookie)524 recsel_select (recsel_expr_t selector,
525 const char *(*getval)(void *cookie, const char *propname),
526 void *cookie)
527 {
528 recsel_expr_t se;
529 const char *value;
530 size_t selen, valuelen;
531 long numvalue;
532 int result = 1;
533
534 se = selector;
535 while (se)
536 {
537 value = getval? getval (cookie, se->name) : NULL;
538 if (!value)
539 value = "";
540
541 if (!*value)
542 {
543 /* Field is empty. */
544 result = 0;
545 }
546 else /* Field has a value. */
547 {
548 valuelen = strlen (value);
549 numvalue = strtol (value, NULL, 0);
550 selen = strlen (se->value);
551
552 switch (se->op)
553 {
554 case SELECT_SAME:
555 if (se->xcase)
556 result = (valuelen==selen && !memcmp (value,se->value,selen));
557 else
558 result = (valuelen==selen && !memicmp (value,se->value,selen));
559 break;
560 case SELECT_SUB:
561 if (se->xcase)
562 result = !!my_memstr (value, valuelen, se->value);
563 else
564 result = !!memistr (value, valuelen, se->value);
565 break;
566 case SELECT_NONEMPTY:
567 result = !!valuelen;
568 break;
569 case SELECT_ISTRUE:
570 result = !!numvalue;
571 break;
572 case SELECT_EQ:
573 result = (numvalue == se->numvalue);
574 break;
575 case SELECT_GT:
576 result = (numvalue > se->numvalue);
577 break;
578 case SELECT_GE:
579 result = (numvalue >= se->numvalue);
580 break;
581 case SELECT_LT:
582 result = (numvalue < se->numvalue);
583 break;
584 case SELECT_LE:
585 result = (numvalue <= se->numvalue);
586 break;
587 case SELECT_STRGT:
588 if (se->xcase)
589 result = strcmp (value, se->value) > 0;
590 else
591 result = strcasecmp (value, se->value) > 0;
592 break;
593 case SELECT_STRGE:
594 if (se->xcase)
595 result = strcmp (value, se->value) >= 0;
596 else
597 result = strcasecmp (value, se->value) >= 0;
598 break;
599 case SELECT_STRLT:
600 if (se->xcase)
601 result = strcmp (value, se->value) < 0;
602 else
603 result = strcasecmp (value, se->value) < 0;
604 break;
605 case SELECT_STRLE:
606 if (se->xcase)
607 result = strcmp (value, se->value) <= 0;
608 else
609 result = strcasecmp (value, se->value) <= 0;
610 break;
611 }
612 }
613
614 if (se->not)
615 result = !result;
616
617 if (result)
618 {
619 /* This expression evaluated to true. See whether there are
620 remaining expressions in this conjunction. */
621 if (!se->next || se->next->disjun)
622 break; /* All expressions are true. Return True. */
623 se = se->next; /* Test the next. */
624 }
625 else
626 {
627 /* This expression evaluated to false and thus the
628 * conjunction evaluates to false. We skip over the
629 * remaining expressions of this conjunction and continue
630 * with the next disjunction if any. */
631 do
632 se = se->next;
633 while (se && !se->disjun);
634 }
635 }
636
637 return result;
638 }
639