-----------------------------------------------------------------------------
-- |
-- Module      :  Distribution.Simple.PackageIndex
-- Copyright   :  (c) David Himmelstrup 2005,
--                    Bjorn Bringert 2007,
--                    Duncan Coutts 2008-2009
--
-- Maintainer  :  cabal-devel@haskell.org
-- Portability :  portable
--
-- An index of packages.
--
module Distribution.Simple.PackageIndex (
  -- * Package index data type
  PackageIndex,

  -- * Creating an index
  fromList,

  -- * Updates
  merge,

  insert,

  deleteInstalledPackageId,
  deleteSourcePackageId,
  deletePackageName,
--  deleteDependency,

  -- * Queries

  -- ** Precise lookups
  lookupInstalledPackageId,
  lookupSourcePackageId,
  lookupPackageName,
  lookupDependency,

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

  -- ** Bulk queries
  allPackages,
  allPackagesByName,

  -- ** Special queries
  brokenPackages,
  dependencyClosure,
  reverseDependencyClosure,
  topologicalOrder,
  reverseTopologicalOrder,
  dependencyInconsistencies,
  dependencyCycles,
  dependencyGraph,
  moduleNameIndex,
  ) where

import Prelude hiding (lookup)
import Control.Exception (assert)
import qualified Data.Map as Map
import Data.Map (Map)
import qualified Data.Tree  as Tree
import qualified Data.Graph as Graph
import qualified Data.Array as Array
import Data.Array ((!))
import Data.List as List
         ( null, foldl', sort
         , groupBy, sortBy, find, isInfixOf, nubBy, deleteBy, deleteFirstsBy )
import Data.Monoid (Monoid(..))
import Data.Maybe (isNothing, fromMaybe)

import Distribution.Package
         ( PackageName(..), PackageId
         , Package(..), packageName, packageVersion
         , Dependency(Dependency)--, --PackageFixedDeps(..)
         , InstalledPackageId(..) )
import Distribution.ModuleName
         ( ModuleName )
import Distribution.InstalledPackageInfo
         ( InstalledPackageInfo, installedPackageId )
import qualified Distribution.InstalledPackageInfo as IPI
import Distribution.Version
         ( Version, withinRange )
import Distribution.Simple.Utils (lowercase, comparing, equating)


