enable APT in unpack/configure ordering to handle loops as well

as tight dependencies between immediate packages better
enabling also the possibility to mark all packages as immediate
(at least Closes: #353290, #540227, #559733, #621836, #639290)

11 files changed, 445 insertions, 169 deletions

diff --git a/apt-pkg/deb/dpkgpm.cc b/apt-pkg/deb/dpkgpm.cc
index 2c34465c0..0cc21f322 100644
--- a/apt-pkg/deb/dpkgpm.cc
+++ b/apt-pkg/deb/dpkgpm.cc
@@ -18,6 +18,7 @@
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/fileutl.h>
 #include <apt-pkg/cachefile.h>
+#include <apt-pkg/packagemanager.h>
 
 #include <unistd.h>
 #include <stdlib.h>
@@ -937,7 +938,7 @@ bool pkgDPkgPM::Go(int OutStatusFd)
       // the argument list is split in a way that A depends on B
       // and they are in the same "--configure A B" run
       // - with the split they may now be configured in different
-      //   runs 
+      //   runs, using Immediate-Configure-All can help prevent this.
       if (J - I > (signed)MaxArgs)
 	 J = I + MaxArgs;
       
@@ -970,6 +971,8 @@ bool pkgDPkgPM::Go(int OutStatusFd)
       snprintf(status_fd_buf,sizeof(status_fd_buf),"%i", fd[1]);
       Args[n++] = status_fd_buf;
       Size += strlen(Args[n-1]);
+      
+      unsigned long const Op = I->Op;
 
       switch (I->Op)
       {
@@ -1079,8 +1082,13 @@ bool pkgDPkgPM::Go(int OutStatusFd)
 	 it to all processes in the group. Since dpkg ignores the signal 
 	 it doesn't die but we do! So we must also ignore it */
       sighandler_t old_SIGQUIT = signal(SIGQUIT,SIG_IGN);
-      sighandler_t old_SIGINT = signal(SIGINT,SIG_IGN);
-
+      sighandler_t old_SIGINT = signal(SIGINT,SigINT);
+      
+      // Check here for any SIGINT
+      if (pkgPackageManager::SigINTStop && (Op == Item::Remove || Op == Item::Purge || Op == Item::Install)) 
+         break;
+      
+      
       // ignore SIGHUP as well (debian #463030)
       sighandler_t old_SIGHUP = signal(SIGHUP,SIG_IGN);
 
@@ -1118,7 +1126,6 @@ bool pkgDPkgPM::Go(int OutStatusFd)
 	    sigprocmask(SIG_SETMASK, &original_sigmask, 0);
 	 }
       }
-
        // Fork dpkg
       pid_t Child;
       _config->Set("APT::Keep-Fds::",fd[1]);
@@ -1224,6 +1231,7 @@ bool pkgDPkgPM::Go(int OutStatusFd)
 	    // Restore sig int/quit
 	    signal(SIGQUIT,old_SIGQUIT);
 	    signal(SIGINT,old_SIGINT);
+
 	    signal(SIGHUP,old_SIGHUP);
 	    return _error->Errno("waitpid","Couldn't wait for subprocess");
 	 }
@@ -1264,6 +1272,7 @@ bool pkgDPkgPM::Go(int OutStatusFd)
       // Restore sig int/quit
       signal(SIGQUIT,old_SIGQUIT);
       signal(SIGINT,old_SIGINT);
+      
       signal(SIGHUP,old_SIGHUP);
 
       if(master >= 0) 
@@ -1301,6 +1310,9 @@ bool pkgDPkgPM::Go(int OutStatusFd)
       }      
    }
    CloseLog();
+   
+   if (pkgPackageManager::SigINTStop)
+       _error->Warning(_("Operation was interrupted before it could finish"));
 
    if (RunScripts("DPkg::Post-Invoke") == false)
       return false;
@@ -1325,6 +1337,11 @@ bool pkgDPkgPM::Go(int OutStatusFd)
    Cache.writeStateFile(NULL);
    return true;
 }
+
+void SigINT(int sig) {
+   if (_config->FindB("APT::Immediate-Configure-All",false)) 
+      pkgPackageManager::SigINTStop = true;
+} 
 									/*}}}*/
 // pkgDpkgPM::Reset - Dump the contents of the command list		/*{{{*/
 // ---------------------------------------------------------------------
diff --git a/apt-pkg/deb/dpkgpm.h b/apt-pkg/deb/dpkgpm.h
index ddf9485c7..3f95c51dc 100644
--- a/apt-pkg/deb/dpkgpm.h
+++ b/apt-pkg/deb/dpkgpm.h
@@ -106,4 +106,6 @@ class pkgDPkgPM : public pkgPackageManager
    virtual ~pkgDPkgPM();
 };
 
+void SigINT(int sig);
+
 #endif
diff --git a/apt-pkg/orderlist.cc b/apt-pkg/orderlist.cc
index 80d7b6619..0ac9a83e3 100644
--- a/apt-pkg/orderlist.cc
+++ b/apt-pkg/orderlist.cc
@@ -1059,8 +1059,10 @@ bool pkgOrderList::AddLoop(DepIterator D)
    Loops[LoopCount++] = D;
    
    // Mark the packages as being part of a loop.
-   Flag(D.TargetPkg(),Loop);
-   Flag(D.ParentPkg(),Loop);
+   //Flag(D.TargetPkg(),Loop);
+   //Flag(D.ParentPkg(),Loop);
+   /* This is currently disabled because the Loop flag is being used for
+      loop management in the package manager. Check the orderlist.h file for more info */
    return true;
 }
 									/*}}}*/
