[commit: Cabal] master: Fix infinite loop in the TopDown dependency resolver (bf2f100)

[Ian Lynagh]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/Cabal

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/bf2f100596d7db413c9a3a3a15abeeee8954c340

>---------------------------------------------------------------

commit bf2f100596d7db413c9a3a3a15abeeee8954c340
Author: Andrea Vezzosi <sanzhiyan at gmail.com>
Date:   Thu Sep 25 18:14:41 2008 +0000

    Fix infinite loop in the TopDown dependency resolver
    The loop occurred only if a package depended on another one
    with the same name, e.g. base-3.0.3.0 <- base-4.0.0.0

>---------------------------------------------------------------

 .../Distribution/Client/Dependency/TopDown.hs      |   13 +++++++++----
 1 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/cabal-install/Distribution/Client/Dependency/TopDown.hs b/cabal-install/Distribution/Client/Dependency/TopDown.hs
index cc781e9..160f3f9 100644
--- a/cabal-install/Distribution/Client/Dependency/TopDown.hs
+++ b/cabal-install/Distribution/Client/Dependency/TopDown.hs
@@ -352,7 +352,10 @@ selectNeededSubset installed available = select mempty mempty
         (next, remaining') = Set.deleteFindMin remaining
         moreInstalled = PackageIndex.lookupPackageName installed next
         moreAvailable = PackageIndex.lookupPackageName available next
-        moreRemaining = nub
+        moreRemaining = -- we filter out packages already included in the indexes
+                        -- this avoids an infinite loop if a package depends on itself
+                        -- like base-3.0.3.0 with base-4.0.0.0
+                        filter notAlreadyIncluded
                       $ [ packageName dep
                         | pkg <- moreInstalled
                         , dep <- depends pkg ]
@@ -360,9 +363,11 @@ selectNeededSubset installed available = select mempty mempty
                         | AvailablePackage _ pkg _ <- moreAvailable
                         , Dependency name _ <-
                             buildDepends (flattenPackageDescription pkg) ]
-        installed''   = foldr PackageIndex.insert installed' moreInstalled
-        available''   = foldr PackageIndex.insert available' moreAvailable
-        remaining''   = foldr          Set.insert remaining' moreRemaining
+        installed''   = foldl' (flip PackageIndex.insert) installed' moreInstalled
+        available''   = foldl' (flip PackageIndex.insert) available' moreAvailable
+        remaining''   = foldl' (flip         Set.insert) remaining' moreRemaining
+        notAlreadyIncluded name = null (PackageIndex.lookupPackageName installed' name)
+                                  && null (PackageIndex.lookupPackageName available' name)
 
 -- ------------------------------------------------------------
 -- * Post processing the solution