{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998
-}

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
module TrieMap(
   -- * Maps over 'Maybe' values
   MaybeMap,
   -- * Maps over 'List' values
   ListMap,
   -- * Maps over 'Literal's
   LiteralMap,
   -- * 'TrieMap' class
   TrieMap(..), insertTM, deleteTM,

   -- * Things helpful for adding additional Instances.
   (>.>), (|>), (|>>), XT,
   foldMaybe,
   -- * Map for leaf compression
   GenMap,
   lkG, xtG, mapG, fdG,
   xtList, lkList

 ) where

import GhcPrelude

import Literal
import UniqDFM
import Unique( Unique )

import qualified Data.Map    as Map
import qualified Data.IntMap as IntMap
import Outputable
import Control.Monad( (>=>) )

{-
This module implements TrieMaps, which are finite mappings
whose key is a structured value like a CoreExpr or Type.

This file implements tries over general data structures.
Implementation for tries over Core Expressions/Types are
available in coreSyn/TrieMap.

The regular pattern for handling TrieMaps on data structures was first
described (to my knowledge) in Connelly and Morris's 1995 paper "A
generalization of the Trie Data Structure"; there is also an accessible
description of the idea in Okasaki's book "Purely Functional Data
Structures", Section 10.3.2

************************************************************************
*                                                                      *
                   The TrieMap class
*                                                                      *
************************************************************************
-}

type XT a = Maybe a -> Maybe a  -- How to alter a non-existent elt (Nothing)
                                --               or an existing elt (Just)

class TrieMap m where
   type Key m :: *
   emptyTM  :: m a
   lookupTM :: forall b. Key m -> m b -> Maybe b
   alterTM  :: forall b. Key m -> XT b -> m b -> m b
   mapTM    :: (a->b) -> m a -> m b

   foldTM   :: (a -> b -> b) -> m a -> b -> b
      -- The unusual argument order here makes
      -- it easy to compose calls to foldTM;
      -- see for example fdE below

insertTM :: TrieMap m => Key m -> a -> m a -> m a
insertTM :: Key m -> a -> m a -> m a
insertTM Key m
k a
v m a
m = Key m -> XT a -> m a -> m a
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM Key m
k (\Maybe a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
v) m a
m

deleteTM :: TrieMap m => Key m -> m a -> m a
deleteTM :: Key m -> m a -> m a
deleteTM Key m
k m a
m = Key m -> XT a -> m a -> m a
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM Key m
k (\Maybe a
_ -> Maybe a
forall a. Maybe a
Nothing) m a
m

----------------------
-- Recall that
--   Control.Monad.(>=>) :: (a -> Maybe b) -> (b -> Maybe c) -> a -> Maybe c

(>.>) :: (a -> b) -> (b -> c) -> a -> c
-- Reverse function composition (do f first, then g)
infixr 1 >.>
(a -> b
f >.> :: (a -> b) -> (b -> c) -> a -> c
>.> b -> c
g) a
x = b -> c
g (a -> b
f a
x)
infixr 1 |>, |>>

(|>) :: a -> (a->b) -> b     -- Reverse application
a
x |> :: a -> (a -> b) -> b
|> a -> b
f = a -> b
f a
x

----------------------
(|>>) :: TrieMap m2
      => (XT (m2 a) -> m1 (m2 a) -> m1 (m2 a))
      -> (m2 a -> m2 a)
      -> m1 (m2 a) -> m1 (m2 a)
