focus_traversal.dart 77 KB
Newer Older
Ian Hickson's avatar
Ian Hickson committed
1
// Copyright 2014 The Flutter Authors. All rights reserved.
2 3 4
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
// @dart = 2.8

7 8
import 'dart:ui';

9 10 11
import 'package:flutter/foundation.dart';
import 'package:flutter/painting.dart';

12
import 'actions.dart';
13
import 'basic.dart';
14
import 'editable_text.dart';
15
import 'focus_manager.dart';
16
import 'focus_scope.dart';
17
import 'framework.dart';
18 19
import 'scroll_position.dart';
import 'scrollable.dart';
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
// BuildContext/Element doesn't have a parent accessor, but it can be simulated
// with visitAncestorElements. _getAncestor is needed because
// context.getElementForInheritedWidgetOfExactType will return itself if it
// happens to be of the correct type. _getAncestor should be O(count), since we
// always return false at a specific ancestor. By default it returns the parent,
// which is O(1).
BuildContext _getAncestor(BuildContext context, {int count = 1}) {
  BuildContext target;
  context.visitAncestorElements((Element ancestor) {
    count--;
    if (count == 0) {
      target = ancestor;
      return false;
    }
    return true;
  });
  return target;
}

void _focusAndEnsureVisible(
  FocusNode node, {
  ScrollPositionAlignmentPolicy alignmentPolicy = ScrollPositionAlignmentPolicy.explicit,
}) {
  node.requestFocus();
  Scrollable.ensureVisible(node.context, alignment: 1.0, alignmentPolicy: alignmentPolicy);
}

// A class to temporarily hold information about FocusTraversalGroups when
// sorting their contents.
class _FocusTraversalGroupInfo {
  _FocusTraversalGroupInfo(
    _FocusTraversalGroupMarker marker, {
    FocusTraversalPolicy defaultPolicy,
    List<FocusNode> members,
  })  : groupNode = marker?.focusNode,
        policy = marker?.policy ?? defaultPolicy ?? ReadingOrderTraversalPolicy(),
        members = members ?? <FocusNode>[];

  final FocusNode groupNode;
  final FocusTraversalPolicy policy;
  final List<FocusNode> members;
}

64 65
/// A direction along either the horizontal or vertical axes.
///
66
/// This is used by the [DirectionalFocusTraversalPolicyMixin], and
67 68
/// [FocusNode.focusInDirection] to indicate which direction to look in for the
/// next focus.
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
enum TraversalDirection {
  /// Indicates a direction above the currently focused widget.
  up,

  /// Indicates a direction to the right of the currently focused widget.
  ///
  /// This direction is unaffected by the [Directionality] of the current
  /// context.
  right,

  /// Indicates a direction below the currently focused widget.
  down,

  /// Indicates a direction to the left of the currently focused widget.
  ///
  /// This direction is unaffected by the [Directionality] of the current
  /// context.
  left,

  // TODO(gspencer): Add diagonal traversal directions used by TV remotes and
  // game controllers when we support them.
}

/// An object used to specify a focus traversal policy used for configuring a
93
/// [FocusTraversalGroup] widget.
94 95
///
/// The focus traversal policy is what determines which widget is "next",
96 97
/// "previous", or in a direction from the widget associated with the currently
/// focused [FocusNode] (usually a [Focus] widget).
98 99 100 101
///
/// One of the pre-defined subclasses may be used, or define a custom policy to
/// create a unique focus order.
///
102 103 104
/// When defining your own, your subclass should implement [sortDescendants] to
/// provide the order in which you would like the descendants to be traversed.
///
105 106
/// See also:
///
107
///  * [FocusNode], for a description of the focus system.
108 109
///  * [FocusTraversalGroup], a widget that groups together and imposes a
///    traversal policy on the [Focus] nodes below it in the widget hierarchy.
110
///  * [FocusNode], which is affected by the traversal policy.
111
///  * [WidgetOrderTraversalPolicy], a policy that relies on the widget
112 113 114
///    creation order to describe the order of traversal.
///  * [ReadingOrderTraversalPolicy], a policy that describes the order as the
///    natural "reading order" for the current [Directionality].
115 116
///  * [OrderedTraversalPolicy], a policy that describes the order
///    explicitly using [FocusTraversalOrder] widgets.
117 118
///  * [DirectionalFocusTraversalPolicyMixin] a mixin class that implements
///    focus traversal in a direction.
119
@immutable
120
abstract class FocusTraversalPolicy with Diagnosticable {
121 122 123
  /// A const constructor so subclasses can be const.
  const FocusTraversalPolicy();

124 125
  /// Returns the node that should receive focus if focus is traversing
  /// forwards, and there is no current focus.
126
  ///
127 128 129
  /// The node returned is the node that should receive focus if focus is
  /// traversing forwards (i.e. with [next]), and there is no current focus in
  /// the nearest [FocusScopeNode] that `currentNode` belongs to.
130
  ///
131
  /// The `currentNode` argument must not be null.
132
  ///
133 134 135 136
  /// The default implementation returns the [FocusScopeNode.focusedChild], if
  /// set, on the nearest scope of the `currentNode`, otherwise, returns the
  /// first node from [sortDescendants], or the given `currentNode` if there are
  /// no descendants.
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
  ///
  /// See also:
  ///
  ///  * [next], the function that is called to move the focus to the next node.
  ///  * [DirectionalFocusTraversalPolicyMixin.findFirstFocusInDirection], a
  ///    function that finds the first focusable widget in a particular direction.
  FocusNode findFirstFocus(FocusNode currentNode) => _findInitialFocus(currentNode);

  /// Returns the node that should receive focus if focus is traversing
  /// backwards, and there is no current focus.
  ///
  /// The node returned is the one that should receive focus if focus is
  /// traversing backwards (i.e. with [previous]), and there is no current focus
  /// in the nearest [FocusScopeNode] that `currentNode` belongs to.
  ///
  /// The `currentNode` argument must not be null.
  ///
  /// The default implementation returns the [FocusScopeNode.focusedChild], if
  /// set, on the nearest scope of the `currentNode`, otherwise, returns the
  /// last node from [sortDescendants], or the given `currentNode` if there are
  /// no descendants.
  ///
  /// See also:
  ///
  ///  * [previous], the function that is called to move the focus to the next node.
  ///  * [DirectionalFocusTraversalPolicyMixin.findFirstFocusInDirection], a
  ///    function that finds the first focusable widget in a particular direction.
  FocusNode findLastFocus(FocusNode currentNode) => _findInitialFocus(currentNode, fromEnd: true);

  FocusNode _findInitialFocus(FocusNode currentNode, {bool fromEnd = false}) {
167 168 169 170
    assert(currentNode != null);
    final FocusScopeNode scope = currentNode.nearestScope;
    FocusNode candidate = scope.focusedChild;
    if (candidate == null && scope.descendants.isNotEmpty) {
171
      final Iterable<FocusNode> sorted = _sortAllDescendants(scope, currentNode);
172 173 174 175 176
      if (sorted.isEmpty) {
        candidate = null;
      } else {
        candidate = fromEnd ? sorted.last : sorted.first;
      }
177 178 179 180 181 182 183
    }

    // If we still didn't find any candidate, use the current node as a
    // fallback.
    candidate ??= currentNode;
    return candidate;
  }
184

185 186 187
  /// Returns the first node in the given `direction` that should receive focus
  /// if there is no current focus in the scope to which the `currentNode`
  /// belongs.
188 189
  ///
  /// This is typically used by [inDirection] to determine which node to focus
190
  /// if it is called when no node is currently focused.
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
  ///
  /// All arguments must not be null.
  FocusNode findFirstFocusInDirection(FocusNode currentNode, TraversalDirection direction);

  /// Clears the data associated with the given [FocusScopeNode] for this object.
  ///
  /// This is used to indicate that the focus policy has changed its mode, and
  /// so any cached policy data should be invalidated. For example, changing the
  /// direction in which focus is moving, or changing from directional to
  /// next/previous navigation modes.
  ///
  /// The default implementation does nothing.
  @mustCallSuper
  @protected
  void invalidateScopeData(FocusScopeNode node) {}

207
  /// This is called whenever the given [node] is re-parented into a new scope,
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
  /// so that the policy has a chance to update or invalidate any cached data
  /// that it maintains per scope about the node.
  ///
  /// The [oldScope] is the previous scope that this node belonged to, if any.
  ///
  /// The default implementation does nothing.
  @mustCallSuper
  void changedScope({FocusNode node, FocusScopeNode oldScope}) {}

  /// Focuses the next widget in the focus scope that contains the given
  /// [currentNode].
  ///
  /// This should determine what the next node to receive focus should be by
  /// inspecting the node tree, and then calling [FocusNode.requestFocus] on
  /// the node that has been selected.
  ///
  /// Returns true if it successfully found a node and requested focus.
  ///
  /// The [currentNode] argument must not be null.
227
  bool next(FocusNode currentNode) => _moveFocus(currentNode, forward: true);
228 229 230 231 232 233 234 235 236 237 238

  /// Focuses the previous widget in the focus scope that contains the given
  /// [currentNode].
  ///
  /// This should determine what the previous node to receive focus should be by
  /// inspecting the node tree, and then calling [FocusNode.requestFocus] on
  /// the node that has been selected.
  ///
  /// Returns true if it successfully found a node and requested focus.
  ///
  /// The [currentNode] argument must not be null.
239
  bool previous(FocusNode currentNode) => _moveFocus(currentNode, forward: false);
240 241 242 243 244 245 246 247 248 249 250 251 252

