Semantic hit test order for Slivers (#11792)

* Semantic hit test order for Slivers

* ++

* fix double space

* refactoring

* fix test

* comment fix

* tests

* remove accidental debugDumpSemanticsTree

* review comments

* fix button
diff --git a/packages/flutter/lib/src/rendering/binding.dart b/packages/flutter/lib/src/rendering/binding.dart
index b323c97..39a1937 100644
--- a/packages/flutter/lib/src/rendering/binding.dart
+++ b/packages/flutter/lib/src/rendering/binding.dart
@@ -99,8 +99,13 @@
     );
 
     registerSignalServiceExtension(
-      name: 'debugDumpSemanticsTree',
-      callback: () { debugDumpSemanticsTree(); return debugPrintDone; }
+      name: 'debugDumpSemanticsTreeInTraversalOrder',
+      callback: () { debugDumpSemanticsTree(DebugSemanticsDumpOrder.traversal); return debugPrintDone; }
+    );
+
+    registerSignalServiceExtension(
+        name: 'debugDumpSemanticsTreeInInverseHitTestOrder',
+        callback: () { debugDumpSemanticsTree(DebugSemanticsDumpOrder.inverseHitTest); return debugPrintDone; }
     );
   }
 
@@ -319,9 +324,12 @@
 
 /// Prints a textual representation of the entire semantics tree.
 /// This will only work if there is a semantics client attached.
-/// Otherwise, the tree is empty and this will print "null".
-void debugDumpSemanticsTree() {
-  debugPrint(RendererBinding.instance?.renderView?.debugSemantics?.toStringDeep() ?? 'Semantics not collected.');
+/// Otherwise, a notice that no semantics are available will be printed.
+///
+/// The order in which the children of a [SemanticsNode] will be printed is
+/// controlled by the [childOrder] parameter.
+void debugDumpSemanticsTree(DebugSemanticsDumpOrder childOrder) {
+  debugPrint(RendererBinding.instance?.renderView?.debugSemantics?.toStringDeep(childOrder) ?? 'Semantics not collected.');
 }
 
 /// A concrete binding for applications that use the Rendering framework
diff --git a/packages/flutter/lib/src/rendering/debug.dart b/packages/flutter/lib/src/rendering/debug.dart
index 28002de..886b867 100644
--- a/packages/flutter/lib/src/rendering/debug.dart
+++ b/packages/flutter/lib/src/rendering/debug.dart
@@ -11,6 +11,23 @@
 // Any changes to this file should be reflected in the debugAssertAllRenderVarsUnset()
 // function below.
 
+/// Used by [debugDumpSemanticsTree] to specify the order in which child nodes
+/// are printed.
+enum DebugSemanticsDumpOrder {
+  /// Print nodes in inverse hit test order.
+  ///
+  /// In inverse hit test order, the last child of a [SemanticsNode] will be
+  /// asked first if it wants to respond to a user's interaction, followed by
+  /// the second last, etc. until a taker is found.
+  inverseHitTest,
+
+  /// Print nodes in traversal order.
+  ///
+  /// Traversal order defines how the user can move the accessibility focus from
+  /// one node to another.
+  traversal,
+}
+
 const HSVColor _kDebugDefaultRepaintColor = const HSVColor.fromAHSV(0.4, 60.0, 1.0, 1.0);
 
 /// Causes each RenderBox to paint a box around its bounds, and some extra
diff --git a/packages/flutter/lib/src/rendering/proxy_box.dart b/packages/flutter/lib/src/rendering/proxy_box.dart
index 0351502..1faa3db 100644
--- a/packages/flutter/lib/src/rendering/proxy_box.dart
+++ b/packages/flutter/lib/src/rendering/proxy_box.dart
@@ -2981,7 +2981,7 @@
       super.assembleSemanticsNode(node, children);
       return;
     }
-    
+
     _innerNode ??= new SemanticsNode(handler: this, showOnScreen: showOnScreen);
     _innerNode
       ..wasAffectedByClip = node.wasAffectedByClip
@@ -2989,7 +2989,7 @@
 
     semanticsAnnotator(_innerNode);
 
