[LayoutNG] Initial support for multicol, introducing NGBlockBreakToken.

[LayoutNG] Initial support for multicol, introducing NGBlockBreakToken.

We can now lay out block-level floats and in-flow blocks inside a multicol
container. Note that painting and hit testing doesn't work too well, since
those operations are still performed on the legacy LayoutObject tree, and
there's no way to fragment a LayoutObject.

No attempt has been made at integrating this with out-of-flow positioning or
inline-level layout.

Review-Url: https://codereview.chromium.org/2632523002
Cr-Commit-Position: refs/heads/master@{#444512}
Committed: https://chromium.googlesource.com/chromium/src/+/24bfa2fe65cc6bb73338d9d7a2f2175efee45c83

[mstensho (USE GERRIT), 2017-01-12 22:49:51]

The CQ bit was checked by mstensho@opera.com to run a CQ dry run

[commit-bot: I haz the power, 2017-01-12 22:51:16]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[mstensho (USE GERRIT), 2017-01-12 22:53:57]

mstensho@opera.com changed reviewers:
+ eae@chromium.org, ikilpatrick@chromium.org

[mstensho (USE GERRIT), 2017-01-12 22:53:58]

@ikilpatrick: Note that the NGBlockBreakToken is quite different (simpler)
compared to what you sketched in an e-mail to me. Maybe I got it all wrong, or
maybe this will do. Please let me know. :)

I should probably add more tests (e.g. for the new class NGColumnMapper), but
I'd like some feedback first, to figure out whether I'm on the right track at
all.

[eae, 2017-01-12 23:11:33]

Love it!

[eae, 2017-01-12 23:11:44]

(detailed review to follow)

