* Implement EDSP in libapt-pkg so that all front-ends which

  use the internal resolver can now be used also with external
  ones as the usage is hidden in between the old API
* provide two edsp solvers in apt-utils:
  - 'dump' to quickly output a complete scenario and
  - 'apt' to use the internal as an external resolver

21 files changed, 1279 insertions, 41 deletions

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index 2dae4258a..6f1f82d50 100644
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -20,12 +20,15 @@
 #include <apt-pkg/version.h>
 #include <apt-pkg/sptr.h>
 #include <apt-pkg/acquire-item.h>
-    
+#include <apt-pkg/edsp.h>
+
 #include <apti18n.h>
 #include <sys/types.h>
 #include <cstdlib>
 #include <algorithm>
 #include <iostream>
+
+#include <stdio.h>
 									/*}}}*/
 using namespace std;
 
@@ -327,6 +330,12 @@ bool pkgFixBroken(pkgDepCache &Cache)
  */
 bool pkgDistUpgrade(pkgDepCache &Cache)
 {
+   std::string const solver = _config->Find("APT::Solver::Name", "internal");
+   if (solver != "internal") {
+      OpTextProgress Prog(*_config);
+      return EDSP::ResolveExternal(solver.c_str(), Cache, false, true, false, &Prog);
+   }
+
    pkgDepCache::ActionGroup group(Cache);
 
    /* Upgrade all installed packages first without autoinst to help the resolver
@@ -379,6 +388,12 @@ bool pkgDistUpgrade(pkgDepCache &Cache)
    to install packages not marked for install */
 bool pkgAllUpgrade(pkgDepCache &Cache)
 {
+   std::string const solver = _config->Find("APT::Solver::Name", "internal");
+   if (solver != "internal") {
+      OpTextProgress Prog(*_config);
+      return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
+   }
+
    pkgDepCache::ActionGroup group(Cache);
 
    pkgProblemResolver Fix(&Cache);
@@ -725,7 +740,20 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
    return true;
 }
 									/*}}}*/
-// ProblemResolver::Resolve - Run the resolution pass			/*{{{*/
+// ProblemResolver::Resolve - calls a resolver to fix the situation	/*{{{*/
+// ---------------------------------------------------------------------
+/* */
+bool pkgProblemResolver::Resolve(bool BrokenFix)
+{
+   std::string const solver = _config->Find("APT::Solver::Name", "internal");
+   if (solver != "internal") {
+      OpTextProgress Prog(*_config);
+      return EDSP::ResolveExternal(solver.c_str(), Cache, false, false, false, &Prog);
+   }
+   return ResolveInternal(BrokenFix);
+}
+									/*}}}*/
+// ProblemResolver::ResolveInternal - Run the resolution pass		/*{{{*/
 // ---------------------------------------------------------------------
 /* This routines works by calculating a score for each package. The score
    is derived by considering the package's priority and all reverse 
@@ -739,12 +767,10 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
  
    The BrokenFix flag enables a mode where the algorithm tries to 
    upgrade packages to advoid problems. */
-bool pkgProblemResolver::Resolve(bool BrokenFix)
+bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 {
    pkgDepCache::ActionGroup group(Cache);
 
-   unsigned long Size = Cache.Head().PackageCount;
-
    // Record which packages are marked for install
    bool Again = false;
    do
@@ -774,7 +800,9 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
       clog << "Starting" << endl;
    
    MakeScores();
-   
+
+   unsigned long const Size = Cache.Head().PackageCount;
+
    /* We have to order the packages so that the broken fixing pass 
       operates from highest score to lowest. This prevents problems when
       high score packages cause the removal of lower score packages that
@@ -1183,6 +1211,21 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
    system was non-broken previously. */
 bool pkgProblemResolver::ResolveByKeep()
 {
+   std::string const solver = _config->Find("APT::Solver::Name", "internal");
+   if (solver != "internal") {
+      OpTextProgress Prog(*_config);
+      return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
+   }
+   return ResolveByKeepInternal();
+}
+									/*}}}*/
+// ProblemResolver::ResolveByKeepInternal - Resolve problems using keep	/*{{{*/
+// ---------------------------------------------------------------------
+/* This is the work horse of the soft upgrade routine. It is very gental
+   in that it does not install or remove any packages. It is assumed that the
+   system was non-broken previously. */
+bool pkgProblemResolver::ResolveByKeepInternal()
+{
    pkgDepCache::ActionGroup group(Cache);
 
    unsigned long Size = Cache.Head().PackageCount;
diff --git a/apt-pkg/algorithms.h b/apt-pkg/algorithms.h
index ebe31cc10..582cbc527 100644
--- a/apt-pkg/algorithms.h
+++ b/apt-pkg/algorithms.h
@@ -105,6 +105,9 @@ class pkgProblemResolver						/*{{{*/
 
    void MakeScores();
    bool DoUpgrade(pkgCache::PkgIterator Pkg);
+
+   bool ResolveInternal(bool const BrokenFix = false);
+   bool ResolveByKeepInternal();
    
    public:
    
diff --git a/apt-pkg/contrib/progress.cc b/apt-pkg/contrib/progress.cc
index 45e81edcb..84ee4c124 100644
--- a/apt-pkg/contrib/progress.cc
+++ b/apt-pkg/contrib/progress.cc
@@ -65,27 +65,18 @@ void OpProgress::OverallProgress(unsigned long Current, unsigned long Total,
 // OpProgress::SubProgress - Set the sub progress state			/*{{{*/
 // ---------------------------------------------------------------------
 /* */
-void OpProgress::SubProgress(unsigned long SubTotal,const string &Op)
+void OpProgress::SubProgress(unsigned long SubTotal,const string &Op,
+			     float const Percent)
 {
    this->SubTotal = SubTotal;
-   SubOp = Op;
-   if (Total == 0)
-      Percent = 0;
+   if (Op.empty() == false)
+      SubOp = Op;
+   if (Total == 0 || Percent == 0)
+      this->Percent = 0;
+   else if (Percent != -1)
+      this->Percent = this->Current += (Size*Percent)/SubTotal;
    else
-      Percent = Current*100.0/Total;
-   Update();
-}
-									/*}}}*/
-// OpProgress::SubProgress - Set the sub progress state			/*{{{*/
-// ---------------------------------------------------------------------
-/* */
-void OpProgress::SubProgress(unsigned long SubTotal)
-{
-   this->SubTotal = SubTotal;
-   if (Total == 0)
-      Percent = 0;
-   else
-      Percent = Current*100.0/Total;
+      this->Percent = Current*100.0/Total;
    Update();
 }
 									/*}}}*/
diff --git a/apt-pkg/contrib/progress.h b/apt-pkg/contrib/progress.h
index 7dd004f7e..3a914d17f 100644
--- a/apt-pkg/contrib/progress.h
+++ b/apt-pkg/contrib/progress.h
@@ -55,8 +55,7 @@ class OpProgress
    public:
    
    void Progress(unsigned long Current);
-   void SubProgress(unsigned long SubTotal);
-   void SubProgress(unsigned long SubTotal,const string &Op);
+   void SubProgress(unsigned long SubTotal, const string &Op = "", float const Percent = -1);
    void OverallProgress(unsigned long Current,unsigned long Total,
 			unsigned long Size,const string &Op);
    virtual void Done() {};
diff --git a/apt-pkg/deb/debindexfile.h b/apt-pkg/deb/debindexfile.h
index b5085992d..6697c5f26 100644
--- a/apt-pkg/deb/debindexfile.h
+++ b/apt-pkg/deb/debindexfile.h
@@ -22,8 +22,9 @@
 
 class debStatusIndex : public pkgIndexFile
 {
+   protected:
    string File;
-   
+
    public:
 
    virtual const Type *GetType() const;
@@ -36,6 +37,7 @@ class debStatusIndex : public pkgIndexFile
    virtual bool HasPackages() const {return true;};
    virtual unsigned long Size() const;
    virtual bool Merge(pkgCacheGenerator &Gen,OpProgress *Prog) const;
+   bool Merge(pkgCacheGenerator &Gen,OpProgress *Prog, unsigned long const Flag) const;
    virtual pkgCache::PkgFileIterator FindInCache(pkgCache &Cache) const;
 
    debStatusIndex(string File);
diff --git a/apt-pkg/deb/deblistparser.h b/apt-pkg/deb/deblistparser.h
index d62ce641c..8b8aff788 100644
--- a/apt-pkg/deb/deblistparser.h
+++ b/apt-pkg/deb/deblistparser.h
@@ -25,9 +25,9 @@ class debListParser : public pkgCacheGenerator::ListParser
       const char *Str;
       unsigned char Val;
    };
-   
-   private:
-   
+
+   protected:
+
    pkgTagFile Tags;
    pkgTagSection Section;
    unsigned long iOffset;
@@ -36,7 +36,7 @@ class debListParser : public pkgCacheGenerator::ListParser
    bool MultiArchEnabled;
 
    unsigned long UniqFindTagWrite(const char *Tag);
-   bool ParseStatus(pkgCache::PkgIterator &Pkg,pkgCache::VerIterator &Ver);
+   virtual bool ParseStatus(pkgCache::PkgIterator &Pkg,pkgCache::VerIterator &Ver);
    bool ParseDepends(pkgCache::VerIterator &Ver,const char *Tag,
 		     unsigned int Type);
    bool ParseProvides(pkgCache::VerIterator &Ver);
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index e9fa097aa..5cb68804d 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -1046,7 +1046,7 @@ void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
    Update(Pkg);
    AddSizes(Pkg);
 
-   if (AutoInst == false)
+   if (AutoInst == false || _config->Find("APT::Solver::Name", "internal") != "internal")
       return;
 
    if (DebugMarker == true)
@@ -1574,6 +1574,12 @@ bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
    return false;
 }
 									/*}}}*/
+// Policy::GetPriority - Get the priority of the package pin		/*{{{*/
+signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &Pkg)
+{ return 0; };
+signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &File)
+{ return 0; };
+									/*}}}*/
 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()		/*{{{*/
 {
   DefaultRootSetFunc *f = new DefaultRootSetFunc;
@@ -1599,6 +1605,9 @@ bool pkgDepCache::MarkFollowsSuggests()
 // pkgDepCache::MarkRequired - the main mark algorithm			/*{{{*/
 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 {
+   if (_config->Find("APT::Solver::Name", "internal") != "internal")
+      return true;
+
    bool follow_recommends;
    bool follow_suggests;
    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h
index 750da3d6f..f95ad9a14 100644
--- a/apt-pkg/depcache.h
+++ b/apt-pkg/depcache.h
@@ -232,6 +232,7 @@ class pkgDepCache : protected pkgCache::Namespace
       inline bool NewInstall() const {return Status == 2 && Mode == ModeInstall;};
       inline bool Delete() const {return Mode == ModeDelete;};
       inline bool Keep() const {return Mode == ModeKeep;};
+      inline bool Protect() const {return (iFlags & Protected) == Protected;};
       inline bool Upgrade() const {return Status > 0 && Mode == ModeInstall;};
       inline bool Upgradable() const {return Status >= 1;};
       inline bool Downgrade() const {return Status < 0 && Mode == ModeInstall;};
@@ -258,7 +259,9 @@ class pkgDepCache : protected pkgCache::Namespace
       
       virtual VerIterator GetCandidateVer(PkgIterator const &Pkg);
       virtual bool IsImportantDep(DepIterator const &Dep);
-      
+      virtual signed short GetPriority(PkgIterator const &Pkg);
+      virtual signed short GetPriority(PkgFileIterator const &File);
+
       virtual ~Policy() {};
    };
 
diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
new file mode 100644
index 000000000..218ce9f24
--- /dev/null
+++ b/apt-pkg/edsp.cc
@@ -0,0 +1,564 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+/* ######################################################################
+   Set of methods to help writing and reading everything needed for EDSP
+   ##################################################################### */
+									/*}}}*/
+// Include Files							/*{{{*/
+#include <apt-pkg/edsp.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/version.h>
+#include <apt-pkg/policy.h>
+#include <apt-pkg/tagfile.h>
+
+#include <apti18n.h>
+#include <limits>
+
+#include <stdio.h>
+									/*}}}*/
+
+// we could use pkgCache::DepType and ::Priority, but these would be localized strings…
+const char * const EDSP::PrioMap[] = {0, "important", "required", "standard",
+				      "optional", "extra"};
+const char * const EDSP::DepMap[] = {"", "Depends", "Pre-Depends", "Suggests",
+				     "Recommends" , "Conflicts", "Replaces",
+				     "Obsoletes", "Breaks", "Enhances"};
+
+// EDSP::WriteScenario - to the given file descriptor			/*{{{*/
+bool EDSP::WriteScenario(pkgDepCache &Cache, FILE* output, OpProgress *Progress)
+{
+   if (Progress != NULL)
+      Progress->SubProgress(Cache.Head().VersionCount, _("Send scenario to solver"));
+   unsigned long p = 0;
+   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); Pkg.end() == false; ++Pkg)
+      for (pkgCache::VerIterator Ver = Pkg.VersionList(); Ver.end() == false; ++Ver, ++p)
+      {
+	 WriteScenarioVersion(Cache, output, Pkg, Ver);
+	 WriteScenarioDependency(Cache, output, Pkg, Ver);
+	 fprintf(output, "\n");
+	 if (Progress != NULL && p % 100 == 0)
+	    Progress->Progress(p);
+      }
+   return true;
+}
+									/*}}}*/
+// EDSP::WriteLimitedScenario - to the given file descriptor		/*{{{*/
+bool EDSP::WriteLimitedScenario(pkgDepCache &Cache, FILE* output,
+				APT::PackageSet const &pkgset,
+				OpProgress *Progress)
+{
+   if (Progress != NULL)
+      Progress->SubProgress(Cache.Head().VersionCount, _("Send scenario to solver"));
+   unsigned long p  = 0;
+   for (APT::PackageSet::const_iterator Pkg = pkgset.begin(); Pkg != pkgset.end(); ++Pkg, ++p)
+      for (pkgCache::VerIterator Ver = Pkg.VersionList(); Ver.end() == false; ++Ver)
+      {
+	 WriteScenarioVersion(Cache, output, Pkg, Ver);
+	 WriteScenarioLimitedDependency(Cache, output, Pkg, Ver, pkgset);
+	 fprintf(output, "\n");
+	 if (Progress != NULL && p % 100 == 0)
+	    Progress->Progress(p);
+      }
+   if (Progress != NULL)
+      Progress->Done();
+   return true;
+}
+									/*}}}*/
+// EDSP::WriteScenarioVersion						/*{{{*/
+void EDSP::WriteScenarioVersion(pkgDepCache &Cache, FILE* output, pkgCache::PkgIterator const &Pkg,
+				pkgCache::VerIterator const &Ver)
+{
+   fprintf(output, "Package: %s\n", Pkg.Name());
+   fprintf(output, "Architecture: %s\n", Ver.Arch());
+   fprintf(output, "Version: %s\n", Ver.VerStr());
+   if (Pkg.CurrentVer() == Ver)
+      fprintf(output, "Installed: yes\n");
+   if (Pkg->SelectedState == pkgCache::State::Hold ||
+       (Cache[Pkg].Keep() == true && Cache[Pkg].Protect() == true))
+      fprintf(output, "Hold: yes\n");
+   fprintf(output, "APT-ID: %d\n", Ver->ID);
+   fprintf(output, "Priority: %s\n", PrioMap[Ver->Priority]);
+   if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+      fprintf(output, "Essential: yes\n");
+   fprintf(output, "Section: %s\n", Ver.Section());
+   if (Ver->MultiArch == pkgCache::Version::Allowed || Ver->MultiArch == pkgCache::Version::AllAllowed)
+      fprintf(output, "Multi-Arch: allowed\n");
+   else if (Ver->MultiArch == pkgCache::Version::Foreign || Ver->MultiArch == pkgCache::Version::AllForeign)
+      fprintf(output, "Multi-Arch: foreign\n");
+   else if (Ver->MultiArch == pkgCache::Version::Same)
+      fprintf(output, "Multi-Arch: same\n");
+   signed short Pin = std::numeric_limits<signed short>::min();
+   for (pkgCache::VerFileIterator File = Ver.FileList(); File.end() == false; ++File) {
+      signed short const p = Cache.GetPolicy().GetPriority(File.File());
+      if (Pin < p)
+	 Pin = p;
+   }
+   fprintf(output, "APT-Pin: %d\n", Pin);
+   if (Cache.GetCandidateVer(Pkg) == Ver)
+      fprintf(output, "APT-Candidate: yes\n");
+   if ((Cache[Pkg].Flags & pkgCache::Flag::Auto) == pkgCache::Flag::Auto)
+      fprintf(output, "APT-Automatic: yes\n");
+}
+									/*}}}*/
+// EDSP::WriteScenarioDependency					/*{{{*/
+void EDSP::WriteScenarioDependency(pkgDepCache &Cache, FILE* output, pkgCache::PkgIterator const &Pkg,
+				pkgCache::VerIterator const &Ver)
+{
+   std::string dependencies[pkgCache::Dep::Enhances + 1];
+   bool orGroup = false;
+   for (pkgCache::DepIterator Dep = Ver.DependsList(); Dep.end() == false; ++Dep)
+   {
+      // Ignore implicit dependencies for multiarch here
+      if (strcmp(Pkg.Arch(), Dep.TargetPkg().Arch()) != 0)
+	 continue;
+      if (orGroup == false)
+	 dependencies[Dep->Type].append(", ");
+      dependencies[Dep->Type].append(Dep.TargetPkg().Name());
+      if (Dep->Version != 0)
+	 dependencies[Dep->Type].append(" (").append(pkgCache::CompTypeDeb(Dep->CompareOp)).append(" ").append(Dep.TargetVer()).append(")");
+      if ((Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or)
+      {
+	 dependencies[Dep->Type].append(" | ");
+	 orGroup = true;
+      }
+      else
+	 orGroup = false;
+   }
+   for (int i = 1; i < pkgCache::Dep::Enhances + 1; ++i)
+      if (dependencies[i].empty() == false)
+	 fprintf(output, "%s: %s\n", DepMap[i], dependencies[i].c_str()+2);
+   string provides;
+   for (pkgCache::PrvIterator Prv = Ver.ProvidesList(); Prv.end() == false; ++Prv)
+   {
+      // Ignore implicit provides for multiarch here
+      if (strcmp(Pkg.Arch(), Prv.ParentPkg().Arch()) != 0 || strcmp(Pkg.Name(),Prv.Name()) == 0)
+	 continue;
+      provides.append(", ").append(Prv.Name());
+   }
+   if (provides.empty() == false)
+      fprintf(output, "Provides: %s\n", provides.c_str()+2);
+}
+									/*}}}*/
+// EDSP::WriteScenarioLimitedDependency					/*{{{*/
+void EDSP::WriteScenarioLimitedDependency(pkgDepCache &Cache, FILE* output,
+					  pkgCache::PkgIterator const &Pkg,
+					  pkgCache::VerIterator const &Ver,
+					  APT::PackageSet const &pkgset)
+{
+   std::string dependencies[pkgCache::Dep::Enhances + 1];
+   bool orGroup = false;
+   for (pkgCache::DepIterator Dep = Ver.DependsList(); Dep.end() == false; ++Dep)
+   {
+      // Ignore implicit dependencies for multiarch here
+      if (strcmp(Pkg.Arch(), Dep.TargetPkg().Arch()) != 0)
+	 continue;
+      if (orGroup == false)
+      {
+	 if (pkgset.find(Dep.TargetPkg()) == pkgset.end())
+	    continue;
+	 dependencies[Dep->Type].append(", ");
+      }
+      else if (pkgset.find(Dep.TargetPkg()) == pkgset.end())
+      {
+	 if ((Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or)
+	    continue;
+	 dependencies[Dep->Type].erase(dependencies[Dep->Type].end()-3, dependencies[Dep->Type].end());
+	 orGroup = false;
+	 continue;
+      }
+      dependencies[Dep->Type].append(Dep.TargetPkg().Name());
+      if (Dep->Version != 0)
+	 dependencies[Dep->Type].append(" (").append(pkgCache::CompTypeDeb(Dep->CompareOp)).append(" ").append(Dep.TargetVer()).append(")");
+      if ((Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or)
+      {
+	 dependencies[Dep->Type].append(" | ");
+	 orGroup = true;
+      }
+      else
+	 orGroup = false;
+   }
+   for (int i = 1; i < pkgCache::Dep::Enhances + 1; ++i)
+      if (dependencies[i].empty() == false)
+	 fprintf(output, "%s: %s\n", DepMap[i], dependencies[i].c_str()+2);
+   string provides;
+   for (pkgCache::PrvIterator Prv = Ver.ProvidesList(); Prv.end() == false; ++Prv)
+   {
+      // Ignore implicit provides for multiarch here
+      if (strcmp(Pkg.Arch(), Prv.ParentPkg().Arch()) != 0 || strcmp(Pkg.Name(),Prv.Name()) == 0)
+	 continue;
+      if (pkgset.find(Prv.ParentPkg()) == pkgset.end())
+	 continue;
+      provides.append(", ").append(Prv.Name());
+   }
+   if (provides.empty() == false)
+      fprintf(output, "Provides: %s\n", provides.c_str()+2);
+}
+									/*}}}*/
+// EDSP::WriteRequest - to the given file descriptor			/*{{{*/
+bool EDSP::WriteRequest(pkgDepCache &Cache, FILE* output, bool const Upgrade,
+			bool const DistUpgrade, bool const AutoRemove,
+			OpProgress *Progress)
+{
+   if (Progress != NULL)
+      Progress->SubProgress(Cache.Head().PackageCount, _("Send request to solver"));
+   unsigned long p = 0;
+   string del, inst;
+   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); Pkg.end() == false; ++Pkg, ++p)
+   {
+      if (Progress != NULL && p % 100 == 0)
+         Progress->Progress(p);
+      string* req;
+      if (Cache[Pkg].Delete() == true)
+	 req = &del;
+      else if (Cache[Pkg].NewInstall() == true || Cache[Pkg].Upgrade() == true)
+	 req = &inst;
+      else
+	 continue;
+      req->append(" ").append(Pkg.FullName());
+   }
+   fprintf(output, "Request: EDSP 0.4\n");
+   if (del.empty() == false)
+      fprintf(output, "Remove: %s\n", del.c_str()+1);
+   if (inst.empty() == false)
+      fprintf(output, "Install: %s\n", inst.c_str()+1);
+   if (Upgrade == true)
+      fprintf(output, "Upgrade: yes\n");
+   if (DistUpgrade == true)
+      fprintf(output, "Dist-Upgrade: yes\n");
+   if (AutoRemove == true)
+      fprintf(output, "Autoremove: yes\n");
+   if (_config->FindB("APT::Solver::Strict-Pinning", true) == false)
+      fprintf(output, "Strict-Pinning: no\n");
+   string solverpref("APT::Solver::");
+   solverpref.append(_config->Find("APT::Solver::Name", "internal")).append("::Preferences");
+   if (_config->Exists(solverpref) == true)
+      fprintf(output, "Preferences: %s\n", _config->Find(solverpref,"").c_str());
+   fprintf(output, "\n");
+
+   return true;
+}
+									/*}}}*/
+// EDSP::ReadResponse - from the given file descriptor			/*{{{*/
+bool EDSP::ReadResponse(int const input, pkgDepCache &Cache, OpProgress *Progress) {
+	/* We build an map id to mmap offset here
+	   In theory we could use the offset as ID, but then VersionCount
+	   couldn't be used to create other versionmappings anymore and it
+	   would be too easy for a (buggy) solver to segfault APT… */
+	unsigned long long const VersionCount = Cache.Head().VersionCount;
+	unsigned long VerIdx[VersionCount];
+	for (pkgCache::PkgIterator P = Cache.PkgBegin(); P.end() == false; ++P) {
+		for (pkgCache::VerIterator V = P.VersionList(); V.end() == false; ++V)
+			VerIdx[V->ID] = V.Index();
+		Cache[P].Marked = true;
+		Cache[P].Garbage = false;
+	}
+
+	FileFd in;
+	in.OpenDescriptor(input, FileFd::ReadOnly);
+	pkgTagFile response(&in, 100);
+	pkgTagSection section;
+
+	while (response.Step(section) == true) {
+		std::string type;
+		if (section.Exists("Install") == true)
+			type = "Install";
+		else if (section.Exists("Remove") == true)
+			type = "Remove";
+		else if (section.Exists("Progress") == true) {
+			if (Progress != NULL) {
+				string msg = section.FindS("Message");
+				if (msg.empty() == true)
+					msg = _("Prepare for receiving solution");
+				Progress->SubProgress(100, msg, section.FindI("Percentage", 0));
+			}
+			continue;
+		} else if (section.Exists("Error") == true) {
+			std::string msg = SubstVar(SubstVar(section.FindS("Message"), "\n .\n", "\n\n"), "\n ", "\n");
+			if (msg.empty() == true) {
+				msg = _("External solver failed without a proper error message");
+				_error->Error(msg.c_str());
+			} else
+				_error->Error("External solver failed with: %s", msg.substr(0,msg.find('\n')).c_str());
+			if (Progress != NULL)
+				Progress->Done();
+			std::cerr << "The solver encountered an error of type: " << section.FindS("Error") << std::endl;
+			std::cerr << "The following information might help you to understand what is wrong:" << std::endl;
+			std::cerr << msg << std::endl << std::endl;
+			return false;
+		} else if (section.Exists("Autoremove") == true)
+			type = "Autoremove";
+		else
+			continue;
+
+		size_t const id = section.FindULL(type.c_str(), VersionCount);
+		if (id == VersionCount) {
+			_error->Warning("Unable to parse %s request with id value '%s'!", type.c_str(), section.FindS(type.c_str()).c_str());
+			continue;
+		} else if (id > Cache.Head().VersionCount) {
+			_error->Warning("ID value '%s' in %s request stanza is to high to refer to a known version!", section.FindS(type.c_str()).c_str(), type.c_str());
+			continue;
+		}
+
+		pkgCache::VerIterator Ver(Cache.GetCache(), Cache.GetCache().VerP + VerIdx[id]);
+		Cache.SetCandidateVersion(Ver);
+		if (type == "Install")
+			Cache.MarkInstall(Ver.ParentPkg(), false, 0, false);
+		else if (type == "Remove")
+			Cache.MarkDelete(Ver.ParentPkg(), false);
+		else if (type == "Autoremove") {
+			Cache[Ver.ParentPkg()].Marked = false;
+			Cache[Ver.ParentPkg()].Garbage = true;
+		}
+	}
+	return true;
+}
+									/*}}}*/
+// EDSP::ReadLine - first line from the given file descriptor		/*{{{*/
+// ---------------------------------------------------------------------
+/* Little helper method to read a complete line into a string. Similar to
+   fgets but we need to use the low-level read() here as otherwise the
+   listparser will be confused later on as mixing of fgets and read isn't
+   a supported action according to the manpages and results are undefined */
+bool EDSP::ReadLine(int const input, std::string &line) {
+	char one;
+	ssize_t data = 0;
+	line.erase();
+	line.reserve(100);
+	while ((data = read(input, &one, sizeof(one))) != -1) {
+		if (data != 1)
+			continue;
+		if (one == '\n')
+			return true;
+		if (one == '\r')
+			continue;
+		if (line.empty() == true && isblank(one) != 0)
+			continue;
+		line += one;
+	}
+	return false;
+}
+									/*}}}*/
+// EDSP::StringToBool - convert yes/no to bool				/*{{{*/
+// ---------------------------------------------------------------------
+/* we are not as lazy as we are in the global StringToBool as we really
+   only accept yes/no here - but we will ignore leading spaces */
+bool EDSP::StringToBool(char const *answer, bool const defValue) {
+   for (; isspace(*answer) != 0; ++answer);
+   if (strncasecmp(answer, "yes", 3) == 0)
+      return true;
+   else if (strncasecmp(answer, "no", 2) == 0)
+      return false;
+   else
+      _error->Warning("Value '%s' is not a boolean 'yes' or 'no'!", answer);
+   return defValue;
+}
+									/*}}}*/
+// EDSP::ReadRequest - first stanza from the given file descriptor	/*{{{*/
+bool EDSP::ReadRequest(int const input, std::list<std::string> &install,
+			std::list<std::string> &remove, bool &upgrade,
+			bool &distUpgrade, bool &autoRemove)
+{
+   install.clear();
+   remove.clear();
+   upgrade = false;
+   distUpgrade = false;
+   autoRemove = false;
+   std::string line;
+   while (ReadLine(input, line) == true)
+   {
+      // Skip empty lines before request
+      if (line.empty() == true)
+	 continue;
+      // The first Tag must be a request, so search for it
+      if (line.compare(0, 8, "Request:") != 0)
+	 continue;
+
+      while (ReadLine(input, line) == true)
+      {
+	 // empty lines are the end of the request
+	 if (line.empty() == true)
+	    return true;
+
+	 std::list<std::string> *request = NULL;
+	 if (line.compare(0, 8, "Install:") == 0)
+	 {
+	    line.erase(0, 8);
+	    request = &install;
+	 }
+	 else if (line.compare(0, 7, "Remove:") == 0)
+	 {
+	    line.erase(0, 7);
+	    request = &remove;
+	 }
+	 else if (line.compare(0, 8, "Upgrade:") == 0)
+	    upgrade = EDSP::StringToBool(line.c_str() + 9, false);
+	 else if (line.compare(0, 13, "Dist-Upgrade:") == 0)
+	    distUpgrade = EDSP::StringToBool(line.c_str() + 14, false);
+	 else if (line.compare(0, 11, "Autoremove:") == 0)
+	    autoRemove = EDSP::StringToBool(line.c_str() + 12, false);
+	 else
+	    _error->Warning("Unknown line in EDSP Request stanza: %s", line.c_str());
+
+	 if (request == NULL)
+	    continue;
+	 size_t end = line.length();
+	 do {
+	    size_t begin = line.rfind(' ');
+	    if (begin == std::string::npos)
+	    {
+	       request->push_back(line.substr(0, end));
+	       break;
+	    }
+	    else if (begin < end)
+	       request->push_back(line.substr(begin + 1, end));
+	    line.erase(begin);
+	    end = line.find_last_not_of(' ');
+	 } while (end != std::string::npos);
+      }
+   }
+   return false;
+}
+									/*}}}*/
+// EDSP::ApplyRequest - first stanza from the given file descriptor	/*{{{*/
+bool EDSP::ApplyRequest(std::list<std::string> const &install,
+			 std::list<std::string> const &remove,
+			 pkgDepCache &Cache)
+{
+	for (std::list<std::string>::const_iterator i = install.begin();
+	     i != install.end(); ++i) {
+		pkgCache::PkgIterator P = Cache.FindPkg(*i);
+		if (P.end() == true)
+			_error->Warning("Package %s is not known, so can't be installed", i->c_str());
+		else
+			Cache.MarkInstall(P, false);
+	}
+
+	for (std::list<std::string>::const_iterator i = remove.begin();
+	     i != remove.end(); ++i) {
+		pkgCache::PkgIterator P = Cache.FindPkg(*i);
+		if (P.end() == true)
+			_error->Warning("Package %s is not known, so can't be installed", i->c_str());
+		else
+			Cache.MarkDelete(P);
+	}
+	return true;
+}
+									/*}}}*/
+// EDSP::WriteSolution - to the given file descriptor			/*{{{*/
+bool EDSP::WriteSolution(pkgDepCache &Cache, FILE* output)
+{
+   bool const Debug = _config->FindB("Debug::EDSP::WriteSolution", false);
+   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); Pkg.end() == false; ++Pkg)
+   {
+      if (Cache[Pkg].Delete() == true)
+      {
+	 fprintf(output, "Remove: %d\n", Pkg.CurrentVer()->ID);
+	 if (Debug == true)
+	    fprintf(output, "Package: %s\nVersion: %s\n", Pkg.FullName().c_str(), Pkg.CurrentVer().VerStr());
+      }
+      else if (Cache[Pkg].NewInstall() == true || Cache[Pkg].Upgrade() == true)
+      {
+	 fprintf(output, "Install: %d\n", Cache.GetCandidateVer(Pkg)->ID);
+	 if (Debug == true)
+	    fprintf(output, "Package: %s\nVersion: %s\n", Pkg.FullName().c_str(), Cache.GetCandidateVer(Pkg).VerStr());
+      }
+      else if (Cache[Pkg].Garbage == true)
+      {
+	 fprintf(output, "Autoremove: %d\n", Pkg.CurrentVer()->ID);
+	 if (Debug == true)
+	    fprintf(output, "Package: %s\nVersion: %s\n", Pkg.FullName().c_str(), Pkg.CurrentVer().VerStr());
+	    fprintf(stderr, "Autoremove: %s\nVersion: %s\n", Pkg.FullName().c_str(), Pkg.CurrentVer().VerStr());
+      }
+      else
+	 continue;
+      fprintf(output, "\n");
+   }
+
+   return true;
+}
+									/*}}}*/
+// EDSP::WriteProgess - pulse to the given file descriptor		/*{{{*/
+bool EDSP::WriteProgress(unsigned short const percent, const char* const message, FILE* output) {
+	fprintf(output, "Progress: %s\n", TimeRFC1123(time(NULL)).c_str());
+	fprintf(output, "Percentage: %d\n", percent);
+	fprintf(output, "Message: %s\n\n", message);
+	fflush(output);
+	return true;
+}
+									/*}}}*/
+// EDSP::WriteError - format an error message to be send to file descriptor /*{{{*/
+bool EDSP::WriteError(char const * const uuid, std::string const &message, FILE* output) {
+	fprintf(output, "Error: %s\n", uuid);
+	fprintf(output, "Message: %s\n\n", SubstVar(SubstVar(message, "\n\n", "\n.\n"), "\n", "\n ").c_str());
+	return true;
+}
+									/*}}}*/
+// EDSP::ExecuteSolver - fork requested solver and setup ipc pipes	{{{*/
+bool EDSP::ExecuteSolver(const char* const solver, int *solver_in, int *solver_out) {
+	std::vector<std::string> const solverDirs = _config->FindVector("Dir::Bin::Solvers");
+	std::string file;
+	for (std::vector<std::string>::const_iterator dir = solverDirs.begin();
+	     dir != solverDirs.end(); ++dir) {
+		file = flCombine(*dir, solver);
+		if (RealFileExists(file.c_str()) == true)
+			break;
+		file.clear();
+	}
+
+	if (file.empty() == true)
+		return _error->Error("Can't call external solver '%s' as it is not in a configured directory!", solver);
+	int external[4] = {-1, -1, -1, -1};
+	if (pipe(external) != 0 || pipe(external + 2) != 0)
+		return _error->Errno("Resolve", "Can't create needed IPC pipes for EDSP");
+	for (int i = 0; i < 4; ++i)
+		SetCloseExec(external[i], true);
+
+	pid_t Solver = ExecFork();
+	if (Solver == 0) {
+		dup2(external[0], STDIN_FILENO);
+		dup2(external[3], STDOUT_FILENO);
+		const char* calling[2] = { file.c_str(), 0 };
+		execv(calling[0], (char**) calling);
+		std::cerr << "Failed to execute solver '" << solver << "'!" << std::endl;
+		_exit(100);
+	}
+	close(external[0]);
+	close(external[3]);
+
+	if (WaitFd(external[1], true, 5) == false)
+		return _error->Errno("Resolve", "Timed out while Waiting on availability of solver stdin");
+
+	*solver_in = external[1];
+	*solver_out = external[2];
+	return true;
+}
+									/*}}}*/
+// EDSP::ResolveExternal - resolve problems by asking external for help	{{{*/
+bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
+			 bool const upgrade, bool const distUpgrade,
+			 bool const autoRemove, OpProgress *Progress) {
+	int solver_in, solver_out;
+	if (EDSP::ExecuteSolver(solver, &solver_in, &solver_out) == false)
+		return false;
+
+	FILE* output = fdopen(solver_in, "w");
+	if (output == NULL)
+		return _error->Errno("Resolve", "fdopen on solver stdin failed");
+
+	if (Progress != NULL)
+		Progress->OverallProgress(0, 100, 5, _("Execute external solver"));
+	EDSP::WriteRequest(Cache, output, upgrade, distUpgrade, autoRemove, Progress);
+	if (Progress != NULL)
+		Progress->OverallProgress(5, 100, 20, _("Execute external solver"));
+	EDSP::WriteScenario(Cache, output, Progress);
+	fclose(output);
+
+	if (Progress != NULL)
+		Progress->OverallProgress(25, 100, 75, _("Execute external solver"));
+	if (EDSP::ReadResponse(solver_out, Cache, Progress) == false)
+		return false;
+
+	return true;
+}
+									/*}}}*/
diff --git a/apt-pkg/edsp.h b/apt-pkg/edsp.h
new file mode 100644
index 000000000..743c3f5d1
--- /dev/null
+++ b/apt-pkg/edsp.h
@@ -0,0 +1,222 @@
+// -*- mode: cpp; mode: fold -*-
+/** Description \file edsp.h						{{{
+   ######################################################################
+   Set of methods to help writing and reading everything needed for EDSP
+   with the noteable exception of reading a scenario for conversion into
+   a Cache as this is handled by edsp interface for listparser and friends
+   ##################################################################### */
+									/*}}}*/
+#ifndef PKGLIB_EDSP_H
+#define PKGLIB_EDSP_H
+
+#include <apt-pkg/depcache.h>
+#include <apt-pkg/cacheset.h>
+#include <apt-pkg/progress.h>
+
+#include <string>
+
+class EDSP								/*{{{*/
+{
+	// we could use pkgCache::DepType and ::Priority, but these would be localized strings…
+	static const char * const PrioMap[];
+	static const char * const DepMap[];
+
+	bool static ReadLine(int const input, std::string &line);
+	bool static StringToBool(char const *answer, bool const defValue);
+
+	void static WriteScenarioVersion(pkgDepCache &Cache, FILE* output,
+					 pkgCache::PkgIterator const &Pkg,
+					 pkgCache::VerIterator const &Ver);
+	void static WriteScenarioDependency(pkgDepCache &Cache, FILE* output,
+					    pkgCache::PkgIterator const &Pkg,
+					    pkgCache::VerIterator const &Ver);
+	void static WriteScenarioLimitedDependency(pkgDepCache &Cache, FILE* output,
+						   pkgCache::PkgIterator const &Pkg,
+						   pkgCache::VerIterator const &Ver,
+						   APT::PackageSet const &pkgset);
+public:
+	/** \brief creates the EDSP request stanza
+	 *
+	 *  In the EDSP protocol the first thing send to the resolver is a stanza
+	 *  encoding the request. This method will write this stanza by looking at
+	 *  the given Cache and requests the installation of all packages which were
+	 *  marked for installation in it (equally for remove).
+	 *
+	 *  \param Cache in which the request is encoded
+	 *  \param output is written to this "file"
+	 *  \param upgrade is true if it is an request like apt-get upgrade
+	 *  \param distUpgrade is true if it is a request like apt-get dist-upgrade
+	 *  \param autoRemove is true if removal of unneeded packages should be performed
+	 *  \param Progress is an instance to report progress to
+	 *
+	 *  \return true if request was composed successfully, otherwise false
+	 */
+	bool static WriteRequest(pkgDepCache &Cache, FILE* output,
+				 bool const upgrade = false,
+				 bool const distUpgrade = false,
+				 bool const autoRemove = false,
+				OpProgress *Progress = NULL);
+
+	/** \brief creates the scenario representing the package universe
+	 *
+	 *  After the request all known information about a package are send
+	 *  to the solver. The output looks similar to a Packages or status file
+	 *
+	 *  All packages and version included in this Cache are send, even if
+	 *  it doesn't make sense from an APT resolver point of view like versions
+	 *  with a negative pin to enable the solver to propose even that as a
+	 *  solution or at least to be able to give a hint what can be done to
+	 *  statisfy a request.
+	 *
+	 *  \param Cache is the known package universe
+	 *  \param output is written to this "file"
+	 *  \param Progress is an instance to report progress to
+	 *
+	 *  \return true if universe was composed successfully, otherwise false
+	 */
+	bool static WriteScenario(pkgDepCache &Cache, FILE* output, OpProgress *Progress = NULL);
+
+	/** \brief creates a limited scenario representing the package universe
+	 *
+	 *  This method works similar to #WriteScenario as it works in the same
+	 *  way but doesn't send the complete universe to the solver but only
+	 *  packages included in the pkgset which will have only dependencies
+	 *  on packages which are in the given set. All other dependencies will
+	 *  be removed, so that this method can be used to create testcases
+	 *
+	 *  \param Cache is the known package universe
+	 *  \param output is written to this "file"
+	 *  \param pkgset is a set of packages the universe should be limited to
+	 *  \param Progress is an instance to report progress to
+	 *
+	 *  \return true if universe was composed successfully, otherwise false
+	 */
+	bool static WriteLimitedScenario(pkgDepCache &Cache, FILE* output,
+					 APT::PackageSet const &pkgset,
+					 OpProgress *Progress = NULL);
+
+	/** \brief waits and acts on the information returned from the solver
+	 *
+	 *  This method takes care of interpreting whatever the solver sends
+	 *  through the standard output like a solution, progress or an error.
+	 *  The main thread should handle his control over to this method to
+	 *  wait for the solver to finish the given task
+	 *
+	 *  \param input file descriptor with the response from the solver
+	 *  \param Cache the solution should be applied on if any
+	 *  \param Progress is an instance to report progress to
+	 *
+	 *  \return true if a solution is found and applied correctly, otherwise false
+	 */
+	bool static ReadResponse(int const input, pkgDepCache &Cache, OpProgress *Progress = NULL);
+
+	/** \brief search and read the request stanza for action later
+	 *
+	 *  This method while ignore the input up to the point it finds the
+	 *  Request: line as an indicator for the Request stanza.
+	 *  The request is stored in the parameters install and remove then,
+	 *  as the cache isn't build yet as the scenario follows the request.
+	 *
+	 *  \param input file descriptor with the edsp input for the solver
+	 *  \param[out] install is a list which gets populated with requested installs
+	 *  \param[out] remove is a list which gets populated with requested removals
+	 *  \param[out] upgrade is true if it is a request like apt-get upgrade
+	 *  \param[out] distUpgrade is true if it is a request like apt-get dist-upgrade
+	 *  \param[out] autoRemove is true if removal of uneeded packages should be performed
+	 *
+	 *  \return true if the request could be found and worked on, otherwise false
+	 */
+	bool static ReadRequest(int const input, std::list<std::string> &install,
+			std::list<std::string> &remove, bool &upgrade,
+			bool &distUpgrade, bool &autoRemove);
+
+	/** \brief takes the request lists and applies it on the cache
+	 *
+	 *  The lists as created by #ReadRequest will be used to find the
+	 *  packages in question and mark them for install/remove.
+	 *  No solving is done and no auto-install/-remove.
+	 *
+	 *  \param install is a list of packages to mark for installation
+	 *  \param remove is a list of packages to mark for removal
+	 *  \param Cache is there the markers should be set
+	 *
+	 *  \return false if the request couldn't be applied, true otherwise
+	 */
+	bool static ApplyRequest(std::list<std::string> const &install,
+				 std::list<std::string> const &remove,
+				 pkgDepCache &Cache);
+
+	/** \brief encodes the changes in the Cache as a EDSP solution
+	 *
+	 *  The markers in the Cache are observed and send to given
+	 *  file. The solution isn't checked for consistency or alike,
+	 *  so even broken solutions can be written successfully,
+	 *  but the front-end revicing it will properly fail then.
+	 *
+	 *  \param Cache which represents the solution
+	 *  \param output to write the stanzas forming the solution to
+	 *
+	 *  \return true if solution could be written, otherwise false
+	 */
+	bool static WriteSolution(pkgDepCache &Cache, FILE* output);
+
+	/** \brief sends a progress report
+	 *
+	 *  \param percent of the solving completed
+	 *  \param message the solver wants the user to see
+	 *  \param output the front-end listens for progress report
+	 */
+	bool static WriteProgress(unsigned short const percent, const char* const message, FILE* output);
+
+	/** \brief sends an error report
+	 *
+	 *  Solvers are expected to execute successfully even if
+	 *  they were unable to calculate a solution for a given task.
+	 *  Obviously they can't send a solution through, so this
+	 *  methods deals with formatting an error message correctly
+	 *  so that the front-ends can recieve and display it.
+	 *
+	 *  The first line of the message should be a short description
+	 *  of the error so it can be used for dialog titles or alike
+	 *
+	 *  \param uuid of this error message
+	 *  \param message is free form text to discribe the error
+	 *  \param output the front-end listens for error messages
+	 */
+	bool static WriteError(char const * const uuid, std::string const &message, FILE* output);
+
+
+	/** \brief executes the given solver and returns the pipe ends
+	 *
+	 *  The given solver is executed if it can be found in one of the
+	 *  configured directories and setup for it is performed.
+	 *
+	 *  \param solver to execute
+	 *  \param[out] solver_in will be the stdin of the solver
+	 *  \param[out] solver_out will be the stdout of the solver
+	 *
+	 *  \return true if the solver could be started and the pipes
+	 *  are set up correctly, otherwise false and the pipes are invalid
+	 */
+	bool static ExecuteSolver(const char* const solver, int *solver_in, int *solver_out);
+
+	/** \brief call an external resolver to handle the request
+	 *
+	 *  This method wraps all the methods above to call an external solver
+	 *
+	 *  \param solver to execute
+	 *  \param Cache with the problem and as universe to work in
+	 *  \param upgrade is true if it is a request like apt-get upgrade
+	 *  \param distUpgrade is true if it is a request like apt-get dist-upgrade
+	 *  \param autoRemove is true if unneeded packages should be removed
+	 *  \param Progress is an instance to report progress to
+	 *
+	 *  \return true if the solver has successfully solved the problem,
+	 *  otherwise false
+	 */
+	bool static ResolveExternal(const char* const solver, pkgDepCache &Cache,
+				    bool const upgrade, bool const distUpgrade,
+				    bool const autoRemove, OpProgress *Progress = NULL);
+};
+									/*}}}*/
+#endif
diff --git a/apt-pkg/edsp/edspindexfile.cc b/apt-pkg/edsp/edspindexfile.cc
new file mode 100644
index 000000000..f5881e663
--- /dev/null
+++ b/apt-pkg/edsp/edspindexfile.cc
@@ -0,0 +1,78 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+/* ######################################################################
+   The scenario file is designed to work as an intermediate file between
+   APT and the resolver. Its on propose very similar to a dpkg status file
+   ##################################################################### */
+									/*}}}*/
+// Include Files							/*{{{*/
+#include <apt-pkg/edspindexfile.h>
+#include <apt-pkg/edsplistparser.h>
+#include <apt-pkg/sourcelist.h>
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/progress.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/strutl.h>
+#include <apt-pkg/acquire-item.h>
+
+#include <sys/stat.h>
+									/*}}}*/
+
+// edspIndex::edspIndex - Constructor					/*{{{*/
+// ---------------------------------------------------------------------
+/* */
+edspIndex::edspIndex(string File) : debStatusIndex(File)
+{
+}
+									/*}}}*/
+// StatusIndex::Merge - Load the index file into a cache		/*{{{*/
+bool edspIndex::Merge(pkgCacheGenerator &Gen,OpProgress *Prog) const
+{
+   FileFd Pkg;
+   if (File != "stdin")
+      Pkg.Open(File, FileFd::ReadOnly);
+   else
+      Pkg.OpenDescriptor(STDIN_FILENO, FileFd::ReadOnly);
+   if (_error->PendingError() == true)
+      return false;
+   edspListParser Parser(&Pkg);
+   if (_error->PendingError() == true)
+      return false;
+
+   if (Prog != NULL)
+      Prog->SubProgress(0,File);
+   if (Gen.SelectFile(File,string(),*this) == false)
+      return _error->Error("Problem with SelectFile %s",File.c_str());
+
+   // Store the IMS information
+   pkgCache::PkgFileIterator CFile = Gen.GetCurFile();
+   struct stat St;
+   if (fstat(Pkg.Fd(),&St) != 0)
+      return _error->Errno("fstat","Failed to stat");
+   CFile->Size = St.st_size;
+   CFile->mtime = St.st_mtime;
+   CFile->Archive = Gen.WriteUniqString("edsp::scenario");
+
+   if (Gen.MergeList(Parser) == false)
+      return _error->Error("Problem with MergeList %s",File.c_str());
+   return true;
+}
+									/*}}}*/
+// Index File types for APT						/*{{{*/
+class edspIFType: public pkgIndexFile::Type
+{
+   public:
+   virtual pkgRecords::Parser *CreatePkgParser(pkgCache::PkgFileIterator File) const
+   {
+      // we don't have a record parser for this type as the file is not presistent
+      return NULL;
+   };
+   edspIFType() {Label = "EDSP scenario file";};
+};
+static edspIFType _apt_Universe;
+
+const pkgIndexFile::Type *edspIndex::GetType() const
+{
+   return &_apt_Universe;
+}
+									/*}}}*/
diff --git a/apt-pkg/edsp/edspindexfile.h b/apt-pkg/edsp/edspindexfile.h
new file mode 100644
index 000000000..87c06557c
--- /dev/null
+++ b/apt-pkg/edsp/edspindexfile.h
@@ -0,0 +1,25 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+/* ######################################################################
+   The scenario file is designed to work as an intermediate file between
+   APT and the resolver. Its on propose very similar to a dpkg status file
+   ##################################################################### */
+									/*}}}*/
+#ifndef PKGLIB_EDSPINDEXFILE_H
+#define PKGLIB_EDSPINDEXFILE_H
+
+#include <apt-pkg/indexfile.h>
+#include <apt-pkg/debindexfile.h>
+
+class edspIndex : public debStatusIndex
+{
+   public:
+
+   virtual const Type *GetType() const;
+
+   virtual bool Merge(pkgCacheGenerator &Gen,OpProgress *Prog) const;
+
+   edspIndex(string File);
+};
+
+#endif
diff --git a/apt-pkg/edsp/edsplistparser.cc b/apt-pkg/edsp/edsplistparser.cc
new file mode 100644
index 000000000..3349e8cce
--- /dev/null
+++ b/apt-pkg/edsp/edsplistparser.cc
@@ -0,0 +1,90 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+/* ######################################################################
+
+   Package Cache Generator - Generator for the cache structure.
+
+   This builds the cache structure from the abstract package list parser.
+
+   ##################################################################### */
+									/*}}}*/
+// Include Files							/*{{{*/
+#include <apt-pkg/edsplistparser.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/strutl.h>
+#include <apt-pkg/md5.h>
+#include <apt-pkg/macros.h>
+									/*}}}*/
+
+// ListParser::edspListParser - Constructor				/*{{{*/
+edspListParser::edspListParser(FileFd *File, string const &Arch) : debListParser(File, Arch)
+{}
+									/*}}}*/
+// ListParser::NewVersion - Fill in the version structure		/*{{{*/
+bool edspListParser::NewVersion(pkgCache::VerIterator &Ver)
+{
+   Ver->ID = Section.FindI("APT-ID", Ver->ID);
+   return debListParser::NewVersion(Ver);
+}
+									/*}}}*/
+// ListParser::Description - Return the description string		/*{{{*/
+// ---------------------------------------------------------------------
+/* Sorry, no description for the resolvers… */
+string edspListParser::Description()
+{
+   return "";
+}
+string edspListParser::DescriptionLanguage()
+{
+   return "";
+}
+MD5SumValue edspListParser::Description_md5()
+{
+   return MD5SumValue("");
+}
+									/*}}}*/
+// ListParser::VersionHash - Compute a unique hash for this version	/*{{{*/
+// ---------------------------------------------------------------------
+/* */
+unsigned short edspListParser::VersionHash()
+{
+   if (Section.Exists("APT-Hash") == true)
+      return Section.FindI("APT-Hash");
+   else if (Section.Exists("APT-ID") == true)
+      return Section.FindI("APT-ID");
+   return 0;
+}
+									/*}}}*/
+// ListParser::ParseStatus - Parse the status field			/*{{{*/
+// ---------------------------------------------------------------------
+/* The Status: line here is not a normal dpkg one but just one which tells
+   use if the package is installed or not, where missing means not. */
+bool edspListParser::ParseStatus(pkgCache::PkgIterator &Pkg,
+				pkgCache::VerIterator &Ver)
+{
+   unsigned long state = 0;
+   if (Section.FindFlag("Hold",state,pkgCache::State::Hold) == false)
+      return false;
+   if (state != 0)
+      Pkg->SelectedState = pkgCache::State::Hold;
+
+   state = 0;
+   if (Section.FindFlag("Installed",state,pkgCache::State::Installed) == false)
+      return false;
+   if (state != 0)
+   {
+      Pkg->CurrentState = pkgCache::State::Installed;
+      Pkg->CurrentVer = Ver.Index();
+   }
+
+   return true;
+}
+									/*}}}*/
+// ListParser::LoadReleaseInfo - Load the release information		/*{{{*/
+bool edspListParser::LoadReleaseInfo(pkgCache::PkgFileIterator &FileI,
+				    FileFd &File, string component)
+{
+   return true;
+}
+									/*}}}*/
diff --git a/apt-pkg/edsp/edsplistparser.h b/apt-pkg/edsp/edsplistparser.h
new file mode 100644
index 000000000..ec9f09905
--- /dev/null
+++ b/apt-pkg/edsp/edsplistparser.h
@@ -0,0 +1,38 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+/* ######################################################################
+
+   EDSP Package List Parser - This implements the abstract parser
+   interface for the APT specific intermediate format which is passed
+   to external resolvers
+
+   ##################################################################### */
+									/*}}}*/
+#ifndef PKGLIB_EDSPLISTPARSER_H
+#define PKGLIB_EDSPLISTPARSER_H
+
+#include <apt-pkg/deblistparser.h>
+#include <apt-pkg/pkgcachegen.h>
+#include <apt-pkg/indexfile.h>
+#include <apt-pkg/tagfile.h>
+
+class edspListParser : public debListParser
+{
+   public:
+   virtual bool NewVersion(pkgCache::VerIterator &Ver);
+   virtual string Description();
+   virtual string DescriptionLanguage();
+   virtual MD5SumValue Description_md5();
+   virtual unsigned short VersionHash();
+
+   bool LoadReleaseInfo(pkgCache::PkgFileIterator &FileI,FileFd &File,
+			string section);
+
+   edspListParser(FileFd *File, string const &Arch = "");
+
+   protected:
+   virtual bool ParseStatus(pkgCache::PkgIterator &Pkg,pkgCache::VerIterator &Ver);
+
+};
+
+#endif
diff --git a/apt-pkg/edsp/edspsystem.cc b/apt-pkg/edsp/edspsystem.cc
new file mode 100644
index 000000000..ac0bb8beb
--- /dev/null
+++ b/apt-pkg/edsp/edspsystem.cc
@@ -0,0 +1,124 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+/* ######################################################################
+
+   This system provides the abstraction to use the scenario file as the
+   only source of package information to be able to feed the created file
+   back to APT for its own consumption (eat your own dogfood).
+
+   ##################################################################### */
+									/*}}}*/
+// Include Files							/*{{{*/
+#include <apt-pkg/edspsystem.h>
+#include <apt-pkg/debversion.h>
+#include <apt-pkg/edspindexfile.h>
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/fileutl.h>
+#include <apti18n.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <dirent.h>
+#include <errno.h>
+									/*}}}*/
+
+edspSystem edspSys;
+
+// System::debSystem - Constructor					/*{{{*/
+edspSystem::edspSystem()
+{
+   StatusFile = 0;
+
+   Label = "Debian APT solver interface";
+   VS = &debVS;
+}
+									/*}}}*/
+// System::~debSystem - Destructor					/*{{{*/
+edspSystem::~edspSystem()
+{
+   delete StatusFile;
+}
+									/*}}}*/
+// System::Lock - Get the lock						/*{{{*/
+bool edspSystem::Lock()
+{
+   return true;
+}
+									/*}}}*/
+// System::UnLock - Drop a lock						/*{{{*/
+bool edspSystem::UnLock(bool NoErrors)
+{
+   return true;
+}
+									/*}}}*/
+// System::CreatePM - Create the underlying package manager		/*{{{*/
+// ---------------------------------------------------------------------
+/* we can't use edsp input as input for real installations - just a
+   simulation can work, but everything else will fail bigtime */
+pkgPackageManager *edspSystem::CreatePM(pkgDepCache *Cache) const
+{
+   return NULL;
+}
+									/*}}}*/
+// System::Initialize - Setup the configuration space..			/*{{{*/
+bool edspSystem::Initialize(Configuration &Cnf)
+{
+   Cnf.Set("Dir::State::extended_states", "/dev/null");
+   Cnf.Set("Dir::State::status","/dev/null");
+   Cnf.Set("Dir::State::lists","/dev/null");
+
+   Cnf.Set("Debug::NoLocking", "true");
+   Cnf.Set("APT::Get::Simulate", "true");
+
+   if (StatusFile) {
+     delete StatusFile;
+     StatusFile = 0;
+   }
+   return true;
+}
+									/*}}}*/
+// System::ArchiveSupported - Is a file format supported		/*{{{*/
+bool edspSystem::ArchiveSupported(const char *Type)
+{
+   return false;
+}
+									/*}}}*/
+// System::Score - Determine if we should use the edsp system		/*{{{*/
+signed edspSystem::Score(Configuration const &Cnf)
+{
+   if (Cnf.Find("edsp::scenario", "") == "stdin")
+      return 1000;
+   if (FileExists(Cnf.FindFile("edsp::scenario","")) == true)
+      return 1000;
+   return -1000;
+}
+									/*}}}*/
+// System::AddStatusFiles - Register the status files			/*{{{*/
+bool edspSystem::AddStatusFiles(vector<pkgIndexFile *> &List)
+{
+   if (StatusFile == 0)
+   {
+      if (_config->Find("edsp::scenario", "") == "stdin")
+	 StatusFile = new edspIndex("stdin");
+      else
+	 StatusFile = new edspIndex(_config->FindFile("edsp::scenario"));
+   }
+   List.push_back(StatusFile);
+   return true;
+}
+									/*}}}*/
+// System::FindIndex - Get an index file for status files		/*{{{*/
+bool edspSystem::FindIndex(pkgCache::PkgFileIterator File,
+			  pkgIndexFile *&Found) const
+{
+   if (StatusFile == 0)
+      return false;
+   if (StatusFile->FindInCache(*File.Cache()) == File)
+   {
+      Found = StatusFile;
+      return true;
+   }
+
+   return false;
+}
+									/*}}}*/
diff --git a/apt-pkg/edsp/edspsystem.h b/apt-pkg/edsp/edspsystem.h
new file mode 100644
index 000000000..bc5be61d1
--- /dev/null
+++ b/apt-pkg/edsp/edspsystem.h
@@ -0,0 +1,38 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+// $Id: debsystem.h,v 1.4 2003/01/11 07:16:33 jgg Exp $
+/* ######################################################################
+
+   System - Debian version of the  System Class
+
+   ##################################################################### */
+									/*}}}*/
+#ifndef PKGLIB_EDSPSYSTEM_H
+#define PKGLIB_EDSPSYSTEM_H
+
+#include <apt-pkg/pkgsystem.h>
+
+class edspIndex;
+class edspSystem : public pkgSystem
+{
+   edspIndex *StatusFile;
+
+   public:
+
+   virtual bool Lock();
+   virtual bool UnLock(bool NoErrors = false);
+   virtual pkgPackageManager *CreatePM(pkgDepCache *Cache) const;
+   virtual bool Initialize(Configuration &Cnf);
+   virtual bool ArchiveSupported(const char *Type);
+   virtual signed Score(Configuration const &Cnf);
+   virtual bool AddStatusFiles(std::vector<pkgIndexFile *> &List);
+   virtual bool FindIndex(pkgCache::PkgFileIterator File,
+			  pkgIndexFile *&Found) const;
+
+   edspSystem();
+   ~edspSystem();
+};
+
+extern edspSystem edspSys;
+
+#endif
diff --git a/apt-pkg/init.cc b/apt-pkg/init.cc
index a30f27844..aff585e3b 100644
--- a/apt-pkg/init.cc
+++ b/apt-pkg/init.cc
@@ -72,7 +72,9 @@ bool pkgInitConfig(Configuration &Cnf)
    Cnf.Set("Dir::Etc::preferencesparts","preferences.d");
    Cnf.Set("Dir::Etc::trusted", "trusted.gpg");
    Cnf.Set("Dir::Etc::trustedparts","trusted.gpg.d");
