r2163 - show tag chain for each account on the user list
[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.
9f54e6e9 21function lexError1 ($state, $text, $pos)
f63072f5 22{
23818dde
DO
23 $message = "invalid char with code " . ord (mb_substr ($text, $pos, 1)) . ' (';
24 $message .= mb_substr ($text, $pos, 1) . ") at position ${pos} (FSM state is '${state}')";
cf25e649 25 return array ('result' => 'NAK', 'load' => $message);
f63072f5
DO
26}
27
28// Complain about martian keyword.
9f54e6e9 29function lexError2 ($word)
f63072f5 30{
cf25e649
DO
31 return array
32 (
33 'result' => 'NAK',
34 'load' => "could not parse keyword '${word}'"
35 );
f63072f5
DO
36}
37
a1b88eca 38// Complain about wrong FSM state.
9f54e6e9 39function lexError3 ($state)
a1b88eca 40{
cf25e649
DO
41 return array
42 (
43 'result' => 'NAK',
44 'load' => "FSM state is still '${state}' at end of input"
45 );
a1b88eca
DO
46}
47
9f54e6e9
DO
48function lexError4 ($s)
49{
50 return array
51 (
52 'result' => 'NAK',
53 'load' => "Invalid tag or predicate name '${s}'"
54 );
55}
56
a1b88eca
DO
57// Produce a list of lexems from the given text. Possible lexems are:
58function getLexemsFromRackCode ($text)
f63072f5
DO
59{
60 $ret = array();
bcd49780 61 $textlen = mb_strlen ($text);
f63072f5
DO
62 $state = "ESOTSM";
63 for ($i = 0; $i < $textlen; $i++) :
bcd49780 64 $char = mb_substr ($text, $i, 1);
f63072f5
DO
65 $newstate = $state;
66 switch ($state) :
67 case 'ESOTSM':
68 switch (TRUE)
69 {
f63072f5 70 case ($char == '('):
a1b88eca 71 $ret[] = array ('type' => 'LEX_LBRACE');
f63072f5
DO
72 break;
73 case ($char == ')'):
a1b88eca 74 $ret[] = array ('type' => 'LEX_RBRACE');
f63072f5
DO
75 break;
76 case ($char == '#'):
77 $newstate = 'skipping comment';
78 break;
bcd49780 79 case (mb_ereg ('[[:alpha:]]', $char) > 0):
cf25e649 80 $newstate = 'reading keyword';
f63072f5
DO
81 $buffer = $char;
82 break;
c6c53ad6 83 case (preg_match ('/^[ \t\n\r]$/', $char)):
f63072f5
DO
84 // nom-nom...
85 break;
86 case ($char == '{'):
87 $newstate = 'reading tag 1';
88 break;
89 case ($char == '['):
90 $newstate = 'reading predicate 1';
91 break;
92 default:
9f54e6e9 93 return lexError1 ($state, $text, $i);
f63072f5
DO
94 }
95 break;
cf25e649 96 case 'reading keyword':
f63072f5
DO
97 switch (TRUE)
98 {
bcd49780 99 case (mb_ereg ('[[:alpha:]]', $char) > 0):
f63072f5
DO
100 $buffer .= $char;
101 break;
102 case (preg_match ('/^[ \t\n]$/', $char)):
103 // got a word, sort it out
104 switch ($buffer)
105 {
106 case 'allow':
f63072f5 107 case 'deny':
a1b88eca 108 $ret[] = array ('type' => 'LEX_DECISION', 'load' => $buffer);
f63072f5
DO
109 break;
110 case 'define':
a1b88eca 111 $ret[] = array ('type' => 'LEX_DEFINE');
f63072f5
DO
112 break;
113 case 'and':
f63072f5 114 case 'or':
a1b88eca
DO
115 $ret[] = array ('type' => 'LEX_BOOLOP', 'load' => $buffer);
116 break;
117 case 'not':
118 $ret[] = array ('type' => 'LEX_NOT');
119 break;
120 case 'false':
121 case 'true':
122 $ret[] = array ('type' => 'LEX_BOOLCONST', 'load' => $buffer);
f63072f5
DO
123 break;
124 default:
9f54e6e9 125 return lexError2 ($buffer);
f63072f5
DO
126 }
127 $newstate = 'ESOTSM';
128 break;
129 default:
9f54e6e9 130 return lexError1 ($state, $text, $i);
f63072f5
DO
131 }
132 break;
133 case 'reading tag 1':
134 switch (TRUE)
135 {
c6c53ad6 136 case (preg_match ('/^[ \t\n\r]$/', $char)):
f63072f5
DO
137 // nom-nom...
138 break;
9f54e6e9 139 case (mb_ereg ('[[:alnum:]\$]', $char) > 0):
f63072f5
DO
140 $buffer = $char;
141 $newstate = 'reading tag 2';
142 break;
143 default:
9f54e6e9 144 return lexError1 ($state, $text, $i);
f63072f5
DO
145 }
146 break;
147 case 'reading tag 2':
148 switch (TRUE)
149 {
150 case ($char == '}'):
e5bd52e5 151 $buffer = rtrim ($buffer);
9f54e6e9
DO
152 if (!validTagName ($buffer, TRUE))
153 return lexError4 ($buffer);
e5bd52e5 154 $ret[] = array ('type' => 'LEX_TAG', 'load' => $buffer);
f63072f5
DO
155 $newstate = 'ESOTSM';
156 break;
23818dde 157 case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
f63072f5
DO
158 $buffer .= $char;
159 break;
160 default:
9f54e6e9 161 return lexError1 ($state, $text, $i);
f63072f5
DO
162 }
163 break;
164 case 'reading predicate 1':
165 switch (TRUE)
166 {
c6c53ad6 167 case (preg_match ('/^[ \t\n\r]$/', $char)):
f63072f5
DO
168 // nom-nom...
169 break;
9f54e6e9 170 case (mb_ereg ('[[:alnum:]]', $char) > 0):
f63072f5
DO
171 $buffer = $char;
172 $newstate = 'reading predicate 2';
173 break;
174 default:
9f54e6e9 175 return lexError1 ($state, $text, $i);
f63072f5
DO
176 }
177 break;
178 case 'reading predicate 2':
179 switch (TRUE)
180 {
181 case ($char == ']'):
e5bd52e5 182 $buffer = rtrim ($buffer);
9f54e6e9
DO
183 if (!validTagName ($buffer))
184 return lexError4 ($buffer);
e5bd52e5 185 $ret[] = array ('type' => 'LEX_PREDICATE', 'load' => $buffer);
f63072f5
DO
186 $newstate = 'ESOTSM';
187 break;
23818dde 188 case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
f63072f5
DO
189 $buffer .= $char;
190 break;
191 default:
9f54e6e9 192 return lexError1 ($state, $text, $i);
f63072f5
DO
193 }
194 break;
195 case 'skipping comment':
bcd49780 196 switch ($char)
f63072f5
DO
197 {
198 case "\n":
199 $newstate = 'ESOTSM';
200 default: // eat char, nom-nom...
201 break;
202 }
203 break;
204 default:
205 die (__FUNCTION__ . "(): internal error, state == ${state}");
206 endswitch;
207 $state = $newstate;
208 endfor;
e6a4adb9 209 if ($state != 'ESOTSM' and $state != 'skipping comment')
9f54e6e9 210 return lexError3 ($state);
cf25e649 211 return array ('result' => 'ACK', 'load' => $ret);
f63072f5
DO
212}
213
a1b88eca 214// Parse the given lexems stream into a list of RackCode sentences. Each such
a27a02c5
DO
215// sentence is a syntax tree, suitable for tag sequence evaluation. The final
216// parse tree may contain the following nodes:
217// LEX_TAG
218// LEX_PREDICATE
219// LEX_BOOLCONST
e5bd52e5
DO
220// SYNT_NOT (1 argument, holding SYNT_EXPR)
221// SYNT_BOOLOP (2 arguments, each holding SYNT_EXPR)
e5bd52e5 222// SYNT_DEFINITION (2 arguments: term and definition)
1381b655 223// SYNT_GRANT (2 arguments: decision and condition)
1381b655 224// SYNT_CODETEXT (sequence of sentences)
a27a02c5
DO
225//
226// After parsing the input successfully a list of SYNT_GRANT and SYNT_DEFINITION
227// trees is returned.
a1b88eca
DO
228function getSentencesFromLexems ($lexems)
229{
a1b88eca
DO
230 $stack = array(); // subject to array_push() and array_pop()
231 $done = 0; // $lexems[$done] is the next item in the tape
232 $todo = count ($lexems);
233
1381b655
DO
234 // Perform shift-reduce processing. The "accept" actions occurs with an
235 // empty input tape and the stack holding only one symbol (the start
236 // symbol, SYNT_CODETEXT).
237 while (TRUE)
a1b88eca
DO
238 {
239 $stacktop = $stacksecondtop = $stackthirdtop = array ('type' => 'null');
240 $stacksize = count ($stack);
241 if ($stacksize >= 1)
242 {
243 $stacktop = array_pop ($stack);
244 // It is possible to run into a S/R conflict, when having a syntaxically
245 // correct sentence base on the stack and some "and {something}" items
246 // on the input tape, hence let's detect this specific case and insist
247 // on "shift" action to make EXPR parsing hungry one.
1381b655
DO
248 if
249 (
250 $stacktop['type'] == 'SYNT_EXPR' and
251 ($done < $todo) and
252 $lexems[$done]['type'] == 'LEX_BOOLOP'
253 )
a1b88eca
DO
254 {
255 // shift!
256 array_push ($stack, $stacktop);
257 array_push ($stack, $lexems[$done++]);
258 continue;
259 }
260 if ($stacksize >= 2)
261 {
262 $stacksecondtop = array_pop ($stack);
263 if ($stacksize >= 3)
264 {
265 $stackthirdtop = array_pop ($stack);
266 array_push ($stack, $stackthirdtop);
267 }
268 array_push ($stack, $stacksecondtop);
269 }
270 array_push ($stack, $stacktop);
1381b655
DO
271 // First detect definition start to save the predicate from being reduced into
272 // expression.
273 if
274 (
275 $stacktop['type'] == 'LEX_PREDICATE' and
276 $stacksecondtop['type'] == 'LEX_DEFINE'
277 )
278 {
279 array_pop ($stack);
280 array_pop ($stack);
281 array_push
282 (
283 $stack,
284 array
285 (
286 'type' => 'SYNT_DEFINE',
287 'load' => $stacktop['load']
288 )
289 );
290 continue;
291 }
a1b88eca
DO
292 // Try "replace" action only on a non-empty stack.
293 // If a handle is found for reversing a production rule, do it and start a new
294 // cycle instead of advancing further on rule list. This will preserve rule priority
295 // in the grammar and keep us from an extra shift action.
296 if
297 (
298 $stacktop['type'] == 'LEX_BOOLCONST' or
299 $stacktop['type'] == 'LEX_TAG' or
300 $stacktop['type'] == 'LEX_PREDICATE'
301 )
302 {
1381b655 303 // reduce!
a1b88eca
DO
304 array_pop ($stack);
305 array_push
306 (
307 $stack,
308 array
309 (
310 'type' => 'SYNT_EXPR',
311 'load' => $stacktop
312 )
313 );
314 continue;
315 }
316 if
317 (
318 $stacktop['type'] == 'SYNT_EXPR' and
319 $stacksecondtop['type'] == 'LEX_NOT'
320 )
321 {
1381b655 322 // reduce!
a1b88eca
DO
323 array_pop ($stack);
324 array_pop ($stack);
325 array_push
326 (
327 $stack,
328 array
329 (
330 'type' => 'SYNT_EXPR',
331 'load' => array
332 (
333 'type' => 'SYNT_NOTEXPR',
a27a02c5 334 'load' => $stacktop['load']
a1b88eca
DO
335 )
336 )
337 );
338 continue;
339 }
340 if
341 (
342 $stacktop['type'] == 'LEX_RBRACE' and
343 $stacksecondtop['type'] == 'SYNT_EXPR' and
344 $stackthirdtop['type'] == 'LEX_LBRACE'
345 )
346 {
1381b655 347 // reduce!
a1b88eca
DO
348 array_pop ($stack);
349 array_pop ($stack);
350 array_pop ($stack);
351 array_push
352 (
353 $stack,
354 $stacksecondtop
355 );
356 continue;
357 }
358 if
359 (
360 $stacktop['type'] == 'SYNT_EXPR' and
361 $stacksecondtop['type'] == 'LEX_BOOLOP' and
362 $stackthirdtop['type'] == 'SYNT_EXPR'
363 )
364 {
1381b655 365 // reduce!
a1b88eca
DO
366 array_pop ($stack);
367 array_pop ($stack);
368 array_pop ($stack);
369 array_push
370 (
371 $stack,
372 array
373 (
374 'type' => 'SYNT_EXPR',
375 'load' => array
376 (
377 'type' => 'SYNT_BOOLOP',
378 'subtype' => $stacksecondtop['load'],
a27a02c5
DO
379 'left' => $stackthirdtop['load'],
380 'right' => $stacktop['load']
a1b88eca
DO
381 )
382 )
383 );
384 continue;
385 }
1381b655
DO
386 if
387 (
388 $stacktop['type'] == 'SYNT_EXPR' and
389 $stacksecondtop['type'] == 'LEX_DECISION'
390 )
391 {
392 // reduce!
393 array_pop ($stack);
394 array_pop ($stack);
395 array_push
396 (
397 $stack,
398 array
399 (
400 'type' => 'SYNT_GRANT',
401 'decision' => $stacksecondtop['load'],
a27a02c5 402 'condition' => $stacktop['load']
1381b655
DO
403 )
404 );
405 continue;
406 }
407 if
408 (
409 $stacktop['type'] == 'SYNT_EXPR' and
410 $stacksecondtop['type'] == 'SYNT_DEFINE'
411 )
412 {
413 // reduce!
414 array_pop ($stack);
415 array_pop ($stack);
416 array_push
417 (
418 $stack,
419 array
420 (
421 'type' => 'SYNT_DEFINITION',
a27a02c5 422 'term' => $stacksecondtop['load'],
bcd37231 423 'definition' => $stacktop['load']
1381b655
DO
424 )
425 );
426 continue;
427 }
428 if
429 (
a27a02c5 430 ($stacktop['type'] == 'SYNT_GRANT' or $stacktop['type'] == 'SYNT_DEFINITION') and
1381b655
DO
431 $stacksecondtop['type'] == 'SYNT_CODETEXT'
432 )
433 {
434 // reduce!
435 array_pop ($stack);
436 array_pop ($stack);
437 $stacksecondtop['load'][] = $stacktop;
438 array_push
439 (
440 $stack,
441 $stacksecondtop
442 );
443 continue;
444 }
445 if
446 (
a27a02c5
DO
447 $stacktop['type'] == 'SYNT_GRANT' or
448 $stacktop['type'] == 'SYNT_DEFINITION'
1381b655
DO
449 )
450 {
451 // reduce!
452 array_pop ($stack);
1381b655
DO
453 array_push
454 (
455 $stack,
456 array
457 (
458 'type' => 'SYNT_CODETEXT',
459 'load' => array ($stacktop)
460 )
461 );
462 continue;
463 }
464 }
465 // The fact we execute here means, that no reduction or early shift
466 // has been done. The only way to enter another iteration is to "shift"
467 // more, if possible. If the tape is empty, we are facing the
468 // "accept"/"reject" dilemma. The only possible way to "accept" is to
469 // have sole starting nonterminal on the stack (SYNT_CODETEXT).
470 if ($done < $todo)
471 {
472 array_push ($stack, $lexems[$done++]);
473 continue;
a1b88eca 474 }
1381b655
DO
475 // The moment of truth.
476 if (count ($stack) == 1 and $stack[0]['type'] == 'SYNT_CODETEXT')
cf25e649
DO
477 return array ('result' => 'ACK', 'load' => $stack[0]['load']);
478 return array ('result' => 'NAK', 'load' => 'Syntax error!');
a1b88eca 479 }
a1b88eca
DO
480}
481
bcd37231 482function eval_expression ($expr, $tagchain, $ptable)
a27a02c5 483{
bcd37231 484 switch ($expr['type'])
a27a02c5 485 {
bcd37231
DO
486 case 'LEX_TAG': // Return true, if given tag is present on the tag chain.
487 foreach ($tagchain as $tagInfo)
488 if ($expr['load'] == $tagInfo['tag'])
489 return TRUE;
a27a02c5 490 return FALSE;
bcd37231
DO
491 case 'LEX_PREDICATE': // Find given predicate in the symbol table and evaluate it.
492 $pname = $expr['load'];
493 if (!isset ($ptable[$pname]))
494 {
85a8ec3f 495 showError ("Predicate '${pname}' is referenced before declaration", __FUNCTION__);
bcd37231
DO
496 return;
497 }
498 return eval_expression ($ptable[$pname], $tagchain, $ptable);
85a8ec3f 499 case 'LEX_BOOLCONST': // Evaluate a boolean constant.
bcd37231
DO
500 switch ($expr['load'])
501 {
502 case 'true':
503 return TRUE;
504 case 'false':
505 return FALSE;
506 default:
85a8ec3f 507 showError ("Could not parse a boolean constant with value '${expr['load']}'", __FUNCTION__);
bcd37231
DO
508 return; // should failure be harder?
509 }
510 case 'SYNT_NOTEXPR':
511 return !eval_expression ($expr['load'], $tagchain, $ptable);
512 case 'SYNT_BOOLOP':
513 $leftresult = eval_expression ($expr['left'], $tagchain, $ptable);
514 switch ($expr['subtype'])
515 {
516 case 'or':
517 if ($leftresult)
518 return TRUE; // early success
519 return eval_expression ($expr['right'], $tagchain, $ptable);
520 case 'and':
521 if (!$leftresult)
522 return FALSE; // early failure
523 return eval_expression ($expr['right'], $tagchain, $ptable);
524 default:
525 showError ("Cannot evaluate unknown boolean operation '${boolop['subtype']}'");
526 return;
527 }
a27a02c5 528 default:
85a8ec3f 529 showError ("Evaluation error, cannot process expression type '${expr['type']}'", __FUNCTION__);
a27a02c5
DO
530 break;
531 }
532}
533
bcd37231 534function gotClearanceForTagChain ($tagchain)
a27a02c5 535{
bcd37231 536 global $rackCode;
a27a02c5 537 $ptable = array();
bcd37231 538 foreach ($rackCode as $sentence)
a27a02c5
DO
539 {
540 switch ($sentence['type'])
541 {
542 case 'SYNT_DEFINITION':
543 $ptable[$sentence['term']] = $sentence['definition'];
544 break;
545 case 'SYNT_GRANT':
546 if (eval_expression ($sentence['condition'], $tagchain, $ptable))
547 switch ($sentence['decision'])
548 {
549 case 'allow':
550 return TRUE;
551 case 'deny':
552 return FALSE;
553 default:
85a8ec3f 554 showError ("Condition match for unknown grant decision '${sentence['decision']}'", __FUNCTION__);
a27a02c5
DO
555 break;
556 }
bcd37231 557 break;
a27a02c5 558 default:
85a8ec3f 559 showError ("Can't process sentence of unknown type '${sentence['type']}'", __FUNCTION__);
a27a02c5
DO
560 break;
561 }
562 }
563 return FALSE;
564}
565
cf25e649 566function getRackCode ($text)
bcd37231 567{
cf25e649
DO
568 if (!mb_strlen ($text))
569 return array ('result' => 'NAK', 'load' => 'The RackCode text was found empty in ' . __FUNCTION__);
570 $text = str_replace ("\r", '', $text) . "\n";
571 $lex = getLexemsFromRackCode ($text);
572 if ($lex['result'] != 'ACK')
573 return $lex;
574 $synt = getSentencesFromLexems ($lex['load']);
575 if ($synt['result'] != 'ACK')
576 return $synt;
577 // An empty sentence list is semantically valid, yet senseless,
578 // so checking intermediate result once more won't hurt.
579 if (!count ($synt['load']))
580 return array ('result' => 'NAK', 'load' => 'Empty parse tree found in ' . __FUNCTION__);
581 return semanticFilter ($synt['load']);
bcd37231
DO
582}
583
3082e137
DO
584// Return NULL, if the given expression can be evaluated against the given
585// predicate list. Return the name of the first show stopper otherwise.
586function firstUnrefPredicate ($plist, $expr)
e6a4adb9
DO
587{
588 switch ($expr['type'])
589 {
85a8ec3f 590 case 'LEX_BOOLCONST':
e6a4adb9 591 case 'LEX_TAG':
3082e137 592 return NULL;
e6a4adb9 593 case 'LEX_PREDICATE':
3082e137 594 return in_array ($expr['load'], $plist) ? NULL : $expr['load'];
e6a4adb9 595 case 'SYNT_NOTEXPR':
3082e137 596 return firstUnrefPredicate ($plist, $expr['load']);
e6a4adb9 597 case 'SYNT_BOOLOP':
3082e137
DO
598 if (($tmp = firstUnrefPredicate ($plist, $expr['left'])) !== NULL)
599 return $tmp;
600 if (($tmp = firstUnrefPredicate ($plist, $expr['right'])) !== NULL)
601 return $tmp;
602 return NULL;
e6a4adb9 603 default:
3082e137 604 return NULL;
e6a4adb9
DO
605 }
606}
607
cf25e649 608function semanticFilter ($code)
e6a4adb9
DO
609{
610 $predicatelist = array();
611 foreach ($code as $sentence)
612 switch ($sentence['type'])
613 {
614 case 'SYNT_DEFINITION':
3082e137
DO
615 $up = firstUnrefPredicate ($predicatelist, $sentence['definition']);
616 if ($up !== NULL)
617 return array
618 (
619 'result' => 'NAK',
620 'load' => "definition [${sentence['term']}] uses unknown predicate [${up}]"
621 );
e6a4adb9
DO
622 $predicatelist[] = $sentence['term'];
623 break;
624 case 'SYNT_GRANT':
3082e137
DO
625 $up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
626 if ($up !== NULL)
627 return array
628 (
629 'result' => 'NAK',
630 'load' => "grant sentence uses unknown predicate [${up}]"
631 );
e6a4adb9
DO
632 break;
633 default:
cf25e649 634 return array ('result' => 'NAK', 'load' => 'unknown sentence type');
e6a4adb9 635 }
cf25e649 636 return array ('result' => 'ACK', 'load' => $code);
e6a4adb9
DO
637}
638
f63072f5 639?>