r2188 - made closing brace be correctly processed right after a keyword
[racktables] / inc / code.php
1 <?php
2 /*
3 * This file implements lexical scanner and syntax analyzer for the RackCode
4 * access configuration language.
5 *
6 * The language consists of the following lexems:
7 *
8 * LEX_LBRACE
9 * LEX_RBRACE
10 * LEX_DECISION
11 * LEX_DEFINE
12 * LEX_BOOLCONST
13 * LEX_NOT
14 * LEX_TAG
15 * LEX_PREDICATE
16 * LEX_BOOLOP
17 *
18 */
19
20 // Complain about martian char.
21 function lexError1 ($state, $text, $pos, $ln = 'N/A')
22 {
23 return array
24 (
25 'result' => 'NAK',
26 'load' => "Invalid character '" . mb_substr ($text, $pos, 1) . "' near line ${ln}"
27 );
28 }
29
30 // Complain about martian keyword.
31 function lexError2 ($word, $ln = 'N/A')
32 {
33 return array
34 (
35 'result' => 'NAK',
36 'load' => "Invalid keyword '${word}' near line ${ln}"
37 );
38 }
39
40 // Complain about wrong FSM state.
41 function lexError3 ($state, $ln = 'N/A')
42 {
43 return array
44 (
45 'result' => 'NAK',
46 'load' => "Lexical error during '${state}' near line ${ln}"
47 );
48 }
49
50 function lexError4 ($s, $ln = 'N/A')
51 {
52 return array
53 (
54 'result' => 'NAK',
55 'load' => "Invalid name '${s}' near line ${ln}"
56 );
57 }
58
59 // Produce a list of lexems from the given text. Possible lexems are:
60 function getLexemsFromRackCode ($text)
61 {
62 $ret = array();
63 $textlen = mb_strlen ($text);
64 $lineno = 1;
65 $state = "ESOTSM";
66 for ($i = 0; $i < $textlen; $i++) :
67 $char = mb_substr ($text, $i, 1);
68 $newstate = $state;
69 switch ($state) :
70 case 'ESOTSM':
71 switch (TRUE)
72 {
73 case ($char == '('):
74 $ret[] = array ('type' => 'LEX_LBRACE', 'lineno' => $lineno);
75 break;
76 case ($char == ')'):
77 $ret[] = array ('type' => 'LEX_RBRACE', 'lineno' => $lineno);
78 break;
79 case ($char == '#'):
80 $newstate = 'skipping comment';
81 break;
82 case (mb_ereg ('[[:alpha:]]', $char) > 0):
83 $newstate = 'reading keyword';
84 $buffer = $char;
85 break;
86 case ($char == "\r"): // FIXME: this should never happen
87 case ($char == "\n"):
88 $lineno++; // fall through
89 case ($char == " "):
90 case ($char == "\t"):
91 // nom-nom...
92 break;
93 case ($char == '{'):
94 $newstate = 'reading tag 1';
95 break;
96 case ($char == '['):
97 $newstate = 'reading predicate 1';
98 break;
99 default:
100 return lexError1 ($state, $text, $i, $lineno);
101 }
102 break;
103 case 'reading keyword':
104 switch (TRUE)
105 {
106 case (mb_ereg ('[[:alpha:]]', $char) > 0):
107 $buffer .= $char;
108 break;
109 case ($char == "\n"):
110 $lineno++; // fall through
111 case ($char == " "):
112 case ($char == "\t"):
113 case ($char == ')'): // this will be handled below
114 // got a word, sort it out
115 switch ($buffer)
116 {
117 case 'allow':
118 case 'deny':
119 $ret[] = array ('type' => 'LEX_DECISION', 'load' => $buffer, 'lineno' => $lineno);
120 break;
121 case 'define':
122 $ret[] = array ('type' => 'LEX_DEFINE', 'lineno' => $lineno);
123 break;
124 case 'and':
125 case 'or':
126 $ret[] = array ('type' => 'LEX_BOOLOP', 'load' => $buffer, 'lineno' => $lineno);
127 break;
128 case 'not':
129 $ret[] = array ('type' => 'LEX_NOT', 'lineno' => $lineno);
130 break;
131 case 'false':
132 case 'true':
133 $ret[] = array ('type' => 'LEX_BOOLCONST', 'load' => $buffer, 'lineno' => $lineno);
134 break;
135 default:
136 return lexError2 ($buffer, $lineno);
137 }
138 if ($char == ')')
139 $ret[] = array ('type' => 'LEX_RBRACE', 'lineno' => $lineno);
140 $newstate = 'ESOTSM';
141 break;
142 default:
143 return lexError1 ($state, $text, $i, $lineno);
144 }
145 break;
146 case 'reading tag 1':
147 switch (TRUE)
148 {
149 case ($char == "\n"):
150 case ($char == "\r"): // FIXME: is this really expected?
151 $lineno++; // fall through
152 case ($char == " "):
153 case ($char == "\t"):
154 // nom-nom...
155 break;
156 case (mb_ereg ('[[:alnum:]\$]', $char) > 0):
157 $buffer = $char;
158 $newstate = 'reading tag 2';
159 break;
160 default:
161 return lexError1 ($state, $text, $i, $lineno);
162 }
163 break;
164 case 'reading tag 2':
165 switch (TRUE)
166 {
167 case ($char == '}'):
168 $buffer = rtrim ($buffer);
169 if (!validTagName ($buffer, TRUE))
170 return lexError4 ($buffer, $lineno);
171 $ret[] = array ('type' => 'LEX_TAG', 'load' => $buffer, 'lineno' => $lineno);
172 $newstate = 'ESOTSM';
173 break;
174 case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
175 $buffer .= $char;
176 break;
177 default:
178 return lexError1 ($state, $text, $i, $lineno);
179 }
180 break;
181 case 'reading predicate 1':
182 switch (TRUE)
183 {
184 case (preg_match ('/^[ \t\n\r]$/', $char)):
185 // nom-nom...
186 break;
187 case (mb_ereg ('[[:alnum:]]', $char) > 0):
188 $buffer = $char;
189 $newstate = 'reading predicate 2';
190 break;
191 default:
192 return lexError1 ($state, $text, $i, $lineno);
193 }
194 break;
195 case 'reading predicate 2':
196 switch (TRUE)
197 {
198 case ($char == ']'):
199 $buffer = rtrim ($buffer);
200 if (!validTagName ($buffer))
201 return lexError4 ($buffer, $lineno);
202 $ret[] = array ('type' => 'LEX_PREDICATE', 'load' => $buffer, 'lineno' => $lineno);
203 $newstate = 'ESOTSM';
204 break;
205 case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
206 $buffer .= $char;
207 break;
208 default:
209 return lexError1 ($state, $text, $i, $lineno);
210 }
211 break;
212 case 'skipping comment':
213 switch ($char)
214 {
215 case "\n":
216 $lineno++;
217 $newstate = 'ESOTSM';
218 default: // eat char, nom-nom...
219 break;
220 }
221 break;
222 default:
223 die (__FUNCTION__ . "(): internal error, state == ${state}");
224 endswitch;
225 $state = $newstate;
226 endfor;
227 if ($state != 'ESOTSM' and $state != 'skipping comment')
228 return lexError3 ($state, $lineno);
229 return array ('result' => 'ACK', 'load' => $ret);
230 }
231
232 // Parse the given lexems stream into a list of RackCode sentences. Each such
233 // sentence is a syntax tree, suitable for tag sequence evaluation. The final
234 // parse tree may contain the following nodes:
235 // LEX_TAG
236 // LEX_PREDICATE
237 // LEX_BOOLCONST
238 // SYNT_NOTEXPR (1 argument, holding SYNT_EXPR)
239 // SYNT_BOOLOP (2 arguments, each holding SYNT_EXPR)
240 // SYNT_DEFINITION (2 arguments: term and definition)
241 // SYNT_GRANT (2 arguments: decision and condition)
242 // SYNT_CODETEXT (sequence of sentences)
243 //
244 // After parsing the input successfully a list of SYNT_GRANT and SYNT_DEFINITION
245 // trees is returned.
246 function getSentencesFromLexems ($lexems)
247 {
248 $stack = array(); // subject to array_push() and array_pop()
249 $done = 0; // $lexems[$done] is the next item in the tape
250 $todo = count ($lexems);
251
252 // Perform shift-reduce processing. The "accept" actions occurs with an
253 // empty input tape and the stack holding only one symbol (the start
254 // symbol, SYNT_CODETEXT). When reducing, set the "line number" of
255 // the reduction result to the line number of the "latest" item of the
256 // reduction base (the one on the stack top). This will help locating
257 // parse errors, if any.
258 while (TRUE)
259 {
260 $stacktop = $stacksecondtop = $stackthirdtop = array ('type' => 'null');
261 $stacksize = count ($stack);
262 if ($stacksize >= 1)
263 {
264 $stacktop = array_pop ($stack);
265 // It is possible to run into a S/R conflict, when having a syntaxically
266 // correct sentence base on the stack and some "and {something}" items
267 // on the input tape, hence let's detect this specific case and insist
268 // on "shift" action to make EXPR parsing hungry one.
269 if
270 (
271 $stacktop['type'] == 'SYNT_EXPR' and
272 ($done < $todo) and
273 $lexems[$done]['type'] == 'LEX_BOOLOP'
274 )
275 {
276 // shift!
277 array_push ($stack, $stacktop);
278 array_push ($stack, $lexems[$done++]);
279 continue;
280 }
281 if ($stacksize >= 2)
282 {
283 $stacksecondtop = array_pop ($stack);
284 if ($stacksize >= 3)
285 {
286 $stackthirdtop = array_pop ($stack);
287 array_push ($stack, $stackthirdtop);
288 }
289 array_push ($stack, $stacksecondtop);
290 }
291 array_push ($stack, $stacktop);
292 // First detect definition start to save the predicate from being reduced into
293 // expression.
294 if
295 (
296 $stacktop['type'] == 'LEX_PREDICATE' and
297 $stacksecondtop['type'] == 'LEX_DEFINE'
298 )
299 {
300 // reduce!
301 array_pop ($stack);
302 array_pop ($stack);
303 array_push
304 (
305 $stack,
306 array
307 (
308 'type' => 'SYNT_DEFINE',
309 'lineno' => $stacktop['lineno'],
310 'load' => $stacktop['load']
311 )
312 );
313 continue;
314 }
315 // Try "replace" action only on a non-empty stack.
316 // If a handle is found for reversing a production rule, do it and start a new
317 // cycle instead of advancing further on rule list. This will preserve rule priority
318 // in the grammar and keep us from an extra shift action.
319 if
320 (
321 $stacktop['type'] == 'LEX_BOOLCONST' or
322 $stacktop['type'] == 'LEX_TAG' or
323 $stacktop['type'] == 'LEX_PREDICATE'
324 )
325 {
326 // reduce!
327 array_pop ($stack);
328 array_push
329 (
330 $stack,
331 array
332 (
333 'type' => 'SYNT_EXPR',
334 'lineno' => $stacktop['lineno'],
335 'load' => $stacktop
336 )
337 );
338 continue;
339 }
340 if
341 (
342 $stacktop['type'] == 'SYNT_EXPR' and
343 $stacksecondtop['type'] == 'LEX_NOT'
344 )
345 {
346 // reduce!
347 array_pop ($stack);
348 array_pop ($stack);
349 array_push
350 (
351 $stack,
352 array
353 (
354 'type' => 'SYNT_EXPR',
355 'lineno' => $stacktop['lineno'],
356 'load' => array
357 (
358 'type' => 'SYNT_NOTEXPR',
359 'load' => $stacktop['load']
360 )
361 )
362 );
363 continue;
364 }
365 if
366 (
367 $stacktop['type'] == 'LEX_RBRACE' and
368 $stacksecondtop['type'] == 'SYNT_EXPR' and
369 $stackthirdtop['type'] == 'LEX_LBRACE'
370 )
371 {
372 // reduce!
373 array_pop ($stack);
374 array_pop ($stack);
375 array_pop ($stack);
376 $stacksecondtop['lineno'] = $stacktop['lineno'];
377 array_push
378 (
379 $stack,
380 $stacksecondtop
381 );
382 continue;
383 }
384 if
385 (
386 $stacktop['type'] == 'SYNT_EXPR' and
387 $stacksecondtop['type'] == 'LEX_BOOLOP' and
388 $stackthirdtop['type'] == 'SYNT_EXPR'
389 )
390 {
391 // reduce!
392 array_pop ($stack);
393 array_pop ($stack);
394 array_pop ($stack);
395 array_push
396 (
397 $stack,
398 array
399 (
400 'type' => 'SYNT_EXPR',
401 'lineno' => $stacktop['lineno'],
402 'load' => array
403 (
404 'type' => 'SYNT_BOOLOP',
405 'subtype' => $stacksecondtop['load'],
406 'left' => $stackthirdtop['load'],
407 'right' => $stacktop['load']
408 )
409 )
410 );
411 continue;
412 }
413 if
414 (
415 $stacktop['type'] == 'SYNT_EXPR' and
416 $stacksecondtop['type'] == 'LEX_DECISION'
417 )
418 {
419 // reduce!
420 array_pop ($stack);
421 array_pop ($stack);
422 array_push
423 (
424 $stack,
425 array
426 (
427 'type' => 'SYNT_GRANT',
428 'lineno' => $stacktop['lineno'],
429 'decision' => $stacksecondtop['load'],
430 'condition' => $stacktop['load']
431 )
432 );
433 continue;
434 }
435 if
436 (
437 $stacktop['type'] == 'SYNT_EXPR' and
438 $stacksecondtop['type'] == 'SYNT_DEFINE'
439 )
440 {
441 // reduce!
442 array_pop ($stack);
443 array_pop ($stack);
444 array_push
445 (
446 $stack,
447 array
448 (
449 'type' => 'SYNT_DEFINITION',
450 'lineno' => $stacktop['lineno'],
451 'term' => $stacksecondtop['load'],
452 'definition' => $stacktop['load']
453 )
454 );
455 continue;
456 }
457 if
458 (
459 ($stacktop['type'] == 'SYNT_GRANT' or $stacktop['type'] == 'SYNT_DEFINITION') and
460 $stacksecondtop['type'] == 'SYNT_CODETEXT'
461 )
462 {
463 // reduce!
464 array_pop ($stack);
465 array_pop ($stack);
466 $stacksecondtop['load'][] = $stacktop;
467 $stacksecondtop['lineno'] = $stacktop['lineno'];
468 array_push
469 (
470 $stack,
471 $stacksecondtop
472 );
473 continue;
474 }
475 if
476 (
477 $stacktop['type'] == 'SYNT_GRANT' or
478 $stacktop['type'] == 'SYNT_DEFINITION'
479 )
480 {
481 // reduce!
482 array_pop ($stack);
483 array_push
484 (
485 $stack,
486 array
487 (
488 'type' => 'SYNT_CODETEXT',
489 'lineno' => $stacktop['lineno'],
490 'load' => array ($stacktop)
491 )
492 );
493 continue;
494 }
495 }
496 // The fact we execute here means, that no reduction or early shift
497 // has been done. The only way to enter another iteration is to "shift"
498 // more, if possible. If the tape is empty, we are facing the
499 // "accept"/"reject" dilemma. The only possible way to "accept" is to
500 // have sole starting nonterminal on the stack (SYNT_CODETEXT).
501 if ($done < $todo)
502 {
503 array_push ($stack, $lexems[$done++]);
504 continue;
505 }
506 // The moment of truth.
507 if (count ($stack) == 1 and $stack[0]['type'] == 'SYNT_CODETEXT')
508 return array ('result' => 'ACK', 'load' => $stack[0]['load']);
509 // No luck. Prepare to complain.
510 if ($lineno = locateSyntaxError ($stack))
511 return array ('result' => 'NAK', 'load' => 'Syntax error near line ' . $lineno);
512 // HCF
513 return array ('result' => 'NAK', 'load' => 'Syntax error: empty text');
514 }
515 }
516
517 function eval_expression ($expr, $tagchain, $ptable)
518 {
519 switch ($expr['type'])
520 {
521 case 'LEX_TAG': // Return true, if given tag is present on the tag chain.
522 foreach ($tagchain as $tagInfo)
523 if ($expr['load'] == $tagInfo['tag'])
524 return TRUE;
525 return FALSE;
526 case 'LEX_PREDICATE': // Find given predicate in the symbol table and evaluate it.
527 $pname = $expr['load'];
528 if (!isset ($ptable[$pname]))
529 {
530 showError ("Predicate '${pname}' is referenced before declaration", __FUNCTION__);
531 return;
532 }
533 return eval_expression ($ptable[$pname], $tagchain, $ptable);
534 case 'LEX_BOOLCONST': // Evaluate a boolean constant.
535 switch ($expr['load'])
536 {
537 case 'true':
538 return TRUE;
539 case 'false':
540 return FALSE;
541 default:
542 showError ("Could not parse a boolean constant with value '${expr['load']}'", __FUNCTION__);
543 return; // should failure be harder?
544 }
545 case 'SYNT_NOTEXPR':
546 return !eval_expression ($expr['load'], $tagchain, $ptable);
547 case 'SYNT_BOOLOP':
548 $leftresult = eval_expression ($expr['left'], $tagchain, $ptable);
549 switch ($expr['subtype'])
550 {
551 case 'or':
552 if ($leftresult)
553 return TRUE; // early success
554 return eval_expression ($expr['right'], $tagchain, $ptable);
555 case 'and':
556 if (!$leftresult)
557 return FALSE; // early failure
558 return eval_expression ($expr['right'], $tagchain, $ptable);
559 default:
560 showError ("Cannot evaluate unknown boolean operation '${boolop['subtype']}'");
561 return;
562 }
563 default:
564 showError ("Evaluation error, cannot process expression type '${expr['type']}'", __FUNCTION__);
565 break;
566 }
567 }
568
569 function gotClearanceForTagChain ($tagchain)
570 {
571 global $rackCode;
572 $ptable = array();
573 foreach ($rackCode as $sentence)
574 {
575 switch ($sentence['type'])
576 {
577 case 'SYNT_DEFINITION':
578 $ptable[$sentence['term']] = $sentence['definition'];
579 break;
580 case 'SYNT_GRANT':
581 if (eval_expression ($sentence['condition'], $tagchain, $ptable))
582 switch ($sentence['decision'])
583 {
584 case 'allow':
585 return TRUE;
586 case 'deny':
587 return FALSE;
588 default:
589 showError ("Condition match for unknown grant decision '${sentence['decision']}'", __FUNCTION__);
590 break;
591 }
592 break;
593 default:
594 showError ("Can't process sentence of unknown type '${sentence['type']}'", __FUNCTION__);
595 break;
596 }
597 }
598 return FALSE;
599 }
600
601 function getRackCode ($text)
602 {
603 if (!mb_strlen ($text))
604 return array ('result' => 'NAK', 'load' => 'The RackCode text was found empty in ' . __FUNCTION__);
605 $text = str_replace ("\r", '', $text) . "\n";
606 $lex = getLexemsFromRackCode ($text);
607 if ($lex['result'] != 'ACK')
608 return $lex;
609 $synt = getSentencesFromLexems ($lex['load']);
610 if ($synt['result'] != 'ACK')
611 return $synt;
612 // An empty sentence list is semantically valid, yet senseless,
613 // so checking intermediate result once more won't hurt.
614 if (!count ($synt['load']))
615 return array ('result' => 'NAK', 'load' => 'Empty parse tree found in ' . __FUNCTION__);
616 return semanticFilter ($synt['load']);
617 }
618
619 // Return NULL, if the given expression can be evaluated against the given
620 // predicate list. Return the name of the first show stopper otherwise.
621 function firstUnrefPredicate ($plist, $expr)
622 {
623 switch ($expr['type'])
624 {
625 case 'LEX_BOOLCONST':
626 case 'LEX_TAG':
627 return NULL;
628 case 'LEX_PREDICATE':
629 return in_array ($expr['load'], $plist) ? NULL : $expr['load'];
630 case 'SYNT_NOTEXPR':
631 return firstUnrefPredicate ($plist, $expr['load']);
632 case 'SYNT_BOOLOP':
633 if (($tmp = firstUnrefPredicate ($plist, $expr['left'])) !== NULL)
634 return $tmp;
635 if (($tmp = firstUnrefPredicate ($plist, $expr['right'])) !== NULL)
636 return $tmp;
637 return NULL;
638 default:
639 return NULL;
640 }
641 }
642
643 function semanticFilter ($code)
644 {
645 $predicatelist = array();
646 foreach ($code as $sentence)
647 switch ($sentence['type'])
648 {
649 case 'SYNT_DEFINITION':
650 $up = firstUnrefPredicate ($predicatelist, $sentence['definition']);
651 if ($up !== NULL)
652 return array
653 (
654 'result' => 'NAK',
655 'load' => "definition [${sentence['term']}] uses unknown predicate [${up}]"
656 );
657 $predicatelist[] = $sentence['term'];
658 break;
659 case 'SYNT_GRANT':
660 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
661 if ($up !== NULL)
662 return array
663 (
664 'result' => 'NAK',
665 'load' => "grant sentence uses unknown predicate [${up}]"
666 );
667 break;
668 default:
669 return array ('result' => 'NAK', 'load' => 'unknown sentence type');
670 }
671 return array ('result' => 'ACK', 'load' => $code);
672 }
673
674 // Accept a stack and figure out the cause of it not being parsed into a tree.
675 // Return the line number or zero.
676 function locateSyntaxError ($stack)
677 {
678 // The first SYNT_CODETEXT node, if is present, holds stuff already
679 // successfully processed. Its line counter shows, where the last reduction
680 // took place (it _might_ be the same line, which causes the syntax error).
681 // The next node (it's very likely to exist) should have its line counter
682 // pointing to the place, where the first (of 1 or more) error is located.
683 if (isset ($stack[0]['type']) and $stack[0]['type'] == 'SYNT_CODETEXT')
684 unset ($stack[0]);
685 foreach ($stack as $node)
686 // Satisfy with the first line number met.
687 if (isset ($node['lineno']))
688 return $node['lineno'];
689 return 0;
690 }
691
692 function refRCLineno ($ln)
693 {
694 global $root;
695 return "<a href='${root}?page=perms&tab=default#line${ln}'>line ${ln}</a>";
696 }
697
698 function getRackCodeWarnings ()
699 {
700 $ret = array();
701 global $rackCode;
702 // tags
703 foreach ($rackCode as $sentence)
704 switch ($sentence['type'])
705 {
706 case 'SYNT_DEFINITION':
707 $ret = array_merge ($ret, findTagWarnings ($sentence['definition']));
708 break;
709 case 'SYNT_GRANT':
710 $ret = array_merge ($ret, findTagWarnings ($sentence['condition']));
711 break;
712 default:
713 $ret[] = array
714 (
715 'header' => 'internal error',
716 'class' => 'error',
717 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
718 );
719 }
720 // autotags
721 foreach ($rackCode as $sentence)
722 switch ($sentence['type'])
723 {
724 case 'SYNT_DEFINITION':
725 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['definition']));
726 break;
727 case 'SYNT_GRANT':
728 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['condition']));
729 break;
730 default:
731 $ret[] = array
732 (
733 'header' => 'internal error',
734 'class' => 'error',
735 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
736 );
737 }
738 // predicates
739 $plist = array();
740 foreach ($rackCode as $sentence)
741 if ($sentence['type'] == 'SYNT_DEFINITION')
742 $plist[$sentence['term']] = $sentence['lineno'];
743 foreach ($plist as $pname => $lineno)
744 {
745 foreach ($rackCode as $sentence)
746 switch ($sentence['type'])
747 {
748 case 'SYNT_DEFINITION':
749 if (referencedPredicate ($pname, $sentence['definition']))
750 continue 3; // clear, next term
751 break;
752 case 'SYNT_GRANT':
753 if (referencedPredicate ($pname, $sentence['condition']))
754 continue 3; // idem
755 break;
756 }
757 $ret[] = array
758 (
759 'header' => refRCLineno ($lineno),
760 'class' => 'warning',
761 'text' => "Predicate '${pname}' is defined, but never used."
762 );
763 }
764 // expressions
765 foreach ($rackCode as $sentence)
766 switch (invariantExpression ($sentence))
767 {
768 case 'always true':
769 $ret[] = array
770 (
771 'header' => refRCLineno ($sentence['lineno']),
772 'class' => 'warning',
773 'text' => "Expression is always true."
774 );
775 break;
776 case 'always false':
777 $ret[] = array
778 (
779 'header' => refRCLineno ($sentence['lineno']),
780 'class' => 'warning',
781 'text' => "Expression is always false."
782 );
783 break;
784 default:
785 break;
786 }
787 // Duplicates. Use the same hash function we used to.
788 $fpcache = array ('SYNT_DEFINITION' => array(), 'SYNT_GRANT' => array());
789 foreach ($rackCode as $sentence)
790 switch ($sentence['type'])
791 {
792 case 'SYNT_DEFINITION':
793 $fp = hash (PASSWORD_HASH, serialize (effectiveValue ($sentence['definition'])));
794 if (isset ($fpcache[$sentence['type']][$fp]))
795 $ret[] = array
796 (
797 'header' => refRCLineno ($sentence['lineno']),
798 'class' => 'warning',
799 'text' => 'Effective definition equals that at line ' . $fpcache[$sentence['type']][$fp]
800 );
801 $fpcache[$sentence['type']][$fp] = $sentence['lineno'];
802 break;
803 case 'SYNT_GRANT':
804 $fp = hash (PASSWORD_HASH, serialize (effectiveValue ($sentence['condition'])));
805 if (isset ($fpcache[$sentence['type']][$fp]))
806 $ret[] = array
807 (
808 'header' => refRCLineno ($sentence['lineno']),
809 'class' => 'warning',
810 'text' => 'Effective condition equals that at line ' . $fpcache[$sentence['type']][$fp]
811 );
812 $fpcache[$sentence['type']][$fp] = $sentence['lineno'];
813 break;
814 }
815 // bail out
816 $nwarnings = count ($ret);
817 $ret[] = array
818 (
819 'header' => 'summary',
820 'class' => $nwarnings ? 'error' : 'success',
821 'text' => "Analysis complete, ${nwarnings} issues discovered."
822 );
823 return $ret;
824 }
825
826 // Scan the given expression and return any issues found about its autotags.
827 function findAutoTagWarnings ($expr)
828 {
829 switch ($expr['type'])
830 {
831 case 'LEX_BOOLCONST':
832 case 'LEX_PREDICATE':
833 return array();
834 case 'LEX_TAG':
835 switch (TRUE)
836 {
837 case (mb_ereg_match ('^\$id_', $expr['load'])):
838 $recid = mb_ereg_replace ('^\$id_', '', $expr['load']);
839 if (recordExists ($recid, 'object'))
840 return array();
841 return array (array
842 (
843 'header' => refRCLineno ($expr['lineno']),
844 'class' => 'warning',
845 'text' => "An object with ID '${recid}' does not exist."
846 ));
847 case (mb_ereg_match ('^\$ipv4netid_', $expr['load'])):
848 $recid = mb_ereg_replace ('^\$ipv4netid_', '', $expr['load']);
849 if (recordExists ($recid, 'ipv4net'))
850 return array();
851 return array (array
852 (
853 'header' => refRCLineno ($expr['lineno']),
854 'class' => 'warning',
855 'text' => "IPv4 network with ID '${recid}' does not exist."
856 ));
857 case (mb_ereg_match ('^\$userid_', $expr['load'])):
858 $recid = mb_ereg_replace ('^\$userid_', '', $expr['load']);
859 if (recordExists ($recid, 'user'))
860 return array();
861 return array (array
862 (
863 'header' => refRCLineno ($expr['lineno']),
864 'class' => 'warning',
865 'text' => "User account with ID '${recid}' does not exist."
866 ));
867 case (mb_ereg_match ('^\$username_', $expr['load'])):
868 global $accounts;
869 $recid = mb_ereg_replace ('^\$username_', '', $expr['load']);
870 if (isset ($accounts[$recid]))
871 return array();
872 return array (array
873 (
874 'header' => refRCLineno ($expr['lineno']),
875 'class' => 'warning',
876 'text' => "User account with name '${recid}' does not exist."
877 ));
878 default:
879 return array();
880 }
881 case 'SYNT_NOTEXPR':
882 return findAutoTagWarnings ($expr['load']);
883 case 'SYNT_BOOLOP':
884 return array_merge
885 (
886 findAutoTagWarnings ($expr['left']),
887 findAutoTagWarnings ($expr['right'])
888 );
889 default:
890 return array (array
891 (
892 'header' => 'internal error',
893 'class' => 'error',
894 'text' => "Skipped expression of unknown type '${expr['type']}'"
895 ));
896 }
897 }
898
899 // Idem WRT tags.
900 function findTagWarnings ($expr)
901 {
902 global $taglist;
903 switch ($expr['type'])
904 {
905 case 'LEX_BOOLCONST':
906 case 'LEX_PREDICATE':
907 return array();
908 case 'LEX_TAG':
909 // Only verify stuff, that has passed through the saving handler.
910 if (!mb_ereg_match (TAGNAME_REGEXP, $expr['load']))
911 return array();
912 foreach ($taglist as $taginfo)
913 if ($taginfo['tag'] == $expr['load'])
914 return array();
915 return array (array
916 (
917 'header' => refRCLineno ($expr['lineno']),
918 'class' => 'warning',
919 'text' => "Tag '${expr['load']}' does not exist."
920 ));
921 case 'SYNT_NOTEXPR':
922 return findTagWarnings ($expr['load']);
923 case 'SYNT_BOOLOP':
924 return array_merge
925 (
926 findTagWarnings ($expr['left']),
927 findTagWarnings ($expr['right'])
928 );
929 default:
930 return array (array
931 (
932 'header' => 'internal error',
933 'class' => 'error',
934 'text' => "Skipped expression of unknown type '${expr['type']}'"
935 ));
936 }
937 }
938
939 // Return true, if the expression makes use of the predicate given.
940 function referencedPredicate ($pname, $expr)
941 {
942 switch ($expr['type'])
943 {
944 case 'LEX_BOOLCONST':
945 case 'LEX_TAG':
946 return FALSE;
947 case 'LEX_PREDICATE':
948 return $pname == $expr['load'];
949 case 'SYNT_NOTEXPR':
950 return referencedPredicate ($pname, $expr['load']);
951 case 'SYNT_BOOLOP':
952 return referencedPredicate ($pname, $expr['left']) or referencedPredicate ($pname, $expr['right']);
953 default: // This is actually an internal error.
954 return FALSE;
955 }
956 }
957
958 // Return 'always true', 'always false' or any other verdict.
959 function invariantExpression ($expr)
960 {
961 $self = __FUNCTION__;
962 switch ($expr['type'])
963 {
964 case 'SYNT_GRANT':
965 return $self ($expr['condition']);
966 case 'SYNT_DEFINITION':
967 return $self ($expr['definition']);
968 case 'LEX_BOOLCONST':
969 if ($expr['load'] == 'true')
970 return 'always true';
971 return 'always false';
972 case 'LEX_TAG':
973 case 'LEX_PREDICATE':
974 return 'sometimes something';
975 case 'SYNT_NOTEXPR':
976 return $self ($expr['load']);
977 case 'SYNT_BOOLOP':
978 $leftanswer = $self ($expr['left']);
979 $rightanswer = $self ($expr['right']);
980 // "true or anything" is always true and thus const
981 if ($expr['subtype'] == 'or' and ($leftanswer == 'always true' or $rightanswer == 'always true'))
982 return 'always true';
983 // "false and anything" is always false and thus const
984 if ($expr['subtype'] == 'and' and ($leftanswer == 'always false' or $rightanswer == 'always false'))
985 return 'always false';
986 // "true and true" is true
987 if ($expr['subtype'] == 'and' and ($leftanswer == 'always true' and $rightanswer == 'always true'))
988 return 'always true';
989 // "false or false" is false
990 if ($expr['subtype'] == 'or' and ($leftanswer == 'always false' and $rightanswer == 'always false'))
991 return 'always false';
992 return '';
993 default: // This is actually an internal error.
994 break;
995 }
996 }
997
998 // FIXME: First do line number stripping, otherwise hashes will always differ even
999 // for the obviously equivalent expressions. In some longer term mean transform the
1000 // expression into minimalistic and ordered form.
1001 function effectiveValue ($expr)
1002 {
1003 return $expr;
1004 }
1005
1006 ?>