Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

This patch:

1. Introduces the NGOffsetMappingBuilder class with a mock implementation;

2. Allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition NGOffsetMappingBuilder parameter, and use it to
construct the whitespace-collapsed offset mapping. The way how the
NGOffsetMappingBuilder is used is straightforward: whenever |text_| is
modified, NGOffsetMappingBuilder should be notified correspondingly.

This patch is the part of the project to support DOM/TextContent offset
mapping in LayoutNG. Design doc: https://goo.gl/CJbxky

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

Review-Url: https://codereview.chromium.org/2943573002
Cr-Commit-Position: refs/heads/master@{#483192}
Committed: https://chromium.googlesource.com/chromium/src/+/1f4be4da171cead27321f786d3b1306fd6bffeb3

[Xiaocheng, 2017-06-15 23:55:04]

Description was changed from

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

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

to

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

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

[Xiaocheng, 2017-06-15 23:55:12]

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

[commit-bot: I haz the power, 2017-06-15 23:55:32]

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-06-16 00:02:43]

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

[commit-bot: I haz the power, 2017-06-16 00:02:45]

Dry run: Try jobs failed on following builders:
  ios-simulator on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)

[Xiaocheng, 2017-06-16 00:06:27]

Description was changed from

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

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

to

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

THIS IS WORK IN PROGRESS. DO NOT COMMIT.

This patch makes NGInlineItemsBuilder::Append(String) return the information of
the collapsed white space characters, including:
- A boolean, indicating whether this Append() call removes a collapsible space
  that was previously added
- A vector of indexes of the removed white space characters in the appended
  string

Callers of Append() can collect the returned information to build offset mapping
between DOM data strings and the text content of NGInlineNode.

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

[Xiaocheng, 2017-06-16 00:08:13]

Description was changed from

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

THIS IS WORK IN PROGRESS. DO NOT COMMIT.

This patch makes NGInlineItemsBuilder::Append(String) return the information of
the collapsed white space characters, including:
- A boolean, indicating whether this Append() call removes a collapsible space
  that was previously added
- A vector of indexes of the removed white space characters in the appended
  string

Callers of Append() can collect the returned information to build offset mapping
between DOM data strings and the text content of NGInlineNode.

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

to

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

DO NOT COMMIT!

This WIP patch is for discussion about how white space collapsing information
should be returned by NGInlineItemsBuilder.

This patch makes NGInlineItemsBuilder::Append(String) return the information of
the collapsed white space characters, including:
- A boolean, indicating whether this Append() call removes a collapsible space
  that was previously added
- A vector of indexes of the removed white space characters in the appended
  string

Callers of Append() can collect the returned information to build offset mapping
between DOM data strings and the text content of NGInlineNode.

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

[Xiaocheng, 2017-06-16 00:09:43]

xiaochengh@chromium.org changed reviewers:
+ eae@chromium.org, kojii@chromium.org, yoichio@chromium.org, yosin@chromium.org

[Xiaocheng, 2017-06-16 00:09:44]

How do you like the idea of returning indexes of removed white spaces from
NGInlineItemsBuilder?

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

https://codereview.chromium.org/2943573002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:87:
bool Finalize();
This function is refactored out from ToString(), so that:
- ToString() no longer has side-effect
- Whether the finalization removes a trailing space is explicitly returned.

[yosin_UTC9, 2017-06-16 01:39:04]

For implementation wise, I guess final shape of NGInlineItemBuilder is

template <typename Purpose> NGInlineItemBuilder { ... }

Purpose is Layout or OffsetMapping.

Note: Using template is for execution speed of Layout.

So, it is easier to store result into sink in Purpose instead of return value.
In mean time, add member variable for OffsetMapping result in
NGInlineItemBuilder to
make patch smaller.

[yoichio, 2017-06-16 01:47:48]

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

https://codereview.chromium.org/2943573002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:57: //
of the collapsed spaces in the appended string.
Does this value have enough information to build offset mapping between
  "foo   bar  baz"
to"foo bar baz" and how do you manage it?

[Xiaocheng, 2017-06-16 01:59:14]

I'm not a fan of storing results in NGInlineItemsBuilder (which is in fact my
first prototype). This is because the builder doesn't have any knowledge about
the DOM tree. As a result, the caller has to perform a second pass to summarize
the results returned by the builder.

Using template seems interesting. Let me think about it.

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

https://codereview.chromium.org/2943573002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:57: //
of the collapsed spaces in the appended string.
On 2017/06/16 at 01:47:48, yoichio wrote:
> Does this value have enough information to build offset mapping between
>   "foo   bar  baz"
> to"foo bar baz" and how do you manage it?

Yes. The returned vector will contain the indexes of removed spaces: {4, 5, 10}.
See the unit tests for more examples.

The caller can use the return value to construct mapping function. I haven't
proceeded to that part, yet.

[yosin_UTC9, 2017-06-16 02:14:14]

On 2017/06/16 at 01:59:14, xiaochengh wrote:
> I'm not a fan of storing results in NGInlineItemsBuilder (which is in fact my
first prototype). This is because the builder doesn't have any knowledge about
the DOM tree. As a result, the caller has to perform a second pass to summarize
the results returned by the builder.
> 
> Using template seems interesting. Let me think about it.

The point is for Layout purpose of NGInlineItemBuilder should yield code without
returning value.
It is worth to think about passing DOM tree information somehow, and collect
info as side effect
rather than function return value.

[Xiaocheng, 2017-06-16 03:10:11]

On 2017/06/16 at 02:14:14, yosin wrote:
> On 2017/06/16 at 01:59:14, xiaochengh wrote:
> > I'm not a fan of storing results in NGInlineItemsBuilder (which is in fact
my first prototype). This is because the builder doesn't have any knowledge
about the DOM tree. As a result, the caller has to perform a second pass to
summarize the results returned by the builder.
> > 
> > Using template seems interesting. Let me think about it.
> 
> The point is for Layout purpose of NGInlineItemBuilder should yield code
without returning value.
> It is worth to think about passing DOM tree information somehow, and collect
info as side effect
> rather than function return value.

Currently, NGInlineItemBuilder::Append(String, ComputedStyle) API is very clean.
Passing in DOM nodes seem to make it not that clean...

I'll think about it.

[kojii, 2017-06-16 07:16:05]

Both points look reasonable to me. In most cases (other than editing or
selected) the data is not needed, and that we'd like to make the computation
optional. While, making it isolated from DOM sounds good too.

How about using the proposed structure, just indexes of collapsed characters,
but it is stored in NGInlineItemBuilder to retrieve instead of returning it?

[Xiaocheng, 2017-06-16 23:50:31]

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

