ALL-IN-ONE: Optimization to previousBoundary() and nextBoundary()

Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed).

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16) (landed).

3. Introduce the |TextBuffer<Direction>| class for efficiently
concatenating text extracted from text iterators. Specifically,
- |TextBuffer<TextBufferForwards>| performs appendings efficiently
- |TextBuffer<TextBufferBackwards>| performs prependings efficiently
The class is implemented as a wrapper of |WTF::Vector|.

4. Detemplatize |copyTextTo()|, fixing its output type as |TextBuffer|.

5. Introduce the |TextAccumulator<Buffer>| class, which wraps |TextBuffer|
and handles text accumulation progressively. The purpose is to prevent
swallowing a huge text node all at once.

6. Optimize |previousBoundary()| and |nextBoundary()| with |TextAccumulator|.

(7. Search for some other places where applying |TextAccumulator| improves
performance.)

BUG=109587

[Xiaocheng, 2016-01-19 08:57:08]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It will be split into
the following parts for review:

1. Add |characterAt()| to |TextIterator|;

2. Allow text iterators to reveal their traversal direction and strategy;

3. Introduce the |ProgressTextAccumulator| class for progressively accumulating
text from text iterators;

4. Optimize |previousBoundary()| and |nextBoundary()| with the above class.

BUG=109587
==========

[yosin_UTC9, 2016-01-20 01:30:21]

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

[yosin_UTC9, 2016-01-20 01:30:22]

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
File
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
(right):

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:32:
void accumulateTextTo(Buffer& output, bool textSecurityAware = false)
Please don't use |bool| parameter,  we should use |enum class| or avoid to use
such flag at all.

Where do we call this function with |textSecurityAware=false|? These call sites
seem be insecure.

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:43:
if (Iterator::direction == TextIteratorDirection::TextIteratorForward)
Can we avoid to use |prepend|? Do clients of this class take accumulating
characters before finishing accumulation?
If clients take characters after accumulating, this class can reverse at end of
accumulating. 
Please check usage pattern and make clients not to access being accumulated
characters.

[Xiaocheng, 2016-01-20 01:47:46]

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
File
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
(right):

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:32:
void accumulateTextTo(Buffer& output, bool textSecurityAware = false)
On 2016/01/20 at 01:30:22, Yosi_UTC9 wrote:
> Please don't use |bool| parameter,  we should use |enum class| or avoid to use
such flag at all.
> 
> Where do we call this function with |textSecurityAware=false|? These call
sites seem be insecure.

There is no call site with |textSecurityAware=false|.

I thought this could make the new class more general, but it seems to be a bad
idea. I'll remove the flag.

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:43:
if (Iterator::direction == TextIteratorDirection::TextIteratorForward)
On 2016/01/20 at 01:30:22, Yosi_UTC9 wrote:
> Can we avoid to use |prepend|? Do clients of this class take accumulating
characters before finishing accumulation?
> If clients take characters after accumulating, this class can reverse at end
of accumulating. 
> Please check usage pattern and make clients not to access being accumulated
characters.

There is one (and only one) such client in |previousBoundary()|, which is the
while loop starting from this line:

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...

It iteratively prepends text to a buffer and passes the buffer to ICU for
finding boundaries.

[yosin_UTC9, 2016-01-20 02:11:16]

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
File
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
(right):

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:32:
void accumulateTextTo(Buffer& output, bool textSecurityAware = false)
On 2016/01/20 at 01:47:46, Xiaocheng wrote:
> On 2016/01/20 at 01:30:22, Yosi_UTC9 wrote:
> > Please don't use |bool| parameter,  we should use |enum class| or avoid to
use such flag at all.
> > 
> > Where do we call this function with |textSecurityAware=false|? These call
sites seem be insecure.
> 
> There is no call site with |textSecurityAware=false|.
> 
> I thought this could make the new class more general, but it seems to be a bad
idea. I'll remove the flag.

Let's be lazy. We think it once we need to have insecure mode. (^_^)

