\begin{code}
{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
module UniqFM (
+ -- * Unique-keyed mappings
UniqFM(..), -- abstract type
-- (de-abstracted for MachRegs.trivColorable optimisation BL 2007/09)
+ -- ** Manipulating those mappings
emptyUFM,
unitUFM,
unitDirectlyUFM,
listToUFM,
listToUFM_Directly,
+ listToUFM_C,
addToUFM,addToUFM_C,addToUFM_Acc,
addListToUFM,addListToUFM_C,
addToUFM_Directly,
listToUFM :: Uniquable key => [(key,elt)] -> UniqFM elt
listToUFM_Directly
:: [(Unique, elt)] -> UniqFM elt
+listToUFM_C :: Uniquable key => (elt -> elt -> elt)
+ -> [(key, elt)]
+ -> UniqFM elt
addToUFM :: Uniquable key => UniqFM elt -> key -> elt -> UniqFM elt
addListToUFM :: Uniquable key => UniqFM elt -> [(key,elt)] -> UniqFM elt
%* *
%************************************************************************
-@UniqFM a@ is a mapping from Unique to a.
-
First, the DataType itself; which is either a Node, a Leaf, or an Empty.
\begin{code}
+-- | @UniqFM a@ is a mapping from Unique to @a@. DO NOT use these constructors
+-- directly unless you live in this module!
data UniqFM ele
= EmptyUFM
- | LeafUFM FastInt ele
- | NodeUFM FastInt -- the switching
- FastInt -- the delta
- (UniqFM ele)
- (UniqFM ele)
+ | LeafUFM !FastInt ele
+ | NodeUFM !FastInt -- the switching
+ !FastInt -- the delta
+ (UniqFM ele)
+ (UniqFM ele)
-- INVARIANT: the children of a NodeUFM are never EmptyUFMs
{-
listToUFM_Directly uniq_elt_pairs
= addListToUFM_directly_C use_snd EmptyUFM uniq_elt_pairs
+
+listToUFM_C combiner key_elt_pairs
+ = addListToUFM_C combiner EmptyUFM key_elt_pairs
\end{code}
Now ways of adding things to UniqFMs.
\begin{code}
mkLeafUFM :: FastInt -> a -> UniqFM a
-mkLeafUFM i a = LeafUFM i a
+mkLeafUFM i a =
+ ASSERT (iBox i >= 0) -- Note [Uniques must be positive]
+ LeafUFM i a
-- The *ONLY* ways of building a NodeUFM.
(indexToRoot j))
(mkLeafUFM i new)
(mkLeafUFM j old)
- | j ==# i = mkLeafUFM j (f old new)
+ | j ==# i = mkLeafUFM j $ f old new
| otherwise =
mkLLNodeUFM (getCommonNodeUFMData
(indexToRoot i)
use_snd _ b = b
\end{code}
-\begin{code}
-_unused :: FS.FastString
-_unused = undefined
-\end{code}
+{- Note [Uniques must be positive]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+The getCommonNodeUFMData function assumes that the nodes use
+positive uniques. Specifically, the inner `loop' shifts the
+low bits out of two uniques until the shifted uniques are the same.
+At the same time, it computes a new delta, by shifting
+to the left.
+
+The failure case I (JPD) encountered:
+If one of the uniques is negative, the shifting may continue
+until all 64 bits have been shifted out, resulting in a new delta
+of 0, which is wrong and can trigger later assertion failures.
+
+Where do the negative uniques come from? Both Simom M and
+I have run into this problem when hashing a data structure.
+In both cases, we have avoided the problem by ensuring that
+the hashes remain positive.
+-}