Access Control List implementation in PHP-MySQL

Announcement

I am currently working on an updated version of this functionality which provides more flexibility. This new variant will have no restrictions on the number of operands the operators will act upon. But we still will not have to use brackets to accomplish this. Stay tuned!

EDIT: This article is now live and can be found here!

Some notes

I am in favor of (abundant) annotation. It is a great way to further explain what code does and better enabling other people to follow ones train of thought. For readability purposes, however, almost all the annotation of the code in this article has been stripped. This does not mean, however, that the code herein is written without any thought.

Summary

This article will discuss an implementation of an Access Control List (ACL) in PHP-MySQL. Obviously, there are many ways to do this and a lot depends on how you manage your roles and rights themselves.

The implementation will enable you to protect resources in a generic way. Basically, you store serialized predicates in Polish Notation alongside your resources. But don't worry if that sounded like complete gibberish, the rest of this article will explain what this means.

Below, we will start off with a general overview of the problem at hand: you have areas in your application that need to be warded off. We assume that there is some kind of login mechanism in place, but the next step is applying rights management in your code.

Next, we will discuss some theory and propose a generic solution that builds upon this theory.

Finally, and here lies the real challenge, we will explore how we convert this solution into a (semi) user friendly implementation that is relatively easy to use by less tech savvy people. Of course, users will need some understanding of boolean logic to be able to use the ACL but, as they say, with great power comes great responsibility.

The dilemma

Stuff you code from scratch yourself has its merits, but you must be constantly vigilant to prevent your code from becoming a complete tangled mess. Suppose at some point you decided to introduce some kind of rights management and you wrote some functionality which is protected by rights represented by numbers. Consider the next piece of code that determines whether an authenticated user has access to its functionality when the following conditions apply:

A possible implementation in pseudo-code would be something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
<?php
if (
    $user->hasRight(1)
    ||
    ($user->hasRight(2) && !$user->hasRight(3))
) {
    // access granted, do stuff
    // ...
} else {
    // access denied, complain, redirect, die
    // ...
}
?>

Although this code serves its purpose, it has a number of drawbacks:

So, our first step towards improvement would be to externalize this check from the code. One way to do this is by storing the check alongside the resource. But what would this check look like, and how would you go about evaluating such a check? Basically, you want to store this boolean expression or predicate in an unambiguous way that is easy to read (for machines). Storing actual PHP-code that is eval()uated is probably not a very good idea. The predicate could potentially have quite a complex structure but it still follows a certain logic (*drum fill*).

Although at this point we do not have a clear view on how to implement such a thing (how to translate a predicate into some kind of structure) we can explore the possibilities on a more abstract level: we doodle.

Make a tree

Predicates have structure. So do trees. It is possible to write out a predicate in a tree? Let's continue our previous example.

OR-+-1
   |
   +-AND-+-2
         |
         +-NOT-3

This looks like a good idea. But then there is still the issue of ambiguity. Take for example A AND B OR C. Depending on what you mean, this results in two completely different trees. Did we mean (A AND B) OR C:

OR-+-C
   |
   +-AND-+-A
         |
         +-B

Or A AND (B OR C):

AND-+-A
    |
    +-OR-+-B
         |
         +-C

And then there is the variant where multiple conditions must apply (such as A AND B AND C AND D). Our first impulse would perhaps be to add brackets around certain parts to group sub-expressions (and our second, perhaps, to scream). Although this solves the problem of ambiguity (the meaning of the predicate is clear through proper use of brackets) this introduces another problem: it makes evaluating such an expression so much harder as we would probably have to parse or recursively traverse it. This might also influence performance in a negative way.

We can avoid this (potential) snakepit by placing some restrictions on our building blocks: both the AND and the OR operators accept exactly two operands and the NOT operator accepts exactly one operand. This completely annihilates the need for brackets. The only drawback is that you would have to stack operators of the same kind, but if you would have a different operator inbetween, it would be unambiguous without the need for brackets. For example, we would need to write out A AND B AND C AND D in the following way:

AND-+-A
    |
    +-AND-+-B
          |
          +-AND-+-C
                |
                +-D

But to be fair, if this is the price to pay to avoid some bracket parsing hell, I would gladly pay it :).

