r3864 copy recent exceptions-related commits 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 (preg_match ('/[\p{L}]/u', $char) == 1):
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 (preg_match ('/[\p{L}]/u', $char) == 1):
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 (preg_match ('/[\p{L}0-9\$]/u', $char) == 1):
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 (preg_match ('/[\p{L}0-9. _~-]/u', $char) == 1):
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 (preg_match ('/[\p{L}0-9]/u', $char) == 1):
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 (preg_match ('/[\p{L}0-9. _~-]/u', $char) == 1):
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 showWarning ("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 showWarning ("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 throw new RackTablesError ('invalid structure', RackTablesError::INTERNAL);
873 }
874 return $didChanges;
875 }
876
877 // The argument doesn't include explicit and implicit tags. This allows us to derive implicit chain
878 // each time we modify the given argument (and work with the modified copy from now on).
879 // After the work is done the global $impl_tags is silently modified
880 function gotClearanceForTagChain ($const_base)
881 {
882 global $rackCode, $expl_tags, $impl_tags;
883 $ptable = array();
884 foreach ($rackCode as $sentence)
885 {
886 switch ($sentence['type'])
887 {
888 case 'SYNT_DEFINITION':
889 $ptable[$sentence['term']] = $sentence['definition'];
890 break;
891 case 'SYNT_GRANT':
892 if (eval_expression ($sentence['condition'], array_merge ($const_base, $expl_tags, $impl_tags), $ptable))
893 switch ($sentence['decision'])
894 {
895 case 'LEX_ALLOW':
896 return TRUE;
897 case 'LEX_DENY':
898 return FALSE;
899 default:
900 showWarning ("Condition match for unknown grant decision '${sentence['decision']}'", __FUNCTION__);
901 break;
902 }
903 break;
904 case 'SYNT_ADJUSTMENT':
905 if
906 (
907 eval_expression ($sentence['condition'], array_merge ($const_base, $expl_tags, $impl_tags), $ptable) and
908 processAdjustmentSentence ($sentence['modlist'], $expl_tags)
909 ) // recalculate implicit chain only after actual change, not just on matched condition
910 $impl_tags = getImplicitTags ($expl_tags); // recalculate
911 break;
912 default:
913 showWarning ("Can't process sentence of unknown type '${sentence['type']}'", __FUNCTION__);
914 break;
915 }
916 }
917 return FALSE;
918 }
919
920 // Top-level wrapper for most of the code in this file. Get a text, return a parse tree
921 // (or error message).
922 function getRackCode ($text)
923 {
924 if (!mb_strlen ($text))
925 return array ('result' => 'NAK', 'load' => 'The RackCode text was found empty in ' . __FUNCTION__);
926 $text = str_replace ("\r", '', $text) . "\n";
927 $synt = spotPayload ($text, 'SYNT_CODETEXT');
928 if ($synt['result'] != 'ACK')
929 return $synt;
930 // An empty sentence list is semantically valid, yet senseless,
931 // so checking intermediate result once more won't hurt.
932 if (!count ($synt['load']))
933 return array ('result' => 'NAK', 'load' => 'Empty parse tree found in ' . __FUNCTION__);
934 return semanticFilter ($synt['load']);
935 }
936
937 // Return NULL, if the given expression can be evaluated against the given
938 // predicate list. Return the name of the first show stopper otherwise.
939 function firstUnrefPredicate ($plist, $expr)
940 {
941 $self = __FUNCTION__;
942 switch ($expr['type'])
943 {
944 case 'LEX_TRUE':
945 case 'LEX_FALSE':
946 case 'LEX_TAG':
947 case 'LEX_AUTOTAG':
948 return NULL;
949 case 'LEX_PREDICATE':
950 return in_array ($expr['load'], $plist) ? NULL : $expr['load'];
951 case 'SYNT_NOT_EXPR':
952 return $self ($plist, $expr['load']);
953 case 'SYNT_EXPR':
954 case 'SYNT_AND_EXPR':
955 if (($tmp = $self ($plist, $expr['left'])) !== NULL)
956 return $tmp;
957 if (($tmp = $self ($plist, $expr['right'])) !== NULL)
958 return $tmp;
959 return NULL;
960 default:
961 return NULL;
962 }
963 }
964
965 function semanticFilter ($code)
966 {
967 $predicatelist = array();
968 foreach ($code as $sentence)
969 switch ($sentence['type'])
970 {
971 case 'SYNT_DEFINITION':
972 // A predicate can only be defined once.
973 if (in_array ($sentence['term'], $predicatelist))
974 return array
975 (
976 'result' => 'NAK',
977 'load' => "[${sentence['term']}] has already been defined earlier"
978 );
979 // Check below makes sure, that definitions are built from already existing
980 // tokens. This also makes recursive definitions impossible.
981 $up = firstUnrefPredicate ($predicatelist, $sentence['definition']);
982 if ($up !== NULL)
983 return array
984 (
985 'result' => 'NAK',
986 'load' => "definition of [${sentence['term']}] refers to [${up}], which is not (yet) defined"
987 );
988 $predicatelist[] = $sentence['term'];
989 break;
990 case 'SYNT_GRANT':
991 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
992 if ($up !== NULL)
993 return array
994 (
995 'result' => 'NAK',
996 'load' => "grant sentence uses unknown predicate [${up}]"
997 );
998 break;
999 case 'SYNT_ADJUSTMENT':
1000 // Only condition part gets tested, because it's normal to set (or even to unset)
1001 // something, that's not set.
1002 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
1003 if ($up !== NULL)
1004 return array
1005 (
1006 'result' => 'NAK',
1007 'load' => "adjustment sentence uses unknown predicate [${up}]"
1008 );
1009 break;
1010 default:
1011 return array ('result' => 'NAK', 'load' => 'unknown sentence type');
1012 }
1013 return array ('result' => 'ACK', 'load' => $code);
1014 }
1015
1016 // Accept a stack and figure out the cause of it not being parsed into a tree.
1017 // Return the line number or zero.
1018 function locateSyntaxError ($stack)
1019 {
1020 // The first SYNT_CODETEXT node, if is present, holds stuff already
1021 // successfully processed. Its line counter shows, where the last reduction
1022 // took place (it _might_ be the same line, which causes the syntax error).
1023 // The next node (it's very likely to exist) should have its line counter
1024 // pointing to the place, where the first (of 1 or more) error is located.
1025 if (isset ($stack[0]['type']) and $stack[0]['type'] == 'SYNT_CODETEXT')
1026 unset ($stack[0]);
1027 foreach ($stack as $node)
1028 // Satisfy with the first line number met.
1029 if (isset ($node['lineno']))
1030 return $node['lineno'];
1031 return 0;
1032 }
1033
1034 function refRCLineno ($ln)
1035 {
1036 return "<a href='index.php?page=perms&tab=default#line${ln}'>line ${ln}</a>";
1037 }
1038
1039 function getRackCodeWarnings ()
1040 {
1041 $ret = array();
1042 global $rackCode;
1043 // tags
1044 foreach ($rackCode as $sentence)
1045 switch ($sentence['type'])
1046 {
1047 case 'SYNT_DEFINITION':
1048 $ret = array_merge ($ret, findTagWarnings ($sentence['definition']));
1049 break;
1050 case 'SYNT_ADJUSTMENT':
1051 $ret = array_merge ($ret, findTagWarnings ($sentence['condition']));
1052 $ret = array_merge ($ret, findCtxModWarnings ($sentence['modlist']));
1053 break;
1054 case 'SYNT_GRANT':
1055 $ret = array_merge ($ret, findTagWarnings ($sentence['condition']));
1056 break;
1057 default:
1058 $ret[] = array
1059 (
1060 'header' => 'internal error',
1061 'class' => 'error',
1062 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
1063 );
1064 }
1065 // autotags
1066 foreach ($rackCode as $sentence)
1067 switch ($sentence['type'])
1068 {
1069 case 'SYNT_DEFINITION':
1070 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['definition']));
1071 break;
1072 case 'SYNT_GRANT':
1073 case 'SYNT_ADJUSTMENT':
1074 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['condition']));
1075 break;
1076 default:
1077 $ret[] = array
1078 (
1079 'header' => 'internal error',
1080 'class' => 'error',
1081 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
1082 );
1083 }
1084 // predicates
1085 $plist = array();
1086 foreach ($rackCode as $sentence)
1087 if ($sentence['type'] == 'SYNT_DEFINITION')
1088 $plist[$sentence['term']] = $sentence['lineno'];
1089 foreach ($plist as $pname => $lineno)
1090 {
1091 foreach ($rackCode as $sentence)
1092 switch ($sentence['type'])
1093 {
1094 case 'SYNT_DEFINITION':
1095 if (referencedPredicate ($pname, $sentence['definition']))
1096 continue 3; // clear, next term
1097 break;
1098 case 'SYNT_GRANT':
1099 case 'SYNT_ADJUSTMENT':
1100 if (referencedPredicate ($pname, $sentence['condition']))
1101 continue 3; // idem
1102 break;
1103 }
1104 $ret[] = array
1105 (
1106 'header' => refRCLineno ($lineno),
1107 'class' => 'warning',
1108 'text' => "Predicate '${pname}' is defined, but never used."
1109 );
1110 }
1111 // expressions
1112 foreach ($rackCode as $sentence)
1113 switch (invariantExpression ($sentence))
1114 {
1115 case 'always true':
1116 $ret[] = array
1117 (
1118 'header' => refRCLineno ($sentence['lineno']),
1119 'class' => 'warning',
1120 'text' => "Expression is always true."
1121 );
1122 break;
1123 case 'always false':
1124 $ret[] = array
1125 (
1126 'header' => refRCLineno ($sentence['lineno']),
1127 'class' => 'warning',
1128 'text' => "Expression is always false."
1129 );
1130 break;
1131 default:
1132 break;
1133 }
1134 // bail out
1135 $nwarnings = count ($ret);
1136 $ret[] = array
1137 (
1138 'header' => 'summary',
1139 'class' => $nwarnings ? 'error' : 'success',
1140 'text' => "Analysis complete, ${nwarnings} issues discovered."
1141 );
1142 return $ret;
1143 }
1144
1145 // Scan the given expression and return any issues found about its autotags.
1146 function findAutoTagWarnings ($expr)
1147 {
1148 $self = __FUNCTION__;
1149 switch ($expr['type'])
1150 {
1151 case 'LEX_TRUE':
1152 case 'LEX_FALSE':
1153 case 'LEX_PREDICATE':
1154 case 'LEX_TAG':
1155 return array();
1156 case 'LEX_AUTOTAG':
1157 switch (1)
1158 {
1159 case (preg_match ('/^\$id_/', $expr['load'])):
1160 $recid = preg_replace ('/^\$id_/', '', $expr['load']);
1161 if (NULL !== spotEntity ('object', $recid))
1162 return array();
1163 return array (array
1164 (
1165 'header' => refRCLineno ($expr['lineno']),
1166 'class' => 'warning',
1167 'text' => "An object with ID '${recid}' does not exist."
1168 ));
1169 case (preg_match ('/^\$ipv4netid_/', $expr['load'])):
1170 $recid = preg_replace ('/^\$ipv4netid_/', '', $expr['load']);
1171 if (NULL != spotEntity ('ipv4net', $recid))
1172 return array();
1173 return array (array
1174 (
1175 'header' => refRCLineno ($expr['lineno']),
1176 'class' => 'warning',
1177 'text' => "IPv4 network with ID '${recid}' does not exist."
1178 ));
1179 case (preg_match ('/^\$userid_/', $expr['load'])):
1180 $recid = preg_replace ('/^\$userid_/', '', $expr['load']);
1181 if (NULL !== spotEntity ('user', $recid))
1182 return array();
1183 return array (array
1184 (
1185 'header' => refRCLineno ($expr['lineno']),
1186 'class' => 'warning',
1187 'text' => "User account with ID '${recid}' does not exist."
1188 ));
1189 case (preg_match ('/^\$username_/', $expr['load'])):
1190 $recid = preg_replace ('/^\$username_/', '', $expr['load']);
1191 global $require_local_account;
1192 if (!$require_local_account)
1193 return array();
1194 if (NULL !== getUserIDByUsername ($recid))
1195 return array();
1196 return array (array
1197 (
1198 'header' => refRCLineno ($expr['lineno']),
1199 'class' => 'warning',
1200 'text' => "Local user account '${recid}' does not exist."
1201 ));
1202 // FIXME: pull identifier at the same pass, which does the matching
1203 case (preg_match ('/^\$page_[\p{L}0-9]+$/u', $expr['load'])):
1204 $recid = preg_replace ('/^\$page_/', '', $expr['load']);
1205 global $page;
1206 if (isset ($page[$recid]))
1207 return array();
1208 return array (array
1209 (
1210 'header' => refRCLineno ($expr['lineno']),
1211 'class' => 'warning',
1212 'text' => "Page number '${recid}' does not exist."
1213 ));
1214 case (preg_match ('/^\$(tab|op)_[\p{L}0-9]+$/u', $expr['load'])):
1215 case (preg_match ('/^\$any_(op|rack|object|ip4net|net|ipv4vs|vs|ipv4rsp|rsp|file)$/', $expr['load'])):
1216 case (preg_match ('/^\$typeid_[[:digit:]]+$/', $expr['load'])): // FIXME: check value validity
1217 case (preg_match ('/^\$cn_.+$/', $expr['load'])): // FIXME: check name validity and asset existence
1218 case (preg_match ('/^\$lgcn_.+$/', $expr['load'])): // FIXME: check name validity
1219 case (preg_match ('/^\$(fromvlan|tovlan)_[[:digit:]]+$/', $expr['load'])):
1220 case (preg_match ('/^\$(unmounted|untagged|no_asset_tag|runs_8021Q)$/', $expr['load'])):
1221 case (preg_match ('/^\$masklen_(eq|le|ge)_[[:digit:]][[:digit:]]?$/', $expr['load'])):
1222 return array();
1223 default:
1224 return array (array
1225 (
1226 'header' => refRCLineno ($expr['lineno']),
1227 'class' => 'warning',
1228 'text' => "Martian autotag '${expr['load']}'"
1229 ));
1230 }
1231 case 'SYNT_NOT_EXPR':
1232 return $self ($expr['load']);
1233 case 'SYNT_AND_EXPR':
1234 case 'SYNT_EXPR':
1235 return array_merge
1236 (
1237 $self ($expr['left']),
1238 $self ($expr['right'])
1239 );
1240 default:
1241 return array (array
1242 (
1243 'header' => "internal error in ${self}",
1244 'class' => 'error',
1245 'text' => "Skipped expression of unknown type '${expr['type']}'"
1246 ));
1247 }
1248 }
1249
1250 // Idem WRT tags.
1251 function findTagWarnings ($expr)
1252 {
1253 $self = __FUNCTION__;
1254 switch ($expr['type'])
1255 {
1256 case 'LEX_TRUE':
1257 case 'LEX_FALSE':
1258 case 'LEX_PREDICATE':
1259 case 'LEX_AUTOTAG':
1260 return array();
1261 case 'LEX_TAG':
1262 if (getTagByName ($expr['load']) !== NULL)
1263 return array();
1264 return array (array
1265 (
1266 'header' => refRCLineno ($expr['lineno']),
1267 'class' => 'warning',
1268 'text' => "Tag '${expr['load']}' does not exist."
1269 ));
1270 case 'SYNT_NOT_EXPR':
1271 return $self ($expr['load']);
1272 case 'SYNT_AND_EXPR':
1273 case 'SYNT_EXPR':
1274 return array_merge
1275 (
1276 $self ($expr['left']),
1277 $self ($expr['right'])
1278 );
1279 default:
1280 return array (array
1281 (
1282 'header' => "internal error in ${self}",
1283 'class' => 'error',
1284 'text' => "Skipped expression of unknown type '${expr['type']}'"
1285 ));
1286 }
1287 }
1288
1289 // Check context modifiers, warn about those, which try referencing non-existent tags.
1290 function findCtxModWarnings ($modlist)
1291 {
1292 $ret = array();
1293 foreach ($modlist as $mod)
1294 if (($mod['op'] == 'insert' or $mod['op'] == 'remove') and NULL === getTagByName ($mod['tag']))
1295 $ret[] = array
1296 (
1297 'header' => refRCLineno ($mod['lineno']),
1298 'class' => 'warning',
1299 'text' => "Tag '${mod['tag']}' does not exist."
1300 );
1301 return $ret;
1302 }
1303
1304 // Return true, if the expression makes use of the predicate given.
1305 function referencedPredicate ($pname, $expr)
1306 {
1307 $self = __FUNCTION__;
1308 switch ($expr['type'])
1309 {
1310 case 'LEX_TRUE':
1311 case 'LEX_FALSE':
1312 case 'LEX_TAG':
1313 case 'LEX_AUTOTAG':
1314 return FALSE;
1315 case 'LEX_PREDICATE':
1316 return $pname == $expr['load'];
1317 case 'SYNT_NOT_EXPR':
1318 return $self ($pname, $expr['load']);
1319 case 'SYNT_AND_EXPR':
1320 case 'SYNT_EXPR':
1321 return $self ($pname, $expr['left']) or $self ($pname, $expr['right']);
1322 default: // This is actually an internal error.
1323 return FALSE;
1324 }
1325 }
1326
1327 // Return 'always true', 'always false' or any other verdict.
1328 function invariantExpression ($expr)
1329 {
1330 $self = __FUNCTION__;
1331 switch ($expr['type'])
1332 {
1333 case 'SYNT_GRANT':
1334 return $self ($expr['condition']);
1335 case 'SYNT_DEFINITION':
1336 return $self ($expr['definition']);
1337 case 'LEX_TRUE':
1338 return 'always true';
1339 case 'LEX_FALSE':
1340 return 'always false';
1341 case 'LEX_TAG':
1342 case 'LEX_AUTOTAG':
1343 case 'LEX_PREDICATE':
1344 return 'sometimes something';
1345 case 'SYNT_NOT_EXPR':
1346 return $self ($expr['load']);
1347 case 'SYNT_AND_EXPR':
1348 $leftanswer = $self ($expr['left']);
1349 $rightanswer = $self ($expr['right']);
1350 // "false and anything" is always false and thus const
1351 if ($leftanswer == 'always false' or $rightanswer == 'always false')
1352 return 'always false';
1353 // "true and true" is true
1354 if ($leftanswer == 'always true' and $rightanswer == 'always true')
1355 return 'always true';
1356 return '';
1357 case 'SYNT_EXPR':
1358 $leftanswer = $self ($expr['left']);
1359 $rightanswer = $self ($expr['right']);
1360 // "true or anything" is always true and thus const
1361 if ($leftanswer == 'always true' or $rightanswer == 'always true')
1362 return 'always true';
1363 // "false or false" is false
1364 if ($leftanswer == 'always false' and $rightanswer == 'always false')
1365 return 'always false';
1366 return '';
1367 default: // This is actually an internal error.
1368 break;
1369 }
1370 }
1371
1372 ?>