https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:43:
if (Iterator::direction == TextIteratorDirection::TextIteratorForward)
On 2016/01/20 at 01:47:46, Xiaocheng wrote:
> On 2016/01/20 at 01:30:22, Yosi_UTC9 wrote:
> > Can we avoid to use |prepend|? Do clients of this class take accumulating
characters before finishing accumulation?
> > If clients take characters after accumulating, this class can reverse at end
of accumulating. 
> > Please check usage pattern and make clients not to access being accumulated
characters.
> 
> There is one (and only one) such client in |previousBoundary()|, which is the
while loop starting from this line:
> 
>
https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...
> 
> It iteratively prepends text to a buffer and passes the buffer to ICU for
finding boundaries.

Please include call sites changes in all-in-one patch to figure out more about
this.
I also would like to remove |Buffer| template parameter, it is too detail of
implementation. For backward iteration, I would like to use backward filling of
vector.

[Xiaocheng, 2016-01-20 04:07:11]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It will be split into
the following parts for review:

1. Add |characterAt()| to |TextIterator|;

2. Allow text iterators to reveal their traversal direction and strategy;

3. Introduce the |ProgressTextAccumulator| class for progressively accumulating
text from text iterators;

4. Optimize |previousBoundary()| and |nextBoundary()| with the above class.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It will be split into
the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator| to always copy
whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction and strategy;

4. Introduce the |ProgressTextAccumulator| class for progressively accumulating
text from text iterators;

5. Optimize |previousBoundary()| and |nextBoundary()| with the above class.
Originally, they call |copyTextTo()| directly and accumulate the full content of
each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn call
|copyTextTo()| with progressively growing lengths.

BUG=109587
==========

[Xiaocheng, 2016-01-20 04:10:42]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It will be split into
the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator| to always copy
whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction and strategy;

4. Introduce the |ProgressTextAccumulator| class for progressively accumulating
text from text iterators;

5. Optimize |previousBoundary()| and |nextBoundary()| with the above class.
Originally, they call |copyTextTo()| directly and accumulate the full content of
each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn call
|copyTextTo()| with progressively growing lengths.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator|
to always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction and strategy;

4. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators;

5. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

[Xiaocheng, 2016-01-20 04:11:16]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator|
to always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction and strategy;

4. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators;

5. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator|
to always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction and strategy;

4. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators;

5. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

[Xiaocheng, 2016-01-20 04:15:17]

On 2016/01/20 at 02:11:16, yosin wrote:
>
https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
> File
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
(right):
> 
>
https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
>
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:32:
void accumulateTextTo(Buffer& output, bool textSecurityAware = false)
> On 2016/01/20 at 01:47:46, Xiaocheng wrote:
> > On 2016/01/20 at 01:30:22, Yosi_UTC9 wrote:
> > > Please don't use |bool| parameter,  we should use |enum class| or avoid to
use such flag at all.
> > > 
> > > Where do we call this function with |textSecurityAware=false|? These call
sites seem be insecure.
> > 
> > There is no call site with |textSecurityAware=false|.
> > 
> > I thought this could make the new class more general, but it seems to be a
bad idea. I'll remove the flag.
> 
> Let's be lazy. We think it once we need to have insecure mode. (^_^)
> 
>
https://codereview.chromium.org/1604783002/diff/40001/third_party/WebKit/Sour...
>
third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h:43:
if (Iterator::direction == TextIteratorDirection::TextIteratorForward)
> On 2016/01/20 at 01:47:46, Xiaocheng wrote:
> > On 2016/01/20 at 01:30:22, Yosi_UTC9 wrote:
> > > Can we avoid to use |prepend|? Do clients of this class take accumulating
characters before finishing accumulation?
> > > If clients take characters after accumulating, this class can reverse at
end of accumulating. 
> > > Please check usage pattern and make clients not to access being
accumulated characters.
> > 
> > There is one (and only one) such client in |previousBoundary()|, which is
the while loop starting from this line:
> > 
> >
https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...
> > 
> > It iteratively prepends text to a buffer and passes the buffer to ICU for
finding boundaries.
> 
> Please include call sites changes in all-in-one patch to figure out more about
this.

Sorry, do you mean changing the description into what it looks like now?

