bpo-37596: Make `set` and `frozenset` marshalling deterministic (GH-27926)

1 files changed, 32 insertions, 0 deletions

diff --git a/Python/marshal.c b/Python/marshal.c
index 1260704..b69c4d0 100644
--- a/Python/marshal.c
+++ b/Python/marshal.c
@@ -503,9 +503,41 @@ w_complex_object(PyObject *v, char flag, WFILE *p)
             W_TYPE(TYPE_SET, p);
         n = PySet_GET_SIZE(v);
         W_SIZE(n, p);
+        // bpo-37596: To support reproducible builds, sets and frozensets need
+        // to have their elements serialized in a consistent order (even when
+        // they have been scrambled by hash randomization). To ensure this, we
+        // use an order equivalent to sorted(v, key=marshal.dumps):
+        PyObject *pairs = PyList_New(0);
+        if (pairs == NULL) {
+            p->error = WFERR_NOMEMORY;
+            return;
+        }
         while (_PySet_NextEntry(v, &pos, &value, &hash)) {
+            PyObject *dump = PyMarshal_WriteObjectToString(value, p->version);
+            if (dump == NULL) {
+                p->error = WFERR_UNMARSHALLABLE;
+                goto anyset_done;
+            }
+            PyObject *pair = PyTuple_Pack(2, dump, value);
+            Py_DECREF(dump);
+            if (pair == NULL || PyList_Append(pairs, pair)) {
+                p->error = WFERR_NOMEMORY;
+                Py_XDECREF(pair);
+                goto anyset_done;
+            }
+            Py_DECREF(pair);
+        }
+        if (PyList_Sort(pairs)) {
+            p->error = WFERR_NOMEMORY;
+            goto anyset_done;
+        }
+        for (Py_ssize_t i = 0; i < n; i++) {
+            PyObject *pair = PyList_GET_ITEM(pairs, i);
+            value = PyTuple_GET_ITEM(pair, 1);
             w_object(value, p);
         }
+    anyset_done:
+        Py_DECREF(pairs);
     }
     else if (PyCode_Check(v)) {
         PyCodeObject *co = (PyCodeObject *)v;