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.app.ActivityTaskManager.INVALID_TASK_ID; 19 import static android.view.View.FOCUS_DOWN; 20 import static android.view.View.FOCUS_LEFT; 21 import static android.view.View.FOCUS_RIGHT; 22 import static android.view.View.FOCUS_UP; 23 import static android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction.ACTION_SCROLL_BACKWARD; 24 import static android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction.ACTION_SCROLL_FORWARD; 25 import static android.view.accessibility.AccessibilityNodeInfo.FOCUS_INPUT; 26 import static android.view.accessibility.AccessibilityWindowInfo.TYPE_APPLICATION; 27 import static android.view.accessibility.AccessibilityWindowInfo.TYPE_INPUT_METHOD; 28 29 import android.content.pm.PackageManager; 30 import android.graphics.Rect; 31 import android.view.Display; 32 import android.view.View; 33 import android.view.accessibility.AccessibilityNodeInfo; 34 import android.view.accessibility.AccessibilityWindowInfo; 35 36 import androidx.annotation.NonNull; 37 import androidx.annotation.Nullable; 38 import androidx.annotation.VisibleForTesting; 39 40 import com.android.car.ui.FocusArea; 41 import com.android.car.ui.FocusParkingView; 42 import com.android.internal.util.dump.DualDumpOutputStream; 43 44 import java.util.ArrayList; 45 import java.util.List; 46 import java.util.function.Predicate; 47 48 /** 49 * A helper class used for finding the next focusable node when the rotary controller is rotated or 50 * nudged. 51 */ 52 class Navigator { 53 54 @NonNull 55 private NodeCopier mNodeCopier = new NodeCopier(); 56 57 @NonNull 58 private final TreeTraverser mTreeTraverser = new TreeTraverser(); 59 60 @NonNull 61 @VisibleForTesting 62 final SurfaceViewHelper mSurfaceViewHelper = new SurfaceViewHelper(); 63 64 private final int mHunLeft; 65 private final int mHunRight; 66 67 @View.FocusRealDirection 68 private int mHunNudgeDirection; 69 70 @NonNull 71 private final Rect mAppWindowBounds; 72 73 private int mAppWindowTaskId = INVALID_TASK_ID; 74 Navigator(int displayWidth, int displayHeight, int hunLeft, int hunRight, boolean showHunOnBottom)75 Navigator(int displayWidth, int displayHeight, int hunLeft, int hunRight, 76 boolean showHunOnBottom) { 77 mHunLeft = hunLeft; 78 mHunRight = hunRight; 79 mHunNudgeDirection = showHunOnBottom ? FOCUS_DOWN : FOCUS_UP; 80 mAppWindowBounds = new Rect(0, 0, displayWidth, displayHeight); 81 } 82 83 @VisibleForTesting Navigator()84 Navigator() { 85 this(0, 0, 0, 0, false); 86 } 87 88 /** 89 * Updates {@link #mAppWindowTaskId} if {@code window} is a full-screen app window on the 90 * default display. 91 */ updateAppWindowTaskId(@onNull AccessibilityWindowInfo window)92 void updateAppWindowTaskId(@NonNull AccessibilityWindowInfo window) { 93 if (window.getType() == TYPE_APPLICATION 94 && window.getDisplayId() == Display.DEFAULT_DISPLAY) { 95 Rect windowBounds = new Rect(); 96 window.getBoundsInScreen(windowBounds); 97 if (mAppWindowBounds.equals(windowBounds)) { 98 mAppWindowTaskId = window.getTaskId(); 99 L.d("Task ID of app window: " + mAppWindowTaskId); 100 } 101 } 102 } 103 104 /** Initializes the package name of the host app. */ initHostApp(@onNull PackageManager packageManager)105 void initHostApp(@NonNull PackageManager packageManager) { 106 mSurfaceViewHelper.initHostApp(packageManager); 107 } 108 109 /** Clears the package name of the host app if the given {@code packageName} matches. */ clearHostApp(@onNull String packageName)110 void clearHostApp(@NonNull String packageName) { 111 mSurfaceViewHelper.clearHostApp(packageName); 112 } 113 114 /** Returns whether it supports AAOS template apps. */ supportTemplateApp()115 boolean supportTemplateApp() { 116 return mSurfaceViewHelper.supportTemplateApp(); 117 } 118 119 /** Adds the package name of the client app. */ addClientApp(@onNull CharSequence clientAppPackageName)120 void addClientApp(@NonNull CharSequence clientAppPackageName) { 121 mSurfaceViewHelper.addClientApp(clientAppPackageName); 122 } 123 124 /** Returns whether the given {@code node} represents a view of the host app. */ isHostNode(@onNull AccessibilityNodeInfo node)125 boolean isHostNode(@NonNull AccessibilityNodeInfo node) { 126 return mSurfaceViewHelper.isHostNode(node); 127 } 128 129 /** Returns whether the given {@code node} represents a view of the client app. */ isClientNode(@onNull AccessibilityNodeInfo node)130 boolean isClientNode(@NonNull AccessibilityNodeInfo node) { 131 return mSurfaceViewHelper.isClientNode(node); 132 } 133 134 @Nullable findHunWindow(@onNull List<AccessibilityWindowInfo> windows)135 AccessibilityWindowInfo findHunWindow(@NonNull List<AccessibilityWindowInfo> windows) { 136 for (AccessibilityWindowInfo window : windows) { 137 if (isHunWindow(window)) { 138 return window; 139 } 140 } 141 return null; 142 } 143 144 /** 145 * Returns the target focusable for a rotate. The caller is responsible for recycling the node 146 * in the result. 147 * 148 * <p>Limits navigation to focusable views within a scrollable container's viewport, if any. 149 * 150 * @param sourceNode the current focus 151 * @param direction rotate direction, must be {@link View#FOCUS_FORWARD} or {@link 152 * View#FOCUS_BACKWARD} 153 * @param rotationCount the number of "ticks" to rotate. Only count nodes that can take focus 154 * (visible, focusable and enabled). If {@code skipNode} is encountered, it 155 * isn't counted. 156 * @return a FindRotateTargetResult containing a node and a count of the number of times the 157 * search advanced to another node. The node represents a focusable view in the given 158 * {@code direction} from the current focus within the same {@link FocusArea}. If the 159 * first or last view is reached before counting up to {@code rotationCount}, the first 160 * or last view is returned. However, if there are no views that can take focus in the 161 * given {@code direction}, {@code null} is returned. 162 */ 163 @Nullable findRotateTarget( @onNull AccessibilityNodeInfo sourceNode, int direction, int rotationCount)164 FindRotateTargetResult findRotateTarget( 165 @NonNull AccessibilityNodeInfo sourceNode, int direction, int rotationCount) { 166 int advancedCount = 0; 167 AccessibilityNodeInfo currentFocusArea = getAncestorFocusArea(sourceNode); 168 AccessibilityNodeInfo candidate = copyNode(sourceNode); 169 AccessibilityNodeInfo target = null; 170 while (advancedCount < rotationCount) { 171 AccessibilityNodeInfo nextCandidate = null; 172 // Virtual View hierarchies like WebViews and ComposeViews do not support focusSearch(). 173 AccessibilityNodeInfo virtualViewAncestor = findVirtualViewAncestor(candidate); 174 if (virtualViewAncestor != null) { 175 nextCandidate = 176 findNextFocusableInVirtualRoot(virtualViewAncestor, candidate, direction); 177 } 178 if (nextCandidate == null) { 179 // If we aren't in a virtual node hierarchy, or there aren't any more focusable 180 // nodes within the virtual node hierarchy, use focusSearch(). 181 nextCandidate = candidate.focusSearch(direction); 182 } 183 AccessibilityNodeInfo candidateFocusArea = 184 nextCandidate == null ? null : getAncestorFocusArea(nextCandidate); 185 186 // Only advance to nextCandidate if: 187 // 1. it's in the same focus area, 188 // 2. and it isn't a FocusParkingView (this is to prevent wrap-around when there is only 189 // one focus area in the window, including when the root node is treated as a focus 190 // area), 191 // 3. and nextCandidate is different from candidate (if sourceNode is the first 192 // focusable node in the window, searching backward will return sourceNode itself). 193 if (nextCandidate != null && currentFocusArea != null 194 && currentFocusArea.equals(candidateFocusArea) 195 && !Utils.isFocusParkingView(nextCandidate) 196 && !nextCandidate.equals(candidate)) { 197 // We need to skip nextTargetNode if: 198 // 1. it can't perform focus action (focusSearch() may return a node with zero 199 // width and height), 200 // 2. or it is a scrollable container but it shouldn't be scrolled (i.e., it is not 201 // scrollable, or its descendants can take focus). 202 // When we want to focus on its element directly, we'll skip the container. When 203 // we want to focus on container and scroll it, we won't skip the container. 204 if (!Utils.canPerformFocus(nextCandidate) 205 || (Utils.isScrollableContainer(nextCandidate) 206 && !Utils.canScrollableContainerTakeFocus(nextCandidate))) { 207 Utils.recycleNode(candidate); 208 Utils.recycleNode(candidateFocusArea); 209 candidate = nextCandidate; 210 continue; 211 } 212 213 // If we're navigating in a scrollable container that can scroll in the specified 214 // direction and the next candidate is off-screen or there are no more focusable 215 // views within the scrollable container, stop navigating so that any remaining 216 // detents are used for scrolling. 217 AccessibilityNodeInfo scrollableContainer = findScrollableContainer(candidate); 218 AccessibilityNodeInfo.AccessibilityAction scrollAction = 219 direction == View.FOCUS_FORWARD 220 ? ACTION_SCROLL_FORWARD 221 : ACTION_SCROLL_BACKWARD; 222 if (scrollableContainer != null 223 && scrollableContainer.getActionList().contains(scrollAction) 224 && (!Utils.isDescendant(scrollableContainer, nextCandidate) 225 || Utils.getBoundsInScreen(nextCandidate).isEmpty())) { 226 Utils.recycleNode(nextCandidate); 227 Utils.recycleNode(candidateFocusArea); 228 break; 229 } 230 Utils.recycleNode(scrollableContainer); 231 232 Utils.recycleNode(candidate); 233 Utils.recycleNode(candidateFocusArea); 234 candidate = nextCandidate; 235 Utils.recycleNode(target); 236 target = copyNode(candidate); 237 advancedCount++; 238 } else { 239 Utils.recycleNode(nextCandidate); 240 Utils.recycleNode(candidateFocusArea); 241 break; 242 } 243 } 244 candidate.recycle(); 245 if (sourceNode.equals(target)) { 246 L.e("Wrap-around on the same node"); 247 target.recycle(); 248 return null; 249 } 250 return target == null ? null : new FindRotateTargetResult(target, advancedCount); 251 } 252 253 /** Sets a NodeCopier instance for testing. */ 254 @VisibleForTesting setNodeCopier(@onNull NodeCopier nodeCopier)255 void setNodeCopier(@NonNull NodeCopier nodeCopier) { 256 mNodeCopier = nodeCopier; 257 mTreeTraverser.setNodeCopier(nodeCopier); 258 } 259 260 /** 261 * Returns the root node in the tree containing {@code node}. The caller is responsible for 262 * recycling the result. 263 */ 264 @NonNull getRoot(@onNull AccessibilityNodeInfo node)265 AccessibilityNodeInfo getRoot(@NonNull AccessibilityNodeInfo node) { 266 // If the node represents a view in the embedded view hierarchy hosted by a SurfaceView, 267 // return the root node of the hierarchy, which is the only child of the SurfaceView node. 268 if (isHostNode(node)) { 269 AccessibilityNodeInfo child = mNodeCopier.copy(node); 270 AccessibilityNodeInfo parent = node.getParent(); 271 while (parent != null && !Utils.isSurfaceView(parent)) { 272 child.recycle(); 273 child = parent; 274 parent = child.getParent(); 275 } 276 Utils.recycleNode(parent); 277 return child; 278 } 279 280 // Get the root node directly via the window. 281 AccessibilityWindowInfo window = node.getWindow(); 282 if (window != null) { 283 AccessibilityNodeInfo root = window.getRoot(); 284 window.recycle(); 285 if (root != null) { 286 return root; 287 } 288 } 289 290 // If the root node can't be accessed via the window, navigate up the node tree. 291 AccessibilityNodeInfo child = mNodeCopier.copy(node); 292 AccessibilityNodeInfo parent = node.getParent(); 293 while (parent != null) { 294 child.recycle(); 295 child = parent; 296 parent = child.getParent(); 297 } 298 return child; 299 } 300 301 /** 302 * Searches {@code root} and its descendants, and returns the currently focused node if it's 303 * not a {@link FocusParkingView}, or returns null in other cases. The caller is responsible 304 * for recycling the result. 305 */ 306 @Nullable findFocusedNodeInRoot(@onNull AccessibilityNodeInfo root)307 AccessibilityNodeInfo findFocusedNodeInRoot(@NonNull AccessibilityNodeInfo root) { 308 AccessibilityNodeInfo focusedNode = findFocusedNodeInRootInternal(root); 309 if (focusedNode != null && Utils.isFocusParkingView(focusedNode)) { 310 focusedNode.recycle(); 311 return null; 312 } 313 return focusedNode; 314 } 315 316 /** 317 * Searches {@code root} and its descendants, and returns the currently focused node, if any, 318 * or returns null if not found. The caller is responsible for recycling the result. 319 */ 320 @Nullable findFocusedNodeInRootInternal( @onNull AccessibilityNodeInfo root)321 private AccessibilityNodeInfo findFocusedNodeInRootInternal( 322 @NonNull AccessibilityNodeInfo root) { 323 AccessibilityNodeInfo surfaceView = null; 324 if (!isClientNode(root)) { 325 AccessibilityNodeInfo focusedNode = Utils.findFocusWithRetry(root); 326 if (focusedNode != null && Utils.isSurfaceView(focusedNode)) { 327 // The focused node represents a SurfaceView. In this case the root node is actually 328 // a client node but Navigator doesn't know that because SurfaceViewHelper doesn't 329 // know the package name of the client app. 330 // Although the package name of the client app will be stored in SurfaceViewHelper 331 // when RotaryService handles TYPE_WINDOW_STATE_CHANGED event, RotaryService may not 332 // receive the event. For example, RotaryService may have been killed and restarted. 333 // In this case, Navigator should store the package name. 334 surfaceView = focusedNode; 335 addClientApp(surfaceView.getPackageName()); 336 } else { 337 return focusedNode; 338 } 339 } 340 341 // The root node is in client app, which contains a SurfaceView to display the embedded 342 // view hierarchy. In this case only search inside the embedded view hierarchy. 343 if (surfaceView == null) { 344 surfaceView = findSurfaceViewInRoot(root); 345 } 346 if (surfaceView == null) { 347 L.w("Failed to find SurfaceView in client app " + root); 348 return null; 349 } 350 if (surfaceView.getChildCount() == 0) { 351 L.d("Host app is not loaded yet"); 352 surfaceView.recycle(); 353 return null; 354 } 355 AccessibilityNodeInfo embeddedRoot = surfaceView.getChild(0); 356 surfaceView.recycle(); 357 if (embeddedRoot == null) { 358 L.w("Failed to get the root of host app"); 359 return null; 360 } 361 AccessibilityNodeInfo focusedNode = embeddedRoot.findFocus(FOCUS_INPUT); 362 embeddedRoot.recycle(); 363 return focusedNode; 364 } 365 366 /** 367 * Searches the window containing {@code node}, and returns the node representing a {@link 368 * FocusParkingView}, if any, or returns null if not found. The caller is responsible for 369 * recycling the result. 370 */ 371 @Nullable findFocusParkingView(@onNull AccessibilityNodeInfo node)372 AccessibilityNodeInfo findFocusParkingView(@NonNull AccessibilityNodeInfo node) { 373 AccessibilityNodeInfo root = getRoot(node); 374 AccessibilityNodeInfo fpv = findFocusParkingViewInRoot(root); 375 root.recycle(); 376 return fpv; 377 } 378 379 /** 380 * Searches {@code root} and its descendants, and returns the node representing a {@link 381 * FocusParkingView}, if any, or returns null if not found. The caller is responsible for 382 * recycling the result. 383 */ 384 @Nullable findFocusParkingViewInRoot(@onNull AccessibilityNodeInfo root)385 AccessibilityNodeInfo findFocusParkingViewInRoot(@NonNull AccessibilityNodeInfo root) { 386 return mTreeTraverser.depthFirstSearch( 387 root, 388 /* skipPredicate= */ Utils::isFocusArea, 389 /* targetPredicate= */ Utils::isFocusParkingView 390 ); 391 } 392 393 /** 394 * Searches {@code root} and its descendants, and returns the node representing a {@link 395 * android.view.SurfaceView}, if any, or returns null if not found. The caller is responsible 396 * for recycling the result. 397 */ 398 @Nullable findSurfaceViewInRoot(@onNull AccessibilityNodeInfo root)399 AccessibilityNodeInfo findSurfaceViewInRoot(@NonNull AccessibilityNodeInfo root) { 400 return mTreeTraverser.depthFirstSearch(root, /* targetPredicate= */ Utils::isSurfaceView); 401 } 402 403 /** 404 * Returns the best target focus area for a nudge in the given {@code direction}. The caller is 405 * responsible for recycling the result. 406 * 407 * @param windows a list of windows to search from 408 * @param sourceNode the current focus 409 * @param currentFocusArea the current focus area 410 * @param direction nudge direction, must be {@link View#FOCUS_UP}, {@link 411 * View#FOCUS_DOWN}, {@link View#FOCUS_LEFT}, or {@link 412 * View#FOCUS_RIGHT} 413 */ findNudgeTargetFocusArea( @onNull List<AccessibilityWindowInfo> windows, @NonNull AccessibilityNodeInfo sourceNode, @NonNull AccessibilityNodeInfo currentFocusArea, int direction)414 AccessibilityNodeInfo findNudgeTargetFocusArea( 415 @NonNull List<AccessibilityWindowInfo> windows, 416 @NonNull AccessibilityNodeInfo sourceNode, 417 @NonNull AccessibilityNodeInfo currentFocusArea, 418 int direction) { 419 AccessibilityWindowInfo currentWindow = sourceNode.getWindow(); 420 if (currentWindow == null) { 421 L.e("Currently focused window is null"); 422 return null; 423 } 424 425 // Build a list of candidate focus areas, starting with all the other focus areas in the 426 // same window as the current focus area. 427 List<AccessibilityNodeInfo> candidateFocusAreas = findNonEmptyFocusAreas(currentWindow); 428 for (AccessibilityNodeInfo focusArea : candidateFocusAreas) { 429 if (focusArea.equals(currentFocusArea)) { 430 candidateFocusAreas.remove(focusArea); 431 focusArea.recycle(); 432 break; 433 } 434 } 435 436 List<Rect> candidateFocusAreasBounds = new ArrayList<>(); 437 for (AccessibilityNodeInfo focusArea : candidateFocusAreas) { 438 Rect bounds = Utils.getBoundsInScreen(focusArea); 439 candidateFocusAreasBounds.add(bounds); 440 } 441 442 maybeAddImplicitFocusArea(currentWindow, candidateFocusAreas, candidateFocusAreasBounds); 443 444 // If the current focus area is an explicit focus area, use its focus area bounds to find 445 // nudge target as usual. Otherwise, use the tailored bounds, which was added as the last 446 // element of the list in maybeAddImplicitFocusArea(). 447 Rect currentFocusAreaBounds; 448 if (Utils.isFocusArea(currentFocusArea)) { 449 currentFocusAreaBounds = Utils.getBoundsInScreen(currentFocusArea); 450 } else if (candidateFocusAreasBounds.size() > 0) { 451 currentFocusAreaBounds = 452 candidateFocusAreasBounds.get(candidateFocusAreasBounds.size() - 1); 453 } else { 454 // TODO(b/323112198): this should never happen, but let's try to recover from this. 455 L.e("currentFocusArea is an implicit focus area but not added to" 456 + " currentFocusAreaBounds"); 457 L.d("sourceNode:" + sourceNode); 458 L.d("currentFocusArea:" + currentFocusArea); 459 AccessibilityNodeInfo root = getRoot(sourceNode); 460 Utils.printDescendants(root, Utils.LOG_INDENT); 461 Utils.recycleNode(root); 462 463 currentFocusArea.recycle(); 464 currentFocusArea = getAncestorFocusArea(sourceNode); 465 currentFocusAreaBounds = Utils.getBoundsInScreen(currentFocusArea); 466 L.d("updated currentFocusArea:" + currentFocusArea); 467 } 468 469 if (currentWindow.getType() != TYPE_INPUT_METHOD 470 || shouldNudgeOutOfIme(sourceNode, currentFocusArea, candidateFocusAreas, 471 direction)) { 472 // Add candidate focus areas in other windows in the given direction. 473 List<AccessibilityWindowInfo> candidateWindows = new ArrayList<>(); 474 boolean isSourceNodeEditable = sourceNode.isEditable(); 475 addWindowsInDirection(windows, currentWindow, candidateWindows, direction, 476 isSourceNodeEditable); 477 currentWindow.recycle(); 478 for (AccessibilityWindowInfo window : candidateWindows) { 479 List<AccessibilityNodeInfo> focusAreasInAnotherWindow = 480 findNonEmptyFocusAreas(window); 481 candidateFocusAreas.addAll(focusAreasInAnotherWindow); 482 483 for (AccessibilityNodeInfo focusArea : focusAreasInAnotherWindow) { 484 Rect bounds = Utils.getBoundsInScreen(focusArea); 485 candidateFocusAreasBounds.add(bounds); 486 } 487 488 maybeAddImplicitFocusArea(window, candidateFocusAreas, candidateFocusAreasBounds); 489 } 490 } 491 492 Rect sourceBounds = Utils.getBoundsInScreen(sourceNode); 493 // Choose the best candidate as our target focus area. 494 AccessibilityNodeInfo targetFocusArea = chooseBestNudgeCandidate(sourceBounds, 495 currentFocusAreaBounds, candidateFocusAreas, candidateFocusAreasBounds, direction); 496 Utils.recycleNodes(candidateFocusAreas); 497 return targetFocusArea; 498 } 499 500 /** 501 * If there are orphan nodes in {@code window}, treats the root node of the window as an 502 * implicit focus area, and add it to {@code candidateFocusAreas}. Besides, tailors its bounds 503 * so that it just wraps its orphan descendants, and adds the tailored bounds to 504 * {@code candidateFocusAreasBounds}. 505 * Orphan nodes are focusable nodes not wrapped inside any explicitly declared focus areas. 506 * It happens in two scenarios: 507 * <ul> 508 * <li>The app developer wants to treat the entire window as a focus area but doesn't bother 509 * declaring a focus area to wrap around them. This is allowed. 510 * <li>The app developer intends to declare focus areas to wrap around focusable views, but 511 * misses some focusable views, causing them to be unreachable via rotary controller. 512 * This is not allowed, but RotaryService will try its best to make them reachable. 513 * </ul> 514 */ 515 @VisibleForTesting maybeAddImplicitFocusArea(@onNull AccessibilityWindowInfo window, @NonNull List<AccessibilityNodeInfo> candidateFocusAreas, @NonNull List<Rect> candidateFocusAreasBounds)516 void maybeAddImplicitFocusArea(@NonNull AccessibilityWindowInfo window, 517 @NonNull List<AccessibilityNodeInfo> candidateFocusAreas, 518 @NonNull List<Rect> candidateFocusAreasBounds) { 519 AccessibilityNodeInfo root = window.getRoot(); 520 if (root == null) { 521 L.e("No root node for " + window); 522 return; 523 } 524 // If the root node is in the client app and therefore contains a SurfaceView, skip the view 525 // hierarchy of the client app, and scan the view hierarchy of the host app, which is 526 // embedded in the SurfaceView. 527 if (isClientNode(root)) { 528 L.v("Root node is client node " + root); 529 AccessibilityNodeInfo hostRoot = getDescendantHostRoot(root); 530 root.recycle(); 531 if (hostRoot == null || !hasFocusableDescendants(hostRoot)) { 532 L.w("No host node or host node has no focusable descendants " + hostRoot); 533 Utils.recycleNode(hostRoot); 534 return; 535 } 536 candidateFocusAreas.add(hostRoot); 537 Rect bounds = new Rect(); 538 // To make things simple, just use the node's bounds. Don't tailor the bounds. 539 hostRoot.getBoundsInScreen(bounds); 540 candidateFocusAreasBounds.add(bounds); 541 return; 542 } 543 544 Rect bounds = computeMinimumBoundsForOrphanDescendants(root); 545 if (bounds.isEmpty()) { 546 return; 547 } 548 L.w("The root node contains focusable nodes that are not inside any focus " 549 + "areas: " + root); 550 candidateFocusAreas.add(root); 551 candidateFocusAreasBounds.add(bounds); 552 } 553 554 /** 555 * Returns whether it should nudge out the IME window. If the current window is IME window and 556 * there are candidate FocusAreas in it for the given direction, it shouldn't nudge out of the 557 * IME window. 558 */ shouldNudgeOutOfIme(@onNull AccessibilityNodeInfo sourceNode, @NonNull AccessibilityNodeInfo currentFocusArea, @NonNull List<AccessibilityNodeInfo> focusAreasInCurrentWindow, int direction)559 private boolean shouldNudgeOutOfIme(@NonNull AccessibilityNodeInfo sourceNode, 560 @NonNull AccessibilityNodeInfo currentFocusArea, 561 @NonNull List<AccessibilityNodeInfo> focusAreasInCurrentWindow, 562 int direction) { 563 if (!focusAreasInCurrentWindow.isEmpty()) { 564 Rect sourceBounds = Utils.getBoundsInScreen(sourceNode); 565 Rect sourceFocusAreaBounds = Utils.getBoundsInScreen(currentFocusArea); 566 Rect candidateBounds = Utils.getBoundsInScreen(currentFocusArea); 567 for (AccessibilityNodeInfo candidate : focusAreasInCurrentWindow) { 568 if (isCandidate(sourceBounds, sourceFocusAreaBounds, candidate, candidateBounds, 569 direction)) { 570 return false; 571 } 572 } 573 } 574 return true; 575 } 576 containsWebViewWithFocusableDescendants(@onNull AccessibilityNodeInfo node)577 private boolean containsWebViewWithFocusableDescendants(@NonNull AccessibilityNodeInfo node) { 578 List<AccessibilityNodeInfo> webViews = new ArrayList<>(); 579 mTreeTraverser.depthFirstSelect(node, Utils::isWebView, webViews); 580 if (webViews.isEmpty()) { 581 return false; 582 } 583 boolean hasFocusableDescendant = false; 584 for (AccessibilityNodeInfo webView : webViews) { 585 if (webViewHasFocusableDescendants(webView)) { 586 hasFocusableDescendant = true; 587 break; 588 } 589 } 590 Utils.recycleNodes(webViews); 591 return hasFocusableDescendant; 592 } 593 webViewHasFocusableDescendants(@onNull AccessibilityNodeInfo webView)594 private boolean webViewHasFocusableDescendants(@NonNull AccessibilityNodeInfo webView) { 595 AccessibilityNodeInfo focusableDescendant = mTreeTraverser.depthFirstSearch(webView, 596 Utils::canPerformFocus); 597 if (focusableDescendant == null) { 598 return false; 599 } 600 focusableDescendant.recycle(); 601 return true; 602 } 603 isWebViewWithFocusableDescendants(@onNull AccessibilityNodeInfo node)604 private boolean isWebViewWithFocusableDescendants(@NonNull AccessibilityNodeInfo node) { 605 return Utils.isWebView(node) && webViewHasFocusableDescendants(node); 606 } 607 608 /** 609 * Adds all the {@code windows} in the given {@code direction} of the given {@code source} 610 * window to the given list if the {@code source} window is not an overlay. If it's an overlay 611 * and the source node is editable, adds the IME window only. Otherwise does nothing. 612 */ addWindowsInDirection(@onNull List<AccessibilityWindowInfo> windows, @NonNull AccessibilityWindowInfo source, @NonNull List<AccessibilityWindowInfo> results, int direction, boolean isSourceNodeEditable)613 private void addWindowsInDirection(@NonNull List<AccessibilityWindowInfo> windows, 614 @NonNull AccessibilityWindowInfo source, 615 @NonNull List<AccessibilityWindowInfo> results, 616 int direction, 617 boolean isSourceNodeEditable) { 618 Rect sourceBounds = new Rect(); 619 source.getBoundsInScreen(sourceBounds); 620 boolean isSourceWindowOverlayWindow = isOverlayWindow(source, sourceBounds); 621 Rect destBounds = new Rect(); 622 for (AccessibilityWindowInfo window : windows) { 623 if (window.equals(source)) { 624 continue; 625 } 626 // Nudging out of the overlay window is not allowed unless the source node is editable 627 // and the target window is an IME window. E.g., nudging from the EditText in the Dialog 628 // to the IME is allowed, while nudging from the Button in the Dialog to the IME is not 629 // allowed. 630 if (isSourceWindowOverlayWindow 631 && (!isSourceNodeEditable || window.getType() != TYPE_INPUT_METHOD)) { 632 continue; 633 } 634 635 window.getBoundsInScreen(destBounds); 636 // Even if only part of destBounds is in the given direction of sourceBounds, we 637 // still include it because that part may contain the target focus area. 638 if (FocusFinder.isPartiallyInDirection(sourceBounds, destBounds, direction)) { 639 results.add(window); 640 } 641 } 642 } 643 644 /** 645 * Returns whether the given {@code window} with the given {@code bounds} is an overlay window. 646 * <p> 647 * If the source window is an application window on the default display and it's smaller than 648 the display, then it's either a TaskView window or an overlay window (such as a Dialog 649 window). The ID of a TaskView task is different from the full screen application, while 650 the ID of an overlay task is the same with the full screen application, so task ID is used 651 to decide whether it's an overlay window. 652 */ isOverlayWindow(@onNull AccessibilityWindowInfo window, @NonNull Rect bounds)653 private boolean isOverlayWindow(@NonNull AccessibilityWindowInfo window, @NonNull Rect bounds) { 654 return window.getType() == TYPE_APPLICATION 655 && window.getDisplayId() == Display.DEFAULT_DISPLAY 656 && !mAppWindowBounds.equals(bounds) 657 && window.getTaskId() == mAppWindowTaskId; 658 } 659 660 /** 661 * Returns whether nudging to the given {@code direction} can dismiss the given {@code window} 662 * with the given {@code bounds}. 663 */ isDismissible(@onNull AccessibilityWindowInfo window, @NonNull Rect bounds, @View.FocusRealDirection int direction)664 boolean isDismissible(@NonNull AccessibilityWindowInfo window, 665 @NonNull Rect bounds, 666 @View.FocusRealDirection int direction) { 667 // Only overlay windows can be dismissed. 668 if (!isOverlayWindow(window, bounds)) { 669 return false; 670 } 671 // The window can be dismissed when part of the underlying window is not covered by it in 672 // the given direction. 673 switch (direction) { 674 case FOCUS_UP: 675 return mAppWindowBounds.top < bounds.top; 676 case FOCUS_DOWN: 677 return mAppWindowBounds.bottom > bounds.bottom; 678 case FOCUS_LEFT: 679 return mAppWindowBounds.left < bounds.left; 680 case FOCUS_RIGHT: 681 return mAppWindowBounds.right > bounds.right; 682 } 683 return false; 684 } 685 686 /** 687 * Scans the view hierarchy of the given {@code window} looking for explicit focus areas with 688 * focusable descendants and returns the focus areas. The caller is responsible for recycling 689 * the result. 690 */ 691 @NonNull 692 @VisibleForTesting findNonEmptyFocusAreas(@onNull AccessibilityWindowInfo window)693 List<AccessibilityNodeInfo> findNonEmptyFocusAreas(@NonNull AccessibilityWindowInfo window) { 694 List<AccessibilityNodeInfo> results = new ArrayList<>(); 695 AccessibilityNodeInfo rootNode = window.getRoot(); 696 if (rootNode == null) { 697 L.e("No root node for " + window); 698 } else if (!isClientNode(rootNode)) { 699 addNonEmptyFocusAreas(rootNode, results); 700 } 701 // If the root node is in the client app, it won't contain any explicit focus areas, so 702 // skip it. 703 704 Utils.recycleNode(rootNode); 705 return results; 706 } 707 708 /** 709 * Searches from {@code clientNode}, and returns the root of the embedded view hierarchy if any, 710 * or returns null if not found. The caller is responsible for recycling the result. 711 */ 712 @Nullable getDescendantHostRoot(@onNull AccessibilityNodeInfo clientNode)713 AccessibilityNodeInfo getDescendantHostRoot(@NonNull AccessibilityNodeInfo clientNode) { 714 return mTreeTraverser.depthFirstSearch(clientNode, this::isHostNode); 715 } 716 717 /** 718 * Returns whether the given window is the Heads-up Notification (HUN) window. The HUN window 719 * is identified by the left and right edges. The top and bottom vary depending on whether the 720 * HUN appears at the top or bottom of the screen and on the height of the notification being 721 * displayed so they aren't used. 722 */ isHunWindow(@ullable AccessibilityWindowInfo window)723 boolean isHunWindow(@Nullable AccessibilityWindowInfo window) { 724 if (window == null || window.getType() != AccessibilityWindowInfo.TYPE_SYSTEM) { 725 return false; 726 } 727 Rect bounds = new Rect(); 728 window.getBoundsInScreen(bounds); 729 return bounds.left == mHunLeft && bounds.right == mHunRight; 730 } 731 732 /** 733 * Searches from the given node up through its ancestors to the containing focus area, looking 734 * for a node that's marked as horizontally or vertically scrollable. Returns a copy of the 735 * first such node or null if none is found. The caller is responsible for recycling the result. 736 */ 737 @Nullable findScrollableContainer(@onNull AccessibilityNodeInfo node)738 AccessibilityNodeInfo findScrollableContainer(@NonNull AccessibilityNodeInfo node) { 739 return mTreeTraverser.findNodeOrAncestor(node, /* stopPredicate= */ Utils::isFocusArea, 740 /* targetPredicate= */ Utils::isScrollableContainer); 741 } 742 743 /** 744 * Returns the previous node before {@code referenceNode} in Tab order that can take focus or 745 * the next node after {@code referenceNode} in Tab order that can take focus, depending on 746 * {@code direction}. The search is limited to descendants of {@code containerNode}. Returns 747 * null if there are no descendants that can take focus in the given direction. The caller is 748 * responsible for recycling the result. 749 * 750 * @param containerNode the node with descendants 751 * @param referenceNode a descendant of {@code containerNode} to start from 752 * @param direction {@link View#FOCUS_FORWARD} or {@link View#FOCUS_BACKWARD} 753 * @return the node before or after {@code referenceNode} or null if none 754 */ 755 @Nullable findFocusableDescendantInDirection( @onNull AccessibilityNodeInfo containerNode, @NonNull AccessibilityNodeInfo referenceNode, int direction)756 AccessibilityNodeInfo findFocusableDescendantInDirection( 757 @NonNull AccessibilityNodeInfo containerNode, 758 @NonNull AccessibilityNodeInfo referenceNode, 759 int direction) { 760 AccessibilityNodeInfo targetNode = copyNode(referenceNode); 761 do { 762 AccessibilityNodeInfo nextTargetNode = targetNode.focusSearch(direction); 763 if (nextTargetNode == null 764 || nextTargetNode.equals(containerNode) 765 || !Utils.isDescendant(containerNode, nextTargetNode)) { 766 Utils.recycleNode(nextTargetNode); 767 Utils.recycleNode(targetNode); 768 return null; 769 } 770 if (nextTargetNode.equals(referenceNode) || nextTargetNode.equals(targetNode)) { 771 L.w((direction == View.FOCUS_FORWARD ? "Next" : "Previous") 772 + " node is the same node: " + referenceNode); 773 Utils.recycleNode(nextTargetNode); 774 Utils.recycleNode(targetNode); 775 return null; 776 } 777 targetNode.recycle(); 778 targetNode = nextTargetNode; 779 } while (!Utils.canTakeFocus(targetNode)); 780 return targetNode; 781 } 782 783 /** 784 * Returns the first descendant of {@code node} which can take focus. The nodes are searched in 785 * in depth-first order, not including {@code node} itself. If no descendant can take focus, 786 * null is returned. The caller is responsible for recycling the result. 787 */ 788 @Nullable findFirstFocusableDescendant(@onNull AccessibilityNodeInfo node)789 AccessibilityNodeInfo findFirstFocusableDescendant(@NonNull AccessibilityNodeInfo node) { 790 return mTreeTraverser.depthFirstSearch(node, 791 candidateNode -> candidateNode != node && Utils.canTakeFocus(candidateNode)); 792 } 793 794 /** 795 * Returns the first orphan descendant (focusable descendant not inside any focus areas) of 796 * {@code node}. The nodes are searched in depth-first order, not including {@code node} itself. 797 * If not found, null is returned. The caller is responsible for recycling the result. 798 */ 799 @Nullable findFirstOrphan(@onNull AccessibilityNodeInfo node)800 AccessibilityNodeInfo findFirstOrphan(@NonNull AccessibilityNodeInfo node) { 801 return mTreeTraverser.depthFirstSearch(node, 802 /* skipPredicate= */ Utils::isFocusArea, 803 /* targetPredicate= */ candidateNode -> candidateNode != node 804 && Utils.canTakeFocus(candidateNode)); 805 } 806 807 /** 808 * Returns the last descendant of {@code node} which can take focus. The nodes are searched in 809 * reverse depth-first order, not including {@code node} itself. If no descendant can take 810 * focus, null is returned. The caller is responsible for recycling the result. 811 */ 812 @Nullable findLastFocusableDescendant(@onNull AccessibilityNodeInfo node)813 AccessibilityNodeInfo findLastFocusableDescendant(@NonNull AccessibilityNodeInfo node) { 814 return mTreeTraverser.reverseDepthFirstSearch(node, 815 candidateNode -> candidateNode != node && Utils.canTakeFocus(candidateNode)); 816 } 817 818 /** 819 * Scans descendants of the given {@code rootNode} looking for explicit focus areas with 820 * focusable descendants and adds the focus areas to the given list. It doesn't scan inside 821 * focus areas since nested focus areas aren't allowed. It ignores focus areas without 822 * focusable descendants, because once we found the best candidate focus area, we don't dig 823 * into other ones. If it has no descendants to take focus, the nudge will fail. The caller is 824 * responsible for recycling added nodes. 825 * 826 * @param rootNode the root to start scanning from 827 * @param results a list of focus areas to add to 828 */ addNonEmptyFocusAreas(@onNull AccessibilityNodeInfo rootNode, @NonNull List<AccessibilityNodeInfo> results)829 private void addNonEmptyFocusAreas(@NonNull AccessibilityNodeInfo rootNode, 830 @NonNull List<AccessibilityNodeInfo> results) { 831 mTreeTraverser.depthFirstSelect(rootNode, 832 (focusArea) -> Utils.isFocusArea(focusArea) && hasFocusableDescendants(focusArea), 833 results); 834 } 835 hasFocusableDescendants(@onNull AccessibilityNodeInfo focusArea)836 private boolean hasFocusableDescendants(@NonNull AccessibilityNodeInfo focusArea) { 837 return Utils.canHaveFocus(focusArea) || containsWebViewWithFocusableDescendants(focusArea); 838 } 839 840 /** 841 * Returns the minimum rectangle wrapping the given {@code node}'s orphan descendants. If 842 * {@code node} has no orphan descendants, returns an empty {@link Rect}. 843 */ 844 @NonNull 845 @VisibleForTesting computeMinimumBoundsForOrphanDescendants( @onNull AccessibilityNodeInfo node)846 Rect computeMinimumBoundsForOrphanDescendants( 847 @NonNull AccessibilityNodeInfo node) { 848 Rect bounds = new Rect(); 849 if (Utils.isFocusArea(node) || Utils.isFocusParkingView(node)) { 850 return bounds; 851 } 852 if (Utils.canTakeFocus(node) || isWebViewWithFocusableDescendants(node)) { 853 return Utils.getBoundsInScreen(node); 854 } 855 for (int i = 0; i < node.getChildCount(); i++) { 856 AccessibilityNodeInfo child = node.getChild(i); 857 if (child == null) { 858 continue; 859 } 860 Rect childBounds = computeMinimumBoundsForOrphanDescendants(child); 861 child.recycle(); 862 if (childBounds != null) { 863 bounds.union(childBounds); 864 } 865 } 866 return bounds; 867 } 868 869 /** 870 * Returns a copy of the best candidate from among the given {@code candidates} for a nudge 871 * from {@code sourceNode} in the given {@code direction}. Returns null if none of the {@code 872 * candidates} are in the given {@code direction}. The caller is responsible for recycling the 873 * result. 874 * 875 * @param candidates could be a list of {@link FocusArea}s, or a list of focusable views 876 */ 877 @Nullable chooseBestNudgeCandidate(@onNull Rect sourceBounds, @NonNull Rect sourceFocusAreaBounds, @NonNull List<AccessibilityNodeInfo> candidates, @NonNull List<Rect> candidatesBounds, int direction)878 private AccessibilityNodeInfo chooseBestNudgeCandidate(@NonNull Rect sourceBounds, 879 @NonNull Rect sourceFocusAreaBounds, 880 @NonNull List<AccessibilityNodeInfo> candidates, 881 @NonNull List<Rect> candidatesBounds, 882 int direction) { 883 if (candidates.isEmpty()) { 884 return null; 885 } 886 AccessibilityNodeInfo bestNode = null; 887 Rect bestBounds = new Rect(); 888 for (int i = 0; i < candidates.size(); i++) { 889 AccessibilityNodeInfo candidate = candidates.get(i); 890 Rect candidateBounds = candidatesBounds.get(i); 891 if (isCandidate(sourceBounds, sourceFocusAreaBounds, candidate, candidateBounds, 892 direction)) { 893 if (bestNode == null || FocusFinder.isBetterCandidate( 894 direction, sourceBounds, candidateBounds, bestBounds)) { 895 bestNode = candidate; 896 bestBounds.set(candidateBounds); 897 } 898 } 899 } 900 return copyNode(bestNode); 901 } 902 903 /** 904 * Returns whether the given {@code node} is a candidate from {@code sourceBounds} to the given 905 * {@code direction}. 906 * <p> 907 * To be a candidate, the node 908 * <ul> 909 * <li>must be considered a candidate by {@link FocusFinder#isCandidate} if it represents a 910 * focusable view within a focus area 911 * <li>must be in the {@code direction} of the {@code sourceFocusAreaBounds} and one of its 912 * focusable descendants must be a candidate if it represents a focus area 913 * </ul> 914 */ isCandidate(@onNull Rect sourceBounds, @NonNull Rect sourceFocusAreaBounds, @NonNull AccessibilityNodeInfo node, @NonNull Rect nodeBounds, int direction)915 private boolean isCandidate(@NonNull Rect sourceBounds, 916 @NonNull Rect sourceFocusAreaBounds, 917 @NonNull AccessibilityNodeInfo node, 918 @NonNull Rect nodeBounds, 919 int direction) { 920 AccessibilityNodeInfo candidate = mTreeTraverser.depthFirstSearch(node, 921 /* skipPredicate= */ candidateNode -> { 922 if (Utils.canTakeFocus(candidateNode)) { 923 return false; 924 } 925 // If a node can't take focus, it represents a focus area. If the focus area 926 // doesn't intersect with sourceFocusAreaBounds, and it's not in the given 927 // direction of sourceFocusAreaBounds, it's not a candidate, so we should return 928 // true to stop searching. 929 return !Rect.intersects(nodeBounds, sourceFocusAreaBounds) 930 && !FocusFinder.isInDirection( 931 sourceFocusAreaBounds, nodeBounds, direction); 932 }, 933 /* targetPredicate= */ candidateNode -> { 934 // RotaryService can navigate to nodes in a WebView or a ComposeView even when 935 // off-screen, so we use canPerformFocus() to skip the bounds check. 936 if (isInVirtualNodeHierarchy(candidateNode)) { 937 return Utils.canPerformFocus(candidateNode); 938 } 939 // If a node isn't visible to the user, e.g. another window is obscuring it, 940 // skip it. 941 if (!candidateNode.isVisibleToUser()) { 942 return false; 943 } 944 // If a node can't take focus, it represents a focus area, so we return false to 945 // skip the node and let it search its descendants. 946 if (!Utils.canTakeFocus(candidateNode)) { 947 return false; 948 } 949 // The node represents a focusable view in a focus area, so check the geometry. 950 return FocusFinder.isCandidate(sourceBounds, nodeBounds, direction); 951 }); 952 if (candidate == null) { 953 return false; 954 } 955 candidate.recycle(); 956 return true; 957 } 958 copyNode(@ullable AccessibilityNodeInfo node)959 private AccessibilityNodeInfo copyNode(@Nullable AccessibilityNodeInfo node) { 960 return mNodeCopier.copy(node); 961 } 962 963 /** 964 * Returns the closest ancestor focus area of the given {@code node}. 965 * <ul> 966 * <li> If the given {@code node} is a {@link FocusArea} node or a descendant of a {@link 967 * FocusArea} node, returns the {@link FocusArea} node. 968 * <li> If there are no explicitly declared {@link FocusArea}s among the ancestors of this 969 * view, and this view is not in an embedded view hierarchy, returns the root node. 970 * <li> If there are no explicitly declared {@link FocusArea}s among the ancestors of this 971 * view, and this view is in an embedded view hierarchy, returns the root node of 972 * embedded view hierarchy. 973 * </ul> 974 * The caller is responsible for recycling the result. 975 */ 976 @NonNull getAncestorFocusArea(@onNull AccessibilityNodeInfo node)977 AccessibilityNodeInfo getAncestorFocusArea(@NonNull AccessibilityNodeInfo node) { 978 Predicate<AccessibilityNodeInfo> isFocusAreaOrRoot = candidateNode -> { 979 if (Utils.isFocusArea(candidateNode)) { 980 // The candidateNode is a focus area. 981 return true; 982 } 983 AccessibilityNodeInfo parent = candidateNode.getParent(); 984 if (parent == null) { 985 // The candidateNode is the root node. 986 return true; 987 } 988 if (Utils.isSurfaceView(parent)) { 989 // Treat the root of embedded view hierarchy (i.e., the only child of the 990 // SurfaceView) as an implicit focus area. 991 return true; 992 } 993 parent.recycle(); 994 return false; 995 }; 996 AccessibilityNodeInfo result = mTreeTraverser.findNodeOrAncestor(node, isFocusAreaOrRoot); 997 if (result == null || !Utils.isFocusArea(result)) { 998 L.w("Ancestor focus area for node " + node + " is not an explicit FocusArea: " 999 + result); 1000 } 1001 return result; 1002 } 1003 1004 /** 1005 * Returns a copy of {@code node} or the nearest ancestor that represents a {@code WebView}. 1006 * Returns null if {@code node} isn't a {@code WebView} and isn't a descendant of a {@code 1007 * WebView}. 1008 */ 1009 @Nullable findWebViewAncestor(@onNull AccessibilityNodeInfo node)1010 private AccessibilityNodeInfo findWebViewAncestor(@NonNull AccessibilityNodeInfo node) { 1011 return mTreeTraverser.findNodeOrAncestor(node, Utils::isWebView); 1012 } 1013 1014 /** 1015 * Returns a copy of {@code node} or the nearest ancestor that represents a {@code ComposeView} 1016 * or a {@code WebView}. Returns null if {@code node} isn't a {@code ComposeView} or a 1017 * {@code WebView} and is not a descendant of a {@code ComposeView} or a {@code WebView}. 1018 * 1019 * TODO(b/192274274): This method may not be necessary anymore if Compose supports focusSearch. 1020 */ 1021 @Nullable findVirtualViewAncestor(@onNull AccessibilityNodeInfo node)1022 private AccessibilityNodeInfo findVirtualViewAncestor(@NonNull AccessibilityNodeInfo node) { 1023 return mTreeTraverser.findNodeOrAncestor(node, /* targetPredicate= */ (nodeInfo) -> 1024 Utils.isComposeView(nodeInfo) || Utils.isWebView(nodeInfo)); 1025 } 1026 1027 /** Returns whether {@code node} is a {@code WebView} or is a descendant of one. */ isInWebView(@onNull AccessibilityNodeInfo node)1028 boolean isInWebView(@NonNull AccessibilityNodeInfo node) { 1029 AccessibilityNodeInfo webView = findWebViewAncestor(node); 1030 if (webView == null) { 1031 return false; 1032 } 1033 webView.recycle(); 1034 return true; 1035 } 1036 1037 /** 1038 * Returns whether {@code node} is a {@code ComposeView}, is a {@code WebView}, or is a 1039 * descendant of either. 1040 */ isInVirtualNodeHierarchy(@onNull AccessibilityNodeInfo node)1041 boolean isInVirtualNodeHierarchy(@NonNull AccessibilityNodeInfo node) { 1042 AccessibilityNodeInfo virtualViewAncestor = findVirtualViewAncestor(node); 1043 if (virtualViewAncestor == null) { 1044 return false; 1045 } 1046 virtualViewAncestor.recycle(); 1047 return true; 1048 } 1049 1050 /** 1051 * Returns the next focusable node after {@code candidate} in {@code direction} in {@code 1052 * root} or null if none. This handles navigating into a WebView as well as within a WebView. 1053 * This also handles navigating into a ComposeView, as well as within a ComposeView. 1054 */ 1055 @Nullable findNextFocusableInVirtualRoot( @onNull AccessibilityNodeInfo root, @NonNull AccessibilityNodeInfo candidate, int direction)1056 private AccessibilityNodeInfo findNextFocusableInVirtualRoot( 1057 @NonNull AccessibilityNodeInfo root, 1058 @NonNull AccessibilityNodeInfo candidate, int direction) { 1059 // focusSearch() doesn't work in WebViews or ComposeViews so use tree traversal instead. 1060 if (Utils.isWebView(candidate) || Utils.isComposeView(candidate)) { 1061 if (direction == View.FOCUS_FORWARD) { 1062 // When entering into the root of a virtual node hierarchy, find the first focusable 1063 // child node of the root if any. 1064 return findFirstFocusableDescendantInVirtualRoot(candidate); 1065 } else { 1066 // When backing into the root of a virtual node hierarchy, find the last focusable 1067 // child node of the root if any. 1068 return findLastFocusableDescendantInVirtualRoot(candidate); 1069 } 1070 } else { 1071 // When navigating within a virtual view hierarchy, find the next or previous focusable 1072 // node in depth-first order. 1073 if (direction == View.FOCUS_FORWARD) { 1074 return findFirstFocusDescendantInVirtualRootAfter(root, candidate); 1075 } else { 1076 return findFirstFocusDescendantInVirtualRootBefore(root, candidate); 1077 } 1078 } 1079 } 1080 1081 /** 1082 * Returns the first descendant of {@code webView} which can perform focus. This includes off- 1083 * screen descendants. The nodes are searched in in depth-first order, not including 1084 * {@code root} itself. If no descendant can perform focus, null is returned. The caller is 1085 * responsible for recycling the result. 1086 */ 1087 @Nullable findFirstFocusableDescendantInVirtualRoot( @onNull AccessibilityNodeInfo root)1088 private AccessibilityNodeInfo findFirstFocusableDescendantInVirtualRoot( 1089 @NonNull AccessibilityNodeInfo root) { 1090 return mTreeTraverser.depthFirstSearch(root, 1091 candidateNode -> candidateNode != root && Utils.canPerformFocus(candidateNode)); 1092 } 1093 1094 /** 1095 * Returns the last descendant of {@code root} which can perform focus. This includes off- 1096 * screen descendants. The nodes are searched in reverse depth-first order, not including 1097 * {@code root} itself. If no descendant can perform focus, null is returned. The caller is 1098 * responsible for recycling the result. 1099 */ 1100 @Nullable findLastFocusableDescendantInVirtualRoot( @onNull AccessibilityNodeInfo root)1101 private AccessibilityNodeInfo findLastFocusableDescendantInVirtualRoot( 1102 @NonNull AccessibilityNodeInfo root) { 1103 return mTreeTraverser.reverseDepthFirstSearch(root, 1104 candidateNode -> candidateNode != root && Utils.canPerformFocus(candidateNode)); 1105 } 1106 1107 @Nullable findFirstFocusDescendantInVirtualRootBefore( @onNull AccessibilityNodeInfo root, @NonNull AccessibilityNodeInfo beforeNode)1108 private AccessibilityNodeInfo findFirstFocusDescendantInVirtualRootBefore( 1109 @NonNull AccessibilityNodeInfo root, @NonNull AccessibilityNodeInfo beforeNode) { 1110 boolean[] foundBeforeNode = new boolean[1]; 1111 return mTreeTraverser.reverseDepthFirstSearch(root, 1112 node -> { 1113 if (foundBeforeNode[0] && Utils.canPerformFocus(node)) { 1114 return true; 1115 } 1116 if (node.equals(beforeNode)) { 1117 foundBeforeNode[0] = true; 1118 } 1119 return false; 1120 }); 1121 } 1122 1123 @Nullable 1124 private AccessibilityNodeInfo findFirstFocusDescendantInVirtualRootAfter( 1125 @NonNull AccessibilityNodeInfo root, @NonNull AccessibilityNodeInfo afterNode) { 1126 boolean[] foundAfterNode = new boolean[1]; 1127 return mTreeTraverser.depthFirstSearch(root, 1128 node -> { 1129 if (foundAfterNode[0] && Utils.canPerformFocus(node)) { 1130 return true; 1131 } 1132 if (node.equals(afterNode)) { 1133 foundAfterNode[0] = true; 1134 } 1135 return false; 1136 }); 1137 } 1138 1139 void dump(@NonNull DualDumpOutputStream dumpOutputStream, boolean dumpAsProto, 1140 @NonNull String fieldName, long fieldId) { 1141 long fieldToken = dumpOutputStream.start(fieldName, fieldId); 1142 dumpOutputStream.write("hunLeft", RotaryProtos.Navigator.HUN_LEFT, mHunLeft); 1143 dumpOutputStream.write("hunRight", RotaryProtos.Navigator.HUN_RIGHT, mHunRight); 1144 DumpUtils.writeFocusDirection(dumpOutputStream, dumpAsProto, "hunNudgeDirection", 1145 RotaryProtos.Navigator.HUN_NUDGE_DIRECTION, mHunNudgeDirection); 1146 DumpUtils.writeRect(dumpOutputStream, mAppWindowBounds, "appWindowBounds", 1147 RotaryProtos.Navigator.APP_WINDOW_BOUNDS); 1148 mSurfaceViewHelper.dump(dumpOutputStream, dumpAsProto, "surfaceViewHelper", 1149 RotaryProtos.Navigator.SURFACE_VIEW_HELPER); 1150 dumpOutputStream.end(fieldToken); 1151 } 1152 1153 static String directionToString(@View.FocusRealDirection int direction) { 1154 switch (direction) { 1155 case FOCUS_UP: 1156 return "FOCUS_UP"; 1157 case FOCUS_DOWN: 1158 return "FOCUS_DOWN"; 1159 case FOCUS_LEFT: 1160 return "FOCUS_LEFT"; 1161 case FOCUS_RIGHT: 1162 return "FOCUS_RIGHT"; 1163 default: 1164 return "<unknown direction " + direction + ">"; 1165 } 1166 } 1167 1168 /** Result from {@link #findRotateTarget}. */ 1169 static class FindRotateTargetResult { 1170 @NonNull final AccessibilityNodeInfo node; 1171 final int advancedCount; 1172 1173 FindRotateTargetResult(@NonNull AccessibilityNodeInfo node, int advancedCount) { 1174 this.node = node; 1175 this.advancedCount = advancedCount; 1176 } 1177 } 1178 } 1179