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.
19 #include "Scintilla.h"
21 #include "SplitVector.h"
22 #include "Partitioning.h"
23 #include "RunStyles.h"
24 #include "ContractionState.h"
25 #include "CellBuffer.h"
27 #include "Indicator.h"
29 #include "LineMarker.h"
31 #include "ViewStyle.h"
32 #include "CharClassify.h"
33 #include "Decoration.h"
36 #include "Selection.h"
37 #include "PositionCache.h"
40 using namespace Scintilla
;
43 static inline bool IsControlCharacter(int ch
) {
44 // iscntrl returns true for lots of chars > 127 which are displayable
45 return ch
>= 0 && ch
< ' ';
48 LineLayout::LineLayout(int maxLineLength_
) :
69 widthLine(wrapWidthInfinite
),
72 bracePreviousStyles
[0] = 0;
73 bracePreviousStyles
[1] = 0;
74 Resize(maxLineLength_
);
77 LineLayout::~LineLayout() {
81 void LineLayout::Resize(int maxLineLength_
) {
82 if (maxLineLength_
> maxLineLength
) {
84 chars
= new char[maxLineLength_
+ 1];
85 styles
= new unsigned char[maxLineLength_
+ 1];
86 indicators
= new char[maxLineLength_
+ 1];
87 // Extra position allocated as sometimes the Windows
88 // GetTextExtentExPoint API writes an extra element.
89 positions
= new XYPOSITION
[maxLineLength_
+ 1 + 1];
90 maxLineLength
= maxLineLength_
;
94 void LineLayout::Free() {
107 void LineLayout::Invalidate(validLevel validity_
) {
108 if (validity
> validity_
)
109 validity
= validity_
;
112 int LineLayout::LineStart(int line
) const {
115 } else if ((line
>= lines
) || !lineStarts
) {
116 return numCharsInLine
;
118 return lineStarts
[line
];
122 int LineLayout::LineLastVisible(int line
) const {
125 } else if ((line
>= lines
-1) || !lineStarts
) {
126 return numCharsBeforeEOL
;
128 return lineStarts
[line
+1];
132 bool LineLayout::InLine(int offset
, int line
) const {
133 return ((offset
>= LineStart(line
)) && (offset
< LineStart(line
+ 1))) ||
134 ((offset
== numCharsInLine
) && (line
== (lines
-1)));
137 void LineLayout::SetLineStart(int line
, int start
) {
138 if ((line
>= lenLineStarts
) && (line
!= 0)) {
139 int newMaxLines
= line
+ 20;
140 int *newLineStarts
= new int[newMaxLines
];
141 for (int i
= 0; i
< newMaxLines
; i
++) {
142 if (i
< lenLineStarts
)
143 newLineStarts
[i
] = lineStarts
[i
];
145 newLineStarts
[i
] = 0;
148 lineStarts
= newLineStarts
;
149 lenLineStarts
= newMaxLines
;
151 lineStarts
[line
] = start
;
154 void LineLayout::SetBracesHighlight(Range rangeLine
, Position braces
[],
155 char bracesMatchStyle
, int xHighlight
, bool ignoreStyle
) {
156 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[0])) {
157 int braceOffset
= braces
[0] - rangeLine
.start
;
158 if (braceOffset
< numCharsInLine
) {
159 bracePreviousStyles
[0] = styles
[braceOffset
];
160 styles
[braceOffset
] = bracesMatchStyle
;
163 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[1])) {
164 int braceOffset
= braces
[1] - rangeLine
.start
;
165 if (braceOffset
< numCharsInLine
) {
166 bracePreviousStyles
[1] = styles
[braceOffset
];
167 styles
[braceOffset
] = bracesMatchStyle
;
170 if ((braces
[0] >= rangeLine
.start
&& braces
[1] <= rangeLine
.end
) ||
171 (braces
[1] >= rangeLine
.start
&& braces
[0] <= rangeLine
.end
)) {
172 xHighlightGuide
= xHighlight
;
176 void LineLayout::RestoreBracesHighlight(Range rangeLine
, Position braces
[], bool ignoreStyle
) {
177 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[0])) {
178 int braceOffset
= braces
[0] - rangeLine
.start
;
179 if (braceOffset
< numCharsInLine
) {
180 styles
[braceOffset
] = bracePreviousStyles
[0];
183 if (!ignoreStyle
&& rangeLine
.ContainsCharacter(braces
[1])) {
184 int braceOffset
= braces
[1] - rangeLine
.start
;
185 if (braceOffset
< numCharsInLine
) {
186 styles
[braceOffset
] = bracePreviousStyles
[1];
192 int LineLayout::FindBefore(XYPOSITION x
, int lower
, int upper
) const {
194 int middle
= (upper
+ lower
+ 1) / 2; // Round high
195 XYPOSITION posMiddle
= positions
[middle
];
201 } while (lower
< upper
);
205 int LineLayout::EndLineStyle() const {
206 return styles
[numCharsBeforeEOL
> 0 ? numCharsBeforeEOL
-1 : 0];
209 LineLayoutCache::LineLayoutCache() :
210 level(0), length(0), size(0), cache(0),
211 allInvalidated(false), styleClock(-1), useCount(0) {
215 LineLayoutCache::~LineLayoutCache() {
219 void LineLayoutCache::Allocate(int length_
) {
220 PLATFORM_ASSERT(cache
== NULL
);
221 allInvalidated
= false;
225 size
= (size
/ 16 + 1) * 16;
228 cache
= new LineLayout
* [size
];
230 for (int i
= 0; i
< size
; i
++)
234 void LineLayoutCache::AllocateForLevel(int linesOnScreen
, int linesInDoc
) {
235 PLATFORM_ASSERT(useCount
== 0);
236 int lengthForLevel
= 0;
237 if (level
== llcCaret
) {
239 } else if (level
== llcPage
) {
240 lengthForLevel
= linesOnScreen
+ 1;
241 } else if (level
== llcDocument
) {
242 lengthForLevel
= linesInDoc
;
244 if (lengthForLevel
> size
) {
246 Allocate(lengthForLevel
);
248 if (lengthForLevel
< length
) {
249 for (int i
= lengthForLevel
; i
< length
; i
++) {
254 length
= lengthForLevel
;
256 PLATFORM_ASSERT(length
== lengthForLevel
);
257 PLATFORM_ASSERT(cache
!= NULL
|| length
== 0);
260 void LineLayoutCache::Deallocate() {
261 PLATFORM_ASSERT(useCount
== 0);
262 for (int i
= 0; i
< length
; i
++)
270 void LineLayoutCache::Invalidate(LineLayout::validLevel validity_
) {
271 if (cache
&& !allInvalidated
) {
272 for (int i
= 0; i
< length
; i
++) {
274 cache
[i
]->Invalidate(validity_
);
277 if (validity_
== LineLayout::llInvalid
) {
278 allInvalidated
= true;
283 void LineLayoutCache::SetLevel(int level_
) {
284 allInvalidated
= false;
285 if ((level_
!= -1) && (level
!= level_
)) {
291 LineLayout
*LineLayoutCache::Retrieve(int lineNumber
, int lineCaret
, int maxChars
, int styleClock_
,
292 int linesOnScreen
, int linesInDoc
) {
293 AllocateForLevel(linesOnScreen
, linesInDoc
);
294 if (styleClock
!= styleClock_
) {
295 Invalidate(LineLayout::llCheckTextAndStyle
);
296 styleClock
= styleClock_
;
298 allInvalidated
= false;
301 if (level
== llcCaret
) {
303 } else if (level
== llcPage
) {
304 if (lineNumber
== lineCaret
) {
306 } else if (length
> 1) {
307 pos
= 1 + (lineNumber
% (length
- 1));
309 } else if (level
== llcDocument
) {
313 PLATFORM_ASSERT(useCount
== 0);
314 if (cache
&& (pos
< length
)) {
316 if ((cache
[pos
]->lineNumber
!= lineNumber
) ||
317 (cache
[pos
]->maxLineLength
< maxChars
)) {
323 cache
[pos
] = new LineLayout(maxChars
);
326 cache
[pos
]->lineNumber
= lineNumber
;
327 cache
[pos
]->inCache
= true;
335 ret
= new LineLayout(maxChars
);
336 ret
->lineNumber
= lineNumber
;
342 void LineLayoutCache::Dispose(LineLayout
*ll
) {
343 allInvalidated
= false;
353 void BreakFinder::Insert(int val
) {
355 if (saeLen
>= saeSize
) {
357 int *selAndEdgeNew
= new int[saeSize
];
358 for (unsigned int j
= 0; j
<saeLen
; j
++) {
359 selAndEdgeNew
[j
] = selAndEdge
[j
];
362 selAndEdge
= selAndEdgeNew
;
365 if (val
>= nextBreak
) {
366 for (unsigned int j
= 0; j
<saeLen
; j
++) {
367 if (val
== selAndEdge
[j
]) {
370 if (val
< selAndEdge
[j
]) {
371 for (unsigned int k
= saeLen
; k
>j
; k
--) {
372 selAndEdge
[k
] = selAndEdge
[k
-1];
379 // Not less than any so append
380 selAndEdge
[saeLen
++] = val
;
384 extern bool BadUTF(const char *s
, int len
, int &trailBytes
);
386 static int NextBadU(const char *s
, int p
, int len
, int &trailBytes
) {
389 if (BadUTF(s
+ p
, len
- p
, trailBytes
))
395 BreakFinder::BreakFinder(LineLayout
*ll_
, int lineStart_
, int lineEnd_
, int posLineStart_
,
396 int xStart
, bool breakForSelection
, Document
*pdoc_
) :
398 lineStart(lineStart_
),
400 posLineStart(posLineStart_
),
401 nextBreak(lineStart_
),
409 selAndEdge
= new int[saeSize
];
410 for (unsigned int j
=0; j
< saeSize
; j
++) {
414 // Search for first visible break
415 // First find the first visible character
416 nextBreak
= ll
->FindBefore(xStart
, lineStart
, lineEnd
);
417 // Now back to a style break
418 while ((nextBreak
> lineStart
) && (ll
->styles
[nextBreak
] == ll
->styles
[nextBreak
- 1])) {
422 if (breakForSelection
) {
423 SelectionPosition
posStart(posLineStart
);
424 SelectionPosition
posEnd(posLineStart
+ lineEnd
);
425 SelectionSegment
segmentLine(posStart
, posEnd
);
426 for (size_t r
=0; r
<ll
->psel
->Count(); r
++) {
427 SelectionSegment portion
= ll
->psel
->Range(r
).Intersect(segmentLine
);
428 if (!(portion
.start
== portion
.end
)) {
429 if (portion
.start
.IsValid())
430 Insert(portion
.start
.Position() - posLineStart
- 1);
431 if (portion
.end
.IsValid())
432 Insert(portion
.end
.Position() - posLineStart
- 1);
437 Insert(ll
->edgeColumn
- 1);
440 if (pdoc
&& (SC_CP_UTF8
== pdoc
->dbcsCodePage
)) {
442 for (int pos
= -1;;) {
443 pos
= NextBadU(ll
->chars
, pos
, lineEnd
, trailBytes
);
450 saeNext
= (saeLen
> 0) ? selAndEdge
[0] : -1;
453 BreakFinder::~BreakFinder() {
457 int BreakFinder::First() const {
461 int BreakFinder::Next() {
462 if (subBreak
== -1) {
463 int prev
= nextBreak
;
464 while (nextBreak
< lineEnd
) {
465 if ((ll
->styles
[nextBreak
] != ll
->styles
[nextBreak
+ 1]) ||
466 (nextBreak
== saeNext
) ||
467 IsControlCharacter(ll
->chars
[nextBreak
]) || IsControlCharacter(ll
->chars
[nextBreak
+ 1])) {
468 if (nextBreak
== saeNext
) {
470 saeNext
= (saeLen
> saeCurrentPos
) ? selAndEdge
[saeCurrentPos
] : -1;
473 if ((nextBreak
- prev
) < lengthStartSubdivision
) {
480 if ((nextBreak
- prev
) < lengthStartSubdivision
) {
485 // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
486 // For very long runs add extra breaks after spaces or if no spaces before low punctuation.
487 if ((nextBreak
- subBreak
) <= lengthEachSubdivision
) {
491 subBreak
+= pdoc
->SafeSegment(ll
->chars
+ subBreak
, nextBreak
-subBreak
, lengthEachSubdivision
);
492 if (subBreak
>= nextBreak
) {
501 PositionCacheEntry::PositionCacheEntry() :
502 styleNumber(0), len(0), clock(0), positions(0) {
505 void PositionCacheEntry::Set(unsigned int styleNumber_
, const char *s_
,
506 unsigned int len_
, XYPOSITION
*positions_
, unsigned int clock_
) {
508 styleNumber
= styleNumber_
;
511 if (s_
&& positions_
) {
512 positions
= new XYPOSITION
[len
+ (len
+ 1) / 2];
513 for (unsigned int i
=0; i
<len
; i
++) {
514 positions
[i
] = static_cast<XYPOSITION
>(positions_
[i
]);
516 memcpy(reinterpret_cast<char *>(positions
+ len
), s_
, len
);
520 PositionCacheEntry::~PositionCacheEntry() {
524 void PositionCacheEntry::Clear() {
532 bool PositionCacheEntry::Retrieve(unsigned int styleNumber_
, const char *s_
,
533 unsigned int len_
, XYPOSITION
*positions_
) const {
534 if ((styleNumber
== styleNumber_
) && (len
== len_
) &&
535 (memcmp(reinterpret_cast<char *>(positions
+ len
), s_
, len
)== 0)) {
536 for (unsigned int i
=0; i
<len
; i
++) {
537 positions_
[i
] = positions
[i
];
545 int PositionCacheEntry::Hash(unsigned int styleNumber_
, const char *s
, unsigned int len_
) {
546 unsigned int ret
= s
[0] << 7;
547 for (unsigned int i
=0; i
<len_
; i
++) {
558 bool PositionCacheEntry::NewerThan(const PositionCacheEntry
&other
) const {
559 return clock
> other
.clock
;
562 void PositionCacheEntry::ResetClock() {
568 PositionCache::PositionCache() {
571 pces
= new PositionCacheEntry
[size
];
575 PositionCache::~PositionCache() {
580 void PositionCache::Clear() {
582 for (size_t i
=0; i
<size
; i
++) {
590 void PositionCache::SetSize(size_t size_
) {
594 pces
= new PositionCacheEntry
[size
];
597 void PositionCache::MeasureWidths(Surface
*surface
, ViewStyle
&vstyle
, unsigned int styleNumber
,
598 const char *s
, unsigned int len
, XYPOSITION
*positions
, Document
*pdoc
) {
602 if ((size
> 0) && (len
< 30)) {
603 // Only store short strings in the cache so it doesn't churn with
604 // long comments with only a single comment.
606 // Two way associative: try two probe positions.
607 int hashValue
= PositionCacheEntry::Hash(styleNumber
, s
, len
);
608 probe
= static_cast<int>(hashValue
% size
);
609 if (pces
[probe
].Retrieve(styleNumber
, s
, len
, positions
)) {
612 int probe2
= static_cast<int>((hashValue
* 37) % size
);
613 if (pces
[probe2
].Retrieve(styleNumber
, s
, len
, positions
)) {
616 // Not found. Choose the oldest of the two slots to replace
617 if (pces
[probe
].NewerThan(pces
[probe2
])) {
621 if (len
> BreakFinder::lengthStartSubdivision
) {
622 // Break up into segments
623 unsigned int startSegment
= 0;
624 XYPOSITION xStartSegment
= 0;
625 while (startSegment
< len
) {
626 unsigned int lenSegment
= pdoc
->SafeSegment(s
+ startSegment
, len
- startSegment
, BreakFinder::lengthEachSubdivision
);
627 surface
->MeasureWidths(vstyle
.styles
[styleNumber
].font
, s
+ startSegment
, lenSegment
, positions
+ startSegment
);
628 for (unsigned int inSeg
= 0; inSeg
< lenSegment
; inSeg
++) {
629 positions
[startSegment
+ inSeg
] += xStartSegment
;
631 xStartSegment
= positions
[startSegment
+ lenSegment
- 1];
632 startSegment
+= lenSegment
;
635 surface
->MeasureWidths(vstyle
.styles
[styleNumber
].font
, s
, len
, positions
);
640 // Since there are only 16 bits for the clock, wrap it round and
641 // reset all cache entries so none get stuck with a high clock.
642 for (size_t i
=0; i
<size
; i
++) {
643 pces
[i
].ResetClock();
647 pces
[probe
].Set(styleNumber
, s
, len
, positions
, clock
);