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