Буквально вчера ночью, вместо того, чтобы рисовать слайды для выступления на 404fest я как-то неожиданно написал кусок кода, который может кому-то ещё пригодиться. Это шаблонный тег и вспомогательный фильтр, которые умеют выводить в шаблон древовидные структуры в виде вложенных списков <ul> (вот таких, например).
Несмотря на то, что изначально я написал его "неожиданно", потом долго сидел и боролся с не очень хотящей думать головой, чтобы на этот код не противно было смотреть. И я победил! Так что код теперь production-качества, что в переводе означает "уже один раз исправлялся".
{% tree %}На самом деле, в Джанге уже есть встроенное средство для вывода древовидных структур в список: фильтр "unordered_list". Но он не подошёл, потому что умеет выводить только строчки, а мне хочется в шаблоне как-то влиять на то, что лежит в отдельных <li>: ссылку сделать, дописать что-то. Поэтому я сделал тег, который работает так:
{% tree some_list %}
<a href="{{ item.get_absolute_url }}">{{ item }}</a>
{% endtree %}
Переменная "some_list" — структурированное дерево в том же формате, что принимает и "unordererd_list" (кому лень было ходить по ссылке, это вот такое: ['item 1', ['subitem 1', 'subitem 2'], 'item 2', 'item 3]).
Между открывающим и закрывающим тегами находится микрошаблон, который используется для одиночного элемента списка. В него передаются две переменные:
Работающий код тега с комментариями, как говорится, for your reading pleasure:
class TreeNode(template.Node):
def __init__(self, tree, node_list):
self.tree = tree
self.node_list = node_list
def render(self, context):
tree = self.tree.resolve(context)
# итератор по входному списку, выдающий пары вида
# (элемент списка, его подсписок), причём одного из элемента пары
# может не быть
def pairs(items):
# внутренний "грязный" генератор, выдающий пары, где могут быть
# бесполезные: с обоими пустыми head и tail
def dirty(items):
items = iter(items)
head = None
try:
while True:
item = items.next()
if isinstance(item, (list, tuple)):
yield head, item
head = None
else:
yield head, None
head = item
except StopIteration:
yield head, None
# фильтр над грязным генератором, удаляющий бесполезные пары
return ((h, t) for h, t in dirty(items) if h or t)
# выводит элемент списка с подсписком
# для подсписка рекурсивно вызывается render_items
def render_item(item, sub_items, level):
return ''.join([
'<li>',
item and self.node_list.render(template.Context({'item': item, 'level': level})) or '',
sub_items and '<ul>%s</ul>' % ''.join(render_items(sub_items, level + 1)) or '',
'</li>'
])
# вывод списка элементов
def render_items(items, level):
return ''.join(render_item(h, t, level) for h, t in pairs(items))
return render_items(tree, 0)
@register.tag
def tree(parser, token):
bits = token.split_contents()
if len(bits) != 2:
raise template.TemplateSyntaxError('"%s" takes one argument: tree-structured list' % bits[0])
node_list = parser.parse('end' + bits[0])
parser.delete_first_token()
return TreeNode(parser.compile_filter(bits[1]), node_list)
Сначала попытался написать по-тупому, разбирая входной список и подпихивая между делом всякие <li>, </li>, <ul> и прочее. Но довольно быстро стало очевидно, что такой подход приводит к невоспринимаемому вороху special-case'ов. Потому что по сути тут нужен итератор с памятью на один элемент: когда вытаскивается одиночный элемент, его нельзя тут же рендерить и закрывать, потому что за ним может идти его подсписок. А может не идти. А может итератор закончится (это особенно гадко). Поэтому я в итоге родил вот тот самый генератор "pairs", отвязанный от рендеринга. На чём и успокоился.
И да, мне это нравится больше, чем код unordered_list :-).
astreeЕщё одна небольшая проблема — это составление списка, который принимает {% tree %}. Изначально такого списка у меня нет, а есть моделька, которая ссылается на себя же в поле "parent", и таким образом определяет дерево. Соответственно, я написал ещё и фильтр, который из queryset'а этой модели делает такой сгруппированный список:
@register.filter
def astree(items, attribute):
# перевод списка в dict: parent -> список детей
parent_map = defaultdict(list)
for item in items:
parent_map[getattr(item, attribute)].append(item)
# рекурсивный вывод детей одного parent'а
def tree_level(parent):
for item in parent_map[parent]:
yield item
sub_items = list(tree_level(item))
if sub_items:
yield sub_items
return list(tree_level(None))
Соответственно, в шаблон передаётся обычный queryset, и всё выглядит так:
{% tree object_list|astree:"parent" %}...{% endtree %}
Комментарии: 26
21.09.09 18:03
Маст-юз, однозначно.
21.09.09 18:11
Клево! Отдельный app будет?
21.09.09 18:13
А почему у вас так много функций, определённых внутри методов? Что мешает вынести их на уровень модуля? Или хотя бы сделать их статическими методами? Я не придираюсь, просто интересно :)
21.09.09 18:14
А чёрт его знает... Я пока так и не нашёл в себе душевного спокойствия как что куда выкладывать. Поддерживать — хлопотно, плодить неподдерживаемый код — нехорошо. Пусть сниппетом пока живёт :-)
21.09.09 18:16
Атлична! :)
21.09.09 18:19
Слова "хотя бы" подразумевают, что это каким-то образом лучше :-). На самом деле, мне нужна конкретная причина, чтобы вытащить функцию в публичный интерфейс класса или модуля. Все эти функции нужны только в том же месте, где определены либо для рекурсии, либо для абстракции одного логического куска. Так зачем их публиковать и мусорить namespace?
Хотя, у pairs есть некоторые шансы переехать поближе к свету, если такая функциональность потребуется где-то ещё.
21.09.09 18:26
Понял вашу позицию, я просто придерживаюсь мнения, что публичный интерфейс != множеству всех методов и аттрибутов класса, а больше определяется суперклассом (в данном случае template.Node - метод render).
21.09.09 18:30
Это не тот вопрос, про который может быть мнение :-). В Питоне совершенно чётко публичный интерфейс — это всё, что выдаёт
dir(obj), и что не начинается с '_'. То есть, все эти функции, которые вы не считаете публичными, будут мешаться юзерам, в Tab-дополнении в какой-нибудь консоли.21.09.09 18:36
Я когда-то делал рекурсию в шаблоне на самих шаблонах. Достаточно просто получается, в общем-то :)
22.09.09 02:57
Но вряд ли настолько же эффективно, как в выше изложенном варианте.
22.09.09 09:37
К вопросу о хранении и отображении деревьев.
Позволю себе малость попиарить свой скромный проект :) в разрезе того, что там тоже решена проблема вывода деревьев. Может, это покажется интересным: http://sqlamp.angri.ru/#sqlamp.tree_recursive_iterator
22.09.09 09:40
Взглянуть на код можно тут: http://bitbucket.org/angri/sqlamp/src/tip/sqlamp/__init__.py#cl-863
25.10.09 18:09
Так ведь скорость падает.
Вот два примера:
в результате имеем:
29.10.09 11:55
29.10.09 23:57
2.11.09 17:45
Кажется закралась ошибка:
выделенное заменить на
sub_items = list(tree_level(<b>item.id</b>))2.11.09 18:29
Нет, id там не нужен. Там везде присутствуют ссылки на объекты, потому что они вполне адекватно сравниваются по id и имеют хеши на том же id.
5.11.09 12:25
Лучше заменить на это:
для доступа к другим переменным контекста.
6.11.09 15:28
Иван, но они же будут пересоздаваться каждый раз, как выполняется эта функция!
будет выглядеть как
9 0 LOAD_GLOBAL 0 (f1)
3 LOAD_FAST 0 (a)
6 CALL_FUNCTION 1
9 LOAD_CONST 1 (1)
12 BINARY_ADD
13 RETURN_VALUE
, в то время как
выглядит как
И что-то я не слишком уверен, что команда с названием MAKE_FUNCTION выполняется достаточно быстро.
6.11.09 15:44
Поскольку это уже второй комментарий такого рода, не могу не отреагировать :-).
Заимствуя фразу у Дж. Спольски — "I couldn't care less". Это такие копейки, что грамотный питонист даже не должен пытаться думать в ту сторону, пока не доказано, что именно в этом месте находится критично тормозящий кусок программы. Этим, собственно, и отличается программирование на высокоуровневом языке от низкоуровневого: здесь приоритет читаемости кода, модульности и общей maintainability не то что больше, чем оптимизация скорости вызова отдельных функций, а больше безоговорочно. Иначе бы мы писали на Си (без всякой подколки).
Я могу не глядя поспорить, что разница в производительности этих двух вариантов будет меньше, чем даже статистическая погрешность при формировании страницы, с которой я начал пример. И даже если таких деревьев там будет 10, тоже результат вряд ли изменится.
6.11.09 17:25
Ммм, неужели __методы хуже по maintainability, притом что они не вызывают ненужной перегенерации функций?
Хм. Если это одно место - то да, копейки. А можете ли вы не глядя оценить, насколько изменится производительность всей системы, если несоздавание вложенных функций без надобности (т.е., когда они не используют контекста внешней функции) ввести в кодинг-стайл и поправить все такие случаи :) ? У вас ведь яндекс, по идее, в его масштабах любая оптимизация, которую можно несложно сделать, полезна.
Ну впрочем всё это брюзжание, я согласен. Я и сам лямбда-функциями по месту балуюсь, что ничем не лучше.
6.11.09 17:32
Хм. Это, кстати, пожалуй, объясняет моё брюзжание. Вложенные функции мне подсознательно не нравятся не потому, что функции пересоздавать, а потому, что оный код Cython-ом не скомпилируется :)
11.11.09 10:32
Код можно немного модифицировать, и сделать возможность описывать весь html в шаблонах.
27.12.09 02:26
Совсем недавно мне это понадобилось! Спасибо за вашу работу!
14.01.10 03:05
Писал реализацию дерева для удобной работы с набором записей в LDAP. Может строить иерархию, например, для имен в LDAP или доменных имен. Может кому пригодится, хотя код наверно не очень хороший.
http://code.activestate.com/recipes/576966/
23.01.10 18:15