  /// Focuses the next widget in the given [direction] in the focus scope that
  /// contains the given [currentNode].
  ///
  /// This should determine what the next node to receive focus in the given
  /// [direction] should be by inspecting the node tree, and then calling
  /// [FocusNode.requestFocus] on the node that has been selected.
  ///
  /// Returns true if it successfully found a node and requested focus.
  ///
  /// All arguments must not be null.
  bool inDirection(FocusNode currentNode, TraversalDirection direction);

253 254 255 256 257
  /// Sorts the given `descendants` into focus order.
  ///
  /// Subclasses should override this to implement a different sort for [next]
  /// and [previous] to use in their ordering. If the returned iterable omits a
  /// node that is a descendant of the given scope, then the user will be unable
258 259 260 261 262 263 264 265 266
  /// to use next/previous keyboard traversal to reach that node.
  ///
  /// The node used to initiate the traversal (the one passed to [next] or
  /// [previous]) is passed as `currentNode`.
  ///
  /// Having the current node in the list is what allows the algorithm to
  /// determine which nodes are adjacent to the current node. If the
  /// `currentNode` is removed from the list, then the focus will be unchanged
  /// when [next] or [previous] are called, and they will return false.
267 268 269 270 271 272 273 274 275 276
  ///
  /// This is not used for directional focus ([inDirection]), only for
  /// determining the focus order for [next] and [previous].
  ///
  /// When implementing an override for this function, be sure to use
  /// [mergeSort] instead of Dart's default list sorting algorithm when sorting
  /// items, since the default algorithm is not stable (items deemed to be equal
  /// can appear in arbitrary order, and change positions between sorts), whereas
  /// [mergeSort] is stable.
  @protected
277
  Iterable<FocusNode> sortDescendants(Iterable<FocusNode> descendants, FocusNode currentNode);
278 279 280 281 282 283 284

  _FocusTraversalGroupMarker _getMarker(BuildContext context) {
    return context?.getElementForInheritedWidgetOfExactType<_FocusTraversalGroupMarker>()?.widget as _FocusTraversalGroupMarker;
  }

  // Sort all descendants, taking into account the FocusTraversalGroup
  // that they are each in, and filtering out non-traversable/focusable nodes.
285
  List<FocusNode> _sortAllDescendants(FocusScopeNode scope, FocusNode currentNode) {
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
    assert(scope != null);
    final _FocusTraversalGroupMarker scopeGroupMarker = _getMarker(scope.context);
    final FocusTraversalPolicy defaultPolicy = scopeGroupMarker?.policy ?? ReadingOrderTraversalPolicy();
    // Build the sorting data structure, separating descendants into groups.
    final Map<FocusNode, _FocusTraversalGroupInfo> groups = <FocusNode, _FocusTraversalGroupInfo>{};
    for (final FocusNode node in scope.descendants) {
      final _FocusTraversalGroupMarker groupMarker = _getMarker(node.context);
      final FocusNode groupNode = groupMarker?.focusNode;
      // Group nodes need to be added to their parent's node, or to the "null"
      // node if no parent is found. This creates the hierarchy of group nodes
      // and makes it so the entire group is sorted along with the other members
      // of the parent group.
      if (node == groupNode) {
        // To find the parent of the group node, we need to skip over the parent
        // of the Focus node in _FocusTraversalGroupState.build, and start
        // looking with that node's parent, since _getMarker will return the
        // context it was called on if it matches the type.
        final BuildContext parentContext = _getAncestor(groupNode.context, count: 2);
        final _FocusTraversalGroupMarker parentMarker = _getMarker(parentContext);
        final FocusNode parentNode = parentMarker?.focusNode;
        groups[parentNode] ??= _FocusTraversalGroupInfo(parentMarker, members: <FocusNode>[], defaultPolicy: defaultPolicy);
        assert(!groups[parentNode].members.contains(node));
        groups[parentNode].members.add(groupNode);
        continue;
      }
      // Skip non-focusable and non-traversable nodes in the same way that
      // FocusScopeNode.traversalDescendants would.
      if (node.canRequestFocus && !node.skipTraversal) {
        groups[groupNode] ??= _FocusTraversalGroupInfo(groupMarker, members: <FocusNode>[], defaultPolicy: defaultPolicy);
        assert(!groups[groupNode].members.contains(node));
        groups[groupNode].members.add(node);
      }
    }

    // Sort the member lists using the individual policy sorts.
    final Set<FocusNode> groupKeys = groups.keys.toSet();
    for (final FocusNode key in groups.keys) {
323
      final List<FocusNode> sortedMembers = groups[key].policy.sortDescendants(groups[key].members, currentNode).toList();
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344
      groups[key].members.clear();
      groups[key].members.addAll(sortedMembers);
    }

    // Traverse the group tree, adding the children of members in the order they
    // appear in the member lists.
    final List<FocusNode> sortedDescendants = <FocusNode>[];
    void visitGroups(_FocusTraversalGroupInfo info) {
      for (final FocusNode node in info.members) {
        if (groupKeys.contains(node)) {
          // This is a policy group focus node. Replace it with the members of
          // the corresponding policy group.
          visitGroups(groups[node]);
        } else {
          sortedDescendants.add(node);
        }
      }
    }

    visitGroups(groups[scopeGroupMarker?.focusNode]);
    assert(
345
      sortedDescendants.length <= scope.traversalDescendants.length && sortedDescendants.toSet().difference(scope.traversalDescendants.toSet()).isEmpty,
346 347 348 349 350
      'sorted descendants contains more nodes than it should: (${sortedDescendants.toSet().difference(scope.traversalDescendants.toSet())})'
    );
    return sortedDescendants;
  }

351 352 353 354 355 356 357 358 359 360 361 362 363 364
  /// Moves the focus to the next node in the FocusScopeNode nearest to the
  /// currentNode argument, either in a forward or reverse direction, depending
  /// on the value of the forward argument.
  ///
  /// This function is called by the next and previous members to move to the
  /// next or previous node, respectively.
  ///
  /// Uses [findFirstFocus]/[findLastFocus] to find the first/last node if there is
  /// no [FocusScopeNode.focusedChild] set. If there is a focused child for the
  /// scope, then it calls sortDescendants to get a sorted list of descendants,
  /// and then finds the node after the current first focus of the scope if
  /// forward is true, and the node before it if forward is false.
  ///
  /// Returns true if a node requested focus.
365 366 367 368 369 370 371 372 373 374
  @protected
  bool _moveFocus(FocusNode currentNode, {@required bool forward}) {
    assert(forward != null);
    if (currentNode == null) {
      return false;
    }
    final FocusScopeNode nearestScope = currentNode.nearestScope;
    invalidateScopeData(nearestScope);
    final FocusNode focusedChild = nearestScope.focusedChild;
    if (focusedChild == null) {
375
      final FocusNode firstFocus = forward ? findFirstFocus(currentNode) : findLastFocus(currentNode);
376 377 378 379 380 381 382 383
      if (firstFocus != null) {
        _focusAndEnsureVisible(
          firstFocus,
          alignmentPolicy: forward ? ScrollPositionAlignmentPolicy.keepVisibleAtEnd : ScrollPositionAlignmentPolicy.keepVisibleAtStart,
        );
        return true;
      }
    }
384
    final List<FocusNode> sortedNodes = _sortAllDescendants(nearestScope, currentNode);
385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
    if (forward && focusedChild == sortedNodes.last) {
      _focusAndEnsureVisible(sortedNodes.first, alignmentPolicy: ScrollPositionAlignmentPolicy.keepVisibleAtEnd);
      return true;
    }
    if (!forward && focusedChild == sortedNodes.first) {
      _focusAndEnsureVisible(sortedNodes.last, alignmentPolicy: ScrollPositionAlignmentPolicy.keepVisibleAtStart);
      return true;
    }

    final Iterable<FocusNode> maybeFlipped = forward ? sortedNodes : sortedNodes.reversed;
    FocusNode previousNode;
    for (final FocusNode node in maybeFlipped) {
      if (previousNode == focusedChild) {
        _focusAndEnsureVisible(
          node,
          alignmentPolicy: forward ? ScrollPositionAlignmentPolicy.keepVisibleAtEnd : ScrollPositionAlignmentPolicy.keepVisibleAtStart,
        );
        return true;
      }
      previousNode = node;
    }
    return false;
  }
408 409
}

410 411
// A policy data object for use by the DirectionalFocusTraversalPolicyMixin so
// it can keep track of the traversal history.
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435
class _DirectionalPolicyDataEntry {
  const _DirectionalPolicyDataEntry({@required this.direction, @required this.node})
      : assert(direction != null),
        assert(node != null);

  final TraversalDirection direction;
  final FocusNode node;
}

class _DirectionalPolicyData {
  const _DirectionalPolicyData({@required this.history}) : assert(history != null);

  /// A queue of entries that describe the path taken to the current node.
  final List<_DirectionalPolicyDataEntry> history;
}

