[racktables] / inc / code.php

<?php
/*
 * This file implements lexical scanner and syntax analyzer for the RackCode
 * access configuration language.
 *
 * The language consists of the following lexems:
 *
 * LEX_LBRACE
 * LEX_RBRACE
 * LEX_DECISION
 * LEX_DEFINE
 * LEX_BOOLCONST
 * LEX_NOT
 * LEX_TAG
 * LEX_PREDICATE
 * LEX_BOOLOP
 *
 */

// Complain about martian char.
function lexError1 ($state, $text, $pos)
{
	$message = "invalid char with code " . ord (mb_substr ($text, $pos, 1)) . ' (';
	$message .= mb_substr ($text, $pos, 1) . ") at position ${pos} (FSM state is '${state}')";
	return array ('result' => 'NAK', 'load' => $message);
}

// Complain about martian keyword.
function lexError2 ($word)
{
	return array
	(
		'result' => 'NAK',
		'load' => "could not parse keyword '${word}'"
	);
}

// Complain about wrong FSM state.
function lexError3 ($state)
{
	return array
	(
		'result' => 'NAK',
		'load' => "FSM state is still '${state}' at end of input"
	);
}

function lexError4 ($s)
{
	return array
	(
		'result' => 'NAK',
		'load' => "Invalid tag or predicate name '${s}'"
	);
}

// Produce a list of lexems from the given text. Possible lexems are:
function getLexemsFromRackCode ($text)
{
	$ret = array();
	$textlen = mb_strlen ($text);
	$state = "ESOTSM";
	for ($i = 0; $i < $textlen; $i++) :
		$char = mb_substr ($text, $i, 1);
		$newstate = $state;
		switch ($state) :
			case 'ESOTSM':
				switch (TRUE)
				{
					case ($char == '('):
						$ret[] = array ('type' => 'LEX_LBRACE');
						break;
					case ($char == ')'):
						$ret[] = array ('type' => 'LEX_RBRACE');
						break;
					case ($char == '#'):
						$newstate = 'skipping comment';
						break;
					case (mb_ereg ('[[:alpha:]]', $char) > 0):
						$newstate = 'reading keyword';
						$buffer = $char;
						break;
					case (preg_match ('/^[ \t\n\r]$/', $char)):
						// nom-nom...
						break;
					case ($char == '{'):
						$newstate = 'reading tag 1';
						break;
					case ($char == '['):
						$newstate = 'reading predicate 1';
						break;
					default:
						return lexError1 ($state, $text, $i);
				}
				break;
			case 'reading keyword':
				switch (TRUE)
				{
					case (mb_ereg ('[[:alpha:]]', $char) > 0):
						$buffer .= $char;
						break;
					case (preg_match ('/^[ \t\n]$/', $char)):
						// got a word, sort it out
						switch ($buffer)
						{
							case 'allow':
							case 'deny':
								$ret[] = array ('type' => 'LEX_DECISION', 'load' => $buffer);
								break;
							case 'define':
								$ret[] = array ('type' => 'LEX_DEFINE');
								break;
							case 'and':
							case 'or':
								$ret[] = array ('type' => 'LEX_BOOLOP', 'load' => $buffer);
								break;
							case 'not':
								$ret[] = array ('type' => 'LEX_NOT');
								break;
							case 'false':
							case 'true':
								$ret[] = array ('type' => 'LEX_BOOLCONST', 'load' => $buffer);
								break;
							default:
								return lexError2 ($buffer);
						}
						$newstate = 'ESOTSM';
						break;
					default:
						return lexError1 ($state, $text, $i);
				}
				break;
			case 'reading tag 1':
				switch (TRUE)
				{
					case (preg_match ('/^[ \t\n\r]$/', $char)):
						// nom-nom...
						break;
					case (mb_ereg ('[[:alnum:]\$]', $char) > 0):
						$buffer = $char;
						$newstate = 'reading tag 2';
						break;
					default:
						return lexError1 ($state, $text, $i);
				}
				break;
			case 'reading tag 2':
				switch (TRUE)
				{
					case ($char == '}'):
						$buffer = rtrim ($buffer);
						if (!validTagName ($buffer, TRUE))
							return lexError4 ($buffer);
						$ret[] = array ('type' => 'LEX_TAG', 'load' => $buffer);
						$newstate = 'ESOTSM';
						break;
					case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
						$buffer .= $char;
						break;
					default:
						return lexError1 ($state, $text, $i);
				}
				break;
			case 'reading predicate 1':
				switch (TRUE)
				{
					case (preg_match ('/^[ \t\n\r]$/', $char)):
						// nom-nom...
						break;
					case (mb_ereg ('[[:alnum:]]', $char) > 0):
						$buffer = $char;
						$newstate = 'reading predicate 2';
						break;
					default:
						return lexError1 ($state, $text, $i);
				}
				break;
			case 'reading predicate 2':
				switch (TRUE)
				{
					case ($char == ']'):
						$buffer = rtrim ($buffer);
						if (!validTagName ($buffer))
							return lexError4 ($buffer);
						$ret[] = array ('type' => 'LEX_PREDICATE', 'load' => $buffer);
						$newstate = 'ESOTSM';
						break;
					case (mb_ereg ('[[:alnum:]\. _~-]', $char) > 0):
						$buffer .= $char;
						break;
					default:
						return lexError1 ($state, $text, $i);
				}
				break;
			case 'skipping comment':
				switch ($char)
				{
					case "\n":
						$newstate = 'ESOTSM';
					default: // eat char, nom-nom...
						break;
				}
				break;
			default:
				die (__FUNCTION__ . "(): internal error, state == ${state}");
		endswitch;
		$state = $newstate;
	endfor;
	if ($state != 'ESOTSM' and $state != 'skipping comment')
		return lexError3 ($state);
	return array ('result' => 'ACK', 'load' => $ret);
}

