/*
 ** Copyright 2011, 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.accessibility;

import android.accessibilityservice.IAccessibilityServiceConnection;
import android.os.Binder;
import android.os.Build;
import android.os.Bundle;
import android.os.Message;
import android.os.Process;
import android.os.RemoteException;
import android.os.SystemClock;
import android.util.Log;
import android.util.LongSparseArray;
import android.util.SparseArray;

import com.android.internal.annotations.VisibleForTesting;
import com.android.internal.util.ArrayUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.atomic.AtomicInteger;

This class is a singleton that performs accessibility interaction
which is it queries remote view hierarchies about snapshots of their
views as well requests from these hierarchies to perform certain
actions on their views.
Rationale: The content retrieval APIs are synchronous from a client's
    perspective but internally they are asynchronous. The client thread
    calls into the system requesting an action and providing a callback
    to receive the result after which it waits up to a timeout for that
    result. The system enforces security and the delegates the request
    to a given view hierarchy where a message is posted (from a binder
    thread) describing what to be performed by the main UI thread the
    result of which it delivered via the mentioned callback. However,
    the blocked client thread and the main UI thread of the target view
    hierarchy can be the same thread, for example an accessibility service
    and an activity run in the same process, thus they are executed on the
    same main thread. In such a case the retrieval will fail since the UI
    thread that has to process the message describing the work to be done
    is blocked waiting for a result is has to compute! To avoid this scenario
    when making a call the client also passes its process and thread ids so
    the accessed view hierarchy can detect if the client making the request
    is running in its main UI thread. In such a case the view hierarchy,
    specifically the binder thread performing the IPC to it, does not post a
    message to be run on the UI thread but passes it to the singleton
    interaction client through which all interactions occur and the latter is
    responsible to execute the message before starting to wait for the
    asynchronous result delivered via the callback. In this case the expected
    result is already received so no waiting is performed.
@hide
/**
 * This class is a singleton that performs accessibility interaction
 * which is it queries remote view hierarchies about snapshots of their
 * views as well requests from these hierarchies to perform certain
 * actions on their views.
 *
 * Rationale: The content retrieval APIs are synchronous from a client's
 *     perspective but internally they are asynchronous. The client thread
 *     calls into the system requesting an action and providing a callback
 *     to receive the result after which it waits up to a timeout for that
 *     result. The system enforces security and the delegates the request
 *     to a given view hierarchy where a message is posted (from a binder
 *     thread) describing what to be performed by the main UI thread the
 *     result of which it delivered via the mentioned callback. However,
 *     the blocked client thread and the main UI thread of the target view
 *     hierarchy can be the same thread, for example an accessibility service
 *     and an activity run in the same process, thus they are executed on the
 *     same main thread. In such a case the retrieval will fail since the UI
 *     thread that has to process the message describing the work to be done
 *     is blocked waiting for a result is has to compute! To avoid this scenario
 *     when making a call the client also passes its process and thread ids so
 *     the accessed view hierarchy can detect if the client making the request
 *     is running in its main UI thread. In such a case the view hierarchy,
 *     specifically the binder thread performing the IPC to it, does not post a
 *     message to be run on the UI thread but passes it to the singleton
 *     interaction client through which all interactions occur and the latter is
 *     responsible to execute the message before starting to wait for the
 *     asynchronous result delivered via the callback. In this case the expected
 *     result is already received so no waiting is performed.
 *
 * @hide
 */
