PHP recursion - algorithm, application
By writing the article, we set up a clock of thoughts and experiments in the construction of hierarchical lists. Initially, the logic ran into SQL queries, but later decided to implement in PHP, in order to remove dependence on the DBMS. In a simple example, I will show how you can go from the root of the hierarchy to each finite element and vice versa, the information is more likely for beginners.
So, the test hierarchy with which we have to work:
')
The database has the simplest table on the simplest MSSQL server, the subtleties of the connection are omitted, our goal is to deal with hierarchy and recursion.
Create a table:
Fill in the information:
The description of the fields is in the comments, a little more about the access field:
By default, in my system, for each new document, inherit is set down , that is, inheritance from the parent. For our experiment for some elements we will register domain groups. In the Domain Users group, my account is available, but in AD Group Secret I do not.
What else do we have. An array containing a list of my domain groups. It comes out quite simply, Windows authentication is enabled on IIS, everything works transparently, in PHP the login of the caller is in the $ _SERVER ["AUTH_USER"] variable, then by LDAP request we get the list of groups.
Now I propose to obtain the necessary data and go directly to the case:
It is necessary to learn how to work with hierarchy as a tree and not a list. The nesting level is not known in advance and can be any, therefore there should be a universal tool that allows you to walk through the tree from top to bottom, and in the opposite direction.
It is necessary to flexibly manage access, that is, to give rights to groups, separate documents, etc., by analogy with the NTFS file system, you can close the rights to the entire folder, but for one document in this folder you should cut access - the same should happen we have.
It is necessary to hide from users the resources to which they do not have access, but most importantly, if they have rights to at least one document somewhere in the depth of the branch closed to it, make the elements leading to this document visible (otherwise, how will the user get to it?)
Here is the basic function itself:
For the most part, the description was given in the comments, but if to speak simply - after the foreach loop passes a line and does something with the data (in our case it simply copies the data to another array, adding the level field and points to the name), it starts the same the function, passing the uid of the string to it, and since in the if condition we compare it with the pid, the next launch will unambiguously capture the child elements. The foreach loop iterates over all the lines in which the parent's uid matches the transmitted value, so by restarting itself, the function will work on each element of each level. For clarity, we also pass the level by increasing it by one. As a result, we will see which document has which nesting level.
Display the $ array in the browser:
Already not bad, right?
And now let's make our function more complicated:
Parse in order:
1. Added the path field - to form the path, add the value of the string to the "/" value, then transfer the resulting value to the function, where history repeats and the output is the path from the root to the element.
2. The resulting array is now formed not in order, starting from zero, but bound to uid - $ array [$ row ['uid']] = $ _row; . In this case, it doesn’t affect the script work, but we will need to be able to access the line by index, rather than by looping through the loop, when we parse the passage through the tree in the opposite direction.
3. Added index $ array_idx_lvl = array (); . We also need this index later; the meaning is as follows - the result set is not added up in one pile, but broken down into arrays indexed by level.
4. Access field. When the function starts itself, along with the rest of the parameters, it passes its setting of rights $ _row ['access'] to daughters, and then the following happens, rights are checked - if inheritance is set, then parent rights are applied, if not - we check through in_array whether there is a domain group specified in access among the groups of the logged in user. If there is, add to the allow line, otherwise deny (ban).
The final result:
Well, with the descent figured out, now it remains to deal with the rise and filling of the last field of view , which determines the visibility of elements. At the beginning of the article, I said why this is necessary, but we can assume a different situation. Suppose you decide to bind a tree view to the site’s navigation menu, made as a multilevel drop-down list with a bunch of items, and you just don’t want a user who has access to just one document to turn over this whole array and search for his item in the volume menu in fact, he needs to show only one branch leading to the desired button.
Why do we need a pass in the opposite direction? Suppose the user has denied access to all content except for one, the most distant (at the last level) document, if you think it would be logical to start from an accessible one and lead it to the root of the tree, showing only the necessary elements.
Let's start:
What this function does is that it takes as its parameter the uid of the line from which to start to act, refers to this line and checks the visibility. If the view field does not show (ie, show), but something else, checks that it is safe, and if there is an allow (access open), makes the element visible, otherwise hidden ( hide ), then launches itself however, passing its pid and visibility setting, as well as the $ ident variable increased by 1, thereby blocking subsequent self-launches. During the second pass, the parent element is located on the transmitted pid , the same check is performed, except for one, if the show view is transferred from the child in the $ view variable, no matter what, the current element is also assigned to show , that is, visible.
In my opinion, working with a limiter is the best option, for imagine a situation, at level 10 we have 100 documents, to completely bypass the whole tree, we need to run this function on each element, since if at the last level we run the function 100 times, then performing self-launches, the search will reach the root 100 times. If you multiply by 10 levels - you will have 1000 cycles, which is not good, so you need to lift evenly, level by level.
This function starts the following code:
This is where the level index was required. Here we move from the farthest level, entering into each one, processing each element in it.
And here is the picture:
Before launching, I intentionally set up a permitting group for the “Report for tax” item in order to clearly show that the code is working correctly. Despite the fact that access to the section "Financial statements" is closed, it is visible.
That's all, I think we coped with the task, the basis was obtained, the algorithm works, it can be applied in a real system.
So, the test hierarchy with which we have to work:
')
The database has the simplest table on the simplest MSSQL server, the subtleties of the connection are omitted, our goal is to deal with hierarchy and recursion.
Create a table:
CREATE TABLE [dbo].[Test]( [uid] [int] IDENTITY(1,1) NOT NULL, -- , [pid] [int] NULL, -- , uid [name] [varchar](255) NULL, [access] [varchar](50) NULL, -- ) ON [PRIMARY] Fill in the information:
The description of the fields is in the comments, a little more about the access field:
By default, in my system, for each new document, inherit is set down , that is, inheritance from the parent. For our experiment for some elements we will register domain groups. In the Domain Users group, my account is available, but in AD Group Secret I do not.
What else do we have. An array containing a list of my domain groups. It comes out quite simply, Windows authentication is enabled on IIS, everything works transparently, in PHP the login of the caller is in the $ _SERVER ["AUTH_USER"] variable, then by LDAP request we get the list of groups.
Now I propose to obtain the necessary data and go directly to the case:
$stmt = $PDO->query("SELECT * FROM Test"); $table = $stmt->fetchAll(); // $groups = LDAP::getGroups('$login'); // ActiveDirectory Problem number 1
It is necessary to learn how to work with hierarchy as a tree and not a list. The nesting level is not known in advance and can be any, therefore there should be a universal tool that allows you to walk through the tree from top to bottom, and in the opposite direction.
Problem number 2
It is necessary to flexibly manage access, that is, to give rights to groups, separate documents, etc., by analogy with the NTFS file system, you can close the rights to the entire folder, but for one document in this folder you should cut access - the same should happen we have.
Problem number 3
It is necessary to hide from users the resources to which they do not have access, but most importantly, if they have rights to at least one document somewhere in the depth of the branch closed to it, make the elements leading to this document visible (otherwise, how will the user get to it?)
Here is the basic function itself:
$array = array(); // function recursive($data, $pid = 0, $level = 0){ global $array; foreach ($data as $row) { // if ($row['pid'] == $pid) { // , pid , 0, .. // $_row['uid'] = $row['uid']; $_row['pid'] = $row['pid']; $_row['name'] = $_row['name'] = str_pad('', $level*3, '.').$row['name']; // str_pad $_row['level'] = $level; // $array[] = $_row; // // , uid, // ( uid pid-) recursive($data, $row['uid'], $level + 1); } } } recursive($table); // For the most part, the description was given in the comments, but if to speak simply - after the foreach loop passes a line and does something with the data (in our case it simply copies the data to another array, adding the level field and points to the name), it starts the same the function, passing the uid of the string to it, and since in the if condition we compare it with the pid, the next launch will unambiguously capture the child elements. The foreach loop iterates over all the lines in which the parent's uid matches the transmitted value, so by restarting itself, the function will work on each element of each level. For clarity, we also pass the level by increasing it by one. As a result, we will see which document has which nesting level.
Display the $ array in the browser:
Already not bad, right?
And now let's make our function more complicated:
$array = array(); // $array_idx_lvl = array(); // level function recursive($data, $pid = 0, $level = 0, $path = "", $access_parent = "inherit"){ global $array; global $array_idx_lvl; // level global $groups; // // foreach ($data as $row) { // , pid , 0, .. if ($row['pid'] == $pid) { // $_row['uid'] = $row['uid']; $_row['pid'] = $row['pid']; $_row['name'] = str_pad('', $level*3, '.').$row['name']; $_row['level'] = $level; // $_row['path'] = $path."/".$row['name']; // $_row['view'] = ""; // if($row['access'] == 'inherit') { $_row['access'] = $access_parent; // , } else { $_row['access'] = (in_array($row['access'], $groups)) ? 'allow' : 'deny'; } $array[$row['uid']] = $_row; // uid // level, $array_idx_lvl[$level][$row['uid']] = $row['uid']; // , uid, // ( uid pid-) recursive($data, $row['uid'], $level + 1, $_row['path'], $_row['access']); } } } recursive($table); // Parse in order:
1. Added the path field - to form the path, add the value of the string to the "/" value, then transfer the resulting value to the function, where history repeats and the output is the path from the root to the element.
2. The resulting array is now formed not in order, starting from zero, but bound to uid - $ array [$ row ['uid']] = $ _row; . In this case, it doesn’t affect the script work, but we will need to be able to access the line by index, rather than by looping through the loop, when we parse the passage through the tree in the opposite direction.
3. Added index $ array_idx_lvl = array (); . We also need this index later; the meaning is as follows - the result set is not added up in one pile, but broken down into arrays indexed by level.
4. Access field. When the function starts itself, along with the rest of the parameters, it passes its setting of rights $ _row ['access'] to daughters, and then the following happens, rights are checked - if inheritance is set, then parent rights are applied, if not - we check through in_array whether there is a domain group specified in access among the groups of the logged in user. If there is, add to the allow line, otherwise deny (ban).
The final result:
Well, with the descent figured out, now it remains to deal with the rise and filling of the last field of view , which determines the visibility of elements. At the beginning of the article, I said why this is necessary, but we can assume a different situation. Suppose you decide to bind a tree view to the site’s navigation menu, made as a multilevel drop-down list with a bunch of items, and you just don’t want a user who has access to just one document to turn over this whole array and search for his item in the volume menu in fact, he needs to show only one branch leading to the desired button.
Why do we need a pass in the opposite direction? Suppose the user has denied access to all content except for one, the most distant (at the last level) document, if you think it would be logical to start from an accessible one and lead it to the root of the tree, showing only the necessary elements.
Let's start:
// uid, // ... function backRecursive($uid, $view = null, $ident = 0) { global $array; // if($ident <= 1) { // - , // if($array[$uid]['view'] != 'show') { $array[$uid]['view'] = ($array[$uid]['access'] == 'allow' or $view == 'show') ? 'show' : 'hide'; } backRecursive($array[$uid]['pid'], $array[$uid]['view'], $ident+1); } } What this function does is that it takes as its parameter the uid of the line from which to start to act, refers to this line and checks the visibility. If the view field does not show (ie, show), but something else, checks that it is safe, and if there is an allow (access open), makes the element visible, otherwise hidden ( hide ), then launches itself however, passing its pid and visibility setting, as well as the $ ident variable increased by 1, thereby blocking subsequent self-launches. During the second pass, the parent element is located on the transmitted pid , the same check is performed, except for one, if the show view is transferred from the child in the $ view variable, no matter what, the current element is also assigned to show , that is, visible.
In my opinion, working with a limiter is the best option, for imagine a situation, at level 10 we have 100 documents, to completely bypass the whole tree, we need to run this function on each element, since if at the last level we run the function 100 times, then performing self-launches, the search will reach the root 100 times. If you multiply by 10 levels - you will have 1000 cycles, which is not good, so you need to lift evenly, level by level.
This function starts the following code:
function startBack(){ global $array_idx_lvl; $levels = array_keys($array_idx_lvl); // $maxLevel = max($levels); // // for ($i = $maxLevel; $i > 0; $i--) { $uids = array_keys($array_idx_lvl[$i]); // 1 foreach ($uids as $uid) { backRecursive($uid); } } } This is where the level index was required. Here we move from the farthest level, entering into each one, processing each element in it.
And here is the picture:
Before launching, I intentionally set up a permitting group for the “Report for tax” item in order to clearly show that the code is working correctly. Despite the fact that access to the section "Financial statements" is closed, it is visible.
That's all, I think we coped with the task, the basis was obtained, the algorithm works, it can be applied in a real system.
Source: https://habr.com/ru/post/280944/
All Articles