car/rotary/Navigator.java

/*
 * Copyright (C) 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.android.car.rotary;

import static android.app.ActivityTaskManager.INVALID_TASK_ID;
import static android.view.View.FOCUS_DOWN;
import static android.view.View.FOCUS_LEFT;
import static android.view.View.FOCUS_RIGHT;
import static android.view.View.FOCUS_UP;
import static android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction.ACTION_SCROLL_BACKWARD;
import static android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction.ACTION_SCROLL_FORWARD;
import static android.view.accessibility.AccessibilityNodeInfo.FOCUS_INPUT;
import static android.view.accessibility.AccessibilityWindowInfo.TYPE_APPLICATION;
import static android.view.accessibility.AccessibilityWindowInfo.TYPE_INPUT_METHOD;

import static com.android.car.internal.ExcludeFromCodeCoverageGeneratedReport.BOILERPLATE_CODE;
import static com.android.car.internal.ExcludeFromCodeCoverageGeneratedReport.DUMP_INFO;

import android.content.pm.PackageManager;
import android.graphics.Rect;
import android.view.Display;
import android.view.View;
import android.view.accessibility.AccessibilityNodeInfo;
import android.view.accessibility.AccessibilityWindowInfo;

import androidx.annotation.NonNull;
import androidx.annotation.Nullable;
import androidx.annotation.VisibleForTesting;

import com.android.car.internal.ExcludeFromCodeCoverageGeneratedReport;
import com.android.car.ui.FocusArea;
import com.android.car.ui.FocusParkingView;
import com.android.internal.util.dump.DualDumpOutputStream;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.function.Predicate;

/**
 * A helper class used for finding the next focusable node when the rotary controller is rotated or
 * nudged.
 */
class Navigator {

    @NonNull
    private NodeCopier mNodeCopier = new NodeCopier();

    @NonNull
    private final TreeTraverser mTreeTraverser = new TreeTraverser();

    @NonNull
    @VisibleForTesting
    final SurfaceViewHelper mSurfaceViewHelper = new SurfaceViewHelper();

    private final int mHunLeft;
    private final int mHunRight;

    @View.FocusRealDirection
    private int mHunNudgeDirection;

    @NonNull
    private final Rect mAppWindowBounds;

    private int mAppWindowTaskId = INVALID_TASK_ID;

    Navigator(int displayWidth, int displayHeight, int hunLeft, int hunRight,
            boolean showHunOnBottom) {
        mHunLeft = hunLeft;
        mHunRight = hunRight;
        mHunNudgeDirection = showHunOnBottom ? FOCUS_DOWN : FOCUS_UP;
        mAppWindowBounds = new Rect(0, 0, displayWidth, displayHeight);
    }

    @VisibleForTesting
    Navigator() {
        this(0, 0, 0, 0, false);
    }

    /**
     * Updates {@link #mAppWindowTaskId} if {@code window} is a full-screen app window on the
     * default display.
     */
    void updateAppWindowTaskId(@NonNull AccessibilityWindowInfo window) {
        if (window.getType() == TYPE_APPLICATION
                && window.getDisplayId() == Display.DEFAULT_DISPLAY) {
            Rect windowBounds = new Rect();
            window.getBoundsInScreen(windowBounds);
            if (mAppWindowBounds.equals(windowBounds)) {
                mAppWindowTaskId = window.getTaskId();
                L.d("Task ID of app window: " + mAppWindowTaskId);
            }
        }
    }

    /** Initializes the package name of the host app. */
    void initHostApp(@NonNull PackageManager packageManager) {
        mSurfaceViewHelper.initHostApp(packageManager);
    }

    /** Clears the package name of the host app if the given {@code packageName} matches. */
    void clearHostApp(@NonNull String packageName) {
        mSurfaceViewHelper.clearHostApp(packageName);
    }

    /** Adds the package name of the client app. */
    void addClientApp(@NonNull CharSequence clientAppPackageName) {
        mSurfaceViewHelper.addClientApp(clientAppPackageName);
    }

    /** Returns whether the given {@code node} represents a view of the host app. */
    boolean isHostNode(@NonNull AccessibilityNodeInfo node) {
        return mSurfaceViewHelper.isHostNode(node);
    }

    /** Returns whether the given {@code node} represents a view of the client app. */
    boolean isClientNode(@NonNull AccessibilityNodeInfo node) {
        return mSurfaceViewHelper.isClientNode(node);
    }

    @Nullable
    AccessibilityWindowInfo findHunWindow(@NonNull List<AccessibilityWindowInfo> windows) {
        for (AccessibilityWindowInfo window : windows) {
            if (isHunWindow(window)) {
                return window;
            }
        }
        return null;
    }

