"""The AUR build DAG.
AUR packages depend on other AUR packages, and those have to be built first. That
ordering is the whole reason a flat "updating 23 packages" line is useless: the
interesting information is *which* packages have to finish before *which*, and
which dependencies are shared (a diamond).
paru computes this internally but does not expose it, so we derive it from the
.SRCINFO files it already cloned.
"""
from __future__ import annotations
from collections import deque
from dataclasses import dataclass, field
from .srcinfo import SrcInfo, dep_name
@dataclass
class Node:
name: str
version: str = ""
#: AUR dependencies that are themselves in this graph
deps: set[str] = field(default_factory=set)
#: AUR dependencies that are NOT in the graph (already satisfied, or missing)
external: set[str] = field(default_factory=set)
#: False when no .SRCINFO was available, which means `deps` is not merely
#: empty but *unknown*, and the node cannot be ordered or scheduled.
metadata_known: bool = True
class MissingMetadata(RuntimeError):
"""Raised when a graph is required to be orderable but is not."""
def __init__(self, names: list[str]) -> None:
self.names = names
super().__init__(
f"{len(names)} package(s) are not cloned yet, so what they depend "
f"on is not known: {', '.join(names[:8])}" + (" …" if len(names) > 8 else "")
)
@property
def detail(self) -> list[str]:
"""What it means and what happens, rather than a restatement."""
return [
"paru keeps a copy of each AUR repository it has built. These have",
"not been built here yet, so there is no copy to read and their",
"dependencies cannot be worked out in advance.",
"",
"Nothing is wrong. They are still built -- paru resolves each",
"package's own dependencies when it gets to it. The only thing",
"lost is the ordering between them, so one may be attempted before",
"something else it needs, and be retried on a later pass.",
"",
"The list:",
"",
*[f" {name}" for name in sorted(self.names)[:20]],
*([f" + {len(self.names) - 20} more"] if len(self.names) > 20 else []),
]
@dataclass
class Graph:
nodes: dict[str, Node] = field(default_factory=dict)
#: names that can be ordered, in the order they may safely start
order: list[str] = field(default_factory=list)
#: dependency cycles; AUR packages really do contain these
cycles: list[list[str]] = field(default_factory=list)
#: nodes depended on by more than one other node (the diamonds)
shared: set[str] = field(default_factory=set)
#: nodes that nothing else depends on
roots: list[str] = field(default_factory=list)
#: nodes with no metadata: present, but not orderable
unknown: list[str] = field(default_factory=list)
#: orderable nodes held back because something they need is not orderable
blocked_by_unknown: list[str] = field(default_factory=list)
def __len__(self) -> int:
return len(self.nodes)
@property
def is_orderable(self) -> bool:
"""Whether the computed order covers every package that must be built."""
return not self.unknown and not self.cycles and not self.blocked_by_unknown
def dependents(self, name: str) -> list[str]:
return sorted(n for n, node in self.nodes.items() if name in node.deps)
def ready(self, completed: set[str], running: set[str] | None = None) -> list[str]:
"""Nodes whose dependencies are all complete and which are not started.
Only orderable nodes are ever returned: a node whose dependencies are
unknown cannot be shown to be ready, so it is never scheduled.
"""
running = running or set()
return [
name
for name in self.order
if name not in completed and name not in running and self.nodes[name].deps <= completed
]
def blocked(self, failed: set[str]) -> set[str]:
"""Everything transitively unbuildable because `failed` could not build."""
out: set[str] = set()
frontier = deque(failed)
while frontier:
name = frontier.popleft()
for dependent in self.dependents(name):
if dependent not in out:
out.add(dependent)
frontier.append(dependent)
return out - set(failed)
def build_graph(infos: dict[str, SrcInfo], candidates: set[str], *, strict: bool = False) -> Graph:
"""Build the DAG for a set of AUR packages that are about to be built.
`infos` maps package name -> metadata (from .SRCINFO). `candidates` is the set
being updated/built; only edges *within* that set become graph edges, because
anything outside it is already installed and needs no ordering.
A candidate with no metadata is kept in the graph but marked unknown. Its
dependencies are not empty, they are *undiscoverable*, so it is excluded from
the order and nothing that depends on it can be ordered either. Pass
`strict=True` to make that a hard error instead of a reported condition.
"""
graph = Graph()
# map provided names back to the providing package so `python-attrs` style
# virtual deps still form edges
provided: dict[str, str] = {}
# sorted: `candidates` is a set, so two packages providing the same virtual
# name would otherwise win by hash order and the graph would differ between
# runs of the same plan.
for name in sorted(candidates):
info = infos.get(name)
if not info:
continue
for prov in info.provides:
provided.setdefault(dep_name(prov), name)
for name in sorted(candidates):
info = infos.get(name)
node = Node(
name=name, version=info.version if info else "", metadata_known=info is not None
)
if info:
for spec in info.build_depends:
dep = dep_name(spec)
target = dep if dep in candidates else provided.get(dep)
if target and target != name:
node.deps.add(target)
elif dep != name:
node.external.add(dep)
graph.nodes[name] = node
graph.unknown = sorted(n for n, node in graph.nodes.items() if not node.metadata_known)
if strict and graph.unknown:
raise MissingMetadata(graph.unknown)
known = {n for n, node in graph.nodes.items() if node.metadata_known}
# a node with more than one dependent is shared (a diamond branch point)
for node in graph.nodes.values():
for dep in node.deps:
if len(graph.dependents(dep)) > 1:
graph.shared.add(dep)
# Kahn over the orderable nodes only, with a deterministic tie-break so the
# display never jitters between runs for no reason
indegree = {n: len(graph.nodes[n].deps) for n in known}
queue = deque(sorted(n for n, d in indegree.items() if d == 0))
while queue:
name = queue.popleft()
graph.order.append(name)
for dependent in graph.dependents(name):
if dependent not in indegree:
continue
indegree[dependent] -= 1
if indegree[dependent] == 0:
queue.append(dependent)
queue = deque(sorted(queue))
unplaced = known - set(graph.order)
if unplaced:
# separate "you have a dependency cycle" from "we are missing metadata
# for something this depends on": they need completely different fixes
graph.blocked_by_unknown = sorted(
n
for n in unplaced
if (graph.nodes[n].deps & set(graph.unknown))
or any(d in graph.unknown for d in graph.nodes[n].deps)
)
graph.blocked_by_unknown = sorted(
set(graph.blocked_by_unknown) | graph.blocked(graph.unknown)
)
cycle_candidates = unplaced - set(graph.blocked_by_unknown)
if cycle_candidates:
graph.cycles = _find_cycles(graph, cycle_candidates)
depended_on = {dep for node in graph.nodes.values() for dep in node.deps}
graph.roots = sorted(known - depended_on)
return graph
def _find_cycles(graph: Graph, remaining: set[str]) -> list[list[str]]:
"""Report the cycles rather than silently dropping the packages.
A cycle means the package is unbuildable as declared, which the user needs to
know about; it is not something to paper over with a best-effort order.
"""
cycles: list[list[str]] = []
colour: dict[str, int] = {}
stack: list[str] = []
def visit(name: str) -> None:
colour[name] = 1
stack.append(name)
for dep in sorted(graph.nodes[name].deps & remaining):
if colour.get(dep) == 1:
cycles.append(stack[stack.index(dep) :] + [dep])
elif colour.get(dep, 0) == 0:
visit(dep)
stack.pop()
colour[name] = 2
for name in sorted(remaining):
if colour.get(name, 0) == 0:
visit(name)
return cycles