1 #if defined HAVE_CONFIG_H
2 # include "config.h"
3 #endif /* HAVE_CONFIG_H */
4 #include <stdlib.h>
5 #include <string.h>
6 #include <stdio.h>
7 #include <stdbool.h>
8 #include "strops.h"
9 #include "dexpr.h"
10 #include "dexpr-parser.h"
11
12 #if !defined STANDALONE
13 # if defined __INTEL_COMPILER
14 # pragma warning (disable:2259)
15 # endif /* __INTEL_COMPILER */
16 # include "dexpr-parser.c"
17 # if defined __INTEL_COMPILER
18 # pragma warning (default:2259)
19 # endif /* __INTEL_COMPILER */
20
21 # if defined __INTEL_COMPILER
22 # pragma warning (disable:2557)
23 # endif /* __INTEL_COMPILER */
24 # include "dexpr-scanner.c"
25 # if defined __INTEL_COMPILER
26 # pragma warning (default:2557)
27 # endif /* __INTEL_COMPILER */
28 #endif /* !STANDALONE */
29
30 static void
free_dexpr(dexpr_t root)31 free_dexpr(dexpr_t root)
32 {
33 /* recursive free :( */
34 switch (root->type) {
35 case DEX_CONJ:
36 case DEX_DISJ:
37 if (root->left != NULL) {
38 free_dexpr(root->left);
39 free(root->left);
40 }
41 if (root->right != NULL) {
42 free_dexpr(root->right);
43 free(root->right);
44 }
45 break;
46 case DEX_UNK:
47 case DEX_VAL:
48 default:
49 break;
50 }
51 return;
52 }
53
54 static __attribute__((unused)) void
__pr_val(struct dexkv_s * kv)55 __pr_val(struct dexkv_s *kv)
56 {
57 switch (kv->sp.spfl) {
58 case DT_SPFL_N_DCNT_MON:
59 fputs("%d ", stdout);
60 break;
61 case DT_SPFL_N_MON:
62 case DT_SPFL_S_MON:
63 fputs("%b ", stdout);
64 break;
65 case DT_SPFL_N_YEAR:
66 fputs("%Y ", stdout);
67 break;
68 case DT_SPFL_N_DCNT_WEEK:
69 case DT_SPFL_S_WDAY:
70 fputs("%a ", stdout);
71 break;
72 case DT_SPFL_N_WCNT_MON:
73 fputs("%c ", stdout);
74 break;
75 case DT_SPFL_N_DCNT_YEAR:
76 fputs("%D ", stdout);
77 break;
78 case DT_SPFL_N_WCNT_YEAR:
79 fputs("%C ", stdout);
80 break;
81 default:
82 break;
83 }
84
85 switch (kv->op) {
86 case OP_LT:
87 fputs("< ", stdout);
88 break;
89 case OP_LE:
90 fputs("<= ", stdout);
91 break;
92 case OP_GT:
93 fputs("> ", stdout);
94 break;
95 case OP_GE:
96 fputs(">= ", stdout);
97 break;
98 case OP_NE:
99 fputs("!= ", stdout);
100 break;
101 case OP_EQ:
102 default:
103 fputs("== ", stdout);
104 break;
105 }
106
107 switch (kv->sp.spfl) {
108 case DT_SPFL_N_STD: {
109 char buf[32];
110 dt_strfdt(buf, sizeof(buf), NULL, kv->d);
111 fputs(buf, stdout);
112 break;
113 }
114 case DT_SPFL_N_DCNT_MON:
115 fprintf(stdout, "%02d", kv->s);
116 break;
117 case DT_SPFL_N_MON:
118 case DT_SPFL_S_MON:
119 if (kv->s >= 0 && kv->s <= 12) {
120 fputs(dut_abbr_mon[kv->s], stdout);
121 }
122 break;
123 case DT_SPFL_N_YEAR:
124 fprintf(stdout, "%04d", kv->s);
125 break;
126 case DT_SPFL_N_DCNT_WEEK:
127 case DT_SPFL_S_WDAY:
128 if (kv->s >= 0 && kv->s <= 7) {
129 fputs(dut_abbr_wday[kv->s], stdout);
130 }
131 break;
132 case DT_SPFL_N_WCNT_MON:
133 case DT_SPFL_N_WCNT_YEAR:
134 fprintf(stdout, "%02d", kv->s);
135 break;
136 case DT_SPFL_N_DCNT_YEAR:
137 fprintf(stdout, "%03d", kv->s);
138 break;
139 default:
140 break;
141 }
142 return;
143 }
144
145 static __attribute__((unused)) void
__pr(dexpr_t root,size_t ind)146 __pr(dexpr_t root, size_t ind)
147 {
148 switch (root->type) {
149 case DEX_VAL:
150 for (size_t i = 0; i < ind; i++) {
151 fputc(' ', stdout);
152 }
153 if (root->nega) {
154 fputs("!(", stdout);
155 }
156 __pr_val(root->kv);
157 if (root->nega) {
158 fputs(")\n", stdout);
159 } else {
160 fputc('\n', stdout);
161 }
162 break;
163
164 case DEX_CONJ:
165 for (size_t i = 0; i < ind; i++) {
166 fputc(' ', stdout);
167 }
168 if (!root->nega) {
169 fputs("AND\n", stdout);
170 } else {
171 fputs("NAND\n", stdout);
172 }
173 __pr(root->left, ind + 2);
174 __pr(root->right, ind + 2);
175 break;
176
177 case DEX_DISJ:
178 for (size_t i = 0; i < ind; i++) {
179 fputc(' ', stdout);
180 }
181 if (!root->nega) {
182 fputs("OR\n", stdout);
183 } else {
184 fputs("NOR\n", stdout);
185 }
186 __pr(root->left, ind + 2);
187 __pr(root->right, ind + 2);
188 break;
189
190 case DEX_UNK:
191 default:
192 for (size_t i = 0; i < ind; i++) {
193 fputc(' ', stdout);
194 }
195 if (root->left != NULL) {
196 fputs("ROOT\n", stderr);
197 __pr(root->left, ind + 2);
198 break;
199 }
200 break;
201 }
202 return;
203 }
204
205 static __attribute__((unused)) void
__pr_infix(dexpr_t root)206 __pr_infix(dexpr_t root)
207 {
208 if (root->type == DEX_VAL) {
209 __pr_val(root->kv);
210 return;
211 }
212
213 __pr_infix(root->left);
214
215 switch (root->type) {
216 case DEX_CONJ:
217 fputs(" && ", stdout);
218 break;
219
220 case DEX_DISJ:
221 fputs(" || ", stdout);
222 break;
223
224 case DEX_VAL:
225 case DEX_UNK:
226 default:
227 /* shouldn't happen :O */
228 fputs(" bollocks ", stdout);
229 break;
230
231 }
232 __pr_infix(root->right);
233
234 /* just ascend */
235 return;
236 }
237
238
239 static dexpr_t
make_dexpr(dex_type_t type)240 make_dexpr(dex_type_t type)
241 {
242 dexpr_t res;
243
244 if ((res = calloc(1, sizeof(*res))) != NULL) {
245 res->type = type;
246 }
247 return res;
248 }
249
250 static dexpr_t
dexpr_copy(const_dexpr_t src)251 dexpr_copy(const_dexpr_t src)
252 {
253 dexpr_t res;
254
255 if ((res = calloc(1, sizeof(*res))) == NULL) {
256 return NULL;
257 }
258 /* otherwise start by (shallow) copying things */
259 memcpy(res, src, sizeof(*res));
260
261 /* deep copy anyone? */
262 switch (src->type) {
263 case DEX_CONJ:
264 case DEX_DISJ:
265 res->left = dexpr_copy(src->left);
266 res->right = dexpr_copy(src->right);
267 break;
268 case DEX_VAL:
269 case DEX_UNK:
270 default:
271 break;
272 }
273 return res;
274 }
275
276 static dexpr_t
dexpr_copy_j(dexpr_t src)277 dexpr_copy_j(dexpr_t src)
278 {
279 /* copy SRC, but only if it's a junction (disjunction or conjunction) */
280 if (src->type == DEX_VAL) {
281 return (dexpr_t)src;
282 }
283 return dexpr_copy(src);
284 }
285
286 static void
__dnf(dexpr_t root)287 __dnf(dexpr_t root)
288 {
289 /* recursive __dnf'er */
290 switch (root->type) {
291 case DEX_CONJ: {
292 /* check if one of the children is a disjunction */
293 dex_type_t rlt = root->left->type;
294 dex_type_t rrt = root->right->type;
295
296 if (rlt == DEX_DISJ && rrt == DEX_DISJ) {
297 /* complexestest case
298 * (a|b)&(c|d) -> (a&c)|(a&d)|(b&c)|(b&d) */
299 dexpr_t a;
300 dexpr_t b;
301 dexpr_t c;
302 dexpr_t d;
303
304 /* get the new idea of b and c */
305 a = root->left->left;
306 b = root->left->right;
307 c = root->right->left;
308 d = root->right->right;
309
310 /* now reuse what's possible */
311 root->type = DEX_DISJ;
312 root->left->type = DEX_CONJ;
313 #if 0
314 /* silly assignment, a comes from left->left */
315 root->left->left = a;
316 #endif /* 0 */
317 root->left->right = c;
318
319 root->right->type = DEX_DISJ;
320 root->right->left = make_dexpr(DEX_CONJ);
321 root->right->left->left = dexpr_copy_j(a);
322 root->right->left->right = d;
323
324 root->right->right = make_dexpr(DEX_DISJ);
325 root->right->right->left = make_dexpr(DEX_CONJ);
326 root->right->right->left->left = b;
327 root->right->right->left->right = dexpr_copy_j(c);
328 /* right side, finalise the right branches with CONJ */
329 root->right->right->right = make_dexpr(DEX_CONJ);
330 root->right->right->right->left = dexpr_copy_j(b);
331 root->right->right->right->right = dexpr_copy_j(d);
332
333 } else if (rlt == DEX_DISJ || rrt == DEX_DISJ) {
334 /* ok'ish case
335 * a&(b|c) -> a&b|a&c
336 * the other case gets normalised: (a|b)&c -> c&(a|b) */
337 dexpr_t a;
338 dexpr_t b;
339 dexpr_t c;
340
341 /* put the non-DISJ case left */
342 if ((a = root->left)->type == DEX_DISJ) {
343 a = root->right;
344 root->right = root->left;
345 }
346 /* get the new idea of b and c */
347 b = root->right->left;
348 c = root->right->right;
349
350 /* turn into disjoint */
351 root->type = DEX_DISJ;
352
353 /* inflate left branch */
354 root->left = make_dexpr(DEX_CONJ);
355 root->left->left = a;
356 root->left->right = b;
357
358 /* rearrange this node now, reuse the right disjoint */
359 root->right->type = DEX_CONJ;
360 root->right->left = a;
361 root->right->right = c;
362 }
363 /* fallthrough! */
364 }
365 case DEX_DISJ:
366 /* nothing to be done other than a quick descent */
367 __dnf(root->left);
368 __dnf(root->right);
369
370 /* upon ascent fixup double OR's */
371 if (root->left->type == DEX_DISJ &&
372 root->right->type == DEX_DISJ) {
373 /* | |
374 * / \ / \
375 * | | ~> a |
376 * / \ / \ / \
377 * a b c d b |
378 * / \
379 * c d */
380 dexpr_t i = root->left;
381 dexpr_t j = root->right;
382 dexpr_t a = i->left;
383 dexpr_t b = i->right;
384 dexpr_t c = j->left;
385
386 root->left = a;
387 root->right = i;
388 i->left = b;
389 i->right = j;
390 j->left = c;
391
392 } else if (root->left->type == DEX_DISJ) {
393 /* | |
394 * / \ / \
395 * | c ~> a |
396 * / \ / \
397 * a b b c */
398 dexpr_t i = root->left;
399 dexpr_t c = root->right;
400 dexpr_t a = i->left;
401 dexpr_t b = i->right;
402
403 root->left = a;
404 root->right = i;
405 i->left = b;
406 i->right = c;
407 }
408 break;
409
410 case DEX_VAL:
411 case DEX_UNK:
412 default:
413 /* can't do anything to get the DNF going */
414 break;
415 }
416 return;
417 }
418
419 static void
__nega_kv(struct dexkv_s * kv)420 __nega_kv(struct dexkv_s *kv)
421 {
422 /* assume the parent dexpr has the nega flag set, negate KV */
423 kv->op = ~kv->op;
424 return;
425 }
426
427 static void
__denega(dexpr_t root)428 __denega(dexpr_t root)
429 {
430 dexpr_t left;
431 dexpr_t right;
432
433 if (root->nega) {
434 /* negate */
435 root->nega = 0;
436
437 switch (root->type) {
438 case DEX_CONJ:
439 /* !(a&b) -> !a | !b */
440 root->type = DEX_DISJ;
441 break;
442 case DEX_DISJ:
443 /* !(a|b) -> !a & !b */
444 root->type = DEX_DISJ;
445 break;
446 case DEX_VAL:
447 __nega_kv(root->kv);
448 /* fallthrough */
449 case DEX_UNK:
450 default:
451 return;
452 }
453
454 if ((left = root->left) != NULL) {
455 left->nega = ~left->nega;
456 }
457 if ((right = root->right) != NULL) {
458 right->nega = ~right->nega;
459 }
460 } else {
461 switch (root->type) {
462 case DEX_CONJ:
463 case DEX_DISJ:
464 left = root->left;
465 right = root->right;
466 break;
467 case DEX_VAL:
468 case DEX_UNK:
469 default:
470 return;
471 }
472 }
473 /* descend */
474 if (left != NULL) {
475 __denega(left);
476 }
477 if (right != NULL) {
478 __denega(right);
479 }
480 return;
481 }
482
483 static void
dexpr_simplify(dexpr_t root)484 dexpr_simplify(dexpr_t root)
485 {
486 __denega(root);
487 __dnf(root);
488 return;
489 }
490
491 static int
__cmp(struct dt_dt_s stream,struct dt_dt_s cell)492 __cmp(struct dt_dt_s stream, struct dt_dt_s cell)
493 {
494 /* special promoting/demoting version of dt_dtcmp()
495 * if CELL is d-only or t-only, demote STREAM */
496 if (dt_sandwich_only_d_p(cell)) {
497 return dt_dcmp(stream.d, cell.d);
498 } else if (dt_sandwich_only_t_p(cell)) {
499 return dt_tcmp(stream.t, cell.t);
500 }
501 return dt_dtcmp(stream, cell);
502 }
503
504
505 static bool
dexkv_matches_p(const_dexkv_t dkv,struct dt_dt_s d)506 dexkv_matches_p(const_dexkv_t dkv, struct dt_dt_s d)
507 {
508 signed int cmp;
509 bool res;
510
511 if (dkv->sp.spfl == DT_SPFL_N_STD) {
512 if ((cmp = __cmp(d, dkv->d)) == -2) {
513 return false;
514 }
515 switch (dkv->op) {
516 case OP_UNK:
517 case OP_EQ:
518 res = cmp == 0;
519 break;
520 case OP_LT:
521 res = cmp < 0;
522 break;
523 case OP_LE:
524 res = cmp <= 0;
525 break;
526 case OP_GT:
527 res = cmp > 0;
528 break;
529 case OP_GE:
530 res = cmp >= 0;
531 break;
532 case OP_NE:
533 res = cmp != 0;
534 break;
535 case OP_TRUE:
536 res = true;
537 break;
538 default:
539 res = false;
540 break;
541 }
542 return res;
543 }
544 /* otherwise it's stuff that uses the S slot */
545 switch (dkv->sp.spfl) {
546 case DT_SPFL_N_YEAR:
547 cmp = dt_get_year(d.d);
548 break;
549 case DT_SPFL_N_MON:
550 case DT_SPFL_S_MON:
551 cmp = dt_get_mon(d.d);
552 break;
553 case DT_SPFL_N_DCNT_MON:
554 cmp = dt_get_mday(d.d);
555 break;
556 case DT_SPFL_N_DCNT_WEEK:
557 case DT_SPFL_S_WDAY:
558 cmp = dt_get_wday(d.d);
559 break;
560 case DT_SPFL_N_WCNT_MON:
561 /* exotic function, needs extern'ing */
562 cmp = /*dt_get_count(d)*/0;
563 break;
564 case DT_SPFL_N_DCNT_YEAR:
565 cmp = dt_get_yday(d.d);
566 break;
567 case DT_SPFL_N_WCNT_YEAR:
568 /* %C/%W week count */
569 cmp = dt_get_wcnt_year(d.d, dkv->sp.wk_cnt);
570 break;
571 case DT_SPFL_N_STD:
572 default:
573 return false;
574 }
575 /* now do the actual comparison */
576 switch (dkv->op) {
577 case OP_EQ:
578 res = dkv->s == cmp;
579 break;
580 case OP_LT:
581 res = dkv->s < cmp;
582 break;
583 case OP_LE:
584 res = dkv->s <= cmp;
585 break;
586 case OP_GT:
587 res = dkv->s > cmp;
588 break;
589 case OP_GE:
590 res = dkv->s >= cmp;
591 break;
592 case OP_NE:
593 res = dkv->s != cmp;
594 break;
595 case OP_TRUE:
596 res = true;
597 break;
598 default:
599 case OP_UNK:
600 res = false;
601 break;
602 }
603 return res;
604 }
605
606 static bool
__conj_matches_p(const_dexpr_t dex,struct dt_dt_s d)607 __conj_matches_p(const_dexpr_t dex, struct dt_dt_s d)
608 {
609 const_dexpr_t a;
610
611 for (a = dex; a->type == DEX_CONJ; a = a->right) {
612 if (!dexkv_matches_p(a->left->kv, d)) {
613 return false;
614 }
615 }
616 /* rightmost cell might be a DEX_VAL */
617 return dexkv_matches_p(a->kv, d);
618 }
619
620 static bool
__disj_matches_p(const_dexpr_t dex,struct dt_dt_s d)621 __disj_matches_p(const_dexpr_t dex, struct dt_dt_s d)
622 {
623 const_dexpr_t o;
624
625 for (o = dex; o->type == DEX_DISJ; o = o->right) {
626 if (__conj_matches_p(o->left, d)) {
627 return true;
628 }
629 }
630 /* rightmost cell may be a DEX_VAL */
631 return __conj_matches_p(o, d);
632 }
633
634 static __attribute__((unused)) bool
dexpr_matches_p(const_dexpr_t dex,struct dt_dt_s d)635 dexpr_matches_p(const_dexpr_t dex, struct dt_dt_s d)
636 {
637 return __disj_matches_p(dex, d);
638 }
639
640
641 #if defined STANDALONE
642 int
main(int argc,char * argv[])643 main(int argc, char *argv[])
644 {
645 dexpr_t root;
646
647 for (int i = 1; i < argc; i++) {
648 root = NULL;
649 dexpr_parse(&root, argv[i], strlen(argv[i]));
650 __pr(root, 0);
651 fputc('\n', stdout);
652 dexpr_simplify(root);
653 __pr(root, 0);
654 fputc('\n', stdout);
655 /* also print an infix line */
656 __pr_infix(root);
657 fputc('\n', stdout);
658 free_dexpr(root);
659 }
660 return 0;
661 }
662 #endif /* STANDALONE */
663
664 /* dexpr.c ends here */
665