Add SpellCheckMarkerList in preparation for DocumentMarkerController refactor

Add SpellCheckMarkerList in preparation for DocumentMarkerController refactor

Split off from https://codereview.chromium.org/2723663002

This CL depends on the CL that adds CompositionMarkerList:
https://codereview.chromium.org/2773883003

One important thing that makes SpellCheckMarkerList special is that it merges
markers with touching endpoints. I've added some test cases for this behavior
in SpellCheckMarkerListTest.cpp.

BUG=707867

[rlanday, 2017-03-25 00:12:06]

rlanday@chromium.org changed reviewers:
+ xiaochengh@chromium.org, yosin@chromium.org

[rlanday, 2017-03-25 00:12:06]

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

[rlanday, 2017-03-25 00:22:52]

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

[commit-bot: I haz the power, 2017-03-25 00:23:26]

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

[commit-bot: I haz the power, 2017-03-25 03:29:10]

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

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

Dry run: This issue passed the CQ dry run.

[Xiaocheng, 2017-03-25 18:55:53]

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
(right):

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:15:
static bool doesNotOverlap(const Member<DocumentMarker>& lhv,
The name doesn't match what it does. Btw, I just realized that the "endsBefore"
in DML.cpp also has a wrong name...

Maybe a better idea is to use lambda expressions?

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:28: void
SpellCheckMarkerList::push_back(DocumentMarker* marker) {
Hmm... We need to be more careful about the function names, because it's not
doing a push_back.

To avoid confusing names while keeping the interface compact, how about just
renaming the function as "add"?

Besides, please add a comment that this function merges the new marker with
existing overlapping ones.

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:44:
m_markers.remove(it - m_markers.begin());
This leads to quadratic running time. Could you reduce it to linear?

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:48: void
SpellCheckMarkerList::removeMarkersForWords(const Text& textNode,
Let's take a String parameter to remove the dependency on DOM objects.

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListTest.cpp
(right):

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListTest.cpp:84:
TEST_F(SpellCheckMarkerListTest, PushBackMerging) {
Could you split the test case into four independent ones?

Ideally, we would like to avoid dependency between test cases.

[rlanday, 2017-03-25 19:33:01]

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
(right):

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:44:
m_markers.remove(it - m_markers.begin());
On 2017/03/25 at 18:55:52, Xiaocheng wrote:
> This leads to quadratic running time. Could you reduce it to linear?

Ah, I did notice this can be improved, I must've been in a hurry to upload this
CL :)

[yosin_UTC9, 2017-03-27 05:02:51]

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h
(right):

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:14: class
CORE_EXPORT SpellCheckMarkerList : public EditingMarkerList {
nit: Please mark this class |final|

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:19:
DocumentMarker::MarkerType allowedMarkerType() const final;
nit: interface implementations should be in |private| section.

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:27:
DocumentMarker::MarkerType m_type;
nit: s/DocumentMarker::MarkerType/const DocumentMarker::MarkerType/

[rlanday, 2017-03-27 21:59:24]

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h
(right):

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:19:
DocumentMarker::MarkerType allowedMarkerType() const final;
On 2017/03/27 at 05:02:51, yosin_UTC9 wrote:
> nit: interface implementations should be in |private| section.

Sorry, I don't understand what you mean here; these methods are all public in
DocumentMarkerList and won't be callable on SpellCheckMarkerList if I make them
private here. E.g. SpellCheckMarkerList will get a compilation error trying to
call add().

[Xiaocheng, 2017-03-27 22:08:24]

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h
(right):

https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:19:
DocumentMarker::MarkerType allowedMarkerType() const final;
On 2017/03/27 at 21:59:24, rlanday wrote:
> On 2017/03/27 at 05:02:51, yosin_UTC9 wrote:
> > nit: interface implementations should be in |private| section.
> 
> Sorry, I don't understand what you mean here; these methods are all public in
DocumentMarkerList and won't be callable on SpellCheckMarkerList if I make them
private here. E.g. SpellCheckMarkerList will get a compilation error trying to
call add().

In most cases, subclasses put overridden functions in their private sections,
even though the superclass declares the function as public.

Just like what you did for SetCharacterDataCommand, where SCDC::doApply and
SCDC::doUnapply are private, though they override public EditCommand::doApply
and EditCommand::doUnapply.

[rlanday, 2017-03-27 22:14:26]

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

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

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

[rlanday, 2017-03-27 22:22:01]

On 2017/03/27 at 22:08:24, xiaochengh wrote:
>
https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
> File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h
(right):
> 
>
https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
> third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:19:
DocumentMarker::MarkerType allowedMarkerType() const final;
> On 2017/03/27 at 21:59:24, rlanday wrote:
> > On 2017/03/27 at 05:02:51, yosin_UTC9 wrote:
> > > nit: interface implementations should be in |private| section.
> > 
> > Sorry, I don't understand what you mean here; these methods are all public
in DocumentMarkerList and won't be callable on SpellCheckMarkerList if I make
them private here. E.g. SpellCheckMarkerList will get a compilation error trying
to call add().
> 
> In most cases, subclasses put overridden functions in their private sections,
even though the superclass declares the function as public.
> 
> Just like what you did for SetCharacterDataCommand, where SCDC::doApply and
SCDC::doUnapply are private, though they override public EditCommand::doApply
and EditCommand::doUnapply.

Sorry, I still don't understand. That doesn't seem like good design to me. As I
mentioned, SpellCheckMarkerListTest will not compile if I do this. I tried to
find a reference for this rule and I found this instead:
https://isocpp.org/wiki/faq/proper-inheritance#hiding-inherited-public

"Should I hide member functions that were public in my base class?  
Never, never, never do this. Never. Never!"

[commit-bot: I haz the power, 2017-03-27 22:48:54]

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

[commit-bot: I haz the power, 2017-03-27 22:48:55]

Dry run: Try jobs failed on following builders:
  android_arm64_dbg_recipe on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_arm6...)

[Xiaocheng, 2017-03-27 23:07:44]

On 2017/03/27 at 22:22:01, rlanday wrote:
> On 2017/03/27 at 22:08:24, xiaochengh wrote:
> >
https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
> > File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h
(right):
> > 
> >
https://codereview.chromium.org/2770413003/diff/20001/third_party/WebKit/Sour...
> > third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.h:19:
DocumentMarker::MarkerType allowedMarkerType() const final;
> > On 2017/03/27 at 21:59:24, rlanday wrote:
> > > On 2017/03/27 at 05:02:51, yosin_UTC9 wrote:
> > > > nit: interface implementations should be in |private| section.
> > > 
> > > Sorry, I don't understand what you mean here; these methods are all public
in DocumentMarkerList and won't be callable on SpellCheckMarkerList if I make
them private here. E.g. SpellCheckMarkerList will get a compilation error trying
to call add().
> > 
> > In most cases, subclasses put overridden functions in their private
sections, even though the superclass declares the function as public.
> > 
> > Just like what you did for SetCharacterDataCommand, where SCDC::doApply and
SCDC::doUnapply are private, though they override public EditCommand::doApply
and EditCommand::doUnapply.
> 
> Sorry, I still don't understand. That doesn't seem like good design to me. As
I mentioned, SpellCheckMarkerListTest will not compile if I do this. I tried to
find a reference for this rule and I found this instead:
> https://isocpp.org/wiki/faq/proper-inheritance#hiding-inherited-public
> 
> "Should I hide member functions that were public in my base class?  
> Never, never, never do this. Never. Never!"

Interesting.

There is at least one benefit of hiding member functions: clients are forced to
hold a reference to the base class, which reduces the exposure of the subclass.
It's helpful when the subclass is considered as an implementation detail that
shouldn't be exposed.

I actually see both patterns (hide / not hide) in Blink. Maybe we should
initiate a discussion thread at chromium-dev@?

Btw, to make SpellCheckMarkerListTest compile, just make it hold a Persist<DML>.

[rlanday, 2017-03-27 23:30:52]

On 2017/03/27 at 23:07:44, xiaochengh wrote:
> Btw, to make SpellCheckMarkerListTest compile, just make it hold a
Persist<DML>.

There's supposed to be a test for removeMarkersForWords() too though (it looks
like I accidentally deleted it), we can't call that method (at least not without
casting) if we use Persist<DML>...

[rlanday, 2017-03-28 17:31:53]

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

[commit-bot: I haz the power, 2017-03-28 17:32:35]

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

[commit-bot: I haz the power, 2017-03-28 17:54:52]

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

[commit-bot: I haz the power, 2017-03-28 17:54:53]

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

[rlanday, 2017-03-28 18:22:14]

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

[commit-bot: I haz the power, 2017-03-28 18:22:38]

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

[commit-bot: I haz the power, 2017-03-28 20:07:21]

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

[commit-bot: I haz the power, 2017-03-28 20:07:22]

Dry run: This issue passed the CQ dry run.

[rlanday, 2017-03-29 01:12:25]

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

[commit-bot: I haz the power, 2017-03-29 01:13:27]

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

[commit-bot: I haz the power, 2017-03-29 03:14:52]

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

[commit-bot: I haz the power, 2017-03-29 03:14:53]

Dry run: Try jobs failed on following builders:
  ios-simulator on master.tryserver.chromium.mac (JOB_TIMED_OUT, build hasn't
started yet, builder probably lacks capacity)

[rlanday, 2017-03-29 18:26:12]

I've added an optimization to SpellCheckMarkerList so add() can be done in
(amortized) O(1) time for a marker being added to the end of the list vs.
(amortized) O(log n) time (for doing std::lower_bound())

[rlanday, 2017-03-29 18:26:15]

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

[commit-bot: I haz the power, 2017-03-29 18:26:48]

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

[commit-bot: I haz the power, 2017-03-29 20:18:50]

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

[commit-bot: I haz the power, 2017-03-29 20:18:51]

Dry run: This issue passed the CQ dry run.

[Xiaocheng, 2017-03-29 20:24:21]

lgtm with a nit.

https://codereview.chromium.org/2770413003/diff/120001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListTest.cpp
(right):

https://codereview.chromium.org/2770413003/diff/120001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListTest.cpp:30:
std::unique_ptr<DummyPageHolder> m_dummyPageHolder;
nit: No need to set up page and document.

[rlanday, 2017-03-29 22:51:46]

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

[rlanday, 2017-03-29 22:51:54]

On 2017/03/29 at 20:24:21, xiaochengh wrote:
> lgtm with a nit.
> 
>
https://codereview.chromium.org/2770413003/diff/120001/third_party/WebKit/Sou...
> File
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListTest.cpp
(right):
> 
>
https://codereview.chromium.org/2770413003/diff/120001/third_party/WebKit/Sou...
>
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListTest.cpp:30:
std::unique_ptr<DummyPageHolder> m_dummyPageHolder;
> nit: No need to set up page and document.

Updated

[commit-bot: I haz the power, 2017-03-29 22:52:54]

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

[Xiaocheng, 2017-03-29 23:26:04]

Still lgtm.

[rlanday, 2017-03-30 00:41:40]

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

[commit-bot: I haz the power, 2017-03-30 00:42:46]

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-03-30 01:33:06]