+
    Cnf.Set("Dir::Bin::methods","/usr/lib/apt/methods");
+   Cnf.Set("Dir::Bin::solvers::","/usr/lib/apt/solvers");
    Cnf.Set("Dir::Media::MountPath","/media/apt");
 
    // State   
diff --git a/apt-pkg/makefile b/apt-pkg/makefile
index 4e5ec107f..e6bcf8524 100644
--- a/apt-pkg/makefile
+++ b/apt-pkg/makefile
@@ -3,7 +3,7 @@ BASE=..
 SUBDIR=apt-pkg
 
 # Header location
-SUBDIRS = deb contrib
+SUBDIRS = deb edsp contrib
 HEADER_TARGETDIRS = apt-pkg
 
 # Bring in the default rules
@@ -35,7 +35,7 @@ SOURCE+= pkgcache.cc version.cc depcache.cc \
 	 srcrecords.cc cachefile.cc versionmatch.cc policy.cc \
 	 pkgsystem.cc indexfile.cc pkgcachegen.cc acquire-item.cc \
 	 indexrecords.cc vendor.cc vendorlist.cc cdrom.cc indexcopy.cc \
-	 aptconfiguration.cc cachefilter.cc cacheset.cc
+	 aptconfiguration.cc cachefilter.cc cacheset.cc edsp.cc
 HEADERS+= algorithms.h depcache.h pkgcachegen.h cacheiterators.h \
 	  orderlist.h sourcelist.h packagemanager.h tagfile.h \
 	  init.h pkgcache.h version.h progress.h pkgrecords.h \