@@ -1111,7 +1113,7 @@ bool pkgOrderList::CheckDep(DepIterator D)
          just needs one */
       if (D.IsNegative() == false)
       {
-	 // ignore provides by older versions of this package
+      	 // ignore provides by older versions of this package
 	 if (((D.Reverse() == false && Pkg == D.ParentPkg()) ||
 	      (D.Reverse() == true && Pkg == D.TargetPkg())) &&
 	     Cache[Pkg].InstallVer != *I)
diff --git a/apt-pkg/orderlist.h b/apt-pkg/orderlist.h
index 264f7ba03..9588d30a5 100644
--- a/apt-pkg/orderlist.h
+++ b/apt-pkg/orderlist.h
@@ -76,7 +76,12 @@ class pkgOrderList : protected pkgCache::Namespace
 
    typedef Package **iterator;
    
-   // State flags
+   /* State flags
+      The Loop flag can be set on a package that is currently being processed by either SmartConfigure or
+      SmartUnPack. This allows the package manager to tell when a loop has been formed as it will try to 
+      SmartUnPack or SmartConfigure a package with the Loop flag set. It will then either stop (as it knows
+      that the operation is unnecessary as its already in process), or in the case of the conflicts resolution
+      in SmartUnPack, use EarlyRemove to resolve the situation.  */
    enum Flags {Added = (1 << 0), AddPending = (1 << 1),
                Immediate = (1 << 2), Loop = (1 << 3),
                UnPacked = (1 << 4), Configured = (1 << 5),
@@ -91,6 +96,9 @@ class pkgOrderList : protected pkgCache::Namespace
    void Flag(PkgIterator Pkg,unsigned long State, unsigned long F) {Flags[Pkg->ID] = (Flags[Pkg->ID] & (~F)) | State;};
    inline void Flag(PkgIterator Pkg,unsigned long F) {Flags[Pkg->ID] |= F;};
    inline void Flag(Package *Pkg,unsigned long F) {Flags[Pkg->ID] |= F;};
+   // RmFlag removes a flag from a package 
+   inline void RmFlag(Package *Pkg,unsigned long F) {Flags[Pkg->ID] &= ~F;};
+   // IsNow will return true if the Pkg has been not been either configured or unpacked
    inline bool IsNow(PkgIterator Pkg) {return (Flags[Pkg->ID] & (States & (~Removed))) == 0;};
    bool IsMissing(PkgIterator Pkg);
    void WipeFlags(unsigned long F);
diff --git a/apt-pkg/packagemanager.cc b/apt-pkg/packagemanager.cc
index c41a1f1ee..3cd9f6f00 100644
--- a/apt-pkg/packagemanager.cc
+++ b/apt-pkg/packagemanager.cc
@@ -31,6 +31,8 @@
 									/*}}}*/
 using namespace std;
 
+bool pkgPackageManager::SigINTStop = false;
+
 // PM::PackageManager - Constructor					/*{{{*/
 // ---------------------------------------------------------------------
 /* */
@@ -168,7 +170,11 @@ bool pkgPackageManager::CreateOrderList()
    delete List;
    List = new pkgOrderList(&Cache);
    
-   static bool const NoImmConfigure = !_config->FindB("APT::Immediate-Configure",true);
+   NoImmConfigure = !_config->FindB("APT::Immediate-Configure",true);
+   ImmConfigureAll = _config->FindB("APT::Immediate-Configure-All",false);
+   
+   if (Debug && ImmConfigureAll) 
+      clog << "CreateOrderList(): Adding Immediate flag for all packages because of APT::Immediate-Configure-All" << endl;
    
    // Generate the list of affected packages and sort it
    for (PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
@@ -178,19 +184,21 @@ bool pkgPackageManager::CreateOrderList()
 	 continue;
       
       // Mark the package and its dependends for immediate configuration
-      if (((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential ||
+      if ((((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential ||
 	   (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) &&
-	  NoImmConfigure == false)
+	  NoImmConfigure == false) || ImmConfigureAll)
       {
-	 if(Debug)
+	 if(Debug && !ImmConfigureAll)
 	    clog << "CreateOrderList(): Adding Immediate flag for " << I.Name() << endl;
 	 List->Flag(I,pkgOrderList::Immediate);
-
-	 // Look for other install packages to make immediate configurea
-	 ImmediateAdd(I, true);
 	 
-	 // And again with the current version.
-	 ImmediateAdd(I, false);
+	 if (!ImmConfigureAll) {
+	    // Look for other install packages to make immediate configurea
+	    ImmediateAdd(I, true);
+	  
+	    // And again with the current version.
+	    ImmediateAdd(I, false);
+	 }
       }
       
       // Not interesting
@@ -258,7 +266,8 @@ bool pkgPackageManager::CheckRConflicts(PkgIterator Pkg,DepIterator D,
 // PM::ConfigureAll - Run the all out configuration			/*{{{*/
 // ---------------------------------------------------------------------
 /* This configures every package. It is assumed they are all unpacked and
-   that the final configuration is valid. */
+   that the final configuration is valid. This is also used to catch packages
+   that have not been configured when using ImmConfigureAll */
 bool pkgPackageManager::ConfigureAll()
 {
    pkgOrderList OList(&Cache);
@@ -279,9 +288,19 @@ bool pkgPackageManager::ConfigureAll()
    for (pkgOrderList::iterator I = OList.begin(); I != OList.end(); ++I)
    {
       PkgIterator Pkg(Cache,*I);
+      
+      /* Check if the package has been configured, this can happen if SmartConfigure
+         calls its self */ 
+      if (List->IsFlag(Pkg,pkgOrderList::Configured)) continue;
 
-      if (ConfigurePkgs == true && Configure(Pkg) == false)
+      if (ConfigurePkgs == true && SmartConfigure(Pkg, 0) == false) {
+         if (ImmConfigureAll)
+            _error->Error(_("Could not perform immediate configuration on '%s'. "
+			"Please see man 5 apt.conf under APT::Immediate-Configure for details. (%d)"),Pkg.Name(),1);
+         else
+            _error->Error("Internal error, packages left unconfigured. %s",Pkg.Name());
 	 return false;
+      }
       
       List->Flag(Pkg,pkgOrderList::Configured,pkgOrderList::States);
    }
@@ -291,35 +310,141 @@ bool pkgPackageManager::ConfigureAll()
 									/*}}}*/
 // PM::SmartConfigure - Perform immediate configuration of the pkg	/*{{{*/
 // ---------------------------------------------------------------------
-/* This routine scheduals the configuration of the given package and all
-   of it's dependents. */
-bool pkgPackageManager::SmartConfigure(PkgIterator Pkg)
+/* This function tries to put the system in a state where Pkg can be configured.
+   This involves checking each of Pkg's dependanies and unpacking and 
+   configuring packages where needed. 
+   
+   Note on failure: This method can fail, without causing any problems. 
+   This can happen when using Immediate-Configure-All, SmartUnPack may call
+   SmartConfigure, it may fail because of a complex dependancy situation, but
+   a error will only be reported if ConfigureAll fails. This is why some of the
+   messages this function reports on failure (return false;) as just warnings
+   only shown when debuging*/
+bool pkgPackageManager::SmartConfigure(PkgIterator Pkg, int const Depth)
 {
-   if (Debug == true)
-      clog << "SmartConfigure " << Pkg.Name() << endl;
+   // If this is true, only check and correct and dependancies without the Loop flag
+   bool PkgLoop = List->IsFlag(Pkg,pkgOrderList::Loop);
+
+   if (Debug) {
+      VerIterator InstallVer = VerIterator(Cache,Cache[Pkg].InstallVer);
+      clog << OutputInDepth(Depth) << "SmartConfigure " << Pkg.Name() << " (" << InstallVer.VerStr() << ")";
+      if (PkgLoop)
+        clog << " (Only Correct Dependancies)";
+      clog << endl;
+   }
 
-   pkgOrderList OList(&Cache);
+   VerIterator const instVer = Cache[Pkg].InstVerIter(Cache);
+      
+   /* Because of the ordered list, most dependancies should be unpacked, 
+      however if there is a loop (A depends on B, B depends on A) this will not 
+      be the case, so check for dependancies before configuring. */
+   bool Bad = false;
+   for (DepIterator D = instVer.DependsList();
+	D.end() == false; )
+   {
+      // Compute a single dependency element (glob or)
+      pkgCache::DepIterator Start;
+      pkgCache::DepIterator End;
+      D.GlobOr(Start,End);
+      
+      if (End->Type == pkgCache::Dep::Depends) 
+          Bad = true;
+
+      // Check for dependanices that have not been unpacked, probably due to loops.
+      while (End->Type == pkgCache::Dep::Depends) {
+         PkgIterator DepPkg;
+         VerIterator InstallVer;
+         SPtrArray<Version *> VList = Start.AllTargets();
+         
+         // Check through each version of each package that could satisfy this dependancy
+	 for (Version **I = VList; *I != 0; I++) {
+	    VerIterator Ver(Cache,*I);
+	    DepPkg = Ver.ParentPkg();
+	    InstallVer = VerIterator(Cache,Cache[DepPkg].InstallVer);
 
-   if (DepAdd(OList,Pkg) == false)
+	    // Check if the current version of the package is avalible and will satisfy this dependancy
+	    if (DepPkg.CurrentVer() == Ver && List->IsNow(DepPkg) == true && 
+		!List->IsFlag(DepPkg,pkgOrderList::Removed) && DepPkg.State() == PkgIterator::NeedsNothing)
+	    {
+	       Bad = false;
+	       break;
+	    }
+	    
+	    // Check if the version that is going to be installed will satisfy the dependancy
+	    if (Cache[DepPkg].InstallVer == *I) {
+	       if (List->IsFlag(DepPkg,pkgOrderList::UnPacked)) {
+	          if (List->IsFlag(DepPkg,pkgOrderList::Loop) && PkgLoop) {
+	            // This dependancy has already been dealt with by another SmartConfigure on Pkg
+	            Bad = false;
+	            break;
+                  } else if (List->IsFlag(Pkg,pkgOrderList::Loop)) {
+	            /* Check for a loop to prevent one forming
+	               If A depends on B and B depends on A, SmartConfigure will
+	               just hop between them if this is not checked. Dont remove the 
+	               loop flag after finishing however as loop is already set.
+	               This means that there is another SmartConfigure call for this 
+	               package and it will remove the loop flag */
+	             Bad = !SmartConfigure(DepPkg, Depth + 1);
+	          } else {
+	            /* Check for a loop to prevent one forming
+	               If A depends on B and B depends on A, SmartConfigure will
+	               just hop between them if this is not checked */
+	            List->Flag(Pkg,pkgOrderList::Loop);
+	            Bad = !SmartConfigure(DepPkg, Depth + 1);
+	            List->RmFlag(Pkg,pkgOrderList::Loop);
+	          }
+	          // If SmartConfigure was succesfull, Bad is false, so break
+	          if (!Bad) break;
+	       } else if (List->IsFlag(DepPkg,pkgOrderList::Configured)) {
+	          Bad = false;
+	          break;
+	       }
+	    }
+	 }
+	 
+	 /* If the dependany is still not satisfied, try, if possible, unpacking a package to satisfy it */
+	 if (InstallVer != 0 && Bad) {
+	    Bad = false;
+	    if (List->IsNow(DepPkg) && !List->IsFlag(DepPkg,pkgOrderList::Loop)) {
+	       List->Flag(Pkg,pkgOrderList::Loop);
+	       if (Debug) 
+	          cout << OutputInDepth(Depth) << "Unpacking " << DepPkg.Name() << " to avoid loop" << endl;
+	       SmartUnPack(DepPkg, true, Depth + 1);
+	       List->RmFlag(Pkg,pkgOrderList::Loop);
+	    }
+	 }
+	 
+	 if (Start==End) {
+	    if (Bad && Debug) {
+	       if (!List->IsFlag(DepPkg,pkgOrderList::Loop)) {
+                  _error->Warning("Could not satisfy dependancies for %s",Pkg.Name());
+               } 
+	    }
+	    break;
+	 } else {
+            Start++;
+         }
+      }
+   }
+   
+   if (Bad) {
+      if (Debug)
+         _error->Warning(_("Could not configure '%s'. "),Pkg.Name());
       return false;
+   }
+   
+   if (PkgLoop) return true;
 
    static std::string const conf = _config->Find("PackageManager::Configure","all");
    static bool const ConfigurePkgs = (conf == "all" || conf == "smart");
 
-   if (ConfigurePkgs == true)
-      if (OList.OrderConfigure() == false)
-	 return false;
+   if (List->IsFlag(Pkg,pkgOrderList::Configured)) 
+      return _error->Error("Internal configure error on '%s'. ",Pkg.Name(),1);
 
-   // Perform the configuring
-   for (pkgOrderList::iterator I = OList.begin(); I != OList.end(); ++I)
-   {
-      PkgIterator Pkg(Cache,*I);
-      
-      if (ConfigurePkgs == true && Configure(Pkg) == false)
-	 return false;
-      
-      List->Flag(Pkg,pkgOrderList::Configured,pkgOrderList::States);
-   }
+   if (ConfigurePkgs == true && Configure(Pkg) == false)
+      return false;
+
+   List->Flag(Pkg,pkgOrderList::Configured,pkgOrderList::States);
 
    if ((Cache[Pkg].InstVerIter(Cache)->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
       for (PkgIterator P = Pkg.Group().PackageList();
@@ -329,97 +454,16 @@ bool pkgPackageManager::SmartConfigure(PkgIterator Pkg)
 	     Cache[P].InstallVer == 0 || (P.CurrentVer() == Cache[P].InstallVer &&
 	      (Cache[Pkg].iFlags & pkgDepCache::ReInstall) != pkgDepCache::ReInstall))
 	    continue;
-	 SmartConfigure(P);
+	 SmartConfigure(P, (Depth +1));
       }
 
    // Sanity Check
    if (List->IsFlag(Pkg,pkgOrderList::Configured) == false)
-      return _error->Error(_("Could not perform immediate configuration on '%s'. "
-			"Please see man 5 apt.conf under APT::Immediate-Configure for details. (%d)"),Pkg.Name(),1);
+      return _error->Error(_("Could not configure '%s'. "),Pkg.Name());
 
    return true;
 }
 									/*}}}*/
-// PM::DepAdd - Add all dependents to the oder list			/*{{{*/
-// ---------------------------------------------------------------------
-/* This recursively adds all dependents to the order list */
-bool pkgPackageManager::DepAdd(pkgOrderList &OList,PkgIterator Pkg,int Depth)
-{
-   if (OList.IsFlag(Pkg,pkgOrderList::Added) == true)
-      return true;
-   if (List->IsFlag(Pkg,pkgOrderList::Configured) == true)
-      return true;
-   if (List->IsFlag(Pkg,pkgOrderList::UnPacked) == false)
-      return false;
-
-   if (Debug) 
-      std::clog << OutputInDepth(Depth) << "DepAdd: " << Pkg.Name() << std::endl;
-      
-   // Put the package on the list
-   OList.push_back(Pkg);
-   OList.Flag(Pkg,pkgOrderList::Added);
-   Depth++;
-
-   // Check the dependencies to see if they are all satisfied.
-   bool Bad = false;
-   for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
-   {
-      if (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends)
-      {
-	 ++D;
-	 continue;
-      }
-      
-      // Grok or groups
-      Bad = true;
-      for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
-      {
-	 LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
-	 
-	 if (Bad == false)
-	    continue;
-
-	 SPtrArray<Version *> VList = D.AllTargets();
-	 for (Version **I = VList; *I != 0 && Bad == true; ++I)
-	 {
-	    VerIterator Ver(Cache,*I);
-	    PkgIterator Pkg = Ver.ParentPkg();
-
-	    // See if the current version is ok
-	    if (Pkg.CurrentVer() == Ver && List->IsNow(Pkg) == true && 
-		Pkg.State() == PkgIterator::NeedsNothing)
-	    {
-	       Bad = false;
-	       continue;
-	    }
-	    
-	    // Not the install version 
-	    if (Cache[Pkg].InstallVer != *I || 
-		(Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing))
-	       continue;
-	    
-	    if (List->IsFlag(Pkg,pkgOrderList::UnPacked) == true)
-	       Bad = !DepAdd(OList,Pkg,Depth);
-	    if (List->IsFlag(Pkg,pkgOrderList::Configured) == true)
-	       Bad = false;
-	 }
-      }
-      
-      if (Bad == true)
-      {
-	 if (Debug) 
-	    std::clog << OutputInDepth(Depth) << "DepAdd FAILS on: " << Pkg.Name() << std::endl;
-	 OList.Flag(Pkg,0,pkgOrderList::Added);
-	 OList.pop_back();
-	 Depth--;
-	 return false;
-      }
-   }
-   
-   Depth--;
-   return true;
-}
-									/*}}}*/
 // PM::EarlyRemove - Perform removal of packages before their time	/*{{{*/
 // ---------------------------------------------------------------------
 /* This is called to deal with conflicts arising from unpacking */
@@ -485,30 +529,44 @@ bool pkgPackageManager::SmartRemove(PkgIterator Pkg)
 									/*}}}*/
 // PM::SmartUnPack - Install helper					/*{{{*/
 // ---------------------------------------------------------------------
-/* This performs the task of handling pre-depends. */
+/* This puts the system in a state where it can Unpack Pkg, if Pkg is allready
+   unpacked, or when it has been unpacked, if Immediate==true it configures it. */
 bool pkgPackageManager::SmartUnPack(PkgIterator Pkg)
 {
-   return SmartUnPack(Pkg, true);
+   return SmartUnPack(Pkg, true, 0);
 }
-bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
+bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate, int const Depth)
 {
+   bool PkgLoop = List->IsFlag(Pkg,pkgOrderList::Loop);
+
+   if (Debug) {
+      clog << OutputInDepth(Depth) << "SmartUnPack " << Pkg.Name();
+      VerIterator InstallVer = VerIterator(Cache,Cache[Pkg].InstallVer);
+      if (Pkg.CurrentVer() == 0)
+        cout << " (install version " << InstallVer.VerStr() << ")";
+      else
+        cout << " (replace version " << Pkg.CurrentVer().VerStr() << " with " << InstallVer.VerStr() << ")";
+      if (PkgLoop)
+        cout << " (Only Perform PreUnpack Checks)";
+      cout << endl;
+   }
+
    // Check if it is already unpacked
    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
        Cache[Pkg].Keep() == true)
    {
-      List->Flag(Pkg,pkgOrderList::UnPacked,pkgOrderList::States);
-      if (Immediate == true &&
-	  List->IsFlag(Pkg,pkgOrderList::Immediate) == true)
-	 if (SmartConfigure(Pkg) == false)
-	    return _error->Error(_("Could not perform immediate configuration on already unpacked '%s'. "
-			"Please see man 5 apt.conf under APT::Immediate-Configure for details."),Pkg.Name());
-      return true;
+      cout << OutputInDepth(Depth) << "SmartUnPack called on Package " << Pkg.Name() << " but its unpacked" << endl;
+      return false;
    }
-
+ 
    VerIterator const instVer = Cache[Pkg].InstVerIter(Cache);
 
-   /* See if this packages install version has any predependencies
-      that are not met by 'now' packages. */
+   /* PreUnpack Checks: This loop checks and attempts to rectify and problems that would prevent the package being unpacked.
+      It addresses: PreDepends, Conflicts, Obsoletes and Breaks (DpkgBreaks). Any resolutions that do not require it should 
+      avoid configuration (calling SmartUnpack with Immediate=true), this is because when unpacking some packages with
+      complex dependancy structures, trying to configure some packages while breaking the loops can complicate things . 
+      This will be either dealt with if the package is configured as a dependency of Pkg (if and when Pkg is configured), 
+      or by the ConfigureAll call at the end of the for loop in OrderInstall. */
    for (DepIterator D = instVer.DependsList();
 	D.end() == false; )
    {
@@ -519,8 +577,8 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
       
       while (End->Type == pkgCache::Dep::PreDepends)
       {
-	 if (Debug == true)
-	    clog << "PreDepends order for " << Pkg.Name() << std::endl;
+	 if (Debug)
+	    clog << OutputInDepth(Depth) << "PreDepends order for " << Pkg.Name() << std::endl;
 
 	 // Look for possible ok targets.
 	 SPtrArray<Version *> VList = Start.AllTargets();
@@ -535,8 +593,8 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
 		Pkg.State() == PkgIterator::NeedsNothing)
 	    {
 	       Bad = false;
-	       if (Debug == true)
-		  clog << "Found ok package " << Pkg.Name() << endl;
+	       if (Debug)
+		  clog << OutputInDepth(Depth) << "Found ok package " << Pkg.Name() << endl;
 	       continue;
 	    }
 	 }
@@ -551,10 +609,15 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
 	    if (Cache[Pkg].InstallVer != *I || 
 		(Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing))
 	       continue;
+	       
+	    if (List->IsFlag(Pkg,pkgOrderList::Configured)) {
+	       Bad = false;
+	       continue;
+	    }
 
-	    if (Debug == true)
-	       clog << "Trying to SmartConfigure " << Pkg.Name() << endl;
-	    Bad = !SmartConfigure(Pkg);
+	    if (Debug)
+	       clog << OutputInDepth(Depth) << "Trying to SmartConfigure " << Pkg.Name() << endl;
+	    Bad = !SmartConfigure(Pkg, Depth + 1);
 	 }
 
 	 /* If this or element did not match then continue on to the
@@ -568,7 +631,7 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
 				    End.TargetPkg().Name(),Pkg.Name());
 	    ++Start;
 	 }
-	 else
+	 else 
 	    break;
       }
       
@@ -581,28 +644,96 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
 	 for (Version **I = VList; *I != 0; I++)
 	 {
 	    VerIterator Ver(Cache,*I);
-	    PkgIterator Pkg = Ver.ParentPkg();
+	    PkgIterator ConflictPkg = Ver.ParentPkg();
+	    VerIterator InstallVer(Cache,Cache[ConflictPkg].InstallVer);
 	    
 	    // See if the current version is conflicting
-	    if (Pkg.CurrentVer() == Ver && List->IsNow(Pkg) == true)
-	    {
-	       if (EarlyRemove(Pkg) == false)
-		  return _error->Error("Internal Error, Could not early remove %s",Pkg.Name());
+	    if (ConflictPkg.CurrentVer() == Ver && List->IsNow(ConflictPkg))
+	    { 
+	       cout << OutputInDepth(Depth) << Pkg.Name() << " conflicts with " << ConflictPkg.Name() << endl;
+	       /* If a loop is not present or has not yet been detected, attempt to unpack packages 
+	          to resolve this conflict. If there is a loop present, remove packages to resolve this conflict */
+	       if (!List->IsFlag(ConflictPkg,pkgOrderList::Loop)) {
+	          if (Cache[ConflictPkg].Keep() == 0 && Cache[ConflictPkg].InstallVer != 0) {
+	              if (Debug)
+                        cout << OutputInDepth(Depth) << OutputInDepth(Depth) << "Unpacking " << ConflictPkg.Name() << " to prevent conflict" << endl;
+                      List->Flag(Pkg,pkgOrderList::Loop);
+	              SmartUnPack(ConflictPkg,false, Depth + 1);
+	              // Remove loop to allow it to be used later if needed
+	              List->RmFlag(Pkg,pkgOrderList::Loop);
+                  } else {
+                      if (EarlyRemove(ConflictPkg) == false)
+                         return _error->Error("Internal Error, Could not early remove %s",ConflictPkg.Name());
+                  }
+	       } else {
+	          if (!List->IsFlag(ConflictPkg,pkgOrderList::Removed)) {
+	              if (Debug)
+                         cout << OutputInDepth(Depth) << "Because of conficts knot, removing " << ConflictPkg.Name() << " to conflict violation" << endl;
+	              if (EarlyRemove(ConflictPkg) == false)
+                          return _error->Error("Internal Error, Could not early remove %s",ConflictPkg.Name());
+	          }
+	       }
+	    }
+	 }
+      }
+      
+      // Check for breaks
+      if (End->Type == pkgCache::Dep::DpkgBreaks) {
+         SPtrArray<Version *> VList = End.AllTargets();
+	 for (Version **I = VList; *I != 0; I++)
+	 {
+	    VerIterator Ver(Cache,*I);
+	    PkgIterator BrokenPkg = Ver.ParentPkg();
+	    VerIterator InstallVer(Cache,Cache[BrokenPkg].InstallVer);
+	    
+	    // Check if it needs to be unpacked
+	    if (List->IsFlag(BrokenPkg,pkgOrderList::InList) && Cache[BrokenPkg].Delete() == false && 
+	        List->IsNow(BrokenPkg)) {
+	      if (List->IsFlag(BrokenPkg,pkgOrderList::Loop) && PkgLoop) {
+	        // This dependancy has already been dealt with by another SmartUnPack on Pkg
+	        break;
+	      } else if (List->IsFlag(Pkg,pkgOrderList::Loop)) {
+	        /* Found a break, so unpack the package, but dont remove loop as already set.
+	           This means that there is another SmartUnPack call for this 
+	           package and it will remove the loop flag. */
+	        if (Debug) 
+	          cout << OutputInDepth(Depth) << "  Unpacking " << BrokenPkg.Name() << " to avoid break" << endl;
+	            
+	        SmartUnPack(BrokenPkg, false, Depth + 1);
+	      } else {
+                List->Flag(Pkg,pkgOrderList::Loop);
+	        // Found a break, so unpack the package
+	        if (Debug) 
+	          cout << OutputInDepth(Depth) << "  Unpacking " << BrokenPkg.Name() << " to avoid break" << endl;
+	         
+	        SmartUnPack(BrokenPkg, false, Depth + 1);
+	        List->RmFlag(Pkg,pkgOrderList::Loop);
+	      }
+	    }
+	    
+	    // Check if a package needs to be removed
+	    if (Cache[BrokenPkg].Delete() == true && !List->IsFlag(BrokenPkg,pkgOrderList::Configured)) {
+	      if (Debug) 
+	         cout << OutputInDepth(Depth) << "  Removing " << BrokenPkg.Name() << " to avoid break" << endl;
+	      SmartRemove(BrokenPkg);
 	    }
 	 }
       }
    }
-
+   
    // Check for reverse conflicts.
    if (CheckRConflicts(Pkg,Pkg.RevDependsList(),
 		   instVer.VerStr()) == false)
-      return false;
+		          return false;
    
    for (PrvIterator P = instVer.ProvidesList();
 	P.end() == false; ++P)
       if (Pkg->Group != P.OwnerPkg()->Group)
 	 CheckRConflicts(Pkg,P.ParentPkg().RevDependsList(),P.ProvideVersion());
 
+   if (PkgLoop)
+      return true;
+
    List->Flag(Pkg,pkgOrderList::UnPacked,pkgOrderList::States);
 
    if (Immediate == true && instVer->MultiArch == pkgCache::Version::Same)
@@ -621,7 +752,7 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
 	     Cache[P].InstallVer == 0 || (P.CurrentVer() == Cache[P].InstallVer &&
 	      (Cache[Pkg].iFlags & pkgDepCache::ReInstall) != pkgDepCache::ReInstall))
 	    continue;
-	 if (SmartUnPack(P, false) == false)
+	 if (SmartUnPack(P, false, Depth + 1) == false)
 	    return false;
       }
       if (installed == false && Install(Pkg,FileNames[Pkg->ID]) == false)
@@ -633,19 +764,19 @@ bool pkgPackageManager::SmartUnPack(PkgIterator Pkg, bool const Immediate)
 	     Cache[P].InstallVer == 0 || (P.CurrentVer() == Cache[P].InstallVer &&
 	      (Cache[Pkg].iFlags & pkgDepCache::ReInstall) != pkgDepCache::ReInstall))
 	    continue;
-	 if (SmartUnPack(P, false) == false)
+	 if (SmartUnPack(P, false, Depth + 1) == false)
 	    return false;
       }
    }
    else if (Install(Pkg,FileNames[Pkg->ID]) == false)
       return false;
 
