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