Contiki-NG
lvm.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 * Logic engine used for quickly evaluating data constraints in relations.
33 * \author
34 * Nicolas Tsiftes <nvt@sics.se>
35 */
36
37#include <limits.h>
38#include <stdio.h>
39#include <stdlib.h>
40#include <string.h>
41
42#include "aql.h"
43#include "lvm.h"
44
45#define DEBUG DEBUG_NONE
46#include "debug.h"
47
48/*
49 * The logic engine determines whether a logical predicate is true for
50 * each tuple in a relation. It uses a stack-based execution model of
51 * operations that are arranged in prefix (Polish) notation.
52 */
53
54/* Default option values. */
55#ifndef LVM_MAX_NAME_LENGTH
56#define LVM_MAX_NAME_LENGTH 16
57#endif
58
59#ifndef LVM_MAX_VARIABLE_ID
60#define LVM_MAX_VARIABLE_ID 8
61#endif
62
63#ifndef LVM_USE_FLOATS
64#define LVM_USE_FLOATS 0
65#endif
66
67#define IS_CONNECTIVE(op) ((op) & LVM_CONNECTIVE)
68
69struct variable {
70 operand_type_t type;
71 operand_value_t value;
72 char name[LVM_MAX_NAME_LENGTH + 1];
73};
74typedef struct variable variable_t;
75
76struct derivation {
77 operand_value_t max;
78 operand_value_t min;
79 uint8_t derived;
80};
81typedef struct derivation derivation_t;
82
83/* Registered variables for a LVM expression. Their values may be
84 changed between executions of the expression. */
85static variable_t variables[LVM_MAX_VARIABLE_ID];
86
87/* Range derivations of variables that are used for index searches. */
88static derivation_t derivations[LVM_MAX_VARIABLE_ID];
89
90#if DEBUG
91static void
92print_derivations(derivation_t *d)
93{
94 int i;
95
96 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
97 if(d[i].derived) {
98 printf("%s is constrained to (%ld,%ld)\n", variables[i].name,
99 d[i].min.l, d[i].max.l);
100 }
101 }
102}
103#endif /* DEBUG */
104
105static variable_id_t
106lookup(char *name)
107{
108 variable_t *var;
109
110 for(var = variables; var <= &variables[LVM_MAX_VARIABLE_ID - 1] && var->name[0] != '\0'; var++) {
111 if(strcmp(var->name, name) == 0) {
112 break;
113 }
114 }
115
116 return (variable_id_t)(var - &variables[0]);
117}
118
119static operator_t *
120get_operator(lvm_instance_t *p)
121{
122 operator_t *operator;
123
124 operator = (operator_t *)&p->code[p->ip];
125 p->ip += sizeof(operator_t);
126 return operator;
127}
128
129static void
130get_operand(lvm_instance_t *p, operand_t *operand)
131{
132 memcpy(operand, &p->code[p->ip], sizeof(*operand));
133 p->ip += sizeof(*operand);
134}
135
136static node_type_t
137get_type(lvm_instance_t *p)
138{
139 node_type_t node_type;
140
141 node_type = *(node_type_t *)(p->code + p->ip);
142 p->ip += sizeof(node_type);
143
144 return node_type;
145}
146
147static long
148operand_to_long(operand_t *operand)
149{
150 switch(operand->type) {
151 case LVM_LONG:
152 return operand->value.l;
153#if LVM_USE_FLOATS
154 case LVM_FLOAT:
155 return (long)operand->value.f;
156 break;
157#endif /* LVM_USE_FLOATS */
158 case LVM_VARIABLE:
159 return variables[operand->value.id].value.l;
160 default:
161 return 0;
162 }
163}
164
165static lvm_status_t
166eval_expr(lvm_instance_t *p, operator_t op, operand_t *result)
167{
168 int i;
169 node_type_t type;
170 operator_t *operator;
171 operand_t operand[2];
172 long value[2];
173 long result_value;
174 lvm_status_t r;
175
176 for(i = 0; i < 2; i++) {
177 type = get_type(p);
178 switch(type) {
179 case LVM_ARITH_OP:
180 operator = get_operator(p);
181 r = eval_expr(p, *operator, &operand[i]);
182 if(LVM_ERROR(r)) {
183 return r;
184 }
185 break;
186 case LVM_OPERAND:
187 get_operand(p, &operand[i]);
188 break;
189 default:
190 return LVM_SEMANTIC_ERROR;
191 }
192 value[i] = operand_to_long(&operand[i]);
193 }
194
195 switch(op) {
196 case LVM_ADD:
197 result_value = value[0] + value[1];
198 break;
199 case LVM_SUB:
200 result_value = value[0] - value[1];
201 break;
202 case LVM_MUL:
203 result_value = value[0] * value[1];
204 break;
205 case LVM_DIV:
206 if(value[1] == 0) {
207 return LVM_MATH_ERROR;
208 }
209 result_value = value[0] / value[1];
210 break;
211 default:
212 return LVM_EXECUTION_ERROR;
213 }
214
215 result->type = LVM_LONG;
216 result->value.l = result_value;
217
218 return LVM_TRUE;
219}
220
221static int
222eval_logic(lvm_instance_t *p, operator_t *op)
223{
224 int i;
225 int r;
226 operand_t operand;
227 long result[2];
228 node_type_t type;
229 operator_t *operator;
230 long l1, l2;
231 int logic_result[2];
232 unsigned arguments;
233
234 if(IS_CONNECTIVE(*op)) {
235 arguments = *op == LVM_NOT ? 1 : 2;
236 for(i = 0; i < arguments; i++) {
237 type = get_type(p);
238 if(type != LVM_CMP_OP) {
239 return LVM_SEMANTIC_ERROR;
240 }
241 operator = get_operator(p);
242 logic_result[i] = eval_logic(p, operator);
243 if(LVM_ERROR(logic_result[i])) {
244 return logic_result[i];
245 }
246 }
247
248 if(*op == LVM_NOT) {
249 return !logic_result[0];
250 } else if(*op == LVM_AND) {
251 return logic_result[0] == LVM_TRUE && logic_result[1] == LVM_TRUE;
252 } else {
253 return logic_result[0] == LVM_TRUE || logic_result[1] == LVM_TRUE;
254 }
255 }
256
257 for(i = 0; i < 2; i++) {
258 type = get_type(p);
259 switch(type) {
260 case LVM_ARITH_OP:
261 operator = get_operator(p);
262 r = eval_expr(p, *operator, &operand);
263 if(LVM_ERROR(r)) {
264 return r;
265 }
266 break;
267 case LVM_OPERAND:
268 get_operand(p, &operand);
269 break;
270 default:
271 return LVM_SEMANTIC_ERROR;
272 }
273 result[i] = operand_to_long(&operand);
274 }
275
276 l1 = result[0];
277 l2 = result[1];
278 PRINTF("Result1: %ld\nResult2: %ld\n", l1, l2);
279
280 switch(*op) {
281 case LVM_EQ:
282 return l1 == l2;
283 case LVM_NEQ:
284 return l1 != l2;
285 case LVM_GE:
286 return l1 > l2;
287 case LVM_GEQ:
288 return l1 >= l2;
289 case LVM_LE:
290 return l1 < l2;
291 case LVM_LEQ:
292 return l1 <= l2;
293 default:
294 break;
295 }
296
297 return LVM_EXECUTION_ERROR;
298}
299
300void
301lvm_reset(lvm_instance_t *p, unsigned char *code, lvm_ip_t size)
302{
303 memset(code, 0, size);
304 p->code = code;
305 p->size = size;
306 p->end = 0;
307 p->ip = 0;
308 p->error = 0;
309
310 memset(variables, 0, sizeof(variables));
311 memset(derivations, 0, sizeof(derivations));
312}
313
314lvm_ip_t
315lvm_jump_to_operand(lvm_instance_t *p)
316{
317 lvm_ip_t old_end;
318
319 old_end = p->end;
320 p->end += sizeof(operator_t) + sizeof(node_type_t);
321 if(p->end >= p->size) {
322 p->error = __LINE__;
323 p->end = old_end;
324 }
325
326 return old_end;
327}
328
329lvm_ip_t
330lvm_shift_for_operator(lvm_instance_t *p, lvm_ip_t end)
331{
332 unsigned char *ptr;
333 lvm_ip_t old_end;
334
335 old_end = p->end;
336
337 if(p->end + sizeof(operator_t) + sizeof(node_type_t) > p->size ||
338 end >= old_end) {
339 p->error = __LINE__;
340 return 0;
341 }
342
343 ptr = p->code + end;
344
345 memmove(ptr + sizeof(operator_t) + sizeof(node_type_t), ptr, old_end - end);
346 p->end = end;
347
348 return old_end + sizeof(operator_t) + sizeof(node_type_t);
349}
350
351lvm_ip_t
352lvm_get_end(lvm_instance_t *p)
353{
354 return p->end;
355}
356
357lvm_ip_t
358lvm_set_end(lvm_instance_t *p, lvm_ip_t end)
359{
360 lvm_ip_t old_end;
361
362 if(end >= p->size) {
363 p->error = __LINE__;
364 return p->end;
365 }
366
367 old_end = p->end;
368 p->end = end;
369
370 return old_end;
371}
372
373lvm_status_t
374lvm_execute(lvm_instance_t *p)
375{
376 node_type_t type;
377 operator_t *operator;
378 lvm_status_t status;
379
380 p->ip = 0;
381 status = LVM_EXECUTION_ERROR;
382 type = get_type(p);
383 switch(type) {
384 case LVM_CMP_OP:
385 operator = get_operator(p);
386 status = eval_logic(p, operator);
387 if(!LVM_ERROR(status)) {
388 PRINTF("The statement is %s\n", status == LVM_TRUE ? "true" : "false");
389 } else {
390 PRINTF("Execution error: %d\n", (int)status);
391 }
392 break;
393 default:
394 PRINTF("Error: The code must start with a relational operator\n");
395 }
396
397 return status;
398}
399
400lvm_status_t
401lvm_set_type(lvm_instance_t *p, node_type_t type)
402{
403 if(p->end + sizeof(node_type_t) >= DB_VM_BYTECODE_SIZE) {
404 PRINTF("Error: overflow in lvm_set_type\n");
405 return LVM_STACK_OVERFLOW;
406 }
407
408 *(node_type_t *)(p->code + p->end) = type;
409 p->end += sizeof(type);
410 return LVM_TRUE;
411}
412
413lvm_status_t
414lvm_set_op(lvm_instance_t *p, operator_t op)
415{
416 lvm_status_t status;
417
418 status = lvm_set_type(p, LVM_ARITH_OP);
419 if(status != LVM_TRUE) {
420 return status;
421 }
422
423 if(p->end + sizeof(op) >= DB_VM_BYTECODE_SIZE) {
424 PRINTF("Error: overflow in lvm_set_op\n");
425 return LVM_STACK_OVERFLOW;
426 }
427
428 memcpy(&p->code[p->end], &op, sizeof(op));
429 p->end += sizeof(op);
430 return LVM_TRUE;
431}
432
433lvm_status_t
434lvm_set_relation(lvm_instance_t *p, operator_t op)
435{
436 lvm_status_t status;
437
438 status = lvm_set_type(p, LVM_CMP_OP);
439 if(status != LVM_TRUE) {
440 return status;
441 }
442
443 if(p->end + sizeof(op) >= DB_VM_BYTECODE_SIZE) {
444 PRINTF("Error: overflow in lvm_set_relation\n");
445 return LVM_STACK_OVERFLOW;
446 }
447
448 memcpy(&p->code[p->end], &op, sizeof(op));
449 p->end += sizeof(op);
450 return LVM_TRUE;
451}
452
453lvm_status_t
454lvm_set_operand(lvm_instance_t *p, operand_t *op)
455{
456 lvm_status_t status;
457
458 status = lvm_set_type(p, LVM_OPERAND);
459 if(status != LVM_TRUE) {
460 return status;
461 }
462
463 if(p->end + sizeof(*op) >= DB_VM_BYTECODE_SIZE) {
464 PRINTF("Error: overflow in lvm_set_operand\n");
465 return LVM_STACK_OVERFLOW;
466 }
467
468 memcpy(&p->code[p->end], op, sizeof(*op));
469 p->end += sizeof(*op);
470 return LVM_TRUE;
471}
472
473lvm_status_t
474lvm_set_long(lvm_instance_t *p, long l)
475{
476 operand_t op;
477
478 op.type = LVM_LONG;
479 op.value.l = l;
480
481 return lvm_set_operand(p, &op);
482}
483
484lvm_status_t
485lvm_register_variable(char *name, operand_type_t type)
486{
487 variable_id_t id;
488 variable_t *var;
489
490 id = lookup(name);
491 if(id == LVM_MAX_VARIABLE_ID) {
492 return LVM_VARIABLE_LIMIT_REACHED;
493 }
494
495 var = &variables[id];
496 if(var->name[0] == '\0') {
497 strncpy(var->name, name, sizeof(var->name) - 1);
498 var->name[sizeof(var->name) - 1] = '\0';
499 var->type = type;
500 }
501
502 return LVM_TRUE;
503}
504
505lvm_status_t
506lvm_set_variable_value(char *name, operand_value_t value)
507{
508 variable_id_t id;
509
510 id = lookup(name);
511 if(id == LVM_MAX_VARIABLE_ID) {
512 return LVM_INVALID_IDENTIFIER;
513 }
514
515 variables[id].value = value;
516 return LVM_TRUE;
517}
518
519lvm_status_t
520lvm_set_variable(lvm_instance_t *p, char *name)
521{
522 operand_t op;
523 variable_id_t id;
524
525 id = lookup(name);
526 if(id == LVM_MAX_VARIABLE_ID) {
527 return LVM_INVALID_IDENTIFIER;
528 }
529
530 PRINTF("var id = %d\n", id);
531 op.type = LVM_VARIABLE;
532 op.value.id = id;
533 return lvm_set_operand(p, &op);
534}
535
536void
537lvm_clone(lvm_instance_t *dst, lvm_instance_t *src)
538{
539 memcpy(dst, src, sizeof(*dst));
540}
541
542static void
543create_intersection(derivation_t *result, derivation_t *d1, derivation_t *d2)
544{
545 int i;
546
547 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
548 if(!d1[i].derived && !d2[i].derived) {
549 continue;
550 } else if(d1[i].derived && !d2[i].derived) {
551 result[i].min.l = d1[i].min.l;
552 result[i].max.l = d1[i].max.l;
553 } else if(!d1[i].derived && d2[i].derived) {
554 result[i].min.l = d2[i].min.l;
555 result[i].max.l = d2[i].max.l;
556 } else {
557 /* Both derivations have been made; create an
558 intersection of the ranges. */
559 if(d1[i].min.l > d2[i].min.l) {
560 result[i].min.l = d1[i].min.l;
561 } else {
562 result[i].min.l = d2[i].min.l;
563 }
564
565 if(d1[i].max.l < d2[i].max.l) {
566 result[i].max.l = d1[i].max.l;
567 } else {
568 result[i].max.l = d2[i].max.l;
569 }
570 }
571 result[i].derived = 1;
572 }
573
574#if DEBUG
575 PRINTF("Created an intersection of D1 and D2\n");
576 PRINTF("D1: \n");
577 print_derivations(d1);
578 PRINTF("D2: \n");
579 print_derivations(d2);
580 PRINTF("Result: \n");
581 print_derivations(result);
582#endif /* DEBUG */
583}
584
585static void
586create_union(derivation_t *result, derivation_t *d1, derivation_t *d2)
587{
588 int i;
589
590 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
591 if(!d1[i].derived && !d2[i].derived) {
592 continue;
593 } else if(d1[i].derived && !d2[i].derived) {
594 result[i].min.l = d1[i].min.l;
595 result[i].max.l = d1[i].max.l;
596 } else if(!d1[i].derived && d2[i].derived) {
597 result[i].min.l = d2[i].min.l;
598 result[i].max.l = d2[i].max.l;
599 } else {
600 /* Both derivations have been made; create a
601 union of the ranges. */
602 if(d1[i].min.l > d2[i].min.l) {
603 result[i].min.l = d2[i].min.l;
604 } else {
605 result[i].min.l = d1[i].min.l;
606 }
607
608 if(d1[i].max.l < d2[i].max.l) {
609 result[i].max.l = d2[i].max.l;
610 } else {
611 result[i].max.l = d1[i].max.l;
612 }
613 }
614 result[i].derived = 1;
615 }
616
617#if DEBUG
618 PRINTF("Created a union of D1 and D2\n");
619 PRINTF("D1: \n");
620 print_derivations(d1);
621 PRINTF("D2: \n");
622 print_derivations(d2);
623 PRINTF("Result: \n");
624 print_derivations(result);
625#endif /* DEBUG */
626}
627
628static int
629derive_relation(lvm_instance_t *p, derivation_t *local_derivations)
630{
631 operator_t *operator;
632 node_type_t type;
633 operand_t operand[2];
634 int i;
635 int variable_id;
636 operand_value_t *value;
637 derivation_t *derivation;
638
639 type = get_type(p);
640 operator = get_operator(p);
641
642 if(IS_CONNECTIVE(*operator)) {
643 derivation_t d1[LVM_MAX_VARIABLE_ID];
644 derivation_t d2[LVM_MAX_VARIABLE_ID];
645
646 if(*operator != LVM_AND && *operator != LVM_OR) {
647 return LVM_DERIVATION_ERROR;
648 }
649
650 PRINTF("Attempting to infer ranges from a logical connective\n");
651
652 memset(d1, 0, sizeof(d1));
653 memset(d2, 0, sizeof(d2));
654
655 if(LVM_ERROR(derive_relation(p, d1)) ||
656 LVM_ERROR(derive_relation(p, d2))) {
657 return LVM_DERIVATION_ERROR;
658 }
659
660 if(*operator == LVM_AND) {
661 create_intersection(local_derivations, d1, d2);
662 } else if(*operator == LVM_OR) {
663 create_union(local_derivations, d1, d2);
664 }
665 return LVM_TRUE;
666 }
667
668 for(i = 0; i < 2; i++) {
669 type = get_type(p);
670 switch(type) {
671 case LVM_OPERAND:
672 get_operand(p, &operand[i]);
673 break;
674 default:
675 return LVM_DERIVATION_ERROR;
676 }
677 }
678
679 if(operand[0].type == LVM_VARIABLE && operand[1].type == LVM_VARIABLE) {
680 return LVM_DERIVATION_ERROR;
681 }
682
683 /* Determine which of the operands that is the variable. */
684 if(operand[0].type == LVM_VARIABLE) {
685 if(operand[1].type == LVM_VARIABLE) {
686 return LVM_DERIVATION_ERROR;
687 }
688 variable_id = operand[0].value.id;
689 value = &operand[1].value;
690 } else {
691 variable_id = operand[1].value.id;
692 value = &operand[0].value;
693 }
694
695 if(variable_id >= LVM_MAX_VARIABLE_ID) {
696 return LVM_DERIVATION_ERROR;
697 }
698
699 PRINTF("variable id %d, value %ld\n", variable_id, *(long *)value);
700
701 derivation = local_derivations + variable_id;
702 /* Default values. */
703 derivation->max.l = LONG_MAX;
704 derivation->min.l = LONG_MIN;
705
706 switch(*operator) {
707 case LVM_EQ:
708 derivation->max = *value;
709 derivation->min = *value;
710 break;
711 case LVM_GE:
712 derivation->min.l = value->l + 1;
713 break;
714 case LVM_GEQ:
715 derivation->min.l = value->l;
716 break;
717 case LVM_LE:
718 derivation->max.l = value->l - 1;
719 break;
720 case LVM_LEQ:
721 derivation->max.l = value->l;
722 break;
723 default:
724 return LVM_DERIVATION_ERROR;
725 }
726
727 derivation->derived = 1;
728
729 return LVM_TRUE;
730}
731
732lvm_status_t
733lvm_derive(lvm_instance_t *p)
734{
735 return derive_relation(p, derivations);
736}
737
738lvm_status_t
739lvm_get_derived_range(lvm_instance_t *p, char *name,
740 operand_value_t *min, operand_value_t *max)
741{
742 int i;
743
744 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
745 if(strcmp(name, variables[i].name) == 0) {
746 if(derivations[i].derived) {
747 *min = derivations[i].min;
748 *max = derivations[i].max;
749 return LVM_TRUE;
750 }
751 return LVM_DERIVATION_ERROR;
752 }
753 }
754 return LVM_INVALID_IDENTIFIER;
755}
756
757#if DEBUG
758static lvm_ip_t
759print_operator(lvm_instance_t *p, lvm_ip_t index)
760{
761 operator_t operator;
762 struct operator_map {
763 operator_t op;
764 char *representation;
765 };
766 struct operator_map operator_map[] = {
767 {LVM_ADD, "+"},
768 {LVM_SUB, "-"},
769 {LVM_MUL, "*"},
770 {LVM_DIV, "/"},
771 {LVM_GE, ">"},
772 {LVM_GEQ, ">="},
773 {LVM_LE, "<"},
774 {LVM_LEQ, "<="},
775 {LVM_EQ, "="},
776 {LVM_NEQ, "<>"},
777 {LVM_AND, "/\\"},
778 {LVM_OR, "\\/"},
779 {LVM_NOT, "!"}
780 };
781 int i;
782
783 memcpy(&operator, p->code + index, sizeof(operator));
784
785 for(i = 0; i < sizeof(operator_map) / sizeof(operator_map[0]); i++) {
786 if(operator_map[i].op == operator) {
787 PRINTF("%s ", operator_map[i].representation);
788 break;
789 }
790 }
791
792 return index + sizeof(operator_t);
793}
794
795static lvm_ip_t
796print_operand(lvm_instance_t *p, lvm_ip_t index)
797{
798 operand_t operand;
799
800 memcpy(&operand, p->code + index, sizeof(operand));
801
802 switch(operand.type) {
803 case LVM_VARIABLE:
804 if(operand.value.id >= LVM_MAX_VARIABLE_ID ||
805 variables[operand.value.id].name == NULL) {
806 PRINTF("var(id:%d):?? ", operand.value.id);
807 } else {
808 PRINTF("var(%s):%ld ", variables[operand.value.id].name,
809 variables[operand.value.id].value.l);
810 }
811 break;
812 case LVM_LONG:
813 PRINTF("long:%ld ", operand.value.l);
814 break;
815 default:
816 PRINTF("?? ");
817 break;
818 }
819
820 return index + sizeof(operand_t);
821}
822
823static lvm_ip_t
824print_relation(lvm_instance_t *p, lvm_ip_t index)
825{
826 /* Relational operators are stored as ordinary operators. */
827 return print_operator(p, index);
828}
829#endif /* DEBUG */
830
831void
832lvm_print_code(lvm_instance_t *p)
833{
834#if DEBUG
835 lvm_ip_t ip;
836
837 PRINTF("Code: ");
838
839 for(ip = 0; ip < p->end;) {
840 switch(*(node_type_t *)(p->code + ip)) {
841 case LVM_CMP_OP:
842 ip = print_relation(p, ip + sizeof(node_type_t));
843 break;
844 case LVM_ARITH_OP:
845 ip = print_operator(p, ip + sizeof(node_type_t));
846 break;
847 case LVM_OPERAND:
848 ip = print_operand(p, ip + sizeof(node_type_t));
849 break;
850 default:
851 PRINTF("Invalid opcode: 0x%x ", p->code[ip]);
852 ip = p->end;
853 break;
854 }
855 }
856 putchar('\n');
857#endif
858}
859
860void
861lvm_print_derivations(lvm_instance_t *p)
862{
863#if DEBUG
864 print_derivations(derivations);
865#endif /* DEBUG */
866}
867
868#ifdef TEST
869int
870main(void)
871{
872 lvm_instance_t p;
873 unsigned char code[256];
874
875 lvm_reset(&p, code, sizeof(code));
876
877 lvm_register_variable("z", LVM_LONG);
878 lvm_set_variable_value("z", (operand_value_t)15L);
879
880 lvm_register_variable("y", LVM_LONG);
881 lvm_set_variable_value("y", (operand_value_t)109L);
882
883 /* Infix: 109 = y /\ 20 > 70 - (6 + z * 3) => 109 = 109 /\ 20 > 19 => true */
884 lvm_set_relation(&p, LVM_AND);
885 lvm_set_relation(&p, LVM_EQ);
886 lvm_set_long(&p, 109);
887 lvm_set_variable(&p, "y");
888 lvm_set_relation(&p, LVM_GE);
889 lvm_set_long(&p, 20);
890 lvm_set_op(&p, LVM_SUB);
891 lvm_set_long(&p, 70);
892 lvm_set_op(&p, LVM_ADD);
893 lvm_set_long(&p, 6);
894 lvm_set_op(&p, LVM_MUL);
895 lvm_set_variable(&p, "z");
896 lvm_set_long(&p, 3);
897
898 lvm_print_code(&p);
899
900 lvm_execute(&p);
901
902 /* Infix: !(9999 + 1 < -1 + 10001) => !(10000 < 10000) => true */
903 lvm_reset(&p, code, sizeof(code));
904 lvm_set_relation(&p, LVM_NOT);
905 lvm_set_relation(&p, LVM_LE);
906 lvm_set_op(&p, LVM_ADD);
907 lvm_set_long(&p, 9999);
908 lvm_set_long(&p, 1);
909 lvm_set_op(&p, LVM_ADD);
910 lvm_set_long(&p, -1);
911 lvm_set_long(&p, 10001);
912
913 lvm_print_code(&p);
914
915 lvm_execute(&p);
916
917 /* Derivation tests */
918
919 /* Infix: a = 5 => a:(5,5) */
920 lvm_reset(&p, code, sizeof(code));
921 lvm_register_variable("a", LVM_LONG);
922 lvm_set_relation(&p, LVM_EQ);
923 lvm_set_variable(&p, "a");
924 lvm_set_long(&p, 5);
925
926 lvm_derive(&p);
927 lvm_print_derivations(&p);
928
929 /* Infix: a < 10 => a:(-oo,9) */
930 lvm_reset(&p, code, sizeof(code));
931 lvm_register_variable("a", LVM_LONG);
932 lvm_set_relation(&p, LVM_LE);
933 lvm_set_variable(&p, "a");
934 lvm_set_long(&p, 10);
935
936 lvm_derive(&p);
937 lvm_print_derivations(&p);
938
939 /* Infix: a < 100 /\ 10 < a => a:(11,99) */
940 lvm_reset(&p, code, sizeof(code));
941 lvm_register_variable("a", LVM_LONG);
942 lvm_set_relation(&p, LVM_AND);
943 lvm_set_relation(&p, LVM_LE);
944 lvm_set_variable(&p, "a");
945 lvm_set_long(&p, 100);
946 lvm_set_relation(&p, LVM_GE);
947 lvm_set_long(&p, 10);
948 lvm_set_variable(&p, "a");
949
950 lvm_derive(&p);
951 lvm_print_derivations(&p);
952
953 /* Infix: a < 100 /\ b > 100 => a:(-oo,99), b:(101,oo) */
954 lvm_reset(&p, code, sizeof(code));
955 lvm_register_variable("a", LVM_LONG);
956 lvm_register_variable("b", LVM_LONG);
957 lvm_set_relation(&p, LVM_AND);
958 lvm_set_relation(&p, LVM_LE);
959 lvm_set_variable(&p, "a");
960 lvm_set_long(&p, 100);
961 lvm_set_relation(&p, LVM_GE);
962 lvm_set_variable(&p, "b");
963 lvm_set_long(&p, 100);
964
965 lvm_derive(&p);
966 lvm_print_derivations(&p);
967
968 /* Infix: a < 100 \/ a < 1000 \/ a < 1902 => a:(-oo,1901) */
969 lvm_reset(&p, code, sizeof(code));
970 lvm_register_variable("a", LVM_LONG);
971 lvm_set_relation(&p, LVM_OR);
972 lvm_set_relation(&p, LVM_LE);
973 lvm_set_variable(&p, "a");
974 lvm_set_long(&p, 100);
975 lvm_set_relation(&p, LVM_OR);
976 lvm_set_relation(&p, LVM_LE);
977 lvm_set_long(&p, 1000);
978 lvm_set_variable(&p, "a");
979 lvm_set_relation(&p, LVM_LE);
980 lvm_set_variable(&p, "a");
981 lvm_set_long(&p, 1902);
982
983 lvm_derive(&p);
984 lvm_print_derivations(&p);
985
986 /* Infix: (a < 100 /\ a < 90 /\ a > 80 /\ a < 105) \/ b > 10000 =>
987 a:(81,89), b:(10001:oo) */
988 lvm_reset(&p, code, sizeof(code));
989 lvm_register_variable("a", LVM_LONG);
990 lvm_register_variable("b", LVM_LONG);
991
992 lvm_set_relation(&p, LVM_OR);
993 lvm_set_relation(&p, LVM_GE);
994 lvm_set_variable(&p, "b");
995 lvm_set_long(&p, 10000);
996
997 lvm_set_relation(&p, LVM_AND);
998 lvm_set_relation(&p, LVM_LE);
999 lvm_set_variable(&p, "a");
1000 lvm_set_long(&p, 100);
1001 lvm_set_relation(&p, LVM_AND);
1002 lvm_set_relation(&p, LVM_LE);
1003 lvm_set_variable(&p, "a");
1004 lvm_set_long(&p, 90);
1005 lvm_set_relation(&p, LVM_AND);
1006 lvm_set_relation(&p, LVM_GE);
1007 lvm_set_variable(&p, "a");
1008 lvm_set_long(&p, 80);
1009 lvm_set_relation(&p, LVM_LE);
1010 lvm_set_variable(&p, "a");
1011 lvm_set_long(&p, 105);
1012
1013 lvm_derive(&p);
1014 lvm_print_derivations(&p);
1015
1016 printf("Done\n");
1017
1018 return 0;
1019}
1020#endif
aql.h
Definitions and declarations for AQL, the Antelope Query Language.
debug.h
A set of debugging macros.
lvm.h
Definitions and declarations for the Propositional Logic Engine.