// Scintilla source code edit control
/** @file PositionCache.cxx
 ** Classes for caching layout information.
 **/
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
// The License.txt file describes the conditions under which this software may be distributed.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>

#include "Platform.h"

#include "Scintilla.h"

#include "SplitVector.h"
#include "Partitioning.h"
#include "RunStyles.h"
#include "ContractionState.h"
#include "CellBuffer.h"
#include "KeyMap.h"
#include "Indicator.h"
#include "XPM.h"
#include "LineMarker.h"
#include "Style.h"
#include "ViewStyle.h"
#include "CharClassify.h"
#include "Decoration.h"
#include "Document.h"
#include "PositionCache.h"

#ifdef SCI_NAMESPACE
using namespace Scintilla;
#endif

static inline bool IsControlCharacter(int ch) {
   // iscntrl returns true for lots of chars > 127 which are displayable
   return ch >= 0 && ch < ' ';
}

LineLayout::LineLayout(int maxLineLength_) :
   lineStarts(0),
   lenLineStarts(0),
   lineNumber(-1),
   inCache(false),
   maxLineLength(-1),
   numCharsInLine(0),
   validity(llInvalid),
   xHighlightGuide(0),
   highlightColumn(0),
   selStart(0),
   selEnd(0),
   containsCaret(false),
   edgeColumn(0),
   chars(0),
   styles(0),
   styleBitsSet(0),
   indicators(0),
   positions(0),
   hsStart(0),
   hsEnd(0),
   widthLine(wrapWidthInfinite),
   lines(1) {
   Resize(maxLineLength_);
}

LineLayout::~LineLayout() {
   Free();
}

void LineLayout::Resize(int maxLineLength_) {
   if (maxLineLength_ > maxLineLength) {
      Free();
      chars = new char[maxLineLength_ + 1];
      styles = new unsigned char[maxLineLength_ + 1];
      indicators = new char[maxLineLength_ + 1];
      // Extra position allocated as sometimes the Windows
      // GetTextExtentExPoint API writes an extra element.
      positions = new int[maxLineLength_ + 1 + 1];
      maxLineLength = maxLineLength_;
   }
}

void LineLayout::Free() {
   delete []chars;
   chars = 0;
   delete []styles;
   styles = 0;
   delete []indicators;
   indicators = 0;
   delete []positions;
   positions = 0;
   delete []lineStarts;
   lineStarts = 0;
}

void LineLayout::Invalidate(validLevel validity_) {
   if (validity > validity_)
      validity = validity_;
}

int LineLayout::LineStart(int line) const {
   if (line <= 0) {
      return 0;
   } else if ((line >= lines) || !lineStarts) {
      return numCharsInLine;
   } else {
      return lineStarts[line];
   }
}

int LineLayout::LineLastVisible(int line) const {
   if (line < 0) {
      return 0;
   } else if ((line >= lines-1) || !lineStarts) {
      int startLine = LineStart(line);
      int endLine = numCharsInLine;
      while ((endLine > startLine) && IsEOLChar(chars[endLine-1])) {
         endLine--;
      }
      return endLine;
   } else {
      return lineStarts[line+1];
   }
}

bool LineLayout::InLine(int offset, int line) const {
   return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) ||
      ((offset == numCharsInLine) && (line == (lines-1)));
}

void LineLayout::SetLineStart(int line, int start) {
   if ((line >= lenLineStarts) && (line != 0)) {
      int newMaxLines = line + 20;
      int *newLineStarts = new int[newMaxLines];
      if (!newLineStarts)
         return;
      for (int i = 0; i < newMaxLines; i++) {
         if (i < lenLineStarts)
            newLineStarts[i] = lineStarts[i];
         else
            newLineStarts[i] = 0;
      }
      delete []lineStarts;
      lineStarts = newLineStarts;
      lenLineStarts = newMaxLines;
   }
   lineStarts[line] = start;
}

void LineLayout::SetBracesHighlight(Range rangeLine, Position braces[],
                                    char bracesMatchStyle, int xHighlight) {
   if (rangeLine.ContainsCharacter(braces[0])) {
      int braceOffset = braces[0] - rangeLine.start;
      if (braceOffset < numCharsInLine) {
         bracePreviousStyles[0] = styles[braceOffset];
         styles[braceOffset] = bracesMatchStyle;
      }
   }
   if (rangeLine.ContainsCharacter(braces[1])) {
      int braceOffset = braces[1] - rangeLine.start;
      if (braceOffset < numCharsInLine) {
         bracePreviousStyles[1] = styles[braceOffset];
         styles[braceOffset] = bracesMatchStyle;
      }
   }
   if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
           (braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
      xHighlightGuide = xHighlight;
   }
}

