implicitly instantiate RunStyles: support ptrdiff_t if it has the same storage size as int, but does *not* alias it

* This is the case e.g. on NetBSD 10 for ARMv6 where Sci::Position == ptrdiff_t == long int,
  but obviously for other platforms as well, where it causes "invalid conversion"
  and "undefined symbol" errors.
  Scintilla was testing for aliasability by comparing the storage size with sizeof()
  or PTRDIFF_MAX == INT_MAX at the preprocessor level.
  This was fundamentally flawed.
* In LineVector<T>::InsertLines() we are now using the C++17 construct
  std::is_convertible_v<From*,To*> instead.
* We need RunStyles<ptrdiff_t> as well on the affected platforms.
  AFAIK this is impossible to test for in a constant expression that can be used
  with the preprocessor.
  A workaround has been added previously for Haiku:
  https://groups.google.com/g/scintilla-interest/c/xPXquJUIXo8/m/BLXBpTTgBwAJ
  The workaround is not very robust, as probably nobody guarantees that ptrdiff_t
  never aliases on Haiku. If it does, you will suddenly get errors about duplicate
  template instantiations.
  Quite possibly, the explicit instantiations of RunStyles were wrong on certain
  32-bit Linux variants as well.
* We could have tried to explicitly instantiate RunStyles for all scalar types that could possibly be behind ptrdiff_t.
  Unfortunately, it would result in "possible loss of data" warnings on MSVC.
  Instead, we now implicitly instantiate RunStyles.

1 files changed, 270 insertions, 23 deletions

