Zubin pushed to branch wip/uniquedfm-todo at Glasgow Haskell Compiler / GHC Commits: 6c885c39 by Zubin Duggal at 2026-07-31T15:56:58+05:30 UniqueDFM: only bump tag when we actually insert a new element - - - - - 1cb350c2 by Zubin Duggal at 2026-07-31T15:56:58+05:30 UniqueDFM: Rewrite Note [Deterministic UniqFM] - - - - - 1 changed file: - compiler/GHC/Types/Unique/DFM.hs Changes: ===================================== compiler/GHC/Types/Unique/DFM.hs ===================================== @@ -82,56 +82,66 @@ import GHC.Types.Unique.FM (UniqFM, nonDetUFMToList, ufmToIntMap, unsafeIntMapTo import Unsafe.Coerce import qualified GHC.Data.Word64Set as W --- Note [Deterministic UniqFM] --- ~~~~~~~~~~~~~~~~~~~~~~~~~~~ --- A @UniqDFM@ is just like @UniqFM@ with the following additional --- property: the function `udfmToList` returns the elements in some --- deterministic order not depending on the Unique key for those elements. --- --- If the client of the map performs operations on the map in deterministic --- order then `udfmToList` returns them in deterministic order. --- --- The order does not depend on how existing entries were --- updated. Updating an existing entry keeps it original position in the order --- This means `alterUDFM` consistent with `addToUDFM` and `adjustUDFM`, --- so that for example `alterUDFM id k = id` and `alterUDFM (fmap f) k = adjustUDFM f k` --- --- There is an implementation cost: each element is given a serial number --- 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. --- --- `foldUDFM` also preserves determinism. --- --- Normal @UniqFM@ when you turn it into a list will use --- Data.IntMap.toList function that returns the elements in the order of --- the keys. The keys in @UniqFM@ are always @Uniques@, so you end up with --- with a list ordered by @Uniques@. --- The order of @Uniques@ is known to be not stable across rebuilds. --- See Note [Unique Determinism] in GHC.Types.Unique. --- --- --- There's more than one way to implement this. The implementation here tags --- every value with the insertion time that can later be used to sort the --- values when asked to convert to a list. --- --- Updating an existing key keeps the old tag. This keeps the order stable for --- maps whose entries are updated many times. The instance environments are --- the main example: inserting an instance updates the entry of its class in a --- DNameEnv, and when updates moved keys to the end the order of instances shown --- by :info depended on the order in which interfaces happened to be loaded --- (#27532). Now a class keeps its place once its first instance is added, so --- loading further interfaces cannot change the order. --- --- An alternative would be to have --- --- data UniqDFM ele = UDFM (M.IntMap ele) [ele] --- --- where the list determines the order. This makes deletion tricky as we'd --- only accumulate elements in that list, but makes merging easier as you --- can just merge both structures independently. --- Deletion can probably be done in amortized fashion when the size of the --- list is twice the size of the set. +{- Note [Deterministic UniqFM] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +When you enumerate the elements of a normal `UniqFM`, using `nonDetUFMToList`, you +get the elements back in the order of their `Unique` keys. This can mess up deterministic +compilation; see Note [Unique Determinism] in GHC.Types.Unique. + +This module defines /deterministic/ unique-keyed finite maps, `UniqDFM`, which have +the following property: + + (UniqDFM property) The function `udfmToList` returns the elements in the order + in which they were inserted; that is, in order of their "insertion date". + + In particular, the order of elements does not depend on: + * The Unique key for those elements + * How existing entries are updated with `alterUDFM`; updating an element does not change + its insertion date. + + If an element is completely deleted and then again inserted, the latter insertion counts as its + insertion date. + + When we take (m1 `plusUDFM` m2), the insertion dates of elements in the smaller map are + adjusted to be after all those in the bigger map. + +Updating an existing entry keeps its original position in the order. +This means `alterUDFM` is consistent with `addToUDFM` and `adjustUDFM`, +so that for example `alterUDFM id k = id` and `alterUDFM (fmap f) k = adjustUDFM f k` + +It also keeps the order stable for +maps whose entries are updated many times. The instance environments are +the main example: inserting an instance updates the entry of its class in a +DNameEnv, and when updates moved keys to the end the order of instances shown +by :info depended on the order in which interfaces happened to be loaded +(#27532). Now a class keeps its place once its first instance is added, so +loading further interfaces cannot change the order. + +`foldUDFM` also preserves determinism: + + foldUDFM k z m = foldr k z (eltsUDFM m) + +Implementation +~~~~~~~~~~~~~~ +There's more than one way to implement this. The implementation here tags +every value with the insertion time that can later be used to sort the +values when asked to convert to a list. + +There is an implementation cost: each element is given a serial number +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. + +An alternative would be to have + + data UniqDFM ele = UDFM (M.IntMap ele) [ele] + +where the list determines the order. This makes deletion tricky as we'd +only accumulate elements in that list, but makes merging easier as you +can just merge both structures independently. +Deletion can probably be done in amortized fashion when the size of the +list is twice the size of the set. +-} -- | A type of values tagged with insertion time data TaggedVal val = @@ -187,33 +197,33 @@ unitUDFM k v = UDFM (M.singleton (getKey $ getUnique k) (TaggedVal v 0)) 1 addToUDFM :: Uniquable key => UniqDFM key elt -> key -> elt -> UniqDFM key elt addToUDFM m k v = addToUDFM_Directly m (getUnique k) v +alteredUDFM :: Int -> (Maybe (TaggedVal elt), M.Word64Map (TaggedVal elt)) -> UniqDFM key elt +alteredUDFM i (new, m) = case new of + Just (TaggedVal _ tag) | tag == i -> UDFM m (i + 1) + _ -> UDFM m i + -- A new key goes to the right of existing ones -- Overwriting an existing key keeps its position in the iteration order addToUDFM_Directly :: UniqDFM key elt -> Unique -> elt -> UniqDFM key elt addToUDFM_Directly (UDFM m i) u v - = UDFM (MS.insertWith tf (getKey u) (TaggedVal v i) m) (i + 1) + = alteredUDFM i (M.alterLookup alterf (getKey u) m) where - tf (TaggedVal new_v _) (TaggedVal _ old_i) = TaggedVal new_v old_i + alterf Nothing = Just $! TaggedVal v i + alterf (Just (TaggedVal _ old_i)) = Just $! TaggedVal v old_i -- Keep the old tag, but insert the new value -- This means that udfmToList typically returns elements -- in the order of insertion, rather than the reverse - -- It is quite critical that the strict insertWith is used as otherwise - -- the combination function 'tf' is not forced and both old values are retained - -- in the map. - addToUDFM_C_Directly :: (elt -> elt -> elt) -- old -> new -> result -> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt addToUDFM_C_Directly f (UDFM m i) u v - = UDFM (MS.insertWith tf (getKey u) (TaggedVal v i) m) (i + 1) + = alteredUDFM i (M.alterLookup alterf (getKey u) m) where - tf (TaggedVal new_v _) (TaggedVal old_v old_i) - = TaggedVal (f old_v new_v) old_i - -- Flip the arguments, because M.insertWith uses (new->old->result) - -- but f needs (old->new->result) + alterf Nothing = Just $! TaggedVal v i + alterf (Just (TaggedVal old_v old_i)) = Just $! TaggedVal (f old_v v) old_i -- Like addToUDFM_Directly, keep the old tag addToUDFM_C @@ -453,7 +463,7 @@ adjustUDFM_Directly f (UDFM m i) k = UDFM (M.adjust (fmap f) (getKey k) m) i -- more efficient. Updating an existing key keeps its position in the -- deterministic iteration order. -- --- 'alterUDFM' is non-strict in @k@. +-- 'alterUDFM' is strict in @k@. alterUDFM :: Uniquable key => (Maybe elt -> Maybe elt) -- ^ How to adjust the element @@ -461,12 +471,12 @@ alterUDFM -> key -- ^ @key@ of the element to adjust -> UniqDFM key elt -- ^ New element at @key@ and modified 'UniqDFM' alterUDFM f (UDFM m i) k = - UDFM (M.alter alterf (getKey $ getUnique k) m) (i + 1) + alteredUDFM i (M.alterLookup alterf (getKey $ getUnique k) m) where alterf Nothing = inject i $ f Nothing alterf (Just (TaggedVal v old_i)) = inject old_i $ f (Just v) inject _ Nothing = Nothing - inject tag (Just v) = Just $ TaggedVal v tag + inject tag (Just v) = Just $! TaggedVal v tag -- | The expression (@'upsertUDFM' f map k@) updates the value at @k@ or inserts -- a new value if @k@ is absent. @@ -480,10 +490,10 @@ upsertUDFM -> key -- ^ @key@ of the element to adjust -> UniqDFM key elt -- ^ New element at @key@ and modified 'UniqDFM' upsertUDFM f (UDFM m i) k = - UDFM (MS.upsert upsertf (getKey $ getUnique k) m) (i + 1) + alteredUDFM i (M.alterLookup upsertf (getKey $ getUnique k) m) where - upsertf Nothing = TaggedVal (f Nothing) i - upsertf (Just (TaggedVal v old_i)) = TaggedVal (f (Just v)) old_i + upsertf Nothing = Just $! TaggedVal (f Nothing) i + upsertf (Just (TaggedVal v old_i)) = Just $! TaggedVal (f (Just v)) old_i -- | The expression (@'alterUDFM_L' f map k@) alters value @x@ at @k@, or absence -- thereof and returns the new element at @k@ if there is any. @@ -500,16 +510,14 @@ alterUDFM_L -> key -- ^ @key@ of the element to adjust -> (Maybe elt, UniqDFM key elt) -- ^ New element at @key@ and modified 'UniqDFM' alterUDFM_L f (UDFM m i) k = - let - (mElt, udfm) = M.alterLookup alterf (getKey $ getUnique k) m - in - (fmap taggedFst mElt, UDFM udfm (i + 1)) + case M.alterLookup alterf (getKey $ getUnique k) m of + res@(mElt, _) -> (fmap taggedFst mElt, alteredUDFM i res) where - alterf :: Maybe (TaggedVal elt) -> (Maybe (TaggedVal elt)) + alterf :: Maybe (TaggedVal elt) -> Maybe (TaggedVal elt) alterf Nothing = inject i $ f Nothing alterf (Just (TaggedVal v old_i)) = inject old_i $ f (Just v) inject _ Nothing = Nothing - inject tag (Just v) = Just $ TaggedVal v tag + inject tag (Just v) = Just $! TaggedVal v tag -- | Map a function over every value in a UniqDFM mapUDFM :: (elt1 -> elt2) -> UniqDFM key elt1 -> UniqDFM key elt2 View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/9218701cda22ed3f6fd91c7d556dd80... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/9218701cda22ed3f6fd91c7d556dd80... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help