[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

The CreateLine() function produces NGTextFragment in the visual order.

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

BUG=636993
Committed: https://crrev.com/f77b0d3954eefc100b4236fb3d8776599071fd29
Cr-Commit-Position: refs/heads/master@{#439427}

[kojii, 2016-12-12 08:00:33]

Description was changed from

==========
WIP: [LayoutNG] Fill in NGTextFragment and NGPhysicalTextFragment

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

to

==========
WIP: [LayoutNG] Fill in NGTextFragment and NGPhysicalTextFragment

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

[kojii, 2016-12-12 08:01:29]

Description was changed from

==========
WIP: [LayoutNG] Fill in NGTextFragment and NGPhysicalTextFragment

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

to

==========
WIP: [LayoutNG] Fill in NGPhysicalTextFragment

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

[kojii, 2016-12-12 08:01:46]

Description was changed from

==========
WIP: [LayoutNG] Fill in NGPhysicalTextFragment

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

to

==========
WIP: [LayoutNG] Fill in text and items to NGPhysicalTextFragment

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

[kojii, 2016-12-12 08:06:16]

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

[kojii, 2016-12-12 08:06:16]

Can I ask yet another early thoughts?

What should NGPhysicalTextFragment have? I put String and
Vector<NGLayoutInlineItem> in PS1, but can think of other options such as:
a. A pointer to NGInlineNode and a list of indexes. We probably don't want this?
b. Instead of NGLayoutInlineItem, create its counterpart for fragment. It may be
the same at this point but may differ in future.

In my understanding, we'd like fragments to have the least dependencies to
InputNode, but NGLayoutInlineItem looks mostly common in InputNode and Fragment
to me. Thoughts appreciated.

[eae, 2016-12-12 17:48:18]

Originally I had envisioned it having a pointer to the NGInlineNode and a start
and end offset.

const NGInlineNode* source_node_;
unsigned start_offset_;	
unsigned end_offset_;

That way we wouldn't have to store a copy of the text and can instead get it by
calling:

source_node_->Text(start_offset_, end_offset_)

[kojii, 2016-12-13 03:20:59]

On 2016/12/12 at 17:48:18, eae wrote:
> Originally I had envisioned it having a pointer to the NGInlineNode and a
start and end offset.

Oh great, I wasn't sure it's ok to have the pointer. Thank you for your prompt
response as always.

[kojii, 2016-12-13 19:53:14]

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

[commit-bot: I haz the power, 2016-12-13 19:53:45]

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, 2016-12-13 20:10:43]

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

[commit-bot: I haz the power, 2016-12-13 20:10:46]

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

[kojii, 2016-12-14 07:09:54]

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

[commit-bot: I haz the power, 2016-12-14 07:10:15]

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, 2016-12-14 08:42:47]

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

[commit-bot: I haz the power, 2016-12-14 08:42:47]

Dry run: This issue passed the CQ dry run.

[kojii, 2016-12-14 13:52:17]

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

[commit-bot: I haz the power, 2016-12-14 13:52:24]

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

[kojii, 2016-12-14 14:14:12]

Description was changed from

==========
WIP: [LayoutNG] Fill in text and items to NGPhysicalTextFragment

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

to

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

The CreateLine() function produces NGTextFragment in the visual order.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

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

[kojii, 2016-12-14 14:19:18]

PTAL, the other CL was merged into this.

[commit-bot: I haz the power, 2016-12-14 15:32:03]

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

[commit-bot: I haz the power, 2016-12-14 15:32:04]

Dry run: This issue passed the CQ dry run.

[eae, 2016-12-14 18:43:43]

