src/metrics/detect_covariance.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   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
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   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.
  14
  15 # Detect the static usage of covariance in the code.
  16 #
  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.
  19 #
  20 # At the end, the statistics are displayed on the screen.
  21 module detect_covariance
  22
  23 import metrics_base
  24 intrude import semantize::typing
  25 private import counter
  26
  27 redef class ToolContext
  28         # --detect-variance-constraints
  29         var opt_detect_covariance = new OptionBool("Detect the static covariance usages", "--detect-covariance")
  30
  31         # Phase that intercepts static type tests then display statistics about covariance
  32         private var detect_covariance_phase = new DetectCovariancePhase(self, null)
  33 end
  34
  35 private class DetectCovariancePhase
  36         super Phase
  37
  38         init
  39         do
  40                 toolcontext.option_context.add_option(toolcontext.opt_detect_covariance)
  41         end
  42
  43         fun is_disabled: Bool
  44         do
  45                 return not toolcontext.opt_detect_covariance.value and not toolcontext.opt_all.value
  46         end
  47
  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]
  51
  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]
  58
  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]
  63
  64         # Display collected statistics
  65         redef fun process_mainmodule(mainmodule, given_mmodules)
  66         do
  67                 if is_disabled then return
  68
  69                 print "--- Detection of the usage of covariance static type conformance ---"
  70
  71                 print "-- Total --"
  72                 print "- Kinds of the subtype -"
  73                 cpt_subtype_kinds.print_elements(10)
  74                 print "  total: {cpt_subtype_kinds.sum}"
  75
  76                 print "- Variance -"
  77                 cpt_total_variance.print_elements(10)
  78                 print "  total: {cpt_total_variance.sum}"
  79
  80                 print "- Classes of the subtype -"
  81                 cpt_total_classes.print_elements(10)
  82                 print "  total: {cpt_total_classes.sum}"
  83
  84                 print "-- On covariance only --"
  85
  86                 print "- Specific covariance case explanations -"
  87                 cpt_explanations.print_elements(10)
  88                 print "  total: {cpt_explanations.sum}"
  89
  90                 print "- Classes of the subtype, when covariance -"
  91                 cpt_classes.print_elements(10)
  92                 print "  total: {cpt_classes.sum}"
  93
  94                 print "- Patterns of the covariant cases -"
  95                 cpt_pattern.print_elements(10)
  96                 print "  total: {cpt_pattern.sum}"
  97
  98                 print "- Nodes of the covariance cases -"
  99                 cpt_nodes.print_elements(10)
 100                 print "  total: {cpt_nodes.sum}"
 101
 102                 print "- Modules of the covariance cases -"
 103                 cpt_modules.print_elements(10)
 104                 print "  total: {cpt_modules.sum}"
 105
 106                 print "- Kind of the expression node (when it make sense) -"
 107                 cpt_expression.print_elements(10)
 108                 print "  total: {cpt_expression.sum}"
 109
 110                 print "-- Casts --"
 111
 112                 print "- Kind of cast target -"
 113                 cpt_cast_kind.print_elements(10)
 114                 print "  total: {cpt_cast_kind.sum}"
 115
 116                 print "- Classes of the cast -"
 117                 cpt_cast_classes.print_elements(10)
 118                 print "  total: {cpt_cast_classes.sum}"
 119
 120                 print "- Cast pattern -"
 121                 cpt_cast_pattern.print_elements(10)
 122                 print "  total: {cpt_cast_pattern.sum}"
 123
 124                 print "- Autocasts -"
 125                 cpt_autocast.print_elements(10)
 126                 print "  total: {cpt_autocast.sum}"
 127         end
 128
 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
 132         do
 133                 sub = sub.undecorate
 134                 sup = sup.undecorate
 135
 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")
 145                 else
 146                         cpt_subtype_kinds.inc("non-generic type")
 147                 end
 148
 149                 # Class of the subtype
 150                 if sub isa MClassType then
 151                         cpt_total_classes.inc(sub.mclass.to_s)
 152                 else
 153                         cpt_total_classes.inc(sub.to_s)
 154                 end
 155
 156                 # Equal monomorph case
 157                 if sub == sup then
 158                         cpt_total_variance.inc("monomorph")
 159                         return false
 160                 end
 161
 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")
 165                         return false
 166                 end
 167
 168                 # Formal case
 169                 if not sub isa MClassType then
 170                         cpt_total_variance.inc("polymorph & formal")
 171                         return false
 172                 end
 173
 174                 # Non generic case
 175                 if not sub isa MGenericType then
 176                         cpt_total_variance.inc("polymorph & non-generic")
 177                         return false
 178                 end
 179
 180                 # Invariant case
 181                 if sub.is_subtype_invar(mmodule, anchor, sup) then
 182                         cpt_total_variance.inc("polymorph & generic & invariant")
 183                         return false
 184                 end
 185
 186                 if sub.is_subtype(mmodule, anchor, sup) then
 187                         # Covariant
 188                         cpt_total_variance.inc("polymorph & generic & covariant")
 189                 else
 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")
 194                                 return false
 195                         end
 196
 197                         if not sup isa MGenericType then
 198                                 cpt_total_variance.inc("polymorph & generic & lateral-cast from non-gen")
 199                                 return false
 200                         end
 201
 202                         cpt_total_variance.inc("polymorph & generic & lateral-cast from gen")
 203                 end
 204
 205                 ## ONLY covariance remains here
 206
 207                 cpt_modules.inc(mmodule.mgroup.mproject.name)
 208                 cpt_classes.inc(sub.mclass)
 209
 210                 # Track if `cpt_explanations` is already decided (used to fallback on unknown)
 211                 var caseknown = false
 212
 213                 # Detect the pattern
 214                 var n = node
 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")
 229                                 caseknown = true
 230                         else
 231                                 node.debug("6.downcast {sup} to {sub}")
 232                         end
 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")
 237                 else
 238                         n.debug("Unknown pattern")
 239                         cpt_pattern.inc("X.unknown")
 240                 end
 241
 242                 if not caseknown then
 243                         if false then
 244                                 cpt_explanations.inc("covariant class")
 245                         else
 246                                 cpt_explanations.inc("other covariance")
 247                         end
 248                 end
 249
 250                 return true
 251         end
 252
 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)
 255         do
 256                 var nsup = sup
 257                 sup = sup.undecorate
 258                 sub = sub.undecorate
 259
 260                 if sub == nsup then
 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)")
 277                         else
 278                                 cpt_cast_pattern.inc("covariant downcast to a generic (same classes)")
 279                         end
 280                 else if not sup isa MGenericType then
 281                         cpt_cast_pattern.inc("invariant downcast from non-generic to a generic")
 282                 else
 283                         assert sup.mclass != sub.mclass
 284                         cpt_cast_pattern.inc("invariant downcast from generic to generic")
 285                 end
 286
 287                 cpt_cast_kind.inc(sub.class_name.to_s)
 288
 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
 293                 else
 294                         cpt_cast_classes.inc(sub.to_s)
 295                 end
 296         end
 297 end
 298
 299 redef class ModelBuilder
 300         redef fun check_subtype(node, mmodule, anchor, sub, sup)
 301         do
 302                 var res = super
 303                 var dcp = toolcontext.detect_covariance_phase
 304
 305                 if dcp.is_disabled then return res
 306
 307                 if res then
 308                         dcp.count_types(node, node, sub, sup, mmodule, anchor)
 309                 else
 310                         dcp.cpt_total_variance.inc("bad mb subtype")
 311                 end
 312
 313                 return res
 314         end
 315 end
 316
 317 redef class TypeVisitor
 318
 319         fun dcp: DetectCovariancePhase do return modelbuilder.toolcontext.detect_covariance_phase
 320
 321         redef fun visit_expr_cast(node, nexpr, ntype)
 322         do
 323                 var sub = super
 324
 325                 if dcp.is_disabled then return sub
 326
 327                 # In case of error, just forward
 328                 if sub == null then
 329                         dcp.cpt_total_variance.inc("bad cast")
 330                         return null
 331                 end
 332
 333                 var sup = nexpr.mtype.as(not null)
 334
 335                 if sub != ntype.mtype.as(not null) then
 336                         node.debug("fishy cast: res={sub} ntype={ntype.mtype.as(not null)}")
 337                 end
 338
 339                 dcp.count_types(node, nexpr, sub, sup, mmodule, anchor)
 340
 341                 dcp.count_cast(node, sub, sup, mmodule, anchor)
 342
 343                 return sub
 344         end
 345
 346         redef fun check_subtype(node: ANode, sub, sup: MType, autocast: Bool): nullable MType
 347         do
 348                 var res = super
 349
 350                 if dcp.is_disabled then return res
 351
 352                 var anchor = self.anchor
 353                 assert anchor != null
 354                 var supx = sup
 355                 var subx = sub
 356                 var p = node.parent.as(not null)
 357                 if p isa AExprs then p = p.parent.as(not null)
 358
 359                 # Case of autocast
 360                 if not self.is_subtype(sub, sup) then
 361                         if node isa AAsCastExpr then
 362                                 return res
 363                         end
 364                         if not autocast then
 365                                 return res
 366                         end
 367                         sup = supx.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, true)
 368                         if self.is_subtype(sub, sup) then
 369                                 dcp.cpt_autocast.inc("vt")
 370                                 dcp.count_cast(node, supx, sub, mmodule, anchor)
 371                         else
 372                                 sup = supx.resolve_for(anchor, null, mmodule, false)
 373                                 if self.is_subtype(sub, sup) then
 374                                         dcp.cpt_autocast.inc("vt+pt")
 375                                         dcp.count_cast(node, supx, sub, mmodule, anchor)
 376                                 else
 377                                         self.modelbuilder.error(node, "Type Error: expected `{sup}`, got `{sub}`")
 378                                         return null
 379                                 end
 380                         end
 381                         dcp.count_types(p, node, supx, subx, mmodule, anchor)
 382                         return res
 383                 end
 384
 385                 # Count case
 386                 if not dcp.count_types(p, node, sub, sup, mmodule, anchor) then return sub
 387
 388                 # Unknown explanation of covariance, go further
 389                 dcp.cpt_explanations["other covariance"] -= 1
 390
 391                 var n = node
 392                 if n isa AOnceExpr then n = n.n_expr
 393                 dcp.cpt_expression.inc(n.class_name)
 394
 395                 if node isa AArrayExpr then
 396                         dcp.cpt_explanations.inc("lit-array")
 397                 else if p isa ACallExpr and (p.n_id.text == "sort" or p.n_id.text == "linearize_mpropdefs") then
 398                         dcp.cpt_explanations.inc("generic methods (sort-method)")
 399                 else if p isa ACallExpr and p.n_id.text == "visit_list" then
 400                         dcp.cpt_explanations.inc("use-site covariance (visit_list-method)")
 401                 else
 402                         dcp.cpt_explanations.inc("other covariance")
 403                 end
 404                 return res
 405         end
 406 end
 407
 408 redef class MType
 409         # Return true if `self` is a invariant subtype of `sup`.
 410         # This is just a copy of the original `is_subtype` method with only two new lines
 411         fun is_subtype_invar(mmodule: MModule, anchor: nullable MClassType, sup: MType): Bool
 412         do
 413                 var sub = self
 414                 if sub == sup then return true
 415
 416                 #print "1.is {sub} a {sup}? ===="
 417
 418                 if anchor == null then
 419                         assert not sub.need_anchor
 420                         assert not sup.need_anchor
 421                 else
 422                         # First, resolve the formal types to the simplest equivalent forms in the receiver
 423                         assert sub.can_resolve_for(anchor, null, mmodule)
 424                         sub = sub.lookup_fixed(mmodule, anchor)
 425                         assert sup.can_resolve_for(anchor, null, mmodule)
 426                         sup = sup.lookup_fixed(mmodule, anchor)
 427                 end
 428
 429                 # Does `sup` accept null or not?
 430                 # Discard the nullable marker if it exists
 431                 var sup_accept_null = false
 432                 if sup isa MNullableType then
 433                         sup_accept_null = true
 434                         sup = sup.mtype
 435                 else if sup isa MNullType then
 436                         sup_accept_null = true
 437                 end
 438
 439                 # Can `sub` provide null or not?
 440                 # Thus we can match with `sup_accept_null`
 441                 # Also discard the nullable marker if it exists
 442                 if sub isa MNullableType then
 443                         if not sup_accept_null then return false
 444                         sub = sub.mtype
 445                 else if sub isa MNullType then
 446                         return sup_accept_null
 447                 end
 448                 # Now the case of direct null and nullable is over.
 449
 450                 # If `sub` is a formal type, then it is accepted if its bound is accepted
 451                 while sub isa MFormalType do
 452                         #print "3.is {sub} a {sup}?"
 453
 454                         # A unfixed formal type can only accept itself
 455                         if sub == sup then return true
 456
 457                         assert anchor != null
 458                         sub = sub.lookup_bound(mmodule, anchor)
 459
 460                         #print "3.is {sub} a {sup}?"
 461
 462                         # Manage the second layer of null/nullable
 463                         if sub isa MNullableType then
 464                                 if not sup_accept_null then return false
 465                                 sub = sub.mtype
 466                         else if sub isa MNullType then
 467                                 return sup_accept_null
 468                         end
 469                 end
 470                 #print "4.is {sub} a {sup}? <- no more resolution"
 471
 472                 assert sub isa MClassType # It is the only remaining type
 473
 474                 # A unfixed formal type can only accept itself
 475                 if sup isa MFormalType then
 476                         return false
 477                 end
 478
 479                 if sup isa MNullType then
 480                         # `sup` accepts only null
 481                         return false
 482                 end
 483
 484                 assert sup isa MClassType # It is the only remaining type
 485
 486                 # Now both are MClassType, we need to dig
 487
 488                 if sub == sup then return true
 489
 490                 if anchor == null then anchor = sub # UGLY: any anchor will work
 491                 var resolved_sub = sub.anchor_to(mmodule, anchor)
 492                 var res = resolved_sub.collect_mclasses(mmodule).has(sup.mclass)
 493                 if res == false then return false
 494                 if not sup isa MGenericType then return true
 495                 var sub2 = sub.supertype_to(mmodule, anchor, sup.mclass)
 496                 assert sub2.mclass == sup.mclass
 497                 for i in [0..sup.mclass.arity[ do
 498                         var sub_arg = sub2.arguments[i]
 499                         var sup_arg = sup.arguments[i]
 500                         res = sub_arg.is_subtype(mmodule, anchor, sup_arg)
 501                         if res == false then return false
 502                         # The two new lines
 503                         res = sup_arg.is_subtype(mmodule, anchor, sub_arg)
 504                         if res == false then return false
 505                         # End of the two new lines
 506                 end
 507                 return true
 508         end
 509 end