[commit-bot: I haz the power, 2017-06-16 23:50:53]

Dry run: CQ is trying da patch.

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

[Xiaocheng, 2017-06-17 00:18:05]

Description was changed from

==========
WIP Make NGInlineItemsBuilder return info of collapsed white spaces

DO NOT COMMIT!

This WIP patch is for discussion about how white space collapsing information
should be returned by NGInlineItemsBuilder.

This patch makes NGInlineItemsBuilder::Append(String) return the information of
the collapsed white space characters, including:
- A boolean, indicating whether this Append() call removes a collapsible space
  that was previously added
- A vector of indexes of the removed white space characters in the appended
  string

Callers of Append() can collect the returned information to build offset mapping
between DOM data strings and the text content of NGInlineNode.

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

to

==========
Make NGInlineItemsBuilder return info of collapsed white spaces

This patch allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition 2-d vector parameter |removed_indexes| , so that when the
builder finishes:
- For each appended string, a vector is added to |removed_indexes|
- The vector stores the indexes of all removed spaces in the string in sorted
  order

Clients of NGInlineItemsBuilder can hence collect the reported indexes to build
offset mapping between DOM data strings and the text content of NGInlineNode.

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

[Xiaocheng, 2017-06-17 00:28:00]

Description was changed from

==========
Make NGInlineItemsBuilder return info of collapsed white spaces

This patch allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition 2-d vector parameter |removed_indexes| , so that when the
builder finishes:
- For each appended string, a vector is added to |removed_indexes|
- The vector stores the indexes of all removed spaces in the string in sorted
  order

Clients of NGInlineItemsBuilder can hence collect the reported indexes to build
offset mapping between DOM data strings and the text content of NGInlineNode.

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

to

==========
Make NGInlineItemsBuilder return info of collapsed white spaces

This patch allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition 2-d vector parameter |removed_indexes| , so that when the
builder finishes:
- For each appended string, a vector is added to |removed_indexes|
- The vector stores the indexes of all removed spaces in the string in sorted
  order

Clients of NGInlineItemsBuilder can hence collect the reported indexes to build
offset mapping between DOM data strings and the text content of NGInlineNode.

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

[Xiaocheng, 2017-06-17 00:35:07]

Updated. PTAL.

Thanks to all the comments. The current version has been improved by a lot with
a very clean API. Hope you like it!

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:91:
Optional<Vector<unsigned>> input_strings_lengths_;
Appending a string may result in the removal of a trailing space in a previous
string, so we need to remember lengths of previous strings to find out the index
of the removed trailing space.

[Xiaocheng, 2017-06-17 00:35:10]

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

[commit-bot: I haz the power, 2017-06-17 00:35:30]

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-06-17 02:15:11]

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

[commit-bot: I haz the power, 2017-06-17 02:15:12]

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

[yosin_UTC9, 2017-06-19 03:23:11]

Better than before.
I would like to avoid patterns, 
  training_new_line = AppendForceBrake()
  if (trailing_new_line && removed_index_),
by introducing high-level function, e.g. AppendBR()

Layout: AppendBR() == AppendForceBreak()
Offset Mapping builder: AppendBR() = AppendForceBR() + ...

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:91:
Optional<Vector<unsigned>> input_strings_lengths_;
On 2017/06/17 at 00:35:06, Xiaocheng wrote:
> Appending a string may result in the removal of a trailing space in a previous
string, so we need to remember lengths of previous strings to find out the index
of the removed trailing space.

Since NGInlineItemsBuild allocated on stack, == only one instance, we don't need
to use Optional<T>.
sizeof(std::vector<T>) is 24 byte (3 pointers in 64-bit), a comment can explain
this is used only for offset mapping calculation.

It is better to introduce new class for collecting offset mapping, e.g.
OffsetCollector, to abstract collecting operations and templatization.

BTW, for me, it is hard to guess what |removed_indexes_| is.

[Xiaocheng, 2017-06-19 05:15:51]

Thanks for the review!

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:91:
Optional<Vector<unsigned>> input_strings_lengths_;
On 2017/06/19 at 03:23:11, yosin_UTC9 wrote:
> On 2017/06/17 at 00:35:06, Xiaocheng wrote:
> > Appending a string may result in the removal of a trailing space in a
previous string, so we need to remember lengths of previous strings to find out
the index of the removed trailing space.
> 
> Since NGInlineItemsBuild allocated on stack, == only one instance, we don't
need to use Optional<T>.
> sizeof(std::vector<T>) is 24 byte (3 pointers in 64-bit), a comment can
explain this is used only for offset mapping calculation.

Will do.

> 
> It is better to introduce new class for collecting offset mapping, e.g.
OffsetCollector, to abstract collecting operations and templatization.

Could you explain more about this?

This patch doesn't introduce class for collecting the offset mapping. It only
makes the builder return how spaces are collapsed. A follow-up patch will
introduce the collector.

So I don't think templatization fits here.

> 
> BTW, for me, it is hard to guess what |removed_indexes_| is.

Will add comments.

[Xiaocheng, 2017-06-19 05:18:55]

On 2017/06/19 at 03:23:11, yosin wrote:
> Better than before.
> I would like to avoid patterns, 
>   training_new_line = AppendForceBrake()
>   if (trailing_new_line && removed_index_),
> by introducing high-level function, e.g. AppendBR()
> 
> Layout: AppendBR() == AppendForceBreak()
> Offset Mapping builder: AppendBR() = AppendForceBR() + ...

Could you also explain more about this idea? Do you want to templatize
NGInlineItemBuilder?

To me, this patch doesn't introduce an alternative version of
NGInlineItemBuilder, but rather, augments it to optionally return some more
information. So an optional parameter seems better than templatization here.

> 
>
https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
> File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):
> 
>
https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
> third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:91:
Optional<Vector<unsigned>> input_strings_lengths_;
> On 2017/06/17 at 00:35:06, Xiaocheng wrote:
> > Appending a string may result in the removal of a trailing space in a
previous string, so we need to remember lengths of previous strings to find out
the index of the removed trailing space.
> 
> Since NGInlineItemsBuild allocated on stack, == only one instance, we don't
need to use Optional<T>.
> sizeof(std::vector<T>) is 24 byte (3 pointers in 64-bit), a comment can
explain this is used only for offset mapping calculation.
> 
> It is better to introduce new class for collecting offset mapping, e.g.
OffsetCollector, to abstract collecting operations and templatization.
> 
> BTW, for me, it is hard to guess what |removed_indexes_| is.

