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

{-# LANGUAGE CPP #-}

module VarSet (
        -- * 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,

        -- * 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, foldDVarSet, filterDVarSet, mapDVarSet,
        dVarSetMinusVarSet, anyDVarSet, allDVarSet,
        transCloDVarSet,
        sizeDVarSet, seqDVarSet,
        partitionDVarSet,
        dVarSetToVarSet,
    ) where

#include "HsVersions.h"

import GhcPrelude

import Var      ( Var, TyVar, CoVar, TyCoVar, Id )
import Unique
import Name     ( Name )
import UniqSet
import UniqDSet
import UniqFM( disjointUFM, pluralUFM, pprUFM )
import UniqDFM( disjointUDFM, udfmToUfm, anyUDFM, allUDFM )
import Outputable (SDoc)

-- | A non-deterministic Variable Set
--
-- A non-deterministic set of variables.
-- See Note [Deterministic UniqFM] in UniqDFM 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 a b. Uniquable a => UniqSet b -> a -> Maybe b
lookupUniqSet
lookupVarSetByName :: VarSet -> Name -> Maybe Var
lookupVarSetByName = VarSet -> Name -> Maybe Var
forall a b. Uniquable a => UniqSet b -> a -> Maybe b
lookupUniqSet
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 :: (a -> VarSet) -> [a] -> VarSet
mapUnionVarSet a -> VarSet
get_set [a]
xs = (a -> VarSet -> VarSet) -> VarSet -> [a] -> VarSet
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 -> UniqFM Var -> Bool
forall elt1 elt2. UniqFM elt1 -> UniqFM elt2 -> Bool
disjointUFM (VarSet -> UniqFM Var
forall a. UniqSet a -> UniqFM a
getUniqSet VarSet
s1) (VarSet -> UniqFM Var
forall a. UniqSet a -> UniqFM 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 :: (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

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 at 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 -> Int
sizeVarSet VarSet
s Int -> () -> ()
`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 -> SDoc
forall a. UniqFM a -> SDoc
pluralUFM (UniqFM Var -> SDoc) -> (VarSet -> UniqFM Var) -> VarSet -> SDoc
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VarSet -> UniqFM Var
forall a. UniqSet a -> UniqFM 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] -> SDoc) -> SDoc
forall a. UniqFM a -> ([a] -> SDoc) -> SDoc
pprUFM (UniqFM Var -> ([Var] -> SDoc) -> SDoc)
-> (VarSet -> UniqFM Var) -> VarSet -> ([Var] -> SDoc) -> SDoc
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VarSet -> UniqFM Var
forall a. UniqSet a -> UniqFM a
getUniqSet

-- Deterministic VarSet
-- See Note [Deterministic UniqFM] in UniqDFM 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 :: (a -> DVarSet) -> [a] -> DVarSet
mapUnionDVarSet a -> DVarSet
get_set [a]
xs = (a -> DVarSet -> DVarSet) -> DVarSet -> [a] -> DVarSet
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 b. UniqDSet a -> UniqSet b -> UniqDSet a
uniqDSetIntersectUniqSet

-- | True if empty intersection
disjointDVarSet :: DVarSet -> DVarSet -> Bool
disjointDVarSet :: DVarSet -> DVarSet -> Bool
disjointDVarSet DVarSet
s1 DVarSet
s2 = UniqDFM Var -> UniqDFM Var -> Bool
forall elt. UniqDFM elt -> UniqDFM elt -> Bool
disjointUDFM (DVarSet -> UniqDFM Var
forall a. UniqDSet a -> UniqDFM a
getUniqDSet DVarSet
s1) (DVarSet -> UniqDFM Var
forall a. UniqDSet a -> UniqDFM 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 b. UniqDSet a -> UniqSet b -> UniqDSet a
uniqDSetMinusUniqSet

foldDVarSet :: (Var -> a -> a) -> a -> DVarSet -> a
foldDVarSet :: (Var -> a -> a) -> a -> DVarSet -> a
foldDVarSet = (Var -> a -> a) -> a -> DVarSet -> a
forall a b. (a -> b -> b) -> b -> UniqDSet a -> b
foldUniqDSet

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

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

mapDVarSet :: Uniquable b => (a -> b) -> UniqDSet a -> UniqDSet b
mapDVarSet :: (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 -> Int
sizeDVarSet DVarSet
s Int -> () -> ()
`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 forgeting the order of insertion
dVarSetToVarSet :: DVarSet -> VarSet
dVarSetToVarSet :: DVarSet -> VarSet
dVarSetToVarSet = UniqFM Var -> VarSet
forall a. UniqFM a -> UniqSet a
unsafeUFMToUniqSet (UniqFM Var -> VarSet)
-> (DVarSet -> UniqFM Var) -> DVarSet -> VarSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDFM Var -> UniqFM Var
forall elt. UniqDFM elt -> UniqFM elt
udfmToUfm (UniqDFM Var -> UniqFM Var)
-> (DVarSet -> UniqDFM Var) -> DVarSet -> UniqFM Var
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DVarSet -> UniqDFM Var
forall a. UniqDSet a -> UniqDFM 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 at 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