// Parse the given lexems stream into a list of RackCode sentences. Each such
// sentence is a syntax tree, suitable for tag sequence evaluation. The final
// parse tree may contain the following nodes:
// LEX_TAG
// LEX_PREDICATE
// LEX_BOOLCONST
// SYNT_NOT (1 argument, holding SYNT_EXPR)
// SYNT_BOOLOP (2 arguments, each holding SYNT_EXPR)
// SYNT_DEFINITION (2 arguments: term and definition)
// SYNT_GRANT (2 arguments: decision and condition)
// SYNT_CODETEXT (sequence of sentences)
//
// After parsing the input successfully a list of SYNT_GRANT and SYNT_DEFINITION
// trees is returned.
function getSentencesFromLexems ($lexems)
{
	$stack = array(); // subject to array_push() and array_pop()
	$done = 0; // $lexems[$done] is the next item in the tape
	$todo = count ($lexems);

	// Perform shift-reduce processing. The "accept" actions occurs with an
	// empty input tape and the stack holding only one symbol (the start
	// symbol, SYNT_CODETEXT).
	while (TRUE)
	{
		$stacktop = $stacksecondtop = $stackthirdtop = array ('type' => 'null');
		$stacksize = count ($stack);
		if ($stacksize >= 1)
		{
			$stacktop = array_pop ($stack);
			// It is possible to run into a S/R conflict, when having a syntaxically
			// correct sentence base on the stack and some "and {something}" items
			// on the input tape, hence let's detect this specific case and insist
			// on "shift" action to make EXPR parsing hungry one.
			if
			(
				$stacktop['type'] == 'SYNT_EXPR' and
				($done < $todo) and 
				$lexems[$done]['type'] == 'LEX_BOOLOP'
			)
			{
				// shift!
				array_push ($stack, $stacktop);
				array_push ($stack, $lexems[$done++]);
				continue;
			}
			if ($stacksize >= 2)
			{
				$stacksecondtop = array_pop ($stack);
				if ($stacksize >= 3)
				{
					$stackthirdtop = array_pop ($stack);
					array_push ($stack, $stackthirdtop);
				}
				array_push ($stack, $stacksecondtop);
			}
			array_push ($stack, $stacktop);
			// First detect definition start to save the predicate from being reduced into
			// expression.
			if
			(
				$stacktop['type'] == 'LEX_PREDICATE' and
				$stacksecondtop['type'] == 'LEX_DEFINE'
			)
			{
				array_pop ($stack);
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_DEFINE',
						'load' => $stacktop['load']
					)
				);
				continue;
			}
			// Try "replace" action only on a non-empty stack.
			// If a handle is found for reversing a production rule, do it and start a new
			// cycle instead of advancing further on rule list. This will preserve rule priority
			// in the grammar and keep us from an extra shift action.
			if
			(
				$stacktop['type'] == 'LEX_BOOLCONST' or
				$stacktop['type'] == 'LEX_TAG' or
				$stacktop['type'] == 'LEX_PREDICATE'
			)
			{
				// reduce!
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_EXPR',
						'load' => $stacktop
					)
				);
				continue;
			}
			if
			(
				$stacktop['type'] == 'SYNT_EXPR' and
				$stacksecondtop['type'] == 'LEX_NOT'
			)
			{
				// reduce!
				array_pop ($stack);
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_EXPR',
						'load' => array
						(
							'type' => 'SYNT_NOTEXPR',
							'load' => $stacktop['load']
						)
					)
				);
				continue;
			}
			if
			(
				$stacktop['type'] == 'LEX_RBRACE' and
				$stacksecondtop['type'] == 'SYNT_EXPR' and
				$stackthirdtop['type'] == 'LEX_LBRACE'
			)
			{
				// reduce!
				array_pop ($stack);
				array_pop ($stack);
				array_pop ($stack);
				array_push
				(
					$stack,
					$stacksecondtop
				);
				continue;
			}
			if
			(
				$stacktop['type'] == 'SYNT_EXPR' and
				$stacksecondtop['type'] == 'LEX_BOOLOP' and
				$stackthirdtop['type'] == 'SYNT_EXPR'
			)
			{
				// reduce!
				array_pop ($stack);
				array_pop ($stack);
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_EXPR',
						'load' => array
						(
							'type' => 'SYNT_BOOLOP',
							'subtype' => $stacksecondtop['load'],
							'left' => $stackthirdtop['load'],
							'right' => $stacktop['load']
						)
					)
				);
				continue;
			}
			if
			(
				$stacktop['type'] == 'SYNT_EXPR' and
				$stacksecondtop['type'] == 'LEX_DECISION'
			)
			{
				// reduce!
				array_pop ($stack);
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_GRANT',
						'decision' => $stacksecondtop['load'],
						'condition' => $stacktop['load']
					)
				);
				continue;
			}
			if
			(
				$stacktop['type'] == 'SYNT_EXPR' and
				$stacksecondtop['type'] == 'SYNT_DEFINE'
			)
			{
				// reduce!
				array_pop ($stack);
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_DEFINITION',
						'term' => $stacksecondtop['load'],
						'definition' => $stacktop['load']
					)
				);
				continue;
			}
			if
			(
				($stacktop['type'] == 'SYNT_GRANT' or $stacktop['type'] == 'SYNT_DEFINITION') and
				$stacksecondtop['type'] == 'SYNT_CODETEXT'
			)
			{
				// reduce!
				array_pop ($stack);
				array_pop ($stack);
				$stacksecondtop['load'][] = $stacktop;
				array_push
				(
					$stack,
					$stacksecondtop
				);
				continue;
			}
			if
			(
				$stacktop['type'] == 'SYNT_GRANT' or
				$stacktop['type'] == 'SYNT_DEFINITION'
			)
			{
				// reduce!
				array_pop ($stack);
				array_push
				(
					$stack,
					array
					(
						'type' => 'SYNT_CODETEXT',
						'load' => array ($stacktop)
					)
				);
				continue;
			}
		}
		// The fact we execute here means, that no reduction or early shift
		// has been done. The only way to enter another iteration is to "shift"
		// more, if possible. If the tape is empty, we are facing the
		// "accept"/"reject" dilemma. The only possible way to "accept" is to
		// have sole starting nonterminal on the stack (SYNT_CODETEXT).
		if ($done < $todo)
		{
			array_push ($stack, $lexems[$done++]);
			continue;
		}
		// The moment of truth.
		if (count ($stack) == 1 and $stack[0]['type'] == 'SYNT_CODETEXT')
			return array ('result' => 'ACK', 'load' => $stack[0]['load']);
		return array ('result' => 'NAK', 'load' => 'Syntax error!');
	}
}

