diff options
Diffstat (limited to 'apt-pkg')
| -rw-r--r-- | apt-pkg/solver3.cc | 79 | ||||
| -rw-r--r-- | apt-pkg/solver3.h | 5 |
2 files changed, 52 insertions, 32 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ed781df13..b4a69d844 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -396,51 +396,66 @@ void APT::Solver::RegisterClause(Clause &&clause) void APT::Solver::Discover(Var var) { - auto &state = (*this)[var]; - - if (state.flags.discovered) - return; - - state.flags.discovered = true; + assert(discoverQ.empty()); + discoverQ.push(var); - if (auto Pkg = var.Pkg(cache); not Pkg.end()) + while (not discoverQ.empty()) { - Clause clause{Var(Pkg), Group::SelectVersion}; - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - clause.solutions.push_back(Var(ver)); + var = discoverQ.front(); + discoverQ.pop(); - std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); - RegisterClause(std::move(clause)); + auto &state = (*this)[var]; - RegisterCommonDependencies(Pkg); - } - else if (auto Ver = var.Ver(cache); not Ver.end()) - { - Clause clause{Var(Ver), Group::SelectVersion}; - clause.solutions = {Var(Ver.ParentPkg())}; - RegisterClause(std::move(clause)); + if (state.flags.discovered) + continue; + + state.flags.discovered = true; - for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) + if (auto Pkg = var.Pkg(cache); not Pkg.end()) { - if (OV == Ver) - continue; + Clause clause{Var(Pkg), Group::SelectVersion}; + for (auto ver = Pkg.VersionList(); not ver.end(); ver++) + clause.solutions.push_back(Var(ver)); - Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */}; - clause.solutions = {Var(OV)}; + std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); RegisterClause(std::move(clause)); - } - for (auto dep = Ver.DependsList(); not dep.end();) + RegisterCommonDependencies(Pkg); + } + else if (auto Ver = var.Ver(cache); not Ver.end()) { - // Compute a single dependency element (glob or) - pkgCache::DepIterator start; - pkgCache::DepIterator end; - dep.GlobOr(start, end); // advances dep + Clause clause{Var(Ver), Group::SelectVersion}; + clause.solutions = {Var(Ver.ParentPkg())}; + RegisterClause(std::move(clause)); - auto clause = TranslateOrGroup(start, end, Var(Ver)); + for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) + { + if (OV == Ver) + continue; - RegisterClause(std::move(clause)); + Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */}; + clause.solutions = {Var(OV)}; + RegisterClause(std::move(clause)); + } + + for (auto dep = Ver.DependsList(); not dep.end();) + { + // Compute a single dependency element (glob or) + pkgCache::DepIterator start; + pkgCache::DepIterator end; + dep.GlobOr(start, end); // advances dep + + auto clause = TranslateOrGroup(start, end, Var(Ver)); + + RegisterClause(std::move(clause)); + } } + + // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0) + for (auto const &clause : state.clauses) + for (auto const &var : clause->solutions) + if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0) + discoverQ.push(var); } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index e43e1065c..34da03ea0 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -205,6 +205,8 @@ class Solver // \brief Propagation queue std::queue<Var> propQ; + // \brief Discover variables + std::queue<Var> discoverQ; // \brief Current decision level. // @@ -232,6 +234,9 @@ class Solver bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)}; // \brief Discover a variable, translating the underlying dependencies to the SAT presentation + // + // This does a breadth-first search of the entire dependency tree of var, + // utilizing the discoverQ above. void Discover(Var var); // \brief Link a clause into the watchers void RegisterClause(Clause &&clause); |