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