1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.view.accessibility; 18 19 import android.os.Build; 20 import android.util.Log; 21 import android.util.LongSparseArray; 22 import android.util.SparseLongArray; 23 24 import java.util.HashSet; 25 import java.util.LinkedList; 26 import java.util.Queue; 27 28 /** 29 * Simple cache for AccessibilityNodeInfos. The cache is mapping an 30 * accessibility id to an info. The cache allows storing of 31 * <code>null</code> values. It also tracks accessibility events 32 * and invalidates accordingly. 33 * 34 * @hide 35 */ 36 public class AccessibilityNodeInfoCache { 37 38 private static final String LOG_TAG = AccessibilityNodeInfoCache.class.getSimpleName(); 39 40 private static final boolean ENABLED = true; 41 42 private static final boolean DEBUG = false; 43 44 private static final boolean CHECK_INTEGRITY_IF_DEBUGGABLE_BUILD = true; 45 46 private final Object mLock = new Object(); 47 48 private final LongSparseArray<AccessibilityNodeInfo> mCacheImpl; 49 50 private int mWindowId; 51 52 public AccessibilityNodeInfoCache() { 53 if (ENABLED) { 54 mCacheImpl = new LongSparseArray<AccessibilityNodeInfo>(); 55 } else { 56 mCacheImpl = null; 57 } 58 } 59 60 /** 61 * The cache keeps track of {@link AccessibilityEvent}s and invalidates 62 * cached nodes as appropriate. 63 * 64 * @param event An event. 65 */ 66 public void onAccessibilityEvent(AccessibilityEvent event) { 67 if (ENABLED) { 68 final int eventType = event.getEventType(); 69 switch (eventType) { 70 case AccessibilityEvent.TYPE_TOUCH_EXPLORATION_GESTURE_END: 71 case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: 72 case AccessibilityEvent.TYPE_VIEW_HOVER_ENTER: 73 case AccessibilityEvent.TYPE_VIEW_HOVER_EXIT: { 74 // If the active window changes, clear the cache. 75 final int windowId = event.getWindowId(); 76 if (mWindowId != windowId) { 77 mWindowId = windowId; 78 clear(); 79 } 80 } break; 81 case AccessibilityEvent.TYPE_VIEW_FOCUSED: 82 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED: 83 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED: 84 case AccessibilityEvent.TYPE_VIEW_SELECTED: 85 case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED: 86 case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: { 87 refreshCachedNode(event.getSourceNodeId()); 88 } break; 89 case AccessibilityEvent.TYPE_VIEW_SCROLLED: { 90 synchronized (mLock) { 91 clearSubTreeLocked(event.getSourceNodeId()); 92 } 93 } break; 94 case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED: { 95 synchronized (mLock) { 96 final long sourceId = event.getSourceNodeId(); 97 if ((event.getContentChangeTypes() 98 & AccessibilityEvent.CONTENT_CHANGE_TYPE_SUBTREE) != 0) { 99 clearSubTreeLocked(sourceId); 100 } else { 101 refreshCachedNode(sourceId); 102 } 103 } 104 } break; 105 } 106 if (CHECK_INTEGRITY_IF_DEBUGGABLE_BUILD && Build.IS_DEBUGGABLE) { 107 checkIntegrity(); 108 } 109 } 110 } 111 112 private void refreshCachedNode(long sourceId) { 113 if (DEBUG) { 114 Log.i(LOG_TAG, "Refreshing cached node."); 115 } 116 synchronized (mLock) { 117 AccessibilityNodeInfo cachedInfo = mCacheImpl.get(sourceId); 118 // If the source is not in the cache - nothing to do. 119 if (cachedInfo == null) { 120 return; 121 } 122 // The node changed so we will just refresh it right now. 123 if (cachedInfo.refresh(true)) { 124 return; 125 } 126 // Weird, we could not refresh. Just evict the entire sub-tree. 127 clearSubTreeLocked(sourceId); 128 } 129 } 130 131 /** 132 * Gets a cached {@link AccessibilityNodeInfo} given its accessibility node id. 133 * 134 * @param accessibilityNodeId The info accessibility node id. 135 * @return The cached {@link AccessibilityNodeInfo} or null if such not found. 136 */ 137 public AccessibilityNodeInfo get(long accessibilityNodeId) { 138 if (ENABLED) { 139 synchronized(mLock) { 140 AccessibilityNodeInfo info = mCacheImpl.get(accessibilityNodeId); 141 if (info != null) { 142 // Return a copy since the client calls to AccessibilityNodeInfo#recycle() 143 // will wipe the data of the cached info. 144 info = AccessibilityNodeInfo.obtain(info); 145 } 146 if (DEBUG) { 147 Log.i(LOG_TAG, "get(" + accessibilityNodeId + ") = " + info); 148 } 149 return info; 150 } 151 } else { 152 return null; 153 } 154 } 155 156 /** 157 * Caches an {@link AccessibilityNodeInfo} given its accessibility node id. 158 * 159 * @param info The {@link AccessibilityNodeInfo} to cache. 160 */ 161 public void add(AccessibilityNodeInfo info) { 162 if (ENABLED) { 163 synchronized(mLock) { 164 if (DEBUG) { 165 Log.i(LOG_TAG, "add(" + info + ")"); 166 } 167 168 final long sourceId = info.getSourceNodeId(); 169 AccessibilityNodeInfo oldInfo = mCacheImpl.get(sourceId); 170 if (oldInfo != null) { 171 // If the added node is in the cache we have to be careful if 172 // the new one represents a source state where some of the 173 // children have been removed to avoid having disconnected 174 // subtrees in the cache. 175 SparseLongArray oldChildrenIds = oldInfo.getChildNodeIds(); 176 SparseLongArray newChildrenIds = info.getChildNodeIds(); 177 final int oldChildCount = oldChildrenIds.size(); 178 for (int i = 0; i < oldChildCount; i++) { 179 final long oldChildId = oldChildrenIds.valueAt(i); 180 if (newChildrenIds.indexOfValue(oldChildId) < 0) { 181 clearSubTreeLocked(oldChildId); 182 } 183 } 184 185 // Also be careful if the parent has changed since the new 186 // parent may be a predecessor of the old parent which will 187 // make the cached tree cyclic. 188 final long oldParentId = oldInfo.getParentNodeId(); 189 if (info.getParentNodeId() != oldParentId) { 190 clearSubTreeLocked(oldParentId); 191 } 192 } 193 194 // Cache a copy since the client calls to AccessibilityNodeInfo#recycle() 195 // will wipe the data of the cached info. 196 AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info); 197 mCacheImpl.put(sourceId, clone); 198 } 199 } 200 } 201 202 /** 203 * Clears the cache. 204 */ 205 public void clear() { 206 if (ENABLED) { 207 synchronized(mLock) { 208 if (DEBUG) { 209 Log.i(LOG_TAG, "clear()"); 210 } 211 // Recycle the nodes before clearing the cache. 212 final int nodeCount = mCacheImpl.size(); 213 for (int i = 0; i < nodeCount; i++) { 214 AccessibilityNodeInfo info = mCacheImpl.valueAt(i); 215 info.recycle(); 216 } 217 mCacheImpl.clear(); 218 } 219 } 220 } 221 222 /** 223 * Clears a subtree rooted at the node with the given id. 224 * 225 * @param rootNodeId The root id. 226 */ 227 private void clearSubTreeLocked(long rootNodeId) { 228 if (DEBUG) { 229 Log.i(LOG_TAG, "Clearing cached subtree."); 230 } 231 clearSubTreeRecursiveLocked(rootNodeId); 232 } 233 234 private void clearSubTreeRecursiveLocked(long rootNodeId) { 235 AccessibilityNodeInfo current = mCacheImpl.get(rootNodeId); 236 if (current == null) { 237 return; 238 } 239 mCacheImpl.remove(rootNodeId); 240 SparseLongArray childNodeIds = current.getChildNodeIds(); 241 final int childCount = childNodeIds.size(); 242 for (int i = 0; i < childCount; i++) { 243 final long childNodeId = childNodeIds.valueAt(i); 244 clearSubTreeRecursiveLocked(childNodeId); 245 } 246 } 247 248 /** 249 * Check the integrity of the cache which is it does not have nodes 250 * from more than one window, there are no duplicates, all nodes are 251 * connected, there is a single input focused node, and there is a 252 * single accessibility focused node. 253 */ 254 private void checkIntegrity() { 255 synchronized (mLock) { 256 // Get the root. 257 if (mCacheImpl.size() <= 0) { 258 return; 259 } 260 261 // If the cache is a tree it does not matter from 262 // which node we start to search for the root. 263 AccessibilityNodeInfo root = mCacheImpl.valueAt(0); 264 AccessibilityNodeInfo parent = root; 265 while (parent != null) { 266 root = parent; 267 parent = mCacheImpl.get(parent.getParentNodeId()); 268 } 269 270 // Traverse the tree and do some checks. 271 final int windowId = root.getWindowId(); 272 AccessibilityNodeInfo accessFocus = null; 273 AccessibilityNodeInfo inputFocus = null; 274 HashSet<AccessibilityNodeInfo> seen = new HashSet<AccessibilityNodeInfo>(); 275 Queue<AccessibilityNodeInfo> fringe = new LinkedList<AccessibilityNodeInfo>(); 276 fringe.add(root); 277 278 while (!fringe.isEmpty()) { 279 AccessibilityNodeInfo current = fringe.poll(); 280 // Check for duplicates 281 if (!seen.add(current)) { 282 Log.e(LOG_TAG, "Duplicate node: " + current); 283 return; 284 } 285 286 // Check for one accessibility focus. 287 if (current.isAccessibilityFocused()) { 288 if (accessFocus != null) { 289 Log.e(LOG_TAG, "Duplicate accessibility focus:" + current); 290 } else { 291 accessFocus = current; 292 } 293 } 294 295 // Check for one input focus. 296 if (current.isFocused()) { 297 if (inputFocus != null) { 298 Log.e(LOG_TAG, "Duplicate input focus: " + current); 299 } else { 300 inputFocus = current; 301 } 302 } 303 304 SparseLongArray childIds = current.getChildNodeIds(); 305 final int childCount = childIds.size(); 306 for (int i = 0; i < childCount; i++) { 307 final long childId = childIds.valueAt(i); 308 AccessibilityNodeInfo child = mCacheImpl.get(childId); 309 if (child != null) { 310 fringe.add(child); 311 } 312 } 313 } 314 315 // Check for disconnected nodes or ones from another window. 316 for (int i = 0; i < mCacheImpl.size(); i++) { 317 AccessibilityNodeInfo info = mCacheImpl.valueAt(i); 318 if (!seen.contains(info)) { 319 if (info.getWindowId() == windowId) { 320 Log.e(LOG_TAG, "Disconneced node: " + info); 321 } else { 322 Log.e(LOG_TAG, "Node from: " + info.getWindowId() + " not from:" 323 + windowId + " " + info); 324 } 325 } 326 } 327 } 328 } 329 } 330