function eval_expression ($expr, $tagchain, $ptable)
{
	switch ($expr['type'])
	{
		case 'LEX_TAG': // Return true, if given tag is present on the tag chain.
			foreach ($tagchain as $tagInfo)
				if ($expr['load'] == $tagInfo['tag'])
					return TRUE;
			return FALSE;
		case 'LEX_PREDICATE': // Find given predicate in the symbol table and evaluate it.
			$pname = $expr['load'];
			if (!isset ($ptable[$pname]))
			{
				showError ("Predicate '${pname}' is referenced before declaration", __FUNCTION__);
				return;
			}
			return eval_expression ($ptable[$pname], $tagchain, $ptable);
		case 'LEX_BOOLCONST': // Evaluate a boolean constant.
			switch ($expr['load'])
			{
				case 'true':
					return TRUE;
				case 'false':
					return FALSE;
				default:
					showError ("Could not parse a boolean constant with value '${expr['load']}'", __FUNCTION__);
					return; // should failure be harder?
			}
		case 'SYNT_NOTEXPR':
			return !eval_expression ($expr['load'], $tagchain, $ptable);
		case 'SYNT_BOOLOP':
			$leftresult = eval_expression ($expr['left'], $tagchain, $ptable);
			switch ($expr['subtype'])
			{
				case 'or':
					if ($leftresult)
						return TRUE; // early success
					return eval_expression ($expr['right'], $tagchain, $ptable);
				case 'and':
					if (!$leftresult)
						return FALSE; // early failure
					return eval_expression ($expr['right'], $tagchain, $ptable);
				default:
					showError ("Cannot evaluate unknown boolean operation '${boolop['subtype']}'");
					return;
			}
		default:
			showError ("Evaluation error, cannot process expression type '${expr['type']}'", __FUNCTION__);
			break;
	}
}

