{-
(c) The University of Glasgow 2006
(c) The AQUA Project, Glasgow University, 1994-1998


UniqFM: Specialised 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@.

(A similar thing to @UniqSet@, as opposed to @Set@.)

The interface is based on @FiniteMap@s, but the implementation uses
@Data.IntMap@, which is both maintained and faster than the past
implementation (see commit log).

The @UniqFM@ interface maps directly to Data.IntMap, only
``Data.IntMap.union'' is left-biased and ``plusUFM'' right-biased
and ``addToUFM\_C'' and ``Data.IntMap.insertWith'' differ in the order
of arguments of combining function.
-}

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE ScopedTypeVariables #-}

{-# OPTIONS_GHC -Wall #-}

module GHC.Types.Unique.FM (
        -- * Unique-keyed mappings
        UniqFM,           -- abstract type
        NonDetUniqFM(..), -- wrapper for opting into nondeterminism

        -- ** Manipulating those mappings
        emptyUFM,
        unitUFM,
        unitDirectlyUFM,
        zipToUFM,
        listToUFM,
        listToUFM_Directly,
        listToUFM_C,
        listToIdentityUFM,
        addToUFM,addToUFM_C,addToUFM_Acc,addToUFM_L,
        addListToUFM,addListToUFM_C,
        addToUFM_Directly,
        addListToUFM_Directly,
        adjustUFM, alterUFM,
        adjustUFM_Directly,
        delFromUFM,
        delFromUFM_Directly,
        delListFromUFM,
        delListFromUFM_Directly,
        plusUFM,
        plusUFM_C,
        plusUFM_CD,
        plusUFM_CD2,
        mergeUFM,
        plusMaybeUFM_C,
        plusUFMList,
        sequenceUFMList,
        minusUFM,
        minusUFM_C,
        intersectUFM,
        intersectUFM_C,
        disjointUFM,
        equalKeysUFM,
        nonDetStrictFoldUFM, foldUFM, nonDetStrictFoldUFM_DirectlyM,
        nonDetStrictFoldUFM_Directly,
        anyUFM, allUFM, seqEltsUFM,
        mapUFM, mapUFM_Directly,
        mapMaybeUFM,
        elemUFM, elemUFM_Directly,
        filterUFM, filterUFM_Directly, partitionUFM,
        sizeUFM,
        isNullUFM,
        lookupUFM, lookupUFM_Directly,
        lookupWithDefaultUFM, lookupWithDefaultUFM_Directly,
        nonDetEltsUFM, nonDetKeysUFM,
        ufmToSet_Directly,
        nonDetUFMToList, ufmToIntMap, unsafeIntMapToUFM,
        unsafeCastUFMKey,
        pprUniqFM, pprUFM, pprUFMWithKeys, pluralUFM
    ) where

import GHC.Prelude

import GHC.Types.Unique ( Uniquable(..), Unique, getKey )
import GHC.Utils.Outputable
import GHC.Utils.Panic.Plain
import qualified Data.IntMap as M
import qualified Data.IntMap.Strict as MS
import qualified Data.IntSet as S
import Data.Data
import qualified Data.Semigroup as Semi
import Data.Functor.Classes (Eq1 (..))
import Data.Coerce

-- | A finite map from @uniques@ of one type to
-- elements in another type.
--
-- 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.
newtype UniqFM key ele = UFM (M.IntMap ele)
  deriving (UniqFM key ele -> DataType
UniqFM key ele -> Constr
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 {key} {ele}.
(Data key, Data ele) =>
Typeable (UniqFM key ele)
forall key ele. (Data key, Data ele) => UniqFM key ele -> DataType
forall key ele. (Data key, Data ele) => UniqFM key ele -> Constr
forall key ele.
(Data key, Data ele) =>
(forall b. Data b => b -> b) -> UniqFM key ele -> UniqFM key ele
forall key ele u.
(Data key, Data ele) =>
Int -> (forall d. Data d => d -> u) -> UniqFM key ele -> u
forall key ele u.
(Data key, Data ele) =>
(forall d. Data d => d -> u) -> UniqFM key ele -> [u]
forall key ele r r'.
(Data key, Data ele) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM key ele -> r
forall key ele r r'.
(Data key, Data ele) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM key ele -> r
forall key ele (m :: * -> *).
(Data key, Data ele, Monad m) =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
forall key ele (m :: * -> *).
(Data key, Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
forall key ele (c :: * -> *).
(Data key, Data ele) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM key ele)
forall key ele (c :: * -> *).
(Data key, Data ele) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM key ele -> c (UniqFM key ele)
forall key ele (t :: * -> *) (c :: * -> *).
(Data key, Data ele, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM key ele))
forall key ele (t :: * -> * -> *) (c :: * -> *).
(Data key, Data ele, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM key ele))
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM key ele)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM key ele -> c (UniqFM key ele)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM key ele))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
$cgmapMo :: forall key ele (m :: * -> *).
(Data key, Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
$cgmapMp :: forall key ele (m :: * -> *).
(Data key, Data ele, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
$cgmapM :: forall key ele (m :: * -> *).
(Data key, Data ele, Monad m) =>
(forall d. Data d => d -> m d)
-> UniqFM key ele -> m (UniqFM key ele)
gmapQi :: forall u.
Int -> (forall d. Data d => d -> u) -> UniqFM key ele -> u
$cgmapQi :: forall key ele u.
(Data key, Data ele) =>
Int -> (forall d. Data d => d -> u) -> UniqFM key ele -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> UniqFM key ele -> [u]
$cgmapQ :: forall key ele u.
(Data key, Data ele) =>
(forall d. Data d => d -> u) -> UniqFM key ele -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM key ele -> r
$cgmapQr :: forall key ele r r'.
(Data key, Data ele) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM key ele -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM key ele -> r
$cgmapQl :: forall key ele r r'.
(Data key, Data ele) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> UniqFM key ele -> r
gmapT :: (forall b. Data b => b -> b) -> UniqFM key ele -> UniqFM key ele
$cgmapT :: forall key ele.
(Data key, Data ele) =>
(forall b. Data b => b -> b) -> UniqFM key ele -> UniqFM key ele
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM key ele))
$cdataCast2 :: forall key ele (t :: * -> * -> *) (c :: * -> *).
(Data key, Data ele, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (UniqFM key ele))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM key ele))
$cdataCast1 :: forall key ele (t :: * -> *) (c :: * -> *).
(Data key, Data ele, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (UniqFM key ele))
dataTypeOf :: UniqFM key ele -> DataType
$cdataTypeOf :: forall key ele. (Data key, Data ele) => UniqFM key ele -> DataType
toConstr :: UniqFM key ele -> Constr
$ctoConstr :: forall key ele. (Data key, Data ele) => UniqFM key ele -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM key ele)
$cgunfold :: forall key ele (c :: * -> *).
(Data key, Data ele) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (UniqFM key ele)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM key ele -> c (UniqFM key ele)
$cgfoldl :: forall key ele (c :: * -> *).
(Data key, Data ele) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> UniqFM key ele -> c (UniqFM key ele)
Data, UniqFM key ele -> UniqFM key ele -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall key ele. Eq ele => UniqFM key ele -> UniqFM key ele -> Bool
/= :: UniqFM key ele -> UniqFM key ele -> Bool
$c/= :: forall key ele. Eq ele => UniqFM key ele -> UniqFM key ele -> Bool
== :: UniqFM key ele -> UniqFM key ele -> Bool
$c== :: forall key ele. Eq ele => UniqFM key ele -> UniqFM key ele -> Bool
Eq, forall a b. a -> UniqFM key b -> UniqFM key a
forall a b. (a -> b) -> UniqFM key a -> UniqFM key b
forall key a b. a -> UniqFM key b -> UniqFM key a
forall key a b. (a -> b) -> UniqFM key a -> UniqFM key b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> UniqFM key b -> UniqFM key a
$c<$ :: forall key a b. a -> UniqFM key b -> UniqFM key a
fmap :: forall a b. (a -> b) -> UniqFM key a -> UniqFM key b
$cfmap :: forall key a b. (a -> b) -> UniqFM key a -> UniqFM key b
Functor)
  -- Nondeterministic Foldable and Traversable instances are accessible through
  -- use of the 'NonDetUniqFM' wrapper.
  -- See Note [Deterministic UniqFM] in GHC.Types.Unique.DFM to learn about determinism.

