Rewrite DocumentMarkerController to use SynchronousMutationObserver

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 41afe11c85185d22f509ddc551141887d1ae33c5..9e6f06b28f1e731421150e71cfb61d9da13861bd 100644
--- a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp
@@ -84,8 +84,10 @@ inline bool DocumentMarkerController::possiblyHasMarkers(
   return m_possiblyExistingMarkerTypes.intersects(types);
 }
 
-DocumentMarkerController::DocumentMarkerController(const Document& document)
-    : m_possiblyExistingMarkerTypes(0), m_document(&document) {}
+DocumentMarkerController::DocumentMarkerController(Document& document)
+    : m_possiblyExistingMarkerTypes(0), m_document(&document) {
+  setContext(&document);
+}
 
 void DocumentMarkerController::clear() {
   m_markers.clear();
@@ -178,11 +180,6 @@ static bool startsFurther(const Member<RenderedDocumentMarker>& lhv,
   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();
@@ -588,6 +585,7 @@ void DocumentMarkerController::invalidateRectsForAllMarkers() {
 DEFINE_TRACE(DocumentMarkerController) {
   visitor->trace(m_markers);
   visitor->trace(m_document);
+  SynchronousMutationObserver::trace(visitor);
 }
 
 void DocumentMarkerController::removeMarkers(
@@ -697,6 +695,32 @@ void DocumentMarkerController::removeMarkersFromList(
   }
 }
 
+void DocumentMarkerController::removeZeroLengthMarkers() {

[Xiaocheng, 2017/02/22 01:49:23]

This function may cause performance issue. It iterates the marker lists for all
nodes. As a result, an editing operation can run time quadratic to the number of
text nodes modified.

It's better to handle empty marker removal right after adjusting the start/end
offsets of a marker.

[rlanday, 2017/02/22 02:01:10]

Ah, good catch

[rlanday, 2017/02/22 22:53:01]

Wait a second, isn't it potentially quadratic anyway? It's an improvement in
that we don't have to go through the lists a second time but we already have to
go through them once, and removing a marker causes an O(n) shift of the vector
elements wherever we do it...

[Xiaocheng, 2017/02/22 23:39:28]

The marker removal itself is indeed quadratic, to a different quantity (marker
list length), though.

My major concern is that this function unnecessarily iterates over all nodes
that have marker lists, resulting in another quadratic running time (to the
number of nodes).

+  for (auto& nodeMarkers : m_markers) {
+    const Node& node = *nodeMarkers.key;
+    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 (list->at(j - 1)->startOffset() == list->at(j - 1)->endOffset()) {
+          list->remove(j - 1);
+          removedMarkers = true;
+        }
+      }
+      if (!removedMarkers)
+        continue;
+      if (markerListIndex != DocumentMarker::TextMatchMarkerIndex)
+        continue;
+      invalidatePaintForTickmarks(node);
+    }
+  }
+}
+
 void DocumentMarkerController::repaintMarkers(
     DocumentMarker::MarkerTypes markerTypes) {
   if (!possiblyHasMarkers(markerTypes))
@@ -727,45 +751,6 @@ void DocumentMarkerController::repaintMarkers(
   }
 }
 
-void DocumentMarkerController::shiftMarkers(Node* node,
-                                            unsigned startOffset,
-                                            int delta) {
-  if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
-    return;
-  DCHECK(!m_markers.isEmpty());
-
-  MarkerLists* markers = m_markers.get(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();
-  }
-}
-
 bool DocumentMarkerController::setMarkersActive(const EphemeralRange& range,
                                                 bool active) {
   if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
@@ -858,6 +843,89 @@ void DocumentMarkerController::showMarkers() const {
 }
 #endif
 
+// 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.get(node);
+  if (!markers)
+    return;
+
+  bool didShiftMarker = false;
+  for (size_t markerListIndex = 0;

[Xiaocheng, 2017/02/22 01:49:23]

Range-based for loop is preferred.

[rlanday, 2017/02/22 02:14:57]

I think that would be difficult given that we're removing markers in the middle
of the loop...unless we want to shove them into a vector and remove them
afterward?

+       markerListIndex < DocumentMarker::MarkerTypeIndexesCount;
+       ++markerListIndex) {
+    Member<MarkerList> list = (*markers)[markerListIndex];
+    if (!list)
+      continue;
+
+    for (MarkerList::iterator marker = list->begin(); marker != list->end();
+         ++marker) {
+      // if marker is contained by but not equal to the replaced range, remove
+      // the marker
+      if ((offset <= (*marker)->startOffset() &&
+           (*marker)->endOffset() < offset + oldLength) ||
+          (offset < (*marker)->startOffset() &&
+           (*marker)->endOffset() <= offset + oldLength)) {
+        list->remove(marker - list->begin());
+        marker--;

[Xiaocheng, 2017/02/22 01:49:23]

s/marker--/--marker/

Chromium prefers prefix increment & decrement:

https://google.github.io/styleguide/cppguide.html#Preincrement_and_Predecrement

+        continue;
+      }
+
+      // 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 beginning of new
+          // text
+          (*marker)->setStartOffset(offset);

[Xiaocheng, 2017/02/22 01:49:23]

It seems more natural to move to end of new text.

New text shouldn't be marked by an existing marker unless it's in the middle of
the marker.

[rlanday, 2017/02/22 02:01:11]

I think this is how it works for DOM ranges, but I can try doing it this way for
markers and see if everything works

+        } else {
+          // Marker start was after the replaced text. Shift by length
+          // difference
+          unsigned oldStartOffset = (*marker)->startOffset();
+          (*marker)->setStartOffset(oldStartOffset + newLength - oldLength);
+        }
+      }
+
+      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;
+    }
+  }
+
+  if (didShiftMarker) {
+    removeZeroLengthMarkers();
+    invalidateRectsForMarkersInNode(*node);
+    // repaint the affected node
+    if (node->layoutObject())
+      node->layoutObject()->setShouldDoFullPaintInvalidation();

[Xiaocheng, 2017/02/22 01:49:23]

Do we really need this call?

Shouldn't paint (along with style and layout) be already invalidated before
entering didUpdateCharacterData?

[rlanday, 2017/02/22 02:01:11]

I'm not really sure, I think I added this because I saw that it got called in
removeMarkers()...

[yosin_UTC9, 2017/02/22 02:25:05]

Please ask wangxianzhu@, very near to you, he is THE expert of invalidation.
He may have some idea about better way.

[Xianzhu, 2017/02/22 21:32:56]

Though layout may also trigger the repaint, I think we should still call it
here, because:
- Here we are sure the object needs paint invalidation because of change of
marker;
- The call is cheap, and is near no-op if the object has already been set needs
paint invalidation;
- Depending on others to issue paint invalidation is fragile. Other code doesn't
know the requirements of markers and may miss the paint invalidation. For
example, some optimization like to avoid repainting an object containing all
blank characters might skip paint invalidation that markers need.

I also suggest to add a PaintInvalidationReason for markers as a follow-up which
will be useful for debugging and analysis.

+  }
+}
+
 }  // namespace blink
 
 #ifndef NDEBUG