Repository: sphinx-doc/sphinx

Issue:
sphinx.search._JavaScriptIndex: non-determinite searchindex.js output
### Describe the bug

While looking at some recent [Reproducible Build](https://reproducible-builds.org/) test failures, I noticed that one of the remaining [differences](https://tests.reproducible-builds.org/debian/rb-pkg/unstable/amd64/diffoscope-results/quodlibet.html) between builds of [`quodlibet`](https://quodlibet.readthedocs.io/) is due to sorting differences in `searchindex.js`, a file produced to enable client-side content search in web browsers.

Looking at the [relevant code in the `sphinx.search._JavaScriptIndex` class](https://github.com/sphinx-doc/sphinx/blob/c1f2a52d5d97f874d84e4d5421c99a566242af6b/sphinx/search/__init__.py#L150-L173), the code to output the `searchindex.js` content is a fairly straightforward [Python built-in `json.dumps`](https://docs.python.org/3/library/json.html#json.dumps) call.

The failures mentioned occurred with Sphinx v5.3.0 -- I believe they would occur when using the latest release v7.2.2 also (the [index export code appears unchanged](https://github.com/sphinx-doc/sphinx/blob/ed84d63e6f2c4fd43b97fc43ee8be4156a13af9e/sphinx/search/__init__.py#L155-L178)).

I think that a fix may be as straightforward as sending a `sort_keys=True` argument to the `json.dumps` call.  Writing test coverage to provide varying inputs that sort unequally otherwise could be the tricky part.

cc @lamby 

### How to Reproduce

I do not yet have a local reproducer for this bug, but the differences in output can be observed in the diffoscope results for `quodlibet` on Sphinx v5.3.0 here: https://tests.reproducible-builds.org/debian/rb-pkg/unstable/amd64/diffoscope-results/quodlibet.html

### Environment Information
Since the reproducer case I'm reporting from was a hosted build, I can't easily run the environment-reporting commands, but some relevant details are:

```text
Sphinx: v5.3.0
Operating System: Debian Linux (unstable / trixie)
Documentation-package-under-test: quodlibet v4.5.0
```


### Sphinx extensions

```python
extensions = ['sphinx.ext.autodoc', 'sphinx.ext.extlinks', 'contributors']
```


### Additional context

_No response_

Discussion:
pietroalbini: Is the Windows failure a spurious one? I don't think I changed anything that would influence translations.
AA-Turner: Yes, there's an issue about it somewhere (@jayaddison had a go at fixing it to no avail)

A
jayaddison: > @.pietroalbini Is the Windows failure a spurious one? I don't think I changed anything that would influence translations.

> @.AA-Turner Yes, there's an issue about it somewhere (@jayaddison had a go at fixing it to no avail)

Ah, yep - that's #11232.  I think we've gotten fairly close to the cause - my latest guess was [these lines here](https://github.com/sphinx-doc/sphinx/blob/fcc38997f1d9b728bb4ffc64fc362c7763a4ee25/tests/test_intl.py#L54-L56).  It's something to do with whether an internationalized byte-order-mark file is rewritten.
AA-Turner: @pietroalbini it looks like I can't push to this branch / apply review comments -- please could you check if the tick-box is ticked for allowing me to do this?

Thanks,
Adam
pietroalbini: Applied all suggestions and rebased on top of master.

> it looks like I can't push to this branch / apply review comments -- please could you check if the tick-box is ticked for allowing me to do this?

Unfortunately the organization I created the fork on doesn't support that :slightly_frowning_face: (it's an enterprise org with SSO).

Patch:
diff --git a/CHANGES.rst b/CHANGES.rst
index 10abb27b4..b02c10934 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -18,6 +18,8 @@ Bugs fixed
 
 * #11668: Raise a useful error when ``theme.conf`` is missing.
   Patch by Vinay Sajip.
+* #11622: Ensure that the order of keys in ``searchindex.js`` is deterministic.
+  Patch by Pietro Albini.
 
 Testing
 -------
diff --git a/sphinx/search/__init__.py b/sphinx/search/__init__.py
index 21758d3f4..114d7fe90 100644
--- a/sphinx/search/__init__.py
+++ b/sphinx/search/__init__.py
@@ -162,7 +162,7 @@ class _JavaScriptIndex:
     SUFFIX = ')'
 
     def dumps(self, data: Any) -> str:
-        return self.PREFIX + json.dumps(data) + self.SUFFIX
+        return self.PREFIX + json.dumps(data, sort_keys=True) + self.SUFFIX
 
     def loads(self, s: str) -> Any:
         data = s[len(self.PREFIX):-len(self.SUFFIX)]


Test patch:
diff --git a/tests/test_search.py b/tests/test_search.py
index 68a7b01aa..d4bbef5b3 100644
--- a/tests/test_search.py
+++ b/tests/test_search.py
@@ -304,3 +304,40 @@ def test_parallel(app):
     app.build()
     index = load_searchindex(app.outdir / 'searchindex.js')
     assert index['docnames'] == ['index', 'nosearch', 'tocitem']
+
+
+@pytest.mark.sphinx(testroot='search')
+def test_search_index_is_deterministic(app):
+    lists_not_to_sort = {
+        # Each element of .titles is related to the element of .docnames in the same position.
+        # The ordering is deterministic because .docnames is sorted.
+        '.titles',
+        # Each element of .filenames is related to the element of .docnames in the same position.
+        # The ordering is deterministic because .docnames is sorted.
+        '.filenames',
+    }
+
+    # In the search index, titles inside .alltitles are stored as a tuple of
+    # (document_idx, title_anchor). Tuples are represented as lists in JSON,
+    # but their contents must not be sorted. We cannot sort them anyway, as
+    # document_idx is an int and title_anchor is a str.
+    def is_title_tuple_type(item):
+        return len(item) == 2 and isinstance(item[0], int) and isinstance(item[1], str)
+
+    def assert_is_sorted(item, path):
+        err_path = path if path else '<root>'
+        if isinstance(item, dict):
+            assert list(item.keys()) == sorted(item.keys()), f'{err_path} is not sorted'
+            for key, value in item.items():
+                assert_is_sorted(value, f'{path}.{key}')
+        elif isinstance(item, list):
+            if not is_title_tuple_type(item) and path not in lists_not_to_sort:
+                assert item == sorted(item), f'{err_path} is not sorted'
+            for i, child in enumerate(item):
+                assert_is_sorted(child, f'{path}[{i}]')
+
+    app.builder.build_all()
+    index = load_searchindex(app.outdir / 'searchindex.js')
+    # Pretty print the index. Only shown by pytest on failure.
+    print(f'searchindex.js contents:\n\n{json.dumps(index, indent=2)}')
+    assert_is_sorted(index, '')