Update to new stable branch 1750

This also includes an updated ninja and chromium dependencies
needed on Windows.

Change-Id: Icd597d80ed3fa4425933c9f1334c3c2e31291c42
Reviewed-by: Zoltan Arvai <zarvai@inf.u-szeged.hu>
Reviewed-by: Zeno Albisser <zeno.albisser@digia.com>

1 files changed, 206 insertions, 575 deletions

diff --git a/chromium/third_party/WebKit/Source/core/loader/HistoryController.cpp b/chromium/third_party/WebKit/Source/core/loader/HistoryController.cpp
index be314f56128..033c7348ec0 100644
--- a/chromium/third_party/WebKit/Source/core/loader/HistoryController.cpp
+++ b/chromium/third_party/WebKit/Source/core/loader/HistoryController.cpp
@@ -31,686 +31,317 @@
 #include "config.h"
 #include "core/loader/HistoryController.h"
 
-#include "core/dom/Document.h"
-#include "core/history/BackForwardController.h"
-#include "core/history/HistoryItem.h"
-#include "core/html/HTMLFrameOwnerElement.h"
-#include "core/loader/DocumentLoader.h"
 #include "core/loader/FrameLoader.h"
-#include "core/loader/FrameLoaderClient.h"
-#include "core/loader/FrameLoaderStateMachine.h"
-#include "core/page/Frame.h"
+#include "core/frame/Frame.h"
 #include "core/page/FrameTree.h"
-#include "core/page/FrameView.h"
 #include "core/page/Page.h"
