Contiki-NG
Loading...
Searching...
No Matches
aql-parser.c
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010, Swedish Institute of Computer Science
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the Institute nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30/**
31 * \file
32 * A recursive parser for AQL, the Antelope Query Language.
33 * \author
34 * Nicolas Tsiftes <nvt@sics.se>
35 */
36
37#include "attribute.h"
38#include "db-options.h"
39#include "index.h"
40#include "aql.h"
41#include "lvm.h"
42
43#include <limits.h>
44#include <stdlib.h>
45#include <stdint.h>
46#include <stdio.h>
47#include <string.h>
48
49#define DEBUG DEBUG_NONE
50#include "debug.h"
51
52#if DEBUG
53static char error_message[DB_ERROR_BUF_SIZE];
54static int error_line;
55static const char *error_function;
56#define RETURN(value) \
57 do { \
58 if(error_message[0] == '\0') { \
59 strncpy(error_message, lexer->input, sizeof(error_message) - 1); \
60 error_line = __LINE__; \
61 error_function = __func__; \
62 } \
63 } while(0); \
64 return (value)
65#define RESET_ERROR() \
66 do { \
67 error_message[0] = '\0'; \
68 error_line = 0; \
69 error_function = NULL; \
70 } while(0)
71#else
72#define RETURN(value) return (value)
73#define RESET_ERROR()
74#endif
75#define PARSER(name) \
76 static aql_status_t \
77 parse_##name(lexer_t *lexer)
78#define PARSER_ARG(name, arg) \
79 static aql_status_t \
80 parse_##name(lexer_t *lexer, arg)
81#define PARSER_TOKEN(name) \
82 static token_t \
83 parse_##name(lexer_t *lexer)
84#define PARSE(name) \
85 !AQL_ERROR(parse_##name(lexer))
86#define PARSE_TOKEN(name) \
87 parse_##name(lexer)
88
89#define NEXT lexer_next(lexer)
90#define REWIND lexer_rewind(lexer); RESET_ERROR()
91#define TOKEN *lexer->token
92#define VALUE *lexer->value
93
94#define CONSUME(token) \
95 do { \
96 NEXT; \
97 if(TOKEN != (token)) { \
98 RETURN(SYNTAX_ERROR); \
99 } \
100 } while(0)
101
102/* The parsing of AQL results in this aql_adt_t object. */
103static aql_adt_t *adt;
104
105/* Conditional statements are compiled into VM bytecode, which is stored in
106 an instance of the LogicVM. */
107static lvm_instance_t p;
108static unsigned char vmcode[DB_VM_BYTECODE_SIZE];
109
110/* Parsing functions for AQL. */
111PARSER_TOKEN(cmp)
112{
113 NEXT;
114 switch(TOKEN) {
115 case EQUAL:
116 case NOT_EQUAL:
117 case GT:
118 case LT:
119 case GEQ:
120 case LEQ:
121 return TOKEN;
122 default:
123 return NONE;
124 }
125}
126
127PARSER_TOKEN(op)
128{
129 NEXT;
130 switch(TOKEN) {
131 case ADD:
132 case SUB:
133 case MUL:
134 case DIV:
135 case RIGHT_PAREN:
136 return TOKEN;
137 default:
138 return NONE;
139 }
140}
141
142PARSER_TOKEN(aggregator)
143{
144 NEXT;
145 switch(TOKEN) {
146 case COUNT:
147 case SUM:
148 case MEAN:
149 case MEDIAN:
150 case MAX:
151 case MIN:
152 return TOKEN;
153 default:
154 return NONE;
155 }
156}
157
158PARSER(attributes)
159{
160 token_t token;
161 aql_aggregator_t function;
162
163 token = PARSE_TOKEN(aggregator);
164 if(token != NONE) {
165 switch(TOKEN) {
166 case COUNT:
167 function = AQL_COUNT;
168 break;
169 case SUM:
170 function = AQL_SUM;
171 break;
172 case MEAN:
173 function = AQL_MEAN;
174 break;
175 case MEDIAN:
176 function = AQL_MEDIAN;
177 break;
178 case MAX:
179 function = AQL_MAX;
180 break;
181 case MIN:
182 function = AQL_MIN;
183 break;
184 default:
185 RETURN(SYNTAX_ERROR);
186 }
187
188 AQL_SET_FLAG(adt, AQL_FLAG_AGGREGATE);
189
190 PRINTF("aggregator: %d\n", TOKEN);
191
192 /* Parse the attribute to aggregate. */
193 CONSUME(LEFT_PAREN);
194 CONSUME(IDENTIFIER);
195
196 AQL_ADD_AGGREGATE(adt, function, VALUE);
197 PRINTF("aggregated attribute: %s\n", VALUE);
198
199 CONSUME(RIGHT_PAREN);
200 goto check_more_attributes;
201 } else {
202 REWIND;
203 }
204
205 /* Plain identifier. */
206
207 CONSUME(IDENTIFIER);
208
209 AQL_ADD_ATTRIBUTE(adt, VALUE, DOMAIN_UNSPECIFIED, 0);
210
211check_more_attributes:
212 NEXT;
213 if(TOKEN == COMMA) {
214 if(!PARSE(attributes)) {
215 RETURN(SYNTAX_ERROR);
216 }
217 } else {
218 REWIND;
219 }
220
221 RETURN(OK);
222}
223
224PARSER(relations)
225{
226 /* Parse comma-separated identifiers for relations. */
227 CONSUME(IDENTIFIER);
228
229 AQL_ADD_RELATION(adt, VALUE);
230 NEXT;
231 if(TOKEN == COMMA) {
232 if(!PARSE(relations)) {
233 RETURN(SYNTAX_ERROR);
234 }
235 } else {
236 REWIND;
237 }
238
239 RETURN(OK);
240}
241
242PARSER(values)
243{
244 /* Parse comma-separated attribute values. */
245 NEXT;
246 switch(TOKEN) {
247 case STRING_VALUE:
248 AQL_ADD_VALUE(adt, DOMAIN_STRING, VALUE);
249 break;
250 case INTEGER_VALUE:
251 AQL_ADD_VALUE(adt, DOMAIN_INT, VALUE);
252 break;
253 default:
254 RETURN(SYNTAX_ERROR);
255 }
256
257 NEXT;
258 if(TOKEN == COMMA) {
259 return PARSE(values);
260 } else {
261 REWIND;
262 }
263
264 RETURN(OK);
265}
266
267PARSER(operand)
268{
269 NEXT;
270 switch(TOKEN) {
271 case IDENTIFIER:
272 if(LVM_ERROR(lvm_register_variable(VALUE, LVM_LONG)) ||
273 LVM_ERROR(lvm_set_variable(&p, VALUE))) {
274 RETURN(SYNTAX_ERROR);
275 }
276 AQL_ADD_PROCESSING_ATTRIBUTE(adt, VALUE);
277 break;
278 case STRING_VALUE:
279 break;
280 case FLOAT_VALUE:
281 break;
282 case INTEGER_VALUE:
283 if(LVM_ERROR(lvm_set_long(&p, *(long *)lexer->value))) {
284 RETURN(SYNTAX_ERROR);
285 }
286 break;
287 default:
288 RETURN(SYNTAX_ERROR);
289 }
290
291 RETURN(OK);
292}
293
294PARSER(expr)
295{
296 token_t token;
297 size_t saved_end;
298 operator_t op;
299
300 saved_end = lvm_get_end(&p);
301
302 NEXT;
303 if(TOKEN == LEFT_PAREN) {
304 if(!PARSE(expr)) {
305 RETURN(SYNTAX_ERROR);
306 }
307 CONSUME(RIGHT_PAREN);
308 } else {
309 REWIND;
310 if(!PARSE(operand)) {
311 RETURN(SYNTAX_ERROR);
312 }
313 }
314
315 while(1) {
316 token = PARSE_TOKEN(op);
317 if(token == NONE) {
318 saved_end = lvm_get_end(&p);
319 REWIND;
320 break;
321 } else if (token == RIGHT_PAREN) {
322 break;
323 }
324
325 if(!PARSE(operand) && !PARSE(expr)) {
326 RETURN(SYNTAX_ERROR);
327 }
328
329 saved_end = lvm_shift_for_operator(&p, saved_end);
330
331 switch(token) {
332 case ADD:
333 op = LVM_ADD;
334 break;
335 case SUB:
336 op = LVM_SUB;
337 break;
338 case MUL:
339 op = LVM_MUL;
340 break;
341 case DIV:
342 op = LVM_DIV;
343 break;
344 default:
345 RETURN(SYNTAX_ERROR);
346 }
347 if(LVM_ERROR(lvm_set_op(&p, op))) {
348 RETURN(SYNTAX_ERROR);
349 }
350 lvm_set_end(&p, saved_end);
351 }
352
353 return OK;
354}
355
356PARSER(comparison)
357{
358 token_t token;
359 size_t saved_end;
360 operator_t rel;
361
362 saved_end = lvm_jump_to_operand(&p);
363
364 if(!PARSE(expr)) {
365 RETURN(SYNTAX_ERROR);
366 }
367
368 saved_end = lvm_set_end(&p, saved_end);
369
370 token = PARSE_TOKEN(cmp);
371 if(token == NONE) {
372 RETURN(SYNTAX_ERROR);
373 }
374
375 switch(token) {
376 case GT:
377 rel = LVM_GE;
378 break;
379 case GEQ:
380 rel = LVM_GEQ;
381 break;
382 case LT:
383 rel = LVM_LE;
384 break;
385 case LEQ:
386 rel = LVM_LEQ;
387 break;
388 case EQUAL:
389 rel = LVM_EQ;
390 break;
391 case NOT_EQUAL:
392 rel = LVM_NEQ;
393 break;
394 default:
395 RETURN(SYNTAX_ERROR);
396 }
397
398 if(LVM_ERROR(lvm_set_relation(&p, rel))) {
399 RETURN(SYNTAX_ERROR);
400 }
401 lvm_set_end(&p, saved_end);
402
403 if(!PARSE(expr)) {
404 RETURN(SYNTAX_ERROR);
405 }
406
407 RETURN(OK);
408}
409
410PARSER(where)
411{
412 int r;
413 operator_t connective;
414 size_t saved_end;
415
416 if(!PARSE(comparison)) {
417 RETURN(SYNTAX_ERROR);
418 }
419
420 saved_end = 0;
421
422 /* The WHERE clause can consist of multiple prepositions. */
423 for(;;) {
424 NEXT;
425 if(TOKEN != AND && TOKEN != OR) {
426 REWIND;
427 break;
428 }
429
430 connective = TOKEN == AND ? LVM_AND : LVM_OR;
431
432 saved_end = lvm_shift_for_operator(&p, saved_end);
433 if(LVM_ERROR(lvm_set_relation(&p, connective))) {
434 RETURN(SYNTAX_ERROR);
435 }
436 lvm_set_end(&p, saved_end);
437
438 NEXT;
439 if(TOKEN == LEFT_PAREN) {
440 r = PARSE(where);
441 if(!r) {
442 RETURN(SYNTAX_ERROR);
443 }
444 CONSUME(RIGHT_PAREN);
445 } else {
446 REWIND;
447 r = PARSE(comparison);
448 if(!r) {
449 RETURN(r);
450 }
451 }
452 }
453
454 lvm_print_code(&p);
455
456 return OK;
457}
458
459PARSER(join)
460{
461 AQL_SET_TYPE(adt, AQL_TYPE_JOIN);
462
463 CONSUME(IDENTIFIER);
464
465 PRINTF("Left relation: %s\n", VALUE);
466 AQL_ADD_RELATION(adt, VALUE);
467
468 CONSUME(COMMA);
469 CONSUME(IDENTIFIER);
470
471 PRINTF("Right relation: %s\n", VALUE);
472 AQL_ADD_RELATION(adt, VALUE);
473
474 CONSUME(ON);
475 CONSUME(IDENTIFIER);
476
477 PRINTF("Join on attribute %s\n", VALUE);
478 AQL_ADD_ATTRIBUTE(adt, VALUE, DOMAIN_UNSPECIFIED, 0);
479
480 CONSUME(PROJECT);
481
482 /* projection attributes... */
483 if(!PARSE(attributes)) {
484 RETURN(SYNTAX_ERROR);
485 }
486
487 CONSUME(END);
488
489 RETURN(OK);
490}
491
492PARSER(select)
493{
494 AQL_SET_TYPE(adt, AQL_TYPE_SELECT);
495
496 /* projection attributes... */
497 if(!PARSE(attributes)) {
498 RETURN(SYNTAX_ERROR);
499 }
500
501 CONSUME(FROM);
502 if(!PARSE(relations)) {
503 RETURN(SYNTAX_ERROR);
504 }
505
506 NEXT;
507 if(TOKEN == WHERE) {
508 lvm_reset(&p, vmcode, sizeof(vmcode));
509
510 if(!PARSE(where)) {
511 RETURN(SYNTAX_ERROR);
512 }
513
514 AQL_SET_CONDITION(adt, &p);
515 } else {
516 REWIND;
517 RETURN(OK);
518 }
519
520 CONSUME(END);
521
522 return OK;
523}
524
525PARSER(insert)
526{
527 AQL_SET_TYPE(adt, AQL_TYPE_INSERT);
528
529 CONSUME(LEFT_PAREN);
530
531 if(!PARSE(values)) {
532 RETURN(SYNTAX_ERROR);
533 }
534
535 CONSUME(RIGHT_PAREN);
536 CONSUME(INTO);
537
538 if(!PARSE(relations)) {
539 RETURN(SYNTAX_ERROR);
540 }
541
542 RETURN(OK);
543}
544
545PARSER(remove_attribute)
546{
547 AQL_SET_TYPE(adt, AQL_TYPE_REMOVE_ATTRIBUTE);
548
549 CONSUME(IDENTIFIER);
550 AQL_ADD_RELATION(adt, VALUE);
551
552 CONSUME(DOT);
553 CONSUME(IDENTIFIER);
554
555 PRINTF("Removing the index for the attribute %s\n", VALUE);
556 AQL_ADD_ATTRIBUTE(adt, VALUE, DOMAIN_UNSPECIFIED, 0);
557
558 RETURN(OK);
559}
560
561#if DB_FEATURE_REMOVE
562PARSER(remove_from)
563{
564 AQL_SET_TYPE(adt, AQL_TYPE_REMOVE_TUPLES);
565
566 /* Use a temporary persistent relation to assign the query result to. */
567 AQL_SET_FLAG(adt, AQL_FLAG_ASSIGN);
568 AQL_ADD_RELATION(adt, REMOVE_RELATION);
569
570 CONSUME(IDENTIFIER);
571 AQL_ADD_RELATION(adt, VALUE);
572
573 CONSUME(WHERE);
574
575 lvm_reset(&p, vmcode, sizeof(vmcode));
576 AQL_SET_CONDITION(adt, &p);
577
578 return PARSE(where);
579
580}
581#endif /* DB_FEATURE_REMOVE */
582
583PARSER(remove_index)
584{
585 AQL_SET_TYPE(adt, AQL_TYPE_REMOVE_INDEX);
586
587 CONSUME(IDENTIFIER);
588 AQL_ADD_RELATION(adt, VALUE);
589
590 CONSUME(DOT);
591 CONSUME(IDENTIFIER);
592
593 PRINTF("remove index: %s\n", VALUE);
594 AQL_ADD_ATTRIBUTE(adt, VALUE, DOMAIN_UNSPECIFIED, 0);
595
596 RETURN(OK);
597}
598
599PARSER(remove_relation)
600{
601 AQL_SET_TYPE(adt, AQL_TYPE_REMOVE_RELATION);
602
603 CONSUME(IDENTIFIER);
604 PRINTF("remove relation: %s\n", VALUE);
605 AQL_ADD_RELATION(adt, VALUE);
606
607 RETURN(OK);
608}
609
610PARSER(remove)
611{
612 aql_status_t r;
613
614 NEXT;
615 switch(TOKEN) {
616 case ATTRIBUTE:
617 r = PARSE(remove_attribute);
618 break;
619#if DB_FEATURE_REMOVE
620 case FROM:
621 r = PARSE(remove_from);
622 break;
623#endif
624 case INDEX:
625 r = PARSE(remove_index);
626 break;
627 case RELATION:
628 r = PARSE(remove_relation);
629 break;
630 default:
631 RETURN(SYNTAX_ERROR);
632 }
633
634 if(!r) {
635 RETURN(SYNTAX_ERROR);
636 }
637
638 CONSUME(END);
639
640 RETURN(OK);
641}
642
643PARSER_TOKEN(index_type)
644{
645 index_type_t type;
646
647 NEXT;
648 switch(TOKEN) {
649 case INLINE:
650 type = INDEX_INLINE;
651 break;
652 case MAXHEAP:
653 type = INDEX_MAXHEAP;
654 break;
655 case MEMHASH:
656 type = INDEX_MEMHASH;
657 break;
658 default:
659 return NONE;
660 };
661
662 AQL_SET_INDEX_TYPE(adt, type);
663 return TOKEN;
664}
665
666PARSER(create_index)
667{
668 AQL_SET_TYPE(adt, AQL_TYPE_CREATE_INDEX);
669
670 CONSUME(IDENTIFIER);
671 AQL_ADD_RELATION(adt, VALUE);
672
673 CONSUME(DOT);
674 CONSUME(IDENTIFIER);
675
676 PRINTF("Creating an index for the attribute %s\n", VALUE);
677 AQL_ADD_ATTRIBUTE(adt, VALUE, DOMAIN_UNSPECIFIED, 0);
678
679 CONSUME(TYPE);
680
681 if(PARSE_TOKEN(index_type) == NONE) {
682 RETURN(SYNTAX_ERROR);
683 }
684
685 RETURN(OK);
686}
687
688PARSER(create_relation)
689{
690 CONSUME(IDENTIFIER);
691
692 AQL_SET_TYPE(adt, AQL_TYPE_CREATE_RELATION);
693 AQL_ADD_RELATION(adt, VALUE);
694
695 RETURN(OK);
696}
697
698PARSER_ARG(domain, char *name)
699{
700 domain_t domain;
701 unsigned element_size;
702
703 NEXT;
704 switch(TOKEN) {
705 case STRING:
706 domain = DOMAIN_STRING;
707
708 /* Parse the amount of characters for this domain. */
709 CONSUME(LEFT_PAREN);
710 CONSUME(INTEGER_VALUE);
711 element_size = *(long *)lexer->value;
712 CONSUME(RIGHT_PAREN);
713
714 break;
715 case LONG:
716 domain = DOMAIN_LONG;
717 element_size = 4;
718 break;
719 case INT:
720 domain = DOMAIN_INT;
721 element_size = 2;
722 break;
723 default:
724 return PLE_ERROR;
725 }
726
727 AQL_ADD_ATTRIBUTE(adt, name, domain, element_size);
728
729 return OK;
730}
731
732PARSER(create_attributes)
733{
734 aql_status_t r;
735 char name[ATTRIBUTE_NAME_LENGTH];
736
737 AQL_SET_TYPE(adt, AQL_TYPE_CREATE_ATTRIBUTE);
738
739 CONSUME(IDENTIFIER);
740
741 strncpy(name, VALUE, sizeof(name) - 1);
742 name[sizeof(name) - 1] = '\0';
743
744 CONSUME(DOMAIN);
745
746 r = parse_domain(lexer, name);
747 if(AQL_ERROR(r)) {
748 RETURN(r);
749 }
750
751 CONSUME(IN);
752 CONSUME(IDENTIFIER);
753
754 AQL_ADD_RELATION(adt, VALUE);
755
756 RETURN(OK);
757}
758
759PARSER(create)
760{
761 aql_status_t r;
762
763 NEXT;
764 switch(TOKEN) {
765 case ATTRIBUTE:
766 r = PARSE(create_attributes);
767 break;
768 case INDEX:
769 r = PARSE(create_index);
770 break;
771 case RELATION:
772 r = PARSE(create_relation);
773 break;
774 default:
775 RETURN(SYNTAX_ERROR);
776 }
777
778 if(!r) {
779 RETURN(SYNTAX_ERROR);
780 }
781
782 CONSUME(END);
783
784 RETURN(OK);
785}
786
787aql_status_t
788aql_parse(aql_adt_t *external_adt, char *input_string)
789{
790 lexer_t lex;
791 token_t token = NONE;
792 value_t value;
793 aql_status_t result;
794
795 RESET_ERROR();
796
797 PRINTF("Parsing \"%s\"\n", input_string);
798
799 adt = external_adt;
800 AQL_CLEAR(adt);
801 AQL_SET_CONDITION(adt, NULL);
802
803 lexer_start(&lex, input_string, &token, &value);
804
805 result = lexer_next(&lex);
806 if(!AQL_ERROR(result)) {
807 switch(token) {
808 case IDENTIFIER:
809 PRINTF("Assign the result to relation %s\n", *lex.value);
810 AQL_ADD_RELATION(adt, *lex.value);
811 AQL_SET_FLAG(adt, AQL_FLAG_ASSIGN);
812 if(AQL_ERROR(lexer_next(&lex))) {
813 result = SYNTAX_ERROR;
814 break;
815 }
816 if(*lex.token != ASSIGN) {
817 result = SYNTAX_ERROR;
818 break;
819 }
820 if(AQL_ERROR(lexer_next(&lex))) {
821 result = SYNTAX_ERROR;
822 break;
823 }
824 switch(*lex.token) {
825 case SELECT:
826 result = parse_select(&lex);
827 break;
828 case JOIN:
829 result = parse_join(&lex);
830 break;
831 default:
832 result = SYNTAX_ERROR;
833 }
834 break;
835 case JOIN:
836 result = parse_join(&lex);
837 break;
838 case CREATE:
839 result = parse_create(&lex);
840 break;
841 case REMOVE:
842 result = parse_remove(&lex);
843 break;
844 case INSERT:
845 result = parse_insert(&lex);
846 break;
847 case SELECT:
848 result = parse_select(&lex);
849 break;
850 case NONE:
851 case COMMENT:
852 result = OK;
853 case END:
854 break;
855 default:
856 result = SYNTAX_ERROR;
857 }
858 }
859
860 if(AQL_ERROR(result)) {
861 PRINTF("Error in function %s, line %d: input \"%s\"\n",
862 error_function, error_line, error_message);
863 }
864
865 return result;
866}
Definitions and declarations for AQL, the Antelope Query Language.
Definitions for attributes.
Database configuration options.
A set of debugging macros.
Definitions and declarations for the Propositional Logic Engine.