-- | The collection of information about packages from one or more 'PackageDB's.
--
-- Packages are uniquely identified in by their 'InstalledPackageId', they can
-- also be effeciently looked up by package name or by name and version.
--
data PackageIndex = PackageIndex
  -- The primary index. Each InstalledPackageInfo record is uniquely identified
  -- by its InstalledPackageId.
  --
  !(Map InstalledPackageId InstalledPackageInfo)

  -- This auxillary index maps package names (case-sensitively) to all the
  -- versions and instances of that package. This allows us to find all
  -- versions satisfying a dependency.
  --
  -- It is a three-level index. The first level is the package name,
  -- the second is the package version and the final level is instances
  -- of the same package version. These are unique by InstalledPackageId
  -- and are kept in preference order.
  --
  !(Map PackageName (Map Version [InstalledPackageInfo]))

  deriving (D:Show ::
  (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> T:Show aShow, D:Read ::
  (Int -> ReadS a)
  -> ReadS [a]
  -> ReadPrec a
  -> ReadPrec [a]
  -> T:Read aRead)

instance ($cmappend) :: PackageIndex -> PackageIndex -> PackageIndexMonoid PackageIndex where
  mempty  = ($WPackageIndex) ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexPackageIndex empty :: Map k aMap.empty empty :: Map k aMap.empty
  mappend = merge :: PackageIndex -> PackageIndex -> PackageIndexmerge
  --save one mappend with empty in the common case:
  mconcat [] = mempty :: Monoid a => amempty
  mconcat xs = foldr1 :: (a -> a -> a) -> [a] -> afoldr1 mappend :: Monoid a => a -> a -> amappend xs :: [PackageIndex]xs

invariant :: PackageIndex -> Bool
invariant (PackageIndex pids pnames) =
     map :: (a -> b) -> [a] -> [b]map installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId (elems :: Map k a -> [a]Map.elems pids :: Map InstalledPackageId InstalledPackageInfopids)
  (==) :: Eq a => a -> a -> Bool== sort :: Ord a => [a] -> [a]sort
     [ assertError :: Addr# -> Bool -> a -> aassert pinstOk :: BoolpinstOk (installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pinst :: InstalledPackageInfo_ ModuleNamepinst)
     | (pname, pvers)  <- toList :: Map k a -> [(k, a)]Map.toList pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames
     , let pversOk = not :: Bool -> Boolnot (null :: Map k a -> BoolMap.null pvers :: Map Version [InstalledPackageInfo]pvers)
     , (pver,  pinsts) <- assertError :: Addr# -> Bool -> a -> aassert pversOk :: BoolpversOk ($) :: (a -> b) -> a -> b$ toList :: Map k a -> [(k, a)]Map.toList pvers :: Map Version [InstalledPackageInfo]pvers
     , let pinsts'  = sortBy :: (a -> a -> Ordering) -> [a] -> [a]sortBy (comparing :: Ord a => (b -> a) -> b -> b -> Orderingcomparing installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId) pinsts :: [InstalledPackageInfo]pinsts
           pinstsOk = all :: (a -> Bool) -> [a] -> Boolall (\g -> length :: [a] -> Intlength g :: [InstalledPackageInfo_ ModuleName]g (==) :: Eq a => a -> a -> Bool== 1)
                          (groupBy :: (a -> a -> Bool) -> [a] -> [[a]]groupBy (equating :: Eq a => (b -> a) -> b -> b -> Boolequating installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId) pinsts' :: [InstalledPackageInfo_ ModuleName]pinsts')
     , pinst           <- assertError :: Addr# -> Bool -> a -> aassert pinstsOk :: BoolpinstsOk ($) :: (a -> b) -> a -> b$ pinsts' :: [InstalledPackageInfo_ ModuleName]pinsts'
     , let pinstOk = packageName :: Package pkg => pkg -> PackageNamepackageName    pinst :: InstalledPackageInfo_ ModuleNamepinst (==) :: Eq a => a -> a -> Bool== pname :: PackageNamepname
                  (&&) :: Bool -> Bool -> Bool&& packageVersion :: Package pkg => pkg -> VersionpackageVersion pinst :: InstalledPackageInfo_ ModuleNamepinst (==) :: Eq a => a -> a -> Bool== pver :: Versionpver
     ]


--
-- * Internal helpers
--

mkPackageIndex :: Map InstalledPackageId InstalledPackageInfo
               -> Map PackageName (Map Version [InstalledPackageInfo])
               -> PackageIndex
mkPackageIndex pids pnames = assertError :: Addr# -> Bool -> a -> aassert (invariant :: PackageIndex -> Boolinvariant index :: PackageIndexindex) index :: PackageIndexindex
  where index = ($WPackageIndex) ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexPackageIndex pids :: Map InstalledPackageId InstalledPackageInfopids pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames


--
-- * Construction
--

-- | Build an index out of a bunch of packages.
--
-- If there are duplicates by 'InstalledPackageId' then later ones mask earlier
-- ones.
--
fromList :: [InstalledPackageInfo] -> PackageIndex
fromList pkgs = mkPackageIndex ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexmkPackageIndex pids :: Map InstalledPackageId InstalledPackageInfopids pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames
  where
    pids      = fromList :: Ord k => [(k, a)] -> Map k aMap.fromList [ (installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pkg :: InstalledPackageInfo_ mpkg, pkg :: InstalledPackageInfo_ mpkg) | pkg <- pkgs :: [InstalledPackageInfo]pkgs ]
    pnames    =
      fromList :: Ord k => [(k, a)] -> Map k aMap.fromList
        [ (packageName :: Package pkg => pkg -> PackageNamepackageName (head :: [a] -> ahead pkgsN :: [InstalledPackageInfo]pkgsN), pvers :: Map Version [InstalledPackageInfo]pvers)
        | pkgsN <- groupBy :: (a -> a -> Bool) -> [a] -> [[a]]groupBy (equating :: Eq a => (b -> a) -> b -> b -> Boolequating  packageName :: Package pkg => pkg -> PackageNamepackageName)
                 (.) :: (b -> c) -> (a -> b) -> a -> c. sortBy :: (a -> a -> Ordering) -> [a] -> [a]sortBy  (comparing :: Ord a => (b -> a) -> b -> b -> Orderingcomparing packageId :: Package pkg => pkg -> PackageIdentifierpackageId)
                 ($) :: (a -> b) -> a -> b$ pkgs :: [InstalledPackageInfo]pkgs
        , let pvers =
                fromList :: Ord k => [(k, a)] -> Map k aMap.fromList
                [ (packageVersion :: Package pkg => pkg -> VersionpackageVersion (head :: [a] -> ahead pkgsNV :: [InstalledPackageInfo]pkgsNV),
                   nubBy :: (a -> a -> Bool) -> [a] -> [a]nubBy (equating :: Eq a => (b -> a) -> b -> b -> Boolequating installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId) (reverse :: [a] -> [a]reverse pkgsNV :: [InstalledPackageInfo]pkgsNV))
                | pkgsNV <- groupBy :: (a -> a -> Bool) -> [a] -> [[a]]groupBy (equating :: Eq a => (b -> a) -> b -> b -> Boolequating packageVersion :: Package pkg => pkg -> VersionpackageVersion) pkgsN :: [InstalledPackageInfo]pkgsN
                ]
        ]

--
-- * Updates
--

-- | Merge two indexes.
--
-- Packages from the second mask packages from the first if they have the exact
-- same 'InstalledPackageId'.
--
-- 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.
--
merge :: PackageIndex -> PackageIndex -> PackageIndex
merge (PackageIndex pids1 pnames1) (PackageIndex pids2 pnames2) =
  mkPackageIndex ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexmkPackageIndex (union :: Ord k => Map k a -> Map k a -> Map k aMap.union pids1 :: Map InstalledPackageId InstalledPackageInfopids1 pids2 :: Map InstalledPackageId InstalledPackageInfopids2)
                 (unionWith ::
  Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k aMap.unionWith (unionWith ::
  Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k aMap.unionWith mergeBuckets ::
  [InstalledPackageInfo_ m]
  -> [InstalledPackageInfo_ m]
  -> [InstalledPackageInfo_ m]mergeBuckets) pnames1 :: Map PackageName (Map Version [InstalledPackageInfo])pnames1 pnames2 :: Map PackageName (Map Version [InstalledPackageInfo])pnames2)
  where
    -- Packages in the second list mask those in the first, however preferred
    -- packages go first in the list.
    mergeBuckets xs ys = ys :: [InstalledPackageInfo_ m]ys (++) :: [a] -> [a] -> [a]++ (xs :: [PackageIndex]xs (\\) ::
  [InstalledPackageInfo_ m]
  -> [InstalledPackageInfo_ m]
  -> [InstalledPackageInfo_ m]\\ ys :: [InstalledPackageInfo_ m]ys)
    (\\) = deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]deleteFirstsBy (equating :: Eq a => (b -> a) -> b -> b -> Boolequating installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId)