-   // Perform immedate configuration of the package.
-   if (Immediate == true &&
-       List->IsFlag(Pkg,pkgOrderList::Immediate) == true)
-      if (SmartConfigure(Pkg) == false)
-	 return _error->Error(_("Could not perform immediate configuration on '%s'. "
-			"Please see man 5 apt.conf under APT::Immediate-Configure for details. (%d)"),Pkg.Name(),2);
+   if (Immediate == true) {
+      // Perform immedate configuration of the package. 
+         if (SmartConfigure(Pkg, Depth + 1) == false)
+            _error->Warning(_("Could not perform immediate configuration on '%s'. "
+               "Please see man 5 apt.conf under APT::Immediate-Configure for details. (%d)"),Pkg.Name(),2);
+   }
    
    return true;
 }
@@ -679,12 +810,19 @@ pkgPackageManager::OrderResult pkgPackageManager::OrderInstall()
    for (pkgOrderList::iterator I = List->begin(); I != List->end(); ++I)
    {
       PkgIterator Pkg(Cache,*I);
-
+      
       if (List->IsNow(Pkg) == false)
       {
-	 if (Debug == true)
-	    clog << "Skipping already done " << Pkg.Name() << endl;
+         if (!List->IsFlag(Pkg,pkgOrderList::Configured) && !NoImmConfigure) {
+            if (SmartConfigure(Pkg, 0) == false && Debug)
+               _error->Warning("Internal Error, Could not configure %s",Pkg.Name());
+            // FIXME: The above warning message might need changing
+         } else {
+	    if (Debug == true)
+	       clog << "Skipping already done " << Pkg.Name() << endl;
+	 }
 	 continue;
+	 
       }
       
       if (List->IsMissing(Pkg) == true)
@@ -715,9 +853,16 @@ pkgPackageManager::OrderResult pkgPackageManager::OrderInstall()
 	    return Failed;
       }
       else
