Improve how DocumentMarkerController updates markers in response to text edits

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 159 matching lines @@
   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 startsAfter(const Member<RenderedDocumentMarker>& marker,
-                        size_t startOffset) {
-  return marker->startOffset() < 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();
 }
 
@@ skipping 107 matching lines @@
 
   if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
     return;
   DCHECK(!m_markers.isEmpty());
 
   MarkerLists* markers = m_markers.at(srcNode);
   if (!markers)
     return;
 
   bool docDirty = false;
-  for (size_t markerListIndex = 0;
-       markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-       ++markerListIndex) {
-    Member<MarkerList>& list = (*markers)[markerListIndex];
+  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
@@ skipping 321 matching lines @@
   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);
   }
 
   m_possiblyExistingMarkerTypes.remove(markerTypes);
 }
 
+bool DocumentMarkerController::relocateMarkerIfNeeded(
+    RenderedDocumentMarker* marker,
+    unsigned offset,
+    unsigned oldLength,
+    unsigned newLength) {
+  bool didShiftMarker = false;
+
+  // algorithm inspired by https://dom.spec.whatwg.org/#concept-cd-replace
+  // but with some changes
+  if (marker->startOffset() > offset) {

[rlanday, 2017/03/23 22:52:00]

I think there's one more tweak we want to make: as written, if an insertion
happens right where a marker starts, the new text will be included in the
marker. E.g. if we have a marker from 5 to 10 and do an insert with offset 5,
oldLength 0, and newLength 5, the new marker will be from 5 to 15 instead of 10
to 15. We can fix this by writing >= here instead of >.

+    // Deviation from the concept-cd-replace algorithm: < instead of <= in
+    // the next line
+    if (marker->startOffset() < offset + oldLength) {

[rlanday, 2017/03/23 22:52:00]

Since we're moving the marker start to the end of the new text, it doesn't
matter if this is <= or < (offset + newLength == marker->startOffset() +
newLength - oldLength if marker->startOffset() == offset + oldLength), so I'm
going to change this back to <= to be consistent with the concept-cd-replace
algorithm

+      // 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;
+  }
+
+  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;
+  }
+
+  return didShiftMarker;
+}
+
 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;
@@ skipping 62 matching lines @@
       // cause the node to be redrawn
       if (LayoutObject* layoutObject = node->layoutObject()) {
         layoutObject->setShouldDoFullPaintInvalidation(
             PaintInvalidationDocumentMarkerChange);
         break;
       }
     }
   }
 }
 
-void DocumentMarkerController::shiftMarkers(Node* node,
-                                            unsigned startOffset,
-                                            int delta) {
-  if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  MarkerLists* markers = m_markers.at(node);
-  if (!markers)
-    return;
-
-  bool didShiftMarker = false;
-  for (size_t markerListIndex = 0;
-       markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
-       ++markerListIndex) {
-    Member<MarkerList>& list = (*markers)[markerListIndex];
-    if (!list)
-      continue;
-    MarkerList::iterator startPos =
-        std::lower_bound(list->begin(), list->end(), startOffset, startsAfter);
-    for (MarkerList::iterator marker = startPos; marker != list->end();
-         ++marker) {
-#if DCHECK_IS_ON()
-      int startOffset = (*marker)->startOffset();
-      DCHECK_GE(startOffset + delta, 0);
-#endif
-      (*marker)->shiftOffsets(delta);
-      didShiftMarker = true;
-    }
-  }
-
-  if (didShiftMarker) {
-    invalidateRectsForMarkersInNode(*node);
-    // repaint the affected node
-    if (node->layoutObject()) {
-      node->layoutObject()->setShouldDoFullPaintInvalidation(
-          PaintInvalidationDocumentMarkerChange);
-    }
-  }
-}
-
 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();
@@ skipping 79 matching lines @@
   LOG(INFO) << m_markers.size() << " nodes have markers:\n"
             << builder.toString().utf8().data();
 }
 #endif
 
 // SynchronousMutationObserver
 void DocumentMarkerController::didUpdateCharacterData(CharacterData* node,
                                                       unsigned offset,
                                                       unsigned oldLength,
                                                       unsigned newLength) {
-  // Shift markers as if we first remove the old text, then insert the new text
-  removeMarkers(node, offset, oldLength);
-  shiftMarkers(node, offset + oldLength, 0 - oldLength);
-  shiftMarkers(node, offset, 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 (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
+      RenderedDocumentMarker& marker = **it;
+      if (relocateMarkerIfNeeded(&marker, offset, oldLength, newLength)) {
+        didShiftMarker = true;
+
+        if (marker.startOffset() < marker.endOffset())
+          continue;
+        list->remove(it - list->begin());
+        --it;
+      }
+    }
+  }
+
+  if (!didShiftMarker)
+    return;
+  if (!node->layoutObject())
+    return;
+  invalidateRectsForMarkersInNode(*node);
+  // repaint the affected node
+  node->layoutObject()->setShouldDoFullPaintInvalidation();
 }
 
 }  // namespace blink
 
 #ifndef NDEBUG
 void showDocumentMarkers(const blink::DocumentMarkerController* controller) {
   if (controller)
     controller->showMarkers();
 }
 #endif