It wasn't until recently I started thinking on this subject again. Even though the functionality serves its purpose I wasn't entirely happy with the way it worked. The form element that is used to interact with the serialized predicates feels a bit clunky. And then there is the limitation of two operands (user rights) per operator. This makes it all somewhat harder to use, especially with more elaborate predicates. It did prove, however, to be an excellent starting point for a somewhat more elegant solution.
The WIKI page on Polish notation mentions the following:
Assuming a given arity of all involved operators ... any well formed prefix representation thereof is unambiguous, and brackets within the prefix expression are unnecessary.
This does not say the arity needs to be fixed, it just needs to be known. The easiest way to accomplish that is to simply tell the operator on how many operands it should be applied to.
Let's take the example from the previous article and spice it up a bit:
AND--+--1 | +--OR--+--2 | | | +--NOT--3 | +--4
The AND operator now operates on three items (either operators or operands) instead of two. The OR operator still operates on two items, but that number is no longer set in stone. The NOT operator still operates on exactly one item. It would also make no sense to have AND and OR operators act upon a single item. So it might be wise to keep in mind that some restrictions still may apply.
We set the arity of the operator by adding a numerical suffix that indicates the number of operators and operands that operator should act upon. We also need some kind of symbol to separate the two. For this purpose we use a colon ( : ). All operators need to take this approach since the arity is no longer bound by the type of operator. Even for the NOT operand this kind of makes sense (even though the count will always be one) because that way we can use the same approach for all operators which is more efficient when identifying an operator token.
Our new serialized expression, based on the above example and with the incorporation of arities, now becomes:
&:3,1,|:2,2,!:1,3,4
Before we (re)create, along other functionality, a function for evaluating this new expression format against a set of granted rights it is very important to keep performance in mind. It is also very important to ensure that we do not try to evaluate incorrect or illegal formats.
However, this syntactical and semantical validation check does not have to take place each time we try to evaluate an expression. As before, as long as we validate the expression somewhere before we start using it we are good. A good moment to validate an expression would be before storing it alongside the resource we are trying to protect. This will push somewhat more elaborate (and more expensive) checks out of the code that needs to stay lean and mean in order to keep evaluation as fast as possible.
So we are back where we started with our evaluation function.
1 2 3 4 5 6
<?php
// @return bool indicating whether a user with $rights is allowed access based on $expression
function isAllowed($expression, $rights) {
// do magic
}
?>
First we will just lay out the code, and then explain what's what.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
<?php
function isAllowed($expression, $rights) {
if ($expression == '') {
return true;
}
$stack = [];
foreach (array_reverse(explode(',', $expression)) as $token) {
if (isset($token[1]) && $token[1] == ':') {
$args = [];
$operator = substr($token, 0, 1);
$count = substr($token, 2);
while ($count--) {
$args[] = array_pop($stack);
}
switch ($operator) {
case '&':
foreach ($args as $val) {
if (!$val) {
$stack[] = false;
break 2;
}
}
$stack[] = true;
break;
case '|':
foreach ($args as $val) {
if ($val) {
$stack[] = true;
break 2;
}
}
$stack[] = false;
break;
case '!':
$stack[] = !$args[0];
break;
}
} else {
$stack[] = isset($rights[$token]);
}
}
return $stack[0];
}
?>
Note that isAllowed()
still operates under the assumption that $expression
is a valid serialized expression.
The isAllowed()
function is roughly the same as before, the only thing that changed is the appearance of the operator token which now consists of an operator symbol and a count part. Also, instead of a fixed number we pop $count
items from the stack and process these, depending on the operator, in the switch-statement to calculate the intermediate boolean result to put back on the stack.
Finally, as before, we return the single remaining value on the stack.
A decent amount of consideration, mainly concerning performance, led to this semi final form. Semi, because I am still tinkering with it :). Decisions were mainly based on some quick benchmarks, so results may vary on different systems.
Because the AND and OR operators can now take any number of arguments (at least two) the calculation of the end result has slightly changed. At first, this appeared hard but in practise it proved really simple. We can even use some lazy evaluation. We will discuss both snippets in turn.
1 2 3 4 5 6 7 8 9 10 11
<?php
case '&':
foreach ($args as $val) {
if (!$val) {
$stack[] = false;
break 2;
}
}
$stack[] = true;
break;
?>
When we evaluate a set of booleans that use the AND operator, all booleans must be true for the result to be true. This could be compared to the universal quantifier ∀. If we find a member that is false we are done. We both terminate the foreach loop and further execution of the case statement with break 2;
. Otherwise, when all items have been traversed, this means all members were true and this is the only case where the end result is actually true.
1 2 3 4 5 6 7 8 9 10 11
<?php
case '|':
foreach ($args as $val) {
if ($val) {
$stack[] = true;
break 2;
}
}
$stack[] = false;
break;
?>
This could be compared to the existential comparison ∃. As soon as we find a member that is true, we are done. Once again we terminate the foreach loop and further execution of the case statement with break 2;
. If we traversed all items and found nothing, the end result will be false.
Adding more operators involves coming up with a unique symbol, writing a new case and doing something similar for the JavaScript part of this functionality which we will discuss later.
The code above can be tweaked further still. The part that deals with an operator (lines 9-37) could be rewritten to:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
<?php
switch (substr($token, 0, 1)) {
case '!':
$result = !array_pop($stack);
break;
case '&':
$result = true;
for ($i = substr($token, 2); $i > 0; $i--) {
if (!array_pop($stack)) {
$result = false;
}
}
break;
case '|':
$result = false;
for ($i = substr($token, 2); $i > 0; $i--) {
if (array_pop($stack)) {
$result = true;
}
}
break;
}
$stack[] = $result;
?>
In this variant we have done away with the $args
helper array. This should result in less writes and with it a (albeit slight) speed increase. Note that in this variant we cannot break early because $stack
still needs to be reduced a specific amount of items (the arity of the operator). The only real difference is that the calculation of the end result was done on the fly.
Let's test this functionality using our previous example. It might be worthwhile to make a truth table to keep track of what outcome calls to isAllowed()
should have with different combinations of granted rights.
4 3 2 1 | AND(1,OR(2,NOT(3)),4) ----------------+----------------------- 0 0 0 0 | 0 0 0 0 1 | 0 0 0 1 0 | 0 0 0 1 1 | 0 0 1 0 0 | 0 0 1 0 1 | 0 0 1 1 0 | 0 0 1 1 1 | 0 1 0 0 0 | 0 1 0 0 1 | 1 1 0 1 0 | 0 1 0 1 1 | 1 1 1 0 0 | 0 1 1 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 1
We use some rights combinations to test this functionality.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
<?php
$myRights = array(
4 => true,
);
if (isAllowed($expression, $myRights)) {
echo '[error] rights: 4; should not be allowed<br />';
} else {
echo 'rights: 4; not allowed<br />';
}
$myRights = array(
1 => true,
3 => true,
);
if (isAllowed($expression, $myRights)) {
echo '[error] rights: 1, 3; should not be allowed<br />';
} else {
echo 'rights: 1,3; not allowed<br />';
}
$myRights = array(
1 => true,
4 => true,
);
if (isAllowed($expression, $myRights)) {
echo 'rights: 1,4; is allowed<br />';
} else {
echo '[error] rights: 1,4; should be allowed<br />';
}
$myRights = array(
2 => true,
4 => true,
);
if (isAllowed($expression, $myRights)) {
echo '[error] rights: 2,4; should not be allowed<br />';
} else {
echo 'rights: 2,4; not allowed<br />';
}
$myRights = array(
1 => true,
2 => true,
3 => true,
);
if (isAllowed($expression, $myRights)) {
echo '[error] rights: 1,2,3; should not be allowed<br />';
} else {
echo 'rights: 1,2,3; not allowed<br />';
}
?>
This outputs:
rights: 4; not allowed rights: 1,3; not allowed rights: 1,4; is allowed rights: 2,4; not allowed rights: 1,2,3; not allowed
We are back to the actual hard part: building a new expression in a user friendly way. This time around I tried to create a form element where a user only has to do some (or maybe a lot) of clicking.
We make use of jQuery (built with version 3.3.1, not really tested for backwards compatibility but it should be fine) for some DOM-management. The same principle is applied as before: we edit a bulleted list and put the resulting serialized expression in a hidden input field. The functionality is also once again set up such that you can easily reuse the code to quickly create multiple form elements.
First off, the JavaScript for using the rights tree:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
function Rights() {
this.$container = false;
this.$tree = false;
this.$output = false;
this.operators = {};
this.rights = {};
var that = this;
this.init = function(options) {
this.$container = $('#'+options.container);
this.$tree = this.$container.find('ul:first');
this.$output = $('#'+options.output);
this.operators = options.operators;
this.rights = options.rights;
this.$tree.on('click', 'a.js-add-operand', function(e) {
var html =
'<li class="operand">\
<span style="display: none;"></span>\
<select>\
<option value="">- select -</option>';
for (i in that.rights) {
html += '<option value="'+i+'">'+that.rights[i]+'</option>';
}
html +=
'</select>\
<a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>\
<span class="message"></span>\
</li>';
$(this).parent().before(html);
if ($(this).parent().hasClass('js-first-level')) {
$(this).parent().hide();
}
that.generateOutput();
});
this.$tree.on('click', 'a.js-add-operator', function(e) {
var html =
'<li class="operator">\
<span style="display: none;"></span>\
<select>\
<option value="">- select -</option>'
for (i in that.operators) {
html += '<option value="'+i+'">'+that.operators[i]+'</option>';
}
html +=
'</select>\
<a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>\
<span class="message"></span>\
<ul>\
<li class="add"><a class="button js-add-operator" href="javascript:void(0)">+operator</a><a class="button js-add-operand" href="javascript:void(0)">+right</a></li>\
</ul>\
</li>';
$(this).parent().before(html);
if ($(this).parent().hasClass('js-first-level')) {
$(this).parent().hide();
}
that.generateOutput();
});
this.$tree.on('click', 'a.js-remove', function(e) {
$(this).parent().remove();
if (that.$tree.find('> li').length == 1) {
that.$tree.find('li.js-first-level').show();
}
that.generateOutput();
});
this.$tree.on('click', 'a.js-edit', function(e) {
var $span = $(this).parent().children(':first');
var $select = $span.next();
var value = $span.attr('data-value');
if ($select.is(':visible') === false) {
if ($span.attr('data-value')) {
$select.find("option[value='"+value+"']").prop('selected', true);
}
} else {
if (typeof value === 'undefined') {
$span.html('<i class="error">empty</i>');
}
}
$span.toggle();
$select.toggle();
});
this.$tree.on('change', 'select', function(e) {
var $span = $(this).prev();
if ($(this).val()) {
$span.attr('data-value', $(this).val());
$span.html($(this).find('option:selected').text());
$span.toggle();
$(this).toggle();
that.generateOutput();
}
});
this.$container.find('a.js-toggle').click(function(e) {
that.$tree.find('span').show();
that.$tree.find('select').hide();
that.$tree.find('li.add').toggle();
if (that.$tree.find('> li').length > 1) {
that.$tree.find('li.js-first-level').hide();
}
that.$tree.find('a.js-edit').toggle();
that.$tree.find('a.js-remove').toggle();
that.$tree.find('li').find('span:first').each(function() {
if (typeof $(this).attr('data-value') === 'undefined') {
$(this).html('<i class="error">empty</i>');
}
});
});
this.$tree.on({
'mouseenter': function() {
$(this).parent().addClass('delete');
},
'mouseleave': function() {
$(this).parent().removeClass('delete');
}
}, 'a.js-remove');
} // init
this.generateOutput = function() {
var out = '';
this.$tree.find('li').each(function() {
if ($(this).hasClass('operator')) {
$span = $(this).children(':first');
var value = $span.attr('data-value');
if (false === (value in that.operators)) {
value = 'O'; // placeholder value for operator
}
var children = $(this).find('> ul > li.operator').length + $(this).find('> ul > li.operand').length;
out = out + (out == '' ? '' : ',') + value + ':' + children;
} else if ($(this).hasClass('operand')) {
$span = $(this).children(':first');
var value = $span.attr('data-value');
value = parseInt(value);
if (isNaN(value)) {
value = 'R'; // placeholder value for right
}
out = out + (out == '' ? '' : ',') + value;
}
});
this.$output.val(out);
}
} // function Rights
Then some CSS for styling everything:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
@CHARSET "UTF-8";
div.rights { font-family: sans-serif; font-size: 10pt; color: #000000; }
div.rights ul.tree li { line-height: 25px; list-style: disc; }
div.rights ul.tree span { font-weight: bold; }
div.rights a.button { color: #000000; background-color: #ffcccc; border-radius: 5px; font-weight: bold; text-decoration: none; padding: 2px 5px; margin-left: 5px; line-height: 25px; }
div.rights a.button:hover { background-color: #ffaaaa; }
div.rights ul.tree .delete span { color: #ff0000; }
div.rights ul.tree .delete select { color: #ff0000; }
div.rights ul.tree .delete i { color: #ff0000; }
div.rights ul.tree .delete a { color: #ff0000; }
div.rights ul.tree .delete li { color: #ff0000; }
div.rights ul.tree li.delete { color: #ff0000; }
div.rights ul.tree span.message { font-weight: normal; font-style: italic; margin-left: 5px; color: #ff0000; }
div.rights ul.tree .error { color: #ff0000; }
div.rights div.toggle { padding: 5px 0; }
div.rights div.validation { width: 300px; border-radius: 15px; padding: 5px; font-weight: bold; text-align: center; }
div.rights div.pass { background-color: #ccffcc; }
div.rights div.fail { background-color: #ffcccc; }
To create a form element, simply write some minimal HTML and instantiate a Rights object with appropriate values. If you have some kind of naming scheme for your form elements this can help organise your form data as well. For example, use the following HTML:
1 2 3 4 5 6 7
<div class="rights" id="rights">
<ul class="tree">
<li class="add js-first-level"><a class="button js-add-operator" href="javascript:void(0)">+operator</a><a class="button js-add-operand" href="javascript:void(0)">+right</a></li>
</ul>
<div class="toggle"><a href="javascript:void(0)" class="button js-toggle">toggle</a></div>
<input type="text" name="expression" id="rights_out" value="" size="50" autocomplete="off">
</div>
And hook up the Rights functionality with the following code:
1 2 3 4 5 6 7 8
<script type="text/javascript">
//<![CDATA[
$().ready(function() {
var rights = new Rights();
rights.init({'container': 'rights', 'output': 'rights_out', 'operators': {"&":"AND","|":"OR","!":"NOT"}, 'rights': {"1":"one","2":"two","3":"three","4":"four"}});
});
//]]>
</script>
In a similar fashion you can create as many Rights elements as you like.
The above code can be combined to create a working form element. If we use our example from the start of the article we can create something like this:
Because the expressions are more flexible than before, there is also a lot more that can go wrong. It is for this reason we make our validation function more verbose.
Besides checking validity of the expression it will try and do its best to point the user towards any errors that may occur. Obviously, the people using this functionality need to have some understanding of how this works to be able to use these form elements.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
<?php
function validate($expression, $validOperators, $validRights=[]) {
if ($expression == '') {
return array('valid' => true);
}
$stack = [];
$tokens = array_reverse(explode(',', $expression));
$tokenIndex = count($tokens);
// First pass: syntax
foreach ($tokens as $token) {
$isRight = isRight($token);
$isOperator = isOperator($token);
if ($isRight === false && $isOperator === false) {
return array(
'valid' => false,
'syntaxErrors' => true,
'errors' => array(
0 => 'could not identify token as either a right id or valid operator on index '.$tokenIndex,
),
);
}
if ($isOperator) {
list($operator, $count) = explode(':', $token);
if (count($stack) < $count) {
return array(
'valid' => false,
'syntaxErrors' => true,
'errors' => array(
0 => 'ran out of rights to inspect for operator on index '.$tokenIndex,
),
);
}
$args = [];
for ($i=0; $i < $count; $i++) {
$args[] = array_pop($stack);
}
}
$stack[] = false; // just put some result boolean back on the stack
$tokenIndex--;
}
if (count($stack) != 1) {
return array(
'valid' => false,
'syntaxErrors' => true,
'errors' => array(
0 => 'too many rights left on stack; if you have multiple rights on a level an operator should always encapsulate these',
),
);
}
// Second pass: semantics
$tokenIndex = count($tokens);
$return = array(
'valid' => false,
'syntaxErrors' => false,
'errors' => array(),
);
foreach ($tokens as $token) {
if (strpos($token, ':') == 1) {
// operator
list($operator, $count) = explode(':', $token);
// when you extend this functionality with your own operators you need to add them to $operatorMap
if (array_key_exists($operator, $validOperators) === false) {
$return['errors'][$tokenIndex] = 'operator not set or unknown';
}
switch ($operator) {
case '&':
case '|':
if ($count < 2) {
$return['errors'][$tokenIndex] = 'illegal item count for '.$validOperators[$operator].' operator, need at least two';
}
break;
case '!':
if ($count != 1) {
$return['errors'][$tokenIndex] = 'illegal item count for NOT operator, need exactly one';
}
break;
}
} else {
// right
if (count($validRights) > 0) {
if (isset($validRights[$token]) === false) {
$return['errors'][$tokenIndex] = 'invalid right id';
}
}
if (isIndex($token) === false) {
$return['errors'][$tokenIndex] = 'right not set';
}
}
$tokenIndex--;
}
if (count($return['errors']) == 0) {
$return['valid'] = true;
}
return $return;
}
?>
This function also uses the following helper functions:
1 2 3 4 5 6 7 8 9 10 11 12 13
<?php
function isOperator($in) {
return preg_match('#^\D\:(0|[1-9][0-9]*)$#', $in) === 1;
}
function isIndex($in) {
return preg_match('#^[1-9][0-9]*$#', $in) === 1;
}
function isRight($in) {
return preg_match('#^(R|[1-9][0-9]*)$#', $in) === 1;
}
?>
Note that both isOperator()
and isRight()
only check if the format of the associated tokens is correct, but not explicitly if the values (operator symbols and right ids) are valid. So these are lenient rudimentary checks to help determine whether the expression is syntactically valid, or at least, "good enough" to build or continue building the tree. The operator symbols and optionally specific right ids are of course explicitly checked at some point.
The validate()
function is split into two parts. First of all a syntactical pass is performed. This is to ensure that the expression is at least syntactically correct so we are able to render a correct, albeit perhaps incomplete, tree. Any errors will break off further execution of the function. This is done because once an error of this kind is detected this means the expression is invalid and beyond repairing. This also means it can no longer be guaranteed the tree can be rendered correctly. Passing this part of the validation still does not guarantee a valid expression, but it at least is an expression we can work with.
This part checks:
The second part performs a semantical pass. Here we finalize all the checks to guarantee we are dealing with a valid expression. If we have gotten past the first part this means we are at least dealing with a syntactically correct, but perhaps incomplete, expression. So in that sense, there is no real need to halt on the first encountered error. Rather, we can validate the entire expression and return all errors we come across. This further enables the user to fix all remaining semantical errors in one go.
This part checks:
$validOperators
parameter$validRights
Finally, when no errors occurred, the valid
key will be set to true.
On a side note, all the JavaScript functionality should assist you to steer clear from the syntax errors, so you should never be able to create a syntactically incorrect tree by just clicking on buttons effectively locking you out of editing.
If the valid
index of the returned array is false this means the expression is invalid. In this case the expression should not be used to evaluate user rights. It is also strongly discouraged to somehow store invalid expressions. Ideally you should always establish the expression is valid before passing it to isAllowed()
.
As pointed out before isAllowed()
operates under the assumption the expression is valid. If you try to evaluate a malformed expression there is no telling what will happen. Worst case isAllowed()
will return true when it really, really shouldn't.
If the valid
index is false the returned array will also come with a syntaxErrors
and errors
index. The syntaxErrors
index contains a boolean indicating whether syntactical errors occurred. This also functions as a handbrake before rendering the tree. The errors
index will contain an array with one or more key-value pairs of a token index (if applicable) mapped to the error that occurred on that index.
It is probably best that you make sure that when you store an expression, it is valid. Then, when you edit it again it will render correctly.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
<?php
function printTree($expression, $operators, $rights, $messages=array()) {
?><ul class="tree"><?php
if (empty($expression) === false) {
$stack = [0 => 1]; // depth => #items
$index = 1;
$level = 0;
foreach (explode(',', $expression) as $token) {
if (strpos($token, ':') == 1) {
// operator
list($operator, $count) = explode(':', $token);
$stack[$level]--;
$level++;
$stack[$level] = (int) $count;
if (isset($operators[$operator])) {
$operatorValue = $operator;
$operatorHTML = escape($operators[$operator]);
} else {
$operatorValue = 'O'; // placeholder value
$operatorHTML = '<i class="error">empty</i>';
}
?><li class="operator">
<span data-value="<?php echo escape($operatorValue); ?>"><?php echo $operatorHTML; ?></span>
<select style="display: none;">
<option value="">- select -</option><?php
foreach ($operators as $k => $v) {
?><option value="<?php echo escape($k); ?>"><?php echo escape($v); ?></option><?php
}
?></select>
<a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>
<span class="message"><?php
if (isset($messages['errors'][$index])) {
echo escape($messages['errors'][$index]);
}
?></span>
<ul><?php
} else {
// right/operand
if (isset($rights[$token])) {
$rightValue = $token;
$rightHTML = escape($rights[$token]);
} else {
$rightValue = 'R'; // placeholder value
$rightHTML = '<i class="error">empty</i>';
}
?><li class="operand">
<span data-value="<?php echo escape($rightValue); ?>"><?php echo $rightHTML; ?></span>
<select style="display: none;">
<option value="">- select -</option><?php
foreach ($rights as $k => $v) {
?><option value="<?php echo escape($k); ?>"><?php echo escape($v); ?></option><?php
}
?></select>
<a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>
<span class="message"><?php
if (isset($messages['errors'][$index])) {
echo escape($messages['errors'][$index]);
}
?></span>
</li><?php
// we printed an item, lower stack count of current level
$stack[$level]--;
}
// close levels that have no more items to print
while ($level > 0 && $stack[$level] == 0) {
array_pop($stack);
?><li class="add">
<a class="button js-add-operator" href="javascript:void(0);">+operator</a><a class="button js-add-operand" href="javascript:void(0);">+right</a>
</li>
</ul></li><?php
$level--;
}
$index++;
}
if (empty($stack) === false) {
while ($level > 0) {
array_pop($stack);
?><li class="add">
<a class="button js-add-operator" href="javascript:void(0);">+operator</a><a class="button js-add-operand" href="javascript:void(0);">+right</a>
</li>
</ul></li><?php
$level--;
}
}
}
// if the expression is empty, we have visible controls on the top level, otherwise, just hide them
$style = ($expression == '' ? '' : ' style="display: none;"');
?><li class="add js-first-level"<?php echo $style; ?>>
<a class="button js-add-operator" href="javascript:void(0);">+operator</a><a class="button js-add-operand" href="javascript:void(0);">+right</a>
</li>
</ul>
<div class="toggle"><a href="javascript:void(0)" class="button js-toggle">toggle</a></div><?php
}
?>
You can then initialize a previously stored, and valid, expression like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
<?php
$expression = '&:3,1,|:2,2,!:1,3,4'; // some valid expression
$operators = ['&' => 'AND', '|' => 'OR', '!' => 'NOT'];
$rights = [1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'];
$messages = validate($expression, $operators);
$printTree = true;
?><div class="rights" id="rights"><?php
if ($messages['valid'] === false) {
if ($messages['syntaxErrors']) {
?><div class="validation fail">
<p>Syntax errors occurred, unable to print tree.</p>
</div>
<p>Message: <?php echo escape($messages['errors'][0]) ?></p><p>Expression: <?php echo escape($expression) ?></p><?php
$printTree = false;
} else {
?><div class="validation fail">
<p>Validation failed, check errors below.</p>
</div><?php
}
} else {
?><div class="validation pass">
<p>Validation passed!</p>
</div><?php
}
if ($printTree) {
printTree($expression, $operators, $rights, $messages);
}
?><input type="text" name="expression" id="rights_out" value="<?php echo escape($expression); ?>" size="50" autocomplete="off">
</div>
<script type="text/javascript">
//<![CDATA[
$().ready(function() {
var rights = new Rights();
rights.init({'container': 'rights', 'output': 'rights_out', 'operators': <?php echo json_encode($operators); ?>, 'rights': <?php echo json_encode($rights); ?>});
});
//]]>
</script>
The above snippets use the helper function escape()
for escaping in the HTML context:
1 2 3 4 5
<?php
function escape($s) {
return htmlspecialchars($s, ENT_QUOTES, 'UTF-8');
}
?>
Ultimately, we want to (re)create a MySQL FUNCTION
that determines if someone, given a serialized list of rights
, is allowed access to a resource warded off by expression
. Easily obtaining debugging feedback from a FUNCTION
is kind of impossible. So, for the creation and debugging we use a PROCEDURE
instead. This will enable us continuous and direct insight about the internal state and will in turn enable us to properly and easily develop and debug SQL code. Because, you know, you kinda want to make sure this code is pretty much flawless.
So first off, we create a PROCEDURE
with a lot of builtin feedback:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
DELIMITER ;;
DROP PROCEDURE IF EXISTS is_allowed;;
CREATE PROCEDURE is_allowed(expression VARCHAR(255), rights VARCHAR(255))
BEGIN
DECLARE stack VARCHAR(255);
DECLARE token VARCHAR(25);
DECLARE count INT(3) UNSIGNED;
DECLARE i INT(3) UNSIGNED;
DECLARE result BOOL;
IF (expression = '') THEN
SET stack = '1';
SELECT CONCAT('empty expression') AS feedback;
ELSE
SET stack = '';
SET expression = REVERSE(expression);
END IF;
WHILE (LENGTH(expression) > 0) DO
SET token = REVERSE(SUBSTRING_INDEX(expression, ',', 1));
SET expression = SUBSTRING(expression, LENGTH(token) + 2);
IF (LOCATE(':', token) = 0) THEN
SET stack = CONCAT(FIND_IN_SET(token, rights) > 0, stack);
SELECT CONCAT('right found: ', token,', stack: ', stack) AS feedback;
ELSE
SET count = SUBSTRING_INDEX(token, ':', -1);
SET token = SUBSTRING(token, 1, 1);
SELECT CONCAT('operator found: ', token, ', count: ', count) AS feedback;
IF (token = '!') THEN
SET result = 1 - SUBSTRING(stack, 1, 1);
ELSEIF (token = '&') THEN
SET result = TRUE;
SET i = 1;
WHILE (i <= count AND result) DO
IF (SUBSTRING(stack, i, 1) = 0) THEN
SELECT CONCAT('found FALSE on index ', i, ' exiting') AS feedback;
SET result = FALSE;
END IF;
SET i = i + 1;
END WHILE;
ELSEIF (token = '|') THEN
SET result = FALSE;
SET i = 1;
WHILE (i <= count AND result = FALSE) DO
IF (SUBSTRING(stack, i, 1) = 1) THEN
SELECT CONCAT('found TRUE on index ', i, ' exiting') AS feedback;
SET result = TRUE;
END IF;
SET i = i + 1;
END WHILE;
END IF;
SET stack = CONCAT(result, SUBSTRING(stack, count + 1));
SELECT CONCAT('stack after processing: ', stack) AS feedback;
END IF;
END WHILE;
SELECT CONCAT('final result: ', stack) AS feedback;
END;;
DELIMITER ;
We can follow exactly which internal path is taken when we call this procedure. Calling it like this:
> CALL is_allowed('&:3,51,|:2,52,!:1,53,54', '51,54');
Will result, minus all the clutter, in the following verbose output:
right found: 54, stack: 1 right found: 53, stack: 01 operator found: !, count: 1 stack after processing: 11 right found: 52, stack: 011 operator found: |, count: 2 found TRUE on index 2 exiting stack after processing: 11 right found: 51, stack: 111 operator found: &, count: 3 stack after processing: 1 final result: 1
A call to:
> CALL is_allowed('&:3,51,|:2,52,!:1,53,54', '51,53');
Results in:
right found: 54, stack: 0 right found: 53, stack: 10 operator found: !, count: 1 stack after processing: 00 right found: 52, stack: 000 operator found: |, count: 2 stack after processing: 00 right found: 51, stack: 100 operator found: &, count: 3 found FALSE on index 2 exiting stack after processing: 0 final result: 0
After some iterations you can port this to an almost equivalent FUNCTION
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
DELIMITER ;;
DROP FUNCTION IF EXISTS is_allowed;;
CREATE FUNCTION is_allowed(expression VARCHAR(255), rights VARCHAR(255)) RETURNS BOOL DETERMINISTIC
BEGIN
DECLARE stack VARCHAR(255);
DECLARE token VARCHAR(25);
DECLARE count INT(3) UNSIGNED;
DECLARE i INT(3) UNSIGNED;
DECLARE result BOOL;
IF (expression = '') THEN
RETURN TRUE;
END IF;
SET stack = '';
SET expression = REVERSE(expression);
WHILE (LENGTH(expression) > 0) DO
SET token = REVERSE(SUBSTRING_INDEX(expression, ',', 1));
SET expression = SUBSTRING(expression, LENGTH(token) + 2);
IF (LOCATE(':', token) = 0) THEN
SET stack = CONCAT(FIND_IN_SET(token, rights) > 0, stack);
ELSE
SET count = SUBSTRING_INDEX(token, ':', -1);
SET token = SUBSTRING(token, 1, 1);
IF (token = '!') THEN
SET result = 1 - SUBSTRING(stack, 1, 1);
ELSEIF (token = '&') THEN
SET result = TRUE;
SET i = 1;
WHILE (i <= count AND result) DO
IF (SUBSTRING(stack, i, 1) = 0) THEN
SET result = FALSE;
END IF;
SET i = i + 1;
END WHILE;
ELSEIF (token = '|') THEN
SET result = FALSE;
SET i = 1;
WHILE (i <= count AND result = FALSE) DO
IF (SUBSTRING(stack, i, 1) = 1) THEN
SET result = TRUE;
END IF;
SET i = i + 1;
END WHILE;
END IF;
SET stack = CONCAT(result, SUBSTRING(stack, count + 1));
END IF;
END WHILE;
RETURN stack;
END;;
DELIMITER ;
And run some more tests like we did in the PHP variant:
> SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '54') AS test; +------+ | test | +------+ | 0 | +------+ 1 row in set (0.01 sec) > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '51,53') AS test; +------+ | test | +------+ | 0 | +------+ 1 row in set (0.00 sec) > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '51,54') AS test; +------+ | test | +------+ | 1 | +------+ 1 row in set (0.00 sec) > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '52,54') AS test; +------+ | test | +------+ | 0 | +------+ 1 row in set (0.00 sec) > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '51,52,53') AS test; +------+ | test | +------+ | 0 | +------+ 1 row in set (0.00 sec)
Note that I am using somewhat longer right ids (above 9) to test in MySQL. This is because when you apply REVERSE()
to a string, it reverses everything, including the numbers of the right ids, as opposed to array_reverse()
in PHP which only reverses the order of its members.
Many changes in printing and validating the expression; these are mostly concerning a smoother user experience and better error feedback.
json_encode()
d arrays) when creating the form elementprintTree()
with more accurate informationInitial post.