function gotClearanceForTagChain ($tagchain)
{
	global $rackCode;
	$ptable = array();
	foreach ($rackCode as $sentence)
	{
		switch ($sentence['type'])
		{
			case 'SYNT_DEFINITION':
				$ptable[$sentence['term']] = $sentence['definition'];
				break;
			case 'SYNT_GRANT':
				if (eval_expression ($sentence['condition'], $tagchain, $ptable))
					switch ($sentence['decision'])
					{
						case 'allow':
							return TRUE;
						case 'deny':
							return FALSE;
						default:
							showError ("Condition match for unknown grant decision '${sentence['decision']}'", __FUNCTION__);
							break;
					}
				break;
			default:
				showError ("Can't process sentence of unknown type '${sentence['type']}'", __FUNCTION__);
				break;
		}
	}
	return FALSE;
}

function getRackCode ($text)
{
	if (!mb_strlen ($text))
		return array ('result' => 'NAK', 'load' => 'The RackCode text was found empty in ' . __FUNCTION__);
	$text = str_replace ("\r", '', $text) . "\n";
	$lex = getLexemsFromRackCode ($text);
	if ($lex['result'] != 'ACK')
		return $lex;
	$synt = getSentencesFromLexems ($lex['load']);
	if ($synt['result'] != 'ACK')
		return $synt;
	// An empty sentence list is semantically valid, yet senseless,
	// so checking intermediate result once more won't hurt.
	if (!count ($synt['load']))
		return array ('result' => 'NAK', 'load' => 'Empty parse tree found in ' . __FUNCTION__);
	return semanticFilter ($synt['load']);
}

// Return NULL, if the given expression can be evaluated against the given
// predicate list. Return the name of the first show stopper otherwise.
function firstUnrefPredicate ($plist, $expr)
{
	switch ($expr['type'])
	{
		case 'LEX_BOOLCONST':
		case 'LEX_TAG':
			return NULL;
		case 'LEX_PREDICATE':
			return in_array ($expr['load'], $plist) ? NULL : $expr['load'];
		case 'SYNT_NOTEXPR':
			return firstUnrefPredicate ($plist, $expr['load']);
		case 'SYNT_BOOLOP':
			if (($tmp = firstUnrefPredicate ($plist, $expr['left'])) !== NULL)
				return $tmp;
			if (($tmp = firstUnrefPredicate ($plist, $expr['right'])) !== NULL)
				return $tmp;
			return NULL;
		default:
			return NULL;
	}
}

