Access Control List implementatie in PHP/MySQL - deel 2/2

Voorwoord

Oorspronkelijk was ik van plan om in het tweede deel een herbruikbaar formulierelement te introduceren voor het bouwen van rechtenbomen. In dit deel zou ook een MySQL-implementatie behandeld worden. Echter, tijdens het schrijven van het eerste deel raakten er wat ideeën in een stroomversnelling wat uiteindelijk uitmondde in een nieuwe, flexibelere versie waarbij het wel mogelijk is om een willekeurig aantal operatoren en operanden (rechten) aan een operator te koppelen. Ook het formulierelement heeft inmiddels een metamorfose ondergaan. Al met al ben ik een stuk tevredener over deze nieuwe variant. De oude variant was wel een noodzakelijke iteratie en vormde een prima uitgangspunt voor verdere ontwikkeling, dus deze was zeker niet overbodig of onaf.


Dit tweede deel zal daarom niet meer gaan over het restant van deel #1, maar zal de nieuwe variant volledig behandelen waarbij onderdelen die reeds besproken waren kort behandeld zullen worden in hun nieuwe opzet. Mocht je toch nog geïnteresseerd zijn in de eerste variant dan is dat artikel, weliswaar in het engels, beschikbaar via mijn website. Misschien is het qua historie ook wel interessant om te zien hoe dit zo gegroeid is.


Allereerst wat historie van deze nieuwe variant.


Een nieuw idee

Op de WIKI-pagina over de Poolse Notatie staat de volgende passage:

Citaat

WIKI wrote:

Assuming a given arity of all involved operators ... any well formed prefix representation thereof is unambiguous, and brackets within the prefix expression are unnecessary.

Als het dus vaststaat op hoeveel operanden een operator acteert (de ariteit), dan is deze notatiewijze (Poolse Notatie of prefix notatie) ondubbelzinnig en is er geen noodzaak om (sub)expressies te groeperen met haken. Dit wisten we in feite al. Maar als we dit wat beter lezen dan staat er nergens dat de ariteit moet vastliggen, maar enkel dat deze op een of andere manier bekend moet zijn. Oftewel, deze mag best variëren.


Maar hoe weet je dan op hoeveel items een operator zou moeten acteren? Welnu, dat is eenvoudig: je vertelt dit simpelweg.


We pakken ons voorbeeld uit het vorige deel en breiden deze uit:



PHP Source Code

Edit Source Code

  1. <?php
  2. /*
  3. AND--+--1
  4. .....|
  5. .....+--OR--+--2
  6. .....|......|
  7. .....|......+--NOT--3
  8. .....|
  9. .....+--4
  10. */
  11. ?>



De AND operator acteert nu op drie items (het recht 1, de operator OR, het recht 4) in plaats van twee.

De OR operator acteert nog steeds op twee items (het recht 2, de operator NOT) maar dit aantal staat niet langer op voorhand vast.

De NOT operator is nog steeds op precies één item actief.

Het zou ook geen hout snijden als de AND of de OR operator op slechts één item zou werken, dus mogelijk is het verstandig om in gedachten te houden dat er nog steeds bepaalde restricties gelden.


We stellen de ariteit van de operator in door een getal toe te voegen aan de operator. Waarschijnlijk is het ook handig (zoals later zal blijken) dat dit aantal en de operator worden gescheiden met een of ander symbool. We gebruiken hiervoor de dubbele punt ( : ). Omdat de ariteit niet langer op voorhand vastligt, en voor uniformiteit, is het zaak dat alle operatoren deze opmaak volgen, dus ook de NOT operator waarbij de ariteit altijd 1 zal zijn.


Onze nieuwe geserialiseerde expressie, gebaseerd op het bovenstaande voorbeeld en met toevoeging van de ariteiten, wordt dan:



Source Code

Edit Source Code

  1. &:3,1,|:2,2,!:1,3,4



Separation of concerns

Voordat we verdergaan is het zeer belangrijk om twee zaken, die in zekere zin nauw samenhangen, te onderkennen.


Allereerst: security. Het is héél belangrijk dat als we een expressie willen evalueren aan de hand van een set rechten, dat deze syntactisch en semantisch klopt. De functionaliteit die deze evaluatie uitvoert gaat hier ook vanuit. Daarom is het zaak dat ergens voor gebruik de expressie wordt gevalideerd. Een ideale plek om dit te doen is het moment voor opslaan bij de resource waar deze expressie betrekking op heeft. En het is in het algemeen waarschijnlijk ook een goed idee om enkel kloppende expressies op te slaan zodat je hier geen omkijken meer naar hebt.


Ten tweede: performance. Het evalueren van expressies zou zo efficiënt mogelijk moeten verlopen. Door het valideren en evalueren te scheiden kun je hier al een hoop winst boeken. De code die de expressie evalueert gaat er vanuit dat deze klopt en kan daardoor heel kort en to-the-point blijven. Dit houdt dus wel in dat je er echt 100% van uit moet kunnen gaan dat deze expressie aan alle kanten klopt.


Voorwaarts, en terug

We zijn in principe weer terug bij de start: gegeven de definitie van een functie moeten we komen tot een implementatie.



PHP Source Code

Edit Source Code

  1. <?php
  2. // @return bool indicating whether a user with $rights is allowed access based on $expression
  3. function isAllowed($expression, $rights) {
  4. // do magic
  5. }
  6. ?>



De nieuwe implementatie is als volgt:



PHP Source Code

