Support dynamic menus

[agjohnson]

We've had a few questions from folks with very large Sphinx projects about build time, and so I decided to profile things to see where we are spending time. Profiling shows that the majority of build time is spent generating the toctree on each page. Even with collapse nav == True, 80% of the build time was spent in the toctree menu block.

We've talked for some time about making the toctree a json blob, so we don't have to generate on each page, however I haven't thought or played with the technical implementation here. If we can get away from generating toctree on each page, we can drop build time on RTD by 90% on these projects.

This also opens up the door to doing dynamic searching of toctree elements with the search box, another feature we've wanted.

The next question: how do we do this?

[Blendify]

This is tricky, nothing comes to mind immediately, will have to do some research into the construction of the toctree in sphinx to see if we can override this build step. This may be a feature for the readthedocs builder.

[jessetan]

Some things that come to mind:

• This could be a suggestion for Sphinx, or the code could be contributed upstream when it's working as intended.
• JSON still needs to be transformed to HTML somewhere. Removing toctree generation from RTD build will reduce the one-time build time, but will require it to be built client-side by the reader's browser on every page view. This seems opposed to the idea of static site generation (do expensive conversion once to create readable output) and it will increase the time to render the website in the browser.
• Is the 80% of the build time from a clean build? In an existing project, the toctree can be expected to take most time since it will need to be recreated for every page if there is a change to one single page. The content of the other pages is cached (pickled) by Sphinx.
• Is the time attributed to the toctree the result of creating the hierarchy or from writing the HTML? if it is the latter, is the HTML generated once and then inserted into every page or is the (same) HTML regenerated for every page?

[agjohnson]

Upstream application might be good, but it does fit our use case more than it would the general Sphinx user. Writing this as an extension to sphinx here initially would make sense -- or maybe this is a more general sphinx extension really. It could be possible to write a generalized extension for this.

JSON to HTML render time is a good point, but i don't think it would be blocking. Definitely worth testing on some doc sets if we develop this though.

Is the 80% of the build time from a clean build?

80% of time from a clean build, correct. For more context here, I profiled the docs from godot and from a customer conversation i had -- they have a docset that generates 30G of docs per doc version. Removing toctree generation from output, I was able to reduce godot doc build time greatly by skipping toctree output, reducing their build time to 1m from 20m+. The amount of build resources RTD could save here simply by writing toctree output more efficiently would be big. The same could be said of reducing our JSON builder step as well though, so perhaps we need another sphinx extension for speed optimizations on RTD.

Is the time attributed to the toctree the result of creating the hierarchy or from writing the HTML?

The overhead from writing is really low actually, though it's difficult to tell exactly how long Sphinx spends writing from the profile. Sphinx spends most of it's time in docutils building up a doctree of nodes -- in this case, a doctree of nodes for the toctrees on each doc page.

[Blendify]

I started playing around with this got some very basic logic to write an xml file dump of the page names:

import xml.etree.ElementTree as ET
from sphinx.writers.html import HTMLTranslator

def setup(app):
    """Setup connects events to the sitemap builder"""
    app.connect('html-page-context', add_html_link)
    app.connect('build-finished', create_sitemap)
    app.links = []
    
    def add_html_link(app, pagename, templatename, context, doctree):
    """As each page is built, collect page names for url path"""
    app.links.append(pagename + ".html"
                             
    root = ET.Element("ul")
    
    for link in app.sitemap_links:
       url = ET.SubElement(root, "li")
       ET.SubElement(url, "a").text = link

    filename = app.outdir + "/sidebar.xml"
    ET.ElementTree(root).write(filename,
                               xml_declaration=True,
                               encoding='utf-8',
                               method="xml")  

This can be converted to html using jquery and js: https://stackoverflow.com/questions/16113188/convert-xml-to-html-using-jquery-javascript