1 // Scintilla source code edit control 2 /** @file PositionCache.cxx 3 ** Classes for caching layout information. 4 **/ 5 // Copyright 1998-2007 by Neil Hodgson <[email protected]> 6 // The License.txt file describes the conditions under which this software may be distributed. 7 8 #include <cstddef> 9 #include <cstdlib> 10 #include <cstring> 11 #include <cmath> 12 13 #include <stdexcept> 14 #include <string> 15 #include <string_view> 16 #include <vector> 17 #include <map> 18 #include <algorithm> 19 #include <iterator> 20 #include <memory> 21 22 #include "Platform.h" 23 24 #include "ILoader.h" 25 #include "ILexer.h" 26 #include "Scintilla.h" 27 28 #include "CharacterCategory.h" 29 #include "Position.h" 30 #include "UniqueString.h" 31 #include "SplitVector.h" 32 #include "Partitioning.h" 33 #include "RunStyles.h" 34 #include "ContractionState.h" 35 #include "CellBuffer.h" 36 #include "KeyMap.h" 37 #include "Indicator.h" 38 #include "LineMarker.h" 39 #include "Style.h" 40 #include "ViewStyle.h" 41 #include "CharClassify.h" 42 #include "Decoration.h" 43 #include "CaseFolder.h" 44 #include "Document.h" 45 #include "UniConversion.h" 46 #include "Selection.h" 47 #include "PositionCache.h" 48 49 using namespace Scintilla; 50 51 void BidiData::Resize(size_t maxLineLength_) { 52 stylesFonts.resize(maxLineLength_ + 1); 53 widthReprs.resize(maxLineLength_ + 1); 54 } 55 56 LineLayout::LineLayout(int maxLineLength_) : 57 lenLineStarts(0), 58 lineNumber(-1), 59 inCache(false), 60 maxLineLength(-1), 61 numCharsInLine(0), 62 numCharsBeforeEOL(0), 63 validity(ValidLevel::invalid), 64 xHighlightGuide(0), 65 highlightColumn(false), 66 containsCaret(false), 67 edgeColumn(0), 68 bracePreviousStyles{}, 69 hotspot(0,0), 70 widthLine(wrapWidthInfinite), 71 lines(1), 72 wrapIndent(0) { 73 Resize(maxLineLength_); 74 } 75 76 LineLayout::~LineLayout() { 77 Free(); 78 } 79 80 void LineLayout::Resize(int maxLineLength_) { 81 if (maxLineLength_ > maxLineLength) { 82 Free(); 83 chars = std::make_unique<char[]>(maxLineLength_ + 1); 84 styles = std::make_unique<unsigned char []>(maxLineLength_ + 1); 85 // Extra position allocated as sometimes the Windows 86 // GetTextExtentExPoint API writes an extra element. 87 positions = std::make_unique<XYPOSITION []>(maxLineLength_ + 1 + 1); 88 if (bidiData) { 89 bidiData->Resize(maxLineLength_); 90 } 91 92 maxLineLength = maxLineLength_; 93 } 94 } 95 96 void LineLayout::EnsureBidiData() { 97 if (!bidiData) { 98 bidiData = std::make_unique<BidiData>(); 99 bidiData->Resize(maxLineLength); 100 } 101 } 102 103 void LineLayout::Free() noexcept { 104 chars.reset(); 105 styles.reset(); 106 positions.reset(); 107 lineStarts.reset(); 108 bidiData.reset(); 109 } 110 111 void LineLayout::Invalidate(ValidLevel validity_) noexcept { 112 if (validity > validity_) 113 validity = validity_; 114 } 115 116 int LineLayout::LineStart(int line) const noexcept { 117 if (line <= 0) { 118 return 0; 119 } else if ((line >= lines) || !lineStarts) { 120 return numCharsInLine; 121 } else { 122 return lineStarts[line]; 123 } 124 } 125 126 int Scintilla::LineLayout::LineLength(int line) const noexcept { 127 if (!lineStarts) { 128 return numCharsInLine; 129 } if (line >= lines - 1) { 130 return numCharsInLine - lineStarts[line]; 131 } else { 132 return lineStarts[line + 1] - lineStarts[line]; 133 } 134 } 135 136 int LineLayout::LineLastVisible(int line, Scope scope) const noexcept { 137 if (line < 0) { 138 return 0; 139 } else if ((line >= lines-1) || !lineStarts) { 140 return scope == Scope::visibleOnly ? numCharsBeforeEOL : numCharsInLine; 141 } else { 142 return lineStarts[line+1]; 143 } 144 } 145 146 Range LineLayout::SubLineRange(int subLine, Scope scope) const noexcept { 147 return Range(LineStart(subLine), LineLastVisible(subLine, scope)); 148 } 149 150 bool LineLayout::InLine(int offset, int line) const noexcept { 151 return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) || 152 ((offset == numCharsInLine) && (line == (lines-1))); 153 } 154 155 int LineLayout::SubLineFromPosition(int posInLine, PointEnd pe) const noexcept { 156 if (!lineStarts || (posInLine > maxLineLength)) { 157 return lines - 1; 158 } 159 160 for (int line = 0; line < lines; line++) { 161 if (pe & peSubLineEnd) { 162 // Return subline not start of next 163 if (lineStarts[line + 1] <= posInLine + 1) 164 return line; 165 } else { 166 if (lineStarts[line + 1] <= posInLine) 167 return line; 168 } 169 } 170 171 return lines - 1; 172 } 173 174 void LineLayout::SetLineStart(int line, int start) { 175 if ((line >= lenLineStarts) && (line != 0)) { 176 const int newMaxLines = line + 20; 177 std::unique_ptr<int[]> newLineStarts = std::make_unique<int[]>(newMaxLines); 178 for (int i = 0; i < newMaxLines; i++) { 179 if (i < lenLineStarts) 180 newLineStarts[i] = lineStarts[i]; 181 else 182 newLineStarts[i] = 0; 183 } 184 lineStarts = std::move(newLineStarts); 185 lenLineStarts = newMaxLines; 186 } 187 lineStarts[line] = start; 188 } 189 190 void LineLayout::SetBracesHighlight(Range rangeLine, const Sci::Position braces[], 191 char bracesMatchStyle, int xHighlight, bool ignoreStyle) { 192 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) { 193 const Sci::Position braceOffset = braces[0] - rangeLine.start; 194 if (braceOffset < numCharsInLine) { 195 bracePreviousStyles[0] = styles[braceOffset]; 196 styles[braceOffset] = bracesMatchStyle; 197 } 198 } 199 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) { 200 const Sci::Position braceOffset = braces[1] - rangeLine.start; 201 if (braceOffset < numCharsInLine) { 202 bracePreviousStyles[1] = styles[braceOffset]; 203 styles[braceOffset] = bracesMatchStyle; 204 } 205 } 206 if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) || 207 (braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) { 208 xHighlightGuide = xHighlight; 209 } 210 } 211 212 void LineLayout::RestoreBracesHighlight(Range rangeLine, const Sci::Position braces[], bool ignoreStyle) { 213 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) { 214 const Sci::Position braceOffset = braces[0] - rangeLine.start; 215 if (braceOffset < numCharsInLine) { 216 styles[braceOffset] = bracePreviousStyles[0]; 217 } 218 } 219 if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) { 220 const Sci::Position braceOffset = braces[1] - rangeLine.start; 221 if (braceOffset < numCharsInLine) { 222 styles[braceOffset] = bracePreviousStyles[1]; 223 } 224 } 225 xHighlightGuide = 0; 226 } 227 228 int LineLayout::FindBefore(XYPOSITION x, Range range) const noexcept { 229 Sci::Position lower = range.start; 230 Sci::Position upper = range.end; 231 do { 232 const Sci::Position middle = (upper + lower + 1) / 2; // Round high 233 const XYPOSITION posMiddle = positions[middle]; 234 if (x < posMiddle) { 235 upper = middle - 1; 236 } else { 237 lower = middle; 238 } 239 } while (lower < upper); 240 return static_cast<int>(lower); 241 } 242 243 244 int LineLayout::FindPositionFromX(XYPOSITION x, Range range, bool charPosition) const noexcept { 245 int pos = FindBefore(x, range); 246 while (pos < range.end) { 247 if (charPosition) { 248 if (x < (positions[pos + 1])) { 249 return pos; 250 } 251 } else { 252 if (x < ((positions[pos] + positions[pos + 1]) / 2)) { 253 return pos; 254 } 255 } 256 pos++; 257 } 258 return static_cast<int>(range.end); 259 } 260 261 Point LineLayout::PointFromPosition(int posInLine, int lineHeight, PointEnd pe) const noexcept { 262 Point pt; 263 // In case of very long line put x at arbitrary large position 264 if (posInLine > maxLineLength) { 265 pt.x = positions[maxLineLength] - positions[LineStart(lines)]; 266 } 267 268 for (int subLine = 0; subLine < lines; subLine++) { 269 const Range rangeSubLine = SubLineRange(subLine, Scope::visibleOnly); 270 if (posInLine >= rangeSubLine.start) { 271 pt.y = static_cast<XYPOSITION>(subLine*lineHeight); 272 if (posInLine <= rangeSubLine.end) { 273 pt.x = positions[posInLine] - positions[rangeSubLine.start]; 274 if (rangeSubLine.start != 0) // Wrapped lines may be indented 275 pt.x += wrapIndent; 276 if (pe & peSubLineEnd) // Return end of first subline not start of next 277 break; 278 } else if ((pe & peLineEnd) && (subLine == (lines-1))) { 279 pt.x = positions[numCharsInLine] - positions[rangeSubLine.start]; 280 if (rangeSubLine.start != 0) // Wrapped lines may be indented 281 pt.x += wrapIndent; 282 } 283 } else { 284 break; 285 } 286 } 287 return pt; 288 } 289 290 int LineLayout::EndLineStyle() const noexcept { 291 return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0]; 292 } 293 294 ScreenLine::ScreenLine( 295 const LineLayout *ll_, 296 int subLine, 297 const ViewStyle &vs, 298 XYPOSITION width_, 299 int tabWidthMinimumPixels_) : 300 ll(ll_), 301 start(ll->LineStart(subLine)), 302 len(ll->LineLength(subLine)), 303 width(width_), 304 height(static_cast<float>(vs.lineHeight)), 305 ctrlCharPadding(vs.ctrlCharPadding), 306 tabWidth(vs.tabWidth), 307 tabWidthMinimumPixels(tabWidthMinimumPixels_) { 308 } 309 310 ScreenLine::~ScreenLine() { 311 } 312 313 std::string_view ScreenLine::Text() const { 314 return std::string_view(&ll->chars[start], len); 315 } 316 317 size_t ScreenLine::Length() const { 318 return len; 319 } 320 321 size_t ScreenLine::RepresentationCount() const { 322 return std::count_if(&ll->bidiData->widthReprs[start], 323 &ll->bidiData->widthReprs[start + len], 324 [](XYPOSITION w) noexcept { return w > 0.0f; }); 325 } 326 327 XYPOSITION ScreenLine::Width() const { 328 return width; 329 } 330 331 XYPOSITION ScreenLine::Height() const { 332 return height; 333 } 334 335 XYPOSITION ScreenLine::TabWidth() const { 336 return tabWidth; 337 } 338 339 XYPOSITION ScreenLine::TabWidthMinimumPixels() const { 340 return static_cast<XYPOSITION>(tabWidthMinimumPixels); 341 } 342 343 const Font *ScreenLine::FontOfPosition(size_t position) const { 344 return &ll->bidiData->stylesFonts[start + position]; 345 } 346 347 XYPOSITION ScreenLine::RepresentationWidth(size_t position) const { 348 return ll->bidiData->widthReprs[start + position]; 349 } 350 351 XYPOSITION ScreenLine::TabPositionAfter(XYPOSITION xPosition) const { 352 return (std::floor((xPosition + TabWidthMinimumPixels()) / TabWidth()) + 1) * TabWidth(); 353 } 354 355 LineLayoutCache::LineLayoutCache() : 356 level(0), 357 allInvalidated(false), styleClock(-1), useCount(0) { 358 Allocate(0); 359 } 360 361 LineLayoutCache::~LineLayoutCache() { 362 Deallocate(); 363 } 364 365 void LineLayoutCache::Allocate(size_t length_) { 366 PLATFORM_ASSERT(cache.empty()); 367 allInvalidated = false; 368 cache.resize(length_); 369 } 370 371 void LineLayoutCache::AllocateForLevel(Sci::Line linesOnScreen, Sci::Line linesInDoc) { 372 PLATFORM_ASSERT(useCount == 0); 373 size_t lengthForLevel = 0; 374 if (level == llcCaret) { 375 lengthForLevel = 1; 376 } else if (level == llcPage) { 377 lengthForLevel = linesOnScreen + 1; 378 } else if (level == llcDocument) { 379 lengthForLevel = linesInDoc; 380 } 381 if (lengthForLevel > cache.size()) { 382 Deallocate(); 383 Allocate(lengthForLevel); 384 } else { 385 if (lengthForLevel < cache.size()) { 386 for (size_t i = lengthForLevel; i < cache.size(); i++) { 387 cache[i].reset(); 388 } 389 } 390 cache.resize(lengthForLevel); 391 } 392 PLATFORM_ASSERT(cache.size() == lengthForLevel); 393 } 394 395 void LineLayoutCache::Deallocate() noexcept { 396 PLATFORM_ASSERT(useCount == 0); 397 cache.clear(); 398 } 399 400 void LineLayoutCache::Invalidate(LineLayout::ValidLevel validity_) noexcept { 401 if (!cache.empty() && !allInvalidated) { 402 for (const std::unique_ptr<LineLayout> &ll : cache) { 403 if (ll) { 404 ll->Invalidate(validity_); 405 } 406 } 407 if (validity_ == LineLayout::ValidLevel::invalid) { 408 allInvalidated = true; 409 } 410 } 411 } 412 413 void LineLayoutCache::SetLevel(int level_) noexcept { 414 allInvalidated = false; 415 if ((level_ != -1) && (level != level_)) { 416 level = level_; 417 Deallocate(); 418 } 419 } 420 421 LineLayout *LineLayoutCache::Retrieve(Sci::Line lineNumber, Sci::Line lineCaret, int maxChars, int styleClock_, 422 Sci::Line linesOnScreen, Sci::Line linesInDoc) { 423 AllocateForLevel(linesOnScreen, linesInDoc); 424 if (styleClock != styleClock_) { 425 Invalidate(LineLayout::ValidLevel::checkTextAndStyle); 426 styleClock = styleClock_; 427 } 428 allInvalidated = false; 429 Sci::Position pos = -1; 430 LineLayout *ret = nullptr; 431 if (level == llcCaret) { 432 pos = 0; 433 } else if (level == llcPage) { 434 if (lineNumber == lineCaret) { 435 pos = 0; 436 } else if (cache.size() > 1) { 437 pos = 1 + (lineNumber % (cache.size() - 1)); 438 } 439 } else if (level == llcDocument) { 440 pos = lineNumber; 441 } 442 if (pos >= 0) { 443 PLATFORM_ASSERT(useCount == 0); 444 if (!cache.empty() && (pos < static_cast<int>(cache.size()))) { 445 if (cache[pos]) { 446 if ((cache[pos]->lineNumber != lineNumber) || 447 (cache[pos]->maxLineLength < maxChars)) { 448 cache[pos].reset(); 449 } 450 } 451 if (!cache[pos]) { 452 cache[pos] = std::make_unique<LineLayout>(maxChars); 453 } 454 cache[pos]->lineNumber = lineNumber; 455 cache[pos]->inCache = true; 456 ret = cache[pos].get(); 457 useCount++; 458 } 459 } 460 461 if (!ret) { 462 ret = new LineLayout(maxChars); 463 ret->lineNumber = lineNumber; 464 } 465 466 return ret; 467 } 468 469 void LineLayoutCache::Dispose(LineLayout *ll) noexcept { 470 allInvalidated = false; 471 if (ll) { 472 if (!ll->inCache) { 473 delete ll; 474 } else { 475 useCount--; 476 } 477 } 478 } 479 480 // Simply pack the (maximum 4) character bytes into an int 481 static unsigned int KeyFromString(const char *charBytes, size_t len) noexcept { 482 PLATFORM_ASSERT(len <= 4); 483 unsigned int k=0; 484 for (size_t i=0; i<len && charBytes[i]; i++) { 485 k = k * 0x100; 486 const unsigned char uc = charBytes[i]; 487 k += uc; 488 } 489 return k; 490 } 491 492 SpecialRepresentations::SpecialRepresentations() { 493 const short none = 0; 494 std::fill(startByteHasReprs, std::end(startByteHasReprs), none); 495 } 496 497 void SpecialRepresentations::SetRepresentation(const char *charBytes, const char *value) { 498 const unsigned int key = KeyFromString(charBytes, UTF8MaxBytes); 499 MapRepresentation::iterator it = mapReprs.find(key); 500 if (it == mapReprs.end()) { 501 // New entry so increment for first byte 502 const unsigned char ucStart = charBytes[0]; 503 startByteHasReprs[ucStart]++; 504 } 505 mapReprs[key] = Representation(value); 506 } 507 508 void SpecialRepresentations::ClearRepresentation(const char *charBytes) { 509 MapRepresentation::iterator it = mapReprs.find(KeyFromString(charBytes, UTF8MaxBytes)); 510 if (it != mapReprs.end()) { 511 mapReprs.erase(it); 512 const unsigned char ucStart = charBytes[0]; 513 startByteHasReprs[ucStart]--; 514 } 515 } 516 517 const Representation *SpecialRepresentations::RepresentationFromCharacter(const char *charBytes, size_t len) const { 518 PLATFORM_ASSERT(len <= 4); 519 const unsigned char ucStart = charBytes[0]; 520 if (!startByteHasReprs[ucStart]) 521 return nullptr; 522 MapRepresentation::const_iterator it = mapReprs.find(KeyFromString(charBytes, len)); 523 if (it != mapReprs.end()) { 524 return &(it->second); 525 } 526 return nullptr; 527 } 528 529 bool SpecialRepresentations::Contains(const char *charBytes, size_t len) const { 530 PLATFORM_ASSERT(len <= 4); 531 const unsigned char ucStart = charBytes[0]; 532 if (!startByteHasReprs[ucStart]) 533 return false; 534 MapRepresentation::const_iterator it = mapReprs.find(KeyFromString(charBytes, len)); 535 return it != mapReprs.end(); 536 } 537 538 void SpecialRepresentations::Clear() { 539 mapReprs.clear(); 540 const short none = 0; 541 std::fill(startByteHasReprs, std::end(startByteHasReprs), none); 542 } 543 544 void BreakFinder::Insert(Sci::Position val) { 545 const int posInLine = static_cast<int>(val); 546 if (posInLine > nextBreak) { 547 const std::vector<int>::iterator it = std::lower_bound(selAndEdge.begin(), selAndEdge.end(), posInLine); 548 if (it == selAndEdge.end()) { 549 selAndEdge.push_back(posInLine); 550 } else if (*it != posInLine) { 551 selAndEdge.insert(it, 1, posInLine); 552 } 553 } 554 } 555 556 BreakFinder::BreakFinder(const LineLayout *ll_, const Selection *psel, Range lineRange_, Sci::Position posLineStart_, 557 int xStart, bool breakForSelection, const Document *pdoc_, const SpecialRepresentations *preprs_, const ViewStyle *pvsDraw) : 558 ll(ll_), 559 lineRange(lineRange_), 560 posLineStart(posLineStart_), 561 nextBreak(static_cast<int>(lineRange_.start)), 562 saeCurrentPos(0), 563 saeNext(0), 564 subBreak(-1), 565 pdoc(pdoc_), 566 encodingFamily(pdoc_->CodePageFamily()), 567 preprs(preprs_) { 568 569 // Search for first visible break 570 // First find the first visible character 571 if (xStart > 0.0f) 572 nextBreak = ll->FindBefore(static_cast<XYPOSITION>(xStart), lineRange); 573 // Now back to a style break 574 while ((nextBreak > lineRange.start) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) { 575 nextBreak--; 576 } 577 578 if (breakForSelection) { 579 const SelectionPosition posStart(posLineStart); 580 const SelectionPosition posEnd(posLineStart + lineRange.end); 581 const SelectionSegment segmentLine(posStart, posEnd); 582 for (size_t r=0; r<psel->Count(); r++) { 583 const SelectionSegment portion = psel->Range(r).Intersect(segmentLine); 584 if (!(portion.start == portion.end)) { 585 if (portion.start.IsValid()) 586 Insert(portion.start.Position() - posLineStart); 587 if (portion.end.IsValid()) 588 Insert(portion.end.Position() - posLineStart); 589 } 590 } 591 } 592 if (pvsDraw && pvsDraw->indicatorsSetFore) { 593 for (const IDecoration *deco : pdoc->decorations->View()) { 594 if (pvsDraw->indicators[deco->Indicator()].OverridesTextFore()) { 595 Sci::Position startPos = deco->EndRun(posLineStart); 596 while (startPos < (posLineStart + lineRange.end)) { 597 Insert(startPos - posLineStart); 598 startPos = deco->EndRun(startPos); 599 } 600 } 601 } 602 } 603 Insert(ll->edgeColumn); 604 Insert(lineRange.end); 605 saeNext = (!selAndEdge.empty()) ? selAndEdge[0] : -1; 606 } 607 608 BreakFinder::~BreakFinder() { 609 } 610 611 TextSegment BreakFinder::Next() { 612 if (subBreak == -1) { 613 const int prev = nextBreak; 614 while (nextBreak < lineRange.end) { 615 int charWidth = 1; 616 if (encodingFamily == EncodingFamily::unicode) 617 charWidth = UTF8DrawBytes(reinterpret_cast<unsigned char *>(&ll->chars[nextBreak]), 618 static_cast<int>(lineRange.end - nextBreak)); 619 else if (encodingFamily == EncodingFamily::dbcs) 620 charWidth = pdoc->DBCSDrawBytes( 621 std::string_view(&ll->chars[nextBreak], lineRange.end - nextBreak)); 622 const Representation *repr = preprs->RepresentationFromCharacter(&ll->chars[nextBreak], charWidth); 623 if (((nextBreak > 0) && (ll->styles[nextBreak] != ll->styles[nextBreak - 1])) || 624 repr || 625 (nextBreak == saeNext)) { 626 while ((nextBreak >= saeNext) && (saeNext < lineRange.end)) { 627 saeCurrentPos++; 628 saeNext = static_cast<int>((saeCurrentPos < selAndEdge.size()) ? selAndEdge[saeCurrentPos] : lineRange.end); 629 } 630 if ((nextBreak > prev) || repr) { 631 // Have a segment to report 632 if (nextBreak == prev) { 633 nextBreak += charWidth; 634 } else { 635 repr = nullptr; // Optimize -> should remember repr 636 } 637 if ((nextBreak - prev) < lengthStartSubdivision) { 638 return TextSegment(prev, nextBreak - prev, repr); 639 } else { 640 break; 641 } 642 } 643 } 644 nextBreak += charWidth; 645 } 646 if ((nextBreak - prev) < lengthStartSubdivision) { 647 return TextSegment(prev, nextBreak - prev); 648 } 649 subBreak = prev; 650 } 651 // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision. 652 // For very long runs add extra breaks after spaces or if no spaces before low punctuation. 653 const int startSegment = subBreak; 654 if ((nextBreak - subBreak) <= lengthEachSubdivision) { 655 subBreak = -1; 656 return TextSegment(startSegment, nextBreak - startSegment); 657 } else { 658 subBreak += pdoc->SafeSegment(&ll->chars[subBreak], nextBreak-subBreak, lengthEachSubdivision); 659 if (subBreak >= nextBreak) { 660 subBreak = -1; 661 return TextSegment(startSegment, nextBreak - startSegment); 662 } else { 663 return TextSegment(startSegment, subBreak - startSegment); 664 } 665 } 666 } 667 668 bool BreakFinder::More() const noexcept { 669 return (subBreak >= 0) || (nextBreak < lineRange.end); 670 } 671 672 PositionCacheEntry::PositionCacheEntry() noexcept : 673 styleNumber(0), len(0), clock(0), positions(nullptr) { 674 } 675 676 // Copy constructor not currently used, but needed for being element in std::vector. 677 PositionCacheEntry::PositionCacheEntry(const PositionCacheEntry &other) : 678 styleNumber(other.styleNumber), len(other.styleNumber), clock(other.styleNumber), positions(nullptr) { 679 if (other.positions) { 680 const size_t lenData = len + (len / sizeof(XYPOSITION)) + 1; 681 positions = std::make_unique<XYPOSITION[]>(lenData); 682 memcpy(positions.get(), other.positions.get(), lenData * sizeof(XYPOSITION)); 683 } 684 } 685 686 void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_, 687 unsigned int len_, const XYPOSITION *positions_, unsigned int clock_) { 688 Clear(); 689 styleNumber = styleNumber_; 690 len = len_; 691 clock = clock_; 692 if (s_ && positions_) { 693 positions = std::make_unique<XYPOSITION[]>(len + (len / sizeof(XYPOSITION)) + 1); 694 for (unsigned int i=0; i<len; i++) { 695 positions[i] = positions_[i]; 696 } 697 memcpy(&positions[len], s_, len); 698 } 699 } 700 701 PositionCacheEntry::~PositionCacheEntry() { 702 Clear(); 703 } 704 705 void PositionCacheEntry::Clear() noexcept { 706 positions.reset(); 707 styleNumber = 0; 708 len = 0; 709 clock = 0; 710 } 711 712 bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_, 713 unsigned int len_, XYPOSITION *positions_) const noexcept { 714 if ((styleNumber == styleNumber_) && (len == len_) && 715 (memcmp(&positions[len], s_, len)== 0)) { 716 for (unsigned int i=0; i<len; i++) { 717 positions_[i] = positions[i]; 718 } 719 return true; 720 } else { 721 return false; 722 } 723 } 724 725 unsigned int PositionCacheEntry::Hash(unsigned int styleNumber_, const char *s, unsigned int len_) noexcept { 726 unsigned int ret = s[0] << 7; 727 for (unsigned int i=0; i<len_; i++) { 728 ret *= 1000003; 729 ret ^= s[i]; 730 } 731 ret *= 1000003; 732 ret ^= len_; 733 ret *= 1000003; 734 ret ^= styleNumber_; 735 return ret; 736 } 737 738 bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) const noexcept { 739 return clock > other.clock; 740 } 741 742 void PositionCacheEntry::ResetClock() noexcept { 743 if (clock > 0) { 744 clock = 1; 745 } 746 } 747 748 PositionCache::PositionCache() { 749 clock = 1; 750 pces.resize(0x400); 751 allClear = true; 752 } 753 754 PositionCache::~PositionCache() { 755 Clear(); 756 } 757 758 void PositionCache::Clear() noexcept { 759 if (!allClear) { 760 for (PositionCacheEntry &pce : pces) { 761 pce.Clear(); 762 } 763 } 764 clock = 1; 765 allClear = true; 766 } 767 768 void PositionCache::SetSize(size_t size_) { 769 Clear(); 770 pces.resize(size_); 771 } 772 773 void PositionCache::MeasureWidths(Surface *surface, const ViewStyle &vstyle, unsigned int styleNumber, 774 const char *s, unsigned int len, XYPOSITION *positions, const Document *pdoc) { 775 776 allClear = false; 777 size_t probe = pces.size(); // Out of bounds 778 if ((!pces.empty()) && (len < 30)) { 779 // Only store short strings in the cache so it doesn't churn with 780 // long comments with only a single comment. 781 782 // Two way associative: try two probe positions. 783 const unsigned int hashValue = PositionCacheEntry::Hash(styleNumber, s, len); 784 probe = hashValue % pces.size(); 785 if (pces[probe].Retrieve(styleNumber, s, len, positions)) { 786 return; 787 } 788 const unsigned int probe2 = (hashValue * 37) % pces.size(); 789 if (pces[probe2].Retrieve(styleNumber, s, len, positions)) { 790 return; 791 } 792 // Not found. Choose the oldest of the two slots to replace 793 if (pces[probe].NewerThan(pces[probe2])) { 794 probe = probe2; 795 } 796 } 797 FontAlias fontStyle = vstyle.styles[styleNumber].font; 798 if (len > BreakFinder::lengthStartSubdivision) { 799 // Break up into segments 800 unsigned int startSegment = 0; 801 XYPOSITION xStartSegment = 0; 802 while (startSegment < len) { 803 const unsigned int lenSegment = pdoc->SafeSegment(s + startSegment, len - startSegment, BreakFinder::lengthEachSubdivision); 804 surface->MeasureWidths(fontStyle, std::string_view(s + startSegment, lenSegment), positions + startSegment); 805 for (unsigned int inSeg = 0; inSeg < lenSegment; inSeg++) { 806 positions[startSegment + inSeg] += xStartSegment; 807 } 808 xStartSegment = positions[startSegment + lenSegment - 1]; 809 startSegment += lenSegment; 810 } 811 } else { 812 surface->MeasureWidths(fontStyle, std::string_view(s, len), positions); 813 } 814 if (probe < pces.size()) { 815 // Store into cache 816 clock++; 817 if (clock > 60000) { 818 // Since there are only 16 bits for the clock, wrap it round and 819 // reset all cache entries so none get stuck with a high clock. 820 for (PositionCacheEntry &pce : pces) { 821 pce.ResetClock(); 822 } 823 clock = 2; 824 } 825 pces[probe].Set(styleNumber, s, len, positions, clock); 826 } 827 } 828