|>> :: (XT (m2 a) -> m1 (m2 a) -> m1 (m2 a))
-> (m2 a -> m2 a) -> m1 (m2 a) -> m1 (m2 a)
(|>>) XT (m2 a) -> m1 (m2 a) -> m1 (m2 a)
f m2 a -> m2 a
g = XT (m2 a) -> m1 (m2 a) -> m1 (m2 a)
f (m2 a -> Maybe (m2 a)
forall a. a -> Maybe a
Just (m2 a -> Maybe (m2 a)) -> (Maybe (m2 a) -> m2 a) -> XT (m2 a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m2 a -> m2 a
g (m2 a -> m2 a) -> (Maybe (m2 a) -> m2 a) -> Maybe (m2 a) -> m2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe (m2 a) -> m2 a
forall (m :: * -> *) a. TrieMap m => Maybe (m a) -> m a
deMaybe)

deMaybe :: TrieMap m => Maybe (m a) -> m a
deMaybe :: Maybe (m a) -> m a
deMaybe Maybe (m a)
Nothing  = m a
forall (m :: * -> *) a. TrieMap m => m a
emptyTM
deMaybe (Just m a
m) = m a
m

{-
************************************************************************
*                                                                      *
                   IntMaps
*                                                                      *
************************************************************************
-}

instance TrieMap IntMap.IntMap where
  type Key IntMap.IntMap = Int
  emptyTM :: IntMap a
emptyTM = IntMap a
forall a. IntMap a
IntMap.empty
  lookupTM :: Key IntMap -> IntMap b -> Maybe b
lookupTM Key IntMap
k IntMap b
m = Key -> IntMap b -> Maybe b
forall a. Key -> IntMap a -> Maybe a
IntMap.lookup Key
Key IntMap
k IntMap b
m
  alterTM :: Key IntMap -> XT b -> IntMap b -> IntMap b
alterTM = Key IntMap -> XT b -> IntMap b -> IntMap b
forall a. Key -> XT a -> IntMap a -> IntMap a
xtInt
  foldTM :: (a -> b -> b) -> IntMap a -> b -> b
foldTM a -> b -> b
k IntMap a
m b
z = (a -> b -> b) -> b -> IntMap a -> b
forall a b. (a -> b -> b) -> b -> IntMap a -> b
IntMap.foldr a -> b -> b
k b
z IntMap a
m
  mapTM :: (a -> b) -> IntMap a -> IntMap b
mapTM a -> b
f IntMap a
m = (a -> b) -> IntMap a -> IntMap b
forall a b. (a -> b) -> IntMap a -> IntMap b
IntMap.map a -> b
f IntMap a
m

xtInt :: Int -> XT a -> IntMap.IntMap a -> IntMap.IntMap a
xtInt :: Key -> XT a -> IntMap a -> IntMap a
xtInt Key
k XT a
f IntMap a
m = XT a -> Key -> IntMap a -> IntMap a
forall a. (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
IntMap.alter XT a
f Key
k IntMap a
m

instance Ord k => TrieMap (Map.Map k) where
  type Key (Map.Map k) = k
  emptyTM :: Map k a
emptyTM = Map k a
forall k a. Map k a
Map.empty
  lookupTM :: Key (Map k) -> Map k b -> Maybe b
lookupTM = Key (Map k) -> Map k b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup
  alterTM :: Key (Map k) -> XT b -> Map k b -> Map k b
alterTM Key (Map k)
k XT b
f Map k b
m = XT b -> k -> Map k b -> Map k b
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter XT b
f k
Key (Map k)
k Map k b
m
  foldTM :: (a -> b -> b) -> Map k a -> b -> b
foldTM a -> b -> b
k Map k a
m b
z = (a -> b -> b) -> b -> Map k a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr a -> b -> b
k b
z Map k a
m
  mapTM :: (a -> b) -> Map k a -> Map k b
mapTM a -> b
f Map k a
m = (a -> b) -> Map k a -> Map k b
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map a -> b
f Map k a
m


{-
Note [foldTM determinism]
~~~~~~~~~~~~~~~~~~~~~~~~~
We want foldTM to be deterministic, which is why we have an instance of
TrieMap for UniqDFM, but not for UniqFM. Here's an example of some things that
go wrong if foldTM is nondeterministic. Consider:

  f a b = return (a <> b)

Depending on the order that the typechecker generates constraints you
get either:

  f :: (Monad m, Monoid a) => a -> a -> m a

or:

  f :: (Monoid a, Monad m) => a -> a -> m a

The generated code will be different after desugaring as the dictionaries
will be bound in different orders, leading to potential ABI incompatibility.

One way to solve this would be to notice that the typeclasses could be
sorted alphabetically.

Unfortunately that doesn't quite work with this example:

  f a b = let x = a <> a; y = b <> b in x

where you infer:

  f :: (Monoid m, Monoid m1) => m1 -> m -> m1

or:

  f :: (Monoid m1, Monoid m) => m1 -> m -> m1

Here you could decide to take the order of the type variables in the type
according to depth first traversal and use it to order the constraints.

The real trouble starts when the user enables incoherent instances and
the compiler has to make an arbitrary choice. Consider:

  class T a b where
    go :: a -> b -> String

  instance (Show b) => T Int b where
    go a b = show a ++ show b

  instance (Show a) => T a Bool where
    go a b = show a ++ show b

  f = go 10 True

GHC is free to choose either dictionary to implement f, but for the sake of
determinism we'd like it to be consistent when compiling the same sources
with the same flags.

inert_dicts :: DictMap is implemented with a TrieMap. In getUnsolvedInerts it
gets converted to a bag of (Wanted) Cts using a fold. Then in
solve_simple_wanteds it's merged with other WantedConstraints. We want the
conversion to a bag to be deterministic. For that purpose we use UniqDFM
instead of UniqFM to implement the TrieMap.

See Note [Deterministic UniqFM] in UniqDFM for more details on how it's made
deterministic.
-}

instance TrieMap UniqDFM where
  type Key UniqDFM = Unique
  emptyTM :: UniqDFM a
emptyTM = UniqDFM a
forall a. UniqDFM a
emptyUDFM
  lookupTM :: Key UniqDFM -> UniqDFM b -> Maybe b
lookupTM Key UniqDFM
k UniqDFM b
m = UniqDFM b -> Unique -> Maybe b
forall key elt. Uniquable key => UniqDFM elt -> key -> Maybe elt
lookupUDFM UniqDFM b
m Unique
Key UniqDFM
k
  alterTM :: Key UniqDFM -> XT b -> UniqDFM b -> UniqDFM b
alterTM Key UniqDFM
k XT b
f UniqDFM b
m = XT b -> UniqDFM b -> Unique -> UniqDFM b
forall key elt.
Uniquable key =>
(Maybe elt -> Maybe elt) -> UniqDFM elt -> key -> UniqDFM elt
alterUDFM XT b
f UniqDFM b
m Unique
Key UniqDFM
k
  foldTM :: (a -> b -> b) -> UniqDFM a -> b -> b
foldTM a -> b -> b
k UniqDFM a
m b
z = (a -> b -> b) -> b -> UniqDFM a -> b
forall elt a. (elt -> a -> a) -> a -> UniqDFM elt -> a
foldUDFM a -> b -> b
k b
z UniqDFM a
m
  mapTM :: (a -> b) -> UniqDFM a -> UniqDFM b
mapTM a -> b
f UniqDFM a
m = (a -> b) -> UniqDFM a -> UniqDFM b
forall a b. (a -> b) -> UniqDFM a -> UniqDFM b
mapUDFM a -> b
f UniqDFM a
m

{-
************************************************************************
*                                                                      *
                   Maybes
*                                                                      *
************************************************************************

If              m is a map from k -> val
then (MaybeMap m) is a map from (Maybe k) -> val
-}

data MaybeMap m a = MM { MaybeMap m a -> Maybe a
mm_nothing  :: Maybe a, MaybeMap m a -> m a
mm_just :: m a }

instance TrieMap m => TrieMap (MaybeMap m) where
   type Key (MaybeMap m) = Maybe (Key m)
   emptyTM :: MaybeMap m a
emptyTM  = MM :: forall (m :: * -> *) a. Maybe a -> m a -> MaybeMap m a
MM { mm_nothing :: Maybe a
mm_nothing = Maybe a
forall a. Maybe a
Nothing, mm_just :: m a
mm_just = m a
forall (m :: * -> *) a. TrieMap m => m a
emptyTM }
   lookupTM :: Key (MaybeMap m) -> MaybeMap m b -> Maybe b
lookupTM = (forall b. Key m -> m b -> Maybe b)
-> Maybe (Key m) -> MaybeMap m b -> Maybe b
forall k (m :: * -> *) a.
(forall b. k -> m b -> Maybe b)
-> Maybe k -> MaybeMap m a -> Maybe a
lkMaybe forall b. Key m -> m b -> Maybe b
forall (m :: * -> *) b. TrieMap m => Key m -> m b -> Maybe b
lookupTM
   alterTM :: Key (MaybeMap m) -> XT b -> MaybeMap m b -> MaybeMap m b
alterTM  = (forall b. Key m -> XT b -> m b -> m b)
-> Maybe (Key m) -> XT b -> MaybeMap m b -> MaybeMap m b
forall k (m :: * -> *) a.
(forall b. k -> XT b -> m b -> m b)
-> Maybe k -> XT a -> MaybeMap m a -> MaybeMap m a
xtMaybe forall b. Key m -> XT b -> m b -> m b
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM
   foldTM :: (a -> b -> b) -> MaybeMap m a -> b -> b
foldTM   = (a -> b -> b) -> MaybeMap m a -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> MaybeMap m a -> b -> b
fdMaybe
   mapTM :: (a -> b) -> MaybeMap m a -> MaybeMap m b
mapTM    = (a -> b) -> MaybeMap m a -> MaybeMap m b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b) -> MaybeMap m a -> MaybeMap m b
mapMb

mapMb :: TrieMap m => (a->b) -> MaybeMap m a -> MaybeMap m b
mapMb :: (a -> b) -> MaybeMap m a -> MaybeMap m b
mapMb a -> b
f (MM { mm_nothing :: forall (m :: * -> *) a. MaybeMap m a -> Maybe a
mm_nothing = Maybe a
mn, mm_just :: forall (m :: * -> *) a. MaybeMap m a -> m a
mm_just = m a
mj })
  = MM :: forall (m :: * -> *) a. Maybe a -> m a -> MaybeMap m a
MM { mm_nothing :: Maybe b
mm_nothing = (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Maybe a
mn, mm_just :: m b
mm_just = (a -> b) -> m a -> m b
forall (m :: * -> *) a b. TrieMap m => (a -> b) -> m a -> m b
mapTM a -> b
f m a
mj }

lkMaybe :: (forall b. k -> m b -> Maybe b)
        -> Maybe k -> MaybeMap m a -> Maybe a
lkMaybe :: (forall b. k -> m b -> Maybe b)
-> Maybe k -> MaybeMap m a -> Maybe a
lkMaybe forall b. k -> m b -> Maybe b
_  Maybe k
Nothing  = MaybeMap m a -> Maybe a
forall (m :: * -> *) a. MaybeMap m a -> Maybe a
mm_nothing
lkMaybe forall b. k -> m b -> Maybe b
lk (Just k
x) = MaybeMap m a -> m a
forall (m :: * -> *) a. MaybeMap m a -> m a
mm_just (MaybeMap m a -> m a)
-> (m a -> Maybe a) -> MaybeMap m a -> Maybe a
forall a b c. (a -> b) -> (b -> c) -> a -> c
>.> k -> m a -> Maybe a
forall b. k -> m b -> Maybe b
lk k
x

xtMaybe :: (forall b. k -> XT b -> m b -> m b)
        -> Maybe k -> XT a -> MaybeMap m a -> MaybeMap m a
xtMaybe :: (forall b. k -> XT b -> m b -> m b)
-> Maybe k -> XT a -> MaybeMap m a -> MaybeMap m a
xtMaybe forall b. k -> XT b -> m b -> m b
_  Maybe k
Nothing  XT a
f MaybeMap m a
m = MaybeMap m a
m { mm_nothing :: Maybe a
mm_nothing  = XT a
f (MaybeMap m a -> Maybe a
forall (m :: * -> *) a. MaybeMap m a -> Maybe a
mm_nothing MaybeMap m a
m) }
xtMaybe forall b. k -> XT b -> m b -> m b
tr (Just k
x) XT a
f MaybeMap m a
m = MaybeMap m a
m { mm_just :: m a
mm_just = MaybeMap m a -> m a
forall (m :: * -> *) a. MaybeMap m a -> m a
mm_just MaybeMap m a
m m a -> (m a -> m a) -> m a
forall a b. a -> (a -> b) -> b
|> k -> XT a -> m a -> m a
forall b. k -> XT b -> m b -> m b
tr k
x XT a
f }

fdMaybe :: TrieMap m => (a -> b -> b) -> MaybeMap m a -> b -> b
fdMaybe :: (a -> b -> b) -> MaybeMap m a -> b -> b
fdMaybe a -> b -> b
k MaybeMap m a
m = (a -> b -> b) -> Maybe a -> b -> b
forall a b. (a -> b -> b) -> Maybe a -> b -> b
foldMaybe a -> b -> b
k (MaybeMap m a -> Maybe a
forall (m :: * -> *) a. MaybeMap m a -> Maybe a
mm_nothing MaybeMap m a
m)
            (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> m a -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> m a -> b -> b
foldTM a -> b -> b
k (MaybeMap m a -> m a
forall (m :: * -> *) a. MaybeMap m a -> m a
mm_just MaybeMap m a
m)

{-
************************************************************************
*                                                                      *
                   Lists
*                                                                      *
************************************************************************
-}

data ListMap m a
  = LM { ListMap m a -> Maybe a
lm_nil  :: Maybe a
       , ListMap m a -> m (ListMap m a)
lm_cons :: m (ListMap m a) }

instance TrieMap m => TrieMap (ListMap m) where
   type Key (ListMap m) = [Key m]
   emptyTM :: ListMap m a
emptyTM  = LM :: forall (m :: * -> *) a. Maybe a -> m (ListMap m a) -> ListMap m a
LM { lm_nil :: Maybe a
lm_nil = Maybe a
forall a. Maybe a
Nothing, lm_cons :: m (ListMap m a)
lm_cons = m (ListMap m a)
forall (m :: * -> *) a. TrieMap m => m a
emptyTM }
   lookupTM :: Key (ListMap m) -> ListMap m b -> Maybe b
lookupTM = (forall b. Key m -> m b -> Maybe b)
-> [Key m] -> ListMap m b -> Maybe b
forall (m :: * -> *) k a.
TrieMap m =>
(forall b. k -> m b -> Maybe b) -> [k] -> ListMap m a -> Maybe a
lkList forall b. Key m -> m b -> Maybe b
forall (m :: * -> *) b. TrieMap m => Key m -> m b -> Maybe b
lookupTM
   alterTM :: Key (ListMap m) -> XT b -> ListMap m b -> ListMap m b
alterTM  = (forall b. Key m -> XT b -> m b -> m b)
-> [Key m] -> XT b -> ListMap m b -> ListMap m b
forall (m :: * -> *) k a.
TrieMap m =>
(forall b. k -> XT b -> m b -> m b)
-> [k] -> XT a -> ListMap m a -> ListMap m a
xtList forall b. Key m -> XT b -> m b -> m b
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM
   foldTM :: (a -> b -> b) -> ListMap m a -> b -> b
foldTM   = (a -> b -> b) -> ListMap m a -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> ListMap m a -> b -> b
fdList
   mapTM :: (a -> b) -> ListMap m a -> ListMap m b
mapTM    = (a -> b) -> ListMap m a -> ListMap m b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b) -> ListMap m a -> ListMap m b
mapList

instance (TrieMap m, Outputable a) => Outputable (ListMap m a) where
  ppr :: ListMap m a -> SDoc
ppr ListMap m a
m = String -> SDoc
text String
"List elts" SDoc -> SDoc -> SDoc
<+> [a] -> SDoc
forall a. Outputable a => a -> SDoc
ppr ((a -> [a] -> [a]) -> ListMap m a -> [a] -> [a]
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> m a -> b -> b
foldTM (:) ListMap m a
m [])

mapList :: TrieMap m => (a->b) -> ListMap m a -> ListMap m b
mapList :: (a -> b) -> ListMap m a -> ListMap m b
mapList a -> b
f (LM { lm_nil :: forall (m :: * -> *) a. ListMap m a -> Maybe a
lm_nil = Maybe a
mnil, lm_cons :: forall (m :: * -> *) a. ListMap m a -> m (ListMap m a)
lm_cons = m (ListMap m a)
mcons })
  = LM :: forall (m :: * -> *) a. Maybe a -> m (ListMap m a) -> ListMap m a
LM { lm_nil :: Maybe b
lm_nil = (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Maybe a
mnil, lm_cons :: m (ListMap m b)
lm_cons = (ListMap m a -> ListMap m b) -> m (ListMap m a) -> m (ListMap m b)
forall (m :: * -> *) a b. TrieMap m => (a -> b) -> m a -> m b
mapTM ((a -> b) -> ListMap m a -> ListMap m b
forall (m :: * -> *) a b. TrieMap m => (a -> b) -> m a -> m b
mapTM a -> b
f) m (ListMap m a)
mcons }

lkList :: TrieMap m => (forall b. k -> m b -> Maybe b)
        -> [k] -> ListMap m a -> Maybe a
lkList :: (forall b. k -> m b -> Maybe b) -> [k] -> ListMap m a -> Maybe a
lkList forall b. k -> m b -> Maybe b
_  []     = ListMap m a -> Maybe a
forall (m :: * -> *) a. ListMap m a -> Maybe a
lm_nil
lkList forall b. k -> m b -> Maybe b
lk (k
x:[k]
xs) = ListMap m a -> m (ListMap m a)
forall (m :: * -> *) a. ListMap m a -> m (ListMap m a)
lm_cons (ListMap m a -> m (ListMap m a))
-> (m (ListMap m a) -> Maybe a) -> ListMap m a -> Maybe a
forall a b c. (a -> b) -> (b -> c) -> a -> c
>.> k -> m (ListMap m a) -> Maybe (ListMap m a)
forall b. k -> m b -> Maybe b
lk k
x (m (ListMap m a) -> Maybe (ListMap m a))
-> (ListMap m a -> Maybe a) -> m (ListMap m a) -> Maybe a
forall (m :: * -> *) a b c.
Monad m =>
(a -> m b) -> (b -> m c) -> a -> m c
>=> (forall b. k -> m b -> Maybe b) -> [k] -> ListMap m a -> Maybe a
forall (m :: * -> *) k a.
TrieMap m =>
(forall b. k -> m b -> Maybe b) -> [k] -> ListMap m a -> Maybe a
lkList forall b. k -> m b -> Maybe b
lk [k]
xs

xtList :: TrieMap m => (forall b. k -> XT b -> m b -> m b)
        -> [k] -> XT a -> ListMap m a -> ListMap m a
xtList :: (forall b. k -> XT b -> m b -> m b)
-> [k] -> XT a -> ListMap m a -> ListMap m a
xtList forall b. k -> XT b -> m b -> m b
_  []     XT a
f ListMap m a
m = ListMap m a
m { lm_nil :: Maybe a
lm_nil  = XT a
f (ListMap m a -> Maybe a
forall (m :: * -> *) a. ListMap m a -> Maybe a
lm_nil ListMap m a
m) }
xtList forall b. k -> XT b -> m b -> m b
tr (k
x:[k]
xs) XT a
f ListMap m a
m = ListMap m a
m { lm_cons :: m (ListMap m a)
lm_cons = ListMap m a -> m (ListMap m a)
forall (m :: * -> *) a. ListMap m a -> m (ListMap m a)
lm_cons ListMap m a
m m (ListMap m a)
-> (m (ListMap m a) -> m (ListMap m a)) -> m (ListMap m a)
forall a b. a -> (a -> b) -> b
|> k -> XT (ListMap m a) -> m (ListMap m a) -> m (ListMap m a)
forall b. k -> XT b -> m b -> m b
tr k
x (XT (ListMap m a) -> m (ListMap m a) -> m (ListMap m a))
-> (ListMap m a -> ListMap m a)
-> m (ListMap m a)
-> m (ListMap m a)
forall (m2 :: * -> *) a (m1 :: * -> *).
TrieMap m2 =>
(XT (m2 a) -> m1 (m2 a) -> m1 (m2 a))
-> (m2 a -> m2 a) -> m1 (m2 a) -> m1 (m2 a)
|>> (forall b. k -> XT b -> m b -> m b)
-> [k] -> XT a -> ListMap m a -> ListMap m a
forall (m :: * -> *) k a.
TrieMap m =>
(forall b. k -> XT b -> m b -> m b)
-> [k] -> XT a -> ListMap m a -> ListMap m a
xtList forall b. k -> XT b -> m b -> m b
tr [k]
xs XT a
f }

fdList :: forall m a b. TrieMap m
       => (a -> b -> b) -> ListMap m a -> b -> b
fdList :: (a -> b -> b) -> ListMap m a -> b -> b
fdList a -> b -> b
k ListMap m a
m = (a -> b -> b) -> Maybe a -> b -> b
forall a b. (a -> b -> b) -> Maybe a -> b -> b
foldMaybe a -> b -> b
k          (ListMap m a -> Maybe a
forall (m :: * -> *) a. ListMap m a -> Maybe a
lm_nil ListMap m a
m)
           (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ListMap m a -> b -> b) -> m (ListMap m a) -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> m a -> b -> b
foldTM    ((a -> b -> b) -> ListMap m a -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> ListMap m a -> b -> b
fdList a -> b -> b
k) (ListMap m a -> m (ListMap m a)
forall (m :: * -> *) a. ListMap m a -> m (ListMap m a)
lm_cons ListMap m a
m)

foldMaybe :: (a -> b -> b) -> Maybe a -> b -> b
foldMaybe :: (a -> b -> b) -> Maybe a -> b -> b
foldMaybe a -> b -> b
_ Maybe a
Nothing  b
b = b
b
foldMaybe a -> b -> b
k (Just a
a) b
b = a -> b -> b
k a
a b
b

{-
************************************************************************
*                                                                      *
                   Basic maps
*                                                                      *
************************************************************************
-}

type LiteralMap  a = Map.Map Literal a

{-
************************************************************************
*                                                                      *
                   GenMap
*                                                                      *
************************************************************************

Note [Compressed TrieMap]
~~~~~~~~~~~~~~~~~~~~~~~~~

The GenMap constructor augments TrieMaps with leaf compression.  This helps
solve the performance problem detailed in #9960: suppose we have a handful
H of entries in a TrieMap, each with a very large key, size K. If you fold over
such a TrieMap you'd expect time O(H). That would certainly be true of an
association list! But with TrieMap we actually have to navigate down a long
singleton structure to get to the elements, so it takes time O(K*H).  This
can really hurt on many type-level computation benchmarks:
see for example T9872d.

The point of a TrieMap is that you need to navigate to the point where only one
key remains, and then things should be fast.  So the point of a SingletonMap
is that, once we are down to a single (key,value) pair, we stop and
just use SingletonMap.

'EmptyMap' provides an even more basic (but essential) optimization: if there is
nothing in the map, don't bother building out the (possibly infinite) recursive
TrieMap structure!

Compressed triemaps are heavily used by CoreMap. So we have to mark some things
as INLINEABLE to permit specialization.
-}

data GenMap m a
   = EmptyMap
   | SingletonMap (Key m) a
   | MultiMap (m a)

instance (Outputable a, Outputable (m a)) => Outputable (GenMap m a) where
  ppr :: GenMap m a -> SDoc
ppr GenMap m a
EmptyMap = String -> SDoc
text String
"Empty map"
  ppr (SingletonMap Key m
_ a
v) = String -> SDoc
text String
"Singleton map" SDoc -> SDoc -> SDoc
<+> a -> SDoc
forall a. Outputable a => a -> SDoc
ppr a
v
  ppr (MultiMap m a
m) = m a -> SDoc
forall a. Outputable a => a -> SDoc
ppr m a
m

-- TODO undecidable instance
instance (Eq (Key m), TrieMap m) => TrieMap (GenMap m) where
   type Key (GenMap m) = Key m
   emptyTM :: GenMap m a
emptyTM  = GenMap m a
forall (m :: * -> *) a. GenMap m a
EmptyMap
   lookupTM :: Key (GenMap m) -> GenMap m b -> Maybe b
lookupTM = Key (GenMap m) -> GenMap m b -> Maybe b
forall (m :: * -> *) a.
(Eq (Key m), TrieMap m) =>
Key m -> GenMap m a -> Maybe a
lkG
   alterTM :: Key (GenMap m) -> XT b -> GenMap m b -> GenMap m b
alterTM  = Key (GenMap m) -> XT b -> GenMap m b -> GenMap m b
forall (m :: * -> *) a.
(Eq (Key m), TrieMap m) =>
Key m -> XT a -> GenMap m a -> GenMap m a
xtG
   foldTM :: (a -> b -> b) -> GenMap m a -> b -> b
foldTM   = (a -> b -> b) -> GenMap m a -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> GenMap m a -> b -> b
fdG
   mapTM :: (a -> b) -> GenMap m a -> GenMap m b
mapTM    = (a -> b) -> GenMap m a -> GenMap m b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b) -> GenMap m a -> GenMap m b
mapG

--We want to be able to specialize these functions when defining eg
--tries over (GenMap CoreExpr) which requires INLINEABLE

{-# INLINEABLE lkG #-}
lkG :: (Eq (Key m), TrieMap m) => Key m -> GenMap m a -> Maybe a
lkG :: Key m -> GenMap m a -> Maybe a
lkG Key m
_ GenMap m a
EmptyMap                         = Maybe a
forall a. Maybe a
Nothing
lkG Key m
k (SingletonMap Key m
k' a
v') | Key m
k Key m -> Key m -> Bool
forall a. Eq a => a -> a -> Bool
== Key m
k'   = a -> Maybe a
forall a. a -> Maybe a
Just a
v'
                           | Bool
otherwise = Maybe a
forall a. Maybe a
Nothing
lkG Key m
k (MultiMap m a
m)                     = Key m -> m a -> Maybe a
forall (m :: * -> *) b. TrieMap m => Key m -> m b -> Maybe b
lookupTM Key m
k m a
m

{-# INLINEABLE xtG #-}
xtG :: (Eq (Key m), TrieMap m) => Key m -> XT a -> GenMap m a -> GenMap m a
xtG :: Key m -> XT a -> GenMap m a -> GenMap m a
xtG Key m
k XT a
f GenMap m a
EmptyMap
    = case XT a
f Maybe a
forall a. Maybe a
Nothing of
        Just a
v  -> Key m -> a -> GenMap m a
forall (m :: * -> *) a. Key m -> a -> GenMap m a
SingletonMap Key m
k a
v
        Maybe a
Nothing -> GenMap m a
forall (m :: * -> *) a. GenMap m a
EmptyMap
xtG Key m
k XT a
f m :: GenMap m a
m@(SingletonMap Key m
k' a
v')
    | Key m
k' Key m -> Key m -> Bool
forall a. Eq a => a -> a -> Bool
== Key m
k
    -- The new key matches the (single) key already in the tree.  Hence,
    -- apply @f@ to @Just v'@ and build a singleton or empty map depending
    -- on the 'Just'/'Nothing' response respectively.
    = case XT a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
v') of
        Just a
v'' -> Key m -> a -> GenMap m a
forall (m :: * -> *) a. Key m -> a -> GenMap m a
SingletonMap Key m
k' a
v''
        Maybe a
Nothing  -> GenMap m a
forall (m :: * -> *) a. GenMap m a
EmptyMap
    | Bool
otherwise
    -- We've hit a singleton tree for a different key than the one we are
    -- searching for. Hence apply @f@ to @Nothing@. If result is @Nothing@ then
    -- we can just return the old map. If not, we need a map with *two*
    -- entries. The easiest way to do that is to insert two items into an empty
    -- map of type @m a@.
    = case XT a
f Maybe a
forall a. Maybe a
Nothing of
        Maybe a
Nothing  -> GenMap m a
m
        Just a
v   -> m a
forall (m :: * -> *) a. TrieMap m => m a
emptyTM m a -> (m a -> GenMap m a) -> GenMap m a
forall a b. a -> (a -> b) -> b
|> Key m -> XT a -> m a -> m a
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM Key m
k' (Maybe a -> XT a
forall a b. a -> b -> a
const (a -> Maybe a
forall a. a -> Maybe a
Just a
v'))
                           (m a -> m a) -> (m a -> GenMap m a) -> m a -> GenMap m a
forall a b c. (a -> b) -> (b -> c) -> a -> c
>.> Key m -> XT a -> m a -> m a
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM Key m
k  (Maybe a -> XT a
forall a b. a -> b -> a
const (a -> Maybe a
forall a. a -> Maybe a
Just a
v))
                           (m a -> m a) -> (m a -> GenMap m a) -> m a -> GenMap m a
forall a b c. (a -> b) -> (b -> c) -> a -> c
>.> m a -> GenMap m a
forall (m :: * -> *) a. m a -> GenMap m a
MultiMap
xtG Key m
k XT a
f (MultiMap m a
m) = m a -> GenMap m a
forall (m :: * -> *) a. m a -> GenMap m a
MultiMap (Key m -> XT a -> m a -> m a
forall (m :: * -> *) b. TrieMap m => Key m -> XT b -> m b -> m b
alterTM Key m
k XT a
f m a
m)

{-# INLINEABLE mapG #-}
mapG :: TrieMap m => (a -> b) -> GenMap m a -> GenMap m b
mapG :: (a -> b) -> GenMap m a -> GenMap m b
mapG a -> b
_ GenMap m a
EmptyMap = GenMap m b
forall (m :: * -> *) a. GenMap m a
EmptyMap
mapG a -> b
f (SingletonMap Key m
k a
v) = Key m -> b -> GenMap m b
forall (m :: * -> *) a. Key m -> a -> GenMap m a
SingletonMap Key m
k (a -> b
f a
v)
mapG a -> b
f (MultiMap m a
m) = m b -> GenMap m b
forall (m :: * -> *) a. m a -> GenMap m a
MultiMap ((a -> b) -> m a -> m b
forall (m :: * -> *) a b. TrieMap m => (a -> b) -> m a -> m b
mapTM a -> b
f m a
m)

{-# INLINEABLE fdG #-}
fdG :: TrieMap m => (a -> b -> b) -> GenMap m a -> b -> b
fdG :: (a -> b -> b) -> GenMap m a -> b -> b
fdG a -> b -> b
_ GenMap m a
EmptyMap = \b
z -> b
z
fdG a -> b -> b
k (SingletonMap Key m
_ a
v) = \b
z -> a -> b -> b
k a
v b
z
fdG a -> b -> b
k (MultiMap m a
m) = (a -> b -> b) -> m a -> b -> b
forall (m :: * -> *) a b.
TrieMap m =>
(a -> b -> b) -> m a -> b -> b
foldTM a -> b -> b
k m a
m