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