Significantly reduce memory used for deleting contiguous ranges backwards.

Compresses sequences of same item in vectors by adding a count field.
Fixes Notepad++ issue 13442.
https://github.com/notepad-plus-plus/notepad-plus-plus/issues/13442

4 files changed, 122 insertions, 46 deletions

diff --git a/doc/ScintillaHistory.html b/doc/ScintillaHistory.html
index a2942ebf4..5a54725a2 100644
--- a/doc/ScintillaHistory.html
+++ b/doc/ScintillaHistory.html
@@ -591,6 +591,10 @@
 	Released 22 September 2023.
 	</li>
 	<li>
+	Fix excesssive memory use when deleting contiguous ranges backwards.
+	<a href="https://github.com/notepad-plus-plus/notepad-plus-plus/issues/13442">Notepad++ Issue #13442</a>.
+	</li>
+	<li>
 	For Cocoa, fix invisible text on macOS 14 Sonoma.
 	<a href="https://sourceforge.net/p/scintilla/bugs/2402/">Bug #2402</a>.
 	</li>
diff --git a/src/ChangeHistory.cxx b/src/ChangeHistory.cxx
index 704f3f1c9..394b37e23 100644
--- a/src/ChangeHistory.cxx
+++ b/src/ChangeHistory.cxx
@@ -37,25 +37,48 @@ void ChangeStack::AddStep() {
 	steps.push_back(0);
 }
 
