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