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

1 files changed, 17 insertions, 7 deletions

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);