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