-	 if (SmartUnPack(Pkg) == false)
+	 if (SmartUnPack(Pkg,List->IsFlag(Pkg,pkgOrderList::Immediate),0) == false)
 	    return Failed;
       DoneSomething = true;
+      
+      if (ImmConfigureAll) {
+         /* ConfigureAll here to pick up and packages left unconfigured becuase they were unpacked in the 
+            "PreUnpack Checks" section */
+         if (!ConfigureAll())
+            return Failed; 
+      }
    }
 
    // Final run through the configure phase
@@ -733,7 +878,7 @@ pkgPackageManager::OrderResult pkgPackageManager::OrderInstall()
 		       PkgIterator(Cache,*I).Name());
 	 return Failed;
       }
-   }   
+   }
 	 
    return Completed;
 }
@@ -765,4 +910,4 @@ pkgPackageManager::OrderResult pkgPackageManager::DoInstall(int statusFd)
    
    return DoInstallPostFork(statusFd);
 }
-									/*}}}*/
+									/*}}}*/	      
diff --git a/apt-pkg/packagemanager.h b/apt-pkg/packagemanager.h
index 053b4dc13..96dc5f236 100644
--- a/apt-pkg/packagemanager.h
+++ b/apt-pkg/packagemanager.h
@@ -42,12 +42,15 @@ class pkgPackageManager : protected pkgCache::Namespace
    public:
    
    enum OrderResult {Completed,Failed,Incomplete};