public final class AccessibilityInteractionClient
        extends IAccessibilityInteractionConnectionCallback.Stub {

    public static final int NO_ID = -1;

    private static final String LOG_TAG = "AccessibilityInteractionClient";

    private static final boolean DEBUG = false;

    private static final boolean CHECK_INTEGRITY = true;

    private static final long TIMEOUT_INTERACTION_MILLIS = 5000;

    private static final Object sStaticLock = new Object();

    private static final LongSparseArray<AccessibilityInteractionClient> sClients =
        new LongSparseArray<>();

    private static final SparseArray<IAccessibilityServiceConnection> sConnectionCache =
            new SparseArray<>();

    private static AccessibilityCache sAccessibilityCache =
            new AccessibilityCache(new AccessibilityCache.AccessibilityNodeRefresher());

    private final AtomicInteger mInteractionIdCounter = new AtomicInteger();

    private final Object mInstanceLock = new Object();

    private volatile int mInteractionId = -1;

    private AccessibilityNodeInfo mFindAccessibilityNodeInfoResult;

    private List<AccessibilityNodeInfo> mFindAccessibilityNodeInfosResult;

    private boolean mPerformAccessibilityActionResult;

    private Message mSameThreadMessage;

    
Returns:
The client for the current thread./**
     * @return The client for the current thread.
     */
    public static AccessibilityInteractionClient getInstance() {
        final long threadId = Thread.currentThread().getId();
        return getInstanceForThread(threadId);
    }

    
Note: We keep one instance per interrogating thread since
the instance contains state which can lead to undesired thread interleavings.
We do not have a thread local variable since other threads should be able to
look up the correct client knowing a thread id. See ViewRootImpl for details.
Returns:
The client for a given threadId./**
     * <strong>Note:</strong> We keep one instance per interrogating thread since
     * the instance contains state which can lead to undesired thread interleavings.
     * We do not have a thread local variable since other threads should be able to
     * look up the correct client knowing a thread id. See ViewRootImpl for details.
     *
     * @return The client for a given <code>threadId</code>.
     */
    public static AccessibilityInteractionClient getInstanceForThread(long threadId) {
        synchronized (sStaticLock) {
            AccessibilityInteractionClient client = sClients.get(threadId);
            if (client == null) {
                client = new AccessibilityInteractionClient();
                sClients.put(threadId, client);
            }
            return client;
        }
    }

    
Gets a cached accessibility service connection.
Params:
connectionId – The connection id.
Returns:
The cached connection if such./**
     * Gets a cached accessibility service connection.
     *
     * @param connectionId The connection id.
     * @return The cached connection if such.
     */
    public static IAccessibilityServiceConnection getConnection(int connectionId) {
        synchronized (sConnectionCache) {
            return sConnectionCache.get(connectionId);
        }
    }

    
Adds a cached accessibility service connection.
Params:
connectionId – The connection id.
connection – The connection./**
     * Adds a cached accessibility service connection.
     *
     * @param connectionId The connection id.
     * @param connection The connection.
     */
    public static void addConnection(int connectionId, IAccessibilityServiceConnection connection) {
        synchronized (sConnectionCache) {
            sConnectionCache.put(connectionId, connection);
        }
    }

    
Removes a cached accessibility service connection.
Params:
connectionId – The connection id./**
     * Removes a cached accessibility service connection.
     *
     * @param connectionId The connection id.
     */
    public static void removeConnection(int connectionId) {
        synchronized (sConnectionCache) {
            sConnectionCache.remove(connectionId);
        }
    }

    
This method is only for testing. Replacing the cache is a generally terrible idea, but
tests need to be able to verify this class's interactions with the cache
/**
     * This method is only for testing. Replacing the cache is a generally terrible idea, but
     * tests need to be able to verify this class's interactions with the cache
     */
    @VisibleForTesting
    public static void setCache(AccessibilityCache cache) {
        sAccessibilityCache = cache;
    }

    private AccessibilityInteractionClient() {
        /* reducing constructor visibility */
    }

    
Sets the message to be processed if the interacted view hierarchy
and the interacting client are running in the same thread.
Params:
message – The message./**
     * Sets the message to be processed if the interacted view hierarchy
     * and the interacting client are running in the same thread.
     *
     * @param message The message.
     */
    public void setSameThreadMessage(Message message) {
        synchronized (mInstanceLock) {
            mSameThreadMessage = message;
            mInstanceLock.notifyAll();
        }
    }

    
Gets the root AccessibilityNodeInfo in the currently active window. 
Params:
connectionId – The id of a connection for interacting with the system.
Returns:
The root AccessibilityNodeInfo if found, null otherwise./**
     * Gets the root {@link AccessibilityNodeInfo} in the currently active window.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @return The root {@link AccessibilityNodeInfo} if found, null otherwise.
     */
    public AccessibilityNodeInfo getRootInActiveWindow(int connectionId) {
        return findAccessibilityNodeInfoByAccessibilityId(connectionId,
                AccessibilityWindowInfo.ACTIVE_WINDOW_ID, AccessibilityNodeInfo.ROOT_NODE_ID,
                false, AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS, null);
    }

    
Gets the info for a window.
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use AccessibilityWindowInfo.ACTIVE_WINDOW_ID to query the currently active window.
Returns:
The AccessibilityWindowInfo./**
     * Gets the info for a window.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @return The {@link AccessibilityWindowInfo}.
     */
    public AccessibilityWindowInfo getWindow(int connectionId, int accessibilityWindowId) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                AccessibilityWindowInfo window = sAccessibilityCache.getWindow(
                        accessibilityWindowId);
                if (window != null) {
                    if (DEBUG) {
                        Log.i(LOG_TAG, "Window cache hit");
                    }
                    return window;
                }
                if (DEBUG) {
                    Log.i(LOG_TAG, "Window cache miss");
                }
                final long identityToken = Binder.clearCallingIdentity();
                try {
                    window = connection.getWindow(accessibilityWindowId);
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }
                if (window != null) {
                    sAccessibilityCache.addWindow(window);
                    return window;
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.e(LOG_TAG, "Error while calling remote getWindow", re);
        }
        return null;
    }

    
