/*
 * Copyright (C) 2012 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 android.view;

import static android.view.accessibility.AccessibilityNodeInfo.ACTION_ARGUMENT_ACCESSIBLE_CLICKABLE_SPAN;
import static android.view.accessibility.AccessibilityNodeInfo.EXTRA_DATA_REQUESTED_KEY;
import static android.view.accessibility.AccessibilityNodeInfo.EXTRA_DATA_TEXT_CHARACTER_LOCATION_KEY;

import android.graphics.Point;
import android.graphics.Rect;
import android.graphics.RectF;
import android.graphics.Region;
import android.os.Binder;
import android.os.Bundle;
import android.os.Handler;
import android.os.Looper;
import android.os.Message;
import android.os.Parcelable;
import android.os.Process;
import android.os.RemoteException;
import android.os.SystemClock;
import android.text.style.AccessibilityClickableSpan;
import android.text.style.ClickableSpan;
import android.util.LongSparseArray;
import android.util.Slog;
import android.view.View.AttachInfo;
import android.view.accessibility.AccessibilityInteractionClient;
import android.view.accessibility.AccessibilityManager;
import android.view.accessibility.AccessibilityNodeInfo;
import android.view.accessibility.AccessibilityNodeInfo.AccessibilityAction;
import android.view.accessibility.AccessibilityNodeProvider;
import android.view.accessibility.AccessibilityRequestPreparer;
import android.view.accessibility.IAccessibilityInteractionConnectionCallback;

import com.android.internal.R;
import com.android.internal.annotations.GuardedBy;
import com.android.internal.annotations.VisibleForTesting;
import com.android.internal.os.SomeArgs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.function.Predicate;

/**
 * Class for managing accessibility interactions initiated from the system
 * and targeting the view hierarchy. A *ClientThread method is to be
 * called from the interaction connection ViewAncestor gives the system to
 * talk to it and a corresponding *UiThread method that is executed on the
 * UI thread.
 *
 * @hide
 */
@VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
public final class AccessibilityInteractionController {

    private static final String LOG_TAG = "AccessibilityInteractionController";

    // Debugging flag
    private static final boolean ENFORCE_NODE_TREE_CONSISTENT = false;

    // Constants for readability
    private static final boolean IGNORE_REQUEST_PREPARERS = true;
    private static final boolean CONSIDER_REQUEST_PREPARERS = false;

    // If an app holds off accessibility for longer than this, the hold-off is canceled to prevent
    // accessibility from hanging
    private static final long REQUEST_PREPARER_TIMEOUT_MS = 500;

    private final ArrayList<AccessibilityNodeInfo> mTempAccessibilityNodeInfoList =
        new ArrayList<AccessibilityNodeInfo>();

    private final Object mLock = new Object();

    private final PrivateHandler mHandler;

    private final ViewRootImpl mViewRootImpl;

    private final AccessibilityNodePrefetcher mPrefetcher;

    private final long mMyLooperThreadId;

    private final int mMyProcessId;

    private final AccessibilityManager mA11yManager;

    private final ArrayList<View> mTempArrayList = new ArrayList<View>();

    private final Point mTempPoint = new Point();
    private final Rect mTempRect = new Rect();
    private final Rect mTempRect1 = new Rect();
    private final Rect mTempRect2 = new Rect();

    private AddNodeInfosForViewId mAddNodeInfosForViewId;

    @GuardedBy("mLock")
    private int mNumActiveRequestPreparers;
    @GuardedBy("mLock")
    private List<MessageHolder> mMessagesWaitingForRequestPreparer;
    @GuardedBy("mLock")
    private int mActiveRequestPreparerId;

    public AccessibilityInteractionController(ViewRootImpl viewRootImpl) {
        Looper looper =  viewRootImpl.mHandler.getLooper();
        mMyLooperThreadId = looper.getThread().getId();
        mMyProcessId = Process.myPid();
        mHandler = new PrivateHandler(looper);
        mViewRootImpl = viewRootImpl;
        mPrefetcher = new AccessibilityNodePrefetcher();
        mA11yManager = mViewRootImpl.mContext.getSystemService(AccessibilityManager.class);
    }

    private void scheduleMessage(Message message, int interrogatingPid, long interrogatingTid,
            boolean ignoreRequestPreparers) {
        if (ignoreRequestPreparers
                || !holdOffMessageIfNeeded(message, interrogatingPid, interrogatingTid)) {
            // If the interrogation is performed by the same thread as the main UI
            // thread in this process, set the message as a static reference so
            // after this call completes the same thread but in the interrogating
            // client can handle the message to generate the result.
            if (interrogatingPid == mMyProcessId && interrogatingTid == mMyLooperThreadId
                    && mHandler.hasAccessibilityCallback(message)) {
                AccessibilityInteractionClient.getInstanceForThread(
                        interrogatingTid).setSameThreadMessage(message);
            } else {
                // For messages without callback of interrogating client, just handle the
                // message immediately if this is UI thread.
                if (!mHandler.hasAccessibilityCallback(message)
                        && Thread.currentThread().getId() == mMyLooperThreadId) {
                    mHandler.handleMessage(message);
                } else {
                    mHandler.sendMessage(message);
                }
            }
        }
    }

    private boolean isShown(View view) {
        // The first two checks are made also made by isShown() which
        // however traverses the tree up to the parent to catch that.
        // Therefore, we do some fail fast check to minimize the up
        // tree traversal.
        return (view.mAttachInfo != null
                && view.mAttachInfo.mWindowVisibility == View.VISIBLE
                && view.isShown());
    }

    public void findAccessibilityNodeInfoByAccessibilityIdClientThread(
            long accessibilityNodeId, Region interactiveRegion, int interactionId,
            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
            long interrogatingTid, MagnificationSpec spec, Bundle arguments) {
        final Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID;
        message.arg1 = flags;

        final SomeArgs args = SomeArgs.obtain();
        args.argi1 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
        args.argi2 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
        args.argi3 = interactionId;
        args.arg1 = callback;
        args.arg2 = spec;
        args.arg3 = interactiveRegion;
        args.arg4 = arguments;
        message.obj = args;

        scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
    }

