Split the frame tree logic out of HistoryItem

Split the frame tree logic out of HistoryItem

This is a proposal for separating the per-frame data we need for history from
the frame-tree that HistoryItem stores.

This patch introduces HistoryEntry, which is basically a wrapper around
a tree of HistoryEntryItems. HistoryEntryItem contains a HistoryItem (which
stores the relevant data for the frame) and a vector of child
HistoryEntryItems. Multiple HistoryEntryItems can hold references to the same
HistoryItem. HistoryEntry/HistoryEntryItem have logic for doing a parital
clone of themselves while replacing the navigated item.

HistoryEntry keeps 2 maps. One maps frame ids (which are new) to HistoryEntryItems, the other maps FrameTree::uniqueName() to HistoryEntryItems. The frame id maps is sufficient for the vast majority of cases, but a secondary mechanism for finding a HistoryEntryItem is necessary when doing a back/forward navigation with iframes, as child iframes may want to load from history, but the HistoryEntry may not know about the new Frame object yet.

HistoryController know lives in Page, though for simplicity I left a helper
on FrameLoader that gets the Page's HistoryController.

This patch doesn't plumb the new data model all the way out, so HistoryController retains a mechanic for converting between the old HistoryItem child tree and the HistoryEntry tree.

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=162131

[Charlie Reis, 2013-10-19 00:44:15]

Very cool.  I haven't looked at the details closely, but this seems like a nice
step towards having Blink only keep track of single-frame HistoryItems.  I
assume HistoryEntry is just a temporary step until we move the tree of
serialized HistoryItems to the browser process.

https://codereview.chromium.org/28983004/diff/1/Source/core/history/HistoryIt...
File Source/core/history/HistoryItem.cpp (left):

https://codereview.chromium.org/28983004/diff/1/Source/core/history/HistoryIt...
Source/core/history/HistoryItem.cpp:205: void
HistoryItem::addChildItem(PassRefPtr<HistoryItem> child)
Why do we still need addChildItem or m_children on HistoryItem?  Seems like
we've removed many of the uses of the children below.  Is it just so we can
export them to WebHistoryItem?

(I suppose the next step would be having WebHistoryItem wrap a HistoryEntry
instead of a HistoryItem, and then remove m_children here?)

[Nate Chapin, 2013-10-21 18:55:18]

On 2013/10/19 00:44:15, creis wrote:
> Very cool.  I haven't looked at the details closely, but this seems like a
nice
> step towards having Blink only keep track of single-frame HistoryItems.  I
> assume HistoryEntry is just a temporary step until we move the tree of
> serialized HistoryItems to the browser process.

That's the theory. It just seems like the same data structure model as you were
suggestion for the browser process (and I think it sounds like the right model,
too).

> 
>
https://codereview.chromium.org/28983004/diff/1/Source/core/history/HistoryIt...
> File Source/core/history/HistoryItem.cpp (left):
> 
>
https://codereview.chromium.org/28983004/diff/1/Source/core/history/HistoryIt...
> Source/core/history/HistoryItem.cpp:205: void
> HistoryItem::addChildItem(PassRefPtr<HistoryItem> child)
> Why do we still need addChildItem or m_children on HistoryItem?  Seems like
> we've removed many of the uses of the children below.  Is it just so we can
> export them to WebHistoryItem?
> 
> (I suppose the next step would be having WebHistoryItem wrap a HistoryEntry
> instead of a HistoryItem, and then remove m_children here?)

That's the idea. I figured it made sense to change core's internal data
structures, then propagate that out in the second step. We'll see if I can get
the halfway solution working :)

[Nate Chapin, 2013-10-29 19:30:47]

This new version passes all layout tests and webkit unit tests locally. 

The downside is that it will require a multi-sided patch, because it adds a
unique frame id that needs to be serialized on the chromium side.

[abarth-chromium, 2013-10-29 20:27:19]

> This patch still fails ~50 layout

Looks like you need to update the description.

[abarth-chromium, 2013-10-29 20:36:57]

