IndexConversion.hs 24 KB
Newer Older
1
module Distribution.Solver.Modular.IndexConversion
2 3
    ( convPIs
    ) where
4 5

import Data.List as L
6 7
import Distribution.Compat.Map.Strict (Map)
import qualified Distribution.Compat.Map.Strict as M
Andres Löh's avatar
Andres Löh committed
8
import Data.Maybe
9
import Data.Monoid as Mon
10
import Data.Set as S
11 12 13 14

import Distribution.Compiler
import Distribution.InstalledPackageInfo as IPI
import Distribution.Package                          -- from Cabal
15
import Distribution.Simple.BuildToolDepends          -- from Cabal
16
import Distribution.Simple.Utils (cabalVersion)      -- from Cabal
17
import Distribution.Types.ExeDependency              -- from Cabal
18
import Distribution.Types.PkgconfigDependency        -- from Cabal
19
import Distribution.Types.ComponentName              -- from Cabal
20
import Distribution.Types.UnqualComponentName        -- from Cabal
21
import Distribution.Types.CondTree                   -- from Cabal
22 23
import Distribution.Types.MungedPackageId            -- from Cabal
import Distribution.Types.MungedPackageName          -- from Cabal
24
import Distribution.PackageDescription as PD         -- from Cabal
25
import Distribution.PackageDescription.Configuration as PDC
26 27
import qualified Distribution.Simple.PackageIndex as SI
import Distribution.System
28
import Distribution.Types.ForeignLib
29

30 31
import           Distribution.Solver.Types.ComponentDeps
                   ( Component(..), componentNameToComponent )
32
import           Distribution.Solver.Types.Flag
33 34 35 36 37 38 39 40 41 42 43
import           Distribution.Solver.Types.OptionalStanza
import qualified Distribution.Solver.Types.PackageIndex as CI
import           Distribution.Solver.Types.Settings
import           Distribution.Solver.Types.SourcePackage

import Distribution.Solver.Modular.Dependency as D
import Distribution.Solver.Modular.Flag as F
import Distribution.Solver.Modular.Index
import Distribution.Solver.Modular.Package
import Distribution.Solver.Modular.Tree
import Distribution.Solver.Modular.Version
44 45 46

-- | Convert both the installed package index and the source package
-- index into one uniform solver index.
47
--
48 49 50
-- We use 'allPackagesBySourcePackageId' for the installed package index
-- because that returns us several instances of the same package and version
-- in order of preference. This allows us in principle to \"shadow\"
51 52 53
-- packages if there are several installed packages of the same version.
-- There are currently some shortcomings in both GHC and Cabal in
-- resolving these situations. However, the right thing to do is to
54 55
-- fix the problem there, so for now, shadowing is only activated if
-- explicitly requested.
56
convPIs :: OS -> Arch -> CompilerInfo -> ShadowPkgs -> StrongFlags -> SolveExecutables ->
57
           SI.InstalledPackageIndex -> CI.PackageIndex (SourcePackage loc) -> Index
kristenk's avatar
kristenk committed
58 59
convPIs os arch comp sip strfl solveExes iidx sidx =
  mkIndex (convIPI' sip iidx ++ convSPI' os arch comp strfl solveExes sidx)
60 61 62

-- | Convert a Cabal installed package index to the simpler,
-- more uniform index format of the solver.
63 64
convIPI' :: ShadowPkgs -> SI.InstalledPackageIndex -> [(PN, I, PInfo)]
convIPI' (ShadowPkgs sip) idx =
Ian D. Bollinger's avatar
Ian D. Bollinger committed
65
    -- apply shadowing whenever there are multiple installed packages with
66
    -- the same version
67
    [ maybeShadow (convIP idx pkg)
68 69 70
    -- IMPORTANT to get internal libraries. See
    -- Note [Index conversion with internal libraries]
    | (_, pkgs) <- SI.allPackagesBySourcePackageIdAndLibName idx
71 72 73
    , (maybeShadow, pkg) <- zip (id : repeat shadow) pkgs ]
  where

74
    -- shadowing is recorded in the package info
