evals/port-python-task-graph/files/taskgraph.py

GitHub
"""Parse a small task-definition format and compute a deterministic run order.

Format, one task per line:

    name: kind [p=N] <- dep1, dep2

`kind` is one of build, test, deploy. `[p=N]` is an optional integer priority
(higher runs first among tasks that are ready at the same time). `<- deps` is
optional. Blank lines and lines starting with '#' are ignored.
"""

KINDS = ("build", "test", "deploy")


class TaskError(Exception):
    """Base class for every error this module raises."""


class ParseError(TaskError):
    def __init__(self, line_no, message):
        super().__init__(f"line {line_no}: {message}")
        self.line_no = line_no


class MissingDependency(TaskError):
    def __init__(self, task, dep):
        super().__init__(f"{task} depends on unknown task {dep}")
        self.task = task
        self.dep = dep


class CycleError(TaskError):
    def __init__(self, cycle):
        super().__init__("cycle: " + " -> ".join(cycle))
        self.cycle = cycle


class Task:
    def __init__(self, name, kind, deps=None, priority=None):
        self.name = name
        self.kind = kind
        self.deps = deps or []
        self.priority = priority

    def __repr__(self):
        return f"Task({self.name!r}, {self.kind!r}, {self.deps!r}, {self.priority!r})"


def parse_tasks(text):
    """Returns a dict of name -> Task, in the order tasks were defined."""
    tasks = {}
    for line_no, raw in enumerate(text.splitlines(), start=1):
        line = raw.strip()
        if not line or line.startswith("#"):
            continue
        if ":" not in line:
            raise ParseError(line_no, "expected 'name: kind'")
        name, rest = line.split(":", 1)
        name = name.strip()
        if not name or not name.replace("-", "").replace("_", "").isalnum():
            raise ParseError(line_no, f"bad task name {name!r}")
        if name in tasks:
            raise ParseError(line_no, f"duplicate task {name}")
        deps = []
        if "<-" in rest:
            rest, dep_text = rest.split("<-", 1)
            deps = [d.strip() for d in dep_text.split(",") if d.strip()]
        priority = None
        if "[p=" in rest:
            rest, prio_text = rest.split("[p=", 1)
            if not prio_text.strip().endswith("]"):
                raise ParseError(line_no, "unclosed priority")
            try:
                priority = int(prio_text.strip()[:-1])
            except ValueError:
                raise ParseError(line_no, "priority must be an integer")
        kind = rest.strip()
        if kind not in KINDS:
            raise ParseError(line_no, f"unknown kind {kind!r}")
        tasks[name] = Task(name, kind, deps, priority)
    return tasks


def _ready_key(task):
    # Higher priority first; tasks without a priority come after all that have one;
    # ties broken by name.
    has = task.priority is not None
    return (not has, -(task.priority or 0), task.name)


def execution_order(tasks):
    """Returns task names in a valid run order.

    Raises MissingDependency for a dependency that isn't defined and CycleError,
    naming the cycle, if no order exists.
    """
    for t in tasks.values():
        for d in t.deps:
            if d not in tasks:
                raise MissingDependency(t.name, d)
    remaining = {name: set(t.deps) for name, t in tasks.items()}
    order = []
    while remaining:
        ready = [tasks[n] for n, deps in remaining.items() if not deps]
        if not ready:
            raise CycleError(_find_cycle(tasks, remaining))
        nxt = min(ready, key=_ready_key)
        order.append(nxt.name)
        del remaining[nxt.name]
        for deps in remaining.values():
            deps.discard(nxt.name)
    return order


def _find_cycle(tasks, remaining):
    start = min(remaining)
    path, seen = [], {}
    node = start
    while node not in seen:
        seen[node] = len(path)
        path.append(node)
        node = min(d for d in tasks[node].deps if d in remaining)
    return path[seen[node]:] + [node]


def summarize(tasks):
    """Returns a count of tasks per kind, for every kind, in KINDS order."""
    counts = {k: 0 for k in KINDS}
    for t in tasks.values():
        counts[t.kind] += 1
    return counts