Gets the info for all windows.
Params:
connectionId – The id of a connection for interacting with the system.
Returns:
The AccessibilityWindowInfo list./**
     * Gets the info for all windows.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @return The {@link AccessibilityWindowInfo} list.
     */
    public List<AccessibilityWindowInfo> getWindows(int connectionId) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                List<AccessibilityWindowInfo> windows = sAccessibilityCache.getWindows();
                if (windows != null) {
                    if (DEBUG) {
                        Log.i(LOG_TAG, "Windows cache hit");
                    }
                    return windows;
                }
                if (DEBUG) {
                    Log.i(LOG_TAG, "Windows cache miss");
                }
                final long identityToken = Binder.clearCallingIdentity();
                try {
                    windows = connection.getWindows();
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }
                if (windows != null) {
                    sAccessibilityCache.setWindows(windows);
                    return windows;
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.e(LOG_TAG, "Error while calling remote getWindows", re);
        }
        return Collections.emptyList();
    }

    
Finds an AccessibilityNodeInfo by accessibility id. 
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use AccessibilityWindowInfo.ACTIVE_WINDOW_ID to query the currently active window.
accessibilityNodeId – A unique view id or virtual descendant id from where to start the search. Use AccessibilityNodeInfo.ROOT_NODE_ID to start from the root.
bypassCache – Whether to bypass the cache while looking for the node.
prefetchFlags – flags to guide prefetching.
Returns:
An AccessibilityNodeInfo if found, null otherwise./**
     * Finds an {@link AccessibilityNodeInfo} by accessibility id.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @param accessibilityNodeId A unique view id or virtual descendant id from
     *     where to start the search. Use
     *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
     *     to start from the root.
     * @param bypassCache Whether to bypass the cache while looking for the node.
     * @param prefetchFlags flags to guide prefetching.
     * @return An {@link AccessibilityNodeInfo} if found, null otherwise.
     */
    public AccessibilityNodeInfo findAccessibilityNodeInfoByAccessibilityId(int connectionId,
            int accessibilityWindowId, long accessibilityNodeId, boolean bypassCache,
            int prefetchFlags, Bundle arguments) {
        if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0
                && (prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) == 0) {
            throw new IllegalArgumentException("FLAG_PREFETCH_SIBLINGS"
                + " requires FLAG_PREFETCH_PREDECESSORS");
        }
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                if (!bypassCache) {
                    AccessibilityNodeInfo cachedInfo = sAccessibilityCache.getNode(
                            accessibilityWindowId, accessibilityNodeId);
                    if (cachedInfo != null) {
                        if (DEBUG) {
                            Log.i(LOG_TAG, "Node cache hit for "
                                    + idToString(accessibilityWindowId, accessibilityNodeId));
                        }
                        return cachedInfo;
                    }
                    if (DEBUG) {
                        Log.i(LOG_TAG, "Node cache miss for "
                                + idToString(accessibilityWindowId, accessibilityNodeId));
                    }
                }
                final int interactionId = mInteractionIdCounter.getAndIncrement();
                final long identityToken = Binder.clearCallingIdentity();
                final String[] packageNames;
                try {
                    packageNames = connection.findAccessibilityNodeInfoByAccessibilityId(
                            accessibilityWindowId, accessibilityNodeId, interactionId, this,
                            prefetchFlags, Thread.currentThread().getId(), arguments);
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }
                if (packageNames != null) {
                    List<AccessibilityNodeInfo> infos = getFindAccessibilityNodeInfosResultAndClear(
                            interactionId);
                    finalizeAndCacheAccessibilityNodeInfos(infos, connectionId,
                            bypassCache, packageNames);
                    if (infos != null && !infos.isEmpty()) {
                        for (int i = 1; i < infos.size(); i++) {
                            infos.get(i).recycle();
                        }
                        return infos.get(0);
                    }
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.e(LOG_TAG, "Error while calling remote"
                    + " findAccessibilityNodeInfoByAccessibilityId", re);
        }
        return null;
    }

    private static String idToString(int accessibilityWindowId, long accessibilityNodeId) {
        return accessibilityWindowId + "/"
                + AccessibilityNodeInfo.idToString(accessibilityNodeId);
    }

    
