Accessibility focus - framework

Usefulness: Keep track of the current user location in the screen when
            traversing the it. Enabling structural and directional
            navigation over all elements on the screen. This enables
            blind users that know the application layout to efficiently
            locate desired elements as opposed to try touch exploring the
            region where the the element should be - very tedious.

Rationale: There are two ways to implement accessibility focus One is
           to let accessibility services keep track of it since they
           have access to the screen content, and another to let the view
           hierarchy keep track of it. While the first approach would
           require almost no work on our part it poses several challenges
           which make it a sub-optimal choice. Having the accessibility focus
           in the accessibility service would require that service to scrape
           the window content every time it changes to sync the view tree
           state and the accessibility focus location. Pretty much the service
           will have to keep an off screen model of the screen content. This
           could be quite challenging to get right and would incur performance
           cost for the multiple IPCs to repeatedly fetch the screen content.
           Further, keeping virtual accessibility focus (i.e. in the service)
           would require sync of the input and accessibility focus. This could
           be challenging to implement right as well. Also, having an unlimited
           number of accessibility services we cannot guarantee that they will
           have a proper implementation, if any, to allow users to perform structural
           navigation of the screen content. Assuming two accessibility
           services implement structural navigation via accessibility focus,
           there is not guarantee that they will behave similarly by default,
           i.e. provide some standard way to navigate the screen content.
           Also feedback from experienced accessibility researchers, specifically
           T.V Raman, provides evidence that having virtual accessibility focus
           creates many issues and it is very hard to get right.
           Therefore, keeping accessibility focus in the system will avoid
           keeping an off-screen model in accessibility services, it will always
           be in sync with the state of the view hierarchy and the input focus.
           Also this will allow having a default behavior for traversing the
           screen via this accessibility focus that is consistent in all
           accessibility services. We provide accessibility services with APIs to
           override this behavior but all of them will perform screen traversal
           in a consistent way by default.

Behavior:  If accessibility is enabled the accessibility focus is the leading one
           and the input follows it. Putting accessibility focus on a view moves
           the input focus there. Clearing the accessibility focus of a view, clears
           the input focus of this view. If accessibility focus is on a view that
           cannot take input focus, then no other view should have input focus.
           In accessibility mode we initially give accessibility focus to the topmost
           view and no view has input focus. This ensures consistent behavior accross
           all apps. Note that accessibility focus can move hierarchically in the
           view tree and having it at the root is better than putting it where the
           input focus would be - at the first input focusable which could be at
           an arbitrary depth in the view tree. By default not all views are reported
           for accessibility, only the important ones. A view may be explicitly labeled
           as important or not for accessibility, or the system determines which one
           is such - default. Important views for accessibility are all views that are
           not dumb layout managers used only to arrange their chidren. Since the same
           content arrangement can be obtained via different combintation of layout
           managers, such managers cannot be used to reliably determine the application
           structure. For example, a user should see a list as a list view with several
           list items and each list item as a text view and a button as opposed to seeing
           all the layout managers used to arrange the list item's content.
           By default only important for accessibility views are regared for accessibility
           purposes. View not regarded for accessibility neither fire accessibility events,
           nor are reported being on the screen. An accessibility service may request the
           system to regard all views. If the target SDK of an accessibility services is
           less than JellyBean, then all views are regarded for accessibility.
           Note that an accessibility service that requires all view to be ragarded for
           accessibility may put accessibility focus on any view. Hence, it may implement
           any navigational paradigm if desired. Especially considering the fact that
           the system is detecting some standard gestures and delegates their processing
           to an accessibility service. The default implementation of an accessibility
           services performs the defualt navigation.

bug:5932640
bug:5605641

Change-Id: Ieac461d480579d706a847b9325720cb254736ebe

1 files changed, 283 insertions, 13 deletions

diff --git a/core/java/android/view/ViewGroup.java b/core/java/android/view/ViewGroup.java
index 121b544..7e90e2b 100644
--- a/core/java/android/view/ViewGroup.java
+++ b/core/java/android/view/ViewGroup.java
@@ -45,6 +45,7 @@ import com.android.internal.R;
 import com.android.internal.util.Predicate;
 
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.HashSet;
 
 /**
@@ -611,13 +612,13 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
     /**
      * {@inheritDoc}
      */
+    @Override
     public boolean requestSendAccessibilityEvent(View child, AccessibilityEvent event) {
-        ViewParent parent = getParent();
+        ViewParent parent = mParent;
         if (parent == null) {
             return false;
         }
         final boolean propagate = onRequestSendAccessibilityEvent(child, event);
-        //noinspection SimplifiableIfStatement
         if (!propagate) {
             return false;
         }
@@ -1552,6 +1553,33 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
         return mFirstHoverTarget != null;
     }
 