> I also would like to remove |Buffer| template parameter, it is too detail of
implementation. For backward iteration, I would like to use backward filling of
vector.

Do we fix |Buffer| as |Vector<UChar, 1024>|?

[yosin_UTC9, 2016-01-20 05:21:44]

https://codereview.chromium.org/1604783002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/VisibleUnits.cpp (right):

https://codereview.chromium.org/1604783002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/VisibleUnits.cpp:762:
ProgressiveTextAccumulator<TextIteratorAlgorithm<Strategy>> it(searchStart,
searchEnd, TextIteratorEmitsCharactersBetweenAllVisiblePositions);
We should have both |accumulator| and |it| rather than
|ProgressiveTextAccumulator| does both accumulation and iteration.
# It seems we don't need to have "Progressive" in class name, it is also
implementation detail.

Here is sketch:

TextIterator it(...);
TextAccumulator accumulator;

while (!it.atEnd()) {
  accumulator.extract(&it); // copy character from it with calling it.advance();
  const auto& string = accumulator.toString(); // construct new Vector<UChar>
  next = searchFunction(string.data(), string.size(), ...)
  ...
}

This model move character buffer management into |TextAccumulator| and we don't
need to make |Buffer| as template parameter.

[Xiaocheng, 2016-01-20 08:00:08]

On 2016/01/20 at 05:21:44, yosin wrote:
>
https://codereview.chromium.org/1604783002/diff/60001/third_party/WebKit/Sour...
> File third_party/WebKit/Source/core/editing/VisibleUnits.cpp (right):
> 
>
https://codereview.chromium.org/1604783002/diff/60001/third_party/WebKit/Sour...
> third_party/WebKit/Source/core/editing/VisibleUnits.cpp:762:
ProgressiveTextAccumulator<TextIteratorAlgorithm<Strategy>> it(searchStart,
searchEnd, TextIteratorEmitsCharactersBetweenAllVisiblePositions);
> We should have both |accumulator| and |it| rather than
|ProgressiveTextAccumulator| does both accumulation and iteration.
> # It seems we don't need to have "Progressive" in class name, it is also
implementation detail.
> 
> Here is sketch:
> 
> TextIterator it(...);
> TextAccumulator accumulator;
> 
> while (!it.atEnd()) {
>   accumulator.extract(&it); // copy character from it with calling
it.advance();
>   const auto& string = accumulator.toString(); // construct new Vector<UChar>
>   next = searchFunction(string.data(), string.size(), ...)
>   ...
> }
> 
> This model move character buffer management into |TextAccumulator| and we
don't need to make |Buffer| as template parameter.

I agree that we should let |TextAccumulator| manage the buffer instead of the
text iterator.

Some thoughts on the iterative prepending issue: Maybe we should wrap
WTF::Vector into a dynamic array that grows from end to begin, namely, the last
element is put at a fixed position. Then we can completely get rid of this issue
and just use |prepend()| arbitrarily without any concern.

[Xiaocheng, 2016-01-20 11:26:15]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator|
to always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction and strategy;

4. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators;

5. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator|
to always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction;

4. Add |prependTo()| with templated buffer type to |WTFString|;

5. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators (the class also contains an
inner custom buffer for efficient iterative prepending);

6. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

[Xiaocheng, 2016-01-20 11:27:33]

I've added the inner buffer class which automatically handles iterative
buffering efficiently.

It requires adding |WTFString::prependTo()| with general output buffer type,
which should be reviewed in another CL.

[yosin_UTC9, 2016-01-21 01:23:29]

On 2016/01/20 at 11:27:33, xiaochengh wrote:
> I've added the inner buffer class which automatically handles iterative
buffering efficiently.
> 
> It requires adding |WTFString::prependTo()| with general output buffer type,
which should be reviewed in another CL.

I don't want to |WTFString::prependTo()|, we should avoid to use |prependTo()|,
which is performance evil for vector.
Can we make ICU boundary functions to work in backward?

[Xiaocheng, 2016-01-21 01:42:20]

