Repository: sphinx-doc/sphinx

Issue:
TOC in navigation side bar is generated incorrectly for depth > 3 
### Describe the bug

The global table of contents in the navigation side bar isn’t generated correctly when the depth of the current document is more than 3.

### How to Reproduce

 
```bash
$ cat index.rst 
index
------

.. toctree::

    a

$ cat a.rst 
a
--

.. toctree::

    b

$ cat b.rst 
b
--

.. toctree::

    c

$ cat c.rst 
c
--

.. toctree::

    d
$ cat d.rst 
d
--

$ sphinx-build -m html . _build
```
**Output**  
Table of contents in navigation sidebar on page `d.html` only shows link to page `a`

**Expected Output**  
All the ancestors till the current page: a, b, c, d were expected to be shown.

### Environment Information

```text
Platform:              linux; (Linux-6.6.31+rpt-rpi-v8-aarch64-with-glibc2.36)
Python version:        3.11.2 (main, Aug 26 2024, 07:20:54) [GCC 12.2.0])
Python implementation: CPython
Sphinx version:        8.1.0+/1b08b66d1
Docutils version:      0.20.1
Jinja2 version:        3.1.4
Pygments version:      2.18.0
```


### Sphinx extensions

_No response_

### Additional context

_No response_

Discussion:
@khanxmetu: Not really sure if this was an intended behavior in global toctree generation to avoid generating siblings at every level of depth in order to reduce build times.  
@mgeier: This likely depends on the HTML theme you are using. With the default `alabaster` theme I'm seeing links to a, b, c and d.

What theme are you using?@khanxmetu: > This likely depends on the HTML theme you are using. With the default `alabaster` theme I'm seeing links to a, b, c and d.
> 
> 
> 
> What theme are you using?

I'm using alabaster too. Sorry for the wrong assumption, the issue  
isn't related to tree depth.

I had a hard time reproducing as well and I figured that the problem occurred due to adding a toctree entry of some document and building the second time while keeping previous build's files.

Here is the reproducer:

```bash
$ cat index.rst
index
-----

.. toctree::
    a

$ cat b.rst 
b
--

.. toctree::


$ cat c.rst 
c
--


$ sphinx-build -b html . _build/

$ # add doc c into b's toctree
$ vi b.rst
$ cat b.rst 
b
--

.. toctree::
    c

$ # build again
$ sphinx-build -b html . _build/

$ cat _build/c.html | grep 'href="a.html"'
<li class="toctree-l1"><a class="reference internal" href="a.html">a</a></li>
$ cat _build/c.html | grep 'href="b.html"'
$ cat _build/c.html | grep 'href="#"'
```
c.html should contain links to a,b and self, however it only contains a link to a.html




Solution patch:
diff --git a/CHANGES.rst b/CHANGES.rst
index a214b3dec82..766b5cc209d 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -142,6 +142,11 @@ Bugs fixed
   which always kept the cache for positive values, and always refreshed it for
   negative ones.
   Patch by Nico Madysa.
+* #12888: Add a warning when document is included in multiple toctrees
+  and ensure deterministic resolution of global toctree in parallel builds
+  by choosing the lexicographically greatest parent document.
+  Patch by A. Rafey Khan
+
 
 Testing
 -------
