| /* |
| * Copyright (C) 2012 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package android.view.accessibility; |
| |
| import android.os.Build; |
| import android.util.ArraySet; |
| import android.util.Log; |
| import android.util.LongArray; |
| import android.util.LongSparseArray; |
| import android.util.SparseArray; |
| |
| import java.util.ArrayList; |
| import java.util.List; |
| |
| /** |
| * Cache for AccessibilityWindowInfos and AccessibilityNodeInfos. |
| * It is updated when windows change or nodes change. |
| * @hide |
| */ |
| public class AccessibilityCache { |
| |
| private static final String LOG_TAG = "AccessibilityCache"; |
| |
| private static final boolean DEBUG = false; |
| |
| private static final boolean CHECK_INTEGRITY = Build.IS_ENG; |
| |
| /** |
| * {@link AccessibilityEvent} types that are critical for the cache to stay up to date |
| * |
| * When adding new event types in {@link #onAccessibilityEvent}, please add it here also, to |
| * make sure that the events are delivered to cache regardless of |
| * {@link android.accessibilityservice.AccessibilityServiceInfo#eventTypes} |
| */ |
| public static final int CACHE_CRITICAL_EVENTS_MASK = |
| AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED |
| | AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED |
| | AccessibilityEvent.TYPE_VIEW_FOCUSED |
| | AccessibilityEvent.TYPE_VIEW_SELECTED |
| | AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED |
| | AccessibilityEvent.TYPE_VIEW_CLICKED |
| | AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED |
| | AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED |
| | AccessibilityEvent.TYPE_VIEW_SCROLLED |
| | AccessibilityEvent.TYPE_WINDOWS_CHANGED |
| | AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED; |
| |
| private final Object mLock = new Object(); |
| |
| private final AccessibilityNodeRefresher mAccessibilityNodeRefresher; |
| |
| private long mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; |
| private long mInputFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; |
| |
| private boolean mIsAllWindowsCached; |
| |
| private final SparseArray<AccessibilityWindowInfo> mWindowCache = |
| new SparseArray<>(); |
| |
| private final SparseArray<LongSparseArray<AccessibilityNodeInfo>> mNodeCache = |
| new SparseArray<>(); |
| |
| private final SparseArray<AccessibilityWindowInfo> mTempWindowArray = |
| new SparseArray<>(); |
| |
| public AccessibilityCache(AccessibilityNodeRefresher nodeRefresher) { |
| mAccessibilityNodeRefresher = nodeRefresher; |
| } |
| |
| public void setWindows(List<AccessibilityWindowInfo> windows) { |
| synchronized (mLock) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "Set windows"); |
| } |
| clearWindowCache(); |
| if (windows == null) { |
| return; |
| } |
| final int windowCount = windows.size(); |
| for (int i = 0; i < windowCount; i++) { |
| final AccessibilityWindowInfo window = windows.get(i); |
| addWindow(window); |
| } |
| mIsAllWindowsCached = true; |
| } |
| } |
| |
| public void addWindow(AccessibilityWindowInfo window) { |
| synchronized (mLock) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "Caching window: " + window.getId()); |
| } |
| final int windowId = window.getId(); |
| AccessibilityWindowInfo oldWindow = mWindowCache.get(windowId); |
| if (oldWindow != null) { |
| oldWindow.recycle(); |
| } |
| mWindowCache.put(windowId, AccessibilityWindowInfo.obtain(window)); |
| } |
| } |
| |
| /** |
| * Notifies the cache that the something in the UI changed. As a result |
| * the cache will either refresh some nodes or evict some nodes. |
| * |
| * Note: any event that ends up affecting the cache should also be present in |
| * {@link #CACHE_CRITICAL_EVENTS_MASK} |
| * |
| * @param event An event. |
| */ |
| public void onAccessibilityEvent(AccessibilityEvent event) { |
| synchronized (mLock) { |
| final int eventType = event.getEventType(); |
| switch (eventType) { |
| case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED: { |
| if (mAccessibilityFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) { |
| refreshCachedNodeLocked(event.getWindowId(), mAccessibilityFocus); |
| } |
| mAccessibilityFocus = event.getSourceNodeId(); |
| refreshCachedNodeLocked(event.getWindowId(), mAccessibilityFocus); |
| } break; |
| |
| case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED: { |
| if (mAccessibilityFocus == event.getSourceNodeId()) { |
| refreshCachedNodeLocked(event.getWindowId(), mAccessibilityFocus); |
| mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; |
| } |
| } break; |
| |
| case AccessibilityEvent.TYPE_VIEW_FOCUSED: { |
| if (mInputFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) { |
| refreshCachedNodeLocked(event.getWindowId(), mInputFocus); |
| } |
| mInputFocus = event.getSourceNodeId(); |
| refreshCachedNodeLocked(event.getWindowId(), mInputFocus); |
| } break; |
| |
| case AccessibilityEvent.TYPE_VIEW_SELECTED: |
| case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED: |
| case AccessibilityEvent.TYPE_VIEW_CLICKED: |
| case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: { |
| refreshCachedNodeLocked(event.getWindowId(), event.getSourceNodeId()); |
| } break; |
| |
| case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED: { |
| synchronized (mLock) { |
| final int windowId = event.getWindowId(); |
| final long sourceId = event.getSourceNodeId(); |
| if ((event.getContentChangeTypes() |
| & AccessibilityEvent.CONTENT_CHANGE_TYPE_SUBTREE) != 0) { |
| clearSubTreeLocked(windowId, sourceId); |
| } else { |
| refreshCachedNodeLocked(windowId, sourceId); |
| } |
| } |
| } break; |
| |
| case AccessibilityEvent.TYPE_VIEW_SCROLLED: { |
| clearSubTreeLocked(event.getWindowId(), event.getSourceNodeId()); |
| } break; |
| |
| case AccessibilityEvent.TYPE_WINDOWS_CHANGED: |
| case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: { |
| clear(); |
| } break; |
| } |
| } |
| |
| if (CHECK_INTEGRITY) { |
| checkIntegrity(); |
| } |
| } |
| |
| private void refreshCachedNodeLocked(int windowId, long sourceId) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "Refreshing cached node."); |
| } |
| |
| LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); |
| if (nodes == null) { |
| return; |
| } |
| AccessibilityNodeInfo cachedInfo = nodes.get(sourceId); |
| // If the source is not in the cache - nothing to do. |
| if (cachedInfo == null) { |
| return; |
| } |
| // The node changed so we will just refresh it right now. |
| if (mAccessibilityNodeRefresher.refreshNode(cachedInfo, true)) { |
| return; |
| } |
| // Weird, we could not refresh. Just evict the entire sub-tree. |
| clearSubTreeLocked(windowId, sourceId); |
| } |
| |
| /** |
| * Gets a cached {@link AccessibilityNodeInfo} given the id of the hosting |
| * window and the accessibility id of the node. |
| * |
| * @param windowId The id of the window hosting the node. |
| * @param accessibilityNodeId The info accessibility node id. |
| * @return The cached {@link AccessibilityNodeInfo} or null if such not found. |
| */ |
| public AccessibilityNodeInfo getNode(int windowId, long accessibilityNodeId) { |
| synchronized(mLock) { |
| LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); |
| if (nodes == null) { |
| return null; |
| } |
| AccessibilityNodeInfo info = nodes.get(accessibilityNodeId); |
| if (info != null) { |
| // Return a copy since the client calls to AccessibilityNodeInfo#recycle() |
| // will wipe the data of the cached info. |
| info = AccessibilityNodeInfo.obtain(info); |
| } |
| if (DEBUG) { |
| Log.i(LOG_TAG, "get(" + accessibilityNodeId + ") = " + info); |
| } |
| return info; |
| } |
| } |
| |
| public List<AccessibilityWindowInfo> getWindows() { |
| synchronized (mLock) { |
| if (!mIsAllWindowsCached) { |
| return null; |
| } |
| |
| final int windowCount = mWindowCache.size(); |
| if (windowCount > 0) { |
| // Careful to return the windows in a decreasing layer order. |
| SparseArray<AccessibilityWindowInfo> sortedWindows = mTempWindowArray; |
| sortedWindows.clear(); |
| |
| for (int i = 0; i < windowCount; i++) { |
| AccessibilityWindowInfo window = mWindowCache.valueAt(i); |
| sortedWindows.put(window.getLayer(), window); |
| } |
| |
| // It's possible in transient conditions for two windows to share the same |
| // layer, which results in sortedWindows being smaller than mWindowCache |
| final int sortedWindowCount = sortedWindows.size(); |
| List<AccessibilityWindowInfo> windows = new ArrayList<>(sortedWindowCount); |
| for (int i = sortedWindowCount - 1; i >= 0; i--) { |
| AccessibilityWindowInfo window = sortedWindows.valueAt(i); |
| windows.add(AccessibilityWindowInfo.obtain(window)); |
| sortedWindows.removeAt(i); |
| } |
| |
| return windows; |
| } |
| return null; |
| } |
| } |
| |
| public AccessibilityWindowInfo getWindow(int windowId) { |
| synchronized (mLock) { |
| AccessibilityWindowInfo window = mWindowCache.get(windowId); |
| if (window != null) { |
| return AccessibilityWindowInfo.obtain(window); |
| } |
| return null; |
| } |
| } |
| |
| /** |
| * Caches an {@link AccessibilityNodeInfo}. |
| * |
| * @param info The node to cache. |
| */ |
| public void add(AccessibilityNodeInfo info) { |
| synchronized(mLock) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "add(" + info + ")"); |
| } |
| |
| final int windowId = info.getWindowId(); |
| LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); |
| if (nodes == null) { |
| nodes = new LongSparseArray<>(); |
| mNodeCache.put(windowId, nodes); |
| } |
| |
| final long sourceId = info.getSourceNodeId(); |
| AccessibilityNodeInfo oldInfo = nodes.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 remove the descendants that |
| // are no longer present. |
| final LongArray newChildrenIds = info.getChildNodeIds(); |
| |
| final int oldChildCount = oldInfo.getChildCount(); |
| for (int i = 0; i < oldChildCount; i++) { |
| if (nodes.get(sourceId) == null) { |
| // We've removed (and thus recycled) this node because it was its own |
| // ancestor (the app gave us bad data), we can't continue using it. |
| // Clear the cache for this window and give up on adding the node. |
| clearNodesForWindowLocked(windowId); |
| return; |
| } |
| final long oldChildId = oldInfo.getChildId(i); |
| // If the child is no longer present, remove the sub-tree. |
| if (newChildrenIds == null || newChildrenIds.indexOf(oldChildId) < 0) { |
| clearSubTreeLocked(windowId, oldChildId); |
| } |
| } |
| |
| // Also be careful if the parent has changed since the new |
| // parent may be a predecessor of the old parent which will |
| // add cycles to the cache. |
| final long oldParentId = oldInfo.getParentNodeId(); |
| if (info.getParentNodeId() != oldParentId) { |
| clearSubTreeLocked(windowId, oldParentId); |
| } else { |
| oldInfo.recycle(); |
| } |
| } |
| |
| // Cache a copy since the client calls to AccessibilityNodeInfo#recycle() |
| // will wipe the data of the cached info. |
| AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info); |
| nodes.put(sourceId, clone); |
| if (clone.isAccessibilityFocused()) { |
| mAccessibilityFocus = sourceId; |
| } |
| if (clone.isFocused()) { |
| mInputFocus = sourceId; |
| } |
| } |
| } |
| |
| /** |
| * Clears the cache. |
| */ |
| public void clear() { |
| synchronized(mLock) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "clear()"); |
| } |
| clearWindowCache(); |
| final int nodesForWindowCount = mNodeCache.size(); |
| for (int i = 0; i < nodesForWindowCount; i++) { |
| final int windowId = mNodeCache.keyAt(i); |
| clearNodesForWindowLocked(windowId); |
| } |
| |
| mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; |
| mInputFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; |
| } |
| } |
| |
| private void clearWindowCache() { |
| final int windowCount = mWindowCache.size(); |
| for (int i = windowCount - 1; i >= 0; i--) { |
| AccessibilityWindowInfo window = mWindowCache.valueAt(i); |
| window.recycle(); |
| mWindowCache.removeAt(i); |
| } |
| mIsAllWindowsCached = false; |
| } |
| |
| /** |
| * Clears nodes for the window with the given id |
| */ |
| private void clearNodesForWindowLocked(int windowId) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "clearNodesForWindowLocked(" + windowId + ")"); |
| } |
| LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); |
| if (nodes == null) { |
| return; |
| } |
| // Recycle the nodes before clearing the cache. |
| final int nodeCount = nodes.size(); |
| for (int i = nodeCount - 1; i >= 0; i--) { |
| AccessibilityNodeInfo info = nodes.valueAt(i); |
| nodes.removeAt(i); |
| info.recycle(); |
| } |
| mNodeCache.remove(windowId); |
| } |
| |
| /** |
| * Clears a subtree rooted at the node with the given id that is |
| * hosted in a given window. |
| * |
| * @param windowId The id of the hosting window. |
| * @param rootNodeId The root id. |
| */ |
| private void clearSubTreeLocked(int windowId, long rootNodeId) { |
| if (DEBUG) { |
| Log.i(LOG_TAG, "Clearing cached subtree."); |
| } |
| LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); |
| if (nodes != null) { |
| clearSubTreeRecursiveLocked(nodes, rootNodeId); |
| } |
| } |
| |
| /** |
| * Clears a subtree given a pointer to the root id and the nodes |
| * in the hosting window. |
| * |
| * @param nodes The nodes in the hosting window. |
| * @param rootNodeId The id of the root to evict. |
| * |
| * @return {@code true} if the cache was cleared |
| */ |
| private boolean clearSubTreeRecursiveLocked(LongSparseArray<AccessibilityNodeInfo> nodes, |
| long rootNodeId) { |
| AccessibilityNodeInfo current = nodes.get(rootNodeId); |
| if (current == null) { |
| // The node isn't in the cache, but its descendents might be. |
| clear(); |
| return true; |
| } |
| nodes.remove(rootNodeId); |
| final int childCount = current.getChildCount(); |
| for (int i = 0; i < childCount; i++) { |
| final long childNodeId = current.getChildId(i); |
| if (clearSubTreeRecursiveLocked(nodes, childNodeId)) { |
| current.recycle(); |
| return true; |
| } |
| } |
| current.recycle(); |
| return false; |
| } |
| |
| /** |
| * Check the integrity of the cache which is nodes from different windows |
| * are not mixed, there is a single active window, there is a single focused |
| * window, for every window there are no duplicates nodes, all nodes for a |
| * window are connected, for every window there is a single input focused |
| * node, and for every window there is a single accessibility focused node. |
| */ |
| public void checkIntegrity() { |
| synchronized (mLock) { |
| // Get the root. |
| if (mWindowCache.size() <= 0 && mNodeCache.size() == 0) { |
| return; |
| } |
| |
| AccessibilityWindowInfo focusedWindow = null; |
| AccessibilityWindowInfo activeWindow = null; |
| |
| final int windowCount = mWindowCache.size(); |
| for (int i = 0; i < windowCount; i++) { |
| AccessibilityWindowInfo window = mWindowCache.valueAt(i); |
| |
| // Check for one active window. |
| if (window.isActive()) { |
| if (activeWindow != null) { |
| Log.e(LOG_TAG, "Duplicate active window:" + window); |
| } else { |
| activeWindow = window; |
| } |
| } |
| |
| // Check for one focused window. |
| if (window.isFocused()) { |
| if (focusedWindow != null) { |
| Log.e(LOG_TAG, "Duplicate focused window:" + window); |
| } else { |
| focusedWindow = window; |
| } |
| } |
| } |
| |
| // Traverse the tree and do some checks. |
| AccessibilityNodeInfo accessFocus = null; |
| AccessibilityNodeInfo inputFocus = null; |
| |
| final int nodesForWindowCount = mNodeCache.size(); |
| for (int i = 0; i < nodesForWindowCount; i++) { |
| LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.valueAt(i); |
| if (nodes.size() <= 0) { |
| continue; |
| } |
| |
| ArraySet<AccessibilityNodeInfo> seen = new ArraySet<>(); |
| final int windowId = mNodeCache.keyAt(i); |
| |
| final int nodeCount = nodes.size(); |
| for (int j = 0; j < nodeCount; j++) { |
| AccessibilityNodeInfo node = nodes.valueAt(j); |
| |
| // Check for duplicates |
| if (!seen.add(node)) { |
| Log.e(LOG_TAG, "Duplicate node: " + node |
| + " in window:" + windowId); |
| // Stop now as we potentially found a loop. |
| continue; |
| } |
| |
| // Check for one accessibility focus. |
| if (node.isAccessibilityFocused()) { |
| if (accessFocus != null) { |
| Log.e(LOG_TAG, "Duplicate accessibility focus:" + node |
| + " in window:" + windowId); |
| } else { |
| accessFocus = node; |
| } |
| } |
| |
| // Check for one input focus. |
| if (node.isFocused()) { |
| if (inputFocus != null) { |
| Log.e(LOG_TAG, "Duplicate input focus: " + node |
| + " in window:" + windowId); |
| } else { |
| inputFocus = node; |
| } |
| } |
| |
| // The node should be a child of its parent if we have the parent. |
| AccessibilityNodeInfo nodeParent = nodes.get(node.getParentNodeId()); |
| if (nodeParent != null) { |
| boolean childOfItsParent = false; |
| final int childCount = nodeParent.getChildCount(); |
| for (int k = 0; k < childCount; k++) { |
| AccessibilityNodeInfo child = nodes.get(nodeParent.getChildId(k)); |
| if (child == node) { |
| childOfItsParent = true; |
| break; |
| } |
| } |
| if (!childOfItsParent) { |
| Log.e(LOG_TAG, "Invalid parent-child relation between parent: " |
| + nodeParent + " and child: " + node); |
| } |
| } |
| |
| // The node should be the parent of its child if we have the child. |
| final int childCount = node.getChildCount(); |
| for (int k = 0; k < childCount; k++) { |
| AccessibilityNodeInfo child = nodes.get(node.getChildId(k)); |
| if (child != null) { |
| AccessibilityNodeInfo parent = nodes.get(child.getParentNodeId()); |
| if (parent != node) { |
| Log.e(LOG_TAG, "Invalid child-parent relation between child: " |
| + node + " and parent: " + nodeParent); |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| // Layer of indirection included to break dependency chain for testing |
| public static class AccessibilityNodeRefresher { |
| public boolean refreshNode(AccessibilityNodeInfo info, boolean bypassCache) { |
| return info.refresh(null, bypassCache); |
| } |
| } |
| } |