+    @Override
+    public void addChildrenForAccessibility(ArrayList<View> childrenForAccessibility) {
+        View[] children = mChildren;
+        final int childrenCount = mChildrenCount;
+        for (int i = 0; i < childrenCount; i++) {
+            View child = children[i];
+            if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE
+                    && (child.mPrivateFlags & IS_ROOT_NAMESPACE) == 0) {
+                if (child.includeForAccessibility()) {
+                    childrenForAccessibility.add(child);
+                } else {
+                    child.addChildrenForAccessibility(childrenForAccessibility);
+                }
+            }
+        }
+    }
+
+    /**
+     * @hide
+     */
+    @Override
+    public void childAccessibilityStateChanged(View child) {
+        if (mParent != null) {
+            mParent.childAccessibilityStateChanged(child);
+        }
+    }
+
     /**
      * Implement this method to intercept hover events before they are handled
      * by child views.
@@ -2294,33 +2322,43 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
 
     @Override
     boolean dispatchPopulateAccessibilityEventInternal(AccessibilityEvent event) {
-        boolean handled = super.dispatchPopulateAccessibilityEventInternal(event);
-        if (handled) {
-            return handled;
+        boolean handled = false;
+        if (includeForAccessibility()) {
+            handled = super.dispatchPopulateAccessibilityEventInternal(event);
+            if (handled) {
+                return handled;
+            }
         }
         // Let our children have a shot in populating the event.
-        for (int i = 0, count = getChildCount(); i < count; i++) {
-            View child = getChildAt(i);
+        ChildListForAccessibility children = ChildListForAccessibility.obtain(this, true);
+        final int childCount = children.getChildCount();
+        for (int i = 0; i < childCount; i++) {
+            View child = children.getChildAt(i);
             if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE) {
-                handled = getChildAt(i).dispatchPopulateAccessibilityEvent(event);
+                handled = child.dispatchPopulateAccessibilityEvent(event);
                 if (handled) {
+                    children.recycle();
                     return handled;
                 }
             }
         }
+        children.recycle();
         return false;
     }
 
     @Override
     void onInitializeAccessibilityNodeInfoInternal(AccessibilityNodeInfo info) {
         super.onInitializeAccessibilityNodeInfoInternal(info);
-        info.setClassName(ViewGroup.class.getName());
-        for (int i = 0, count = mChildrenCount; i < count; i++) {
-            View child = mChildren[i];
-            if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE
-                    && (child.mPrivateFlags & IS_ROOT_NAMESPACE) == 0) {
+        if (mAttachInfo != null) {
+            ArrayList<View> childrenForAccessibility = mAttachInfo.mTempArrayList;
+            childrenForAccessibility.clear();
+            addChildrenForAccessibility(childrenForAccessibility);
+            final int childrenForAccessibilityCount = childrenForAccessibility.size();
+            for (int i = 0; i < childrenForAccessibilityCount; i++) {
+                View child = childrenForAccessibility.get(i);
                 info.addChild(child);
             }
+            childrenForAccessibility.clear();
         }
     }
 
@@ -2331,6 +2369,20 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
     }
 
     /**
+     * @hide
+     */
+    @Override
+    public void resetAccessibilityStateChanged() {
+        super.resetAccessibilityStateChanged();
+        View[] children = mChildren;
+        final int childCount = mChildrenCount;
+        for (int i = 0; i < childCount; i++) {
+            View child = children[i];
+            child.resetAccessibilityStateChanged();
+        }
+    }
+
+    /**
      * {@inheritDoc}
      */
     @Override
@@ -3400,6 +3452,10 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
             clearChildFocus(view);
             ensureInputFocusOnFirstFocusable();
         }