Okay, so now we have trees as a formalised (albeit, for now, abstract) way to represent our predicates. Now what? Now we need a way to write this out in a serialized form so we can store this information alongside our resource. This serialized form must also be suitable to quickly return a YES or NO when it is evaluated against a list of granted rights, to establish whether the user is granted access or not. Wouldn't it be great if such a thing would exist...

Polish notation to the rescue

Well, it already does. The Polish notation, or prefix notation, is a notation scheme where operators are placed in front (prefixed) of their operands. The WIKI page explains that if the arity of the operators is fixed (meaning, if it is predetermined on how many parameters a mathematical or logical symbol operates) then this results in a syntax that is unambiguous and therefore does not need parentheses or brackets. This is exactly what we already accomplished in the last paragraph. Moreover, the WIKI page even describes a simple algorithm on how to evaluate such an expression!

But first things first. How do we rewrite our tree to an expression in Polish notation? The easiest way is to read the tree from the bottom to the top, and then construct the expression from right to left. If we continue our original example, repeated here:

OR-+-1
   |
   +-AND-+-2
         |
         +-NOT-3

This would result in:

OR 1 AND 2 NOT 3

Which kind of exactly follows the tree structure as well, but we need to learn how to read these structures from a Polish-notation-point-of-view. I encourage you to read the WIKI page to get a better feel for this.

Seriously, read the WIKI, then return here.

When I first wrote such a serialized expression, I combined the NOT operator with its operand. I ended up separating them as treating them as separate tokens proved to be (a lot) easier. So, we are almost there. The expression above is still a bit bloated, it can be made shorter still. In my variant I shortened it in the following way (but feel free to cook up your own variant):

Our very first serialized predicate in Polish notation will thus become:

|,1,&,2,!,3

At this point, you might not realise yet how flipping awesome this actually is.

A little less conversation and a little more action

Okay, let's get coding. Where to start? There are a couple of things we need to implement to be able to use all this:

Let's pretend we succeeded in the first step (don't worry, I won't skip anything) and we stored an expression we now want to evaluate against our granted rights. So, we would need something like a function:

1
2
3
4
5
<?php
function isAllowed($expression, $rights) {
    // do magic
}
?>

This function will simply return a boolean (true or false) indicating whether a user with rights $rights (an array) has access to a certain resource according to its accompanied set of conditions $expression (a logical-tree-stored-in-serialized-form-using-Polish-notation which is validated against $rights). So how to perform this magic? The WIKI page describes an algorithm on how to accomplish this:

scan the given prefix expression from right to left
for each symbol {
    if operand then
        push onto stack
    if operator then {
        operand1=pop stack
        operand2=pop stack
        compute operand1 operator operand2
        push result onto stack
    }
}
return top of stack as result

This can almost be translated 1:1 to PHP. I think the best way to explain it is to just lay out the code first, and then talk about what I did, and why.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php
function isAllowed($expression, $rights) {
    if ($expression == '') {
        return true;
    }
    $stack = array();
    foreach (array_reverse(explode(',', $expression)) as $token) {
        if ($token == '&' || $token == '|') {
            $val1 = array_pop($stack);
            $val2 = array_pop($stack);
            $stack[] = ($token == '|' ? $val1 || $val2 : $val1 && $val2);
        } elseif ($token == '!') {
            $n = count($stack) - 1;
            $stack[$n] = !$stack[$n];
        } else {
            $stack[] = !empty($rights[$token]);
        }
    }
    return $stack[0];
}
?>

Let's break this code into digestible chunks. Note that this function operates under the assumption that $expression is a valid serialized predicate in Polish notation.

1
2
3
4
5
<?php
if ($expression == '') {
    return true;
}
?>

This is pretty straight forward: if the expression is empty, this means there are no special conditions for unlocking access to this resource, in other words, everyone is allowed to access it so we return true immediately, regardless of what rights the user might have (this is irrelevant in this case).

For the sake of understanding this code the next bit is quite important. We need to view $stack as a collection of (intermediate) boolean results. When we traverse $expression we store the result of evaluated operators and operands as booleans (true or false) on the stack. Based on what we come across in $expression we may also take previous results from the stack and recombine them into a boolean (result) value. The algorithm works in such a way that when we have traversed the entire expression a single boolean value remains on the stack which is the calculated end result of the validation of $expression against $rights.

