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.ArraySet; 21 import android.util.Log; 22 import android.util.LongArray; 23 import android.util.LongSparseArray; 24 import android.util.SparseArray; 25 26 import java.util.ArrayList; 27 import java.util.List; 28 29 /** 30 * Cache for AccessibilityWindowInfos and AccessibilityNodeInfos. 31 * It is updated when windows change or nodes change. 32 * @hide 33 */ 34 public class AccessibilityCache { 35 36 private static final String LOG_TAG = "AccessibilityCache"; 37 38 private static final boolean DEBUG = false; 39 40 private static final boolean CHECK_INTEGRITY = Build.IS_ENG; 41 42 /** 43 * {@link AccessibilityEvent} types that are critical for the cache to stay up to date 44 * 45 * When adding new event types in {@link #onAccessibilityEvent}, please add it here also, to 46 * make sure that the events are delivered to cache regardless of 47 * {@link android.accessibilityservice.AccessibilityServiceInfo#eventTypes} 48 */ 49 public static final int CACHE_CRITICAL_EVENTS_MASK = 50 AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED 51 | AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED 52 | AccessibilityEvent.TYPE_VIEW_FOCUSED 53 | AccessibilityEvent.TYPE_VIEW_SELECTED 54 | AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED 55 | AccessibilityEvent.TYPE_VIEW_CLICKED 56 | AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED 57 | AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED 58 | AccessibilityEvent.TYPE_VIEW_SCROLLED 59 | AccessibilityEvent.TYPE_WINDOWS_CHANGED 60 | AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED; 61 62 private final Object mLock = new Object(); 63 64 private final AccessibilityNodeRefresher mAccessibilityNodeRefresher; 65 66 private long mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; 67 private long mInputFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; 68 69 private boolean mIsAllWindowsCached; 70 71 private final SparseArray<AccessibilityWindowInfo> mWindowCache = 72 new SparseArray<>(); 73 74 private final SparseArray<LongSparseArray<AccessibilityNodeInfo>> mNodeCache = 75 new SparseArray<>(); 76 77 private final SparseArray<AccessibilityWindowInfo> mTempWindowArray = 78 new SparseArray<>(); 79 80 public AccessibilityCache(AccessibilityNodeRefresher nodeRefresher) { 81 mAccessibilityNodeRefresher = nodeRefresher; 82 } 83 84 public void setWindows(List<AccessibilityWindowInfo> windows) { 85 synchronized (mLock) { 86 if (DEBUG) { 87 Log.i(LOG_TAG, "Set windows"); 88 } 89 clearWindowCache(); 90 if (windows == null) { 91 return; 92 } 93 final int windowCount = windows.size(); 94 for (int i = 0; i < windowCount; i++) { 95 final AccessibilityWindowInfo window = windows.get(i); 96 addWindow(window); 97 } 98 mIsAllWindowsCached = true; 99 } 100 } 101 102 public void addWindow(AccessibilityWindowInfo window) { 103 synchronized (mLock) { 104 if (DEBUG) { 105 Log.i(LOG_TAG, "Caching window: " + window.getId()); 106 } 107 final int windowId = window.getId(); 108 AccessibilityWindowInfo oldWindow = mWindowCache.get(windowId); 109 if (oldWindow != null) { 110 oldWindow.recycle(); 111 } 112 mWindowCache.put(windowId, AccessibilityWindowInfo.obtain(window)); 113 } 114 } 115 116 /** 117 * Notifies the cache that the something in the UI changed. As a result 118 * the cache will either refresh some nodes or evict some nodes. 119 * 120 * Note: any event that ends up affecting the cache should also be present in 121 * {@link #CACHE_CRITICAL_EVENTS_MASK} 122 * 123 * @param event An event. 124 */ 125 public void onAccessibilityEvent(AccessibilityEvent event) { 126 synchronized (mLock) { 127 final int eventType = event.getEventType(); 128 switch (eventType) { 129 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED: { 130 if (mAccessibilityFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) { 131 refreshCachedNodeLocked(event.getWindowId(), mAccessibilityFocus); 132 } 133 mAccessibilityFocus = event.getSourceNodeId(); 134 refreshCachedNodeLocked(event.getWindowId(), mAccessibilityFocus); 135 } break; 136 137 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED: { 138 if (mAccessibilityFocus == event.getSourceNodeId()) { 139 refreshCachedNodeLocked(event.getWindowId(), mAccessibilityFocus); 140 mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; 141 } 142 } break; 143 144 case AccessibilityEvent.TYPE_VIEW_FOCUSED: { 145 if (mInputFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) { 146 refreshCachedNodeLocked(event.getWindowId(), mInputFocus); 147 } 148 mInputFocus = event.getSourceNodeId(); 149 refreshCachedNodeLocked(event.getWindowId(), mInputFocus); 150 } break; 151 152 case AccessibilityEvent.TYPE_VIEW_SELECTED: 153 case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED: 154 case AccessibilityEvent.TYPE_VIEW_CLICKED: 155 case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: { 156 refreshCachedNodeLocked(event.getWindowId(), event.getSourceNodeId()); 157 } break; 158 159 case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED: { 160 synchronized (mLock) { 161 final int windowId = event.getWindowId(); 162 final long sourceId = event.getSourceNodeId(); 163 if ((event.getContentChangeTypes() 164 & AccessibilityEvent.CONTENT_CHANGE_TYPE_SUBTREE) != 0) { 165 clearSubTreeLocked(windowId, sourceId); 166 } else { 167 refreshCachedNodeLocked(windowId, sourceId); 168 } 169 } 170 } break; 171 172 case AccessibilityEvent.TYPE_VIEW_SCROLLED: { 173 clearSubTreeLocked(event.getWindowId(), event.getSourceNodeId()); 174 } break; 175 176 case AccessibilityEvent.TYPE_WINDOWS_CHANGED: 177 case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: { 178 clear(); 179 } break; 180 } 181 } 182 183 if (CHECK_INTEGRITY) { 184 checkIntegrity(); 185 } 186 } 187 188 private void refreshCachedNodeLocked(int windowId, long sourceId) { 189 if (DEBUG) { 190 Log.i(LOG_TAG, "Refreshing cached node."); 191 } 192 193 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 194 if (nodes == null) { 195 return; 196 } 197 AccessibilityNodeInfo cachedInfo = nodes.get(sourceId); 198 // If the source is not in the cache - nothing to do. 199 if (cachedInfo == null) { 200 return; 201 } 202 // The node changed so we will just refresh it right now. 203 if (mAccessibilityNodeRefresher.refreshNode(cachedInfo, true)) { 204 return; 205 } 206 // Weird, we could not refresh. Just evict the entire sub-tree. 207 clearSubTreeLocked(windowId, sourceId); 208 } 209 210 /** 211 * Gets a cached {@link AccessibilityNodeInfo} given the id of the hosting 212 * window and the accessibility id of the node. 213 * 214 * @param windowId The id of the window hosting the node. 215 * @param accessibilityNodeId The info accessibility node id. 216 * @return The cached {@link AccessibilityNodeInfo} or null if such not found. 217 */ 218 public AccessibilityNodeInfo getNode(int windowId, long accessibilityNodeId) { 219 synchronized(mLock) { 220 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 221 if (nodes == null) { 222 return null; 223 } 224 AccessibilityNodeInfo info = nodes.get(accessibilityNodeId); 225 if (info != null) { 226 // Return a copy since the client calls to AccessibilityNodeInfo#recycle() 227 // will wipe the data of the cached info. 228 info = AccessibilityNodeInfo.obtain(info); 229 } 230 if (DEBUG) { 231 Log.i(LOG_TAG, "get(" + accessibilityNodeId + ") = " + info); 232 } 233 return info; 234 } 235 } 236 237 public List<AccessibilityWindowInfo> getWindows() { 238 synchronized (mLock) { 239 if (!mIsAllWindowsCached) { 240 return null; 241 } 242 243 final int windowCount = mWindowCache.size(); 244 if (windowCount > 0) { 245 // Careful to return the windows in a decreasing layer order. 246 SparseArray<AccessibilityWindowInfo> sortedWindows = mTempWindowArray; 247 sortedWindows.clear(); 248 249 for (int i = 0; i < windowCount; i++) { 250 AccessibilityWindowInfo window = mWindowCache.valueAt(i); 251 sortedWindows.put(window.getLayer(), window); 252 } 253 254 // It's possible in transient conditions for two windows to share the same 255 // layer, which results in sortedWindows being smaller than mWindowCache 256 final int sortedWindowCount = sortedWindows.size(); 257 List<AccessibilityWindowInfo> windows = new ArrayList<>(sortedWindowCount); 258 for (int i = sortedWindowCount - 1; i >= 0; i--) { 259 AccessibilityWindowInfo window = sortedWindows.valueAt(i); 260 windows.add(AccessibilityWindowInfo.obtain(window)); 261 sortedWindows.removeAt(i); 262 } 263 264 return windows; 265 } 266 return null; 267 } 268 } 269 270 public AccessibilityWindowInfo getWindow(int windowId) { 271 synchronized (mLock) { 272 AccessibilityWindowInfo window = mWindowCache.get(windowId); 273 if (window != null) { 274 return AccessibilityWindowInfo.obtain(window); 275 } 276 return null; 277 } 278 } 279 280 /** 281 * Caches an {@link AccessibilityNodeInfo}. 282 * 283 * @param info The node to cache. 284 */ 285 public void add(AccessibilityNodeInfo info) { 286 synchronized(mLock) { 287 if (DEBUG) { 288 Log.i(LOG_TAG, "add(" + info + ")"); 289 } 290 291 final int windowId = info.getWindowId(); 292 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 293 if (nodes == null) { 294 nodes = new LongSparseArray<>(); 295 mNodeCache.put(windowId, nodes); 296 } 297 298 final long sourceId = info.getSourceNodeId(); 299 AccessibilityNodeInfo oldInfo = nodes.get(sourceId); 300 if (oldInfo != null) { 301 // If the added node is in the cache we have to be careful if 302 // the new one represents a source state where some of the 303 // children have been removed to remove the descendants that 304 // are no longer present. 305 final LongArray newChildrenIds = info.getChildNodeIds(); 306 307 final int oldChildCount = oldInfo.getChildCount(); 308 for (int i = 0; i < oldChildCount; i++) { 309 if (nodes.get(sourceId) == null) { 310 // We've removed (and thus recycled) this node because it was its own 311 // ancestor (the app gave us bad data), we can't continue using it. 312 // Clear the cache for this window and give up on adding the node. 313 clearNodesForWindowLocked(windowId); 314 return; 315 } 316 final long oldChildId = oldInfo.getChildId(i); 317 // If the child is no longer present, remove the sub-tree. 318 if (newChildrenIds == null || newChildrenIds.indexOf(oldChildId) < 0) { 319 clearSubTreeLocked(windowId, oldChildId); 320 } 321 } 322 323 // Also be careful if the parent has changed since the new 324 // parent may be a predecessor of the old parent which will 325 // add cycles to the cache. 326 final long oldParentId = oldInfo.getParentNodeId(); 327 if (info.getParentNodeId() != oldParentId) { 328 clearSubTreeLocked(windowId, oldParentId); 329 } else { 330 oldInfo.recycle(); 331 } 332 } 333 334 // Cache a copy since the client calls to AccessibilityNodeInfo#recycle() 335 // will wipe the data of the cached info. 336 AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info); 337 nodes.put(sourceId, clone); 338 if (clone.isAccessibilityFocused()) { 339 mAccessibilityFocus = sourceId; 340 } 341 if (clone.isFocused()) { 342 mInputFocus = sourceId; 343 } 344 } 345 } 346 347 /** 348 * Clears the cache. 349 */ 350 public void clear() { 351 synchronized(mLock) { 352 if (DEBUG) { 353 Log.i(LOG_TAG, "clear()"); 354 } 355 clearWindowCache(); 356 final int nodesForWindowCount = mNodeCache.size(); 357 for (int i = 0; i < nodesForWindowCount; i++) { 358 final int windowId = mNodeCache.keyAt(i); 359 clearNodesForWindowLocked(windowId); 360 } 361 362 mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; 363 mInputFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID; 364 } 365 } 366 367 private void clearWindowCache() { 368 final int windowCount = mWindowCache.size(); 369 for (int i = windowCount - 1; i >= 0; i--) { 370 AccessibilityWindowInfo window = mWindowCache.valueAt(i); 371 window.recycle(); 372 mWindowCache.removeAt(i); 373 } 374 mIsAllWindowsCached = false; 375 } 376 377 /** 378 * Clears nodes for the window with the given id 379 */ 380 private void clearNodesForWindowLocked(int windowId) { 381 if (DEBUG) { 382 Log.i(LOG_TAG, "clearNodesForWindowLocked(" + windowId + ")"); 383 } 384 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 385 if (nodes == null) { 386 return; 387 } 388 // Recycle the nodes before clearing the cache. 389 final int nodeCount = nodes.size(); 390 for (int i = nodeCount - 1; i >= 0; i--) { 391 AccessibilityNodeInfo info = nodes.valueAt(i); 392 nodes.removeAt(i); 393 info.recycle(); 394 } 395 mNodeCache.remove(windowId); 396 } 397 398 /** 399 * Clears a subtree rooted at the node with the given id that is 400 * hosted in a given window. 401 * 402 * @param windowId The id of the hosting window. 403 * @param rootNodeId The root id. 404 */ 405 private void clearSubTreeLocked(int windowId, long rootNodeId) { 406 if (DEBUG) { 407 Log.i(LOG_TAG, "Clearing cached subtree."); 408 } 409 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId); 410 if (nodes != null) { 411 clearSubTreeRecursiveLocked(nodes, rootNodeId); 412 } 413 } 414 415 /** 416 * Clears a subtree given a pointer to the root id and the nodes 417 * in the hosting window. 418 * 419 * @param nodes The nodes in the hosting window. 420 * @param rootNodeId The id of the root to evict. 421 */ 422 private void clearSubTreeRecursiveLocked(LongSparseArray<AccessibilityNodeInfo> nodes, 423 long rootNodeId) { 424 AccessibilityNodeInfo current = nodes.get(rootNodeId); 425 if (current == null) { 426 return; 427 } 428 nodes.remove(rootNodeId); 429 final int childCount = current.getChildCount(); 430 for (int i = 0; i < childCount; i++) { 431 final long childNodeId = current.getChildId(i); 432 clearSubTreeRecursiveLocked(nodes, childNodeId); 433 } 434 current.recycle(); 435 } 436 437 /** 438 * Check the integrity of the cache which is nodes from different windows 439 * are not mixed, there is a single active window, there is a single focused 440 * window, for every window there are no duplicates nodes, all nodes for a 441 * window are connected, for every window there is a single input focused 442 * node, and for every window there is a single accessibility focused node. 443 */ 444 public void checkIntegrity() { 445 synchronized (mLock) { 446 // Get the root. 447 if (mWindowCache.size() <= 0 && mNodeCache.size() == 0) { 448 return; 449 } 450 451 AccessibilityWindowInfo focusedWindow = null; 452 AccessibilityWindowInfo activeWindow = null; 453 454 final int windowCount = mWindowCache.size(); 455 for (int i = 0; i < windowCount; i++) { 456 AccessibilityWindowInfo window = mWindowCache.valueAt(i); 457 458 // Check for one active window. 459 if (window.isActive()) { 460 if (activeWindow != null) { 461 Log.e(LOG_TAG, "Duplicate active window:" + window); 462 } else { 463 activeWindow = window; 464 } 465 } 466 467 // Check for one focused window. 468 if (window.isFocused()) { 469 if (focusedWindow != null) { 470 Log.e(LOG_TAG, "Duplicate focused window:" + window); 471 } else { 472 focusedWindow = window; 473 } 474 } 475 } 476 477 // Traverse the tree and do some checks. 478 AccessibilityNodeInfo accessFocus = null; 479 AccessibilityNodeInfo inputFocus = null; 480 481 final int nodesForWindowCount = mNodeCache.size(); 482 for (int i = 0; i < nodesForWindowCount; i++) { 483 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.valueAt(i); 484 if (nodes.size() <= 0) { 485 continue; 486 } 487 488 ArraySet<AccessibilityNodeInfo> seen = new ArraySet<>(); 489 final int windowId = mNodeCache.keyAt(i); 490 491 final int nodeCount = nodes.size(); 492 for (int j = 0; j < nodeCount; j++) { 493 AccessibilityNodeInfo node = nodes.valueAt(j); 494 495 // Check for duplicates 496 if (!seen.add(node)) { 497 Log.e(LOG_TAG, "Duplicate node: " + node 498 + " in window:" + windowId); 499 // Stop now as we potentially found a loop. 500 continue; 501 } 502 503 // Check for one accessibility focus. 504 if (node.isAccessibilityFocused()) { 505 if (accessFocus != null) { 506 Log.e(LOG_TAG, "Duplicate accessibility focus:" + node 507 + " in window:" + windowId); 508 } else { 509 accessFocus = node; 510 } 511 } 512 513 // Check for one input focus. 514 if (node.isFocused()) { 515 if (inputFocus != null) { 516 Log.e(LOG_TAG, "Duplicate input focus: " + node 517 + " in window:" + windowId); 518 } else { 519 inputFocus = node; 520 } 521 } 522 523 // The node should be a child of its parent if we have the parent. 524 AccessibilityNodeInfo nodeParent = nodes.get(node.getParentNodeId()); 525 if (nodeParent != null) { 526 boolean childOfItsParent = false; 527 final int childCount = nodeParent.getChildCount(); 528 for (int k = 0; k < childCount; k++) { 529 AccessibilityNodeInfo child = nodes.get(nodeParent.getChildId(k)); 530 if (child == node) { 531 childOfItsParent = true; 532 break; 533 } 534 } 535 if (!childOfItsParent) { 536 Log.e(LOG_TAG, "Invalid parent-child relation between parent: " 537 + nodeParent + " and child: " + node); 538 } 539 } 540 541 // The node should be the parent of its child if we have the child. 542 final int childCount = node.getChildCount(); 543 for (int k = 0; k < childCount; k++) { 544 AccessibilityNodeInfo child = nodes.get(node.getChildId(k)); 545 if (child != null) { 546 AccessibilityNodeInfo parent = nodes.get(child.getParentNodeId()); 547 if (parent != node) { 548 Log.e(LOG_TAG, "Invalid child-parent relation between child: " 549 + node + " and parent: " + nodeParent); 550 } 551 } 552 } 553 } 554 } 555 } 556 } 557 558 // Layer of indirection included to break dependency chain for testing 559 public static class AccessibilityNodeRefresher { 560 public boolean refreshNode(AccessibilityNodeInfo info, boolean bypassCache) { 561 return info.refresh(null, bypassCache); 562 } 563 } 564 } 565