-- | Inserts a single package into the index.
--
-- This is equivalent to (but slightly quicker than) using 'mappend' or
-- 'merge' with a singleton index.
--
insert :: InstalledPackageInfo -> PackageIndex -> PackageIndex
insert pkg (PackageIndex pids pnames) =
    mkPackageIndex ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexmkPackageIndex pids' :: Map InstalledPackageId InstalledPackageInfopids' pnames' :: Map PackageName (Map Version [InstalledPackageInfo])pnames'

  where
    pids'   = insert :: Ord k => k -> a -> Map k a -> Map k aMap.insert (installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pkg :: InstalledPackageInfo_ mpkg) pkg :: InstalledPackageInfo_ mpkg pids :: Map InstalledPackageId InstalledPackageInfopids
    pnames' = insertPackageName ::
  Map PackageName (Map Version [InstalledPackageInfo])
  -> Map PackageName (Map Version [InstalledPackageInfo])insertPackageName pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames
    insertPackageName =
      insertWith' ::
  Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aMap.insertWith' (\_ -> insertPackageVersion ::
  Map Version [InstalledPackageInfo]
  -> Map Version [InstalledPackageInfo]insertPackageVersion)
                     (packageName :: Package pkg => pkg -> PackageNamepackageName pkg :: InstalledPackageInfo_ mpkg)
                     (singleton :: k -> a -> Map k aMap.singleton (packageVersion :: Package pkg => pkg -> VersionpackageVersion pkg :: InstalledPackageInfo_ mpkg) [pkg :: InstalledPackageInfo_ mpkg])

    insertPackageVersion =
      insertWith' ::
  Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aMap.insertWith' (\_ -> insertPackageInstance ::
  [InstalledPackageInfo] -> [InstalledPackageInfo]insertPackageInstance)
                     (packageVersion :: Package pkg => pkg -> VersionpackageVersion pkg :: InstalledPackageInfo_ mpkg) [pkg :: InstalledPackageInfo_ mpkg]

    insertPackageInstance pkgs =
      pkg :: InstalledPackageInfo_ mpkg (:) :: a -> [a] -> [a]: deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]deleteBy (equating :: Eq a => (b -> a) -> b -> b -> Boolequating installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId) pkg :: InstalledPackageInfo_ mpkg pkgs :: [InstalledPackageInfo]pkgs


-- | Removes a single installed package from the index.
--
deleteInstalledPackageId :: InstalledPackageId -> PackageIndex -> PackageIndex
deleteInstalledPackageId ipkgid original@(PackageIndex pids pnames) =
  case updateLookupWithKey ::
  Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)Map.updateLookupWithKey (\_ _ -> Nothing :: Maybe aNothing) ipkgid :: InstalledPackageIdipkgid pids :: Map InstalledPackageId InstalledPackageInfopids of
    (Nothing,     _)     -> original :: PackageIndexoriginal
    (Just spkgid, pids') -> mkPackageIndex ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexmkPackageIndex pids' :: Map InstalledPackageId InstalledPackageInfopids'
                                          (deletePkgName ::
  Map PackageName (Map Version a) -> Map PackageName (Map Version a)deletePkgName spkgid :: pkgspkgid pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames)

  where
    deletePkgName spkgid =
      update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k aMap.update (deletePkgVersion :: Map Version a -> Maybe (Map Version a)deletePkgVersion spkgid :: pkgspkgid) (packageName :: Package pkg => pkg -> PackageNamepackageName spkgid :: pkgspkgid)

    deletePkgVersion spkgid =
        (\m -> if null :: Map k a -> BoolMap.null m :: Map Version am then Nothing :: Maybe aNothing else Just :: a -> Maybe aJust m :: Map Version am)
      (.) :: (b -> c) -> (a -> b) -> a -> c. update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k aMap.update deletePkgInstance ::
  [InstalledPackageInfo_ m] -> Maybe [InstalledPackageInfo_ m]deletePkgInstance (packageVersion :: Package pkg => pkg -> VersionpackageVersion spkgid :: pkgspkgid)

    deletePkgInstance =
        (\xs -> if null :: [a] -> BoolList.null xs :: [PackageIndex]xs then Nothing :: Maybe aNothing else Just :: a -> Maybe aJust xs :: [PackageIndex]xs)
      (.) :: (b -> c) -> (a -> b) -> a -> c. deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]List.deleteBy (\_ pkg -> installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pkg :: InstalledPackageInfo_ mpkg (==) :: Eq a => a -> a -> Bool== ipkgid :: InstalledPackageIdipkgid) undefined :: aundefined


