Add DVarSet - a deterministic set of Vars

This implements `DVarSet`, a deterministic set of Vars, with an
interface very similar to `VarSet` with a couple of functions missing.

I will need this in changes that follow, one of them will be about
changing the type of the set of Vars that `RuleInfo` holds to make the
free variable computation deterministic.

Test Plan:
./validate
I can add new tests if anyone wants me to.

Reviewers: simonpj, simonmar, austin, bgamari

Reviewed By: simonmar, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1487

GHC Trac Issues: #4012

1 files changed, 88 insertions, 0 deletions

diff --git a/compiler/utils/UniqDSet.hs b/compiler/utils/UniqDSet.hs
new file mode 100644
index 0000000000..bf9f7a301c
--- /dev/null
+++ b/compiler/utils/UniqDSet.hs
@@ -0,0 +1,88 @@
+-- (c) Bartosz Nitka, Facebook, 2015
+
+-- |
+-- Specialised deterministic sets, for things with @Uniques@
+--
+-- Based on @UniqDFMs@ (as you would expect).
+-- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need it.
+--
+-- Basically, the things need to be in class @Uniquable@.
+
+module UniqDSet (
+        -- * Unique set type
+        UniqDSet,    -- type synonym for UniqFM a
+
+        -- ** Manipulating these sets
+        delOneFromUniqDSet,
+        emptyUniqDSet,
+        unitUniqDSet,
+        mkUniqDSet,
+        addOneToUniqDSet, addListToUniqDSet,
+        unionUniqDSets, unionManyUniqDSets,
+        minusUniqDSet,
+        intersectUniqDSets,
+        foldUniqDSet,
+        elementOfUniqDSet,
+        filterUniqDSet,
+        sizeUniqDSet,
+        isEmptyUniqDSet,
+        lookupUniqDSet,
+        uniqDSetToList,
+    ) where
+
+import UniqDFM
+import Unique
+
+type UniqDSet a = UniqDFM a
+
+emptyUniqDSet :: UniqDSet a
+emptyUniqDSet = emptyUDFM
+
+unitUniqDSet :: Uniquable a => a -> UniqDSet a
+unitUniqDSet x = unitUDFM x x
+
+mkUniqDSet :: Uniquable a => [a]  -> UniqDSet a
+mkUniqDSet = foldl addOneToUniqDSet emptyUniqDSet
+
+addOneToUniqDSet :: Uniquable a => UniqDSet a -> a -> UniqDSet a
+addOneToUniqDSet set x = addToUDFM set x x
+
+addListToUniqDSet :: Uniquable a => UniqDSet a -> [a] -> UniqDSet a
+addListToUniqDSet = foldl addOneToUniqDSet
+
+delOneFromUniqDSet :: Uniquable a => UniqDSet a -> a -> UniqDSet a
+delOneFromUniqDSet = delFromUDFM
+
+unionUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
+unionUniqDSets = plusUDFM
+
+unionManyUniqDSets :: [UniqDSet a] -> UniqDSet a
+unionManyUniqDSets [] = emptyUniqDSet
+unionManyUniqDSets sets = foldr1 unionUniqDSets sets
+
+minusUniqDSet  :: UniqDSet a -> UniqDSet a -> UniqDSet a
+minusUniqDSet = minusUDFM
+
+intersectUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
+intersectUniqDSets = intersectUDFM
+
+foldUniqDSet :: (a -> b -> b) -> b -> UniqDSet a -> b
+foldUniqDSet = foldUDFM
+
+elementOfUniqDSet :: Uniquable a => a -> UniqDSet a -> Bool
+elementOfUniqDSet = elemUDFM
+
+filterUniqDSet :: (a -> Bool) -> UniqDSet a -> UniqDSet a
+filterUniqDSet = filterUDFM
+
+sizeUniqDSet :: UniqDSet a -> Int
+sizeUniqDSet = sizeUDFM
+
+isEmptyUniqDSet :: UniqDSet a -> Bool
+isEmptyUniqDSet = isNullUDFM
+
+lookupUniqDSet :: Uniquable a => UniqDSet a -> a -> Maybe a
+lookupUniqDSet = lookupUDFM
+
+uniqDSetToList :: UniqDSet a -> [a]
+uniqDSetToList = eltsUDFM