src/stc/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 <stdlib.h>
   9 #include <string.h>
  10 #include <stdio.h>
  11 #include <ctype.h>
  12
  13 #include "Platform.h"
  14
  15 #include "Scintilla.h"
  16
  17 #include "SplitVector.h"
  18 #include "Partitioning.h"
  19 #include "RunStyles.h"
  20 #include "ContractionState.h"
  21 #include "CellBuffer.h"
  22 #include "KeyMap.h"
  23 #include "Indicator.h"
  24 #include "XPM.h"
  25 #include "LineMarker.h"
  26 #include "Style.h"
  27 #include "ViewStyle.h"
  28 #include "CharClassify.h"
  29 #include "Decoration.h"
  30 #include "Document.h"
  31 #include "Selection.h"
  32 #include "PositionCache.h"
  33
  34 #ifdef SCI_NAMESPACE
  35 using namespace Scintilla;
  36 #endif
  37
  38 static inline bool IsControlCharacter(int ch) {
  39         // iscntrl returns true for lots of chars > 127 which are displayable
  40         return ch >= 0 && ch < ' ';
  41 }
  42
  43 LineLayout::LineLayout(int maxLineLength_) :
  44         lineStarts(0),
  45         lenLineStarts(0),
  46         lineNumber(-1),
  47         inCache(false),
  48         maxLineLength(-1),
  49         numCharsInLine(0),
  50         numCharsBeforeEOL(0),
  51         validity(llInvalid),
  52         xHighlightGuide(0),
  53         highlightColumn(0),
  54         psel(NULL),
  55         containsCaret(false),
  56         edgeColumn(0),
  57         chars(0),
  58         styles(0),
  59         styleBitsSet(0),
  60         indicators(0),
  61         positions(0),
  62         hsStart(0),
  63         hsEnd(0),
  64         widthLine(wrapWidthInfinite),
  65         lines(1),
  66         wrapIndent(0) {
  67         Resize(maxLineLength_);
  68 }
  69
  70 LineLayout::~LineLayout() {
  71         Free();
  72 }
  73
  74 void LineLayout::Resize(int maxLineLength_) {
  75         if (maxLineLength_ > maxLineLength) {
  76                 Free();
  77                 chars = new char[maxLineLength_ + 1];
  78                 styles = new unsigned char[maxLineLength_ + 1];
  79                 indicators = new char[maxLineLength_ + 1];
  80                 // Extra position allocated as sometimes the Windows
  81                 // GetTextExtentExPoint API writes an extra element.
  82                 positions = new int[maxLineLength_ + 1 + 1];
  83                 maxLineLength = maxLineLength_;
  84         }
  85 }
  86
  87 void LineLayout::Free() {
  88         delete []chars;
  89         chars = 0;
  90         delete []styles;
  91         styles = 0;
  92         delete []indicators;
  93         indicators = 0;
  94         delete []positions;
  95         positions = 0;
  96         delete []lineStarts;
  97         lineStarts = 0;
  98 }
  99
 100 void LineLayout::Invalidate(validLevel validity_) {
 101         if (validity > validity_)
 102                 validity = validity_;
 103 }
 104
 105 int LineLayout::LineStart(int line) const {
 106         if (line <= 0) {
 107                 return 0;
 108         } else if ((line >= lines) || !lineStarts) {
 109                 return numCharsInLine;
 110         } else {
 111                 return lineStarts[line];
 112         }
 113 }
 114
 115 int LineLayout::LineLastVisible(int line) const {
 116         if (line < 0) {
 117                 return 0;
 118         } else if ((line >= lines-1) || !lineStarts) {
 119                 return numCharsBeforeEOL;
 120         } else {
 121                 return lineStarts[line+1];
 122         }
 123 }
 124
 125 bool LineLayout::InLine(int offset, int line) const {
 126         return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) ||
 127                 ((offset == numCharsInLine) && (line == (lines-1)));
 128 }
 129
 130 void LineLayout::SetLineStart(int line, int start) {
 131         if ((line >= lenLineStarts) && (line != 0)) {
 132                 int newMaxLines = line + 20;
 133                 int *newLineStarts = new int[newMaxLines];
 134                 for (int i = 0; i < newMaxLines; i++) {
 135                         if (i < lenLineStarts)
 136                                 newLineStarts[i] = lineStarts[i];
 137                         else
 138                                 newLineStarts[i] = 0;
 139                 }
 140                 delete []lineStarts;
 141                 lineStarts = newLineStarts;
 142                 lenLineStarts = newMaxLines;
 143         }
 144         lineStarts[line] = start;
 145 }
 146
 147 void LineLayout::SetBracesHighlight(Range rangeLine, Position braces[],
 148                                     char bracesMatchStyle, int xHighlight) {
 149         if (rangeLine.ContainsCharacter(braces[0])) {
 150                 int braceOffset = braces[0] - rangeLine.start;
 151                 if (braceOffset < numCharsInLine) {
 152                         bracePreviousStyles[0] = styles[braceOffset];
 153                         styles[braceOffset] = bracesMatchStyle;
 154                 }
 155         }
 156         if (rangeLine.ContainsCharacter(braces[1])) {
 157                 int braceOffset = braces[1] - rangeLine.start;
 158                 if (braceOffset < numCharsInLine) {
 159                         bracePreviousStyles[1] = styles[braceOffset];
 160                         styles[braceOffset] = bracesMatchStyle;
 161                 }
 162         }
 163         if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
 164                 (braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
 165                 xHighlightGuide = xHighlight;
 166         }
 167 }
 168
 169 void LineLayout::RestoreBracesHighlight(Range rangeLine, Position braces[]) {
 170         if (rangeLine.ContainsCharacter(braces[0])) {
 171                 int braceOffset = braces[0] - rangeLine.start;
 172                 if (braceOffset < numCharsInLine) {
 173                         styles[braceOffset] = bracePreviousStyles[0];
 174                 }
 175         }
 176         if (rangeLine.ContainsCharacter(braces[1])) {
 177                 int braceOffset = braces[1] - rangeLine.start;
 178                 if (braceOffset < numCharsInLine) {
 179                         styles[braceOffset] = bracePreviousStyles[1];
 180                 }
 181         }
 182         xHighlightGuide = 0;
 183 }
 184
 185 int LineLayout::FindBefore(int x, int lower, int upper) const {
 186         do {
 187                 int middle = (upper + lower + 1) / 2;   // Round high
 188                 int posMiddle = positions[middle];
 189                 if (x < posMiddle) {
 190                         upper = middle - 1;
 191                 } else {
 192                         lower = middle;
 193                 }
 194         } while (lower < upper);
 195         return lower;
 196 }
 197
 198 int LineLayout::EndLineStyle() const {
 199         return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0];
 200 }
 201
 202 LineLayoutCache::LineLayoutCache() :
 203         level(0), length(0), size(0), cache(0),
 204         allInvalidated(false), styleClock(-1), useCount(0) {
 205         Allocate(0);
 206 }
 207
 208 LineLayoutCache::~LineLayoutCache() {
 209         Deallocate();
 210 }
 211
 212 void LineLayoutCache::Allocate(int length_) {
 213         PLATFORM_ASSERT(cache == NULL);
 214         allInvalidated = false;
 215         length = length_;
 216         size = length;
 217         if (size > 1) {
 218                 size = (size / 16 + 1) * 16;
 219         }
 220         if (size > 0) {
 221                 cache = new LineLayout * [size];
 222         }
 223         for (int i = 0; i < size; i++)
 224                 cache[i] = 0;
 225 }
 226
 227 void LineLayoutCache::AllocateForLevel(int linesOnScreen, int linesInDoc) {
 228         PLATFORM_ASSERT(useCount == 0);
 229         int lengthForLevel = 0;
 230         if (level == llcCaret) {
 231                 lengthForLevel = 1;
 232         } else if (level == llcPage) {
 233                 lengthForLevel = linesOnScreen + 1;
 234         } else if (level == llcDocument) {
 235                 lengthForLevel = linesInDoc;
 236         }
 237         if (lengthForLevel > size) {
 238                 Deallocate();
 239                 Allocate(lengthForLevel);
 240         } else {
 241                 if (lengthForLevel < length) {
 242                         for (int i = lengthForLevel; i < length; i++) {
 243                                 delete cache[i];
 244                                 cache[i] = 0;
 245                         }
 246                 }
 247                 length = lengthForLevel;
 248         }
 249         PLATFORM_ASSERT(length == lengthForLevel);
 250         PLATFORM_ASSERT(cache != NULL || length == 0);
 251 }
 252
 253 void LineLayoutCache::Deallocate() {
 254         PLATFORM_ASSERT(useCount == 0);
 255         for (int i = 0; i < length; i++)
 256                 delete cache[i];
 257         delete []cache;
 258         cache = 0;
 259         length = 0;
 260         size = 0;
 261 }
 262
 263 void LineLayoutCache::Invalidate(LineLayout::validLevel validity_) {
 264         if (cache && !allInvalidated) {
 265                 for (int i = 0; i < length; i++) {
 266                         if (cache[i]) {
 267                                 cache[i]->Invalidate(validity_);
 268                         }
 269                 }
 270                 if (validity_ == LineLayout::llInvalid) {
 271                         allInvalidated = true;
 272                 }
 273         }
 274 }
 275
 276 void LineLayoutCache::SetLevel(int level_) {
 277         allInvalidated = false;
 278         if ((level_ != -1) && (level != level_)) {
 279                 level = level_;
 280                 Deallocate();
 281         }
 282 }
 283
 284 LineLayout *LineLayoutCache::Retrieve(int lineNumber, int lineCaret, int maxChars, int styleClock_,
 285                                       int linesOnScreen, int linesInDoc) {
 286         AllocateForLevel(linesOnScreen, linesInDoc);
 287         if (styleClock != styleClock_) {
 288                 Invalidate(LineLayout::llCheckTextAndStyle);
 289                 styleClock = styleClock_;
 290         }
 291         allInvalidated = false;
 292         int pos = -1;
 293         LineLayout *ret = 0;
 294         if (level == llcCaret) {
 295                 pos = 0;
 296         } else if (level == llcPage) {
 297                 if (lineNumber == lineCaret) {
 298                         pos = 0;
 299                 } else if (length > 1) {
 300                         pos = 1 + (lineNumber % (length - 1));
 301                 }
 302         } else if (level == llcDocument) {
 303                 pos = lineNumber;
 304         }
 305         if (pos >= 0) {
 306                 PLATFORM_ASSERT(useCount == 0);
 307                 if (cache && (pos < length)) {
 308                         if (cache[pos]) {
 309                                 if ((cache[pos]->lineNumber != lineNumber) ||
 310                                         (cache[pos]->maxLineLength < maxChars)) {
 311                                         delete cache[pos];
 312                                         cache[pos] = 0;
 313                                 }
 314                         }
 315                         if (!cache[pos]) {
 316                                 cache[pos] = new LineLayout(maxChars);
 317                         }
 318                         if (cache[pos]) {
 319                                 cache[pos]->lineNumber = lineNumber;
 320                                 cache[pos]->inCache = true;
 321                                 ret = cache[pos];
 322                                 useCount++;
 323                         }
 324                 }
 325         }
 326
 327         if (!ret) {
 328                 ret = new LineLayout(maxChars);
 329                 ret->lineNumber = lineNumber;
 330         }
 331
 332         return ret;
 333 }
 334
 335 void LineLayoutCache::Dispose(LineLayout *ll) {
 336         allInvalidated = false;
 337         if (ll) {
 338                 if (!ll->inCache) {
 339                         delete ll;
 340                 } else {
 341                         useCount--;
 342                 }
 343         }
 344 }
 345
 346 void BreakFinder::Insert(int val) {
 347         // Expand if needed
 348         if (saeLen >= saeSize) {
 349                 saeSize *= 2;
 350                 int *selAndEdgeNew = new int[saeSize];
 351                 for (unsigned int j = 0; j<saeLen; j++) {
 352                         selAndEdgeNew[j] = selAndEdge[j];
 353                 }
 354                 delete []selAndEdge;
 355                 selAndEdge = selAndEdgeNew;
 356         }
 357
 358         if (val >= nextBreak) {
 359                 for (unsigned int j = 0; j<saeLen; j++) {
 360                         if (val == selAndEdge[j]) {
 361                                 return;
 362                         } if (val < selAndEdge[j]) {
 363                                 for (unsigned int k = saeLen; k>j; k--) {
 364                                         selAndEdge[k] = selAndEdge[k-1];
 365                                 }
 366                                 saeLen++;
 367                                 selAndEdge[j] = val;
 368                                 return;
 369                         }
 370                 }
 371                 // Not less than any so append
 372                 selAndEdge[saeLen++] = val;
 373         }
 374 }
 375
 376 extern bool BadUTF(const char *s, int len, int &trailBytes);
 377
 378 static int NextBadU(const char *s, int p, int len, int &trailBytes) {
 379         while (p < len) {
 380                 p++;
 381                 if (BadUTF(s + p, len - p, trailBytes))
 382                         return p;
 383         }
 384         return -1;
 385 }
 386
 387 BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_, bool utf8_, int xStart, bool breakForSelection) :
 388         ll(ll_),
 389         lineStart(lineStart_),
 390         lineEnd(lineEnd_),
 391         posLineStart(posLineStart_),
 392         utf8(utf8_),
 393         nextBreak(lineStart_),
 394         saeSize(0),
 395         saeLen(0),
 396         saeCurrentPos(0),
 397         saeNext(0),
 398         subBreak(-1) {
 399         saeSize = 8;
 400         selAndEdge = new int[saeSize];
 401         for (unsigned int j=0; j < saeSize; j++) {
 402                 selAndEdge[j] = 0;
 403         }
 404
 405         // Search for first visible break
 406         // First find the first visible character
 407         nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
 408         // Now back to a style break
 409         while ((nextBreak > lineStart) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
 410                 nextBreak--;
 411         }
 412
 413         if (breakForSelection) {
 414                 SelectionPosition posStart(posLineStart);
 415                 SelectionPosition posEnd(posLineStart + lineEnd);
 416                 SelectionSegment segmentLine(posStart, posEnd);
 417                 for (size_t r=0; r<ll->psel->Count(); r++) {
 418                         SelectionSegment portion = ll->psel->Range(r).Intersect(segmentLine);
 419                         if (!(portion.start == portion.end)) {
 420                                 if (portion.start.IsValid())
 421                                         Insert(portion.start.Position() - posLineStart - 1);
 422                                 if (portion.end.IsValid())
 423                                         Insert(portion.end.Position() - posLineStart - 1);
 424                         }
 425                 }
 426         }
 427
 428         Insert(ll->edgeColumn - 1);
 429         Insert(lineEnd - 1);
 430
 431         if (utf8) {
 432                 int trailBytes=0;
 433                 for (int pos = -1;;) {
 434                         pos = NextBadU(ll->chars, pos, lineEnd, trailBytes);
 435                         if (pos < 0)
 436                                 break;
 437                         Insert(pos-1);
 438                         Insert(pos);
 439                 }
 440         }
 441         saeNext = (saeLen > 0) ? selAndEdge[0] : -1;
 442 }
 443
 444 BreakFinder::~BreakFinder() {
 445         delete []selAndEdge;
 446 }
 447
 448 int BreakFinder::First() {
 449         return nextBreak;
 450 }
 451
 452 static bool IsTrailByte(int ch) {
 453         return (ch >= 0x80) && (ch < (0x80 + 0x40));
 454 }
 455
 456 int BreakFinder::Next() {
 457         if (subBreak == -1) {
 458                 int prev = nextBreak;
 459                 while (nextBreak < lineEnd) {
 460                         if ((ll->styles[nextBreak] != ll->styles[nextBreak + 1]) ||
 461                                         (nextBreak == saeNext) ||
 462                                         IsControlCharacter(ll->chars[nextBreak]) || IsControlCharacter(ll->chars[nextBreak + 1])) {
 463                                 if (nextBreak == saeNext) {
 464                                         saeCurrentPos++;
 465                                         saeNext = (saeLen > saeCurrentPos) ? selAndEdge[saeCurrentPos] : -1;
 466                                 }
 467                                 nextBreak++;
 468                                 if ((nextBreak - prev) < lengthStartSubdivision) {
 469                                         return nextBreak;
 470                                 }
 471                                 break;
 472                         }
 473                         nextBreak++;
 474                 }
 475                 if ((nextBreak - prev) < lengthStartSubdivision) {
 476                         return nextBreak;
 477                 }
 478                 subBreak = prev;
 479         }
 480         // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
 481         // For very long runs add extra breaks after spaces or if no spaces before low punctuation.
 482         if ((nextBreak - subBreak) <= lengthEachSubdivision) {
 483                 subBreak = -1;
 484                 return nextBreak;
 485         } else {
 486                 int lastGoodBreak = -1;
 487                 int lastOKBreak = -1;
 488                 int lastUTF8Break = -1;
 489                 int j;
 490                 for (j = subBreak + 1; j <= nextBreak; j++) {
 491                         if (IsSpaceOrTab(ll->chars[j - 1]) && !IsSpaceOrTab(ll->chars[j])) {
 492                                 lastGoodBreak = j;
 493                         }
 494                         if (static_cast<unsigned char>(ll->chars[j]) < 'A') {
 495                                 lastOKBreak = j;
 496                         }
 497                         if (utf8 && !IsTrailByte(static_cast<unsigned char>(ll->chars[j]))) {
 498                                 lastUTF8Break = j;
 499                         }
 500                         if (((j - subBreak) >= lengthEachSubdivision) &&
 501                                 ((lastGoodBreak >= 0) || (lastOKBreak >= 0) || (lastUTF8Break >= 0))) {
 502                                 break;
 503                         }
 504                 }
 505                 if (lastGoodBreak >= 0) {
 506                         subBreak = lastGoodBreak;
 507                 } else if (lastOKBreak >= 0) {
 508                         subBreak = lastOKBreak;
 509                 } else if (lastUTF8Break >= 0) {
 510                         subBreak = lastUTF8Break;
 511                 } else {
 512                         subBreak = nextBreak;
 513                 }
 514                 if (subBreak >= nextBreak) {
 515                         subBreak = -1;
 516                         return nextBreak;
 517                 } else {
 518                         return subBreak;
 519                 }
 520         }
 521 }
 522
 523 PositionCacheEntry::PositionCacheEntry() :
 524         styleNumber(0), len(0), clock(0), positions(0) {
 525 }
 526
 527 void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_,
 528         unsigned int len_, int *positions_, unsigned int clock_) {
 529         Clear();
 530         styleNumber = styleNumber_;
 531         len = len_;
 532         clock = clock_;
 533         if (s_ && positions_) {
 534                 positions = new short[len + (len + 1) / 2];
 535                 for (unsigned int i=0;i<len;i++) {
 536                         positions[i] = static_cast<short>(positions_[i]);
 537                 }
 538                 memcpy(reinterpret_cast<char *>(positions + len), s_, len);
 539         }
 540 }
 541
 542 PositionCacheEntry::~PositionCacheEntry() {
 543         Clear();
 544 }
 545
 546 void PositionCacheEntry::Clear() {
 547         delete []positions;
 548         positions = 0;
 549         styleNumber = 0;
 550         len = 0;
 551         clock = 0;
 552 }
 553
 554 bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_,
 555         unsigned int len_, int *positions_) const {
 556         if ((styleNumber == styleNumber_) && (len == len_) &&
 557                 (memcmp(reinterpret_cast<char *>(positions + len), s_, len)== 0)) {
 558                 for (unsigned int i=0;i<len;i++) {
 559                         positions_[i] = positions[i];
 560                 }
 561                 return true;
 562         } else {
 563                 return false;
 564         }
 565 }
 566
 567 int PositionCacheEntry::Hash(unsigned int styleNumber, const char *s, unsigned int len) {
 568         unsigned int ret = s[0] << 7;
 569         for (unsigned int i=0; i<len; i++) {
 570                 ret *= 1000003;
 571                 ret ^= s[i];
 572         }
 573         ret *= 1000003;
 574         ret ^= len;
 575         ret *= 1000003;
 576         ret ^= styleNumber;
 577         return ret;
 578 }
 579
 580 bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) {
 581         return clock > other.clock;
 582 }
 583
 584 void PositionCacheEntry::ResetClock() {
 585         if (clock > 0) {
 586                 clock = 1;
 587         }
 588 }
 589
 590 PositionCache::PositionCache() {
 591         size = 0x400;
 592         clock = 1;
 593         pces = new PositionCacheEntry[size];
 594         allClear = true;
 595 }
 596
 597 PositionCache::~PositionCache() {
 598         Clear();
 599         delete []pces;
 600 }
 601
 602 void PositionCache::Clear() {
 603         if (!allClear) {
 604                 for (size_t i=0;i<size;i++) {
 605                         pces[i].Clear();
 606                 }
 607         }
 608         clock = 1;
 609         allClear = true;
 610 }
 611
 612 void PositionCache::SetSize(size_t size_) {
 613         Clear();
 614         delete []pces;
 615         size = size_;
 616         pces = new PositionCacheEntry[size];
 617 }
 618
 619 void PositionCache::MeasureWidths(Surface *surface, ViewStyle &vstyle, unsigned int styleNumber,
 620         const char *s, unsigned int len, int *positions) {
 621         allClear = false;
 622         int probe = -1;
 623         if ((size > 0) && (len < 30)) {
 624                 // Only store short strings in the cache so it doesn't churn with
 625                 // long comments with only a single comment.
 626
 627                 // Two way associative: try two probe positions.
 628                 int hashValue = PositionCacheEntry::Hash(styleNumber, s, len);
 629                 probe = hashValue % size;
 630                 if (pces[probe].Retrieve(styleNumber, s, len, positions)) {
 631                         return;
 632                 }
 633                 int probe2 = (hashValue * 37) % size;
 634                 if (pces[probe2].Retrieve(styleNumber, s, len, positions)) {
 635                         return;
 636                 }
 637                 // Not found. Choose the oldest of the two slots to replace
 638                 if (pces[probe].NewerThan(pces[probe2])) {
 639                         probe = probe2;
 640                 }
 641         }
 642         surface->MeasureWidths(vstyle.styles[styleNumber].font, s, len, positions);
 643         if (probe >= 0) {
 644                 clock++;
 645                 if (clock > 60000) {
 646                         // Since there are only 16 bits for the clock, wrap it round and
 647                         // reset all cache entries so none get stuck with a high clock.
 648                         for (size_t i=0;i<size;i++) {
 649                                 pces[i].ResetClock();
 650                         }
 651                         clock = 2;
 652                 }
 653                 pces[probe].Set(styleNumber, s, len, positions, clock);
 654         }
 655 }