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

3 4
-----------------------------------------------------------------------------
-- |
5
-- Module      :  Distribution.Simple.PackageIndex
6 7
-- Copyright   :  (c) David Himmelstrup 2005,
--                    Bjorn Bringert 2007,
Duncan Coutts's avatar
Duncan Coutts committed
8
--                    Duncan Coutts 2008-2009
9
--
Duncan Coutts's avatar
Duncan Coutts committed
10
-- Maintainer  :  cabal-devel@haskell.org
11 12
-- Portability :  portable
--
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
-- 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.
--
-- 'PackageIndex' is parametric over what it actually records, and it
-- is used in two ways:
--
--      * 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.)
--
--      * The 'PlanIndex' (defined in 'Distribution.Client.InstallPlan'),
--        contains a graph of 'GenericPlanPackage'.  Ignoring its type
--        parameters for a moment, a 'PlanIndex' is an extension of the
--        'InstalledPackageIndex' to also record nodes for packages
--        which are *planned* to be installed, but not actually
--        installed yet.  A 'PlanIndex' containing only 'PreExisting'
--        packages is essentially a 'PackageIndex'.
--
--        'PlanIndex'es actually require some auxiliary information, so
--        most users interact with a 'GenericInstallPlan'.  This type is
--        specialized as an 'ElaboratedInstallPlan' (for @cabal
--        new-build@) or an 'InstallPlan' (for @cabal install@).
--
-- 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
57
--
58 59
module Distribution.Simple.PackageIndex (
  -- * Package index data type
60
  InstalledPackageIndex,
61
  PackageIndex,
62

63
  -- * Creating an index
64 65
  fromList,

66
  -- * Updates
67
  merge,
Duncan Coutts's avatar
Duncan Coutts committed
68

69
  insert,
Duncan Coutts's avatar
Duncan Coutts committed
70

71
  deleteUnitId,
Duncan Coutts's avatar
Duncan Coutts committed
72
  deleteSourcePackageId,
73
  deletePackageName,
Duncan Coutts's avatar
Duncan Coutts committed
74
--  deleteDependency,
75 76 77 78

  -- * Queries

  -- ** Precise lookups
79
  lookupUnitId,
80
  lookupComponentId,
Duncan Coutts's avatar
Duncan Coutts committed
81
  lookupSourcePackageId,
82
  lookupPackageId,
83
  lookupPackageName,
84 85 86 87 88 89 90 91 92 93
  lookupDependency,

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

  -- ** Bulk queries
  allPackages,
  allPackagesByName,
94
  allPackagesBySourcePackageId,
95 96 97 98 99 100 101 102 103 104

  -- ** Special queries
  brokenPackages,
  dependencyClosure,
  reverseDependencyClosure,
  topologicalOrder,
  reverseTopologicalOrder,
  dependencyInconsistencies,
  dependencyCycles,
  dependencyGraph,
Duncan Coutts's avatar
Duncan Coutts committed
105
  moduleNameIndex,
106 107 108 109

  -- * Backwards compatibility
  deleteInstalledPackageId,
  lookupInstalledPackageId,
110 111
  ) where

112 113
import Prelude ()
import Distribution.Compat.Prelude hiding (lookup)
114
import qualified Distribution.Compat.Map.Strict as Map
115

116
import Distribution.Package
117
import Distribution.Backpack
118 119 120 121
import Distribution.ModuleName
import qualified Distribution.InstalledPackageInfo as IPI
import Distribution.Version
import Distribution.Simple.Utils
122
import Distribution.Types.Dependency
123

124
import Control.Exception (assert)
125
import Data.Array ((!))
ttuegel's avatar
ttuegel committed
126 127
import qualified Data.Array as Array
import qualified Data.Graph as Graph
128
import Data.List as List ( groupBy,  deleteBy, deleteFirstsBy )
ttuegel's avatar
ttuegel committed
129
import qualified Data.Tree  as Tree
130
import Control.Monad
131 132

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

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

157
  } deriving (Eq, Generic, Show, Read)
ttuegel's avatar
ttuegel committed
158 159

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

161 162
-- | The default package index which contains 'InstalledPackageInfo'.  Normally
-- use this.
163
type InstalledPackageIndex = PackageIndex IPI.InstalledPackageInfo
164

165
instance HasUnitId a => Monoid (PackageIndex a) where
Duncan Coutts's avatar
Duncan Coutts committed
166
  mempty  = PackageIndex Map.empty Map.empty
167
  mappend = (<>)
168
  --save one mappend with empty in the common case:
169
  mconcat [] = mempty
170 171
  mconcat xs = foldr1 mappend xs

172
instance HasUnitId a => Semigroup (PackageIndex a) where
173 174
  (<>) = merge

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

196

197 198 199 200
--
-- * Internal helpers
--

