AccessibilityCache.java revision 0322100598e3afae207bb98202b9ce53604bdb28
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 17package android.view.accessibility; 18 19import android.os.Build; 20import android.util.ArraySet; 21import android.util.Log; 22import android.util.LongArray; 23import android.util.LongSparseArray; 24import android.util.SparseArray; 25 26import java.util.ArrayList; 27import java.util.List; 28 29/** 30 * Cache for AccessibilityWindowInfos and AccessibilityNodeInfos. 31 * It is updated when windows change or nodes change. 32 */ 33final class AccessibilityCache { 34 35 private static final String LOG_TAG = "AccessibilityCache"; 36 37 private static final boolean DEBUG = false; 38 39 private static final boolean CHECK_INTEGRITY = "eng".equals(Build.TYPE); 40 41 private final Object mLock = new Object(); 42 43 private final SparseArray<AccessibilityWindowInfo> mWindowCache = 44 new SparseArray<>(); 45 46 private final SparseArray<LongSparseArray<AccessibilityNodeInfo>> mNodeCache = 47 new SparseArray<>(); 48 49 private final SparseArray<AccessibilityWindowInfo> mTempWindowArray = 50 new SparseArray<>(); 51 52 public void addWindow(AccessibilityWindowInfo window) { 53 synchronized (mLock) { 54 if (DEBUG) { 55 Log.i(LOG_TAG, "Caching window: " + window.getId()); 56 } 57 final int windowId = window.getId(); 58 AccessibilityWindowInfo oldWindow = mWindowCache.get(windowId); 59 if (oldWindow != null) { 60 oldWindow.recycle(); 61 } 62 mWindowCache.put(windowId, AccessibilityWindowInfo.obtain(window)); 63 } 64 } 65 66 /** 67 * Notifies the cache that the something in the UI changed. As a result 68 * the cache will either refresh some nodes or evict some nodes. 69 * 70 * @param event An event. 71 */ 72 public void onAccessibilityEvent(AccessibilityEvent event) { 73 synchronized (mLock) { 74 final int eventType = event.getEventType(); 75 switch (eventType) { 76 case AccessibilityEvent.TYPE_VIEW_FOCUSED: 77 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED: 78 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED: 79 case AccessibilityEvent.TYPE_VIEW_SELECTED: 80 case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED: 81 case AccessibilityEvent.TYPE_VIEW_CLICKED: 82 case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: { 83 refreshCachedNodeLocked(event.getWindowId(), event.getSourceNodeId()); 84 } break; 85 86 case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED: { 87 synchronized (mLock) { 88 final int windowId = event.getWindowId(); 89 final long sourceId = event.getSourceNodeId(); 90 if ((event.getContentChangeTypes() 91 & AccessibilityEvent.CONTENT_CHANGE_TYPE_SUBTREE) != 0) { 92 clearSubTreeLocked(windowId, sourceId); 93 } else { 94 refreshCachedNodeLocked(windowId, sourceId); 95 } 96 } 97 } break; 98 99 case AccessibilityEvent.TYPE_VIEW_SCROLLED: { 100 clearSubTreeLocked(event.getWindowId(), event.getSourceNodeId()); 101 } break; 102 103 case AccessibilityEvent.TYPE_WINDOWS_CHANGED: 104 case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: { 105 clear(); 106 } break; 107 } 108 } 109 110 if (CHECK_INTEGRITY) { 111 checkIntegrity(); 112 } 113 } 114 115 private void refreshCachedNodeLocked(int windowId, long sourceId) { 116 if (DEBUG) { 117 Log.i(LOG_TAG, "Refreshing cached node."); 118 } 119 120 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 121 if (nodes == null) { 122 return; 123 } 124 AccessibilityNodeInfo cachedInfo = nodes.get(sourceId); 125 // If the source is not in the cache - nothing to do. 126 if (cachedInfo == null) { 127 return; 128 } 129 // The node changed so we will just refresh it right now. 130 if (cachedInfo.refresh(true)) { 131 return; 132 } 133 // Weird, we could not refresh. Just evict the entire sub-tree. 134 clearSubTreeLocked(windowId, sourceId); 135 } 136 137 /** 138 * Gets a cached {@link AccessibilityNodeInfo} given the id of the hosting 139 * window and the accessibility id of the node. 140 * 141 * @param windowId The id of the window hosting the node. 142 * @param accessibilityNodeId The info accessibility node id. 143 * @return The cached {@link AccessibilityNodeInfo} or null if such not found. 144 */ 145 public AccessibilityNodeInfo getNode(int windowId, long accessibilityNodeId) { 146 synchronized(mLock) { 147 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 148 if (nodes == null) { 149 return null; 150 } 151 AccessibilityNodeInfo info = nodes.get(accessibilityNodeId); 152 if (info != null) { 153 // Return a copy since the client calls to AccessibilityNodeInfo#recycle() 154 // will wipe the data of the cached info. 155 info = AccessibilityNodeInfo.obtain(info); 156 } 157 if (DEBUG) { 158 Log.i(LOG_TAG, "get(" + accessibilityNodeId + ") = " + info); 159 } 160 return info; 161 } 162 } 163 164 public List<AccessibilityWindowInfo> getWindows() { 165 synchronized (mLock) { 166 final int windowCount = mWindowCache.size(); 167 if (windowCount > 0) { 168 // Careful to return the windows in a decreasing layer order. 169 SparseArray<AccessibilityWindowInfo> sortedWindows = mTempWindowArray; 170 sortedWindows.clear(); 171 172 for (int i = 0; i < windowCount; i++) { 173 AccessibilityWindowInfo window = mWindowCache.valueAt(i); 174 sortedWindows.put(window.getLayer(), window); 175 } 176 177 List<AccessibilityWindowInfo> windows = new ArrayList<>(windowCount); 178 for (int i = windowCount - 1; i >= 0; i--) { 179 AccessibilityWindowInfo window = sortedWindows.valueAt(i); 180 windows.add(AccessibilityWindowInfo.obtain(window)); 181 sortedWindows.removeAt(i); 182 } 183 184 return windows; 185 } 186 return null; 187 } 188 } 189 190 public AccessibilityWindowInfo getWindow(int windowId) { 191 synchronized (mLock) { 192 AccessibilityWindowInfo window = mWindowCache.get(windowId); 193 if (window != null) { 194 return AccessibilityWindowInfo.obtain(window); 195 } 196 return null; 197 } 198 } 199 200 /** 201 * Caches an {@link AccessibilityNodeInfo}. 202 * 203 * @param info The node to cache. 204 */ 205 public void add(AccessibilityNodeInfo info) { 206 synchronized(mLock) { 207 if (DEBUG) { 208 Log.i(LOG_TAG, "add(" + info + ")"); 209 } 210 211 final int windowId = info.getWindowId(); 212 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 213 if (nodes == null) { 214 nodes = new LongSparseArray<>(); 215 mNodeCache.put(windowId, nodes); 216 } 217 218 final long sourceId = info.getSourceNodeId(); 219 AccessibilityNodeInfo oldInfo = nodes.get(sourceId); 220 if (oldInfo != null) { 221 // If the added node is in the cache we have to be careful if 222 // the new one represents a source state where some of the 223 // children have been removed to remove the descendants that 224 // are no longer present. 225 final LongArray newChildrenIds = info.getChildNodeIds(); 226 227 final int oldChildCount = oldInfo.getChildCount(); 228 for (int i = 0; i < oldChildCount; i++) { 229 final long oldChildId = oldInfo.getChildId(i); 230 // If the child is no longer present, remove the sub-tree. 231 if (newChildrenIds == null || newChildrenIds.indexOf(oldChildId) < 0) { 232 clearSubTreeLocked(windowId, oldChildId); 233 } 234 } 235 236 // Also be careful if the parent has changed since the new 237 // parent may be a predecessor of the old parent which will 238 // add cyclse to the cache. 239 final long oldParentId = oldInfo.getParentNodeId(); 240 if (info.getParentNodeId() != oldParentId) { 241 clearSubTreeLocked(windowId, oldParentId); 242 } 243 } 244 245 // Cache a copy since the client calls to AccessibilityNodeInfo#recycle() 246 // will wipe the data of the cached info. 247 AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info); 248 nodes.put(sourceId, clone); 249 } 250 } 251 252 /** 253 * Clears the cache. 254 */ 255 public void clear() { 256 synchronized(mLock) { 257 if (DEBUG) { 258 Log.i(LOG_TAG, "clear()"); 259 } 260 final int windowCount = mWindowCache.size(); 261 for (int i = windowCount - 1; i >= 0; i--) { 262 AccessibilityWindowInfo window = mWindowCache.valueAt(i); 263 window.recycle(); 264 mWindowCache.removeAt(i); 265 } 266 final int nodesForWindowCount = mNodeCache.size(); 267 for (int i = 0; i < nodesForWindowCount; i++) { 268 final int windowId = mNodeCache.keyAt(i); 269 clearNodesForWindowLocked(windowId); 270 } 271 } 272 } 273 274 private void clearNodesForWindowLocked(int windowId) { 275 if (DEBUG) { 276 Log.i(LOG_TAG, "clearNodesForWindowLocked(" + windowId + ")"); 277 } 278 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 279 if (nodes == null) { 280 return; 281 } 282 // Recycle the nodes before clearing the cache. 283 final int nodeCount = nodes.size(); 284 for (int i = nodeCount - 1; i >= 0; i--) { 285 AccessibilityNodeInfo info = nodes.valueAt(i); 286 nodes.removeAt(i); 287 info.recycle(); 288 } 289 mNodeCache.remove(windowId); 290 } 291 292 /** 293 * Clears a subtree rooted at the node with the given id that is 294 * hosted in a given window. 295 * 296 * @param windowId The id of the hosting window. 297 * @param rootNodeId The root id. 298 */ 299 private void clearSubTreeLocked(int windowId, long rootNodeId) { 300 if (DEBUG) { 301 Log.i(LOG_TAG, "Clearing cached subtree."); 302 } 303 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 304 if (nodes != null) { 305 clearSubTreeRecursiveLocked(nodes, rootNodeId); 306 } 307 } 308 309 /** 310 * Clears a subtree given a pointer to the root id and the nodes 311 * in the hosting window. 312 * 313 * @param nodes The nodes in the hosting window. 314 * @param rootNodeId The id of the root to evict. 315 */ 316 private void clearSubTreeRecursiveLocked(LongSparseArray<AccessibilityNodeInfo> nodes, 317 long rootNodeId) { 318 AccessibilityNodeInfo current = nodes.get(rootNodeId); 319 if (current == null) { 320 return; 321 } 322 nodes.remove(rootNodeId); 323 final int childCount = current.getChildCount(); 324 for (int i = 0; i < childCount; i++) { 325 final long childNodeId = current.getChildId(i); 326 clearSubTreeRecursiveLocked(nodes, childNodeId); 327 } 328 } 329 330 /** 331 * Check the integrity of the cache which is nodes from different windows 332 * are not mixed, there is a single active window, there is a single focused 333 * window, for every window there are no duplicates nodes, all nodes for a 334 * window are connected, for every window there is a single input focused 335 * node, and for every window there is a single accessibility focused node. 336 */ 337 public void checkIntegrity() { 338 synchronized (mLock) { 339 // Get the root. 340 if (mWindowCache.size() <= 0 && mNodeCache.size() == 0) { 341 return; 342 } 343 344 AccessibilityWindowInfo focusedWindow = null; 345 AccessibilityWindowInfo activeWindow = null; 346 347 final int windowCount = mWindowCache.size(); 348 for (int i = 0; i < windowCount; i++) { 349 AccessibilityWindowInfo window = mWindowCache.valueAt(i); 350 351 // Check for one active window. 352 if (window.isActive()) { 353 if (activeWindow != null) { 354 Log.e(LOG_TAG, "Duplicate active window:" + window); 355 } else { 356 activeWindow = window; 357 } 358 } 359 360 // Check for one focused window. 361 if (window.isFocused()) { 362 if (focusedWindow != null) { 363 Log.e(LOG_TAG, "Duplicate focused window:" + window); 364 } else { 365 focusedWindow = window; 366 } 367 } 368 } 369 370 // Traverse the tree and do some checks. 371 AccessibilityNodeInfo accessFocus = null; 372 AccessibilityNodeInfo inputFocus = null; 373 374 final int nodesForWindowCount = mNodeCache.size(); 375 for (int i = 0; i < nodesForWindowCount; i++) { 376 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.valueAt(i); 377 if (nodes.size() <= 0) { 378 continue; 379 } 380 381 ArraySet<AccessibilityNodeInfo> seen = new ArraySet<>(); 382 final int windowId = mNodeCache.keyAt(i); 383 384 final int nodeCount = nodes.size(); 385 for (int j = 0; j < nodeCount; j++) { 386 AccessibilityNodeInfo node = nodes.valueAt(j); 387 388 // Check for duplicates 389 if (!seen.add(node)) { 390 Log.e(LOG_TAG, "Duplicate node: " + node 391 + " in window:" + windowId); 392 // Stop now as we potentially found a loop. 393 continue; 394 } 395 396 // Check for one accessibility focus. 397 if (node.isAccessibilityFocused()) { 398 if (accessFocus != null) { 399 Log.e(LOG_TAG, "Duplicate accessibility focus:" + node 400 + " in window:" + windowId); 401 } else { 402 accessFocus = node; 403 } 404 } 405 406 // Check for one input focus. 407 if (node.isFocused()) { 408 if (inputFocus != null) { 409 Log.e(LOG_TAG, "Duplicate input focus: " + node 410 + " in window:" + windowId); 411 } else { 412 inputFocus = node; 413 } 414 } 415 416 // The node should be a child of its parent if we have the parent. 417 AccessibilityNodeInfo nodeParent = nodes.get(node.getParentNodeId()); 418 if (nodeParent != null) { 419 boolean childOfItsParent = false; 420 final int childCount = nodeParent.getChildCount(); 421 for (int k = 0; k < childCount; k++) { 422 AccessibilityNodeInfo child = nodes.get(nodeParent.getChildId(k)); 423 if (child == node) { 424 childOfItsParent = true; 425 break; 426 } 427 } 428 if (!childOfItsParent) { 429 Log.e(LOG_TAG, "Invalid parent-child relation between parent: " 430 + nodeParent + " and child: " + node); 431 } 432 } 433 434 // The node should be the parent of its child if we have the child. 435 final int childCount = node.getChildCount(); 436 for (int k = 0; k < childCount; k++) { 437 AccessibilityNodeInfo child = nodes.get(node.getChildId(k)); 438 if (child != null) { 439 AccessibilityNodeInfo parent = nodes.get(child.getParentNodeId()); 440 if (parent != node) { 441 Log.e(LOG_TAG, "Invalid child-parent relation between child: " 442 + node + " and parent: " + nodeParent); 443 } 444 } 445 } 446 } 447 } 448 } 449 } 450} 451