[yosin_UTC9, 2017-06-19 05:55:13]

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:91:
Optional<Vector<unsigned>> input_strings_lengths_;
On 2017/06/19 at 05:15:51, Xiaocheng wrote:
> On 2017/06/19 at 03:23:11, yosin_UTC9 wrote:
> > On 2017/06/17 at 00:35:06, Xiaocheng wrote:
> > > Appending a string may result in the removal of a trailing space in a
previous string, so we need to remember lengths of previous strings to find out
the index of the removed trailing space.
> > 
> > Since NGInlineItemsBuild allocated on stack, == only one instance, we don't
need to use Optional<T>.
> > sizeof(std::vector<T>) is 24 byte (3 pointers in 64-bit), a comment can
explain this is used only for offset mapping calculation.
> 
> Will do.
> 
> > 
> > It is better to introduce new class for collecting offset mapping, e.g.
OffsetCollector, to abstract collecting operations and templatization.
> 
> Could you explain more about this?
It is functional abstraction of each then-clause and else-clause.
I imagine SAX API for XML parsing.
However, I'm not sure we can do so.

This comes from:

      // LayoutBR does not set preserve_newline, but should be preserved.
      if (!i && end == 1 && layout_object && layout_object->IsBR()) {
        bool trailing_space_removed = AppendForcedBreak(style, layout_object);
        if (trailing_space_removed && removed_indexes_)
          AddLastTrailingSpaceToRemovedIndexes(i);
        return;
      }

> This patch doesn't introduce class for collecting the offset mapping. It only
makes the builder return how spaces are collapsed. A follow-up patch will
introduce the collector.
> 
> So I don't think templatization fits here.

Templatization is the requirement. We should not make NGInlineItemBuilder slow
for layout.
It is OK to checking mode, e.g. Layout or Offset, for prototyping, but final
code should not.

Returning |bool| may be OK, I assume compiler will remove |return| statement for
unused returning value.

In another look, it seems we don't need to return |bool| for
|AppendForcedBreak()|.
We can do it in |AppendForceBreak()|, not sure we have call sites of
|AppendForceBreak()| don't need to
update |removed_indexe_|.

It seems |RemoveTrailingCollapsibleNewlineIfNeeded()| too.
In other words, move map construction into them.

[kojii, 2017-06-19 05:56:34]

> Do you want to templatize NGInlineItemBuilder?

We may want to templatize if the perf hits due to this change, but not now. In
other words, if the overall API allows us to templateize in future without large
overhaul, that's fine.

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

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:197:
AddLastTrailingSpaceToRemovedIndexes(i);
Why don't we add to removed_indexes in RemoveTrailingCollapsibleSpaceIfExists()
but let it return the result and do here?

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:32: //
Optionally, NGInlineItemsBuilder takes parameter |removed_indexes| to return
How about naming |removed_indexes| as |collapsed_indexes|? "Removed" sounds like
different from "collapsed".

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:90:
Vector<Vector<unsigned>>* removed_indexes_;
ditto.

[Xiaocheng, 2017-06-19 17:53:01]

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

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:197:
AddLastTrailingSpaceToRemovedIndexes(i);
On 2017/06/19 at 05:56:33, kojii wrote:
> Why don't we add to removed_indexes in
RemoveTrailingCollapsibleSpaceIfExists() but let it return the result and do
here?

Updating |removed_indexes_| needs the number of characters in the current string
that have been processed (i.e., |i|).

Let me try passing in this parameter instead, and hope that the performance
impact is negligible.

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:32: //
Optionally, NGInlineItemsBuilder takes parameter |removed_indexes| to return
On 2017/06/19 at 05:56:33, kojii wrote:
> How about naming |removed_indexes| as |collapsed_indexes|? "Removed" sounds
like different from "collapsed".

Sound good. Done.

https://codereview.chromium.org/2943573002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:90:
Vector<Vector<unsigned>>* removed_indexes_;
On 2017/06/19 at 05:56:33, kojii wrote:
> ditto.

Done.

[Xiaocheng, 2017-06-19 22:03:27]

Patch updated.

Regarding the performance impact, I did some experiments with the following
benchmark:

TEST_F(NGInlineItemsBuilderTest, LoremIpsumBenchmark) {
  Vector<String> lorem_ipsum_paragraph = {
    "\nLorem ipsum  dolor sit amet, consectetur  adipiscing  elit.\n",
    "\n",
    "Nam ornare enim eget elementum viverra.  ",
    "\nSed a porttitor ante. Pellentesque \taliquet iaculis dictum. \n",
    "Etiam id  molestie sapien,  nec malesuada enim. Quisque sem magna,\n",
    "\n pharetra vitae dolor at, ultricies   vulputate erat.",
    "  Morbi eu nibh a elit \n"
    "eleifend tincidunt. Aliquam turpis lacus,\n\n"
    "\ntincidunt eu  tincidunt eu, lobortis\tsit amet nulla.\n"
  };
  const unsigned repeat = 1000000;

  double start_time = MonotonicallyIncreasingTime();
  for (unsigned i = 0; i < repeat; ++i) {
    Vector<NGInlineItem> items;
    NGInlineItemsBuilder builder(&items);
    for (const String& string : lorem_ipsum_paragraph)
      builder.Append(string, style_.Get());
    builder.ToString();
  }
  double end_time = MonotonicallyIncreasingTime();

  LOG(ERROR) << (end_time - start_time) / repeat;
}

Results are here, where the second and the third columns are for running time
without/with this patch, respectively.

https://docs.google.com/a/chromium.org/spreadsheets/d/1gSonaK8lvPSUzLy6-TFDJk...

Conclusion: No measurable performance impact.

[Xiaocheng, 2017-06-19 22:03:40]

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

[commit-bot: I haz the power, 2017-06-19 22:04:14]

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-06-19 23:04:57]

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

[commit-bot: I haz the power, 2017-06-19 23:04:58]

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...)
  ios-device-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device-xcode-...)

[yosin_UTC9, 2017-06-20 05:38:59]

