Add CompositionMarkerList 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..c2d52404ccf35b88e63c0f19f4972590621ba2f5
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.cpp
@@ -0,0 +1,165 @@
+// 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 {
+
+namespace {
+
+bool endsBefore(size_t startOffset, const Member<DocumentMarker>& rhv) {
+  return startOffset < rhv->endOffset();
+}
+
+}  // namespace
+
+DocumentMarkerList::DocumentMarkerList() {}
+
+bool DocumentMarkerList::isEditingMarkerList() const {
+  return false;
+}
+
+bool DocumentMarkerList::isSpellCheckMarkerList() const {
+  return false;
+}
+
+void DocumentMarkerList::clear() {
+  m_markers.clear();
+}
+
+void DocumentMarkerList::appendMarkersToInputList(
+    DocumentMarkerVector* list) const {
+  for (Member<DocumentMarker> marker : m_markers) {
+    list->push_back(marker);
+  }
+}
+
+bool DocumentMarkerList::copyMarkers(unsigned startOffset,
+                                     int length,
+                                     DocumentMarkerList* dstList,
+                                     int delta) const {
+  bool docDirty = false;
+  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) {
+      docDirty = true;
+      if (marker->startOffset() < startOffset)
+        marker->setStartOffset(startOffset);
+      if (marker->endOffset() > endOffset)
+        marker->setEndOffset(endOffset);
+      marker->shiftOffsets(delta);
+
+      dstList->push_back(marker);
+    }
+  }
+
+  return docDirty;
+}
+
+void DocumentMarkerList::removeMarkers(
+    unsigned startOffset,
+    int length,
+    bool shouldRemovePartiallyOverlappingMarkers,
+    bool* didRemoveMarker) {
+  unsigned endOffset = startOffset + length;
+  size_t markerIndex = 0;
+  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 = true;
+
+    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);
+      }
+    }
+  }
+}
+
+bool DocumentMarkerList::shiftMarkers(unsigned offset,
+                                      unsigned oldLength,
+                                      unsigned newLength) {
+  bool didShift = false;
+  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 = true;
+    } else if (result.newStartOffset != marker.startOffset() ||
+               result.newEndOffset != marker.endOffset()) {
+      marker.setStartOffset(result.newStartOffset);
+      marker.setEndOffset(result.newEndOffset);
+
+      didShift = true;
+    }
+  }
+  return didShift;
+}
+
+HeapVector<Member<DocumentMarker>>::iterator
+DocumentMarkerList::getPosOfFirstMarkerNotEndingBefore(size_t startOffset) {
+  DCHECK(markerListIsSorted());
+  return std::upper_bound(m_markers.begin(), m_markers.end(), startOffset,
+                          endsBefore);
+}
+
+DEFINE_TRACE(DocumentMarkerList) {
+  visitor->trace(m_markers);
+}
+
+}  // namespace blink