Draft: Environment.file_to_rebuild: pickle to sorted `list` instead of `set`

[jayaddison]

Feature or Bugfix

• Bugfix

Purpose

• Attempt to resolve nondeterministic toctree rendering, by removing randomisable runtime set content ordering (that may be pickled to .doctree files).

Detail

• Instead of storing Environment.files_to_rebuild -- a cached/pickled doctree attribute that is used as an ordered iterator by some of the table-of-contents generation code -- using Python's built-in set datatype, use the built-in list type instead.
• Maintain some performance scalability opportunities by ensuring that the list value is stored in sorted order.
• May introduce some runtime performance regression. Building ephemeral SortedList instances after deserialization of pickled .doctree contents, and then subsequently re-casting to list before pickling could improve this.
• Requires an increment to the Sphinx env pickle version number (63 to 64).

Relates

• May resolve #6714 (requires testing).

cc @bmwiedemann

[bmwiedemann]

I tried this patch on top of 8.0.2 and still got similar diffs: when comparing builds on 1-core-VM and 4-core-VM: https://rb.zq1.de/other/kernel-docs/kernel-source-compare.out

[bmwiedemann]

also note, that in the diff, not just the order changes, but whole blocks go missing.

[jayaddison]

Ok, thank you. I'd suggest we focus on one of the ToC entries that is entirely absent during one of the builds, and try to determine where that inclusion/exclusion originates. One opportunity for that is the Core API Documentation entry, I think.

[jayaddison]

My working theory in this branch was that the .doctree could be a causal link in the nondeterminism of the ToC trees; for the record there were three sources of nondeterminism in .doctree writing:

• The build path is embedded in some filenames in the file. I resolved these by using a fixed build path for each build.
• Dynamic timestamps are associated with each docname in the file by this line of code -- I resolved this temporarily by using a fixed/constant value, but it would be better handled by using SOURCE_DATE_EPOCH instead.
• The ordering of some of the data within the file was not deterministic -- this branch resolved that factor, at least for some small-scale test builds (of test-toctree in particular).

[jayaddison]

Ok, thank you. I'd suggest we focus on one of the ToC entries that is entirely absent during one of the builds, and try to determine where that inclusion/exclusion originates. One opportunity for that is the Core API Documentation entry, I think.

The findings at https://github.com/sphinx-doc/sphinx/issues/6714#issuecomment-2344865013 uncover more about what was happening there: basically, some elements in the HTML navigational menu are included/omitted based on build-time non-determinism.

On further inspection I note that env.numbered_toctrees also appears to be a factor in the traversal order of the toctree nodes. Perhaps it too may require item-order stabilization? (currently it appears to be stored in a Python set). Note that this is not necessarily the same as sorted / lexicographic order; sometimes there are reasons to retain a different ordering.

[jayaddison]

Ok, thank you. I'd suggest we focus on one of the ToC entries that is entirely absent during one of the builds, and try to determine where that inclusion/exclusion originates. One opportunity for that is the Core API Documentation entry, I think.

The findings at #6714 (comment) uncover more about what was happening there: basically, some elements in the HTML navigational menu are included/omitted based on build-time non-determinism.

On further inspection I note that env.numbered_toctrees also appears to be a factor in the traversal order of the toctree nodes. Perhaps it too may require item-order stabilization? (currently it appears to be stored in a Python set). Note that this is not necessarily the same as sorted / lexicographic order; sometimes there are reasons to retain a different ordering.

Nope; seems more likely to be env.glob_toctrees that's relevant here, now that I think about it; at least in the case of these navigation menu elements.

[jayaddison]

Closing; this changeset doesn't resolve the linked issue as-is, and I'm not currently aware of a pressing need to make the (intermediate output) .doctree files deterministic.