/// A mixin class that provides an implementation for finding a node in a
/// particular direction.
///
/// This can be mixed in to other [FocusTraversalPolicy] implementations that
/// only want to implement new next/previous policies.
///
/// Since hysteresis in the navigation order is undesirable, this implementation
/// maintains a stack of previous locations that have been visited on the
436
/// policy data for the affected [FocusScopeNode]. If the previous direction
437 438 439 440 441 442 443
/// was the opposite of the current direction, then the this policy will request
/// focus on the previously focused node. Change to another direction other than
/// the current one or its opposite will clear the stack.
///
/// For instance, if the focus moves down, down, down, and then up, up, up, it
/// will follow the same path through the widgets in both directions. However,
/// if it moves down, down, down, left, right, and then up, up, up, it may not
444 445
/// follow the same path on the way up as it did on the way down, since changing
/// the axis of motion resets the history.
446 447 448
///
/// See also:
///
449
///  * [FocusNode], for a description of the focus system.
450 451 452
///  * [FocusTraversalGroup], a widget that groups together and imposes a
///    traversal policy on the [Focus] nodes below it in the widget hierarchy.
///  * [WidgetOrderTraversalPolicy], a policy that relies on the widget
453 454 455
///    creation order to describe the order of traversal.
///  * [ReadingOrderTraversalPolicy], a policy that describes the order as the
///    natural "reading order" for the current [Directionality].
456 457
///  * [OrderedTraversalPolicy], a policy that describes the order
///    explicitly using [FocusTraversalOrder] widgets.
458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
mixin DirectionalFocusTraversalPolicyMixin on FocusTraversalPolicy {
  final Map<FocusScopeNode, _DirectionalPolicyData> _policyData = <FocusScopeNode, _DirectionalPolicyData>{};

  @override
  void invalidateScopeData(FocusScopeNode node) {
    super.invalidateScopeData(node);
    _policyData.remove(node);
  }

  @override
  void changedScope({FocusNode node, FocusScopeNode oldScope}) {
    super.changedScope(node: node, oldScope: oldScope);
    if (oldScope != null) {
      _policyData[oldScope]?.history?.removeWhere((_DirectionalPolicyDataEntry entry) {
        return entry.node == node;
      });
    }
  }

  @override
  FocusNode findFirstFocusInDirection(FocusNode currentNode, TraversalDirection direction) {
    assert(direction != null);
    assert(currentNode != null);
    switch (direction) {
      case TraversalDirection.up:
        // Find the bottom-most node so we can go up from there.
        return _sortAndFindInitial(currentNode, vertical: true, first: false);
      case TraversalDirection.down:
        // Find the top-most node so we can go down from there.
        return _sortAndFindInitial(currentNode, vertical: true, first: true);
      case TraversalDirection.left:
        // Find the right-most node so we can go left from there.
        return _sortAndFindInitial(currentNode, vertical: false, first: false);
      case TraversalDirection.right:
        // Find the left-most node so we can go right from there.
        return _sortAndFindInitial(currentNode, vertical: false, first: true);
    }
    return null;
  }

498
  FocusNode _sortAndFindInitial(FocusNode currentNode, {bool vertical, bool first}) {
499
    final Iterable<FocusNode> nodes = currentNode.nearestScope.traversalDescendants;
500
    final List<FocusNode> sorted = nodes.toList();
501
    mergeSort<FocusNode>(sorted, compare: (FocusNode a, FocusNode b) {
502 503 504 505 506 507 508 509 510 511 512 513 514 515
      if (vertical) {
        if (first) {
          return a.rect.top.compareTo(b.rect.top);
        } else {
          return b.rect.bottom.compareTo(a.rect.bottom);
        }
      } else {
        if (first) {
          return a.rect.left.compareTo(b.rect.left);
        } else {
          return b.rect.right.compareTo(a.rect.right);
        }
      }
    });
516

517
    if (sorted.isNotEmpty) {
518
      return sorted.first;
519
    }
520 521

    return null;
522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537
  }

  // Sorts nodes from left to right horizontally, and removes nodes that are
  // either to the right of the left side of the target node if we're going
  // left, or to the left of the right side of the target node if we're going
  // right.
  //
  // This doesn't need to take into account directionality because it is
  // typically intending to actually go left or right, not in a reading
  // direction.
  Iterable<FocusNode> _sortAndFilterHorizontally(
    TraversalDirection direction,
    Rect target,
    FocusNode nearestScope,
  ) {
    assert(direction == TraversalDirection.left || direction == TraversalDirection.right);
538
    final Iterable<FocusNode> nodes = nearestScope.traversalDescendants;
539 540
    assert(!nodes.contains(nearestScope));
    final List<FocusNode> sorted = nodes.toList();
541
    mergeSort<FocusNode>(sorted, compare: (FocusNode a, FocusNode b) => a.rect.center.dx.compareTo(b.rect.center.dx));
542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565
    Iterable<FocusNode> result;
    switch (direction) {
      case TraversalDirection.left:
        result = sorted.where((FocusNode node) => node.rect != target && node.rect.center.dx <= target.left);
        break;
      case TraversalDirection.right:
        result = sorted.where((FocusNode node) => node.rect != target && node.rect.center.dx >= target.right);
        break;
      case TraversalDirection.up:
      case TraversalDirection.down:
        break;
    }
    return result;
  }

  // Sorts nodes from top to bottom vertically, and removes nodes that are
  // either below the top of the target node if we're going up, or above the
  // bottom of the target node if we're going down.
  Iterable<FocusNode> _sortAndFilterVertically(
    TraversalDirection direction,
    Rect target,
    Iterable<FocusNode> nodes,
  ) {
    final List<FocusNode> sorted = nodes.toList();
566
    mergeSort<FocusNode>(sorted, compare: (FocusNode a, FocusNode b) => a.rect.center.dy.compareTo(b.rect.center.dy));
567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586
    switch (direction) {
      case TraversalDirection.up:
        return sorted.where((FocusNode node) => node.rect != target && node.rect.center.dy <= target.top);
      case TraversalDirection.down:
        return sorted.where((FocusNode node) => node.rect != target && node.rect.center.dy >= target.bottom);
      case TraversalDirection.left:
      case TraversalDirection.right:
        break;
    }
    assert(direction == TraversalDirection.up || direction == TraversalDirection.down);
    return null;
  }

  // Updates the policy data to keep the previously visited node so that we can
  // avoid hysteresis when we change directions in navigation.
  //
  // Returns true if focus was requested on a previous node.
  bool _popPolicyDataIfNeeded(TraversalDirection direction, FocusScopeNode nearestScope, FocusNode focusedChild) {
    final _DirectionalPolicyData policyData = _policyData[nearestScope];
    if (policyData != null && policyData.history.isNotEmpty && policyData.history.first.direction != direction) {
587 588 589
      if (policyData.history.last.node.parent == null) {
        // If a node has been removed from the tree, then we should stop
        // referencing it and reset the scope data so that we don't try and
590 591 592
        // request focus on it. This can happen in slivers where the rendered
        // node has been unmounted. This has the side effect that hysteresis
        // might not be avoided when items that go off screen get unmounted.
593 594 595
        invalidateScopeData(nearestScope);
        return false;
      }
596 597 598 599 600 601 602 603 604

      // Returns true if successfully popped the history.
      bool popOrInvalidate(TraversalDirection direction) {
        final FocusNode lastNode = policyData.history.removeLast().node;
        if (Scrollable.of(lastNode.context) != Scrollable.of(primaryFocus.context)) {
          invalidateScopeData(nearestScope);
          return false;
        }
        ScrollPositionAlignmentPolicy alignmentPolicy;
605
        switch (direction) {
606 607 608 609 610 611
          case TraversalDirection.up:
          case TraversalDirection.left:
            alignmentPolicy = ScrollPositionAlignmentPolicy.keepVisibleAtStart;
            break;
          case TraversalDirection.right:
          case TraversalDirection.down:
612
            alignmentPolicy = ScrollPositionAlignmentPolicy.keepVisibleAtEnd;
613 614 615 616 617 618 619 620 621
            break;
        }
        _focusAndEnsureVisible(
          lastNode,
          alignmentPolicy: alignmentPolicy,
        );
        return true;
      }

622 623 624 625 626 627 628 629 630 631 632
      switch (direction) {
        case TraversalDirection.down:
        case TraversalDirection.up:
          switch (policyData.history.first.direction) {
            case TraversalDirection.left:
            case TraversalDirection.right:
              // Reset the policy data if we change directions.
              invalidateScopeData(nearestScope);
              break;
            case TraversalDirection.up:
            case TraversalDirection.down:
633 634 635 636
              if (popOrInvalidate(direction)) {
                return true;
              }
              break;
637 638 639 640 641 642 643
          }
          break;
        case TraversalDirection.left:
        case TraversalDirection.right:
          switch (policyData.history.first.direction) {
            case TraversalDirection.left:
            case TraversalDirection.right:
644 645 646 647
              if (popOrInvalidate(direction)) {
                return true;
              }
              break;
648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
            case TraversalDirection.up:
            case TraversalDirection.down:
              // Reset the policy data if we change directions.
              invalidateScopeData(nearestScope);
              break;
          }
      }
    }
    if (policyData != null && policyData.history.isEmpty) {
      invalidateScopeData(nearestScope);
    }
    return false;
  }

  void _pushPolicyData(TraversalDirection direction, FocusScopeNode nearestScope, FocusNode focusedChild) {
    final _DirectionalPolicyData policyData = _policyData[nearestScope];
    if (policyData != null && policyData is! _DirectionalPolicyData) {
      return;
    }
    final _DirectionalPolicyDataEntry newEntry = _DirectionalPolicyDataEntry(node: focusedChild, direction: direction);
    if (policyData != null) {
      policyData.history.add(newEntry);
    } else {
      _policyData[nearestScope] = _DirectionalPolicyData(history: <_DirectionalPolicyDataEntry>[newEntry]);
    }
  }

  /// Focuses the next widget in the given [direction] in the [FocusScope] that
  /// contains the [currentNode].
  ///
  /// This determines what the next node to receive focus in the given
  /// [direction] will be by inspecting the node tree, and then calling
  /// [FocusNode.requestFocus] on it.
  ///
  /// Returns true if it successfully found a node and requested focus.
  ///
  /// Maintains a stack of previous locations that have been visited on the
685
  /// policy data for the affected [FocusScopeNode]. If the previous direction
686 687 688 689 690 691 692 693 694 695 696 697
  /// was the opposite of the current direction, then the this policy will
  /// request focus on the previously focused node. Change to another direction
  /// other than the current one or its opposite will clear the stack.
  ///
  /// If this function returns true when called by a subclass, then the subclass
  /// should return true and not request focus from any node.
  @mustCallSuper
  @override
  bool inDirection(FocusNode currentNode, TraversalDirection direction) {
    final FocusScopeNode nearestScope = currentNode.nearestScope;
    final FocusNode focusedChild = nearestScope.focusedChild;
    if (focusedChild == null) {
698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714
      final FocusNode firstFocus = findFirstFocusInDirection(currentNode, direction) ?? currentNode;
      switch (direction) {
        case TraversalDirection.up:
        case TraversalDirection.left:
          _focusAndEnsureVisible(
            firstFocus,
            alignmentPolicy: ScrollPositionAlignmentPolicy.keepVisibleAtStart,
          );
          break;
        case TraversalDirection.right:
        case TraversalDirection.down:
          _focusAndEnsureVisible(
            firstFocus,
            alignmentPolicy: ScrollPositionAlignmentPolicy.keepVisibleAtEnd,
          );
          break;
      }
715 716 717 718 719 720
      return true;
    }
    if (_popPolicyDataIfNeeded(direction, nearestScope, focusedChild)) {
      return true;
    }
    FocusNode found;
721
    final ScrollableState focusedScrollable = Scrollable.of(focusedChild.context);
722 723 724
    switch (direction) {
      case TraversalDirection.down:
      case TraversalDirection.up:
725
        Iterable<FocusNode> eligibleNodes = _sortAndFilterVertically(
726 727
          direction,
          focusedChild.rect,
728
          nearestScope.traversalDescendants,
729
        );
730 731 732 733 734 735
        if (focusedScrollable != null && !focusedScrollable.position.atEdge) {
          final Iterable<FocusNode> filteredEligibleNodes = eligibleNodes.where((FocusNode node) => Scrollable.of(node.context) == focusedScrollable);
          if (filteredEligibleNodes.isNotEmpty) {
            eligibleNodes = filteredEligibleNodes;
          }
        }
736 737 738 739 740 741 742 743 744 745 746
        if (eligibleNodes.isEmpty) {
          break;
        }
        List<FocusNode> sorted = eligibleNodes.toList();
        if (direction == TraversalDirection.up) {
          sorted = sorted.reversed.toList();
        }
        // Find any nodes that intersect the band of the focused child.
        final Rect band = Rect.fromLTRB(focusedChild.rect.left, -double.infinity, focusedChild.rect.right, double.infinity);
        final Iterable<FocusNode> inBand = sorted.where((FocusNode node) => !node.rect.intersect(band).isEmpty);
        if (inBand.isNotEmpty) {
747 748
          // The inBand list is already sorted by horizontal distance, so pick
          // the closest one.
749 750 751
          found = inBand.first;
          break;
        }
752 753 754
        // Only out-of-band targets remain, so pick the one that is closest the
        // to the center line horizontally.
        mergeSort<FocusNode>(sorted, compare: (FocusNode a, FocusNode b) {
755 756 757 758 759 760
          return (a.rect.center.dx - focusedChild.rect.center.dx).abs().compareTo((b.rect.center.dx - focusedChild.rect.center.dx).abs());
        });
        found = sorted.first;
        break;
      case TraversalDirection.right:
      case TraversalDirection.left:
761 762 763 764 765 766 767
        Iterable<FocusNode> eligibleNodes = _sortAndFilterHorizontally(direction, focusedChild.rect, nearestScope);
        if (focusedScrollable != null && !focusedScrollable.position.atEdge) {
          final Iterable<FocusNode> filteredEligibleNodes = eligibleNodes.where((FocusNode node) => Scrollable.of(node.context) == focusedScrollable);
          if (filteredEligibleNodes.isNotEmpty) {
            eligibleNodes = filteredEligibleNodes;
          }
        }
768 769 770 771 772 773 774 775 776 777 778
        if (eligibleNodes.isEmpty) {
          break;
        }
        List<FocusNode> sorted = eligibleNodes.toList();
        if (direction == TraversalDirection.left) {
          sorted = sorted.reversed.toList();
        }
        // Find any nodes that intersect the band of the focused child.
        final Rect band = Rect.fromLTRB(-double.infinity, focusedChild.rect.top, double.infinity, focusedChild.rect.bottom);
        final Iterable<FocusNode> inBand = sorted.where((FocusNode node) => !node.rect.intersect(band).isEmpty);
        if (inBand.isNotEmpty) {
779 780
          // The inBand list is already sorted by vertical distance, so pick the
          // closest one.
781 782 783
          found = inBand.first;
          break;
        }
784 785 786
        // Only out-of-band targets remain, so pick the one that is closest the
        // to the center line vertically.
        mergeSort<FocusNode>(sorted, compare: (FocusNode a, FocusNode b) {
787 788 789 790 791 792 793
          return (a.rect.center.dy - focusedChild.rect.center.dy).abs().compareTo((b.rect.center.dy - focusedChild.rect.center.dy).abs());
        });
        found = sorted.first;
        break;
    }
    if (found != null) {
      _pushPolicyData(direction, nearestScope, focusedChild);
794 795 796 797 798 799 800 801 802 803
      switch (direction) {
        case TraversalDirection.up:
        case TraversalDirection.left:
          _focusAndEnsureVisible(
            found,
            alignmentPolicy: ScrollPositionAlignmentPolicy.keepVisibleAtStart,
          );
          break;
        case TraversalDirection.down:
        case TraversalDirection.right:
804 805 806 807
          _focusAndEnsureVisible(
            found,
            alignmentPolicy: ScrollPositionAlignmentPolicy.keepVisibleAtEnd,
          );
808 809
          break;
      }
810 811 812 813 814 815 816 817 818 819 820 821 822 823
      return true;
    }
    return false;
  }
}

