driver: Make `checkHomeUnitsClosed` faster
The implementation of checkHomeUnitsClosed was traversing every single path
in the unit dependency graph - this grows exponentially and quickly grows to be
infeasible on larger unit dependency graphs.
Instead we replace this with a faster implementation which follows from the specificiation of the closure property - there is a closure error if there are units which are both are both (transitively) depended upon by home units and (transitively) depend on home units, but are not themselves home units.
To compute the set of units required for closure, we first compute the closure of the unit dependency graph, then the transpose of this closure, and find all units that are reachable from the home units in the transpose of the closure.
Merge request reports
Activity
added backport needed:9.10 backport needed:9.6 backport needed:9.8 labels
mentioned in issue #24503
@wz1000 is planning to add a test.
To compute the set of units required for closure, we first compute the closure of the unit dependency graph, then the transpose of this closure, and find all units that are reachable from the home units in the transpose of the closure.
My understanding is that we could compute something like:
home_unit_dependency(x) = exists y . home_unit(y) /\ dependency*(y, x) home_unit_dependant(x) = exists y . home_unit(y) /\ dependency*(x, y) is_bad(x) = home_unit_dependency(x) /\ home_unit_dependant(x) /\ not home_unit(x)Is this right? So we compute the reachable set from home units, and the reachable set from home units with the transpose, and then we intersect those and check that all the things in the set are home units?
requested review from @fendor
assigned to @marge-bot
