[LayoutNG] Compute baseline from fragment tree

[LayoutNG] Compute baseline from fragment tree

This patch computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsurBjkxZxAq028EbhFjo/edit?usp=sharing

BUG=636993
Review-Url: https://codereview.chromium.org/2867293002
Cr-Commit-Position: refs/heads/master@{#485889}
Committed: https://chromium.googlesource.com/chromium/src/+/f66aae2d690ff7d3d22bfd086a203bb5e9ce80a4

[kojii, 2017-05-09 03:07:22]

Description was changed from

==========
ngbaseline

BUG=
==========

to

==========
3. Moves BaselinePosition() to NGBoxFragment, in preparation of not
   building RootInlineBox when NG has its own paint.

https://codereview.chromium.org/2845913002#msg45
==========

[kojii, 2017-05-09 04:39:46]

Description was changed from

==========
3. Moves BaselinePosition() to NGBoxFragment, in preparation of not
   building RootInlineBox when NG has its own paint.

https://codereview.chromium.org/2845913002#msg45
==========

to

==========
3. Moves BaselinePosition() to NGBoxFragment, in preparation of not
   building RootInlineBox when NG has its own paint.

https://codereview.chromium.org/2845913002#msg45

CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_layout_ng
==========

[cbiesinger, 2017-05-11 19:57:11]

cbiesinger@chromium.org changed reviewers:
+ cbiesinger@chromium.org

[cbiesinger, 2017-05-11 19:57:12]

I know you haven't sent this for review yet but I really think this has to be
calculated by the algorithm and just stored on the fragment. A number of cases
need special handling and can't just be handled by looking in the line boxes --
inline-block, tables, form controls, etc.

[kojii, 2017-05-11 22:25:17]

On 2017/05/11 at 19:57:12, cbiesinger wrote:
> I know you haven't sent this for review yet but I really think this has to be
calculated by the algorithm and just stored on the fragment. A number of cases
need special handling and can't just be handled by looking in the line boxes --
inline-block, tables, form controls, etc.

Agreed, I think I need a design doc and discuss there, since it's not that
simple to calculate and store in fragments as I commented in the other CL.

There are too many types of baselines to store all of them in fragments. I'll
try to list up possible options and ask wide reviews.

[kojii, 2017-07-05 19:46:52]

Description was changed from

==========
3. Moves BaselinePosition() to NGBoxFragment, in preparation of not
   building RootInlineBox when NG has its own paint.

https://codereview.chromium.org/2845913002#msg45

CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_layout_ng
==========

to

==========
[LayoutNG] Add NGBaselineSource

NGBaselineSource computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_layout_ng
==========

[kojii, 2017-07-05 19:55:27]

kojii@chromium.org changed reviewers:
+ eae@chromium.org, ikilpatrick@chromium.org

[kojii, 2017-07-05 19:55:28]

The primary purpose of this CL is to complement the doc and to discuss how to
implement baseline, but if we can agree this approach looks good to go, I hope
this isn't too far to land.

The current code calls LayoutBox::BaselinePosition(), which will stop working
once we stop creating RootInlineBox by enabling NG paint.

I remember Ian and Christian were concerned about tree walking before, but
computing and storing all information doesn't look cheap, and I suppose
baselines are not needed so often (inline block, table, flex, grid?) that
walking looks more reasonable than always computing.

We can cache this as a mutable member of fragments if we need to compute this
repeatedly, but given old layout still walk the tree, I hope it's not that much
needed, and we can add cache anytime.

Thoughts appreciated.

[kojii, 2017-07-10 16:15:00]

Patchset #15 (id:280001) has been deleted

[kojii, 2017-07-10 19:25:43]

Some tests still failing but feedback appreciated.

This approach turned out to have a few inefficiencies. AFAIU, we prefer not to
traverse knowing some inefficiencies, but a couple of them observed so far FYI:
1. Previous approach was all on stack, but we have 24 bytes on every box
fragment. I'm hoping to switch to unique_ptr to shrink it to 8 bytes, but it
comes with heap allocation cost.
2. Previous approach computed baselines of last or first block only. New
approach propagates from bottom-to-top, and we don't know if the current child
is last or not, so we compute all of them.

Are you still good to pursue this direction?

[kojii, 2017-07-11 04:53:54]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-07-11 04:54:13]

