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 
69 struct variable {
70  operand_type_t type;
71  operand_value_t value;
72  char name[LVM_MAX_NAME_LENGTH + 1];
73 };
74 typedef struct variable variable_t;
75 
76 struct derivation {
77  operand_value_t max;
78  operand_value_t min;
79  uint8_t derived;
80 };
81 typedef struct derivation derivation_t;
82 
83 /* Registered variables for a LVM expression. Their values may be
84  changed between executions of the expression. */
85 static variable_t variables[LVM_MAX_VARIABLE_ID];
86 
87 /* Range derivations of variables that are used for index searches. */
88 static derivation_t derivations[LVM_MAX_VARIABLE_ID];
89 
90 #if DEBUG
91 static void
92 print_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 
105 static variable_id_t
106 lookup(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 
119 static operator_t *
120 get_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 
129 static void
130 get_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 
136 static node_type_t
137 get_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 
147 static long
148 operand_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 
165 static lvm_status_t
166 eval_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 
221 static int
222 eval_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 
300 void
301 lvm_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 
314 lvm_ip_t
315 lvm_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 
329 lvm_ip_t
330 lvm_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 
351 lvm_ip_t
352 lvm_get_end(lvm_instance_t *p)
353 {
354  return p->end;
355 }
356 
357 lvm_ip_t
358 lvm_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 
373 lvm_status_t
374 lvm_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 
400 lvm_status_t
401 lvm_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 
413 lvm_status_t
414 lvm_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 
433 lvm_status_t
434 lvm_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 
453 lvm_status_t
454 lvm_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 
473 lvm_status_t
474 lvm_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 
484 lvm_status_t
485 lvm_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 
505 lvm_status_t
506 lvm_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 
519 lvm_status_t
520 lvm_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 
536 void
537 lvm_clone(lvm_instance_t *dst, lvm_instance_t *src)
538 {
539  memcpy(dst, src, sizeof(*dst));
540 }
541 
542 static void
543 create_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 
585 static void
586 create_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 
628 static int
629 derive_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 
732 lvm_status_t
733 lvm_derive(lvm_instance_t *p)
734 {
735  return derive_relation(p, derivations);
736 }
737 
738 lvm_status_t
739 lvm_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
758 static lvm_ip_t
759 print_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 
795 static lvm_ip_t
796 print_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 
823 static lvm_ip_t
824 print_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 
831 void
832 lvm_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 
860 void
861 lvm_print_derivations(lvm_instance_t *p)
862 {
863 #if DEBUG
864  print_derivations(derivations);
865 #endif /* DEBUG */
866 }
867 
868 #ifdef TEST
869 int
870 main(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
A set of debugging macros.
Definitions and declarations for AQL, the Antelope Query Language.
Definitions and declarations for the Propositional Logic Engine.