-#include "core/page/scrolling/ScrollingCoordinator.h"
-#include "core/platform/Logging.h"
-#include "wtf/text/CString.h"
+#include "wtf/Deque.h"
+#include "wtf/text/StringHash.h"
 
 namespace WebCore {
 
-HistoryController::HistoryController(Frame* frame)
-    : m_frame(frame)
-    , m_defersLoading(false)
+PassOwnPtr<HistoryNode> HistoryNode::create(HistoryEntry* entry, HistoryItem* value)
 {
+    return adoptPtr(new HistoryNode(entry, value));
 }
 
-HistoryController::~HistoryController()
+HistoryNode* HistoryNode::addChild(PassRefPtr<HistoryItem> item)
 {
+    m_children.append(HistoryNode::create(m_entry, item.get()));
+    return m_children.last().get();
 }
 
-void HistoryController::saveScrollPositionAndViewStateToItem(HistoryItem* item)
+PassOwnPtr<HistoryNode> HistoryNode::cloneAndReplace(HistoryEntry* newEntry, HistoryItem* newItem, bool clipAtTarget, Frame* targetFrame, Frame* currentFrame)
 {
-    if (!item || !m_frame->view())
-        return;
+    bool isNodeBeingNavigated = targetFrame == currentFrame;
+    HistoryItem* itemForCreate = isNodeBeingNavigated ? newItem : m_value.get();
+    OwnPtr<HistoryNode> newHistoryNode = create(newEntry, itemForCreate);
 
-    item->setScrollPoint(m_frame->view()->scrollPosition());
-
-    Page* page = m_frame->page();
-    if (page && page->mainFrame() == m_frame)
-        item->setPageScaleFactor(page->pageScaleFactor());
+    if (!clipAtTarget || !isNodeBeingNavigated) {
+        for (Frame* child = currentFrame->tree().firstChild(); child; child = child->tree().nextSibling()) {
+            HistoryNode* childHistoryNode = m_entry->historyNodeForFrame(child);
+            if (!childHistoryNode)
+                continue;
+            newHistoryNode->m_children.append(childHistoryNode->cloneAndReplace(newEntry, newItem, clipAtTarget, targetFrame, child));
+        }
+    }
+    return newHistoryNode.release();
 }
 
-void HistoryController::clearScrollPositionAndViewState()
+HistoryNode::HistoryNode(HistoryEntry* entry, HistoryItem* value)
+    : m_entry(entry)
+    , m_value(value)
 {
-    if (!m_currentItem)
-        return;
-
-    m_currentItem->clearScrollPoint();
-    m_currentItem->setPageScaleFactor(0);
+    m_entry->m_framesToItems.add(value->targetFrameID(), this);
+    String target = value->target();
+    if (target.isNull())
+        target = emptyString();
+    m_entry->m_uniqueNamesToItems.add(target, this);
 }
 
-/*
- There is a race condition between the layout and load completion that affects restoring the scroll position.
- We try to restore the scroll position at both the first layout and upon load completion.
-
- 1) If first layout happens before the load completes, we want to restore the scroll position then so that the
- first time we draw the page is already scrolled to the right place, instead of starting at the top and later
- jumping down.  It is possible that the old scroll position is past the part of the doc laid out so far, in
- which case the restore silent fails and we will fix it in when we try to restore on doc completion.
- 2) If the layout happens after the load completes, the attempt to restore at load completion time silently
- fails.  We then successfully restore it when the layout happens.
-*/
-void HistoryController::restoreScrollPositionAndViewState()
+void HistoryNode::removeChildren()
 {
-    if (!m_frame->loader()->stateMachine()->committedFirstRealDocumentLoad())
-        return;
-
-    ASSERT(m_currentItem);
+    // FIXME: This is inefficient. Figure out a cleaner way to ensure this HistoryNode isn't cached anywhere.
+    for (unsigned i = 0; i < m_children.size(); i++) {
+        m_children[i]->removeChildren();
 
-    // FIXME: As the ASSERT attests, it seems we should always have a currentItem here.
-    // One counterexample is <rdar://problem/4917290>
-    // For now, to cover this issue in release builds, there is no technical harm to returning
-    // early and from a user standpoint - as in the above radar - the previous page load failed
-    // so there *is* no scroll or view state to restore!
-    if (!m_currentItem)
-        return;
-
-    if (FrameView* view = m_frame->view()) {
-        Page* page = m_frame->page();
-        if (page && page->mainFrame() == m_frame) {
-            if (ScrollingCoordinator* scrollingCoordinator = page->scrollingCoordinator())
-                scrollingCoordinator->frameViewRootLayerDidChange(view);
+        HashMap<uint64_t, HistoryNode*>::iterator framesEnd = m_entry->m_framesToItems.end();
+        HashMap<String, HistoryNode*>::iterator uniqueNamesEnd = m_entry->m_uniqueNamesToItems.end();
+        for (HashMap<uint64_t, HistoryNode*>::iterator it = m_entry->m_framesToItems.begin(); it != framesEnd; ++it) {
+            if (it->value == m_children[i])
+                m_entry->m_framesToItems.remove(it);
         }
-
-        if (!view->wasScrolledByUser()) {
-            if (page && page->mainFrame() == m_frame && m_currentItem->pageScaleFactor())
-                page->setPageScaleFactor(m_currentItem->pageScaleFactor(), m_currentItem->scrollPoint());
-            else
-                view->setScrollPositionNonProgrammatically(m_currentItem->scrollPoint());
+        for (HashMap<String, HistoryNode*>::iterator it = m_entry->m_uniqueNamesToItems.begin(); it != uniqueNamesEnd; ++it) {
+            if (it->value == m_children[i])
+                m_entry->m_uniqueNamesToItems.remove(it);
         }
     }
+    m_children.clear();
 }
 
-void HistoryController::updateBackForwardListForFragmentScroll()
+HistoryEntry::HistoryEntry(HistoryItem* root)
 {
-    updateBackForwardListClippedAtTarget(false);
+    m_root = HistoryNode::create(this, root);
 }
 
-void HistoryController::saveDocumentState()
+PassOwnPtr<HistoryEntry> HistoryEntry::create(HistoryItem* root)
 {
-    if (!m_currentItem)
-        return;
-
-    Document* document = m_frame->document();
-    ASSERT(document);
-
-    if (m_currentItem->isCurrentDocument(document) && document->attached()) {
-        LOG(Loading, "WebCoreLoading %s: saving form state to %p", m_frame->tree()->uniqueName().string().utf8().data(), m_currentItem.get());
-        m_currentItem->setDocumentState(document->formElementsState());
-    }
+    return adoptPtr(new HistoryEntry(root));
 }
 
-// Walk the frame tree, telling all frames to save their form state into their current
-// history item.
-void HistoryController::saveDocumentAndScrollState()
+PassOwnPtr<HistoryEntry> HistoryEntry::cloneAndReplace(HistoryItem* newItem, bool clipAtTarget, Frame* targetFrame, Page* page)
 {
-    for (Frame* frame = m_frame; frame; frame = frame->tree()->traverseNext(m_frame)) {
-        frame->loader()->history()->saveDocumentState();
-        frame->loader()->history()->saveScrollPositionAndViewStateToItem(frame->loader()->history()->currentItem());
-    }
+    OwnPtr<HistoryEntry> newEntry = adoptPtr(new HistoryEntry());
+    newEntry->m_root = m_root->cloneAndReplace(newEntry.get(), newItem, clipAtTarget, targetFrame, page->mainFrame());
+    return newEntry.release();
 }
 
-static inline bool isAssociatedToRequestedHistoryItem(const HistoryItem* current, Frame* frame, const HistoryItem* requested)
+HistoryNode* HistoryEntry::historyNodeForFrame(Frame* frame)
 {
-    if (requested == current)
-        return true;
-    if (requested)
-        return false;
-    while ((frame = frame->tree()->parent())) {
-        requested = frame->loader()->requestedHistoryItem();
-        if (!requested)
-            continue;
-        if (requested->isAncestorOf(current))
-            return true;
-    }
-    return false;
+    if (HistoryNode* historyNode = m_framesToItems.get(frame->frameID()))
+        return historyNode;
+    String target = frame->tree().uniqueName();
+    if (target.isNull())
+        target = emptyString();
+    return m_uniqueNamesToItems.get(target);
 }
 
-void HistoryController::restoreDocumentState()
+HistoryItem* HistoryEntry::itemForFrame(Frame* frame)
 {
-    Document* doc = m_frame->document();
-
-    HistoryItem* itemToRestore = 0;
-
-    switch (m_frame->loader()->loadType()) {
-        case FrameLoadTypeReload:
-        case FrameLoadTypeReloadFromOrigin:
-        case FrameLoadTypeSame:
-            break;
-        case FrameLoadTypeBackForward:
-        case FrameLoadTypeRedirectWithLockedBackForwardList:
-        case FrameLoadTypeInitialInChildFrame:
-        case FrameLoadTypeStandard:
-            itemToRestore = m_currentItem.get();
-    }
-
-    if (!itemToRestore)
-        return;
-    if (isAssociatedToRequestedHistoryItem(itemToRestore, m_frame, m_frame->loader()->requestedHistoryItem()) && !m_frame->loader()->documentLoader()->isClientRedirect()) {
-        LOG(Loading, "WebCoreLoading %s: restoring form state from %p", m_frame->tree()->uniqueName().string().utf8().data(), itemToRestore);
-        doc->setStateForNewFormElements(itemToRestore->documentState());
-    }
-}
-
-bool HistoryController::shouldStopLoadingForHistoryItem(HistoryItem* targetItem) const
-{
-    if (!m_currentItem)
-        return false;
-    // Don't abort the current load if we're navigating within the current document.
-    return !m_currentItem->shouldDoSameDocumentNavigationTo(targetItem);
+    if (HistoryNode* historyNode = historyNodeForFrame(frame))
+        return historyNode->value();
+    return 0;
 }
 
-// Main funnel for navigating to a previous location (back/forward, non-search snap-back)
-// This includes recursion to handle loading into framesets properly
-void HistoryController::goToItem(HistoryItem* targetItem)
+HistoryController::HistoryController(Page* page)
+    : m_page(page)
+    , m_defersLoading(false)
 {
-    ASSERT(!m_frame->tree()->parent());
-
-    // shouldGoToHistoryItem is a private delegate method. This is needed to fix:
-    // <rdar://problem/3951283> can view pages from the back/forward cache that should be disallowed by Parental Controls
-    // Ultimately, history item navigations should go through the policy delegate. That's covered in:
-    // <rdar://problem/3979539> back/forward cache navigations should consult policy delegate
-    Page* page = m_frame->page();
-    if (!page)
-        return;
-    if (m_defersLoading) {
-        m_deferredItem = targetItem;
-        return;
-    }
-
-    // Set the BF cursor before commit, which lets the user quickly click back/forward again.
-    // - plus, it only makes sense for the top level of the operation through the frametree,
-    // as opposed to happening for some/one of the page commits that might happen soon
-    RefPtr<HistoryItem> currentItem = page->backForward().currentItem();
-    page->backForward().setCurrentItem(targetItem);
-
-    // First set the provisional item of any frames that are not actually navigating.
-    // This must be done before trying to navigate the desired frame, because some
-    // navigations can commit immediately (such as about:blank).  We must be sure that
-    // all frames have provisional items set before the commit.
-    recursiveSetProvisionalItem(targetItem, currentItem.get());
-    // Now that all other frames have provisional items, do the actual navigation.
-    recursiveGoToItem(targetItem, currentItem.get());
 }
 
-void HistoryController::setDefersLoading(bool defer)
-{
-    m_defersLoading = defer;
-    if (!defer && m_deferredItem) {
-        goToItem(m_deferredItem.get());
-        m_deferredItem = 0;
-    }
-}
-
-void HistoryController::updateForBackForwardNavigation()
+HistoryController::~HistoryController()
 {
-#if !LOG_DISABLED
-    LOG(History, "WebCoreHistory: Updating History for back/forward navigation in frame %s", m_frame->document()->title().utf8().data());
-#endif
-
-    saveScrollPositionAndViewStateToItem(m_previousItem.get());
-
-    // When traversing history, we may end up redirecting to a different URL
-    // this time (e.g., due to cookies).  See http://webkit.org/b/49654.
-    updateCurrentItem();
 }
 
-void HistoryController::updateForReload()
+void HistoryController::updateBackForwardListForFragmentScroll(Frame* frame, HistoryItem* item)
 {
-#if !LOG_DISABLED
-    LOG(History, "WebCoreHistory: Updating History for reload in frame %s", m_frame->document()->title().utf8().data());
-#endif
-
-    if (m_currentItem) {
-        if (m_frame->loader()->loadType() == FrameLoadTypeReload || m_frame->loader()->loadType() == FrameLoadTypeReloadFromOrigin)
-            saveScrollPositionAndViewStateToItem(m_currentItem.get());
-    }
-
-    // When reloading the page, we may end up redirecting to a different URL
-    // this time (e.g., due to cookies).  See http://webkit.org/b/4072.
-    updateCurrentItem();
+    m_provisionalEntry.clear();
+    createNewBackForwardItem(frame, item, false);
 }
 
-// There are 2 things you might think of as "history", all of which are handled by these functions.
-//
-//     1) Back/forward: The m_currentItem is part of this mechanism.
-//     2) Global history: Handled by the client.
-//
-void HistoryController::updateForStandardLoad()
+void HistoryController::goToEntry(PassOwnPtr<HistoryEntry> targetEntry)
 {
-    LOG(History, "WebCoreHistory: Updating History for Standard Load in frame %s", m_frame->loader()->documentLoader()->url().string().ascii().data());
+    ASSERT(m_sameDocumentLoadsInProgress.isEmpty());
+    ASSERT(m_differentDocumentLoadsInProgress.isEmpty());
 
-    if (!m_frame->loader()->documentLoader()->urlForHistory().isEmpty())
-        updateBackForwardListClippedAtTarget(true);
-}
+    m_provisionalEntry = targetEntry;
+    if (m_currentEntry)
+        recursiveGoToEntry(m_page->mainFrame());
+    else
+        m_differentDocumentLoadsInProgress.set(m_page->mainFrame(), m_provisionalEntry->root());
 
-void HistoryController::updateForRedirectWithLockedBackForwardList()
-{
-#if !LOG_DISABLED
-    LOG(History, "WebCoreHistory: Updating History for redirect load in frame %s", m_frame->document()->title().utf8().data());
-#endif
+    if (m_sameDocumentLoadsInProgress.isEmpty() && m_differentDocumentLoadsInProgress.isEmpty())
+        m_sameDocumentLoadsInProgress.set(m_page->mainFrame(), m_provisionalEntry->root());
 
-    if (!m_currentItem && !m_frame->tree()->parent()) {
-        if (!m_frame->loader()->documentLoader()->urlForHistory().isEmpty())
-            updateBackForwardListClippedAtTarget(true);
+    if (m_differentDocumentLoadsInProgress.isEmpty()) {
+        m_previousEntry = m_currentEntry.release();
+        m_currentEntry = m_provisionalEntry.release();
+    } else {
+        m_page->mainFrame()->loader().stopAllLoaders();
     }
-    // The client redirect replaces the current history item.
-    updateCurrentItem();
-}
 
-void HistoryController::updateForInitialLoadInChildFrame()
-{
-    Frame* parentFrame = m_frame->tree()->parent();
-    if (parentFrame && parentFrame->loader()->history()->m_currentItem)
-        parentFrame->loader()->history()->m_currentItem->setChildItem(createItem());
+    for (HistoryFrameLoadSet::iterator it = m_sameDocumentLoadsInProgress.begin(); it != m_sameDocumentLoadsInProgress.end(); ++it)
+        it->key->loader().loadHistoryItem(it->value.get(), HistorySameDocumentLoad);
+    for (HistoryFrameLoadSet::iterator it = m_differentDocumentLoadsInProgress.begin(); it != m_differentDocumentLoadsInProgress.end(); ++it)
+        it->key->loader().loadHistoryItem(it->value.get(), HistoryDifferentDocumentLoad);
+    m_sameDocumentLoadsInProgress.clear();
+    m_differentDocumentLoadsInProgress.clear();
 }
 
-void HistoryController::updateForCommit()
+void HistoryController::recursiveGoToEntry(Frame* frame)
 {
-    FrameLoader* frameLoader = m_frame->loader();
-#if !LOG_DISABLED
-    if (m_frame->document())
-        LOG(History, "WebCoreHistory: Updating History for commit in frame %s", m_frame->document()->title().utf8().data());
-#endif
-    FrameLoadType type = frameLoader->loadType();
-    if (isBackForwardLoadType(type) || (isReloadTypeWithProvisionalItem(type) && !frameLoader->documentLoader()->unreachableURL().isEmpty())) {
-        // Once committed, we want to use current item for saving DocState, and
-        // the provisional item for restoring state.
-        // Note previousItem must be set before we close the URL, which will
-        // happen when the data source is made non-provisional below
-        m_previousItem = m_currentItem;
-        ASSERT(m_provisionalItem);
-        m_currentItem = m_provisionalItem;
-        m_provisionalItem = 0;
-
-        // Tell all other frames in the tree to commit their provisional items and
-        // restore their scroll position.  We'll avoid this frame (which has already
-        // committed) and its children (which will be replaced).
-        Page* page = m_frame->page();
-        ASSERT(page);
-        page->mainFrame()->loader()->history()->recursiveUpdateForCommit();
-    }
-
-    switch (type) {
-    case FrameLoadTypeBackForward:
-        updateForBackForwardNavigation();
+    ASSERT(m_provisionalEntry);
+    ASSERT(m_currentEntry);
+    HistoryItem* newItem = m_provisionalEntry->itemForFrame(frame);
+    HistoryItem* oldItem = m_currentEntry->itemForFrame(frame);
+    if (!newItem)
         return;
-    case FrameLoadTypeReload:
-    case FrameLoadTypeReloadFromOrigin:
-    case FrameLoadTypeSame:
-        updateForReload();
-        return;
-    case FrameLoadTypeStandard:
-        updateForStandardLoad();
-        return;
-    case FrameLoadTypeRedirectWithLockedBackForwardList:
-        updateForRedirectWithLockedBackForwardList();
-        return;
-    case FrameLoadTypeInitialInChildFrame:
-        updateForInitialLoadInChildFrame();
+
+    if (!oldItem || (newItem != oldItem && newItem->itemSequenceNumber() != oldItem->itemSequenceNumber())) {
+        if (oldItem && newItem->documentSequenceNumber() == oldItem->documentSequenceNumber())
+            m_sameDocumentLoadsInProgress.set(frame, newItem);
+        else
+            m_differentDocumentLoadsInProgress.set(frame, newItem);
         return;
-    default:
-        ASSERT_NOT_REACHED();
     }
-}
 
-bool HistoryController::isReloadTypeWithProvisionalItem(FrameLoadType type)
-{
-    return (type == FrameLoadTypeReload || type == FrameLoadTypeReloadFromOrigin) && m_provisionalItem;
+    for (Frame* child = frame->tree().firstChild(); child; child = child->tree().nextSibling())
+        recursiveGoToEntry(child);
 }
 
-void HistoryController::recursiveUpdateForCommit()
+void HistoryController::goToItem(HistoryItem* targetItem)
 {
-    // The frame that navigated will now have a null provisional item.
-    // Ignore it and its children.
-    if (!m_provisionalItem)
+    if (m_defersLoading) {
+        m_deferredItem = targetItem;
         return;
-
-    // For each frame that already had the content the item requested (based on
-    // (a matching URL and frame tree snapshot), just restore the scroll position.
-    // Save form state
-    if (m_currentItem && itemsAreClones(m_currentItem.get(), m_provisionalItem.get())) {
-        saveDocumentState();
-        saveScrollPositionAndViewStateToItem(m_currentItem.get());
-
-        if (FrameView* view = m_frame->view())
-            view->setWasScrolledByUser(false);
-
-        // Now commit the provisional item
-        m_previousItem = m_currentItem;
-        m_currentItem = m_provisionalItem;
-        m_provisionalItem = 0;
-
-        // Restore form state (works from currentItem)
-        restoreDocumentState();
-
-        // Restore the scroll position (we choose to do this rather than going back to the anchor point)
-        restoreScrollPositionAndViewState();
     }
 
-    // Iterate over the rest of the tree
-    for (Frame* child = m_frame->tree()->firstChild(); child; child = child->tree()->nextSibling())
-        child->loader()->history()->recursiveUpdateForCommit();
+    OwnPtr<HistoryEntry> newEntry = HistoryEntry::create(targetItem);
+    Deque<HistoryNode*> historyNodes;
+    historyNodes.append(newEntry->rootHistoryNode());
+    while (!historyNodes.isEmpty()) {
+        // For each item, read the children (if any) off the HistoryItem,
+        // create a new HistoryNode for each child and attach it,
+        // then clear the children on the HistoryItem.
+        HistoryNode* historyNode = historyNodes.takeFirst();
+        const HistoryItemVector& children = historyNode->value()->children();
+        for (size_t i = 0; i < children.size(); i++) {
+            HistoryNode* childHistoryNode = historyNode->addChild(children[i].get());
+            historyNodes.append(childHistoryNode);
+        }
+        historyNode->value()->clearChildren();
+    }
+    goToEntry(newEntry.release());
 }
 
-void HistoryController::updateForSameDocumentNavigation()
+void HistoryController::setDefersLoading(bool defer)
 {
-    if (m_frame->document()->url().isEmpty())
-        return;
-
-    Page* page = m_frame->page();
-    if (!page)
-        return;
-
-    page->mainFrame()->loader()->history()->recursiveUpdateForSameDocumentNavigation();
-
-    if (m_currentItem)
-        m_currentItem->setURL(m_frame->document()->url());
+    m_defersLoading = defer;
+    if (!defer && m_deferredItem) {
+        goToItem(m_deferredItem.get());
+        m_deferredItem = 0;
+    }
 }
 
-void HistoryController::recursiveUpdateForSameDocumentNavigation()
+void HistoryController::updateForInitialLoadInChildFrame(Frame* frame, HistoryItem* item)
 {
-    // The frame that navigated will now have a null provisional item.
-    // Ignore it and its children.
-    if (!m_provisionalItem)
-        return;
-
-    // The provisional item may represent a different pending navigation.
-    // Don't commit it if it isn't a same document navigation.
-    if (m_currentItem && !m_currentItem->shouldDoSameDocumentNavigationTo(m_provisionalItem.get()))
+    ASSERT(frame->tree().parent());
+    if (!m_currentEntry)
         return;
-
-    // Commit the provisional item.
-    m_previousItem = m_currentItem;
-    m_currentItem = m_provisionalItem;
-    m_provisionalItem = 0;
-
-    // Iterate over the rest of the tree.
-    for (Frame* child = m_frame->tree()->firstChild(); child; child = child->tree()->nextSibling())
-        child->loader()->history()->recursiveUpdateForSameDocumentNavigation();
-}
-
-void HistoryController::setCurrentItem(HistoryItem* item)
-{
-    m_previousItem = m_currentItem;
-    m_currentItem = item;
-}
-
-void HistoryController::setCurrentItemTitle(const String& title)
-{
-    if (m_currentItem)
-        m_currentItem->setTitle(title);
-}
-
-bool HistoryController::currentItemShouldBeReplaced() const
-{
-    // From the HTML5 spec for location.assign():
-    //  "If the browsing context's session history contains only one Document,
-    //   and that was the about:blank Document created when the browsing context
-    //   was created, then the navigation must be done with replacement enabled."
-    return m_currentItem && !m_previousItem && equalIgnoringCase(m_currentItem->urlString(), blankURL());
-}
-
-void HistoryController::setProvisionalItem(HistoryItem* item)
-{
-    m_provisionalItem = item;
+    if (HistoryNode* existingChildHistoryNode = m_currentEntry->historyNodeForFrame(frame))
+        existingChildHistoryNode->updateValue(item);
+    else if (HistoryNode* parentHistoryNode = m_currentEntry->historyNodeForFrame(frame->tree().parent()))
+        parentHistoryNode->addChild(item);
+}
+
+// FIXME: This is a temporary hack designed to be mergeable to the 1750 branch.
+// As trunk stands currently, we should never clear the provisional entry, since it's
+// possible to clear based on a commit in an irrelevant frame. On trunk, the provisional entry is
+// an implementation detail of HistoryController and only used when we know that we're in
+// a back/forward navigation. Also, it is clobbered when a new history navigation begins,
+// so we can be sure that a stale provisional entry won't be confused with a new one.
+// On the branch, however, the provisional entry is observable because
+// WebFrameImpl::currentHistoryItem() will return data based on the provisional entry preferentially
+// over the current entry, so we can't leave a stale provisional entry around indefinitely.
+// Therefore, search the frame tree for any back/forward navigations in progress, and only clear
+// the provisional entry if none are found.
+// Once the fix is merged to the branch, this can be removed, along with all places that we clear
+// m_provisionalEntry.
+static bool shouldClearProvisionalEntry(Page* page)
+{
+    for (Frame* frame = page->mainFrame(); frame; frame = frame->tree().traverseNext()) {
+        if (frame->loader().loadType() == FrameLoadTypeBackForward)
+            return false;
+    }
+    return true;
 }
 
-void HistoryController::initializeItem(HistoryItem* item)
+void HistoryController::updateForCommit(Frame* frame, HistoryItem* item)
 {
-    DocumentLoader* documentLoader = m_frame->loader()->documentLoader();
-    ASSERT(documentLoader);
-
-    KURL unreachableURL = documentLoader->unreachableURL();
-
-    KURL url;
-    KURL originalURL;
-
-    if (!unreachableURL.isEmpty()) {
-        url = unreachableURL;
-        originalURL = unreachableURL;
-    } else {
-        url = documentLoader->url();
-        originalURL = documentLoader->originalURL();
+    FrameLoadType type = frame->loader().loadType();
+    if (isBackForwardLoadType(type) && m_provisionalEntry) {
+        // Once committed, we want to use current item for saving DocState, and
+        // the provisional item for restoring state.
+        // Note previousItem must be set before we close the URL, which will
+        // happen when the data source is made non-provisional below
+        m_previousEntry = m_currentEntry.release();
+        ASSERT(m_provisionalEntry);
+        m_currentEntry = m_provisionalEntry.release();
+    } else if (type != FrameLoadTypeRedirectWithLockedBackForwardList && shouldClearProvisionalEntry(m_page)) {
+        m_provisionalEntry.clear();
     }
 
-    // Frames that have never successfully loaded any content
-    // may have no URL at all. Currently our history code can't
-    // deal with such things, so we nip that in the bud here.
-    // Later we may want to learn to live with nil for URL.
-    // See bug 3368236 and related bugs for more information.
-    if (url.isEmpty())
-        url = blankURL();
-    if (originalURL.isEmpty())
-        originalURL = blankURL();
-
-    Frame* parentFrame = m_frame->tree()->parent();
-    String parent = parentFrame ? parentFrame->tree()->uniqueName() : "";
-
-    item->setURL(url);
-    item->setTarget(m_frame->tree()->uniqueName());
-    item->setParent(parent);
-    // FIXME: should store title directionality in history as well.
-    item->setTitle(m_frame->document()->title());
-    item->setOriginalURLString(originalURL.string());
-
-    // Save form state if this is a POST
-    item->setFormInfoFromRequest(documentLoader->request());
+    if (type == FrameLoadTypeStandard)
+        createNewBackForwardItem(frame, item, true);
+    else if (type == FrameLoadTypeInitialInChildFrame)
+        updateForInitialLoadInChildFrame(frame, item);
 }
 
-PassRefPtr<HistoryItem> HistoryController::createItem()
+static PassRefPtr<HistoryItem> itemForExport(HistoryNode* historyNode)
 {
-    RefPtr<HistoryItem> item = HistoryItem::create();
-    initializeItem(item.get());
-
-    // Set the item for which we will save document state
-    m_previousItem = m_currentItem;
-    m_currentItem = item;
-
-    return item.release();
+    RefPtr<HistoryItem> item = historyNode->value()->copy();
+    const Vector<OwnPtr<HistoryNode> >& childEntries = historyNode->children();
+    for (size_t i = 0; i < childEntries.size(); i++)
+        item->addChildItem(itemForExport(childEntries[i].get()));
+    return item;
 }
 
-PassRefPtr<HistoryItem> HistoryController::createItemTree(Frame* targetFrame, bool clipAtTarget)
+PassRefPtr<HistoryItem> HistoryController::currentItemForExport()
 {
-    RefPtr<HistoryItem> bfItem = createItem();
-    saveScrollPositionAndViewStateToItem(m_previousItem.get());
-
-    if (!clipAtTarget || m_frame != targetFrame) {
-        // save frame state for items that aren't loading (khtml doesn't save those)
-        saveDocumentState();
-
-        // clipAtTarget is false for navigations within the same document, so
-        // we should copy the documentSequenceNumber over to the newly create
-        // item.  Non-target items are just clones, and they should therefore
-        // preserve the same itemSequenceNumber.
-        if (m_previousItem) {
-            if (m_frame != targetFrame)
-                bfItem->setItemSequenceNumber(m_previousItem->itemSequenceNumber());
-            bfItem->setDocumentSequenceNumber(m_previousItem->documentSequenceNumber());
-        }
-
-        for (Frame* child = m_frame->tree()->firstChild(); child; child = child->tree()->nextSibling()) {
-            // If the child is a frame corresponding to an <object> element that never loaded,
-            // we don't want to create a history item, because that causes fallback content
-            // to be ignored on reload.
-            FrameLoader* childLoader = child->loader();
-            if (childLoader->stateMachine()->startedFirstRealLoad() || !child->ownerElement()->isObjectElement())
-                bfItem->addChildItem(childLoader->history()->createItemTree(targetFrame, clipAtTarget));
-        }
-    }
-    // FIXME: Eliminate the isTargetItem flag in favor of itemSequenceNumber.
-    if (m_frame == targetFrame)
-        bfItem->setIsTargetItem(true);
-    return bfItem;
+    if (!m_currentEntry)
+        return 0;
+    return itemForExport(m_currentEntry->rootHistoryNode());
 }
 
-// The general idea here is to traverse the frame tree and the item tree in parallel,
-// tracking whether each frame already has the content the item requests.  If there is
-// a match, we set the provisional item and recurse.  Otherwise we will reload that
-// frame and all its kids in recursiveGoToItem.
-void HistoryController::recursiveSetProvisionalItem(HistoryItem* item, HistoryItem* fromItem)
+PassRefPtr<HistoryItem> HistoryController::previousItemForExport()
 {
-    ASSERT(item);
-
-    if (itemsAreClones(item, fromItem)) {
-        // Set provisional item, which will be committed in recursiveUpdateForCommit.
-        m_provisionalItem = item;
-
-        const HistoryItemVector& childItems = item->children();
-
-        int size = childItems.size();
-
-        for (int i = 0; i < size; ++i) {
-            String childFrameName = childItems[i]->target();
-            HistoryItem* fromChildItem = fromItem->childItemWithTarget(childFrameName);
-            ASSERT(fromChildItem);
-            Frame* childFrame = m_frame->tree()->child(childFrameName);
-            ASSERT(childFrame);
-            childFrame->loader()->history()->recursiveSetProvisionalItem(childItems[i].get(), fromChildItem);
-        }
-    }
-}
-
-// We now traverse the frame tree and item tree a second time, loading frames that
-// do have the content the item requests.
-void HistoryController::recursiveGoToItem(HistoryItem* item, HistoryItem* fromItem)
-{
-    ASSERT(item);
-
-    if (itemsAreClones(item, fromItem)) {
-        // Just iterate over the rest, looking for frames to navigate.
-        const HistoryItemVector& childItems = item->children();
-
-        int size = childItems.size();
-        for (int i = 0; i < size; ++i) {
-            String childFrameName = childItems[i]->target();
-            HistoryItem* fromChildItem = fromItem->childItemWithTarget(childFrameName);
-            ASSERT(fromChildItem);
-            Frame* childFrame = m_frame->tree()->child(childFrameName);
-            ASSERT(childFrame);
-            childFrame->loader()->history()->recursiveGoToItem(childItems[i].get(), fromChildItem);
-        }
-    } else {
-        m_frame->loader()->loadHistoryItem(item);
-    }
+    if (!m_previousEntry)
+        return 0;
+    return itemForExport(m_previousEntry->rootHistoryNode());
 }
 
-bool HistoryController::itemsAreClones(HistoryItem* item1, HistoryItem* item2) const
+PassRefPtr<HistoryItem> HistoryController::provisionalItemForExport()
 {
-    // If the item we're going to is a clone of the item we're at, then we do
-    // not need to load it again.  The current frame tree and the frame tree
-    // snapshot in the item have to match.
-    // Note: Some clients treat a navigation to the current history item as
-    // a reload.  Thus, if item1 and item2 are the same, we need to create a
-    // new document and should not consider them clones.
-    // (See http://webkit.org/b/35532 for details.)
-    return item1
-        && item2
-        && item1 != item2
-        && item1->itemSequenceNumber() == item2->itemSequenceNumber()
-        && currentFramesMatchItem(item1)
-        && item2->hasSameFrames(item1);
+    if (!m_provisionalEntry)
+        return 0;
+    return itemForExport(m_provisionalEntry->rootHistoryNode());
 }
 
-// Helper method that determines whether the current frame tree matches given history item's.
-bool HistoryController::currentFramesMatchItem(HistoryItem* item) const
+HistoryItem* HistoryController::itemForNewChildFrame(Frame* frame) const
 {
-    if ((!m_frame->tree()->uniqueName().isEmpty() || !item->target().isEmpty()) && m_frame->tree()->uniqueName() != item->target())
-        return false;
-
-    const HistoryItemVector& childItems = item->children();
-    if (childItems.size() != m_frame->tree()->childCount())
-        return false;
-
-    unsigned size = childItems.size();
-    for (unsigned i = 0; i < size; ++i) {
-        if (!m_frame->tree()->child(childItems[i]->target()))
-            return false;
-    }
-
-    return true;
+    return m_currentEntry ? m_currentEntry->itemForFrame(frame) : 0;
 }
 
-void HistoryController::updateBackForwardListClippedAtTarget(bool doClip)
+void HistoryController::removeChildrenForRedirect(Frame* frame)
 {
-    // In the case of saving state about a page with frames, we store a tree of items that mirrors the frame tree.
-    // The item that was the target of the user's navigation is designated as the "targetItem".
-    // When this function is called with doClip=true we're able to create the whole tree except for the target's children,
-    // which will be loaded in the future. That part of the tree will be filled out as the child loads are committed.
-
-    Page* page = m_frame->page();
-    if (!page)
-        return;
-
-    if (m_frame->loader()->documentLoader()->urlForHistory().isEmpty())
+    if (!m_provisionalEntry)
         return;
-
-    Frame* mainFrame = page->mainFrame();
-    ASSERT(mainFrame);
-
-    RefPtr<HistoryItem> topItem = mainFrame->loader()->history()->createItemTree(m_frame, doClip);
-    LOG(BackForward, "WebCoreBackForward - Adding backforward item %p for frame %s", topItem.get(), m_frame->loader()->documentLoader()->url().string().ascii().data());
-    page->backForward().addItem(topItem.release());
+    if (HistoryNode* node = m_provisionalEntry->historyNodeForFrame(frame))
+        node->removeChildren();
 }
 
-void HistoryController::updateCurrentItem()
+void HistoryController::createNewBackForwardItem(Frame* targetFrame, HistoryItem* item, bool clipAtTarget)
 {
-    if (!m_currentItem)
-        return;
-
-    DocumentLoader* documentLoader = m_frame->loader()->documentLoader();
-
-    if (!documentLoader->unreachableURL().isEmpty())
-        return;
-
-    if (m_currentItem->url() != documentLoader->url()) {
-        // We ended up on a completely different URL this time, so the HistoryItem
-        // needs to be re-initialized.  Preserve the isTargetItem flag as it is a
-        // property of how this HistoryItem was originally created and is not
-        // dependent on the document.
-        bool isTargetItem = m_currentItem->isTargetItem();
-        m_currentItem->reset();
-        initializeItem(m_currentItem.get());
-        m_currentItem->setIsTargetItem(isTargetItem);
+    RefPtr<HistoryItem> newItem = item;
+    if (!m_currentEntry) {
+        m_currentEntry = HistoryEntry::create(newItem.get());
     } else {
-        // Even if the final URL didn't change, the form data may have changed.
-        m_currentItem->setFormInfoFromRequest(documentLoader->request());
+        HistoryItem* oldItem = m_currentEntry->itemForFrame(targetFrame);
+        if (!clipAtTarget && oldItem)
+            newItem->setDocumentSequenceNumber(oldItem->documentSequenceNumber());
+        m_previousEntry = m_currentEntry.release();
+        m_currentEntry = m_previousEntry->cloneAndReplace(newItem.get(), clipAtTarget, targetFrame, m_page);
     }
 }
 
-void HistoryController::pushState(PassRefPtr<SerializedScriptValue> stateObject, const String& title, const String& urlString)
-{
-    if (!m_currentItem)
-        return;
-
-    Page* page = m_frame->page();
-    ASSERT(page);
-
-    // Get a HistoryItem tree for the current frame tree.
-    RefPtr<HistoryItem> topItem = page->mainFrame()->loader()->history()->createItemTree(m_frame, false);
-
-    // Override data in the current item (created by createItemTree) to reflect
-    // the pushState() arguments.
-    m_currentItem->setTitle(title);
-    m_currentItem->setStateObject(stateObject);
-    m_currentItem->setURLString(urlString);
-    page->backForward().addItem(topItem.release());
-}
-
-void HistoryController::replaceState(PassRefPtr<SerializedScriptValue> stateObject, const String& title, const String& urlString)
-{
-    if (!m_currentItem)
-        return;
-
-    if (!urlString.isEmpty())
-        m_currentItem->setURLString(urlString);
-    m_currentItem->setTitle(title);
-    m_currentItem->setStateObject(stateObject);
-    m_currentItem->setFormData(0);
-    m_currentItem->setFormContentType(String());
-
-    ASSERT(m_frame->page());
-}
-
 } // namespace WebCore