emptyUFM :: UniqFM key elt
emptyUFM :: forall key elt. UniqFM key elt
emptyUFM = forall key ele. IntMap ele -> UniqFM key ele
UFM forall a. IntMap a
M.empty

isNullUFM :: UniqFM key elt -> Bool
isNullUFM :: forall key elt. UniqFM key elt -> Bool
isNullUFM (UFM IntMap elt
m) = forall a. IntMap a -> Bool
M.null IntMap elt
m

unitUFM :: Uniquable key => key -> elt -> UniqFM key elt
unitUFM :: forall key elt. Uniquable key => key -> elt -> UniqFM key elt
unitUFM key
k elt
v = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. Int -> a -> IntMap a
M.singleton (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v)

-- when you've got the Unique already
unitDirectlyUFM :: Unique -> elt -> UniqFM key elt
unitDirectlyUFM :: forall elt key. Unique -> elt -> UniqFM key elt
unitDirectlyUFM Unique
u elt
v = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. Int -> a -> IntMap a
M.singleton (Unique -> Int
getKey Unique
u) elt
v)

-- zipToUFM ks vs = listToUFM (zip ks vs)
-- This function exists because it's a common case (#18535), and
-- it's inefficient to first build a list of pairs, and then immediately
-- take it apart. Astonishingly, fusing this one list away reduces total
-- compiler allocation by more than 10% (in T12545, see !3935)
-- Note that listToUFM (zip ks vs) performs similarly, but
-- the explicit recursion avoids relying too much on fusion.
zipToUFM :: Uniquable key => [key] -> [elt] -> UniqFM key elt
zipToUFM :: forall key elt. Uniquable key => [key] -> [elt] -> UniqFM key elt
zipToUFM [key]
ks [elt]
vs = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Int
length [key]
ks forall a. Eq a => a -> a -> Bool
== forall (t :: * -> *) a. Foldable t => t a -> Int
length [elt]
vs ) forall {key} {elt}.
Uniquable key =>
UniqFM key elt -> [key] -> [elt] -> UniqFM key elt
innerZip forall key elt. UniqFM key elt
emptyUFM [key]
ks [elt]
vs
  where
    innerZip :: UniqFM key elt -> [key] -> [elt] -> UniqFM key elt
innerZip UniqFM key elt
ufm (key
k:[key]
kList) (elt
v:[elt]
vList) = UniqFM key elt -> [key] -> [elt] -> UniqFM key elt
innerZip (forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM UniqFM key elt
ufm key
k elt
v) [key]
kList [elt]
vList
    innerZip UniqFM key elt
ufm [key]
_ [elt]
_ = UniqFM key elt
ufm

listToUFM :: Uniquable key => [(key,elt)] -> UniqFM key elt
listToUFM :: forall key elt. Uniquable key => [(key, elt)] -> UniqFM key elt
listToUFM = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key elt
m (key
k, elt
v) -> forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM UniqFM key elt
m key
k elt
v) forall key elt. UniqFM key elt
emptyUFM

listToUFM_Directly :: [(Unique, elt)] -> UniqFM key elt
listToUFM_Directly :: forall elt key. [(Unique, elt)] -> UniqFM key elt
listToUFM_Directly = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key elt
m (Unique
u, elt
v) -> forall key elt. UniqFM key elt -> Unique -> elt -> UniqFM key elt
addToUFM_Directly UniqFM key elt
m Unique
u elt
v) forall key elt. UniqFM key elt
emptyUFM

listToIdentityUFM :: Uniquable key => [key] -> UniqFM key key
listToIdentityUFM :: forall key. Uniquable key => [key] -> UniqFM key key
listToIdentityUFM = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key key
m key
x -> forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM UniqFM key key
m key
x key
x) forall key elt. UniqFM key elt
emptyUFM

listToUFM_C
  :: Uniquable key
  => (elt -> elt -> elt)
  -> [(key, elt)]
  -> UniqFM key elt
