{-
(c) Bartosz Nitka, Facebook, 2015

UniqDFM: Specialised deterministic finite maps, for things with @Uniques@.

Basically, the things need to be in class @Uniquable@, and we use the
@getUnique@ method to grab their @Uniques@.

This is very similar to @UniqFM@, the major difference being that the order of
folding is not dependent on @Unique@ ordering, giving determinism.
Currently the ordering is determined by insertion order.

See Note [Unique Determinism] in GHC.Types.Unique for explanation why @Unique@ ordering
is not deterministic.
-}

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# OPTIONS_GHC -Wall #-}

module GHC.Types.Unique.DFM (
        -- * Unique-keyed deterministic mappings
        UniqDFM,       -- abstract type

        -- ** Manipulating those mappings
        emptyUDFM,
        unitUDFM,
        addToUDFM,
        addToUDFM_C,
        addToUDFM_C_Directly,
        addToUDFM_Directly,
        addListToUDFM,
        delFromUDFM,
        delListFromUDFM,
        adjustUDFM,
        adjustUDFM_Directly,
        alterUDFM,
        mapUDFM,
        mapMaybeUDFM,
        mapMUDFM,
        plusUDFM,
        plusUDFM_C, plusUDFM_CK,
        lookupUDFM, lookupUDFM_Directly,
        elemUDFM,
        foldUDFM, foldWithKeyUDFM,
        eltsUDFM,
        filterUDFM, filterUDFM_Directly,
        isNullUDFM,
        sizeUDFM,
        intersectUDFM, udfmIntersectUFM,
        disjointUDFM, disjointUdfmUfm,
        equalKeysUDFM,
        minusUDFM,
        listToUDFM, listToUDFM_Directly,
        listToUDFM_C_Directly,
        udfmMinusUFM, ufmMinusUDFM,
        partitionUDFM,
        udfmRestrictKeys,
        udfmRestrictKeysSet,
        anyUDFM, allUDFM,
        pprUniqDFM, pprUDFM,

        udfmToList,
        udfmToUfm,
        nonDetStrictFoldUDFM,
        unsafeCastUDFMKey,
        alwaysUnsafeUfmToUdfm,
    ) where

import GHC.Prelude

import GHC.Types.Unique ( Uniquable(..), Unique, getKey, mkUniqueGrimily )
import GHC.Utils.Outputable

