Accessibility focus - framework

Usefulness: Keep track of the current user location in the screen when
            traversing the it. Enabling structural and directional
            navigation over all elements on the screen. This enables
            blind users that know the application layout to efficiently
            locate desired elements as opposed to try touch exploring the
            region where the the element should be - very tedious.

Rationale: There are two ways to implement accessibility focus One is
           to let accessibility services keep track of it since they
           have access to the screen content, and another to let the view
           hierarchy keep track of it. While the first approach would
           require almost no work on our part it poses several challenges
           which make it a sub-optimal choice. Having the accessibility focus
           in the accessibility service would require that service to scrape
           the window content every time it changes to sync the view tree
           state and the accessibility focus location. Pretty much the service
           will have to keep an off screen model of the screen content. This
           could be quite challenging to get right and would incur performance
           cost for the multiple IPCs to repeatedly fetch the screen content.
           Further, keeping virtual accessibility focus (i.e. in the service)
           would require sync of the input and accessibility focus. This could
           be challenging to implement right as well. Also, having an unlimited
           number of accessibility services we cannot guarantee that they will
           have a proper implementation, if any, to allow users to perform structural
           navigation of the screen content. Assuming two accessibility
           services implement structural navigation via accessibility focus,
           there is not guarantee that they will behave similarly by default,
           i.e. provide some standard way to navigate the screen content.
           Also feedback from experienced accessibility researchers, specifically
           T.V Raman, provides evidence that having virtual accessibility focus
           creates many issues and it is very hard to get right.
           Therefore, keeping accessibility focus in the system will avoid
           keeping an off-screen model in accessibility services, it will always
           be in sync with the state of the view hierarchy and the input focus.
           Also this will allow having a default behavior for traversing the
           screen via this accessibility focus that is consistent in all
           accessibility services. We provide accessibility services with APIs to
           override this behavior but all of them will perform screen traversal
           in a consistent way by default.

Behavior:  If accessibility is enabled the accessibility focus is the leading one
           and the input follows it. Putting accessibility focus on a view moves
           the input focus there. Clearing the accessibility focus of a view, clears
           the input focus of this view. If accessibility focus is on a view that
           cannot take input focus, then no other view should have input focus.
           In accessibility mode we initially give accessibility focus to the topmost
           view and no view has input focus. This ensures consistent behavior accross
           all apps. Note that accessibility focus can move hierarchically in the
           view tree and having it at the root is better than putting it where the
           input focus would be - at the first input focusable which could be at
           an arbitrary depth in the view tree. By default not all views are reported
           for accessibility, only the important ones. A view may be explicitly labeled
           as important or not for accessibility, or the system determines which one
           is such - default. Important views for accessibility are all views that are
           not dumb layout managers used only to arrange their chidren. Since the same
           content arrangement can be obtained via different combintation of layout
           managers, such managers cannot be used to reliably determine the application
           structure. For example, a user should see a list as a list view with several
           list items and each list item as a text view and a button as opposed to seeing
           all the layout managers used to arrange the list item's content.
           By default only important for accessibility views are regared for accessibility
           purposes. View not regarded for accessibility neither fire accessibility events,
           nor are reported being on the screen. An accessibility service may request the
           system to regard all views. If the target SDK of an accessibility services is
           less than JellyBean, then all views are regarded for accessibility.
           Note that an accessibility service that requires all view to be ragarded for
           accessibility may put accessibility focus on any view. Hence, it may implement
           any navigational paradigm if desired. Especially considering the fact that
           the system is detecting some standard gestures and delegates their processing
           to an accessibility service. The default implementation of an accessibility
           services performs the defualt navigation.

bug:5932640
bug:5605641

Change-Id: Ieac461d480579d706a847b9325720cb254736ebe

1 files changed, 900 insertions, 0 deletions

