spark
cdf6828fe0
topo_sort read graph.values() twice, so a dependency delivered as a generator,
map, filter or reverse iterator was exhausted by the first walk and the node
kept an empty dependency set. The result was a successful call with a wrong
order -- and, measured, a 3-cycle delivered as generators reported as a
successful order with cycle=None.
Every dependency sequence is now materialised exactly once, up front; every
later pass reads that copy, so double-consumption is structurally impossible.
Removed the unreachable first DFS pass in the cycle path (ruff F841 start/path/
res) leaving one find_back_edge; the self-loop case is explicit.
test_toposort.py resolved the module from /root/.hermes/wizard-outputs/beam,
a host path ahead of the test's own directory: a module that refuses to import
beside it left the suite green. It now resolves from Path(__file__).parent and
asserts the imported file's identity. 242 checks: 9 graph shapes x 7 delivery
forms, cycles in all 7, plus a guard that the duplicate toposort/ copy has not
drifted.
Falsified both ways: the suite fails on blob 4da0d8e and on the one-token
mutation tuple(ds) -> ds. CHECK rc 0 (85 unittests OK), verify.py 8/8.
172 lines
6.3 KiB
Python
172 lines
6.3 KiB
Python
"""Tests for toposort.topo_sort.
|
|
|
|
Runs two ways, both from this directory only:
|
|
python3 test_toposort.py
|
|
python3 -m unittest discover -p 'test_*.py'
|
|
|
|
Assertions execute at import (the convention this file already used), so a
|
|
failure surfaces under `unittest discover` as an import error rather than a
|
|
silent pass.
|
|
|
|
Q61 / 2026-10-24: the module is resolved from THIS file's directory and from
|
|
nowhere else. The previous `sys.path.insert(0, '/root/.hermes/wizard-outputs/beam')`
|
|
measured a host copy rather than the committed bytes, so the gate could pass
|
|
while the repository's blob was broken. `MODULE_PATH` is asserted below.
|
|
"""
|
|
import pathlib
|
|
import sys
|
|
|
|
HERE = pathlib.Path(__file__).resolve().parent
|
|
sys.path.insert(0, str(HERE))
|
|
|
|
import toposort as toposort_module
|
|
from toposort import topo_sort
|
|
|
|
# The module under test must be the committed file next to this test.
|
|
MODULE_PATH = pathlib.Path(toposort_module.__file__).resolve()
|
|
assert MODULE_PATH == (HERE / "toposort.py"), (MODULE_PATH, HERE)
|
|
|
|
_checks = 0
|
|
|
|
|
|
def eq(got, expected, what):
|
|
global _checks
|
|
_checks += 1
|
|
assert got == expected, f"{what}: got {got!r}, expected {expected!r}"
|
|
|
|
|
|
def ok(cond, what):
|
|
global _checks
|
|
_checks += 1
|
|
assert cond, what
|
|
|
|
|
|
def order_of(spec, take):
|
|
"""Build a graph from `spec`, passing every dependency sequence through `take`."""
|
|
return {n: (() if ds is None else take(ds)) for n, ds in spec.items()}
|
|
|
|
|
|
def check_valid(result, spec, what):
|
|
"""result must be a valid topological order of `spec` (deps before dependents)."""
|
|
global _checks
|
|
_checks += 1
|
|
assert result.cycle is None, f"{what}: unexpected cycle {result.cycle!r}"
|
|
order = result.sorted
|
|
assert order is not None, f"{what}: sorted is None with no cycle"
|
|
nodes = set(spec)
|
|
for ds in spec.values():
|
|
nodes.update(ds or ())
|
|
assert sorted(order) == sorted(nodes), f"{what}: not a permutation: {order!r}"
|
|
pos = {n: i for i, n in enumerate(order)}
|
|
for node, ds in spec.items():
|
|
for dep in (ds or ()):
|
|
assert pos[dep] < pos[node], f"{what}: {dep!r} after {node!r} in {order!r}"
|
|
|
|
|
|
def check_cycle(result, spec, what):
|
|
"""result.cycle must be a real cycle: consecutive edges exist, last -> first."""
|
|
global _checks
|
|
_checks += 1
|
|
assert result.sorted is None, f"{what}: expected no order, got {result.sorted!r}"
|
|
cyc = result.cycle
|
|
assert cyc, f"{what}: empty cycle"
|
|
for i, u in enumerate(cyc):
|
|
v = cyc[(i + 1) % len(cyc)]
|
|
assert v in (spec.get(u) or ()), f"{what}: no edge {u!r}->{v!r} in {cyc!r}"
|
|
|
|
|
|
# ---------------------------------------------------------------- baseline cases
|
|
r = topo_sort({'a': ['b'], 'b': []})
|
|
eq(r.sorted, ['b', 'a'], "simple")
|
|
eq(r.cycle, None, "simple cycle")
|
|
|
|
eq(topo_sort({'a': [], 'b': []}).sorted, ['a', 'b'], "disconnected")
|
|
eq(topo_sort({}).sorted, [], "empty")
|
|
|
|
DIAMOND = {'a': ['b', 'c'], 'b': ['d'], 'c': ['d'], 'd': []}
|
|
d = topo_sort(DIAMOND)
|
|
eq(d.cycle, None, "diamond cycle")
|
|
check_valid(d, DIAMOND, "diamond")
|
|
|
|
two = topo_sort({'a': ['b'], 'b': ['a']})
|
|
eq(two.sorted, None, "2-cycle sorted")
|
|
check_cycle(two, {'a': ['b'], 'b': ['a']}, "2-cycle")
|
|
|
|
eq(topo_sort({'a': ['a']}).cycle, ['a'], "self loop")
|
|
eq(topo_sort({'a': ['b']}).sorted, ['b', 'a'], "successor only")
|
|
|
|
# ------------------------------------------------- Q61(a): iterator dependencies
|
|
# Specs are written with plain tuples; `take` decides how each dependency
|
|
# sequence is delivered. Every delivery form must produce the SAME order, and
|
|
# that order must be valid -- not merely equal to a wrong reference.
|
|
SPECS = {
|
|
"single": {'a': ('b',), 'b': ()},
|
|
"chain3": {'c': ('b',), 'b': ('d',), 'd': ()},
|
|
"chain6": {'f': ('e',), 'e': ('d',), 'd': ('c',), 'c': ('b',), 'b': ('a',), 'a': ()},
|
|
"diamond": DIAMOND,
|
|
"fork": {'root': ('l', 'r'), 'l': (), 'r': ()},
|
|
"join": {'a': ('x',), 'b': ('x',), 'c': ('a', 'b'), 'x': ()},
|
|
"multi": {'a': ('b',), 'b': (), 'c': ('d',), 'd': (), 'e': ()},
|
|
"missingdep": {'a': ('z',)},
|
|
"empty": {},
|
|
}
|
|
|
|
TAKERS = {
|
|
"tuple": tuple,
|
|
"list": list,
|
|
"generator": lambda ds: (d for d in ds),
|
|
"map_object": lambda ds: map(str, ds),
|
|
"filter": lambda ds: filter(lambda d: True, ds),
|
|
"reversed_iter": lambda ds: reversed(list(ds)),
|
|
"set": set,
|
|
}
|
|
|
|
for name, spec in SPECS.items():
|
|
reference = topo_sort(order_of(spec, tuple))
|
|
check_valid(reference, spec, f"{name}/tuple")
|
|
for tname, take in TAKERS.items():
|
|
result = topo_sort(order_of(spec, take))
|
|
eq(result.cycle, None, f"{name}/{tname} cycle")
|
|
eq(result.sorted, reference.sorted, f"{name}/{tname} order")
|
|
check_valid(result, spec, f"{name}/{tname}")
|
|
|
|
# The exact repro from Q61: a two-node graph where the generator was exhausted
|
|
# by the first pass and the result was a silent, wrong 'success'.
|
|
gen = topo_sort({'a': iter(['b']), 'b': []})
|
|
eq(gen.sorted, ['b', 'a'], "Q61 repro: generator dependency")
|
|
|
|
# Cycles must survive iterator delivery too -- and still be reported as cycles.
|
|
CYCLES = {
|
|
"self": {'a': ('a',)},
|
|
"two": {'a': ('b',), 'b': ('a',)},
|
|
"three": {'a': ('b',), 'b': ('c',), 'c': ('a',)},
|
|
"tail": {'head': ('a',), 'a': ('b',), 'b': ('a',)},
|
|
}
|
|
for name, spec in CYCLES.items():
|
|
for tname, take in TAKERS.items():
|
|
check_cycle(topo_sort(order_of(spec, take)), spec, f"{name}/{tname}")
|
|
|
|
eq(topo_sort({'a': iter(['a'])}).cycle, ['a'], "self loop as iterator")
|
|
|
|
# ------------------------------------------------------- determinism / stability
|
|
for _ in range(3):
|
|
eq(topo_sort(order_of(SPECS["join"], list)).sorted,
|
|
topo_sort(order_of(SPECS["join"], tuple)).sorted, "repeat determinism")
|
|
|
|
# ------------------------------------------- Q61(b) sibling copy drift guard
|
|
# wizard-work/beam carries a second, historically byte-identical copy at
|
|
# toposort/toposort.py. Two copies of a fixed bug is how it comes back; assert
|
|
# they agree rather than trusting that they do.
|
|
SIBLING = HERE / "toposort" / "toposort.py"
|
|
if SIBLING.exists():
|
|
ok(SIBLING.read_bytes() == (HERE / "toposort.py").read_bytes(),
|
|
f"sibling copy differs from toposort.py: {SIBLING}")
|
|
|
|
|
|
def test_all():
|
|
"""Kept so pytest/unittest see a callable; module-level asserts already ran."""
|
|
return _checks
|
|
|
|
|
|
print(f"ALL PASS ({_checks} checks)")
|