Add CompositionMarkerList in preparation for DocumentMarkerController refactor

third_party/WebKit/Source/core/editing/markers/DocumentMarkerListTest.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/DocumentMarkerList.h"
+
+#include "platform/heap/Handle.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace blink {
+
+class DocumentMarkerListForTesting : public DocumentMarkerList {

[Xiaocheng, 2017/03/25 00:05:35]

This is not dummy enough. Let's have:

class DMLForTesting : public DML {
protected:
 bool markerListIsSorted() const override { return false; }
private:
 DM::MarkerType allowedMarkerType() const final { ... }
};

Use DMLForTesting for shiftMarkers(), copyMarkers() and removeMarkers() with
unsorted list.

And then:

class SortedDMLForTesting final : public DMLForTesting {
private:
 bool markerListIsSorted() const final { return true; }
};

Use SortedDMLForTesting for removeMarkers() with sorted list.

Actually, I just realized that EditingMarkerListTest only needs to verify the
maintenance of |m_markersAreSorted|, which is exactly what you are doing :)

+ public:
+  DocumentMarkerListForTesting() : m_markersAreSorted(true) {}
+
+  DocumentMarker::MarkerType allowedMarkerType() const final {
+    return DocumentMarker::Composition;
+  }
+
+  void push_back(DocumentMarker* marker) final {
+    if (!m_markers.isEmpty() &&
+        m_markers.back()->endOffset() > marker->startOffset())
+      m_markersAreSorted = false;
+
+    m_markers.push_back(marker);
+  }
+
+  void clear() final {
+    m_markersAreSorted = true;
+    DocumentMarkerList::clear();
+  }
+
+ protected:
+  bool markerListIsSorted() const final { return m_markersAreSorted; }
+
+ private:
+  bool m_markersAreSorted;
+};
+
+class DocumentMarkerListTest : public ::testing::Test {
+ protected:
+  DocumentMarkerListTest() : m_markerList(new DocumentMarkerListForTesting()) {}
+
+  DocumentMarker* createMarker(unsigned startOffset, unsigned endOffset) {
+    return new DocumentMarker(startOffset, endOffset, Color::black, false,
+                              Color::black);
+  }
+
+  Persistent<DocumentMarkerListForTesting> m_markerList;
+};
+
+TEST_F(DocumentMarkerListTest,
+       RemoveMarkersSortedDoRemovePartiallyOverlapping) {
+  m_markerList->push_back(createMarker(0, 5));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(20, 25));
+  m_markerList->push_back(createMarker(30, 35));
+  m_markerList->push_back(createMarker(40, 45));
+
+  EXPECT_EQ(5u, m_markerList->size());
+
+  bool didRemoveMarker = false;
+
+  // test no-op remove
+  m_markerList->removeMarkers(100, 100, true, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, false);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  // remove middle marker
+  m_markerList->removeMarkers(20, 2, true, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(4u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(15u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(40u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(3)->endOffset());
+
+  // remove middle two markers
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(13, 19, true, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(2u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(40u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(1)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest,
+       RemoveMarkersUnsortedDoRemovePartiallyOverlapping) {
+  m_markerList->push_back(createMarker(40, 45));
+  m_markerList->push_back(createMarker(30, 35));
+  m_markerList->push_back(createMarker(20, 25));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(0, 5));
+
+  EXPECT_EQ(5u, m_markerList->size());
+
+  bool didRemoveMarker = false;
+
+  // test no-op remove
+  m_markerList->removeMarkers(100, 100, true, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, false);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  // remove middle marker
+  m_markerList->removeMarkers(20, 2, true, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(4u, m_markerList->size());
+
+  EXPECT_EQ(40u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(15u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(0u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(3)->endOffset());
+
+  // remove middle two markers
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(13, 19, true, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(2u, m_markerList->size());
+
+  EXPECT_EQ(40u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(0u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(1)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest,
+       RemoveMarkersSortedDontRemovePartiallyOverlapping) {
+  m_markerList->push_back(createMarker(0, 5));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(20, 25));
+  m_markerList->push_back(createMarker(30, 35));
+  m_markerList->push_back(createMarker(40, 45));
+
+  EXPECT_EQ(5u, m_markerList->size());
+
+  bool didRemoveMarker = false;
+
+  // test no-op remove
+  m_markerList->removeMarkers(100, 100, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, false);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  // remove chunk from beginning of middle marker
+  m_markerList->removeMarkers(20, 2, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(15u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(3)->endOffset());
+
+  EXPECT_EQ(40u, m_markerList->at(4)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(4)->endOffset());
+
+  // remove chunk from end of second marker
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(13, 2, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(13u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(3)->endOffset());
+
+  EXPECT_EQ(40u, m_markerList->at(4)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(4)->endOffset());
+
+  // remove chunk from middle of fourth marker
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(31, 1, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(6u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(13u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(31u, m_markerList->at(3)->endOffset());
+
+  EXPECT_EQ(32u, m_markerList->at(4)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(4)->endOffset());
+
+  EXPECT_EQ(40u, m_markerList->at(5)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(5)->endOffset());
+
+  // remove middle four markers
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(10, 25, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(2u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(40u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(1)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest,
+       RemoveMarkersUnsortedDontRemovePartiallyOverlapping) {
+  m_markerList->push_back(createMarker(40, 45));
+  m_markerList->push_back(createMarker(30, 35));
+  m_markerList->push_back(createMarker(20, 25));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(0, 5));
+
+  EXPECT_EQ(5u, m_markerList->size());
+
+  bool didRemoveMarker = false;
+
+  // test no-op remove
+  m_markerList->removeMarkers(100, 100, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, false);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  // remove chunk from beginning of middle marker
+  m_markerList->removeMarkers(20, 2, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  EXPECT_EQ(40u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(15u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(0u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(3)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(4)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(4)->endOffset());
+
+  // remove chunk from end of middle marker
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(13, 2, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(5u, m_markerList->size());
+
+  EXPECT_EQ(40u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(0u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(3)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(4)->startOffset());
+  EXPECT_EQ(13u, m_markerList->at(4)->endOffset());
+
+  // remove chunk from middle of second marker
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(31, 1, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(6u, m_markerList->size());
+
+  EXPECT_EQ(40u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(0u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(13u, m_markerList->at(3)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(4)->startOffset());
+  EXPECT_EQ(31u, m_markerList->at(4)->endOffset());
+
+  EXPECT_EQ(32u, m_markerList->at(5)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(5)->endOffset());
+
+  // remove all markers except 0 to 5 and 40 to 45
+  didRemoveMarker = false;
+  m_markerList->removeMarkers(5, 35, false, &didRemoveMarker);
+  EXPECT_EQ(didRemoveMarker, true);
+  EXPECT_EQ(2u, m_markerList->size());
+
+  EXPECT_EQ(40u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(45u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(0u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(1)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest, ShiftMarkersDeletions) {
+  m_markerList->push_back(createMarker(0, 5));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(20, 25));
+  m_markerList->push_back(createMarker(30, 35));
+  m_markerList->push_back(createMarker(40, 45));
+  // delete end of second marker, entirety of third marker, and start of fourth
+  // marker
+  m_markerList->shiftMarkers(13, 19, 0);
+
+  EXPECT_EQ(4u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(13u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(13u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(16u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(21u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(26u, m_markerList->at(3)->endOffset());
+
+  m_markerList->clear();
+  m_markerList->push_back(createMarker(5, 10));
+  // delete exactly on a marker
+  m_markerList->shiftMarkers(5, 5, 0);
+  EXPECT_EQ(0u, m_markerList->size());
+
+  m_markerList->push_back(createMarker(5, 10));
+  // delete middle of marker
+  m_markerList->shiftMarkers(6, 3, 0);
+  EXPECT_EQ(1u, m_markerList->size());
+  EXPECT_EQ(5u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(7u, m_markerList->at(0)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest, ShiftMarkersInsertions) {
+  m_markerList->push_back(createMarker(0, 5));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(20, 25));
+  // insert in middle of second marker
+  m_markerList->shiftMarkers(12, 0, 5);
+
+  EXPECT_EQ(3u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(20u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(25u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(30u, m_markerList->at(2)->endOffset());
+
+  // insert right after first marker
+  m_markerList->shiftMarkers(5, 0, 5);
+
+  EXPECT_EQ(3u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(15u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(30u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(35u, m_markerList->at(2)->endOffset());
+
+  // insert right before second marker
+  m_markerList->shiftMarkers(15, 0, 5);
+
+  EXPECT_EQ(3u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(20u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(30u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(35u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(40u, m_markerList->at(2)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest, ShiftMarkersReplacements) {
+  m_markerList->push_back(createMarker(0, 5));
+  m_markerList->push_back(createMarker(10, 15));
+  m_markerList->push_back(createMarker(20, 25));
+  m_markerList->push_back(createMarker(30, 35));
+  m_markerList->push_back(createMarker(40, 45));
+
+  // Replace entirely of third marker and portions of second and fourth
+  m_markerList->shiftMarkers(13, 19, 1);
+
+  EXPECT_EQ(4u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(5u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(10u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(13u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(14u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(17u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(22u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(27u, m_markerList->at(3)->endOffset());
+
+  // Replace end of first marker
+  m_markerList->shiftMarkers(3, 2, 1);
+
+  EXPECT_EQ(4u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(4u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(9u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(12u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(13u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(16u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(21u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(26u, m_markerList->at(3)->endOffset());
+
+  // Replace beginning of fourth marker
+  m_markerList->shiftMarkers(13, 2, 1);
+
+  EXPECT_EQ(4u, m_markerList->size());
+
+  EXPECT_EQ(0u, m_markerList->at(0)->startOffset());
+  EXPECT_EQ(4u, m_markerList->at(0)->endOffset());
+
+  EXPECT_EQ(9u, m_markerList->at(1)->startOffset());
+  EXPECT_EQ(12u, m_markerList->at(1)->endOffset());
+
+  EXPECT_EQ(13u, m_markerList->at(2)->startOffset());
+  EXPECT_EQ(15u, m_markerList->at(2)->endOffset());
+
+  EXPECT_EQ(20u, m_markerList->at(3)->startOffset());
+  EXPECT_EQ(25u, m_markerList->at(3)->endOffset());
+}
+
+TEST_F(DocumentMarkerListTest, CopyMarkers) {
+  m_markerList->push_back(createMarker(1, 2));
+  m_markerList->push_back(createMarker(3, 4));
+  m_markerList->push_back(createMarker(5, 6));
+  m_markerList->push_back(createMarker(7, 8));
+
+  DocumentMarkerListForTesting* dstList = new DocumentMarkerListForTesting();
+
+  // Copy all markers that intersect the range 2 through 5, i.e. the first three
+  m_markerList->copyMarkers(2, 4, dstList, -1);
+
+  EXPECT_EQ(3u, dstList->size());
+
+  // Markers are clamped to the range 2 through 5, so the first and third
+  // markers are now length 0

[Xiaocheng, 2017/03/25 00:05:35]

Though this matches the current behavior, it doesn't quite make sense...

I would like to have a TODO for future investigation.

+  EXPECT_EQ(1u, dstList->at(0)->startOffset());
+  EXPECT_EQ(1u, dstList->at(0)->endOffset());
+
+  EXPECT_EQ(2u, dstList->at(1)->startOffset());
+  EXPECT_EQ(3u, dstList->at(1)->endOffset());
+
+  EXPECT_EQ(4u, dstList->at(2)->startOffset());
+  EXPECT_EQ(4u, dstList->at(2)->endOffset());
+}
+
+}  // namespace blink