[Aptitude-devel] r3148 - in branches/aptitude-0.3/aptitude: . src/generic src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Wed, 27 Apr 2005 14:44:06 +0000
Author: dburrows
Date: Wed Apr 27 14:44:03 2005
New Revision: 3148
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Use domain-specific knowledge to check whether dependencies are broken.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Wed Apr 27 14:44:03 2005
@@ -1,5 +1,11 @@
2005-04-27 Daniel Burrows <dburrows@debian.org>
+ * src/generic/aptitude_resolver.h, src/generic/problemresolver/problemresolver.h:
+
+ Add a 'broken_under' method to the aptitude_resolver_dep class,
+ and use it in the problem resolver to (hopefully) speed up
+ checking whether dependencies are broken in a given solution.
+
* src/generic/aptcache.cc, src/generic/aptitude_resolver.cc, src/generic/aptitude_resolver.h, src/generic/problemresolver/problemresolver.h:
Add basic support in the problem-resolver for specifying
Modified: branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h (original)
+++ branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h Wed Apr 27 14:44:03 2005
@@ -238,6 +238,12 @@
return false;
}
+ /** SolutionType is a class defining the method ST.version_of(pkg),
+ * which returns the installed version of pkg according to ST.
+ */
+ template<class SolutionType>
+ bool broken_under(const SolutionType &S) const;
+
pkgCache::DepIterator get_dep() const
{
return start;
@@ -583,7 +589,7 @@
public:
solver_iterator(const pkgCache::DepIterator &start)
- :dep_lst(start),
+ :dep_lst(start),
prv_lst(*apt_cache_file, 0, (pkgCache::Package *) 0),
finished(start.end())
{
@@ -696,6 +702,75 @@
return solver_iterator(start, prv);
}
+template<class SolutionType>
+bool aptitude_resolver_dep::broken_under(const SolutionType &S) const
+{
+ // First, check that the solution actually installs the source.
+ if(const_cast<pkgCache::DepIterator &>(start).ParentVer() != S.version_of(const_cast<pkgCache::DepIterator &>(start).ParentPkg()).get_ver())
+ return false;
+
+ if(start->Type != pkgCache::Dep::Conflicts)
+ {
+ pkgCache::DepIterator dep=start;
+
+ while(!dep.end())
+ {
+ pkgCache::VerIterator direct_ver=S.version_of(dep.TargetPkg()).get_ver();
+ if(!direct_ver.end() &&
+ _system->VS->CheckDep(direct_ver.VerStr(),
+ dep->CompareOp,
+ dep.TargetVer()))
+ return false;
+
+ if(!dep.TargetVer())
+ {
+ for(pkgCache::PrvIterator prv=dep.TargetPkg().ProvidesList();
+ !prv.end(); ++prv)
+ if(prv.OwnerVer() == S.version_of(prv.OwnerPkg()).get_ver())
+ return false;
+ }
+
+ if(!(dep->CompareOp & pkgCache::Dep::Or))
+ break;
+ ++dep;
+ }
+
+ return true;
+ }
+ else
+ {
+ // Recall that a Conflicts dep iterator is looking at a single
+ // element of the Conflicts: either a direct conflict or an
+ // indirect conflict (i.e., via a virtual pkg).
+
+ if(prv.end())
+ {
+ if(const_cast<pkgCache::DepIterator &>(start).TargetPkg() == const_cast<pkgCache::DepIterator &>(start).ParentPkg())
+ return false;
+
+ pkgCache::VerIterator direct_ver=S.version_of(const_cast<pkgCache::DepIterator &>(start).TargetPkg()).get_ver();
+
+ if(!(!direct_ver.end() &&
+ _system->VS->CheckDep(direct_ver.VerStr(),
+ start->CompareOp,
+ start.TargetVer())))
+ return true;
+ else
+ return false;
+ }
+ else
+ {
+ if(const_cast<pkgCache::PrvIterator &>(prv).OwnerPkg() == const_cast<pkgCache::DepIterator &>(start).ParentPkg())
+ return false;
+
+ if(start.TargetVer())
+ return false;
+
+ return S.version_of(const_cast<pkgCache::PrvIterator &>(prv).OwnerPkg()).get_ver()==const_cast<pkgCache::PrvIterator &>(prv).OwnerVer();
+ }
+ }
+}
+
class aptitude_universe
{
public:
Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h (original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h Wed Apr 27 14:44:03 2005
@@ -494,41 +494,39 @@
/** Stores already-seen solutions: */
std::set<solution, solution_contents_compare> closed;
- /** Test whether a version is "installed" given a solution and
- * a new version to install.
+ /** Represents a possible successor to the given solution, created
+ * by installing a single 'new' version.
*/
- bool ver_installed(const solution &s,
- const version &add_ver,
- const version &test_ver)
+ class partial_solution
{
- if(add_ver.get_package() == test_ver.get_package())
- return add_ver == test_ver;
- else
- return s.version_of(test_ver.get_package()) == test_ver;
- }
+ /** The solution this is based on. */
+ solution s;
+ /** The version to installed. */
+ version ver;
+ public:
+ partial_solution (const solution &_s, const version &_ver)
+ :s(_s), ver(_ver)
+ {
+ }
- /** Test whether a dependency is broken given the a solution and a
- * single-version installation.
- */
- bool dep_broken(const solution &s,
- const version &v,
- const dep &d)
- {
- if(!ver_installed(s, v, d.get_source()))
- return false;
-
- // Could be somewhat inefficient for APT; think about how to
- // mitigate that by offering higher-level "imagine this situation;
- // is this dep broken?" operations in the universe.
- for(typename dep::solver_iterator i=d.solvers_begin();
- !i.end(); ++i)
- {
- if(ver_installed(s, v, *i))
- return false;
- }
+ /** \return the currently installed version of the given
+ * package.
+ */
+ version version_of(const package &pkg) const
+ {
+ if(pkg == ver.get_package())
+ return ver;
+ else
+ return s.version_of(pkg);
+ }
- return true;
- }
+ /** Test whether the given version is installed in this solution.
+ */
+ bool ver_installed(const version &test_ver) const
+ {
+ return version_of(test_ver.get_package()) == test_ver;
+ }
+ };
/** Enqueues a single successor node to the given solution by
* installing the given package version.
@@ -550,6 +548,7 @@
assert(v.get_package().current_version().get_id()<universe.get_version_count());
new_action_score-=version_scores[v.get_package().current_version().get_id()];
+ partial_solution S(s, v);
std::set<dep> new_broken;
// Check all revdeps of the old AND new package versions, and all
// previously broken deps. Is there any way to speed this up?
@@ -571,18 +570,18 @@
for(typename version::revdep_iterator rd=old_version.revdeps_begin();
!rd.end(); ++rd)
- if(dep_broken(s, v, *rd))
+ if((*rd).broken_under(S))
new_broken.insert(*rd);
for(typename version::revdep_iterator rd=v.revdeps_begin();
!rd.end(); ++rd)
- if(dep_broken(s, v, *rd))
+ if((*rd).broken_under(S))
new_broken.insert(*rd);
const std::set<dep> &old_broken=s.get_broken();
for(typename std::set<dep>::const_iterator bd=old_broken.begin();
bd!=old_broken.end(); ++bd)
- if(dep_broken(s, v, *bd))
+ if((*bd).broken_under(S))
new_broken.insert(*bd);
int new_score=new_action_score+broken_score*new_broken.size();