DRAFT CL: Add FrameNavigationEntry and track subframe session histories.

content/browser/frame_host/navigation_controller_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_controller_impl.h"
 
 #include "base/bind.h"
 #include "base/command_line.h"
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
 #include "base/strings/string_number_conversions.h"  // Temporary
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
 #include "base/time/time.h"
 #include "base/trace_event/trace_event.h"
 #include "cc/base/switches.h"
 #include "content/browser/browser_url_handler_impl.h"
 #include "content/browser/dom_storage/dom_storage_context_wrapper.h"
 #include "content/browser/dom_storage/session_storage_namespace_impl.h"
 #include "content/browser/frame_host/debug_urls.h"
+#include "content/browser/frame_host/frame_navigation_entry.h"
 #include "content/browser/frame_host/interstitial_page_impl.h"
 #include "content/browser/frame_host/navigation_entry_impl.h"
 #include "content/browser/frame_host/navigation_entry_screenshot_manager.h"
+#include "content/browser/frame_host/navigator_impl.h"
 #include "content/browser/renderer_host/render_view_host_impl.h"  // Temporary
 #include "content/browser/site_instance_impl.h"
 #include "content/common/frame_messages.h"
 #include "content/common/view_messages.h"
 #include "content/public/browser/browser_context.h"
 #include "content/public/browser/content_browser_client.h"
 #include "content/public/browser/invalidate_type.h"
 #include "content/public/browser/navigation_details.h"
 #include "content/public/browser/notification_service.h"
 #include "content/public/browser/notification_types.h"
@@ skipping 29 matching lines @@
 }
 
 // Ensure the given NavigationEntry has a valid state, so that WebKit does not
 // get confused if we navigate back to it.
 //
 // An empty state is treated as a new navigation by WebKit, which would mean
 // losing the navigation entries and generating a new navigation entry after
 // this one. We don't want that. To avoid this we create a valid state which
 // WebKit will not treat as a new navigation.
 void SetPageStateIfEmpty(NavigationEntryImpl* entry) {
+  // TODO(creis): Do this for FrameNavigationEntries instead.
   if (!entry->GetPageState().IsValid())
     entry->SetPageState(PageState::CreateFromURL(entry->GetURL()));
 }
 
 NavigationEntryImpl::RestoreType ControllerRestoreTypeToEntryType(
     NavigationController::RestoreType type) {
   switch (type) {
     case NavigationController::RESTORE_CURRENT_SESSION:
       return NavigationEntryImpl::RESTORE_CURRENT_SESSION;
     case NavigationController::RESTORE_LAST_SESSION_EXITED_CLEANLY:
       return NavigationEntryImpl::RESTORE_LAST_SESSION_EXITED_CLEANLY;
     case NavigationController::RESTORE_LAST_SESSION_CRASHED:
       return NavigationEntryImpl::RESTORE_LAST_SESSION_CRASHED;
   }
   NOTREACHED();
   return NavigationEntryImpl::RESTORE_CURRENT_SESSION;
 }
 
 // Configure all the NavigationEntries in entries for restore. This resets
 // the transition type to reload and makes sure the content state isn't empty.