What you need to remember from the previous paragraph is: $stack is an array of booleans. When $expression is fully analysed, one boolean value remains on the stack that indicates whether the user had sufficient rights for access.

1
2
3
4
5
<?php
foreach (array_reverse(explode(',', $expression)) as $token) {
    // ...
}
?>

Next, we split this serialized expression by its separator (with explode()), effectively converting it into an array. We also reverse the order of the elements. This is because of the way in which we read expressions in Polish notation: from right to left. We are now ready to traverse the different tokens (operators and operands) which constitute the expression. Each token either contains an operator (& (AND), | (OR) or ! (NOT)) or an operand (a right id which is required for access to the resource).

1
2
3
4
5
6
7
8
9
10
11
12
<?php
if ($token == '&' || $token == '|') {
    $val1 = array_pop($stack);
    $val2 = array_pop($stack);
    $stack[] = ($token == '|' ? $val1 || $val2 : $val1 && $val2);
} elseif ($token == '!') {
    $n = count($stack) - 1;
    $stack[$n] = !$stack[$n];
} else {
    $stack[] = !empty($rights[$token]);
}
?>

This chunk is where all the hard work is done. Here we distinguish between the different tokens we can come across:

To explain this part it is probably best to start with the else { ... } part. In this case we inspect if the current token (which is a right id) occurs in the $rights array. We assume that $rights is an array in which the keys contain the right id (for fast lookup, as opposed to a solution where you put all the rights in array values and you perform the check using in_array()) and the value is something that does not evaluate to false. You could also use isset() instead of !empty(), and then make sure the values of $rights differ from NULL. Our rights array might for example look like this (note that it only contains rights we actually do have):

1
2
3
4
5
6
7
<?php
$myRights = array(
    1 => true,
    2 => true,
    5 => true,
);
?>

So if the user has the right, we put the boolean value true on top of the stack, otherwise we put false on top of the stack. We do this for a couple of rights (operands) until we come across a token which is an operator (either &, | or !).

If the token is ! (NOT), we simply negate what is on top of the stack. If the value on top of the stack is true it becomes false and vice versa. Note that because we read the expression from right to left and we prefix the operators we always come across a (at least one) operand first.

If the token is either & (AND) or | (OR) we take the top two boolean values from the stack (remember that we made the decision earlier to let the AND and OR operators operate on exactly two values). We then recombine those two values into one value and put the boolean result of this comparison back on the stack. The evaluation of this follows the normal rules for logical operations. If the token was | (OR) we perform a logical OR comparison in PHP (with ||), otherwise we perform a logical AND comparison in PHP (with &&).

1
2
3
<?php
return $stack[0];
?>

After we have traversed the entire expression there is only one boolean value left on the stack which indicates whether the rights in $rights were sufficient to access the resource with predicate $expression. This boolean is returned. The expression MUST be valid (meaning: must have the correct form) in order to ensure exactly one boolean remains on the stack, so we have to make sure we properly validate the expression before we store it with the resource. We will look into this later. First, an example.

Let's consider some rights setups to validate against. Once again we take our initial example.

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
error_reporting(E_ALL);
ini_set('display_errors', 'stdout');

function isAllowed($expression, $rights) {
    if ($expression == '') {
        return true;
    }
    $stack = array();
    foreach (array_reverse(explode(',', $expression)) as $token) {
        if ($token == '&' || $token == '|') {
            $val1 = array_pop($stack);
            $val2 = array_pop($stack);
            $stack[] = ($token == '|' ? $val1 || $val2 : $val1 && $val2);
        } elseif ($token == '!') {
            $n = count($stack) - 1;
            $stack[$n] = !$stack[$n];
        } else {
            $stack[] = !empty($rights[$token]);
        }
    }
    return $stack[0];
}

$expression = '|,1,&,2,!,3';

// This should result in access being granted.
$myRights = array(
    1 => true,
);
if (isAllowed($expression, $myRights)) {
    echo 'rights: 1. Access granted.<br />';
} else {
    echo '[error] rights: 1. Should be granted access!<br />';
}

