Refactor DocumentMarkerController

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

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  *           (C) 2006 Alexey Proskuryakov (ap@webkit.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights
  * reserved.
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved.
  * (http://www.torchmobile.com/)
  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
@@ skipping 10 matching lines @@
  *
  * You should have received a copy of the GNU Library General Public License
  * along with this library; see the file COPYING.LIB.  If not, write to
  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  * Boston, MA 02110-1301, USA.
  *
  */
 
 #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/EditingMarkerList.h"
+#include "core/editing/markers/SpellCheckMarkerList.h"
+#include "core/editing/markers/TextMatchMarkerList.h"
 #include "core/frame/FrameView.h"
 #include "core/layout/LayoutObject.h"
-#include <algorithm>
 
 #ifndef NDEBUG
 #include <stdio.h>
 #endif
 
 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;
+  for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    MarkerMap& markerMap = markerMapForType(type);
+    markerMap.clear();
+  }
 }
 
 void DocumentMarkerController::addMarker(const Position& start,
                                          const Position& end,
                                          DocumentMarker::MarkerType type,
                                          const String& description) {
+  DCHECK(type != DocumentMarker::TextMatch);
   // Use a TextIterator to visit the potentially multiple nodes the range
   // 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));
   }
 }
 
 void DocumentMarkerController::addTextMatchMarker(const EphemeralRange& range,
                                                   bool activeMatch) {
   DCHECK(!m_document->needsLayoutTreeUpdate());
 
   // 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 TextMatchMarker(markedText.startOffsetInCurrentContainer(),
+                                  markedText.endOffsetInCurrentContainer(),
+                                  activeMatch));
+  }
   // Don't invalidate tickmarks here. TextFinder invalidates tickmarks using a
   // throttling algorithm. crbug.com/6819.
 }
 
 void DocumentMarkerController::addCompositionMarker(const Position& start,
                                                     const Position& end,
                                                     Color underlineColor,
                                                     bool thick,
                                                     Color backgroundColor) {
   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() {
   clear();
 }
 
 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
         shouldRemovePartiallyOverlappingMarker) {
   DCHECK(!m_document->needsLayoutTreeUpdate());
 
   TextIterator markedText(range.startPosition(), range.endPosition());
   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) {
-  Range* range = Range::create(node.document());
-  // The offsets of the marker may be out-dated, so check for exceptions.
-  DummyExceptionStateForTesting exceptionState;
-  range->setStart(&const_cast<Node&>(node), marker.startOffset(),
-                  exceptionState);
-  if (!exceptionState.hadException()) {
-    range->setEnd(&const_cast<Node&>(node), marker.endOffset(),
-                  IGNORE_EXCEPTION_FOR_TESTING);
-  }
-  if (!exceptionState.hadException()) {
-    // TODO(yosin): Once we have a |EphemeralRange| version of |boundingBox()|,
-    // we should use it instead of |Range| version.
-    marker.setRenderedRect(LayoutRect(range->boundingBox()));
-  } else {
-    marker.nullifyRenderedRect();
-  }
-  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);
+  MarkerMap& markerMap = markerMapForType(newMarker->type());
+  auto it = markerMap.find(node);
+  if (it == markerMap.end()) {
+    markerMap.insert(node, createMarkerListOfType(newMarker->type()));
+    it = markerMap.find(node);
   }
 
-  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);
-    }
-  }
+  it->value.get()->add(newMarker);
 
   // repaint the affected node
   if (node->layoutObject()) {
     node->layoutObject()->setShouldDoFullPaintInvalidation(
         PaintInvalidationDocumentMarkerChange);
   }
 }
 
