Tweaks to ViewManager:

. OnNodeHierarchyChanged() is only sent for nodes the client cares
  about (see ShouldNotifyOnHierarchyChange for exact details).
. OnNodeHierarchyChanged() now includes any nodes not yet known to the
  client.
. Added OnServerChangeIdAdvanced, which is sent if the change id
  advances but the client didn't get a notification (this can happen
  when hierarchy changes are done in other clients that the client
  isn't notified about).
. OnConnectionEstablished now includes the state of the tree.

BUG=365012
TEST=covered by tests
R=ben@chromium.org

Review URL: https://codereview.chromium.org/288313002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@270925 0039d316-1c4b-4281-b951-d872f2087c98

13 files changed, 686 insertions, 197 deletions

diff --git a/mojo/mojo_services.gypi b/mojo/mojo_services.gypi
index f3433ab..6740ff0 100644
--- a/mojo/mojo_services.gypi
+++ b/mojo/mojo_services.gypi
@@ -239,6 +239,8 @@
             'services/view_manager/root_node_manager.h',
             'services/view_manager/root_view_manager.cc',
             'services/view_manager/root_view_manager.h',
+            'services/view_manager/type_converters.cc',
+            'services/view_manager/type_converters.h',
             'services/view_manager/view.cc',
             'services/view_manager/view.h',
             'services/view_manager/view_manager_connection.cc',
diff --git a/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.cc b/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.cc
index cb9a8ef..7959583 100644
--- a/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.cc
+++ b/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.cc
@@ -306,12 +306,8 @@ ViewManagerSynchronizer::ViewManagerSynchronizer(ViewManager* view_manager)
             &service_);
   service_->SetClient(this);
 
-  AllocationScope scope;
-  service_->GetNodeTree(
-      1,
-      base::Bind(&ViewManagerSynchronizer::OnRootTreeReceived,
-                 base::Unretained(this)));
-
+  // Start a runloop. This loop is quit when the server tells us about the
+  // connection (OnConnectionEstablished()).
   base::RunLoop loop;
   init_loop_ = &loop;
   init_loop_->Run();
@@ -397,18 +393,51 @@ void ViewManagerSynchronizer::SetActiveView(TransportNodeId node_id,
 
 void ViewManagerSynchronizer::OnConnectionEstablished(
     TransportConnectionId connection_id,
-    TransportChangeId next_server_change_id) {
+    TransportChangeId next_server_change_id,
+    const mojo::Array<INode>& nodes) {
   connected_ = true;
   connection_id_ = connection_id;
   next_server_change_id_ = next_server_change_id;
+
+  ViewManagerPrivate private_manager(view_manager_);
+  std::vector<ViewTreeNode*> parents;
+  ViewTreeNode* root = NULL;
+  ViewTreeNode* last_node = NULL;
+  for (size_t i = 0; i < nodes.size(); ++i) {
+    if (last_node && nodes[i].parent_id() == last_node->id()) {
+      parents.push_back(last_node);
+    } else if (!parents.empty()) {
+      while (parents.back()->id() != nodes[i].parent_id())
+        parents.pop_back();
+    }
+    ViewTreeNode* node =
+        AddNodeToViewManager(view_manager_,
+                             !parents.empty() ? parents.back() : NULL,
+                             nodes[i].node_id(),
+                             nodes[i].view_id());
+    if (!last_node)
+      root = node;
+    last_node = node;
+  }
+  private_manager.set_root(root);
+  if (init_loop_)
+    init_loop_->Quit();
+
   Sync();
 }
 
+void ViewManagerSynchronizer::OnServerChangeIdAdvanced(
+    uint32_t next_server_change_id) {
+  next_server_change_id_ = next_server_change_id;
+}
+
 void ViewManagerSynchronizer::OnNodeHierarchyChanged(
     uint32_t node_id,
     uint32_t new_parent_id,
     uint32_t old_parent_id,
-    TransportChangeId server_change_id) {
+    TransportChangeId server_change_id,
+    const mojo::Array<INode>& nodes) {
+  // TODO: deal with |nodes|.
   next_server_change_id_ = server_change_id + 1;
 
   ViewTreeNode* new_parent =
@@ -493,32 +522,5 @@ void ViewManagerSynchronizer::RemoveFromPendingQueue(
   pending_transactions_.erase(pending_transactions_.begin());
 }
 
-void ViewManagerSynchronizer::OnRootTreeReceived(
-    const Array<INode>& nodes) {
-  ViewManagerPrivate private_manager(view_manager_);
-  std::vector<ViewTreeNode*> parents;
-  ViewTreeNode* root = NULL;
-  ViewTreeNode* last_node = NULL;
-  for (size_t i = 0; i < nodes.size(); ++i) {
-    if (last_node && nodes[i].parent_id() == last_node->id()) {
-      parents.push_back(last_node);
-    } else if (!parents.empty()) {
-      while (parents.back()->id() != nodes[i].parent_id())
-        parents.pop_back();
-    }
-    ViewTreeNode* node =
-        AddNodeToViewManager(view_manager_,
-                             !parents.empty() ? parents.back() : NULL,
-                             nodes[i].node_id(),
-                             nodes[i].view_id());
-    if (!last_node)
-      root = node;
-    last_node = node;
-  }
-  private_manager.set_root(root);
-  if (init_loop_)
-    init_loop_->Quit();
-}
-
 }  // namespace view_manager
 }  // namespace mojo