-- | Removes all packages with this source 'PackageId' from the index.
--
deleteSourcePackageId :: PackageId -> PackageIndex -> PackageIndex
deleteSourcePackageId pkgid original@(PackageIndex pids pnames) =
  case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup (packageName :: Package pkg => pkg -> PackageNamepackageName pkgid :: PackageIdpkgid) pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames of
    Nothing     -> original :: PackageIndexoriginal
    Just pvers  -> case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup (packageVersion :: Package pkg => pkg -> VersionpackageVersion pkgid :: PackageIdpkgid) pvers :: Map Version [InstalledPackageInfo]pvers of
      Nothing   -> original :: PackageIndexoriginal
      Just pkgs -> mkPackageIndex ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexmkPackageIndex
                     (foldl' :: (a -> b -> a) -> a -> [b] -> afoldl' (flip :: (a -> b -> c) -> b -> a -> cflip (delete :: Ord k => k -> Map k a -> Map k aMap.delete (.) :: (b -> c) -> (a -> b) -> a -> c. installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId)) pids :: Map InstalledPackageId InstalledPackageInfopids pkgs :: [InstalledPackageInfo]pkgs)
                     (deletePkgName ::
  Map PackageName (Map Version a) -> Map PackageName (Map Version a)deletePkgName pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames)
  where
    deletePkgName =
      update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k aMap.update deletePkgVersion :: Map Version a -> Maybe (Map Version a)deletePkgVersion (packageName :: Package pkg => pkg -> PackageNamepackageName pkgid :: PackageIdpkgid)

    deletePkgVersion =
        (\m -> if null :: Map k a -> BoolMap.null m :: Map Version am then Nothing :: Maybe aNothing else Just :: a -> Maybe aJust m :: Map Version am)
      (.) :: (b -> c) -> (a -> b) -> a -> c. delete :: Ord k => k -> Map k a -> Map k aMap.delete (packageVersion :: Package pkg => pkg -> VersionpackageVersion pkgid :: PackageIdpkgid)


-- | Removes all packages with this (case-sensitive) name from the index.
--
deletePackageName :: PackageName -> PackageIndex -> PackageIndex
deletePackageName name original@(PackageIndex pids pnames) =
  case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup name :: PackageNamename pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames of
    Nothing     -> original :: PackageIndexoriginal
    Just pvers  -> mkPackageIndex ::
  Map InstalledPackageId InstalledPackageInfo
  -> Map PackageName (Map Version [InstalledPackageInfo])
  -> PackageIndexmkPackageIndex
                     (foldl' :: (a -> b -> a) -> a -> [b] -> afoldl' (flip :: (a -> b -> c) -> b -> a -> cflip (delete :: Ord k => k -> Map k a -> Map k aMap.delete (.) :: (b -> c) -> (a -> b) -> a -> c. installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId)) pids :: Map InstalledPackageId InstalledPackageInfopids
                             (concat :: [[a]] -> [a]concat (elems :: Map k a -> [a]Map.elems pvers :: Map Version [InstalledPackageInfo]pvers)))
                     (delete :: Ord k => k -> Map k a -> Map k aMap.delete name :: PackageNamename pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames)

{-
-- | Removes all packages satisfying this dependency from the index.
--
deleteDependency :: Dependency -> PackageIndex -> PackageIndex
deleteDependency (Dependency name verstionRange) =
  delete' name (\pkg -> packageVersion pkg `withinRange` verstionRange)
-}

--
-- * Bulk queries
--

-- | Get all the packages from the index.
--
allPackages :: PackageIndex -> [InstalledPackageInfo]
allPackages (PackageIndex pids _) = elems :: Map k a -> [a]Map.elems pids :: Map InstalledPackageId InstalledPackageInfopids

-- | Get all the packages from the index.
--
-- They are grouped by package name, case-sensitively.
--
allPackagesByName :: PackageIndex -> [[InstalledPackageInfo]]
allPackagesByName (PackageIndex _ pnames) =
  concatMap :: (a -> [b]) -> [a] -> [b]concatMap elems :: Map k a -> [a]Map.elems (elems :: Map k a -> [a]Map.elems pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames)

--
-- * Lookups
--

-- | Does a lookup by source package id (name & version).
--
-- Since multiple package DBs mask each other by 'InstalledPackageId',
-- then we get back at most one package.
--
lookupInstalledPackageId :: PackageIndex -> InstalledPackageId
                         -> Maybe InstalledPackageInfo
