Liquid Data Structures

04 Jul 2019 - zach

The Problem

After much consternation, I had finally decided what I wanted my website to look like. My final design was perhaps disapointingly basic, given how much time I had thought about it. But the old fashioned header-section-sidebar-footer layout is a tried-and-true way to make content intuitive for readers.

I was pleased that every item on the page was either something I had already written or could write very quickly. But there was one element that I did not have the faintest idea how to write: a drop-down menu in the navigation ribbon.

The menu made sense because all the pages in my website are laid out in a tree, with index.HTML as the root. Every category of posts may have any number of subcategories, all of which may have subcategories of their own.

Jekyll and Liquid gave me the ability to make this tree structure convenient. I wrote Liquid code such that I could simply write a new category page, specity its parent category in the frontmatter, and see it fully reflected everywhere in the site without having to touch a single other page.

I had already used Liquid to reflect this in category pages. The layout for a category page contains Liquid code that (1) displays all posts in the category subtree, and (2) displays all immediate child categories.

The former feature is where I started to run into difficulties. The problem was very simple: traverse the tree rooted at the page’s category, collect all posts in each category, and display them all at the end. But I discovered that Liquid has a number of limitations.

No while loops
No recursion
No way to instantiate arrays, or manipulate them at all, really
Really terrible commenting syntax

Perhaps Liquid is just so genius that I don’t understand it. It wouldn’t be the first time I failed to appreciate a technology. More likely, however, I’m just using it to do things it was never meant to do. So, of course, I wanted to see just how far I could stretch it.

The Algorithm

I needed an algorithm that would traverse the tree of the website and output every category in the form of an HTML unordered list. It had to be 100% imperative and could not use function calls of any kind.

I knew that a preorder tree traversal would go in the correct order. The only question was how it could decide which HTML elements to to place and close.

Some heuristic experimentation revealed that the placement of HTML elements varied in three scenarios:

If the traversal goes down a level, start a list element, place a hyperlink, and start another list.
If the traversal goes to a sibling category, close the previous list, close the previous list element, start a new list element, place a hyperlink, and start a new list.
If the traversal goes up n levels, then for each level, close a list and close a list element. Then, close a list, close a list element, place a hyperlink, and open a list.

I chose the iterative version of the preorder tree traversal algorithm, using a stack. To keep track of how many levels up up the traversal went when popping the next element off the stack, I chose to store breadcrumbs of each level on another stack. I think there’s a term in CLRS for this, but I don’t remember what it is.

So the algorithm is:

visitStack
push index.html to visitStack

breadcrumbStack

add <ul>

while visitStack is not empty {
    pop a page off visitStack
    if breadcrumbStack.peek is not the page's parent {
        if breadcrumbStack.peek is not the page's grandparent {
            while breadcrumbStack.peek is not the page's parent {
                pop breadcrumbStack
                add </ul></li>
            }
            add </ul></li><li><a href="page.url">page.title</a><ul>
        } else {
            push page's parent to breadcrumbStack
            add <li><a href="page.url">page.title</a><ul>
        }
    } else {
        </ul></li><li><a href="page.url">page.title</a><ul>
    }
    add all page's children to visitStack
}

while breadcrumbStack is not empty {
    add </ul></li>
}

</ul>

The While Loop Workaround

Only for loops are supported in Liquid. Since indefinite iteration is necessary for a tree traversal, there must be a workaround. Fortunately, the iteration doesn’t have to be totally unbounded. If there is an upper bound to the number of iterations, you can combine a for loop with if and break statements. For example:

{% for notUsed in site.pages %}{% if condition %}
    ... here have code
{% else %}{% break %}{% endif %}{% endfor %}

One drawback is that the upper limit is specific to this problem. For every while loop you implement in Liquid, you must find an upper bound, which not all problems have.

The Liquid Stack

This is where I really ran into syntax limitations. The easiest way for me to implement a stack in Liquid was to use an array and a number to indicate the latest index.

However, Liquid has very poor syntax for arrays. For one, it’s completely impossible to instantiate them. If you want an array, you have to take an array that already exists (like site.pages) and manipulate it with filters and concatenation. And even then, there are more shortcomings.

Initialization

Initialization is fairly straightforward.

{% assign breadcrumbStack = nil %}
{% assign breadcrumbStackPop = -1 %}

However, a non-empty stack is always easier to work with. You can use the concat and size filters.

{% assign visitStack = site.pages | where:"attribute","desired" %}
{% assign visitStackPop = visitStack | size %}
{% assign visitStackPop = visitStackPop | minus: 1 %}

Peek

Just view the array at the pop index:


{{ visitStack[visitStackPop] }}

Push

The main issue with pushing to a stack is that you can only concatenate two arrays together, which means that you must somehow convert the item you want to an array. Shopify suggests that you use the split filter to append a string, but fortunately, in this problem, I just used the results of the where filter.

Another implication of this rule is that if the stack is empty (that is, it is nil), you can’t use the concat filter, either. So I had to use an if statement to check for that.

{% assign toAdd = site.pages | where:"category",parentCat %}
{% if breadcrumbStackPop < 0 %}
    {% assign breadcrumbStack = toAdd %}
{% else %}
    {% assign breadcrumbStack = breadcrumbStack | concat: toAdd %}
{% endif %}
{% assign breadcrumbStackPop = breadcrumbStackPop | plus: 1 %}

Pop

Popping an element from a stack is a real pain in the butt. First, you have to decrement the pop index. Then, since you can’t use a dot expression in a where filter, you have to store the bottom page’s category as a variable. Finally, you must build the stack all over again.

