Better remove HistoryNodes

Clean up some technical debt related to removing children. Currently we do an expensive traversal to clear the unique name and frame id maps of stale references to children being removed. Stash some state on HistoryNodes to make it faster and more readable.

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

Cr-Commit-Position: refs/heads/master@{#332272}

8 files changed, 73 insertions, 106 deletions

diff --git a/content/common/page_state_serialization.cc b/content/common/page_state_serialization.cc
index cff62c3..77e2abf 100644
--- a/content/common/page_state_serialization.cc
+++ b/content/common/page_state_serialization.cc
@@ -195,12 +195,13 @@ struct SerializeObject {
 //     viewport within the unzoomed main frame.
 // 21: Add frame sequence number.
 // 22: Add scroll restoration type.
+// 23: Remove frame sequence number, there are easier ways.
 //
 // NOTE: If the version is -1, then the pickle contains only a URL string.
 // See ReadPageState.
 //
 const int kMinVersion = 11;
-const int kCurrentVersion = 22;
+const int kCurrentVersion = 23;
 
 // A bunch of convenience functions to read/write to SerializeObjects.  The
 // de-serializers assume the input data will be in the correct format and fall
@@ -493,7 +494,6 @@ void WriteFrameState(
   WriteReal(state.page_scale_factor, obj);
   WriteInteger64(state.item_sequence_number, obj);
   WriteInteger64(state.document_sequence_number, obj);
-  WriteInteger64(state.frame_sequence_number, obj);
   WriteInteger(state.referrer_policy, obj);
   WriteReal(state.pinch_viewport_scroll_offset.x(), obj);
   WriteReal(state.pinch_viewport_scroll_offset.y(), obj);
@@ -552,8 +552,8 @@ void ReadFrameState(SerializeObject* obj, bool is_top,
   state->page_scale_factor = ReadReal(obj);
   state->item_sequence_number = ReadInteger64(obj);
   state->document_sequence_number = ReadInteger64(obj);
-  if (obj->version >= 21)
-    state->frame_sequence_number = ReadInteger64(obj);
+  if (obj->version >= 21 && obj->version < 23)
+    ReadInteger64(obj); // Skip obsolete frame sequence number.
 
   if (obj->version >= 17 && obj->version < 19)
     ReadInteger64(obj); // Skip obsolete target frame id number.
@@ -685,7 +685,6 @@ ExplodedFrameState::ExplodedFrameState()
     : scroll_restoration_type(blink::WebHistoryScrollRestorationAuto),
       item_sequence_number(0),
       document_sequence_number(0),
-      frame_sequence_number(0),
       page_scale_factor(0.0),
       referrer_policy(blink::WebReferrerPolicyDefault) {
 }
@@ -713,7 +712,6 @@ void ExplodedFrameState::assign(const ExplodedFrameState& other) {
   scroll_offset = other.scroll_offset;
   item_sequence_number = other.item_sequence_number;
   document_sequence_number = other.document_sequence_number;
-  frame_sequence_number = other.frame_sequence_number;
   page_scale_factor = other.page_scale_factor;
   referrer_policy = other.referrer_policy;
   http_body = other.http_body;
diff --git a/content/common/page_state_serialization.h b/content/common/page_state_serialization.h
index 9613a2e..4d60e14 100644
--- a/content/common/page_state_serialization.h
+++ b/content/common/page_state_serialization.h
@@ -54,7 +54,6 @@ struct CONTENT_EXPORT ExplodedFrameState {
   gfx::Point scroll_offset;
   int64 item_sequence_number;
   int64 document_sequence_number;
-  int64 frame_sequence_number;
   double page_scale_factor;
   blink::WebReferrerPolicy referrer_policy;
   ExplodedHttpBody http_body;
diff --git a/content/common/page_state_serialization_unittest.cc b/content/common/page_state_serialization_unittest.cc
index f860b21..9f58c76 100644
--- a/content/common/page_state_serialization_unittest.cc
+++ b/content/common/page_state_serialization_unittest.cc
@@ -106,7 +106,6 @@ class PageStateSerializationTest : public testing::Test {
     frame_state->scroll_offset = gfx::Point(0, 100);
     frame_state->item_sequence_number = 1;
     frame_state->document_sequence_number = 2;
-    frame_state->frame_sequence_number = 3;
     frame_state->page_scale_factor = 2.0;
   }
 
@@ -147,7 +146,6 @@ class PageStateSerializationTest : public testing::Test {
     frame_state->scroll_offset = gfx::Point(42, -42);
     frame_state->item_sequence_number = 123;
     frame_state->document_sequence_number = 456;
-    frame_state->frame_sequence_number = 789;
     frame_state->page_scale_factor = 2.0f;
 
     frame_state->document_state.push_back(
@@ -437,5 +435,9 @@ TEST_F(PageStateSerializationTest, BackwardsCompat_v21) {
   TestBackwardsCompat(21);
 }
 
+TEST_F(PageStateSerializationTest, BackwardsCompat_v22) {
+  TestBackwardsCompat(22);
+}
+
 }  // namespace
 }  // namespace content
diff --git a/content/renderer/history_controller.cc b/content/renderer/history_controller.cc
index f2d3d96..5f53009 100644
--- a/content/renderer/history_controller.cc
+++ b/content/renderer/history_controller.cc
@@ -153,7 +153,7 @@ void HistoryController::UpdateForInitialLoadInChildFrame(
     return;
   if (HistoryEntry::HistoryNode* parent_history_node =
           current_entry_->GetHistoryNodeForFrame(parent)) {
-    parent_history_node->AddChild(item, frame->GetRoutingID());
+    parent_history_node->AddChild(item);
   }
 }
 
@@ -217,8 +217,7 @@ void HistoryController::CreateNewBackForwardItem(
     const WebHistoryItem& new_item,
     bool clone_children_of_target) {
   if (!current_entry_) {
-    current_entry_.reset(
-        new HistoryEntry(new_item, target_frame->GetRoutingID()));
+    current_entry_.reset(new HistoryEntry(new_item));
   } else {
     current_entry_.reset(current_entry_->CloneAndReplace(
         new_item, clone_children_of_target, target_frame, render_view_));
diff --git a/content/renderer/history_entry.cc b/content/renderer/history_entry.cc
index 7686165..efd6fb5 100644
--- a/content/renderer/history_entry.cc
+++ b/content/renderer/history_entry.cc
@@ -44,37 +44,25 @@ using blink::WebHistoryItem;
 
 namespace content {
 
-// Frame routing ids are not safe to serialize, so instead create a mapping
-// from routing ids to frame sequence numbers. The sequence numbers can be
-// benignly serialized with limited risk of collision in a different process.
-// FrameMap is a singleton per-process.
-typedef base::hash_map<uint64_t, uint64_t> FrameMap;
-static FrameMap& GetFrameMap() {
-  CR_DEFINE_STATIC_LOCAL(FrameMap, routing_ids_to_internal_frame_ids, ());
-  return routing_ids_to_internal_frame_ids;
-}
-
 HistoryEntry::HistoryNode* HistoryEntry::HistoryNode::AddChild(
-    const WebHistoryItem& item,
-    int64_t frame_id) {
-  children_->push_back(new HistoryNode(entry_, item, frame_id));
+    const WebHistoryItem& item) {
+  children_->push_back(new HistoryNode(entry_, item));
   return children_->back();
 }
 
 HistoryEntry::HistoryNode* HistoryEntry::HistoryNode::AddChild() {
-  return AddChild(WebHistoryItem(), kInvalidFrameRoutingID);
+  return AddChild(WebHistoryItem());
 }
 
 HistoryEntry::HistoryNode* HistoryEntry::HistoryNode::CloneAndReplace(
-    HistoryEntry* new_entry,
+    const base::WeakPtr<HistoryEntry>& new_entry,
     const WebHistoryItem& new_item,
     bool clone_children_of_target,
     RenderFrameImpl* target_frame,
     RenderFrameImpl* current_frame) {
   bool is_target_frame = target_frame == current_frame;
   const WebHistoryItem& item_for_create = is_target_frame ? new_item : item_;
-  HistoryNode* new_history_node = new HistoryNode(
-      new_entry, item_for_create, current_frame->GetRoutingID());
+  HistoryNode* new_history_node = new HistoryNode(new_entry, item_for_create);
 
   if (is_target_frame && clone_children_of_target && !item_.isNull()) {
     new_history_node->item().setDocumentSequenceNumber(
@@ -108,80 +96,45 @@ HistoryEntry::HistoryNode* HistoryEntry::HistoryNode::CloneAndReplace(
 }
 
 void HistoryEntry::HistoryNode::set_item(const WebHistoryItem& item) {
-  // The previous HistoryItem might not have had a target set, or it might be
-  // different than the current one.
+  DCHECK(!item.isNull());
   entry_->unique_names_to_items_[item.target().utf8()] = this;
-  entry_->frames_to_items_[item.frameSequenceNumber()] = this;
+  unique_names_.push_back(item.target().utf8());
   item_ = item;
 }
 
-HistoryEntry::HistoryNode::HistoryNode(HistoryEntry* entry,
-                                       const WebHistoryItem& item,
-                                       int64_t frame_id)
-    : entry_(entry), item_(item) {
-  if (frame_id != kInvalidFrameRoutingID) {
-    // Each history item is given a frame sequence number on creation.
-    // If we've already mapped this frame id to a sequence number, standardize
-    // this item to that sequence number. Otherwise, map the frame id to this
-    // item's existing sequence number.
-    if (GetFrameMap()[frame_id] == 0)
-        GetFrameMap()[frame_id] = item_.frameSequenceNumber();
-    else if (!item_.isNull())
-        item_.setFrameSequenceNumber(GetFrameMap()[frame_id]);
-    entry_->frames_to_items_[GetFrameMap()[frame_id]] = this;
-  }
-
-  if (!item_.isNull())
-    entry_->unique_names_to_items_[item_.target().utf8()] = this;
+HistoryEntry::HistoryNode::HistoryNode(const base::WeakPtr<HistoryEntry>& entry,
+                                       const WebHistoryItem& item)
+    : entry_(entry) {
+  if (!item.isNull())
+    set_item(item);
   children_.reset(new ScopedVector<HistoryNode>);
 }
 
 HistoryEntry::HistoryNode::~HistoryNode() {
+  if (!entry_ || item_.isNull())
+    return;
+
+  for (std::string name : unique_names_) {
+    if (entry_->unique_names_to_items_[name] == this)
+      entry_->unique_names_to_items_.erase(name);
+  }
 }
 
 void HistoryEntry::HistoryNode::RemoveChildren() {
-  // TODO(japhet): This is inefficient. Figure out a cleaner way to ensure
-  // this HistoryNode isn't cached anywhere.
-  std::vector<uint64_t> frames_to_remove;
-  std::vector<std::string> unique_names_to_remove;
-  for (size_t i = 0; i < children().size(); i++) {
-    children().at(i)->RemoveChildren();
-
-    HistoryEntry::FramesToItems::iterator frames_end =
-        entry_->frames_to_items_.end();
-    HistoryEntry::UniqueNamesToItems::iterator unique_names_end =
-        entry_->unique_names_to_items_.end();
-    for (HistoryEntry::FramesToItems::iterator it =
-             entry_->frames_to_items_.begin();
-         it != frames_end;
-         ++it) {
-      if (it->second == children().at(i))
-        frames_to_remove.push_back(GetFrameMap()[it->first]);
-    }
-    for (HistoryEntry::UniqueNamesToItems::iterator it =
-             entry_->unique_names_to_items_.begin();
-         it != unique_names_end;
-         ++it) {
-      if (it->second == children().at(i))
-        unique_names_to_remove.push_back(it->first);
-    }
-  }
-  for (unsigned i = 0; i < frames_to_remove.size(); i++)
-    entry_->frames_to_items_.erase(frames_to_remove[i]);
-  for (unsigned i = 0; i < unique_names_to_remove.size(); i++)
-    entry_->unique_names_to_items_.erase(unique_names_to_remove[i]);
   children_.reset(new ScopedVector<HistoryNode>);
 }
 
-HistoryEntry::HistoryEntry() {
-  root_.reset(new HistoryNode(this, WebHistoryItem(), kInvalidFrameRoutingID));
+HistoryEntry::HistoryEntry() : weak_ptr_factory_(this) {
+  root_.reset(
+      new HistoryNode(weak_ptr_factory_.GetWeakPtr(), WebHistoryItem()));
 }
 
 HistoryEntry::~HistoryEntry() {
 }
 
-HistoryEntry::HistoryEntry(const WebHistoryItem& root, int64_t frame_id) {
-  root_.reset(new HistoryNode(this, root, frame_id));
+HistoryEntry::HistoryEntry(const WebHistoryItem& root)
+    : weak_ptr_factory_(this) {
+  root_.reset(new HistoryNode(weak_ptr_factory_.GetWeakPtr(), root));
 }
 
 HistoryEntry* HistoryEntry::CloneAndReplace(const WebHistoryItem& new_item,
@@ -190,19 +143,16 @@ HistoryEntry* HistoryEntry::CloneAndReplace(const WebHistoryItem& new_item,
                                             RenderViewImpl* render_view) {
   HistoryEntry* new_entry = new HistoryEntry();
   new_entry->root_.reset(
-      root_->CloneAndReplace(new_entry,
-                             new_item,
-                             clone_children_of_target,
-                             target_frame,
+      root_->CloneAndReplace(new_entry->weak_ptr_factory_.GetWeakPtr(),
+                             new_item, clone_children_of_target, target_frame,
                              render_view->GetMainRenderFrame()));
   return new_entry;
 }
 
 HistoryEntry::HistoryNode* HistoryEntry::GetHistoryNodeForFrame(
     RenderFrameImpl* frame) {
-  if (HistoryNode* history_node =
-          frames_to_items_[GetFrameMap()[frame->GetRoutingID()]])
-    return history_node;
+  if (!frame->GetWebFrame()->parent())
+    return root_history_node();
   return unique_names_to_items_[frame->GetWebFrame()->uniqueName().utf8()];
 }
 
diff --git a/content/renderer/history_entry.h b/content/renderer/history_entry.h
index 62da86a..627419b 100644
--- a/content/renderer/history_entry.h
+++ b/content/renderer/history_entry.h
@@ -38,6 +38,7 @@
 #include "base/containers/hash_tables.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/memory/scoped_vector.h"
+#include "base/memory/weak_ptr.h"
 #include "content/common/content_export.h"
 #include "third_party/WebKit/public/platform/WebURLRequest.h"
 #include "third_party/WebKit/public/web/WebHistoryItem.h"
@@ -56,14 +57,13 @@ class CONTENT_EXPORT HistoryEntry {
  public:
   class HistoryNode {
    public:
-    HistoryNode(HistoryEntry* entry,
-                const blink::WebHistoryItem& item,
-                int64_t frame_id);
+    HistoryNode(const base::WeakPtr<HistoryEntry>& entry,
+                const blink::WebHistoryItem& item);
     ~HistoryNode();
 
-    HistoryNode* AddChild(const blink::WebHistoryItem& item, int64_t frame_id);
+    HistoryNode* AddChild(const blink::WebHistoryItem& item);
     HistoryNode* AddChild();
-    HistoryNode* CloneAndReplace(HistoryEntry* new_entry,
+    HistoryNode* CloneAndReplace(const base::WeakPtr<HistoryEntry>& new_entry,
                                  const blink::WebHistoryItem& new_item,
                                  bool clone_children_of_target,
                                  RenderFrameImpl* target_frame,
@@ -74,12 +74,20 @@ class CONTENT_EXPORT HistoryEntry {
     void RemoveChildren();
 
    private:
-    HistoryEntry* entry_;
+    // When a HistoryEntry is destroyed, it takes all its HistoryNodes with it.
+    // Use a WeakPtr to ensure that HistoryNodes don't try to illegally access
+    // a dying HistoryEntry, or do unnecessary work when the whole entry is
+    // being destroyed.
+    base::WeakPtr<HistoryEntry> entry_;
     scoped_ptr<ScopedVector<HistoryNode> > children_;
     blink::WebHistoryItem item_;
+    // We need to track multiple names because the name of a frame can change
+    // over its lifetime. This allows us to clean up all of the names this node
+    // has ever known by when it is destroyed.
+    std::vector<std::string> unique_names_;
   };
 
-  HistoryEntry(const blink::WebHistoryItem& root, int64_t frame_id);
+  HistoryEntry(const blink::WebHistoryItem& root);
   HistoryEntry();
   ~HistoryEntry();
 
@@ -94,14 +102,12 @@ class CONTENT_EXPORT HistoryEntry {
   HistoryNode* root_history_node() const { return root_.get(); }
 
  private:
-
   scoped_ptr<HistoryNode> root_;
 
-  typedef base::hash_map<uint64_t, HistoryNode*> FramesToItems;
-  FramesToItems frames_to_items_;
-
   typedef base::hash_map<std::string, HistoryNode*> UniqueNamesToItems;
   UniqueNamesToItems unique_names_to_items_;
+
+  base::WeakPtrFactory<HistoryEntry> weak_ptr_factory_;
 };
 
 }  // namespace content
diff --git a/content/renderer/history_serialization.cc b/content/renderer/history_serialization.cc
index 1d14357..5dd704c 100644
--- a/content/renderer/history_serialization.cc
+++ b/content/renderer/history_serialization.cc
@@ -95,8 +95,6 @@ void GenerateFrameStateFromItem(const WebHistoryItem& item,
   state->item_sequence_number = item.itemSequenceNumber();
   state->document_sequence_number =
       item.documentSequenceNumber();
-  state->frame_sequence_number =
-      item.frameSequenceNumber();
   state->page_scale_factor = item.pageScaleFactor();
   ToNullableString16Vector(item.documentState(), &state->document_state);
 
@@ -155,8 +153,6 @@ void RecursivelyGenerateHistoryItem(const ExplodedFrameState& state,
     item.setItemSequenceNumber(state.item_sequence_number);
   if (state.document_sequence_number)
     item.setDocumentSequenceNumber(state.document_sequence_number);
-  if (state.frame_sequence_number)
-    item.setFrameSequenceNumber(state.frame_sequence_number);
 
   item.setHTTPContentType(state.http_body.http_content_type);
   if (!state.http_body.is_null) {
diff --git a/content/test/data/page_state/serialized_v22.dat b/content/test/data/page_state/serialized_v22.dat
new file mode 100644
index 0000000..484187a
--- /dev/null
+++ b/content/test/data/page_state/serialized_v22.dat
@@ -0,0 +1,17 @@
+rAMAABcAAAABAAAAEAAAAGYAaQBsAGUALgB0AHgAdAAoAAAAaAB0AHQAcAA6AC8ALwBjAGgAcgBv
+AG0AaQB1AG0ALgBvAHIAZwAvAAwAAAB0AGEAcgBnAGUAdAAqAAAA1v///yQAAABoAHQAdABwADoA
+LwAvAGcAbwBvAGcAbABlAC4AYwBvAG0ALwAIAAAAYAAAAAoADQA/ACUAIABXAGUAYgBLAGkAdAAg
+AHMAZQByAGkAYQBsAGkAegBlAGQAIABmAG8AcgBtACAAcwB0AGEAdABlACAAdgBlAHIAcwBpAG8A
+bgAgADgAIAAKAA0APQAmABAAAABmAG8AcgBtACAAawBlAHkAAgAAADEAAAAGAAAAZgBvAG8AAAAI
+AAAAZgBpAGwAZQACAAAAMgAAABAAAABmAGkAbABlAC4AdAB4AHQAFgAAAGQAaQBzAHAAbABhAHkA
+TgBhAG0AZQAAAAgAAAAAAAAAAAAAQHsAAAAAAAAAyAEAAAAAAAABAAAACAAAAAAAAAAAAPC/CAAA
+AAAAAAAAAPC/AAAAAAAAAAABAAAAAwAAAAAAAAAQAAAAZmlyc3QgZGF0YSBibG9jawEAAAAQAAAA
+ZgBpAGwAZQAuAHQAeAB0AAAAAAAAAAAA//////////8IAAAAAAAAAAAA+H8AAAAADwAAAGRhdGEg
+dGhlIHNlY29uZAAVAwAAAAAAAAAAAAAOAAAAZgBvAG8ALwBiAGEAcgAAAAEAAAAoAAAAaAB0AHQA
+cAA6AC8ALwBjAGgAcgBvAG0AaQB1AG0ALgBvAHIAZwAvAP////8qAAAA1v///yQAAABoAHQAdABw
+ADoALwAvAGcAbwBvAGcAbABlAC4AYwBvAG0ALwAIAAAAYAAAAAoADQA/ACUAIABXAGUAYgBLAGkA
+dAAgAHMAZQByAGkAYQBsAGkAegBlAGQAIABmAG8AcgBtACAAcwB0AGEAdABlACAAdgBlAHIAcwBp
+AG8AbgAgADgAIAAKAA0APQAmABAAAABmAG8AcgBtACAAawBlAHkAAgAAADEAAAAGAAAAZgBvAG8A
+AAAIAAAAZgBpAGwAZQACAAAAMgAAABAAAABmAGkAbABlAC4AdAB4AHQAFgAAAGQAaQBzAHAAbABh
+AHkATgBhAG0AZQAAAAgAAAAAAAAAAAAAQHsAAAAAAAAAyAEAAAAAAAABAAAACAAAAAAAAAAAAPC/
+CAAAAAAAAAAAAPC/AAAAAAAAAAAAAAAA/////wAAAAA=