// This should also result in access being granted.
$myRights = array(
    1 => true,
    2 => true,
);
if (isAllowed($expression, $myRights)) {
    echo 'rights: 1, 2. Access granted.<br />';
} else {
    echo '[error] rights: 1, 2. Should be granted access!<br />';
}

// Same.
$myRights = array(
    1 => true,
    3 => true,
);
if (isAllowed($expression, $myRights)) {
    echo 'rights: 1, 3. Access granted.<br />';
} else {
    echo '[error] rights: 1, 3. Should be granted access!<br />';
}

// Same.
$myRights = array(
    2 => true,
);
if (isAllowed($expression, $myRights)) {
    echo 'rights: 2. Access granted.<br />';
} else {
    echo '[error] rights: 2. Should be granted access!<br />';
}

// This combination is invalid, so access should be denied.
$myRights = array(
    2 => true,
    3 => true,
);
if (isAllowed($expression, $myRights)) {
    echo '[error] rights: 2, 3. Access should not be granted!<br />';
} else {
    echo 'rights: 2, 3. Access denied.<br />';
}

// Although this is probably an odd combination of granted rights, it should give you access.
$myRights = array(
    1 => true,
    2 => true,
    3 => true,
);
if (isAllowed($expression, $myRights)) {
    echo 'rights: 1, 2, 3. Access granted.<br />';
} else {
    echo '[error] rights: 1, 2, 3. Should be granted access!<br />';
}

// Yeah... no rights. Good luck.
$myRights = array();
if (isAllowed($expression, $myRights)) {
    echo '[error] rights: none. Access should not be granted!<br />';
} else {
    echo 'rights: none. Access denied. Shoo!<br />';
}
?>

This should output:

rights: 1. Access granted.
rights: 1, 2. Access granted.
rights: 1, 3. Access granted.
rights: 2. Access granted.
rights: 2, 3. Access denied.
rights: 1, 2, 3. Access granted.
rights: none. Access denied. Shoo!

So what we basically have done is rewritten something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
<?php
if (
    $user->hasRight(1)
    ||
    ($user->hasRight(2) && !$user->hasRight(3))
) {
    // access granted, do stuff
    // ...
} else {
    // access denied, complain, redirect, die
    // ...
}
?>

Into something like this:

1
2
3
4
5
6
7
8
9
10
<?php
$expression = '|,1,&,2,!,3';
if (isAllowed($expression, $user->getRights())) {
    // access granted, do stuff
    // ...
} else {
    // access denied, complain, redirect, die
    // ...
}
?>

Where $expression can be pulled from... anywhere. It is no longer bound to this code. Are you beginning to see the awesome? No? Meh.

You now basically already have a flexible ACL without an interface. Theoretically you could secure all your resources by typing in serialized predicates in Polish notation. But yeah, going that extra mile to create a somewhat more intuitive interface for building these expressions would be nice.

I wrote code for both creating new expressions and editing existing ones. For both I use a combination of PHP and HTML/CSS/JavaScript (in the form of jQuery). You can probably incorporate this code in your own forms in which you manange your resources. Let's see what needs to be done.

Building a new expression

So yeah, how to cook some kind of reusable form element for this functionality. A good starting point is probably a list, because it's quite suitable for displaying tree-like structures. Our default example would look something like this:

Or this (both expressions are equivalent -there are two more- so you should be able to build it like this, too):

A form may have multiple elements which deal with various actions you are allowed to perform when you possess specific rights. Therefore it is probably a good idea to write your jQuery in such a way that you are able to reuse this element multiple times in the same form.

On a side note, up till now we only talked about access rights but of course you can use these predicates to specify all kinds of actions (create, read, update, delete et cetera). It goes beyond the scope of solely "access".

