Use Opportunity Iterator to position text fragments in NGLineBuilder

Use Opportunity Iterator to position text fragments in NGLineBuilder

This patch introduces NGLayoutOpportunityIterator to NGLineBuilder so it
can use it to search the next available opportunity to position text
fragments.

With this patch NGLayout starts supporting a base text floating around
floats that are positioned before an inline fragment.
Example:
<div id="container">
  <div id="left-float1"></div>
  <div id="left-float2"></div>
  <div id="right-float"></div>
  The quick brown fox jumps over the lazy dog
</div>

BUG=635619
TEST=NGTextLayoutAlgorithmTest::TextFloatsAroundFloatsBefore

Review-Url: https://codereview.chromium.org/2739683006
Cr-Commit-Position: refs/heads/master@{#456278}
Committed: https://chromium.googlesource.com/chromium/src/+/207688fb45319568db61e59c4c8391517793bf47

[Gleb Lanbin, 2017-03-08 20:56:13]

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

[kojii, 2017-03-09 03:01:54]

This looks great, thank you so much for working on this. Only for NGLineBuilder
and NGTextLayoutAlgorithm:

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_line_builder.cc:245: top);
Don't we need to add |line_box_data.inline_size|, or is it included somewhere I
missed?

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:51:
line_builder->FindNextLayoutOpportunity();
It looks more natural to call this at the end of |SetStart|.

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:108:
line_builder->FindNextLayoutOpportunity();
and at the end of |CreateLineUpToLastBreakOpportunity|.

[ikilpatrick, 2017-03-09 22:00:51]

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/geometry/ng_logical_offset.cc:60:
return std::tie(other.inline_offset, other.block_offset) !=
just "return !operator==(other);" ?

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_base_layout_algorithm_test.h:14: //
Base class for all NG Layout Algorithms unit test classes.
s/NG Layout/LayoutNG

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:78: if
(line_builder->CanFitOnLine()) {
we also need logic to check if the height of the linebox can fit within the
current opportunity, where does that fit in? I worry that we'll need to do
line-by-line layout to have the right layering here?
@kojii thoughts?

[Gleb Lanbin, 2017-03-09 22:25:07]

Patchset #2 (id:20001) has been deleted

[Gleb Lanbin, 2017-03-09 22:26:45]

PTAL

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/geometry/ng_logical_offset.cc:60:
return std::tie(other.inline_offset, other.block_offset) !=
On 2017/03/09 22:00:51, ikilpatrick wrote:
> just "return !operator==(other);" ?

nice, thanks!

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_base_layout_algorithm_test.h:14: //
Base class for all NG Layout Algorithms unit test classes.
On 2017/03/09 22:00:51, ikilpatrick wrote:
> s/NG Layout/LayoutNG

Done.

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_line_builder.cc:245: top);
On 2017/03/09 03:01:54, kojii wrote:
> Don't we need to add |line_box_data.inline_size|, or is it included somewhere
I
> missed?

could you explain why you think we need to include it?
Here is how I understand it
1) LayoutOpportunityIterator returns a LayoutOpportunity(NGLogicalRect)
2) NGTextLayoutAlgorithm::LayoutInline tries to fit as much text as possible to
that opportunity and then calls
NGLineBuilder::CreateLineUpToLastBreakOpportunity which place line_item_chunks
that has inline_size. 
3) In order to calculate the logical offset for each line we need to subtract
the current layout opportunity's offset from ConstraintSpace().offset.

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:51:
line_builder->FindNextLayoutOpportunity();
On 2017/03/09 03:01:54, kojii wrote:
> It looks more natural to call this at the end of |SetStart|.

done. Although I think it adds an additional side effect to SetStart and
CreateLineUpToLastBreakOpportunity and violates the single responsibility
principle.

may be we can to change the line builder API a bit
1) rename SetStart -> Initialize
2) Move the logic starting from line 91-107 to line_builder->Finalize or
line_builder->CreateLine or line_builder->BuildLine
Feel free to ignore this if you already have a solution for this.

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:78: if
(line_builder->CanFitOnLine()) {
On 2017/03/09 22:00:51, ikilpatrick wrote:
> we also need logic to check if the height of the linebox can fit within the
> current opportunity, where does that fit in? I worry that we'll need to do
> line-by-line layout to have the right layering here?
> @kojii thoughts?

good point. added TODO for now

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:108:
line_builder->FindNextLayoutOpportunity();
On 2017/03/09 03:01:54, kojii wrote:
> and at the end of |CreateLineUpToLastBreakOpportunity|.

Done.

[kojii, 2017-03-10 03:12:43]

lgtm for my part, but please check Ian.

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_line_builder.cc:245: top);
On 2017/03/09 at 22:26:45, Gleb Lanbin wrote:
> On 2017/03/09 03:01:54, kojii wrote:
> > Don't we need to add |line_box_data.inline_size|, or is it included
somewhere I
> > missed?
> 
> could you explain why you think we need to include it?

Ok if tests pass, I'll need to debug to understand better, and we can fix
anytime later.

When you have multiple elements, or multiple bidi-items, this is where we flow
inline items horizontally, and |line_box_data.inline_size| is the offset from
the left edge. The original comment was that I was not sure either opportunity
or BfcOffset() incorporates it.

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

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:51:
line_builder->FindNextLayoutOpportunity();
On 2017/03/09 at 22:26:45, Gleb Lanbin wrote:
> may be we can to change the line builder API a bit
> 1) rename SetStart -> Initialize

Yeah, I was thinking of this, eae@ misunderstood this before, and I'm seeing a
need of "SetStart without initialize". But let's do this later, we'll probably
have large refactoring + renaming sometime soon, and currently eae@ has a WIP to
re-write this line breaker.

