DisplayTopology: fix erroneous attach-to-corner

Using x/y deviation to choose which edge to attach to was causing corner
attachment too easily when only a small amount of the larger edge was
overlapping. Effectively the block would be bumped to the corner even
though attaching along the longer edge would have been closer to the
requested position.

Do not use deviation to choose an attachment edge, but use the overlap
values. Update comments accordingly, as well as reword and refactor
them.

Flag: com.android.settings.flags.display_topology_pane_in_display_list
Test: atest DisplayTopologyTest.kt
Bug: b/352650922
Change-Id: I38024ab1500020fe195348e96b0c99ec85886e03

2 files changed, 80 insertions, 29 deletions

diff --git a/core/java/android/hardware/display/DisplayTopology.java b/core/java/android/hardware/display/DisplayTopology.java
index 211aefffa34c..85c997673cf3 100644
--- a/core/java/android/hardware/display/DisplayTopology.java
+++ b/core/java/android/hardware/display/DisplayTopology.java
@@ -201,10 +201,9 @@ public final class DisplayTopology implements Parcelable {
         // The optimal pair is the pair which has the smallest deviation. The deviation consists of
         // an x-axis component and a y-axis component, called xDeviation and yDeviation.
         //
-        // The deviations are like distances but a little different. They are calculated in two
-        // steps. The first step calculates both axes in a similar way. The next step compares the
-        // two values and chooses which axis to attach along. Depending on which axis is chosen,
-        // the deviation for one axis is updated. See below for details.
+        // The deviations are like distances but a little different. When they are calculated, each
+        // dimension is treated differently, depending on which edges (left+right or top+bottom) are
+        // attached.
         while (!needsParent.isEmpty()) {
             double bestDist = Double.POSITIVE_INFINITY;
             TreeNode bestChild = null, bestParent = null;
@@ -218,33 +217,32 @@ public final class DisplayTopology implements Parcelable {
                     float parentRight = parentPos.x + parent.getWidth();
                     float parentBottom = parentPos.y + parent.getHeight();
 
-                    // This is the smaller of the two ranges minus the amount of overlap shared
-                    // between them. The "amount of overlap" is negative if there is no overlap, but
-                    // this does not make a parenting ineligible, because we allow for attaching at
-                    // the corner and for floating point error. The overlap is more negative the
-                    // farther apart the closest corner pair is.
-                    //
-                    // For each axis, this calculates (SmallerRange - Overlap). If one range lies
-                    // completely in the other (or they are equal), the axis' deviation will be
-                    // zero.
-                    //
-                    // The "SmallerRange," which refers to smaller of the widths of the two rects,
-                    // or smaller of the heights of the two rects, is added to the deviation so that
-                    // a maximum overlap results in a deviation of zero.
-                    float xSmallerRange = Math.min(child.getWidth(), parent.getWidth());
-                    float ySmallerRange = Math.min(child.getHeight(), parent.getHeight());
-                    float xOverlap
-                            = Math.min(parentRight, childRight)
-                            - Math.max(parentPos.x, childPos.x);
-                    float yOverlap
-                            = Math.min(parentBottom, childBottom)
-                            - Math.max(parentPos.y, childPos.y);
-                    float xDeviation = xSmallerRange - xOverlap;
-                    float yDeviation = ySmallerRange - yOverlap;
+                    // The "amount of overlap" indicates how much of one display is within the other
+                    // (considering one axis only). It's zero if they only share an edge and
+                    // negative if they're away from each other.
+                    // A zero or negative overlap does not make a parenting ineligible, because we
+                    // allow for attaching at the corner and for floating point error.
+                    float xOverlap =
+                            Math.min(parentRight, childRight) - Math.max(parentPos.x, childPos.x);
+                    float yOverlap =
+                            Math.min(parentBottom, childBottom) - Math.max(parentPos.y, childPos.y);
+                    float xDeviation, yDeviation;
 
                     float offset;
                     int pos;
-                    if (xDeviation <= yDeviation) {
+                    if (Math.abs(xOverlap) > Math.abs(yOverlap)) {
+                        // Deviation in each dimension is a penalty in the potential parenting. To
+                        // get the X deviation, overlap is subtracted from the lesser width so that
+                        // a maximum overlap results in a deviation of zero.
+                        // Note that because xOverlap is *subtracted* from the lesser width, no
+                        // overlap in X becomes a *penalty* if we are attaching on the top+bottom
+                        // edges.
+                        //
+                        // The Y deviation is simply the distance from the clamping edges.
+                        //
+                        // Treatment of the X and Y deviations are swapped for
+                        // POSITION_LEFT/POSITION_RIGHT attachments in the "else" block below.
+                        xDeviation = Math.min(child.getWidth(), parent.getWidth()) - xOverlap;
                         if (childPos.y < parentPos.y) {
                             yDeviation = childBottom - parentPos.y;
                             pos = POSITION_TOP;
@@ -254,6 +252,7 @@ public final class DisplayTopology implements Parcelable {
                         }
                         offset = childPos.x - parentPos.x;
                     } else {
+                        yDeviation = Math.min(child.getHeight(), parent.getHeight()) - yOverlap;
                         if (childPos.x < parentPos.x) {
                             xDeviation = childRight - parentPos.x;
                             pos = POSITION_LEFT;
diff --git a/core/tests/coretests/src/android/hardware/display/DisplayTopologyTest.kt b/core/tests/coretests/src/android/hardware/display/DisplayTopologyTest.kt
index 4a227d8ff1ef..da618b0f0e9d 100644
--- a/core/tests/coretests/src/android/hardware/display/DisplayTopologyTest.kt
+++ b/core/tests/coretests/src/android/hardware/display/DisplayTopologyTest.kt
@@ -572,13 +572,65 @@ class DisplayTopologyTest {
         verifyDisplay(
                 root.children[0], id = 1, width = 30f, height = 30f, POSITION_RIGHT, offset = 10f,
                 noOfChildren = 1)
-        // In the case of corner adjacency, we prefer a left/right attachment.
         verifyDisplay(
                 root.children[0].children[0], id = 2, width = 29.5f, height = 30f, POSITION_BOTTOM,
                 offset = 30f, noOfChildren = 0)
     }
 
     @Test
+    fun rearrange_preferLessShiftInOverlapDimension() {
+        val root = rearrangeRects(
+            // '*' represents overlap
+            // Clamping requires moving display 2 and 1 slightly to avoid overlap with 0. We should
+            // shift the minimal amount to avoid overlap - e.g. display 2 shifts left (10 pixels)
+            // rather than up (20 pixels).
+            // 222
+            // 22*00
+            // 22*00
+            //   0**1
+            //    111
+            //    111
+            RectF(20f, 10f, 50f, 40f),
+            RectF(30f, 30f, 60f, 60f),
+            RectF(0f, 0f, 30f, 30f),
+        )
+
+        verifyDisplay(root, id = 0, width = 30f, height = 30f, noOfChildren = 2)
+        verifyDisplay(
+                root.children[0], id = 1, width = 30f, height = 30f, POSITION_BOTTOM, offset = 10f,
+                noOfChildren = 0)
+        verifyDisplay(
+                root.children[1], id = 2, width = 30f, height = 30f, POSITION_LEFT, offset = -10f,
+                noOfChildren = 0)
+    }
+
+    @Test
+    fun rearrange_doNotAttachCornerForShortOverlapOnLongEdgeBottom() {
+        val root = rearrangeRects(
+            RectF(0f, 0f, 1920f, 1080f),
+            RectF(1850f, 1070f, 3770f, 2150f),
+        )
+
+        verifyDisplay(root, id = 0, width = 1920f, height = 1080f, noOfChildren = 1)
+        verifyDisplay(
+                root.children[0], id = 1, width = 1920f, height = 1080f, POSITION_BOTTOM,
+                offset = 1850f, noOfChildren = 0)
+    }
+
+    @Test
+    fun rearrange_doNotAttachCornerForShortOverlapOnLongEdgeLeft() {
+        val root = rearrangeRects(
+            RectF(0f, 0f, 1080f, 1920f),
+            RectF(-1070f, -1880f, 10f, 40f),
+        )
+
+        verifyDisplay(root, id = 0, width = 1080f, height = 1920f, noOfChildren = 1)
+        verifyDisplay(
+                root.children[0], id = 1, width = 1080f, height = 1920f, POSITION_LEFT,
+                offset = -1880f, noOfChildren = 0)
+    }
+
+    @Test
     fun copy() {
         val display1 = DisplayTopology.TreeNode(/* displayId= */ 1, /* width= */ 200f,
             /* height= */ 600f, /* position= */ 0, /* offset= */ 0f)