Implement NativeWidgetMac::ReorderNativeViews

ui/views/widget/widget_mac_utils.mm

+// 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/views/widget/widget_mac_utils.h"
+
+#import <objc/runtime.h>
+
+#include <vector>
+
+#include "base/mac/foundation_util.h"
+#include "ui/views/cocoa/bridged_content_view.h"
+#include "ui/views/controls/native/native_view_host.h"
+#include "ui/views/widget/widget.h"
+
+namespace views {
+namespace {
+
+using HostedViews = std::vector<std::pair<const views::View*, NSView*>>;
+
+struct EqualToView {
+  EqualToView(const views::View* view) : view_(view) {}
+  bool operator()(const HostedViews::value_type& v) const {
+    return v.first == view_;
+  }
+
+ private:
+  const views::View* view_;
+};
+
+struct EqualToNSView {
+  EqualToNSView(NSView* native_view) : native_view_(native_view) {}
+  bool operator()(const HostedViews::value_type& v) const {
+    return v.second == native_view_;
+  }
+
+ private:
+  NSView* native_view_;
+};
+
+HostedViews GetViewsWithAssociatedNativeViews(const Widget* widget) {
+  HostedViews result;
+  const auto* subviews = [widget->GetNativeView() subviews];
+  for (NSView* child in subviews) {
+    NSValue* value = objc_getAssociatedObject(child, &kAssociatedViewHostKey);
+    if (value)
+      result.emplace_back(static_cast<const views::View*>(value.pointerValue),
+                          child);
+  }
+  return result;
+}
+
+HostedViews::iterator SortViewsList(const views::View* view,
+                                    HostedViews::iterator begin,
+                                    HostedViews::iterator end) {
+  auto it = std::find_if(begin, end, EqualToView(view));
+  if (it != end) {
+    std::swap(*begin, *it);
+    ++begin;
+  }
+  for (int i = 0; i < view->child_count(); ++i)
+    begin = SortViewsList(view->child_at(i), begin, end);
+  return begin;
+}
+
+NSComparisonResult SubviewSorter(id lhs, id rhs, void* hosts_as_void) {
+  DCHECK_NE(lhs, rhs);
+
+  const HostedViews* hosts = static_cast<const HostedViews*>(hosts_as_void);
+  auto left_it = std::find_if(hosts->begin(), hosts->end(), EqualToNSView(lhs));

[tapted, 2016/03/15 22:54:53]

This call is O(n) so it makes the sorting algorithm O(n*n*log(n)); My suggestion
to first collect the "rank" as an integer would keep the algorithm at
O(n*log(n)*log(n))  (or just O(n*log(n)) if a hashmap is used for |rank|). Was
there a reason you didn't like that idea? (I think also neater/easier to read
than using find_if and the extra functors.).

Comparator functions typically need to scale well - the shouldn't take time
proportional to the number of things being sorted. But I guess there also aren't
expected to be particularly many associated views in a particular widget. If we
are assuming that we can comment here that this makes the comparator slow, but
it shouldn't matter.

[kirr, 2016/03/16 09:16:34]

I used vector of pairs as one container for all (against associative map + views
order map); because it just looks simpler for me.
Also it allows to check if views is already in correct order (hosts !=
sorted_hosts).
But there is not a big difference. So I'll use a map if you want.

BTW
I've checked the performance with clang.
Small vector is faster without optimizations and with -O2. Map is faster with
-O1.
https://gist.github.com/kirr/9480fc2e4836f27fd814

[kirr, 2016/03/16 21:43:45]

Done.

+  auto right_it =
+      std::find_if(hosts->begin(), hosts->end(), EqualToNSView(rhs));
+  bool left_found = left_it != hosts->end();
+  bool right_found = right_it != hosts->end();
+
+  // Sort unassociated views below associated views.
+  if (left_found != right_found) {

[tapted, 2016/03/15 22:54:53]

nit: doesn't need curlies

[kirr, 2016/03/16 21:43:45]

Done.

+    return left_found ? NSOrderedDescending : NSOrderedAscending;
+  }
+
+  if (left_found)

[tapted, 2016/03/15 22:54:53]

nit: needs curlies

[kirr, 2016/03/16 21:43:45]

Done.

+    return std::distance(hosts->begin(), left_it) <
+                   std::distance(hosts->begin(), right_it)
+               ? NSOrderedAscending
+               : NSOrderedDescending;
+
+  // If both are unassociated, consider that order is not important
+  return NSOrderedSame;
+}
+
+}  // namespace
+
+int kAssociatedViewHostKey;
+
+void AttachNSViewRelatedToHost(NSView* native_view, NativeViewHost* host) {

[tapted, 2016/03/15 22:54:53]

I don't think this function is necessary.

Aura observes the kViewHostKey being added to the NativeView and then just does
`reorderer_->ReorderChildWindows();`. We can do the same, but without an
observer. (just do `[new_superview addSubview:native_view];` and call
ReorderChildNSViews)

In fact I'd go with something like


void ReparentNSView(NSView* native_view, NativeViewHost* host) {
  DCHECK(native_view);
  // Mac's NativeViewHost has no support for hosting its own child widgets.
  // This check is probably overly restrictive, since the Widget containing the
  // NativeViewHost _is_ allowed child Widgets. However, we don't know yet
  // whether those child Widgets need to be distinguished from Widgets that code
  // might want to associate with the hosted NSView instead.
  {
    Widget::Widgets child_widgets;
    Widget::GetAllChildWidgets(native_view, &child_widgets);
    CHECK_GE(1u, child_widgets.size());  // 1 (itself) or 0 if detached.
  }

  if (!host) {
    BridgedContentView* old_superview =
        base::mac::ObjCCastStrict<BridgedContentView>(
            [native_view superview]);
    DCHECK(old_superview);
    [old_superview clearAssociationForView:host];
    return;
  }

  BridgedContentView* new_superview =
      base::mac::ObjCCastStrict<BridgedContentView>(
          new_parent->GetNativeView());
  DCHECK(new_superview);
  [new_superview setAssociationForView:host toNativeView:native_view];
}


Then in @implementation BridgedContentView (after adding a std::map<View*,
NSView*> associated_views member)

- (void)setAssociationForView:(views::View*)view
    toNativeView(NSView*)native_view {
  DCHECK_EQ(0u, associated_views.count(view));
  [self addSubview:native_view];
  associated_views[view] = native_view;
  hostedView_->GetWidget()->ReorderNativeViews();
}

- (void)clearAssociatedView:(views::View*)view {
  auto it = associated_views.find(view);
  DCHECK(it != associated_views.end());
  [it->second removeFromSuperview]
  associated_views.erase(it);
}

[kirr, 2016/03/16 21:43:45]

Done.

+  Widget* new_parent = host->GetWidget();
+  HostedViews hosts = GetViewsWithAssociatedNativeViews(new_parent);
+  hosts.emplace_back(host, native_view);
+  SortViewsList(new_parent->GetRootView(), hosts.begin(), hosts.end());
+
+  BridgedContentView* new_superview =
+      base::mac::ObjCCastStrict<BridgedContentView>(
+          new_parent->GetNativeView());
+  DCHECK(new_superview);
+
+  auto it = std::find_if(hosts.begin(), hosts.end(), EqualToView(host));
+  if (it == hosts.end() || (it + 1) == hosts.end()) {
+    [new_superview addSubview:native_view];
+  } else {
+    NSView* view_above = (it + 1)->second;
+    [new_superview addSubview:native_view
+                   positioned:NSWindowBelow
+                   relativeTo:view_above];
+  }
+}
+
+void ReorderChildNSViews(Widget* widget) {
+  HostedViews hosts = GetViewsWithAssociatedNativeViews(widget);
+  HostedViews sorted_hosts = hosts;
+  SortViewsList(widget->GetRootView(), sorted_hosts.begin(),
+                sorted_hosts.end());
+
+  if (hosts != sorted_hosts)

[tapted, 2016/03/15 22:54:53]

nit: need curlies

(policy is if the body is multi lines [including comments] then it must have
curlies. If the body is one line, curlies are optional [generally preferred
not]. Note the lines that the _condition_ takes up isn't a factor -- you can
have a multi-line `if (..)` condition without curlies)

[kirr, 2016/03/16 21:43:45]

Done. Thanks.

+    [widget->GetNativeView() sortSubviewsUsingFunction:&SubviewSorter

[tapted, 2016/03/15 22:54:53]

If we are worried about using this function in particular, you can do

NSView* superview = [widget->GetNativeView() subviews]
NSArray new_subviews = [superview sortedArrayUsingFunction:.. context:..];
[superview setSubviews:new_subviews];

But they should really be amounting to the same thing in AppKit.


However, there is also 

sortedArrayWithOptions:usingComparator:

which we get access to on NSArray - that would allow us to pass NSSortStable so
that the unassociated NSViews that compare as NSOrderedSame do not get
reordered. (We may actually need that.. but if it adds complexity we should wait
until there is a need)

[kirr, 2016/03/16 21:43:45]

Seems like it's better not worry about it until we have no case.

+                                               context:&sorted_hosts];
+}
+
+}  // namespace views