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