1 /** @file RunStyles.cxx 2 ** Data structure used to store sparse styles. 3 **/ 4 // Copyright 1998-2007 by Neil Hodgson <[email protected]> 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 <algorithm> 19 #include <memory> 20 21 #include "Platform.h" 22 23 #include "Scintilla.h" 24 #include "Position.h" 25 #include "SplitVector.h" 26 #include "Partitioning.h" 27 #include "RunStyles.h" 28 29 using namespace Scintilla; 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 if (styles->ValueAt(run-1) == styles->ValueAt(run)) { 75 RemoveRun(run); 76 } 77 } 78 } 79 80 template <typename DISTANCE, typename STYLE> 81 RunStyles<DISTANCE, STYLE>::RunStyles() { 82 starts = std::make_unique<Partitioning<DISTANCE>>(8); 83 styles = std::make_unique<SplitVector<STYLE>>(); 84 styles->InsertValue(0, 2, 0); 85 } 86 87 template <typename DISTANCE, typename STYLE> 88 RunStyles<DISTANCE, STYLE>::~RunStyles() { 89 } 90 91 template <typename DISTANCE, typename STYLE> 92 DISTANCE RunStyles<DISTANCE, STYLE>::Length() const noexcept { 93 return starts->PositionFromPartition(starts->Partitions()); 94 } 95 96 template <typename DISTANCE, typename STYLE> 97 STYLE RunStyles<DISTANCE, STYLE>::ValueAt(DISTANCE position) const noexcept { 98 return styles->ValueAt(starts->PartitionFromPosition(position)); 99 } 100 101 template <typename DISTANCE, typename STYLE> 102 DISTANCE RunStyles<DISTANCE, STYLE>::FindNextChange(DISTANCE position, DISTANCE end) const noexcept { 103 const DISTANCE run = starts->PartitionFromPosition(position); 104 if (run < starts->Partitions()) { 105 const DISTANCE runChange = starts->PositionFromPartition(run); 106 if (runChange > position) 107 return runChange; 108 const DISTANCE nextChange = starts->PositionFromPartition(run + 1); 109 if (nextChange > position) { 110 return nextChange; 111 } else if (position < end) { 112 return end; 113 } else { 114 return end + 1; 115 } 116 } else { 117 return end + 1; 118 } 119 } 120 121 template <typename DISTANCE, typename STYLE> 122 DISTANCE RunStyles<DISTANCE, STYLE>::StartRun(DISTANCE position) const noexcept { 123 return starts->PositionFromPartition(starts->PartitionFromPosition(position)); 124 } 125 126 template <typename DISTANCE, typename STYLE> 127 DISTANCE RunStyles<DISTANCE, STYLE>::EndRun(DISTANCE position) const noexcept { 128 return starts->PositionFromPartition(starts->PartitionFromPosition(position) + 1); 129 } 130 131 template <typename DISTANCE, typename STYLE> 132 FillResult<DISTANCE> RunStyles<DISTANCE, STYLE>::FillRange(DISTANCE position, STYLE value, DISTANCE fillLength) { 133 const FillResult<DISTANCE> resultNoChange{false, position, fillLength}; 134 if (fillLength <= 0) { 135 return resultNoChange; 136 } 137 DISTANCE end = position + fillLength; 138 if (end > Length()) { 139 return resultNoChange; 140 } 141 DISTANCE runEnd = RunFromPosition(end); 142 if (styles->ValueAt(runEnd) == value) { 143 // End already has value so trim range. 144 end = starts->PositionFromPartition(runEnd); 145 if (position >= end) { 146 // Whole range is already same as value so no action 147 return resultNoChange; 148 } 149 fillLength = end - position; 150 } else { 151 runEnd = SplitRun(end); 152 } 153 DISTANCE runStart = RunFromPosition(position); 154 if (styles->ValueAt(runStart) == value) { 155 // Start is in expected value so trim range. 156 runStart++; 157 position = starts->PositionFromPartition(runStart); 158 fillLength = end - position; 159 } else { 160 if (starts->PositionFromPartition(runStart) < position) { 161 runStart = SplitRun(position); 162 runEnd++; 163 } 164 } 165 if (runStart < runEnd) { 166 const FillResult<DISTANCE> result{ true, position, fillLength }; 167 styles->SetValueAt(runStart, value); 168 // Remove each old run over the range 169 for (DISTANCE run=runStart+1; run<runEnd; run++) { 170 RemoveRun(runStart+1); 171 } 172 runEnd = RunFromPosition(end); 173 RemoveRunIfSameAsPrevious(runEnd); 174 RemoveRunIfSameAsPrevious(runStart); 175 runEnd = RunFromPosition(end); 176 RemoveRunIfEmpty(runEnd); 177 return result; 178 } else { 179 return resultNoChange; 180 } 181 } 182 183 template <typename DISTANCE, typename STYLE> 184 void RunStyles<DISTANCE, STYLE>::SetValueAt(DISTANCE position, STYLE value) { 185 FillRange(position, value, 1); 186 } 187 188 template <typename DISTANCE, typename STYLE> 189 void RunStyles<DISTANCE, STYLE>::InsertSpace(DISTANCE position, DISTANCE insertLength) { 190 DISTANCE runStart = RunFromPosition(position); 191 if (starts->PositionFromPartition(runStart) == position) { 192 STYLE runStyle = ValueAt(position); 193 // Inserting at start of run so make previous longer 194 if (runStart == 0) { 195 // Inserting at start of document so ensure 0 196 if (runStyle) { 197 styles->SetValueAt(0, STYLE()); 198 starts->InsertPartition(1, 0); 199 styles->InsertValue(1, 1, runStyle); 200 starts->InsertText(0, insertLength); 201 } else { 202 starts->InsertText(runStart, insertLength); 203 } 204 } else { 205 if (runStyle) { 206 starts->InsertText(runStart-1, insertLength); 207 } else { 208 // Insert at end of run so do not extend style 209 starts->InsertText(runStart, insertLength); 210 } 211 } 212 } else { 213 starts->InsertText(runStart, insertLength); 214 } 215 } 216 217 template <typename DISTANCE, typename STYLE> 218 void RunStyles<DISTANCE, STYLE>::DeleteAll() { 219 starts = std::make_unique<Partitioning<DISTANCE>>(8); 220 styles = std::make_unique<SplitVector<STYLE>>(); 221 styles->InsertValue(0, 2, 0); 222 } 223 224 template <typename DISTANCE, typename STYLE> 225 void RunStyles<DISTANCE, STYLE>::DeleteRange(DISTANCE position, DISTANCE deleteLength) { 226 DISTANCE end = position + deleteLength; 227 DISTANCE runStart = RunFromPosition(position); 228 DISTANCE runEnd = RunFromPosition(end); 229 if (runStart == runEnd) { 230 // Deleting from inside one run 231 starts->InsertText(runStart, -deleteLength); 232 RemoveRunIfEmpty(runStart); 233 } else { 234 runStart = SplitRun(position); 235 runEnd = SplitRun(end); 236 starts->InsertText(runStart, -deleteLength); 237 // Remove each old run over the range 238 for (DISTANCE run=runStart; run<runEnd; run++) { 239 RemoveRun(runStart); 240 } 241 RemoveRunIfEmpty(runStart); 242 RemoveRunIfSameAsPrevious(runStart); 243 } 244 } 245 246 template <typename DISTANCE, typename STYLE> 247 DISTANCE RunStyles<DISTANCE, STYLE>::Runs() const noexcept { 248 return starts->Partitions(); 249 } 250 251 template <typename DISTANCE, typename STYLE> 252 bool RunStyles<DISTANCE, STYLE>::AllSame() const noexcept { 253 for (DISTANCE run = 1; run < starts->Partitions(); run++) { 254 if (styles->ValueAt(run) != styles->ValueAt(run - 1)) 255 return false; 256 } 257 return true; 258 } 259 260 template <typename DISTANCE, typename STYLE> 261 bool RunStyles<DISTANCE, STYLE>::AllSameAs(STYLE value) const noexcept { 262 return AllSame() && (styles->ValueAt(0) == value); 263 } 264 265 template <typename DISTANCE, typename STYLE> 266 DISTANCE RunStyles<DISTANCE, STYLE>::Find(STYLE value, DISTANCE start) const noexcept { 267 if (start < Length()) { 268 DISTANCE run = start ? RunFromPosition(start) : 0; 269 if (styles->ValueAt(run) == value) 270 return start; 271 run++; 272 while (run < starts->Partitions()) { 273 if (styles->ValueAt(run) == value) 274 return starts->PositionFromPartition(run); 275 run++; 276 } 277 } 278 return -1; 279 } 280 281 template <typename DISTANCE, typename STYLE> 282 void RunStyles<DISTANCE, STYLE>::Check() const { 283 if (Length() < 0) { 284 throw std::runtime_error("RunStyles: Length can not be negative."); 285 } 286 if (starts->Partitions() < 1) { 287 throw std::runtime_error("RunStyles: Must always have 1 or more partitions."); 288 } 289 if (starts->Partitions() != styles->Length()-1) { 290 throw std::runtime_error("RunStyles: Partitions and styles different lengths."); 291 } 292 DISTANCE start=0; 293 while (start < Length()) { 294 const DISTANCE end = EndRun(start); 295 if (start >= end) { 296 throw std::runtime_error("RunStyles: Partition is 0 length."); 297 } 298 start = end; 299 } 300 if (styles->ValueAt(styles->Length()-1) != 0) { 301 throw std::runtime_error("RunStyles: Unused style at end changed."); 302 } 303 for (ptrdiff_t j=1; j<styles->Length()-1; j++) { 304 if (styles->ValueAt(j) == styles->ValueAt(j-1)) { 305 throw std::runtime_error("RunStyles: Style of a partition same as previous."); 306 } 307 } 308 } 309 310 template class Scintilla::RunStyles<int, int>; 311 template class Scintilla::RunStyles<int, char>; 312 #if (PTRDIFF_MAX != INT_MAX) || PLAT_HAIKU 313 template class Scintilla::RunStyles<ptrdiff_t, int>; 314 template class Scintilla::RunStyles<ptrdiff_t, char>; 315 #endif 316