Procedural dependencies: order, cycles and stop gates

Last updated: 7 Oct 20265 min read

tutorial

Represent runbook prerequisites as a directed graph, detect impossible ordering and stop when a required condition is unknown.

Order is not always the written list

A numbered runbook can still say “verify the replica before step three,” or put a shared prerequisite in a warning box. Build step IDs and dependency edges from explicit text. Do not infer every adjacent pair as a mandatory dependency; some checks can run in parallel. Mark inferred edges separately from explicit ones so reviewers can challenge them. Step frames carry the source span for each action and condition.

Detect impossible graphs

A cycle means the extracted ordering cannot be executed as written: step A requires B, while B requires A. It can reflect a parsing mistake, a stale runbook or a genuine documentation defect. Report the cycle and source spans to the owner; do not break it by arbitrary ordering. Python’s standard graph sorter is enough for a local check. The code below yields an order only for an acyclic, fully referenced set of steps.

Gate unknown conditions

A topological order says only that dependencies have an order. It does not prove the replica is healthy or that an operator may restart it. Each condition needs a typed observation, freshness rule and trusted source. If the observation is missing, hold. Keep “verification required” distinct from “verified false.” Trusted action gates control the later move from a reviewed procedure to a real tool.

Audit graph quality

Test missing step references, cycles, negated steps, cross-section dependencies and alternative branches. Report edge precision and recall, condition attachment accuracy and false-ready rate. A parser can produce an acyclic graph that is still wrong because it omitted one prerequisite. Review high-impact steps separately from harmless documentation checks. The project keeps a human confirmation boundary.

Implementation

from graphlib import CycleError, TopologicalSorter

def reviewed_step_order(dependencies):
    known = set(dependencies)
    if any(required not in known for parents in dependencies.values()
           for required in parents):
        return {"state": "review", "reason": "missing-step"}
    try:
        ordered = list(TopologicalSorter(dependencies).static_order())
    except CycleError:
        return {"state": "review", "reason": "dependency-cycle"}
    return {"state": "ordered", "step_ids": ordered}

steps = {"verify-replica": set(),
         "drain-traffic": {"verify-replica"},
         "restart-gateway": {"drain-traffic"}}
assert reviewed_step_order(steps)["step_ids"] == [
    "verify-replica", "drain-traffic", "restart-gateway"]
assert reviewed_step_order({"a": {"b"}, "b": {"a"}})["reason"] ==     "dependency-cycle"

Performance and operating cost

Topological sorting and missing-reference checks take O(v+e) time and O(v+e) space for v steps and e dependency edges. The returned order does not validate condition truth, tool permissions or runbook currency. Those are separate gates before execution.

Common Mistakes

Using document order as the only dependency signal.
Breaking a cycle by silently dropping an edge.
Treating an ordered graph as authorization to run commands.
Marking an unobserved condition as satisfied.