lookupInstalledPackageId (PackageIndex pids _) pid = lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup pid :: PackageIdpid pids :: Map InstalledPackageId InstalledPackageInfopids


-- | Does a lookup by source package id (name & version).
--
-- There can be multiple installed packages with the same source 'PackageId'
-- but different 'InstalledPackageId'. They are returned in order of
-- preference, with the most preferred first.
--
lookupSourcePackageId :: PackageIndex -> PackageId -> [InstalledPackageInfo]
lookupSourcePackageId (PackageIndex _ pnames) pkgid =
  case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup (packageName :: Package pkg => pkg -> PackageNamepackageName pkgid :: PackageIdpkgid) pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames of
    Nothing     -> [] :: [a][]
    Just pvers  -> case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup (packageVersion :: Package pkg => pkg -> VersionpackageVersion pkgid :: PackageIdpkgid) pvers :: Map Version [InstalledPackageInfo]pvers of
      Nothing   -> [] :: [a][]
      Just pkgs -> pkgs :: [InstalledPackageInfo]pkgs -- in preference order


-- | Does a lookup by source package name.
--
lookupPackageName :: PackageIndex -> PackageName
                  -> [(Version, [InstalledPackageInfo])]
lookupPackageName (PackageIndex _ pnames) name =
  case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup name :: PackageNamename pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames of
    Nothing     -> [] :: [a][]
    Just pvers  -> toList :: Map k a -> [(k, a)]Map.toList pvers :: Map Version [InstalledPackageInfo]pvers


-- | 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.
--
lookupDependency :: PackageIndex -> Dependency
                 -> [(Version, [InstalledPackageInfo])]
lookupDependency (PackageIndex _ pnames) (Dependency name versionRange) =
  case lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup name :: PackageNamename pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames of
    Nothing    -> [] :: [a][]
    Just pvers -> [ entry :: (Version, [InstalledPackageInfo])entry
                  | entry@(ver, _) <- toList :: Map k a -> [(k, a)]Map.toList pvers :: Map Version [InstalledPackageInfo]pvers
                  , ver :: Versionver withinRange :: Version -> VersionRange -> Bool`withinRange` versionRange :: VersionRangeversionRange ]

--
-- * Case insensitive name lookups
--

-- | Does a case-insensitive search by package name.
--
-- If there is only one package that compares case-insentiviely to this name
-- then the search is unambiguous and we get back all versions of that package.
-- If several match case-insentiviely but one matches exactly then it is also
-- unambiguous.
--
-- If however several match case-insentiviely and none match exactly then we
-- 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.
--
searchByName :: PackageIndex -> String -> SearchResult [InstalledPackageInfo]
searchByName (PackageIndex _ pnames) name =
  case [ pkgs :: [InstalledPackageInfo]pkgs | pkgs@(PackageName name',_) <- toList :: Map k a -> [(k, a)]Map.toList pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames
              , lowercase :: String -> Stringlowercase name' :: Stringname' (==) :: Eq a => a -> a -> Bool== lname :: Stringlname ] of
    []               -> None :: SearchResult aNone
    [(_,pvers)]      -> Unambiguous :: a -> SearchResult aUnambiguous (concat :: [[a]] -> [a]concat (elems :: Map k a -> [a]Map.elems pvers :: Map Version [InstalledPackageInfo]pvers))
    pkgss            -> case find :: (a -> Bool) -> [a] -> Maybe afind ((PackageName :: String -> PackageNamePackageName name :: PackageNamename(==) :: Eq a => a -> a -> Bool==) (.) :: (b -> c) -> (a -> b) -> a -> c. fst :: (a, b) -> afst) pkgss :: [(PackageName, Map Version [InstalledPackageInfo])]pkgss of
      Just (_,pvers) -> Unambiguous :: a -> SearchResult aUnambiguous (concat :: [[a]] -> [a]concat (elems :: Map k a -> [a]Map.elems pvers :: Map Version [InstalledPackageInfo]pvers))
      Nothing        -> Ambiguous :: [a] -> SearchResult aAmbiguous (map :: (a -> b) -> [a] -> [b]map (concat :: [[a]] -> [a]concat (.) :: (b -> c) -> (a -> b) -> a -> c. elems :: Map k a -> [a]Map.elems (.) :: (b -> c) -> (a -> b) -> a -> c. snd :: (a, b) -> bsnd) pkgss :: [(PackageName, Map Version [InstalledPackageInfo])]pkgss)
  where lname = lowercase :: String -> Stringlowercase name :: PackageNamename

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.
--
searchByNameSubstring :: PackageIndex -> String -> [InstalledPackageInfo]
searchByNameSubstring (PackageIndex _ pnames) searchterm =
  [ pkg :: InstalledPackageInfo_ mpkg
  | (PackageName name, pvers) <- toList :: Map k a -> [(k, a)]Map.toList pnames :: Map PackageName (Map Version [InstalledPackageInfo])pnames
  , lsearchterm :: Stringlsearchterm isInfixOf :: Eq a => [a] -> [a] -> Bool`isInfixOf` lowercase :: String -> Stringlowercase name :: PackageNamename
  , pkgs <- elems :: Map k a -> [a]Map.elems pvers :: Map Version [InstalledPackageInfo]pvers
  , pkg <- pkgs :: [InstalledPackageInfo]pkgs ]
  where lsearchterm = lowercase :: String -> Stringlowercase searchterm :: Stringsearchterm


--
-- * Special queries
--

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

-- | 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.
--
dependencyCycles :: PackageIndex -> [[InstalledPackageInfo]]
dependencyCycles index =
  [ vs :: [InstalledPackageInfo]vs | Graph.CyclicSCC vs <- stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]Graph.stronglyConnComp adjacencyList ::
  [(InstalledPackageInfo, InstalledPackageId, [InstalledPackageId])]adjacencyList ]
  where
    adjacencyList = [ (pkg :: InstalledPackageInfo_ mpkg, installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pkg :: InstalledPackageInfo_ mpkg, depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends pkg :: InstalledPackageInfo_ mpkg)
                    | pkg <- allPackages :: PackageIndex -> [InstalledPackageInfo]allPackages index :: PackageIndexindex ]