function semanticFilter ($code)
{
	$predicatelist = array();
	foreach ($code as $sentence)
		switch ($sentence['type'])
		{
			case 'SYNT_DEFINITION':
				$up = firstUnrefPredicate ($predicatelist, $sentence['definition']);
				if ($up !== NULL)
					return array
					(
						'result' => 'NAK',
						'load' => "definition [${sentence['term']}] uses unknown predicate [${up}]"
					);
				$predicatelist[] = $sentence['term'];
				break;
			case 'SYNT_GRANT':
				$up = firstUnrefPredicate ($predicatelist, $sentence['condition']);
				if ($up !== NULL)
					return array
					(
						'result' => 'NAK',
						'load' => "grant sentence uses unknown predicate [${up}]"
					);
				break;
			default:
				return array ('result' => 'NAK', 'load' => 'unknown sentence type');
		}
	return array ('result' => 'ACK', 'load' => $code);
}

?>
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
f63072f5 DO	20	// Complain about martian char.
9f54e6e9	21	function lexError1 ($state, $text, $pos)
f63072f5	22	{
23818dde DO	23	$message = "invalid char with code " . ord (mb_substr ($text, $pos, 1)) . ' (';
23818dde DO	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	29	function lexError2 ($word)
f63072f5	30	{
cf25e649 DO	31	return array
	32	(
	33	'result' => 'NAK',
	34	'load' => "could not parse keyword '${word}'"
	35	);
f63072f5 DO	36	}
f63072f5 DO	37
a1b88eca	38	// Complain about wrong FSM state.
9f54e6e9	39	function 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	}
a1b88eca DO	47
9f54e6e9 DO	48	function 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:
a1b88eca DO	58	function getLexemsFromRackCode ($text)
f63072f5 DO	59	{
f63072f5 DO	60	$ret = array();
bcd49780	61	$textlen = mb_strlen ($text);
f63072f5 DO	62	$state = "ESOTSM";
f63072f5 DO	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;
f63072f5 DO	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;
f63072f5 DO	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	}
f63072f5 DO	95	break;
cf25e649	96	case 'reading keyword':
f63072f5 DO	97	switch (TRUE)
f63072f5 DO	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;
f63072f5 DO	110	case 'define':
a1b88eca	111	$ret[] = array ('type' => 'LEX_DEFINE');
f63072f5 DO	112	break;
f63072f5 DO	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;
f63072f5 DO	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...
f63072f5 DO	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))
9f54e6e9 DO	153	return lexError4 ($buffer);
e5bd52e5	154	$ret[] = array ('type' => 'LEX_TAG', 'load' => $buffer);
f63072f5 DO	155	$newstate = 'ESOTSM';
f63072f5 DO	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...
f63072f5 DO	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))
9f54e6e9 DO	184	return lexError4 ($buffer);
e5bd52e5	185	$ret[] = array ('type' => 'LEX_PREDICATE', 'load' => $buffer);
f63072f5 DO	186	$newstate = 'ESOTSM';
f63072f5 DO	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	}
f63072f5 DO	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)
e5bd52e5 DO	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	228	function getSentencesFromLexems ($lexems)
a1b88eca DO	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'],
a27a02c5 DO	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
a27a02c5 DO	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.
1381b655 DO	476	if (count ($stack) == 1 and $stack[0]['type'] == 'SYNT_CODETEXT')
cf25e649 DO	477	return array ('result' => 'ACK', 'load' => $stack[0]['load']);
cf25e649 DO	478	return array ('result' => 'NAK', 'load' => 'Syntax error!');
a1b88eca	479	}
a1b88eca DO	480	}
a1b88eca DO	481
bcd37231	482	function 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	534	function 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;
a27a02c5 DO	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	566	function 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	}
bcd37231 DO	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.
	586	function 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	608	function 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;
e6a4adb9 DO	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	}
e6a4adb9 DO	638
f63072f5	639	?>