login  Naam:   Wachtwoord: 
Registreer je!
 Forum

eenvoudige maar flexibele ACL

Offline Thomas - 26/08/2014 11:13 (laatste wijziging 12/09/2014 17:53)
Avatar van ThomasModerator EDIT: >hier< kun je de laatste versie in actie zien.

Nota bene: dit idee is verre van origineel. Ik heb hier al een soortgelijke uitwerking van in gebruik gezien, dus het lijkt mij zeker iets wat inzetbaar is.

Het idee
Okay, waar te beginnen. Ik heb een aantal resources, denk bijvoorbeeld aan een webpagina, een artikel, een geupload bestand. Op grond van rollen/rechten (of hoe je het ook wilt noemen) die ik toeken aan een gebruiker wil ik bepalen of zo iemand (een geauthoriseerde gebruiker) toegang heeft tot deze resource. De controle hierop zal een of andere boolse expressie (een predikaat) zijn. Het antwoord op de vraag "heeft gebruiker X toegang tot resource Y" is dus altijd ja (true) of nee (false) als antwoord. Nu is de vraag dus, hoe implementeer ik dit precies (op een transparante, eenvoudige manier)?

Ik heb al even zitten zoeken. Het Yii framework gebruikt bijvoorbeeld "business rules", een soort van snippets code die geëvalueerd worden om te bepalen of iemand toegang heeft, in combinatie met het definiëren en toekennen van rollen/rechten/whatever. Zoiets wil ik ook, maar het wordt al snel één grote brei in Yii volgens mij, vooral als je niet heel strak je naamgeving regelt.

Het liefst sla ik de controle (zo dicht mogelijk) bij de resource zelf op. Maar hoe doe ik dat? Een lap code in de database (bleh) die je vervolgens evalueert (bleeehhhh). Vrij belangrijk hierbij is het formaat: hoe ziet de controle (het predikaat) er uit en is dit een "nette" oplossing (geen eval() en dat soort voodoo).

Theorie
Aan de hand van een uitwerking die ik ergens ooit heb gezien (die ik nooit echt inhoudelijk heb bekeken of begrepen) moest ik terugdenken aan mijn studententijd, waarin ik ooit een soort van geserialiseerde notatie voor (wiskundige) expressies de revue heb zien passeren. Dit betrof de (Poolse) prefix notatie.

In het WIKI-artikel staan een aantal interessante/belangrijke concepten:
- de prefix notatie is een schrijfwijze voor logica, wiskunde en algebra
- het plaatst operatoren (+, -, ...) links van haar operanden (3, -2, ...)
- als de ariteit van de operatoren (de hoeveelheid operanden waarop een operator werkt) vastligt, dan resulteert dit in een syntax die geen haken of andere groepeersymbolen nodig heeft waarbij expressies nog steeds ondubbelzinnig geïnterpreteerd (geparsed) kunnen worden

Dit laatste is een interessant gegeven, de waarheidstabel van het predikaat A && (B || C) ziet er namelijk heel anders uit dan (A && B) || C terwijl het, afgezien van de haken, dezelfde expressie is.

Dus wat heb ik nu eigenlijk? De operatoren voor de te bouwen expressie voor het controleren van rechten zijn de logische AND, de logische OR en de negatie (meestal geschreven als ! of ¬). Deze negatie wil ik zowel kunnen laten werken op een operand (!A) of een verzameling hiervan (!(A && B)). (En ja deze laatste variant kun je weer omschrijven naar !A || !B (DeMorgan)).

Hierbij pin ik de ariteit van de operatoren vast op (maximaal) 2 (de negatie werkt maar op één operand (een verzameling van operanden is (vereenvoudigd) ook weer een operand)).

De WIKI geeft tevens een (abstracte) implementatie van de Poolse notatie met behulp van een stack:
Citaat:
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


