Merge "Prefetching can be interrupted by other service requests." into sc-dev

3 files changed, 314 insertions, 139 deletions

diff --git a/core/java/android/view/AccessibilityInteractionController.java b/core/java/android/view/AccessibilityInteractionController.java
index 9473845b15e6..0499f39f2fe4 100644
--- a/core/java/android/view/AccessibilityInteractionController.java
+++ b/core/java/android/view/AccessibilityInteractionController.java
@@ -86,12 +86,19 @@ public final class AccessibilityInteractionController {
     // accessibility from hanging
     private static final long REQUEST_PREPARER_TIMEOUT_MS = 500;
 
+    // Callbacks should have the same configuration of the flags below to allow satisfying a pending
+    // node request on prefetch
+    private static final int FLAGS_AFFECTING_REPORTED_DATA =
+            AccessibilityNodeInfo.FLAG_INCLUDE_NOT_IMPORTANT_VIEWS
+            | AccessibilityNodeInfo.FLAG_REPORT_VIEW_IDS;
+
     private final ArrayList<AccessibilityNodeInfo> mTempAccessibilityNodeInfoList =
         new ArrayList<AccessibilityNodeInfo>();
 
     private final Object mLock = new Object();
 
-    private final PrivateHandler mHandler;
+    @VisibleForTesting
+    public final PrivateHandler mHandler;
 
     private final ViewRootImpl mViewRootImpl;
 
@@ -114,6 +121,9 @@ public final class AccessibilityInteractionController {
     private AddNodeInfosForViewId mAddNodeInfosForViewId;
 
     @GuardedBy("mLock")
+    private ArrayList<Message> mPendingFindNodeByIdMessages;
+
+    @GuardedBy("mLock")
     private int mNumActiveRequestPreparers;
     @GuardedBy("mLock")
     private List<MessageHolder> mMessagesWaitingForRequestPreparer;
@@ -128,6 +138,7 @@ public final class AccessibilityInteractionController {
         mViewRootImpl = viewRootImpl;
         mPrefetcher = new AccessibilityNodePrefetcher();
         mA11yManager = mViewRootImpl.mContext.getSystemService(AccessibilityManager.class);
+        mPendingFindNodeByIdMessages = new ArrayList<>();
     }
 
     private void scheduleMessage(Message message, int interrogatingPid, long interrogatingTid,
@@ -177,6 +188,9 @@ public final class AccessibilityInteractionController {
         args.arg4 = arguments;
         message.obj = args;
 
+        synchronized (mLock) {
+            mPendingFindNodeByIdMessages.add(message);
+        }
         scheduleMessage(message, interrogatingPid, interrogatingTid, CONSIDER_REQUEST_PREPARERS);
     }
 
@@ -315,6 +329,9 @@ public final class AccessibilityInteractionController {
     }
 
     private void findAccessibilityNodeInfoByAccessibilityIdUiThread(Message message) {
+        synchronized (mLock) {
+            mPendingFindNodeByIdMessages.remove(message);
+        }
         final int flags = message.arg1;
 
         SomeArgs args = (SomeArgs) message.obj;
@@ -329,22 +346,58 @@ public final class AccessibilityInteractionController {
 
         args.recycle();
 
-        List<AccessibilityNodeInfo> infos = mTempAccessibilityNodeInfoList;
-        infos.clear();
+        View rootView = null;
+        AccessibilityNodeInfo rootNode = null;
         try {
             if (mViewRootImpl.mView == null || mViewRootImpl.mAttachInfo == null) {
                 return;
             }
             mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = flags;
-            final View root = findViewByAccessibilityId(accessibilityViewId);
-            if (root != null && isShown(root)) {
-                mPrefetcher.prefetchAccessibilityNodeInfos(
-                        root, virtualDescendantId, flags, infos, arguments);
+            rootView = findViewByAccessibilityId(accessibilityViewId);
+            if (rootView != null && isShown(rootView)) {
+                rootNode = populateAccessibilityNodeInfoForView(
+                        rootView, arguments, virtualDescendantId);
             }
         } finally {
-            updateInfosForViewportAndReturnFindNodeResult(
-                    infos, callback, interactionId, spec, interactiveRegion);
+            updateInfoForViewportAndReturnFindNodeResult(
+                    rootNode == null ? null : AccessibilityNodeInfo.obtain(rootNode),
+                    callback, interactionId, spec, interactiveRegion);
+        }
+        ArrayList<AccessibilityNodeInfo> infos = mTempAccessibilityNodeInfoList;
+        infos.clear();
+        mPrefetcher.prefetchAccessibilityNodeInfos(
+                rootView, rootNode == null ? null : AccessibilityNodeInfo.obtain(rootNode),
+                virtualDescendantId, flags, infos);
+        mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
+        updateInfosForViewPort(infos, spec, interactiveRegion);
+        returnPrefetchResult(interactionId, infos, callback);
+        returnPendingFindAccessibilityNodeInfosInPrefetch(rootNode, infos, flags);
+    }
+
+    private AccessibilityNodeInfo populateAccessibilityNodeInfoForView(
+            View view, Bundle arguments, int virtualViewId) {
+        AccessibilityNodeProvider provider = view.getAccessibilityNodeProvider();
+        // Determine if we'll be populating extra data
+        final String extraDataRequested = (arguments == null) ? null
+                : arguments.getString(EXTRA_DATA_REQUESTED_KEY);
+        AccessibilityNodeInfo root = null;
+        if (provider == null) {
+            root = view.createAccessibilityNodeInfo();
+            if (root != null) {
+                if (extraDataRequested != null) {
+                    view.addExtraDataToAccessibilityNodeInfo(root, extraDataRequested, arguments);
+                }
+            }
+        } else {
+            root = provider.createAccessibilityNodeInfo(virtualViewId);
+            if (root != null) {
+                if (extraDataRequested != null) {
+                    provider.addExtraDataToAccessibilityNodeInfo(
+                            virtualViewId, root, extraDataRequested, arguments);
+                }
+            }
         }
+        return root;
     }
 
     public void findAccessibilityNodeInfosByViewIdClientThread(long accessibilityNodeId,
@@ -402,6 +455,7 @@ public final class AccessibilityInteractionController {
                 mAddNodeInfosForViewId.reset();
             }
         } finally {
+            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
             updateInfosForViewportAndReturnFindNodeResult(
                     infos, callback, interactionId, spec, interactiveRegion);
         }
@@ -484,6 +538,7 @@ public final class AccessibilityInteractionController {
                 }
             }
         } finally {
+            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
             updateInfosForViewportAndReturnFindNodeResult(
                     infos, callback, interactionId, spec, interactiveRegion);
         }
@@ -575,6 +630,7 @@ public final class AccessibilityInteractionController {
                 }
             }
         } finally {
+            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
             updateInfoForViewportAndReturnFindNodeResult(
                     focused, callback, interactionId, spec, interactiveRegion);
         }
@@ -629,6 +685,7 @@ public final class AccessibilityInteractionController {
                 }
             }
         } finally {
+            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
             updateInfoForViewportAndReturnFindNodeResult(
                     next, callback, interactionId, spec, interactiveRegion);
         }
