PackageIndex.hs 26.3 KB
Newer Older
ttuegel's avatar
ttuegel committed
1
{-# LANGUAGE DeriveGeneric #-}
John Ericson's avatar
John Ericson committed
2
{-# LANGUAGE FlexibleContexts #-}
3
{-# LANGUAGE FlexibleInstances #-}
ttuegel's avatar
ttuegel committed
4

5 6
-----------------------------------------------------------------------------
-- |
7
-- Module      :  Distribution.Simple.PackageIndex
8 9
-- Copyright   :  (c) David Himmelstrup 2005,
--                    Bjorn Bringert 2007,
Duncan Coutts's avatar
Duncan Coutts committed
10
--                    Duncan Coutts 2008-2009
11
--
Duncan Coutts's avatar
Duncan Coutts committed
12
-- Maintainer  :  cabal-devel@haskell.org
13 14
-- Portability :  portable
--
15 16 17 18 19 20
-- An index of packages whose primary key is 'UnitId'.  Public libraries
-- are additionally indexed by 'PackageName' and 'Version'.
-- Technically, these are an index of *units* (so we should eventually
-- rename it to 'UnitIndex'); but in the absence of internal libraries
-- or Backpack each unit is equivalent to a package.
--
Edward Z. Yang's avatar
Edward Z. Yang committed
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
-- While 'PackageIndex' is parametric over what it actually records,
-- it is in fact only ever instantiated with a single element:
-- The 'InstalledPackageIndex' (defined here) contains a graph of
-- 'InstalledPackageInfo's representing the packages in a
-- package database stack.  It is used in a variety of ways:
--
--   * The primary use to let Cabal access the same installed
--     package database which is used by GHC during compilation.
--     For example, this data structure is used by 'ghc-pkg'
--     and 'Cabal' to do consistency checks on the database
--     (are the references closed).
--
--   * Given a set of dependencies, we can compute the transitive
--     closure of dependencies.  This is to check if the versions
--     of packages are consistent, and also needed by multiple
--     tools (Haddock must be explicitly told about the every
--     transitive package to do cross-package linking;
--     preprocessors must know about the include paths of all
--     transitive dependencies.)
40 41 42 43 44
--
-- This 'PackageIndex' is NOT to be confused with
-- 'Distribution.Client.PackageIndex', which indexes packages only by
-- 'PackageName' (this makes it suitable for indexing source packages,
-- for which we don't know 'UnitId's.)
Duncan Coutts's avatar
Duncan Coutts committed
45
--
46 47
module Distribution.Simple.PackageIndex (
  -- * Package index data type
48
  InstalledPackageIndex,
49
  PackageIndex,
50

51
  -- * Creating an index
52 53
  fromList,

54
  -- * Updates
55
  merge,
Duncan Coutts's avatar
Duncan Coutts committed
56

57
  insert,
Duncan Coutts's avatar
Duncan Coutts committed
58

59
  deleteUnitId,
Duncan Coutts's avatar
Duncan Coutts committed
60
  deleteSourcePackageId,
61
  deletePackageName,
Duncan Coutts's avatar
Duncan Coutts committed
62
--  deleteDependency,
63 64 65 66

  -- * Queries

  -- ** Precise lookups
67
  lookupUnitId,
68
  lookupComponentId,
Duncan Coutts's avatar
Duncan Coutts committed
69
  lookupSourcePackageId,
70
  lookupPackageId,
71
  lookupPackageName,
72
  lookupDependency,
73
  lookupInternalDependency,
74 75 76 77 78 79 80 81 82

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

  -- ** Bulk queries
  allPackages,
  allPackagesByName,
83
  allPackagesBySourcePackageId,
84
  allPackagesBySourcePackageIdAndLibName,
85 86 87 88 89 90 91 92 93 94

  -- ** Special queries
  brokenPackages,
  dependencyClosure,
  reverseDependencyClosure,
  topologicalOrder,
  reverseTopologicalOrder,
  dependencyInconsistencies,
  dependencyCycles,
  dependencyGraph,
Duncan Coutts's avatar
Duncan Coutts committed
95
  moduleNameIndex,
96 97 98 99

  -- * Backwards compatibility
  deleteInstalledPackageId,
  lookupInstalledPackageId,
100 101
  ) where

102 103
import Prelude ()
import Distribution.Compat.Prelude hiding (lookup)
104
import qualified Distribution.Compat.Map.Strict as Map
105

106
import Distribution.Package
107
import Distribution.Backpack
108 109 110 111
import Distribution.ModuleName
import qualified Distribution.InstalledPackageInfo as IPI
import Distribution.Version
import Distribution.Simple.Utils
112
import Distribution.Types.Dependency
113
import Distribution.Types.UnqualComponentName
114

115
import Control.Exception (assert)
116
import Data.Array ((!))
ttuegel's avatar
ttuegel committed
117 118
import qualified Data.Array as Array
import qualified Data.Graph as Graph
119
import Data.List as List ( groupBy,  deleteBy, deleteFirstsBy )
ttuegel's avatar
ttuegel committed
120
import qualified Data.Tree  as Tree
121
import Control.Monad
Edward Z. Yang's avatar
Edward Z. Yang committed
122
import Distribution.Compat.Stack
123 124

-- | The collection of information about packages from one or more 'PackageDB's.
125
-- These packages generally should have an instance of 'PackageInstalled'
126
--
127
-- Packages are uniquely identified in by their 'UnitId', they can
Ian D. Bollinger's avatar
Ian D. Bollinger committed
128
-- also be efficiently looked up by package name or by name and version.
129
--
130
data PackageIndex a = PackageIndex {
Duncan Coutts's avatar
Duncan Coutts committed
131
  -- The primary index. Each InstalledPackageInfo record is uniquely identified
132
  -- by its UnitId.
Duncan Coutts's avatar
Duncan Coutts committed
133
  --
134
  unitIdIndex :: !(Map UnitId a),
Duncan Coutts's avatar
Duncan Coutts committed
135

Ian D. Bollinger's avatar
Ian D. Bollinger committed
136
  -- This auxiliary index maps package names (case-sensitively) to all the
Duncan Coutts's avatar
Duncan Coutts committed
137 138
  -- versions and instances of that package. This allows us to find all
  -- versions satisfying a dependency.
139
  --
Duncan Coutts's avatar
Duncan Coutts committed
140 141
  -- 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
142
  -- of the same package version. These are unique by UnitId
Duncan Coutts's avatar
Duncan Coutts committed
143
  -- and are kept in preference order.
144
  --
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
145 146
  -- FIXME: Clarify what "preference order" means. Check that this invariant is
  -- preserved. See #1463 for discussion.
147
  packageIdIndex :: !(Map (PackageName, Maybe UnqualComponentName) (Map Version [a]))
148

149
  } deriving (Eq, Generic, Show, Read)
ttuegel's avatar
ttuegel committed
150 151

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

153 154
-- | The default package index which contains 'InstalledPackageInfo'.  Normally
-- use this.
155
type InstalledPackageIndex = PackageIndex IPI.InstalledPackageInfo
156

157
instance Monoid (PackageIndex IPI.InstalledPackageInfo) where
Duncan Coutts's avatar
Duncan Coutts committed
158
  mempty  = PackageIndex Map.empty Map.empty
159
  mappend = (<>)
160
  --save one mappend with empty in the common case:
161
  mconcat [] = mempty
162 163
  mconcat xs = foldr1 mappend xs

164
instance Semigroup (PackageIndex IPI.InstalledPackageInfo) where
165 166
  (<>) = merge

Edward Z. Yang's avatar
Edward Z. Yang committed
167 168
{-# NOINLINE invariant #-}
invariant :: WithCallStack (InstalledPackageIndex -> Bool)
Duncan Coutts's avatar
Duncan Coutts committed
169
invariant (PackageIndex pids pnames) =
Edward Z. Yang's avatar
Edward Z. Yang committed
170 171 172 173 174
  -- trace (show pids' ++ "\n" ++ show pnames') $
  pids' == pnames'
 where
  pids' = map installedUnitId (Map.elems pids)
  pnames' = sort
175
     [ assert pinstOk (installedUnitId pinst)
176
     | ((pname, plib), pvers)  <- Map.toList pnames
Duncan Coutts's avatar
Duncan Coutts committed
177 178
     , let pversOk = not (Map.null pvers)
     , (pver,  pinsts) <- assert pversOk $ Map.toList pvers
179
     , let pinsts'  = sortBy (comparing installedUnitId) pinsts
Duncan Coutts's avatar
Duncan Coutts committed
180
           pinstsOk = all (\g -> length g == 1)
181
                          (groupBy (equating installedUnitId) pinsts')
Duncan Coutts's avatar
Duncan Coutts committed
182 183 184
     , pinst           <- assert pinstsOk $ pinsts'
     , let pinstOk = packageName    pinst == pname
                  && packageVersion pinst == pver
185
                  && IPI.sourceLibName  pinst == plib
Duncan Coutts's avatar
Duncan Coutts committed
186
     ]
187 188 189 190 191
  -- If you see this invariant failing (ie the assert in mkPackageIndex below)
  -- then one thing to check is if it is happening in fromList. Check if the
  -- second list above (the sort [...] bit) is ending up with duplicates. This
  -- has been observed in practice once due to a messed up ghc-pkg db. How/why
  -- it became messed up was not discovered.
Duncan Coutts's avatar
Duncan Coutts committed
192

193

194 195 196 197
--
-- * Internal helpers
--

Edward Z. Yang's avatar
Edward Z. Yang committed
198
mkPackageIndex :: WithCallStack (Map UnitId IPI.InstalledPackageInfo
199 200
               -> Map (PackageName, Maybe UnqualComponentName)
                      (Map Version [IPI.InstalledPackageInfo])
Edward Z. Yang's avatar
Edward Z. Yang committed
201
               -> InstalledPackageIndex)
Duncan Coutts's avatar
Duncan Coutts committed
202 203
mkPackageIndex pids pnames = assert (invariant index) index
  where index = PackageIndex pids pnames
204

205 206 207

--
-- * Construction
208 209
--

210
-- | Build an index out of a bunch of packages.
211
--
212
-- If there are duplicates by 'UnitId' then later ones mask earlier
Duncan Coutts's avatar
Duncan Coutts committed
213
-- ones.
214
--
215
fromList :: [IPI.InstalledPackageInfo] -> InstalledPackageIndex
Duncan Coutts's avatar
Duncan Coutts committed
216
fromList pkgs = mkPackageIndex pids pnames
217
  where
218
    pids      = Map.fromList [ (installedUnitId pkg, pkg) | pkg <- pkgs ]
Duncan Coutts's avatar
Duncan Coutts committed
219 220
    pnames    =
      Map.fromList
221 222
        [ (liftM2 (,) packageName IPI.sourceLibName (head pkgsN), pvers)
        | pkgsN <- groupBy (equating  (liftM2 (,) packageName IPI.sourceLibName))
Edward Z. Yang's avatar
Edward Z. Yang committed
223
                 . sortBy  (comparing (liftM2 (,) packageId IPI.sourceLibName))
Duncan Coutts's avatar
Duncan Coutts committed
224 225 226 227
                 $ pkgs
        , let pvers =
                Map.fromList
                [ (packageVersion (head pkgsNV),
228
                   nubBy (equating installedUnitId) (reverse pkgsNV))
Duncan Coutts's avatar
Duncan Coutts committed
229 230 231
                | pkgsNV <- groupBy (equating packageVersion) pkgsN
                ]
        ]
232

233 234 235 236
--
-- * Updates
--

237 238
-- | Merge two indexes.
--
Duncan Coutts's avatar
Duncan Coutts committed
239
-- Packages from the second mask packages from the first if they have the exact
240
-- same 'UnitId'.
241
--
Duncan Coutts's avatar
Duncan Coutts committed
242 243 244 245 246
-- 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.
--
247 248
merge :: InstalledPackageIndex -> InstalledPackageIndex
      -> InstalledPackageIndex
Duncan Coutts's avatar
Duncan Coutts committed
249
merge (PackageIndex pids1 pnames1) (PackageIndex pids2 pnames2) =
250
  mkPackageIndex (Map.unionWith (\_ y -> y) pids1 pids2)
Duncan Coutts's avatar
Duncan Coutts committed
251 252 253 254 255
                 (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)
256
    (\\) = deleteFirstsBy (equating installedUnitId)
257

258

Duncan Coutts's avatar
Duncan Coutts committed
259
-- | Inserts a single package into the index.
260 261 262 263
--
-- This is equivalent to (but slightly quicker than) using 'mappend' or
-- 'merge' with a singleton index.
--
264
insert :: IPI.InstalledPackageInfo -> InstalledPackageIndex -> InstalledPackageIndex
Duncan Coutts's avatar
Duncan Coutts committed
265 266 267
insert pkg (PackageIndex pids pnames) =
    mkPackageIndex pids' pnames'

268
  where
269
    pids'   = Map.insert (installedUnitId pkg) pkg pids
Duncan Coutts's avatar
Duncan Coutts committed
270 271
    pnames' = insertPackageName pnames
    insertPackageName =
272
      Map.insertWith (\_ -> insertPackageVersion)
273
                     (packageName pkg, IPI.sourceLibName pkg)
Duncan Coutts's avatar
Duncan Coutts committed
274 275 276
                     (Map.singleton (packageVersion pkg) [pkg])

    insertPackageVersion =
277
      Map.insertWith (\_ -> insertPackageInstance)
Duncan Coutts's avatar
Duncan Coutts committed
278 279 280
                     (packageVersion pkg) [pkg]

    insertPackageInstance pkgs =
281
      pkg : deleteBy (equating installedUnitId) pkg pkgs
Duncan Coutts's avatar
Duncan Coutts committed
282 283 284 285


-- | Removes a single installed package from the index.
--
286 287
deleteUnitId :: UnitId -> InstalledPackageIndex
             -> InstalledPackageIndex
288
deleteUnitId ipkgid original@(PackageIndex pids pnames) =
Duncan Coutts's avatar
Duncan Coutts committed
289 290 291 292 293
  case Map.updateLookupWithKey (\_ _ -> Nothing) ipkgid pids of
    (Nothing,     _)     -> original
    (Just spkgid, pids') -> mkPackageIndex pids'
                                          (deletePkgName spkgid pnames)

Duncan Coutts's avatar
Duncan Coutts committed
294
  where
Duncan Coutts's avatar
Duncan Coutts committed
295
    deletePkgName spkgid =
296
      Map.update (deletePkgVersion spkgid) (packageName spkgid, IPI.sourceLibName spkgid)
Duncan Coutts's avatar
Duncan Coutts committed
297 298 299 300

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

Duncan Coutts's avatar
Duncan Coutts committed
302
    deletePkgInstance =
303
        (\xs -> if null xs then Nothing else Just xs)
304
      . List.deleteBy (\_ pkg -> installedUnitId pkg == ipkgid) undefined
Duncan Coutts's avatar
Duncan Coutts committed
305

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
306
-- | Backwards compatibility wrapper for Cabal pre-1.24.
307
{-# DEPRECATED deleteInstalledPackageId "Use deleteUnitId instead" #-}
308 309
deleteInstalledPackageId :: UnitId -> InstalledPackageIndex
                         -> InstalledPackageIndex
310
deleteInstalledPackageId = deleteUnitId
Duncan Coutts's avatar
Duncan Coutts committed
311 312

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

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

333 334 335

-- | Removes all packages with this (case-sensitive) name from the index.
--
336 337 338 339
-- NB: Does NOT delete internal libraries from this package.
--
deletePackageName :: PackageName -> InstalledPackageIndex
                  -> InstalledPackageIndex
Duncan Coutts's avatar
Duncan Coutts committed
340
deletePackageName name original@(PackageIndex pids pnames) =
341
  case Map.lookup (name, Nothing) pnames of
Duncan Coutts's avatar
Duncan Coutts committed
342 343
    Nothing     -> original
    Just pvers  -> mkPackageIndex
344
                     (foldl' (flip (Map.delete . installedUnitId)) pids
Duncan Coutts's avatar
Duncan Coutts committed
345
                             (concat (Map.elems pvers)))
346
                     (Map.delete (name, Nothing) pnames)
347

Duncan Coutts's avatar
Duncan Coutts committed
348
{-
349 350
-- | Removes all packages satisfying this dependency from the index.
--
Duncan Coutts's avatar
Duncan Coutts committed
351
deleteDependency :: Dependency -> PackageIndex -> PackageIndex
352
deleteDependency (Dependency name verstionRange) =
Duncan Coutts's avatar
Duncan Coutts committed
353 354
  delete' name (\pkg -> packageVersion pkg `withinRange` verstionRange)
-}
355

356 357 358 359
--
-- * Bulk queries
--

360 361
-- | Get all the packages from the index.
--
362
allPackages :: PackageIndex a -> [a]
363
allPackages = Map.elems . unitIdIndex
364 365 366

-- | Get all the packages from the index.
--
367
-- They are grouped by package name (case-sensitively).
368
--
369 370
-- (Doesn't include private libraries.)
--
371
allPackagesByName :: PackageIndex a -> [(PackageName, [a])]
372
allPackagesByName index =
373
  [ (pkgname, concat (Map.elems pvers))
374
  | ((pkgname, Nothing), pvers) <- Map.toList (packageIdIndex index) ]
375 376 377 378 379

-- | Get all the packages from the index.
--
-- They are grouped by source package id (package name and version).
--
380 381
-- (Doesn't include private libraries)
--
382
allPackagesBySourcePackageId :: HasUnitId a => PackageIndex a
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
383
                             -> [(PackageId, [a])]
384
allPackagesBySourcePackageId index =
385
  [ (packageId ipkg, ipkgs)
386 387 388 389 390 391 392 393 394 395 396 397 398
  | ((_, Nothing), pvers) <- Map.toList (packageIdIndex index)
  , ipkgs@(ipkg:_) <- Map.elems pvers ]

-- | Get all the packages from the index.
--
-- They are grouped by source package id and library name.
--
-- This DOES include internal libraries.
allPackagesBySourcePackageIdAndLibName :: HasUnitId a => PackageIndex a
                             -> [((PackageId, Maybe UnqualComponentName), [a])]
allPackagesBySourcePackageIdAndLibName index =
  [ ((packageId ipkg, ln), ipkgs)
  | ((_, ln), pvers) <- Map.toList (packageIdIndex index)
399
  , ipkgs@(ipkg:_) <- Map.elems pvers ]
400 401 402 403 404

--
-- * Lookups
--

405
-- | Does a lookup by unit identifier.
406
--
407
-- Since multiple package DBs mask each other by 'UnitId',
408 409
-- then we get back at most one package.
--
410
lookupUnitId :: PackageIndex a -> UnitId
411
             -> Maybe a
412
lookupUnitId index uid = Map.lookup uid (unitIdIndex index)
413 414 415 416 417 418

-- | Does a lookup by component identifier.  In the absence
-- of Backpack, this is just a 'lookupUnitId'.
--
lookupComponentId :: PackageIndex a -> ComponentId
                  -> Maybe a
419 420
lookupComponentId index cid =
    Map.lookup (newSimpleUnitId cid) (unitIdIndex index)
Duncan Coutts's avatar
Duncan Coutts committed
421

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
422
-- | Backwards compatibility for Cabal pre-1.24.
423 424 425 426 427
{-# DEPRECATED lookupInstalledPackageId "Use lookupUnitId instead" #-}
lookupInstalledPackageId :: PackageIndex a -> UnitId
                         -> Maybe a
lookupInstalledPackageId = lookupUnitId

428

Duncan Coutts's avatar
Duncan Coutts committed
429 430 431
-- | Does a lookup by source package id (name & version).
--
-- There can be multiple installed packages with the same source 'PackageId'
432
-- but different 'UnitId'. They are returned in order of
Duncan Coutts's avatar
Duncan Coutts committed
433
-- preference, with the most preferred first.
434
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
435
lookupSourcePackageId :: PackageIndex a -> PackageId -> [a]
436
lookupSourcePackageId index pkgid =
437 438
  -- Do not lookup internal libraries
  case Map.lookup (packageName pkgid, Nothing) (packageIdIndex index) of
Duncan Coutts's avatar
Duncan Coutts committed
439 440 441 442
    Nothing     -> []
    Just pvers  -> case Map.lookup (packageVersion pkgid) pvers of
      Nothing   -> []
      Just pkgs -> pkgs -- in preference order
443

444 445
-- | Convenient alias of 'lookupSourcePackageId', but assuming only
-- one package per package ID.
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
446
lookupPackageId :: PackageIndex a -> PackageId -> Maybe a
447 448 449 450
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
451 452 453

-- | Does a lookup by source package name.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
454
lookupPackageName :: PackageIndex a -> PackageName
455
                  -> [(Version, [a])]
456
lookupPackageName index name =
457 458
  -- Do not match internal libraries
  case Map.lookup (name, Nothing) (packageIdIndex index) of
Duncan Coutts's avatar
Duncan Coutts committed
459 460 461 462 463
    Nothing     -> []
    Just pvers  -> Map.toList pvers


-- | Does a lookup by source package name and a range of versions.
464 465 466 467
--
-- We get back any number of versions of the specified package name, all
-- satisfying the version range constraint.
--
468 469 470
-- This does NOT work for internal dependencies, DO NOT use this
-- function on those; use 'lookupInternalDependency' instead.
--
471 472 473 474
-- INVARIANT: List of eligible 'IPI.InstalledPackageInfo' is non-empty.
--
lookupDependency :: InstalledPackageIndex -> Dependency
                 -> [(Version, [IPI.InstalledPackageInfo])]
475 476 477
lookupDependency index dep =
    -- Yes, a little bit of a misnomer here!
    lookupInternalDependency index dep Nothing
478

479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
-- | Does a lookup by source package name and a range of versions.
--
-- We get back any number of versions of the specified package name, all
-- satisfying the version range constraint.
--
-- INVARIANT: List of eligible 'IPI.InstalledPackageInfo' is non-empty.
--
lookupInternalDependency :: InstalledPackageIndex -> Dependency
                 -> Maybe UnqualComponentName
                 -> [(Version, [IPI.InstalledPackageInfo])]
lookupInternalDependency index (Dependency name versionRange) libn =
  case Map.lookup (name, libn) (packageIdIndex index) of
    Nothing    -> []
    Just pvers -> [ (ver, pkgs')
                  | (ver, pkgs) <- Map.toList pvers
                  , ver `withinRange` versionRange
                  , let pkgs' = filter eligible pkgs
                  -- Enforce the invariant
                  , not (null pkgs')
                  ]
 where
  -- When we select for dependencies, we ONLY want to pick up indefinite
  -- packages, or packages with no instantiations.  We'll do mix-in
  -- linking to improve any such package into an instantiated one
  -- later.
  eligible pkg = IPI.indefinite pkg || null (IPI.instantiatedWith pkg)


507 508 509
--
-- * Case insensitive name lookups
--
510 511 512

-- | Does a case-insensitive search by package name.
--
Ian D. Bollinger's avatar
Ian D. Bollinger committed
513
-- If there is only one package that compares case-insensitively to this name
514
-- then the search is unambiguous and we get back all versions of that package.
Ian D. Bollinger's avatar
Ian D. Bollinger committed
515
-- If several match case-insensitively but one matches exactly then it is also
516 517
-- unambiguous.
--
Ian D. Bollinger's avatar
Ian D. Bollinger committed
518
-- If however several match case-insensitively and none match exactly then we
519 520 521 522
-- 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.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
523
searchByName :: PackageIndex a -> String -> SearchResult [a]
524
searchByName index name =
525 526
  -- Don't match internal packages
  case [ pkgs | pkgs@((pname, Nothing),_) <- Map.toList (packageIdIndex index)
527
              , lowercase (unPackageName pname) == lname ] of
Duncan Coutts's avatar
Duncan Coutts committed
528 529
    []               -> None
    [(_,pvers)]      -> Unambiguous (concat (Map.elems pvers))
530
    pkgss            -> case find ((mkPackageName name ==) . fst . fst) pkgss of
Duncan Coutts's avatar
Duncan Coutts committed
531 532
      Just (_,pvers) -> Unambiguous (concat (Map.elems pvers))
      Nothing        -> Ambiguous (map (concat . Map.elems . snd) pkgss)
533
  where lname = lowercase name
534 535 536 537 538 539 540

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.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
541
searchByNameSubstring :: PackageIndex a -> String -> [a]
542
searchByNameSubstring index searchterm =
543
  [ pkg
544 545
  -- Don't match internal packages
  | ((pname, Nothing), pvers) <- Map.toList (packageIdIndex index)
546
  , lsearchterm `isInfixOf` lowercase (unPackageName pname)
Duncan Coutts's avatar
Duncan Coutts committed
547
  , pkgs <- Map.elems pvers
548
  , pkg <- pkgs ]
549
  where lsearchterm = lowercase searchterm
550

Duncan Coutts's avatar
Duncan Coutts committed
551 552 553 554 555 556 557 558

--
-- * Special queries
--

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

559 560 561 562 563 564 565
-- | 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.
--
566
dependencyCycles :: PackageInstalled a => PackageIndex a -> [[a]]
567
dependencyCycles index =
568 569
  [ vs | Graph.CyclicSCC vs <- Graph.stronglyConnComp adjacencyList ]
  where
570
    adjacencyList = [ (pkg, installedUnitId pkg, installedDepends pkg)
571 572 573
                    | pkg <- allPackages index ]


Duncan Coutts's avatar
Duncan Coutts committed
574
-- | All packages that have immediate dependencies that are not in the index.
575
--
576 577
-- Returns such packages along with the dependencies that they're missing.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
578
brokenPackages :: PackageInstalled a => PackageIndex a
579
               -> [(a, [UnitId])]
580
brokenPackages index =
581
  [ (pkg, missing)
Duncan Coutts's avatar
Duncan Coutts committed
582
  | pkg  <- allPackages index
583
  , let missing = [ pkg' | pkg' <- installedDepends pkg
584
                         , isNothing (lookupUnitId index pkg') ]
585 586
  , not (null missing) ]

587
-- | Tries to take the transitive closure of the package dependencies.
588
--
589
-- If the transitive closure is complete then it returns that subset of the
590 591 592
-- 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
593
-- the original given 'PackageId's do not occur in the index.
594
--
595
dependencyClosure :: InstalledPackageIndex
596
                  -> [UnitId]
597 598
                  -> Either (InstalledPackageIndex)
                            [(IPI.InstalledPackageInfo, [UnitId])]
599
dependencyClosure index pkgids0 = case closure mempty [] pkgids0 of
600 601
  (completed, []) -> Left completed
  (completed, _)  -> Right (brokenPackages completed)
602
 where
603
    closure completed failed []             = (completed, failed)
604
    closure completed failed (pkgid:pkgids) = case lookupUnitId index pkgid of
605
      Nothing   -> closure completed (pkgid:failed) pkgids
606
      Just pkg  -> case lookupUnitId completed (installedUnitId pkg) of
607 608
        Just _  -> closure completed  failed pkgids
        Nothing -> closure completed' failed pkgids'
Duncan Coutts's avatar
Duncan Coutts committed
609
          where completed' = insert pkg completed
610
                pkgids'    = installedDepends pkg ++ pkgids
611

612
-- | Takes the transitive closure of the packages reverse dependencies.
613
--
Duncan Coutts's avatar
Duncan Coutts committed
614
-- * The given 'PackageId's must be in the index.
615
--
616
reverseDependencyClosure :: PackageInstalled a => PackageIndex a
617
                         -> [UnitId]
618
                         -> [a]
619
reverseDependencyClosure index =
620 621 622 623
    map vertexToPkg
  . concatMap Tree.flatten
  . Graph.dfs reverseDepGraph
  . map (fromMaybe noSuchPkgId . pkgIdToVertex)
624

625
  where
626
    (depGraph, vertexToPkg, pkgIdToVertex) = dependencyGraph index
627 628 629
    reverseDepGraph = Graph.transposeG depGraph
    noSuchPkgId = error "reverseDependencyClosure: package is not in the graph"

630
topologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
631 632 633 634 635
topologicalOrder index = map toPkgId
                       . Graph.topSort
                       $ graph
  where (graph, toPkgId, _) = dependencyGraph index

636
reverseTopologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
637 638 639 640 641 642 643 644 645 646 647
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'.
--
648
dependencyGraph :: PackageInstalled a => PackageIndex a
649
                -> (Graph.Graph,
650
                    Graph.Vertex -> a,
651
                    UnitId -> Maybe Graph.Vertex)
652
dependencyGraph index = (graph, vertex_to_pkg, id_to_vertex)
653 654
  where
    graph = Array.listArray bounds
655
              [ [ v | Just v <- map id_to_vertex (installedDepends pkg) ]
656
              | pkg <- pkgs ]
657

Duncan Coutts's avatar
Duncan Coutts committed
658
    pkgs             = sortBy (comparing packageId) (allPackages index)
659
    vertices         = zip (map installedUnitId pkgs) [0..]
660
    vertex_map       = Map.fromList vertices
661
    id_to_vertex pid = Map.lookup pid vertex_map
662 663

    vertex_to_pkg vertex = pkgTable ! vertex
664 665 666 667 668

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

669 670
-- | We maintain the invariant that, for any 'DepUniqueKey', there
-- is only one instance of the package in our database.
671
type DepUniqueKey = (PackageName, Maybe UnqualComponentName, Map ModuleName OpenModule)
672

673 674 675 676 677 678 679 680 681 682
-- | 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.
--
683
dependencyInconsistencies :: InstalledPackageIndex
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701
                             -- At DepUniqueKey...
                          -> [(DepUniqueKey,
                               -- There were multiple packages (BAD!)
                               [(UnitId,
                                 -- And here are the packages which
                                 -- immediately depended on it
                                 [IPI.InstalledPackageInfo])])]
dependencyInconsistencies index = do
    (dep_key, insts_map) <- Map.toList inverseIndex
    let insts = Map.toList insts_map
    guard (length insts >= 2)
    return (dep_key, insts)
  where
    inverseIndex :: Map DepUniqueKey (Map UnitId [IPI.InstalledPackageInfo])
    inverseIndex = Map.fromListWith (Map.unionWith (++)) $ do
        pkg <- allPackages index
        dep_ipid <- installedDepends pkg
        Just dep <- [lookupUnitId index dep_ipid]
702 703
        let dep_key = (packageName dep, IPI.sourceLibName dep,
                       Map.fromList (IPI.instantiatedWith dep))
704
        return (dep_key, Map.singleton dep_ipid [pkg])
Duncan Coutts's avatar
Duncan Coutts committed
705

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
706 707 708 709
-- | A rough approximation of GHC's module finder, takes a
-- 'InstalledPackageIndex' and turns it into a map from module names to their
-- source packages.  It's used to initialize the @build-deps@ field in @cabal
-- init@.
710
moduleNameIndex :: InstalledPackageIndex -> Map ModuleName [IPI.InstalledPackageInfo]
Duncan Coutts's avatar
Duncan Coutts committed
711
moduleNameIndex index =
712 713
  Map.fromListWith (++) $ do
    pkg <- allPackages index
714
    IPI.ExposedModule m reexport <- IPI.exposedModules pkg
715 716
    case reexport of
        Nothing -> return (m, [pkg])
717 718
        Just (OpenModuleVar _) -> []
        Just (OpenModule _ m') | m == m'   -> []
719
                                | otherwise -> return (m', [pkg])
720 721 722 723 724
        -- 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!