Added change history which can display document changes (modified, saved, ...)

in the margin or in the text.

12 files changed, 790 insertions, 4 deletions

diff --git a/src/CellBuffer.cxx b/src/CellBuffer.cxx
index 2a3aed146..be018bbd6 100644
--- a/src/CellBuffer.cxx
+++ b/src/CellBuffer.cxx
@@ -27,6 +27,9 @@
 #include "Position.h"
 #include "SplitVector.h"
 #include "Partitioning.h"
+#include "RunStyles.h"
+#include "SparseVector.h"
+#include "ChangeHistory.h"
 #include "CellBuffer.h"
 #include "UniConversion.h"
 
@@ -396,6 +399,11 @@ const char *UndoHistory::AppendAction(ActionType at, Sci::Position position, con
 	//	actions[currentAction - 1].position, actions[currentAction - 1].lenData);
 	if (currentAction < savePoint) {
 		savePoint = -1;
+		if (!detach) {
+			detach = currentAction;
+		}
+	} else if (detach && (*detach > currentAction)) {
+		detach = currentAction;
 	}
 	int oldCurrentAction = currentAction;
 	if (currentAction >= 1) {
@@ -503,12 +511,29 @@ void UndoHistory::DeleteUndoHistory() {
 
 void UndoHistory::SetSavePoint() noexcept {
 	savePoint = currentAction;
+	detach.reset();
 }
 
 bool UndoHistory::IsSavePoint() const noexcept {
 	return savePoint == currentAction;
 }
 
+bool UndoHistory::BeforeSavePoint() const noexcept {
+	return (savePoint < 0) || (savePoint > currentAction);
+}
+
+bool UndoHistory::BeforeReachableSavePoint() const noexcept {
+	return (savePoint >= 0) && !detach && (savePoint > currentAction);
+}
+
+bool UndoHistory::AfterSavePoint() const noexcept {
+	return (savePoint >= 0) && (savePoint <= currentAction);
+}
+
+bool UndoHistory::AfterDetachPoint() const noexcept {
+	return detach && (*detach < currentAction);
+}
+
 void UndoHistory::TentativeStart() {
 	tentativePoint = currentAction;
 }
@@ -682,6 +707,9 @@ const char *CellBuffer::InsertString(Sci::Position position, const char *s, Sci:
 		}
 
 		BasicInsertString(position, s, insertLength);
+		if (changeHistory) {
+			changeHistory->Insert(position, insertLength, collectingUndo, uh.BeforeReachableSavePoint());
+		}
 	}
 	return data;
 }
@@ -730,6 +758,11 @@ const char *CellBuffer::DeleteChars(Sci::Position position, Sci::Position delete
 			data = uh.AppendAction(ActionType::remove, position, data, deleteLength, startSequence);
 		}
 
+		if (changeHistory) {
+			changeHistory->DeleteRangeSavingHistory(position, deleteLength,
+				uh.BeforeReachableSavePoint(), uh.AfterDetachPoint());
+		}
+
 		BasicDeleteChars(position, deleteLength);
 	}
 	return data;