Finds an AccessibilityNodeInfo by View id. The search is performed in the window whose id is specified and starts from the node whose accessibility id is specified. 
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use ACTIVE_WINDOW_ID.ACTIVE_WINDOW_ID to query the currently active window.
accessibilityNodeId – A unique view id or virtual descendant id from where to start the search. Use AccessibilityNodeInfo.ROOT_NODE_ID to start from the root.
viewId – The fully qualified resource name of the view id to find.
Returns:
An list of AccessibilityNodeInfo if found, empty list otherwise./**
     * Finds an {@link AccessibilityNodeInfo} by View id. The search is performed in
     * the window whose id is specified and starts from the node whose accessibility
     * id is specified.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @param accessibilityNodeId A unique view id or virtual descendant id from
     *     where to start the search. Use
     *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
     *     to start from the root.
     * @param viewId The fully qualified resource name of the view id to find.
     * @return An list of {@link AccessibilityNodeInfo} if found, empty list otherwise.
     */
    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByViewId(int connectionId,
            int accessibilityWindowId, long accessibilityNodeId, String viewId) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                final int interactionId = mInteractionIdCounter.getAndIncrement();
                final long identityToken = Binder.clearCallingIdentity();
                final String[] packageNames;
                try {
                    packageNames = connection.findAccessibilityNodeInfosByViewId(
                            accessibilityWindowId, accessibilityNodeId, viewId, interactionId, this,
                            Thread.currentThread().getId());
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }

                if (packageNames != null) {
                    List<AccessibilityNodeInfo> infos = getFindAccessibilityNodeInfosResultAndClear(
                            interactionId);
                    if (infos != null) {
                        finalizeAndCacheAccessibilityNodeInfos(infos, connectionId,
                                false, packageNames);
                        return infos;
                    }
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.w(LOG_TAG, "Error while calling remote"
                    + " findAccessibilityNodeInfoByViewIdInActiveWindow", re);
        }
        return Collections.emptyList();
    }

    
Finds AccessibilityNodeInfos by View text. The match is case insensitive containment. The search is performed in the window whose id is specified and starts from the node whose accessibility id is specified. 
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use AccessibilityWindowInfo.ACTIVE_WINDOW_ID to query the currently active window.
accessibilityNodeId – A unique view id or virtual descendant id from where to start the search. Use AccessibilityNodeInfo.ROOT_NODE_ID to start from the root.
text – The searched text.
Returns:
A list of found AccessibilityNodeInfos./**
     * Finds {@link AccessibilityNodeInfo}s by View text. The match is case
     * insensitive containment. The search is performed in the window whose
     * id is specified and starts from the node whose accessibility id is
     * specified.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @param accessibilityNodeId A unique view id or virtual descendant id from
     *     where to start the search. Use
     *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
     *     to start from the root.
     * @param text The searched text.
     * @return A list of found {@link AccessibilityNodeInfo}s.
     */
    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByText(int connectionId,
            int accessibilityWindowId, long accessibilityNodeId, String text) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                final int interactionId = mInteractionIdCounter.getAndIncrement();
                final long identityToken = Binder.clearCallingIdentity();
                final String[] packageNames;
                try {
                    packageNames = connection.findAccessibilityNodeInfosByText(
                            accessibilityWindowId, accessibilityNodeId, text, interactionId, this,
                            Thread.currentThread().getId());
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }

                if (packageNames != null) {
                    List<AccessibilityNodeInfo> infos = getFindAccessibilityNodeInfosResultAndClear(
                            interactionId);
                    if (infos != null) {
                        finalizeAndCacheAccessibilityNodeInfos(infos, connectionId,
                                false, packageNames);
                        return infos;
                    }
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.w(LOG_TAG, "Error while calling remote"
                    + " findAccessibilityNodeInfosByViewText", re);
        }
        return Collections.emptyList();
    }

    