void LineLayout::RestoreBracesHighlight(Range rangeLine, Position braces[]) {
   if (rangeLine.ContainsCharacter(braces[0])) {
      int braceOffset = braces[0] - rangeLine.start;
      if (braceOffset < numCharsInLine) {
         styles[braceOffset] = bracePreviousStyles[0];
      }
   }
   if (rangeLine.ContainsCharacter(braces[1])) {
      int braceOffset = braces[1] - rangeLine.start;
      if (braceOffset < numCharsInLine) {
         styles[braceOffset] = bracePreviousStyles[1];
      }
   }
   xHighlightGuide = 0;
}

int LineLayout::FindBefore(int x, int lower, int upper) const {
   do {
      int middle = (upper + lower + 1) / 2;    // Round high
      int posMiddle = positions[middle];
      if (x < posMiddle) {
         upper = middle - 1;
      } else {
         lower = middle;
      }
   } while (lower < upper);
   return lower;
}

LineLayoutCache::LineLayoutCache() :
   level(0), length(0), size(0), cache(0),
   allInvalidated(false), styleClock(-1), useCount(0) {
   Allocate(0);
}

LineLayoutCache::~LineLayoutCache() {
   Deallocate();
}

void LineLayoutCache::Allocate(int length_) {
   PLATFORM_ASSERT(cache == NULL);
   allInvalidated = false;
   length = length_;
   size = length;
   if (size > 1) {
      size = (size / 16 + 1) * 16;
   }
   if (size > 0) {
      cache = new LineLayout * [size];
   }
   for (int i = 0; i < size; i++)
      cache[i] = 0;
}

void LineLayoutCache::AllocateForLevel(int linesOnScreen, int linesInDoc) {
   PLATFORM_ASSERT(useCount == 0);
   int lengthForLevel = 0;
   if (level == llcCaret) {
      lengthForLevel = 1;
   } else if (level == llcPage) {
      lengthForLevel = linesOnScreen + 1;
   } else if (level == llcDocument) {
      lengthForLevel = linesInDoc;
   }
   if (lengthForLevel > size) {
      Deallocate();
      Allocate(lengthForLevel);
   } else {
      if (lengthForLevel < length) {
         for (int i = lengthForLevel; i < length; i++) {
            delete cache[i];
            cache[i] = 0;
         }
      }
      length = lengthForLevel;
   }
   PLATFORM_ASSERT(length == lengthForLevel);
   PLATFORM_ASSERT(cache != NULL || length == 0);
}

void LineLayoutCache::Deallocate() {
   PLATFORM_ASSERT(useCount == 0);
   for (int i = 0; i < length; i++)
      delete cache[i];
   delete []cache;
   cache = 0;
   length = 0;
   size = 0;
}

void LineLayoutCache::Invalidate(LineLayout::validLevel validity_) {
   if (cache && !allInvalidated) {
      for (int i = 0; i < length; i++) {
         if (cache[i]) {
            cache[i]->Invalidate(validity_);
         }
      }
      if (validity_ == LineLayout::llInvalid) {
         allInvalidated = true;
      }
   }
}

void LineLayoutCache::SetLevel(int level_) {
   allInvalidated = false;
   if ((level_ != -1) && (level != level_)) {
      level = level_;
      Deallocate();
   }
}

LineLayout *LineLayoutCache::Retrieve(int lineNumber, int lineCaret, int maxChars, int styleClock_,
                                      int linesOnScreen, int linesInDoc) {
   AllocateForLevel(linesOnScreen, linesInDoc);
   if (styleClock != styleClock_) {
      Invalidate(LineLayout::llCheckTextAndStyle);
      styleClock = styleClock_;
   }
   allInvalidated = false;
   int pos = -1;
   LineLayout *ret = 0;
   if (level == llcCaret) {
      pos = 0;
   } else if (level == llcPage) {
      if (lineNumber == lineCaret) {
         pos = 0;
      } else if (length > 1) {
         pos = 1 + (lineNumber % (length - 1));
      }
   } else if (level == llcDocument) {
      pos = lineNumber;
   }
   if (pos >= 0) {
      PLATFORM_ASSERT(useCount == 0);
      if (cache && (pos < length)) {
         if (cache[pos]) {
            if ((cache[pos]->lineNumber != lineNumber) ||
                    (cache[pos]->maxLineLength < maxChars)) {
               delete cache[pos];
               cache[pos] = 0;
            }
         }
         if (!cache[pos]) {
            cache[pos] = new LineLayout(maxChars);
         }
         if (cache[pos]) {
            cache[pos]->lineNumber = lineNumber;
            cache[pos]->inCache = true;
            ret = cache[pos];
            useCount++;
         }
      }
   }

   if (!ret) {
      ret = new LineLayout(maxChars);
      ret->lineNumber = lineNumber;
   }

   return ret;
}