@@ -785,33 +842,6 @@ public final class AccessibilityInteractionController {
         }
     }
 
-    private void applyAppScaleAndMagnificationSpecIfNeeded(List<AccessibilityNodeInfo> infos,
-            MagnificationSpec spec) {
-        if (infos == null) {
-            return;
-        }
-        final float applicationScale = mViewRootImpl.mAttachInfo.mApplicationScale;
-        if (shouldApplyAppScaleAndMagnificationSpec(applicationScale, spec)) {
-            final int infoCount = infos.size();
-            for (int i = 0; i < infoCount; i++) {
-                AccessibilityNodeInfo info = infos.get(i);
-                applyAppScaleAndMagnificationSpecIfNeeded(info, spec);
-            }
-        }
-    }
-
-    private void adjustIsVisibleToUserIfNeeded(List<AccessibilityNodeInfo> infos,
-            Region interactiveRegion) {
-        if (interactiveRegion == null || infos == null) {
-            return;
-        }
-        final int infoCount = infos.size();
-        for (int i = 0; i < infoCount; i++) {
-            AccessibilityNodeInfo info = infos.get(i);
-            adjustIsVisibleToUserIfNeeded(info, interactiveRegion);
-        }
-    }
-
     private void adjustIsVisibleToUserIfNeeded(AccessibilityNodeInfo info,
             Region interactiveRegion) {
         if (interactiveRegion == null || info == null) {
@@ -832,17 +862,6 @@ public final class AccessibilityInteractionController {
         return false;
     }
 
-    private void adjustBoundsInScreenIfNeeded(List<AccessibilityNodeInfo> infos) {
-        if (infos == null || shouldBypassAdjustBoundsInScreen()) {
-            return;
-        }
-        final int infoCount = infos.size();
-        for (int i = 0; i < infoCount; i++) {
-            final AccessibilityNodeInfo info = infos.get(i);
-            adjustBoundsInScreenIfNeeded(info);
-        }
-    }
-
     private void adjustBoundsInScreenIfNeeded(AccessibilityNodeInfo info) {
         if (info == null || shouldBypassAdjustBoundsInScreen()) {
             return;
@@ -890,17 +909,6 @@ public final class AccessibilityInteractionController {
         return screenMatrix == null || screenMatrix.isIdentity();
     }
 
-    private void associateLeashedParentIfNeeded(List<AccessibilityNodeInfo> infos) {
-        if (infos == null || shouldBypassAssociateLeashedParent()) {
-            return;
-        }
-        final int infoCount = infos.size();
-        for (int i = 0; i < infoCount; i++) {
-            final AccessibilityNodeInfo info = infos.get(i);
-            associateLeashedParentIfNeeded(info);
-        }
-    }
-
     private void associateLeashedParentIfNeeded(AccessibilityNodeInfo info) {
         if (info == null || shouldBypassAssociateLeashedParent()) {
             return;
@@ -974,18 +982,46 @@ public final class AccessibilityInteractionController {
         return (appScale != 1.0f || (spec != null && !spec.isNop()));
     }
 
+    private void updateInfosForViewPort(List<AccessibilityNodeInfo> infos, MagnificationSpec spec,
+                                        Region interactiveRegion) {
+        for (int i = 0; i < infos.size(); i++) {
+            updateInfoForViewPort(infos.get(i), spec, interactiveRegion);
+        }
+    }
+
+    private void updateInfoForViewPort(AccessibilityNodeInfo info, MagnificationSpec spec,
+                                       Region interactiveRegion) {
+        associateLeashedParentIfNeeded(info);
+        applyScreenMatrixIfNeeded(info);
+        adjustBoundsInScreenIfNeeded(info);
+        // To avoid applyAppScaleAndMagnificationSpecIfNeeded changing the bounds of node,
+        // then impact the visibility result, we need to adjust visibility before apply scale.
+        adjustIsVisibleToUserIfNeeded(info, interactiveRegion);
+        applyAppScaleAndMagnificationSpecIfNeeded(info, spec);
+    }
+
     private void updateInfosForViewportAndReturnFindNodeResult(List<AccessibilityNodeInfo> infos,
             IAccessibilityInteractionConnectionCallback callback, int interactionId,
             MagnificationSpec spec, Region interactiveRegion) {
+        if (infos != null) {
+            updateInfosForViewPort(infos, spec, interactiveRegion);
+        }
+        returnFindNodesResult(infos, callback, interactionId);
+    }
+
+    private void returnFindNodeResult(AccessibilityNodeInfo info,
+                                      IAccessibilityInteractionConnectionCallback callback,
+                                      int interactionId) {
+        try {
+            callback.setFindAccessibilityNodeInfoResult(info, interactionId);
+        } catch (RemoteException re) {
+            /* ignore - the other side will time out */
+        }
+    }
+
+    private void returnFindNodesResult(List<AccessibilityNodeInfo> infos,
+            IAccessibilityInteractionConnectionCallback callback, int interactionId) {
         try {
-            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
-            associateLeashedParentIfNeeded(infos);
-            applyScreenMatrixIfNeeded(infos);
-            adjustBoundsInScreenIfNeeded(infos);
-            // To avoid applyAppScaleAndMagnificationSpecIfNeeded changing the bounds of node,
-            // then impact the visibility result, we need to adjust visibility before apply scale.
-            adjustIsVisibleToUserIfNeeded(infos, interactiveRegion);
-            applyAppScaleAndMagnificationSpecIfNeeded(infos, spec);
             callback.setFindAccessibilityNodeInfosResult(infos, interactionId);
             if (infos != null) {
                 infos.clear();
@@ -995,22 +1031,80 @@ public final class AccessibilityInteractionController {
         }
     }
 
+    private void returnPendingFindAccessibilityNodeInfosInPrefetch(AccessibilityNodeInfo rootNode,
+            List<AccessibilityNodeInfo> infos, int flags) {
+
+        AccessibilityNodeInfo satisfiedPendingRequestPrefetchedNode = null;
+        IAccessibilityInteractionConnectionCallback satisfiedPendingRequestCallback = null;
+        int satisfiedPendingRequestInteractionId = AccessibilityInteractionClient.NO_ID;
+
+        synchronized (mLock) {
+            for (int i = 0; i < mPendingFindNodeByIdMessages.size(); i++) {
+                final Message pendingMessage = mPendingFindNodeByIdMessages.get(i);
+                final int pendingFlags = pendingMessage.arg1;
+                if ((pendingFlags & FLAGS_AFFECTING_REPORTED_DATA)
+                        != (flags & FLAGS_AFFECTING_REPORTED_DATA)) {
+                    continue;
+                }
+                SomeArgs args = (SomeArgs) pendingMessage.obj;
+                final int accessibilityViewId = args.argi1;
+                final int virtualDescendantId = args.argi2;
+
+                satisfiedPendingRequestPrefetchedNode = nodeWithIdFromList(rootNode,
+                        infos, AccessibilityNodeInfo.makeNodeId(
+                                accessibilityViewId, virtualDescendantId));
+
+                if (satisfiedPendingRequestPrefetchedNode != null) {
+                    satisfiedPendingRequestCallback =
+                            (IAccessibilityInteractionConnectionCallback) args.arg1;
+                    satisfiedPendingRequestInteractionId = args.argi3;
+                    mHandler.removeMessages(
+                            PrivateHandler.MSG_FIND_ACCESSIBILITY_NODE_INFO_BY_ACCESSIBILITY_ID,
+                            pendingMessage.obj);
+                    args.recycle();
+                    break;
+                }
+            }
+            mPendingFindNodeByIdMessages.clear();
+        }
+
+        if (satisfiedPendingRequestPrefetchedNode != null) {
+            returnFindNodeResult(
+                    AccessibilityNodeInfo.obtain(satisfiedPendingRequestPrefetchedNode),
+                    satisfiedPendingRequestCallback, satisfiedPendingRequestInteractionId);
+        }
+    }
+
+    private AccessibilityNodeInfo nodeWithIdFromList(AccessibilityNodeInfo rootNode,
+            List<AccessibilityNodeInfo> infos, long nodeId) {
+        if (rootNode != null && rootNode.getSourceNodeId() == nodeId) {
+            return rootNode;
+        }
+        for (int j = 0; j < infos.size(); j++) {
+            AccessibilityNodeInfo info = infos.get(j);
+            if (info.getSourceNodeId() == nodeId) {
+                return info;
+            }
+        }
+        return null;
+    }
+
+    private void returnPrefetchResult(int interactionId, List<AccessibilityNodeInfo> infos,
+                                      IAccessibilityInteractionConnectionCallback callback) {
+        if (infos.size() > 0) {
+            try {
+                callback.setPrefetchAccessibilityNodeInfoResult(infos, interactionId);
+            } catch (RemoteException re) {
+                /* ignore - other side isn't too bothered if this doesn't arrive */
+            }
+        }
+    }
+
     private void updateInfoForViewportAndReturnFindNodeResult(AccessibilityNodeInfo info,
             IAccessibilityInteractionConnectionCallback callback, int interactionId,
             MagnificationSpec spec, Region interactiveRegion) {
-        try {
-            mViewRootImpl.mAttachInfo.mAccessibilityFetchFlags = 0;
-            associateLeashedParentIfNeeded(info);
-            applyScreenMatrixIfNeeded(info);
-            adjustBoundsInScreenIfNeeded(info);
-            // To avoid applyAppScaleAndMagnificationSpecIfNeeded changing the bounds of node,
-            // then impact the visibility result, we need to adjust visibility before apply scale.
-            adjustIsVisibleToUserIfNeeded(info, interactiveRegion);
-            applyAppScaleAndMagnificationSpecIfNeeded(info, spec);
-            callback.setFindAccessibilityNodeInfoResult(info, interactionId);
-        } catch (RemoteException re) {
-                /* ignore - the other side will time out */
-        }
+        updateInfoForViewPort(info, spec, interactiveRegion);
+        returnFindNodeResult(info, callback, interactionId);
     }
 
     private boolean handleClickableSpanActionUiThread(
@@ -1053,56 +1147,45 @@ public final class AccessibilityInteractionController {
 
         private final ArrayList<View> mTempViewList = new ArrayList<View>();
 
-        public void prefetchAccessibilityNodeInfos(View view, int virtualViewId, int fetchFlags,
-                List<AccessibilityNodeInfo> outInfos, Bundle arguments) {
+        public void prefetchAccessibilityNodeInfos(View view, AccessibilityNodeInfo root,
+                int virtualViewId, int fetchFlags, List<AccessibilityNodeInfo> outInfos) {
+            if (root == null) {
+                return;
+            }
             AccessibilityNodeProvider provider = view.getAccessibilityNodeProvider();
-            // Determine if we'll be populating extra data
-            final String extraDataRequested = (arguments == null) ? null
-                    : arguments.getString(EXTRA_DATA_REQUESTED_KEY);
             if (provider == null) {
-                AccessibilityNodeInfo root = view.createAccessibilityNodeInfo();
-                if (root != null) {
-                    if (extraDataRequested != null) {
-                        view.addExtraDataToAccessibilityNodeInfo(
-                                root, extraDataRequested, arguments);
-                    }
-                    outInfos.add(root);
-                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
-                        prefetchPredecessorsOfRealNode(view, outInfos);
-                    }
-                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
-                        prefetchSiblingsOfRealNode(view, outInfos);
-                    }
-                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
-                        prefetchDescendantsOfRealNode(view, outInfos);
-                    }
+                if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
+                    prefetchPredecessorsOfRealNode(view, outInfos);
+                }
+                if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
+                    prefetchSiblingsOfRealNode(view, outInfos);
+                }
+                if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
+                    prefetchDescendantsOfRealNode(view, outInfos);
                 }
             } else {
-                final AccessibilityNodeInfo root =
-                        provider.createAccessibilityNodeInfo(virtualViewId);
-                if (root != null) {
-                    if (extraDataRequested != null) {
-                        provider.addExtraDataToAccessibilityNodeInfo(
-                                virtualViewId, root, extraDataRequested, arguments);
-                    }
-                    outInfos.add(root);
-                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
-                        prefetchPredecessorsOfVirtualNode(root, view, provider, outInfos);
-                    }
-                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
-                        prefetchSiblingsOfVirtualNode(root, view, provider, outInfos);
-                    }
-                    if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
-                        prefetchDescendantsOfVirtualNode(root, provider, outInfos);
-                    }
+                if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_PREDECESSORS) != 0) {
+                    prefetchPredecessorsOfVirtualNode(root, view, provider, outInfos);
+                }
+                if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_SIBLINGS) != 0) {
+                    prefetchSiblingsOfVirtualNode(root, view, provider, outInfos);
+                }
+                if ((fetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_DESCENDANTS) != 0) {
+                    prefetchDescendantsOfVirtualNode(root, provider, outInfos);
                 }
             }
             if (ENFORCE_NODE_TREE_CONSISTENT) {
-                enforceNodeTreeConsistent(outInfos);
+                enforceNodeTreeConsistent(root, outInfos);
             }
         }
 