Edit Source Code

  1. <?php
  2. function isAllowed($expression, $rights) {
  3. if ($expression == '') {
  4. return true;
  5. }
  6. $stack = [];
  7. foreach (array_reverse(explode(',', $expression)) as $token) {
  8. if (isset($token[1]) && $token[1] == ':') {
  9. $args = [];
  10. $operator = substr($token, 0, 1);
  11. $count = substr($token, 2);
  12. while ($count--) {
  13. $args[] = array_pop($stack);
  14. }
  15. switch ($operator) {
  16. case '&':
  17. foreach ($args as $val) {
  18. if (!$val) {
  19. $stack[] = false;
  20. break 2;
  21. }
  22. }
  23. $stack[] = true;
  24. break;
  25. case '|':
  26. foreach ($args as $val) {
  27. if ($val) {
  28. $stack[] = true;
  29. break 2;
  30. }
  31. }
  32. $stack[] = false;
  33. break;
  34. case '!':
  35. $stack[] = !$args[0];
  36. break;
  37. }
  38. } else {
  39. $stack[] = isset($rights[$token]);
  40. }
  41. }
  42. return $stack[0];
  43. }
  44. ?>



Nogmaals ten overvloede: deze functie gaat er vanuit dat $expression een geldige expressie (een geserialiseerde rechtenboom in Poolse Notatie) is.


De functie isAllowed() is in grote lijnen hetzelfde. Het enige wat verschilt is het operator token wat nu is opgebouwd uit een symbool ($operator) en een ariteit ($count). Daarnaast halen we in plaats van een vast aantal items -voorheen afhankelijk van de operator- nu $count items van de stack af, berekenen we op grond van de operator het tussenresultaat, en plaatsen we deze terug op de stack. En uiteindelijk retourneren we zoals voorheen het enige overgebleven resultaat op $stack.


Deze implementatie is ontstaan na redelijk wat benchmarks en is eigenlijk nooit af, in die zin dat er vast nog ergens wat performancewinst te boeken valt.


Omdat de AND en OR operatoren nu op een willekeurig aantal items (ten minste twee) van toepassing kan zijn is de berekening van het eindresultaat wat veranderd. In eerste instantie leek dit moeilijk te tacklen maar de uiteindelijke vorm is eigenlijk verbazingwekkend eenvoudig. We kunnen zelfs wat lazy evaluation toepassen bij de berekening van het (tussen)resultaat. We bespreken beide cases kort.



PHP Source Code

Edit Source Code

  1. <?php
  2. case '&':
  3. foreach ($args as $val) {
  4. if (!$val) {
  5. $stack[] = false;
  6. break 2;
  7. }
  8. }
  9. $stack[] = true;
  10. break;
  11. ?>



Wanneer we de AND operatie evalueren moeten alle items gelijk zijn aan true om het eindresultaat ook true te laten zijn. De werking hiervan zou je kunnen vergelijken met de universele kwantor ∀. Als we een item tegenkomen die false is zijn we klaar. Op dat moment kunnen we zowel de uitvoering van de foreach-loop alsook het restant van het case-statement afbreken. Anders, als alle items doorlopen zijn betekent dit dat deze alle true waren en dit is dan ook het enige geval waarin het eindresultaat true is.



PHP Source Code

Edit Source Code

  1. <?php
  2. case '|':
  3. foreach ($args as $val) {
  4. if ($val) {
  5. $stack[] = true;
  6. break 2;
  7. }
  8. }
  9. $stack[] = false;
  10. break;
  11. ?>


Voor de OR operator geldt iets soortgelijks en de werking zou je kunnen vergelijken met de existentiekwantor ∃. Op het moment dat we een item vinden die true is zijn we klaar. Op dat moment breken we zowel de foreach-loop als het case-statement af. Als we alle items doorlopen hebben houdt dat in dat er geen item was die true was. In dat geval retourneren we dan ook false.


Het is prima mogelijk om meer operatoren toe te voegen. Dit omvat het verzinnen van een uniek symbool, het schrijven van een nieuwe case en iets soortgelijks te doen voor het formulierelement in JavaScript, waarover later meer.


Verdere optimalisatie

De bovenstaande code kan verder geoptimaliseerd worden. Zo zou het onderdeel dat betrekking heeft op operatoren (regel 9-37) vervangen kunnen worden door de volgende code:



PHP Source Code

Edit Source Code

  1. <?php
  2. switch (substr($token, 0, 1)) {
  3. case '!':
  4. $result = !array_pop($stack);
  5. break;
  6. case '&':
  7. $result = true;
  8. for ($i = substr($token, 2); $i > 0; $i--) {
  9. if (!array_pop($stack)) {
  10. $result = false;
  11. }
  12. }
  13. break;
  14. case '|':
  15. $result = false;
  16. for ($i = substr($token, 2); $i > 0; $i--) {
  17. if (array_pop($stack)) {
  18. $result = true;
  19. }
  20. }
  21. break;
  22. }
  23. $stack[] = $result;
  24. ?>



In deze variant is het $args hulparray komen te vervallen. Dit resulteert in minder variabelen en schrijfacties en is daardoor iets sneller. Let hierbij op dat we in deze variant de loop niet voortijdig kunnen afbreken omdat er nog steeds een voorgeschreven aantal items (ariteit van de operator) van $stack gehaald moeten worden. Het verschil met de oude variant is hier dat het eindresultaat dat teruggeplaatst wordt op $stack terloops wordt berekend.


Slagen we voor de test?

Het is tijd om wat dingen te gaan testen. Om het overzicht te bewaren over wat de uitkomst van isAllowed() zou moeten zijn loont het de moeite om een waarheidstabel op te stellen.



PHP Source Code

Edit Source Code

  1. <?php
  2. /*
  3. 4 3 2 1 | AND(1,OR(2,NOT(3)),4)
  4. ---------+----------------------
  5. 0 0 0 0 | 0
  6. 0 0 0 1 | 0
  7. 0 0 1 0 | 0
  8. 0 0 1 1 | 0
  9. 0 1 0 0 | 0
  10. 0 1 0 1 | 0
  11. 0 1 1 0 | 0
  12. 0 1 1 1 | 0
  13. 1 0 0 0 | 0
  14. 1 0 0 1 | 1
  15. 1 0 1 0 | 0
  16. 1 0 1 1 | 1
  17. 1 1 0 0 | 0
  18. 1 1 0 1 | 0
  19. 1 1 1 0 | 0
  20. 1 1 1 1 | 1
  21. */
  22. ?>