void LineLayoutCache::Dispose(LineLayout *ll) {
   allInvalidated = false;
   if (ll) {
      if (!ll->inCache) {
         delete ll;
      } else {
         useCount--;
      }
   }
}

void BreakFinder::Insert(int val) {
   // Expand if needed
   if (saeLen >= saeSize) {
      saeSize *= 2;
      int *selAndEdgeNew = new int[saeSize];
      for (unsigned int j = 0; j<saeLen; j++) {
         selAndEdgeNew[j] = selAndEdge[j];
      }
      delete []selAndEdge;
      selAndEdge = selAndEdgeNew;
   }

   if (val >= nextBreak) {
      for (unsigned int j = 0; j<saeLen; j++) {
         if (val == selAndEdge[j]) {
            return;
         } if (val < selAndEdge[j]) {
            for (unsigned int k = saeLen; k>j; k--) {
               selAndEdge[k] = selAndEdge[k-1];
            }
            saeLen++;
            selAndEdge[j] = val;
            return;
         }
      }
      // Not less than any so append
      selAndEdge[saeLen++] = val;
   }
}

extern bool BadUTF(const char *s, int len, int &trailBytes);

static int NextBadU(const char *s, int p, int len, int &trailBytes) {
   while (p < len) {
      p++;
      if (BadUTF(s + p, len - p, trailBytes))
         return p;
   }
   return -1;
}

BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_, bool utf8_, int xStart) :
   ll(ll_),
   lineStart(lineStart_),
   lineEnd(lineEnd_),
   posLineStart(posLineStart_),
   utf8(utf8_),
   nextBreak(lineStart_),
   saeSize(0),
   saeLen(0),
   saeCurrentPos(0),
   saeNext(0),
   subBreak(-1) {
   saeSize = 8;
   selAndEdge = new int[saeSize];
   for (unsigned int j=0; j < saeSize; j++) {
      selAndEdge[j] = 0;
   }

   // Search for first visible break
   // First find the first visible character
   nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
   // Now back to a style break
   while ((nextBreak > lineStart) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
      nextBreak--;
   }

   if (ll->selStart != ll->selEnd) {
      Insert(ll->selStart - posLineStart - 1);
      Insert(ll->selEnd - posLineStart - 1);
   }

   Insert(ll->edgeColumn - 1);
   Insert(lineEnd - 1);

   if (utf8) {
      int trailBytes=0;
      for (int pos = -1;;) {
         pos = NextBadU(ll->chars, pos, lineEnd, trailBytes);
         if (pos < 0)
            break;
         Insert(pos-1);
         Insert(pos);
      }
   }
   saeNext = (saeLen > 0) ? selAndEdge[0] : -1;
}

BreakFinder::~BreakFinder() {
   delete []selAndEdge;
}

int BreakFinder::First() {
   return nextBreak;
}

int BreakFinder::Next() {
   if (subBreak == -1) {
      int prev = nextBreak;
      while (nextBreak < lineEnd) {
         if ((ll->styles[nextBreak] != ll->styles[nextBreak + 1]) ||
               (nextBreak == saeNext) ||
               IsControlCharacter(ll->chars[nextBreak]) || IsControlCharacter(ll->chars[nextBreak + 1])) {
            if (nextBreak == saeNext) {
               saeCurrentPos++;
               saeNext = (saeLen > saeCurrentPos) ? selAndEdge[saeCurrentPos] : -1;
            }
            nextBreak++;
            if ((nextBreak - prev) < lengthStartSubdivision) {
               return nextBreak;
            }
            break;
         }
         nextBreak++;
      }
      if ((nextBreak - prev) < lengthStartSubdivision) {
         return nextBreak;
      }
      subBreak = prev;
   }
   // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
   // For very long runs add extra breaks after spaces or if no spaces before low punctuation.
   if ((nextBreak - subBreak) <= lengthEachSubdivision) {
      subBreak = -1;
      return nextBreak;
   } else {
      int lastGoodBreak = -1;
      int lastOKBreak = -1;
      int j;
      for (j = subBreak + 1; j <= nextBreak; j++) {
         if (IsSpaceOrTab(ll->chars[j - 1]) && !IsSpaceOrTab(ll->chars[j])) {
            lastGoodBreak = j;
         }
         if (ll->chars[j] < 'A') {
            lastOKBreak = j;
         }
         if (((j - subBreak) >= lengthEachSubdivision) && ((lastGoodBreak >= 0) || (lastOKBreak >= 0))) {
            break;
         }
      }
      if (lastGoodBreak >= 0) {
         subBreak = lastGoodBreak;
      } else if (lastOKBreak >= 0) {
         subBreak = lastOKBreak;
      } else {
         subBreak = nextBreak;
      }
      if (subBreak >= nextBreak) {
         subBreak = -1;
         return nextBreak;
      } else {
         return subBreak;
      }
   }
}

