[Aptitude-devel] r2968 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Sat, 09 Apr 2005 18:52:50 +0000
Author: dburrows
Date: Sat Apr 9 18:52:46 2005
New Revision: 2968
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Drastic changes to how Conflicts are handled to be more correct. Hopefully.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Sat Apr 9 18:52:46 2005
@@ -2,6 +2,19 @@
* src/generic/problemresolver/aptitude_resolver.h:
+ Drastically overhaul how Conflicts are handled. Now each
+ Conflicts line generates a separate dependency for every listed
+ package *and* one dependency for each provider of every listed
+ package. This is the only sensible way to handle Conflicts in
+ the presence of virtual deps.
+
+ * src/generic/problemresolver/aptitude_resolver.h:
+
+ Actually, no need to test dep_lst.end() -- just correct
+ the erroneous test of the OR bit (I hate C++).
+
+ * src/generic/problemresolver/aptitude_resolver.h:
+
Assert that dep_lst is non-end BEFORE possibly pushing it off
the end, make dep_lst's end-ness part of the end() condition for
solver_iterators, and test against end() instead of finished.
Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h (original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h Sat Apr 9 18:52:46 2005
@@ -158,8 +158,21 @@
class aptitude_resolver_dep
{
pkgCache::DepIterator start;
+ /** If start is a Conflicts and prv is not an end iterator, then the
+ * object represents "V -> {V'_1 V'_2 ..} where the V'-s are
+ * versions of prv.OwnerPkg() that do *not* provide V.ParentPkg().
+ * Otherwise, if start is a Conflicts and prv is an end iterator,
+ * the object represents the non-virtual part of the Conflicts; if
+ * start is not a Conflicts, prv is unused.
+ *
+ * All that discussion is mainly important when checking if the dep
+ * is broken and/or when finding its solvers.
+ */
+ pkgCache::PrvIterator prv;
public:
- aptitude_resolver_dep(const pkgCache::DepIterator dep)
+ aptitude_resolver_dep(const pkgCache::DepIterator dep,
+ const pkgCache::PrvIterator _prv)
+ :prv(_prv)
{
assert(!dep.end());
if(dep->Type != pkgCache::Dep::Conflicts)
@@ -178,17 +191,24 @@
bool operator==(const aptitude_resolver_dep &other) const
{
- return start == other.start;
+ return start == other.start && prv == other.prv;
}
bool operator!=(const aptitude_resolver_dep &other) const
{
- return start != other.start;
+ return start != other.start || prv != other.prv;
}
bool operator<(const aptitude_resolver_dep &other) const
{
- return ((const pkgCache::Dependency *) start) < ((const pkgCache::Dependency *) other.start);
+ if(((const pkgCache::Dependency *) start) < ((const pkgCache::Dependency *) other.start))
+ return true;
+ else if(((const pkgCache::Dependency *) start) > ((const pkgCache::Dependency *) other.start))
+ return false;
+ else if(((const pkgCache::Provides *) prv) < ((const pkgCache::Provides *) other.prv))
+ return true;
+ else
+ return false;
}
aptitude_resolver_version get_source()
@@ -249,52 +269,77 @@
return version_iterator(pkg, pkg.VersionList());
}
+/** \note For our purposes, conflicts are revdeps of the conflicted
+ * package version(s): this is much easier to calculate than the
+ * alternative and it is sufficient (since we only need to make sure
+ * that newly broken deps due to p:v1->p:v2 show up in either v1's
+ * revdep list or v2's revdep list).
+ */
class aptitude_resolver_version::revdep_iterator
{
- /** Use the rev_dep_iterator from aptitude to make sure we pick up
- * EVERY rev_dep.
+ /** The Depends which is currently being tried. */
+ pkgCache::DepIterator dep_lst;
+ /** The Provides which is currently being tried. */
+ pkgCache::PrvIterator prv_lst;
+ /** The package version to which this dep should apply (used
+ * to check versioned deps).
*/
- rev_dep_iterator dep;
-
pkgCache::VerIterator ver;
+ /** Whether we've started looking at provides yet. */
+ bool provides_open;
+
+ /** Advance to the next valid iterator. */
+ void normalize()
+ {
+ while(dep_lst.end())
+ {
+ if(!provides_open)
+ {
+ provides_open=true;
+ prv_lst=ver.ProvidesList();
+ }
+ else
+ ++prv_lst;
+
+ if(!prv_lst.end())
+ dep_lst=prv_lst.ParentPkg().RevDependsList();
+ }
+ }
- /** \return true if dep applies to ver: this is, if it is
- * a strong dependency on ver or if it is
- * a conflicts on pkg that does NOT match ver.
+ /** \return true if dep_lst applies to ver: this is, if it is
+ * a strong dependency on ver.
*/
bool applicable() const
{
- const pkgCache::DepIterator &d=*dep;
- if(!const_cast<pkgCache::DepIterator &>(d).IsCritical())
+ if(!const_cast<pkgCache::DepIterator &>(dep_lst).IsCritical())
return false;
- const bool is_conflict=(d->Type == pkgCache::Dep::Conflicts);
-
// Unversioned deps always apply.
- if(!d.TargetVer())
- return !is_conflict;
-
- // Otherwise, it doesn't apply (whether it's a conflict or not) if
- // it's a virtual dep (will have to fix this when versioned
- // provides are available, but it's not easy 'cos I'd have to
- // extract the PrvIterator; maybe add capabilities to
- // rev_dep_iterator?).
- if(const_cast<pkgCache::DepIterator &>(d).TargetPkg() != ver.ParentPkg())
- return false;
+ if(!dep_lst.TargetVer())
+ return true;
- // ok, it's a versioned dep on the right package. Check the dep.
- if(_system->VS->CheckDep(ver.VerStr(), d->CompareOp, d.TargetVer()))
- return !is_conflict;
+ if(provides_open)
+ return _system->VS->CheckDep(prv_lst.ProvideVersion(),
+ dep_lst->CompareOp, dep_lst.TargetVer());
else
- return is_conflict;
+ return _system->VS->CheckDep(ver.VerStr(),
+ dep_lst->CompareOp, dep_lst.TargetVer());
}
public:
/** Generate a revdep_iterator to cover the reverse deps of
* the given version. (note that v may be an end iterator..)
*/
revdep_iterator(const pkgCache::VerIterator &v)
- :dep(v), ver(v)
+ :ver(v), prv_lst(*apt_cache_file, 0, (pkgCache::Package *) 0),
+ provides_open(false)
{
+ // Note that if v is an end iterator, we present an empty list and
+ // hence don't need to know its package. This is safe because the
+ // [UNINST] version has no reverse dependencies (except conflicts,
+ // but those are handled in the usual way).
+ if(!v.end())
+ dep_lst=v.ParentPkg().RevDependsList();
+ normalize();
}
// bool operator==(const revdep_iterator &other) const
@@ -309,19 +354,22 @@
bool end() const
{
- return dep.end();
+ return dep_lst.end();
}
aptitude_resolver_dep operator*() const
{
- return *dep;
+ return aptitude_resolver_dep(dep_lst, prv_lst);
}
revdep_iterator &operator++()
{
do
- ++dep;
- while(!dep.end() && !applicable());
+ {
+ ++dep_lst;
+ normalize();
+ }
+ while(!dep_lst.end() && !applicable());
return *this;
}
@@ -337,6 +385,8 @@
* by the universe's broken_dep_iterator and hidden from the
* resolver).
*
+ * For Conflicts, at most one Provides is followed.
+ *
* Ugh, too many members :(.
*/
class aptitude_resolver_dep::solver_iterator
@@ -350,6 +400,121 @@
*/
bool finished;
+ /** Advance to the next interesting version/provides -- i.e., skip
+ * uninteresting ones.
+ */
+ void normalize()
+ {
+ if(dep_lst->Type != pkgCache::Dep::Conflicts)
+ {
+ while(!end())
+ {
+ while(!ver_lst.end())
+ {
+ bool ver_matches=(!dep_lst.TargetVer()) || _system->VS->CheckDep(ver_lst.VerStr(), dep_lst->CompareOp, dep_lst.TargetVer());
+
+ if(ver_matches)
+ // Found the next entry; drop out.
+ return;
+ else
+ ++ver_lst;
+ }
+
+ // If we ran out of versions, try provides instead.
+ while(!prv_lst.end())
+ {
+ bool prv_matches=(!dep_lst.TargetVer()) ||
+ (prv_lst.ProvideVersion() &&
+ _system->VS->CheckDep(prv_lst.ProvideVersion(),
+ dep_lst->CompareOp,
+ dep_lst.TargetVer()));
+
+ if(prv_matches)
+ return;
+ else
+ ++prv_lst;
+ }
+ }
+
+ if(!(dep_lst->CompareOp & pkgCache::Dep::Or))
+ finished=true;
+ else
+ {
+ ++dep_lst;
+ // Since we aren't finished, dep_lst should be valid.
+ assert(!dep_lst.end());
+ ver_lst=dep_lst.TargetPkg().VersionList();
+
+ // Only set the prv_lst to non-end if there is no target
+ // version.
+ if(!dep_lst.TargetVer())
+ prv_lst=dep_lst.TargetPkg().ProvidesList();
+ }
+ }
+ else
+ {
+ // For Conflicts, 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())
+ {
+ bool ver_matches=false;
+
+ // Does this version Provide something that hits
+ // the conflict?
+ for(pkgCache::PrvIterator prv2=ver_lst.ProvidesList();
+ !ver_matches && !prv2.end(); ++prv2)
+ if(prv2.ParentPkg()==dep_lst.ParentPkg())
+ ver_matches=(!dep_lst.TargetVer()) ||
+ (prv2.ProvideVersion() &&
+ _system->VS->CheckDep(prv2.ProvideVersion(),
+ dep_lst->CompareOp,
+ dep_lst.TargetVer()));
+
+ // If not, it can resolve the conflict.
+ if(!ver_matches)
+ return;
+
+ ++ver_lst;
+ }
+ // Important point: end version iterators always match
+ // a Conflicts! (i.e., any Conflicts can 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)
+ // This version resolves the conflict.
+ return;
+ else
+ ++ver_lst;
+ }
+
+ // Ignore provides; as above, end versions are A-OK.
+ return;
+ }
+ }
+
+ }
+
public:
solver_iterator(const pkgCache::DepIterator &start)
:dep_lst(start),
@@ -358,86 +523,54 @@
{
if(!dep_lst.end())
{
+ assert(dep_lst->Type != pkgCache::Dep::Conflicts);
+
ver_lst=const_cast<pkgCache::DepIterator &>(start).TargetPkg().VersionList();
prv_lst=const_cast<pkgCache::DepIterator &>(start).TargetPkg().ProvidesList();
+ normalize();
}
}
- solver_iterator()
- :prv_lst(*apt_cache_file, 0, (pkgCache::Package *) 0), finished(true)
- {
- }
-
- // Note that all "finished" iterators are considered equal. boo.
- // Maybe I should just break down and have "end" routines here.
- bool operator==(const solver_iterator &other)
+ /** Initialize a Conflicts solution iterator. */
+ solver_iterator(const pkgCache::DepIterator &d,
+ const pkgCache::PrvIterator &p)
+ :dep_lst(d), prv_lst(p), finished(d.end())
{
- if(finished && other.finished)
- return true;
- else if(!finished && !other.finished &&
- dep_lst == other.dep_lst &&
- ver_lst == other.ver_lst &&
- prv_lst == other.prv_lst)
- return true;
- else
- return false;
+ if(!dep_lst.end())
+ {
+ assert(d->Type == pkgCache::Dep::Conflicts);
+ // Either we're looking at all versions of the named dep, or
+ // at all versions of the providing package.
+ if(prv_lst.end())
+ ver_lst=const_cast<pkgCache::DepIterator &>(dep_lst).TargetPkg().VersionList();
+ else
+ ver_lst=const_cast<pkgCache::PrvIterator &>(p).OwnerPkg().VersionList();
+ }
}
- bool operator!=(const solver_iterator &other)
+ solver_iterator()
+ :prv_lst(*apt_cache_file, 0, (pkgCache::Package *) 0), finished(true)
{
- if(finished != other.finished)
- return true;
- else if(!finished && (dep_lst != other.dep_lst ||
- ver_lst != other.ver_lst ||
- prv_lst != other.prv_lst))
- return true;
- else
- return false;
}
solver_iterator &operator++()
{
- // Note that we're OK as long as dependencies last.
- while(!end())
- {
- // First, advance whatever needs to be advanced next in the
- // sub-list.
-
- if(!ver_lst.end())
- ++ver_lst;
- else if(!prv_lst.end())
- ++prv_lst;
-
- while(!ver_lst.end())
- {
- bool ver_matches=(!dep_lst.TargetVer()) || _system->VS->CheckDep(ver_lst.VerStr(), dep_lst->CompareOp, dep_lst.TargetVer());
+ assert(!end());
- if((ver_matches && dep_lst->Type != pkgCache::Dep::Conflicts) ||
- (!ver_matches && dep_lst->Type == pkgCache::Dep::Conflicts))
- // Found the next entry.
- return *this;
- else
- ++ver_lst;
- }
+ // Advance whatever needs to be advanced next in the
+ // sub-list.
- // If we ran out of versions, try provides instead.
+ if(!ver_lst.end())
+ ++ver_lst;
+ else if(dep_lst->Type != pkgCache::Dep::Conflicts)
+ {
if(!prv_lst.end())
- return *this;
-
- // All conflicts are a conflict alone. Or something like
- // that.
- if(dep_lst->Type == pkgCache::Dep::Conflicts ||
- !(dep_lst->CompareOp & pkgCache::Dep::Or))
- finished=true;
- else
- {
- // Since we aren't finished, dep_lst should be valid.
- assert(!dep_lst.end());
- ++dep_lst;
- ver_lst=dep_lst.TargetPkg().VersionList();
- prv_lst=dep_lst.TargetPkg().ProvidesList();
- }
+ ++prv_lst;
}
+ else
+ finished=true;
+
+ normalize();
}
aptitude_resolver_version operator*() const
@@ -446,8 +579,20 @@
if(!ver_lst.end())
return aptitude_resolver_version(ver_lst.ParentPkg(),ver_lst);
- else // Assume !prv_lst.end()
- return aptitude_resolver_version(const_cast<pkgCache::PrvIterator &>(prv_lst).OwnerPkg(),const_cast<pkgCache::PrvIterator &>(prv_lst).OwnerVer());
+ else // In this case we're trying to remove some package or other.
+ {
+ if(dep_lst->Type != pkgCache::Dep::Conflicts)
+ {
+ // Assume this because otherwise end() should be true.
+ assert(!prv_lst.end());
+
+ return aptitude_resolver_version(const_cast<pkgCache::PrvIterator &>(prv_lst).OwnerPkg(),const_cast<pkgCache::PrvIterator &>(prv_lst).OwnerVer());
+ }
+ else if(!prv_lst.end())
+ return aptitude_resolver_version(const_cast<pkgCache::PrvIterator &>(prv_lst).OwnerPkg(),ver_lst);
+ else
+ return aptitude_resolver_version(const_cast<pkgCache::DepIterator &>(dep_lst).TargetPkg(),ver_lst);
+ }
}
bool end() const
@@ -510,12 +655,23 @@
class pkgCache::PkgIterator pkg;
class pkgCache::VerIterator ver;
class pkgCache::DepIterator dep;
+ class pkgCache::PrvIterator prv;
+ bool prv_open;
// Advance to the next valid dep (inclusive of dep).
void normalize()
{
while(dep.end() && !pkg.end())
{
+ // If prv_open, we are iterating over the Provides of
+ // something upon which a package depends. This is a good
+ // situation *unless* we ran out of Provides.
+ if(prv_open && prv.end())
+ prv_open=false;
+
+ if(prv_open)
+ return;
+
while(dep.end() && !ver.end())
{
// Since dep is an end iterator, advance at least
@@ -541,7 +697,8 @@
public:
// Start from the given package (typically Head() or End()).
dep_iterator(const pkgCache::PkgIterator &_pkg)
- :pkg(_pkg)
+ :pkg(_pkg), prv(*apt_cache_file, 0, (pkgCache::Package *) 0),
+ prv_open(false)
{
if(!pkg.end())
ver=pkg.VersionList();
@@ -553,21 +710,38 @@
aptitude_universe::dep operator*() const
{
- return dep;
+ return aptitude_universe::dep(dep, prv);
}
dep_iterator &operator++()
{
- // Advance to the end of the OR...
- while(!dep.end() && (dep->CompareOp & pkgCache::Dep::Or))
- ++dep;
-
- // ...and beyond!
- if(!dep.end())
- ++dep;
+ assert(!dep.end());
- // Look for a valid dep.
- normalize();
+ // If the Provides list is open, push it.
+ if(!prv.end())
+ ++prv;
+ // otherwise, if we aren't trying to iterate over a Provides
+ // list and the current dep is a Conflicts, start such an
+ // iteration.
+ else if(!prv_open && dep->Type == pkgCache::Dep::Conflicts)
+ {
+ prv_open=true;
+ prv=dep.TargetPkg().ProvidesList();
+ }
+ // Otherwise just advance blindly.
+ else
+ {
+ // Advance to the end of the OR...
+ while(!dep.end() && (dep->CompareOp & pkgCache::Dep::Or))
+ ++dep;
+
+ // ...and beyond!
+ if(!dep.end())
+ ++dep;
+
+ // Look for a valid dep.
+ normalize();
+ }
}
bool end() const
@@ -593,6 +767,11 @@
{
class pkgCache::PkgIterator pkg;
class pkgCache::DepIterator the_dep;
+ /** If the_dep is a Conflicts, then the following keep track
+ * of which sub-relationship is being examined.
+ */
+ class pkgCache::PrvIterator prv;
+ bool prv_open;
// Push forward to the next interesting point.
void normalize()
@@ -620,11 +799,64 @@
++the_dep;
}
}
+
+ // Now dep is a broken dep or an end dep. If it is a conflicts,
+ // we might need to push down into Provides...
+ if(!the_dep.end() && the_dep->Type == pkgCache::Dep::Conflicts)
+ {
+ // If we aren't in provides, check whether the dep is
+ // trivially broken (i.e., without following provides).
+ if(!prv_open)
+ {
+ pkgCache::VerIterator ver=(*apt_cache_file)[the_dep.TargetPkg()].InstVerIter(*apt_cache_file);
+
+ if(!ver.end() &&
+ (!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())
+ {
+ // First, is the providing version going to be
+ // installed?
+ if((*apt_cache_file)[prv.OwnerPkg()].InstVerIter(*apt_cache_file) == prv.OwnerVer())
+ {
+ // Ok, does it match the version string?
+ if(!the_dep.TargetVer() ||
+ (prv.ProvideVersion() &&
+ _system->VS->CheckDep(prv.ProvideVersion(),
+ the_dep->CompareOp,
+ the_dep.TargetVer())))
+ return;
+ }
+
+ ++prv;
+ }
+
+ // Control should never reach this point because if a
+ // Conflicts is InstBroken, then SOMETHING providing the
+ // conflicted name should be planned to be installed.
+ assert(!prv.end());
+ }
}
public:
// Start from the given package (typically Head() or End()).
broken_dep_iterator(const pkgCache::PkgIterator &_pkg)
- :pkg(_pkg)
+ :pkg(_pkg), prv(*apt_cache_file, 0, (pkgCache::Package *) 0),
+ prv_open(false)
{
if(!pkg.end())
{
@@ -639,7 +871,7 @@
aptitude_universe::dep operator*() const
{
- return the_dep;
+ return aptitude_universe::dep(the_dep, prv);
}
broken_dep_iterator &operator++()
@@ -648,7 +880,16 @@
// If the_dep.end() we have pkg.end().
assert(!the_dep.end());
- ++the_dep;
+ if(!prv_open && the_dep->Type == pkgCache::Dep::Conflicts)
+ {
+ prv_open = true;
+ prv = the_dep.TargetPkg().ProvidesList();
+ }
+ else if(prv_open && !prv.end())
+ ++prv;
+ else
+ ++the_dep;
+
normalize();
return *this;
}
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 Sat Apr 9 18:52:46 2005
@@ -133,6 +133,12 @@
*
* A PU::dep::solvers_iterator iterates over the list B,C,... above.
* Dereferencing it returns a ver_iterator.
+ *
+ * \note revdeps need not iterate over \b all reverse dependencies of
+ * a version; it is sufficient that for versions v1,v2, if a
+ * dependency is satisfied by one and not the other, it appears in
+ * the revdeps list of at least one of the versions. (this allows
+ * apt's conflicts to be handled efficiently)
*/
@@ -546,6 +552,12 @@
// Note that this might be a rather expensive step -- on the other
// hand, if lots of deps are broken, we might have problems
// anyway. Just plowing ahead for now.
+ //
+ // If you touch this code, remember that the revdeps list is not a
+ // full list of the reverse dependencies; the constraint on it is
+ // that any deps newly broken by installing v must appear in
+ // *either* the reverse list of v *or* the reverse list of
+ // old_version.
for(typename version::revdep_iterator rd=old_version.revdeps_begin();
!rd.end(); ++rd)