[eae, 2017-01-12 23:36:23]

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:473: if
(!fragmentainer_mapper_) {
When is fragmentainer_mapper_ expected to be null?

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm_test.cc
(right):

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm_test.cc:850:
class FragmentChildIterator
This class seem pretty useful, perhaps move out of the test class?

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/ng/ng_column_mapper.h (right):

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_column_mapper.h:51:
NGBlockBreakToken* Advance() {
DCHECK(break_token_) or are there cases when we might call advance with a
break_token_ of null?

[commit-bot: I haz the power, 2017-01-13 00:58:09]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-01-13 00:58:10]

Dry run: This issue passed the CQ dry run.

[mstensho (USE GERRIT), 2017-01-13 14:30:18]

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:473: if
(!fragmentainer_mapper_) {
On 2017/01/12 23:36:23, eae wrote:
> When is fragmentainer_mapper_ expected to be null?

Almost "always". :) It's only set on the root fragmentation context algorithms,
e.g. on the very block that specifies columns.

I added a comment about it now, where fragmentainer_mapper_ is defined.

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm_test.cc
(right):

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm_test.cc:850:
class FragmentChildIterator
On 2017/01/12 23:36:23, eae wrote:
> This class seem pretty useful, perhaps move out of the test class?

Are you suggesting that I move it out to a separate header and name it
NGPhysicalBoxFragmentIterator or something? I wanted something quick and simple
that only worked on physical box fragments (since that's what the tests are
interested in), which ignores all other types of fragments. Not sure how useful
or non-confusing that would be outside of tests.

Maybe add a more generic NGPhysicalFragmentIterator, and keep a subclass here
that filters out non-box fragments?

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/ng/ng_column_mapper.h (right):

https://codereview.chromium.org/2632523002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_column_mapper.h:51:
NGBlockBreakToken* Advance() {
On 2017/01/12 23:36:23, eae wrote:
> DCHECK(break_token_) or are there cases when we might call advance with a
> break_token_ of null?

The idea was that it should be legal for break_token_ to be null (and we do cope
with such a situation both here and at the call site), but right now I cannot
think of a situation where it may happen.

[eae, 2017-01-17 02:56:28]

Thanks for the clarifications, makes a lot more sense now!

LGTM

[ikilpatrick, 2017-01-17 04:40:21]

I'll have a look tomorrow Morten :).

[ikilpatrick, 2017-01-18 02:12:22]

lgtm

Have a look at the IsLayoutFinished comment.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:281: new
NGColumnMapper(inline_progression, adjusted_block_size);
this is just local to a single instance of this algorithm right? No side effects
leak out?

(i'm pretty sure it is, just checking).

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:443: while
(current_child_ && current_child_->IsLayoutFinished())
hmmm..., is there any way to encode the "IsLayoutFinished" information inside
the break token? I think this leaks a side-effect (we want to keep LayoutInput
(ConstraintSpace, BreakToken, etc) immutable, and the output Immutable).

I'm fine with adding a TODO here to fix this.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:457: //
block right away, due to the posibility of parallel flows. We can only
this doesn't support parallel flows yet right?

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:459: //
process.
Thank you for the detailed comments :)

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_constraint_space.h (right):

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_constraint_space.h:75: return
fragmentainer_space_available_;
does a DCHECK(HasBlockFragmentation()) make sense here?

[mstensho (USE GERRIT), 2017-01-18 11:52:10]

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:281: new
NGColumnMapper(inline_progression, adjusted_block_size);
On 2017/01/18 02:12:22, ikilpatrick wrote:
> this is just local to a single instance of this algorithm right? No side
effects
> leak out?
> 
> (i'm pretty sure it is, just checking).

Correct.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:443: while
(current_child_ && current_child_->IsLayoutFinished())
On 2017/01/18 02:12:21, ikilpatrick wrote:
> hmmm..., is there any way to encode the "IsLayoutFinished" information inside
> the break token? I think this leaks a side-effect (we want to keep LayoutInput
> (ConstraintSpace, BreakToken, etc) immutable, and the output Immutable).
> 
> I'm fine with adding a TODO here to fix this.

I don't quite understand what you mean. If layout is finished, there'll be no
break token on the last fragment. And that's what IsLayoutFinished() checks;
we're not finished if we have no fragment, or if the last fragment has a break
token.

BlockNode (a LayoutInputNode) certainly isn't immutable today, since it has a
fragment pointer, which is updated when a fragment is created. This wasn't
introduced by this CL, though.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:457: //
block right away, due to the posibility of parallel flows. We can only
On 2017/01/18 02:12:21, ikilpatrick wrote:
> this doesn't support parallel flows yet right?

Yes, it does. :) We both support content beside floats and also parallel flow
situations that arise when overflowing the bottom of a block.

See the new unit tests that have "Float" in their name, and also
OverflowedBlock.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_constraint_space.h (right):

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_constraint_space.h:75: return
fragmentainer_space_available_;
On 2017/01/18 02:12:22, ikilpatrick wrote:
> does a DCHECK(HasBlockFragmentation()) make sense here?

I was thinking that it would be okay to call this method regardless of
fragmentation (and return indefinite if we're not in a fragmentation context),
but maybe that's not going to be necessary. At least it's not currently. I'll
add a DCHECK.

Done.

[ikilpatrick, 2017-01-18 18:46:47]

still lgtm, I'm fine with addressing issues in a followup patch.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:443: while
(current_child_ && current_child_->IsLayoutFinished())
On 2017/01/18 11:52:09, mstensho wrote:
> On 2017/01/18 02:12:21, ikilpatrick wrote:
> > hmmm..., is there any way to encode the "IsLayoutFinished" information
inside
> > the break token? I think this leaks a side-effect (we want to keep
LayoutInput
> > (ConstraintSpace, BreakToken, etc) immutable, and the output Immutable).
> > 
> > I'm fine with adding a TODO here to fix this.
> 
> I don't quite understand what you mean. If layout is finished, there'll be no
> break token on the last fragment. And that's what IsLayoutFinished() checks;
> we're not finished if we have no fragment, or if the last fragment has a break
> token.
> 
> BlockNode (a LayoutInputNode) certainly isn't immutable today, since it has a
> fragment pointer, which is updated when a fragment is created. This wasn't
> introduced by this CL, though.

So take the example where the caller of this function calls it twice with a
different break token, e.g.

NGBreakToken* break_token = /* from a previous layout or something */;

NGAlgorithm algorithm(style, children, constraint_space, break_token);
NGFragment* fragment = algorithm->Layout();

// Parent inspects the fragment and decides that it doesn't like the result.
if (fragment->BlockSize() > kConstant) {
  NGAlgorithm algorithm2(style, children, constraint_space, break_token);
  fragment = algorithm2->Layout(); // This may produce a bad result because
IsLayoutFinished() returns true.
}

Does that make sense?

Basically we need to encode that the a child is "done" inside the break token
for the above to work.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:457: //
block right away, due to the posibility of parallel flows. We can only
On 2017/01/18 11:52:09, mstensho wrote:
> On 2017/01/18 02:12:21, ikilpatrick wrote:
> > this doesn't support parallel flows yet right?
> 
> Yes, it does. :) We both support content beside floats and also parallel flow
> situations that arise when overflowing the bottom of a block.
> 
> See the new unit tests that have "Float" in their name, and also
> OverflowedBlock.

Sg. Ok, but this doesn't support yet the fragmentainer fragmenting yet? The
NGBreakToken will need a list of child NGBreakTokens to support this?

https://codereview.chromium.org/2632523002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_layout_input_node.cc (right):

https://codereview.chromium.org/2632523002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_layout_input_node.cc:20:
NGConstraintSpace* constraint_space) {
This should be passed the break_token as an argument instead of getting it from
the NGBlockNode (similarly up the call chain). I'm fine with adding this in a
followup patch.

[mstensho (USE GERRIT), 2017-01-18 20:21:53]

Landing this now. Please press the big red button if you have any further
concerns. :)

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:443: while
(current_child_ && current_child_->IsLayoutFinished())
On 2017/01/18 18:46:47, ikilpatrick wrote:
> On 2017/01/18 11:52:09, mstensho wrote:
> > On 2017/01/18 02:12:21, ikilpatrick wrote:
> > > hmmm..., is there any way to encode the "IsLayoutFinished" information
> inside
> > > the break token? I think this leaks a side-effect (we want to keep
> LayoutInput
> > > (ConstraintSpace, BreakToken, etc) immutable, and the output Immutable).
> > > 
> > > I'm fine with adding a TODO here to fix this.
> > 
> > I don't quite understand what you mean. If layout is finished, there'll be
no
> > break token on the last fragment. And that's what IsLayoutFinished() checks;
> > we're not finished if we have no fragment, or if the last fragment has a
break
> > token.
> > 
> > BlockNode (a LayoutInputNode) certainly isn't immutable today, since it has
a
> > fragment pointer, which is updated when a fragment is created. This wasn't
> > introduced by this CL, though.
> 
> So take the example where the caller of this function calls it twice with a
> different break token, e.g.
> 
> NGBreakToken* break_token = /* from a previous layout or something */;
> 
> NGAlgorithm algorithm(style, children, constraint_space, break_token);
> NGFragment* fragment = algorithm->Layout();
> 
> // Parent inspects the fragment and decides that it doesn't like the result.
> if (fragment->BlockSize() > kConstant) {
>   NGAlgorithm algorithm2(style, children, constraint_space, break_token);
>   fragment = algorithm2->Layout(); // This may produce a bad result because
> IsLayoutFinished() returns true.
> }
> 
> Does that make sense?

So in this example we want to throw away |fragment| and create a new one with a
different algorithm type (or with the same algorithm, only with different
parameters, such as constraint space)?

If that's the case, I still don't understand the problem. Then we just discard
the fragment tree that we got from the first algorithm instance, and call
Layout() on the second algorithm instance, with the exact same break token (if
we have one at all). I was kind of imagining that node could hold a list of weak
pointers to all the fragments that have been created for it.

> Basically we need to encode that the a child is "done" inside the break token
> for the above to work.

Good thing it's BlinkOn soon. I think some F2F would be useful here. :) I think
I'm missing some essential bits about the NG philosophy.

Anyway: Added a TODO.

https://codereview.chromium.org/2632523002/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:457: //
block right away, due to the posibility of parallel flows. We can only
On 2017/01/18 18:46:47, ikilpatrick wrote:
> On 2017/01/18 11:52:09, mstensho wrote:
> > On 2017/01/18 02:12:21, ikilpatrick wrote:
> > > this doesn't support parallel flows yet right?
> > 
> > Yes, it does. :) We both support content beside floats and also parallel
flow
> > situations that arise when overflowing the bottom of a block.
> > 
> > See the new unit tests that have "Float" in their name, and also
> > OverflowedBlock.
> 
> Sg. Ok, but this doesn't support yet the fragmentainer fragmenting yet?

