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