Respect Z ordering in touch dispatch, software drawing

bug:14390526
Change-Id: I617a6ea7dbac1facae246491a247cf307452fc0e

5 files changed, 166 insertions, 42 deletions

diff --git a/core/java/android/view/ViewGroup.java b/core/java/android/view/ViewGroup.java
index b821a3e..0f40ee7 100644
--- a/core/java/android/view/ViewGroup.java
+++ b/core/java/android/view/ViewGroup.java
@@ -456,6 +456,10 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
     // views during a transition when they otherwise would have become gone/invisible
     private ArrayList<View> mVisibilityChangingChildren;
 
+    // Temporary holder of presorted children, only used for
+    // input/software draw dispatch for correctly Z ordering.
+    private ArrayList<View> mPreSortedChildren;
+
     // Indicates how many of this container's child subtrees contain transient state
     @ViewDebug.ExportedProperty(category = "layout")
     private int mChildCountWithTransientState = 0;
@@ -1499,13 +1503,15 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
             final float y = event.getY();
             final int childrenCount = mChildrenCount;
             if (childrenCount != 0) {
-                final boolean customChildOrder = isChildrenDrawingOrderEnabled();
+                final ArrayList<View> preorderedList = buildOrderedChildList();
+                final boolean customOrder = preorderedList == null
+                        && isChildrenDrawingOrderEnabled();
                 final View[] children = mChildren;
                 HoverTarget lastHoverTarget = null;
                 for (int i = childrenCount - 1; i >= 0; i--) {
-                    final int childIndex = customChildOrder
-                            ? getChildDrawingOrder(childrenCount, i) : i;
-                    final View child = children[childIndex];
+                    int childIndex = customOrder ? getChildDrawingOrder(childrenCount, i) : i;
+                    final View child = (preorderedList == null)
+                            ? children[childIndex] : preorderedList.get(childIndex);
                     if (!canViewReceivePointerEvents(child)
                             || !isTransformedTouchPointInView(x, y, child, null)) {
                         continue;
@@ -1572,6 +1578,7 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
                         break;
                     }
                 }
+                if (preorderedList != null) preorderedList.clear();
             }
         }
 
@@ -1778,23 +1785,28 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
         // Send the event to the child under the pointer.
         final int childrenCount = mChildrenCount;
         if (childrenCount != 0) {
-            final View[] children = mChildren;
             final float x = event.getX();
             final float y = event.getY();
 
-            final boolean customOrder = isChildrenDrawingOrderEnabled();
+            final ArrayList<View> preorderedList = buildOrderedChildList();
+            final boolean customOrder = preorderedList == null
+                    && isChildrenDrawingOrderEnabled();
+            final View[] children = mChildren;
             for (int i = childrenCount - 1; i >= 0; i--) {
-                final int childIndex = customOrder ? getChildDrawingOrder(childrenCount, i) : i;
-                final View child = children[childIndex];
+                int childIndex = customOrder ? getChildDrawingOrder(childrenCount, i) : i;
+                final View child = (preorderedList == null)
+                        ? children[childIndex] : preorderedList.get(childIndex);
                 if (!canViewReceivePointerEvents(child)
                         || !isTransformedTouchPointInView(x, y, child, null)) {
                     continue;
                 }
 
                 if (dispatchTransformedGenericPointerEvent(event, child)) {
+                    if (preorderedList != null) preorderedList.clear();
                     return true;
                 }
             }
+            if (preorderedList != null) preorderedList.clear();
         }
 
         // No child handled the event.  Send it to this view group.
@@ -1910,13 +1922,15 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
                         final float y = ev.getY(actionIndex);
                         // Find a child that can receive the event.
                         // Scan children from front to back.
+                        final ArrayList<View> preorderedList = buildOrderedChildList();
+                        final boolean customOrder = preorderedList == null
+                                && isChildrenDrawingOrderEnabled();
                         final View[] children = mChildren;
