    -- | Conflict sets
    --
    -- Intended for double import
    --
    -- > import Distribution.Solver.Modular.ConflictSet (ConflictSet)
    -- > import qualified Distribution.Solver.Modular.ConflictSet as CS
    module Distribution.Solver.Modular.ConflictSet (
        ConflictSet -- opaque
      , Conflict(..)
      , ConflictMap
      , OrderedVersionRange(..)
      , showConflictSet
      , showCSSortedByFrequency
      , showCSWithFrequency
        -- Set-like operations
      , toSet
      , toList
      , union
      , unions
      , insert
      , delete
      , empty
      , singleton
      , singletonWithConflict
      , size
      , member
      , lookup
      , filter
      , fromList
      ) where

    import Prelude hiding (lookup)
    import Data.List (intercalate, sortBy)
    import Data.Map (Map)
    import Data.Set (Set)
    import Data.Function (on)
    import qualified Data.Map.Strict as M
    import qualified Data.Set as S

    import Distribution.Solver.Modular.Var
    import Distribution.Solver.Modular.Version
    import Distribution.Solver.Types.PackagePath

    -- | The set of variables involved in a solver conflict, each paired with
    -- details about the conflict.
    newtype ConflictSet = CS {
        -- | The set of variables involved in the conflict
        ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap :: Map (Var QPN) (Set Conflict)
      }
      deriving (ConflictSet -> ConflictSet -> Bool
    (ConflictSet -> ConflictSet -> Bool)
    -> (ConflictSet -> ConflictSet -> Bool) -> Eq ConflictSet
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: ConflictSet -> ConflictSet -> Bool
    == :: ConflictSet -> ConflictSet -> Bool
    $c/= :: ConflictSet -> ConflictSet -> Bool
    /= :: ConflictSet -> ConflictSet -> Bool
    Eq, Int -> ConflictSet -> ShowS
    [ConflictSet] -> ShowS
    ConflictSet -> String
    (Int -> ConflictSet -> ShowS)
    -> (ConflictSet -> String)
    -> ([ConflictSet] -> ShowS)
    -> Show ConflictSet
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> ConflictSet -> ShowS
    showsPrec :: Int -> ConflictSet -> ShowS
    $cshow :: ConflictSet -> String
    show :: ConflictSet -> String
    $cshowList :: [ConflictSet] -> ShowS
    showList :: [ConflictSet] -> ShowS
    Show)

    -- | More detailed information about how a conflict set variable caused a
    -- conflict. This information can be used to determine whether a second value
    -- for that variable would lead to the same conflict.
    --
    -- TODO: Handle dependencies under flags or stanzas.
    data Conflict =

        -- | The conflict set variable represents a package which depends on the
        -- specified problematic package. For example, the conflict set entry
        -- '(P x, GoalConflict y)' means that package x introduced package y, and y
        -- led to a conflict.
        GoalConflict QPN

        -- | The conflict set variable represents a package with a constraint that
        -- excluded the specified package and version. For example, the conflict set
        -- entry '(P x, VersionConstraintConflict y (mkVersion [2, 0]))' means that
        -- package x's constraint on y excluded y-2.0.
      | VersionConstraintConflict QPN Ver

        -- | The conflict set variable represents a package that was excluded by a
        -- constraint from the specified package. For example, the conflict set
        -- entry '(P x, VersionConflict y (orLaterVersion (mkVersion [2, 0])))'
        -- means that package y's constraint 'x >= 2.0' excluded some version of x.
      | VersionConflict QPN OrderedVersionRange

        -- | Any other conflict.
      | OtherConflict
      deriving (Conflict -> Conflict -> Bool
    (Conflict -> Conflict -> Bool)
    -> (Conflict -> Conflict -> Bool) -> Eq Conflict
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Conflict -> Conflict -> Bool
    == :: Conflict -> Conflict -> Bool
    $c/= :: Conflict -> Conflict -> Bool
    /= :: Conflict -> Conflict -> Bool
    Eq, Eq Conflict
    Eq Conflict =>
    (Conflict -> Conflict -> Ordering)
    -> (Conflict -> Conflict -> Bool)
    -> (Conflict -> Conflict -> Bool)
    -> (Conflict -> Conflict -> Bool)
    -> (Conflict -> Conflict -> Bool)
    -> (Conflict -> Conflict -> Conflict)
    -> (Conflict -> Conflict -> Conflict)
    -> Ord Conflict
    Conflict -> Conflict -> Bool
    Conflict -> Conflict -> Ordering
    Conflict -> Conflict -> Conflict
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: Conflict -> Conflict -> Ordering
    compare :: Conflict -> Conflict -> Ordering
    $c< :: Conflict -> Conflict -> Bool
    < :: Conflict -> Conflict -> Bool
    $c<= :: Conflict -> Conflict -> Bool
    <= :: Conflict -> Conflict -> Bool
    $c> :: Conflict -> Conflict -> Bool
    > :: Conflict -> Conflict -> Bool
    $c>= :: Conflict -> Conflict -> Bool
    >= :: Conflict -> Conflict -> Bool
    $cmax :: Conflict -> Conflict -> Conflict
    max :: Conflict -> Conflict -> Conflict
    $cmin :: Conflict -> Conflict -> Conflict
    min :: Conflict -> Conflict -> Conflict
    Ord, Int -> Conflict -> ShowS
    [Conflict] -> ShowS
    Conflict -> String
    (Int -> Conflict -> ShowS)
    -> (Conflict -> String) -> ([Conflict] -> ShowS) -> Show Conflict
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Conflict -> ShowS
    showsPrec :: Int -> Conflict -> ShowS
    $cshow :: Conflict -> String
    show :: Conflict -> String
    $cshowList :: [Conflict] -> ShowS
    showList :: [Conflict] -> ShowS
    Show)

    -- | Version range with an 'Ord' instance.
    newtype OrderedVersionRange = OrderedVersionRange VR
      deriving (OrderedVersionRange -> OrderedVersionRange -> Bool
    (OrderedVersionRange -> OrderedVersionRange -> Bool)
    -> (OrderedVersionRange -> OrderedVersionRange -> Bool)
    -> Eq OrderedVersionRange
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: OrderedVersionRange -> OrderedVersionRange -> Bool
    == :: OrderedVersionRange -> OrderedVersionRange -> Bool
    $c/= :: OrderedVersionRange -> OrderedVersionRange -> Bool
    /= :: OrderedVersionRange -> OrderedVersionRange -> Bool
    Eq, Int -> OrderedVersionRange -> ShowS
    [OrderedVersionRange] -> ShowS
    OrderedVersionRange -> String
    (Int -> OrderedVersionRange -> ShowS)
    -> (OrderedVersionRange -> String)
    -> ([OrderedVersionRange] -> ShowS)
    -> Show OrderedVersionRange
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> OrderedVersionRange -> ShowS
    showsPrec :: Int -> OrderedVersionRange -> ShowS
    $cshow :: OrderedVersionRange -> String
    show :: OrderedVersionRange -> String
    $cshowList :: [OrderedVersionRange] -> ShowS
    showList :: [OrderedVersionRange] -> ShowS
    Show)

    -- TODO: Avoid converting the version ranges to strings.
    instance Ord OrderedVersionRange where
      compare :: OrderedVersionRange -> OrderedVersionRange -> Ordering
    compare = String -> String -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare (String -> String -> Ordering)
    -> (OrderedVersionRange -> String)
    -> OrderedVersionRange
    -> OrderedVersionRange
    -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` OrderedVersionRange -> String
    forall a. Show a => a -> String
    show

    showConflictSet :: ConflictSet -> String
    showConflictSet :: ConflictSet -> String
    showConflictSet = String -> [String] -> String
    forall a. [a] -> [[a]] -> [a]
    intercalate String
    ", " ([String] -> String)
    -> (ConflictSet -> [String]) -> ConflictSet -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Var QPN -> String) -> [Var QPN] -> [String]
    forall a b. (a -> b) -> [a] -> [b]
    map Var QPN -> String
    showVar ([Var QPN] -> [String])
    -> (ConflictSet -> [Var QPN]) -> ConflictSet -> [String]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> [Var QPN]
    toList

    showCSSortedByFrequency :: ConflictMap -> ConflictSet -> String
    showCSSortedByFrequency :: ConflictMap -> ConflictSet -> String
    showCSSortedByFrequency = Bool -> ConflictMap -> ConflictSet -> String
    showCS Bool
    False

    showCSWithFrequency :: ConflictMap -> ConflictSet -> String
    showCSWithFrequency :: ConflictMap -> ConflictSet -> String
    showCSWithFrequency = Bool -> ConflictMap -> ConflictSet -> String
    showCS Bool
    True

    showCS :: Bool -> ConflictMap -> ConflictSet -> String
    showCS :: Bool -> ConflictMap -> ConflictSet -> String
    showCS Bool
    showCount ConflictMap
    cm =
        String -> [String] -> String
    forall a. [a] -> [[a]] -> [a]
    intercalate String
    ", " ([String] -> String)
    -> (ConflictSet -> [String]) -> ConflictSet -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((Var QPN, Maybe Int) -> String)
    -> [(Var QPN, Maybe Int)] -> [String]
    forall a b. (a -> b) -> [a] -> [b]
    map (Var QPN, Maybe Int) -> String
    forall {a}. Show a => (Var QPN, Maybe a) -> String
    showWithFrequency ([(Var QPN, Maybe Int)] -> [String])
    -> (ConflictSet -> [(Var QPN, Maybe Int)])
    -> ConflictSet
    -> [String]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> [(Var QPN, Maybe Int)]
    indexByFrequency
      where
        indexByFrequency :: ConflictSet -> [(Var QPN, Maybe Int)]
    indexByFrequency = ((Var QPN, Maybe Int) -> (Var QPN, Maybe Int) -> Ordering)
    -> [(Var QPN, Maybe Int)] -> [(Var QPN, Maybe Int)]
    forall a. (a -> a -> Ordering) -> [a] -> [a]
    sortBy ((Maybe Int -> Maybe Int -> Ordering)
    -> Maybe Int -> Maybe Int -> Ordering
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Maybe Int -> Maybe Int -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare (Maybe Int -> Maybe Int -> Ordering)
    -> ((Var QPN, Maybe Int) -> Maybe Int)
    -> (Var QPN, Maybe Int)
    -> (Var QPN, Maybe Int)
    -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` (Var QPN, Maybe Int) -> Maybe Int
    forall a b. (a, b) -> b
    snd) ([(Var QPN, Maybe Int)] -> [(Var QPN, Maybe Int)])
    -> (ConflictSet -> [(Var QPN, Maybe Int)])
    -> ConflictSet
    -> [(Var QPN, Maybe Int)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Var QPN -> (Var QPN, Maybe Int))
    -> [Var QPN] -> [(Var QPN, Maybe Int)]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Var QPN
    c -> (Var QPN
    c, Var QPN -> ConflictMap -> Maybe Int
    forall k a. Ord k => k -> Map k a -> Maybe a
    M.lookup Var QPN
    c ConflictMap
    cm)) ([Var QPN] -> [(Var QPN, Maybe Int)])
    -> (ConflictSet -> [Var QPN])
    -> ConflictSet
    -> [(Var QPN, Maybe Int)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> [Var QPN]
    toList
        showWithFrequency :: (Var QPN, Maybe a) -> String
    showWithFrequency (Var QPN
    conflict, Maybe a
    maybeFrequency) = case Maybe a
    maybeFrequency of
          Just a
    frequency
            | Bool
    showCount -> Var QPN -> String
    showVar Var QPN
    conflict String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " (" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ a -> String
    forall a. Show a => a -> String
    show a
    frequency String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    ")"
          Maybe a
    _             -> Var QPN -> String
    showVar Var QPN
    conflict

    {-------------------------------------------------------------------------------
      Set-like operations
    -------------------------------------------------------------------------------}

    toSet :: ConflictSet -> Set (Var QPN)
    toSet :: ConflictSet -> Set (Var QPN)
    toSet = Map (Var QPN) (Set Conflict) -> Set (Var QPN)
    forall k a. Map k a -> Set k
    M.keysSet (Map (Var QPN) (Set Conflict) -> Set (Var QPN))
    -> (ConflictSet -> Map (Var QPN) (Set Conflict))
    -> ConflictSet
    -> Set (Var QPN)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap

    toList :: ConflictSet -> [Var QPN]
    toList :: ConflictSet -> [Var QPN]
    toList = Map (Var QPN) (Set Conflict) -> [Var QPN]
    forall k a. Map k a -> [k]
    M.keys (Map (Var QPN) (Set Conflict) -> [Var QPN])
    -> (ConflictSet -> Map (Var QPN) (Set Conflict))
    -> ConflictSet
    -> [Var QPN]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap

    union :: ConflictSet -> ConflictSet -> ConflictSet
    union :: ConflictSet -> ConflictSet -> ConflictSet
    union ConflictSet
    cs ConflictSet
    cs' = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = (Set Conflict -> Set Conflict -> Set Conflict)
    -> Map (Var QPN) (Set Conflict)
    -> Map (Var QPN) (Set Conflict)
    -> Map (Var QPN) (Set Conflict)
    forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWith Set Conflict -> Set Conflict -> Set Conflict
    forall a. Ord a => Set a -> Set a -> Set a
    S.union (ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap ConflictSet
    cs) (ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap ConflictSet
    cs')
        }

    unions :: [ConflictSet] -> ConflictSet
    unions :: [ConflictSet] -> ConflictSet
    unions [ConflictSet]
    css = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = (Set Conflict -> Set Conflict -> Set Conflict)
    -> [Map (Var QPN) (Set Conflict)] -> Map (Var QPN) (Set Conflict)
    forall (f :: * -> *) k a.
    (Foldable f, Ord k) =>
    (a -> a -> a) -> f (Map k a) -> Map k a
    M.unionsWith Set Conflict -> Set Conflict -> Set Conflict
    forall a. Ord a => Set a -> Set a -> Set a
    S.union ((ConflictSet -> Map (Var QPN) (Set Conflict))
    -> [ConflictSet] -> [Map (Var QPN) (Set Conflict)]
    forall a b. (a -> b) -> [a] -> [b]
    map ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap [ConflictSet]
    css)
        }

    insert :: Var QPN -> ConflictSet -> ConflictSet
    insert :: Var QPN -> ConflictSet -> ConflictSet
    insert Var QPN
    var ConflictSet
    cs = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = Var QPN
    -> Set Conflict
    -> Map (Var QPN) (Set Conflict)
    -> Map (Var QPN) (Set Conflict)
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    M.insert Var QPN
    var (Conflict -> Set Conflict
    forall a. a -> Set a
    S.singleton Conflict
    OtherConflict) (ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap ConflictSet
    cs)
        }

    delete :: Var QPN -> ConflictSet -> ConflictSet
    delete :: Var QPN -> ConflictSet -> ConflictSet
    delete Var QPN
    var ConflictSet
    cs = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = Var QPN
    -> Map (Var QPN) (Set Conflict) -> Map (Var QPN) (Set Conflict)
    forall k a. Ord k => k -> Map k a -> Map k a
    M.delete Var QPN
    var (ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap ConflictSet
    cs)
        }

    empty :: ConflictSet
    empty :: ConflictSet
    empty = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = Map (Var QPN) (Set Conflict)
    forall k a. Map k a
    M.empty
        }

    singleton :: Var QPN -> ConflictSet
    singleton :: Var QPN -> ConflictSet
    singleton Var QPN
    var = Var QPN -> Conflict -> ConflictSet
    singletonWithConflict Var QPN
    var Conflict
    OtherConflict

    singletonWithConflict :: Var QPN -> Conflict -> ConflictSet
    singletonWithConflict :: Var QPN -> Conflict -> ConflictSet
    singletonWithConflict Var QPN
    var Conflict
    conflict = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = Var QPN -> Set Conflict -> Map (Var QPN) (Set Conflict)
    forall k a. k -> a -> Map k a
    M.singleton Var QPN
    var (Conflict -> Set Conflict
    forall a. a -> Set a
    S.singleton Conflict
    conflict)
        }

    size :: ConflictSet -> Int
    size :: ConflictSet -> Int
    size = Map (Var QPN) (Set Conflict) -> Int
    forall k a. Map k a -> Int
    M.size (Map (Var QPN) (Set Conflict) -> Int)
    -> (ConflictSet -> Map (Var QPN) (Set Conflict))
    -> ConflictSet
    -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap

    member :: Var QPN -> ConflictSet -> Bool
    member :: Var QPN -> ConflictSet -> Bool
    member Var QPN
    var = Var QPN -> Map (Var QPN) (Set Conflict) -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    M.member Var QPN
    var (Map (Var QPN) (Set Conflict) -> Bool)
    -> (ConflictSet -> Map (Var QPN) (Set Conflict))
    -> ConflictSet
    -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap

    lookup :: Var QPN -> ConflictSet -> Maybe (Set Conflict)
    lookup :: Var QPN -> ConflictSet -> Maybe (Set Conflict)
    lookup Var QPN
    var = Var QPN -> Map (Var QPN) (Set Conflict) -> Maybe (Set Conflict)
    forall k a. Ord k => k -> Map k a -> Maybe a
    M.lookup Var QPN
    var (Map (Var QPN) (Set Conflict) -> Maybe (Set Conflict))
    -> (ConflictSet -> Map (Var QPN) (Set Conflict))
    -> ConflictSet
    -> Maybe (Set Conflict)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ConflictSet -> Map (Var QPN) (Set Conflict)
    conflictSetToMap

    fromList :: [Var QPN] -> ConflictSet
    fromList :: [Var QPN] -> ConflictSet
    fromList [Var QPN]
    vars = CS {
          conflictSetToMap :: Map (Var QPN) (Set Conflict)
    conflictSetToMap = [(Var QPN, Set Conflict)] -> Map (Var QPN) (Set Conflict)
    forall k a. Ord k => [(k, a)] -> Map k a
    M.fromList [(Var QPN
    var, Conflict -> Set Conflict
    forall a. a -> Set a
    S.singleton Conflict
    OtherConflict) | Var QPN
    var <- [Var QPN]
    vars]
        }

    type ConflictMap = Map (Var QPN) Int