Optimize performance with many control characters such as when opening

a binary file.
Simplify use of BreakFinder and use for layout as well as drawing.

3 files changed, 163 insertions, 197 deletions

diff --git a/src/Editor.cxx b/src/Editor.cxx
index 75c1336d7..276326877 100644
--- a/src/Editor.cxx
+++ b/src/Editor.cxx
@@ -2279,74 +2279,54 @@ void Editor::LayoutLine(int line, Surface *surface, ViewStyle &vstyle, LineLayou
 		XYPOSITION tabWidth = vstyle.spaceWidth * pdoc->tabInChars;
 		bool lastSegItalics = false;
 
-		EncodingFamily encodingFamily = pdoc->CodePageFamily();
-
-		XYPOSITION positionsRepr[256];	// Should expand when needed
-		int charWidthNext = 1;
-		if (encodingFamily == efUnicode)
-			charWidthNext = UTF8DrawBytes(reinterpret_cast<unsigned char *>(ll->chars), numCharsInLine);
-		else if (encodingFamily == efDBCS)
-			charWidthNext = pdoc->IsDBCSLeadByte(ll->chars[0]) ? 2 : 1;
-		Representation *reprNext = reprs.RepresentationFromCharacter(ll->chars, charWidthNext);
-		int charWidth = 1;
-
-		for (int charInLine = 0; charInLine < numCharsInLine; charInLine += charWidth) {
-
-			charWidth = charWidthNext;
-			Representation *repr = reprNext;
-
-			charWidthNext = 1;
-			if (encodingFamily == efUnicode)
-				charWidthNext = UTF8DrawBytes(reinterpret_cast<unsigned char *>(ll->chars+charInLine + charWidth), numCharsInLine - charInLine - charWidth);
-			else if (encodingFamily == efDBCS)
-				charWidthNext = pdoc->IsDBCSLeadByte(ll->chars[charInLine + charWidth]) ? 2 : 1;
-			reprNext = reprs.RepresentationFromCharacter(ll->chars+charInLine + charWidth, charWidthNext);
-
-			if ((ll->styles[charInLine] != ll->styles[charInLine + 1]) ||
-			        repr || reprNext || ((charInLine+charWidth) >= numCharsBeforeEOL)) {
-				ll->positions[startseg] = 0;
-				if (vstyle.styles[ll->styles[charInLine]].visible) {
-					if (repr) {
-						if (ll->chars[charInLine] == '\t') {
-							// Tab is a special case of repr, taking a variable amount of space
-							ll->positions[charInLine + 1] =
-								((static_cast<int>((startsegx + 2) / tabWidth) + 1) * tabWidth) - startsegx;
-						} else if (controlCharSymbol < 32) {
-							posCache.MeasureWidths(surface, vstyle, STYLE_CONTROLCHAR, repr->stringRep.c_str(),
-								static_cast<unsigned int>(repr->stringRep.length()), positionsRepr, pdoc);
-							XYPOSITION endRepr = positionsRepr[repr->stringRep.length()-1] + 3;
-							for (int ii=0; ii < charWidth; ii++)
-								ll->positions[startseg + 1 + ii] = endRepr;
-						} else {
-							char cc[2] = { static_cast<char>(controlCharSymbol), '\0' };
-							surface->MeasureWidths(vstyle.styles[STYLE_CONTROLCHAR].font, cc, 1,
-							        ll->positions + startseg + 1);
- 						}
+		BreakFinder bfLayout(ll, 0, numCharsInLine, posLineStart, 0, false, pdoc, &reprs);
+		while (bfLayout.More()) {
+
+			TextSegment ts = bfLayout.Next();
+			startseg = ts.start;
+
+			ll->positions[startseg] = 0;
+			if (vstyle.styles[ll->styles[startseg]].visible) {
+				if (ts.repr) {
+					if (ll->chars[startseg] == '\t') {
+						// Tab is a special case of repr, taking a variable amount of space
+						ll->positions[startseg + 1] =
+							((static_cast<int>((startsegx + 2) / tabWidth) + 1) * tabWidth) - startsegx;
+					} else if (controlCharSymbol < 32) {
+						XYPOSITION positionsRepr[256];	// Should expand when needed
+						posCache.MeasureWidths(surface, vstyle, STYLE_CONTROLCHAR, ts.repr->stringRep.c_str(),
+							static_cast<unsigned int>(ts.repr->stringRep.length()), positionsRepr, pdoc);
+						XYPOSITION endRepr = positionsRepr[ts.repr->stringRep.length()-1] + 3;
+						for (int ii=0; ii < ts.length; ii++)
+							ll->positions[startseg + 1 + ii] = endRepr;
+					} else {
+						char cc[2] = { static_cast<char>(controlCharSymbol), '\0' };
+						surface->MeasureWidths(vstyle.styles[STYLE_CONTROLCHAR].font, cc, 1,
+							    ll->positions + startseg + 1);
+ 					}
+					lastSegItalics = false;
+				} else {
+					if ((ts.length == 1) && (' ' == ll->chars[startseg])) {
 						lastSegItalics = false;
+						// Over half the segments are single characters and of these about half are space characters.
+						ll->positions[startseg + 1] = vstyle.styles[ll->styles[startseg]].spaceWidth;
 					} else {
-						int lenSeg = charInLine - startseg + charWidth;
-						if ((lenSeg == 1) && (' ' == ll->chars[startseg])) {
-							lastSegItalics = false;
-							// Over half the segments are single characters and of these about half are space characters.
-							ll->positions[charInLine + 1] = vstyle.styles[ll->styles[charInLine]].spaceWidth;
-						} else {
-							lastSegItalics = vstyle.styles[ll->styles[charInLine]].italic;
-							posCache.MeasureWidths(surface, vstyle, ll->styles[charInLine], ll->chars + startseg,
-							        lenSeg, ll->positions + startseg + 1, pdoc);
-						}
-					}
-				} else {    // invisible
-					for (int posToZero = startseg; posToZero <= (charInLine + charWidth); posToZero++) {
-						ll->positions[posToZero] = 0;
+						lastSegItalics = vstyle.styles[ll->styles[startseg]].italic;
+						posCache.MeasureWidths(surface, vstyle, ll->styles[startseg], ll->chars + startseg,
+							    ts.length, ll->positions + startseg + 1, pdoc);
 					}
 				}
-				for (int posToIncrease = startseg; posToIncrease <= (charInLine + charWidth); posToIncrease++) {
-					ll->positions[posToIncrease] += startsegx;
+			} else {    // invisible
+				for (int posToZero = startseg; posToZero <= (startseg + ts.length); posToZero++) {
+					ll->positions[posToZero] = 0;
 				}
-				startsegx = ll->positions[charInLine + charWidth];
-				startseg = charInLine + charWidth;
 			}
+			for (int posToIncrease = startseg; posToIncrease <= (startseg + ts.length); posToIncrease++) {
+				ll->positions[posToIncrease] += startsegx;
+			}
+			startsegx = ll->positions[startseg + ts.length];
 		}
+
 		// Small hack to make lines that end with italics not cut off the edge of the last character
 		if ((startseg > 0) && lastSegItalics) {
 			ll->positions[startseg] += lastSegItalicsOffset;
@@ -2968,14 +2948,13 @@ void Editor::DrawLine(Surface *surface, ViewStyle &vsDraw, int line, int lineVis
 	ll->psel = &sel;
 
 	BreakFinder bfBack(ll, lineStart, lineEnd, posLineStart, xStartVisible, selBackDrawn, pdoc, &reprs);
-	int next = bfBack.First();
 
 	// Background drawing loop
-	while (twoPhaseDraw && (next < lineEnd)) {
+	while (twoPhaseDraw && bfBack.More()) {
 
-		startseg = next;
-		next = bfBack.Next();
-		int i = next - 1;
+		TextSegment ts = bfBack.Next();
+		startseg = ts.start;
+		int i = ts.start + ts.length - 1;
 		int iDoc = i + posLineStart;
 
 		rcSegment.left = ll->positions[startseg] + xStart - subLineStart;
@@ -3063,14 +3042,12 @@ void Editor::DrawLine(Surface *surface, ViewStyle &vsDraw, int line, int lineVis
 	// Foreground drawing loop
 	BreakFinder bfFore(ll, lineStart, lineEnd, posLineStart, xStartVisible,
 		((!twoPhaseDraw && selBackDrawn) || vsDraw.selforeset), pdoc, &reprs);
-	next = bfFore.First();
-
-	while (next < lineEnd) {
 
-		startseg = next;
-		next = bfFore.Next();
-		int i = next - 1;
+	while (bfFore.More()) {
 
+		TextSegment ts = bfFore.Next();
+		startseg = ts.start;
+		int i = ts.start + ts.length - 1;
 		int iDoc = i + posLineStart;
 
 		rcSegment.left = ll->positions[startseg] + xStart - subLineStart;
@@ -3121,71 +3098,66 @@ void Editor::DrawLine(Surface *surface, ViewStyle &vsDraw, int line, int lineVis
 						DrawTabArrow(surface, rcTab, rcSegment.top + vsDraw.lineHeight / 2);
 					}
 				}
+			} else if (ts.repr) {
+				inIndentation = false;
+				if (controlCharSymbol < 32) {
+					DrawTextBlob(surface, vsDraw, rcSegment, ts.repr->stringRep.c_str(), textBack, textFore, twoPhaseDraw);
+				} else {
+					char cc[2] = { static_cast<char>(controlCharSymbol), '\0' };
+					surface->DrawTextNoClip(rcSegment, ctrlCharsFont,
+					        rcSegment.top + vsDraw.maxAscent,
+					        cc, 1, textBack, textFore);
+				}
 			} else {
-				Representation *repr = 0;
-				if ((i - startseg + 1) <= 4)
-					repr = reprs.RepresentationFromCharacter(ll->chars + startseg, i - startseg + 1);
-				if (repr) {
-					inIndentation = false;	// May need to special case ' '.
-					if (controlCharSymbol < 32) {
-						DrawTextBlob(surface, vsDraw, rcSegment, repr->stringRep.c_str(), textBack, textFore, twoPhaseDraw);
+				// Normal text display
+				if (vsDraw.styles[styleMain].visible) {
+					if (twoPhaseDraw) {
+						surface->DrawTextTransparent(rcSegment, textFont,
+						        rcSegment.top + vsDraw.maxAscent, ll->chars + startseg,
+						        i - startseg + 1, textFore);
 					} else {
-						char cc[2] = { static_cast<char>(controlCharSymbol), '\0' };
-						surface->DrawTextNoClip(rcSegment, ctrlCharsFont,
-								rcSegment.top + vsDraw.maxAscent,
-								cc, 1, textBack, textFore);
+						surface->DrawTextNoClip(rcSegment, textFont,
+						        rcSegment.top + vsDraw.maxAscent, ll->chars + startseg,
+						        i - startseg + 1, textFore, textBack);
 					}
-				} else {
-					// Normal text display
-					if (vsDraw.styles[styleMain].visible) {
-						if (twoPhaseDraw) {
-							surface->DrawTextTransparent(rcSegment, textFont,
-							        rcSegment.top + vsDraw.maxAscent, ll->chars + startseg,
-							        i - startseg + 1, textFore);
-						} else {
-							surface->DrawTextNoClip(rcSegment, textFont,
-							        rcSegment.top + vsDraw.maxAscent, ll->chars + startseg,
-							        i - startseg + 1, textFore, textBack);
-						}
-					}
-					if (vsDraw.viewWhitespace != wsInvisible ||
-					        (inIndentation && vsDraw.viewIndentationGuides != ivNone)) {
-						for (int cpos = 0; cpos <= i - startseg; cpos++) {
-							if (ll->chars[cpos + startseg] == ' ') {
-								if (vsDraw.viewWhitespace != wsInvisible) {
-									if (vsDraw.whitespaceForegroundSet)
-										textFore = vsDraw.whitespaceForeground;
-									if (!inIndentation || vsDraw.viewWhitespace == wsVisibleAlways) {
-										XYPOSITION xmid = (ll->positions[cpos + startseg] + ll->positions[cpos + startseg + 1]) / 2;
-										if (!twoPhaseDraw && drawWhitespaceBackground &&
-										        (!inIndentation || vsDraw.viewWhitespace == wsVisibleAlways)) {
-											textBack = vsDraw.whitespaceBackground;
-											PRectangle rcSpace(ll->positions[cpos + startseg] + xStart - subLineStart,
-												rcSegment.top,
-												ll->positions[cpos + startseg + 1] + xStart - subLineStart,
-												rcSegment.bottom);
-											surface->FillRectangle(rcSpace, textBack);
-										}
-										PRectangle rcDot(xmid + xStart - subLineStart, rcSegment.top + vsDraw.lineHeight / 2, 0, 0);
-										rcDot.right = rcDot.left + vs.whitespaceSize;
-										rcDot.bottom = rcDot.top + vs.whitespaceSize;
-										surface->FillRectangle(rcDot, textFore);
+				}
+				if (vsDraw.viewWhitespace != wsInvisible ||
+				        (inIndentation && vsDraw.viewIndentationGuides != ivNone)) {
+					for (int cpos = 0; cpos <= i - startseg; cpos++) {
+						if (ll->chars[cpos + startseg] == ' ') {
+							if (vsDraw.viewWhitespace != wsInvisible) {
+								if (vsDraw.whitespaceForegroundSet)
+									textFore = vsDraw.whitespaceForeground;
+								if (!inIndentation || vsDraw.viewWhitespace == wsVisibleAlways) {
+									XYPOSITION xmid = (ll->positions[cpos + startseg] + ll->positions[cpos + startseg + 1]) / 2;
+									if (!twoPhaseDraw && drawWhitespaceBackground &&
+									        (!inIndentation || vsDraw.viewWhitespace == wsVisibleAlways)) {
+										textBack = vsDraw.whitespaceBackground;
+										PRectangle rcSpace(ll->positions[cpos + startseg] + xStart - subLineStart,
+											rcSegment.top,
+											ll->positions[cpos + startseg + 1] + xStart - subLineStart,
+											rcSegment.bottom);
+										surface->FillRectangle(rcSpace, textBack);
 									}
+									PRectangle rcDot(xmid + xStart - subLineStart, rcSegment.top + vsDraw.lineHeight / 2, 0, 0);
+									rcDot.right = rcDot.left + vs.whitespaceSize;
+									rcDot.bottom = rcDot.top + vs.whitespaceSize;
+									surface->FillRectangle(rcDot, textFore);
 								}
-								if (inIndentation && vsDraw.viewIndentationGuides == ivReal) {
-									for (int indentCount = (ll->positions[cpos + startseg] + epsilon) / indentWidth;
-										indentCount <= (ll->positions[cpos + startseg + 1] - epsilon) / indentWidth;
-										indentCount++) {
-										if (indentCount > 0) {
-											int xIndent = indentCount * indentWidth;
-											DrawIndentGuide(surface, lineVisible, vsDraw.lineHeight, xIndent + xStart, rcSegment,
-													(ll->xHighlightGuide == xIndent));
-										}
+							}
+							if (inIndentation && vsDraw.viewIndentationGuides == ivReal) {
+								for (int indentCount = (ll->positions[cpos + startseg] + epsilon) / indentWidth;
+									indentCount <= (ll->positions[cpos + startseg + 1] - epsilon) / indentWidth;
+									indentCount++) {
+									if (indentCount > 0) {
+										int xIndent = indentCount * indentWidth;
+										DrawIndentGuide(surface, lineVisible, vsDraw.lineHeight, xIndent + xStart, rcSegment,
+												(ll->xHighlightGuide == xIndent));
 									}
 								}
-							} else {
-								inIndentation = false;
 							}
+						} else {
+							inIndentation = false;
 						}
 					}
 				}
diff --git a/src/PositionCache.cxx b/src/PositionCache.cxx
index 009ed7cfa..d833ac982 100644
--- a/src/PositionCache.cxx
+++ b/src/PositionCache.cxx
@@ -13,6 +13,7 @@
 #include <string>
 #include <vector>
 #include <map>
+#include <algorithm>
 
 #include "Platform.h"
 
@@ -343,7 +344,7 @@ static inline int KeyFromString(const char *charBytes, size_t len) {
 	int k=0;
 	for (size_t i=0; i<len && charBytes[i]; i++) {
 		k = k * 0x100;
-		k += charBytes[i];
+		k += static_cast<unsigned char>(charBytes[i]);
 	}
 	return k;
 }
@@ -394,33 +395,15 @@ void SpecialRepresentations::Clear() {
 }
 
 void BreakFinder::Insert(int val) {
-	if (val >= nextBreak) {
-		for (std::vector<int>::iterator it = selAndEdge.begin(); it != selAndEdge.end(); ++it) {
-			if (val == *it) {
-				return;
-			}
-			if (val <*it) {
-				selAndEdge.insert(it, 1, val);
-				return;
-			}
+	if (val > nextBreak) {
+		const std::vector<int>::iterator it = std::lower_bound(selAndEdge.begin(), selAndEdge.end(), val);
+		if (it == selAndEdge.end()) {
+			selAndEdge.push_back(val);
+		} else if (*it != val) {
+			selAndEdge.insert(it, 1, val);
 		}
-		// Not less than any so append
-		selAndEdge.push_back(val);
-	}
-}
-
-/*
-extern bool BadUTF(const char *s, int len, int &trailBytes);
-
-static int NextBadU(const char *s, int p, int len, int &trailBytes) {
-	while (p < len) {
-		p++;
-		if (BadUTF(s + p, len - p, trailBytes))
-			return p;
 	}
-	return -1;
 }
-*/
 
 BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_,
 	int xStart, bool breakForSelection, Document *pdoc_, SpecialRepresentations *preprs_) :
@@ -433,11 +416,13 @@ BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posL
 	saeNext(0),
 	subBreak(-1),
 	pdoc(pdoc_),
+	encodingFamily(pdoc_->CodePageFamily()),
 	preprs(preprs_) {
 
 	// Search for first visible break
 	// First find the first visible character
-	nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
+	if (xStart > 0.0f)
+		nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
 	// Now back to a style break
 	while ((nextBreak > lineStart) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
 		nextBreak--;
@@ -451,81 +436,80 @@ BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posL
 			SelectionSegment portion = ll->psel->Range(r).Intersect(segmentLine);
 			if (!(portion.start == portion.end)) {
 				if (portion.start.IsValid())
-					Insert(portion.start.Position() - posLineStart - 1);
+					Insert(portion.start.Position() - posLineStart);
 				if (portion.end.IsValid())
-					Insert(portion.end.Position() - posLineStart - 1);
+					Insert(portion.end.Position() - posLineStart);
 			}
 		}
 	}
 
-	Insert(ll->edgeColumn - 1);
-	Insert(lineEnd - 1);
-
-	if (pdoc && preprs) {
-		EncodingFamily encodingFamily = pdoc->CodePageFamily();
-		for (int posRepr=0; posRepr<lineEnd;) {
-			int charWidth = 1;
-			if (encodingFamily == efUnicode)
-				charWidth = UTF8DrawBytes(reinterpret_cast<unsigned char *>(ll->chars) + posRepr, lineEnd - posRepr);
-			else if (encodingFamily == efDBCS)
-				charWidth = pdoc->IsDBCSLeadByte(ll->chars[posRepr]) ? 2 : 1;
-			if (preprs->Contains(ll->chars + posRepr, charWidth)) {
-				Insert(posRepr - 1);
-				Insert(posRepr + charWidth - 1);
-			}
-			posRepr += charWidth;
-		}
-	}
+	Insert(ll->edgeColumn);
+	Insert(lineEnd);
 	saeNext = (!selAndEdge.empty()) ? selAndEdge[0] : -1;
 }
 
 BreakFinder::~BreakFinder() {
 }
 
-int BreakFinder::First() const {
-	return nextBreak;
-}
-
-int BreakFinder::Next() {
+TextSegment BreakFinder::Next() {
 	if (subBreak == -1) {
 		int prev = nextBreak;
-		while (nextBreak < lineEnd) {
-			if ((ll->styles[nextBreak] != ll->styles[nextBreak + 1]) ||
-					(nextBreak == saeNext) ||
-					IsControlCharacter(ll->chars[nextBreak]) || IsControlCharacter(ll->chars[nextBreak + 1])) {
-				if (nextBreak == saeNext) {
+ 		while (nextBreak < lineEnd) {
+			int charWidth = 1;
+			if (encodingFamily == efUnicode)
+				charWidth = UTF8DrawBytes(reinterpret_cast<unsigned char *>(ll->chars) + nextBreak, lineEnd - nextBreak);
+			else if (encodingFamily == efDBCS)
+				charWidth = pdoc->IsDBCSLeadByte(ll->chars[nextBreak]) ? 2 : 1;
+			Representation *repr = preprs->RepresentationFromCharacter(ll->chars + nextBreak, charWidth);
+			if ((ll->styles[nextBreak] != ll->styles[nextBreak - 1]) ||
+					repr ||
+					(nextBreak == saeNext)) {
+				while ((nextBreak >= saeNext) && (saeNext < lineEnd)) {
 					saeCurrentPos++;
-					saeNext = (saeCurrentPos < selAndEdge.size()) ? selAndEdge[saeCurrentPos] : -1;
+					saeNext = (saeCurrentPos < selAndEdge.size()) ? selAndEdge[saeCurrentPos] : lineEnd;
 				}
-				nextBreak++;
-				if ((nextBreak - prev) < lengthStartSubdivision) {
-					return nextBreak;
+				if ((nextBreak > prev) || repr) {
+					// Have a segment to report
+					if (nextBreak == prev) {
+						nextBreak += charWidth;
+					} else {
+						repr = 0;	// Optimize -> should remember repr
+					}
+					if ((nextBreak - prev) < lengthStartSubdivision) {
+						return TextSegment(prev, nextBreak - prev, repr);
+					} else {
+						break;
+					}
 				}
-				break;
 			}
-			nextBreak++;
+			nextBreak += charWidth;
 		}
 		if ((nextBreak - prev) < lengthStartSubdivision) {
-			return nextBreak;
+			return TextSegment(prev, nextBreak - prev);
 		}
 		subBreak = prev;
 	}
 	// Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
 	// For very long runs add extra breaks after spaces or if no spaces before low punctuation.
+	int startSegment = subBreak;
 	if ((nextBreak - subBreak) <= lengthEachSubdivision) {
 		subBreak = -1;
-		return nextBreak;
+		return TextSegment(startSegment, nextBreak - startSegment);
 	} else {
 		subBreak += pdoc->SafeSegment(ll->chars + subBreak, nextBreak-subBreak, lengthEachSubdivision);
 		if (subBreak >= nextBreak) {
 			subBreak = -1;
-			return nextBreak;
+			return TextSegment(startSegment, nextBreak - startSegment);
 		} else {
-			return subBreak;
+			return TextSegment(startSegment, subBreak - startSegment);
 		}
 	}
 }
 
+bool BreakFinder::More() const {
+	return (subBreak >= 0) || (nextBreak < lineEnd);
+}
+
 PositionCacheEntry::PositionCacheEntry() :
 	styleNumber(0), len(0), clock(0), positions(0) {
 }
diff --git a/src/PositionCache.h b/src/PositionCache.h
index 10afbd972..a0b805743 100644
--- a/src/PositionCache.h
+++ b/src/PositionCache.h
@@ -134,6 +134,15 @@ public:
 	void Clear();
 };
 
+struct TextSegment {
+	int start;
+	int length;
+	Representation *repr;
+	TextSegment(int start_=0, int length_=0, Representation *repr_=0) :
+		start(start_), length(length_), repr(repr_) {
+	}
+};
+
 // Class to break a line of text into shorter runs at sensible places.
 class BreakFinder {
 	LineLayout *ll;
@@ -146,6 +155,7 @@ class BreakFinder {
 	int saeNext;
 	int subBreak;
 	Document *pdoc;
+	EncodingFamily encodingFamily;
 	SpecialRepresentations *preprs;
 	void Insert(int val);
 	// Private so BreakFinder objects can not be copied
@@ -159,8 +169,8 @@ public:
 	BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_,
 		int xStart, bool breakForSelection, Document *pdoc_, SpecialRepresentations *preprs_);
 	~BreakFinder();
-	int First() const;
-	int Next();
+	TextSegment Next();
+	bool More() const;
 };
 
 class PositionCache {