De uitwerking (theoretisch)
Wat wil ik vervolgens kunnen doen? Ik wil mijn predikaat geserialiseerd opslaan bij mijn resource. Ik zal dus moeten kiezen voor een notatiewijze. In eerste instantie moet ik onderscheid kunnen maken tussen de verschillende onderdelen (tokens) in de expressie. Hiertoe kies ik een scheidingskarakter, bijvoorbeeld de komma (,). Daarnaast heb ik symbolen nodig voor mijn operatoren. Bijvoorbeeld ! voor de negatie, | voor de logische OR en & voor de logische AND. En tot slot zijn daar de operanden: de rechten waar ik op wil kunnen controleren, deze zullen in eerste instantie enkel vertegenwoordigd worden door getallen. Dit zijn indexen van de rechten id's. Maar dit kan veel diverser als je wilt, je zou bijvoorbeeld onderscheid kunnen maken tussen groepsrechten (geef een id een G prefix) en gebruikersrechten (geef een id een U prefix) - de mogelijkheden zijn onbeperkt, je kunt je eigen definities verzinnen.

Een voorbeeld: het predikaat !(A || B) && (C || (D && E)) zou je dan als volgt schrijven in mijn variant van de Poolse notatie:
&,!|,A,B,|,C,&,D,E
Het vereist wat oefening om deze omzetting te doen. De truc is om de expressie van rechts naar links om te zetten en hierbij kan het handig zijn om alle gegroepeerde (deel)expressies eerst naar rechts de verplaatsen. Dit mag, immers:
(A || B) && C
is equivalent aan
C && (A || B)
(oftewel && (en ook ||) is commutatief)

Dan zijn er eigenlijk twee bewerkingen die ik wil kunnen doen:
1. een controle die kijkt of de Poolse notatie syntactisch klopt, je wilt hier namelijk van uit kunnen gaan als je deze gaat valideren. Een goede plaats om deze controle uit te voeren is als je de controle wegschrijft bij de resource. Dit kun je verifiëren door:
- te kijken of de expressie uit enkel toegestane karakters bestaat
- vanwege de ariteit is de volgende regel "invariant": het aantal operatoren (met uitzondering van de negatie) moet gelijk zijn aan het aantal operanden + 1

Hieruit volgt een klein dilemma in combinatie met de stack-implementatie hierboven: wat nu als je maar één recht hebt waar je op controleert? De "stack" zou tijdens verwerking te allen tijde minimaal twee waarden moeten bevatten, maar je hebt dan maar één operand.

Praktische oplossing: stel je hebt het predikaat A. Dit is hetzelfde als A && True (en ook A && True && True et cetera). Oftewel: plak aan je expressie "&& True" vast. Hiermee verander je de werking niet, maar zorg je wel dat dit altijd werkt, ook met slechts één operand (recht) waar je op controleert.

en 2, waar het eigenlijk allemaal om begonnen was: een (enkele, eenvoudige) controle die de expressie toepast op de gebruikersrechten die iemand heeft, en op grond hiervan besluit of iemand toegang heeft tot de resource, of niet.

Een uitwerking (praktijk)
Hieronder de twee eerder genoemde bewerkingen (mogelijk kunnen deze nog gerefactord worden) en een hulpfunctie:
  1. <?php
  2. // helper
  3. function validateNumber($in) {
  4. return preg_match('#^[1-9][0-9]*$#', $in);
  5. }
  6.  
  7. function validateSerializedString($in) {
  8. // empty string is always correct
  9. if ($in == '') {
  10. return true;
  11. }
  12. $operators = 0; // the added & operator will be counted automatically below
  13. $operands = 1; // the added "true" on the (imaginary) stack
  14.  
  15. // we add "&& true" to ensure at least two operands ($in could consist of exactly one right)
  16. $in = explode(',', '&,'.$in); // mind the prefixed "&,"
  17.  
  18. foreach ($in as $token) {
  19. $current = $token;
  20. if ($token{0} == '!') {
  21. $current = substr($token, 1);
  22. }
  23. if ($current == '|' || $current == '&') {
  24. $operators++;
  25. } elseif (validateNumber($current)) {
  26. $operands++;
  27. } else {
  28. // illegal character (sequence)
  29. return false;
  30. }
  31. }
  32. return ($operators + 1 == $operands);
  33. }
  34.  
  35. function isAllowed($in, $rights=array()) {
  36. if ($in == '') {
  37. return true;
  38. }
  39. // we add "&& true" to ensure at least two operands ($in could consist of exactly one right)
  40. $stack = array(true);
  41. $in = array_reverse(explode(',', '&,'.$in)); // read from back to front, mind the prefixed "&,"
  42. foreach ($in as $token) {
  43. $negate = false;
  44. $current = $token;
  45. if ($token{0} == '!') {
  46. $negate = true;
  47. $current = substr($token, 1);
  48. }
  49. if ($current == '|' || $current == '&') {
  50. // $stack should have at least two items - validation should guarantee this
  51. // note that $val1 and $val2 already are boolean values (true or false)
  52. $val1 = array_pop($stack);
  53. $val2 = array_pop($stack);
  54. // calculate new value to put back on the stack
  55. $value = ($current == '|' ? $val1 || $val2 : $val1 && $val2);
  56. } elseif (validateNumber($current)) {
  57. // add a boolean to the stack indicating whether the user has this right
  58. $value = in_array($current, $rights);
  59. }
  60. // put (intermediate) result back on the stack
  61. $stack[] = ($negate ? !$value : $value);
  62. }
  63. // after this loop $stack should have exactly 1 value - the validation should guarantee this
  64. return $stack[0];
  65. }
  66. ?>


