Zubin pushed to branch wip/uniquedfm-todo at Glasgow Haskell Compiler / GHC

Commits:

1 changed file:

Changes:

  • compiler/GHC/Types/Unique/DFM.hs
    ... ... @@ -82,56 +82,66 @@ import GHC.Types.Unique.FM (UniqFM, nonDetUFMToList, ufmToIntMap, unsafeIntMapTo
    82 82 
     import Unsafe.Coerce
    83 83 
     import qualified GHC.Data.Word64Set as W
    84 84
    85 
    --- Note [Deterministic UniqFM]
    86 
    --- ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    87 
    --- A @UniqDFM@ is just like @UniqFM@ with the following additional
    88 
    --- property: the function `udfmToList` returns the elements in some
    89 
    --- deterministic order not depending on the Unique key for those elements.
    90 
    ---
    91 
    --- If the client of the map performs operations on the map in deterministic
    92 
    --- order then `udfmToList` returns them in deterministic order.
    93 
    ---
    94 
    --- The order does not depend on how existing entries were
    95 
    --- updated. Updating an existing entry keeps it original position in the order
    96 
    --- This means `alterUDFM` consistent with `addToUDFM` and `adjustUDFM`,
    97 
    --- so that for example `alterUDFM id k = id` and `alterUDFM (fmap f) k = adjustUDFM f k`
    98 
    ---
    99 
    --- There is an implementation cost: each element is given a serial number
    100 
    --- as it is added, and `udfmToList` sorts its result by this serial
    101 
    --- number. So you should only use `UniqDFM` if you need the deterministic
    102 
    --- property.
    103 
    ---
    104 
    --- `foldUDFM` also preserves determinism.
    105 
    ---
    106 
    --- Normal @UniqFM@ when you turn it into a list will use
    107 
    --- Data.IntMap.toList function that returns the elements in the order of
    108 
    --- the keys. The keys in @UniqFM@ are always @Uniques@, so you end up with
    109 
    --- with a list ordered by @Uniques@.
    110 
    --- The order of @Uniques@ is known to be not stable across rebuilds.
    111 
    --- See Note [Unique Determinism] in GHC.Types.Unique.
    112 
    ---
    113 
    ---
    114 
    --- There's more than one way to implement this. The implementation here tags
    115 
    --- every value with the insertion time that can later be used to sort the
    116 
    --- values when asked to convert to a list.
    117 
    ---
    118 
    --- Updating an existing key keeps the old tag. This keeps the order stable for
    119 
    --- maps whose entries are updated many times. The instance environments are
    120 
    --- the main example: inserting an instance updates the entry of its class in a
    121 
    --- DNameEnv, and when updates moved keys to the end the order of instances shown
    122 
    --- by :info depended on the order in which interfaces happened to be loaded
    123 
    --- (#27532). Now a class keeps its place once its first instance is added, so
    124 
    --- loading further interfaces cannot change the order.
    125 
    ---
    126 
    --- An alternative would be to have
    127 
    ---
    128 
    ---   data UniqDFM ele = UDFM (M.IntMap ele) [ele]
    129 
    ---
    130 
    --- where the list determines the order. This makes deletion tricky as we'd
    131 
    --- only accumulate elements in that list, but makes merging easier as you
    132 
    --- can just merge both structures independently.
    133 
    --- Deletion can probably be done in amortized fashion when the size of the
    134 
    --- list is twice the size of the set.
    85 
    +{- Note [Deterministic UniqFM]
    86 
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    87 
    +When you enumerate the elements of a normal `UniqFM`, using `nonDetUFMToList`, you
    88 
    +get the elements back in the order of their `Unique` keys.  This can mess up deterministic
    89 
    +compilation; see Note [Unique Determinism] in GHC.Types.Unique.
    90 
    +
    91 
    +This module defines /deterministic/ unique-keyed finite maps, `UniqDFM`, which have
    92 
    +the following property:
    93 
    +
    94 
    +  (UniqDFM property) The function `udfmToList` returns the elements in the order
    95 
    +  in which they were inserted; that is, in order of their "insertion date".
    96 
    +
    97 
    +  In particular, the order of elements does not depend on:
    98 
    +     * The Unique key for those elements
    99 
    +     * How existing entries are updated with `alterUDFM`; updating an element does not change
    100 
    +       its insertion date.
    101 
    +
    102 
    +  If an element is completely deleted and then again inserted, the latter insertion counts as its
    103 
    +  insertion date.
    104 
    +
    105 
    +  When we take (m1 `plusUDFM` m2), the insertion dates of elements in the smaller map are
    106 
    +  adjusted to be after all those in the bigger map.
    107 
    +
    108 
    +Updating an existing entry keeps its original position in the order.
    109 
    +This means `alterUDFM` is consistent with `addToUDFM` and `adjustUDFM`,
    110 
    +so that for example `alterUDFM id k = id` and `alterUDFM (fmap f) k = adjustUDFM f k`
    111 
    +
    112 
    +It also keeps the order stable for
    113 
    +maps whose entries are updated many times. The instance environments are
    114 
    +the main example: inserting an instance updates the entry of its class in a
    115 
    +DNameEnv, and when updates moved keys to the end the order of instances shown
    116 
    +by :info depended on the order in which interfaces happened to be loaded
    117 
    +(#27532). Now a class keeps its place once its first instance is added, so
    118 
    +loading further interfaces cannot change the order.
    119 
    +
    120 
    +`foldUDFM` also preserves determinism:
    121 
    +
    122 
    +  foldUDFM k z m  =  foldr k z (eltsUDFM m)
    123 
    +
    124 
    +Implementation
    125 
    +~~~~~~~~~~~~~~
    126 
    +There's more than one way to implement this. The implementation here tags
    127 
    +every value with the insertion time that can later be used to sort the
    128 
    +values when asked to convert to a list.
    129 
    +
    130 
    +There is an implementation cost: each element is given a serial number
    131 
    +as it is added, and `udfmToList` sorts its result by this serial
    132 
    +number. So you should only use `UniqDFM` if you need the deterministic
    133 
    +property.
    134 
    +
    135 
    +An alternative would be to have
    136 
    +
    137 
    +  data UniqDFM ele = UDFM (M.IntMap ele) [ele]
    138 
    +
    139 
    +where the list determines the order. This makes deletion tricky as we'd
    140 
    +only accumulate elements in that list, but makes merging easier as you
    141 
    +can just merge both structures independently.
    142 
    +Deletion can probably be done in amortized fashion when the size of the
    143 
    +list is twice the size of the set.
    144 
    +-}
    135 145
    136 146 
     -- | A type of values tagged with insertion time
    137 147 
     data TaggedVal val =
    ... ... @@ -187,34 +197,36 @@ unitUDFM k v = UDFM (M.singleton (getKey $ getUnique k) (TaggedVal v 0)) 1
    187 197 
     addToUDFM :: Uniquable key => UniqDFM key elt -> key -> elt  -> UniqDFM key elt
    188 198 
     addToUDFM m k v = addToUDFM_Directly m (getUnique k) v
    189 199
    200 
    +alteredUDFM :: Int -> (Maybe (TaggedVal elt), M.Word64Map (TaggedVal elt)) -> UniqDFM key elt
    201 
    +alteredUDFM i (new, m) = case new of
    202 
    +  Just (TaggedVal _ tag) | tag == i -> UDFM m (i + 1)
    203 
    +  _                                 -> UDFM m i
    204 
    +
    190 205 
     -- A new key goes to the right of existing ones
    191 206 
     -- Overwriting an existing key keeps its position in the iteration order
    192 207 
     addToUDFM_Directly :: UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
    193 208 
     addToUDFM_Directly (UDFM m i) u v
    194 
    -  = UDFM (MS.insertWith tf (getKey u) (TaggedVal v i) m) (i + 1)
    209 
    +  = alteredUDFM i (M.alterLookup alterf (getKey u) m)
    195 210 
       where
    196 
    -    tf (TaggedVal new_v _) (TaggedVal _ old_i) = TaggedVal new_v old_i
    211 
    +    alterf Nothing = Just $ TaggedVal v i
    212 
    +    alterf (Just (TaggedVal _ old_i)) = Just $ TaggedVal v old_i
    197 213 
           -- Keep the old tag, but insert the new value
    198 214 
           -- This means that udfmToList typically returns elements
    199 215 
           -- in the order of insertion, rather than the reverse
    200 216
    201 
    -      -- It is quite critical that the strict insertWith is used as otherwise
    202 
    -      -- the combination function 'tf' is not forced and both old values are retained
    203 
    -      -- in the map.
    204 
    -
    205 217 
     addToUDFM_C_Directly
    206 218 
       :: (elt -> elt -> elt)   -- old -> new -> result
    207 219 
       -> UniqDFM key elt
    208 220 
       -> Unique -> elt
    209 221 
       -> UniqDFM key elt
    210 222 
     addToUDFM_C_Directly f (UDFM m i) u v
    211 
    -  = UDFM (MS.insertWith tf (getKey u) (TaggedVal v i) m) (i + 1)
    223 
    +  = alteredUDFM i (M.alterLookup alterf (getKey u) m)
    212 224 
         where
    213 
    -      tf (TaggedVal new_v _) (TaggedVal old_v old_i)
    214 
    -         = TaggedVal (f old_v new_v) old_i
    215 
    -          -- Flip the arguments, because M.insertWith uses  (new->old->result)
    216 
    -          --                         but f            needs (old->new->result)
    225 
    +      alterf Nothing = Just $ TaggedVal v i
    226 
    +      alterf (Just (TaggedVal old_v old_i)) = Just $ TaggedVal (f old_v v) old_i
    217 227 
               -- Like addToUDFM_Directly, keep the old tag
    228 
    +          -- The strict val field of TaggedVal forces (f old_v v), so the map
    229 
    +          -- does not retain a thunk holding both values.
    218 230
    219 231 
     addToUDFM_C
    220 232 
       :: Uniquable key => (elt -> elt -> elt) -- old -> new -> result
    ... ... @@ -452,8 +464,6 @@ adjustUDFM_Directly f (UDFM m i) k = UDFM (M.adjust (fmap f) (getKey k) m) i
    452 464 
     -- UniqDFM. Use addToUDFM, delFromUDFM or adjustUDFM when possible, they are
    453 465 
     -- more efficient. Updating an existing key keeps its position in the
    454 466 
     -- deterministic iteration order.
    455 
    ---
    456 
    --- 'alterUDFM' is non-strict in @k@.
    457 467 
     alterUDFM
    458 468 
       :: Uniquable key
    459 469 
       => (Maybe elt -> Maybe elt)  -- ^ How to adjust the element
    ... ... @@ -461,7 +471,7 @@ alterUDFM
    461 471 
       -> key                       -- ^ @key@ of the element to adjust
    462 472 
       -> UniqDFM key elt           -- ^ New element at @key@ and modified 'UniqDFM'
    463 473 
     alterUDFM f (UDFM m i) k =
    464 
    -  UDFM (M.alter alterf (getKey $ getUnique k) m) (i + 1)
    474 
    +  alteredUDFM i (M.alterLookup alterf (getKey $ getUnique k) m)
    465 475 
       where
    466 476 
       alterf Nothing = inject i $ f Nothing
    467 477 
       alterf (Just (TaggedVal v old_i)) = inject old_i $ f (Just v)
    ... ... @@ -480,10 +490,10 @@ upsertUDFM
    480 490 
       -> key                 -- ^ @key@ of the element to adjust
    481 491 
       -> UniqDFM key elt     -- ^ New element at @key@ and modified 'UniqDFM'
    482 492 
     upsertUDFM f (UDFM m i) k =
    483 
    -  UDFM (MS.upsert upsertf (getKey $ getUnique k) m) (i + 1)
    493 
    +  alteredUDFM i (M.alterLookup upsertf (getKey $ getUnique k) m)
    484 494 
       where
    485 
    -    upsertf Nothing = TaggedVal (f Nothing) i
    486 
    -    upsertf (Just (TaggedVal v old_i)) = TaggedVal (f (Just v)) old_i
    495 
    +    upsertf Nothing = Just $ TaggedVal (f Nothing) i
    496 
    +    upsertf (Just (TaggedVal v old_i)) = Just $ TaggedVal (f (Just v)) old_i
    487 497
    488 498 
     -- | The expression (@'alterUDFM_L' f map k@) alters value @x@ at @k@, or absence
    489 499 
     -- thereof and returns the new element at @k@ if there is any.
    ... ... @@ -491,8 +501,6 @@ upsertUDFM f (UDFM m i) k =
    491 501 
     -- UniqDFM. Use addToUDFM, delFromUDFM or adjustUDFM when possible, they are
    492 502 
     -- more efficient. Updating an existing key keeps its position in the
    493 503 
     -- deterministic iteration order.
    494 
    ---
    495 
    --- Note, 'alterUDFM_L' is strict in @k@.
    496 504 
     alterUDFM_L
    497 505 
       :: forall key elt . Uniquable key
    498 506 
       => (Maybe elt -> Maybe elt)      -- ^ How to adjust the element
    ... ... @@ -500,12 +508,10 @@ alterUDFM_L
    500 508 
       -> key                           -- ^ @key@ of the element to adjust
    501 509 
       -> (Maybe elt, UniqDFM key elt)  -- ^ New element at @key@ and modified 'UniqDFM'
    502 510 
     alterUDFM_L f (UDFM m i) k =
    503 
    -  let
    504 
    -    (mElt, udfm) = M.alterLookup alterf (getKey $ getUnique k) m
    505 
    -  in
    506 
    -    (fmap taggedFst mElt, UDFM udfm (i + 1))
    511 
    +  case M.alterLookup alterf (getKey $ getUnique k) m of
    512 
    +    res@(mElt, _) -> (fmap taggedFst mElt, alteredUDFM i res)
    507 513 
       where
    508 
    -  alterf :: Maybe (TaggedVal elt) -> (Maybe (TaggedVal elt))
    514 
    +  alterf :: Maybe (TaggedVal elt) -> Maybe (TaggedVal elt)
    509 515 
       alterf Nothing = inject i $ f Nothing
    510 516 
       alterf (Just (TaggedVal v old_i)) = inject old_i $ f (Just v)
    511 517 
       inject _ Nothing = Nothing

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications · Help Notification message regarding https://gitlab.haskell.org/ghc/ghc/-/compare/1d03e25adf64b62eae46620e21fc98fa0bdafd24...9218701cda22ed3f6fd91c7d556dd80c8bf082cc at 1785479621