On 2017/06/19 at 22:03:27, xiaochengh wrote:
> Patch updated.
> 
> Regarding the performance impact, I did some experiments with the following
benchmark:
> 
> TEST_F(NGInlineItemsBuilderTest, LoremIpsumBenchmark) {
>   Vector<String> lorem_ipsum_paragraph = {
>     "\nLorem ipsum  dolor sit amet, consectetur  adipiscing  elit.\n",
>     "\n",
>     "Nam ornare enim eget elementum viverra.  ",
>     "\nSed a porttitor ante. Pellentesque \taliquet iaculis dictum. \n",
>     "Etiam id  molestie sapien,  nec malesuada enim. Quisque sem magna,\n",
>     "\n pharetra vitae dolor at, ultricies   vulputate erat.",
>     "  Morbi eu nibh a elit \n"
>     "eleifend tincidunt. Aliquam turpis lacus,\n\n"
>     "\ntincidunt eu  tincidunt eu, lobortis\tsit amet nulla.\n"
>   };
>   const unsigned repeat = 1000000;
> 
>   double start_time = MonotonicallyIncreasingTime();
>   for (unsigned i = 0; i < repeat; ++i) {
>     Vector<NGInlineItem> items;
>     NGInlineItemsBuilder builder(&items);
>     for (const String& string : lorem_ipsum_paragraph)
>       builder.Append(string, style_.Get());
>     builder.ToString();
>   }
>   double end_time = MonotonicallyIncreasingTime();
> 
>   LOG(ERROR) << (end_time - start_time) / repeat;
> }
> 
> Results are here, where the second and the third columns are for running time
without/with this patch, respectively.
> 
>
https://docs.google.com/a/chromium.org/spreadsheets/d/1gSonaK8lvPSUzLy6-TFDJk...
> 
> Conclusion: No measurable performance impact.

Thanks for collecting data.
Does number of overhead equal to number of whitespaces?

[yosin_UTC9, 2017-06-20 05:39:09]

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