75 76
    shadow (pn, i, PInfo fdeps comps fds _)
      | sip = (pn, i, PInfo fdeps comps fds (Just Shadowed))
77
    shadow x                                     = x
78

79 80 81
-- | Extract/recover the the package ID from an installed package info, and convert it to a solver's I.
convId :: InstalledPackageInfo -> (PN, I)
convId ipi = (pn, I ver $ Inst $ IPI.installedUnitId ipi)
82 83 84
  where MungedPackageId mpn ver = mungedId ipi
        -- HACK. See Note [Index conversion with internal libraries]
        pn = mkPackageName (unMungedPackageName mpn)
85

86
-- | Convert a single installed package into the solver-specific format.
87
convIP :: SI.InstalledPackageIndex -> InstalledPackageInfo -> (PN, I, PInfo)
88
convIP idx ipi =
89
  case mapM (convIPId (DependencyReason pn M.empty S.empty) comp idx) (IPI.depends ipi) of
90
        Nothing  -> (pn, i, PInfo [] [] M.empty (Just Broken))
91
        Just fds -> (pn, i, PInfo fds [ExposedLib] M.empty Nothing)
92
 where
93 94 95
  (pn, i) = convId ipi
  -- 'sourceLibName' is unreliable, but for now we only really use this for
  -- primary libs anyways
kristenk's avatar
kristenk committed
96
  comp = componentNameToComponent $ libraryComponentName $ sourceLibName ipi
97 98
-- TODO: Installed packages should also store their encapsulations!

99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
-- Note [Index conversion with internal libraries]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Something very interesting happens when we have internal libraries
-- in our index.  In this case, we maybe have p-0.1, which itself
-- depends on the internal library p-internal ALSO from p-0.1.
-- Here's the danger:
--
--      - If we treat both of these packages as having PN "p",
--        then the solver will try to pick one or the other,
--        but never both.
--
--      - If we drop the internal packages, now p-0.1 has a
--        dangling dependency on an "installed" package we know
--        nothing about. Oops.
--
-- An expedient hack is to put p-internal into cabal-install's
-- index as a MUNGED package name, so that it doesn't conflict
-- with anyone else (except other instances of itself).  But
-- yet, we ought NOT to say that PNs in the solver are munged
-- package names, because they're not; for source packages,
Edward Z. Yang's avatar
Edward Z. Yang committed
119
-- we really will never see munged package names.
120 121 122 123 124 125
--
-- The tension here is that the installed package index is actually
-- per library, but the solver is per package.  We need to smooth
-- it over, and munging the package names is a pretty good way to
-- do it.

126 127
-- | Convert dependencies specified by an installed package id into
-- flagged dependencies of the solver.
Andres Löh's avatar
Andres Löh committed
128 129 130 131
--
-- May return Nothing if the package can't be found in the index. That
-- indicates that the original package having this dependency is broken
-- and should be ignored.
132 133
convIPId :: DependencyReason PN -> Component -> SI.InstalledPackageIndex -> UnitId -> Maybe (FlaggedDep PN)
convIPId dr comp idx ipid =
134
  case SI.lookupUnitId idx ipid of
Andres Löh's avatar
Andres Löh committed
135
    Nothing  -> Nothing
136
    Just ipi -> let (pn, i) = convId ipi
137
                in  Just (D.Simple (LDep dr (Dep (PkgComponent pn ExposedLib) (Fixed i))) comp)
138 139
                -- NB: something we pick up from the
                -- InstalledPackageIndex is NEVER an executable
140 141 142

-- | Convert a cabal-install source package index to the simpler,
-- more uniform index format of the solver.
143
convSPI' :: OS -> Arch -> CompilerInfo -> StrongFlags -> SolveExecutables ->
144
            CI.PackageIndex (SourcePackage loc) -> [(PN, I, PInfo)]
kristenk's avatar
kristenk committed
145
convSPI' os arch cinfo strfl solveExes = L.map (convSP os arch cinfo strfl solveExes) . CI.allPackages
146

