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 | 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::Internal::RunStyles<int, int>; |
311 | template class Scintilla::Internal::RunStyles<int, char>; |
312 | #if (PTRDIFF_MAX != INT_MAX) || PLAT_HAIKU |
313 | template class Scintilla::Internal::RunStyles<ptrdiff_t, int>; |
314 | template class Scintilla::Internal::RunStyles<ptrdiff_t, char>; |
315 | #endif |
316 | |