diff --git a/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.h b/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.h
index 1063a50..1a50583 100644
--- a/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.h
+++ b/mojo/services/public/cpp/view_manager/lib/view_manager_synchronizer.h
@@ -55,12 +55,16 @@ class ViewManagerSynchronizer : public IViewManagerClient {
   // Overridden from IViewManagerClient:
   virtual void OnConnectionEstablished(
       TransportConnectionId connection_id,
-      TransportChangeId next_server_change_id) OVERRIDE;
+      TransportChangeId next_server_change_id,
+      const mojo::Array<INode>& nodes) OVERRIDE;
+  virtual void OnServerChangeIdAdvanced(
+      uint32_t next_server_change_id) OVERRIDE;
   virtual void OnNodeHierarchyChanged(
       uint32 node_id,
       uint32 new_parent_id,
       uint32 old_parent_id,
-      TransportChangeId server_change_id) OVERRIDE;
+      TransportChangeId server_change_id,
+      const mojo::Array<INode>& nodes) OVERRIDE;
   virtual void OnNodeDeleted(TransportNodeId node_id,
                              TransportChangeId server_change_id) OVERRIDE;
   virtual void OnNodeViewReplaced(uint32_t node,
@@ -76,8 +80,6 @@ class ViewManagerSynchronizer : public IViewManagerClient {
   // front of the queue.
   void RemoveFromPendingQueue(ViewManagerTransaction* transaction);
 
-  void OnRootTreeReceived(const Array<INode>& data);
-
   ViewManager* view_manager_;
   bool connected_;
   TransportConnectionId connection_id_;
diff --git a/mojo/services/public/interfaces/view_manager/view_manager.mojom b/mojo/services/public/interfaces/view_manager/view_manager.mojom
index 8c64a29..01079e5 100644
--- a/mojo/services/public/interfaces/view_manager/view_manager.mojom
+++ b/mojo/services/public/interfaces/view_manager/view_manager.mojom
@@ -28,9 +28,9 @@ interface IViewManager {
   // the connection.
   CreateNode(uint32 node_id) => (bool success);
 
-  // Deletes a node. This does not recurse. Children are removed from the node
-  // before it is destroyed. Deletion is always allowed and implicitly advances
-  // |server_change_id|.
+  // Deletes a node. This does not recurse. No hierarchy change notifications
+  // are sent as a result of this. Deletion is always allowed and implicitly
+  // advances |server_change_id|.
   DeleteNode(uint32 node_id) => (bool success);
 
   // Reparents a node. See description above class for details of |change_id|.
@@ -79,20 +79,34 @@ interface IViewManager {
 interface IViewManagerClient {
   // Invoked once the connection has been established. |connection_id| is the id
   // that uniquely identifies this connection. |next_server_change_id| is the
-  // id of the next change the server is expecting.
-  OnConnectionEstablished(uint16 connection_id, uint32 next_server_change_id);
+  // id of the next change the server is expecting. |nodes| are the nodes
+  // parented to the root.
+  OnConnectionEstablished(uint16 connection_id,
+                          uint32 next_server_change_id,
+                          INode[] nodes);
+
+  // This is sent to clients when a change is made to the server that results
+  // in the |server_change_id| changing but the client isn't notified. This is
+  // not sent if the client receives a callback giving a new
+  // |server_change_id|. For example, if a client 1 changes the hierarchy in
+  // some way but client 2 isn't notified of the change, then client 2 gets
+  // OnServerChangeIdAdvanced().
+  OnServerChangeIdAdvanced(uint32 next_server_change_id);
 
   // Invoked when a change is done to the hierarchy. A value of 0 is used to
   // identify a null node. For example, if the old_parent is NULL, 0 is
   // supplied. See description above ViewManager for details on the change ids.
+  // |nodes| contains any nodes that are that the client has not been told
+  // about. This is not sent for hierarchy changes of nodes not known to this
+  // client or not attached to the tree.
   OnNodeHierarchyChanged(uint32 node,
                          uint32 new_parent,
                          uint32 old_parent,
-                         uint32 server_change_id);
+                         uint32 server_change_id,
+                         INode[] nodes);
 
   // Invoked when a node is deleted.
   OnNodeDeleted(uint32 node, uint32 server_change_id);
-                
 
   // Invoked when the view associated with a node is replaced by another view.
   // 0 is used to identify a null view.
diff --git a/mojo/services/view_manager/node.cc b/mojo/services/view_manager/node.cc
index 49d9376..21b3b5c 100644
--- a/mojo/services/view_manager/node.cc
+++ b/mojo/services/view_manager/node.cc
@@ -40,7 +40,7 @@ Node::~Node() {
   SetView(NULL);
 }
 
-Node* Node::GetParent() {
+const Node* Node::GetParent() const {
   if (!window_.parent())
     return NULL;
   return window_.parent()->GetProperty(kNodeKey);
@@ -54,6 +54,13 @@ void Node::Remove(Node* child) {
   window_.RemoveChild(&child->window_);
 }
 
+const Node* Node::GetRoot() const {
+  const aura::Window* window = &window_;
+  while (window && window->parent())
+    window = window->parent();
+  return window->GetProperty(kNodeKey);
+}
+
 std::vector<Node*> Node::GetChildren() {
   std::vector<Node*> children;
   children.reserve(window_.children().size());
@@ -62,6 +69,10 @@ std::vector<Node*> Node::GetChildren() {
   return children;
 }
 
+bool Node::Contains(const Node* node) const {
+  return node && window_.Contains(&(node->window_));
+}
+
 void Node::SetView(View* view) {
   if (view == view_)
     return;
diff --git a/mojo/services/view_manager/node.h b/mojo/services/view_manager/node.h
index 9dda564..b989b04 100644
--- a/mojo/services/view_manager/node.h
+++ b/mojo/services/view_manager/node.h
@@ -39,13 +39,24 @@ class MOJO_VIEW_MANAGER_EXPORT Node
 
   aura::Window* window() { return &window_; }
 
-  Node* GetParent();
+  const Node* GetParent() const;
+  Node* GetParent() {
+    return const_cast<Node*>(const_cast<const Node*>(this)->GetParent());
+  }
+
+  const Node* GetRoot() const;
+  Node* GetRoot() {
+    return const_cast<Node*>(const_cast<const Node*>(this)->GetRoot());
+  }
 
   std::vector<Node*> GetChildren();
 
+  bool Contains(const Node* node) const;
+
   // Sets the view associated with this node. Node does not own its View.
   void SetView(View* view);
   View* view() { return view_; }
+  const View* view() const { return view_; }
 
  private:
   // WindowObserver overrides:
diff --git a/mojo/services/view_manager/root_node_manager.cc b/mojo/services/view_manager/root_node_manager.cc
index 80a27f9..9366d76 100644
--- a/mojo/services/view_manager/root_node_manager.cc
+++ b/mojo/services/view_manager/root_node_manager.cc
@@ -24,10 +24,11 @@ const TransportConnectionId kNoConnection = 0;
 RootNodeManager::ScopedChange::ScopedChange(
     ViewManagerConnection* connection,
     RootNodeManager* root,
-    RootNodeManager::ChangeType change_type)
+    RootNodeManager::ChangeType change_type,
+    bool is_delete_node)
     : root_(root),
       change_type_(change_type) {
-  root_->PrepareForChange(connection);
+  root_->PrepareForChange(connection, is_delete_node);
 }
 
 RootNodeManager::ScopedChange::~ScopedChange() {
@@ -46,6 +47,7 @@ RootNodeManager::RootNodeManager(Shell* shell)
     : next_connection_id_(1),
       next_server_change_id_(1),
       change_source_(kNoConnection),
+      is_processing_delete_node_(false),
       root_view_manager_(shell, this),
       root_(this, NodeId(0, kRootId)) {
 }
@@ -88,79 +90,74 @@ View* RootNodeManager::GetView(const ViewId& id) {
   return i == connection_map_.end() ? NULL : i->second->GetView(id);
 }
 
-void RootNodeManager::NotifyNodeHierarchyChanged(const NodeId& node,
-                                                 const NodeId& new_parent,
-                                                 const NodeId& old_parent) {
+void RootNodeManager::ProcessNodeHierarchyChanged(const NodeId& node,
+                                                  const NodeId& new_parent,
+                                                  const NodeId& old_parent) {
   // TODO(sky): make a macro for this.
   for (ConnectionMap::iterator i = connection_map_.begin();
        i != connection_map_.end(); ++i) {
-    if (ShouldNotifyConnection(i->first)) {
-      i->second->NotifyNodeHierarchyChanged(
-          node, new_parent, old_parent, next_server_change_id_);
-    }
+    i->second->ProcessNodeHierarchyChanged(
+        node, new_parent, old_parent, next_server_change_id_,
+        IsChangeSource(i->first));
   }
 }
 
-void RootNodeManager::NotifyNodeViewReplaced(const NodeId& node,
-                                             const ViewId& new_view_id,
-                                             const ViewId& old_view_id) {
+void RootNodeManager::ProcessNodeViewReplaced(const NodeId& node,
+                                              const ViewId& new_view_id,
+                                              const ViewId& old_view_id) {
   // TODO(sky): make a macro for this.
   for (ConnectionMap::iterator i = connection_map_.begin();
        i != connection_map_.end(); ++i) {
-    if (ShouldNotifyConnection(i->first))
-      i->second->NotifyNodeViewReplaced(node, new_view_id, old_view_id);
+    i->second->ProcessNodeViewReplaced(node, new_view_id, old_view_id,
+                                       IsChangeSource(i->first));
   }
 }
 
-void RootNodeManager::NotifyNodeDeleted(const NodeId& node) {
+void RootNodeManager::ProcessNodeDeleted(const NodeId& node) {
   // TODO(sky): make a macro for this.
   for (ConnectionMap::iterator i = connection_map_.begin();
        i != connection_map_.end(); ++i) {
-    if (ShouldNotifyConnection(i->first))
-      i->second->NotifyNodeDeleted(node, next_server_change_id_);
+    i->second->ProcessNodeDeleted(node, next_server_change_id_,
+                                 IsChangeSource(i->first));
   }
 }
 
-void RootNodeManager::NotifyViewDeleted(const ViewId& view) {
+void RootNodeManager::ProcessViewDeleted(const ViewId& view) {
   // TODO(sky): make a macro for this.
   for (ConnectionMap::iterator i = connection_map_.begin();
        i != connection_map_.end(); ++i) {
-    if (ShouldNotifyConnection(i->first))
-      i->second->NotifyViewDeleted(view);
+    i->second->ProcessViewDeleted(view, IsChangeSource(i->first));
   }
 }
 
-void RootNodeManager::PrepareForChange(ViewManagerConnection* connection) {
+void RootNodeManager::PrepareForChange(ViewManagerConnection* connection,
+                                       bool is_delete_node) {
   // Should only ever have one change in flight.
   DCHECK_EQ(kNoConnection, change_source_);
   change_source_ = connection->id();
+  is_processing_delete_node_ = is_delete_node;
 }
 
 void RootNodeManager::FinishChange(ChangeType change_type) {
   // PrepareForChange/FinishChange should be balanced.
   DCHECK_NE(kNoConnection, change_source_);
   change_source_ = 0;
+  is_processing_delete_node_ = false;
   if (change_type == CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID)
     next_server_change_id_++;
 }
 
-bool RootNodeManager::ShouldNotifyConnection(
-    TransportConnectionId connection_id) const {
-  // Don't notify the source that originated the change.
-  return connection_id != change_source_;
-}
-
 void RootNodeManager::OnNodeHierarchyChanged(const NodeId& node,
                                              const NodeId& new_parent,
                                              const NodeId& old_parent) {
   if (!root_view_manager_.in_setup())
-    NotifyNodeHierarchyChanged(node, new_parent, old_parent);
+    ProcessNodeHierarchyChanged(node, new_parent, old_parent);
 }
 
 void RootNodeManager::OnNodeViewReplaced(const NodeId& node,
                                          const ViewId& new_view_id,
                                          const ViewId& old_view_id) {
-  NotifyNodeViewReplaced(node, new_view_id, old_view_id);
+  ProcessNodeViewReplaced(node, new_view_id, old_view_id);
 }
 
 }  // namespace service
diff --git a/mojo/services/view_manager/root_node_manager.h b/mojo/services/view_manager/root_node_manager.h
index b81a566..321faf7 100644
--- a/mojo/services/view_manager/root_node_manager.h
+++ b/mojo/services/view_manager/root_node_manager.h
@@ -41,7 +41,8 @@ class MOJO_VIEW_MANAGER_EXPORT RootNodeManager : public NodeDelegate {
    public:
     ScopedChange(ViewManagerConnection* connection,
                  RootNodeManager* root,
-                 RootNodeManager::ChangeType change_type);
+                 RootNodeManager::ChangeType change_type,
+                 bool is_delete_node);
     ~ScopedChange();
 
    private:
@@ -75,16 +76,20 @@ class MOJO_VIEW_MANAGER_EXPORT RootNodeManager : public NodeDelegate {
 
   Node* root() { return &root_; }
 
+  bool IsProcessingChange() const { return change_source_ != 0; }
+
+  bool is_processing_delete_node() const { return is_processing_delete_node_; }
+
   // These functions trivially delegate to all ViewManagerConnections, which in
   // term notify their clients.
-  void NotifyNodeHierarchyChanged(const NodeId& node,
-                                  const NodeId& new_parent,
-                                  const NodeId& old_parent);
-  void NotifyNodeViewReplaced(const NodeId& node,
-                              const ViewId& new_view_id,
-                              const ViewId& old_view_id);
-  void NotifyNodeDeleted(const NodeId& node);
-  void NotifyViewDeleted(const ViewId& view);
+  void ProcessNodeHierarchyChanged(const NodeId& node,
+                                   const NodeId& new_parent,
+                                   const NodeId& old_parent);
+  void ProcessNodeViewReplaced(const NodeId& node,
+                               const ViewId& new_view_id,
+                               const ViewId& old_view_id);
+  void ProcessNodeDeleted(const NodeId& node);
+  void ProcessViewDeleted(const ViewId& view);
 
  private:
   // Used to setup any static state needed by RootNodeManager.
@@ -101,14 +106,15 @@ class MOJO_VIEW_MANAGER_EXPORT RootNodeManager : public NodeDelegate {
   // Changes should never nest, meaning each PrepareForChange() must be
   // balanced with a call to FinishChange() with no PrepareForChange()
   // in between.
-  void PrepareForChange(ViewManagerConnection* connection);
+  void PrepareForChange(ViewManagerConnection* connection, bool is_delete_node);
 
   // Balances a call to PrepareForChange().
   void FinishChange(ChangeType change_type);
 
-  // Returns true if the specified connection should be notified of the current
-  // change.
-  bool ShouldNotifyConnection(TransportConnectionId connection_id) const;
+  // Returns true if the specified connection originated the current change.
+  bool IsChangeSource(TransportConnectionId connection_id) const {
+    return connection_id == change_source_;
+  }
 
   // Overriden from NodeDelegate:
   virtual void OnNodeHierarchyChanged(const NodeId& node,
@@ -131,6 +137,9 @@ class MOJO_VIEW_MANAGER_EXPORT RootNodeManager : public NodeDelegate {
   // If non-zero we're processing a change from this client.
   TransportConnectionId change_source_;
 
+  // True if we're processing a DeleteNode request.
+  bool is_processing_delete_node_;
+
   RootViewManager root_view_manager_;
 
   // Root node.
diff --git a/mojo/services/view_manager/type_converters.cc b/mojo/services/view_manager/type_converters.cc
new file mode 100644
index 0000000..9a9b4a7
--- /dev/null
+++ b/mojo/services/view_manager/type_converters.cc
@@ -0,0 +1,34 @@
+// Copyright 2014 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 "mojo/services/view_manager/type_converters.h"
+
+#include "mojo/public/cpp/bindings/buffer.h"
+#include "mojo/services/public/interfaces/view_manager/view_manager.mojom.h"
+#include "mojo/services/view_manager/ids.h"
+#include "mojo/services/view_manager/node.h"
+#include "mojo/services/view_manager/view.h"
+
+using mojo::view_manager::INode;
+using mojo::view_manager::service::Node;
+using mojo::view_manager::service::NodeId;
+using mojo::view_manager::service::ViewId;
+
+namespace mojo {
+
+// static
+INode TypeConverter<INode, Node*>::ConvertFrom(const Node* node,
+                                               Buffer* buf) {
+  DCHECK(node);
+
+  INode::Builder builder(buf);
+  const Node* parent = node->GetParent();
+  builder.set_parent_id(NodeIdToTransportId(parent ? parent->id() : NodeId()));
+  builder.set_node_id(NodeIdToTransportId(node->id()));
+  builder.set_view_id(ViewIdToTransportId(
+                          node->view() ? node->view()->id() : ViewId()));
+  return builder.Finish();
+}
+
+}  // namespace mojo
diff --git a/mojo/services/view_manager/type_converters.h b/mojo/services/view_manager/type_converters.h
new file mode 100644
index 0000000..98ff4f3
--- /dev/null
+++ b/mojo/services/view_manager/type_converters.h
@@ -0,0 +1,36 @@
+// Copyright 2014 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.
+
+#ifndef MOJO_SERVICES_VIEW_MANAGER_TYPE_CONVERTERS_H_
+#define MOJO_SERVICES_VIEW_MANAGER_TYPE_CONVERTERS_H_
+
+#include "mojo/public/cpp/bindings/type_converter.h"
+
+namespace mojo {
+
+class Buffer;
+
+namespace view_manager {
+
+class INode;
+
+namespace service {
+class Node;
+}  // namespace service
+}  // namespace view_manager
+
+template <>
+class TypeConverter<view_manager::INode,
+                    view_manager::service::Node*> {
+ public:
+  static view_manager::INode ConvertFrom(
+      const view_manager::service::Node* node,
+      Buffer* buf);
+
+  MOJO_ALLOW_IMPLICIT_TYPE_CONVERSION();
+};
+
+}  // namespace mojo
+
+#endif  // MOJO_SERVICES_VIEW_MANAGER_TYPE_CONVERTERS_H_
diff --git a/mojo/services/view_manager/view_manager_connection.cc b/mojo/services/view_manager/view_manager_connection.cc
index 749f25c..a148027 100644
--- a/mojo/services/view_manager/view_manager_connection.cc
+++ b/mojo/services/view_manager/view_manager_connection.cc
@@ -8,6 +8,7 @@
 #include "mojo/public/cpp/bindings/allocation_scope.h"
 #include "mojo/services/view_manager/node.h"
 #include "mojo/services/view_manager/root_node_manager.h"
+#include "mojo/services/view_manager/type_converters.h"
 #include "mojo/services/view_manager/view.h"
 #include "third_party/skia/include/core/SkBitmap.h"
 #include "ui/aura/window.h"
@@ -18,43 +19,16 @@ namespace view_manager {
 namespace service {
 namespace {
 
-// Implementation of NodeCount(). |count| is the current count.
-void NodeCountImpl(Node* node, size_t* count) {
-  (*count)++;
-  std::vector<Node*> children(node->GetChildren());
-  for (size_t i = 0 ; i < children.size(); ++i)
-    NodeCountImpl(children[i], count);
-}
-
-// Returns the number of descendants of |node|.
-size_t NodeCount(Node* node) {
-  size_t count = 0;
-  if (node)
-    NodeCountImpl(node, &count);
-  return count;
-}
-
-// Converts a Node to an INode, putting the result at |index| in
-// |array_builder|. This then recurses through the children.
-void NodeToINode(Node* node,
-                 Array<INode>::Builder* array_builder,
-                 size_t* index) {
+// Places |node| in |nodes| and recurses through the children.
+void GetDescendants(Node* node, std::vector<Node*>* nodes) {
   if (!node)
     return;
 
-  INode::Builder builder;
-  Node* parent = node->GetParent();
-  builder.set_parent_id(NodeIdToTransportId(parent ? parent->id() : NodeId()));
-  builder.set_node_id(NodeIdToTransportId(node->id()));
-  builder.set_view_id(ViewIdToTransportId(
-                          node->view() ? node->view()->id() : ViewId()));
-  (*array_builder)[*index] = builder.Finish();
+  nodes->push_back(node);
 
   std::vector<Node*> children(node->GetChildren());
-  for (size_t i = 0 ; i < children.size(); ++i) {
-    (*index)++;
-    NodeToINode(children[i], array_builder, index);
-  }
+  for (size_t i = 0 ; i < children.size(); ++i)
+    GetDescendants(children[i], nodes);
 }
 
 }  // namespace
@@ -85,7 +59,12 @@ void ViewManagerConnection::Initialize() {
   DCHECK_EQ(0, id_);  // Should only get Initialize() once.
   id_ = context()->GetAndAdvanceNextConnectionId();
   context()->AddConnection(this);
-  client()->OnConnectionEstablished(id_, context()->next_server_change_id());
+  std::vector<Node*> to_send;
+  GetUnknownNodesFrom(context()->root(), &to_send);
+  AllocationScope allocation_scope;
+  client()->OnConnectionEstablished(id_,
+                                    context()->next_server_change_id(),
+                                    Array<INode>::From(to_send));
 }
 
 Node* ViewManagerConnection::GetNode(const NodeId& id) {
@@ -104,33 +83,62 @@ View* ViewManagerConnection::GetView(const ViewId& id) {
   return context()->GetView(id);
 }
 
-void ViewManagerConnection::NotifyNodeHierarchyChanged(
-    const NodeId& node,
-    const NodeId& new_parent,
-    const NodeId& old_parent,
-    TransportChangeId server_change_id) {
-  client()->OnNodeHierarchyChanged(NodeIdToTransportId(node),
-                                   NodeIdToTransportId(new_parent),
-                                   NodeIdToTransportId(old_parent),
-                                   server_change_id);
+void ViewManagerConnection::ProcessNodeHierarchyChanged(
+    const NodeId& node_id,
+    const NodeId& new_parent_id,
+    const NodeId& old_parent_id,
+    TransportChangeId server_change_id,
+    bool originated_change) {
+  if (originated_change || context()->is_processing_delete_node())
+    return;
+  std::vector<Node*> to_send;
+  if (!ShouldNotifyOnHierarchyChange(node_id, new_parent_id, old_parent_id,
+                                     &to_send)) {
+    if (context()->IsProcessingChange()) {
+      client()->OnServerChangeIdAdvanced(
+          context()->next_server_change_id() + 1);
+    }
+    return;
+  }
+  AllocationScope allocation_scope;
+  client()->OnNodeHierarchyChanged(NodeIdToTransportId(node_id),
+                                   NodeIdToTransportId(new_parent_id),
+                                   NodeIdToTransportId(old_parent_id),
+                                   server_change_id,
+                                   Array<INode>::From(to_send));
 }
 
-void ViewManagerConnection::NotifyNodeViewReplaced(
+void ViewManagerConnection::ProcessNodeViewReplaced(
     const NodeId& node,
     const ViewId& new_view_id,
-    const ViewId& old_view_id) {
+    const ViewId& old_view_id,
+    bool originated_change) {
+  if (originated_change)
+    return;
   client()->OnNodeViewReplaced(NodeIdToTransportId(node),
                                ViewIdToTransportId(new_view_id),
                                ViewIdToTransportId(old_view_id));
 }
 
-void ViewManagerConnection::NotifyNodeDeleted(
+void ViewManagerConnection::ProcessNodeDeleted(
     const NodeId& node,
-    TransportChangeId server_change_id) {
-  client()->OnNodeDeleted(NodeIdToTransportId(node), server_change_id);
+    TransportChangeId server_change_id,
+    bool originated_change) {
+  const bool in_known = known_nodes_.erase(NodeIdToTransportId(node)) > 0;
+
+  if (originated_change)
+    return;
+
+  if (in_known)
+    client()->OnNodeDeleted(NodeIdToTransportId(node), server_change_id);
+  else if (context()->IsProcessingChange())
+    client()->OnServerChangeIdAdvanced(context()->next_server_change_id() + 1);
 }
 
-void ViewManagerConnection::NotifyViewDeleted(const ViewId& view) {
+void ViewManagerConnection::ProcessViewDeleted(const ViewId& view,
+                                               bool originated_change) {
+  if (originated_change)
+    return;
   client()->OnViewDeleted(ViewIdToTransportId(view));
 }
 
@@ -141,7 +149,8 @@ bool ViewManagerConnection::DeleteNodeImpl(ViewManagerConnection* source,
   if (!node)
     return false;
   RootNodeManager::ScopedChange change(
-      source, context(), RootNodeManager::CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID);
+      source, context(), RootNodeManager::CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID,
+      true);
   if (node->GetParent())
     node->GetParent()->Remove(node);
   std::vector<Node*> children(node->GetChildren());
@@ -151,7 +160,7 @@ bool ViewManagerConnection::DeleteNodeImpl(ViewManagerConnection* source,
   node_map_.erase(node_id.node_id);
   delete node;
   node = NULL;
-  context()->NotifyNodeDeleted(node_id);
+  context()->ProcessNodeDeleted(node_id);
   return true;
 }
 
@@ -163,7 +172,7 @@ bool ViewManagerConnection::DeleteViewImpl(ViewManagerConnection* source,
     return false;
   RootNodeManager::ScopedChange change(
       source, context(),
-      RootNodeManager::CHANGE_TYPE_DONT_ADVANCE_SERVER_CHANGE_ID);
+      RootNodeManager::CHANGE_TYPE_DONT_ADVANCE_SERVER_CHANGE_ID, false);
   if (view->node())
     view->node()->SetView(NULL);
   view_map_.erase(view_id.view_id);
@@ -171,7 +180,7 @@ bool ViewManagerConnection::DeleteViewImpl(ViewManagerConnection* source,
   // valid.
   const ViewId view_id_copy(view_id);
   delete view;
-  context()->NotifyViewDeleted(view_id_copy);
+  context()->ProcessViewDeleted(view_id_copy);
   return true;
 }
 
@@ -185,11 +194,56 @@ bool ViewManagerConnection::SetViewImpl(const NodeId& node_id,
     return false;
   RootNodeManager::ScopedChange change(
       this, context(),
-      RootNodeManager::CHANGE_TYPE_DONT_ADVANCE_SERVER_CHANGE_ID);
+      RootNodeManager::CHANGE_TYPE_DONT_ADVANCE_SERVER_CHANGE_ID, false);
   node->SetView(view);
   return true;
 }
 
+void ViewManagerConnection::GetUnknownNodesFrom(
+    Node* node,
+    std::vector<Node*>* nodes) {
+  const TransportNodeId transport_id = NodeIdToTransportId(node->id());
+  if (known_nodes_.count(transport_id) == 1)
+    return;
+  nodes->push_back(node);
+  known_nodes_.insert(transport_id);
+  std::vector<Node*> children(node->GetChildren());
+  for (size_t i = 0 ; i < children.size(); ++i)
+    GetUnknownNodesFrom(children[i], nodes);
+}
+
+bool ViewManagerConnection::ShouldNotifyOnHierarchyChange(
+    const NodeId& node_id,
+    const NodeId& new_parent_id,
+    const NodeId& old_parent_id,
+    std::vector<Node*>* to_send) {
+  Node* new_parent = GetNode(new_parent_id);
+  if (new_parent) {
+    // On getting a new parent we may need to communicate new nodes to the
+    // client. We do that in the following cases:
+    // . New parent is a descendant of the root. In this case the client already
+    //   knows all ancestors, so we only have to communicate descendants of node
+    //   the client doesn't know about.
+    // . If the client knew about the parent, we have to do the same.
+    // . If the client knows about the node and is added to a tree the client
+    //   doesn't know about we have to communicate from the root down (the
+    //   client is learning about a new root).
+    if (context()->root()->Contains(new_parent) ||
+        known_nodes_.count(NodeIdToTransportId(new_parent_id))) {
+      GetUnknownNodesFrom(GetNode(node_id), to_send);
+      return true;
+    }
+    // If parent wasn't known we have to communicate from the root down.
+    if (known_nodes_.count(NodeIdToTransportId(node_id))) {
+      GetUnknownNodesFrom(new_parent->GetRoot(), to_send);
+      return true;
+    }
+  }
+  // Otherwise only communicate the change if the node was known. We shouldn't
+  // need to communicate any nodes on a remove.
+  return known_nodes_.count(NodeIdToTransportId(node_id));
+}
+
 void ViewManagerConnection::CreateNode(
     TransportNodeId transport_node_id,
     const Callback<void(bool)>& callback) {
@@ -206,6 +260,7 @@ void ViewManagerConnection::CreateNode(
 void ViewManagerConnection::DeleteNode(
     TransportNodeId transport_node_id,
     const Callback<void(bool)>& callback) {
+  AllocationScope allocation_scope;
   const NodeId node_id(NodeIdFromTransportId(transport_node_id));
   ViewManagerConnection* connection = context()->GetConnection(
       node_id.connection_id);
@@ -227,7 +282,7 @@ void ViewManagerConnection::AddNode(
       success = true;
       RootNodeManager::ScopedChange change(
           this, context(),
-          RootNodeManager::CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID);
+          RootNodeManager::CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID, false);
       parent->Add(child);
     }
   }
@@ -245,7 +300,7 @@ void ViewManagerConnection::RemoveNodeFromParent(
       success = true;
       RootNodeManager::ScopedChange change(
           this, context(),
-          RootNodeManager::CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID);
+          RootNodeManager::CHANGE_TYPE_ADVANCE_SERVER_CHANGE_ID, false);
       node->GetParent()->Remove(node);
     }
   }
@@ -257,12 +312,11 @@ void ViewManagerConnection::GetNodeTree(
     const Callback<void(Array<INode>)>& callback) {
   AllocationScope allocation_scope;
   Node* node = GetNode(NodeIdFromTransportId(node_id));
-  Array<INode>::Builder array_builder(NodeCount(node));
-  {
-    size_t index = 0;
-    NodeToINode(node, &array_builder, &index);
-  }
-  callback.Run(array_builder.Finish());
+  std::vector<Node*> nodes;
+  GetDescendants(node, &nodes);
+  for (size_t i = 0; i < nodes.size(); ++i)
+    known_nodes_.insert(NodeIdToTransportId(nodes[i]->id()));
+  callback.Run(Array<INode>::From(nodes));
 }
 
 void ViewManagerConnection::CreateView(
@@ -316,13 +370,13 @@ void ViewManagerConnection::SetViewContents(
 void ViewManagerConnection::OnNodeHierarchyChanged(const NodeId& node,
                                                    const NodeId& new_parent,
                                                    const NodeId& old_parent) {
-  context()->NotifyNodeHierarchyChanged(node, new_parent, old_parent);
+  context()->ProcessNodeHierarchyChanged(node, new_parent, old_parent);
 }
 
 void ViewManagerConnection::OnNodeViewReplaced(const NodeId& node,
                                                const ViewId& new_view_id,
                                                const ViewId& old_view_id) {
-  context()->NotifyNodeViewReplaced(node, new_view_id, old_view_id);
+  context()->ProcessNodeViewReplaced(node, new_view_id, old_view_id);
 }
 
 }  // namespace service
diff --git a/mojo/services/view_manager/view_manager_connection.h b/mojo/services/view_manager/view_manager_connection.h
index 87997d1..b3fa8d7 100644
--- a/mojo/services/view_manager/view_manager_connection.h
+++ b/mojo/services/view_manager/view_manager_connection.h
@@ -6,9 +6,11 @@
 #define MOJO_SERVICES_VIEW_MANAGER_VIEW_MANAGER_CONNECTION_H_
 
 #include <set>
+#include <vector>
 
 #include "base/basictypes.h"
 #include "base/compiler_specific.h"
+#include "base/containers/hash_tables.h"
 #include "mojo/public/cpp/shell/service.h"
 #include "mojo/services/public/interfaces/view_manager/view_manager.mojom.h"
 #include "mojo/services/view_manager/ids.h"
@@ -50,21 +52,28 @@ class MOJO_VIEW_MANAGER_EXPORT ViewManagerConnection
   // Returns the View with the specified id.
   View* GetView(const ViewId& id);
 
-  // Notifies the client of a hierarchy change.
-  void NotifyNodeHierarchyChanged(const NodeId& node,
-                                  const NodeId& new_parent,
-                                  const NodeId& old_parent,
-                                  TransportChangeId server_change_id);
-  void NotifyNodeViewReplaced(const NodeId& node,
-                              const ViewId& new_view_id,
-                              const ViewId& old_view_id);
-  void NotifyNodeDeleted(const NodeId& node,
-                         TransportChangeId server_change_id);
-  void NotifyViewDeleted(const ViewId& view);
+  // The following methods are invoked after the corresponding change has been
+  // processed. They do the appropriate bookkeeping and update the client as
+  // necessary.
+  // TODO(sky): convert these to take Node*s.
+  void ProcessNodeHierarchyChanged(const NodeId& node_id,
+                                   const NodeId& new_parent_id,
+                                   const NodeId& old_parent_id,
+                                   TransportChangeId server_change_id,
+                                   bool originated_change);
+  void ProcessNodeViewReplaced(const NodeId& node,
+                               const ViewId& new_view_id,
+                               const ViewId& old_view_id,
+                               bool originated_change);
+  void ProcessNodeDeleted(const NodeId& node,
+                          TransportChangeId server_change_id,
+                          bool originated_change);
+  void ProcessViewDeleted(const ViewId& view, bool originated_change);
 
  private:
   typedef std::map<TransportConnectionSpecificNodeId, Node*> NodeMap;
   typedef std::map<TransportConnectionSpecificViewId, View*> ViewMap;
+  typedef base::hash_set<TransportNodeId> NodeIdSet;
 
   // Deletes a node owned by this connection. Returns true on success. |source|
   // is the connection that originated the change.
@@ -77,6 +86,18 @@ class MOJO_VIEW_MANAGER_EXPORT ViewManagerConnection
   // Sets the view associated with a node.
   bool SetViewImpl(const NodeId& node_id, const ViewId& view_id);
 
+  // If |node| is known (in |known_nodes_|) does nothing. Otherwise adds |node|
+  // to |nodes|, marks |node| as known and recurses.
+  void GetUnknownNodesFrom(Node* node, std::vector<Node*>* nodes);
+
+  // Returns true if notification should be sent of a hierarchy change. If true
+  // is returned, any nodes that need to be sent to the client are added to
+  // |to_send|.
+  bool ShouldNotifyOnHierarchyChange(const NodeId& node_id,
+                                     const NodeId& new_parent_id,
+                                     const NodeId& old_parent_id,
+                                     std::vector<Node*>* to_send);
+
   // Overridden from IViewManager:
   virtual void CreateNode(TransportNodeId transport_node_id,
                           const Callback<void(bool)>& callback) OVERRIDE;
@@ -120,6 +141,9 @@ class MOJO_VIEW_MANAGER_EXPORT ViewManagerConnection
 
   ViewMap view_map_;
 
+  // The set of nodes that has been communicated to the client.
+  NodeIdSet known_nodes_;
+
   DISALLOW_COPY_AND_ASSIGN(ViewManagerConnection);
 };
 
diff --git a/mojo/services/view_manager/view_manager_connection_unittest.cc b/mojo/services/view_manager/view_manager_connection_unittest.cc
index c1f4d33..385fb05 100644
--- a/mojo/services/view_manager/view_manager_connection_unittest.cc
+++ b/mojo/services/view_manager/view_manager_connection_unittest.cc
@@ -62,10 +62,8 @@ struct TestNode {
   TransportNodeId view_id;
 };
 
-// Callback that results in a vector of INodes. The INodes are converted to
-// TestNodes.
-void INodesCallback(std::vector<TestNode>* test_nodes,
-                    const mojo::Array<INode>& data) {
+void INodesToTestNodes(const mojo::Array<INode>& data,
+                       std::vector<TestNode>* test_nodes) {
   for (size_t i = 0; i < data.size(); ++i) {
     TestNode node;
     node.parent_id = data[i].parent_id();
@@ -73,6 +71,13 @@ void INodesCallback(std::vector<TestNode>* test_nodes,
     node.view_id = data[i].view_id();
     test_nodes->push_back(node);
   }
+}
+
+// Callback that results in a vector of INodes. The INodes are converted to
+// TestNodes.
+void INodesCallback(std::vector<TestNode>* test_nodes,
+                    const mojo::Array<INode>& data) {
+  INodesToTestNodes(data, test_nodes);
   current_run_loop->Quit();
 }
 
@@ -180,6 +185,12 @@ class ViewManagerClientImpl : public IViewManagerClient {
   TransportChangeId next_server_change_id() const {
     return next_server_change_id_;
   }
+  const std::vector<TestNode>& initial_nodes() const {
+    return initial_nodes_;
+  }
+  const std::vector<TestNode>& hierarchy_changed_nodes() const {
+    return hierarchy_changed_nodes_;
+  }
 
   Changes GetAndClearChanges() {
     Changes changes;
@@ -203,17 +214,28 @@ class ViewManagerClientImpl : public IViewManagerClient {
   // IViewManagerClient overrides:
   virtual void OnConnectionEstablished(
       TransportConnectionId connection_id,
-      TransportChangeId next_server_change_id) OVERRIDE {
+      TransportChangeId next_server_change_id,
+      const mojo::Array<INode>& nodes) OVERRIDE {
     id_ = connection_id;
     next_server_change_id_ = next_server_change_id;
+    INodesToTestNodes(nodes, &initial_nodes_);
     if (current_run_loop)
       current_run_loop->Quit();
   }
+  virtual void OnServerChangeIdAdvanced(
+      uint32_t next_server_change_id) OVERRIDE {
+    changes_.push_back(
+        base::StringPrintf(
+            "ServerChangeIdAdvanced %d",
+            static_cast<int>(next_server_change_id)));
+    QuitIfNecessary();
+  }
   virtual void OnNodeHierarchyChanged(
       TransportNodeId node,
       TransportNodeId new_parent,
       TransportNodeId old_parent,
-      TransportChangeId server_change_id) OVERRIDE {
+      TransportChangeId server_change_id,
+      const mojo::Array<INode>& nodes) OVERRIDE {
     changes_.push_back(
         base::StringPrintf(
             "HierarchyChanged change_id=%d node=%s new_parent=%s old_parent=%s",
@@ -221,6 +243,8 @@ class ViewManagerClientImpl : public IViewManagerClient {
             NodeIdToString(node).c_str(),
             NodeIdToString(new_parent).c_str(),
             NodeIdToString(old_parent).c_str()));
+    hierarchy_changed_nodes_.clear();
+    INodesToTestNodes(nodes, &hierarchy_changed_nodes_);
     QuitIfNecessary();
   }
   virtual void OnNodeDeleted(TransportNodeId node,
@@ -264,6 +288,12 @@ class ViewManagerClientImpl : public IViewManagerClient {
 
   Changes changes_;
 
+  // Set of nodes sent when connection created.
+  std::vector<TestNode> initial_nodes_;
+
+  // Nodes sent from last OnNodeHierarchyChanged.
+  std::vector<TestNode> hierarchy_changed_nodes_;
+
   DISALLOW_COPY_AND_ASSIGN(ViewManagerClientImpl);
 };
 
@@ -361,9 +391,7 @@ TEST_F(ViewManagerConnectionTest, AddRemoveNotify) {
     client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(1u, changes.size());
-    EXPECT_EQ(
-        "HierarchyChanged change_id=1 node=1,2 new_parent=1,1 old_parent=null",
-        changes[0]);
+    EXPECT_EQ("ServerChangeIdAdvanced 2", changes[0]);
   }
 
   // Remove 2 from its parent.
@@ -378,9 +406,7 @@ TEST_F(ViewManagerConnectionTest, AddRemoveNotify) {
     client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(1u, changes.size());
-    EXPECT_EQ(
-        "HierarchyChanged change_id=2 node=1,2 new_parent=null old_parent=1,1",
-        changes[0]);
+    EXPECT_EQ("ServerChangeIdAdvanced 3", changes[0]);
   }
 }
 
@@ -407,9 +433,7 @@ TEST_F(ViewManagerConnectionTest, AddNodeWithNoChange) {
     client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(1u, changes.size());
-    EXPECT_EQ(
-        "HierarchyChanged change_id=1 node=1,2 new_parent=1,1 old_parent=null",
-        changes[0]);
+    EXPECT_EQ("ServerChangeIdAdvanced 2", changes[0]);
   }
 
   // Try again, this should fail.
@@ -447,9 +471,7 @@ TEST_F(ViewManagerConnectionTest, AddAncestorFails) {
     client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(1u, changes.size());
-    EXPECT_EQ(
-        "HierarchyChanged change_id=1 node=1,2 new_parent=1,1 old_parent=null",
-        changes[0]);
+    EXPECT_EQ("ServerChangeIdAdvanced 2", changes[0]);
   }
 
   // Try to make 1 a child of 2, this should fail since 1 is an ancestor of 2.
@@ -504,9 +526,7 @@ TEST_F(ViewManagerConnectionTest, AddToRoot) {
     client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(1u, changes.size());
-    EXPECT_EQ(
-        "HierarchyChanged change_id=1 node=1,3 new_parent=1,21 old_parent=null",
-        changes[0]);
+    EXPECT_EQ("ServerChangeIdAdvanced 2", changes[0]);
   }
 
   // Make 21 a child of the root.
@@ -528,6 +548,206 @@ TEST_F(ViewManagerConnectionTest, AddToRoot) {
   }
 }
 
+// Verifies adding to root sends right notifications.
+TEST_F(ViewManagerConnectionTest, NodeHierarchyChangedNodes) {
+  // Create nodes 1 and 11 with 1 parented to the root and 11 a child of 1.
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 1));
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 11));
+
+  // Make 11 a child of 1.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(client_.id(), 1),
+                        CreateNodeId(client_.id(), 11),
+                        1));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+  }
+
+  EstablishSecondConnection();
+
+  // Make 1 a child of the root.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(0, 1),
+                        CreateNodeId(client_.id(), 1),
+                        2));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+
+    // Client 2 should get a hierarchy change that includes the new nodes as it
+    // has not yet seen them.
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes(client2_.GetAndClearChanges());
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ(
+        "HierarchyChanged change_id=2 node=1,1 new_parent=0,1 old_parent=null",
+        changes[0]);
+    const std::vector<TestNode>& nodes(client2_.hierarchy_changed_nodes());
+    ASSERT_EQ(2u, nodes.size());
+    EXPECT_EQ("node=1,1 parent=0,1 view=null", nodes[0].ToString());
+    EXPECT_EQ("node=1,11 parent=1,1 view=null", nodes[1].ToString());
+  }
+
+  // Remove 1 from the root.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(RemoveNodeFromParent(view_manager_.get(),
+                                     CreateNodeId(client_.id(), 1),
+                                     3));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes(client2_.GetAndClearChanges());
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ(
+        "HierarchyChanged change_id=3 node=1,1 new_parent=null old_parent=0,1",
+        changes[0]);
+  }
+
+  // Create another node, 111, parent it to 11.
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 111));
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(client_.id(), 11),
+                        CreateNodeId(client_.id(), 111),
+                        4));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes(client2_.GetAndClearChanges());
+    ASSERT_EQ(1u, changes.size());
+    // Even though 11 isn't attached to the root client 2 is still notified of
+    // the change because it was told about 11.
+    EXPECT_EQ(
+        "HierarchyChanged change_id=4 node=1,111 new_parent=1,11 "
+        "old_parent=null", changes[0]);
+    const std::vector<TestNode>& nodes(client2_.hierarchy_changed_nodes());
+    ASSERT_EQ(1u, nodes.size());
+    EXPECT_EQ("node=1,111 parent=1,11 view=null", nodes[0].ToString());
+  }
+
+  // Reattach 1 to the root.
+  {
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(0, 1),
+                        CreateNodeId(client_.id(), 1),
+                        5));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes = client2_.GetAndClearChanges();
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ(
+        "HierarchyChanged change_id=5 node=1,1 new_parent=0,1 old_parent=null",
+        changes[0]);
+    ASSERT_TRUE(client2_.hierarchy_changed_nodes().empty());
+  }
+}
+
+TEST_F(ViewManagerConnectionTest, NodeHierarchyChangedAddingKnownToUnknown) {
+  // Create the following structure: root -> 1 -> 11 and 2->21 (2 has no
+  // parent).
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 1));
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 11));
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 2));
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 21));
+
+  // Set up the hierarchy.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(0, 1),
+                        CreateNodeId(client_.id(), 1),
+                        1));
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(client_.id(), 1),
+                        CreateNodeId(client_.id(), 11),
+                        2));
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(client_.id(), 2),
+                        CreateNodeId(client_.id(), 21),
+                        3));
+  }
+
+  EstablishSecondConnection();
+
+  // Remove 11.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(RemoveNodeFromParent(view_manager_.get(),
+                                     CreateNodeId(client_.id(), 11),
+                                     4));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes(client2_.GetAndClearChanges());
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ(
+        "HierarchyChanged change_id=4 node=1,11 new_parent=null old_parent=1,1",
+        changes[0]);
+    EXPECT_TRUE(client2_.hierarchy_changed_nodes().empty());
+  }
+
+  // Add 11 to 21. As client2 knows about 11 it should receive the new
+  // hierarchy.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(client_.id(), 21),
+                        CreateNodeId(client_.id(), 11),
+                        5));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes(client2_.GetAndClearChanges());
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ(
+        "HierarchyChanged change_id=5 node=1,11 new_parent=1,21 "
+        "old_parent=null", changes[0]);
+    const std::vector<TestNode>& nodes(client2_.hierarchy_changed_nodes());
+    ASSERT_EQ(2u, nodes.size());
+    EXPECT_EQ("node=1,2 parent=null view=null", nodes[0].ToString());
+    EXPECT_EQ("node=1,21 parent=1,2 view=null", nodes[1].ToString());
+  }
+}
+
+// Verifies connection on told descendants of the root when connecting.
+TEST_F(ViewManagerConnectionTest, GetInitialNodesOnInit) {
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 21));
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 3));
+  EXPECT_TRUE(client_.GetAndClearChanges().empty());
+
+  // Make 3 a child of 21.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(client_.id(), 21),
+                        CreateNodeId(client_.id(), 3),
+                        1));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+  }
+
+  // Make 21 a child of the root.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(0, 1),
+                        CreateNodeId(client_.id(), 21),
+                        2));
+    ASSERT_TRUE(client_.GetAndClearChanges().empty());
+  }
+
+  EstablishSecondConnection();
+  // Should get notification of children of the root.
+  const std::vector<TestNode>& nodes(client2_.initial_nodes());
+  ASSERT_EQ(3u, nodes.size());
+  EXPECT_EQ("node=0,1 parent=null view=null", nodes[0].ToString());
+  EXPECT_EQ("node=1,21 parent=0,1 view=null", nodes[1].ToString());
+  EXPECT_EQ("node=1,3 parent=1,21 view=null", nodes[2].ToString());
+}
+
 // Verifies DeleteNode works.
 TEST_F(ViewManagerConnectionTest, DeleteNode) {
   ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 1));