-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->erase(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.
 void DocumentMarkerController::copyMarkers(Node* srcNode,
                                            unsigned startOffset,
                                            int length,
                                            Node* dstNode,
                                            int delta) {
   if (length <= 0)
     return;
 
-  if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
-    return;
-  DCHECK(!m_markers.isEmpty());
+  bool docDirty = false;
 
-  MarkerLists* markers = m_markers.at(srcNode);
-  if (!markers)
-    return;
+  for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    MarkerMap& markerMap = markerMapForType(type);
+    auto dst_it = markerMap.find(dstNode);
+    if (dst_it == markerMap.end()) {
+      markerMap.insert(dstNode, createMarkerListOfType(type));
+      dst_it = markerMap.find(dstNode);
+    }
 
-  bool docDirty = false;
-  for (Member<MarkerList> list : *markers) {
-    if (!list)
+    // note: this must be looked up after dst_it because inserting a new
+    // destination list can cause the HashMap to re-hash, invalidating iterators
+    auto src_it = markerMap.find(srcNode);
+    if (src_it == markerMap.end())
       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);
-    }
+    docDirty = (src_it->value->copyMarkers(startOffset, length, dst_it->value,
+                                           delta) ==
+                DocumentMarkerList::DidCopyMarkerOrNot::DidCopyMarker) ||
+               docDirty;
   }
 
   // repaint the affected node
   if (docDirty && dstNode->layoutObject()) {
     dstNode->layoutObject()->setShouldDoFullPaintInvalidation(
         PaintInvalidationDocumentMarkerChange);
   }
 }
 
 void DocumentMarkerController::removeMarkers(
     Node* node,
     unsigned startOffset,
     int length,
     DocumentMarker::MarkerTypes markerTypes,
     RemovePartiallyOverlappingMarkerOrNot
         shouldRemovePartiallyOverlappingMarker) {
   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;
+  for (DocumentMarker::MarkerType type : markerTypes) {
+    MarkerMap& markerMap = markerMapForType(type);
+    auto it = markerMap.find(node);
+    if (it != markerMap.end()) {
+      docDirty =
+          (it->value->removeMarkers(startOffset, length,
+                                    shouldRemovePartiallyOverlappingMarker) ==
+           DocumentMarkerList::DidRemoveMarkerOrNot::DidRemoveMarker) ||
+          docDirty;
+      if (it->value->empty())
+        markerMap.erase(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();) {
-      const 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->erase(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.clone();
-        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.clone();
-        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 (list->isEmpty()) {
-      list.clear();
-      ++emptyListsCount;
-    }
-  }
-
-  if (emptyListsCount == DocumentMarker::MarkerTypeIndexesCount) {
-    m_markers.erase(node);
-    if (m_markers.isEmpty())
-      m_possiblyExistingMarkerTypes = 0;
   }
 
   // repaint the affected node
   if (docDirty && node->layoutObject()) {
     node->layoutObject()->setShouldDoFullPaintInvalidation(
         PaintInvalidationDocumentMarkerChange);
   }
 }
 
 DocumentMarkerVector DocumentMarkerController::markersFor(
     Node* node,
     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);
   return result;
 }
 
 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 (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    MarkerMap& markerMap = markerMapForType(type);
+    for (auto it = markerMap.begin(); it != markerMap.end(); ++it)
+      it->value->appendMarkersToInputList(&result);
   }
+
   std::sort(result.begin(), result.end(), compareByStart);
   return result;
 }
 
 DocumentMarkerVector DocumentMarkerController::markersInRange(
     const EphemeralRange& range,
     DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return DocumentMarkerVector();
 
   DocumentMarkerVector foundMarkers;
 
   Node* startContainer = range.startPosition().computeContainerNode();
   DCHECK(startContainer);
   unsigned startOffset = static_cast<unsigned>(
       range.startPosition().computeOffsetInContainerNode());
   Node* endContainer = range.endPosition().computeContainerNode();
   DCHECK(endContainer);
   unsigned endOffset =
       static_cast<unsigned>(range.endPosition().computeOffsetInContainerNode());
 
   for (Node& node : range.nodes()) {
     for (DocumentMarker* marker : markersFor(&node)) {
       if (!markerTypes.contains(marker->type()))
         continue;
       if (node == startContainer && marker->endOffset() <= startOffset)
         continue;
       if (node == endContainer && marker->startOffset() >= endOffset)
         continue;
       foundMarkers.push_back(marker);
     }
   }
   return foundMarkers;
 }
 
+// This method is only ever called with the type DocumentMarker::TextMatch
+// TODO(rlanday): remove the param
 Vector<IntRect> DocumentMarkerController::renderedRectsForMarkers(
-    DocumentMarker::MarkerType markerType) {
+    DocumentMarker::MarkerType) {
   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) {
-    // inner loop; process each marker in this node
+  for (auto nodeIterator = m_textMatches.begin();
+       nodeIterator != m_textMatches.end(); ++nodeIterator) {
     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)
-        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());
-      }
+    TextMatchMarkerList* list =
+        toTextMatchMarkerList(nodeIterator->value.get());
+#if DCHECK_IS_ON()
+    if (!list->empty()) {
+      DCHECK(!m_document->view() || !m_document->view()->needsLayout());
+      DCHECK(!m_document->needsLayoutTreeUpdate());
     }
