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