listToUFM_C :: forall key elt.
Uniquable key =>
(elt -> elt -> elt) -> [(key, elt)] -> UniqFM key elt
listToUFM_C elt -> elt -> elt
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key elt
m (key
k, elt
v) -> forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM_C elt -> elt -> elt
f UniqFM key elt
m key
k elt
v) forall key elt. UniqFM key elt
emptyUFM

addToUFM :: Uniquable key => UniqFM key elt -> key -> elt  -> UniqFM key elt
addToUFM :: forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM (UFM IntMap elt
m) key
k elt
v = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. Int -> a -> IntMap a -> IntMap a
M.insert (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v IntMap elt
m)

addListToUFM :: Uniquable key => UniqFM key elt -> [(key,elt)] -> UniqFM key elt
addListToUFM :: forall key elt.
Uniquable key =>
UniqFM key elt -> [(key, elt)] -> UniqFM key elt
addListToUFM = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key elt
m (key
k, elt
v) -> forall key elt.
Uniquable key =>
UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM UniqFM key elt
m key
k elt
v)

addListToUFM_Directly :: UniqFM key elt -> [(Unique,elt)] -> UniqFM key elt
addListToUFM_Directly :: forall key elt. UniqFM key elt -> [(Unique, elt)] -> UniqFM key elt
addListToUFM_Directly = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key elt
m (Unique
k, elt
v) -> forall key elt. UniqFM key elt -> Unique -> elt -> UniqFM key elt
addToUFM_Directly UniqFM key elt
m Unique
k elt
v)

addToUFM_Directly :: UniqFM key elt -> Unique -> elt -> UniqFM key elt
addToUFM_Directly :: forall key elt. UniqFM key elt -> Unique -> elt -> UniqFM key elt
addToUFM_Directly (UFM IntMap elt
m) Unique
u elt
v = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. Int -> a -> IntMap a -> IntMap a
M.insert (Unique -> Int
getKey Unique
u) elt
v IntMap elt
m)

addToUFM_C
  :: Uniquable key
  => (elt -> elt -> elt)  -- old -> new -> result
  -> UniqFM key elt           -- old
  -> key -> elt           -- new
  -> UniqFM key elt           -- result
-- Arguments of combining function of M.insertWith and addToUFM_C are flipped.
addToUFM_C :: forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM_C elt -> elt -> elt
f (UFM IntMap elt
m) key
k elt
v =
  forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
M.insertWith (forall a b c. (a -> b -> c) -> b -> a -> c
flip elt -> elt -> elt
f) (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) elt
v IntMap elt
m)

addToUFM_Acc
  :: Uniquable key
  => (elt -> elts -> elts)  -- Add to existing
  -> (elt -> elts)          -- New element
  -> UniqFM key elts            -- old
  -> key -> elt             -- new
  -> UniqFM key elts            -- result
addToUFM_Acc :: forall key elt elts.
Uniquable key =>
(elt -> elts -> elts)
-> (elt -> elts)
-> UniqFM key elts
-> key
-> elt
-> UniqFM key elts
addToUFM_Acc elt -> elts -> elts
exi elt -> elts
new (UFM IntMap elts
m) key
k elt
v =
  forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
M.insertWith (\elts
_new elts
old -> elt -> elts -> elts
exi elt
v elts
old) (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) (elt -> elts
new elt
v) IntMap elts
m)

-- | Add an element, returns previous lookup result and new map. If
-- old element doesn't exist, add the passed element directly,
-- otherwise compute the element to add using the passed function.
addToUFM_L
  :: Uniquable key
  => (key -> elt -> elt -> elt) -- key,old,new
  -> key
  -> elt -- new
  -> UniqFM key elt
  -> (Maybe elt, UniqFM key elt) -- old, result
addToUFM_L :: forall key elt.
Uniquable key =>
(key -> elt -> elt -> elt)
-> key -> elt -> UniqFM key elt -> (Maybe elt, UniqFM key elt)
addToUFM_L key -> elt -> elt -> elt
f key
k elt
v (UFM IntMap elt
m) =
  coerce :: forall a b. Coercible a b => a -> b
coerce forall a b. (a -> b) -> a -> b
$
    forall a.
(Int -> a -> a -> a) -> Int -> a -> IntMap a -> (Maybe a, IntMap a)
M.insertLookupWithKey
      (\Int
_ elt
_n elt
_o -> key -> elt -> elt -> elt
f key
k elt
_o elt
_n)
      (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k)
      elt
v
      IntMap elt
m

alterUFM
  :: Uniquable key
  => (Maybe elt -> Maybe elt)  -- How to adjust
  -> UniqFM key elt                -- old
  -> key                       -- new
  -> UniqFM key elt                -- result
alterUFM :: forall key elt.
Uniquable key =>
(Maybe elt -> Maybe elt) -> UniqFM key elt -> key -> UniqFM key elt
alterUFM Maybe elt -> Maybe elt
f (UFM IntMap elt
m) key
k = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
M.alter Maybe elt -> Maybe elt
f (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m)

-- | Add elements to the map, combining existing values with inserted ones using
-- the given function.
addListToUFM_C
  :: Uniquable key
  => (elt -> elt -> elt)
  -> UniqFM key elt -> [(key,elt)]
  -> UniqFM key elt
addListToUFM_C :: forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqFM key elt -> [(key, elt)] -> UniqFM key elt
addListToUFM_C elt -> elt -> elt
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\UniqFM key elt
m (key
k, elt
v) -> forall key elt.
Uniquable key =>
(elt -> elt -> elt)
-> UniqFM key elt -> key -> elt -> UniqFM key elt
addToUFM_C elt -> elt -> elt
f UniqFM key elt
m key
k elt
v)

adjustUFM :: Uniquable key => (elt -> elt) -> UniqFM key elt -> key -> UniqFM key elt
adjustUFM :: forall key elt.
Uniquable key =>
(elt -> elt) -> UniqFM key elt -> key -> UniqFM key elt
adjustUFM elt -> elt
f (UFM IntMap elt
m) key
k = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (a -> a) -> Int -> IntMap a -> IntMap a
M.adjust elt -> elt
f (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m)

adjustUFM_Directly :: (elt -> elt) -> UniqFM key elt -> Unique -> UniqFM key elt
adjustUFM_Directly :: forall elt key.
(elt -> elt) -> UniqFM key elt -> Unique -> UniqFM key elt
adjustUFM_Directly elt -> elt
f (UFM IntMap elt
m) Unique
u = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (a -> a) -> Int -> IntMap a -> IntMap a
M.adjust elt -> elt
f (Unique -> Int
getKey Unique
u) IntMap elt
m)