    /**
     * Returns the target focusable for a rotate. The caller is responsible for recycling the node
     * in the result.
     *
     * <p>Limits navigation to focusable views within a scrollable container's viewport, if any.
     *
     * @param sourceNode    the current focus
     * @param direction     rotate direction, must be {@link View#FOCUS_FORWARD} or {@link
     *                      View#FOCUS_BACKWARD}
     * @param rotationCount the number of "ticks" to rotate. Only count nodes that can take focus
     *                      (visible, focusable and enabled). If {@code skipNode} is encountered, it
     *                      isn't counted.
     * @return a FindRotateTargetResult containing a node and a count of the number of times the
     *         search advanced to another node. The node represents a focusable view in the given
     *         {@code direction} from the current focus within the same {@link FocusArea}. If the
     *         first or last view is reached before counting up to {@code rotationCount}, the first
     *         or last view is returned. However, if there are no views that can take focus in the
     *         given {@code direction}, {@code null} is returned.
     */
    @Nullable
    FindRotateTargetResult findRotateTarget(
            @NonNull AccessibilityNodeInfo sourceNode, int direction, int rotationCount) {
        int advancedCount = 0;
        AccessibilityNodeInfo currentFocusArea = getAncestorFocusArea(sourceNode);
        AccessibilityNodeInfo candidate = copyNode(sourceNode);
        AccessibilityNodeInfo target = null;
        while (advancedCount < rotationCount) {
            AccessibilityNodeInfo nextCandidate = null;
            AccessibilityNodeInfo webView = findWebViewAncestor(candidate);
            if (webView != null) {
                nextCandidate = findNextFocusableInWebView(webView, candidate, direction);
            }
            if (nextCandidate == null) {
                // If we aren't in a WebView or there aren't any more focusable nodes within the
                // WebView, use focusSearch().
                nextCandidate = candidate.focusSearch(direction);
            }
            AccessibilityNodeInfo candidateFocusArea =
                    nextCandidate == null ? null : getAncestorFocusArea(nextCandidate);

            // Only advance to nextCandidate if:
            // 1. it's in the same focus area,
            // 2. and it isn't a FocusParkingView (this is to prevent wrap-around when there is only
            //    one focus area in the window, including when the root node is treated as a focus
            //    area),
            // 3. and nextCandidate is different from candidate (if sourceNode is the first
            //    focusable node in the window, searching backward will return sourceNode itself).
            if (nextCandidate != null && currentFocusArea.equals(candidateFocusArea)
                    && !Utils.isFocusParkingView(nextCandidate)
                    && !nextCandidate.equals(candidate)) {
                // We need to skip nextTargetNode if:
                // 1. it can't perform focus action (focusSearch() may return a node with zero
                //    width and height),
                // 2. or it is a scrollable container but it shouldn't be scrolled (i.e., it is not
                //    scrollable, or its descendants can take focus).
                //    When we want to focus on its element directly, we'll skip the container. When
                //    we want to focus on container and scroll it, we won't skip the container.
                if (!Utils.canPerformFocus(nextCandidate)
                        || (Utils.isScrollableContainer(nextCandidate)
                            && !Utils.canScrollableContainerTakeFocus(nextCandidate))) {
                    Utils.recycleNode(candidate);
                    Utils.recycleNode(candidateFocusArea);
                    candidate = nextCandidate;
                    continue;
                }

                // If we're navigating in a scrollable container that can scroll in the specified
                // direction and the next candidate is off-screen or there are no more focusable
                // views within the scrollable container, stop navigating so that any remaining
                // detents are used for scrolling.
                AccessibilityNodeInfo scrollableContainer = findScrollableContainer(candidate);
                AccessibilityNodeInfo.AccessibilityAction scrollAction =
                        direction == View.FOCUS_FORWARD
                                ? ACTION_SCROLL_FORWARD
                                : ACTION_SCROLL_BACKWARD;
                if (scrollableContainer != null
                        && scrollableContainer.getActionList().contains(scrollAction)
                        && (!Utils.isDescendant(scrollableContainer, nextCandidate)
                                || Utils.getBoundsInScreen(nextCandidate).isEmpty())) {
                    Utils.recycleNode(nextCandidate);
                    Utils.recycleNode(candidateFocusArea);
                    break;
                }
                Utils.recycleNode(scrollableContainer);

                Utils.recycleNode(candidate);
                Utils.recycleNode(candidateFocusArea);
                candidate = nextCandidate;
                Utils.recycleNode(target);
                target = copyNode(candidate);
                advancedCount++;
            } else {
                Utils.recycleNode(nextCandidate);
                Utils.recycleNode(candidateFocusArea);
                break;
            }
        }
        currentFocusArea.recycle();
        candidate.recycle();
        if (sourceNode.equals(target)) {
            L.e("Wrap-around on the same node");
            target.recycle();
            return null;
        }
        return target == null ? null : new FindRotateTargetResult(target, advancedCount);
    }

    /** Sets a NodeCopier instance for testing. */
    @VisibleForTesting
    void setNodeCopier(@NonNull NodeCopier nodeCopier) {
        mNodeCopier = nodeCopier;
        mTreeTraverser.setNodeCopier(nodeCopier);
    }

    /**
     * Returns the root node in the tree containing {@code node}. The caller is responsible for
     * recycling the result.
     */
    @NonNull
    AccessibilityNodeInfo getRoot(@NonNull AccessibilityNodeInfo node) {
        // If the node represents a view in the embedded view hierarchy hosted by a SurfaceView,
        // return the root node of the hierarchy, which is the only child of the SurfaceView node.
        if (isHostNode(node)) {
            AccessibilityNodeInfo child = mNodeCopier.copy(node);
            AccessibilityNodeInfo parent = node.getParent();
            while (parent != null && !Utils.isSurfaceView(parent)) {
                child.recycle();
                child = parent;
                parent = child.getParent();
            }
            Utils.recycleNode(parent);
            return child;
        }

        // Get the root node directly via the window.
        AccessibilityWindowInfo window = node.getWindow();
        if (window != null) {
            AccessibilityNodeInfo root = window.getRoot();
            window.recycle();
            if (root != null) {
                return root;
            }
        }

        // If the root node can't be accessed via the window, navigate up the node tree.
        AccessibilityNodeInfo child = mNodeCopier.copy(node);
        AccessibilityNodeInfo parent = node.getParent();
        while (parent != null) {
            child.recycle();
            child = parent;
            parent = child.getParent();
        }
        return child;
    }