+#endif
+    list->appendRenderedRectsToInputList(node, &result);
   }
 
   return result;
 }
 
 static void invalidatePaintForTickmarks(const Node& node) {
   if (FrameView* frameView = node.document().view())
     frameView->invalidatePaintForTickmarks();
 }
 
-void DocumentMarkerController::updateMarkerRenderedRectIfNeeded(
-    const Node& node,
-    RenderedDocumentMarker& marker) {
-  DCHECK(!m_document->view() || !m_document->view()->needsLayout());
-  DCHECK(!m_document->needsLayoutTreeUpdate());
-  if (!marker.isValid())
-    updateMarkerRenderedRect(node, marker);
-}
+void DocumentMarkerController::invalidateRectsForMarkersInNode(Node& node) {
+  if (!m_textMatches.contains(&node))
+    return;
 
-void DocumentMarkerController::invalidateRectsForMarkersInNode(
-    const Node& node) {
-  MarkerLists* markers = m_markers.at(&node);
-
-  for (auto& markerList : *markers) {
-    if (!markerList || markerList->isEmpty())
-      continue;
-
-    for (auto& marker : *markerList)
-      marker->invalidate();
-
-    if (markerList->front()->type() == DocumentMarker::TextMatch)
-      invalidatePaintForTickmarks(node);
-  }
+  toTextMatchMarkerList(m_textMatches.find(&node)->value.get())
+      ->invalidateRects();
+  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);
 }
 
 void DocumentMarkerController::removeMarkers(
     Node* node,
     DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  MarkerMap::iterator iterator = m_markers.find(node);
-  if (iterator != m_markers.end())
-    removeMarkersFromList(iterator, markerTypes);
-}
-
-void DocumentMarkerController::removeMarkers(
-    const MarkerRemoverPredicate& shouldRemoveMarker) {
-  for (auto& nodeMarkers : m_markers) {
-    const Node& node = *nodeMarkers.key;
-    if (!node.isTextNode())  // MarkerRemoverPredicate requires a Text node.
-      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->erase(j - 1);
-          removedMarkers = true;
-        }
-      }
-      if (removedMarkers &&
-          markerListIndex == DocumentMarker::TextMatchMarkerIndex)
-        invalidatePaintForTickmarks(node);
-    }
+  for (DocumentMarker::MarkerType type : markerTypes) {
+    MarkerMap& markerMap = markerMapForType(type);
+    markerMap.erase(node);
   }
 }
 
 void DocumentMarkerController::removeMarkers(
     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);
+  for (DocumentMarker::MarkerType type : markerTypes) {
+    MarkerMap& markerMap = markerMapForType(type);
+    markerMap.clear();
   }