https://codereview.chromium.org/2943573002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:372:
void NGInlineItemsBuilder::AddLastTrailingSpaceToRemovedIndexes(
nit: %s/RemovedIndexes/CollapsedIndexes/

[Xiaocheng, 2017-06-20 05:56:46]

On 2017/06/20 at 05:38:59, yosin wrote:
> On 2017/06/19 at 22:03:27, xiaochengh wrote:
> > Results are here, where the second and the third columns are for running
time without/with this patch, respectively.
> > 
> >
https://docs.google.com/a/chromium.org/spreadsheets/d/1gSonaK8lvPSUzLy6-TFDJk...
> > 
> > Conclusion: No measurable performance impact.
> 
> Thanks for collecting data.
> Does number of overhead equal to number of whitespaces?

It is linear to the number of removed whitespaces.

We perform the extra nullptr check and branching if and only if a space is
removed.

[yosin_UTC9, 2017-06-21 04:22:42]

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

https://codereview.chromium.org/2943573002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:107:
Vector<Vector<unsigned>>* collapsed_indexes_;
Could you introduce OffsetMappingBuilder class to hold |collapsed_indexes_| and
|input_strings_length_| and
member functions to update them in another file?
We would like to bold editing related part in core/layout for ease of
maintenance.

e.g.
  if (collapsed_indexes_) {
    input_strings_lengths_.push_back(string.length());
    collapsed_indexes_->emplace_back();
  }
=>
  if (offset_builder_)
    offset_builder_->Append(string);


  if (collapsed_indeexs_)
    collapsed_indexes_->back().push_back(i);
=>
   if (offset_builder_)
    offset_builder_->Append(i);

These names are just example. 
Please use appropriate name for member functions.

[kojii, 2017-06-21 09:47:13]

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

https://codereview.chromium.org/2943573002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:372:
void NGInlineItemsBuilder::AddLastTrailingSpaceToRemovedIndexes(
This may depend on above, but I can't understand what this function is doing.
Can you explain?

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

https://codereview.chromium.org/2943573002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:107:
Vector<Vector<unsigned>>* collapsed_indexes_;
On 2017/06/21 at 04:22:41, yosin_UTC9 wrote:
> Could you introduce OffsetMappingBuilder class to hold |collapsed_indexes_|
and |input_strings_length_| and
> member functions to update them in another file?
> We would like to bold editing related part in core/layout for ease of
maintenance.

I take this opposite. Since this is tightly coupled with this class, separating
out will make us harder to change this class. Higher-level classes/logic can
live in editing.

Agree on better to have a struct/class of a vector, rather than two vector, but
I haven't understood why we need a vector of vector for each append. Isn't what
we need just a map of character indexes?

If possible, I'd like to avoid editing code depends on how we call Append(), but
you must have some needs for this data, can you explain?

[Xiaocheng, 2017-06-21 18:15:07]

Thanks for the review. I think it's better to take an OffsetMappingBuilder as
the additional parameter, rather than a raw vector of vector. I'll update the
patch to see how it works.

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

https://codereview.chromium.org/2943573002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:372:
void NGInlineItemsBuilder::AddLastTrailingSpaceToRemovedIndexes(
On 2017/06/21 at 09:47:13, kojii wrote:
> This may depend on above, but I can't understand what this function is doing.
Can you explain?

This function is called when RemoveTrailingCollapsibleSpace() removes a trailing
space that was previously appended.

It finds the index of this space in its string, which may or may not be the
current string being appended, and adds it to |collapsed_indexes_|.

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

https://codereview.chromium.org/2943573002/diff/80001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:107:
Vector<Vector<unsigned>>* collapsed_indexes_;
On 2017/06/21 at 09:47:13, kojii wrote:
> On 2017/06/21 at 04:22:41, yosin_UTC9 wrote:
> > Could you introduce OffsetMappingBuilder class to hold |collapsed_indexes_|
and |input_strings_length_| and
> > member functions to update them in another file?
> > We would like to bold editing related part in core/layout for ease of
maintenance.
> 
> I take this opposite. Since this is tightly coupled with this class,
separating out will make us harder to change this class. Higher-level
classes/logic can live in editing.

I agree with yosin@ that it's a better pattern if we take an
OffsetMappingBuilder as the optional parameter instead of |collapsed_indexes|.
With the builder, we can return the collapsing information in a more flexible
way, and allows the builder to utilize the information more easily. I'll update
the patch to see how it works.

> 
> Agree on better to have a struct/class of a vector, rather than two vector,
but I haven't understood why we need a vector of vector for each append. Isn't
what we need just a map of character indexes?

The current design is: for each string appended, we need a vector to store the
indexes of the collapsed spaces. So we need a vector of vector for all the
strings together. An offset mapping builder will take this vector of vector and
build the mapping.

> 
> If possible, I'd like to avoid editing code depends on how we call Append(),
but you must have some needs for this data, can you explain?

I'll see if the dependence can be reduced in the updated patch.

[Xiaocheng, 2017-06-21 23:48:57]

PTAL at Patch 7. I think this version is cleaner.

Instead of returning vectors, this version takes an NGOffsetMappingBuilder as
the optional parameter, so that:

- NGOffsetMappingBuilder::AppendBijection(length) is called if the next |length|
characters should be appended without collapsing
- NGOffsetMappingBuilder::AppendCollapsed(length) is called if the next |length|
characters should be collapsed
- NGOffsetMappingBuilder::CollapseLastCharacter() is called if the last appended
character should be changed into collapsed

In this way the API is much more flexible. It doesn't constrain the data format
of the white space collapsing information, and implementation of the builder can
use the information in whatever way it likes.

[Xiaocheng, 2017-06-22 03:15:08]

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

[commit-bot: I haz the power, 2017-06-22 03:15:22]

Dry run: CQ is trying da patch.

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

[yosin_UTC9, 2017-06-22 03:31:05]

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:19:
virtual ~NGOffsetMappingBuilder();
Why interface? Do you want to introduce DoNothingOffsetMappingBuilder to avoid
|if (mapping_builder_) ...|?
It seems we still have |if (mapping_builder_) ...| in |NGInlineItemBuilder|.
Maybe for testing?

If using an interface is just for testing, it is better to have concrete class
and having member test only(?) function to access
result mapping.

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:25:
DISALLOW_COPY_AND_ASSIGN(NGOffsetMappingBuilder);
nit: |DISALLOW_...| should be in private section.

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:100:
NGOffsetMappingBuilder* mapping_builder_;
nit: s/NGOffsetMappingBuilder*/NGOffsetMappingBuilder* const/

[Xiaocheng, 2017-06-22 03:36:10]

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:19:
virtual ~NGOffsetMappingBuilder();
On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> Why interface? Do you want to introduce DoNothingOffsetMappingBuilder to avoid
|if (mapping_builder_) ...|?
> It seems we still have |if (mapping_builder_) ...| in |NGInlineItemBuilder|.
> Maybe for testing?
> 
> If using an interface is just for testing, it is better to have concrete class
and having member test only(?) function to access
> result mapping.

I would like to have different types of offset mapping builder. Some builders in
my mind are:

1. For offset mapping before and white space collapsing
2. For offset mapping before and after text-transform
3. For offset mapping from DOM to after white space collapsing, which is
obtained by compositing the above two

So I intentionally leave some flexibility in the class so that it may grow into
something powerful.

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:25:
DISALLOW_COPY_AND_ASSIGN(NGOffsetMappingBuilder);
On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> nit: |DISALLOW_...| should be in private section.

Will do.

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.h:100:
NGOffsetMappingBuilder* mapping_builder_;
On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> nit: s/NGOffsetMappingBuilder*/NGOffsetMappingBuilder* const/

Will do.

[yosin_UTC9, 2017-06-22 03:44:22]

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:19:
virtual ~NGOffsetMappingBuilder();
On 2017/06/22 at 03:36:10, Xiaocheng wrote:
> On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> > Why interface? Do you want to introduce DoNothingOffsetMappingBuilder to
avoid |if (mapping_builder_) ...|?
> > It seems we still have |if (mapping_builder_) ...| in |NGInlineItemBuilder|.
> > Maybe for testing?
> > 
> > If using an interface is just for testing, it is better to have concrete
class and having member test only(?) function to access
> > result mapping.
> 
> I would like to have different types of offset mapping builder. Some builders
in my mind are:
> 
> 1. For offset mapping before and white space collapsing
> 2. For offset mapping before and after text-transform
> 3. For offset mapping from DOM to after white space collapsing, which is
obtained by compositing the above two
> 
> So I intentionally leave some flexibility in the class so that it may grow
into something powerful.

Editing is case 3. What cases do use 1 and 2?

[Xiaocheng, 2017-06-22 03:50:07]

On 2017/06/22 at 03:44:22, yosin wrote:
>
https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
> File third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):
> 
>
https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
> third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:19:
virtual ~NGOffsetMappingBuilder();
> On 2017/06/22 at 03:36:10, Xiaocheng wrote:
> > On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> > > Why interface? Do you want to introduce DoNothingOffsetMappingBuilder to
avoid |if (mapping_builder_) ...|?
> > > It seems we still have |if (mapping_builder_) ...| in
|NGInlineItemBuilder|.
> > > Maybe for testing?
> > > 
> > > If using an interface is just for testing, it is better to have concrete
class and having member test only(?) function to access
> > > result mapping.
> > 
> > I would like to have different types of offset mapping builder. Some
builders in my mind are:
> > 
> > 1. For offset mapping before and white space collapsing
> > 2. For offset mapping before and after text-transform
> > 3. For offset mapping from DOM to after white space collapsing, which is
obtained by compositing the above two
> > 
> > So I intentionally leave some flexibility in the class so that it may grow
into something powerful.
> 
> Editing is case 3. What cases do use 1 and 2?

What this patch does is in fact case 1, not case 3.

Our current strategy is to assume that cases 1 and 3 are the same because
there's no handling of case 2 at all in the entire code base...

I would like to add handling of case 2 in the future, so that we handle case 3
correctly.

[kojii, 2017-06-22 05:01:39]

Sorry, this is even harder to understand than before.

What is "bijection"? Please use more common term, long word is fine.

Please include impl, it's not easy to review interfaces without impl.

And more comments in source file please. If questions were asked in the review,
it's a good indication that the code should be re-written for easier to
understand, or comments are needed. NG prefers more comments than we used to.

[commit-bot: I haz the power, 2017-06-22 05:24:37]

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

[commit-bot: I haz the power, 2017-06-22 05:24:38]

Dry run: This issue passed the CQ dry run.

[Xiaocheng, 2017-06-22 06:02:10]

On 2017/06/22 at 05:01:39, kojii wrote:
> Sorry, this is even harder to understand than before.

Sorry I should have included documentation in this patch. I was thinking posting
it first and see if you like the idea.

> 
> What is "bijection"? Please use more common term, long word is fine.

Maybe the functions of should be renamed as:

- AppendEqualLength(n) // Called when the next n characters of the string are
appended as is
- AppendCollapsed(n) // Called when the next n characters of the string are
collapsed
- CollapseLastCharacter() // Called when the last appended character should be
changed to collapsed

I made this change so that the more flexibility is given to
OffsetMappingBuilder, so that it can utilize the passed information in the most
convenient way.

> 
> Please include impl, it's not easy to review interfaces without impl.

Please refer to the unit test for a mock impl.

This patch is not supposed to include impl because we'll introduce different
mapping builders for different transformations. For example, text-transform and
whitespace collapsing need different builder impls.

Maybe I should write a doc to fully explain this idea first?

> 
> And more comments in source file please. If questions were asked in the
review, it's a good indication that the code should be re-written for easier to
understand, or comments are needed. NG prefers more comments than we used to.

Will do next time. Sorry for the confusion.

[kojii, 2017-06-22 07:00:31]

On 2017/06/22 at 06:02:10, xiaochengh wrote:
> On 2017/06/22 at 05:01:39, kojii wrote:
> > Sorry, this is even harder to understand than before.
> 
> Sorry I should have included documentation in this patch. I was thinking
posting it first and see if you like the idea.

Can be rough, formal ones can come later, but needed to understand your
intentions to review ;)

> 
> > 
> > What is "bijection"? Please use more common term, long word is fine.
> 
> Maybe the functions of should be renamed as:
> 
> - AppendEqualLength(n) // Called when the next n characters of the string are
appended as is
> - AppendCollapsed(n) // Called when the next n characters of the string are
collapsed
> - CollapseLastCharacter() // Called when the last appended character should be
changed to collapsed
> 
> I made this change so that the more flexibility is given to
OffsetMappingBuilder, so that it can utilize the passed information in the most
convenient way.

Understood now. Maybe:
  NotifyCharactersAppended(n)
  NotifyCharactersCollapsed(n)
  NotifyLastCharactersChangedToCollapsed(n)
? (assuming these are what it means?)

> > Please include impl, it's not easy to review interfaces without impl.
> 
> Please refer to the unit test for a mock impl.

Oh, I missed it, sorry. Ok, mock is for test and also for understanding
interface, can we just use Vector or BitVector, not bit operations, for better
readability?

> This patch is not supposed to include impl because we'll introduce different
mapping builders for different transformations. For example, text-transform and
whitespace collapsing need different builder impls.

One impl is fine. I think text-transform will need different interfaces too, but
probably we can build it on top of this.

> Maybe I should write a doc to fully explain this idea first?

Just wish more comments. Commented code is generally easier for me than doc,
unless we're discussing very high-level thing.

> > And more comments in source file please. If questions were asked in the
review, it's a good indication that the code should be re-written for easier to
understand, or comments are needed. NG prefers more comments than we used to.
> 
> Will do next time. Sorry for the confusion.

Not a confusion at all, I know this is different style than we used to. I was
asked to add comments several times by reviewers and now I like it, I hope
you'll like it too.

[yosin_UTC9, 2017-06-22 07:01:22]

On 2017/06/22 at 03:50:07, xiaochengh wrote:
> On 2017/06/22 at 03:44:22, yosin wrote:
> >
https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
> > File
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):
> > 
> >
https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
> > third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:19:
virtual ~NGOffsetMappingBuilder();
> > On 2017/06/22 at 03:36:10, Xiaocheng wrote:
> > > On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> > > > Why interface? Do you want to introduce DoNothingOffsetMappingBuilder to
avoid |if (mapping_builder_) ...|?
> > > > It seems we still have |if (mapping_builder_) ...| in
|NGInlineItemBuilder|.
> > > > Maybe for testing?
> > > > 
> > > > If using an interface is just for testing, it is better to have concrete
class and having member test only(?) function to access
> > > > result mapping.
> > > 
> > > I would like to have different types of offset mapping builder. Some
builders in my mind are:
> > > 
> > > 1. For offset mapping before and white space collapsing
> > > 2. For offset mapping before and after text-transform
> > > 3. For offset mapping from DOM to after white space collapsing, which is
obtained by compositing the above two
> > > 
> > > So I intentionally leave some flexibility in the class so that it may grow
into something powerful.
> > 
> > Editing is case 3. What cases do use 1 and 2?
> 
> What this patch does is in fact case 1, not case 3.
> 
> Our current strategy is to assume that cases 1 and 3 are the same because
there's no handling of case 2 at all in the entire code base...
> 
> I would like to add handling of case 2 in the future, so that we handle case 3
correctly.