/// A [FocusTraversalPolicy] that traverses the focus order in widget hierarchy
/// order.
///
/// This policy is used when the order desired is the order in which widgets are
/// created in the widget hierarchy.
///
/// See also:
///
824
///  * [FocusNode], for a description of the focus system.
825 826
///  * [FocusTraversalGroup], a widget that groups together and imposes a
///    traversal policy on the [Focus] nodes below it in the widget hierarchy.
827 828 829 830
///  * [ReadingOrderTraversalPolicy], a policy that describes the order as the
///    natural "reading order" for the current [Directionality].
///  * [DirectionalFocusTraversalPolicyMixin] a mixin class that implements
///    focus traversal in a direction.
831 832 833
///  * [OrderedTraversalPolicy], a policy that describes the order
///    explicitly using [FocusTraversalOrder] widgets.
class WidgetOrderTraversalPolicy extends FocusTraversalPolicy with DirectionalFocusTraversalPolicyMixin {
834
  @override
835
  Iterable<FocusNode> sortDescendants(Iterable<FocusNode> descendants, FocusNode currentNode) => descendants;
836 837 838 839 840 841 842 843 844 845
}

// This class exists mainly for efficiency reasons: the rect is copied out of
// the node, because it will be accessed many times in the reading order
// algorithm, and the FocusNode.rect accessor does coordinate transformation. If
// not for this optimization, it could just be removed, and the node used
// directly.
//
// It's also a convenient place to put some utility functions having to do with
// the sort data.
846
class _ReadingOrderSortData with Diagnosticable {
847 848 849 850 851 852 853 854 855 856 857 858 859
  _ReadingOrderSortData(this.node)
      : assert(node != null),
        rect = node.rect,
        directionality = _findDirectionality(node.context);

  final TextDirection directionality;
  final Rect rect;
  final FocusNode node;

  // Find the directionality in force for a build context without creating a
  // dependency.
  static TextDirection _findDirectionality(BuildContext context) {
    return (context.getElementForInheritedWidgetOfExactType<Directionality>()?.widget as Directionality)?.textDirection;
860
  }
861

862 863 864 865 866 867 868
  /// Finds the common Directional ancestor of an entire list of groups.
  static TextDirection commonDirectionalityOf(List<_ReadingOrderSortData> list) {
    final Iterable<Set<Directionality>> allAncestors = list.map<Set<Directionality>>((_ReadingOrderSortData member) => member.directionalAncestors.toSet());
    Set<Directionality> common;
    for (final Set<Directionality> ancestorSet in allAncestors) {
      common ??= ancestorSet;
      common = common.intersection(ancestorSet);
869
    }
870 871 872 873 874
    if (common.isEmpty) {
      // If there is no common ancestor, then arbitrarily pick the
      // directionality of the first group, which is the equivalent of the "first
      // strongly typed" item in a bidi algorithm.
      return list.first.directionality;
875
    }
876 877 878 879 880 881 882 883 884 885 886 887 888 889
    // Find the closest common ancestor. The memberAncestors list contains the
    // ancestors for all members, but the first member's ancestry was
    // added in order from nearest to furthest, so we can still use that
    // to determine the closest one.
    return list.first.directionalAncestors.firstWhere(common.contains).textDirection;
  }

  static void sortWithDirectionality(List<_ReadingOrderSortData> list, TextDirection directionality) {
    mergeSort<_ReadingOrderSortData>(list, compare: (_ReadingOrderSortData a, _ReadingOrderSortData b) {
      switch (directionality) {
        case TextDirection.ltr:
          return a.rect.left.compareTo(b.rect.left);
        case TextDirection.rtl:
          return b.rect.right.compareTo(a.rect.right);
890
      }
891 892 893 894
      assert(false, 'Unhandled directionality $directionality');
      return 0;
    });
  }
895

896 897 898 899 900 901 902 903 904
  /// Returns the list of Directionality ancestors, in order from nearest to
  /// furthest.
  Iterable<Directionality> get directionalAncestors {
    List<Directionality> getDirectionalityAncestors(BuildContext context) {
      final List<Directionality> result = <Directionality>[];
      InheritedElement directionalityElement = context.getElementForInheritedWidgetOfExactType<Directionality>();
      while (directionalityElement != null) {
        result.add(directionalityElement.widget as Directionality);
        directionalityElement = _getAncestor(directionalityElement)?.getElementForInheritedWidgetOfExactType<Directionality>();
905
      }
906
      return result;
907
    }
908 909 910

    _directionalAncestors ??= getDirectionalityAncestors(node.context);
    return _directionalAncestors;
911 912
  }

913
  List<Directionality> _directionalAncestors;
914 915

  @override
916 917 918 919 920 921
  void debugFillProperties(DiagnosticPropertiesBuilder properties) {
    super.debugFillProperties(properties);
    properties.add(DiagnosticsProperty<TextDirection>('directionality', directionality));
    properties.add(StringProperty('name', node.debugLabel, defaultValue: null));
    properties.add(DiagnosticsProperty<Rect>('rect', rect));
  }
922 923
}

