Store undo text in ScrapStack, a single allocation instead of one allocation per

step. This saves about 50% for a long sequence of single byte actions.

4 files changed, 122 insertions, 58 deletions

diff --git a/src/CellBuffer.cxx b/src/CellBuffer.cxx
index fd6fe55fb..01074d666 100644
--- a/src/CellBuffer.cxx
+++ b/src/CellBuffer.cxx
@@ -1088,16 +1088,11 @@ int CellBuffer::StartUndo() noexcept {
 }
 
 Action CellBuffer::GetUndoStep() const noexcept {
-	const UndoAction &actionStep = uh->GetUndoStep();
-	Action acta{ actionStep.at, actionStep.mayCoalesce, actionStep.position, nullptr, actionStep.lenData };
-	if (actionStep.lenData) {
-		acta.data = actionStep.data.get();
-	}
-	return acta;
+	return uh->GetUndoStep();
 }
 
 void CellBuffer::PerformUndoStep() {
-	const UndoAction &actionStep = uh->GetUndoStep();
+	const Action actionStep = uh->GetUndoStep();
 	if (changeHistory && uh->BeforeSavePoint()) {
 		changeHistory->StartReversion();
 	}
@@ -1112,7 +1107,7 @@ void CellBuffer::PerformUndoStep() {
 		}
 		BasicDeleteChars(actionStep.position, actionStep.lenData);
 	} else if (actionStep.at == ActionType::remove) {
-		BasicInsertString(actionStep.position, actionStep.data.get(), actionStep.lenData);
+		BasicInsertString(actionStep.position, actionStep.data, actionStep.lenData);
 		if (changeHistory) {
 			changeHistory->UndoDeleteStep(actionStep.position, actionStep.lenData, uh->AfterDetachPoint());
 		}
@@ -1129,18 +1124,13 @@ int CellBuffer::StartRedo() noexcept {
 }
 
 Action CellBuffer::GetRedoStep() const noexcept {
-	const UndoAction &actionStep = uh->GetRedoStep();
-	Action acta {actionStep.at, actionStep.mayCoalesce, actionStep.position, nullptr, actionStep.lenData};
-	if (actionStep.lenData) {
-		acta.data = actionStep.data.get();
-	}
-	return acta;
+	return uh->GetRedoStep();
 }
 
 void CellBuffer::PerformRedoStep() {
-	const UndoAction &actionStep = uh->GetRedoStep();
+	Action actionStep = uh->GetRedoStep();
 	if (actionStep.at == ActionType::insert) {
-		BasicInsertString(actionStep.position, actionStep.data.get(), actionStep.lenData);
+		BasicInsertString(actionStep.position, actionStep.data, actionStep.lenData);
 		if (changeHistory) {
 			changeHistory->Insert(actionStep.position, actionStep.lenData, collectingUndo,
 				uh->BeforeSavePoint() && !uh->AfterDetachPoint());
diff --git a/src/UndoHistory.cxx b/src/UndoHistory.cxx
index d667c9b4d..bc1a4d36a 100644
--- a/src/UndoHistory.cxx
+++ b/src/UndoHistory.cxx
@@ -38,23 +38,50 @@ namespace Scintilla::Internal {
 
 UndoAction::UndoAction() noexcept = default;
 
-void UndoAction::Create(ActionType at_, Sci::Position position_, const char *data_, Sci::Position lenData_, bool mayCoalesce_) {
+void UndoAction::Create(ActionType at_, Sci::Position position_, Sci::Position lenData_, bool mayCoalesce_) noexcept {
 	position = position_;
 	at = at_;
 	mayCoalesce = mayCoalesce_;
 	lenData = lenData_;
-	data = nullptr;
-	if (lenData_) {
-		data = std::make_unique<char[]>(lenData_);
-		memcpy(&data[0], data_, lenData_);
-	}
 }
 
 void UndoAction::Clear() noexcept {
-	data = nullptr;
 	lenData = 0;
 }
 
+const char *ScrapStack::Push(const char *text, size_t length) {
+	if (current < stack.length()) {
+		stack.resize(current);
+	}
+	stack.append(text, length);
+	current = stack.length();
+	return stack.data() + current - length;
+}
+
+void ScrapStack::SetCurrent(size_t position) noexcept {
+	current = position;
+}
+
+void ScrapStack::MoveForward(size_t length) noexcept {
+	if ((current + length) <= stack.length()) {
+		current += length;
+	}
+}
+
+void ScrapStack::MoveBack(size_t length) noexcept {
+	if (current >= length) {
+		current -= length;
+	}
+}
+
+const char *ScrapStack::CurrentText() const noexcept {
+	return stack.data() + current;
+}
+
+const char *ScrapStack::TextAt(size_t position) const noexcept {
+	return stack.data() + position;
+}
+
 // The undo history stores a sequence of user operations that represent the user's view of the
 // commands executed on the text.
 // Each user operation contains a sequence of text insertion and text deletion actions.
@@ -81,10 +108,13 @@ UndoHistory::UndoHistory() {
 	undoSequenceDepth = 0;
 	savePoint = 0;
 	tentativePoint = -1;
+	scraps = std::make_unique<ScrapStack>();
 
 	actions[currentAction].Create(ActionType::start);
 }
 
+UndoHistory::~UndoHistory() noexcept = default;
+
 void UndoHistory::EnsureUndoRoom() {
 	// Have to test that there is room for 2 more actions in the array
 	// as two actions may be created by the calling function
@@ -163,12 +193,12 @@ const char *UndoHistory::AppendAction(ActionType at, Sci::Position position, con
 		currentAction++;
 	}
 	startSequence = oldCurrentAction != currentAction;
-	const int actionWithData = currentAction;
-	actions[currentAction].Create(at, position, data, lengthData, mayCoalesce);
+	const char *dataNew = lengthData ? scraps->Push(data, lengthData) : nullptr;
+	actions[currentAction].Create(at, position, lengthData, mayCoalesce);
 	currentAction++;
 	actions[currentAction].Create(ActionType::start);
 	maxAction = currentAction;
-	return actions[actionWithData].data.get();
+	return dataNew;
 }
 
 void UndoHistory::BeginUndoAction() {
@@ -202,7 +232,7 @@ void UndoHistory::DropUndoSequence() noexcept {
 	undoSequenceDepth = 0;
 }
 
-void UndoHistory::DeleteUndoHistory() {
+void UndoHistory::DeleteUndoHistory() noexcept {
 	for (int i = 1; i < maxAction; i++)
 		actions[i].Clear();
 	maxAction = 0;
@@ -278,11 +308,17 @@ int UndoHistory::StartUndo() noexcept {
 	return currentAction - act;
 }
 
-const UndoAction &UndoHistory::GetUndoStep() const noexcept {
-	return actions[currentAction];
+Action UndoHistory::GetUndoStep() const noexcept {
+	const UndoAction &step = actions[currentAction];
+	Action acta {step.at, step.mayCoalesce, step.position, nullptr, step.lenData};
+	if (step.lenData) {
+		acta.data = scraps->CurrentText() - step.lenData;
+	}
+	return acta;
 }
 
 void UndoHistory::CompletedUndoStep() noexcept {
+	scraps->MoveBack(actions[currentAction].lenData);
 	currentAction--;
 }
 
@@ -303,11 +339,17 @@ int UndoHistory::StartRedo() noexcept {
 	return act - currentAction;
 }
 
-const UndoAction &UndoHistory::GetRedoStep() const noexcept {
-	return actions[currentAction];
+Action UndoHistory::GetRedoStep() const noexcept {
+	const UndoAction &step = actions[currentAction];
+	Action acta {step.at, step.mayCoalesce, step.position, nullptr, step.lenData};
+	if (step.lenData) {
+		acta.data = scraps->CurrentText();
+	}
+	return acta;
 }
 
 void UndoHistory::CompletedRedoStep() noexcept {
+	scraps->MoveForward(actions[currentAction].lenData);
 	currentAction++;
 }
 
diff --git a/src/UndoHistory.h b/src/UndoHistory.h
index 423b50a7f..98df93465 100644
--- a/src/UndoHistory.h
+++ b/src/UndoHistory.h
@@ -15,14 +15,25 @@ public:
 	ActionType at = ActionType::insert;
 	bool mayCoalesce = false;
 	Sci::Position position = 0;
-	std::unique_ptr<char[]> data;
 	Sci::Position lenData = 0;
 
 	UndoAction() noexcept;
-	void Create(ActionType at_, Sci::Position position_ = 0, const char *data_ = nullptr, Sci::Position lenData_ = 0, bool mayCoalesce_ = true);
+	void Create(ActionType at_, Sci::Position position_=0, Sci::Position lenData_=0, bool mayCoalesce_=true) noexcept;
 	void Clear() noexcept;
 };
 
+class ScrapStack {
+	std::string stack;
+	size_t current = 0;
+public:
+	const char *Push(const char *text, size_t length);
+	void SetCurrent(size_t position) noexcept;
+	void MoveForward(size_t length) noexcept;
+	void MoveBack(size_t length) noexcept;
+	[[nodiscard]] const char *CurrentText() const noexcept;
+	[[nodiscard]] const char *TextAt(size_t position) const noexcept;
+};
+
 /**
  *
  */
@@ -34,18 +45,20 @@ class UndoHistory {
 	int savePoint;
 	int tentativePoint;
 	std::optional<int> detach;
+	std::unique_ptr<ScrapStack> scraps;
 
 	void EnsureUndoRoom();
 
 public:
 	UndoHistory();
+	~UndoHistory() noexcept;
 
 	const char *AppendAction(ActionType at, Sci::Position position, const char *data, Sci::Position lengthData, bool &startSequence, bool mayCoalesce=true);
 
 	void BeginUndoAction();
 	void EndUndoAction();
 	void DropUndoSequence() noexcept;
-	void DeleteUndoHistory();
+	void DeleteUndoHistory() noexcept;
 
 	/// The save point is a marker in the undo stack where the container has stated that
 	/// the buffer was saved. Undo and redo can move over the save point.
@@ -66,11 +79,11 @@ public:
 	/// called that many times. Similarly for redo.
 	bool CanUndo() const noexcept;
 	int StartUndo() noexcept;
-	const UndoAction &GetUndoStep() const noexcept;
+	Action GetUndoStep() const noexcept;
 	void CompletedUndoStep() noexcept;
 	bool CanRedo() const noexcept;
 	int StartRedo() noexcept;
-	const UndoAction &GetRedoStep() const noexcept;
+	Action GetRedoStep() const noexcept;
 	void CompletedRedoStep() noexcept;
 };
 
diff --git a/test/unit/testCellBuffer.cxx b/test/unit/testCellBuffer.cxx
index 7fd2d3e7e..405bd520d 100644
--- a/test/unit/testCellBuffer.cxx
+++ b/test/unit/testCellBuffer.cxx
@@ -35,6 +35,25 @@ bool Equal(const char *ptr, std::string_view sv) noexcept {
 	return memcmp(ptr, sv.data(), sv.length()) == 0;
 }
 
+TEST_CASE("ScrapStack") {
+
+	ScrapStack ss;
+
+	SECTION("Push") {
+		ss.Push("abc", 3);
+		ss.MoveBack(3);
+		const char *text = ss.CurrentText();
+		REQUIRE(memcmp(text, "abc", 3) == 0);
+
+		ss.MoveForward(1);
+		const char *text2 = ss.CurrentText();
+		REQUIRE(memcmp(text2, "bc", 2) == 0);
+
+		const char *text3 = ss.TextAt(2);
+		REQUIRE(memcmp(text3, "c", 1) == 0);
+	}
+}
+
 TEST_CASE("CellBuffer") {
 
 	constexpr std::string_view sText = "Scintilla";
@@ -211,7 +230,7 @@ TEST_CASE("CellBuffer") {
 
 }
 
-bool Equal(const UndoAction &a, ActionType at, Sci::Position position, std::string_view value) noexcept {
+bool Equal(const Action &a, ActionType at, Sci::Position position, std::string_view value) noexcept {
 	// Currently ignores mayCoalesce since this is not set consistently when following
 	// start action implies it.
 	if (a.at != at)
@@ -220,12 +239,12 @@ bool Equal(const UndoAction &a, ActionType at, Sci::Position position, std::stri
 		return false;
 	if (a.lenData != static_cast<Sci::Position>(value.length()))
 		return false;
-	if (memcmp(a.data.get(), value.data(), a.lenData) != 0)
+	if (memcmp(a.data, value.data(), a.lenData) != 0)
 		return false;
 	return true;
 }
 
-bool EqualContainerAction(const UndoAction &a, Sci::Position token) noexcept {
+bool EqualContainerAction(const Action &a, Sci::Position token) noexcept {
 	// Currently ignores mayCoalesce
 	if (a.at != ActionType::container)
 		return false;
@@ -275,14 +294,14 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartUndo();
 			REQUIRE(steps == 1);
-			const UndoAction &action = uh.GetUndoStep();
+			const Action action = uh.GetUndoStep();
 			REQUIRE(Equal(action, ActionType::remove, 0, "ab"));
 			uh.CompletedUndoStep();
 		}
 		{
 			const int steps = uh.StartUndo();
 			REQUIRE(steps == 1);
-			const UndoAction &action = uh.GetUndoStep();
+			const Action action = uh.GetUndoStep();
 			REQUIRE(Equal(action, ActionType::insert, 0, "ab"));
 			uh.CompletedUndoStep();
 		}
@@ -293,14 +312,14 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartRedo();
 			REQUIRE(steps == 1);
-			const UndoAction &action = uh.GetRedoStep();
+			const Action action = uh.GetRedoStep();
 			REQUIRE(Equal(action, ActionType::insert, 0, "ab"));
 			uh.CompletedRedoStep();
 		}
 		{
 			const int steps = uh.StartRedo();
 			REQUIRE(steps == 1);
-			const UndoAction &action = uh.GetRedoStep();
+			const Action action = uh.GetRedoStep();
 			REQUIRE(Equal(action, ActionType::remove, 0, "ab"));
 			uh.CompletedRedoStep();
 		}
@@ -326,10 +345,10 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartUndo();
 			REQUIRE(steps == 2);
-			const UndoAction &action2 = uh.GetUndoStep();
+			const Action action2 = uh.GetUndoStep();
 			REQUIRE(Equal(action2, ActionType::insert, 2, "cd"));
 			uh.CompletedUndoStep();
-			const UndoAction &action1 = uh.GetUndoStep();
+			const Action action1 = uh.GetUndoStep();
 			REQUIRE(Equal(action1, ActionType::insert, 0, "ab"));
 			uh.CompletedUndoStep();
 		}
@@ -340,10 +359,10 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartRedo();
 			REQUIRE(steps == 2);
-			const UndoAction &action1 = uh.GetRedoStep();
+			const Action action1 = uh.GetRedoStep();
 			REQUIRE(Equal(action1, ActionType::insert, 0, "ab"));
 			uh.CompletedRedoStep();
-			const UndoAction &action2 = uh.GetRedoStep();
+			const Action action2 = uh.GetRedoStep();
 			REQUIRE(Equal(action2, ActionType::insert, 2, "cd"));
 			uh.CompletedRedoStep();
 		}
@@ -384,7 +403,7 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartUndo();
 			REQUIRE(steps == 1);
-			const UndoAction &actionContainer = uh.GetUndoStep();
+			const Action actionContainer = uh.GetUndoStep();
 			REQUIRE(EqualContainerAction(actionContainer, 1002));
 			REQUIRE(actionContainer.mayCoalesce == false);
 			uh.CompletedUndoStep();
@@ -392,21 +411,21 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartUndo();
 			REQUIRE(steps == 4);
-			const UndoAction &actionInsert = uh.GetUndoStep();
+			const Action actionInsert = uh.GetUndoStep();
 			REQUIRE(Equal(actionInsert, ActionType::insert, 2, "cd"));
 			uh.CompletedUndoStep();
 			{
-				const UndoAction &actionContainer = uh.GetUndoStep();
+				const Action actionContainer = uh.GetUndoStep();
 				REQUIRE(EqualContainerAction(actionContainer, 1001));
 				uh.CompletedUndoStep();
 			}
 			{
-				const UndoAction &actionContainer = uh.GetUndoStep();
+				const Action actionContainer = uh.GetUndoStep();
 				REQUIRE(EqualContainerAction(actionContainer, 1000));
 				uh.CompletedUndoStep();
 			}
 			{
-				const UndoAction &actionInsert1 = uh.GetUndoStep();
+				const Action actionInsert1 = uh.GetUndoStep();
 				REQUIRE(Equal(actionInsert1, ActionType::insert, 0, "ab"));
 				uh.CompletedUndoStep();
 			}
@@ -440,13 +459,13 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartUndo();
 			REQUIRE(steps == 3);
-			const UndoAction &action3 = uh.GetUndoStep();
+			const Action action3 = uh.GetUndoStep();
 			REQUIRE(Equal(action3, ActionType::insert, 0, "cde"));
 			uh.CompletedUndoStep();
-			const UndoAction &action2 = uh.GetUndoStep();
+			const Action action2 = uh.GetUndoStep();
 			REQUIRE(Equal(action2, ActionType::remove, 0, "ab"));
 			uh.CompletedUndoStep();
-			const UndoAction &action1 = uh.GetUndoStep();
+			const Action action1 = uh.GetUndoStep();
 			REQUIRE(Equal(action1, ActionType::insert, 0, "ab"));
 			uh.CompletedUndoStep();
 		}
@@ -457,13 +476,13 @@ TEST_CASE("UndoHistory") {
 		{
 			const int steps = uh.StartRedo();
 			REQUIRE(steps == 3);
-			const UndoAction &action1 = uh.GetRedoStep();
+			const Action action1 = uh.GetRedoStep();
 			REQUIRE(Equal(action1, ActionType::insert, 0, "ab"));
 			uh.CompletedRedoStep();
-			const UndoAction &action2 = uh.GetRedoStep();
+			const Action action2 = uh.GetRedoStep();
 			REQUIRE(Equal(action2, ActionType::remove, 0, "ab"));
 			uh.CompletedRedoStep();
-			const UndoAction &action3 = uh.GetRedoStep();
+			const Action action3 = uh.GetRedoStep();
 			REQUIRE(Equal(action3, ActionType::insert, 0, "cde"));
 			uh.CompletedRedoStep();
 		}