201 202
mkPackageIndex :: HasUnitId a
               => Map UnitId a
203 204
               -> Map PackageName (Map Version [a])
               -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
205 206
mkPackageIndex pids pnames = assert (invariant index) index
  where index = PackageIndex pids pnames
207

208 209 210

--
-- * Construction
211 212
--

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

236 237 238 239
--
-- * Updates
--

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

261

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

271
  where
272
    pids'   = Map.insert (installedUnitId pkg) pkg pids
Duncan Coutts's avatar
Duncan Coutts committed
273 274
    pnames' = insertPackageName pnames
    insertPackageName =
275
      Map.insertWith (\_ -> insertPackageVersion)
Duncan Coutts's avatar
Duncan Coutts committed
276 277 278 279
                     (packageName pkg)
                     (Map.singleton (packageVersion pkg) [pkg])

    insertPackageVersion =
280
      Map.insertWith (\_ -> insertPackageInstance)
Duncan Coutts's avatar
Duncan Coutts committed
281 282 283
                     (packageVersion pkg) [pkg]

    insertPackageInstance pkgs =
284
      pkg : deleteBy (equating installedUnitId) pkg pkgs
Duncan Coutts's avatar
Duncan Coutts committed
285 286 287 288


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

Duncan Coutts's avatar
Duncan Coutts committed
298
  where
Duncan Coutts's avatar
Duncan Coutts committed
299 300 301 302 303 304
    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
