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