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