    /**
     * Check if this message needs to be held off while the app prepares to meet either this
     * request, or a request ahead of it.
     *
     * @param originalMessage The message to be processed
     * @param callingPid The calling process id
     * @param callingTid The calling thread id
     *
     * @return {@code true} if the message is held off and will be processed later, {@code false} if
     *         the message should be posted.
     */
    private boolean holdOffMessageIfNeeded(
            Message originalMessage, int callingPid, long callingTid) {
        synchronized (mLock) {
            // If a request is already pending, queue this request for when it's finished
            if (mNumActiveRequestPreparers != 0) {
                queueMessageToHandleOncePrepared(originalMessage, callingPid, callingTid);
                return true;
            }

            // Currently the only message that can hold things off is findByA11yId with extra data.
            if (originalMessage.what
                    != PrivateHandler.MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID) {
                return false;
            }
            SomeArgs originalMessageArgs = (SomeArgs) originalMessage.obj;
            Bundle requestArguments = (Bundle) originalMessageArgs.arg4;
            if (requestArguments == null) {
                return false;
            }

            // If nothing it registered for this view, nothing to do
            int accessibilityViewId = originalMessageArgs.argi1;
            final List<AccessibilityRequestPreparer> preparers =
                    mA11yManager.getRequestPreparersForAccessibilityId(accessibilityViewId);
            if (preparers == null) {
                return false;
            }

            // If the bundle doesn't request the extra data, nothing to do
            final String extraDataKey = requestArguments.getString(EXTRA_DATA_REQUESTED_KEY);
            if (extraDataKey == null) {
                return false;
            }

            // Send the request to the AccessibilityRequestPreparers on the UI thread
            mNumActiveRequestPreparers = preparers.size();
            for (int i = 0; i < preparers.size(); i++) {
                final Message requestPreparerMessage = mHandler.obtainMessage(
                        PrivateHandler.MSG_PREPARE_FOR_EXTRA_DATA_REQUEST);
                final SomeArgs requestPreparerArgs = SomeArgs.obtain();
                // virtualDescendentId
                requestPreparerArgs.argi1 =
                        (originalMessageArgs.argi2 == AccessibilityNodeInfo.UNDEFINED_ITEM_ID)
                        ? AccessibilityNodeProvider.HOST_VIEW_ID : originalMessageArgs.argi2;
                requestPreparerArgs.arg1 = preparers.get(i);
                requestPreparerArgs.arg2 = extraDataKey;
                requestPreparerArgs.arg3 = requestArguments;
                Message preparationFinishedMessage = mHandler.obtainMessage(
                        PrivateHandler.MSG_APP_PREPARATION_FINISHED);
                preparationFinishedMessage.arg1 = ++mActiveRequestPreparerId;
                requestPreparerArgs.arg4 = preparationFinishedMessage;

                requestPreparerMessage.obj = requestPreparerArgs;
                scheduleMessage(requestPreparerMessage, callingPid, callingTid,
                        IGNORE_REQUEST_PREPARERS);
                mHandler.obtainMessage(PrivateHandler.MSG_APP_PREPARATION_TIMEOUT);
                mHandler.sendEmptyMessageDelayed(PrivateHandler.MSG_APP_PREPARATION_TIMEOUT,
                        REQUEST_PREPARER_TIMEOUT_MS);
            }

            // Set the initial request aside
            queueMessageToHandleOncePrepared(originalMessage, callingPid, callingTid);
            return true;
        }
    }

    private void prepareForExtraDataRequestUiThread(Message message) {
        SomeArgs args = (SomeArgs) message.obj;
        final int virtualDescendantId = args.argi1;
        final AccessibilityRequestPreparer preparer = (AccessibilityRequestPreparer) args.arg1;
        final String extraDataKey = (String) args.arg2;
        final Bundle requestArguments = (Bundle) args.arg3;
        final Message preparationFinishedMessage = (Message) args.arg4;

        preparer.onPrepareExtraData(virtualDescendantId, extraDataKey,
                requestArguments, preparationFinishedMessage);
    }

    private void queueMessageToHandleOncePrepared(Message message, int interrogatingPid,
            long interrogatingTid) {
        if (mMessagesWaitingForRequestPreparer == null) {
            mMessagesWaitingForRequestPreparer = new ArrayList<>(1);
        }
        MessageHolder messageHolder =
                new MessageHolder(message, interrogatingPid, interrogatingTid);
        mMessagesWaitingForRequestPreparer.add(messageHolder);
    }

    private void requestPreparerDoneUiThread(Message message) {
        synchronized (mLock) {
            if (message.arg1 != mActiveRequestPreparerId) {
                Slog.e(LOG_TAG, "Surprising AccessibilityRequestPreparer callback (likely late)");
                return;
            }
            mNumActiveRequestPreparers--;
            if (mNumActiveRequestPreparers <= 0) {
                mHandler.removeMessages(PrivateHandler.MSG_APP_PREPARATION_TIMEOUT);
                scheduleAllMessagesWaitingForRequestPreparerLocked();
            }
        }
    }

    private void requestPreparerTimeoutUiThread() {
        synchronized (mLock) {
            Slog.e(LOG_TAG, "AccessibilityRequestPreparer timed out");
            scheduleAllMessagesWaitingForRequestPreparerLocked();
        }
    }

    @GuardedBy("mLock")
    private void scheduleAllMessagesWaitingForRequestPreparerLocked() {
        int numMessages = mMessagesWaitingForRequestPreparer.size();
        for (int i = 0; i < numMessages; i++) {
            MessageHolder request = mMessagesWaitingForRequestPreparer.get(i);
            scheduleMessage(request.mMessage, request.mInterrogatingPid,
                    request.mInterrogatingTid,
                    (i == 0) /* the app is ready for the first request */);
        }
        mMessagesWaitingForRequestPreparer.clear();
        mNumActiveRequestPreparers = 0; // Just to be safe - should be unnecessary
        mActiveRequestPreparerId = -1;
    }

