Optimize subclass/subtype queries

Optimize subclass/subtype queries

BUG=
R=karlklose@google.com

Committed: https://github.com/dart-lang/sdk/commit/285400c7a73f98da3e3076038d91ddf3ecbbba9e

Reverted: https://github.com/dart-lang/sdk/commit/2affe22138c009a06be421d9f3ad3aa5d144e31e

Committed: https://github.com/dart-lang/sdk/commit/8ab89a265301b787de7093737ee3c94232338c2a

[Johnni Winther, 2016-01-26 09:35:40]

johnniwinther@google.com changed reviewers:
+ karlklose@google.com

[Johnni Winther, 2016-01-26 09:35:41]

Main changes in universe/class_set.dart

[karlklose, 2016-01-26 12:13:32]

LGTM.

https://codereview.chromium.org/1627333002/diff/20001/pkg/compiler/lib/src/un...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1627333002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:216: /// [predicate] is a applied
to subclasses if their instantiation properties
'is applied' (remove 'a'). Also in the comment below and the comments in
ClassSet.

https://codereview.chromium.org/1627333002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:249: if (!strict) {
Join the condition and set forEach = ForEach.CONTINUE in the else-branch?

[Johnni Winther, 2016-01-26 13:44:34]

Description was changed from

==========
Optimize subclass/subtype queries

BUG=
==========

to

==========
Optimize subclass/subtype queries

BUG=
R=karlklose@google.com

Committed:
https://github.com/dart-lang/sdk/commit/285400c7a73f98da3e3076038d91ddf3ecbbba9e
==========

[Johnni Winther, 2016-01-26 13:44:36]

Committed patchset #3 (id:40001) manually as
285400c7a73f98da3e3076038d91ddf3ecbbba9e (presubmit successful).

[asgerf, 2016-01-26 14:20:44]

It seems the test co19/LibTest/collection/DoubleLinkedQueue/iterator_A01_t01
broke after this landed.

[Johnni Winther, 2016-01-27 09:19:58]

Description was changed from

==========
Optimize subclass/subtype queries

BUG=
R=karlklose@google.com

Committed:
https://github.com/dart-lang/sdk/commit/285400c7a73f98da3e3076038d91ddf3ecbbba9e
==========

to

==========
Optimize subclass/subtype queries

BUG=
R=karlklose@google.com

Committed:
https://github.com/dart-lang/sdk/commit/285400c7a73f98da3e3076038d91ddf3ecbbba9e

Reverted:
https://github.com/dart-lang/sdk/commit/2affe22138c009a06be421d9f3ad3aa5d144e31e
==========

[Johnni Winther, 2016-01-27 09:20:05]

https://codereview.chromium.org/1627333002/diff/20001/pkg/compiler/lib/src/un...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1627333002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:216: /// [predicate] is a applied
to subclasses if their instantiation properties
On 2016/01/26 12:13:32, karlklose wrote:
> 'is applied' (remove 'a'). Also in the comment below and the comments in
> ClassSet.

Done.

https://codereview.chromium.org/1627333002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:249: if (!strict) {
On 2016/01/26 12:13:32, karlklose wrote:
> Join the condition and set forEach = ForEach.CONTINUE in the else-branch?

Conditions join. `forEach ??= ForEach.CONTINUE` is left after the if-statement
because I want to support that [f] returns `null`. Added a comment.

[Johnni Winther, 2016-01-27 12:26:26]

PTAL at patches after rebase

[karlklose, 2016-01-27 12:29:56]

LGTM.

[Johnni Winther, 2016-01-27 13:34:08]

Description was changed from

==========
Optimize subclass/subtype queries

BUG=
R=karlklose@google.com

Committed:
https://github.com/dart-lang/sdk/commit/285400c7a73f98da3e3076038d91ddf3ecbbba9e

Reverted:
https://github.com/dart-lang/sdk/commit/2affe22138c009a06be421d9f3ad3aa5d144e31e
==========

to

==========
Optimize subclass/subtype queries

BUG=
R=karlklose@google.com

Committed:
https://github.com/dart-lang/sdk/commit/285400c7a73f98da3e3076038d91ddf3ecbbba9e

Reverted:
https://github.com/dart-lang/sdk/commit/2affe22138c009a06be421d9f3ad3aa5d144e31e

Committed:
https://github.com/dart-lang/sdk/commit/8ab89a265301b787de7093737ee3c94232338c2a
==========

[Johnni Winther, 2016-01-27 13:34:09]

Committed patchset #6 (id:100001) manually as
8ab89a265301b787de7093737ee3c94232338c2a (presubmit successful).

[Siggi Cherem (dart-lang), 2016-02-06 00:17:26]

sigmund@google.com changed reviewers:
+ sigmund@google.com

[Siggi Cherem (dart-lang), 2016-02-06 00:17:27]

