[go: nahoru, domu]

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