[Aptitude-devel] r2934 - branches/aptitude-0.3/aptitude/src/generic/problemresolver

[Daniel Burrows]

Author: dburrows
Date: Thu Apr  7 17:19:28 2005
New Revision: 2934

Modified:
   branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Further work towards the new problem resolver, including
more concrete documentation of just what I expect the package
universe to provide.

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 17:19:28 2005
@@ -100,6 +100,29 @@
  *    - a penalty is applied for broken (strong) dependencies.
  *      This aims at directing the search towards "less broken"
  *      situations.
+ *
+ *  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.
+ *
+ *  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.
+ *
+ *  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
+ *  efficiently test whether a dep is satisfied using information
+ *  available at the concrete package system level.
+ *
+ *  A PU::dep::solvers_iterator iterates over the list B,C,... above.
+ *  Dereferencing it returns a ver_iterator.
  */
 
 
@@ -369,23 +392,21 @@
     if(!ver_installed(s, v, d.get_source_version()))
       return false;
 
-    for(PackageUniverse::dep::target_iterator i=d.targets_begin();
-	i!=d.targets_end(); ++i)
+    for(PackageUniverse::dep::solvers_iterator i=d.solvers_begin();
+	i!=d.solvers_end(); ++i)
       {
-	PackageUniverse::package p=i.get_package();
-
-	if(i.satisfied_by(v.get_package() == p ? v : s.version_of(p)))
+	if(ver_installed(s, v, *i))
 	  return false;
       }
 
     return true;
   }
 
-  /** Generates a single successor node to the given solution by
+  /** Enqueues a single successor node to the given solution by
    *  installing the given package version.
    */
-  void do_install(const solution &s,
-		  const PackageUniverse::version &v)
+  void try_install(const solution &s,
+		   const PackageUniverse::version &v)
   {
     PackageUniverse::version old_version=s.version_of(v.get_package());
 
@@ -402,15 +423,34 @@
     // 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.
+    // Note that for the old version we only care about Depends and
+    // for the new we only care about Conflicts...but it's not clear
+    // that information can really be used in any good way (aside from
+    // satisfied_by()).
     //
     // 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.
 
-    for(PackageUniverse::version::revdep_iterator rd=v.revdeps_begin();
+    for(PackageUniverse::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();
+	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();
+	bd!=old_broken.end(); ++bd)
+      if(dep_broken(s, v, *bd))
+	new_broken.push_back(*bd);
+
+    q.enqueue(solution(action(v), s,
+		       action_score+broken_score*new_broken.size(),
+		       action_score));
   }
 
   /** Generates (and enqueues) successor nodes for the given broken
@@ -419,9 +459,29 @@
   void generate_successors(const solution &s,
 			   const PackageUniverse::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);
+
     // If the source of the dependency was not modified and is
     // presently installed, try installing a different version.
-    PackageUniverse::
+    if(sol_version==source_version)
+      {
+	if(source_version == source_package.current_version())
+	  {
+	    for(PackageUniverse::package::version_iterator vi=source_package.versions_begin();
+		vi!=source_package.versions_end(); ++vi)
+	      try_install(s, *v);
+	  }
+      }
+    // Ok, the LHS *is* satisfied; hence the RHS must fail (since the
+    // dep is known broken).  Enqueue each potential solution.
+    else
+      {
+	for(PackageUniverse::dep::solvers_iterator si=d.solvers_begin();
+	    si!=d.solvers_end(); ++si)
+	  try_install(s, *si);
+      }
   }
 
   /** Processes the given solution by enqueuing its successor nodes