{-
(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     = forall a. UniqSet a
emptyUniqSet
unitVarSet :: Var -> VarSet
unitVarSet      = forall a. Uniquable a => a -> UniqSet a
unitUniqSet
extendVarSet :: VarSet -> Var -> VarSet
extendVarSet    = forall a. Uniquable a => UniqSet a -> a -> UniqSet a
addOneToUniqSet
extendVarSetList :: VarSet -> [Var] -> VarSet
extendVarSetList= forall a. Uniquable a => UniqSet a -> [a] -> UniqSet a
addListToUniqSet
intersectVarSet :: VarSet -> VarSet -> VarSet
intersectVarSet = 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     = forall a. UniqSet a -> UniqSet a -> UniqSet a
unionUniqSets
unionVarSets :: [VarSet] -> VarSet
unionVarSets    = forall a. [UniqSet a] -> UniqSet a
unionManyUniqSets
elemVarSet :: Var -> VarSet -> Bool
elemVarSet      = forall a. Uniquable a => a -> UniqSet a -> Bool
elementOfUniqSet
minusVarSet :: VarSet -> VarSet -> VarSet
minusVarSet     = forall a. UniqSet a -> UniqSet a -> UniqSet a
minusUniqSet
delVarSet :: VarSet -> Var -> VarSet
delVarSet       = forall a. Uniquable a => UniqSet a -> a -> UniqSet a
delOneFromUniqSet
delVarSetList :: VarSet -> [Var] -> VarSet
delVarSetList   = forall a. Uniquable a => UniqSet a -> [a] -> UniqSet a
delListFromUniqSet
isEmptyVarSet :: VarSet -> Bool
isEmptyVarSet   = forall a. UniqSet a -> Bool
isEmptyUniqSet
mkVarSet :: [Var] -> VarSet
mkVarSet        = forall a. Uniquable a => [a] -> UniqSet a
mkUniqSet
lookupVarSet_Directly :: VarSet -> Unique -> Maybe Var
lookupVarSet_Directly = forall a. UniqSet a -> Unique -> Maybe a
lookupUniqSet_Directly
lookupVarSet :: VarSet -> Var -> Maybe Var
lookupVarSet    = forall key. Uniquable key => UniqSet key -> key -> Maybe key
lookupUniqSet
lookupVarSetByName :: VarSet -> Name -> Maybe Var
lookupVarSetByName VarSet
set Name
name = forall a. UniqSet a -> Unique -> Maybe a
lookupUniqSet_Directly VarSet
set (forall a. Uniquable a => a -> Unique
getUnique Name
name)
sizeVarSet :: VarSet -> Int
sizeVarSet      = forall a. UniqSet a -> Int
sizeUniqSet
filterVarSet :: (Var -> Bool) -> VarSet -> VarSet
filterVarSet    = forall a. (a -> Bool) -> UniqSet a -> UniqSet a
filterUniqSet
delVarSetByKey :: VarSet -> Unique -> VarSet
delVarSetByKey  = forall a. UniqSet a -> Unique -> UniqSet a
delOneFromUniqSet_Directly
elemVarSetByKey :: Unique -> VarSet -> Bool
elemVarSetByKey = forall a. Unique -> UniqSet a -> Bool
elemUniqSet_Directly
partitionVarSet :: (Var -> Bool) -> VarSet -> (VarSet, VarSet)
partitionVarSet = 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 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (VarSet -> VarSet -> VarSet
unionVarSet 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 = forall key elt1 elt2. UniqFM key elt1 -> UniqFM key elt2 -> Bool
disjointUFM (forall a. UniqSet a -> UniqFM a a
getUniqSet VarSet
s1) (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 = forall a. (a -> Bool) -> UniqSet a -> Bool
uniqSetAny

allVarSet :: (Var -> Bool) -> VarSet -> Bool
allVarSet :: (Var -> Bool) -> VarSet -> Bool
allVarSet = 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 = 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 = 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 seq :: 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 = forall key a. UniqFM key a -> SDoc
pluralUFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall key a. UniqFM key a -> ([a] -> SDoc) -> SDoc
pprUFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. UniqDSet a
emptyUniqDSet

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

mkDVarSet :: [Var] -> DVarSet
mkDVarSet :: [Var] -> DVarSet
mkDVarSet = 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 = forall a. Uniquable a => UniqDSet a -> a -> UniqDSet a
addOneToUniqDSet

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

dVarSetElems :: DVarSet -> [Var]
dVarSetElems :: DVarSet -> [Var]
dVarSetElems = 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 = forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
unionUniqDSets

unionDVarSets :: [DVarSet] -> DVarSet
unionDVarSets :: [DVarSet] -> DVarSet
unionDVarSets = 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 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (DVarSet -> DVarSet -> DVarSet
unionDVarSet 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 = forall a. UniqDSet a -> UniqDSet a -> UniqDSet a
intersectUniqDSets

dVarSetIntersectVarSet :: DVarSet -> VarSet -> DVarSet
dVarSetIntersectVarSet :: DVarSet -> VarSet -> DVarSet
dVarSetIntersectVarSet = 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 = forall key elt. UniqDFM key elt -> UniqDFM key elt -> Bool
disjointUDFM (forall a. UniqDSet a -> UniqDFM a a
getUniqDSet DVarSet
s1) (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 = forall a. UniqDSet a -> Bool
isEmptyUniqDSet

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

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

dVarSetMinusVarSet :: DVarSet -> VarSet -> DVarSet
dVarSetMinusVarSet :: DVarSet -> VarSet -> DVarSet
dVarSetMinusVarSet = 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 = 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 = forall elt key. (elt -> Bool) -> UniqDFM key elt -> Bool
anyUDFM Var -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. UniqDSet a -> UniqDFM a a
getUniqDSet

allDVarSet :: (Var -> Bool) -> DVarSet -> Bool
allDVarSet :: (Var -> Bool) -> DVarSet -> Bool
allDVarSet Var -> Bool
p = forall elt key. (elt -> Bool) -> UniqDFM key elt -> Bool
allUDFM Var -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall b a. Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
mapUniqDSet

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

sizeDVarSet :: DVarSet -> Int
sizeDVarSet :: DVarSet -> Int
sizeDVarSet = 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 = 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 = forall a. Uniquable a => UniqDSet a -> [a] -> UniqDSet a
delListFromUniqDSet

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

-- | Add a list of variables to DVarSet
extendDVarSetList :: DVarSet -> [Var] -> DVarSet
extendDVarSetList :: DVarSet -> [Var] -> DVarSet
extendDVarSetList = 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 = forall a. UniqFM a a -> UniqSet a
unsafeUFMToUniqSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key elt. UniqDFM key elt -> UniqFM key elt
udfmToUfm forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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