-        private void enforceNodeTreeConsistent(List<AccessibilityNodeInfo> nodes) {
+        private boolean shouldStopPrefetching(List prefetchededInfos) {
+            return mHandler.hasUserInteractiveMessagesWaiting()
+                    || prefetchededInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE;
+        }
+
+        private void enforceNodeTreeConsistent(
+                AccessibilityNodeInfo root, List<AccessibilityNodeInfo> nodes) {
             LongSparseArray<AccessibilityNodeInfo> nodeMap =
                     new LongSparseArray<AccessibilityNodeInfo>();
             final int nodeCount = nodes.size();
@@ -1113,7 +1196,6 @@ public final class AccessibilityInteractionController {
 
             // If the nodes are a tree it does not matter from
             // which node we start to search for the root.
-            AccessibilityNodeInfo root = nodeMap.valueAt(0);
             AccessibilityNodeInfo parent = root;
             while (parent != null) {
                 root = parent;
@@ -1180,9 +1262,11 @@ public final class AccessibilityInteractionController {
 
         private void prefetchPredecessorsOfRealNode(View view,
                 List<AccessibilityNodeInfo> outInfos) {
+            if (shouldStopPrefetching(outInfos)) {
+                return;
+            }
             ViewParent parent = view.getParentForAccessibility();
-            while (parent instanceof View
-                    && outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+            while (parent instanceof View && !shouldStopPrefetching(outInfos)) {
                 View parentView = (View) parent;
                 AccessibilityNodeInfo info = parentView.createAccessibilityNodeInfo();
                 if (info != null) {
@@ -1194,6 +1278,9 @@ public final class AccessibilityInteractionController {
 
         private void prefetchSiblingsOfRealNode(View current,
                 List<AccessibilityNodeInfo> outInfos) {
+            if (shouldStopPrefetching(outInfos)) {
+                return;
+            }
             ViewParent parent = current.getParentForAccessibility();
             if (parent instanceof ViewGroup) {
                 ViewGroup parentGroup = (ViewGroup) parent;
@@ -1203,7 +1290,7 @@ public final class AccessibilityInteractionController {
                     parentGroup.addChildrenForAccessibility(children);
                     final int childCount = children.size();
                     for (int i = 0; i < childCount; i++) {
-                        if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                        if (shouldStopPrefetching(outInfos)) {
                             return;
                         }
                         View child = children.get(i);
@@ -1231,7 +1318,7 @@ public final class AccessibilityInteractionController {
 
         private void prefetchDescendantsOfRealNode(View root,
                 List<AccessibilityNodeInfo> outInfos) {
-            if (!(root instanceof ViewGroup)) {
+            if (shouldStopPrefetching(outInfos) || !(root instanceof ViewGroup)) {
                 return;
             }
             HashMap<View, AccessibilityNodeInfo> addedChildren =
@@ -1242,7 +1329,7 @@ public final class AccessibilityInteractionController {
                 root.addChildrenForAccessibility(children);
                 final int childCount = children.size();
                 for (int i = 0; i < childCount; i++) {
-                    if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                    if (shouldStopPrefetching(outInfos)) {
                         return;
                     }
                     View child = children.get(i);
@@ -1267,7 +1354,7 @@ public final class AccessibilityInteractionController {
             } finally {
                 children.clear();
             }
-            if (outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+            if (!shouldStopPrefetching(outInfos)) {
                 for (Map.Entry<View, AccessibilityNodeInfo> entry : addedChildren.entrySet()) {
                     View addedChild = entry.getKey();
                     AccessibilityNodeInfo virtualRoot = entry.getValue();
@@ -1289,7 +1376,7 @@ public final class AccessibilityInteractionController {
             long parentNodeId = root.getParentNodeId();
             int accessibilityViewId = AccessibilityNodeInfo.getAccessibilityViewId(parentNodeId);
             while (accessibilityViewId != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) {
-                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                if (shouldStopPrefetching(outInfos)) {
                     return;
                 }
                 final int virtualDescendantId =
@@ -1334,7 +1421,7 @@ public final class AccessibilityInteractionController {
                 if (parent != null) {
                     final int childCount = parent.getChildCount();
                     for (int i = 0; i < childCount; i++) {
-                        if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                        if (shouldStopPrefetching(outInfos)) {
                             return;
                         }
                         final long childNodeId = parent.getChildId(i);
@@ -1359,7 +1446,7 @@ public final class AccessibilityInteractionController {
             final int initialOutInfosSize = outInfos.size();
             final int childCount = root.getChildCount();
             for (int i = 0; i < childCount; i++) {
-                if (outInfos.size() >= MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+                if (shouldStopPrefetching(outInfos)) {
                     return;
                 }
                 final long childNodeId = root.getChildId(i);
@@ -1369,7 +1456,7 @@ public final class AccessibilityInteractionController {
                     outInfos.add(child);
                 }
             }
-            if (outInfos.size() < MAX_ACCESSIBILITY_NODE_INFO_BATCH_SIZE) {
+            if (!shouldStopPrefetching(outInfos)) {
                 final int addedChildCount = outInfos.size() - initialOutInfosSize;
                 for (int i = 0; i < addedChildCount; i++) {
                     AccessibilityNodeInfo child = outInfos.get(initialOutInfosSize + i);
@@ -1478,6 +1565,10 @@ public final class AccessibilityInteractionController {
         boolean hasAccessibilityCallback(Message message) {
             return message.what < FIRST_NO_ACCESSIBILITY_CALLBACK_MSG ? true : false;
         }
+
+        boolean hasUserInteractiveMessagesWaiting() {
+            return hasMessagesOrCallbacks();
+        }
     }
 
     private final class AddNodeInfosForViewId implements Predicate<View> {
diff --git a/core/java/android/view/accessibility/AccessibilityInteractionClient.java b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
index f63749be6df2..9556c25575cd 100644
--- a/core/java/android/view/accessibility/AccessibilityInteractionClient.java
+++ b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
@@ -23,7 +23,9 @@ import android.compat.annotation.UnsupportedAppUsage;
 import android.os.Binder;
 import android.os.Build;
 import android.os.Bundle;
+import android.os.Handler;
 import android.os.IBinder;
+import android.os.Looper;
 import android.os.Message;
 import android.os.Process;
 import android.os.RemoteException;
@@ -113,6 +115,8 @@ public final class AccessibilityInteractionClient
 
     private final Object mInstanceLock = new Object();
 
+    private Handler mMainHandler;
+
     private volatile int mInteractionId = -1;
 
     private AccessibilityNodeInfo mFindAccessibilityNodeInfoResult;
@@ -123,6 +127,11 @@ public final class AccessibilityInteractionClient
 
     private Message mSameThreadMessage;
 
+    private int mInteractionIdWaitingForPrefetchResult;
+    private int mConnectionIdWaitingForPrefetchResult;
+    private String[] mPackageNamesForNextPrefetchResult;
+    private Runnable mPrefetchResultRunnable;
+
     /**
      * @return The client for the current thread.
      */
@@ -197,6 +206,9 @@ public final class AccessibilityInteractionClient
 
     private AccessibilityInteractionClient() {
         /* reducing constructor visibility */
+        if (Looper.getMainLooper() != null) {
+            mMainHandler = new Handler(Looper.getMainLooper());
+        }
     }
 
     /**
@@ -451,16 +463,16 @@ public final class AccessibilityInteractionClient
                     Binder.restoreCallingIdentity(identityToken);
                 }
                 if (packageNames != null) {
-                    List<AccessibilityNodeInfo> infos = getFindAccessibilityNodeInfosResultAndClear(
-                            interactionId);
-                    finalizeAndCacheAccessibilityNodeInfos(infos, connectionId,
-                            bypassCache, packageNames);
-                    if (infos != null && !infos.isEmpty()) {
-                        for (int i = 1; i < infos.size(); i++) {
-                            infos.get(i).recycle();
-                        }
-                        return infos.get(0);
+                    AccessibilityNodeInfo info =
+                            getFindAccessibilityNodeInfoResultAndClear(interactionId);
+                    if ((prefetchFlags & AccessibilityNodeInfo.FLAG_PREFETCH_MASK) != 0
+                            && info != null) {
+                        setInteractionWaitingForPrefetchResult(interactionId, connectionId,
+                                packageNames);
                     }
+                    finalizeAndCacheAccessibilityNodeInfo(info, connectionId,
+                            bypassCache, packageNames);
+                    return info;
                 }
             } else {
                 if (DEBUG) {
@@ -474,6 +486,15 @@ public final class AccessibilityInteractionClient
         return null;
     }
 
+    private void setInteractionWaitingForPrefetchResult(int interactionId, int connectionId,
+            String[] packageNames) {
+        synchronized (mInstanceLock) {
+            mInteractionIdWaitingForPrefetchResult = interactionId;
+            mConnectionIdWaitingForPrefetchResult = connectionId;
+            mPackageNamesForNextPrefetchResult = packageNames;
+        }
+    }
+
     private static String idToString(int accessibilityWindowId, long accessibilityNodeId) {
         return accessibilityWindowId + "/"
                 + AccessibilityNodeInfo.idToString(accessibilityNodeId);
@@ -829,6 +850,60 @@ public final class AccessibilityInteractionClient
     }
 
     /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void setPrefetchAccessibilityNodeInfoResult(@NonNull List<AccessibilityNodeInfo> infos,
+                                                       int interactionId) {
+        List<AccessibilityNodeInfo> infosCopy = null;
+        int mConnectionIdWaitingForPrefetchResultCopy = -1;
+        String[] mPackageNamesForNextPrefetchResultCopy = null;
+
+        synchronized (mInstanceLock) {
+            if (!infos.isEmpty() && mInteractionIdWaitingForPrefetchResult == interactionId) {
+                if (mMainHandler != null) {
+                    if (mPrefetchResultRunnable != null) {
+                        mMainHandler.removeCallbacks(mPrefetchResultRunnable);
+                        mPrefetchResultRunnable = null;
+                    }
+                    /**
+                     * TODO(b/180957109): AccessibilityCache is prone to deadlocks
+                     * We post caching the prefetched nodes in the main thread. Using the binder
+                     * thread results in "Long monitor contention with owner main" logs where
+                     * service response times may exceed 5 seconds. This is due to the cache calling
+                     * out to the system when refreshing nodes with the lock held.
+                     */
+                    mPrefetchResultRunnable = () -> finalizeAndCacheAccessibilityNodeInfos(
+                            infos, mConnectionIdWaitingForPrefetchResult, false,
+                            mPackageNamesForNextPrefetchResult);
+                    mMainHandler.post(mPrefetchResultRunnable);
+
+                } else {
+                    for (AccessibilityNodeInfo info : infos) {
+                        infosCopy.add(new AccessibilityNodeInfo(info));
+                    }
+                    mConnectionIdWaitingForPrefetchResultCopy =
+                            mConnectionIdWaitingForPrefetchResult;
+                    mPackageNamesForNextPrefetchResultCopy =
+                            new String[mPackageNamesForNextPrefetchResult.length];
+                    for (int i = 0; i < mPackageNamesForNextPrefetchResult.length; i++) {
+                        mPackageNamesForNextPrefetchResultCopy[i] =
+                                mPackageNamesForNextPrefetchResult[i];
+
+                    }
+                }
+            }
+
+        }
+
+        if (infosCopy != null) {
+            finalizeAndCacheAccessibilityNodeInfos(
+                    infosCopy, mConnectionIdWaitingForPrefetchResultCopy, false,
+                    mPackageNamesForNextPrefetchResultCopy);
+        }
+    }
+
+    /**
      * Gets the result of a request to perform an accessibility action.
      *
      * @param interactionId The interaction id to match the result with the request.
diff --git a/core/java/android/view/accessibility/IAccessibilityInteractionConnectionCallback.aidl b/core/java/android/view/accessibility/IAccessibilityInteractionConnectionCallback.aidl
index 049bb31adbb1..231e75a19a06 100644
--- a/core/java/android/view/accessibility/IAccessibilityInteractionConnectionCallback.aidl
+++ b/core/java/android/view/accessibility/IAccessibilityInteractionConnectionCallback.aidl
@@ -47,6 +47,15 @@ oneway interface IAccessibilityInteractionConnectionCallback {
         int interactionId);
 
     /**
+     * Sets the result of a prefetch request that returns {@link AccessibilityNodeInfo}s.
+     *
+     * @param root The {@link AccessibilityNodeInfo} for which the prefetching is based off of.
+     * @param infos The result {@link AccessibilityNodeInfo}s.
+     */
+    void setPrefetchAccessibilityNodeInfoResult(
+        in List<AccessibilityNodeInfo> infos, int interactionId);
+
+    /**
      * Sets the result of a request to perform an accessibility action.
      *
      * @param Whether the action was performed.