// aptitude_resolver_universe.cc -*-c++-*- #include "aptitude_resolver_universe.h" #include "config_signal.h" #include #include #include #include #include #include #include #include using namespace std; using aptitude::Loggers; using cwidget::util::ssprintf; static inline bool ver_disappeared(const pkgCache::VerIterator ver) { return !ver.Downloadable() && (ver != ver.ParentPkg().CurrentVer() || ver.ParentPkg()->CurrentState == pkgCache::State::ConfigFiles); } /** Detects dependencies that (provides ignored) are conflicts that * can't be triggered ever. * * We want to eliminate these dependencies because they are an * inconsistency (albiet spurious) in aptitude's model: they don't * appear as reverse dependencies since there is no package that they * would be followed backwards from. * * Ignoring provides is safe since conflicts as seen in the model are * specific to a particular provides link, and * conflicts-through-provides can't be empty (true? maybe not: what * about disappeared providers?). */ static bool empty_conflict(const pkgCache::DepIterator &dep, const pkgCache::PrvIterator &prv) { if(!is_conflict(dep->Type)) return false; if(prv.end()) { bool found = false; for(pkgCache::VerIterator ver = const_cast(dep).TargetPkg().VersionList(); !ver.end() && !found; ++ver) { if(!ver_disappeared(ver) && (dep.TargetVer() == NULL || _system->VS->CheckDep(ver.VerStr(), dep->CompareOp, dep.TargetVer()))) found = true; } // If we found no matching non-disappeared version, then this // conflict is irrelevant. return !found; } else { if(ver_disappeared(const_cast(prv).OwnerVer())) return true; // If the provider doesn't match the dependency, then this is an // irrelevant conflict. return !_system->VS->CheckDep(prv.ProvideVersion(), dep->CompareOp, dep.TargetVer()); } } string aptitude_resolver_version::get_name() const { pkgCache::VerIterator ver(get_ver()); pkgCache::PkgIterator pkg(get_pkg()); if(!ver.end()) { // If there are two distinct package files with the same // Version, apt will give them the same VerStr. Detect and // compensate for this. int count=0; int idx=-1; for(pkgCache::VerIterator i=pkg.VersionList(); !i.end(); ++i) { if(i==ver) { idx=count; ++count; } else if(!strcmp(i.VerStr(), ver.VerStr())) ++count; } // if not, we have a "version" of this package that's not in // its list of versions! eassert(idx>=0); if(count>1) { ostringstream s; s << ver.VerStr() << "<" << idx+1 << ">"; return s.str(); } else return ver.VerStr(); } else // Note that this is an invalid version string for apt, so we // can't clash with real versions. return "[UNINST]"; } bool aptitude_resolver_version::revdep_iterator::applicable() const { if(!is_interesting_dep(dep_lst, cache)) return false; // Screen out self-conflicts from the reverse dependency list. Note // that we can screen out *any* conflict on a version of the same // package: if a version conflicts with itself it's ignored, and if // a version conflicts with a different version of the same package, // that's just a redundant expression of the rule that no two // versions of the same package can be simultaneously installed. // // As a bonus, this lets us match what gets generated for forward // deps. if(is_conflict(dep_lst->Type) && !prv_lst.end() && const_cast(prv_lst).OwnerPkg() == const_cast(dep_lst).ParentPkg()) return false; // Self-deps are always irrelevant regardless of whether we're in a // Provides: or not. if(prv_lst.end() && const_cast(dep_lst).ParentPkg() == const_cast(dep_lst).TargetPkg()) return false; // Drop irrelevant conflicts; that is, conflicts that are never // satisfied. This improves the connection consistency of the // abstract model. if(empty_conflict(dep_lst, prv_lst)) return false; // Unversioned deps always apply unless they are self-deps or // empty conflicts. if(!dep_lst.TargetVer()) return true; if(provides_open) return _system->VS->CheckDep(prv_lst.ProvideVersion(), dep_lst->CompareOp, dep_lst.TargetVer()); else return _system->VS->CheckDep(ver.VerStr(), dep_lst->CompareOp, dep_lst.TargetVer()); } void aptitude_resolver_version::revdep_iterator::normalize() { while(!dep_lst.end() && !applicable()) ++dep_lst; if(dep_lst.end() && !provides_open) { eassert(prv_lst.end()); prv_lst=ver.ProvidesList(); provides_open=true; if(!prv_lst.end()) { dep_lst=prv_lst.ParentPkg().RevDependsList(); while(!dep_lst.end() && !applicable()) ++dep_lst; } } // When we've run out of provides, give up.. while(dep_lst.end() && !prv_lst.end()) { eassert(provides_open); ++prv_lst; if(!prv_lst.end()) { eassert(!prv_lst.ParentPkg().end()); dep_lst=prv_lst.ParentPkg().RevDependsList(); while(!dep_lst.end() && !applicable()) ++dep_lst; } } } inline void aptitude_resolver_version::dep_iterator::advance() { bool move_to_next_dep = true; eassert(prv_open == !prv.end()); // If the Provides list is nonempty, advance it. if(!prv.end()) { eassert(prv_open); ++prv; if(prv.end()) prv_open = false; else move_to_next_dep = false; } // If we weren't trying to iterate over a Provides list *and* the // current dep is a non-versioned Conflicts, start such an // iteration. else if(!prv_open && is_conflict(dep->Type) && !dep.TargetVer()) { prv = dep.TargetPkg().ProvidesList(); if(!prv.end()) // otherwise we should advance to the next dep. { prv_open = true; move_to_next_dep = false; } } eassert(prv_open == !prv.end()); if(move_to_next_dep) { if(!dep.end() && is_conflict(dep->Type)) ++dep; else { // If it's not a conflict, skip a whole OR group. while(!dep.end() && (dep->CompareOp & pkgCache::Dep::Or)) ++dep; // Now we're on the last element of the OR group, push // forward. if(!dep.end()) ++dep; } } } inline bool aptitude_resolver_version::dep_iterator::applicable(const pkgCache::DepIterator &dep, const pkgCache::PrvIterator &prv, bool prv_open, pkgDepCache *cache) { if(prv_open) { eassert(!dep.end()); eassert(!prv.end()); eassert(is_conflict(dep->Type)); // NB: inlined pkgCache::DepIterator::IsIgnorable // if(dep.IsIgnorable(prv) == true) // return false; const pkgCache::PkgIterator pkg = dep.ParentPkg(); if(prv.OwnerPkg()->Group == pkg->Group) return false; if(pkg->Group == dep.TargetPkg()->Group && prv.OwnerPkg()->Group != pkg->Group) return false; } else if(dep.ParentPkg() == dep.TargetPkg()) return false; if(!is_interesting_dep(dep, cache)) return false; if(empty_conflict(dep, prv)) return false; return true; } bool aptitude_resolver_version::dep_iterator::applicable() { if(is_conflict(dep->Type)) // In this case the current dependency is represented completely // by the depends and provides iterators; no need to step. return applicable(dep, prv, prv_open, cache); else { // We need to check everything in the current OR block. pkgCache::DepIterator tmpdep = dep; if(!tmpdep.end() && applicable(tmpdep, prv, prv_open, cache)) return true; while(!tmpdep.end() && (tmpdep->CompareOp & pkgCache::Dep::Or)) { ++tmpdep; if(!tmpdep.end() && applicable(tmpdep, prv, prv_open, cache)) return true; } } return false; } void aptitude_resolver_version::dep_iterator::normalize() { while(!dep.end() && !applicable()) advance(); // If we ran out of deps, we're done! } void aptitude_resolver_dep::solver_iterator::normalize() { if(!is_conflict(dep_lst->Type)) { while(!end()) { for(; ver_lst.end() == false; ++ver_lst) { if(dep_lst.IsIgnorable(ver_lst.ParentPkg()) == true) continue; if(_system->VS->CheckDep(ver_lst.VerStr(), dep_lst->CompareOp, dep_lst.TargetVer()) == false) continue; if(ver_disappeared(ver_lst) == false) return; } // If we ran out of versions, try provides instead. for(; prv_lst.end() == false; ++prv_lst) { if(dep_lst.IsIgnorable(prv_lst) == true) continue; if(_system->VS->CheckDep(prv_lst.ProvideVersion(), dep_lst->CompareOp, dep_lst.TargetVer()) == false) continue; if(ver_disappeared(prv_lst.OwnerVer()) == false) return; } // No more target versions or providers of the target; // increment the dependency list if we aren't yet at the // end of the OR group. if(!(dep_lst->CompareOp & pkgCache::Dep::Or)) finished=true; else { ++dep_lst; // Since we aren't finished, dep_lst should still be // valid. eassert(!dep_lst.end()); ver_lst=dep_lst.TargetPkg().VersionList(); // Only set the prv_lst to non-end if there is no target // version. prv_lst=dep_lst.TargetPkg().ProvidesList(); } } } else { // For Conflicts/Breaks, we're iterating over all the versions of // *one* package for *one* dep, either the owner of the // dep or a provided package. (prv_lst is mostly // unnecessary, but it makes it simple to remember whether // we have a provides). Note that the efficiency of this // stanza is based on the *assumption* that most packages // only Provide a few things. // For provided packages, return exactly those packages // that *don't* have a matching Provides. if(!prv_lst.end()) { while(!ver_lst.end()) { if(ver_lst != prv_lst.OwnerVer() && !ver_disappeared(ver_lst)) return; ++ver_lst; } // Important point: end version iterators always match // a Conflicts/Breaks! (i.e., those can always be resolved // by removing the conflicted package) return; } else { while(!ver_lst.end()) { bool ver_matches=(!dep_lst.TargetVer()) || (ver_lst.VerStr() && _system->VS->CheckDep(ver_lst.VerStr(), dep_lst->CompareOp, dep_lst.TargetVer())); if(!ver_matches && !ver_disappeared(ver_lst)) // This version resolves the conflict. return; else ++ver_lst; } // Ignore provides; as above, end versions are A-OK. return; } } } bool aptitude_resolver_dep::solved_by(const aptitude_resolver_version &v) const { pkgCache::DepIterator start_iter(cache->GetCache(), const_cast(start)); // First check for moving the source. if(v.get_pkg() == start_iter.ParentPkg() && v.get_ver() != start_iter.ParentVer()) return true; // Now check each of the members of the OR group. pkgCache::DepIterator d = start_iter; if(!is_conflict(start_iter->Type)) { // Of course, installing an end version never fixes a // non-conflict unless it removes the source (tested for above). if(v.get_ver().end()) return false; while(1) { if(d.IsIgnorable(v.get_pkg()) == false && _system->VS->CheckDep(v.get_ver().VerStr(), d->CompareOp, d.TargetVer()) == true) return true; // Check for a resolution via Provides. for(pkgCache::PrvIterator p2 = v.get_ver().ProvidesList(); p2.end() == false; ++p2) { if(d.IsIgnorable(p2) == true) continue; if(p2.ParentPkg() != d.TargetPkg()) continue; if(_system->VS->CheckDep(p2.ProvideVersion(), d->CompareOp, d.TargetVer()) == true) return true; } if((d->CompareOp & pkgCache::Dep::Or) != 0) ++d; else return false; } } else if(prv == NULL) { if(d.TargetPkg() != v.get_pkg()) return false; if(v.get_ver().end()) return true; // Check the non-virtual part of the conflict: the package is // the same and the version **doesn't** match. return !(!d.TargetVer() || _system->VS->CheckDep(v.get_ver().VerStr(), d->CompareOp, d.TargetVer())); } else { pkgCache::PrvIterator prv_iter(cache->GetCache(), const_cast(prv), (pkgCache::Package *)0); // Only other versions of the provider can solve this. if(v.get_pkg() != prv_iter.OwnerPkg()) return false; else return v.get_ver() != prv_iter.OwnerVer(); } } aptitude_resolver_dep::solver_iterator &aptitude_resolver_dep::solver_iterator::operator++() { eassert(!end()); // Advance whatever needs to be advanced next in the // sub-list. if(!ver_lst.end()) ++ver_lst; else if(!is_conflict(dep_lst->Type)) { if(!prv_lst.end()) ++prv_lst; } else finished=true; normalize(); return *this; } aptitude_resolver_version::dep_iterator &aptitude_resolver_version::dep_iterator::operator++() { eassert(!dep.end()); advance(); normalize(); return *this; } aptitude_resolver_version aptitude_resolver_dep::solver_iterator::operator*() const { eassert(!end()); if(!ver_lst.end()) return aptitude_resolver_version::make_install(ver_lst, cache); else // In this case we're trying to remove some package or other. { if(!is_conflict(dep_lst->Type)) { // Assume this because otherwise end() should be true. eassert(!prv_lst.end()); return aptitude_resolver_version::make_install(const_cast(prv_lst).OwnerVer(), cache); } else if(!prv_lst.end()) return aptitude_resolver_version::make_removal(const_cast(prv_lst).OwnerPkg(), cache); else return aptitude_resolver_version::make_removal(const_cast(dep_lst).TargetPkg(), cache); } } void aptitude_universe::dep_iterator::normalize() { while(dep.end() && !pkg.end()) { while(dep.end() && !ver.end()) { ++ver; if(!ver.end()) dep=aptitude_resolver_version::dep_iterator(ver, cache); } if(dep.end()) { ++pkg; if(!pkg.end()) { ver=pkg.VersionList(); if(!ver.end()) dep=aptitude_resolver_version::dep_iterator(ver, cache); } } } } bool aptitude_universe::broken_dep_iterator::dep_is_inst_broken(const pkgCache::DepIterator &d) const { pkgCache::DepIterator d2=d; while(d2->CompareOp & pkgCache::Dep::Or) ++d2; return ((*cache)[d2] & pkgDepCache::DepGInstall)==0; } struct DummyEmptySolution { aptitude_resolver_version version_of(const aptitude_resolver_package &p) const { return p.current_version(); } }; void dumpDep(std::ostream &out, pkgCache::DepIterator &dep, pkgDepCache *cache) { out << dep.ParentPkg().FullName(false) << " (" << dep.ParentVer().VerStr() << ") " << dep.DepType() << " " << dep.TargetPkg().FullName(false); if(dep.TargetVer() != NULL) { out << " (" << dep.CompType() << " " << dep.TargetVer() << ")"; } std::vector flags; if(dep->Type & pkgCache::Dep::Or) flags.push_back("OR"); unsigned char dep_state = (*cache)[dep]; if(dep_state & pkgDepCache::DepNow) flags.push_back("DEPNOW"); if(dep_state & pkgDepCache::DepInstall) flags.push_back("DEPINSTALL"); if(dep_state & pkgDepCache::DepCVer) flags.push_back("DEPCVER"); if(dep_state & pkgDepCache::DepGNow) flags.push_back("DEPGNOW"); if(dep_state & pkgDepCache::DepGInstall) flags.push_back("DEPGINSTALL"); if(dep_state & pkgDepCache::DepGCVer) flags.push_back("DEPGCVER"); out << "["; bool first = true; for(std::vector::const_iterator it = flags.begin(); it != flags.end(); ++it) { if(first) first = false; else out << " "; out << *it; } out << "]"; } void aptitude_universe::broken_dep_iterator::normalize() { while(!the_dep.end() && !(is_interesting_dep(the_dep, cache) && dep_is_inst_broken(the_dep))) ++the_dep; while(the_dep.end() && !pkg.end()) { // Make sure we move at least one package forward! // Otherwise we just spin on the same package over and over, // since it's still broken.. ++pkg; if(!pkg.end()) { // Examine just the InstVer of the package. pkgCache::VerIterator ver=(*cache)[pkg].InstVerIter(*cache); if(!ver.end()) the_dep=ver.DependsList(); while(!the_dep.end() && !(is_interesting_dep(the_dep, cache) && dep_is_inst_broken(the_dep))) ++the_dep; if(the_dep.end()) ++ver; } } eassert(the_dep.end() || is_interesting_dep(the_dep, cache)); // Now dep is a broken critical dep or an end dep. If it is a // conflicts, we might need to push down into Provides... if(!the_dep.end() && is_conflict(the_dep->Type)) { // If we aren't in provides, check whether the dep is // trivially broken (i.e., without following provides). if(!prv_open) { // If it's a direct self-conflict, jump into provides // right away. if(the_dep.TargetPkg() != the_dep.ParentPkg()) { pkgCache::VerIterator ver=(*cache)[the_dep.TargetPkg()].InstVerIter(*cache); if(!ver.end() && !ver_disappeared(ver) && (!the_dep.TargetVer() || (ver.VerStr() && _system->VS->CheckDep(ver.VerStr(), the_dep->CompareOp, the_dep.TargetVer())))) // OK, the dep is broken without provides, no need // to descend. return; } prv_open=true; prv=the_dep.TargetPkg().ProvidesList(); } // Ok, we have found something that causes breakage. The // provides-list is a list of all the package versions that // provide this package name; move forward until we find one // that matches. while(!prv.end()) { // Ignore indirect self-conflicts. if(prv.OwnerPkg() != the_dep.ParentPkg()) { // First, is the providing version going to be // installed? if((*cache)[prv.OwnerPkg()].InstVerIter(*cache) == prv.OwnerVer()) { // Ok, does it match the version string? bool matches = !the_dep.TargetVer() || (prv.ProvideVersion() && _system->VS->CheckDep(prv.ProvideVersion(), the_dep->CompareOp, the_dep.TargetVer())); if(ver_disappeared(prv.OwnerVer())) matches = false; if(matches) return; } } ++prv; } // if all provides are exhausted, increment the dep and try // again. (probably this was only a self-conflict and // nothing else) ++the_dep; prv_open=false; normalize(); // hopefully g++ is smart enough to optimize this into a // tail call. return; } if(!end() && !(**this).broken_under(DummyEmptySolution())) { std::ostringstream s; s << **this; // Not translated because this is an internal error that users // should report to me verbatim. _error->Warning("apt thinks that %s is broken, but I don't.", s.str().c_str()); ++(*this); return; } } aptitude_universe::broken_dep_iterator &aptitude_universe::broken_dep_iterator::operator++() { eassert(!pkg.end()); // If the_dep.end() we have pkg.end(). eassert(!the_dep.end()); if(!prv_open && is_conflict(the_dep->Type)) { prv_open = true; prv = the_dep.TargetPkg().ProvidesList(); } else if(prv_open && !prv.end()) ++prv; else ++the_dep; normalize(); return *this; } std::ostream &operator<<(ostream &out, const aptitude_resolver_package &p) { return out << p.get_name(); } std::ostream &operator<<(ostream &out, const aptitude_resolver_version &v) { return out << v.get_package().get_name() << " " << v.get_name(); } std::ostream &operator<<(ostream &out, const aptitude_resolver_dep &d) { std::vector solvers; for(aptitude_resolver_dep::solver_iterator i=d.solvers_begin(); !i.end(); ++i) solvers.push_back(*i); generic_solution::ver_name_lt lt; sort(solvers.begin(), solvers.end(), lt); out << d.get_source() << (d.is_soft() ? " -S> {" : " -> {"); for(std::vector::const_iterator i = solvers.begin(); i != solvers.end(); ++i) { if(i != solvers.begin()) out << " "; out << *i; } out << "}"; return out; } std::ostream &operator<<(std::ostream &out, const cfg_level &level) { if(level.get_is_discard()) out << "discard"; else out << level.get_level(); return out; } cfg_level aptitude_universe::parse_level(const std::string &s) { if(s == "maximum") return cfg_level::make_level(cost_limits::maximum_level); else if(s == "minimum" || s == "") return cfg_level::make_level(cost_limits::minimum_level); else if(s == "conflict" || s == "discard") return cfg_level::make_conflict(); else { char *endptr; int n = static_cast(strtol(s.c_str(), &endptr, 0)); if(*endptr != '\0') { std::string msg(ssprintf(N_("Invalid safety level \"%s\" (not \"discard\", \"maximum\", \"minimum\", or an integer)."), s.c_str())); LOG_ERROR(Loggers::getAptitudeResolverCosts(), msg); _error->Error("%s", _(msg.c_str())); return cfg_level::make_level(cost_limits::minimum_level); } else return cfg_level::make_level(n); } } cfg_level aptitude_universe::parse_levels(const std::string &level1, const std::string &level2, cfg_level default_level) { if(level1.empty() && level2.empty()) return default_level; else if(level1.empty()) return parse_level(level2); else if(level2.empty()) return parse_level(level1); else return std::max(parse_level(level1), parse_level(level2)); } cfg_level aptitude_universe::get_safe_level() { return parse_levels(aptcfg->Find(PACKAGE "::ProblemResolver::Safe-Level", ""), aptcfg->Find(PACKAGE "::ProblemResolver::Safe-Tier", ""), cfg_level::make_level(10000)); } cfg_level aptitude_universe::get_keep_all_level() { return parse_levels(aptcfg->Find(PACKAGE "::ProblemResolver::Keep-All-Level", ""), aptcfg->Find(PACKAGE "::ProblemResolver::Keep-All-Tier", ""), cfg_level::make_level(20000)); } cfg_level aptitude_universe::get_remove_level() { return parse_levels(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Level", ""), aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Tier", ""), cfg_level::make_level(10000)); } cfg_level aptitude_universe::get_break_hold_level() { return parse_levels(aptcfg->Find(PACKAGE "::ProblemResolver::Break-Hold-Level", ""), aptcfg->Find(PACKAGE "::ProblemResolver::Break-Hold-Tier", ""), cfg_level::make_level(40000)); } cfg_level aptitude_universe::get_non_default_level() { return parse_levels(aptcfg->Find(PACKAGE "::ProblemResolver::Non-Default-Level", ""), aptcfg->Find(PACKAGE "::ProblemResolver::Non-Default-Tier", ""), cfg_level::make_level(50000)); } cfg_level aptitude_universe::get_remove_essential_level() { return parse_levels(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Essential-Level", ""), aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Essential-Tier", ""), cfg_level::make_level(60000)); } bool aptitude_universe::is_candidate_for_initial_set(const aptitude_resolver_dep &d) const { if(!d.is_soft()) return true; if(cache == NULL) return false; pkgCache::DepIterator d2(d.get_dep()); while(!d2.end() && (d2->CompareOp & pkgCache::Dep::Or)) ++d2; if(d2.end()) return true; // Return true only if the dependency is *currently* not broken. return (*cache)[d2] & pkgDepCache::DepGNow; }