diff --git a/src/RunStyles.h b/src/RunStyles.h
index 44367adf7..98c50f224 100644
--- a/src/RunStyles.h
+++ b/src/RunStyles.h
@@ -27,30 +27,277 @@ class RunStyles {
 private:
 	Partitioning<DISTANCE> starts;
 	SplitVector<STYLE> styles;
-	DISTANCE RunFromPosition(DISTANCE position) const noexcept;
-	DISTANCE SplitRun(DISTANCE position);
-	void RemoveRun(DISTANCE run);
-	void RemoveRunIfEmpty(DISTANCE run);
-	void RemoveRunIfSameAsPrevious(DISTANCE run);
+
+	// Find the first run at a position
+	DISTANCE RunFromPosition(DISTANCE position) const noexcept {
+		DISTANCE run = starts.PartitionFromPosition(position);
+		// Go to first element with this position
+		while ((run > 0) && (position == starts.PositionFromPartition(run-1))) {
+			run--;
+		}
+		return run;
+	}
+
+	// If there is no run boundary at position, insert one continuing style.
+	DISTANCE SplitRun(DISTANCE position) {
+		DISTANCE run = RunFromPosition(position);
+		const DISTANCE posRun = starts.PositionFromPartition(run);
+		if (posRun < position) {
+			STYLE runStyle = ValueAt(position);
+			run++;
+			starts.InsertPartition(run, position);
+			styles.InsertValue(run, 1, runStyle);
+		}
+		return run;
+	}
+
+	void RemoveRun(DISTANCE run) {
+		starts.RemovePartition(run);
+		styles.DeleteRange(run, 1);
+	}
+
+	void RemoveRunIfEmpty(DISTANCE run) {
+		if ((run < starts.Partitions()) && (starts.Partitions() > 1)) {
+			if (starts.PositionFromPartition(run) == starts.PositionFromPartition(run+1)) {
+				RemoveRun(run);
+			}
+		}
+	}
+
+	void RemoveRunIfSameAsPrevious(DISTANCE run) {
+		if ((run > 0) && (run < starts.Partitions())) {
+			const DISTANCE runBefore = run - 1;
+			if (styles.ValueAt(runBefore) == styles.ValueAt(run)) {
+				RemoveRun(run);
+			}
+		}
+	}
+
 public:
-	RunStyles();
-	DISTANCE Length() const noexcept;
-	STYLE ValueAt(DISTANCE position) const noexcept;
-	DISTANCE FindNextChange(DISTANCE position, DISTANCE end) const noexcept;
-	DISTANCE StartRun(DISTANCE position) const noexcept;
-	DISTANCE EndRun(DISTANCE position) const noexcept;
-	// Returns changed=true if some values may have changed
-	FillResult<DISTANCE> FillRange(DISTANCE position, STYLE value, DISTANCE fillLength);
-	void SetValueAt(DISTANCE position, STYLE value);
-	void InsertSpace(DISTANCE position, DISTANCE insertLength);
-	void DeleteAll();
-	void DeleteRange(DISTANCE position, DISTANCE deleteLength);
-	DISTANCE Runs() const noexcept;
-	bool AllSame() const noexcept;
-	bool AllSameAs(STYLE value) const noexcept;
-	DISTANCE Find(STYLE value, DISTANCE start) const noexcept;
-
-	void Check() const;
+	RunStyles() {
+		styles.InsertValue(0, 2, 0);
+	}
+
+	DISTANCE Length() const noexcept {
+		return starts.PositionFromPartition(starts.Partitions());
+	}
+
+	STYLE ValueAt(DISTANCE position) const noexcept {
+		return styles.ValueAt(starts.PartitionFromPosition(position));
+	}
+
+	DISTANCE FindNextChange(DISTANCE position, DISTANCE end) const noexcept {
+		const DISTANCE run = starts.PartitionFromPosition(position);
+		if (run < starts.Partitions()) {
+			const DISTANCE runChange = starts.PositionFromPartition(run);
+			if (runChange > position)
+				return runChange;
+			const DISTANCE nextChange = starts.PositionFromPartition(run + 1);
+			if (nextChange > position) {
+				return nextChange;
+			} else if (position < end) {
+				return end;
+			} else {
+				return end + 1;
+			}
+		} else {
+			return end + 1;
+		}
+	}
+
+	DISTANCE StartRun(DISTANCE position) const noexcept {
+		return starts.PositionFromPartition(starts.PartitionFromPosition(position));
+	}
+
+	DISTANCE EndRun(DISTANCE position) const noexcept {
+		return starts.PositionFromPartition(starts.PartitionFromPosition(position) + 1);
+	}
+
+	FillResult<DISTANCE> FillRange(DISTANCE position, STYLE value, DISTANCE fillLength) {
+		const FillResult<DISTANCE> resultNoChange{false, position, fillLength};
+		if (fillLength <= 0) {
+			return resultNoChange;
+		}
+		DISTANCE end = position + fillLength;
+		if (end > Length()) {
+			return resultNoChange;
+		}
+		DISTANCE runEnd = RunFromPosition(end);
+		const STYLE valueCurrent = styles.ValueAt(runEnd);
+		if (valueCurrent == value) {
+			// End already has value so trim range.
+			end = starts.PositionFromPartition(runEnd);
+			if (position >= end) {
+				// Whole range is already same as value so no action
+				return resultNoChange;
+			}
+			fillLength = end - position;
+		} else {
+			const DISTANCE startRun = starts.PositionFromPartition(runEnd);
+			if (position > startRun) {
+				const DISTANCE runNext = runEnd + 1;
+				const DISTANCE endRun = starts.PositionFromPartition(runNext);
+				if (end < endRun) {
+					// New piece is completely inside a run with a different value so its a simple
+					// insertion of two points [ (position, value), (end, valueCurrent) ]
+					const DISTANCE range[] { position, end};
+					starts.InsertPartitions(runEnd + 1, range, 2);
+					// Temporary runEndIndex silences non-useful arithmetic overflow warnings
+					const ptrdiff_t runEndIndex = runEnd;
+					styles.Insert(runEndIndex + 1, value);
+					styles.Insert(runEndIndex + 2, valueCurrent);
+					return { true, position, fillLength };
+				}
+			}
+			runEnd = SplitRun(end);
+		}
+		DISTANCE runStart = RunFromPosition(position);
+		if (styles.ValueAt(runStart) == value) {
+			// Start is in expected value so trim range.
+			runStart++;
+			position = starts.PositionFromPartition(runStart);
+			fillLength = end - position;
+		} else {
+			if (starts.PositionFromPartition(runStart) < position) {
+				runStart = SplitRun(position);
+				runEnd++;
+			}
+		}
+		if (runStart < runEnd) {
+			const FillResult<DISTANCE> result{ true, position, fillLength };
+			styles.SetValueAt(runStart, value);
+			// Remove each old run over the range
+			for (DISTANCE run=runStart+1; run<runEnd; run++) {
+				RemoveRun(runStart+1);
+			}
+			runEnd = RunFromPosition(end);
+			RemoveRunIfSameAsPrevious(runEnd);
+			RemoveRunIfSameAsPrevious(runStart);
+			runEnd = RunFromPosition(end);
+			RemoveRunIfEmpty(runEnd);
+			return result;
+		}
+		return resultNoChange;
+	}
+
+	void SetValueAt(DISTANCE position, STYLE value) {
+		FillRange(position, value, 1);
+	}
+
+	void InsertSpace(DISTANCE position, DISTANCE insertLength) {
+		DISTANCE runStart = RunFromPosition(position);
+		if (starts.PositionFromPartition(runStart) == position) {
+			STYLE runStyle = ValueAt(position);
+			// Inserting at start of run so make previous longer
+			if (runStart == 0) {
+				// Inserting at start of document so ensure 0
+				if (runStyle) {
+					styles.SetValueAt(0, STYLE());
+					starts.InsertPartition(1, 0);
+					styles.InsertValue(1, 1, runStyle);
+					starts.InsertText(0, insertLength);
+				} else {
+					starts.InsertText(runStart, insertLength);
+				}
+			} else {
+				if (runStyle) {
+					starts.InsertText(runStart-1, insertLength);
+				} else {
+					// Insert at end of run so do not extend style
+					starts.InsertText(runStart, insertLength);
+				}
+			}
+		} else {
+			starts.InsertText(runStart, insertLength);
+		}
+	}
+
+	void DeleteAll() {
+		starts = Partitioning<DISTANCE>();
+		styles = SplitVector<STYLE>();
+		styles.InsertValue(0, 2, 0);
+	}
+
+	void DeleteRange(DISTANCE position, DISTANCE deleteLength) {
+		DISTANCE end = position + deleteLength;
+		DISTANCE runStart = RunFromPosition(position);
+		DISTANCE runEnd = RunFromPosition(end);
+		if (runStart == runEnd) {
+			// Deleting from inside one run
+			starts.InsertText(runStart, -deleteLength);
+			RemoveRunIfEmpty(runStart);
+		} else {
+			runStart = SplitRun(position);
+			runEnd = SplitRun(end);
+			starts.InsertText(runStart, -deleteLength);
+			// Remove each old run over the range
+			for (DISTANCE run=runStart; run<runEnd; run++) {
+				RemoveRun(runStart);
+			}
+			RemoveRunIfEmpty(runStart);
+			RemoveRunIfSameAsPrevious(runStart);
+		}
+	}
+
+	DISTANCE Runs() const noexcept {
+		return starts.Partitions();
+	}
+
+	bool AllSame() const noexcept {
+		for (DISTANCE run = 1; run < starts.Partitions(); run++) {
+			const DISTANCE runBefore = run - 1;
+			if (styles.ValueAt(run) != styles.ValueAt(runBefore))
+				return false;
+		}
+		return true;
+	}
+
+	bool AllSameAs(STYLE value) const noexcept {
+		return AllSame() && (styles.ValueAt(0) == value);
+	}
+
+	DISTANCE Find(STYLE value, DISTANCE start) const noexcept {
+		if (start < Length()) {
+			DISTANCE run = start ? RunFromPosition(start) : 0;
+			if (styles.ValueAt(run) == value)
+				return start;
+			run++;
+			while (run < starts.Partitions()) {
+				if (styles.ValueAt(run) == value)
+					return starts.PositionFromPartition(run);
+				run++;
+			}
+		}
+		return -1;
+	}
+
+	void Check() const {
+		if (Length() < 0) {
+			throw std::runtime_error("RunStyles: Length can not be negative.");
+		}
+		if (starts.Partitions() < 1) {
+			throw std::runtime_error("RunStyles: Must always have 1 or more partitions.");
+		}
+		if (starts.Partitions() != styles.Length()-1) {
+			throw std::runtime_error("RunStyles: Partitions and styles different lengths.");
+		}
+		DISTANCE start=0;
+		while (start < Length()) {
+			const DISTANCE end = EndRun(start);
+			if (start >= end) {
+				throw std::runtime_error("RunStyles: Partition is 0 length.");
+			}
+			start = end;
+		}
+		if (styles.ValueAt(styles.Length()-1) != 0) {
+			throw std::runtime_error("RunStyles: Unused style at end changed.");
+		}
+		for (ptrdiff_t j=1; j<styles.Length()-1; j++) {
+			if (styles.ValueAt(j) == styles.ValueAt(j-1)) {
+				throw std::runtime_error("RunStyles: Style of a partition same as previous.");
+			}
+		}
+	}
 };
 
 }