924 925
// A class for containing group data while sorting in reading order while taking
// into account the ambient directionality.
926
class _ReadingOrderDirectionalGroupData with Diagnosticable {
927
  _ReadingOrderDirectionalGroupData(this.members);
928

929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977
  final List<_ReadingOrderSortData> members;

  TextDirection get directionality => members.first.directionality;

  Rect _rect;
  Rect get rect {
    if (_rect == null) {
      for (final Rect rect in members.map<Rect>((_ReadingOrderSortData data) => data.rect)) {
        _rect ??= rect;
        _rect = _rect.expandToInclude(rect);
      }
    }
    return _rect;
  }

  List<Directionality> get memberAncestors {
    if (_memberAncestors == null) {
      _memberAncestors = <Directionality>[];
      for (final _ReadingOrderSortData member in members) {
        _memberAncestors.addAll(member.directionalAncestors);
      }
    }
    return _memberAncestors;
  }

  List<Directionality> _memberAncestors;

  static void sortWithDirectionality(List<_ReadingOrderDirectionalGroupData> list, TextDirection directionality) {
    mergeSort<_ReadingOrderDirectionalGroupData>(list, compare: (_ReadingOrderDirectionalGroupData a, _ReadingOrderDirectionalGroupData b) {
      switch (directionality) {
        case TextDirection.ltr:
          return a.rect.left.compareTo(b.rect.left);
        case TextDirection.rtl:
          return b.rect.right.compareTo(a.rect.right);
      }
      assert(false, 'Unhandled directionality $directionality');
      return 0;
    });
  }

  @override
  void debugFillProperties(DiagnosticPropertiesBuilder properties) {
    super.debugFillProperties(properties);
    properties.add(DiagnosticsProperty<TextDirection>('directionality', directionality));
    properties.add(DiagnosticsProperty<Rect>('rect', rect));
    properties.add(IterableProperty<String>('members', members.map<String>((_ReadingOrderSortData member) {
      return '"${member.node.debugLabel}"(${member.rect})';
    })));
  }
978 979 980 981 982 983 984 985 986 987 988 989 990
}

/// Traverses the focus order in "reading order".
///
/// By default, reading order traversal goes in the reading direction, and then
/// down, using this algorithm:
///
/// 1. Find the node rectangle that has the highest `top` on the screen.
/// 2. Find any other nodes that intersect the infinite horizontal band defined
///    by the highest rectangle's top and bottom edges.
/// 3. Pick the closest to the beginning of the reading order from among the
///    nodes discovered above.
///
991 992
/// It uses the ambient [Directionality] in the context for the enclosing
/// [FocusTraversalGroup] to determine which direction is "reading order".
993 994 995
///
/// See also:
///
996
///  * [FocusNode], for a description of the focus system.
997 998 999
///  * [FocusTraversalGroup], a widget that groups together and imposes a
///    traversal policy on the [Focus] nodes below it in the widget hierarchy.
///  * [WidgetOrderTraversalPolicy], a policy that relies on the widget
1000 1001 1002
///    creation order to describe the order of traversal.
///  * [DirectionalFocusTraversalPolicyMixin] a mixin class that implements
///    focus traversal in a direction.
1003 1004
///  * [OrderedTraversalPolicy], a policy that describes the order
///    explicitly using [FocusTraversalOrder] widgets.
1005
class ReadingOrderTraversalPolicy extends FocusTraversalPolicy with DirectionalFocusTraversalPolicyMixin {
1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021
  // Collects the given candidates into groups by directionality. The candidates
  // have already been sorted as if they all had the directionality of the
  // nearest Directionality ancestor.
  List<_ReadingOrderDirectionalGroupData> _collectDirectionalityGroups(Iterable<_ReadingOrderSortData> candidates) {
    TextDirection currentDirection = candidates.first.directionality;
    List<_ReadingOrderSortData> currentGroup = <_ReadingOrderSortData>[];
    final List<_ReadingOrderDirectionalGroupData> result = <_ReadingOrderDirectionalGroupData>[];
    // Split candidates into runs of the same directionality.
    for (final _ReadingOrderSortData candidate in candidates) {
      if (candidate.directionality == currentDirection) {
        currentGroup.add(candidate);
        continue;
      }
      currentDirection = candidate.directionality;
      result.add(_ReadingOrderDirectionalGroupData(currentGroup));
      currentGroup = <_ReadingOrderSortData>[candidate];
1022
    }
1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033
    if (currentGroup.isNotEmpty) {
      result.add(_ReadingOrderDirectionalGroupData(currentGroup));
    }
    // Sort each group separately. Each group has the same directionality.
    for (final _ReadingOrderDirectionalGroupData bandGroup in result) {
      if (bandGroup.members.length == 1) {
        continue; // No need to sort one node.
      }
      _ReadingOrderSortData.sortWithDirectionality(bandGroup.members, bandGroup.directionality);
    }
    return result;
1034 1035
  }

1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046
  _ReadingOrderSortData _pickNext(List<_ReadingOrderSortData> candidates) {
    // Find the topmost node by sorting on the top of the rectangles.
    mergeSort<_ReadingOrderSortData>(candidates, compare: (_ReadingOrderSortData a, _ReadingOrderSortData b) => a.rect.top.compareTo(b.rect.top));
    final _ReadingOrderSortData topmost = candidates.first;

    // Find the candidates that are in the same horizontal band as the current one.
    List<_ReadingOrderSortData> inBand(_ReadingOrderSortData current, Iterable<_ReadingOrderSortData> candidates) {
      final Rect band = Rect.fromLTRB(double.negativeInfinity, current.rect.top, double.infinity, current.rect.bottom);
      return candidates.where((_ReadingOrderSortData item) {
        return !item.rect.intersect(band).isEmpty;
      }).toList();
1047 1048
    }

1049 1050 1051 1052 1053 1054 1055
    final List<_ReadingOrderSortData> inBandOfTop = inBand(topmost, candidates);
    // It has to have at least topmost in it if the topmost is not degenerate.
    assert(topmost.rect.isEmpty || inBandOfTop.isNotEmpty);

    // The topmost rect in is in a band by itself, so just return that one.
    if (inBandOfTop.length <= 1) {
      return topmost;
1056 1057
    }

1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079
    // Now that we know there are others in the same band as the topmost, then pick
    // the one at the beginning, depending on the text direction in force.

    // Find out the directionality of the nearest common Directionality
    // ancestor for all nodes. This provides a base directionality to use for
    // the ordering of the groups.
    final TextDirection nearestCommonDirectionality = _ReadingOrderSortData.commonDirectionalityOf(inBandOfTop);

    // Do an initial common-directionality-based sort to get consistent geometric
    // ordering for grouping into directionality groups. It has to use the
    // common directionality to be able to group into sane groups for the
    // given directionality, since rectangles can overlap and give different
    // results for different directionalities.
    _ReadingOrderSortData.sortWithDirectionality(inBandOfTop, nearestCommonDirectionality);

    // Collect the top band into internally sorted groups with shared directionality.
    final List<_ReadingOrderDirectionalGroupData> bandGroups = _collectDirectionalityGroups(inBandOfTop);
    if (bandGroups.length == 1) {
      // There's only one directionality group, so just send back the first
      // one in that group, since it's already sorted.
      return bandGroups.first.members.first;
    }
1080

1081 1082 1083 1084
    // Sort the groups based on the common directionality and bounding boxes.
    _ReadingOrderDirectionalGroupData.sortWithDirectionality(bandGroups, nearestCommonDirectionality);
    return bandGroups.first.members.first;
  }
1085

1086 1087 1088
  // Sorts the list of nodes based on their geometry into the desired reading
  // order based on the directionality of the context for each node.
  @override
1089
  Iterable<FocusNode> sortDescendants(Iterable<FocusNode> descendants, FocusNode currentNode) {
1090 1091 1092
    assert(descendants != null);
    if (descendants.length <= 1) {
      return descendants;
1093 1094
    }

1095 1096
    final List<_ReadingOrderSortData> data = <_ReadingOrderSortData>[
      for (final FocusNode node in descendants) _ReadingOrderSortData(node),
1097
    ];
1098

1099 1100 1101 1102 1103 1104 1105
    final List<FocusNode> sortedList = <FocusNode>[];
    final List<_ReadingOrderSortData> unplaced = data;

    // Pick the initial widget as the one that is at the beginning of the band
    // of the topmost, or the topmost, if there are no others in its band.
    _ReadingOrderSortData current = _pickNext(unplaced);
    sortedList.add(current.node);
1106 1107
    unplaced.remove(current);

1108 1109 1110
    // Go through each node, picking the next one after eliminating the previous
    // one, since removing the previously picked node will expose a new band in
    // which to choose candidates.
1111
    while (unplaced.isNotEmpty) {
1112
      final _ReadingOrderSortData next = _pickNext(unplaced);
1113
      current = next;
1114
      sortedList.add(current.node);
1115 1116
      unplaced.remove(current);
    }
1117
    return sortedList;
1118
  }
1119
}
1120

