r2666 - introduced LDAPCache table (ticket:193)
[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 */
7
8 // Complain about martian char.
9 function lexError1 ($state, $text, $pos, $ln = 'N/A')
10 {
11 return array
12 (
13 'result' => 'NAK',
14 'load' => "Invalid character '" . mb_substr ($text, $pos, 1) . "' near line ${ln}"
15 );
16 }
17
18 // Complain about martian keyword.
19 function lexError2 ($word, $ln = 'N/A')
20 {
21 return array
22 (
23 'result' => 'NAK',
24 'load' => "Invalid keyword '${word}' near line ${ln}"
25 );
26 }
27
28 // Complain about wrong FSM state.
29 function lexError3 ($state, $ln = 'N/A')
30 {
31 return array
32 (
33 'result' => 'NAK',
34 'load' => "Lexical error in scanner state '${state}' near line ${ln}"
35 );
36 }
37
38 function lexError4 ($s, $ln = 'N/A')
39 {
40 return array
41 (
42 'result' => 'NAK',
43 'load' => "Invalid name '${s}' near line ${ln}"
44 );
45 }
46
47 /* Produce a list of lexems from the given text. Possible lexems are:
48 *
49 * LEX_LBRACE
50 * LEX_RBRACE
51 * LEX_DECISION
52 * LEX_DEFINE
53 * LEX_BOOLCONST
54 * LEX_NOT
55 * LEX_TAG
56 * LEX_AUTOTAG
57 * LEX_PREDICATE
58 * LEX_BOOLOP
59 * LEX_CONTEXT
60 * LEX_CLEAR
61 * LEX_INSERT
62 * LEX_REMOVE
63 * LEX_ON
64 *
65 */
66 function getLexemsFromRawText ($text)
67 {
68 $ret = array();
69 // Add a mock character to aid in synchronization with otherwise correct,
70 // but short or odd-terminated final lines.
71 $text .= ' ';
72 $textlen = mb_strlen ($text);
73 $lineno = 1;
74 $state = "ESOTSM";
75 for ($i = 0; $i < $textlen; $i++) :
76 $char = mb_substr ($text, $i, 1);
77 $newstate = $state;
78 switch ($state) :
79 case 'ESOTSM':
80 switch (TRUE)
81 {
82 case ($char == '('):
83 $ret[] = array ('type' => 'LEX_LBRACE', 'lineno' => $lineno);
84 break;
85 case ($char == ')'):
86 $ret[] = array ('type' => 'LEX_RBRACE', 'lineno' => $lineno);
87 break;
88 case ($char == '#'):
89 $newstate = 'skipping comment';
90 break;
91 case (mb_ereg ('[[:alpha:]]', $char) > 0):
92 $newstate = 'reading keyword';
93 $buffer = $char;
94 break;
95 case ($char == "\n"):
96 $lineno++; // fall through
97 case ($char == " "):
98 case ($char == "\t"):
99 // nom-nom...
100 break;
101 case ($char == '{'):
102 $newstate = 'reading tag 1';
103 break;
104 case ($char == '['):
105 $newstate = 'reading predicate 1';
106 break;
107 default:
108 return lexError1 ($state, $text, $i, $lineno);
109 }
110 break;
111 case 'reading keyword':
112 switch (TRUE)
113 {
114 case (mb_ereg ('[[:alpha:]]', $char) > 0):
115 $buffer .= $char;
116 break;
117 case ($char == "\n"):
118 $lineno++; // fall through
119 case ($char == " "):
120 case ($char == "\t"):
121 case ($char == ')'): // this will be handled below
122 // got a word, sort it out
123 switch ($buffer)
124 {
125 case 'allow':
126 case 'deny':
127 $ret[] = array ('type' => 'LEX_DECISION', 'load' => $buffer, 'lineno' => $lineno);
128 break;
129 case 'define':
130 $ret[] = array ('type' => 'LEX_DEFINE', 'lineno' => $lineno);
131 break;
132 case 'and':
133 case 'or':
134 $ret[] = array ('type' => 'LEX_BOOLOP', 'load' => $buffer, 'lineno' => $lineno);
135 break;
136 case 'not':
137 $ret[] = array ('type' => 'LEX_NOT', 'lineno' => $lineno);
138 break;
139 case 'false':
140 case 'true':
141 $ret[] = array ('type' => 'LEX_BOOLCONST', 'load' => $buffer, 'lineno' => $lineno);
142 break;
143 case 'context':
144 $ret[] = array ('type' => 'LEX_CONTEXT', 'lineno' => $lineno);
145 break;
146 case 'clear':
147 $ret[] = array ('type' => 'LEX_CLEAR', 'lineno' => $lineno);
148 break;
149 case 'insert':
150 $ret[] = array ('type' => 'LEX_INSERT', 'lineno' => $lineno);
151 break;
152 case 'remove':
153 $ret[] = array ('type' => 'LEX_REMOVE', 'lineno' => $lineno);
154 break;
155 case 'on':
156 $ret[] = array ('type' => 'LEX_ON', 'lineno' => $lineno);
157 break;
158 default:
159 return lexError2 ($buffer, $lineno);
160 }
161 if ($char == ')')
162 $ret[] = array ('type' => 'LEX_RBRACE', 'lineno' => $lineno);
163 $newstate = 'ESOTSM';
164 break;
165 default:
166 return lexError1 ($state, $text, $i, $lineno);
167 }
168 break;
169 case 'reading tag 1':
170 switch (TRUE)
171 {
172 case ($char == "\n"):
173 $lineno++; // fall through
174 case ($char == " "):
175 case ($char == "\t"):
176 // nom-nom...
177 break;
178 case (mb_ereg ('[[:alnum:]\$]', $char) > 0):
179 $buffer = $char;
180 $newstate = 'reading tag 2';
181 break;
182 default:
183 return lexError1 ($state, $text, $i, $lineno);
184 }
185 break;
186 case 'reading tag 2':
187 switch (TRUE)
188 {
189 case ($char == '}'):
190 $buffer = rtrim ($buffer);
191 if (!validTagName ($buffer, TRUE))
192 return lexError4 ($buffer, $lineno);
193 $ret[] = array ('type' => ($buffer[0] == '$' ? 'LEX_AUTOTAG' : 'LEX_TAG'), 'load' => $buffer, 'lineno' => $lineno);
194 $newstate = 'ESOTSM';
195 break;
196 case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
197 $buffer .= $char;
198 break;
199 default:
200 return lexError1 ($state, $text, $i, $lineno);
201 }
202 break;
203 case 'reading predicate 1':
204 switch (TRUE)
205 {
206 case (preg_match ('/^[ \t\n]$/', $char)):
207 // nom-nom...
208 break;
209 case (mb_ereg ('[[:alnum:]]', $char) > 0):
210 $buffer = $char;
211 $newstate = 'reading predicate 2';
212 break;
213 default:
214 return lexError1 ($state, $text, $i, $lineno);
215 }
216 break;
217 case 'reading predicate 2':
218 switch (TRUE)
219 {
220 case ($char == ']'):
221 $buffer = rtrim ($buffer);
222 if (!validTagName ($buffer))
223 return lexError4 ($buffer, $lineno);
224 $ret[] = array ('type' => 'LEX_PREDICATE', 'load' => $buffer, 'lineno' => $lineno);
225 $newstate = 'ESOTSM';
226 break;
227 case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
228 $buffer .= $char;
229 break;
230 default:
231 return lexError1 ($state, $text, $i, $lineno);
232 }
233 break;
234 case 'skipping comment':
235 switch ($char)
236 {
237 case "\n":
238 $lineno++;
239 $newstate = 'ESOTSM';
240 default: // eat char, nom-nom...
241 break;
242 }
243 break;
244 default:
245 die (__FUNCTION__ . "(): internal error, state == ${state}");
246 endswitch;
247 $state = $newstate;
248 endfor;
249 if ($state != 'ESOTSM' and $state != 'skipping comment')
250 return lexError3 ($state, $lineno);
251 return array ('result' => 'ACK', 'load' => $ret);
252 }
253
254 // Take a parse tree and figure out if it is a valid payload or not.
255 // Depending on that return either NULL or an array filled with the load
256 // of that expression.
257 function spotPayload ($text, $reqtype = 'SYNT_CODETEXT')
258 {
259 $lex = getLexemsFromRawText ($text);
260 if ($lex['result'] != 'ACK')
261 return $lex;
262 $stack = getParseTreeFromLexems ($lex['load']);
263 // The only possible way to "accept" is to have sole starting
264 // nonterminal on the stack (and it must be of the requested class).
265 if (count ($stack) == 1 and $stack[0]['type'] == $reqtype)
266 return array ('result' => 'ACK', 'load' => $stack[0]['load']);
267 // No luck. Prepare to complain.
268 if ($lineno = locateSyntaxError ($stack))
269 return array ('result' => 'NAK', 'load' => "Syntax error for type '${reqtype}' near line ${lineno}");
270 // HCF!
271 return array ('result' => 'NAK', 'load' => "Syntax error for type '${reqtype}', line number unknown");
272 }
273
274 // Parse the given lexems stream into a list of RackCode sentences. Each such
275 // sentence is a syntax tree, suitable for tag sequence evaluation. The final
276 // parse tree may contain the following nodes:
277 // LEX_TAG
278 // LEX_AUTOTAG
279 // LEX_PREDICATE
280 // LEX_BOOLCONST
281 // SYNT_NOTEXPR (1 argument, holding SYNT_EXPR)
282 // SYNT_BOOLOP (2 arguments, each holding SYNT_EXPR)
283 // SYNT_DEFINITION (2 arguments: term and definition)
284 // SYNT_GRANT (2 arguments: decision and condition)
285 // SYNT_ADJUSTMENT (context modifier with action(s) and condition)
286 // SYNT_CODETEXT (sequence of sentences)
287 //
288 // After parsing the input successfully a list of SYNT_GRANT and SYNT_DEFINITION
289 // trees is returned.
290 //
291 // P.S. The above is true for input, which is a complete and correct RackCode text.
292 // Other inputs may produce different combinations of lex/synt structures. Calling
293 // function must check the parse tree itself.
294 function getParseTreeFromLexems ($lexems)
295 {
296 $stack = array(); // subject to array_push() and array_pop()
297 $done = 0; // $lexems[$done] is the next item in the tape
298 $todo = count ($lexems);
299
300 // Perform shift-reduce processing. The "accept" actions occurs with an
301 // empty input tape and the stack holding only one symbol (the start
302 // symbol, SYNT_CODETEXT). When reducing, set the "line number" of
303 // the reduction result to the line number of the "latest" item of the
304 // reduction base (the one on the stack top). This will help locating
305 // parse errors, if any.
306 while (TRUE)
307 {
308 $stacktop = $stacksecondtop = $stackthirdtop = $stackfourthtop = array ('type' => 'null');
309 $stacksize = count ($stack);
310 if ($stacksize >= 1)
311 {
312 $stacktop = array_pop ($stack);
313 // It is possible to run into a S/R conflict, when having a syntaxically
314 // correct sentence base on the stack and some "and {something}" items
315 // on the input tape, hence let's detect this specific case and insist
316 // on "shift" action to make EXPR parsing hungry one.
317 if
318 (
319 $stacktop['type'] == 'SYNT_EXPR' and
320 ($done < $todo) and
321 $lexems[$done]['type'] == 'LEX_BOOLOP'
322 )
323 {
324 // shift!
325 array_push ($stack, $stacktop);
326 array_push ($stack, $lexems[$done++]);
327 continue;
328 }
329 if ($stacksize >= 2)
330 {
331 $stacksecondtop = array_pop ($stack);
332 if ($stacksize >= 3)
333 {
334 $stackthirdtop = array_pop ($stack);
335 if ($stacksize >= 4)
336 {
337 $stackfourthtop = array_pop ($stack);
338 array_push ($stack, $stackfourthtop);
339 }
340 array_push ($stack, $stackthirdtop);
341 }
342 array_push ($stack, $stacksecondtop);
343 }
344 array_push ($stack, $stacktop);
345 // First detect definition start to save the predicate from being reduced into
346 // expression.
347 if
348 (
349 $stacktop['type'] == 'LEX_PREDICATE' and
350 $stacksecondtop['type'] == 'LEX_DEFINE'
351 )
352 {
353 // reduce!
354 array_pop ($stack);
355 array_pop ($stack);
356 array_push
357 (
358 $stack,
359 array
360 (
361 'type' => 'SYNT_DEFINE',
362 'lineno' => $stacktop['lineno'],
363 'load' => $stacktop['load']
364 )
365 );
366 continue;
367 }
368 if
369 (
370 $stacktop['type'] == 'LEX_CLEAR'
371 )
372 {
373 // reduce!
374 array_pop ($stack);
375 array_push
376 (
377 $stack,
378 array
379 (
380 'type' => 'SYNT_CTXMOD',
381 'lineno' => $stacktop['lineno'],
382 'load' => array ('op' => 'clear')
383 )
384 );
385 continue;
386 }
387 if
388 (
389 $stacktop['type'] == 'LEX_TAG' and
390 $stacksecondtop['type'] == 'LEX_INSERT'
391 )
392 {
393 // reduce!
394 array_pop ($stack);
395 array_pop ($stack);
396 array_push
397 (
398 $stack,
399 array
400 (
401 'type' => 'SYNT_CTXMOD',
402 'lineno' => $stacktop['lineno'],
403 'load' => array ('op' => 'insert', 'tag' => $stacktop['load'], 'lineno' => $stacktop['lineno'])
404 )
405 );
406 continue;
407 }
408 if
409 (
410 $stacktop['type'] == 'LEX_TAG' and
411 $stacksecondtop['type'] == 'LEX_REMOVE'
412 )
413 {
414 // reduce!
415 array_pop ($stack);
416 array_pop ($stack);
417 array_push
418 (
419 $stack,
420 array
421 (
422 'type' => 'SYNT_CTXMOD',
423 'lineno' => $stacktop['lineno'],
424 'load' => array ('op' => 'remove', 'tag' => $stacktop['load'], 'lineno' => $stacktop['lineno'])
425 )
426 );
427 continue;
428 }
429 if
430 (
431 $stacktop['type'] == 'SYNT_CTXMOD' and
432 $stacksecondtop['type'] == 'SYNT_CTXMODLIST'
433 )
434 {
435 // reduce!
436 array_pop ($stack);
437 array_pop ($stack);
438 array_push
439 (
440 $stack,
441 array
442 (
443 'type' => 'SYNT_CTXMODLIST',
444 'lineno' => $stacktop['lineno'],
445 'load' => array_merge ($stacksecondtop['load'], array ($stacktop['load']))
446 )
447 );
448 continue;
449 }
450 if
451 (
452 $stacktop['type'] == 'SYNT_CTXMOD'
453 )
454 {
455 // reduce!
456 array_pop ($stack);
457 array_push
458 (
459 $stack,
460 array
461 (
462 'type' => 'SYNT_CTXMODLIST',
463 'lineno' => $stacktop['lineno'],
464 'load' => array ($stacktop['load'])
465 )
466 );
467 continue;
468 }
469 // Try "replace" action only on a non-empty stack.
470 // If a handle is found for reversing a production rule, do it and start a new
471 // cycle instead of advancing further on rule list. This will preserve rule priority
472 // in the grammar and keep us from an extra shift action.
473 if
474 (
475 $stacktop['type'] == 'LEX_BOOLCONST' or
476 $stacktop['type'] == 'LEX_TAG' or
477 $stacktop['type'] == 'LEX_AUTOTAG' or
478 $stacktop['type'] == 'LEX_PREDICATE'
479 )
480 {
481 // reduce!
482 array_pop ($stack);
483 array_push
484 (
485 $stack,
486 array
487 (
488 'type' => 'SYNT_EXPR',
489 'lineno' => $stacktop['lineno'],
490 'load' => $stacktop
491 )
492 );
493 continue;
494 }
495 if
496 (
497 $stacktop['type'] == 'SYNT_EXPR' and
498 $stacksecondtop['type'] == 'LEX_NOT'
499 )
500 {
501 // reduce!
502 array_pop ($stack);
503 array_pop ($stack);
504 array_push
505 (
506 $stack,
507 array
508 (
509 'type' => 'SYNT_EXPR',
510 'lineno' => $stacktop['lineno'],
511 'load' => array
512 (
513 'type' => 'SYNT_NOTEXPR',
514 'load' => $stacktop['load']
515 )
516 )
517 );
518 continue;
519 }
520 if
521 (
522 $stacktop['type'] == 'LEX_RBRACE' and
523 $stacksecondtop['type'] == 'SYNT_EXPR' and
524 $stackthirdtop['type'] == 'LEX_LBRACE'
525 )
526 {
527 // reduce!
528 array_pop ($stack);
529 array_pop ($stack);
530 array_pop ($stack);
531 $stacksecondtop['lineno'] = $stacktop['lineno'];
532 array_push
533 (
534 $stack,
535 $stacksecondtop
536 );
537 continue;
538 }
539 if
540 (
541 $stacktop['type'] == 'SYNT_EXPR' and
542 $stacksecondtop['type'] == 'LEX_BOOLOP' and
543 $stackthirdtop['type'] == 'SYNT_EXPR'
544 )
545 {
546 // reduce!
547 array_pop ($stack);
548 array_pop ($stack);
549 array_pop ($stack);
550 array_push
551 (
552 $stack,
553 array
554 (
555 'type' => 'SYNT_EXPR',
556 'lineno' => $stacktop['lineno'],
557 'load' => array
558 (
559 'type' => 'SYNT_BOOLOP',
560 'subtype' => $stacksecondtop['load'],
561 'left' => $stackthirdtop['load'],
562 'right' => $stacktop['load']
563 )
564 )
565 );
566 continue;
567 }
568 if
569 (
570 $stacktop['type'] == 'SYNT_EXPR' and
571 $stacksecondtop['type'] == 'LEX_DECISION'
572 )
573 {
574 // reduce!
575 array_pop ($stack);
576 array_pop ($stack);
577 array_push
578 (
579 $stack,
580 array
581 (
582 'type' => 'SYNT_GRANT',
583 'lineno' => $stacktop['lineno'],
584 'decision' => $stacksecondtop['load'],
585 'condition' => $stacktop['load']
586 )
587 );
588 continue;
589 }
590 if
591 (
592 $stacktop['type'] == 'SYNT_EXPR' and
593 $stacksecondtop['type'] == 'SYNT_DEFINE'
594 )
595 {
596 // reduce!
597 array_pop ($stack);
598 array_pop ($stack);
599 array_push
600 (
601 $stack,
602 array
603 (
604 'type' => 'SYNT_DEFINITION',
605 'lineno' => $stacktop['lineno'],
606 'term' => $stacksecondtop['load'],
607 'definition' => $stacktop['load']
608 )
609 );
610 continue;
611 }
612 if
613 (
614 $stacktop['type'] == 'SYNT_EXPR' and
615 $stacksecondtop['type'] == 'LEX_ON' and
616 $stackthirdtop['type'] == 'SYNT_CTXMODLIST' and
617 $stackfourthtop['type'] == 'LEX_CONTEXT'
618 )
619 {
620 // reduce!
621 array_pop ($stack);
622 array_pop ($stack);
623 array_pop ($stack);
624 array_pop ($stack);
625 array_push
626 (
627 $stack,
628 array
629 (
630 'type' => 'SYNT_ADJUSTMENT',
631 'lineno' => $stacktop['lineno'],
632 'modlist' => $stackthirdtop['load'],
633 'condition' => $stacktop['load']
634 )
635 );
636 continue;
637 }
638 if
639 (
640 ($stacktop['type'] == 'SYNT_GRANT' or $stacktop['type'] == 'SYNT_DEFINITION' or $stacktop['type'] == 'SYNT_ADJUSTMENT') and
641 $stacksecondtop['type'] == 'SYNT_CODETEXT'
642 )
643 {
644 // reduce!
645 array_pop ($stack);
646 array_pop ($stack);
647 $stacksecondtop['load'][] = $stacktop;
648 $stacksecondtop['lineno'] = $stacktop['lineno'];
649 array_push
650 (
651 $stack,
652 $stacksecondtop
653 );
654 continue;
655 }
656 if
657 (
658 $stacktop['type'] == 'SYNT_GRANT' or
659 $stacktop['type'] == 'SYNT_DEFINITION' or
660 $stacktop['type'] == 'SYNT_ADJUSTMENT'
661 )
662 {
663 // reduce!
664 array_pop ($stack);
665 array_push
666 (
667 $stack,
668 array
669 (
670 'type' => 'SYNT_CODETEXT',
671 'lineno' => $stacktop['lineno'],
672 'load' => array ($stacktop)
673 )
674 );
675 continue;
676 }
677 }
678 // The fact we execute here means, that no reduction or early shift
679 // has been done. The only way to enter another iteration is to "shift"
680 // more, if possible. If shifting isn't possible due to empty input tape,
681 // we are facing the final "accept"/"reject" dilemma. In this case our
682 // work is done here, so return the whole stack to the calling function
683 // to decide depending on what it is expecting.
684 if ($done < $todo)
685 {
686 array_push ($stack, $lexems[$done++]);
687 continue;
688 }
689 // The moment of truth.
690 return $stack;
691 }
692 }
693
694 function eval_expression ($expr, $tagchain, $ptable, $silent = FALSE)
695 {
696 switch ($expr['type'])
697 {
698 // Return true, if given tag is present on the tag chain.
699 case 'LEX_TAG':
700 case 'LEX_AUTOTAG':
701 foreach ($tagchain as $tagInfo)
702 if ($expr['load'] == $tagInfo['tag'])
703 return TRUE;
704 return FALSE;
705 case 'LEX_PREDICATE': // Find given predicate in the symbol table and evaluate it.
706 $pname = $expr['load'];
707 if (!isset ($ptable[$pname]))
708 {
709 if (!$silent)
710 showError ("Predicate '${pname}' is referenced before declaration", __FUNCTION__);
711 return NULL;
712 }
713 return eval_expression ($ptable[$pname], $tagchain, $ptable);
714 case 'LEX_BOOLCONST': // Evaluate a boolean constant.
715 switch ($expr['load'])
716 {
717 case 'true':
718 return TRUE;
719 case 'false':
720 return FALSE;
721 default:
722 if (!$silent)
723 showError ("Could not parse a boolean constant with value '${expr['load']}'", __FUNCTION__);
724 return NULL; // should failure be harder?
725 }
726 case 'SYNT_NOTEXPR':
727 $tmp = eval_expression ($expr['load'], $tagchain, $ptable);
728 if ($tmp === TRUE)
729 return FALSE;
730 elseif ($tmp === FALSE)
731 return TRUE;
732 else
733 return $tmp;
734 case 'SYNT_BOOLOP':
735 $leftresult = eval_expression ($expr['left'], $tagchain, $ptable);
736 switch ($expr['subtype'])
737 {
738 case 'or':
739 if ($leftresult)
740 return TRUE; // early success
741 return eval_expression ($expr['right'], $tagchain, $ptable);
742 case 'and':
743 if (!$leftresult)
744 return FALSE; // early failure
745 return eval_expression ($expr['right'], $tagchain, $ptable);
746 default:
747 if (!$silent)
748 showError ("Cannot evaluate unknown boolean operation '${boolop['subtype']}'");
749 return NULL;
750 }
751 default:
752 if (!$silent)
753 showError ("Evaluation error, cannot process expression type '${expr['type']}'", __FUNCTION__);
754 return NULL;
755 break;
756 }
757 }
758
759 // Process a context adjustment request, update given chain accordingly,
760 // return TRUE on any changes done.
761 // The request is a sequence of clear/insert/remove requests exactly as cooked
762 // for each SYNT_CTXMODLIST node.
763 function processAdjustmentSentence ($modlist, &$chain)
764 {
765 global $rackCode;
766 $didChanges = FALSE;
767 foreach ($modlist as $mod)
768 switch ($mod['op'])
769 {
770 case 'insert':
771 foreach ($chain as $etag)
772 if ($etag['tag'] == $mod['tag']) // already there, next request
773 break 2;
774 $search = getTagByName ($mod['tag']);
775 if ($search === NULL) // skip martians silently
776 break;
777 $chain[] = $search;
778 $didChanges = TRUE;
779 break;
780 case 'remove':
781 foreach ($chain as $key => $etag)
782 if ($etag['tag'] == $mod['tag']) // drop first match and return
783 {
784 unset ($chain[$key]);
785 $didChanges = TRUE;
786 break 2;
787 }
788 break;
789 case 'clear':
790 $chain = array();
791 $didChanges = TRUE;
792 break;
793 default: // HCF
794 showError ('Internal error', __FUNCTION__);
795 die;
796 }
797 return $didChanges;
798 }
799
800 // The argument doesn't include explicit and implicit tags. This allows us to derive implicit chain
801 // each time we modify the given argument (and work with the modified copy from now on).
802 // After the work is done the global $impl_tags is silently modified
803 function gotClearanceForTagChain ($const_base)
804 {
805 global $rackCode, $expl_tags, $impl_tags;
806 $ptable = array();
807 foreach ($rackCode as $sentence)
808 {
809 switch ($sentence['type'])
810 {
811 case 'SYNT_DEFINITION':
812 $ptable[$sentence['term']] = $sentence['definition'];
813 break;
814 case 'SYNT_GRANT':
815 if (eval_expression ($sentence['condition'], array_merge ($const_base, $expl_tags, $impl_tags), $ptable))
816 switch ($sentence['decision'])
817 {
818 case 'allow':
819 return TRUE;
820 case 'deny':
821 return FALSE;
822 default:
823 showError ("Condition match for unknown grant decision '${sentence['decision']}'", __FUNCTION__);
824 break;
825 }
826 break;
827 case 'SYNT_ADJUSTMENT':
828 if
829 (
830 eval_expression ($sentence['condition'], array_merge ($const_base, $expl_tags, $impl_tags), $ptable) and
831 processAdjustmentSentence ($sentence['modlist'], $expl_tags)
832 ) // recalculate implicit chain only after actual change, not just on matched condition
833 $impl_tags = getImplicitTags ($expl_tags); // recalculate
834 break;
835 default:
836 showError ("Can't process sentence of unknown type '${sentence['type']}'", __FUNCTION__);
837 break;
838 }
839 }
840 return FALSE;
841 }
842
843 // Top-level wrapper for most of the code in this file. Get a text, return a parse tree
844 // (or error message).
845 function getRackCode ($text)
846 {
847 if (!mb_strlen ($text))
848 return array ('result' => 'NAK', 'load' => 'The RackCode text was found empty in ' . __FUNCTION__);
849 $text = str_replace ("\r", '', $text) . "\n";
850 $synt = spotPayload ($text, 'SYNT_CODETEXT');
851 if ($synt['result'] != 'ACK')
852 return $synt;
853 // An empty sentence list is semantically valid, yet senseless,
854 // so checking intermediate result once more won't hurt.
855 if (!count ($synt['load']))
856 return array ('result' => 'NAK', 'load' => 'Empty parse tree found in ' . __FUNCTION__);
857 return semanticFilter ($synt['load']);
858 }
859
860 // Return NULL, if the given expression can be evaluated against the given
861 // predicate list. Return the name of the first show stopper otherwise.
862 function firstUnrefPredicate ($plist, $expr)
863 {
864 switch ($expr['type'])
865 {
866 case 'LEX_BOOLCONST':
867 case 'LEX_TAG':
868 case 'LEX_AUTOTAG':
869 return NULL;
870 case 'LEX_PREDICATE':
871 return in_array ($expr['load'], $plist) ? NULL : $expr['load'];
872 case 'SYNT_NOTEXPR':
873 return firstUnrefPredicate ($plist, $expr['load']);
874 case 'SYNT_BOOLOP':
875 if (($tmp = firstUnrefPredicate ($plist, $expr['left'])) !== NULL)
876 return $tmp;
877 if (($tmp = firstUnrefPredicate ($plist, $expr['right'])) !== NULL)
878 return $tmp;
879 return NULL;
880 default:
881 return NULL;
882 }
883 }
884
885 function semanticFilter ($code)
886 {
887 $predicatelist = array();
888 foreach ($code as $sentence)
889 switch ($sentence['type'])
890 {
891 case 'SYNT_DEFINITION':
892 $up = firstUnrefPredicate ($predicatelist, $sentence['definition']);
893 if ($up !== NULL)
894 return array
895 (
896 'result' => 'NAK',
897 'load' => "definition [${sentence['term']}] uses unknown predicate [${up}]"
898 );
899 $predicatelist[] = $sentence['term'];
900 break;
901 case 'SYNT_GRANT':
902 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
903 if ($up !== NULL)
904 return array
905 (
906 'result' => 'NAK',
907 'load' => "grant sentence uses unknown predicate [${up}]"
908 );
909 break;
910 case 'SYNT_ADJUSTMENT':
911 // Only condition part gets tested, because it's normal to set (or even to unset)
912 // something, that's not set.
913 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
914 if ($up !== NULL)
915 return array
916 (
917 'result' => 'NAK',
918 'load' => "adjustment sentence uses unknown predicate [${up}]"
919 );
920 break;
921 default:
922 return array ('result' => 'NAK', 'load' => 'unknown sentence type');
923 }
924 return array ('result' => 'ACK', 'load' => $code);
925 }
926
927 // Accept a stack and figure out the cause of it not being parsed into a tree.
928 // Return the line number or zero.
929 function locateSyntaxError ($stack)
930 {
931 // The first SYNT_CODETEXT node, if is present, holds stuff already
932 // successfully processed. Its line counter shows, where the last reduction
933 // took place (it _might_ be the same line, which causes the syntax error).
934 // The next node (it's very likely to exist) should have its line counter
935 // pointing to the place, where the first (of 1 or more) error is located.
936 if (isset ($stack[0]['type']) and $stack[0]['type'] == 'SYNT_CODETEXT')
937 unset ($stack[0]);
938 foreach ($stack as $node)
939 // Satisfy with the first line number met.
940 if (isset ($node['lineno']))
941 return $node['lineno'];
942 return 0;
943 }
944
945 function refRCLineno ($ln)
946 {
947 global $root;
948 return "<a href='${root}?page=perms&tab=default#line${ln}'>line ${ln}</a>";
949 }
950
951 function getRackCodeWarnings ()
952 {
953 $ret = array();
954 global $rackCode;
955 // tags
956 foreach ($rackCode as $sentence)
957 switch ($sentence['type'])
958 {
959 case 'SYNT_DEFINITION':
960 $ret = array_merge ($ret, findTagWarnings ($sentence['definition']));
961 break;
962 case 'SYNT_ADJUSTMENT':
963 $ret = array_merge ($ret, findTagWarnings ($sentence['condition']));
964 $ret = array_merge ($ret, findCtxModWarnings ($sentence['modlist']));
965 break;
966 case 'SYNT_GRANT':
967 $ret = array_merge ($ret, findTagWarnings ($sentence['condition']));
968 break;
969 default:
970 $ret[] = array
971 (
972 'header' => 'internal error',
973 'class' => 'error',
974 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
975 );
976 }
977 // autotags
978 foreach ($rackCode as $sentence)
979 switch ($sentence['type'])
980 {
981 case 'SYNT_DEFINITION':
982 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['definition']));
983 break;
984 case 'SYNT_GRANT':
985 case 'SYNT_ADJUSTMENT':
986 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['condition']));
987 break;
988 default:
989 $ret[] = array
990 (
991 'header' => 'internal error',
992 'class' => 'error',
993 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
994 );
995 }
996 // predicates
997 $plist = array();
998 foreach ($rackCode as $sentence)
999 if ($sentence['type'] == 'SYNT_DEFINITION')
1000 $plist[$sentence['term']] = $sentence['lineno'];
1001 foreach ($plist as $pname => $lineno)
1002 {
1003 foreach ($rackCode as $sentence)
1004 switch ($sentence['type'])
1005 {
1006 case 'SYNT_DEFINITION':
1007 if (referencedPredicate ($pname, $sentence['definition']))
1008 continue 3; // clear, next term
1009 break;
1010 case 'SYNT_GRANT':
1011 case 'SYNT_ADJUSTMENT':
1012 if (referencedPredicate ($pname, $sentence['condition']))
1013 continue 3; // idem
1014 break;
1015 }
1016 $ret[] = array
1017 (
1018 'header' => refRCLineno ($lineno),
1019 'class' => 'warning',
1020 'text' => "Predicate '${pname}' is defined, but never used."
1021 );
1022 }
1023 // expressions
1024 foreach ($rackCode as $sentence)
1025 switch (invariantExpression ($sentence))
1026 {
1027 case 'always true':
1028 $ret[] = array
1029 (
1030 'header' => refRCLineno ($sentence['lineno']),
1031 'class' => 'warning',
1032 'text' => "Expression is always true."
1033 );
1034 break;
1035 case 'always false':
1036 $ret[] = array
1037 (
1038 'header' => refRCLineno ($sentence['lineno']),
1039 'class' => 'warning',
1040 'text' => "Expression is always false."
1041 );
1042 break;
1043 default:
1044 break;
1045 }
1046 // bail out
1047 $nwarnings = count ($ret);
1048 $ret[] = array
1049 (
1050 'header' => 'summary',
1051 'class' => $nwarnings ? 'error' : 'success',
1052 'text' => "Analysis complete, ${nwarnings} issues discovered."
1053 );
1054 return $ret;
1055 }
1056
1057 // Scan the given expression and return any issues found about its autotags.
1058 function findAutoTagWarnings ($expr)
1059 {
1060 switch ($expr['type'])
1061 {
1062 case 'LEX_BOOLCONST':
1063 case 'LEX_PREDICATE':
1064 case 'LEX_TAG':
1065 return array();
1066 case 'LEX_AUTOTAG':
1067 switch (TRUE)
1068 {
1069 case (mb_ereg_match ('^\$id_', $expr['load'])):
1070 $recid = mb_ereg_replace ('^\$id_', '', $expr['load']);
1071 if (recordExists ($recid, 'object'))
1072 return array();
1073 return array (array
1074 (
1075 'header' => refRCLineno ($expr['lineno']),
1076 'class' => 'warning',
1077 'text' => "An object with ID '${recid}' does not exist."
1078 ));
1079 case (mb_ereg_match ('^\$ipv4netid_', $expr['load'])):
1080 $recid = mb_ereg_replace ('^\$ipv4netid_', '', $expr['load']);
1081 if (recordExists ($recid, 'ipv4net'))
1082 return array();
1083 return array (array
1084 (
1085 'header' => refRCLineno ($expr['lineno']),
1086 'class' => 'warning',
1087 'text' => "IPv4 network with ID '${recid}' does not exist."
1088 ));
1089 case (mb_ereg_match ('^\$userid_', $expr['load'])):
1090 $recid = mb_ereg_replace ('^\$userid_', '', $expr['load']);
1091 if (recordExists ($recid, 'user'))
1092 return array();
1093 return array (array
1094 (
1095 'header' => refRCLineno ($expr['lineno']),
1096 'class' => 'warning',
1097 'text' => "User account with ID '${recid}' does not exist."
1098 ));
1099 case (mb_ereg_match ('^\$username_', $expr['load'])):
1100 global $accounts;
1101 $recid = mb_ereg_replace ('^\$username_', '', $expr['load']);
1102 if (isset ($accounts[$recid]))
1103 return array();
1104 return array (array
1105 (
1106 'header' => refRCLineno ($expr['lineno']),
1107 'class' => 'warning',
1108 'text' => "User account with name '${recid}' does not exist."
1109 ));
1110 case (mb_ereg_match ('^\$page_[[:alpha:]]+$', $expr['load'])):
1111 case (mb_ereg_match ('^\$tab_[[:alpha:]]+$', $expr['load'])):
1112 case (mb_ereg_match ('^\$op_[[:alpha:]]+$', $expr['load'])):
1113 case (mb_ereg_match ('^\$any_op$', $expr['load'])):
1114 case (mb_ereg_match ('^\$any_rack$', $expr['load'])):
1115 case (mb_ereg_match ('^\$any_object$', $expr['load'])):
1116 case (mb_ereg_match ('^\$any_ip4net$', $expr['load'])):
1117 case (mb_ereg_match ('^\$any_net$', $expr['load'])):
1118 case (mb_ereg_match ('^\$any_ipv4vs$', $expr['load'])):
1119 case (mb_ereg_match ('^\$any_vs$', $expr['load'])):
1120 case (mb_ereg_match ('^\$any_ipv4rsp$', $expr['load'])):
1121 case (mb_ereg_match ('^\$any_rsp$', $expr['load'])):
1122 case (mb_ereg_match ('^\$any_file$', $expr['load'])):
1123 case (mb_ereg_match ('^\$typeid_[[:digit:]]+$', $expr['load'])): // FIXME: check value validity
1124 case (mb_ereg_match ('^\$cn_.+$', $expr['load'])): // FIXME: check name validity and asset existence
1125 case (mb_ereg_match ('^\$lgcn_.+$', $expr['load'])): // FIXME: check name validity
1126 return array();
1127 default:
1128 return array (array
1129 (
1130 'header' => refRCLineno ($expr['lineno']),
1131 'class' => 'warning',
1132 'text' => "Martian autotag '${expr['load']}'"
1133 ));
1134 }
1135 case 'SYNT_NOTEXPR':
1136 return findAutoTagWarnings ($expr['load']);
1137 case 'SYNT_BOOLOP':
1138 return array_merge
1139 (
1140 findAutoTagWarnings ($expr['left']),
1141 findAutoTagWarnings ($expr['right'])
1142 );
1143 default:
1144 return array (array
1145 (
1146 'header' => 'internal error',
1147 'class' => 'error',
1148 'text' => "Skipped expression of unknown type '${expr['type']}'"
1149 ));
1150 }
1151 }
1152
1153 // Idem WRT tags.
1154 function findTagWarnings ($expr)
1155 {
1156 switch ($expr['type'])
1157 {
1158 case 'LEX_BOOLCONST':
1159 case 'LEX_PREDICATE':
1160 case 'LEX_AUTOTAG':
1161 return array();
1162 case 'LEX_TAG':
1163 if (getTagByName ($expr['load']) !== NULL)
1164 return array();
1165 return array (array
1166 (
1167 'header' => refRCLineno ($expr['lineno']),
1168 'class' => 'warning',
1169 'text' => "Tag '${expr['load']}' does not exist."
1170 ));
1171 case 'SYNT_NOTEXPR':
1172 return findTagWarnings ($expr['load']);
1173 case 'SYNT_BOOLOP':
1174 return array_merge
1175 (
1176 findTagWarnings ($expr['left']),
1177 findTagWarnings ($expr['right'])
1178 );
1179 default:
1180 return array (array
1181 (
1182 'header' => 'internal error',
1183 'class' => 'error',
1184 'text' => "Skipped expression of unknown type '${expr['type']}'"
1185 ));
1186 }
1187 }
1188
1189 // Check context modifiers, warn about those, which try referencing non-existent tags.
1190 function findCtxModWarnings ($modlist)
1191 {
1192 $ret = array();
1193 foreach ($modlist as $mod)
1194 if (($mod['op'] == 'insert' or $mod['op'] == 'remove') and NULL === getTagByName ($mod['tag']))
1195 $ret[] = array
1196 (
1197 'header' => refRCLineno ($mod['lineno']),
1198 'class' => 'warning',
1199 'text' => "Tag '${mod['tag']}' does not exist."
1200 );
1201 return $ret;
1202 }
1203
1204 // Return true, if the expression makes use of the predicate given.
1205 function referencedPredicate ($pname, $expr)
1206 {
1207 switch ($expr['type'])
1208 {
1209 case 'LEX_BOOLCONST':
1210 case 'LEX_TAG':
1211 case 'LEX_AUTOTAG':
1212 return FALSE;
1213 case 'LEX_PREDICATE':
1214 return $pname == $expr['load'];
1215 case 'SYNT_NOTEXPR':
1216 return referencedPredicate ($pname, $expr['load']);
1217 case 'SYNT_BOOLOP':
1218 return referencedPredicate ($pname, $expr['left']) or referencedPredicate ($pname, $expr['right']);
1219 default: // This is actually an internal error.
1220 return FALSE;
1221 }
1222 }
1223
1224 // Return 'always true', 'always false' or any other verdict.
1225 function invariantExpression ($expr)
1226 {
1227 $self = __FUNCTION__;
1228 switch ($expr['type'])
1229 {
1230 case 'SYNT_GRANT':
1231 return $self ($expr['condition']);
1232 case 'SYNT_DEFINITION':
1233 return $self ($expr['definition']);
1234 case 'LEX_BOOLCONST':
1235 if ($expr['load'] == 'true')
1236 return 'always true';
1237 return 'always false';
1238 case 'LEX_TAG':
1239 case 'LEX_AUTOTAG':
1240 case 'LEX_PREDICATE':
1241 return 'sometimes something';
1242 case 'SYNT_NOTEXPR':
1243 return $self ($expr['load']);
1244 case 'SYNT_BOOLOP':
1245 $leftanswer = $self ($expr['left']);
1246 $rightanswer = $self ($expr['right']);
1247 // "true or anything" is always true and thus const
1248 if ($expr['subtype'] == 'or' and ($leftanswer == 'always true' or $rightanswer == 'always true'))
1249 return 'always true';
1250 // "false and anything" is always false and thus const
1251 if ($expr['subtype'] == 'and' and ($leftanswer == 'always false' or $rightanswer == 'always false'))
1252 return 'always false';
1253 // "true and true" is true
1254 if ($expr['subtype'] == 'and' and ($leftanswer == 'always true' and $rightanswer == 'always true'))
1255 return 'always true';
1256 // "false or false" is false
1257 if ($expr['subtype'] == 'or' and ($leftanswer == 'always false' and $rightanswer == 'always false'))
1258 return 'always false';
1259 return '';
1260 default: // This is actually an internal error.
1261 break;
1262 }
1263 }
1264
1265 ?>