1 /* 2 * Copyright (C) 2024 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.hardware.display; 18 19 import static android.hardware.display.DisplayTopology.TreeNode.POSITION_BOTTOM; 20 import static android.hardware.display.DisplayTopology.TreeNode.POSITION_LEFT; 21 import static android.hardware.display.DisplayTopology.TreeNode.POSITION_RIGHT; 22 import static android.hardware.display.DisplayTopology.TreeNode.POSITION_TOP; 23 24 import android.annotation.FlaggedApi; 25 import android.annotation.IntDef; 26 import android.annotation.Nullable; 27 import android.annotation.TestApi; 28 import android.graphics.PointF; 29 import android.graphics.RectF; 30 import android.os.Parcel; 31 import android.os.Parcelable; 32 import android.util.DisplayMetrics; 33 import android.util.IndentingPrintWriter; 34 import android.util.MathUtils; 35 import android.util.Pair; 36 import android.util.Slog; 37 import android.util.SparseArray; 38 import android.util.SparseIntArray; 39 import android.view.Display; 40 41 import androidx.annotation.NonNull; 42 43 import com.android.internal.annotations.VisibleForTesting; 44 import com.android.server.display.feature.flags.Flags; 45 46 import java.io.PrintWriter; 47 import java.io.StringWriter; 48 import java.lang.annotation.Retention; 49 import java.lang.annotation.RetentionPolicy; 50 import java.util.ArrayDeque; 51 import java.util.ArrayList; 52 import java.util.Collections; 53 import java.util.Comparator; 54 import java.util.HashMap; 55 import java.util.List; 56 import java.util.Map; 57 import java.util.Queue; 58 59 /** 60 * Represents the relative placement of extended displays. 61 * Does not support concurrent calls, so a lock should be held when calling into this class. 62 * 63 * @hide 64 */ 65 @TestApi 66 @FlaggedApi(Flags.FLAG_DISPLAY_TOPOLOGY) 67 public final class DisplayTopology implements Parcelable { 68 private static final String TAG = "DisplayTopology"; 69 private static final float EPSILON = 0.0001f; 70 private static final float MAX_GAP = 5; 71 72 @android.annotation.NonNull 73 public static final Creator<DisplayTopology> CREATOR = 74 new Creator<>() { 75 @Override 76 public DisplayTopology createFromParcel(Parcel source) { 77 return new DisplayTopology(source); 78 } 79 80 @Override 81 public DisplayTopology[] newArray(int size) { 82 return new DisplayTopology[size]; 83 } 84 }; 85 86 /** 87 * @param px The value in logical pixels 88 * @param dpi The logical density of the display 89 * @return The value in density-independent pixels 90 * @hide 91 */ pxToDp(float px, int dpi)92 public static float pxToDp(float px, int dpi) { 93 return px * DisplayMetrics.DENSITY_DEFAULT / dpi; 94 } 95 96 /** 97 * @param dp The value in density-independent pixels 98 * @param dpi The logical density of the display 99 * @return The value in logical pixels 100 * @hide 101 */ dpToPx(float dp, int dpi)102 public static float dpToPx(float dp, int dpi) { 103 return dp * dpi / DisplayMetrics.DENSITY_DEFAULT; 104 } 105 106 /** 107 * The topology tree 108 */ 109 @Nullable 110 private TreeNode mRoot; 111 112 /** 113 * The logical display ID of the primary display that will show certain UI elements. 114 * This is not necessarily the same as the default display. 115 */ 116 private int mPrimaryDisplayId = Display.INVALID_DISPLAY; 117 118 /** 119 * @hide 120 */ DisplayTopology()121 public DisplayTopology() {} 122 123 /** 124 * @hide 125 */ DisplayTopology(@ullable TreeNode root, int primaryDisplayId)126 public DisplayTopology(@Nullable TreeNode root, int primaryDisplayId) { 127 mRoot = root; 128 if (mRoot != null) { 129 // Set mRoot's position and offset to predictable values, just so we don't leak state 130 // from some previous arrangement the node was used in, or leak arbitrary values passed 131 // to the TreeNode constructor. The position and offset don't mean anything because 132 // mRoot doesn't have a parent. 133 mRoot.mPosition = POSITION_LEFT; 134 mRoot.mOffset = 0f; 135 } 136 137 mPrimaryDisplayId = primaryDisplayId; 138 } 139 140 /** 141 * @hide 142 */ DisplayTopology(Parcel source)143 public DisplayTopology(Parcel source) { 144 this(source.readTypedObject(TreeNode.CREATOR), source.readInt()); 145 } 146 147 /** 148 * @hide 149 */ 150 @Nullable getRoot()151 public TreeNode getRoot() { 152 return mRoot; 153 } 154 155 /** 156 * @hide 157 */ getPrimaryDisplayId()158 public int getPrimaryDisplayId() { 159 return mPrimaryDisplayId; 160 } 161 162 /** 163 * Add a display to the topology. 164 * If this is the second display in the topology, it will be placed above the first display. 165 * Subsequent displays will be places to the left or right of the second display. 166 * @param displayId The logical display ID 167 * @param width The width of the display 168 * @param height The height of the display 169 * @hide 170 */ addDisplay(int displayId, float width, float height)171 public void addDisplay(int displayId, float width, float height) { 172 if (findDisplay(displayId, mRoot) != null) { 173 return; 174 } 175 if (mRoot == null) { 176 mRoot = new TreeNode(displayId, width, height, POSITION_LEFT, /* offset= */ 0); 177 mPrimaryDisplayId = displayId; 178 } else if (mRoot.mChildren.isEmpty()) { 179 // This is the 2nd display. Align the middles of the top and bottom edges. 180 float offset = mRoot.mWidth / 2 - width / 2; 181 TreeNode display = new TreeNode(displayId, width, height, POSITION_TOP, offset); 182 mRoot.mChildren.add(display); 183 } else { 184 TreeNode rightMostDisplay = findRightMostDisplay(mRoot, mRoot.mWidth).first; 185 TreeNode newDisplay = new TreeNode(displayId, width, height, POSITION_RIGHT, 186 /* offset= */ 0); 187 rightMostDisplay.mChildren.add(newDisplay); 188 } 189 } 190 191 /** 192 * Update the size of a display and normalize the topology. 193 * @param displayId The logical display ID 194 * @param width The new width 195 * @param height The new height 196 * @return True if the topology has changed. 197 * @hide 198 */ updateDisplay(int displayId, float width, float height)199 public boolean updateDisplay(int displayId, float width, float height) { 200 TreeNode display = findDisplay(displayId, mRoot); 201 if (display == null) { 202 return false; 203 } 204 if (floatEquals(display.mWidth, width) && floatEquals(display.mHeight, height)) { 205 return false; 206 } 207 display.mWidth = width; 208 display.mHeight = height; 209 normalize(); 210 Slog.i(TAG, "Display with ID " + displayId + " updated, new width: " + width 211 + ", new height: " + height); 212 return true; 213 } 214 215 /** 216 * Remove a display from the topology. 217 * The default topology is created from the remaining displays, as if they were reconnected 218 * one by one. 219 * @param displayId The logical display ID 220 * @return True if the display was present in the topology and removed. 221 * @hide 222 */ removeDisplay(int displayId)223 public boolean removeDisplay(int displayId) { 224 if (findDisplay(displayId, mRoot) == null) { 225 return false; 226 } 227 228 // Re-add the other displays to a new tree 229 Queue<TreeNode> queue = new ArrayDeque<>(); 230 queue.add(mRoot); 231 mRoot = null; 232 while (!queue.isEmpty()) { 233 TreeNode node = queue.poll(); 234 if (node.mDisplayId != displayId) { 235 addDisplay(node.mDisplayId, node.mWidth, node.mHeight); 236 } 237 queue.addAll(node.mChildren); 238 } 239 240 if (mPrimaryDisplayId == displayId) { 241 if (mRoot != null) { 242 mPrimaryDisplayId = mRoot.mDisplayId; 243 } else { 244 mPrimaryDisplayId = Display.INVALID_DISPLAY; 245 } 246 } 247 return true; 248 } 249 250 /** 251 * Rearranges the topology toward the positions given for each display. The width and height of 252 * each display, as well as the primary display, are not changed by this call. 253 * <p> 254 * Upon returning, the topology will be valid and normalized with each display as close to the 255 * requested positions as possible. 256 * 257 * @param newPos the desired positions (upper-left corner) of each display. The keys in the map 258 * are the display IDs. 259 * @throws IllegalArgumentException if the keys in {@code positions} are not the exact display 260 * IDs in this topology, no more, no less 261 * @hide 262 */ rearrange(Map<Integer, PointF> newPos)263 public void rearrange(Map<Integer, PointF> newPos) { 264 if (mRoot == null) { 265 return; 266 } 267 var availableParents = new ArrayList<TreeNode>(); 268 269 availableParents.addLast(mRoot); 270 271 var needsParent = allNodesIdMap(); 272 273 // In the case of missing items, if this check doesn't detect it, a NPE will be thrown 274 // later. 275 if (needsParent.size() != newPos.size()) { 276 throw new IllegalArgumentException("newPos has wrong number of entries: " + newPos); 277 } 278 279 mRoot.mChildren.clear(); 280 for (TreeNode n : needsParent.values()) { 281 n.mChildren.clear(); 282 } 283 284 needsParent.remove(mRoot.mDisplayId); 285 // Start with a root island and add children to it one-by-one until the island consists of 286 // all the displays. The root island begins with only the root node, which has no 287 // parent. Then we greedily choose an optimal pairing of two nodes, consisting of a node 288 // from the island and a node not yet in the island. This is repeating until all nodes are 289 // in the island. 290 // 291 // The optimal pair is the pair which has the smallest deviation. The deviation consists of 292 // an x-axis component and a y-axis component, called xDeviation and yDeviation. 293 // 294 // The deviations are like distances but a little different. When they are calculated, each 295 // dimension is treated differently, depending on which edges (left+right or top+bottom) are 296 // attached. 297 while (!needsParent.isEmpty()) { 298 double bestDist = Double.POSITIVE_INFINITY; 299 TreeNode bestChild = null, bestParent = null; 300 301 for (var child : needsParent.values()) { 302 PointF childPos = newPos.get(child.mDisplayId); 303 float childRight = childPos.x + child.getWidth(); 304 float childBottom = childPos.y + child.getHeight(); 305 for (var parent : availableParents) { 306 PointF parentPos = newPos.get(parent.mDisplayId); 307 float parentRight = parentPos.x + parent.getWidth(); 308 float parentBottom = parentPos.y + parent.getHeight(); 309 310 // The "amount of overlap" indicates how much of one display is within the other 311 // (considering one axis only). It's zero if they only share an edge and 312 // negative if they're away from each other. 313 // A zero or negative overlap does not make a parenting ineligible, because we 314 // allow for attaching at the corner and for floating point error. 315 float xOverlap = 316 Math.min(parentRight, childRight) - Math.max(parentPos.x, childPos.x); 317 float yOverlap = 318 Math.min(parentBottom, childBottom) - Math.max(parentPos.y, childPos.y); 319 float xDeviation, yDeviation; 320 321 float offset; 322 int pos; 323 if (xOverlap > yOverlap) { 324 // Deviation in each dimension is a penalty in the potential parenting. To 325 // get the X deviation, overlap is subtracted from the lesser width so that 326 // a maximum overlap results in a deviation of zero. 327 // Note that because xOverlap is *subtracted* from the lesser width, no 328 // overlap in X becomes a *penalty* if we are attaching on the top+bottom 329 // edges. 330 // 331 // The Y deviation is simply the distance from the clamping edges. 332 // 333 // Treatment of the X and Y deviations are swapped for 334 // POSITION_LEFT/POSITION_RIGHT attachments in the "else" block below. 335 xDeviation = Math.min(child.getWidth(), parent.getWidth()) - xOverlap; 336 if (childPos.y < parentPos.y) { 337 yDeviation = childBottom - parentPos.y; 338 pos = POSITION_TOP; 339 } else { 340 yDeviation = parentBottom - childPos.y; 341 pos = POSITION_BOTTOM; 342 } 343 offset = childPos.x - parentPos.x; 344 } else { 345 yDeviation = Math.min(child.getHeight(), parent.getHeight()) - yOverlap; 346 if (childPos.x < parentPos.x) { 347 xDeviation = childRight - parentPos.x; 348 pos = POSITION_LEFT; 349 } else { 350 xDeviation = parentRight - childPos.x; 351 pos = POSITION_RIGHT; 352 } 353 offset = childPos.y - parentPos.y; 354 } 355 356 double dist = Math.hypot(xDeviation, yDeviation); 357 if (dist >= bestDist) { 358 continue; 359 } 360 361 bestDist = dist; 362 bestChild = child; 363 bestParent = parent; 364 // Eagerly update the child's parenting info, even though we may not use it, in 365 // which case it will be overwritten later. 366 bestChild.mPosition = pos; 367 bestChild.mOffset = offset; 368 } 369 } 370 371 assert bestParent != null & bestChild != null; 372 373 bestParent.addChild(bestChild); 374 if (null == needsParent.remove(bestChild.mDisplayId)) { 375 throw new IllegalStateException("child not in pending set! " + bestChild); 376 } 377 availableParents.add(bestChild); 378 } 379 380 // The conversion may have introduced an intersection of two display rects. If they are 381 // bigger than our error tolerance, this function will remove them. 382 normalize(); 383 } 384 385 /** 386 * Clamp offsets and remove any overlaps between displays. 387 * @hide 388 */ normalize()389 public void normalize() { 390 if (mRoot == null) { 391 return; 392 } 393 clampOffsets(mRoot); 394 395 Map<TreeNode, RectF> bounds = new HashMap<>(); 396 Map<TreeNode, Integer> depths = new HashMap<>(); 397 Map<TreeNode, TreeNode> parents = new HashMap<>(); 398 getInfo(bounds, depths, parents, mRoot, /* x= */ 0, /* y= */ 0, /* depth= */ 0); 399 400 // Sort the displays first by their depth in the tree, then by the distance of their top 401 // left point from the root display's origin (0, 0). This way we process the displays 402 // starting at the root and we push out a display if necessary. 403 Comparator<TreeNode> comparator = (d1, d2) -> { 404 if (d1 == d2) { 405 return 0; 406 } 407 408 int compareDepths = Integer.compare(depths.get(d1), depths.get(d2)); 409 if (compareDepths != 0) { 410 return compareDepths; 411 } 412 413 RectF bounds1 = bounds.get(d1); 414 RectF bounds2 = bounds.get(d2); 415 return Double.compare(Math.hypot(bounds1.left, bounds1.top), 416 Math.hypot(bounds2.left, bounds2.top)); 417 }; 418 List<TreeNode> displays = new ArrayList<>(bounds.keySet()); 419 displays.sort(comparator); 420 421 for (int i = 1; i < displays.size(); i++) { 422 TreeNode targetDisplay = displays.get(i); 423 TreeNode lastIntersectingSourceDisplay = null; 424 float lastOffsetX = 0; 425 float lastOffsetY = 0; 426 427 for (int j = 0; j < i; j++) { 428 TreeNode sourceDisplay = displays.get(j); 429 RectF sourceBounds = bounds.get(sourceDisplay); 430 RectF targetBounds = bounds.get(targetDisplay); 431 432 if (!RectF.intersects(sourceBounds, targetBounds)) { 433 continue; 434 } 435 436 // Find the offset by which to move the display. Pick the smaller one among the x 437 // and y axes. 438 float offsetX = targetBounds.left >= 0 439 ? sourceBounds.right - targetBounds.left 440 : sourceBounds.left - targetBounds.right; 441 float offsetY = targetBounds.top >= 0 442 ? sourceBounds.bottom - targetBounds.top 443 : sourceBounds.top - targetBounds.bottom; 444 if (Math.abs(offsetX) <= Math.abs(offsetY)) { 445 targetBounds.left += offsetX; 446 targetBounds.right += offsetX; 447 // We need to also update the offset in the tree 448 if (targetDisplay.mPosition == POSITION_TOP 449 || targetDisplay.mPosition == POSITION_BOTTOM) { 450 targetDisplay.mOffset += offsetX; 451 } 452 offsetY = 0; 453 } else { 454 targetBounds.top += offsetY; 455 targetBounds.bottom += offsetY; 456 // We need to also update the offset in the tree 457 if (targetDisplay.mPosition == POSITION_LEFT 458 || targetDisplay.mPosition == POSITION_RIGHT) { 459 targetDisplay.mOffset += offsetY; 460 } 461 offsetX = 0; 462 } 463 464 lastIntersectingSourceDisplay = sourceDisplay; 465 lastOffsetX = offsetX; 466 lastOffsetY = offsetY; 467 } 468 469 // Now re-parent the target display to the last intersecting source display if it no 470 // longer touches its parent. 471 if (lastIntersectingSourceDisplay == null) { 472 // There was no overlap. 473 continue; 474 } 475 TreeNode parent = parents.get(targetDisplay); 476 if (parent == lastIntersectingSourceDisplay) { 477 // The displays are moved in such a way that they're adjacent to the intersecting 478 // display. If the last intersecting display happens to be the parent then we 479 // already know that the display is adjacent to its parent. 480 continue; 481 } 482 483 RectF childBounds = bounds.get(targetDisplay); 484 RectF parentBounds = bounds.get(parent); 485 // Check that the edges are on the same line 486 boolean areTouching = switch (targetDisplay.mPosition) { 487 case POSITION_LEFT -> floatEquals(parentBounds.left, childBounds.right); 488 case POSITION_RIGHT -> floatEquals(parentBounds.right, childBounds.left); 489 case POSITION_TOP -> floatEquals(parentBounds.top, childBounds.bottom); 490 case POSITION_BOTTOM -> floatEquals(parentBounds.bottom, childBounds.top); 491 default -> throw new IllegalStateException( 492 "Unexpected value: " + targetDisplay.mPosition); 493 }; 494 // Check that the offset is within bounds 495 areTouching &= switch (targetDisplay.mPosition) { 496 case POSITION_LEFT, POSITION_RIGHT -> 497 childBounds.bottom + EPSILON > parentBounds.top 498 && childBounds.top < parentBounds.bottom + EPSILON; 499 case POSITION_TOP, POSITION_BOTTOM -> 500 childBounds.right + EPSILON > parentBounds.left 501 && childBounds.left < parentBounds.right + EPSILON; 502 default -> throw new IllegalStateException( 503 "Unexpected value: " + targetDisplay.mPosition); 504 }; 505 506 if (!areTouching) { 507 // Re-parent the display. 508 parent.mChildren.remove(targetDisplay); 509 RectF lastIntersectingSourceDisplayBounds = 510 bounds.get(lastIntersectingSourceDisplay); 511 lastIntersectingSourceDisplay.mChildren.add(targetDisplay); 512 513 if (lastOffsetX != 0) { 514 targetDisplay.mPosition = lastOffsetX > 0 ? POSITION_RIGHT : POSITION_LEFT; 515 targetDisplay.mOffset = 516 childBounds.top - lastIntersectingSourceDisplayBounds.top; 517 } else if (lastOffsetY != 0) { 518 targetDisplay.mPosition = lastOffsetY > 0 ? POSITION_BOTTOM : POSITION_TOP; 519 targetDisplay.mOffset = 520 childBounds.left - lastIntersectingSourceDisplayBounds.left; 521 } 522 } 523 } 524 525 // Sort children lists by display ID. 526 final Comparator<TreeNode> idComparator = (d1, d2) -> { 527 return Integer.compare(d1.mDisplayId, d2.mDisplayId); 528 }; 529 for (TreeNode display : displays) { 530 display.mChildren.sort(idComparator); 531 } 532 } 533 534 /** 535 * @return A deep copy of the topology that will not be modified by the system. 536 * @hide 537 */ copy()538 public DisplayTopology copy() { 539 TreeNode rootCopy = mRoot == null ? null : mRoot.copy(); 540 return new DisplayTopology(rootCopy, mPrimaryDisplayId); 541 } 542 543 /** 544 * Assign absolute bounds to each display. The top-left corner of the root is at position 545 * (0, 0). 546 * @return Map from logical display ID to the display's absolute bounds 547 */ 548 @NonNull getAbsoluteBounds()549 public SparseArray<RectF> getAbsoluteBounds() { 550 Map<TreeNode, RectF> bounds = new HashMap<>(); 551 getInfo(bounds, /* depths= */ null, /* parents= */ null, mRoot, /* x= */ 0, /* y= */ 0, 552 /* depth= */ 0); 553 SparseArray<RectF> boundsById = new SparseArray<>(); 554 for (Map.Entry<TreeNode, RectF> entry : bounds.entrySet()) { 555 boundsById.append(entry.getKey().mDisplayId, entry.getValue()); 556 } 557 return boundsById; 558 } 559 560 @Override describeContents()561 public int describeContents() { 562 return 0; 563 } 564 565 @Override writeToParcel(@onNull Parcel dest, int flags)566 public void writeToParcel(@NonNull Parcel dest, int flags) { 567 dest.writeTypedObject(mRoot, flags); 568 dest.writeInt(mPrimaryDisplayId); 569 } 570 571 /** 572 * Print the object's state and debug information into the given stream. 573 * @hide 574 * @param pw The stream to dump information to. 575 */ dump(PrintWriter pw)576 public void dump(PrintWriter pw) { 577 pw.println("DisplayTopology:"); 578 pw.println("--------------------"); 579 IndentingPrintWriter ipw = new IndentingPrintWriter(pw); 580 ipw.increaseIndent(); 581 582 ipw.println("mPrimaryDisplayId: " + mPrimaryDisplayId); 583 584 ipw.println("Topology tree:"); 585 if (mRoot != null) { 586 ipw.increaseIndent(); 587 mRoot.dump(ipw); 588 ipw.decreaseIndent(); 589 } 590 } 591 592 @Override equals(Object obj)593 public boolean equals(Object obj) { 594 if (!(obj instanceof DisplayTopology)) { 595 return false; 596 } 597 return obj.toString().equals(toString()); 598 } 599 600 @Override hashCode()601 public int hashCode() { 602 return toString().hashCode(); 603 } 604 605 @Override toString()606 public String toString() { 607 StringWriter out = new StringWriter(); 608 PrintWriter writer = new PrintWriter(out); 609 dump(writer); 610 return out.toString(); 611 } 612 613 /** 614 * @param display The display from which the search should start. 615 * @param xPos The x position of the right edge of that display. 616 * @return The display that is the furthest to the right and the x position of the right edge 617 * of that display 618 */ findRightMostDisplay(TreeNode display, float xPos)619 private static Pair<TreeNode, Float> findRightMostDisplay(TreeNode display, float xPos) { 620 Pair<TreeNode, Float> result = new Pair<>(display, xPos); 621 for (TreeNode child : display.mChildren) { 622 // The x position of the right edge of the child 623 float childXPos; 624 switch (child.mPosition) { 625 case POSITION_LEFT -> childXPos = xPos - display.mWidth; 626 case POSITION_TOP, POSITION_BOTTOM -> 627 childXPos = xPos - display.mWidth + child.mOffset + child.mWidth; 628 case POSITION_RIGHT -> childXPos = xPos + child.mWidth; 629 default -> throw new IllegalStateException("Unexpected value: " + child.mPosition); 630 } 631 632 // Recursive call - find the rightmost display starting from the child 633 Pair<TreeNode, Float> childResult = findRightMostDisplay(child, childXPos); 634 // Check if the one found is further right 635 if (childResult.second > result.second) { 636 result = new Pair<>(childResult.first, childResult.second); 637 } 638 } 639 return result; 640 } 641 642 /** 643 * @hide 644 */ 645 @Nullable findDisplay(int displayId, @Nullable TreeNode startingNode)646 public static TreeNode findDisplay(int displayId, @Nullable TreeNode startingNode) { 647 if (startingNode == null) { 648 return null; 649 } 650 if (startingNode.mDisplayId == displayId) { 651 return startingNode; 652 } 653 for (TreeNode child : startingNode.mChildren) { 654 TreeNode display = findDisplay(displayId, child); 655 if (display != null) { 656 return display; 657 } 658 } 659 return null; 660 } 661 662 /** 663 * Get information about the topology. 664 * Assigns positions to each display to compute the bounds. The root is at position (0, 0). 665 * @param bounds The map where the bounds of each display will be put 666 * @param depths The map where the depths of each display in the tree will be put 667 * @param parents The map where the parent of each display will be put 668 * @param display The starting node 669 * @param x The starting x position 670 * @param y The starting y position 671 * @param depth The starting depth 672 */ getInfo(@ullable Map<TreeNode, RectF> bounds, @Nullable Map<TreeNode, Integer> depths, @Nullable Map<TreeNode, TreeNode> parents, @Nullable TreeNode display, float x, float y, int depth)673 private static void getInfo(@Nullable Map<TreeNode, RectF> bounds, 674 @Nullable Map<TreeNode, Integer> depths, @Nullable Map<TreeNode, TreeNode> parents, 675 @Nullable TreeNode display, float x, float y, int depth) { 676 if (display == null) { 677 return; 678 } 679 if (bounds != null) { 680 bounds.put(display, new RectF(x, y, x + display.mWidth, y + display.mHeight)); 681 } 682 if (depths != null) { 683 depths.put(display, depth); 684 } 685 for (TreeNode child : display.mChildren) { 686 if (parents != null) { 687 parents.put(child, display); 688 } 689 if (child.mPosition == POSITION_LEFT) { 690 getInfo(bounds, depths, parents, child, x - child.mWidth, y + child.mOffset, 691 depth + 1); 692 } else if (child.mPosition == POSITION_RIGHT) { 693 getInfo(bounds, depths, parents, child, x + display.mWidth, y + child.mOffset, 694 depth + 1); 695 } else if (child.mPosition == POSITION_TOP) { 696 getInfo(bounds, depths, parents, child, x + child.mOffset, y - child.mHeight, 697 depth + 1); 698 } else if (child.mPosition == POSITION_BOTTOM) { 699 getInfo(bounds, depths, parents, child, x + child.mOffset, y + display.mHeight, 700 depth + 1); 701 } 702 } 703 } 704 705 /** 706 * Check if two displays are touching. 707 * If the gap between two edges is <= {@link MAX_GAP}, they are still considered adjacent. 708 * The position indicates where the second display is touching the first one and the offset 709 * indicates where along the first display the second display is located. 710 * @param bounds1 The bounds of the first display 711 * @param bounds2 The bounds of the second display 712 * @return Empty list if the displays are not adjacent; 713 * List of one Pair(position, offset) if the displays are adjacent but not by a corner; 714 * List of two Pair(position, offset) if the displays are adjacent by a corner. 715 */ findDisplayPlacements(RectF bounds1, RectF bounds2)716 private List<Pair<Integer, Float>> findDisplayPlacements(RectF bounds1, RectF bounds2) { 717 List<Pair<Integer, Float>> placements = new ArrayList<>(); 718 if (bounds1.top <= bounds2.bottom + MAX_GAP && bounds2.top <= bounds1.bottom + MAX_GAP) { 719 if (MathUtils.abs(bounds1.left - bounds2.right) <= MAX_GAP) { 720 placements.add(new Pair<>(POSITION_LEFT, bounds2.top - bounds1.top)); 721 } 722 if (MathUtils.abs(bounds1.right - bounds2.left) <= MAX_GAP) { 723 placements.add(new Pair<>(POSITION_RIGHT, bounds2.top - bounds1.top)); 724 } 725 } 726 if (bounds1.left <= bounds2.right + MAX_GAP && bounds2.left <= bounds1.right + MAX_GAP) { 727 if (MathUtils.abs(bounds1.top - bounds2.bottom) < MAX_GAP) { 728 placements.add(new Pair<>(POSITION_TOP, bounds2.left - bounds1.left)); 729 } 730 if (MathUtils.abs(bounds1.bottom - bounds2.top) < MAX_GAP) { 731 placements.add(new Pair<>(POSITION_BOTTOM, bounds2.left - bounds1.left)); 732 } 733 } 734 return placements; 735 } 736 737 /** 738 * @param densityPerDisplay The logical display densities, indexed by logical display ID 739 * @return The graph representation of the topology. If there is a corner adjacency, the same 740 * display will appear twice in the list of adjacent displays with both possible placements. 741 * @hide 742 */ 743 @Nullable getGraph(SparseIntArray densityPerDisplay)744 public DisplayTopologyGraph getGraph(SparseIntArray densityPerDisplay) { 745 // Sort the displays by position 746 SparseArray<RectF> bounds = getAbsoluteBounds(); 747 Comparator<Integer> comparator = (displayId1, displayId2) -> { 748 RectF bounds1 = bounds.get(displayId1); 749 RectF bounds2 = bounds.get(displayId2); 750 751 int compareX = Float.compare(bounds1.left, bounds2.left); 752 if (compareX != 0) { 753 return compareX; 754 } 755 return Float.compare(bounds1.top, bounds2.top); 756 }; 757 List<Integer> displayIds = new ArrayList<>(bounds.size()); 758 for (int i = 0; i < bounds.size(); i++) { 759 displayIds.add(bounds.keyAt(i)); 760 } 761 displayIds.sort(comparator); 762 763 SparseArray<List<DisplayTopologyGraph.AdjacentDisplay>> adjacentDisplaysPerId = 764 new SparseArray<>(); 765 for (int id : displayIds) { 766 if (densityPerDisplay.get(id) == 0) { 767 Slog.e(TAG, "Cannot construct graph, no density for display " + id); 768 return null; 769 } 770 adjacentDisplaysPerId.append(id, new ArrayList<>(Math.min(10, displayIds.size()))); 771 } 772 773 // Find touching displays 774 for (int i = 0; i < displayIds.size(); i++) { 775 int displayId1 = displayIds.get(i); 776 RectF bounds1 = bounds.get(displayId1); 777 List<DisplayTopologyGraph.AdjacentDisplay> adjacentDisplays1 = 778 adjacentDisplaysPerId.get(displayId1); 779 780 for (int j = i + 1; j < displayIds.size(); j++) { 781 int displayId2 = displayIds.get(j); 782 RectF bounds2 = bounds.get(displayId2); 783 List<DisplayTopologyGraph.AdjacentDisplay> adjacentDisplays2 = 784 adjacentDisplaysPerId.get(displayId2); 785 786 List<Pair<Integer, Float>> placements1 = findDisplayPlacements(bounds1, bounds2); 787 List<Pair<Integer, Float>> placements2 = findDisplayPlacements(bounds2, bounds1); 788 for (Pair<Integer, Float> placement : placements1) { 789 adjacentDisplays1.add(new DisplayTopologyGraph.AdjacentDisplay(displayId2, 790 /* position= */ placement.first, /* offsetDp= */ placement.second)); 791 } 792 for (Pair<Integer, Float> placement : placements2) { 793 adjacentDisplays2.add(new DisplayTopologyGraph.AdjacentDisplay(displayId1, 794 /* position= */ placement.first, /* offsetDp= */ placement.second)); 795 } 796 if (bounds2.left >= bounds1.right + EPSILON) { 797 // This and the subsequent displays are already too far away 798 break; 799 } 800 } 801 } 802 803 DisplayTopologyGraph.DisplayNode[] nodes = 804 new DisplayTopologyGraph.DisplayNode[adjacentDisplaysPerId.size()]; 805 for (int i = 0; i < nodes.length; i++) { 806 int displayId = adjacentDisplaysPerId.keyAt(i); 807 nodes[i] = new DisplayTopologyGraph.DisplayNode(displayId, 808 densityPerDisplay.get(displayId), adjacentDisplaysPerId.valueAt(i).toArray( 809 new DisplayTopologyGraph.AdjacentDisplay[0])); 810 } 811 return new DisplayTopologyGraph(mPrimaryDisplayId, nodes); 812 } 813 814 /** 815 * Tests whether two float values are within a small enough tolerance of each other. 816 * @param a first float to compare 817 * @param b second float to compare 818 * @return whether the two values are within a small enough tolerance value 819 */ floatEquals(float a, float b)820 private static boolean floatEquals(float a, float b) { 821 return a == b || (Float.isNaN(a) && Float.isNaN(b)) || Math.abs(a - b) < EPSILON; 822 } 823 allNodesIdMap()824 private Map<Integer, TreeNode> allNodesIdMap() { 825 var pend = new ArrayDeque<TreeNode>(); 826 var found = new HashMap<Integer, TreeNode>(); 827 828 pend.push(mRoot); 829 do { 830 TreeNode node = pend.pop(); 831 found.put(node.mDisplayId, node); 832 pend.addAll(node.mChildren); 833 } while (!pend.isEmpty()); 834 835 return found; 836 } 837 838 /** 839 * Ensure that the offsets of all displays within the given tree are within bounds. 840 * @param display The starting node 841 */ clampOffsets(@ullable TreeNode display)842 private void clampOffsets(@Nullable TreeNode display) { 843 if (display == null) { 844 return; 845 } 846 for (TreeNode child : display.mChildren) { 847 if (child.mPosition == POSITION_LEFT || child.mPosition == POSITION_RIGHT) { 848 child.mOffset = MathUtils.constrain(child.mOffset, -child.mHeight, display.mHeight); 849 } else if (child.mPosition == POSITION_TOP || child.mPosition == POSITION_BOTTOM) { 850 child.mOffset = MathUtils.constrain(child.mOffset, -child.mWidth, display.mWidth); 851 } 852 clampOffsets(child); 853 } 854 } 855 856 /** 857 * @hide 858 */ 859 public static final class TreeNode implements Parcelable { 860 public static final int POSITION_LEFT = 0; 861 public static final int POSITION_TOP = 1; 862 public static final int POSITION_RIGHT = 2; 863 public static final int POSITION_BOTTOM = 3; 864 865 @IntDef(prefix = { "POSITION_" }, value = { 866 POSITION_LEFT, POSITION_TOP, POSITION_RIGHT, POSITION_BOTTOM 867 }) 868 @Retention(RetentionPolicy.SOURCE) 869 public @interface Position{} 870 871 @android.annotation.NonNull 872 public static final Creator<TreeNode> CREATOR = 873 new Creator<>() { 874 @Override 875 public TreeNode createFromParcel(Parcel source) { 876 return new TreeNode(source); 877 } 878 879 @Override 880 public TreeNode[] newArray(int size) { 881 return new TreeNode[size]; 882 } 883 }; 884 885 /** 886 * The logical display ID 887 */ 888 private final int mDisplayId; 889 890 /** 891 * The width of the display in density-independent pixels (dp). 892 */ 893 private float mWidth; 894 895 /** 896 * The height of the display in density-independent pixels (dp). 897 */ 898 private float mHeight; 899 900 /** 901 * The position of this display relative to its parent. 902 */ 903 @Position 904 private int mPosition; 905 906 /** 907 * The distance from the top edge of the parent display to the top edge of this display (in 908 * case of POSITION_LEFT or POSITION_RIGHT) or from the left edge of the parent display 909 * to the left edge of this display (in case of POSITION_TOP or POSITION_BOTTOM). The unit 910 * used is density-independent pixels (dp). 911 */ 912 private float mOffset; 913 914 private final List<TreeNode> mChildren; 915 916 @VisibleForTesting TreeNode(int displayId, float width, float height, @Position int position, float offset)917 public TreeNode(int displayId, float width, float height, @Position int position, 918 float offset) { 919 this(displayId, width, height, position, offset, List.of()); 920 } 921 TreeNode(int displayId, float width, float height, int position, float offset, List<TreeNode> children)922 public TreeNode(int displayId, float width, float height, int position, 923 float offset, List<TreeNode> children) { 924 mDisplayId = displayId; 925 mWidth = width; 926 mHeight = height; 927 mPosition = position; 928 mOffset = offset; 929 mChildren = new ArrayList<>(children); 930 } 931 TreeNode(Parcel source)932 public TreeNode(Parcel source) { 933 this(source.readInt(), source.readFloat(), source.readFloat(), source.readInt(), 934 source.readFloat()); 935 source.readTypedList(mChildren, CREATOR); 936 } 937 getDisplayId()938 public int getDisplayId() { 939 return mDisplayId; 940 } 941 getWidth()942 public float getWidth() { 943 return mWidth; 944 } 945 getHeight()946 public float getHeight() { 947 return mHeight; 948 } 949 getPosition()950 public int getPosition() { 951 return mPosition; 952 } 953 getOffset()954 public float getOffset() { 955 return mOffset; 956 } 957 getChildren()958 public List<TreeNode> getChildren() { 959 return Collections.unmodifiableList(mChildren); 960 } 961 962 /** 963 * @return A deep copy of the node that will not be modified by the system. 964 */ copy()965 public TreeNode copy() { 966 TreeNode copy = new TreeNode(mDisplayId, mWidth, mHeight, mPosition, mOffset); 967 for (TreeNode child : mChildren) { 968 copy.mChildren.add(child.copy()); 969 } 970 return copy; 971 } 972 973 @Override toString()974 public String toString() { 975 return "Display {id=" + mDisplayId + ", width=" + mWidth + ", height=" + mHeight 976 + ", position=" + positionToString(mPosition) + ", offset=" + mOffset + "}"; 977 } 978 979 /** 980 * @param position The position 981 * @return The string representation 982 */ positionToString(@osition int position)983 public static String positionToString(@Position int position) { 984 return switch (position) { 985 case POSITION_LEFT -> "left"; 986 case POSITION_TOP -> "top"; 987 case POSITION_RIGHT -> "right"; 988 case POSITION_BOTTOM -> "bottom"; 989 default -> throw new IllegalStateException("Unexpected value: " + position); 990 }; 991 } 992 993 @Override describeContents()994 public int describeContents() { 995 return 0; 996 } 997 998 @Override writeToParcel(@onNull Parcel dest, int flags)999 public void writeToParcel(@NonNull Parcel dest, int flags) { 1000 dest.writeInt(mDisplayId); 1001 dest.writeFloat(mWidth); 1002 dest.writeFloat(mHeight); 1003 dest.writeInt(mPosition); 1004 dest.writeFloat(mOffset); 1005 dest.writeTypedList(mChildren); 1006 } 1007 1008 /** 1009 * Print the object's state and debug information into the given stream. 1010 * @param ipw The stream to dump information to. 1011 */ dump(IndentingPrintWriter ipw)1012 public void dump(IndentingPrintWriter ipw) { 1013 ipw.println(this); 1014 ipw.increaseIndent(); 1015 for (TreeNode child : mChildren) { 1016 child.dump(ipw); 1017 } 1018 ipw.decreaseIndent(); 1019 } 1020 1021 /** 1022 * @param child The child to add 1023 */ 1024 @VisibleForTesting addChild(TreeNode child)1025 public void addChild(TreeNode child) { 1026 mChildren.add(child); 1027 } 1028 } 1029 } 1030