1121 1122 1123 1124
/// Base class for all sort orders for [OrderedTraversalPolicy] traversal.
///
/// {@template flutter.widgets.focusorder.comparable}
/// Only orders of the same type are comparable. If a set of widgets in the same
1125 1126 1127 1128
/// [FocusTraversalGroup] contains orders that are not comparable with each
/// other, it will assert, since the ordering between such keys is undefined. To
/// avoid collisions, use a [FocusTraversalGroup] to group similarly ordered
/// widgets together.
1129
///
1130 1131 1132
/// When overriding, [FocusOrder.doCompare] must be overridden instead of
/// [FocusOrder.compareTo], which calls [FocusOrder.doCompare] to do the actual
/// comparison.
1133 1134 1135 1136
/// {@endtemplate}
///
/// See also:
///
1137 1138 1139 1140 1141 1142 1143 1144
/// * [FocusTraversalGroup], a widget that groups together and imposes a
///   traversal policy on the [Focus] nodes below it in the widget hierarchy.
/// * [FocusTraversalOrder], a widget that assigns an order to a widget subtree
///   for the [OrderedTraversalPolicy] to use.
/// * [NumericFocusOrder], for a focus order that describes its order with a
///   `double`.
/// * [LexicalFocusOrder], a focus order that assigns a string-based lexical
///   traversal order to a [FocusTraversalOrder] widget.
1145
@immutable
1146
abstract class FocusOrder with Diagnosticable implements Comparable<FocusOrder> {
1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193
  /// Abstract const constructor. This constructor enables subclasses to provide
  /// const constructors so that they can be used in const expressions.
  const FocusOrder();

  /// Compares this object to another [Comparable].
  ///
  /// When overriding [FocusOrder], implement [doCompare] instead of this
  /// function to do the actual comparison.
  ///
  /// Returns a value like a [Comparator] when comparing `this` to [other].
  /// That is, it returns a negative integer if `this` is ordered before [other],
  /// a positive integer if `this` is ordered after [other],
  /// and zero if `this` and [other] are ordered together.
  ///
  /// The [other] argument must be a value that is comparable to this object.
  @override
  @nonVirtual
  int compareTo(FocusOrder other) {
    assert(
        runtimeType == other.runtimeType,
        "The sorting algorithm must not compare incomparable keys, since they don't "
        'know how to order themselves relative to each other. Comparing $this with $other');
    return doCompare(other);
  }

  /// The subclass implementation called by [compareTo] to compare orders.
  ///
  /// The argument is guaranteed to be of the same [runtimeType] as this object.
  ///
  /// The method should return a negative number if this object comes earlier in
  /// the sort order than the `other` argument; and a positive number if it
  /// comes later in the sort order than `other`. Returning zero causes the
  /// system to fall back to the secondary sort order defined by
  /// [OrderedTraversalPolicy.secondary]
  @protected
  int doCompare(covariant FocusOrder other);
}

/// Can be given to a [FocusTraversalOrder] widget to assign a numerical order
/// to a widget subtree that is using a [OrderedTraversalPolicy] to define the
/// order in which widgets should be traversed with the keyboard.
///
/// {@macro flutter.widgets.focusorder.comparable}
///
/// See also:
///
///  * [FocusTraversalOrder], a widget that assigns an order to a widget subtree
1194
///    for the [OrderedTraversalPolicy] to use.
1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231
class NumericFocusOrder extends FocusOrder {
  /// Const constructor. This constructor enables subclasses to provide
  /// const constructors so that they can be used in const expressions.
  const NumericFocusOrder(this.order) : assert(order != null);

  /// The numerical order to assign to the widget subtree using
  /// [FocusTraversalOrder].
  ///
  /// Determines the placement of this widget in a sequence of widgets that defines
  /// the order in which this node is traversed by the focus policy.
  ///
  /// Lower values will be traversed first.
  final double order;

  @override
  int doCompare(NumericFocusOrder other) => order.compareTo(other.order);

  @override
  void debugFillProperties(DiagnosticPropertiesBuilder properties) {
    super.debugFillProperties(properties);
    properties.add(DoubleProperty('order', order));
  }
}

/// Can be given to a [FocusTraversalOrder] widget to use a String to assign a
/// lexical order to a widget subtree that is using a
/// [OrderedTraversalPolicy] to define the order in which widgets should be
/// traversed with the keyboard.
///
/// This sorts strings using Dart's default string comparison, which is not
/// locale specific.
///
/// {@macro flutter.widgets.focusorder.comparable}
///
/// See also:
///
///  * [FocusTraversalOrder], a widget that assigns an order to a widget subtree
1232
///    for the [OrderedTraversalPolicy] to use.
1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336
class LexicalFocusOrder extends FocusOrder {
  /// Const constructor. This constructor enables subclasses to provide
  /// const constructors so that they can be used in const expressions.
  const LexicalFocusOrder(this.order) : assert(order != null);

  /// The String that defines the lexical order to assign to the widget subtree
  /// using [FocusTraversalOrder].
  ///
  /// Determines the placement of this widget in a sequence of widgets that defines
  /// the order in which this node is traversed by the focus policy.
  ///
  /// Lower lexical values will be traversed first (e.g. 'a' comes before 'z').
  final String order;

  @override
  int doCompare(LexicalFocusOrder other) => order.compareTo(other.order);

  @override
  void debugFillProperties(DiagnosticPropertiesBuilder properties) {
    super.debugFillProperties(properties);
    properties.add(StringProperty('order', order));
  }
}

// Used to help sort the focus nodes in an OrderedFocusTraversalPolicy.
class _OrderedFocusInfo {
  const _OrderedFocusInfo({@required this.node, @required this.order})
      : assert(node != null),
        assert(order != null);

  final FocusNode node;
  final FocusOrder order;
}

/// A [FocusTraversalPolicy] that orders nodes by an explicit order that resides
/// in the nearest [FocusTraversalOrder] widget ancestor.
///
/// {@macro flutter.widgets.focusorder.comparable}
///
/// {@tool dartpad --template=stateless_widget_scaffold_center}
/// This sample shows how to assign a traversal order to a widget. In the
/// example, the focus order goes from bottom right (the "One" button) to top
/// left (the "Six" button).
///
/// ```dart preamble
/// class DemoButton extends StatelessWidget {
///   const DemoButton({this.name, this.autofocus = false, this.order});
///
///   final String name;
///   final bool autofocus;
///   final double order;
///
///   void _handleOnPressed() {
///     print('Button $name pressed.');
///     debugDumpFocusTree();
///   }
///
///   @override
///   Widget build(BuildContext context) {
///     return FocusTraversalOrder(
///       order: NumericFocusOrder(order),
///       child: FlatButton(
///         autofocus: autofocus,
///         focusColor: Colors.red,
///         onPressed: () => _handleOnPressed(),
///         child: Text(name),
///       ),
///     );
///   }
/// }
/// ```
///
/// ```dart
/// Widget build(BuildContext context) {
///   return FocusTraversalGroup(
///     policy: OrderedTraversalPolicy(),
///     child: Column(
///       mainAxisAlignment: MainAxisAlignment.center,
///       children: <Widget>[
///         Row(
///           mainAxisAlignment: MainAxisAlignment.center,
///           children: const <Widget>[
///             DemoButton(name: 'Six', order: 6),
///           ],
///         ),
///         Row(
///           mainAxisAlignment: MainAxisAlignment.center,
///           children: const <Widget>[
///             DemoButton(name: 'Five', order: 5),
///             DemoButton(name: 'Four', order: 4),
///           ],
///         ),
///         Row(
///           mainAxisAlignment: MainAxisAlignment.center,
///           children: const <Widget>[
///             DemoButton(name: 'Three', order: 3),
///             DemoButton(name: 'Two', order: 2),
///             DemoButton(name: 'One', order: 1, autofocus: true),
///           ],
///         ),
///       ],
///     ),
///   );
/// }
1337
/// ```
1338 1339 1340 1341
/// {@end-tool}
///
/// See also:
///
1342 1343 1344
///  * [FocusTraversalGroup], a widget that groups together and imposes a
///    traversal policy on the [Focus] nodes below it in the widget hierarchy.
///  * [WidgetOrderTraversalPolicy], a policy that relies on the widget
1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373
///    creation order to describe the order of traversal.
///  * [ReadingOrderTraversalPolicy], a policy that describes the order as the
///    natural "reading order" for the current [Directionality].
///  * [NumericFocusOrder], a focus order that assigns a numeric traversal order
///    to a [FocusTraversalOrder] widget.
///  * [LexicalFocusOrder], a focus order that assigns a string-based lexical
///    traversal order to a [FocusTraversalOrder] widget.
///  * [FocusOrder], an abstract base class for all types of focus traversal
///    orderings.
class OrderedTraversalPolicy extends FocusTraversalPolicy with DirectionalFocusTraversalPolicyMixin {
  /// Constructs a traversal policy that orders widgets for keyboard traversal
  /// based on an explicit order.
  ///
  /// If [secondary] is null, it will default to [ReadingOrderTraversalPolicy].
  OrderedTraversalPolicy({this.secondary});

  /// This is the policy that is used when a node doesn't have an order
  /// assigned, or when multiple nodes have orders which are identical.
  ///
  /// If not set, this defaults to [ReadingOrderTraversalPolicy].
  ///
  /// This policy determines the secondary sorting order of nodes which evaluate
  /// as having an identical order (including those with no order specified).
  ///
  /// Nodes with no order specified will be sorted after nodes with an explicit
  /// order.
  final FocusTraversalPolicy secondary;

  @override
1374
  Iterable<FocusNode> sortDescendants(Iterable<FocusNode> descendants, FocusNode currentNode) {
1375
    final FocusTraversalPolicy secondaryPolicy = secondary ?? ReadingOrderTraversalPolicy();
1376
    final Iterable<FocusNode> sortedDescendants = secondaryPolicy.sortDescendants(descendants, currentNode);
1377 1378 1379 1380 1381 1382 1383 1384
    final List<FocusNode> unordered = <FocusNode>[];
    final List<_OrderedFocusInfo> ordered = <_OrderedFocusInfo>[];
    for (final FocusNode node in sortedDescendants) {
      final FocusOrder order = FocusTraversalOrder.of(node.context, nullOk: true);
      if (order != null) {
        ordered.add(_OrderedFocusInfo(node: node, order: order));
      } else {
        unordered.add(node);
1385
      }
1386
    }
1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399
    mergeSort<_OrderedFocusInfo>(ordered, compare: (_OrderedFocusInfo a, _OrderedFocusInfo b) {
      assert(
        a.order.runtimeType == b.order.runtimeType,
        'When sorting nodes for determining focus order, the order (${a.order}) of '
        "node ${a.node}, isn't the same type as the order (${b.order}) of ${b.node}. "
        "Incompatible order types can't be compared.  Use a FocusTraversalGroup to group "
        'similar orders together.',
      );
      return a.order.compareTo(b.order);
    });
    return ordered.map<FocusNode>((_OrderedFocusInfo info) => info.node).followedBy(unordered);
  }
}
1400

