Rewrite DocumentMarkerController to use SynchronousMutationObserver

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 66 matching lines @@
   return DocumentMarker::SpellingMarkerIndex;
 }
 
 }  // namespace
 
 inline bool DocumentMarkerController::possiblyHasMarkers(
     DocumentMarker::MarkerTypes types) {
   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();
   m_possiblyExistingMarkerTypes = 0;
 }
 
 void DocumentMarkerController::addMarker(const Position& start,
                                          const Position& end,
                                          DocumentMarker::MarkerType type,
                                          const String& description,
@@ skipping 72 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 385 matching lines @@
 
       if (markerList->front()->type() == DocumentMarker::TextMatch)
         invalidatePaintForTickmarks(node);
     }
   }
 }
 
 DEFINE_TRACE(DocumentMarkerController) {
   visitor->trace(m_markers);
   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);
@@ skipping 89 matching lines @@
     invalidatePaintForTickmarks(node);
   }
 
   if (nodeCanBeRemoved) {
     m_markers.remove(iterator);
     if (m_markers.isEmpty())
       m_possiblyExistingMarkerTypes = 0;
   }
 }
 
+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))
     return;
   DCHECK(!m_markers.isEmpty());
 
   // 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;
@@ skipping 10 matching lines @@
 
       // cause the node to be redrawn
       if (LayoutObject* layoutObject = node->layoutObject()) {
         layoutObject->setShouldDoFullPaintInvalidation();
         break;
       }
     }
   }
 }
 
-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()))
     return false;
 
   DCHECK(!m_markers.isEmpty());
 
   Node* const startContainer = range.startPosition().computeContainerNode();
   DCHECK(startContainer);
   Node* const endContainer = range.endPosition().computeContainerNode();
@@ skipping 72 matching lines @@
         builder.append(")");
       }
     }
     builder.append("\n");
   }
   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) {
+  // 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
 void showDocumentMarkers(const blink::DocumentMarkerController* controller) {
   if (controller)
     controller->showMarkers();
 }
 #endif