delFromUFM :: Uniquable key => UniqFM key elt -> key    -> UniqFM key elt
delFromUFM :: forall key elt.
Uniquable key =>
UniqFM key elt -> key -> UniqFM key elt
delFromUFM (UFM IntMap elt
m) key
k = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. Int -> IntMap a -> IntMap a
M.delete (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m)

delListFromUFM :: Uniquable key => UniqFM key elt -> [key] -> UniqFM key elt
delListFromUFM :: forall key elt.
Uniquable key =>
UniqFM key elt -> [key] -> UniqFM key elt
delListFromUFM = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall key elt.
Uniquable key =>
UniqFM key elt -> key -> UniqFM key elt
delFromUFM

delListFromUFM_Directly :: UniqFM key elt -> [Unique] -> UniqFM key elt
delListFromUFM_Directly :: forall key elt. UniqFM key elt -> [Unique] -> UniqFM key elt
delListFromUFM_Directly = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall key elt. UniqFM key elt -> Unique -> UniqFM key elt
delFromUFM_Directly

delFromUFM_Directly :: UniqFM key elt -> Unique -> UniqFM key elt
delFromUFM_Directly :: forall key elt. UniqFM key elt -> Unique -> UniqFM key elt
delFromUFM_Directly (UFM IntMap elt
m) Unique
u = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. Int -> IntMap a -> IntMap a
M.delete (Unique -> Int
getKey Unique
u) IntMap elt
m)

-- Bindings in right argument shadow those in the left
plusUFM :: UniqFM key elt -> UniqFM key elt -> UniqFM key elt
-- M.union is left-biased, plusUFM should be right-biased.
plusUFM :: forall key elt. UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM (UFM IntMap elt
x) (UFM IntMap elt
y) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. IntMap a -> IntMap a -> IntMap a
M.union IntMap elt
y IntMap elt
x)
     -- Note (M.union y x), with arguments flipped
     -- M.union is left-biased, plusUFM should be right-biased.

plusUFM_C :: (elt -> elt -> elt) -> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM_C :: forall elt key.
(elt -> elt -> elt)
-> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM_C elt -> elt -> elt
f (UFM IntMap elt
x) (UFM IntMap elt
y) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
M.unionWith elt -> elt -> elt
f IntMap elt
x IntMap elt
y)

-- | `plusUFM_CD f m1 d1 m2 d2` merges the maps using `f` as the
-- combinding function and `d1` resp. `d2` as the default value if
-- there is no entry in `m1` reps. `m2`. The domain is the union of
-- the domains of `m1` and `m2`.
--
-- IMPORTANT NOTE: This function strictly applies the modification function
-- and forces the result unlike most the other functions in this module.
--
-- Representative example:
--
-- @
-- plusUFM_CD f {A: 1, B: 2} 23 {B: 3, C: 4} 42
--    == {A: f 1 42, B: f 2 3, C: f 23 4 }
-- @
{-# INLINE plusUFM_CD #-}
plusUFM_CD
  :: (elta -> eltb -> eltc)
  -> UniqFM key elta  -- map X
  -> elta         -- default for X
  -> UniqFM key eltb  -- map Y
  -> eltb         -- default for Y
  -> UniqFM key eltc
plusUFM_CD :: forall elta eltb eltc key.
(elta -> eltb -> eltc)
-> UniqFM key elta
-> elta
-> UniqFM key eltb
-> eltb
-> UniqFM key eltc
plusUFM_CD elta -> eltb -> eltc
f (UFM IntMap elta
xm) elta
dx (UFM IntMap eltb
ym) eltb
dy
  = forall key ele. IntMap ele -> UniqFM key ele
UFM forall a b. (a -> b) -> a -> b
$ forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
MS.mergeWithKey
      (\Int
_ elta
x eltb
y -> forall a. a -> Maybe a
Just (elta
x elta -> eltb -> eltc
`f` eltb
y))
      (forall a b. (a -> b) -> IntMap a -> IntMap b
MS.map (\elta
x -> elta
x elta -> eltb -> eltc
`f` eltb
dy))
      (forall a b. (a -> b) -> IntMap a -> IntMap b
MS.map (\eltb
y -> elta
dx elta -> eltb -> eltc
`f` eltb
y))
      IntMap elta
xm IntMap eltb
ym

-- | `plusUFM_CD2 f m1 m2` merges the maps using `f` as the combining
-- function. Unlike `plusUFM_CD`, a missing value is not defaulted: it is
-- instead passed as `Nothing` to `f`. `f` can never have both its arguments
-- be `Nothing`.
--
-- IMPORTANT NOTE: This function strictly applies the modification function
-- and forces the result.
--
-- `plusUFM_CD2 f m1 m2` is the same as `plusUFM_CD f (mapUFM Just m1) Nothing
-- (mapUFM Just m2) Nothing`.
plusUFM_CD2
  :: (Maybe elta -> Maybe eltb -> eltc)
  -> UniqFM key elta  -- map X
  -> UniqFM key eltb  -- map Y
  -> UniqFM key eltc
plusUFM_CD2 :: forall elta eltb eltc key.
(Maybe elta -> Maybe eltb -> eltc)
-> UniqFM key elta -> UniqFM key eltb -> UniqFM key eltc
plusUFM_CD2 Maybe elta -> Maybe eltb -> eltc
f (UFM IntMap elta
xm) (UFM IntMap eltb
ym)
  = forall key ele. IntMap ele -> UniqFM key ele
UFM forall a b. (a -> b) -> a -> b
$ forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
MS.mergeWithKey
      (\Int
_ elta
x eltb
y -> forall a. a -> Maybe a
Just (forall a. a -> Maybe a
Just elta
x Maybe elta -> Maybe eltb -> eltc
`f` forall a. a -> Maybe a
Just eltb
y))
      (forall a b. (a -> b) -> IntMap a -> IntMap b
MS.map (\elta
x -> forall a. a -> Maybe a
Just elta
x Maybe elta -> Maybe eltb -> eltc
`f` forall a. Maybe a
Nothing))
      (forall a b. (a -> b) -> IntMap a -> IntMap b
MS.map (\eltb
y -> forall a. Maybe a
Nothing Maybe elta -> Maybe eltb -> eltc
`f` forall a. a -> Maybe a
Just eltb
y))
      IntMap elta
xm IntMap eltb
ym

mergeUFM
  :: (elta -> eltb -> Maybe eltc)
  -> (UniqFM key elta -> UniqFM key eltc)  -- map X
  -> (UniqFM key eltb -> UniqFM key eltc) -- map Y
  -> UniqFM key elta
  -> UniqFM key eltb
  -> UniqFM key eltc
mergeUFM :: forall elta eltb eltc key.
(elta -> eltb -> Maybe eltc)
-> (UniqFM key elta -> UniqFM key eltc)
-> (UniqFM key eltb -> UniqFM key eltc)
-> UniqFM key elta
-> UniqFM key eltb
-> UniqFM key eltc
mergeUFM elta -> eltb -> Maybe eltc
f UniqFM key elta -> UniqFM key eltc
g UniqFM key eltb -> UniqFM key eltc
h (UFM IntMap elta
xm) (UFM IntMap eltb
ym)
  = forall key ele. IntMap ele -> UniqFM key ele
UFM forall a b. (a -> b) -> a -> b
$ forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
MS.mergeWithKey
      (\Int
_ elta
x eltb
y -> (elta
x elta -> eltb -> Maybe eltc
`f` eltb
y))
      (coerce :: forall a b. Coercible a b => a -> b
coerce UniqFM key elta -> UniqFM key eltc
g)
      (coerce :: forall a b. Coercible a b => a -> b
coerce UniqFM key eltb -> UniqFM key eltc
h)
      IntMap elta
xm IntMap eltb
ym

plusMaybeUFM_C :: (elt -> elt -> Maybe elt)
               -> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusMaybeUFM_C :: forall elt key.
(elt -> elt -> Maybe elt)
-> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusMaybeUFM_C elt -> elt -> Maybe elt
f (UFM IntMap elt
xm) (UFM IntMap elt
ym)
    = forall key ele. IntMap ele -> UniqFM key ele
UFM forall a b. (a -> b) -> a -> b
$ forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
M.mergeWithKey
        (\Int
_ elt
x elt
y -> elt
x elt -> elt -> Maybe elt
`f` elt
y)
        forall a. a -> a
id
        forall a. a -> a
id
        IntMap elt
xm IntMap elt
ym

plusUFMList :: [UniqFM key elt] -> UniqFM key elt
plusUFMList :: forall key elt. [UniqFM key elt] -> UniqFM key elt
plusUFMList = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall key elt. UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM forall key elt. UniqFM key elt
emptyUFM

sequenceUFMList :: forall key elt. [UniqFM key elt] -> UniqFM key [elt]
sequenceUFMList :: forall key elt. [UniqFM key elt] -> UniqFM key [elt]
sequenceUFMList = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall elta eltb eltc key.
(Maybe elta -> Maybe eltb -> eltc)
-> UniqFM key elta -> UniqFM key eltb -> UniqFM key eltc
plusUFM_CD2 Maybe elt -> Maybe [elt] -> [elt]
cons) forall key elt. UniqFM key elt
emptyUFM
  where
    cons :: Maybe elt -> Maybe [elt] -> [elt]
    cons :: Maybe elt -> Maybe [elt] -> [elt]
