1 // Copyright 2019 Google LLC.
2 // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
3
4 #include "modules/skplaintexteditor/include/editor.h"
5
6 #include "include/core/SkCanvas.h"
7 #include "include/core/SkExecutor.h"
8 #include "include/core/SkPath.h"
9 #include "src/utils/SkUTF.h"
10
11 #include "modules/skplaintexteditor/src/shape.h"
12
13 #include <algorithm>
14
15 using namespace SkPlainTextEditor;
16
offset(SkRect r,SkIPoint p)17 static inline SkRect offset(SkRect r, SkIPoint p) {
18 return r.makeOffset((float)p.x(), (float)p.y());
19 }
20
21 static constexpr SkRect kUnsetRect{-FLT_MAX, -FLT_MAX, -FLT_MAX, -FLT_MAX};
22
valid_utf8(const char * ptr,size_t size)23 static bool valid_utf8(const char* ptr, size_t size) { return SkUTF::CountUTF8(ptr, size) >= 0; }
24
25 // Kind of like Python's readlines(), but without any allocation.
26 // Calls f() on each line.
27 // F is [](const char*, size_t) -> void
28 template <typename F>
readlines(const void * data,size_t size,F f)29 static void readlines(const void* data, size_t size, F f) {
30 const char* start = (const char*)data;
31 const char* end = start + size;
32 const char* ptr = start;
33 while (ptr < end) {
34 while (*ptr++ != '\n' && ptr < end) {}
35 size_t len = ptr - start;
36 SkASSERT(len > 0);
37 f(start, len);
38 start = ptr;
39 }
40 }
41
remove_newline(const char * str,size_t len)42 static StringSlice remove_newline(const char* str, size_t len) {
43 return SkASSERT((str != nullptr) || (len == 0)),
44 StringSlice(str, (len > 0 && str[len - 1] == '\n') ? len - 1 : len);
45 }
46
markDirty(TextLine * line)47 void Editor::markDirty(TextLine* line) {
48 line->fBlob = nullptr;
49 line->fShaped = false;
50 line->fWordBoundaries = std::vector<bool>();
51 }
52
setFont(SkFont font)53 void Editor::setFont(SkFont font) {
54 if (font != fFont) {
55 fFont = std::move(font);
56 fNeedsReshape = true;
57 for (auto& l : fLines) { this->markDirty(&l); }
58 }
59 }
60
setWidth(int w)61 void Editor::setWidth(int w) {
62 if (fWidth != w) {
63 fWidth = w;
64 fNeedsReshape = true;
65 for (auto& l : fLines) { this->markDirty(&l); }
66 }
67 }
to_point(SkIPoint p)68 static SkPoint to_point(SkIPoint p) { return {(float)p.x(), (float)p.y()}; }
69
getPosition(SkIPoint xy)70 Editor::TextPosition Editor::getPosition(SkIPoint xy) {
71 Editor::TextPosition approximatePosition;
72 this->reshapeAll();
73 for (size_t j = 0; j < fLines.size(); ++j) {
74 const TextLine& line = fLines[j];
75 SkIRect lineRect = {0,
76 line.fOrigin.y(),
77 fWidth,
78 j + 1 < fLines.size() ? fLines[j + 1].fOrigin.y() : INT_MAX};
79 if (const SkTextBlob* b = line.fBlob.get()) {
80 SkIRect r = b->bounds().roundOut();
81 r.offset(line.fOrigin);
82 lineRect.join(r);
83 }
84 if (!lineRect.contains(xy.x(), xy.y())) {
85 continue;
86 }
87 SkPoint pt = to_point(xy - line.fOrigin);
88 const std::vector<SkRect>& pos = line.fCursorPos;
89 for (size_t i = 0; i < pos.size(); ++i) {
90 if (pos[i] != kUnsetRect && pos[i].contains(pt.x(), pt.y())) {
91 return Editor::TextPosition{i, j};
92 }
93 }
94 approximatePosition = {xy.x() <= line.fOrigin.x() ? 0 : line.fText.size(), j};
95 }
96 return approximatePosition;
97 }
98
is_utf8_continuation(char v)99 static inline bool is_utf8_continuation(char v) {
100 return ((unsigned char)v & 0b11000000) ==
101 0b10000000;
102 }
103
next_utf8(const char * p,const char * end)104 static const char* next_utf8(const char* p, const char* end) {
105 if (p < end) {
106 do {
107 ++p;
108 } while (p < end && is_utf8_continuation(*p));
109 }
110 return p;
111 }
112
align_utf8(const char * p,const char * begin)113 static const char* align_utf8(const char* p, const char* begin) {
114 while (p > begin && is_utf8_continuation(*p)) {
115 --p;
116 }
117 return p;
118 }
119
prev_utf8(const char * p,const char * begin)120 static const char* prev_utf8(const char* p, const char* begin) {
121 return p > begin ? align_utf8(p - 1, begin) : begin;
122 }
123
getLocation(Editor::TextPosition cursor)124 SkRect Editor::getLocation(Editor::TextPosition cursor) {
125 this->reshapeAll();
126 cursor = this->move(Editor::Movement::kNowhere, cursor);
127 if (fLines.size() > 0) {
128 const TextLine& cLine = fLines[cursor.fParagraphIndex];
129 SkRect pos = {0, 0, 0, 0};
130 if (cursor.fTextByteIndex < cLine.fCursorPos.size()) {
131 pos = cLine.fCursorPos[cursor.fTextByteIndex];
132 }
133 pos.fRight = pos.fLeft + 1;
134 pos.fLeft -= 1;
135 return offset(pos, cLine.fOrigin);
136 }
137 return SkRect{0, 0, 0, 0};
138 }
139
count_char(const StringSlice & string,char value)140 static size_t count_char(const StringSlice& string, char value) {
141 size_t count = 0;
142 for (char c : string) { if (c == value) { ++count; } }
143 return count;
144 }
145
insert(TextPosition pos,const char * utf8Text,size_t byteLen)146 Editor::TextPosition Editor::insert(TextPosition pos, const char* utf8Text, size_t byteLen) {
147 if (!valid_utf8(utf8Text, byteLen) || 0 == byteLen) {
148 return pos;
149 }
150 pos = this->move(Editor::Movement::kNowhere, pos);
151 fNeedsReshape = true;
152 if (pos.fParagraphIndex < fLines.size()) {
153 fLines[pos.fParagraphIndex].fText.insert(pos.fTextByteIndex, utf8Text, byteLen);
154 this->markDirty(&fLines[pos.fParagraphIndex]);
155 } else {
156 SkASSERT(pos.fParagraphIndex == fLines.size());
157 SkASSERT(pos.fTextByteIndex == 0);
158 fLines.push_back(Editor::TextLine(StringSlice(utf8Text, byteLen)));
159 }
160 pos = Editor::TextPosition{pos.fTextByteIndex + byteLen, pos.fParagraphIndex};
161 size_t newlinecount = count_char(fLines[pos.fParagraphIndex].fText, '\n');
162 if (newlinecount > 0) {
163 StringSlice src = std::move(fLines[pos.fParagraphIndex].fText);
164 std::vector<TextLine>::const_iterator next = fLines.begin() + pos.fParagraphIndex + 1;
165 fLines.insert(next, newlinecount, TextLine());
166 TextLine* line = &fLines[pos.fParagraphIndex];
167 readlines(src.begin(), src.size(), [&line](const char* str, size_t l) {
168 (line++)->fText = remove_newline(str, l);
169 });
170 }
171 return pos;
172 }
173
remove(TextPosition pos1,TextPosition pos2)174 Editor::TextPosition Editor::remove(TextPosition pos1, TextPosition pos2) {
175 pos1 = this->move(Editor::Movement::kNowhere, pos1);
176 pos2 = this->move(Editor::Movement::kNowhere, pos2);
177 auto cmp = [](const Editor::TextPosition& u, const Editor::TextPosition& v) { return u < v; };
178 Editor::TextPosition start = std::min(pos1, pos2, cmp);
179 Editor::TextPosition end = std::max(pos1, pos2, cmp);
180 if (start == end || start.fParagraphIndex == fLines.size()) {
181 return start;
182 }
183 fNeedsReshape = true;
184 if (start.fParagraphIndex == end.fParagraphIndex) {
185 SkASSERT(end.fTextByteIndex > start.fTextByteIndex);
186 fLines[start.fParagraphIndex].fText.remove(
187 start.fTextByteIndex, end.fTextByteIndex - start.fTextByteIndex);
188 this->markDirty(&fLines[start.fParagraphIndex]);
189 } else {
190 SkASSERT(end.fParagraphIndex < fLines.size());
191 auto& line = fLines[start.fParagraphIndex];
192 line.fText.remove(start.fTextByteIndex,
193 line.fText.size() - start.fTextByteIndex);
194 line.fText.insert(start.fTextByteIndex,
195 fLines[end.fParagraphIndex].fText.begin() + end.fTextByteIndex,
196 fLines[end.fParagraphIndex].fText.size() - end.fTextByteIndex);
197 this->markDirty(&line);
198 fLines.erase(fLines.begin() + start.fParagraphIndex + 1,
199 fLines.begin() + end.fParagraphIndex + 1);
200 }
201 return start;
202 }
203
append(char ** dst,size_t * count,const char * src,size_t n)204 static void append(char** dst, size_t* count, const char* src, size_t n) {
205 if (*dst) {
206 ::memcpy(*dst, src, n);
207 *dst += n;
208 }
209 *count += n;
210 }
211
copy(TextPosition pos1,TextPosition pos2,char * dst) const212 size_t Editor::copy(TextPosition pos1, TextPosition pos2, char* dst) const {
213 size_t size = 0;
214 pos1 = this->move(Editor::Movement::kNowhere, pos1);
215 pos2 = this->move(Editor::Movement::kNowhere, pos2);
216 auto cmp = [](const Editor::TextPosition& u, const Editor::TextPosition& v) { return u < v; };
217 Editor::TextPosition start = std::min(pos1, pos2, cmp);
218 Editor::TextPosition end = std::max(pos1, pos2, cmp);
219 if (start == end || start.fParagraphIndex == fLines.size()) {
220 return size;
221 }
222 if (start.fParagraphIndex == end.fParagraphIndex) {
223 SkASSERT(end.fTextByteIndex > start.fTextByteIndex);
224 auto& str = fLines[start.fParagraphIndex].fText;
225 append(&dst, &size, str.begin() + start.fTextByteIndex,
226 end.fTextByteIndex - start.fTextByteIndex);
227 return size;
228 }
229 SkASSERT(end.fParagraphIndex < fLines.size());
230 const std::vector<TextLine>::const_iterator firstP = fLines.begin() + start.fParagraphIndex;
231 const std::vector<TextLine>::const_iterator lastP = fLines.begin() + end.fParagraphIndex;
232 const auto& first = firstP->fText;
233 const auto& last = lastP->fText;
234
235 append(&dst, &size, first.begin() + start.fTextByteIndex, first.size() - start.fTextByteIndex);
236 for (auto line = firstP + 1; line < lastP; ++line) {
237 append(&dst, &size, "\n", 1);
238 append(&dst, &size, line->fText.begin(), line->fText.size());
239 }
240 append(&dst, &size, "\n", 1);
241 append(&dst, &size, last.begin(), end.fTextByteIndex);
242 return size;
243 }
244
begin(const StringSlice & s)245 static inline const char* begin(const StringSlice& s) { return s.begin(); }
246
end(const StringSlice & s)247 static inline const char* end(const StringSlice& s) { return s.end(); }
248
align_column(const StringSlice & str,size_t p)249 static size_t align_column(const StringSlice& str, size_t p) {
250 if (p >= str.size()) {
251 return str.size();
252 }
253 return align_utf8(begin(str) + p, begin(str)) - begin(str);
254 }
255
256 // returns smallest i such that list[i] > value. value > list[i-1]
257 // Use a binary search since list is monotonic
258 template <typename T>
find_first_larger(const std::vector<T> & list,T value)259 static size_t find_first_larger(const std::vector<T>& list, T value) {
260 return (size_t)(std::upper_bound(list.begin(), list.end(), value) - list.begin());
261 }
262
find_closest_x(const std::vector<SkRect> & bounds,float x,size_t b,size_t e)263 static size_t find_closest_x(const std::vector<SkRect>& bounds, float x, size_t b, size_t e) {
264 if (b >= e) {
265 return b;
266 }
267 SkASSERT(e <= bounds.size());
268 size_t best_index = b;
269 float best_diff = ::fabsf(bounds[best_index].x() - x);
270 for (size_t i = b + 1; i < e; ++i) {
271 float d = ::fabsf(bounds[i].x() - x);
272 if (d < best_diff) {
273 best_diff = d;
274 best_index = i;
275 }
276 }
277 return best_index;
278 }
279
move(Editor::Movement move,Editor::TextPosition pos) const280 Editor::TextPosition Editor::move(Editor::Movement move, Editor::TextPosition pos) const {
281 if (fLines.empty()) {
282 return {0, 0};
283 }
284 // First thing: fix possible bad input values.
285 if (pos.fParagraphIndex >= fLines.size()) {
286 pos.fParagraphIndex = fLines.size() - 1;
287 pos.fTextByteIndex = fLines[pos.fParagraphIndex].fText.size();
288 } else {
289 pos.fTextByteIndex = align_column(fLines[pos.fParagraphIndex].fText, pos.fTextByteIndex);
290 }
291
292 SkASSERT(pos.fParagraphIndex < fLines.size());
293 SkASSERT(pos.fTextByteIndex <= fLines[pos.fParagraphIndex].fText.size());
294
295 SkASSERT(pos.fTextByteIndex == fLines[pos.fParagraphIndex].fText.size() ||
296 !is_utf8_continuation(fLines[pos.fParagraphIndex].fText.begin()[pos.fTextByteIndex]));
297
298 switch (move) {
299 case Editor::Movement::kNowhere:
300 break;
301 case Editor::Movement::kLeft:
302 if (0 == pos.fTextByteIndex) {
303 if (pos.fParagraphIndex > 0) {
304 --pos.fParagraphIndex;
305 pos.fTextByteIndex = fLines[pos.fParagraphIndex].fText.size();
306 }
307 } else {
308 const auto& str = fLines[pos.fParagraphIndex].fText;
309 pos.fTextByteIndex =
310 prev_utf8(begin(str) + pos.fTextByteIndex, begin(str)) - begin(str);
311 }
312 break;
313 case Editor::Movement::kRight:
314 if (fLines[pos.fParagraphIndex].fText.size() == pos.fTextByteIndex) {
315 if (pos.fParagraphIndex + 1 < fLines.size()) {
316 ++pos.fParagraphIndex;
317 pos.fTextByteIndex = 0;
318 }
319 } else {
320 const auto& str = fLines[pos.fParagraphIndex].fText;
321 pos.fTextByteIndex =
322 next_utf8(begin(str) + pos.fTextByteIndex, end(str)) - begin(str);
323 }
324 break;
325 case Editor::Movement::kHome:
326 {
327 const std::vector<size_t>& list = fLines[pos.fParagraphIndex].fLineEndOffsets;
328 size_t f = find_first_larger(list, pos.fTextByteIndex);
329 pos.fTextByteIndex = f > 0 ? list[f - 1] : 0;
330 }
331 break;
332 case Editor::Movement::kEnd:
333 {
334 const std::vector<size_t>& list = fLines[pos.fParagraphIndex].fLineEndOffsets;
335 size_t f = find_first_larger(list, pos.fTextByteIndex);
336 if (f < list.size()) {
337 pos.fTextByteIndex = list[f] > 0 ? list[f] - 1 : 0;
338 } else {
339 pos.fTextByteIndex = fLines[pos.fParagraphIndex].fText.size();
340 }
341 }
342 break;
343 case Editor::Movement::kUp:
344 {
345 SkASSERT(pos.fTextByteIndex < fLines[pos.fParagraphIndex].fCursorPos.size());
346 float x = fLines[pos.fParagraphIndex].fCursorPos[pos.fTextByteIndex].left();
347 const std::vector<size_t>& list = fLines[pos.fParagraphIndex].fLineEndOffsets;
348 size_t f = find_first_larger(list, pos.fTextByteIndex);
349 // list[f] > value. value > list[f-1]
350 if (f > 0) {
351 // not the first line in paragraph.
352 pos.fTextByteIndex = find_closest_x(fLines[pos.fParagraphIndex].fCursorPos, x,
353 (f == 1) ? 0 : list[f - 2],
354 list[f - 1]);
355 } else if (pos.fParagraphIndex > 0) {
356 --pos.fParagraphIndex;
357 const auto& newLine = fLines[pos.fParagraphIndex];
358 size_t r = newLine.fLineEndOffsets.size();
359 if (r > 0) {
360 pos.fTextByteIndex = find_closest_x(newLine.fCursorPos, x,
361 newLine.fLineEndOffsets[r - 1],
362 newLine.fCursorPos.size());
363 } else {
364 pos.fTextByteIndex = find_closest_x(newLine.fCursorPos, x, 0,
365 newLine.fCursorPos.size());
366 }
367 }
368 pos.fTextByteIndex =
369 align_column(fLines[pos.fParagraphIndex].fText, pos.fTextByteIndex);
370 }
371 break;
372 case Editor::Movement::kDown:
373 {
374 const std::vector<size_t>& list = fLines[pos.fParagraphIndex].fLineEndOffsets;
375 float x = fLines[pos.fParagraphIndex].fCursorPos[pos.fTextByteIndex].left();
376
377 size_t f = find_first_larger(list, pos.fTextByteIndex);
378 if (f < list.size()) {
379 const auto& bounds = fLines[pos.fParagraphIndex].fCursorPos;
380 pos.fTextByteIndex = find_closest_x(bounds, x, list[f],
381 f + 1 < list.size() ? list[f + 1]
382 : bounds.size());
383 } else if (pos.fParagraphIndex + 1 < fLines.size()) {
384 ++pos.fParagraphIndex;
385 const auto& bounds = fLines[pos.fParagraphIndex].fCursorPos;
386 const std::vector<size_t>& l2 = fLines[pos.fParagraphIndex].fLineEndOffsets;
387 pos.fTextByteIndex = find_closest_x(bounds, x, 0,
388 l2.size() > 0 ? l2[0] : bounds.size());
389 } else {
390 pos.fTextByteIndex = fLines[pos.fParagraphIndex].fText.size();
391 }
392 pos.fTextByteIndex =
393 align_column(fLines[pos.fParagraphIndex].fText, pos.fTextByteIndex);
394 }
395 break;
396 case Editor::Movement::kWordLeft:
397 {
398 if (pos.fTextByteIndex == 0) {
399 pos = this->move(Editor::Movement::kLeft, pos);
400 break;
401 }
402 const std::vector<bool>& words = fLines[pos.fParagraphIndex].fWordBoundaries;
403 SkASSERT(words.size() == fLines[pos.fParagraphIndex].fText.size());
404 do {
405 --pos.fTextByteIndex;
406 } while (pos.fTextByteIndex > 0 && !words[pos.fTextByteIndex]);
407 }
408 break;
409 case Editor::Movement::kWordRight:
410 {
411 const StringSlice& text = fLines[pos.fParagraphIndex].fText;
412 if (pos.fTextByteIndex == text.size()) {
413 pos = this->move(Editor::Movement::kRight, pos);
414 break;
415 }
416 const std::vector<bool>& words = fLines[pos.fParagraphIndex].fWordBoundaries;
417 SkASSERT(words.size() == text.size());
418 do {
419 ++pos.fTextByteIndex;
420 } while (pos.fTextByteIndex < text.size() && !words[pos.fTextByteIndex]);
421 }
422 break;
423
424 }
425 return pos;
426 }
427
paint(SkCanvas * c,PaintOpts options)428 void Editor::paint(SkCanvas* c, PaintOpts options) {
429 this->reshapeAll();
430 if (!c) {
431 return;
432 }
433
434 c->drawPaint(SkPaint(options.fBackgroundColor));
435
436 SkPaint selection = SkPaint(options.fSelectionColor);
437 auto cmp = [](const Editor::TextPosition& u, const Editor::TextPosition& v) { return u < v; };
438 for (TextPosition pos = std::min(options.fSelectionBegin, options.fSelectionEnd, cmp),
439 end = std::max(options.fSelectionBegin, options.fSelectionEnd, cmp);
440 pos < end;
441 pos = this->move(Editor::Movement::kRight, pos))
442 {
443 SkASSERT(pos.fParagraphIndex < fLines.size());
444 const TextLine& l = fLines[pos.fParagraphIndex];
445 c->drawRect(offset(l.fCursorPos[pos.fTextByteIndex], l.fOrigin), selection);
446 }
447
448 if (fLines.size() > 0) {
449 c->drawRect(Editor::getLocation(options.fCursor), SkPaint(options.fCursorColor));
450 }
451
452 SkPaint foreground = SkPaint(options.fForegroundColor);
453 for (const TextLine& line : fLines) {
454 if (line.fBlob) {
455 c->drawTextBlob(line.fBlob.get(), line.fOrigin.x(), line.fOrigin.y(), foreground);
456 }
457 }
458 }
459
reshapeAll()460 void Editor::reshapeAll() {
461 if (fNeedsReshape) {
462 if (fLines.empty()) {
463 fLines.push_back(TextLine());
464 }
465 float shape_width = (float)(fWidth);
466 #ifdef SK_EDITOR_GO_FAST
467 SkSemaphore semaphore;
468 std::unique_ptr<SkExecutor> executor = SkExecutor::MakeFIFOThreadPool(100);
469 int jobCount = 0;
470 for (TextLine& line : fLines) {
471 if (!line.fShaped) {
472 executor->add([&]() {
473 ShapeResult result = Shape(line.fText.begin(), line.fText.size(),
474 fFont, fLocale, shape_width);
475 line.fBlob = std::move(result.blob);
476 line.fLineEndOffsets = std::move(result.lineBreakOffsets);
477 line.fCursorPos = std::move(result.glyphBounds);
478 line.fWordBoundaries = std::move(result.wordBreaks);
479 line.fHeight = result.verticalAdvance;
480 line.fShaped = true;
481 semaphore.signal();
482 }
483 ++jobCount;
484 });
485 }
486 while (jobCount-- > 0) { semaphore.wait(); }
487 #else
488 int i = 0;
489 for (TextLine& line : fLines) {
490 if (!line.fShaped) {
491 ShapeResult result = Shape(line.fText.begin(), line.fText.size(),
492 fFont, fLocale, shape_width);
493 line.fBlob = std::move(result.blob);
494 line.fLineEndOffsets = std::move(result.lineBreakOffsets);
495 line.fCursorPos = std::move(result.glyphBounds);
496 line.fWordBoundaries = std::move(result.wordBreaks);
497 line.fHeight = result.verticalAdvance;
498 line.fShaped = true;
499 }
500 ++i;
501 }
502 #endif
503 int y = 0;
504 for (TextLine& line : fLines) {
505 line.fOrigin = {0, y};
506 y += line.fHeight;
507 }
508 fHeight = y;
509 fNeedsReshape = false;
510 }
511 }
512
513