import qualified GHC.Data.Word64Map.Strict as MS
import qualified GHC.Data.Word64Map as M
import Data.Data
import Data.Functor.Classes (Eq1 (..))
import Data.List (sortBy)
import Data.Function (on)
import GHC.Types.Unique.FM (UniqFM, nonDetUFMToList, ufmToIntMap, unsafeIntMapToUFM)
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.
--
-- 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.
--
-- 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 =
  TaggedVal
    !val
    {-# UNPACK #-} !Int -- ^ insertion time
  deriving stock (Typeable (TaggedVal val)
Typeable (TaggedVal val) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> TaggedVal val -> c (TaggedVal val))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (TaggedVal val))
-> (TaggedVal val -> Constr)
-> (TaggedVal val -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (TaggedVal val)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (TaggedVal val)))
-> ((forall b. Data b => b -> b) -> TaggedVal val -> TaggedVal val)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r)
-> (forall u. (forall d. Data d => d -> u) -> TaggedVal val -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> TaggedVal val -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> TaggedVal val -> m (TaggedVal val))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> TaggedVal val -> m (TaggedVal val))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> TaggedVal val -> m (TaggedVal val))
-> Data (TaggedVal val)
TaggedVal val -> Constr
TaggedVal val -> DataType
(forall b. Data b => b -> b) -> TaggedVal val -> TaggedVal val
forall val. Data val => Typeable (TaggedVal val)
forall val. Data val => TaggedVal val -> Constr
forall val. Data val => TaggedVal val -> DataType
forall val.
Data val =>
(forall b. Data b => b -> b) -> TaggedVal val -> TaggedVal val
forall val u.
Data val =>
Int -> (forall d. Data d => d -> u) -> TaggedVal val -> u
forall val u.
Data val =>
(forall d. Data d => d -> u) -> TaggedVal val -> [u]
forall val r r'.
Data val =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
forall val r r'.
Data val =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
forall val (m :: * -> *).
(Data val, Monad m) =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
forall val (m :: * -> *).
(Data val, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
forall val (c :: * -> *).
Data val =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (TaggedVal val)
forall val (c :: * -> *).
Data val =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> TaggedVal val -> c (TaggedVal val)
forall val (t :: * -> *) (c :: * -> *).
(Data val, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (TaggedVal val))
forall val (t :: * -> * -> *) (c :: * -> *).
(Data val, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (TaggedVal val))
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> TaggedVal val -> u
forall u. (forall d. Data d => d -> u) -> TaggedVal val -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (TaggedVal val)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> TaggedVal val -> c (TaggedVal val)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (TaggedVal val))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (TaggedVal val))
$cgfoldl :: forall val (c :: * -> *).
Data val =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> TaggedVal val -> c (TaggedVal val)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> TaggedVal val -> c (TaggedVal val)
$cgunfold :: forall val (c :: * -> *).
Data val =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (TaggedVal val)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (TaggedVal val)
$ctoConstr :: forall val. Data val => TaggedVal val -> Constr
toConstr :: TaggedVal val -> Constr
$cdataTypeOf :: forall val. Data val => TaggedVal val -> DataType
dataTypeOf :: TaggedVal val -> DataType
$cdataCast1 :: forall val (t :: * -> *) (c :: * -> *).
(Data val, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (TaggedVal val))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (TaggedVal val))
$cdataCast2 :: forall val (t :: * -> * -> *) (c :: * -> *).
(Data val, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (TaggedVal val))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (TaggedVal val))
$cgmapT :: forall val.
Data val =>
(forall b. Data b => b -> b) -> TaggedVal val -> TaggedVal val
gmapT :: (forall b. Data b => b -> b) -> TaggedVal val -> TaggedVal val
$cgmapQl :: forall val r r'.
Data val =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
$cgmapQr :: forall val r r'.
Data val =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> TaggedVal val -> r
$cgmapQ :: forall val u.
Data val =>
(forall d. Data d => d -> u) -> TaggedVal val -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> TaggedVal val -> [u]
$cgmapQi :: forall val u.
Data val =>
Int -> (forall d. Data d => d -> u) -> TaggedVal val -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> TaggedVal val -> u
$cgmapM :: forall val (m :: * -> *).
(Data val, Monad m) =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
$cgmapMp :: forall val (m :: * -> *).
(Data val, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
$cgmapMo :: forall val (m :: * -> *).
(Data val, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> TaggedVal val -> m (TaggedVal val)
Data, (forall a b. (a -> b) -> TaggedVal a -> TaggedVal b)
-> (forall a b. a -> TaggedVal b -> TaggedVal a)
-> Functor TaggedVal
forall a b. a -> TaggedVal b -> TaggedVal a
forall a b. (a -> b) -> TaggedVal a -> TaggedVal b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> TaggedVal a -> TaggedVal b
fmap :: forall a b. (a -> b) -> TaggedVal a -> TaggedVal b
$c<$ :: forall a b. a -> TaggedVal b -> TaggedVal a
<$ :: forall a b. a -> TaggedVal b -> TaggedVal a
Functor, (forall m. Monoid m => TaggedVal m -> m)
-> (forall m a. Monoid m => (a -> m) -> TaggedVal a -> m)
-> (forall m a. Monoid m => (a -> m) -> TaggedVal a -> m)
-> (forall a b. (a -> b -> b) -> b -> TaggedVal a -> b)
-> (forall a b. (a -> b -> b) -> b -> TaggedVal a -> b)
-> (forall b a. (b -> a -> b) -> b -> TaggedVal a -> b)
-> (forall b a. (b -> a -> b) -> b -> TaggedVal a -> b)
-> (forall a. (a -> a -> a) -> TaggedVal a -> a)
-> (forall a. (a -> a -> a) -> TaggedVal a -> a)
-> (forall a. TaggedVal a -> [a])
-> (forall a. TaggedVal a -> Bool)
-> (forall a. TaggedVal a -> Int)
-> (forall a. Eq a => a -> TaggedVal a -> Bool)
-> (forall a. Ord a => TaggedVal a -> a)
-> (forall a. Ord a => TaggedVal a -> a)
-> (forall a. Num a => TaggedVal a -> a)
-> (forall a. Num a => TaggedVal a -> a)
-> Foldable TaggedVal
forall a. Eq a => a -> TaggedVal a -> Bool
forall a. Num a => TaggedVal a -> a
forall a. Ord a => TaggedVal a -> a
forall m. Monoid m => TaggedVal m -> m
forall a. TaggedVal a -> Bool
forall a. TaggedVal a -> Int
forall a. TaggedVal a -> [a]
forall a. (a -> a -> a) -> TaggedVal a -> a
forall m a. Monoid m => (a -> m) -> TaggedVal a -> m
forall b a. (b -> a -> b) -> b -> TaggedVal a -> b
forall a b. (a -> b -> b) -> b -> TaggedVal a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall m. Monoid m => TaggedVal m -> m
fold :: forall m. Monoid m => TaggedVal m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> TaggedVal a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> TaggedVal a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> TaggedVal a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> TaggedVal a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> TaggedVal a -> b
foldr :: forall a b. (a -> b -> b) -> b -> TaggedVal a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> TaggedVal a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> TaggedVal a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> TaggedVal a -> b
foldl :: forall b a. (b -> a -> b) -> b -> TaggedVal a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> TaggedVal a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> TaggedVal a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> TaggedVal a -> a
foldr1 :: forall a. (a -> a -> a) -> TaggedVal a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> TaggedVal a -> a
foldl1 :: forall a. (a -> a -> a) -> TaggedVal a -> a
$ctoList :: forall a. TaggedVal a -> [a]
toList :: forall a. TaggedVal a -> [a]
$cnull :: forall a. TaggedVal a -> Bool
null :: forall a. TaggedVal a -> Bool
$clength :: forall a. TaggedVal a -> Int
length :: forall a. TaggedVal a -> Int
$celem :: forall a. Eq a => a -> TaggedVal a -> Bool
elem :: forall a. Eq a => a -> TaggedVal a -> Bool
$cmaximum :: forall a. Ord a => TaggedVal a -> a
maximum :: forall a. Ord a => TaggedVal a -> a
$cminimum :: forall a. Ord a => TaggedVal a -> a
minimum :: forall a. Ord a => TaggedVal a -> a
$csum :: forall a. Num a => TaggedVal a -> a
sum :: forall a. Num a => TaggedVal a -> a
$cproduct :: forall a. Num a => TaggedVal a -> a
product :: forall a. Num a => TaggedVal a -> a
Foldable, Functor TaggedVal
Foldable TaggedVal
(Functor TaggedVal, Foldable TaggedVal) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> TaggedVal a -> f (TaggedVal b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    TaggedVal (f a) -> f (TaggedVal a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> TaggedVal a -> m (TaggedVal b))
-> (forall (m :: * -> *) a.
    Monad m =>
    TaggedVal (m a) -> m (TaggedVal a))
-> Traversable TaggedVal
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
TaggedVal (m a) -> m (TaggedVal a)
forall (f :: * -> *) a.
Applicative f =>
TaggedVal (f a) -> f (TaggedVal a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> TaggedVal a -> m (TaggedVal b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TaggedVal a -> f (TaggedVal b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TaggedVal a -> f (TaggedVal b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TaggedVal a -> f (TaggedVal b)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
TaggedVal (f a) -> f (TaggedVal a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
TaggedVal (f a) -> f (TaggedVal a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> TaggedVal a -> m (TaggedVal b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> TaggedVal a -> m (TaggedVal b)
$csequence :: forall (m :: * -> *) a.
Monad m =>
TaggedVal (m a) -> m (TaggedVal a)
sequence :: forall (m :: * -> *) a.
Monad m =>
TaggedVal (m a) -> m (TaggedVal a)
Traversable)

taggedFst :: TaggedVal val -> val
taggedFst :: forall val. TaggedVal val -> val
taggedFst (TaggedVal val
v Int
_) = val
v

taggedSnd :: TaggedVal val -> Int
taggedSnd :: forall a. TaggedVal a -> Int
taggedSnd (TaggedVal val
_ Int
i) = Int
i

instance Eq val => Eq (TaggedVal val) where
  (TaggedVal val
v1 Int
_) == :: TaggedVal val -> TaggedVal val -> Bool
== (TaggedVal val
v2 Int
_) = val
v1 val -> val -> Bool
forall a. Eq a => a -> a -> Bool
== val
v2

-- | Type of unique deterministic finite maps
--
-- The key is just here to keep us honest. It's always safe
-- to use a single type as key.
-- If two types don't overlap in their uniques it's also safe
-- to index the same map at multiple key types. But this is
-- very much discouraged.
data UniqDFM key ele =
  UDFM
    !(M.Word64Map (TaggedVal ele)) -- A map where keys are Unique's values and
                                -- values are tagged with insertion time.
                                -- The invariant is that all the tags will
                                -- be distinct within a single map
    {-# UNPACK #-} !Int         -- Upper bound on the values' insertion
                                -- time. See Note [Overflow on plusUDFM]
  deriving (Typeable (UniqDFM key ele)
Typeable (UniqDFM key ele) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> UniqDFM key ele -> c (UniqDFM key ele))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (UniqDFM key ele))
-> (UniqDFM key ele -> Constr)
-> (UniqDFM key ele -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (UniqDFM key ele)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (UniqDFM key ele)))
-> ((forall b. Data b => b -> b)
    -> UniqDFM key ele -> UniqDFM key ele)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r)
-> (forall u.
    (forall d. Data d => d -> u) -> UniqDFM key ele -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> UniqDFM key ele -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> UniqDFM key ele -> m (UniqDFM key ele))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> UniqDFM key ele -> m (UniqDFM key ele))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> UniqDFM key ele -> m (UniqDFM key ele))
-> Data (UniqDFM key ele)
UniqDFM key ele -> Constr
UniqDFM key ele -> DataType
(forall b. Data b => b -> b) -> UniqDFM key ele -> UniqDFM key ele
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u.
Int -> (forall d. Data d => d -> u) -> UniqDFM key ele -> u
forall u. (forall d. Data d => d -> u) -> UniqDFM key ele -> [u]
forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
Typeable (UniqDFM key ele)
forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
UniqDFM key ele -> Constr
forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
UniqDFM key ele -> DataType
forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
(forall b. Data b => b -> b) -> UniqDFM key ele -> UniqDFM key ele
forall k (key :: k) ele u.
(Typeable key, Typeable k, Data ele) =>
Int -> (forall d. Data d => d -> u) -> UniqDFM key ele -> u
forall k (key :: k) ele u.
(Typeable key, Typeable k, Data ele) =>
(forall d. Data d => d -> u) -> UniqDFM key ele -> [u]
forall k (key :: k) ele r r'.
(Typeable key, Typeable k, Data ele) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
forall k (key :: k) ele r r'.
(Typeable key, Typeable k, Data ele) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
forall k (key :: k) ele (m :: * -> *).
(Typeable key, Typeable k, Data ele, Monad m) =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
forall k (key :: k) ele (m :: * -> *).
(Typeable key, Typeable k, Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
forall k (key :: k) ele (c :: * -> *).
(Typeable key, Typeable k, Data ele) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqDFM key ele)
forall k (key :: k) ele (c :: * -> *).
(Typeable key, Typeable k, Data ele) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqDFM key ele -> c (UniqDFM key ele)
forall k (key :: k) ele (t :: * -> *) (c :: * -> *).
(Typeable key, Typeable k, Data ele, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqDFM key ele))
forall k (key :: k) ele (t :: * -> * -> *) (c :: * -> *).
(Typeable key, Typeable k, Data ele, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqDFM key ele))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqDFM key ele)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqDFM key ele -> c (UniqDFM key ele)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqDFM key ele))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqDFM key ele))
$cgfoldl :: forall k (key :: k) ele (c :: * -> *).
(Typeable key, Typeable k, Data ele) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqDFM key ele -> c (UniqDFM key ele)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqDFM key ele -> c (UniqDFM key ele)
$cgunfold :: forall k (key :: k) ele (c :: * -> *).
(Typeable key, Typeable k, Data ele) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqDFM key ele)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqDFM key ele)
$ctoConstr :: forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
UniqDFM key ele -> Constr
toConstr :: UniqDFM key ele -> Constr
$cdataTypeOf :: forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
UniqDFM key ele -> DataType
dataTypeOf :: UniqDFM key ele -> DataType
$cdataCast1 :: forall k (key :: k) ele (t :: * -> *) (c :: * -> *).
(Typeable key, Typeable k, Data ele, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqDFM key ele))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqDFM key ele))
$cdataCast2 :: forall k (key :: k) ele (t :: * -> * -> *) (c :: * -> *).
(Typeable key, Typeable k, Data ele, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqDFM key ele))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqDFM key ele))
$cgmapT :: forall k (key :: k) ele.
(Typeable key, Typeable k, Data ele) =>
(forall b. Data b => b -> b) -> UniqDFM key ele -> UniqDFM key ele
gmapT :: (forall b. Data b => b -> b) -> UniqDFM key ele -> UniqDFM key ele
$cgmapQl :: forall k (key :: k) ele r r'.
(Typeable key, Typeable k, Data ele) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
$cgmapQr :: forall k (key :: k) ele r r'.
(Typeable key, Typeable k, Data ele) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqDFM key ele -> r
$cgmapQ :: forall k (key :: k) ele u.
(Typeable key, Typeable k, Data ele) =>
(forall d. Data d => d -> u) -> UniqDFM key ele -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> UniqDFM key ele -> [u]
$cgmapQi :: forall k (key :: k) ele u.
(Typeable key, Typeable k, Data ele) =>
Int -> (forall d. Data d => d -> u) -> UniqDFM key ele -> u
gmapQi :: forall u.
Int -> (forall d. Data d => d -> u) -> UniqDFM key ele -> u
$cgmapM :: forall k (key :: k) ele (m :: * -> *).
(Typeable key, Typeable k, Data ele, Monad m) =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
$cgmapMp :: forall k (key :: k) ele (m :: * -> *).
(Typeable key, Typeable k, Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
$cgmapMo :: forall k (key :: k) ele (m :: * -> *).
(Typeable key, Typeable k, Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> UniqDFM key ele -> m (UniqDFM key ele)
Data, (forall a b. (a -> b) -> UniqDFM key a -> UniqDFM key b)
-> (forall a b. a -> UniqDFM key b -> UniqDFM key a)
-> Functor (UniqDFM key)
forall k (key :: k) a b. a -> UniqDFM key b -> UniqDFM key a
forall k (key :: k) a b. (a -> b) -> UniqDFM key a -> UniqDFM key b
forall a b. a -> UniqDFM key b -> UniqDFM key a
forall a b. (a -> b) -> UniqDFM key a -> UniqDFM key b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall k (key :: k) a b. (a -> b) -> UniqDFM key a -> UniqDFM key b
fmap :: forall a b. (a -> b) -> UniqDFM key a -> UniqDFM key b
$c<$ :: forall k (key :: k) a b. a -> UniqDFM key b -> UniqDFM key a
<$ :: forall a b. a -> UniqDFM key b -> UniqDFM key a
Functor)

-- | Deterministic, in O(n log n).
instance Foldable (UniqDFM key) where
  foldr :: forall a b. (a -> b -> b) -> b -> UniqDFM key a -> b
foldr = (a -> b -> b) -> b -> UniqDFM key a -> b
forall {k} elt a (key :: k).
(elt -> a -> a) -> a -> UniqDFM key elt -> a
foldUDFM

-- | Deterministic, in O(n log n).
instance Traversable (UniqDFM key) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> UniqDFM key a -> f (UniqDFM key b)
traverse a -> f b
f = ([(Unique, b)] -> UniqDFM key b)
-> f [(Unique, b)] -> f (UniqDFM key b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(Unique, b)] -> UniqDFM key b
forall {k} elt (key :: k). [(Unique, elt)] -> UniqDFM key elt
listToUDFM_Directly
             (f [(Unique, b)] -> f (UniqDFM key b))
-> (UniqDFM key a -> f [(Unique, b)])
-> UniqDFM key a
-> f (UniqDFM key b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Unique, a) -> f (Unique, b)) -> [(Unique, a)] -> f [(Unique, b)]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse (\(Unique
u,a
a) -> (Unique
u,) (b -> (Unique, b)) -> f b -> f (Unique, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a)
             ([(Unique, a)] -> f [(Unique, b)])
-> (UniqDFM key a -> [(Unique, a)])
-> UniqDFM key a
-> f [(Unique, b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqDFM key a -> [(Unique, a)]
forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList

emptyUDFM :: UniqDFM key elt
emptyUDFM :: forall {k} (key :: k) elt. UniqDFM key elt
emptyUDFM = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM Word64Map (TaggedVal elt)
forall a. Word64Map a
M.empty Int
0

unitUDFM :: Uniquable key => key -> elt -> UniqDFM key elt
unitUDFM :: forall key elt. Uniquable key => key -> elt -> UniqDFM key elt
unitUDFM key
k elt
v = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Key -> TaggedVal elt -> Word64Map (TaggedVal elt)
forall a. Key -> a -> Word64Map a
M.singleton (Unique -> Key
getKey (Unique -> Key) -> Unique -> Key
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) (elt -> Int -> TaggedVal elt
forall val. val -> Int -> TaggedVal val
TaggedVal elt
v Int
0)) Int
1

-- The new binding always goes to the right of existing ones
addToUDFM :: Uniquable key => UniqDFM key elt -> key -> elt  -> UniqDFM key elt
addToUDFM :: forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> elt -> UniqDFM key elt
addToUDFM UniqDFM key elt
m key
k elt
v = UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} (key :: k) elt.
UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_Directly UniqDFM key elt
m (key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v

-- The new binding always goes to the right of existing ones
addToUDFM_Directly :: UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_Directly :: forall {k} (key :: k) elt.
UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_Directly (UDFM Word64Map (TaggedVal elt)
m Int
i) Unique
u elt
v
  = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt -> TaggedVal elt -> TaggedVal elt)
-> Key
-> TaggedVal elt
-> Word64Map (TaggedVal elt)
-> Word64Map (TaggedVal elt)
forall a. (a -> a -> a) -> Key -> a -> Word64Map a -> Word64Map a
MS.insertWith TaggedVal elt -> TaggedVal elt -> TaggedVal elt
forall {val} {val}. TaggedVal val -> TaggedVal val -> TaggedVal val
tf (Unique -> Key
getKey Unique
u) (elt -> Int -> TaggedVal elt
forall val. val -> Int -> TaggedVal val
TaggedVal elt
v Int
i) Word64Map (TaggedVal elt)
m) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  where
    tf :: TaggedVal val -> TaggedVal val -> TaggedVal val