https://codereview.chromium.org/28983004/diff/60001/Source/core/frame/Frame.h
File Source/core/frame/Frame.h (right):

https://codereview.chromium.org/28983004/diff/60001/Source/core/frame/Frame.h...
Source/core/frame/Frame.h:192: int64_t m_id;
We should make sure creis sees this change to make sure it harmonizes with OOPIF

https://codereview.chromium.org/28983004/diff/60001/Source/core/history/Histo...
File Source/core/history/HistoryItem.h (right):

https://codereview.chromium.org/28983004/diff/60001/Source/core/history/Histo...
Source/core/history/HistoryItem.h:94: void setTargetFrameID(int64_t number) {
m_targetFrameID = number; }
s/number/id/ ?

https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/FrameL...
File Source/core/loader/FrameLoader.cpp (right):

https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/FrameL...
Source/core/loader/FrameLoader.cpp:157: , m_history(frame->page()->history())
Don't we need to clear out m_history when the Frame detaches from the Page? 
Otherwise, the Page can die and we'll have a dangling pointer to the
HistoryController.  Maybe instead of caching a pointer here we should just
always grab the canonical one from the page?

HistoryController* history() const { return m_frame->page() ?
m_frame->page()->history() : 0; }

All the callers of this function need to worry about the case when we're
detached from the page and we've lost the connection to the history controller.

https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/Histor...
File Source/core/loader/HistoryController.h (right):

https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/Histor...
Source/core/loader/HistoryController.h:84: HashMap<uint64_t, HistoryEntryItem*>
m_framesToItems;
uint64_t -> I wonder if we should have a typedef for readability.

[Nate Chapin, 2013-11-11 17:52:42]

On 2013/10/29 20:36:57, abarth wrote:
> https://codereview.chromium.org/28983004/diff/60001/Source/core/frame/Frame.h
> File Source/core/frame/Frame.h (right):
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/frame/Frame.h...
> Source/core/frame/Frame.h:192: int64_t m_id;
> We should make sure creis sees this change to make sure it harmonizes with
OOPIF
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/history/Histo...
> File Source/core/history/HistoryItem.h (right):
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/history/Histo...
> Source/core/history/HistoryItem.h:94: void setTargetFrameID(int64_t number) {
> m_targetFrameID = number; }
> s/number/id/ ?
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/FrameL...
> File Source/core/loader/FrameLoader.cpp (right):
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/FrameL...
> Source/core/loader/FrameLoader.cpp:157: , m_history(frame->page()->history())
> Don't we need to clear out m_history when the Frame detaches from the Page? 
> Otherwise, the Page can die and we'll have a dangling pointer to the
> HistoryController.  Maybe instead of caching a pointer here we should just
> always grab the canonical one from the page?
> 
> HistoryController* history() const { return m_frame->page() ?
> m_frame->page()->history() : 0; }
> 
> All the callers of this function need to worry about the case when we're
> detached from the page and we've lost the connection to the history
controller.
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/Histor...
> File Source/core/loader/HistoryController.h (right):
> 
>
https://codereview.chromium.org/28983004/diff/60001/Source/core/loader/Histor...
> Source/core/loader/HistoryController.h:84: HashMap<uint64_t,
HistoryEntryItem*>
> m_framesToItems;
> uint64_t -> I wonder if we should have a typedef for readability.

Ok, I think previous review comments and trybot objections have all been
addressed. Ready for review!

[abarth-chromium, 2013-11-13 19:15:37]

LGTM, but it's likely I wouldn't find subtle bugs in this CL.  The design looks
like what you explained before.  When you're happy with how this works, it might
be worth writing a largish comment explaining how it's supposed to work.

