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