| 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 library type_graph_inferrer; | |
| 6 | |
| 7 import 'dart:collection' show Queue, IterableBase; | |
| 8 | |
| 9 import '../constants/expressions.dart'; | |
| 10 import '../constants/values.dart'; | |
| 11 import '../cps_ir/cps_ir_nodes.dart' as cps_ir | |
| 12 show Node; | |
| 13 import '../dart_types.dart' | |
| 14 show DartType, | |
| 15 FunctionType, | |
| 16 InterfaceType, | |
| 17 TypeKind; | |
| 18 import '../dart2jslib.dart' | |
| 19 show ClassWorld, | |
| 20 Compiler, | |
| 21 Constant, | |
| 22 FunctionConstant, | |
| 23 invariant, | |
| 24 TreeElementMapping; | |
| 25 import '../elements/elements.dart'; | |
| 26 import '../native/native.dart' as native; | |
| 27 import '../tree/tree.dart' as ast | |
| 28 show DartString, | |
| 29 Node, | |
| 30 TryStatement; | |
| 31 import '../types/types.dart' | |
| 32 show ContainerTypeMask, | |
| 33 DictionaryTypeMask, | |
| 34 MapTypeMask, | |
| 35 TypeMask, | |
| 36 TypesInferrer, | |
| 37 ValueTypeMask; | |
| 38 import '../universe/universe.dart' | |
| 39 show Selector, | |
| 40 SideEffects, | |
| 41 TypedSelector; | |
| 42 import '../util/util.dart' | |
| 43 show ImmutableEmptySet, | |
| 44 Setlet, | |
| 45 Spannable; | |
| 46 | |
| 47 import 'inferrer_visitor.dart' | |
| 48 show ArgumentsTypes, | |
| 49 TypeSystem; | |
| 50 import 'simple_types_inferrer.dart'; | |
| 51 | |
| 52 part 'closure_tracer.dart'; | |
| 53 part 'list_tracer.dart'; | |
| 54 part 'map_tracer.dart'; | |
| 55 part 'node_tracer.dart'; | |
| 56 part 'type_graph_nodes.dart'; | |
| 57 | |
| 58 bool _VERBOSE = false; | |
| 59 bool _PRINT_SUMMARY = false; | |
| 60 final _ANOMALY_WARN = false; | |
| 61 | |
| 62 class TypeInformationSystem extends TypeSystem<TypeInformation> { | |
| 63 final Compiler compiler; | |
| 64 final ClassWorld classWorld; | |
| 65 | |
| 66 /// [ElementTypeInformation]s for elements. | |
| 67 final Map<Element, TypeInformation> typeInformations = | |
| 68 new Map<Element, TypeInformation>(); | |
| 69 | |
| 70 /// [ListTypeInformation] for allocated lists. | |
| 71 final Map<ast.Node, TypeInformation> allocatedLists = | |
| 72 new Map<ast.Node, TypeInformation>(); | |
| 73 | |
| 74 /// [MapTypeInformation] for allocated Maps. | |
| 75 final Map<ast.Node, TypeInformation> allocatedMaps = | |
| 76 new Map<ast.Node, TypeInformation>(); | |
| 77 | |
| 78 /// Closures found during the analysis. | |
| 79 final Set<TypeInformation> allocatedClosures = new Set<TypeInformation>(); | |
| 80 | |
| 81 /// Cache of [ConcreteTypeInformation]. | |
| 82 final Map<TypeMask, TypeInformation> concreteTypes = | |
| 83 new Map<TypeMask, TypeInformation>(); | |
| 84 | |
| 85 /// List of [TypeInformation]s allocated inside method bodies (calls, | |
| 86 /// narrowing, phis, and containers). | |
| 87 final List<TypeInformation> allocatedTypes = <TypeInformation>[]; | |
| 88 | |
| 89 TypeInformationSystem(Compiler compiler) | |
| 90 : this.compiler = compiler, | |
| 91 this.classWorld = compiler.world { | |
| 92 nonNullEmptyType = getConcreteTypeFor(const TypeMask.nonNullEmpty()); | |
| 93 } | |
| 94 | |
| 95 /// Used to group [TypeInformation] nodes by the element that triggered their | |
| 96 /// creation. | |
| 97 MemberTypeInformation _currentMember = null; | |
| 98 MemberTypeInformation get currentMember => _currentMember; | |
| 99 | |
| 100 void withMember(MemberElement element, action) { | |
| 101 assert(invariant(element, _currentMember == null, | |
| 102 message: "Already constructing graph for $_currentMember.")); | |
| 103 _currentMember = getInferredTypeOf(element); | |
| 104 action(); | |
| 105 _currentMember = null; | |
| 106 } | |
| 107 | |
| 108 TypeInformation nullTypeCache; | |
| 109 TypeInformation get nullType { | |
| 110 if (nullTypeCache != null) return nullTypeCache; | |
| 111 return nullTypeCache = getConcreteTypeFor(compiler.typesTask.nullType); | |
| 112 } | |
| 113 | |
| 114 TypeInformation intTypeCache; | |
| 115 TypeInformation get intType { | |
| 116 if (intTypeCache != null) return intTypeCache; | |
| 117 return intTypeCache = getConcreteTypeFor(compiler.typesTask.intType); | |
| 118 } | |
| 119 | |
| 120 TypeInformation uint32TypeCache; | |
| 121 TypeInformation get uint32Type { | |
| 122 if (uint32TypeCache != null) return uint32TypeCache; | |
| 123 return uint32TypeCache = getConcreteTypeFor(compiler.typesTask.uint32Type); | |
| 124 } | |
| 125 | |
| 126 TypeInformation uint31TypeCache; | |
| 127 TypeInformation get uint31Type { | |
| 128 if (uint31TypeCache != null) return uint31TypeCache; | |
| 129 return uint31TypeCache = getConcreteTypeFor(compiler.typesTask.uint31Type); | |
| 130 } | |
| 131 | |
| 132 TypeInformation positiveIntTypeCache; | |
| 133 TypeInformation get positiveIntType { | |
| 134 if (positiveIntTypeCache != null) return positiveIntTypeCache; | |
| 135 return positiveIntTypeCache = | |
| 136 getConcreteTypeFor(compiler.typesTask.positiveIntType); | |
| 137 } | |
| 138 | |
| 139 TypeInformation doubleTypeCache; | |
| 140 TypeInformation get doubleType { | |
| 141 if (doubleTypeCache != null) return doubleTypeCache; | |
| 142 return doubleTypeCache = getConcreteTypeFor(compiler.typesTask.doubleType); | |
| 143 } | |
| 144 | |
| 145 TypeInformation numTypeCache; | |
| 146 TypeInformation get numType { | |
| 147 if (numTypeCache != null) return numTypeCache; | |
| 148 return numTypeCache = getConcreteTypeFor(compiler.typesTask.numType); | |
| 149 } | |
| 150 | |
| 151 TypeInformation boolTypeCache; | |
| 152 TypeInformation get boolType { | |
| 153 if (boolTypeCache != null) return boolTypeCache; | |
| 154 return boolTypeCache = getConcreteTypeFor(compiler.typesTask.boolType); | |
| 155 } | |
| 156 | |
| 157 TypeInformation functionTypeCache; | |
| 158 TypeInformation get functionType { | |
| 159 if (functionTypeCache != null) return functionTypeCache; | |
| 160 return functionTypeCache = | |
| 161 getConcreteTypeFor(compiler.typesTask.functionType); | |
| 162 } | |
| 163 | |
| 164 TypeInformation listTypeCache; | |
| 165 TypeInformation get listType { | |
| 166 if (listTypeCache != null) return listTypeCache; | |
| 167 return listTypeCache = getConcreteTypeFor(compiler.typesTask.listType); | |
| 168 } | |
| 169 | |
| 170 TypeInformation constListTypeCache; | |
| 171 TypeInformation get constListType { | |
| 172 if (constListTypeCache != null) return constListTypeCache; | |
| 173 return constListTypeCache = | |
| 174 getConcreteTypeFor(compiler.typesTask.constListType); | |
| 175 } | |
| 176 | |
| 177 TypeInformation fixedListTypeCache; | |
| 178 TypeInformation get fixedListType { | |
| 179 if (fixedListTypeCache != null) return fixedListTypeCache; | |
| 180 return fixedListTypeCache = | |
| 181 getConcreteTypeFor(compiler.typesTask.fixedListType); | |
| 182 } | |
| 183 | |
| 184 TypeInformation growableListTypeCache; | |
| 185 TypeInformation get growableListType { | |
| 186 if (growableListTypeCache != null) return growableListTypeCache; | |
| 187 return growableListTypeCache = | |
| 188 getConcreteTypeFor(compiler.typesTask.growableListType); | |
| 189 } | |
| 190 | |
| 191 TypeInformation mapTypeCache; | |
| 192 TypeInformation get mapType { | |
| 193 if (mapTypeCache != null) return mapTypeCache; | |
| 194 return mapTypeCache = getConcreteTypeFor(compiler.typesTask.mapType); | |
| 195 } | |
| 196 | |
| 197 TypeInformation constMapTypeCache; | |
| 198 TypeInformation get constMapType { | |
| 199 if (constMapTypeCache != null) return constMapTypeCache; | |
| 200 return constMapTypeCache = | |
| 201 getConcreteTypeFor(compiler.typesTask.constMapType); | |
| 202 } | |
| 203 | |
| 204 TypeInformation stringTypeCache; | |
| 205 TypeInformation get stringType { | |
| 206 if (stringTypeCache != null) return stringTypeCache; | |
| 207 return stringTypeCache = getConcreteTypeFor(compiler.typesTask.stringType); | |
| 208 } | |
| 209 | |
| 210 TypeInformation typeTypeCache; | |
| 211 TypeInformation get typeType { | |
| 212 if (typeTypeCache != null) return typeTypeCache; | |
| 213 return typeTypeCache = getConcreteTypeFor(compiler.typesTask.typeType); | |
| 214 } | |
| 215 | |
| 216 TypeInformation dynamicTypeCache; | |
| 217 TypeInformation get dynamicType { | |
| 218 if (dynamicTypeCache != null) return dynamicTypeCache; | |
| 219 return dynamicTypeCache = | |
| 220 getConcreteTypeFor(compiler.typesTask.dynamicType); | |
| 221 } | |
| 222 | |
| 223 TypeInformation nonNullEmptyType; | |
| 224 | |
| 225 TypeInformation stringLiteralType(ast.DartString value) { | |
| 226 return new StringLiteralTypeInformation( | |
| 227 value, compiler.typesTask.stringType); | |
| 228 } | |
| 229 | |
| 230 TypeInformation computeLUB(TypeInformation firstType, | |
| 231 TypeInformation secondType) { | |
| 232 if (firstType == null) return secondType; | |
| 233 if (firstType == secondType) return firstType; | |
| 234 if (firstType == nonNullEmptyType) return secondType; | |
| 235 if (secondType == nonNullEmptyType) return firstType; | |
| 236 if (firstType == dynamicType || secondType == dynamicType) { | |
| 237 return dynamicType; | |
| 238 } | |
| 239 return getConcreteTypeFor( | |
| 240 firstType.type.union(secondType.type, classWorld)); | |
| 241 } | |
| 242 | |
| 243 bool selectorNeedsUpdate(TypeInformation info, Selector selector) | |
| 244 { | |
| 245 return info.type != selector.mask; | |
| 246 } | |
| 247 | |
| 248 TypeInformation refineReceiver(Selector selector, TypeInformation receiver) { | |
| 249 if (receiver.type.isExact) return receiver; | |
| 250 TypeMask otherType = compiler.world.allFunctions.receiverType(selector); | |
| 251 // If this is refining to nullable subtype of `Object` just return | |
| 252 // the receiver. We know the narrowing is useless. | |
| 253 if (otherType.isNullable && otherType.containsAll(classWorld)) { | |
| 254 return receiver; | |
| 255 } | |
| 256 assert(TypeMask.assertIsNormalized(otherType, classWorld)); | |
| 257 TypeInformation newType = new NarrowTypeInformation(receiver, otherType); | |
| 258 allocatedTypes.add(newType); | |
| 259 return newType; | |
| 260 } | |
| 261 | |
| 262 TypeInformation narrowType(TypeInformation type, | |
| 263 DartType annotation, | |
| 264 {bool isNullable: true}) { | |
| 265 if (annotation.treatAsDynamic) return type; | |
| 266 if (annotation.isVoid) return nullType; | |
| 267 if (annotation.element == classWorld.objectClass && isNullable) return type; | |
| 268 TypeMask otherType; | |
| 269 if (annotation.isTypedef || annotation.isFunctionType) { | |
| 270 otherType = functionType.type; | |
| 271 } else if (annotation.isTypeVariable) { | |
| 272 // TODO(ngeoffray): Narrow to bound. | |
| 273 return type; | |
| 274 } else { | |
| 275 assert(annotation.isInterfaceType); | |
| 276 otherType = annotation.element == classWorld.objectClass | |
| 277 ? dynamicType.type.nonNullable() | |
| 278 : new TypeMask.nonNullSubtype(annotation.element, classWorld); | |
| 279 } | |
| 280 if (isNullable) otherType = otherType.nullable(); | |
| 281 if (type.type.isExact) { | |
| 282 return type; | |
| 283 } else { | |
| 284 assert(TypeMask.assertIsNormalized(otherType, classWorld)); | |
| 285 TypeInformation newType = new NarrowTypeInformation(type, otherType); | |
| 286 allocatedTypes.add(newType); | |
| 287 return newType; | |
| 288 } | |
| 289 } | |
| 290 | |
| 291 ElementTypeInformation getInferredTypeOf(Element element) { | |
| 292 element = element.implementation; | |
| 293 return typeInformations.putIfAbsent(element, () { | |
| 294 return new ElementTypeInformation(element, this); | |
| 295 }); | |
| 296 } | |
| 297 | |
| 298 ConcreteTypeInformation getConcreteTypeFor(TypeMask mask) { | |
| 299 assert(mask != null); | |
| 300 return concreteTypes.putIfAbsent(mask, () { | |
| 301 return new ConcreteTypeInformation(mask); | |
| 302 }); | |
| 303 } | |
| 304 | |
| 305 String getInferredSignatureOf(FunctionElement function) { | |
| 306 ElementTypeInformation info = getInferredTypeOf(function); | |
| 307 FunctionElement impl = function.implementation; | |
| 308 FunctionSignature signature = impl.functionSignature; | |
| 309 var res = ""; | |
| 310 signature.forEachParameter((Element parameter) { | |
| 311 TypeInformation type = getInferredTypeOf(parameter); | |
| 312 res += "${res.isEmpty ? '(' : ', '}${type.type} ${parameter.name}"; | |
| 313 }); | |
| 314 res += ") -> ${info.type}"; | |
| 315 return res; | |
| 316 } | |
| 317 | |
| 318 TypeInformation nonNullSubtype(ClassElement type) { | |
| 319 return getConcreteTypeFor( | |
| 320 new TypeMask.nonNullSubtype(type.declaration, classWorld)); | |
| 321 } | |
| 322 | |
| 323 TypeInformation nonNullSubclass(ClassElement type) { | |
| 324 return getConcreteTypeFor( | |
| 325 new TypeMask.nonNullSubclass(type.declaration, classWorld)); | |
| 326 } | |
| 327 | |
| 328 TypeInformation nonNullExact(ClassElement type) { | |
| 329 return getConcreteTypeFor( | |
| 330 new TypeMask.nonNullExact(type.declaration, classWorld)); | |
| 331 } | |
| 332 | |
| 333 TypeInformation nonNullEmpty() { | |
| 334 return nonNullEmptyType; | |
| 335 } | |
| 336 | |
| 337 bool isNull(TypeInformation type) { | |
| 338 return type == nullType; | |
| 339 } | |
| 340 | |
| 341 TypeInformation allocateList(TypeInformation type, | |
| 342 ast.Node node, | |
| 343 Element enclosing, | |
| 344 [TypeInformation elementType, int length]) { | |
| 345 bool isTypedArray = | |
| 346 compiler.typedDataClass != null && | |
| 347 classWorld.isInstantiated(compiler.typedDataClass) && | |
| 348 type.type.satisfies(compiler.typedDataClass, classWorld); | |
| 349 bool isConst = (type.type == compiler.typesTask.constListType); | |
| 350 bool isFixed = (type.type == compiler.typesTask.fixedListType) || | |
| 351 isConst || | |
| 352 isTypedArray; | |
| 353 bool isElementInferred = isConst || isTypedArray; | |
| 354 | |
| 355 int inferredLength = isFixed ? length : null; | |
| 356 TypeMask elementTypeMask = isElementInferred | |
| 357 ? elementType.type | |
| 358 : dynamicType.type; | |
| 359 ContainerTypeMask mask = new ContainerTypeMask( | |
| 360 type.type, node, enclosing, elementTypeMask, inferredLength); | |
| 361 ElementInContainerTypeInformation element = | |
| 362 new ElementInContainerTypeInformation(currentMember, elementType); | |
| 363 element.inferred = isElementInferred; | |
| 364 | |
| 365 allocatedTypes.add(element); | |
| 366 return allocatedLists[node] = | |
| 367 new ListTypeInformation(currentMember, mask, element, length); | |
| 368 } | |
| 369 | |
| 370 TypeInformation allocateClosure(ast.Node node, Element element) { | |
| 371 TypeInformation result = | |
| 372 new ClosureTypeInformation(currentMember, node, element); | |
| 373 allocatedClosures.add(result); | |
| 374 return result; | |
| 375 } | |
| 376 | |
| 377 TypeInformation allocateMap(ConcreteTypeInformation type, | |
| 378 ast.Node node, | |
| 379 Element element, | |
| 380 [List<TypeInformation> keyTypes, | |
| 381 List<TypeInformation> valueTypes]) { | |
| 382 assert(keyTypes.length == valueTypes.length); | |
| 383 bool isFixed = (type.type == compiler.typesTask.constMapType); | |
| 384 | |
| 385 TypeMask keyType, valueType; | |
| 386 if (isFixed) { | |
| 387 keyType = keyTypes.fold(nonNullEmptyType.type, | |
| 388 (type, info) => type.union(info.type, classWorld)); | |
| 389 valueType = valueTypes.fold(nonNullEmptyType.type, | |
| 390 (type, info) => type.union(info.type, classWorld)); | |
| 391 } else { | |
| 392 keyType = valueType = dynamicType.type; | |
| 393 } | |
| 394 MapTypeMask mask = new MapTypeMask(type.type, | |
| 395 node, | |
| 396 element, | |
| 397 keyType, | |
| 398 valueType); | |
| 399 | |
| 400 TypeInformation keyTypeInfo = | |
| 401 new KeyInMapTypeInformation(currentMember, null); | |
| 402 TypeInformation valueTypeInfo = | |
| 403 new ValueInMapTypeInformation(currentMember, null); | |
| 404 allocatedTypes.add(keyTypeInfo); | |
| 405 allocatedTypes.add(valueTypeInfo); | |
| 406 | |
| 407 MapTypeInformation map = | |
| 408 new MapTypeInformation(currentMember, mask, keyTypeInfo, valueTypeInfo); | |
| 409 | |
| 410 for (int i = 0; i < keyTypes.length; ++i) { | |
| 411 TypeInformation newType = | |
| 412 map.addEntryAssignment(keyTypes[i], valueTypes[i], true); | |
| 413 if (newType != null) allocatedTypes.add(newType); | |
| 414 } | |
| 415 | |
| 416 // Shortcut: If we already have a first approximation of the key/value type, | |
| 417 // start propagating it early. | |
| 418 if (isFixed) map.markAsInferred(); | |
| 419 | |
| 420 allocatedMaps[node] = map; | |
| 421 return map; | |
| 422 } | |
| 423 | |
| 424 Selector newTypedSelector(TypeInformation info, Selector selector) { | |
| 425 // Only type the selector if [info] is concrete, because the other | |
| 426 // kinds of [TypeInformation] have the empty type at this point of | |
| 427 // analysis. | |
| 428 return info.isConcrete | |
| 429 ? new TypedSelector(info.type, selector, classWorld) | |
| 430 : selector; | |
| 431 } | |
| 432 | |
| 433 TypeInformation allocateDiamondPhi(TypeInformation firstInput, | |
| 434 TypeInformation secondInput) { | |
| 435 PhiElementTypeInformation result = | |
| 436 new PhiElementTypeInformation(currentMember, null, false, null); | |
| 437 result.addAssignment(firstInput); | |
| 438 result.addAssignment(secondInput); | |
| 439 allocatedTypes.add(result); | |
| 440 return result; | |
| 441 } | |
| 442 | |
| 443 PhiElementTypeInformation _addPhi(ast.Node node, | |
| 444 Local variable, | |
| 445 inputType, | |
| 446 bool isLoop) { | |
| 447 PhiElementTypeInformation result = | |
| 448 new PhiElementTypeInformation(currentMember, node, isLoop, variable); | |
| 449 allocatedTypes.add(result); | |
| 450 result.addAssignment(inputType); | |
| 451 return result; | |
| 452 } | |
| 453 | |
| 454 PhiElementTypeInformation allocatePhi(ast.Node node, | |
| 455 Local variable, | |
| 456 inputType) { | |
| 457 // Check if [inputType] is a phi for a local updated in | |
| 458 // the try/catch block [node]. If it is, no need to allocate a new | |
| 459 // phi. | |
| 460 if (inputType is PhiElementTypeInformation && | |
| 461 inputType.branchNode == node && | |
| 462 inputType.branchNode is ast.TryStatement) { | |
| 463 return inputType; | |
| 464 } | |
| 465 return _addPhi(node, variable, inputType, false); | |
| 466 } | |
| 467 | |
| 468 PhiElementTypeInformation allocateLoopPhi(ast.Node node, | |
| 469 Local variable, | |
| 470 inputType) { | |
| 471 return _addPhi(node, variable, inputType, true); | |
| 472 } | |
| 473 | |
| 474 TypeInformation simplifyPhi(ast.Node node, | |
| 475 Local variable, | |
| 476 PhiElementTypeInformation phiType) { | |
| 477 assert(phiType.branchNode == node); | |
| 478 if (phiType.assignments.length == 1) return phiType.assignments.first; | |
| 479 return phiType; | |
| 480 } | |
| 481 | |
| 482 PhiElementTypeInformation addPhiInput(Local variable, | |
| 483 PhiElementTypeInformation phiType, | |
| 484 TypeInformation newType) { | |
| 485 phiType.addAssignment(newType); | |
| 486 return phiType; | |
| 487 } | |
| 488 | |
| 489 TypeMask computeTypeMask(Iterable<TypeInformation> assignments) { | |
| 490 return joinTypeMasks(assignments.map((e) => e.type)); | |
| 491 } | |
| 492 | |
| 493 TypeMask joinTypeMasks(Iterable<TypeMask> masks) { | |
| 494 TypeMask newType = const TypeMask.nonNullEmpty(); | |
| 495 for (TypeMask mask in masks) { | |
| 496 newType = newType.union(mask, classWorld); | |
| 497 } | |
| 498 return newType.containsAll(classWorld) ? dynamicType.type : newType; | |
| 499 } | |
| 500 } | |
| 501 | |
| 502 /** | |
| 503 * A work queue for the inferrer. It filters out nodes that are tagged as | |
| 504 * [TypeInformation.doNotEnqueue], as well as ensures through | |
| 505 * [TypeInformation.inQueue] that a node is in the queue only once at | |
| 506 * a time. | |
| 507 */ | |
| 508 class WorkQueue { | |
| 509 final Queue<TypeInformation> queue = new Queue<TypeInformation>(); | |
| 510 | |
| 511 void add(TypeInformation element) { | |
| 512 if (element.doNotEnqueue) return; | |
| 513 if (element.inQueue) return; | |
| 514 queue.addLast(element); | |
| 515 element.inQueue = true; | |
| 516 } | |
| 517 | |
| 518 void addAll(Iterable<TypeInformation> all) { | |
| 519 all.forEach(add); | |
| 520 } | |
| 521 | |
| 522 TypeInformation remove() { | |
| 523 TypeInformation element = queue.removeFirst(); | |
| 524 element.inQueue = false; | |
| 525 return element; | |
| 526 } | |
| 527 | |
| 528 bool get isEmpty => queue.isEmpty; | |
| 529 | |
| 530 int get length => queue.length; | |
| 531 } | |
| 532 | |
| 533 /** | |
| 534 * An inferencing engine that computes a call graph of | |
| 535 * [TypeInformation] nodes by visiting the AST of the application, and | |
| 536 * then does the inferencing on the graph. | |
| 537 * | |
| 538 */ | |
| 539 class TypeGraphInferrerEngine | |
| 540 extends InferrerEngine<TypeInformation, TypeInformationSystem> { | |
| 541 final Map<Element, TypeInformation> defaultTypeOfParameter = | |
| 542 new Map<Element, TypeInformation>(); | |
| 543 final List<CallSiteTypeInformation> allocatedCalls = | |
| 544 <CallSiteTypeInformation>[]; | |
| 545 final WorkQueue workQueue = new WorkQueue(); | |
| 546 final Element mainElement; | |
| 547 final Set<Element> analyzedElements = new Set<Element>(); | |
| 548 | |
| 549 /// The maximum number of times we allow a node in the graph to | |
| 550 /// change types. If a node reaches that limit, we give up | |
| 551 /// inferencing on it and give it the dynamic type. | |
| 552 final int MAX_CHANGE_COUNT = 6; | |
| 553 | |
| 554 int overallRefineCount = 0; | |
| 555 int addedInGraph = 0; | |
| 556 | |
| 557 TypeGraphInferrerEngine(Compiler compiler, this.mainElement) | |
| 558 : super(compiler, new TypeInformationSystem(compiler)); | |
| 559 | |
| 560 /** | |
| 561 * A set of selector names that [List] implements, that we know return | |
| 562 * their element type. | |
| 563 */ | |
| 564 final Set<Selector> _returnsListElementTypeSet = new Set<Selector>.from( | |
| 565 <Selector>[ | |
| 566 new Selector.getter('first', null), | |
| 567 new Selector.getter('last', null), | |
| 568 new Selector.getter('single', null), | |
| 569 new Selector.call('singleWhere', null, 1), | |
| 570 new Selector.call('elementAt', null, 1), | |
| 571 new Selector.index(), | |
| 572 new Selector.call('removeAt', null, 1), | |
| 573 new Selector.call('removeLast', null, 0) | |
| 574 ]); | |
| 575 | |
| 576 bool returnsListElementType(Selector selector) { | |
| 577 return (selector.mask != null) && | |
| 578 selector.mask.isContainer && | |
| 579 _returnsListElementTypeSet.contains(selector.asUntyped); | |
| 580 } | |
| 581 | |
| 582 bool returnsMapValueType(Selector selector) { | |
| 583 return (selector.mask != null) && | |
| 584 selector.mask.isMap && | |
| 585 selector.isIndex; | |
| 586 } | |
| 587 | |
| 588 void analyzeListAndEnqueue(ListTypeInformation info) { | |
| 589 if (info.analyzed) return; | |
| 590 info.analyzed = true; | |
| 591 | |
| 592 ListTracerVisitor tracer = new ListTracerVisitor(info, this); | |
| 593 bool succeeded = tracer.run(); | |
| 594 if (!succeeded) return; | |
| 595 | |
| 596 info.bailedOut = false; | |
| 597 info.elementType.inferred = true; | |
| 598 TypeMask fixedListType = compiler.typesTask.fixedListType; | |
| 599 if (info.originalType.forwardTo == fixedListType) { | |
| 600 info.checksGrowable = tracer.callsGrowableMethod; | |
| 601 } | |
| 602 tracer.assignments.forEach(info.elementType.addAssignment); | |
| 603 // Enqueue the list for later refinement | |
| 604 workQueue.add(info); | |
| 605 workQueue.add(info.elementType); | |
| 606 } | |
| 607 | |
| 608 void analyzeMapAndEnqueue(MapTypeInformation info) { | |
| 609 if (info.analyzed) return; | |
| 610 info.analyzed = true; | |
| 611 MapTracerVisitor tracer = new MapTracerVisitor(info, this); | |
| 612 | |
| 613 bool succeeded = tracer.run(); | |
| 614 if (!succeeded) return; | |
| 615 | |
| 616 info.bailedOut = false; | |
| 617 for (int i = 0; i < tracer.keyAssignments.length; ++i) { | |
| 618 TypeInformation newType = info.addEntryAssignment( | |
| 619 tracer.keyAssignments[i], tracer.valueAssignments[i]); | |
| 620 if (newType != null) workQueue.add(newType); | |
| 621 } | |
| 622 for (TypeInformation map in tracer.mapAssignments) { | |
| 623 workQueue.addAll(info.addMapAssignment(map)); | |
| 624 } | |
| 625 | |
| 626 info.markAsInferred(); | |
| 627 workQueue.add(info.keyType); | |
| 628 workQueue.add(info.valueType); | |
| 629 workQueue.addAll(info.typeInfoMap.values); | |
| 630 workQueue.add(info); | |
| 631 } | |
| 632 | |
| 633 void runOverAllElements() { | |
| 634 if (compiler.disableTypeInference) return; | |
| 635 if (compiler.verbose) { | |
| 636 compiler.progress.reset(); | |
| 637 } | |
| 638 sortResolvedElements().forEach((Element element) { | |
| 639 if (compiler.shouldPrintProgress) { | |
| 640 compiler.log('Added $addedInGraph elements in inferencing graph.'); | |
| 641 compiler.progress.reset(); | |
| 642 } | |
| 643 // This also forces the creation of the [ElementTypeInformation] to ensure | |
| 644 // it is in the graph. | |
| 645 types.withMember(element, () => analyze(element, null)); | |
| 646 }); | |
| 647 compiler.log('Added $addedInGraph elements in inferencing graph.'); | |
| 648 | |
| 649 buildWorkQueue(); | |
| 650 refine(); | |
| 651 | |
| 652 // Try to infer element types of lists and compute their escape information. | |
| 653 types.allocatedLists.values.forEach((ListTypeInformation info) { | |
| 654 analyzeListAndEnqueue(info); | |
| 655 }); | |
| 656 | |
| 657 // Try to infer the key and value types for maps and compute the values' | |
| 658 // escape information. | |
| 659 types.allocatedMaps.values.forEach((MapTypeInformation info) { | |
| 660 analyzeMapAndEnqueue(info); | |
| 661 }); | |
| 662 | |
| 663 Set<FunctionElement> bailedOutOn = new Set<FunctionElement>(); | |
| 664 | |
| 665 // Trace closures to potentially infer argument types. | |
| 666 types.allocatedClosures.forEach((info) { | |
| 667 void trace(Iterable<FunctionElement> elements, | |
| 668 ClosureTracerVisitor tracer) { | |
| 669 tracer.run(); | |
| 670 if (!tracer.continueAnalyzing) { | |
| 671 elements.forEach((FunctionElement e) { | |
| 672 compiler.world.registerMightBePassedToApply(e); | |
| 673 if (_VERBOSE) print("traced closure $e as ${true} (bail)"); | |
| 674 e.functionSignature.forEachParameter((parameter) { | |
| 675 types.getInferredTypeOf(parameter).giveUp( | |
| 676 this, | |
| 677 clearAssignments: false); | |
| 678 }); | |
| 679 }); | |
| 680 bailedOutOn.addAll(elements); | |
| 681 return; | |
| 682 } | |
| 683 elements | |
| 684 .where((e) => !bailedOutOn.contains(e)) | |
| 685 .forEach((FunctionElement e) { | |
| 686 e.functionSignature.forEachParameter((parameter) { | |
| 687 var info = types.getInferredTypeOf(parameter); | |
| 688 info.maybeResume(); | |
| 689 workQueue.add(info); | |
| 690 }); | |
| 691 if (tracer.tracedType.mightBePassedToFunctionApply) { | |
| 692 compiler.world.registerMightBePassedToApply(e); | |
| 693 }; | |
| 694 if (_VERBOSE) { | |
| 695 print("traced closure $e as " | |
| 696 "${compiler.world.getMightBePassedToApply(e)}"); | |
| 697 } | |
| 698 }); | |
| 699 } | |
| 700 if (info is ClosureTypeInformation) { | |
| 701 Iterable<FunctionElement> elements = [info.element]; | |
| 702 trace(elements, new ClosureTracerVisitor(elements, info, this)); | |
| 703 } else if (info is CallSiteTypeInformation) { | |
| 704 // We only are interested in functions here, as other targets | |
| 705 // of this closure call are not a root to trace but an intermediate | |
| 706 // for some other function. | |
| 707 Iterable<FunctionElement> elements = info.callees | |
| 708 .where((e) => e.isFunction); | |
| 709 trace(elements, new ClosureTracerVisitor(elements, info, this)); | |
| 710 } else { | |
| 711 assert(info is ElementTypeInformation); | |
| 712 trace([info.element], | |
| 713 new StaticTearOffClosureTracerVisitor(info.element, info, this)); | |
| 714 } | |
| 715 }); | |
| 716 | |
| 717 // Reset all nodes that use lists/maps that have been inferred, as well | |
| 718 // as nodes that use elements fetched from these lists/maps. The | |
| 719 // workset for a new run of the analysis will be these nodes. | |
| 720 Set<TypeInformation> seenTypes = new Set<TypeInformation>(); | |
| 721 while (!workQueue.isEmpty) { | |
| 722 TypeInformation info = workQueue.remove(); | |
| 723 if (seenTypes.contains(info)) continue; | |
| 724 // If the node cannot be reset, we do not need to update its users either. | |
| 725 if (!info.reset(this)) continue; | |
| 726 seenTypes.add(info); | |
| 727 workQueue.addAll(info.users); | |
| 728 } | |
| 729 | |
| 730 workQueue.addAll(seenTypes); | |
| 731 refine(); | |
| 732 | |
| 733 if (_PRINT_SUMMARY) { | |
| 734 types.allocatedLists.values.forEach((ListTypeInformation info) { | |
| 735 print('${info.type} ' | |
| 736 'for ${info.originalType.allocationNode} ' | |
| 737 'at ${info.originalType.allocationElement} ' | |
| 738 'after ${info.refineCount}'); | |
| 739 }); | |
| 740 types.allocatedMaps.values.forEach((MapTypeInformation info) { | |
| 741 print('${info.type} ' | |
| 742 'for ${info.originalType.allocationNode} ' | |
| 743 'at ${info.originalType.allocationElement} ' | |
| 744 'after ${info.refineCount}'); | |
| 745 }); | |
| 746 types.allocatedClosures.forEach((TypeInformation info) { | |
| 747 if (info is ElementTypeInformation) { | |
| 748 print('${types.getInferredSignatureOf(info.element)} for ' | |
| 749 '${info.element}'); | |
| 750 } else if (info is ClosureTypeInformation) { | |
| 751 print('${types.getInferredSignatureOf(info.element)} for ' | |
| 752 '${info.element}'); | |
| 753 } else if (info is DynamicCallSiteTypeInformation) { | |
| 754 for (Element target in info.targets) { | |
| 755 if (target is FunctionElement) { | |
| 756 print('${types.getInferredSignatureOf(target)} for ${target}'); | |
| 757 } else { | |
| 758 print('${types.getInferredTypeOf(target).type} for ${target}'); | |
| 759 } | |
| 760 } | |
| 761 } else { | |
| 762 print('${info.type} for some unknown kind of closure'); | |
| 763 } | |
| 764 }); | |
| 765 analyzedElements.forEach((Element elem) { | |
| 766 TypeInformation type = types.getInferredTypeOf(elem); | |
| 767 print('${elem} :: ${type} from ${type.assignments} '); | |
| 768 }); | |
| 769 } | |
| 770 | |
| 771 compiler.log('Inferred $overallRefineCount types.'); | |
| 772 | |
| 773 processLoopInformation(); | |
| 774 } | |
| 775 | |
| 776 void analyze(Element element, ArgumentsTypes arguments) { | |
| 777 element = element.implementation; | |
| 778 if (analyzedElements.contains(element)) return; | |
| 779 analyzedElements.add(element); | |
| 780 | |
| 781 SimpleTypeInferrerVisitor visitor = | |
| 782 new SimpleTypeInferrerVisitor(element, compiler, this); | |
| 783 TypeInformation type; | |
| 784 compiler.withCurrentElement(element, () { | |
| 785 type = visitor.run(); | |
| 786 }); | |
| 787 addedInGraph++; | |
| 788 | |
| 789 if (element.isField) { | |
| 790 VariableElement fieldElement = element; | |
| 791 ast.Node node = fieldElement.node; | |
| 792 if (element.isFinal || element.isConst) { | |
| 793 // If [element] is final and has an initializer, we record | |
| 794 // the inferred type. | |
| 795 if (fieldElement.initializer != null) { | |
| 796 if (type is! ListTypeInformation && type is! MapTypeInformation) { | |
| 797 // For non-container types, the constant handler does | |
| 798 // constant folding that could give more precise results. | |
| 799 ConstantExpression constant = compiler.backend.constants | |
| 800 .getConstantForVariable(element); | |
| 801 if (constant != null) { | |
| 802 ConstantValue value = constant.value; | |
| 803 if (value.isFunction) { | |
| 804 FunctionConstantValue functionConstant = value; | |
| 805 type = types.allocateClosure(node, functionConstant.element); | |
| 806 } else { | |
| 807 // Although we might find a better type, we have to keep | |
| 808 // the old type around to ensure that we get a complete view | |
| 809 // of the type graph and do not drop any flow edges. | |
| 810 TypeMask refinedType = value.computeMask(compiler); | |
| 811 assert(TypeMask.assertIsNormalized(refinedType, classWorld)); | |
| 812 type = new NarrowTypeInformation(type, refinedType); | |
| 813 types.allocatedTypes.add(type); | |
| 814 } | |
| 815 } | |
| 816 } | |
| 817 recordType(element, type); | |
| 818 } else if (!element.isInstanceMember) { | |
| 819 recordType(element, types.nullType); | |
| 820 } | |
| 821 } else if (fieldElement.initializer == null) { | |
| 822 // Only update types of static fields if there is no | |
| 823 // assignment. Instance fields are dealt with in the constructor. | |
| 824 if (Elements.isStaticOrTopLevelField(element)) { | |
| 825 recordTypeOfNonFinalField(node, element, type); | |
| 826 } | |
| 827 } else { | |
| 828 recordTypeOfNonFinalField(node, element, type); | |
| 829 } | |
| 830 if (Elements.isStaticOrTopLevelField(element) && | |
| 831 fieldElement.initializer != null && | |
| 832 !element.isConst) { | |
| 833 var argument = fieldElement.initializer; | |
| 834 // TODO(13429): We could do better here by using the | |
| 835 // constant handler to figure out if it's a lazy field or not. | |
| 836 if (argument.asSend() != null || | |
| 837 (argument.asNewExpression() != null && !argument.isConst)) { | |
| 838 recordType(element, types.nullType); | |
| 839 } | |
| 840 } | |
| 841 } else { | |
| 842 recordReturnType(element, type); | |
| 843 } | |
| 844 } | |
| 845 | |
| 846 void processLoopInformation() { | |
| 847 allocatedCalls.forEach((info) { | |
| 848 if (!info.inLoop) return; | |
| 849 if (info is StaticCallSiteTypeInformation) { | |
| 850 compiler.world.addFunctionCalledInLoop(info.calledElement); | |
| 851 } else if (info.selector.mask != null && | |
| 852 !info.selector.mask.containsAll(compiler.world)) { | |
| 853 // For instance methods, we only register a selector called in a | |
| 854 // loop if it is a typed selector, to avoid marking too many | |
| 855 // methods as being called from within a loop. This cuts down | |
| 856 // on the code bloat. | |
| 857 info.targets.forEach(compiler.world.addFunctionCalledInLoop); | |
| 858 } | |
| 859 }); | |
| 860 } | |
| 861 | |
| 862 void refine() { | |
| 863 while (!workQueue.isEmpty) { | |
| 864 if (compiler.shouldPrintProgress) { | |
| 865 compiler.log('Inferred $overallRefineCount types.'); | |
| 866 compiler.progress.reset(); | |
| 867 } | |
| 868 TypeInformation info = workQueue.remove(); | |
| 869 TypeMask oldType = info.type; | |
| 870 TypeMask newType = info.refine(this); | |
| 871 // Check that refinement has not accidentially changed the type. | |
| 872 assert(oldType == info.type); | |
| 873 if (info.abandonInferencing) info.doNotEnqueue = true; | |
| 874 if ((info.type = newType) != oldType) { | |
| 875 overallRefineCount++; | |
| 876 info.refineCount++; | |
| 877 if (info.refineCount > MAX_CHANGE_COUNT) { | |
| 878 if (_ANOMALY_WARN) { | |
| 879 print("ANOMALY WARNING: max refinement reached for $info"); | |
| 880 } | |
| 881 info.giveUp(this); | |
| 882 info.type = info.refine(this); | |
| 883 info.doNotEnqueue = true; | |
| 884 } | |
| 885 workQueue.addAll(info.users); | |
| 886 if (info.hasStableType(this)) { | |
| 887 info.stabilize(this); | |
| 888 } | |
| 889 } | |
| 890 } | |
| 891 } | |
| 892 | |
| 893 void buildWorkQueue() { | |
| 894 workQueue.addAll(types.typeInformations.values); | |
| 895 workQueue.addAll(types.allocatedTypes); | |
| 896 workQueue.addAll(types.allocatedClosures); | |
| 897 workQueue.addAll(allocatedCalls); | |
| 898 } | |
| 899 | |
| 900 /** | |
| 901 * Update the assignments to parameters in the graph. [remove] tells | |
| 902 * wheter assignments must be added or removed. If [init] is false, | |
| 903 * parameters are added to the work queue. | |
| 904 */ | |
| 905 void updateParameterAssignments(TypeInformation caller, | |
| 906 Element callee, | |
| 907 ArgumentsTypes arguments, | |
| 908 Selector selector, | |
| 909 {bool remove, bool addToQueue: true}) { | |
| 910 if (callee.name == Compiler.NO_SUCH_METHOD) return; | |
| 911 if (callee.isField) { | |
| 912 if (selector.isSetter) { | |
| 913 ElementTypeInformation info = types.getInferredTypeOf(callee); | |
| 914 if (remove) { | |
| 915 info.removeAssignment(arguments.positional[0]); | |
| 916 } else { | |
| 917 info.addAssignment(arguments.positional[0]); | |
| 918 } | |
| 919 if (addToQueue) workQueue.add(info); | |
| 920 } | |
| 921 } else if (callee.isGetter) { | |
| 922 return; | |
| 923 } else if (selector != null && selector.isGetter) { | |
| 924 // We are tearing a function off and thus create a closure. | |
| 925 assert(callee.isFunction); | |
| 926 MemberTypeInformation info = types.getInferredTypeOf(callee); | |
| 927 if (remove) { | |
| 928 info.closurizedCount--; | |
| 929 } else { | |
| 930 info.closurizedCount++; | |
| 931 if (Elements.isStaticOrTopLevel(callee)) { | |
| 932 types.allocatedClosures.add(info); | |
| 933 } else { | |
| 934 // We add the call-site type information here so that we | |
| 935 // can benefit from further refinement of the selector. | |
| 936 types.allocatedClosures.add(caller); | |
| 937 } | |
| 938 FunctionElement function = callee.implementation; | |
| 939 FunctionSignature signature = function.functionSignature; | |
| 940 signature.forEachParameter((Element parameter) { | |
| 941 ParameterTypeInformation info = types.getInferredTypeOf(parameter); | |
| 942 info.tagAsTearOffClosureParameter(this); | |
| 943 if (addToQueue) workQueue.add(info); | |
| 944 }); | |
| 945 } | |
| 946 } else { | |
| 947 FunctionElement function = callee.implementation; | |
| 948 FunctionSignature signature = function.functionSignature; | |
| 949 int parameterIndex = 0; | |
| 950 bool visitingRequiredParameter = true; | |
| 951 signature.forEachParameter((Element parameter) { | |
| 952 if (signature.hasOptionalParameters && | |
| 953 parameter == signature.firstOptionalParameter) { | |
| 954 visitingRequiredParameter = false; | |
| 955 } | |
| 956 TypeInformation type = visitingRequiredParameter | |
| 957 ? arguments.positional[parameterIndex] | |
| 958 : signature.optionalParametersAreNamed | |
| 959 ? arguments.named[parameter.name] | |
| 960 : parameterIndex < arguments.positional.length | |
| 961 ? arguments.positional[parameterIndex] | |
| 962 : null; | |
| 963 if (type == null) type = getDefaultTypeOfParameter(parameter); | |
| 964 TypeInformation info = types.getInferredTypeOf(parameter); | |
| 965 if (remove) { | |
| 966 info.removeAssignment(type); | |
| 967 } else { | |
| 968 info.addAssignment(type); | |
| 969 } | |
| 970 parameterIndex++; | |
| 971 if (addToQueue) workQueue.add(info); | |
| 972 }); | |
| 973 } | |
| 974 } | |
| 975 | |
| 976 /** | |
| 977 * Sets the type of a parameter's default value to [type]. If the global | |
| 978 * mapping in [defaultTypeOfParameter] already contains a type, it must be | |
| 979 * a [PlaceholderTypeInformation], which will be replaced. All its uses are | |
| 980 * updated. | |
| 981 */ | |
| 982 void setDefaultTypeOfParameter(ParameterElement parameter, | |
| 983 TypeInformation type) { | |
| 984 assert(parameter.functionDeclaration.isImplementation); | |
| 985 TypeInformation existing = defaultTypeOfParameter[parameter]; | |
| 986 defaultTypeOfParameter[parameter] = type; | |
| 987 TypeInformation info = types.getInferredTypeOf(parameter); | |
| 988 if (existing != null && existing is PlaceholderTypeInformation) { | |
| 989 // Replace references to [existing] to use [type] instead. | |
| 990 if (parameter.functionDeclaration.isInstanceMember) { | |
| 991 ParameterAssignments assignments = info.assignments; | |
| 992 assignments.replace(existing, type); | |
| 993 type.addUser(info); | |
| 994 } else { | |
| 995 List<TypeInformation> assignments = info.assignments; | |
| 996 for (int i = 0; i < assignments.length; i++) { | |
| 997 if (assignments[i] == existing) { | |
| 998 assignments[i] = type; | |
| 999 type.addUser(info); | |
| 1000 } | |
| 1001 } | |
| 1002 } | |
| 1003 } else { | |
| 1004 assert(existing == null); | |
| 1005 } | |
| 1006 } | |
| 1007 | |
| 1008 /** | |
| 1009 * Returns the [TypeInformation] node for the default value of a parameter. | |
| 1010 * If this is queried before it is set by [setDefaultTypeOfParameter], a | |
| 1011 * [PlaceholderTypeInformation] is returned, which will later be replaced | |
| 1012 * by the actual node when [setDefaultTypeOfParameter] is called. | |
| 1013 * | |
| 1014 * Invariant: After graph construction, no [PlaceholderTypeInformation] nodes | |
| 1015 * should be present and a default type for each parameter should | |
| 1016 * exist. | |
| 1017 */ | |
| 1018 TypeInformation getDefaultTypeOfParameter(Element parameter) { | |
| 1019 return defaultTypeOfParameter.putIfAbsent(parameter, () { | |
| 1020 return new PlaceholderTypeInformation(types.currentMember); | |
| 1021 }); | |
| 1022 } | |
| 1023 | |
| 1024 /** | |
| 1025 * Helper to inspect the [TypeGraphInferrer]'s state. To be removed by | |
| 1026 * TODO(johnniwinther) once synthetic parameters get their own default | |
| 1027 * values. | |
| 1028 */ | |
| 1029 bool hasAlreadyComputedTypeOfParameterDefault(Element parameter) { | |
| 1030 TypeInformation seen = defaultTypeOfParameter[parameter]; | |
| 1031 return (seen != null && seen is! PlaceholderTypeInformation); | |
| 1032 } | |
| 1033 | |
| 1034 TypeInformation typeOfElement(Element element) { | |
| 1035 if (element is FunctionElement) return types.functionType; | |
| 1036 return types.getInferredTypeOf(element); | |
| 1037 } | |
| 1038 | |
| 1039 TypeInformation returnTypeOfElement(Element element) { | |
| 1040 if (element is !FunctionElement) return types.dynamicType; | |
| 1041 return types.getInferredTypeOf(element); | |
| 1042 } | |
| 1043 | |
| 1044 void recordTypeOfFinalField(Spannable node, | |
| 1045 Element analyzed, | |
| 1046 Element element, | |
| 1047 TypeInformation type) { | |
| 1048 types.getInferredTypeOf(element).addAssignment(type); | |
| 1049 } | |
| 1050 | |
| 1051 void recordTypeOfNonFinalField(Spannable node, | |
| 1052 Element element, | |
| 1053 TypeInformation type) { | |
| 1054 types.getInferredTypeOf(element).addAssignment(type); | |
| 1055 } | |
| 1056 | |
| 1057 void recordType(Element element, TypeInformation type) { | |
| 1058 types.getInferredTypeOf(element).addAssignment(type); | |
| 1059 } | |
| 1060 | |
| 1061 void recordReturnType(Element element, TypeInformation type) { | |
| 1062 TypeInformation info = types.getInferredTypeOf(element); | |
| 1063 if (element.name == '==') { | |
| 1064 // Even if x.== doesn't return a bool, 'x == null' evaluates to 'false'. | |
| 1065 info.addAssignment(types.boolType); | |
| 1066 } | |
| 1067 // TODO(ngeoffray): Clean up. We do these checks because | |
| 1068 // [SimpleTypesInferrer] deals with two different inferrers. | |
| 1069 if (type == null) return; | |
| 1070 if (info.assignments.isEmpty) info.addAssignment(type); | |
| 1071 } | |
| 1072 | |
| 1073 TypeInformation addReturnTypeFor(Element element, | |
| 1074 TypeInformation unused, | |
| 1075 TypeInformation newType) { | |
| 1076 TypeInformation type = types.getInferredTypeOf(element); | |
| 1077 // TODO(ngeoffray): Clean up. We do this check because | |
| 1078 // [SimpleTypesInferrer] deals with two different inferrers. | |
| 1079 if (element.isGenerativeConstructor) return type; | |
| 1080 type.addAssignment(newType); | |
| 1081 return type; | |
| 1082 } | |
| 1083 | |
| 1084 TypeInformation registerCalledElement(Spannable node, | |
| 1085 Selector selector, | |
| 1086 Element caller, | |
| 1087 Element callee, | |
| 1088 ArgumentsTypes arguments, | |
| 1089 SideEffects sideEffects, | |
| 1090 bool inLoop) { | |
| 1091 CallSiteTypeInformation info = new StaticCallSiteTypeInformation( | |
| 1092 types.currentMember, node, caller, callee, selector, arguments, | |
| 1093 inLoop); | |
| 1094 info.addToGraph(this); | |
| 1095 allocatedCalls.add(info); | |
| 1096 updateSideEffects(sideEffects, selector, callee); | |
| 1097 return info; | |
| 1098 } | |
| 1099 | |
| 1100 TypeInformation registerCalledSelector(ast.Node node, | |
| 1101 Selector selector, | |
| 1102 TypeInformation receiverType, | |
| 1103 Element caller, | |
| 1104 ArgumentsTypes arguments, | |
| 1105 SideEffects sideEffects, | |
| 1106 bool inLoop) { | |
| 1107 if (selector.isClosureCall) { | |
| 1108 return registerCalledClosure( | |
| 1109 node, selector, receiverType, caller, arguments, sideEffects, inLoop); | |
| 1110 } | |
| 1111 | |
| 1112 compiler.world.allFunctions.filter(selector).forEach((callee) { | |
| 1113 updateSideEffects(sideEffects, selector, callee); | |
| 1114 }); | |
| 1115 | |
| 1116 CallSiteTypeInformation info = new DynamicCallSiteTypeInformation( | |
| 1117 types.currentMember, node, caller, selector, receiverType, arguments, | |
| 1118 inLoop); | |
| 1119 | |
| 1120 info.addToGraph(this); | |
| 1121 allocatedCalls.add(info); | |
| 1122 return info; | |
| 1123 } | |
| 1124 | |
| 1125 TypeInformation registerCalledClosure(ast.Node node, | |
| 1126 Selector selector, | |
| 1127 TypeInformation closure, | |
| 1128 Element caller, | |
| 1129 ArgumentsTypes arguments, | |
| 1130 SideEffects sideEffects, | |
| 1131 bool inLoop) { | |
| 1132 sideEffects.setDependsOnSomething(); | |
| 1133 sideEffects.setAllSideEffects(); | |
| 1134 CallSiteTypeInformation info = new ClosureCallSiteTypeInformation( | |
| 1135 types.currentMember, node, caller, selector, closure, arguments, | |
| 1136 inLoop); | |
| 1137 info.addToGraph(this); | |
| 1138 allocatedCalls.add(info); | |
| 1139 return info; | |
| 1140 } | |
| 1141 | |
| 1142 // Sorts the resolved elements by size. We do this for this inferrer | |
| 1143 // to get the same results for [ListTracer] compared to the | |
| 1144 // [SimpleTypesInferrer]. | |
| 1145 Iterable<Element> sortResolvedElements() { | |
| 1146 int max = 0; | |
| 1147 Map<int, Setlet<Element>> methodSizes = new Map<int, Setlet<Element>>(); | |
| 1148 compiler.enqueuer.resolution.resolvedElements.forEach((AstElement element) { | |
| 1149 // TODO(ngeoffray): Not sure why the resolver would put a null | |
| 1150 // mapping. | |
| 1151 if (!compiler.enqueuer.resolution.hasBeenResolved(element)) return; | |
| 1152 TreeElementMapping mapping = element.resolvedAst.elements; | |
| 1153 element = element.implementation; | |
| 1154 if (element.impliesType) return; | |
| 1155 assert(invariant(element, | |
| 1156 element.isField || | |
| 1157 element.isFunction || | |
| 1158 element.isGenerativeConstructor || | |
| 1159 element.isGetter || | |
| 1160 element.isSetter, | |
| 1161 message: 'Unexpected element kind: ${element.kind}')); | |
| 1162 if (element.isAbstract) return; | |
| 1163 // Put the other operators in buckets by length, later to be added in | |
| 1164 // length order. | |
| 1165 int length = mapping.getSelectorCount(); | |
| 1166 max = length > max ? length : max; | |
| 1167 Setlet<Element> set = methodSizes.putIfAbsent( | |
| 1168 length, () => new Setlet<Element>()); | |
| 1169 set.add(element); | |
| 1170 }); | |
| 1171 | |
| 1172 List<Element> result = <Element>[]; | |
| 1173 for (int i = 0; i <= max; i++) { | |
| 1174 Setlet<Element> set = methodSizes[i]; | |
| 1175 if (set != null) result.addAll(set); | |
| 1176 } | |
| 1177 return result; | |
| 1178 } | |
| 1179 | |
| 1180 void clear() { | |
| 1181 allocatedCalls.clear(); | |
| 1182 defaultTypeOfParameter.clear(); | |
| 1183 types.typeInformations.values.forEach((info) => info.clear()); | |
| 1184 types.allocatedTypes.clear(); | |
| 1185 types.concreteTypes.clear(); | |
| 1186 types.allocatedClosures.clear(); | |
| 1187 analyzedElements.clear(); | |
| 1188 generativeConstructorsExposingThis.clear(); | |
| 1189 } | |
| 1190 | |
| 1191 Iterable<Element> getCallersOf(Element element) { | |
| 1192 if (compiler.disableTypeInference) { | |
| 1193 throw new UnsupportedError( | |
| 1194 "Cannot query the type inferrer when type inference is disabled."); | |
| 1195 } | |
| 1196 MemberTypeInformation info = types.getInferredTypeOf(element); | |
| 1197 return info.callers; | |
| 1198 } | |
| 1199 | |
| 1200 /** | |
| 1201 * Returns the type of [element] when being called with [selector]. | |
| 1202 */ | |
| 1203 TypeInformation typeOfElementWithSelector(Element element, | |
| 1204 Selector selector) { | |
| 1205 if (element.name == Compiler.NO_SUCH_METHOD && | |
| 1206 selector.name != element.name) { | |
| 1207 // An invocation can resolve to a [noSuchMethod], in which case | |
| 1208 // we get the return type of [noSuchMethod]. | |
| 1209 return returnTypeOfElement(element); | |
| 1210 } else if (selector.isGetter) { | |
| 1211 if (element.isFunction) { | |
| 1212 // [functionType] is null if the inferrer did not run. | |
| 1213 return types.functionType == null | |
| 1214 ? types.dynamicType | |
| 1215 : types.functionType; | |
| 1216 } else if (element.isField) { | |
| 1217 return typeOfElement(element); | |
| 1218 } else if (Elements.isUnresolved(element)) { | |
| 1219 return types.dynamicType; | |
| 1220 } else { | |
| 1221 assert(element.isGetter); | |
| 1222 return returnTypeOfElement(element); | |
| 1223 } | |
| 1224 } else if (element.isGetter || element.isField) { | |
| 1225 assert(selector.isCall || selector.isSetter); | |
| 1226 return types.dynamicType; | |
| 1227 } else { | |
| 1228 return returnTypeOfElement(element); | |
| 1229 } | |
| 1230 } | |
| 1231 | |
| 1232 void recordCapturedLocalRead(Local local) {} | |
| 1233 | |
| 1234 void recordLocalUpdate(Local local, TypeInformation type) {} | |
| 1235 } | |
| 1236 | |
| 1237 class TypeGraphInferrer implements TypesInferrer { | |
| 1238 TypeGraphInferrerEngine inferrer; | |
| 1239 final Compiler compiler; | |
| 1240 TypeGraphInferrer(Compiler this.compiler); | |
| 1241 | |
| 1242 String get name => 'Graph inferrer'; | |
| 1243 | |
| 1244 void analyzeMain(Element main) { | |
| 1245 inferrer = new TypeGraphInferrerEngine(compiler, main); | |
| 1246 inferrer.runOverAllElements(); | |
| 1247 } | |
| 1248 | |
| 1249 TypeMask getReturnTypeOfElement(Element element) { | |
| 1250 if (compiler.disableTypeInference) return compiler.typesTask.dynamicType; | |
| 1251 // Currently, closure calls return dynamic. | |
| 1252 if (element is! FunctionElement) return compiler.typesTask.dynamicType; | |
| 1253 return inferrer.types.getInferredTypeOf(element).type; | |
| 1254 } | |
| 1255 | |
| 1256 TypeMask getTypeOfElement(Element element) { | |
| 1257 if (compiler.disableTypeInference) return compiler.typesTask.dynamicType; | |
| 1258 // The inferrer stores the return type for a function, so we have to | |
| 1259 // be careful to not return it here. | |
| 1260 if (element is FunctionElement) return compiler.typesTask.functionType; | |
| 1261 return inferrer.types.getInferredTypeOf(element).type; | |
| 1262 } | |
| 1263 | |
| 1264 TypeMask getTypeOfNode(Element owner, ast.Node node) { | |
| 1265 if (compiler.disableTypeInference) return compiler.typesTask.dynamicType; | |
| 1266 return inferrer.types.allocatedLists[node].type; | |
| 1267 } | |
| 1268 | |
| 1269 bool isFixedArrayCheckedForGrowable(ast.Node node) { | |
| 1270 if (compiler.disableTypeInference) return true; | |
| 1271 ListTypeInformation info = inferrer.types.allocatedLists[node]; | |
| 1272 return info.checksGrowable; | |
| 1273 } | |
| 1274 | |
| 1275 TypeMask getTypeOfSelector(Selector selector) { | |
| 1276 if (compiler.disableTypeInference) return compiler.typesTask.dynamicType; | |
| 1277 // Bailout for closure calls. We're not tracking types of | |
| 1278 // closures. | |
| 1279 if (selector.isClosureCall) return compiler.typesTask.dynamicType; | |
| 1280 if (selector.isSetter || selector.isIndexSet) { | |
| 1281 return compiler.typesTask.dynamicType; | |
| 1282 } | |
| 1283 if (inferrer.returnsListElementType(selector)) { | |
| 1284 ContainerTypeMask mask = selector.mask; | |
| 1285 TypeMask elementType = mask.elementType; | |
| 1286 return elementType == null ? compiler.typesTask.dynamicType : elementType; | |
| 1287 } | |
| 1288 if (inferrer.returnsMapValueType(selector)) { | |
| 1289 MapTypeMask mask = selector.mask; | |
| 1290 TypeMask valueType = mask.valueType; | |
| 1291 return valueType == null ? compiler.typesTask.dynamicType | |
| 1292 : valueType; | |
| 1293 } | |
| 1294 | |
| 1295 TypeMask result = const TypeMask.nonNullEmpty(); | |
| 1296 Iterable<Element> elements = compiler.world.allFunctions.filter(selector); | |
| 1297 for (Element element in elements) { | |
| 1298 TypeMask type = | |
| 1299 inferrer.typeOfElementWithSelector(element, selector).type; | |
| 1300 result = result.union(type, compiler.world); | |
| 1301 } | |
| 1302 return result; | |
| 1303 } | |
| 1304 | |
| 1305 Iterable<Element> getCallersOf(Element element) { | |
| 1306 if (compiler.disableTypeInference) { | |
| 1307 throw new UnsupportedError( | |
| 1308 "Cannot query the type inferrer when type inference is disabled."); | |
| 1309 } | |
| 1310 return inferrer.getCallersOf(element); | |
| 1311 } | |
| 1312 | |
| 1313 bool isCalledOnce(Element element) { | |
| 1314 if (compiler.disableTypeInference) return false; | |
| 1315 MemberTypeInformation info = inferrer.types.getInferredTypeOf(element); | |
| 1316 return info.isCalledOnce(); | |
| 1317 } | |
| 1318 | |
| 1319 void clear() { | |
| 1320 inferrer.clear(); | |
| 1321 } | |
| 1322 } | |
| 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