-    final List<SemanticsNode> excluded = <SemanticsNode>[];
+    final List<SemanticsNode> excluded = <SemanticsNode>[_innerNode];
     final List<SemanticsNode> included = <SemanticsNode>[];
     for (SemanticsNode child in children) {
       if (child.hasTag(excludeFromScrolling))
@@ -2997,7 +2997,6 @@
       else
         included.add(child);
     }
-    excluded.add(_innerNode);
     node.addChildren(excluded);
     _innerNode.addChildren(included);
     _innerNode.finalizeChildren();
diff --git a/packages/flutter/lib/src/rendering/semantics.dart b/packages/flutter/lib/src/rendering/semantics.dart
index c63346a..f65e447 100644
--- a/packages/flutter/lib/src/rendering/semantics.dart
+++ b/packages/flutter/lib/src/rendering/semantics.dart
@@ -10,6 +10,7 @@
 import 'package:flutter/painting.dart';
 import 'package:vector_math/vector_math_64.dart';
 
+import 'debug.dart';
 import 'node.dart';
 
 export 'dart:ui' show SemanticsAction;
@@ -391,11 +392,13 @@
 
   /// Append the given children as children of this node.
   ///
+  /// Children must be added in inverse hit test order (i.e. paint order).
+  ///
   /// The [finalizeChildren] method must be called after all children have been
   /// added.
-  void addChildren(Iterable<SemanticsNode> children) {
+  void addChildren(Iterable<SemanticsNode> childrenInInverseHitTestOrder) {
     _newChildren ??= <SemanticsNode>[];
-    _newChildren.addAll(children);
+    _newChildren.addAll(childrenInInverseHitTestOrder);
     // we do the asserts afterwards because children is an Iterable
     // and doing the asserts before would mean the behavior is
     // different in checked mode vs release mode (if you walk an
@@ -417,6 +420,7 @@
     });
   }
 
+  /// Contains the children in inverse hit test order (i.e. paint order).
   List<SemanticsNode> _children;
 
   /// Whether this node has a non-zero number of children.
@@ -485,6 +489,17 @@
         }
       }
     }
+    if (!sawChange && _children != null) {
+      assert(_newChildren != null);
+      assert(_newChildren.length == _children.length);
+      // Did the order change?
+      for (int i = 0; i < _children.length; i++) {
+        if (_children[i].id != _newChildren[i].id) {
+          sawChange = true;
+          break;
+        }
+      }
+    }
     final List<SemanticsNode> oldChildren = _children;
     _children = _newChildren;
     oldChildren?.clear();
@@ -685,20 +700,47 @@
   }
 
   /// Returns a string representation of this node and its descendants.
-  String toStringDeep([String prefixLineOne = '', String prefixOtherLines = '']) {
+  ///
+  /// The order in which the children of the [SemanticsNode] will be printed is
+  /// controlled by the [childOrder] parameter.
+  String toStringDeep(DebugSemanticsDumpOrder childOrder, [
+    String prefixLineOne = '',
+    String prefixOtherLines = ''
+  ]) {
+    assert(childOrder != null);
     final StringBuffer result = new StringBuffer()
       ..write(prefixLineOne)
       ..write(this)
       ..write('\n');
     if (_children != null && _children.isNotEmpty) {
-      for (int index = 0; index < _children.length - 1; index += 1) {
-        final SemanticsNode child = _children[index];
-        result.write(child.toStringDeep("$prefixOtherLines \u251C", "$prefixOtherLines \u2502"));
+      final List<SemanticsNode> childrenInOrder = _getChildrenInOrder(childOrder);
+      for (int index = 0; index < childrenInOrder.length - 1; index += 1) {
+        final SemanticsNode child = childrenInOrder[index];
+        result.write(child.toStringDeep(childOrder, "$prefixOtherLines \u251C", "$prefixOtherLines \u2502"));
       }
-      result.write(_children.last.toStringDeep("$prefixOtherLines \u2514", "$prefixOtherLines  "));
+      result.write(childrenInOrder.last.toStringDeep(childOrder, "$prefixOtherLines \u2514", "$prefixOtherLines  "));
     }
     return result.toString();
   }
+
+  Iterable<SemanticsNode> _getChildrenInOrder(DebugSemanticsDumpOrder childOrder) {
+    assert(childOrder != null);
+    switch(childOrder) {
+      case DebugSemanticsDumpOrder.traversal:
+        return new List<SemanticsNode>.from(_children)..sort(_geometryComparator);
+      case DebugSemanticsDumpOrder.inverseHitTest:
+        return _children;
+    }
+    assert(false);
+    return null;
+  }
+
+  static int _geometryComparator(SemanticsNode a, SemanticsNode b) {
+    final Rect rectA = MatrixUtils.transformRect(a.transform, a.rect);
+    final Rect rectB = MatrixUtils.transformRect(b.transform, b.rect);
+    final int top = rectA.top.compareTo(rectB.top);
+    return top == 0 ? rectA.left.compareTo(rectB.left) : top;
+  }
 }
 
 /// Owns [SemanticsNode] objects and notifies listeners of changes to the
diff --git a/packages/flutter/lib/src/rendering/viewport.dart b/packages/flutter/lib/src/rendering/viewport.dart
index 3555c61..7e4d9bc 100644
--- a/packages/flutter/lib/src/rendering/viewport.dart
+++ b/packages/flutter/lib/src/rendering/viewport.dart
@@ -94,6 +94,14 @@
     node.addTag(RenderSemanticsGestureHandler.useTwoPaneSemantics);
   }
 
