[go: nahoru, domu]
Google Git
Sign in
chromium / chromium / src / 75f4152e5cde392fdb1519fdebc34faed74e3e12 / . / ui / display / unified_desktop_utils.cc
blob: 6a0da75f1271475414295bfcf3d914a8269778b5 [file] [log] [blame]
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]1// Copyright 2017 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "ui/display/unified_desktop_utils.h"
6
7#include <map>
8#include <set>
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]9
Brett Wilson1f07f20e2017-10-02 18:55:28[diff] [blame]10#include "base/containers/stack.h"
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]11#include "base/logging.h"
12#include "base/stl_util.h"
13#include "ui/display/types/display_constants.h"
14
15namespace display {
16
17namespace {
18
19// Defines a row and column indices of a cell in the layout matrix.
20struct Cell {
21 int row;
22 int column;
23
24 Cell(int r, int c) : row(r), column(c) {}
25};
26
27// Validates that the display placements defines a graph where there is a path
28// from each display to the primary display (root) and there are no cycles or
29// unparented displays.
30using DisplayChildToParentMap = std::map<int64_t, int64_t>;
31bool ValidateDisplayGraph(const DisplayChildToParentMap& child_to_parent,
32 int64_t primary_id) {
33 for (const auto& iter : child_to_parent) {
34 int64_t current_id = iter.first;
35 if (current_id == primary_id) {
36 // The primary display should not have a parent, and shouldn't exist in
37 // the map as a key. That's a potential cycle.
38 LOG(ERROR) << "Primary display must not have a parent.";
39 return false;
40 }
41
42 std::set<int64_t> visited_ids;
43 while (current_id != primary_id) {
44 if (!visited_ids.emplace(current_id).second) {
45 LOG(ERROR) << "A cycle exists at display ID: " << current_id;
46 return false;
47 }
48
49 const auto parent_iter = child_to_parent.find(current_id);
50 if (parent_iter == child_to_parent.end()) {
51 LOG(ERROR) << "Display ID: " << current_id << " has no parent.";
52 return false;
53 }
54
55 current_id = parent_iter->second;
56 }
57 }
58
59 return true;
60}
61
62// Builds and returns the Unified Desktop layout matrix given the display
63// |layout|. This function must only be called on an already-validated |layout|.
64// Returns an empty matrix if an error occurs.
65UnifiedDesktopLayoutMatrix BuildDisplayMatrix(const DisplayLayout& layout) {
66 // Maps a display ID to its Cell position in the matrix.
67 std::map<int64_t, Cell> displays_cells;
68 // The root primary display is at (0, 0).
69 displays_cells.emplace(layout.primary_id, Cell(0, 0));
70
71 // After we finish building the Cells, we might have some displays
72 // positioned at negative cell coordinates (relative to the root primary
73 // display). We need to normalize our Cells so that the least row and column
74 // indices are zeros.
75 // Calculate the min/max row and column indices.
76 int max_row = 0;
77 int max_column = 0;
78 int min_row = 0;
79 int min_column = 0;
80
81 // Calculate the Cell positions of all displays in the placement list.
82 for (const auto& placement : layout.placement_list) {
83 int64_t current_display_id = placement.display_id;
Brett Wilson1f07f20e2017-10-02 18:55:28[diff] [blame]84 base::stack<DisplayPlacement> unhandled_displays;
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]85 while (displays_cells.count(current_display_id) == 0) {
Ahmed Fakhry4ce143c2017-11-06 23:42:38[diff] [blame]86 auto placement_iter = std::find_if(
87 layout.placement_list.begin(), layout.placement_list.end(),
88 [current_display_id](const DisplayPlacement& p) {
89 return p.display_id == current_display_id;
90 });
91 DCHECK(placement_iter != layout.placement_list.end());
92 unhandled_displays.emplace(*placement_iter);
93 current_display_id = placement_iter->parent_display_id;
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]94 }
95
96 // For each unhandled display, find its parent's cell, and use it to deduce
97 // its own cell.
98 while (!unhandled_displays.empty()) {
99 const DisplayPlacement current_placement = unhandled_displays.top();
100 unhandled_displays.pop();
101 const Cell& parent_cell =
102 displays_cells.at(current_placement.parent_display_id);
103 std::map<int64_t, Cell>::iterator new_cell_itr;
104 switch (current_placement.position) {
105 case DisplayPlacement::TOP:
106 // Top of its parent. Go up a row (row - 1).
107 new_cell_itr =
108 displays_cells
109 .emplace(current_placement.display_id,
110 Cell(parent_cell.row - 1, parent_cell.column))
111 .first;
112 break;
113
114 case DisplayPlacement::RIGHT:
115 // Right of its parent. Go right a column (column + 1).
116 new_cell_itr =
117 displays_cells
118 .emplace(current_placement.display_id,
119 Cell(parent_cell.row, parent_cell.column + 1))
120 .first;
121 break;
122
123 case DisplayPlacement::BOTTOM:
124 // Bottom of its parent. Go down a row (row + 1).
125 new_cell_itr =
126 displays_cells
127 .emplace(current_placement.display_id,
128 Cell(parent_cell.row + 1, parent_cell.column))
129 .first;
130 break;
131
132 case DisplayPlacement::LEFT:
133 // Left of its parent. Go left a column (column - 1).
134 new_cell_itr =
135 displays_cells
136 .emplace(current_placement.display_id,
137 Cell(parent_cell.row, parent_cell.column - 1))
138 .first;
139 break;
140 }
141
142 const Cell& cell = new_cell_itr->second;
143 max_row = std::max(max_row, cell.row);
144 max_column = std::max(max_column, cell.column);
145 min_row = std::min(min_row, cell.row);
146 min_column = std::min(min_column, cell.column);
147 }
148 }
149
150 // Now build the matrix.
151 UnifiedDesktopLayoutMatrix matrix;
152 const size_t num_rows = max_row - min_row + 1;
153 const size_t num_columns = max_column - min_column + 1;
154
155 if (displays_cells.size() != num_rows * num_columns) {
156 LOG(ERROR) << "Unified Desktop layout matrix has wrong dimentions";
157 // Return an empty matrix, ValidateMatrix() will catch it as invalid.
158 return matrix;
159 }
160
161 matrix.resize(num_rows);
162 for (auto& matrix_row : matrix)
163 matrix_row.resize(num_columns, display::kInvalidDisplayId);
164
165 for (const auto& iter : displays_cells) {
166 const Cell& cell = iter.second;
167 const int row_index = cell.row - min_row;
168 const int column_index = cell.column - min_column;
169 matrix[row_index][column_index] = iter.first;
170 }
171
172 return matrix;
173}
174
Ahmed Fakhry4f8e3722017-10-31 21:01:58[diff] [blame]175} // namespace
176
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]177bool ValidateMatrix(const UnifiedDesktopLayoutMatrix& matrix) {
178 if (matrix.empty())
179 return false;
180
Ahmed Fakhry4f8e3722017-10-31 21:01:58[diff] [blame]181 const size_t column_count = matrix[0].size();
182 if (column_count == 0)
183 return false;
184
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]185 for (const auto& row : matrix) {
Ahmed Fakhry4f8e3722017-10-31 21:01:58[diff] [blame]186 if (row.size() != column_count) {
187 LOG(ERROR) << "Wrong matrix dimensions. Unequal rows sizes.";
188 return false;
189 }
190
191 // No holes or repeated IDs are allowed.
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]192 for (const auto& id : row) {
193 if (id == display::kInvalidDisplayId) {
194 LOG(ERROR) << "Unified Desktop layout matrix has an empty cell in it.";
195 return false;
196 }
197 }
198 }
199
200 return true;
201}
202
Ahmed Fakhryace707692017-09-21 19:40:09[diff] [blame]203bool BuildUnifiedDesktopMatrix(const DisplayIdList& ids_list,
204 const DisplayLayout& layout,
205 UnifiedDesktopLayoutMatrix* out_matrix) {
206 // The primary display should be in the IDs list.
207 if (!base::ContainsValue(ids_list, layout.primary_id)) {
208 LOG(ERROR) << "The primary ID: " << layout.primary_id
209 << " is not in the IDs list.";
210 return false;
211 }
212
213 // Each ID in |ids_list| must have a placement in the layout except the
214 // primary display.
215 for (const auto& id : ids_list) {
216 if (id == layout.primary_id)
217 continue;
218 const auto iter =
219 std::find_if(layout.placement_list.begin(), layout.placement_list.end(),
220 [id](const DisplayPlacement& placement) {
221 return placement.display_id == id;
222 });
223 if (iter == layout.placement_list.end()) {
224 LOG(ERROR) << "Display with ID: " << id << " has no placement.";
225 return false;
226 }
227 }
228
229 if (layout.placement_list.empty()) {
230 LOG(ERROR) << "Placement list is empty.";
231 return false;
232 }
233
234 // This map is used to validate that each display has no more than one child
235 // on eithr of its sides.
236 std::map<int64_t, std::set<DisplayPlacement::Position>> displays_filled_sides;
237
238 // This map is used to validate that all displays has a path to the primary
239 // (root) display with no cycles.
240 DisplayChildToParentMap child_to_parent;
241
242 bool has_primary_as_parent = false;
243 for (const auto& placement : layout.placement_list) {
244 // Unified mode placements are not allowed to have offsets.
245 if (placement.offset != 0) {
246 LOG(ERROR) << "Unified mode placements are not allowed to have offsets.";
247 return false;
248 }
249
250 if (placement.display_id == kInvalidDisplayId) {
251 LOG(ERROR) << "display_id is not initialized";
252 return false;
253 }
254 if (placement.parent_display_id == kInvalidDisplayId) {
255 LOG(ERROR) << "parent_display_id is not initialized";
256 return false;
257 }
258 if (placement.display_id == placement.parent_display_id) {
259 LOG(ERROR) << "display_id must not be the same as parent_display_id";
260 return false;
261 }
262 if (!base::ContainsValue(ids_list, placement.display_id)) {
263 LOG(ERROR) << "display_id: " << placement.display_id
264 << " is not in the id list: " << placement.ToString();
265 return false;
266 }
267
268 if (!base::ContainsValue(ids_list, placement.parent_display_id)) {
269 LOG(ERROR) << "parent_display_id: " << placement.parent_display_id
270 << " is not in the id list: " << placement.ToString();
271 return false;
272 }
273
274 if (!displays_filled_sides[placement.parent_display_id]
275 .emplace(placement.position)
276 .second) {
277 LOG(ERROR) << "Parent display with ID: " << placement.parent_display_id
278 << " has more than one display on the same side: "
279 << placement.position;
280 return false;
281 }
282
283 if (!child_to_parent
284 .emplace(placement.display_id, placement.parent_display_id)
285 .second) {
286 LOG(ERROR) << "Display ID: " << placement.display_id << " appears more "
287 << "than once in the placement list.";
288 return false;
289 }
290
291 has_primary_as_parent |= layout.primary_id == placement.parent_display_id;
292 }
293
294 if (!has_primary_as_parent) {
295 LOG(ERROR) << "At least, one placement must have the primary as a parent.";
296 return false;
297 }
298
299 if (!ValidateDisplayGraph(child_to_parent, layout.primary_id))
300 return false;
301
302 UnifiedDesktopLayoutMatrix matrix = BuildDisplayMatrix(layout);
303 if (!ValidateMatrix(matrix))
304 return false;
305
306 *out_matrix = matrix;
307 return true;
308}
309
310} // namespace display