@@ -845,6 +878,9 @@ bool CellBuffer::HasStyles() const noexcept {
 
 void CellBuffer::SetSavePoint() {
 	uh.SetSavePoint();
+	if (changeHistory) {
+		changeHistory->SetSavePoint();
+	}
 }
 
 bool CellBuffer::IsSavePoint() const noexcept {
@@ -1304,14 +1340,24 @@ const Action &CellBuffer::GetUndoStep() const {
 
 void CellBuffer::PerformUndoStep() {
 	const Action &actionStep = uh.GetUndoStep();
+	if (changeHistory && uh.BeforeSavePoint()) {
+		changeHistory->StartReversion();
+	}
 	if (actionStep.at == ActionType::insert) {
 		if (substance.Length() < actionStep.lenData) {
 			throw std::runtime_error(
 				"CellBuffer::PerformUndoStep: deletion must be less than document length.");
 		}
+		if (changeHistory) {
+			changeHistory->DeleteRange(actionStep.position, actionStep.lenData,
+				uh.BeforeSavePoint() && !uh.AfterDetachPoint());
+		}
 		BasicDeleteChars(actionStep.position, actionStep.lenData);
 	} else if (actionStep.at == ActionType::remove) {
 		BasicInsertString(actionStep.position, actionStep.data.get(), actionStep.lenData);
+		if (changeHistory) {
+			changeHistory->UndoDeleteStep(actionStep.position, actionStep.lenData, uh.AfterDetachPoint());
+		}
 	}
 	uh.CompletedUndoStep();
 }
@@ -1332,9 +1378,57 @@ void CellBuffer::PerformRedoStep() {
 	const Action &actionStep = uh.GetRedoStep();
 	if (actionStep.at == ActionType::insert) {
 		BasicInsertString(actionStep.position, actionStep.data.get(), actionStep.lenData);
+		if (changeHistory) {
+			changeHistory->Insert(actionStep.position, actionStep.lenData, collectingUndo,
+				uh.BeforeSavePoint() && !uh.AfterDetachPoint());
+		}
 	} else if (actionStep.at == ActionType::remove) {
+		if (changeHistory) {
+			changeHistory->DeleteRangeSavingHistory(actionStep.position, actionStep.lenData,
+				uh.BeforeReachableSavePoint(), uh.AfterDetachPoint());
+		}
 		BasicDeleteChars(actionStep.position, actionStep.lenData);
 	}
+	if (changeHistory && uh.AfterSavePoint()) {
+		changeHistory->EndReversion();
+	}
 	uh.CompletedRedoStep();
 }
 
+void CellBuffer::ChangeHistorySet(bool set) {
+	if (set) {
+		if (!changeHistory) {
+			changeHistory = std::make_unique<ChangeHistory>(Length());
+		}
+	} else {
+		changeHistory.reset();
+	}
+}
+
+int CellBuffer::EditionAt(Sci::Position pos) const noexcept {
+	if (changeHistory) {
+		return changeHistory->EditionAt(pos);
+	}
+	return 0;
+}
+
+Sci::Position CellBuffer::EditionEndRun(Sci::Position pos) const noexcept {
+	if (changeHistory) {
+		return changeHistory->EditionEndRun(pos);
+	}
+	return Length();
+}
+
+unsigned int CellBuffer::EditionDeletesAt(Sci::Position pos) const noexcept {
+	if (changeHistory) {
+		return changeHistory->EditionDeletesAt(pos);
+	}
+	return 0;
+}
+
+Sci::Position CellBuffer::EditionNextDelete(Sci::Position pos) const noexcept {
+	if (changeHistory) {
+		return changeHistory->EditionNextDelete(pos);
+	}
+	return Length() + 1;
+}
diff --git a/src/CellBuffer.h b/src/CellBuffer.h
index 727e14944..7f0b87c4d 100644
--- a/src/CellBuffer.h
+++ b/src/CellBuffer.h
@@ -20,6 +20,7 @@ public:
 	virtual void RemoveLine(Sci::Line line)=0;
 };
 
+class ChangeHistory;
 /**
  * The line vector contains information about each of the lines in a cell buffer.
  */
@@ -53,6 +54,7 @@ class UndoHistory {
 	int undoSequenceDepth;
 	int savePoint;
 	int tentativePoint;
+	std::optional<int> detach;
 
 	void EnsureUndoRoom();
 
@@ -70,6 +72,10 @@ public:
 	/// the buffer was saved. Undo and redo can move over the save point.
 	void SetSavePoint() noexcept;
 	bool IsSavePoint() const noexcept;
+	bool BeforeSavePoint() const noexcept;
+	bool BeforeReachableSavePoint() const noexcept;
+	bool AfterSavePoint() const noexcept;
+	bool AfterDetachPoint() const noexcept;
 
 	// Tentative actions are used for input composition so that it can be undone cleanly
 	void TentativeStart();
@@ -133,6 +139,8 @@ private:
 	bool collectingUndo;
 	UndoHistory uh;
 
+	std::unique_ptr<ChangeHistory> changeHistory;
+
 	std::unique_ptr<ILineVector> plv;
 
 	bool UTF8LineEndOverlaps(Sci::Position position) const noexcept;
@@ -224,6 +232,12 @@ public:
 	int StartRedo();
 	const Action &GetRedoStep() const;
 	void PerformRedoStep();
+
+	void ChangeHistorySet(bool set);
+	[[nodiscard]] int EditionAt(Sci::Position pos) const noexcept;
+	[[nodiscard]] Sci::Position EditionEndRun(Sci::Position pos) const noexcept;
+	[[nodiscard]] unsigned int EditionDeletesAt(Sci::Position pos) const noexcept;
+	[[nodiscard]] Sci::Position EditionNextDelete(Sci::Position pos) const noexcept;
 };
 
 }
diff --git a/src/ChangeHistory.cxx b/src/ChangeHistory.cxx
new file mode 100644
index 000000000..4c771a93c
--- /dev/null
+++ b/src/ChangeHistory.cxx
@@ -0,0 +1,422 @@
+// Scintilla source code edit control
+/** @file ChangeHistory.cxx
+ ** Manages a history of changes in a document.
+ **/
+// Copyright 2022 by Neil Hodgson <neilh@scintilla.org>
+// The License.txt file describes the conditions under which this software may be distributed.
+
+#include <cstddef>
+#include <cstdlib>
+#include <cassert>
+
+#include <stdexcept>
+#include <vector>
+#include <set>
+#include <algorithm>
+#include <memory>
+
+#include "ScintillaTypes.h"
+
+#include "Debugging.h"
+
+#include "Position.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
+#include "RunStyles.h"
+#include "SparseVector.h"
+#include "ChangeHistory.h"
+
+namespace Scintilla::Internal {
+
+void ChangeStack::Clear() noexcept {
+	steps.clear();
+	insertions.clear();
+}
+
+void ChangeStack::AddStep() {
+	steps.push_back(0);
+}
+
+void ChangeStack::PushDeletion(Sci::Position positionDeletion, int edition) {
+	steps.back()++;
+	insertions.push_back({ positionDeletion, 0, edition, InsertionSpan::Direction::deletion });
+}
+
+void ChangeStack::PushInsertion(Sci::Position positionInsertion, Sci::Position length, int edition) {
+	steps.back()++;
+	insertions.push_back({ positionInsertion, length, edition, InsertionSpan::Direction::insertion });
+};
+
+size_t ChangeStack::PopStep() noexcept {
+	const size_t spans = steps.back();
+	steps.pop_back();
+	return spans;
+}
+
+InsertionSpan ChangeStack::PopSpan() noexcept {
+	const InsertionSpan span = insertions.back();
+	insertions.pop_back();
+	return span;
+}
+
+void ChangeStack::SetSavePoint() noexcept {
+	// Switch changeUnsaved to changeSaved
+	for (InsertionSpan &x : insertions) {
+		if (x.edition == changeModified) {
+			x.edition = changeSaved;
+		}
+	}
+}
+
+void ChangeLog::Clear(Sci::Position length) {
+	changeStack.Clear();
+	insertEdition.DeleteAll();
+	deleteEdition.DeleteAll();
+	InsertSpace(0, length);
+}
+
+void ChangeLog::InsertSpace(Sci::Position position, Sci::Position insertLength) {
+	assert(insertEdition.Length() == deleteEdition.Length());
+	insertEdition.InsertSpace(position, insertLength);
+	deleteEdition.InsertSpace(position, insertLength);
+}
+
+void ChangeLog::DeleteRange(Sci::Position position, Sci::Position deleteLength) {
+	insertEdition.DeleteRange(position, deleteLength);
+	const EditionSetOwned &editions = deleteEdition.ValueAt(position);
+	if (editions) {
+		const EditionSet savedEditions = *editions;
+		deleteEdition.DeleteRange(position, deleteLength);
+		EditionSetOwned reset = std::make_unique<EditionSet>(savedEditions);
+		deleteEdition.SetValueAt(position, std::move(reset));
+	} else {
+		deleteEdition.DeleteRange(position, deleteLength);
+	}
+	assert(insertEdition.Length() == deleteEdition.Length());
+}
+
+void ChangeLog::Insert(Sci::Position start, Sci::Position length, int edition) {
+	insertEdition.FillRange(start, edition, length);
+}
+
+void ChangeLog::CollapseRange(Sci::Position position, Sci::Position deleteLength) {
+	const Sci::Position positionMax = position + deleteLength;
+	Sci::Position positionDeletion = position + 1;
+	while (positionDeletion <= positionMax) {
+		const EditionSetOwned &editions = deleteEdition.ValueAt(positionDeletion);
+		if (editions) {
+			for (const int ed : *editions) {
+				PushDeletionAt(position, ed);
+			}
+			EditionSetOwned empty;
+			deleteEdition.SetValueAt(positionDeletion, std::move(empty));
+		}
+		positionDeletion = deleteEdition.PositionNext(positionDeletion);
+	}
+}
+
+void ChangeLog::PushDeletionAt(Sci::Position position, int edition) {
+	if (!deleteEdition.ValueAt(position)) {
+		deleteEdition.SetValueAt(position, std::make_unique<EditionSet>());
+	}
+	deleteEdition.ValueAt(position)->push_back(edition);
+}
+
+void ChangeLog::InsertFrontDeletionAt(Sci::Position position, int edition) {
+	if (!deleteEdition.ValueAt(position)) {
+		deleteEdition.SetValueAt(position, std::make_unique<EditionSet>());
+	}
+	const EditionSetOwned &editions = deleteEdition.ValueAt(position);
+	editions->insert(editions->begin(), edition);
+}
+
+void ChangeLog::SaveRange(Sci::Position position, Sci::Position length) {
+	// Save insertEdition range into undo stack
+	changeStack.AddStep();
+	Sci::Position positionInsertion = position;
+	const ptrdiff_t editionStart = insertEdition.ValueAt(positionInsertion);
+	if (editionStart == 0) {
+		positionInsertion = insertEdition.EndRun(positionInsertion);
+	}
+	const Sci::Position positionMax = position + length;
+	while (positionInsertion < positionMax) {
+		const Sci::Position positionEndInsertion = insertEdition.EndRun(positionInsertion);
+		changeStack.PushInsertion(positionInsertion, std::min(positionEndInsertion, positionMax) - positionInsertion,
+			insertEdition.ValueAt(positionInsertion));
+		positionInsertion = insertEdition.EndRun(positionEndInsertion);
+	}
+	Sci::Position positionDeletion = position + 1;
+	while (positionDeletion <= positionMax) {
+		const EditionSetOwned &editions = deleteEdition.ValueAt(positionDeletion);
+		if (editions) {
+			for (const int ed : *editions) {
+				changeStack.PushDeletion(positionDeletion, ed);
+			}
+		}
+		positionDeletion = deleteEdition.PositionNext(positionDeletion);
+	}
+}
+
+void ChangeLog::PopDeletion(Sci::Position position, Sci::Position deleteLength) {
+	// Just performed InsertSpace(position, deleteLength) so *this* element in
+	// deleteEdition moved forward by deleteLength
+	EditionSetOwned eso = deleteEdition.Extract(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 InsertionSpan span = changeStack.PopSpan();
+		if (span.direction == InsertionSpan::Direction::insertion) {
+			insertEdition.FillRange(span.start, span.edition, span.length);
+		} else {
+			assert(editions);
+			assert(editions->back() == span.edition);
+			editions->pop_back();
+			InsertFrontDeletionAt(span.start, span.edition);
+		}
+	}
+
+	if (editions->empty()) {
+		deleteEdition.SetValueAt(position, EditionSetOwned{});
+	}
+}
+
+void ChangeLog::SaveHistoryForDelete(Sci::Position position, Sci::Position deleteLength) {
+	assert(position >= 0);
+	assert(deleteLength >= 0);
+	assert(position + deleteLength <= Length());
+	SaveRange(position, deleteLength);
+	CollapseRange(position, deleteLength);
+}
+
+void ChangeLog::DeleteRangeSavingHistory(Sci::Position position, Sci::Position deleteLength) {
+	SaveHistoryForDelete(position, deleteLength);
+	DeleteRange(position, deleteLength);
+}
+
+void ChangeLog::SetSavePoint() {
+	// Switch changeUnsaved to changeSaved
+	changeStack.SetSavePoint();
+
+	const Sci::Position length = insertEdition.Length();
+
+	for (Sci::Position startRun = 0; startRun < length;) {
+		const Sci::Position endRun = insertEdition.EndRun(startRun);
+		if (insertEdition.ValueAt(startRun) == changeModified) {
+			insertEdition.FillRange(startRun, changeSaved, endRun - startRun);
+		}
+		startRun = endRun;
+	}
+	
+	for (Sci::Position positionDeletion = 0; positionDeletion <= length;) {
+		const EditionSetOwned &editions = deleteEdition.ValueAt(positionDeletion);
+		if (editions) {
+			for (int &ed : *editions) {
+				if (ed == changeModified) {
+					ed = changeSaved;
+				}
+			}
+		}
+		positionDeletion = deleteEdition.PositionNext(positionDeletion);
+	}
+}
+
+Sci::Position ChangeLog::Length() const noexcept {
+	return insertEdition.Length();
+}
+
+size_t ChangeLog::DeletionCount(Sci::Position start, Sci::Position length) const noexcept {
+	const Sci::Position end = start + length;
+	size_t count = 0;
+	while (start <= end) {
+		const EditionSetOwned &editions = deleteEdition.ValueAt(start);
+		if (editions) {
+			count += editions->size();
+		}
+		start = deleteEdition.PositionNext(start);
+	}
+	return count;
+}
+
+void ChangeLog::Check() const noexcept {
+	assert(insertEdition.Length() == deleteEdition.Length());
+}
+
+ChangeHistory::ChangeHistory(Sci::Position length) {
+	changeLog.Clear(length);
+}
+
+void ChangeHistory::Insert(Sci::Position position, Sci::Position insertLength, bool collectingUndo, bool beforeSave) {
+	Check();
+	changeLog.InsertSpace(position, insertLength);
+	const int edition = collectingUndo ? (beforeSave ? changeSaved : changeModified) :
+		changeOriginal;
+	changeLog.Insert(position, insertLength, edition);
+	if (changeLogReversions) {
+		changeLogReversions->InsertSpace(position, insertLength);
+		if (beforeSave) {
+			changeLogReversions->PopDeletion(position, insertLength);
+		}
+	}
+	Check();
+}
+
+void ChangeHistory::DeleteRange(Sci::Position position, Sci::Position deleteLength, bool reverting) {
+	Check();
+	assert(DeletionCount(position, deleteLength-1) == 0);
+	changeLog.DeleteRange(position, deleteLength);
+	if (changeLogReversions) {
+		changeLogReversions->DeleteRangeSavingHistory(position, deleteLength);
+		if (reverting) {
+			changeLogReversions->PushDeletionAt(position, 1);
+		}
+	}
+	Check();
+}
+
+void ChangeHistory::DeleteRangeSavingHistory(Sci::Position position, Sci::Position deleteLength, bool beforeSave, bool isDetached) {
+	changeLog.DeleteRangeSavingHistory(position, deleteLength);
+	changeLog.PushDeletionAt(position, beforeSave ? changeSaved : changeModified);
+	if (changeLogReversions) {
+		if (isDetached) {
+			changeLogReversions->SaveHistoryForDelete(position, deleteLength);
+		}
+		changeLogReversions->DeleteRange(position, deleteLength);
+	}
+	Check();
+}
+
+void ChangeHistory::StartReversion() {
+	if (!changeLogReversions) {
+		changeLogReversions = std::make_unique<ChangeLog>();
+		changeLogReversions->Clear(changeLog.Length());
+	}
+	Check();
+}
+
+void ChangeHistory::EndReversion() noexcept {
+	changeLogReversions.reset();
+	Check();
+}
+
+void ChangeHistory::SetSavePoint() {
+	changeLog.SetSavePoint();
+	EndReversion();
+}
+
+void ChangeHistory::UndoDeleteStep(Sci::Position position, Sci::Position deleteLength, bool isDetached) {
+	Check();
+	changeLog.InsertSpace(position, deleteLength);
+	changeLog.PopDeletion(position, deleteLength);
+	if (changeLogReversions) {
+		changeLogReversions->InsertSpace(position, deleteLength);
+		if (!isDetached) {
+			changeLogReversions->Insert(position, deleteLength, 1);
+		}
+	}
+	Check();
+}
+
+Sci::Position ChangeHistory::Length() const noexcept {
+	return changeLog.Length();
+}
+
+void ChangeHistory::SetEpoch(int epoch) noexcept {
+	historicEpoch = epoch;
+}
+
+void ChangeHistory::EditionCreateHistory(Sci::Position start, Sci::Position length) {
+	if (start <= changeLog.Length()) {
+		if (length) {
+			changeLog.insertEdition.FillRange(start, historicEpoch, length);
+		} else {
+			changeLog.PushDeletionAt(start, historicEpoch);
+		}
+	}
+}
+
+// Editions:
+// <0 History
+// 0 Original unchanged
+// 1 Reverted to origin
+// 2 Saved
+// 3 Unsaved
+// 4 Reverted to change
+int ChangeHistory::EditionAt(Sci::Position pos) const noexcept {
+	const int edition = changeLog.insertEdition.ValueAt(pos);
+	if (changeLogReversions) {
+		const int editionReversion = changeLogReversions->insertEdition.ValueAt(pos);
+		if (editionReversion) {
+			if (edition < 0)
+				return 1;
+			return edition ? 4 : 1;
+		}
+	}
+	return edition;
+}
+
+Sci::Position ChangeHistory::EditionEndRun(Sci::Position pos) const noexcept {
+	if (changeLogReversions) {
+		assert(changeLogReversions->Length() == changeLog.Length());
+		const Sci::Position nextReversion = changeLogReversions->insertEdition.EndRun(pos);
+		const Sci::Position next = changeLog.insertEdition.EndRun(pos);
+		return std::min(next, nextReversion);
+	}
+	return changeLog.insertEdition.EndRun(pos);
+}
+
+// Produce a 4-bit value from the deletions at a position
+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));
+		}
+	}
+	if (changeLogReversions) {
+		const EditionSetOwned &editionSetReversions = changeLogReversions->deleteEdition.ValueAt(pos);
+		if (editionSetReversions) {
+			// If there is no saved or modified -> revertedToOrigin
+			if (!(editionSet & (bitSaved | bitModified))) {
+				editionSet = editionSet | bitRevertedToOriginal;
+			} else {
+				editionSet = editionSet | bitRevertedToModified;
+			}
+		}
+	}
+	return editionSet;
+}
+
+Sci::Position ChangeHistory::EditionNextDelete(Sci::Position pos) const noexcept {
+	const Sci::Position next = changeLog.deleteEdition.PositionNext(pos);
+	if (changeLogReversions) {
+		const Sci::Position nextReversion = changeLogReversions->deleteEdition.PositionNext(pos);
+		return std::min(next, nextReversion);
+	}
+	return next;
+}
+
+size_t ChangeHistory::DeletionCount(Sci::Position start, Sci::Position length) const noexcept {
+	return changeLog.DeletionCount(start, length);
+}
+
+EditionSet ChangeHistory::DeletionsAt(Sci::Position pos) const {
+	const EditionSetOwned &editions = changeLog.deleteEdition.ValueAt(pos);
+	if (editions) {
+		return *editions;
+	}
+	return {};
+}
+
+void ChangeHistory::Check() noexcept {
+	changeLog.Check();
+	if (changeLogReversions) {
+		changeLogReversions->Check();
+		assert(changeLogReversions->Length() == changeLog.Length());
+	}
+}
+
+}
diff --git a/src/ChangeHistory.h b/src/ChangeHistory.h
new file mode 100644
index 000000000..8a6e745dc
--- /dev/null
+++ b/src/ChangeHistory.h
@@ -0,0 +1,112 @@
+// Scintilla source code edit control
+/** @file ChangeHistory.h
+ ** Manages a history of changes in a document.
+ **/
+// Copyright 2022 by Neil Hodgson <neilh@scintilla.org>
+// The License.txt file describes the conditions under which this software may be distributed.
+
+#ifndef CHANGEHISTORY_H
+#define CHANGEHISTORY_H
+
+namespace Scintilla::Internal {
+
+constexpr int changeOriginal = 0;
+constexpr int changeRevertedOriginal = 1;
+constexpr int changeSaved = 2;
+constexpr int changeModified = 3;
+constexpr int changeRevertedToChange = 4;
+
+// As bit flags
+constexpr unsigned int bitRevertedToOriginal = 1;
+constexpr unsigned int bitSaved = 2;
+constexpr unsigned int bitModified = 4;
+constexpr unsigned int bitRevertedToModified = 8;
+
+struct InsertionSpan {
+	Sci::Position start;
+	Sci::Position length;
+	int edition;
+	enum class Direction { insertion, deletion } direction;
+};
+
+using EditionSet = std::vector<int>;
+using EditionSetOwned = std::unique_ptr<EditionSet>;
+
+class ChangeStack {
+	std::vector<size_t> steps;
+	std::vector<InsertionSpan> insertions;
+public:
+	void Clear() noexcept;
+	void AddStep();
+	void PushDeletion(Sci::Position positionDeletion, int edition);
+	void PushInsertion(Sci::Position positionInsertion, Sci::Position length, int edition);
+	[[nodiscard]] size_t PopStep() noexcept;
+	[[nodiscard]] InsertionSpan PopSpan() noexcept;
+	void SetSavePoint() noexcept;
+};
+
+struct ChangeLog {
+	ChangeStack changeStack;
+	RunStyles<Sci::Position, int> insertEdition;
+	SparseVector<EditionSetOwned> deleteEdition;
+
+	void Clear(Sci::Position length);
+	void InsertSpace(Sci::Position position, Sci::Position insertLength);
+	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 SaveRange(Sci::Position position, Sci::Position length);
+	void PopDeletion(Sci::Position position, Sci::Position deleteLength);
+	void SaveHistoryForDelete(Sci::Position position, Sci::Position deleteLength);
+	void DeleteRangeSavingHistory(Sci::Position position, Sci::Position deleteLength);
+	void SetSavePoint();
+
+	Sci::Position Length() const noexcept;
+	[[nodiscard]] size_t DeletionCount(Sci::Position start, Sci::Position length) const noexcept;
+	void Check() const noexcept;
+};
+
+enum class ReversionState { clear, reverting, detached };
+
+class ChangeHistory {
+	ChangeLog changeLog;
+	std::unique_ptr<ChangeLog> changeLogReversions;
+	int historicEpoch = -1;
+
+public:
+	ChangeHistory(Sci::Position length=0);
+
+	void Insert(Sci::Position position, Sci::Position insertLength, bool collectingUndo, bool beforeSave);
+	void DeleteRange(Sci::Position position, Sci::Position deleteLength, bool reverting);
+	void DeleteRangeSavingHistory(Sci::Position position, Sci::Position deleteLength, bool beforeSave, bool isDetached);
+
+	void StartReversion();
+	void EndReversion() noexcept;
+
+	void SetSavePoint();
+
+	void UndoDeleteStep(Sci::Position position, Sci::Position deleteLength, bool isDetached);
+
+	[[nodiscard]] Sci::Position Length() const noexcept;
+
+	// Setting up history before this session
+	void SetEpoch(int epoch) noexcept;
+	void EditionCreateHistory(Sci::Position start, Sci::Position length);
+
+	// Queries for drawing
+	[[nodiscard]] int EditionAt(Sci::Position pos) const noexcept;
+	[[nodiscard]] Sci::Position EditionEndRun(Sci::Position pos) const noexcept;
+	[[nodiscard]] unsigned int EditionDeletesAt(Sci::Position pos) const noexcept;
+	[[nodiscard]] Sci::Position EditionNextDelete(Sci::Position pos) const noexcept;
+
+	// Testing - not used by Scintilla
+	[[nodiscard]] size_t DeletionCount(Sci::Position start, Sci::Position length) const noexcept;
+	EditionSet DeletionsAt(Sci::Position pos) const;
+	void Check() noexcept;
+};
+
+}
+
+#endif
diff --git a/src/Document.cxx b/src/Document.cxx
index 2312e3f5a..1c3015c92 100644
--- a/src/Document.cxx
+++ b/src/Document.cxx
@@ -339,8 +339,32 @@ void Document::TentativeUndo() {
 	}
 }
 