dbc

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
pkg/compiler/lib/src/universe/class_set.dart:581: forEach ??= ForEach.CONTINUE;
nit: here and elsewhere, I rather keep the variable with a single assignment and
use ?? instead, that makes it more obvious that it is a default value. In other
words:

  var x = something ?? defaultValue;

instead of 

  var x = something;
  x ??= defaultValue;

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
pkg/compiler/lib/src/universe/class_set.dart:859: enum ForEach {
naming nit: could we rename this to something that describes what this is,
rather than where it is used?

Some ideas:
- enum IterationControl { CONTINUE, STOP, SKIP_SUBCLASSES }
- enum IterationStep    { NEXT_CLASS, STOP, NEXT_SUBCLASS }

I like the latter, since the corresponding local variable names in the code
above become more readable. For example:

var nextStep =
    node.forEachSubclass(f, mask, strict: strict) ?? IterationStep.NEXT_CLASS;

if (nextStep == ForEach.NEXT_CLASS && _directSubtypes != null) {
  for (ClassHierarchyNode subclass in _directSubtypes) {
    var subStep = subclass.forEachSubclass(f, mask);
    if (subStep == IterationStep.STOP) return IterationStep.STOP;
  }
}

return nextStep;

[Siggi Cherem (dart-lang), 2016-02-09 23:40:12]

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
pkg/compiler/lib/src/universe/class_set.dart:450: bool get
hasOnlyInstantiatedSubclasses {
I was looking into something else and run into this part of the change. I think
I understand how this works now, but I wanted to confirm/double check with you.

In particular, I was thinking of this example:

  class B extends A {}
  class C extends B {}
  class D implements B {}
  main() => print([new A(), new B(), new C(), new D()]);

I expect hasOnlyInstantiatedSubclasses for `A` to be false. I believe that's the
case here because the 'directSubtypes' includes subtypes of subclasses too, so
in this case `D` is in the subtypes list of `A`'s class-set, and because of that
we'll say false here.

Is that right?

[Johnni Winther, 2016-02-10 09:32:08]

Comments addressed in https://codereview.chromium.org/1683063002

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
pkg/compiler/lib/src/universe/class_set.dart:450: bool get
hasOnlyInstantiatedSubclasses {
On 2016/02/09 23:40:12, Siggi Cherem (dart-lang) wrote:
> I was looking into something else and run into this part of the change. I
think
> I understand how this works now, but I wanted to confirm/double check with
you.
> 
> In particular, I was thinking of this example:
> 
>   class B extends A {}
>   class C extends B {}
>   class D implements B {}
>   main() => print([new A(), new B(), new C(), new D()]);
> 
> I expect hasOnlyInstantiatedSubclasses for `A` to be false. I believe that's
the
> case here because the 'directSubtypes' includes subtypes of subclasses too, so
> in this case `D` is in the subtypes list of `A`'s class-set, and because of
that
> we'll say false here.
> 
> Is that right?

Yes. The cause is that implements is transitive. The
[hasOnlyInstantiatedSubclasses] is checked to know if `subtype of A` means
`extends A`, and because of `D` we say no. We should, though, rename
[directSubtypes] to something else.

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
pkg/compiler/lib/src/universe/class_set.dart:581: forEach ??= ForEach.CONTINUE;
On 2016/02/06 00:17:26, Siggi Cherem (dart-lang) wrote:
> nit: here and elsewhere, I rather keep the variable with a single assignment
and
> use ?? instead, that makes it more obvious that it is a default value. In
other
> words:
> 
>   var x = something ?? defaultValue;
> 
> instead of 
> 
>   var x = something;
>   x ??= defaultValue;

Will do. Code motion caused this ;-)

https://codereview.chromium.org/1627333002/diff/100001/pkg/compiler/lib/src/u...
pkg/compiler/lib/src/universe/class_set.dart:859: enum ForEach {
On 2016/02/06 00:17:26, Siggi Cherem (dart-lang) wrote:
> naming nit: could we rename this to something that describes what this is,
> rather than where it is used?
> 
> Some ideas:
> - enum IterationControl { CONTINUE, STOP, SKIP_SUBCLASSES }
> - enum IterationStep    { NEXT_CLASS, STOP, NEXT_SUBCLASS }
> 
> I like the latter, since the corresponding local variable names in the code
> above become more readable. For example:
> 
> var nextStep =
>     node.forEachSubclass(f, mask, strict: strict) ?? IterationStep.NEXT_CLASS;
> 
> if (nextStep == ForEach.NEXT_CLASS && _directSubtypes != null) {
>   for (ClassHierarchyNode subclass in _directSubtypes) {
>     var subStep = subclass.forEachSubclass(f, mask);
>     if (subStep == IterationStep.STOP) return IterationStep.STOP;
>   }
> }
> 
> return nextStep;

If find the latter confusing but like enum class name.