Een voorbeeld:
Gegeven de "validatieregel" (A || B) && (C || D) waarbij A, B, C en D rechten voorstellen. Je zou dan toegang moeten hebben tot de bijbehorende resource indien de gebruiker een van de volgende (minimale) combinaties van rechten heeft:
A,C (en eventueel B of D)
A,D (en eventueel B of C)
B,C (en eventueel A of D)
B,D (en eventueel A of C)

De bijbehorende Poolse notatie is:
&,|,A,B,|,C,D

Neem voor de operanden A, B, C, D respectievelijk de id's 1, 2, 3, 4.

En de test (varieer $userRights en bekijk het resultaat):
  1. <?php
  2. $userRights = array('2', '4');
  3. $accessRights = '&,|,1,2,|,3,4'; // (1 | 2) & (3 | 4)
  4.  
  5. // normally, you check this when storing the access rights
  6. if (validateSerializedString($accessRights)) {
  7. if (isAllowed($accessRights, $userRights)) {
  8. echo 'authorized';
  9. } else {
  10. echo 'unauthorized';
  11. }
  12. } else {
  13. // complain (e.g. throw exception)
  14. die('did not validate');
  15. }
  16. ?>


Wat vinden jullie van dit idee? Overigens, het parsen van de accessrights zou je ook met enige moeite onder kunnen brengen in MySQL zelf, bijvoorbeeld in een stored procedure, zodat je direct records zou kunnen controleren of je deze (gegeven een userid) in zou mogen zien. Je kunt dat dan dus al doen tijdens het ophalen van records, als conditie in de query.

Dit alles vormt een eenvoudig maar toch vrij krachtig mechanisme voor het toekennen/ontzeggen van toegang tot resources.

EDIT: (refactoring) regel 56 uit het bovenstaande fragment zou je om kunnen zetten in een simpele "else", het token moet op dat moment uit een getal bestaan, de voorgaande validatie zou dit moeten garanderen.

EDIT2: De "uitdaging" zal dus vooral zitten in het maken van een gebruiksvriendelijke interface voor het definiëren / bouwen van de toegangsrechten, die daarna omgezet moeten worden tot een geldige geserialiseerde notatie. Maar in eerste instantie zou je dit dus ook "rauw" kunnen doen . Met name als je complexe toegangsrechten hebt, zul je toch al redelijk goed moeten weten wat je aan het doen bent.

EDIT3: (refactoring) regel 58: en als je de rechten van gebruikers opslaat als keys kun je in_array() vervangen door isset() of array_key_exists().

EDIT4: regel 8 t/m 11 toegevoegd aan validatie: een lege rechten-string is altijd goed (true) en hoeft niet verder gecontroleerd te worden.

4 antwoorden

Gesponsorde links
Offline Wijnand - 01/09/2014 09:09
Avatar van Wijnand Moderator Ik heb 'm gelezen (een paar dagen geleden), maar zal 'm nog eens lezen en eventueel meedenken.