tf (TaggedVal val
new_v Int
_) (TaggedVal val
_ Int
old_i) = val -> Int -> TaggedVal val
forall val. val -> Int -> TaggedVal val
TaggedVal val
new_v Int
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 :: forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_C_Directly elt -> elt -> elt
f (UDFM Word64Map (TaggedVal elt)
m Int
i) Unique
u elt
v
  = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt -> TaggedVal elt -> TaggedVal elt)
-> Key
-> TaggedVal elt
-> Word64Map (TaggedVal elt)
-> Word64Map (TaggedVal elt)
forall a. (a -> a -> a) -> Key -> a -> Word64Map a -> Word64Map a
MS.insertWith TaggedVal elt -> TaggedVal elt -> TaggedVal elt
tf (Unique -> Key
getKey Unique
u) (elt -> Int -> TaggedVal elt
forall val. val -> Int -> TaggedVal val
TaggedVal elt
v Int
i) Word64Map (TaggedVal elt)
m) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
    where
      tf :: TaggedVal elt -> TaggedVal elt -> TaggedVal elt
tf (TaggedVal elt
new_v Int
_) (TaggedVal elt
old_v Int
old_i)
         = elt -> Int -> TaggedVal elt
forall val. val -> Int -> TaggedVal val
TaggedVal (elt -> elt -> elt
f elt
old_v elt
new_v) Int
old_i
          -- Flip the arguments, because M.insertWith uses  (new->old->result)
          --                         but f            needs (old->new->result)
          -- Like addToUDFM_Directly, keep the old tag

addToUDFM_C
  :: Uniquable key => (elt -> elt -> elt) -- old -> new -> result
  -> UniqDFM key elt -- old
  -> key -> elt -- new
  -> UniqDFM key elt -- result
