Prefetching can be interrupted by other service requests.

This is the re-merging of ag/12923546 (where most of that original
message is posted below), which includes various bug fixes.

Slow prefetch requests would block user interactive requests, creating
noticeable sluggishness and unresponsiveness in accessibility services,
especially on the web.

Let's make it so a user interactive requests stops prefetching.
We can't interrupt an API call, but we can stop in between API calls.

On the service side, we have to separate the prefetch callbacks from the
find callback. And we have to make it asynchronous. It does dispatch
intothe main thread, so the AccessibilityCache can remain single threaded.

When the calls are interrupted on the application side,
returnPendingFindAccessibilityNodeInfosInPrefetch checks the find
requests that are waiting in the queue, to see if they can be addressed
by the prefetch results. If they can be, we don't have to call into
potentially non-performant application code. We don't  check requests
that have differing prefetch flags (FLAG_INCLUDE_NOT_IMPORTANT_VIEWS,
FLAG_REPORT_VIEW_IDS) that would result in different caches.

We also make mPendingFindNodeByIdMessages thread-safe and ensure in
ActionReplacingCallback we don't return null results. Merged
ag/13246536, ag/13256330

UiAutomation does't require a main thread, so getMainLooper may
return null. In this case, instead of posting to the main looper,
we cache nodes on the binder thread (which is our ultimate goal
once b/180957109 is fixed).

Added tests to verify AccessibilityInteractionController interactions

Test: atest AccessibilityInteractionControllerNodeRequestsTest,
FrameworksServicesTests FrameworksCoreTests, CtsAccessibility, Manual
testing

Bug: b/176195360, b/175877007, b/175884343, b/178726546, b/175832139,
b/176195505

Change-Id: I346a3f40c84c6697b8a1e1d84a636eada655b984

1 files changed, 221 insertions, 130 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> {