Implement least upper bound.

Implement least upper bound.

As a side-effect disallow multiple inheritance with different type arguments.

R=karlklose@google.com

Committed: https://code.google.com/p/dart/source/detail?r=30661

[Johnni Winther, 2013-11-14 12:51:34]

PTAL

[Johnni Winther, 2013-11-20 08:46:53]

ping

[karlklose, 2013-11-21 13:29:09]

LGTM.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/dart_types.dart (right):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/dart_types.dart:1501: int
maxCommonDepth = aClass.hierarchyDepth;
`= min(aClass.hierarchyDepth, bClass.hierarchyDepth);`

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/dart_types.dart:1532: DartType
computeLeastUpperBoundFunctionTypes(FunctionType a,
Perhaps add comments explaining what happens for functions with different
optional parameter lists.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/ordered_typeset.dart (right):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:30: class
OrderedTypeSet {
Where do you enforce that this really is a set? Is that guaranteed by using the
builder?

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:32: final
Link<DartType> _head;
What is this used for? Can you find a better name?

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:47:
OrderedTypeSet extendClass(InterfaceType type) {
Please add a comment explaining what this method does.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:51:
List<Link<DartType>> list = new List<Link<DartType>>(levels+1);
Missing spaces around operator 'levels_+_1'.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:52: for (int i =
0 ; i < levels ; i++) {
No space before ';'.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:59: 
Remove empty line.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:66: int get
maxDepth => levels-1;
Missing spaces around operator.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:79: level > 0 ?
_levels[level-1] : const Link<DartType>();
Ditto.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:123:
_addAtDepth(compiler, type, maxDepth+1);
Spaces around operator.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:133:
LinkEntry<DartType> head = map[depth];
Is [head] used somewhere else than in l. 135?  If not, inline it at use site.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:162:
OrderedTypeSet toSet() {
toSet -> toTypeSet?

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:163:
List<Link<DartType>> levels = new List<Link<DartType>>(maxDepth+1);
Spaces.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:169: for (int
depth = 0 ; depth <= maxDepth ; depth++) {
No spaces before ';'.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:188: for (int
depth = 0 ; depth <= maxDepth ; depth++) {
Ditto.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/resolution/members.dart (left):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4084: *
Please restore this line.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/resolution/members.dart (right):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4094: *  
supertypes(C) = [S, I1, I2] ++ supertypes(S) ++ supertypes(I1)
Is this invariant still valid?

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4106:
OrderedTypeSetBuilder allSupertypes = new OrderedTypeSetBuilder(cls);
Could this iteration be part of the OrderedTypeSetBuilder?

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4120:
allSupertypes.add(compiler, cls.computeType(compiler));
Ditto.

https://codereview.chromium.org/52263003/diff/40001/tests/compiler/dart2js/le...
File tests/compiler/dart2js/least_upper_bound_test.dart (right):

https://codereview.chromium.org/52263003/diff/40001/tests/compiler/dart2js/le...
tests/compiler/dart2js/least_upper_bound_test.dart:149: """).then((var env) {
Remove 'var' (also in the other tests).

https://codereview.chromium.org/52263003/diff/40001/tests/language/least_uppe...
File tests/language/least_upper_bound_expansive_test.dart (right):

https://codereview.chromium.org/52263003/diff/40001/tests/language/least_uppe...
tests/language/least_upper_bound_expansive_test.dart:27: *
lub(C1<int>,N<C1<String>>)=lub(N<N<C1<int>>>,N<C1<String>>)
Please add space between arguments and around '='.

https://codereview.chromium.org/52263003/diff/40001/tests/language/least_uppe...
tests/language/least_upper_bound_expansive_test.dart:35: if (z) {
This guard against dead-code elimination is brittle.  You could use `new
DateTime.now().millisecondsSinceEpoch == 42` instead.

[Johnni Winther, 2013-11-25 13:58:27]

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/dart_types.dart (right):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/dart_types.dart:1501: int
maxCommonDepth = aClass.hierarchyDepth;
On 2013/11/21 13:29:10, karlklose wrote:
> `= min(aClass.hierarchyDepth, bClass.hierarchyDepth);`

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/dart_types.dart:1532: DartType
computeLeastUpperBoundFunctionTypes(FunctionType a,
On 2013/11/21 13:29:10, karlklose wrote:
> Perhaps add comments explaining what happens for functions with different
> optional parameter lists.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/ordered_typeset.dart (right):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:30: class
OrderedTypeSet {
On 2013/11/21 13:29:10, karlklose wrote:
> Where do you enforce that this really is a set? Is that guaranteed by using
the
> builder?

Yes. Made the default constructor private to further enforce this.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:32: final
Link<DartType> _head;
On 2013/11/21 13:29:10, karlklose wrote:
> What is this used for? Can you find a better name?

It holds the list of the types. Renamed to types (replacing the getter).

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:47:
OrderedTypeSet extendClass(InterfaceType type) {
On 2013/11/21 13:29:10, karlklose wrote:
> Please add a comment explaining what this method does.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:51:
List<Link<DartType>> list = new List<Link<DartType>>(levels+1);
On 2013/11/21 13:29:10, karlklose wrote:
> Missing spaces around operator 'levels_+_1'.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:52: for (int i =
0 ; i < levels ; i++) {
On 2013/11/21 13:29:10, karlklose wrote:
> No space before ';'.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:59: 
On 2013/11/21 13:29:10, karlklose wrote:
> Remove empty line.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:66: int get
maxDepth => levels-1;
On 2013/11/21 13:29:10, karlklose wrote:
> Missing spaces around operator.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:79: level > 0 ?
_levels[level-1] : const Link<DartType>();
On 2013/11/21 13:29:10, karlklose wrote:
> Ditto.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:123:
_addAtDepth(compiler, type, maxDepth+1);
On 2013/11/21 13:29:10, karlklose wrote:
> Spaces around operator.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:133:
LinkEntry<DartType> head = map[depth];
On 2013/11/21 13:29:10, karlklose wrote:
> Is [head] used somewhere else than in l. 135?  If not, inline it at use site.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:162:
OrderedTypeSet toSet() {
On 2013/11/21 13:29:10, karlklose wrote:
> toSet -> toTypeSet?

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:163:
List<Link<DartType>> levels = new List<Link<DartType>>(maxDepth+1);
On 2013/11/21 13:29:10, karlklose wrote:
> Spaces.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:169: for (int
depth = 0 ; depth <= maxDepth ; depth++) {
On 2013/11/21 13:29:10, karlklose wrote:
> No spaces before ';'.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/ordered_typeset.dart:188: for (int
depth = 0 ; depth <= maxDepth ; depth++) {
On 2013/11/21 13:29:10, karlklose wrote:
> Ditto.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/resolution/members.dart (left):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4084: *
On 2013/11/21 13:29:10, karlklose wrote:
> Please restore this line.

Done.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
File sdk/lib/_internal/compiler/implementation/resolution/members.dart (right):

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4094: *  
supertypes(C) = [S, I1, I2] ++ supertypes(S) ++ supertypes(I1)
On 2013/11/21 13:29:10, karlklose wrote:
> Is this invariant still valid?

Yes.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4106:
OrderedTypeSetBuilder allSupertypes = new OrderedTypeSetBuilder(cls);
On 2013/11/21 13:29:10, karlklose wrote:
> Could this iteration be part of the OrderedTypeSetBuilder?

Added a TODO.

https://codereview.chromium.org/52263003/diff/40001/sdk/lib/_internal/compile...
sdk/lib/_internal/compiler/implementation/resolution/members.dart:4120:
allSupertypes.add(compiler, cls.computeType(compiler));
On 2013/11/21 13:29:10, karlklose wrote:
> Ditto.

Done.

https://codereview.chromium.org/52263003/diff/40001/tests/compiler/dart2js/le...
File tests/compiler/dart2js/least_upper_bound_test.dart (right):

https://codereview.chromium.org/52263003/diff/40001/tests/compiler/dart2js/le...
tests/compiler/dart2js/least_upper_bound_test.dart:149: """).then((var env) {
On 2013/11/21 13:29:10, karlklose wrote:
> Remove 'var' (also in the other tests).

Done.

https://codereview.chromium.org/52263003/diff/40001/tests/language/least_uppe...
File tests/language/least_upper_bound_expansive_test.dart (right):

https://codereview.chromium.org/52263003/diff/40001/tests/language/least_uppe...
tests/language/least_upper_bound_expansive_test.dart:27: *
lub(C1<int>,N<C1<String>>)=lub(N<N<C1<int>>>,N<C1<String>>)
On 2013/11/21 13:29:10, karlklose wrote:
> Please add space between arguments and around '='.

Done.

https://codereview.chromium.org/52263003/diff/40001/tests/language/least_uppe...
tests/language/least_upper_bound_expansive_test.dart:35: if (z) {
On 2013/11/21 13:29:10, karlklose wrote:
> This guard against dead-code elimination is brittle.  You could use `new
> DateTime.now().millisecondsSinceEpoch == 42` instead.

It doesn't really matter. I don't want to run it, but any analyzer should
provide the warnings.

[Johnni Winther, 2013-11-26 08:33:11]

Committed patchset #3 manually as r30661 (presubmit successful).