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