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