Maar dan weet je dat het er niet helemaal voor nop op staat .
Offline Thomas - 01/09/2014 12:05 (laatste wijziging 01/09/2014 14:47)
Avatar van Thomas Moderator De "uitdaging" (het maken van een gebruiksvriendelijke interface voor het definiëren / bouwen van de toegangsrechten, die daarna omgezet moeten worden tot een geldige geserialiseerde notatie) is inmiddels ook aardig gelukt. Hiertoe heb ik de implementatie van de PHP-functies een klein beetje aangepast. Ik beschouw de negatie (!) nu als een apart token. Hiermee wordt de PHP implementatie aldus:
  1. function validateSerializedString($expression) {
  2. if ($expression == '') {
  3. return true;
  4. }
  5. $operators = 0; // the added & operator will be counted automatically below
  6. $operands = 1; // the added "true" on the (imaginary) stack
  7.  
  8. // we add "&& true" to ensure at least two operands ($expression could consist of exactly one right)
  9. $tokens = explode(',', '&,'.$expression); // mind the prefixed "&,"
  10.  
  11. foreach ($tokens as $token) {
  12. if ($token == '&' || $token == '|') {
  13. $operators++;
  14. } elseif ($token == '!') {
  15. // do not count the ! token
  16. } elseif (validateNumber($token)) {
  17. $operands++;
  18. } else {
  19. // illegal character (sequence)
  20. return false;
  21. }
  22. }
  23. return ($operators + 1 == $operands);
  24. }
  25.  
  26. function isAllowed($expression, $rights=array()) {
  27. if ($expression == '') {
  28. return true;
  29. }
  30. // we add "&& true" to ensure at least two operands ($expression could consist of exactly one right)
  31. $stack = array(true);
  32. $tokens = array_reverse(explode(',', '&,'.$expression)); // read from back to front, mind the prefixed "&,"
  33. foreach ($tokens as $token) {
  34. if ($token == '&' || $token == '|') {
  35. // $stack should have at least two items - validation should guarantee this
  36. // note that $val1 and $val2 already are boolean values (true or false)
  37. $val1 = array_pop($stack);
  38. $val2 = array_pop($stack);
  39. // calculate new value to put back on the stack
  40. $stack[] = ($token == '|' ? $val1 || $val2 : $val1 && $val2);
  41. } elseif ($token == '!') {
  42. // negate whatever is on the top of the stack
  43. $stack[count($stack)-1] = !($stack[count($stack)-1]);
  44. } else {
  45. // this is a number, validation should guarantee this!
  46. // add a boolean to the stack indicating whether the user has this right
  47. $stack[] = in_array($token, $rights);
  48. }
  49. }
  50. // after this loop $stack should have exactly 1 value - the validation should guarantee this
  51. return $stack[0];
  52. }

Zoals je ziet is de negatie van toepassing op het bovenste (resultaat)element op de stack.

Vervolgens het HTML/jQuery ding voor het bouwen van de logische boom (code volgt na de toelichting), hierin zijn uiteraard weer enkele problemen .

De opsteller van de boom zou in principe alle mogelijke bomen die hij/zij kan verzinnen mogen bouwen, echter, als je een boom als volgt opbouwt, wordt het uitleesproces nogal lastig:
  1. AND
  2. +----OR
  3. | +----[A]
  4. | +----[B]
  5. |
  6. +----[C]

Je moet dan namelijk operators soms gaan prefixen, soms gaan postfixen, kortom je moet een heleboel beslissingen nemen. Uiteindelijk wil je dat het uitleesresultaat er zo uitziet:
  1. AND,C,OR,A,B

Want zo heb je een ondubbelzinnige prefix notatie ((inverse) Poolse notatie).

Het liefste had je dus gehad dat de opsteller van de boom deze als volgt in elkaar had gezet:
  1. AND
  2. +----[C]
  3. |
  4. +----OR
  5. . +----[A]
  6. . +----[B]