-int Document::GetMark(Sci::Line line) const noexcept {
-	return Markers()->MarkValue(line);
+int Document::GetMark(Sci::Line line, bool includeChangeHistory) const {
+	int marksHistory = 0;
+	if (includeChangeHistory) {
+		int marksEdition = 0;
+
+		const Sci::Position start = LineStart(line);
+		const Sci::Position lineNext = LineStart(line + 1);
+		for (Sci::Position position = start; position < lineNext;) {
+			const int edition = EditionAt(position);
+			if (edition) {
+				marksEdition |= 1 << (edition-1);
+			}
+			position = EditionEndRun(position);
+		}
+		const Sci::Position lineEnd = LineEnd(line);
+		for (Sci::Position position = start; position <= lineEnd;) {
+			marksEdition |= EditionDeletesAt(position);
+			position = EditionNextDelete(position);
+		}
+
+		/* Bits: RevertedToOrigin, Saved, Modified, RevertedToModified */
+		constexpr unsigned int editionShift = static_cast<unsigned int>(MarkerOutline::HistoryRevertedToOrigin);
+		marksHistory = marksEdition << editionShift;
+	}
+
+	return marksHistory | Markers()->MarkValue(line);
 }
 
 Sci::Line Document::MarkerNext(Sci::Line lineStart, int mask) const noexcept {
diff --git a/src/Document.h b/src/Document.h
index e406118a7..4bb7cde15 100644
--- a/src/Document.h
+++ b/src/Document.h
@@ -383,6 +383,12 @@ public:
 	void TentativeUndo();
 	bool TentativeActive() const noexcept { return cb.TentativeActive(); }
 
+	void ChangeHistorySet(bool set) { cb.ChangeHistorySet(set); };
+	[[nodiscard]] int EditionAt(Sci::Position pos) const noexcept { return cb.EditionAt(pos); };
+	[[nodiscard]] Sci::Position EditionEndRun(Sci::Position pos) const noexcept { return cb.EditionEndRun(pos); };
+	[[nodiscard]] unsigned int EditionDeletesAt(Sci::Position pos) const noexcept { return cb.EditionDeletesAt(pos); };
+	[[nodiscard]] Sci::Position EditionNextDelete(Sci::Position pos) const noexcept { return cb.EditionNextDelete(pos); };
+
 	const char * SCI_METHOD BufferPointer() override { return cb.BufferPointer(); }
 	const char *RangePointer(Sci::Position position, Sci::Position rangeLength) noexcept { return cb.RangePointer(position, rangeLength); }
 	Sci::Position GapPosition() const noexcept { return cb.GapPosition(); }
@@ -414,7 +420,7 @@ public:
 	void GetStyleRange(unsigned char *buffer, Sci::Position position, Sci::Position lengthRetrieve) const {
 		cb.GetStyleRange(buffer, position, lengthRetrieve);
 	}
-	int GetMark(Sci::Line line) const noexcept;
+	int GetMark(Sci::Line line, bool includeChangeHistory) const;
 	Sci::Line MarkerNext(Sci::Line lineStart, int mask) const noexcept;
 	int AddMark(Sci::Line line, int markerNum);
 	void AddMarkSet(Sci::Line line, int valueSet);
diff --git a/src/EditModel.cxx b/src/EditModel.cxx
index e8e5e5d1e..dd441322e 100644
--- a/src/EditModel.cxx
+++ b/src/EditModel.cxx
@@ -128,5 +128,5 @@ InSelection EditModel::LineEndInSelection(Sci::Line lineDoc) const {
 }
 
 int EditModel::GetMark(Sci::Line line) const {
-	return pdoc->GetMark(line);
+	return pdoc->GetMark(line, FlagSet(changeHistoryOption, ChangeHistoryOption::Markers));
 }
diff --git a/src/EditModel.h b/src/EditModel.h
index 48c230f84..d86f41250 100644
--- a/src/EditModel.h
+++ b/src/EditModel.h
@@ -49,6 +49,8 @@ public:
 	bool hotspotSingleLine;
 	Sci::Position hoverIndicatorPos;
 
+	Scintilla::ChangeHistoryOption changeHistoryOption = Scintilla::ChangeHistoryOption::Disabled;
+
 	// Wrapping support
 	int wrapWidth;
 
diff --git a/src/EditView.cxx b/src/EditView.cxx
index c3709f25b..c4768a2a3 100644
--- a/src/EditView.cxx
+++ b/src/EditView.cxx
@@ -1326,6 +1326,45 @@ static void DrawIndicators(Surface *surface, const EditModel &model, const ViewS
 			}
 		}
 	}