Dry run: CQ is trying da patch.

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

[commit-bot: I haz the power, 2017-07-11 06:04:11]

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

[commit-bot: I haz the power, 2017-07-11 06:04:12]

Dry run: Try jobs failed on following builders:
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)

[kojii, 2017-07-11 09:14:49]

PTAL. Regular tests pass, there maybe ngbot failures.

As noted above, there are some inefficiencies, some of them are probably
workable I think.

[kojii, 2017-07-11 09:15:46]

Description was changed from

==========
[LayoutNG] Add NGBaselineSource

NGBaselineSource computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_layout_ng
==========

to

==========
[LayoutNG] Compute baseline from fragment tree

This patch computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_layout_ng
==========

[eae, 2017-07-11 22:23:56]

Thank you for the very thorough design doc and the detailed comments. This looks
great and matches the design we've agreed upon.

LGTM!

[kojii, 2017-07-12 05:32:04]

Description was changed from

==========
[LayoutNG] Compute baseline from fragment tree

This patch computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_layout_ng
==========

to

==========
[LayoutNG] Compute baseline from fragment tree

This patch computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993
==========

[kojii, 2017-07-12 05:32:13]

The CQ bit was checked by kojii@chromium.org

[commit-bot: I haz the power, 2017-07-12 05:32:23]

CQ is trying da patch.

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

[commit-bot: I haz the power, 2017-07-12 07:27:58]

CQ is committing da patch.

Bot data: {"patchset_id": 360001, "attempt_start_ts": 1499837533539860,
"parent_rev": "4782b12a04373772f011a4fbaaf271e6512d0727", "commit_rev":
"f66aae2d690ff7d3d22bfd086a203bb5e9ce80a4"}

[commit-bot: I haz the power, 2017-07-12 07:28:16]

Description was changed from

==========
[LayoutNG] Compute baseline from fragment tree

This patch computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993
==========

to

==========
[LayoutNG] Compute baseline from fragment tree

This patch computes baseline from fragment tree.

Design doc:
https://docs.google.com/a/chromium.org/document/d/1ukrQxkSKMuU1lW2XaQMzgRlsur...

BUG=636993

