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