Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent

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

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "core/editing/markers/DocumentMarkerListEditor.h"
 
 #include "core/editing/markers/SpellCheckMarkerListImpl.h"
 
 namespace blink {
 
@@ skipping 54 matching lines @@
   MarkerList::iterator end_pos = std::lower_bound(
       list->begin(), list->end(), end_offset,
       [](const Member<DocumentMarker>& marker, size_t end_offset) {
         return marker->StartOffset() < end_offset;
       });
 
   list->erase(start_pos - list->begin(), end_pos - start_pos);
   return start_pos != end_pos;
 }
 
-// TODO(rlanday): make this not take O(n^2) time when all the markers are
-// removed
 bool DocumentMarkerListEditor::ShiftMarkersContentDependent(
     MarkerList* list,
     unsigned offset,
     unsigned old_length,
     unsigned new_length) {
+  // Find first marker that ends after the start of the region being edited.
+  // Markers before this one can be left untouched. This saves us some time over
+  // scanning the entire list linearly if the edit region is near the end of the
+  // text node.
+  MarkerList::iterator shift_range_begin =

[yosin_UTC9, 2017/06/05 03:35:40]

nit: s/MarkerList::iterator/const MarkerList::iterator&/

+      std::upper_bound(list->begin(), list->end(), offset,
+                       [](size_t offset, const Member<DocumentMarker>& marker) {
+                         return offset < marker->EndOffset();
+                       });
+
+  MarkerList::iterator erase_range_end = shift_range_begin;
+
   bool did_shift_marker = false;
-  for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
+  for (MarkerList::iterator it = shift_range_begin; it != list->end(); ++it) {
     DocumentMarker& marker = **it;
 
-    // marked text is neither changed nor shifted
-    if (marker.EndOffset() <= offset)
-      continue;
-
     // marked text is (potentially) changed by edit, remove marker
     if (marker.StartOffset() < offset + old_length) {
-      list->erase(it - list->begin());
-      --it;
+      erase_range_end = it + 1;

[yosin_UTC9, 2017/06/05 03:35:40]

nit: s/it + 1/std::next(it)/

       did_shift_marker = true;
       continue;
     }
 
     // marked text is shifted but not changed
     marker.ShiftOffsets(new_length - old_length);
     did_shift_marker = true;
   }
 
+  // Note: shift_range_begin could point at a marker being shifted instead of
+  // deleted, but if this is the case, we don't need to delete any markers, and
+  // erase() will get 0 for the length param
+  list->erase(shift_range_begin - list->begin(),
+              erase_range_end - shift_range_begin);
   return did_shift_marker;
 }
 
-// TODO(rlanday): make this not take O(n^2) time when all the markers are
-// removed
 bool DocumentMarkerListEditor::ShiftMarkersContentIndependent(
     MarkerList* list,
     unsigned offset,
     unsigned old_length,
     unsigned new_length) {
+  // Find first marker that ends after the start of the region being edited.
+  // Markers before this one can be left untouched. This saves us some time over
+  // scanning the entire list linearly if the edit region is near the end of the
+  // text node.
+  MarkerList::iterator shift_range_begin =

[yosin_UTC9, 2017/06/05 03:35:40]

nit: s/MarkerList::iterator/const MarkerList::iterator&/

+      std::upper_bound(list->begin(), list->end(), offset,
+                       [](size_t offset, const Member<DocumentMarker>& marker) {
+                         return offset < marker->EndOffset();
+                       });
+
+  MarkerList::iterator erase_range_begin = list->end();
+  MarkerList::iterator erase_range_end = list->end();
+
   bool did_shift_marker = false;
-  for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
+  for (MarkerList::iterator it = shift_range_begin; it != list->end(); ++it) {
     DocumentMarker& marker = **it;
     Optional<DocumentMarker::MarkerOffsets> result =
         marker.ComputeOffsetsAfterShift(offset, old_length, new_length);
     if (result == WTF::nullopt) {
-      list->erase(it - list->begin());
-      --it;
+      if (erase_range_begin == list->end())
+        erase_range_begin = it;
+      erase_range_end = it + 1;

[yosin_UTC9, 2017/06/05 03:35:40]

nit: s/it + 1/std::next(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);
     }
   }
 
+  list->erase(erase_range_begin - list->begin(),
+              erase_range_end - erase_range_begin);
   return did_shift_marker;
 }
 
 }  // namespace blink