cons (Just elt
x) (Just [elt]
ys) = elt
x forall a. a -> [a] -> [a]
: [elt]
ys
    cons Maybe elt
Nothing  (Just [elt]
ys) = [elt]
ys
    cons (Just elt
x) Maybe [elt]
Nothing   = [elt
x]
    cons Maybe elt
Nothing  Maybe [elt]
Nothing   = []

minusUFM :: UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM :: forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM (UFM IntMap elt1
x) (UFM IntMap elt2
y) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b. IntMap a -> IntMap b -> IntMap a
M.difference IntMap elt1
x IntMap elt2
y)

-- | @minusUFC_C f map1 map2@ returns @map1@, except that every mapping @key
-- |-> value1@ in @map1@ that shares a key with a mapping @key |-> value2@ in
-- @map2@ is altered by @f@: @value1@ is replaced by @f value1 value2@, where
-- 'Just' means that the new value is used and 'Nothing' means that the mapping
-- is deleted.
minusUFM_C :: (elt1 -> elt2 -> Maybe elt1) -> UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM_C :: forall elt1 elt2 key.
(elt1 -> elt2 -> Maybe elt1)
-> UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
minusUFM_C elt1 -> elt2 -> Maybe elt1
f (UFM IntMap elt1
x) (UFM IntMap elt2
y) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b. (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
M.differenceWith elt1 -> elt2 -> Maybe elt1
f IntMap elt1
x IntMap elt2
y)

intersectUFM :: UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
intersectUFM :: forall key elt1 elt2.
UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
intersectUFM (UFM IntMap elt1
x) (UFM IntMap elt2
y) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b. IntMap a -> IntMap b -> IntMap a
M.intersection IntMap elt1
x IntMap elt2
y)

intersectUFM_C
  :: (elt1 -> elt2 -> elt3)
  -> UniqFM key elt1
  -> UniqFM key elt2
  -> UniqFM key elt3
intersectUFM_C :: forall elt1 elt2 elt3 key.
(elt1 -> elt2 -> elt3)
-> UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt3
intersectUFM_C elt1 -> elt2 -> elt3
f (UFM IntMap elt1
x) (UFM IntMap elt2
y) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b c. (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
M.intersectionWith elt1 -> elt2 -> elt3
f IntMap elt1
x IntMap elt2
y)

disjointUFM :: UniqFM key elt1 -> UniqFM key elt2 -> Bool
disjointUFM :: forall key elt1 elt2. UniqFM key elt1 -> UniqFM key elt2 -> Bool
disjointUFM (UFM IntMap elt1
x) (UFM IntMap elt2
y) = forall a b. IntMap a -> IntMap b -> Bool
M.disjoint IntMap elt1
x IntMap elt2
y