+  @override
+  void visitChildrenForSemantics(RenderObjectVisitor visitor) {
+    for (RenderSliver sliver in childrenInPaintOrder) {
+      if (sliver.geometry.paintExtent != 0)
+        visitor(sliver);
+    }
+  }
+
   /// The direction in which the [SliverConstraints.scrollOffset] increases.
   ///
   /// For example, if the [axisDirection] is [AxisDirection.down], a scroll
diff --git a/packages/flutter/test/foundation/service_extensions_test.dart b/packages/flutter/test/foundation/service_extensions_test.dart
index f5a79a6..7da776d 100644
--- a/packages/flutter/test/foundation/service_extensions_test.dart
+++ b/packages/flutter/test/foundation/service_extensions_test.dart
@@ -178,11 +178,21 @@
     console.clear();
   });
 
-  test('Service extensions - debugDumpSemanticsTree', () async {
+  test('Service extensions - debugDumpSemanticsTreeInTraversalOrder', () async {
     Map<String, String> result;
 
     await binding.doFrame();
-    result = await binding.testExtension('debugDumpSemanticsTree', <String, String>{});
+    result = await binding.testExtension('debugDumpSemanticsTreeInTraversalOrder', <String, String>{});
+    expect(result, <String, String>{});
+    expect(console, <String>['Semantics not collected.']);
+    console.clear();
+  });
+
+  test('Service extensions - debugDumpSemanticsTreeInInverseHitTestOrder', () async {
+    Map<String, String> result;
+
+    await binding.doFrame();
+    result = await binding.testExtension('debugDumpSemanticsTreeInInverseHitTestOrder', <String, String>{});
     expect(result, <String, String>{});
     expect(console, <String>['Semantics not collected.']);
     console.clear();
@@ -482,7 +492,7 @@
   test('Service extensions - posttest', () async {
     // If you add a service extension... TEST IT! :-)
     // ...then increment this number.
-    expect(binding.extensions.length, 16);
+    expect(binding.extensions.length, 17);
 
     expect(console, isEmpty);
     debugPrint = debugPrintThrottled;
diff --git a/packages/flutter/test/rendering/semantics_test.dart b/packages/flutter/test/rendering/semantics_test.dart
index baad951..64f49a6 100644
--- a/packages/flutter/test/rendering/semantics_test.dart
+++ b/packages/flutter/test/rendering/semantics_test.dart
@@ -90,8 +90,6 @@
 
       expectedActions = SemanticsAction.tap.index | SemanticsAction.longPress.index | SemanticsAction.scrollDown.index | SemanticsAction.scrollRight.index;
       expect(root.debugSemantics.getSemanticsData().actions, expectedActions);
-
-      debugDumpSemanticsTree();
     });
   });
 }
diff --git a/packages/flutter/test/widgets/semantics_tester.dart b/packages/flutter/test/widgets/semantics_tester.dart
index 1c4f2b2..f1bb0ca 100644
--- a/packages/flutter/test/widgets/semantics_tester.dart
+++ b/packages/flutter/test/widgets/semantics_tester.dart
@@ -199,7 +199,7 @@
   String toString() => 'SemanticsTester';
 }
 
