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
"--- Metrics of covariance detection ---"
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 redef class MParameterType
80 # The fully-qualified name of the formal parameter.
81 fun full_name
: String do return "{mclass.full_name}::{name}"
84 # A specific analysis that detects the variance constraints of formal parameters.
86 # The client has 3 steps to do:
88 # * call `collect` to initialize the attributes.
89 # * call `propagate` to propagate the variance constraints.
90 # * call `print_stats` to print the results.
91 class DetectVarianceConstraints
92 # Collect all types used in covariant and contravariant positions.
94 # The collect visits all classes and properties of `mainmodule` and its imported modules.
96 # After the visit, the attributes of `self` are filled.
97 fun collect
(mainmodule
: MModule)
99 for m
in mainmodule
.in_importation
.greaters
do
100 for cd
in m
.mclassdefs
do
102 pts
.add_all
(cd
.mclass
.mparameters
)
103 var a
= cd
.mclass
.arity
105 cpt_class
.inc
("non generic")
107 cpt_class
.inc
("with 1 formal type parameter")
109 cpt_class
.inc
("with {a} formal type parameters")
112 for t
in cd
.supertypes
do
113 # Supertype (covariant)
114 if t
.need_anchor
then covar_classes
.add
(t
)
116 for pd
in cd
.mpropdefs
do
117 if exclude_private
and pd
.mproperty
.visibility
<= private_visibility
then continue
118 if pd
isa MMethodDef then
119 # Parameters (contravariant)
120 for p
in pd
.msignature
.mparameters
do
121 var t
= p
.mtype
.as_notnullable
122 if not t
.need_anchor
then
124 else if t
isa MParameterType then
126 else if t
isa MVirtualType then
128 else if t
isa MClassType then
129 contravar_classes
.add
(t
)
135 var t
= pd
.msignature
.return_mtype
136 if t
!= null and t
.need_anchor
then
138 if t
isa MParameterType then
140 else if t
isa MVirtualType then
142 else if t
isa MClassType then
148 else if pd
isa MAttributeDef then
149 # Attribute (invariant)
150 var t
= pd
.static_mtype
151 if t
!= null and t
.need_anchor
then
153 if t
isa MParameterType then
156 else if t
isa MVirtualType then
158 else if t
isa MClassType then
160 contravar_classes
.add
(t
)
165 else if pd
isa MVirtualTypeDef then
166 # Virtual type bound (covariant)
168 if t
!= null and t
.need_anchor
then
170 if t
isa MParameterType then
172 else if t
isa MVirtualType then
174 else if t
isa MClassType then
186 # The set of all collected formal parameters
187 var pts
= new HashSet[MParameterType]
189 # The set of generic types found in a covariant (and invariant) position
190 var covar_classes
= new HashSet[MClassType]
192 # The set of formal parameters found in a covariant (and invariant) position
193 var covar_pt
= new HashSet[MParameterType]
195 # The set of generic types found in a contravariant (and invariant) position
196 var contravar_classes
= new HashSet[MClassType]
198 # The set of formal parameters found in a contravariant (and invariant) position
199 var contravar_pt
= new HashSet[MParameterType]
201 # Classes by number of formal parameters
202 var cpt_class
= new Counter[String]
204 # Does the collect exclude private properties?
206 var exclude_private
= false
208 # Propagate the variance constraints on `covar_classes`, `covar_pt`, `contravar_classes` and `contravar_pt`
210 # The algorithm uses a fixed-point approach on the covariance/contravariance rules.
213 # Classes to add to the `covar_classes` set at the end of an iteration
214 var new_covar
= new Array[MClassType]
215 # Classes to add to the `contravar_classes` set at the end of an iteration
216 var new_contravar
= new Array[MClassType]
217 # Does a modification occurred, so that another iteration is needed?
219 # Total number of iterations
228 # Process the generic types in a covariant position
229 for c
in covar_classes
do for i
in [0..c
.mclass
.arity
[ do
230 # The type used in the argument
231 var ta
= c
.arguments
[i
].as_notnullable
232 # The associated formal parameter
233 var tp
= c
.mclass
.mparameters
[i
]
235 if not ta
.need_anchor
then
237 else if ta
isa MParameterType then
238 # COVAR * COVAR = COVAR
239 if covar_pt
.has
(tp
) and not covar_pt
.has
(ta
) then
243 # COVAR * CONTRAVAR = CONTRAVAR
244 if contravar_pt
.has
(tp
) and not contravar_pt
.has
(ta
) then
248 else if ta
isa MVirtualType then
250 else if ta
isa MClassType then
251 # COVAR * COVAR = COVAR
252 if covar_pt
.has
(tp
) and not covar_classes
.has
(ta
) then
256 # COVAR * CONTRAVAR = CONTRAVAR
257 if contravar_pt
.has
(tp
) and not contravar_classes
.has
(ta
) then
264 # Process the generic types in a contravariant position
265 for c
in contravar_classes
do for i
in [0..c
.mclass
.arity
[ do
266 # The type used in the argument
267 var ta
= c
.arguments
[i
].as_notnullable
268 # The associated formal parameter
269 var tp
= c
.mclass
.mparameters
[i
]
271 if not ta
.need_anchor
then
273 else if ta
isa MParameterType then
274 # CONTRAVAR * CONTRAVAR = COVAR
275 if contravar_pt
.has
(tp
) and not covar_pt
.has
(ta
) then
279 # CONTRAVAR * COVAR = CONTRAVAR
280 if covar_pt
.has
(tp
) and not contravar_pt
.has
(ta
) then
284 else if ta
isa MVirtualType then
286 else if ta
isa MClassType then
287 # CONTRAVAR * CONTRAVAR = COVAR
288 if contravar_pt
.has
(tp
) and not covar_classes
.has
(ta
) then
292 # CONTRAVAR * COVAR = CONTRAVAR
293 if covar_pt
.has
(tp
) and not contravar_classes
.has
(ta
) then
300 covar_classes
.add_all
(new_covar
)
301 contravar_classes
.add_all
(new_contravar
)
305 # Print the final stats on the screen
314 if covar_pt
.has
(pt
) then
315 if contravar_pt
.has
(pt
) then
319 #print "covar: {pt.full_name}"
322 if contravar_pt
.has
(pt
) then
324 #print "contravar: {pt.full_name}"
327 #print "bivar: {pt.full_name}"
332 print
" covariants: {nb_cov} ({div(nb_cov*100, pts.length)}%)"
333 print
" contravariants: {nb_con} ({div(nb_con*100, pts.length)}%)"
334 print
" bivariants: {nb_biv} ({div(nb_biv*100, pts.length)}%)"
335 print
" invariants: {nb_inv} ({div(nb_inv*100, pts.length)}%)"
336 print
" total: {pts.length}"