Буквально вчера ночью, вместо того, чтобы рисовать слайды для выступления на 404fest я как-то неожиданно написал кусок кода, который может кому-то ещё пригодиться. Это шаблонный тег и вспомогательный фильтр, которые умеют выводить в шаблон древовидные структуры в виде вложенных списков <ul> (вот таких, например).

Несмотря на то, что изначально я написал его "неожиданно", потом долго сидел и боролся с не очень хотящей думать головой, чтобы на этот код не противно было смотреть. И я победил! Так что код теперь production-качества, что в переводе означает "уже один раз исправлялся".

Тег {% tree %}

На самом деле, в Джанге уже есть встроенное средство для вывода древовидных структур в список: фильтр "unordered_list". Но он не подошёл, потому что умеет выводить только строчки, а мне хочется в шаблоне как-то влиять на то, что лежит в отдельных <li>: ссылку сделать, дописать что-то. Поэтому я сделал тег, который работает так:

{% tree some_list %}
<a href="{{ item.get_absolute_url }}">{{ item }}</a>
{% endtree %}

Работающий код тега с комментариями, как говорится, 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 %}

Комментарии: 42

  1. astur.net.ru

    Маст-юз, однозначно.

  2. Alexander Artemenko

    Клево! Отдельный app будет?

  3. bsdemon

    А почему у вас так много функций, определённых внутри методов? Что мешает вынести их на уровень модуля? Или хотя бы сделать их статическими методами? Я не придираюсь, просто интересно :)

  4. Ivan Sagalaev

    Отдельный app будет?

    А чёрт его знает... Я пока так и не нашёл в себе душевного спокойствия как что куда выкладывать. Поддерживать — хлопотно, плодить неподдерживаемый код — нехорошо. Пусть сниппетом пока живёт :-)

  5. Basil Shubin

    Атлична! :)

  6. Ivan Sagalaev

    А почему у вас так много функций, определённых внутри методов? Что мешает вынести их на уровень модуля? Или хотя бы сделать их статическими методами? Я не придираюсь, просто интересно :)

    Слова "хотя бы" подразумевают, что это каким-то образом лучше :-). На самом деле, мне нужна конкретная причина, чтобы вытащить функцию в публичный интерфейс класса или модуля. Все эти функции нужны только в том же месте, где определены либо для рекурсии, либо для абстракции одного логического куска. Так зачем их публиковать и мусорить namespace?

    Хотя, у pairs есть некоторые шансы переехать поближе к свету, если такая функциональность потребуется где-то ещё.

  7. bsdemon

    На самом деле, мне нужна конкретная причина, чтобы вытащить функцию в публичный интерфейс класса или модуля. Все эти функции нужны только в том же месте, где определены либо для рекурсии, либо для абстракции одного логического куска. Так зачем их публиковать и мусорить namespace?

    Понял вашу позицию, я просто придерживаюсь мнения, что публичный интерфейс != множеству всех методов и аттрибутов класса, а больше определяется суперклассом (в данном случае template.Node - метод render).

  8. Ivan Sagalaev

    Это не тот вопрос, про который может быть мнение :-). В Питоне совершенно чётко публичный интерфейс — это всё, что выдаёт dir(obj), и что не начинается с '_'. То есть, все эти функции, которые вы не считаете публичными, будут мешаться юзерам, в Tab-дополнении в какой-нибудь консоли.

  9. angry-elf.livejournal.com

    Я когда-то делал рекурсию в шаблоне на самих шаблонах. Достаточно просто получается, в общем-то :)

  10. Алексей

    Elf
    Я когда-то делал рекурсию в шаблоне на самих шаблонах.
    Достаточно просто получается, в общем-то :)

    Но вряд ли настолько же эффективно, как в выше изложенном варианте.

  11. angri

    К вопросу о хранении и отображении деревьев.

    Позволю себе малость попиарить свой скромный проект :) в разрезе того, что там тоже решена проблема вывода деревьев. Может, это покажется интересным: http://sqlamp.angri.ru/#sqlamp.tree_recursive_iterator

  12. angri

    Взглянуть на код можно тут: http://bitbucket.org/angri/sqlamp/src/tip/sqlamp/__init__.py#cl-863

  13. Сергей

    Слова "хотя бы" подразумевают, что это каким-то образом лучше :-). На
    самом деле, мне нужна конкретная причина, чтобы вытащить функцию в
    публичный интерфейс класса или модуля. Все эти функции нужны только в том
    же месте, где определены либо для рекурсии, либо для абстракции одного
    логического куска. Так зачем их публиковать и мусорить namespace?

    Так ведь скорость падает.
    Вот два примера:

    #test1.py
      def f2(x):
          return x+3
      def f1(a):
          return f2(f2(a))
      for i in range(10000000):
          f1(1)
    
    #test2.py
    def f1(a):
        def f2(x):
           return x+3
        return f2(f2(a))
    for i in range(10000000):
        f1(1)
    

    в результате имеем:

    time python test1.py
    python test.py  15,00s user 0,22s system 98% cpu 15,420 total
    time python test2.py
    python test.py  10,99s user 0,23s system 96% cpu 11,621 total
    
  14. [...] 29.10.2009 11:55 Написал пост и чуть позже нашёл статью Ивана про деревья и этот самый фильтр http://softwaremaniacs.org/blog/2009/09/21/trees-in-django-templates/ [...]

  15. [...] Никто не мешает выбрать за один запрос всю таблицу и построить дерево в памяти. Чтобы это начало тормозить, таблица должна быть [...]

  16. Elias

    Кажется закралась ошибка:

    # рекурсивный вывод детей одного 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
    

    выделенное заменить на sub_items = list(tree_level(item.id))

  17. Ivan Sagalaev

    Нет, id там не нужен. Там везде присутствуют ссылки на объекты, потому что они вполне адекватно сравниваются по id и имеют хеши на том же id.

  18. Elias

    Лучше заменить на это:

    # выводит элемент списка с подсписком
    # для подсписка рекурсивно вызывается render_items
    def render_item(item, sub_items, level):
        context.update({'item': item, 'level': level})
        return ''.join([
            '<li>',
            item and self.node_list.render(context) or '',
            sub_items and '<ul>%s</ul>' % ''.join(render_items(sub_items, level + 1)) or '',
            '</li>'
        ])
    

    для доступа к другим переменным контекста.

  19. Alex

    А почему у вас так много функций, определённых внутри методов?

    Слова "хотя бы" подразумевают, что это каким-то образом лучше :-).

    Иван, но они же будут пересоздаваться каждый раз, как выполняется эта функция!

    def f2a(a):
        return f1(a) + 1
    

    будет выглядеть как
    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

    , в то время как

    def f2b(a):
        def f1(a):
            return a + 1
        return f1(a) + 1
    

    выглядит как

     12           0 LOAD_CONST               1 (<code object f1 at 0x7fc362f23648, file "./1.py", line 12>)
                  3 MAKE_FUNCTION            0
                  6 STORE_FAST               1 (f1)
    
     14           9 LOAD_FAST                1 (f1)
                 12 LOAD_FAST                0 (a)
                 15 CALL_FUNCTION            1
                 18 LOAD_CONST               2 (1)
                 21 BINARY_ADD
                 22 RETURN_VALUE
    

    И что-то я не слишком уверен, что команда с названием MAKE_FUNCTION выполняется достаточно быстро.

  20. Ivan Sagalaev

    Поскольку это уже второй комментарий такого рода, не могу не отреагировать :-).

    Заимствуя фразу у Дж. Спольски — "I couldn't care less". Это такие копейки, что грамотный питонист даже не должен пытаться думать в ту сторону, пока не доказано, что именно в этом месте находится критично тормозящий кусок программы. Этим, собственно, и отличается программирование на высокоуровневом языке от низкоуровневого: здесь приоритет читаемости кода, модульности и общей maintainability не то что больше, чем оптимизация скорости вызова отдельных функций, а больше безоговорочно. Иначе бы мы писали на Си (без всякой подколки).

    Я могу не глядя поспорить, что разница в производительности этих двух вариантов будет меньше, чем даже статистическая погрешность при формировании страницы, с которой я начал пример. И даже если таких деревьев там будет 10, тоже результат вряд ли изменится.

  21. Alex

    Ммм, неужели __методы хуже по maintainability, притом что они не вызывают ненужной перегенерации функций?

    И даже если таких деревьев там будет 10, тоже результат вряд ли изменится.

    Хм. Если это одно место - то да, копейки. А можете ли вы не глядя оценить, насколько изменится производительность всей системы, если несоздавание вложенных функций без надобности (т.е., когда они не используют контекста внешней функции) ввести в кодинг-стайл и поправить все такие случаи :) ? У вас ведь яндекс, по идее, в его масштабах любая оптимизация, которую можно несложно сделать, полезна.

    Ну впрочем всё это брюзжание, я согласен. Я и сам лямбда-функциями по месту балуюсь, что ничем не лучше.

  22. Alex

    Иначе бы мы писали на Си (без всякой подколки).

    Хм. Это, кстати, пожалуй, объясняет моё брюзжание. Вложенные функции мне подсознательно не нравятся не потому, что функции пересоздавать, а потому, что оный код Cython-ом не скомпилируется :)

  23. Elias

    Код можно немного модифицировать, и сделать возможность описывать весь html в шаблонах.

  24. Иван

    Совсем недавно мне это понадобилось! Спасибо за вашу работу!

  25. Андрей Григорьев

    Писал реализацию дерева для удобной работы с набором записей в LDAP. Может строить иерархию, например, для имен в LDAP или доменных имен. Может кому пригодится, хотя код наверно не очень хороший.

    http://code.activestate.com/recipes/576966/

  26. master, с чего бы? Это как раз та сортировка. Дальше, если это дерево строго с единичной вложенностью, достаточно сделать {% regroup %} в шаблоне. Если вложенность произвольная, то могу свой {% tree %} предложить.

  27. gygenot

    Все хорошо, только слишком много обращений в базу происходит: только для получения родителя каждый дочерний элемент сделает по вызову в базу. Она конечно первый результат закеширует, но все равно лишние обращения к базе ни к чему.

    Для предотвращения этого я решил сохранять все объекты в памяти (естественно, подразумевается, что объектов не слишком много).

    class Category(models.Model):
        name = models.CharField(max_length=100)
        comment = models.TextField(blank=True)
        date_created = models.DateTimeField(auto_now_add=True)
        date_modified = models.DateTimeField(auto_now=True)
        сategory = models.ForeignKey("self", blank=True, null=True, default=None)
    
    q = list(models.Category.objects.only("name", "category"))
    q = dict(zip([i.id for i in q], q))
    parent_map = defaultdict(list)
    
    def tree_level(parent):
        for item in parent_map[parent]:
            yield q[item]
            sub_items = list(tree_level(item))
            if sub_items:
                yield sub_items
    
     print list(tree_level(None))
    

    Данный код используется для вывода значений иерархически в selectbox, поэтому ограничен список получаемых полей модели, т.к. кроме имени, больше ничего не надо.

  28. gygenot

    В предыдущем примере забыл перед функцией заполнить словарь:

    for item in q.itervalues():
        parent_map[item.category_id].append(item.id)
    
  29. gygenot

    Может кому интересно, выложу функции для вывода значений в список. Бился над ним почти день. Хитрость в том, что нужно вывести все пары сразу в один список, чтобы потом передать в качестве choices виджету:

    def render_item(item, sub_items, level):
        return [(item.pk, u"%s|- %s" % ("  "*level, smart_unicode(item.name))),] +
        (sub_items and render_items(sub_items, level + 1) or [])
    
    def render_items(items, level):
         return list(render_item(h, t, level) for h, t in pairs(items))
    

    Сейчас смотрю на это дело, ведь очень все просто получилось, в чем у меня проблема была даже вспомнить не могу :).

  30. Иван Иванов

    Не используйте метод, который написал gygenot. Вместо этого можно просто выбрать родителей заранее, тогда все категории будут выбираться за один запрос.

    Пример:

    Category.objects.select_related('parent').order_by('ordering')
    

    В результате получится QuerySet, который не полезет в базу за родителем каждый раз. Все уже решено давно.

    Литература:

    http://docs.djangoproject.com/en/dev/ref/models/querysets/#id4

  31. Жнец

    Иван Иванов, зато этот select_related с joinами будет вытаскивать в строки ответа бд все поля родителя, которые не будут использоваться

  32. http://softwaremaniacs.org/blog/2009/09/21/trees-in-django-templates/Если просто отдать ему objects.all(), то он будет создавать запросы для каждого родителя. Select_related по родителю делает 1 запрос с JOIN, но в каждой возвращаемой строке находится и вся информация о родителе.Может есть какой-то способ делать это правильно?

  33. http://softwaremaniacs.org/blog/2009/09/21/trees-in-django-templates/А возможно ли с помощью этой штуки получать отдельные ветки дерева?

  34. Евгений

    Очень полезный сниппет. Буквально вчера столкнулся с проблемой вывода дерева в шаблон. Я пока еще джуниор, поэтому этот код для меня - царский подарок. Иван Сагалаев, спасибо

  35. nip

    Заметил небольшую неприятность - внутри дерева недоступны другие элементы контекста :( А так крайне полезный тэг.

  36. Мой пост про tree пойдёт?

  37. Google user

    Вы нарочно игнорируете весь контекст, кроме определенных:

    {{ item }}, {{ level }}
    

    Если да то зачем?

  38. Ivan Sagalaev

    Никакой определённой причины, кроме общего принципа "явное лучше неявного". Можно и добавить остальной контекст, если надо. Мне тогда не было надо.

  39. Думаю {% tree %} Ивана поможет.http://softwaremaniacs.org/blog/2009/09/21/trees-in-django-templates/

  40. Andrey

    «Нет, id там не нужен. Там везде присутствуют ссылки на объекты, потому что они << вполне адекватно сравниваются по id и имеют хеши на том же id»

    Без id у меня не работает, а только с поправкой, которую Elias указал.

    В любом случае спасибо большое за статью!

  41. ptaiga

    Иван благодарю за тег и фильтр - они мне очень пригодились.

    Также спасибо Elias за дополнения к коду, позволяющее из тега получить доступ к другим переменным контекста.

    От себя добавлю, что в приложениях под Python3 необходимо строчку item = items.next() поменять на item = next(items) или item = items.__next__(), т.к. метод .next() был удален в новой версии языка.

  42. ptaiga

    А возможно ли с помощью этой штуки получать отдельные ветки дерева?

    Как раз столкнулся с этой проблемой и реализовал её добавлением в самое начало функции astree следующих срок:

    for item in items:
      if item.parent and item.parent not in items:
        item.parent = None
    

    Дело в том, что фильтр обрабатывает элементы с parent = None, таким образом нужно в дереве найти отдельные ветки и явно назначить им родителя None.

    Если кто-то может дать обратную связь по этому решению или предложить лучший вариант, то буду благодарен!

Добавить комментарий