A possible jQuery setup for building such a form element is thus:

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
// uses escape.js
function Rights() {
    this.$container = false;
    this.$output    = false;

    this.init = function(options) {
        this.$container = $('#'+options.container);
        this.$output    = $('#'+options.output);

        this.$container.find('li').click(this.handleClick);

        this.$container.find('li').on('mouseover mouseout', function(e) {
            e.stopPropagation();
            if (e.type == 'mouseover') {
                $(e.target).closest('li').addClass('hover');
            } else {
                $(e.target).closest('li').removeClass('hover');
            }
        });

        this.generateOutput();
    }

    var that = this;

    this.handleClick = function(e) {
        e.stopPropagation();
        var $element = $(this);
        var value    = $element.find('span').first().text();
        var $html    = $('<input type="text" value="" \/>').val(value);

        $html.click(function(e) {
            e.stopPropagation();
        });

        $html.keypress(function(e) {
            if (e.which == 13) {
                e.preventDefault();
                $(this).blur();
            }
        });

        $html.blur(function() {
            var value = $(this).val();
            if (value == '') {
                value = 'empty';
            }
            $element.html('<span>'+escapeHtml(value)+'<\/span>');
            if (value == 'AND' || value == 'OR') {
                $ul = $('<ul><\/ul>');
                $ul.append($('<li><span>empty<\/span><\/li>').click(that.handleClick));
                $ul.append($('<li><span>empty<\/span><\/li>').click(that.handleClick));
                $element.append($ul);
            } else if (value == 'NOT') {
                $ul = $('<ul><\/ul>');
                $ul.append($('<li><span>empty<\/span><\/li>').click(that.handleClick));
                $element.append($ul);
            }
            that.generateOutput();
        });
        $element.html($html);
        $html.focus().select();
    }

    this.generateOutput = function() {
        var out = '';
        this.$container.find('li span').each(function() {
            var value = $(this).text();
            var map = {'AND': '&', 'OR': '|', 'NOT': '!'};
            if (value in map) {
                value = map[value];
            }
            out = out+(out == '' ? '' : ',')+value;
        });
        if (out == 'empty') {
            out = '';
        }
        this.$output.val(out);
    }
}

This code uses the escapeHtml() function from the mustache template system. You can put it in a separate .js file (for example escape.js):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// @see https://github.com/janl/mustache.js
var entityMap = {
    "&": "&amp;",
    "<": "&lt;",
    ">": "&gt;",
    '"': '&quot;',
    "'": '&#39;',
    "/": '&#x2F;'
};
function escapeHtml(string) {
    return String(string).replace(/[&<>"'\/]/g, function (s) {
        return entityMap[s];
    });
}

And some CSS.