foldUFM :: (elt -> a -> a) -> a -> UniqFM key elt -> a
foldUFM :: forall elt a key. (elt -> a -> a) -> a -> UniqFM key elt -> a
foldUFM elt -> a -> a
k a
z (UFM IntMap elt
m) = forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr elt -> a -> a
k a
z IntMap elt
m

mapUFM :: (elt1 -> elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapUFM :: forall elt1 elt2 key.
(elt1 -> elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapUFM elt1 -> elt2
f (UFM IntMap elt1
m) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b. (a -> b) -> IntMap a -> IntMap b
M.map elt1 -> elt2
f IntMap elt1
m)

mapMaybeUFM :: (elt1 -> Maybe elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapMaybeUFM :: forall elt1 elt2 key.
(elt1 -> Maybe elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapMaybeUFM elt1 -> Maybe elt2
f (UFM IntMap elt1
m) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
M.mapMaybe elt1 -> Maybe elt2
f IntMap elt1
m)

mapUFM_Directly :: (Unique -> elt1 -> elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapUFM_Directly :: forall elt1 elt2 key.
(Unique -> elt1 -> elt2) -> UniqFM key elt1 -> UniqFM key elt2
mapUFM_Directly Unique -> elt1 -> elt2
f (UFM IntMap elt1
m) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a b. (Int -> a -> b) -> IntMap a -> IntMap b
M.mapWithKey (Unique -> elt1 -> elt2
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Uniquable a => a -> Unique
getUnique) IntMap elt1
m)

filterUFM :: (elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM :: forall elt key. (elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM elt -> Bool
p (UFM IntMap elt
m) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (a -> Bool) -> IntMap a -> IntMap a
M.filter elt -> Bool
p IntMap elt
m)

filterUFM_Directly :: (Unique -> elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM_Directly :: forall elt key.
(Unique -> elt -> Bool) -> UniqFM key elt -> UniqFM key elt
filterUFM_Directly Unique -> elt -> Bool
p (UFM IntMap elt
m) = forall key ele. IntMap ele -> UniqFM key ele
UFM (forall a. (Int -> a -> Bool) -> IntMap a -> IntMap a
M.filterWithKey (Unique -> elt -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Uniquable a => a -> Unique
getUnique) IntMap elt
m)

partitionUFM :: (elt -> Bool) -> UniqFM key elt -> (UniqFM key elt, UniqFM key elt)
partitionUFM :: forall elt key.
(elt -> Bool) -> UniqFM key elt -> (UniqFM key elt, UniqFM key elt)
partitionUFM elt -> Bool
p (UFM IntMap elt
m) =
  case forall a. (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
M.partition elt -> Bool
p IntMap elt
m of
    (IntMap elt
left, IntMap elt
right) -> (forall key ele. IntMap ele -> UniqFM key ele
UFM IntMap elt
left, forall key ele. IntMap ele -> UniqFM key ele
UFM IntMap elt
right)

sizeUFM :: UniqFM key elt -> Int
sizeUFM :: forall key elt. UniqFM key elt -> Int
sizeUFM (UFM IntMap elt
m) = forall a. IntMap a -> Int
M.size IntMap elt
m

elemUFM :: Uniquable key => key -> UniqFM key elt -> Bool
elemUFM :: forall key elt. Uniquable key => key -> UniqFM key elt -> Bool
elemUFM key
k (UFM IntMap elt
m) = forall a. Int -> IntMap a -> Bool
M.member (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m

elemUFM_Directly :: Unique -> UniqFM key elt -> Bool
elemUFM_Directly :: forall key elt. Unique -> UniqFM key elt -> Bool
elemUFM_Directly Unique
u (UFM IntMap elt
m) = forall a. Int -> IntMap a -> Bool
M.member (Unique -> Int
getKey Unique
u) IntMap elt
m

lookupUFM :: Uniquable key => UniqFM key elt -> key -> Maybe elt
lookupUFM :: forall key elt. Uniquable key => UniqFM key elt -> key -> Maybe elt
lookupUFM (UFM IntMap elt
m) key
k = forall a. Int -> IntMap a -> Maybe a
M.lookup (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m

-- when you've got the Unique already
lookupUFM_Directly :: UniqFM key elt -> Unique -> Maybe elt
lookupUFM_Directly :: forall key elt. UniqFM key elt -> Unique -> Maybe elt
lookupUFM_Directly (UFM IntMap elt
m) Unique
u = forall a. Int -> IntMap a -> Maybe a
M.lookup (Unique -> Int
getKey Unique
u) IntMap elt
m

lookupWithDefaultUFM :: Uniquable key => UniqFM key elt -> elt -> key -> elt
lookupWithDefaultUFM :: forall key elt.
Uniquable key =>
UniqFM key elt -> elt -> key -> elt
lookupWithDefaultUFM (UFM IntMap elt
m) elt
v key
k = forall a. a -> Int -> IntMap a -> a
M.findWithDefault elt
v (Unique -> Int
getKey forall a b. (a -> b) -> a -> b
$ forall a. Uniquable a => a -> Unique
getUnique key
k) IntMap elt
m

lookupWithDefaultUFM_Directly :: UniqFM key elt -> elt -> Unique -> elt
lookupWithDefaultUFM_Directly :: forall key elt. UniqFM key elt -> elt -> Unique -> elt
lookupWithDefaultUFM_Directly (UFM IntMap elt
m) elt
v Unique
u = forall a. a -> Int -> IntMap a -> a
M.findWithDefault elt
v (Unique -> Int
getKey Unique
u) IntMap elt
m

ufmToSet_Directly :: UniqFM key elt -> S.IntSet
ufmToSet_Directly :: forall key elt. UniqFM key elt -> IntSet
ufmToSet_Directly (UFM IntMap elt
m) = forall a. IntMap a -> IntSet
M.keysSet IntMap elt
m

anyUFM :: (elt -> Bool) -> UniqFM key elt -> Bool
anyUFM :: forall elt key. (elt -> Bool) -> UniqFM key elt -> Bool
anyUFM elt -> Bool
p (UFM IntMap elt
m) = forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr (Bool -> Bool -> Bool
(||) forall b c a. (b -> c) -> (a -> b) -> a -> c
. elt -> Bool
p) Bool
False IntMap elt
m

allUFM :: (elt -> Bool) -> UniqFM key elt -> Bool
allUFM :: forall elt key. (elt -> Bool) -> UniqFM key elt -> Bool
allUFM elt -> Bool
p (UFM IntMap elt
m) = forall a b. (a -> b -> b) -> b -> IntMap a -> b
M.foldr (Bool -> Bool -> Bool
(&&) forall b c a. (b -> c) -> (a -> b) -> a -> c
. elt -> Bool
p) Bool
True IntMap elt
m

seqEltsUFM :: (elt -> ()) -> UniqFM key elt -> ()
seqEltsUFM :: forall elt key. (elt -> ()) -> UniqFM key elt -> ()
seqEltsUFM elt -> ()
seqElt = forall elt a key. (elt -> a -> a) -> a -> UniqFM key elt -> a
foldUFM (\elt
v ()
rest -> elt -> ()
seqElt elt
v seq :: forall a b. a -> b -> b
`seq` ()
rest) ()

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetEltsUFM :: UniqFM key elt -> [elt]
nonDetEltsUFM :: forall key elt. UniqFM key elt -> [elt]
nonDetEltsUFM (UFM IntMap elt
m) = forall a. IntMap a -> [a]
M.elems IntMap elt
m

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetKeysUFM :: UniqFM key elt -> [Unique]
nonDetKeysUFM :: forall key elt. UniqFM key elt -> [Unique]
nonDetKeysUFM (UFM IntMap elt
m) = forall a b. (a -> b) -> [a] -> [b]
map forall a. Uniquable a => a -> Unique
getUnique forall a b. (a -> b) -> a -> b
$ forall a. IntMap a -> [Int]
M.keys IntMap elt
m

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetStrictFoldUFM :: (elt -> a -> a) -> a -> UniqFM key elt -> a
nonDetStrictFoldUFM :: forall elt a key. (elt -> a -> a) -> a -> UniqFM key elt -> a
nonDetStrictFoldUFM elt -> a -> a
k a
z (UFM IntMap elt
m) = forall a b. (a -> b -> a) -> a -> IntMap b -> a
M.foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip elt -> a -> a
k) a
z IntMap elt
m
{-# INLINE nonDetStrictFoldUFM #-}

-- | In essence foldM
-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
{-# INLINE nonDetStrictFoldUFM_DirectlyM #-} -- Allow specialization
nonDetStrictFoldUFM_DirectlyM :: (Monad m) => (Unique -> b -> elt -> m b) -> b -> UniqFM key elt -> m b
nonDetStrictFoldUFM_DirectlyM :: forall (m :: * -> *) b elt key.
Monad m =>
(Unique -> b -> elt -> m b) -> b -> UniqFM key elt -> m b
nonDetStrictFoldUFM_DirectlyM Unique -> b -> elt -> m b
f b
z0 (UFM IntMap elt
xs) = forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
M.foldrWithKey Int -> elt -> (b -> m b) -> b -> m b
c forall (m :: * -> *) a. Monad m => a -> m a
return IntMap elt
xs b
z0
  -- See Note [List fusion and continuations in 'c']
  where c :: Int -> elt -> (b -> m b) -> b -> m b
c Int
u elt
x b -> m b
k b
z = Unique -> b -> elt -> m b
f (forall a. Uniquable a => a -> Unique
getUnique Int
u) b
z elt
x forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= b -> m b
k
        {-# INLINE c #-}

nonDetStrictFoldUFM_Directly:: (Unique -> elt -> a -> a) -> a -> UniqFM key elt -> a
nonDetStrictFoldUFM_Directly :: forall elt a key.
(Unique -> elt -> a -> a) -> a -> UniqFM key elt -> a
nonDetStrictFoldUFM_Directly Unique -> elt -> a -> a
k a
z (UFM IntMap elt
m) = forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
M.foldlWithKey' (\a
z' Int
i elt
x -> Unique -> elt -> a -> a
k (forall a. Uniquable a => a -> Unique
getUnique Int
i) elt
x a
z') a
z IntMap elt
m
{-# INLINE nonDetStrictFoldUFM_Directly #-}

-- See Note [Deterministic UniqFM] to learn about nondeterminism.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
nonDetUFMToList :: UniqFM key elt -> [(Unique, elt)]
nonDetUFMToList :: forall key elt. UniqFM key elt -> [(Unique, elt)]
nonDetUFMToList (UFM IntMap elt
m) = forall a b. (a -> b) -> [a] -> [b]
map (\(Int
k, elt
v) -> (forall a. Uniquable a => a -> Unique
getUnique Int
k, elt
v)) forall a b. (a -> b) -> a -> b
$ forall a. IntMap a -> [(Int, a)]
M.toList IntMap elt
m

-- | A wrapper around 'UniqFM' with the sole purpose of informing call sites
-- that the provided 'Foldable' and 'Traversable' instances are
-- nondeterministic.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
-- See Note [Deterministic UniqFM] in "GHC.Types.Unique.DFM" to learn about determinism.
newtype NonDetUniqFM key ele = NonDetUniqFM { forall key ele. NonDetUniqFM key ele -> UniqFM key ele
getNonDet :: UniqFM key ele }
  deriving (forall a b. a -> NonDetUniqFM key b -> NonDetUniqFM key a
forall a b. (a -> b) -> NonDetUniqFM key a -> NonDetUniqFM key b
forall key a b. a -> NonDetUniqFM key b -> NonDetUniqFM key a
forall key a b.
(a -> b) -> NonDetUniqFM key a -> NonDetUniqFM key b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> NonDetUniqFM key b -> NonDetUniqFM key a
$c<$ :: forall key a b. a -> NonDetUniqFM key b -> NonDetUniqFM key a
fmap :: forall a b. (a -> b) -> NonDetUniqFM key a -> NonDetUniqFM key b
$cfmap :: forall key a b.
(a -> b) -> NonDetUniqFM key a -> NonDetUniqFM key b
Functor)

-- | Inherently nondeterministic.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
-- See Note [Deterministic UniqFM] in "GHC.Types.Unique.DFM" to learn about determinism.
instance forall key. Foldable (NonDetUniqFM key) where
  foldr :: forall a b. (a -> b -> b) -> b -> NonDetUniqFM key a -> b
foldr a -> b -> b
f b
z (NonDetUniqFM (UFM IntMap a
m)) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
z IntMap a
m

-- | Inherently nondeterministic.
-- If you use this please provide a justification why it doesn't introduce
-- nondeterminism.
-- See Note [Deterministic UniqFM] in "GHC.Types.Unique.DFM" to learn about determinism.
instance forall key. Traversable (NonDetUniqFM key) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NonDetUniqFM key a -> f (NonDetUniqFM key b)
traverse a -> f b
f (NonDetUniqFM (UFM IntMap a
m)) = forall key ele. UniqFM key ele -> NonDetUniqFM key ele
NonDetUniqFM forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key ele. IntMap ele -> UniqFM key ele
UFM forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f IntMap a
m

ufmToIntMap :: UniqFM key elt -> M.IntMap elt
ufmToIntMap :: forall key elt. UniqFM key elt -> IntMap elt
ufmToIntMap (UFM IntMap elt
m) = IntMap elt
m

unsafeIntMapToUFM :: M.IntMap elt -> UniqFM key elt
unsafeIntMapToUFM :: forall elt key. IntMap elt -> UniqFM key elt
unsafeIntMapToUFM = forall key ele. IntMap ele -> UniqFM key ele
UFM

-- | Cast the key domain of a UniqFM.
--
-- As long as the domains don't overlap in their uniques
-- this is safe.
unsafeCastUFMKey :: UniqFM key1 elt -> UniqFM key2 elt
unsafeCastUFMKey :: forall key1 elt key2. UniqFM key1 elt -> UniqFM key2 elt
unsafeCastUFMKey (UFM IntMap elt
m) = forall key ele. IntMap ele -> UniqFM key ele
UFM IntMap elt
m

-- Determines whether two 'UniqFM's contain the same keys.
equalKeysUFM :: UniqFM key a -> UniqFM key b -> Bool
equalKeysUFM :: forall key elt1 elt2. UniqFM key elt1 -> UniqFM key elt2 -> Bool
equalKeysUFM (UFM IntMap a
m1) (UFM IntMap b
m2) = forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq (\a
_ b
_ -> Bool
True) IntMap a
m1 IntMap b
m2

-- Instances

instance Semi.Semigroup (UniqFM key a) where
  <> :: UniqFM key a -> UniqFM key a -> UniqFM key a
(<>) = forall key elt. UniqFM key elt -> UniqFM key elt -> UniqFM key elt
plusUFM

instance Monoid (UniqFM key a) where
    mempty :: UniqFM key a
mempty = forall key elt. UniqFM key elt
emptyUFM
    mappend :: UniqFM key a -> UniqFM key a -> UniqFM key a
mappend = forall a. Semigroup a => a -> a -> a
(Semi.<>)

-- Output-ery

instance Outputable a => Outputable (UniqFM key a) where
    ppr :: UniqFM key a -> SDoc
ppr UniqFM key a
ufm = forall a key. (a -> SDoc) -> UniqFM key a -> SDoc
pprUniqFM forall a. Outputable a => a -> SDoc
ppr UniqFM key a
ufm

pprUniqFM :: (a -> SDoc) -> UniqFM key a -> SDoc
pprUniqFM :: forall a key. (a -> SDoc) -> UniqFM key a -> SDoc
pprUniqFM a -> SDoc
ppr_elt UniqFM key a
ufm
  = forall doc. IsLine doc => doc -> doc
brackets forall a b. (a -> b) -> a -> b
$ forall doc. IsLine doc => [doc] -> doc
fsep forall a b. (a -> b) -> a -> b
$ forall doc. IsLine doc => doc -> [doc] -> [doc]
punctuate forall doc. IsLine doc => doc
comma forall a b. (a -> b) -> a -> b
$
    [ forall a. Outputable a => a -> SDoc
ppr Unique
uq forall doc. IsLine doc => doc -> doc -> doc
<+> forall doc. IsLine doc => String -> doc
text String
":->" forall doc. IsLine doc => doc -> doc -> doc
<+> a -> SDoc
ppr_elt a
elt
    | (Unique
uq, a
elt) <- forall key elt. UniqFM key elt -> [(Unique, elt)]
nonDetUFMToList UniqFM key a
ufm ]
  -- It's OK to use nonDetUFMToList here because we only use it for
  -- pretty-printing.

-- | Pretty-print a non-deterministic set.
-- The order of variables is non-deterministic and for pretty-printing that
-- shouldn't be a problem.
-- Having this function helps contain the non-determinism created with
-- nonDetEltsUFM.
pprUFM :: UniqFM 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
pprUFM :: forall key a. UniqFM key a -> ([a] -> SDoc) -> SDoc
pprUFM UniqFM key a
ufm [a] -> SDoc
pp = [a] -> SDoc
pp (forall key elt. UniqFM key elt -> [elt]
nonDetEltsUFM UniqFM key a
ufm)

-- | Pretty-print a non-deterministic set.
-- The order of variables is non-deterministic and for pretty-printing that
-- shouldn't be a problem.
-- Having this function helps contain the non-determinism created with
-- nonDetUFMToList.
pprUFMWithKeys
       :: UniqFM key a                -- ^ The things to be pretty printed
       -> ([(Unique, a)] -> SDoc) -- ^ The pretty printing function to use on the elements
       -> SDoc                    -- ^ 'SDoc' where the things have been pretty
                                  -- printed
pprUFMWithKeys :: forall key a. UniqFM key a -> ([(Unique, a)] -> SDoc) -> SDoc
pprUFMWithKeys UniqFM key a
ufm [(Unique, a)] -> SDoc
pp = [(Unique, a)] -> SDoc
pp (forall key elt. UniqFM key elt -> [(Unique, elt)]
nonDetUFMToList UniqFM key a
ufm)

-- | Determines the pluralisation suffix appropriate for the length of a set
-- in the same way that plural from Outputable does for lists.
pluralUFM :: UniqFM key a -> SDoc
pluralUFM :: forall key a. UniqFM key a -> SDoc
pluralUFM UniqFM key a
ufm
  | forall key elt. UniqFM key elt -> Int
sizeUFM UniqFM key a
ufm forall a. Eq a => a -> a -> Bool
== Int
1 = forall doc. IsOutput doc => doc
empty
  | Bool
otherwise = forall doc. IsLine doc => Char -> doc
char Char
's'