compiler/basicTypes/VarSet.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   4 %
   5
   6 \begin{code}
   7 module VarSet (
   8         -- * Var, Id and TyVar set types
   9         VarSet, IdSet, TyVarSet, TyCoVarSet, CoVarSet,
  10
  11         -- ** Manipulating these sets
  12         emptyVarSet, unitVarSet, mkVarSet,
  13         extendVarSet, extendVarSetList, extendVarSet_C,
  14         elemVarSet, varSetElems, subVarSet,
  15         unionVarSet, unionVarSets,
  16         intersectVarSet, intersectsVarSet, disjointVarSet,
  17         isEmptyVarSet, delVarSet, delVarSetList, delVarSetByKey,
  18         minusVarSet, foldVarSet, filterVarSet, fixVarSet,
  19         lookupVarSet, mapVarSet, sizeVarSet, seqVarSet,
  20         elemVarSetByKey
  21     ) where
  22
  23 #include "HsVersions.h"
  24
  25 import Var      ( Var, TyVar, CoVar, TyCoVar, Id )
  26 import Unique
  27 import UniqSet
  28 \end{code}
  29
  30 %************************************************************************
  31 %*                                                                      *
  32 \subsection{@VarSet@s}
  33 %*                                                                      *
  34 %************************************************************************
  35
  36 \begin{code}
  37 type VarSet       = UniqSet Var
  38 type IdSet        = UniqSet Id
  39 type TyVarSet     = UniqSet TyVar
  40 type TyCoVarSet   = UniqSet TyCoVar
  41 type CoVarSet     = UniqSet CoVar
  42
  43 emptyVarSet     :: VarSet
  44 intersectVarSet :: VarSet -> VarSet -> VarSet
  45 unionVarSet     :: VarSet -> VarSet -> VarSet
  46 unionVarSets    :: [VarSet] -> VarSet
  47 varSetElems     :: VarSet -> [Var]
  48 unitVarSet      :: Var -> VarSet
  49 extendVarSet    :: VarSet -> Var -> VarSet
  50 extendVarSetList:: VarSet -> [Var] -> VarSet
  51 elemVarSet      :: Var -> VarSet -> Bool
  52 delVarSet       :: VarSet -> Var -> VarSet
  53 delVarSetList   :: VarSet -> [Var] -> VarSet
  54 minusVarSet     :: VarSet -> VarSet -> VarSet
  55 isEmptyVarSet   :: VarSet -> Bool
  56 mkVarSet        :: [Var] -> VarSet
  57 foldVarSet      :: (Var -> a -> a) -> a -> VarSet -> a
  58 lookupVarSet    :: VarSet -> Var -> Maybe Var
  59                         -- Returns the set element, which may be
  60                         -- (==) to the argument, but not the same as
  61 mapVarSet       :: (Var -> Var) -> VarSet -> VarSet
  62 sizeVarSet      :: VarSet -> Int
  63 filterVarSet    :: (Var -> Bool) -> VarSet -> VarSet
  64 extendVarSet_C  :: (Var->Var->Var) -> VarSet -> Var -> VarSet
  65
  66 delVarSetByKey  :: VarSet -> Unique -> VarSet
  67 elemVarSetByKey :: Unique -> VarSet -> Bool
  68 fixVarSet       :: (VarSet -> VarSet) -> VarSet -> VarSet
  69
  70 emptyVarSet     = emptyUniqSet
  71 unitVarSet      = unitUniqSet
  72 extendVarSet    = addOneToUniqSet
  73 extendVarSetList= addListToUniqSet
  74 intersectVarSet = intersectUniqSets
  75
  76 intersectsVarSet:: VarSet -> VarSet -> Bool     -- True if non-empty intersection
  77 disjointVarSet  :: VarSet -> VarSet -> Bool     -- True if empty intersection
  78 subVarSet       :: VarSet -> VarSet -> Bool     -- True if first arg is subset of second
  79         -- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty;
  80         -- ditto disjointVarSet, subVarSet
  81
  82 unionVarSet     = unionUniqSets
  83 unionVarSets    = unionManyUniqSets
  84 varSetElems     = uniqSetToList
  85 elemVarSet      = elementOfUniqSet
  86 minusVarSet     = minusUniqSet
  87 delVarSet       = delOneFromUniqSet
  88 delVarSetList   = delListFromUniqSet
  89 isEmptyVarSet   = isEmptyUniqSet
  90 mkVarSet        = mkUniqSet
  91 foldVarSet      = foldUniqSet
  92 lookupVarSet    = lookupUniqSet
  93 mapVarSet       = mapUniqSet
  94 sizeVarSet      = sizeUniqSet
  95 filterVarSet    = filterUniqSet
  96 extendVarSet_C = addOneToUniqSet_C
  97 delVarSetByKey  = delOneFromUniqSet_Directly
  98 elemVarSetByKey = elemUniqSet_Directly
  99 \end{code}
 100
 101 \begin{code}
 102 -- See comments with type signatures
 103 intersectsVarSet s1 s2 = not (s1 `disjointVarSet` s2)
 104 disjointVarSet   s1 s2 = isEmptyVarSet (s1 `intersectVarSet` s2)
 105 subVarSet        s1 s2 = isEmptyVarSet (s1 `minusVarSet` s2)
 106
 107 -- Iterate f to a fixpoint
 108 fixVarSet f s | new_s `subVarSet` s = s
 109               | otherwise           = fixVarSet f new_s
 110               where
 111                 new_s = f s
 112 \end{code}
 113
 114 \begin{code}
 115 seqVarSet :: VarSet -> ()
 116 seqVarSet s = sizeVarSet s `seq` ()
 117 \end{code}
 118