schedule() is unreliable

Usage by agent

Timeline

1. planner iteration 1 ✓Finished 3 calls · 9,562 tokens · $0.0014 · 13.2s

   Loading…

2. coder iteration 1 ✓Finished 5 calls · 29.8K tokens · $0.0023 · 14.7s

   Loading…

3. tester iteration 1 ✓Finished 3 calls · 22.1K tokens · $0.0019 · 12.1s

   Loading…

4. verify iteration 1 ✓Passed 0.5s

   ................                                                         [100%]
   16 passed in 0.03s
   

Final diff

diff --git a/scheduler.py b/scheduler.py
index d2d5b46..0cf1288 100644
--- a/scheduler.py
+++ b/scheduler.py
@@ -1,15 +1,40 @@
+import heapq
+
 from graph import dependents
 
 
+class CycleError(ValueError):
+    """Raised when tasks contain a dependency cycle."""
+
+
+class UnknownTaskError(ValueError):
+    """Raised when a task depends on a name that is not a task."""
+
+
 def schedule(tasks: dict[str, list[str]]) -> list[str]:
+    for name, deps in tasks.items():
+        for dep in deps:
+            if dep not in tasks:
+                raise UnknownTaskError(
+                    f"unknown dependency {dep!r} required by {name!r}"
+                )
+
+    children = dependents(tasks)
     remaining = {name: len(deps) for name, deps in tasks.items()}
     ready = [name for name, count in remaining.items() if count == 0]
+    heapq.heapify(ready)
     order = []
     while ready:
-        name = ready.pop()
+        name = heapq.heappop(ready)
         order.append(name)
-        for child in dependents(tasks)[name]:
+        for child in children[name]:
             remaining[child] -= 1
             if remaining[child] == 0:
-                ready.append(child)
+                heapq.heappush(ready, child)
+
+    if len(order) < len(tasks):
+        done = set(order)
+        stuck = sorted(name for name in tasks if name not in done)
+        names = ", ".join(repr(name) for name in stuck)
+        raise CycleError(f"dependency cycle among tasks: {names}")
     return order
diff --git a/test_scheduler.py b/test_scheduler.py
index 83bc850..9931acf 100644
--- a/test_scheduler.py
+++ b/test_scheduler.py
@@ -1,5 +1,89 @@
-from scheduler import schedule
+import pytest
+
+from scheduler import CycleError, UnknownTaskError, schedule
 
 
 def test_chain():
     assert schedule({"a": [], "b": ["a"], "c": ["b"]}) == ["a", "b", "c"]
+
+
+def test_empty():
+    assert schedule({}) == []
+
+
+def test_cycle_raises_with_names():
+    with pytest.raises(CycleError) as exc:
+        schedule({"a": ["b"], "b": ["a"]})
+    assert "'a'" in str(exc.value) and "'b'" in str(exc.value)
+
+
+def test_self_cycle_raises():
+    with pytest.raises(CycleError) as exc:
+        schedule({"a": ["a"]})
+    assert "'a'" in str(exc.value)
+
+
+def test_partial_cycle_names_only_stuck_tasks():
+    with pytest.raises(CycleError) as exc:
+        schedule({"x": [], "a": ["b"], "b": ["a"]})
+    assert "'a'" in str(exc.value) and "'b'" in str(exc.value)
+    assert "'x'" not in str(exc.value)
+
+
+def test_unknown_dependency_raises():
+    with pytest.raises(UnknownTaskError) as exc:
+        schedule({"a": ["zzz"]})
+    assert "zzz" in str(exc.value)
+
+
+def test_error_types_are_value_errors():
+    assert issubclass(CycleError, ValueError)
+    assert issubclass(UnknownTaskError, ValueError)
+
+
+def test_deterministic_among_roots():
+    assert schedule({"c": [], "a": [], "b": []}) == ["a", "b", "c"]
+
+
+def test_alphabetical_among_ready_tasks():
+    assert schedule({"b": [], "a": ["b"], "c": []}) == ["b", "a", "c"]
+
+
+def test_unknown_dependency_message_names_dependent():
+    with pytest.raises(UnknownTaskError) as exc:
+        schedule({"a": [], "b": ["x"]})
+    assert "'x'" in str(exc.value) and "'b'" in str(exc.value)
+
+
+def test_unknown_dependency_reported_before_cycle():
+    # Validation must run first, so an unknown dep inside a cycle
+    # is reported as unknown, not misreported as a cycle.
+    with pytest.raises(UnknownTaskError):
+        schedule({"a": ["b"], "b": ["a", "zzz"]})
+
+
+def test_unknown_dependency_is_not_key_error():
+    with pytest.raises(UnknownTaskError):
+        schedule({"a": ["zzz"]})
+    assert not issubclass(UnknownTaskError, KeyError)
+
+
+def test_duplicate_dependencies_are_scheduled():
+    assert schedule({"a": [], "b": ["a", "a"]}) == ["a", "b"]
+
+
+def test_newly_ready_smaller_task_runs_next():
+    # 'a' becomes ready after 'm' runs and must go before 'z'.
+    assert schedule({"m": [], "z": [], "a": ["m"]}) == ["m", "a", "z"]
+
+
+def test_downstream_of_cycle_is_named_as_stuck():
+    with pytest.raises(CycleError) as exc:
+        schedule({"a": ["b"], "b": ["a"], "c": ["a"]})
+    msg = str(exc.value)
+    assert "'a'" in msg and "'b'" in msg and "'c'" in msg
+
+
+def test_acceptance_examples_exact():
+    assert schedule({"b": [], "a": ["b"], "c": []}) == ["b", "a", "c"]
+    assert schedule({"a": [], "b": ["a"], "c": ["b"]}) == ["a", "b", "c"]