+// TODO(creis): Take in a vector of FrameNavigationEntries instead.
 void ConfigureEntriesForRestore(
     std::vector<linked_ptr<NavigationEntryImpl> >* entries,
     NavigationController::RestoreType type) {
   for (size_t i = 0; i < entries->size(); ++i) {
     // Use a transition type of reload so that we don't incorrectly increase
     // the typed count.
     (*entries)[i]->SetTransitionType(ui::PAGE_TRANSITION_RELOAD);
     (*entries)[i]->set_restore_type(ControllerRestoreTypeToEntryType(type));
     // NOTE(darin): This code is only needed for backwards compat.
     SetPageStateIfEmpty((*entries)[i].get());
@@ skipping 71 matching lines @@
 
   // Allow the browser URL handler to rewrite the URL. This will, for example,
   // remove "view-source:" from the beginning of the URL to get the URL that
   // will actually be loaded. This real URL won't be shown to the user, just
   // used internally.
   GURL loaded_url(dest_url);
   bool reverse_on_redirect = false;
   BrowserURLHandlerImpl::GetInstance()->RewriteURLIfNecessary(
       &loaded_url, browser_context, &reverse_on_redirect);
 
+  // Common case: Navigate the top-level frame.
   NavigationEntryImpl* entry = new NavigationEntryImpl(
       NULL,  // The site instance for tabs is sent on navigation
              // (WebContents::GetSiteInstance).
       -1,
       loaded_url,
       referrer,
       base::string16(),
       transition,
       is_renderer_initiated);
   entry->SetVirtualURL(dest_url);
   entry->set_user_typed_url(dest_url);
   entry->set_update_virtual_url_with_url(reverse_on_redirect);
   entry->set_extra_headers(extra_headers);
   return entry;
 }
 
+// TODO(creis): Share code with CreateNavigationEntry.
+NavigationEntryImpl* NavigationControllerImpl::CreateSubframeNavigationEntry(
+    int64 frame_tree_node_id,
+    const GURL& url,
+    const Referrer& referrer,
+    ui::PageTransition transition,
+    bool is_renderer_initiated,
+    const std::string& extra_headers,
+    BrowserContext* browser_context) {
+  // Allow the browser URL handler to rewrite the URL. This will, for example,
+  // remove "view-source:" from the beginning of the URL to get the URL that
+  // will actually be loaded. This real URL won't be shown to the user, just
+  // used internally.
+  GURL loaded_url(url);
+  bool reverse_on_redirect = false;
+  BrowserURLHandlerImpl::GetInstance()->RewriteURLIfNecessary(
+      &loaded_url, browser_context, &reverse_on_redirect);
+
+  FrameTreeNode* main_frame = delegate_->GetFrameTreeRoot();
+
+  // Subframe navigation: Clone the current tree, then create a FrameNavEntry
+  // for the specified frame, clearing its subtree.
+  // TODO(creis): Don't clear subtree for in-page navigations.
+  NavigationEntryImpl* entry = new NavigationEntryImpl();
+  AddFramesToNavigationEntry(entry->root_node(), main_frame);
+  NavigationEntryImpl::TreeNode* node =
+      entry->GetTreeNodeForFrame(
+          main_frame->frame_tree()->FindByID(frame_tree_node_id));
+  DCHECK(node) << "Couldn't find TreeNode for " << frame_tree_node_id;
+  node->frame_entry = new FrameNavigationEntry(NULL, loaded_url, referrer);
+  node->frame_entry->set_frame_tree_node_id(frame_tree_node_id);
+  node->children.clear();
+
+  entry->SetVirtualURL(url);
+  entry->set_user_typed_url(url);
+  entry->set_update_virtual_url_with_url(reverse_on_redirect);
+  entry->set_extra_headers(extra_headers);
+  return entry;
+}
+
 // static
 void NavigationController::DisablePromptOnRepost() {
   g_check_for_repost = false;
 }
 
 base::Time NavigationControllerImpl::TimeSmoother::GetSmoothedTime(
     base::Time t) {
   // If |t| is between the water marks, we're in a run of duplicates
   // or just getting out of it, so increase the high-water mark to get
   // a time that probably hasn't been used before and return it.
@@ skipping 10 matching lines @@
 
 NavigationControllerImpl::NavigationControllerImpl(
     NavigationControllerDelegate* delegate,
     BrowserContext* browser_context)
     : browser_context_(browser_context),
       pending_entry_(NULL),
       last_committed_entry_index_(-1),
       pending_entry_index_(-1),
       transient_entry_index_(-1),
       delegate_(delegate),
+      next_page_id_(1),
       max_restored_page_id_(-1),
       ssl_manager_(this),
       needs_reload_(false),
       is_initial_navigation_(true),
       in_navigate_to_pending_entry_(false),
       pending_reload_(NO_RELOAD),
       get_timestamp_callback_(base::Bind(&base::Time::Now)),
       screenshot_manager_(new NavigationEntryScreenshotManager(this)) {
   DCHECK(browser_context_);
 }
@@ skipping 162 matching lines @@
     ReloadInternal(false, pending_reload_);
     pending_reload_ = NO_RELOAD;
   }
 }
 
 bool NavigationControllerImpl::IsInitialNavigation() const {
   return is_initial_navigation_;
 }
 
 NavigationEntryImpl* NavigationControllerImpl::GetEntryWithPageID(
-  SiteInstance* instance, int32 page_id) const {
-  int index = GetEntryIndexWithPageID(instance, page_id);
+    int32 page_id) const {
+  int index = GetEntryIndexWithPageID(page_id);
   return (index != -1) ? entries_[index].get() : NULL;
 }
 
 void NavigationControllerImpl::LoadEntry(NavigationEntryImpl* entry) {
   // When navigating to a new page, we don't know for sure if we will actually
   // end up leaving the current page.  The new page load could for example
   // result in a download or a 'no content' response (e.g., a mailto: URL).
   SetPendingEntry(entry);
   NavigateToPendingEntry(NO_RELOAD);
 }
@@ skipping 288 matching lines @@
       break;
     case UA_OVERRIDE_FALSE:
       override = false;
       break;
     default:
       NOTREACHED();
       break;
   }
 
   NavigationEntryImpl* entry = NavigationEntryImpl::FromNavigationEntry(
-      CreateNavigationEntry(
-          params.url,
-          params.referrer,
-          params.transition_type,
-          params.is_renderer_initiated,
-          params.extra_headers,
-          browser_context_));
-  if (params.frame_tree_node_id != -1)
-    entry->set_frame_tree_node_id(params.frame_tree_node_id);
+      params.frame_tree_node_id == -1 ?
+          CreateNavigationEntry(
+              params.url,
+              params.referrer,
+              params.transition_type,
+              params.is_renderer_initiated,
+              params.extra_headers,
+              browser_context_) :
+          CreateSubframeNavigationEntry(
+              params.frame_tree_node_id,
+              params.url,
+              params.referrer,
+              params.transition_type,
+              params.is_renderer_initiated,
+              params.extra_headers,
+              browser_context_));
+  // TODO(creis): Move source_site_instance to FNE.
   entry->set_source_site_instance(
       static_cast<SiteInstanceImpl*>(params.source_site_instance.get()));
   if (params.redirect_chain.size() > 0)
     entry->SetRedirectChain(params.redirect_chain);
   // Don't allow an entry replacement if there is no entry to replace.
   // http://crbug.com/457149
   if (params.should_replace_current_entry && entries_.size() > 0)
     entry->set_should_replace_entry(true);
   entry->set_should_clear_history_list(params.should_clear_history_list);
   entry->SetIsOverridingUserAgent(override);
@@ skipping 112 matching lines @@
   // We should not have a pending entry anymore.  Clear it again in case any
   // error cases above forgot to do so.
   DiscardNonCommittedEntriesInternal();
 
   // All committed entries should have nonempty content state so WebKit doesn't
   // get confused when we go back to them (see the function for details).
   DCHECK(params.page_state.IsValid());
   NavigationEntryImpl* active_entry = GetLastCommittedEntry();
   active_entry->SetTimestamp(timestamp);
   active_entry->SetHttpStatusCode(params.http_status_code);
-  active_entry->SetPageState(params.page_state);
   active_entry->SetRedirectChain(params.redirects);
+  FrameNavigationEntry* frame_entry =
+      active_entry->GetFrameEntryForFrame(rfh->frame_tree_node());
+  frame_entry->set_page_state(params.page_state);
 
   // Use histogram to track memory impact of redirect chain because it's now
   // not cleared for committed entries.
   size_t redirect_chain_size = 0;
   for (size_t i = 0; i < params.redirects.size(); ++i) {
     redirect_chain_size += params.redirects[i].spec().length();
   }
   UMA_HISTOGRAM_COUNTS("Navigation.RedirectChainSize", redirect_chain_size);
 
   // Once it is committed, we no longer need to track several pieces of state on
   // the entry.
   active_entry->ResetForCommit();
 
   // The active entry's SiteInstance should match our SiteInstance.
