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..88c9e21aeaf6ec7fc1b544ee5175268bd4daa079
--- /dev/null
+++ b/ui/base/x/x11_window_cache.cc
@@ -0,0 +1,583 @@
+// 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;
+}
+
+}  // 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() {}
+XWindowCache::Request::~Request() {}
+
+XWindowCache::GetWindowAttributesRequest::GetWindowAttributesRequest(
+    xcb_window_t window,
+    XWindowCache* cache)
+    : id(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)
+    : id(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)
+    : id(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)
+    : id(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;
+
+  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)
+    : id(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;
+  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);
+  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), net_wm_icon_(0) {
+  connection_ = xcb_connect(DisplayString(display), nullptr);
+  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_);
+}
+
+void XWindowCache::PrintWindowTreeForTesting() const {
+  PrintWindowTreeForTestingAux(root_, 0);
+}
+
+void XWindowCache::PrintWindowTreeForTestingAux(Window* window,

[Tom (Use chromium acct), 2016/07/26 20:17:42]

This was useful when developing, but it causes a presubmit error for using
printf.

Should this be changed to use logging instead, or just get rid of this?

[Tom (Use chromium acct), 2016/08/06 00:38:17]

No longer applicable.  Removed.

+                                                int indent) const {
+  if (!window)
+    return;
+  for (int i = 0; i < indent; i++)
+    printf("\t");
+  printf("%d\n", window->id);
+  if (window->cached_children) {
+    for (Window* child : window->children)
+      PrintWindowTreeForTestingAux(child, indent + 1);
+  }
+}
+
+bool XWindowCache::BlockUntilConnectionIsReadable() {
+  if (ConnectionHasError())
+    return false;
+
+  int conn_fd = ConnectionFd();
+
+  struct pollfd rfd;
+  rfd.fd = conn_fd;
+  rfd.events = POLLIN;
+  rfd.revents = 0;
+  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() {

[Tom (Use chromium acct), 2016/07/26 20:17:42]

So we process events last as the comment points out.

Would it be reliable to use the sequence number given in each reply/event to
merge the events/replies back into a chronological stream?

The X11 protocol spec says that events "contains the least significant 16 bits
of the sequence number of the last request issued by the client that was (or is
currently being) processed by the server."  It's the "or is currently being"
that worries me.

[Tom (Use chromium acct), 2016/08/06 00:38:17]

No longer applicable.  Reordered events/replies

+  // xcb serially reads events and replies and then stores them in two queues.
+  // There's no perfect way to merge these responses back into a chronological
+  // stream, so handle all replies before events.  This avoids getting stuck in
+  // an old state.
+  //
+  // xcb_poll_for_reply does not read any new data, while xcb_poll_for_event
+  // does, so get all available events first and store them so they can be
+  // processed last.
+
+  // Get all events.
+  std::vector<xcb_generic_event_t*> events;
+  xcb_generic_event_t* event;
+  while ((event = xcb_poll_for_event(connection_)))
+    events.push_back(event);
+
+  // Process all replies.
+  while (!requests_.empty()) {
+    void* reply = nullptr;
+    Request* request = requests_.front().get();
+    if (!xcb_poll_for_reply(connection_, request->sequence, &reply, nullptr))
+      break;
+    if (reply) {
+      request->OnReply(reply, this);
+      free(reply);
+    }
+    requests_.pop();
+  }
+
+  // Process all events.
+  for (auto* event : events) {
+    ProcessEvent(event);
+    free(event);
+  }
+
+  // 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 = std::find_if(parent->children.begin(), parent->children.end(),
+                               [&event](Window* child) {
+                                 return child->id == 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;
+
+      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) {
+        // |window| is no longer in our tree
+        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) {
+  xcb_window_t id = window->id;
+  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;
+  }
+  xcb_change_window_attributes(connection_, id, XCB_CW_EVENT_MASK, &event_mask);
+
+  // Get the desired window state AFTER requesting state change events to avoid
+  // race conditions.
+
+  if (!window->cached_attributes)
+    requests_.emplace(new GetWindowAttributesRequest(id, this));
+
+  if (!window->cached_geometry)
+    requests_.emplace(new GetGeometryRequest(id, this));
+
+  if (!window->cached_properties)
+    requests_.emplace(new ListPropertiesRequest(id, this));
+
+  if (!window->cached_children)
+    requests_.emplace(new QueryTreeRequest(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