diff options
Diffstat (limited to 'compiler/utils/UniqDFM.hs')
| -rw-r--r-- | compiler/utils/UniqDFM.hs | 19 |
1 files changed, 14 insertions, 5 deletions
diff --git a/compiler/utils/UniqDFM.hs b/compiler/utils/UniqDFM.hs index 38bf79df24..a7a0ef8d32 100644 --- a/compiler/utils/UniqDFM.hs +++ b/compiler/utils/UniqDFM.hs @@ -81,7 +81,7 @@ import UniqFM (UniqFM, listToUFM_Directly, nonDetUFMToList, ufmToIntMap) -- order then `udfmToList` returns them in deterministic order. -- -- There is an implementation cost: each element is given a serial number --- as it is added, and `udfmToList` sorts it's result by this serial +-- as it is added, and `udfmToList` sorts its result by this serial -- number. So you should only use `UniqDFM` if you need the deterministic -- property. -- @@ -193,9 +193,10 @@ delFromUDFM (UDFM m i) k = UDFM (M.delete (getKey $ getUnique k) m) i plusUDFM_C :: (elt -> elt -> elt) -> UniqDFM elt -> UniqDFM elt -> UniqDFM elt plusUDFM_C f udfml@(UDFM _ i) udfmr@(UDFM _ j) - -- we will use the upper bound on the tag as a proxy for the set size, - -- to insert the smaller one into the bigger one - | i > j = insertUDFMIntoLeft_C f udfml udfmr + -- We will use the upper bound on the tag as a proxy for the set size, + -- to insert the smaller one into the bigger one. + -- See Note [Order of insertion]. + | i >= j = insertUDFMIntoLeft_C f udfml udfmr | otherwise = insertUDFMIntoLeft_C f udfmr udfml -- Note [Overflow on plusUDFM] @@ -230,12 +231,20 @@ plusUDFM_C f udfml@(UDFM _ i) udfmr@(UDFM _ j) -- O(m log m) for extracting the elements from the smaller set in the -- insertion order and O(m * min(n+m, W)) to insert them into the bigger -- set. +-- +-- Note [Order of insertion] +-- ~~~~~~~~~~~~~~~~~~~~~~~~~ +-- When two UDFMs have the same maximum tag, we choose to insert the right +-- argument into the left. This preserves left-to-right ordering when unioning +-- a bunch of one-element sets, for example - if we inserted the left argument +-- into the right one, then the two elements would be transposed. plusUDFM :: UniqDFM elt -> UniqDFM elt -> UniqDFM elt plusUDFM udfml@(UDFM _ i) udfmr@(UDFM _ j) -- we will use the upper bound on the tag as a proxy for the set size, -- to insert the smaller one into the bigger one - | i > j = insertUDFMIntoLeft udfml udfmr + -- See Note [Order of insertion]. + | i >= j = insertUDFMIntoLeft udfml udfmr | otherwise = insertUDFMIntoLeft udfmr udfml insertUDFMIntoLeft :: UniqDFM elt -> UniqDFM elt -> UniqDFM elt |