1 // Copyright 2019 Google LLC.
2 #include <memory>
3
4 #include "modules/skparagraph/include/FontArguments.h"
5 #include "modules/skparagraph/include/ParagraphCache.h"
6 #include "modules/skparagraph/src/ParagraphImpl.h"
7
8 namespace skia {
9 namespace textlayout {
10
11 namespace {
relax(SkScalar a)12 SkScalar relax(SkScalar a) {
13 // This rounding is done to match Flutter tests. Must be removed..
14 if (SkScalarIsFinite(a)) {
15 auto threshold = SkIntToScalar(1 << 12);
16 return SkScalarRoundToScalar(a * threshold)/threshold;
17 } else {
18 return a;
19 }
20 }
21
exactlyEqual(SkScalar x,SkScalar y)22 bool exactlyEqual(SkScalar x, SkScalar y) {
23 return x == y || (x != x && y != y);
24 }
25 } // namespace
26
27 class ParagraphCacheKey {
28 public:
ParagraphCacheKey(const ParagraphImpl * paragraph)29 ParagraphCacheKey(const ParagraphImpl* paragraph)
30 : fText(paragraph->fText.c_str(), paragraph->fText.size())
31 , fPlaceholders(paragraph->fPlaceholders)
32 , fTextStyles(paragraph->fTextStyles)
33 , fParagraphStyle(paragraph->paragraphStyle()) {
34 fHash = computeHash();
35 }
36
37 ParagraphCacheKey(const ParagraphCacheKey& other) = default;
38
ParagraphCacheKey(ParagraphCacheKey && other)39 ParagraphCacheKey(ParagraphCacheKey&& other)
40 : fText(std::move(other.fText))
41 , fPlaceholders(std::move(other.fPlaceholders))
42 , fTextStyles(std::move(other.fTextStyles))
43 , fParagraphStyle(std::move(other.fParagraphStyle))
44 , fHash(other.fHash) {
45 other.fHash = 0;
46 }
47
48 bool operator==(const ParagraphCacheKey& other) const;
49
hash() const50 uint32_t hash() const { return fHash; }
51
text() const52 const SkString& text() const { return fText; }
53
54 private:
55 static uint32_t mix(uint32_t hash, uint32_t data);
56 uint32_t computeHash() const;
57
58 SkString fText;
59 SkTArray<Placeholder, true> fPlaceholders;
60 SkTArray<Block, true> fTextStyles;
61 ParagraphStyle fParagraphStyle;
62 uint32_t fHash;
63 };
64
65 class ParagraphCacheValue {
66 public:
ParagraphCacheValue(ParagraphCacheKey && key,const ParagraphImpl * paragraph)67 ParagraphCacheValue(ParagraphCacheKey&& key, const ParagraphImpl* paragraph)
68 : fKey(std::move(key))
69 , fRuns(paragraph->fRuns)
70 , fClusters(paragraph->fClusters)
71 , fClustersIndexFromCodeUnit(paragraph->fClustersIndexFromCodeUnit)
72 , fCodeUnitProperties(paragraph->fCodeUnitProperties)
73 , fWords(paragraph->fWords)
74 , fBidiRegions(paragraph->fBidiRegions)
75 , fHasLineBreaks(paragraph->fHasLineBreaks)
76 , fHasWhitespacesInside(paragraph->fHasWhitespacesInside)
77 , fTrailingSpaces(paragraph->fTrailingSpaces) { }
78
79 // Input == key
80 ParagraphCacheKey fKey;
81
82 // Shaped results
83 SkTArray<Run, false> fRuns;
84 SkTArray<Cluster, true> fClusters;
85 SkTArray<size_t, true> fClustersIndexFromCodeUnit;
86 // ICU results
87 SkTArray<SkUnicode::CodeUnitFlags, true> fCodeUnitProperties;
88 std::vector<size_t> fWords;
89 std::vector<SkUnicode::BidiRegion> fBidiRegions;
90 bool fHasLineBreaks;
91 bool fHasWhitespacesInside;
92 TextIndex fTrailingSpaces;
93 };
94
mix(uint32_t hash,uint32_t data)95 uint32_t ParagraphCacheKey::mix(uint32_t hash, uint32_t data) {
96 hash += data;
97 hash += (hash << 10);
98 hash ^= (hash >> 6);
99 return hash;
100 }
101
computeHash() const102 uint32_t ParagraphCacheKey::computeHash() const {
103 uint32_t hash = 0;
104 for (auto& ph : fPlaceholders) {
105 if (ph.fRange.width() == 0) {
106 continue;
107 }
108 hash = mix(hash, SkGoodHash()(ph.fRange.start));
109 hash = mix(hash, SkGoodHash()(ph.fRange.end));
110 hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fHeight)));
111 hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fWidth)));
112 hash = mix(hash, SkGoodHash()(ph.fStyle.fAlignment));
113 hash = mix(hash, SkGoodHash()(ph.fStyle.fBaseline));
114 if (ph.fStyle.fAlignment == PlaceholderAlignment::kBaseline) {
115 hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fBaselineOffset)));
116 }
117 }
118
119 for (auto& ts : fTextStyles) {
120 if (ts.fStyle.isPlaceholder()) {
121 continue;
122 }
123 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getLetterSpacing())));
124 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getWordSpacing())));
125 hash = mix(hash, SkGoodHash()(ts.fStyle.getLocale()));
126 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getHeight())));
127 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getBaselineShift())));
128 for (auto& ff : ts.fStyle.getFontFamilies()) {
129 hash = mix(hash, SkGoodHash()(ff));
130 }
131 for (auto& ff : ts.fStyle.getFontFeatures()) {
132 hash = mix(hash, SkGoodHash()(ff.fValue));
133 hash = mix(hash, SkGoodHash()(ff.fName));
134 }
135 hash = mix(hash, std::hash<std::optional<FontArguments>>()(ts.fStyle.getFontArguments()));
136 hash = mix(hash, SkGoodHash()(ts.fStyle.getFontStyle()));
137 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getFontSize())));
138 hash = mix(hash, SkGoodHash()(ts.fRange));
139 }
140
141 hash = mix(hash, SkGoodHash()(relax(fParagraphStyle.getHeight())));
142 hash = mix(hash, SkGoodHash()(fParagraphStyle.getTextDirection()));
143 hash = mix(hash, SkGoodHash()(fParagraphStyle.getReplaceTabCharacters() ? 1 : 0));
144
145 auto& strutStyle = fParagraphStyle.getStrutStyle();
146 if (strutStyle.getStrutEnabled()) {
147 hash = mix(hash, SkGoodHash()(relax(strutStyle.getHeight())));
148 hash = mix(hash, SkGoodHash()(relax(strutStyle.getLeading())));
149 hash = mix(hash, SkGoodHash()(relax(strutStyle.getFontSize())));
150 hash = mix(hash, SkGoodHash()(strutStyle.getHeightOverride()));
151 hash = mix(hash, SkGoodHash()(strutStyle.getFontStyle()));
152 hash = mix(hash, SkGoodHash()(strutStyle.getForceStrutHeight()));
153 for (auto& ff : strutStyle.getFontFamilies()) {
154 hash = mix(hash, SkGoodHash()(ff));
155 }
156 }
157
158 hash = mix(hash, SkGoodHash()(fText));
159 return hash;
160 }
161
operator ()(const ParagraphCacheKey & key) const162 uint32_t ParagraphCache::KeyHash::operator()(const ParagraphCacheKey& key) const {
163 return key.hash();
164 }
165
operator ==(const ParagraphCacheKey & other) const166 bool ParagraphCacheKey::operator==(const ParagraphCacheKey& other) const {
167 if (fText.size() != other.fText.size()) {
168 return false;
169 }
170 if (fPlaceholders.size() != other.fPlaceholders.size()) {
171 return false;
172 }
173 if (fText != other.fText) {
174 return false;
175 }
176 if (fTextStyles.size() != other.fTextStyles.size()) {
177 return false;
178 }
179
180 // There is no need to compare default paragraph styles - they are included into fTextStyles
181 if (!exactlyEqual(fParagraphStyle.getHeight(), other.fParagraphStyle.getHeight())) {
182 return false;
183 }
184 if (fParagraphStyle.getTextDirection() != other.fParagraphStyle.getTextDirection()) {
185 return false;
186 }
187
188 if (!(fParagraphStyle.getStrutStyle() == other.fParagraphStyle.getStrutStyle())) {
189 return false;
190 }
191
192 if (!(fParagraphStyle.getReplaceTabCharacters() == other.fParagraphStyle.getReplaceTabCharacters())) {
193 return false;
194 }
195
196 for (int i = 0; i < fTextStyles.size(); ++i) {
197 auto& tsa = fTextStyles[i];
198 auto& tsb = other.fTextStyles[i];
199 if (tsa.fStyle.isPlaceholder()) {
200 continue;
201 }
202 if (!(tsa.fStyle.equalsByFonts(tsb.fStyle))) {
203 return false;
204 }
205 if (tsa.fRange.width() != tsb.fRange.width()) {
206 return false;
207 }
208 if (tsa.fRange.start != tsb.fRange.start) {
209 return false;
210 }
211 }
212 for (int i = 0; i < fPlaceholders.size(); ++i) {
213 auto& tsa = fPlaceholders[i];
214 auto& tsb = other.fPlaceholders[i];
215 if (tsa.fRange.width() == 0 && tsb.fRange.width() == 0) {
216 continue;
217 }
218 if (!(tsa.fStyle.equals(tsb.fStyle))) {
219 return false;
220 }
221 if (tsa.fRange.width() != tsb.fRange.width()) {
222 return false;
223 }
224 if (tsa.fRange.start != tsb.fRange.start) {
225 return false;
226 }
227 }
228
229 return true;
230 }
231
232 struct ParagraphCache::Entry {
233
Entryskia::textlayout::ParagraphCache::Entry234 Entry(ParagraphCacheValue* value) : fValue(value) {}
235 std::unique_ptr<ParagraphCacheValue> fValue;
236 };
237
ParagraphCache()238 ParagraphCache::ParagraphCache()
239 : fChecker([](ParagraphImpl* impl, const char*, bool){ })
240 , fLRUCacheMap(kMaxEntries)
241 , fCacheIsOn(true)
242 , fLastCachedValue(nullptr)
243 #ifdef PARAGRAPH_CACHE_STATS
244 , fTotalRequests(0)
245 , fCacheMisses(0)
246 , fHashMisses(0)
247 #endif
248 { }
249
~ParagraphCache()250 ParagraphCache::~ParagraphCache() { }
251
updateTo(ParagraphImpl * paragraph,const Entry * entry)252 void ParagraphCache::updateTo(ParagraphImpl* paragraph, const Entry* entry) {
253
254 paragraph->fRuns.clear();
255 paragraph->fRuns = entry->fValue->fRuns;
256 paragraph->fClusters = entry->fValue->fClusters;
257 paragraph->fClustersIndexFromCodeUnit = entry->fValue->fClustersIndexFromCodeUnit;
258 paragraph->fCodeUnitProperties = entry->fValue->fCodeUnitProperties;
259 paragraph->fWords = entry->fValue->fWords;
260 paragraph->fBidiRegions = entry->fValue->fBidiRegions;
261 paragraph->fHasLineBreaks = entry->fValue->fHasLineBreaks;
262 paragraph->fHasWhitespacesInside = entry->fValue->fHasWhitespacesInside;
263 paragraph->fTrailingSpaces = entry->fValue->fTrailingSpaces;
264 for (auto& run : paragraph->fRuns) {
265 run.setOwner(paragraph);
266 }
267 for (auto& cluster : paragraph->fClusters) {
268 cluster.setOwner(paragraph);
269 }
270 }
271
printStatistics()272 void ParagraphCache::printStatistics() {
273 SkDebugf("--- Paragraph Cache ---\n");
274 SkDebugf("Total requests: %d\n", fTotalRequests);
275 SkDebugf("Cache misses: %d\n", fCacheMisses);
276 SkDebugf("Cache miss %%: %f\n", (fTotalRequests > 0) ? 100.f * fCacheMisses / fTotalRequests : 0.f);
277 int cacheHits = fTotalRequests - fCacheMisses;
278 SkDebugf("Hash miss %%: %f\n", (cacheHits > 0) ? 100.f * fHashMisses / cacheHits : 0.f);
279 SkDebugf("---------------------\n");
280 }
281
abandon()282 void ParagraphCache::abandon() {
283 this->reset();
284 }
285
reset()286 void ParagraphCache::reset() {
287 SkAutoMutexExclusive lock(fParagraphMutex);
288 #ifdef PARAGRAPH_CACHE_STATS
289 fTotalRequests = 0;
290 fCacheMisses = 0;
291 fHashMisses = 0;
292 #endif
293 fLRUCacheMap.reset();
294 fLastCachedValue = nullptr;
295 }
296
findParagraph(ParagraphImpl * paragraph)297 bool ParagraphCache::findParagraph(ParagraphImpl* paragraph) {
298 if (!fCacheIsOn) {
299 return false;
300 }
301 #ifdef PARAGRAPH_CACHE_STATS
302 ++fTotalRequests;
303 #endif
304 SkAutoMutexExclusive lock(fParagraphMutex);
305 ParagraphCacheKey key(paragraph);
306 std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
307
308 if (!entry) {
309 // We have a cache miss
310 #ifdef PARAGRAPH_CACHE_STATS
311 ++fCacheMisses;
312 #endif
313 fChecker(paragraph, "missingParagraph", true);
314 return false;
315 }
316 updateTo(paragraph, entry->get());
317 fChecker(paragraph, "foundParagraph", true);
318 return true;
319 }
320
updateParagraph(ParagraphImpl * paragraph)321 bool ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
322 if (!fCacheIsOn) {
323 return false;
324 }
325 #ifdef PARAGRAPH_CACHE_STATS
326 ++fTotalRequests;
327 #endif
328 SkAutoMutexExclusive lock(fParagraphMutex);
329
330 ParagraphCacheKey key(paragraph);
331 std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
332 if (!entry) {
333 // isTooMuchMemoryWasted(paragraph) not needed for now
334 if (isPossiblyTextEditing(paragraph)) {
335 // Skip this paragraph
336 return false;
337 }
338 ParagraphCacheValue* value = new ParagraphCacheValue(std::move(key), paragraph);
339 fLRUCacheMap.insert(value->fKey, std::make_unique<Entry>(value));
340 fChecker(paragraph, "addedParagraph", true);
341 fLastCachedValue = value;
342 return true;
343 } else {
344 // We do not have to update the paragraph
345 return false;
346 }
347 }
348
349 // Special situation: (very) long paragraph that is close to the last formatted paragraph
350 #define NOCACHE_PREFIX_LENGTH 40
isPossiblyTextEditing(ParagraphImpl * paragraph)351 bool ParagraphCache::isPossiblyTextEditing(ParagraphImpl* paragraph) {
352 if (fLastCachedValue == nullptr) {
353 return false;
354 }
355
356 auto& lastText = fLastCachedValue->fKey.text();
357 auto& text = paragraph->fText;
358
359 if ((lastText.size() < NOCACHE_PREFIX_LENGTH) || (text.size() < NOCACHE_PREFIX_LENGTH)) {
360 // Either last text or the current are too short
361 return false;
362 }
363
364 if (std::strncmp(lastText.c_str(), text.c_str(), NOCACHE_PREFIX_LENGTH) == 0) {
365 // Texts have the same starts
366 return true;
367 }
368
369 if (std::strncmp(lastText.c_str() + lastText.size() - NOCACHE_PREFIX_LENGTH, &text[text.size() - NOCACHE_PREFIX_LENGTH], NOCACHE_PREFIX_LENGTH) == 0) {
370 // Texts have the same ends
371 return true;
372 }
373
374 // It does not look like editing the text
375 return false;
376 }
377 } // namespace textlayout
378 } // namespace skia
379