addToUDFM_C :: forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqDFM key elt -> key -> elt -> UniqDFM key elt
addToUDFM_C elt -> elt -> elt
f UniqDFM key elt
m key
k elt
v = (elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_C_Directly elt -> elt -> elt
f UniqDFM key elt
m (key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v

addListToUDFM :: Uniquable key => UniqDFM key elt -> [(key,elt)] -> UniqDFM key elt
addListToUDFM :: forall key elt.
Uniquable key =>
UniqDFM key elt -> [(key, elt)] -> UniqDFM key elt
addListToUDFM = (UniqDFM key elt -> (key, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(key, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (key
k, elt
v) -> UniqDFM key elt -> key -> elt -> UniqDFM key elt
forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> elt -> UniqDFM key elt
addToUDFM UniqDFM key elt
m key
k elt
v)
{-# INLINEABLE addListToUDFM #-}

addListToUDFM_Directly :: UniqDFM key elt -> [(Unique,elt)] -> UniqDFM key elt
addListToUDFM_Directly :: forall {k} (key :: k) elt.
UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
addListToUDFM_Directly = (UniqDFM key elt -> (Unique, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (Unique
k, elt
v) -> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} (key :: k) elt.
UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_Directly UniqDFM key elt
m Unique
k elt
v)
{-# INLINEABLE addListToUDFM_Directly #-}

addListToUDFM_Directly_C
  :: (elt -> elt -> elt) -> UniqDFM key elt -> [(Unique,elt)] -> UniqDFM key elt
addListToUDFM_Directly_C :: forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
addListToUDFM_Directly_C elt -> elt -> elt
f = (UniqDFM key elt -> (Unique, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (Unique
k, elt
v) -> (elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_C_Directly elt -> elt -> elt
f UniqDFM key elt
m Unique
k elt
v)
{-# INLINEABLE addListToUDFM_Directly_C #-}

-- | Like 'addListToUDFM_Directly_C' but also passes the unique key to the combine function
addListToUDFM_Directly_CK
  :: (Unique -> elt -> elt -> elt) -> UniqDFM key elt -> [(Unique,elt)] -> UniqDFM key elt
addListToUDFM_Directly_CK :: forall {k} elt (key :: k).
(Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
addListToUDFM_Directly_CK Unique -> elt -> elt -> elt
f = (UniqDFM key elt -> (Unique, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (Unique
k, elt
v) -> (elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_C_Directly (Unique -> elt -> elt -> elt
f Unique
k) UniqDFM key elt
m Unique
k elt
v)
{-# INLINEABLE addListToUDFM_Directly_CK #-}

delFromUDFM :: Uniquable key => UniqDFM key elt -> key -> UniqDFM key elt
delFromUDFM :: forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> UniqDFM key elt
delFromUDFM (UDFM Word64Map (TaggedVal elt)
m Int
i) key
k = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Key -> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a. Key -> Word64Map a -> Word64Map a
M.delete (Unique -> Key
getKey (Unique -> Key) -> Unique -> Key
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) Word64Map (TaggedVal elt)
m) Int
i

plusUDFM_C :: (elt -> elt -> elt) -> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
plusUDFM_C :: forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
plusUDFM_C elt -> elt -> elt
f udfml :: UniqDFM key elt
udfml@(UDFM Word64Map (TaggedVal elt)
_ Int
i) udfmr :: UniqDFM key elt
udfmr@(UDFM Word64Map (TaggedVal elt)
_ Int
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
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
j = (elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_C elt -> elt -> elt
f UniqDFM key elt
udfml UniqDFM key elt
udfmr
  | Bool
otherwise = (elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_C elt -> elt -> elt
f UniqDFM key elt
udfmr UniqDFM key elt
udfml

-- | Like 'plusUDFM_C' but the combine function also receives the unique key
plusUDFM_CK :: (Unique -> elt -> elt -> elt) -> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
plusUDFM_CK :: forall {k} elt (key :: k).
(Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
plusUDFM_CK Unique -> elt -> elt -> elt
f udfml :: UniqDFM key elt
udfml@(UDFM Word64Map (TaggedVal elt)
_ Int
i) udfmr :: UniqDFM key elt
udfmr@(UDFM Word64Map (TaggedVal elt)
_ Int
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
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
j = (Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
forall {k} elt (key :: k).
(Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_CK Unique -> elt -> elt -> elt
f UniqDFM key elt
udfml UniqDFM key elt
udfmr
  | Bool
otherwise = (Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
forall {k} elt (key :: k).
(Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_CK Unique -> elt -> elt -> elt
f UniqDFM key elt
udfmr UniqDFM key elt
udfml


-- Note [Overflow on plusUDFM]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- There are multiple ways of implementing plusUDFM.
-- The main problem that needs to be solved is overlap on times of
-- insertion between different keys in two maps.
-- Consider:
--
-- A = fromList [(a, (x, 1))]
-- B = fromList [(b, (y, 1))]
--
-- If you merge them naively you end up with:
--
-- C = fromList [(a, (x, 1)), (b, (y, 1))]
--
-- Which loses information about ordering and brings us back into
-- non-deterministic world.
--
-- The solution I considered before would increment the tags on one of the
-- sets by the upper bound of the other set. The problem with this approach
-- is that you'll run out of tags for some merge patterns.
-- Say you start with A with upper bound 1, you merge A with A to get A' and
-- the upper bound becomes 2. You merge A' with A' and the upper bound
-- doubles again. After 64 merges you overflow.
-- This solution would have the same time complexity as plusUFM, namely O(n+m).
--
-- The solution I ended up with has time complexity of
-- O(m log m + m * min (n+m, W)) where m is the smaller set.
-- It simply inserts the elements of the smaller set into the larger
-- set in the order that they were inserted into the smaller set. That's
-- 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.

plusUDFM :: UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
plusUDFM :: forall {k} (key :: k) elt.
UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
plusUDFM udfml :: UniqDFM key elt
udfml@(UDFM Word64Map (TaggedVal elt)
_ Int
i) udfmr :: UniqDFM key elt
udfmr@(UDFM Word64Map (TaggedVal elt)
_ Int
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
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
j = UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
forall {k} (key :: k) elt.
UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft UniqDFM key elt
udfml UniqDFM key elt
udfmr
  | Bool
otherwise = UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
forall {k} (key :: k) elt.
UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft UniqDFM key elt
udfmr UniqDFM key elt
udfml

insertUDFMIntoLeft :: UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft :: forall {k} (key :: k) elt.
UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft UniqDFM key elt
udfml UniqDFM key elt
udfmr = UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall {k} (key :: k) elt.
UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
addListToUDFM_Directly UniqDFM key elt
udfml ([(Unique, elt)] -> UniqDFM key elt)
-> [(Unique, elt)] -> UniqDFM key elt
forall a b. (a -> b) -> a -> b
$ UniqDFM key elt -> [(Unique, elt)]
forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList UniqDFM key elt
udfmr

insertUDFMIntoLeft_C
  :: (elt -> elt -> elt) -> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_C :: forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_C elt -> elt -> elt
f UniqDFM key elt
udfml UniqDFM key elt
udfmr =
  (elt -> elt -> elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
addListToUDFM_Directly_C elt -> elt -> elt
f UniqDFM key elt
udfml ([(Unique, elt)] -> UniqDFM key elt)
-> [(Unique, elt)] -> UniqDFM key elt
forall a b. (a -> b) -> a -> b
$ UniqDFM key elt -> [(Unique, elt)]
forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList UniqDFM key elt
udfmr

-- | Like 'insertUDFMIntoLeft_C', but the merge function also receives the unique key
insertUDFMIntoLeft_CK
  :: (Unique -> elt -> elt -> elt) -> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_CK :: forall {k} elt (key :: k).
(Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
insertUDFMIntoLeft_CK Unique -> elt -> elt -> elt
f UniqDFM key elt
udfml UniqDFM key elt
udfmr =
  (Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall {k} elt (key :: k).
(Unique -> elt -> elt -> elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
addListToUDFM_Directly_CK Unique -> elt -> elt -> elt
f UniqDFM key elt
udfml ([(Unique, elt)] -> UniqDFM key elt)
-> [(Unique, elt)] -> UniqDFM key elt
forall a b. (a -> b) -> a -> b
$ UniqDFM key elt -> [(Unique, elt)]
forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList UniqDFM key elt
udfmr

lookupUDFM :: Uniquable key => UniqDFM key elt -> key -> Maybe elt
lookupUDFM :: forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> Maybe elt
lookupUDFM (UDFM Word64Map (TaggedVal elt)
m Int
_i) key
k = TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst (TaggedVal elt -> elt) -> Maybe (TaggedVal elt) -> Maybe elt
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` Key -> Word64Map (TaggedVal elt) -> Maybe (TaggedVal elt)
forall a. Key -> Word64Map a -> Maybe a
M.lookup (Unique -> Key
getKey (Unique -> Key) -> Unique -> Key
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) Word64Map (TaggedVal elt)
m

lookupUDFM_Directly :: UniqDFM key elt -> Unique -> Maybe elt
lookupUDFM_Directly :: forall {k} (key :: k) elt. UniqDFM key elt -> Unique -> Maybe elt
lookupUDFM_Directly (UDFM Word64Map (TaggedVal elt)
m Int
_i) Unique
k = TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst (TaggedVal elt -> elt) -> Maybe (TaggedVal elt) -> Maybe elt
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` Key -> Word64Map (TaggedVal elt) -> Maybe (TaggedVal elt)
forall a. Key -> Word64Map a -> Maybe a
M.lookup (Unique -> Key
getKey Unique
k) Word64Map (TaggedVal elt)
m

elemUDFM :: Uniquable key => key -> UniqDFM key elt -> Bool
elemUDFM :: forall key elt. Uniquable key => key -> UniqDFM key elt -> Bool
elemUDFM key
k (UDFM Word64Map (TaggedVal elt)
m Int
_i) = Key -> Word64Map (TaggedVal elt) -> Bool
forall a. Key -> Word64Map a -> Bool
M.member (Unique -> Key
getKey (Unique -> Key) -> Unique -> Key
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) Word64Map (TaggedVal elt)
m

-- | Performs a deterministic fold over the UniqDFM.
-- It's O(n log n) while the corresponding function on `UniqFM` is O(n).
foldUDFM :: (elt -> a -> a) -> a -> UniqDFM key elt -> a
{-# INLINE foldUDFM #-}
-- This INLINE prevents a regression in !10568
foldUDFM :: forall {k} elt a (key :: k).
(elt -> a -> a) -> a -> UniqDFM key elt -> a
foldUDFM elt -> a -> a
k a
z UniqDFM key elt
m = (elt -> a -> a) -> a -> [elt] -> a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr elt -> a -> a
k a
z (UniqDFM key elt -> [elt]
forall k (key :: k) a. UniqDFM key a -> [a]
eltsUDFM UniqDFM key elt
m)

-- | Like 'foldUDFM' but the function also receives a key
foldWithKeyUDFM :: (Unique -> elt -> a -> a) -> a -> UniqDFM key elt -> a
{-# INLINE foldWithKeyUDFM #-}
-- This INLINE was copied from foldUDFM
foldWithKeyUDFM :: forall {k} elt a (key :: k).
(Unique -> elt -> a -> a) -> a -> UniqDFM key elt -> a
foldWithKeyUDFM Unique -> elt -> a -> a
k a
z UniqDFM key elt
m = ((Unique, elt) -> a -> a) -> a -> [(Unique, elt)] -> a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((Unique -> elt -> a -> a) -> (Unique, elt) -> a -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Unique -> elt -> a -> a
k) a
z (UniqDFM key elt -> [(Unique, elt)]
forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList UniqDFM key elt
m)

-- | Performs a nondeterministic strict fold over the UniqDFM.
-- It's O(n), same as the corresponding function on `UniqFM`.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetStrictFoldUDFM :: (elt -> a -> a) -> a -> UniqDFM key elt -> a
nonDetStrictFoldUDFM :: forall {k} elt a (key :: k).
(elt -> a -> a) -> a -> UniqDFM key elt -> a
nonDetStrictFoldUDFM elt -> a -> a
k a
z (UDFM Word64Map (TaggedVal elt)
m Int
_i) = (a -> TaggedVal elt -> a) -> a -> Word64Map (TaggedVal elt) -> a
forall b a. (b -> a -> b) -> b -> Word64Map a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' a -> TaggedVal elt -> a
k' a
z Word64Map (TaggedVal elt)
m
  where
    k' :: a -> TaggedVal elt -> a
k' a
acc (TaggedVal elt
v Int
_) = elt -> a -> a
k elt
v a
acc

eltsUDFM :: UniqDFM key elt -> [elt]
{-# INLINE eltsUDFM #-}
-- The INLINE makes it a good producer (from the map)
eltsUDFM :: forall k (key :: k) a. UniqDFM key a -> [a]
eltsUDFM (UDFM Word64Map (TaggedVal elt)
m Int
_i) = (TaggedVal elt -> elt) -> [TaggedVal elt] -> [elt]
forall a b. (a -> b) -> [a] -> [b]
map TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst (Word64Map (TaggedVal elt) -> [TaggedVal elt]
forall elt. Word64Map (TaggedVal elt) -> [TaggedVal elt]
sort_it Word64Map (TaggedVal elt)
m)

sort_it :: M.Word64Map (TaggedVal elt) -> [TaggedVal elt]
sort_it :: forall elt. Word64Map (TaggedVal elt) -> [TaggedVal elt]
sort_it Word64Map (TaggedVal elt)
m = (TaggedVal elt -> TaggedVal elt -> Ordering)
-> [TaggedVal elt] -> [TaggedVal elt]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Int -> Int -> Ordering)
-> (TaggedVal elt -> Int)
-> TaggedVal elt
-> TaggedVal elt
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TaggedVal elt -> Int
forall a. TaggedVal a -> Int
taggedSnd) (Word64Map (TaggedVal elt) -> [TaggedVal elt]
forall a. Word64Map a -> [a]
M.elems Word64Map (TaggedVal elt)
m)

filterUDFM :: (elt -> Bool) -> UniqDFM key elt -> UniqDFM key elt
filterUDFM :: forall {k} elt (key :: k).
(elt -> Bool) -> UniqDFM key elt -> UniqDFM key elt
filterUDFM elt -> Bool
p (UDFM Word64Map (TaggedVal elt)
m Int
i) = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt -> Bool)
-> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a. (a -> Bool) -> Word64Map a -> Word64Map a
M.filter (\(TaggedVal elt
v Int
_) -> elt -> Bool
p elt
v) Word64Map (TaggedVal elt)
m) Int
i

filterUDFM_Directly :: (Unique -> elt -> Bool) -> UniqDFM key elt -> UniqDFM key elt
filterUDFM_Directly :: forall {k} elt (key :: k).
(Unique -> elt -> Bool) -> UniqDFM key elt -> UniqDFM key elt
filterUDFM_Directly Unique -> elt -> Bool
p (UDFM Word64Map (TaggedVal elt)
m Int
i) = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((Key -> TaggedVal elt -> Bool)
-> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a. (Key -> a -> Bool) -> Word64Map a -> Word64Map a
M.filterWithKey Key -> TaggedVal elt -> Bool
p' Word64Map (TaggedVal elt)
m) Int
i
  where
  p' :: Key -> TaggedVal elt -> Bool
p' Key
k (TaggedVal elt
v Int
_) = Unique -> elt -> Bool
p (Key -> Unique
mkUniqueGrimily Key
k) elt
v

udfmRestrictKeys :: UniqDFM key elt -> UniqDFM key elt2 -> UniqDFM key elt
udfmRestrictKeys :: forall {k} (key :: k) elt elt2.
UniqDFM key elt -> UniqDFM key elt2 -> UniqDFM key elt
udfmRestrictKeys (UDFM Word64Map (TaggedVal elt)
a Int
i) (UDFM Word64Map (TaggedVal elt2)
b Int
_) = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Word64Map (TaggedVal elt) -> Word64Set -> Word64Map (TaggedVal elt)
forall a. Word64Map a -> Word64Set -> Word64Map a
M.restrictKeys Word64Map (TaggedVal elt)
a (Word64Map (TaggedVal elt2) -> Word64Set
forall a. Word64Map a -> Word64Set
M.keysSet Word64Map (TaggedVal elt2)
b)) Int
i

udfmRestrictKeysSet :: UniqDFM key elt -> W.Word64Set -> UniqDFM key elt
udfmRestrictKeysSet :: forall {k} (key :: k) elt.
UniqDFM key elt -> Word64Set -> UniqDFM key elt
udfmRestrictKeysSet (UDFM Word64Map (TaggedVal elt)
val_set Int
i) Word64Set
set =
  let key_set :: Word64Set
key_set = Word64Set
set
  in Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Word64Map (TaggedVal elt) -> Word64Set -> Word64Map (TaggedVal elt)
forall a. Word64Map a -> Word64Set -> Word64Map a
M.restrictKeys Word64Map (TaggedVal elt)
val_set Word64Set
key_set) Int
i

-- | Converts `UniqDFM` to a list, with elements in deterministic order.
-- It's O(n log n) while the corresponding function on `UniqFM` is O(n).
udfmToList :: UniqDFM key elt -> [(Unique, elt)]
udfmToList :: forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList (UDFM Word64Map (TaggedVal elt)
m Int
_i) =
  [ (Key -> Unique
mkUniqueGrimily Key
k, TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst TaggedVal elt
v)
  | (Key
k, TaggedVal elt
v) <- ((Key, TaggedVal elt) -> (Key, TaggedVal elt) -> Ordering)
-> [(Key, TaggedVal elt)] -> [(Key, TaggedVal elt)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Int -> Int -> Ordering)
-> ((Key, TaggedVal elt) -> Int)
-> (Key, TaggedVal elt)
-> (Key, TaggedVal elt)
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (TaggedVal elt -> Int
forall a. TaggedVal a -> Int
taggedSnd (TaggedVal elt -> Int)
-> ((Key, TaggedVal elt) -> TaggedVal elt)
-> (Key, TaggedVal elt)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Key, TaggedVal elt) -> TaggedVal elt
forall a b. (a, b) -> b
snd)) ([(Key, TaggedVal elt)] -> [(Key, TaggedVal elt)])
-> [(Key, TaggedVal elt)] -> [(Key, TaggedVal elt)]
forall a b. (a -> b) -> a -> b
$ Word64Map (TaggedVal elt) -> [(Key, TaggedVal elt)]
forall a. Word64Map a -> [(Key, a)]
M.toList Word64Map (TaggedVal elt)
m ]

-- Determines whether two 'UniqDFM's contain the same keys.
equalKeysUDFM :: UniqDFM key a -> UniqDFM key b -> Bool
equalKeysUDFM :: forall {k} (key :: k) a b. UniqDFM key a -> UniqDFM key b -> Bool
equalKeysUDFM (UDFM Word64Map (TaggedVal a)
m1 Int
_) (UDFM Word64Map (TaggedVal b)
m2 Int
_) = (TaggedVal a -> TaggedVal b -> Bool)
-> Word64Map (TaggedVal a) -> Word64Map (TaggedVal b) -> Bool
forall a b. (a -> b -> Bool) -> Word64Map a -> Word64Map b -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq (\TaggedVal a
_ TaggedVal b
_ -> Bool
True) Word64Map (TaggedVal a)
m1 Word64Map (TaggedVal b)
m2

isNullUDFM :: UniqDFM key elt -> Bool
isNullUDFM :: forall k (key :: k) a. UniqDFM key a -> Bool
isNullUDFM (UDFM Word64Map (TaggedVal elt)
m Int
_) = Word64Map (TaggedVal elt) -> Bool
forall a. Word64Map a -> Bool
M.null Word64Map (TaggedVal elt)
m

sizeUDFM :: UniqDFM key elt -> Int
sizeUDFM :: forall k (key :: k) a. UniqDFM key a -> Int
sizeUDFM (UDFM Word64Map (TaggedVal elt)
m Int
_i) = Word64Map (TaggedVal elt) -> Int
forall a. Word64Map a -> Int
M.size Word64Map (TaggedVal elt)
m

intersectUDFM :: UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
intersectUDFM :: forall {k} (key :: k) elt.
UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
intersectUDFM (UDFM Word64Map (TaggedVal elt)
x Int
i) (UDFM Word64Map (TaggedVal elt)
y Int
_j) = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Word64Map (TaggedVal elt)
-> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a b. Word64Map a -> Word64Map b -> Word64Map a
M.intersection Word64Map (TaggedVal elt)
x Word64Map (TaggedVal elt)
y) Int
i
  -- M.intersection is left biased, that means the result will only have
  -- a subset of elements from the left set, so `i` is a good upper bound.

udfmIntersectUFM :: UniqDFM key elt1 -> UniqFM key elt2 -> UniqDFM key elt1
udfmIntersectUFM :: forall {k} (key :: k) elt1 elt2.
UniqDFM key elt1 -> UniqFM key elt2 -> UniqDFM key elt1
udfmIntersectUFM (UDFM Word64Map (TaggedVal elt1)
x Int
i) UniqFM key elt2
y = Word64Map (TaggedVal elt1) -> Int -> UniqDFM key elt1
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Word64Map (TaggedVal elt1)
-> Word64Map elt2 -> Word64Map (TaggedVal elt1)
forall a b. Word64Map a -> Word64Map b -> Word64Map a
M.intersection Word64Map (TaggedVal elt1)
x (UniqFM key elt2 -> Word64Map elt2
forall {k} (key :: k) elt. UniqFM key elt -> Word64Map elt
ufmToIntMap UniqFM key elt2
y)) Int
i
  -- M.intersection is left biased, that means the result will only have
  -- a subset of elements from the left set, so `i` is a good upper bound.

disjointUDFM :: UniqDFM key elt -> UniqDFM key elt -> Bool
disjointUDFM :: forall {k} (key :: k) elt.
UniqDFM key elt -> UniqDFM key elt -> Bool
disjointUDFM (UDFM Word64Map (TaggedVal elt)
x Int
_i) (UDFM Word64Map (TaggedVal elt)
y Int
_j) = Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt) -> Bool
forall a b. Word64Map a -> Word64Map b -> Bool
M.disjoint Word64Map (TaggedVal elt)
x Word64Map (TaggedVal elt)
y

disjointUdfmUfm :: UniqDFM key elt -> UniqFM key elt2 -> Bool
disjointUdfmUfm :: forall {k} (key :: k) elt elt2.
UniqDFM key elt -> UniqFM key elt2 -> Bool
disjointUdfmUfm (UDFM Word64Map (TaggedVal elt)
x Int
_i) UniqFM key elt2
y = Word64Map (TaggedVal elt) -> Word64Map elt2 -> Bool
forall a b. Word64Map a -> Word64Map b -> Bool
M.disjoint Word64Map (TaggedVal elt)
x (UniqFM key elt2 -> Word64Map elt2
forall {k} (key :: k) elt. UniqFM key elt -> Word64Map elt
ufmToIntMap UniqFM key elt2
y)

minusUDFM :: UniqDFM key elt1 -> UniqDFM key elt2 -> UniqDFM key elt1
minusUDFM :: forall {k} (key :: k) elt elt2.
UniqDFM key elt -> UniqDFM key elt2 -> UniqDFM key elt
minusUDFM (UDFM Word64Map (TaggedVal elt1)
x Int
i) (UDFM Word64Map (TaggedVal elt2)
y Int
_j) = Word64Map (TaggedVal elt1) -> Int -> UniqDFM key elt1
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Word64Map (TaggedVal elt1)
-> Word64Map (TaggedVal elt2) -> Word64Map (TaggedVal elt1)
forall a b. Word64Map a -> Word64Map b -> Word64Map a
M.difference Word64Map (TaggedVal elt1)
x Word64Map (TaggedVal elt2)
y) Int
i
  -- M.difference returns a subset of a left set, so `i` is a good upper
  -- bound.

udfmMinusUFM :: UniqDFM key elt1 -> UniqFM key elt2 -> UniqDFM key elt1
udfmMinusUFM :: forall {k} (key :: k) elt1 elt2.
UniqDFM key elt1 -> UniqFM key elt2 -> UniqDFM key elt1
udfmMinusUFM (UDFM Word64Map (TaggedVal elt1)
x Int
i) UniqFM key elt2
y = Word64Map (TaggedVal elt1) -> Int -> UniqDFM key elt1
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM (Word64Map (TaggedVal elt1)
-> Word64Map elt2 -> Word64Map (TaggedVal elt1)
forall a b. Word64Map a -> Word64Map b -> Word64Map a
M.difference Word64Map (TaggedVal elt1)
x (UniqFM key elt2 -> Word64Map elt2
forall {k} (key :: k) elt. UniqFM key elt -> Word64Map elt
ufmToIntMap UniqFM key elt2
y)) Int
i
  -- M.difference returns a subset of a left set, so `i` is a good upper
  -- bound.

ufmMinusUDFM :: UniqFM key elt1 -> UniqDFM key elt2 -> UniqFM key elt1
ufmMinusUDFM :: forall {k} (key :: k) elt1 elt2.
UniqFM key elt1 -> UniqDFM key elt2 -> UniqFM key elt1
ufmMinusUDFM UniqFM key elt1
x (UDFM Word64Map (TaggedVal elt2)
y Int
_i) = Word64Map elt1 -> UniqFM key elt1
forall {k} elt (key :: k). Word64Map elt -> UniqFM key elt
unsafeIntMapToUFM (Word64Map elt1 -> Word64Map (TaggedVal elt2) -> Word64Map elt1
forall a b. Word64Map a -> Word64Map b -> Word64Map a
M.difference (UniqFM key elt1 -> Word64Map elt1
forall {k} (key :: k) elt. UniqFM key elt -> Word64Map elt
ufmToIntMap UniqFM key elt1
x) Word64Map (TaggedVal elt2)
y)

-- | Partition UniqDFM into two UniqDFMs according to the predicate
partitionUDFM :: (elt -> Bool) -> UniqDFM key elt -> (UniqDFM key elt, UniqDFM key elt)
partitionUDFM :: forall {k} elt (key :: k).
(elt -> Bool)
-> UniqDFM key elt -> (UniqDFM key elt, UniqDFM key elt)
partitionUDFM elt -> Bool
p (UDFM Word64Map (TaggedVal elt)
m Int
i) =
  case (TaggedVal elt -> Bool)
-> Word64Map (TaggedVal elt)
-> (Word64Map (TaggedVal elt), Word64Map (TaggedVal elt))
forall a. (a -> Bool) -> Word64Map a -> (Word64Map a, Word64Map a)
M.partition (elt -> Bool
p (elt -> Bool) -> (TaggedVal elt -> elt) -> TaggedVal elt -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst) Word64Map (TaggedVal elt)
m of
    (Word64Map (TaggedVal elt)
left, Word64Map (TaggedVal elt)
right) -> (Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM Word64Map (TaggedVal elt)
left Int
i, Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM Word64Map (TaggedVal elt)
right Int
i)

-- | Delete a list of elements from a UniqDFM
delListFromUDFM  :: Uniquable key => UniqDFM key elt -> [key] -> UniqDFM key elt
delListFromUDFM :: forall key elt.
Uniquable key =>
UniqDFM key elt -> [key] -> UniqDFM key elt
delListFromUDFM = (UniqDFM key elt -> key -> UniqDFM key elt)
-> UniqDFM key elt -> [key] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' UniqDFM key elt -> key -> UniqDFM key elt
forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> UniqDFM key elt
delFromUDFM

-- | This allows for lossy conversion from UniqDFM to UniqFM
udfmToUfm :: UniqDFM key elt -> UniqFM key elt
udfmToUfm :: forall {k} (key :: k) elt. UniqDFM key elt -> UniqFM key elt
udfmToUfm (UDFM Word64Map (TaggedVal elt)
m Int
_i) = Word64Map elt -> UniqFM key elt
forall {k} elt (key :: k). Word64Map elt -> UniqFM key elt
unsafeIntMapToUFM ((TaggedVal elt -> elt)
-> Word64Map (TaggedVal elt) -> Word64Map elt
forall a b. (a -> b) -> Word64Map a -> Word64Map b
M.map TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst Word64Map (TaggedVal elt)
m)

listToUDFM :: Uniquable key => [(key,elt)] -> UniqDFM key elt
listToUDFM :: forall key elt. Uniquable key => [(key, elt)] -> UniqDFM key elt
listToUDFM = (UniqDFM key elt -> (key, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(key, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (key
k, elt
v) -> UniqDFM key elt -> key -> elt -> UniqDFM key elt
forall key elt.
Uniquable key =>
UniqDFM key elt -> key -> elt -> UniqDFM key elt
addToUDFM UniqDFM key elt
m key
k elt
v) UniqDFM key elt
forall {k} (key :: k) elt. UniqDFM key elt
emptyUDFM

listToUDFM_Directly :: [(Unique, elt)] -> UniqDFM key elt
listToUDFM_Directly :: forall {k} elt (key :: k). [(Unique, elt)] -> UniqDFM key elt
listToUDFM_Directly = (UniqDFM key elt -> (Unique, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (Unique
u, elt
v) -> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} (key :: k) elt.
UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_Directly UniqDFM key elt
m Unique
u elt
v) UniqDFM key elt
forall {k} (key :: k) elt. UniqDFM key elt
emptyUDFM

listToUDFM_C_Directly :: (elt -> elt -> elt) -> [(Unique, elt)] -> UniqDFM key elt
listToUDFM_C_Directly :: forall {k} elt (key :: k).
(elt -> elt -> elt) -> [(Unique, elt)] -> UniqDFM key elt
listToUDFM_C_Directly elt -> elt -> elt
f = (UniqDFM key elt -> (Unique, elt) -> UniqDFM key elt)
-> UniqDFM key elt -> [(Unique, elt)] -> UniqDFM key elt
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqDFM key elt
m (Unique
u, elt
v) -> (elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
forall {k} elt (key :: k).
(elt -> elt -> elt)
-> UniqDFM key elt -> Unique -> elt -> UniqDFM key elt
addToUDFM_C_Directly elt -> elt -> elt
f UniqDFM key elt
m Unique
u elt
v) UniqDFM key elt
forall {k} (key :: k) elt. UniqDFM key elt
emptyUDFM

-- | Apply a function to a particular element
adjustUDFM :: Uniquable key => (elt -> elt) -> UniqDFM key elt -> key -> UniqDFM key elt
adjustUDFM :: forall key elt.
Uniquable key =>
(elt -> elt) -> UniqDFM key elt -> key -> UniqDFM key elt
adjustUDFM elt -> elt
f (UDFM Word64Map (TaggedVal elt)
m Int
i) key
k = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt -> TaggedVal elt)
-> Key -> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a. (a -> a) -> Key -> Word64Map a -> Word64Map a
M.adjust ((elt -> elt) -> TaggedVal elt -> TaggedVal elt
forall a b. (a -> b) -> TaggedVal a -> TaggedVal b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap elt -> elt
f) (Unique -> Key
getKey (Unique -> Key) -> Unique -> Key
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) Word64Map (TaggedVal elt)
m) Int
i

-- | Apply a function to a particular element
adjustUDFM_Directly :: (elt -> elt) -> UniqDFM key elt -> Unique -> UniqDFM key elt
adjustUDFM_Directly :: forall {k} elt (key :: k).
(elt -> elt) -> UniqDFM key elt -> Unique -> UniqDFM key elt
adjustUDFM_Directly elt -> elt
f (UDFM Word64Map (TaggedVal elt)
m Int
i) Unique
k = Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt -> TaggedVal elt)
-> Key -> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a. (a -> a) -> Key -> Word64Map a -> Word64Map a
M.adjust ((elt -> elt) -> TaggedVal elt -> TaggedVal elt
forall a b. (a -> b) -> TaggedVal a -> TaggedVal b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap elt -> elt
f) (Unique -> Key
getKey Unique
k) Word64Map (TaggedVal elt)
m) Int
i

-- | The expression (alterUDFM f k map) alters value x at k, or absence
-- thereof. alterUDFM can be used to insert, delete, or update a value in
-- UniqDFM. Use addToUDFM, delFromUDFM or adjustUDFM when possible, they are
-- more efficient.
alterUDFM
  :: Uniquable key
  => (Maybe elt -> Maybe elt)  -- How to adjust
  -> UniqDFM key elt               -- old
  -> key                       -- new
  -> UniqDFM key elt               -- result
alterUDFM :: forall key elt.
Uniquable key =>
(Maybe elt -> Maybe elt)
-> UniqDFM key elt -> key -> UniqDFM key elt
alterUDFM Maybe elt -> Maybe elt
f (UDFM Word64Map (TaggedVal elt)
m Int
i) key
k =
  Word64Map (TaggedVal elt) -> Int -> UniqDFM key elt
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((Maybe (TaggedVal elt) -> Maybe (TaggedVal elt))
-> Key -> Word64Map (TaggedVal elt) -> Word64Map (TaggedVal elt)
forall a. (Maybe a -> Maybe a) -> Key -> Word64Map a -> Word64Map a
M.alter Maybe (TaggedVal elt) -> Maybe (TaggedVal elt)
alterf (Unique -> Key
getKey (Unique -> Key) -> Unique -> Key
forall a b. (a -> b) -> a -> b
$ key -> Unique
forall a. Uniquable a => a -> Unique
getUnique key
k) Word64Map (TaggedVal elt)
m) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  where
  alterf :: Maybe (TaggedVal elt) -> Maybe (TaggedVal elt)
alterf Maybe (TaggedVal elt)
Nothing = Maybe elt -> Maybe (TaggedVal elt)
inject (Maybe elt -> Maybe (TaggedVal elt))
-> Maybe elt -> Maybe (TaggedVal elt)
forall a b. (a -> b) -> a -> b
$ Maybe elt -> Maybe elt
f Maybe elt
forall a. Maybe a
Nothing
  alterf (Just (TaggedVal elt
v Int
_)) = Maybe elt -> Maybe (TaggedVal elt)
inject (Maybe elt -> Maybe (TaggedVal elt))
-> Maybe elt -> Maybe (TaggedVal elt)
forall a b. (a -> b) -> a -> b
$ Maybe elt -> Maybe elt
f (elt -> Maybe elt
forall a. a -> Maybe a
Just elt
v)
  inject :: Maybe elt -> Maybe (TaggedVal elt)
inject Maybe elt
Nothing = Maybe (TaggedVal elt)
forall a. Maybe a
Nothing
  inject (Just elt
v) = TaggedVal elt -> Maybe (TaggedVal elt)
forall a. a -> Maybe a
Just (TaggedVal elt -> Maybe (TaggedVal elt))
-> TaggedVal elt -> Maybe (TaggedVal elt)
forall a b. (a -> b) -> a -> b
$ elt -> Int -> TaggedVal elt
forall val. val -> Int -> TaggedVal val
TaggedVal elt
v Int
i

-- | Map a function over every value in a UniqDFM
mapUDFM :: (elt1 -> elt2) -> UniqDFM key elt1 -> UniqDFM key elt2
mapUDFM :: forall {k} elt1 elt2 (key :: k).
(elt1 -> elt2) -> UniqDFM key elt1 -> UniqDFM key elt2
mapUDFM elt1 -> elt2
f (UDFM Word64Map (TaggedVal elt1)
m Int
i) = Word64Map (TaggedVal elt2) -> Int -> UniqDFM key elt2
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt1 -> TaggedVal elt2)
-> Word64Map (TaggedVal elt1) -> Word64Map (TaggedVal elt2)
forall a b. (a -> b) -> Word64Map a -> Word64Map b
MS.map ((elt1 -> elt2) -> TaggedVal elt1 -> TaggedVal elt2
forall a b. (a -> b) -> TaggedVal a -> TaggedVal b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap elt1 -> elt2
f) Word64Map (TaggedVal elt1)
m) Int
i
-- Critical this is strict map, otherwise you get a big space leak when reloading
-- in GHCi because all old ModDetails are retained (see pruneHomePackageTable).
-- Modify with care.

{-# INLINEABLE mapMUDFM #-}
-- | 'mapM' for a 'UniqDFM'.
mapMUDFM :: Monad m => (elt1 -> m elt2) -> UniqDFM key elt1 -> m (UniqDFM key elt2)
mapMUDFM :: forall {k} (m :: * -> *) elt1 elt2 (key :: k).
Monad m =>
(elt1 -> m elt2) -> UniqDFM key elt1 -> m (UniqDFM key elt2)
mapMUDFM elt1 -> m elt2
f (UDFM Word64Map (TaggedVal elt1)
m Int
i) = do
  m' <- (TaggedVal elt1 -> m (TaggedVal elt2))
-> Word64Map (TaggedVal elt1) -> m (Word64Map (TaggedVal elt2))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Word64Map a -> f (Word64Map b)
traverse ((elt1 -> m elt2) -> TaggedVal elt1 -> m (TaggedVal elt2)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TaggedVal a -> f (TaggedVal b)
traverse elt1 -> m elt2
f) Word64Map (TaggedVal elt1)
m
  return $ UDFM m' i

mapMaybeUDFM :: forall elt1 elt2 key.
                (elt1 -> Maybe elt2) -> UniqDFM key elt1 -> UniqDFM key elt2
mapMaybeUDFM :: forall {k} elt1 elt2 (key :: k).
(elt1 -> Maybe elt2) -> UniqDFM key elt1 -> UniqDFM key elt2
mapMaybeUDFM elt1 -> Maybe elt2
f (UDFM Word64Map (TaggedVal elt1)
m Int
i) = Word64Map (TaggedVal elt2) -> Int -> UniqDFM key elt2
forall {k} (key :: k) ele.
Word64Map (TaggedVal ele) -> Int -> UniqDFM key ele
UDFM ((TaggedVal elt1 -> Maybe (TaggedVal elt2))
-> Word64Map (TaggedVal elt1) -> Word64Map (TaggedVal elt2)
forall a b. (a -> Maybe b) -> Word64Map a -> Word64Map b
M.mapMaybe ((elt1 -> Maybe elt2) -> TaggedVal elt1 -> Maybe (TaggedVal elt2)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TaggedVal a -> f (TaggedVal b)
traverse elt1 -> Maybe elt2
f) Word64Map (TaggedVal elt1)
m) Int
i

anyUDFM :: (elt -> Bool) -> UniqDFM key elt -> Bool
anyUDFM :: forall {k} elt (key :: k). (elt -> Bool) -> UniqDFM key elt -> Bool
anyUDFM elt -> Bool
p (UDFM Word64Map (TaggedVal elt)
m Int
_i) = (TaggedVal elt -> Bool -> Bool)
-> Bool -> Word64Map (TaggedVal elt) -> Bool
forall a b. (a -> b -> b) -> b -> Word64Map a -> b
M.foldr (Bool -> Bool -> Bool
(||) (Bool -> Bool -> Bool)
-> (TaggedVal elt -> Bool) -> TaggedVal elt -> Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. elt -> Bool
p (elt -> Bool) -> (TaggedVal elt -> elt) -> TaggedVal elt -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst) Bool
False Word64Map (TaggedVal elt)
m

allUDFM :: (elt -> Bool) -> UniqDFM key elt -> Bool
allUDFM :: forall {k} elt (key :: k). (elt -> Bool) -> UniqDFM key elt -> Bool
allUDFM elt -> Bool
p (UDFM Word64Map (TaggedVal elt)
m Int
_i) = (TaggedVal elt -> Bool -> Bool)
-> Bool -> Word64Map (TaggedVal elt) -> Bool
forall a b. (a -> b -> b) -> b -> Word64Map a -> b
M.foldr (Bool -> Bool -> Bool
(&&) (Bool -> Bool -> Bool)
-> (TaggedVal elt -> Bool) -> TaggedVal elt -> Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. elt -> Bool
p (elt -> Bool) -> (TaggedVal elt -> elt) -> TaggedVal elt -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TaggedVal elt -> elt
forall val. TaggedVal val -> val
taggedFst) Bool
True Word64Map (TaggedVal elt)
m

-- This should not be used in committed code, provided for convenience to
-- make ad-hoc conversions when developing
alwaysUnsafeUfmToUdfm :: UniqFM key elt -> UniqDFM key elt
alwaysUnsafeUfmToUdfm :: forall {k} (key :: k) elt. UniqFM key elt -> UniqDFM key elt
alwaysUnsafeUfmToUdfm = [(Unique, elt)] -> UniqDFM key elt
forall {k} elt (key :: k). [(Unique, elt)] -> UniqDFM key elt
listToUDFM_Directly ([(Unique, elt)] -> UniqDFM key elt)
-> (UniqFM key elt -> [(Unique, elt)])
-> UniqFM key elt
-> UniqDFM key elt
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UniqFM key elt -> [(Unique, elt)]
forall {k} (key :: k) elt. UniqFM key elt -> [(Unique, elt)]
nonDetUFMToList

-- | Cast the key domain of a UniqFM.
--
-- As long as the domains don't overlap in their uniques
-- this is safe.
unsafeCastUDFMKey :: UniqDFM key1 elt -> UniqDFM key2 elt
unsafeCastUDFMKey :: forall {k} {k} (key1 :: k) elt (key2 :: k).
UniqDFM key1 elt -> UniqDFM key2 elt
unsafeCastUDFMKey = UniqDFM key1 elt -> UniqDFM key2 elt
forall a b. a -> b
unsafeCoerce -- Only phantom parameter changes so
                                 -- this is safe and avoids reallocation.

-- Output-ery

instance Outputable a => Outputable (UniqDFM key a) where
    ppr :: UniqDFM key a -> SDoc
ppr UniqDFM key a
ufm = (a -> SDoc) -> UniqDFM key a -> SDoc
forall {k} a (key :: k). (a -> SDoc) -> UniqDFM key a -> SDoc
pprUniqDFM a -> SDoc
forall a. Outputable a => a -> SDoc
ppr UniqDFM key a
ufm

pprUniqDFM :: (a -> SDoc) -> UniqDFM key a -> SDoc
pprUniqDFM :: forall {k} a (key :: k). (a -> SDoc) -> UniqDFM key a -> SDoc
pprUniqDFM a -> SDoc
ppr_elt UniqDFM key a
ufm
  = SDoc -> SDoc
forall doc. IsLine doc => doc -> doc
brackets (SDoc -> SDoc) -> SDoc -> SDoc
forall a b. (a -> b) -> a -> b
$ [SDoc] -> SDoc
forall doc. IsLine doc => [doc] -> doc
fsep ([SDoc] -> SDoc) -> [SDoc] -> SDoc
forall a b. (a -> b) -> a -> b
$ SDoc -> [SDoc] -> [SDoc]
forall doc. IsLine doc => doc -> [doc] -> [doc]
punctuate SDoc
forall doc. IsLine doc => doc
comma ([SDoc] -> [SDoc]) -> [SDoc] -> [SDoc]
forall a b. (a -> b) -> a -> b
$
    [ Unique -> SDoc
forall a. Outputable a => a -> SDoc
ppr Unique
uq SDoc -> SDoc -> SDoc
forall doc. IsLine doc => doc -> doc -> doc
<+> String -> SDoc
forall doc. IsLine doc => String -> doc
text String
":->" SDoc -> SDoc -> SDoc
forall doc. IsLine doc => doc -> doc -> doc
<+> a -> SDoc
ppr_elt a
elt
    | (Unique
uq, a
elt) <- UniqDFM key a -> [(Unique, a)]
forall {k} (key :: k) elt. UniqDFM key elt -> [(Unique, elt)]
udfmToList UniqDFM key a
ufm ]

pprUDFM :: UniqDFM key a    -- ^ The things to be pretty printed
       -> ([a] -> SDoc) -- ^ The pretty printing function to use on the elements
       -> SDoc          -- ^ 'SDoc' where the things have been pretty
                        -- printed
pprUDFM :: forall {k} (key :: k) a. UniqDFM key a -> ([a] -> SDoc) -> SDoc
pprUDFM UniqDFM key a
ufm [a] -> SDoc
pp = [a] -> SDoc
pp (UniqDFM key a -> [a]
forall k (key :: k) a. UniqDFM key a -> [a]
eltsUDFM UniqDFM key a
ufm)