1 /* 2 * Copyright (C) 2020 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.android.car.rotary; 17 18 import static android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction.ACTION_SCROLL_BACKWARD; 19 import static android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction.ACTION_SCROLL_FORWARD; 20 21 import android.graphics.Rect; 22 import android.os.SystemClock; 23 import android.view.View; 24 import android.view.accessibility.AccessibilityNodeInfo; 25 import android.view.accessibility.AccessibilityWindowInfo; 26 27 import androidx.annotation.NonNull; 28 import androidx.annotation.Nullable; 29 import androidx.annotation.VisibleForTesting; 30 31 import com.android.car.ui.FocusArea; 32 import com.android.car.ui.FocusParkingView; 33 34 import java.util.ArrayList; 35 import java.util.Iterator; 36 import java.util.List; 37 38 /** 39 * A helper class used for finding the next focusable node when the rotary controller is rotated or 40 * nudged. 41 */ 42 class Navigator { 43 44 @NonNull 45 private NodeCopier mNodeCopier = new NodeCopier(); 46 47 @NonNull 48 private final TreeTraverser mTreeTraverser = new TreeTraverser(); 49 50 private final RotaryCache mRotaryCache; 51 52 private final int mHunLeft; 53 private final int mHunRight; 54 55 @View.FocusRealDirection 56 private int mHunNudgeDirection; 57 Navigator(@otaryCache.CacheType int focusHistoryCacheType, int focusHistoryCacheSize, int focusHistoryExpirationTimeMs, @RotaryCache.CacheType int focusAreaHistoryCacheType, int focusAreaHistoryCacheSize, int focusAreaHistoryExpirationTimeMs, @RotaryCache.CacheType int focusWindowCacheType, int focusWindowCacheSize, int focusWindowExpirationTimeMs, int hunLeft, int hunRight, boolean showHunOnBottom)58 Navigator(@RotaryCache.CacheType int focusHistoryCacheType, 59 int focusHistoryCacheSize, 60 int focusHistoryExpirationTimeMs, 61 @RotaryCache.CacheType int focusAreaHistoryCacheType, 62 int focusAreaHistoryCacheSize, 63 int focusAreaHistoryExpirationTimeMs, 64 @RotaryCache.CacheType int focusWindowCacheType, 65 int focusWindowCacheSize, 66 int focusWindowExpirationTimeMs, 67 int hunLeft, 68 int hunRight, 69 boolean showHunOnBottom) { 70 mRotaryCache = new RotaryCache(focusHistoryCacheType, 71 focusHistoryCacheSize, 72 focusHistoryExpirationTimeMs, 73 focusAreaHistoryCacheType, 74 focusAreaHistoryCacheSize, 75 focusAreaHistoryExpirationTimeMs, 76 focusWindowCacheType, 77 focusWindowCacheSize, 78 focusWindowExpirationTimeMs); 79 mHunLeft = hunLeft; 80 mHunRight = hunRight; 81 mHunNudgeDirection = showHunOnBottom ? View.FOCUS_DOWN : View.FOCUS_UP; 82 } 83 84 /** Clears focus area history cache. */ clearFocusAreaHistory()85 void clearFocusAreaHistory() { 86 mRotaryCache.clearFocusAreaHistory(); 87 } 88 89 /** Caches the focused node by focus area and by window. */ saveFocusedNode(@onNull AccessibilityNodeInfo focusedNode)90 void saveFocusedNode(@NonNull AccessibilityNodeInfo focusedNode) { 91 long elapsedRealtime = SystemClock.elapsedRealtime(); 92 AccessibilityNodeInfo focusArea = getAncestorFocusArea(focusedNode); 93 mRotaryCache.saveFocusedNode(focusArea, focusedNode, elapsedRealtime); 94 mRotaryCache.saveWindowFocus(focusedNode, elapsedRealtime); 95 Utils.recycleNode(focusArea); 96 } 97 98 /** 99 * Returns the most recently focused valid node or {@code null} if there are no valid nodes 100 * saved by {@link #saveFocusedNode}. The caller is responsible for recycling the result. 101 */ getMostRecentFocus()102 AccessibilityNodeInfo getMostRecentFocus() { 103 return mRotaryCache.getMostRecentFocus(SystemClock.elapsedRealtime()); 104 } 105 106 /** 107 * Returns the target focusable for a nudge: 108 * <ol> 109 * <li>If the HUN is present and the nudge is towards it, a focusable in the HUN is 110 * returned. See {@link #findHunNudgeTarget} for details. 111 * <li>Otherwise, a target focus area is chosen, either from the focus area history or by 112 * choosing the best candidate. See {@link #findNudgeTargetFocusArea} for details. 113 * <li>Finally a focusable view within the chosen focus area is chosen, either from the 114 * focus history or by choosing the best candidate. 115 * </ol> 116 * The caller is responsible for recycling the result. 117 * 118 * @param windows a list of windows to search from 119 * @param sourceNode the current focus 120 * @param direction nudge direction, must be {@link View#FOCUS_UP}, {@link View#FOCUS_DOWN}, 121 * {@link View#FOCUS_LEFT}, or {@link View#FOCUS_RIGHT} 122 * @return a view that can take focus (visible, focusable and enabled) within another {@link 123 * FocusArea}, which is in the given {@code direction} from the current {@link 124 * FocusArea}, or null if not found 125 */ findNudgeTarget(@onNull List<AccessibilityWindowInfo> windows, @NonNull AccessibilityNodeInfo sourceNode, int direction)126 AccessibilityNodeInfo findNudgeTarget(@NonNull List<AccessibilityWindowInfo> windows, 127 @NonNull AccessibilityNodeInfo sourceNode, int direction) { 128 // If the user is trying to nudge to the HUN, search for a focus area in the HUN window. 129 AccessibilityNodeInfo hunNudgeTarget = findHunNudgeTarget(windows, sourceNode, direction); 130 if (hunNudgeTarget != null) { 131 return hunNudgeTarget; 132 } 133 134 long elapsedRealtime = SystemClock.elapsedRealtime(); 135 AccessibilityNodeInfo currentFocusArea = getAncestorFocusArea(sourceNode); 136 AccessibilityNodeInfo targetFocusArea = 137 findNudgeTargetFocusArea(windows, sourceNode, currentFocusArea, direction); 138 Utils.recycleNode(currentFocusArea); 139 if (targetFocusArea == null) { 140 return null; 141 } 142 143 // Return the recently focused node within the target focus area, if any. 144 AccessibilityNodeInfo cachedFocusedNode = 145 mRotaryCache.getFocusedNode(targetFocusArea, elapsedRealtime); 146 if (cachedFocusedNode != null) { 147 Utils.recycleNode(targetFocusArea); 148 return cachedFocusedNode; 149 } 150 151 // Make a list of candidate nodes in the target FocusArea. 152 List<AccessibilityNodeInfo> candidateNodes = new ArrayList<>(); 153 addFocusDescendants(targetFocusArea, candidateNodes); 154 155 // Choose the best candidate as the target node. 156 AccessibilityNodeInfo bestCandidate = 157 chooseBestNudgeCandidate(sourceNode, candidateNodes, direction); 158 159 Utils.recycleNodes(candidateNodes); 160 Utils.recycleNode(targetFocusArea); 161 return bestCandidate; 162 } 163 164 /** 165 * Returns the target focusable for a nudge to the HUN if the HUN is present and the nudge is 166 * in the right direction. The target focusable is chosen as follows: 167 * <ol> 168 * <li>The best candidate focus area is chosen. If there aren't any valid candidates, the 169 * first (only) focus area in the HUN is used. This happens when nudging from a view 170 * obscured by the HUN. 171 * <li>The focus history is checked. If one of the focusable views in the chosen focus area 172 * is in the cache, it's returned. 173 * <li>Finally the best candidate focusable view in the chosen focus area is selected. 174 * Again, if there aren't any candidates, the first focusable view is chosen. 175 * </ol> 176 * The caller is responsible for recycling the result. 177 * 178 * @param windows a list of windows to search from 179 * @param sourceNode the current focus 180 * @param direction nudge direction, must be {@link View#FOCUS_UP}, {@link View#FOCUS_DOWN}, 181 * {@link View#FOCUS_LEFT}, or {@link View#FOCUS_RIGHT} 182 * @return a view that can take focus (visible, focusable and enabled) within the HUN, or null 183 * if the HUN isn't present, the nudge isn't in the direction of the HUN, or the HUN 184 * contains no views that can take focus 185 */ findHunNudgeTarget(@onNull List<AccessibilityWindowInfo> windows, @NonNull AccessibilityNodeInfo sourceNode, int direction)186 private AccessibilityNodeInfo findHunNudgeTarget(@NonNull List<AccessibilityWindowInfo> windows, 187 @NonNull AccessibilityNodeInfo sourceNode, int direction) { 188 if (direction != mHunNudgeDirection) { 189 return null; 190 } 191 192 // Find the HUN window, if any. 193 AccessibilityWindowInfo hunWindow = null; 194 for (AccessibilityWindowInfo window : windows) { 195 if (isHunWindow(window)) { 196 hunWindow = window; 197 break; 198 } 199 } 200 if (hunWindow == null) { 201 return null; 202 } 203 204 // Find the target focus area within the HUN. The HUN may overlap the source node, in which 205 // case the geometric search will fail. The fallback is to use the first (typically only) 206 // focus area. 207 List<AccessibilityNodeInfo> hunFocusAreas = findFocusAreas(hunWindow); 208 removeEmptyFocusAreas(hunFocusAreas); 209 AccessibilityNodeInfo targetFocusArea = 210 chooseBestNudgeCandidate(sourceNode, hunFocusAreas, direction); 211 if (targetFocusArea == null && !hunFocusAreas.isEmpty()) { 212 targetFocusArea = copyNode(hunFocusAreas.get(0)); 213 } 214 Utils.recycleNodes(hunFocusAreas); 215 if (targetFocusArea == null) { 216 return null; 217 } 218 219 // Save nudge history. 220 AccessibilityNodeInfo currentFocusArea = getAncestorFocusArea(sourceNode); 221 long elapsedRealtime = SystemClock.elapsedRealtime(); 222 mRotaryCache.saveTargetFocusArea( 223 currentFocusArea, targetFocusArea, direction, elapsedRealtime); 224 225 // Check the cache to see if a node was focused in the HUN. 226 AccessibilityNodeInfo cachedFocusedNode = 227 mRotaryCache.getFocusedNode(targetFocusArea, elapsedRealtime); 228 if (cachedFocusedNode != null) { 229 Utils.recycleNode(targetFocusArea); 230 Utils.recycleNode(currentFocusArea); 231 return cachedFocusedNode; 232 } 233 234 // Choose the best candidate target node. The HUN may overlap the source node, in which 235 // case the geometric search will fail. The fallback is to use the first focusable node. 236 List<AccessibilityNodeInfo> candidateNodes = new ArrayList<>(); 237 addFocusDescendants(targetFocusArea, candidateNodes); 238 AccessibilityNodeInfo bestCandidate = 239 chooseBestNudgeCandidate(sourceNode, candidateNodes, direction); 240 if (bestCandidate == null && !candidateNodes.isEmpty()) { 241 bestCandidate = copyNode(candidateNodes.get(0)); 242 } 243 Utils.recycleNodes(candidateNodes); 244 Utils.recycleNode(targetFocusArea); 245 Utils.recycleNode(currentFocusArea); 246 return bestCandidate; 247 } 248 249 /** 250 * Returns the target focusable for a rotate. The caller is responsible for recycling the node 251 * in the result. 252 * 253 * <p>If {@code skipNode} isn't null, this node will be skipped. This is used when the focus is 254 * inside a scrollable container to avoid moving the focus to the scrollable container itself. 255 * 256 * <p>Limits navigation to focusable views within a scrollable container's viewport, if any. 257 * 258 * @param sourceNode the current focus 259 * @param skipNode a node to skip - optional 260 * @param direction rotate direction, must be {@link View#FOCUS_FORWARD} or {@link 261 * View#FOCUS_BACKWARD} 262 * @param rotationCount the number of "ticks" to rotate. Only count nodes that can take focus 263 * (visible, focusable and enabled). If {@code skipNode} is encountered, it 264 * isn't counted. 265 * @return a FindRotateTargetResult containing a node and a count of the number of times the 266 * search advanced to another node. The node represents a focusable view in the given 267 * {@code direction} from the current focus within the same {@link FocusArea}. If the 268 * first or last view is reached before counting up to {@code rotationCount}, the first 269 * or last view is returned. However, if there are no views that can take focus in the 270 * given {@code direction}, {@code null} is returned. 271 */ 272 @Nullable findRotateTarget(@onNull AccessibilityNodeInfo sourceNode, @Nullable AccessibilityNodeInfo skipNode, int direction, int rotationCount)273 FindRotateTargetResult findRotateTarget(@NonNull AccessibilityNodeInfo sourceNode, 274 @Nullable AccessibilityNodeInfo skipNode, int direction, int rotationCount) { 275 int advancedCount = 0; 276 AccessibilityNodeInfo currentFocusArea = getAncestorFocusArea(sourceNode); 277 AccessibilityNodeInfo targetNode = copyNode(sourceNode); 278 for (int i = 0; i < rotationCount; i++) { 279 AccessibilityNodeInfo nextTargetNode = targetNode.focusSearch(direction); 280 if (skipNode != null && skipNode.equals(nextTargetNode)) { 281 Utils.recycleNode(nextTargetNode); 282 nextTargetNode = skipNode.focusSearch(direction); 283 } 284 AccessibilityNodeInfo targetFocusArea = 285 nextTargetNode == null ? null : getAncestorFocusArea(nextTargetNode); 286 287 // Only advance to nextTargetNode if it's in the same focus area and it isn't a 288 // FocusParkingView. The second condition prevents wrap-around when there is only one 289 // focus area in the window, including when the root node is treated as a focus area. 290 if (nextTargetNode != null && currentFocusArea.equals(targetFocusArea) 291 && !Utils.isFocusParkingView(nextTargetNode)) { 292 // If we're navigating through a scrolling view that can scroll in the specified 293 // direction and the next view is off-screen, don't advance to it. (We'll scroll 294 // instead.) 295 Rect nextTargetBounds = new Rect(); 296 nextTargetNode.getBoundsInScreen(nextTargetBounds); 297 AccessibilityNodeInfo scrollableContainer = findScrollableContainer(targetNode); 298 AccessibilityNodeInfo.AccessibilityAction scrollAction = 299 direction == View.FOCUS_FORWARD 300 ? ACTION_SCROLL_FORWARD 301 : ACTION_SCROLL_BACKWARD; 302 if (scrollableContainer != null 303 && scrollableContainer.getActionList().contains(scrollAction)) { 304 Rect scrollBounds = new Rect(); 305 scrollableContainer.getBoundsInScreen(scrollBounds); 306 boolean intersects = nextTargetBounds.intersect(scrollBounds); 307 if (!intersects) { 308 Utils.recycleNode(nextTargetNode); 309 Utils.recycleNode(targetFocusArea); 310 break; 311 } 312 } 313 Utils.recycleNode(scrollableContainer); 314 315 Utils.recycleNode(targetNode); 316 Utils.recycleNode(targetFocusArea); 317 targetNode = nextTargetNode; 318 advancedCount++; 319 } else { 320 Utils.recycleNode(nextTargetNode); 321 Utils.recycleNode(targetFocusArea); 322 break; 323 } 324 } 325 Utils.recycleNode(currentFocusArea); 326 if (sourceNode.equals(targetNode)) { 327 targetNode.recycle(); 328 return null; 329 } 330 return new FindRotateTargetResult(targetNode, advancedCount); 331 } 332 333 /** 334 * Searches the {@code rootNode} and its descendants in depth-first order, and returns the first 335 * focus descendant (a node inside a focus area that can take focus) if any, or returns null if 336 * not found. The caller is responsible for recycling the result. 337 */ findFirstFocusDescendant(@onNull AccessibilityNodeInfo rootNode)338 AccessibilityNodeInfo findFirstFocusDescendant(@NonNull AccessibilityNodeInfo rootNode) { 339 // First try finding the first focus area and searching forward from the focus area. This 340 // is a quick way to find the first node but it doesn't always work. 341 AccessibilityNodeInfo focusDescendant = findFirstFocus(rootNode); 342 if (focusDescendant != null) { 343 return focusDescendant; 344 } 345 346 // Fall back to tree traversal. 347 L.w("Falling back to tree traversal"); 348 focusDescendant = findDepthFirstFocus(rootNode); 349 if (focusDescendant == null) { 350 L.w("No node can take focus in the current window"); 351 } 352 return focusDescendant; 353 } 354 355 /** Sets a mock Utils instance for testing. */ 356 @VisibleForTesting setNodeCopier(@onNull NodeCopier nodeCopier)357 void setNodeCopier(@NonNull NodeCopier nodeCopier) { 358 mNodeCopier = nodeCopier; 359 mTreeTraverser.setNodeCopier(nodeCopier); 360 mRotaryCache.setNodeCopier(nodeCopier); 361 } 362 363 /** 364 * Searches all the nodes in the {@code window}, and returns the node representing a {@link 365 * FocusParkingView}, if any, or returns null if not found. The caller is responsible for 366 * recycling the result. 367 */ findFocusParkingView(@onNull AccessibilityWindowInfo window)368 AccessibilityNodeInfo findFocusParkingView(@NonNull AccessibilityWindowInfo window) { 369 AccessibilityNodeInfo root = window.getRoot(); 370 if (root == null) { 371 L.e("No root node in " + window); 372 return null; 373 } 374 AccessibilityNodeInfo focusParkingView = findFocusParkingView(root); 375 root.recycle(); 376 return focusParkingView; 377 } 378 379 /** 380 * Searches the {@code node} and its descendants in depth-first order, and returns the node 381 * representing a {@link FocusParkingView}, if any, or returns null if not found. The caller is 382 * responsible for recycling the result. 383 */ findFocusParkingView(@onNull AccessibilityNodeInfo node)384 private AccessibilityNodeInfo findFocusParkingView(@NonNull AccessibilityNodeInfo node) { 385 return mTreeTraverser.depthFirstSearch(node, /* skipPredicate= */ Utils::isFocusArea, 386 /* targetPredicate= */ Utils::isFocusParkingView); 387 } 388 389 /** 390 * Searches the {@code rootNode} and its descendants in depth-first order for the first focus 391 * area, and returns the first node that can take focus in tab order from the focus area. 392 * The return value could be a node inside or outside the first focus area, or null if not 393 * found. The caller is responsible for recycling result. 394 */ findFirstFocus(@onNull AccessibilityNodeInfo rootNode)395 private AccessibilityNodeInfo findFirstFocus(@NonNull AccessibilityNodeInfo rootNode) { 396 AccessibilityNodeInfo focusArea = findFirstFocusArea(rootNode); 397 if (focusArea == null) { 398 L.w("No FocusArea in the tree"); 399 // rootNode is an implicit focus area if no explicit FocusAreas are specified. 400 focusArea = copyNode(rootNode); 401 } 402 403 AccessibilityNodeInfo targetNode = focusArea.focusSearch(View.FOCUS_FORWARD); 404 AccessibilityNodeInfo firstTarget = copyNode(targetNode); 405 // focusSearch() searches in the active window, which has at least one FocusParkingView. We 406 // need to skip it. 407 while (targetNode != null && Utils.isFocusParkingView(targetNode)) { 408 L.d("Found FocusParkingView, continue focusSearch() ..."); 409 AccessibilityNodeInfo nextTargetNode = targetNode.focusSearch(View.FOCUS_FORWARD); 410 targetNode.recycle(); 411 targetNode = nextTargetNode; 412 413 // If we found the same FocusParkingView again, it means all the focusable views in 414 // current window are FocusParkingViews, so we should just return null. 415 if (firstTarget.equals(targetNode)) { 416 L.w("Stop focusSearch() because there is no view to take focus except " 417 + "FocusParkingViews"); 418 Utils.recycleNode(targetNode); 419 targetNode = null; 420 break; 421 } 422 } 423 Utils.recycleNode(firstTarget); 424 focusArea.recycle(); 425 return targetNode; 426 } 427 428 /** 429 * Searches the given {@code node} and its descendants in depth-first order, and returns the 430 * first {@link FocusArea}, or returns null if not found. The caller is responsible for 431 * recycling the result. 432 */ findFirstFocusArea(@onNull AccessibilityNodeInfo node)433 private AccessibilityNodeInfo findFirstFocusArea(@NonNull AccessibilityNodeInfo node) { 434 return mTreeTraverser.depthFirstSearch(node, Utils::isFocusArea); 435 } 436 437 /** 438 * Searches the given {@code node} and its descendants in depth-first order, and returns the 439 * first node that can take focus, or returns null if not found. The caller is responsible for 440 * recycling result. 441 */ findDepthFirstFocus(@onNull AccessibilityNodeInfo node)442 private AccessibilityNodeInfo findDepthFirstFocus(@NonNull AccessibilityNodeInfo node) { 443 return mTreeTraverser.depthFirstSearch(node, Utils::canTakeFocus); 444 } 445 446 /** 447 * Returns the target focus area for a nudge in the given {@code direction} from the current 448 * focus, or null if not found. Checks the cache first. If nothing is found in the cache, 449 * returns the best nudge target from among all the candidate focus areas. In all cases, the 450 * nudge back is saved in the cache. The caller is responsible for recycling the result. 451 */ findNudgeTargetFocusArea( @onNull List<AccessibilityWindowInfo> windows, @NonNull AccessibilityNodeInfo focusedNode, @NonNull AccessibilityNodeInfo currentFocusArea, int direction)452 private AccessibilityNodeInfo findNudgeTargetFocusArea( 453 @NonNull List<AccessibilityWindowInfo> windows, 454 @NonNull AccessibilityNodeInfo focusedNode, 455 @NonNull AccessibilityNodeInfo currentFocusArea, 456 int direction) { 457 long elapsedRealtime = SystemClock.elapsedRealtime(); 458 // If there is a target focus area in the cache, returns it. 459 AccessibilityNodeInfo cachedTargetFocusArea = 460 mRotaryCache.getTargetFocusArea(currentFocusArea, direction, elapsedRealtime); 461 if (cachedTargetFocusArea != null && Utils.canHaveFocus(cachedTargetFocusArea)) { 462 // We already got nudge history in the cache. Before nudging back, let's save "nudge 463 // back" history. 464 mRotaryCache.saveTargetFocusArea( 465 currentFocusArea, cachedTargetFocusArea, direction, elapsedRealtime); 466 return cachedTargetFocusArea; 467 } 468 Utils.recycleNode(cachedTargetFocusArea); 469 470 // No target focus area in the cache; we need to search the node tree to find it. 471 AccessibilityWindowInfo currentWindow = focusedNode.getWindow(); 472 if (currentWindow == null) { 473 L.e("Currently focused window is null"); 474 return null; 475 } 476 477 // Build a list of candidate focus areas, starting with all the other focus areas in the 478 // same window as the current focus area. 479 List<AccessibilityNodeInfo> candidateFocusAreas = findFocusAreas(currentWindow); 480 for (AccessibilityNodeInfo focusArea : candidateFocusAreas) { 481 if (focusArea.equals(currentFocusArea)) { 482 candidateFocusAreas.remove(focusArea); 483 focusArea.recycle(); 484 break; 485 } 486 } 487 488 // Add candidate focus areas in other windows in the given direction. 489 List<AccessibilityWindowInfo> candidateWindows = new ArrayList<>(); 490 addWindowsInDirection(windows, currentWindow, candidateWindows, direction); 491 currentWindow.recycle(); 492 for (AccessibilityWindowInfo window : candidateWindows) { 493 List<AccessibilityNodeInfo> focusAreasInAnotherWindow = findFocusAreas(window); 494 candidateFocusAreas.addAll(focusAreasInAnotherWindow); 495 } 496 497 // Exclude focus areas that have no descendants to take focus, because once we found a best 498 // candidate focus area, we don't dig into other ones. If it has no descendants to take 499 // focus, the nudge will fail. 500 removeEmptyFocusAreas(candidateFocusAreas); 501 502 // Choose the best candidate as our target focus area. 503 AccessibilityNodeInfo targetFocusArea = 504 chooseBestNudgeCandidate(focusedNode, candidateFocusAreas, direction); 505 Utils.recycleNodes(candidateFocusAreas); 506 507 if (targetFocusArea != null) { 508 // Save nudge history. 509 mRotaryCache.saveTargetFocusArea( 510 currentFocusArea, targetFocusArea, direction, elapsedRealtime); 511 } 512 513 return targetFocusArea; 514 } 515 removeEmptyFocusAreas(@onNull List<AccessibilityNodeInfo> focusAreas)516 private static void removeEmptyFocusAreas(@NonNull List<AccessibilityNodeInfo> focusAreas) { 517 for (Iterator<AccessibilityNodeInfo> iterator = focusAreas.iterator(); 518 iterator.hasNext(); ) { 519 AccessibilityNodeInfo focusArea = iterator.next(); 520 if (!Utils.canHaveFocus(focusArea)) { 521 iterator.remove(); 522 focusArea.recycle(); 523 } 524 } 525 } 526 527 /** 528 * Adds all the {@code windows} in the given {@code direction} of the given {@code source} 529 * window to the given list. 530 */ addWindowsInDirection(@onNull List<AccessibilityWindowInfo> windows, @NonNull AccessibilityWindowInfo source, @NonNull List<AccessibilityWindowInfo> results, int direction)531 private void addWindowsInDirection(@NonNull List<AccessibilityWindowInfo> windows, 532 @NonNull AccessibilityWindowInfo source, 533 @NonNull List<AccessibilityWindowInfo> results, 534 int direction) { 535 Rect sourceBounds = new Rect(); 536 source.getBoundsInScreen(sourceBounds); 537 Rect destBounds = new Rect(); 538 for (AccessibilityWindowInfo window : windows) { 539 if (!window.equals(source)) { 540 window.getBoundsInScreen(destBounds); 541 542 // Even if only part of destBounds is in the given direction of sourceBounds, we 543 // still include it because that part may contain the target focus area. 544 if (FocusFinder.isPartiallyInDirection(sourceBounds, destBounds, direction)) { 545 results.add(window); 546 } 547 } 548 } 549 } 550 551 /** 552 * Scans the view hierarchy of the given {@code window} looking for focus areas and returns 553 * them. If there are no explicitly declared {@link FocusArea}s, returns the root view. The 554 * caller is responsible for recycling the result. 555 */ 556 private @NonNull findFocusAreas(@onNull AccessibilityWindowInfo window)557 List<AccessibilityNodeInfo> findFocusAreas(@NonNull AccessibilityWindowInfo window) { 558 List<AccessibilityNodeInfo> results = new ArrayList<>(); 559 AccessibilityNodeInfo rootNode = window.getRoot(); 560 if (rootNode != null) { 561 addFocusAreas(rootNode, results); 562 if (results.isEmpty()) { 563 results.add(copyNode(rootNode)); 564 } 565 rootNode.recycle(); 566 } 567 return results; 568 } 569 570 /** 571 * Returns whether the given window is the Heads-up Notification (HUN) window. The HUN window 572 * is identified by the left and right edges. The top and bottom vary depending on whether the 573 * HUN appears at the top or bottom of the screen and on the height of the notification being 574 * displayed so they aren't used. 575 */ isHunWindow(@onNull AccessibilityWindowInfo window)576 boolean isHunWindow(@NonNull AccessibilityWindowInfo window) { 577 if (window.getType() != AccessibilityWindowInfo.TYPE_SYSTEM) { 578 return false; 579 } 580 Rect bounds = new Rect(); 581 window.getBoundsInScreen(bounds); 582 return bounds.left == mHunLeft && bounds.right == mHunRight; 583 } 584 585 /** 586 * Searches from the given node up through its ancestors to the containing focus area, looking 587 * for a node that's marked as horizontally or vertically scrollable. Returns a copy of the 588 * first such node or null if none is found. The caller is responsible for recycling the result. 589 */ 590 @Nullable findScrollableContainer(@onNull AccessibilityNodeInfo node)591 AccessibilityNodeInfo findScrollableContainer(@NonNull AccessibilityNodeInfo node) { 592 return mTreeTraverser.findNodeOrAncestor(node, /* stopPredicate= */ Utils::isFocusArea, 593 /* targetPredicate= */ Utils::isScrollableContainer); 594 } 595 596 /** 597 * Returns the previous node in Tab order before {@code referenceNode} within 598 * {@code containerNode} or null if none. The caller is responsible for recycling the result. 599 */ 600 @Nullable findPreviousFocusableDescendant( @onNull AccessibilityNodeInfo containerNode, @NonNull AccessibilityNodeInfo referenceNode)601 static AccessibilityNodeInfo findPreviousFocusableDescendant( 602 @NonNull AccessibilityNodeInfo containerNode, 603 @NonNull AccessibilityNodeInfo referenceNode) { 604 return findFocusableDescendantInDirection(containerNode, referenceNode, 605 View.FOCUS_BACKWARD); 606 } 607 608 /** 609 * Returns the next node after {@code referenceNode} in Tab order within {@code containerNode} 610 * or null if none. The caller is responsible for recycling the result. 611 */ 612 @Nullable findNextFocusableDescendant( @onNull AccessibilityNodeInfo containerNode, @NonNull AccessibilityNodeInfo referenceNode)613 static AccessibilityNodeInfo findNextFocusableDescendant( 614 @NonNull AccessibilityNodeInfo containerNode, 615 @NonNull AccessibilityNodeInfo referenceNode) { 616 return findFocusableDescendantInDirection(containerNode, referenceNode, View.FOCUS_FORWARD); 617 } 618 619 /** 620 * Returns the previous node before {@code referenceNode} in Tab order or the next node after 621 * {@code referenceNode} in Tab order, depending on {@code direction}. The search is limited to 622 * descendants of {@code containerNode}. Returns null if there are no focusable descendants in 623 * the given direction. The caller is responsible for recycling the result. 624 * 625 * @param containerNode the node with descendants 626 * @param referenceNode a descendant of {@code containerNode} to start from 627 * @param direction {@link View#FOCUS_FORWARD} or {@link View#FOCUS_BACKWARD} 628 * @return the node before or after {@code referenceNode} or null if none 629 */ 630 @Nullable findFocusableDescendantInDirection( @onNull AccessibilityNodeInfo containerNode, @NonNull AccessibilityNodeInfo referenceNode, int direction)631 static AccessibilityNodeInfo findFocusableDescendantInDirection( 632 @NonNull AccessibilityNodeInfo containerNode, 633 @NonNull AccessibilityNodeInfo referenceNode, 634 int direction) { 635 AccessibilityNodeInfo targetNode = referenceNode.focusSearch(direction); 636 if (targetNode == null 637 || targetNode.equals(containerNode) 638 || !Utils.canTakeFocus(targetNode) 639 || !Utils.isDescendant(containerNode, targetNode)) { 640 Utils.recycleNode(targetNode); 641 return null; 642 } 643 if (targetNode.equals(referenceNode)) { 644 L.w((direction == View.FOCUS_FORWARD ? "Next" : "Previous") 645 + " node is the same node: " + referenceNode); 646 Utils.recycleNode(targetNode); 647 return null; 648 } 649 return targetNode; 650 } 651 652 /** 653 * Returns the first descendant of {@code node} which can take focus. The nodes are searched in 654 * in depth-first order, not including {@code node} itself. If no descendant can take focus, 655 * null is returned. The caller is responsible for recycling the result. 656 */ 657 @Nullable findFirstFocusableDescendant(@onNull AccessibilityNodeInfo node)658 AccessibilityNodeInfo findFirstFocusableDescendant(@NonNull AccessibilityNodeInfo node) { 659 return mTreeTraverser.depthFirstSearch(node, 660 candidateNode -> candidateNode != node && Utils.canTakeFocus(candidateNode)); 661 } 662 663 /** 664 * Returns the last descendant of {@code node} which can take focus. The nodes are searched in 665 * reverse depth-first order, not including {@code node} itself. If no descendant can take 666 * focus, null is returned. The caller is responsible for recycling the result. 667 */ 668 @Nullable findLastFocusableDescendant(@onNull AccessibilityNodeInfo node)669 AccessibilityNodeInfo findLastFocusableDescendant(@NonNull AccessibilityNodeInfo node) { 670 return mTreeTraverser.reverseDepthFirstSearch(node, 671 candidateNode -> candidateNode != node && Utils.canTakeFocus(candidateNode)); 672 } 673 674 /** 675 * Scans descendants of the given {@code rootNode} looking for focus areas and adds them to the 676 * given list. It doesn't scan inside focus areas since nested focus areas aren't allowed. The 677 * caller is responsible for recycling added nodes. 678 * 679 * @param rootNode the root to start scanning from 680 * @param results a list of focus areas to add to 681 */ addFocusAreas(@onNull AccessibilityNodeInfo rootNode, @NonNull List<AccessibilityNodeInfo> results)682 private void addFocusAreas(@NonNull AccessibilityNodeInfo rootNode, 683 @NonNull List<AccessibilityNodeInfo> results) { 684 mTreeTraverser.depthFirstSelect(rootNode, Utils::isFocusArea, results); 685 } 686 687 /** 688 * Adds the given {@code node} and all its focus descendants (nodes that can take focus) to the 689 * given list. The caller is responsible for recycling added nodes. 690 */ addFocusDescendants(@onNull AccessibilityNodeInfo node, @NonNull List<AccessibilityNodeInfo> results)691 private void addFocusDescendants(@NonNull AccessibilityNodeInfo node, 692 @NonNull List<AccessibilityNodeInfo> results) { 693 mTreeTraverser.depthFirstSelect(node, Utils::canTakeFocus, results); 694 } 695 696 /** 697 * Returns a copy of the best candidate from among the given {@code candidates} for a nudge 698 * from {@code sourceNode} in the given {@code direction}. Returns null if none of the {@code 699 * candidates} are in the given {@code direction}. The caller is responsible for recycling the 700 * result. 701 * 702 * @param candidates could be a list of {@link FocusArea}s, or a list of focusable views 703 */ chooseBestNudgeCandidate( @onNull AccessibilityNodeInfo sourceNode, @NonNull List<AccessibilityNodeInfo> candidates, int direction)704 private AccessibilityNodeInfo chooseBestNudgeCandidate( 705 @NonNull AccessibilityNodeInfo sourceNode, 706 @NonNull List<AccessibilityNodeInfo> candidates, 707 int direction) { 708 if (candidates.isEmpty()) { 709 return null; 710 } 711 Rect sourceBounds = new Rect(); 712 sourceNode.getBoundsInScreen(sourceBounds); 713 714 AccessibilityNodeInfo bestNode = null; 715 Rect bestBounds = new Rect(); 716 717 Rect candidateBounds = new Rect(); 718 for (AccessibilityNodeInfo candidate : candidates) { 719 if (isCandidate(sourceBounds, candidate, direction)) { 720 candidate.getBoundsInScreen(candidateBounds); 721 if (bestNode == null || FocusFinder.isBetterCandidate( 722 direction, sourceBounds, candidateBounds, bestBounds)) { 723 bestNode = candidate; 724 bestBounds.set(candidateBounds); 725 } 726 } 727 } 728 return copyNode(bestNode); 729 } 730 731 /** 732 * Returns whether the given {@code node} is a candidate from {@code sourceBounds} to the given 733 * {@code direction}. To be a candidate, the node or one of its descendants must be able to take 734 * focus and must be considered a candidate by {@link FocusFinder#isCandidate}. 735 */ isCandidate(@onNull Rect sourceBounds, @NonNull AccessibilityNodeInfo node, int direction)736 private boolean isCandidate(@NonNull Rect sourceBounds, 737 @NonNull AccessibilityNodeInfo node, 738 int direction) { 739 AccessibilityNodeInfo candidate = mTreeTraverser.depthFirstSearch(node, candidateNode -> { 740 // First check if the node can take focus. 741 if (!Utils.canTakeFocus(candidateNode)) { 742 return false; 743 } 744 // The node represents a focusable view in the FocusArea, so check the geometry. 745 Rect candidateBounds = new Rect(); 746 candidateNode.getBoundsInScreen(candidateBounds); 747 return FocusFinder.isCandidate(sourceBounds, candidateBounds, direction); 748 }); 749 if (candidate == null) { 750 return false; 751 } 752 candidate.recycle(); 753 return true; 754 } 755 copyNode(@ullable AccessibilityNodeInfo node)756 private AccessibilityNodeInfo copyNode(@Nullable AccessibilityNodeInfo node) { 757 return mNodeCopier.copy(node); 758 } 759 760 /** 761 * Finds the closest ancestor focus area of the given {@code node}. If the given {@code node} 762 * is a focus area, returns it; if there are no explicitly declared {@link FocusArea}s among the 763 * ancestors of this view, returns the root view. The caller is responsible for recycling the 764 * result. 765 */ 766 @NonNull getAncestorFocusArea(@onNull AccessibilityNodeInfo node)767 private AccessibilityNodeInfo getAncestorFocusArea(@NonNull AccessibilityNodeInfo node) { 768 TreeTraverser.NodePredicate isFocusAreaOrRoot = candidateNode -> { 769 if (Utils.isFocusArea(candidateNode)) { 770 // The candidateNode is a focus area. 771 return true; 772 } 773 AccessibilityNodeInfo parent = candidateNode.getParent(); 774 if (parent == null) { 775 // The candidateNode is the root node. 776 return true; 777 } 778 parent.recycle(); 779 return false; 780 }; 781 AccessibilityNodeInfo result = mTreeTraverser.findNodeOrAncestor(node, isFocusAreaOrRoot); 782 if (!Utils.isFocusArea(result)) { 783 L.w("Couldn't find ancestor focus area for given node: " + node); 784 } 785 return result; 786 } 787 788 /** Result from {@link #findRotateTarget}. */ 789 static class FindRotateTargetResult { 790 @NonNull final AccessibilityNodeInfo node; 791 final int advancedCount; 792 FindRotateTargetResult(@onNull AccessibilityNodeInfo node, int advancedCount)793 FindRotateTargetResult(@NonNull AccessibilityNodeInfo node, int advancedCount) { 794 this.node = node; 795 this.advancedCount = advancedCount; 796 } 797 } 798 } 799