Add DocumentMarkerList in preparation for DocumentMarkerController refactor

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

Index: third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.cpp
diff --git a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.cpp b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..ee725e7868ac7c9178d0477b9336348cbe067286
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.cpp
@@ -0,0 +1,169 @@
+// 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/DocumentMarkerList.h"
+
+namespace blink {
+
+DocumentMarkerList::DocumentMarkerList() {}
+
+bool DocumentMarkerList::isEditingMarkerList() const {
+  return false;
+}
+
+bool DocumentMarkerList::isSpellCheckMarkerList() const {
+  return false;
+}
+
+void DocumentMarkerList::add(DocumentMarker* marker) {
+  m_markers.push_back(marker);
+}
+
+void DocumentMarkerList::clear() {
+  m_markers.clear();
+}
+
+void DocumentMarkerList::appendMarkersToInputList(
+    DocumentMarkerVector* list) const {
+  for (Member<DocumentMarker> marker : m_markers) {
+    list->push_back(marker);
+  }
+}
+
+DocumentMarkerList::DidCopyMarkerOrNot DocumentMarkerList::copyMarkers(
+    unsigned startOffset,
+    int length,
+    DocumentMarkerList* dstList,
+    int delta) const {
+  DidCopyMarkerOrNot didCopyMarker = DidNotCopyMarker;
+  unsigned endOffset = startOffset + length - 1;
+
+  for (Member<DocumentMarker> marker : m_markers) {
+    // pin the marker to the specified range and apply the shift delta
+    if (marker->endOffset() >= startOffset &&
+        marker->startOffset() <= endOffset) {
+      didCopyMarker = DidCopyMarker;
+      if (marker->startOffset() < startOffset)
+        marker->setStartOffset(startOffset);
+      if (marker->endOffset() > endOffset)
+        marker->setEndOffset(endOffset);
+      marker->shiftOffsets(delta);
+
+      dstList->add(marker);

[Xiaocheng, 2017/03/28 00:02:06]

This might have some side-effect...

Now the same marker may present in multiple lists, which means an operation in
one list may modify another list.

Fortunately, currently the only caller of copyMarkers() is SplitTextNodeCommand,
which removes the duplicated markers right after calling copyMarkers().

Still, this appears as a bad design to me. A clean design should be that each
marker is stored exactly once in one marker list, which can be ensured by:
1. Put DocumentMarker and DocumentMarkerDetails off-heap; DM should store DMD
with a std::unique_ptr, and DISALLOW_COPY_AND_ASSIGN
2. DML::m_markers should hold its markers with std::unique_ptr (maybe something
like Vector<std::unique_ptr<DocumentMarker>>? I haven't tried yet...)
3. Which 2, DML can be made off-heap, which means DMC can also hold its lists
via std::unique_ptr

Anyway, this seems another big patch. It's fine to just have a TODO there.

+    }
+  }
+
+  return didCopyMarker;
+}
+
+DocumentMarkerList::DidRemoveMarkerOrNot DocumentMarkerList::removeMarkers(
+    unsigned startOffset,
+    int length,
+    bool shouldRemovePartiallyOverlappingMarkers) {
+  unsigned endOffset = startOffset + length;
+  size_t markerIndex = 0;
+  DidRemoveMarkerOrNot didRemoveMarker = DidNotRemoveMarker;
+
+  if (markerListIsSorted()) {
+    markerIndex =
+        getPosOfFirstMarkerNotEndingBefore(startOffset) - m_markers.begin();
+  }
+
+  while (markerIndex < m_markers.size()) {
+    DocumentMarker& marker = *m_markers.at(markerIndex);
+    if (!markerListIsSorted()) {
+      if (marker.endOffset() <= startOffset) {
+        ++markerIndex;
+        continue;
+      }
+    }
+
+    if (marker.startOffset() >= endOffset) {
+      if (markerListIsSorted())
+        break;
+      ++markerIndex;
+      continue;
+    }
+
+    // pitch the old marker
+    m_markers.remove(markerIndex);
+    didRemoveMarker = DidRemoveMarker;
+
+    if (shouldRemovePartiallyOverlappingMarkers) {
+      // Stop here. Don't add resulting slices back.
+      continue;
+    }
+
+    // add either of the resulting slices that are left after removing target
+    if (startOffset > marker.startOffset()) {
+      DocumentMarker* newLeft = new DocumentMarker(marker);
+      newLeft->setEndOffset(startOffset);
+      if (markerListIsSorted()) {
+        m_markers.insert(markerIndex, *newLeft);
+        // Move to the marker after the inserted one.
+        ++markerIndex;
+      } else {
+        // For the unsorted case, we just stick the new marker at the end of the
+        // list. The loop will eventually run on it but that's not a problem
+        // since it's known to be outside the range being removed.
+        m_markers.push_back(*newLeft);
+      }
+    }
+    if (marker.endOffset() > endOffset) {
+      DocumentMarker* newRight = new DocumentMarker(marker);
+      newRight->setStartOffset(endOffset);
+      if (markerListIsSorted()) {
+        m_markers.insert(markerIndex, *newRight);
+        // Move to the marker after the inserted one.
+        ++markerIndex;
+      } else {
+        m_markers.push_back(*newRight);
+      }
+    }
+  }
+
+  return didRemoveMarker;
+}
+
+DocumentMarkerList::DidShiftMarkerOrNot DocumentMarkerList::shiftMarkers(
+    unsigned offset,
+    unsigned oldLength,
+    unsigned newLength) {
+  DocumentMarkerList::DidShiftMarkerOrNot didShift = DidNotShiftMarker;
+  for (auto it = m_markers.begin(); it != m_markers.end(); ++it) {
+    DocumentMarker& marker = **it;
+
+    DocumentMarker::ShiftMarkerResult result =
+        marker.getShiftedMarkerPosition(offset, oldLength, newLength);
+    if (result.shouldRemoveMarker) {
+      m_markers.remove(it - m_markers.begin());
+      --it;
+
+      didShift = DidShiftMarker;
+    } else if (result.newStartOffset != marker.startOffset() ||
+               result.newEndOffset != marker.endOffset()) {
+      marker.setStartOffset(result.newStartOffset);
+      marker.setEndOffset(result.newEndOffset);
+
+      didShift = DidShiftMarker;
+    }
+  }
+  return didShift;
+}
+
+HeapVector<Member<DocumentMarker>>::iterator
+DocumentMarkerList::getPosOfFirstMarkerNotEndingBefore(size_t startOffset) {
+  DCHECK(markerListIsSorted());
+  return std::upper_bound(
+      m_markers.begin(), m_markers.end(), startOffset,
+      [](size_t startOffset, const Member<DocumentMarker>& rhv) -> bool {
+        return startOffset < rhv->endOffset();
+      });
+}
+
+DEFINE_TRACE(DocumentMarkerList) {
+  visitor->trace(m_markers);
+}
+
+}  // namespace blink