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();
 }
 
+// Extracts the displays IDs list from the displays list.
+DisplayIdList DisplayListToDisplayIdList(const Displays& displays) {
+  DisplayIdList list;
+  for (const auto& display : displays)
+    list.emplace_back(display.id());
+
+  return list;
+}
+
+// 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);
+}
+
+// Returns the tree depth of the display with ID |display_id| from the tree root
+// (i.e. from the primary display).
+int GetDisplayTreeDepth(
+    int64_t display_id,
+    int64_t primary_id,
+    const std::map<int64_t, int64_t>& display_to_parent_ids_map) {
+  if (display_id == primary_id)
+    return 0;
+
+  int64_t current_id = display_id;
+  int depth = 0;
+  while (display_to_parent_ids_map.count(current_id)) {
+    ++depth;
+    int64_t parent_id = display_to_parent_ids_map.at(current_id);
+    if (parent_id == primary_id)
+      break;
+    current_id = parent_id;
+  }
+
+  return depth;
+}
+
+// Returns true if the child and parent displays are sharing a border that
+// matches the child's relative position to its parent.
+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();
+
+  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;
+}
+
+// After the layout has been applied to the |display_list| and any possible
+// overlaps have been fixed, this function is called to update the offsets in
+// the |placement_list|.
+void UpdateOffsets(Displays* display_list,
+                   std::vector<DisplayPlacement>* placement_list) {
+  for (DisplayPlacement& 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();
+    }
+  }
+}
+
+// Fixes any overlapping displays and repared displays if necessary.
+void DeIntersectDisplays(int64_t primary_id,
+                         Displays* display_list,
+                         std::vector<DisplayPlacement>* placement_list,
+                         std::set<int64_t>* updated_displays) {
+  std::map<int64_t, int64_t> display_to_parent_ids_map;
+  for (const DisplayPlacement& placement : *placement_list) {
+    display_to_parent_ids_map[placement.display_id] =
+        placement.parent_display_id;
+  }
+
+  std::vector<Display*> sorted_displays;
+  for (Display& display : *display_list)
+    sorted_displays.push_back(&display);
+
+  // Sort the displays first by their depth in the display hierarchy tree, and
+  // then by distance of their top left points from the origin. This way we
+  // process the displays starting at the root (the primary display), in the
+  // order of their decendence spanning out from the primary display.
+  std::sort(sorted_displays.begin(), sorted_displays.end(), [&](Display* d1,
+                                                                Display* d2) {
+    const int d1_depth =
+        GetDisplayTreeDepth(d1->id(), primary_id, display_to_parent_ids_map);
+    const int d2_depth =
+        GetDisplayTreeDepth(d2->id(), primary_id, display_to_parent_ids_map);
+
+    if (d1_depth != d2_depth)
+      return d1_depth < d2_depth;
+
+    return d1->bounds().OffsetFromOrigin().LengthSquared() <
+           d2->bounds().OffsetFromOrigin().LengthSquared();
+  });
+  // This must result in the primary display being at the front of the list.
+  DCHECK_EQ(sorted_displays.front()->id(), primary_id);
+
+  for (size_t i = 1; i < sorted_displays.size(); ++i) {

[afakhry, 2017/01/30 22:25:57]

Actually I need to use int here. I need to be able to compare j >= 0 without
compiler warnings, in other words, I need j to be signed.

[oshima, 2017/01/31 16:55:43]

ok. You can actually iterate back on sorted_displays, but I'll leave it to you.

+    Display* target_display = sorted_displays[i];
+    const Display* last_intersecting_source_display = nullptr;
+    int last_offset_x = 0;
+    int last_offset_y = 0;
+    for (int j = i - 1; j >= 0; --j) {
+      const Display* source_display = sorted_displays[j];
+      const gfx::Rect source_bounds = source_display->bounds();
+      const gfx::Rect target_bounds = target_display->bounds();
+
+      gfx::Rect intersection = source_bounds;
+      intersection.Intersect(target_bounds);
+
+      if (intersection.IsEmpty())
+        continue;
+
+      // Calculate offsets along both X and Y axes such that either can remove
+      // the overlap, but choose and apply the smaller offset. This way we have
+      // a more predictable results.
+      int offset_x = 0;
+      int offset_y = 0;
+      if (intersection.width()) {
+        if (target_bounds.x() >= 0) {
+          // Target display moves along the +ve X direction.
+          offset_x = source_bounds.right() - target_bounds.x();
+        } else {
+          // Target display moves along the -ve X direction.
+          offset_x = -(target_bounds.right() - source_bounds.x());
+        }
+      }
+
+      if (intersection.height()) {
+        if (target_bounds.y() >= 0) {
+          // Target display moves along the +ve Y direction.
+          offset_y = source_bounds.bottom() - target_bounds.y();
+        } else {
+          // Target display moves along the -ve Y direction.
+          offset_y = -(target_bounds.bottom() - source_bounds.y());
+        }
+      }
+
+      if (offset_x == 0 && offset_y == 0)
+        continue;
+
+      // Choose the smaller offset.
+      if (std::abs(offset_x) <= std::abs(offset_y))
+        offset_y = 0;
+      else
+        offset_x = 0;
+
+      gfx::Point new_origin = target_bounds.origin();
+      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());

[oshima, 2017/01/30 20:30:43]

this can add the target display more than once if it overlaps more than one
source displays. can you include this scenario in the unit test?

[afakhry, 2017/01/30 22:25:57]

This shouldn't be a problem since I already changed |updated_displays| from a
vector to a set to avoid this case.

+
+      // The most recent performed de-intersection data.
+      last_intersecting_source_display = source_display;
+      last_offset_x = offset_x;
+      last_offset_y = offset_y;
+    }
+
+    if (!last_intersecting_source_display)
+      continue;
+
+    // A de-intersection was performed.
+    // The offset target display may have moved such that it no longer touches
+    // its parent. Reparent if necessary.
+    const int64_t parent_display_id =
+        display_to_parent_ids_map.at(target_display->id());
+    if (parent_display_id == last_intersecting_source_display->id()) {
+      // It was just de-intersected with the source display in such a way that
+      // they're touching, and the source display is its parent. So no need to
+      // do any reparenting.
+      continue;
+    }
+
+    Display* parent_display =
+        FindDisplayById(display_list, parent_display_id);
+    DCHECK(parent_display);
+
+    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();
+                     });
+    DCHECK(target_display_placement_itr != placement_list->end());
+    DisplayPlacement& target_display_placement =
+        *target_display_placement_itr;
+    if (AreDisplaysTouching(*target_display, *parent_display,
+                            target_display_placement.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.parent_display_id =
+        last_intersecting_source_display->id();
+    if (last_offset_x) {
+      target_display_placement.position =
+          last_offset_x > 0 ? DisplayPlacement::RIGHT : DisplayPlacement::LEFT;
+    } else {
+      target_display_placement.position =
+          last_offset_y > 0 ? DisplayPlacement::BOTTOM : DisplayPlacement::TOP;
+    }

[oshima, 2017/01/30 20:30:43]

refactor "reparent" part to a method?

[afakhry, 2017/01/30 22:25:57]

Done.

+  }
+
+  // The offsets might have changed and we must update them.
+  UpdateOffsets(display_list, placement_list);
 }
 
 }  // 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) {
+  if (placement_list.empty())
+    return;
+
+  if (!DisplayLayout::Validate(DisplayListToDisplayIdList(*display_list),
+                               *this)) {
+    // Prevent invalid and non-relevant display layouts.
+    return;
+  }
+
   // 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);
+
+  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));
+  if (!IsIdInList(layout.primary_id, list)) {
+    LOG(ERROR) << "The primary id: " << layout.primary_id
+               << " is not in the id list.";
+    return false;
+  }
 
   // Unified mode, or mirror mode switched from unified mode,
   // may not have the placement yet.
   if (layout.placement_list.size() == 0u)
     return true;
 
   bool has_primary_as_parent = false;
   int64_t prev_id = std::numeric_limits<int64_t>::min();
   for (const auto& placement : layout.placement_list) {
     // Placements are sorted by display_id.
@@ skipping 136 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();
 }
 
 }  // namespace display