1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431
/// An inherited widget that describes the order in which its child subtree
/// should be traversed.
///
/// {@macro flutter.widgets.focusorder.comparable}
///
/// The order for a widget is determined by the [FocusOrder] returned by
/// [FocusTraversalOrder.of] for a particular context.
class FocusTraversalOrder extends InheritedWidget {
  /// A const constructor so that subclasses can be const.
  const FocusTraversalOrder({Key key, this.order, Widget child}) : super(key: key, child: child);

  /// The order for the widget descendants of this [FocusTraversalOrder].
  final FocusOrder order;

  /// Finds the [FocusOrder] in the nearest ancestor [FocusTraversalOrder] widget.
  ///
  /// It does not create a rebuild dependency because changing the traversal
  /// order doesn't change the widget tree, so nothing needs to be rebuilt as a
  /// result of an order change.
  static FocusOrder of(BuildContext context, {bool nullOk = false}) {
    assert(context != null);
    assert(nullOk != null);
    final FocusTraversalOrder marker = context.getElementForInheritedWidgetOfExactType<FocusTraversalOrder>()?.widget as FocusTraversalOrder;
    final FocusOrder order = marker?.order;
    if (order == null && !nullOk) {
      throw FlutterError('FocusTraversalOrder.of() was called with a context that '
          'does not contain a TraversalOrder widget. No TraversalOrder widget '
          'ancestor could be found starting from the context that was passed to '
          'FocusTraversalOrder.of().\n'
          'The context used was:\n'
          '  $context');
1432
    }
1433
    return order;
1434 1435
  }

1436 1437
  // Since the order of traversal doesn't affect display of anything, we don't
  // need to force a rebuild of anything that depends upon it.
1438
  @override
1439
  bool updateShouldNotify(InheritedWidget oldWidget) => false;
1440 1441

  @override
1442 1443 1444 1445
  void debugFillProperties(DiagnosticPropertiesBuilder properties) {
    super.debugFillProperties(properties);
    properties.add(DiagnosticsProperty<FocusOrder>('order', order));
  }
1446 1447
}

1448 1449 1450 1451 1452 1453 1454
/// A widget that describes the inherited focus policy for focus traversal for
/// its descendants, grouping them into a separate traversal group.
///
/// A traversal group is treated as one entity when sorted by the traversal
/// algorithm, so it can be used to segregate different parts of the widget tree
/// that need to be sorted using different algorithms and/or sort orders when
/// using an [OrderedTraversalPolicy].
1455
///
1456 1457 1458 1459
/// Within the group, it will use the given [policy] to order the elements. The
/// group itself will be ordered using the parent group's policy.
///
/// By default, traverses in reading order using [ReadingOrderTraversalPolicy].
1460
///
1461 1462 1463
/// To prevent the members of the group from being focused, set the
/// [descendantsAreFocusable] attribute to true.
///
1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530
/// {@tool dartpad --template=stateless_widget_material}
/// This sample shows three rows of buttons, each grouped by a
/// [FocusTraversalGroup], each with different traversal order policies. Use tab
/// traversal to see the order they are traversed in.  The first row follows a
/// numerical order, the second follows a lexical order (ordered to traverse
/// right to left), and the third ignores the numerical order assigned to it and
/// traverses in widget order.
///
/// ```dart preamble
/// /// A button wrapper that adds either a numerical or lexical order, depending on
/// /// the type of T.
/// class OrderedButton<T> extends StatefulWidget {
///   const OrderedButton({
///     this.name,
///     this.canRequestFocus = true,
///     this.autofocus = false,
///     this.order,
///   });
///
///   final String name;
///   final bool canRequestFocus;
///   final bool autofocus;
///   final T order;
///
///   @override
///   _OrderedButtonState createState() => _OrderedButtonState();
/// }
///
/// class _OrderedButtonState<T> extends State<OrderedButton<T>> {
///   FocusNode focusNode;
///
///   @override
///   void initState() {
///     super.initState();
///     focusNode = FocusNode(
///       debugLabel: widget.name,
///       canRequestFocus: widget.canRequestFocus,
///     );
///   }
///
///   @override
///   void dispose() {
///     focusNode?.dispose();
///     super.dispose();
///   }
///
///   @override
///   void didUpdateWidget(OrderedButton oldWidget) {
///     super.didUpdateWidget(oldWidget);
///     focusNode.canRequestFocus = widget.canRequestFocus;
///   }
///
///   void _handleOnPressed() {
///     focusNode.requestFocus();
///     print('Button ${widget.name} pressed.');
///     debugDumpFocusTree();
///   }
///
///   @override
///   Widget build(BuildContext context) {
///     FocusOrder order;
///     if (widget.order is num) {
///       order = NumericFocusOrder((widget.order as num).toDouble());
///     } else {
///       order = LexicalFocusOrder(widget.order.toString());
///     }
///
1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547
///     Color overlayColor(Set<MaterialState> states) {
///       if (states.contains(MaterialState.focused)) {
///         return Colors.red;
///       }
///       if (states.contains(MaterialState.hovered)) {
///         return Colors.blue;
///       }
///       return null;  // defer to the default overlayColor
///     }
///
///     Color foregroundColor(Set<MaterialState> states) {
///       if (states.contains(MaterialState.focused) || states.contains(MaterialState.hovered)) {
///         return Colors.white;
///       }
///       return null;  // defer to the default foregroundColor
///     }
///
1548 1549 1550 1551
///     return FocusTraversalOrder(
///       order: order,
///       child: Padding(
///         padding: const EdgeInsets.all(8.0),
1552
///         child: OutlinedButton(
1553 1554
///           focusNode: focusNode,
///           autofocus: widget.autofocus,
1555 1556 1557 1558
///           style: ButtonStyle(
///             overlayColor: MaterialStateProperty.resolveWith<Color>(overlayColor),
///             foregroundColor: MaterialStateProperty.resolveWith<Color>(foregroundColor),
///           ),
1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632
///           onPressed: () => _handleOnPressed(),
///           child: Text(widget.name),
///         ),
///       ),
///     );
///   }
/// }
/// ```
///
/// ```dart
/// Widget build(BuildContext context) {
///   return Container(
///     color: Colors.white,
///     child: FocusTraversalGroup(
///       policy: OrderedTraversalPolicy(),
///       child: Column(
///         mainAxisAlignment: MainAxisAlignment.center,
///         children: <Widget>[
///           // A group that is ordered with a numerical order, from left to right.
///           FocusTraversalGroup(
///             policy: OrderedTraversalPolicy(),
///             child: Row(
///               mainAxisAlignment: MainAxisAlignment.center,
///               children: List<Widget>.generate(3, (int index) {
///                 return OrderedButton<num>(
///                   name: 'num: $index',
///                   // TRY THIS: change this to "3 - index" and see how the order changes.
///                   order: index,
///                 );
///               }),
///             ),
///           ),
///           // A group that is ordered with a lexical order, from right to left.
///           FocusTraversalGroup(
///             policy: OrderedTraversalPolicy(),
///             child: Row(
///               mainAxisAlignment: MainAxisAlignment.center,
///               children: List<Widget>.generate(3, (int index) {
///                 // Order as "C" "B", "A".
///                 String order =
///                     String.fromCharCode('A'.codeUnitAt(0) + (2 - index));
///                 return OrderedButton<String>(
///                   name: 'String: $order',
///                   order: order,
///                 );
///               }),
///             ),
///           ),
///           // A group that orders in widget order, regardless of what the order is set to.
///           FocusTraversalGroup(
///             // Note that because this is NOT an OrderedTraversalPolicy, the
///             // assigned order of these OrderedButtons is ignored, and they
///             // are traversed in widget order. TRY THIS: change this to
///             // "OrderedTraversalPolicy()" and see that it now follows the
///             // numeric order set on them instead of the widget order.
///             policy: WidgetOrderTraversalPolicy(),
///             child: Row(
///               mainAxisAlignment: MainAxisAlignment.center,
///               children: List<Widget>.generate(3, (int index) {
///                 return OrderedButton<num>(
///                   name: 'ignored num: ${3 - index}',
///                   order: 3 - index,
///                 );
///               }),
///             ),
///           ),
///         ],
///       ),
///     ),
///   );
/// }
/// ```
/// {@end-tool}
///
1633 1634
/// See also:
///
1635
///  * [FocusNode], for a description of the focus system.
1636
///  * [WidgetOrderTraversalPolicy], a policy that relies on the widget
1637 1638 1639 1640 1641
///    creation order to describe the order of traversal.
///  * [ReadingOrderTraversalPolicy], a policy that describes the order as the
///    natural "reading order" for the current [Directionality].
///  * [DirectionalFocusTraversalPolicyMixin] a mixin class that implements
///    focus traversal in a direction.
1642 1643 1644
class FocusTraversalGroup extends StatefulWidget {
  /// Creates a [FocusTraversalGroup] object.
  ///
1645
  /// The [child] and [descendantsAreFocusable] arguments must not be null.
1646 1647 1648
  FocusTraversalGroup({
    Key key,
    FocusTraversalPolicy policy,
1649
    this.descendantsAreFocusable = true,
1650
    @required this.child,
1651 1652
  })  : assert(descendantsAreFocusable != null),
        policy = policy ?? ReadingOrderTraversalPolicy(),
1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671
        super(key: key);