1
2
3
4
5
div.rights              { background-color: #ccccff; padding: 10px; }
div.rights ul           { list-style: disc inside; margin: 0; padding-left: 25px; }
div.rights > ul         { padding-left: 0; }
div.rights ul li        { line-height: 20px; padding-left: 5px; }
div.rights ul li.hover  { background-color: #ffcccc; }

The best way to explain how this works is probably by showing a working example. Combine all the files into a HTML document:

example

To be able to use this functionality, we only need to do a few things (check the HTML source in the example above):

It is probably easiest if you apply (semi) strict naming conventions. If you use some kind of form system these are probably already in place. The JavaScript Rights object variable in the above example has the same name as the id of the output field. The container has the same name with the "_container" suffix. Note that you can create as many instances as you like in the same fashion. All these instance names must be unique, obviously.

We are now ready to store our expression(s) with our resource(s). But before we actually do so, we need to absolutely make sure the expression is syntactically correct. It is probably also wise to re-check the expression when we make calls to the isAllowed() function. Strictly speaking, this should not be necessary (you checked it before you stored it with the resource, right?), but one cannot be too careful when it comes to security.

Validating an expression in PHP

For this we introduce another function:

1
2
3
4
5
<?php
function validate($expression, $validRights=array()) {
    // do magic
}
?>

We need to realise this function serves a completely different purpose from the isAllowed() function. The isAllowed() function checks if a user with certain rights is allowed to perform a specific action on a resource according to its accompanied boolean expression whereas the validate() function checks if the expression itself is syntactically and semantically correct.

Sometimes it can be desirable that we do not explicitly check what rights are valid. This is why the $validRights parameter is optional. If we supply a nonempty array of right ids (as keys, similar to isAllowed()) we check the rights, if we don't, we do not. In that case the operands might contain gibberish, but that should not matter as long as the rest of the expression is syntactically correct. It is, of course, for you to decide when checking for valid rights really matters. One of those occasions would be when you actually store the expression alongside the resource. You can always decide to go for a more strict mode and make it mandatory to always supply an array of valid rights. But keep in mind that this might break functionality when you decide to delete obsolete rights which might still be present in one or more serialized expressions.

A possible implementation of this function is thus:

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
<?php
function validate($expression, $validRights=array()) {
    if ($expression == '') {
        return true;
    }
    $stackSize = 0;
    $operators = 0;
    $operands  = 0;
    foreach (array_reverse(explode(',', $expression)) as $token) {
        if ($token == '&' || $token == '|') {
            if ($stackSize < 2) {
                return false;
            }
            $stackSize--;
            $operators++;
        } elseif ($token == '!') {
            if ($stackSize < 1) {
                return false;
            }
        } else {
            if (count($validRights) > 0) {
                if (!isset($validRights[$token])) {
                    return false;
                }
            }
            $stackSize++;
            $operands++;
        }
    }
    return ($operators + 1 === $operands && $stackSize === 1);
}
?>

Basically, the above code counts the number of operators and operands and keeps track of how many (intermediate) boolean values there are on the stack. If we do not have enough values to evaluate this means the syntax is wrong and we immediately return false. Note that we do not count the NOT operator because it does not modify the stack size. Documentation on the WIKI page (kind of) states that an expression in Polish notation always consists of N - 1 operators and N operands. After evaluating the entire expression (if we get that far) we also should have one item remaining on the stack. If both these conditions apply (one might even imply the other, I'm not entirely sure) then the expression has a correct syntax. We also (optionally) check if the expression consists solely of known (valid) rights.

In a similar fashion as with the isAllowed() function you can write some checks to see if certain expressions (with optionally an array of valid rights) are considered valid (syntactically and semantically correct).

Editing an existing expression

We have almost come full circle. We can build expressions, validate them, store them and check if access should be granted to the associated resource based on a list of rights a user owns. The only thing that is missing is the ability to edit a previously stored expression. For this, we need to be able to rebuild a (nested) list in HTML based on an expression so that we can pick up where we left off with our jQuery functionality. We introduce yet another (helper) function for this:

1
2
3
4
5
<?php
function printTree($expression) {
    // do magic
}
?>

I chose not to incorporate the outer <ul> when converting the expression into a HTML list. This is so you can easily hook up additional logic to it if needed. Building a list out of an earlier stored expression will therefore amount to something like:

1
2
3
4
5
6
7
8
9
10
11
12
<div class="rights" id="rights_test_1_container">
    <ul><?php printTree($expression) ?></ul>
</div>
<input type="hidden" id="rights_test_1" value="" />
<script type="text/javascript">
//<![CDATA[
$().ready(function() {
    var rights_test_1 = new Rights();
    rights_test_1.init({'container': 'rights_test_1_container', 'output': 'rights_test_1'});
});
//]]>
</script>

You do not even have to initialize the hidden field as this is done by jQuery. A possible implementation of printTree() is 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
<?php
function printTree($expression) {
    if ($expression == '') {
        $expression = 'empty';
    }
    $currentDepth = 0;
    $stack[0] = 1;

    $positions = array(
        '|' => 2,
        '&' => 2,
        '!' => 1,
    );
    $map = array(
        '|' => 'OR',
        '&' => 'AND',
        '!' => 'NOT',
    );
    foreach (explode(',', $expression) as $token) {
        while ($currentDepth > 0 && $stack[$currentDepth] == 0) {
            ?></ul></li><?php
            $currentDepth--;
        }
        $stack[$currentDepth]--;
        if (isset($positions[$token])) {
            $currentDepth++;
            $stack[$currentDepth] = $positions[$token];
            ?><li><span><?php echo escape($map[$token]) ?></span><ul><?php
        } else {
            ?><li><span><?php echo escape($token) ?></span></li><?php
        }
    }
    if ($currentDepth > 0) {
        echo str_repeat('</ul></li>', $currentDepth);
    }
}
?>

I will give a very quick rundown of this code. The strategy for rebuilding an existing rights tree is as follows: tokens occupy spots on various levels of depth in the tree. We track on what level we are currently looking and how many spots are free on each level. Each operand consumes a spot on the current level. Each operator does this as well. In addition, it also creates a new level with one or more free spots, dependent on the type of operator. Each iteration in which we put a token in the tree we first determine the location of the first free spot that we come across by switching to this depth. Initially we have one free spot (the root of the tree). This is pretty much the gist of it. Truth be told, I wrote this code through a bit of experimentation and little else, but it seems to work for the expressions on which I tested it.

You may have noticed an additional function for escaping output: escape(). This is to ensure that both the operators and operands are printed in a HTML safe way. The implementation of escape() is basically just a shorthand (you should be using UTF-8 already to be fair):

1
2
3
4
5
<?php
function escape($in) {
    return htmlspecialchars($in, ENT_QUOTES, 'UTF-8');
}
?>

MySQL implementation

Say you have a list of resources of a certain type stored in your database, and you want to filter these based on granted rights. With the current code you could fetch all these resources and then filter them with the isAllowed() function afterwards. This is a bit unpractical of course, especially when you want to divide displaying this list over several pages. You would first have to traverse all the items to determine how many remain after filtering and how many pages this would result in. And then you probably only display a small part of all the fetched data. This is rather inefficient.

A better solution would be to filter these items directly when executing the query. MySQL can use functions too but does not have anything like an array data type, at least not that I am aware. So we need to resort to some (clever) string manipulation. The following is a semi experimental implementation so use it with some caution.

toggle display of old version

Updated implementation

I did some more thinking and tinkering and this resulted in a semi updated version of the previous implementation. Basically I could simplify some stuff by treating the stack as an actual list of Booleans, that is, the length of each element is fixed. As before this function comes with a disclaimer - it is still somewhat experimental. Also, as mentioned at the start of this article a new variant of this implementation is in the making which should provide more flexibility.

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
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(5);
    IF (expression = '') THEN
        RETURN TRUE;
    END IF;
    SET stack = '';
    SET expression = REVERSE(expression);
    WHILE (LENGTH(expression) > 0) DO
        SET token      = SUBSTRING_INDEX(expression, ',', 1);
        SET expression = SUBSTRING(expression, LENGTH(token) + 2);
        IF (token = '|' OR token = '&') THEN
            IF (token = '|') THEN
                SET stack = CONCAT(SUBSTRING(stack, 1, 1) OR SUBSTRING(stack, 2, 1), SUBSTRING(stack, 3));
            ELSE
                SET stack = CONCAT(SUBSTRING(stack, 1, 1) AND SUBSTRING(stack, 2, 1), SUBSTRING(stack, 3));
            END IF;
        ELSEIF (token = '!') THEN
            SET stack = CONCAT(NOT(SUBSTRING(stack, 1, 1)), SUBSTRING(stack, 2));
        ELSE
            SET stack = CONCAT(FIND_IN_SET(REVERSE(token), rights) > 0, stack);
        END IF;
    END WHILE;
    RETURN stack;
END;;
DELIMITER ;

After creating this function you could run some tests:

mysql> SELECT is_allowed('|,1,&,2,!,3', '1');
+--------------------------------+
| is_allowed('|,1,&,2,!,3', '1') |
+--------------------------------+
|                              1 |
+--------------------------------+
1 row in set (0.00 sec)

mysql> SELECT is_allowed('|,1,&,2,!,3', '1,2');
+----------------------------------+
| is_allowed('|,1,&,2,!,3', '1,2') |
+----------------------------------+
|                                1 |
+----------------------------------+
1 row in set (0.00 sec)

mysql> SELECT is_allowed('|,1,&,2,!,3', '1,3');
+----------------------------------+
| is_allowed('|,1,&,2,!,3', '1,3') |
+----------------------------------+
|                                1 |
+----------------------------------+
1 row in set (0.00 sec)

mysql> SELECT is_allowed('|,1,&,2,!,3', '2,3');
+----------------------------------+
| is_allowed('|,1,&,2,!,3', '2,3') |
+----------------------------------+
|                                0 |
+----------------------------------+
1 row in set (0.00 sec)

mysql> SELECT is_allowed('|,1,&,2,!,3', '1,2,3');
+------------------------------------+
| is_allowed('|,1,&,2,!,3', '1,2,3') |
+------------------------------------+
|                                  1 |
+------------------------------------+
1 row in set (0.00 sec)

mysql> SELECT is_allowed('|,1,&,2,!,3', '');
+-------------------------------+
| is_allowed('|,1,&,2,!,3', '') |
+-------------------------------+
|                             0 |
+-------------------------------+
1 row in set (0.00 sec)

Changelog

created 2014-08-26