util.inspect.object_description: does not emit reliable ordering for a set nested within another collection

[jayaddison]

Describe the bug

Summary

Differences appear in some sphinx v5.3.0 generated set object descriptions for alembic v1.8.1, as demonstrated by recent results visible on the Reproducible Builds diffoscope dashboard.

Arguably it could make sense for code authors to intentionally write set elements in their code files in a way that does not correspond to their computed sort order -- as a means to communicate with human readers about abstract ideas that aren't relevant to computers at runtime, for example.

However, the current behaviour does result in non-reproducible documentation output.

Details

In particular, the ordering of a class attribute with a value that contains a set-within-a-tuple seems unreliable across differing builds:

https://github.com/sqlalchemy/alembic/blob/a968c9d2832173ee7d5dde50c7573f7b99424c38/alembic/ddl/impl.py#L90

... is emitted variously as ...

<span·class="pre">({'NUMERIC',</span>·<span·class="pre">'DECIMAL'},)</span>

... or ...

<span·class="pre">({'DECIMAL',</span>·<span·class="pre">'NUMERIC'},)</span>

cc @lamby who has been investigating a fix on the reproducible-builds mailing list.

How to Reproduce

It is not yet clear to me exactly what circumstances cause the ordering of elements to vary - and it's OK not to proceed until that's figured out (maybe not a blocker, but it would be nice to have confidence about the cause).

From searching around on previous issues while writing up this bugreport: I wonder if this could be an edge-case for / follow-up to #4834.

Environment Information

Although these build log links are somewhat ephemeral, the system environment details for two builds that produce differing output are visible at:

• https://tests.reproducible-builds.org/debian/rbuild/unstable/amd64/alembic_1.8.1-2.rbuild.log.gz
• https://tests.reproducible-builds.org/debian/logs/unstable/amd64/alembic_1.8.1-2.build2.log.gz

Sphinx extensions

https://github.com/sqlalchemy/alembic/blob/rel_1_8_1/docs/build/conf.py#L36-L42


sphinx.ext.autodoc
sphinx.ext.intersphinx
changelog
sphinx_paramlinks
sphinx_copybutton

Additional context

No response

[lamby]

Here's what I wrote on the mailing list that I think is important to surface here: This seems to be because Sphinx is essentially running repr(…) on a set() data structure nested within a tuple object, and it isn't sorting the contents of that nested set() when rendering it.

This change to Sphinx makes alembic reproducible:

diff --git a/sphinx/util/inspect.py b/sphinx/util/inspect.py
index 47776d65b3..1a083b8a38 100644
--- a/sphinx/util/inspect.py
+++ b/sphinx/util/inspect.py
@@ -386,6 +386,13 @@ def object_description(object: Any) -> str:
                                                  for x in sorted_values)
     elif isinstance(object, enum.Enum):
         return f"{object.__class__.__name__}.{object.name}"
+    elif isinstance(object, tuple):
+        return "(%s%s)" % (
+            ", ".join(object_description(x) for x in object),
+            "," if len(object) == 1 else ""
+        )
+    elif isinstance(object, list):  # is this even needed?
+        return "[%s]" % ", ".join(object_description(x) for x in object)
 
     try:
         s = repr(object)
diff --git a/tests/test_util_inspect.py b/tests/test_util_inspect.py
index bc1b25674a..d670886bcf 100644
--- a/tests/test_util_inspect.py
+++ b/tests/test_util_inspect.py
@@ -533,6 +533,16 @@ def test_frozenset_sorting_fallback():
     assert description in ("frozenset({1, None})", "frozenset({None, 1})")
 
 
+def test_nested_tuple_sorting():
+    tuple_ = ({"c", "b", "a"},)  # nb. trailing comma
+    description = inspect.object_description(tuple_)
+    assert description == "({'a', 'b', 'c'},)"
+
+    tuple_ = ({"c", "b", "a"}, {"f", "e", "d"})
+    description = inspect.object_description(tuple_)
+    assert description == "({'a', 'b', 'c'}, {'d', 'e', 'f'})"
+
+
 def test_dict_customtype():
     class CustomType:
         def __init__(self, value):

Link to WIP patch

Why it hasn't been a problem before is rather curious though. I mean, surely this isn't such a rare case? It may be just that it hasn't come up, but it may be because this value ultimately comes from a Python typing annotation. Yet at that point in the code, there doesn't seem to be anything special whatsoever about this tuple & set: it's really just a regular tuple and set.