-void ChangeStack::PushDeletion(Sci::Position positionDeletion, int edition) {
-	steps.back()++;
-	changes.push_back({ positionDeletion, 0, edition, ChangeSpan::Direction::deletion });
+namespace {
+
+constexpr bool InsertionSpanSameDeletion(const ChangeSpan &is, Sci::Position positionDeletion, int edition) {
+	// Equal except for count
+	return
+		is.direction == ChangeSpan::Direction::deletion &&
+		is.start == positionDeletion &&
+		is.length == 0 &&
+		is.edition == edition;
+};
+
+}
+
+void ChangeStack::PushDeletion(Sci::Position positionDeletion, const EditionCount &ec) {
+	steps.back() += ec.count;
+	if (changes.empty() || !InsertionSpanSameDeletion(changes.back(), positionDeletion, ec.edition)) {
+		changes.push_back({ positionDeletion, 0, ec.edition, ec.count, ChangeSpan::Direction::deletion });
+	} else {
+		changes.back().count += ec.count;
+	}
 }
 
 void ChangeStack::PushInsertion(Sci::Position positionInsertion, Sci::Position length, int edition) {
 	steps.back()++;
-	changes.push_back({ positionInsertion, length, edition, ChangeSpan::Direction::insertion });
+	changes.push_back({ positionInsertion, length, edition, 1, ChangeSpan::Direction::insertion });
 }
 
-size_t ChangeStack::PopStep() noexcept {
-	const size_t spans = steps.back();
+int ChangeStack::PopStep() noexcept {
+	const int spans = steps.back();
 	steps.pop_back();
 	return spans;
 }
 
-ChangeSpan ChangeStack::PopSpan() noexcept {
-	const ChangeSpan span = changes.back();
-	changes.pop_back();
+ChangeSpan ChangeStack::PopSpan(int maxSteps) noexcept {
+	ChangeSpan span = changes.back();
+	const int remove = std::min(maxSteps, span.count);
+	if (span.count == remove) {
+		changes.pop_back();
+	} else {
+		changes.back().count -= remove;
+		span.count = remove;
+	}
 	return span;
 }
 
@@ -71,11 +94,14 @@ void ChangeStack::SetSavePoint() noexcept {
 void ChangeStack::Check() const noexcept {
 #ifdef _DEBUG
 	// Ensure count in steps same as insertions;
-	size_t sizeSteps = 0;
-	for (const size_t c : steps) {
+	int sizeSteps = 0;
+	for (const int c : steps) {
 		sizeSteps += c;
 	}
-	const size_t sizeInsertions = changes.size();
+	int sizeInsertions = 0;
+	for (const ChangeSpan &is: changes) {
+		sizeInsertions += is.count;
+	}
 	assert(sizeSteps == sizeInsertions);
 #endif
 }
@@ -117,8 +143,8 @@ void ChangeLog::CollapseRange(Sci::Position position, Sci::Position deleteLength
 	while (positionDeletion <= positionMax) {
 		const EditionSetOwned &editions = deleteEdition.ValueAt(positionDeletion);
 		if (editions) {
-			for (const int ed : *editions) {
-				PushDeletionAt(position, ed);
+			for (const EditionCount &ec : *editions) {
+				PushDeletionAt(position, ec);
 			}
 			EditionSetOwned empty;
 			deleteEdition.SetValueAt(positionDeletion, std::move(empty));
@@ -127,19 +153,50 @@ void ChangeLog::CollapseRange(Sci::Position position, Sci::Position deleteLength
 	}
 }
 
-void ChangeLog::PushDeletionAt(Sci::Position position, int edition) {
+namespace {
+
+// EditionSets have repeat counts on items so push and pop may just
+// manipulate the count field or may push/pop items.
+
+void EditionSetPush(EditionSet &set, EditionCount ec) {
+	if (set.empty() || (set.back().edition != ec.edition)) {
+		set.push_back(ec);
+	} else {
+		set.back().count += ec.count;
+	}
+}
+
+void EditionSetPop(EditionSet &set) noexcept {
+	if (set.back().count == 1) {
+		set.pop_back();
+	} else {
+		set.back().count--;
+	}
+}
+
+int EditionSetCount(const EditionSet &set) noexcept {
+	int count = 0;
+	for (const EditionCount &ec : set) {
+		count += ec.count;
+	}
+	return count;
+}
+
+}
+
+void ChangeLog::PushDeletionAt(Sci::Position position, EditionCount ec) {
 	if (!deleteEdition.ValueAt(position)) {
 		deleteEdition.SetValueAt(position, std::make_unique<EditionSet>());
 	}
-	deleteEdition.ValueAt(position)->push_back(edition);
+	EditionSetPush(*deleteEdition.ValueAt(position), ec);
 }
 
-void ChangeLog::InsertFrontDeletionAt(Sci::Position position, int edition) {
+void ChangeLog::InsertFrontDeletionAt(Sci::Position position, EditionCount ec) {
 	if (!deleteEdition.ValueAt(position)) {
 		deleteEdition.SetValueAt(position, std::make_unique<EditionSet>());
 	}
 	const EditionSetOwned &editions = deleteEdition.ValueAt(position);
-	editions->insert(editions->begin(), edition);
+	editions->insert(editions->begin(), ec);
 }
 
 void ChangeLog::SaveRange(Sci::Position position, Sci::Position length) {
@@ -161,8 +218,8 @@ void ChangeLog::SaveRange(Sci::Position position, Sci::Position length) {
 	while (positionDeletion <= positionMax) {
 		const EditionSetOwned &editions = deleteEdition.ValueAt(positionDeletion);
 		if (editions) {
-			for (const int ed : *editions) {
-				changeStack.PushDeletion(positionDeletion, ed);
+			for (const EditionCount &ec : *editions) {
+				changeStack.PushDeletion(positionDeletion, ec);
 			}
 		}
 		positionDeletion = deleteEdition.PositionNext(positionDeletion);
@@ -176,20 +233,25 @@ void ChangeLog::PopDeletion(Sci::Position position, Sci::Position deleteLength)
 	deleteEdition.SetValueAt(position, std::move(eso));
 	const EditionSetOwned &editions = deleteEdition.ValueAt(position);
 	assert(editions);
-	editions->pop_back();
-	const size_t inserts = changeStack.PopStep();
-	for (size_t i = 0; i < inserts; i++) {
-		const ChangeSpan span = changeStack.PopSpan();
+	EditionSetPop(*editions);
+	const int inserts = changeStack.PopStep();
+	for (int i = 0; i < inserts;) {
+		const ChangeSpan span = changeStack.PopSpan(inserts);
 		if (span.direction == ChangeSpan::Direction::insertion) {
+			assert(span.count == 1);	// Insertions are never compressed
 			insertEdition.FillRange(span.start, span.edition, span.length);
+			i++;
 		} else {
 			assert(editions);
-			assert(editions->back() == span.edition);
-			editions->pop_back();
+			assert(editions->back().edition == span.edition);
+			for (int j = 0; j < span.count; j++) {
+				EditionSetPop(*editions);
+			}
 			// Iterating backwards (pop) through changeStack, reverse order of insertion
 			// and original deletion list.
 			// Therefore need to insert at front to recreate original order.
-			InsertFrontDeletionAt(span.start, span.edition);
+			InsertFrontDeletionAt(span.start, { span.edition, span.count });
+			i += span.count;
 		}
 	}
 
@@ -228,9 +290,9 @@ void ChangeLog::SetSavePoint() {
 	for (Sci::Position positionDeletion = 0; positionDeletion <= length;) {
 		const EditionSetOwned &editions = deleteEdition.ValueAt(positionDeletion);
 		if (editions) {
-			for (int &ed : *editions) {
-				if (ed == changeModified) {
-					ed = changeSaved;
+			for (EditionCount &ec : *editions) {
+				if (ec.edition == changeModified) {
+					ec.edition = changeSaved;
 				}
 			}
 		}
@@ -248,7 +310,7 @@ size_t ChangeLog::DeletionCount(Sci::Position start, Sci::Position length) const
 	while (start <= end) {
 		const EditionSetOwned &editions = deleteEdition.ValueAt(start);
 		if (editions) {
-			count += editions->size();
+			count += EditionSetCount(*editions);
 		}
 		start = deleteEdition.PositionNext(start);
 	}
@@ -286,7 +348,7 @@ void ChangeHistory::DeleteRange(Sci::Position position, Sci::Position deleteLeng
 	if (changeLogReversions) {
 		changeLogReversions->DeleteRangeSavingHistory(position, deleteLength);
 		if (reverting) {
-			changeLogReversions->PushDeletionAt(position, changeRevertedOriginal);
+			changeLogReversions->PushDeletionAt(position, { changeRevertedOriginal, 1 });
 		}
 	}
 	Check();
@@ -294,7 +356,7 @@ void ChangeHistory::DeleteRange(Sci::Position position, Sci::Position deleteLeng
 
 void ChangeHistory::DeleteRangeSavingHistory(Sci::Position position, Sci::Position deleteLength, bool beforeSave, bool isDetached) {
 	changeLog.DeleteRangeSavingHistory(position, deleteLength);
-	changeLog.PushDeletionAt(position, beforeSave ? changeSaved : changeModified);
+	changeLog.PushDeletionAt(position, { beforeSave ? changeSaved : changeModified, 1 });
 	if (changeLogReversions) {
 		if (isDetached) {
 			changeLogReversions->SaveHistoryForDelete(position, deleteLength);
@@ -348,7 +410,7 @@ void ChangeHistory::EditionCreateHistory(Sci::Position start, Sci::Position leng
 		if (length) {
 			changeLog.insertEdition.FillRange(start, historicEpoch, length);
 		} else {
-			changeLog.PushDeletionAt(start, historicEpoch);
+			changeLog.PushDeletionAt(start, { historicEpoch, 1 });
 		}
 	}
 }
@@ -388,8 +450,8 @@ unsigned int ChangeHistory::EditionDeletesAt(Sci::Position pos) const noexcept {
 	unsigned int editionSet = 0;
 	const EditionSetOwned &editionSetDeletions = changeLog.deleteEdition.ValueAt(pos);
 	if (editionSetDeletions) {
-		for (const unsigned int ed : *editionSetDeletions) {
-			editionSet = editionSet | (1u << (ed-1));
+		for (const EditionCount &ec : *editionSetDeletions) {
+			editionSet = editionSet | (1u << (ec.edition-1));
 		}
 	}
 	if (changeLogReversions) {
diff --git a/src/ChangeHistory.h b/src/ChangeHistory.h
index 0475a3a6e..c39603670 100644
--- a/src/ChangeHistory.h
+++ b/src/ChangeHistory.h
@@ -26,23 +26,33 @@ struct ChangeSpan {
 	Sci::Position start;
 	Sci::Position length;
 	int edition;
+	int count;
 	enum class Direction { insertion, deletion } direction;
 };
 
+struct EditionCount {
+	int edition;
+	int count;
+	// Used in tests.
+	constexpr bool operator==(const EditionCount &other) const noexcept {
+		return (edition == other.edition) && (count == other.count);
+	}
+};
+
 // EditionSet is ordered from oldest to newest, its not really a set
-using EditionSet = std::vector<int>;
+using EditionSet = std::vector<EditionCount>;
 using EditionSetOwned = std::unique_ptr<EditionSet>;
 
 class ChangeStack {
-	std::vector<size_t> steps;
+	std::vector<int> steps;
 	std::vector<ChangeSpan> changes;
 public:
 	void Clear() noexcept;
 	void AddStep();
-	void PushDeletion(Sci::Position positionDeletion, int edition);
+	void PushDeletion(Sci::Position positionDeletion, const EditionCount &ec);
 	void PushInsertion(Sci::Position positionInsertion, Sci::Position length, int edition);
-	[[nodiscard]] size_t PopStep() noexcept;
-	[[nodiscard]] ChangeSpan PopSpan() noexcept;
+	[[nodiscard]] int PopStep() noexcept;
+	[[nodiscard]] ChangeSpan PopSpan(int maxSteps) noexcept;
 	void SetSavePoint() noexcept;
 	void Check() const noexcept;
 };
@@ -57,8 +67,8 @@ struct ChangeLog {
 	void DeleteRange(Sci::Position position, Sci::Position deleteLength);
 	void Insert(Sci::Position start, Sci::Position length, int edition);
 	void CollapseRange(Sci::Position position, Sci::Position deleteLength);
-	void PushDeletionAt(Sci::Position position, int edition);
-	void InsertFrontDeletionAt(Sci::Position position, int edition);
+	void PushDeletionAt(Sci::Position position, EditionCount ec);
+	void InsertFrontDeletionAt(Sci::Position position, EditionCount ec);
 	void SaveRange(Sci::Position position, Sci::Position length);
 	void PopDeletion(Sci::Position position, Sci::Position deleteLength);
 	void SaveHistoryForDelete(Sci::Position position, Sci::Position deleteLength);
diff --git a/test/unit/testCellBuffer.cxx b/test/unit/testCellBuffer.cxx
index f7795c9e7..690611d2f 100644
--- a/test/unit/testCellBuffer.cxx
+++ b/test/unit/testCellBuffer.cxx
@@ -586,14 +586,14 @@ TEST_CASE("ChangeHistory") {
 		REQUIRE(il.DeletionCount(0, 2) == 0);
 		il.DeleteRangeSavingHistory(1, 1, true, false);
 		REQUIRE(il.DeletionCount(0,2) == 1);
-		const EditionSet at1 = {2};
+		const EditionSet at1 = { {2, 1} };
 		REQUIRE(il.DeletionsAt(1) == at1);
 		il.DeleteRangeSavingHistory(1, 1, false, false);
 		REQUIRE(il.DeletionCount(0,1) == 2);
-		const EditionSet at2 = { 2, 3 };
+		const EditionSet at2 = { {2, 1}, {3, 1} };
 		REQUIRE(il.DeletionsAt(1) == at2);
 		il.DeleteRangeSavingHistory(0, 1, false, false);
-		const EditionSet at3 = { 2, 3, 3 };
+		const EditionSet at3 = { {2, 1}, {3, 2} };
 		REQUIRE(il.DeletionsAt(0) == at3);
 		REQUIRE(il.DeletionCount(0,0) == 3);