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