[paravoid]

Coincidentally, I'm trying to debug a different but very similar issue, a reproducibility issue with structlog 21.0.3. Thanks for this issue, it really helped me understand what's going on there!

The two issues are definitely different, but related:

structlog.processors has (simplified for clarity):

class CallsiteParameter(enum.Enum):
    PATHNAME = "pathname"
    FILENAME = "filename"
...

class CallsiteParameterAdder:
    _all_parameters: ClassVar[set[CallsiteParameter]] = set(CallsiteParameter)
...
    def __init__(
        self,
        parameters: Collection[CallsiteParameter] = _all_parameters,
        additional_ignores: list[str] | None = None,
    ) -> None:
...

The description of the parameters argument is not-deterministic

Sphinx's object_description seems to be handling sets (and, separately, enums) but in this case it's trying to do sorted(object) but here object == set(CallsiteParameter), so it ends up failing with TypeError: '<' not supported between instances of 'CallsiteParameter' and 'CallsiteParameter'.

So a fix would be something along the lines of what @lamby did above with recursion: on sets, attempt to do something like sorted({object_description(m) for m in object}) instead. I wonder if this should be generalized somehow, though?

[jayaddison]

@lamby your patch looks good to me (I applied the unit change locally first, to confirm that the tests begin failing, and then applied the fix to verify that it resolves the failures)

[paravoid]

@lamby your patch looks good to me (I applied the unit change locally first, to confirm that the tests begin failing, and then applied the fix to verify that it resolves the failures)

FWIW @lamby's patch will not fix the issue I described above. If you think that it is sufficiently different to belong in a different issue, let me know. My reasoning was that it was similar enough to discuss in tandem, but I'm happy to adapt!

[jayaddison]

it ends up failing with TypeError: '<' not supported between instances of 'CallsiteParameter' and 'CallsiteParameter'

@paravoid is there a way to reduce that case further to that it becomes suitable for inclusion in tests/test_util_inspect.py?

If we can agree that it's a general aspect of the same problem then we could resolve it at the same time - otherwise yep, a separate issue could be a good idea.

[paravoid]

Here's a test case, alongside a proposed fix that a) passes the entire suite, and b) creates reproducible documentation for structlog. Note that there are existing unit tests that already assume there is variance in the output, so I've modified these as well to indicate that no variance is acceptable.

diff --git a/tests/test_util_inspect.py b/tests/test_util_inspect.py
index cc67e37b3..ffc1bcd83 100644
--- a/tests/test_util_inspect.py
+++ b/tests/test_util_inspect.py
@@ -503,10 +503,20 @@ def test_set_sorting():
     assert description == "{'a', 'b', 'c', 'd', 'e', 'f', 'g'}"
 
 
+def test_set_sorting_enum():
+    class MyEnum(enum.Enum):
+        a = 1
+        b = 2
+        c = 3
+
+    set_ = set(MyEnum)
+    description = inspect.object_description(set_)
+    assert description == "{MyEnum.a, MyEnum.b, MyEnum.c}"
+
 def test_set_sorting_fallback():
     set_ = {None, 1}
     description = inspect.object_description(set_)
-    assert description in ("{1, None}", "{None, 1}")
+    assert description == "{1, None}"
 
 
 def test_frozenset_sorting():
@@ -518,7 +528,7 @@ def test_frozenset_sorting():
 def test_frozenset_sorting_fallback():
     frozenset_ = frozenset((None, 1))
     description = inspect.object_description(frozenset_)
-    assert description in ("frozenset({1, None})", "frozenset({None, 1})")
+    assert description == "frozenset({1, None})"
 
 
 def test_dict_customtype():
diff --git a/sphinx/util/inspect.py b/sphinx/util/inspect.py
index 8e98ca447..dad47aff8 100644
--- a/sphinx/util/inspect.py
+++ b/sphinx/util/inspect.py
@@ -370,20 +370,21 @@ def object_description(object: Any) -> str:
                      for key in sorted_keys)
             return "{%s}" % ", ".join(items)
     elif isinstance(object, set):
+        set_descr = (object_description(x) for x in object)
         try:
-            sorted_values = sorted(object)
+            sorted_set_descr = sorted(set_descr)
         except TypeError:
             pass  # Cannot sort set values, fall back to generic repr
         else:
-            return "{%s}" % ", ".join(object_description(x) for x in sorted_values)
+            return "{%s}" % ", ".join(sorted_set_descr)
     elif isinstance(object, frozenset):
