Fix inconsitency in aAccessibilityNodeInfo cache.

1. Fixed errors in the accessibility node cache.

  A. The cache was not catching the case when the current window changes as a
     result the user touch exploring it. As a result the cache had nodes from
     more that one window but the node ids are not unique thus causing a mess.

  B. The node info tree was prefetched regardless if a prefetched node is root
     name space (i.e. view ids - not accessibility ids - are namespaced) while
     the prefetched nodes were taking this into account. As a result there can
     get disconnected subtrees in the cache.

  C. When an event for a property change such as focus was received the cache
     we were removing the source node. As a result there may be disconnected nodes.

  D. When a node was added to the cache and an older version exists there was
     no check if it will point to the same children and parent. As a result if
     the state of the node has fewer children the subtrees rooted at the no
     longer present children will stay disconnected in the cache.

  E. When a node got accessibility or input focus the old one in the cache was
     not removed. As a result you may have a state with more than one access
     or input focus.

2. Added integrity check enabled only on user builds when a specific flag is set
   for the cache which checks whether:

  A. All nodes are from the same window.

  B. All nodes are connected.

  C. There are no duplicates.

  D. There is only one input focus.

  E. There is only one accessibility focus.

3. The reported accessibility node info tree was stopping at the root namespace
   boundary which is not correct. The reported tree has to reflect everything
   on the screen that the user can see such a workspace with widgets. The root
   namespace is added to avoid clash of view id but the accessibility ids are
   unique no matter if the view is inflated from a remote view.

4. Added calls to notify the accessibility layer when a preoprty that is interesting
   for accessibiliy has changed.

bug:6471710

Change-Id: I069470d91f209ba16313fa6539787a55efa3512e

4 files changed, 198 insertions, 54 deletions

diff --git a/core/java/android/view/View.java b/core/java/android/view/View.java
index bf7d037969cb..85fd8fe40de4 100644
--- a/core/java/android/view/View.java
+++ b/core/java/android/view/View.java
@@ -4723,11 +4723,9 @@ public class View implements Drawable.Callback, Drawable.Callback2, KeyEvent.Cal
         getBoundsOnScreen(bounds);
         info.setBoundsInScreen(bounds);
 
