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