diff --git a/core/java/android/view/AccessibilityInteractionController.java b/core/java/android/view/AccessibilityInteractionController.java
new file mode 100644
index 000000000000..ab21b325fbd0
--- /dev/null
+++ b/core/java/android/view/AccessibilityInteractionController.java
@@ -0,0 +1,900 @@
+/*
+ * 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.INCLUDE_NOT_IMPORTANT_VIEWS;
+
+import android.os.Handler;
+import android.os.Looper;
+import android.os.Message;
+import android.os.Process;
+import android.os.RemoteException;
+import android.util.Pool;
+import android.util.Poolable;
+import android.util.PoolableManager;
+import android.util.Pools;
+import android.util.SparseLongArray;
+import android.view.ViewGroup.ChildListForAccessibility;
+import android.view.accessibility.AccessibilityInteractionClient;
+import android.view.accessibility.AccessibilityNodeInfo;
+import android.view.accessibility.AccessibilityNodeProvider;
+import android.view.accessibility.IAccessibilityInteractionConnectionCallback;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * 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.
+ */
+final class AccessibilityInteractionController {
+    private static final int POOL_SIZE = 5;
+
+    private ArrayList<AccessibilityNodeInfo> mTempAccessibilityNodeInfoList =
+        new ArrayList<AccessibilityNodeInfo>();
+
+    private final Handler mHandler = new PrivateHandler();
+
+    private final ViewRootImpl mViewRootImpl;
+
+    private final AccessibilityNodePrefetcher mPrefetcher;
+
+    public AccessibilityInteractionController(ViewRootImpl viewRootImpl) {
+        mViewRootImpl = viewRootImpl;
+        mPrefetcher = new AccessibilityNodePrefetcher();
+    }
+
+    // Reusable poolable arguments for interacting with the view hierarchy
+    // to fit more arguments than Message and to avoid sharing objects between
+    // two messages since several threads can send messages concurrently.
+    private final Pool<SomeArgs> mPool = Pools.synchronizedPool(Pools.finitePool(
+            new PoolableManager<SomeArgs>() {
+                public SomeArgs newInstance() {
+                    return new SomeArgs();
+                }
+
+                public void onAcquired(SomeArgs info) {
+                    /* do nothing */
+                }
+
+                public void onReleased(SomeArgs info) {
+                    info.clear();
+                }
+            }, POOL_SIZE)
+    );
+
+    private class SomeArgs implements Poolable<SomeArgs> {
+        private SomeArgs mNext;
+        private boolean mIsPooled;
+
+        public Object arg1;
+        public Object arg2;
+        public int argi1;
+        public int argi2;
+        public int argi3;
+
+        public SomeArgs getNextPoolable() {
+            return mNext;
+        }
+
+        public boolean isPooled() {
+            return mIsPooled;
+        }
+
+        public void setNextPoolable(SomeArgs args) {
+            mNext = args;
+        }
+
+        public void setPooled(boolean isPooled) {
+            mIsPooled = isPooled;
+        }
+
+        private void clear() {
+            arg1 = null;
+            arg2 = null;
+            argi1 = 0;
+            argi2 = 0;
+            argi3 = 0;
+        }
+    }
+
+    public void findAccessibilityNodeInfoByAccessibilityIdClientThread(
+            long accessibilityNodeId, int interactionId,
+            IAccessibilityInteractionConnectionCallback callback, int flags, int interrogatingPid,
+            long interrogatingTid) {
+        Message message = mHandler.obtainMessage();
+        message.what = PrivateHandler.MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_ACCESSIBILITY_ID;
+        message.arg1 = flags;
+        SomeArgs args = mPool.acquire();
+        args.argi1 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
+        args.argi2 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
+        args.argi3 = interactionId;
+        args.arg1 = callback;
+        message.obj = args;
+        // 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 == Process.myPid()
+                && interrogatingTid == Looper.getMainLooper().getThread().getId()) {
+            AccessibilityInteractionClient.getInstanceForThread(
+                    interrogatingTid).setSameThreadMessage(message);
+        } else {
+            mHandler.sendMessage(message);
+        }
+    }
+
+    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;
+        mPool.release(args);
+        List<AccessibilityNodeInfo> infos = mTempAccessibilityNodeInfoList;
+        infos.clear();
+        try {
+            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
+                return;
+            }
+            mViewRootImpl.mAttachInfo.mIncludeNotImportantViews =
+                (flags & INCLUDE_NOT_IMPORTANT_VIEWS) != 0;
+            View root = null;
+            if (accessibilityViewId == AccessibilityNodeInfo.UNDEFINED) {
+                root = mViewRootImpl.mView;
+            } else {
+                root = findViewByAccessibilityId(accessibilityViewId);
+            }
+            if (root != null && isDisplayedOnScreen(root)) {
+                mPrefetcher.prefetchAccessibilityNodeInfos(root, virtualDescendantId, flags, infos);
+            }
+        } finally {
+            try {
+                mViewRootImpl.mAttachInfo.mIncludeNotImportantViews = false;
+                callback.setFindAccessibilityNodeInfosResult(infos, interactionId);
+                infos.clear();
+            } catch (RemoteException re) {
+                /* ignore - the other side will time out */
+            }
+        }
+    }
+
+    public void findAccessibilityNodeInfoByViewIdClientThread(long accessibilityNodeId,
+            int viewId, int interactionId, IAccessibilityInteractionConnectionCallback callback,
+            int flags, int interrogatingPid, long interrogatingTid) {
+        Message message = mHandler.obtainMessage();
+        message.what = PrivateHandler.MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_VIEW_ID;
+        message.arg1 = flags;
+        message.arg2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
+        SomeArgs args = mPool.acquire();
+        args.argi1 = viewId;
+        args.argi2 = interactionId;
+        args.arg1 = callback;
+        message.obj = args;
+        // 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 == Process.myPid()
+                && interrogatingTid == Looper.getMainLooper().getThread().getId()) {
+            AccessibilityInteractionClient.getInstanceForThread(
+                    interrogatingTid).setSameThreadMessage(message);
+        } else {
+            mHandler.sendMessage(message);
+        }
+    }
+
+    private void findAccessibilityNodeInfoByViewIdUiThread(Message message) {
+        final int flags = message.arg1;
+        final int accessibilityViewId = message.arg2;
+        SomeArgs args = (SomeArgs) message.obj;
+        final int viewId = args.argi1;
+        final int interactionId = args.argi2;
+        final IAccessibilityInteractionConnectionCallback callback =
+            (IAccessibilityInteractionConnectionCallback) args.arg1;
+        mPool.release(args);
+        AccessibilityNodeInfo info = null;
+        try {
+            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
+                return;
+            }
+            mViewRootImpl.mAttachInfo.mIncludeNotImportantViews =
+                (flags & INCLUDE_NOT_IMPORTANT_VIEWS) != 0;
+            View root = null;
+            if (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                root = findViewByAccessibilityId(accessibilityViewId);
+            } else {
+                root = mViewRootImpl.mView;
+            }
+            if (root != null) {
+                View target = root.findViewById(viewId);
+                if (target != null && isDisplayedOnScreen(target)) {
+                    info = target.createAccessibilityNodeInfo();
+                }
+            }
+        } finally {
+            try {
+                mViewRootImpl.mAttachInfo.mIncludeNotImportantViews = false;
+                callback.setFindAccessibilityNodeInfoResult(info, interactionId);
+            } catch (RemoteException re) {
+                /* ignore - the other side will time out */
+            }
+        }
+    }
+
+    public void findAccessibilityNodeInfosByTextClientThread(long accessibilityNodeId,
+            String text, int interactionId, IAccessibilityInteractionConnectionCallback callback,
+            int flags,  int interrogatingPid, long interrogatingTid) {
+        Message message = mHandler.obtainMessage();
+        message.what = PrivateHandler.MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_TEXT;
+        message.arg1 = flags;
+        SomeArgs args = mPool.acquire();
+        args.arg1 = text;
+        args.argi1 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
+        args.argi2 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
+        args.argi3 = interactionId;
+        args.arg2 = callback;
+        message.obj = args;
+        // 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 == Process.myPid()
+                && interrogatingTid == Looper.getMainLooper().getThread().getId()) {
+            AccessibilityInteractionClient.getInstanceForThread(
+                    interrogatingTid).setSameThreadMessage(message);
+        } else {
+            mHandler.sendMessage(message);
+        }
+    }
+
+    private void findAccessibilityNodeInfosByTextUiThread(Message message) {
+        final int flags = message.arg1;
+        SomeArgs args = (SomeArgs) message.obj;
+        final String text = (String) args.arg1;
+        final int accessibilityViewId = args.argi1;
+        final int virtualDescendantId = args.argi2;
+        final int interactionId = args.argi3;
+        final IAccessibilityInteractionConnectionCallback callback =
+            (IAccessibilityInteractionConnectionCallback) args.arg2;
+        mPool.release(args);
+        List<AccessibilityNodeInfo> infos = null;
+        try {
+            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
+                return;
+            }
+            mViewRootImpl.mAttachInfo.mIncludeNotImportantViews =
+                (flags & INCLUDE_NOT_IMPORTANT_VIEWS) != 0;
+            View root = null;
+            if (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                root = findViewByAccessibilityId(accessibilityViewId);
+            } else {
+                root = mViewRootImpl.mView;
+            }
+            if (root != null && isDisplayedOnScreen(root)) {
+                AccessibilityNodeProvider provider = root.getAccessibilityNodeProvider();
+                if (provider != null) {
+                    infos = provider.findAccessibilityNodeInfosByText(text,
+                            virtualDescendantId);
+                } else if (virtualDescendantId == AccessibilityNodeInfo.UNDEFINED) {
+                    ArrayList<View> foundViews = mViewRootImpl.mAttachInfo.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 (isDisplayedOnScreen(foundView)) {
+                                provider = foundView.getAccessibilityNodeProvider();
+                                if (provider != null) {
+                                    List<AccessibilityNodeInfo> infosFromProvider =
+                                        provider.findAccessibilityNodeInfosByText(text,
+                                                virtualDescendantId);
+                                    if (infosFromProvider != null) {
+                                        infos.addAll(infosFromProvider);
+                                    }
+                                } else  {
+                                    infos.add(foundView.createAccessibilityNodeInfo());
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        } finally {
+            try {
+                mViewRootImpl.mAttachInfo.mIncludeNotImportantViews = false;
+                callback.setFindAccessibilityNodeInfosResult(infos, interactionId);
+            } catch (RemoteException re) {
+                /* ignore - the other side will time out */
+            }
+        }
+    }
+
+    public void findFocusClientThread(long accessibilityNodeId, int interactionId, int focusType,
+            IAccessibilityInteractionConnectionCallback callback,  int flags, int interogatingPid,
+            long interrogatingTid) {
+        Message message = mHandler.obtainMessage();
+        message.what = PrivateHandler.MSG_FIND_FOCUS;
+        message.arg1 = flags;
+        message.arg2 = focusType;
+        SomeArgs args = mPool.acquire();
+        args.argi1 = interactionId;
+        args.argi2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
+        args.argi3 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
+        args.arg1 = callback;
+        message.obj = args;
+        // 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 (interogatingPid == Process.myPid()
+                && interrogatingTid == Looper.getMainLooper().getThread().getId()) {
+            AccessibilityInteractionClient.getInstanceForThread(
+                    interrogatingTid).setSameThreadMessage(message);
+        } else {
+            mHandler.sendMessage(message);
+        }
+    }
+
+    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;
+        mPool.release(args);
+        AccessibilityNodeInfo focused = null;
+        try {
+            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
+                return;
+            }
+            mViewRootImpl.mAttachInfo.mIncludeNotImportantViews =
+                (flags & INCLUDE_NOT_IMPORTANT_VIEWS) != 0;
+            View root = null;
+            if (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                root = findViewByAccessibilityId(accessibilityViewId);
+            } else {
+                root = mViewRootImpl.mView;
+            }
+            if (root != null && isDisplayedOnScreen(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;
+                        }
+                        // 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) {
+                            focused = provider.findAccessibilitiyFocus(virtualDescendantId);
+                        } else if (virtualDescendantId == View.NO_ID) {
+                            focused = host.createAccessibilityNodeInfo();
+                        }
+                    } break;
+                    case AccessibilityNodeInfo.FOCUS_INPUT: {
+                        // Input focus cannot go to virtual views.
+                        View target = root.findFocus();
+                        if (target != null && isDisplayedOnScreen(target)) {
+                            focused = target.createAccessibilityNodeInfo();
+                        }
+                    } break;
+                    default:
+                        throw new IllegalArgumentException("Unknown focus type: " + focusType);
+                }
+            }
+        } finally {
+            try {
+                mViewRootImpl.mAttachInfo.mIncludeNotImportantViews = false;
+                callback.setFindAccessibilityNodeInfoResult(focused, interactionId);
+            } catch (RemoteException re) {
+                /* ignore - the other side will time out */
+            }
+        }
+    }
+
+    public void focusSearchClientThread(long accessibilityNodeId, int interactionId, int direction,
+            IAccessibilityInteractionConnectionCallback callback, int flags, int interogatingPid,
+            long interrogatingTid) {
+        Message message = mHandler.obtainMessage();
+        message.what = PrivateHandler.MSG_FOCUS_SEARCH;
+        message.arg1 = flags;
+        message.arg2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
+        SomeArgs args = mPool.acquire();
+        args.argi1 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
+        args.argi2 = direction;
+        args.argi3 = interactionId;
+        args.arg1 = callback;
+        message.obj = args;
+        // 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 (interogatingPid == Process.myPid()
+                && interrogatingTid == Looper.getMainLooper().getThread().getId()) {
+            AccessibilityInteractionClient.getInstanceForThread(
+                    interrogatingTid).setSameThreadMessage(message);
+        } else {
+            mHandler.sendMessage(message);
+        }
+    }
+
+    private void focusSearchUiThread(Message message) {
+        final int flags = message.arg1;
+        final int accessibilityViewId = message.arg2;
+        SomeArgs args = (SomeArgs) message.obj;
+        final int virtualDescendantId = args.argi1;
+        final int direction = args.argi2;
+        final int interactionId = args.argi3;
+        final IAccessibilityInteractionConnectionCallback callback =
+            (IAccessibilityInteractionConnectionCallback) args.arg1;
+        mPool.release(args);
+        AccessibilityNodeInfo next = null;
+        try {
+            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
+                return;
+            }
+            mViewRootImpl.mAttachInfo.mIncludeNotImportantViews =
+                (flags & INCLUDE_NOT_IMPORTANT_VIEWS) != 0;
+            View root = null;
+            if (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                root = findViewByAccessibilityId(accessibilityViewId);
+            } else {
+                root = mViewRootImpl.mView;
+            }
+            if (root != null && isDisplayedOnScreen(root)) {
+                if ((direction & View.FOCUS_ACCESSIBILITY) ==  View.FOCUS_ACCESSIBILITY) {
+                    AccessibilityNodeProvider provider = root.getAccessibilityNodeProvider();
+                    if (provider != null) {
+                        next = provider.accessibilityFocusSearch(direction,
+                                virtualDescendantId);
+                    } else if (virtualDescendantId == View.NO_ID) {
+                        View nextView = root.focusSearch(direction);
+                        if (nextView != null) {
+                            // If the focus search reached a node with a provider
+                            // we delegate to the provider to find the next one.
+                            provider = nextView.getAccessibilityNodeProvider();
+                            if (provider != null) {
+                                next = provider.accessibilityFocusSearch(direction,
+                                        virtualDescendantId);
+                            } else {
+                                next = nextView.createAccessibilityNodeInfo();
+                             }
+                        }
+                    }
+                } else {
+                    View nextView = root.focusSearch(direction);
+                    if (nextView != null) {
+                        next = nextView.createAccessibilityNodeInfo();
+                    }
+                }
+            }
+        } finally {
+            try {
+                mViewRootImpl.mAttachInfo.mIncludeNotImportantViews = false;
+                callback.setFindAccessibilityNodeInfoResult(next, interactionId);
+            } catch (RemoteException re) {
+                /* ignore - the other side will time out */
+            }
+        }
+    }
+
+    public void performAccessibilityActionClientThread(long accessibilityNodeId, int action,
+            int interactionId, IAccessibilityInteractionConnectionCallback callback, int flags,
+            int interogatingPid, long interrogatingTid) {
+        Message message = mHandler.obtainMessage();
+        message.what = PrivateHandler.MSG_PERFORM_ACCESSIBILITY_ACTION;
+        message.arg1 = flags;
+        message.arg2 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
+        SomeArgs args = mPool.acquire();
+        args.argi1 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
+        args.argi2 = action;
+        args.argi3 = interactionId;
+        args.arg1 = callback;
+        message.obj = args;
+        // 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 (interogatingPid == Process.myPid()
+                && interrogatingTid == Looper.getMainLooper().getThread().getId()) {
+            AccessibilityInteractionClient.getInstanceForThread(
+                    interrogatingTid).setSameThreadMessage(message);
+        } else {
+            mHandler.sendMessage(message);
+        }
+    }
+
+    private void perfromAccessibilityActionUiThread(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;
+        mPool.release(args);
+        boolean succeeded = false;
+        try {
+            if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
+                return;
+            }
+            mViewRootImpl.mAttachInfo.mIncludeNotImportantViews =
+                (flags & INCLUDE_NOT_IMPORTANT_VIEWS) != 0;
+            View target = null;
+            if (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                target = findViewByAccessibilityId(accessibilityViewId);
+            } else {
+                target = mViewRootImpl.mView;
+            }
+            if (target != null && isDisplayedOnScreen(target)) {
+                AccessibilityNodeProvider provider = target.getAccessibilityNodeProvider();
+                if (provider != null) {
+                    succeeded = provider.performAccessibilityAction(action, virtualDescendantId);
+                } else if (virtualDescendantId == View.NO_ID) {
+                    succeeded = target.performAccessibilityAction(action);
+                }
+            }
+        } finally {
+            try {
+                mViewRootImpl.mAttachInfo.mIncludeNotImportantViews = false;
+                callback.setPerformAccessibilityActionResult(succeeded, interactionId);
+            } catch (RemoteException re) {
+                /* ignore - the other side will time out */
+            }
+        }
+    }
+
+    private View findViewByAccessibilityId(int accessibilityId) {
+        View root = mViewRootImpl.mView;
+        if (root == null) {
+            return null;
+        }
+        View foundView = root.findViewByAccessibilityId(accessibilityId);
+        if (foundView != null && !isDisplayedOnScreen(foundView)) {
+            return null;
+        }
+        return foundView;
+    }
+
+    /**
+     * Computes whether a view is visible on the screen.
+     *
+     * @param view The view to check.
+     * @return Whether the view is visible on the screen.
+     */
+    private boolean isDisplayedOnScreen(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()
+                && view.getGlobalVisibleRect(mViewRootImpl.mTempRect));
+    }
+
+    /**
+     * 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;
+
+        public void prefetchAccessibilityNodeInfos(View view, int virtualViewId, int prefetchFlags,
+                List<AccessibilityNodeInfo> outInfos) {
+            AccessibilityNodeProvider provider = view.getAccessibilityNodeProvider();
+            if (provider == null) {
+                AccessibilityNodeInfo root = view.createAccessibilityNodeInfo();
+                if (root != null) {
+                    outInfos.add(root);
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
+                        prefetchPredecessorsOfRealNode(view, outInfos);
+                    }
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
+                        prefetchSiblingsOfRealNode(view, outInfos);
+                    }
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
+                        prefetchDescendantsOfRealNode(view, outInfos);
+                    }
+                }
+            } else {
+                AccessibilityNodeInfo root = provider.createAccessibilityNodeInfo(virtualViewId);
+                if (root != null) {
+                    outInfos.add(root);
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
+                        prefetchPredecessorsOfVirtualNode(root, view, provider, outInfos);
+                    }
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
+                        prefetchSiblingsOfVirtualNode(root, view, provider, outInfos);
+                    }
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
+                        prefetchDescendantsOfVirtualNode(root, provider, outInfos);
+                    }
+                }
+            }
+        }
+
+        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;
+                final long parentNodeId = AccessibilityNodeInfo.makeNodeId(
+                        parentView.getAccessibilityViewId(), AccessibilityNodeInfo.UNDEFINED);
+                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;
+                ChildListForAccessibility children = ChildListForAccessibility.obtain(parentGroup,
+                        false);
+                final int childCount = children.getChildCount();
+                for (int i = 0; i < childCount; i++) {
+                    if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                        children.recycle();
+                        return;
+                    }
+                    View child = children.getChildAt(i);
+                    if (child.getAccessibilityViewId() != current.getAccessibilityViewId()
+                            &&  isDisplayedOnScreen(child)) {
+                        AccessibilityNodeInfo info = null;
+                        AccessibilityNodeProvider provider = child.getAccessibilityNodeProvider();
+                        if (provider == null) {
+                            info = child.createAccessibilityNodeInfo();
+                        } else {
+                            info = provider.createAccessibilityNodeInfo(
+                                    AccessibilityNodeInfo.UNDEFINED);
+                        }
+                        if (info != null) {
+                            outInfos.add(info);
+                        }
+                    }
+                }
+                children.recycle();
+            }
+        }
+
+        private void prefetchDescendantsOfRealNode(View root,
+                List<AccessibilityNodeInfo> outInfos) {
+            if (!(root instanceof ViewGroup)) {
+                return;
+            }
+            ViewGroup rootGroup = (ViewGroup) root;
+            HashMap<View, AccessibilityNodeInfo> addedChildren =
+                new HashMap<View, AccessibilityNodeInfo>();
+            ChildListForAccessibility children = ChildListForAccessibility.obtain(rootGroup, false);
+            final int childCount = children.getChildCount();
+            for (int i = 0; i < childCount; i++) {
+                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                    children.recycle();
+                    return;
+                }
+                View child = children.getChildAt(i);
+                if ( isDisplayedOnScreen(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(
+                               AccessibilityNodeInfo.UNDEFINED);
+                        if (info != null) {
+                            outInfos.add(info);
+                            addedChildren.put(child, info);
+                        }
+                    }
+                }
+            }
+            children.recycle();
+            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) {
+            long parentNodeId = root.getParentNodeId();
+            int accessibilityViewId = AccessibilityNodeInfo.getAccessibilityViewId(parentNodeId);
+            while (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                    return;
+                }
+                final int virtualDescendantId =
+                    AccessibilityNodeInfo.getVirtualDescendantId(parentNodeId);
+                if (virtualDescendantId != AccessibilityNodeInfo.UNDEFINED
+                        || accessibilityViewId == providerHost.getAccessibilityViewId()) {
+                    AccessibilityNodeInfo parent = provider.createAccessibilityNodeInfo(
+                            virtualDescendantId);
+                    if (parent != null) {
+                        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 != AccessibilityNodeInfo.UNDEFINED
+                    || parentAccessibilityViewId == providerHost.getAccessibilityViewId()) {
+                AccessibilityNodeInfo parent =
+                    provider.createAccessibilityNodeInfo(parentVirtualDescendantId);
+                if (parent != null) {
+                    SparseLongArray childNodeIds = parent.getChildNodeIds();
+                    final int childCount = childNodeIds.size();
+                    for (int i = 0; i < childCount; i++) {
+                        if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                            return;
+                        }
+                        final long childNodeId = childNodeIds.get(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) {
+            SparseLongArray childNodeIds = root.getChildNodeIds();
+            final int initialOutInfosSize = outInfos.size();
+            final int childCount = childNodeIds.size();
+            for (int i = 0; i < childCount; i++) {
+                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                    return;
+                }
+                final long childNodeId = childNodeIds.get(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 final static int MSG_PERFORM_ACCESSIBILITY_ACTION = 1;
+        private final static int MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_ACCESSIBILITY_ID = 2;
+        private final static int MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_VIEW_ID = 3;
+        private final static int MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_TEXT = 4;
+        private final static int MSG_FIND_FOCUS = 5;
+        private final static int MSG_FOCUS_SEARCH = 6;
+
+        public PrivateHandler() {
+            super(Looper.getMainLooper());
+        }
+
+        @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_ACCESSIBLITY_NODE_INFO_BY_ACCESSIBILITY_ID:
+                    return "MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_ACCESSIBILITY_ID";
+                case MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_VIEW_ID:
+                    return "MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_VIEW_ID";
+                case MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_TEXT:
+                    return "MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_TEXT";
+                case MSG_FIND_FOCUS:
+                    return "MSG_FIND_FOCUS";
+                case MSG_FOCUS_SEARCH:
+                    return "MSG_FOCUS_SEARCH";
+                default:
+                    throw new IllegalArgumentException("Unknown message type: " + type);
+            }
+        }
+
+        @Override
+        public void handleMessage(Message message) {
+            final int type = message.what;
+            switch (type) {
+                case MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_ACCESSIBILITY_ID: {
+                    findAccessibilityNodeInfoByAccessibilityIdUiThread(message);
+                } break;
+                case MSG_PERFORM_ACCESSIBILITY_ACTION: {
+                    perfromAccessibilityActionUiThread(message);
+                } break;
+                case MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_VIEW_ID: {
+                    findAccessibilityNodeInfoByViewIdUiThread(message);
+                } break;
+                case MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_TEXT: {
+                    findAccessibilityNodeInfosByTextUiThread(message);
+                } break;
+                case MSG_FIND_FOCUS: {
+                    findFocusUiThread(message);
+                } break;
+                case MSG_FOCUS_SEARCH: {
+                    focusSearchUiThread(message);
+                } break;
+                default:
+                    throw new IllegalArgumentException("Unknown message type: " + type);
+            }
+        }
+    }
+}