1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Collect metrics about detected variances constraints on formal types.
17 # In some OO-language that feature safe invariant generics by default,
18 # formal parameter types can annotated to be usable in covariant and contravariant positions.
19 # The price to pay is that the usage of formal parameter types in the class has constraints:
21 # * covariant-annotated formal types cannot be used in parameters or in attributes
22 # * contravariant-annotated formal types cannot be used in return or in attributes
24 # This module provide a backward analysis that infers the possible variance annotations
25 # of formal types in Nit programs by identifying the existing constraints on the usage of those formal type.
27 # It collects the types used in the signatures of properties then propagates constraints between types.
28 module detect_variance_constraints
33 redef class ToolContext
34 # --detect-variance-constraints
35 var opt_detect_variance_constraints
= new OptionBool("Detect the definition-site variance constraints on formal parameters", "--detect-variance-constraints")
37 # The DetectVarianceConstraints phase
38 var detect_variance_constraints_phase
: Phase = new DetectVarianceConstraintsPhase(self, null)
41 private class DetectVarianceConstraintsPhase
46 toolcontext
.option_context
.add_option
(toolcontext
.opt_detect_variance_constraints
)
49 redef fun process_mainmodule
(mainmodule
, given_mmodules
)
51 if not toolcontext
.opt_detect_variance_constraints
.value
and not toolcontext
.opt_all
.value
then return
53 print
"--- Detection of variance constraints on formal parameter types ---"
55 var k
= new DetectVarianceConstraints
58 print
"-- Generic classes --"
59 k
.cpt_class
.print_elements
(10)
60 print
" total classes: {k.cpt_class.sum}"
61 print
" total formal parameters: {k.pts.length}"
65 print
"-- Including `private` properties --"
68 k
= new DetectVarianceConstraints
69 k
.exclude_private
= true
74 print
"-- Excluding `private` properties --"
79 # A specific analysis that detects the variance constraints of formal parameters.
81 # The client has 3 steps to do:
83 # * call `collect` to initialize the attributes.
84 # * call `propagate` to propagate the variance constraints.
85 # * call `print_stats` to print the results.
86 class DetectVarianceConstraints
87 # Collect all types used in covariant and contravariant positions.
89 # The collect visits all classes and properties of `mainmodule` and its imported modules.
91 # After the visit, the attributes of `self` are filled.
92 fun collect
(mainmodule
: MModule)
94 for m
in mainmodule
.in_importation
.greaters
do
95 for cd
in m
.mclassdefs
do
97 pts
.add_all
(cd
.mclass
.mparameters
)
98 var a
= cd
.mclass
.arity
100 cpt_class
.inc
("non generic")
102 cpt_class
.inc
("with 1 formal type parameter")
104 cpt_class
.inc
("with {a} formal type parameters")
107 for t
in cd
.supertypes
do
108 # Supertype (covariant)
109 if t
.need_anchor
then covar_classes
.add
(t
)
111 for pd
in cd
.mpropdefs
do
112 if exclude_private
and pd
.mproperty
.visibility
<= private_visibility
then continue
113 if pd
isa MMethodDef then
114 # Parameters (contravariant)
115 for p
in pd
.msignature
.mparameters
do
116 var t
= p
.mtype
.undecorate
117 if not t
.need_anchor
then
119 else if t
isa MParameterType then
121 else if t
isa MVirtualType then
123 else if t
isa MClassType then
124 contravar_classes
.add
(t
)
130 var t
= pd
.msignature
.return_mtype
131 if t
!= null and t
.need_anchor
then
133 if t
isa MParameterType then
135 else if t
isa MVirtualType then
137 else if t
isa MClassType then
143 else if pd
isa MAttributeDef then
144 # Attribute (invariant)
145 var t
= pd
.static_mtype
146 if t
!= null and t
.need_anchor
then
148 if t
isa MParameterType then
151 else if t
isa MVirtualType then
153 else if t
isa MClassType then
155 contravar_classes
.add
(t
)
160 else if pd
isa MVirtualTypeDef then
161 # Virtual type bound (covariant)
163 if t
!= null and t
.need_anchor
then
165 if t
isa MParameterType then
167 else if t
isa MVirtualType then
169 else if t
isa MClassType then
181 # The set of all collected formal parameters
182 var pts
= new HashSet[MParameterType]
184 # The set of generic types found in a covariant (and invariant) position
185 var covar_classes
= new HashSet[MClassType]
187 # The set of formal parameters found in a covariant (and invariant) position
188 var covar_pt
= new HashSet[MParameterType]
190 # The set of generic types found in a contravariant (and invariant) position
191 var contravar_classes
= new HashSet[MClassType]
193 # The set of formal parameters found in a contravariant (and invariant) position
194 var contravar_pt
= new HashSet[MParameterType]
196 # Classes by number of formal parameters
197 var cpt_class
= new Counter[String]
199 # Does the collect exclude private properties?
201 var exclude_private
= false
203 # Propagate the variance constraints on `covar_classes`, `covar_pt`, `contravar_classes` and `contravar_pt`
205 # The algorithm uses a fixed-point approach on the covariance/contravariance rules.
208 # Classes to add to the `covar_classes` set at the end of an iteration
209 var new_covar
= new Array[MClassType]
210 # Classes to add to the `contravar_classes` set at the end of an iteration
211 var new_contravar
= new Array[MClassType]
212 # Does a modification occurred, so that another iteration is needed?
214 # Total number of iterations
223 # Process the generic types in a covariant position
224 for c
in covar_classes
do for i
in [0..c
.mclass
.arity
[ do
225 # The type used in the argument
226 var ta
= c
.arguments
[i
].undecorate
227 # The associated formal parameter
228 var tp
= c
.mclass
.mparameters
[i
]
230 if not ta
.need_anchor
then
232 else if ta
isa MParameterType then
233 # COVAR * COVAR = COVAR
234 if covar_pt
.has
(tp
) and not covar_pt
.has
(ta
) then
238 # COVAR * CONTRAVAR = CONTRAVAR
239 if contravar_pt
.has
(tp
) and not contravar_pt
.has
(ta
) then
243 else if ta
isa MVirtualType then
245 else if ta
isa MClassType then
246 # COVAR * COVAR = COVAR
247 if covar_pt
.has
(tp
) and not covar_classes
.has
(ta
) then
251 # COVAR * CONTRAVAR = CONTRAVAR
252 if contravar_pt
.has
(tp
) and not contravar_classes
.has
(ta
) then
259 # Process the generic types in a contravariant position
260 for c
in contravar_classes
do for i
in [0..c
.mclass
.arity
[ do
261 # The type used in the argument
262 var ta
= c
.arguments
[i
].undecorate
263 # The associated formal parameter
264 var tp
= c
.mclass
.mparameters
[i
]
266 if not ta
.need_anchor
then
268 else if ta
isa MParameterType then
269 # CONTRAVAR * CONTRAVAR = COVAR
270 if contravar_pt
.has
(tp
) and not covar_pt
.has
(ta
) then
274 # CONTRAVAR * COVAR = CONTRAVAR
275 if covar_pt
.has
(tp
) and not contravar_pt
.has
(ta
) then
279 else if ta
isa MVirtualType then
281 else if ta
isa MClassType then
282 # CONTRAVAR * CONTRAVAR = COVAR
283 if contravar_pt
.has
(tp
) and not covar_classes
.has
(ta
) then
287 # CONTRAVAR * COVAR = CONTRAVAR
288 if covar_pt
.has
(tp
) and not contravar_classes
.has
(ta
) then
295 covar_classes
.add_all
(new_covar
)
296 contravar_classes
.add_all
(new_contravar
)
300 # Print the final stats on the screen
309 if covar_pt
.has
(pt
) then
310 if contravar_pt
.has
(pt
) then
314 #print "covar: {pt.full_name}"
317 if contravar_pt
.has
(pt
) then
319 #print "contravar: {pt.full_name}"
322 #print "bivar: {pt.full_name}"
327 print
" covariants: {nb_cov} ({div(nb_cov*100, pts.length)}%)"
328 print
" contravariants: {nb_con} ({div(nb_con*100, pts.length)}%)"
329 print
" bivariants: {nb_biv} ({div(nb_biv*100, pts.length)}%)"
330 print
" invariants: {nb_inv} ({div(nb_inv*100, pts.length)}%)"
331 print
" total: {pts.length}"