X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2Futils%2FUniqFM.lhs;h=cc2d066ab761896f15e54e176b4b2259fdb46cd8;hb=d436c70d43fb905c63220040168295e473f4b90a;hp=de02227031fb5a06c1c6fa92dc9bbc4518727f35;hpb=cd25dd99f1135d58b1e02b9abca4162debddffe4;p=ghc-hetmet.git

diff --git a/compiler/utils/UniqFM.lhs b/compiler/utils/UniqFM.lhs
index de02227..cc2d066 100644
--- a/compiler/utils/UniqFM.lhs
+++ b/compiler/utils/UniqFM.lhs
@@ -15,14 +15,17 @@ Basically, the things need to be in class @Uniquable@, and we use the
 \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,
@@ -74,6 +77,9 @@ unitDirectlyUFM -- got the Unique already
 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
@@ -196,18 +202,18 @@ This code is explained in the paper:
 %*									*
 %************************************************************************
 
-@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
 
 {-
@@ -243,6 +249,9 @@ listToUFM key_elt_pairs
 
 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.
@@ -634,7 +643,9 @@ functionality, but may do a few needless evaluations.
 
 \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.
 
@@ -698,7 +709,7 @@ insert_ele  f (LeafUFM j old) i new
 			  (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)
@@ -792,8 +803,8 @@ getCommonNodeUFMData (NodeUFMData i p) (NodeUFMData i2 p2)
   | p <# p2	= getCommonNodeUFMData_ p2 (j `quotFastInt` (p2 `quotFastInt` p)) j2
   | otherwise	= getCommonNodeUFMData_ p j (j2 `quotFastInt` (p `quotFastInt` p2))
   where
-    j  = i  `quotFastInt` (shiftL1 p)
-    j2 = i2 `quotFastInt` (shiftL1 p2)
+    !j  = i  `quotFastInt` (shiftL1 p)
+    !j2 = i2 `quotFastInt` (shiftL1 p2)
 
     getCommonNodeUFMData_ :: FastInt -> FastInt -> FastInt -> NodeUFMData
 
@@ -839,7 +850,21 @@ use_snd :: a -> b -> b
 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.
+-}