Skip to content
  • Zubin's avatar
    driver: Make `checkHomeUnitsClosed` faster · a933aff3
    Zubin authored and Marge Bot's avatar Marge Bot committed
    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.
    a933aff3