scintilla/src/PositionCache.cxx

   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 }