Finds the AccessibilityNodeInfo that has the specified focus type. The search is performed in the window whose id is specified and starts from the node whose accessibility id is specified. 
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use AccessibilityWindowInfo.ACTIVE_WINDOW_ID to query the currently active window.
accessibilityNodeId – A unique view id or virtual descendant id from where to start the search. Use AccessibilityNodeInfo.ROOT_NODE_ID to start from the root.
focusType – The focus type.
Returns:
The accessibility focused AccessibilityNodeInfo./**
     * Finds the {@link android.view.accessibility.AccessibilityNodeInfo} that has the
     * specified focus type. The search is performed in the window whose id is specified
     * and starts from the node whose accessibility id is specified.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @param accessibilityNodeId A unique view id or virtual descendant id from
     *     where to start the search. Use
     *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
     *     to start from the root.
     * @param focusType The focus type.
     * @return The accessibility focused {@link AccessibilityNodeInfo}.
     */
    public AccessibilityNodeInfo findFocus(int connectionId, int accessibilityWindowId,
            long accessibilityNodeId, int focusType) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                final int interactionId = mInteractionIdCounter.getAndIncrement();
                final long identityToken = Binder.clearCallingIdentity();
                final String[] packageNames;
                try {
                    packageNames = connection.findFocus(accessibilityWindowId,
                            accessibilityNodeId, focusType, interactionId, this,
                            Thread.currentThread().getId());
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }

                if (packageNames != null) {
                    AccessibilityNodeInfo info = getFindAccessibilityNodeInfoResultAndClear(
                            interactionId);
                    finalizeAndCacheAccessibilityNodeInfo(info, connectionId, false, packageNames);
                    return info;
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.w(LOG_TAG, "Error while calling remote findFocus", re);
        }
        return null;
    }

    
Finds the accessibility focused AccessibilityNodeInfo. The search is performed in the window whose id is specified and starts from the node whose accessibility id is specified. 
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use AccessibilityWindowInfo.ACTIVE_WINDOW_ID to query the currently active window.
accessibilityNodeId – A unique view id or virtual descendant id from where to start the search. Use AccessibilityNodeInfo.ROOT_NODE_ID to start from the root.
direction – The direction in which to search for focusable.
Returns:
The accessibility focused AccessibilityNodeInfo./**
     * Finds the accessibility focused {@link android.view.accessibility.AccessibilityNodeInfo}.
     * The search is performed in the window whose id is specified and starts from the
     * node whose accessibility id is specified.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @param accessibilityNodeId A unique view id or virtual descendant id from
     *     where to start the search. Use
     *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
     *     to start from the root.
     * @param direction The direction in which to search for focusable.
     * @return The accessibility focused {@link AccessibilityNodeInfo}.
     */
    public AccessibilityNodeInfo focusSearch(int connectionId, int accessibilityWindowId,
            long accessibilityNodeId, int direction) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                final int interactionId = mInteractionIdCounter.getAndIncrement();
                final long identityToken = Binder.clearCallingIdentity();
                final String[] packageNames;
                try {
                    packageNames = connection.focusSearch(accessibilityWindowId,
                            accessibilityNodeId, direction, interactionId, this,
                            Thread.currentThread().getId());
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }

                if (packageNames != null) {
                    AccessibilityNodeInfo info = getFindAccessibilityNodeInfoResultAndClear(
                            interactionId);
                    finalizeAndCacheAccessibilityNodeInfo(info, connectionId, false, packageNames);
                    return info;
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.w(LOG_TAG, "Error while calling remote accessibilityFocusSearch", re);
        }
        return null;
    }

    