+
+	if (FlagSet(model.changeHistoryOption, ChangeHistoryOption::Indicators)) {
+		// Draw editions
+		const int indexHistory = static_cast<int>(IndicatorNumbers::HistoryRevertedToOriginInsertion);
+		{
+			// Draw insertions
+			Sci::Position startPos = posLineStart + lineStart;
+			while (startPos < posLineEnd) {
+				const Range rangeRun(startPos, model.pdoc->EditionEndRun(startPos));
+				const Sci::Position endPos = std::min(rangeRun.end, posLineEnd);
+				const int edition = model.pdoc->EditionAt(startPos);
+				if (edition != 0) {
+					const int indicator = (edition - 1) * 2 + indexHistory;
+					const Sci::Position posSecond = model.pdoc->MovePositionOutsideChar(rangeRun.First() + 1, 1);
+					DrawIndicator(indicator, startPos - posLineStart, endPos - posLineStart,
+						surface, vsDraw, ll, xStart, rcLine, posSecond - posLineStart, subLine, Indicator::State::normal,
+						1, model.BidirectionalEnabled(), tabWidthMinimumPixels);
+				}
+				startPos = endPos;
+			}
+		}
+		{
+			// Draw deletions
+			Sci::Position startPos = posLineStart + lineStart;
+			while (startPos <= posLineEnd) {
+				const unsigned int editions = model.pdoc->EditionDeletesAt(startPos);
+				const Sci::Position posSecond = model.pdoc->MovePositionOutsideChar(startPos + 1, 1);
+				for (unsigned int edition=0; edition<4; edition++) {
+					if (editions & (1 << edition)) {
+						const int indicator = edition * 2 + indexHistory + 1;
+						DrawIndicator(indicator, startPos - posLineStart, posSecond - posLineStart,
+							surface, vsDraw, ll, xStart, rcLine, posSecond - posLineStart, subLine, Indicator::State::normal,
+							1, model.BidirectionalEnabled(), tabWidthMinimumPixels);
+					}
+				}
+				startPos = model.pdoc->EditionNextDelete(startPos);
+			}
+		}
+	}
 }
 
 void EditView::DrawFoldDisplayText(Surface *surface, const EditModel &model, const ViewStyle &vsDraw, const LineLayout *ll,
diff --git a/src/Editor.cxx b/src/Editor.cxx
index ccf187c65..c2c31f0d1 100644
--- a/src/Editor.cxx
+++ b/src/Editor.cxx
@@ -2405,6 +2405,9 @@ void Editor::NotifySavePoint(bool isSavePoint) {
 	NotificationData scn = {};
 	if (isSavePoint) {
 		scn.nmhdr.code = Notification::SavePointReached;
+		if (changeHistoryOption != ChangeHistoryOption::Disabled) {
+			Redraw();
+		}
 	} else {
 		scn.nmhdr.code = Notification::SavePointLeft;
 	}
@@ -2733,6 +2736,9 @@ void Editor::NotifyModified(Document *, DocModification mh, void *) {
 					QueueIdleWork(WorkItems::style, mh.position + mh.length);
 				}
 				InvalidateRange(mh.position, mh.position + mh.length);
+				if (FlagSet(changeHistoryOption, ChangeHistoryOption::Markers)) {
+					RedrawSelMargin(pdoc->SciLineFromPosition(mh.position));
+				}
 			}
 		}
 	}
