Add SubclassNode to prepare for optimized queries on ClassWorld.

Add SubclassNode to prepare for optimized queries on ClassWorld.

BUG=
R=karlklose@google.com

Committed: https://github.com/dart-lang/sdk/commit/2526ef6b4bd5f2185fba3be067bcb3444c3c635d

[Johnni Winther, 2015-07-14 11:24:39]

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

[Siggi Cherem (dart-lang), 2015-07-14 23:51:06]

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

[Siggi Cherem (dart-lang), 2015-07-14 23:51:07]

nice

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:16: class SubclassNode {
This is a hard one name :) - Somehow SubclassNode sounds to me a bit like this
is a node representing a subclass.

A possible idea is to use the term "class hierarchy tree" to refer to the
subclass relation, so we could use: ClassHierarchyNode or
ClassHierarchyTreeNode. thoughts?

Similarly - maybe rename the file and library name from class_set to
class_hierarchy?

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:30: /// For instance `B` and `C`
but _not_ `A` in:
I was expecting `A` would be true in this case (since B & C extend from it)?

Or did you mean to have the following code instead?

  class A {}
  class B {} // no extends A
  class C extends B {}
  main() => new C();

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:96: /// Iterator for subclasses of
a [SubclassNode].
it might be worth mentioning here or in the sublasses functions above that the
iterable will return the classes in a DFS fashion in pre-order (top-down
depth-first).

