Refactor DocumentMarkerController

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

Index: third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
diff --git a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
index dc1e08194faa0e5e3de94bdb46020662681f6b2d..c4f423a478cd53d2bdaf3c5d67f4fd470867b882 100644
--- a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
@@ -28,15 +28,20 @@
 
 #include "core/editing/markers/DocumentMarkerController.h"
 
+#include <algorithm>
 #include "core/dom/Node.h"
 #include "core/dom/NodeTraversal.h"
 #include "core/dom/Range.h"
 #include "core/dom/Text.h"
 #include "core/editing/iterators/TextIterator.h"
-#include "core/editing/markers/RenderedDocumentMarker.h"
+#include "core/editing/markers/CompositionMarkerList.h"
+#include "core/editing/markers/DocumentMarkerList.h"
+#include "core/editing/markers/GrammarMarkerList.h"
+#include "core/editing/markers/RenderedTextMatchMarker.h"
+#include "core/editing/markers/SpellingMarkerList.h"
+#include "core/editing/markers/TextMatchMarkerList.h"
 #include "core/frame/FrameView.h"
 #include "core/layout/LayoutObject.h"
-#include <algorithm>
 
 #ifndef NDEBUG
 #include <stdio.h>
@@ -47,49 +52,16 @@ namespace blink {
 MarkerRemoverPredicate::MarkerRemoverPredicate(const Vector<String>& words)
     : m_words(words) {}
 
-bool MarkerRemoverPredicate::operator()(const DocumentMarker& documentMarker,
-                                        const Text& textNode) const {
-  unsigned start = documentMarker.startOffset();
-  unsigned length = documentMarker.endOffset() - documentMarker.startOffset();
-
-  String markerText = textNode.data().substring(start, length);
-  return m_words.contains(markerText);
-}
-
-namespace {
-
-DocumentMarker::MarkerTypeIndex MarkerTypeToMarkerIndex(
-    DocumentMarker::MarkerType type) {
-  switch (type) {
-    case DocumentMarker::Spelling:
-      return DocumentMarker::SpellingMarkerIndex;
-    case DocumentMarker::Grammar:
-      return DocumentMarker::GrammarMarkerIndex;
-    case DocumentMarker::TextMatch:
-      return DocumentMarker::TextMatchMarkerIndex;
-    case DocumentMarker::Composition:
-      return DocumentMarker::CompositionMarkerIndex;
-  }
-
-  NOTREACHED();
-  return DocumentMarker::SpellingMarkerIndex;
-}
-
-}  // namespace
-
-inline bool DocumentMarkerController::possiblyHasMarkers(
-    DocumentMarker::MarkerTypes types) {
-  return m_possiblyExistingMarkerTypes.intersects(types);
-}
-
 DocumentMarkerController::DocumentMarkerController(Document& document)
-    : m_possiblyExistingMarkerTypes(0), m_document(&document) {
+    : m_document(&document) {
   setContext(&document);
 }
 
 void DocumentMarkerController::clear() {
-  m_markers.clear();
-  m_possiblyExistingMarkerTypes = 0;
+  m_spelling.clear();
+  m_grammar.clear();
+  m_textMatches.clear();
+  m_compositions.clear();
 }
 
 void DocumentMarkerController::addMarker(const Position& start,
@@ -100,10 +72,10 @@ void DocumentMarkerController::addMarker(const Position& start,
   // covers.
   for (TextIterator markedText(start, end); !markedText.atEnd();
        markedText.advance()) {
-    addMarker(
-        markedText.currentContainer(),
-        DocumentMarker(type, markedText.startOffsetInCurrentContainer(),
-                       markedText.endOffsetInCurrentContainer(), description));
+    addMarker(markedText.currentContainer(),
+              new DocumentMarker(
+                  type, markedText.startOffsetInCurrentContainer(),
+                  markedText.endOffsetInCurrentContainer(), description));
   }
 }
 
@@ -114,11 +86,12 @@ void DocumentMarkerController::addTextMatchMarker(const EphemeralRange& range,
   // Use a TextIterator to visit the potentially multiple nodes the range
   // covers.
   for (TextIterator markedText(range.startPosition(), range.endPosition());
-       !markedText.atEnd(); markedText.advance())
-    addMarker(
-        markedText.currentContainer(),
-        DocumentMarker(markedText.startOffsetInCurrentContainer(),
-                       markedText.endOffsetInCurrentContainer(), activeMatch));
+       !markedText.atEnd(); markedText.advance()) {
+    addMarker(markedText.currentContainer(),
+              new DocumentMarker(markedText.startOffsetInCurrentContainer(),
+                                 markedText.endOffsetInCurrentContainer(),
+                                 activeMatch));
+  }
   // Don't invalidate tickmarks here. TextFinder invalidates tickmarks using a
   // throttling algorithm. crbug.com/6819.
 }
@@ -131,11 +104,12 @@ void DocumentMarkerController::addCompositionMarker(const Position& start,
   DCHECK(!m_document->needsLayoutTreeUpdate());
 
   for (TextIterator markedText(start, end); !markedText.atEnd();
-       markedText.advance())
+       markedText.advance()) {
     addMarker(markedText.currentContainer(),
-              DocumentMarker(markedText.startOffsetInCurrentContainer(),
-                             markedText.endOffsetInCurrentContainer(),
-                             underlineColor, thick, backgroundColor));
+              new DocumentMarker(markedText.startOffsetInCurrentContainer(),
+                                 markedText.endOffsetInCurrentContainer(),
+                                 underlineColor, thick, backgroundColor));
+  }
 }
 
 void DocumentMarkerController::prepareForDestruction() {
@@ -143,24 +117,6 @@ void DocumentMarkerController::prepareForDestruction() {
 }
 
 void DocumentMarkerController::removeMarkers(
-    TextIterator& markedText,
-    DocumentMarker::MarkerTypes markerTypes,
-    RemovePartiallyOverlappingMarkerOrNot
-        shouldRemovePartiallyOverlappingMarker) {
-  for (; !markedText.atEnd(); markedText.advance()) {
-    if (!possiblyHasMarkers(markerTypes))
-      return;
-    DCHECK(!m_markers.isEmpty());
-
-    int startOffset = markedText.startOffsetInCurrentContainer();
-    int endOffset = markedText.endOffsetInCurrentContainer();
-    removeMarkers(markedText.currentContainer(), startOffset,
-                  endOffset - startOffset, markerTypes,
-                  shouldRemovePartiallyOverlappingMarker);
-  }
-}
-
-void DocumentMarkerController::removeMarkers(
     const EphemeralRange& range,
     DocumentMarker::MarkerTypes markerTypes,
     RemovePartiallyOverlappingMarkerOrNot
@@ -172,33 +128,13 @@ void DocumentMarkerController::removeMarkers(
       markedText, markerTypes, shouldRemovePartiallyOverlappingMarker);
 }
 
-static bool startsFurther(const Member<RenderedDocumentMarker>& lhv,
-                          const DocumentMarker* rhv) {
-  return lhv->startOffset() < rhv->startOffset();
-}
-
-static bool endsBefore(size_t startOffset,
-                       const Member<RenderedDocumentMarker>& rhv) {
-  return startOffset < rhv->endOffset();
-}
-
 static bool compareByStart(const Member<DocumentMarker>& lhv,
                            const Member<DocumentMarker>& rhv) {
   return lhv->startOffset() < rhv->startOffset();
 }
 
-static bool doesNotOverlap(const Member<RenderedDocumentMarker>& lhv,
-                           const DocumentMarker* rhv) {
-  return lhv->endOffset() < rhv->startOffset();
-}
-
-static bool doesNotInclude(const Member<RenderedDocumentMarker>& marker,
-                           size_t startOffset) {
-  return marker->endOffset() < startOffset;
-}
-
-static void updateMarkerRenderedRect(const Node& node,
-                                     RenderedDocumentMarker& marker) {
+static void updateTextMatchMarkerRenderedRect(const Node& node,
+                                              RenderedTextMatchMarker& marker) {
   Range* range = Range::create(node.document());
   // The offsets of the marker may be out-dated, so check for exceptions.
   DummyExceptionStateForTesting exceptionState;
@@ -218,43 +154,48 @@ static void updateMarkerRenderedRect(const Node& node,
   range->dispose();
 }
 
-// Markers are stored in order sorted by their start offset.
-// Markers of the same type do not overlap each other.
-
 void DocumentMarkerController::addMarker(Node* node,
-                                         const DocumentMarker& newMarker) {
-  DCHECK_GE(newMarker.endOffset(), newMarker.startOffset());
-  if (newMarker.endOffset() == newMarker.startOffset())
+                                         DocumentMarker* newMarker) {
+  DCHECK_GE(newMarker->endOffset(), newMarker->startOffset());
+  if (newMarker->endOffset() == newMarker->startOffset())
     return;
 
-  m_possiblyExistingMarkerTypes.add(newMarker.type());
-
-  Member<MarkerLists>& markers =
-      m_markers.insert(node, nullptr).storedValue->value;
-  if (!markers) {
-    markers = new MarkerLists;
-    markers->grow(DocumentMarker::MarkerTypeIndexesCount);
-  }
-
-  DocumentMarker::MarkerTypeIndex markerListIndex =
-      MarkerTypeToMarkerIndex(newMarker.type());
-  if (!markers->at(markerListIndex)) {
-    markers->at(markerListIndex) = new MarkerList;
-  }
-
-  Member<MarkerList>& list = markers->at(markerListIndex);
-  RenderedDocumentMarker* newRenderedMarker =
-      RenderedDocumentMarker::create(newMarker);
-  if (list->isEmpty() || list->back()->endOffset() < newMarker.startOffset()) {
-    list->push_back(newRenderedMarker);
-  } else {
-    if (newMarker.type() != DocumentMarker::TextMatch &&
-        newMarker.type() != DocumentMarker::Composition) {
-      mergeOverlapping(list.get(), newRenderedMarker);
-    } else {
-      MarkerList::iterator pos = std::lower_bound(list->begin(), list->end(),
-                                                  &newMarker, startsFurther);
-      list->insert(pos - list->begin(), newRenderedMarker);
+  switch (newMarker->type()) {
+    case DocumentMarker::Spelling: {
+      auto it = m_spelling.find(node);
+      if (it == m_spelling.end()) {
+        m_spelling.insert(node, new SpellingMarkerList(this));
+        it = m_spelling.find(node);
+      }
+      it->value->insert(newMarker);
+      break;
+    }
+    case DocumentMarker::Grammar: {
+      auto it = m_grammar.find(node);
+      if (it == m_grammar.end()) {
+        m_grammar.insert(node, new GrammarMarkerList(this));
+        it = m_grammar.find(node);
+      }
+      it->value->insert(newMarker);
+      break;
+    }
+    case DocumentMarker::TextMatch: {
+      auto it = m_textMatches.find(node);
+      if (it == m_textMatches.end()) {
+        m_textMatches.insert(node, new TextMatchMarkerList(this));
+        it = m_textMatches.find(node);
+      }
+      it->value->push_back(static_cast<TextMatchMarker*>(newMarker));
+      break;
+    }
+    case DocumentMarker::Composition: {
+      auto it = m_compositions.find(node);
+      if (it == m_compositions.end()) {
+        m_compositions.insert(node, new CompositionMarkerList(this));
+        it = m_compositions.find(node);
+      }
+      it->value->insert(newMarker);
+      break;
     }
   }
 
@@ -265,25 +206,6 @@ void DocumentMarkerController::addMarker(Node* node,
   }
 }
 
-void DocumentMarkerController::mergeOverlapping(
-    MarkerList* list,
-    RenderedDocumentMarker* toInsert) {
-  MarkerList::iterator firstOverlapping =
-      std::lower_bound(list->begin(), list->end(), toInsert, doesNotOverlap);
-  size_t index = firstOverlapping - list->begin();
-  list->insert(index, toInsert);
-  MarkerList::iterator inserted = list->begin() + index;
-  firstOverlapping = inserted + 1;
-  for (MarkerList::iterator i = firstOverlapping;
-       i != list->end() && (*i)->startOffset() <= (*inserted)->endOffset();) {
-    (*inserted)->setStartOffset(
-        std::min((*inserted)->startOffset(), (*i)->startOffset()));
-    (*inserted)->setEndOffset(
-        std::max((*inserted)->endOffset(), (*i)->endOffset()));
-    list->remove(i - list->begin());
-  }
-}
-
 // copies markers from srcNode to dstNode, applying the specified shift delta to
 // the copies. The shift is useful if, e.g., the caller has created the dstNode
 // from a non-prefix substring of the srcNode.
@@ -295,39 +217,11 @@ void DocumentMarkerController::copyMarkers(Node* srcNode,
   if (length <= 0)
     return;
 
-  if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  MarkerLists* markers = m_markers.at(srcNode);
-  if (!markers)
-    return;
-
   bool docDirty = false;
-  for (Member<MarkerList> list : *markers) {
-    if (!list)
-      continue;
 
-    unsigned endOffset = startOffset + length - 1;
-    MarkerList::iterator startPos = std::lower_bound(
-        list->begin(), list->end(), startOffset, doesNotInclude);
-    for (MarkerList::iterator i = startPos; i != list->end(); ++i) {
-      DocumentMarker* marker = i->get();
-
-      // stop if we are now past the specified range
-      if (marker->startOffset() > endOffset)
-        break;
-
-      // pin the marker to the specified range and apply the shift delta
-      docDirty = true;
-      if (marker->startOffset() < startOffset)
-        marker->setStartOffset(startOffset);
-      if (marker->endOffset() > endOffset)
-        marker->setEndOffset(endOffset);
-      marker->shiftOffsets(delta);
-
-      addMarker(dstNode, *marker);
-    }
+  for (Member<DocumentMarkerList> list : getMarkerListsForNode(srcNode)) {
+    docDirty =
+        list->copyMarkers(startOffset, length, dstNode, delta) || docDirty;
   }
 
   // repaint the affected node
@@ -347,79 +241,49 @@ void DocumentMarkerController::removeMarkers(
   if (length <= 0)
     return;
 
-  if (!possiblyHasMarkers(markerTypes))
-    return;
-  DCHECK(!(m_markers.isEmpty()));
-
-  MarkerLists* markers = m_markers.at(node);
-  if (!markers)
-    return;
-
   bool docDirty = false;
-  size_t emptyListsCount = 0;
-  for (size_t markerListIndex = 0;
-       markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-       ++markerListIndex) {
-    Member<MarkerList>& list = (*markers)[markerListIndex];
-    if (!list || list->isEmpty()) {
-      if (list.get() && list->isEmpty())
-        list.clear();
-      ++emptyListsCount;
-      continue;
+  if (markerTypes.contains(DocumentMarker::Spelling)) {
+    auto it = m_spelling.find(node);
+    if (it != m_spelling.end()) {
+      it->value->removeMarkers(startOffset, length,
+                               shouldRemovePartiallyOverlappingMarker,
+                               &docDirty);
+      if (it->value->empty())
+        m_spelling.remove(node);
     }
-    if (!markerTypes.contains((*list->begin())->type()))
-      continue;
-    unsigned endOffset = startOffset + length;
-    MarkerList::iterator startPos =
-        std::upper_bound(list->begin(), list->end(), startOffset, endsBefore);
-    for (MarkerList::iterator i = startPos; i != list->end();) {
-      DocumentMarker marker(*i->get());
-
-      // markers are returned in order, so stop if we are now past the specified
-      // range
-      if (marker.startOffset() >= endOffset)
-        break;
-
-      // at this point we know that marker and target intersect in some way
-      docDirty = true;
-
-      // pitch the old marker
-      list->remove(i - list->begin());
-
-      if (shouldRemovePartiallyOverlappingMarker) {
-        // Stop here. Don't add resulting slices back.
-        continue;
-      }
+  }
 
-      // add either of the resulting slices that are left after removing target
-      if (startOffset > marker.startOffset()) {
-        DocumentMarker newLeft = marker;
-        newLeft.setEndOffset(startOffset);
-        size_t insertIndex = i - list->begin();
-        list->insert(insertIndex, RenderedDocumentMarker::create(newLeft));
-        // Move to the marker after the inserted one.
-        i = list->begin() + insertIndex + 1;
-      }
-      if (marker.endOffset() > endOffset) {
-        DocumentMarker newRight = marker;
-        newRight.setStartOffset(endOffset);
-        size_t insertIndex = i - list->begin();
-        list->insert(insertIndex, RenderedDocumentMarker::create(newRight));
-        // Move to the marker after the inserted one.
-        i = list->begin() + insertIndex + 1;
-      }
+  if (markerTypes.contains(DocumentMarker::Grammar)) {
+    auto it = m_grammar.find(node);
+    if (it != m_grammar.end()) {
+      it->value->removeMarkers(startOffset, length,
+                               shouldRemovePartiallyOverlappingMarker,
+                               &docDirty);
+      if (it->value->empty())
+        m_grammar.remove(node);
     }
+  }
 
-    if (list->isEmpty()) {
-      list.clear();
-      ++emptyListsCount;
+  if (markerTypes.contains(DocumentMarker::TextMatch)) {
+    auto it = m_textMatches.find(node);
+    if (it != m_textMatches.end()) {
+      it->value->removeMarkers(startOffset, length,
+                               shouldRemovePartiallyOverlappingMarker,
+                               &docDirty);
+      if (it->value->empty())
+        m_textMatches.remove(node);
     }
   }
 
-  if (emptyListsCount == DocumentMarker::MarkerTypeIndexesCount) {
-    m_markers.erase(node);
-    if (m_markers.isEmpty())
-      m_possiblyExistingMarkerTypes = 0;
+  if (markerTypes.contains(DocumentMarker::Composition)) {
+    auto it = m_compositions.find(node);
+    if (it != m_compositions.end()) {
+      it->value->removeMarkers(startOffset, length,
+                               shouldRemovePartiallyOverlappingMarker,
+                               &docDirty);
+      if (it->value->empty())
+        m_compositions.remove(node);
+    }
   }
 
   // repaint the affected node
@@ -434,20 +298,9 @@ DocumentMarkerVector DocumentMarkerController::markersFor(
     DocumentMarker::MarkerTypes markerTypes) {
   DocumentMarkerVector result;
 
-  MarkerLists* markers = m_markers.at(node);
-  if (!markers)
-    return result;
-
-  for (size_t markerListIndex = 0;
-       markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-       ++markerListIndex) {
-    Member<MarkerList>& list = (*markers)[markerListIndex];
-    if (!list || list->isEmpty() ||
-        !markerTypes.contains((*list->begin())->type()))
-      continue;
-
-    for (size_t i = 0; i < list->size(); ++i)
-      result.push_back(list->at(i).get());
+  for (Member<DocumentMarkerList> list :
+       getMarkerListsForNode(node, markerTypes)) {
+    list->appendMarkersToInputList(&result);
   }
 
   std::sort(result.begin(), result.end(), compareByStart);
@@ -456,16 +309,18 @@ DocumentMarkerVector DocumentMarkerController::markersFor(
 
 DocumentMarkerVector DocumentMarkerController::markers() {
   DocumentMarkerVector result;
-  for (MarkerMap::iterator i = m_markers.begin(); i != m_markers.end(); ++i) {
-    MarkerLists* markers = i->value.get();
-    for (size_t markerListIndex = 0;
-         markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-         ++markerListIndex) {
-      Member<MarkerList>& list = (*markers)[markerListIndex];
-      for (size_t j = 0; list.get() && j < list->size(); ++j)
-        result.push_back(list->at(j).get());
-    }
-  }
+  for (auto it = m_spelling.begin(); it != m_spelling.end(); ++it)
+    it->value->appendMarkersToInputList(&result);
+
+  for (auto it = m_grammar.begin(); it != m_grammar.end(); ++it)
+    it->value->appendMarkersToInputList(&result);
+
+  for (auto it = m_textMatches.begin(); it != m_textMatches.end(); ++it)
+    it->value->appendMarkersToInputList(&result);
+
+  for (auto it = m_compositions.begin(); it != m_compositions.end(); ++it)
+    it->value->appendMarkersToInputList(&result);
+
   std::sort(result.begin(), result.end(), compareByStart);
   return result;
 }
@@ -473,8 +328,6 @@ DocumentMarkerVector DocumentMarkerController::markers() {
 DocumentMarkerVector DocumentMarkerController::markersInRange(
     const EphemeralRange& range,
     DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return DocumentMarkerVector();
 
   DocumentMarkerVector foundMarkers;
 
@@ -501,35 +354,21 @@ DocumentMarkerVector DocumentMarkerController::markersInRange(
   return foundMarkers;
 }
 
-Vector<IntRect> DocumentMarkerController::renderedRectsForMarkers(
-    DocumentMarker::MarkerType markerType) {
+Vector<IntRect> DocumentMarkerController::renderedRectsForMarkers() {
   Vector<IntRect> result;
 
-  if (!possiblyHasMarkers(markerType))
-    return result;
-  DCHECK(!(m_markers.isEmpty()));
-
   // outer loop: process each node
-  MarkerMap::iterator end = m_markers.end();
-  for (MarkerMap::iterator nodeIterator = m_markers.begin();
-       nodeIterator != end; ++nodeIterator) {
+  for (auto nodeIterator = m_textMatches.begin();
+       nodeIterator != m_textMatches.end(); ++nodeIterator) {
     // inner loop; process each marker in this node
     const Node& node = *nodeIterator->key;
-    MarkerLists* markers = nodeIterator->value.get();
-    for (size_t markerListIndex = 0;
-         markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-         ++markerListIndex) {
-      Member<MarkerList>& list = (*markers)[markerListIndex];
-      if (!list || list->isEmpty() || (*list->begin())->type() != markerType)
+    TextMatchMarkerList* list = nodeIterator->value.get();
+    for (unsigned markerIndex = 0; markerIndex < list->size(); ++markerIndex) {
+      RenderedTextMatchMarker* marker = list->at(markerIndex);
+      updateTextMatchMarkerRenderedRectIfNeeded(node, *marker);
+      if (!marker->isRendered())
         continue;
-      for (unsigned markerIndex = 0; markerIndex < list->size();
-           ++markerIndex) {
-        RenderedDocumentMarker* marker = list->at(markerIndex).get();
-        updateMarkerRenderedRectIfNeeded(node, *marker);
-        if (!marker->isRendered())
-          continue;
-        result.push_back(marker->renderedRect());
-      }
+      result.push_back(marker->renderedRect());
     }
   }
 
@@ -541,49 +380,40 @@ static void invalidatePaintForTickmarks(const Node& node) {
     frameView->invalidatePaintForTickmarks();
 }
 
-void DocumentMarkerController::updateMarkerRenderedRectIfNeeded(
+void DocumentMarkerController::updateTextMatchMarkerRenderedRectIfNeeded(
     const Node& node,
-    RenderedDocumentMarker& marker) {
+    RenderedTextMatchMarker& marker) {
   DCHECK(!m_document->view() || !m_document->view()->needsLayout());
   DCHECK(!m_document->needsLayoutTreeUpdate());
   if (!marker.isValid())
-    updateMarkerRenderedRect(node, marker);
+    updateTextMatchMarkerRenderedRect(node, marker);
 }
 
-void DocumentMarkerController::invalidateRectsForMarkersInNode(
-    const Node& node) {
-  MarkerLists* markers = m_markers.at(&node);
-
-  for (auto& markerList : *markers) {
-    if (!markerList || markerList->isEmpty())
-      continue;
+void DocumentMarkerController::invalidateRectsForMarkersInNode(Node& node) {
+  if (!m_textMatches.contains(&node))
+    return;
 
-    for (auto& marker : *markerList)
-      marker->invalidate();
+  TextMatchMarkerList& markerList = *(m_textMatches.find(&node)->value);
 
-    if (markerList->front()->type() == DocumentMarker::TextMatch)
-      invalidatePaintForTickmarks(node);
+  for (Member<DocumentMarker> marker : markerList) {
+    auto renderedTextMatchMarker =
+        static_cast<RenderedTextMatchMarker*>(marker.get());
+    renderedTextMatchMarker->invalidate();
   }
+
+  invalidatePaintForTickmarks(node);
 }
 
 void DocumentMarkerController::invalidateRectsForAllMarkers() {
-  for (auto& nodeMarkers : m_markers) {
-    const Node& node = *nodeMarkers.key;
-    for (auto& markerList : *nodeMarkers.value) {
-      if (!markerList || markerList->isEmpty())
-        continue;
-
-      for (auto& marker : *markerList)
-        marker->invalidate();
-
-      if (markerList->front()->type() == DocumentMarker::TextMatch)
-        invalidatePaintForTickmarks(node);
-    }
-  }
+  for (auto& nodeMarkers : m_textMatches)
+    invalidateRectsForMarkersInNode(*nodeMarkers.key);
 }
 
 DEFINE_TRACE(DocumentMarkerController) {
-  visitor->trace(m_markers);
+  visitor->trace(m_spelling);
+  visitor->trace(m_grammar);
+  visitor->trace(m_textMatches);
+  visitor->trace(m_compositions);
   visitor->trace(m_document);
   SynchronousMutationObserver::trace(visitor);
 }
@@ -591,150 +421,80 @@ DEFINE_TRACE(DocumentMarkerController) {
 void DocumentMarkerController::removeMarkers(
     Node* node,
     DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return;
-  DCHECK(!m_markers.isEmpty());
+  if (markerTypes.contains(DocumentMarker::Spelling))
+    m_spelling.remove(node);
+
+  if (markerTypes.contains(DocumentMarker::Grammar))
+    m_grammar.remove(node);
+
+  if (markerTypes.contains(DocumentMarker::TextMatch))
+    m_textMatches.remove(node);
+
+  if (markerTypes.contains(DocumentMarker::Composition))
+    m_compositions.remove(node);
+}
+
+void DocumentMarkerController::removeMarkers(
+    DocumentMarker::MarkerTypes markerTypes) {
+  if (markerTypes.contains(DocumentMarker::Spelling))
+    m_spelling.clear();
 
-  MarkerMap::iterator iterator = m_markers.find(node);
-  if (iterator != m_markers.end())
-    removeMarkersFromList(iterator, markerTypes);
+  if (markerTypes.contains(DocumentMarker::Grammar))
+    m_grammar.clear();
+
+  if (markerTypes.contains(DocumentMarker::TextMatch))
+    m_textMatches.clear();
+
+  if (markerTypes.contains(DocumentMarker::Composition))
+    m_compositions.clear();
 }
 
 void DocumentMarkerController::removeMarkers(
     const MarkerRemoverPredicate& shouldRemoveMarker) {
-  for (auto& nodeMarkers : m_markers) {
+  for (auto& nodeMarkers : m_spelling) {
     const Node& node = *nodeMarkers.key;
-    if (!node.isTextNode())  // MarkerRemoverPredicate requires a Text node.
+    if (!node.isTextNode())
       continue;
-    MarkerLists& markers = *nodeMarkers.value;
-    for (size_t markerListIndex = 0;
-         markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-         ++markerListIndex) {
-      Member<MarkerList>& list = markers[markerListIndex];
-      if (!list)
-        continue;
-      bool removedMarkers = false;
-      for (size_t j = list->size(); j > 0; --j) {
-        if (shouldRemoveMarker(*list->at(j - 1),
-                               static_cast<const Text&>(node))) {
-          list->remove(j - 1);
-          removedMarkers = true;
-        }
-      }
-      if (removedMarkers &&
-          markerListIndex == DocumentMarker::TextMatchMarkerIndex)
-        invalidatePaintForTickmarks(node);
-    }
+    nodeMarkers.value->removeMarkersForWords(static_cast<const Text&>(node),
+                                             shouldRemoveMarker.m_words);
   }
 }
 
-void DocumentMarkerController::removeMarkers(
+void DocumentMarkerController::repaintMarkers(
     DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  HeapVector<Member<const Node>> nodesWithMarkers;
-  copyKeysToVector(m_markers, nodesWithMarkers);
-  unsigned size = nodesWithMarkers.size();
-  for (unsigned i = 0; i < size; ++i) {
-    MarkerMap::iterator iterator = m_markers.find(nodesWithMarkers[i]);
-    if (iterator != m_markers.end())
-      removeMarkersFromList(iterator, markerTypes);
+  HeapHashSet<Member<Node>> nodesToRepaint;
+  for (auto& nodeMarkers : m_spelling) {
+    if (!nodeMarkers.value->empty())
+      nodesToRepaint.insert(nodeMarkers.key.get());
   }
 
-  m_possiblyExistingMarkerTypes.remove(markerTypes);
-}
-
-void DocumentMarkerController::removeMarkersFromList(
-    MarkerMap::iterator iterator,
-    DocumentMarker::MarkerTypes markerTypes) {
-  bool needsRepainting = false;
-  bool nodeCanBeRemoved;
-
-  size_t emptyListsCount = 0;
-  if (markerTypes == DocumentMarker::AllMarkers()) {
-    needsRepainting = true;
-    nodeCanBeRemoved = true;
-  } else {
-    MarkerLists* markers = iterator->value.get();
-
-    for (size_t markerListIndex = 0;
-         markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-         ++markerListIndex) {
-      Member<MarkerList>& list = (*markers)[markerListIndex];
-      if (!list || list->isEmpty()) {
-        if (list.get() && list->isEmpty())
-          list.clear();
-        ++emptyListsCount;
-        continue;
-      }
-      if (markerTypes.contains((*list->begin())->type())) {
-        list->clear();
-        list.clear();
-        ++emptyListsCount;
-        needsRepainting = true;
-      }
-    }
-
-    nodeCanBeRemoved =
-        emptyListsCount == DocumentMarker::MarkerTypeIndexesCount;
+  for (auto& nodeMarkers : m_grammar) {
+    if (!nodeMarkers.value->empty())
+      nodesToRepaint.insert(nodeMarkers.key.get());
   }
 
-  if (needsRepainting) {
-    const Node& node = *iterator->key;
-    if (LayoutObject* layoutObject = node.layoutObject()) {
-      layoutObject->setShouldDoFullPaintInvalidation(
-          PaintInvalidationDocumentMarkerChange);
-    }
-    invalidatePaintForTickmarks(node);
+  for (auto& nodeMarkers : m_textMatches) {
+    if (!nodeMarkers.value->empty())
+      nodesToRepaint.insert(nodeMarkers.key.get());
   }
 
-  if (nodeCanBeRemoved) {
-    m_markers.remove(iterator);
-    if (m_markers.isEmpty())
-      m_possiblyExistingMarkerTypes = 0;
+  for (auto& nodeMarkers : m_compositions) {
+    if (!nodeMarkers.value->empty())
+      nodesToRepaint.insert(nodeMarkers.key.get());
   }
-}
-
-void DocumentMarkerController::repaintMarkers(
-    DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  // outer loop: process each markered node in the document
-  MarkerMap::iterator end = m_markers.end();
-  for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
-    const Node* node = i->key;
-
-    // inner loop: process each marker in the current node
-    MarkerLists* markers = i->value.get();
-    for (size_t markerListIndex = 0;
-         markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-         ++markerListIndex) {
-      Member<MarkerList>& list = (*markers)[markerListIndex];
-      if (!list || list->isEmpty() ||
-          !markerTypes.contains((*list->begin())->type()))
-        continue;
 
-      // cause the node to be redrawn
-      if (LayoutObject* layoutObject = node->layoutObject()) {
-        layoutObject->setShouldDoFullPaintInvalidation(
-            PaintInvalidationDocumentMarkerChange);
-        break;
-      }
+  for (Member<Node> node : nodesToRepaint) {
+    // cause the node to be redrawn
+    if (LayoutObject* layoutObject = node->layoutObject()) {
+      layoutObject->setShouldDoFullPaintInvalidation(
+          PaintInvalidationDocumentMarkerChange);
+      break;
     }
   }
 }
 
 bool DocumentMarkerController::setMarkersActive(const EphemeralRange& range,
                                                 bool active) {
-  if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
-    return false;
-
-  DCHECK(!m_markers.isEmpty());
-
   Node* const startContainer = range.startPosition().computeContainerNode();
   DCHECK(startContainer);
   Node* const endContainer = range.endPosition().computeContainerNode();
@@ -754,147 +514,188 @@ bool DocumentMarkerController::setMarkersActive(const EphemeralRange& range,
   return markerFound;
 }
 
+bool DocumentMarkerController::hasMarkers(Node* node) const {
+  return m_spelling.contains(node) || m_grammar.contains(node) ||
+         m_textMatches.contains(node) || m_compositions.contains(node);
+}
+
 bool DocumentMarkerController::setMarkersActive(Node* node,
                                                 unsigned startOffset,
                                                 unsigned endOffset,
                                                 bool active) {
-  MarkerLists* markers = m_markers.at(node);
-  if (!markers)
-    return false;
-
   bool docDirty = false;
-  Member<MarkerList>& list =
-      (*markers)[MarkerTypeToMarkerIndex(DocumentMarker::TextMatch)];
-  if (!list)
-    return false;
-  MarkerList::iterator startPos =
-      std::upper_bound(list->begin(), list->end(), startOffset, endsBefore);
-  for (MarkerList::iterator marker = startPos; marker != list->end();
-       ++marker) {
-    // Markers are returned in order, so stop if we are now past the specified
-    // range.
-    if ((*marker)->startOffset() >= endOffset)
-      break;
-
-    (*marker)->setActiveMatch(active);
-    docDirty = true;
+  if (m_textMatches.contains(node)) {
+    docDirty = m_textMatches.at(node)->setTextMatchMarkersActive(
+        startOffset, endOffset, active);
   }
 
-  // repaint the affected node
-  if (docDirty && node->layoutObject()) {
+  if (docDirty && node->layoutObject())
     node->layoutObject()->setShouldDoFullPaintInvalidation(
         PaintInvalidationDocumentMarkerChange);
-  }
+
   return docDirty;
 }
 
 #ifndef NDEBUG
+static String showMarkerHelper(const DocumentMarkerVector& markers) {
+  StringBuilder builder;
+
+  for (const Member<DocumentMarker> marker : markers) {
+    builder.append(" ");
+    builder.appendNumber(marker->type());
+    builder.append(":[");
+    builder.appendNumber(marker->startOffset());
+    builder.append(":");
+    builder.appendNumber(marker->endOffset());
+    builder.append("](");
+    builder.appendNumber(marker->activeMatch());
+    builder.append(")");
+  }
+
+  return builder.toString();
+}
+
 void DocumentMarkerController::showMarkers() const {
   StringBuilder builder;
-  MarkerMap::const_iterator end = m_markers.end();
-  for (MarkerMap::const_iterator nodeIterator = m_markers.begin();
-       nodeIterator != end; ++nodeIterator) {
-    const Node* node = nodeIterator->key;
+
+  HeapHashSet<Member<Node>> nodes;
+  for (const auto& nodeMarkers : m_spelling)
+    nodes.insert(nodeMarkers.key);
+  for (const auto& nodeMarkers : m_grammar)
+    nodes.insert(nodeMarkers.key);
+  for (const auto& nodeMarkers : m_textMatches)
+    nodes.insert(nodeMarkers.key);
+  for (const auto& nodeMarkers : m_compositions)
+    nodes.insert(nodeMarkers.key);
+
+  HeapHashSet<Member<const Node>> nodesWithMarkers;
+  for (Node* node : nodes) {
     builder.append(String::format("%p", node));
-    MarkerLists* markers = m_markers.at(node);
-    for (size_t markerListIndex = 0;
-         markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-         ++markerListIndex) {
-      Member<MarkerList>& list = (*markers)[markerListIndex];
-      for (unsigned markerIndex = 0; list.get() && markerIndex < list->size();
-           ++markerIndex) {
-        DocumentMarker* marker = list->at(markerIndex).get();
-        builder.append(" ");
-        builder.appendNumber(marker->type());
-        builder.append(":[");
-        builder.appendNumber(marker->startOffset());
-        builder.append(":");
-        builder.appendNumber(marker->endOffset());
-        builder.append("](");
-        builder.appendNumber(marker->activeMatch());
-        builder.append(")");
+
+    if (m_spelling.contains(node)) {
+      DocumentMarkerVector markers;
+      m_spelling.at(node)->appendMarkersToInputList(&markers);
+      if (!markers.isEmpty()) {
+        builder.append(showMarkerHelper(markers));
+        nodesWithMarkers.insert(node);
       }
     }
+
+    if (m_grammar.contains(node)) {
+      DocumentMarkerVector markers;
+      m_grammar.at(node)->appendMarkersToInputList(&markers);
+      if (!markers.isEmpty()) {
+        builder.append(showMarkerHelper(markers));
+        nodesWithMarkers.insert(node);
+      }
+    }
+
+    if (m_textMatches.contains(node)) {
+      DocumentMarkerVector markers;
+      m_textMatches.at(node)->appendMarkersToInputList(&markers);
+      if (!markers.isEmpty()) {
+        builder.append(showMarkerHelper(markers));
+        nodesWithMarkers.insert(node);
+      }
+    }
+
+    if (m_compositions.contains(node)) {
+      DocumentMarkerVector markers;
+      m_compositions.at(node)->appendMarkersToInputList(&markers);
+      if (!markers.isEmpty()) {
+        builder.append(showMarkerHelper(markers));
+        nodesWithMarkers.insert(node);
+      }
+    }
+
     builder.append("\n");
   }
-  LOG(INFO) << m_markers.size() << " nodes have markers:\n"
+  LOG(INFO) << nodesWithMarkers.size() << " nodes have markers:\n"
             << builder.toString().utf8().data();
 }
 #endif
 
+HeapVector<Member<DocumentMarkerList>>
+DocumentMarkerController::getMarkerListsForNode(
+    Node* node,
+    DocumentMarker::MarkerTypes markerTypes) {
+  HeapVector<Member<DocumentMarkerList>> markerLists;
+
+  if (markerTypes.contains(DocumentMarker::Spelling)) {
+    auto spellingIt = m_spelling.find(node);
+    if (spellingIt != m_spelling.end())
+      markerLists.push_back(spellingIt->value);
+  }
+
+  if (markerTypes.contains(DocumentMarker::Grammar)) {
+    auto grammarIt = m_grammar.find(node);
+    if (grammarIt != m_grammar.end())
+      markerLists.push_back(grammarIt->value);
+  }
+
+  if (markerTypes.contains(DocumentMarker::TextMatch)) {
+    auto textMatchesIt = m_textMatches.find(node);
+    if (textMatchesIt != m_textMatches.end())
+      markerLists.push_back(textMatchesIt->value);
+  }
+
+  if (markerTypes.contains(DocumentMarker::Composition)) {
+    auto compositionsIt = m_compositions.find(node);
+    if (compositionsIt != m_compositions.end())
+      markerLists.push_back(compositionsIt->value);
+  }
+
+  return markerLists;
+}
+
+void DocumentMarkerController::removeMarkers(
+    TextIterator& markedText,
+    DocumentMarker::MarkerTypes markerTypes,
+    RemovePartiallyOverlappingMarkerOrNot
+        shouldRemovePartiallyOverlappingMarker) {
+  for (; !markedText.atEnd(); markedText.advance()) {
+    int startOffset = markedText.startOffsetInCurrentContainer();
+    int endOffset = markedText.endOffsetInCurrentContainer();
+    removeMarkers(markedText.currentContainer(), startOffset,
+                  endOffset - startOffset, markerTypes,
+                  shouldRemovePartiallyOverlappingMarker);
+  }
+}
+
 // SynchronousMutationObserver
 void DocumentMarkerController::didUpdateCharacterData(CharacterData* node,
                                                       unsigned offset,
                                                       unsigned oldLength,
                                                       unsigned newLength) {
-  // If we're doing a pure remove operation, remove the markers in the range
-  // being removed (markers containing, but larger than, the range, will be
-  // split)
-  if (newLength == 0)
-    removeMarkers(node, offset, oldLength);
-
-  if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  MarkerLists* markers = m_markers.at(node);
-  if (!markers)
-    return;
-
   bool didShiftMarker = false;
-  for (MarkerList* list : *markers) {
-    if (!list)
-      continue;
+  for (auto& nodeMarkers : m_spelling) {
+    didShiftMarker = didShiftMarker || nodeMarkers.value->shiftMarkers(
+                                           offset, oldLength, newLength);
+  }
 
-    for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
-      RenderedDocumentMarker& marker = **it;
-      // algorithm inspired by https://dom.spec.whatwg.org/#concept-cd-replace
-      // but with some changes
-      if (marker.startOffset() > offset) {
-        // Deviation from the concept-cd-replace algorithm: < instead of <= in
-        // the next line
-        if (marker.startOffset() < offset + oldLength) {
-          // Marker start was in the replaced text. Move to end of new text
-          // (Deviation from the concept-cd-replace algorithm: that algorithm
-          // would move to the beginning of the new text here)
-          marker.setStartOffset(offset + newLength);
-        } else {
-          // Marker start was after the replaced text. Shift by length
-          // difference
-          unsigned oldStartOffset = marker.startOffset();
-          marker.setStartOffset(oldStartOffset + newLength - oldLength);
-        }
-        didShiftMarker = true;
-      }
+  for (auto& nodeMarkers : m_grammar) {
+    didShiftMarker = didShiftMarker || nodeMarkers.value->shiftMarkers(
+                                           offset, oldLength, newLength);
+  }
 
-      if (marker.endOffset() > offset) {
-        // Deviation from the concept-cd-replace algorithm: < instead of <= in
-        // the next line
-        if (marker.endOffset() < offset + oldLength) {
-          // Marker end was in the replaced text. Move to beginning of new text
-          marker.setEndOffset(offset);
-        } else {
-          // Marker end was after the replaced text. Shift by length difference
-          unsigned oldEndOffset = marker.endOffset();
-          marker.setEndOffset(oldEndOffset + newLength - oldLength);
-        }
-        didShiftMarker = true;
-      }
+  for (auto& nodeMarkers : m_textMatches) {
+    didShiftMarker = didShiftMarker || nodeMarkers.value->shiftMarkers(
+                                           offset, oldLength, newLength);
+  }
 
-      if (marker.startOffset() < marker.endOffset())
-        continue;
-      list->remove(it - list->begin());
-      --it;
-    }
+  for (auto& nodeMarkers : m_compositions) {
+    didShiftMarker = didShiftMarker || nodeMarkers.value->shiftMarkers(
+                                           offset, oldLength, newLength);
   }
 
-  if (!didShiftMarker)
-    return;
-  if (!node->layoutObject())
-    return;
-  invalidateRectsForMarkersInNode(*node);
-  // repaint the affected node
-  node->layoutObject()->setShouldDoFullPaintInvalidation();
+  if (didShiftMarker) {
+    invalidateRectsForMarkersInNode(*node);
+    // repaint the affected node
+    if (node->layoutObject()) {
+      node->layoutObject()->setShouldDoFullPaintInvalidation(
+          PaintInvalidationDocumentMarkerChange);
+    }
+  }
 }
 
 }  // namespace blink