What client use case 2, == text-transform only w/o whitespace collapsing?

[Xiaocheng, 2017-06-22 07:10:25]

On 2017/06/22 at 07:01:22, yosin wrote:
> On 2017/06/22 at 03:50:07, xiaochengh wrote:
> > On 2017/06/22 at 03:44:22, yosin wrote:
> > >
https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
> > > File
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):
> > > 
> > >
https://codereview.chromium.org/2943573002/diff/120001/third_party/WebKit/Sou...
> > >
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:19:
virtual ~NGOffsetMappingBuilder();
> > > On 2017/06/22 at 03:36:10, Xiaocheng wrote:
> > > > On 2017/06/22 at 03:31:04, yosin_UTC9 wrote:
> > > > > Why interface? Do you want to introduce DoNothingOffsetMappingBuilder
to avoid |if (mapping_builder_) ...|?
> > > > > It seems we still have |if (mapping_builder_) ...| in
|NGInlineItemBuilder|.
> > > > > Maybe for testing?
> > > > > 
> > > > > If using an interface is just for testing, it is better to have
concrete class and having member test only(?) function to access
> > > > > result mapping.
> > > > 
> > > > I would like to have different types of offset mapping builder. Some
builders in my mind are:
> > > > 
> > > > 1. For offset mapping before and white space collapsing
> > > > 2. For offset mapping before and after text-transform
> > > > 3. For offset mapping from DOM to after white space collapsing, which is
obtained by compositing the above two
> > > > 
> > > > So I intentionally leave some flexibility in the class so that it may
grow into something powerful.
> > > 
> > > Editing is case 3. What cases do use 1 and 2?
> > 
> > What this patch does is in fact case 1, not case 3.
> > 
> > Our current strategy is to assume that cases 1 and 3 are the same because
there's no handling of case 2 at all in the entire code base...
> > 
> > I would like to add handling of case 2 in the future, so that we handle case
3 correctly.
> 
> What client use case 2, == text-transform only w/o whitespace collapsing?

No. However, case 3 can only be solved by combining results of cases 1 and 2

[Xiaocheng, 2017-06-22 07:12:47]

On 2017/06/22 at 07:00:31, kojii wrote:
> On 2017/06/22 at 06:02:10, xiaochengh wrote:
> > On 2017/06/22 at 05:01:39, kojii wrote:
> > > Sorry, this is even harder to understand than before.
> > 
> > Sorry I should have included documentation in this patch. I was thinking
posting it first and see if you like the idea.
> 
> Can be rough, formal ones can come later, but needed to understand your
intentions to review ;)
> 
> > 
> > > 
> > > What is "bijection"? Please use more common term, long word is fine.
> > 
> > Maybe the functions of should be renamed as:
> > 
> > - AppendEqualLength(n) // Called when the next n characters of the string
are appended as is
> > - AppendCollapsed(n) // Called when the next n characters of the string are
collapsed
> > - CollapseLastCharacter() // Called when the last appended character should
be changed to collapsed
> > 
> > I made this change so that the more flexibility is given to
OffsetMappingBuilder, so that it can utilize the passed information in the most
convenient way.
> 
> Understood now. Maybe:
>   NotifyCharactersAppended(n)
>   NotifyCharactersCollapsed(n)
>   NotifyLastCharactersChangedToCollapsed(n)
> ? (assuming these are what it means?)

