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