    /**
     * Searches {@code root} and its descendants, and returns the currently focused node if it's
     * not a {@link FocusParkingView}, or returns null in other cases. The caller is responsible
     * for recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findFocusedNodeInRoot(@NonNull AccessibilityNodeInfo root) {
        AccessibilityNodeInfo focusedNode = findFocusedNodeInRootInternal(root);
        if (focusedNode != null && Utils.isFocusParkingView(focusedNode)) {
            focusedNode.recycle();
            return null;
        }
        return focusedNode;
    }

    /**
     * Searches {@code root} and its descendants, and returns the currently focused node, if any,
     * or returns null if not found. The caller is responsible for recycling the result.
     */
    @Nullable
    private AccessibilityNodeInfo findFocusedNodeInRootInternal(
            @NonNull AccessibilityNodeInfo root) {
        AccessibilityNodeInfo surfaceView = null;
        if (!isClientNode(root)) {
            AccessibilityNodeInfo focusedNode = root.findFocus(FOCUS_INPUT);
            if (focusedNode != null && Utils.isSurfaceView(focusedNode)) {
                // The focused node represents a SurfaceView. In this case the root node is actually
                // a client node but Navigator doesn't know that because SurfaceViewHelper doesn't
                // know the package name of the client app.
                // Although the package name of the client app will be stored in SurfaceViewHelper
                // when RotaryService handles TYPE_WINDOW_STATE_CHANGED event, RotaryService may not
                // receive the event. For example, RotaryService may have been killed and restarted.
                // In this case, Navigator should store the package name.
                surfaceView = focusedNode;
                addClientApp(surfaceView.getPackageName());
            } else {
                return focusedNode;
            }
        }

        // The root node is in client app, which contains a SurfaceView to display the embedded
        // view hierarchy. In this case only search inside the embedded view hierarchy.
        if (surfaceView == null) {
            surfaceView = findSurfaceViewInRoot(root);
        }
        if (surfaceView == null) {
            L.w("Failed to find SurfaceView in client app " + root);
            return null;
        }
        if (surfaceView.getChildCount() == 0) {
            L.d("Host app is not loaded yet");
            surfaceView.recycle();
            return null;
        }
        AccessibilityNodeInfo embeddedRoot = surfaceView.getChild(0);
        surfaceView.recycle();
        if (embeddedRoot == null) {
            L.w("Failed to get the root of host app");
            return null;
        }
        AccessibilityNodeInfo focusedNode = embeddedRoot.findFocus(FOCUS_INPUT);
        embeddedRoot.recycle();
        return focusedNode;
    }

