| ... |
... |
@@ -129,6 +129,10 @@ But we must take care (see #14880): |
|
129
|
129
|
free variables. This is plain wrong. We must instead compute that b is free
|
|
130
|
130
|
and then conclude that b's kind is free.
|
|
131
|
131
|
|
|
|
132
|
+ BUT: there is no worry here any more because of Invariant (NoTypeShadowing).
|
|
|
133
|
+ in GHC.Core. In the example, the `forall k` shadows the `k` in
|
|
|
134
|
+ b's kind, which is now illegal and checked by Lint.
|
|
|
135
|
+
|
|
132
|
136
|
An obvious first approach is to compute the /shallow/ free variables of the type,
|
|
133
|
137
|
and /then/ close over kinds. But that turns out not to be very efficient.
|
|
134
|
138
|
Fortunately, there is a simpler way, which works with the accumulating
|
| ... |
... |
@@ -139,18 +143,20 @@ GHC.Types.Var.FV. At an occurrence of a variable (a::k) |
|
139
|
143
|
|
|
140
|
144
|
* Check if `a` is already in the accumulator; if so, ignore it because we have
|
|
141
|
145
|
deal with its kind already. Also pre-checking set membership before inserting
|
|
142
|
|
- ends up not only being faster,
|
|
|
146
|
+ allocates less than just inserting, because the no-op case of insertion does
|
|
|
147
|
+ allocation.
|
|
143
|
148
|
|
|
144
|
149
|
* Otherwise add `a` to the accumulator,
|
|
145
|
150
|
AND add on the free vars of its kind `k`.
|
|
146
|
151
|
BUT in this latter step, start with an empty BoundVars set.
|
|
147
|
152
|
|
|
148
|
|
-This twist is implemented in `deepUnitFV`
|
|
149
|
|
-
|
|
150
|
|
-So now consider:
|
|
|
153
|
+The "start with an empty BoundVars set" is implemented in `deepUnitFV`. It's
|
|
|
154
|
+not /necessary/ to zap the BoundVars set, because of Invariant (NoTypeShadowing).
|
|
|
155
|
+But it's a tiny bit more efficient because the BoundVars set is smaller.
|
|
151
|
156
|
|
|
|
157
|
+Side note: the free-variable binder would still work even without (NoTypeShadowing).
|
|
|
158
|
+Consider:
|
|
152
|
159
|
forall k. b -> k
|
|
153
|
|
-
|
|
154
|
160
|
where b :: k->Type is free; but of course, it's a different k! When looking at
|
|
155
|
161
|
b -> k we'll have k in the bound-var set. So we'll ignore the k. But suppose
|
|
156
|
162
|
this is our first encounter with b; we want the free vars of its kind. But we
|
| ... |
... |
@@ -537,8 +543,6 @@ deepDetCoVarFolder = TyCoFolder { tcf_view = noView |
|
537
|
543
|
* *
|
|
538
|
544
|
********************************************************************* -}
|
|
539
|
545
|
|
|
540
|
|
-------------- Closing over kinds -----------------
|
|
541
|
|
-
|
|
542
|
546
|
closeOverKinds :: TyCoVarSet -> TyCoVarSet
|
|
543
|
547
|
-- For each element of the input set,
|
|
544
|
548
|
-- add the deep free variables of its kind
|
| ... |
... |
@@ -553,60 +557,6 @@ closeOverKindsDSet vs = nonDetStrictFoldDVarSet do_one vs vs |
|
553
|
557
|
where
|
|
554
|
558
|
do_one v = runFVAcc (deepDetTypeFV (varType v))
|
|
555
|
559
|
|
|
556
|
|
-{- --------------- Alternative version 1 (using FV) ------------
|
|
557
|
|
-closeOverKinds = fvVarSet . closeOverKindsFV . nonDetEltsUniqSet
|
|
558
|
|
--}
|
|
559
|
|
-
|
|
560
|
|
-{- ---------------- Alternative version 2 -------------
|
|
561
|
|
-
|
|
562
|
|
--- | Add the kind variables free in the kinds of the tyvars in the given set.
|
|
563
|
|
--- Returns a non-deterministic set.
|
|
564
|
|
-closeOverKinds :: TyCoVarSet -> TyCoVarSet
|
|
565
|
|
-closeOverKinds vs
|
|
566
|
|
- = go vs vs
|
|
567
|
|
- where
|
|
568
|
|
- go :: VarSet -- Work list
|
|
569
|
|
- -> VarSet -- Accumulator, always a superset of wl
|
|
570
|
|
- -> VarSet
|
|
571
|
|
- go wl acc
|
|
572
|
|
- | isEmptyVarSet wl = acc
|
|
573
|
|
- | otherwise = go wl_kvs (acc `unionVarSet` wl_kvs)
|
|
574
|
|
- where
|
|
575
|
|
- k v inner_acc = ty_co_vars_of_type (varType v) acc inner_acc
|
|
576
|
|
- wl_kvs = nonDetFoldVarSet k emptyVarSet wl
|
|
577
|
|
- -- wl_kvs = union of shallow free vars of the kinds of wl
|
|
578
|
|
- -- but don't bother to collect vars in acc
|
|
579
|
|
-
|
|
580
|
|
--}
|
|
581
|
|
-
|
|
582
|
|
-{- ---------------- Alternative version 3 -------------
|
|
583
|
|
--- | Add the kind variables free in the kinds of the tyvars in the given set.
|
|
584
|
|
--- Returns a non-deterministic set.
|
|
585
|
|
-closeOverKinds :: TyVarSet -> TyVarSet
|
|
586
|
|
-closeOverKinds vs = close_over_kinds vs emptyVarSet
|
|
587
|
|
-
|
|
588
|
|
-
|
|
589
|
|
-close_over_kinds :: TyVarSet -- Work list
|
|
590
|
|
- -> TyVarSet -- Accumulator
|
|
591
|
|
- -> TyVarSet
|
|
592
|
|
--- Precondition: in any call (close_over_kinds wl acc)
|
|
593
|
|
--- for every tv in acc, the shallow kind-vars of tv
|
|
594
|
|
--- are either in the work list wl, or in acc
|
|
595
|
|
--- Postcondition: result is the deep free vars of (wl `union` acc)
|
|
596
|
|
-close_over_kinds wl acc
|
|
597
|
|
- = nonDetFoldVarSet do_one acc wl
|
|
598
|
|
- where
|
|
599
|
|
- do_one :: Var -> TyVarSet -> TyVarSet
|
|
600
|
|
- -- (do_one v acc) adds v and its deep free-vars to acc
|
|
601
|
|
- do_one v acc | v `elemVarSet` acc
|
|
602
|
|
- = acc
|
|
603
|
|
- | otherwise
|
|
604
|
|
- = close_over_kinds (shallowTyCoVarsOfType (varType v)) $
|
|
605
|
|
- acc `extendVarSet` v
|
|
606
|
|
--}
|
|
607
|
|
-
|
|
608
|
|
-
|
|
609
|
|
-
|
|
610
|
560
|
|
|
611
|
561
|
{-
|
|
612
|
562
|
%************************************************************************
|
| ... |
... |
@@ -614,7 +564,6 @@ close_over_kinds wl acc |
|
614
|
564
|
almostDevoidCoVarOfCo
|
|
615
|
565
|
%* *
|
|
616
|
566
|
%************************************************************************
|
|
617
|
|
-
|
|
618
|
567
|
-}
|
|
619
|
568
|
|
|
620
|
569
|
----- Whether a covar is /Almost Devoid/ in a type or coercion ----
|