Return EphemeralRange from Editor::findRangeOfString.

Return EphemeralRange from Editor::findRangeOfString.

It is possible to use EphemeralRange instead of allocating a Range object
in Editor::find* functions.

BUG=

[Andrey Kraynov, 2015-10-21 11:20:40]

iceman@yandex-team.ru changed reviewers:
+ yosin@chromium.org

[Andrey Kraynov, 2015-10-21 11:20:40]

This is my attempt to use an EphemeralRange instead of Range objects in Editor
find related functions.

But I'm not sure that I did it right.
It seems that main job were done in Range constructor to detect bad boundaries.
And the most important function is static function 
checkForDifferentRootContainer in Range.cpp, and then
Range::compareBoundaryPoints.
There are couple of functions for comparing Positions in
EditingUtilities.{h,cpp}
and even a method PositionTemplate<Strategy>::compareTo(). Currently I used the
latter.

Unfortunately, I still had to use a Range object in 
findStringAndScrollToVisibleAlgorithm, to get it's boundingBox and return to
caller.

Also, I removed reference to a Document from internal find* functions parameters
and use ephemeralRange.document() instead.
Is it OK?

I'll be glad to have some advices.

yosin@, PTAL
Thanks in advance!

[yosin_UTC9, 2015-10-22 02:26:43]

On 2015/10/21 at 11:20:40, iceman wrote:
> This is my attempt to use an EphemeralRange instead of Range objects in Editor
find related functions.
> 
> But I'm not sure that I did it right.
> It seems that main job were done in Range constructor to detect bad
boundaries. And the most important function is static function 
> checkForDifferentRootContainer in Range.cpp, and then
Range::compareBoundaryPoints.
> There are couple of functions for comparing Positions in
EditingUtilities.{h,cpp}
> and even a method PositionTemplate<Strategy>::compareTo(). Currently I used
the latter.
> 

Let's delegate handling of tree crossing range to caller. We can use two Range
objects
to represent range in composed tree, e.g.

EphemeralRangeInComposedTree match = findStringAndScrollToVisible(...)
m_activeMatchStart =
Range::createCollapsedRange(toPositionInDOMTree(match.startPosition()));
m_activeMatchEnd =
Range::createCollapsedRange(toPositionInDOMTree(match.startPosition()));
// Note: createCollapedRange() doesn't exist. Use it for short.

> Unfortunately, I still had to use a Range object in 
> findStringAndScrollToVisibleAlgorithm, to get it's boundingBox and return to
caller.
Let's make EphemeraRangeTempalte version of boundingBox().


> Also, I removed reference to a Document from internal find* functions
parameters and use ephemeralRange.document() instead.
> Is it OK?
Good catch. I'm wander why I didn't.

[yosin_UTC9, 2015-10-22 02:28:28]

Thanks for tackling this!

My refactoring reaped low handing fruits. ;-P

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/Editor.cpp (left):

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1152:
RefPtrWillBeRawPtr<Range> resultRange = findRangeOfString(target,
EphemeralRange(selection.start(), selection.end()),
static_cast<FindOptions>(options | FindAPICall));
Just FYI. We have usage counters

- https://www.chromestatus.com/metrics/feature/popularity#WindowFind
 calls of window.find()
-
https://www.chromestatus.com/metrics/feature/popularity#WindowFindWithShadowTree
 number of window.find() enters shadow tree

