1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// Copyright 2014 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
import 'package:flutter/foundation.dart';
import 'package:flutter/semantics.dart';
import 'package:flutter/widgets.dart';
/// Provides an iterable that efficiently returns all the [Element]s
/// rooted at the given [Element]. See [CachingIterable] for details.
///
/// This function must be called again if the tree changes. You cannot
/// call this function once, then reuse the iterable after having
/// changed the state of the tree, because the iterable returned by
/// this function caches the results and only walks the tree once.
///
/// The same applies to any iterable obtained indirectly through this
/// one, for example the results of calling `where` on this iterable
/// are also cached.
Iterable<Element> collectAllElementsFrom(
Element rootElement, {
required bool skipOffstage,
}) {
return CachingIterable<Element>(_DepthFirstElementTreeIterator(rootElement, !skipOffstage));
}
/// Provides an iterable that efficiently returns all the [SemanticsNode]s
/// rooted at the given [SemanticsNode]. See [CachingIterable] for details.
///
/// By default, this will traverse the semantics tree in semantic traversal
/// order, but the traversal order can be changed by passing in a different
/// value to `order`.
///
/// This function must be called again if the semantics change. You cannot call
/// this function once, then reuse the iterable after having changed the state
/// of the tree, because the iterable returned by this function caches the
/// results and only walks the tree once.
///
/// The same applies to any iterable obtained indirectly through this
/// one, for example the results of calling `where` on this iterable
/// are also cached.
Iterable<SemanticsNode> collectAllSemanticsNodesFrom(
SemanticsNode root, {
DebugSemanticsDumpOrder order = DebugSemanticsDumpOrder.traversalOrder,
}) {
return CachingIterable<SemanticsNode>(_DepthFirstSemanticsTreeIterator(root, order));
}
/// Provides a recursive, efficient, depth first search of a tree.
///
/// This iterator executes a depth first search as an iterable, and iterates in
/// a left to right order:
///
/// 1
/// / \
/// 2 3
/// / \ / \
/// 4 5 6 7
///
/// Will iterate in order 2, 4, 5, 3, 6, 7. The given root element is not
/// included in the traversal.
abstract class _DepthFirstTreeIterator<ItemType> implements Iterator<ItemType> {
_DepthFirstTreeIterator(ItemType root) {
_fillStack(_collectChildren(root));
}
@override
ItemType get current => _current!;
late ItemType _current;
final List<ItemType> _stack = <ItemType>[];
@override
bool moveNext() {
if (_stack.isEmpty) {
return false;
}
_current = _stack.removeLast();
_fillStack(_collectChildren(_current));
return true;
}
/// Fills the stack in such a way that the next element of a depth first
/// traversal is easily and efficiently accessible when calling `moveNext`.
void _fillStack(List<ItemType> children) {
// We reverse the list of children so we don't have to do use expensive
// `insert` or `remove` operations, and so the order of the traversal
// is depth first when built lazily through the iterator.
//
// This is faster than `_stack.addAll(children.reversed)`, presumably since
// we don't actually care about maintaining an iteration pointer.
while (children.isNotEmpty) {
_stack.add(children.removeLast());
}
}
/// Collect the children from [root] in the order they are expected to traverse.
List<ItemType> _collectChildren(ItemType root);
}
/// [Element.visitChildren] does not guarantee order, but does guarantee stable
/// order. This iterator also guarantees stable order, and iterates in a left
/// to right order:
///
/// 1
/// / \
/// 2 3
/// / \ / \
/// 4 5 6 7
///
/// Will iterate in order 2, 4, 5, 3, 6, 7.
///
/// Performance is important here because this class is on the critical path
/// for flutter_driver and package:integration_test performance tests.
/// Performance is measured in the all_elements_bench microbenchmark.
/// Any changes to this implementation should check the before and after numbers
/// on that benchmark to avoid regressions in general performance test overhead.
///
/// If we could use RTL order, we could save on performance, but numerous tests
/// have been written (and developers clearly expect) that LTR order will be
/// respected.
class _DepthFirstElementTreeIterator extends _DepthFirstTreeIterator<Element> {
_DepthFirstElementTreeIterator(super.root, this.includeOffstage);
final bool includeOffstage;
@override
List<Element> _collectChildren(Element root) {
final List<Element> children = <Element>[];
if (includeOffstage) {
root.visitChildren(children.add);
} else {
root.debugVisitOnstageChildren(children.add);
}
return children;
}
}
/// Iterates the semantics tree starting at the given `root`.
///
/// This will iterate in the same order expected from accessibility services,
/// so the results can be used to simulate the same traversal the engine will
/// make. The results are not filtered based on flags or visibility, so they
/// will need to be further filtered to fully simulate an accessibility service.
class _DepthFirstSemanticsTreeIterator extends _DepthFirstTreeIterator<SemanticsNode> {
_DepthFirstSemanticsTreeIterator(super.root, this.order);
final DebugSemanticsDumpOrder order;
@override
List<SemanticsNode> _collectChildren(SemanticsNode root) {
return root.debugListChildrenInOrder(order);
}
}