ghc/compiler/basicTypes/VarSet.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   3 %
   4 \section{@VarSet@: Variable sets}
   5
   6 \begin{code}
   7 module VarSet (
   8         VarSet, IdSet, TyVarSet, IdOrTyVarSet, UVarSet,
   9         emptyVarSet, unitVarSet, mkVarSet,
  10         extendVarSet,
  11         elemVarSet, varSetElems, subVarSet,
  12         unionVarSet, unionVarSets,
  13         intersectVarSet, intersectsVarSet,
  14         isEmptyVarSet, delVarSet, delVarSetByKey,
  15         minusVarSet, foldVarSet, filterVarSet,
  16         lookupVarSet, mapVarSet, sizeVarSet, seqVarSet,
  17
  18         uniqAway
  19     ) where
  20
  21 #include "HsVersions.h"
  22
  23 import CmdLineOpts      ( opt_PprStyle_Debug )
  24 import Var              ( Var, Id, TyVar, UVar, IdOrTyVar, setVarUnique )
  25 import Unique           ( Unique, Uniquable(..), incrUnique, deriveUnique )
  26 import UniqSet
  27 import UniqFM           ( delFromUFM_Directly )
  28 import Outputable
  29 \end{code}
  30
  31 %************************************************************************
  32 %*                                                                      *
  33 \subsection{@VarSet@s}
  34 %*                                                                      *
  35 %************************************************************************
  36
  37 \begin{code}
  38 type VarSet       = UniqSet Var
  39 type IdSet        = UniqSet Id
  40 type TyVarSet     = UniqSet TyVar
  41 type IdOrTyVarSet = UniqSet IdOrTyVar
  42 type UVarSet      = UniqSet UVar
  43
  44 emptyVarSet     :: VarSet
  45 intersectVarSet :: VarSet -> VarSet -> VarSet
  46 intersectsVarSet:: VarSet -> VarSet -> Bool     -- True if non-empty intersection
  47 unionVarSet     :: VarSet -> VarSet -> VarSet
  48 unionVarSets    :: [VarSet] -> VarSet
  49 varSetElems     :: VarSet -> [Var]
  50 unitVarSet      :: Var -> VarSet
  51 extendVarSet    :: VarSet -> Var -> VarSet
  52 elemVarSet      :: Var -> VarSet -> Bool
  53 delVarSet       :: 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 subVarSet       :: VarSet -> VarSet -> Bool
  65
  66 delVarSetByKey  :: VarSet -> Unique -> VarSet
  67
  68 emptyVarSet     = emptyUniqSet
  69 unitVarSet      = unitUniqSet
  70 extendVarSet    = addOneToUniqSet
  71 intersectVarSet = intersectUniqSets
  72 intersectsVarSet s1 s2 = not (isEmptyVarSet (s1 `intersectVarSet` s2))
  73 unionVarSet     = unionUniqSets
  74 unionVarSets    = unionManyUniqSets
  75 varSetElems     = uniqSetToList
  76 elemVarSet      = elementOfUniqSet
  77 minusVarSet     = minusUniqSet
  78 delVarSet       = delOneFromUniqSet
  79 isEmptyVarSet   = isEmptyUniqSet
  80 mkVarSet        = mkUniqSet
  81 foldVarSet      = foldUniqSet
  82 lookupVarSet    = lookupUniqSet
  83 mapVarSet       = mapUniqSet
  84 sizeVarSet      = sizeUniqSet
  85 filterVarSet    = filterUniqSet
  86 a `subVarSet` b = isEmptyVarSet (a `minusVarSet` b)
  87 delVarSetByKey  = delFromUFM_Directly   -- Can't be bothered to add this to UniqSet
  88 \end{code}
  89
  90 \begin{code}
  91 seqVarSet :: VarSet -> ()
  92 seqVarSet s = sizeVarSet s `seq` ()
  93 \end{code}
  94
  95 \begin{code}
  96 uniqAway :: VarSet -> Var -> Var
  97 -- Give the Var a new unique, different to any in the VarSet
  98 uniqAway set var
  99   | not (var `elemVarSet` set) = var    -- Nothing to do
 100
 101   | otherwise
 102   = try 1 (deriveUnique (getUnique var) (hashUniqSet set))
 103   where
 104     try n uniq | uniq `elemUniqSet_Directly` set = try ((n+1)::Int) (incrUnique uniq)
 105 #ifdef DEBUG
 106                | opt_PprStyle_Debug && n > 3
 107                = pprTrace "uniqAway:" (ppr n <+> text "tries" <+> ppr var)
 108                  setVarUnique var uniq
 109 #endif
 110                | otherwise = setVarUnique var uniq
 111 \end{code}