@@ -43,7 +43,7 @@ HEADERS+= algorithms.h depcache.h pkgcachegen.h cacheiterators.h \
 	  clean.h srcrecords.h cachefile.h versionmatch.h policy.h \
 	  pkgsystem.h indexfile.h metaindex.h indexrecords.h vendor.h \
 	  vendorlist.h cdrom.h indexcopy.h aptconfiguration.h \
-	  cachefilter.h cacheset.h
+	  cachefilter.h cacheset.h edsp.h
 
 # Source code for the debian specific components
 # In theory the deb headers do not need to be exported..
@@ -53,6 +53,10 @@ SOURCE+= deb/deblistparser.cc deb/debrecords.cc deb/dpkgpm.cc \
 HEADERS+= debversion.h debsrcrecords.h dpkgpm.h debrecords.h \
 	  deblistparser.h debsystem.h debindexfile.h debmetaindex.h
 
+# Source code for the APT resolver interface specific components
+SOURCE+= edsp/edsplistparser.cc edsp/edspindexfile.cc edsp/edspsystem.cc
+HEADERS+= edsplistparser.h edspindexfile.h edspsystem.h
+
 HEADERS := $(addprefix apt-pkg/,$(HEADERS))
 
 include $(LIBRARY_H)
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index 9820fde81..8e088ba68 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -642,7 +642,7 @@ bool pkgCacheGenerator::FinishCache(OpProgress *Progress)
 	       bool const coInstall = ((V->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same);
 	       for (vector<string>::const_iterator A = archs.begin(); A != archs.end(); ++A)
 	       {
-		  if (*A == Arch)
+		  if (Arch == 0 || *A == Arch)
 		     continue;
 		  /* We allow only one installed arch at the time
 		     per group, therefore each group member conflicts
diff --git a/apt-pkg/policy.cc b/apt-pkg/policy.cc
index 2cc2e5e39..4fc272a74 100644
--- a/apt-pkg/policy.cc
+++ b/apt-pkg/policy.cc
@@ -282,6 +282,10 @@ signed short pkgPolicy::GetPriority(pkgCache::PkgIterator const &Pkg)
    
    return 0;
 }
+signed short pkgPolicy::GetPriority(pkgCache::PkgFileIterator const &File)
+{
+   return PFPriority[File->ID];
+}
 									/*}}}*/
 // PreferenceSection class - Overriding the default TrimRecord method	/*{{{*/
 // ---------------------------------------------------------------------
diff --git a/apt-pkg/policy.h b/apt-pkg/policy.h
index f8b2678de..e7f36d618 100644
--- a/apt-pkg/policy.h
+++ b/apt-pkg/policy.h
@@ -69,14 +69,13 @@ class pkgPolicy : public pkgDepCache::Policy
    // Things for manipulating pins
    void CreatePin(pkgVersionMatch::MatchType Type,string Pkg,
 		  string Data,signed short Priority);
-   inline signed short GetPriority(pkgCache::PkgFileIterator const &File) 
-       {return PFPriority[File->ID];};
-   signed short GetPriority(pkgCache::PkgIterator const &Pkg);
    pkgCache::VerIterator GetMatch(pkgCache::PkgIterator const &Pkg);
 
    // Things for the cache interface.
    virtual pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator const &Pkg);
-   virtual bool IsImportantDep(pkgCache::DepIterator const &Dep) {return pkgDepCache::Policy::IsImportantDep(Dep);};
+   virtual signed short GetPriority(pkgCache::PkgIterator const &Pkg);
+   virtual signed short GetPriority(pkgCache::PkgFileIterator const &File);
+
    bool InitDefaults();
    
    pkgPolicy(pkgCache *Owner);