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 | |
56 | using namespace Scintilla; |
57 | using namespace Scintilla::Internal; |
58 | |
59 | void BidiData::Resize(size_t maxLineLength_) { |
60 | stylesFonts.resize(maxLineLength_ + 1); |
61 | widthReprs.resize(maxLineLength_ + 1); |
62 | } |
63 | |
64 | LineLayout::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 | |
82 | LineLayout::~LineLayout() { |
83 | Free(); |
84 | } |
85 | |
86 | void 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 | |
102 | void LineLayout::EnsureBidiData() { |
103 | if (!bidiData) { |
104 | bidiData = std::make_unique<BidiData>(); |
105 | bidiData->Resize(maxLineLength); |
106 | } |
107 | } |
108 | |
109 | void LineLayout::Free() noexcept { |
110 | chars.reset(); |
111 | styles.reset(); |
112 | positions.reset(); |
113 | lineStarts.reset(); |
114 | bidiData.reset(); |
115 | } |
116 | |
117 | void LineLayout::Invalidate(ValidLevel validity_) noexcept { |
118 | if (validity > validity_) |
119 | validity = validity_; |
120 | } |
121 | |
122 | Sci::Line LineLayout::LineNumber() const noexcept { |
123 | return lineNumber; |
124 | } |
125 | |
126 | bool LineLayout::CanHold(Sci::Line lineDoc, int lineLength_) const noexcept { |
127 | return (lineNumber == lineDoc) && (lineLength_ <= maxLineLength); |
128 | } |
129 | |
130 | int 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 | |
140 | int 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 | |
150 | int 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 | |
160 | Range LineLayout::SubLineRange(int subLine, Scope scope) const noexcept { |
161 | return Range(LineStart(subLine), LineLastVisible(subLine, scope)); |
162 | } |
163 | |
164 | bool 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 | |
169 | int 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 | |
188 | void 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 | |
201 | void 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 | |
223 | void 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 | |
239 | int 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 | |
255 | int 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 | |
272 | Point 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 | |
301 | int LineLayout::EndLineStyle() const noexcept { |
302 | return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0]; |
303 | } |
304 | |
305 | ScreenLine::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 | |
321 | ScreenLine::~ScreenLine() { |
322 | } |
323 | |
324 | std::string_view ScreenLine::Text() const { |
325 | return std::string_view(&ll->chars[start], len); |
326 | } |
327 | |
328 | size_t ScreenLine::Length() const { |
329 | return len; |
330 | } |
331 | |
332 | size_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 | |
338 | XYPOSITION ScreenLine::Width() const { |
339 | return width; |
340 | } |
341 | |
342 | XYPOSITION ScreenLine::Height() const { |
343 | return height; |
344 | } |
345 | |
346 | XYPOSITION ScreenLine::TabWidth() const { |
347 | return tabWidth; |
348 | } |
349 | |
350 | XYPOSITION ScreenLine::TabWidthMinimumPixels() const { |
351 | return static_cast<XYPOSITION>(tabWidthMinimumPixels); |
352 | } |
353 | |
354 | const Font *ScreenLine::FontOfPosition(size_t position) const { |
355 | return ll->bidiData->stylesFonts[start + position].get(); |
356 | } |
357 | |
358 | XYPOSITION ScreenLine::RepresentationWidth(size_t position) const { |
359 | return ll->bidiData->widthReprs[start + position]; |
360 | } |
361 | |
362 | XYPOSITION ScreenLine::TabPositionAfter(XYPOSITION xPosition) const { |
363 | return (std::floor((xPosition + TabWidthMinimumPixels()) / TabWidth()) + 1) * TabWidth(); |
364 | } |
365 | |
366 | LineLayoutCache::LineLayoutCache() : |
367 | level(LineCache::None), |
368 | allInvalidated(false), styleClock(-1) { |
369 | } |
370 | |
371 | LineLayoutCache::~LineLayoutCache() = default; |
372 | |
373 | namespace { |
374 | |
375 | constexpr size_t AlignUp(size_t value, size_t alignment) noexcept { |
376 | return ((value - 1) / alignment + 1) * alignment; |
377 | } |
378 | |
379 | constexpr size_t alignmentLLC = 20; |
380 | |
381 | constexpr bool GraphicASCII(char ch) noexcept { |
382 | return ch >= ' ' && ch <= '~'; |
383 | } |
384 | |
385 | bool AllGraphicASCII(std::string_view text) noexcept { |
386 | return std::all_of(text.cbegin(), text.cend(), GraphicASCII); |
387 | } |
388 | |
389 | } |
390 | |
391 | |
392 | size_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 | |
406 | void 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 | |
459 | void LineLayoutCache::Deallocate() noexcept { |
460 | cache.clear(); |
461 | } |
462 | |
463 | void 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 | |
476 | void LineLayoutCache::SetLevel(LineCache level_) noexcept { |
477 | if (level != level_) { |
478 | level = level_; |
479 | allInvalidated = false; |
480 | cache.clear(); |
481 | } |
482 | } |
483 | |
484 | std::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 | |
545 | namespace { |
546 | |
547 | // Simply pack the (maximum 4) character bytes into an int |
548 | constexpr 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 | |
557 | constexpr unsigned int representationKeyCrLf = KeyFromString("\r\n" ); |
558 | |
559 | } |
560 | |
561 | void 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 | |
579 | void 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 | |
591 | void 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 | |
604 | void 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 | |
622 | const 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 | |
634 | const 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 | |
644 | void 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 | |
652 | void 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 | |
664 | BreakFinder::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 | |
731 | BreakFinder::~BreakFinder() noexcept = default; |
732 | |
733 | TextSegment 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 | |
798 | bool BreakFinder::More() const noexcept { |
799 | return (subBreak >= 0) || (nextBreak < lineRange.end); |
800 | } |
801 | |
802 | PositionCacheEntry::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. |
807 | PositionCacheEntry::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 | |
816 | void 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 | |
831 | PositionCacheEntry::~PositionCacheEntry() { |
832 | Clear(); |
833 | } |
834 | |
835 | void PositionCacheEntry::Clear() noexcept { |
836 | positions.reset(); |
837 | styleNumber = 0; |
838 | len = 0; |
839 | clock = 0; |
840 | } |
841 | |
842 | bool 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 | |
854 | size_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 | |
860 | bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) const noexcept { |
861 | return clock > other.clock; |
862 | } |
863 | |
864 | void PositionCacheEntry::ResetClock() noexcept { |
865 | if (clock > 0) { |
866 | clock = 1; |
867 | } |
868 | } |
869 | |
870 | PositionCache::PositionCache() { |
871 | clock = 1; |
872 | pces.resize(0x400); |
873 | allClear = true; |
874 | } |
875 | |
876 | void PositionCache::Clear() noexcept { |
877 | if (!allClear) { |
878 | for (PositionCacheEntry &pce : pces) { |
879 | pce.Clear(); |
880 | } |
881 | } |
882 | clock = 1; |
883 | allClear = true; |
884 | } |
885 | |
886 | void PositionCache::SetSize(size_t size_) { |
887 | Clear(); |
888 | pces.resize(size_); |
889 | } |
890 | |
891 | size_t PositionCache::GetSize() const noexcept { |
892 | return pces.size(); |
893 | } |
894 | |
895 | void 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 | |