2 Commits

Author SHA1 Message Date
Julian Brost
63e9ef58ba Prevent worst-case exponential complexity in dependency evaluation
So far, calling Checkable::IsReachable() traversed all possible paths to it's
parents. In case a parent is reachable via multiple paths, all it's parents
were evaluated multiple times, result in a worst-case exponential complexity.

With this commit, the implementation keeps track of which checkables were
already visited and uses the already-computed reachability instead of repeating
the computation, ensuring a worst-case linear runtime within the graph size.
2025-08-04 10:42:20 +02:00
Julian Brost
43f1e6f3a1 Move code involved in recursive dependency evaluation to helper class
Checkable::IsReachable() and DependencyGroup::GetState() call each other
recursively. Moving them to a common helper class allows adding caching to them
in a later commit without having to pass a cache between the functions (through
a public interface) or resorting to thread_local variables.
2025-08-04 10:42:20 +02:00