1// Copyright 2014 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 "chrome/browser/chromeos/ui/accessibility_focus_ring_controller.h"
6
7#include "ash/display/display_controller.h"
8#include "ash/shell.h"
9#include "base/logging.h"
10#include "chrome/browser/chromeos/ui/focus_ring_layer.h"
11#include "ui/gfx/screen.h"
12
13namespace chromeos {
14
15namespace {
16
17// The number of pixels the focus ring is outset from the object it outlines,
18// which also determines the border radius of the rounded corners.
19// TODO(dmazzoni): take display resolution into account.
20const int kAccessibilityFocusRingMargin = 7;
21
22// Time to transition between one location and the next.
23const int kTransitionTimeMilliseconds = 300;
24
25// A Region is an unordered collection of Rects that maintains its
26// bounding box. Used in the middle of an algorithm that groups
27// adjacent and overlapping rects.
28struct Region {
29  explicit Region(gfx::Rect initial_rect) {
30    bounds = initial_rect;
31    rects.push_back(initial_rect);
32  }
33  gfx::Rect bounds;
34  std::vector<gfx::Rect> rects;
35};
36
37}  // namespace
38
39// static
40AccessibilityFocusRingController*
41    AccessibilityFocusRingController::GetInstance() {
42  return Singleton<AccessibilityFocusRingController>::get();
43}
44
45AccessibilityFocusRingController::AccessibilityFocusRingController()
46    : compositor_(NULL) {
47}
48
49AccessibilityFocusRingController::~AccessibilityFocusRingController() {
50}
51
52void AccessibilityFocusRingController::SetFocusRing(
53    const std::vector<gfx::Rect>& rects) {
54  rects_ = rects;
55  Update();
56}
57
58void AccessibilityFocusRingController::Update() {
59  previous_rings_.swap(rings_);
60  rings_.clear();
61  RectsToRings(rects_, &rings_);
62  layers_.resize(rings_.size());
63  for (size_t i = 0; i < rings_.size(); ++i) {
64    if (!layers_[i])
65      layers_[i].reset(new AccessibilityFocusRingLayer(this));
66
67    if (i > 0) {
68      // Focus rings other than the first one don't animate.
69      layers_[i]->Set(rings_[i]);
70      continue;
71    }
72
73    gfx::Rect bounds = rings_[0].GetBounds();
74    gfx::Display display =
75      gfx::Screen::GetNativeScreen()->GetDisplayMatching(bounds);
76    aura::Window* root_window = ash::Shell::GetInstance()->display_controller()
77        ->GetRootWindowForDisplayId(display.id());
78    ui::Compositor* compositor = root_window->layer()->GetCompositor();
79    if (!compositor || root_window != layers_[0]->root_window()) {
80      layers_[0]->Set(rings_[0]);
81      if (compositor_ && compositor_->HasAnimationObserver(this)) {
82        compositor_->RemoveAnimationObserver(this);
83        compositor_ = NULL;
84      }
85      continue;
86    }
87
88    focus_change_time_ = base::TimeTicks::Now();
89    if (!compositor->HasAnimationObserver(this)) {
90      compositor_ = compositor;
91      compositor_->AddAnimationObserver(this);
92    }
93  }
94}
95
96void AccessibilityFocusRingController::RectsToRings(
97    const std::vector<gfx::Rect>& src_rects,
98    std::vector<AccessibilityFocusRing>* rings) const {
99  if (src_rects.empty())
100    return;
101
102  // Give all of the rects a margin.
103  std::vector<gfx::Rect> rects;
104  rects.resize(src_rects.size());
105  for (size_t i = 0; i < src_rects.size(); ++i) {
106    rects[i] = src_rects[i];
107    rects[i].Inset(-GetMargin(), -GetMargin());
108  }
109
110  // Split the rects into contiguous regions.
111  std::vector<Region> regions;
112  regions.push_back(Region(rects[0]));
113  for (size_t i = 1; i < rects.size(); ++i) {
114    bool found = false;
115    for (size_t j = 0; j < regions.size(); ++j) {
116      if (Intersects(rects[i], regions[j].bounds)) {
117        regions[j].rects.push_back(rects[i]);
118        regions[j].bounds.Union(rects[i]);
119        found = true;
120      }
121    }
122    if (!found) {
123      regions.push_back(Region(rects[i]));
124    }
125  }
126
127  // Keep merging regions that intersect.
128  // TODO(dmazzoni): reduce the worst-case complexity! This appears like
129  // it could be O(n^3), make sure it's not in practice.
130  bool merged;
131  do {
132    merged = false;
133    for (size_t i = 0; i < regions.size() - 1 && !merged; ++i) {
134      for (size_t j = i + 1; j < regions.size() && !merged; ++j) {
135        if (Intersects(regions[i].bounds, regions[j].bounds)) {
136          regions[i].rects.insert(regions[i].rects.end(),
137                                  regions[j].rects.begin(),
138                                  regions[j].rects.end());
139          regions[i].bounds.Union(regions[j].bounds);
140          regions.erase(regions.begin() + j);
141          merged = true;
142        }
143      }
144    }
145  } while (merged);
146
147  for (size_t i = 0; i < regions.size(); ++i) {
148    std::sort(regions[i].rects.begin(), regions[i].rects.end());
149    rings->push_back(RingFromSortedRects(regions[i].rects));
150  }
151}
152
153int AccessibilityFocusRingController::GetMargin() const {
154  return kAccessibilityFocusRingMargin;
155}
156
157// Given a vector of rects that all overlap, already sorted from top to bottom
158// and left to right, split them into three shapes covering the top, middle,
159// and bottom of a "paragraph shape".
160//
161// Input:
162//
163//                       +---+---+
164//                       | 1 | 2 |
165// +---------------------+---+---+
166// |             3               |
167// +--------+---------------+----+
168// |    4   |         5     |
169// +--------+---------------+--+
170// |             6             |
171// +---------+-----------------+
172// |    7    |
173// +---------+
174//
175// Output:
176//
177//                       +-------+
178//                       |  Top  |
179// +---------------------+-------+
180// |                             |
181// |                             |
182// |           Middle            |
183// |                             |
184// |                             |
185// +---------+-------------------+
186// | Bottom  |
187// +---------+
188//
189// When there's no clear "top" or "bottom" segment, split the overall rect
190// evenly so that some of the area still fits into the "top" and "bottom"
191// segments.
192void AccessibilityFocusRingController::SplitIntoParagraphShape(
193    const std::vector<gfx::Rect>& rects,
194    gfx::Rect* top,
195    gfx::Rect* middle,
196    gfx::Rect* bottom) const {
197  size_t n = rects.size();
198
199  // Figure out how many rects belong in the top portion.
200  gfx::Rect top_rect = rects[0];
201  int top_middle = (top_rect.y() + top_rect.bottom()) / 2;
202  size_t top_count = 1;
203  while (top_count < n && rects[top_count].y() < top_middle) {
204    top_rect.Union(rects[top_count]);
205    top_middle = (top_rect.y() + top_rect.bottom()) / 2;
206    top_count++;
207  }
208
209  // Figure out how many rects belong in the bottom portion.
210  gfx::Rect bottom_rect = rects[n - 1];
211  int bottom_middle = (bottom_rect.y() + bottom_rect.bottom()) / 2;
212  size_t bottom_count = std::min(static_cast<size_t>(1), n - top_count);
213  while (bottom_count + top_count < n &&
214         rects[n - bottom_count - 1].bottom() > bottom_middle) {
215    bottom_rect.Union(rects[n - bottom_count - 1]);
216    bottom_middle = (bottom_rect.y() + bottom_rect.bottom()) / 2;
217    bottom_count++;
218  }
219
220  // Whatever's left goes to the middle rect, but if there's no middle or
221  // bottom rect, split the existing rects evenly to make one.
222  gfx::Rect middle_rect;
223  if (top_count + bottom_count < n) {
224    middle_rect = rects[top_count];
225    for (size_t i = top_count + 1; i < n - bottom_count; i++)
226      middle_rect.Union(rects[i]);
227  } else if (bottom_count > 0) {
228    gfx::Rect enclosing_rect = top_rect;
229    enclosing_rect.Union(bottom_rect);
230    int middle_top = (top_rect.y() + top_rect.bottom() * 2) / 3;
231    int middle_bottom = (bottom_rect.y() * 2 + bottom_rect.bottom()) / 3;
232    top_rect.set_height(middle_top - top_rect.y());
233    bottom_rect.set_height(bottom_rect.bottom() - middle_bottom);
234    bottom_rect.set_y(middle_bottom);
235    middle_rect = gfx::Rect(enclosing_rect.x(), middle_top,
236                            enclosing_rect.width(), middle_bottom - middle_top);
237  } else {
238    int middle_top = (top_rect.y() * 2 + top_rect.bottom()) / 3;
239    int middle_bottom = (top_rect.y() + top_rect.bottom() * 2) / 3;
240    middle_rect = gfx::Rect(top_rect.x(), middle_top,
241                            top_rect.width(), middle_bottom - middle_top);
242    bottom_rect = gfx::Rect(
243        top_rect.x(), middle_bottom,
244        top_rect.width(), top_rect.bottom() - middle_bottom);
245    top_rect.set_height(middle_top - top_rect.y());
246  }
247
248  if (middle_rect.y() > top_rect.bottom()) {
249    middle_rect.set_height(
250        middle_rect.height() + middle_rect.y() - top_rect.bottom());
251    middle_rect.set_y(top_rect.bottom());
252  }
253
254  if (middle_rect.bottom() < bottom_rect.y()) {
255    middle_rect.set_height(bottom_rect.y() - middle_rect.y());
256  }
257
258  *top = top_rect;
259  *middle = middle_rect;
260  *bottom = bottom_rect;
261}
262
263AccessibilityFocusRing AccessibilityFocusRingController::RingFromSortedRects(
264    const std::vector<gfx::Rect>& rects) const {
265  if (rects.size() == 1)
266    return AccessibilityFocusRing::CreateWithRect(rects[0], GetMargin());
267
268  gfx::Rect top;
269  gfx::Rect middle;
270  gfx::Rect bottom;
271  SplitIntoParagraphShape(rects, &top, &middle, &bottom);
272
273  return AccessibilityFocusRing::CreateWithParagraphShape(
274      top, middle, bottom, GetMargin());
275}
276
277bool AccessibilityFocusRingController::Intersects(
278  const gfx::Rect& r1, const gfx::Rect& r2) const {
279  int slop = GetMargin();
280  return (r2.x() <= r1.right() + slop &&
281          r2.right() >= r1.x() - slop &&
282          r2.y() <= r1.bottom() + slop &&
283          r2.bottom() >= r1.y() - slop);
284}
285
286void AccessibilityFocusRingController::OnDeviceScaleFactorChanged() {
287  Update();
288}
289
290void AccessibilityFocusRingController::OnAnimationStep(
291    base::TimeTicks timestamp) {
292  if (rings_.empty())
293    return;
294
295  CHECK(compositor_);
296  CHECK(!rings_.empty());
297  CHECK(!layers_.empty());
298  CHECK(layers_[0]);
299
300  // It's quite possible for the first 1 or 2 animation frames to be
301  // for a timestamp that's earlier than the time we received the
302  // focus change, so we just treat those as a delta of zero.
303  if (timestamp < focus_change_time_)
304    timestamp = focus_change_time_;
305
306  base::TimeDelta delta = timestamp - focus_change_time_;
307  base::TimeDelta transition_time =
308      base::TimeDelta::FromMilliseconds(kTransitionTimeMilliseconds);
309  if (delta >= transition_time) {
310    layers_[0]->Set(rings_[0]);
311    compositor_->RemoveAnimationObserver(this);
312    compositor_ = NULL;
313    return;
314  }
315
316  double fraction = delta.InSecondsF() / transition_time.InSecondsF();
317
318  // Ease-in effect.
319  fraction = pow(fraction, 0.3);
320
321  layers_[0]->Set(AccessibilityFocusRing::Interpolate(
322      previous_rings_[0], rings_[0], fraction));
323}
324
325}  // namespace chromeos
326