We verzinnen wat combinatie om deze code te testen:



PHP Source Code

Edit Source Code

  1. ?php
  2. $myRights = array(
  3. 4 => true,
  4. );
  6. if (isAllowed($expression, $myRights)) {
  7. echo '[error] rights: 4; should not be allowed<br />';
  8. } else {
  9. echo 'rights: 4; not allowed<br />';
  10. }
  12. $myRights = array(
  13. 1 => true,
  14. 3 => true,
  15. );
  17. if (isAllowed($expression, $myRights)) {
  18. echo '[error] rights: 1, 3; should not be allowed<br />';
  19. } else {
  20. echo 'rights: 1,3; not allowed<br />';
  21. }
  23. $myRights = array(
  24. 1 => true,
  25. 4 => true,
  26. );
  28. if (isAllowed($expression, $myRights)) {
  29. echo 'rights: 1,4; is allowed<br />';
  30. } else {
  31. echo '[error] rights: 1,4; should be allowed<br />';
  32. }
  34. $myRights = array(
  35. 2 => true,
  36. 4 => true,
  37. );
  39. if (isAllowed($expression, $myRights)) {
  40. echo '[error] rights: 2,4; should not be allowed<br />';
  41. } else {
  42. echo 'rights: 2,4; not allowed<br />';
  43. }
  45. $myRights = array(
  46. 1 => true,
  47. 2 => true,
  48. 3 => true,
  49. );
  51. if (isAllowed($expression, $myRights)) {
  52. echo '[error] rights: 1,2,3; should not be allowed<br />';
  53. } else {
  54. echo 'rights: 1,2,3; not allowed<br />';
  55. }
  56. ?>


Dit levert het volgende resultaat:



Source Code

Edit Source Code

  1. rights: 4; not allowed
  2. rights: 1,3; not allowed
  3. rights: 1,4; is allowed
  4. rights: 2,4; not allowed
  5. rights: 1,2,3; not allowed


Het bouwen van een nieuwe expressie

We zijn aanbeland bij een van de wat moeilijkere onderdelen: het op een gebruiksvriendelijke manier bouwen van een nieuwe expressie. In deze variant, in tegenstelling tot zijn voorganger, is het element volledig met de muis te bedienen, het is niet langer nodig om te typen. We maken hierbij gebruik van jQuery (gebouwd met versie 3.3.1 en verder niet getest met oudere versies maar dit zou geen problemen moeten opleveren) voor eenvoudige(re) manipulatie van het DOM. We hanteren hierbij hetzelfde principe als voorheen: we manipuleren een bulleted list en slaan het resultaat op in een verborgen invoerveld. De code is ook wederom zo opgezet dat deze zich leent voor het makkelijk creëren van meerdere elementen.


Allereerst de JavaScript voor het bouwen van de rechtenboom:



JavaScript Source Code

Edit Source Code

  1. function Rights() {
  2. this.$container = false;
  3. this.$tree = false;
  4. this.$output = false;
  5. this.operators = {};
  6. this.rights = {};
  8. var that = this;
  10. this.init = function(options) {
  11. this.$container = $('#'+options.container);
  12. this.$tree = this.$container.find('ul:first');
  13. this.$output = $('#'+options.output);
  14. this.operators = options.operators;
  15. this.rights = options.rights;
  17. this.$tree.on('click', 'a.js-add-operand', function(e) {
  18. var html =
  19. '<li class="operand">\
  20. <span style="display: none;"></span>\
  21. <select>\
  22. <option value="">- select -</option>';
  23. for (i in that.rights) {
  24. html += '<option value="'+i+'">'+that.rights[i]+'</option>';
  25. }
  26. html +=
  27. '</select>\
  28. <a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>\
  29. <span class="message"></span>\
  30. </li>';
  31. $(this).parent().before(html);
  32. if ($(this).parent().hasClass('js-first-level')) {
  33. $(this).parent().hide();
  34. }
  35. that.generateOutput();
  36. });
  38. this.$tree.on('click', 'a.js-add-operator', function(e) {
  39. var html =
  40. '<li class="operator">\
  41. <span style="display: none;"></span>\
  42. <select>\
  43. <option value="">- select -</option>'
  44. for (i in that.operators) {
  45. html += '<option value="'+i+'">'+that.operators[i]+'</option>';
  46. }
  47. html +=
  48. '</select>\
  49. <a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>\
  50. <span class="message"></span>\
  51. <ul>\
  52. <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>\
  53. </ul>\
  54. </li>';
  55. $(this).parent().before(html);
  56. if ($(this).parent().hasClass('js-first-level')) {
  57. $(this).parent().hide();
  58. }
  59. that.generateOutput();
  60. });
  62. this.$tree.on('click', 'a.js-remove', function(e) {
  63. $(this).parent().remove();
  64. if (that.$tree.find('> li').length == 1) {
  65. that.$tree.find('li.js-first-level').show();
  66. }
  67. that.generateOutput();
  68. });
  70. this.$tree.on('click', 'a.js-edit', function(e) {
  71. var $span = $(this).parent().children(':first');
  72. var $select = $span.next();
  73. var value = $span.attr('data-value');
  74. if ($select.is(':visible') === false) {
  75. if ($span.attr('data-value')) {
  76. $select.find("option[value='"+value+"']").prop('selected', true);
  77. }
  78. } else {
  79. if (typeof value === 'undefined') {
  80. $span.html('<i class="error">empty</i>');
  81. }
  82. }
  83. $span.toggle();
  84. $select.toggle();
  85. });
  87. this.$tree.on('change', 'select', function(e) {
  88. var $span = $(this).prev();
  89. if ($(this).val()) {
  90. $span.attr('data-value', $(this).val());
  91. $span.html($(this).find('option:selected').text());
  92. $span.toggle();
  93. $(this).toggle();
  94. that.generateOutput();
  95. }
  96. });
  98. this.$container.find('a.js-toggle').click(function(e) {
  99. that.$tree.find('span').show();
  100. that.$tree.find('select').hide();
  101. that.$tree.find('li.add').toggle();
  102. if (that.$tree.find('> li').length > 1) {
  103. that.$tree.find('li.js-first-level').hide();
  104. }
  105. that.$tree.find('a.js-edit').toggle();
  106. that.$tree.find('a.js-remove').toggle();
  107. that.$tree.find('li').find('span:first').each(function() {
  108. if (typeof $(this).attr('data-value') === 'undefined') {
  109. $(this).html('<i class="error">empty</i>');
  110. }
  111. });
  112. });
  114. this.$tree.on({
  115. 'mouseenter': function() {
  116. $(this).parent().addClass('delete');
  117. },
  118. 'mouseleave': function() {
  119. $(this).parent().removeClass('delete');
  120. }
  121. }, 'a.js-remove');
  122. } // init
  124. this.generateOutput = function() {
  125. var out = '';
  126. this.$tree.find('li').each(function() {
  127. if ($(this).hasClass('operator')) {
  128. $span = $(this).children(':first');
  129. var value = $span.attr('data-value');
  130. if (false === (value in that.operators)) {
  131. value = 'O'; // placeholder value for operator
  132. }
  133. var children = $(this).find('> ul > li.operator').length + $(this).find('> ul > li.operand').length;
  134. out = out + (out == '' ? '' : ',') + value + ':' + children;
  135. } else if ($(this).hasClass('operand')) {
  136. $span = $(this).children(':first');
  137. var value = $span.attr('data-value');
  138. value = parseInt(value);
  139. if (isNaN(value)) {
  140. value = 'R'; // placeholder value for right
  141. }
  142. out = out + (out == '' ? '' : ',') + value;
  143. }
  144. });
  145. this.$output.val(out);
  146. }
  147. } // function Rights