Yes, we do! :) But it's kind of broken when it comes to painting, hit testing
and so on, since we still rely on being painted via the LayoutObject tree, and
there's no way to split a LayoutObject into fragments. There are several unit
tests in this CL that prove that fragmentation works.

> The NGBreakToken will need a list of child NGBreakTokens to support this?

That's indeed how you suggested to do it some time ago, but I ended up with
something simpler (but I may be doing something I'm not supposed to). As I think
I mentioned elsewhere, BlockNode has a pointer to a fragment. With this CL, a
node may create multiple fragments, so then the fragment will be the last
fragment created. When resuming layout for a node (i.e. when creating a layout
algorithm), we just read out the break token from the last fragment created for
a node and pass it to the algorithm. The break token will tell us the block
offset and (optionally) the child node to resume at. If there's no child node,
it just means that we had to break inside a "content-less" part of some block,
e.g.:

<div style="columns:2; column-fill:auto; height:100px;">
    <div id="child" style="height:150px;">
        <div id="grandchild" style="height:20px;"></div>
    </div>
</div>

#child needs to break at offset 100px, but #child doesn't have any children at
that location.

Maybe the fragment pointer in BlockNode was added by accident, and that I'm just
abusing it. I don't know. I was thinking that the way forward would be to extend
this from one fragment pointer to a list of weak pointers to all the fragments
created for the node.

https://codereview.chromium.org/2632523002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_layout_input_node.cc (right):

https://codereview.chromium.org/2632523002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_layout_input_node.cc:20:
NGConstraintSpace* constraint_space) {
On 2017/01/18 18:46:47, ikilpatrick wrote:
> This should be passed the break_token as an argument instead of getting it
from
> the NGBlockNode (similarly up the call chain). I'm fine with adding this in a
> followup patch.

Adding a TODO for this.

[mstensho (USE GERRIT), 2017-01-18 20:22:06]

The CQ bit was checked by mstensho@opera.com

[mstensho (USE GERRIT), 2017-01-18 20:22:06]

The patchset sent to the CQ was uploaded after l-g-t-m from eae@chromium.org,
ikilpatrick@chromium.org
Link to the patchset: https://codereview.chromium.org/2632523002/#ps100001
(title: "Add TODO.")

[commit-bot: I haz the power, 2017-01-18 20:22:56]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[ikilpatrick, 2017-01-18 21:56:02]

Sounds good, yeah fine to land.

The fragment pointer inside the NGBlockNode shouldn't really be used, but this
is probably easier F2F.

Are you around any of the weeks surrounding blinkon? I'm actually can't attend,
but perhaps we should VC instead.

(still lgtm obviously).

[commit-bot: I haz the power, 2017-01-18 22:24:34]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1484770926023610,
"parent_rev": "13b9222716acd3be1ff8fe6ec66ab4e63fd1abe6", "commit_rev":
"24bfa2fe65cc6bb73338d9d7a2f2175efee45c83"}

