    {-
    (c) The University of Glasgow 2006
    (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
    -}

    module GHC.Types.Var.Set (
            -- * Var, Id and TyVar set types
            VarSet, IdSet, TyVarSet, CoVarSet, TyCoVarSet,

            -- ** Manipulating these sets
            emptyVarSet, unitVarSet, mkVarSet,
            extendVarSet, extendVarSetList,
            elemVarSet, subVarSet,
            unionVarSet, unionVarSets, mapUnionVarSet,
            intersectVarSet, intersectsVarSet, disjointVarSet,
            isEmptyVarSet, delVarSet, delVarSetList, delVarSetByKey,
            minusVarSet, filterVarSet, mapVarSet,
            anyVarSet, allVarSet,
            transCloVarSet, fixVarSet,
            lookupVarSet_Directly, lookupVarSet, lookupVarSetByName,
            sizeVarSet, seqVarSet,
            elemVarSetByKey, partitionVarSet,
            pluralVarSet, pprVarSet,
            nonDetStrictFoldVarSet,

            -- * Deterministic Var set types
            DVarSet, DIdSet, DTyVarSet, DTyCoVarSet,

            -- ** Manipulating these sets
            emptyDVarSet, unitDVarSet, mkDVarSet,
            extendDVarSet, extendDVarSetList,
            elemDVarSet, dVarSetElems, subDVarSet,
            unionDVarSet, unionDVarSets, mapUnionDVarSet,
            intersectDVarSet, dVarSetIntersectVarSet,
            intersectsDVarSet, disjointDVarSet,
            isEmptyDVarSet, delDVarSet, delDVarSetList,
            minusDVarSet,
            nonDetStrictFoldDVarSet,
            filterDVarSet, mapDVarSet,
            dVarSetMinusVarSet, anyDVarSet, allDVarSet,
            transCloDVarSet,
            sizeDVarSet, seqDVarSet,
            partitionDVarSet,
            dVarSetToVarSet,
        ) where

    import GHC.Prelude

    import GHC.Types.Var      ( Var, TyVar, CoVar, TyCoVar, Id )
    import GHC.Types.Unique
    import GHC.Types.Name     ( Name )
    import GHC.Types.Unique.Set
    import GHC.Types.Unique.DSet
    import GHC.Types.Unique.FM( disjointUFM, pluralUFM, pprUFM )
    import GHC.Types.Unique.DFM( disjointUDFM, udfmToUfm, anyUDFM, allUDFM )
    import GHC.Utils.Outputable (SDoc)

    -- | A non-deterministic Variable Set
    --
    -- A non-deterministic set of variables.
    -- See Note [Deterministic UniqFM] in "GHC.Types.Unique.DFM" for explanation why it's not
    -- deterministic and why it matters. Use DVarSet if the set eventually
    -- gets converted into a list or folded over in a way where the order
    -- changes the generated code, for example when abstracting variables.
    type VarSet       = UniqSet Var

    -- | Identifier Set
    type IdSet        = UniqSet Id

    -- | Type Variable Set
    type TyVarSet     = UniqSet TyVar

    -- | Coercion Variable Set
    type CoVarSet     = UniqSet CoVar

    -- | Type or Coercion Variable Set
    type TyCoVarSet   = UniqSet TyCoVar

    emptyVarSet     :: VarSet
    intersectVarSet :: VarSet -> VarSet -> VarSet
    unionVarSet     :: VarSet -> VarSet -> VarSet
    unionVarSets    :: [VarSet] -> VarSet

    mapUnionVarSet  :: (a -> VarSet) -> [a] -> VarSet
    -- ^ map the function over the list, and union the results

    unitVarSet      :: Var -> VarSet
    extendVarSet    :: VarSet -> Var -> VarSet
    extendVarSetList:: VarSet -> [Var] -> VarSet
    elemVarSet      :: Var -> VarSet -> Bool
    delVarSet       :: VarSet -> Var -> VarSet
    delVarSetList   :: VarSet -> [Var] -> VarSet
    minusVarSet     :: VarSet -> VarSet -> VarSet
    isEmptyVarSet   :: VarSet -> Bool
    mkVarSet        :: [Var] -> VarSet
    lookupVarSet_Directly :: VarSet -> Unique -> Maybe Var
    lookupVarSet    :: VarSet -> Var -> Maybe Var
                            -- Returns the set element, which may be
                            -- (==) to the argument, but not the same as
    lookupVarSetByName :: VarSet -> Name -> Maybe Var
    sizeVarSet      :: VarSet -> Int
    filterVarSet    :: (Var -> Bool) -> VarSet -> VarSet

    delVarSetByKey  :: VarSet -> Unique -> VarSet
    elemVarSetByKey :: Unique -> VarSet -> Bool
    partitionVarSet :: (Var -> Bool) -> VarSet -> (VarSet, VarSet)

    emptyVarSet :: VarSet
    emptyVarSet     = VarSet
    forall a. UniqSet a
    emptyUniqSet
    unitVarSet :: Var -> VarSet
    unitVarSet      = Var -> VarSet
    forall a. Uniquable a => a -> UniqSet a
    unitUniqSet
    extendVarSet :: VarSet -> Var -> VarSet
    extendVarSet    = VarSet -> Var -> VarSet
    forall a. Uniquable a => UniqSet a -> a -> UniqSet a
    addOneToUniqSet
    extendVarSetList :: VarSet -> [Var] -> VarSet
    extendVarSetList= VarSet -> [Var] -> VarSet
    forall a. Uniquable a => UniqSet a -> [a] -> UniqSet a
    addListToUniqSet
    intersectVarSet :: VarSet -> VarSet -> VarSet
    intersectVarSet = VarSet -> VarSet -> VarSet
    forall a. UniqSet a -> UniqSet a -> UniqSet a
    intersectUniqSets

    intersectsVarSet:: VarSet -> VarSet -> Bool     -- True if non-empty intersection
    disjointVarSet  :: VarSet -> VarSet -> Bool     -- True if empty intersection
    subVarSet       :: VarSet -> VarSet -> Bool     -- True if first arg is subset of second
            -- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty;
            -- ditto disjointVarSet, subVarSet

    unionVarSet :: VarSet -> VarSet -> VarSet
    unionVarSet     = VarSet -> VarSet -> VarSet
    forall a. UniqSet a -> UniqSet a -> UniqSet a
    unionUniqSets
    unionVarSets :: [VarSet] -> VarSet
    unionVarSets    = [VarSet] -> VarSet
    forall a. [UniqSet a] -> UniqSet a
    unionManyUniqSets
    elemVarSet :: Var -> VarSet -> Bool
    elemVarSet      = Var -> VarSet -> Bool
    forall a. Uniquable a => a -> UniqSet a -> Bool
    elementOfUniqSet
    minusVarSet :: VarSet -> VarSet -> VarSet
    minusVarSet     = VarSet -> VarSet -> VarSet
    forall a. UniqSet a -> UniqSet a -> UniqSet a
    minusUniqSet
    delVarSet :: VarSet -> Var -> VarSet
    delVarSet       = VarSet -> Var -> VarSet
    forall a. Uniquable a => UniqSet a -> a -> UniqSet a
    delOneFromUniqSet
    delVarSetList :: VarSet -> [Var] -> VarSet
    delVarSetList   = VarSet -> [Var] -> VarSet
    forall a. Uniquable a => UniqSet a -> [a] -> UniqSet a
    delListFromUniqSet
    isEmptyVarSet :: VarSet -> Bool
    isEmptyVarSet   = VarSet -> Bool
    forall a. UniqSet a -> Bool
    isEmptyUniqSet
    mkVarSet :: [Var] -> VarSet
    mkVarSet        = [Var] -> VarSet
    forall a. Uniquable a => [a] -> UniqSet a
    mkUniqSet
    lookupVarSet_Directly :: VarSet -> Unique -> Maybe Var
    lookupVarSet_Directly = VarSet -> Unique -> Maybe Var
    forall a. UniqSet a -> Unique -> Maybe a
    lookupUniqSet_Directly
    lookupVarSet :: VarSet -> Var -> Maybe Var
    lookupVarSet    = VarSet -> Var -> Maybe Var
    forall key. Uniquable key => UniqSet key -> key -> Maybe key
    lookupUniqSet
    lookupVarSetByName :: VarSet -> Name -> Maybe Var
    lookupVarSetByName VarSet
    set Name
    name = VarSet -> Unique -> Maybe Var
    forall a. UniqSet a -> Unique -> Maybe a
    lookupUniqSet_Directly VarSet
    set (Name -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique Name
    name)
    sizeVarSet :: VarSet -> Int
    sizeVarSet      = VarSet -> Int
    forall a. UniqSet a -> Int
    sizeUniqSet
    filterVarSet :: (Var -> Bool) -> VarSet -> VarSet
    filterVarSet    = (Var -> Bool) -> VarSet -> VarSet
    forall a. (a -> Bool) -> UniqSet a -> UniqSet a
    filterUniqSet
    delVarSetByKey :: VarSet -> Unique -> VarSet
    delVarSetByKey  = VarSet -> Unique -> VarSet
    forall a. UniqSet a -> Unique -> UniqSet a
    delOneFromUniqSet_Directly
    elemVarSetByKey :: Unique -> VarSet -> Bool
    elemVarSetByKey = Unique -> VarSet -> Bool
    forall a. Unique -> UniqSet a -> Bool
    elemUniqSet_Directly
    partitionVarSet :: (Var -> Bool) -> VarSet -> (VarSet, VarSet)
    partitionVarSet = (Var -> Bool) -> VarSet -> (VarSet, VarSet)
    forall a. (a -> Bool) -> UniqSet a -> (UniqSet a, UniqSet a)
    partitionUniqSet

    mapUnionVarSet :: forall a. (a -> VarSet) -> [a] -> VarSet
    mapUnionVarSet a -> VarSet
    get_set [a]
    xs = (a -> VarSet -> VarSet) -> VarSet -> [a] -> VarSet
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (VarSet -> VarSet -> VarSet
    unionVarSet (VarSet -> VarSet -> VarSet)
    -> (a -> VarSet) -> a -> VarSet -> VarSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> VarSet
    get_set) VarSet
    emptyVarSet [a]
    xs

    -- See comments with type signatures
    intersectsVarSet :: VarSet -> VarSet -> Bool
    intersectsVarSet VarSet
    s1 VarSet
    s2 = Bool -> Bool
    not (VarSet
    s1 VarSet -> VarSet -> Bool
    `disjointVarSet` VarSet
    s2)
    disjointVarSet :: VarSet -> VarSet -> Bool
    disjointVarSet   VarSet
    s1 VarSet
    s2 = UniqFM Var Var -> UniqFM Var Var -> Bool
    forall {k} (key :: k) elt1 elt2.
    UniqFM key elt1 -> UniqFM key elt2 -> Bool
    disjointUFM (VarSet -> UniqFM Var Var
    forall a. UniqSet a -> UniqFM a a
    getUniqSet VarSet
    s1) (VarSet -> UniqFM Var Var
    forall a. UniqSet a -> UniqFM a a
    getUniqSet VarSet
    s2)
    subVarSet :: VarSet -> VarSet -> Bool
    subVarSet        VarSet
    s1 VarSet
    s2 = VarSet -> Bool
    isEmptyVarSet (VarSet
    s1 VarSet -> VarSet -> VarSet
    `minusVarSet` VarSet
    s2)

    anyVarSet :: (Var -> Bool) -> VarSet -> Bool
    anyVarSet :: (Var -> Bool) -> VarSet -> Bool
    anyVarSet = (Var -> Bool) -> VarSet -> Bool
    forall a. (a -> Bool) -> UniqSet a -> Bool
    uniqSetAny

    allVarSet :: (Var -> Bool) -> VarSet -> Bool
    allVarSet :: (Var -> Bool) -> VarSet -> Bool
    allVarSet = (Var -> Bool) -> VarSet -> Bool
    forall a. (a -> Bool) -> UniqSet a -> Bool
    uniqSetAll

    mapVarSet :: Uniquable b => (a -> b) -> UniqSet a -> UniqSet b
    mapVarSet :: forall b a. Uniquable b => (a -> b) -> UniqSet a -> UniqSet b
    mapVarSet = (a -> b) -> UniqSet a -> UniqSet b
    forall b a. Uniquable b => (a -> b) -> UniqSet a -> UniqSet b
    mapUniqSet

    -- See Note [Deterministic UniqFM] to learn about nondeterminism.
    -- If you use this please provide a justification why it doesn't introduce
    -- nondeterminism.
    nonDetStrictFoldVarSet :: (Var -> a -> a) -> a -> VarSet -> a
    nonDetStrictFoldVarSet :: forall a. (Var -> a -> a) -> a -> VarSet -> a
    nonDetStrictFoldVarSet = (Var -> a -> a) -> a -> VarSet -> a
    forall elt a. (elt -> a -> a) -> a -> UniqSet elt -> a
    nonDetStrictFoldUniqSet

    fixVarSet :: (VarSet -> VarSet)   -- Map the current set to a new set
              -> VarSet -> VarSet
    -- (fixVarSet f s) repeatedly applies f to the set s,
    -- until it reaches a fixed point.
    fixVarSet :: (VarSet -> VarSet) -> VarSet -> VarSet
    fixVarSet VarSet -> VarSet
    fn VarSet
    vars
      | VarSet
    new_vars VarSet -> VarSet -> Bool
    `subVarSet` VarSet
    vars = VarSet
    vars
      | Bool
    otherwise                 = (VarSet -> VarSet) -> VarSet -> VarSet
    fixVarSet VarSet -> VarSet
    fn VarSet
    new_vars
      where
        new_vars :: VarSet
    new_vars = VarSet -> VarSet
    fn VarSet
    vars

    transCloVarSet :: (VarSet -> VarSet)
                      -- Map some variables in the set to
                      -- extra variables that should be in it
                   -> VarSet -> VarSet
    -- (transCloVarSet f s) repeatedly applies f to new candidates, adding any
    -- new variables to s that it finds thereby, until it reaches a fixed point.
    --
    -- The function fn could be (Var -> VarSet), but we use (VarSet -> VarSet)
    -- for efficiency, so that the test can be batched up.
    -- It's essential that fn will work fine if given new candidates
    -- one at a time; ie  fn {v1,v2} = fn v1 `union` fn v2
    -- Use fixVarSet if the function needs to see the whole set all at once
    transCloVarSet :: (VarSet -> VarSet) -> VarSet -> VarSet
    transCloVarSet VarSet -> VarSet
    fn VarSet
    seeds
      = VarSet -> VarSet -> VarSet
    go VarSet
    seeds VarSet
    seeds
      where
        go :: VarSet  -- Accumulating result
           -> VarSet  -- Work-list; un-processed subset of accumulating result
           -> VarSet
        -- Specification: go acc vs = acc `union` transClo fn vs

        go :: VarSet -> VarSet -> VarSet
    go VarSet
    acc VarSet
    candidates
           | VarSet -> Bool
    isEmptyVarSet VarSet
    new_vs = VarSet
    acc
           | Bool
    otherwise            = VarSet -> VarSet -> VarSet
    go (VarSet
    acc VarSet -> VarSet -> VarSet
    `unionVarSet` VarSet
    new_vs) VarSet
    new_vs
           where
             new_vs :: VarSet
    new_vs = VarSet -> VarSet
    fn VarSet
    candidates VarSet -> VarSet -> VarSet
    `minusVarSet` VarSet
    acc

    seqVarSet :: VarSet -> ()
    seqVarSet :: VarSet -> ()
    seqVarSet VarSet
    s = VarSet
    s VarSet -> () -> ()
    forall a b. a -> b -> b
    `seq` ()

    -- | Determines the pluralisation suffix appropriate for the length of a set
    -- in the same way that plural from Outputable does for lists.
    pluralVarSet :: VarSet -> SDoc
    pluralVarSet :: VarSet -> SDoc
    pluralVarSet = UniqFM Var Var -> SDoc
    forall {k} (key :: k) a. UniqFM key a -> SDoc
    pluralUFM (UniqFM Var Var -> SDoc)
    -> (VarSet -> UniqFM Var Var) -> VarSet -> SDoc
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . VarSet -> UniqFM Var Var
    forall a. UniqSet a -> UniqFM a a
    getUniqSet

    -- | Pretty-print a non-deterministic set.
    -- The order of variables is non-deterministic and for pretty-printing that
    -- shouldn't be a problem.
    -- Having this function helps contain the non-determinism created with
    -- nonDetEltsUFM.
    -- Passing a list to the pretty-printing function allows the caller
    -- to decide on the order of Vars (eg. toposort them) without them having
    -- to use nonDetEltsUFM at the call site. This prevents from let-binding
    -- non-deterministically ordered lists and reusing them where determinism
    -- matters.
    pprVarSet :: VarSet          -- ^ The things to be pretty printed
              -> ([Var] -> SDoc) -- ^ The pretty printing function to use on the
                                 -- elements
              -> SDoc            -- ^ 'SDoc' where the things have been pretty
                                 -- printed
    pprVarSet :: VarSet -> ([Var] -> SDoc) -> SDoc
    pprVarSet = UniqFM Var Var -> ([Var] -> SDoc) -> SDoc
    forall {k} (key :: k) a. UniqFM key a -> ([a] -> SDoc) -> SDoc
    pprUFM (UniqFM Var Var -> ([Var] -> SDoc) -> SDoc)
    -> (VarSet -> UniqFM Var Var) -> VarSet -> ([Var] -> SDoc) -> SDoc
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . VarSet -> UniqFM Var Var
    forall a. UniqSet a -> UniqFM a a
    getUniqSet

    -- Deterministic VarSet
    -- See Note [Deterministic UniqFM] in GHC.Types.Unique.DFM for explanation why we need
    -- DVarSet.

    -- | Deterministic Variable Set
    type DVarSet     = UniqDSet Var

    -- | Deterministic Identifier Set
    type DIdSet      = UniqDSet Id

    -- | Deterministic Type Variable Set
    type DTyVarSet   = UniqDSet TyVar

    -- | Deterministic Type or Coercion Variable Set
    type DTyCoVarSet = UniqDSet TyCoVar

    emptyDVarSet :: DVarSet
    emptyDVarSet :: DVarSet
    emptyDVarSet = DVarSet
    forall a. UniqDSet a
    emptyUniqDSet

    unitDVarSet :: Var -> DVarSet
    unitDVarSet :: Var -> DVarSet
    unitDVarSet = Var -> DVarSet
    forall a. Uniquable a => a -> UniqDSet a
    unitUniqDSet

    mkDVarSet :: [Var] -> DVarSet
    mkDVarSet :: [Var] -> DVarSet
    mkDVarSet = [Var] -> DVarSet
    forall a. Uniquable a => [a] -> UniqDSet a
    mkUniqDSet

    -- The new element always goes to the right of existing ones.
    extendDVarSet :: DVarSet -> Var -> DVarSet
    extendDVarSet :: DVarSet -> Var -> DVarSet
    extendDVarSet = DVarSet -> Var -> DVarSet
    forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
    addOneToUniqDSet

    elemDVarSet :: Var -> DVarSet -> Bool
    elemDVarSet :: Var -> DVarSet -> Bool
    elemDVarSet = Var -> DVarSet -> Bool
    forall a. Uniquable a => a -> UniqDSet a -> Bool
    elementOfUniqDSet

    dVarSetElems :: DVarSet -> [Var]
    dVarSetElems :: DVarSet -> [Var]
    dVarSetElems = DVarSet -> [Var]
    forall a. UniqDSet a -> [a]
    uniqDSetToList

    subDVarSet :: DVarSet -> DVarSet -> Bool
    subDVarSet :: DVarSet -> DVarSet -> Bool
    subDVarSet DVarSet
    s1 DVarSet
    s2 = DVarSet -> Bool
    isEmptyDVarSet (DVarSet
    s1 DVarSet -> DVarSet -> DVarSet
    `minusDVarSet` DVarSet
    s2)

    unionDVarSet :: DVarSet -> DVarSet -> DVarSet
    unionDVarSet :: DVarSet -> DVarSet -> DVarSet
    unionDVarSet = DVarSet -> DVarSet -> DVarSet
    forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
    unionUniqDSets

    unionDVarSets :: [DVarSet] -> DVarSet
    unionDVarSets :: [DVarSet] -> DVarSet
    unionDVarSets = [DVarSet] -> DVarSet
    forall a. [UniqDSet a] -> UniqDSet a
    unionManyUniqDSets

    -- | Map the function over the list, and union the results
    mapUnionDVarSet  :: (a -> DVarSet) -> [a] -> DVarSet
    mapUnionDVarSet :: forall a. (a -> DVarSet) -> [a] -> DVarSet
    mapUnionDVarSet a -> DVarSet
    get_set [a]
    xs = (a -> DVarSet -> DVarSet) -> DVarSet -> [a] -> DVarSet
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (DVarSet -> DVarSet -> DVarSet
    unionDVarSet (DVarSet -> DVarSet -> DVarSet)
    -> (a -> DVarSet) -> a -> DVarSet -> DVarSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> DVarSet
    get_set) DVarSet
    emptyDVarSet [a]
    xs

    intersectDVarSet :: DVarSet -> DVarSet -> DVarSet
    intersectDVarSet :: DVarSet -> DVarSet -> DVarSet
    intersectDVarSet = DVarSet -> DVarSet -> DVarSet
    forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
    intersectUniqDSets

    dVarSetIntersectVarSet :: DVarSet -> VarSet -> DVarSet
    dVarSetIntersectVarSet :: DVarSet -> VarSet -> DVarSet
    dVarSetIntersectVarSet = DVarSet -> VarSet -> DVarSet
    forall a. UniqDSet a -> UniqSet a -> UniqDSet a
    uniqDSetIntersectUniqSet

    -- | True if empty intersection
    disjointDVarSet :: DVarSet -> DVarSet -> Bool
    disjointDVarSet :: DVarSet -> DVarSet -> Bool
    disjointDVarSet DVarSet
    s1 DVarSet
    s2 = UniqDFM Var Var -> UniqDFM Var Var -> Bool
    forall {k} (key :: k) elt.
    UniqDFM key elt -> UniqDFM key elt -> Bool
    disjointUDFM (DVarSet -> UniqDFM Var Var
    forall a. UniqDSet a -> UniqDFM a a
    getUniqDSet DVarSet
    s1) (DVarSet -> UniqDFM Var Var
    forall a. UniqDSet a -> UniqDFM a a
    getUniqDSet DVarSet
    s2)

    -- | True if non-empty intersection
    intersectsDVarSet :: DVarSet -> DVarSet -> Bool
    intersectsDVarSet :: DVarSet -> DVarSet -> Bool
    intersectsDVarSet DVarSet
    s1 DVarSet
    s2 = Bool -> Bool
    not (DVarSet
    s1 DVarSet -> DVarSet -> Bool
    `disjointDVarSet` DVarSet
    s2)

    isEmptyDVarSet :: DVarSet -> Bool
    isEmptyDVarSet :: DVarSet -> Bool
    isEmptyDVarSet = DVarSet -> Bool
    forall a. UniqDSet a -> Bool
    isEmptyUniqDSet

    delDVarSet :: DVarSet -> Var -> DVarSet
    delDVarSet :: DVarSet -> Var -> DVarSet
    delDVarSet = DVarSet -> Var -> DVarSet
    forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
    delOneFromUniqDSet

    minusDVarSet :: DVarSet -> DVarSet -> DVarSet
    minusDVarSet :: DVarSet -> DVarSet -> DVarSet
    minusDVarSet = DVarSet -> DVarSet -> DVarSet
    forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
    minusUniqDSet

    dVarSetMinusVarSet :: DVarSet -> VarSet -> DVarSet
    dVarSetMinusVarSet :: DVarSet -> VarSet -> DVarSet
    dVarSetMinusVarSet = DVarSet -> VarSet -> DVarSet
    forall a. UniqDSet a -> UniqSet a -> UniqDSet a
    uniqDSetMinusUniqSet

    -- See Note [Deterministic UniqFM] to learn about nondeterminism.
    -- If you use this please provide a justification why it doesn't introduce
    -- nondeterminism.
    nonDetStrictFoldDVarSet :: (Var -> a -> a) -> a -> DVarSet -> a
    nonDetStrictFoldDVarSet :: forall a. (Var -> a -> a) -> a -> DVarSet -> a
    nonDetStrictFoldDVarSet = (Var -> a -> a) -> a -> DVarSet -> a
    forall a b. (a -> b -> b) -> b -> UniqDSet a -> b
    nonDetStrictFoldUniqDSet

    anyDVarSet :: (Var -> Bool) -> DVarSet -> Bool
    anyDVarSet :: (Var -> Bool) -> DVarSet -> Bool
    anyDVarSet Var -> Bool
    p = (Var -> Bool) -> UniqDFM Var Var -> Bool
    forall {k} elt (key :: k). (elt -> Bool) -> UniqDFM key elt -> Bool
    anyUDFM Var -> Bool
    p (UniqDFM Var Var -> Bool)
    -> (DVarSet -> UniqDFM Var Var) -> DVarSet -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DVarSet -> UniqDFM Var Var
    forall a. UniqDSet a -> UniqDFM a a
    getUniqDSet

    allDVarSet :: (Var -> Bool) -> DVarSet -> Bool
    allDVarSet :: (Var -> Bool) -> DVarSet -> Bool
    allDVarSet Var -> Bool
    p = (Var -> Bool) -> UniqDFM Var Var -> Bool
    forall {k} elt (key :: k). (elt -> Bool) -> UniqDFM key elt -> Bool
    allUDFM Var -> Bool
    p (UniqDFM Var Var -> Bool)
    -> (DVarSet -> UniqDFM Var Var) -> DVarSet -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DVarSet -> UniqDFM Var Var
    forall a. UniqDSet a -> UniqDFM a a
    getUniqDSet

    mapDVarSet :: Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
    mapDVarSet :: forall b a. Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
    mapDVarSet = (a -> b) -> UniqDSet a -> UniqDSet b
    forall b a. Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
    mapUniqDSet

    filterDVarSet :: (Var -> Bool) -> DVarSet -> DVarSet
    filterDVarSet :: (Var -> Bool) -> DVarSet -> DVarSet
    filterDVarSet = (Var -> Bool) -> DVarSet -> DVarSet
    forall a. (a -> Bool) -> UniqDSet a -> UniqDSet a
    filterUniqDSet

    sizeDVarSet :: DVarSet -> Int
    sizeDVarSet :: DVarSet -> Int
    sizeDVarSet = DVarSet -> Int
    forall a. UniqDSet a -> Int
    sizeUniqDSet

    -- | Partition DVarSet according to the predicate given
    partitionDVarSet :: (Var -> Bool) -> DVarSet -> (DVarSet, DVarSet)
    partitionDVarSet :: (Var -> Bool) -> DVarSet -> (DVarSet, DVarSet)
    partitionDVarSet = (Var -> Bool) -> DVarSet -> (DVarSet, DVarSet)
    forall a. (a -> Bool) -> UniqDSet a -> (UniqDSet a, UniqDSet a)
    partitionUniqDSet

    -- | Delete a list of variables from DVarSet
    delDVarSetList :: DVarSet -> [Var] -> DVarSet
    delDVarSetList :: DVarSet -> [Var] -> DVarSet
    delDVarSetList = DVarSet -> [Var] -> DVarSet
    forall a. Uniquable a => UniqDSet a -> [a] -> UniqDSet a
    delListFromUniqDSet

    seqDVarSet :: DVarSet -> ()
    seqDVarSet :: DVarSet -> ()
    seqDVarSet DVarSet
    s = DVarSet
    s DVarSet -> () -> ()
    forall a b. a -> b -> b
    `seq` ()

    -- | Add a list of variables to DVarSet
    extendDVarSetList :: DVarSet -> [Var] -> DVarSet
    extendDVarSetList :: DVarSet -> [Var] -> DVarSet
    extendDVarSetList = DVarSet -> [Var] -> DVarSet
    forall a. Uniquable a => UniqDSet a -> [a] -> UniqDSet a
    addListToUniqDSet

    -- | Convert a DVarSet to a VarSet by forgetting the order of insertion
    dVarSetToVarSet :: DVarSet -> VarSet
    dVarSetToVarSet :: DVarSet -> VarSet
    dVarSetToVarSet = UniqFM Var Var -> VarSet
    forall a. UniqFM a a -> UniqSet a
    unsafeUFMToUniqSet (UniqFM Var Var -> VarSet)
    -> (DVarSet -> UniqFM Var Var) -> DVarSet -> VarSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqDFM Var Var -> UniqFM Var Var
    forall {k} (key :: k) elt. UniqDFM key elt -> UniqFM key elt
    udfmToUfm (UniqDFM Var Var -> UniqFM Var Var)
    -> (DVarSet -> UniqDFM Var Var) -> DVarSet -> UniqFM Var Var
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DVarSet -> UniqDFM Var Var
    forall a. UniqDSet a -> UniqDFM a a
    getUniqDSet

    -- | transCloVarSet for DVarSet
    transCloDVarSet :: (DVarSet -> DVarSet)
                      -- Map some variables in the set to
                      -- extra variables that should be in it
                    -> DVarSet -> DVarSet
    -- (transCloDVarSet f s) repeatedly applies f to new candidates, adding any
    -- new variables to s that it finds thereby, until it reaches a fixed point.
    --
    -- The function fn could be (Var -> DVarSet), but we use (DVarSet -> DVarSet)
    -- for efficiency, so that the test can be batched up.
    -- It's essential that fn will work fine if given new candidates
    -- one at a time; ie  fn {v1,v2} = fn v1 `union` fn v2
    transCloDVarSet :: (DVarSet -> DVarSet) -> DVarSet -> DVarSet
    transCloDVarSet DVarSet -> DVarSet
    fn DVarSet
    seeds
      = DVarSet -> DVarSet -> DVarSet
    go DVarSet
    seeds DVarSet
    seeds
      where
        go :: DVarSet  -- Accumulating result
           -> DVarSet  -- Work-list; un-processed subset of accumulating result
           -> DVarSet
        -- Specification: go acc vs = acc `union` transClo fn vs

        go :: DVarSet -> DVarSet -> DVarSet
    go DVarSet
    acc DVarSet
    candidates
           | DVarSet -> Bool
    isEmptyDVarSet DVarSet
    new_vs = DVarSet
    acc
           | Bool
    otherwise            = DVarSet -> DVarSet -> DVarSet
    go (DVarSet
    acc DVarSet -> DVarSet -> DVarSet
    `unionDVarSet` DVarSet
    new_vs) DVarSet
    new_vs
           where
             new_vs :: DVarSet
    new_vs = DVarSet -> DVarSet
    fn DVarSet
    candidates DVarSet -> DVarSet -> DVarSet
    `minusDVarSet` DVarSet
    acc