Add CompositionMarkerList in preparation for DocumentMarkerController refactor

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

+// 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/EditingMarkerList.h"
+
+#include <algorithm>
+#include "core/editing/markers/DocumentMarkerController.h"
+
+namespace blink {
+
+namespace {
+
+bool compareByStart(const Member<DocumentMarker>& lhv,
+                    const Member<DocumentMarker>& rhv) {
+  return lhv->startOffset() < rhv->startOffset();
+}
+
+}  // namespace
+
+EditingMarkerList::EditingMarkerList(
+    DocumentMarkerController* documentMarkerController)
+    : DocumentMarkerList(documentMarkerController), m_markersAreSorted(true) {}
+
+bool EditingMarkerList::isEditingMarkerList() const {
+  return true;
+}
+
+void EditingMarkerList::clear() {
+  m_markers.clear();
+  m_markersAreSorted = true;
+}
+
+void EditingMarkerList::removeMarkers(
+    unsigned startOffset,
+    int length,
+    bool shouldRemovePartiallyOverlappingMarkers,
+    bool* didRemoveMarker) {
+  unsigned endOffset = startOffset + length;
+  size_t markerIndex = 0;
+  if (m_markersAreSorted) {
+    markerIndex =
+        getPosOfFirstMarkerNotEndingBefore(startOffset) - m_markers.begin();
+  }
+
+  for (; markerIndex < m_markers.size();) {
+    DocumentMarker& marker = *m_markers.at(markerIndex);
+    if (!m_markersAreSorted) {
+      if (marker.endOffset() <= startOffset) {
+        ++markerIndex;
+        continue;
+      }
+    }
+
+    if (marker.startOffset() >= endOffset) {
+      if (m_markersAreSorted)
+        break;
+      ++markerIndex;
+      continue;
+    }
+
+    // pitch the old marker
+    m_markers.remove(markerIndex);

[Xiaocheng, 2017/03/24 03:57:47]

The handling of each marker in the removal range is basically identical with
TextMatchMarker::removeMarkers

Could you de-duplicate?

[rlanday, 2017/03/24 17:45:49]

Yeah, I think we can add a helper method that just takes an iterator range to
limit the search to, that lets us optimize for the case where the lis tis sorted

+    *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()) {

[Xiaocheng, 2017/03/24 03:57:47]

The case |startOffset > marker.startOffset() && endOffset < marker.endOffset()|
doesn't seem well-handled.

The two remaining pieces at its ends should be added back.

[rlanday, 2017/03/24 17:45:48]

I'm pretty sure this case is handled (it goes through both if statements)

Search EditingMarkerListTest for "remove chunk from" for proof

+      DocumentMarker* newLeft = new DocumentMarker(marker);
+      newLeft->setEndOffset(startOffset);
+      if (m_markersAreSorted) {
+        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 (m_markersAreSorted) {
+        m_markers.insert(markerIndex, *newRight);
+        // Move to the marker after the inserted one.
+        ++markerIndex;
+      } else {
+        m_markers.push_back(*newRight);
+      }
+    }
+  }
+}
+
+bool EditingMarkerList::shiftMarkers(unsigned offset,

[Xiaocheng, 2017/03/24 03:57:47]

This function is completely the same as TextMatchMarkerList::shiftMarkers. No
need to make it virtual.

[rlanday, 2017/03/24 17:45:48]

Oh...I think at one point, I thought I could optimize it when the marker list
was sorted, and realized I couldn't (markers are sorted by start offset, and
there's no way to guarantee that a shift won't affect a marker based only on the
marker's start position), and then it became the same...I'll move it to
DocumentMarkerList

+                                     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;
+}
+
+void EditingMarkerList::insert(DocumentMarker* marker) {
+  DCHECK(marker->type() == allowedMarkerType());
+  if (m_markersAreSorted && !m_markers.isEmpty() &&
+      m_markers.back()->endOffset() > marker->startOffset())
+    m_markersAreSorted = false;
+  m_markers.push_back(marker);
+}
+
+void EditingMarkerList::sortMarkerList() {
+  if (m_markersAreSorted)
+    return;
+
+  std::sort(m_markers.begin(), m_markers.end(), compareByStart);
+
+  m_markersAreSorted = true;
+}
+
+DEFINE_TRACE(EditingMarkerList) {
+  visitor->trace(m_markers);
+  DocumentMarkerList::trace(visitor);
+}
+
+}  // namespace blink