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 <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>
RemoveRun(DISTANCE run)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>
RemoveRunIfEmpty(DISTANCE run)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>
RemoveRunIfSameAsPrevious(DISTANCE run)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>
RunStyles()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>
~RunStyles()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>
ValueAt(DISTANCE position) const97 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>
FillRange(DISTANCE position,STYLE value,DISTANCE fillLength)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>
SetValueAt(DISTANCE position,STYLE value)184 void RunStyles<DISTANCE, STYLE>::SetValueAt(DISTANCE position, STYLE value) {
185 FillRange(position, value, 1);
186 }
187
188 template <typename DISTANCE, typename STYLE>
InsertSpace(DISTANCE position,DISTANCE insertLength)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>
DeleteAll()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>
DeleteRange(DISTANCE position,DISTANCE deleteLength)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>
AllSame() const252 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>
AllSameAs(STYLE value) const261 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>
Check() const282 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