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

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 15 16 17 18 19
-- 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
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
-- 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.)
39 40 41 42 43
--
-- 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
44
--
45 46
module Distribution.Simple.PackageIndex (
  -- * Package index data type
47
  InstalledPackageIndex,
48
  PackageIndex,
49

50
  -- * Creating an index
51 52
  fromList,

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

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

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

  -- * Queries

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Edward Z. Yang's avatar
Edward Z. Yang committed
166 167
{-# NOINLINE invariant #-}
invariant :: WithCallStack (InstalledPackageIndex -> Bool)
Duncan Coutts's avatar
Duncan Coutts committed
168
invariant (PackageIndex pids pnames) =
Edward Z. Yang's avatar
Edward Z. Yang committed
169 170 171 172 173
  -- trace (show pids' ++ "\n" ++ show pnames') $
  pids' == pnames'
 where
  pids' = map installedUnitId (Map.elems pids)
  pnames' = sort
174
     [ assert pinstOk (installedUnitId pinst)
175
     | ((pname, plib), pvers)  <- Map.toList pnames
Duncan Coutts's avatar
Duncan Coutts committed
176 177
     , let pversOk = not (Map.null pvers)
     , (pver,  pinsts) <- assert pversOk $ Map.toList pvers
178
     , let pinsts'  = sortBy (comparing installedUnitId) pinsts
Duncan Coutts's avatar
Duncan Coutts committed
179
           pinstsOk = all (\g -> length g == 1)
180
                          (groupBy (equating installedUnitId) pinsts')
Duncan Coutts's avatar
Duncan Coutts committed
181 182 183
     , pinst           <- assert pinstsOk $ pinsts'
     , let pinstOk = packageName    pinst == pname
                  && packageVersion pinst == pver
184
                  && IPI.sourceLibName  pinst == plib
Duncan Coutts's avatar
Duncan Coutts committed
185
     ]
186 187 188 189 190
  -- 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
191

192

193 194 195 196
--
-- * Internal helpers
--

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

204 205 206

--
-- * Construction
207 208
--

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

232 233 234 235
--
-- * Updates
--

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

257

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

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

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

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


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

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

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

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

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

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

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

332 333 334

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

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

355 356 357 358
--
-- * Bulk queries
--

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

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

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

--
-- * Lookups
--

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

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

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

427

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

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

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


-- | Does a lookup by source package name and a range of versions.
463 464 465 466
--
-- We get back any number of versions of the specified package name, all
-- satisfying the version range constraint.
--
467 468 469
-- This does NOT work for internal dependencies, DO NOT use this
-- function on those; use 'lookupInternalDependency' instead.
--
470 471 472 473
-- INVARIANT: List of eligible 'IPI.InstalledPackageInfo' is non-empty.
--
lookupDependency :: InstalledPackageIndex -> Dependency
                 -> [(Version, [IPI.InstalledPackageInfo])]
474
lookupDependency index (Dependency name versionRange) =
475
  case Map.lookup (name, Nothing) (packageIdIndex index) of
Duncan Coutts's avatar
Duncan Coutts committed
476
    Nothing    -> []
477 478 479 480 481 482 483 484 485 486 487 488 489
    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)
490

491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518
-- | 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)


519 520 521
--
-- * Case insensitive name lookups
--
522 523 524

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

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
553
searchByNameSubstring :: PackageIndex a -> String -> [a]
554
searchByNameSubstring index searchterm =
555
  [ pkg
556 557
  -- Don't match internal packages
  | ((pname, Nothing), pvers) <- Map.toList (packageIdIndex index)
558
  , lsearchterm `isInfixOf` lowercase (unPackageName pname)
Duncan Coutts's avatar
Duncan Coutts committed
559
  , pkgs <- Map.elems pvers
560
  , pkg <- pkgs ]
561
  where lsearchterm = lowercase searchterm
562

Duncan Coutts's avatar
Duncan Coutts committed
563 564 565 566 567 568 569 570

--
-- * Special queries
--

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

571 572 573 574 575 576 577
-- | 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.
--
578
dependencyCycles :: PackageInstalled a => PackageIndex a -> [[a]]
579
dependencyCycles index =
580 581
  [ vs | Graph.CyclicSCC vs <- Graph.stronglyConnComp adjacencyList ]
  where
582
    adjacencyList = [ (pkg, installedUnitId pkg, installedDepends pkg)
583 584 585
                    | pkg <- allPackages index ]


Duncan Coutts's avatar
Duncan Coutts committed
586
-- | All packages that have immediate dependencies that are not in the index.
587
--
588 589
-- Returns such packages along with the dependencies that they're missing.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
590
brokenPackages :: PackageInstalled a => PackageIndex a
591
               -> [(a, [UnitId])]
592
brokenPackages index =
593
  [ (pkg, missing)
Duncan Coutts's avatar
Duncan Coutts committed
594
  | pkg  <- allPackages index
595
  , let missing = [ pkg' | pkg' <- installedDepends pkg
596
                         , isNothing (lookupUnitId index pkg') ]
597 598
  , not (null missing) ]

599
-- | Tries to take the transitive closure of the package dependencies.
600
--
601
-- If the transitive closure is complete then it returns that subset of the
602 603 604
-- 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
605
-- the original given 'PackageId's do not occur in the index.
606
--
607
dependencyClosure :: InstalledPackageIndex
608
                  -> [UnitId]
609 610
                  -> Either (InstalledPackageIndex)
                            [(IPI.InstalledPackageInfo, [UnitId])]
611
dependencyClosure index pkgids0 = case closure mempty [] pkgids0 of
612 613
  (completed, []) -> Left completed
  (completed, _)  -> Right (brokenPackages completed)
614
 where
615
    closure completed failed []             = (completed, failed)
616
    closure completed failed (pkgid:pkgids) = case lookupUnitId index pkgid of
617
      Nothing   -> closure completed (pkgid:failed) pkgids
618
      Just pkg  -> case lookupUnitId completed (installedUnitId pkg) of
619 620
        Just _  -> closure completed  failed pkgids
        Nothing -> closure completed' failed pkgids'
Duncan Coutts's avatar
Duncan Coutts committed
621
          where completed' = insert pkg completed
622
                pkgids'    = installedDepends pkg ++ pkgids
623

624
-- | Takes the transitive closure of the packages reverse dependencies.
625
--
Duncan Coutts's avatar
Duncan Coutts committed
626
-- * The given 'PackageId's must be in the index.
627
--
628
reverseDependencyClosure :: PackageInstalled a => PackageIndex a
629
                         -> [UnitId]
630
                         -> [a]
631
reverseDependencyClosure index =
632 633 634 635
    map vertexToPkg
  . concatMap Tree.flatten
  . Graph.dfs reverseDepGraph
  . map (fromMaybe noSuchPkgId . pkgIdToVertex)
636

637
  where
638
    (depGraph, vertexToPkg, pkgIdToVertex) = dependencyGraph index
639 640 641
    reverseDepGraph = Graph.transposeG depGraph
    noSuchPkgId = error "reverseDependencyClosure: package is not in the graph"

642
topologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
643 644 645 646 647
topologicalOrder index = map toPkgId
                       . Graph.topSort
                       $ graph
  where (graph, toPkgId, _) = dependencyGraph index

648
reverseTopologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
649 650 651 652 653 654 655 656 657 658 659
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'.
--
660
dependencyGraph :: PackageInstalled a => PackageIndex a
661
                -> (Graph.Graph,
662
                    Graph.Vertex -> a,
663
                    UnitId -> Maybe Graph.Vertex)
664
dependencyGraph index = (graph, vertex_to_pkg, id_to_vertex)
665 666
  where
    graph = Array.listArray bounds
667
              [ [ v | Just v <- map id_to_vertex (installedDepends pkg) ]
668
              | pkg <- pkgs ]
669

Duncan Coutts's avatar
Duncan Coutts committed
670
    pkgs             = sortBy (comparing packageId) (allPackages index)
671
    vertices         = zip (map installedUnitId pkgs) [0..]
672
    vertex_map       = Map.fromList vertices
673
    id_to_vertex pid = Map.lookup pid vertex_map
674 675

    vertex_to_pkg vertex = pkgTable ! vertex
676 677 678 679 680

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

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

685 686 687 688 689 690 691 692 693 694
-- | 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.
--
695
dependencyInconsistencies :: InstalledPackageIndex
696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713
                             -- 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]
714 715
        let dep_key = (packageName dep, IPI.sourceLibName dep,
                       Map.fromList (IPI.instantiatedWith dep))
716
        return (dep_key, Map.singleton dep_ipid [pkg])
Duncan Coutts's avatar
Duncan Coutts committed
717

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
718 719 720 721
-- | 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@.
722
moduleNameIndex :: InstalledPackageIndex -> Map ModuleName [IPI.InstalledPackageInfo]
Duncan Coutts's avatar
Duncan Coutts committed
723
moduleNameIndex index =
724 725
  Map.fromListWith (++) $ do
    pkg <- allPackages index
726
    IPI.ExposedModule m reexport <- IPI.exposedModules pkg
727 728
    case reexport of
        Nothing -> return (m, [pkg])
729 730
        Just (OpenModuleVar _) -> []
        Just (OpenModule _ m') | m == m'   -> []
731
                                | otherwise -> return (m', [pkg])
732 733 734 735 736
        -- 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!