Performs an accessibility action on an AccessibilityNodeInfo. 
Params:
connectionId – The id of a connection for interacting with the system.
accessibilityWindowId – A unique window id. Use AccessibilityWindowInfo.ACTIVE_WINDOW_ID to query the currently active window.
accessibilityNodeId – A unique view id or virtual descendant id from where to start the search. Use AccessibilityNodeInfo.ROOT_NODE_ID to start from the root.
action – The action to perform.
arguments – Optional action arguments.
Returns:
Whether the action was performed./**
     * Performs an accessibility action on an {@link AccessibilityNodeInfo}.
     *
     * @param connectionId The id of a connection for interacting with the system.
     * @param accessibilityWindowId A unique window id. Use
     *     {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID}
     *     to query the currently active window.
     * @param accessibilityNodeId A unique view id or virtual descendant id from
     *     where to start the search. Use
     *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
     *     to start from the root.
     * @param action The action to perform.
     * @param arguments Optional action arguments.
     * @return Whether the action was performed.
     */
    public boolean performAccessibilityAction(int connectionId, int accessibilityWindowId,
            long accessibilityNodeId, int action, Bundle arguments) {
        try {
            IAccessibilityServiceConnection connection = getConnection(connectionId);
            if (connection != null) {
                final int interactionId = mInteractionIdCounter.getAndIncrement();
                final long identityToken = Binder.clearCallingIdentity();
                final boolean success;
                try {
                    success = connection.performAccessibilityAction(
                            accessibilityWindowId, accessibilityNodeId, action, arguments,
                            interactionId, this, Thread.currentThread().getId());
                } finally {
                    Binder.restoreCallingIdentity(identityToken);
                }

                if (success) {
                    return getPerformAccessibilityActionResultAndClear(interactionId);
                }
            } else {
                if (DEBUG) {
                    Log.w(LOG_TAG, "No connection for connection id: " + connectionId);
                }
            }
        } catch (RemoteException re) {
            Log.w(LOG_TAG, "Error while calling remote performAccessibilityAction", re);
        }
        return false;
    }

    public void clearCache() {
        sAccessibilityCache.clear();
    }

    public void onAccessibilityEvent(AccessibilityEvent event) {
        sAccessibilityCache.onAccessibilityEvent(event);
    }

    
Gets the the result of an async request that returns an AccessibilityNodeInfo. 
Params:
interactionId – The interaction id to match the result with the request.
Returns:
The result AccessibilityNodeInfo./**
     * Gets the the result of an async request that returns an {@link AccessibilityNodeInfo}.
     *
     * @param interactionId The interaction id to match the result with the request.
     * @return The result {@link AccessibilityNodeInfo}.
     */
    private AccessibilityNodeInfo getFindAccessibilityNodeInfoResultAndClear(int interactionId) {
        synchronized (mInstanceLock) {
            final boolean success = waitForResultTimedLocked(interactionId);
            AccessibilityNodeInfo result = success ? mFindAccessibilityNodeInfoResult : null;
            clearResultLocked();
            return result;
        }
    }

    
{@inheritDoc}
/**
     * {@inheritDoc}
     */
    public void setFindAccessibilityNodeInfoResult(AccessibilityNodeInfo info,
                int interactionId) {
        synchronized (mInstanceLock) {
            if (interactionId > mInteractionId) {
                mFindAccessibilityNodeInfoResult = info;
                mInteractionId = interactionId;
            }
            mInstanceLock.notifyAll();
        }
    }

    