I'll use "WindowFindWithShadowTree" as evidence to make TextIterator composed
tree
version only.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/Editor.cpp (right):

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1149: const EphemeralRange&
resultRange = findRangeOfString(
Remove |&|. Does clang allow this?

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1165:
RefPtrWillBeRawPtr<Range> nextMatch =
createRange(editor.findRangeOfString(target, previousMatch, options));
Let's return EphmeralRange here and ask call to handle it.
Note: We can't create Range objects which cross tree boundaries, see comments
for EphemeralRangeInComposedTree
version of createRange()

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1193: while
(endRootContainer->parentNode())
Can we use Node::commonAncestor()?

Why not position.compareTo() enough?

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1206: using EphemeralRangeT =
EphemeralRangeTemplate<Strategy>;
We don't have rule about "using alias". In our experience, it is hard to 
use consistent alias name across files and different alias names readers
confusing.

Since Blink doesn't limit length of line, at this time ;-), long original 
type name is preferred.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1213: const EphemeralRangeT&
resultRange = findPlainText(searchRange, target, options);
Remove |&|. I think returned object lives on stack or registers.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/EphemeralRange.cpp (right):

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/EphemeralRange.cpp:147:
PassRefPtrWillBeRawPtr<Range> createRange(const EphemeralRangeInComposedTree&
range)
Since DOM Range object can't represent a range crossing trees boundary.
Although, AFAKI, Range.cpp doesn't check this.
See Range::createAdjustedToTreeScope() how adjusting a range crossing 
tree boundary.

[Andrey Kraynov, 2015-10-22 09:46:25]

On 2015/10/22 02:26:43, Yosi_UTC9 wrote:
> Let's delegate handling of tree crossing range to caller. We can use two Range
> objects
> to represent range in composed tree, e.g.

It seems that such change will affect a lot of the TextFinder code, but I will
try.

> 
> > Unfortunately, I still had to use a Range object in 
> > findStringAndScrollToVisibleAlgorithm, to get it's boundingBox and return to
> caller.
> Let's make EphemeraRangeTempalte version of boundingBox(). 

Could you point me to it?
Range::boundingBox() uses Range::textRects function to gather rects.
I failed to find something similar for EphemeraRange.

> 
> > Also, I removed reference to a Document from internal find* functions
> parameters and use ephemeralRange.document() instead.
> > Is it OK?
> Good catch. I'm wander why I didn't.

In theory it is possible to pass a range from one document to Editor::find() of
the other document.
But the old code was vulnerable to that too.
How do you think, should we consider this case or it is a wrong assumption?

[Andrey Kraynov, 2015-10-22 09:53:20]

Thank you for all these comments!
I will rework this CL according to them.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/Editor.cpp (right):

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1149: const EphemeralRange&
resultRange = findRangeOfString(
On 2015/10/22 02:28:27, Yosi_UTC9 wrote:
> Remove |&|. Does clang allow this?

It's a valid C++ code for all compilers ;)

http://stackoverflow.com/questions/2784262/does-a-const-reference-prolong-the...
Temporary will live in the scope of const-reference.
RVO is unpredictable and EphemeralRange doesn't have a move-ctor, but we can
avoid creating a copy.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1193: while
(endRootContainer->parentNode())
On 2015/10/22 02:28:28, Yosi_UTC9 wrote:
> Can we use Node::commonAncestor()?
> 
> Why not position.compareTo() enough?

I looked at the checkForDifferentRootContainer() function and tried to keep
close to it.
checkForDifferentRootContainer checks for nodes common ancestor and then calls
Range::compareBoundaryPoints, which in turn calls comparePositionsInDOMTree from
EditingUtilities.
But Position::compareTo() just calls comparePositionsInDOMTree.

Maybe common ancestor check is a some kind of optimisation for early return?
How do you think, can we safely skip this check?
It seems that comparePositionsInDOMTree will try to find a commonAncestor and
return 0 if it doesn't exist.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1206: using EphemeralRangeT =
EphemeralRangeTemplate<Strategy>;
On 2015/10/22 02:28:27, Yosi_UTC9 wrote:
> Since Blink doesn't limit length of line, at this time ;-), long original 
> type name is preferred.

OK, I'll revert these changes.
But sometimes it's not easy to read Blink code ;(

[yosin_UTC9, 2015-10-23 01:52:50]

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/Editor.cpp (right):

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1193: while
(endRootContainer->parentNode())
On 2015/10/22 at 09:53:20, Andrey Kraynov wrote:
> On 2015/10/22 02:28:28, Yosi_UTC9 wrote:
> > Can we use Node::commonAncestor()?
> > 
> > Why not position.compareTo() enough?
> 
> I looked at the checkForDifferentRootContainer() function and tried to keep
close to it.
> checkForDifferentRootContainer checks for nodes common ancestor and then calls
Range::compareBoundaryPoints, which in turn calls comparePositionsInDOMTree from
EditingUtilities.
> But Position::compareTo() just calls comparePositionsInDOMTree.
> 
> Maybe common ancestor check is a some kind of optimisation for early return?
> How do you think, can we safely skip this check?
> It seems that comparePositionsInDOMTree will try to find a commonAncestor and
return 0 if it doesn't exist.

I have no idea when we have a range which start and end have no common ancestor.
One of start and end is orphaned?
If we're not sure, having ASSERT(commonAncestor(start, end)) is enough.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1206: using EphemeralRangeT =
EphemeralRangeTemplate<Strategy>;
On 2015/10/22 at 09:53:20, Andrey Kraynov wrote:
> On 2015/10/22 02:28:27, Yosi_UTC9 wrote:
> > Since Blink doesn't limit length of line, at this time ;-), long original 
> > type name is preferred.
> 
> OK, I'll revert these changes.
> But sometimes it's not easy to read Blink code ;(

You're not alone. I think so too.
I'm voting to use 80-char per line like Chromium.

[Andrey Kraynov, 2015-10-30 18:24:25]

Hi!

Now my CL compiles and webkit_unit_tests passed.
I reverted some changes in Editor and EphemeralRange files, and added a function
for finding range bounding box.

I don't want to make big changes in TextFinder class in this particular CL, so I
used the same approach as TextFinder::scopeStringMatchesAlgorithm does.
Collapsed ranges will be skipped now, but later I can use two ranges to
represent a range in composed tree, as you pointed to me earlier.

Please take a look at the latest changes.
Thanks!

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/Editor.cpp (right):

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1165:
RefPtrWillBeRawPtr<Range> nextMatch =
createRange(editor.findRangeOfString(target, previousMatch, options));
On 2015/10/22 02:28:28, Yosi_OOO_til_Oct_30 wrote:
> Let's return EphmeralRange here and ask call to handle it.
> Note: We can't create Range objects which cross tree boundaries, see comments
> for EphemeralRangeInComposedTree
> version of createRange()

Done.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1193: while
(endRootContainer->parentNode())
On 2015/10/23 01:52:50, Yosi_OOO_til_Oct_30 wrote:
> On 2015/10/22 at 09:53:20, Andrey Kraynov wrote:
> > On 2015/10/22 02:28:28, Yosi_UTC9 wrote:
> > > Can we use Node::commonAncestor()?
> > > 
> > > Why not position.compareTo() enough?
> > 
> > I looked at the checkForDifferentRootContainer() function and tried to keep
> close to it.
> > checkForDifferentRootContainer checks for nodes common ancestor and then
calls
> Range::compareBoundaryPoints, which in turn calls comparePositionsInDOMTree
from
> EditingUtilities.
> > But Position::compareTo() just calls comparePositionsInDOMTree.
> > 
> > Maybe common ancestor check is a some kind of optimisation for early return?
> > How do you think, can we safely skip this check?
> > It seems that comparePositionsInDOMTree will try to find a commonAncestor
and
> return 0 if it doesn't exist.
> 
> I have no idea when we have a range which start and end have no common
ancestor.
> One of start and end is orphaned?
> If we're not sure, having ASSERT(commonAncestor(start, end)) is enough.

Done.

https://codereview.chromium.org/1409073004/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/Editor.cpp:1206: using EphemeralRangeT =
EphemeralRangeTemplate<Strategy>;
On 2015/10/22 02:28:27, Yosi_OOO_til_Oct_30 wrote:
> We don't have rule about "using alias". In our experience, it is hard to 
> use consistent alias name across files and different alias names readers
> confusing.
> 
> Since Blink doesn't limit length of line, at this time ;-), long original 
> type name is preferred.

Done.

[yosin_UTC9, 2015-11-02 03:44:17]

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/Editor.cpp (right):

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/Editor.cpp:1203: return
(range.startPosition().compareTo(range.endPosition()) < 0);
nit: Could you omit parenthesis around return expression?

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/EphemeralRange.cpp (right):

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/EphemeralRange.cpp:136: IntRect
EphemeralRangeTemplate<Strategy>::textBoundingBox() const
Rather than copying code from Range::textRects(), can we share the code between
EphemeralRange and Range?

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/web/TextFinder.cpp (right):

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/web/TextFinder.cpp:131: if (!resultRange->collapsed())
{
nit: Please get rid of redundant curly braces.

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/web/TextFinder.cpp:136: // FIXME: Show such matches to
users.
nit: Please use "TODO(iceman):" instead of "FIXME:"

[Andrey Kraynov, 2015-11-02 14:06:57]

Fix nits.

I have extracted collecting of the text bounds into a function
|collectTextBoundsInRange| and placed it to
core/editing/EditingUtilities.{h,cpp}
Is there a better place for such function?

I failed to make it as a template, otherwise it could look better.

Please, take a look.

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/Editor.cpp (right):

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/Editor.cpp:1203: return
(range.startPosition().compareTo(range.endPosition()) < 0);
On 2015/11/02 03:44:17, Yosi_OOO_til_Oct_30 wrote:
> nit: Could you omit parenthesis around return expression?

Done.

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/EphemeralRange.cpp (right):

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/EphemeralRange.cpp:136: IntRect
EphemeralRangeTemplate<Strategy>::textBoundingBox() const
On 2015/11/02 03:44:17, Yosi_OOO_til_Oct_30 wrote:
> Rather than copying code from Range::textRects(), can we share the code
between
> EphemeralRange and Range?

I tried to do it.
Pros: it can be used to shorten both Range::textQuads and Range::textRects
function and remove code duplication.

Cons: my new function is quite ugly =(
Too many parameters and two overloads for IntRect and FloatQuad.

I failed to use NodeTraversalIterator here, because my function isn't a template
function.

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/web/TextFinder.cpp (right):

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/web/TextFinder.cpp:131: if (!resultRange->collapsed())
{
On 2015/11/02 03:44:17, Yosi_OOO_til_Oct_30 wrote:
> nit: Please get rid of redundant curly braces.

Done.

https://codereview.chromium.org/1409073004/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/web/TextFinder.cpp:136: // FIXME: Show such matches to
users.
On 2015/11/02 03:44:17, Yosi_OOO_til_Oct_30 wrote:
> nit: Please use "TODO(iceman):" instead of "FIXME:"

Done.

[yosin_UTC9, 2015-11-04 06:21:09]

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

[commit-bot: I haz the power, 2015-11-04 06:21:16]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1409073004/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1409073004/60001

[yosin_UTC9, 2015-11-04 07:11:06]

Let's use two |Range| object for representing active match and having position
in composed tree version
of DocumentMarkerController::addTextMatchMarker(), removeMarkers(), and
setMarkesActive(), which traverse composed tree and map them to DOM tree
positions. This doesn't need to generic, since document markers are
associated to |Text| node.

If we choose this way, we don't need to solve  shadow boundary crossing problem.

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

https://codereview.chromium.org/1409073004/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/EditingUtilities.cpp:1695: void
collectTextBoundsInRangeAlgorithm(
nit: Please add |static|, just in case.

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

https://codereview.chromium.org/1409073004/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/Editor.cpp:1195: static bool
rangeBoundariesAreValid(const EphemeralRangeTemplate<Strategy>& range)
This function doesn't check shadow boundary crossing as comment mentioned.

I talked with shadow DOM experts offline, there are no easy way to detect
crossing shadow boundary.

I think we want to have a way not to detect crossing shadow boundary.

https://codereview.chromium.org/1409073004/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/Editor.cpp:1197: const Node*
endRootContainer = range.endPosition().computeContainerNode();
When start is null position, end must be null position too, as of ctor of
EphemeralRange.
So, this check could be:

if (range.isNull())
  return false;

https://codereview.chromium.org/1409073004/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/Editor.cpp:1218: if
(rangeBoundariesAreValid(resultRange))
Just return found range even if it is crossing shadow boundary.
Composed tree version can represent found text spans multiple trees.

According to
https://www.chromestatus.com/metrics/feature/popularity#WindowFindWithShadowTree
we can switch window.find() to composed tree version or drop shadow tree support
in DOM version.

[commit-bot: I haz the power, 2015-11-04 07:20:32]

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

[commit-bot: I haz the power, 2015-11-04 07:20:34]

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

[Andrey Kraynov, 2015-11-04 11:42:54]

On 2015/11/04 07:11:06, Yosi_OOO_til_Oct_30 wrote:
> Let's use two |Range| object for representing active match and having position
> in composed tree version
> of DocumentMarkerController::addTextMatchMarker(), removeMarkers(), and
> setMarkesActive(), which traverse composed tree and map them to DOM tree
> positions. This doesn't need to generic, since document markers are
> associated to |Text| node.
> 
> If we choose this way, we don't need to solve  shadow boundary crossing
problem.

OK, I will continue working on this.
Thanks for you help with that CL!