CSS voor de opmaak:



CSS Source Code

Edit Source Code

  1. div.rights { font-family: sans-serif; font-size: 10pt; color: #000000; }
  2. div.rights ul.tree li { line-height: 25px; list-style: disc; }
  3. div.rights ul.tree span { font-weight: bold; }
  4. 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; }
  5. div.rights a.button:hover { background-color: #ffaaaa; }
  7. div.rights ul.tree .delete span { color: #ff0000; }
  8. div.rights ul.tree .delete select { color: #ff0000; }
  9. div.rights ul.tree .delete i { color: #ff0000; }
  10. div.rights ul.tree .delete a { color: #ff0000; }
  11. div.rights ul.tree .delete li { color: #ff0000; }
  12. div.rights ul.tree li.delete { color: #ff0000; }
  14. div.rights ul.tree span.message { font-weight: normal; font-style: italic; margin-left: 5px; color: #ff0000; }
  15. div.rights ul.tree .error { color: #ff0000; }
  16. div.rights div.toggle { padding: 5px 0; }
  17. div.rights div.validation { width: 300px; border-radius: 15px; padding: 5px; font-weight: bold; text-align: center; }
  18. div.rights div.pass { background-color: #ccffcc; }
  19. div.rights div.fail { background-color: #ffcccc; }


Daarbij een minimale lap HTML voor het opzetten van (placeholders) voor dit formulierelement:



HTML Source Code

Edit Source Code

  1. <div class="rights" id="rights">
  2. <ul class="tree">
  3. <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>
  4. </ul>
  5. <div class="toggle"><a href="javascript:void(0)" class="button js-toggle">toggle</a></div>
  6. <input type="text" name="expression" id="rights_out" value="" size="50" autocomplete="off">
  7. </div>


En uiteindelijk een stukje JavaScript voor het koppelen van de functionaliteit aan dit element:



Source Code

Edit Source Code

  1. <script type="text/javascript">
  2. //<![CDATA[
  3. $().ready(function() {
  4. var rights = new Rights();
  5. rights.init({'container': 'rights', 'output': 'rights_out', 'operators': {"&":"AND","|":"OR","!":"NOT"}, 'rights': {"1":"one","2":"two","3":"three","4":"four"}});
  6. });
  7. //]]>
  8. </script>


Op een soortgelijke manier kun je zoveel elementen creëren als je wilt.


Alle bovenstaande code kun je combineren zodat dit resulteert in een werkend voorbeeld. Als we de expressie uit het begin van dit artikel gebruiken kunnen we bijvoorbeeld de volgende boom bouwen:


tree.png


Het valideren van de expressie in PHP

Omdat de expressies flexibeler zijn dan voorheen kan er ook meer misgaan. Het is om deze reden dat we de validatiefunctie veel en gedetailleerde meldingen laten retourneren.


Naast het vaststellen van de kloppendheid van de expressie doet deze functie zijn best om aan te geven waar dingen precies fout gaan als er fouten optreden. Uiteraard moeten de mensen die werken met deze formulierelementen wel enigszins grip hebben op wat zij aan het doen zijn.



PHP Source Code

Edit Source Code

  1. <?php
  2. function validate($expression, $validOperators, $validRights=[]) {
  3. if ($expression == '') {
  4. return array('valid' => true);
  5. }
  6. $stack = [];
  7. $tokens = array_reverse(explode(',', $expression));
  8. $tokenIndex = count($tokens);
  10. // First pass: syntax
  11. foreach ($tokens as $token) {
  12. $isRight = isRight($token);
  13. $isOperator = isOperator($token);
  14. if ($isRight === false && $isOperator === false) {
  15. return array(
  16. 'valid' => false,
  17. 'syntaxErrors' => true,
  18. 'errors' => array(
  19. 0 => 'could not identify token as either a right id or valid operator on index '.$tokenIndex,
  20. ),
  21. );
  22. }
  23. if ($isOperator) {
  24. list($operator, $count) = explode(':', $token);
  25. if (count($stack) < $count) {
  26. return array(
  27. 'valid' => false,
  28. 'syntaxErrors' => true,
  29. 'errors' => array(
  30. 0 => 'ran out of rights to inspect for operator on index '.$tokenIndex,
  31. ),
  32. );
  33. }
  34. $args = [];
  35. for ($i=0; $i < $count; $i++) {
  36. $args[] = array_pop($stack);
  37. }
  38. }
  39. $stack[] = false; // just put some result boolean back on the stack
  40. $tokenIndex--;
  41. }
  42. if (count($stack) != 1) {
  43. return array(
  44. 'valid' => false,
  45. 'syntaxErrors' => true,
  46. 'errors' => array(
  47. 0 => 'too many rights left on stack; if you have multiple rights on a level an operator should always encapsulate these',
  48. ),
  49. );
  50. }
  52. // Second pass: semantics
  53. $tokenIndex = count($tokens);
  54. $return = array(
  55. 'valid' => false,
  56. 'syntaxErrors' => false,
  57. 'errors' => array(),
  58. );
  59. foreach ($tokens as $token) {
  60. if (strpos($token, ':') == 1) {
  61. // operator
  62. list($operator, $count) = explode(':', $token);
  64. // when you extend this functionality with your own operators you need to add them to $operatorMap
  65. if (array_key_exists($operator, $validOperators) === false) {
  66. $return['errors'][$tokenIndex] = 'operator not set or unknown';
  67. }
  68. switch ($operator) {
  69. case '&':
  70. case '|':
  71. if ($count < 2) {
  72. $return['errors'][$tokenIndex] = 'illegal item count for '.$validOperators[$operator].' operator, need at least two';
  73. }
  74. break;
  75. case '!':
  76. if ($count != 1) {
  77. $return['errors'][$tokenIndex] = 'illegal item count for NOT operator, need exactly one';
  78. }
  79. break;
  80. }
  81. } else {
  82. // right
  83. if (count($validRights) > 0) {
  84. if (isset($validRights[$token]) === false) {
  85. $return['errors'][$tokenIndex] = 'invalid right id';
  86. }
  87. }
  88. if (isIndex($token) === false) {
  89. $return['errors'][$tokenIndex] = 'right not set';
  90. }
  91. }
  92. $tokenIndex--;
  93. }
  94. if (count($return['errors']) == 0) {
  95. $return['valid'] = true;
  96. }
  97. return $return;
  98. }
  99. ?>


Deze functie gebruikt ook de volgende hulpfuncties:



PHP Source Code

Edit Source Code

  1. <?php
  2. function isOperator($in) {
  3. return preg_match('#^\D\:(0|[1-9][0-9]*)$#', $in) === 1;
  4. }
  6. function isIndex($in) {
  7. return preg_match('#^[1-9][0-9]*$#', $in) === 1;
  8. }
  10. function isRight($in) {
  11. return preg_match('#^(R|[1-9][0-9]*)$#', $in) === 1;
  12. }
  13. ?>


Merk op dat zowel isOperator() alsook iSRight() alleen controleren of het token syntactisch correct is, maar niet expliciet of de waarden (symbolen van de operatoren en de id's van de rechten) geldig zijn. Dit zijn dus rudimentaire checks om vast te stellen of de expressie er "goed genoeg" uitziet om een boom (verder uit te) bouwen. Uiteraard worden de symbolen voor de operatoren en optioneel de id's van de rechten op een zeker moment expliciet geïnspecteerd.


De functie validate() valt uiteen in twee delen. Eerst wordt een syntactische controle uitgevoerd. Dit om vast te stellen dat de expressie op zijn minst syntactisch correct is zodat gegarandeerd kan worden dat er een (weliswaar mogelijk incomplete) rechtenboom gerenderd kan worden. Wanneer er fouten in dit onderdeel optreden wordt de controle meteen gestaakt. Dit doen we omdat als er in dit onderdeel sprake is van een fout dan houdt dat in dat de expressie echt ongeldig is en niet te repareren valt. Dit betekent ook dat vanaf dat moment niet meer gegarandeerd kan worden dat de rechtenboom correct gerenderd kan worden. Als we dit onderdeel zonder fouten hebben doorlopen garandeert dit nog steeds niet dat de expressie geldig is, maar het is er op zijn minst een waarmee we verder kunnen werken.


Dit onderdeel controleert:

  • of de tokens (tot op zekere hoogte) geïdentificeerd kunnen worden als ofwel een operator, ofwel een recht id (placeholder waarden worden geaccepteerd)
  • of er op elk moment voldoende items op de stack aanwezig zijn om aan de volgende operator te voeren
  • of er na afloop van het consumeren van de volledige expressie er nog een enkel item op de stack aanwezig is

In het tweede deel wordt de expressie nogmaals doorlopen en worden er een aantal semantische checks uitgevoerd. Deze controles in combinatie met de controles uit het eerste deel garanderen tezamen dat de expressie geldig is. Zoals gezegd, als we door het eerste deel heen waren gekomen dan houdt dit in dat we in ieder geval te maken hebben met een syntactisch correcte, maar wellicht incomplete, expressie. Dus in dat opzicht is het hier niet langer noodzakelijk om het validatieproces te staken op het moment dat we een fout constateren. Deze fouten kunnen we opsparen en in één keer retourneren zodat de gebruiker deze ook in één bewerkingsronde kan oplossen.


Dit onderdeel controleert:

  • of alle operator-symbolen bekend zijn, deze kunnen doorgegeven worden via de parameter $validOperators (array met key-value paren)
  • of alle operatoren acteren op een geldig aantal items
  • (optioneel) of alle rechten id's geldig zijn, deze kunnen opgegeven worden via de optionele parameter $validRights

De functie retourneert een array die altijd een valid index heeft. De waarde van deze index geeft aan of de expressie geldig is. Indien er aan het einde van de rit (na de syntactische en semantische controles) geen fouten zijn opgetreden zal deze index de waarde true krijgen.


Nota bene: de JavaScript functionaliteit zou je in grote lijnen moeten helpen bij het wegsturen van situaties waarin de expressie syntactisch ongeldig is, dus het zou niet mogelijk moeten zijn om met klikacties in de boom een syntactisch ongeldige expressie te genereren die je op den duur zou kunnen buitensluiten van het aanpassen van deze boom.


Echter, als deze waarde false is dan betekent dit dat de expressie ongeldig is. In dit geval zou de expressie niet gebruikt mogen worden voor de evaluatie van gebruikersrechten. Het wordt ook met klem afgeraden niet-kloppende expressies op te slaan in de database. Idealiter zou je altijd ergens de expressie gevalideerd moeten hebben voordat je hier isAllowed() op loslaat.


Zoals al eerder is aangehaald opereert isAllowed() onder de aanname dat de expressie geldig is. Als je probeert een niet-kloppende expressie te evalueren dan is het niet gegarandeerd dat dit de juiste resultaten oplevert. In het ergste geval zal er true geretourneerd worden op het moment dat dit echt niet de bedoeling is.


Indien de status index gelijk is aan false zal het geretourneerde array ook een errors en syntaxErrors index bevatten. De syntaxErrors index bevat een Boolse waarde die aangeeft of er syntaxfouten zijn opgetreden. Dit vormt een mogelijk stopsignaal voor het renderen van de rechtenboom. De errors index bevat een subarray die een lijst van volgnummer-foutmelding paren bevat indien er semantische fouten waren.


Het wijzigen van een bestaande expressie

Het is nog steeds een goed idee om enkel geldige expressies op te slaan zodat als je deze later bewerkt de voorafgedrukte boom ook juist wordt weergegeven.



PHP Source Code

Edit Source Code

  1. <?php
  2. function printTree($expression, $operators, $rights, $messages=array()) {
  3. ?><ul class="tree"><?php
  4. if (empty($expression) === false) {
  5. $stack = [0 => 1]; // depth => #items
  6. $index = 1;
  7. $level = 0;
  8. foreach (explode(',', $expression) as $token) {
  9. if (strpos($token, ':') == 1) {
  10. // operator
  11. list($operator, $count) = explode(':', $token);
  12. $stack[$level]--;
  13. $level++;
  14. $stack[$level] = (int) $count;
  15. if (isset($operators[$operator])) {
  16. $operatorValue = $operator;
  17. $operatorHTML = escape($operators[$operator]);
  18. } else {
  19. $operatorValue = 'O'; // placeholder value
  20. $operatorHTML = '<i class="error">empty</i>';
  21. }
  22. ?><li class="operator">
  23. <span data-value="<?php echo escape($operatorValue); ?>"><?php echo $operatorHTML; ?></span>
  24. <select style="display: none;" rel="display: none;">
  25. <option value="">- select -</option><?php
  26. foreach ($operators as $k => $v) {
  27. ?><option value="<?php echo escape($k); ?>"><?php echo escape($v); ?></option><?php
  28. }
  29. ?></select>
  30. <a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>
  31. <span class="message"><?php
  32. if (isset($messages['errors'][$index])) {
  33. echo escape($messages['errors'][$index]);
  34. }
  35. ?></span>
  36. <ul><?php
  37. } else {
  38. // right/operand
  39. if (isset($rights[$token])) {
  40. $rightValue = $token;
  41. $rightHTML = escape($rights[$token]);
  42. } else {
  43. $rightValue = 'R'; // placeholder value
  44. $rightHTML = '<i class="error">empty</i>';
  45. }
  46. ?><li class="operand">
  47. <span data-value="<?php echo escape($rightValue); ?>"><?php echo $rightHTML; ?></span>
  48. <select style="display: none;">
  49. <option value="">- select -</option><?php
  50. foreach ($rights as $k => $v) {
  51. ?><option value="<?php echo escape($k); ?>"><?php echo escape($v); ?></option><?php
  52. }
  53. ?></select>
  54. <a href="javascript:void(0)" class="button js-edit">✱</a><a class="button js-remove" href="javascript:void(0);">✖</a>
  55. <span class="message"><?php
  56. if (isset($messages['errors'][$index])) {
  57. echo escape($messages['errors'][$index]);
  58. }
  59. ?></span>
  60. </li><?php
  61. // we printed an item, lower stack count of current level
  62. $stack[$level]--;
  63. }
  64. // close levels that have no more items to print
  65. while ($level > 0 && $stack[$level] == 0) {
  66. array_pop($stack);
  67. ?><li class="add">
  68. <a class="button js-add-operator" href="javascript:void(0);">+operator</a><a class="button js-add-operand" href="javascript:void(0);">+right</a>
  69. </li>
  70. </ul></li><?php
  71. $level--;
  72. }
  73. $index++;
  74. }
  75. if (empty($stack) === false) {
  76. while ($level > 0) {
  77. array_pop($stack);
  78. ?><li class="add">
  79. <a class="button js-add-operator" href="javascript:void(0);">+operator</a><a class="button js-add-operand" href="javascript:void(0);">+right</a>
  80. </li>
  81. </ul></li><?php
  82. $level--;
  83. }
  84. }
  85. }
  86. // if the expression is empty, we have visible controls on the top level, otherwise, just hide them
  87. $style = ($expression == '' ? '' : ' style="display: none;"');
  88. ?><li class="add js-first-level"<?php echo $style; ?>>
  89. <a class="button js-add-operator" href="javascript:void(0);">+operator</a><a class="button js-add-operand" href="javascript:void(0);">+right</a>
  90. </li>
  91. </ul>
  92. <div class="toggle"><a href="javascript:void(0)" class="button js-toggle">toggle</a></div><?php
  93. }
  94. ?>


Hiermee kun je een eerder opgeslagen, kloppende, expressie als volgt initialiseren:



PHP Source Code

Edit Source Code

  1. ?php
  2. $expression = '&:3,1,|:2,2,!:1,3,4'; // some valid expression
  3. $operators = ['&' => 'AND', '|' => 'OR', '!' => 'NOT'];
  4. $rights = [1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'];
  5. $messages = validate($expression, $operators);
  6. $printTree = true;
  8. ?><div class="rights" id="rights"><?php
  9. if ($messages['valid'] === false) {
  10. if ($messages['syntaxErrors']) {
  11. ?><div class="validation fail">
  12. <p>Syntax errors occurred, unable to print tree.</p>
  13. </div>
  14. <p>Message: <?php echo escape($messages['errors'][0]) ?></p><p>Expression: <?php echo escape($expression) ?></p><?php
  15. $printTree = false;
  16. } else {
  17. ?><div class="validation fail">
  18. <p>Validation failed, check errors below.</p>
  19. </div><?php
  20. }
  21. } else {
  22. ?><div class="validation pass">
  23. <p>Validation passed!</p>
  24. </div><?php
  25. }
  26. if ($printTree) {
  27. printTree($expression, $operators, $rights, $messages);
  28. }
  29. ?><input type="text" name="expression" id="rights_out" value="<?php echo escape($expression); ?>" size="50" autocomplete="off">
  30. </div>
  31. <script type="text/javascript">
  32. //<![CDATA[
  33. $().ready(function() {
  34. var rights = new Rights();
  35. rights.init({'container': 'rights', 'output': 'rights_out', 'operators': <?php echo json_encode($operators); ?>, 'rights': <?php echo json_encode($rights); ?>});
  36. });
  37. //]]>
  38. </script>


Het bovenstaande fragment bevat de escape() hulpfunctie voor het escapen van data binnen de HTML-context:



PHP Source Code

Edit Source Code

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



MySQL implementatie

Het is ook zinnig om een MySQL implementatie van deze functionaliteit te hebben. Bijvoorbeeld voor het genereren van gepagineerde lijsten van items waar jij toegang toe hebt. Als je dit niet aan de database-kant zou kunnen filteren dan zou je dit alsnog aan de PHP-kant moeten doen. Ook zou je dan alle items op moeten halen omdat je niet op voorhand weet wat je zou mogen inzien of gebruiken. Daarnaast wordt het berekenen van alle pagina's een moeilijke klus waarbij je eigenlijk alle pagina's zou moeten genereren, in plaats van enkel de actuele. Zonder een implementatie aan de MySQL-kant dreigt dus het gevaar dat het gebruik van deze rechtenfunctionaliteit traag en complex wordt.


Uiteindelijk willen we een MySQL FUNCTION die we aan kunnen roepen waarbij de expressie (expression) wordt toegepast op een verschafte (geserialiseerde) lijst van rechten (rights). Het is echter vrij onmogelijk om fatsoenlijke feedback te krijgen tijdens de ontwikkeling van zo'n FUNCTION. Daartoe gebruiken we voor de ontwikkeling in plaats van een FUNCTION een PROCEDURE. Dit stelt ons continu in staat om rechtstreeks inzicht te verkrijgen over de interne toestand wat het vervolgens vele malen makkelijker maakt om SQL-code te ontwikkelen en te debuggen. Dit omdat je toch enige zekerheid wilt hebben dat deze functionaliteit enigszins klopt ;).


Disclaimer: ik heb er wel vertrouwen in, maar deze PROCEDURE en FUNCTION zijn in zekere zin nog wat experimenteel. Ga hier voorzichtig mee om.


Allereerst bouwen we dus een PROCEDURE met een hele hoop terugkoppeling:



SQL-Query

Edit Source Code

  1. DELIMITER ;;
  2. DROP PROCEDURE IF EXISTS is_allowed;;
  3. CREATE PROCEDURE is_allowed(expression VARCHAR(255), rights VARCHAR(255))
  4. BEGIN
  5. DECLARE stack VARCHAR(255);
  6. DECLARE token VARCHAR(25);
  7. DECLARE count INT(3) UNSIGNED;
  8. DECLARE i INT(3) UNSIGNED;
  9. DECLARE result BOOL;
  10. IF (expression = '') THEN
  11. SET stack = '1';
  12. SELECT CONCAT('empty expression') AS feedback;
  13. ELSE
  14. SET stack = '';
  15. SET expression = REVERSE(expression);
  16. END IF;
  17. WHILE (LENGTH(expression) > 0) DO
  18. SET token = REVERSE(SUBSTRING_INDEX(expression, ',', 1));
  19. SET expression = SUBSTRING(expression, LENGTH(token) + 2);
  20. IF (LOCATE(':', token) = 0) THEN
  21. SET stack = CONCAT(FIND_IN_SET(token, rights) > 0, stack);
  22. SELECT CONCAT('right found: ', token,', stack: ', stack) AS feedback;
  23. ELSE
  24. SET count = SUBSTRING_INDEX(token, ':', -1);
  25. SET token = SUBSTRING(token, 1, 1);
  26. SELECT CONCAT('operator found: ', token, ', count: ', count) AS feedback;
  27. IF (token = '!') THEN
  28. SET result = 1 - SUBSTRING(stack, 1, 1);
  29. ELSEIF (token = '&') THEN
  30. SET result = TRUE;
  31. SET i = 1;
  32. WHILE (i <= count AND result) DO
  33. IF (SUBSTRING(stack, i, 1) = 0) THEN
  34. SELECT CONCAT('found FALSE on index ', i, ' exiting') AS feedback;
  35. SET result = FALSE;
  36. END IF;
  37. SET i = i + 1;
  38. END WHILE;
  39. ELSEIF (token = '|') THEN
  40. SET result = FALSE;
  41. SET i = 1;
  42. WHILE (i <= count AND result = FALSE) DO
  43. IF (SUBSTRING(stack, i, 1) = 1) THEN
  44. SELECT CONCAT('found TRUE on index ', i, ' exiting') AS feedback;
  45. SET result = TRUE;
  46. END IF;
  47. SET i = i + 1;
  48. END WHILE;
  49. END IF;
  50. SET stack = CONCAT(result, SUBSTRING(stack, count + 1));
  51. SELECT CONCAT('stack after processing: ', stack) AS feedback;
  52. END IF;
  53. END WHILE;
  54. SELECT CONCAT('final result: ', stack) AS feedback;
  55. END;;
  56. DELIMITER ;


Op deze manier kunnen we exact volgen welk intern pad wordt bewandeld binnen deze code. Roepen we deze PROCEDURE bijvoorbeeld als volgt aan:



SQL-Query

Edit Source Code

  1. CALL is_allowed('&:3,51,|:2,52,!:1,53,54', '51,54');



Dan resulteert dit (met enige opschoning) de volgende feedback:



Source Code

Edit Source Code

  1. right found: 54, stack: 1
  2. right found: 53, stack: 01
  3. operator found: !, count: 1
  4. stack after processing: 11
  5. right found: 52, stack: 011
  6. operator found: |, count: 2
  7. found TRUE on index 2 exiting
  8. stack after processing: 11
  9. right found: 51, stack: 111
  10. operator found: &, count: 3
  11. stack after processing: 1
  12. final result: 1


Een aanroep van:



SQL-Query

Edit Source Code

  1. CALL is_allowed('&:3,51,|:2,52,!:1,53,54', '51,53');



Levert de volgende feedback op:



Source Code

Edit Source Code

  1. right found: 54, stack: 0
  2. right found: 53, stack: 10
  3. operator found: !, count: 1
  4. stack after processing: 00
  5. right found: 52, stack: 000
  6. operator found: |, count: 2
  7. stack after processing: 00
  8. right found: 51, stack: 100
  9. operator found: &, count: 3
  10. found FALSE on index 2 exiting
  11. stack after processing: 0
  12. final result: 0


Na een aantal iteraties kun je dit vrijwel 1:1 converteren naar een vrijwel identieke FUNCTION:



SQL-Query

Edit Source Code

  1. DELIMITER ;;
  2. DROP FUNCTION IF EXISTS is_allowed;;
  3. CREATE FUNCTION is_allowed(expression VARCHAR(255), rights VARCHAR(255)) RETURNS BOOL DETERMINISTIC
  4. BEGIN
  5. DECLARE stack VARCHAR(255);
  6. DECLARE token VARCHAR(25);
  7. DECLARE count INT(3) UNSIGNED;
  8. DECLARE i INT(3) UNSIGNED;
  9. DECLARE result BOOL;
  10. IF (expression = '') THEN
  11. RETURN TRUE;
  12. END IF;
  13. SET stack = '';
  14. SET expression = REVERSE(expression);
  15. WHILE (LENGTH(expression) > 0) DO
  16. SET token = REVERSE(SUBSTRING_INDEX(expression, ',', 1));
  17. SET expression = SUBSTRING(expression, LENGTH(token) + 2);
  18. IF (LOCATE(':', token) = 0) THEN
  19. SET stack = CONCAT(FIND_IN_SET(token, rights) > 0, stack);
  20. ELSE
  21. SET count = SUBSTRING_INDEX(token, ':', -1);
  22. SET token = SUBSTRING(token, 1, 1);
  23. IF (token = '!') THEN
  24. SET result = 1 - SUBSTRING(stack, 1, 1);
  25. ELSEIF (token = '&') THEN
  26. SET result = TRUE;
  27. SET i = 1;
  28. WHILE (i <= count AND result) DO
  29. IF (SUBSTRING(stack, i, 1) = 0) THEN
  30. SET result = FALSE;
  31. END IF;
  32. SET i = i + 1;
  33. END WHILE;
  34. ELSEIF (token = '|') THEN
  35. SET result = FALSE;
  36. SET i = 1;
  37. WHILE (i <= count AND result = FALSE) DO
  38. IF (SUBSTRING(stack, i, 1) = 1) THEN
  39. SET result = TRUE;
  40. END IF;
  41. SET i = i + 1;
  42. END WHILE;
  43. END IF;
  44. SET stack = CONCAT(result, SUBSTRING(stack, count + 1));
  45. END IF;
  46. END WHILE;
  47. RETURN stack;
  48. END;;
  49. DELIMITER ;



Daarna zou je nog wat tests kunnen uitvoeren net als bij de PHP-variant:



Source Code

Edit Source Code

  1. > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '54') AS test;
  2. +------+
  3. | test |
  4. +------+
  5. | 0 |
  6. +------+
  7. 1 row in set (0.01 sec)
  9. > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '51,53') AS test;
  10. +------+
  11. | test |
  12. +------+
  13. | 0 |
  14. +------+
  15. 1 row in set (0.00 sec)
  17. > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '51,54') AS test;
  18. +------+
  19. | test |
  20. +------+
  21. | 1 |
  22. +------+
  23. 1 row in set (0.00 sec)
  25. > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '52,54') AS test;
  26. +------+
  27. | test |
  28. +------+
  29. | 0 |
  30. +------+
  31. 1 row in set (0.00 sec)
  33. > SELECT is_allowed('&:3,51,|:2,52,!:1,53,54', '51,52,53') AS test;
  34. +------+
  35. | test |
  36. +------+
  37. | 0 |
  38. +------+
  39. 1 row in set (0.00 sec)



Merk op dat ik hier expres wat grotere rechten id's (groter dan 9) test in MySQL. Dit omdat wanneer je REVERSE() toepast op een string in MySQL, dit de hele string omdraait, dus ook de cijfers waaruit de rechten zijn opgebouwd, en niet enkel de volgorde van items in een lijst zoals bij array_reverse() in PHP het geval is. MySQL kent het type array niet wat voor wat uitdagingen zorgt.