Gets the the result of an async request that returns AccessibilityNodeInfos. 
Params:
interactionId – The interaction id to match the result with the request.
Returns:
The result AccessibilityNodeInfos./**
     * Gets the the result of an async request that returns {@link AccessibilityNodeInfo}s.
     *
     * @param interactionId The interaction id to match the result with the request.
     * @return The result {@link AccessibilityNodeInfo}s.
     */
    private List<AccessibilityNodeInfo> getFindAccessibilityNodeInfosResultAndClear(
                int interactionId) {
        synchronized (mInstanceLock) {
            final boolean success = waitForResultTimedLocked(interactionId);
            final List<AccessibilityNodeInfo> result;
            if (success) {
                result = mFindAccessibilityNodeInfosResult;
            } else {
                result = Collections.emptyList();
            }
            clearResultLocked();
            if (Build.IS_DEBUGGABLE && CHECK_INTEGRITY) {
                checkFindAccessibilityNodeInfoResultIntegrity(result);
            }
            return result;
        }
    }

    
{@inheritDoc}
/**
     * {@inheritDoc}
     */
    public void setFindAccessibilityNodeInfosResult(List<AccessibilityNodeInfo> infos,
                int interactionId) {
        synchronized (mInstanceLock) {
            if (interactionId > mInteractionId) {
                if (infos != null) {
                    // If the call is not an IPC, i.e. it is made from the same process, we need to
                    // instantiate new result list to avoid passing internal instances to clients.
                    final boolean isIpcCall = (Binder.getCallingPid() != Process.myPid());
                    if (!isIpcCall) {
                        mFindAccessibilityNodeInfosResult = new ArrayList<>(infos);
                    } else {
                        mFindAccessibilityNodeInfosResult = infos;
                    }
                } else {
                    mFindAccessibilityNodeInfosResult = Collections.emptyList();
                }
                mInteractionId = interactionId;
            }
            mInstanceLock.notifyAll();
        }
    }

    
Gets the result of a request to perform an accessibility action.
Params:
interactionId – The interaction id to match the result with the request.
Returns:
Whether the action was performed./**
     * Gets the result of a request to perform an accessibility action.
     *
     * @param interactionId The interaction id to match the result with the request.
     * @return Whether the action was performed.
     */
    private boolean getPerformAccessibilityActionResultAndClear(int interactionId) {
        synchronized (mInstanceLock) {
            final boolean success = waitForResultTimedLocked(interactionId);
            final boolean result = success ? mPerformAccessibilityActionResult : false;
            clearResultLocked();
            return result;
        }
    }

    
{@inheritDoc}
/**
     * {@inheritDoc}
     */
    public void setPerformAccessibilityActionResult(boolean succeeded, int interactionId) {
        synchronized (mInstanceLock) {
            if (interactionId > mInteractionId) {
                mPerformAccessibilityActionResult = succeeded;
                mInteractionId = interactionId;
            }
            mInstanceLock.notifyAll();
        }
    }

    
Clears the result state.
/**
     * Clears the result state.
     */
    private void clearResultLocked() {
        mInteractionId = -1;
        mFindAccessibilityNodeInfoResult = null;
        mFindAccessibilityNodeInfosResult = null;
        mPerformAccessibilityActionResult = false;
    }

    
Waits up to a given bound for a result of a request and returns it.
Params:
interactionId – The interaction id to match the result with the request.
Returns:
Whether the result was received./**
     * Waits up to a given bound for a result of a request and returns it.
     *
     * @param interactionId The interaction id to match the result with the request.
     * @return Whether the result was received.
     */
    private boolean waitForResultTimedLocked(int interactionId) {
        long waitTimeMillis = TIMEOUT_INTERACTION_MILLIS;
        final long startTimeMillis = SystemClock.uptimeMillis();
        while (true) {
            try {
                Message sameProcessMessage = getSameProcessMessageAndClear();
                if (sameProcessMessage != null) {
                    sameProcessMessage.getTarget().handleMessage(sameProcessMessage);
                }

                if (mInteractionId == interactionId) {
                    return true;
                }
                if (mInteractionId > interactionId) {
                    return false;
                }
                final long elapsedTimeMillis = SystemClock.uptimeMillis() - startTimeMillis;
                waitTimeMillis = TIMEOUT_INTERACTION_MILLIS - elapsedTimeMillis;
                if (waitTimeMillis <= 0) {
                    return false;
                }
                mInstanceLock.wait(waitTimeMillis);
            } catch (InterruptedException ie) {
                /* ignore */
            }
        }
    }

    