Het uitleesproces was dan SUPER simpel geweest, je kunt dan de boom gewoon van onder naar boven uitlezen! Merk hierbij op dat je A en B kunt verwisselen vanwege de commutativiteit van OR (en AND), oftewel A OR B is equivalent aan B OR A.

Maar je wilt dit niet aan een gebruiker opleggen om bomen in een bepaalde voorgeschreven vorm op te stellen.

Daartoe heb ik de volgende "slimmigheid" ingebouwd: indien een tak van de boom van een "samengesteld" type (AND, OR) is, en het tweede kind-element een simpel (niet-samengesteld) element is en het eerste kind-element een "complex" (samengesteld) element is, dan draai ik deze twee om. Op deze manier kan ik dus de eerste boom omzetten naar de tweede boom en vervolgens kan ik deze dus in een ruk van achter naar voren uitlezen.

Hiermee kom ik tot de volgende implementatie in HTML/jQuery:
EDIT: het omdraaien van boomfragmenten bleek bij nader inzien niet (meer) nodig, zie notities achteraan.
  1. <!DOCTYPE html>
  2. <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
  3. <title>tree</title>
  4. <script type="text/javascript" src="http://code.jquery.com/jquery-1.11.1.min.js"></script>
  5. <style type="text/css">
  6. li.red > span { color: #ff0000; }
  7. </head>
  8.  
  9. <div id="tree_container">
  10. <ul id="tree">
  11. <li><span>empty</span></li>
  12. </ul>
  13. </div>
  14. <p><em>Click on a list item to edit it. Special values: AND, OR, NOT (case sensitive)</em></p>
  15. <button type="button" id="daddy">parents</button>
  16. <button type="button" id="notation">notation</button>
  17. <br />
  18. <textarea id="pn" rows="10" cols="50"></textarea>
  19.  
  20. <script type="text/javascript">
  21. //<![CDATA[
  22. // https://github.com/janl/mustache.js/blob/master/mustache.js
  23. var entityMap = {
  24. "&": "&amp;",
  25. "<": "&lt;",
  26. ">": "&gt;",
  27. '"': '&quot;',
  28. "'": '&#39;',
  29. "/": '&#x2F;'
  30. };
  31. function escapeHtml(string) {
  32. return String(string).replace(/[&<>"'\/]/g, function (s) {
  33. return entityMap[s];
  34. });
  35. }
  36.  
  37. $().ready(function() {
  38. // click event function for building a logical tree
  39. var handleclick = function(e) {
  40. // prevent the click event to bubble to the parent when clicking on input
  41. // so parent li clicks do not get triggered again
  42. e.stopPropagation();
  43.  
  44. var $element = $(this);
  45. var go = false;
  46. if ($element.has('ul').length) {
  47. go = confirm('editing this element will cause the child elements to be deleted; proceed?');
  48. } else {
  49. go = true;
  50. }
  51.  
  52. if (go) {
  53. var value = $element.find('span').first().text();
  54. // @todo the next line might remove an entire subtree, do anything to save or cleanup items/events?
  55. var $html = $('<input type="text" value="" />').val(value);
  56.  
  57. $html.click(function(e) {
  58. // so it does not trigger click event of direct parent li
  59. e.stopPropagation();
  60. });
  61.  
  62. $html.blur(function() {
  63. var value = $(this).val();
  64. if (value == '') {
  65. value = 'empty';
  66. }
  67. $element.html('<span>'+escapeHtml(value)+'</span>');
  68. if (value == 'AND' || value == 'OR') {
  69. $ul = $('<ul></ul>');
  70. $ul.append($('<li><span>empty</span></li>').click(handleclick));
  71. $ul.append($('<li><span>empty</span></li>').click(handleclick));
  72. $element.append($ul);
  73. } else if (value == 'NOT') {
  74. $ul = $('<ul></ul>');
  75. $ul.append($('<li><span>empty</span></li>').click(handleclick));
  76. $element.append($ul);
  77. }
  78. });
  79.  
  80. $element.html($html);
  81. $html.focus();
  82. } // go
  83. } // handleclick
  84.  
  85. // onload event: add clickevents to initial present list items (serves as init)
  86. $('#tree li').click(handleclick);
  87.  
  88. $('#daddy').click(function() {
  89. // *ugh* how to select all first list items of an <ul> that contain an <ul>?
  90. $('#tree_container').find('ul').each(function() {
  91. // check if a direct descendant is a parent too
  92. $(this).children('li').each(function() {
  93. // reset
  94. $(this).removeClass('red');
  95.  
  96. // first element always is a span
  97. // note the .length element, if omitted, it returns true regardless of whether
  98. // the element actually has a ul within
  99. if ($(this).has('ul').length) {
  100. $(this).addClass('red');
  101. }
  102. });
  103. });
  104. });
  105.  
  106. $('#notation').click(function() {
  107. var out = '';
  108. // first we check if we need to rearrange the tree
  109. // we need the simple (non compound) statement in front
  110. // NOT NEEDED
  111. /*
  112. $('#tree_container').find('ul').each(function() {
  113. var $children = $(this).children('li');
  114. if ($children.length == 2) {
  115. var $child2 = $children.eq(1);
  116. var value = $child2.find('span').html();
  117. if (value == 'AND' || value == 'OR') {
  118. // compound statement, do nothing
  119. } else {
  120. // second element is simple, check first
  121. var $child1 = $children.eq(0);
  122. var value = $child1.find('span').html();
  123. // if the first element is complex, we need to swap
  124. if (value == 'AND' || value == 'OR') {
  125. // x.before(y) = put y before x
  126. $child1.before($child2);
  127. } else {
  128. // both elements simple, swapping not needed after all
  129. }
  130. }
  131. }
  132. });
  133. */
  134. // next we read the tree from back to front
  135. // NOT NEEDED
  136. // $($('#tree li span').get().reverse()).each(function() {
  137. $('#tree li span').each(function() {
  138. // NOT NEEDED
  139. // out = $(this).text()+(out == '' ? '' : ',')+out;
  140. out = out+(out == '' ? '' : ',')+$(this).text();
  141. });
  142. // output the generated string
  143. $('#pn').val(out);
  144. });
  145. });
  146. //]]>
  147. </body>
  148. </html>

Hiermee heb ik dus effectief het opstellen (op een redelijk gebruiksvriendelijke manier, die nog verder uitgewerkt kan worden) en het uitlezen (in PHP) bij elkaar gebracht.

EDIT: HTML/jQuery aangepast:
- escaping van karakters gaat nu... beter 
- de gebruiker krijgt een bevestiging voordat een subboom wordt weggekieperd wanneer deze op een AND- of OR-tak klikt

EDIT: de volgende notatie (eerste boom) voldeed in principe ook:
  1. AND,OR,A,B,C

Huh, misschien was die omdraaiing helemaal niet nodig .
EDIT: de omdraaiing lijkt inderdaad niet (meer) nodig, dit is voornamelijk te danken aan het apart schrijven van de NOT operator (denk ik, lol). Voorheen was het lastig om zoiets te doen:
  1. !(A | B | C)

omdat de NOT aan de buitenste OR werd gekoppeld. Je kwam dan in de problemen met C (een derde operand). Door de NOT apart te zetten heb je dit probleem niet meer. De jQuery wordt hierdoor (stukken) simpeler.
Offline Wijnand - 01/09/2014 13:07
Avatar van Wijnand Moderator Ik moet altijd lachen van jouw zinnen. Ik begrijp je code vaak wel, maar je zinnen niet :-).