-- | All packages that have immediate dependencies that are not in the index.
--
-- Returns such packages along with the dependencies that they're missing.
--
brokenPackages :: PackageIndex -> [(InstalledPackageInfo, [InstalledPackageId])]
brokenPackages index =
  [ (pkg :: InstalledPackageInfo_ mpkg, missing :: [InstalledPackageId]missing)
  | pkg  <- allPackages :: PackageIndex -> [InstalledPackageInfo]allPackages index :: PackageIndexindex
  , let missing = [ pkg' :: InstalledPackageIdpkg' | pkg' <- depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends pkg :: InstalledPackageInfo_ mpkg
                         , isNothing :: Maybe a -> BoolisNothing (lookupInstalledPackageId ::
  PackageIndex -> InstalledPackageId -> Maybe InstalledPackageInfolookupInstalledPackageId index :: PackageIndexindex pkg' :: InstalledPackageIdpkg') ]
  , not :: Bool -> Boolnot (null :: [a] -> Boolnull missing :: [InstalledPackageId]missing) ]


-- | Tries to take the transitive closure of the package dependencies.
--
-- If the transitive closure is complete then it returns that subset of the
-- index. Otherwise it returns the broken packages as in 'brokenPackages'.
--
-- * Note that if the result is @Right []@ it is because at least one of
-- the original given 'PackageId's do not occur in the index.
--
dependencyClosure :: PackageIndex
                  -> [InstalledPackageId]
                  -> Either PackageIndex
                            [(InstalledPackageInfo, [InstalledPackageId])]
dependencyClosure index pkgids0 = case closure ::
  PackageIndex
  -> [InstalledPackageId]
  -> [InstalledPackageId]
  -> (PackageIndex, [InstalledPackageId])closure mempty :: Monoid a => amempty [] :: [a][] pkgids0 :: [InstalledPackageId]pkgids0 of
  (completed, []) -> Left :: a -> Either a bLeft completed :: PackageIndexcompleted
  (completed, _)  -> Right :: b -> Either a bRight (brokenPackages ::
  PackageIndex -> [(InstalledPackageInfo, [InstalledPackageId])]brokenPackages completed :: PackageIndexcompleted)
 where
    closure completed failed []             = (completed :: PackageIndexcompleted, failed :: [InstalledPackageId]failed)
    closure completed failed (pkgid:pkgids) = case lookupInstalledPackageId ::
  PackageIndex -> InstalledPackageId -> Maybe InstalledPackageInfolookupInstalledPackageId index :: PackageIndexindex pkgid :: PackageIdpkgid of
      Nothing   -> closure ::
  PackageIndex
  -> [InstalledPackageId]
  -> [InstalledPackageId]
  -> (PackageIndex, [InstalledPackageId])closure completed :: PackageIndexcompleted (pkgid :: PackageIdpkgid(:) :: a -> [a] -> [a]:failed :: [InstalledPackageId]failed) pkgids :: [InstalledPackageId]pkgids
      Just pkg  -> case lookupInstalledPackageId ::
  PackageIndex -> InstalledPackageId -> Maybe InstalledPackageInfolookupInstalledPackageId completed :: PackageIndexcompleted (installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pkg :: InstalledPackageInfo_ mpkg) of
        Just _  -> closure ::
  PackageIndex
  -> [InstalledPackageId]
  -> [InstalledPackageId]
  -> (PackageIndex, [InstalledPackageId])closure completed :: PackageIndexcompleted  failed :: [InstalledPackageId]failed pkgids :: [InstalledPackageId]pkgids
        Nothing -> closure ::
  PackageIndex
  -> [InstalledPackageId]
  -> [InstalledPackageId]
  -> (PackageIndex, [InstalledPackageId])closure completed' :: PackageIndexcompleted' failed :: [InstalledPackageId]failed pkgids' :: [InstalledPackageId]pkgids'
          where completed' = insert :: InstalledPackageInfo -> PackageIndex -> PackageIndexinsert pkg :: InstalledPackageInfo_ mpkg completed :: PackageIndexcompleted
                pkgids'    = depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends pkg :: InstalledPackageInfo_ mpkg (++) :: [a] -> [a] -> [a]++ pkgids :: [InstalledPackageId]pkgids

