Access Control List implementation in PHP-MySQL - revisited

Introduction

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.

A new idea

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

Concerns, you gotta keep 'em separated

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.

Forwards, and back

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($token01);
            $count substr($token2);
            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.

Further optimization

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($token01)) {
    case '!':
        $result = !array_pop($stack);
    break;
    case '&':
        $result true;
        for ($i substr($token2); $i 0$i--) {
            if (!array_pop($stack)) {
                $result false;
            }
        }
    break;
    case '|':
        $result false;
        for ($i substr($token2); $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.

Did I pass the acid test?

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(
    => true,
);

if (isAllowed($expression$myRights)) {
    echo '[error] rights: 4; should not be allowed<br />';
} else {
    echo 'rights: 4; not allowed<br />';
}

$myRights = array(
    => true,
    => 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(
    => true,
    => true,
);

if (isAllowed($expression$myRights)) {
    echo 'rights: 1,4; is allowed<br />';
} else {
    echo '[error] rights: 1,4; should be allowed<br />';
}

$myRights = array(
    => true,
    => 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(
    => true,
    => true,
    => 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

Building a new expression

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">&#10033;</a><a class="button js-remove" href="javascript:void(0);">&#10006;</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">&#10033;</a><a class="button js-remove" href="javascript:void(0);">&#10006;</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:

Validating an expression in PHP

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(
                    => '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(
                        => '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(
                => '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:

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.

Editing an existing expression

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 = [=> 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">&#10033;</a><a class="button js-remove" href="javascript:void(0);">&#10006;</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">&#10033;</a><a class="button js-remove" href="javascript:void(0);">&#10006;</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 && $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     = [=> 'one'=> 'two'=> 'three'=> '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($sENT_QUOTES'UTF-8');
}
?>

MySQL implementation

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.

Todo

Changelog

2021-03-24

2018-06-04

2018-05-31

Many changes in printing and validating the expression; these are mostly concerning a smoother user experience and better error feedback.

2018-05-23

Initial post.