1 // Scintilla source code edit control
2 /** @file PositionCache.cxx
3 ** Classes for caching layout information.
5 // Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
6 // The License.txt file describes the conditions under which this software may be distributed.
21 #include "Scintilla.h"
23 #include "SplitVector.h"
24 #include "Partitioning.h"
25 #include "RunStyles.h"
26 #include "ContractionState.h"
27 #include "CellBuffer.h"
29 #include "Indicator.h"
31 #include "LineMarker.h"
33 #include "ViewStyle.h"
34 #include "CharClassify.h"
35 #include "Decoration.h"
36 #include "CaseFolder.h"
38 #include "UniConversion.h"
39 #include "Selection.h"
40 #include "PositionCache.h"
43 using namespace Scintilla
;
46 LineLayout::LineLayout(int maxLineLength_
) :
63 widthLine(wrapWidthInfinite
),
66 bracePreviousStyles
[0] = 0;
67 bracePreviousStyles
[1] = 0;
68 Resize(maxLineLength_
);
71 LineLayout::~LineLayout() {
75 void LineLayout::Resize(int maxLineLength_
) {
76 if (maxLineLength_
> maxLineLength
) {
78 chars
= new char[maxLineLength_
+ 1];
79 styles
= new unsigned char[maxLineLength_
+ 1];
80 // Extra position allocated as sometimes the Windows
81 // GetTextExtentExPoint API writes an extra element.
82 positions
= new XYPOSITION
[maxLineLength_
+ 1 + 1];
83 maxLineLength
= maxLineLength_
;
87 void LineLayout::Free() {
98 void LineLayout::Invalidate(validLevel validity_
) {
99 if (validity
> validity_
)
100 validity
= validity_
;
103 int LineLayout::LineStart(int line
) const {
106 } else if ((line
>= lines
) || !lineStarts
) {
107 return numCharsInLine
;
109 return lineStarts
[line
];
113 int LineLayout::LineLastVisible(int line
) const {
116 } else if ((line
>= lines
-1) || !lineStarts
) {
117 return numCharsBeforeEOL
;
119 return lineStarts
[line
+1];
123 Range
LineLayout::SubLineRange(int subLine
) const {
124 return Range(LineStart(subLine
), LineLastVisible(subLine
));
127 bool LineLayout::InLine(int offset
, int line
) const {
128 return ((offset
>= LineStart(line
)) && (offset
< LineStart(line
+ 1))) ||
129 ((offset
== numCharsInLine
) && (line
== (lines
-1)));
132 void LineLayout::SetLineStart(int line
, int start
) {
133 if ((line
>= lenLineStarts
) && (line
!= 0)) {
134 int newMaxLines
= line
+ 20;
135 int *newLineStarts
= new int[newMaxLines
];
136 for (int i
= 0; i
< newMaxLines
; i
++) {
137 if (i
< lenLineStarts
)
138 newLineStarts
[i
] = lineStarts
[i
];
140 newLineStarts
[i
] = 0;
143 lineStarts
= newLineStarts
;
144 lenLineStarts
= newMaxLines
;
146 lineStarts
[line
] = start
;
149 void LineLayout::SetBracesHighlight(Range rangeLine
, const Position braces
[],
150 char bracesMatchStyle
, int xHighlight
, bool ignoreStyle
) {
151 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[0])) {
152 int braceOffset
= braces
[0] - rangeLine
.start
;
153 if (braceOffset
< numCharsInLine
) {
154 bracePreviousStyles
[0] = styles
[braceOffset
];
155 styles
[braceOffset
] = bracesMatchStyle
;
158 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[1])) {
159 int braceOffset
= braces
[1] - rangeLine
.start
;
160 if (braceOffset
< numCharsInLine
) {
161 bracePreviousStyles
[1] = styles
[braceOffset
];
162 styles
[braceOffset
] = bracesMatchStyle
;
165 if ((braces
[0] >= rangeLine
.start
&& braces
[1] <= rangeLine
.end
) ||
166 (braces
[1] >= rangeLine
.start
&& braces
[0] <= rangeLine
.end
)) {
167 xHighlightGuide
= xHighlight
;
171 void LineLayout::RestoreBracesHighlight(Range rangeLine
, const Position braces
[], bool ignoreStyle
) {
172 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[0])) {
173 int braceOffset
= braces
[0] - rangeLine
.start
;
174 if (braceOffset
< numCharsInLine
) {
175 styles
[braceOffset
] = bracePreviousStyles
[0];
178 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[1])) {
179 int braceOffset
= braces
[1] - rangeLine
.start
;
180 if (braceOffset
< numCharsInLine
) {
181 styles
[braceOffset
] = bracePreviousStyles
[1];
187 int LineLayout::FindBefore(XYPOSITION x
, int lower
, int upper
) const {
189 int middle
= (upper
+ lower
+ 1) / 2; // Round high
190 XYPOSITION posMiddle
= positions
[middle
];
196 } while (lower
< upper
);
201 int LineLayout::FindPositionFromX(XYPOSITION x
, Range range
, bool charPosition
) const {
202 int pos
= FindBefore(x
, range
.start
, range
.end
);
203 while (pos
< range
.end
) {
205 if (x
< (positions
[pos
+ 1])) {
209 if (x
< ((positions
[pos
] + positions
[pos
+ 1]) / 2)) {
218 Point
LineLayout::PointFromPosition(int posInLine
, int lineHeight
) const {
220 // In case of very long line put x at arbitrary large position
221 if (posInLine
> maxLineLength
) {
222 pt
.x
= positions
[maxLineLength
] - positions
[LineStart(lines
)];
225 for (int subLine
= 0; subLine
< lines
; subLine
++) {
226 const Range rangeSubLine
= SubLineRange(subLine
);
227 if (posInLine
>= rangeSubLine
.start
) {
228 pt
.y
= static_cast<XYPOSITION
>(subLine
*lineHeight
);
229 if (posInLine
<= rangeSubLine
.end
) {
230 pt
.x
= positions
[posInLine
] - positions
[rangeSubLine
.start
];
231 if (rangeSubLine
.start
!= 0) // Wrapped lines may be indented
241 int LineLayout::EndLineStyle() const {
242 return styles
[numCharsBeforeEOL
> 0 ? numCharsBeforeEOL
-1 : 0];
245 LineLayoutCache::LineLayoutCache() :
247 allInvalidated(false), styleClock(-1), useCount(0) {
251 LineLayoutCache::~LineLayoutCache() {
255 void LineLayoutCache::Allocate(size_t length_
) {
256 PLATFORM_ASSERT(cache
.empty());
257 allInvalidated
= false;
258 cache
.resize(length_
);
261 void LineLayoutCache::AllocateForLevel(int linesOnScreen
, int linesInDoc
) {
262 PLATFORM_ASSERT(useCount
== 0);
263 size_t lengthForLevel
= 0;
264 if (level
== llcCaret
) {
266 } else if (level
== llcPage
) {
267 lengthForLevel
= linesOnScreen
+ 1;
268 } else if (level
== llcDocument
) {
269 lengthForLevel
= linesInDoc
;
271 if (lengthForLevel
> cache
.size()) {
273 Allocate(lengthForLevel
);
275 if (lengthForLevel
< cache
.size()) {
276 for (size_t i
= lengthForLevel
; i
< cache
.size(); i
++) {
281 cache
.resize(lengthForLevel
);
283 PLATFORM_ASSERT(cache
.size() == lengthForLevel
);
286 void LineLayoutCache::Deallocate() {
287 PLATFORM_ASSERT(useCount
== 0);
288 for (size_t i
= 0; i
< cache
.size(); i
++)
293 void LineLayoutCache::Invalidate(LineLayout::validLevel validity_
) {
294 if (!cache
.empty() && !allInvalidated
) {
295 for (size_t i
= 0; i
< cache
.size(); i
++) {
297 cache
[i
]->Invalidate(validity_
);
300 if (validity_
== LineLayout::llInvalid
) {
301 allInvalidated
= true;
306 void LineLayoutCache::SetLevel(int level_
) {
307 allInvalidated
= false;
308 if ((level_
!= -1) && (level
!= level_
)) {
314 LineLayout
*LineLayoutCache::Retrieve(int lineNumber
, int lineCaret
, int maxChars
, int styleClock_
,
315 int linesOnScreen
, int linesInDoc
) {
316 AllocateForLevel(linesOnScreen
, linesInDoc
);
317 if (styleClock
!= styleClock_
) {
318 Invalidate(LineLayout::llCheckTextAndStyle
);
319 styleClock
= styleClock_
;
321 allInvalidated
= false;
324 if (level
== llcCaret
) {
326 } else if (level
== llcPage
) {
327 if (lineNumber
== lineCaret
) {
329 } else if (cache
.size() > 1) {
330 pos
= 1 + (lineNumber
% (cache
.size() - 1));
332 } else if (level
== llcDocument
) {
336 PLATFORM_ASSERT(useCount
== 0);
337 if (!cache
.empty() && (pos
< static_cast<int>(cache
.size()))) {
339 if ((cache
[pos
]->lineNumber
!= lineNumber
) ||
340 (cache
[pos
]->maxLineLength
< maxChars
)) {
346 cache
[pos
] = new LineLayout(maxChars
);
348 cache
[pos
]->lineNumber
= lineNumber
;
349 cache
[pos
]->inCache
= true;
356 ret
= new LineLayout(maxChars
);
357 ret
->lineNumber
= lineNumber
;
363 void LineLayoutCache::Dispose(LineLayout
*ll
) {
364 allInvalidated
= false;
374 // Simply pack the (maximum 4) character bytes into an int
375 static inline int KeyFromString(const char *charBytes
, size_t len
) {
376 PLATFORM_ASSERT(len
<= 4);
378 for (size_t i
=0; i
<len
&& charBytes
[i
]; i
++) {
380 k
+= static_cast<unsigned char>(charBytes
[i
]);
385 SpecialRepresentations::SpecialRepresentations() {
386 std::fill(startByteHasReprs
, startByteHasReprs
+0x100, 0);
389 void SpecialRepresentations::SetRepresentation(const char *charBytes
, const char *value
) {
390 MapRepresentation::iterator it
= mapReprs
.find(KeyFromString(charBytes
, UTF8MaxBytes
));
391 if (it
== mapReprs
.end()) {
392 // New entry so increment for first byte
393 startByteHasReprs
[static_cast<unsigned char>(charBytes
[0])]++;
395 mapReprs
[KeyFromString(charBytes
, UTF8MaxBytes
)] = Representation(value
);
398 void SpecialRepresentations::ClearRepresentation(const char *charBytes
) {
399 MapRepresentation::iterator it
= mapReprs
.find(KeyFromString(charBytes
, UTF8MaxBytes
));
400 if (it
!= mapReprs
.end()) {
402 startByteHasReprs
[static_cast<unsigned char>(charBytes
[0])]--;
406 const Representation
*SpecialRepresentations::RepresentationFromCharacter(const char *charBytes
, size_t len
) const {
407 PLATFORM_ASSERT(len
<= 4);
408 if (!startByteHasReprs
[static_cast<unsigned char>(charBytes
[0])])
410 MapRepresentation::const_iterator it
= mapReprs
.find(KeyFromString(charBytes
, len
));
411 if (it
!= mapReprs
.end()) {
412 return &(it
->second
);
417 bool SpecialRepresentations::Contains(const char *charBytes
, size_t len
) const {
418 PLATFORM_ASSERT(len
<= 4);
419 if (!startByteHasReprs
[static_cast<unsigned char>(charBytes
[0])])
421 MapRepresentation::const_iterator it
= mapReprs
.find(KeyFromString(charBytes
, len
));
422 return it
!= mapReprs
.end();
425 void SpecialRepresentations::Clear() {
427 std::fill(startByteHasReprs
, startByteHasReprs
+0x100, 0);
430 void BreakFinder::Insert(int val
) {
431 if (val
> nextBreak
) {
432 const std::vector
<int>::iterator it
= std::lower_bound(selAndEdge
.begin(), selAndEdge
.end(), val
);
433 if (it
== selAndEdge
.end()) {
434 selAndEdge
.push_back(val
);
435 } else if (*it
!= val
) {
436 selAndEdge
.insert(it
, 1, val
);
441 BreakFinder::BreakFinder(const LineLayout
*ll_
, const Selection
*psel
, int lineStart_
, int lineEnd_
, int posLineStart_
,
442 int xStart
, bool breakForSelection
, const Document
*pdoc_
, const SpecialRepresentations
*preprs_
) :
444 lineStart(lineStart_
),
446 posLineStart(posLineStart_
),
447 nextBreak(lineStart_
),
452 encodingFamily(pdoc_
->CodePageFamily()),
455 // Search for first visible break
456 // First find the first visible character
458 nextBreak
= ll
->FindBefore(static_cast<XYPOSITION
>(xStart
), lineStart
, lineEnd
);
459 // Now back to a style break
460 while ((nextBreak
> lineStart
) && (ll
->styles
[nextBreak
] == ll
->styles
[nextBreak
- 1])) {
464 if (breakForSelection
) {
465 SelectionPosition
posStart(posLineStart
);
466 SelectionPosition
posEnd(posLineStart
+ lineEnd
);
467 SelectionSegment
segmentLine(posStart
, posEnd
);
468 for (size_t r
=0; r
<psel
->Count(); r
++) {
469 SelectionSegment portion
= psel
->Range(r
).Intersect(segmentLine
);
470 if (!(portion
.start
== portion
.end
)) {
471 if (portion
.start
.IsValid())
472 Insert(portion
.start
.Position() - posLineStart
);
473 if (portion
.end
.IsValid())
474 Insert(portion
.end
.Position() - posLineStart
);
479 Insert(ll
->edgeColumn
);
481 saeNext
= (!selAndEdge
.empty()) ? selAndEdge
[0] : -1;
484 BreakFinder::~BreakFinder() {
487 TextSegment
BreakFinder::Next() {
488 if (subBreak
== -1) {
489 int prev
= nextBreak
;
490 while (nextBreak
< lineEnd
) {
492 if (encodingFamily
== efUnicode
)
493 charWidth
= UTF8DrawBytes(reinterpret_cast<unsigned char *>(ll
->chars
) + nextBreak
, lineEnd
- nextBreak
);
494 else if (encodingFamily
== efDBCS
)
495 charWidth
= pdoc
->IsDBCSLeadByte(ll
->chars
[nextBreak
]) ? 2 : 1;
496 const Representation
*repr
= preprs
->RepresentationFromCharacter(ll
->chars
+ nextBreak
, charWidth
);
497 if (((nextBreak
> 0) && (ll
->styles
[nextBreak
] != ll
->styles
[nextBreak
- 1])) ||
499 (nextBreak
== saeNext
)) {
500 while ((nextBreak
>= saeNext
) && (saeNext
< lineEnd
)) {
502 saeNext
= (saeCurrentPos
< selAndEdge
.size()) ? selAndEdge
[saeCurrentPos
] : lineEnd
;
504 if ((nextBreak
> prev
) || repr
) {
505 // Have a segment to report
506 if (nextBreak
== prev
) {
507 nextBreak
+= charWidth
;
509 repr
= 0; // Optimize -> should remember repr
511 if ((nextBreak
- prev
) < lengthStartSubdivision
) {
512 return TextSegment(prev
, nextBreak
- prev
, repr
);
518 nextBreak
+= charWidth
;
520 if ((nextBreak
- prev
) < lengthStartSubdivision
) {
521 return TextSegment(prev
, nextBreak
- prev
);
525 // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
526 // For very long runs add extra breaks after spaces or if no spaces before low punctuation.
527 int startSegment
= subBreak
;
528 if ((nextBreak
- subBreak
) <= lengthEachSubdivision
) {
530 return TextSegment(startSegment
, nextBreak
- startSegment
);
532 subBreak
+= pdoc
->SafeSegment(ll
->chars
+ subBreak
, nextBreak
-subBreak
, lengthEachSubdivision
);
533 if (subBreak
>= nextBreak
) {
535 return TextSegment(startSegment
, nextBreak
- startSegment
);
537 return TextSegment(startSegment
, subBreak
- startSegment
);
542 bool BreakFinder::More() const {
543 return (subBreak
>= 0) || (nextBreak
< lineEnd
);
546 PositionCacheEntry::PositionCacheEntry() :
547 styleNumber(0), len(0), clock(0), positions(0) {
550 void PositionCacheEntry::Set(unsigned int styleNumber_
, const char *s_
,
551 unsigned int len_
, XYPOSITION
*positions_
, unsigned int clock_
) {
553 styleNumber
= styleNumber_
;
556 if (s_
&& positions_
) {
557 positions
= new XYPOSITION
[len
+ (len
/ 4) + 1];
558 for (unsigned int i
=0; i
<len
; i
++) {
559 positions
[i
] = positions_
[i
];
561 memcpy(reinterpret_cast<char *>(reinterpret_cast<void *>(positions
+ len
)), s_
, len
);
565 PositionCacheEntry::~PositionCacheEntry() {
569 void PositionCacheEntry::Clear() {
577 bool PositionCacheEntry::Retrieve(unsigned int styleNumber_
, const char *s_
,
578 unsigned int len_
, XYPOSITION
*positions_
) const {
579 if ((styleNumber
== styleNumber_
) && (len
== len_
) &&
580 (memcmp(reinterpret_cast<char *>(reinterpret_cast<void *>(positions
+ len
)), s_
, len
)== 0)) {
581 for (unsigned int i
=0; i
<len
; i
++) {
582 positions_
[i
] = positions
[i
];
590 unsigned int PositionCacheEntry::Hash(unsigned int styleNumber_
, const char *s
, unsigned int len_
) {
591 unsigned int ret
= s
[0] << 7;
592 for (unsigned int i
=0; i
<len_
; i
++) {
603 bool PositionCacheEntry::NewerThan(const PositionCacheEntry
&other
) const {
604 return clock
> other
.clock
;
607 void PositionCacheEntry::ResetClock() {
613 PositionCache::PositionCache() {
619 PositionCache::~PositionCache() {
623 void PositionCache::Clear() {
625 for (size_t i
=0; i
<pces
.size(); i
++) {
633 void PositionCache::SetSize(size_t size_
) {
638 void PositionCache::MeasureWidths(Surface
*surface
, const ViewStyle
&vstyle
, unsigned int styleNumber
,
639 const char *s
, unsigned int len
, XYPOSITION
*positions
, Document
*pdoc
) {
642 size_t probe
= pces
.size(); // Out of bounds
643 if ((!pces
.empty()) && (len
< 30)) {
644 // Only store short strings in the cache so it doesn't churn with
645 // long comments with only a single comment.
647 // Two way associative: try two probe positions.
648 unsigned int hashValue
= PositionCacheEntry::Hash(styleNumber
, s
, len
);
649 probe
= hashValue
% pces
.size();
650 if (pces
[probe
].Retrieve(styleNumber
, s
, len
, positions
)) {
653 unsigned int probe2
= (hashValue
* 37) % pces
.size();
654 if (pces
[probe2
].Retrieve(styleNumber
, s
, len
, positions
)) {
657 // Not found. Choose the oldest of the two slots to replace
658 if (pces
[probe
].NewerThan(pces
[probe2
])) {
662 if (len
> BreakFinder::lengthStartSubdivision
) {
663 // Break up into segments
664 unsigned int startSegment
= 0;
665 XYPOSITION xStartSegment
= 0;
666 while (startSegment
< len
) {
667 unsigned int lenSegment
= pdoc
->SafeSegment(s
+ startSegment
, len
- startSegment
, BreakFinder::lengthEachSubdivision
);
668 FontAlias fontStyle
= vstyle
.styles
[styleNumber
].font
;
669 surface
->MeasureWidths(fontStyle
, s
+ startSegment
, lenSegment
, positions
+ startSegment
);
670 for (unsigned int inSeg
= 0; inSeg
< lenSegment
; inSeg
++) {
671 positions
[startSegment
+ inSeg
] += xStartSegment
;
673 xStartSegment
= positions
[startSegment
+ lenSegment
- 1];
674 startSegment
+= lenSegment
;
677 FontAlias fontStyle
= vstyle
.styles
[styleNumber
].font
;
678 surface
->MeasureWidths(fontStyle
, s
, len
, positions
);
680 if (probe
< pces
.size()) {
684 // Since there are only 16 bits for the clock, wrap it round and
685 // reset all cache entries so none get stuck with a high clock.
686 for (size_t i
=0; i
<pces
.size(); i
++) {
687 pces
[i
].ResetClock();
691 pces
[probe
].Set(styleNumber
, s
, len
, positions
, clock
);