A Determinism Check Has to Leave the Process

Code: Megapixel99/nondet

The obvious way to check whether a Python function is deterministic is to call it twice and compare. I wrote that check, and it is blind to the commonest source of nondeterminism in the language. String hashing is randomised per interpreter, so set and dict iteration order is stable within a process and different in every new one. A function returning list({'alpha', 'beta', 'gamma'}) answers identically twenty times out of twenty inside one interpreter. In the transcript the README records, three fresh python3 -c invocations gave three different orderings (six orderings are possible, so a rerun sometimes repeats one, and the arithmetic on that is below).

nondet is the check rebuilt around that fact: point it at a tree or a FILE::NAME, and it re-runs each function against a fixed input ladder in fresh worker processes. The ladder is a deterministic list of probe inputs (a rung is one of them), covering functions of one to three positional arguments; variadics, keyword-only signatures and zero-arity functions are refused with a reason rather than guessed at. PYTHONHASHSEED is cleared for the workers, so a seed fixed in your environment cannot blind the check.

pip install nondet
nondet src/                     # every module-level function under a tree
nondet src/util.py::normalise   # one function

A finding prints the function, the input, and the two answers:

  nondeterministic  src/features.py::resolve_features
         [["alpha","beta","gamma","delta","epsilon"]] -> V:set["epsilon","delta",...]  then  V:set["beta","gamma",...]

The claim worth checking is the control committed as test_in_process_repetition_would_have_missed_it. It asserts that the in-process check finds no variation over 20 calls on a hash-order function, and that nondet finds it anyway. If in-process repetition ever catches it, fresh processes are expensive theatre and the test says so in those words.

The verdicts are deliberately asymmetric. nondeterministic comes with a witness, an input and the two different answers it produced, and a witness is a fact. deterministic means no run disagreed across the ladder, which is the absence of a counterexample rather than proof of one's absence. The output says so instead of letting you read it as a guarantee. The package's own numbers put a magnitude on that gap. A hash-order defect in a three-key dict admits 3! = 6 orderings, so three fresh processes miss it about 2.8% of the time. An eight-key dict admits 40,320 and is missed about once in a billion. The ladder carries both shapes, and the wide one does the detecting.

Scoring it needed labels written down separately from the function names, so the checker is not graded against its own naming convention. On the 19-function fixture set, 9 of 9 nondeterministic functions are caught and 0 of 10 deterministic ones are falsely flagged. One deterministic function comes back as a refusal instead, deliberately. Every rung of its ladder raised, and a ladder that only ever reached a function's type errors has not measured its behaviour. The fixture pairs are the point of the set. dedup_unsorted and dedup_sorted are one sorted() apart. seeded uses random.Random(42): deterministic, and exactly the false positive a static gate that greps for random produces. duration_arithmetic imports time and never reads the clock.

Pointed at a real 283-function tree, it probed 127 with the safety gate on and found 2 genuinely nondeterministic functions. One returns a set, and one's value moves between runs. (That census predates a newer rule that files a function whose every rung raised as a refusal, so a run today probes slightly fewer; the README says so under the table, and neither finding moves.) The gate exists because of the sharpest thing I learned building this: the probe executes the code it is asked about. An early run reported a function raising TypeError once and FileExistsError the next time. That is a true finding, and it is also proof that the probe had just created a file on the disk. The line is drawn at writing and communicating rather than at impurity, since time, random, uuid and set ordering are read-only and are exactly the target. open(), subprocess and sockets are refused. The gate costs recall and the census (the printed count of what was refused and why) says so: --unsafe lifts probing to 169 functions and the findings to 4. One of the two findings it hides (a function returning a path under a fresh temp directory) is a true positive the gated run can no longer see.

The environment is varied between runs too, timezone and locale, an idea taken directly from reprotest. The fixture that justifies it is epoch_year: fromtimestamp(0).year is 1970 in UTC and 1969 west of it, does not move with the clock, and is caught only because the timezone varies.

The part of the README I would keep if I could keep one paragraph is about the tool's own bugs, because both wore the costume of findings about the code under test. Loading a package module by file path broke relative imports and refused 56 of 68 functions; sending the result vector over stdout meant any function that printed corrupted it. Both were caught by pointing the tool at a real codebase and disbelieving the refusal rate. One fix took reach from 2 of 68 functions to 60 of 68 while breaking correctness on all 17 fixtures of the time. A tool watched only by how many functions it probed would have scored that as an improvement.

Prior art was swept on both registries before publishing. On npm, keywords:purity returns 26 packages and every one is static analysis. The real neighbours are reprotest at build granularity, Groce and Holmes (QRS 2020) at test granularity, and the pytest-flakefinder family, which reruns tests. Nothing found points at an arbitrary function, walks a ladder in fresh processes, and hands back the input that distinguished two runs. That is the granularity this fills.