On 2016/01/21 at 01:23:29, yosin wrote:
> On 2016/01/20 at 11:27:33, xiaochengh wrote:
> > I've added the inner buffer class which automatically handles iterative
buffering efficiently.
> > 
> > It requires adding |WTFString::prependTo()| with general output buffer type,
which should be reviewed in another CL.
> 
> I don't want to |WTFString::prependTo()|, we should avoid to use
|prependTo()|, which is performance evil for vector.
> Can we make ICU boundary functions to work in backward?

|WTFString::prependTo()| does not have any performance issue when prepending to
the new buffer class. That's the reason I wrote the new class.

[Xiaocheng, 2016-01-21 07:42:46]

On 2016/01/21 at 01:42:20, Xiaocheng wrote:
> On 2016/01/21 at 01:23:29, yosin wrote:
> > On 2016/01/20 at 11:27:33, xiaochengh wrote:
> > > I've added the inner buffer class which automatically handles iterative
buffering efficiently.
> > > 
> > > It requires adding |WTFString::prependTo()| with general output buffer
type, which should be reviewed in another CL.
> > 
> > I don't want to |WTFString::prependTo()|, we should avoid to use
|prependTo()|, which is performance evil for vector.
> > Can we make ICU boundary functions to work in backward?
> 
> |WTFString::prependTo()| does not have any performance issue when prepending
to the new buffer class. That's the reason I wrote the new class.

I've rewritten |SimplifiedBackwardsTextIterator::copyCodeUnitsTo|. Now it
doesn't call |WTFString::prependTo()| any more.

In fact there's no call site of |WTFString::prependTo()| any more. We should
remove it in another patch.

[Xiaocheng, 2016-01-21 07:45:30]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Augment |TextIterator| and |SimplifiedBackwardsTextIterator|
to always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction;

4. Add |prependTo()| with templated buffer type to |WTFString|;

5. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators (the class also contains an
inner custom buffer for efficient iterative prepending);

6. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction;

4. Detach |SimplifiedBackwardsTextIterator| from |WTFString::prependTo|;

5. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators (the class also contains an
inner custom buffer for efficient iterative prepending);

6. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

[Xiaocheng, 2016-01-22 02:04:30]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed);

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16);

3. Allow text iterators to reveal their traversal direction;

4. Detach |SimplifiedBackwardsTextIterator| from |WTFString::prependTo|;

5. Introduce the |ProgressTextAccumulator| class for progressively
accumulating text from text iterators (the class also contains an
inner custom buffer for efficient iterative prepending);

6. Optimize |previousBoundary()| and |nextBoundary()| with the above
class. Originally, they call |copyTextTo()| directly and accumulate
the full content of each text node all at once; now they call
|ProgressTextAccumulator::accumulateTextTo()| instead, which in turn
call |copyTextTo()| with progressively growing lengths.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed).

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16) (landed).

3. Introduce the |TextBufferTemplate<Direction>| class for efficiently
concatenating text extracted from text iterators. Specifically,
- |TextBufferTemplate<TextBufferForwards>| performs appendings efficiently
- |TextBufferTemplate<TextBufferBackwards>| performs prependings efficiently
The class is implemented as a wrapper of |WTF::Vector|.

4. Detemplatize |copyTextTo()|, make it output only to |TextBufferTemplate|.

5. Introduce the |TextAccumulatorTemplate<Direction>| class, which wraps
|TextBufferTemplate| and handles text accumulation progressively. The purpose
it to prevent swallowing a huge text node all at once.

6. Optimize |previousBoundary()| and |nextBoundary()| with
|TextAccumulatorTemplate|.

BUG=109587
==========

[Xiaocheng, 2016-01-22 07:10:10]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed).

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16) (landed).

3. Introduce the |TextBufferTemplate<Direction>| class for efficiently
concatenating text extracted from text iterators. Specifically,
- |TextBufferTemplate<TextBufferForwards>| performs appendings efficiently
- |TextBufferTemplate<TextBufferBackwards>| performs prependings efficiently
The class is implemented as a wrapper of |WTF::Vector|.

4. Detemplatize |copyTextTo()|, make it output only to |TextBufferTemplate|.

