[Aptitude-devel] r2958 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Sat, 09 Apr 2005 14:29:58 +0000
Author: dburrows
Date: Sat Apr 9 14:29:56 2005
New Revision: 2958
Added:
branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
Log:
Add an APT-based resolver.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Sat Apr 9 14:29:56 2005
@@ -1,5 +1,10 @@
2005-04-09 Daniel Burrows <dburrows@debian.org>
+ * src/generic/problemresolver/aptitude_resolver.h:
+
+ Add a preliminary APT-based resolver universe (totally untested, but it
+ sort of compiles).
+
* src/generic/problemresolver/problemresolver.h, src/generic/problemresolver/test.cc:
Make changes necessary to support apt universes in a simple way.
Added: branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h
==============================================================================
--- (empty file)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/aptitude_resolver.h Sat Apr 9 14:29:56 2005
@@ -0,0 +1,633 @@
+// aptitude_resolver.h -*-c++-*-
+//
+//
+// Copyright (C) 2005 Daniel Burrows
+
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of
+// the License, or (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; see the file COPYING. If not, write to
+// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+// Boston, MA 02111-1307, USA.
+//
+// Glue code to make the resolver talk to the core aptitude classes.
+//
+// shootshootshoot...maybe I should just teach the core about
+// conflicts...anyway, if not, then I need to be much more careful how
+// I iterate over conflicts if an OR is involved (it should be
+// basically ignored)
+
+#ifndef APTITUDE_RESOLVER_H
+#define APTITUDE_RESOLVER_H
+
+#include <apt-pkg/pkgcache.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/version.h>
+
+#include <generic/apt.h>
+#include <generic/aptcache.h>
+#include <generic/rev_dep_iterator.h>
+
+#include "problemresolver.h"
+
+class aptitude_resolver_version;
+
+/** Wraps a PkgIterator for the resolver. */
+class aptitude_resolver_package
+{
+ pkgCache::PkgIterator pkg;
+public:
+ aptitude_resolver_package(const pkgCache::PkgIterator &_pkg)
+ :pkg(_pkg)
+ {
+ }
+
+ unsigned int get_id() const
+ {
+ return pkg->ID;
+ }
+
+ bool operator==(const aptitude_resolver_package &other) const
+ {
+ return pkg==other.pkg;
+ }
+
+ bool operator!=(const aptitude_resolver_package &other) const
+ {
+ return pkg!=other.pkg;
+ }
+
+ bool operator<(const aptitude_resolver_package &other) const
+ {
+ return ((const pkgCache::Package *) pkg) < ((const pkgCache::Package *) other.pkg);
+ }
+
+ aptitude_resolver_version current_version() const;
+
+ class version_iterator;
+
+ version_iterator versions_begin() const;
+};
+
+/** Wraps a package/version pair for the resolver. */
+class aptitude_resolver_version
+{
+ pkgCache::PkgIterator pkg;
+ pkgCache::VerIterator ver;
+public:
+ aptitude_resolver_version(const pkgCache::PkgIterator &_pkg,
+ const pkgCache::VerIterator &_ver)
+ :pkg(_pkg), ver(_ver)
+ {
+ }
+
+ unsigned int get_id() const
+ {
+ if(!ver.end())
+ return ver->ID;
+ else
+ // non-installed versions are faked.
+ //
+ // If this eats a lot of time, it could be memoized..but then
+ // there's more to copy. I could also teach the resolver about
+ // "null" versions...but that would mean a bunch of pointless
+ // special-casing caller-side anyway.
+ return (*apt_cache_file)->Head().PackageCount+pkg->ID;
+ }
+
+ bool operator==(const aptitude_resolver_version &other) const
+ {
+ return pkg == other.pkg && ver == other.ver;
+ }
+
+ bool operator!=(const aptitude_resolver_version &other) const
+ {
+ return pkg == other.pkg || ver != other.ver;
+ }
+
+ bool operator<(const aptitude_resolver_version &other) const
+ {
+ if(((const pkgCache::Package *) pkg) < ((const pkgCache::Package *) other.pkg))
+ return true;
+ else if(((const pkgCache::Package *) other.pkg) < ((const pkgCache::Package *) pkg))
+ return false;
+ else if(((const pkgCache::Version *) ver) < ((const pkgCache::Version *) other.ver))
+ return true;
+ else // if(((pkgCache::Version *) other.ver) < ((pkgCache::Version *) ver))
+ return false;
+ }
+
+ class revdep_iterator;
+
+ revdep_iterator revdeps_begin();
+};
+
+aptitude_resolver_version aptitude_resolver_package::current_version() const
+{
+ return aptitude_resolver_version(pkg, (*apt_cache_file)[pkg].InstVerIter(*apt_cache_file));
+}
+
+class aptitude_resolver_dep
+{
+ pkgCache::DepIterator start;
+public:
+ aptitude_resolver_dep(const pkgCache::DepIterator dep)
+ {
+ if(dep->Type != pkgCache::Dep::Conflicts)
+ {
+ // Throw away the end, since it's not necessary.
+ pkgCache::DepIterator end;
+ surrounding_or(dep, start, end);
+ }
+ else
+ // Ignore ORs and just use the selected conflict.
+ //
+ // NOTE: as of this writing, no known package does something as
+ // stupid as ORed conflicts.
+ start=dep;
+ }
+
+ bool operator==(const aptitude_resolver_dep &other) const
+ {
+ return start == other.start;
+ }
+
+ bool operator!=(const aptitude_resolver_dep &other) const
+ {
+ return start != other.start;
+ }
+
+ bool operator<(const aptitude_resolver_dep &other) const
+ {
+ return ((const pkgCache::Dependency *) start) < ((const pkgCache::Dependency *) other.start);
+ }
+
+ aptitude_resolver_version get_source()
+ {
+ assert(!start.ParentPkg().end());
+ return aptitude_resolver_version(start.ParentPkg(), start.ParentVer());
+ }
+
+ class solver_iterator;
+
+ solver_iterator solvers_begin() const;
+};
+
+class aptitude_resolver_package::version_iterator
+{
+ pkgCache::PkgIterator pkg;
+ pkgCache::VerIterator ver;
+public:
+ version_iterator(pkgCache::PkgIterator _pkg,
+ pkgCache::VerIterator _ver)
+ :pkg(_pkg), ver(_ver)
+ {
+ }
+
+ bool operator==(const version_iterator &other) const
+ {
+ return pkg == other.pkg && ver == other.ver;
+ }
+
+ bool operator!=(const version_iterator &other) const
+ {
+ return pkg != other.pkg || ver != other.ver;
+ }
+
+ aptitude_resolver_version operator *() const
+ {
+ return aptitude_resolver_version(pkg, ver);
+ }
+
+ version_iterator &operator++()
+ {
+ ++ver;
+ return *this;
+ }
+
+ bool end() const
+ {
+ return ver.end();
+ }
+};
+
+inline aptitude_resolver_package::version_iterator aptitude_resolver_package::versions_begin() const
+{
+ return version_iterator(pkg, pkg.VersionList());
+}
+
+class aptitude_resolver_version::revdep_iterator
+{
+ /** Use the rev_dep_iterator from aptitude to make sure we pick up
+ * EVERY rev_dep.
+ */
+ rev_dep_iterator dep;
+
+ pkgCache::VerIterator ver;
+
+ /** \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.
+ */
+ bool applicable() const
+ {
+ const pkgCache::DepIterator &d=*dep;
+ if(!const_cast<pkgCache::DepIterator &>(d).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;
+
+ // 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;
+ else
+ return is_conflict;
+ }
+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)
+ {
+ }
+
+// bool operator==(const revdep_iterator &other) const
+// {
+// return dep == other.dep && ver == other.ver;
+// }
+
+// bool operator!=(const revdep_iterator &other) const
+// {
+// return dep != other.dep || ver != other.ver;
+// }
+
+ bool end() const
+ {
+ return dep.end();
+ }
+
+ aptitude_resolver_dep operator*() const
+ {
+ return *dep;
+ }
+
+ revdep_iterator &operator++()
+ {
+ do
+ ++dep;
+ while(!dep.end() && !applicable());
+
+ return *this;
+ }
+};
+
+inline aptitude_resolver_version::revdep_iterator aptitude_resolver_version::revdeps_begin()
+{
+ return revdep_iterator(ver);
+}
+
+/** This class uses a technique similar to rev_dep_lst. It assumes
+ * that the dependency is critical (noncritical deps are weeded out
+ * by the universe's broken_dep_iterator and hidden from the
+ * resolver).
+ *
+ * Ugh, too many members :(.
+ */
+class aptitude_resolver_dep::solver_iterator
+{
+ pkgCache::DepIterator dep_lst;
+ pkgCache::VerIterator ver_lst;
+ pkgCache::PrvIterator prv_lst;
+ /** \b true if we exhausted all options; needed because
+ * dep_lst might not be an end iterator (since it'll
+ * move to the next OR group)
+ */
+ bool finished;
+
+public:
+ solver_iterator(const pkgCache::DepIterator &start)
+ :dep_lst(start),
+ prv_lst(*apt_cache_file, 0, (pkgCache::Package *) 0),
+ finished(start.end())
+ {
+ if(!dep_lst.end())
+ {
+ ver_lst=const_cast<pkgCache::DepIterator &>(start).TargetPkg().VersionList();
+ prv_lst=const_cast<pkgCache::DepIterator &>(start).TargetPkg().ProvidesList();
+ }
+ }
+
+ 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)
+ {
+ 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;
+ }
+
+ bool operator!=(const solver_iterator &other)
+ {
+ 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(!finished)
+ {
+ // 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());
+
+ 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;
+ }
+
+ // If we ran out of versions, try provides instead.
+ 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
+ {
+ ++dep_lst;
+ // Since we aren't finished, dep_lst should be valid.
+ assert(!dep_lst.end());
+ ver_lst=dep_lst.TargetPkg().VersionList();
+ prv_lst=dep_lst.TargetPkg().ProvidesList();
+ }
+ }
+ }
+
+ aptitude_resolver_version operator*() const
+ {
+ assert(!finished);
+
+ 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());
+ }
+
+ bool end()
+ {
+ return finished;
+ }
+};
+
+inline aptitude_resolver_dep::solver_iterator aptitude_resolver_dep::solvers_begin() const
+{
+ return solver_iterator(start);
+}
+
+class aptitude_universe
+{
+public:
+ typedef aptitude_resolver_package package;
+ typedef aptitude_resolver_version version;
+ typedef aptitude_resolver_dep dep;
+
+ class package_iterator
+ {
+ pkgCache::PkgIterator realiter;
+ public:
+ package_iterator(pkgCache::PkgIterator _realiter)
+ :realiter(_realiter)
+ {
+ }
+
+ bool operator==(const package_iterator &other) const
+ {
+ return realiter==other.realiter;
+ }
+
+ bool operator!=(const package_iterator &other) const
+ {
+ return realiter!=other.realiter;
+ }
+
+ package operator*() const
+ {
+ return realiter;
+ }
+
+ package_iterator &operator++()
+ {
+ ++realiter;
+ return *this;
+ }
+
+ bool end() const
+ {
+ return realiter.end();
+ }
+ };
+
+ // ew
+ class dep_iterator
+ {
+ class pkgCache::PkgIterator pkg;
+ class pkgCache::VerIterator ver;
+ class pkgCache::DepIterator dep;
+
+ public:
+ // Start from the given package (typically Head() or End()).
+ dep_iterator(const pkgCache::PkgIterator &_pkg)
+ :pkg(_pkg)
+ {
+ if(!pkg.end())
+ ver=pkg.VersionList();
+ if(!ver.end())
+ dep=ver.DependsList();
+ }
+
+ aptitude_universe::dep operator*() const
+ {
+ return dep;
+ }
+
+ dep_iterator &operator++()
+ {
+ while(!pkg.end())
+ {
+ while(!ver.end())
+ {
+ while(!dep.end() && dep->CompareOp & pkgCache::Dep::Or)
+ ++dep;
+
+ if(!dep.end())
+ ++dep;
+
+ if(!dep.end())
+ return *this;
+
+ ++ver;
+ if(!ver.end())
+ dep=ver.DependsList();
+ }
+ ++pkg;
+ if(!pkg.end())
+ ver=pkg.VersionList();
+ }
+ return *this;
+ }
+
+ bool end() const
+ {
+ return pkg.end();
+ }
+ };
+
+ /** A bit like dep_iterator, but skips non-broken packages and deps.
+ * Since the "exposed version" of a package is its InstVersion, we
+ * need to test at most one version per package, so no need to keep
+ * a version iterator here.
+ *
+ * Note on OR groups: DepGInstall is only set on the last entry in
+ * an OR group. But Conflicts should be handled individually. As
+ * I'm not even sure ORed conflicts are valid, none exist in the
+ * wild, and ORed conflicts are a Pointless Idea[tm] anyway, THIS
+ * WILL NOT PRODUCE CORRECT OUTPUT for ORed conflicts. \todo try
+ * to find a way to get correct output without compromising in the
+ * main codepath.
+ */
+ class broken_dep_iterator
+ {
+ class pkgCache::PkgIterator pkg;
+ class pkgCache::DepIterator the_dep;
+
+ // Push forward to the next interesting point.
+ void normalize()
+ {
+ while(!the_dep.end() &&
+ !the_dep.IsCritical() &&
+ ((*apt_cache_file)[the_dep] & pkgDepCache::DepGInstall))
+ ++the_dep;
+
+ while(the_dep.end() && !pkg.end())
+ {
+ while(!pkg.end() && !(*apt_cache_file)[pkg].InstBroken())
+ ++pkg;
+
+ if(!pkg.end())
+ {
+ pkgCache::VerIterator ver=(*apt_cache_file)[pkg].InstVerIter(*apt_cache_file);
+
+ if(!ver.end())
+ the_dep=ver.DependsList();
+
+ while(!the_dep.end() &&
+ !the_dep.IsCritical() &&
+ ((*apt_cache_file)[the_dep] & pkgDepCache::DepGInstall))
+ ++the_dep;
+ }
+ }
+ }
+ public:
+ // Start from the given package (typically Head() or End()).
+ broken_dep_iterator(const pkgCache::PkgIterator &_pkg)
+ :pkg(_pkg)
+ {
+ if(!pkg.end())
+ {
+ pkgCache::VerIterator ver=(*apt_cache_file)[pkg].InstVerIter(*apt_cache_file);
+
+ if(!ver.end())
+ the_dep=ver.DependsList();
+ }
+
+ normalize();
+ }
+
+ aptitude_universe::dep operator*() const
+ {
+ return the_dep;
+ }
+
+ broken_dep_iterator &operator++()
+ {
+ assert(!pkg.end());
+ // If the_dep.end() we have pkg.end().
+ assert(!the_dep.end());
+
+ ++the_dep;
+ normalize();
+ return *this;
+ }
+
+ bool end() const
+ {
+ return pkg.end();
+ }
+ };
+
+ package_iterator packages_begin()
+ {
+ return (*apt_cache_file)->PkgBegin();
+ }
+
+ dep_iterator deps_begin()
+ {
+ return (*apt_cache_file)->PkgBegin();
+ }
+};
+
+typedef generic_problem_resolver<aptitude_universe> aptitude_resolver;
+
+#endif