@@ -550,9 +770,7 @@ TEST_F(ViewManagerConnectionTest, DeleteNode) {
     client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(1u, changes.size());
-    EXPECT_EQ(
-        "HierarchyChanged change_id=1 node=1,2 new_parent=1,1 old_parent=null",
-        changes[0]);
+    EXPECT_EQ("ServerChangeIdAdvanced 2", changes[0]);
   }
 
   // Add 1 to the root
@@ -573,24 +791,78 @@ TEST_F(ViewManagerConnectionTest, DeleteNode) {
         changes[0]);
   }
 
-  // Delete 1. Deleting 1 sends out notification of a removal for both nodes (1
-  // and 2).
+  // Delete 1.
   {
     AllocationScope scope;
     ASSERT_TRUE(DeleteNode(view_manager_.get(), CreateNodeId(client_.id(), 1)));
     Changes changes(client_.GetAndClearChanges());
     ASSERT_TRUE(changes.empty());
 
-    client2_.DoRunLoopUntilChangesCount(3);
+    client2_.DoRunLoopUntilChangesCount(1);
     changes = client2_.GetAndClearChanges();
-    ASSERT_EQ(3u, changes.size());
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ("NodeDeleted change_id=3 node=1,1", changes[0]);
+  }
+}
+
+// Verifies if a node was deleted and then reused that other clients are
+// properly notified.
+TEST_F(ViewManagerConnectionTest, ReusedDeletedId) {
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 1));
+  EXPECT_TRUE(client_.GetAndClearChanges().empty());
+
+  EstablishSecondConnection();
+
+  // Make 1 a child of the root.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(0, 1),
+                        CreateNodeId(client_.id(), 1),
+                        1));
+    EXPECT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes = client2_.GetAndClearChanges();
     EXPECT_EQ(
-        "HierarchyChanged change_id=3 node=1,1 new_parent=null old_parent=0,1",
+        "HierarchyChanged change_id=1 node=1,1 new_parent=0,1 old_parent=null",
         changes[0]);
