OLD | NEW |
---|---|
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library dart_types; | 5 library dart_types; |
6 | 6 |
7 import 'dart2jslib.dart' show Compiler, invariant, Script, Message; | 7 import 'dart2jslib.dart' show Compiler, invariant, Script, Message; |
8 import 'elements/modelx.dart' | 8 import 'elements/modelx.dart' |
9 show VoidElementX, LibraryElementX, BaseClassElementX; | 9 show VoidElementX, LibraryElementX, BaseClassElementX; |
10 import 'elements/elements.dart'; | 10 import 'elements/elements.dart'; |
11 import 'util/util.dart' show Link, LinkBuilder; | 11 import 'ordered_typeset.dart' show OrderedTypeSet; |
12 import 'util/util.dart' show Link, LinkBuilder, CURRENT_ELEMENT_SPANNABLE; | |
12 | 13 |
13 class TypeKind { | 14 class TypeKind { |
14 final String id; | 15 final String id; |
15 | 16 |
16 const TypeKind(String this.id); | 17 const TypeKind(String this.id); |
17 | 18 |
18 static const TypeKind FUNCTION = const TypeKind('function'); | 19 static const TypeKind FUNCTION = const TypeKind('function'); |
19 static const TypeKind INTERFACE = const TypeKind('interface'); | 20 static const TypeKind INTERFACE = const TypeKind('interface'); |
20 static const TypeKind STATEMENT = const TypeKind('statement'); | 21 static const TypeKind STATEMENT = const TypeKind('statement'); |
21 static const TypeKind TYPEDEF = const TypeKind('typedef'); | 22 static const TypeKind TYPEDEF = const TypeKind('typedef'); |
(...skipping 1448 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1470 } else if (!b.isEmpty) { | 1471 } else if (!b.isEmpty) { |
1471 // [b] is longer than [a] => a < b. | 1472 // [b] is longer than [a] => a < b. |
1472 return -1; | 1473 return -1; |
1473 } | 1474 } |
1474 return 0; | 1475 return 0; |
1475 } | 1476 } |
1476 | 1477 |
1477 static List<DartType> sorted(Iterable<DartType> types) { | 1478 static List<DartType> sorted(Iterable<DartType> types) { |
1478 return types.toList()..sort(compare); | 1479 return types.toList()..sort(compare); |
1479 } | 1480 } |
1481 | |
1482 /// Computes the least upper bound of two interface types [a] and [b]. | |
1483 InterfaceType computeLeastUpperBoundInterfaces(InterfaceType a, | |
1484 InterfaceType b) { | |
1485 | |
1486 /// Returns the set of supertypes of [type] at depth [depth]. | |
1487 Set<DartType> getSupertypesAtDepth(InterfaceType type, int depth) { | |
1488 ClassElement cls = type.element; | |
1489 OrderedTypeSet types = cls.allSupertypesAndSelf; | |
1490 Link<DartType> typeVariables = cls.typeVariables; | |
1491 Link<DartType> typeArguments = type.typeArguments; | |
1492 Set<DartType> set = new Set<DartType>(); | |
1493 types.forEach(depth, (DartType type) { | |
1494 set.add(type.subst(typeArguments, typeVariables)); | |
1495 }); | |
1496 return set; | |
1497 } | |
1498 | |
1499 ClassElement aClass = a.element; | |
1500 ClassElement bClass = b.element; | |
1501 int maxCommonDepth = aClass.hierarchyDepth; | |
karlklose
2013/11/21 13:29:10
`= min(aClass.hierarchyDepth, bClass.hierarchyDept
Johnni Winther
2013/11/25 13:58:27
Done.
| |
1502 if (bClass.hierarchyDepth < maxCommonDepth) { | |
1503 maxCommonDepth = bClass.hierarchyDepth; | |
1504 } | |
1505 for (int depth = maxCommonDepth; depth >= 0; depth--) { | |
1506 Set<DartType> aTypeSet = getSupertypesAtDepth(a, depth); | |
1507 Set<DartType> bTypeSet = getSupertypesAtDepth(b, depth); | |
1508 Set<DartType> intersection = aTypeSet..retainAll(bTypeSet); | |
1509 if (intersection.length == 1) { | |
1510 return intersection.first; | |
1511 } | |
1512 } | |
1513 assert(invariant(CURRENT_ELEMENT_SPANNABLE, false, | |
1514 message: 'No least upper bound computed for $a and $b.')); | |
1515 } | |
1516 | |
1517 /// Computes the least upper bound of the types in the longest prefix of [a] | |
1518 /// and [b]. | |
1519 Link<DartType> computeLeastUpperBoundsTypes(Link<DartType> a, | |
1520 Link<DartType> b) { | |
1521 if (a.isEmpty || b.isEmpty) return const Link<DartType>(); | |
1522 LinkBuilder<DartType> types = new LinkBuilder<DartType>(); | |
1523 while (!a.isEmpty && !b.isEmpty) { | |
1524 types.addLast(computeLeastUpperBound(a.head, b.head)); | |
1525 a = a.tail; | |
1526 b = b.tail; | |
1527 } | |
1528 return types.toLink(); | |
1529 } | |
1530 | |
1531 /// Computes the least upper bound of two function types [a] and [b]. | |
1532 DartType computeLeastUpperBoundFunctionTypes(FunctionType a, | |
karlklose
2013/11/21 13:29:10
Perhaps add comments explaining what happens for f
Johnni Winther
2013/11/25 13:58:27
Done.
| |
1533 FunctionType b) { | |
1534 if (a.parameterTypes.slowLength() != b.parameterTypes.slowLength()) { | |
1535 return compiler.functionClass.rawType; | |
1536 } | |
1537 DartType returnType = computeLeastUpperBound(a.returnType, b.returnType); | |
1538 Link<DartType> parameterTypes = | |
1539 computeLeastUpperBoundsTypes(a.parameterTypes, b.parameterTypes); | |
1540 Link<DartType> optionalParameterTypes = | |
1541 computeLeastUpperBoundsTypes(a.optionalParameterTypes, | |
1542 b.optionalParameterTypes); | |
1543 LinkBuilder<String> namedParameters = new LinkBuilder<String>(); | |
1544 Link<String> aNamedParameters = a.namedParameters; | |
1545 Link<String> bNamedParameters = b.namedParameters; | |
1546 LinkBuilder<DartType> namedParameterTypes = new LinkBuilder<DartType>(); | |
1547 Link<DartType> aNamedParameterTypes = a.namedParameterTypes; | |
1548 Link<DartType> bNamedParameterTypes = b.namedParameterTypes; | |
1549 while (!aNamedParameters.isEmpty && !bNamedParameters.isEmpty) { | |
1550 String aNamedParameter = aNamedParameters.head; | |
1551 String bNamedParameter = bNamedParameters.head; | |
1552 int result = aNamedParameter.compareTo(bNamedParameter); | |
1553 if (result == 0) { | |
1554 namedParameters.addLast(aNamedParameter); | |
1555 namedParameterTypes.addLast(computeLeastUpperBound( | |
1556 aNamedParameterTypes.head, bNamedParameterTypes.head)); | |
1557 } | |
1558 if (result <= 0) { | |
1559 aNamedParameters = aNamedParameters.tail; | |
1560 aNamedParameterTypes = aNamedParameterTypes.tail; | |
1561 } | |
1562 if (result >= 0) { | |
1563 bNamedParameters = bNamedParameters.tail; | |
1564 bNamedParameterTypes = bNamedParameterTypes.tail; | |
1565 } | |
1566 } | |
1567 return new FunctionType(compiler.functionClass, | |
1568 returnType, | |
1569 parameterTypes, optionalParameterTypes, | |
1570 namedParameters.toLink(), namedParameterTypes.toLink()); | |
1571 } | |
1572 | |
1573 /// Computes the least upper bound of two types of which at least one is a | |
1574 /// type variable. The least upper bound of a type variable is defined in | |
1575 /// terms of its bound, but to ensure reflexivity we need to check for common | |
1576 /// bounds transitively. | |
1577 DartType computeLeastUpperBoundTypeVariableTypes(DartType a, | |
1578 DartType b) { | |
1579 Set<DartType> typeVariableBounds = new Set<DartType>(); | |
1580 while (a.kind == TypeKind.TYPE_VARIABLE) { | |
1581 if (a == b) return a; | |
1582 typeVariableBounds.add(a); | |
1583 TypeVariableElement element = a.element; | |
1584 a = element.bound; | |
1585 } | |
1586 while (b.kind == TypeKind.TYPE_VARIABLE) { | |
1587 if (typeVariableBounds.contains(b)) return b; | |
1588 TypeVariableElement element = b.element; | |
1589 b = element.bound; | |
1590 } | |
1591 return computeLeastUpperBound(a, b); | |
1592 } | |
1593 | |
1594 /// Computes the least upper bound for [a] and [b]. | |
1595 DartType computeLeastUpperBound(DartType a, DartType b) { | |
1596 if (a == b) return a; | |
1597 | |
1598 if (a.kind == TypeKind.TYPE_VARIABLE || | |
1599 b.kind == TypeKind.TYPE_VARIABLE) { | |
1600 return computeLeastUpperBoundTypeVariableTypes(a, b); | |
1601 } | |
1602 | |
1603 a = a.unalias(compiler); | |
1604 b = b.unalias(compiler); | |
1605 | |
1606 if (a.treatAsDynamic || b.treatAsDynamic) return dynamicType; | |
1607 if (a.isVoid || b.isVoid) return voidType; | |
1608 | |
1609 if (a.kind == TypeKind.FUNCTION && b.kind == TypeKind.FUNCTION) { | |
1610 return computeLeastUpperBoundFunctionTypes(a, b); | |
1611 } | |
1612 | |
1613 if (a.kind == TypeKind.FUNCTION) { | |
1614 a = compiler.functionClass.rawType; | |
1615 } | |
1616 if (b.kind == TypeKind.FUNCTION) { | |
1617 b = compiler.functionClass.rawType; | |
1618 } | |
1619 | |
1620 if (a.kind == TypeKind.INTERFACE && b.kind == TypeKind.INTERFACE) { | |
1621 return computeLeastUpperBoundInterfaces(a, b); | |
1622 } | |
1623 return dynamicType; | |
1624 } | |
1480 } | 1625 } |
1481 | 1626 |
1482 /** | 1627 /** |
1483 * Type visitor that determines one type could a subtype of another given the | 1628 * Type visitor that determines one type could a subtype of another given the |
1484 * right type variable substitution. The computation is approximate and returns | 1629 * right type variable substitution. The computation is approximate and returns |
1485 * [:false:] only if we are sure no such substitution exists. | 1630 * [:false:] only if we are sure no such substitution exists. |
1486 */ | 1631 */ |
1487 class PotentialSubtypeVisitor extends SubtypeVisitor { | 1632 class PotentialSubtypeVisitor extends SubtypeVisitor { |
1488 PotentialSubtypeVisitor(Compiler compiler, | 1633 PotentialSubtypeVisitor(Compiler compiler, |
1489 DynamicType dynamicType, | 1634 DynamicType dynamicType, |
1490 VoidType voidType) | 1635 VoidType voidType) |
1491 : super(compiler, dynamicType, voidType); | 1636 : super(compiler, dynamicType, voidType); |
1492 | 1637 |
1493 | 1638 |
1494 bool isSubtype(DartType t, DartType s) { | 1639 bool isSubtype(DartType t, DartType s) { |
1495 if (t is TypeVariableType || s is TypeVariableType) { | 1640 if (t is TypeVariableType || s is TypeVariableType) { |
1496 return true; | 1641 return true; |
1497 } | 1642 } |
1498 return super.isSubtype(t, s); | 1643 return super.isSubtype(t, s); |
1499 } | 1644 } |
1500 } | 1645 } |
OLD | NEW |