Ik ga reageren zodra ik met google.nl:definities heb uitgezocht wat worden zoals negatie, commutativiteit en dergelijke woorden betekenen.

Offline Thomas - 02/09/2014 14:21 (laatste wijziging 28/03/2015 16:28)
Avatar van Thomas Moderator EDIT #2: In de MySQL functie staat het token achterstevoren als deze uit meer dan 1 karakter bestaat (als dit bijvoorbeeld recht-nummers betreft groter dan 9), dit omdat je expression aan het begin REVERSEd. Hiertoe moet je het token ook REVERSEn (inmiddels in onderstaande code aangepast).

EDIT: shameless bump; aan het einde staat een MySQL functie die hetzelfde doet, want soms wil je misschien op voorhand opgehaalde resultaten filteren op grond van de rechten die iemand heeft.

En dan nog het laatste stukje, om een eerder opgeslagen expressie weer uit te lezen en om te zetten in een geneste bulleted list. Om e.e.a. bij te houden en makkelijk (recursief) te doorlopen bij het afdrukken van de lijst zetten we dit in een class:

  1. <?php
  2. class RightsTree
  3. {
  4. protected $_tree;
  5.  
  6. public function __construct($expression) {
  7. $this->_tree = $this->buildTree($expression);
  8. }
  9.  
  10. protected function buildTree($input) {
  11. $tree = array(); // result array
  12. $freeSpots = array(0 => 1); // depth => number of free spots
  13. $parents = array(); // stack with indexes of $tree which are parents
  14. $currentDepth = 0;
  15.  
  16. // list of tokens that will create new free spots at a (one) lower level
  17. $newSpots = array(
  18. '&' => 2,
  19. '|' => 2,
  20. '!' => 1,
  21. );
  22. // mapping to a more readable form
  23. $map = array(
  24. '&' => 'AND',
  25. '|' => 'OR',
  26. '!' => 'NOT',
  27. );
  28. foreach (explode(',', $input) as $position => $token) {
  29. // find highest level at which there are free spots
  30. $spotFound = false;
  31. $d = count($freeSpots) - 1;
  32. while ($d > -1 && $spotFound === false) {
  33. if ($freeSpots[$d] > 0) {
  34. $currentDepth = $d;
  35. $spotFound = true;
  36. } else {
  37. array_pop($freeSpots); // do not inspect this level again (also to prevent popping too many elements from $parents)
  38. array_pop($parents); // this parent no longer has any free spots
  39. $d--; // look one level lower
  40. }
  41. }
  42.  
  43. if ($spotFound === false) {
  44. // complain, e.g. throw exception
  45. die('malformed expression at position '.$position);
  46. }
  47.  
  48. // add token to tree
  49. $parent = (count($parents) ? $parents[count($parents)-1] : -1);
  50. $tree[] = array(
  51. 'parent' => $parent,
  52. 'children' => array(),
  53. 'value' => (array_key_exists($token, $map) ? $map[$token] : $token),
  54. );
  55. if ($parent > -1) {
  56. $tree[$parent]['children'][] = count($tree) - 1; // index of the element we just added
  57. }
  58.  
  59. // subtract free spots
  60. $freeSpots[$currentDepth] -= 1;
  61.  
  62. // is this a token that creates new spots?
  63. if (array_key_exists($token, $newSpots)) {
  64. // add number of free spots defined in $spots
  65. $freeSpots[$currentDepth+1] = $newSpots[$token];
  66. // this is a new parent
  67. $parents[] = count($tree) - 1; // index of the element we just added
  68. }
  69. } // foreach
  70. return $tree;
  71. }
  72.  
  73. public function printTree($index=0) {
  74. // @todo add output escaping
  75. ?><li><span><?php echo $this->_tree[$index]['value']; ?></span><?php
  76. if (count($this->_tree[$index]['children'])) {
  77. ?><ul><?php
  78. foreach ($this->_tree[$index]['children'] as $child) {
  79. $this->printTree($child);
  80. }
  81. ?></ul><?php
  82. }
  83. ?></li><?php
  84. }
  85. }