Yes, exactly.

> 
> > > Please include impl, it's not easy to review interfaces without impl.
> > 
> > Please refer to the unit test for a mock impl.
> 
> Oh, I missed it, sorry. Ok, mock is for test and also for understanding
interface, can we just use Vector or BitVector, not bit operations, for better
readability?
> 
> > This patch is not supposed to include impl because we'll introduce different
mapping builders for different transformations. For example, text-transform and
whitespace collapsing need different builder impls.
> 
> One impl is fine. I think text-transform will need different interfaces too,
but probably we can build it on top of this.

I'm think of using this interface to do something fancy, like concatenation and
composition of two builders.

I'll update the doc to include details of this idea.

> 
> > Maybe I should write a doc to fully explain this idea first?
> 
> Just wish more comments. Commented code is generally easier for me than doc,
unless we're discussing very high-level thing.
> 
> > > And more comments in source file please. If questions were asked in the
review, it's a good indication that the code should be re-written for easier to
understand, or comments are needed. NG prefers more comments than we used to.
> > 
> > Will do next time. Sorry for the confusion.
> 
> Not a confusion at all, I know this is different style than we used to. I was
asked to add comments several times by reviewers and now I like it, I hope
you'll like it too.

[Xiaocheng, 2017-06-22 07:14:34]

Sorry for my mistake of rushing too hard.

We've got quite some good new ideas in the review. I should update my design doc
first so that we can ensure that these ideas work, and also that anything landed
here is not going to be rewritten later.

This patch will not be updated before the doc update is done, which may take a
few days.

[kojii, 2017-06-22 07:53:15]

ok, look forward to updates.

Please keep in mind, NGInlineItemsBuilder is not really final. I'll probably
need to add some more logic, which you may need to add more notifications to
handle them. One that may come is change non-last characters to collapsed.

I appreciate your efforts to make these changes easier.

[yosin_UTC9, 2017-06-22 07:55:48]

On 2017/06/22 at 07:53:15, kojii wrote:
> ok, look forward to updates.
> 
> Please keep in mind, NGInlineItemsBuilder is not really final. I'll probably
need to add some more logic, which you may need to add more notifications to
handle them. One that may come is change non-last characters to collapsed.
> 
> I appreciate your efforts to make these changes easier.

Let's use concrete class for this patch to make this patch smaller.
And postpone discussion about interface or not.
I would like to see high-level API and usage in TextIterator.

[kojii, 2017-06-26 03:35:22]

On 2017/06/22 at 07:53:15, kojii wrote:
> Please keep in mind, NGInlineItemsBuilder is not really final. I'll probably
need to add some more logic, which you may need to add more notifications to
handle them. One that may come is change non-last characters to collapsed.

The mentioned change landed:
https://codereview.chromium.org/2951213005

I hope this made us a little easier, by avoiding changes to the interface after
landed.

[Xiaocheng, 2017-06-26 05:09:37]

On 2017/06/26 at 03:35:22, kojii wrote:
> On 2017/06/22 at 07:53:15, kojii wrote:
> > Please keep in mind, NGInlineItemsBuilder is not really final. I'll probably
need to add some more logic, which you may need to add more notifications to
handle them. One that may come is change non-last characters to collapsed.
> 
> The mentioned change landed:
> https://codereview.chromium.org/2951213005
> 
> I hope this made us a little easier, by avoiding changes to the interface
after landed.

Thanks! I'll study your patch tomorrow.

[Xiaocheng, 2017-06-27 22:31:20]

Description was changed from

==========
Make NGInlineItemsBuilder return info of collapsed white spaces

This patch allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition 2-d vector parameter |removed_indexes| , so that when the
builder finishes:
- For each appended string, a vector is added to |removed_indexes|
- The vector stores the indexes of all removed spaces in the string in sorted
  order

Clients of NGInlineItemsBuilder can hence collect the reported indexes to build
offset mapping between DOM data strings and the text content of NGInlineNode.

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

to

==========
Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

This patch:

1. Introduces the NGOffsetMappingBuilder class with a mock implementation;

2. Allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition NGOffsetMappingBuilder parameter, and use it to
construct the whitespace-collapsed offset mapping. The way how the
NGOffsetMappingBuilder is used is straightforward: whenever |text_| is
modified, NGOffsetMappingBuilder should be notified correspondingly.

This patch is the part of the project to support DOM/TextContent offset
mapping in LayoutNG. Design doc: https://goo.gl/CJbxky

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

[Xiaocheng, 2017-06-27 22:33:00]

Patch updated following the updated design doc.

I also did the same benchmark before, and found that the nullptr check caused %2
performance regression... Should I templatize NGInlineItemsBuilder?

Benchmark results:
https://docs.google.com/a/chromium.org/spreadsheets/d/1gSonaK8lvPSUzLy6-TFDJk...

[yosin_UTC9, 2017-06-28 01:40:08]

On 2017/06/27 at 22:33:00, xiaochengh wrote:
> Patch updated following the updated design doc.
> 
> I also did the same benchmark before, and found that the nullptr check caused
%2 performance regression... 
> Should I templatize NGInlineItemsBuilder?
Yes, please. It seems mapping builder is now called for every character instead
of only for collapsed whitespace.

> 
> Benchmark results:
https://docs.google.com/a/chromium.org/spreadsheets/d/1gSonaK8lvPSUzLy6-TFDJk...

[yosin_UTC9, 2017-06-28 01:44:21]

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

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.cc:16:
DCHECK_GT(length, 0u);
Please add |DCHECK(!mapping_.IsEmpty())| for |mapping_.back()|

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.cc:25:
unsigned back = mapping_.back();
nit: s/unsigned/const unsigned/
Please add |DCHECK(!mapping_.IsEmpty())| for |mapping_.back()|

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.cc:31:
DCHECK(mapping_.size());
nit: s/mapping_.size()/!mapping.IsEmpty()/

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

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:197:
mapping_builder_->AppendIdentityMapping(end_of_non_space - i);
So, do we call mapping builder for every word?

[Xiaocheng, 2017-06-28 02:05:20]

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

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc:197:
mapping_builder_->AppendIdentityMapping(end_of_non_space - i);
On 2017/06/28 at 01:44:21, yosin_UTC9 wrote:
> So, do we call mapping builder for every word?

Yes. To decouple the mapping builder with impl details in whitespace collapsing
and inline collection, it should be notified of every change to |text_| and
every collapsed space.