This is great and so much easier to read and reason about than the old
implementation! Thank you for working on this.

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_bidi_paragraph.cc (right):

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_bidi_paragraph.cc:45: unsigned
start,
item_offset or start_item might be a better name, I originally thought this was
a character index.

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_bidi_paragraph.h (right):

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_bidi_paragraph.h:48:
Vector<NGLayoutInlineItem>& items,
const

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_bidi_paragraph.h:51: Vector<int32_t,
32>& item_indicies_in_visual_order);
Presumably this is the out param? If so please make it a pointer.

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc (right):

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc:218: void
NGInlineNode::CreateLine(unsigned start,
This method probably makes more sense in ng_text_layout_algorithm.

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc:220:
NGFragmentBuilder* builder) {
const

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc:250: unsigned size =
end - start;
DCHECK(end >= start);

[ikilpatrick, 2016-12-14 18:49:34]

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc (right):

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc:220:
NGFragmentBuilder* builder) {
So we probably want most of this logic on NGTextLayoutAlgorithm.

Basically what I was imagining is that:

NGTextLayoutAlgorithm->Layout() => produces a single NGTextFragment

NGInlineLayoutAlgorithm calls NGTextLayoutAlgorithm for each of these
NGTextFragments and positions them on lines, etc.

Does that make sense?

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_physical_text_fragment.h
(right):

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_physical_text_fragment.h:49:
Member<const NGInlineNode> node_;
comment why we have a ptr back to the NGInlineNode, maybe also a NOTE/TODO that
this would be better pointing to a text thing.

[kojii, 2016-12-14 21:36:37]

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc (right):

https://codereview.chromium.org/2563403002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc:220:
NGFragmentBuilder* builder) {
On 2016/12/14 at 18:49:34, ikilpatrick wrote:
> So we probably want most of this logic on NGTextLayoutAlgorithm.
> 
> Basically what I was imagining is that:
> 
> NGTextLayoutAlgorithm->Layout() => produces a single NGTextFragment
> 
> NGInlineLayoutAlgorithm calls NGTextLayoutAlgorithm for each of these
NGTextFragments and positions them on lines, etc.
> 
> Does that make sense?

Can you explain a bit more? If NGTextLayoutAlgorithm->Layout() can produce only
one NGTextFragment, since one line can contain multiple NGTextFragment, the line
breaker and bidi reorder should happen in NGInlineLayoutAlgorithm.

But you also said "most of this logic on NGTextLayoutAlgorithm". If
NGTextLayoutAlgorithm does line breaker and bidi reorder, it will produce
multiple NGTextFragment.

What did I miss?

[kojii, 2016-12-15 07:55:24]

I think I understand what you said better, after my head refreshed.

IIUC I should separate line breaking and Bidi reordering; was thinking these two
too much together.

1. Consume chunk that can fill up the current line.
  - NGTextLayoutAlgorithm consumes if text.
  - Do something different for inline blocks.
  - At this point, we know width, but position is not final.
2. When line break point was determined, bidi reorder.
  - So bidi reorder probably belongs to NGInlineLayoutAlgorithm.
3. Accumulate widths to determine position of each fragment.

I was thinking (and this CL) to create fragments in step 3. But for non-bidi, we
know the position is final in step 1, and step 3 is not necessary. So for
non-RTL to perform good, we should build fragments in step 1, then bidi reorders
the fragment tree, not NGLayoutInlineItem. This needs a little more thoughts,
probably in following CLs.

[kojii, 2016-12-15 08:30:25]

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

[commit-bot: I haz the power, 2016-12-15 08:30:39]

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

[kojii, 2016-12-15 08:31:27]

Description was changed from

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

The CreateLine() function produces NGTextFragment in the visual order.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

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

to

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

The CreateLine() function produces NGTextFragment in the visual order.

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

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

[kojii, 2016-12-15 08:36:40]

PTAL. Moved the logic to NGTextLayoutAlgorithm, added a helper class
NGLayoutInlineItemRange, a class like StringView is for String.

> then Bidi reorders the fragment tree, not NGLayoutInlineItem

It not only reorders but also splits NGTextFragment. I'll see if it's feasible.

[commit-bot: I haz the power, 2016-12-15 10:15:47]

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

[commit-bot: I haz the power, 2016-12-15 10:15:48]

Dry run: This issue passed the CQ dry run.

[ikilpatrick, 2016-12-18 22:54:06]

lgtm, sorry for the slow review.

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc (right):

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.cc:46:
NGLayoutInlineItemRange::NGLayoutInlineItemRange(
move to end of file?

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_inline_node.h (right):

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_inline_node.h:131: class
NGLayoutInlineItemRange {
move below type cast?

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc
(right):

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:60:
NGConstraintSpace* constraint_space,
i'd make this const NGConstraintSpace& and deref above.

https://codereview.chromium.org/2563403002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/ng_text_layout_algorithm.cc:149: }
newline.

[kojii, 2016-12-19 05:09:17]

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

[commit-bot: I haz the power, 2016-12-19 05:09:27]

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, 2016-12-19 06:55:43]

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

[commit-bot: I haz the power, 2016-12-19 06:55:45]

Dry run: This issue passed the CQ dry run.

[kojii, 2016-12-19 07:45:23]

Thank you, all done! Not slow at all!

[kojii, 2016-12-19 07:45:25]

The CQ bit was checked by kojii@chromium.org

[kojii, 2016-12-19 07:45:26]

The patchset sent to the CQ was uploaded after l-g-t-m from
ikilpatrick@chromium.org
Link to the patchset: https://codereview.chromium.org/2563403002/#ps180001
(title: "ikilpatrick review")

[commit-bot: I haz the power, 2016-12-19 07:45:39]

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, 2016-12-19 07:49:38]

CQ is committing da patch.

Bot data: {"patchset_id": 180001, "attempt_start_ts": 1482133525697730,
"parent_rev": "75b3613123801182acce727e53e53eb27ee17c2f", "commit_rev":
"f5dffe458c9f87318d215d68e1a2b3701088871a"}

[commit-bot: I haz the power, 2016-12-19 07:50:04]

Description was changed from

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

The CreateLine() function produces NGTextFragment in the visual order.

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

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

to

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

The CreateLine() function produces NGTextFragment in the visual order.

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

BUG=636993

Review-Url: https://codereview.chromium.org/2563403002
==========

[commit-bot: I haz the power, 2016-12-19 07:50:05]

Committed patchset #10 (id:180001)

[commit-bot: I haz the power, 2016-12-19 07:53:03]

Description was changed from

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

The CreateLine() function produces NGTextFragment in the visual order.

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

BUG=636993

Review-Url: https://codereview.chromium.org/2563403002
==========

to

==========
[LayoutNG] Add Bidi reordering and fill in NGPhysicalTextFragment

This patch adds Bidi reordering to NGInlineNode, using ICU BiDi[1] to
implement rules defined in UAX#9 3.4 Reordering Resolved Levels[2].

The CreateLine() function produces NGTextFragment in the visual order.

This patch also adds a pointer to NGInlineNode and item index range to
NGPhysicalTextFragment.

UAX#9 L1[3] is not supported in this patch. ICU BiDi has a function for
L1, but efficient implementation needs more considerations. This will be
revisited after the line breaker. Note, L1 is not fully supported in
BidiResolver <crbug.com/316409>.

There is only one test case for the Bidi reordering in this patch. We
may run test cases from Unicode[4], or maybe it's overkill. More test
coverage is to be worked out.

[1] http://userguide.icu-project.org/transforms/bidi
[2] http://unicode.org/reports/tr9/#Reordering_Resolved_Levels
[3] http://unicode.org/reports/tr9/#L1
[4] http://www.unicode.org/Public/UNIDATA/

BUG=636993

Committed: https://crrev.com/f77b0d3954eefc100b4236fb3d8776599071fd29
Cr-Commit-Position: refs/heads/master@{#439427}
==========

[commit-bot: I haz the power, 2016-12-19 07:53:04]

Patchset 10 (id:??) landed as
https://crrev.com/f77b0d3954eefc100b4236fb3d8776599071fd29
Cr-Commit-Position: refs/heads/master@{#439427}