| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 part of type_graph_inferrer; | |
| 6 | |
| 7 /** | |
| 8 * Common class for all nodes in the graph. The current nodes are: | |
| 9 * | |
| 10 * - Concrete types | |
| 11 * - Elements | |
| 12 * - Call sites | |
| 13 * - Narrowing instructions | |
| 14 * - Phi instructions | |
| 15 * - Containers (for lists) | |
| 16 * - Type of the element in a container | |
| 17 * | |
| 18 * A node has a set of assignments and users. Assignments are used to | |
| 19 * compute the type of the node ([TypeInformation.computeType]). Users are | |
| 20 * added to the inferrer's work queue when the type of the node | |
| 21 * changes. | |
| 22 */ | |
| 23 abstract class TypeInformation { | |
| 24 Set<TypeInformation> users; | |
| 25 var /* List|ParameterAssignments */ _assignments; | |
| 26 | |
| 27 /// The type the inferrer has found for this [TypeInformation]. | |
| 28 /// Initially empty. | |
| 29 TypeMask type = const TypeMask.nonNullEmpty(); | |
| 30 | |
| 31 /// The graph node of the member this [TypeInformation] node belongs to. | |
| 32 final MemberTypeInformation context; | |
| 33 | |
| 34 /// The element this [TypeInformation] node belongs to. | |
| 35 MemberElement get contextMember => context == null ? null : context.element; | |
| 36 | |
| 37 Iterable<TypeInformation> get assignments => _assignments; | |
| 38 | |
| 39 /// We abandon inference in certain cases (complex cyclic flow, native | |
| 40 /// behaviours, etc.). In some case, we might resume inference in the | |
| 41 /// closure tracer, which is handled by checking whether [assignments] has | |
| 42 /// been set to [STOP_TRACKING_ASSIGNMENTS_MARKER]. | |
| 43 bool abandonInferencing = false; | |
| 44 bool get mightResume => | |
| 45 !identical(assignments, STOP_TRACKING_ASSIGNMENTS_MARKER); | |
| 46 | |
| 47 /// Number of times this [TypeInformation] has changed type. | |
| 48 int refineCount = 0; | |
| 49 | |
| 50 /// Whether this [TypeInformation] is currently in the inferrer's | |
| 51 /// work queue. | |
| 52 bool inQueue = false; | |
| 53 | |
| 54 /// Used to disable enqueueing of type informations where we know that their | |
| 55 /// type will not change for other reasons than being stable. For example, | |
| 56 /// if inference is disabled for a type and it is hardwired to dynamic, this | |
| 57 /// is set to true to spare recomputing dynamic again and again. Changing this | |
| 58 /// to false should never change inference outcome, just make is slower. | |
| 59 bool doNotEnqueue = false; | |
| 60 | |
| 61 /// Whether this [TypeInformation] has a stable [type] that will not | |
| 62 /// change. | |
| 63 bool isStable = false; | |
| 64 | |
| 65 // TypeInformations are unique. | |
| 66 static int staticHashCode = 0; | |
| 67 final int hashCode = staticHashCode++; | |
| 68 | |
| 69 bool get isConcrete => false; | |
| 70 | |
| 71 TypeInformation(this.context) : _assignments = <TypeInformation>[], | |
| 72 users = new Setlet<TypeInformation>(); | |
| 73 | |
| 74 TypeInformation.noAssignments(this.context) | |
| 75 : _assignments = const <TypeInformation>[], | |
| 76 users = new Setlet<TypeInformation>(); | |
| 77 | |
| 78 TypeInformation.untracked() | |
| 79 : _assignments = const <TypeInformation>[], | |
| 80 users = const ImmutableEmptySet(), | |
| 81 context = null; | |
| 82 | |
| 83 TypeInformation.withAssignments(this.context, this._assignments) | |
| 84 : users = new Setlet<TypeInformation>(); | |
| 85 | |
| 86 void addUser(TypeInformation user) { | |
| 87 assert(!user.isConcrete); | |
| 88 users.add(user); | |
| 89 } | |
| 90 | |
| 91 void removeUser(TypeInformation user) { | |
| 92 assert(!user.isConcrete); | |
| 93 users.remove(user); | |
| 94 } | |
| 95 | |
| 96 // The below is not a compile time constant to make it differentiable | |
| 97 // from other empty lists of [TypeInformation]. | |
| 98 static final STOP_TRACKING_ASSIGNMENTS_MARKER = new List<TypeInformation>(0); | |
| 99 | |
| 100 bool areAssignmentsTracked() { | |
| 101 return assignments != STOP_TRACKING_ASSIGNMENTS_MARKER; | |
| 102 } | |
| 103 | |
| 104 void addAssignment(TypeInformation assignment) { | |
| 105 // Cheap one-level cycle detection. | |
| 106 if (assignment == this) return; | |
| 107 if (areAssignmentsTracked()) { | |
| 108 _assignments.add(assignment); | |
| 109 } | |
| 110 // Even if we abandon inferencing on this [TypeInformation] we | |
| 111 // need to collect the users, so that phases that track where | |
| 112 // elements flow in still work. | |
| 113 assignment.addUser(this); | |
| 114 } | |
| 115 | |
| 116 void removeAssignment(TypeInformation assignment) { | |
| 117 if (!abandonInferencing || mightResume) { | |
| 118 _assignments.remove(assignment); | |
| 119 } | |
| 120 // We can have multiple assignments of the same [TypeInformation]. | |
| 121 if (!assignments.contains(assignment)) { | |
| 122 assignment.removeUser(this); | |
| 123 } | |
| 124 } | |
| 125 | |
| 126 TypeMask refine(TypeGraphInferrerEngine inferrer) { | |
| 127 return abandonInferencing ? safeType(inferrer) : computeType(inferrer); | |
| 128 } | |
| 129 | |
| 130 /** | |
| 131 * Computes a new type for this [TypeInformation] node depending on its | |
| 132 * potentially updated inputs. | |
| 133 */ | |
| 134 TypeMask computeType(TypeGraphInferrerEngine inferrer); | |
| 135 | |
| 136 /** | |
| 137 * Returns an approximation for this [TypeInformation] node that is always | |
| 138 * safe to use. Used when abandoning inference on a node. | |
| 139 */ | |
| 140 TypeMask safeType(TypeGraphInferrerEngine inferrer) { | |
| 141 return inferrer.types.dynamicType.type; | |
| 142 } | |
| 143 | |
| 144 void giveUp(TypeGraphInferrerEngine inferrer, {bool clearAssignments: true}) { | |
| 145 abandonInferencing = true; | |
| 146 // Do not remove [this] as a user of nodes in [assignments], | |
| 147 // because our tracing analysis could be interested in tracing | |
| 148 // this node. | |
| 149 if (clearAssignments) _assignments = STOP_TRACKING_ASSIGNMENTS_MARKER; | |
| 150 // Do not remove users because our tracing analysis could be | |
| 151 // interested in tracing the users of this node. | |
| 152 } | |
| 153 | |
| 154 void clear() { | |
| 155 _assignments = STOP_TRACKING_ASSIGNMENTS_MARKER; | |
| 156 users = const ImmutableEmptySet(); | |
| 157 } | |
| 158 | |
| 159 /// Reset the analysis of this node by making its type empty. | |
| 160 | |
| 161 bool reset(TypeGraphInferrerEngine inferrer) { | |
| 162 if (abandonInferencing) return false; | |
| 163 type = const TypeMask.nonNullEmpty(); | |
| 164 refineCount = 0; | |
| 165 return true; | |
| 166 } | |
| 167 | |
| 168 accept(TypeInformationVisitor visitor); | |
| 169 | |
| 170 /// The [Element] where this [TypeInformation] was created. May be | |
| 171 /// for some [TypeInformation] nodes, where we do not need to store | |
| 172 /// the information. | |
| 173 Element get owner => null; | |
| 174 | |
| 175 /// Returns whether the type cannot change after it has been | |
| 176 /// inferred. | |
| 177 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 178 return !mightResume && assignments.every((e) => e.isStable); | |
| 179 } | |
| 180 | |
| 181 void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { | |
| 182 assignments.forEach((info) { info.removeUser(this); }); | |
| 183 } | |
| 184 | |
| 185 void stabilize(TypeGraphInferrerEngine inferrer) { | |
| 186 removeAndClearReferences(inferrer); | |
| 187 // Do not remove users because the tracing analysis could be interested | |
| 188 // in tracing the users of this node. | |
| 189 _assignments = STOP_TRACKING_ASSIGNMENTS_MARKER; | |
| 190 abandonInferencing = true; | |
| 191 isStable = true; | |
| 192 } | |
| 193 | |
| 194 void maybeResume() { | |
| 195 if (!mightResume) return; | |
| 196 abandonInferencing = false; | |
| 197 doNotEnqueue = false; | |
| 198 } | |
| 199 } | |
| 200 | |
| 201 abstract class ApplyableTypeInformation implements TypeInformation { | |
| 202 bool mightBePassedToFunctionApply = false; | |
| 203 } | |
| 204 | |
| 205 /** | |
| 206 * Marker node used only during tree construction but not during actual type | |
| 207 * refinement. | |
| 208 * | |
| 209 * Currently, this is used to give a type to an optional parameter even before | |
| 210 * the corresponding default expression has been analyzed. See | |
| 211 * [getDefaultTypeOfParameter] and [setDefaultTypeOfParameter] for details. | |
| 212 */ | |
| 213 class PlaceholderTypeInformation extends TypeInformation { | |
| 214 PlaceholderTypeInformation(MemberTypeInformation context) : super(context); | |
| 215 | |
| 216 void accept(TypeInformationVisitor visitor) { | |
| 217 throw new UnsupportedError("Cannot visit placeholder"); | |
| 218 } | |
| 219 | |
| 220 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 221 throw new UnsupportedError("Cannot refine placeholder"); | |
| 222 } | |
| 223 | |
| 224 toString() => "Placeholder [$hashCode]"; | |
| 225 } | |
| 226 | |
| 227 /** | |
| 228 * Parameters of instance functions behave differently than other | |
| 229 * elements because the inferrer may remove assignments. This happens | |
| 230 * when the receiver of a dynamic call site can be refined | |
| 231 * to a type where we know more about which instance method is being | |
| 232 * called. | |
| 233 */ | |
| 234 class ParameterAssignments extends IterableBase<TypeInformation> { | |
| 235 final Map<TypeInformation, int> assignments = | |
| 236 new Map<TypeInformation, int>(); | |
| 237 | |
| 238 void remove(TypeInformation info) { | |
| 239 int existing = assignments[info]; | |
| 240 if (existing == null) return; | |
| 241 if (existing == 1) { | |
| 242 assignments.remove(info); | |
| 243 } else { | |
| 244 assignments[info] = existing - 1; | |
| 245 } | |
| 246 } | |
| 247 | |
| 248 void add(TypeInformation info) { | |
| 249 int existing = assignments[info]; | |
| 250 if (existing == null) { | |
| 251 assignments[info] = 1; | |
| 252 } else { | |
| 253 assignments[info] = existing + 1; | |
| 254 } | |
| 255 } | |
| 256 | |
| 257 void replace(TypeInformation old, TypeInformation replacement) { | |
| 258 int existing = assignments[old]; | |
| 259 if (existing != null) { | |
| 260 int other = assignments[replacement]; | |
| 261 if (other != null) existing += other; | |
| 262 assignments[replacement] = existing; | |
| 263 assignments.remove(old); | |
| 264 } | |
| 265 } | |
| 266 | |
| 267 Iterator<TypeInformation> get iterator => assignments.keys.iterator; | |
| 268 Iterable<TypeInformation> where(Function f) => assignments.keys.where(f); | |
| 269 | |
| 270 bool contains(TypeInformation info) => assignments.containsKey(info); | |
| 271 | |
| 272 String toString() => assignments.keys.toList().toString(); | |
| 273 } | |
| 274 | |
| 275 /** | |
| 276 * A node representing a resolved element of the program. The kind of | |
| 277 * elements that need an [ElementTypeInformation] are: | |
| 278 * | |
| 279 * - Functions (including getters and setters) | |
| 280 * - Constructors (factory or generative) | |
| 281 * - Fields | |
| 282 * - Parameters | |
| 283 * - Local variables mutated in closures | |
| 284 * | |
| 285 * The [ElementTypeInformation] of a function and a constructor is its | |
| 286 * return type. | |
| 287 * | |
| 288 * Note that a few elements of these kinds must be treated specially, | |
| 289 * and they are dealt in [ElementTypeInformation.handleSpecialCases]: | |
| 290 * | |
| 291 * - Parameters of closures, [noSuchMethod] and [call] instance | |
| 292 * methods: we currently do not infer types for those. | |
| 293 * | |
| 294 * - Fields and parameters being assigned by synthesized calls done by | |
| 295 * the backend: we do not know what types the backend will use. | |
| 296 * | |
| 297 * - Native functions and fields: because native methods contain no Dart | |
| 298 * code, and native fields do not have Dart assignments, we just | |
| 299 * trust their type annotation. | |
| 300 * | |
| 301 */ | |
| 302 abstract class ElementTypeInformation extends TypeInformation { | |
| 303 final Element element; | |
| 304 | |
| 305 /// Marker to disable inference for closures in [handleSpecialCases]. | |
| 306 bool disableInferenceForClosures = true; | |
| 307 | |
| 308 factory ElementTypeInformation(Element element, TypeInformationSystem types) { | |
| 309 if (element.isParameter || element.isInitializingFormal) { | |
| 310 ParameterElement parameter = element; | |
| 311 if (parameter.functionDeclaration.isInstanceMember) { | |
| 312 return new ParameterTypeInformation._instanceMember(element, types); | |
| 313 } | |
| 314 return new ParameterTypeInformation._internal(element, types); | |
| 315 } | |
| 316 return new MemberTypeInformation._internal(element); | |
| 317 } | |
| 318 | |
| 319 ElementTypeInformation._internal(MemberTypeInformation context, this.element) | |
| 320 : super(context); | |
| 321 ElementTypeInformation._withAssignments(MemberTypeInformation context, | |
| 322 this.element, assignments) | |
| 323 : super.withAssignments(context, assignments); | |
| 324 } | |
| 325 | |
| 326 /** | |
| 327 * A node representing members in the broadest sense: | |
| 328 * | |
| 329 * - Functions | |
| 330 * - Constructors | |
| 331 * - Fields (also synthetic ones due to closures) | |
| 332 * - Local functions (closures) | |
| 333 * | |
| 334 * These should never be created directly but instead are constructed by | |
| 335 * the [ElementTypeInformation] factory. | |
| 336 */ | |
| 337 class MemberTypeInformation extends ElementTypeInformation | |
| 338 with ApplyableTypeInformation { | |
| 339 TypedElement get element => super.element; | |
| 340 | |
| 341 /** | |
| 342 * If [element] is a function, [closurizedCount] is the number of | |
| 343 * times it is closurized. The value gets updated while infering. | |
| 344 */ | |
| 345 int closurizedCount = 0; | |
| 346 | |
| 347 /** | |
| 348 * This map contains the callers of [element]. It stores all unique call sites | |
| 349 * to enable counting the global number of call sites of [element]. | |
| 350 * | |
| 351 * A call site is either an AST [ast.Node], a [cps_ir.Node] or in the case of | |
| 352 * synthesized calls, an [Element] (see uses of [synthesizeForwardingCall] | |
| 353 * in [SimpleTypeInferrerVisitor]). | |
| 354 */ | |
| 355 final Map<Element, Setlet<Spannable>> _callers = new Map<Element, Setlet>(); | |
| 356 | |
| 357 MemberTypeInformation._internal(Element element) | |
| 358 : super._internal(null, element); | |
| 359 | |
| 360 void addCall(Element caller, Spannable node) { | |
| 361 assert(node is ast.Node || node is cps_ir.Node || node is Element); | |
| 362 _callers.putIfAbsent(caller, () => new Setlet()).add(node); | |
| 363 } | |
| 364 | |
| 365 void removeCall(Element caller, node) { | |
| 366 Setlet calls = _callers[caller]; | |
| 367 if (calls == null) return; | |
| 368 calls.remove(node); | |
| 369 if (calls.isEmpty) { | |
| 370 _callers.remove(caller); | |
| 371 } | |
| 372 } | |
| 373 | |
| 374 Iterable<Element> get callers => _callers.keys; | |
| 375 | |
| 376 bool isCalledOnce() { | |
| 377 int count = 0; | |
| 378 for (var set in _callers.values) { | |
| 379 count += set.length; | |
| 380 if (count > 1) return false; | |
| 381 } | |
| 382 return count == 1; | |
| 383 } | |
| 384 | |
| 385 bool get isClosurized => closurizedCount > 0; | |
| 386 | |
| 387 // Closurized methods never become stable to ensure that the information in | |
| 388 // [users] is accurate. The inference stops tracking users for stable types. | |
| 389 // Note that we only override the getter, the setter will still modify the | |
| 390 // state of the [isStable] field inhertied from [TypeInformation]. | |
| 391 bool get isStable => super.isStable && !isClosurized; | |
| 392 | |
| 393 TypeMask handleSpecialCases(TypeGraphInferrerEngine inferrer) { | |
| 394 if (element.isField && | |
| 395 !inferrer.compiler.backend.canBeUsedForGlobalOptimizations(element)) { | |
| 396 // Do not infer types for fields being assigned by synthesized calls. | |
| 397 giveUp(inferrer); | |
| 398 return safeType(inferrer); | |
| 399 } | |
| 400 if (inferrer.isNativeElement(element)) { | |
| 401 // Use the type annotation as the type for native elements. We | |
| 402 // also give up on inferring to make sure this element never | |
| 403 // goes in the work queue. | |
| 404 giveUp(inferrer); | |
| 405 if (element.isField) { | |
| 406 return inferrer.typeOfNativeBehavior( | |
| 407 native.NativeBehavior.ofFieldLoad(element, inferrer.compiler)).type; | |
| 408 } else { | |
| 409 assert(element.isFunction || | |
| 410 element.isGetter || | |
| 411 element.isSetter); | |
| 412 TypedElement typedElement = element; | |
| 413 var elementType = typedElement.type; | |
| 414 if (elementType.kind != TypeKind.FUNCTION) { | |
| 415 return safeType(inferrer); | |
| 416 } else { | |
| 417 return inferrer.typeOfNativeBehavior( | |
| 418 native.NativeBehavior.ofMethod(element, inferrer.compiler)).type; | |
| 419 } | |
| 420 } | |
| 421 } | |
| 422 | |
| 423 Compiler compiler = inferrer.compiler; | |
| 424 if (element.declaration == compiler.intEnvironment) { | |
| 425 giveUp(inferrer); | |
| 426 return compiler.typesTask.intType.nullable(); | |
| 427 } else if (element.declaration == compiler.boolEnvironment) { | |
| 428 giveUp(inferrer); | |
| 429 return compiler.typesTask.boolType.nullable(); | |
| 430 } else if (element.declaration == compiler.stringEnvironment) { | |
| 431 giveUp(inferrer); | |
| 432 return compiler.typesTask.stringType.nullable(); | |
| 433 } | |
| 434 return null; | |
| 435 } | |
| 436 | |
| 437 TypeMask potentiallyNarrowType(TypeMask mask, | |
| 438 TypeGraphInferrerEngine inferrer) { | |
| 439 Compiler compiler = inferrer.compiler; | |
| 440 if (!compiler.trustTypeAnnotations && !compiler.enableTypeAssertions) { | |
| 441 return mask; | |
| 442 } | |
| 443 if (element.isGenerativeConstructor || | |
| 444 element.isSetter) { | |
| 445 return mask; | |
| 446 } | |
| 447 if (element.isField) { | |
| 448 return new TypeMaskSystem(compiler).narrowType(mask, element.type); | |
| 449 } | |
| 450 assert(element.isFunction || | |
| 451 element.isGetter || | |
| 452 element.isFactoryConstructor); | |
| 453 | |
| 454 FunctionType type = element.type; | |
| 455 return new TypeMaskSystem(compiler).narrowType(mask, type.returnType); | |
| 456 } | |
| 457 | |
| 458 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 459 TypeMask special = handleSpecialCases(inferrer); | |
| 460 if (special != null) return potentiallyNarrowType(special, inferrer); | |
| 461 return potentiallyNarrowType( | |
| 462 inferrer.types.computeTypeMask(assignments), inferrer); | |
| 463 } | |
| 464 | |
| 465 TypeMask safeType(TypeGraphInferrerEngine inferrer) { | |
| 466 return potentiallyNarrowType(super.safeType(inferrer), inferrer); | |
| 467 } | |
| 468 | |
| 469 String toString() => 'MemberElement $element $type'; | |
| 470 | |
| 471 accept(TypeInformationVisitor visitor) { | |
| 472 return visitor.visitMemberTypeInformation(this); | |
| 473 } | |
| 474 | |
| 475 Element get owner => element.outermostEnclosingMemberOrTopLevel; | |
| 476 | |
| 477 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 478 // The number of assignments of non-final fields is | |
| 479 // not stable. Therefore such a field cannot be stable. | |
| 480 if (element.isField && !(element.isConst || element.isFinal)) { | |
| 481 return false; | |
| 482 } | |
| 483 | |
| 484 if (element.isFunction) return false; | |
| 485 | |
| 486 return super.hasStableType(inferrer); | |
| 487 } | |
| 488 } | |
| 489 | |
| 490 /** | |
| 491 * A node representing parameters: | |
| 492 * | |
| 493 * - Parameters | |
| 494 * - Initializing formals | |
| 495 * | |
| 496 * These should never be created directly but instead are constructed by | |
| 497 * the [ElementTypeInformation] factory. | |
| 498 */ | |
| 499 class ParameterTypeInformation extends ElementTypeInformation { | |
| 500 ParameterElement get element => super.element; | |
| 501 | |
| 502 ParameterTypeInformation._internal(ParameterElement element, | |
| 503 TypeInformationSystem types) | |
| 504 : super._internal(types.getInferredTypeOf(element.functionDeclaration), | |
| 505 element) { | |
| 506 assert(!element.functionDeclaration.isInstanceMember); | |
| 507 } | |
| 508 | |
| 509 ParameterTypeInformation._instanceMember(ParameterElement element, | |
| 510 TypeInformationSystem types) | |
| 511 : super._withAssignments( | |
| 512 types.getInferredTypeOf(element.functionDeclaration), | |
| 513 element, | |
| 514 new ParameterAssignments()) { | |
| 515 assert(element.functionDeclaration.isInstanceMember); | |
| 516 } | |
| 517 | |
| 518 bool isTearOffClosureParameter = false; | |
| 519 | |
| 520 void tagAsTearOffClosureParameter(TypeGraphInferrerEngine inferrer) { | |
| 521 assert(element.isParameter); | |
| 522 isTearOffClosureParameter = true; | |
| 523 } | |
| 524 | |
| 525 // TODO(herhut): Cleanup into one conditional. | |
| 526 TypeMask handleSpecialCases(TypeGraphInferrerEngine inferrer) { | |
| 527 if (!inferrer.compiler.backend.canBeUsedForGlobalOptimizations(element)) { | |
| 528 // Do not infer types for fields and parameters being assigned | |
| 529 // by synthesized calls. | |
| 530 giveUp(inferrer); | |
| 531 return safeType(inferrer); | |
| 532 } | |
| 533 | |
| 534 // The below do not apply to parameters of constructors, so skip | |
| 535 // initializing formals. | |
| 536 if (element.isInitializingFormal) return null; | |
| 537 | |
| 538 FunctionElement function = element.functionDeclaration; | |
| 539 if ((isTearOffClosureParameter || function.isLocal) && | |
| 540 disableInferenceForClosures) { | |
| 541 // Do not infer types for parameters of closures. We do not | |
| 542 // clear the assignments in case the closure is successfully | |
| 543 // traced. | |
| 544 giveUp(inferrer, clearAssignments: false); | |
| 545 return safeType(inferrer); | |
| 546 } | |
| 547 if (function.isInstanceMember && | |
| 548 (function.name == Compiler.NO_SUCH_METHOD || | |
| 549 (function.name == Compiler.CALL_OPERATOR_NAME && | |
| 550 disableInferenceForClosures))) { | |
| 551 // Do not infer types for parameters of [noSuchMethod] and | |
| 552 // [call] instance methods. | |
| 553 giveUp(inferrer); | |
| 554 return safeType(inferrer); | |
| 555 } | |
| 556 if (function == inferrer.mainElement) { | |
| 557 // The implicit call to main is not seen by the inferrer, | |
| 558 // therefore we explicitly set the type of its parameters as | |
| 559 // dynamic. | |
| 560 // TODO(14566): synthesize a call instead to get the exact | |
| 561 // types. | |
| 562 giveUp(inferrer); | |
| 563 return safeType(inferrer); | |
| 564 } | |
| 565 | |
| 566 return null; | |
| 567 } | |
| 568 | |
| 569 TypeMask potentiallyNarrowType(TypeMask mask, | |
| 570 TypeGraphInferrerEngine inferrer) { | |
| 571 Compiler compiler = inferrer.compiler; | |
| 572 if (!compiler.trustTypeAnnotations) { | |
| 573 return mask; | |
| 574 } | |
| 575 // When type assertions are enabled (aka checked mode), we have to always | |
| 576 // ignore type annotations to ensure that the checks are actually inserted | |
| 577 // into the function body and retained until runtime. | |
| 578 assert(!compiler.enableTypeAssertions); | |
| 579 return new TypeMaskSystem(compiler).narrowType(mask, element.type); | |
| 580 } | |
| 581 | |
| 582 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 583 TypeMask special = handleSpecialCases(inferrer); | |
| 584 if (special != null) return special; | |
| 585 return potentiallyNarrowType(inferrer.types.computeTypeMask(assignments), | |
| 586 inferrer); | |
| 587 } | |
| 588 | |
| 589 TypeMask safeType(TypeGraphInferrerEngine inferrer) { | |
| 590 return potentiallyNarrowType(super.safeType(inferrer), inferrer); | |
| 591 } | |
| 592 | |
| 593 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 594 // The number of assignments of parameters of instance methods is | |
| 595 // not stable. Therefore such a parameter cannot be stable. | |
| 596 if (element.functionDeclaration.isInstanceMember) { | |
| 597 return false; | |
| 598 } | |
| 599 return super.hasStableType(inferrer); | |
| 600 } | |
| 601 | |
| 602 accept(TypeInformationVisitor visitor) { | |
| 603 return visitor.visitParameterTypeInformation(this); | |
| 604 } | |
| 605 | |
| 606 String toString() => 'ParameterElement $element $type'; | |
| 607 } | |
| 608 | |
| 609 /** | |
| 610 * A [CallSiteTypeInformation] is a call found in the AST, or a | |
| 611 * synthesized call for implicit calls in Dart (such as forwarding | |
| 612 * factories). The [call] field is a [ast.Node] for the former, and an | |
| 613 * [Element] for the latter. | |
| 614 * | |
| 615 * In the inferrer graph, [CallSiteTypeInformation] nodes do not have | |
| 616 * any assignment. They rely on the [caller] field for static calls, | |
| 617 * and [selector] and [receiver] fields for dynamic calls. | |
| 618 */ | |
| 619 abstract class CallSiteTypeInformation extends TypeInformation | |
| 620 with ApplyableTypeInformation { | |
| 621 final Spannable call; | |
| 622 final Element caller; | |
| 623 final Selector selector; | |
| 624 final ArgumentsTypes arguments; | |
| 625 final bool inLoop; | |
| 626 | |
| 627 CallSiteTypeInformation( | |
| 628 MemberTypeInformation context, | |
| 629 this.call, | |
| 630 this.caller, | |
| 631 this.selector, | |
| 632 this.arguments, | |
| 633 this.inLoop) : super.noAssignments(context); | |
| 634 | |
| 635 String toString() => 'Call site $call $type'; | |
| 636 | |
| 637 /// Add [this] to the graph being computed by [engine]. | |
| 638 void addToGraph(TypeGraphInferrerEngine engine); | |
| 639 | |
| 640 /// Return an iterable over the targets of this call. | |
| 641 Iterable<Element> get callees; | |
| 642 | |
| 643 Element get owner => caller; | |
| 644 } | |
| 645 | |
| 646 class StaticCallSiteTypeInformation extends CallSiteTypeInformation { | |
| 647 final Element calledElement; | |
| 648 | |
| 649 StaticCallSiteTypeInformation( | |
| 650 MemberTypeInformation context, | |
| 651 Spannable call, | |
| 652 Element enclosing, | |
| 653 this.calledElement, | |
| 654 Selector selector, | |
| 655 ArgumentsTypes arguments, | |
| 656 bool inLoop) | |
| 657 : super(context, call, enclosing, selector, arguments, inLoop); | |
| 658 | |
| 659 void addToGraph(TypeGraphInferrerEngine inferrer) { | |
| 660 MemberTypeInformation callee = | |
| 661 inferrer.types.getInferredTypeOf(calledElement); | |
| 662 callee.addCall(caller, call); | |
| 663 callee.addUser(this); | |
| 664 if (arguments != null) { | |
| 665 arguments.forEach((info) => info.addUser(this)); | |
| 666 } | |
| 667 inferrer.updateParameterAssignments( | |
| 668 this, calledElement, arguments, selector, remove: false, | |
| 669 addToQueue: false); | |
| 670 } | |
| 671 | |
| 672 bool get isSynthesized { | |
| 673 // Some calls do not have a corresponding node, for example | |
| 674 // fowarding factory constructors, or synthesized super | |
| 675 // constructor calls. We synthesize these calls but do | |
| 676 // not create a selector for them. | |
| 677 return selector == null; | |
| 678 } | |
| 679 | |
| 680 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 681 if (isSynthesized) { | |
| 682 assert(arguments != null); | |
| 683 return inferrer.types.getInferredTypeOf(calledElement).type; | |
| 684 } else { | |
| 685 return inferrer.typeOfElementWithSelector(calledElement, selector).type; | |
| 686 } | |
| 687 } | |
| 688 | |
| 689 Iterable<Element> get callees => [calledElement.implementation]; | |
| 690 | |
| 691 accept(TypeInformationVisitor visitor) { | |
| 692 return visitor.visitStaticCallSiteTypeInformation(this); | |
| 693 } | |
| 694 | |
| 695 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 696 return inferrer.types.getInferredTypeOf(calledElement).isStable && | |
| 697 (arguments == null || arguments.every((info) => info.isStable)) && | |
| 698 super.hasStableType(inferrer); | |
| 699 } | |
| 700 | |
| 701 void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { | |
| 702 ElementTypeInformation callee = | |
| 703 inferrer.types.getInferredTypeOf(calledElement); | |
| 704 callee.removeUser(this); | |
| 705 if (arguments != null) { | |
| 706 arguments.forEach((info) => info.removeUser(this)); | |
| 707 } | |
| 708 super.removeAndClearReferences(inferrer); | |
| 709 } | |
| 710 } | |
| 711 | |
| 712 class DynamicCallSiteTypeInformation extends CallSiteTypeInformation { | |
| 713 final TypeInformation receiver; | |
| 714 /// Cached targets of this call. | |
| 715 Iterable<Element> targets; | |
| 716 | |
| 717 DynamicCallSiteTypeInformation( | |
| 718 MemberTypeInformation context, | |
| 719 Spannable call, | |
| 720 Element enclosing, | |
| 721 Selector selector, | |
| 722 this.receiver, | |
| 723 ArgumentsTypes arguments, | |
| 724 bool inLoop) | |
| 725 : super(context, call, enclosing, selector, arguments, inLoop); | |
| 726 | |
| 727 void addToGraph(TypeGraphInferrerEngine inferrer) { | |
| 728 assert(receiver != null); | |
| 729 Selector typedSelector = computeTypedSelector(inferrer); | |
| 730 targets = inferrer.compiler.world.allFunctions.filter(typedSelector); | |
| 731 receiver.addUser(this); | |
| 732 if (arguments != null) { | |
| 733 arguments.forEach((info) => info.addUser(this)); | |
| 734 } | |
| 735 for (Element element in targets) { | |
| 736 MemberTypeInformation callee = inferrer.types.getInferredTypeOf(element); | |
| 737 callee.addCall(caller, call); | |
| 738 callee.addUser(this); | |
| 739 inferrer.updateParameterAssignments( | |
| 740 this, element, arguments, typedSelector, remove: false, | |
| 741 addToQueue: false); | |
| 742 } | |
| 743 } | |
| 744 | |
| 745 Iterable<Element> get callees => targets.map((e) => e.implementation); | |
| 746 | |
| 747 Selector computeTypedSelector(TypeGraphInferrerEngine inferrer) { | |
| 748 TypeMask receiverType = receiver.type; | |
| 749 | |
| 750 if (selector.mask != receiverType) { | |
| 751 return receiverType == inferrer.compiler.typesTask.dynamicType | |
| 752 ? selector.asUntyped | |
| 753 : new TypedSelector(receiverType, selector, inferrer.classWorld); | |
| 754 } else { | |
| 755 return selector; | |
| 756 } | |
| 757 } | |
| 758 | |
| 759 bool get targetsIncludeNoSuchMethod { | |
| 760 return targets.any((Element e) { | |
| 761 return e is FunctionElement && | |
| 762 e.isInstanceMember && | |
| 763 e.name == Compiler.NO_SUCH_METHOD; | |
| 764 }); | |
| 765 } | |
| 766 | |
| 767 /** | |
| 768 * We optimize certain operations on the [int] class because we know | |
| 769 * more about their return type than the actual Dart code. For | |
| 770 * example, we know int + int returns an int. The Dart code for | |
| 771 * [int.operator+] only says it returns a [num]. | |
| 772 */ | |
| 773 TypeInformation handleIntrisifiedSelector(Selector selector, | |
| 774 TypeGraphInferrerEngine inferrer) { | |
| 775 ClassWorld classWorld = inferrer.classWorld; | |
| 776 if (!classWorld.backend.intImplementation.isResolved) return null; | |
| 777 TypeMask emptyType = const TypeMask.nonNullEmpty(); | |
| 778 if (selector.mask == null) return null; | |
| 779 if (!selector.mask.containsOnlyInt(classWorld)) { | |
| 780 return null; | |
| 781 } | |
| 782 if (!selector.isCall && !selector.isOperator) return null; | |
| 783 if (!arguments.named.isEmpty) return null; | |
| 784 if (arguments.positional.length > 1) return null; | |
| 785 | |
| 786 ClassElement uint31Implementation = classWorld.backend.uint31Implementation; | |
| 787 bool isInt(info) => info.type.containsOnlyInt(classWorld); | |
| 788 bool isEmpty(info) => info.type == emptyType; | |
| 789 bool isUInt31(info) { | |
| 790 return info.type.satisfies(uint31Implementation, classWorld); | |
| 791 } | |
| 792 bool isPositiveInt(info) { | |
| 793 return info.type.satisfies( | |
| 794 classWorld.backend.positiveIntImplementation, classWorld); | |
| 795 } | |
| 796 | |
| 797 String name = selector.name; | |
| 798 // We are optimizing for the cases that are not expressed in the | |
| 799 // Dart code, for example: | |
| 800 // int + int -> int | |
| 801 // uint31 | uint31 -> uint31 | |
| 802 if (name == '*' || name == '+' || name == '%' || name == 'remainder' || | |
| 803 name == '~/') { | |
| 804 if (isPositiveInt(receiver) && | |
| 805 arguments.hasOnePositionalArgumentThatMatches(isPositiveInt)) { | |
| 806 return inferrer.types.positiveIntType; | |
| 807 } else if (arguments.hasOnePositionalArgumentThatMatches(isInt)) { | |
| 808 return inferrer.types.intType; | |
| 809 } else if (arguments.hasOnePositionalArgumentThatMatches(isEmpty)) { | |
| 810 return inferrer.types.nonNullEmptyType; | |
| 811 } else { | |
| 812 return null; | |
| 813 } | |
| 814 } else if (name == '|' || name == '^') { | |
| 815 if (isUInt31(receiver) && | |
| 816 arguments.hasOnePositionalArgumentThatMatches(isUInt31)) { | |
| 817 return inferrer.types.uint31Type; | |
| 818 } | |
| 819 } else if (name == '>>') { | |
| 820 if (isUInt31(receiver)) { | |
| 821 return inferrer.types.uint31Type; | |
| 822 } | |
| 823 } else if (name == '&') { | |
| 824 if (isUInt31(receiver) || | |
| 825 arguments.hasOnePositionalArgumentThatMatches(isUInt31)) { | |
| 826 return inferrer.types.uint31Type; | |
| 827 } | |
| 828 } else if (name == 'unary-') { | |
| 829 // The receiver being an int, the return value will also be an | |
| 830 // int. | |
| 831 return inferrer.types.intType; | |
| 832 } else if (name == '-') { | |
| 833 if (arguments.hasOnePositionalArgumentThatMatches(isInt)) { | |
| 834 return inferrer.types.intType; | |
| 835 } else if (arguments.hasOnePositionalArgumentThatMatches(isEmpty)) { | |
| 836 return inferrer.types.nonNullEmptyType; | |
| 837 } | |
| 838 return null; | |
| 839 } else if (name == 'abs') { | |
| 840 return arguments.hasNoArguments() ? inferrer.types.positiveIntType : null; | |
| 841 } | |
| 842 return null; | |
| 843 } | |
| 844 | |
| 845 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 846 Iterable<Element> oldTargets = targets; | |
| 847 Selector typedSelector = computeTypedSelector(inferrer); | |
| 848 inferrer.updateSelectorInTree(caller, call, typedSelector); | |
| 849 | |
| 850 Compiler compiler = inferrer.compiler; | |
| 851 Selector selectorToUse = typedSelector.extendIfReachesAll(compiler); | |
| 852 bool canReachAll = compiler.enabledInvokeOn && | |
| 853 (selectorToUse != typedSelector); | |
| 854 | |
| 855 // If this call could potentially reach all methods that satisfy | |
| 856 // the untyped selector (through noSuchMethod's `Invocation` | |
| 857 // and a call to `delegate`), we iterate over all these methods to | |
| 858 // update their parameter types. | |
| 859 targets = compiler.world.allFunctions.filter(selectorToUse); | |
| 860 Iterable<Element> typedTargets = canReachAll | |
| 861 ? compiler.world.allFunctions.filter(typedSelector) | |
| 862 : targets; | |
| 863 | |
| 864 // Walk over the found targets, and compute the joined union type mask | |
| 865 // for all these targets. | |
| 866 TypeMask newType = inferrer.types.joinTypeMasks(targets.map((element) { | |
| 867 if (!oldTargets.contains(element)) { | |
| 868 MemberTypeInformation callee = | |
| 869 inferrer.types.getInferredTypeOf(element); | |
| 870 callee.addCall(caller, call); | |
| 871 callee.addUser(this); | |
| 872 inferrer.updateParameterAssignments( | |
| 873 this, element, arguments, typedSelector, remove: false, | |
| 874 addToQueue: true); | |
| 875 } | |
| 876 | |
| 877 // If [canReachAll] is true, then we are iterating over all | |
| 878 // targets that satisfy the untyped selector. We skip the return | |
| 879 // type of the targets that can only be reached through | |
| 880 // `Invocation.delegate`. Note that the `noSuchMethod` targets | |
| 881 // are included in [typedTargets]. | |
| 882 if (canReachAll && !typedTargets.contains(element)) { | |
| 883 return const TypeMask.nonNullEmpty(); | |
| 884 } | |
| 885 | |
| 886 if (inferrer.returnsListElementType(typedSelector)) { | |
| 887 ContainerTypeMask mask = receiver.type; | |
| 888 return mask.elementType; | |
| 889 } else if (inferrer.returnsMapValueType(typedSelector)) { | |
| 890 if (typedSelector.mask.isDictionary && | |
| 891 arguments.positional[0].type.isValue) { | |
| 892 DictionaryTypeMask mask = typedSelector.mask; | |
| 893 ValueTypeMask arg = arguments.positional[0].type; | |
| 894 String key = arg.value; | |
| 895 if (mask.typeMap.containsKey(key)) { | |
| 896 if (_VERBOSE) { | |
| 897 print("Dictionary lookup for $key yields ${mask.typeMap[key]}."); | |
| 898 } | |
| 899 return mask.typeMap[key]; | |
| 900 } else { | |
| 901 // The typeMap is precise, so if we do not find the key, the lookup | |
| 902 // will be [null] at runtime. | |
| 903 if (_VERBOSE) { | |
| 904 print("Dictionary lookup for $key yields [null]."); | |
| 905 } | |
| 906 return inferrer.types.nullType.type; | |
| 907 } | |
| 908 } | |
| 909 MapTypeMask mask = typedSelector.mask; | |
| 910 if (_VERBOSE) { | |
| 911 print("Map lookup for $typedSelector yields ${mask.valueType}."); | |
| 912 } | |
| 913 return mask.valueType; | |
| 914 } else { | |
| 915 TypeInformation info = | |
| 916 handleIntrisifiedSelector(typedSelector, inferrer); | |
| 917 if (info != null) return info.type; | |
| 918 return inferrer.typeOfElementWithSelector(element, typedSelector).type; | |
| 919 } | |
| 920 })); | |
| 921 | |
| 922 // Walk over the old targets, and remove calls that cannot happen | |
| 923 // anymore. | |
| 924 oldTargets.forEach((element) { | |
| 925 if (!targets.contains(element)) { | |
| 926 MemberTypeInformation callee = | |
| 927 inferrer.types.getInferredTypeOf(element); | |
| 928 callee.removeCall(caller, call); | |
| 929 callee.removeUser(this); | |
| 930 inferrer.updateParameterAssignments( | |
| 931 this, element, arguments, typedSelector, remove: true, | |
| 932 addToQueue: true); | |
| 933 } | |
| 934 }); | |
| 935 | |
| 936 return newType; | |
| 937 } | |
| 938 | |
| 939 void giveUp(TypeGraphInferrerEngine inferrer, {bool clearAssignments: true}) { | |
| 940 if (!abandonInferencing) { | |
| 941 inferrer.updateSelectorInTree(caller, call, selector); | |
| 942 Iterable<Element> oldTargets = targets; | |
| 943 targets = inferrer.compiler.world.allFunctions.filter(selector); | |
| 944 for (Element element in targets) { | |
| 945 if (!oldTargets.contains(element)) { | |
| 946 MemberTypeInformation callee = | |
| 947 inferrer.types.getInferredTypeOf(element); | |
| 948 callee.addCall(caller, call); | |
| 949 inferrer.updateParameterAssignments( | |
| 950 this, element, arguments, selector, remove: false, | |
| 951 addToQueue: true); | |
| 952 } | |
| 953 } | |
| 954 } | |
| 955 super.giveUp(inferrer, clearAssignments: clearAssignments); | |
| 956 } | |
| 957 | |
| 958 void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { | |
| 959 for (Element element in targets) { | |
| 960 ElementTypeInformation callee = inferrer.types.getInferredTypeOf(element); | |
| 961 callee.removeUser(this); | |
| 962 } | |
| 963 if (arguments != null) { | |
| 964 arguments.forEach((info) => info.removeUser(this)); | |
| 965 } | |
| 966 super.removeAndClearReferences(inferrer); | |
| 967 } | |
| 968 | |
| 969 String toString() => 'Call site $call on ${receiver.type} $type'; | |
| 970 | |
| 971 accept(TypeInformationVisitor visitor) { | |
| 972 return visitor.visitDynamicCallSiteTypeInformation(this); | |
| 973 } | |
| 974 | |
| 975 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 976 return receiver.isStable && | |
| 977 targets.every( | |
| 978 (element) => inferrer.types.getInferredTypeOf(element).isStable) && | |
| 979 (arguments == null || arguments.every((info) => info.isStable)) && | |
| 980 super.hasStableType(inferrer); | |
| 981 } | |
| 982 } | |
| 983 | |
| 984 class ClosureCallSiteTypeInformation extends CallSiteTypeInformation { | |
| 985 final TypeInformation closure; | |
| 986 | |
| 987 ClosureCallSiteTypeInformation( | |
| 988 MemberTypeInformation context, | |
| 989 Spannable call, | |
| 990 Element enclosing, | |
| 991 Selector selector, | |
| 992 this.closure, | |
| 993 ArgumentsTypes arguments, | |
| 994 bool inLoop) | |
| 995 : super(context, call, enclosing, selector, arguments, inLoop); | |
| 996 | |
| 997 void addToGraph(TypeGraphInferrerEngine inferrer) { | |
| 998 arguments.forEach((info) => info.addUser(this)); | |
| 999 closure.addUser(this); | |
| 1000 } | |
| 1001 | |
| 1002 TypeMask computeType(TypeGraphInferrerEngine inferrer) => safeType(inferrer); | |
| 1003 | |
| 1004 Iterable<Element> get callees { | |
| 1005 throw new UnsupportedError("Cannot compute callees of a closure call."); | |
| 1006 } | |
| 1007 | |
| 1008 String toString() => 'Closure call $call on $closure'; | |
| 1009 | |
| 1010 accept(TypeInformationVisitor visitor) { | |
| 1011 return visitor.visitClosureCallSiteTypeInformation(this); | |
| 1012 } | |
| 1013 | |
| 1014 void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { | |
| 1015 // This method is a placeholder for the following comment: | |
| 1016 // We should maintain the information that the closure is a user | |
| 1017 // of its arguments because we do not check that the arguments | |
| 1018 // have a stable type for a closure call to be stable; our tracing | |
| 1019 // analysis want to know whether an (non-stable) argument is | |
| 1020 // passed to a closure. | |
| 1021 return super.removeAndClearReferences(inferrer); | |
| 1022 } | |
| 1023 } | |
| 1024 | |
| 1025 /** | |
| 1026 * A [ConcreteTypeInformation] represents a type that needed | |
| 1027 * to be materialized during the creation of the graph. For example, | |
| 1028 * literals, [:this:] or [:super:] need a [ConcreteTypeInformation]. | |
| 1029 * | |
| 1030 * [ConcreteTypeInformation] nodes have no assignment. Also, to save | |
| 1031 * on memory, we do not add users to [ConcreteTypeInformation] nodes, | |
| 1032 * because we know such node will never be refined to a different | |
| 1033 * type. | |
| 1034 */ | |
| 1035 class ConcreteTypeInformation extends TypeInformation { | |
| 1036 ConcreteTypeInformation(TypeMask type) : super.untracked() { | |
| 1037 this.type = type; | |
| 1038 this.isStable = true; | |
| 1039 } | |
| 1040 | |
| 1041 bool get isConcrete => true; | |
| 1042 | |
| 1043 void addUser(TypeInformation user) { | |
| 1044 // Nothing to do, a concrete type does not get updated so never | |
| 1045 // needs to notify its users. | |
| 1046 } | |
| 1047 | |
| 1048 void removeUser(TypeInformation user) { | |
| 1049 } | |
| 1050 | |
| 1051 void addAssignment(TypeInformation assignment) { | |
| 1052 throw "Not supported"; | |
| 1053 } | |
| 1054 | |
| 1055 void removeAssignment(TypeInformation assignment) { | |
| 1056 throw "Not supported"; | |
| 1057 } | |
| 1058 | |
| 1059 TypeMask computeType(TypeGraphInferrerEngine inferrer) => type; | |
| 1060 | |
| 1061 bool reset(TypeGraphInferrerEngine inferrer) { | |
| 1062 throw "Not supported"; | |
| 1063 } | |
| 1064 | |
| 1065 String toString() => 'Type $type'; | |
| 1066 | |
| 1067 accept(TypeInformationVisitor visitor) { | |
| 1068 return visitor.visitConcreteTypeInformation(this); | |
| 1069 } | |
| 1070 | |
| 1071 bool hasStableType(TypeGraphInferrerEngine inferrer) => true; | |
| 1072 } | |
| 1073 | |
| 1074 class StringLiteralTypeInformation extends ConcreteTypeInformation { | |
| 1075 final ast.DartString value; | |
| 1076 | |
| 1077 StringLiteralTypeInformation(value, TypeMask mask) | |
| 1078 : super(new ValueTypeMask(mask, value.slowToString())), | |
| 1079 this.value = value; | |
| 1080 | |
| 1081 String asString() => value.slowToString(); | |
| 1082 String toString() => 'Type $type value ${value.slowToString()}'; | |
| 1083 | |
| 1084 accept(TypeInformationVisitor visitor) { | |
| 1085 return visitor.visitStringLiteralTypeInformation(this); | |
| 1086 } | |
| 1087 } | |
| 1088 | |
| 1089 /** | |
| 1090 * A [NarrowTypeInformation] narrows a [TypeInformation] to a type, | |
| 1091 * represented in [typeAnnotation]. | |
| 1092 * | |
| 1093 * A [NarrowTypeInformation] node has only one assignment: the | |
| 1094 * [TypeInformation] it narrows. | |
| 1095 * | |
| 1096 * [NarrowTypeInformation] nodes are created for: | |
| 1097 * | |
| 1098 * - Code after `is` and `as` checks, where we have more information | |
| 1099 * on the type of the right hand side of the expression. | |
| 1100 * | |
| 1101 * - Code after a dynamic call, where we have more information on the | |
| 1102 * type of the receiver: it can only be of a class that holds a | |
| 1103 * potential target of this dynamic call. | |
| 1104 * | |
| 1105 * - In checked mode, after a type annotation, we have more | |
| 1106 * information on the type of a local. | |
| 1107 */ | |
| 1108 class NarrowTypeInformation extends TypeInformation { | |
| 1109 final TypeMask typeAnnotation; | |
| 1110 | |
| 1111 NarrowTypeInformation(TypeInformation narrowedType, this.typeAnnotation) | |
| 1112 : super(narrowedType.context) { | |
| 1113 addAssignment(narrowedType); | |
| 1114 } | |
| 1115 | |
| 1116 addAssignment(TypeInformation info) { | |
| 1117 super.addAssignment(info); | |
| 1118 assert(assignments.length == 1); | |
| 1119 } | |
| 1120 | |
| 1121 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 1122 TypeMask input = assignments.first.type; | |
| 1123 TypeMask intersection = input.intersection(typeAnnotation, | |
| 1124 inferrer.classWorld); | |
| 1125 if (_ANOMALY_WARN) { | |
| 1126 if (!input.containsMask(intersection, inferrer.classWorld) || | |
| 1127 !typeAnnotation.containsMask(intersection, inferrer.classWorld)) { | |
| 1128 print("ANOMALY WARNING: narrowed $input to $intersection via " | |
| 1129 "$typeAnnotation"); | |
| 1130 } | |
| 1131 } | |
| 1132 return intersection; | |
| 1133 } | |
| 1134 | |
| 1135 String toString() { | |
| 1136 return 'Narrow to $typeAnnotation $type'; | |
| 1137 } | |
| 1138 | |
| 1139 accept(TypeInformationVisitor visitor) { | |
| 1140 return visitor.visitNarrowTypeInformation(this); | |
| 1141 } | |
| 1142 } | |
| 1143 | |
| 1144 /** | |
| 1145 * An [InferredTypeInformation] is a [TypeInformation] that | |
| 1146 * defaults to the dynamic type until it is marked as beeing | |
| 1147 * inferred, at which point it computes its type based on | |
| 1148 * its assignments. | |
| 1149 */ | |
| 1150 abstract class InferredTypeInformation extends TypeInformation { | |
| 1151 /** Whether the element type in that container has been inferred. */ | |
| 1152 bool inferred = false; | |
| 1153 | |
| 1154 InferredTypeInformation(MemberTypeInformation context, | |
| 1155 TypeInformation parentType) | |
| 1156 : super(context) { | |
| 1157 if (parentType != null) addAssignment(parentType); | |
| 1158 } | |
| 1159 | |
| 1160 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 1161 if (!inferred) return safeType(inferrer); | |
| 1162 return inferrer.types.computeTypeMask(assignments); | |
| 1163 } | |
| 1164 | |
| 1165 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 1166 return inferred && super.hasStableType(inferrer); | |
| 1167 } | |
| 1168 } | |
| 1169 | |
| 1170 /** | |
| 1171 * A [ListTypeInformation] is a [TypeInformation] created | |
| 1172 * for each `List` instantiations. | |
| 1173 */ | |
| 1174 class ListTypeInformation extends TypeInformation | |
| 1175 with TracedTypeInformation { | |
| 1176 final ElementInContainerTypeInformation elementType; | |
| 1177 | |
| 1178 /** The container type before it is inferred. */ | |
| 1179 final ContainerTypeMask originalType; | |
| 1180 | |
| 1181 /** The length at the allocation site. */ | |
| 1182 final int originalLength; | |
| 1183 | |
| 1184 /** The length after the container has been traced. */ | |
| 1185 int inferredLength; | |
| 1186 | |
| 1187 /** | |
| 1188 * Whether this list goes through a growable check. | |
| 1189 * We conservatively assume it does. | |
| 1190 */ | |
| 1191 bool checksGrowable = true; | |
| 1192 | |
| 1193 ListTypeInformation(MemberTypeInformation context, | |
| 1194 this.originalType, | |
| 1195 this.elementType, | |
| 1196 this.originalLength) | |
| 1197 : super(context) { | |
| 1198 type = originalType; | |
| 1199 inferredLength = originalType.length; | |
| 1200 elementType.addUser(this); | |
| 1201 } | |
| 1202 | |
| 1203 String toString() => 'List type $type'; | |
| 1204 | |
| 1205 accept(TypeInformationVisitor visitor) { | |
| 1206 return visitor.visitListTypeInformation(this); | |
| 1207 } | |
| 1208 | |
| 1209 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 1210 return elementType.isStable && super.hasStableType(inferrer); | |
| 1211 } | |
| 1212 | |
| 1213 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 1214 var mask = type; | |
| 1215 if (!mask.isContainer || | |
| 1216 mask.elementType != elementType.type || | |
| 1217 mask.length != inferredLength) { | |
| 1218 return new ContainerTypeMask(originalType.forwardTo, | |
| 1219 originalType.allocationNode, | |
| 1220 originalType.allocationElement, | |
| 1221 elementType.type, | |
| 1222 inferredLength); | |
| 1223 } | |
| 1224 return mask; | |
| 1225 } | |
| 1226 | |
| 1227 TypeMask safeType(TypeGraphInferrerEngine inferrer) => originalType; | |
| 1228 } | |
| 1229 | |
| 1230 /** | |
| 1231 * An [ElementInContainerTypeInformation] holds the common type of the | |
| 1232 * elements in a [ListTypeInformation]. | |
| 1233 */ | |
| 1234 class ElementInContainerTypeInformation extends InferredTypeInformation { | |
| 1235 ElementInContainerTypeInformation(MemberTypeInformation context, | |
| 1236 elementType) | |
| 1237 : super(context, elementType); | |
| 1238 | |
| 1239 String toString() => 'Element in container $type'; | |
| 1240 | |
| 1241 accept(TypeInformationVisitor visitor) { | |
| 1242 return visitor.visitElementInContainerTypeInformation(this); | |
| 1243 } | |
| 1244 } | |
| 1245 | |
| 1246 /** | |
| 1247 * A [MapTypeInformation] is a [TypeInformation] created | |
| 1248 * for maps. | |
| 1249 */ | |
| 1250 class MapTypeInformation extends TypeInformation | |
| 1251 with TracedTypeInformation { | |
| 1252 // When in Dictionary mode, this map tracks the type of the values that | |
| 1253 // have been assigned to a specific [String] key. | |
| 1254 final Map<String, ValueInMapTypeInformation> typeInfoMap = {}; | |
| 1255 // These fields track the overall type of the keys/values in the map. | |
| 1256 final KeyInMapTypeInformation keyType; | |
| 1257 final ValueInMapTypeInformation valueType; | |
| 1258 final MapTypeMask originalType; | |
| 1259 | |
| 1260 // Set to false if a statically unknown key flows into this map. | |
| 1261 bool _allKeysAreStrings = true; | |
| 1262 | |
| 1263 bool get inDictionaryMode => !bailedOut && _allKeysAreStrings; | |
| 1264 | |
| 1265 MapTypeInformation(MemberTypeInformation context, | |
| 1266 this.originalType, | |
| 1267 this.keyType, | |
| 1268 this.valueType) | |
| 1269 : super(context) { | |
| 1270 keyType.addUser(this); | |
| 1271 valueType.addUser(this); | |
| 1272 type = originalType; | |
| 1273 } | |
| 1274 | |
| 1275 TypeInformation addEntryAssignment(TypeInformation key, | |
| 1276 TypeInformation value, | |
| 1277 [bool nonNull = false]) { | |
| 1278 TypeInformation newInfo = null; | |
| 1279 if (_allKeysAreStrings && key is StringLiteralTypeInformation) { | |
| 1280 String keyString = key.asString(); | |
| 1281 typeInfoMap.putIfAbsent(keyString, () { | |
| 1282 newInfo = new ValueInMapTypeInformation(context, null, nonNull); | |
| 1283 return newInfo; | |
| 1284 }); | |
| 1285 typeInfoMap[keyString].addAssignment(value); | |
| 1286 } else { | |
| 1287 _allKeysAreStrings = false; | |
| 1288 typeInfoMap.clear(); | |
| 1289 } | |
| 1290 keyType.addAssignment(key); | |
| 1291 valueType.addAssignment(value); | |
| 1292 if (newInfo != null) newInfo.addUser(this); | |
| 1293 | |
| 1294 return newInfo; | |
| 1295 } | |
| 1296 | |
| 1297 List<TypeInformation> addMapAssignment(MapTypeInformation other) { | |
| 1298 List<TypeInformation> newInfos = <TypeInformation>[]; | |
| 1299 if (_allKeysAreStrings && other.inDictionaryMode) { | |
| 1300 other.typeInfoMap.forEach((keyString, value) { | |
| 1301 typeInfoMap.putIfAbsent(keyString, () { | |
| 1302 TypeInformation newInfo = | |
| 1303 new ValueInMapTypeInformation(context, null, false); | |
| 1304 newInfos.add(newInfo); | |
| 1305 return newInfo; | |
| 1306 }); | |
| 1307 typeInfoMap[keyString].addAssignment(value); | |
| 1308 }); | |
| 1309 } else { | |
| 1310 _allKeysAreStrings = false; | |
| 1311 typeInfoMap.clear(); | |
| 1312 } | |
| 1313 keyType.addAssignment(other.keyType); | |
| 1314 valueType.addAssignment(other.valueType); | |
| 1315 | |
| 1316 return newInfos; | |
| 1317 } | |
| 1318 | |
| 1319 markAsInferred() { | |
| 1320 keyType.inferred = valueType.inferred = true; | |
| 1321 typeInfoMap.values.forEach((v) => v.inferred = true); | |
| 1322 } | |
| 1323 | |
| 1324 addAssignment(TypeInformation other) { | |
| 1325 throw "not supported"; | |
| 1326 } | |
| 1327 | |
| 1328 accept(TypeInformationVisitor visitor) { | |
| 1329 return visitor.visitMapTypeInformation(this); | |
| 1330 } | |
| 1331 | |
| 1332 TypeMask toTypeMask(TypeGraphInferrerEngine inferrer) { | |
| 1333 if (inDictionaryMode) { | |
| 1334 Map<String, TypeMask> mappings = new Map<String, TypeMask>(); | |
| 1335 for (var key in typeInfoMap.keys) { | |
| 1336 mappings[key] = typeInfoMap[key].type; | |
| 1337 } | |
| 1338 return new DictionaryTypeMask(originalType.forwardTo, | |
| 1339 originalType.allocationNode, | |
| 1340 originalType.allocationElement, | |
| 1341 keyType.type, | |
| 1342 valueType.type, | |
| 1343 mappings); | |
| 1344 } else { | |
| 1345 return new MapTypeMask(originalType.forwardTo, | |
| 1346 originalType.allocationNode, | |
| 1347 originalType.allocationElement, | |
| 1348 keyType.type, | |
| 1349 valueType.type); | |
| 1350 } | |
| 1351 } | |
| 1352 | |
| 1353 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 1354 if (type.isDictionary != inDictionaryMode) { | |
| 1355 return toTypeMask(inferrer); | |
| 1356 } else if (type.isDictionary) { | |
| 1357 assert(inDictionaryMode); | |
| 1358 DictionaryTypeMask mask = type; | |
| 1359 for (var key in typeInfoMap.keys) { | |
| 1360 TypeInformation value = typeInfoMap[key]; | |
| 1361 if (!mask.typeMap.containsKey(key) && | |
| 1362 !value.type.containsAll(inferrer.classWorld) && | |
| 1363 !value.type.isNullable) { | |
| 1364 return toTypeMask(inferrer); | |
| 1365 } | |
| 1366 if (mask.typeMap[key] != typeInfoMap[key].type) { | |
| 1367 return toTypeMask(inferrer); | |
| 1368 } | |
| 1369 } | |
| 1370 } else if (type.isMap) { | |
| 1371 MapTypeMask mask = type; | |
| 1372 if (mask.keyType != keyType.type || | |
| 1373 mask.valueType != valueType.type) { | |
| 1374 return toTypeMask(inferrer); | |
| 1375 } | |
| 1376 } else { | |
| 1377 return toTypeMask(inferrer); | |
| 1378 } | |
| 1379 | |
| 1380 return type; | |
| 1381 } | |
| 1382 | |
| 1383 TypeMask safeType(TypeGraphInferrerEngine inferrer) => originalType; | |
| 1384 | |
| 1385 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 1386 return keyType.isStable && | |
| 1387 valueType.isStable && | |
| 1388 super.hasStableType(inferrer); | |
| 1389 } | |
| 1390 | |
| 1391 String toString() { | |
| 1392 return 'Map $type (K:$keyType, V:$valueType) contents $typeInfoMap'; | |
| 1393 } | |
| 1394 } | |
| 1395 | |
| 1396 /** | |
| 1397 * A [KeyInMapTypeInformation] holds the common type | |
| 1398 * for the keys in a [MapTypeInformation] | |
| 1399 */ | |
| 1400 class KeyInMapTypeInformation extends InferredTypeInformation { | |
| 1401 KeyInMapTypeInformation(MemberTypeInformation context, | |
| 1402 TypeInformation keyType) | |
| 1403 : super(context, keyType); | |
| 1404 | |
| 1405 accept(TypeInformationVisitor visitor) { | |
| 1406 return visitor.visitKeyInMapTypeInformation(this); | |
| 1407 } | |
| 1408 | |
| 1409 String toString() => 'Key in Map $type'; | |
| 1410 } | |
| 1411 | |
| 1412 /** | |
| 1413 * A [ValueInMapTypeInformation] holds the common type | |
| 1414 * for the values in a [MapTypeInformation] | |
| 1415 */ | |
| 1416 class ValueInMapTypeInformation extends InferredTypeInformation { | |
| 1417 // [nonNull] is set to true if this value is known to be part of the map. | |
| 1418 // Note that only values assigned to a specific key value in dictionary | |
| 1419 // mode can ever be marked as [nonNull]. | |
| 1420 final bool nonNull; | |
| 1421 | |
| 1422 ValueInMapTypeInformation(MemberTypeInformation context, | |
| 1423 TypeInformation valueType, [this.nonNull = false]) | |
| 1424 : super(context, valueType); | |
| 1425 | |
| 1426 accept(TypeInformationVisitor visitor) { | |
| 1427 return visitor.visitValueInMapTypeInformation(this); | |
| 1428 } | |
| 1429 | |
| 1430 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 1431 return nonNull ? super.computeType(inferrer) | |
| 1432 : super.computeType(inferrer).nullable(); | |
| 1433 } | |
| 1434 | |
| 1435 String toString() => 'Value in Map $type'; | |
| 1436 } | |
| 1437 | |
| 1438 /** | |
| 1439 * A [PhiElementTypeInformation] is an union of | |
| 1440 * [ElementTypeInformation], that is local to a method. | |
| 1441 */ | |
| 1442 class PhiElementTypeInformation extends TypeInformation { | |
| 1443 final ast.Node branchNode; | |
| 1444 final bool isLoopPhi; | |
| 1445 final Local variable; | |
| 1446 | |
| 1447 PhiElementTypeInformation(MemberTypeInformation context, this.branchNode, | |
| 1448 this.isLoopPhi, this.variable) | |
| 1449 : super(context); | |
| 1450 | |
| 1451 TypeMask computeType(TypeGraphInferrerEngine inferrer) { | |
| 1452 return inferrer.types.computeTypeMask(assignments); | |
| 1453 } | |
| 1454 | |
| 1455 String toString() => 'Phi $variable $type'; | |
| 1456 | |
| 1457 accept(TypeInformationVisitor visitor) { | |
| 1458 return visitor.visitPhiElementTypeInformation(this); | |
| 1459 } | |
| 1460 } | |
| 1461 | |
| 1462 class ClosureTypeInformation extends TypeInformation | |
| 1463 with ApplyableTypeInformation { | |
| 1464 final ast.Node node; | |
| 1465 final Element element; | |
| 1466 | |
| 1467 ClosureTypeInformation(MemberTypeInformation context, this.node, | |
| 1468 this.element) | |
| 1469 : super(context); | |
| 1470 | |
| 1471 TypeMask computeType(TypeGraphInferrerEngine inferrer) => safeType(inferrer); | |
| 1472 | |
| 1473 TypeMask safeType(TypeGraphInferrerEngine inferrer) { | |
| 1474 return inferrer.types.functionType.type; | |
| 1475 } | |
| 1476 | |
| 1477 String toString() => 'Closure $element'; | |
| 1478 | |
| 1479 accept(TypeInformationVisitor visitor) { | |
| 1480 return visitor.visitClosureTypeInformation(this); | |
| 1481 } | |
| 1482 | |
| 1483 bool hasStableType(TypeGraphInferrerEngine inferrer) { | |
| 1484 return false; | |
| 1485 } | |
| 1486 } | |
| 1487 | |
| 1488 /** | |
| 1489 * Mixin for [TypeInformation] nodes that can bail out during tracing. | |
| 1490 */ | |
| 1491 abstract class TracedTypeInformation implements TypeInformation { | |
| 1492 /// Set to false once analysis has succeeded. | |
| 1493 bool bailedOut = true; | |
| 1494 /// Set to true once analysis is completed. | |
| 1495 bool analyzed = false; | |
| 1496 | |
| 1497 Set<TypeInformation> _flowsInto; | |
| 1498 | |
| 1499 /** | |
| 1500 * The set of [TypeInformation] nodes where values from the traced node could | |
| 1501 * flow in. | |
| 1502 */ | |
| 1503 Set<TypeInformation> get flowsInto { | |
| 1504 return (_flowsInto == null) ? const ImmutableEmptySet<TypeInformation>() | |
| 1505 : _flowsInto; | |
| 1506 } | |
| 1507 | |
| 1508 /** | |
| 1509 * Adds [nodes] to the sets of values this [TracedTypeInformation] flows into. | |
| 1510 */ | |
| 1511 void addFlowsIntoTargets(Iterable<TypeInformation> nodes) { | |
| 1512 if (_flowsInto == null) { | |
| 1513 _flowsInto = nodes.toSet(); | |
| 1514 } else { | |
| 1515 _flowsInto.addAll(nodes); | |
| 1516 } | |
| 1517 } | |
| 1518 } | |
| 1519 | |
| 1520 abstract class TypeInformationVisitor<T> { | |
| 1521 T visitNarrowTypeInformation(NarrowTypeInformation info); | |
| 1522 T visitPhiElementTypeInformation(PhiElementTypeInformation info); | |
| 1523 T visitElementInContainerTypeInformation( | |
| 1524 ElementInContainerTypeInformation info); | |
| 1525 T visitKeyInMapTypeInformation(KeyInMapTypeInformation info); | |
| 1526 T visitValueInMapTypeInformation(ValueInMapTypeInformation info); | |
| 1527 T visitListTypeInformation(ListTypeInformation info); | |
| 1528 T visitMapTypeInformation(MapTypeInformation info); | |
| 1529 T visitConcreteTypeInformation(ConcreteTypeInformation info); | |
| 1530 T visitStringLiteralTypeInformation(StringLiteralTypeInformation info); | |
| 1531 T visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info); | |
| 1532 T visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info); | |
| 1533 T visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info); | |
| 1534 T visitMemberTypeInformation(MemberTypeInformation info); | |
| 1535 T visitParameterTypeInformation(ParameterTypeInformation info); | |
| 1536 T visitClosureTypeInformation(ClosureTypeInformation info); | |
| 1537 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart