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