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