  /// The policy used to move the focus from one focus node to another when
  /// traversing them using a keyboard.
  ///
  /// If not specified, traverses in reading order using
  /// [ReadingOrderTraversalPolicy].
  ///
  /// See also:
  ///
  ///  * [FocusTraversalPolicy] for the API used to impose traversal order
  ///    policy.
  ///  * [WidgetOrderTraversalPolicy] for a traversal policy that traverses
  ///    nodes in the order they are added to the widget tree.
  ///  * [ReadingOrderTraversalPolicy] for a traversal policy that traverses
  ///    nodes in the reading order defined in the widget tree, and then top to
  ///    bottom.
  final FocusTraversalPolicy policy;

1672 1673 1674 1675 1676 1677 1678 1679
  /// {@macro flutter.widgets.Focus.descendantsAreFocusable}
  final bool descendantsAreFocusable;

  /// The child widget of this [FocusTraversalGroup].
  ///
  /// {@macro flutter.widgets.child}
  final Widget child;

1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757
  /// Returns the focus policy set by the [FocusTraversalGroup] that most
  /// tightly encloses the given [BuildContext].
  ///
  /// It does not create a rebuild dependency because changing the traversal
  /// order doesn't change the widget tree, so nothing needs to be rebuilt as a
  /// result of an order change.
  ///
  /// Will assert if no [FocusTraversalGroup] ancestor is found, and `nullOk` is false.
  ///
  /// If `nullOk` is true, then it will return null if it doesn't find a
  /// [FocusTraversalGroup] ancestor.
  static FocusTraversalPolicy of(BuildContext context, {bool nullOk = false}) {
    assert(context != null);
    final _FocusTraversalGroupMarker inherited = context?.dependOnInheritedWidgetOfExactType<_FocusTraversalGroupMarker>();
    assert(() {
      if (nullOk) {
        return true;
      }
      if (inherited == null) {
        throw FlutterError(
          'Unable to find a FocusTraversalGroup widget in the context.\n'
          'FocusTraversalGroup.of() was called with a context that does not contain a '
          'FocusTraversalGroup.\n'
          'No FocusTraversalGroup ancestor could be found starting from the context that was '
          'passed to FocusTraversalGroup.of(). This can happen because there is not a '
          'WidgetsApp or MaterialApp widget (those widgets introduce a FocusTraversalGroup), '
          'or it can happen if the context comes from a widget above those widgets.\n'
          'The context used was:\n'
          '  $context',
        );
      }
      return true;
    }());
    return inherited?.policy;
  }

  @override
  _FocusTraversalGroupState createState() => _FocusTraversalGroupState();

  @override
  void debugFillProperties(DiagnosticPropertiesBuilder properties) {
    super.debugFillProperties(properties);
    properties.add(DiagnosticsProperty<FocusTraversalPolicy>('policy', policy));
  }
}

class _FocusTraversalGroupState extends State<FocusTraversalGroup> {
  // The internal focus node used to collect the children of this node into a
  // group, and to provide a context for the traversal algorithm to sort the
  // group with.
  FocusNode focusNode;

  @override
  void initState() {
    super.initState();
    focusNode = FocusNode(
      canRequestFocus: false,
      skipTraversal: true,
      debugLabel: 'FocusTraversalGroup',
    );
  }

  @override
  void dispose() {
    focusNode?.dispose();
    super.dispose();
  }

  @override
  Widget build(BuildContext context) {
    return _FocusTraversalGroupMarker(
      policy: widget.policy,
      focusNode: focusNode,
      child: Focus(
        focusNode: focusNode,
        canRequestFocus: false,
        skipTraversal: true,
        includeSemantics: false,
1758
        descendantsAreFocusable: widget.descendantsAreFocusable,
1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781
        child: widget.child,
      ),
    );
  }
}

// A "marker" inherited widget to make the group faster to find.
class _FocusTraversalGroupMarker extends InheritedWidget {
  const _FocusTraversalGroupMarker({
    @required this.policy,
    @required this.focusNode,
    Widget child,
  })  : assert(policy != null),
        assert(focusNode != null),
        super(child: child);

  final FocusTraversalPolicy policy;
  final FocusNode focusNode;

  @override
  bool updateShouldNotify(InheritedWidget oldWidget) => false;
}

1782 1783 1784 1785 1786 1787 1788
/// An intent for use with the [RequestFocusAction], which supplies the
/// [FocusNode] that should be focused.
class RequestFocusIntent extends Intent {
  /// A const constructor for a [RequestFocusIntent], so that subclasses may be
  /// const.
  const RequestFocusIntent(this.focusNode)
      : assert(focusNode != null);
1789

1790 1791
  /// The [FocusNode] that is to be focused.
  final FocusNode focusNode;
1792 1793
}

1794 1795
/// An [Action] that requests the focus on the node it is given in its
/// [RequestFocusIntent].
1796 1797 1798 1799 1800
///
/// This action can be used to request focus for a particular node, by calling
/// [Action.invoke] like so:
///
/// ```dart
1801
/// Actions.invoke(context, const RequestFocusIntent(focusNode));
1802 1803
/// ```
///
1804
/// Where the `focusNode` is the node for which the focus will be requested.
1805 1806
///
/// The difference between requesting focus in this way versus calling
1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818
/// [FocusNode.requestFocus] directly is that it will use the [Action]
/// registered in the nearest [Actions] widget associated with
/// [RequestFocusIntent] to make the request, rather than just requesting focus
/// directly. This allows the action to have additional side effects, like
/// logging, or undo and redo functionality.
///
/// This [RequestFocusAction] class is the default action associated with the
/// [RequestFocusIntent] in the [WidgetsApp], and it simply requests focus. You
/// can redefine the associated action with your own [Actions] widget.
///
/// See [FocusTraversalPolicy] for more information about focus traversal.
class RequestFocusAction extends Action<RequestFocusIntent> {
1819
  @override
1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831
  void invoke(RequestFocusIntent intent) {
    _focusAndEnsureVisible(intent.focusNode);
  }
}

/// An [Intent] bound to [NextFocusAction], which moves the focus to the next
/// focusable node in the focus traversal order.
///
/// See [FocusTraversalPolicy] for more information about focus traversal.
class NextFocusIntent extends Intent {
  /// Creates a const [NextFocusIntent] so subclasses can be const.
  const NextFocusIntent();
1832 1833 1834 1835 1836
}

/// An [Action] that moves the focus to the next focusable node in the focus
/// order.
///
1837 1838 1839 1840 1841
/// This action is the default action registered for the [NextFocusIntent], and
/// by default is bound to the [LogicalKeyboardKey.tab] key in the [WidgetsApp].
///
/// See [FocusTraversalPolicy] for more information about focus traversal.
class NextFocusAction extends Action<NextFocusIntent> {
1842
  @override
1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854
  void invoke(NextFocusIntent intent) {
    primaryFocus.nextFocus();
  }
}

/// An [Intent] bound to [PreviousFocusAction], which moves the focus to the
/// previous focusable node in the focus traversal order.
///
/// See [FocusTraversalPolicy] for more information about focus traversal.
class PreviousFocusIntent extends Intent {
  /// Creates a const [PreviousFocusIntent] so subclasses can be const.
  const PreviousFocusIntent();
1855 1856 1857 1858 1859
}

/// An [Action] that moves the focus to the previous focusable node in the focus
/// order.
///
1860 1861 1862 1863 1864 1865
/// This action is the default action registered for the [PreviousFocusIntent],
/// and by default is bound to a combination of the [LogicalKeyboardKey.tab] key
/// and the [LogicalKeyboardKey.shift] key in the [WidgetsApp].
///
/// See [FocusTraversalPolicy] for more information about focus traversal.
class PreviousFocusAction extends Action<PreviousFocusIntent> {
1866
  @override
1867 1868 1869
  void invoke(PreviousFocusIntent intent) {
    primaryFocus.previousFocus();
  }
1870 1871 1872 1873 1874 1875 1876 1877 1878
}

/// An [Intent] that represents moving to the next focusable node in the given
/// [direction].
///
/// This is the [Intent] bound by default to the [LogicalKeyboardKey.arrowUp],
/// [LogicalKeyboardKey.arrowDown], [LogicalKeyboardKey.arrowLeft], and
/// [LogicalKeyboardKey.arrowRight] keys in the [WidgetsApp], with the
/// appropriate associated directions.
1879 1880
///
/// See [FocusTraversalPolicy] for more information about focus traversal.
1881
class DirectionalFocusIntent extends Intent {
1882 1883
  /// Creates a [DirectionalFocusIntent] intending to move the focus in the
  /// given [direction].
1884
  const DirectionalFocusIntent(this.direction, {this.ignoreTextFields = true})
1885
      : assert(ignoreTextFields != null);
1886 1887 1888 1889

  /// The direction in which to look for the next focusable node when the
  /// associated [DirectionalFocusAction] is invoked.
  final TraversalDirection direction;
1890 1891 1892 1893 1894 1895 1896

  /// If true, then directional focus actions that occur within a text field
  /// will not happen when the focus node which received the key is a text
  /// field.
  ///
  /// Defaults to true.
  final bool ignoreTextFields;
1897 1898
}

1899 1900
/// An [Action] that moves the focus to the focusable node in the direction
/// configured by the associated [DirectionalFocusIntent.direction].
1901
///
1902 1903
/// This is the [Action] associated with [DirectionalFocusIntent] and bound by
/// default to the [LogicalKeyboardKey.arrowUp], [LogicalKeyboardKey.arrowDown],
1904 1905
/// [LogicalKeyboardKey.arrowLeft], and [LogicalKeyboardKey.arrowRight] keys in
/// the [WidgetsApp], with the appropriate associated directions.
1906
class DirectionalFocusAction extends Action<DirectionalFocusIntent> {
1907
  @override
1908 1909 1910
  void invoke(DirectionalFocusIntent intent) {
    if (!intent.ignoreTextFields || primaryFocus.context.widget is! EditableText) {
      primaryFocus.focusInDirection(intent.direction);
1911
    }
1912 1913
  }
}