Finalize an AccessibilityNodeInfo before passing it to the client. 
Params:
info – The info.
connectionId – The id of the connection to the system.
bypassCache – Whether or not to bypass the cache. The node is added to the cache if this value is false
packageNames – The valid package names a node can come from./**
     * Finalize an {@link AccessibilityNodeInfo} before passing it to the client.
     *
     * @param info The info.
     * @param connectionId The id of the connection to the system.
     * @param bypassCache Whether or not to bypass the cache. The node is added to the cache if
     *                    this value is {@code false}
     * @param packageNames The valid package names a node can come from.
     */
    private void finalizeAndCacheAccessibilityNodeInfo(AccessibilityNodeInfo info,
            int connectionId, boolean bypassCache, String[] packageNames) {
        if (info != null) {
            info.setConnectionId(connectionId);
            // Empty array means any package name is Okay
            if (!ArrayUtils.isEmpty(packageNames)) {
                CharSequence packageName = info.getPackageName();
                if (packageName == null
                        || !ArrayUtils.contains(packageNames, packageName.toString())) {
                    // If the node package not one of the valid ones, pick the top one - this
                    // is one of the packages running in the introspected UID.
                    info.setPackageName(packageNames[0]);
                }
            }
            info.setSealed(true);
            if (!bypassCache) {
                sAccessibilityCache.add(info);
            }
        }
    }

    
Finalize AccessibilityNodeInfos before passing them to the client. 
Params:
infos – The AccessibilityNodeInfos.
connectionId – The id of the connection to the system.
bypassCache – Whether or not to bypass the cache. The nodes are added to the cache if this value is false
packageNames – The valid package names a node can come from./**
     * Finalize {@link AccessibilityNodeInfo}s before passing them to the client.
     *
     * @param infos The {@link AccessibilityNodeInfo}s.
     * @param connectionId The id of the connection to the system.
     * @param bypassCache Whether or not to bypass the cache. The nodes are added to the cache if
     *                    this value is {@code false}
     * @param packageNames The valid package names a node can come from.
     */
    private void finalizeAndCacheAccessibilityNodeInfos(List<AccessibilityNodeInfo> infos,
            int connectionId, boolean bypassCache, String[] packageNames) {
        if (infos != null) {
            final int infosCount = infos.size();
            for (int i = 0; i < infosCount; i++) {
                AccessibilityNodeInfo info = infos.get(i);
                finalizeAndCacheAccessibilityNodeInfo(info, connectionId,
                        bypassCache, packageNames);
            }
        }
    }

    
Gets the message stored if the interacted and interacting
threads are the same.
Returns:
The message./**
     * Gets the message stored if the interacted and interacting
     * threads are the same.
     *
     * @return The message.
     */
    private Message getSameProcessMessageAndClear() {
        synchronized (mInstanceLock) {
            Message result = mSameThreadMessage;
            mSameThreadMessage = null;
            return result;
        }
    }

    
Checks whether the infos are a fully connected tree with no duplicates.
Params:
infos – The result list to check./**
     * Checks whether the infos are a fully connected tree with no duplicates.
     *
     * @param infos The result list to check.
     */
    private void checkFindAccessibilityNodeInfoResultIntegrity(List<AccessibilityNodeInfo> infos) {
        if (infos.size() == 0) {
            return;
        }
        // Find the root node.
        AccessibilityNodeInfo root = infos.get(0);
        final int infoCount = infos.size();
        for (int i = 1; i < infoCount; i++) {
            for (int j = i; j < infoCount; j++) {
                AccessibilityNodeInfo candidate = infos.get(j);
                if (root.getParentNodeId() == candidate.getSourceNodeId()) {
                    root = candidate;
                    break;
                }
            }
        }
        if (root == null) {
            Log.e(LOG_TAG, "No root.");
        }
        // Check for duplicates.
        HashSet<AccessibilityNodeInfo> seen = new HashSet<>();
        Queue<AccessibilityNodeInfo> fringe = new LinkedList<>();
        fringe.add(root);
        while (!fringe.isEmpty()) {
            AccessibilityNodeInfo current = fringe.poll();
            if (!seen.add(current)) {
                Log.e(LOG_TAG, "Duplicate node.");
                return;
            }
            final int childCount = current.getChildCount();
            for (int i = 0; i < childCount; i++) {
                final long childId = current.getChildId(i);
                for (int j = 0; j < infoCount; j++) {
                    AccessibilityNodeInfo child = infos.get(j);
                    if (child.getSourceNodeId() == childId) {
                        fringe.add(child);
                    }
                }
            }
        }
        final int disconnectedCount = infos.size() - seen.size();
        if (disconnectedCount > 0) {
            Log.e(LOG_TAG, disconnectedCount + " Disconnected nodes.");
        }
    }
}