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