+   static bool SigINTStop;
    
    protected:
    string *FileNames;
    pkgDepCache &Cache;
    pkgOrderList *List;
    bool Debug;
+   bool NoImmConfigure;
+   bool ImmConfigureAll;
 
    /** \brief saves packages dpkg let disappear
 
@@ -57,7 +60,6 @@ class pkgPackageManager : protected pkgCache::Namespace
    */
    std::set<std::string> disappearedPkgs;
 
-   bool DepAdd(pkgOrderList &Order,PkgIterator P,int Depth = 0);
    void ImmediateAdd(PkgIterator P, bool UseInstallVer, unsigned const int &Depth = 0);
    virtual OrderResult OrderInstall();
    bool CheckRConflicts(PkgIterator Pkg,DepIterator Dep,const char *Ver);
@@ -68,12 +70,12 @@ class pkgPackageManager : protected pkgCache::Namespace
    
    // Install helpers
    bool ConfigureAll();
-   bool SmartConfigure(PkgIterator Pkg);
+   bool SmartConfigure(PkgIterator Pkg, int const Depth);
    //FIXME: merge on abi break
    bool SmartUnPack(PkgIterator Pkg);
-   bool SmartUnPack(PkgIterator Pkg, bool const Immediate);
+   bool SmartUnPack(PkgIterator Pkg, bool const Immediate, int const Depth);
    bool SmartRemove(PkgIterator Pkg);