https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
(right):

https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:23:
DCHECK(marker->type() == allowedMarkerType());
nit: Let's use DCHECK_EQ(). If we need to introduce printer, let's introduce
printer too for ease of debugging.

https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:32: auto
firstOverlappingIt = std::lower_bound(
nit: s/auto/const auto&/

https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:40: auto
insertedIt = m_markers.begin() + index;
nit: s/auto/const auto&/

https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:62: for
(Member<DocumentMarker> marker : m_markers) {
Can we use std::copy_if()[1]?

[1] http://en.cppreference.com/w/cpp/algorithm/copy

https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:65:
String markerText = nodeText.substring(start, length);
nit: s/String/const String&/

[commit-bot: I haz the power, 2017-03-30 02:44:59]

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

[commit-bot: I haz the power, 2017-03-30 02:45:00]

Dry run: Try jobs failed on following builders:
  ios-simulator on master.tryserver.chromium.mac (JOB_TIMED_OUT, build hasn't
started yet, builder probably lacks capacity)

[rlanday, 2017-03-30 03:28:00]

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

[rlanday, 2017-03-30 03:28:22]

On 2017/03/30 at 01:33:06, yosin wrote:
>
https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
> File third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
(right):
> 
>
https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
> third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:23:
DCHECK(marker->type() == allowedMarkerType());
> nit: Let's use DCHECK_EQ(). If we need to introduce printer, let's introduce
printer too for ease of debugging.
> 
>
https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
> third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:32:
auto firstOverlappingIt = std::lower_bound(
> nit: s/auto/const auto&/
> 
>
https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
> third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:40:
auto insertedIt = m_markers.begin() + index;
> nit: s/auto/const auto&/
> 
>
https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
> third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:62:
for (Member<DocumentMarker> marker : m_markers) {
> Can we use std::copy_if()[1]?
> 
> [1] http://en.cppreference.com/w/cpp/algorithm/copy
> 
>
https://codereview.chromium.org/2770413003/diff/150001/third_party/WebKit/Sou...
> third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp:65:
String markerText = nodeText.substring(start, length);
> nit: s/String/const String&/

Updated

[commit-bot: I haz the power, 2017-03-30 03:28:35]

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

[commit-bot: I haz the power, 2017-03-30 05:16:18]

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

[commit-bot: I haz the power, 2017-03-30 05:16:19]

Dry run: This issue passed the CQ dry run.

[rlanday, 2017-03-30 18:48:58]

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

[commit-bot: I haz the power, 2017-03-30 18:50:01]

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

[commit-bot: I haz the power, 2017-03-30 21:25:31]

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

[commit-bot: I haz the power, 2017-03-30 21:25:32]

Dry run: This issue passed the CQ dry run.

[rlanday, 2017-03-30 23:00:08]

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

[commit-bot: I haz the power, 2017-03-30 23:01: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-03-31 00:56:24]

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

[commit-bot: I haz the power, 2017-03-31 00:56:25]

Dry run: This issue passed the CQ dry run.

[rlanday, 2017-04-03 18:56:22]

Description was changed from

==========
Add SpellCheckMarkerList in preparation for DocumentMarkerController refactor

Split off from https://codereview.chromium.org/2723663002

This CL depends on the CL that adds CompositionMarkerList:
https://codereview.chromium.org/2773883003

One important thing that makes SpellCheckMarkerList special is that it merges
markers with touching endpoints. I've added some test cases for this behavior
in SpellCheckMarkerListTest.cpp.
==========

to

==========
Add SpellCheckMarkerList in preparation for DocumentMarkerController refactor

Split off from https://codereview.chromium.org/2723663002

This CL depends on the CL that adds CompositionMarkerList:
https://codereview.chromium.org/2773883003

One important thing that makes SpellCheckMarkerList special is that it merges
markers with touching endpoints. I've added some test cases for this behavior
in SpellCheckMarkerListTest.cpp.

BUG=707867
==========