[commit-bot: I haz the power, 2017-01-18 22:25:02]

Description was changed from

==========
[LayoutNG] Initial support for multicol, introducing NGBlockBreakToken.

We can now lay out block-level floats and in-flow blocks inside a multicol
container. Note that painting and hit testing doesn't work too well, since
those operations are still performed on the legacy LayoutObject tree, and
there's no way to fragment a LayoutObject.

No attempt has been made at integrating this with out-of-flow positioning or
inline-level layout.
==========

to

==========
[LayoutNG] Initial support for multicol, introducing NGBlockBreakToken.

We can now lay out block-level floats and in-flow blocks inside a multicol
container. Note that painting and hit testing doesn't work too well, since
those operations are still performed on the legacy LayoutObject tree, and
there's no way to fragment a LayoutObject.

No attempt has been made at integrating this with out-of-flow positioning or
inline-level layout.

Review-Url: https://codereview.chromium.org/2632523002
Cr-Commit-Position: refs/heads/master@{#444512}
Committed:
https://chromium.googlesource.com/chromium/src/+/24bfa2fe65cc6bb73338d9d7a2f2...
==========

[commit-bot: I haz the power, 2017-01-18 22:25:05]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/chromium/src/+/24bfa2fe65cc6bb73338d9d7a2f2...