1// Scintilla source code edit control
2/** @file PositionCache.cxx
3 ** Classes for caching layout information.
4 **/
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.
7
8#include <cstddef>
9#include <cstdlib>
10#include <cstdint>
11#include <cstring>
12#include <cmath>
13
14#include <stdexcept>
15#include <string>
16#include <string_view>
17#include <vector>
18#include <map>
19#include <set>
20#include <optional>
21#include <algorithm>
22#include <iterator>
23#include <memory>
24
25#include "ScintillaTypes.h"
26#include "ScintillaMessages.h"
27#include "ILoader.h"
28#include "ILexer.h"
29
30#include "Debugging.h"
31#include "Geometry.h"
32#include "Platform.h"
33
34#include "CharacterType.h"
35#include "CharacterCategoryMap.h"
36#include "Position.h"
37#include "UniqueString.h"
38#include "SplitVector.h"
39#include "Partitioning.h"
40#include "RunStyles.h"
41#include "ContractionState.h"
42#include "CellBuffer.h"
43#include "KeyMap.h"
44#include "Indicator.h"
45#include "LineMarker.h"
46#include "Style.h"
47#include "ViewStyle.h"
48#include "CharClassify.h"
49#include "Decoration.h"
50#include "CaseFolder.h"
51#include "Document.h"
52#include "UniConversion.h"
53#include "Selection.h"
54#include "PositionCache.h"
55
56using namespace Scintilla;
57using namespace Scintilla::Internal;
58
59void BidiData::Resize(size_t maxLineLength_) {
60 stylesFonts.resize(maxLineLength_ + 1);
61 widthReprs.resize(maxLineLength_ + 1);
62}
63
64LineLayout::LineLayout(Sci::Line lineNumber_, int maxLineLength_) :
65 lenLineStarts(0),
66 lineNumber(lineNumber_),
67 maxLineLength(-1),
68 numCharsInLine(0),
69 numCharsBeforeEOL(0),
70 validity(ValidLevel::invalid),
71 xHighlightGuide(0),
72 highlightColumn(false),
73 containsCaret(false),
74 edgeColumn(0),
75 bracePreviousStyles{},
76 widthLine(wrapWidthInfinite),
77 lines(1),
78 wrapIndent(0) {
79 Resize(maxLineLength_);
80}
81
82LineLayout::~LineLayout() {
83 Free();
84}
85
86void LineLayout::Resize(int maxLineLength_) {
87 if (maxLineLength_ > maxLineLength) {
88 Free();
89 chars = std::make_unique<char[]>(maxLineLength_ + 1);
90 styles = std::make_unique<unsigned char []>(maxLineLength_ + 1);
91 // Extra position allocated as sometimes the Windows
92 // GetTextExtentExPoint API writes an extra element.
93 positions = std::make_unique<XYPOSITION []>(maxLineLength_ + 1 + 1);
94 if (bidiData) {
95 bidiData->Resize(maxLineLength_);
96 }
97
98 maxLineLength = maxLineLength_;
99 }
100}
101
102void LineLayout::EnsureBidiData() {
103 if (!bidiData) {
104 bidiData = std::make_unique<BidiData>();
105 bidiData->Resize(maxLineLength);
106 }
107}
108
109void LineLayout::Free() noexcept {
110 chars.reset();
111 styles.reset();
112 positions.reset();
113 lineStarts.reset();
114 bidiData.reset();
115}
116
117void LineLayout::Invalidate(ValidLevel validity_) noexcept {
118 if (validity > validity_)
119 validity = validity_;
120}
121
122Sci::Line LineLayout::LineNumber() const noexcept {
123 return lineNumber;
124}
125
126bool LineLayout::CanHold(Sci::Line lineDoc, int lineLength_) const noexcept {
127 return (lineNumber == lineDoc) && (lineLength_ <= maxLineLength);
128}
129
130int LineLayout::LineStart(int line) const noexcept {
131 if (line <= 0) {
132 return 0;
133 } else if ((line >= lines) || !lineStarts) {
134 return numCharsInLine;
135 } else {
136 return lineStarts[line];
137 }
138}
139
140int LineLayout::LineLength(int line) const noexcept {
141 if (!lineStarts) {
142 return numCharsInLine;
143 } if (line >= lines - 1) {
144 return numCharsInLine - lineStarts[line];
145 } else {
146 return lineStarts[line + 1] - lineStarts[line];
147 }
148}
149
150int LineLayout::LineLastVisible(int line, Scope scope) const noexcept {
151 if (line < 0) {
152 return 0;
153 } else if ((line >= lines-1) || !lineStarts) {
154 return scope == Scope::visibleOnly ? numCharsBeforeEOL : numCharsInLine;
155 } else {
156 return lineStarts[line+1];
157 }
158}
159
160Range LineLayout::SubLineRange(int subLine, Scope scope) const noexcept {
161 return Range(LineStart(subLine), LineLastVisible(subLine, scope));
162}
163
164bool LineLayout::InLine(int offset, int line) const noexcept {
165 return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) ||
166 ((offset == numCharsInLine) && (line == (lines-1)));
167}
168
169int LineLayout::SubLineFromPosition(int posInLine, PointEnd pe) const noexcept {
170 if (!lineStarts || (posInLine > maxLineLength)) {
171 return lines - 1;
172 }
173
174 for (int line = 0; line < lines; line++) {
175 if (FlagSet(pe, PointEnd::subLineEnd)) {
176 // Return subline not start of next
177 if (lineStarts[line + 1] <= posInLine + 1)
178 return line;
179 } else {
180 if (lineStarts[line + 1] <= posInLine)
181 return line;
182 }
183 }
184
185 return lines - 1;
186}
187
188void LineLayout::SetLineStart(int line, int start) {
189 if ((line >= lenLineStarts) && (line != 0)) {
190 const int newMaxLines = line + 20;
191 std::unique_ptr<int[]> newLineStarts = std::make_unique<int[]>(newMaxLines);
192 if (lenLineStarts) {
193 std::copy(lineStarts.get(), lineStarts.get() + lenLineStarts, newLineStarts.get());
194 }
195 lineStarts = std::move(newLineStarts);
196 lenLineStarts = newMaxLines;
197 }
198 lineStarts[line] = start;
199}
200
201void LineLayout::SetBracesHighlight(Range rangeLine, const Sci::Position braces[],
202 char bracesMatchStyle, int xHighlight, bool ignoreStyle) {
203 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) {
204 const Sci::Position braceOffset = braces[0] - rangeLine.start;
205 if (braceOffset < numCharsInLine) {
206 bracePreviousStyles[0] = styles[braceOffset];
207 styles[braceOffset] = bracesMatchStyle;
208 }
209 }
210 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) {
211 const Sci::Position braceOffset = braces[1] - rangeLine.start;
212 if (braceOffset < numCharsInLine) {
213 bracePreviousStyles[1] = styles[braceOffset];
214 styles[braceOffset] = bracesMatchStyle;
215 }
216 }
217 if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
218 (braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
219 xHighlightGuide = xHighlight;
220 }
221}
222
223void LineLayout::RestoreBracesHighlight(Range rangeLine, const Sci::Position braces[], bool ignoreStyle) {
224 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) {
225 const Sci::Position braceOffset = braces[0] - rangeLine.start;
226 if (braceOffset < numCharsInLine) {
227 styles[braceOffset] = bracePreviousStyles[0];
228 }
229 }
230 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) {
231 const Sci::Position braceOffset = braces[1] - rangeLine.start;
232 if (braceOffset < numCharsInLine) {
233 styles[braceOffset] = bracePreviousStyles[1];
234 }
235 }
236 xHighlightGuide = 0;
237}
238
239int LineLayout::FindBefore(XYPOSITION x, Range range) const noexcept {
240 Sci::Position lower = range.start;
241 Sci::Position upper = range.end;
242 do {
243 const Sci::Position middle = (upper + lower + 1) / 2; // Round high
244 const XYPOSITION posMiddle = positions[middle];
245 if (x < posMiddle) {
246 upper = middle - 1;
247 } else {
248 lower = middle;
249 }
250 } while (lower < upper);
251 return static_cast<int>(lower);
252}
253
254
255int LineLayout::FindPositionFromX(XYPOSITION x, Range range, bool charPosition) const noexcept {
256 int pos = FindBefore(x, range);
257 while (pos < range.end) {
258 if (charPosition) {
259 if (x < (positions[pos + 1])) {
260 return pos;
261 }
262 } else {
263 if (x < ((positions[pos] + positions[pos + 1]) / 2)) {
264 return pos;
265 }
266 }
267 pos++;
268 }
269 return static_cast<int>(range.end);
270}
271
272Point LineLayout::PointFromPosition(int posInLine, int lineHeight, PointEnd pe) const noexcept {
273 Point pt;
274 // In case of very long line put x at arbitrary large position
275 if (posInLine > maxLineLength) {
276 pt.x = positions[maxLineLength] - positions[LineStart(lines)];
277 }
278
279 for (int subLine = 0; subLine < lines; subLine++) {
280 const Range rangeSubLine = SubLineRange(subLine, Scope::visibleOnly);
281 if (posInLine >= rangeSubLine.start) {
282 pt.y = static_cast<XYPOSITION>(subLine*lineHeight);
283 if (posInLine <= rangeSubLine.end) {
284 pt.x = positions[posInLine] - positions[rangeSubLine.start];
285 if (rangeSubLine.start != 0) // Wrapped lines may be indented
286 pt.x += wrapIndent;
287 if (FlagSet(pe, PointEnd::subLineEnd)) // Return end of first subline not start of next
288 break;
289 } else if (FlagSet(pe, PointEnd::lineEnd) && (subLine == (lines-1))) {
290 pt.x = positions[numCharsInLine] - positions[rangeSubLine.start];
291 if (rangeSubLine.start != 0) // Wrapped lines may be indented
292 pt.x += wrapIndent;
293 }
294 } else {
295 break;
296 }
297 }
298 return pt;
299}
300
301int LineLayout::EndLineStyle() const noexcept {
302 return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0];
303}
304
305ScreenLine::ScreenLine(
306 const LineLayout *ll_,
307 int subLine,
308 const ViewStyle &vs,
309 XYPOSITION width_,
310 int tabWidthMinimumPixels_) :
311 ll(ll_),
312 start(ll->LineStart(subLine)),
313 len(ll->LineLength(subLine)),
314 width(width_),
315 height(static_cast<float>(vs.lineHeight)),
316 ctrlCharPadding(vs.ctrlCharPadding),
317 tabWidth(vs.tabWidth),
318 tabWidthMinimumPixels(tabWidthMinimumPixels_) {
319}
320
321ScreenLine::~ScreenLine() {
322}
323
324std::string_view ScreenLine::Text() const {
325 return std::string_view(&ll->chars[start], len);
326}
327
328size_t ScreenLine::Length() const {
329 return len;
330}
331
332size_t ScreenLine::RepresentationCount() const {
333 return std::count_if(&ll->bidiData->widthReprs[start],
334 &ll->bidiData->widthReprs[start + len],
335 [](XYPOSITION w) noexcept { return w > 0.0f; });
336}
337
338XYPOSITION ScreenLine::Width() const {
339 return width;
340}
341
342XYPOSITION ScreenLine::Height() const {
343 return height;
344}
345
346XYPOSITION ScreenLine::TabWidth() const {
347 return tabWidth;
348}
349
350XYPOSITION ScreenLine::TabWidthMinimumPixels() const {
351 return static_cast<XYPOSITION>(tabWidthMinimumPixels);
352}
353
354const Font *ScreenLine::FontOfPosition(size_t position) const {
355 return ll->bidiData->stylesFonts[start + position].get();
356}
357
358XYPOSITION ScreenLine::RepresentationWidth(size_t position) const {
359 return ll->bidiData->widthReprs[start + position];
360}
361
362XYPOSITION ScreenLine::TabPositionAfter(XYPOSITION xPosition) const {
363 return (std::floor((xPosition + TabWidthMinimumPixels()) / TabWidth()) + 1) * TabWidth();
364}
365
366LineLayoutCache::LineLayoutCache() :
367 level(LineCache::None),
368 allInvalidated(false), styleClock(-1) {
369}
370
371LineLayoutCache::~LineLayoutCache() = default;
372
373namespace {
374
375constexpr size_t AlignUp(size_t value, size_t alignment) noexcept {
376 return ((value - 1) / alignment + 1) * alignment;
377}
378
379constexpr size_t alignmentLLC = 20;
380
381constexpr bool GraphicASCII(char ch) noexcept {
382 return ch >= ' ' && ch <= '~';
383}
384
385bool AllGraphicASCII(std::string_view text) noexcept {
386 return std::all_of(text.cbegin(), text.cend(), GraphicASCII);
387}
388
389}
390
391
392size_t LineLayoutCache::EntryForLine(Sci::Line line) const noexcept {
393 switch (level) {
394 case LineCache::None:
395 return 0;
396 case LineCache::Caret:
397 return 0;
398 case LineCache::Page:
399 return 1 + (line % (cache.size() - 1));
400 case LineCache::Document:
401 return line;
402 }
403 return 0;
404}
405
406void LineLayoutCache::AllocateForLevel(Sci::Line linesOnScreen, Sci::Line linesInDoc) {
407 size_t lengthForLevel = 0;
408 if (level == LineCache::Caret) {
409 lengthForLevel = 1;
410 } else if (level == LineCache::Page) {
411 lengthForLevel = AlignUp(linesOnScreen + 1, alignmentLLC);
412 } else if (level == LineCache::Document) {
413 lengthForLevel = AlignUp(linesInDoc, alignmentLLC);
414 }
415
416 if (lengthForLevel != cache.size()) {
417 allInvalidated = false;
418 cache.resize(lengthForLevel);
419 // Cache::none -> no entries
420 // Cache::caret -> 1 entry can take any line
421 // Cache::document -> entry per line so each line in correct entry after resize
422 if (level == LineCache::Page) {
423 // Cache::page -> locates lines in particular entries which may be incorrect after
424 // a resize so move them to correct entries.
425 for (size_t i = 1; i < cache.size();) {
426 size_t increment = 1;
427 if (cache[i]) {
428 const size_t posForLine = EntryForLine(cache[i]->LineNumber());
429 if (posForLine != i) {
430 if (cache[posForLine]) {
431 if (EntryForLine(cache[posForLine]->LineNumber()) == posForLine) {
432 // [posForLine] already holds line that is in correct place
433 cache[i].reset(); // This line has nowhere to go so reset it.
434 } else {
435 std::swap(cache[i], cache[posForLine]);
436 increment = 0;
437 // Don't increment as newly swapped in value may have to move
438 }
439 } else {
440 cache[posForLine] = std::move(cache[i]);
441 }
442 }
443 }
444 i += increment;
445 }
446
447#ifdef CHECK_LLC
448 for (size_t i = 1; i < cache.size(); i++) {
449 if (cache[i]) {
450 PLATFORM_ASSERT(EntryForLine(cache[i]->LineNumber()) == i);
451 }
452 }
453#endif
454 }
455 }
456 PLATFORM_ASSERT(cache.size() == lengthForLevel);
457}
458
459void LineLayoutCache::Deallocate() noexcept {
460 cache.clear();
461}
462
463void LineLayoutCache::Invalidate(LineLayout::ValidLevel validity_) noexcept {
464 if (!cache.empty() && !allInvalidated) {
465 for (const std::shared_ptr<LineLayout> &ll : cache) {
466 if (ll) {
467 ll->Invalidate(validity_);
468 }
469 }
470 if (validity_ == LineLayout::ValidLevel::invalid) {
471 allInvalidated = true;
472 }
473 }
474}
475
476void LineLayoutCache::SetLevel(LineCache level_) noexcept {
477 if (level != level_) {
478 level = level_;
479 allInvalidated = false;
480 cache.clear();
481 }
482}
483
484std::shared_ptr<LineLayout> LineLayoutCache::Retrieve(Sci::Line lineNumber, Sci::Line lineCaret, int maxChars, int styleClock_,
485 Sci::Line linesOnScreen, Sci::Line linesInDoc) {
486 AllocateForLevel(linesOnScreen, linesInDoc);
487 if (styleClock != styleClock_) {
488 Invalidate(LineLayout::ValidLevel::checkTextAndStyle);
489 styleClock = styleClock_;
490 }
491 allInvalidated = false;
492 size_t pos = 0;
493 if (level == LineCache::Page) {
494 // If first entry is this line then just reuse it.
495 if (!(cache[0] && (cache[0]->lineNumber == lineNumber))) {
496 const size_t posForLine = EntryForLine(lineNumber);
497 if (lineNumber == lineCaret) {
498 // Use position 0 for caret line.
499 if (cache[0]) {
500 // Another line is currently in [0] so move it out to its normal position.
501 // Since it was recently the caret line its likely to be needed soon.
502 const size_t posNewForEntry0 = EntryForLine(cache[0]->lineNumber);
503 if (posForLine == posNewForEntry0) {
504 std::swap(cache[0], cache[posNewForEntry0]);
505 } else {
506 cache[posNewForEntry0] = std::move(cache[0]);
507 }
508 }
509 if (cache[posForLine] && (cache[posForLine]->lineNumber == lineNumber)) {
510 // Caret line is currently somewhere else so move it to [0].
511 cache[0] = std::move(cache[posForLine]);
512 }
513 } else {
514 pos = posForLine;
515 }
516 }
517 } else if (level == LineCache::Document) {
518 pos = lineNumber;
519 }
520
521 if (pos < cache.size()) {
522 if (cache[pos] && !cache[pos]->CanHold(lineNumber, maxChars)) {
523 cache[pos].reset();
524 }
525 if (!cache[pos]) {
526 cache[pos] = std::make_shared<LineLayout>(lineNumber, maxChars);
527 }
528#ifdef CHECK_LLC
529 // Expensive check that there is only one entry for any line number
530 std::vector<bool> linesInCache(linesInDoc);
531 for (const auto &entry : cache) {
532 if (entry) {
533 PLATFORM_ASSERT(!linesInCache[entry->LineNumber()]);
534 linesInCache[entry->LineNumber()] = true;
535 }
536 }
537#endif
538 return cache[pos];
539 }
540
541 // Only reach here for level == Cache::none
542 return std::make_shared<LineLayout>(lineNumber, maxChars);
543}
544
545namespace {
546
547// Simply pack the (maximum 4) character bytes into an int
548constexpr unsigned int KeyFromString(std::string_view charBytes) noexcept {
549 PLATFORM_ASSERT(charBytes.length() <= 4);
550 unsigned int k=0;
551 for (const unsigned char uc : charBytes) {
552 k = k * 0x100 + uc;
553 }
554 return k;
555}
556
557constexpr unsigned int representationKeyCrLf = KeyFromString("\r\n");
558
559}
560
561void SpecialRepresentations::SetRepresentation(std::string_view charBytes, std::string_view value) {
562 if ((charBytes.length() <= 4) && (value.length() <= Representation::maxLength)) {
563 const unsigned int key = KeyFromString(charBytes);
564 const bool inserted = mapReprs.insert_or_assign(key, Representation(value)).second;
565 if (inserted) {
566 // New entry so increment for first byte
567 const unsigned char ucStart = charBytes.empty() ? 0 : charBytes[0];
568 startByteHasReprs[ucStart]++;
569 if (key > maxKey) {
570 maxKey = key;
571 }
572 if (key == representationKeyCrLf) {
573 crlf = true;
574 }
575 }
576 }
577}
578
579void SpecialRepresentations::SetRepresentationAppearance(std::string_view charBytes, RepresentationAppearance appearance) {
580 if (charBytes.length() <= 4) {
581 const unsigned int key = KeyFromString(charBytes);
582 const MapRepresentation::iterator it = mapReprs.find(key);
583 if (it == mapReprs.end()) {
584 // Not present so fail
585 return;
586 }
587 it->second.appearance = appearance;
588 }
589}
590
591void SpecialRepresentations::SetRepresentationColour(std::string_view charBytes, ColourRGBA colour) {
592 if (charBytes.length() <= 4) {
593 const unsigned int key = KeyFromString(charBytes);
594 const MapRepresentation::iterator it = mapReprs.find(key);
595 if (it == mapReprs.end()) {
596 // Not present so fail
597 return;
598 }
599 it->second.appearance = it->second.appearance | RepresentationAppearance::Colour;
600 it->second.colour = colour;
601 }
602}
603
604void SpecialRepresentations::ClearRepresentation(std::string_view charBytes) {
605 if (charBytes.length() <= 4) {
606 const unsigned int key = KeyFromString(charBytes);
607 const MapRepresentation::iterator it = mapReprs.find(key);
608 if (it != mapReprs.end()) {
609 mapReprs.erase(it);
610 const unsigned char ucStart = charBytes.empty() ? 0 : charBytes[0];
611 startByteHasReprs[ucStart]--;
612 if (key == maxKey && startByteHasReprs[ucStart] == 0) {
613 maxKey = mapReprs.empty() ? 0 : mapReprs.crbegin()->first;
614 }
615 if (key == representationKeyCrLf) {
616 crlf = false;
617 }
618 }
619 }
620}
621
622const Representation *SpecialRepresentations::GetRepresentation(std::string_view charBytes) const {
623 const unsigned int key = KeyFromString(charBytes);
624 if (key > maxKey) {
625 return nullptr;
626 }
627 const MapRepresentation::const_iterator it = mapReprs.find(key);
628 if (it != mapReprs.end()) {
629 return &(it->second);
630 }
631 return nullptr;
632}
633
634const Representation *SpecialRepresentations::RepresentationFromCharacter(std::string_view charBytes) const {
635 if (charBytes.length() <= 4) {
636 const unsigned char ucStart = charBytes.empty() ? 0 : charBytes[0];
637 if (!startByteHasReprs[ucStart])
638 return nullptr;
639 return GetRepresentation(charBytes);
640 }
641 return nullptr;
642}
643
644void SpecialRepresentations::Clear() {
645 mapReprs.clear();
646 constexpr unsigned short none = 0;
647 std::fill(startByteHasReprs, std::end(startByteHasReprs), none);
648 maxKey = 0;
649 crlf = false;
650}
651
652void BreakFinder::Insert(Sci::Position val) {
653 const int posInLine = static_cast<int>(val);
654 if (posInLine > nextBreak) {
655 const std::vector<int>::iterator it = std::lower_bound(selAndEdge.begin(), selAndEdge.end(), posInLine);
656 if (it == selAndEdge.end()) {
657 selAndEdge.push_back(posInLine);
658 } else if (*it != posInLine) {
659 selAndEdge.insert(it, 1, posInLine);
660 }
661 }
662}
663
664BreakFinder::BreakFinder(const LineLayout *ll_, const Selection *psel, Range lineRange_, Sci::Position posLineStart_,
665 XYPOSITION xStart, BreakFor breakFor, const Document *pdoc_, const SpecialRepresentations *preprs_, const ViewStyle *pvsDraw) :
666 ll(ll_),
667 lineRange(lineRange_),
668 posLineStart(posLineStart_),
669 nextBreak(static_cast<int>(lineRange_.start)),
670 saeCurrentPos(0),
671 saeNext(0),
672 subBreak(-1),
673 pdoc(pdoc_),
674 encodingFamily(pdoc_->CodePageFamily()),
675 preprs(preprs_) {
676
677 // Search for first visible break
678 // First find the first visible character
679 if (xStart > 0.0f)
680 nextBreak = ll->FindBefore(xStart, lineRange);
681 // Now back to a style break
682 while ((nextBreak > lineRange.start) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
683 nextBreak--;
684 }
685
686 if (FlagSet(breakFor, BreakFor::Selection)) {
687 const SelectionPosition posStart(posLineStart);
688 const SelectionPosition posEnd(posLineStart + lineRange.end);
689 const SelectionSegment segmentLine(posStart, posEnd);
690 for (size_t r=0; r<psel->Count(); r++) {
691 const SelectionSegment portion = psel->Range(r).Intersect(segmentLine);
692 if (!(portion.start == portion.end)) {
693 if (portion.start.IsValid())
694 Insert(portion.start.Position() - posLineStart);
695 if (portion.end.IsValid())
696 Insert(portion.end.Position() - posLineStart);
697 }
698 }
699 // On the curses platform, the terminal is drawing its own caret, so add breaks around the
700 // caret in the main selection in order to help prevent the selection from being drawn in
701 // the caret's cell.
702 if (FlagSet(pvsDraw->caret.style, CaretStyle::Curses) && !psel->RangeMain().Empty()) {
703 const Sci::Position caretPos = psel->RangeMain().caret.Position();
704 const Sci::Position anchorPos = psel->RangeMain().anchor.Position();
705 if (caretPos < anchorPos) {
706 const Sci::Position nextPos = pdoc->MovePositionOutsideChar(caretPos + 1, 1);
707 Insert(nextPos - posLineStart);
708 } else if (caretPos > anchorPos && pvsDraw->DrawCaretInsideSelection(false, false)) {
709 const Sci::Position prevPos = pdoc->MovePositionOutsideChar(caretPos - 1, -1);
710 if (prevPos > anchorPos)
711 Insert(prevPos - posLineStart);
712 }
713 }
714 }
715 if (FlagSet(breakFor, BreakFor::Foreground) && pvsDraw->indicatorsSetFore) {
716 for (const IDecoration *deco : pdoc->decorations->View()) {
717 if (pvsDraw->indicators[deco->Indicator()].OverridesTextFore()) {
718 Sci::Position startPos = deco->EndRun(posLineStart);
719 while (startPos < (posLineStart + lineRange.end)) {
720 Insert(startPos - posLineStart);
721 startPos = deco->EndRun(startPos);
722 }
723 }
724 }
725 }
726 Insert(ll->edgeColumn);
727 Insert(lineRange.end);
728 saeNext = (!selAndEdge.empty()) ? selAndEdge[0] : -1;
729}
730
731BreakFinder::~BreakFinder() noexcept = default;
732
733TextSegment BreakFinder::Next() {
734 if (subBreak < 0) {
735 const int prev = nextBreak;
736 const Representation *repr = nullptr;
737 while (nextBreak < lineRange.end) {
738 int charWidth = 1;
739 const char * const chars = &ll->chars[nextBreak];
740 const unsigned char ch = chars[0];
741 if (!UTF8IsAscii(ch) && encodingFamily != EncodingFamily::eightBit) {
742 if (encodingFamily == EncodingFamily::unicode) {
743 charWidth = UTF8DrawBytes(reinterpret_cast<const unsigned char *>(chars), static_cast<int>(lineRange.end - nextBreak));
744 } else {
745 charWidth = pdoc->DBCSDrawBytes(std::string_view(chars, lineRange.end - nextBreak));
746 }
747 }
748 repr = nullptr;
749 if (preprs->MayContain(ch)) {
750 // Special case \r\n line ends if there is a representation
751 if (ch == '\r' && preprs->ContainsCrLf() && chars[1] == '\n') {
752 charWidth = 2;
753 }
754 repr = preprs->GetRepresentation(std::string_view(chars, charWidth));
755 }
756 if (((nextBreak > 0) && (ll->styles[nextBreak] != ll->styles[nextBreak - 1])) ||
757 repr ||
758 (nextBreak == saeNext)) {
759 while ((nextBreak >= saeNext) && (saeNext < lineRange.end)) {
760 saeCurrentPos++;
761 saeNext = static_cast<int>((saeCurrentPos < selAndEdge.size()) ? selAndEdge[saeCurrentPos] : lineRange.end);
762 }
763 if ((nextBreak > prev) || repr) {
764 // Have a segment to report
765 if (nextBreak == prev) {
766 nextBreak += charWidth;
767 } else {
768 repr = nullptr; // Optimize -> should remember repr
769 }
770 break;
771 }
772 }
773 nextBreak += charWidth;
774 }
775
776 const int lengthSegment = nextBreak - prev;
777 if (lengthSegment < lengthStartSubdivision) {
778 return TextSegment(prev, lengthSegment, repr);
779 }
780 subBreak = prev;
781 }
782
783 // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
784 const int startSegment = subBreak;
785 const int remaining = nextBreak - startSegment;
786 int lengthSegment = remaining;
787 if (lengthSegment > lengthEachSubdivision) {
788 lengthSegment = static_cast<int>(pdoc->SafeSegment(std::string_view(&ll->chars[startSegment], lengthEachSubdivision)));
789 }
790 if (lengthSegment < remaining) {
791 subBreak += lengthSegment;
792 } else {
793 subBreak = -1;
794 }
795 return TextSegment(startSegment, lengthSegment);
796}
797
798bool BreakFinder::More() const noexcept {
799 return (subBreak >= 0) || (nextBreak < lineRange.end);
800}
801
802PositionCacheEntry::PositionCacheEntry() noexcept :
803 styleNumber(0), len(0), clock(0) {
804}
805
806// Copy constructor not currently used, but needed for being element in std::vector.
807PositionCacheEntry::PositionCacheEntry(const PositionCacheEntry &other) :
808 styleNumber(other.styleNumber), len(other.len), clock(other.clock) {
809 if (other.positions) {
810 const size_t lenData = len + (len / sizeof(XYPOSITION)) + 1;
811 positions = std::make_unique<XYPOSITION[]>(lenData);
812 memcpy(positions.get(), other.positions.get(), lenData * sizeof(XYPOSITION));
813 }
814}
815
816void PositionCacheEntry::Set(unsigned int styleNumber_, std::string_view sv,
817 const XYPOSITION *positions_, uint16_t clock_) {
818 Clear();
819 styleNumber = static_cast<uint16_t>(styleNumber_);
820 len = static_cast<uint16_t>(sv.length());
821 clock = clock_;
822 if (sv.data() && positions_) {
823 positions = std::make_unique<XYPOSITION[]>(len + (len / sizeof(XYPOSITION)) + 1);
824 for (unsigned int i=0; i<len; i++) {
825 positions[i] = positions_[i];
826 }
827 memcpy(&positions[len], sv.data(), sv.length());
828 }
829}
830
831PositionCacheEntry::~PositionCacheEntry() {
832 Clear();
833}
834
835void PositionCacheEntry::Clear() noexcept {
836 positions.reset();
837 styleNumber = 0;
838 len = 0;
839 clock = 0;
840}
841
842bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, std::string_view sv, XYPOSITION *positions_) const noexcept {
843 if ((styleNumber == styleNumber_) && (len == sv.length()) &&
844 (memcmp(&positions[len], sv.data(), sv.length())== 0)) {
845 for (unsigned int i=0; i<len; i++) {
846 positions_[i] = positions[i];
847 }
848 return true;
849 } else {
850 return false;
851 }
852}
853
854size_t PositionCacheEntry::Hash(unsigned int styleNumber_, std::string_view sv) noexcept {
855 const size_t h1 = std::hash<std::string_view>{}(sv);
856 const size_t h2 = std::hash<unsigned int>{}(styleNumber_);
857 return h1 ^ (h2 << 1);
858}
859
860bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) const noexcept {
861 return clock > other.clock;
862}
863
864void PositionCacheEntry::ResetClock() noexcept {
865 if (clock > 0) {
866 clock = 1;
867 }
868}
869
870PositionCache::PositionCache() {
871 clock = 1;
872 pces.resize(0x400);
873 allClear = true;
874}
875
876void PositionCache::Clear() noexcept {
877 if (!allClear) {
878 for (PositionCacheEntry &pce : pces) {
879 pce.Clear();
880 }
881 }
882 clock = 1;
883 allClear = true;
884}
885
886void PositionCache::SetSize(size_t size_) {
887 Clear();
888 pces.resize(size_);
889}
890
891size_t PositionCache::GetSize() const noexcept {
892 return pces.size();
893}
894
895void PositionCache::MeasureWidths(Surface *surface, const ViewStyle &vstyle, unsigned int styleNumber,
896 std::string_view sv, XYPOSITION *positions) {
897 const Style &style = vstyle.styles[styleNumber];
898 if (style.monospaceASCII) {
899 if (AllGraphicASCII(sv)) {
900 const XYPOSITION monospaceCharacterWidth = style.monospaceCharacterWidth;
901 for (size_t i = 0; i < sv.length(); i++) {
902 positions[i] = monospaceCharacterWidth * (i+1);
903 }
904 return;
905 }
906 }
907
908 size_t probe = pces.size(); // Out of bounds
909 if ((!pces.empty()) && (sv.length() < 30)) {
910 // Only store short strings in the cache so it doesn't churn with
911 // long comments with only a single comment.
912
913 // Two way associative: try two probe positions.
914 const size_t hashValue = PositionCacheEntry::Hash(styleNumber, sv);
915 probe = hashValue % pces.size();
916 if (pces[probe].Retrieve(styleNumber, sv, positions)) {
917 return;
918 }
919 const size_t probe2 = (hashValue * 37) % pces.size();
920 if (pces[probe2].Retrieve(styleNumber, sv, positions)) {
921 return;
922 }
923 // Not found. Choose the oldest of the two slots to replace
924 if (pces[probe].NewerThan(pces[probe2])) {
925 probe = probe2;
926 }
927 }
928
929 const Font *fontStyle = style.font.get();
930 surface->MeasureWidths(fontStyle, sv, positions);
931 if (probe < pces.size()) {
932 // Store into cache
933 clock++;
934 if (clock > 60000) {
935 // Since there are only 16 bits for the clock, wrap it round and
936 // reset all cache entries so none get stuck with a high clock.
937 for (PositionCacheEntry &pce : pces) {
938 pce.ResetClock();
939 }
940 clock = 2;
941 }
942 allClear = false;
943 pces[probe].Set(styleNumber, sv, positions, clock);
944 }
945}
946