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