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..9fcacc8ab6e6939edb17047220fdcafb3df08c47
--- /dev/null
+++ b/ui/base/x/x11_window_cache.cc
@@ -0,0 +1,617 @@
+// 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 <poll.h>
+#include <X11/Xlib.h>
+#include <xcb/xcbext.h>
+
+#include <algorithm>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include "base/logging.h"
+
+namespace ui {
+
+namespace {
+
+const char kNetWmIcon[] = "_NET_WM_ICON";
+
+template <typename T>
+void CacheWindowGeometryFromEvent(XWindowCache::Window* window, T* event) {
+  window->cached_geometry = true;
+  window->x = event->x;
+  window->y = event->y;
+  window->width = event->width;
+  window->height = event->height;
+  window->border_width = event->border_width;
+}
+
+auto 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](XWindowCache::Window* child) {
+                        return child->id == child_id;
+                      });
+}
+
+}  // anonymous namespace
+
+XWindowCache::Property::Property(xcb_atom_t name)
+    : name(name), cached_property(false) {
+  data.bits_8 = nullptr;
+}
+
+XWindowCache::Property::~Property() {
+  delete[] data.bits_8;
+}
+
+const XWindowCache::Property* XWindowCache::Window::GetProperty(
+    XID atom) const {
+  auto it = properties.find(atom);
+  return it == properties.end() ? nullptr : it->second.get();
+}
+
+XWindowCache::Window::Window(xcb_window_t id, XWindowCache::Window* parent)
+    : id(id),
+      parent(parent),
+      cached_attributes(false),
+      cached_geometry(false),
+      cached_properties(false),
+      cached_children(false) {}
+
+XWindowCache::Window::~Window() {}
+
+XWindowCache::Request::Request(xcb_window_t id) : id_(id) {}
+
+XWindowCache::GetWindowAttributesRequest::GetWindowAttributesRequest(
+    xcb_window_t window,
+    XWindowCache* cache)
+    : Request(window) {
+  sequence_ = xcb_get_window_attributes(cache->connection_, window).sequence;
+}
+
+void XWindowCache::GetWindowAttributesRequest::OnReply(void* r,
+                                                       XWindowCache* cache) {
+  auto* reply = reinterpret_cast<xcb_get_window_attributes_reply_t*>(r);
+
+  // Don't bother getting stale attributes if the window was destroyed.
+  Window* window = cache->GetWindow(id_);
+  if (!window)
+    return;
+
+  window->cached_attributes = true;
+  window->override_redirect = reply->override_redirect;
+  window->is_mapped = reply->map_state != XCB_MAP_STATE_UNMAPPED;
+}
+
+XWindowCache::GetGeometryRequest::GetGeometryRequest(xcb_window_t window,
+                                                     XWindowCache* cache)
+    : Request(window) {
+  sequence_ = xcb_get_geometry(cache->connection_, window).sequence;
+}
+
+void XWindowCache::GetGeometryRequest::OnReply(void* r, XWindowCache* cache) {
+  auto* reply = reinterpret_cast<xcb_get_geometry_reply_t*>(r);
+
+  // Don't bother getting stale attributes if the window was destroyed.
+  Window* window = cache->GetWindow(id_);
+  if (!window)
+    return;
+
+  window->cached_geometry = true;
+  window->x = reply->x;
+  window->y = reply->y;
+  window->width = reply->width;
+  window->height = reply->height;
+  window->border_width = reply->border_width;
+}
+
+XWindowCache::ListPropertiesRequest::ListPropertiesRequest(xcb_window_t window,
+                                                           XWindowCache* cache)
+    : Request(window) {
+  sequence_ = xcb_list_properties(cache->connection_, window).sequence;
+}
+
+void XWindowCache::ListPropertiesRequest::OnReply(void* r,
+                                                  XWindowCache* cache) {
+  auto* reply = reinterpret_cast<xcb_list_properties_reply_t*>(r);
+
+  // Don't bother getting stale properties if the window was destroyed.
+  Window* window = cache->GetWindow(id_);
+  if (!window)
+    return;
+
+  window->cached_properties = true;
+  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);
+  }
+}
+
+XWindowCache::QueryTreeRequest::QueryTreeRequest(xcb_window_t window,
+                                                 XWindowCache* cache)
+    : Request(window) {
+  sequence_ = xcb_query_tree(cache->connection_, window).sequence;
+}
+
+void XWindowCache::QueryTreeRequest::OnReply(void* r, XWindowCache* cache) {
+  auto* reply = reinterpret_cast<xcb_query_tree_reply_t*>(r);
+
+  // Don't bother getting stale children if the parent was destroyed.
+  Window* p = cache->GetWindow(id_);
+  if (!p)
+    return;
+
+  DCHECK(p->children.empty());
+
+  xcb_window_t* children = xcb_query_tree_children(reply);
+  int n_children = xcb_query_tree_children_length(reply);
+
+  p->cached_children = true;
+
+  // Iterate over children from top-to-bottom.
+  for (int i = n_children - 1; i >= 0; i--) {
+    Window* child = new Window(children[i], p);
+    p->children.push_back(child);
+    cache->CacheWindow(child);
+  }
+}
+
+XWindowCache::GetPropertyRequest::GetPropertyRequest(xcb_window_t window,
+                                                     xcb_atom_t atom,
+                                                     XWindowCache* cache)
+    : Request(window), atom_(atom) {
+  // 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 max_property_size = 0xffff;
+  sequence_ = xcb_get_property(cache->connection_, false, window, atom,
+                               XCB_ATOM_ANY, 0, max_property_size)
+                  .sequence;
+}
+
+void XWindowCache::GetPropertyRequest::OnReply(void* r, XWindowCache* cache) {
+  auto* reply = reinterpret_cast<xcb_get_property_reply_t*>(r);
+
+  Window* window = cache->GetWindow(id_);
+  if (!window)
+    return;
+
+  if (window->properties.find(atom_) == window->properties.end())
+    return;
+  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 = window->properties[atom_].get();
+
+  property->cached_property = true;
+  property->type = reply->type;
+  DCHECK(reply->format == 8 || reply->format == 16 || reply->format == 32);
+  property->data_format = reply->format;
+  property->data_length = xcb_get_property_value_length(reply);
+  // TODO(thomasanderson): verify data_bytes is correct
+  uint32_t data_bytes = property->data_length * (property->data_format / 8);
+  property->data.bits_8 = new uint8_t[data_bytes];
+  std::memcpy(property->data.bits_8, xcb_get_property_value(reply), data_bytes);
+}
+
+XWindowCache::XWindowCache(XDisplay* display, XID root)
+    : root_(nullptr), sequence_(0), net_wm_icon_(0) {
+  connection_ = xcb_connect(DisplayString(display), nullptr);

[Daniel Erat, 2016/08/06 00:49:22]

this is establishing a second connection to the X server. this makes me anxious;
races are likely when doing this.

[Tom (Use chromium acct), 2016/08/08 23:23:38]

Acknowledged.

+  if (xcb_connection_has_error(connection_))
+    return;
+
+  net_wm_icon_cookie_ =
+      xcb_intern_atom(connection_, false, sizeof(kNetWmIcon) - 1, kNetWmIcon);
+
+  root_ = new Window(root, nullptr);
+  CacheWindow(root_);
+
+  xcb_flush(connection_);
+}
+
+XWindowCache::~XWindowCache() {
+  xcb_disconnect(connection_);
+}
+
+bool XWindowCache::ConnectionHasError() const {
+  return xcb_connection_has_error(connection_);
+}
+
+int XWindowCache::ConnectionFd() const {
+  return xcb_get_file_descriptor(connection_);
+}
+
+bool XWindowCache::BlockUntilConnectionIsReadable() {
+  if (ConnectionHasError())
+    return false;
+
+  int conn_fd = ConnectionFd();
+
+  struct pollfd rfd;
+  rfd.fd = conn_fd;
+  rfd.events = POLLIN;
+  rfd.revents = 0;
+  // TODO(thomasanderson): should we handle EAGAIN?

[Elliot Glaysher, 2016/08/08 18:17:28]

I suspect that you might. If you EAGAIN here, will you just do nothing and
reenter the poll()?

[Tom (Use chromium acct), 2016/08/08 23:23:38]

yeah pretty much.  So I guess the best thing to do is to keep polling while poll
returns -1 (which could even be because we got a signal), with a timeout? 
poll() doesn't tell us how much time is left like select() does, so we'd have to
manage the timeout ourselves

[Tom (Use chromium acct), 2016/08/15 19:57:00]

Fixed. Turns out we have a convention just to handle EINTR, and there's macros
for this in //base.

+  poll(&rfd, 1, 3000);  // Use a timeout of 3s.
+  return rfd.revents & POLLIN;
+}
+
+const XWindowCache::Window* XWindowCache::GetWindow(XID id) const {
+  return GetWindow(static_cast<xcb_window_t>(id));
+}
+
+XWindowCache::Window* XWindowCache::GetWindow(xcb_window_t id) const {
+  auto it = windows_.find(id);
+  return it == windows_.end() ? nullptr : it->second.get();
+}
+
+void XWindowCache::OnConnectionReadable() {
+  // xcb serially reads events and replies and then stores them in two queues.
+  // We want to merge these queues into one to make sure we process events and
+  // replies in order.
+  //
+  // xcb_poll_for_reply does not read any new data, while xcb_poll_for_event
+  // does, so get all available events first, followed by all replies.
+  //
+  // xcb_poll_for_event reads all available data, so we cannot have an outer
+  // loop reading events and an inner loop reading replies.  That would be too
+  // easy.  The only way to guarantee ordering is to read all events at once,
+  // followed by all replies.
+
+  // Get all events.
+  std::queue<xcb_generic_event_t*> events;
+  xcb_generic_event_t* event;
+  while ((event = xcb_poll_for_event(connection_)))
+    events.emplace(event);
+
+  // Get all replies for which we have a queued request.  Some requests, such as
+  // xcb_change_window_attributes, do not have a corresponding reply, so skip
+  // over those sequence numbers.  We may also want to poll for replies
+  // ourselves, such as when getting the _NET_WM_ICON atom, or when
+  // synchronizing.  Skip over these too.
+  std::queue<std::unique_ptr<Request>> requests;
+  std::queue<xcb_generic_reply_t*> replies;
+  while (!requests_.empty()) {
+    uint16_t front_sequence = requests_.front()->sequence();
+    void* reply;
+    if (!xcb_poll_for_reply(connection_, front_sequence, &reply, nullptr))
+      break;
+    if (reply) {
+      requests.emplace(std::move(requests_.front()));
+      replies.emplace(reinterpret_cast<xcb_generic_reply_t*>(reply));
+    }
+    // Remove the request from the queue even if there was an error.
+    requests_.pop();
+  }
+
+  // Process events and replies in order.
+  while (!events.empty() || !replies.empty()) {
+    // Give precedence to replies.
+    if (!replies.empty() && sequence_ == replies.front()->sequence) {
+      xcb_generic_reply_t* reply = replies.front();
+      requests.front()->OnReply(reply, this);
+      free(reply);
+      requests.pop();
+      replies.pop();
+    } else if (!events.empty() && sequence_ == events.front()->sequence) {
+      xcb_generic_event_t* event = events.front();
+      ProcessEvent(event);
+      free(event);
+      events.pop();
+    } else {
+      sequence_++;
+    }
+  }
+
+  // Write out any requests we may have made.
+  xcb_flush(connection_);
+}
+
+bool XWindowCache::BlockUntilTreeIsCached() {
+  while (!requests_.empty()) {
+    if (!BlockUntilConnectionIsReadable())
+      return false;
+    OnConnectionReadable();
+  }
+  return true;
+}
+
+bool XWindowCache::Synchronize() {
+  if (!root_)
+    return true;  // There's nothing to synchronize if the root was destroyed.
+
+  // Try getting some info about the root window and wait until we get a
+  // response or an error.
+  auto sequence = xcb_get_window_attributes(connection_, root_->id).sequence;
+  xcb_flush(connection_);
+
+  while (BlockUntilConnectionIsReadable()) {
+    OnConnectionReadable();
+    void* reply = nullptr;
+    if (!xcb_poll_for_reply(connection_, sequence, &reply, nullptr))
+      continue;
+    if (reply) {
+      free(reply);
+      return true;
+    }
+    // There was some sort of error.  This may just be because the root was
+    // destroyed.  Only return false if there was a connection error.
+    return !ConnectionHasError();
+  }
+  xcb_discard_reply(connection_, sequence);
+  return false;
+}
+
+bool XWindowCache::SynchronizeWith(XDisplay* display) {
+  XSync(display, False);
+  return Synchronize();
+}
+
+void XWindowCache::ProcessEvent(xcb_generic_event_t* g) {
+  switch (g->response_type & ~0x80) {
+    case XCB_PROPERTY_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_property_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      switch (event->state) {
+        case XCB_PROPERTY_DELETE:
+          window->properties.erase(event->atom);
+          break;
+        case XCB_PROPERTY_NEW_VALUE:
+          CacheProperty(window, event->atom);
+          break;
+        default:
+          NOTREACHED();
+      }
+      break;
+    }
+    case XCB_CIRCULATE_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_circulate_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      if (event->event == event->window)
+        break;  // This is our root window
+
+      Window* parent = window->parent;
+      DCHECK_EQ(parent->id, event->event);
+
+      parent->children.remove(window);
+      switch (event->place) {
+        case XCB_PLACE_ON_TOP:
+          parent->children.push_front(window);
+          break;
+        case XCB_PLACE_ON_BOTTOM:
+          parent->children.push_back(window);
+          break;
+        default:
+          NOTREACHED();
+      }
+      break;
+    }
+    case XCB_CONFIGURE_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_configure_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      CacheWindowGeometryFromEvent(window, event);
+
+      if (event->event == event->window)
+        break;
+
+      Window* parent = window->parent;
+      DCHECK_EQ(parent->id, event->event);
+
+      parent->children.remove(window);
+      if (event->above_sibling) {
+        auto it = FindChild(parent, event->above_sibling);
+        if (it == parent->children.end()) {
+          NOTREACHED();
+          // We got into a bad state.  Recache |parent|.
+          Window* grandparent = parent->parent;
+          xcb_window_t id = parent->id;
+          DeleteSubtree(parent);
+          CacheWindow(new Window(id, grandparent));
+        } else {
+          parent->children.insert(it, window);
+        }
+      } else {
+        // |window| is not above any other sibling window
+        parent->children.push_back(window);
+      }
+      break;
+    }
+    case XCB_CREATE_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_create_notify_event_t*>(g);
+
+      Window* parent = GetWindow(event->parent);
+      if (!parent)
+        break;
+
+      if (!parent->cached_children) {
+        // |parent| is in the process of being cached, so we will pick up this
+        // window in the near future.
+        break;
+      }
+
+      Window* window = new Window(event->window, parent);
+
+      window->cached_attributes = true;
+      window->override_redirect = event->override_redirect;
+      window->is_mapped = false;
+
+      CacheWindowGeometryFromEvent(window, event);
+
+      CacheWindow(window);
+      parent->children.push_front(window);
+      break;
+    }
+    case XCB_DESTROY_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_destroy_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      if (window->parent) {
+        auto& children = window->parent->children;
+        auto it = std::find(children.begin(), children.end(), window);
+        if (it != children.end())
+          window->parent->children.erase(it);
+      } else {
+        // Window has no parent, so this must be the root that's going away.
+        root_ = nullptr;
+      }
+
+      DeleteSubtree(window);
+      break;
+    }
+    case XCB_GRAVITY_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_gravity_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      window->x = event->x;
+      window->y = event->y;
+      break;
+    }
+    case XCB_MAP_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_map_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      window->cached_attributes = true;
+      window->override_redirect = event->override_redirect;
+      window->is_mapped = true;
+      break;
+    }
+    case XCB_REPARENT_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_reparent_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      window->x = event->x;
+      window->y = event->y;
+
+      window->cached_attributes = true;
+      window->override_redirect = event->override_redirect;
+      window->is_mapped = false;  // Reparenting a window unmaps it
+
+      Window* parent = window->parent;
+      if (parent)
+        parent->children.remove(window);
+      else
+        break;  // Don't worry about caching windows above our root.
+
+      parent = GetWindow(event->parent);
+      if (!parent || !parent->cached_children) {
+        // |window| is either no longer in our tree, or we are already waiting
+        // to receive a list of |parent|'s children.
+        DeleteSubtree(window);
+        break;
+      }
+      window->parent = parent;
+
+      parent->children.push_front(window);
+      break;
+    }
+    case XCB_UNMAP_NOTIFY: {
+      auto* event = reinterpret_cast<xcb_unmap_notify_event_t*>(g);
+
+      Window* window = GetWindow(event->window);
+      if (!window)
+        break;
+
+      window->is_mapped = false;
+      break;
+    }
+    default:
+      // We can't opt-out of receiving events like MappingNotify or
+      // ClientMessage.
+      break;
+  }
+}
+
+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;
+  xcb_window_t id = window->id;
+  Property* property = new Property(atom);
+  window->properties[atom].reset(property);
+  if (!property->cached_property)
+    requests_.emplace(new GetPropertyRequest(id, atom, this));
+}
+
+void XWindowCache::CacheWindow(XWindowCache::Window* window) {
+  DCHECK(window);
+  xcb_window_t id = window->id;
+  DCHECK(windows_.find(id) == windows_.end());
+
+  uint32_t event_mask =
+      XCB_EVENT_MASK_SUBSTRUCTURE_NOTIFY | XCB_EVENT_MASK_PROPERTY_CHANGE;
+  if (id == root_->id) {
+    event_mask |= XCB_EVENT_MASK_STRUCTURE_NOTIFY;
+  }
+  auto cookie = xcb_change_window_attributes(connection_, id, XCB_CW_EVENT_MASK,
+                                             &event_mask);
+  xcb_discard_reply(connection_, cookie.sequence);
+
+  // Get the desired window state AFTER requesting state change events to avoid
+  // race conditions.
+
+  if (!window->cached_children)
+    requests_.emplace(new QueryTreeRequest(id, this));
+
+  if (!window->cached_properties)
+    requests_.emplace(new ListPropertiesRequest(id, this));
+
+  if (!window->cached_attributes)
+    requests_.emplace(new GetWindowAttributesRequest(id, this));
+
+  if (!window->cached_geometry)
+    requests_.emplace(new GetGeometryRequest(id, this));
+
+  windows_[id].reset(window);
+}
+
+void XWindowCache::DeleteSubtree(XWindowCache::Window* window) {
+  DCHECK(window);
+  for (auto* child : window->children)
+    DeleteSubtree(child);
+  windows_.erase(window->id);
+}
+
+}  // namespace ui