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.mpackage.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 check_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                 var supx = sup
 354                 var subx = sub
 355                 var p = node.parent.as(not null)
 356                 if p isa AExprs then p = p.parent.as(not null)
 357
 358                 # Case of autocast
 359                 if not self.is_subtype(sub, sup) then
 360                         if node isa AAsCastExpr then
 361                                 return res
 362                         end
 363                         if not autocast then
 364                                 return res
 365                         end
 366                         sup = supx.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, true)
 367                         if self.is_subtype(sub, sup) then
 368                                 dcp.cpt_autocast.inc("vt")
 369                                 dcp.count_cast(node, supx, sub, mmodule, anchor)
 370                         else
 371                                 sup = supx.resolve_for(anchor, null, mmodule, false)
 372                                 if self.is_subtype(sub, sup) then
 373                                         dcp.cpt_autocast.inc("vt+pt")
 374                                         dcp.count_cast(node, supx, sub, mmodule, anchor)
 375                                 else
 376                                         self.modelbuilder.error(node, "Type Error: expected `{sup}`, got `{sub}`")
 377                                         return null
 378                                 end
 379                         end
 380                         dcp.count_types(p, node, supx, subx, mmodule, anchor)
 381                         return res
 382                 end
 383
 384                 # Count case
 385                 if not dcp.count_types(p, node, sub, sup, mmodule, anchor) then return sub
 386
 387                 # Unknown explanation of covariance, go further
 388                 dcp.cpt_explanations["other covariance"] -= 1
 389
 390                 var n = node
 391                 if n isa AOnceExpr then n = n.n_expr
 392                 dcp.cpt_expression.inc(n.class_name)
 393
 394                 if node isa AArrayExpr then
 395                         dcp.cpt_explanations.inc("lit-array")
 396                 else if p isa ACallExpr then
 397                         var name = p.n_qid.n_id.text
 398                         if name == "sort" or name == "linearize_mpropdefs" then
 399                                 dcp.cpt_explanations.inc("generic methods (sort-method)")
 400                         else if name == "visit_list" then
 401                                 dcp.cpt_explanations.inc("use-site covariance (visit_list-method)")
 402                         else
 403                                 dcp.cpt_explanations.inc("other covariance")
 404                         end
 405                 else
 406                         dcp.cpt_explanations.inc("other covariance")
 407                 end
 408                 return res
 409         end
 410 end
 411
 412 redef class MType
 413         # Return true if `self` is a invariant subtype of `sup`.
 414         # This is just a copy of the original `is_subtype` method with only two new lines
 415         fun is_subtype_invar(mmodule: MModule, anchor: nullable MClassType, sup: MType): Bool
 416         do
 417                 var sub = self
 418                 if sub == sup then return true
 419
 420                 #print "1.is {sub} a {sup}? ===="
 421
 422                 if anchor == null then
 423                         assert not sub.need_anchor
 424                         assert not sup.need_anchor
 425                 else
 426                         # First, resolve the formal types to the simplest equivalent forms in the receiver
 427                         assert sub.can_resolve_for(anchor, null, mmodule)
 428                         sub = sub.lookup_fixed(mmodule, anchor)
 429                         assert sup.can_resolve_for(anchor, null, mmodule)
 430                         sup = sup.lookup_fixed(mmodule, anchor)
 431                 end
 432
 433                 # Does `sup` accept null or not?
 434                 # Discard the nullable marker if it exists
 435                 var sup_accept_null = false
 436                 if sup isa MNullableType then
 437                         sup_accept_null = true
 438                         sup = sup.mtype
 439                 else if sup isa MNullType then
 440                         sup_accept_null = true
 441                 end
 442
 443                 # Can `sub` provide null or not?
 444                 # Thus we can match with `sup_accept_null`
 445                 # Also discard the nullable marker if it exists
 446                 if sub isa MNullableType then
 447                         if not sup_accept_null then return false
 448                         sub = sub.mtype
 449                 else if sub isa MNullType then
 450                         return sup_accept_null
 451                 end
 452                 # Now the case of direct null and nullable is over.
 453
 454                 # If `sub` is a formal type, then it is accepted if its bound is accepted
 455                 while sub isa MFormalType do
 456                         #print "3.is {sub} a {sup}?"
 457
 458                         # A unfixed formal type can only accept itself
 459                         if sub == sup then return true
 460
 461                         assert anchor != null
 462                         sub = sub.lookup_bound(mmodule, anchor)
 463
 464                         #print "3.is {sub} a {sup}?"
 465
 466                         # Manage the second layer of null/nullable
 467                         if sub isa MNullableType then
 468                                 if not sup_accept_null then return false
 469                                 sub = sub.mtype
 470                         else if sub isa MNullType then
 471                                 return sup_accept_null
 472                         end
 473                 end
 474                 #print "4.is {sub} a {sup}? <- no more resolution"
 475
 476                 assert sub isa MClassType # It is the only remaining type
 477
 478                 # A unfixed formal type can only accept itself
 479                 if sup isa MFormalType then
 480                         return false
 481                 end
 482
 483                 if sup isa MNullType then
 484                         # `sup` accepts only null
 485                         return false
 486                 end
 487
 488                 assert sup isa MClassType # It is the only remaining type
 489
 490                 # Now both are MClassType, we need to dig
 491
 492                 if sub == sup then return true
 493
 494                 if anchor == null then anchor = sub # UGLY: any anchor will work
 495                 var resolved_sub = sub.anchor_to(mmodule, anchor)
 496                 var res = resolved_sub.collect_mclasses(mmodule).has(sup.mclass)
 497                 if res == false then return false
 498                 if not sup isa MGenericType then return true
 499                 var sub2 = sub.supertype_to(mmodule, anchor, sup.mclass)
 500                 assert sub2.mclass == sup.mclass
 501                 for i in [0..sup.mclass.arity[ do
 502                         var sub_arg = sub2.arguments[i]
 503                         var sup_arg = sup.arguments[i]
 504                         res = sub_arg.is_subtype(mmodule, anchor, sup_arg)
 505                         if res == false then return false
 506                         # The two new lines
 507                         res = sup_arg.is_subtype(mmodule, anchor, sub_arg)
 508                         if res == false then return false
 509                         # End of the two new lines
 510                 end
 511                 return true
 512         end
 513 end