[Aptitude-devel] r3031 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Thu, 21 Apr 2005 23:12:02 +0000
Author: dburrows
Date: Thu Apr 21 23:11:59 2005
New Revision: 3031
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Lift solutions out of the problem resolver so pointers to them
can be declared.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Thu Apr 21 23:11:59 2005
@@ -1,5 +1,11 @@
2005-04-21 Daniel Burrows <dburrows@debian.org>
+ * src/generic/problemresolver/problemresolver.h:
+
+ Lift the "solution" class out of the generic_problem_resolver
+ class so I can forward-declare it (and hence declare pointers
+ and references to it in aptcache.h).
+
* src/generic/aptitude_resolver.h:
Make the glue code functions static.
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 21 23:11:59 2005
@@ -78,6 +78,273 @@
class NoMoreSolutions:public ProblemResolverError {
};
+/** Represents a partial or complete solution to a dependency
+ * problem. Solutions are transparently refcounted to save on
+ * memory and avoid copies.
+ */
+template<class PackageUniverse>
+class generic_solution
+{
+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
+ {
+ version ver;
+
+ action() {}
+
+ action(const version &_ver):ver(_ver) {}
+
+ bool operator<(const action &other) const {return ver<other.ver;}
+ };
+
+private:
+ class solution_rep
+ {
+ /** The actions performed by this solution.
+ *
+ * Originally the plan was to read this off by tracing to the
+ * root -- but it seems likely that this will be read many more
+ * times than it's created, so I'm swallowing the space/time
+ * hit to build a lookup table at each node in the hope that it
+ * pays off later..
+ *
+ * Note that this also means you can't find out chronological
+ * ordering, which might help make sense of everything; that
+ * can be added in later one way or another, though. (eg,
+ * storing the DAG structure after all?)
+ */
+ std::map<package, action> actions;
+
+ /** The full list of currently broken dependencies. */
+ std::set<dep> broken_deps;
+
+ /** The score of this solution. */
+ int score;
+
+ /** The combined score due to package version installations
+ * and distance from the root -- "score" is calculated by
+ * adding the broken-dependency count to this.
+ */
+ int action_score;
+
+ /** The reference count of this solution. */
+ mutable unsigned int refcount;
+
+ public:
+ void incref() const {++refcount;}
+ void decref() const {assert(refcount>0); if(--refcount==0) delete this;}
+
+ /** Construct a new solution_rep. The initial reference count
+ * is \b 1.
+ *
+ * \param ver the version to install beyond what is in the parent
+ * \param parent the parent solution
+ * \param _broken_deps the dependencies that are broken in this partial solution
+ * \param _score the score of this solution
+ * \param _action_score the score not due to broken deps
+ */
+ solution_rep(const action &the_action,
+ const generic_solution &parent,
+ const std::set<dep> &_broken_deps,
+ int _score, int _action_score)
+ :actions(parent.get_actions()), broken_deps(_broken_deps),
+ score(_score), action_score(_action_score),
+ refcount(1)
+ {
+ assert(actions.find(the_action.ver.get_package()) == actions.end());
+ actions[the_action.ver.get_package()] = the_action;
+ }
+
+ /** Construct a solution with \b no action, the given set of
+ * broken dependencies, and the given score. Used to generate
+ * the root node of the search.
+ */
+ solution_rep(const std::set<dep> &_broken_deps,
+ int _score)
+ :broken_deps(_broken_deps), score(_score),
+ action_score(0), refcount(1)
+ {
+ }
+
+ const std::set<dep> &get_broken_deps() const
+ {
+ return broken_deps;
+ }
+
+ std::set<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;}
+
+ version version_of(const package &pkg) const
+ {
+ typename std::map<package, action>::const_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 package &pkg) const
+ {
+ return actions.find(pkg) != actions.end();
+ }
+ }; // End solution representation.
+
+ solution_rep *real_soln;
+public:
+ generic_solution():real_soln(0) {}
+
+ generic_solution(const action &a, const generic_solution &parent,
+ const std::set<dep> &broken_deps,
+ int score, int action_score)
+ :real_soln(new solution_rep(a, parent, broken_deps, score, action_score))
+ {
+ }
+
+ generic_solution(const std::set<dep> &broken_deps,
+ int score)
+ :real_soln(new solution_rep(broken_deps, score))
+ {
+ }
+
+ generic_solution(const generic_solution &other)
+ :real_soln(other.real_soln)
+ {
+ if(real_soln)
+ real_soln->incref();
+ }
+
+ ~generic_solution()
+ {
+ if(real_soln)
+ real_soln->decref();
+ }
+
+ generic_solution &operator=(const generic_solution &other)
+ {
+ if(other.real_soln)
+ other.real_soln->incref();
+ if(real_soln)
+ real_soln->decref();
+ real_soln=other.real_soln;
+
+ return *this;
+ }
+
+ /** \note solutions are compared by pointer identity, not by
+ * value.
+ *
+ * \return \b true if the solutions are the same solution.
+ */
+ bool operator==(const generic_solution &other) const
+ {
+ return &real_soln == &other.real_soln;
+ }
+
+ operator bool() const
+ {
+ return real_soln != 0;
+ }
+
+ const action &operator*() const
+ {
+ return real_soln->get_action();
+ }
+
+ const action *operator->() const
+ {
+ return &real_soln->get_action();
+ }
+
+ const generic_solution &get_parent() const
+ {
+ return real_soln->get_parent();
+ }
+
+ /** \return an immutable list of all the broken dependencies
+ * in this solution. The list will live at least as long as
+ * the reference from which it was retrieved.
+ */
+ const std::set<dep> &get_broken() const
+ {
+ return real_soln->get_broken_deps();
+ }
+
+ const std::map<package, action> &get_actions() const
+ {
+ return real_soln->get_actions();
+ }
+
+ /** \return the score of the scolution */
+ int get_score() const
+ {
+ return real_soln->get_score();
+ }
+
+ /** \return the score of the solution's actions. */
+ int get_action_score() const
+ {
+ return real_soln->get_action_score();
+ }
+
+ version version_of(const package &pkg) const
+ {
+ return real_soln->version_of(pkg);
+ }
+
+ bool package_modified(const package &pkg) const
+ {
+ return real_soln->package_modified(pkg);
+ }
+
+ void dump(std::ostream &out) const
+ {
+ out << "<";
+ for(typename std::map<package, action>::const_iterator i=get_actions().begin();
+ i!=get_actions().end(); ++i)
+ {
+ if(i!=get_actions().begin())
+ out << ", ";
+ out << i->first.get_name() << ":=" << i->second.ver.get_name();
+ }
+ out << ">;[";
+
+ for(typename std::set<dep>::const_iterator i=get_broken().begin();
+ i!=get_broken().end(); ++i)
+ {
+ if(i!=get_broken().begin())
+ std::cout << ", ";
+ std::cout << *i;
+ }
+
+ std::cout << "];" << get_score();
+ }
+}; // End solution wrapper
+
/** An exception indicating that the resolver ran out of time to
* find a solution.
*/
@@ -150,265 +417,10 @@
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
- {
- version ver;
-
- action() {}
-
- action(const version &_ver):ver(_ver) {}
-
- bool operator<(const action &other) const {return ver<other.ver;}
- };
-
- /** Represents a partial or complete solution to a dependency
- * problem. Solutions are transparently refcounted to save on
- * memory and avoid copies. (Q: is this worth the effort?)
- */
- class solution
- {
- class solution_rep
- {
- /** The actions performed by this solution.
- *
- * Originally the plan was to read this off by tracing to the
- * root -- but it seems likely that this will be read many more
- * times than it's created, so I'm swallowing the space/time
- * hit to build a lookup table at each node in the hope that it
- * pays off later..
- *
- * Note that this also means you can't find out chronological
- * ordering, which might help make sense of everything; that
- * can be added in later one way or another, though. (eg,
- * storing the DAG structure after all?)
- */
- std::map<package, action> actions;
-
- /** The full list of currently broken dependencies. */
- std::set<dep> broken_deps;
-
- /** The score of this solution. */
- int score;
-
- /** The combined score due to package version installations
- * and distance from the root -- "score" is calculated by
- * adding the broken-dependency count to this.
- */
- int action_score;
-
- /** The reference count of this solution. */
- mutable unsigned int refcount;
-
- public:
- void incref() const {++refcount;}
- void decref() const {assert(refcount>0); if(--refcount==0) delete this;}
-
- /** Construct a new solution_rep. The initial reference count
- * is \b 1.
- *
- * \param ver the version to install beyond what is in the parent
- * \param parent the parent solution
- * \param _broken_deps the dependencies that are broken in this partial solution
- * \param _score the score of this solution
- * \param _action_score the score not due to broken deps
- */
- solution_rep(const action &the_action,
- const solution &parent,
- const std::set<dep> &_broken_deps,
- int _score, int _action_score)
- :actions(parent.get_actions()), broken_deps(_broken_deps),
- score(_score), action_score(_action_score),
- refcount(1)
- {
- assert(actions.find(the_action.ver.get_package()) == actions.end());
- actions[the_action.ver.get_package()] = the_action;
- }
-
- /** Construct a solution with \b no action, the given set of
- * broken dependencies, and the given score. Used to generate
- * the root node of the search.
- */
- solution_rep(const std::set<dep> &_broken_deps,
- int _score)
- :broken_deps(_broken_deps), score(_score),
- action_score(0), refcount(1)
- {
- }
-
- const std::set<dep> &get_broken_deps() const
- {
- return broken_deps;
- }
-
- std::set<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;}
-
- version version_of(const package &pkg) const
- {
- typename std::map<package, action>::const_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 package &pkg) const
- {
- return actions.find(pkg) != actions.end();
- }
- }; // End solution representation.
-
- solution_rep *real_soln;
- public:
- solution():real_soln(0) {}
-
- solution(const action &a, const solution &parent,
- const std::set<dep> &broken_deps,
- int score, int action_score)
- :real_soln(new solution_rep(a, parent, broken_deps, score, action_score))
- {
- }
-
- solution(const std::set<dep> &broken_deps,
- int score)
- :real_soln(new solution_rep(broken_deps, score))
- {
- }
-
- solution(const solution &other)
- :real_soln(other.real_soln)
- {
- if(real_soln)
- real_soln->incref();
- }
-
- ~solution()
- {
- if(real_soln)
- real_soln->decref();
- }
-
- solution &operator=(const solution &other)
- {
- if(other.real_soln)
- other.real_soln->incref();
- if(real_soln)
- real_soln->decref();
- real_soln=other.real_soln;
-
- return *this;
- }
-
- /** \note solutions are compared by pointer identity, not by
- * value.
- *
- * \return \b true if the solutions are the same solution.
- */
- bool operator==(const solution &other) const
- {
- return &real_soln == &other.real_soln;
- }
-
- operator bool() const
- {
- return real_soln != 0;
- }
-
- const action &operator*() const
- {
- return real_soln->get_action();
- }
-
- const action *operator->() const
- {
- return &real_soln->get_action();
- }
-
- const solution &get_parent() const
- {
- return real_soln->get_parent();
- }
+ typedef generic_solution<PackageUniverse> solution;
- /** \return an immutable list of all the broken dependencies
- * in this solution. The list will live at least as long as
- * the reference from which it was retrieved.
- */
- const std::set<dep> &get_broken() const
- {
- return real_soln->get_broken_deps();
- }
-
- const std::map<package, action> &get_actions() const
- {
- return real_soln->get_actions();
- }
+ typedef typename solution::action action;
- /** \return the score of the scolution */
- int get_score() const
- {
- return real_soln->get_score();
- }
-
- /** \return the score of the solution's actions. */
- int get_action_score() const
- {
- return real_soln->get_action_score();
- }
-
- version version_of(const package &pkg) const
- {
- return real_soln->version_of(pkg);
- }
-
- bool package_modified(const package &pkg) const
- {
- return real_soln->package_modified(pkg);
- }
-
- void dump(std::ostream &out) const
- {
- out << "<";
- for(typename std::map<package, action>::const_iterator i=get_actions().begin();
- i!=get_actions().end(); ++i)
- {
- if(i!=get_actions().begin())
- out << ", ";
- out << i->first.get_name() << ":=" << i->second.ver.get_name();
- }
- out << ">;[";
-
- for(typename std::set<dep>::const_iterator i=get_broken().begin();
- i!=get_broken().end(); ++i)
- {
- if(i!=get_broken().begin())
- std::cout << ", ";
- std::cout << *i;
- }
-
- std::cout << "];" << get_score();
- }
- }; // End solution wrapper
private:
/** Compares solutions according to their "goodness". */
struct solution_goodness_compare