-const String _matcherHelp = 'Try dumping the semantics with debugDumpSemanticsTree() from the rendering library to see what the semantics tree looks like.';
+const String _matcherHelp = 'Try dumping the semantics with debugDumpSemanticsTree(DebugSemanticsDumpOrder.inverseHitTest) from the package:flutter/rendering.dart library to see what the semantics tree looks like.';
 
 class _HasSemantics extends Matcher {
   const _HasSemantics(this._semantics, { this.ignoreRect: false, this.ignoreTransform: false }) : assert(_semantics != null), assert(ignoreRect != null), assert(ignoreTransform != null);
diff --git a/packages/flutter/test/widgets/sliver_semantics_test.dart b/packages/flutter/test/widgets/sliver_semantics_test.dart
index e9fb2b9..2ae758e 100644
--- a/packages/flutter/test/widgets/sliver_semantics_test.dart
+++ b/packages/flutter/test/widgets/sliver_semantics_test.dart
@@ -54,16 +54,16 @@
                   children: <TestSemantics>[
                     new TestSemantics(
                       id: 2,
-                      label: 'Semantics Test with Slivers',
-                    ),
-                    new TestSemantics(
-                      id: 3,
                       label: 'Item 0',
                     ),
                     new TestSemantics(
-                      id: 4,
+                      id: 3,
                       label: 'Item 1',
                     ),
+                    new TestSemantics(
+                      id: 4,
+                      label: 'Semantics Test with Slivers',
+                    ),
                   ],
                 ),
               ],
@@ -87,28 +87,28 @@
             tags: <SemanticsTag>[RenderSemanticsGestureHandler.useTwoPaneSemantics],
             children: <TestSemantics>[
               new TestSemantics(
-                id: 6,
-                label: 'Semantics Test with Slivers',
-                tags: <SemanticsTag>[RenderSemanticsGestureHandler.excludeFromScrolling],
-              ),
-              new TestSemantics(
                 id: 5,
                 actions: SemanticsAction.scrollUp.index | SemanticsAction.scrollDown.index,
                 children: <TestSemantics>[
                   new TestSemantics(
-                    id: 3,
+                    id: 2,
                     label: 'Item 0',
                   ),
                   new TestSemantics(
-                    id: 4,
+                    id: 3,
                     label: 'Item 1',
                   ),
                   new TestSemantics(
-                    id: 7,
+                    id: 6,
                     label: 'Item 2',
                   ),
                 ],
               ),
+              new TestSemantics(
+                id: 7,
+                label: 'Semantics Test with Slivers',
+                tags: <SemanticsTag>[RenderSemanticsGestureHandler.excludeFromScrolling],
+              ),
             ],
           )
         ],
@@ -134,21 +134,21 @@
                 actions: SemanticsAction.scrollUp.index | SemanticsAction.scrollDown.index,
                 children: <TestSemantics>[
                   new TestSemantics(
-                    id: 8,
-                    label: 'Semantics Test with Slivers',
-                  ),
-                  new TestSemantics(
-                    id: 3,
+                    id: 2,
                     label: 'Item 0',
                   ),
                   new TestSemantics(
-                    id: 4,
+                    id: 3,
                     label: 'Item 1',
                   ),
                   new TestSemantics(
-                    id: 7,
+                    id: 6,
                     label: 'Item 2',
                   ),
+                  new TestSemantics(
+                    id: 8,
+                    label: 'Semantics Test with Slivers',
+                  ),
                 ],
               ),
             ],
@@ -158,5 +158,127 @@
       ignoreRect: true,
       ignoreTransform: true,
     ));