305

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

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
310
-- | Backwards compatibility wrapper for Cabal pre-1.24.
311 312 313 314 315
{-# DEPRECATED deleteInstalledPackageId "Use deleteUnitId instead" #-}
deleteInstalledPackageId :: HasUnitId a
                         => UnitId -> PackageIndex a
                         -> PackageIndex a
deleteInstalledPackageId = deleteUnitId
Duncan Coutts's avatar
Duncan Coutts committed
316 317

-- | Removes all packages with this source 'PackageId' from the index.
318
--
319
deleteSourcePackageId :: HasUnitId a => PackageId -> PackageIndex a
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
320
                      -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
321 322 323 324 325 326
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
327
                     (foldl' (flip (Map.delete . installedUnitId)) pids pkgs)
Duncan Coutts's avatar
Duncan Coutts committed
328 329 330 331 332 333 334 335 336
                     (deletePkgName pnames)
  where
    deletePkgName =
      Map.update deletePkgVersion (packageName pkgid)

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

337 338 339

-- | Removes all packages with this (case-sensitive) name from the index.
--
340
deletePackageName :: HasUnitId a => PackageName -> PackageIndex a
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
341
                  -> PackageIndex a
Duncan Coutts's avatar
Duncan Coutts committed
342 343 344 345
deletePackageName name original@(PackageIndex pids pnames) =
  case Map.lookup name pnames of
    Nothing     -> original
    Just pvers  -> mkPackageIndex
346
                     (foldl' (flip (Map.delete . installedUnitId)) pids
Duncan Coutts's avatar
Duncan Coutts committed
347 348
                             (concat (Map.elems pvers)))
                     (Map.delete name pnames)
349

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

358 359 360 361
--
-- * Bulk queries
--

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

-- | Get all the packages from the index.
--
369
-- They are grouped by package name (case-sensitively).
370
--
371
allPackagesByName :: PackageIndex a -> [(PackageName, [a])]
372
allPackagesByName index =
373
  [ (pkgname, concat (Map.elems pvers))
374
  | (pkgname, 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
allPackagesBySourcePackageId :: HasUnitId a => PackageIndex a
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
381
                             -> [(PackageId, [a])]
382
allPackagesBySourcePackageId index =
383
  [ (packageId ipkg, ipkgs)
384
  | pvers <- Map.elems (packageIdIndex index)
385
  , ipkgs@(ipkg:_) <- Map.elems pvers ]
386 387 388 389 390

--
-- * Lookups
--

391
-- | Does a lookup by unit identifier.
392
--
393
-- Since multiple package DBs mask each other by 'UnitId',
394 395
-- then we get back at most one package.
--
396
lookupUnitId :: PackageIndex a -> UnitId
397
             -> Maybe a
398
lookupUnitId index uid = Map.lookup uid (unitIdIndex index)
399 400 401 402 403 404

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

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
408
-- | Backwards compatibility for Cabal pre-1.24.
409 410 411 412 413
{-# DEPRECATED lookupInstalledPackageId "Use lookupUnitId instead" #-}
lookupInstalledPackageId :: PackageIndex a -> UnitId
                         -> Maybe a
lookupInstalledPackageId = lookupUnitId

414

Duncan Coutts's avatar
Duncan Coutts committed
415 416 417
-- | Does a lookup by source package id (name & version).
--
-- There can be multiple installed packages with the same source 'PackageId'
418
-- but different 'UnitId'. They are returned in order of
Duncan Coutts's avatar
Duncan Coutts committed
419
-- preference, with the most preferred first.
420
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
421
lookupSourcePackageId :: PackageIndex a -> PackageId -> [a]
422 423
lookupSourcePackageId index pkgid =
  case Map.lookup (packageName pkgid) (packageIdIndex index) of
Duncan Coutts's avatar
Duncan Coutts committed
424 425 426 427
    Nothing     -> []
    Just pvers  -> case Map.lookup (packageVersion pkgid) pvers of
      Nothing   -> []
      Just pkgs -> pkgs -- in preference order
428

429 430
-- | Convenient alias of 'lookupSourcePackageId', but assuming only
-- one package per package ID.
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
431
lookupPackageId :: PackageIndex a -> PackageId -> Maybe a
432 433 434 435
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
436 437 438

-- | Does a lookup by source package name.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
439
lookupPackageName :: PackageIndex a -> PackageName
440
                  -> [(Version, [a])]
441 442
lookupPackageName index name =
  case Map.lookup name (packageIdIndex index) of
Duncan Coutts's avatar
Duncan Coutts committed
443 444 445 446 447
    Nothing     -> []
    Just pvers  -> Map.toList pvers


-- | Does a lookup by source package name and a range of versions.
448 449 450 451
--
-- We get back any number of versions of the specified package name, all
-- satisfying the version range constraint.
--
452 453 454 455
-- INVARIANT: List of eligible 'IPI.InstalledPackageInfo' is non-empty.
--
lookupDependency :: InstalledPackageIndex -> Dependency
                 -> [(Version, [IPI.InstalledPackageInfo])]
456 457
lookupDependency index (Dependency name versionRange) =
  case Map.lookup name (packageIdIndex index) of
Duncan Coutts's avatar
Duncan Coutts committed
458
    Nothing    -> []
459 460 461 462 463 464 465 466 467 468 469 470 471
    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)
472 473 474 475

--
-- * Case insensitive name lookups
--
476 477 478

-- | Does a case-insensitive search by package name.
--
Ian D. Bollinger's avatar
Ian D. Bollinger committed
479
-- If there is only one package that compares case-insensitively to this name
480
-- then the search is unambiguous and we get back all versions of that package.
Ian D. Bollinger's avatar
Ian D. Bollinger committed
481
-- If several match case-insensitively but one matches exactly then it is also
482 483
-- unambiguous.
--
Ian D. Bollinger's avatar
Ian D. Bollinger committed
484
-- If however several match case-insensitively and none match exactly then we
485 486 487 488
-- 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
489
searchByName :: PackageIndex a -> String -> SearchResult [a]
490
searchByName index name =
491 492
  case [ pkgs | pkgs@(pname,_) <- Map.toList (packageIdIndex index)
              , lowercase (unPackageName pname) == lname ] of
Duncan Coutts's avatar
Duncan Coutts committed
493 494
    []               -> None
    [(_,pvers)]      -> Unambiguous (concat (Map.elems pvers))
495
    pkgss            -> case find ((mkPackageName name ==) . fst) pkgss of
Duncan Coutts's avatar
Duncan Coutts committed
496 497
      Just (_,pvers) -> Unambiguous (concat (Map.elems pvers))
      Nothing        -> Ambiguous (map (concat . Map.elems . snd) pkgss)
498
  where lname = lowercase name
499 500 501 502 503 504 505

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
506
searchByNameSubstring :: PackageIndex a -> String -> [a]
507
searchByNameSubstring index searchterm =
508
  [ pkg
509 510
  | (pname, pvers) <- Map.toList (packageIdIndex index)
  , lsearchterm `isInfixOf` lowercase (unPackageName pname)
Duncan Coutts's avatar
Duncan Coutts committed
511
  , pkgs <- Map.elems pvers
512
  , pkg <- pkgs ]
513
  where lsearchterm = lowercase searchterm
514

Duncan Coutts's avatar
Duncan Coutts committed
515 516 517 518 519 520 521 522

--
-- * Special queries
--

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

523 524 525 526 527 528 529
-- | 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.
--
530
dependencyCycles :: PackageInstalled a => PackageIndex a -> [[a]]
531
dependencyCycles index =
532 533
  [ vs | Graph.CyclicSCC vs <- Graph.stronglyConnComp adjacencyList ]
  where
534
    adjacencyList = [ (pkg, installedUnitId pkg, installedDepends pkg)
535 536 537
                    | pkg <- allPackages index ]


Duncan Coutts's avatar
Duncan Coutts committed
538
-- | All packages that have immediate dependencies that are not in the index.
539
--
540 541
-- Returns such packages along with the dependencies that they're missing.
--
Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
542
brokenPackages :: PackageInstalled a => PackageIndex a
543
               -> [(a, [UnitId])]
544
brokenPackages index =
545
  [ (pkg, missing)
Duncan Coutts's avatar
Duncan Coutts committed
546
  | pkg  <- allPackages index
547
  , let missing = [ pkg' | pkg' <- installedDepends pkg
548
                         , isNothing (lookupUnitId index pkg') ]
549 550
  , not (null missing) ]

551
-- | Tries to take the transitive closure of the package dependencies.
552
--
553
-- If the transitive closure is complete then it returns that subset of the
554 555 556
-- 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
557
-- the original given 'PackageId's do not occur in the index.
558
--
559
dependencyClosure :: PackageInstalled a => PackageIndex a
560
                  -> [UnitId]
561
                  -> Either (PackageIndex a)
562
                            [(a, [UnitId])]
563
dependencyClosure index pkgids0 = case closure mempty [] pkgids0 of
564 565
  (completed, []) -> Left completed
  (completed, _)  -> Right (brokenPackages completed)
566
 where
567
    closure completed failed []             = (completed, failed)
568
    closure completed failed (pkgid:pkgids) = case lookupUnitId index pkgid of
569
      Nothing   -> closure completed (pkgid:failed) pkgids
570
      Just pkg  -> case lookupUnitId completed (installedUnitId pkg) of
571 572
        Just _  -> closure completed  failed pkgids
        Nothing -> closure completed' failed pkgids'
Duncan Coutts's avatar
Duncan Coutts committed
573
          where completed' = insert pkg completed
574
                pkgids'    = installedDepends pkg ++ pkgids
575

576
-- | Takes the transitive closure of the packages reverse dependencies.
577
--
Duncan Coutts's avatar
Duncan Coutts committed
578
-- * The given 'PackageId's must be in the index.
579
--
580
reverseDependencyClosure :: PackageInstalled a => PackageIndex a
581
                         -> [UnitId]
582
                         -> [a]
583
reverseDependencyClosure index =
584 585 586 587
    map vertexToPkg
  . concatMap Tree.flatten
  . Graph.dfs reverseDepGraph
  . map (fromMaybe noSuchPkgId . pkgIdToVertex)
588

589
  where
590
    (depGraph, vertexToPkg, pkgIdToVertex) = dependencyGraph index
591 592 593
    reverseDepGraph = Graph.transposeG depGraph
    noSuchPkgId = error "reverseDependencyClosure: package is not in the graph"

594
topologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
595 596 597 598 599
topologicalOrder index = map toPkgId
                       . Graph.topSort
                       $ graph
  where (graph, toPkgId, _) = dependencyGraph index

600
reverseTopologicalOrder :: PackageInstalled a => PackageIndex a -> [a]
601 602 603 604 605 606 607 608 609 610 611
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'.
--
612
dependencyGraph :: PackageInstalled a => PackageIndex a
613
                -> (Graph.Graph,
614
                    Graph.Vertex -> a,
615
                    UnitId -> Maybe Graph.Vertex)
616
dependencyGraph index = (graph, vertex_to_pkg, id_to_vertex)
617 618
  where
    graph = Array.listArray bounds
619
              [ [ v | Just v <- map id_to_vertex (installedDepends pkg) ]
620
              | pkg <- pkgs ]
621

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

    vertex_to_pkg vertex = pkgTable ! vertex
628 629 630 631 632

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

633 634 635 636
-- | We maintain the invariant that, for any 'DepUniqueKey', there
-- is only one instance of the package in our database.
type DepUniqueKey = (PackageName, Map ModuleName OpenModule)

637 638 639 640 641 642 643 644 645 646
-- | 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.
--
647
dependencyInconsistencies :: InstalledPackageIndex
648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667
                             -- 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]
        let dep_key = (packageName dep, Map.fromList (IPI.instantiatedWith dep))
        return (dep_key, Map.singleton dep_ipid [pkg])
Duncan Coutts's avatar
Duncan Coutts committed
668

Mikhail Glushenkov's avatar
Mikhail Glushenkov committed
669 670 671 672
-- | 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@.
673
moduleNameIndex :: InstalledPackageIndex -> Map ModuleName [IPI.InstalledPackageInfo]
Duncan Coutts's avatar
Duncan Coutts committed
674
moduleNameIndex index =
675 676
  Map.fromListWith (++) $ do
    pkg <- allPackages index
677
    IPI.ExposedModule m reexport <- IPI.exposedModules pkg
678 679
    case reexport of
        Nothing -> return (m, [pkg])
680 681
        Just (OpenModuleVar _) -> []
        Just (OpenModule _ m') | m == m'   -> []
682
                                | otherwise -> return (m', [pkg])
683 684 685 686 687
        -- 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!