-  // TODO(creis): This check won't pass for subframes until we create entries
-  // for subframe navigations.
-  if (ui::PageTransitionIsMainFrame(params.transition))
-    CHECK(active_entry->site_instance() == rfh->GetSiteInstance());
+  CHECK(frame_entry->site_instance() == rfh->GetSiteInstance());
 
   // Remember the bindings the renderer process has at this point, so that
   // we do not grant this entry additional bindings if we come back to it.
   active_entry->SetBindings(rfh->GetEnabledBindings());
 
   // Now prep the rest of the details for the notification and broadcast.
   details->entry = active_entry;
   details->is_main_frame =
       ui::PageTransitionIsMainFrame(params.transition);
   details->serialized_security_info = params.security_info;
   details->http_status_code = params.http_status_code;
   NotifyNavigationEntryCommitted(details);
 
   return true;
 }
 
 NavigationType NavigationControllerImpl::ClassifyNavigation(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params) const {
-  if (params.page_id == -1) {
-    // TODO(nasko, creis):  An out-of-process child frame has no way of
-    // knowing the page_id of its parent, so it is passing back -1. The
-    // semantics here should be re-evaluated during session history refactor
-    // (see http://crbug.com/236848). For now, we assume this means the
-    // child frame loaded and proceed. Note that this may do the wrong thing
-    // for cross-process AUTO_SUBFRAME navigations.
-    if (rfh->IsCrossProcessSubframe())
-      return NAVIGATION_TYPE_NEW_SUBFRAME;
-
+  // TODO(creis): Can this go away?  We now have page_id == -1 for all new navs.
+  if (params.item_sequence_number == -1) {
     // The renderer generates the page IDs, and so if it gives us the invalid
     // page ID (-1) we know it didn't actually navigate. This happens in a few
     // cases:
     //
     // - If a page makes a popup navigated to about blank, and then writes
     //   stuff like a subframe navigated to a real page. We'll get the commit
     //   for the subframe, but there won't be any commit for the outer page.
     //
     // - We were also getting these for failed loads (for example, bug 21849).
     //   The guess is that we get a "load commit" for the alternate error page,
     //   but that doesn't affect the page ID, so we get the "old" one, which
     //   could be invalid. This can also happen for a cross-site transition
     //   that causes us to swap processes. Then the error page load will be in
     //   a new process with no page IDs ever assigned (and hence a -1 value),
     //   yet the navigation controller still might have previous pages in its
     //   list.
     //
     // In these cases, there's nothing we can do with them, so ignore.
     return NAVIGATION_TYPE_NAV_IGNORE;
   }
 
-  if (params.page_id > delegate_->GetMaxPageIDForSiteInstance(
-          rfh->GetSiteInstance())) {
+  if (params.page_id == -1) {
+    // A page ID of -1 means this is a new navigation of some kind.
+    // TODO(creis): update comment below.
     // Greater page IDs than we've ever seen before are new pages. We may or may
     // not have a pending entry for the page, and this may or may not be the
     // main frame.
     if (ui::PageTransitionIsMainFrame(params.transition))
       return NAVIGATION_TYPE_NEW_PAGE;
 
     // When this is a new subframe navigation, we should have a committed page
     // for which it's a suframe in. This may not be the case when an iframe is
     // navigated on a popup navigated to about:blank (the iframe would be
     // written into the popup by script on the main page). For these cases,
     // there isn't any navigation stuff we can do, so just ignore it.
     if (!GetLastCommittedEntry())
       return NAVIGATION_TYPE_NAV_IGNORE;
 
     // Valid subframe navigation.
+    // TODO(creis): Do this once 464014 is fixed.
+    //if (ui::PageTransitionCoreTypeIs(params.transition,
+    //                                 ui::PAGE_TRANSITION_AUTO_SUBFRAME))
+    //  return NAVIGATION_TYPE_AUTO_SUBFRAME;
     return NAVIGATION_TYPE_NEW_SUBFRAME;
   }
 
   // We only clear the session history when navigating to a new page.
   DCHECK(!params.history_list_was_cleared);
 
   // Now we know that the notification is for an existing page. Find that entry.
-  int existing_entry_index = GetEntryIndexWithPageID(
-      rfh->GetSiteInstance(),
-      params.page_id);
+  int existing_entry_index = GetEntryIndexWithPageID(params.page_id);
   if (existing_entry_index == -1) {
     // The page was not found. It could have been pruned because of the limit on
     // back/forward entries (not likely since we'll usually tell it to navigate
     // to such entries). It could also mean that the renderer is smoking crack.
     NOTREACHED();
 
     // Because the unknown entry has committed, we risk showing the wrong URL in
     // release builds. Instead, we'll kill the renderer process to be safe.
     LOG(ERROR) << "terminating renderer for bad navigation: " << params.url;
     RecordAction(base::UserMetricsAction("BadMessageTerminate_NC"));
@@ skipping 66 matching lines @@
   // Since we weeded out "new" navigations above, we know this is an existing
   // (back/forward) navigation.
   return NAVIGATION_TYPE_EXISTING_PAGE;
 }
 
 void NavigationControllerImpl::RendererDidNavigateToNewPage(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params,
     bool replace_entry) {
   NavigationEntryImpl* new_entry;
+  FrameNavigationEntry* new_frame_entry;
   bool update_virtual_url;
   // Only make a copy of the pending entry if it is appropriate for the new page
   // that was just loaded.  We verify this at a coarse grain by checking that
   // the SiteInstance hasn't been assigned to something else.
-  if (pending_entry_ &&
-      (!pending_entry_->site_instance() ||
-       pending_entry_->site_instance() == rfh->GetSiteInstance())) {
-    new_entry = pending_entry_->Clone();
+  // TODO(creis): Copy over details from pending entry when appropriate.
+  // (Do we need a pending entry for each frame?)
+  /*FrameNavigationEntryImpl* pending_entry = ...;
+  if (pending_entry &&
+      (!pending_entry_>site_instance() ||
+       pending_entry->site_instance() == rfh->GetSiteInstance())) {
+    new_entry = new FrameNavigationEntryImpl(*pending_entry);
 
     update_virtual_url = new_entry->update_virtual_url_with_url();
-  } else {
+  } else { */
     new_entry = new NavigationEntryImpl;
+    new_frame_entry = new FrameNavigationEntry;
+    int64 frame_tree_node_id = rfh->frame_tree_node()->frame_tree_node_id();
+    new_frame_entry->set_frame_tree_node_id(frame_tree_node_id);
 
     // Find out whether the new entry needs to update its virtual URL on URL
     // change and set up the entry accordingly. This is needed to correctly
     // update the virtual URL when replaceState is called after a pushState.
     GURL url = params.url;
     bool needs_update = false;
     BrowserURLHandlerImpl::GetInstance()->RewriteURLIfNecessary(
         &url, browser_context_, &needs_update);
     new_entry->set_update_virtual_url_with_url(needs_update);
 
     // When navigating to a new page, give the browser URL handler a chance to
     // update the virtual URL based on the new URL. For example, this is needed
     // to show chrome://bookmarks/#1 when the bookmarks webui extension changes
     // the URL.
     update_virtual_url = needs_update;
-  }
+  //}
 
   // Don't use the page type from the pending entry. Some interstitial page
   // may have set the type to interstitial. Once we commit, however, the page
   // type must always be normal or error.
+  // TODO(creis): Move page type to FNE.
   new_entry->set_page_type(params.url_is_unreachable ? PAGE_TYPE_ERROR
                                                      : PAGE_TYPE_NORMAL);
-  new_entry->SetURL(params.url);
+  new_frame_entry->set_url(params.url);
   if (update_virtual_url)
     UpdateVirtualURLToURL(new_entry, params.url);
-  new_entry->SetReferrer(params.referrer);
-  new_entry->SetPageID(params.page_id);
+  new_frame_entry->set_referrer(params.referrer);
+  new_frame_entry->set_site_instance(rfh->GetSiteInstance());
+  new_frame_entry->set_item_sequence_number(params.item_sequence_number);
+  new_frame_entry->set_document_sequence_number(
+      params.document_sequence_number);
+
+  // Use a new page ID for this entry.
+  CHECK_EQ(-1, params.page_id);
+  new_entry->SetPageID(next_page_id_++);
+
   new_entry->SetTransitionType(params.transition);
-  new_entry->set_site_instance(
-      static_cast<SiteInstanceImpl*>(rfh->GetSiteInstance()));
   new_entry->SetHasPostData(params.is_post);
   new_entry->SetPostID(params.post_id);
   new_entry->SetOriginalRequestURL(params.original_request_url);
   new_entry->SetIsOverridingUserAgent(params.is_overriding_user_agent);
 
   // history.pushState() is classified as a navigation to a new page, but
   // sets was_within_same_page to true. In this case, we already have the
   // title and favicon available, so set them immediately.
   if (params.was_within_same_page && GetLastCommittedEntry()) {
     new_entry->SetTitle(GetLastCommittedEntry()->GetTitle());
     new_entry->GetFavicon() = GetLastCommittedEntry()->GetFavicon();
   }
 
   DCHECK(!params.history_list_was_cleared || !replace_entry);
   // The browser requested to clear the session history when it initiated the
   // navigation. Now we know that the renderer has updated its state accordingly
   // and it is safe to also clear the browser side history.
   if (params.history_list_was_cleared) {
     DiscardNonCommittedEntriesInternal();
     entries_.clear();
     last_committed_entry_index_ = -1;
+    rfh->frame_tree_node()->set_last_committed_frame_entry(nullptr);
   }
 
-  InsertOrReplaceEntry(new_entry, replace_entry);
+  InsertOrReplaceEntry(rfh, new_entry, new_frame_entry, replace_entry);
 }
 
 void NavigationControllerImpl::RendererDidNavigateToExistingPage(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params) {
   // We should only get here for main frame navigations.
   DCHECK(ui::PageTransitionIsMainFrame(params.transition));
 
   // This is a back/forward navigation. The existing page for the ID is
   // guaranteed to exist by ClassifyNavigation, and we just need to update it
   // with new information from the renderer.
-  int entry_index = GetEntryIndexWithPageID(rfh->GetSiteInstance(),
-                                            params.page_id);
+  int entry_index = GetEntryIndexWithPageID(params.page_id);
   DCHECK(entry_index >= 0 &&
          entry_index < static_cast<int>(entries_.size()));
   NavigationEntryImpl* entry = entries_[entry_index].get();
 
+  // TODO(creis): Do these operations directly on the FNE.
   // The URL may have changed due to redirects.
   entry->set_page_type(params.url_is_unreachable ? PAGE_TYPE_ERROR
                                                  : PAGE_TYPE_NORMAL);
   entry->SetURL(params.url);
   entry->SetReferrer(params.referrer);
   if (entry->update_virtual_url_with_url())
     UpdateVirtualURLToURL(entry, params.url);
 
   // The redirected to page should not inherit the favicon from the previous
   // page.
   if (ui::PageTransitionIsRedirect(params.transition))
     entry->GetFavicon() = FaviconStatus();
 
   // The site instance will normally be the same except during session restore,
   // when no site instance will be assigned.
   DCHECK(entry->site_instance() == NULL ||
          entry->site_instance() == rfh->GetSiteInstance());
-  entry->set_site_instance(
-      static_cast<SiteInstanceImpl*>(rfh->GetSiteInstance()));
+  entry->set_site_instance(rfh->GetSiteInstance());
 
   entry->SetHasPostData(params.is_post);
   entry->SetPostID(params.post_id);
 
   // The entry we found in the list might be pending if the user hit
   // back/forward/reload. This load should commit it (since it's already in the
   // list, we can just discard the pending pointer).  We should also discard the
   // pending entry if it corresponds to a different navigation, since that one
   // is now likely canceled.  If it is not canceled, we will treat it as a new
   // navigation when it arrives, which is also ok.
   //
   // Note that we need to use the "internal" version since we don't want to
   // actually change any other state, just kill the pointer.
   DiscardNonCommittedEntriesInternal();
 
   // If a transient entry was removed, the indices might have changed, so we
   // have to query the entry index again.
-  last_committed_entry_index_ =
-      GetEntryIndexWithPageID(rfh->GetSiteInstance(), params.page_id);
+  last_committed_entry_index_ = GetEntryIndexWithPageID(params.page_id);
+  rfh->frame_tree_node()->set_last_committed_frame_entry(
+      entry->GetFrameEntryForFrame(rfh->frame_tree_node()));
 }
 
 void NavigationControllerImpl::RendererDidNavigateToSamePage(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params) {
   // This mode implies we have a pending entry that's the same as an existing
   // entry for this page ID. This entry is guaranteed to exist by
   // ClassifyNavigation. All we need to do is update the existing entry.
-  NavigationEntryImpl* existing_entry = GetEntryWithPageID(
-      rfh->GetSiteInstance(), params.page_id);
+  NavigationEntryImpl* existing_entry = GetEntryWithPageID(params.page_id);
 
   // We assign the entry's unique ID to be that of the new one. Since this is
   // always the result of a user action, we want to dismiss infobars, etc. like
   // a regular user-initiated navigation.
   existing_entry->set_unique_id(pending_entry_->GetUniqueID());
 
   // The URL may have changed due to redirects.
   existing_entry->set_page_type(params.url_is_unreachable ? PAGE_TYPE_ERROR
                                                           : PAGE_TYPE_NORMAL);
   if (existing_entry->update_virtual_url_with_url())
     UpdateVirtualURLToURL(existing_entry, params.url);
   existing_entry->SetURL(params.url);
   existing_entry->SetReferrer(params.referrer);
 
   // The page may have been requested with a different HTTP method.
   existing_entry->SetHasPostData(params.is_post);
   existing_entry->SetPostID(params.post_id);
 
   DiscardNonCommittedEntries();
 }
 
 void NavigationControllerImpl::RendererDidNavigateInPage(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params,
     bool* did_replace_entry) {
+  // TODO(creis): Why?  Is this by spec?
   DCHECK(ui::PageTransitionIsMainFrame(params.transition)) <<
       "WebKit should only tell us about in-page navs for the main frame.";
   // We're guaranteed to have an entry for this one.
-  NavigationEntryImpl* existing_entry = GetEntryWithPageID(
-      rfh->GetSiteInstance(), params.page_id);
+  NavigationEntryImpl* existing_entry = GetEntryWithPageID(params.page_id);
 
   // Reference fragment navigation. We're guaranteed to have the last_committed
   // entry and it will be the same page as the new navigation (minus the
   // reference fragments, of course).  We'll update the URL of the existing
   // entry without pruning the forward history.
   existing_entry->set_page_type(params.url_is_unreachable ? PAGE_TYPE_ERROR
                                                           : PAGE_TYPE_NORMAL);
   existing_entry->SetURL(params.url);
   if (existing_entry->update_virtual_url_with_url())
     UpdateVirtualURLToURL(existing_entry, params.url);
 
   existing_entry->SetHasPostData(params.is_post);
   existing_entry->SetPostID(params.post_id);
 
   // This replaces the existing entry since the page ID didn't change.
   *did_replace_entry = true;
 
   DiscardNonCommittedEntriesInternal();
 
   // If a transient entry was removed, the indices might have changed, so we
   // have to query the entry index again.
-  last_committed_entry_index_ =
-      GetEntryIndexWithPageID(rfh->GetSiteInstance(), params.page_id);
+  last_committed_entry_index_ = GetEntryIndexWithPageID(params.page_id);
+  rfh->frame_tree_node()->set_last_committed_frame_entry(
+      existing_entry->GetFrameEntryForFrame(rfh->frame_tree_node()));
 }
 
 void NavigationControllerImpl::RendererDidNavigateNewSubframe(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params) {
-  if (!ui::PageTransitionCoreTypeIs(params.transition,
-                                    ui::PAGE_TRANSITION_MANUAL_SUBFRAME)) {
+  int64 frame_tree_node_id = rfh->frame_tree_node()->frame_tree_node_id();
+  // TODO(creis): Is this equivalent to checking PAGE_TRANSITION_AUTO_SUBFRAME?
+  if (!rfh->frame_tree_node()->last_committed_frame_entry()) {
+    DCHECK(ui::PageTransitionCoreTypeIs(params.transition,
+                                        ui::PAGE_TRANSITION_AUTO_SUBFRAME));
     // There was a comment here that said, "This is not user-initiated. Ignore."
     // But this makes no sense; non-user-initiated navigations should be
     // determined to be of type NAVIGATION_TYPE_AUTO_SUBFRAME and sent to
     // RendererDidNavigateAutoSubframe below.
     //
     // This if clause dates back to https://codereview.chromium.org/115919 and
     // the handling of immediate redirects. TODO(avi): Is this still valid? I'm
     // pretty sure that's there's nothing left of that code and that we should
     // take this out.
     //
     // Except for cross-process iframes; this doesn't work yet for them.
     if (!base::CommandLine::ForCurrentProcess()->HasSwitch(
           switches::kSitePerProcess)) {
       NOTREACHED();
     }
 
     DiscardNonCommittedEntriesInternal();
+
+    // New: We do need to add a FrameNavigationEntry.
+    // TODO(creis): Refactor this method to avoid duplication.
+    FrameNavigationEntry* frame_entry = new FrameNavigationEntry(
+        rfh->GetSiteInstance(), params.url, params.referrer);
+    frame_entry->set_frame_tree_node_id(frame_tree_node_id);
+    frame_entry->set_item_sequence_number(params.item_sequence_number);
+    frame_entry->set_document_sequence_number(params.document_sequence_number);
+    rfh->frame_tree_node()->set_last_committed_frame_entry(frame_entry);
+
+    // Reset the frame tree pointers for the last committed entry.
+    NavigationEntryImpl* last_committed =
+        NavigationEntryImpl::FromNavigationEntry(GetLastCommittedEntry());
+    // TODO(creis): Just add this one; don't try to reset the whole tree.
+    last_committed->ResetFrameTree();
+    AddFramesToNavigationEntry(last_committed->root_node(),
+                               delegate_->GetFrameTreeRoot());
+
     return;
   }
 
   // Manual subframe navigations just get the current entry cloned so the user
   // can go back or forward to it. The actual subframe information will be
   // stored in the page state for each of those entries. This happens out of
   // band with the actual navigations.
   DCHECK(GetLastCommittedEntry()) << "ClassifyNavigation should guarantee "
                                   << "that a last committed entry exists.";
   NavigationEntryImpl* new_entry = GetLastCommittedEntry()->Clone();
-  new_entry->SetPageID(params.page_id);
-  InsertOrReplaceEntry(new_entry, false);
+
+  // Use a new page ID for this entry.
+  CHECK_EQ(-1, params.page_id);
+  new_entry->SetPageID(next_page_id_++);
+
+  // Create an appropriate subframe entry for it.
+  FrameNavigationEntry* frame_entry = new FrameNavigationEntry(
+      rfh->GetSiteInstance(), params.url, params.referrer);
+  frame_entry->set_frame_tree_node_id(frame_tree_node_id);
+  frame_entry->set_item_sequence_number(params.item_sequence_number);
+  frame_entry->set_document_sequence_number(params.document_sequence_number);
+
+  InsertOrReplaceEntry(rfh, new_entry, frame_entry, false);
 }
 
 bool NavigationControllerImpl::RendererDidNavigateAutoSubframe(
     RenderFrameHostImpl* rfh,
     const FrameHostMsg_DidCommitProvisionalLoad_Params& params) {
   DCHECK(ui::PageTransitionCoreTypeIs(params.transition,
                                       ui::PAGE_TRANSITION_AUTO_SUBFRAME));
 
   // We're guaranteed to have a previously committed entry, and we now need to
   // handle navigation inside of a subframe in it without creating a new entry.
   DCHECK(GetLastCommittedEntry());
 
-  // Handle the case where we're navigating back/forward to a previous subframe
-  // navigation entry. This is case "2." in NAV_AUTO_SUBFRAME comment in the
-  // header file. In case "1." this will be a NOP.
-  int entry_index = GetEntryIndexWithPageID(
-      rfh->GetSiteInstance(),
-      params.page_id);
-  if (entry_index < 0 ||
-      entry_index >= static_cast<int>(entries_.size())) {
+  // TODO(creis): Split this out into ExistingSubframe.
+  // Handle the case where we're navigating back/forward to a previous
+  // subframe navigation entry. This is case "2." in NAV_AUTO_SUBFRAME comment
+  // in the header file. In case "1." this will be a NOP.
+  int entry_index = GetEntryIndexWithPageID(params.page_id);
+  if (entry_index < 0 || entry_index >= static_cast<int>(entries_.size())) {
     NOTREACHED();
     return false;
   }
 
   // Update the current navigation entry in case we're going back/forward.
   if (entry_index != last_committed_entry_index_) {
     last_committed_entry_index_ = entry_index;
     DiscardNonCommittedEntriesInternal();
+
+    // New: Find the FrameNavigationEntry this corresponds to and update our
+    // index for that frame.
+    // TODO(creis): Update the FNE, similar to ExistingPage.
+    NavigationEntryImpl* entry = GetEntryAtIndex(entry_index);
+    FrameNavigationEntry* frame_entry =
+       entry->GetFrameEntryForFrame(rfh->frame_tree_node());
+    rfh->frame_tree_node()->set_last_committed_frame_entry(frame_entry);
+
     return true;
   }
 
+  // If we get here without returning, then this was a second (or greater)
+  // subframe committing as part of a back/forward.  Only the first one causes
+  // us to change the last_committed_entry_index_.
+
+  // New: We do need to add a FrameNavigationEntry.
+  FrameNavigationEntry* frame_entry = new FrameNavigationEntry(
+      rfh->GetSiteInstance(), params.url, params.referrer);
+  int64 frame_tree_node_id = rfh->frame_tree_node()->frame_tree_node_id();
+  frame_entry->set_frame_tree_node_id(frame_tree_node_id);
+  frame_entry->set_item_sequence_number(params.item_sequence_number);
+  frame_entry->set_document_sequence_number(params.document_sequence_number);
+
+  // TODO(creis): This was missing in the case of going forward from an old main
+  // frame to one with a subframe.  We don't give the re-created subframe the
+  // same FTN ID, so we don't find it in our array.  (That's a bug on its own.)
+  // But when we do get here legitimately, don't we need to assign page state?
+  // What else?
+  frame_entry->set_page_state(params.page_state);
+
+  rfh->frame_tree_node()->set_last_committed_frame_entry(frame_entry);
+
+  // Reset the frame tree pointers for the last committed entry.
+  NavigationEntryImpl* last_committed =
+      NavigationEntryImpl::FromNavigationEntry(GetLastCommittedEntry());
+  // TODO(creis): Just add this one; don't try to reset the whole tree.
+  last_committed->ResetFrameTree();
+  AddFramesToNavigationEntry(last_committed->root_node(),
+                             delegate_->GetFrameTreeRoot());
+
   // We do not need to discard the pending entry in this case, since we will
   // not generate commit notifications for this auto-subframe navigation.
   return false;
 }
 
 int NavigationControllerImpl::GetIndexOfEntry(
     const NavigationEntryImpl* entry) const {
   const NavigationEntries::const_iterator i(std::find(
       entries_.begin(),
       entries_.end(),
@@ skipping 127 matching lines @@
 void NavigationControllerImpl::PruneAllButLastCommittedInternal() {
   // It is up to callers to check the invariants before calling this.
   CHECK(CanPruneAllButLastCommitted());
 
   // Erase all entries but the last committed entry.  There may still be a
   // new pending entry after this.
   entries_.erase(entries_.begin(),
                  entries_.begin() + last_committed_entry_index_);
   entries_.erase(entries_.begin() + 1, entries_.end());
   last_committed_entry_index_ = 0;
+  // TODO(creis): Update last committed FNE?.
 }
 
 void NavigationControllerImpl::ClearAllScreenshots() {
   screenshot_manager_->ClearAllScreenshots();
 }
 
 void NavigationControllerImpl::SetSessionStorageNamespace(
     const std::string& partition_id,
     SessionStorageNamespace* session_storage_namespace) {
   if (!session_storage_namespace)
@@ skipping 102 matching lines @@
 }
 
 NavigationEntryImpl* NavigationControllerImpl::GetPendingEntry() const {
   return pending_entry_;
 }
 
 int NavigationControllerImpl::GetPendingEntryIndex() const {
   return pending_entry_index_;
 }
 
-void NavigationControllerImpl::InsertOrReplaceEntry(NavigationEntryImpl* entry,
-                                                    bool replace) {
+void NavigationControllerImpl::InsertOrReplaceEntry(
+    RenderFrameHostImpl* rfh,
+    NavigationEntryImpl* entry,
+    FrameNavigationEntry* frame_entry,
+    bool replace) {
   DCHECK(entry->GetTransitionType() != ui::PAGE_TRANSITION_AUTO_SUBFRAME);
 
   // Copy the pending entry's unique ID to the committed entry.
   // I don't know if pending_entry_index_ can be other than -1 here.
   const NavigationEntryImpl* const pending_entry =
       (pending_entry_index_ == -1) ?
           pending_entry_ : entries_[pending_entry_index_].get();
   if (pending_entry)
     entry->set_unique_id(pending_entry->GetUniqueID());
 
@@ skipping 16 matching lines @@
       num_pruned++;
       entries_.pop_back();
       current_size--;
     }
     if (num_pruned > 0)  // Only notify if we did prune something.
       NotifyPrunedEntries(this, false, num_pruned);
   }
 
   PruneOldestEntryIfFull();
 
+  // New: Set the last committed frame entry for this frame.
+  // TODO(creis): This breaks in the replace case.  We need to update the
+  // existing FNE with all the data from frame_entry in that case, since many
+  // NE's might already have references to the existing one.
+  rfh->frame_tree_node()->set_last_committed_frame_entry(frame_entry);
+
+  // New: Give the entry a fresh tree of pointers to the current frame entry for
+  // each current frame, starting from the root.
+  // TODO(creis): How can we clear it without deleting the refcounted FNEs?
+  // I think we want to verify that it's empty here, and have a different way to
+  // append a new frame to an existing NE.
+  entry->ResetFrameTree();
+  AddFramesToNavigationEntry(entry->root_node(), delegate_->GetFrameTreeRoot());
+
+  // Finally, add the entry to the joint session history.
   entries_.push_back(linked_ptr<NavigationEntryImpl>(entry));
   last_committed_entry_index_ = static_cast<int>(entries_.size()) - 1;
 
   // This is a new page ID, so we need everybody to know about it.
+  // TODO(creis): Is this still necessary?
   delegate_->UpdateMaxPageID(entry->GetPageID());
 }
 
+void NavigationControllerImpl::AddFramesToNavigationEntry(
+    NavigationEntryImpl::TreeNode* entry_node,
+    FrameTreeNode* frame_tree_node) {
+  // TODO(creis): Remove this once auto-subframe case is fixed.  // ?
+  if (!frame_tree_node->last_committed_frame_entry())
+    return;
+
+  // Put the last committed FrameNavigationEntry for this frame into the
+  // corresponding spot of the top-level NavigationEntry.
+  entry_node->SetFrameEntry(frame_tree_node->last_committed_frame_entry());
+  CHECK(entry_node->frame_entry);
+
+  // Repeat for all the child frames.
+  for (size_t i=0; i < frame_tree_node->child_count(); i++) {
+    entry_node->children.push_back(
+        new NavigationEntryImpl::TreeNode(entry_node->entry, nullptr));
+    CHECK_EQ(i + 1, entry_node->children.size());
+    AddFramesToNavigationEntry(entry_node->children[i],
+                               frame_tree_node->child_at(i));
+  }
+}
+
 void NavigationControllerImpl::PruneOldestEntryIfFull() {
   if (entries_.size() >= max_entry_count()) {
     DCHECK_EQ(max_entry_count(), entries_.size());
     DCHECK_GT(last_committed_entry_index_, 0);
     RemoveEntryAtIndex(0);
     NotifyPrunedEntries(this, true, 1);
   }
 }
 
 void NavigationControllerImpl::NavigateToPendingEntry(ReloadType reload_type) {
@@ skipping 33 matching lines @@
 
   // For session history navigations only the pending_entry_index_ is set.
   if (!pending_entry_) {
     DCHECK_NE(pending_entry_index_, -1);
     pending_entry_ = entries_[pending_entry_index_].get();
   }
 
   // This call does not support re-entrancy.  See http://crbug.com/347742.
   CHECK(!in_navigate_to_pending_entry_);
   in_navigate_to_pending_entry_ = true;
-  bool success = delegate_->NavigateToPendingEntry(reload_type);
+  bool success = NavigateToPendingEntryInternal(reload_type);
   in_navigate_to_pending_entry_ = false;
 
   if (!success)
     DiscardNonCommittedEntries();
 
   // If the entry is being restored and doesn't have a SiteInstance yet, fill
   // it in now that we know. This allows us to find the entry when it commits.
   if (pending_entry_ && !pending_entry_->site_instance() &&
       pending_entry_->restore_type() != NavigationEntryImpl::RESTORE_NONE) {
     pending_entry_->set_site_instance(static_cast<SiteInstanceImpl*>(
@@ skipping 58 matching lines @@
 }
 
 void NavigationControllerImpl::FinishRestore(int selected_index,
                                              RestoreType type) {
   DCHECK(selected_index >= 0 && selected_index < GetEntryCount());
   ConfigureEntriesForRestore(&entries_, type);
 
   SetMaxRestoredPageID(static_cast<int32>(GetEntryCount()));
 
   last_committed_entry_index_ = selected_index;
+  // TODO(creis): Update last committed FNE.
 }
 
 void NavigationControllerImpl::DiscardNonCommittedEntriesInternal() {
   DiscardPendingEntry();
   DiscardTransientEntry();
 }
 
 void NavigationControllerImpl::DiscardPendingEntry() {
   // It is not safe to call DiscardPendingEntry while NavigateToEntry is in
   // progress, since this will cause a use-after-free.  (We only allow this
   // when the tab is being destroyed for shutdown, since it won't return to
   // NavigateToEntry in that case.)  http://crbug.com/347742.
   CHECK(!in_navigate_to_pending_entry_ || delegate_->IsBeingDestroyed());
 
   if (pending_entry_index_ == -1)
     delete pending_entry_;
   pending_entry_ = NULL;
   pending_entry_index_ = -1;
 }
 
 void NavigationControllerImpl::DiscardTransientEntry() {
   if (transient_entry_index_ == -1)
     return;
   entries_.erase(entries_.begin() + transient_entry_index_);
   if (last_committed_entry_index_ > transient_entry_index_)
     last_committed_entry_index_--;
   transient_entry_index_ = -1;
 }
 
-int NavigationControllerImpl::GetEntryIndexWithPageID(
-    SiteInstance* instance, int32 page_id) const {
+int NavigationControllerImpl::GetEntryIndexWithPageID(int32 page_id) const {
   for (int i = static_cast<int>(entries_.size()) - 1; i >= 0; --i) {
-    if ((entries_[i]->site_instance() == instance) &&
-        (entries_[i]->GetPageID() == page_id))
+    if (entries_[i]->GetPageID() == page_id)
       return i;
   }
   return -1;
 }
 
 NavigationEntryImpl* NavigationControllerImpl::GetTransientEntry() const {
   if (transient_entry_index_ == -1)
     return NULL;
   return entries_[transient_entry_index_].get();
 }
@@ skipping 27 matching lines @@
                           source.entries_[i]->Clone()));
     }
   }
 }
 
 void NavigationControllerImpl::SetGetTimestampCallbackForTest(
     const base::Callback<base::Time()>& get_timestamp_callback) {
   get_timestamp_callback_ = get_timestamp_callback;
 }
 
+bool NavigationControllerImpl::NavigateToPendingEntryInternal(
+    ReloadType reload_type) {
+  FrameLoadVector same_document_loads;
+  FrameLoadVector different_document_loads;
+  DCHECK(pending_entry_);
+
+  FrameTreeNode* main_frame = delegate_->GetFrameTreeRoot();
+  if (GetLastCommittedEntry()) {
+    RecursiveNavigateToPendingEntry(
+        main_frame, &same_document_loads, &different_document_loads);
+  }
+
+  if (same_document_loads.empty() && different_document_loads.empty()) {
+    // If we don't have any frames to navigate at this point, either
+    // (1) there is no previous history entry to compare against, or
+    // (2) we were unable to match any frames by name. In the first case,
+    // doing a different document navigation to the root item is the only valid
+    // thing to do. In the second case, we should have been able to find a
+    // frame to navigate based on names if this were a same document
+    // navigation, so we can safely assume this is the different document case.
+    // TODO(creis): Is it safe to use a raw pointer for the FNE here?
+    different_document_loads.push_back(
+        std::make_pair(main_frame,
+                       pending_entry_->root_node()->frame_entry.get()));
+  }
+
+  // If all the frame loads fail, we will discard the pending entry.
+  bool success = false;
+
+  // Send all the same document frame loads before the different document loads.
+  for (size_t i = 0; i < same_document_loads.size(); ++i) {
+    FrameTreeNode* frame = same_document_loads[i].first;
+    success |= frame->navigator()->NavigateToPendingEntry(
+        frame, *same_document_loads[i].second, reload_type);
+  }
+  for (size_t i = 0; i < different_document_loads.size(); ++i) {
+    FrameTreeNode* frame = different_document_loads[i].first;
+    success |= frame->navigator()->NavigateToPendingEntry(
+        frame, *different_document_loads[i].second, reload_type);
+  }
+  return success;
+}
+
+void NavigationControllerImpl::RecursiveNavigateToPendingEntry(
+    FrameTreeNode* frame,
+    FrameLoadVector* same_document_loads,
+    FrameLoadVector* different_document_loads) {
+  DCHECK(pending_entry_);
+  DCHECK_GE(last_committed_entry_index_, 0);
+  FrameNavigationEntry* new_item = pending_entry_->GetFrameEntryForFrame(frame);
+  FrameNavigationEntry* old_item =
+      GetLastCommittedEntry()->GetFrameEntryForFrame(frame);
+  if (!new_item)
+    return;
+
+  if (!old_item ||
+      new_item->item_sequence_number() != old_item->item_sequence_number()) {
+    if (old_item &&
+        new_item->document_sequence_number() ==
+            old_item->document_sequence_number()) {
+      same_document_loads->push_back(std::make_pair(frame, new_item));
+    } else {
+      different_document_loads->push_back(std::make_pair(frame, new_item));
+    }
+    return;
+  }
+
+  for (size_t i = 0; i < frame->child_count(); i++) {
+    RecursiveNavigateToPendingEntry(frame->child_at(i), same_document_loads,
+                                    different_document_loads);
+  }
+}
+
 }  // namespace content