Backport: Bug [#2094]. gtk: Accessible: use the built-in character position cache

It's quite a lot faster even after trying and optimizing the custom
version, and it makes the code simpler.

Also improve ByteOffsetFromCharacterOffset() to make use of the cache,
making it drastically faster.

Backport of changeset 7405:01aab5f24e50.

4 files changed, 23 insertions, 25 deletions

diff --git a/doc/ScintillaHistory.html b/doc/ScintillaHistory.html
index 299547eb9..8aa71263e 100644
--- a/doc/ScintillaHistory.html
+++ b/doc/ScintillaHistory.html
@@ -566,6 +566,10 @@
 	<a href="https://sourceforge.net/p/scintilla/feature-requests/1259/">Feature #1259</a>.
 	</li>
  	<li>
+	Improve performance of accessibility on GTK.
+	<a href="https://sourceforge.net/p/scintilla/bugs/2094/">Bug #2094</a>.
+	</li>
+ 	<li>
 	Fix flicker when inserting primary selection on GTK.
 	<a href="https://sourceforge.net/p/scintilla/bugs/2087/">Bug #2087</a>.
 	</li>
diff --git a/gtk/ScintillaGTK.cxx b/gtk/ScintillaGTK.cxx
index 22b01cbaf..e3acacbf9 100644
--- a/gtk/ScintillaGTK.cxx
+++ b/gtk/ScintillaGTK.cxx
@@ -866,7 +866,7 @@ sptr_t ScintillaGTK::WndProc(unsigned int iMessage, uptr_t wParam, sptr_t lParam
 			if (accessible) {
 				ScintillaGTKAccessible *sciAccessible = ScintillaGTKAccessible::FromAccessible(accessible);
 				if (sciAccessible) {
-					sciAccessible->SetAccessibility();
+					sciAccessible->SetAccessibility(accessibilityEnabled);
 				}
 			}
 			break;
diff --git a/gtk/ScintillaGTKAccessible.cxx b/gtk/ScintillaGTKAccessible.cxx
index b7d52a221..7e93b8a5e 100644
--- a/gtk/ScintillaGTKAccessible.cxx
+++ b/gtk/ScintillaGTKAccessible.cxx
@@ -162,6 +162,7 @@ ScintillaGTKAccessible::ScintillaGTKAccessible(GtkAccessible *accessible_, GtkWi
 		sci(ScintillaGTK::FromWidget(widget_)),
 		deletionLengthChar(0),
 		old_pos(-1) {
+	SetAccessibility(true);
 	g_signal_connect(widget_, "sci-notify", G_CALLBACK(SciNotify), this);
 }
 
@@ -865,10 +866,12 @@ void ScintillaGTKAccessible::NotifyReadOnly() {
 #endif
 }
 
-void ScintillaGTKAccessible::SetAccessibility() {
+void ScintillaGTKAccessible::SetAccessibility(bool enabled) {
 	// Called by ScintillaGTK when application has enabled or disabled accessibility
-	character_offsets.resize(0);
-	character_offsets.push_back(0);
+	if (enabled)
+		sci->pdoc->AllocateLineCharacterIndex(SC_LINECHARACTERINDEX_UTF32);
+	else
+		sci->pdoc->ReleaseLineCharacterIndex(SC_LINECHARACTERINDEX_UTF32);
 }
 
 void ScintillaGTKAccessible::Notify(GtkWidget *, gint, SCNotification *nt) {
@@ -876,13 +879,6 @@ void ScintillaGTKAccessible::Notify(GtkWidget *, gint, SCNotification *nt) {
 		return;
 	switch (nt->nmhdr.code) {
 		case SCN_MODIFIED: {
-			if (nt->modificationType & (SC_MOD_INSERTTEXT | SC_MOD_DELETETEXT)) {
-				// invalidate character offset cache if applicable
-				const Sci::Line line = sci->pdoc->LineFromPosition(nt->position);
-				if (character_offsets.size() > static_cast<size_t>(line + 1)) {
-					character_offsets.resize(line + 1);
-				}
-			}
 			if (nt->modificationType & SC_MOD_INSERTTEXT) {
 				int startChar = CharacterOffsetFromByteOffset(nt->position);
 				int lengthChar = sci->pdoc->CountCharacters(nt->position, nt->position + nt->length);
diff --git a/gtk/ScintillaGTKAccessible.h b/gtk/ScintillaGTKAccessible.h
index 2c39d5257..00570acce 100644
--- a/gtk/ScintillaGTKAccessible.h
+++ b/gtk/ScintillaGTKAccessible.h
@@ -18,9 +18,6 @@ private:
 	GtkAccessible *accessible;
 	ScintillaGTK *sci;
 
-	// cache holding character offset for each line start, see CharacterOffsetFromByteOffset()
-	std::vector<Sci::Position> character_offsets;
-
 	// cached length of the deletion, in characters (see Notify())
 	int deletionLengthChar;
 	// local state for comparing
@@ -37,6 +34,16 @@ private:
 	}
 
 	Sci::Position ByteOffsetFromCharacterOffset(Sci::Position startByte, int characterOffset) {
+		if (characterOffset > 0) {
+			// Try and reduce the range by reverse-looking into the character offset cache
+			Sci::Line lineStart = sci->pdoc->LineFromPosition(startByte);
+			Sci::Position posStart = sci->pdoc->IndexLineStart(lineStart, SC_LINECHARACTERINDEX_UTF32);
+			Sci::Line line = sci->pdoc->LineFromPositionIndex(posStart + characterOffset, SC_LINECHARACTERINDEX_UTF32);
+			if (line != lineStart) {
+				startByte += sci->pdoc->LineStart(line) - sci->pdoc->LineStart(lineStart);
+				characterOffset -= sci->pdoc->IndexLineStart(line, SC_LINECHARACTERINDEX_UTF32) - posStart;
+			}
+		}
 		Sci::Position pos = sci->pdoc->GetRelativePosition(startByte, characterOffset);
 		if (pos == INVALID_POSITION) {
 			// clamp invalid positions inside the document
@@ -55,17 +62,8 @@ private:
 
 	Sci::Position CharacterOffsetFromByteOffset(Sci::Position byteOffset) {
 		const Sci::Line line = sci->pdoc->LineFromPosition(byteOffset);
-		if (character_offsets.size() <= static_cast<size_t>(line)) {
-			if (character_offsets.empty())
-				character_offsets.push_back(0);
-			for (Sci::Position i = character_offsets.size(); i <= line; i++) {
-				const Sci::Position start = sci->pdoc->LineStart(i - 1);
-				const Sci::Position end = sci->pdoc->LineStart(i);
-				character_offsets.push_back(character_offsets[i - 1] + sci->pdoc->CountCharacters(start, end));
-			}
-		}
 		const Sci::Position lineStart = sci->pdoc->LineStart(line);
-		return character_offsets[line] + sci->pdoc->CountCharacters(lineStart, byteOffset);
+		return sci->pdoc->IndexLineStart(line, SC_LINECHARACTERINDEX_UTF32) + sci->pdoc->CountCharacters(lineStart, byteOffset);
 	}
 
 	void CharacterRangeFromByteRange(Sci::Position startByte, Sci::Position endByte, int *startChar, int *endChar) {
@@ -135,7 +133,7 @@ public:
 	// So ScintillaGTK can notify us
 	void ChangeDocument(Document *oldDoc, Document *newDoc);
 	void NotifyReadOnly();
-	void SetAccessibility();
+	void SetAccessibility(bool enabled);
 
 	// Helper GtkWidget methods
 	static AtkObject *WidgetGetAccessibleImpl(GtkWidget *widget, AtkObject **cache, gpointer widget_parent_class);