Detect and fix overlapping displays

ui/display/display_layout.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/display/display_layout.h"
 
 #include <algorithm>
 #include <set>
 #include <sstream>
 
@@ skipping 18 matching lines @@
 // to change this value in case to support even larger displays.
 const int kMaxValidOffset = 10000;
 
 bool IsIdInList(int64_t id, const DisplayIdList& list) {
   const auto iter =
       std::find_if(list.begin(), list.end(),
                    [id](int64_t display_id) { return display_id == id; });
   return iter != list.end();
 }
 
+// Ruturns nullptr if display with |id| is not found.
 Display* FindDisplayById(Displays* display_list, int64_t id) {
   auto iter =
       std::find_if(display_list->begin(), display_list->end(),
                    [id](const Display& display) { return display.id() == id; });
-  return &(*iter);
+  return iter == display_list->end() ? nullptr : &(*iter);
+}
+
+enum class IntersectionAxis {
+  POSITIVE_X,
+  NEGATIVE_X,
+  POSITIVE_Y,
+  NEGATIVE_Y,
+};

[oshima, 2017/01/09 21:46:46]

can you document how logic works?

[afakhry, 2017/01/12 21:00:56]

I added a comment above DeIntersectDisplays(), and more comments overall.

+
+// Returns true if the child and parent displays are sharing a border.
+bool AreDisplaysTouching(const Display& child_display,
+                         const Display& parent_display,
+                         DisplayPlacement::Position child_position) {
+  const gfx::Rect& a_bounds = child_display.bounds();
+  const gfx::Rect& b_bounds = parent_display.bounds();

[oshima, 2017/01/09 21:46:46]

you can get intersects and check if the width is 1.

[afakhry, 2017/01/12 21:00:56]

Unfortunately, that doesn't work. The intersection width is 0 rather than 1 if
they are touching.

+
+  int rx = std::max(a_bounds.x(), b_bounds.x());
+  int ry = std::max(a_bounds.y(), b_bounds.y());
+  int rr = std::min(a_bounds.right(), b_bounds.right());
+  int rb = std::min(a_bounds.bottom(), b_bounds.bottom());
+
+  if (child_position == DisplayPlacement::TOP ||
+      child_position == DisplayPlacement::BOTTOM) {
+    return rb == ry;
+  }
+
+  return rr == rx;
+}
+
+void DeIntersectDisplaysAlong(IntersectionAxis axis,
+                              int64_t primary_id,
+                              std::vector<Display*>* displays,
+                              std::vector<DisplayPlacement>* placement_list,
+                              std::set<int64_t>* updated_displays) {
+  // Start processing in the required direction from the origin (i.e. from the
+  // primary display). This is needed as we never offset the primary display.
+  auto primary_itr =
+      std::find_if(displays->begin(), displays->end(),
+                   [primary_id](Display* d) { return d->id() == primary_id; });
+  const int begin =
+      primary_itr == displays->end() ? 0 : primary_itr - displays->begin();
+  const int end = static_cast<int>(displays->size());
+  int increment = 1;
+
+  if (axis == IntersectionAxis::NEGATIVE_X ||
+      axis == IntersectionAxis::NEGATIVE_Y) {
+    increment = -1;
+  }
+
+  for (int i = begin; i >= 0 && i < end; i += increment) {
+    const Display* source_display = (*displays)[i];
+    const gfx::Rect source_bounds = source_display->bounds();
+    for (int j = i + increment; j >= 0 && j < end; j += increment) {
+      Display* target_display = (*displays)[j];
+      const gfx::Rect target_bounds = target_display->bounds();
+
+      gfx::Rect intersection = source_bounds;
+      intersection.Intersect(target_bounds);
+      if (intersection.IsEmpty())

[oshima, 2017/01/09 21:46:46]

can't you also skip if they're touching?

[afakhry, 2017/01/12 21:00:56]

Yes, but I need the intersection Rect anyways below.

+        continue;
+
+      // Offset the target display in the direction of the smaller overlap side
+      // if it's on the axis we're working on.
+      int offset_x = 0;
+      int offset_y = 0;
+      gfx::Point new_origin = target_bounds.origin();
+      if (intersection.width() <= intersection.height()) {
+        if (axis == IntersectionAxis::POSITIVE_X)
+          offset_x = source_bounds.right() - intersection.x();
+        else if (axis == IntersectionAxis::NEGATIVE_X)
+          offset_x = -(target_bounds.right() - intersection.x());
+      } else if (intersection.width() > intersection.height()) {
+        if (axis == IntersectionAxis::POSITIVE_Y)
+          offset_y = source_bounds.bottom() - intersection.y();
+        else if (axis == IntersectionAxis::NEGATIVE_Y)
+          offset_y = -(target_bounds.bottom() - intersection.y());
+      }
+
+      if (offset_x == 0 && offset_y == 0)
+        continue;
+
+      new_origin.Offset(offset_x, offset_y);
+      gfx::Insets insets = target_display->GetWorkAreaInsets();
+      target_display->set_bounds(gfx::Rect(new_origin, target_bounds.size()));
+      target_display->UpdateWorkAreaFromInsets(insets);
+
+      if (updated_displays)
+        updated_displays->insert(target_display->id());
+
+      // The offset target display may have moved such that it no longer touches
+      // its parent. Reparent if necessary.
+      auto target_display_placement_itr =
+          std::find_if(placement_list->begin(), placement_list->end(),
+                       [&target_display](const DisplayPlacement& p) {
+                         return p.display_id == target_display->id();
+                       });
+      if (target_display_placement_itr == placement_list->end())

[oshima, 2017/01/09 21:46:46]

this should happen only for primary, right?

[afakhry, 2017/01/12 21:00:56]

As a matter of fact, this should never happen! We always start processing from
the primary display, so the primary display is always the source, never the
target display.

I replaced this 'if' with a 'DCHECK'.

+        continue;
+      if (target_display_placement_itr->parent_display_id ==
+          source_display->id()) {
+        continue;
+      }
+
+      auto parent_display_itr =
+          std::find_if(displays->begin(), displays->end(),
+                       [&target_display_placement_itr](Display* display) {
+                         return display->id() ==
+                                target_display_placement_itr->parent_display_id;
+                       });
+      if (parent_display_itr == displays->end())

[oshima, 2017/01/09 21:46:46]

Can this happen?

[afakhry, 2017/01/12 21:00:56]

It shouldn't. Replaced with a DCHECK.

+        continue;
+
+      if (AreDisplaysTouching(*target_display, *(*parent_display_itr),
+                              target_display_placement_itr->position)) {
+        continue;
+      }
+
+      // Reparent the target to source and update the position. No need to
+      // update the offset here as it will be done later when UpdateOffsets()
+      // is called.
+      target_display_placement_itr->parent_display_id = source_display->id();

[oshima, 2017/01/09 21:46:46]

this should not happen to the primary, otherwise it'll create circular
dependency.

[afakhry, 2017/01/12 21:00:56]

The primary display is never the target display. So this should never happen.
However, I added a check to make sure that we don't offset the target display if
the source is a descendant of it. I also added a new test to make sure this case
is handled correctly.

+      if (axis == IntersectionAxis::POSITIVE_X ||
+          axis == IntersectionAxis::NEGATIVE_X) {
+        target_display_placement_itr->position =
+            axis == IntersectionAxis::POSITIVE_X ? DisplayPlacement::RIGHT
+                                                 : DisplayPlacement::LEFT;
+      } else {
+        target_display_placement_itr->position =
+            axis == IntersectionAxis::POSITIVE_Y ? DisplayPlacement::BOTTOM
+                                                 : DisplayPlacement::TOP;
+      }
+    }
+  }
+}
+
+void DeIntersectDisplays(int64_t primary_id,
+                         Displays* display_list,
+                         std::vector<DisplayPlacement>* placement_list,
+                         std::set<int64_t>* updated_displays) {
+  std::vector<Display*> displays;
+  for (auto& display : *display_list)
+    displays.push_back(&display);
+
+  // Sort the displays by "Y" then by descending "X" and process in both
+  // directions.
+  std::sort(displays.begin(), displays.end(), [](Display* d1, Display* d2) {
+    if (d1->bounds().y() == d2->bounds().y()) {
+      // This makes displays with same y be sorted from right to left.
+      return d1->bounds().x() > d2->bounds().x();
+    }
+
+    return d1->bounds().y() < d2->bounds().y();
+  });
+  DeIntersectDisplaysAlong(IntersectionAxis::POSITIVE_Y, primary_id, &displays,
+                           placement_list, updated_displays);
+  DeIntersectDisplaysAlong(IntersectionAxis::NEGATIVE_Y, primary_id, &displays,
+                           placement_list, updated_displays);
+
+  // Sort the displays by "X" then by ascending "Y" and process in both
+  // directions.
+  std::sort(displays.begin(), displays.end(), [](Display* d1, Display* d2) {
+    if (d1->bounds().x() == d2->bounds().x()) {
+      // This makes displays with same x be sorted from top to bottom.
+      return d1->bounds().y() < d2->bounds().y();
+    }
+
+    return d1->bounds().x() < d2->bounds().x();
+  });
+  DeIntersectDisplaysAlong(IntersectionAxis::POSITIVE_X, primary_id, &displays,
+                           placement_list, updated_displays);
+  DeIntersectDisplaysAlong(IntersectionAxis::NEGATIVE_X, primary_id, &displays,
+                           placement_list, updated_displays);

[oshima, 2017/01/09 21:46:46]

can't adjusting X will cause new overlap?

[afakhry, 2017/01/12 21:00:56]

Yes, in a very rare case. To fix that, I modified it to run the algorithm as
long as there's still an overlap for a maximum of 4 iterations. In the third
iteration, I relax the requirement of offsetting only along the shorter overlap
side, and just offset along the axis.

The newly added test checks this special case.

 }
 
 }  // namespace
 
 ////////////////////////////////////////////////////////////////////////////////
 // DisplayPlacement
 
 DisplayPlacement::DisplayPlacement()
     : DisplayPlacement(kInvalidDisplayId,
                        kInvalidDisplayId,
@@ skipping 121 matching lines @@
 ////////////////////////////////////////////////////////////////////////////////
 // DisplayLayout
 
 DisplayLayout::DisplayLayout()
     : mirrored(false), default_unified(true), primary_id(kInvalidDisplayId) {}
 
 DisplayLayout::~DisplayLayout() {}
 
 void DisplayLayout::ApplyToDisplayList(Displays* display_list,
                                        std::vector<int64_t>* updated_ids,
-                                       int minimum_offset_overlap) const {
+                                       int minimum_offset_overlap) {
   // Layout from primary, then dependent displays.
   std::set<int64_t> parents;
+  std::set<int64_t> updated_displays;
   parents.insert(primary_id);
   while (parents.size()) {
     int64_t parent_id = *parents.begin();
     parents.erase(parent_id);
     for (const DisplayPlacement& placement : placement_list) {
       if (placement.parent_display_id == parent_id) {
         if (ApplyDisplayPlacement(placement, display_list,
-                                  minimum_offset_overlap) &&
-            updated_ids) {
-          updated_ids->push_back(placement.display_id);
+                                  minimum_offset_overlap)) {
+          updated_displays.insert(placement.display_id);
         }
         parents.insert(placement.display_id);
       }
     }
   }
+
+  // Now that all the placements have been applied, we must detect and fix any
+  // overlapping displays.
+  DeIntersectDisplays(primary_id, display_list, &placement_list,
+                      &updated_displays);
+
+  // The offsets might have changed and we must update them.
+  UpdateOffsets(display_list);
+
+  if (updated_ids) {
+    updated_ids->insert(updated_ids->begin(), updated_displays.begin(),
+                        updated_displays.end());
+  }
 }
 
 // static
 bool DisplayLayout::Validate(const DisplayIdList& list,
                              const DisplayLayout& layout) {
   // The primary display should be in the list.
   DCHECK(IsIdInList(layout.primary_id, list));
 
   // Unified mode, or mirror mode switched from unified mode,
   // may not have the placement yet.
@@ skipping 142 matching lines @@
   }
 
   gfx::Insets insets = target_display->GetWorkAreaInsets();
   target_display->set_bounds(
       gfx::Rect(new_target_origin, target_bounds.size()));
   target_display->UpdateWorkAreaFromInsets(insets);
 
   return old_bounds != target_display->bounds();
 }
 
+void DisplayLayout::UpdateOffsets(Displays* display_list) {
+  for (auto& placement : placement_list) {
+    const Display* child_display =
+        FindDisplayById(display_list, placement.display_id);
+    const Display* parent_display =
+        FindDisplayById(display_list, placement.parent_display_id);
+
+    if (!child_display || !parent_display)
+      continue;
+
+    const gfx::Rect& child_bounds = child_display->bounds();
+    const gfx::Rect& parent_bounds = parent_display->bounds();
+
+    if (placement.position == DisplayPlacement::TOP ||
+        placement.position == DisplayPlacement::BOTTOM) {
+      placement.offset = child_bounds.x() - parent_bounds.x();
+    } else {
+      placement.offset = child_bounds.y() - parent_bounds.y();
+    }
+  }
+}
+
 }  // namespace display