Merge "Fixing issues with the AccessibilityNodeInfo cache."

9 files changed, 310 insertions, 176 deletions

diff --git a/core/java/android/accessibilityservice/IAccessibilityServiceConnection.aidl b/core/java/android/accessibilityservice/IAccessibilityServiceConnection.aidl
index 882dd6bd5503..8d17325fe065 100644
--- a/core/java/android/accessibilityservice/IAccessibilityServiceConnection.aidl
+++ b/core/java/android/accessibilityservice/IAccessibilityServiceConnection.aidl
@@ -42,11 +42,12 @@ interface IAccessibilityServiceConnection {
      * @param interactionId The id of the interaction for matching with the callback result.
      * @param callback Callback which to receive the result.
      * @param threadId The id of the calling thread.
+     * @param prefetchFlags flags to guide prefetching.
      * @return The current window scale, where zero means a failure.
      */
     float findAccessibilityNodeInfoByAccessibilityId(int accessibilityWindowId,
         long accessibilityNodeId, int interactionId,
-        IAccessibilityInteractionConnectionCallback callback, long threadId);
+        IAccessibilityInteractionConnectionCallback callback, long threadId, int prefetchFlags);
 
     /**
      * Finds {@link android.view.accessibility.AccessibilityNodeInfo}s by View text.
diff --git a/core/java/android/accessibilityservice/UiTestAutomationBridge.java b/core/java/android/accessibilityservice/UiTestAutomationBridge.java
index 334981a10d19..9b3da53a6701 100644
--- a/core/java/android/accessibilityservice/UiTestAutomationBridge.java
+++ b/core/java/android/accessibilityservice/UiTestAutomationBridge.java
@@ -57,6 +57,11 @@ public class UiTestAutomationBridge {
 
     public static final int UNDEFINED = -1;
 
+    private static final int FIND_ACCESSIBILITY_NODE_INFO_PREFETCH_FLAGS =
+        AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS
+        | AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS
+        | AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS;
+
     private final Object mLock = new Object();
 
     private volatile int mConnectionId = AccessibilityInteractionClient.NO_ID;
@@ -351,13 +356,15 @@ public class UiTestAutomationBridge {
         ensureValidConnection(connectionId);
         return AccessibilityInteractionClient.getInstance()
                 .findAccessibilityNodeInfoByAccessibilityId(mConnectionId,
-                        accessibilityWindowId, accessibilityNodeId);
+                        accessibilityWindowId, accessibilityNodeId,
+                        FIND_ACCESSIBILITY_NODE_INFO_PREFETCH_FLAGS);
     }
 
     /**
      * Finds an {@link AccessibilityNodeInfo} by View id in the active
      * window. The search is performed from the root node.
      *
+     * @param viewId The id of a View.
      * @return The current window scale, where zero means a failure.
      */
     public AccessibilityNodeInfo findAccessibilityNodeInfoByViewIdInActiveWindow(int viewId) {
@@ -373,6 +380,7 @@ public class UiTestAutomationBridge {
      *     {@link  #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  #ROOT_NODE_ID} to start from the root.
+     * @param viewId The id of a View.
      * @return The current window scale, where zero means a failure.
      */
     public AccessibilityNodeInfo findAccessibilityNodeInfoByViewId(int accessibilityWindowId,
@@ -460,7 +468,7 @@ public class UiTestAutomationBridge {
         ensureValidConnection(connectionId);
         return AccessibilityInteractionClient.getInstance()
                 .findAccessibilityNodeInfoByAccessibilityId(connectionId, ACTIVE_WINDOW_ID,
-                        ROOT_NODE_ID);
+                        ROOT_NODE_ID, AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS);
     }
 
     private void ensureValidConnection(int connectionId) {
diff --git a/core/java/android/view/ViewRootImpl.java b/core/java/android/view/ViewRootImpl.java
index f831d85f70f2..31d874f6a75c 100644
--- a/core/java/android/view/ViewRootImpl.java
+++ b/core/java/android/view/ViewRootImpl.java
@@ -54,12 +54,12 @@ import android.util.AndroidRuntimeException;
 import android.util.DisplayMetrics;
 import android.util.EventLog;
 import android.util.Log;
-import android.util.LongSparseArray;
 import android.util.Pool;
 import android.util.Poolable;
 import android.util.PoolableManager;
 import android.util.Pools;
 import android.util.Slog;
+import android.util.SparseLongArray;
 import android.util.TypedValue;
 import android.view.View.AttachInfo;
 import android.view.View.MeasureSpec;
@@ -87,7 +87,9 @@ import java.io.IOException;
 import java.io.OutputStream;
 import java.lang.ref.WeakReference;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 
 /**
  * The top of a view hierarchy, implementing the needed protocol between View
@@ -309,7 +311,7 @@ public final class ViewRootImpl implements ViewParent,
 
     SendWindowContentChangedAccessibilityEvent mSendWindowContentChangedAccessibilityEvent;
 
-    AccessibilityPrefetchStrategy mAccessibilityPrefetchStrategy;
+    AccessibilityNodePrefetcher mAccessibilityNodePrefetcher;
 
     private final int mDensity;
 
@@ -379,8 +381,6 @@ public final class ViewRootImpl implements ViewParent,
         mAccessibilityManager = AccessibilityManager.getInstance(context);
         mAccessibilityInteractionConnectionManager =
             new AccessibilityInteractionConnectionManager();
-        mAccessibilityManager.addAccessibilityStateChangeListener(
-                mAccessibilityInteractionConnectionManager);
         mAttachInfo = new View.AttachInfo(sWindowSession, mWindow, this, mHandler, this);
         mViewConfiguration = ViewConfiguration.get(context);
         mDensity = context.getResources().getDisplayMetrics().densityDpi;
@@ -3564,15 +3564,15 @@ public final class ViewRootImpl implements ViewParent,
         return mAccessibilityInteractionController;
     }
 
-    public AccessibilityPrefetchStrategy getAccessibilityPrefetchStrategy() {
+    public AccessibilityNodePrefetcher getAccessibilityNodePrefetcher() {
         if (mView == null) {
-            throw new IllegalStateException("getAccessibilityPrefetchStrategy"
+            throw new IllegalStateException("getAccessibilityNodePrefetcher"
                     + " called when there is no mView");
         }
-        if (mAccessibilityPrefetchStrategy == null) {
-            mAccessibilityPrefetchStrategy = new AccessibilityPrefetchStrategy();
+        if (mAccessibilityNodePrefetcher == null) {
+            mAccessibilityNodePrefetcher = new AccessibilityNodePrefetcher();
         }
-        return mAccessibilityPrefetchStrategy;
+        return mAccessibilityNodePrefetcher;
     }
 
     private int relayoutWindow(WindowManager.LayoutParams params, int viewVisibility,
@@ -4118,7 +4118,6 @@ public final class ViewRootImpl implements ViewParent,
         if (mView == null) {
             return false;
         }
-        getAccessibilityPrefetchStrategy().onAccessibilityEvent(event);
         mAccessibilityManager.sendAccessibilityEvent(event);
         return true;
     }
@@ -4690,12 +4689,12 @@ public final class ViewRootImpl implements ViewParent,
 
         public void findAccessibilityNodeInfoByAccessibilityId(long accessibilityNodeId,
                 int interactionId, IAccessibilityInteractionConnectionCallback callback,
-                int interrogatingPid, long interrogatingTid) {
+                int prefetchFlags, int interrogatingPid, long interrogatingTid) {
             ViewRootImpl viewRootImpl = mViewRootImpl.get();
             if (viewRootImpl != null && viewRootImpl.mView != null) {
                 viewRootImpl.getAccessibilityInteractionController()
                     .findAccessibilityNodeInfoByAccessibilityIdClientThread(accessibilityNodeId,
-                        interactionId, callback, interrogatingPid, interrogatingTid);
+                        interactionId, callback, prefetchFlags, interrogatingPid, interrogatingTid);
             } else {
                 // We cannot make the call and notify the caller so it does not wait.
                 try {
@@ -4830,11 +4829,11 @@ public final class ViewRootImpl implements ViewParent,
 
         public void findAccessibilityNodeInfoByAccessibilityIdClientThread(
                 long accessibilityNodeId, int interactionId,
-                IAccessibilityInteractionConnectionCallback callback, int interrogatingPid,
-                long interrogatingTid) {
+                IAccessibilityInteractionConnectionCallback callback, int prefetchFlags,
+                int interrogatingPid, long interrogatingTid) {
             Message message = mHandler.obtainMessage();
             message.what = MSG_FIND_ACCESSIBLITY_NODE_INFO_BY_ACCESSIBILITY_ID;
-            message.arg1 = interrogatingPid;
+            message.arg1 = prefetchFlags;
             SomeArgs args = mPool.acquire();
             args.argi1 = AccessibilityNodeInfo.getAccessibilityViewId(accessibilityNodeId);
             args.argi2 = AccessibilityNodeInfo.getVirtualDescendantId(accessibilityNodeId);
@@ -4855,8 +4854,8 @@ public final class ViewRootImpl implements ViewParent,
         }
 
         public void findAccessibilityNodeInfoByAccessibilityIdUiThread(Message message) {
+            final int prefetchFlags = message.arg1;
             SomeArgs args = (SomeArgs) message.obj;
-            final int interrogatingPid = message.arg1;
             final int accessibilityViewId = args.argi1;
             final int virtualDescendantId = args.argi2;
             final int interactionId = args.argi3;
@@ -4866,22 +4865,15 @@ public final class ViewRootImpl implements ViewParent,
             List<AccessibilityNodeInfo> infos = mTempAccessibilityNodeInfoList;
             infos.clear();
             try {
+                View target = null;
                 if (accessibilityViewId == AccessibilityNodeInfo.UNDEFINED) {
-                    View target = ViewRootImpl.this.mView;
-                    if (target != null && target.getVisibility() == View.VISIBLE) {
-                        infos.add(target.createAccessibilityNodeInfo());
-                    }
+                    target = ViewRootImpl.this.mView;
                 } else {
-                    View target = findViewByAccessibilityId(accessibilityViewId);
-                    if (target != null && target.getVisibility() == View.VISIBLE) {
-                        AccessibilityNodeProvider provider = target.getAccessibilityNodeProvider();
-                        if (provider != null) {
-                            infos.add(provider.createAccessibilityNodeInfo(virtualDescendantId));
-                        } else if (virtualDescendantId == AccessibilityNodeInfo.UNDEFINED) {
-                            getAccessibilityPrefetchStrategy().prefetchAccessibilityNodeInfos(
-                                    interrogatingPid, target, infos);
-                        }
-                    }
+                    target = findViewByAccessibilityId(accessibilityViewId);
+                }
+                if (target != null && target.getVisibility() == View.VISIBLE) {
+                    getAccessibilityNodePrefetcher().prefetchAccessibilityNodeInfos(target,
+                            virtualDescendantId, prefetchFlags, infos);
                 }
             } finally {
                 try {
@@ -5142,83 +5134,216 @@ public final class ViewRootImpl implements ViewParent,
 
     /**
      * 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. It caches
-     * the ids of the prefeteched nodes such that they are fetched only once.
+     * querying window content. It is responsible to prefetch a batch of
+     * AccessibilityNodeInfos in addition to the one for a requested node.
      */
-    class AccessibilityPrefetchStrategy {
-        private static final int MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE = 100;
+    class AccessibilityNodePrefetcher {
 
-        // We need to keep track of what we have sent for each interrogating
-        // process. Usually there will be only one such process but we
-        // should support the general case. Note that the accessibility event
-        // stream will take care of clearing caches of querying processes that
-        // are not longer alive, so we do not waste memory.
-        private final LongSparseArray<AccessibilityNodeInfoCache> mAccessibilityNodeInfoCaches =
-            new LongSparseArray<AccessibilityNodeInfoCache>();
+        private static final int MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE = 50;
 
-        private AccessibilityNodeInfoCache getCacheForInterrogatingPid(long interrogatingPid) {
-            AccessibilityNodeInfoCache cache = mAccessibilityNodeInfoCaches.get(interrogatingPid);
-            if (cache == null) {
-                cache = AccessibilityNodeInfoCache.newAccessibilityNodeInfoCache();
-                mAccessibilityNodeInfoCaches.put(interrogatingPid, cache);
+        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);
+                    }
+                }
             }
-            return cache;
         }
 
-        public void onAccessibilityEvent(AccessibilityEvent event) {
-            final int cacheCount = mAccessibilityNodeInfoCaches.size();
-            for (int i = 0; i < cacheCount; i++) {
-                AccessibilityNodeInfoCache cache = mAccessibilityNodeInfoCaches.valueAt(i);
-                cache.onAccessibilityEvent(event);
+        private void prefetchPredecessorsOfRealNode(View view,
+                List<AccessibilityNodeInfo> outInfos) {
+            ViewParent parent = view.getParent();
+            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.getParent();
             }
         }
 
-        public void prefetchAccessibilityNodeInfos(long interrogatingPid, View root,
+        private void prefetchSiblingsOfRealNode(View current,
                 List<AccessibilityNodeInfo> outInfos) {
-            addAndCacheNotCachedNodeInfo(interrogatingPid, root, outInfos);
-            addAndCacheNotCachedPredecessorInfos(interrogatingPid, root, outInfos);
-            addAndCacheNotCachedDescendantInfos(interrogatingPid, root, outInfos);
+            ViewParent parent = current.getParent();
+            if (parent instanceof ViewGroup) {
+                ViewGroup parentGroup = (ViewGroup) parent;
+                final int childCount = parentGroup.getChildCount();
+                for (int i = 0; i < childCount; i++) {
+                    View child = parentGroup.getChildAt(i);
+                    if (outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE
+                            && child.getAccessibilityViewId() != current.getAccessibilityViewId()
+                            && child.getVisibility() == View.VISIBLE) {
+                        final long childNodeId = AccessibilityNodeInfo.makeNodeId(
+                                child.getAccessibilityViewId(), AccessibilityNodeInfo.UNDEFINED);
+                        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);
+                        }
+                    }
+                }
+            }
         }
 
-        private void addAndCacheNotCachedNodeInfo(long interrogatingPid,
-                View view, List<AccessibilityNodeInfo> outInfos) {
-            final long accessibilityNodeId = AccessibilityNodeInfo.makeNodeId(
-                    view.getAccessibilityViewId(), AccessibilityNodeInfo.UNDEFINED);
-            AccessibilityNodeInfoCache cache = getCacheForInterrogatingPid(interrogatingPid);
-            if (!cache.containsKey(accessibilityNodeId)) {
-                // Account for the ids of the fetched infos. The infos will be
-                // cached in the window querying process. We just need to know
-                // which infos are cached to avoid fetching a cached one again.
-                cache.put(accessibilityNodeId, null);
-                outInfos.add(view.createAccessibilityNodeInfo());
+        private void prefetchDescendantsOfRealNode(View root,
+                List<AccessibilityNodeInfo> outInfos) {
+            if (root instanceof ViewGroup) {
+                ViewGroup rootGroup = (ViewGroup) root;
+                HashMap<View, AccessibilityNodeInfo> addedChildren =
+                    new HashMap<View, AccessibilityNodeInfo>();
+                final int childCount = rootGroup.getChildCount();
+                for (int i = 0; i < childCount; i++) {
+                    View child = rootGroup.getChildAt(i);
+                    if (child.getVisibility() == View.VISIBLE
+                            && outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                        final long childNodeId = AccessibilityNodeInfo.makeNodeId(
+                                child.getAccessibilityViewId(), AccessibilityNodeInfo.UNDEFINED);
+                        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);
+                            }
+                        }
+                    }
+                }
+                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 addAndCacheNotCachedPredecessorInfos(long interrogatingPid, View view,
+        private void prefetchPredecessorsOfVirtualNode(AccessibilityNodeInfo root,
+                View providerHost, AccessibilityNodeProvider provider,
                 List<AccessibilityNodeInfo> outInfos) {
-            ViewParent predecessor = view.getParent();
-            while (predecessor instanceof View
-                    && outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
-                View predecessorView = (View) predecessor;
-                addAndCacheNotCachedNodeInfo(interrogatingPid, predecessorView, outInfos);
-                predecessor = predecessor.getParent();
+            long parentNodeId = root.getParentNodeId();
+            int accessibilityViewId = AccessibilityNodeInfo.getAccessibilityViewId(parentNodeId);
+            while (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED) {
+                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 addAndCacheNotCachedDescendantInfos(long interrogatingPid, View view,
-                List<AccessibilityNodeInfo> outInfos) {
-            if (outInfos.size() > MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE
-                    || view.getAccessibilityNodeProvider() != null) {
-                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++) {
+                        final long childNodeId = childNodeIds.get(i);
+                        if (childNodeId != current.getSourceNodeId()
+                                && outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                            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) {
+                    final long childNodeId = childNodeIds.get(i);
+                    AccessibilityNodeInfo child = provider.createAccessibilityNodeInfo(
+                            AccessibilityNodeInfo.getVirtualDescendantId(childNodeId));
+                    if (child != null) {
+                        outInfos.add(child);
+                    }
+                }
             }
-            addAndCacheNotCachedNodeInfo(interrogatingPid, view, outInfos);
-            if (view instanceof ViewGroup) {
-                ViewGroup rootGroup = (ViewGroup) view;
-                final int childCount = rootGroup.getChildCount();
-                for (int i = 0; i < childCount; i++) {
-                View child = rootGroup.getChildAt(i);
-                    addAndCacheNotCachedDescendantInfos(interrogatingPid, child, outInfos);
+            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);
                 }
             }
         }
diff --git a/core/java/android/view/accessibility/AccessibilityInteractionClient.java b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
index 105c010d4be9..be74b312c1ea 100644
--- a/core/java/android/view/accessibility/AccessibilityInteractionClient.java
+++ b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
@@ -24,7 +24,6 @@ import android.os.SystemClock;
 import android.util.Log;
 import android.util.LongSparseArray;
 import android.util.SparseArray;
-import android.view.AccessibilityNodeInfoCache;
 
 import java.util.ArrayList;
 import java.util.Collections;
@@ -102,7 +101,7 @@ public final class AccessibilityInteractionClient
     // The connection cache is shared between all interrogating threads since
     // at any given time there is only one window allowing querying.
     private static final AccessibilityNodeInfoCache sAccessibilityNodeInfoCache =
-        AccessibilityNodeInfoCache.newSynchronizedAccessibilityNodeInfoCache();
+        new AccessibilityNodeInfoCache();
 
     /**
      * @return The client for the current thread.
@@ -159,10 +158,11 @@ public final class AccessibilityInteractionClient
      *     where to start the search. Use
      *     {@link android.view.accessibility.AccessibilityNodeInfo#ROOT_NODE_ID}
      *     to start from the root.
+     * @param prefetchFlags flags to guide prefetching.
      * @return An {@link AccessibilityNodeInfo} if found, null otherwise.
      */
     public AccessibilityNodeInfo findAccessibilityNodeInfoByAccessibilityId(int connectionId,
-            int accessibilityWindowId, long accessibilityNodeId) {
+            int accessibilityWindowId, long accessibilityNodeId, int prefetchFlags) {
         try {
             IAccessibilityServiceConnection connection = getConnection(connectionId);
             if (connection != null) {
@@ -174,7 +174,7 @@ public final class AccessibilityInteractionClient
                 final int interactionId = mInteractionIdCounter.getAndIncrement();
                 final float windowScale = connection.findAccessibilityNodeInfoByAccessibilityId(
                         accessibilityWindowId, accessibilityNodeId, interactionId, this,
-                        Thread.currentThread().getId());
+                        Thread.currentThread().getId(), prefetchFlags);
                 // If the scale is zero the call has failed.
                 if (windowScale > 0) {
                     List<AccessibilityNodeInfo> infos = getFindAccessibilityNodeInfosResultAndClear(
diff --git a/core/java/android/view/accessibility/AccessibilityNodeInfo.java b/core/java/android/view/accessibility/AccessibilityNodeInfo.java
index 84ad268f59e1..c094fda58a46 100644
--- a/core/java/android/view/accessibility/AccessibilityNodeInfo.java
+++ b/core/java/android/view/accessibility/AccessibilityNodeInfo.java
@@ -61,6 +61,15 @@ public class AccessibilityNodeInfo implements Parcelable {
     /** @hide */
     public static final int ACTIVE_WINDOW_ID = UNDEFINED;
 
+    /** @hide */
+    public static final int FLAG_PREFETCH_PREDECESSORS = 0x00000001;
+
+    /** @hide */
+    public static final int FLAG_PREFETCH_SIBLINGS = 0x00000002;
+
+    /** @hide */
+    public static final int FLAG_PREFETCH_DESCENDANTS = 0x00000003;
+
     // Actions.
 
     /**
@@ -181,7 +190,7 @@ public class AccessibilityNodeInfo implements Parcelable {
     private CharSequence mText;
     private CharSequence mContentDescription;
 
-    private SparseLongArray mChildIds = new SparseLongArray();
+    private SparseLongArray mChildNodeIds = new SparseLongArray();
     private int mActions;
 
     private int mConnectionId = UNDEFINED;
@@ -244,12 +253,21 @@ public class AccessibilityNodeInfo implements Parcelable {
     }
 
     /**
+     * @return The ids of the children.
+     *
+     * @hide
+     */
+    public SparseLongArray getChildNodeIds() {
+        return mChildNodeIds;
+    }
+
+    /**
      * Gets the number of children.
      *
      * @return The child count.
      */
     public int getChildCount() {
-        return mChildIds.size();
+        return mChildNodeIds.size();
     }
 
     /**
@@ -271,9 +289,10 @@ public class AccessibilityNodeInfo implements Parcelable {
         if (!canPerformRequestOverConnection(mSourceNodeId)) {
             return null;
         }
-        final long childId = mChildIds.get(index);
+        final long childId = mChildNodeIds.get(index);
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
-        return client.findAccessibilityNodeInfoByAccessibilityId(mConnectionId, mWindowId, childId);
+        return client.findAccessibilityNodeInfoByAccessibilityId(mConnectionId, mWindowId,
+                childId, FLAG_PREFETCH_DESCENDANTS);
     }
 
     /**
@@ -308,11 +327,11 @@ public class AccessibilityNodeInfo implements Parcelable {
      */
     public void addChild(View root, int virtualDescendantId) {
         enforceNotSealed();
-        final int index = mChildIds.size();
+        final int index = mChildNodeIds.size();
         final int rootAccessibilityViewId =
             (root != null) ? root.getAccessibilityViewId() : UNDEFINED;
         final long childNodeId = makeNodeId(rootAccessibilityViewId, virtualDescendantId);
-        mChildIds.put(index, childNodeId);
+        mChildNodeIds.put(index, childNodeId);
     }
 
     /**
@@ -408,7 +427,16 @@ public class AccessibilityNodeInfo implements Parcelable {
         }
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
         return client.findAccessibilityNodeInfoByAccessibilityId(mConnectionId,
-                mWindowId, mParentNodeId);
+                mWindowId, mParentNodeId, FLAG_PREFETCH_DESCENDANTS | FLAG_PREFETCH_SIBLINGS);
+    }
+
+    /**
+     * @return The parent node id.
+     *
+     * @hide
+     */
+    public long getParentNodeId() {
+        return mParentNodeId;
     }
 
     /**
@@ -1070,7 +1098,7 @@ public class AccessibilityNodeInfo implements Parcelable {
         parcel.writeLong(mParentNodeId);
         parcel.writeInt(mConnectionId);
 
-        SparseLongArray childIds = mChildIds;
+        SparseLongArray childIds = mChildNodeIds;
         final int childIdsSize = childIds.size();
         parcel.writeInt(childIdsSize);
         for (int i = 0; i < childIdsSize; i++) {
@@ -1120,7 +1148,7 @@ public class AccessibilityNodeInfo implements Parcelable {
         mContentDescription = other.mContentDescription;
         mActions= other.mActions;
         mBooleanProperties = other.mBooleanProperties;
-        mChildIds = other.mChildIds.clone();
+        mChildNodeIds = other.mChildNodeIds.clone();
     }
 
     /**
@@ -1135,7 +1163,7 @@ public class AccessibilityNodeInfo implements Parcelable {
         mParentNodeId = parcel.readLong();
         mConnectionId = parcel.readInt();
 
-        SparseLongArray childIds = mChildIds;
+        SparseLongArray childIds = mChildNodeIds;
         final int childrenSize = parcel.readInt();
         for (int i = 0; i < childrenSize; i++) {
             final long childId = parcel.readLong();
@@ -1171,7 +1199,7 @@ public class AccessibilityNodeInfo implements Parcelable {
         mParentNodeId = ROOT_NODE_ID;
         mWindowId = UNDEFINED;
         mConnectionId = UNDEFINED;
-        mChildIds.clear();
+        mChildNodeIds.clear();
         mBoundsInParent.set(0, 0, 0, 0);
         mBoundsInScreen.set(0, 0, 0, 0);
         mBooleanProperties = 0;
@@ -1249,7 +1277,7 @@ public class AccessibilityNodeInfo implements Parcelable {
             builder.append("; accessibilityViewId: " + getAccessibilityViewId(mSourceNodeId));
             builder.append("; virtualDescendantId: " + getVirtualDescendantId(mSourceNodeId));
             builder.append("; mParentNodeId: " + mParentNodeId);
-            SparseLongArray childIds = mChildIds;
+            SparseLongArray childIds = mChildNodeIds;
             builder.append("; childAccessibilityIds: [");
             for (int i = 0, count = childIds.size(); i < count; i++) {
                 builder.append(childIds.valueAt(i));
diff --git a/core/java/android/view/AccessibilityNodeInfoCache.java b/core/java/android/view/accessibility/AccessibilityNodeInfoCache.java
index 84b510d8c7ef..4fb0046ffe12 100644
--- a/core/java/android/view/AccessibilityNodeInfoCache.java
+++ b/core/java/android/view/accessibility/AccessibilityNodeInfoCache.java
@@ -14,13 +14,11 @@
  * limitations under the License.
  */
 
-package android.view;
+package android.view.accessibility;
 
 import android.os.Process;
 import android.util.Log;
 import android.util.LongSparseArray;
-import android.view.accessibility.AccessibilityEvent;
-import android.view.accessibility.AccessibilityNodeInfo;
 
 /**
  * Simple cache for AccessibilityNodeInfos. The cache is mapping an
@@ -38,53 +36,11 @@ public class AccessibilityNodeInfoCache {
 
     private static final boolean DEBUG = false;
 
-    /**
-     * @return A new <strong>not synchronized</strong> AccessibilityNodeInfoCache.
-     */
-    public static AccessibilityNodeInfoCache newAccessibilityNodeInfoCache() {
-        return new AccessibilityNodeInfoCache();
-    }
-
-    /**
-     * @return A new <strong>synchronized</strong> AccessibilityNodeInfoCache.
-     */
-    public static AccessibilityNodeInfoCache newSynchronizedAccessibilityNodeInfoCache() {
-        return new AccessibilityNodeInfoCache() {
-            private final Object mLock = new Object();
-
-            @Override
-            public void clear() {
-                synchronized(mLock) {
-                    super.clear();
-                }
-            }
-
-            @Override
-            public AccessibilityNodeInfo get(long accessibilityNodeId) {
-                synchronized(mLock) {
-                    return super.get(accessibilityNodeId);
-                }
-            }
-
-            @Override
-            public void put(long accessibilityNodeId, AccessibilityNodeInfo info) {
-                synchronized(mLock) {
-                   super.put(accessibilityNodeId, info);
-                }
-            }
-
-            @Override
-            public void remove(long accessibilityNodeId) {
-                synchronized(mLock) {
-                   super.remove(accessibilityNodeId);
-                }
-            }
-        };
-    }
+    private final Object mLock = new Object();
 
     private final LongSparseArray<AccessibilityNodeInfo> mCacheImpl;
 
-    private AccessibilityNodeInfoCache() {
+    public AccessibilityNodeInfoCache() {
         if (ENABLED) {
             mCacheImpl = new LongSparseArray<AccessibilityNodeInfo>();
         } else {
@@ -124,13 +80,15 @@ public class AccessibilityNodeInfoCache {
      */
     public AccessibilityNodeInfo get(long accessibilityNodeId) {
         if (ENABLED) {
-            if (DEBUG) {
-                AccessibilityNodeInfo info = mCacheImpl.get(accessibilityNodeId);
-                Log.i(LOG_TAG, "Process: " + Process.myPid() +
-                        " get(" + accessibilityNodeId + ") = " + info);
-                return info;
-            } else {
-                return mCacheImpl.get(accessibilityNodeId);
+            synchronized(mLock) {
+                if (DEBUG) {
+                    AccessibilityNodeInfo info = mCacheImpl.get(accessibilityNodeId);
+                    Log.i(LOG_TAG, "Process: " + Process.myPid() +
+                            " get(" + accessibilityNodeId + ") = " + info);
+                    return info;
+                } else {
+                    return mCacheImpl.get(accessibilityNodeId);
+                }
             }
         } else {
             return null;
@@ -145,11 +103,13 @@ public class AccessibilityNodeInfoCache {
      */
     public void put(long accessibilityNodeId, AccessibilityNodeInfo info) {
         if (ENABLED) {
-            if (DEBUG) {
-                Log.i(LOG_TAG, "Process: " + Process.myPid()
-                        + " put(" + accessibilityNodeId + ", " + info + ")");
+            synchronized(mLock) {
+                if (DEBUG) {
+                    Log.i(LOG_TAG, "Process: " + Process.myPid()
+                            + " put(" + accessibilityNodeId + ", " + info + ")");
+                }
+                mCacheImpl.put(accessibilityNodeId, info);
             }
-            mCacheImpl.put(accessibilityNodeId, info);
         }
     }
 
@@ -161,7 +121,9 @@ public class AccessibilityNodeInfoCache {
      */
     public boolean containsKey(long accessibilityNodeId) {
         if (ENABLED) {
-            return (mCacheImpl.indexOfKey(accessibilityNodeId) >= 0);
+            synchronized(mLock) {
+                return (mCacheImpl.indexOfKey(accessibilityNodeId) >= 0);
+            }
         } else {
             return false;
         }
@@ -174,11 +136,13 @@ public class AccessibilityNodeInfoCache {
      */
     public void remove(long accessibilityNodeId) {
         if (ENABLED) {
-            if (DEBUG) {
-                Log.i(LOG_TAG,  "Process: " + Process.myPid()
-                        + " remove(" + accessibilityNodeId + ")");
+            synchronized(mLock) {
+                if (DEBUG) {
+                    Log.i(LOG_TAG,  "Process: " + Process.myPid()
+                            + " remove(" + accessibilityNodeId + ")");
+                }
+                mCacheImpl.remove(accessibilityNodeId);
             }
-            mCacheImpl.remove(accessibilityNodeId);
         }
     }
 
@@ -187,10 +151,12 @@ public class AccessibilityNodeInfoCache {
      */
     public void clear() {
         if (ENABLED) {
-            if (DEBUG) {
-                Log.i(LOG_TAG,  "Process: " + Process.myPid() + "clear()");
+            synchronized(mLock) {
+                if (DEBUG) {
+                    Log.i(LOG_TAG,  "Process: " + Process.myPid() + "clear()");
+                }
+                mCacheImpl.clear();
             }
-            mCacheImpl.clear();
         }
     }
 }
diff --git a/core/java/android/view/accessibility/AccessibilityRecord.java b/core/java/android/view/accessibility/AccessibilityRecord.java
index b60f50eb5d9d..23b235cbe395 100644
--- a/core/java/android/view/accessibility/AccessibilityRecord.java
+++ b/core/java/android/view/accessibility/AccessibilityRecord.java
@@ -56,6 +56,11 @@ public class AccessibilityRecord {
     private static final int PROPERTY_FULL_SCREEN = 0x00000080;
     private static final int PROPERTY_SCROLLABLE = 0x00000100;
 
+    private static final int GET_SOURCE_PREFETCH_FLAGS =
+        AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS
+        | AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS
+        | AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS;
+
     // Housekeeping
     private static final int MAX_POOL_SIZE = 10;
     private static final Object sPoolLock = new Object();
@@ -144,7 +149,7 @@ public class AccessibilityRecord {
         }
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
         return client.findAccessibilityNodeInfoByAccessibilityId(mConnectionId, mSourceWindowId,
-                mSourceNodeId);
+                mSourceNodeId, GET_SOURCE_PREFETCH_FLAGS);
     }
 
     /**
diff --git a/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl b/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl
index ae6869cad9f5..fc3651c6451f 100644
--- a/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl
+++ b/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl
@@ -28,7 +28,7 @@ import android.view.accessibility.IAccessibilityInteractionConnectionCallback;
 oneway interface IAccessibilityInteractionConnection {
 
     void findAccessibilityNodeInfoByAccessibilityId(long accessibilityNodeId, int interactionId,
-        IAccessibilityInteractionConnectionCallback callback,
+        IAccessibilityInteractionConnectionCallback callback, int prefetchFlags,
         int interrogatingPid, long interrogatingTid);
 
     void findAccessibilityNodeInfoByViewId(long accessibilityNodeId, int id, int interactionId,
diff --git a/services/java/com/android/server/accessibility/AccessibilityManagerService.java b/services/java/com/android/server/accessibility/AccessibilityManagerService.java
index 455325af5156..c99aa026cf52 100644
--- a/services/java/com/android/server/accessibility/AccessibilityManagerService.java
+++ b/services/java/com/android/server/accessibility/AccessibilityManagerService.java
@@ -1129,7 +1129,8 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub
 
         public float findAccessibilityNodeInfoByAccessibilityId(int accessibilityWindowId,
                 long accessibilityNodeId, int interactionId,
-                IAccessibilityInteractionConnectionCallback callback, long interrogatingTid)
+                IAccessibilityInteractionConnectionCallback callback, long interrogatingTid,
+                int prefetchFlags)
                 throws RemoteException {
             final int resolvedWindowId = resolveAccessibilityWindowId(accessibilityWindowId);
             IAccessibilityInteractionConnection connection = null;
@@ -1150,7 +1151,7 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub
             final long identityToken = Binder.clearCallingIdentity();
             try {
                 connection.findAccessibilityNodeInfoByAccessibilityId(accessibilityNodeId,
-                        interactionId, callback, interrogatingPid, interrogatingTid);
+                        interactionId, callback, prefetchFlags, interrogatingPid, interrogatingTid);
             } catch (RemoteException re) {
                 if (DEBUG) {
                     Slog.e(LOG_TAG, "Error calling findAccessibilityNodeInfoByAccessibilityId()");