147
-- | Convert a single source package into the solver-specific format.
148
convSP :: OS -> Arch -> CompilerInfo -> StrongFlags -> SolveExecutables -> SourcePackage loc -> (PN, I, PInfo)
kristenk's avatar
kristenk committed
149
convSP os arch cinfo strfl solveExes (SourcePackage (PackageIdentifier pn pv) gpd _ _pl) =
150
  let i = I pv InRepo
151
  in  (pn, i, convGPD os arch cinfo strfl solveExes pn gpd)
152

153
-- We do not use 'flattenPackageDescription' or 'finalizePD'
154 155 156 157
-- from 'Distribution.PackageDescription.Configuration' here, because we
-- want to keep the condition tree, but simplify much of the test.

-- | Convert a generic package description to a solver-specific 'PInfo'.
158
convGPD :: OS -> Arch -> CompilerInfo -> StrongFlags -> SolveExecutables ->
159 160
           PN -> GenericPackageDescription -> PInfo
convGPD os arch cinfo strfl solveExes pn
161
        (GenericPackageDescription pkg flags mlib sub_libs flibs exes tests benchs) =
162
  let
163
    fds  = flagInfo strfl flags
164

165 166 167 168 169
    -- | We have to be careful to filter out dependencies on
    -- internal libraries, since they don't refer to real packages
    -- and thus cannot actually be solved over.  We'll do this
    -- by creating a set of package names which are "internal"
    -- and dropping them as we convert.
170 171

    ipns = S.fromList $ [ unqualComponentNameToPackageName nm
kristenk's avatar
kristenk committed
172
                        | (nm, _) <- sub_libs ]
173

174
    conv :: Mon.Monoid a => Component -> (a -> BuildInfo) -> DependencyReason PN ->
kristenk's avatar
kristenk committed
175
            CondTree ConfVar [Dependency] a -> FlaggedDeps PN
176
    conv comp getInfo dr =
177
        convCondTree M.empty dr pkg os arch cinfo pn fds comp getInfo ipns solveExes .
178 179
        PDC.addBuildableCondition getInfo

180
    initDR = DependencyReason pn M.empty S.empty
181 182

    flagged_deps
183 184 185 186
        = concatMap (\ds ->       conv ComponentLib         libBuildInfo        initDR ds) (maybeToList mlib)
       ++ concatMap (\(nm, ds) -> conv (ComponentSubLib nm) libBuildInfo        initDR ds) sub_libs
       ++ concatMap (\(nm, ds) -> conv (ComponentFLib nm)   foreignLibBuildInfo initDR ds) flibs
       ++ concatMap (\(nm, ds) -> conv (ComponentExe nm)    buildInfo           initDR ds) exes
187
       ++ prefix (Stanza (SN pn TestStanzas))
188 189
            (L.map  (\(nm, ds) -> conv (ComponentTest nm)   testBuildInfo (addStanza TestStanzas initDR) ds)
                    tests)
190
       ++ prefix (Stanza (SN pn BenchStanzas))
191 192
            (L.map  (\(nm, ds) -> conv (ComponentBench nm)  benchmarkBuildInfo (addStanza BenchStanzas initDR) ds)
                    benchs)
193
       ++ maybe []  (convSetupBuildInfo pn) (setupBuildInfo pkg)
194

195
    addStanza :: Stanza -> DependencyReason pn -> DependencyReason pn
