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