Итак, тестовая иерархия, с которой нам предстоит работать:
В базе данных имеется самая простая таблица на самом простом MSSQL сервере, тонкости подключения опустим, наша цель — разобраться с иерархией и рекурсией.
Создадим таблицу:
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]
Наполним сведениями:
Описание полей есть в комментариях, чуть подробнее о поле access:
По умолчанию в моей системе для каждого нового документа проставляется inherit, то есть наследование от родителя. Для нашего эксперимента для некоторых эелементов пропишем доменные группы. В группе Domain Users моя учётная запись имеется, а вот в AD Group Secret меня нет.
Что ещё мы имеем. Массив, содержащий список моих доменных групп. Достаётся он достаточно просто, на IIS включена аутентификация Windows, всё работает прозрачно, в PHP логин зашедшего находится в переменной $_SERVER[«AUTH_USER»], далее LDAP запросом получаем список групп.
Теперь предлагаю получить необходимые данные и перейти непосредственно к делу:
$stmt = $PDO->query("SELECT * FROM Test");
$table = $stmt->fetchAll(); //Получим таблицу из БД
$groups = LDAP::getGroups('$login'); //Получим группы ActiveDirectory
Задача №1
Необходимо научиться работать с иерархией как с деревом а не списком. Уровень вложенности заранее не известен и может быть любым, следовательно должно быть универсальное средство, позволяющее выполнять проход по дереву как сверху вниз, так и в обратном направлении.
Задача №2
Необходимо гибко управлять доступами, то есть, давать права на группы, отдельные документы и т.д., по аналогии с файловой системой NTFS, можно закрыть права на всю папку, но для одного документа в этой папке доступ нарезать — тоже самое должно получиться и у нас.
Задача №3
Необходимо скрыть от пользователей ресурсы, к которым у них нет доступа, но самое главное, при наличии прав хотя бы на один документ где то в глубине закрытой для него ветки, делать видимыми элементы ведущие к этому документу (иначе как пользователь до него доберётся?)
Вот собственно базовая функция:
$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); //Запускаем
Описание по большей части привёл в комментариях, но если говорить просто — после того как цикл foreach проходит строку и делает что то с данными(в нашем случае просто копирует данные в другой массив, добавляя поле level и точки к имени), он запускает эту же функцию, передав ей uid строки, и поскольку в условии if мы сравниваем его с pid, то следующий запуск однозначно захватит дочерние элементы. Цикл foreach перебирает все строки у которых uid родителя совпадает с переданным значением, поэтому перезапуская саму себя, функция отработает на каждом элементе каждого уровня. Для наглядности, мы так же передаём level увеличивая его на единицу. В итоге мы увидим какой документ какой уровень вложенности имеет.
Выводим массив $array в браузер:
Уже не плохо, не так ли?
А теперь немного усложним нашу функцию:
$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); //Запускаем
Разбираем по порядку:
1. Добавлено поле path — для формирования пути, добавляем к значению "/" и имя строки, затем полученное значение передаём в функцию, где история повторяется и на выходе получается путь от корня до элемента.
2. Результирующий массив теперь формируется не по порядку, начиная с нуля а с привязкой к uid — $array[$row['uid']] = $_row;. В данном случае это ни как не влияет на работу скрипта, но возможность обращаться к строке по индексу, а не перебором в цикле потребуется нам в дальнейшем, когда будем разбирать проход по дереву в обратную сторону.
3. Добавлен индекс $array_idx_lvl = array();. Этот индекс нам так же потребуется позже, смысл таков — результирующий набор складывается не в одну кучу, а с разбивкой на массивы индексируемые по level.
4. Поле Access. Когда функция запускает саму себя, вместе с остальными параметрами она передаёт свою настройку прав $_row['access'] дочерям, а далее происходит следующее, проверяются права — если выставлено наследование (inherit), то применяются права родителя, если нет — через in_array проверяем, есть ли указанная в access доменная группа среди групп зашедшего пользователя. Если есть — добавляем в строку allow (разрешить), иначе deny (запрет).
Итоговый результат:
Ну что же, со спуском разобрались, теперь осталось разобраться с подъёмом и заполнением последнего поля view, определяющего видимость элементов. В начале статьи, я говорил для чего это нужно, но можно предположить иную ситуацию. Допустим вы решили привязать древовидный список к навигационному меню сайта, сделанному в виде многоуровневого выпадающего списка с кучей пунктов, и вы просто не хотите, чтобы пользователь, имеющий доступ всего лишь к одному документу ворочал весь этот массив и в объёмном меню искал свой пункт, ведь по сути ему нужно показать всего лишь одну ветку ведущую к нужной кнопке.
Почему здесь нужен проход в обратную сторону? Предположим у пользователя закрыт доступ для всего контента за исключением одного, самого дальнего(на последнем уровне) документа, если подумать, логично было бы брать начало от доступного, и вести его к корню дерева, показывая только нужные элементы.
Приступим:
//Функция прохода вверх по дереву на один уроверь от заданного 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);
}
}
Что делает эта функция — принимает в качестве параметра uid строки, с которой нужно начать действовать, обращается к этой строке и проверяет видимость. Если в поле view не show(т.е. показывать), а что то другое, проверяет что находится в безопасности, и если там стоит allow(доступ открыт), делает элемент видимым, в противном случае скрытым(hide), затем запускает себя же, передавая свой pid и настройку видимости, а так же переменную $ident увеличенную на 1, тем самым блокируя последующие самозапуски. При втором проходе, по переданному pid находится родительский элемент, выполняется та же проверка, за исключением одного, если от дочернего в переменной $view передано 'show', то не смотря ни на что, текущему элементу так же присвоится show, то есть видимый.
На мой взгляд, работа с ограничителем — самый оптимальный вариант, ибо представьте ситуацию, на 10 уровне у нас 100 документов, для полного обхода всего дерева, нам нужно запускать эту функцию на каждом элементе, т.к. если на последнем уровне мы запустим функцию 100 раз, то выполняя самозапуски, перебор 100 раз дойдёт до корня. Если умножить на 10 уровней — уже получится 1000 циклов, что не есть хорошо, поэтому подъём нужно осуществлять равномерно, уровень за уровнем.
Запускает эту функцию следующий код:
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);
}
}
}
Вот тут как раз и потребовался индекс по уровню. Здесь мы движемся от самого дальнего уровня, заходя в каждый, обрабатывая в нём каждый элемент.
А вот и картинка:
Перед запуском, я намеренно прописал разрешающую группу для пункта «Отчет для налоговой», чтобы наглядно показать что код отрабатывает корректно. Несмотря на то, что доступ к разделу «Бухгалтерская отчетность» закрыт, он видимый.
Вот и собственно всё, думаю с задачей мы справились, основа получена, алгоритм работает, можно применить в реальной системе.
Комментарии (27)
michael_vostrikov
05.04.2016 12:28+2- Рекомендую вам освоить ООП и научиться пользоваться объектами. Все ваши глобальные функции и переменные вполне можно инкапсулировать в объект класса Tree.
- Заполнение дерева вполне можно сделать без рекурсии. Вот пример для объектов, для массивов можно сделать аналогично, только надо вручную указывать доступ по ссылке.
function getDocumentTree() { $documents = Document::find()->indexBy('id')->all(); $topLevelDocuments = []; foreach ($documents as $document) { if ($document->parent_id) { $parentDocument = $documents[$document->parent_id]; $document->parentDocument = $parentDocument; $parentDocument->childDocuments[$document->id] = $document; } else { $topLevelDocuments[$document->id] = $document; } } return $topLevelDocuments; }
- Не очень понял ваши рассуждения про самозапуски, но рекурсия здесь тоже не нужна. Можно сделать что-то типа такого (псевдокод, в работе не проверял):
foreach ($array as $uid => $row) { $node = $row; if ($node['access'] == 'allow') { // поднимаемся вверх по ветке, разрешаем просмотр для родительских узлов $pid = $row['pid']; while ($pid != null) { $node = $array[$pid]; $node['view'] = 'show'; $pid = $node['pid']; } } }
сравнивая level каждого документа нам пришлось бы обойти сотни строк, это несёт большие накладные расходы
Вы проводили измерения, на сколько миллисекунд у вас увеличивается время загрузки страницы при обработке сотни элементов вместо десяти?
Alcogolic
05.04.2016 13:39-11. Ну причём тут ООП… не обращайте внимание на код, естественно финальный вариант будет упакован в класс, я лишь описал свою логику, которая вобщем то работает…
2. Не совсем понял идею
3. По-моему не слишком оптимально, во всяком случае не оставлю без внимания, найду время и проведу сравнительный тест, спасибо.
- Рекомендую вам освоить ООП и научиться пользоваться объектами. Все ваши глобальные функции и переменные вполне можно инкапсулировать в объект класса Tree.
greabock
05.04.2016 12:32+9Ждём статью "пишем echo"
Alcogolic
05.04.2016 14:18-1По-моему вы не правы. Не всем данная тема может показаться тривиальной. Очень много новичков просто не знают с чего начать. Я буду рад если написанное выше кому то будет полезным…
Dolbe
05.04.2016 15:58Как же это так, новички не знают с чего начать… А гугл? Уж сегодня, в 2016 году, гугл ничего не находит подобных примеров данной тематике?
Alcogolic
05.04.2016 16:00-1Теперь будет на один больше). Много теории гугл находит, а вот законченных решений, где расписано от и до, к сожалению не так уж и много.
NLO
05.04.2016 13:20НЛО прилетело и опубликовало эту надпись здесь
Alcogolic
05.04.2016 14:05Честно говоря, настолько глубоко в изучение деревьев не погружался,
простая логика, простое исполнение, так сказать конкретный рабочий пример. Этот материал скорее для новичков, понять суть…
А за наводку спасибо, нашёл даже пару хороших статей по nested sets, почитаем…greabock
05.04.2016 16:15+1А стоило бы изучить этот вопрос несколько глубже. Я вот на хабр «ворвался», тоже с довольно тривиальным примером. Без понятия, как меня с ним вообще «захабрили». Но вот к его изучению и рассмотрению, я подошел довольно основательно.
Однако, как можно было миновать четрые основных паттерна (al, ns, mp и ct) при изучении деревьев? Ума не приложу…Alcogolic
05.04.2016 16:22-2Послушайте, тут задачка то простая, и решена она просто, парой функций. Я не говорил что представляю грааль,
я показал как это можно сделать просто и быстро.
Вы когда на обочине, меняете колесо на машине, всегда пользуетесь динамометрическим ключём и смотрите в книге моменты затяжки болтов? Думаю нет.
Будь это коммерческий проект, естественно подход был бы несколько другим. Видимо вначале мне всё же стоило написать «Это материал для новичков, гуру просим не читать.»greabock
05.04.2016 16:39Послушайте, тут задачка то простая, и решена она просто, парой функций.
я бы не смог сказать лучше
aks1983
05.04.2016 17:25Напишешь доступно — заминусуют за банальность, потому что поэтому задавать глупые вопросы лучше гуглу?
Alcogolic
05.04.2016 19:29Я думал тут карму сливают за копипаст, или неадекватное поведение, оскорбления и прочее,
а тут оказывается и за труды можно в нехорошие попасть? Мда… людишки видать тут те ещё собрались…
oxidmod
05.04.2016 13:43+1>> global $array;
>> global $array_idx_lvl; //Индекс по level
>> global $groups; //доменные группы
лицо_рука.jpg
для работы с древовидными структурами есть куда более удачные алгоритмы, чем полный перебор всех елементовAlcogolic
05.04.2016 13:45+1Честно, я не придумал ничего лучше, как обойти всё, иначе я не представляю как можно определить какой элемент показывать, а какой нет.
alexkunin
05.04.2016 15:31+2Вместо глобальных переменных лучше использовать аргументы функций. Уж лучше много параметров, чем глобальные переменные — код портабельным становится.
Alcogolic
06.04.2016 09:30Это уже стиль программирования. Одному удобнее так, другому так,
некоторые юзают паттерн registry во всех своих разработках, другие же считают что это лишает портабельности и объекты нужно передавать в другие классы при инициализации. Боюсь мы ушли от сути статьи…alexkunin
06.04.2016 10:01Uлобальные переменные к стилю отношения не имеют, зато имеют непосредственное отношение к качеству кода.
Alcogolic
05.04.2016 15:33-1Смысл статьи немного в другом… я просто кинул текстовый файл в корень web сервера и назвал его index.php, считайте что в реальном проекте эти стоки выглядят так:
$this->array;
$this->array_idx_lvl; //Индекс по level
$this->groups; //доменные группы
alexkunin
05.04.2016 16:15+1Ваш код работает, но в итоге у вас одна монструозная и парочка упитанных функций (в плане плотности непонятных вещей), все очень специфические, труднорасширяемые — в том смысле, что добавление новой функциональности увеличит и без того большую recursive().
Я бы в данном случае написал бы несколько функций с небольшими, но конкретными целями:
getLevel($uid) — посчитать уровень для конкретного элемента
getAccess($uid) — посчитать доступ для конкретного элемента (тут же ресолвим inherit)
isAccessible($uid, $access) — доступен ли элемент для данной маски доступа?
hasAccessibleDescendants($uid, $access) — доступен ли хоть один (или сам элемент) потомок для данной маски доступа?
А еще завернул бы все в класс, чтобы поменьше передавать разные параметры, да и вообще сгруппировать функции по смыслу.
И вот что у меня получилось бы: repl.it/CCWZ/1.
Нарочно нет комментариев, имена функций позволяют свободно читать код. При большом количестве элементов все это начнет тормозить, но никто не мешает закешировать результаты рекурсивных функций (можно через __call, и тогда код просто станет немного «магическим», при этом не будут усложняться наши рекурсивные геттеры). Добавить новое рекурсивное свойство не составит труда, и код от этого не захламится. А пассаж в конструкторе можно еще на уровне fetchAll решить, но я не мог это сделать в рамках repl.it.
В любом случае, спасибо за утреннюю разминку. ;)Alcogolic
05.04.2016 16:28За конкретные примеры спасибо, всегда приятно когда разговор по существу, а не понты и метание умных красивых слов как зачастую тут бывает…
DCrystal
05.04.2016 16:57В конструкторе вместо reduce'a для группировки по ключу можно(наглядней) использовать array_column — array_column($items, null, 'uid')
alexkunin
05.04.2016 17:00Спасибо. :) Я все еще одной ногой в PHP 5.4.
DCrystal
05.04.2016 17:04Не вы одни :) Если еще не видели — там есть полифилл — github.com/ramsey/array_column/blob/master/src/array_column.php
MetaDone
2016 год на дворе, а вы все глобальные переменные используете.
и по поводу деревьев можете глянуть сюда — http://gsbelarus.com/pw/articles/post/derev-ia-v-sql/
в статье описаны способы, которыми можно Ваши проблемы решить на корню чтоб не городить лишнего
Alcogolic
Отличная статья, спасибо за ссылку, но там более серьёзный подход, во всём что написано нужно разбираться… как ни будь обязательно потрачу время…
этот код написан на коленке, на скорую руку, вот на global вы обратили внимание, а на эту конструкцию «LDAP::getGroups» почему то нет))
MetaDone
тогда и на
и на отстутствие phpdoc к функциям стоило бы. Просто глобальные переменные прям бросаются в глаза. А статью все же перечитайте — потратите немного на ее чтение, потом сэкономите кучу времени при работе с подобными задачами