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.

3 files changed, 81 insertions, 36 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;
 };