Fixes https://bugs.openjdk.org/browse/JDK-8181411 and
https://bugs.openjdk.org/browse/JDK-8380308
`TreeUtil.getItem` is used pervasively throughout `TreeView` and
`TreeTableView`, specifically `getTreeItem`. This performs a depth-first-search
(DFS) of the tree, and caches the target item. This is ok for random access,
but is slow for sequential access with a cold cache, as each subsequent call to
`getTreeItem` starts a new DFS from the root of the tree. For `selectAll`, this
has O(N^2) time complexity.
This PR adds a stateful iterator that resumes the DFS from the previously
retrieved item, and caches each item during the traversal. This reduces the
time complexity `selectAll` case to O(N).
This change revealed an otherwise harmless bug in the order of event handling
in the `invalidated()` method of the root property.
Current behavior:
1. `expandedItemCountChangeEvent` fires
2. Focus model listener fires
3. Focus model calls `getTreeItem`, `expandedItemCountDirty` is false, cache
miss, correct item returned
5. `rootEvent` fires, sets `expandedItemCountDirty = true`
The correct behavior would be to set `expandedItemCountDirty = true` before the
focus model calls getTreeItem. This works because any item that is not in the
cache triggers a full DFS from the root, which is always valid.
This PR:
1. `expandedItemCountChangeEvent` fires
2. `rootEvent` fires, sets `expandedItemCountDirty = true`
3. Focus model listener fires
4. Focus model calls `getTreeItem`, `expandedItemCountDirty` is true, iterator
resets, correct item returned
This is fixed by using `expandedItemCountChangeEvent` instead of the super type
`treeNotificationEvent`. The subclass event types are processed before their
super counterparts, regardless of registration order. Now that they are the
same type, the order is correct.
This behavior is already covered (and is motivated) by `TreeTableViewTest >
test_rt17522_focusShouldMoveWhenItemRemovedBeforeFocusIndex_1()` and
`TreeTableViewTest >
test_rt17522_focusShouldMoveWhenItemAddedAtFocusIndex_1()`.
┌─────────┬───────────────────┬──────────────────┬────────────────────────┬───────────────────────┐
│ Items │ TreeView (before) │ TreeView (after) │ TreeTableView (before) │
TreeTableView (after) │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 64 │ 1ms │ 1ms │ 2ms │
2ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 128 │ 0ms │ 0ms │ 0ms │
0ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 256 │ 0ms │ 0ms │ 0ms │
1ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 512 │ 1ms │ 0ms │ 2ms │
1ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 1,024 │ 3ms │ 0ms │ 2ms │
1ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 2,048 │ 2ms │ 1ms │ 5ms │
1ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 4,096 │ 10ms │ 1ms │ 14ms │
3ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 8,192 │ 45ms │ 2ms │ 58ms │
5ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 16,384 │ 285ms │ 2ms │ 336ms │
6ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 32,768 │ 1,306ms │ 4ms │ 1,742ms │
12ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 65,536 │ 6,011ms │ 5ms │ 6,416ms │
16ms │
├─────────┼───────────────────┼──────────────────┼────────────────────────┼───────────────────────┤
│ 131,072 │ 34,092ms │ 8ms │ 33,174ms │
63ms │
└─────────┴───────────────────┴──────────────────┴────────────────────────┴───────────────────────┘
-------------
Commit messages:
- use updated method for dfs iterator
- apply analogous changes to TreeView
- clean up iterator
- Merge branch 'openjdk:master' into 8181411-treetableview
- Merge branch 'openjdk:master' into 8181411-treetableview
- minor cleanup of iterator
- use updated name of iterator
- use persistent dfs iterator to efficiently traverse and cache tree items;
use specific event for cache invalidation to fix focus issues
- add dfs treeitem iterator
Changes: https://git.openjdk.org/jfx/pull/2142/files
Webrev: https://webrevs.openjdk.org/?repo=jfx&pr=2142&range=00
Issue: https://bugs.openjdk.org/browse/JDK-8181411
Stats: 138 lines in 3 files changed: 80 ins; 31 del; 27 mod
Patch: https://git.openjdk.org/jfx/pull/2142.diff
Fetch: git fetch https://git.openjdk.org/jfx.git pull/2142/head:pull/2142
PR: https://git.openjdk.org/jfx/pull/2142