196
    addStanza s (DependencyReason pn' fs ss) = DependencyReason pn' fs (S.insert s ss)
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225

    -- | We infer the maximally supported spec-version from @lib:Cabal@'s version
    --
    -- As we cannot predict the future, we can only properly support
    -- spec-versions predating (and including) the @lib:Cabal@ version
    -- used by @cabal-install@.
    --
    -- This relies on 'cabalVersion' having always at least 3 components to avoid
    -- comparisons like @2.0.0 > 2.0@ which would result in confusing results.
    --
    -- NOTE: Before we can switch to a /normalised/ spec-version
    -- comparison (e.g. by truncating to 3 components, and removing
    -- trailing zeroes) we'd have to make sure all other places where
    -- the spec-version is compared against a bound do it
    -- consistently.
    maxSpecVer = cabalVersion

    -- | Required/declared spec-version of the package
    --
    -- We don't truncate patch-levels, as specifying a patch-level
    -- spec-version is discouraged and not supported anymore starting
    -- with spec-version 2.2.
    reqSpecVer = specVersion pkg

    -- | A too-new specVersion is turned into a global 'FailReason'
    -- which prevents the solver from selecting this release (and if
    -- forced to, emit a meaningful solver error message).
    fr | reqSpecVer > maxSpecVer = Just (UnsupportedSpecVer reqSpecVer)
       | otherwise               = Nothing
226
  in
227
    PInfo flagged_deps (L.map (ExposedExe . fst) exes ++ [ExposedLib | isJust mlib]) fds fr
228

229 230 231
-- | Create a flagged dependency tree from a list @fds@ of flagged
-- dependencies, using @f@ to form the tree node (@f@ will be
-- something like @Stanza sn@).
kristenk's avatar
kristenk committed
232 233
prefix :: (FlaggedDeps qpn -> FlaggedDep qpn)
       -> [FlaggedDeps qpn] -> FlaggedDeps qpn
Andres Löh's avatar
Andres Löh committed
234
prefix _ []  = []
235
prefix f fds = [f (concat fds)]
Andres Löh's avatar
Andres Löh committed
236

Andres Löh's avatar
Andres Löh committed
237 238
-- | Convert flag information. Automatic flags are now considered weak
-- unless strong flags have been selected explicitly.
239 240
flagInfo :: StrongFlags -> [PD.Flag] -> FlagInfo
flagInfo (StrongFlags strfl) =
241
    M.fromList . L.map (\ (MkFlag fn _ b m) -> (fn, FInfo b (flagType m) (weak m)))
242 243
  where
    weak m = WeakOrTrivial $ not (strfl || m)
244
    flagType m = if m then Manual else Automatic
245

246 247 248 249
-- | Internal package names, which should not be interpreted as true
-- dependencies.
type IPNs = Set PN

250
-- | Convenience function to delete a 'Dependency' if it's
251
-- for a 'PN' that isn't actually real.
252 253 254 255
filterIPNs :: IPNs -> Dependency -> Maybe Dependency
filterIPNs ipns d@(Dependency pn _)
    | S.notMember pn ipns = Just d
    | otherwise           = Nothing
256

257 258 259
-- | Convert condition trees to flagged dependencies.  Mutually
-- recursive with 'convBranch'.  See 'convBranch' for an explanation
-- of all arguments preceeding the input 'CondTree'.
260
convCondTree :: Map FlagName Bool -> DependencyReason PN -> PackageDescription -> OS -> Arch -> CompilerInfo -> PN -> FlagInfo ->
261
                Component ->
262
                (a -> BuildInfo) ->
263
                IPNs ->
264
                SolveExecutables ->
kristenk's avatar
kristenk committed
265
                CondTree ConfVar [Dependency] a -> FlaggedDeps PN
266
convCondTree flags dr pkg os arch cinfo pn fds comp getInfo ipns solveExes@(SolveExecutables solveExes') (CondNode info ds branches) =
267 268 269 270 271 272
             -- Merge all library and build-tool dependencies at every level in
             -- the tree of flagged dependencies. Otherwise 'extractCommon'
             -- could create duplicate dependencies, and the number of
             -- duplicates could grow exponentially from the leaves to the root
             -- of the tree.
             mergeSimpleDeps $
273
                 L.map (\d -> D.Simple (convLibDep dr d) comp)
274
                       (mapMaybe (filterIPNs ipns) ds)                                -- unconditional package dependencies
275 276 277
              ++ L.map (\e -> D.Simple (LDep dr (Ext  e)) comp) (PD.allExtensions bi) -- unconditional extension dependencies
              ++ L.map (\l -> D.Simple (LDep dr (Lang l)) comp) (PD.allLanguages  bi) -- unconditional language dependencies
              ++ L.map (\(PkgconfigDependency pkn vr) -> D.Simple (LDep dr (Pkg pkn vr)) comp) (PD.pkgconfigDepends bi) -- unconditional pkg-config dependencies
278
              ++ concatMap (convBranch flags dr pkg os arch cinfo pn fds comp getInfo ipns solveExes) branches
279
              -- build-tools dependencies
280 281 282 283
              -- NB: Only include these dependencies if SolveExecutables
              -- is True.  It might be false in the legacy solver
              -- codepath, in which case there won't be any record of
              -- an executable we need.
284
              ++ [ D.Simple (convExeDep dr exeDep) comp
kristenk's avatar
kristenk committed
285
                 | solveExes'
286 287
                 , exeDep <- getAllToolDependencies pkg bi
                 , not $ isInternal pkg exeDep
288
                 ]
289 290
  where
    bi = getInfo info
291

292
data SimpleFlaggedDepKey qpn =
293
    SimpleFlaggedDepKey (PkgComponent qpn) Component
294 295
  deriving (Eq, Ord)

296 297
data SimpleFlaggedDepValue qpn = SimpleFlaggedDepValue (DependencyReason qpn) VR

298
-- | Merge 'Simple' dependencies that apply to the same library or build-tool.
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
-- This function should be able to merge any two dependencies that can be merged
-- by extractCommon, in order to prevent the exponential growth of dependencies.
--
-- Note that this function can merge dependencies that have different
-- DependencyReasons, which can make the DependencyReasons less precise. This
-- loss of precision only affects performance and log messages, not correctness.
-- However, when 'mergeSimpleDeps' is only called on dependencies at a single
-- location in the dependency tree, the only difference between
-- DependencyReasons should be flags that have value FlagBoth. Adding extra
-- flags with value FlagBoth should not affect performance, since they are not
-- added to the conflict set. The only downside is the possibility of the log
-- incorrectly saying that the flag contributed to excluding a specific version
-- of a dependency. For example, if +/-flagA introduces pkg >=2 and +/-flagB
-- introduces pkg <5, the merged dependency would mean that
-- +/-flagA and +/-flagB introduce pkg >=2 && <5, which would incorrectly imply
-- that +/-flagA excludes pkg-6.
315 316 317 318 319 320
mergeSimpleDeps :: Ord qpn => FlaggedDeps qpn -> FlaggedDeps qpn
mergeSimpleDeps deps = L.map (uncurry toFlaggedDep) (M.toList merged) ++ unmerged
  where
    (merged, unmerged) = L.foldl' f (M.empty, []) deps
      where
        f :: Ord qpn
321
          => (Map (SimpleFlaggedDepKey qpn) (SimpleFlaggedDepValue qpn), FlaggedDeps qpn)
322
          -> FlaggedDep qpn
323
          -> (Map (SimpleFlaggedDepKey qpn) (SimpleFlaggedDepValue qpn), FlaggedDeps qpn)
324
        f (merged', unmerged') (D.Simple (LDep dr (Dep dep (Constrained vr))) comp) =
325
            ( M.insertWith mergeValues
326
                           (SimpleFlaggedDepKey dep comp)
327 328 329
                           (SimpleFlaggedDepValue dr vr)
                           merged'
            , unmerged')
330 331
        f (merged', unmerged') unmergeableDep = (merged', unmergeableDep : unmerged')

332 333 334 335 336 337 338 339 340
        mergeValues :: SimpleFlaggedDepValue qpn
                    -> SimpleFlaggedDepValue qpn
                    -> SimpleFlaggedDepValue qpn
        mergeValues (SimpleFlaggedDepValue dr1 vr1) (SimpleFlaggedDepValue dr2 vr2) =
            SimpleFlaggedDepValue (unionDRs dr1 dr2) (vr1 .&&. vr2)

    toFlaggedDep :: SimpleFlaggedDepKey qpn
                 -> SimpleFlaggedDepValue qpn
                 -> FlaggedDep qpn
341 342
    toFlaggedDep (SimpleFlaggedDepKey dep comp) (SimpleFlaggedDepValue dr vr) =
        D.Simple (LDep dr (Dep dep (Constrained vr))) comp
343

344
-- | Branch interpreter.  Mutually recursive with 'convCondTree'.
345 346 347 348 349 350 351
--
-- Here, we try to simplify one of Cabal's condition tree branches into the
-- solver's flagged dependency format, which is weaker. Condition trees can
-- contain complex logical expression composed from flag choices and special
-- flags (such as architecture, or compiler flavour). We try to evaluate the
-- special flags and subsequently simplify to a tree that only depends on
-- simple flag choices.
352 353 354
--
-- This function takes a number of arguments:
--
355 356 357 358 359 360 361 362 363 364
--      1. A map of flag values that have already been chosen. It allows
--         convBranch to avoid creating nested FlaggedDeps that are
--         controlled by the same flag and avoid creating DependencyReasons with
--         conflicting values for the same flag.
--
--      2. The DependencyReason calculated at this point in the tree of
--         conditionals. The flag values in the DependencyReason are similar to
--         the values in the map above, except for the use of FlagBoth.
--
--      3. Some pre dependency-solving known information ('OS', 'Arch',
365 366
--         'CompilerInfo') for @os()@, @arch()@ and @impl()@ variables,
--
367
--      4. The package name @'PN'@ which this condition tree
368 369 370
--         came from, so that we can correctly associate @flag()@
--         variables with the correct package name qualifier,
--
371
--      5. The flag defaults 'FlagInfo' so that we can populate
372 373
--         'Flagged' dependencies with 'FInfo',
--
374
--      6. The name of the component 'Component' so we can record where
375 376 377
--         the fine-grained information about where the component came
--         from (see 'convCondTree'), and
--
378
--      7. A selector to extract the 'BuildInfo' from the leaves of
379 380
--         the 'CondTree' (which actually contains the needed
--         dependency information.)
381
--
382
--      8. The set of package names which should be considered internal
383
--         dependencies, and thus not handled as dependencies.
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398
convBranch :: Map FlagName Bool
           -> DependencyReason PN
           -> PackageDescription
           -> OS
           -> Arch
           -> CompilerInfo
           -> PN
           -> FlagInfo
           -> Component
           -> (a -> BuildInfo)
           -> IPNs
           -> SolveExecutables
           -> CondBranch ConfVar [Dependency] a
           -> FlaggedDeps PN
convBranch flags dr pkg os arch cinfo pn fds comp getInfo ipns solveExes (CondBranch c' t' mf') =
399
    go c'
400 401 402
       (\flags' dr' ->           convCondTree flags' dr' pkg os arch cinfo pn fds comp getInfo ipns solveExes  t')
       (\flags' dr' -> maybe [] (convCondTree flags' dr' pkg os arch cinfo pn fds comp getInfo ipns solveExes) mf')
       flags dr
403
  where
404
    go :: Condition ConfVar
405 406 407
       -> (Map FlagName Bool -> DependencyReason PN -> FlaggedDeps PN)
       -> (Map FlagName Bool -> DependencyReason PN -> FlaggedDeps PN)
       ->  Map FlagName Bool -> DependencyReason PN -> FlaggedDeps PN
408 409 410 411 412
    go (Lit True)  t _ = t
    go (Lit False) _ f = f
    go (CNot c)    t f = go c f t
    go (CAnd c d)  t f = go c (go d t f) f
    go (COr  c d)  t f = go c t (go d t f)
413 414 415 416 417 418 419 420 421 422 423 424 425 426 427
    go (Var (Flag fn)) t f = \flags' ->
        case M.lookup fn flags' of
          Just True  -> t flags'
          Just False -> f flags'
          Nothing    -> \dr' ->
            -- Add each flag to the DependencyReason for all dependencies below,
            -- including any extracted dependencies. Extracted dependencies are
            -- introduced by both flag values (FlagBoth). Note that we don't
            -- actually need to add the flag to the extracted dependencies for
            -- correct backjumping; the information only improves log messages
            -- by giving the user the full reason for each dependency.
            let addFlagValue v = addFlagToDependencyReason fn v dr'
                addFlag v = M.insert fn v flags'
            in extractCommon (t (addFlag True)  (addFlagValue FlagBoth))
                             (f (addFlag False) (addFlagValue FlagBoth))
428 429
                ++ [ Flagged (FN pn fn) (fds M.! fn) (t (addFlag True)  (addFlagValue FlagTrue))
                                                     (f (addFlag False) (addFlagValue FlagFalse)) ]
430 431 432 433 434 435
    go (Var (OS os')) t f
      | os == os'      = t
      | otherwise      = f
    go (Var (Arch arch')) t f
      | arch == arch'  = t
      | otherwise      = f
436 437 438 439 440 441 442
    go (Var (Impl cf cvr)) t f
      | matchImpl (compilerInfoId cinfo) ||
            -- fixme: Nothing should be treated as unknown, rather than empty
            --        list. This code should eventually be changed to either
            --        support partial resolution of compiler flags or to
            --        complain about incompletely configured compilers.
        any matchImpl (fromMaybe [] $ compilerInfoCompat cinfo) = t
443
      | otherwise      = f
444 445
      where
        matchImpl (CompilerId cf' cv) = cf == cf' && checkVR cvr cv
446

447 448 449
    addFlagToDependencyReason :: FlagName -> FlagValue -> DependencyReason pn -> DependencyReason pn
    addFlagToDependencyReason fn v (DependencyReason pn' fs ss) =
        DependencyReason pn' (M.insert fn v fs) ss
450

451
    -- If both branches contain the same package as a simple dep, we lift it to
452 453 454 455
    -- the next higher-level, but with the union of version ranges. This
    -- heuristic together with deferring flag choices will then usually first
    -- resolve this package, and try an already installed version before imposing
    -- a default flag choice that might not be what we want.
456 457
    --
    -- Note that we make assumptions here on the form of the dependencies that
458 459
    -- can occur at this point. In particular, no occurrences of Fixed, as all
    -- dependencies below this point have been generated using 'convLibDep'.
460 461
    --
    -- WARNING: This is quadratic!
462 463
    extractCommon :: Eq pn => FlaggedDeps pn -> FlaggedDeps pn -> FlaggedDeps pn
    extractCommon ps ps' =
464
        -- Union the DependencyReasons, because the extracted dependency can be
465 466
        -- avoided by removing the dependency from either side of the
        -- conditional.
467 468 469 470
        [ D.Simple (LDep (unionDRs vs1 vs2) (Dep dep1 (Constrained $ vr1 .||. vr2))) comp
        | D.Simple (LDep vs1                (Dep dep1 (Constrained vr1))) _ <- ps
        , D.Simple (LDep vs2                (Dep dep2 (Constrained vr2))) _ <- ps'
        , dep1 == dep2
471 472 473 474 475 476
        ]

-- | Merge DependencyReasons by unioning their variables.
unionDRs :: DependencyReason pn -> DependencyReason pn -> DependencyReason pn
unionDRs (DependencyReason pn' fs1 ss1) (DependencyReason _ fs2 ss2) =
    DependencyReason pn' (M.union fs1 fs2) (S.union ss1 ss2)
477

478
-- | Convert a Cabal dependency on a library to a solver-specific dependency.
479
convLibDep :: DependencyReason PN -> Dependency -> LDep PN
480
convLibDep dr (Dependency pn vr) = LDep dr $ Dep (PkgComponent pn ExposedLib) (Constrained vr)
481

482
-- | Convert a Cabal dependency on an executable (build-tools) to a solver-specific dependency.
483
convExeDep :: DependencyReason PN -> ExeDependency -> LDep PN
484
convExeDep dr (ExeDependency pn exe vr) = LDep dr $ Dep (PkgComponent pn (ExposedExe exe)) (Constrained vr)
485

486
-- | Convert setup dependencies
487 488
convSetupBuildInfo :: PN -> SetupBuildInfo -> FlaggedDeps PN
convSetupBuildInfo pn nfo =
489 490
    L.map (\d -> D.Simple (convLibDep (DependencyReason pn M.empty S.empty) d) ComponentSetup)
          (PD.setupDepends nfo)