-
-  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;
-  }
-
-  if (needsRepainting) {
-    const Node& node = *iterator->key;
-    if (LayoutObject* layoutObject = node.layoutObject()) {
-      layoutObject->setShouldDoFullPaintInvalidation(
-          PaintInvalidationDocumentMarkerChange);
-    }
-    invalidatePaintForTickmarks(node);
-  }
-
-  if (nodeCanBeRemoved) {
-    m_markers.erase(iterator);
-    if (m_markers.isEmpty())
-      m_possiblyExistingMarkerTypes = 0;
+void DocumentMarkerController::removeMarkers(
+    const MarkerRemoverPredicate& shouldRemoveMarker) {
+  for (auto& nodeMarkers : m_spelling) {
+    const Node& node = *nodeMarkers.key;
+    if (!node.isTextNode())
+      continue;
+    toSpellCheckMarkerList(nodeMarkers.value.get())
+        ->removeMarkersForWords(static_cast<const Text&>(node).data(),
+                                shouldRemoveMarker.m_words);
   }
 }
 
 void DocumentMarkerController::repaintMarkers(
     DocumentMarker::MarkerTypes markerTypes) {
-  if (!possiblyHasMarkers(markerTypes))
-    return;
-  DCHECK(!m_markers.isEmpty());
+  HeapHashSet<Member<Node>> nodesToRepaint;
+  for (DocumentMarker::MarkerType type : markerTypes) {
+    MarkerMap& markerMap = markerMapForType(type);
+    for (auto& nodeMarkers : markerMap) {
+      if (!nodeMarkers.value->empty())
+        nodesToRepaint.insert(nodeMarkers.key.get());
+    }
+  }
 
-  // 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();
   DCHECK(endContainer);
 
   const unsigned containerStartOffset =
       range.startPosition().computeOffsetInContainerNode();
   const unsigned containerEndOffset =
       range.endPosition().computeOffsetInContainerNode();
 
   bool markerFound = false;
   for (Node& node : range.nodes()) {
     int startOffset = node == startContainer ? containerStartOffset : 0;
     int endOffset = node == endContainer ? containerEndOffset : INT_MAX;
     markerFound |= setMarkersActive(&node, startOffset, endOffset, active);
   }
   return markerFound;
 }
 
+bool DocumentMarkerController::hasMarkers(Node* node) const {
+  for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    const MarkerMap& markerMap = markerMapForType(type);
+    if (markerMap.contains(node))
+      return true;
+  }
+
+  return false;
+}
+
 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 = toTextMatchMarkerList(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 (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    const MarkerMap& markerMap = markerMapForType(type);
+    for (const auto& nodeMarkers : markerMap)
+      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(")");
+
+    for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+      const MarkerMap& markerMap = markerMapForType(type);
+      if (markerMap.contains(node)) {
+        DocumentMarkerVector markers;
+        markerMap.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
 
+DocumentMarkerList* DocumentMarkerController::createMarkerListOfType(
+    DocumentMarker::MarkerType type) {
+  switch (type) {
+    case DocumentMarker::Spelling:
+      return new SpellCheckMarkerList(DocumentMarker::Spelling);
+    case DocumentMarker::Grammar:
+      return new SpellCheckMarkerList(DocumentMarker::Grammar);
+    case DocumentMarker::TextMatch:
+      return new TextMatchMarkerList();
+    case DocumentMarker::Composition:
+      return new CompositionMarkerList();
+    default:
+      // MSVC thinks this method doesn't handle all enum values even though it
+      // does. So we have to return something for the default case to avoid a
+      // C4715 warning.
+      UNREACHABLE();
+      return nullptr;
+  }
+}
+
+HeapVector<Member<DocumentMarkerList>>
+DocumentMarkerController::getMarkerListsForNode(
+    Node* node,
+    DocumentMarker::MarkerTypes markerTypes) {
+  HeapVector<Member<DocumentMarkerList>> markerLists;
+
+  for (DocumentMarker::MarkerType type : markerTypes) {
+    MarkerMap& markerMap = markerMapForType(type);
+    auto it = markerMap.find(node);
+    if (it != markerMap.end())
+      markerLists.push_back(it->value);
+  }
+
+  return markerLists;
+}
+
+DocumentMarkerController::MarkerMap& DocumentMarkerController::markerMapForType(
+    DocumentMarker::MarkerType type) {
+  return const_cast<MarkerMap&>(
+      const_cast<const DocumentMarkerController&>(*this).markerMapForType(
+          type));
+}
+
+const DocumentMarkerController::MarkerMap&
+DocumentMarkerController::markerMapForType(
+    DocumentMarker::MarkerType type) const {
+  switch (type) {
+    case DocumentMarker::Spelling:
+      return m_spelling;
+    case DocumentMarker::Grammar:
+      return m_grammar;
+    case DocumentMarker::TextMatch:
+      return m_textMatches;
+    case DocumentMarker::Composition:
+      return m_compositions;
+    default:
+      // MSVC thinks this method doesn't handle all enum values even though it
+      // does. So we have to return something for the default case to avoid a
+      // C4715 warning.
+      UNREACHABLE();
+      return m_spelling;
+  }
+}
+
+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);
+  bool didShiftMarker = false;
+  for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    MarkerMap& markerMap = markerMapForType(type);
 
-  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 (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
-      RenderedDocumentMarker& marker = **it;
-      Optional<DocumentMarker::MarkerOffsets> result =
-          marker.computeOffsetsAfterShift(offset, oldLength, newLength);
-      if (result == WTF::nullopt) {
-        list->erase(it - list->begin());
-        --it;
-        didShiftMarker = true;
-        continue;
-      }
-
-      if (marker.startOffset() != result.value().startOffset ||
-          marker.endOffset() != result.value().endOffset) {
-        didShiftMarker = true;
-        marker.setStartOffset(result.value().startOffset);
-        marker.setEndOffset(result.value().endOffset);
-      }
+    auto it = markerMap.find(node);
+    if (it != markerMap.end()) {
+      didShiftMarker =
+          (it->value->shiftMarkers(offset, oldLength, newLength) ==
+           DocumentMarkerList::DidShiftMarkerOrNot::DidShiftMarker) ||
+          didShiftMarker;
     }
   }
 
-  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
 
 #ifndef NDEBUG
 void showDocumentMarkers(const blink::DocumentMarkerController* controller) {
   if (controller)
     controller->showMarkers();
 }
 #endif