*** FOR PROTOTYPE PURPOSES ONLY! NOT INTENDED FOR COMMIT! ***

*** FOR PROTOTYPE PURPOSES ONLY! NOT INTENDED FOR COMMIT! ***

Non-recursive layout for the RenderBlockFlow class and all of its subclasses

Non-recursive layout for the RenderBlockFlow class and all of its subclasses.  This
is my first attempt at a prototype for how we can incrementally change over the various
render tree classes to use non-recursive layout both for tree traversal and for
multiple passes.

The key to this prototype is found in the RenderObject::nextForLayout method which
introduces a non-recursive algorithm for traversing the render tree in both pre and
post order.  It also takes care of switching between recursive and non-recursive
tree traversal for those nodes that do not yet support non-recursive layout.  I
developed this algorithm by creating a toy model of the render tree and its layout
methods.

A couple of big architectural changes come to light with this prototype:

1) It becomes necessary to split up the current ::layout* methods into pre and post
order methods.  Currently, most nodes do some layout work *before* visiting children
and then some more work *after* visiting children.  This is accomplished with recursion
by recursing into children in the middle of the current ::layout methods and holding
state on the stack.  With non-recursive traversal we have to explicitly visit each node
in pre-order and then in post-order.

NOTE: One potentially good part of this split up into pre/post part is perhaps
a performance gain to be had in the case of multiple passes.  Right now, I believe
multiple passes is unnecessarily executing code paths that are unnecessary and
we might be able to reduce this by splitting up the layout method with more granularity.

2) We need to store all the state that was previously held on the stack frame in
another fashion.  This patch just does the dumb thing and adds that state as member
variables to the RenderObject subclass.  Obviously, this is less than adequate and
we'll need to find a better way to allocate and maintain this state and the lifetime
thereof.  I've left that work until we can talk it over how best to do it.  The first
thought that comes to mind is using the current LayoutState, but we have to be careful
not to make this more complicated than necessary as LayoutState currently holds state
that is more or less used by all the render tree subclasses.

3) One obvious advantage of using non-recursive layout is the fact that we can be explicit
where we put the tree traversal.  Right now, the tree traversal is hidden deep within
the layout methods because of #1.  Although I haven't had time to do it yet, this patch
hopefully makes it clear that this traveral can be moved to the head of the layout method.

I've added various comments in the code where I think it helps to make clear what
is going on.  To be clear, there is plenty more work to be done.  Right now this patch
passes all layout 10,000+ fast tests when using the default recursive method, but
still fails on roughly 500 tests when switched to non-recursive.

Hopefully, this is enough to see where this is headed and to evaluate before going
further.

*** FOR PROTOTYPE PURPOSES ONLY! NOT INTENDED FOR COMMIT! ***

BUG=

[atreat, 2014-02-14 21:19:16]

Please have a look :)

[esprehn, 2014-02-15 00:35:43]

Adding tons of member variables isn't going to work, you also can't malloc
structures for every layout like the MarginInfo

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlockFlow.cpp (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.cpp:522: m_statePusher = 0;
This should be an OwnPtr you just clear.

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.cpp:597: m_childNeededLayout =
child->needsLayout();
This doesn't feel right. Storing so much state in the render object is not good.

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.cpp:952: m_marginInfo = new
MarginInfo(this, beforeEdge, afterEdge);
Adding more mallocs doesn't seem like the right way to go. Now you cause a
malloc per block as we walk down the tree.

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlockFlow.h (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.h:577: bool m_childNeededLayout;
This is huge, I don't think you can make RenderBlockFlow this large.

[eseidel, 2014-02-15 00:37:18]

I think this is very intresting.  I will need to read it more carefully when I'm
less tired. :)

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlock.cpp (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlock.cpp:1311: LayoutRectRecorder recorder(*this);
This won't work, it will expect that layout is done when its destructor is
called.

One of the unfortunate effects of splitting layout() into halves is that all of
our existing RAIIs (like this one) will be confused.  We'll need to instead push
these RAIIs on a stack?

[atreat, 2014-02-18 16:03:56]

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlock.cpp (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlock.cpp:1311: LayoutRectRecorder recorder(*this);
On 2014/02/15 00:37:18, eseidel wrote:
> This won't work, it will expect that layout is done when its destructor is
> called.
> 
> One of the unfortunate effects of splitting layout() into halves is that all
of
> our existing RAIIs (like this one) will be confused.  We'll need to instead
push
> these RAIIs on a stack?

Yes, this one I missed and we'll need a stack.  More on that in another comment.

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlockFlow.cpp (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.cpp:597: m_childNeededLayout =
child->needsLayout();
On 2014/02/15 00:35:43, esprehn wrote:
> This doesn't feel right. Storing so much state in the render object is not
good.

Right, see the comment in the header file.  We'll need to figure out where/how
to store this state.

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlockFlow.h (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlockFlow.h:577: bool m_childNeededLayout;
On 2014/02/15 00:35:43, esprehn wrote:
> This is huge, I don't think you can make RenderBlockFlow this large.

No, of course not.  That is why I said in the comment that this is for prototype
purposes and we'll need a better way to handle the state.  I could have put this
in LayoutState, but I did not want to complicate the prototype and I wanted to
discuss with you guys the best way to manage this state

My current thinking is to add an InternalLayoutState to LayoutState that each
class could override that would provide a place to hold this state.

[dsinclair, 2014-02-18 16:07:05]

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlock.cpp (right):

https://codereview.chromium.org/166033009/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlock.cpp:1311: LayoutRectRecorder recorder(*this);
On 2014/02/18 16:03:57, atreat wrote:
> On 2014/02/15 00:37:18, eseidel wrote:
> > This won't work, it will expect that layout is done when its destructor is
> > called.
> > 
> > One of the unfortunate effects of splitting layout() into halves is that all
> of
> > our existing RAIIs (like this one) will be confused.  We'll need to instead
> push
> > these RAIIs on a stack?
> 
> Yes, this one I missed and we'll need a stack.  More on that in another
comment.


LayoutRectRecorder should be fine, you just have to make sure you create it in
both the pre and post layout. It's already designed that if you call it multiple
times it will set the oldRepaintRect size and won't over-write it, but it will
over-write newRepaintRect when it's created a second time. So, you shouldn't
need a special stack of them.