PositionCacheEntry::PositionCacheEntry() :
   styleNumber(0), len(0), clock(0), positions(0) {
}

void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_,
   unsigned int len_, int *positions_, unsigned int clock_) {
   Clear();
   styleNumber = styleNumber_;
   len = len_;
   clock = clock_;
   if (s_ && positions_) {
      positions = new short[len + (len + 1) / 2];
      for (unsigned int i=0;i<len;i++) {
         positions[i] = static_cast<short>(positions_[i]);
      }
      memcpy(reinterpret_cast<char *>(positions + len), s_, len);
   }
}

PositionCacheEntry::~PositionCacheEntry() {
   Clear();
}

void PositionCacheEntry::Clear() {
   delete []positions;
   positions = 0;
   styleNumber = 0;
   len = 0;
   clock = 0;
}

bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_,
   unsigned int len_, int *positions_) const {
   if ((styleNumber == styleNumber_) && (len == len_) &&
      (memcmp(reinterpret_cast<char *>(positions + len), s_, len)== 0)) {
      for (unsigned int i=0;i<len;i++) {
         positions_[i] = positions[i];
      }
      return true;
   } else {
      return false;
   }
}

int PositionCacheEntry::Hash(unsigned int styleNumber, const char *s, unsigned int len) {
   unsigned int ret = s[0] << 7;
   for (unsigned int i=0; i<len; i++) {
      ret *= 1000003;
      ret ^= s[i];
   }
   ret *= 1000003;
   ret ^= len;
   ret *= 1000003;
   ret ^= styleNumber;
   return ret;
}

bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) {
   return clock > other.clock;
}

void PositionCacheEntry::ResetClock() {
   if (clock > 0) {
      clock = 1;
   }
}

PositionCache::PositionCache() {
   size = 0x400;
   clock = 1;
   pces = new PositionCacheEntry[size];
   allClear = true;
}

PositionCache::~PositionCache() {
   Clear();
   delete []pces;
}

void PositionCache::Clear() {
   if (!allClear) {
      for (size_t i=0;i<size;i++) {
         pces[i].Clear();
      }
   }
   clock = 1;
   allClear = true;
}

void PositionCache::SetSize(size_t size_) {
   Clear();
   delete []pces;
   size = size_;
   pces = new PositionCacheEntry[size];
}

void PositionCache::MeasureWidths(Surface *surface, ViewStyle &vstyle, unsigned int styleNumber,
   const char *s, unsigned int len, int *positions) {
   allClear = false;
   int probe = -1;
   if ((size > 0) && (len < 30)) {
      // Only store short strings in the cache so it doesn't churn with
      // long comments with only a single comment.

      // Two way associative: try two probe positions.
      int hashValue = PositionCacheEntry::Hash(styleNumber, s, len);
      probe = hashValue % size;
      if (pces[probe].Retrieve(styleNumber, s, len, positions)) {
         return;
      }
      int probe2 = (hashValue * 37) % size;
      if (pces[probe2].Retrieve(styleNumber, s, len, positions)) {
         return;
      }
      // Not found. Choose the oldest of the two slots to replace
      if (pces[probe].NewerThan(pces[probe2])) {
         probe = probe2;
      }
   }
   surface->MeasureWidths(vstyle.styles[styleNumber].font, s, len, positions);
   if (probe >= 0) {
      clock++;
      if (clock > 60000) {
         // Since there are only 16 bits for the clock, wrap it round and
         // reset all cache entries so none get stuck with a high clock.
         for (size_t i=0;i<size;i++) {
            pces[i].ResetClock();
         }
         clock = 2;
      }
      pces[probe].Set(styleNumber, s, len, positions, clock);
   }
}