+
+    semantics.dispose();
+  });
+
+  testWidgets('Offscreen sliver are not included in semantics tree', (WidgetTester tester) async {
+    final SemanticsTester semantics = new SemanticsTester(tester);
+
+    const double containerHeight = 200.0;
+
+    final ScrollController scrollController = new ScrollController(
+      initialScrollOffset: containerHeight * 1.5,
+    );
+    final List<Widget> slivers = new List<Widget>.generate(30, (int i) {
+      return new SliverToBoxAdapter(
+        child: new Container(
+          height: containerHeight,
+          child: new Text('Item $i'),
+        ),
+      );
+    });
+    await tester.pumpWidget(
+      new Center(
+        child: new SizedBox(
+          height: containerHeight,
+          child: new CustomScrollView(
+            controller: scrollController,
+            slivers: slivers,
+          ),
+        ),
+      ),
+    );
+
+    expect(semantics, hasSemantics(
+      new TestSemantics.root(
+        children: <TestSemantics>[
+          new TestSemantics.rootChild(
+            id: 9,
+            tags: <SemanticsTag>[RenderSemanticsGestureHandler.useTwoPaneSemantics],
+            children: <TestSemantics>[
+              new TestSemantics(
+                id: 12,
+                actions: SemanticsAction.scrollUp.index | SemanticsAction.scrollDown.index,
+                children: <TestSemantics>[
+                  new TestSemantics(
+                    id: 10,
+                    label: 'Item 2',
+                  ),
+                  new TestSemantics(
+                    id: 11,
+                    label: 'Item 1',
+                  ),
+                ],
+              ),
+            ],
+          )
+        ],
+      ),
+      ignoreRect: true,
+      ignoreTransform: true,
+    ));
+
+    semantics.dispose();
+  });
+
+  testWidgets('SemanticsNodes of Slivers are in paint order', (WidgetTester tester) async {
+    final SemanticsTester semantics = new SemanticsTester(tester);
+
+    final List<Widget> slivers = new List<Widget>.generate(5, (int i) {
+      return new SliverToBoxAdapter(
+        child: new Container(
+          height: 20.0,
+          child: new Text('Item $i'),
+        ),
+      );
+    });
+    await tester.pumpWidget(
+      new CustomScrollView(
+        slivers: slivers,
+      ),
+    );
+    
+    expect(semantics, hasSemantics(
+      new TestSemantics.root(
+        children: <TestSemantics>[
+          new TestSemantics.rootChild(
+            id: 13,
+            tags: <SemanticsTag>[RenderSemanticsGestureHandler.useTwoPaneSemantics],
+            children: <TestSemantics>[
+              new TestSemantics(
+                id: 19,
+                children: <TestSemantics>[
+                  new TestSemantics(
+                    id: 14,
+                    label: 'Item 4',
+                  ),
+                  new TestSemantics(
+                    id: 15,
+                    label: 'Item 3',
+                  ),
+                  new TestSemantics(
+                    id: 16,
+                    label: 'Item 2',
+                  ),
+                  new TestSemantics(
+                    id: 17,
+                    label: 'Item 1',
+                  ),
+                  new TestSemantics(
+                    id: 18,
+                    label: 'Item 0',
+                  ),
+                ],
+              ),
+            ],
+          )
+        ],
+      ),
+      ignoreRect: true,
+      ignoreTransform: true,
+    ));
+
+    semantics.dispose();
   });
 }
diff --git a/packages/flutter_tools/lib/src/resident_runner.dart b/packages/flutter_tools/lib/src/resident_runner.dart
index ecb404c..80c04cc 100644
--- a/packages/flutter_tools/lib/src/resident_runner.dart
+++ b/packages/flutter_tools/lib/src/resident_runner.dart
@@ -145,9 +145,14 @@
       await view.uiIsolate.flutterDebugDumpLayerTree();
   }
 
