aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/ScintillaHistory.html4
-rw-r--r--src/ChangeHistory.cxx134
-rw-r--r--src/ChangeHistory.h24
-rw-r--r--test/unit/testCellBuffer.cxx6
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);
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-11 22:12:25 +0000