5f6554ed6c1e5112733fc728bffe5c1562564312
[ghc.git] / compiler / utils / UniqDFM.hs
1 {-
2 (c) Bartosz Nitka, Facebook, 2015
3
4 UniqDFM: Specialised deterministic finite maps, for things with @Uniques@.
5
6 Basically, the things need to be in class @Uniquable@, and we use the
7 @getUnique@ method to grab their @Uniques@.
8
9 This is very similar to @UniqFM@, the major difference being that the order of
10 folding is not dependent on @Unique@ ordering, giving determinism.
11 Currently the ordering is determined by insertion order.
12
13 See Note [Unique Determinism] in Unique for explanation why @Unique@ ordering
14 is not deterministic.
15 -}
16
17 {-# LANGUAGE DeriveDataTypeable #-}
18 {-# LANGUAGE DeriveFunctor #-}
19 {-# LANGUAGE FlexibleContexts #-}
20 {-# OPTIONS_GHC -Wall #-}
21
22 module UniqDFM (
23 -- * Unique-keyed deterministic mappings
24 UniqDFM, -- abstract type
25
26 -- ** Manipulating those mappings
27 emptyUDFM,
28 addToUDFM,
29 lookupUDFM,
30 foldUDFM,
31 eltsUDFM,
32 udfmToList,
33 ) where
34
35 import FastString
36 import Unique ( Uniquable(..), Unique, getKey )
37 import Outputable
38
39 import qualified Data.IntMap as M
40 import Data.Typeable
41 import Data.Data
42 import Data.List (sortBy)
43 import Data.Function (on)
44
45 -- Note [Deterministic UniqFM]
46 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~
47 -- Normal @UniqFM@ when you turn it into a list will use
48 -- Data.IntMap.toList function that returns the elements in the order of
49 -- the keys. The keys in @UniqFM@ are always @Uniques@, so you end up with
50 -- with a list ordered by @Uniques@.
51 -- The order of @Uniques@ is known to be not stable across rebuilds.
52 -- See Note [Unique Determinism] in Unique.
53
54 -- There's more than one way to implement this. The implementation here tags
55 -- every value with the insertion time that can later be used to sort the
56 -- values when asked to convert to a list.
57 --
58 -- An alternative would be to have
59 --
60 -- data UniqDFM ele = UDFM (M.IntMap ele) [ele]
61 --
62 -- where the list determines the order. This makes deletion tricky as we'd
63 -- only accumulate elements in that list, but makes merging easier as you
64 -- don't have to renumber everything.
65 -- I've tested both approaches by replacing UniqFM and the cost was about
66 -- the same for both. We don't need merging nor deletion yet, but when we
67 -- do it might be worth to reevaluate the trade-offs here.
68
69 data TaggedVal val = TaggedVal val {-# UNPACK #-} !Int
70 deriving (Data, Typeable)
71
72 taggedFst :: TaggedVal val -> val
73 taggedFst (TaggedVal v _) = v
74
75 taggedSnd :: TaggedVal val -> Int
76 taggedSnd (TaggedVal _ i) = i
77
78 instance Eq val => Eq (TaggedVal val) where
79 (TaggedVal v1 _) == (TaggedVal v2 _) = v1 == v2
80
81 instance Functor TaggedVal where
82 fmap f (TaggedVal val i) = TaggedVal (f val) i
83
84 data UniqDFM ele = UDFM !(M.IntMap (TaggedVal ele)) {-# UNPACK #-} !Int
85 deriving (Data, Typeable, Functor)
86
87 emptyUDFM :: UniqDFM elt
88 emptyUDFM = UDFM M.empty 0
89
90 addToUDFM :: Uniquable key => UniqDFM elt -> key -> elt -> UniqDFM elt
91 addToUDFM (UDFM m i) k v =
92 UDFM (M.insert (getKey $ getUnique k) (TaggedVal v i) m) (i + 1)
93
94 lookupUDFM :: Uniquable key => UniqDFM elt -> key -> Maybe elt
95 lookupUDFM (UDFM m _i) k = taggedFst `fmap` M.lookup (getKey $ getUnique k) m
96
97 foldUDFM :: (elt -> a -> a) -> a -> UniqDFM elt -> a
98 foldUDFM k z m = foldr k z (eltsUDFM m)
99
100 eltsUDFM :: UniqDFM elt -> [elt]
101 eltsUDFM (UDFM m _i) =
102 map taggedFst $ sortBy (compare `on` taggedSnd) $ M.elems m
103
104 udfmToList :: UniqDFM elt -> [(Unique, elt)]
105 udfmToList (UDFM m _i) =
106 [ (getUnique k, taggedFst v)
107 | (k, v) <- sortBy (compare `on` (taggedSnd . snd)) $ M.toList m ]
108
109 -- Output-ery
110
111 instance Outputable a => Outputable (UniqDFM a) where
112 ppr ufm = pprUniqDFM ppr ufm
113
114 pprUniqDFM :: (a -> SDoc) -> UniqDFM a -> SDoc
115 pprUniqDFM ppr_elt ufm
116 = brackets $ fsep $ punctuate comma $
117 [ ppr uq <+> ptext (sLit ":->") <+> ppr_elt elt
118 | (uq, elt) <- udfmToList ufm ]