RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

[Erik Österlund]

On Fri, 19 Feb 2021 15:20:50 GMT, Vladimir Ivanov <vlivanov at openjdk.org> wrote:

>> src/hotspot/share/oops/instanceKlass.hpp line 1461:
>> 
>>> 1459:     if (_visit_subclasses && _current->subklass() != NULL) {
>>> 1460:       _current = _current->subklass();
>>> 1461:       return; // visit next subclass
>> 
>> _visit_subclasses is initially true in the constructor. That seems to imply that after the first call to next(), we will take this path, just returning the subklass() without walking the siblings. The _visit_subclasses variable is never mutated away from the true state at all if it was already true, until we get to the bottom of the class hierarchy. That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal. Therefore, it looks to me like the use of the _visit_subclasses variable needs to be looked over a bit in this function in general, unless I misunderstood something.
>
> `_visit_subclasses` is mutated only from the outside (there's `ClassHierarchyIterator::skip_subclasses()` specificlaly for that) when user code needs to ignore subclasses:
> 
> https://github.com/openjdk/jdk/blob/ae78e51e4248c2ccfa73c772fb1db1baad2c2903/src/hotspot/share/code/dependencies.cpp#L1359:
> 
>   for (ClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
>     Klass* sub = iter.klass();
> 
>     // Do not report participant types.
>     if (is_participant(sub)) {
>       // Walk beneath a participant only when it doesn't hide witnesses.
>       if (participants_hide_witnesses) {
>         iter.skip_subclasses();
>       }
> 
> And `_visit_subclasses` is cleared to the initial state on the very next call to `next()`.
> 
>> That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal.
> 
> Yes, that's the intended behavior. Why do think it doesn't obey depth-first order? `next_sibling()` points to a class on the same level of class hierarchy.

Okay, I see. So you traverse all the way down, following the subclass links until you can't go further, and then traverse the siblings on the way up. That makes sense. Thanks for the explanation.

-------------

PR: https://git.openjdk.java.net/jdk/pull/2630