-   bool EarlyRemove(PkgIterator Pkg);   
+   bool EarlyRemove(PkgIterator Pkg);  
    
    // The Actual installation implementation
    virtual bool Install(PkgIterator /*Pkg*/,string /*File*/) {return false;};
diff --git a/debian/changelog b/debian/changelog
index 62bbdcdd8..444a99ba7 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,5 +1,11 @@
 apt (0.8.16~exp6) experimental; urgency=low
 
+  [ Christopher Baines ]
+  * enable APT in unpack/configure ordering to handle loops as well
+    as tight dependencies between immediate packages better
+    enabling also the possibility to mark all packages as immediate
+    (at least Closes: #353290, #540227, #559733, #621836, #639290)
+
   [ David Kalnischkies ]
   * [abi-break] Support large files in the complete toolset. Indexes of this
     size are pretty unlikely for now, but we need it for deb
diff --git a/test/integration/test-bug-618288-multiarch-same-lockstep b/test/integration/test-bug-618288-multiarch-same-lockstep
index a05f03df4..7333054cc 100755
--- a/test/integration/test-bug-618288-multiarch-same-lockstep
+++ b/test/integration/test-bug-618288-multiarch-same-lockstep
@@ -17,7 +17,8 @@ buildsimplenativepackage 'apt2' 'amd64' '2' 'unstable' 'Depends: libsame (= 2)'
 
 setupaptarchive
 
-testequal 'Reading package lists...
+# order in switch libsame:{amd64,i386} are unpacked is irrelevant, as both are installed - but we need to do it together
+testequalor2 'Reading package lists...
 Building dependency tree...
 The following packages will be upgraded:
   apt:i386 apt2 libsame libsame:i386
@@ -29,4 +30,16 @@ Conf libsame (2 unstable [amd64]) [apt2:amd64 apt:i386 ]
 Inst apt2 [1] (2 unstable [amd64]) [apt:i386 ]
 Conf apt2 (2 unstable [amd64]) [apt:i386 ]
 Inst apt:i386 [1] (2 unstable [i386])
+Conf apt:i386 (2 unstable [i386])' 'Reading package lists...
+Building dependency tree...
+The following packages will be upgraded:
+  apt:i386 apt2 libsame libsame:i386
+4 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
+Inst libsame [1] (2 unstable [amd64]) [libsame:amd64 on libsame:i386] [libsame:i386 on libsame:amd64] [libsame:i386 apt2:amd64 ]
+Inst libsame:i386 [1] (2 unstable [i386]) [apt2:amd64 apt:i386 ]
+Conf libsame:i386 (2 unstable [i386]) [apt2:amd64 apt:i386 ]
+Conf libsame (2 unstable [amd64]) [apt2:amd64 apt:i386 ]
+Inst apt2 [1] (2 unstable [amd64]) [apt:i386 ]
+Conf apt2 (2 unstable [amd64]) [apt:i386 ]
+Inst apt:i386 [1] (2 unstable [i386])
 Conf apt:i386 (2 unstable [i386])' aptget dist-upgrade -s
diff --git a/test/integration/test-conflicts-loop b/test/integration/test-conflicts-loop
new file mode 100755
index 000000000..f76c016fb
--- /dev/null
+++ b/test/integration/test-conflicts-loop
@@ -0,0 +1,18 @@
+#!/bin/sh
+set -e
+
+TESTDIR=$(readlink -f $(dirname $0))
+. $TESTDIR/framework
+setupenvironment
+configarchitecture "i386"
+
+insertinstalledpackage 'openjdk-6-jre' 'i386' '6b16-1.8-0ubuntu1' 
+insertpackage 'unstable' 'openjdk-6-jre' 'i386' '6b20-1.9.8-0ubuntu1~10.04.1' 'Conflicts: openjdk-6-jre-headless (<< 6b17~pre3-1), openjdk-6-jre-lib (<< 6b17~pre3-1)'
+insertinstalledpackage 'openjdk-6-jre-lib' 'i386' '6b16-1.8-0ubuntu1' 
+insertpackage 'unstable' 'openjdk-6-jre-lib' 'i386' '6b20-1.9.8-0ubuntu1~10.04.1' 'Conflicts:  openjdk-6-jre (<< 6b17~pre3-1), openjdk-6-jre-headless (<< 6b17~pre3-1)'
+insertinstalledpackage 'openjdk-6-jre-headless' 'i386' '6b16-1.8-0ubuntu1' 
+insertpackage 'unstable' 'openjdk-6-jre-headless' 'i386' '6b20-1.9.8-0ubuntu1~10.04.1' 'Conflicts:  openjdk-6-jre (<< 6b17~pre3-1), openjdk-6-jre-lib (<< 6b17~pre3-1)'
+
+setupaptarchive
+
+aptget dist-upgrade -s -o Debug::pkgPackageManager=true -o Debug::pkgDpkgPM=true -o APT::Immediate-Configure-All=true
diff --git a/test/integration/test-package-reinstallation b/test/integration/test-package-reinstallation
new file mode 100755
index 000000000..359f69284
--- /dev/null
+++ b/test/integration/test-package-reinstallation
@@ -0,0 +1,17 @@
+#!/bin/sh
+set -e
+
+TESTDIR=$(readlink -f $(dirname $0))
+. $TESTDIR/framework
+setupenvironment
+configarchitecture "i386"
+
+insertinstalledpackage 'libc-bin' 'i386' '2.13-8' 'Replaces: libc6'
+insertpackage 'unstable' 'libc-bin' 'i386' '2.13-8' 'Replaces: libc6'
+insertinstalledpackage 'libc6' 'i386' '2.13-8' 'Depends: libc-bin (= 2.13-8)'
+insertpackage 'unstable' 'libc6' 'i386' '2.13-8' 'Depends: libc-bin (= 2.13-8)'
+insertinstalledpackage 'apt' 'i386' '0.8.15' 'Depends: libc6'
+
+setupaptarchive
+
+aptget install --reinstall libc6 libc-bin -s -o Debug::pkgPackageManager=1
diff --git a/test/integration/test-provides-gone-with-upgrade b/test/integration/test-provides-gone-with-upgrade
new file mode 100755
index 000000000..ece2eaa41
--- /dev/null
+++ b/test/integration/test-provides-gone-with-upgrade
@@ -0,0 +1,46 @@
+#!/bin/sh
+set -e
+
+TESTDIR=$(readlink -f $(dirname $0))
+. $TESTDIR/framework
+setupenvironment
+configarchitecture "i386"
+
+insertinstalledpackage 'apt' 'i386' '0.8.14' 'Provides: libapt-pkg4.10'
+insertpackage 'unstable' 'apt' 'i386' '0.8.15' 'Depends: libapt-pkg4.10'
+insertpackage 'unstable' 'libapt-pkg4.10' 'i386' '0.8.15' 'Breaks: apt (<< 0.8.15)
+Replaces: apt (<< 0.8.15)'
+
+setupaptarchive
+
+#testequal 'Reading package lists...
+#Building dependency tree...
+#The following NEW packages will be installed:
+#  libapt-pkg4.10
+#The following packages will be upgraded:
+#  apt
+#1 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+#Inst libapt-pkg4.10 (0.8.15 unstable [i386]) [libapt-pkg4.10:i386 on apt:i386] []
+#Conf libapt-pkg4.10:i386 broken
+# Breaks:apt:i386
+# []
+#Inst apt [0.8.14] (0.8.15 unstable [i386])
+#Conf apt (0.8.15 unstable [i386])
+#E: Conf Broken libapt-pkg4.10:i386' 
+aptget dist-upgrade -s -o Debug::pkgPackageManager=1
+# the solution by dpkg will be to deconfigure apt with the configuration of libapt-pkg4.10
+
+exit 0
+
+#FIXME: a good result would be this instead, but it requires that APT can delay his immediate configuration…
+testequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  libapt-pkg4.10
+The following packages will be upgraded:
+  apt
+1 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst libapt-pkg4.10 (0.8.15 unstable [i386])
+Conf libapt-pkg4.10 (0.8.15 unstable [i386])
+Inst apt [0.8.14] (0.8.15 unstable [i386])
+Conf apt (0.8.15 unstable [i386])' aptget dist-upgrade -s