En vervolgens kunnen we, gegeven een expressie, de boom als volgt maken en afdrukken:

  1. <?php
  2. $input = '&,|,&,D,E,C,!,|,A,B'; // assumption: this expression was validated successfully earlier
  3. $tree = new RightsTree($input);
  4. ?><ul id="tree"><?php
  5. $tree->printTree();
  6. ?></ul>

En hier kun je dus weer de eerdere jQuery op toepassen (o.a. hangen van clickevents aan list-items).

Nu zijn we helemaal rond .

EDIT: extra gebruiksvriendelijkheid: waarschijnlijk zal de interactieve rechtenboom onderdeel uit gaan maken van een formulier. Als je op de ENTER-toets drukt bij het wijzigen van een recht wil je waarschijnlijk niet dat je formulier meteen wordt gesubmit. Dit kun je afvangen door op regel 65 van de jQuery code het volgende toe te voegen:

  1. $html.keypress(function(e) {
  2. if (e.which == 13) {
  3. // do not submit form...
  4. e.preventDefault();
  5. // ... but trigger blur() event instead
  6. $(this).blur();
  7. }
  8. });

Daarnaast kan het misschien handig zijn dat je meteen kunt gaan typen, door het toevoegen van .select() aan regel 85 van het oorspronkelijke fragment selecteer je meteen alle tekst, deze regel wordt:

  1. $html.focus().select();


