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.Log; 21 import android.util.LongSparseArray; 22 import android.util.SparseLongArray; 23 24 import java.util.HashSet; 25 import java.util.LinkedList; 26 import java.util.Queue; 27 28 /** 29 * Simple cache for AccessibilityNodeInfos. The cache is mapping an 30 * accessibility id to an info. The cache allows storing of 31 * <code>null</code> values. It also tracks accessibility events 32 * and invalidates accordingly. 33 * 34 * @hide 35 */ 36 public class AccessibilityNodeInfoCache { 37 38 private static final String LOG_TAG = AccessibilityNodeInfoCache.class.getSimpleName(); 39 40 private static final boolean ENABLED = true; 41 42 private static final boolean DEBUG = false; 43 44 private static final boolean CHECK_INTEGRITY = true; 45 46 private final Object mLock = new Object(); 47 48 private final LongSparseArray<AccessibilityNodeInfo> mCacheImpl; 49 50 private int mWindowId; 51 52 public AccessibilityNodeInfoCache() { 53 if (ENABLED) { 54 mCacheImpl = new LongSparseArray<AccessibilityNodeInfo>(); 55 } else { 56 mCacheImpl = null; 57 } 58 } 59 60 /** 61 * The cache keeps track of {@link AccessibilityEvent}s and invalidates 62 * cached nodes as appropriate. 63 * 64 * @param event An event. 65 */ 66 public void onAccessibilityEvent(AccessibilityEvent event) { 67 if (ENABLED) { 68 final int eventType = event.getEventType(); 69 switch (eventType) { 70 case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: { 71 // New window so we clear the cache. 72 mWindowId = event.getWindowId(); 73 clear(); 74 } break; 75 case AccessibilityEvent.TYPE_VIEW_HOVER_ENTER: 76 case AccessibilityEvent.TYPE_VIEW_HOVER_EXIT: { 77 final int windowId = event.getWindowId(); 78 if (mWindowId != windowId) { 79 // New window so we clear the cache. 80 mWindowId = windowId; 81 clear(); 82 } 83 } break; 84 case AccessibilityEvent.TYPE_VIEW_FOCUSED: 85 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED: 86 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED: 87 case AccessibilityEvent.TYPE_VIEW_SELECTED: 88 case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED: 89 case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: { 90 // Since we prefetch the descendants of a node we 91 // just remove the entire subtree since when the node 92 // is fetched we will gets its descendant anyway. 93 synchronized (mLock) { 94 final long sourceId = event.getSourceNodeId(); 95 clearSubTreeLocked(sourceId); 96 if (eventType == AccessibilityEvent.TYPE_VIEW_FOCUSED) { 97 clearSubtreeWithOldInputFocusLocked(sourceId); 98 } 99 if (eventType == AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED) { 100 clearSubtreeWithOldAccessibilityFocusLocked(sourceId); 101 } 102 } 103 } break; 104 case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED: 105 case AccessibilityEvent.TYPE_VIEW_SCROLLED: { 106 synchronized (mLock) { 107 final long accessibilityNodeId = event.getSourceNodeId(); 108 clearSubTreeLocked(accessibilityNodeId); 109 } 110 } break; 111 } 112 if (Build.IS_DEBUGGABLE && CHECK_INTEGRITY) { 113 checkIntegrity(); 114 } 115 } 116 } 117 118 /** 119 * Gets a cached {@link AccessibilityNodeInfo} given its accessibility node id. 120 * 121 * @param accessibilityNodeId The info accessibility node id. 122 * @return The cached {@link AccessibilityNodeInfo} or null if such not found. 123 */ 124 public AccessibilityNodeInfo get(long accessibilityNodeId) { 125 if (ENABLED) { 126 synchronized(mLock) { 127 AccessibilityNodeInfo info = mCacheImpl.get(accessibilityNodeId); 128 if (info != null) { 129 // Return a copy since the client calls to AccessibilityNodeInfo#recycle() 130 // will wipe the data of the cached info. 131 info = AccessibilityNodeInfo.obtain(info); 132 } 133 if (DEBUG) { 134 Log.i(LOG_TAG, "get(" + accessibilityNodeId + ") = " + info); 135 } 136 return info; 137 } 138 } else { 139 return null; 140 } 141 } 142 143 /** 144 * Caches an {@link AccessibilityNodeInfo} given its accessibility node id. 145 * 146 * @param info The {@link AccessibilityNodeInfo} to cache. 147 */ 148 public void add(AccessibilityNodeInfo info) { 149 if (ENABLED) { 150 synchronized(mLock) { 151 if (DEBUG) { 152 Log.i(LOG_TAG, "add(" + info + ")"); 153 } 154 155 final long sourceId = info.getSourceNodeId(); 156 AccessibilityNodeInfo oldInfo = mCacheImpl.get(sourceId); 157 if (oldInfo != null) { 158 // If the added node is in the cache we have to be careful if 159 // the new one represents a source state where some of the 160 // children have been removed to avoid having disconnected 161 // subtrees in the cache. 162 SparseLongArray oldChildrenIds = oldInfo.getChildNodeIds(); 163 SparseLongArray newChildrenIds = info.getChildNodeIds(); 164 final int oldChildCount = oldChildrenIds.size(); 165 for (int i = 0; i < oldChildCount; i++) { 166 final long oldChildId = oldChildrenIds.valueAt(i); 167 if (newChildrenIds.indexOfValue(oldChildId) < 0) { 168 clearSubTreeLocked(oldChildId); 169 } 170 } 171 172 // Also be careful if the parent has changed since the new 173 // parent may be a predecessor of the old parent which will 174 // make the cached tree cyclic. 175 final long oldParentId = oldInfo.getParentNodeId(); 176 if (info.getParentNodeId() != oldParentId) { 177 clearSubTreeLocked(oldParentId); 178 } 179 } 180 181 // Cache a copy since the client calls to AccessibilityNodeInfo#recycle() 182 // will wipe the data of the cached info. 183 AccessibilityNodeInfo clone = AccessibilityNodeInfo.obtain(info); 184 mCacheImpl.put(sourceId, clone); 185 } 186 } 187 } 188 189 /** 190 * Clears the cache. 191 */ 192 public void clear() { 193 if (ENABLED) { 194 synchronized(mLock) { 195 if (DEBUG) { 196 Log.i(LOG_TAG, "clear()"); 197 } 198 // Recycle the nodes before clearing the cache. 199 final int nodeCount = mCacheImpl.size(); 200 for (int i = 0; i < nodeCount; i++) { 201 AccessibilityNodeInfo info = mCacheImpl.valueAt(i); 202 info.recycle(); 203 } 204 mCacheImpl.clear(); 205 } 206 } 207 } 208 209 /** 210 * Clears a subtree rooted at the node with the given id. 211 * 212 * @param rootNodeId The root id. 213 */ 214 private void clearSubTreeLocked(long rootNodeId) { 215 AccessibilityNodeInfo current = mCacheImpl.get(rootNodeId); 216 if (current == null) { 217 return; 218 } 219 mCacheImpl.remove(rootNodeId); 220 SparseLongArray childNodeIds = current.getChildNodeIds(); 221 final int childCount = childNodeIds.size(); 222 for (int i = 0; i < childCount; i++) { 223 final long childNodeId = childNodeIds.valueAt(i); 224 clearSubTreeLocked(childNodeId); 225 } 226 } 227 228 /** 229 * We are enforcing the invariant for a single input focus. 230 * 231 * @param currentInputFocusId The current input focused node. 232 */ 233 private void clearSubtreeWithOldInputFocusLocked(long currentInputFocusId) { 234 final int cacheSize = mCacheImpl.size(); 235 for (int i = 0; i < cacheSize; i++) { 236 AccessibilityNodeInfo info = mCacheImpl.valueAt(i); 237 final long infoSourceId = info.getSourceNodeId(); 238 if (infoSourceId != currentInputFocusId && info.isFocused()) { 239 clearSubTreeLocked(infoSourceId); 240 return; 241 } 242 } 243 } 244 245 /** 246 * We are enforcing the invariant for a single accessibility focus. 247 * 248 * @param currentAccessibilityFocusId The current input focused node. 249 */ 250 private void clearSubtreeWithOldAccessibilityFocusLocked(long currentAccessibilityFocusId) { 251 final int cacheSize = mCacheImpl.size(); 252 for (int i = 0; i < cacheSize; i++) { 253 AccessibilityNodeInfo info = mCacheImpl.valueAt(i); 254 final long infoSourceId = info.getSourceNodeId(); 255 if (infoSourceId != currentAccessibilityFocusId && info.isAccessibilityFocused()) { 256 clearSubTreeLocked(infoSourceId); 257 return; 258 } 259 } 260 } 261 262 /** 263 * Check the integrity of the cache which is it does not have nodes 264 * from more than one window, there are no duplicates, all nodes are 265 * connected, there is a single input focused node, and there is a 266 * single accessibility focused node. 267 */ 268 private void checkIntegrity() { 269 synchronized (mLock) { 270 // Get the root. 271 if (mCacheImpl.size() <= 0) { 272 return; 273 } 274 275 // If the cache is a tree it does not matter from 276 // which node we start to search for the root. 277 AccessibilityNodeInfo root = mCacheImpl.valueAt(0); 278 AccessibilityNodeInfo parent = root; 279 while (parent != null) { 280 root = parent; 281 parent = mCacheImpl.get(parent.getParentNodeId()); 282 } 283 284 // Traverse the tree and do some checks. 285 final int windowId = root.getWindowId(); 286 AccessibilityNodeInfo accessFocus = null; 287 AccessibilityNodeInfo inputFocus = null; 288 HashSet<AccessibilityNodeInfo> seen = new HashSet<AccessibilityNodeInfo>(); 289 Queue<AccessibilityNodeInfo> fringe = new LinkedList<AccessibilityNodeInfo>(); 290 fringe.add(root); 291 292 while (!fringe.isEmpty()) { 293 AccessibilityNodeInfo current = fringe.poll(); 294 // Check for duplicates 295 if (!seen.add(current)) { 296 Log.e(LOG_TAG, "Duplicate node: " + current); 297 return; 298 } 299 300 // Check for one accessibility focus. 301 if (current.isAccessibilityFocused()) { 302 if (accessFocus != null) { 303 Log.e(LOG_TAG, "Duplicate accessibility focus:" + current); 304 } else { 305 accessFocus = current; 306 } 307 } 308 309 // Check for one input focus. 310 if (current.isFocused()) { 311 if (inputFocus != null) { 312 Log.e(LOG_TAG, "Duplicate input focus: " + current); 313 } else { 314 inputFocus = current; 315 } 316 } 317 318 SparseLongArray childIds = current.getChildNodeIds(); 319 final int childCount = childIds.size(); 320 for (int i = 0; i < childCount; i++) { 321 final long childId = childIds.valueAt(i); 322 AccessibilityNodeInfo child = mCacheImpl.get(childId); 323 if (child != null) { 324 fringe.add(child); 325 } 326 } 327 } 328 329 // Check for disconnected nodes or ones from another window. 330 final int cacheSize = mCacheImpl.size(); 331 for (int i = 0; i < cacheSize; i++) { 332 AccessibilityNodeInfo info = mCacheImpl.valueAt(i); 333 if (!seen.contains(info)) { 334 if (info.getWindowId() == windowId) { 335 Log.e(LOG_TAG, "Disconneced node: "); 336 } else { 337 Log.e(LOG_TAG, "Node from: " + info.getWindowId() + " not from:" 338 + windowId + " " + info); 339 } 340 } 341 } 342 } 343 } 344 } 345