-  Future<Null> debugDumpSemanticsTree() async {
+  Future<Null> debugDumpSemanticsTreeInTraversalOrder() async {
     for (FlutterView view in views)
-      await view.uiIsolate.flutterDebugDumpSemanticsTree();
+      await view.uiIsolate.flutterDebugDumpSemanticsTreeInTraversalOrder();
+  }
+
+  Future<Null> debugDumpSemanticsTreeInInverseHitTestOrder() async {
+    for (FlutterView view in views)
+      await view.uiIsolate.flutterDebugDumpSemanticsTreeInInverseHitTestOrder();
   }
 
   Future<Null> toggleDebugPaintSizeEnabled() async {
@@ -431,10 +436,16 @@
       await device.debugDumpLayerTree();
   }
 
-  Future<Null> _debugDumpSemanticsTree() async {
+  Future<Null> _debugDumpSemanticsTreeInTraversalOrder() async {
     await refreshViews();
     for (FlutterDevice device in flutterDevices)
-      await device.debugDumpSemanticsTree();
+      await device.debugDumpSemanticsTreeInTraversalOrder();
+  }
+
+  Future<Null> _debugDumpSemanticsTreeInInverseHitTestOrder() async {
+    await refreshViews();
+    for (FlutterDevice device in flutterDevices)
+      await device.debugDumpSemanticsTreeInInverseHitTestOrder();
   }
 
   Future<Null> _debugToggleDebugPaintSizeEnabled() async {
@@ -607,7 +618,12 @@
       }
     } else if (character == 'S') {
       if (supportsServiceProtocol) {
-        await _debugDumpSemanticsTree();
+        await _debugDumpSemanticsTreeInTraversalOrder();
+        return true;
+      }
+    } else if (character == 'P') {
+      if (supportsServiceProtocol) {
+        await _debugDumpSemanticsTreeInInverseHitTestOrder();
         return true;
       }
     } else if (character == 'p') {
@@ -743,12 +759,12 @@
       printStatus('You can dump the widget hierarchy of the app (debugDumpApp) by pressing "w".');
       printStatus('To dump the rendering tree of the app (debugDumpRenderTree), press "t".');
       if (isRunningDebug) {
-        printStatus('For layers (debugDumpLayerTree), use "L"; accessibility (debugDumpSemantics), "S".');
+        printStatus('For layers (debugDumpLayerTree), use "L"; accessibility (debugDumpSemantics), "S" (traversal order) or "P" (inverse hit test order).');
         printStatus('To toggle the widget inspector (WidgetsApp.showWidgetInspectorOverride), press "i".');
         printStatus('To toggle the display of construction lines (debugPaintSizeEnabled), press "p".');
         printStatus('To simulate different operating systems, (defaultTargetPlatform), press "o".');
       } else {
-        printStatus('To dump the accessibility tree (debugDumpSemantics), press "S".');
+        printStatus('To dump the accessibility tree (debugDumpSemantics), press "S" (for traversal order) or "P" (for inverse hit test order).');
       }
       printStatus('To display the performance overlay (WidgetsApp.showPerformanceOverlay), press "P".');
     }
diff --git a/packages/flutter_tools/lib/src/vmservice.dart b/packages/flutter_tools/lib/src/vmservice.dart
index f444648..ef81678 100644
--- a/packages/flutter_tools/lib/src/vmservice.dart
+++ b/packages/flutter_tools/lib/src/vmservice.dart
@@ -1069,8 +1069,12 @@
     return invokeFlutterExtensionRpcRaw('ext.flutter.debugDumpLayerTree', timeout: kLongRequestTimeout);
   }
 
-  Future<Map<String, dynamic>> flutterDebugDumpSemanticsTree() {
-    return invokeFlutterExtensionRpcRaw('ext.flutter.debugDumpSemanticsTree', timeout: kLongRequestTimeout);
+  Future<Map<String, dynamic>> flutterDebugDumpSemanticsTreeInTraversalOrder() {
+    return invokeFlutterExtensionRpcRaw('ext.flutter.debugDumpSemanticsTreeInTraversalOrder', timeout: kLongRequestTimeout);
+  }
+
+  Future<Map<String, dynamic>> flutterDebugDumpSemanticsTreeInInverseHitTestOrder() {
+    return invokeFlutterExtensionRpcRaw('ext.flutter.debugDumpSemanticsTreeInInverseHitTestOrder', timeout: kLongRequestTimeout);
   }
 
   Future<Map<String, dynamic>> _flutterToggle(String name) async {