1#ifdef HAVE_CONFIG_H
2#include "config.h"
3#endif
4
5#include <stdlib.h>
6#include <string.h>
7#include <stdio.h>
8
9#include "err.h"
10#include "query.h"
11
12static const query_field_t* find_field(const char* name,
13				       const query_field_t* fields);
14static int arith_query(query_node_t* query, void* target);
15static int string_query(query_node_t* query, void* target);
16
17static query_node_t*	match_specifier(const char* query,
18					const char** cursor,
19					const query_field_t* fields);
20static query_node_t*	group_match(const char* query,
21				    const char** cursor,
22				    const query_field_t* fields);
23static query_node_t*	single_match(const char* query,
24				     const char** cursor,
25				     const query_field_t* fields);
26static int		get_field_name(const char** pcursor,
27				       const char* query,
28				       char* name,
29				       int len);
30static int		get_opcode(const char** pcursor,
31				   const char* query,
32				   char* name,
33				   int len);
34static query_node_t*	match_number(const query_field_t* field,
35				     char not, char opcode,
36				     const char** pcursor,
37				     const char* query);
38static query_node_t*	match_string(const query_field_t* field,
39				     char not, char opcode,
40				     const char** pcursor,
41				     const char* query);
42char*			query_unescape(const char* query);
43
44query_node_t* query_build(const char* query, const query_field_t* fields)
45{
46    query_node_t*	left = 0;
47    char*		raw = query_unescape(query);
48    const char*		cursor = raw;
49    query_node_t*	right = 0;
50    query_type_t	join;
51
52    if(0 == (left = match_specifier(query, &cursor, fields)))
53	goto error;
54
55    while(*cursor)
56    {
57	query_node_t*	con;
58
59	switch(*cursor)
60	{
61	case '+':
62	case ' ':	join = qot_and;		break;
63	case ',':	join = qot_or;		break;
64	default:
65	    DPRINTF(E_LOG,L_QRY, "Illegal character '%c' (0%o) at index %d: %s\n",
66		    *cursor, *cursor, cursor - raw, raw);
67	    goto error;
68	}
69
70	cursor++;
71
72	if(0 == (right = match_specifier(raw, &cursor, fields)))
73	    goto error;
74
75	con = (query_node_t*) calloc(1, sizeof(*con));
76	con->type = join;
77	con->left.node = left;
78	con->right.node = right;
79
80	left = con;
81    }
82
83    if(query != raw)
84	free(raw);
85
86    return left;
87
88 error:
89    if(left != 0)
90	query_free(left);
91    if(raw != query)
92	free(raw);
93
94    return NULL;
95}
96
97static query_node_t*	match_specifier(const char* query,
98					const char** cursor,
99					const query_field_t* fields)
100{
101    switch(**cursor)
102    {
103    case '\'':		return single_match(query, cursor, fields);
104    case '(':		return group_match(query, cursor, fields);
105    }
106
107    DPRINTF(E_LOG,L_QRY,"Illegal character '%c' (0%o) at index %d: %s\n",
108	    **cursor, **cursor, *cursor - query, query);
109    return NULL;
110}
111
112static query_node_t*	group_match(const char* query,
113				    const char** pcursor,
114				    const query_field_t* fields)
115{
116    query_node_t*	left = 0;
117    query_node_t*	right = 0;
118    query_node_t*	join = 0;
119    query_type_t	opcode;
120    const char*		cursor = *pcursor;
121
122    /* skip the opening ')' */
123    ++cursor;
124
125    if(0 == (left = single_match(query, &cursor, fields)))
126	return NULL;
127
128    switch(*cursor)
129    {
130    case '+':
131    case ' ':
132	opcode = qot_and;
133	break;
134
135    case ',':
136	opcode = qot_or;
137	break;
138
139    default:
140	DPRINTF(E_LOG,L_QRY,"Illegal character '%c' (0%o) at index %d: %s\n",
141		*cursor, *cursor, cursor - query, query);
142	goto error;
143    }
144
145    if(0 == (right = single_match(query, &cursor, fields)))
146	goto error;
147
148    if(*cursor != ')')
149    {
150	DPRINTF(E_LOG,L_QRY,"Illegal character '%c' (0%o) at index %d: %s\n",
151		*cursor, *cursor, cursor - query, query);
152	goto error;
153    }
154
155    *pcursor = cursor + 1;
156
157    join = (query_node_t*) calloc(1, sizeof(*join));
158    join->type = opcode;
159    join->left.node = left;
160    join->right.node = right;
161
162    return join;
163
164 error:
165    if(0 != left)
166	query_free(left);
167    if(0 != right)
168	query_free(right);
169
170    return 0;
171}
172
173static query_node_t*	single_match(const char* query,
174				     const char** pcursor,
175				     const query_field_t* fields)
176{
177    char			fname[64];
178    const query_field_t*	field;
179    char			not = 0;
180    char			op = 0;
181    query_node_t*		node = 0;
182
183    /* skip opening ' */
184    (*pcursor)++;
185
186    /* collect the field name */
187    if(!get_field_name(pcursor, query, fname, sizeof(fname)))
188	return NULL;
189
190    if(**pcursor == '!')
191    {
192	not = '!';
193	++(*pcursor);
194    }
195
196    if(strchr(":+-", **pcursor))
197    {
198	op = **pcursor;
199	++(*pcursor);
200    }
201    else
202    {
203	DPRINTF(E_LOG,L_QRY,"Illegal Operator: %c (0%o) at index %d: %s\n",
204		**pcursor, **pcursor, *pcursor - query, query);
205	return NULL;
206    }
207
208    if(0 == (field = find_field(fname, fields)))
209    {
210	DPRINTF(E_LOG,L_QRY,"Unknown field: %s\n", fname);
211	return NULL;
212    }
213
214    switch(field->type)
215    {
216    case qft_i32:
217    case qft_i64:
218	node = match_number(field, not, op, pcursor, query);
219	break;
220
221    case qft_string:
222	node = match_string(field, not, op, pcursor, query);
223	break;
224
225    default:
226	DPRINTF(E_LOG,L_QRY,"Invalid field type: %d\n", field->type);
227	break;
228    }
229
230    if(**pcursor != '\'')
231    {
232	DPRINTF(E_LOG,L_QRY,"Illegal Character: %c (0%o) index %d: %s\n",
233		**pcursor, **pcursor, *pcursor - query, query);
234	query_free(node);
235	node = 0;
236    }
237    else
238	++(*pcursor);
239
240    return node;
241}
242
243static int		get_field_name(const char** pcursor,
244				       const char* query,
245				       char* name,
246				       int len)
247{
248    const char*	cursor = *pcursor;
249
250    if(!isalpha(*cursor))
251	return 0;
252
253    while(isalpha(*cursor) || *cursor == '.')
254    {
255	if(--len <= 0)
256	{
257	    DPRINTF(E_LOG,L_QRY,"token length exceeded at offset %d: %s\n",
258		    cursor - query, query);
259	    return 0;
260	}
261
262	*name++ = *cursor++;
263    }
264
265    *pcursor = cursor;
266
267    *name = 0;
268
269    return 1;
270}
271
272static query_node_t*	match_number(const query_field_t* field,
273				     char not, char opcode,
274				     const char** pcursor,
275				     const char* query)
276{
277    query_node_t*	node = (query_node_t*) calloc(1, sizeof(*node));
278
279    switch(opcode)
280    {
281    case ':':
282	node->type = not ? qot_ne : qot_eq;
283	break;
284    case '+':
285    case ' ':
286	node->type = not ? qot_le : qot_gt;
287	break;
288    case '-':
289	node->type = not ? qot_ge : qot_lt;
290	break;
291    }
292
293    node->left.field = field;
294
295    switch(field->type)
296    {
297    case qft_i32:
298	node->right.i32 = strtol(*pcursor, (char**) pcursor, 10);
299	break;
300    case qft_i64:
301	node->right.i64 = strtoll(*pcursor, (char**) pcursor, 10);
302	break;
303    }
304
305    if(**pcursor != '\'')
306    {
307	DPRINTF(E_LOG,L_QRY,"Illegal char in number '%c' (0%o) at index %d: %s\n",
308		**pcursor, **pcursor, *pcursor - query, query);
309	free(node);
310	return 0;
311    }
312
313    return node;
314}
315
316static query_node_t*	match_string(const query_field_t* field,
317				     char not, char opcode,
318				     const char** pcursor,
319				     const char* query)
320{
321    char		match[64];
322    char*		dst = match;
323    int			left = sizeof(match);
324    const char*		cursor = *pcursor;
325    query_type_t	op = qot_is;
326    query_node_t*	node;
327
328    if(opcode != ':')
329    {
330	DPRINTF(E_LOG,L_QRY,"Illegal operation on string: %c at index %d: %s\n",
331		opcode, cursor - query - 1);
332	return NULL;
333    }
334
335    if(*cursor == '*')
336    {
337	op = qot_ends;
338	cursor++;
339    }
340
341    while(*cursor && *cursor != '\'')
342    {
343	if(--left == 0)
344	{
345	    DPRINTF(E_LOG,L_QRY,"string too long at index %d: %s\n",
346		    cursor - query, query);
347	    return NULL;
348	}
349
350	if(*cursor == '\\')
351	{
352	    switch(*++cursor)
353	    {
354	    case '*':
355	    case '\'':
356	    case '\\':
357		*dst++ = *cursor++;
358		break;
359	    default:
360		DPRINTF(E_LOG,L_QRY,"Illegal escape: %c (0%o) at index %d: %s\n",
361			*cursor, *cursor, cursor - query, query);
362		return NULL;
363	    }
364	}
365	else
366	    *dst++ = *cursor++;
367    }
368
369    if(dst[-1] == '*')
370    {
371	op = (op == qot_is) ? qot_begins : qot_contains;
372	dst--;
373    }
374
375    *dst = 0;
376
377    node = (query_node_t*) calloc(1, sizeof(*node));
378    node->type = op;
379    node->left.field = field;
380    node->right.str = strdup(match);
381
382    *pcursor = cursor;
383
384    return node;
385}
386
387int query_test(query_node_t* query, void* target)
388{
389    switch(query->type)
390    {
391	/* conjunction */
392    case qot_and:
393	return (query_test(query->left.node, target) &&
394		query_test(query->right.node, target));
395
396    case qot_or:
397	return (query_test(query->left.node, target) ||
398		query_test(query->right.node, target));
399
400	/* negation */
401    case qot_not:
402	return !query_test(query->left.node, target);
403
404	/* arithmetic */
405    case qot_eq:
406    case qot_ne:
407    case qot_le:
408    case qot_lt:
409    case qot_ge:
410    case qot_gt:
411	return arith_query(query, target);
412
413	/* string */
414    case qot_is:
415    case qot_begins:
416    case qot_ends:
417    case qot_contains:
418	return string_query(query, target);
419	break;
420
421	/* constants */
422    case qot_const:
423	return query->left.constant;
424    }
425}
426
427void query_free(query_node_t* query)
428{
429    if(0 != query)
430    {
431	switch(query->type)
432	{
433	    /* conjunction */
434	case qot_and:
435	case qot_or:
436	    query_free(query->left.node);
437	    query_free(query->right.node);
438	    break;
439
440	    /* negation */
441	case qot_not:
442	    query_free(query->left.node);
443	    break;
444
445	    /* arithmetic */
446	case qot_eq:
447	case qot_ne:
448	case qot_le:
449	case qot_lt:
450	case qot_ge:
451	case qot_gt:
452	    break;
453
454	    /* string */
455	case qot_is:
456	case qot_begins:
457	case qot_ends:
458	case qot_contains:
459	    free(query->right.str);
460	    break;
461
462	    /* constants */
463	case qot_const:
464	    break;
465
466	default:
467	    DPRINTF(E_LOG,L_QRY,"Illegal query type: %d\n", query->type);
468	    break;
469	}
470
471	free(query);
472    }
473}
474
475static const query_field_t* find_field(const char* name, const query_field_t* fields)
476{
477    while(fields->name && strcasecmp(fields->name, name))
478	fields++;
479
480    if(fields->name == 0)
481    {
482	DPRINTF(E_LOG,L_QRY,"Illegal query field: %s\n", name);
483	return NULL;
484    }
485
486    return fields;
487}
488
489static int arith_query(query_node_t* query, void* target)
490{
491    const query_field_t*	field = query->left.field;
492
493    switch(field->type)
494    {
495    case qft_i32:
496	{
497	    int		tv = * (int*) ((size_t) target + field->offset);
498
499	    tv -= query->right.i32;
500
501	    switch(query->type)
502	    {
503	    case qot_eq:	return tv == 0;
504	    case qot_ne:	return tv != 0;
505	    case qot_le:	return tv <= 0;
506	    case qot_lt:	return tv < 0;
507	    case qot_ge:	return tv >= 0;
508	    case qot_gt:	return tv > 0;
509	    default:
510		DPRINTF(E_LOG,L_QRY,"illegal query type: %d\n", query->type);
511		break;
512	    }
513	}
514	break;
515
516    case qft_i64:
517	{
518	    long long tv = * (long long*) ((size_t) target + field->offset);
519
520	    tv -= query->right.i32;
521
522	    switch(query->type)
523	    {
524	    case qot_eq:	return tv == 0;
525	    case qot_ne:	return tv != 0;
526	    case qot_le:	return tv <= 0;
527	    case qot_lt:	return tv < 0;
528	    case qot_ge:	return tv >= 0;
529	    case qot_gt:	return tv > 0;
530	    default:
531		DPRINTF(E_LOG,L_QRY,"illegal query type: %d\n", query->type);
532		break;
533	    }
534	}
535	break;
536
537    default:
538	DPRINTF(E_LOG,L_QRY,"illegal field type: %d\n", field->type);
539	break;
540    }
541
542    return 0;
543}
544
545static int string_query(query_node_t* query, void* target)
546{
547    const query_field_t*	field = query->left.field;
548    const char*		ts;
549
550    if(field->type != qft_string)
551    {
552	DPRINTF(E_LOG,L_QRY,"illegal field type: %d\n", field->type);
553	return 0;
554    }
555
556    ts = * (const char**) ((size_t) target + field->offset);
557
558    if(0 == ts)
559	return strlen(query->right.str) == 0;
560
561    switch(query->type)
562    {
563    case qot_is:
564	return !strcasecmp(query->right.str, ts);
565
566    case qot_begins:
567	return !strncasecmp(query->right.str, ts, strlen(query->right.str));
568
569    case qot_ends:
570	{
571	    int start = strlen(ts) - strlen(query->right.str);
572
573	    if(start < 0)
574		return 0;
575
576	    return !strcasecmp(query->right.str, ts + start);
577	}
578
579    case qot_contains:
580	return (int) strcasestr(ts, query->right.str); /* returns null if not found */
581
582    default:
583	DPRINTF(E_LOG,L_QRY,"Illegal query type: %d\n", query->type);
584	break;
585    }
586
587    return 0;
588}
589
590void query_dump(FILE* fp, query_node_t* query, int depth)
591{
592    static const char* labels[] = {
593	"NOP",
594	"and",
595	"or",
596	"not",
597	"==",
598	"!=",
599	"<=",
600	"<",
601	">=",
602	">",
603	"eq",
604	"beginswith",
605	"endwith",
606	"contains",
607	"constant"
608    };
609
610#ifndef DEBUG
611    return;
612#endif
613
614    switch(query->type)
615    {
616    case qot_and:
617    case qot_or:
618	fprintf(fp, "%*s(%s\n", depth, "", labels[query->type]);
619	query_dump(fp, query->left.node, depth + 4);
620	query_dump(fp, query->right.node, depth + 4);
621	fprintf(fp, "%*s)\n", depth, "");
622	break;
623
624    case qot_not:
625	fprintf(fp, "%*s(not\n", depth, "");
626	query_dump(fp, query->left.node, depth + 4);
627	fprintf(fp, "%*s)\n", depth, "");
628	break;
629
630	/* arithmetic */
631    case qot_eq:
632    case qot_ne:
633    case qot_le:
634    case qot_lt:
635    case qot_ge:
636    case qot_gt:
637	if(query->left.field->type == qft_i32)
638	    fprintf(fp, "%*s(%s %s %d)\n",
639		    depth, "", labels[query->type],
640		    query->left.field->name, query->right.i32);
641	else
642	    fprintf(fp, "%*s(%s %s %q)\n",
643		    depth, "", labels[query->type],
644		    query->left.field->name, query->right.i64);
645	break;
646
647	/* string */
648    case qot_is:
649    case qot_begins:
650    case qot_ends:
651    case qot_contains:
652	fprintf(fp, "%*s(%s %s \"%s\")\n",
653		depth, "", labels[query->type],
654		query->left.field->name, query->right.str);
655	break;
656
657	/* constants */
658    case qot_const:
659	fprintf(fp, "%*s(%s)\n", depth, "", query->left.constant ? "true" : "false");
660	break;
661    }
662
663}
664
665char* query_unescape(const char* src)
666{
667    char*	copy = malloc(strlen(src) + 1);
668    char*	dst = copy;
669
670    while(*src)
671    {
672	if(*src == '%')
673	{
674	    int		val = 0;
675
676	    if(*++src)
677	    {
678		if(isdigit(*src))
679		    val = val * 16 + *src - '0';
680		else
681		    val = val * 16 + tolower(*src) - 'a' + 10;
682	    }
683
684	    if(*++src)
685	    {
686		if(isdigit(*src))
687		    val = val * 16 + *src - '0';
688		else
689		    val = val * 16 + tolower(*src) - 'a' + 10;
690	    }
691
692	    src++;
693	    *dst++ = val;
694	}
695	else
696	    *dst++ = *src++;
697    }
698
699    *dst++ = 0;
700
701    return copy;
702}
703