Clone children of FrameNavigationEntries for in-page navigations.

content/browser/frame_host/navigation_entry_impl.cc

 // Copyright 2013 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 "content/browser/frame_host/navigation_entry_impl.h"
 
 #include <stddef.h>
 
 #include <queue>
 #include <utility>
@@ skipping 98 matching lines @@
   if (is_root_tree_node)
     return frame_tree_node->IsMainFrame();
 
   // Otherwise check the unique name for subframes.
   return !frame_tree_node->IsMainFrame() &&
          frame_tree_node->unique_name() == frame_entry->frame_unique_name();
 }
 
 std::unique_ptr<NavigationEntryImpl::TreeNode>
 NavigationEntryImpl::TreeNode::CloneAndReplace(
-    FrameTreeNode* frame_tree_node,
     FrameNavigationEntry* frame_navigation_entry,
+    bool clone_children_of_target,
+    FrameTreeNode* target_frame_tree_node,
+    FrameTreeNode* current_frame_tree_node,
     bool is_root_tree_node) const {
-  if (frame_tree_node && MatchesFrame(frame_tree_node, is_root_tree_node)) {
-    // Replace this node in the cloned tree and prune its children.
-    return base::WrapUnique(
-        new NavigationEntryImpl::TreeNode(frame_navigation_entry));
-  }
+  // Clone this TreeNode, possibly replacing its FrameNavigationEntry.
+  bool is_target_frame =
+      target_frame_tree_node &&
+      MatchesFrame(target_frame_tree_node, is_root_tree_node);
+  std::unique_ptr<NavigationEntryImpl::TreeNode> copy(
+      new NavigationEntryImpl::TreeNode(
+          is_target_frame ? frame_navigation_entry : frame_entry->Clone()));
 
-  // Clone the tree using a copy of the FrameNavigationEntry, without sharing.
-  // TODO(creis): Share FNEs unless it's for another tab.
-  std::unique_ptr<NavigationEntryImpl::TreeNode> copy(
-      new NavigationEntryImpl::TreeNode(frame_entry->Clone()));
+  // Recursively clone the children if needed.
+  if (!is_target_frame || clone_children_of_target) {
+    for (size_t i = 0; i < children.size(); i++) {
+      NavigationEntryImpl::TreeNode* child = children[i];
 
-  // Recursively clone the children.
-  for (auto* child : children) {
-    copy->children.push_back(
-        child->CloneAndReplace(frame_tree_node, frame_navigation_entry, false));
+      // Don't check whether it's still in the tree if |current_frame_tree_node|
+      // is null.
+      if (!current_frame_tree_node) {
+        copy->children.push_back(child->CloneAndReplace(
+            frame_navigation_entry, clone_children_of_target,
+            target_frame_tree_node, nullptr, false));
+        continue;
+      }
+
+      // Otherwise, make sure the frame is still in the tree before cloning it.
+      // This is O(N^2) in the worst case because we need to look up each frame
+      // (and since we want to avoid a map of unique names, which can be very
+      // long).  To partly mitigate this, we add an optimization for the common
+      // case that the two child lists are the same length and are likely in the
+      // same order: we pick the starting offset of the inner loop to get O(N).
+      size_t ftn_child_count = current_frame_tree_node->child_count();
+      for (size_t j = 0; j < ftn_child_count; j++) {
+        size_t index = j;
+        // If the two lists of children are the same length, start looking at
+        // the same index as |child|.
+        if (children.size() == ftn_child_count)
+          index = (i + j) % ftn_child_count;

[Avi (use Gerrit), 2016/07/26 15:03:58]

Cute, and actually decently easy to reason about.

+
+        if (current_frame_tree_node->child_at(index)->unique_name() ==
+            child->frame_entry->frame_unique_name()) {
+          // Found |child| in the tree.  Clone it and break out of inner loop.
+          copy->children.push_back(child->CloneAndReplace(
+              frame_navigation_entry, clone_children_of_target,
+              target_frame_tree_node, current_frame_tree_node->child_at(index),
+              false));
+          break;
+        }
+      }
+    }
   }
 
   return copy;
 }
 
 std::unique_ptr<NavigationEntry> NavigationEntry::Create() {
   return base::WrapUnique(new NavigationEntryImpl());
 }
 
 NavigationEntryImpl* NavigationEntryImpl::FromNavigationEntry(
@@ skipping 362 matching lines @@
     return false;
   *data = iter->second;
   return true;
 }
 
 void NavigationEntryImpl::ClearExtraData(const std::string& key) {
   extra_data_.erase(key);
 }
 
 std::unique_ptr<NavigationEntryImpl> NavigationEntryImpl::Clone() const {
-  return NavigationEntryImpl::CloneAndReplace(nullptr, nullptr);
+  return NavigationEntryImpl::CloneAndReplace(nullptr, false, nullptr, nullptr);
 }
 
 std::unique_ptr<NavigationEntryImpl> NavigationEntryImpl::CloneAndReplace(
-    FrameTreeNode* frame_tree_node,
-    FrameNavigationEntry* frame_navigation_entry) const {
+    FrameNavigationEntry* frame_navigation_entry,
+    bool clone_children_of_target,
+    FrameTreeNode* target_frame_tree_node,
+    FrameTreeNode* root_frame_tree_node) const {
   std::unique_ptr<NavigationEntryImpl> copy =
       base::WrapUnique(new NavigationEntryImpl());
 
   // TODO(creis): Only share the same FrameNavigationEntries if cloning within
   // the same tab.
   copy->frame_tree_ = frame_tree_->CloneAndReplace(
-      frame_tree_node, frame_navigation_entry, true);
+      frame_navigation_entry, clone_children_of_target, target_frame_tree_node,
+      root_frame_tree_node, true);
 
   // Copy most state over, unless cleared in ResetForCommit.
   // Don't copy unique_id_, otherwise it won't be unique.
   copy->bindings_ = bindings_;
   copy->page_type_ = page_type_;
   copy->virtual_url_ = virtual_url_;
   copy->update_virtual_url_with_url_ = update_virtual_url_with_url_;
   copy->title_ = title_;
   copy->favicon_ = favicon_;
   copy->page_id_ = page_id_;
@@ skipping 232 matching lines @@
       return node;
 
     // Enqueue any children and keep looking.
     for (auto* child : node->children)
       work_queue.push(child);
   }
   return nullptr;
 }
 
 }  // namespace content