> 2) Move the logic starting from line 91-107 to line_builder->Finalize or
line_builder->CreateLine or line_builder->BuildLine
> Feel free to ignore this if you already have a solution for this.

Finalize isn't probably appropriate here though, since the call flow would be:
  SetStart w/Initialize
  CreateLine
  (may need to call SetStart without initialize)
  CreateLine
  CreateLine
  CreateFragments <= so maybe this is finalize
but this may change as we support BreakToken.

Thank you for the nice advice anyway.

https://codereview.chromium.org/2739683006/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:78: if
(line_builder->CanFitOnLine()) {
On 2017/03/09 at 22:26:45, Gleb Lanbin wrote:
> On 2017/03/09 22:00:51, ikilpatrick wrote:
> > we also need logic to check if the height of the linebox can fit within the
> > current opportunity, where does that fit in? I worry that we'll need to do
> > line-by-line layout to have the right layering here?
> > @kojii thoughts?
> 
> good point. added TODO for now

TODO sounds good for now. I think this will be a collaboration of NGLineBuilder
and line breaker.

There are a few other cases where we need to move a line down after it was
built:
https://cs.chromium.org/chromium/src/third_party/WebKit/LayoutTests/fast/css3...

In these cases, we build a line assuming it will fit, but find out it doesn't as
we build it or after we built it, and move it down. It may need to build the
line again using new logical top, because available width will change.

[ikilpatrick, 2017-03-10 17:20:17]

lgtm, thanks!

[Gleb Lanbin, 2017-03-10 17:49:09]

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

[commit-bot: I haz the power, 2017-03-10 17:49:43]

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-03-10 19:05:01]

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

[commit-bot: I haz the power, 2017-03-10 19:05:02]

Dry run: Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[Gleb Lanbin, 2017-03-10 21:06:14]

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

[commit-bot: I haz the power, 2017-03-10 21:06:43]

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-03-10 22:45:47]

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

[commit-bot: I haz the power, 2017-03-10 22:45:48]

Dry run: Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

[Gleb Lanbin, 2017-03-11 00:15:06]

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

[commit-bot: I haz the power, 2017-03-11 00:15:25]

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-03-11 02:03:10]

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

[commit-bot: I haz the power, 2017-03-11 02:03:14]

Dry run: Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

[Gleb Lanbin, 2017-03-11 02:41:38]

The CQ bit was checked by glebl@chromium.org

[Gleb Lanbin, 2017-03-11 02:41:38]

The patchset sent to the CQ was uploaded after l-g-t-m from
ikilpatrick@chromium.org, kojii@chromium.org
Link to the patchset: https://codereview.chromium.org/2739683006/#ps80001
(title: "add font-family")

[commit-bot: I haz the power, 2017-03-11 02:41:51]

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-03-11 04:14:39]

CQ is committing da patch.

Bot data: {"patchset_id": 80001, "attempt_start_ts": 1489200098213600,
"parent_rev": "0c449aad3898922b599d8a32c2380cc8c962040e", "commit_rev":
"207688fb45319568db61e59c4c8391517793bf47"}

[commit-bot: I haz the power, 2017-03-11 04:15:59]

Description was changed from

==========
Use Opportunity Iterator to position text fragments in NGLineBuilder

This patch introduces NGLayoutOpportunityIterator to NGLineBuilder so it
can use it to search the next available opportunity to position text
fragments.

With this patch NGLayout starts supporting a base text floating around
floats that are positioned before an inline fragment.
Example:
<div id="container">
  <div id="left-float1"></div>
  <div id="left-float2"></div>
  <div id="right-float"></div>
  The quick brown fox jumps over the lazy dog
</div>

BUG=635619
TEST=NGTextLayoutAlgorithmTest::TextFloatsAroundFloatsBefore
==========

to

==========
Use Opportunity Iterator to position text fragments in NGLineBuilder

This patch introduces NGLayoutOpportunityIterator to NGLineBuilder so it
can use it to search the next available opportunity to position text
fragments.

With this patch NGLayout starts supporting a base text floating around
floats that are positioned before an inline fragment.
Example:
<div id="container">
  <div id="left-float1"></div>
  <div id="left-float2"></div>
  <div id="right-float"></div>
  The quick brown fox jumps over the lazy dog
</div>

BUG=635619
TEST=NGTextLayoutAlgorithmTest::TextFloatsAroundFloatsBefore

Review-Url: https://codereview.chromium.org/2739683006
Cr-Commit-Position: refs/heads/master@{#456278}
Committed:
https://chromium.googlesource.com/chromium/src/+/207688fb45319568db61e59c4c83...
==========

[commit-bot: I haz the power, 2017-03-11 04:16:01]

Committed patchset #4 (id:80001) as
https://chromium.googlesource.com/chromium/src/+/207688fb45319568db61e59c4c83...

[yoichio, 2017-03-13 08:09:08]

A revert of this CL (patchset #4 id:80001) has been created in
https://codereview.chromium.org/2746823003/ by yoichio@chromium.org.

The reason for reverting is: Test failures on bot:
NGTextLayoutAlgorithmTest.TextFloatsAroundFloatsBefore

https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Andr....

[kimberly.james628, 2017-03-13 13:25:24]

On 2017/03/13 08:09:08, yoichio wrote:
> A revert of this CL (patchset #4 id:80001) has been created in
> https://codereview.chromium.org/2746823003/ by mailto:yoichio@chromium.org.
> 
> The reason for reverting is: Test failures on bot:
> NGTextLayoutAlgorithmTest.TextFloatsAroundFloatsBefore
> 
>
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Andr....

Stupid