[DMC #1] Refactor DocumentMarkerController on top of new DocumentMarkerListEditor class

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 a35faf98d9bc605e554452059d210cb6680f0860..8ca5d8ef1ab09fc907d85e199d596f03f5f160c4 100644
--- a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
@@ -77,6 +77,151 @@ DocumentMarker::MarkerTypeIndex MarkerTypeToMarkerIndex(
 
 }  // namespace
 
+static bool StartsFurther(const Member<DocumentMarker>& lhv,
+                          const DocumentMarker* rhv) {
+  return lhv->StartOffset() < rhv->StartOffset();
+}
+
+static bool EndsBefore(size_t start_offset, const Member<DocumentMarker>& rhv) {
+  return start_offset < rhv->EndOffset();
+}
+
+static bool CompareByStart(const Member<DocumentMarker>& lhv,
+                           const Member<DocumentMarker>& rhv) {
+  return lhv->StartOffset() < rhv->StartOffset();
+}
+
+static bool DoesNotOverlap(const Member<DocumentMarker>& lhv,
+                           const DocumentMarker* rhv) {
+  return lhv->EndOffset() < rhv->StartOffset();
+}
+
+bool DocumentMarkerList::IsEmpty() const {
+  return markers_.IsEmpty();
+}
+
+void DocumentMarkerList::Add(DocumentMarker* marker) {
+  if (markers_.IsEmpty() ||
+      markers_.back()->EndOffset() < marker->StartOffset()) {
+    markers_.push_back(marker);
+  } else {
+    if (marker->GetType() != DocumentMarker::kTextMatch &&
+        marker->GetType() != DocumentMarker::kComposition) {
+      MergeOverlapping(marker);
+    } else {
+      const auto pos = std::lower_bound(markers_.begin(), markers_.end(),
+                                        marker, StartsFurther);
+      markers_.insert(pos - markers_.begin(), marker);
+    }
+  }
+}
+
+void DocumentMarkerList::Clear() {
+  markers_.Clear();
+}
+
+void DocumentMarkerList::AppendMarkersToInputList(
+    DocumentMarkerVector* input_list) const {
+  input_list->AppendVector(markers_);
+}
+
+bool DocumentMarkerList::MoveMarkers(int length, DocumentMarkerList* dst_list) {
+  DCHECK_GT(length, 0);
+  bool didMoveMarker = false;
+  unsigned end_offset = length - 1;
+
+  DocumentMarkerVector::iterator it;
+  for (it = markers_.begin(); it != markers_.end(); ++it) {
+    DocumentMarker& marker = **it;
+    if (marker.StartOffset() > end_offset)
+      break;
+
+    // pin the marker to the specified range and apply the shift delta
+    if (marker.EndOffset() > end_offset)
+      marker.SetEndOffset(end_offset);
+
+    dst_list->Add(&marker);
+    didMoveMarker = true;
+  }
+
+  // Remove the range of markers that were moved to dstNode
+  markers_.erase(0, it - markers_.begin());
+
+  return didMoveMarker;
+}
+
+bool DocumentMarkerList::RemoveMarkers(unsigned start_offset, int length) {
+  unsigned end_offset = start_offset + length;
+
+  const auto startPos = std::upper_bound(markers_.begin(), markers_.end(),
+                                         start_offset, EndsBefore);
+  auto it = startPos;
+  for (; it != markers_.end(); ++it) {
+    if ((*it)->StartOffset() >= end_offset)
+      break;
+  }
+
+  // it should now point at the first marker *not* to be removed (or at
+  // markers_->end())
+  markers_.erase(startPos - markers_.begin(), it - startPos);
+
+  if (it == startPos)
+    return false;
+
+  return true;
+}
+
+bool DocumentMarkerList::ShiftMarkers(unsigned offset,
+                                      unsigned old_length,
+                                      unsigned new_length) {
+  DocumentMarkerVector newMarkerList;
+  bool didShiftMarker = false;
+  for (Member<DocumentMarker> marker : markers_) {
+    Optional<DocumentMarker::MarkerOffsets> result =
+        marker->ComputeOffsetsAfterShift(offset, old_length, new_length);
+
+    if (result == WTF::kNullopt) {
+      didShiftMarker = true;
+      continue;
+    }
+
+    if (result.value().start_offset != marker->StartOffset() ||
+        result.value().end_offset != marker->EndOffset()) {
+      marker->SetStartOffset(result.value().start_offset);
+      marker->SetEndOffset(result.value().end_offset);
+
+      didShiftMarker = true;
+    }
+
+    newMarkerList.push_back(marker);
+  }
+
+  swap(markers_, newMarkerList);
+  return didShiftMarker;
+}
+
+void DocumentMarkerList::MergeOverlapping(DocumentMarker* marker) {
+  auto first_overlapping = std::lower_bound(markers_.begin(), markers_.end(),
+                                            marker, DoesNotOverlap);
+  size_t index = first_overlapping - markers_.begin();
+  markers_.insert(index, marker);
+  const auto inserted = markers_.begin() + index;
+  first_overlapping = inserted + 1;
+  for (auto i = first_overlapping;
+       i != markers_.end() &&
+       (*i)->StartOffset() <= (*inserted)->EndOffset();) {
+    (*inserted)->SetStartOffset(
+        std::min((*inserted)->StartOffset(), (*i)->StartOffset()));
+    (*inserted)->SetEndOffset(
+        std::max((*inserted)->EndOffset(), (*i)->EndOffset()));
+    markers_.erase(i - markers_.begin());
+  }
+}
+
+DEFINE_TRACE(DocumentMarkerList) {
+  visitor->Trace(markers_);
+}
+
 inline bool DocumentMarkerController::PossiblyHasMarkers(
     DocumentMarker::MarkerTypes types) {
   return possibly_existing_marker_types_.Intersects(types);
@@ -100,10 +245,10 @@ void DocumentMarkerController::AddMarker(const Position& start,
   // covers.
   for (TextIterator marked_text(start, end); !marked_text.AtEnd();
        marked_text.Advance()) {
-    AddMarker(
-        marked_text.CurrentContainer(),
-        DocumentMarker(type, marked_text.StartOffsetInCurrentContainer(),
-                       marked_text.EndOffsetInCurrentContainer(), description));
+    AddMarker(marked_text.CurrentContainer(),
+              new DocumentMarker(
+                  type, marked_text.StartOffsetInCurrentContainer(),
+                  marked_text.EndOffsetInCurrentContainer(), description));
   }
 }
 
@@ -117,9 +262,9 @@ void DocumentMarkerController::AddTextMatchMarker(
   for (TextIterator marked_text(range.StartPosition(), range.EndPosition());
        !marked_text.AtEnd(); marked_text.Advance()) {
     AddMarker(marked_text.CurrentContainer(),
-              DocumentMarker(marked_text.StartOffsetInCurrentContainer(),
-                             marked_text.EndOffsetInCurrentContainer(),
-                             match_status));
+              new DocumentMarker(marked_text.StartOffsetInCurrentContainer(),
+                                 marked_text.EndOffsetInCurrentContainer(),
+                                 match_status));
   }
   // Don't invalidate tickmarks here. TextFinder invalidates tickmarks using a
   // throttling algorithm. crbug.com/6819.
@@ -133,11 +278,12 @@ void DocumentMarkerController::AddCompositionMarker(const Position& start,
   DCHECK(!document_->NeedsLayoutTreeUpdate());
 
   for (TextIterator marked_text(start, end); !marked_text.AtEnd();
-       marked_text.Advance())
+       marked_text.Advance()) {
     AddMarker(marked_text.CurrentContainer(),
-              DocumentMarker(marked_text.StartOffsetInCurrentContainer(),
-                             marked_text.EndOffsetInCurrentContainer(),
-                             underline_color, thick, background_color));
+              new DocumentMarker(marked_text.StartOffsetInCurrentContainer(),
+                                 marked_text.EndOffsetInCurrentContainer(),
+                                 underline_color, thick, background_color));
+  }
 }
 
 void DocumentMarkerController::PrepareForDestruction() {
@@ -168,26 +314,6 @@ void DocumentMarkerController::RemoveMarkers(
   DocumentMarkerController::RemoveMarkers(marked_text, marker_types);
 }
 
-static bool StartsFurther(const Member<RenderedDocumentMarker>& lhv,

[Xiaocheng, 2017/04/13 02:39:51]

There's no need to touch these functions if we keep RenderedDocumentMarker in
this patch. That's going to make the patch smaller.

-                          const DocumentMarker* rhv) {
-  return lhv->StartOffset() < rhv->StartOffset();
-}
-
-static bool EndsBefore(size_t start_offset,
-                       const Member<RenderedDocumentMarker>& rhv) {
-  return start_offset < 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 void UpdateMarkerRenderedRect(const Node& node,
                                      RenderedDocumentMarker& marker) {
   Range* range = Range::Create(node.GetDocument());
@@ -213,12 +339,12 @@ static void UpdateMarkerRenderedRect(const Node& node,
 // Markers of the same type do not overlap each other.
 
 void DocumentMarkerController::AddMarker(Node* node,
-                                         const DocumentMarker& new_marker) {
-  DCHECK_GE(new_marker.EndOffset(), new_marker.StartOffset());
-  if (new_marker.EndOffset() == new_marker.StartOffset())
+                                         const DocumentMarker* new_marker) {
+  DCHECK_GE(new_marker->EndOffset(), new_marker->StartOffset());
+  if (new_marker->EndOffset() == new_marker->StartOffset())
     return;
 
-  possibly_existing_marker_types_.Add(new_marker.GetType());
+  possibly_existing_marker_types_.Add(new_marker->GetType());
 
   Member<MarkerLists>& markers =
       markers_.insert(node, nullptr).stored_value->value;
@@ -228,26 +354,15 @@ void DocumentMarkerController::AddMarker(Node* node,
   }
 
   DocumentMarker::MarkerTypeIndex marker_list_index =
-      MarkerTypeToMarkerIndex(new_marker.GetType());
+      MarkerTypeToMarkerIndex(new_marker->GetType());
   if (!markers->at(marker_list_index)) {
-    markers->at(marker_list_index) = new MarkerList;
+    markers->at(marker_list_index) = new DocumentMarkerList;
   }
 
-  Member<MarkerList>& list = markers->at(marker_list_index);
+  DocumentMarkerList* list = markers->at(marker_list_index);
   RenderedDocumentMarker* new_rendered_marker =
-      RenderedDocumentMarker::Create(new_marker);
-  if (list->IsEmpty() || list->back()->EndOffset() < new_marker.StartOffset()) {
-    list->push_back(new_rendered_marker);
-  } else {
-    if (new_marker.GetType() != DocumentMarker::kTextMatch &&
-        new_marker.GetType() != DocumentMarker::kComposition) {
-      MergeOverlapping(list.Get(), new_rendered_marker);
-    } else {
-      MarkerList::iterator pos = std::lower_bound(list->begin(), list->end(),
-                                                  &new_marker, StartsFurther);
-      list->insert(pos - list->begin(), new_rendered_marker);
-    }
-  }
+      RenderedDocumentMarker::Create(*new_marker);
+  list->Add(new_rendered_marker);
 
   // repaint the affected node
   if (node->GetLayoutObject()) {
@@ -256,25 +371,6 @@ void DocumentMarkerController::AddMarker(Node* node,
   }
 }
 
-void DocumentMarkerController::MergeOverlapping(

[Xiaocheng, 2017/04/13 02:39:51]

DML::MergeOverlapping can be put here, so that it is clear that the old impl is
not thrown away.

-    MarkerList* list,
-    RenderedDocumentMarker* to_insert) {
-  MarkerList::iterator first_overlapping =
-      std::lower_bound(list->begin(), list->end(), to_insert, DoesNotOverlap);
-  size_t index = first_overlapping - list->begin();
-  list->insert(index, to_insert);
-  MarkerList::iterator inserted = list->begin() + index;
-  first_overlapping = inserted + 1;
-  for (MarkerList::iterator i = first_overlapping;
-       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());
-  }
-}
-
 // Moves markers from src_node to dst_node. Markers are moved if their start
 // offset is less than length. Markers that run past that point are truncated.
 void DocumentMarkerController::MoveMarkers(Node* src_node,
@@ -287,34 +383,29 @@ void DocumentMarkerController::MoveMarkers(Node* src_node,
     return;
   DCHECK(!markers_.IsEmpty());
 
-  MarkerLists* markers = markers_.at(src_node);
-  if (!markers)
+  MarkerLists* src_markers = markers_.at(src_node);
+  if (!src_markers)
     return;
 
+  Member<MarkerLists>& dst_markers =
+      markers_.insert(dst_node, nullptr).stored_value->value;
+  if (!dst_markers) {
+    dst_markers = new MarkerLists;
+    dst_markers->Grow(DocumentMarker::kMarkerTypeIndexesCount);
+  }
+
   bool doc_dirty = false;
-  for (Member<MarkerList> list : *markers) {
-    if (!list)
+  for (size_t marker_list_index = 0; marker_list_index < src_markers->size();
+       marker_list_index++) {
+    DocumentMarkerList* src_list = src_markers->at(marker_list_index);
+    if (!src_list)
       continue;
 
-    unsigned end_offset = length - 1;
-    MarkerList::iterator it;
-    for (it = list->begin(); it != list->end(); ++it) {
-      DocumentMarker* marker = it->Get();
-
-      // stop if we are now past the specified range
-      if (marker->StartOffset() > end_offset)
-        break;
-
-      // pin the marker to the specified range
-      doc_dirty = true;
-      if (marker->EndOffset() > end_offset)
-        marker->SetEndOffset(end_offset);
-
-      AddMarker(dst_node, *marker);
+    if (!dst_markers->at(marker_list_index)) {
+      dst_markers->at(marker_list_index) = new DocumentMarkerList;
     }
 
-    // Remove the range of markers that were moved to dstNode
-    list->erase(0, it - list->begin());
+    src_list->MoveMarkers(length, dst_markers->at(marker_list_index));
   }
 
   // repaint the affected node
@@ -342,32 +433,20 @@ void DocumentMarkerController::RemoveMarkers(
 
   bool doc_dirty = false;
   size_t empty_lists_count = 0;
-  for (size_t marker_list_index = 0;
-       marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
-       ++marker_list_index) {
-    Member<MarkerList>& list = (*markers)[marker_list_index];
+  for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    size_t marker_list_index = MarkerTypeToMarkerIndex(type);
+
+    Member<DocumentMarkerList>& list = (*markers)[marker_list_index];
     if (!list || list->IsEmpty()) {
       if (list.Get() && list->IsEmpty())
         list.Clear();
       ++empty_lists_count;
       continue;
     }
-    if (!marker_types.Contains((*list->begin())->GetType()))
+    if (!marker_types.Contains(type))
       continue;
-    unsigned end_offset = start_offset + length;
-    MarkerList::iterator start_pos =
-        std::upper_bound(list->begin(), list->end(), start_offset, EndsBefore);
-    for (MarkerList::iterator i = start_pos; 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() >= end_offset)
-        break;
 
-      list->erase(i - list->begin());
-      doc_dirty = true;
-    }
+    doc_dirty = list->RemoveMarkers(start_offset, length) || doc_dirty;
 
     if (list->IsEmpty()) {
       list.Clear();
@@ -397,16 +476,14 @@ DocumentMarkerVector DocumentMarkerController::MarkersFor(
   if (!markers)
     return result;
 
-  for (size_t marker_list_index = 0;
-       marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
-       ++marker_list_index) {
-    Member<MarkerList>& list = (*markers)[marker_list_index];
-    if (!list || list->IsEmpty() ||
-        !marker_types.Contains((*list->begin())->GetType()))
+  for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+    size_t marker_list_index = MarkerTypeToMarkerIndex(type);
+
+    DocumentMarkerList* list = (*markers)[marker_list_index];
+    if (!list || list->IsEmpty() || !marker_types.Contains(type))
       continue;
 
-    for (size_t i = 0; i < list->size(); ++i)
-      result.push_back(list->at(i).Get());
+    list->AppendMarkersToInputList(&result);
   }
 
   std::sort(result.begin(), result.end(), CompareByStart);
@@ -420,11 +497,14 @@ DocumentMarkerVector DocumentMarkerController::Markers() {
     for (size_t marker_list_index = 0;
          marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
          ++marker_list_index) {
-      Member<MarkerList>& list = (*markers)[marker_list_index];
-      for (size_t j = 0; list.Get() && j < list->size(); ++j)
-        result.push_back(list->at(j).Get());
+      DocumentMarkerList* list = (*markers)[marker_list_index];
+      if (!list)
+        continue;
+
+      list->AppendMarkersToInputList(&result);
     }
   }
+
   std::sort(result.begin(), result.end(), CompareByStart);
   return result;
 }
@@ -475,20 +555,20 @@ Vector<IntRect> DocumentMarkerController::RenderedRectsForMarkers(
     // inner loop; process each marker in this node
     const Node& node = *node_iterator->key;
     MarkerLists* markers = node_iterator->value.Get();
-    for (size_t marker_list_index = 0;
-         marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
-         ++marker_list_index) {
-      Member<MarkerList>& list = (*markers)[marker_list_index];
-      if (!list || list->IsEmpty() ||
-          (*list->begin())->GetType() != marker_type)
+    for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+      size_t marker_list_index = MarkerTypeToMarkerIndex(type);
+      DocumentMarkerList* list = (*markers)[marker_list_index];
+      if (!list || list->IsEmpty() || type != marker_type)
         continue;
-      for (unsigned marker_index = 0; marker_index < list->size();
-           ++marker_index) {
-        RenderedDocumentMarker* marker = list->at(marker_index).Get();
-        UpdateMarkerRenderedRectIfNeeded(node, *marker);
-        if (!marker->IsRendered())
+      DocumentMarkerVector markers_in_list;
+      list->AppendMarkersToInputList(&markers_in_list);
+      for (DocumentMarker* marker : markers_in_list) {
+        RenderedDocumentMarker* rendered_marker =
+            ToRenderedDocumentMarker(marker);
+        UpdateMarkerRenderedRectIfNeeded(node, *rendered_marker);
+        if (!rendered_marker->IsRendered())
           continue;
-        result.push_back(marker->RenderedRect());
+        result.push_back(rendered_marker->RenderedRect());
       }
     }
   }
@@ -514,14 +594,17 @@ void DocumentMarkerController::InvalidateRectsForMarkersInNode(
     const Node& node) {
   MarkerLists* markers = markers_.at(&node);
 
-  for (auto& marker_list : *markers) {
+  for (DocumentMarkerList* marker_list : *markers) {
     if (!marker_list || marker_list->IsEmpty())
       continue;
 
-    for (auto& marker : *marker_list)
-      marker->Invalidate();
+    DocumentMarkerVector markers_in_list;
+    marker_list->AppendMarkersToInputList(&markers_in_list);
+
+    for (DocumentMarker* marker : markers_in_list)
+      ToRenderedDocumentMarker(marker)->Invalidate();
 
-    if (marker_list->front()->GetType() == DocumentMarker::kTextMatch)
+    if (markers_in_list.front()->GetType() == DocumentMarker::kTextMatch)
       InvalidatePaintForTickmarks(node);
   }
 }
@@ -529,14 +612,16 @@ void DocumentMarkerController::InvalidateRectsForMarkersInNode(
 void DocumentMarkerController::InvalidateRectsForAllMarkers() {
   for (auto& node_markers : markers_) {
     const Node& node = *node_markers.key;
-    for (auto& marker_list : *node_markers.value) {
+    for (DocumentMarkerList* marker_list : *node_markers.value) {
       if (!marker_list || marker_list->IsEmpty())
         continue;
 
-      for (auto& marker : *marker_list)
-        marker->Invalidate();
+      DocumentMarkerVector markers_in_list;
+      marker_list->AppendMarkersToInputList(&markers_in_list);
+      for (DocumentMarker* marker : markers_in_list)
+        ToRenderedDocumentMarker(marker)->Invalidate();
 
-      if (marker_list->front()->GetType() == DocumentMarker::kTextMatch)
+      if (markers_in_list.front()->GetType() == DocumentMarker::kTextMatch)
         InvalidatePaintForTickmarks(node);
     }
   }
@@ -570,17 +655,26 @@ void DocumentMarkerController::RemoveMarkers(
     for (size_t marker_list_index = 0;
          marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
          ++marker_list_index) {
-      Member<MarkerList>& list = markers[marker_list_index];
+      DocumentMarkerList* list = markers[marker_list_index];
       if (!list)
         continue;
       bool removed_markers = false;
-      for (size_t j = list->size(); j > 0; --j) {
-        if (should_remove_marker(*list->at(j - 1),
+
+      DocumentMarkerVector markers_in_list;
+      list->AppendMarkersToInputList(&markers_in_list);
+
+      for (size_t j = markers_in_list.size(); j > 0; --j) {
+        if (should_remove_marker(*markers_in_list[j - 1],
                                  static_cast<const Text&>(node))) {
-          list->erase(j - 1);
+          markers_in_list.erase(j - 1);
           removed_markers = true;
         }
       }
+
+      list->Clear();
+      for (DocumentMarker* marker : markers_in_list)
+        list->Add(marker);
+
       if (removed_markers &&
           marker_list_index == DocumentMarker::kTextMatchMarkerIndex)
         InvalidatePaintForTickmarks(node);
@@ -619,22 +713,14 @@ void DocumentMarkerController::RemoveMarkersFromList(
   } else {
     MarkerLists* markers = iterator->value.Get();
 
-    for (size_t marker_list_index = 0;
-         marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
-         ++marker_list_index) {
-      Member<MarkerList>& list = (*markers)[marker_list_index];
-      if (!list || list->IsEmpty()) {
-        if (list.Get() && list->IsEmpty())
-          list.Clear();
-        ++empty_lists_count;
-        continue;
-      }
-      if (marker_types.Contains((*list->begin())->GetType())) {
+    for (DocumentMarker::MarkerType type : marker_types) {
+      size_t marker_list_index = MarkerTypeToMarkerIndex(type);
+      DocumentMarkerList* list = (*markers)[marker_list_index];
+      if (list)
         list->Clear();
-        list.Clear();
-        ++empty_lists_count;
-        needs_repainting = true;
-      }
+
+      ++empty_lists_count;
+      needs_repainting = true;
     }
 
     node_can_be_removed =
@@ -670,12 +756,10 @@ void DocumentMarkerController::RepaintMarkers(
 
     // inner loop: process each marker in the current node
     MarkerLists* markers = i->value.Get();
-    for (size_t marker_list_index = 0;
-         marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
-         ++marker_list_index) {
-      Member<MarkerList>& list = (*markers)[marker_list_index];
-      if (!list || list->IsEmpty() ||
-          !marker_types.Contains((*list->begin())->GetType()))
+    for (DocumentMarker::MarkerType type : DocumentMarker::AllMarkers()) {
+      size_t marker_list_index = MarkerTypeToMarkerIndex(type);
+      DocumentMarkerList* list = (*markers)[marker_list_index];
+      if (!list || list->IsEmpty() || !marker_types.Contains(type))
         continue;
 
       // cause the node to be redrawn
@@ -723,20 +807,24 @@ bool DocumentMarkerController::SetMarkersActive(Node* node,
     return false;
 
   bool doc_dirty = false;
-  Member<MarkerList>& list =
-      (*markers)[MarkerTypeToMarkerIndex(DocumentMarker::kTextMatch)];
+  DocumentMarkerList* list =
+      markers->at(MarkerTypeToMarkerIndex(DocumentMarker::kTextMatch));
   if (!list)
     return false;
-  MarkerList::iterator start_pos =
-      std::upper_bound(list->begin(), list->end(), start_offset, EndsBefore);
-  for (MarkerList::iterator marker = start_pos; marker != list->end();
-       ++marker) {
+
+  DocumentMarkerVector markers_in_list;
+  list->AppendMarkersToInputList(&markers_in_list);
+
+  const auto start_pos = std::upper_bound(
+      markers_in_list.begin(), markers_in_list.end(), start_offset, EndsBefore);
+  for (auto marker_it = start_pos; marker_it != markers_in_list.end();
+       ++marker_it) {
     // Markers are returned in order, so stop if we are now past the specified
     // range.
-    if ((*marker)->StartOffset() >= end_offset)
+    if ((*marker_it)->StartOffset() >= end_offset)
       break;
 
-    (*marker)->SetIsActiveMatch(active);
+    (*marker_it)->SetIsActiveMatch(active);
     doc_dirty = true;
   }
 
@@ -760,10 +848,12 @@ void DocumentMarkerController::ShowMarkers() const {
     for (size_t marker_list_index = 0;
          marker_list_index < DocumentMarker::kMarkerTypeIndexesCount;
          ++marker_list_index) {
-      Member<MarkerList>& list = (*markers)[marker_list_index];
-      for (unsigned marker_index = 0; list.Get() && marker_index < list->size();
-           ++marker_index) {
-        DocumentMarker* marker = list->at(marker_index).Get();
+      DocumentMarkerList* list = markers->at(marker_list_index);
+      DocumentMarkerVector markers_in_list;
+      list->AppendMarkersToInputList(&markers_in_list);
+      for (unsigned marker_index = 0;
+           list && marker_index < markers_in_list.size(); ++marker_index) {
+        DocumentMarker* marker = markers_in_list[marker_index];
         builder.Append(" ");
         builder.AppendNumber(marker->GetType());
         builder.Append(":[");
@@ -796,28 +886,12 @@ void DocumentMarkerController::DidUpdateCharacterData(CharacterData* node,
     return;
 
   bool did_shift_marker = false;
-  for (MarkerList* list : *markers) {
+  for (DocumentMarkerList* 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, old_length, new_length);
-      if (result == WTF::kNullopt) {
-        list->erase(it - list->begin());
-        --it;
-        did_shift_marker = true;
-        continue;
-      }
-
-      if (marker.StartOffset() != result.value().start_offset ||
-          marker.EndOffset() != result.value().end_offset) {
-        did_shift_marker = true;
-        marker.SetStartOffset(result.value().start_offset);
-        marker.SetEndOffset(result.value().end_offset);
-      }
-    }
+    did_shift_marker =
+        list->ShiftMarkers(offset, old_length, new_length) || did_shift_marker;
   }
 
   if (!did_shift_marker)