Review-Url: https://codereview.chromium.org/2867293002
Cr-Commit-Position: refs/heads/master@{#485889}
Committed:
https://chromium.googlesource.com/chromium/src/+/f66aae2d690ff7d3d22bfd086a20...
==========

[commit-bot: I haz the power, 2017-07-12 07:28:18]

Committed patchset #18 (id:360001) as
https://chromium.googlesource.com/chromium/src/+/f66aae2d690ff7d3d22bfd086a20...

[cbiesinger, 2017-07-12 15:48:44]

Sorry for the delayed (kinda too late) review but I have some comments.
Generally though this looks good, I like it!

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:735:
LayoutObject* layout_object = child->GetLayoutObject();
It's pretty unfortunate that we have to rely on the layout object for this, do
we not have any NG functions for this check?

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:763: if
(AddBaseline(request, i))
Why not pass the child fragment directly instead of the index? I guess you need
the offset too but I think it would be more elegant to pass offset+fragment than
the index, what do you think?

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_builder.cc
(right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_constraint_space_builder.cc:161:
NGBaselineRequest{algorithm_type, baseline_type});
I wonder if we should make an effort to deduplicate requests for the same
algorithm/baseline type pair?

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h (right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h:133: const
Vector<NGLogicalOffset>& Offsets() const { return offsets_; }
Add a brief comment that this is each child's offset? Or maybe rename to
ChildOffsets?

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h:142: void
AddBaseline(NGBaselineAlgorithmType, FontBaseline, LayoutUnit);
Could you add some brief documentation for how this is expected to work? Just
mention that for each baseline request in the constraint space, this function
should be called to provide the corresponding baseline, and the results are
undefined if it is called more than once for a given type/FontBaseline pair.

[kojii, 2017-07-12 18:21:53]

> Sorry for the delayed (kinda too late) review but I have some comments.
Generally though this looks good, I like it!

Not delayed at all, maybe I went ahead too quick, but this is 1st patch and I'm
sure we need more tweaks here. Thanks for liking this, and feedback for
e-mail/doc, that really helped me so much.

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
(right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:735:
LayoutObject* layout_object = child->GetLayoutObject();
On 2017/07/12 at 15:48:44, cbiesinger wrote:
> It's pretty unfortunate that we have to rely on the layout object for this, do
we not have any NG functions for this check?

NGLayoutInputNode has one but not in fragment tree. Yeah, this needs cleanup
when LayoutObject tree is really gone, I look forward to working on it!

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc:763: if
(AddBaseline(request, i))
On 2017/07/12 at 15:48:44, cbiesinger wrote:
> Why not pass the child fragment directly instead of the index? I guess you
need the offset too but I think it would be more elegant to pass offset+fragment
than the index, what do you think?

Hm, thought this is easier to read, to clarify we do the same thing but just in
opposite order, but I'm good either way. I'll send following patch.

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_builder.cc
(right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_constraint_space_builder.cc:161:
NGBaselineRequest{algorithm_type, baseline_type});
On 2017/07/12 at 15:48:44, cbiesinger wrote:
> I wonder if we should make an effort to deduplicate requests for the same
algorithm/baseline type pair?

Good point.

The question is whether computing same pair multiple times is faster if that
occurs, or deduplicating everytime is faster. I was thinking of it a bit, then
forgot.

WDYT?

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h (right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h:133: const
Vector<NGLogicalOffset>& Offsets() const { return offsets_; }
On 2017/07/12 at 15:48:44, cbiesinger wrote:
> Add a brief comment that this is each child's offset? Or maybe rename to
ChildOffsets?

We have MutableOffsets() already and this is interface-compatible with
NGLineBoxFragmentBuilder. I'll add comment.

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h:142: void
AddBaseline(NGBaselineAlgorithmType, FontBaseline, LayoutUnit);
On 2017/07/12 at 15:48:44, cbiesinger wrote:
> Could you add some brief documentation for how this is expected to work? Just
mention that for each baseline request in the constraint space, this function
should be called to provide the corresponding baseline, and the results are
undefined if it is called more than once for a given type/FontBaseline pair.

Thank you for pointing this out. I was caring comments for users of baselines
but forgot to think about algorithms. In a following patch.

[cbiesinger, 2017-07-12 20:23:09]

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_constraint_space_builder.cc
(right):

https://codereview.chromium.org/2867293002/diff/360001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_constraint_space_builder.cc:161:
NGBaselineRequest{algorithm_type, baseline_type});
On 2017/07/12 18:21:52, kojii wrote:
> On 2017/07/12 at 15:48:44, cbiesinger wrote:
> > I wonder if we should make an effort to deduplicate requests for the same
> algorithm/baseline type pair?
> 
> Good point.
> 
> The question is whether computing same pair multiple times is faster if that
> occurs, or deduplicating everytime is faster. I was thinking of it a bit, then
> forgot.
> 
> WDYT?

Yeah, hm, it's a bit hard to tell. But I think it's probably better to
deduplicate because the cost of that is bounded.

[kojii, 2017-07-13 03:44:49]

On 2017/07/12 at 20:23:09, cbiesinger wrote:
> Yeah, hm, it's a bit hard to tell. But I think it's probably better to
deduplicate because the cost of that is bounded.

Ok, will do, thanks!