+    const std::vector<TestNode>& nodes(client2_.hierarchy_changed_nodes());
+    ASSERT_EQ(1u, nodes.size());
+    EXPECT_EQ("node=1,1 parent=0,1 view=null", nodes[0].ToString());
+  }
+
+  // Delete 1.
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(DeleteNode(view_manager_.get(), CreateNodeId(client_.id(), 1)));
+    EXPECT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes = client2_.GetAndClearChanges();
+    ASSERT_EQ(1u, changes.size());
+    EXPECT_EQ("NodeDeleted change_id=2 node=1,1", changes[0]);
+  }
+
+  // Create 1 again, and add it back to the root. Should get the same
+  // notification.
+  ASSERT_TRUE(CreateNode(view_manager_.get(), 1, 1));
+  {
+    AllocationScope scope;
+    ASSERT_TRUE(AddNode(view_manager_.get(),
+                        CreateNodeId(0, 1),
+                        CreateNodeId(client_.id(), 1),
+                        3));
+    EXPECT_TRUE(client_.GetAndClearChanges().empty());
+
+    client2_.DoRunLoopUntilChangesCount(1);
+    Changes changes = client2_.GetAndClearChanges();
     EXPECT_EQ(
-        "HierarchyChanged change_id=3 node=1,2 new_parent=null old_parent=1,1",
-        changes[1]);
-    EXPECT_EQ("NodeDeleted change_id=3 node=1,1", changes[2]);
+        "HierarchyChanged change_id=3 node=1,1 new_parent=0,1 old_parent=null",
+        changes[0]);
+    const std::vector<TestNode>& nodes(client2_.hierarchy_changed_nodes());
+    ASSERT_EQ(1u, nodes.size());
+    EXPECT_EQ("node=1,1 parent=0,1 view=null", nodes[0].ToString());
   }
 }
 
