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