BTW - I wonder if there is an order that makes more sense for our algorithms, or
if we want to introduce more than one order? (would some order let us stop
iterating earlier?)

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:130: if
(currentNode.hasDirectSubclasses) {
it would be nice to only have this part of the logic that uses
`directSubclasses` in a single place. How about making moveNext only initialize
the stack with `root` and let _findNext add the rest?

For example:

bool moveNext() {
  if (stack == null) {
    // first call to moveNext
    if (root == null) return false;
    var pending = const Link<SubclassNode>().prepend(root);
    stack = (const Link<...>()).prepend(pending);
  }
  return _findNext();
}

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:145: bool findNext() {
make private?

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:161: stack =
stack.prepend(currentNode.directSubclasses);
What do you think about flattening the list here (keep a stack of nodes, rather
than a stack with lists of nodes)?

It would probably make the iterator invariant a bit simpler, and it seems the
cost is very similar to the current algorithm:

- current algorithm: 1 operation to append children, 2 * n operations later (1
to pop the a child, and 1 push back the pending children)

- w/flattening: n operations upfront to append children, n operations later (1
to pop each child)

where `n` is just the number of directSubclasses on a node (not the total number
of descendants)

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:170: bool isValid(SubclassNode
node) {
make private too?

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/world....
File pkg/compiler/lib/src/world.dart (right):

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/world....
pkg/compiler/lib/src/world.dart:350: SubclassNode
createNodeForClass(ClassElement cls,
nit, rename to: `ensureNodeForClass` (that helps convey that the boolean
properties might be updated).

[Johnni Winther, 2015-07-15 08:55:09]

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:16: class SubclassNode {
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> This is a hard one name :) - Somehow SubclassNode sounds to me a bit like this
> is a node representing a subclass.
> 
> A possible idea is to use the term "class hierarchy tree" to refer to the
> subclass relation, so we could use: ClassHierarchyNode or
> ClassHierarchyTreeNode. thoughts?
> 
> Similarly - maybe rename the file and library name from class_set to
> class_hierarchy?

ClassHierarchyNode or ClassHierarchyTreeNode it is. The filename is in
anticipation that it'll contains Set-like classes for subclass and subtype
relations build upon ClassHierarchy(Tree)Node.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:30: /// For instance `B` and `C`
but _not_ `A` in:
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> I was expecting `A` would be true in this case (since B & C extend from it)?
> 
> Or did you mean to have the following code instead?
> 
>   class A {}
>   class B {} // no extends A
>   class C extends B {}
>   main() => new C();

It should have been: `A` and `B` but _not_ `C`

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:96: /// Iterator for subclasses of
a [SubclassNode].
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> it might be worth mentioning here or in the sublasses functions above that the
> iterable will return the classes in a DFS fashion in pre-order (top-down
> depth-first).
> 
> BTW - I wonder if there is an order that makes more sense for our algorithms,
or
> if we want to introduce more than one order? (would some order let us stop
> iterating earlier?)

The iterator is an intermediate step towards the intended solution: Currently we
use strictSubclassesOf and strictSubtypesOf which return Iterable. 

This class for providing such functionality. Long-term users of ClassWorld
should not have access to such brute-force iteration through classes but more
high level function that choose the order and terminate based on the intention
of the query. 

For instance, for computing whether a  noSuchMethod stub is needed for a method
on a type-mask we run through all classes (using strictSubclassesOf or
strictSubtypesOf, depending on the maks) and for each run up the superclass
chain to determinate if that class need a stub for the method. This means that
we for instance test Object once for each class in the iterable. What we should
do instead is to run through superclasses first and skip subtrees when a method
is found. For instance checking the need for a noSuchMethod stub for 'toString'
will then only require a check on Object and nothing more.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:130: if
(currentNode.hasDirectSubclasses) {
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> it would be nice to only have this part of the logic that uses
> `directSubclasses` in a single place. How about making moveNext only
initialize
> the stack with `root` and let _findNext add the rest?
> 
> For example:
> 
> bool moveNext() {
>   if (stack == null) {
>     // first call to moveNext
>     if (root == null) return false;
>     var pending = const Link<SubclassNode>().prepend(root);
>     stack = (const Link<...>()).prepend(pending);
>   }
>   return _findNext();
> }

Good idea!

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:161: stack =
stack.prepend(currentNode.directSubclasses);
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> What do you think about flattening the list here (keep a stack of nodes,
rather
> than a stack with lists of nodes)?
> 
> It would probably make the iterator invariant a bit simpler, and it seems the
> cost is very similar to the current algorithm:
> 
> - current algorithm: 1 operation to append children, 2 * n operations later (1
> to pop the a child, and 1 push back the pending children)
> 
> - w/flattening: n operations upfront to append children, n operations later (1
> to pop each child)
> 
> where `n` is just the number of directSubclasses on a node (not the total
number
> of descendants)

I'll give it a try.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:170: bool isValid(SubclassNode
node) {
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> make private too?

Will do.

[Johnni Winther, 2015-07-20 12:50:57]

Ping

[Siggi Cherem (dart-lang), 2015-07-20 15:19:52]

Hey Johnni - did you mean to upload a new patch?

[Johnni Winther, 2015-07-21 12:11:01]

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
File pkg/compiler/lib/src/universe/class_set.dart (right):

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:16: class SubclassNode {
On 2015/07/15 08:55:08, Johnni Winther wrote:
> On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> > This is a hard one name :) - Somehow SubclassNode sounds to me a bit like
this
> > is a node representing a subclass.
> > 
> > A possible idea is to use the term "class hierarchy tree" to refer to the
> > subclass relation, so we could use: ClassHierarchyNode or
> > ClassHierarchyTreeNode. thoughts?
> > 
> > Similarly - maybe rename the file and library name from class_set to
> > class_hierarchy?
> 
> ClassHierarchyNode or ClassHierarchyTreeNode it is. The filename is in
> anticipation that it'll contains Set-like classes for subclass and subtype
> relations build upon ClassHierarchy(Tree)Node.

Done.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:30: /// For instance `B` and `C`
but _not_ `A` in:
On 2015/07/15 08:55:08, Johnni Winther wrote:
> On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> > I was expecting `A` would be true in this case (since B & C extend from it)?
> > 
> > Or did you mean to have the following code instead?
> > 
> >   class A {}
> >   class B {} // no extends A
> >   class C extends B {}
> >   main() => new C();
> 
> It should have been: `A` and `B` but _not_ `C`

Done.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:130: if
(currentNode.hasDirectSubclasses) {
On 2015/07/15 08:55:09, Johnni Winther wrote:
> On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> > it would be nice to only have this part of the logic that uses
> > `directSubclasses` in a single place. How about making moveNext only
> initialize
> > the stack with `root` and let _findNext add the rest?
> > 
> > For example:
> > 
> > bool moveNext() {
> >   if (stack == null) {
> >     // first call to moveNext
> >     if (root == null) return false;
> >     var pending = const Link<SubclassNode>().prepend(root);
> >     stack = (const Link<...>()).prepend(pending);
> >   }
> >   return _findNext();
> > }
> 
> Good idea!

Done.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:145: bool findNext() {
On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> make private?

Done.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:161: stack =
stack.prepend(currentNode.directSubclasses);
On 2015/07/15 08:55:08, Johnni Winther wrote:
> On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> > What do you think about flattening the list here (keep a stack of nodes,
> rather
> > than a stack with lists of nodes)?
> > 
> > It would probably make the iterator invariant a bit simpler, and it seems
the
> > cost is very similar to the current algorithm:
> > 
> > - current algorithm: 1 operation to append children, 2 * n operations later
(1
> > to pop the a child, and 1 push back the pending children)
> > 
> > - w/flattening: n operations upfront to append children, n operations later
(1
> > to pop each child)
> > 
> > where `n` is just the number of directSubclasses on a node (not the total
> number
> > of descendants)
> 
> I'll give it a try.

Done.

https://codereview.chromium.org/1234053002/diff/1/pkg/compiler/lib/src/univer...
pkg/compiler/lib/src/universe/class_set.dart:170: bool isValid(SubclassNode
node) {
On 2015/07/15 08:55:08, Johnni Winther wrote:
> On 2015/07/14 23:51:07, Siggi Cherem (dart-lang) wrote:
> > make private too?
> 
> Will do.

Done.

[karlklose, 2015-07-21 12:47:21]

LGTM.

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

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:38: /// The node for the direct
subclasses of [cls].
'node' -> 'nodes'.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:39: Link<ClassHierarchyNode>
_directSubclasses = const Link<ClassHierarchyNode>();
Is this a performance optimization?

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:54: bool get hasDirectSubclasses =>
!_directSubclasses.isEmpty;
Are these two getters still used?

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:131: if (root == null) return
false;
How about letting the ClassHierarchyNodeIterable cosntructor throw instead? Or
is this behavior desirable?

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
File pkg/compiler/lib/src/world.dart (right):

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:153: /// [cls] possibly including [cls] itself.
Maybe extend to '... including [cls] itself, if it live.'

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:155: ClassHierarchyNode subclasses =
_classHierarchyNodes[cls.declaration];
'subclasses' -> 'hierarchy'?

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:173: /// _not_ including [cls] if it is live.
Remove 'if it is live', it is implied.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:350: ClassHierarchyNode createNodeForClass(
'create[Class]HierarchyNodeForClass'?

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:370: return node;
Is there a contract to only call this method for a class that is eitehr directly
or indirectly instantiated? Then please add an assert.

Otherwise, we can have the situation, that we call it with both booleans false
first, which creates the node for the superclass with
indirectlyInstantiated=false and later updates would not change the flag of the
superclass.

[Johnni Winther, 2015-07-21 14:22:01]

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

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:38: /// The node for the direct
subclasses of [cls].
On 2015/07/21 12:47:21, karlklose wrote:
> 'node' -> 'nodes'.

Done.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:39: Link<ClassHierarchyNode>
_directSubclasses = const Link<ClassHierarchyNode>();
On 2015/07/21 12:47:21, karlklose wrote:
> Is this a performance optimization?

To use Link, yes. May not be worthwhile. Will change to List if it becomes an
obstacle.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:54: bool get hasDirectSubclasses =>
!_directSubclasses.isEmpty;
On 2015/07/21 12:47:21, karlklose wrote:
> Are these two getters still used?

No, removing them.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/un...
pkg/compiler/lib/src/universe/class_set.dart:131: if (root == null) return
false;
On 2015/07/21 12:47:21, karlklose wrote:
> How about letting the ClassHierarchyNodeIterable cosntructor throw instead? Or
> is this behavior desirable?

Throwing instead.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
File pkg/compiler/lib/src/world.dart (right):

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:153: /// [cls] possibly including [cls] itself.
On 2015/07/21 12:47:21, karlklose wrote:
> Maybe extend to '... including [cls] itself, if it live.'

Done.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:155: ClassHierarchyNode subclasses =
_classHierarchyNodes[cls.declaration];
On 2015/07/21 12:47:21, karlklose wrote:
> 'subclasses' -> 'hierarchy'?

Done.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:173: /// _not_ including [cls] if it is live.
On 2015/07/21 12:47:21, karlklose wrote:
> Remove 'if it is live', it is implied.

Done.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:350: ClassHierarchyNode createNodeForClass(
On 2015/07/21 12:47:21, karlklose wrote:
> 'create[Class]HierarchyNodeForClass'?

Done.

https://codereview.chromium.org/1234053002/diff/20001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:370: return node;
On 2015/07/21 12:47:21, karlklose wrote:
> Is there a contract to only call this method for a class that is eitehr
directly
> or indirectly instantiated? Then please add an assert.
> 
> Otherwise, we can have the situation, that we call it with both booleans false
> first, which creates the node for the superclass with
> indirectlyInstantiated=false and later updates would not change the flag of
the
> superclass.

Moved into [populate] and assertion added.

[Johnni Winther, 2015-07-21 14:30:24]

Committed patchset #3 (id:40001) manually as
2526ef6b4bd5f2185fba3be067bcb3444c3c635d (presubmit successful).

[Siggi Cherem (dart-lang), 2015-07-21 14:35:09]

lgtm