-        if ((mPrivateFlags & IS_ROOT_NAMESPACE) == 0) {
-            ViewParent parent = getParentForAccessibility();
-            if (parent instanceof View) {
-                info.setParent((View) parent);
-            }
+        ViewParent parent = getParentForAccessibility();
+        if (parent instanceof View) {
+            info.setParent((View) parent);
         }
 
         info.setVisibleToUser(isVisibleToUser());
@@ -6503,6 +6501,9 @@ public class View implements Drawable.Callback, Drawable.Callback2, KeyEvent.Cal
      *       that is interesting for accessilility purposes.
      */
     public void notifyAccessibilityStateChanged() {
+        if (!AccessibilityManager.getInstance(mContext).isEnabled()) {
+            return;
+        }
         if ((mPrivateFlags2 & ACCESSIBILITY_STATE_CHANGED) == 0) {
             mPrivateFlags2 |= ACCESSIBILITY_STATE_CHANGED;
             if (mParent != null) {
diff --git a/core/java/android/view/ViewGroup.java b/core/java/android/view/ViewGroup.java
index b3c8895a9f9e..f55b7acca9a0 100644
--- a/core/java/android/view/ViewGroup.java
+++ b/core/java/android/view/ViewGroup.java
@@ -1635,8 +1635,7 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
             final int childrenCount = children.getChildCount();
             for (int i = 0; i < childrenCount; i++) {
                 View child = children.getChildAt(i);
-                if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE
-                        && (child.mPrivateFlags & IS_ROOT_NAMESPACE) == 0) {
+                if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE) {
                     if (child.includeForAccessibility()) {
                         childrenForAccessibility.add(child);
                     } else {
diff --git a/core/java/android/view/accessibility/AccessibilityInteractionClient.java b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
index 24e90fdfe160..bd341d0b10eb 100644
--- a/core/java/android/view/accessibility/AccessibilityInteractionClient.java
+++ b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
@@ -441,10 +441,6 @@ public final class AccessibilityInteractionClient
         sAccessibilityNodeInfoCache.clear();
     }
 
-    public void removeCachedNode(long accessibilityNodeId) {
-        sAccessibilityNodeInfoCache.remove(accessibilityNodeId);
-    }
-
     public void onAccessibilityEvent(AccessibilityEvent event) {
         sAccessibilityNodeInfoCache.onAccessibilityEvent(event);
     }
@@ -630,7 +626,7 @@ public final class AccessibilityInteractionClient
             applyCompatibilityScaleIfNeeded(info, windowScale);
             info.setConnectionId(connectionId);
             info.setSealed(true);
-            sAccessibilityNodeInfoCache.put(info.getSourceNodeId(), info);
+            sAccessibilityNodeInfoCache.add(info);
         }
     }
 
diff --git a/core/java/android/view/accessibility/AccessibilityNodeInfoCache.java b/core/java/android/view/accessibility/AccessibilityNodeInfoCache.java
index d2609bb42d1d..52b7772864f7 100644
--- a/core/java/android/view/accessibility/AccessibilityNodeInfoCache.java
+++ b/core/java/android/view/accessibility/AccessibilityNodeInfoCache.java
@@ -16,10 +16,15 @@
 
 package android.view.accessibility;
 
+import android.os.Build;
 import android.util.Log;
 import android.util.LongSparseArray;
 import android.util.SparseLongArray;
 
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Queue;
+
 /**
  * Simple cache for AccessibilityNodeInfos. The cache is mapping an
  * accessibility id to an info. The cache allows storing of
@@ -36,10 +41,14 @@ public class AccessibilityNodeInfoCache {
 
     private static final boolean DEBUG = false;
 
+    private static final boolean CHECK_INTEGRITY = true;
+
     private final Object mLock = new Object();
 
     private final LongSparseArray<AccessibilityNodeInfo> mCacheImpl;
 
+    private int mWindowId;
+
     public AccessibilityNodeInfoCache() {
         if (ENABLED) {
             mCacheImpl = new LongSparseArray<AccessibilityNodeInfo>();
@@ -59,21 +68,49 @@ public class AccessibilityNodeInfoCache {
             final int eventType = event.getEventType();
             switch (eventType) {
                 case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: {
+                    // New window so we clear the cache.
+                    mWindowId = event.getWindowId();
                     clear();
                 } break;
+                case AccessibilityEvent.TYPE_VIEW_HOVER_ENTER:
+                case AccessibilityEvent.TYPE_VIEW_HOVER_EXIT: {
+                    final int windowId = event.getWindowId();
+                    if (mWindowId != windowId) {
+                        // New window so we clear the cache.
+                        mWindowId = windowId;
+                        clear();
+                    }
+                } break;
                 case AccessibilityEvent.TYPE_VIEW_FOCUSED:
+                case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED:
                 case AccessibilityEvent.TYPE_VIEW_SELECTED:
                 case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED:
                 case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: {
-                    final long accessibilityNodeId = event.getSourceNodeId();
-                    remove(accessibilityNodeId);
+                    // Since we prefetch the descendants of a node we
+                    // just remove the entire subtree since when the node
+                    // is fetched we will gets its descendant anyway.
+                    synchronized (mLock) {
+                        final long sourceId = event.getSourceNodeId();
+                        clearSubTreeLocked(sourceId);
+                        if (eventType == AccessibilityEvent.TYPE_VIEW_FOCUSED) {
+                            clearSubtreeWithOldInputFocusLocked(sourceId);
+                        }
+                        if (eventType == AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED) {
+                            clearSubtreeWithOldAccessibilityFocusLocked(sourceId);
+                        }
+                    }
                 } break;
                 case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED:
                 case AccessibilityEvent.TYPE_VIEW_SCROLLED: {
-                    final long accessibilityNodeId = event.getSourceNodeId();
-                    clearSubTree(accessibilityNodeId);
+                    synchronized (mLock) {
+                        final long accessibilityNodeId = event.getSourceNodeId();
+                        clearSubTreeLocked(accessibilityNodeId);
+                    }
                 } break;
             }
+            if (Build.IS_DEBUGGABLE && CHECK_INTEGRITY) {
+                checkIntegrity();
+            }
         }
     }
 
@@ -105,51 +142,45 @@ public class AccessibilityNodeInfoCache {
     /**
      * Caches an {@link AccessibilityNodeInfo} given its accessibility node id.
      *
-     * @param accessibilityNodeId The info accessibility node id.
      * @param info The {@link AccessibilityNodeInfo} to cache.
      */
-    public void put(long accessibilityNodeId, AccessibilityNodeInfo info) {
+    public void add(AccessibilityNodeInfo info) {
         if (ENABLED) {
             synchronized(mLock) {
                 if (DEBUG) {
-                    Log.i(LOG_TAG, "put(" + accessibilityNodeId + ", " + info + ")");
+                    Log.i(LOG_TAG, "add(" + info + ")");
                 }
-                // Cache a copy since the client calls to AccessibilityNodeInfo#recycle()
-                // will wipe the data of the cached info.
-                AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info);
-                mCacheImpl.put(accessibilityNodeId, clone);
-            }
-        }
-    }
 
-    /**
-     * Returns whether the cache contains an accessibility node id key.
-     *
-     * @param accessibilityNodeId The key for which to check.
-     * @return True if the key is in the cache.
-     */
-    public boolean containsKey(long accessibilityNodeId) {
-        if (ENABLED) {
-            synchronized(mLock) {
-                return (mCacheImpl.indexOfKey(accessibilityNodeId) >= 0);
-            }
-        } else {
-            return false;
-        }
-    }
+                final long sourceId = info.getSourceNodeId();
+                AccessibilityNodeInfo oldInfo = mCacheImpl.get(sourceId);
+                if (oldInfo != null) {
+                    // If the added node is in the cache we have to be careful if
+                    // the new one represents a source state where some of the
+                    // children have been removed to avoid having disconnected
+                    // subtrees in the cache.
+                    SparseLongArray oldChildrenIds = oldInfo.getChildNodeIds();
+                    SparseLongArray newChildrenIds = info.getChildNodeIds();
+                    final int oldChildCount = oldChildrenIds.size();
+                    for (int i = 0; i < oldChildCount; i++) {
+                        final long oldChildId = oldChildrenIds.valueAt(i);
+                        if (newChildrenIds.indexOfValue(oldChildId) < 0) {
+                            clearSubTreeLocked(oldChildId);
+                        }
+                    }
 
-    /**
-     * Removes a cached {@link AccessibilityNodeInfo}.
-     *
-     * @param accessibilityNodeId The info accessibility node id.
-     */
-    public void remove(long accessibilityNodeId) {
-        if (ENABLED) {
-            synchronized(mLock) {
-                if (DEBUG) {
-                    Log.i(LOG_TAG, "remove(" + accessibilityNodeId + ")");
+                    // Also be careful if the parent has changed since the new
+                    // parent may be a predecessor of the old parent which will
+                    // make the cached tree cyclic.
+                    final long oldParentId = oldInfo.getParentNodeId();
+                    if (info.getParentNodeId() != oldParentId) {
+                        clearSubTreeLocked(oldParentId);
+                    }
                 }
-                mCacheImpl.remove(accessibilityNodeId);
+
+                // Cache a copy since the client calls to AccessibilityNodeInfo#recycle()
+                // will wipe the data of the cached info.
+                AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info);
+                mCacheImpl.put(sourceId, clone);
             }
         }
     }
@@ -179,7 +210,7 @@ public class AccessibilityNodeInfoCache {
      *
      * @param rootNodeId The root id.
      */
-    private void clearSubTree(long rootNodeId) {
+    private void clearSubTreeLocked(long rootNodeId) {
         AccessibilityNodeInfo current = mCacheImpl.get(rootNodeId);
         if (current == null) {
             return;
@@ -189,7 +220,124 @@ public class AccessibilityNodeInfoCache {
         final int childCount = childNodeIds.size();
         for (int i = 0; i < childCount; i++) {
             final long childNodeId = childNodeIds.valueAt(i);
-            clearSubTree(childNodeId);
+            clearSubTreeLocked(childNodeId);
+        }
+    }
+
+    /**
+     * We are enforcing the invariant for a single input focus.
+     *
+     * @param currentInputFocusId The current input focused node.
+     */
+    private void clearSubtreeWithOldInputFocusLocked(long currentInputFocusId) {
+        final int cacheSize = mCacheImpl.size();
+        for (int i = 0; i < cacheSize; i++) {
+            AccessibilityNodeInfo info = mCacheImpl.valueAt(i);
+            final long infoSourceId = info.getSourceNodeId();
+            if (infoSourceId != currentInputFocusId && info.isFocused()) {
+                clearSubTreeLocked(infoSourceId);
+                return;
+            }
+        }
+    }
+
+    /**
+     * We are enforcing the invariant for a single accessibility focus.
+     *
+     * @param currentInputFocusId The current input focused node.
+     */
+    private void clearSubtreeWithOldAccessibilityFocusLocked(long currentAccessibilityFocusId) {
+        final int cacheSize = mCacheImpl.size();
+        for (int i = 0; i < cacheSize; i++) {
+            AccessibilityNodeInfo info = mCacheImpl.valueAt(i);
+            final long infoSourceId = info.getSourceNodeId();
+            if (infoSourceId != currentAccessibilityFocusId && info.isAccessibilityFocused()) {
+                clearSubTreeLocked(infoSourceId);
+                return;
+            }
+        }
+    }
+
+    /**
+     * Check the integrity of the cache which is it does not have nodes
+     * from more than one window, there are no duplicates, all nodes are
+     * connected, there is a single input focused node, and there is a
+     * single accessibility focused node.
+     */
+    private void checkIntegrity() {
+        synchronized (mLock) {
+            // Get the root.
+            if (mCacheImpl.size() <= 0) {
+                return;
+            }
+
+            // If the cache is a tree it does not matter from
+            // which node we start to search for the root.
+            AccessibilityNodeInfo root = mCacheImpl.valueAt(0);
+            AccessibilityNodeInfo parent = root;
+            while (parent != null) {
+                root = parent;
+                parent = mCacheImpl.get(parent.getParentNodeId());
+            }
+
+            // Traverse the tree and do some checks.
+            final int windowId = root.getWindowId();
+            AccessibilityNodeInfo accessFocus = null;
+            AccessibilityNodeInfo inputFocus = null;
+            HashSet<AccessibilityNodeInfo> seen = new HashSet<AccessibilityNodeInfo>();
+            Queue<AccessibilityNodeInfo> fringe = new LinkedList<AccessibilityNodeInfo>();
+            fringe.add(root);
+
+            while (!fringe.isEmpty()) {
+                AccessibilityNodeInfo current = fringe.poll();
+                // Check for duplicates
+                if (!seen.add(current)) {
+                    Log.e(LOG_TAG, "Duplicate node: " + current);
+                    return;
+                }
+
+                // Check for one accessibility focus.
+                if (current.isAccessibilityFocused()) {
+                    if (accessFocus != null) {
+                        Log.e(LOG_TAG, "Duplicate accessibility focus:" + current);
+                    } else {
+                        accessFocus = current;
+                    }
+                }
+
+                // Check for one input focus.
+                if (current.isFocused()) {
+                    if (inputFocus != null) {
+                        Log.e(LOG_TAG, "Duplicate input focus: " + current);
+                    } else {
+                        inputFocus = current;
+                    }
+                }
+
+                SparseLongArray childIds = current.getChildNodeIds();
+                final int childCount = childIds.size();
+                for (int i = 0; i < childCount; i++) {
+                    final long childId = childIds.valueAt(i);
+                    AccessibilityNodeInfo child = mCacheImpl.get(childId);
+                    if (child != null) {
+                        fringe.add(child);
+                    }
+                }
+            }
+
+            // Check for disconnected nodes or ones from another window.
+            final int cacheSize = mCacheImpl.size();
+            for (int i = 0; i < cacheSize; i++) {
+                AccessibilityNodeInfo info = mCacheImpl.valueAt(i);
+                if (!seen.contains(info)) {
+                    if (info.getWindowId() == windowId) {
+                        Log.e(LOG_TAG, "Disconneced node: ");
+                    } else {
+                        Log.e(LOG_TAG, "Node from: " + info.getWindowId() + " not from:"
+                                + windowId + " " + info);
+                    }
+                }
+            }
         }
     }
 }