• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
20 import static android.view.accessibility.AccessibilityNodeInfo.FOCUS_ACCESSIBILITY;
21 
22 import android.annotation.Nullable;
23 import android.os.Build;
24 import android.os.SystemClock;
25 import android.util.ArraySet;
26 import android.util.Log;
27 import android.util.LongArray;
28 import android.util.LongSparseArray;
29 import android.util.SparseArray;
30 
31 import java.util.ArrayList;
32 import java.util.List;
33 
34 /**
35  * Cache for AccessibilityWindowInfos and AccessibilityNodeInfos.
36  * It is updated when windows change or nodes change.
37  * @hide
38  */
39 public class AccessibilityCache {
40 
41     private static final String LOG_TAG = "AccessibilityCache";
42 
43     private static final boolean DEBUG = Log.isLoggable(LOG_TAG, Log.DEBUG) && Build.IS_DEBUGGABLE;
44 
45     private static final boolean VERBOSE =
46             Log.isLoggable(LOG_TAG, Log.VERBOSE) && Build.IS_DEBUGGABLE;
47 
48     private static final boolean CHECK_INTEGRITY = Build.IS_ENG;
49 
50     private boolean mEnabled = true;
51 
52     private final SparseArray<String> mWindowIdToEventSourceClassName = new SparseArray<>();
53 
54     /**
55      * {@link AccessibilityEvent} types that are critical for the cache to stay up to date
56      *
57      * When adding new event types in {@link #onAccessibilityEvent}, please add it here also, to
58      * make sure that the events are delivered to cache regardless of
59      * {@link android.accessibilityservice.AccessibilityServiceInfo#eventTypes}
60      */
61     public static final int CACHE_CRITICAL_EVENTS_MASK =
62             AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED
63                     | AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED
64                     | AccessibilityEvent.TYPE_VIEW_FOCUSED
65                     | AccessibilityEvent.TYPE_VIEW_SELECTED
66                     | AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED
67                     | AccessibilityEvent.TYPE_VIEW_CLICKED
68                     | AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED
69                     | AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED
70                     | AccessibilityEvent.TYPE_VIEW_SCROLLED
71                     | AccessibilityEvent.TYPE_WINDOWS_CHANGED
72                     | AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED;
73 
74     private final Object mLock = new Object();
75 
76     private final AccessibilityNodeRefresher mAccessibilityNodeRefresher;
77 
78     private OnNodeAddedListener mOnNodeAddedListener;
79 
80     private long mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID;
81     private long mInputFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID;
82     /**
83      * The event time of the {@link AccessibilityEvent} which presents the populated windows cache
84      * before it is stale.
85      */
86     private long mValidWindowCacheTimeStamp = 0;
87 
88     private int mAccessibilityFocusedWindow = AccessibilityWindowInfo.UNDEFINED_WINDOW_ID;
89     private int mInputFocusWindow = AccessibilityWindowInfo.UNDEFINED_WINDOW_ID;
90 
91     private boolean mIsAllWindowsCached;
92 
93     // The SparseArray of all {@link AccessibilityWindowInfo}s on all displays.
94     // The key of outer SparseArray is display ID and the key of inner SparseArray is window ID.
95     private final SparseArray<SparseArray<AccessibilityWindowInfo>> mWindowCacheByDisplay =
96             new SparseArray<>();
97 
98     private final SparseArray<LongSparseArray<AccessibilityNodeInfo>> mNodeCache =
99             new SparseArray<>();
100 
101     private final SparseArray<AccessibilityWindowInfo> mTempWindowArray =
102             new SparseArray<>();
103 
AccessibilityCache(AccessibilityNodeRefresher nodeRefresher)104     public AccessibilityCache(AccessibilityNodeRefresher nodeRefresher) {
105         mAccessibilityNodeRefresher = nodeRefresher;
106     }
107 
108     /** Returns if the cache is enabled. */
isEnabled()109     public boolean isEnabled() {
110         synchronized (mLock) {
111             return mEnabled;
112         }
113     }
114 
115     /** Sets enabled status. */
setEnabled(boolean enabled)116     public void setEnabled(boolean enabled) {
117         synchronized (mLock) {
118             mEnabled = enabled;
119             clear();
120         }
121     }
122 
123     /**
124      * Sets all {@link AccessibilityWindowInfo}s of all displays into the cache.
125      * The key of SparseArray is display ID.
126      *
127      * @param windowsOnAllDisplays The accessibility windows of all displays.
128      * @param populationTimeStamp The timestamp from {@link SystemClock#uptimeMillis()} when the
129      *                            client requests the data.
130      */
setWindowsOnAllDisplays( SparseArray<List<AccessibilityWindowInfo>> windowsOnAllDisplays, long populationTimeStamp)131     public void setWindowsOnAllDisplays(
132             SparseArray<List<AccessibilityWindowInfo>> windowsOnAllDisplays,
133             long populationTimeStamp) {
134         synchronized (mLock) {
135             if (!mEnabled) {
136                 if (DEBUG) {
137                     Log.i(LOG_TAG, "Cache is disabled");
138                 }
139                 return;
140             }
141             if (DEBUG) {
142                 Log.i(LOG_TAG, "Set windows");
143             }
144             if (mValidWindowCacheTimeStamp > populationTimeStamp) {
145                 // Discard the windows because it might be stale.
146                 return;
147             }
148             clearWindowCacheLocked();
149             if (windowsOnAllDisplays == null) {
150                 return;
151             }
152 
153             final int displayCounts = windowsOnAllDisplays.size();
154             for (int i = 0; i < displayCounts; i++) {
155                 final List<AccessibilityWindowInfo> windowsOfDisplay =
156                         windowsOnAllDisplays.valueAt(i);
157 
158                 if (windowsOfDisplay == null) {
159                     continue;
160                 }
161 
162                 final int displayId = windowsOnAllDisplays.keyAt(i);
163                 final int windowCount = windowsOfDisplay.size();
164                 for (int j = 0; j < windowCount; j++) {
165                     addWindowByDisplayLocked(displayId, windowsOfDisplay.get(j));
166                 }
167             }
168             mIsAllWindowsCached = true;
169         }
170     }
171 
172     /**
173      * Sets an {@link AccessibilityWindowInfo} into the cache.
174      *
175      * @param window The accessibility window.
176      */
addWindow(AccessibilityWindowInfo window)177     public void addWindow(AccessibilityWindowInfo window) {
178         synchronized (mLock) {
179             if (!mEnabled) {
180                 if (DEBUG) {
181                     Log.i(LOG_TAG, "Cache is disabled");
182                 }
183                 return;
184             }
185             if (DEBUG) {
186                 Log.i(LOG_TAG, "Caching window: " + window.getId() + " at display Id [ "
187                         + window.getDisplayId() + " ]");
188             }
189             addWindowByDisplayLocked(window.getDisplayId(), window);
190         }
191     }
192 
addWindowByDisplayLocked(int displayId, AccessibilityWindowInfo window)193     private void addWindowByDisplayLocked(int displayId, AccessibilityWindowInfo window) {
194         SparseArray<AccessibilityWindowInfo> windows = mWindowCacheByDisplay.get(displayId);
195         if (windows == null) {
196             windows = new SparseArray<>();
197             mWindowCacheByDisplay.put(displayId, windows);
198         }
199         final int windowId = window.getId();
200         windows.put(windowId, new AccessibilityWindowInfo(window));
201     }
202     /**
203      * Notifies the cache that the something in the UI changed. As a result
204      * the cache will either refresh some nodes or evict some nodes.
205      *
206      * Note: any event that ends up affecting the cache should also be present in
207      * {@link #CACHE_CRITICAL_EVENTS_MASK}
208      *
209      * @param event An event.
210      */
onAccessibilityEvent(AccessibilityEvent event)211     public void onAccessibilityEvent(AccessibilityEvent event) {
212         AccessibilityNodeInfo nodeToRefresh = null;
213         synchronized (mLock) {
214             if (!mEnabled) {
215                 if (DEBUG) {
216                     Log.i(LOG_TAG, "Cache is disabled");
217                 }
218                 return;
219             }
220             if (DEBUG) {
221                 Log.i(LOG_TAG, "onAccessibilityEvent(" + event + ")");
222             }
223             final int eventType = event.getEventType();
224             switch (eventType) {
225                 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUSED: {
226                     if (mAccessibilityFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) {
227                         removeCachedNodeLocked(mAccessibilityFocusedWindow, mAccessibilityFocus);
228                     }
229                     mAccessibilityFocus = event.getSourceNodeId();
230                     mAccessibilityFocusedWindow = event.getWindowId();
231                     nodeToRefresh = removeCachedNodeLocked(mAccessibilityFocusedWindow,
232                             mAccessibilityFocus);
233                 } break;
234 
235                 case AccessibilityEvent.TYPE_VIEW_ACCESSIBILITY_FOCUS_CLEARED: {
236                     if (mAccessibilityFocus == event.getSourceNodeId()
237                             && mAccessibilityFocusedWindow == event.getWindowId()) {
238                         nodeToRefresh = removeCachedNodeLocked(mAccessibilityFocusedWindow,
239                                 mAccessibilityFocus);
240                         mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID;
241                         mAccessibilityFocusedWindow = AccessibilityWindowInfo.UNDEFINED_WINDOW_ID;
242                     }
243                 } break;
244 
245                 case AccessibilityEvent.TYPE_VIEW_FOCUSED: {
246                     if (mInputFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID) {
247                         removeCachedNodeLocked(event.getWindowId(), mInputFocus);
248                     }
249                     mInputFocus = event.getSourceNodeId();
250                     mInputFocusWindow = event.getWindowId();
251                     nodeToRefresh = removeCachedNodeLocked(event.getWindowId(), mInputFocus);
252                 } break;
253 
254                 case AccessibilityEvent.TYPE_VIEW_SELECTED:
255                 case AccessibilityEvent.TYPE_VIEW_TEXT_CHANGED:
256                 case AccessibilityEvent.TYPE_VIEW_CLICKED:
257                 case AccessibilityEvent.TYPE_VIEW_TEXT_SELECTION_CHANGED: {
258                     nodeToRefresh = removeCachedNodeLocked(event.getWindowId(),
259                             event.getSourceNodeId());
260                 } break;
261 
262                 case AccessibilityEvent.TYPE_WINDOW_CONTENT_CHANGED: {
263                     synchronized (mLock) {
264                         final int windowId = event.getWindowId();
265                         final long sourceId = event.getSourceNodeId();
266                         if ((event.getContentChangeTypes()
267                                 & AccessibilityEvent.CONTENT_CHANGE_TYPE_SUBTREE) != 0) {
268                             clearSubTreeLocked(windowId, sourceId);
269                         } else {
270                             nodeToRefresh = removeCachedNodeLocked(windowId, sourceId);
271                         }
272                     }
273                 } break;
274 
275                 case AccessibilityEvent.TYPE_VIEW_SCROLLED: {
276                     clearSubTreeLocked(event.getWindowId(), event.getSourceNodeId());
277                 } break;
278 
279                 case AccessibilityEvent.TYPE_WINDOWS_CHANGED: {
280                     mValidWindowCacheTimeStamp = event.getEventTime();
281                     if (event.getWindowChanges() == AccessibilityEvent.WINDOWS_CHANGE_REMOVED) {
282                         mWindowIdToEventSourceClassName.remove(event.getWindowId());
283                     }
284                     if (event.getWindowChanges()
285                             == AccessibilityEvent.WINDOWS_CHANGE_ACCESSIBILITY_FOCUSED) {
286                         // Don't need to clear all cache. Unless the changes are related to
287                         // content, we won't clear all cache here with clear().
288                         clearWindowCacheLocked();
289                         break;
290                     }
291                     clear();
292                 }
293                 break;
294                 case AccessibilityEvent.TYPE_WINDOW_STATE_CHANGED: {
295                     mValidWindowCacheTimeStamp = event.getEventTime();
296                     if (event.getContentChangeTypes() == 0 && event.getClassName() != null) {
297                         mWindowIdToEventSourceClassName.put(event.getWindowId(),
298                                 event.getClassName().toString());
299                     }
300                     clear();
301                 } break;
302             }
303         }
304 
305         if (nodeToRefresh != null) {
306             if (DEBUG) {
307                 Log.i(LOG_TAG, "Refreshing and re-adding cached node.");
308             }
309             if (mAccessibilityNodeRefresher.refreshNode(nodeToRefresh, true)) {
310                 add(nodeToRefresh);
311             }
312         }
313         if (CHECK_INTEGRITY) {
314             checkIntegrity();
315         }
316     }
317 
removeCachedNodeLocked(int windowId, long sourceId)318     private AccessibilityNodeInfo removeCachedNodeLocked(int windowId, long sourceId) {
319         if (DEBUG) {
320             Log.i(LOG_TAG, "Removing cached node.");
321         }
322         LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId);
323         if (nodes == null) {
324             return null;
325         }
326         AccessibilityNodeInfo cachedInfo = nodes.get(sourceId);
327         // If the source is not in the cache - nothing to do.
328         if (cachedInfo == null) {
329             return null;
330         }
331         nodes.remove(sourceId);
332         return cachedInfo;
333     }
334 
335     /**
336      * Gets a cached {@link AccessibilityNodeInfo} given the id of the hosting
337      * window and the accessibility id of the node.
338      *
339      * @param windowId The id of the window hosting the node.
340      * @param accessibilityNodeId The info accessibility node id.
341      * @return The cached {@link AccessibilityNodeInfo} or null if such not found.
342      */
getNode(int windowId, long accessibilityNodeId)343     public AccessibilityNodeInfo getNode(int windowId, long accessibilityNodeId) {
344         synchronized(mLock) {
345             if (!mEnabled) {
346                 if (DEBUG) {
347                     Log.i(LOG_TAG, "Cache is disabled");
348                 }
349                 return null;
350             }
351             LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId);
352             if (nodes == null) {
353                 return null;
354             }
355             AccessibilityNodeInfo info = nodes.get(accessibilityNodeId);
356             if (info != null) {
357                 // Return a copy since the client calls to AccessibilityNodeInfo#recycle()
358                 // will wipe the data of the cached info.
359                 info = new AccessibilityNodeInfo(info);
360             }
361             if (VERBOSE) {
362                 Log.i(LOG_TAG, "get(0x" + Long.toHexString(accessibilityNodeId) + ") = " + info);
363             }
364             return info;
365         }
366     }
367 
368     /** Returns {@code true} if {@code info} is in the cache. */
isNodeInCache(AccessibilityNodeInfo info)369     public boolean isNodeInCache(AccessibilityNodeInfo info) {
370         if (info == null) {
371             return false;
372         }
373         int windowId = info.getWindowId();
374         long accessibilityNodeId = info.getSourceNodeId();
375         synchronized (mLock) {
376             if (!mEnabled) {
377                 if (DEBUG) {
378                     Log.i(LOG_TAG, "Cache is disabled");
379                 }
380                 return false;
381             }
382             LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId);
383             if (nodes == null) {
384                 return false;
385             }
386             return nodes.get(accessibilityNodeId) != null;
387         }
388     }
389 
390     /**
391      * Gets all {@link AccessibilityWindowInfo}s of all displays from the cache.
392      *
393      * @return All cached {@link AccessibilityWindowInfo}s of all displays
394      *         or null if such not found. The key of SparseArray is display ID.
395      */
getWindowsOnAllDisplays()396     public SparseArray<List<AccessibilityWindowInfo>> getWindowsOnAllDisplays() {
397         synchronized (mLock) {
398             if (!mEnabled) {
399                 if (DEBUG) {
400                     Log.i(LOG_TAG, "Cache is disabled");
401                 }
402                 return null;
403             }
404             if (!mIsAllWindowsCached) {
405                 return null;
406             }
407             final SparseArray<List<AccessibilityWindowInfo>> returnWindows = new SparseArray<>();
408             final int displayCounts = mWindowCacheByDisplay.size();
409 
410             if (displayCounts > 0) {
411                 for (int i = 0; i < displayCounts; i++) {
412                     final int displayId = mWindowCacheByDisplay.keyAt(i);
413                     final SparseArray<AccessibilityWindowInfo> windowsOfDisplay =
414                             mWindowCacheByDisplay.valueAt(i);
415 
416                     if (windowsOfDisplay == null) {
417                         continue;
418                     }
419 
420                     final int windowCount = windowsOfDisplay.size();
421                     if (windowCount > 0) {
422                         // Careful to return the windows in a decreasing layer order.
423                         SparseArray<AccessibilityWindowInfo> sortedWindows = mTempWindowArray;
424                         sortedWindows.clear();
425 
426                         for (int j = 0; j < windowCount; j++) {
427                             AccessibilityWindowInfo window = windowsOfDisplay.valueAt(j);
428                             sortedWindows.put(window.getLayer(), window);
429                         }
430 
431                         // It's possible in transient conditions for two windows to share the same
432                         // layer, which results in sortedWindows being smaller than
433                         // mWindowCacheByDisplay
434                         final int sortedWindowCount = sortedWindows.size();
435                         List<AccessibilityWindowInfo> windows =
436                                 new ArrayList<>(sortedWindowCount);
437                         for (int j = sortedWindowCount - 1; j >= 0; j--) {
438                             AccessibilityWindowInfo window = sortedWindows.valueAt(j);
439                             windows.add(new AccessibilityWindowInfo(window));
440                             sortedWindows.removeAt(j);
441                         }
442                         returnWindows.put(displayId, windows);
443                     }
444                 }
445                 return returnWindows;
446             }
447             return null;
448         }
449     }
450 
451     /**
452      * Gets an {@link AccessibilityWindowInfo} by windowId.
453      *
454      * @param windowId The id of the window.
455      *
456      * @return The {@link AccessibilityWindowInfo} or null if such not found.
457      */
getWindow(int windowId)458     public AccessibilityWindowInfo getWindow(int windowId) {
459         synchronized (mLock) {
460             if (!mEnabled) {
461                 if (DEBUG) {
462                     Log.i(LOG_TAG, "Cache is disabled");
463                 }
464                 return null;
465             }
466             final int displayCounts = mWindowCacheByDisplay.size();
467             for (int i = 0; i < displayCounts; i++) {
468                 final SparseArray<AccessibilityWindowInfo> windowsOfDisplay =
469                         mWindowCacheByDisplay.valueAt(i);
470                 if (windowsOfDisplay == null) {
471                     continue;
472                 }
473 
474                 AccessibilityWindowInfo window = windowsOfDisplay.get(windowId);
475                 if (window != null) {
476                     return new AccessibilityWindowInfo(window);
477                 }
478             }
479             return null;
480         }
481     }
482 
483     /**
484      * Caches an {@link AccessibilityNodeInfo}.
485      *
486      * @param info The node to cache.
487      */
add(AccessibilityNodeInfo info)488     public void add(AccessibilityNodeInfo info) {
489         synchronized(mLock) {
490             if (!mEnabled) {
491                 if (DEBUG) {
492                     Log.i(LOG_TAG, "Cache is disabled");
493                 }
494                 return;
495             }
496             if (VERBOSE) {
497                 Log.i(LOG_TAG, "add(" + info + ")");
498             }
499 
500             final int windowId = info.getWindowId();
501             LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId);
502             if (nodes == null) {
503                 nodes = new LongSparseArray<>();
504                 mNodeCache.put(windowId, nodes);
505             }
506 
507             final long sourceId = info.getSourceNodeId();
508             AccessibilityNodeInfo oldInfo = nodes.get(sourceId);
509             if (oldInfo != null) {
510                 // If the added node is in the cache we have to be careful if
511                 // the new one represents a source state where some of the
512                 // children have been removed to remove the descendants that
513                 // are no longer present.
514                 final LongArray newChildrenIds = info.getChildNodeIds();
515 
516                 final int oldChildCount = oldInfo.getChildCount();
517                 for (int i = 0; i < oldChildCount; i++) {
518                     final long oldChildId = oldInfo.getChildId(i);
519                     // If the child is no longer present, remove the sub-tree.
520                     if (newChildrenIds == null || newChildrenIds.indexOf(oldChildId) < 0) {
521                         clearSubTreeLocked(windowId, oldChildId);
522                     }
523                     if (nodes.get(sourceId) == null) {
524                         // We've removed (and thus recycled) this node because it was its own
525                         // ancestor (the app gave us bad data), we can't continue using it.
526                         // Clear the cache for this window and give up on adding the node.
527                         clearNodesForWindowLocked(windowId);
528                         return;
529                     }
530                 }
531 
532                 // Also be careful if the parent has changed since the new
533                 // parent may be a predecessor of the old parent which will
534                 // add cycles to the cache.
535                 final long oldParentId = oldInfo.getParentNodeId();
536                 if (info.getParentNodeId() != oldParentId) {
537                     clearSubTreeLocked(windowId, oldParentId);
538                 }
539            }
540 
541             // Cache a copy since the client calls to AccessibilityNodeInfo#recycle()
542             // will wipe the data of the cached info.
543             AccessibilityNodeInfo clone = new AccessibilityNodeInfo(info);
544             nodes.put(sourceId, clone);
545             if (clone.isAccessibilityFocused()) {
546                 if (mAccessibilityFocus != AccessibilityNodeInfo.UNDEFINED_ITEM_ID
547                         && mAccessibilityFocus != sourceId) {
548                     removeCachedNodeLocked(windowId, mAccessibilityFocus);
549                 }
550                 mAccessibilityFocus = sourceId;
551                 mAccessibilityFocusedWindow = windowId;
552             } else if (mAccessibilityFocus == sourceId) {
553                 mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID;
554                 mAccessibilityFocusedWindow = AccessibilityWindowInfo.UNDEFINED_WINDOW_ID;
555             }
556             if (clone.isFocused()) {
557                 mInputFocus = sourceId;
558                 mInputFocusWindow = windowId;
559             }
560 
561             if (mOnNodeAddedListener != null) {
562                 mOnNodeAddedListener.onNodeAdded(clone);
563             }
564         }
565     }
566 
567     /**
568      * Clears the cache.
569      */
clear()570     public void clear() {
571         synchronized(mLock) {
572             if (DEBUG) {
573                 Log.i(LOG_TAG, "clear()");
574             }
575             clearWindowCacheLocked();
576             final int nodesForWindowCount = mNodeCache.size();
577             for (int i = nodesForWindowCount - 1; i >= 0; i--) {
578                 final int windowId = mNodeCache.keyAt(i);
579                 clearNodesForWindowLocked(windowId);
580             }
581 
582             mAccessibilityFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID;
583             mInputFocus = AccessibilityNodeInfo.UNDEFINED_ITEM_ID;
584 
585             mAccessibilityFocusedWindow = AccessibilityWindowInfo.UNDEFINED_WINDOW_ID;
586             mInputFocusWindow = AccessibilityWindowInfo.UNDEFINED_WINDOW_ID;
587         }
588     }
589 
clearWindowCacheLocked()590     private void clearWindowCacheLocked() {
591         if (DEBUG) {
592             Log.i(LOG_TAG, "clearWindowCacheLocked");
593         }
594         final int displayCounts = mWindowCacheByDisplay.size();
595 
596         if (displayCounts > 0) {
597             for (int i = displayCounts - 1; i >= 0; i--) {
598                 final int displayId = mWindowCacheByDisplay.keyAt(i);
599                 final SparseArray<AccessibilityWindowInfo> windows =
600                         mWindowCacheByDisplay.get(displayId);
601                 if (windows != null) {
602                     windows.clear();
603                 }
604                 mWindowCacheByDisplay.remove(displayId);
605             }
606         }
607         mIsAllWindowsCached = false;
608     }
609 
610     /**
611      * Gets a cached {@link AccessibilityNodeInfo} with focus according to focus type.
612      *
613      * Note: {@link android.view.accessibility.AccessibilityWindowInfo#ACTIVE_WINDOW_ID} will return
614      * null.
615      *
616      * @param focusType The focus type.
617      * @param windowId A unique window id.
618      * @param initialNodeId A unique view id or virtual descendant id from where to start the
619      *                      search.
620      * @return The cached {@link AccessibilityNodeInfo} if it has a11y focus or null if such not
621      * found.
622      */
getFocus(int focusType, long initialNodeId, int windowId)623     public AccessibilityNodeInfo getFocus(int focusType, long initialNodeId, int windowId) {
624         synchronized (mLock) {
625             if (!mEnabled) {
626                 if (DEBUG) {
627                     Log.i(LOG_TAG, "Cache is disabled");
628                 }
629                 return null;
630             }
631             int currentFocusWindowId;
632             long currentFocusId;
633             if (focusType == FOCUS_ACCESSIBILITY) {
634                 currentFocusWindowId = mAccessibilityFocusedWindow;
635                 currentFocusId = mAccessibilityFocus;
636             } else {
637                 currentFocusWindowId = mInputFocusWindow;
638                 currentFocusId = mInputFocus;
639             }
640 
641             if (currentFocusWindowId == AccessibilityWindowInfo.UNDEFINED_WINDOW_ID) {
642                 return null;
643             }
644 
645             if (windowId != AccessibilityWindowInfo.ANY_WINDOW_ID
646                     && windowId != currentFocusWindowId) {
647                 return null;
648             }
649 
650             LongSparseArray<AccessibilityNodeInfo> nodes =
651                     mNodeCache.get(currentFocusWindowId);
652             if (nodes == null) {
653                 return null;
654             }
655 
656             final AccessibilityNodeInfo currentFocusedNode = nodes.get(currentFocusId);
657             if (currentFocusedNode == null) {
658                 return null;
659             }
660 
661             if (initialNodeId == currentFocusId || (isCachedNodeOrDescendantLocked(
662                     currentFocusedNode.getParentNodeId(), initialNodeId, nodes))) {
663                 if (VERBOSE) {
664                     Log.i(LOG_TAG, "getFocus(0x" + Long.toHexString(currentFocusId) + ") = "
665                             + currentFocusedNode + " with type: "
666                             + (focusType == FOCUS_ACCESSIBILITY
667                             ? "FOCUS_ACCESSIBILITY"
668                             : "FOCUS_INPUT"));
669                 }
670                 // Return a copy since the client calls to AccessibilityNodeInfo#recycle()
671                 // will wipe the data of the cached info.
672                 return new AccessibilityNodeInfo(currentFocusedNode);
673             }
674 
675             if (VERBOSE) {
676                 Log.i(LOG_TAG, "getFocus is null with type: "
677                         + (focusType == FOCUS_ACCESSIBILITY
678                         ? "FOCUS_ACCESSIBILITY"
679                         : "FOCUS_INPUT"));
680             }
681             return null;
682         }
683     }
684 
isCachedNodeOrDescendantLocked(long nodeId, long ancestorId, LongSparseArray<AccessibilityNodeInfo> nodes)685     private boolean isCachedNodeOrDescendantLocked(long nodeId, long ancestorId,
686             LongSparseArray<AccessibilityNodeInfo> nodes) {
687         if (ancestorId == nodeId) {
688             return true;
689         }
690         AccessibilityNodeInfo node = nodes.get(nodeId);
691         if (node == null) {
692             return false;
693         }
694         return isCachedNodeOrDescendantLocked(node.getParentNodeId(), ancestorId,  nodes);
695     }
696 
697     /**
698      * Clears nodes for the window with the given id
699      */
clearNodesForWindowLocked(int windowId)700     private void clearNodesForWindowLocked(int windowId) {
701         if (DEBUG) {
702             Log.i(LOG_TAG, "clearNodesForWindowLocked(" + windowId + ")");
703         }
704         LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId);
705         if (nodes == null) {
706             return;
707         }
708         mNodeCache.remove(windowId);
709     }
710 
711     /** Clears a subtree rooted at {@code info}. */
clearSubTree(AccessibilityNodeInfo info)712     public boolean clearSubTree(AccessibilityNodeInfo info) {
713         if (info == null) {
714             return false;
715         }
716         synchronized (mLock) {
717             if (!mEnabled) {
718                 if (DEBUG) {
719                     Log.i(LOG_TAG, "Cache is disabled");
720                 }
721                 return false;
722             }
723             clearSubTreeLocked(info.getWindowId(), info.getSourceNodeId());
724             return true;
725         }
726     }
727 
728     /**
729      * Clears a subtree rooted at the node with the given id that is
730      * hosted in a given window.
731      *
732      * @param windowId The id of the hosting window.
733      * @param rootNodeId The root id.
734      */
clearSubTreeLocked(int windowId, long rootNodeId)735     private void clearSubTreeLocked(int windowId, long rootNodeId) {
736         if (DEBUG) {
737             Log.i(LOG_TAG, "Clearing cached subtree.");
738         }
739         LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.get(windowId);
740         if (nodes != null) {
741             clearSubTreeRecursiveLocked(nodes, rootNodeId);
742         }
743     }
744 
745     /**
746      * Clears a subtree given a pointer to the root id and the nodes
747      * in the hosting window.
748      *
749      * @param nodes The nodes in the hosting window.
750      * @param rootNodeId The id of the root to evict.
751      *
752      * @return {@code true} if the cache was cleared
753      */
clearSubTreeRecursiveLocked(LongSparseArray<AccessibilityNodeInfo> nodes, long rootNodeId)754     private boolean clearSubTreeRecursiveLocked(LongSparseArray<AccessibilityNodeInfo> nodes,
755             long rootNodeId) {
756         AccessibilityNodeInfo current = nodes.get(rootNodeId);
757         if (current == null) {
758             // The node isn't in the cache, but its descendents might be.
759             clear();
760             return true;
761         }
762         nodes.remove(rootNodeId);
763         final int childCount = current.getChildCount();
764         for (int i = 0; i < childCount; i++) {
765             final long childNodeId = current.getChildId(i);
766             if (clearSubTreeRecursiveLocked(nodes, childNodeId)) {
767                 return true;
768             }
769         }
770         return false;
771     }
772 
773     /**
774      * Check the integrity of the cache which is nodes from different windows
775      * are not mixed, there is a single active window, there is a single focused
776      * window, for every window there are no duplicates nodes, all nodes for a
777      * window are connected, for every window there is a single input focused
778      * node, and for every window there is a single accessibility focused node.
779      */
checkIntegrity()780     public void checkIntegrity() {
781         synchronized (mLock) {
782             // Get the root.
783             if (mWindowCacheByDisplay.size() <= 0 && mNodeCache.size() == 0) {
784                 return;
785             }
786 
787             AccessibilityWindowInfo focusedWindow = null;
788             AccessibilityWindowInfo activeWindow = null;
789 
790             final int displayCounts = mWindowCacheByDisplay.size();
791             for (int i = 0; i < displayCounts; i++) {
792                 final SparseArray<AccessibilityWindowInfo> windowsOfDisplay =
793                         mWindowCacheByDisplay.valueAt(i);
794 
795                 if (windowsOfDisplay == null) {
796                     continue;
797                 }
798 
799                 final int windowCount = windowsOfDisplay.size();
800                 for (int j = 0; j < windowCount; j++) {
801                     final AccessibilityWindowInfo window = windowsOfDisplay.valueAt(j);
802 
803                     // Check for one active window.
804                     if (window.isActive()) {
805                         if (activeWindow != null) {
806                             Log.e(LOG_TAG, "Duplicate active window:" + window);
807                         } else {
808                             activeWindow = window;
809                         }
810                     }
811                     // Check for one focused window.
812                     if (window.isFocused()) {
813                         if (focusedWindow != null) {
814                             Log.e(LOG_TAG, "Duplicate focused window:" + window);
815                         } else {
816                             focusedWindow = window;
817                         }
818                     }
819                 }
820             }
821 
822             // Traverse the tree and do some checks.
823             AccessibilityNodeInfo accessFocus = null;
824             AccessibilityNodeInfo inputFocus = null;
825 
826             final int nodesForWindowCount = mNodeCache.size();
827             for (int i = 0; i < nodesForWindowCount; i++) {
828                 LongSparseArray<AccessibilityNodeInfo> nodes = mNodeCache.valueAt(i);
829                 if (nodes.size() <= 0) {
830                     continue;
831                 }
832 
833                 ArraySet<AccessibilityNodeInfo> seen = new ArraySet<>();
834                 final int windowId = mNodeCache.keyAt(i);
835 
836                 final int nodeCount = nodes.size();
837                 for (int j = 0; j < nodeCount; j++) {
838                     AccessibilityNodeInfo node = nodes.valueAt(j);
839 
840                     // Check for duplicates
841                     if (!seen.add(node)) {
842                         Log.e(LOG_TAG, "Duplicate node: " + node
843                                 + " in window:" + windowId);
844                         // Stop now as we potentially found a loop.
845                         continue;
846                     }
847 
848                     // Check for one accessibility focus.
849                     if (node.isAccessibilityFocused()) {
850                         if (accessFocus != null) {
851                             Log.e(LOG_TAG, "Duplicate accessibility focus:" + node
852                                     + " in window:" + windowId);
853                         } else {
854                             accessFocus = node;
855                         }
856                     }
857 
858                     // Check for one input focus.
859                     if (node.isFocused()) {
860                         if (inputFocus != null) {
861                             Log.e(LOG_TAG, "Duplicate input focus: " + node
862                                     + " in window:" + windowId);
863                         } else {
864                             inputFocus = node;
865                         }
866                     }
867 
868                     // The node should be a child of its parent if we have the parent.
869                     AccessibilityNodeInfo nodeParent = nodes.get(node.getParentNodeId());
870                     if (nodeParent != null) {
871                         boolean childOfItsParent = false;
872                         final int childCount = nodeParent.getChildCount();
873                         for (int k = 0; k < childCount; k++) {
874                             AccessibilityNodeInfo child = nodes.get(nodeParent.getChildId(k));
875                             if (child == node) {
876                                 childOfItsParent = true;
877                                 break;
878                             }
879                         }
880                         if (!childOfItsParent) {
881                             Log.e(LOG_TAG, "Invalid parent-child relation between parent: "
882                                     + nodeParent + " and child: " + node);
883                         }
884                     }
885 
886                     // The node should be the parent of its child if we have the child.
887                     final int childCount = node.getChildCount();
888                     for (int k = 0; k < childCount; k++) {
889                         AccessibilityNodeInfo child = nodes.get(node.getChildId(k));
890                         if (child != null) {
891                             AccessibilityNodeInfo parent = nodes.get(child.getParentNodeId());
892                             if (parent != node) {
893                                 Log.e(LOG_TAG, "Invalid child-parent relation between child: "
894                                         + node + " and parent: " + nodeParent);
895                             }
896                         }
897                     }
898                 }
899             }
900         }
901     }
902 
903     /**
904      * Registers a listener to receive callbacks whenever nodes are added to cache.
905      *
906      * @param listener the listener to be registered.
907      */
registerOnNodeAddedListener(OnNodeAddedListener listener)908     public void registerOnNodeAddedListener(OnNodeAddedListener listener) {
909         synchronized (mLock) {
910             mOnNodeAddedListener = listener;
911         }
912     }
913 
914     /**
915      * Clears the current reference to an OnNodeAddedListener, if one exists.
916      */
clearOnNodeAddedListener()917     public void clearOnNodeAddedListener() {
918         synchronized (mLock) {
919             mOnNodeAddedListener = null;
920         }
921     }
922 
923     /** Returns the source class associated with the window with the given id. */
924     @Nullable
getEventSourceClassName(int windowId)925     public String getEventSourceClassName(int windowId) {
926         return mWindowIdToEventSourceClassName.get(windowId);
927     }
928 
929     // Layer of indirection included to break dependency chain for testing
930     public static class AccessibilityNodeRefresher {
931         /** Refresh the given AccessibilityNodeInfo object. */
refreshNode(AccessibilityNodeInfo info, boolean bypassCache)932         public boolean refreshNode(AccessibilityNodeInfo info, boolean bypassCache) {
933             return info.refresh(null, bypassCache);
934         }
935 
936         /** Refresh the given AccessibilityWindowInfo object. */
refreshWindow(AccessibilityWindowInfo info)937         public boolean refreshWindow(AccessibilityWindowInfo info) {
938             return info.refresh();
939         }
940     }
941 
942     /**
943      * Listener interface that receives callbacks when nodes are added to cache.
944      */
945     public interface OnNodeAddedListener {
946         /** Called when a node is added to cache. */
onNodeAdded(AccessibilityNodeInfo node)947         void onNodeAdded(AccessibilityNodeInfo node);
948     }
949 }
950