r2379 - drop user_enabled column and all related stuff
[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'],
416 'load' => array_merge ($stacksecondtop['load'], $stacktop['load'])
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
bcd37231 721function gotClearanceForTagChain ($tagchain)
a27a02c5 722{
bcd37231 723 global $rackCode;
a27a02c5 724 $ptable = array();
bcd37231 725 foreach ($rackCode as $sentence)
a27a02c5
DO
726 {
727 switch ($sentence['type'])
728 {
729 case 'SYNT_DEFINITION':
730 $ptable[$sentence['term']] = $sentence['definition'];
731 break;
732 case 'SYNT_GRANT':
733 if (eval_expression ($sentence['condition'], $tagchain, $ptable))
734 switch ($sentence['decision'])
735 {
736 case 'allow':
737 return TRUE;
738 case 'deny':
739 return FALSE;
740 default:
85a8ec3f 741 showError ("Condition match for unknown grant decision '${sentence['decision']}'", __FUNCTION__);
a27a02c5
DO
742 break;
743 }
bcd37231 744 break;
578d9d02
DO
745 case 'SYNT_ADJUSTMENT':
746 // do nothing yet
747 break;
a27a02c5 748 default:
85a8ec3f 749 showError ("Can't process sentence of unknown type '${sentence['type']}'", __FUNCTION__);
a27a02c5
DO
750 break;
751 }
752 }
753 return FALSE;
754}
755
cf25e649 756function getRackCode ($text)
bcd37231 757{
cf25e649
DO
758 if (!mb_strlen ($text))
759 return array ('result' => 'NAK', 'load' => 'The RackCode text was found empty in ' . __FUNCTION__);
760 $text = str_replace ("\r", '', $text) . "\n";
761 $lex = getLexemsFromRackCode ($text);
762 if ($lex['result'] != 'ACK')
763 return $lex;
764 $synt = getSentencesFromLexems ($lex['load']);
765 if ($synt['result'] != 'ACK')
766 return $synt;
767 // An empty sentence list is semantically valid, yet senseless,
768 // so checking intermediate result once more won't hurt.
769 if (!count ($synt['load']))
770 return array ('result' => 'NAK', 'load' => 'Empty parse tree found in ' . __FUNCTION__);
771 return semanticFilter ($synt['load']);
bcd37231
DO
772}
773
3082e137
DO
774// Return NULL, if the given expression can be evaluated against the given
775// predicate list. Return the name of the first show stopper otherwise.
776function firstUnrefPredicate ($plist, $expr)
e6a4adb9
DO
777{
778 switch ($expr['type'])
779 {
85a8ec3f 780 case 'LEX_BOOLCONST':
e6a4adb9 781 case 'LEX_TAG':
3082e137 782 return NULL;
e6a4adb9 783 case 'LEX_PREDICATE':
3082e137 784 return in_array ($expr['load'], $plist) ? NULL : $expr['load'];
e6a4adb9 785 case 'SYNT_NOTEXPR':
3082e137 786 return firstUnrefPredicate ($plist, $expr['load']);
e6a4adb9 787 case 'SYNT_BOOLOP':
3082e137
DO
788 if (($tmp = firstUnrefPredicate ($plist, $expr['left'])) !== NULL)
789 return $tmp;
790 if (($tmp = firstUnrefPredicate ($plist, $expr['right'])) !== NULL)
791 return $tmp;
792 return NULL;
e6a4adb9 793 default:
3082e137 794 return NULL;
e6a4adb9
DO
795 }
796}
797
cf25e649 798function semanticFilter ($code)
e6a4adb9
DO
799{
800 $predicatelist = array();
801 foreach ($code as $sentence)
802 switch ($sentence['type'])
803 {
804 case 'SYNT_DEFINITION':
3082e137
DO
805 $up = firstUnrefPredicate ($predicatelist, $sentence['definition']);
806 if ($up !== NULL)
807 return array
808 (
809 'result' => 'NAK',
810 'load' => "definition [${sentence['term']}] uses unknown predicate [${up}]"
811 );
e6a4adb9
DO
812 $predicatelist[] = $sentence['term'];
813 break;
814 case 'SYNT_GRANT':
3082e137
DO
815 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
816 if ($up !== NULL)
817 return array
818 (
819 'result' => 'NAK',
820 'load' => "grant sentence uses unknown predicate [${up}]"
821 );
e6a4adb9 822 break;
578d9d02
DO
823 case 'SYNT_ADJUSTMENT':
824 // Only condition part gets tested, because it's normal to set (or even to unset)
825 // something, that's not set.
826 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
827 if ($up !== NULL)
828 return array
829 (
830 'result' => 'NAK',
831 'load' => "adjustment sentence uses unknown predicate [${up}]"
832 );
833 break;
e6a4adb9 834 default:
cf25e649 835 return array ('result' => 'NAK', 'load' => 'unknown sentence type');
e6a4adb9 836 }
cf25e649 837 return array ('result' => 'ACK', 'load' => $code);
e6a4adb9
DO
838}
839
05693a83
DO
840// Accept a stack and figure out the cause of it not being parsed into a tree.
841// Return the line number or zero.
842function locateSyntaxError ($stack)
843{
844 // The first SYNT_CODETEXT node, if is present, holds stuff already
845 // successfully processed. Its line counter shows, where the last reduction
846 // took place (it _might_ be the same line, which causes the syntax error).
847 // The next node (it's very likely to exist) should have its line counter
848 // pointing to the place, where the first (of 1 or more) error is located.
849 if (isset ($stack[0]['type']) and $stack[0]['type'] == 'SYNT_CODETEXT')
850 unset ($stack[0]);
851 foreach ($stack as $node)
852 // Satisfy with the first line number met.
853 if (isset ($node['lineno']))
854 return $node['lineno'];
855 return 0;
856}
857
061452b9
DO
858function refRCLineno ($ln)
859{
860 global $root;
861 return "<a href='${root}?page=perms&tab=default#line${ln}'>line ${ln}</a>";
862}
863
15555995 864function getRackCodeWarnings ()
88d513cd 865{
15555995
DO
866 $ret = array();
867 global $rackCode;
1a4096cb
DO
868 // tags
869 foreach ($rackCode as $sentence)
870 switch ($sentence['type'])
871 {
872 case 'SYNT_DEFINITION':
873 $ret = array_merge ($ret, findTagWarnings ($sentence['definition']));
874 break;
875 case 'SYNT_GRANT':
578d9d02 876 case 'SYNT_ADJUSTMENT':
1a4096cb
DO
877 $ret = array_merge ($ret, findTagWarnings ($sentence['condition']));
878 break;
879 default:
880 $ret[] = array
881 (
882 'header' => 'internal error',
883 'class' => 'error',
884 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
885 );
886 }
15555995
DO
887 // autotags
888 foreach ($rackCode as $sentence)
889 switch ($sentence['type'])
890 {
891 case 'SYNT_DEFINITION':
892 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['definition']));
893 break;
894 case 'SYNT_GRANT':
578d9d02 895 case 'SYNT_ADJUSTMENT':
15555995
DO
896 $ret = array_merge ($ret, findAutoTagWarnings ($sentence['condition']));
897 break;
898 default:
899 $ret[] = array
900 (
901 'header' => 'internal error',
902 'class' => 'error',
903 'text' => "Skipped sentence of unknown type '${sentence['type']}'"
904 );
905 }
52837ce6
DO
906 // predicates
907 $plist = array();
908 foreach ($rackCode as $sentence)
909 if ($sentence['type'] == 'SYNT_DEFINITION')
910 $plist[$sentence['term']] = $sentence['lineno'];
911 foreach ($plist as $pname => $lineno)
912 {
913 foreach ($rackCode as $sentence)
914 switch ($sentence['type'])
915 {
916 case 'SYNT_DEFINITION':
917 if (referencedPredicate ($pname, $sentence['definition']))
918 continue 3; // clear, next term
919 break;
920 case 'SYNT_GRANT':
578d9d02 921 case 'SYNT_ADJUSTMENT':
52837ce6
DO
922 if (referencedPredicate ($pname, $sentence['condition']))
923 continue 3; // idem
924 break;
925 }
926 $ret[] = array
927 (
061452b9 928 'header' => refRCLineno ($lineno),
52837ce6
DO
929 'class' => 'warning',
930 'text' => "Predicate '${pname}' is defined, but never used."
931 );
932 }
d05ed211
DO
933 // expressions
934 foreach ($rackCode as $sentence)
935 switch (invariantExpression ($sentence))
936 {
937 case 'always true':
938 $ret[] = array
939 (
061452b9 940 'header' => refRCLineno ($sentence['lineno']),
d05ed211
DO
941 'class' => 'warning',
942 'text' => "Expression is always true."
943 );
944 break;
945 case 'always false':
946 $ret[] = array
947 (
061452b9 948 'header' => refRCLineno ($sentence['lineno']),
d05ed211
DO
949 'class' => 'warning',
950 'text' => "Expression is always false."
951 );
952 break;
953 default:
954 break;
955 }
986544a6
DO
956 // Duplicates. Use the same hash function we used to.
957 $fpcache = array ('SYNT_DEFINITION' => array(), 'SYNT_GRANT' => array());
958 foreach ($rackCode as $sentence)
959 switch ($sentence['type'])
960 {
961 case 'SYNT_DEFINITION':
962 $fp = hash (PASSWORD_HASH, serialize (effectiveValue ($sentence['definition'])));
963 if (isset ($fpcache[$sentence['type']][$fp]))
964 $ret[] = array
965 (
061452b9 966 'header' => refRCLineno ($sentence['lineno']),
986544a6
DO
967 'class' => 'warning',
968 'text' => 'Effective definition equals that at line ' . $fpcache[$sentence['type']][$fp]
969 );
970 $fpcache[$sentence['type']][$fp] = $sentence['lineno'];
971 break;
972 case 'SYNT_GRANT':
973 $fp = hash (PASSWORD_HASH, serialize (effectiveValue ($sentence['condition'])));
974 if (isset ($fpcache[$sentence['type']][$fp]))
975 $ret[] = array
976 (
061452b9 977 'header' => refRCLineno ($sentence['lineno']),
986544a6
DO
978 'class' => 'warning',
979 'text' => 'Effective condition equals that at line ' . $fpcache[$sentence['type']][$fp]
980 );
981 $fpcache[$sentence['type']][$fp] = $sentence['lineno'];
982 break;
983 }
52837ce6 984 // bail out
15555995
DO
985 $nwarnings = count ($ret);
986 $ret[] = array
987 (
988 'header' => 'summary',
989 'class' => $nwarnings ? 'error' : 'success',
990 'text' => "Analysis complete, ${nwarnings} issues discovered."
991 );
88d513cd
DO
992 return $ret;
993}
994
52837ce6 995// Scan the given expression and return any issues found about its autotags.
15555995
DO
996function findAutoTagWarnings ($expr)
997{
998 switch ($expr['type'])
999 {
1000 case 'LEX_BOOLCONST':
1001 case 'LEX_PREDICATE':
1002 return array();
1003 case 'LEX_TAG':
1004 switch (TRUE)
1005 {
1006 case (mb_ereg_match ('^\$id_', $expr['load'])):
1007 $recid = mb_ereg_replace ('^\$id_', '', $expr['load']);
1008 if (recordExists ($recid, 'object'))
1009 return array();
1010 return array (array
1011 (
061452b9 1012 'header' => refRCLineno ($expr['lineno']),
15555995 1013 'class' => 'warning',
52837ce6 1014 'text' => "An object with ID '${recid}' does not exist."
15555995
DO
1015 ));
1016 case (mb_ereg_match ('^\$ipv4netid_', $expr['load'])):
1017 $recid = mb_ereg_replace ('^\$ipv4netid_', '', $expr['load']);
1018 if (recordExists ($recid, 'ipv4net'))
1019 return array();
1020 return array (array
1021 (
061452b9 1022 'header' => refRCLineno ($expr['lineno']),
15555995 1023 'class' => 'warning',
1a315491
DO
1024 'text' => "IPv4 network with ID '${recid}' does not exist."
1025 ));
1026 case (mb_ereg_match ('^\$userid_', $expr['load'])):
1027 $recid = mb_ereg_replace ('^\$userid_', '', $expr['load']);
1028 if (recordExists ($recid, 'user'))
1029 return array();
1030 return array (array
1031 (
061452b9 1032 'header' => refRCLineno ($expr['lineno']),
1a315491
DO
1033 'class' => 'warning',
1034 'text' => "User account with ID '${recid}' does not exist."
1035 ));
1036 case (mb_ereg_match ('^\$username_', $expr['load'])):
1037 global $accounts;
1038 $recid = mb_ereg_replace ('^\$username_', '', $expr['load']);
1039 if (isset ($accounts[$recid]))
1040 return array();
1041 return array (array
1042 (
061452b9 1043 'header' => refRCLineno ($expr['lineno']),
1a315491
DO
1044 'class' => 'warning',
1045 'text' => "User account with name '${recid}' does not exist."
15555995
DO
1046 ));
1047 default:
1048 return array();
1049 }
1050 case 'SYNT_NOTEXPR':
1051 return findAutoTagWarnings ($expr['load']);
1052 case 'SYNT_BOOLOP':
1053 return array_merge
1054 (
1055 findAutoTagWarnings ($expr['left']),
1056 findAutoTagWarnings ($expr['right'])
1057 );
1058 default:
1059 return array (array
1060 (
1061 'header' => 'internal error',
1062 'class' => 'error',
1a4096cb
DO
1063 'text' => "Skipped expression of unknown type '${expr['type']}'"
1064 ));
1065 }
1066}
1067
1068// Idem WRT tags.
1069function findTagWarnings ($expr)
1070{
1071 global $taglist;
1072 switch ($expr['type'])
1073 {
1074 case 'LEX_BOOLCONST':
1075 case 'LEX_PREDICATE':
1076 return array();
1077 case 'LEX_TAG':
1078 // Only verify stuff, that has passed through the saving handler.
1079 if (!mb_ereg_match (TAGNAME_REGEXP, $expr['load']))
1080 return array();
1081 foreach ($taglist as $taginfo)
1082 if ($taginfo['tag'] == $expr['load'])
1083 return array();
1084 return array (array
1085 (
061452b9 1086 'header' => refRCLineno ($expr['lineno']),
1a4096cb
DO
1087 'class' => 'warning',
1088 'text' => "Tag '${expr['load']}' does not exist."
1089 ));
1090 case 'SYNT_NOTEXPR':
1091 return findTagWarnings ($expr['load']);
1092 case 'SYNT_BOOLOP':
1093 return array_merge
1094 (
1095 findTagWarnings ($expr['left']),
1096 findTagWarnings ($expr['right'])
1097 );
1098 default:
1099 return array (array
1100 (
1101 'header' => 'internal error',
1102 'class' => 'error',
1103 'text' => "Skipped expression of unknown type '${expr['type']}'"
15555995
DO
1104 ));
1105 }
1106}
1107
52837ce6
DO
1108// Return true, if the expression makes use of the predicate given.
1109function referencedPredicate ($pname, $expr)
1110{
1111 switch ($expr['type'])
1112 {
1113 case 'LEX_BOOLCONST':
1114 case 'LEX_TAG':
1115 return FALSE;
1116 case 'LEX_PREDICATE':
1117 return $pname == $expr['load'];
1118 case 'SYNT_NOTEXPR':
1119 return referencedPredicate ($pname, $expr['load']);
1120 case 'SYNT_BOOLOP':
1121 return referencedPredicate ($pname, $expr['left']) or referencedPredicate ($pname, $expr['right']);
1122 default: // This is actually an internal error.
1123 return FALSE;
1124 }
1125}
1126
d05ed211
DO
1127// Return 'always true', 'always false' or any other verdict.
1128function invariantExpression ($expr)
1129{
1130 $self = __FUNCTION__;
1131 switch ($expr['type'])
1132 {
1133 case 'SYNT_GRANT':
1134 return $self ($expr['condition']);
1135 case 'SYNT_DEFINITION':
1136 return $self ($expr['definition']);
1137 case 'LEX_BOOLCONST':
1138 if ($expr['load'] == 'true')
1139 return 'always true';
1140 return 'always false';
1141 case 'LEX_TAG':
1142 case 'LEX_PREDICATE':
1143 return 'sometimes something';
1144 case 'SYNT_NOTEXPR':
1145 return $self ($expr['load']);
1146 case 'SYNT_BOOLOP':
1147 $leftanswer = $self ($expr['left']);
1148 $rightanswer = $self ($expr['right']);
1149 // "true or anything" is always true and thus const
1150 if ($expr['subtype'] == 'or' and ($leftanswer == 'always true' or $rightanswer == 'always true'))
1151 return 'always true';
1152 // "false and anything" is always false and thus const
1153 if ($expr['subtype'] == 'and' and ($leftanswer == 'always false' or $rightanswer == 'always false'))
1154 return 'always false';
1155 // "true and true" is true
1156 if ($expr['subtype'] == 'and' and ($leftanswer == 'always true' and $rightanswer == 'always true'))
1157 return 'always true';
1158 // "false or false" is false
1159 if ($expr['subtype'] == 'or' and ($leftanswer == 'always false' and $rightanswer == 'always false'))
1160 return 'always false';
1161 return '';
1162 default: // This is actually an internal error.
1163 break;
1164 }
1165}
1166
986544a6
DO
1167// FIXME: First do line number stripping, otherwise hashes will always differ even
1168// for the obviously equivalent expressions. In some longer term mean transform the
1169// expression into minimalistic and ordered form.
1170function effectiveValue ($expr)
1171{
1172 return $expr;
1173}
1174
f63072f5 1175?>