MySQL functie:
  1. DELIMITER ;;
  2. DROP FUNCTION IF EXISTS has_rights;;
  3. CREATE FUNCTION has_rights(expression VARCHAR(255), rights VARCHAR(255)) RETURNS BOOL DETERMINISTIC
  4. BEGIN
  5. DECLARE stack VARCHAR(255);
  6. DECLARE token VARCHAR(5);
  7. DECLARE val1 VARCHAR(5);
  8. DECLARE val2 VARCHAR(5);
  9. IF (expression = '') THEN
  10. RETURN TRUE;
  11. END IF;
  12. SET stack = '1,';
  13. SET expression = REVERSE(CONCAT(',&,', expression));
  14. WHILE (LOCATE(',', expression) > 0) DO
  15. SET token = REVERSE(SUBSTRING_INDEX(expression, ',', 1));
  16. SET expression = SUBSTRING(expression, LENGTH(token) + 2);
  17. IF (LENGTH(token) > 0) THEN
  18. IF (token = '|' OR token = '&') THEN
  19. SET val1 = SUBSTRING_INDEX(stack, ',', 1);
  20. SET stack = SUBSTRING(stack, LENGTH(val1) + 2);
  21. SET val2 = SUBSTRING_INDEX(stack, ',', 1);
  22. SET stack = SUBSTRING(stack, LENGTH(val2) + 2);
  23. IF (token = '|') THEN
  24. SET stack = CONCAT((val1 OR val2), ',', stack);
  25. ELSE
  26. SET stack = CONCAT((val1 AND val2), ',', stack);
  27. END IF;
  28. ELSEIF (token = '!') THEN
  29. SET val1 = SUBSTRING_INDEX(stack, ',', 1);
  30. SET stack = CONCAT(NOT(val1), ',', SUBSTRING(stack, LENGTH(val1) + 2));
  31. ELSE
  32. SET val1 = LOCATE(CONCAT(',', token, ','), CONCAT(',', rights, ',')) > 0;
  33. SET stack = CONCAT(val1, ',', stack);
  34. END IF;
  35. END IF;
  36. END WHILE;
  37. SET val1 = SUBSTRING_INDEX(stack, ',', 1);
  38. RETURN (val1 = 1);
  39. END;;
  40. DELIMITER ;


Voorbeelden van aanroep:
  1. mysql> SELECT has_rights('|,1,&,2,!,3', '1');
  2. +--------------------------------+
  3. | has_rights('|,1,&,2,!,3', '1') |
  4. +--------------------------------+
  5. | 1 |
  6. +--------------------------------+
  7. 1 row IN SET (0.00 sec)
  8.  
  9. mysql> SELECT has_rights('|,1,&,2,!,3', '2');
  10. +--------------------------------+
  11. | has_rights('|,1,&,2,!,3', '2') |
  12. +--------------------------------+
  13. | 1 |
  14. +--------------------------------+
  15. 1 row IN SET (0.00 sec)
  16.  
  17. mysql> SELECT has_rights('|,1,&,2,!,3', '2,3');
  18. +----------------------------------+
  19. | has_rights('|,1,&,2,!,3', '2,3') |
  20. +----------------------------------+
  21. | 0 |
  22. +----------------------------------+
  23. 1 row IN SET (0.00 sec)
Gesponsorde links
Je moet ingelogd zijn om een reactie te kunnen posten.
Actieve forumberichten
© 2002-2024 Sitemasters.be - Regels - Laadtijd: 0.622s