    private void findAccessibilityNodeInfoByAccessibilityIdUiThread(Message message) {
        final int flags = message.arg1;

        SomeArgs args = (SomeArgs) message.obj;
        final int accessibilityViewId = args.argi1;
        final int virtualDescendantId = args.argi2;
        final int interactionId = args.argi3;
        final IAccessibilityInteractionConnectionCallback callback =
            (IAccessibilityInteractionConnectionCallback) args.arg1;
        final MagnificationSpec spec = (MagnificationSpec) args.arg2;
        final Region interactiveRegion = (Region) args.arg3;
        final Bundle arguments = (Bundle) args.arg4;

        args.recycle();

        List<AccessibilityNodeInfo> infos = mTempAccessibilityNodeInfoList;
        infos.clear();
        try {
            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
                return;
            }
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
            View root = null;
            if (accessibilityViewId == AccessibilityNodeInfo.ROOT_ITEM_ID) {
                root = mViewRootImpl.mView;
            } else {
                root = findViewByAccessibilityId(accessibilityViewId);
            }
            if (root != null && isShown(root)) {
                mPrefetcher.prefetchAccessibilityNodeInfos(
                        root, virtualDescendantId, flags, infos, arguments);
            }
        } finally {
            updateInfosForViewportAndReturnFindNodeResult(
                    infos, callback, interactionId, spec, interactiveRegion);
        }
    }

    public void findAccessibilityNodeInfosByViewIdClientThread(long accessibilityNodeId,
            String viewId, Region interactiveRegion, int interactionId,
            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
            long interrogatingTid, MagnificationSpec spec) {
        Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_FIND_ACCESSIBILITY_NODE_INFOS_BY_VIEW_ID;
        message.arg1 = flags;
        message.arg2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);

        SomeArgs args = SomeArgs.obtain();
        args.argi1 = interactionId;
        args.arg1 = callback;
        args.arg2 = spec;
        args.arg3 = viewId;
        args.arg4 = interactiveRegion;
        message.obj = args;

        scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
    }

    private void findAccessibilityNodeInfosByViewIdUiThread(Message message) {
        final int flags = message.arg1;
        final int accessibilityViewId = message.arg2;

        SomeArgs args = (SomeArgs) message.obj;
        final int interactionId = args.argi1;
        final IAccessibilityInteractionConnectionCallback callback =
            (IAccessibilityInteractionConnectionCallback) args.arg1;
        final MagnificationSpec spec = (MagnificationSpec) args.arg2;
        final String viewId = (String) args.arg3;
        final Region interactiveRegion = (Region) args.arg4;
        args.recycle();

        final List<AccessibilityNodeInfo> infos = mTempAccessibilityNodeInfoList;
        infos.clear();
        try {
            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
                return;
            }
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
            View root = null;
            if (accessibilityViewId != AccessibilityNodeInfo.ROOT_ITEM_ID) {
                root = findViewByAccessibilityId(accessibilityViewId);
            } else {
                root = mViewRootImpl.mView;
            }
            if (root != null) {
                final int resolvedViewId = root.getContext().getResources()
                        .getIdentifier(viewId, null, null);
                if (resolvedViewId <= 0) {
                    return;
                }
                if (mAddNodeInfosForViewId == null) {
                    mAddNodeInfosForViewId = new AddNodeInfosForViewId();
                }
                mAddNodeInfosForViewId.init(resolvedViewId, infos);
                root.findViewByPredicate(mAddNodeInfosForViewId);
                mAddNodeInfosForViewId.reset();
            }
        } finally {
            updateInfosForViewportAndReturnFindNodeResult(
                    infos, callback, interactionId, spec, interactiveRegion);
        }
    }

    public void findAccessibilityNodeInfosByTextClientThread(long accessibilityNodeId,
            String text, Region interactiveRegion, int interactionId,
            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
            long interrogatingTid, MagnificationSpec spec) {
        Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_TEXT;
        message.arg1 = flags;

        SomeArgs args = SomeArgs.obtain();
        args.arg1 = text;
        args.arg2 = callback;
        args.arg3 = spec;
        args.argi1 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
        args.argi2 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
        args.argi3 = interactionId;
        args.arg4 = interactiveRegion;
        message.obj = args;

        scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
    }

    private void findAccessibilityNodeInfosByTextUiThread(Message message) {
        final int flags = message.arg1;

        SomeArgs args = (SomeArgs) message.obj;
        final String text = (String) args.arg1;
        final IAccessibilityInteractionConnectionCallback callback =
            (IAccessibilityInteractionConnectionCallback) args.arg2;
        final MagnificationSpec spec = (MagnificationSpec) args.arg3;
        final int accessibilityViewId = args.argi1;
        final int virtualDescendantId = args.argi2;
        final int interactionId = args.argi3;
        final Region interactiveRegion = (Region) args.arg4;
        args.recycle();

        List<AccessibilityNodeInfo> infos = null;
        try {
            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
                return;
            }
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
            View root = null;
            if (accessibilityViewId != AccessibilityNodeInfo.ROOT_ITEM_ID) {
                root = findViewByAccessibilityId(accessibilityViewId);
            } else {
                root = mViewRootImpl.mView;
            }
            if (root != null && isShown(root)) {
                AccessibilityNodeProvider provider = root.getAccessibilityNodeProvider();
                if (provider != null) {
                    infos = provider.findAccessibilityNodeInfosByText(text,
                            virtualDescendantId);
                } else if (virtualDescendantId == AccessibilityNodeProvider.HOST_VIEW_ID) {
                    ArrayList<View> foundViews = mTempArrayList;
                    foundViews.clear();
                    root.findViewsWithText(foundViews, text, View.FIND_VIEWS_WITH_TEXT
                            | View.FIND_VIEWS_WITH_CONTENT_DESCRIPTION
                            | View.FIND_VIEWS_WITH_ACCESSIBILITY_NODE_PROVIDERS);
                    if (!foundViews.isEmpty()) {
                        infos = mTempAccessibilityNodeInfoList;
                        infos.clear();
                        final int viewCount = foundViews.size();
                        for (int i = 0; i < viewCount; i++) {
                            View foundView = foundViews.get(i);
                            if (isShown(foundView)) {
                                provider = foundView.getAccessibilityNodeProvider();
                                if (provider != null) {
                                    List<AccessibilityNodeInfo> infosFromProvider =
                                        provider.findAccessibilityNodeInfosByText(text,
                                                AccessibilityNodeProvider.HOST_VIEW_ID);
                                    if (infosFromProvider != null) {
                                        infos.addAll(infosFromProvider);
                                    }
                                } else  {
                                    infos.add(foundView.createAccessibilityNodeInfo());
                                }
                            }
                        }
                    }
                }
            }
        } finally {
            updateInfosForViewportAndReturnFindNodeResult(
                    infos, callback, interactionId, spec, interactiveRegion);
        }
    }

    public void findFocusClientThread(long accessibilityNodeId, int focusType,
            Region interactiveRegion, int interactionId,
            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
            long interrogatingTid, MagnificationSpec spec) {
        Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_FIND_FOCUS;
        message.arg1 = flags;
        message.arg2 = focusType;

        SomeArgs args = SomeArgs.obtain();
        args.argi1 = interactionId;
        args.argi2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
        args.argi3 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
        args.arg1 = callback;
        args.arg2 = spec;
        args.arg3 = interactiveRegion;

        message.obj = args;

        scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
    }

    private void findFocusUiThread(Message message) {
        final int flags = message.arg1;
        final int focusType = message.arg2;

        SomeArgs args = (SomeArgs) message.obj;
        final int interactionId = args.argi1;
        final int accessibilityViewId = args.argi2;
        final int virtualDescendantId = args.argi3;
        final IAccessibilityInteractionConnectionCallback callback =
            (IAccessibilityInteractionConnectionCallback) args.arg1;
        final MagnificationSpec spec = (MagnificationSpec) args.arg2;
        final Region interactiveRegion = (Region) args.arg3;
        args.recycle();

        AccessibilityNodeInfo focused = null;
        try {
            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
                return;
            }
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
            View root = null;
            if (accessibilityViewId != AccessibilityNodeInfo.ROOT_ITEM_ID) {
                root = findViewByAccessibilityId(accessibilityViewId);
            } else {
                root = mViewRootImpl.mView;
            }
            if (root != null && isShown(root)) {
                switch (focusType) {
                    case AccessibilityNodeInfo.FOCUS_ACCESSIBILITY: {
                        View host = mViewRootImpl.mAccessibilityFocusedHost;
                        // If there is no accessibility focus host or it is not a descendant
                        // of the root from which to start the search, then the search failed.
                        if (host == null || !ViewRootImpl.isViewDescendantOf(host, root)) {
                            break;
                        }
                        // The focused view not shown, we failed.
                        if (!isShown(host)) {
                            break;
                        }
                        // If the host has a provider ask this provider to search for the
                        // focus instead fetching all provider nodes to do the search here.
                        AccessibilityNodeProvider provider = host.getAccessibilityNodeProvider();
                        if (provider != null) {
                            if (mViewRootImpl.mAccessibilityFocusedVirtualView != null) {
                                focused = AccessibilityNodeInfo.obtain(
                                        mViewRootImpl.mAccessibilityFocusedVirtualView);
                            }
                        } else if (virtualDescendantId == AccessibilityNodeProvider.HOST_VIEW_ID) {
                            focused = host.createAccessibilityNodeInfo();
                        }
                    } break;
                    case AccessibilityNodeInfo.FOCUS_INPUT: {
                        View target = root.findFocus();
                        if (target == null || !isShown(target)) {
                            break;
                        }
                        AccessibilityNodeProvider provider = target.getAccessibilityNodeProvider();
                        if (provider != null) {
                            focused = provider.findFocus(focusType);
                        }
                        if (focused == null) {
                            focused = target.createAccessibilityNodeInfo();
                        }
                    } break;
                    default:
                        throw new IllegalArgumentException("Unknown focus type: " + focusType);
                }
            }
        } finally {
            updateInfoForViewportAndReturnFindNodeResult(
                    focused, callback, interactionId, spec, interactiveRegion);
        }
    }

    public void focusSearchClientThread(long accessibilityNodeId, int direction,
            Region interactiveRegion, int interactionId,
            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
            long interrogatingTid, MagnificationSpec spec) {
        Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_FOCUS_SEARCH;
        message.arg1 = flags;
        message.arg2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);

        SomeArgs args = SomeArgs.obtain();
        args.argi2 = direction;
        args.argi3 = interactionId;
        args.arg1 = callback;
        args.arg2 = spec;
        args.arg3 = interactiveRegion;

        message.obj = args;

        scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
    }

    private void focusSearchUiThread(Message message) {
        final int flags = message.arg1;
        final int accessibilityViewId = message.arg2;

        SomeArgs args = (SomeArgs) message.obj;
        final int direction = args.argi2;
        final int interactionId = args.argi3;
        final IAccessibilityInteractionConnectionCallback callback =
            (IAccessibilityInteractionConnectionCallback) args.arg1;
        final MagnificationSpec spec = (MagnificationSpec) args.arg2;
        final Region interactiveRegion = (Region) args.arg3;

        args.recycle();

        AccessibilityNodeInfo next = null;
        try {
            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
                return;
            }
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
            View root = null;
            if (accessibilityViewId != AccessibilityNodeInfo.ROOT_ITEM_ID) {
                root = findViewByAccessibilityId(accessibilityViewId);
            } else {
                root = mViewRootImpl.mView;
            }
            if (root != null && isShown(root)) {
                View nextView = root.focusSearch(direction);
                if (nextView != null) {
                    next = nextView.createAccessibilityNodeInfo();
                }
            }
        } finally {
            updateInfoForViewportAndReturnFindNodeResult(
                    next, callback, interactionId, spec, interactiveRegion);
        }
    }

    public void performAccessibilityActionClientThread(long accessibilityNodeId, int action,
            Bundle arguments, int interactionId,
            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
            long interrogatingTid) {
        Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_PERFORM_ACCESSIBILITY_ACTION;
        message.arg1 = flags;
        message.arg2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);

        SomeArgs args = SomeArgs.obtain();
        args.argi1 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
        args.argi2 = action;
        args.argi3 = interactionId;
        args.arg1 = callback;
        args.arg2 = arguments;

        message.obj = args;

        scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
    }

    private void performAccessibilityActionUiThread(Message message) {
        final int flags = message.arg1;
        final int accessibilityViewId = message.arg2;

        SomeArgs args = (SomeArgs) message.obj;
        final int virtualDescendantId = args.argi1;
        final int action = args.argi2;
        final int interactionId = args.argi3;
        final IAccessibilityInteractionConnectionCallback callback =
            (IAccessibilityInteractionConnectionCallback) args.arg1;
        Bundle arguments = (Bundle) args.arg2;

        args.recycle();

        boolean succeeded = false;
        try {
            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null ||
                    mViewRootImpl.mStopped || mViewRootImpl.mPausedForTransition) {
                return;
            }
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
            View target = null;
            if (accessibilityViewId != AccessibilityNodeInfo.ROOT_ITEM_ID) {
                target = findViewByAccessibilityId(accessibilityViewId);
            } else {
                target = mViewRootImpl.mView;
            }
            if (target != null && isShown(target)) {
                if (action == R.id.accessibilityActionClickOnClickableSpan) {
                    // Handle this hidden action separately
                    succeeded = handleClickableSpanActionUiThread(
                            target, virtualDescendantId, arguments);
                } else if (action == R.id.accessibilityActionOutsideTouch) {
                    // trigger ACTION_OUTSIDE to notify windows
                    final long now = SystemClock.uptimeMillis();
                    MotionEvent event = MotionEvent.obtain(now, now, MotionEvent.ACTION_OUTSIDE,
                            0, 0, 0);
                    event.setSource(InputDevice.SOURCE_TOUCHSCREEN);
                    mViewRootImpl.dispatchInputEvent(event);
                    succeeded = true;
                } else {
                    AccessibilityNodeProvider provider = target.getAccessibilityNodeProvider();
                    if (provider != null) {
                        succeeded = provider.performAction(virtualDescendantId, action,
                                arguments);
                    } else if (virtualDescendantId == AccessibilityNodeProvider.HOST_VIEW_ID) {
                        succeeded = target.performAccessibilityAction(action, arguments);
                    }
                }
            }
        } finally {
            try {
                mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
                callback.setPerformAccessibilityActionResult(succeeded, interactionId);
            } catch (RemoteException re) {
                /* ignore - the other side will time out */
            }
        }
    }

    /**
     * Finds the accessibility focused node in the root, and clears the accessibility focus.
     */
    public void clearAccessibilityFocusClientThread() {
        final Message message = mHandler.obtainMessage();
        message.what = PrivateHandler.MSG_CLEAR_ACCESSIBILITY_FOCUS;

        // Don't care about pid and tid because there's no interrogating client for this message.
        scheduleMessage(message, 0, 0, CONSIDER_REQUEST_PREPARERS);
    }

    private void clearAccessibilityFocusUiThread() {
        if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
            return;
        }
        try {
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags =
                    AccessibilityNodeInfo.FLAG_INCLUDE_NOT_IMPORTANT_VIEWS;
            final View root = mViewRootImpl.mView;
            if (root != null && isShown(root)) {
                final View host = mViewRootImpl.mAccessibilityFocusedHost;
                // If there is no accessibility focus host or it is not a descendant
                // of the root from which to start the search, then the search failed.
                if (host == null || !ViewRootImpl.isViewDescendantOf(host, root)) {
                    return;
                }
                final AccessibilityNodeProvider provider = host.getAccessibilityNodeProvider();
                final AccessibilityNodeInfo focusNode =
                        mViewRootImpl.mAccessibilityFocusedVirtualView;
                if (provider != null && focusNode != null) {
                    final int virtualNodeId = AccessibilityNodeInfo.getVirtualDescendantId(
                            focusNode.getSourceNodeId());
                    provider.performAction(virtualNodeId,
                            AccessibilityAction.ACTION_CLEAR_ACCESSIBILITY_FOCUS.getId(),
                            null);
                } else {
                    host.performAccessibilityAction(
                            AccessibilityAction.ACTION_CLEAR_ACCESSIBILITY_FOCUS.getId(),
                            null);
                }
            }
        } finally {
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
        }
    }

    private View findViewByAccessibilityId(int accessibilityId) {
        View root = mViewRootImpl.mView;
        if (root == null) {
            return null;
        }
        View foundView = root.findViewByAccessibilityId(accessibilityId);
        if (foundView != null && !isShown(foundView)) {
            return null;
        }
        return foundView;
    }

    private void applyAppScaleAndMagnificationSpecIfNeeded(List<AccessibilityNodeInfo> infos,
            MagnificationSpec spec) {
        if (infos == null) {
            return;
        }
        final float applicationScale = mViewRootImpl.mAttachInfo.mApplicationScale;
        if (shouldApplyAppScaleAndMagnificationSpec(applicationScale, spec)) {
            final int infoCount = infos.size();
            for (int i = 0; i < infoCount; i++) {
                AccessibilityNodeInfo info = infos.get(i);
                applyAppScaleAndMagnificationSpecIfNeeded(info, spec);
            }
        }
    }

    private void adjustIsVisibleToUserIfNeeded(List<AccessibilityNodeInfo> infos,
            Region interactiveRegion) {
        if (interactiveRegion == null || infos == null) {
            return;
        }
        final int infoCount = infos.size();
        for (int i = 0; i < infoCount; i++) {
            AccessibilityNodeInfo info = infos.get(i);
            adjustIsVisibleToUserIfNeeded(info, interactiveRegion);
        }
    }

    private void adjustIsVisibleToUserIfNeeded(AccessibilityNodeInfo info,
            Region interactiveRegion) {
        if (interactiveRegion == null || info == null) {
            return;
        }
        Rect boundsInScreen = mTempRect;
        info.getBoundsInScreen(boundsInScreen);
        if (interactiveRegion.quickReject(boundsInScreen)) {
            info.setVisibleToUser(false);
        }
    }

    private void applyAppScaleAndMagnificationSpecIfNeeded(AccessibilityNodeInfo info,
            MagnificationSpec spec) {
        if (info == null) {
            return;
        }

        final float applicationScale = mViewRootImpl.mAttachInfo.mApplicationScale;
        if (!shouldApplyAppScaleAndMagnificationSpec(applicationScale, spec)) {
            return;
        }

        Rect boundsInParent = mTempRect;
        Rect boundsInScreen = mTempRect1;

        info.getBoundsInParent(boundsInParent);
        info.getBoundsInScreen(boundsInScreen);
        if (applicationScale != 1.0f) {
            boundsInParent.scale(applicationScale);
            boundsInScreen.scale(applicationScale);
        }
        if (spec != null) {
            boundsInParent.scale(spec.scale);
            // boundsInParent must not be offset.
            boundsInScreen.scale(spec.scale);
            boundsInScreen.offset((int) spec.offsetX, (int) spec.offsetY);
        }
        info.setBoundsInParent(boundsInParent);
        info.setBoundsInScreen(boundsInScreen);

        // Scale text locations if they are present
        if (info.hasExtras()) {
            Bundle extras = info.getExtras();
            Parcelable[] textLocations =
                    extras.getParcelableArray(EXTRA_DATA_TEXT_CHARACTER_LOCATION_KEY);
            if (textLocations != null) {
                for (int i = 0; i < textLocations.length; i++) {
                    // Unchecked cast - an app that puts other objects in this bundle with this
                    // key will crash.
                    RectF textLocation = ((RectF) textLocations[i]);
                    textLocation.scale(applicationScale);
                    if (spec != null) {
                        textLocation.scale(spec.scale);
                        textLocation.offset(spec.offsetX, spec.offsetY);
                    }
                }
            }
        }

        if (spec != null) {
            AttachInfo attachInfo = mViewRootImpl.mAttachInfo;
            if (attachInfo.mDisplay == null) {
                return;
            }

            final float scale = attachInfo.mApplicationScale * spec.scale;

            Rect visibleWinFrame = mTempRect1;
            visibleWinFrame.left = (int) (attachInfo.mWindowLeft * scale + spec.offsetX);
            visibleWinFrame.top = (int) (attachInfo.mWindowTop * scale + spec.offsetY);
            visibleWinFrame.right = (int) (visibleWinFrame.left + mViewRootImpl.mWidth * scale);
            visibleWinFrame.bottom = (int) (visibleWinFrame.top + mViewRootImpl.mHeight * scale);

            attachInfo.mDisplay.getRealSize(mTempPoint);
            final int displayWidth = mTempPoint.x;
            final int displayHeight = mTempPoint.y;

            Rect visibleDisplayFrame = mTempRect2;
            visibleDisplayFrame.set(0, 0, displayWidth, displayHeight);

            if (!visibleWinFrame.intersect(visibleDisplayFrame)) {
                // If there's no intersection with display, set visibleWinFrame empty.
                visibleDisplayFrame.setEmpty();
            }

            if (!visibleWinFrame.intersects(boundsInScreen.left, boundsInScreen.top,
                    boundsInScreen.right, boundsInScreen.bottom)) {
                info.setVisibleToUser(false);
            }
        }
    }

    private boolean shouldApplyAppScaleAndMagnificationSpec(float appScale,
            MagnificationSpec spec) {
        return (appScale != 1.0f || (spec != null && !spec.isNop()));
    }

    private void updateInfosForViewportAndReturnFindNodeResult(List<AccessibilityNodeInfo> infos,
            IAccessibilityInteractionConnectionCallback callback, int interactionId,
            MagnificationSpec spec, Region interactiveRegion) {
        try {
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
            applyAppScaleAndMagnificationSpecIfNeeded(infos, spec);
            adjustIsVisibleToUserIfNeeded(infos, interactiveRegion);
            callback.setFindAccessibilityNodeInfosResult(infos, interactionId);
            if (infos != null) {
                infos.clear();
            }
        } catch (RemoteException re) {
            /* ignore - the other side will time out */
        } finally {
            recycleMagnificationSpecAndRegionIfNeeded(spec, interactiveRegion);
        }
    }

    private void updateInfoForViewportAndReturnFindNodeResult(AccessibilityNodeInfo info,
            IAccessibilityInteractionConnectionCallback callback, int interactionId,
            MagnificationSpec spec, Region interactiveRegion) {
        try {
            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
            applyAppScaleAndMagnificationSpecIfNeeded(info, spec);
            adjustIsVisibleToUserIfNeeded(info, interactiveRegion);
            callback.setFindAccessibilityNodeInfoResult(info, interactionId);
        } catch (RemoteException re) {
                /* ignore - the other side will time out */
        } finally {
            recycleMagnificationSpecAndRegionIfNeeded(spec, interactiveRegion);
        }
    }

    private void recycleMagnificationSpecAndRegionIfNeeded(MagnificationSpec spec, Region region) {
        if (android.os.Process.myPid() != Binder.getCallingPid()) {
            // Specs are cached in the system process and obtained from a pool when read from
            // a parcel, so only recycle the spec if called from another process.
            if (spec != null) {
                spec.recycle();
            }
        } else {
            // Regions are obtained in the system process and instantiated when read from
            // a parcel, so only recycle the region if caled from the same process.
            if (region != null) {
                region.recycle();
            }
        }
    }

    private boolean handleClickableSpanActionUiThread(
            View view, int virtualDescendantId, Bundle arguments) {
        Parcelable span = arguments.getParcelable(ACTION_ARGUMENT_ACCESSIBLE_CLICKABLE_SPAN);
        if (!(span instanceof AccessibilityClickableSpan)) {
            return false;
        }

        // Find the original ClickableSpan if it's still on the screen
        AccessibilityNodeInfo infoWithSpan = null;
        AccessibilityNodeProvider provider = view.getAccessibilityNodeProvider();
        if (provider != null) {
            infoWithSpan = provider.createAccessibilityNodeInfo(virtualDescendantId);
        } else if (virtualDescendantId == AccessibilityNodeProvider.HOST_VIEW_ID) {
            infoWithSpan = view.createAccessibilityNodeInfo();
        }
        if (infoWithSpan == null) {
            return false;
        }

        // Click on the corresponding span
        ClickableSpan clickableSpan = ((AccessibilityClickableSpan) span).findClickableSpan(
                infoWithSpan.getOriginalText());
        if (clickableSpan != null) {
            clickableSpan.onClick(view);
            return true;
        }
        return false;
    }

    /**
     * This class encapsulates a prefetching strategy for the accessibility APIs for
     * querying window content. It is responsible to prefetch a batch of
     * AccessibilityNodeInfos in addition to the one for a requested node.
     */
    private class AccessibilityNodePrefetcher {

        private static final int MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE = 50;

        private final ArrayList<View> mTempViewList = new ArrayList<View>();

        public void prefetchAccessibilityNodeInfos(View view, int virtualViewId, int fetchFlags,
                List<AccessibilityNodeInfo> outInfos, Bundle arguments) {
            AccessibilityNodeProvider provider = view.getAccessibilityNodeProvider();
            // Determine if we'll be populating extra data
            final String extraDataRequested = (arguments == null) ? null
                    : arguments.getString(EXTRA_DATA_REQUESTED_KEY);
            if (provider == null) {
                AccessibilityNodeInfo root = view.createAccessibilityNodeInfo();
                if (root != null) {
                    if (extraDataRequested != null) {
                        view.addExtraDataToAccessibilityNodeInfo(
                                root, extraDataRequested, arguments);
                    }
                    outInfos.add(root);
                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
                        prefetchPredecessorsOfRealNode(view, outInfos);
                    }
                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
                        prefetchSiblingsOfRealNode(view, outInfos);
                    }
                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
                        prefetchDescendantsOfRealNode(view, outInfos);
                    }
                }
            } else {
                final AccessibilityNodeInfo root =
                        provider.createAccessibilityNodeInfo(virtualViewId);
                if (root != null) {
                    if (extraDataRequested != null) {
                        provider.addExtraDataToAccessibilityNodeInfo(
                                virtualViewId, root, extraDataRequested, arguments);
                    }
                    outInfos.add(root);
                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
                        prefetchPredecessorsOfVirtualNode(root, view, provider, outInfos);
                    }
                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
                        prefetchSiblingsOfVirtualNode(root, view, provider, outInfos);
                    }
                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
                        prefetchDescendantsOfVirtualNode(root, provider, outInfos);
                    }
                }
            }
            if (ENFORCE_NODE_TREE_CONSISTENT) {
                enforceNodeTreeConsistent(outInfos);
            }
        }

        private void enforceNodeTreeConsistent(List<AccessibilityNodeInfo> nodes) {
            LongSparseArray<AccessibilityNodeInfo> nodeMap =
                    new LongSparseArray<AccessibilityNodeInfo>();
            final int nodeCount = nodes.size();
            for (int i = 0; i < nodeCount; i++) {
                AccessibilityNodeInfo node = nodes.get(i);
                nodeMap.put(node.getSourceNodeId(), node);
            }

            // If the nodes are a tree it does not matter from
            // which node we start to search for the root.
            AccessibilityNodeInfo root = nodeMap.valueAt(0);
            AccessibilityNodeInfo parent = root;
            while (parent != null) {
                root = parent;
                parent = nodeMap.get(parent.getParentNodeId());
            }

            // Traverse the tree and do some checks.
            AccessibilityNodeInfo accessFocus = null;
            AccessibilityNodeInfo inputFocus = null;
            HashSet<AccessibilityNodeInfo> seen = new HashSet<AccessibilityNodeInfo>();
            Queue<AccessibilityNodeInfo> fringe = new LinkedList<AccessibilityNodeInfo>();
            fringe.add(root);

            while (!fringe.isEmpty()) {
                AccessibilityNodeInfo current = fringe.poll();

                // Check for duplicates
                if (!seen.add(current)) {
                    throw new IllegalStateException("Duplicate node: "
                            + current + " in window:"
                            + mViewRootImpl.mAttachInfo.mAccessibilityWindowId);
                }

                // Check for one accessibility focus.
                if (current.isAccessibilityFocused()) {
                    if (accessFocus != null) {
                        throw new IllegalStateException("Duplicate accessibility focus:"
                                + current
                                + " in window:" + mViewRootImpl.mAttachInfo.mAccessibilityWindowId);
                    } else {
                        accessFocus = current;
                    }
                }

                // Check for one input focus.
                if (current.isFocused()) {
                    if (inputFocus != null) {
                        throw new IllegalStateException("Duplicate input focus: "
                            + current + " in window:"
                            + mViewRootImpl.mAttachInfo.mAccessibilityWindowId);
                    } else {
                        inputFocus = current;
                    }
                }

                final int childCount = current.getChildCount();
                for (int j = 0; j < childCount; j++) {
                    final long childId = current.getChildId(j);
                    final AccessibilityNodeInfo child = nodeMap.get(childId);
                    if (child != null) {
                        fringe.add(child);
                    }
                }
            }

            // Check for disconnected nodes.
            for (int j = nodeMap.size() - 1; j >= 0; j--) {
                AccessibilityNodeInfo info = nodeMap.valueAt(j);
                if (!seen.contains(info)) {
                    throw new IllegalStateException("Disconnected node: " + info);
                }
            }
        }

        private void prefetchPredecessorsOfRealNode(View view,
                List<AccessibilityNodeInfo> outInfos) {
            ViewParent parent = view.getParentForAccessibility();
            while (parent instanceof View
                    && outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                View parentView = (View) parent;
                AccessibilityNodeInfo info = parentView.createAccessibilityNodeInfo();
                if (info != null) {
                    outInfos.add(info);
                }
                parent = parent.getParentForAccessibility();
            }
        }

        private void prefetchSiblingsOfRealNode(View current,
                List<AccessibilityNodeInfo> outInfos) {
            ViewParent parent = current.getParentForAccessibility();
            if (parent instanceof ViewGroup) {
                ViewGroup parentGroup = (ViewGroup) parent;
                ArrayList<View> children = mTempViewList;
                children.clear();
                try {
                    parentGroup.addChildrenForAccessibility(children);
                    final int childCount = children.size();
                    for (int i = 0; i < childCount; i++) {
                        if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                            return;
                        }
                        View child = children.get(i);
                        if (child.getAccessibilityViewId() != current.getAccessibilityViewId()
                                &&  isShown(child)) {
                            AccessibilityNodeInfo info = null;
                            AccessibilityNodeProvider provider =
                                child.getAccessibilityNodeProvider();
                            if (provider == null) {
                                info = child.createAccessibilityNodeInfo();
                            } else {
                                info = provider.createAccessibilityNodeInfo(
                                        AccessibilityNodeProvider.HOST_VIEW_ID);
                            }
                            if (info != null) {
                                outInfos.add(info);
                            }
                        }
                    }
                } finally {
                    children.clear();
                }
            }
        }

        private void prefetchDescendantsOfRealNode(View root,
                List<AccessibilityNodeInfo> outInfos) {
            if (!(root instanceof ViewGroup)) {
                return;
            }
            HashMap<View, AccessibilityNodeInfo> addedChildren =
                new HashMap<View, AccessibilityNodeInfo>();
            ArrayList<View> children = mTempViewList;
            children.clear();
            try {
                root.addChildrenForAccessibility(children);
                final int childCount = children.size();
                for (int i = 0; i < childCount; i++) {
                    if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                        return;
                    }
                    View child = children.get(i);
                    if (isShown(child)) {
                        AccessibilityNodeProvider provider = child.getAccessibilityNodeProvider();
                        if (provider == null) {
                            AccessibilityNodeInfo info = child.createAccessibilityNodeInfo();
                            if (info != null) {
                                outInfos.add(info);
                                addedChildren.put(child, null);
                            }
                        } else {
                            AccessibilityNodeInfo info = provider.createAccessibilityNodeInfo(
                                   AccessibilityNodeProvider.HOST_VIEW_ID);
                            if (info != null) {
                                outInfos.add(info);
                                addedChildren.put(child, info);
                            }
                        }
                    }
                }
            } finally {
                children.clear();
            }
            if (outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                for (Map.Entry<View, AccessibilityNodeInfo> entry : addedChildren.entrySet()) {
                    View addedChild = entry.getKey();
                    AccessibilityNodeInfo virtualRoot = entry.getValue();
                    if (virtualRoot == null) {
                        prefetchDescendantsOfRealNode(addedChild, outInfos);
                    } else {
                        AccessibilityNodeProvider provider =
                            addedChild.getAccessibilityNodeProvider();
                        prefetchDescendantsOfVirtualNode(virtualRoot, provider, outInfos);
                    }
                }
            }
        }

        private void prefetchPredecessorsOfVirtualNode(AccessibilityNodeInfo root,
                View providerHost, AccessibilityNodeProvider provider,
                List<AccessibilityNodeInfo> outInfos) {
            final int initialResultSize = outInfos.size();
            long parentNodeId = root.getParentNodeId();
            int accessibilityViewId = AccessibilityNodeInfo.getAccessibilityViewId(parentNodeId);
            while (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) {
                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                    return;
                }
                final int virtualDescendantId =
                    AccessibilityNodeInfo.getVirtualDescendantId(parentNodeId);
                if (virtualDescendantId != AccessibilityNodeProvider.HOST_VIEW_ID
                        || accessibilityViewId == providerHost.getAccessibilityViewId()) {
                    final AccessibilityNodeInfo parent;
                    parent = provider.createAccessibilityNodeInfo(virtualDescendantId);
                    if (parent == null) {
                        // Going up the parent relation we found a null predecessor,
                        // so remove these disconnected nodes form the result.
                        final int currentResultSize = outInfos.size();
                        for (int i = currentResultSize - 1; i >= initialResultSize; i--) {
                            outInfos.remove(i);
                        }
                        // Couldn't obtain the parent, which means we have a
                        // disconnected sub-tree. Abort prefetch immediately.
                        return;
                    }
                    outInfos.add(parent);
                    parentNodeId = parent.getParentNodeId();
                    accessibilityViewId = AccessibilityNodeInfo.getAccessibilityViewId(
                            parentNodeId);
                } else {
                    prefetchPredecessorsOfRealNode(providerHost, outInfos);
                    return;
                }
            }
        }

        private void prefetchSiblingsOfVirtualNode(AccessibilityNodeInfo current, View providerHost,
                AccessibilityNodeProvider provider, List<AccessibilityNodeInfo> outInfos) {
            final long parentNodeId = current.getParentNodeId();
            final int parentAccessibilityViewId =
                AccessibilityNodeInfo.getAccessibilityViewId(parentNodeId);
            final int parentVirtualDescendantId =
                AccessibilityNodeInfo.getVirtualDescendantId(parentNodeId);
            if (parentVirtualDescendantId != AccessibilityNodeProvider.HOST_VIEW_ID
                    || parentAccessibilityViewId == providerHost.getAccessibilityViewId()) {
                final AccessibilityNodeInfo parent =
                        provider.createAccessibilityNodeInfo(parentVirtualDescendantId);
                if (parent != null) {
                    final int childCount = parent.getChildCount();
                    for (int i = 0; i < childCount; i++) {
                        if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                            return;
                        }
                        final long childNodeId = parent.getChildId(i);
                        if (childNodeId != current.getSourceNodeId()) {
                            final int childVirtualDescendantId =
                                AccessibilityNodeInfo.getVirtualDescendantId(childNodeId);
                            AccessibilityNodeInfo child = provider.createAccessibilityNodeInfo(
                                    childVirtualDescendantId);
                            if (child != null) {
                                outInfos.add(child);
                            }
                        }
                    }
                }
            } else {
                prefetchSiblingsOfRealNode(providerHost, outInfos);
            }
        }

        private void prefetchDescendantsOfVirtualNode(AccessibilityNodeInfo root,
                AccessibilityNodeProvider provider, List<AccessibilityNodeInfo> outInfos) {
            final int initialOutInfosSize = outInfos.size();
            final int childCount = root.getChildCount();
            for (int i = 0; i < childCount; i++) {
                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                    return;
                }
                final long childNodeId = root.getChildId(i);
                AccessibilityNodeInfo child = provider.createAccessibilityNodeInfo(
                        AccessibilityNodeInfo.getVirtualDescendantId(childNodeId));
                if (child != null) {
                    outInfos.add(child);
                }
            }
            if (outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
                final int addedChildCount = outInfos.size() - initialOutInfosSize;
                for (int i = 0; i < addedChildCount; i++) {
                    AccessibilityNodeInfo child = outInfos.get(initialOutInfosSize + i);
                    prefetchDescendantsOfVirtualNode(child, provider, outInfos);
                }
            }
        }
    }

    private class PrivateHandler extends Handler {
        private static final int MSG_PERFORM_ACCESSIBILITY_ACTION = 1;
        private static final int MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID = 2;
        private static final int MSG_FIND_ACCESSIBILITY_NODE_INFOS_BY_VIEW_ID = 3;
        private static final int MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_TEXT = 4;
        private static final int MSG_FIND_FOCUS = 5;
        private static final int MSG_FOCUS_SEARCH = 6;
        private static final int MSG_PREPARE_FOR_EXTRA_DATA_REQUEST = 7;
        private static final int MSG_APP_PREPARATION_FINISHED = 8;
        private static final int MSG_APP_PREPARATION_TIMEOUT = 9;

        // Uses FIRST_NO_ACCESSIBILITY_CALLBACK_MSG for messages that don't need to call back
        // results to interrogating client.
        private static final int FIRST_NO_ACCESSIBILITY_CALLBACK_MSG = 100;
        private static final int MSG_CLEAR_ACCESSIBILITY_FOCUS =
                FIRST_NO_ACCESSIBILITY_CALLBACK_MSG + 1;

        public PrivateHandler(Looper looper) {
            super(looper);
        }

        @Override
        public String getMessageName(Message message) {
            final int type = message.what;
            switch (type) {
                case MSG_PERFORM_ACCESSIBILITY_ACTION:
                    return "MSG_PERFORM_ACCESSIBILITY_ACTION";
                case MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID:
                    return "MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID";
                case MSG_FIND_ACCESSIBILITY_NODE_INFOS_BY_VIEW_ID:
                    return "MSG_FIND_ACCESSIBILITY_NODE_INFOS_BY_VIEW_ID";
                case MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_TEXT:
                    return "MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_TEXT";
                case MSG_FIND_FOCUS:
                    return "MSG_FIND_FOCUS";
                case MSG_FOCUS_SEARCH:
                    return "MSG_FOCUS_SEARCH";
                case MSG_PREPARE_FOR_EXTRA_DATA_REQUEST:
                    return "MSG_PREPARE_FOR_EXTRA_DATA_REQUEST";
                case MSG_APP_PREPARATION_FINISHED:
                    return "MSG_APP_PREPARATION_FINISHED";
                case MSG_APP_PREPARATION_TIMEOUT:
                    return "MSG_APP_PREPARATION_TIMEOUT";
                case MSG_CLEAR_ACCESSIBILITY_FOCUS:
                    return "MSG_CLEAR_ACCESSIBILITY_FOCUS";
                default:
                    throw new IllegalArgumentException("Unknown message type: " + type);
            }
        }

        @Override
        public void handleMessage(Message message) {
            final int type = message.what;
            switch (type) {
                case MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID: {
                    findAccessibilityNodeInfoByAccessibilityIdUiThread(message);
                } break;
                case MSG_PERFORM_ACCESSIBILITY_ACTION: {
                    performAccessibilityActionUiThread(message);
                } break;
                case MSG_FIND_ACCESSIBILITY_NODE_INFOS_BY_VIEW_ID: {
                    findAccessibilityNodeInfosByViewIdUiThread(message);
                } break;
                case MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_TEXT: {
                    findAccessibilityNodeInfosByTextUiThread(message);
                } break;
                case MSG_FIND_FOCUS: {
                    findFocusUiThread(message);
                } break;
                case MSG_FOCUS_SEARCH: {
                    focusSearchUiThread(message);
                } break;
                case MSG_PREPARE_FOR_EXTRA_DATA_REQUEST: {
                    prepareForExtraDataRequestUiThread(message);
                } break;
                case MSG_APP_PREPARATION_FINISHED: {
                    requestPreparerDoneUiThread(message);
                } break;
                case MSG_APP_PREPARATION_TIMEOUT: {
                    requestPreparerTimeoutUiThread();
                } break;
                case MSG_CLEAR_ACCESSIBILITY_FOCUS: {
                    clearAccessibilityFocusUiThread();
                } break;
                default:
                    throw new IllegalArgumentException("Unknown message type: " + type);
            }
        }

        boolean hasAccessibilityCallback(Message message) {
            return message.what < FIRST_NO_ACCESSIBILITY_CALLBACK_MSG ? true : false;
        }
    }

    private final class AddNodeInfosForViewId implements Predicate<View> {
        private int mViewId = View.NO_ID;
        private List<AccessibilityNodeInfo> mInfos;

        public void init(int viewId, List<AccessibilityNodeInfo> infos) {
            mViewId = viewId;
            mInfos = infos;
        }

        public void reset() {
            mViewId = View.NO_ID;
            mInfos = null;
        }

        @Override
        public boolean test(View view) {
            if (view.getId() == mViewId && isShown(view)) {
                mInfos.add(view.createAccessibilityNodeInfo());
            }
            return false;
        }
    }

    private static final class MessageHolder {
        final Message mMessage;
        final int mInterrogatingPid;
        final long mInterrogatingTid;

        MessageHolder(Message message, int interrogatingPid, long interrogatingTid) {
            mMessage = message;
            mInterrogatingPid = interrogatingPid;
            mInterrogatingTid = interrogatingTid;
        }
    }
}