Refactor DocumentMarkerController

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

+// 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/SpellingMarkerList.h"
+
+#include <utility>
+#include "core/dom/Text.h"
+
+namespace blink {
+
+SpellingMarkerList::SpellingMarkerList(
+    DocumentMarkerController* documentMarkerController)
+    : EditingMarkerListThatMergesTouchingMarkers(documentMarkerController) {}
+
+DocumentMarker::MarkerType SpellingMarkerList::allowedMarkerType() const {
+  return DocumentMarker::Spelling;
+}
+
+void SpellingMarkerList::removeMarkersForWords(const Text& textNode,
+                                               const Vector<String>& words) {
+  // Build a second vector and swap with m_markers to avoid O(n^2) performance

[Xiaocheng, 2017/03/17 23:56:34]

This is still quadratic running time: O(m_markers.size() * words.size()).

Anyway, it doesn't seem to be a serious issue, and there's no easy way to get
rid of this nested loop. I guess there's no need to overkill it with
Aho-Corasick algorithm...

[rlanday, 2017/03/18 01:12:27]

It's linear in m_markers.size() and words.size(), quadratic if you increase them
together :)

Taking the substring might also be slow if the markers contain a lot of text...I
think we're at

O(# markers * (avg. length of marked text + words.size())) 

One easy optimization for the asymptotic complexity would be storing the list of
words in a hash set, I suspect the number of words is typically going to be
small here though (I think this is called when you add a word to the custom
dictionary) so I don't know if that would actually help or not.

[Xiaocheng, 2017/03/18 01:58:09]

Using anything more complicated than a simple nested loop might be an overkill
here, unless we have evidence this part is a performance bottleneck. However, we
don't have any evidence.

So forget it...

+  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