+
+        if (view.isAccessibilityFocused()) {
+            view.clearAccessibilityFocus();
+        }
     }
 
     /**
@@ -5622,4 +5678,218 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
             }
         }
     }
+
+    /**
+     * Pooled class that orderes the children of a ViewGroup from start
+     * to end based on how they are laid out and the layout direction.
+     */
+    static class ChildListForAccessibility {
+
+        private static final int MAX_POOL_SIZE = 32;
+
+        private static final Object sPoolLock = new Object();
+
+        private static ChildListForAccessibility sPool;
+
+        private static int sPoolSize;
+
+        private boolean mIsPooled;
+
+        private ChildListForAccessibility mNext;
+
+        private final ArrayList<View> mChildren = new ArrayList<View>();
+
+        private final ArrayList<ViewLocationHolder> mHolders = new ArrayList<ViewLocationHolder>();
+
+        public static ChildListForAccessibility obtain(ViewGroup parent, boolean sort) {
+            ChildListForAccessibility list = null;
+            synchronized (sPoolLock) {
+                if (sPool != null) {
+                    list = sPool;
+                    sPool = list.mNext;
+                    list.mNext = null;
+                    list.mIsPooled = false;
+                    sPoolSize--;
+                } else {
+                    list = new ChildListForAccessibility();
+                }
+                list.init(parent, sort);
+                return list;
+            }
+        }
+
+        public void recycle() {
+            if (mIsPooled) {
+                throw new IllegalStateException("Instance already recycled.");
+            }
+            clear();
+            if (sPoolSize < MAX_POOL_SIZE) {
+                mNext = sPool;
+                mIsPooled = true;
+                sPool = this;
+                sPoolSize++;
+            }
+        }
+
+        public int getChildCount() {
+            return mChildren.size();
+        }
+
+        public View getChildAt(int index) {
+            return mChildren.get(index);
+        }
+
+        public int getChildIndex(View child) {
+            return mChildren.indexOf(child);
+        }
+
+        private void init(ViewGroup parent, boolean sort) {
+            ArrayList<View> children = mChildren;
+            final int childCount = parent.getChildCount();
+            for (int i = 0; i < childCount; i++) {
+                View child = parent.getChildAt(i);
+                children.add(child);
+            }
+            if (sort) {
+                ArrayList<ViewLocationHolder> holders = mHolders;
+                for (int i = 0; i < childCount; i++) {
+                    View child = children.get(i);
+                    ViewLocationHolder holder = ViewLocationHolder.obtain(parent, child);
+                    holders.add(holder);
+                }
+                Collections.sort(holders);
+                for (int i = 0; i < childCount; i++) {
+                    ViewLocationHolder holder = holders.get(i);
+                    children.set(i, holder.mView);
+                    holder.recycle();
+                }
+                holders.clear();
+            }
+        }
+
+        private void clear() {
+            mChildren.clear();
+        }
+    }
+
+    /**
+     * Pooled class that holds a View and its location with respect to
+     * a specified root. This enables sorting of views based on their
+     * coordinates without recomputing the position relative to the root
+     * on every comparison.
+     */
+    static class ViewLocationHolder implements Comparable<ViewLocationHolder> {
+
+        private static final int MAX_POOL_SIZE = 32;
+
+        private static final Object sPoolLock = new Object();
+
+        private static ViewLocationHolder sPool;
+
+        private static int sPoolSize;
+
+        private boolean mIsPooled;
+
+        private ViewLocationHolder mNext;
+
+        private final Rect mLocation = new Rect();
+
+        public View mView;
+
+        private int mLayoutDirection;
+
+        public static ViewLocationHolder obtain(ViewGroup root, View view) {
+            ViewLocationHolder holder = null;
+            synchronized (sPoolLock) {
+                if (sPool != null) {
+                    holder = sPool;
+                    sPool = holder.mNext;
+                    holder.mNext = null;
+                    holder.mIsPooled = false;
+                    sPoolSize--;
+                } else {
+                    holder = new ViewLocationHolder();
+                }
+                holder.init(root, view);
+                return holder;
+            }
+        }
+
+        public void recycle() {
+            if (mIsPooled) {
+                throw new IllegalStateException("Instance already recycled.");
+            }
+            clear();
+            if (sPoolSize < MAX_POOL_SIZE) {
+                mNext = sPool;
+                mIsPooled = true;
+                sPool = this;
+                sPoolSize++;
+            }
+        }
+
+        @Override
+        public int compareTo(ViewLocationHolder another) {
+            // This instance is greater than an invalid argument.
+            if (another == null) {
+                return 1;
+            }
+            if (getClass() != another.getClass()) {
+                return 1;
+            }
+            // First is above second.
+            if (mLocation.bottom - another.mLocation.top <= 0) {
+                return -1;
+            }
+            // First is below second.
+            if (mLocation.top - another.mLocation.bottom >= 0) {
+                return 1;
+            }
+            // LTR
+            if (mLayoutDirection == LAYOUT_DIRECTION_LTR) {
+                final int leftDifference = mLocation.left - another.mLocation.left;
+                // First more to the left than second.
+                if (leftDifference != 0) {
+                    return leftDifference;
+                }
+            } else { // RTL
+                final int rightDifference = mLocation.right - another.mLocation.right;
+                // First more to the right than second.
+                if (rightDifference != 0) {
+                    return -rightDifference;
+                }
+            }
+            // Break tie by top.
+            final int topDiference = mLocation.top - another.mLocation.top;
+            if (topDiference != 0) {
+                return topDiference;
+            }
+            // Break tie by height.
+            final int heightDiference = mLocation.height() - another.mLocation.height();
+            if (heightDiference != 0) {
+                return -heightDiference;
+            }
+            // Break tie by width.
+            final int widthDiference = mLocation.width() - another.mLocation.width();
+            if (widthDiference != 0) {
+                return -widthDiference;
+            }
+            // Return nondeterministically one of them since we do
+            // not want to ignore any views.
+            return 1;
+        }
+
+        private void init(ViewGroup root, View view) {
+            Rect viewLocation = mLocation;
+            view.getDrawingRect(viewLocation);
+            root.offsetDescendantRectToMyCoords(view, viewLocation);
+            mView = view;
+            mLayoutDirection = root.getResolvedLayoutDirection();
+        }
+
+        private void clear() {
+            mView = null;
+            mLocation.set(0, 0, 0, 0);
+        }
+    }
 }