PackageIndex.hs 26.2 KB
Newer Older
1
{-# LANGUAGE CPP #-}
ttuegel's avatar
ttuegel committed
2 3
{-# LANGUAGE DeriveGeneric #-}

4 5
-----------------------------------------------------------------------------
-- |
6
-- Module      :  Distribution.Simple.PackageIndex
7 8
-- Copyright   :  (c) David Himmelstrup 2005,
--                    Bjorn Bringert 2007,
Duncan Coutts's avatar
Duncan Coutts committed
9
--                    Duncan Coutts 2008-2009
10
--
Duncan Coutts's avatar
Duncan Coutts committed
11
-- Maintainer  :  cabal-devel@haskell.org
12 13
-- Portability :  portable
--
14
-- An index of packages.
Duncan Coutts's avatar
Duncan Coutts committed
15
--
16 17
module Distribution.Simple.PackageIndex (
  -- * Package index data type
18
  InstalledPackageIndex,
19
  PackageIndex,
20
  FakeMap,
21

22
  -- * Creating an index
23 24
  fromList,

25
  -- * Updates
26
  merge,
Duncan Coutts's avatar
Duncan Coutts committed
27

28
  insert,
Duncan Coutts's avatar
Duncan Coutts committed
29 30 31

  deleteInstalledPackageId,
  deleteSourcePackageId,
32
  deletePackageName,
Duncan Coutts's avatar
Duncan Coutts committed
33
--  deleteDependency,
34 35 36 37

  -- * Queries

  -- ** Precise lookups
Duncan Coutts's avatar
Duncan Coutts committed
38 39
  lookupInstalledPackageId,
  lookupSourcePackageId,
40
  lookupPackageId,
41
  lookupPackageName,
42 43 44 45 46 47 48 49 50 51
  lookupDependency,

  -- ** Case-insensitive searches
  searchByName,
  SearchResult(..),
  searchByNameSubstring,

  -- ** Bulk queries
  allPackages,
  allPackagesByName,
52
  allPackagesBySourcePackageId,
53 54 55 56 57 58 59 60 61 62

  -- ** Special queries
  brokenPackages,
  dependencyClosure,
  reverseDependencyClosure,
  topologicalOrder,
  reverseTopologicalOrder,
  dependencyInconsistencies,
  dependencyCycles,
  dependencyGraph,
Duncan Coutts's avatar
Duncan Coutts committed
63
  moduleNameIndex,
64 65 66 67 68 69 70 71 72

  -- ** Variants of special queries supporting fake map
  fakeLookupInstalledPackageId,
  brokenPackages',
  dependencyClosure',
  reverseDependencyClosure',
  dependencyInconsistencies',
  dependencyCycles',
  dependencyGraph',
73 74 75
  ) where

import Control.Exception (assert)
76
import Data.Array ((!))
ttuegel's avatar
ttuegel committed
77
import qualified Data.Array as Array
78
import Distribution.Compat.Binary (Binary)
ttuegel's avatar
ttuegel committed
79
import qualified Data.Graph as Graph
Duncan Coutts's avatar
Duncan Coutts committed
80
import Data.List as List
81
         ( null, foldl', sort
Duncan Coutts's avatar
Duncan Coutts committed
82
         , groupBy, sortBy, find, isInfixOf, nubBy, deleteBy, deleteFirstsBy )
83
#if __GLASGOW_HASKELL__ < 710
84
import Data.Monoid (Monoid(..))
85
#endif
ttuegel's avatar
ttuegel committed
86 87
import Data.Map (Map)
import qualified Data.Map as Map
88
import Data.Maybe (isNothing, fromMaybe)
ttuegel's avatar
ttuegel committed
89 90 91
import qualified Data.Tree  as Tree
import GHC.Generics (Generic)
import Prelude hiding (lookup)
92

93
import Distribution.Package
Duncan Coutts's avatar
Duncan Coutts committed
94
         ( PackageName(..), PackageId
95
         , Package(..), packageName, packageVersion
Duncan Coutts's avatar
Duncan Coutts committed
96
         , Dependency(Dependency)--, --PackageFixedDeps(..)
97 98
         , InstalledPackageId(..)
         , HasInstalledPackageId(..), PackageInstalled(..) )
Duncan Coutts's avatar
Duncan Coutts committed
99 100
import Distribution.ModuleName
         ( ModuleName )
101
import Distribution.InstalledPackageInfo
102
         ( InstalledPackageInfo )
103
import qualified Distribution.InstalledPackageInfo as IPI
104
import Distribution.Version
105
         ( Version, withinRange )
Duncan Coutts's avatar
Duncan Coutts committed
106
import Distribution.Simple.Utils (lowercase, comparing, equating)
107

108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
-- Note [FakeMap]
-----------------
-- We'd like to use the PackageIndex defined in this module for
-- cabal-install's InstallPlan.  However, at the moment, this
-- data structure is indexed by InstalledPackageId, which we don't
-- know until after we've compiled a package (whereas InstallPlan
-- needs to store not-compiled packages in the index.) Eventually,
-- an InstalledPackageId will be calculatable prior to actually
-- building the package (making it something of a misnomer), but
-- at the moment, the "fake installed package ID map" is a workaround
-- to solve this problem while reusing PackageIndex.  The basic idea
-- is that, since we don't know what an InstalledPackageId is
-- beforehand, we just fake up one based on the package ID (it only
-- needs to be unique for the particular install plan), and fill
-- it out with the actual generated InstalledPackageId after the
-- package is successfully compiled.
--
-- However, there is a problem: in the index there may be
-- references using the old package ID, which are now dangling if
-- we update the InstalledPackageId.  We could map over the entire
-- index to update these pointers as well (a costly operation), but
-- instead, we've chosen to parametrize a variety of important functions
-- by a FakeMap, which records what a fake installed package ID was
-- actually resolved to post-compilation.  If we do a lookup, we first
-- check and see if it's a fake ID in the FakeMap.
--
-- It's a bit grungy, but we expect this to only be temporary anyway.
-- (Another possible workaround would have been to *not* update
-- the installed package ID, but I decided this would be hard to
-- understand.)

-- | Map from fake installed package IDs to real ones.  See Note [FakeMap]
type FakeMap = Map InstalledPackageId InstalledPackageId

142
-- | The collection of information about packages from one or more 'PackageDB's.
143
-- These packages generally should have an instance of 'PackageInstalled'
144
--
Duncan Coutts's avatar
Duncan Coutts committed
145
-- Packages are uniquely identified in by their 'InstalledPackageId', they can
Ian D. Bollinger's avatar
Ian D. Bollinger committed
146
-- also be efficiently looked up by package name or by name and version.
147
--
148
data PackageIndex a = PackageIndex
Duncan Coutts's avatar
Duncan Coutts committed
149 150 151
  -- The primary index. Each InstalledPackageInfo record is uniquely identified
  -- by its InstalledPackageId.
  --
152
  !(Map InstalledPackageId a)
Duncan Coutts's avatar
Duncan Coutts committed
153

Ian D. Bollinger's avatar
Ian D. Bollinger committed
154
  -- This auxiliary index maps package names (case-sensitively) to all the
Duncan Coutts's avatar
Duncan Coutts committed
155 156
  -- versions and instances of that package. This allows us to find all
  -- versions satisfying a dependency.
157
  --
Duncan Coutts's avatar
Duncan Coutts committed
158 159 160 161
  -- It is a three-level index. The first level is the package name,
  -- the second is the package version and the final level is instances
  -- of the same package version. These are unique by InstalledPackageId
  -- and are kept in preference order.
162
  --
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
163 164
  -- FIXME: Clarify what "preference order" means. Check that this invariant is
  -- preserved. See #1463 for discussion.
165
  !(Map PackageName (Map Version [a]))
166

ttuegel's avatar
ttuegel committed
167 168 169
  deriving (Generic, Show, Read)

instance Binary a => Binary (PackageIndex a)
Duncan Coutts's avatar
Duncan Coutts committed
170

171 172 173 174
-- | The default package index which contains 'InstalledPackageInfo'.  Normally
-- use this.
type InstalledPackageIndex = PackageIndex InstalledPackageInfo

175
instance HasInstalledPackageId a => Monoid (PackageIndex a) where
Duncan Coutts's avatar
Duncan Coutts committed
176
  mempty  = PackageIndex Map.empty Map.empty
177 178 179 180 181
  mappend = merge
  --save one mappend with empty in the common case:
  mconcat [] = mempty
  mconcat xs = foldr1 mappend xs

182
invariant :: HasInstalledPackageId a => PackageIndex a -> Bool
Duncan Coutts's avatar
Duncan Coutts committed
183 184
invariant (PackageIndex pids pnames) =
     map installedPackageId (Map.elems pids)
185 186
  == sort
     [ assert pinstOk (installedPackageId pinst)
Duncan Coutts's avatar
Duncan Coutts committed
187 188 189 190 191 192 193 194 195 196 197
     | (pname, pvers)  <- Map.toList pnames
     , let pversOk = not (Map.null pvers)
     , (pver,  pinsts) <- assert pversOk $ Map.toList pvers
     , let pinsts'  = sortBy (comparing installedPackageId) pinsts
           pinstsOk = all (\g -> length g == 1)
                          (groupBy (equating installedPackageId) pinsts')
     , pinst           <- assert pinstsOk $ pinsts'
     , let pinstOk = packageName    pinst == pname
                  && packageVersion pinst == pver
     ]

198

199 200 201 202
--
-- * Internal helpers
--

203
mkPackageIndex :: HasInstalledPackageId a
204 205 206
               => Map InstalledPackageId a
               -> Map PackageName (Map Version [a])
               -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
207 208
mkPackageIndex pids pnames = assert (invariant index) index
  where index = PackageIndex pids pnames
209

210 211 212

--
-- * Construction
213 214
--

215
-- | Build an index out of a bunch of packages.
216
--
Duncan Coutts's avatar
Duncan Coutts committed
217 218
-- If there are duplicates by 'InstalledPackageId' then later ones mask earlier
-- ones.
219
--
220
fromList :: HasInstalledPackageId a => [a] -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
221
fromList pkgs = mkPackageIndex pids pnames
222
  where
Duncan Coutts's avatar
Duncan Coutts committed
223 224 225 226 227 228 229 230 231 232 233 234 235 236
    pids      = Map.fromList [ (installedPackageId pkg, pkg) | pkg <- pkgs ]
    pnames    =
      Map.fromList
        [ (packageName (head pkgsN), pvers)
        | pkgsN <- groupBy (equating  packageName)
                 . sortBy  (comparing packageId)
                 $ pkgs
        , let pvers =
                Map.fromList
                [ (packageVersion (head pkgsNV),
                   nubBy (equating installedPackageId) (reverse pkgsNV))
                | pkgsNV <- groupBy (equating packageVersion) pkgsN
                ]
        ]
237

238 239 240 241
--
-- * Updates
--

242 243
-- | Merge two indexes.
--
Duncan Coutts's avatar
Duncan Coutts committed
244 245
-- Packages from the second mask packages from the first if they have the exact
-- same 'InstalledPackageId'.
246
--
Duncan Coutts's avatar
Duncan Coutts committed
247 248 249 250 251
-- For packages with the same source 'PackageId', packages from the second are
-- \"preferred\" over those from the first. Being preferred means they are top
-- result when we do a lookup by source 'PackageId'. This is the mechanism we
-- use to prefer user packages over global packages.
--
252
merge :: HasInstalledPackageId a => PackageIndex a -> PackageIndex a -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
253
merge (PackageIndex pids1 pnames1) (PackageIndex pids2 pnames2) =
254
  mkPackageIndex (Map.unionWith (\_ y -> y) pids1 pids2)
Duncan Coutts's avatar
Duncan Coutts committed
255 256 257 258 259 260
                 (Map.unionWith (Map.unionWith mergeBuckets) pnames1 pnames2)
  where
    -- Packages in the second list mask those in the first, however preferred
    -- packages go first in the list.
    mergeBuckets xs ys = ys ++ (xs \\ ys)
    (\\) = deleteFirstsBy (equating installedPackageId)
261

262

Duncan Coutts's avatar
Duncan Coutts committed
263
-- | Inserts a single package into the index.
264 265 266 267
--
-- This is equivalent to (but slightly quicker than) using 'mappend' or
-- 'merge' with a singleton index.
--
268
insert :: HasInstalledPackageId a => a -> PackageIndex a -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
269 270 271
insert pkg (PackageIndex pids pnames) =
    mkPackageIndex pids' pnames'

272
  where
Duncan Coutts's avatar
Duncan Coutts committed
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289
    pids'   = Map.insert (installedPackageId pkg) pkg pids
    pnames' = insertPackageName pnames
    insertPackageName =
      Map.insertWith' (\_ -> insertPackageVersion)
                     (packageName pkg)
                     (Map.singleton (packageVersion pkg) [pkg])

    insertPackageVersion =
      Map.insertWith' (\_ -> insertPackageInstance)
                     (packageVersion pkg) [pkg]

    insertPackageInstance pkgs =
      pkg : deleteBy (equating installedPackageId) pkg pkgs


-- | Removes a single installed package from the index.
--
290
deleteInstalledPackageId :: HasInstalledPackageId a => InstalledPackageId -> PackageIndex a -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
291 292 293 294 295 296
deleteInstalledPackageId ipkgid original@(PackageIndex pids pnames) =
  case Map.updateLookupWithKey (\_ _ -> Nothing) ipkgid pids of
    (Nothing,     _)     -> original
    (Just spkgid, pids') -> mkPackageIndex pids'
                                          (deletePkgName spkgid pnames)

Duncan Coutts's avatar
Duncan Coutts committed
297
  where
Duncan Coutts's avatar
Duncan Coutts committed
298 299 300 301 302 303
    deletePkgName spkgid =
      Map.update (deletePkgVersion spkgid) (packageName spkgid)

    deletePkgVersion spkgid =
        (\m -> if Map.null m then Nothing else Just m)
      . Map.update deletePkgInstance (packageVersion spkgid)
Duncan Coutts's avatar
Duncan Coutts committed
304

Duncan Coutts's avatar
Duncan Coutts committed
305 306 307 308 309 310
    deletePkgInstance =
        (\xs -> if List.null xs then Nothing else Just xs)
      . List.deleteBy (\_ pkg -> installedPackageId pkg == ipkgid) undefined


-- | Removes all packages with this source 'PackageId' from the index.
311
--
312
deleteSourcePackageId :: HasInstalledPackageId a => PackageId -> PackageIndex a -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
deleteSourcePackageId pkgid original@(PackageIndex pids pnames) =
  case Map.lookup (packageName pkgid) pnames of
    Nothing     -> original
    Just pvers  -> case Map.lookup (packageVersion pkgid) pvers of
      Nothing   -> original
      Just pkgs -> mkPackageIndex
                     (foldl' (flip (Map.delete . installedPackageId)) pids pkgs)
                     (deletePkgName pnames)
  where
    deletePkgName =
      Map.update deletePkgVersion (packageName pkgid)

    deletePkgVersion =
        (\m -> if Map.null m then Nothing else Just m)
      . Map.delete (packageVersion pkgid)

329 330 331

-- | Removes all packages with this (case-sensitive) name from the index.
--
332
deletePackageName :: HasInstalledPackageId a => PackageName -> PackageIndex a -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
333 334 335 336 337 338 339
deletePackageName name original@(PackageIndex pids pnames) =
  case Map.lookup name pnames of
    Nothing     -> original
    Just pvers  -> mkPackageIndex
                     (foldl' (flip (Map.delete . installedPackageId)) pids
                             (concat (Map.elems pvers)))
                     (Map.delete name pnames)
340

Duncan Coutts's avatar
Duncan Coutts committed
341
{-
342 343
-- | Removes all packages satisfying this dependency from the index.
--
Duncan Coutts's avatar
Duncan Coutts committed
344
deleteDependency :: Dependency -> PackageIndex -> PackageIndex
345
deleteDependency (Dependency name verstionRange) =
Duncan Coutts's avatar
Duncan Coutts committed
346 347
  delete' name (\pkg -> packageVersion pkg `withinRange` verstionRange)
-}
348

349 350 351 352
--
-- * Bulk queries
--

353 354
-- | Get all the packages from the index.
--
355
allPackages :: PackageIndex a -> [a]
Duncan Coutts's avatar
Duncan Coutts committed
356
allPackages (PackageIndex pids _) = Map.elems pids
357 358 359

-- | Get all the packages from the index.
--
360
-- They are grouped by package name (case-sensitively).
361
--
362
allPackagesByName :: PackageIndex a -> [(PackageName, [a])]
Duncan Coutts's avatar
Duncan Coutts committed
363
allPackagesByName (PackageIndex _ pnames) =
364 365 366 367 368 369 370
  [ (pkgname, concat (Map.elems pvers))
  | (pkgname, pvers) <- Map.toList pnames ]

-- | Get all the packages from the index.
--
-- They are grouped by source package id (package name and version).
--
371
allPackagesBySourcePackageId :: HasInstalledPackageId a => PackageIndex a -> [(PackageId, [a])]
372 373 374 375
allPackagesBySourcePackageId (PackageIndex _ pnames) =
  [ (packageId ipkg, ipkgs)
  | pvers <- Map.elems pnames
  , ipkgs@(ipkg:_) <- Map.elems pvers ]
376 377 378 379 380

--
-- * Lookups
--

Duncan Coutts's avatar
Duncan Coutts committed
381
-- | Does a lookup by source package id (name & version).
382
--
Duncan Coutts's avatar
Duncan Coutts committed
383
-- Since multiple package DBs mask each other by 'InstalledPackageId',
384 385
-- then we get back at most one package.
--
386
lookupInstalledPackageId :: HasInstalledPackageId a => PackageIndex a -> InstalledPackageId
387
                         -> Maybe a
Duncan Coutts's avatar
Duncan Coutts committed
388 389
lookupInstalledPackageId (PackageIndex pids _) pid = Map.lookup pid pids

390

Duncan Coutts's avatar
Duncan Coutts committed
391 392 393 394 395
-- | Does a lookup by source package id (name & version).
--
-- There can be multiple installed packages with the same source 'PackageId'
-- but different 'InstalledPackageId'. They are returned in order of
-- preference, with the most preferred first.
396
--
397
lookupSourcePackageId :: HasInstalledPackageId a => PackageIndex a -> PackageId -> [a]
Duncan Coutts's avatar
Duncan Coutts committed
398 399 400 401 402 403
lookupSourcePackageId (PackageIndex _ pnames) pkgid =
  case Map.lookup (packageName pkgid) pnames of
    Nothing     -> []
    Just pvers  -> case Map.lookup (packageVersion pkgid) pvers of
      Nothing   -> []
      Just pkgs -> pkgs -- in preference order
404

405 406
-- | Convenient alias of 'lookupSourcePackageId', but assuming only
-- one package per package ID.
407
lookupPackageId :: HasInstalledPackageId a => PackageIndex a -> PackageId -> Maybe a
408 409 410 411
lookupPackageId index pkgid = case lookupSourcePackageId index pkgid  of
    []    -> Nothing
    [pkg] -> Just pkg
    _     -> error "Distribution.Simple.PackageIndex: multiple matches found"
Duncan Coutts's avatar
Duncan Coutts committed
412 413 414

-- | Does a lookup by source package name.
--
415
lookupPackageName :: HasInstalledPackageId a => PackageIndex a -> PackageName
416
                  -> [(Version, [a])]
Duncan Coutts's avatar
Duncan Coutts committed
417 418 419 420 421 422 423
lookupPackageName (PackageIndex _ pnames) name =
  case Map.lookup name pnames of
    Nothing     -> []
    Just pvers  -> Map.toList pvers


-- | Does a lookup by source package name and a range of versions.
424 425 426 427
--
-- We get back any number of versions of the specified package name, all
-- satisfying the version range constraint.
--
428
lookupDependency :: HasInstalledPackageId a => PackageIndex a -> Dependency
429
                 -> [(Version, [a])]
Duncan Coutts's avatar
Duncan Coutts committed
430 431 432 433 434 435
lookupDependency (PackageIndex _ pnames) (Dependency name versionRange) =
  case Map.lookup name pnames of
    Nothing    -> []
    Just pvers -> [ entry
                  | entry@(ver, _) <- Map.toList pvers
                  , ver `withinRange` versionRange ]
436 437 438 439

--
-- * Case insensitive name lookups
--
440 441 442

-- | Does a case-insensitive search by package name.
--
Ian D. Bollinger's avatar
Ian D. Bollinger committed
443
-- If there is only one package that compares case-insensitively to this name
444
-- then the search is unambiguous and we get back all versions of that package.
Ian D. Bollinger's avatar
Ian D. Bollinger committed
445
-- If several match case-insensitively but one matches exactly then it is also
446 447
-- unambiguous.
--
Ian D. Bollinger's avatar
Ian D. Bollinger committed
448
-- If however several match case-insensitively and none match exactly then we
449 450 451 452
-- have an ambiguous result, and we get back all the versions of all the
-- packages. The list of ambiguous results is split by exact package name. So
-- it is a non-empty list of non-empty lists.
--
453
searchByName :: HasInstalledPackageId a => PackageIndex a -> String -> SearchResult [a]
Duncan Coutts's avatar
Duncan Coutts committed
454 455
searchByName (PackageIndex _ pnames) name =
  case [ pkgs | pkgs@(PackageName name',_) <- Map.toList pnames
456
              , lowercase name' == lname ] of
Duncan Coutts's avatar
Duncan Coutts committed
457 458 459 460 461
    []               -> None
    [(_,pvers)]      -> Unambiguous (concat (Map.elems pvers))
    pkgss            -> case find ((PackageName name==) . fst) pkgss of
      Just (_,pvers) -> Unambiguous (concat (Map.elems pvers))
      Nothing        -> Ambiguous (map (concat . Map.elems . snd) pkgss)
462
  where lname = lowercase name
463 464 465 466 467 468 469

data SearchResult a = None | Unambiguous a | Ambiguous [a]

-- | Does a case-insensitive substring search by package name.
--
-- That is, all packages that contain the given string in their name.
--
470
searchByNameSubstring :: HasInstalledPackageId a => PackageIndex a -> String -> [a]
Duncan Coutts's avatar
Duncan Coutts committed
471
searchByNameSubstring (PackageIndex _ pnames) searchterm =
472
  [ pkg
Duncan Coutts's avatar
Duncan Coutts committed
473
  | (PackageName name, pvers) <- Map.toList pnames
474
  , lsearchterm `isInfixOf` lowercase name
Duncan Coutts's avatar
Duncan Coutts committed
475
  , pkgs <- Map.elems pvers
476
  , pkg <- pkgs ]
477
  where lsearchterm = lowercase searchterm
478

Duncan Coutts's avatar
Duncan Coutts committed
479 480 481 482 483 484 485 486

--
-- * Special queries
--

-- None of the stuff below depends on the internal representation of the index.
--

487 488 489 490 491 492 493
-- | Find if there are any cycles in the dependency graph. If there are no
-- cycles the result is @[]@.
--
-- This actually computes the strongly connected components. So it gives us a
-- list of groups of packages where within each group they all depend on each
-- other, directly or indirectly.
--
494
dependencyCycles :: PackageInstalled a => PackageIndex a -> [[a]]
495 496 497 498 499
dependencyCycles = dependencyCycles' Map.empty

-- | Variant of 'dependencyCycles' which accepts a 'FakeMap'.  See Note [FakeMap].
dependencyCycles' :: PackageInstalled a => FakeMap -> PackageIndex a -> [[a]]
dependencyCycles' fakeMap index =
500 501
  [ vs | Graph.CyclicSCC vs <- Graph.stronglyConnComp adjacencyList ]
  where
502
    adjacencyList = [ (pkg, installedPackageId pkg, fakeInstalledDepends fakeMap pkg)
503 504 505
                    | pkg <- allPackages index ]


Duncan Coutts's avatar
Duncan Coutts committed
506
-- | All packages that have immediate dependencies that are not in the index.
507
--
508 509
-- Returns such packages along with the dependencies that they're missing.
--
510
brokenPackages :: PackageInstalled a => PackageIndex a -> [(a, [InstalledPackageId])]
511 512 513 514 515
brokenPackages = brokenPackages' Map.empty

-- | Variant of 'brokenPackages' which accepts a 'FakeMap'.  See Note [FakeMap].
brokenPackages' :: PackageInstalled a => FakeMap -> PackageIndex a -> [(a, [InstalledPackageId])]
brokenPackages' fakeMap index =
516
  [ (pkg, missing)
Duncan Coutts's avatar
Duncan Coutts committed
517
  | pkg  <- allPackages index
518
  , let missing = [ pkg' | pkg' <- installedDepends pkg
519
                         , isNothing (fakeLookupInstalledPackageId fakeMap index pkg') ]
520 521
  , not (null missing) ]

522
-- | Variant of 'lookupInstalledPackageId' which accepts a 'FakeMap'.  See Note [FakeMap].
523
fakeLookupInstalledPackageId :: HasInstalledPackageId a => FakeMap -> PackageIndex a -> InstalledPackageId -> Maybe a
524
fakeLookupInstalledPackageId fakeMap index pkg = lookupInstalledPackageId index (Map.findWithDefault pkg pkg fakeMap)
525

526
-- | Tries to take the transitive closure of the package dependencies.
527
--
528
-- If the transitive closure is complete then it returns that subset of the
529 530 531
-- index. Otherwise it returns the broken packages as in 'brokenPackages'.
--
-- * Note that if the result is @Right []@ it is because at least one of
Duncan Coutts's avatar
Duncan Coutts committed
532
-- the original given 'PackageId's do not occur in the index.
533
--
534
dependencyClosure :: PackageInstalled a => PackageIndex a
535
                  -> [InstalledPackageId]
536 537
                  -> Either (PackageIndex a)
                            [(a, [InstalledPackageId])]
538 539 540 541 542 543 544 545 546
dependencyClosure = dependencyClosure' Map.empty

-- | Variant of 'dependencyClosure' which accepts a 'FakeMap'.  See Note [FakeMap].
dependencyClosure' :: PackageInstalled a => FakeMap
                  -> PackageIndex a
                  -> [InstalledPackageId]
                  -> Either (PackageIndex a)
                            [(a, [InstalledPackageId])]
dependencyClosure' fakeMap index pkgids0 = case closure mempty [] pkgids0 of
547 548
  (completed, []) -> Left completed
  (completed, _)  -> Right (brokenPackages completed)
549
 where
550
    closure completed failed []             = (completed, failed)
551
    closure completed failed (pkgid:pkgids) = case fakeLookupInstalledPackageId fakeMap index pkgid of
552
      Nothing   -> closure completed (pkgid:failed) pkgids
553
      Just pkg  -> case fakeLookupInstalledPackageId fakeMap completed (installedPackageId pkg) of
554 555
        Just _  -> closure completed  failed pkgids
        Nothing -> closure completed' failed pkgids'
Duncan Coutts's avatar
Duncan Coutts committed
556
          where completed' = insert pkg completed
557
                pkgids'    = installedDepends pkg ++ pkgids
558

559
-- | Takes the transitive closure of the packages reverse dependencies.
560
--
Duncan Coutts's avatar
Duncan Coutts committed
561
-- * The given 'PackageId's must be in the index.
562
--
563
reverseDependencyClosure :: PackageInstalled a => PackageIndex a
564
                         -> [InstalledPackageId]
565
                         -> [a]
566 567 568 569 570 571 572 573
reverseDependencyClosure = reverseDependencyClosure' Map.empty

-- | Variant of 'reverseDependencyClosure' which accepts a 'FakeMap'.  See Note [FakeMap].
reverseDependencyClosure' :: PackageInstalled a => FakeMap
                         -> PackageIndex a
                         -> [InstalledPackageId]
                         -> [a]
reverseDependencyClosure' fakeMap index =
574 575 576 577
    map vertexToPkg
  . concatMap Tree.flatten
  . Graph.dfs reverseDepGraph
  . map (fromMaybe noSuchPkgId . pkgIdToVertex)
578

579
  where
580
    (depGraph, vertexToPkg, pkgIdToVertex) = dependencyGraph' fakeMap index
581 582 583
    reverseDepGraph = Graph.transposeG depGraph
    noSuchPkgId = error "reverseDependencyClosure: package is not in the graph"

584
topologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
585 586 587 588 589
topologicalOrder index = map toPkgId
                       . Graph.topSort
                       $ graph
  where (graph, toPkgId, _) = dependencyGraph index

590
reverseTopologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
591 592 593 594 595 596 597 598 599 600 601
reverseTopologicalOrder index = map toPkgId
                              . Graph.topSort
                              . Graph.transposeG
                              $ graph
  where (graph, toPkgId, _) = dependencyGraph index

-- | Builds a graph of the package dependencies.
--
-- Dependencies on other packages that are not in the index are discarded.
-- You can check if there are any such dependencies with 'brokenPackages'.
--
602
dependencyGraph :: PackageInstalled a => PackageIndex a
603
                -> (Graph.Graph,
604
                    Graph.Vertex -> a,
605
                    InstalledPackageId -> Maybe Graph.Vertex)
606 607 608 609 610 611 612 613 614
dependencyGraph = dependencyGraph' Map.empty

-- | Variant of 'dependencyGraph' which accepts a 'FakeMap'.  See Note [FakeMap].
dependencyGraph' :: PackageInstalled a => FakeMap
                -> PackageIndex a
                -> (Graph.Graph,
                    Graph.Vertex -> a,
                    InstalledPackageId -> Maybe Graph.Vertex)
dependencyGraph' fakeMap index = (graph, vertex_to_pkg, id_to_vertex)
615 616
  where
    graph = Array.listArray bounds
617
              [ [ v | Just v <- map id_to_vertex (installedDepends pkg) ]
618
              | pkg <- pkgs ]
619

Duncan Coutts's avatar
Duncan Coutts committed
620
    pkgs             = sortBy (comparing packageId) (allPackages index)
621 622
    vertices         = zip (map installedPackageId pkgs) [0..]
    vertex_map       = Map.fromList vertices
623
    id_to_vertex pid = Map.lookup (Map.findWithDefault pid pid fakeMap) vertex_map
624 625

    vertex_to_pkg vertex = pkgTable ! vertex
626 627 628 629 630

    pkgTable   = Array.listArray bounds pkgs
    topBound = length pkgs - 1
    bounds = (0, topBound)

631 632 633 634 635 636 637 638 639 640
-- | Given a package index where we assume we want to use all the packages
-- (use 'dependencyClosure' if you need to get such a index subset) find out
-- if the dependencies within it use consistent versions of each package.
-- Return all cases where multiple packages depend on different versions of
-- some other package.
--
-- Each element in the result is a package name along with the packages that
-- depend on it and the versions they require. These are guaranteed to be
-- distinct.
--
641
dependencyInconsistencies :: PackageInstalled a => PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
642
                          -> [(PackageName, [(PackageId, Version)])]
643 644 645 646 647 648
dependencyInconsistencies = dependencyInconsistencies' Map.empty

-- | Variant of 'dependencyInconsistencies' which accepts a 'FakeMap'.  See Note [FakeMap].
dependencyInconsistencies' :: PackageInstalled a => FakeMap -> PackageIndex a
                          -> [(PackageName, [(PackageId, Version)])]
dependencyInconsistencies' fakeMap index =
649 650 651 652 653 654 655 656 657 658 659 660
  [ (name, [ (pid,packageVersion dep) | (dep,pids) <- uses, pid <- pids])
  | (name, ipid_map) <- Map.toList inverseIndex
  , let uses = Map.elems ipid_map
  , reallyIsInconsistent (map fst uses) ]

  where -- for each PackageName,
        --   for each package with that name,
        --     the InstalledPackageInfo and the package Ids of packages
        --     that depend on it.
        inverseIndex = Map.fromListWith (Map.unionWith (\(a,b) (_,b') -> (a,b++b')))
          [ (packageName dep,
             Map.fromList [(ipid,(dep,[packageId pkg]))])
Duncan Coutts's avatar
Duncan Coutts committed
661
          | pkg <- allPackages index
662 663
          , ipid <- fakeInstalledDepends fakeMap pkg
          , Just dep <- [fakeLookupInstalledPackageId fakeMap index ipid]
664 665
          ]

666
        reallyIsInconsistent :: PackageInstalled a => [a] -> Bool
667 668 669
        reallyIsInconsistent []       = False
        reallyIsInconsistent [_p]     = False
        reallyIsInconsistent [p1, p2] =
670 671 672 673
          let pid1 = installedPackageId p1
              pid2 = installedPackageId p2
          in Map.findWithDefault pid1 pid1 fakeMap `notElem` fakeInstalledDepends fakeMap p2
          && Map.findWithDefault pid2 pid2 fakeMap `notElem` fakeInstalledDepends fakeMap p1
674
        reallyIsInconsistent _ = True
Duncan Coutts's avatar
Duncan Coutts committed
675

676 677 678
-- | Variant of 'installedDepends' which accepts a 'FakeMap'.  See Note [FakeMap].
fakeInstalledDepends :: PackageInstalled a => FakeMap -> a -> [InstalledPackageId]
fakeInstalledDepends fakeMap = map (\pid -> Map.findWithDefault pid pid fakeMap) . installedDepends
Duncan Coutts's avatar
Duncan Coutts committed
679

680
-- | A rough approximation of GHC's module finder, takes a 'InstalledPackageIndex' and
681 682
-- turns it into a map from module names to their source packages.  It's used to
-- initialize the @build-deps@ field in @cabal init@.
683
moduleNameIndex :: InstalledPackageIndex -> Map ModuleName [InstalledPackageInfo]
Duncan Coutts's avatar
Duncan Coutts committed
684
moduleNameIndex index =
685 686 687 688 689 690 691
  Map.fromListWith (++) $ do
    pkg <- allPackages index
    IPI.ExposedModule m reexport _ <- IPI.exposedModules pkg
    case reexport of
        Nothing -> return (m, [pkg])
        Just (IPI.OriginalModule _ m') | m == m'   -> []
                                       | otherwise -> return (m', [pkg])
692 693 694 695 696
        -- The heuristic is this: we want to prefer the original package
        -- which originally exported a module.  However, if a reexport
        -- also *renamed* the module (m /= m'), then we have to use the
        -- downstream package, since the upstream package has the wrong
        -- module name!