| 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 inferrer_visitor; | |
| 6 | |
| 7 import 'dart:collection' show IterableMixin; | |
| 8 | |
| 9 import '../common.dart'; | |
| 10 import '../options.dart' show CompilerOptions; | |
| 11 import '../compiler.dart' show Compiler; | |
| 12 import '../constants/constant_system.dart'; | |
| 13 import '../constants/expressions.dart'; | |
| 14 import '../elements/resolution_types.dart'; | |
| 15 import '../elements/elements.dart'; | |
| 16 import '../resolution/operators.dart'; | |
| 17 import '../resolution/semantic_visitor.dart'; | |
| 18 import '../resolution/tree_elements.dart' show TreeElements; | |
| 19 import '../tree/tree.dart'; | |
| 20 import '../types/constants.dart' show computeTypeMask; | |
| 21 import '../types/types.dart' show TypeMask; | |
| 22 import '../universe/call_structure.dart' show CallStructure; | |
| 23 import '../universe/selector.dart' show Selector; | |
| 24 import '../util/util.dart'; | |
| 25 import '../world.dart' show ClosedWorld; | |
| 26 import 'inferrer_engine.dart'; | |
| 27 import 'type_graph_nodes.dart'; | |
| 28 import 'type_system.dart'; | |
| 29 | |
| 30 /** | |
| 31 * A variable scope holds types for variables. It has a link to a | |
| 32 * parent scope, but never changes the types in that parent. Instead, | |
| 33 * updates to locals of a parent scope are put in the current scope. | |
| 34 * The inferrer makes sure updates get merged into the parent scope, | |
| 35 * once the control flow block has been visited. | |
| 36 */ | |
| 37 class VariableScope { | |
| 38 Map<Local, TypeInformation> variables; | |
| 39 | |
| 40 /// The parent of this scope. Null for the root scope. | |
| 41 final VariableScope parent; | |
| 42 | |
| 43 /// The [Node] that created this scope. | |
| 44 final Node block; | |
| 45 | |
| 46 VariableScope(this.block, [parent]) | |
| 47 : this.variables = null, | |
| 48 this.parent = parent; | |
| 49 | |
| 50 VariableScope.deepCopyOf(VariableScope other) | |
| 51 : variables = other.variables == null | |
| 52 ? null | |
| 53 : new Map<Local, TypeInformation>.from(other.variables), | |
| 54 block = other.block, | |
| 55 parent = other.parent == null | |
| 56 ? null | |
| 57 : new VariableScope.deepCopyOf(other.parent); | |
| 58 | |
| 59 VariableScope.topLevelCopyOf(VariableScope other) | |
| 60 : variables = other.variables == null | |
| 61 ? null | |
| 62 : new Map<Local, TypeInformation>.from(other.variables), | |
| 63 block = other.block, | |
| 64 parent = other.parent; | |
| 65 | |
| 66 TypeInformation operator [](Local variable) { | |
| 67 TypeInformation result; | |
| 68 if (variables == null || (result = variables[variable]) == null) { | |
| 69 return parent == null ? null : parent[variable]; | |
| 70 } | |
| 71 return result; | |
| 72 } | |
| 73 | |
| 74 void operator []=(Local variable, TypeInformation mask) { | |
| 75 assert(mask != null); | |
| 76 if (variables == null) { | |
| 77 variables = new Map<Local, TypeInformation>(); | |
| 78 } | |
| 79 variables[variable] = mask; | |
| 80 } | |
| 81 | |
| 82 void forEachOwnLocal(void f(Local variable, TypeInformation type)) { | |
| 83 if (variables == null) return; | |
| 84 variables.forEach(f); | |
| 85 } | |
| 86 | |
| 87 void forEachLocalUntilNode( | |
| 88 Node node, void f(Local variable, TypeInformation type), | |
| 89 [Setlet<Local> seenLocals]) { | |
| 90 if (seenLocals == null) seenLocals = new Setlet<Local>(); | |
| 91 if (variables != null) { | |
| 92 variables.forEach((variable, type) { | |
| 93 if (seenLocals.contains(variable)) return; | |
| 94 seenLocals.add(variable); | |
| 95 f(variable, type); | |
| 96 }); | |
| 97 } | |
| 98 if (block == node) return; | |
| 99 if (parent != null) parent.forEachLocalUntilNode(node, f, seenLocals); | |
| 100 } | |
| 101 | |
| 102 void forEachLocal(void f(Local variable, TypeInformation type)) { | |
| 103 forEachLocalUntilNode(null, f); | |
| 104 } | |
| 105 | |
| 106 bool updates(Local variable) { | |
| 107 if (variables == null) return false; | |
| 108 return variables.containsKey(variable); | |
| 109 } | |
| 110 | |
| 111 String toString() { | |
| 112 String rest = parent == null ? "null" : parent.toString(); | |
| 113 return '$variables $rest'; | |
| 114 } | |
| 115 } | |
| 116 | |
| 117 class FieldInitializationScope { | |
| 118 final TypeSystem types; | |
| 119 Map<Element, TypeInformation> fields; | |
| 120 bool isThisExposed; | |
| 121 | |
| 122 FieldInitializationScope(this.types) : isThisExposed = false; | |
| 123 | |
| 124 FieldInitializationScope.internalFrom(FieldInitializationScope other) | |
| 125 : types = other.types, | |
| 126 isThisExposed = other.isThisExposed; | |
| 127 | |
| 128 factory FieldInitializationScope.from(FieldInitializationScope other) { | |
| 129 if (other == null) return null; | |
| 130 return new FieldInitializationScope.internalFrom(other); | |
| 131 } | |
| 132 | |
| 133 void updateField(Element field, TypeInformation type) { | |
| 134 if (isThisExposed) return; | |
| 135 if (fields == null) fields = new Map<Element, TypeInformation>(); | |
| 136 fields[field] = type; | |
| 137 } | |
| 138 | |
| 139 TypeInformation readField(Element field) { | |
| 140 return fields == null ? null : fields[field]; | |
| 141 } | |
| 142 | |
| 143 void forEach(void f(Element element, TypeInformation type)) { | |
| 144 if (fields == null) return; | |
| 145 fields.forEach(f); | |
| 146 } | |
| 147 | |
| 148 void mergeDiamondFlow( | |
| 149 FieldInitializationScope thenScope, FieldInitializationScope elseScope) { | |
| 150 // Quick bailout check. If [isThisExposed] is true, we know the | |
| 151 // code following won'TypeInformation do anything. | |
| 152 if (isThisExposed) return; | |
| 153 if (elseScope == null || elseScope.fields == null) { | |
| 154 elseScope = this; | |
| 155 } | |
| 156 | |
| 157 thenScope.forEach((Element field, TypeInformation type) { | |
| 158 TypeInformation otherType = elseScope.readField(field); | |
| 159 if (otherType == null) return; | |
| 160 updateField(field, types.allocateDiamondPhi(type, otherType)); | |
| 161 }); | |
| 162 isThisExposed = thenScope.isThisExposed || elseScope.isThisExposed; | |
| 163 } | |
| 164 } | |
| 165 | |
| 166 /** | |
| 167 * Placeholder for inferred arguments types on sends. | |
| 168 */ | |
| 169 class ArgumentsTypes extends IterableMixin<TypeInformation> { | |
| 170 final List<TypeInformation> positional; | |
| 171 final Map<String, TypeInformation> named; | |
| 172 ArgumentsTypes(this.positional, named) | |
| 173 : this.named = (named == null || named.isEmpty) ? const {} : named { | |
| 174 assert(this.positional.every((TypeInformation type) => type != null)); | |
| 175 assert(this.named.values.every((TypeInformation type) => type != null)); | |
| 176 } | |
| 177 | |
| 178 ArgumentsTypes.empty() | |
| 179 : positional = const [], | |
| 180 named = const {}; | |
| 181 | |
| 182 int get length => positional.length + named.length; | |
| 183 | |
| 184 Iterator<TypeInformation> get iterator => new ArgumentsTypesIterator(this); | |
| 185 | |
| 186 String toString() => "{ positional = $positional, named = $named }"; | |
| 187 | |
| 188 bool operator ==(other) { | |
| 189 if (positional.length != other.positional.length) return false; | |
| 190 if (named.length != other.named.length) return false; | |
| 191 for (int i = 0; i < positional.length; i++) { | |
| 192 if (positional[i] != other.positional[i]) return false; | |
| 193 } | |
| 194 named.forEach((name, type) { | |
| 195 if (other.named[name] != type) return false; | |
| 196 }); | |
| 197 return true; | |
| 198 } | |
| 199 | |
| 200 int get hashCode => throw new UnsupportedError('ArgumentsTypes.hashCode'); | |
| 201 | |
| 202 bool hasNoArguments() => positional.isEmpty && named.isEmpty; | |
| 203 | |
| 204 void forEach(void f(TypeInformation type)) { | |
| 205 positional.forEach(f); | |
| 206 named.values.forEach(f); | |
| 207 } | |
| 208 | |
| 209 bool every(bool f(TypeInformation type)) { | |
| 210 return positional.every(f) && named.values.every(f); | |
| 211 } | |
| 212 | |
| 213 bool contains(TypeInformation type) { | |
| 214 return positional.contains(type) || named.containsValue(type); | |
| 215 } | |
| 216 } | |
| 217 | |
| 218 class ArgumentsTypesIterator implements Iterator<TypeInformation> { | |
| 219 final Iterator<TypeInformation> positional; | |
| 220 final Iterator<TypeInformation> named; | |
| 221 bool _iteratePositional = true; | |
| 222 | |
| 223 ArgumentsTypesIterator(ArgumentsTypes iteratee) | |
| 224 : positional = iteratee.positional.iterator, | |
| 225 named = iteratee.named.values.iterator; | |
| 226 | |
| 227 Iterator<TypeInformation> get _currentIterator => | |
| 228 _iteratePositional ? positional : named; | |
| 229 | |
| 230 TypeInformation get current => _currentIterator.current; | |
| 231 | |
| 232 bool moveNext() { | |
| 233 if (_iteratePositional && positional.moveNext()) { | |
| 234 return true; | |
| 235 } | |
| 236 _iteratePositional = false; | |
| 237 return named.moveNext(); | |
| 238 } | |
| 239 } | |
| 240 | |
| 241 /** | |
| 242 * Placeholder for inferred types of local variables. | |
| 243 */ | |
| 244 class LocalsHandler { | |
| 245 final CompilerOptions options; | |
| 246 final TypeSystem types; | |
| 247 final InferrerEngine inferrer; | |
| 248 final VariableScope locals; | |
| 249 final Map<Local, Element> captured; | |
| 250 final Map<Local, Element> capturedAndBoxed; | |
| 251 final FieldInitializationScope fieldScope; | |
| 252 LocalsHandler tryBlock; | |
| 253 bool seenReturnOrThrow = false; | |
| 254 bool seenBreakOrContinue = false; | |
| 255 | |
| 256 bool get aborts { | |
| 257 return seenReturnOrThrow || seenBreakOrContinue; | |
| 258 } | |
| 259 | |
| 260 bool get inTryBlock => tryBlock != null; | |
| 261 | |
| 262 LocalsHandler(this.inferrer, this.types, this.options, Node block, | |
| 263 [this.fieldScope]) | |
| 264 : locals = new VariableScope(block), | |
| 265 captured = new Map<Local, Element>(), | |
| 266 capturedAndBoxed = new Map<Local, Element>(), | |
| 267 tryBlock = null; | |
| 268 | |
| 269 LocalsHandler.from(LocalsHandler other, Node block, | |
| 270 {bool useOtherTryBlock: true}) | |
| 271 : locals = new VariableScope(block, other.locals), | |
| 272 fieldScope = new FieldInitializationScope.from(other.fieldScope), | |
| 273 captured = other.captured, | |
| 274 capturedAndBoxed = other.capturedAndBoxed, | |
| 275 types = other.types, | |
| 276 inferrer = other.inferrer, | |
| 277 options = other.options { | |
| 278 tryBlock = useOtherTryBlock ? other.tryBlock : this; | |
| 279 } | |
| 280 | |
| 281 LocalsHandler.deepCopyOf(LocalsHandler other) | |
| 282 : locals = new VariableScope.deepCopyOf(other.locals), | |
| 283 fieldScope = new FieldInitializationScope.from(other.fieldScope), | |
| 284 captured = other.captured, | |
| 285 capturedAndBoxed = other.capturedAndBoxed, | |
| 286 tryBlock = other.tryBlock, | |
| 287 types = other.types, | |
| 288 inferrer = other.inferrer, | |
| 289 options = other.options; | |
| 290 | |
| 291 LocalsHandler.topLevelCopyOf(LocalsHandler other) | |
| 292 : locals = new VariableScope.topLevelCopyOf(other.locals), | |
| 293 fieldScope = new FieldInitializationScope.from(other.fieldScope), | |
| 294 captured = other.captured, | |
| 295 capturedAndBoxed = other.capturedAndBoxed, | |
| 296 tryBlock = other.tryBlock, | |
| 297 types = other.types, | |
| 298 inferrer = other.inferrer, | |
| 299 options = other.options; | |
| 300 | |
| 301 TypeInformation use(Local local) { | |
| 302 if (capturedAndBoxed.containsKey(local)) { | |
| 303 return inferrer.typeOfElement(capturedAndBoxed[local]); | |
| 304 } else { | |
| 305 if (captured.containsKey(local)) { | |
| 306 inferrer.recordCapturedLocalRead(local); | |
| 307 } | |
| 308 return locals[local]; | |
| 309 } | |
| 310 } | |
| 311 | |
| 312 void update(LocalElement local, TypeInformation type, Node node) { | |
| 313 assert(type != null); | |
| 314 if (options.trustTypeAnnotations || options.enableTypeAssertions) { | |
| 315 type = types.narrowType(type, local.type); | |
| 316 } | |
| 317 updateLocal() { | |
| 318 TypeInformation currentType = locals[local]; | |
| 319 | |
| 320 SendSet send = node != null ? node.asSendSet() : null; | |
| 321 if (send != null && send.isIfNullAssignment && currentType != null) { | |
| 322 // If-null assignments may return either the new or the original value | |
| 323 // narrowed to non-null. | |
| 324 type = types.addPhiInput( | |
| 325 local, | |
| 326 types.allocatePhi( | |
| 327 locals.block, local, types.narrowNotNull(currentType)), | |
| 328 type); | |
| 329 } | |
| 330 locals[local] = type; | |
| 331 if (currentType != type) { | |
| 332 inferrer.recordLocalUpdate(local, type); | |
| 333 } | |
| 334 } | |
| 335 | |
| 336 if (capturedAndBoxed.containsKey(local)) { | |
| 337 inferrer.recordTypeOfNonFinalField(node, capturedAndBoxed[local], type); | |
| 338 } else if (inTryBlock) { | |
| 339 // We don'TypeInformation know if an assignment in a try block | |
| 340 // will be executed, so all assigments in that block are | |
| 341 // potential types after we have left it. We update the parent | |
| 342 // of the try block so that, at exit of the try block, we get | |
| 343 // the right phi for it. | |
| 344 TypeInformation existing = tryBlock.locals.parent[local]; | |
| 345 if (existing != null) { | |
| 346 TypeInformation phiType = | |
| 347 types.allocatePhi(tryBlock.locals.block, local, existing); | |
| 348 TypeInformation inputType = types.addPhiInput(local, phiType, type); | |
| 349 tryBlock.locals.parent[local] = inputType; | |
| 350 } | |
| 351 // Update the current handler unconditionnally with the new | |
| 352 // type. | |
| 353 updateLocal(); | |
| 354 } else { | |
| 355 updateLocal(); | |
| 356 } | |
| 357 } | |
| 358 | |
| 359 void setCaptured(Local local, Element field) { | |
| 360 captured[local] = field; | |
| 361 } | |
| 362 | |
| 363 void setCapturedAndBoxed(Local local, Element field) { | |
| 364 capturedAndBoxed[local] = field; | |
| 365 } | |
| 366 | |
| 367 void mergeDiamondFlow(LocalsHandler thenBranch, LocalsHandler elseBranch) { | |
| 368 if (fieldScope != null && elseBranch != null) { | |
| 369 fieldScope.mergeDiamondFlow(thenBranch.fieldScope, elseBranch.fieldScope); | |
| 370 } | |
| 371 seenReturnOrThrow = thenBranch.seenReturnOrThrow && | |
| 372 elseBranch != null && | |
| 373 elseBranch.seenReturnOrThrow; | |
| 374 seenBreakOrContinue = thenBranch.seenBreakOrContinue && | |
| 375 elseBranch != null && | |
| 376 elseBranch.seenBreakOrContinue; | |
| 377 if (aborts) return; | |
| 378 | |
| 379 void mergeOneBranch(LocalsHandler other) { | |
| 380 other.locals.forEachOwnLocal((Local local, TypeInformation type) { | |
| 381 TypeInformation myType = locals[local]; | |
| 382 if (myType == null) return; // Variable is only defined in [other]. | |
| 383 if (type == myType) return; | |
| 384 locals[local] = types.allocateDiamondPhi(myType, type); | |
| 385 }); | |
| 386 } | |
| 387 | |
| 388 void inPlaceUpdateOneBranch(LocalsHandler other) { | |
| 389 other.locals.forEachOwnLocal((Local local, TypeInformation type) { | |
| 390 TypeInformation myType = locals[local]; | |
| 391 if (myType == null) return; // Variable is only defined in [other]. | |
| 392 if (type == myType) return; | |
| 393 locals[local] = type; | |
| 394 }); | |
| 395 } | |
| 396 | |
| 397 if (thenBranch.aborts) { | |
| 398 if (elseBranch == null) return; | |
| 399 inPlaceUpdateOneBranch(elseBranch); | |
| 400 } else if (elseBranch == null) { | |
| 401 mergeOneBranch(thenBranch); | |
| 402 } else if (elseBranch.aborts) { | |
| 403 inPlaceUpdateOneBranch(thenBranch); | |
| 404 } else { | |
| 405 void mergeLocal(Local local) { | |
| 406 TypeInformation myType = locals[local]; | |
| 407 if (myType == null) return; | |
| 408 TypeInformation elseType = elseBranch.locals[local]; | |
| 409 TypeInformation thenType = thenBranch.locals[local]; | |
| 410 if (thenType == elseType) { | |
| 411 locals[local] = thenType; | |
| 412 } else { | |
| 413 locals[local] = types.allocateDiamondPhi(thenType, elseType); | |
| 414 } | |
| 415 } | |
| 416 | |
| 417 thenBranch.locals.forEachOwnLocal((Local local, _) { | |
| 418 mergeLocal(local); | |
| 419 }); | |
| 420 elseBranch.locals.forEachOwnLocal((Local local, _) { | |
| 421 // Discard locals we already processed when iterating over | |
| 422 // [thenBranch]'s locals. | |
| 423 if (!thenBranch.locals.updates(local)) mergeLocal(local); | |
| 424 }); | |
| 425 } | |
| 426 } | |
| 427 | |
| 428 /** | |
| 429 * Merge all [LocalsHandler] in [handlers] into [:this:]. | |
| 430 * | |
| 431 * If [keepOwnLocals] is true, the types of locals in this | |
| 432 * [LocalsHandler] are being used in the merge. [keepOwnLocals] | |
| 433 * should be true if this [LocalsHandler], the dominator of | |
| 434 * all [handlers], also direclty flows into the join point, | |
| 435 * that is the code after all [handlers]. For example, consider: | |
| 436 * | |
| 437 * [: switch (...) { | |
| 438 * case 1: ...; break; | |
| 439 * } | |
| 440 * :] | |
| 441 * | |
| 442 * The [LocalsHandler] at entry of the switch also flows into the | |
| 443 * exit of the switch, because there is no default case. So the | |
| 444 * types of locals at entry of the switch have to take part to the | |
| 445 * merge. | |
| 446 * | |
| 447 * The above situation is also true for labeled statements like | |
| 448 * | |
| 449 * [: L: { | |
| 450 * if (...) break; | |
| 451 * ... | |
| 452 * } | |
| 453 * :] | |
| 454 * | |
| 455 * where [:this:] is the [LocalsHandler] for the paths through the | |
| 456 * labeled statement that do not break out. | |
| 457 */ | |
| 458 void mergeAfterBreaks(List<LocalsHandler> handlers, | |
| 459 {bool keepOwnLocals: true}) { | |
| 460 Node level = locals.block; | |
| 461 // Use a separate locals handler to perform the merge in, so that Phi | |
| 462 // creation does not invalidate previous type knowledge while we might | |
| 463 // still look it up. | |
| 464 LocalsHandler merged = new LocalsHandler.from(this, level); | |
| 465 Set<Local> seenLocals = new Setlet<Local>(); | |
| 466 bool allBranchesAbort = true; | |
| 467 // Merge all other handlers. | |
| 468 for (LocalsHandler handler in handlers) { | |
| 469 allBranchesAbort = allBranchesAbort && handler.seenReturnOrThrow; | |
| 470 merged.mergeHandler(handler, seenLocals); | |
| 471 } | |
| 472 // If we want to keep own locals, we merge [seenLocals] from [this] into | |
| 473 // [merged] to update the Phi nodes with original values. | |
| 474 if (keepOwnLocals && !seenReturnOrThrow) { | |
| 475 for (Local variable in seenLocals) { | |
| 476 TypeInformation originalType = locals[variable]; | |
| 477 if (originalType != null) { | |
| 478 merged.locals[variable] = types.addPhiInput( | |
| 479 variable, merged.locals[variable], originalType); | |
| 480 } | |
| 481 } | |
| 482 } | |
| 483 // Clean up Phi nodes with single input and store back result into | |
| 484 // actual locals handler. | |
| 485 merged.locals.forEachOwnLocal((Local variable, TypeInformation type) { | |
| 486 locals[variable] = types.simplifyPhi(level, variable, type); | |
| 487 }); | |
| 488 seenReturnOrThrow = | |
| 489 allBranchesAbort && (!keepOwnLocals || seenReturnOrThrow); | |
| 490 } | |
| 491 | |
| 492 /** | |
| 493 * Merge [other] into this handler. Returns whether a local in this | |
| 494 * has changed. If [seen] is not null, we allocate new Phi nodes | |
| 495 * unless the local is already present in the set [seen]. This effectively | |
| 496 * overwrites the current type knowledge in this handler. | |
| 497 */ | |
| 498 bool mergeHandler(LocalsHandler other, [Set<Local> seen]) { | |
| 499 if (other.seenReturnOrThrow) return false; | |
| 500 bool changed = false; | |
| 501 other.locals.forEachLocalUntilNode(locals.block, (local, otherType) { | |
| 502 TypeInformation myType = locals[local]; | |
| 503 if (myType == null) return; | |
| 504 TypeInformation newType; | |
| 505 if (seen != null && !seen.contains(local)) { | |
| 506 newType = types.allocatePhi(locals.block, local, otherType); | |
| 507 seen.add(local); | |
| 508 } else { | |
| 509 newType = types.addPhiInput(local, myType, otherType); | |
| 510 } | |
| 511 if (newType != myType) { | |
| 512 changed = true; | |
| 513 locals[local] = newType; | |
| 514 } | |
| 515 }); | |
| 516 return changed; | |
| 517 } | |
| 518 | |
| 519 /** | |
| 520 * Merge all [LocalsHandler] in [handlers] into this handler. | |
| 521 * Returns whether a local in this handler has changed. | |
| 522 */ | |
| 523 bool mergeAll(List<LocalsHandler> handlers) { | |
| 524 bool changed = false; | |
| 525 assert(!seenReturnOrThrow); | |
| 526 handlers.forEach((other) { | |
| 527 changed = mergeHandler(other) || changed; | |
| 528 }); | |
| 529 return changed; | |
| 530 } | |
| 531 | |
| 532 void startLoop(Node loop) { | |
| 533 locals.forEachLocal((Local variable, TypeInformation type) { | |
| 534 TypeInformation newType = types.allocateLoopPhi(loop, variable, type); | |
| 535 if (newType != type) { | |
| 536 locals[variable] = newType; | |
| 537 } | |
| 538 }); | |
| 539 } | |
| 540 | |
| 541 void endLoop(Node loop) { | |
| 542 locals.forEachLocal((Local variable, TypeInformation type) { | |
| 543 TypeInformation newType = types.simplifyPhi(loop, variable, type); | |
| 544 if (newType != type) { | |
| 545 locals[variable] = newType; | |
| 546 } | |
| 547 }); | |
| 548 } | |
| 549 | |
| 550 void updateField(Element element, TypeInformation type) { | |
| 551 fieldScope.updateField(element, type); | |
| 552 } | |
| 553 } | |
| OLD | NEW |