Repository: sphinx-doc/sphinx

Issue:
sphinx-build -jauto has nondeterministic html results
**Describe the bug**
html rendering with -jauto has nondeterministic results, except when run on a 1-core-VM

**To Reproduce**
Steps to reproduce the behavior:
```
osc checkout openSUSE:Factory/kernel-docs && cd $_
osc build --noservice
# extract html/Documentation/output/core-api/refcount-vs-atomic.html
# compare to those from another build

or maybe

git clone --depth 1 git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
cd linux-2.6
make htmldocs
```

**Expected behavior**
output should be deterministic

**Your project**
https://github.com/torvalds/linux/blob/master/Documentation/conf.py

**Screenshots**

```diff
-<p>Il kernel è scritto nel linguaggio di programmazione C <a class="reference internal" href="../../../process/programming-language.html#href_anchor" id="a_idN"><span>[c-language]</span></a>.
-Più precisamente, il kernel viene compilato con <code class="docutils literal notranslate"><span class="pre">gcc</span></code> <a class="reference internal" href="../../../process/programming-language.html#href_anchor" id="a_idN"><span>[gcc]</span></a> usando
-l’opzione <code class="docutils literal notranslate"><span class="pre">-std=gnu89</span></code> <a class="reference internal" href="../../../process/programming-language.html#href_anchor" id="a_idN"><span>[gcc-c-dialect-options]</span></a>: il dialetto GNU
+<p>Il kernel è scritto nel linguaggio di programmazione C <a class="reference internal" href="#href_anchor" id="a_idN"><span>[c-language]</span></a>.
+Più precisamente, il kernel viene compilato con <code class="docutils literal notranslate"><span class="pre">gcc</span></code> <a class="reference internal" href="#href_anchor" id="a_idN"><span>[gcc]</span></a> usando
+l’opzione <code class="docutils literal notranslate"><span class="pre">-std=gnu89</span></code> <a class="reference internal" href="#href_anchor" id="a_idN"><span>[gcc-c-dialect-options]</span></a>: il dialetto GNU
```

**Environment info**
- OS: openSUSE Tumbleweed
- Python version: 3.7.3
- Sphinx version: 2.2.0
- Sphinx extensions: websupport, devhelp, htmlhelp, jsmath, serializinghtml

**Additional context**
Got same result when adding -E

This bug was found while working on reproducible builds for openSUSE.

