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