Minor comments below.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
File Source/core/loader/HistoryController.cpp (right):

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.cpp:85:
m_entry->m_framesToItems.add(value->targetFrameID(), this);
I didn't see any calls to remove on this map.  I guess there's an invariant that
HistoryEntries only grow.  Look at the code, that seems to be the case, but I
wanted to mention it explicitly in this comment in case I'm misunderstanding.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
File Source/core/loader/HistoryController.h (right):

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:48: class HistoryEntryItem {
HistoryNode?

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:72: HistoryEntryItem*
entryForFrame(Frame*);
It's awkward that this returns a HistoryEntryItem rather than an HistoryEntry
given the name of the function.  If you rename HistoryEntryItem to HistoryNode,
consider renaming this function to historyNodeForFrame.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:75: HistoryEntryItem* rootEntry() const {
return m_root.get(); }
Same comment here w/ rootNode

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:85: HashMap<String, HistoryEntryItem*>
m_uniqueNamesToItems;
It's unfortunate that we need both these maps...  Is there a future for this
code in which we could get down to one map?

[Nate Chapin, 2013-11-13 19:30:38]

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
File Source/core/loader/HistoryController.cpp (right):

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.cpp:85:
m_entry->m_framesToItems.add(value->targetFrameID(), this);
On 2013/11/13 19:15:37, abarth wrote:
> I didn't see any calls to remove on this map.  I guess there's an invariant
that
> HistoryEntries only grow.  Look at the code, that seems to be the case, but I
> wanted to mention it explicitly in this comment in case I'm misunderstanding.

AFAICT, that's how HistoryController work on trunk, too. Once a HistoryItem is
added to the tree, it isn't removed, though it's possible that, on back/forward
navigation, it won't actually be requested during initial load.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
File Source/core/loader/HistoryController.h (right):

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:48: class HistoryEntryItem {
On 2013/11/13 19:15:37, abarth wrote:
> HistoryNode?

Yeah, that's a better name. Will change it.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:72: HistoryEntryItem*
entryForFrame(Frame*);
On 2013/11/13 19:15:37, abarth wrote:
> It's awkward that this returns a HistoryEntryItem rather than an HistoryEntry
> given the name of the function.  If you rename HistoryEntryItem to
HistoryNode,
> consider renaming this function to historyNodeForFrame.

Will do.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:75: HistoryEntryItem* rootEntry() const {
return m_root.get(); }
On 2013/11/13 19:15:37, abarth wrote:
> Same comment here w/ rootNode

Will do.

https://codereview.chromium.org/28983004/diff/510001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:85: HashMap<String, HistoryEntryItem*>
m_uniqueNamesToItems;
On 2013/11/13 19:15:37, abarth wrote:
> It's unfortunate that we need both these maps...  Is there a future for this
> code in which we could get down to one map?

Yeah, it's lame, and I'm not sure there's a way around it. You need the
names->items mapping to handle the back/forward case where the frame doesn't
exist yet, and you need some way to make the system resilient to the frame name
(and therefore the uniqueName) changing, so you either need to index all current
and former names, or have something that doesn't change when the name changes
(the frameid->item mapping). This seemed the least terrible and most stable
option I could think of, but I don't immediately see how to fix it.

[Nate Chapin, 2013-11-13 21:49:42]

Comments addressed. I'd appreciate a proofread of my wall of text before
submitting.

[Nate Chapin, 2013-11-13 21:49:58]

On 2013/11/13 21:49:42, Nate Chapin wrote:
> Comments addressed. I'd appreciate a proofread of my wall of text before
> submitting.

(It's near the top of HistoryContorller.h)

[abarth-chromium, 2013-11-14 05:37:30]

Looks great!

https://codereview.chromium.org/28983004/diff/660001/Source/core/loader/Histo...
File Source/core/loader/HistoryController.h (right):

https://codereview.chromium.org/28983004/diff/660001/Source/core/loader/Histo...
Source/core/loader/HistoryController.h:58: // the strucutre of the page, but
don't hold any per-frame state except a list of child frames.
strucutre -> structure

[commit-bot: I haz the power, 2013-11-14 22:15:09]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/japhet@chromium.org/28983004/740001

[commit-bot: I haz the power, 2013-11-15 19:05:32]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/japhet@chromium.org/28983004/910001

[commit-bot: I haz the power, 2013-11-15 20:48:39]

Change committed as 162131