diff --git a/sphinx/builders/__init__.py b/sphinx/builders/__init__.py
index c463ee561b4..4f1815b40da 100644
--- a/sphinx/builders/__init__.py
+++ b/sphinx/builders/__init__.py
@@ -691,6 +691,9 @@ def write(
                     docnames.add(tocdocname)
         docnames.add(self.config.root_doc)
 
+        # sort to ensure deterministic toctree generation
+        self.env.toctree_includes = dict(sorted(self.env.toctree_includes.items()))
+
         with progress_message(__('preparing documents')):
             self.prepare_writing(docnames)
 
diff --git a/sphinx/environment/__init__.py b/sphinx/environment/__init__.py
index 9d9f077c508..871810bfeff 100644
--- a/sphinx/environment/__init__.py
+++ b/sphinx/environment/__init__.py
@@ -772,6 +772,10 @@ def check_consistency(self) -> None:
                 logger.warning(
                     __("document isn't included in any toctree"), location=docname
                 )
+        # Call _check_toc_parents here rather than in  _get_toctree_ancestors()
+        # because that method is called multiple times per document and would
+        # lead to duplicate warnings.
+        _check_toc_parents(self.toctree_includes)
 
         # call check-consistency for all extensions
         self.domains._check_consistency()
@@ -817,3 +821,24 @@ def _traverse_toctree(
             if sub_docname not in traversed:
                 yield sub_parent, sub_docname
                 traversed.add(sub_docname)
+
+
+def _check_toc_parents(toctree_includes: dict[str, list[str]]) -> None:
+    toc_parents: dict[str, list[str]] = {}
+    for parent, children in toctree_includes.items():
+        for child in children:
+            toc_parents.setdefault(child, []).append(parent)
+
+    for doc, parents in sorted(toc_parents.items()):
+        if len(parents) > 1:
+            logger.info(
+                __(
+                    'document is referenced in multiple toctrees: %s, selecting: %s <- %s'
+                ),
+                parents,
+                max(parents),
+                doc,
+                location=doc,
+                type='toc',
+                subtype='multiple_toc_parents',
+            )


Test patch:
diff --git a/tests/roots/test-toctree-multiple-parents/alpha.rst b/tests/roots/test-toctree-multiple-parents/alpha.rst
new file mode 100644
index 00000000000..c77c94122e1
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/alpha.rst
@@ -0,0 +1,7 @@
+Alpha
+=====
+
+.. literalinclude:: relation_graph.txt
+
+.. toctree::
+   bravo
diff --git a/tests/roots/test-toctree-multiple-parents/bravo.rst b/tests/roots/test-toctree-multiple-parents/bravo.rst
new file mode 100644
index 00000000000..9f65ea6be10
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/bravo.rst
@@ -0,0 +1,7 @@
+Bravo
+=====
+
+.. literalinclude:: relation_graph.txt
+
+.. toctree::
+   charlie
diff --git a/tests/roots/test-toctree-multiple-parents/charlie.rst b/tests/roots/test-toctree-multiple-parents/charlie.rst
new file mode 100644
index 00000000000..931979b62df
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/charlie.rst
@@ -0,0 +1,4 @@
+Charlie
+=======
+
+.. literalinclude:: relation_graph.txt
diff --git a/tests/roots/test-toctree-multiple-parents/conf.py b/tests/roots/test-toctree-multiple-parents/conf.py
new file mode 100644
index 00000000000..4db50a3c6ef
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/conf.py
@@ -0,0 +1 @@
+html_theme = 'basic'
diff --git a/tests/roots/test-toctree-multiple-parents/delta.rst b/tests/roots/test-toctree-multiple-parents/delta.rst
new file mode 100644
index 00000000000..f9887912a0e
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/delta.rst
@@ -0,0 +1,7 @@
+Delta
+=====
+
+.. literalinclude:: relation_graph.txt
+
+.. toctree::
+   charlie
diff --git a/tests/roots/test-toctree-multiple-parents/index.rst b/tests/roots/test-toctree-multiple-parents/index.rst
new file mode 100644
index 00000000000..d642aa111b7
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/index.rst
@@ -0,0 +1,8 @@
+test-toctree-multiple-parents
+=============================
+
+.. literalinclude:: relation_graph.txt
+
+.. toctree::
+   alpha
+   delta
diff --git a/tests/roots/test-toctree-multiple-parents/relation_graph.txt b/tests/roots/test-toctree-multiple-parents/relation_graph.txt
new file mode 100644
index 00000000000..a610eac2622
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/relation_graph.txt
@@ -0,0 +1,7 @@
+     index
+    /     \
+ alpha   delta
+    \      /
+   bravo  /
+      \  /
+     charlie
diff --git a/tests/test_builders/test_build.py b/tests/test_builders/test_build.py
index 6a5ed0b6d26..5f396cc48af 100644
--- a/tests/test_builders/test_build.py
+++ b/tests/test_builders/test_build.py
@@ -100,6 +100,14 @@ def test_numbered_circular_toctree(app):
     ) in warnings
 
 
+@pytest.mark.sphinx('text', testroot='toctree-multiple-parents')
+def test_multiple_parents_toctree(app):
+    app.build(force_all=True)
+    assert (
+        "document is referenced in multiple toctrees: ['bravo', 'delta'], selecting: delta <- charlie"
+    ) in app.status.getvalue()
+
+
 @pytest.mark.usefixtures('_http_teapot')
 @pytest.mark.sphinx('dummy', testroot='images')
 def test_image_glob(app):
diff --git a/tests/test_builders/test_build_html_toctree.py b/tests/test_builders/test_build_html_toctree.py
index 7b9e5a49d13..a59de6328e6 100644
--- a/tests/test_builders/test_build_html_toctree.py
+++ b/tests/test_builders/test_build_html_toctree.py
@@ -1,6 +1,7 @@
 """Test the HTML builder and check output against XPath."""
 
 import re
+from unittest.mock import patch
 
 import pytest
 
@@ -63,3 +64,24 @@ def test_numbered_toctree(app):
 def test_singlehtml_hyperlinks(app, cached_etree_parse, expect):
     app.build()
     check_xpath(cached_etree_parse(app.outdir / 'index.html'), 'index.html', *expect)
+
+
+@pytest.mark.sphinx(
+    'html',
+    testroot='toctree-multiple-parents',
+    confoverrides={'html_theme': 'alabaster'},
+)
+def test_toctree_multiple_parents(app, cached_etree_parse):
+    # The lexicographically greatest parent of the document in global toctree
+    # should be chosen, regardless of the order in which files are read
+    with patch.object(app.builder, '_read_serial') as m:
+        # Read files in reversed order
+        _read_serial = type(app.builder)._read_serial
+        m.side_effect = lambda docnames: _read_serial(app.builder, docnames[::-1])
+        app.build()
+        # Check if charlie is a child of delta in charlie.html
+        xpath_delta_children = (
+            ".//ul[@class='current']//a[@href='delta.html']/../ul/li//a"
+        )
+        etree = cached_etree_parse(app.outdir / 'charlie.html')
+        check_xpath(etree, 'charlie.html', xpath=xpath_delta_children, check='Charlie')