{{visitStack[visitStackPop].title}}
{% assign visitStackPop = visitStackPop | minus: 1 %}
{% assign tmpCat = visitStack[0].category %}
{% assign tmpStack = site.pages | where:"category",tmpCat %}
{% for i in (1..visitStackPop) %}
    {% assign tmpCat = visitStack[i].category %}
    {% assign tmpArr = site.pages | where:"category",tmpCat %}
    {% assign tmpStack = tmpStack | concat: tmpArr %}
{% endfor %}
{% assign visitStack = tmpStack %}

If it were possible in Liquid to just assign variable indexes, like

visitStack[x] = y,

that would make this data structure so much easier to implement.

Implementation

It took me a while to write and especially debug this, but this is the Liquid that generates the multi-level dropdown menus on my home page.

<ul>

{% assign visitStack = site.pages | where:"parent_category","root" %}
{% assign visitStackPop = visitStack | size %}
{% assign visitStackPop = visitStackPop | minus: 1 %}

{% assign breadcrumbStack = nil %}
{% assign breadcrumbStackPop = -1 %}

{% for notUsed in site.pages %}{% if visitStackPop > -1 %}

    {% comment %}Seriously, this is what it takes to pop a stack{% endcomment %}
    {% assign thisPage = visitStack[visitStackPop] %}
    {% assign visitStackPop = visitStackPop | minus: 1 %}
    {% assign tmpCat = visitStack[0].category %}
    {% assign tmpStack = site.pages | where:"category",tmpCat %}
    {% for i in (1..visitStackPop) %}
        {% assign tmpCat = visitStack[i].category %}
        {% assign tmpArr = site.pages | where:"category",tmpCat %}
        {% assign tmpStack = tmpStack | concat: tmpArr %}
    {% endfor %}
    {% assign visitStack = tmpStack %}

    {% if breadcrumbStackPop < 0 or breadcrumbStack[breadcrumbStackPop].category != thisPage.parent_category %}
        {% assign parentCat = thisPage.parent_category %}
        {% assign thisPageParent = site.pages | where:"category",parentCat %}{% comment %}this is an array{% endcomment %}
        {% if breadcrumbStackPop >= 0 and breadcrumbStack[breadcrumbStackPop].category != thisPageParent[0].parent_category %}
            {% for notUsed2 in site.pages %}{% if breadcrumbStack[breadcrumbStackPop].category != thisPage.parent_category %}
                {% assign breadcrumbStackPop = breadcrumbStackPop | minus: 1 %}
                {% assign tmpCat = breadcrumbStack[0].category %}
                {% assign tmpStack = site.pages | where:"category",tmpCat %}
                {% for i in (1..breadcrumbStackPop) %}
                    {% assign tmpCat = breadcrumbStack[i].category %}
                    {% assign tmpArr = site.pages | where:"category",tmpCat %}
                    {% assign tmpStack = tmpStack | concat: tmpArr %}
                {% endfor %}
                {% assign breadcrumbStack = tmpStack %}
                </ul></li>
            {% else %}{% break %}{% endif %}{% endfor %}
            </ul></li><li><a href="{{thisPage.url}}">{{thisPage.title}}</a><ul>
        {% else %}{% comment %}You went down a level{% endcomment %}
                {% assign toAdd = site.pages | where:"category",parentCat %}
                {% if breadcrumbStackPop < 0 %}
                    {% assign breadcrumbStack = toAdd %}
                {% else %}
                    {% assign breadcrumbStack = breadcrumbStack | concat: toAdd %}
                {% endif %}
                {% assign breadcrumbStackPop = breadcrumbStackPop | plus: 1 %}
                <li><a href="{{thisPage.url}}">{{thisPage.title}}</a><ul>
        {% endif %}
    {% else %}{% comment %}You went to a sibling{% endcomment %}
        </ul></li><li><a href="{{thisPage.url}}">{{thisPage.title}}</a><ul>
    {% endif %}

    {% assign thisPageCategory = thisPage.category %}{% comment %}this language is ridiculous{% endcomment %}
    {% assign pageChildren = site.pages | where:"parent_category",thisPageCategory %}
    {% unless visitStackPop < 0 %}
        {% assign visitStack = visitStack | concat: pageChildren %}
    {% else %}
        {% assign visitStack = pageChildren %}
    {% endunless %}
    {% assign visitStackPop = visitStackPop | plus: pageChildren.size %}

{% else %}{% break %}{% endif %}{% endfor %}

{% for notUsed in site.pages %}{% if breadcrumbStackPop > -1 %}
    {% assign breadcrumbStackPop = breadcrumbStackPop | minus: 1 %}
    {% assign tmpCat = breadcrumbStack[0].category %}
    {% assign tmpStack = site.pages | where:"category",tmpCat %}
    {% for i in (1..breadcrumbStackPop) %}
        {% assign tmpCat = breadcrumbStack[i].category %}
        {% assign tmpArr = site.pages | where:"category",tmpCat %}
        {% assign tmpStack = tmpStack | concat: tmpArr %}
    {% endfor %}
    {% assign breadcrumbStack = tmpStack %}
    </ul></li>
{% endif %}{% endfor %}

</ul>

Afterword

One thing I definitely took for granted in computer science are data structures, and how easy they are to implement in most languages.

As for making the dropdown menus work, that was done entirely in CSS thanks to a number of web tutorials, especially the HTML Dog tutorial here.