Add SpellCheckMarkerList in preparation for DocumentMarkerController refactor

third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp

Index: third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
diff --git a/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp b/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..54bb777085f3dd583b7c65000a601f9bd816e439
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
@@ -0,0 +1,64 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "core/editing/markers/SpellCheckMarkerList.h"
+
+#include <algorithm>
+#include "core/dom/Text.h"
+
+namespace blink {
+
+SpellCheckMarkerList::SpellCheckMarkerList(DocumentMarker::MarkerType type)
+    : m_type(type) {}
+
+static bool doesNotOverlap(const Member<DocumentMarker>& lhv,

[Xiaocheng, 2017/03/25 18:55:52]

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?

+                           const DocumentMarker* rhv) {
+  return lhv->endOffset() < rhv->startOffset();
+}
+
+DocumentMarker::MarkerType SpellCheckMarkerList::allowedMarkerType() const {
+  return m_type;
+}
+
+bool SpellCheckMarkerList::isSpellCheckMarkerList() const {
+  return true;
+}
+
+void SpellCheckMarkerList::push_back(DocumentMarker* marker) {

[Xiaocheng, 2017/03/25 18:55:52]

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.

+  DCHECK(marker->type() == allowedMarkerType());
+  auto firstOverlappingIt = std::lower_bound(m_markers.begin(), m_markers.end(),
+                                             marker, doesNotOverlap);
+  size_t index = firstOverlappingIt - m_markers.begin();
+  m_markers.insert(index, marker);
+  auto insertedIt = m_markers.begin() + index;
+  for (auto it = insertedIt + 1;
+       it != m_markers.end() &&
+       (*it)->startOffset() <= (*insertedIt)->endOffset();) {
+    (*insertedIt)
+        ->setStartOffset(
+            std::min((*insertedIt)->startOffset(), (*it)->startOffset()));
+    (*insertedIt)
+        ->setEndOffset(
+            std::max((*insertedIt)->endOffset(), (*it)->endOffset()));
+    m_markers.remove(it - m_markers.begin());

[Xiaocheng, 2017/03/25 18:55:52]

This leads to quadratic running time. Could you reduce it to linear?

[rlanday, 2017/03/25 19:33:00]

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

+  }
+}
+
+void SpellCheckMarkerList::removeMarkersForWords(const Text& textNode,

[Xiaocheng, 2017/03/25 18:55:52]

Let's take a String parameter to remove the dependency on DOM objects.

+                                                 const Vector<String>& words) {
+  // Build a second vector and swap with m_markers to avoid O(n^2) performance
+  HeapVector<Member<DocumentMarker>> newMarkerList;
+
+  for (Member<DocumentMarker> marker : m_markers) {
+    unsigned start = marker->startOffset();
+    unsigned length = marker->endOffset() - marker->startOffset();
+    String markerText = textNode.data().substring(start, length);
+    if (!words.contains(markerText))
+      newMarkerList.push_back(marker);
+  }
+
+  std::swap(m_markers, newMarkerList);
+}
+
+}  // namespace blink