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 # Detect the static usage of covariance in the code.
17 # The module works by refining various methods of the modelize and semantize
18 # phases to intercept type tests, then discriminate and count the cases.
20 # At the end, the statistics are displayed on the screen.
21 module detect_covariance
24 intrude import semantize
::typing
25 private import counter
27 redef class ToolContext
28 # --detect-variance-constraints
29 var opt_detect_covariance
= new OptionBool("Detect the static covariance usages", "--detect-covariance")
31 # Phase that intercepts static type tests then display statistics about covariance
32 private var detect_covariance_phase
= new DetectCovariancePhase(self, null)
35 private class DetectCovariancePhase
40 toolcontext
.option_context
.add_option
(toolcontext
.opt_detect_covariance
)
45 return not toolcontext
.opt_detect_covariance
.value
and not toolcontext
.opt_all
.value
48 fun cpt_subtype_kinds
: Counter[String] do return once
new Counter[String]
49 fun cpt_total_variance
: Counter[String] do return once
new Counter[String]
50 fun cpt_total_classes
: Counter[String] do return once
new Counter[String]
52 fun cpt_explanations
: Counter[String] do return once
new Counter[String]
53 fun cpt_classes
: Counter[MClass] do return once
new Counter[MClass]
54 fun cpt_pattern
: Counter[String] do return once
new Counter[String]
55 fun cpt_nodes
: Counter[String] do return once
new Counter[String]
56 fun cpt_modules
: Counter[String] do return once
new Counter[String]
57 fun cpt_expression
: Counter[String] do return once
new Counter[String]
59 fun cpt_cast_kind
: Counter[String] do return once
new Counter[String]
60 fun cpt_cast_classes
: Counter[String] do return once
new Counter[String]
61 fun cpt_cast_pattern
: Counter[String] do return once
new Counter[String]
62 fun cpt_autocast
: Counter[String] do return once
new Counter[String]
64 # Display collected statistics
65 redef fun process_mainmodule
(mainmodule
, given_mmodules
)
67 if is_disabled
then return
69 print
"--- Detection of the usage of covariance static type conformance ---"
72 print
"- Kinds of the subtype -"
73 cpt_subtype_kinds
.print_elements
(10)
74 print
" total: {cpt_subtype_kinds.sum}"
77 cpt_total_variance
.print_elements
(10)
78 print
" total: {cpt_total_variance.sum}"
80 print
"- Classes of the subtype -"
81 cpt_total_classes
.print_elements
(10)
82 print
" total: {cpt_total_classes.sum}"
84 print
"-- On covariance only --"
86 print
"- Specific covariance case explanations -"
87 cpt_explanations
.print_elements
(10)
88 print
" total: {cpt_explanations.sum}"
90 print
"- Classes of the subtype, when covariance -"
91 cpt_classes
.print_elements
(10)
92 print
" total: {cpt_classes.sum}"
94 print
"- Patterns of the covariant cases -"
95 cpt_pattern
.print_elements
(10)
96 print
" total: {cpt_pattern.sum}"
98 print
"- Nodes of the covariance cases -"
99 cpt_nodes
.print_elements
(10)
100 print
" total: {cpt_nodes.sum}"
102 print
"- Modules of the covariance cases -"
103 cpt_modules
.print_elements
(10)
104 print
" total: {cpt_modules.sum}"
106 print
"- Kind of the expression node (when it make sense) -"
107 cpt_expression
.print_elements
(10)
108 print
" total: {cpt_expression.sum}"
112 print
"- Kind of cast target -"
113 cpt_cast_kind
.print_elements
(10)
114 print
" total: {cpt_cast_kind.sum}"
116 print
"- Classes of the cast -"
117 cpt_cast_classes
.print_elements
(10)
118 print
" total: {cpt_cast_classes.sum}"
120 print
"- Cast pattern -"
121 cpt_cast_pattern
.print_elements
(10)
122 print
" total: {cpt_cast_pattern.sum}"
124 print
"- Autocasts -"
125 cpt_autocast
.print_elements
(10)
126 print
" total: {cpt_autocast.sum}"
129 # Common method used when static subtype test is performed by a phase
130 # Returns true if the test concern real generic covariance
131 fun count_types
(node
, elem
: ANode, sub
, sup
: MType, mmodule
: MModule, anchor
: nullable MClassType): Bool
133 sub
= sub
.as_notnullable
134 sup
= sup
.as_notnullable
136 # Category of the target type
137 if sub
isa MGenericType then
138 cpt_subtype_kinds
.inc
("generic type")
139 else if not sub
isa MClassType then
140 cpt_subtype_kinds
.inc
("formal type")
141 else if sub
.mclass
.kind
== enum_kind
then
142 cpt_subtype_kinds
.inc
("primitive type")
143 else if sub
.mclass
.name
== "Object" then
144 cpt_subtype_kinds
.inc
("object")
146 cpt_subtype_kinds
.inc
("non-generic type")
149 # Class of the subtype
150 if sub
isa MClassType then
151 cpt_total_classes
.inc
(sub
.mclass
.to_s
)
153 cpt_total_classes
.inc
(sub
.to_s
)
156 # Equal monomorph case
158 cpt_total_variance
.inc
("monomorph")
162 # Equivalent monomorph case
163 if sub
.is_subtype_invar
(mmodule
, anchor
, sup
) and sup
.is_subtype_invar
(mmodule
, anchor
, sub
) then
164 cpt_total_variance
.inc
("monomorph equiv")
169 if not sub
isa MClassType then
170 cpt_total_variance
.inc
("polymorph & formal")
175 if not sub
isa MGenericType then
176 cpt_total_variance
.inc
("polymorph & non-generic")
181 if sub
.is_subtype_invar
(mmodule
, anchor
, sup
) then
182 cpt_total_variance
.inc
("polymorph & generic & invariant")
186 if sub
.is_subtype
(mmodule
, anchor
, sup
) then
188 cpt_total_variance
.inc
("polymorph & generic & covariant")
190 # Cast (explicit or autocast)
191 if sup
.is_subtype
(mmodule
, anchor
, sub
) then
192 cpt_total_variance
.inc
("polymorph & generic & upcast!?")
193 cpt_pattern
.inc
("7.upcast")
197 if not sup
isa MGenericType then
198 cpt_total_variance
.inc
("polymorph & generic & lateral-cast from non-gen")
202 cpt_total_variance
.inc
("polymorph & generic & lateral-cast from gen")
205 ## ONLY covariance remains here
207 cpt_modules
.inc
(mmodule
.mgroup
.mproject
.name
)
208 cpt_classes
.inc
(sub
.mclass
)
210 # Track if `cpt_explanations` is already decided (used to fallback on unknown)
211 var caseknown
= false
215 while n
isa AType or n
isa AExprs do n
= n
.parent
.as(not null)
216 cpt_nodes
.inc
(n
.class_name
)
217 if n
isa AVarAssignExpr or n
isa AAttrPropdef and elem
isa AExpr then
218 cpt_pattern
.inc
("1.assign")
219 else if n
isa ASendExpr or n
isa ANewExpr then
220 cpt_pattern
.inc
("2.param")
221 else if n
isa AReturnExpr then
222 cpt_pattern
.inc
("3.return")
223 else if n
isa APropdef or n
isa ASignature then
224 cpt_pattern
.inc
("4.redef")
225 else if n
isa AAsCastExpr or n
isa AIsaExpr then
226 cpt_pattern
.inc
("6.downcast")
227 if n
isa AIsaExpr and n
.n_expr
isa ASelfExpr then
228 cpt_explanations
.inc
("downcast on self")
231 node
.debug
("6.downcast {sup} to {sub}")
233 else if n
isa ASuperPropdef then
234 cpt_pattern
.inc
("8.subclass")
235 else if n
isa AArrayExpr then
236 cpt_pattern
.inc
("9.array element")
238 n
.debug
("Unknown pattern")
239 cpt_pattern
.inc
("X.unknown")
242 if not caseknown
then
244 cpt_explanations
.inc
("covariant class")
246 cpt_explanations
.inc
("other covariance")
253 # Common method used when static cast test is seen by a phase
254 fun count_cast
(node
: ANode, sub
, sup
: MType, mmodule
: MModule, anchor
: nullable MClassType)
257 sup
= sup
.as_notnullable
258 sub
= sub
.as_notnullable
261 cpt_cast_pattern
.inc
("monomorphic cast!?!")
262 node
.debug
("monomorphic cast {sup} to {sub}")
263 else if not sub
isa MClassType then
264 cpt_cast_pattern
.inc
("cast to formal")
265 else if not sub
isa MGenericType then
266 cpt_cast_pattern
.inc
("cast to non-generic")
267 else if sub
== sup
then
268 cpt_cast_pattern
.inc
("nonullable monomorphic cast")
269 else if sup
.is_subtype
(mmodule
, anchor
, sub
) then
270 cpt_cast_pattern
.inc
("upcast to generic")
271 else if not sub
.is_subtype
(mmodule
, anchor
, sup
) then
272 cpt_cast_pattern
.inc
("lateral cast to generic")
273 else if not sub
.is_subtype_invar
(mmodule
, anchor
, sup
) then
274 assert sup
isa MGenericType
275 if sup
.mclass
!= sub
.mclass
then
276 cpt_cast_pattern
.inc
("covariant downcast to a generic (distinct classes)")
278 cpt_cast_pattern
.inc
("covariant downcast to a generic (same classes)")
280 else if not sup
isa MGenericType then
281 cpt_cast_pattern
.inc
("invariant downcast from non-generic to a generic")
283 assert sup
.mclass
!= sub
.mclass
284 cpt_cast_pattern
.inc
("invariant downcast from generic to generic")
287 cpt_cast_kind
.inc
(sub
.class_name
.to_s
)
289 if sub
isa MGenericType then
290 cpt_cast_classes
.inc
(sub
.mclass
.to_s
)
291 else if sub
isa MClassType then
292 # No generic class, so no covariance at runtime
294 cpt_cast_classes
.inc
(sub
.to_s
)
299 redef class ModelBuilder
300 redef fun check_subtype
(node
, mmodule
, anchor
, sub
, sup
)
303 var dcp
= toolcontext
.detect_covariance_phase
305 if dcp
.is_disabled
then return res
308 dcp
.count_types
(node
, node
, sub
, sup
, mmodule
, anchor
)
310 dcp
.cpt_total_variance
.inc
("bad mb subtype")
317 redef class TypeVisitor
319 fun dcp
: DetectCovariancePhase do return modelbuilder
.toolcontext
.detect_covariance_phase
321 redef fun visit_expr_cast
(node
, nexpr
, ntype
)
325 if dcp
.is_disabled
then return sub
327 # In case of error, just forward
329 dcp
.cpt_total_variance
.inc
("bad cast")
333 var sup
= nexpr
.mtype
.as(not null)
335 if sub
!= ntype
.mtype
.as(not null) then
336 node
.debug
("fishy cast: res={sub} ntype={ntype.mtype.as(not null)}")
339 dcp
.count_types
(node
, nexpr
, sub
, sup
, mmodule
, anchor
)
341 dcp
.count_cast
(node
, sub
, sup
, mmodule
, anchor
)
346 redef fun check_subtype
(node
: ANode, sub
, sup
: MType): nullable MType
350 if dcp
.is_disabled
then return res
352 var anchor
= self.anchor
353 assert anchor
!= null
356 var p
= node
.parent
.as(not null)
357 if p
isa AExprs then p
= p
.parent
.as(not null)
360 if not self.is_subtype
(sub
, sup
) then
361 if node
isa AAsCastExpr then
364 sup
= supx
.resolve_for
(anchor
.mclass
.mclass_type
, anchor
, mmodule
, true)
365 if self.is_subtype
(sub
, sup
) then
366 dcp
.cpt_autocast
.inc
("vt")
367 dcp
.count_cast
(node
, supx
, sub
, mmodule
, anchor
)
369 sup
= supx
.resolve_for
(anchor
, null, mmodule
, false)
370 if self.is_subtype
(sub
, sup
) then
371 dcp
.cpt_autocast
.inc
("vt+pt")
372 dcp
.count_cast
(node
, supx
, sub
, mmodule
, anchor
)
374 self.modelbuilder
.error
(node
, "Type error: expected {sup}, got {sub}")
378 dcp
.count_types
(p
, node
, supx
, subx
, mmodule
, anchor
)
383 if not dcp
.count_types
(p
, node
, sub
, sup
, mmodule
, anchor
) then return sub
385 # Unknown explanation of covariance, go further
386 dcp
.cpt_explanations
["other covariance"] -= 1
389 if n
isa AOnceExpr then n
= n
.n_expr
390 dcp
.cpt_expression
.inc
(n
.class_name
)
392 if node
isa AArrayExpr then
393 dcp
.cpt_explanations
.inc
("lit-array")
394 else if p
isa ACallExpr and (p
.n_id
.text
== "sort" or p
.n_id
.text
== "linearize_mpropdefs") then
395 dcp
.cpt_explanations
.inc
("generic methods (sort-method)")
396 else if p
isa ACallExpr and p
.n_id
.text
== "visit_list" then
397 dcp
.cpt_explanations
.inc
("use-site covariance (visit_list-method)")
399 dcp
.cpt_explanations
.inc
("other covariance")
406 # Return true if `self` is a invariant subtype of `sup`.
407 # This is just a copy of the original `is_subtype` method with only two new lines
408 fun is_subtype_invar
(mmodule
: MModule, anchor
: nullable MClassType, sup
: MType): Bool
411 if sub
== sup
then return true
413 #print "1.is {sub} a {sup}? ===="
415 if anchor
== null then
416 assert not sub
.need_anchor
417 assert not sup
.need_anchor
419 # First, resolve the formal types to the simplest equivalent forms in the receiver
420 assert sub
.can_resolve_for
(anchor
, null, mmodule
)
421 sub
= sub
.lookup_fixed
(mmodule
, anchor
)
422 assert sup
.can_resolve_for
(anchor
, null, mmodule
)
423 sup
= sup
.lookup_fixed
(mmodule
, anchor
)
426 # Does `sup` accept null or not?
427 # Discard the nullable marker if it exists
428 var sup_accept_null
= false
429 if sup
isa MNullableType then
430 sup_accept_null
= true
432 else if sup
isa MNullType then
433 sup_accept_null
= true
436 # Can `sub` provide null or not?
437 # Thus we can match with `sup_accept_null`
438 # Also discard the nullable marker if it exists
439 if sub
isa MNullableType then
440 if not sup_accept_null
then return false
442 else if sub
isa MNullType then
443 return sup_accept_null
445 # Now the case of direct null and nullable is over.
447 # If `sub` is a formal type, then it is accepted if its bound is accepted
448 while sub
isa MParameterType or sub
isa MVirtualType do
449 #print "3.is {sub} a {sup}?"
451 # A unfixed formal type can only accept itself
452 if sub
== sup
then return true
454 assert anchor
!= null
455 sub
= sub
.lookup_bound
(mmodule
, anchor
)
457 #print "3.is {sub} a {sup}?"
459 # Manage the second layer of null/nullable
460 if sub
isa MNullableType then
461 if not sup_accept_null
then return false
463 else if sub
isa MNullType then
464 return sup_accept_null
467 #print "4.is {sub} a {sup}? <- no more resolution"
469 assert sub
isa MClassType # It is the only remaining type
471 # A unfixed formal type can only accept itself
472 if sup
isa MParameterType or sup
isa MVirtualType then
476 if sup
isa MNullType then
477 # `sup` accepts only null
481 assert sup
isa MClassType # It is the only remaining type
483 # Now both are MClassType, we need to dig
485 if sub
== sup
then return true
487 if anchor
== null then anchor
= sub
# UGLY: any anchor will work
488 var resolved_sub
= sub
.anchor_to
(mmodule
, anchor
)
489 var res
= resolved_sub
.collect_mclasses
(mmodule
).has
(sup
.mclass
)
490 if res
== false then return false
491 if not sup
isa MGenericType then return true
492 var sub2
= sub
.supertype_to
(mmodule
, anchor
, sup
.mclass
)
493 assert sub2
.mclass
== sup
.mclass
494 for i
in [0..sup
.mclass
.arity
[ do
495 var sub_arg
= sub2
.arguments
[i
]
496 var sup_arg
= sup
.arguments
[i
]
497 res
= sub_arg
.is_subtype
(mmodule
, anchor
, sup_arg
)
498 if res
== false then return false
500 res
= sup_arg
.is_subtype
(mmodule
, anchor
, sub_arg
)
501 if res
== false then return false
502 # End of the two new lines