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