-- | Takes the transitive closure of the packages reverse dependencies.
--
-- * The given 'PackageId's must be in the index.
--
reverseDependencyClosure :: PackageIndex
                         -> [InstalledPackageId]
                         -> [InstalledPackageInfo]
reverseDependencyClosure index =
    map :: (a -> b) -> [a] -> [b]map vertexToPkg :: Vertex -> InstalledPackageInfovertexToPkg
  (.) :: (b -> c) -> (a -> b) -> a -> c. concatMap :: (a -> [b]) -> [a] -> [b]concatMap flatten :: Tree a -> [a]Tree.flatten
  (.) :: (b -> c) -> (a -> b) -> a -> c. dfs :: Graph -> [Vertex] -> Forest VertexGraph.dfs reverseDepGraph :: GraphreverseDepGraph
  (.) :: (b -> c) -> (a -> b) -> a -> c. map :: (a -> b) -> [a] -> [b]map (fromMaybe :: a -> Maybe a -> afromMaybe noSuchPkgId :: tnoSuchPkgId (.) :: (b -> c) -> (a -> b) -> a -> c. pkgIdToVertex :: InstalledPackageId -> Maybe VertexpkgIdToVertex)

  where
    (depGraph, vertexToPkg, pkgIdToVertex) = dependencyGraph ::
  PackageIndex
  -> (Graph,
      Vertex -> InstalledPackageInfo,
      InstalledPackageId -> Maybe Vertex)dependencyGraph index :: PackageIndexindex
    reverseDepGraph = transposeG :: Graph -> GraphGraph.transposeG depGraph :: GraphdepGraph
    noSuchPkgId = error :: [Char] -> aerror "reverseDependencyClosure: package is not in the graph"

topologicalOrder :: PackageIndex -> [InstalledPackageInfo]
topologicalOrder index = map :: (a -> b) -> [a] -> [b]map toPkgId :: Vertex -> InstalledPackageInfotoPkgId
                       (.) :: (b -> c) -> (a -> b) -> a -> c. topSort :: Graph -> [Vertex]Graph.topSort
                       ($) :: (a -> b) -> a -> b$ graph :: Graphgraph
  where (graph, toPkgId, _) = dependencyGraph ::
  PackageIndex
  -> (Graph,
      Vertex -> InstalledPackageInfo,
      InstalledPackageId -> Maybe Vertex)dependencyGraph index :: PackageIndexindex

reverseTopologicalOrder :: PackageIndex -> [InstalledPackageInfo]
reverseTopologicalOrder index = map :: (a -> b) -> [a] -> [b]map toPkgId :: Vertex -> InstalledPackageInfotoPkgId
                              (.) :: (b -> c) -> (a -> b) -> a -> c. topSort :: Graph -> [Vertex]Graph.topSort
                              (.) :: (b -> c) -> (a -> b) -> a -> c. transposeG :: Graph -> GraphGraph.transposeG
                              ($) :: (a -> b) -> a -> b$ graph :: Graphgraph
  where (graph, toPkgId, _) = dependencyGraph ::
  PackageIndex
  -> (Graph,
      Vertex -> InstalledPackageInfo,
      InstalledPackageId -> Maybe Vertex)dependencyGraph index :: PackageIndexindex

-- | 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'.
--
dependencyGraph :: PackageIndex
                -> (Graph.Graph,
                    Graph.Vertex -> InstalledPackageInfo,
                    InstalledPackageId -> Maybe Graph.Vertex)
dependencyGraph index = (graph :: Graphgraph, vertex_to_pkg :: Int -> InstalledPackageInfovertex_to_pkg, id_to_vertex :: InstalledPackageId -> Maybe Vertexid_to_vertex)
  where
    graph = listArray :: Ix i => (i, i) -> [e] -> Array i eArray.listArray bounds :: (Int, Int)bounds
              [ [ v :: Vertexv | Just v <- map :: (a -> b) -> [a] -> [b]map id_to_vertex :: InstalledPackageId -> Maybe Vertexid_to_vertex (depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends pkg :: InstalledPackageInfo_ mpkg) ]
              | pkg <- pkgs :: [InstalledPackageInfo]pkgs ]

    pkgs             = sortBy :: (a -> a -> Ordering) -> [a] -> [a]sortBy (comparing :: Ord a => (b -> a) -> b -> b -> Orderingcomparing packageId :: Package pkg => pkg -> PackageIdentifierpackageId) (allPackages :: PackageIndex -> [InstalledPackageInfo]allPackages index :: PackageIndexindex)
    vertices         = zip :: [a] -> [b] -> [(a, b)]zip (map :: (a -> b) -> [a] -> [b]map installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId pkgs :: [InstalledPackageInfo]pkgs) [0..]
    vertex_map       = fromList :: Ord k => [(k, a)] -> Map k aMap.fromList vertices :: [(InstalledPackageId, Vertex)]vertices
    id_to_vertex pid = lookup :: Ord k => k -> Map k a -> Maybe aMap.lookup pid :: PackageIdpid vertex_map :: Map InstalledPackageId Vertexvertex_map

    vertex_to_pkg vertex = pkgTable :: Array Int InstalledPackageInfopkgTable (!) :: Ix i => Array i e -> i -> e! vertex :: Intvertex

    pkgTable   = listArray :: Ix i => (i, i) -> [e] -> Array i eArray.listArray bounds :: (Int, Int)bounds pkgs :: [InstalledPackageInfo]pkgs
    topBound = length :: [a] -> Intlength pkgs :: [InstalledPackageInfo]pkgs (-) :: Num a => a -> a -> a- 1
    bounds = (0, topBound :: InttopBound)