Discussion:
khanxmetu: This PR only resolves the issue of non-determinism, however users may still have their own expectations of what parent should be chosen which is not trivial to solve. I think we should warn the user when a document is included in multiple toctrees. What do you think?
khanxmetu: 
>   * Whether tree depth might be better than lexicographic order as a sort key (@khanxmetu has also [noted this as a possibility](https://github.com/sphinx-doc/sphinx/issues/6714#issuecomment-2351757525) in an updated comment)

This seems a better approach than solely relying upon lexicographic order. However note that sorting and lexicographic order is still required to break the tie in case of equal path depths. Besides that, are you proposing for minimum or maximum path depth to be chosen? Note that global toctree generation is an expensive process as it generates siblings for each nested level.  

>   * A question really: it puzzles me slightly that we have nondeterminism here and not in the breadcrumb navigation trail (e.g. `System Emulation > QEMU System Emulator Targets > PowerPC System emulator > pSeries family boards (pseries) > ...` in the header of the referenced [`qemu` page](https://www.qemu.org/docs/master/specs/ppc-spapr-numa.html)).  Does that component gather the navtree differently?  (I should, and will eventually, check)

Thank you for bringing this up. I found two important issues:
1. It's true that the navtree header is different than what is shown in the sidebar but the problem in this specific case of qemu is not related to determinism. I've opened a new issue for that: #12926

2. You're right that navtree header is gathered differently than the global toctree and this needs to be considered here. The parents in the navtree header come from `BuildEnvironment.collect_relations()` which uses `_traverse_toctree()` generator. Here an *in order* tree traversal takes place and the relations: parent, prev, next are generated in one pass. The parent obtained from in order traversal is the one that is discovered first in traversal and doesn't depend on lexicograph order or path depth. We also need to make sure this is consistent with our desired behavior of toctree generation. (In case of qemu’s specs/ppc-spapr-numa, navtree header happens to be generated consistently with toctree ancestors by chance).

I propose that shortest depth path should be chosen. We can add a BFS traversal function similar to `_traverse_toctree` to find the parents for all nodes satisfying shortest path. I would also suggest that we precompute desired parent mapping and use the same implementation for `_get_toctree_ancestors `.
jayaddison: > > * Whether tree depth might be better than lexicographic order as a sort key (@khanxmetu has also [noted this as a possibility](https://github.com/sphinx-doc/sphinx/issues/6714#issuecomment-2351757525) in an updated comment)
> 
> This seems a better approach than solely relying upon lexicographic order. However note that sorting and lexicographic order is still required to break the tie in case of equal path depths. Besides that, are you proposing for minimum or maximum path depth to be chosen?

Thanks @khanxmetu, that makes sense that a tiebreaker will still be required if we use a path-depth approach.

To answer whether I'm suggesting to include path-depth in the sorting: initially I say no, let's continue to use solely lexicographic sorting -- because whatever method we choose, I think some projects/pages will still emit sidebar navigation menus that seem unexpected to some people, because the origin of the ambiguity is in the source files.

Even so, I think additional discussion of the navtree is worthwhile:
 
> 2. You're right that navtree header is gathered differently than the global toctree and this needs to be considered here. The parents in the navtree header come from `BuildEnvironment.collect_relations()` which uses `_traverse_toctree()` generator. Here an _in order_ tree traversal takes place and the relations: parent, prev, next are generated in one pass. The parent obtained from in order traversal is the one that is discovered first in traversal and doesn't depend on lexicograph order or path depth. We also need to make sure this is consistent with our desired behavior of toctree generation. (In case of qemu’s specs/ppc-spapr-numa, navtree header happens to be generated consistently with toctree ancestors by chance).

I wouldn't worry too much about ensuring that the navtree is always consistent with the sidebar toctree; as you've noticed in #12926, table-of-contents displays can be customized by themes and layout; my sense is that it could be difficult to get them to correspond precisely, and also that additional tree traversals might introduce unpredictable build performance changes (especially for large projects).

To resolve the bug we can focus on making the build output stable (ensuring that it stays the same for two or more subsequent builds) - and your changeset here already does that.

**If** it seems easy to re-use logic between `_traverse_toctree` and `_get_toctree_ancestors`,  -- or alternatively to rename them to make them more distinct -- then that could be a nice subsequent cleanup as a separate pull request, but I don't think that's required initially.
AA-Turner: Our docs are failing... should we consider "INFO" for this or is "WARNING" appropriate? This is just to fix determinism so I think "WARNING" is a bit heavy...

```
/home/runner/work/sphinx/sphinx/doc/usage/configuration.rst: WARNING: document is referenced in multiple toctrees: ['usage/index', 'index'], selecting: usage/index <- usage/configuration [toc.multiple_toc_parents]
  /home/runner/work/sphinx/sphinx/doc/usage/extensions/index.rst: WARNING: document is referenced in multiple toctrees: ['usage/index', 'index'], selecting: usage/index <- usage/extensions/index [toc.multiple_toc_parents]
  /home/runner/work/sphinx/sphinx/doc/usage/restructuredtext/index.rst: WARNING: document is referenced in multiple toctrees: ['usage/index', 'index'], selecting: usage/index <- usage/restructuredtext/index [toc.multiple_toc_parents]
```
jayaddison: > Our docs are failing... should we consider "INFO" for this or is "WARNING" appropriate? This is just to fix determinism so I think "WARNING" is a bit heavy...
> 
> ```
> /home/runner/work/sphinx/sphinx/doc/usage/configuration.rst: WARNING: document is referenced in multiple toctrees: ['usage/index', 'index'], selecting: usage/index <- usage/configuration [toc.multiple_toc_parents]
>   /home/runner/work/sphinx/sphinx/doc/usage/extensions/index.rst: WARNING: document is referenced in multiple toctrees: ['usage/index', 'index'], selecting: usage/index <- usage/extensions/index [toc.multiple_toc_parents]
>   /home/runner/work/sphinx/sphinx/doc/usage/restructuredtext/index.rst: WARNING: document is referenced in multiple toctrees: ['usage/index', 'index'], selecting: usage/index <- usage/restructuredtext/index [toc.multiple_toc_parents]
> ```

These seem to be false-positives in the case of the Sphinx documentation: yes there are multiple entries, but in each of these three examples the ancestor path always resolves to the same value (in other words: `index` + `usage/configuration` == `index/usage` + `configuration`).

So I'd probably agree with downgrading to `info`-level messaging for now.
AA-Turner: > false-positives 

Is there a simple way to avoid these? False positives are pretty frustrating for users.

A
jayaddison: Maybe; if so I think it may require some kind of relative-path-resolution approach (I'm experimenting with it at the moment).
jayaddison: I've a fairly terrible work-in-progress patch:

```diff
diff --git a/sphinx/environment/__init__.py b/sphinx/environment/__init__.py
index 28e53aa7d..bec8fef75 100644
--- a/sphinx/environment/__init__.py
+++ b/sphinx/environment/__init__.py
@@ -789,19 +789,24 @@ def _traverse_toctree(
 
 
 def _check_toc_parents(toctree_includes: dict[str, list[str]]) -> None:
-    toc_parents: dict[str, list[str]] = {}
+    toc_parents: dict[str, set[str]] = {}
     for parent, children in toctree_includes.items():
         for child in children:
-            toc_parents.setdefault(child, []).append(parent)
+            base = path.commonprefix([parent, child])
+            if base and base.endswith('/'):
+                parent = parent.removeprefix(base)
+                child = child.removeprefix(base)
+            toc_parents.setdefault(child, set()).add(f"{parent}/{child}")
 
     for doc, parents in sorted(toc_parents.items()):
         if len(parents) > 1:
+            candidates = sorted(parent.removesuffix(f"/{doc}") for parent in parents)
             logger.info(
                 __(
                     'document is referenced in multiple toctrees: %s, selecting: %s <- %s'
                 ),
-                parents,
-                max(parents),
+                candidates,
+                max(candidates),
                 doc,
                 location=doc,
                 type='toc',
```

However I'm yet to convince myself that it's correct, and it's definitely not clean code.
jayaddison: No; I think it's incorrect due to the absence of the `base` component from the combined `{parent}/{child}` path.
jayaddison: I think this is more like it, but supporting unit test coverage is required:

```diff
diff --git a/sphinx/environment/__init__.py b/sphinx/environment/__init__.py
index 28e53aa7d..9780ef396 100644
--- a/sphinx/environment/__init__.py
+++ b/sphinx/environment/__init__.py
@@ -789,19 +789,27 @@ def _traverse_toctree(
 
 
 def _check_toc_parents(toctree_includes: dict[str, list[str]]) -> None:
-    toc_parents: dict[str, list[str]] = {}
+    toc_parents: dict[str, set[str]] = {}
     for parent, children in toctree_includes.items():
         for child in children:
-            toc_parents.setdefault(child, []).append(parent)
+            # Remove duplicate ancestry if it exists
+            base = path.commonprefix([parent, child])
+            if base and base.endswith('/'):
+                parent = parent.removeprefix(base)
+                child = child.removeprefix(base)
+            # Record de-duplicated toctree routes to each document
+            absolute_path = "/".join(filter(None, [base, parent]))
+            toc_parents.setdefault(child, set()).add(absolute_path)
 
     for doc, parents in sorted(toc_parents.items()):
         if len(parents) > 1:
+            candidates = sorted(parent for parent in parents)
             logger.info(
                 __(
                     'document is referenced in multiple toctrees: %s, selecting: %s <- %s'
                 ),
-                parents,
-                max(parents),
+                candidates,
+                max(candidates),
                 doc,
                 location=doc,
                 type='toc',
```
jayaddison: Possibly also wrong, in particular due to incorrect in-place modification of the `child` variable.
jayaddison: I'll try to write some unit test coverage within the next day or so to help implement more-precise messaging `_check_toc_parents` under various conditions.  If I don't get around to that, then I'd suggest we remove the relevant messages since they can be misleading.
khanxmetu: > These seem to be false-positives in the case of the Sphinx documentation: yes there are multiple entries, but in each of these three examples the ancestor path always resolves to the same value (in other words: `index` + `usage/configuration` == `index/usage` + `configuration`).

@jayaddison I don't quite understand how are the warnings false-positive.  

I don't think it's best to think of ancestor path as a single string representing path to root because the underlying implementation does not have any sense of directories and is merely a list of docnames/docpaths entities as strings each pointing to the next child in chain.  
Also maybe you missed `index` on RHS in your example, I think it should appear on both sides since it's the root. From my understanding the comparison should be as follows:  
```py
['index', 'usage/configuration'] != ['index', 'usage/index', 'usage/configuration']. 
```
A graphical representation similar to what I had in tests:  

```
         index
        /     \
       /       \
      /         \
usage/index      \
       \          \
        \          \
        usage/configuration

```
There exists an ambiguity as to what parent should be chosen by `usage/configuration`. In serial builds or the patch in this pr, lexicographically greatest parent i.e `usage/index` is chosen due to which it is expanded under "Using Sphinx" in the sidebar.  

Had it been that `index` > `usage/index` (for example let's say we had similar structure but for appendix: `index` > `appendix/index`) the sidebar contents wouldn't have been expanded.
jayaddison: Ok, thanks @khanxmetu.  What you say makes sense.  I suppose the particular scenario I'm considering is cases where apparently-ambiguous toctree references all in fact map to a single path.

In other words: `a/b/c` and `a/c` may be less ambiguous in some sense than `a/b/c` and `a/d/c` -- the latter contains two genuinely distinct navigation routes, while the first contains a single route but allows for a jump over the intermediate step.
jayaddison: > Also maybe you missed `index` on RHS in your example, I think it should appear on both sides since it's the root. From my understanding the comparison should be as follows:
> 
> ```python
> ['index', 'usage/configuration'] != ['index', 'usage/index', 'usage/configuration']. 
> ```

It's certainly possible that I made a mistake here; but I think that by implicitly expanding an `index` path for any non-index document (e.g. `usage/configuration` has an implicit parent of `usage/index`) that it's feasible to resolve these.
jayaddison: My apologies: reading the code, it appears that, apart from the root document, docpaths ending in `index` are purely used by convention to provide something like a familiar directory structure -- the term `index` does not have a special meaning.  As a result, I don't think we can (or should) infer their implicit existence.

Given that, I think the existing `info`-level messaging here is fine -- it does not indicate a false-positive, since the ambiguity that @khanxmetu mentions is genuine:

> There exists an ambiguity as to what parent should be chosen by `'usage/configuration'`. In serial builds or the patch in this pr, lexicographically greatest parent i.e `'usage/index'` is chosen due to which "Configuration" section is expanded under "Using Sphinx" in the sidebar.

I'll re-approve the PR to indicate that.
jayaddison: @AA-Turner it's taken me a longwinded route to get there, but I believe that the ambiguity messages about the Sphinx documentation are genuine, in that they make it unclear (in machine terms, if not in human terms) about how the corresponding sidebar toctree should be expanded.

I still feel that it _might_ be possible somehow to devise a more advanced algorithm that can resolve a subset of the multi-toctree reference cases unambiguously, however I don't have 100% confidence that it's feasible in a performant way (mostly I don't feel I have a complete mental model of the problem space yet), nor do I think we should do it during this PR even if it is.

So in short: I'm comfortable with merging the pull request.
timhoffm: Semi-OT: from https://github.com/sphinx-doc/sphinx/issues/6714#issuecomment-2351757525

> The main issue here is the assumption of _get_toctree_ancestors that the toctree is indeed a tree (meaning each node/doc has a unique parent)

Is a non-tree toc arrangement really desirable? Or is it just a structure that happens to be allowed through the way `.. toctree` is designed and implemented?

I mean the name "toctree" already implies a tree. And from a user prespective, I find a clear hierarchial TOC helpful to understand the structure of docs. For my docs, I'd rather place a topic in one place and cross-reference from another place, rather than including in fully in two locations. So, while it's nice to make this deterministic, the ambiguity persists: I go into a subtopic from one location and find myself in a completely different toc path. I would consider that a bug for my documentation. Wouldn't it be better (or at least an option) to warn on multiple inclusions of the same document?
khanxmetu: > Or is it just a structure that happens to be allowed through the way .. toctree is designed and implemented?

Looking at the implementation, it wasn't designed to handle non-tree toc. This PR was supposedly to warn

I mean the name "toctree" already implies a tree. And from a user prespective, I find a clear hierarchial TOC helpful to understand the structure of docs. For my docs, I'd rather place a topic in one place and cross-reference from another place, rather than including it fully in two locations. So, while it's nice to make this deterministic, the ambiguity persists: I go into a subtopic from one location and find myself in a completely different toc path. I would consider that a bug for my documentation. Wouldn't it be better (or at least an option) to warn on multiple inclusions of the same document?
khanxmetu: > Semi-OT: from https://github.com/sphinx-doc/sphinx/issues/6714#issuecomment-2351757525
> 
> 
> 
> > The main issue here is the assumption of _get_toctree_ancestors that the toctree is indeed a tree (meaning each node/doc has a unique parent)
> 
> 
> 
> Is a non-tree toc arrangement really desirable? Or is it just a structure that happens to be allowed through the way `.. toctree` is designed and implemented?
> 
> 
> 
> I mean the name "toctree" already implies a tree. And from a user prespective, I find a clear hierarchial TOC helpful to understand the structure of docs. For my docs, I'd rather place a topic in one place and cross-reference from another place, rather than including it fully in two locations. So, while it's nice to make this deterministic, the ambiguity persists: I go into a subtopic from one location and find myself in a completely different toc path. I would consider that a bug for my documentation. Wouldn't it be better (or at least an option) to warn on multiple inclusions of the same document?

> Semi-OT: from https://github.com/sphinx-doc/sphinx/issues/6714#issuecomment-2351757525
> 
> 
> 
> > The main issue here is the assumption of _get_toctree_ancestors that the toctree is indeed a tree (meaning each node/doc has a unique parent)
> 
> 
> 
> Is a non-tree toc arrangement really desirable? Or is it just a structure that happens to be allowed through the way `.. toctree` is designed and implemented?
> 
> 
> 
> I mean the name "toctree" already implies a tree. And from a user prespective, I find a clear hierarchial TOC helpful to understand the structure of docs. For my docs, I'd rather place a topic in one place and cross-reference from another place, rather than including it fully in two locations. So, while it's nice to make this deterministic, the ambiguity persists: I go into a subtopic from one location and find myself in a completely different toc path. I would consider that a bug for my documentation. Wouldn't it be better (or at least an option) to warn on multiple inclusions of the same document?

The existing implementation doesn't fully account for non-tree tocs and I don't think if there's any good way to resolve multiple parents/references in navigation bar without jumping locations in toc as you mentioned.  

This PR has two purposes in case of multiple parents:
1. Ensure determinism to achieve reproducible parallel builds.
2. Warn the user, though it has been downgraded to info-level output currently due to less severity.  

The workflow you mentioned is ideal for *local toc* (in-document, see the issue with qemu-docs for example). However, in some cases it could be desirable to have a secondary reference in *global toctree* (side-bar navigation) as is the case with Sphinx's documentation where "Configuration" link is also put on the root-level in the sidebar for convenience.  

If this issue seems significant, perhaps, in the future we could have primary(to be used as toc parent) and secondary(not to be used as toc parent) toc entries in the case of conflicts.

Patch:
diff --git a/CHANGES.rst b/CHANGES.rst
index a214b3dec..766b5cc20 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 c463ee561..4f1815b40 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 9d9f077c5..871810bfe 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 000000000..c77c94122
--- /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 000000000..9f65ea6be
--- /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 000000000..931979b62
--- /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 000000000..4db50a3c6
--- /dev/null
+++ b/tests/roots/test-toctree-multiple-parents/conf.py
@@ -0,0 +1,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 000000000..f9887912a
--- /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 000000000..d642aa111
--- /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 000000000..a610eac26
--- /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 6a5ed0b6d..5f396cc48 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 7b9e5a49d..a59de6328 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')