Add kind equalities to GHC.
[ghc.git] / compiler / basicTypes / VarEnv.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 -}
5
6 module VarEnv (
7 -- * Var, Id and TyVar environments (maps)
8 VarEnv, IdEnv, TyVarEnv, CoVarEnv, TyCoVarEnv,
9
10 -- ** Manipulating these environments
11 emptyVarEnv, unitVarEnv, mkVarEnv, mkVarEnv_Directly,
12 elemVarEnv, varEnvElts, varEnvKeys, varEnvToList,
13 extendVarEnv, extendVarEnv_C, extendVarEnv_Acc, extendVarEnv_Directly,
14 extendVarEnvList,
15 plusVarEnv, plusVarEnv_C, plusVarEnv_CD, alterVarEnv,
16 delVarEnvList, delVarEnv, delVarEnv_Directly,
17 minusVarEnv, intersectsVarEnv,
18 lookupVarEnv, lookupVarEnv_NF, lookupWithDefaultVarEnv,
19 mapVarEnv, zipVarEnv,
20 modifyVarEnv, modifyVarEnv_Directly,
21 isEmptyVarEnv, foldVarEnv, foldVarEnv_Directly,
22 elemVarEnvByKey, lookupVarEnv_Directly,
23 filterVarEnv, filterVarEnv_Directly, restrictVarEnv,
24 partitionVarEnv,
25
26 -- * Deterministic Var environments (maps)
27 DVarEnv,
28
29 -- ** Manipulating these environments
30 emptyDVarEnv,
31 extendDVarEnv,
32 lookupDVarEnv,
33 foldDVarEnv,
34
35 -- * The InScopeSet type
36 InScopeSet,
37
38 -- ** Operations on InScopeSets
39 emptyInScopeSet, mkInScopeSet, delInScopeSet,
40 extendInScopeSet, extendInScopeSetList, extendInScopeSetSet,
41 getInScopeVars, lookupInScope, lookupInScope_Directly,
42 unionInScope, elemInScopeSet, uniqAway,
43
44 -- * The RnEnv2 type
45 RnEnv2,
46
47 -- ** Operations on RnEnv2s
48 mkRnEnv2, rnBndr2, rnBndrs2, rnBndr2_var,
49 rnOccL, rnOccR, inRnEnvL, inRnEnvR, rnOccL_maybe, rnOccR_maybe,
50 rnBndrL, rnBndrR, nukeRnEnvL, nukeRnEnvR, rnSwap,
51 delBndrL, delBndrR, delBndrsL, delBndrsR,
52 addRnInScopeSet,
53 rnEtaL, rnEtaR,
54 rnInScope, rnInScopeSet, lookupRnInScope,
55 rnEnvL, rnEnvR,
56
57 -- * TidyEnv and its operation
58 TidyEnv,
59 emptyTidyEnv
60 ) where
61
62 import OccName
63 import Var
64 import VarSet
65 import UniqFM
66 import UniqDFM
67 import Unique
68 import Util
69 import Maybes
70 import Outputable
71 import StaticFlags
72 import FastString
73
74 {-
75 ************************************************************************
76 * *
77 In-scope sets
78 * *
79 ************************************************************************
80 -}
81
82 -- | A set of variables that are in scope at some point
83 data InScopeSet = InScope (VarEnv Var) {-# UNPACK #-} !Int
84 -- The (VarEnv Var) is just a VarSet. But we write it like
85 -- this to remind ourselves that you can look up a Var in
86 -- the InScopeSet. Typically the InScopeSet contains the
87 -- canonical version of the variable (e.g. with an informative
88 -- unfolding), so this lookup is useful.
89 --
90 -- INVARIANT: the VarEnv maps (the Unique of) a variable to
91 -- a variable with the same Uniqua. (This was not
92 -- the case in the past, when we had a grevious hack
93 -- mapping var1 to var2.
94 --
95 -- The Int is a kind of hash-value used by uniqAway
96 -- For example, it might be the size of the set
97 -- INVARIANT: it's not zero; we use it as a multiplier in uniqAway
98
99 instance Outputable InScopeSet where
100 ppr (InScope s _) = ptext (sLit "InScope") <+> ppr s
101
102 emptyInScopeSet :: InScopeSet
103 emptyInScopeSet = InScope emptyVarSet 1
104
105 getInScopeVars :: InScopeSet -> VarEnv Var
106 getInScopeVars (InScope vs _) = vs
107
108 mkInScopeSet :: VarEnv Var -> InScopeSet
109 mkInScopeSet in_scope = InScope in_scope 1
110
111 extendInScopeSet :: InScopeSet -> Var -> InScopeSet
112 extendInScopeSet (InScope in_scope n) v = InScope (extendVarEnv in_scope v v) (n + 1)
113
114 extendInScopeSetList :: InScopeSet -> [Var] -> InScopeSet
115 extendInScopeSetList (InScope in_scope n) vs
116 = InScope (foldl (\s v -> extendVarEnv s v v) in_scope vs)
117 (n + length vs)
118
119 extendInScopeSetSet :: InScopeSet -> VarEnv Var -> InScopeSet
120 extendInScopeSetSet (InScope in_scope n) vs
121 = InScope (in_scope `plusVarEnv` vs) (n + sizeUFM vs)
122
123 delInScopeSet :: InScopeSet -> Var -> InScopeSet
124 delInScopeSet (InScope in_scope n) v = InScope (in_scope `delVarEnv` v) n
125
126 elemInScopeSet :: Var -> InScopeSet -> Bool
127 elemInScopeSet v (InScope in_scope _) = v `elemVarEnv` in_scope
128
129 -- | Look up a variable the 'InScopeSet'. This lets you map from
130 -- the variable's identity (unique) to its full value.
131 lookupInScope :: InScopeSet -> Var -> Maybe Var
132 lookupInScope (InScope in_scope _) v = lookupVarEnv in_scope v
133
134 lookupInScope_Directly :: InScopeSet -> Unique -> Maybe Var
135 lookupInScope_Directly (InScope in_scope _) uniq
136 = lookupVarEnv_Directly in_scope uniq
137
138 unionInScope :: InScopeSet -> InScopeSet -> InScopeSet
139 unionInScope (InScope s1 _) (InScope s2 n2)
140 = InScope (s1 `plusVarEnv` s2) n2
141
142 -- | @uniqAway in_scope v@ finds a unique that is not used in the
143 -- in-scope set, and gives that to v.
144 uniqAway :: InScopeSet -> Var -> Var
145 -- It starts with v's current unique, of course, in the hope that it won't
146 -- have to change, and thereafter uses a combination of that and the hash-code
147 -- found in the in-scope set
148 uniqAway in_scope var
149 | var `elemInScopeSet` in_scope = uniqAway' in_scope var -- Make a new one
150 | otherwise = var -- Nothing to do
151
152 uniqAway' :: InScopeSet -> Var -> Var
153 -- This one *always* makes up a new variable
154 uniqAway' (InScope set n) var
155 = try 1
156 where
157 orig_unique = getUnique var
158 try k
159 | debugIsOn && (k > 1000)
160 = pprPanic "uniqAway loop:" (ppr k <+> text "tries" <+> ppr var <+> int n)
161 | uniq `elemVarSetByKey` set = try (k + 1)
162 | debugIsOn && opt_PprStyle_Debug && (k > 3)
163 = pprTrace "uniqAway:" (ppr k <+> text "tries" <+> ppr var <+> int n)
164 setVarUnique var uniq
165 | otherwise = setVarUnique var uniq
166 where
167 uniq = deriveUnique orig_unique (n * k)
168
169 {-
170 ************************************************************************
171 * *
172 Dual renaming
173 * *
174 ************************************************************************
175 -}
176
177 -- | When we are comparing (or matching) types or terms, we are faced with
178 -- \"going under\" corresponding binders. E.g. when comparing:
179 --
180 -- > \x. e1 ~ \y. e2
181 --
182 -- Basically we want to rename [@x@ -> @y@] or [@y@ -> @x@], but there are lots of
183 -- things we must be careful of. In particular, @x@ might be free in @e2@, or
184 -- y in @e1@. So the idea is that we come up with a fresh binder that is free
185 -- in neither, and rename @x@ and @y@ respectively. That means we must maintain:
186 --
187 -- 1. A renaming for the left-hand expression
188 --
189 -- 2. A renaming for the right-hand expressions
190 --
191 -- 3. An in-scope set
192 --
193 -- Furthermore, when matching, we want to be able to have an 'occurs check',
194 -- to prevent:
195 --
196 -- > \x. f ~ \y. y
197 --
198 -- matching with [@f@ -> @y@]. So for each expression we want to know that set of
199 -- locally-bound variables. That is precisely the domain of the mappings 1.
200 -- and 2., but we must ensure that we always extend the mappings as we go in.
201 --
202 -- All of this information is bundled up in the 'RnEnv2'
203 data RnEnv2
204 = RV2 { envL :: VarEnv Var -- Renaming for Left term
205 , envR :: VarEnv Var -- Renaming for Right term
206 , in_scope :: InScopeSet } -- In scope in left or right terms
207
208 -- The renamings envL and envR are *guaranteed* to contain a binding
209 -- for every variable bound as we go into the term, even if it is not
210 -- renamed. That way we can ask what variables are locally bound
211 -- (inRnEnvL, inRnEnvR)
212
213 mkRnEnv2 :: InScopeSet -> RnEnv2
214 mkRnEnv2 vars = RV2 { envL = emptyVarEnv
215 , envR = emptyVarEnv
216 , in_scope = vars }
217
218 addRnInScopeSet :: RnEnv2 -> VarEnv Var -> RnEnv2
219 addRnInScopeSet env vs
220 | isEmptyVarEnv vs = env
221 | otherwise = env { in_scope = extendInScopeSetSet (in_scope env) vs }
222
223 rnInScope :: Var -> RnEnv2 -> Bool
224 rnInScope x env = x `elemInScopeSet` in_scope env
225
226 rnInScopeSet :: RnEnv2 -> InScopeSet
227 rnInScopeSet = in_scope
228
229 -- | Retrieve the left mapping
230 rnEnvL :: RnEnv2 -> VarEnv Var
231 rnEnvL = envL
232
233 -- | Retrieve the right mapping
234 rnEnvR :: RnEnv2 -> VarEnv Var
235 rnEnvR = envR
236
237 rnBndrs2 :: RnEnv2 -> [Var] -> [Var] -> RnEnv2
238 -- ^ Applies 'rnBndr2' to several variables: the two variable lists must be of equal length
239 rnBndrs2 env bsL bsR = foldl2 rnBndr2 env bsL bsR
240
241 rnBndr2 :: RnEnv2 -> Var -> Var -> RnEnv2
242 -- ^ @rnBndr2 env bL bR@ goes under a binder @bL@ in the Left term,
243 -- and binder @bR@ in the Right term.
244 -- It finds a new binder, @new_b@,
245 -- and returns an environment mapping @bL -> new_b@ and @bR -> new_b@
246 rnBndr2 env bL bR = fst $ rnBndr2_var env bL bR
247
248 rnBndr2_var :: RnEnv2 -> Var -> Var -> (RnEnv2, Var)
249 -- ^ Similar to 'rnBndr2' but returns the new variable as well as the
250 -- new environment
251 rnBndr2_var (RV2 { envL = envL, envR = envR, in_scope = in_scope }) bL bR
252 = (RV2 { envL = extendVarEnv envL bL new_b -- See Note
253 , envR = extendVarEnv envR bR new_b -- [Rebinding]
254 , in_scope = extendInScopeSet in_scope new_b }, new_b)
255 where
256 -- Find a new binder not in scope in either term
257 new_b | not (bL `elemInScopeSet` in_scope) = bL
258 | not (bR `elemInScopeSet` in_scope) = bR
259 | otherwise = uniqAway' in_scope bL
260
261 -- Note [Rebinding]
262 -- If the new var is the same as the old one, note that
263 -- the extendVarEnv *deletes* any current renaming
264 -- E.g. (\x. \x. ...) ~ (\y. \z. ...)
265 --
266 -- Inside \x \y { [x->y], [y->y], {y} }
267 -- \x \z { [x->x], [y->y, z->x], {y,x} }
268
269 rnBndrL :: RnEnv2 -> Var -> (RnEnv2, Var)
270 -- ^ Similar to 'rnBndr2' but used when there's a binder on the left
271 -- side only.
272 rnBndrL (RV2 { envL = envL, envR = envR, in_scope = in_scope }) bL
273 = (RV2 { envL = extendVarEnv envL bL new_b
274 , envR = envR
275 , in_scope = extendInScopeSet in_scope new_b }, new_b)
276 where
277 new_b = uniqAway in_scope bL
278
279 rnBndrR :: RnEnv2 -> Var -> (RnEnv2, Var)
280 -- ^ Similar to 'rnBndr2' but used when there's a binder on the right
281 -- side only.
282 rnBndrR (RV2 { envL = envL, envR = envR, in_scope = in_scope }) bR
283 = (RV2 { envR = extendVarEnv envR bR new_b
284 , envL = envL
285 , in_scope = extendInScopeSet in_scope new_b }, new_b)
286 where
287 new_b = uniqAway in_scope bR
288
289 rnEtaL :: RnEnv2 -> Var -> (RnEnv2, Var)
290 -- ^ Similar to 'rnBndrL' but used for eta expansion
291 -- See Note [Eta expansion]
292 rnEtaL (RV2 { envL = envL, envR = envR, in_scope = in_scope }) bL
293 = (RV2 { envL = extendVarEnv envL bL new_b
294 , envR = extendVarEnv envR new_b new_b -- Note [Eta expansion]
295 , in_scope = extendInScopeSet in_scope new_b }, new_b)
296 where
297 new_b = uniqAway in_scope bL
298
299 rnEtaR :: RnEnv2 -> Var -> (RnEnv2, Var)
300 -- ^ Similar to 'rnBndr2' but used for eta expansion
301 -- See Note [Eta expansion]
302 rnEtaR (RV2 { envL = envL, envR = envR, in_scope = in_scope }) bR
303 = (RV2 { envL = extendVarEnv envL new_b new_b -- Note [Eta expansion]
304 , envR = extendVarEnv envR bR new_b
305 , in_scope = extendInScopeSet in_scope new_b }, new_b)
306 where
307 new_b = uniqAway in_scope bR
308
309 delBndrL, delBndrR :: RnEnv2 -> Var -> RnEnv2
310 delBndrL rn@(RV2 { envL = env, in_scope = in_scope }) v
311 = rn { envL = env `delVarEnv` v, in_scope = in_scope `extendInScopeSet` v }
312 delBndrR rn@(RV2 { envR = env, in_scope = in_scope }) v
313 = rn { envR = env `delVarEnv` v, in_scope = in_scope `extendInScopeSet` v }
314
315 delBndrsL, delBndrsR :: RnEnv2 -> [Var] -> RnEnv2
316 delBndrsL rn@(RV2 { envL = env, in_scope = in_scope }) v
317 = rn { envL = env `delVarEnvList` v, in_scope = in_scope `extendInScopeSetList` v }
318 delBndrsR rn@(RV2 { envR = env, in_scope = in_scope }) v
319 = rn { envR = env `delVarEnvList` v, in_scope = in_scope `extendInScopeSetList` v }
320
321 rnOccL, rnOccR :: RnEnv2 -> Var -> Var
322 -- ^ Look up the renaming of an occurrence in the left or right term
323 rnOccL (RV2 { envL = env }) v = lookupVarEnv env v `orElse` v
324 rnOccR (RV2 { envR = env }) v = lookupVarEnv env v `orElse` v
325
326 rnOccL_maybe, rnOccR_maybe :: RnEnv2 -> Var -> Maybe Var
327 -- ^ Look up the renaming of an occurrence in the left or right term
328 rnOccL_maybe (RV2 { envL = env }) v = lookupVarEnv env v
329 rnOccR_maybe (RV2 { envR = env }) v = lookupVarEnv env v
330
331 inRnEnvL, inRnEnvR :: RnEnv2 -> Var -> Bool
332 -- ^ Tells whether a variable is locally bound
333 inRnEnvL (RV2 { envL = env }) v = v `elemVarEnv` env
334 inRnEnvR (RV2 { envR = env }) v = v `elemVarEnv` env
335
336 lookupRnInScope :: RnEnv2 -> Var -> Var
337 lookupRnInScope env v = lookupInScope (in_scope env) v `orElse` v
338
339 nukeRnEnvL, nukeRnEnvR :: RnEnv2 -> RnEnv2
340 -- ^ Wipe the left or right side renaming
341 nukeRnEnvL env = env { envL = emptyVarEnv }
342 nukeRnEnvR env = env { envR = emptyVarEnv }
343
344 rnSwap :: RnEnv2 -> RnEnv2
345 -- ^ swap the meaning of left and right
346 rnSwap (RV2 { envL = envL, envR = envR, in_scope = in_scope })
347 = RV2 { envL = envR, envR = envL, in_scope = in_scope }
348
349 {-
350 Note [Eta expansion]
351 ~~~~~~~~~~~~~~~~~~~~
352 When matching
353 (\x.M) ~ N
354 we rename x to x' with, where x' is not in scope in
355 either term. Then we want to behave as if we'd seen
356 (\x'.M) ~ (\x'.N x')
357 Since x' isn't in scope in N, the form (\x'. N x') doesn't
358 capture any variables in N. But we must nevertheless extend
359 the envR with a binding [x' -> x'], to support the occurs check.
360 For example, if we don't do this, we can get silly matches like
361 forall a. (\y.a) ~ v
362 succeeding with [a -> v y], which is bogus of course.
363
364
365 ************************************************************************
366 * *
367 Tidying
368 * *
369 ************************************************************************
370 -}
371
372 -- | When tidying up print names, we keep a mapping of in-scope occ-names
373 -- (the 'TidyOccEnv') and a Var-to-Var of the current renamings
374 type TidyEnv = (TidyOccEnv, VarEnv Var)
375
376 emptyTidyEnv :: TidyEnv
377 emptyTidyEnv = (emptyTidyOccEnv, emptyVarEnv)
378
379 {-
380 ************************************************************************
381 * *
382 \subsection{@VarEnv@s}
383 * *
384 ************************************************************************
385 -}
386
387 type VarEnv elt = UniqFM elt
388 type IdEnv elt = VarEnv elt
389 type TyVarEnv elt = VarEnv elt
390 type TyCoVarEnv elt = VarEnv elt
391 type CoVarEnv elt = VarEnv elt
392
393 emptyVarEnv :: VarEnv a
394 mkVarEnv :: [(Var, a)] -> VarEnv a
395 mkVarEnv_Directly :: [(Unique, a)] -> VarEnv a
396 zipVarEnv :: [Var] -> [a] -> VarEnv a
397 unitVarEnv :: Var -> a -> VarEnv a
398 alterVarEnv :: (Maybe a -> Maybe a) -> VarEnv a -> Var -> VarEnv a
399 extendVarEnv :: VarEnv a -> Var -> a -> VarEnv a
400 extendVarEnv_C :: (a->a->a) -> VarEnv a -> Var -> a -> VarEnv a
401 extendVarEnv_Acc :: (a->b->b) -> (a->b) -> VarEnv b -> Var -> a -> VarEnv b
402 extendVarEnv_Directly :: VarEnv a -> Unique -> a -> VarEnv a
403 plusVarEnv :: VarEnv a -> VarEnv a -> VarEnv a
404 extendVarEnvList :: VarEnv a -> [(Var, a)] -> VarEnv a
405
406 lookupVarEnv_Directly :: VarEnv a -> Unique -> Maybe a
407 filterVarEnv_Directly :: (Unique -> a -> Bool) -> VarEnv a -> VarEnv a
408 delVarEnv_Directly :: VarEnv a -> Unique -> VarEnv a
409 partitionVarEnv :: (a -> Bool) -> VarEnv a -> (VarEnv a, VarEnv a)
410 restrictVarEnv :: VarEnv a -> VarSet -> VarEnv a
411 delVarEnvList :: VarEnv a -> [Var] -> VarEnv a
412 delVarEnv :: VarEnv a -> Var -> VarEnv a
413 minusVarEnv :: VarEnv a -> VarEnv b -> VarEnv a
414 intersectsVarEnv :: VarEnv a -> VarEnv a -> Bool
415 plusVarEnv_C :: (a -> a -> a) -> VarEnv a -> VarEnv a -> VarEnv a
416 plusVarEnv_CD :: (a -> a -> a) -> VarEnv a -> a -> VarEnv a -> a -> VarEnv a
417 mapVarEnv :: (a -> b) -> VarEnv a -> VarEnv b
418 modifyVarEnv :: (a -> a) -> VarEnv a -> Var -> VarEnv a
419 varEnvElts :: VarEnv a -> [a]
420 varEnvKeys :: VarEnv a -> [Unique]
421 varEnvToList :: VarEnv a -> [(Unique, a)]
422
423 isEmptyVarEnv :: VarEnv a -> Bool
424 lookupVarEnv :: VarEnv a -> Var -> Maybe a
425 filterVarEnv :: (a -> Bool) -> VarEnv a -> VarEnv a
426 lookupVarEnv_NF :: VarEnv a -> Var -> a
427 lookupWithDefaultVarEnv :: VarEnv a -> a -> Var -> a
428 elemVarEnv :: Var -> VarEnv a -> Bool
429 elemVarEnvByKey :: Unique -> VarEnv a -> Bool
430 foldVarEnv :: (a -> b -> b) -> b -> VarEnv a -> b
431 foldVarEnv_Directly :: (Unique -> a -> b -> b) -> b -> VarEnv a -> b
432
433 elemVarEnv = elemUFM
434 elemVarEnvByKey = elemUFM_Directly
435 alterVarEnv = alterUFM
436 extendVarEnv = addToUFM
437 extendVarEnv_C = addToUFM_C
438 extendVarEnv_Acc = addToUFM_Acc
439 extendVarEnv_Directly = addToUFM_Directly
440 extendVarEnvList = addListToUFM
441 plusVarEnv_C = plusUFM_C
442 plusVarEnv_CD = plusUFM_CD
443 delVarEnvList = delListFromUFM
444 delVarEnv = delFromUFM
445 minusVarEnv = minusUFM
446 intersectsVarEnv e1 e2 = not (isEmptyVarEnv (e1 `intersectUFM` e2))
447 plusVarEnv = plusUFM
448 lookupVarEnv = lookupUFM
449 filterVarEnv = filterUFM
450 lookupWithDefaultVarEnv = lookupWithDefaultUFM
451 mapVarEnv = mapUFM
452 mkVarEnv = listToUFM
453 mkVarEnv_Directly= listToUFM_Directly
454 emptyVarEnv = emptyUFM
455 varEnvElts = eltsUFM
456 varEnvKeys = keysUFM
457 varEnvToList = ufmToList
458 unitVarEnv = unitUFM
459 isEmptyVarEnv = isNullUFM
460 foldVarEnv = foldUFM
461 foldVarEnv_Directly = foldUFM_Directly
462 lookupVarEnv_Directly = lookupUFM_Directly
463 filterVarEnv_Directly = filterUFM_Directly
464 delVarEnv_Directly = delFromUFM_Directly
465 partitionVarEnv = partitionUFM
466
467 restrictVarEnv env vs = filterVarEnv_Directly keep env
468 where
469 keep u _ = u `elemVarSetByKey` vs
470
471 zipVarEnv tyvars tys = mkVarEnv (zipEqual "zipVarEnv" tyvars tys)
472 lookupVarEnv_NF env id = case lookupVarEnv env id of
473 Just xx -> xx
474 Nothing -> panic "lookupVarEnv_NF: Nothing"
475
476 {-
477 @modifyVarEnv@: Look up a thing in the VarEnv,
478 then mash it with the modify function, and put it back.
479 -}
480
481 modifyVarEnv mangle_fn env key
482 = case (lookupVarEnv env key) of
483 Nothing -> env
484 Just xx -> extendVarEnv env key (mangle_fn xx)
485
486 modifyVarEnv_Directly :: (a -> a) -> UniqFM a -> Unique -> UniqFM a
487 modifyVarEnv_Directly mangle_fn env key
488 = case (lookupUFM_Directly env key) of
489 Nothing -> env
490 Just xx -> addToUFM_Directly env key (mangle_fn xx)
491
492 -- Deterministic VarEnv
493 -- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need
494 -- DVarEnv.
495
496 type DVarEnv elt = UniqDFM elt
497
498 emptyDVarEnv :: DVarEnv a
499 emptyDVarEnv = emptyUDFM
500
501 extendDVarEnv :: DVarEnv a -> Var -> a -> DVarEnv a
502 extendDVarEnv = addToUDFM
503
504 lookupDVarEnv :: DVarEnv a -> Var -> Maybe a
505 lookupDVarEnv = lookupUDFM
506
507 foldDVarEnv :: (a -> b -> b) -> b -> DVarEnv a -> b
508 foldDVarEnv = foldUDFM