@@ -664,9 +936,17 @@ TEST_F(ViewManagerConnectionTest, DeleteNodeWithView) {
     changes = client2_.GetAndClearChanges();
     ASSERT_EQ(2u, changes.size());
     EXPECT_EQ("ViewReplaced node=1,1 new_view=null old_view=1,11", changes[0]);
-    EXPECT_EQ("NodeDeleted change_id=1 node=1,1", changes[1]);
+    EXPECT_EQ("ServerChangeIdAdvanced 2", changes[1]);
   }
 
+  // Parent 2 to the root.
+  ASSERT_TRUE(AddNode(view_manager_.get(),
+                      CreateNodeId(0, 1),
+                      CreateNodeId(client_.id(), 2),
+                      2));
+  client2_.DoRunLoopUntilChangesCount(1);
+  client2_.GetAndClearChanges();
+
   // Set view 11 on node 2.
   {
     ASSERT_TRUE(SetView(view_manager_.get(),
@@ -680,6 +960,19 @@ TEST_F(ViewManagerConnectionTest, DeleteNodeWithView) {
     ASSERT_EQ(1u, changes.size());
     EXPECT_EQ("ViewReplaced node=1,2 new_view=1,11 old_view=null", changes[0]);
   }
+
+  // Delete node.
+  {
+    ASSERT_TRUE(DeleteNode(view_manager_.get(), CreateNodeId(client_.id(), 2)));
+    Changes changes(client_.GetAndClearChanges());
+    ASSERT_TRUE(changes.empty());
+
+    client2_.DoRunLoopUntilChangesCount(2);
+    changes = client2_.GetAndClearChanges();
+    ASSERT_EQ(2u, changes.size());
+    EXPECT_EQ("ViewReplaced node=1,2 new_view=null old_view=1,11", changes[0]);
+    EXPECT_EQ("NodeDeleted change_id=3 node=1,2", changes[1]);
+  }
 }
 
 // Sets view from one connection on another.