-
-                        final boolean customOrder = isChildrenDrawingOrderEnabled();
                         for (int i = childrenCount - 1; i >= 0; i--) {
-                            final int childIndex = customOrder ?
-                                    getChildDrawingOrder(childrenCount, i) : i;
-                            final View child = children[childIndex];
+                            final int childIndex = customOrder
+                                    ? getChildDrawingOrder(childrenCount, i) : i;
+                            final View child = (preorderedList == null)
+                                    ? children[childIndex] : preorderedList.get(childIndex);
                             if (!canViewReceivePointerEvents(child)
                                     || !isTransformedTouchPointInView(x, y, child, null)) {
                                 continue;
@@ -1934,7 +1948,17 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
                             if (dispatchTransformedTouchEvent(ev, false, child, idBitsToAssign)) {
                                 // Child wants to receive touch within its bounds.
                                 mLastTouchDownTime = ev.getDownTime();
-                                mLastTouchDownIndex = childIndex;
+                                if (preorderedList != null) {
+                                    // childIndex points into presorted list, find original index
+                                    for (int j = 0; j < childrenCount; j++) {
+                                        if (children[childIndex] == mChildren[j]) {
+                                            mLastTouchDownIndex = j;
+                                            break;
+                                        }
+                                    }
+                                } else {
+                                    mLastTouchDownIndex = childIndex;
+                                }
                                 mLastTouchDownX = ev.getX();
                                 mLastTouchDownY = ev.getY();
                                 newTouchTarget = addTouchTarget(child, idBitsToAssign);
@@ -1942,6 +1966,7 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
                                 break;
                             }
                         }
+                        if (preorderedList != null) preorderedList.clear();
                     }
 
                     if (newTouchTarget == null && mFirstTouchTarget != null) {
@@ -2928,7 +2953,7 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
      */
     @Override
     protected void dispatchDraw(Canvas canvas) {
-        final int count = mChildrenCount;
+        final int childrenCount = mChildrenCount;
         final View[] children = mChildren;
         int flags = mGroupFlags;
 
@@ -2936,15 +2961,15 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
             final boolean cache = (mGroupFlags & FLAG_ANIMATION_CACHE) == FLAG_ANIMATION_CACHE;
 
             final boolean buildCache = !isHardwareAccelerated();
-            for (int i = 0; i < count; i++) {
+            for (int i = 0; i < childrenCount; i++) {
                 final View child = children[i];
                 if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE) {
                     final LayoutParams params = child.getLayoutParams();
-                    attachLayoutAnimationParameters(child, params, i, count);
+                    attachLayoutAnimationParameters(child, params, i, childrenCount);
                     bindLayoutAnimation(child);
                     if (cache) {
                         child.setDrawingCacheEnabled(true);
-                        if (buildCache) {                        
+                        if (buildCache) {
                             child.buildDrawingCache(true);
                         }
                     }
@@ -2997,21 +3022,22 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
         boolean more = false;
         final long drawingTime = getDrawingTime();
 
-        if ((flags & FLAG_USE_CHILD_DRAWING_ORDER) == 0) {
-            for (int i = 0; i < count; i++) {
-                final View child = children[i];
-                if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE || child.getAnimation() != null) {
-                    more |= drawChild(canvas, child, drawingTime);
-                }
-            }
-        } else {
-            for (int i = 0; i < count; i++) {
-                final View child = children[getChildDrawingOrder(count, i)];
-                if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE || child.getAnimation() != null) {
-                    more |= drawChild(canvas, child, drawingTime);
-                }
+
+        // Only use the preordered list if not HW accelerated, since the HW pipeline will do the
+        // draw reordering internally
+        final ArrayList<View> preorderedList = canvas.isHardwareAccelerated()
+                ? null : buildOrderedChildList();
+        final boolean customOrder = preorderedList == null
+                && isChildrenDrawingOrderEnabled();
+        for (int i = 0; i < childrenCount; i++) {
+            int childIndex = customOrder ? getChildDrawingOrder(childrenCount, i) : i;
+            final View child = (preorderedList == null)
+                    ? children[childIndex] : preorderedList.get(childIndex);
+            if ((child.mViewFlags & VISIBILITY_MASK) == VISIBLE || child.getAnimation() != null) {
+                more |= drawChild(canvas, child, drawingTime);
             }
         }
+        if (preorderedList != null) preorderedList.clear();
 
         // Draw any disappearing views that have animations
         if (mDisappearingChildren != null) {
@@ -3096,6 +3122,47 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
         return i;
     }
 
+    private boolean hasChildWithZ() {
+        for (int i = 0; i < mChildrenCount; i++) {
+            if (mChildren[i].getZ() != 0) return true;
+        }
+        return false;
+    }
+
+    /**
+     * Populates (and returns) mPreSortedChildren with a pre-ordered list of the View's children,
+     * sorted first by Z, then by child drawing order (if applicable).
+     *
+     * Uses a stable, insertion sort which is commonly O(n) for ViewGroups with very few elevated
+     * children.
+     */
+    private ArrayList<View> buildOrderedChildList() {
+        final int count = mChildrenCount;
+        if (count <= 1 || !hasChildWithZ()) return null;
+
+        if (mPreSortedChildren == null) {
+            mPreSortedChildren = new ArrayList<View>(count);
+        } else {
+            mPreSortedChildren.ensureCapacity(count);
+        }
+
+        final boolean useCustomOrder = isChildrenDrawingOrderEnabled();
+        for (int i = 0; i < mChildrenCount; i++) {
+            // add next child (in child order) to end of list
+            int childIndex = useCustomOrder ? getChildDrawingOrder(mChildrenCount, i) : i;
+            View nextChild = mChildren[childIndex];
+            float currentZ = nextChild.getZ();
+
+            // insert ahead of any Views with greater Z
+            int insertIndex = i;
+            while (insertIndex > 0 && mPreSortedChildren.get(insertIndex - 1).getZ() > currentZ) {
+                insertIndex--;
+            }
+            mPreSortedChildren.add(insertIndex, nextChild);
+        }
+        return mPreSortedChildren;
+    }
+
     private void notifyAnimationListener() {
         mGroupFlags &= ~FLAG_NOTIFY_ANIMATION_LISTENER;
         mGroupFlags |= FLAG_ANIMATION_DONE;
diff --git a/tests/HwAccelerationTest/AndroidManifest.xml b/tests/HwAccelerationTest/AndroidManifest.xml
index db802c5..6b70631 100644
--- a/tests/HwAccelerationTest/AndroidManifest.xml
+++ b/tests/HwAccelerationTest/AndroidManifest.xml
@@ -902,5 +902,14 @@
                 <category android:name="com.android.test.hwui.TEST" />
             </intent-filter>
         </activity>
+
+        <activity
+                android:name=".ZOrderingActivity"
+                android:label="Reordering/Z Ordering">
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="com.android.test.hwui.TEST" />
+            </intent-filter>
+        </activity>
     </application>
 </manifest>
diff --git a/tests/HwAccelerationTest/res/layout/z_ordering.xml b/tests/HwAccelerationTest/res/layout/z_ordering.xml
new file mode 100644
index 0000000..970c5fd
--- /dev/null
+++ b/tests/HwAccelerationTest/res/layout/z_ordering.xml
@@ -0,0 +1,17 @@
+<?xml version="1.0" encoding="utf-8"?>
+<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
+        android:layout_width="match_parent"
+        android:layout_height="wrap_content"
+        android:orientation="horizontal"
+        android:id="@+id/parent">
+    <RelativeLayout
+            android:layout_width="400dp"
+            android:layout_height="200dp"
+            android:layout_weight="1"
+            android:orientation="vertical">
+        <TextView style="@style/TopLeftReorderTextView"/>
+        <TextView style="@style/BottomLeftReorderTextView"/>
+        <TextView style="@style/TopRightReorderTextView"/>
+        <TextView style="@style/BottomRightReorderTextView"/>
+    </RelativeLayout>
+</LinearLayout>
\ No newline at end of file
diff --git a/tests/HwAccelerationTest/res/values/styles.xml b/tests/HwAccelerationTest/res/values/styles.xml
index cde5d20..108709b 100644
--- a/tests/HwAccelerationTest/res/values/styles.xml
+++ b/tests/HwAccelerationTest/res/values/styles.xml
@@ -1,34 +1,37 @@
 <resources>
     <style name="ReorderTextView" parent="@android:style/TextAppearance.Medium">
-        <item name="android:layout_width">match_parent</item>
+        <item name="android:background">@drawable/appwidget_background</item>
+        <item name="android:layout_width">300dp</item>
         <item name="android:layout_height">100dp</item>
         <item name="android:gravity">center</item>
     </style>
     <style name="LeftReorderTextView" parent="@style/ReorderTextView">
-        <item name="android:translationX">20dp</item>
+        <item name="android:translationX">50dp</item>
+        <item name="android:layout_alignParentLeft">true</item>
     </style>
     <style name="RightReorderTextView" parent="@style/ReorderTextView">
-        <item name="android:translationX">-20dp</item>
+        <item name="android:translationX">-50dp</item>
+        <item name="android:layout_alignParentRight">true</item>
     </style>
 
     <style name="TopLeftReorderTextView" parent="@style/LeftReorderTextView">
-        <item name="android:background">#666</item>
-        <item name="android:text">100</item>
-        <item name="android:translationZ">100dp</item>
+        <item name="android:text">200</item>
+        <item name="android:translationZ">200dp</item>
+        <item name="android:layout_alignParentTop">true</item>
     </style>
     <style name="BottomLeftReorderTextView" parent="@style/LeftReorderTextView">
-        <item name="android:background">#bbb</item>
         <item name="android:text">300</item>
         <item name="android:translationZ">300dp</item>
+        <item name="android:layout_alignParentBottom">true</item>
     </style>
     <style name="TopRightReorderTextView" parent="@style/RightReorderTextView">
-        <item name="android:background">#888</item>
-        <item name="android:text">200</item>
-        <item name="android:translationZ">200dp</item>
+        <item name="android:text">100</item>
+        <item name="android:translationZ">100dp</item>
+        <item name="android:layout_alignParentTop">true</item>
     </style>
     <style name="BottomRightReorderTextView" parent="@style/RightReorderTextView">
-        <item name="android:background">#ccc</item>
         <item name="android:text">400</item>
         <item name="android:translationZ">400dp</item>
+        <item name="android:layout_alignParentBottom">true</item>
     </style>
 </resources>
diff --git a/tests/HwAccelerationTest/src/com/android/test/hwui/ZOrderingActivity.java b/tests/HwAccelerationTest/src/com/android/test/hwui/ZOrderingActivity.java
new file mode 100644
index 0000000..45e77ed
--- /dev/null
+++ b/tests/HwAccelerationTest/src/com/android/test/hwui/ZOrderingActivity.java
@@ -0,0 +1,28 @@
+package com.android.test.hwui;
+
+import android.app.Activity;
+import android.os.Bundle;
+import android.util.Log;
+import android.view.View;
+import android.view.ViewGroup;
+
+public class ZOrderingActivity extends Activity {
+    @Override
+    protected void onCreate(Bundle savedInstanceState) {
+        super.onCreate(savedInstanceState);
+        setContentView(R.layout.z_ordering);
+
+        ViewGroup grandParent = (ViewGroup) findViewById(R.id.parent);
+        if (grandParent == null) throw new IllegalStateException();
+        View.OnClickListener l = new View.OnClickListener() {
+            @Override
+            public void onClick(View v) {}
+        };
+        for (int i = 0; i < grandParent.getChildCount(); i++) {
+            ViewGroup parent = (ViewGroup) grandParent.getChildAt(i);
+            for (int j = 0; j < parent.getChildCount(); j++) {
+                parent.getChildAt(j).setOnClickListener(l);
+            }
+        }
+    }
+}