5. Introduce the |TextAccumulatorTemplate<Direction>| class, which wraps
|TextBufferTemplate| and handles text accumulation progressively. The purpose
it to prevent swallowing a huge text node all at once.

6. Optimize |previousBoundary()| and |nextBoundary()| with
|TextAccumulatorTemplate|.

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed).

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16) (landed).

3. Introduce the |TextBuffer<Direction>| class for efficiently
concatenating text extracted from text iterators. Specifically,
- |TextBuffer<TextBufferForwards>| performs appendings efficiently
- |TextBuffer<TextBufferBackwards>| performs prependings efficiently
The class is implemented as a wrapper of |WTF::Vector|.

4. Detemplatize |copyTextTo()|, fixing its output type as |TextBuffer|.

5. Introduce the |TextAccumulator<Buffer>| class, which wraps |TextBuffer|
and handles text accumulation progressively. The purpose is to prevent
swallowing a huge text node all at once.

6. Optimize |previousBoundary()| and |nextBoundary()| with
|TextAccumulatorTemplate|.

(7. Search for some other places where applying |TextAccumulator| improves
performance.)

BUG=109587
==========

[Xiaocheng, 2016-01-22 07:19:58]

The patch (and its description) has been significantly revised. PTAL.

The revised description also tells what has been changed.

[Xiaocheng, 2016-01-22 07:51:39]

Description was changed from

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed).

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16) (landed).

3. Introduce the |TextBuffer<Direction>| class for efficiently
concatenating text extracted from text iterators. Specifically,
- |TextBuffer<TextBufferForwards>| performs appendings efficiently
- |TextBuffer<TextBufferBackwards>| performs prependings efficiently
The class is implemented as a wrapper of |WTF::Vector|.

4. Detemplatize |copyTextTo()|, fixing its output type as |TextBuffer|.

5. Introduce the |TextAccumulator<Buffer>| class, which wraps |TextBuffer|
and handles text accumulation progressively. The purpose is to prevent
swallowing a huge text node all at once.

6. Optimize |previousBoundary()| and |nextBoundary()| with
|TextAccumulatorTemplate|.

(7. Search for some other places where applying |TextAccumulator| improves
performance.)

BUG=109587
==========

to

==========
Optimization to previousBoundary() and nextBoundary()

This is an all-in-one patch only for reference purposes. It
will be split into the following parts for review:

1. Add |characterAt()| to |TextIterator| (landed).

2. Make sure |TextIterator| and |SimplifiedBackwardsTextIterator|
always copy whole code points (at least on well-formed UTF-16) (landed).

3. Introduce the |TextBuffer<Direction>| class for efficiently
concatenating text extracted from text iterators. Specifically,
- |TextBuffer<TextBufferForwards>| performs appendings efficiently
- |TextBuffer<TextBufferBackwards>| performs prependings efficiently
The class is implemented as a wrapper of |WTF::Vector|.

4. Detemplatize |copyTextTo()|, fixing its output type as |TextBuffer|.

5. Introduce the |TextAccumulator<Buffer>| class, which wraps |TextBuffer|
and handles text accumulation progressively. The purpose is to prevent
swallowing a huge text node all at once.

6. Optimize |previousBoundary()| and |nextBoundary()| with |TextAccumulator|.

(7. Search for some other places where applying |TextAccumulator| improves
performance.)

BUG=109587
==========

[Xiaocheng, 2016-01-26 13:38:57]

Ping and PTAL.

The patch (and its description) has been significantly revised.

The revised description also tells what has been changed.

[yosin_UTC9, 2016-02-09 02:28:05]

https://codereview.chromium.org/1604783002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/editing/VisibleUnits.cpp (right):

https://codereview.chromium.org/1604783002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/VisibleUnits.cpp:697: string.extract(it);
it.copyTo(string)

https://codereview.chromium.org/1604783002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/VisibleUnits.cpp:704: string.advance(it);
if (string.isSomeCondition()) {
  string.resetAccumulatedInCurrentNode(); // Not sure
  it.advance();
}

Not sure about |isSomeCondition()|, it is |m_accumulatedInCurrentNode ==
it.length())|