+        frozenset_descr = (object_description(x) for x in object)
         try:
-            sorted_values = sorted(object)
+            sorted_frozenset_descr = sorted(frozenset_descr)
         except TypeError:
             pass  # Cannot sort frozenset values, fall back to generic repr
         else:
-            return "frozenset({%s})" % ", ".join(object_description(x)
-                                                 for x in sorted_values)
+            return "frozenset({%s})" % ", ".join(sorted_frozenset_descr)
     elif isinstance(object, enum.Enum):
         return f"{object.__class__.__name__}.{object.name}"
 

[lamby]

(Still waking up here, but just to underline that my "WIP patch" wasn't meant to be used — it was more of a kind of code-based demonstration. 👍)

[jayaddison]

@paravoid a nitpick: the existing code seems to prefer re-using variable names within each object description case.

(in other words: perhaps rename both set_descr and frozenset_descr to described_values?)

That may also help to clarify that the proposed change sorts the (string) descriptions and not the Python values of the collections (I think that's true - is it? and even if it is, is it a good idea?).

[jayaddison]

That may also help to clarify that the proposed change sorts the (string) descriptions and not the Python values of the collections (I think that's true - is it? and even if it is, is it a good idea?).

+        set_descr = (object_description(x) for x in object)
         try:
-            sorted_values = sorted(object)
+            sorted_set_descr = sorted(set_descr)
         except TypeError:
             pass  # Cannot sort set values, fall back to generic repr

set_descr would contain str elements and so always be sortable - that'd be a change-in-behaviour from the existing logic where a TypeError is raised (and handled with fallback) for non-sortable collections.

That can happen when a set contains a mixture of elements that don't support order comparison (an int and a str value, for example).

[jayaddison]

Refreshing the context here:

Quoting @lamby re: his patch:

This seems to be because Sphinx is essentially running repr(…) on a set() data structure nested within a tuple object, and it isn't sorting the contents of that nested set() when rendering it.

Ok, yep: that explains the use of recursive calls in the patch, because without them, the relevant collection datatypes would use simple, non-order-coercing representations.

Quoting myself again re: @paravoid's patch:

That may also help to clarify that the proposed change sorts the (string) descriptions and not the Python values of the collections (I think that's true - is it? and even if it is, is it a good idea?).

Some caution may be required here:

• We should continue to attempt to sort the elements as-received if possible, because if we can do that, then that is the preferred (and deterministic) presentation order.

• If it isn't possible to sort the elements -- like the {1, None} example in the existing test coverage -- then the solution is trickier.

  • In this case, I think as a fallback we could describe (format-as-string) each element in the collection and sort those results (to achieve determinism).
  • The set datatype should not have any recursion/circular-dependency edge-cases, because sets are not hashable and so a set cannot contain itself or another set.

[jayaddison]

I'm going to attempt to build a third patch that combines the two offered so far.

However: it will only call object_description recursively if the initial attempt to sort the collection fails.

[AA-Turner]

• The set datatype should not have any recursion/circular-dependency edge-cases, because sets are not hashable and so a set cannot contain itself or another set.

frozensets are recursivley hashable, if this is relevant. I'll have time to review this and your updated localisation commits towards the end of the month, thank you!

A

[jayaddison]

@paravoid could you confirm whether the changes in #11312 resolve the problem you encountered when generating documentation for structlog? (the changes build upon, but also diverge from, your patch)

[jayaddison]

frozensets are recursivley hashable, if this is relevant.

@AA-Turner thank you! I didn't know that. I'll have a think about it.

[paravoid]

@paravoid could you confirm whether the changes in #11312 resolve the problem you encountered when generating documentation for structlog? (the changes build upon, but also diverge from, your patch)

I confirm the changes resolve the problem I encountered. For what it's worth, the reproduction case is:

$ git clone -b 22.3.0 https://github.com/hynek/structlog/
$ pip install -e '.[dev]'
$ make -C docs html BUILDDIR=build1; make -C docs html BUILDDIR=build2; make -C docs html BUILDDIR=build3;
$ diff -Nurp docs/build1 docs/build2; diff -Nurp docs/build2 docs/build3  # no text differences should occur

Thank you so much for taking care of this!

[jayaddison]

@lamby any chance you could also take a look at the potential fix for this in #11312?

[jayaddison]

frozensets are recursivley hashable, if this is relevant.

@AA-Turner thank you! I didn't know that. I'll have a think about it.

Initially I thought that that might mean that frozenset objects can be used to create recursive datastructures (dict objects certainly can). However, since frozenset is immutable -- and consumes the contents of its constructor argument as an iterator, removing any object references -- I don't think that that should be possible.

However: Python does seem to accept recursive datastructures as the value of type hints; so perhaps that edge case is also worth handling in object_description. Elsewhere, for example, pprint.saferepr does protect against stack exhaustion by catching recursive references.

[jayaddison]

However, since frozenset is immutable -- and consumes the contents of its constructor argument as an iterator, removing any object references -- I don't think that that should be possible.

I didn't phrase that very precisely. I'll try to find counter-examples to see whether it's possible to, for example, use multi-level nested structures to create a frozenset containing recursive references.

[jayaddison]

However, since frozenset is immutable -- and consumes the contents of its constructor argument as an iterator, removing any object references -- I don't think that that should be possible.

I didn't phrase that very precisely. I'll try to find counter-examples to see whether it's possible to, for example, use multi-level nested structures to create a frozenset containing recursive references.

Ok, I think a better attempt to prove that frozensets cannot, by themselves, result in recursive datastructures would be:

• A frozenset can only contain elements that were generated at-or-before the time that the frozenset itself was constructed
• A frozenset cannot have any elements added to it after construction

Therefore although one frozenset could contain zero or more (older) frozenset references -- which in turn could each contain zero or more older frozensets, and so on -- it shouldn't be possible to modify any of them, and so it shouldn't be possible to create a circular reference, since that would require at least one link that navigates forward through object-creation-time.

(note: this doesn't change the fact that dict datatypes can break that recursion-safety property)

[picnixz]

However, since frozenset is mutable

Aren't frozensets immutable objects by essence ? also, hashable objects must be immutable in Python:

An object is hashable if [1] it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). [2] Hashable objects which compare equal must have the same hash value.

(You technically can have a mutable hashable object but you need to specify the hash value yourself and ensure the above conditions. I don't see a use-case where you have mutability and hashability except for singletons.)

By the way you could take a look at reprlib.recursive_repr to see how they handle recursive calls of repr on recursive structures.

[jayaddison]

However, since frozenset is mutable

Aren't frozensets immutable objects by essence ? also, hashable objects must be immutable in Python:

Sorry, yep - immutable is exactly what I meant to write (holds a static, unmodifiable value after initial assignment).

An object is hashable if [1] it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). [2] Hashable objects which compare equal must have the same hash value.

(You technically can have a mutable hashable object but you need to specify the hash value yourself and ensure the above conditions. I don't see a use-case where you have mutability and hashability.)

By the way you could take a look at reprlib.recursive_repr to see how they handle recursive calls of repr on recursive structures.

Thank you. I'll read about that soon.

So far in #11312, I've begun accumulating a unique collection of input object id(...) values during the object_description call -- and returning a recursive-structure-placeholder when a repeat object is encountered.

[lamby]

@paravoid wrote:

FWIW @lamby's patch will not fix the issue I described above. […]

Just to underline that my patch was never seriously intended to be committed; note the commit message and, of course, the lack of real testing. :)

@jayaddison wrote:

@lamby any chance you could also take a look at the potential fix for this in #11312?

I've just gone back to the Debian package that precipitated my original bug report and applied the patch to object_description -- it makes this package reproducible. 👍

[jayaddison]

@lamby:

Just to underline that my patch was never seriously intended to be committed; note the commit message and, of course, the lack of real testing. :)

Test results aside: are you OK with the way it has been included in #11312?

(if not, please let me know)

[lamby]

By "it has been included" do you mean to ask whether I happy with way the fix was implemented...? If so, it LGTM. I might just add a brief, one-liner comment why we are tracking seen, but otherwise looking forward to seeing this land.

[jayaddison]

Thanks for confirming, and good idea - I've added that comment.

Basically I wanted to check where the intent of your message "my patch was never seriously intended to be committed" sits, within the bounds of "this was some exploratory work that is OK to build upon" and "this was some untested code that I'd be apprehensive to see included in a codebase".

On second thoughts, work-in-progress probably indicates the former, but I wasn't sure.

[lamby]

Ah, very much "this was some exploratory work that is OK to build upon". :) I'll use that phrasing here and elsewhere in the future - I often find it useful to make a disgustingly hacky 'fix' as it demonstrates beyond doubt that a particular codepath is being executed and that the problem at least exists in a certain topic area within the code.

Cheers!