ext/scintilla/src/RunStyles.cxx

   1 /** @file RunStyles.cxx
   2  ** Data structure used to store sparse styles.
   3  **/
   4 // Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
   5 // The License.txt file describes the conditions under which this software may be distributed.
   6
   7 #include <cstddef>
   8 #include <cstdlib>
   9 #include <cstdint>
  10 #include <cstring>
  11 #include <cstdio>
  12 #include <cstdarg>
  13 #include <climits>
  14
  15 #include <stdexcept>
  16 #include <string_view>
  17 #include <vector>
  18 #include <optional>
  19 #include <algorithm>
  20 #include <memory>
  21
  22 #include "Debugging.h"
  23
  24 #include "Position.h"
  25 #include "SplitVector.h"
  26 #include "Partitioning.h"
  27 #include "RunStyles.h"
  28
  29 using namespace Scintilla::Internal;
  30
  31 // Find the first run at a position
  32 template <typename DISTANCE, typename STYLE>
  33 DISTANCE RunStyles<DISTANCE, STYLE>::RunFromPosition(DISTANCE position) const noexcept {
  34         DISTANCE run = starts.PartitionFromPosition(position);
  35         // Go to first element with this position
  36         while ((run > 0) && (position == starts.PositionFromPartition(run-1))) {
  37                 run--;
  38         }
  39         return run;
  40 }
  41
  42 // If there is no run boundary at position, insert one continuing style.
  43 template <typename DISTANCE, typename STYLE>
  44 DISTANCE RunStyles<DISTANCE, STYLE>::SplitRun(DISTANCE position) {
  45         DISTANCE run = RunFromPosition(position);
  46         const DISTANCE posRun = starts.PositionFromPartition(run);
  47         if (posRun < position) {
  48                 STYLE runStyle = ValueAt(position);
  49                 run++;
  50                 starts.InsertPartition(run, position);
  51                 styles.InsertValue(run, 1, runStyle);
  52         }
  53         return run;
  54 }
  55
  56 template <typename DISTANCE, typename STYLE>
  57 void RunStyles<DISTANCE, STYLE>::RemoveRun(DISTANCE run) {
  58         starts.RemovePartition(run);
  59         styles.DeleteRange(run, 1);
  60 }
  61
  62 template <typename DISTANCE, typename STYLE>
  63 void RunStyles<DISTANCE, STYLE>::RemoveRunIfEmpty(DISTANCE run) {
  64         if ((run < starts.Partitions()) && (starts.Partitions() > 1)) {
  65                 if (starts.PositionFromPartition(run) == starts.PositionFromPartition(run+1)) {
  66                         RemoveRun(run);
  67                 }
  68         }
  69 }
  70
  71 template <typename DISTANCE, typename STYLE>
  72 void RunStyles<DISTANCE, STYLE>::RemoveRunIfSameAsPrevious(DISTANCE run) {
  73         if ((run > 0) && (run < starts.Partitions())) {
  74                 const DISTANCE runBefore = run - 1;
  75                 if (styles.ValueAt(runBefore) == styles.ValueAt(run)) {
  76                         RemoveRun(run);
  77                 }
  78         }
  79 }
  80
  81 template <typename DISTANCE, typename STYLE>
  82 RunStyles<DISTANCE, STYLE>::RunStyles() {
  83         starts = Partitioning<DISTANCE>(8);
  84         styles = SplitVector<STYLE>();
  85         styles.InsertValue(0, 2, 0);
  86 }
  87
  88 template <typename DISTANCE, typename STYLE>
  89 DISTANCE RunStyles<DISTANCE, STYLE>::Length() const noexcept {
  90         return starts.PositionFromPartition(starts.Partitions());
  91 }
  92
  93 template <typename DISTANCE, typename STYLE>
  94 STYLE RunStyles<DISTANCE, STYLE>::ValueAt(DISTANCE position) const noexcept {
  95         return styles.ValueAt(starts.PartitionFromPosition(position));
  96 }
  97
  98 template <typename DISTANCE, typename STYLE>
  99 DISTANCE RunStyles<DISTANCE, STYLE>::FindNextChange(DISTANCE position, DISTANCE end) const noexcept {
 100         const DISTANCE run = starts.PartitionFromPosition(position);
 101         if (run < starts.Partitions()) {
 102                 const DISTANCE runChange = starts.PositionFromPartition(run);
 103                 if (runChange > position)
 104                         return runChange;
 105                 const DISTANCE nextChange = starts.PositionFromPartition(run + 1);
 106                 if (nextChange > position) {
 107                         return nextChange;
 108                 } else if (position < end) {
 109                         return end;
 110                 } else {
 111                         return end + 1;
 112                 }
 113         } else {
 114                 return end + 1;
 115         }
 116 }
 117
 118 template <typename DISTANCE, typename STYLE>
 119 DISTANCE RunStyles<DISTANCE, STYLE>::StartRun(DISTANCE position) const noexcept {
 120         return starts.PositionFromPartition(starts.PartitionFromPosition(position));
 121 }
 122
 123 template <typename DISTANCE, typename STYLE>
 124 DISTANCE RunStyles<DISTANCE, STYLE>::EndRun(DISTANCE position) const noexcept {
 125         return starts.PositionFromPartition(starts.PartitionFromPosition(position) + 1);
 126 }
 127
 128 template <typename DISTANCE, typename STYLE>
 129 FillResult<DISTANCE> RunStyles<DISTANCE, STYLE>::FillRange(DISTANCE position, STYLE value, DISTANCE fillLength) {
 130         const FillResult<DISTANCE> resultNoChange{false, position, fillLength};
 131         if (fillLength <= 0) {
 132                 return resultNoChange;
 133         }
 134         DISTANCE end = position + fillLength;
 135         if (end > Length()) {
 136                 return resultNoChange;
 137         }
 138         DISTANCE runEnd = RunFromPosition(end);
 139         if (styles.ValueAt(runEnd) == value) {
 140                 // End already has value so trim range.
 141                 end = starts.PositionFromPartition(runEnd);
 142                 if (position >= end) {
 143                         // Whole range is already same as value so no action
 144                         return resultNoChange;
 145                 }
 146                 fillLength = end - position;
 147         } else {
 148                 runEnd = SplitRun(end);
 149         }
 150         DISTANCE runStart = RunFromPosition(position);
 151         if (styles.ValueAt(runStart) == value) {
 152                 // Start is in expected value so trim range.
 153                 runStart++;
 154                 position = starts.PositionFromPartition(runStart);
 155                 fillLength = end - position;
 156         } else {
 157                 if (starts.PositionFromPartition(runStart) < position) {
 158                         runStart = SplitRun(position);
 159                         runEnd++;
 160                 }
 161         }
 162         if (runStart < runEnd) {
 163                 const FillResult<DISTANCE> result{ true, position, fillLength };
 164                 styles.SetValueAt(runStart, value);
 165                 // Remove each old run over the range
 166                 for (DISTANCE run=runStart+1; run<runEnd; run++) {
 167                         RemoveRun(runStart+1);
 168                 }
 169                 runEnd = RunFromPosition(end);
 170                 RemoveRunIfSameAsPrevious(runEnd);
 171                 RemoveRunIfSameAsPrevious(runStart);
 172                 runEnd = RunFromPosition(end);
 173                 RemoveRunIfEmpty(runEnd);
 174                 return result;
 175         } else {
 176                 return resultNoChange;
 177         }
 178 }
 179
 180 template <typename DISTANCE, typename STYLE>
 181 void RunStyles<DISTANCE, STYLE>::SetValueAt(DISTANCE position, STYLE value) {
 182         FillRange(position, value, 1);
 183 }
 184
 185 template <typename DISTANCE, typename STYLE>
 186 void RunStyles<DISTANCE, STYLE>::InsertSpace(DISTANCE position, DISTANCE insertLength) {
 187         DISTANCE runStart = RunFromPosition(position);
 188         if (starts.PositionFromPartition(runStart) == position) {
 189                 STYLE runStyle = ValueAt(position);
 190                 // Inserting at start of run so make previous longer
 191                 if (runStart == 0) {
 192                         // Inserting at start of document so ensure 0
 193                         if (runStyle) {
 194                                 styles.SetValueAt(0, STYLE());
 195                                 starts.InsertPartition(1, 0);
 196                                 styles.InsertValue(1, 1, runStyle);
 197                                 starts.InsertText(0, insertLength);
 198                         } else {
 199                                 starts.InsertText(runStart, insertLength);
 200                         }
 201                 } else {
 202                         if (runStyle) {
 203                                 starts.InsertText(runStart-1, insertLength);
 204                         } else {
 205                                 // Insert at end of run so do not extend style
 206                                 starts.InsertText(runStart, insertLength);
 207                         }
 208                 }
 209         } else {
 210                 starts.InsertText(runStart, insertLength);
 211         }
 212 }
 213
 214 template <typename DISTANCE, typename STYLE>
 215 void RunStyles<DISTANCE, STYLE>::DeleteAll() {
 216         starts = Partitioning<DISTANCE>(8);
 217         styles = SplitVector<STYLE>();
 218         styles.InsertValue(0, 2, 0);
 219 }
 220
 221 template <typename DISTANCE, typename STYLE>
 222 void RunStyles<DISTANCE, STYLE>::DeleteRange(DISTANCE position, DISTANCE deleteLength) {
 223         DISTANCE end = position + deleteLength;
 224         DISTANCE runStart = RunFromPosition(position);
 225         DISTANCE runEnd = RunFromPosition(end);
 226         if (runStart == runEnd) {
 227                 // Deleting from inside one run
 228                 starts.InsertText(runStart, -deleteLength);
 229                 RemoveRunIfEmpty(runStart);
 230         } else {
 231                 runStart = SplitRun(position);
 232                 runEnd = SplitRun(end);
 233                 starts.InsertText(runStart, -deleteLength);
 234                 // Remove each old run over the range
 235                 for (DISTANCE run=runStart; run<runEnd; run++) {
 236                         RemoveRun(runStart);
 237                 }
 238                 RemoveRunIfEmpty(runStart);
 239                 RemoveRunIfSameAsPrevious(runStart);
 240         }
 241 }
 242
 243 template <typename DISTANCE, typename STYLE>
 244 DISTANCE RunStyles<DISTANCE, STYLE>::Runs() const noexcept {
 245         return starts.Partitions();
 246 }
 247
 248 template <typename DISTANCE, typename STYLE>
 249 bool RunStyles<DISTANCE, STYLE>::AllSame() const noexcept {
 250         for (DISTANCE run = 1; run < starts.Partitions(); run++) {
 251                 const DISTANCE runBefore = run - 1;
 252                 if (styles.ValueAt(run) != styles.ValueAt(runBefore))
 253                         return false;
 254         }
 255         return true;
 256 }
 257
 258 template <typename DISTANCE, typename STYLE>
 259 bool RunStyles<DISTANCE, STYLE>::AllSameAs(STYLE value) const noexcept {
 260         return AllSame() && (styles.ValueAt(0) == value);
 261 }
 262
 263 template <typename DISTANCE, typename STYLE>
 264 DISTANCE RunStyles<DISTANCE, STYLE>::Find(STYLE value, DISTANCE start) const noexcept {
 265         if (start < Length()) {
 266                 DISTANCE run = start ? RunFromPosition(start) : 0;
 267                 if (styles.ValueAt(run) == value)
 268                         return start;
 269                 run++;
 270                 while (run < starts.Partitions()) {
 271                         if (styles.ValueAt(run) == value)
 272                                 return starts.PositionFromPartition(run);
 273                         run++;
 274                 }
 275         }
 276         return -1;
 277 }
 278
 279 template <typename DISTANCE, typename STYLE>
 280 void RunStyles<DISTANCE, STYLE>::Check() const {
 281         if (Length() < 0) {
 282                 throw std::runtime_error("RunStyles: Length can not be negative.");
 283         }
 284         if (starts.Partitions() < 1) {
 285                 throw std::runtime_error("RunStyles: Must always have 1 or more partitions.");
 286         }
 287         if (starts.Partitions() != styles.Length()-1) {
 288                 throw std::runtime_error("RunStyles: Partitions and styles different lengths.");
 289         }
 290         DISTANCE start=0;
 291         while (start < Length()) {
 292                 const DISTANCE end = EndRun(start);
 293                 if (start >= end) {
 294                         throw std::runtime_error("RunStyles: Partition is 0 length.");
 295                 }
 296                 start = end;
 297         }
 298         if (styles.ValueAt(styles.Length()-1) != 0) {
 299                 throw std::runtime_error("RunStyles: Unused style at end changed.");
 300         }
 301         for (ptrdiff_t j=1; j<styles.Length()-1; j++) {
 302                 if (styles.ValueAt(j) == styles.ValueAt(j-1)) {
 303                         throw std::runtime_error("RunStyles: Style of a partition same as previous.");
 304                 }
 305         }
 306 }
 307
 308 template class Scintilla::Internal::RunStyles<int, int>;
 309 template class Scintilla::Internal::RunStyles<int, char>;
 310 #if (PTRDIFF_MAX != INT_MAX) || defined(__HAIKU__)
 311 template class Scintilla::Internal::RunStyles<ptrdiff_t, int>;
 312 template class Scintilla::Internal::RunStyles<ptrdiff_t, char>;
 313 #endif