X11: Add window cache

ui/base/x/x11_window_cache.cc

Index: ui/base/x/x11_window_cache.cc
diff --git a/ui/base/x/x11_window_cache.cc b/ui/base/x/x11_window_cache.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ee3577e3178055f01e2c5cec19bb03c9e4949091
--- /dev/null
+++ b/ui/base/x/x11_window_cache.cc
@@ -0,0 +1,731 @@
+// 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/base/x/x11_window_cache.h"
+
+#include <X11/Xlib.h>
+#include <X11/Xlib-xcb.h>
+#include <xcb/xcbext.h>
+
+#include <algorithm>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include "base/logging.h"
+#include "ui/base/x/x11_window_event_manager.h"
+#include "ui/events/platform/platform_event_source.h"
+#include "ui/events/platform/x11/x11_event_source.h"
+
+namespace ui {
+
+namespace {
+
+using ChildIterator = XWindowCache::Window::Children::iterator;
+
+const char kNetWmIcon[] = "_NET_WM_ICON";
+
+// In case a property's value is huge, only cache the first 64KiB, and
+// indicate in Property that the cached value is not the entire value.
+static constexpr auto kMaxPropertySize = 0xffff;
+
+}  // anonymous namespace
+
+// static
+template <typename T>
+void XWindowCache::CacheWindowGeometryFromResponse(XWindowCache::Window* window,
+                                                   const T& response) {
+  window->x_ = response.x;
+  window->y_ = response.y;
+  window->width_ = response.width;
+  window->height_ = response.height;
+  window->border_width_ = response.border_width;
+}
+
+// static
+auto XWindowCache::FindChild(XWindowCache::Window* parent,
+                             xcb_window_t child_id)
+    -> decltype(parent->children_.begin()) {
+  return std::find_if(parent->children_.begin(), parent->children_.end(),
+                      [child_id](std::unique_ptr<XWindowCache::Window>& child) {
+                        return child->id() == child_id;
+                      });
+}
+
+struct XWindowCache::GetWindowAttributesRequest
+    : public X11EventSource::Request {
+  GetWindowAttributesRequest(Window* window, XWindowCache* cache)
+      : Request(xcb_get_window_attributes(cache->connection_, window->id())
+                    .sequence),
+        cache_(cache),
+        window_(window) {
+    window_->attributes_request_ = this;
+  }
+
+  void OnReply(xcb_generic_reply_t* r, xcb_generic_error_t* error) override {
+    if (error) {
+      switch (error->error_code) {
+        case BadDrawable:
+        case BadWindow:
+          break;
+        default:
+          NOTREACHED();
+      }
+      cache_->DestroyWindow(window_);
+      return;
+    }
+    auto* reply = reinterpret_cast<xcb_get_window_attributes_reply_t*>(r);
+
+    window_->attributes_request_ = nullptr;
+    window_->override_redirect_ = reply->override_redirect;
+    window_->is_mapped_ = reply->map_state != XCB_MAP_STATE_UNMAPPED;
+  }
+
+ protected:
+  XWindowCache* cache_;
+  Window* window_;
+};
+
+struct XWindowCache::GetGeometryRequest : public X11EventSource::Request {
+  GetGeometryRequest(Window* window, XWindowCache* cache)
+      : Request(xcb_get_geometry(cache->connection_, window->id()).sequence),
+        cache_(cache),
+        window_(window) {
+    window_->geometry_request_ = this;
+  }
+
+  void OnReply(xcb_generic_reply_t* r, xcb_generic_error_t* error) override {
+    if (error) {
+      switch (error->error_code) {
+        case BadDrawable:
+          break;
+        default:
+          NOTREACHED();
+      }
+      cache_->DestroyWindow(window_);
+      return;
+    }
+    auto* reply = reinterpret_cast<xcb_get_geometry_reply_t*>(r);
+
+    window_->geometry_request_ = nullptr;
+    CacheWindowGeometryFromResponse(window_, *reply);
+  }
+
+ protected:
+  XWindowCache* cache_;
+  Window* window_;
+};
+
+struct XWindowCache::ListPropertiesRequest : public X11EventSource::Request {
+  ListPropertiesRequest(Window* window, XWindowCache* cache)
+      : Request(xcb_list_properties(cache->connection_, window->id()).sequence),
+        cache_(cache),
+        window_(window) {
+    window_->properties_request_ = this;
+  }
+
+  void OnReply(xcb_generic_reply_t* r, xcb_generic_error_t* error) override {
+    if (error) {
+      switch (error->error_code) {
+        case BadWindow:
+          break;
+        default:
+          NOTREACHED();
+      }
+      cache_->DestroyWindow(window_);
+      return;
+    }
+    auto* reply = reinterpret_cast<xcb_list_properties_reply_t*>(r);
+
+    window_->properties_request_ = nullptr;
+    for (int i = 0; i < xcb_list_properties_atoms_length(reply); i++) {
+      xcb_atom_t atom = xcb_list_properties_atoms(reply)[i];
+      cache_->CacheProperty(window_, atom);
+    }
+  }
+
+ protected:
+  XWindowCache* cache_;
+  Window* window_;
+};
+
+struct XWindowCache::QueryTreeRequest : public X11EventSource::Request {
+  QueryTreeRequest(Window* window, XWindowCache* cache)
+      : Request(xcb_query_tree(cache->connection_, window->id()).sequence),
+        cache_(cache),
+        window_(window) {
+    window_->children_request_ = this;
+  }
+
+  void OnReply(xcb_generic_reply_t* r, xcb_generic_error_t* error) override {
+    if (error) {
+      switch (error->error_code) {
+        case BadWindow:
+          break;
+        default:
+          NOTREACHED();
+      }
+      cache_->DestroyWindow(window_);
+      return;
+    }
+    auto* reply = reinterpret_cast<xcb_query_tree_reply_t*>(r);
+
+    DCHECK(window_->children_.empty());
+
+    xcb_window_t* children = xcb_query_tree_children(reply);
+    int n_children = xcb_query_tree_children_length(reply);
+
+    window_->children_request_ = nullptr;
+
+    // Iterate over children from top-to-bottom.
+    for (int i = 0; i < n_children; i++)
+      cache_->CreateWindow(children[i], window_);
+  }
+
+ protected:
+  XWindowCache* cache_;
+  Window* window_;
+};
+
+struct XWindowCache::GetPropertyRequest : public X11EventSource::Request {
+  GetPropertyRequest(Window* window,
+                     Property* property,
+                     xcb_atom_t atom,
+                     XWindowCache* cache)
+      : Request(xcb_get_property(cache->connection_,
+                                 false,
+                                 window->id(),
+                                 atom,
+                                 XCB_ATOM_ANY,
+                                 0,
+                                 kMaxPropertySize)
+                    .sequence),
+        cache_(cache),
+        window_(window),
+        property_(property),
+        atom_(atom) {
+    property->property_request_ = this;
+  }
+
+  void OnReply(xcb_generic_reply_t* r, xcb_generic_error_t* error) override {
+    if (error) {
+      switch (error->error_code) {
+        case BadWindow:
+          break;
+        case BadValue:
+        case BadAtom:
+        default:
+          NOTREACHED();
+      }
+      // Destruct the |window_| later because clients may still want
+      // its info, but remove the property.
+      window_->properties_.erase(atom_);
+      return;
+    }
+    auto* reply = reinterpret_cast<xcb_get_property_reply_t*>(r);
+
+    if (reply->format == 0) {
+      // According to Xlib, a format of anything other than 8, 16, or
+      // 32 is a BadImplementation error.  However, this occurs when
+      // creating a new xterm window, so just forget about the
+      // property in question.
+      window_->properties_.erase(atom_);
+      return;
+    }
+
+    property_->property_request_ = nullptr;
+    property_->type_ = reply->type;
+    DCHECK(reply->format == 8 || reply->format == 16 || reply->format == 32);
+    property_->format_ = reply->format;
+    property_->length_ = xcb_get_property_value_length(reply);
+    uint32_t data_bytes = property_->length_ * (property_->format_ / 8);
+    property_->data_ = new uint8_t[data_bytes];
+    std::memcpy(property_->data_, xcb_get_property_value(reply), data_bytes);
+  }
+
+ protected:
+  XWindowCache* cache_;
+  Window* window_;
+  Property* property_;
+  xcb_atom_t atom_;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+// XWindowCache
+
+// Xlib shall own the event queue.
+XWindowCache::XWindowCache(XDisplay* display,
+                           X11EventSource* event_source,
+                           XID root)
+    : display_(display),
+      connection_(XGetXCBConnection(display_)),
+      root_id_(root),
+      event_source_(event_source),
+      root_(nullptr),
+      net_wm_icon_(0) {
+  DCHECK(event_source);
+  DCHECK(!xcb_connection_has_error(connection_));
+
+  if (PlatformEventSource::GetInstance())
+    PlatformEventSource::GetInstance()->AddPlatformEventObserver(this);
+
+  net_wm_icon_cookie_ =
+      xcb_intern_atom(connection_, false, sizeof(kNetWmIcon) - 1, kNetWmIcon);
+
+  CreateWindow(root, nullptr);
+}
+
+XWindowCache::~XWindowCache() {
+  if (PlatformEventSource::GetInstance())
+    PlatformEventSource::GetInstance()->RemovePlatformEventObserver(this);
+}
+
+const XWindowCache::Window* XWindowCache::GetWindow(XID id) const {
+  Window* window = GetWindowInternal(id);
+  if (!window) {
+    // The window may not be cached yet, so fall back on a BFS (don't
+    // use a DFS here because we spend less time blocking if we cache
+    // top-down).
+    std::queue<Window*> q;
+    if (root_)
+      q.push(root_.get());
+    while (!q.empty()) {
+      Window* next = q.front();
+      if(next->id() == id) {
+        window = next;
+        break;
+      }
+      q.pop();
+      if (!next->children_request_ ||
+          event_source_->DispatchRequestNow(next->children_request_)) {
+        for (auto& child : next->children_)
+          q.push(child.get());
+      }
+    }
+  }
+  return window && window->Validate() ? window : nullptr;
+}
+
+XWindowCache::Window* XWindowCache::GetWindowInternal(XID id) const {
+  auto it = windows_.find(id);
+  return it == windows_.end() ? nullptr : it->second;
+}
+
+// TODO(thomasanderson): Call ProcessEvent directly from X11EventSource.  Have
+// ProcessEvent return an indication of if it is possible for clients other
+// than XWindowCache to be interested in the event, so that event dispatchers
+// don't get bogged down with the many events that XWindowCache selects.
+void XWindowCache::WillProcessEvent(const PlatformEvent& event) {
+  ProcessEvent(event);
+}
+
+void XWindowCache::DidProcessEvent(const PlatformEvent& event) {}
+
+void XWindowCache::ProcessEvent(const XEvent* e) {
+  switch (e->type) {
+    case PropertyNotify: {
+      Window* window = GetWindowInternal(e->xproperty.window);
+      if (!window)
+        break;
+
+      switch (e->xproperty.state) {
+        case PropertyDelete:
+          window->properties_.erase(e->xproperty.atom);
+          break;
+        case PropertyNewValue:
+          CacheProperty(window, e->xproperty.atom);
+          break;
+        default:
+          NOTREACHED();
+      }
+      break;
+    }
+    case CirculateNotify: {
+      Window* window = GetWindowInternal(e->xcirculate.window);
+      if (!window)
+        break;
+
+      if (e->xcirculate.event == e->xcirculate.window)
+        break;  // This is our root window
+
+      Window* parent = window->parent_;
+      if (parent->id() != e->xcirculate.event)
+        ResetCache();
+
+      auto it = FindChild(parent, window->id());
+      switch (e->xcirculate.place) {
+        case PlaceOnTop:
+          parent->children_.push_front(std::move(*it));
+          break;
+        case PlaceOnBottom:
+          parent->children_.push_back(std::move(*it));
+          break;
+        default:
+          NOTREACHED();
+      }
+      parent->children_.erase(it);
+      break;
+    }
+    case ConfigureNotify: {
+      Window* window = GetWindowInternal(e->xconfigure.window);
+      if (!window)
+        break;
+
+      CacheWindowGeometryFromResponse(window, e->xconfigure);
+
+      if (e->xconfigure.event == e->xconfigure.window)
+        break;
+
+      Window* parent = window->parent_;
+      if (parent->id() != e->xconfigure.event)
+        ResetCache();
+
+      auto it = FindChild(parent, window->id());
+      if (e->xconfigure.above) {
+        auto it_above = FindChild(parent, e->xconfigure.above);
+        if (it == parent->children_.end())
+          ResetCache();
+        else
+          parent->children_.insert(it_above, std::move(*it));
+      } else {
+        // |window| is not above any other sibling window
+        parent->children_.push_back(std::move(*it));
+      }
+      parent->children_.erase(it);
+      break;
+    }
+    case CreateNotify: {
+      Window* parent = GetWindowInternal(e->xcreatewindow.parent);
+      if (!parent)
+        break;
+
+      if (parent->children_request_) {
+        // |parent| is in the process of being cached, so we will pick up this
+        // window in the near future.
+        break;
+      }
+
+      CreateWindow(e->xcreatewindow.window, parent);
+      break;
+    }
+    case DestroyNotify: {
+      Window* window = GetWindowInternal(e->xdestroywindow.window);
+      if (!window)
+        break;
+      DestroyWindow(window);
+      break;
+    }
+    case GravityNotify: {
+      Window* window = GetWindowInternal(e->xgravity.window);
+      if (!window)
+        break;
+
+      window->x_ = e->xgravity.x;
+      window->y_ = e->xgravity.y;
+      break;
+    }
+    case MapNotify: {
+      Window* window = GetWindowInternal(e->xmap.window);
+      if (!window)
+        break;
+
+      window->override_redirect_ = e->xmap.override_redirect;
+      window->is_mapped_ = true;
+      break;
+    }
+    case ReparentNotify: {
+      Window* window = GetWindowInternal(e->xreparent.window);
+      if (!window)
+        break;
+
+      window->x_ = e->xreparent.x;
+      window->y_ = e->xreparent.y;
+
+      window->override_redirect_ = e->xreparent.override_redirect;
+      window->is_mapped_ = false;  // Reparenting a window unmaps it
+
+      Window* old_parent = window->parent_;
+      if (!old_parent)
+        break;  // Don't worry about caching windows above our root.
+
+      Window* new_parent = GetWindowInternal(e->xreparent.parent);
+      if (!new_parent || new_parent->children_request_) {
+        // |window| is either no longer in our tree, or we are already
+        // waiting to receive a list of |new_parent|'s children.  We
+        // conservatively throw away |window| in the second case
+        // because of a race condition where (eg.) |window| gets
+        // reparented to |new_parent| and changes its size before the
+        // server has received our request to select substructure
+        // events on |new_parent|.  We could avoid this by selecting
+        // structure events on |window|, but we need to select
+        // substructure events on all windows anyway to receive
+        // CreateNotify events, and we don't want to 2 duplicate
+        // events every time a window moves or is resized.
+        DestroyWindow(window);
+        break;
+      }
+      window->parent_ = new_parent;
+
+      auto it = FindChild(old_parent, window->id());
+      new_parent->children_.push_front(std::move(*it));
+      old_parent->children_.erase(it);
+      break;
+    }
+    case UnmapNotify: {
+      Window* window = GetWindowInternal(e->xunmap.window);
+      if (!window)
+        break;
+
+      window->is_mapped_ = false;
+      break;
+    }
+    default:
+      break;
+  }
+}
+
+void XWindowCache::ResetCache() {
+  NOTREACHED();
+
+  // On release builds, try to fix our state.
+  ResetCacheImpl();
+}
+
+void XWindowCache::ResetCacheImpl() {
+  // TODO(thomasanderson): Log something in UMA.
+  if (root_) {
+    DestroyWindow(root_.get());
+    DCHECK(windows_.empty());
+    CreateWindow(root_id_, nullptr);
+  }
+}
+
+void XWindowCache::CacheProperty(XWindowCache::Window* window,
+                                 xcb_atom_t atom) {
+  if (!net_wm_icon_ && net_wm_icon_cookie_.sequence) {
+    auto reply =
+        xcb_intern_atom_reply(connection_, net_wm_icon_cookie_, nullptr);
+    if (reply) {
+      net_wm_icon_ = reply->atom;
+      free(reply);
+    }
+    net_wm_icon_cookie_.sequence = 0;
+  }
+  if (atom == net_wm_icon_)
+    return;
+  window->properties_[atom].reset(new Property(atom, window, this));
+}
+
+void XWindowCache::CreateWindow(xcb_window_t id, XWindowCache::Window* parent) {
+  auto it = windows_.find(id);
+  if (it != windows_.end()) {
+    // We're already tracking window |id|.
+    return;
+  }
+
+  Window* window = new Window(id, parent, this);
+  windows_[id] = window;
+  if (parent) {
+    parent->children_.emplace_front(window);
+  } else {
+    DCHECK(!root_);
+    root_.reset(window);
+  }
+}
+
+void XWindowCache::DestroyWindow(Window* window) {
+  DCHECK(window);
+  xcb_window_t id = window->id();
+  if (window->parent_) {
+    auto it = FindChild(window->parent_, window->id());
+    DCHECK(it != window->parent_->children_.end());
+    window->parent_->children_.erase(it);
+  } else {
+    DCHECK_EQ(window, root_.get());
+    root_.reset();
+  }
+  windows_.erase(id);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// XWindowCache::Property
+
+XWindowCache::Property::Property(xcb_atom_t name,
+                                 Window* window,
+                                 XWindowCache* cache)
+    : name_(name), property_request_(nullptr), data_(nullptr), cache_(cache) {
+  cache->event_source_->EnqueueRequest(
+      new GetPropertyRequest(window, this, name, cache));
+  xcb_flush(cache->connection_);
+}
+
+XWindowCache::Property::~Property() {
+  if (property_request_)
+    cache_->event_source_->DiscardRequest(property_request_);
+
+  delete[] data_;
+}
+
+bool XWindowCache::Property::Validate() {
+  return (!property_request_ ||
+          cache_->event_source_->DispatchRequestNow(property_request_));
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// XWindowCache::Window
+
+XWindowCache::Window::Window(xcb_window_t id,
+                             XWindowCache::Window* parent,
+                             XWindowCache* cache)
+    : id_(id),
+      parent_(parent),
+      attributes_request_(nullptr),
+      geometry_request_(nullptr),
+      properties_request_(nullptr),
+      children_request_(nullptr),
+      cache_(cache) {
+  // Select state change events BEFORE getting the initial window state to avoid
+  // race conditions.
+  uint32_t event_mask =
+      XCB_EVENT_MASK_SUBSTRUCTURE_NOTIFY | XCB_EVENT_MASK_PROPERTY_CHANGE;
+  if (id == cache->root_id_)
+    event_mask |= XCB_EVENT_MASK_STRUCTURE_NOTIFY;
+  selected_events_.reset(new XScopedEventSelector(id, event_mask));
+
+  cache->event_source_->EnqueueRequest(new QueryTreeRequest(this, cache));
+  cache->event_source_->EnqueueRequest(new ListPropertiesRequest(this, cache));
+  cache->event_source_->EnqueueRequest(new GetGeometryRequest(this, cache));
+  cache->event_source_->EnqueueRequest(
+      new GetWindowAttributesRequest(this, cache));
+  xcb_flush(cache->connection_);
+}
+
+XWindowCache::Window::~Window() {
+  // The window tree was created top-down, so must be destroyed bottom-up.
+  while (!children_.empty())
+    cache_->DestroyWindow(children_.front().get());
+
+  if (attributes_request_)
+    cache_->event_source_->DiscardRequest(attributes_request_);
+  if (geometry_request_)
+    cache_->event_source_->DiscardRequest(geometry_request_);
+  if (properties_request_)
+    cache_->event_source_->DiscardRequest(properties_request_);
+  if (children_request_)
+    cache_->event_source_->DiscardRequest(children_request_);
+}
+
+bool XWindowCache::Window::Validate() {
+  auto es = cache_->event_source_;
+  if ((children_request_ && !es->DispatchRequestNow(children_request_)) ||
+      (properties_request_ && !es->DispatchRequestNow(properties_request_)) ||
+      (geometry_request_ && !es->DispatchRequestNow(geometry_request_)) ||
+      (attributes_request_ && !es->DispatchRequestNow(attributes_request_)))
+    return false;
+
+  return true;
+}
+
+bool XWindowCache::Window::IsValid() const {
+  return !children_request_ && !properties_request_ && !geometry_request_ &&
+         !attributes_request_;
+}
+
+const XWindowCache::Property* XWindowCache::Window::GetProperty(
+    XID atom) const {
+  // |window_| should already be validated for clients to be able to
+  // call this function
+  DCHECK(IsValid());
+  auto it = properties_.find(atom);
+  if (it == properties_.end())
+    return nullptr;
+  Property* property = it->second.get();
+  return property->Validate() ? property : nullptr;
+}
+
+XWindowCache::Window::Children XWindowCache::Window::GetChildren() const {
+  return Children(this);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// XWindowCache::Window::Children
+
+XWindowCache::Window::Children::Children(const XWindowCache::Window* window)
+    : window_(window) {}
+
+std::size_t XWindowCache::Window::Children::size() const {
+  std::size_t count = 0;
+  for (const auto* window : *this) {
+    (void)window;
+    count++;
+  }
+  return count;
+}
+
+ChildIterator XWindowCache::Window::Children::begin() const {
+  return iterator(window_->children_.begin(), window_->children_.end());
+}
+
+ChildIterator XWindowCache::Window::Children::end() const {
+  return iterator(window_->children_.end(), window_->children_.end());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// XWindowCache::Window::Children::iterator
+
+ChildIterator::iterator(std::list<std::unique_ptr<Window>>::const_iterator it,
+                        std::list<std::unique_ptr<Window>>::const_iterator end)
+    : it_(it), end_(end) {
+  SkipInvalidChildren();
+}
+
+ChildIterator::iterator(const iterator& other)
+    : it_(other.it_), end_(other.end_) {}
+
+ChildIterator::~iterator() {}
+
+auto ChildIterator::operator++() -> iterator& {
+  it_++;
+  SkipInvalidChildren();
+  return *this;
+}
+
+bool ChildIterator::operator==(const iterator& other) const {
+  return it_ == other.it_;
+}
+
+bool ChildIterator::operator!=(const iterator& other) const {
+  return it_ != other.it_;
+}
+
+const XWindowCache::Window* ChildIterator::operator*() const {
+  return it_->get();
+}
+
+// The CAP theorem says we can only guarantee two out of (Consistency,
+// Availability, Partition Tolerance).  We want to guarantee
+// availability (ie, when a client requests window information, we
+// want to at least give them something) and partition tolerance (we
+// want to return an atomic window, not one that was destroyed
+// half-way through caching that we can no longer obtain information
+// about).  XWindowCache sacrifices consistency and settles for BASE
+// (Basically Available, Soft state, Eventual consistency) semantics.
+// There are cases when the cache may not be entirely built, but
+// clients need window information.  In this case, we must process
+// events and replies out-of-order to obtain the necessary
+// information.  By doing this, we sacrifice consistency for
+// availability.  However, we select events on windows before caching
+// their information, so even though we early-process replies, the
+// queued events will bring the window to eventual consistency.
+void ChildIterator::SkipInvalidChildren() {
+  while (it_ != end_) {
+    auto next = it_;
+    next++;
+    if ((*it_)->Validate())
+      return;
+    it_ = next;
+  }
+}
+
+}  // namespace ui