    /**
     * Searches the window containing {@code node}, and returns the node representing a {@link
     * FocusParkingView}, if any, or returns null if not found. The caller is responsible for
     * recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findFocusParkingView(@NonNull AccessibilityNodeInfo node) {
        AccessibilityNodeInfo root = getRoot(node);
        AccessibilityNodeInfo fpv = findFocusParkingViewInRoot(root);
        root.recycle();
        return fpv;
    }

    /**
     * Searches {@code root} and its descendants, and returns the node representing a {@link
     * FocusParkingView}, if any, or returns null if not found. The caller is responsible for
     * recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findFocusParkingViewInRoot(@NonNull AccessibilityNodeInfo root) {
        return mTreeTraverser.depthFirstSearch(
                root,
                /* skipPredicate= */ Utils::isFocusArea,
                /* targetPredicate= */ Utils::isFocusParkingView
        );
    }

    /**
     * Searches {@code root} and its descendants, and returns the node representing a {@link
     * android.view.SurfaceView}, if any, or returns null if not found. The caller is responsible
     * for recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findSurfaceViewInRoot(@NonNull AccessibilityNodeInfo root) {
        return mTreeTraverser.depthFirstSearch(root, /* targetPredicate= */ Utils::isSurfaceView);
    }

    /**
     * Returns the best target focus area for a nudge in the given {@code direction}. The caller is
     * responsible for recycling the result.
     *
     * @param windows          a list of windows to search from
     * @param sourceNode       the current focus
     * @param currentFocusArea the current focus area
     * @param direction        nudge direction, must be {@link View#FOCUS_UP}, {@link
     *                         View#FOCUS_DOWN}, {@link View#FOCUS_LEFT}, or {@link
     *                         View#FOCUS_RIGHT}
     */
    AccessibilityNodeInfo findNudgeTargetFocusArea(
            @NonNull List<AccessibilityWindowInfo> windows,
            @NonNull AccessibilityNodeInfo sourceNode,
            @NonNull AccessibilityNodeInfo currentFocusArea,
            int direction) {
        AccessibilityWindowInfo currentWindow = sourceNode.getWindow();
        if (currentWindow == null) {
            L.e("Currently focused window is null");
            return null;
        }

        // Build a list of candidate focus areas, starting with all the other focus areas in the
        // same window as the current focus area.
        List<AccessibilityNodeInfo> candidateFocusAreas = findFocusAreas(currentWindow);
        for (AccessibilityNodeInfo focusArea : candidateFocusAreas) {
            if (focusArea.equals(currentFocusArea)) {
                candidateFocusAreas.remove(focusArea);
                focusArea.recycle();
                break;
            }
        }

        // Exclude focus areas that have no descendants to take focus, because once we found a best
        // candidate focus area, we don't dig into other ones. If it has no descendants to take
        // focus, the nudge will fail.
        removeEmptyFocusAreas(candidateFocusAreas);

        if (currentWindow.getType() != TYPE_INPUT_METHOD
                || shouldNudgeOutOfIme(sourceNode, currentFocusArea, candidateFocusAreas,
                           direction)) {
            // Add candidate focus areas in other windows in the given direction.
            List<AccessibilityWindowInfo> candidateWindows = new ArrayList<>();
            boolean isSourceNodeEditable = sourceNode.isEditable();
            addWindowsInDirection(windows, currentWindow, candidateWindows, direction,
                    isSourceNodeEditable);
            currentWindow.recycle();
            for (AccessibilityWindowInfo window : candidateWindows) {
                List<AccessibilityNodeInfo> focusAreasInAnotherWindow = findFocusAreas(window);
                candidateFocusAreas.addAll(focusAreasInAnotherWindow);
            }

            // Exclude focus areas that have no descendants to take focus, because once we found a
            // best candidate focus area, we don't dig into other ones. If it has no descendants to
            // take focus, the nudge will fail.
            removeEmptyFocusAreas(candidateFocusAreas);
        }

        // Choose the best candidate as our target focus area.
        AccessibilityNodeInfo targetFocusArea =
                chooseBestNudgeCandidate(sourceNode, candidateFocusAreas, direction);
        Utils.recycleNodes(candidateFocusAreas);
        return targetFocusArea;
    }

    /**
     * Returns whether it should nudge out the IME window. If the current window is IME window and
     * there are candidate FocusAreas in it for the given direction, it shouldn't nudge out of the
     * IME window.
     */
    private boolean shouldNudgeOutOfIme(@NonNull AccessibilityNodeInfo sourceNode,
            @NonNull AccessibilityNodeInfo currentFocusArea,
            @NonNull List<AccessibilityNodeInfo> focusAreasInCurrentWindow,
            int direction) {
        if (!focusAreasInCurrentWindow.isEmpty()) {
            Rect sourceBounds = Utils.getBoundsInScreen(sourceNode);
            Rect sourceFocusAreaBounds = Utils.getBoundsInScreen(currentFocusArea);
            for (AccessibilityNodeInfo candidate : focusAreasInCurrentWindow) {
                if (isCandidate(sourceBounds, sourceFocusAreaBounds, candidate, direction)) {
                    return false;
                }
            }
        }
        return true;
    }

    private void removeEmptyFocusAreas(@NonNull List<AccessibilityNodeInfo> focusAreas) {
        for (Iterator<AccessibilityNodeInfo> iterator = focusAreas.iterator();
                iterator.hasNext(); ) {
            AccessibilityNodeInfo focusArea = iterator.next();
            if (!Utils.canHaveFocus(focusArea)
                    && !containsWebViewWithFocusableDescendants(focusArea)) {
                iterator.remove();
                focusArea.recycle();
            }
        }
    }

    private boolean containsWebViewWithFocusableDescendants(@NonNull AccessibilityNodeInfo node) {
        List<AccessibilityNodeInfo> webViews = new ArrayList<>();
        mTreeTraverser.depthFirstSelect(node, Utils::isWebView, webViews);
        if (webViews.isEmpty()) {
            return false;
        }
        boolean hasFocusableDescendant = false;
        for (AccessibilityNodeInfo webView : webViews) {
            AccessibilityNodeInfo focusableDescendant = mTreeTraverser.depthFirstSearch(webView,
                    Utils::canPerformFocus);
            if (focusableDescendant != null) {
                hasFocusableDescendant = true;
                focusableDescendant.recycle();
                break;
            }
        }
        Utils.recycleNodes(webViews);
        return hasFocusableDescendant;
    }

    /**
     * Adds all the {@code windows} in the given {@code direction} of the given {@code source}
     * window to the given list if the {@code source} window is not an overlay. If it's an overlay
     * and the source node is editable, adds the IME window only. Otherwise does nothing.
     */
    private void addWindowsInDirection(@NonNull List<AccessibilityWindowInfo> windows,
            @NonNull AccessibilityWindowInfo source,
            @NonNull List<AccessibilityWindowInfo> results,
            int direction,
            boolean isSourceNodeEditable) {
        Rect sourceBounds = new Rect();
        source.getBoundsInScreen(sourceBounds);
        boolean isSourceWindowOverlayWindow = isOverlayWindow(source, sourceBounds);
        Rect destBounds = new Rect();
        for (AccessibilityWindowInfo window : windows) {
            if (window.equals(source)) {
               continue;
            }
            // Nudging out of the overlay window is not allowed unless the source node is editable
            // and the target window is an IME window. E.g., nudging from the EditText in the Dialog
            // to the IME is allowed, while nudging from the Button in the Dialog to the IME is not
            // allowed.
            if (isSourceWindowOverlayWindow
                    && (!isSourceNodeEditable || window.getType() != TYPE_INPUT_METHOD)) {
                continue;
            }

            window.getBoundsInScreen(destBounds);
            // Even if only part of destBounds is in the given direction of sourceBounds, we
            // still include it because that part may contain the target focus area.
            if (FocusFinder.isPartiallyInDirection(sourceBounds, destBounds, direction)) {
                results.add(window);
            }
        }
    }

    /**
     * Returns whether the given {@code window} with the given {@code bounds} is an overlay window.
     * <p>
     * If the source window is an application window on the default display and it's smaller than
       the display, then it's either a TaskView window or an overlay window (such as a Dialog
       window). The ID of a TaskView task is different from the full screen application, while
       the ID of an overlay task is the same with the full screen application, so task ID is used
       to decide whether it's an overlay window.
     */
    private boolean isOverlayWindow(@NonNull AccessibilityWindowInfo window, @NonNull Rect bounds) {
        return window.getType() == TYPE_APPLICATION
                && window.getDisplayId() == Display.DEFAULT_DISPLAY
                && !mAppWindowBounds.equals(bounds)
                && window.getTaskId() == mAppWindowTaskId;
    }

    /**
     * Returns whether nudging to the given {@code direction} can dismiss the given {@code window}
     * with the given {@code bounds}.
     */
    boolean isDismissible(@NonNull AccessibilityWindowInfo window,
            @NonNull Rect bounds,
            @View.FocusRealDirection int direction) {
        // Only overlay windows can be dismissed.
        if (!isOverlayWindow(window, bounds)) {
            return false;
        }
        // The window can be dismissed when part of the underlying window is not covered by it in
        // the given direction.
        switch (direction) {
            case FOCUS_UP:
                return mAppWindowBounds.top < bounds.top;
            case FOCUS_DOWN:
                return mAppWindowBounds.bottom > bounds.bottom;
            case FOCUS_LEFT:
                return mAppWindowBounds.left < bounds.left;
            case FOCUS_RIGHT:
                return mAppWindowBounds.right > bounds.right;
        }
        return false;
    }

    /**
     * Scans the view hierarchy of the given {@code window} looking for focus areas and returns
     * them. If there are no explicitly declared {@link FocusArea}s, returns the root view. The
     * caller is responsible for recycling the result.
     */
    @NonNull
    @VisibleForTesting
    List<AccessibilityNodeInfo> findFocusAreas(@NonNull AccessibilityWindowInfo window) {
        List<AccessibilityNodeInfo> results = new ArrayList<>();
        AccessibilityNodeInfo rootNode = window.getRoot();
        if (rootNode != null) {
            // If the root node is in the client app therefore contains a SurfaceView, skip the view
            // hierarchy of the client app, and scan the view hierarchy of the host app, which is
            // embedded in the SurfaceView.
            if (isClientNode(rootNode)) {
                AccessibilityNodeInfo hostRoot = getDescendantHostRoot(rootNode);
                rootNode.recycle();
                rootNode = hostRoot;
            }

            addFocusAreas(rootNode, results);
            if (results.isEmpty()) {
                results.add(copyNode(rootNode));
            }
            rootNode.recycle();
        }
        return results;
    }

    /**
     * Searches from {@code clientNode}, and returns the root of the embedded view hierarchy if any,
     * or returns null if not found. The caller is responsible for recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo getDescendantHostRoot(@NonNull AccessibilityNodeInfo clientNode) {
        return mTreeTraverser.depthFirstSearch(clientNode, this::isHostNode);
    }

    /**
     * Returns whether the given window is the Heads-up Notification (HUN) window. The HUN window
     * is identified by the left and right edges. The top and bottom vary depending on whether the
     * HUN appears at the top or bottom of the screen and on the height of the notification being
     * displayed so they aren't used.
     */
    boolean isHunWindow(@Nullable AccessibilityWindowInfo window) {
        if (window == null || window.getType() != AccessibilityWindowInfo.TYPE_SYSTEM) {
            return false;
        }
        Rect bounds = new Rect();
        window.getBoundsInScreen(bounds);
        return bounds.left == mHunLeft && bounds.right == mHunRight;
    }

    /**
     * Returns whether the {@code window} is the main application window. A main application
     * window is an application window on the default display that takes up the entire display.
     */
    boolean isMainApplicationWindow(@NonNull AccessibilityWindowInfo window) {
        Rect windowBounds = new Rect();
        window.getBoundsInScreen(windowBounds);
        return window.getType() == TYPE_APPLICATION
                && window.getDisplayId() == Display.DEFAULT_DISPLAY
                && mAppWindowBounds.equals(windowBounds);
    }

    /**
     * Searches from the given node up through its ancestors to the containing focus area, looking
     * for a node that's marked as horizontally or vertically scrollable. Returns a copy of the
     * first such node or null if none is found. The caller is responsible for recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findScrollableContainer(@NonNull AccessibilityNodeInfo node) {
        return mTreeTraverser.findNodeOrAncestor(node, /* stopPredicate= */ Utils::isFocusArea,
                /* targetPredicate= */ Utils::isScrollableContainer);
    }

    /**
     * Returns the previous node  before {@code referenceNode} in Tab order that can take focus or
     * the next node after {@code referenceNode} in Tab order that can take focus, depending on
     * {@code direction}. The search is limited to descendants of {@code containerNode}. Returns
     * null if there are no descendants that can take focus in the given direction. The caller is
     * responsible for recycling the result.
     *
     * @param containerNode the node with descendants
     * @param referenceNode a descendant of {@code containerNode} to start from
     * @param direction     {@link View#FOCUS_FORWARD} or {@link View#FOCUS_BACKWARD}
     * @return the node before or after {@code referenceNode} or null if none
     */
    @Nullable
    AccessibilityNodeInfo findFocusableDescendantInDirection(
            @NonNull AccessibilityNodeInfo containerNode,
            @NonNull AccessibilityNodeInfo referenceNode,
            int direction) {
        AccessibilityNodeInfo targetNode = copyNode(referenceNode);
        do {
            AccessibilityNodeInfo nextTargetNode = targetNode.focusSearch(direction);
            if (nextTargetNode == null
                    || nextTargetNode.equals(containerNode)
                    || !Utils.isDescendant(containerNode, nextTargetNode)) {
                Utils.recycleNode(nextTargetNode);
                Utils.recycleNode(targetNode);
                return null;
            }
            if (nextTargetNode.equals(referenceNode) || nextTargetNode.equals(targetNode)) {
                L.w((direction == View.FOCUS_FORWARD ? "Next" : "Previous")
                        + " node is the same node: " + referenceNode);
                Utils.recycleNode(nextTargetNode);
                Utils.recycleNode(targetNode);
                return null;
            }
            targetNode.recycle();
            targetNode = nextTargetNode;
        } while (!Utils.canTakeFocus(targetNode));
        return targetNode;
    }

    /**
     * Returns the first descendant of {@code node} which can take focus. The nodes are searched in
     * in depth-first order, not including {@code node} itself. If no descendant can take focus,
     * null is returned. The caller is responsible for recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findFirstFocusableDescendant(@NonNull AccessibilityNodeInfo node) {
        return mTreeTraverser.depthFirstSearch(node,
                candidateNode -> candidateNode != node && Utils.canTakeFocus(candidateNode));
    }

    /**
     * Returns the last descendant of {@code node} which can take focus. The nodes are searched in
     * reverse depth-first order, not including {@code node} itself. If no descendant can take
     * focus, null is returned. The caller is responsible for recycling the result.
     */
    @Nullable
    AccessibilityNodeInfo findLastFocusableDescendant(@NonNull AccessibilityNodeInfo node) {
        return mTreeTraverser.reverseDepthFirstSearch(node,
                candidateNode -> candidateNode != node && Utils.canTakeFocus(candidateNode));
    }

    /**
     * Scans descendants of the given {@code rootNode} looking for focus areas and adds them to the
     * given list. It doesn't scan inside focus areas since nested focus areas aren't allowed. The
     * caller is responsible for recycling added nodes.
     *
     * @param rootNode the root to start scanning from
     * @param results  a list of focus areas to add to
     */
    private void addFocusAreas(@NonNull AccessibilityNodeInfo rootNode,
            @NonNull List<AccessibilityNodeInfo> results) {
        mTreeTraverser.depthFirstSelect(rootNode, Utils::isFocusArea, results);
    }

    /**
     * Returns a copy of the best candidate from among the given {@code candidates} for a nudge
     * from {@code sourceNode} in the given {@code direction}. Returns null if none of the {@code
     * candidates} are in the given {@code direction}. The caller is responsible for recycling the
     * result.
     *
     * @param candidates could be a list of {@link FocusArea}s, or a list of focusable views
     */
    @Nullable
    private AccessibilityNodeInfo chooseBestNudgeCandidate(
            @NonNull AccessibilityNodeInfo sourceNode,
            @NonNull List<AccessibilityNodeInfo> candidates,
            int direction) {
        if (candidates.isEmpty()) {
            return null;
        }
        Rect sourceBounds = Utils.getBoundsInScreen(sourceNode);
        AccessibilityNodeInfo sourceFocusArea = getAncestorFocusArea(sourceNode);
        Rect sourceFocusAreaBounds = Utils.getBoundsInScreen(sourceFocusArea);
        sourceFocusArea.recycle();
        AccessibilityNodeInfo bestNode = null;
        Rect bestBounds = new Rect();

        for (AccessibilityNodeInfo candidate : candidates) {
            if (isCandidate(sourceBounds, sourceFocusAreaBounds, candidate, direction)) {
                Rect candidateBounds = Utils.getBoundsInScreen(candidate);
                if (bestNode == null || FocusFinder.isBetterCandidate(
                        direction, sourceBounds, candidateBounds, bestBounds)) {
                    bestNode = candidate;
                    bestBounds.set(candidateBounds);
                }
            }
        }
        return copyNode(bestNode);
    }

    /**
     * Returns whether the given {@code node} is a candidate from {@code sourceBounds} to the given
     * {@code direction}.
     * <p>
     * To be a candidate, the node
     * <ul>
     *     <li>must be considered a candidate by {@link FocusFinder#isCandidate} if it represents a
     *         focusable view within a focus area
     *     <li>must be in the {@code direction} of the {@code sourceFocusAreaBounds} and one of its
     *         focusable descendants must be a candidate if it represents a focus area
     * </ul>
     */
    private boolean isCandidate(@NonNull Rect sourceBounds,
            @NonNull Rect sourceFocusAreaBounds,
            @NonNull AccessibilityNodeInfo node,
            int direction) {
        AccessibilityNodeInfo candidate = mTreeTraverser.depthFirstSearch(node,
                /* skipPredicate= */ candidateNode -> {
                    if (Utils.canTakeFocus(candidateNode)) {
                        return false;
                    }
                    // If a node can't take focus, it represents a focus area. If the focus area
                    // doesn't intersect with sourceFocusAreaBounds, and it's not in the given
                    // direction of sourceFocusAreaBounds, it's not a candidate, so we should return
                    // true to stop searching.
                    Rect candidateBounds = Utils.getBoundsInScreen(candidateNode);
                    return !Rect.intersects(candidateBounds,sourceFocusAreaBounds)
                            && !FocusFinder.isInDirection(
                                sourceFocusAreaBounds, candidateBounds, direction);
                },
                /* targetPredicate= */ candidateNode -> {
                    // RotaryService can navigate to nodes in a WebView even when off-screen so we
                    // use canPerformFocus() to skip the bounds check.
                    if (isInWebView(candidateNode)) {
                        return Utils.canPerformFocus(candidateNode);
                    }
                    // If a node isn't visible to the user, e.g. another window is obscuring it,
                    // skip it.
                    if (!candidateNode.isVisibleToUser()) {
                        return false;
                    }
                    // If a node can't take focus, it represents a focus area, so we return false to
                    // skip the node and let it search its descendants.
                    if (!Utils.canTakeFocus(candidateNode)) {
                        return false;
                    }
                    // The node represents a focusable view in a focus area, so check the geometry.
                    Rect candidateBounds = Utils.getBoundsInScreen(candidateNode);
                    return FocusFinder.isCandidate(sourceBounds, candidateBounds, direction);
                });
        if (candidate == null) {
            return false;
        }
        candidate.recycle();
        return true;
    }

    private AccessibilityNodeInfo copyNode(@Nullable AccessibilityNodeInfo node) {
        return mNodeCopier.copy(node);
    }

    /**
     * Returns the closest ancestor focus area of the given {@code node}.
     * <ul>
     *     <li> If the given {@code node} is a {@link FocusArea} node or a descendant of a {@link
     *          FocusArea} node, returns the {@link FocusArea} node.
     *     <li> If there are no explicitly declared {@link FocusArea}s among the ancestors of this
     *          view, and this view is not in an embedded view hierarchy, returns the root node.
     *     <li> If there are no explicitly declared {@link FocusArea}s among the ancestors of this
     *          view, and this view is in an embedded view hierarchy, returns the root node of
     *          embedded view hierarchy.
     * </ul>
     * The caller is responsible for recycling the result.
     */
    @NonNull
    AccessibilityNodeInfo getAncestorFocusArea(@NonNull AccessibilityNodeInfo node) {
        Predicate<AccessibilityNodeInfo> isFocusAreaOrRoot = candidateNode -> {
            if (Utils.isFocusArea(candidateNode)) {
                // The candidateNode is a focus area.
                return true;
            }
            AccessibilityNodeInfo parent = candidateNode.getParent();
            if (parent == null) {
                // The candidateNode is the root node.
                return true;
            }
            if (Utils.isSurfaceView(parent)) {
                // Treat the root of embedded view hierarchy (i.e., the only child of the
                // SurfaceView) as an implicit focus area.
                return true;
            }
            parent.recycle();
            return false;
        };
        AccessibilityNodeInfo result = mTreeTraverser.findNodeOrAncestor(node, isFocusAreaOrRoot);
        if (result == null || !Utils.isFocusArea(result)) {
            L.w("Couldn't find ancestor focus area for given node: " + node);
        }
        return result;
    }

    /**
     * Returns a copy of {@code node} or the nearest ancestor that represents a {@code WebView}.
     * Returns null if {@code node} isn't a {@code WebView} and isn't a descendant of a {@code
     * WebView}.
     */
    @Nullable
    private AccessibilityNodeInfo findWebViewAncestor(@NonNull AccessibilityNodeInfo node) {
        return mTreeTraverser.findNodeOrAncestor(node, Utils::isWebView);
    }

    /** Returns whether {@code node} is a {@code WebView} or is a descendant of one. */
    boolean isInWebView(@NonNull AccessibilityNodeInfo node) {
        AccessibilityNodeInfo webView = findWebViewAncestor(node);
        if (webView == null) {
            return false;
        }
        webView.recycle();
        return true;
    }

    /**
     * Returns the next focusable node after {@code candidate} in {@code direction} in {@code
     * webView} or null if none. This handles navigating into a WebView as well as within a WebView.
     */
    @Nullable
    private AccessibilityNodeInfo findNextFocusableInWebView(@NonNull AccessibilityNodeInfo webView,
            @NonNull AccessibilityNodeInfo candidate, int direction) {
        // focusSearch() doesn't work in WebViews so use tree traversal instead.
        if (Utils.isWebView(candidate)) {
            if (direction == View.FOCUS_FORWARD) {
                // When entering into a WebView, find the first focusable node within the
                // WebView if any.
                return findFirstFocusableDescendantInWebView(candidate);
            } else {
                // When backing into a WebView, find the last focusable node within the
                // WebView if any.
                return findLastFocusableDescendantInWebView(candidate);
            }
        } else {
            // When navigating within a WebView, find the next or previous focusable node in
            // depth-first order.
            if (direction == View.FOCUS_FORWARD) {
                return findFirstFocusDescendantInWebViewAfter(webView, candidate);
            } else {
                return findFirstFocusDescendantInWebViewBefore(webView, candidate);
            }
        }
    }

    /**
     * Returns the first descendant of {@code webView} which can perform focus. This includes off-
     * screen descendants. The nodes are searched in in depth-first order, not including
     * {@code webView} itself. If no descendant can perform focus, null is returned. The caller is
     * responsible for recycling the result.
     */
    @Nullable
    private AccessibilityNodeInfo findFirstFocusableDescendantInWebView(
            @NonNull AccessibilityNodeInfo webView) {
        return mTreeTraverser.depthFirstSearch(webView,
                candidateNode -> candidateNode != webView && Utils.canPerformFocus(candidateNode));
    }

    /**
     * Returns the last descendant of {@code webView} which can perform focus. This includes off-
     * screen descendants. The nodes are searched in reverse depth-first order, not including
     * {@code webView} itself. If no descendant can perform focus, null is returned. The caller is
     * responsible for recycling the result.
     */
    @Nullable
    private AccessibilityNodeInfo findLastFocusableDescendantInWebView(
            @NonNull AccessibilityNodeInfo webView) {
        return mTreeTraverser.reverseDepthFirstSearch(webView,
                candidateNode -> candidateNode != webView && Utils.canPerformFocus(candidateNode));
    }

    @Nullable
    private AccessibilityNodeInfo findFirstFocusDescendantInWebViewBefore(
            @NonNull AccessibilityNodeInfo webView, @NonNull AccessibilityNodeInfo beforeNode) {
        boolean[] foundBeforeNode = new boolean[1];
        return mTreeTraverser.reverseDepthFirstSearch(webView,
                node -> {
                    if (foundBeforeNode[0] && Utils.canPerformFocus(node)) {
                        return true;
                    }
                    if (node.equals(beforeNode)) {
                        foundBeforeNode[0] = true;
                    }
                    return false;
                });
    }

    @Nullable
    private AccessibilityNodeInfo findFirstFocusDescendantInWebViewAfter(
            @NonNull AccessibilityNodeInfo webView, @NonNull AccessibilityNodeInfo afterNode) {
        boolean[] foundAfterNode = new boolean[1];
        return mTreeTraverser.depthFirstSearch(webView,
                node -> {
                    if (foundAfterNode[0] && Utils.canPerformFocus(node)) {
                        return true;
                    }
                    if (node.equals(afterNode)) {
                        foundAfterNode[0] = true;
                    }
                    return false;
                });
    }

    @ExcludeFromCodeCoverageGeneratedReport(reason = DUMP_INFO)
    void dump(@NonNull DualDumpOutputStream dumpOutputStream, boolean dumpAsProto,
            @NonNull String fieldName, long fieldId) {
        long fieldToken = dumpOutputStream.start(fieldName, fieldId);
        dumpOutputStream.write("hunLeft", RotaryProtos.Navigator.HUN_LEFT, mHunLeft);
        dumpOutputStream.write("hunRight", RotaryProtos.Navigator.HUN_RIGHT, mHunRight);
        DumpUtils.writeFocusDirection(dumpOutputStream, dumpAsProto, "hunNudgeDirection",
                RotaryProtos.Navigator.HUN_NUDGE_DIRECTION, mHunNudgeDirection);
        DumpUtils.writeRect(dumpOutputStream, mAppWindowBounds, "appWindowBounds",
                RotaryProtos.Navigator.APP_WINDOW_BOUNDS);
        mSurfaceViewHelper.dump(dumpOutputStream, dumpAsProto, "surfaceViewHelper",
                RotaryProtos.Navigator.SURFACE_VIEW_HELPER);
        dumpOutputStream.end(fieldToken);
    }

    @ExcludeFromCodeCoverageGeneratedReport(reason = BOILERPLATE_CODE)
    static String directionToString(@View.FocusRealDirection int direction) {
        switch (direction) {
            case FOCUS_UP:
                return "FOCUS_UP";
            case FOCUS_DOWN:
                return "FOCUS_DOWN";
            case FOCUS_LEFT:
                return "FOCUS_LEFT";
            case FOCUS_RIGHT:
                return "FOCUS_RIGHT";
            default:
                return "<unknown direction " + direction + ">";
        }
    }

    /** Result from {@link #findRotateTarget}. */
    static class FindRotateTargetResult {
        @NonNull final AccessibilityNodeInfo node;
        final int advancedCount;

        FindRotateTargetResult(@NonNull AccessibilityNodeInfo node, int advancedCount) {
            this.node = node;
            this.advancedCount = advancedCount;
        }
    }
}