@@ -8349,6 +8355,14 @@ sptr_t Editor::WndProc(Message iMessage, uptr_t wParam, sptr_t lParam) {
 	case Message::GetGapPosition:
 		return pdoc->GapPosition();
 
+	case Message::SetChangeHistory:
+		changeHistoryOption = static_cast<ChangeHistoryOption>(wParam);
+		pdoc->ChangeHistorySet(wParam & 1);
+		break;
+
+	case Message::GetChangeHistory:
+		return static_cast<sptr_t>(changeHistoryOption);
+
 	case Message::SetExtraAscent:
 		vs.extraAscent = static_cast<int>(wParam);
 		InvalidateStyleRedraw();
diff --git a/src/SparseVector.h b/src/SparseVector.h
index f8c35fdc5..09eb1f98d 100644
--- a/src/SparseVector.h
+++ b/src/SparseVector.h
@@ -57,6 +57,22 @@ public:
 			return empty;
 		}
 	}
+	T Extract(Sci::Position position) {
+		// Move value currently at position; clear and remove position; return value.
+		// Doesn't remove position at start or end.
+		assert(position <= Length());
+		const Sci::Position partition = ElementFromPosition(position);
+		assert(partition >= 0);
+		assert(partition <= starts.Partitions());
+		assert(starts.PositionFromPartition(partition) == position);
+		T value = std::move(values.operator[](partition));
+		if ((partition > 0) && (partition < starts.Partitions())) {
+			starts.RemovePartition(partition);
+			values.Delete(partition);
+		}
+		Check();
+		return value;
+	}
 	template <typename ParamType>
 	void SetValueAt(Sci::Position position, ParamType &&value) {
 		assert(position <= Length());
diff --git a/src/ViewStyle.cxx b/src/ViewStyle.cxx
index 25a5f9cad..01b94cca1 100644
--- a/src/ViewStyle.cxx
+++ b/src/ViewStyle.cxx
@@ -104,6 +104,49 @@ ViewStyle::ViewStyle(size_t stylesSize_) :
 	indicators[1] = Indicator(IndicatorStyle::TT, ColourRGBA(0, 0, 0xff));
 	indicators[2] = Indicator(IndicatorStyle::Plain, ColourRGBA(0xff, 0, 0));
 
+	// Reverted to origin
+	constexpr ColourRGBA revertedToOrigin(0x40, 0xA0, 0xBF);
+	// Saved
+	constexpr ColourRGBA saved(0x0, 0xA0, 0x0);
+	// Modified
+	constexpr ColourRGBA modified(0xA0, 0xA0, 0x0);
+	// Reverted to change
+	constexpr ColourRGBA revertedToChange(0xFF, 0x80, 0x0);
+
+	// Edition indicators
+	constexpr size_t indexHistory = static_cast<size_t>(IndicatorNumbers::HistoryRevertedToOriginInsertion);
+
+	indicators[indexHistory+0] = Indicator(IndicatorStyle::StraightBox, ColourRGBA(revertedToOrigin, 0x40));
+	indicators[indexHistory+1] = Indicator(IndicatorStyle::Point, revertedToOrigin);
+	indicators[indexHistory+2] = Indicator(IndicatorStyle::StraightBox, ColourRGBA(saved, 0x40));
+	indicators[indexHistory+3] = Indicator(IndicatorStyle::Point, saved);
+	indicators[indexHistory+4] = Indicator(IndicatorStyle::StraightBox, ColourRGBA(modified, 0x40));
+	indicators[indexHistory+5] = Indicator(IndicatorStyle::Point, modified);
+	indicators[indexHistory+6] = Indicator(IndicatorStyle::StraightBox, ColourRGBA(revertedToChange, 0x40));
+	indicators[indexHistory+7] = Indicator(IndicatorStyle::Point, revertedToChange);
+
+	// Edition markers
+	// Reverted to origin
+	constexpr size_t indexHistoryRevertedToOrigin = static_cast<size_t>(MarkerOutline::HistoryRevertedToOrigin);
+	markers[indexHistoryRevertedToOrigin].back = revertedToOrigin;
+	markers[indexHistoryRevertedToOrigin].fore = revertedToOrigin;
+	markers[indexHistoryRevertedToOrigin].markType = MarkerSymbol::LeftRect;
+	// Saved
+	constexpr size_t indexHistorySaved = static_cast<size_t>(MarkerOutline::HistorySaved);
+	markers[indexHistorySaved].back = saved;
+	markers[indexHistorySaved].fore = saved;
+	markers[indexHistorySaved].markType = MarkerSymbol::LeftRect;
+	// Modified
+	constexpr size_t indexHistoryModified = static_cast<size_t>(MarkerOutline::HistoryModified);
+	markers[indexHistoryModified].back = ColourRGBA(modified, 0x40);
+	markers[indexHistoryModified].fore = modified;
+	markers[indexHistoryModified].markType = MarkerSymbol::LeftRect;
+	// Reverted to change
+	constexpr size_t indexHistoryRevertedToModified = static_cast<size_t>(MarkerOutline::HistoryRevertedToModified);
+	markers[indexHistoryRevertedToModified].back = revertedToChange;
+	markers[indexHistoryRevertedToModified].fore = revertedToChange;
+	markers[indexHistoryRevertedToModified].markType = MarkerSymbol::LeftRect;
+
 	technology = Technology::Default;
 	indicatorsDynamic = false;
 	indicatorsSetFore = false;