[Xiaocheng, 2017-06-28 03:34:05]

Updated. NGInlineItemsBuilder is templatized in a preparation patch.

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

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.cc:16:
DCHECK_GT(length, 0u);
On 2017/06/28 at 01:44:21, yosin_UTC9 wrote:
> Please add |DCHECK(!mapping_.IsEmpty())| for |mapping_.back()|

Done.

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.cc:25:
unsigned back = mapping_.back();
On 2017/06/28 at 01:44:21, yosin_UTC9 wrote:
> nit: s/unsigned/const unsigned/
> Please add |DCHECK(!mapping_.IsEmpty())| for |mapping_.back()|

Done.

https://codereview.chromium.org/2943573002/diff/160001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.cc:31:
DCHECK(mapping_.size());
On 2017/06/28 at 01:44:21, yosin_UTC9 wrote:
> nit: s/mapping_.size()/!mapping.IsEmpty()/

Done.

[Xiaocheng, 2017-06-28 03:34:10]

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

[commit-bot: I haz the power, 2017-06-28 03:34:33]

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-06-28 04:13:56]

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

[commit-bot: I haz the power, 2017-06-28 04:13:57]

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

[Xiaocheng, 2017-06-28 05:32:37]

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

[commit-bot: I haz the power, 2017-06-28 05:32: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-06-28 07:30:28]

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

[commit-bot: I haz the power, 2017-06-28 07:30:30]

Dry run: This issue passed the CQ dry run.

[kojii, 2017-06-28 07:45:50]

lgtm w/nits

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/BUILD.gn (right):

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/BUILD.gn:330:
"ng/api/ng_offset_mapping_builder.h",
Can you please put them into "inline"? These are about inlines.

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:74:
Vector<unsigned> mapping_;
Can add explanation what this holds? "This is a vector of ..."

[Xiaocheng, 2017-06-28 18:21:58]

Thanks for reviewing!

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/BUILD.gn (right):

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/BUILD.gn:330:
"ng/api/ng_offset_mapping_builder.h",
On 2017/06/28 at 07:45:50, kojii wrote:
> Can you please put them into "inline"? These are about inlines.

Done.

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h
(right):

https://codereview.chromium.org/2943573002/diff/190001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/layout/ng/api/ng_offset_mapping_builder.h:74:
Vector<unsigned> mapping_;
On 2017/06/28 at 07:45:50, kojii wrote:
> Can add explanation what this holds? "This is a vector of ..."

Done.

[Xiaocheng, 2017-06-28 18:22:05]

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

[commit-bot: I haz the power, 2017-06-28 18:22:23]

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-06-28 18:35:19]

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

[commit-bot: I haz the power, 2017-06-28 18:35:20]

Dry run: Try jobs failed on following builders:
  chromeos_amd64-generic_chromium_compile_only_ng on
master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromeos_amd64-...)
  chromeos_daisy_chromium_compile_only_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/chromeos_daisy_...)
  mac_chromium_compile_dbg_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_comp...)

[Xiaocheng, 2017-06-28 18:45:14]

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

[commit-bot: I haz the power, 2017-06-28 18:45:44]

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-06-28 19:19:35]

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

[commit-bot: I haz the power, 2017-06-28 19:19:36]

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

[Xiaocheng, 2017-06-28 20:53:59]

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

[commit-bot: I haz the power, 2017-06-28 20:54:37]

Dry run: CQ is trying da patch.

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

[Xiaocheng, 2017-06-28 23:17:53]

The CQ bit was unchecked by xiaochengh@chromium.org

[Xiaocheng, 2017-06-28 23:17:56]

The CQ bit was checked by xiaochengh@chromium.org

[Xiaocheng, 2017-06-28 23:18:02]

The patchset sent to the CQ was uploaded after l-g-t-m from kojii@chromium.org
Link to the patchset: https://codereview.chromium.org/2943573002/#ps230001
(title: "Wed Jun 28 11:44:29 PDT 2017")

[commit-bot: I haz the power, 2017-06-28 23:18:25]

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-06-28 23:32:01]

CQ is committing da patch.

Bot data: {"patchset_id": 230001, "attempt_start_ts": 1498691876399000,
"parent_rev": "fb97d866ca2ba77f826975a13524eae76839c37a", "commit_rev":
"a20841a144602be2bc3f16c853edbf422053b958"}

[commit-bot: I haz the power, 2017-06-28 23:32:25]

CQ is committing da patch.

Bot data: {"patchset_id": 230001, "attempt_start_ts": 1498691876399000,
"parent_rev": "e14c4c49b1644ac9afce55148186cd0c9d9ad3a8", "commit_rev":
"121980e014681402b93fd93279af8622a45da57e"}

[commit-bot: I haz the power, 2017-06-28 23:32:39]

CQ is committing da patch.

Bot data: {"patchset_id": 230001, "attempt_start_ts": 1498691876399000,
"parent_rev": "2f7fc637e426f4d432e35bae82609280add316fd", "commit_rev":
"1f4be4da171cead27321f786d3b1306fd6bffeb3"}

[commit-bot: I haz the power, 2017-06-28 23:32:52]

Description was changed from

==========
Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

This patch:

1. Introduces the NGOffsetMappingBuilder class with a mock implementation;

2. Allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition NGOffsetMappingBuilder parameter, and use it to
construct the whitespace-collapsed offset mapping. The way how the
NGOffsetMappingBuilder is used is straightforward: whenever |text_| is
modified, NGOffsetMappingBuilder should be notified correspondingly.

This patch is the part of the project to support DOM/TextContent offset
mapping in LayoutNG. Design doc: https://goo.gl/CJbxky

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

to

==========
Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

This patch:

1. Introduces the NGOffsetMappingBuilder class with a mock implementation;

2. Allows NGInlineItemsBuilder to report how white spaces are collapsed
by taking an addition NGOffsetMappingBuilder parameter, and use it to
construct the whitespace-collapsed offset mapping. The way how the
NGOffsetMappingBuilder is used is straightforward: whenever |text_| is
modified, NGOffsetMappingBuilder should be notified correspondingly.

This patch is the part of the project to support DOM/TextContent offset
mapping in LayoutNG. Design doc: https://goo.gl/CJbxky

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

Review-Url: https://codereview.chromium.org/2943573002
Cr-Commit-Position: refs/heads/master@{#483192}
Committed:
https://chromium.googlesource.com/chromium/src/+/1f4be4da171cead27321f786d3b1...
==========

[commit-bot: I haz the power, 2017-06-28 23:32:54]

Committed patchset #13 (id:230001) as
https://chromium.googlesource.com/chromium/src/+/1f4be4da171cead27321f786d3b1...