-- | 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.
--
dependencyInconsistencies :: PackageIndex
                          -> [(PackageName, [(PackageId, Version)])]
dependencyInconsistencies index =
  [ (name :: PackageNamename, [ (pid :: PackageIdpid,packageVersion :: Package pkg => pkg -> VersionpackageVersion dep :: InstalledPackageInfodep) | (dep,pids) <- uses :: [(InstalledPackageInfo, [PackageId])]uses, pid <- pids :: Map InstalledPackageId InstalledPackageInfopids])
  | (name, ipid_map) <- toList :: Map k a -> [(k, a)]Map.toList inverseIndex ::
  Map
    PackageName
    (Map InstalledPackageId (InstalledPackageInfo, [PackageId]))inverseIndex
  , let uses = elems :: Map k a -> [a]Map.elems ipid_map ::
  Map InstalledPackageId (InstalledPackageInfo, [PackageId])ipid_map
  , reallyIsInconsistent :: [InstalledPackageInfo] -> BoolreallyIsInconsistent (map :: (a -> b) -> [a] -> [b]map fst :: (a, b) -> afst uses :: [(InstalledPackageInfo, [PackageId])]uses) ]

  where -- for each PackageName,
        --   for each package with that name,
        --     the InstalledPackageInfo and the package Ids of packages
        --     that depend on it.
        inverseIndex :: Map PackageName
                            (Map InstalledPackageId
                                 (InstalledPackageInfo, [PackageId]))
        inverseIndex = fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k aMap.fromListWith (unionWith ::
  Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k aMap.unionWith (\(a,b) (_,b') -> (a :: Inta,b :: [PackageId]b(++) :: [a] -> [a] -> [a]++b' :: [PackageId]b')))
          [ (packageName :: Package pkg => pkg -> PackageNamepackageName dep :: InstalledPackageInfodep,
             fromList :: Ord k => [(k, a)] -> Map k aMap.fromList [(ipid :: InstalledPackageIdipid,(dep :: InstalledPackageInfodep,[packageId :: Package pkg => pkg -> PackageIdentifierpackageId pkg :: InstalledPackageInfo_ mpkg]))])
          | pkg <- allPackages :: PackageIndex -> [InstalledPackageInfo]allPackages index :: PackageIndexindex
          , ipid <- depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends pkg :: InstalledPackageInfo_ mpkg
          , Just dep <- [lookupInstalledPackageId ::
  PackageIndex -> InstalledPackageId -> Maybe InstalledPackageInfolookupInstalledPackageId index :: PackageIndexindex ipid :: InstalledPackageIdipid]
          ]

        reallyIsInconsistent :: [InstalledPackageInfo] -> Bool
        reallyIsInconsistent []       = False :: BoolFalse
        reallyIsInconsistent [_p]     = False :: BoolFalse
        reallyIsInconsistent [p1, p2] =
             installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId p1 :: InstalledPackageInfop1 notElem :: Eq a => a -> [a] -> Bool`notElem` depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends p2 :: InstalledPackageInfop2
          (&&) :: Bool -> Bool -> Bool&& installedPackageId :: InstalledPackageInfo_ m -> InstalledPackageIdinstalledPackageId p2 :: InstalledPackageInfop2 notElem :: Eq a => a -> [a] -> Bool`notElem` depends :: InstalledPackageInfo_ m -> [InstalledPackageId]IPI.depends p1 :: InstalledPackageInfop1
        reallyIsInconsistent _ = True :: BoolTrue


moduleNameIndex :: PackageIndex -> Map ModuleName [InstalledPackageInfo]
moduleNameIndex index =
  fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k aMap.fromListWith (++) :: [a] -> [a] -> [a](++)
    [ (moduleName :: ModuleNamemoduleName, [pkg :: InstalledPackageInfo_ mpkg])
    | pkg        <- allPackages :: PackageIndex -> [InstalledPackageInfo]allPackages index :: PackageIndexindex
    , moduleName <- exposedModules :: InstalledPackageInfo_ m -> [m]IPI.exposedModules pkg :: InstalledPackageInfo_ mpkg ]