[Aptitude-devel] r2935 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Thu, 07 Apr 2005 21:44:28 +0000
Author: dburrows
Date: Thu Apr 7 21:44:24 2005
New Revision: 2935
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc
Log:
First compilable draft of the resolver.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Thu Apr 7 21:44:24 2005
@@ -1,5 +1,11 @@
2005-04-07 Daniel Burrows <dburrows@debian.org>
+ * src/generic/problemresolver/problemresolver.h, src/generic/problemresolver/test.cc:
+
+ Complete and compile the resolver ...... theoretically.
+ Now it's time to watch it run reallllly sloowwwly
+ and produce stoopid answers.
+
* src/generic/problemresolver/problemresolver.h:
Start work on a currently broken problem resolver.
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 Thu Apr 7 21:44:24 2005
@@ -39,6 +39,11 @@
#ifndef PROBLEMRESOLVER_H
#define PROBLEMRESOLVER_H
+#include <map>
+#include <queue>
+#include <set>
+#include <vector>
+
/** \defgroup problemresolver Aptitude's problem resolver
*
* This is a replacement for the generic apt problem resolver. It
@@ -55,7 +60,7 @@
* problem resolver will try to keep it on the system (or, for
* negative scores, to remove it from the system). The sum of all
* installed package's scores is used as a heuristic in a directed
- * search of the solution space (see aptitude_problem_resolver's
+ * search of the solution space (see generic_problem_resolver's
* documentation for the interface and its documentation for the gory
* details).
*/
@@ -103,21 +108,22 @@
*
* PackageUniverse::package is the representation of a package; the
* main interesting thing about packages is that they have lists of
- * versions. Packages can be compared with ==, they have unique
- * numerical IDs, and PackageUniverse::package::version_iterator
- * lets you iterate from p.versions_begin() to p.versions_end();
- * dereferencing the iterator results in a PackageUniverse::version.
+ * versions. Packages can be compared with == and <, they have
+ * unique numerical IDs, and
+ * PackageUniverse::package::version_iterator lets you iterate from
+ * p.versions_begin() to p.versions_end(); dereferencing the iterator
+ * results in a PackageUniverse::version.
*
* A PackageUniverse::version is the object upon which dependencies
- * operate. Given a PackageUniverse::version, you can retrieve its
- * corresponding package, or get a PU::version::revdep_iterator
- * to iterate from v.revdeps_begin() to v.revdeps_end().
- * Dereferencing this iterator gives you a PU::dep.
+ * operate. Given a PackageUniverse::version, you can compare it
+ * with == and <, retrieve its corresponding package, or get a
+ * PU::version::revdep_iterator to iterate from v.revdeps_begin() to
+ * v.revdeps_end(). Dereferencing this iterator gives you a PU::dep.
*
* A PU::dep is a dependency of the form "A -> B | C | ...". Given a
- * dep, you can retrieve A with d.get_source_version(), and retrieve
- * a PU::dep::solvers_iterator with
- * d.solvers_begin()/d.solvers_end(). \todo add a function to
+ * dep, you can compare it with ==, retrieve A with
+ * d.get_source_version(), and retrieve a PU::dep::solvers_iterator
+ * with d.solvers_begin()/d.solvers_end(). \todo add a function to
* efficiently test whether a dep is satisfied using information
* available at the concrete package system level.
*
@@ -127,15 +133,19 @@
template<class PackageUniverse>
-class aptitude_problem_resolver
+class generic_problem_resolver
{
public:
+ typedef typename PackageUniverse::package package;
+ typedef typename PackageUniverse::version version;
+ typedef typename PackageUniverse::dep dep;
+
/** Represents a single action taken by the resolver: the
* installation of a particular version of a package.
*/
struct action
{
- PackageUniverse::version ver;
+ version ver;
bool operator<(const action &other) {return ver<other.ver;}
};
@@ -148,12 +158,6 @@
{
class solution_rep
{
- static bool operator<(const PackageUniverse::package &a,
- const PackageUniverse::package &b)
- {
- return a.get_id() < b.get_id();
- }
-
/** The actions performed by this solution.
*
* Originally the plan was to read this off by tracing to the
@@ -167,10 +171,10 @@
* can be added in later one way or another, though. (eg,
* storing the DAG structure after all?)
*/
- map<PackageUniverse::package, action> my_actions;
+ std::map<package, action> actions;
/** The full list of currently broken dependencies. */
- vector<PackageUniverse::dep> broken_deps;
+ std::vector<dep> broken_deps;
/** The reference count of this solution. */
mutable unsigned int refcount;
@@ -196,50 +200,60 @@
* \param _score the score of this solution
* \param _action_score the score not due to broken deps
*/
- solution_rep(const PackageUniverse::version &ver,
+ solution_rep(const version &ver,
const solution &parent,
int _score, int _action_score)
- :my_action(parent.my_action), refcount(1),
+ :actions(parent.actions), refcount(1),
score(_score), action_score(_action_score)
{
- assert(my_action.find(ver.get_package()) == my_action.end());
- my_action[ver.get_package()] = action(ver);
+ assert(actions.find(ver.get_package()) == actions.end());
+ actions[ver.get_package()] = action(ver);
}
- const vector<PackageUniverse::dep> &get_broken_deps() const
+ const std::vector<dep> &get_broken_deps() const
{
return broken_deps;
}
- vector<PackageUniverse::dep> &get_broken_deps()
+ std::vector<dep> &get_broken_deps()
{
return broken_deps;
}
+ const std::map<package, action> &get_actions() const
+ {
+ return actions;
+ }
+
+ std::map<package, action> &get_actions()
+ {
+ return actions;
+ }
+
const action &get_action() {return my_action;}
int get_score() const {return score;}
int get_action_score() const {return action_score;}
- PackageUniverse::version version_of(const PackageUniverse::package &pkg) const
+ version version_of(const package &pkg) const
{
- map<action>::iterator found=my_actions.find(pkg);
- if(found == my_actions.end())
+ typename std::map<package, action>::iterator found=actions.find(pkg);
+ if(found == actions.end())
return pkg.current_version();
else
return found->second.ver;
}
/** \return true iff this solution touches the given package. */
- bool package_modified(const PackageUniverse::package &pkg) const
+ bool package_modified(const package &pkg) const
{
- return my_actions.find(pkg) != my_actions.end();
+ return actions.find(pkg) != actions.end();
}
}; // End solution representation.
solution_rep *real_soln;
public:
- solution():real_soln=0;
+ solution():real_soln(0) {}
solution(const action &a, const solution &parent,
int score, int action_score)
@@ -273,7 +287,7 @@
return &real_soln == &other.real_soln;
}
- bool operator bool() const
+ operator bool() const
{
return real_soln != 0;
}
@@ -297,7 +311,7 @@
* in this solution. The list will live at least as long
* as the reference from which it was retrieved.
*/
- vector<PackageUniverse::dep> get_broken()
+ std::vector<dep> get_broken()
{
return real_soln->get_broken_deps();
}
@@ -306,7 +320,7 @@
* in this solution. The list will live at least as long as
* the reference from which it was retrieved.
*/
- const vector<PackageUniverse::dep> get_broken() const
+ const std::vector<dep> get_broken() const
{
return real_soln->get_broken_deps();
}
@@ -323,33 +337,68 @@
return real_soln->get_action_score();
}
- PackageUniverse::version version_of(PackageUniverse::package &pkg)
+ version version_of(package &pkg)
{
return real_soln->version_of(pkg);
}
- bool package_modified(PackageUniverse::package &pkg)
+ bool package_modified(package &pkg)
{
return real_soln->package_modified(pkg);
}
}; // End solution wrapper
private:
- /** A closure whose purpose is to compare two solutions. */
- struct solution_compare
+ /** Compares solutions according to their "goodness". */
+ struct solution_goodness_compare
{
- /** The problem resolver for which solutions are being
- * compared (i.e., "this").
- */
- const aptitude_problem_resolver &resolver;
-
- solution_compare(const aptitude_problem_resolver &_resolver) const
- :resolver(_resolver)
+ bool operator()(const solution &s1, const solution &s2) const
{
+ // Solutions that solve *all* dependencies always score higher
+ // than those that don't; guarantees we deal with them
+ // immediately (but in order of goodness).
+ if(s1.get_broken().empty() && !s2.get_broken().empty())
+ return false;
+ if(s2.get_broken().empty() && !s1.get_broken().empty())
+ return true;
+
+ // If both are either non-final or final solutions, compare
+ // scores.
+ return s1.get_score() < s2.get_score();
}
+ };
+ /** Compares solutions according to their contents; used to
+ * manage "closed".
+ */
+ struct solution_contents_compare
+ {
bool operator()(const solution &s1, const solution &s2) const
{
- return s1.get_score() < s2.get_score();
+ // Variation on orthographic sort.
+ //
+ // S1 < S2 if
+ // - S1(p)=S2(p) for all p<p' and S1(p')<S2(p'), where
+ // p,p' \in \dom(S1) \cup dom(S2)
+ typename std::map<package,version>::const_iterator i1,i2;
+ const std::map<package,version>
+ &a1=s1.get_actions(), &a2=s2.get_actions();
+
+ i1=a1.begin();
+ i2=a2.begin();
+
+ while(i1!=a1.end() && i2!=a2.end())
+ {
+ if(i1->first == i2->first && i1->second != i2->second)
+ return i1->second < i2->second;
+ else if(i1->first < i2->first)
+ return i1->second < i2->first.get_current_version();
+ else
+ return i1->first.get_current_version() < i2->second;
+ }
+
+ // If they have unequal lengths, the longer one is considered
+ // larger.
+ return i2 != a2.end();
}
};
@@ -367,14 +416,17 @@
int *version_score;
/** The working queue: */
- priority_queue<solution, vector<solution>, solution_compare> q;
+ std::priority_queue<solution, std::vector<solution>, solution_goodness_compare> open;
+
+ /** 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.
*/
bool ver_installed(const solution &s,
- const PackageUniverse::version &add_ver,
- const PackageUniverse::version &test_ver)
+ const version &add_ver,
+ const version &test_ver)
{
if(add_ver.get_package() == test_ver.get_package())
return add_ver == test_ver;
@@ -386,13 +438,13 @@
* single-version installation.
*/
bool dep_broken(const solution &s,
- const PackageUniverse::version &v,
- const PackageUniverse::dep &d)
+ const version &v,
+ const dep &d)
{
if(!ver_installed(s, v, d.get_source_version()))
return false;
- for(PackageUniverse::dep::solvers_iterator i=d.solvers_begin();
+ for(typename dep::solver_iterator i=d.solvers_begin();
i!=d.solvers_end(); ++i)
{
if(ver_installed(s, v, *i))
@@ -406,9 +458,9 @@
* installing the given package version.
*/
void try_install(const solution &s,
- const PackageUniverse::version &v)
+ const version &v)
{
- PackageUniverse::version old_version=s.version_of(v.get_package());
+ version old_version=s.version_of(v.get_package());
assert(old_version == v.get_package().get_current_version() &&
old_version != v);
@@ -419,7 +471,7 @@
new_action_score+=version_scores[v.get_id()];
new_action_score-=version_scores[v.get_package().current_version().get_id()];
- vector<PackageUniverse::dep> new_broken;
+ std::vector<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?
// For instance, by keeping a cache of already-examined deps.
@@ -432,18 +484,18 @@
// hand, if lots of deps are broken, we might have problems
// anyway. Just plowing ahead for now.
- for(PackageUniverse::version::revdep_iterator rd=orig_version.revdeps_begin();
+ for(typename version::revdep_iterator rd=orig_version.revdeps_begin();
rd!=orig_version.revdeps_end(); ++rd)
if(dep_broken(s, v, *rd))
new_broken.push_back(*rd);
- for(PackageUniverse::version::revdep_iterator rd=v.revdeps_begin();
+ for(typename version::revdep_iterator rd=v.revdeps_begin();
rd!=v.revdeps_end(); ++rd)
if(dep_broken(s, v, *rd))
new_broken.push_back(*rd);
- const vector<PackageUniverse::dep> &old_broken=s.get_broken_deps();
- for(vector<PackageUniverse::dep>::const_iterator bd=old_broken.begin();
+ const std::vector<dep> &old_broken=s.get_broken_deps();
+ for(typename std::vector<dep>::const_iterator bd=old_broken.begin();
bd!=old_broken.end(); ++bd)
if(dep_broken(s, v, *bd))
new_broken.push_back(*bd);
@@ -457,11 +509,11 @@
* dependency of the given solution.
*/
void generate_successors(const solution &s,
- const PackageUniverse::dep &d)
+ const dep &d)
{
- PackageUniverse::version source_version=d.get_source_version();
- PackageUniverse::package source_package=source_version.get_package();
- PackageUniverse::version sol_version=s.version_of(source_package);
+ version source_version=d.get_source_version();
+ package source_package=source_version.get_package();
+ version sol_version=s.version_of(source_package);
// If the source of the dependency was not modified and is
// presently installed, try installing a different version.
@@ -469,7 +521,7 @@
{
if(source_version == source_package.current_version())
{
- for(PackageUniverse::package::version_iterator vi=source_package.versions_begin();
+ for(typename package::version_iterator vi=source_package.versions_begin();
vi!=source_package.versions_end(); ++vi)
try_install(s, *v);
}
@@ -478,7 +530,7 @@
// dep is known broken). Enqueue each potential solution.
else
{
- for(PackageUniverse::dep::solvers_iterator si=d.solvers_begin();
+ for(typename dep::solvers_iterator si=d.solvers_begin();
si!=d.solvers_end(); ++si)
try_install(s, *si);
}
@@ -489,17 +541,19 @@
*/
void process_solution(const solution &s)
{
-
+ for(typename std::vector<dep>::const_iterator bi=s.get_broken().begin();
+ bi!=s.get_broken().end(); ++bi)
+ generate_successors(s, *bi);
}
public:
- /** Construct a new aptitude_problem_resolver.
+ /** Construct a new generic_problem_resolver.
*
* \param _step_penalty the penalty per "step" of a (partial) solution.
* \param _broken_penalty the penalty per broken dependency of a (partial) solution.
* \param _universe the universe in which we are working.
*/
- aptitude_problem_resolver(int step_penalty, int broken_penalty,
+ generic_problem_resolver(int step_penalty, int broken_penalty,
const PackageUniverse &_universe)
:step_score(-step_penalty), broken_score(-broken_penalty),
universe(_universe)
@@ -509,7 +563,7 @@
version_penalty[i]=0;
}
- ~aptitude_problem_resolver()
+ ~generic_problem_resolver()
{
delete[] version_penalty;
}
@@ -519,8 +573,7 @@
* result in a bias towards that version appearing in the final
* solution.
*/
- void set_version_score(PackageUniverse::version &ver,
- int score)
+ void set_version_score(version &ver, int score)
{
version_scores[ver.get_id()]=score;
}
@@ -528,8 +581,7 @@
/** As set_version_score, but instead of replacing the current score
* increment it.
*/
- void add_version_score(PackageUniverse::version &ver,
- int score)
+ void add_version_score(version &ver, int score)
{
version_score[ver.get_id()]+=score;
}
@@ -550,12 +602,21 @@
*
* \param max_steps the maximum number of solutions to test.
*
- * \return a partial solution
+ * \return a solution that fixes all broken dependencies
*
* \throws NoMoreSolutions if the potential solution list is exhausted.
* \throws NoMoreTime if no solution is found within max_steps steps.
+ *
+ * \todo when throwing NoMoreSolutions or NoMoreTime, maybe we
+ * should include the "least broken" solution seen.
*/
-
+ solution find_next_solution(unsigned int max_steps)
+ {
+ while(max_steps>0)
+ {
+
+ }
+ }
};
#endif
Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc (original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/test.cc Thu Apr 7 21:44:24 2005
@@ -88,6 +88,11 @@
return this != &other;
}
+ bool operator<(const dummy_package &other) const
+ {
+ return ID < other.ID;
+ }
+
void add_version(dummy_version *version)
{
versions.push_back(version);
@@ -168,6 +173,11 @@
return this != &other;
}
+ bool operator<(const dummy_version &other) const
+ {
+ return ID < other.ID;
+ }
+
void add_revdep(dummy_dep *dep)
{
revdeps.push_back(dep);
@@ -209,25 +219,25 @@
public:
// I want to keep the interface free of pointers so that I can
// easily plug in an APT-based interface later.
- class target_iterator
+ class solver_iterator
{
vector<dummy_version *>::const_iterator realiter;
public:
- target_iterator(const vector<dummy_version *>::const_iterator &_realiter):realiter(_realiter) {}
+ solver_iterator(const vector<dummy_version *>::const_iterator &_realiter):realiter(_realiter) {}
const dummy_version &operator*() {return **realiter;}
const dummy_version *operator->() {return *realiter;}
- target_iterator &operator++()
+ solver_iterator &operator++()
{
++realiter;
return *this;
}
- bool operator==(const target_iterator &other)
+ bool operator==(const solver_iterator &other)
{
return realiter==other.realiter;
}
- bool operator!=(const target_iterator &other)
+ bool operator!=(const solver_iterator &other)
{
return realiter!=other.realiter;
}
@@ -251,11 +261,11 @@
const dummy_version &get_source() const {return *source;}
- target_iterator target_begin() const
+ solver_iterator solvers_begin() const
{
return target_set.begin();
}
- target_iterator target_end() const
+ solver_iterator solvers_end() const
{
return target_set.end();
}
@@ -373,6 +383,7 @@
}
};
+typedef generic_problem_resolver<dummy_universe> dummy_resolver;
// To make things easier, the tests are specified as plaintext files.
// The syntax is quite simple: it consists of whitespace-separated
@@ -537,8 +548,8 @@
out << "DEP " << sp.get_name() << " " << sv.get_name() << " < ";
- for(dummy_universe::dep::target_iterator t=(*d)->target_begin();
- t!=(*d)->target_end(); ++t)
+ for(dummy_universe::dep::solver_iterator t=(*d)->solvers_begin();
+ t!=(*d)->solvers_end(); ++t)
{
out << " " << t->get_package().get_name() << " " << t->get_name() << " ";
}