1// Copyright 2019 Google LLC.
2#include <memory>
3
4#include "modules/skparagraph/include/ParagraphCache.h"
5#include "modules/skparagraph/src/ParagraphImpl.h"
6
7namespace skia {
8namespace textlayout {
9
10namespace {
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} // namespace
21
22class ParagraphCacheKey {
23public:
24 ParagraphCacheKey(const ParagraphImpl* paragraph)
25 : fText(paragraph->fText.c_str(), paragraph->fText.size())
26 , fPlaceholders(paragraph->fPlaceholders)
27 , fTextStyles(paragraph->fTextStyles)
28 , fParagraphStyle(paragraph->paragraphStyle()) { }
29
30 SkString fText;
31 SkTArray<Placeholder, true> fPlaceholders;
32 SkTArray<Block, true> fTextStyles;
33 ParagraphStyle fParagraphStyle;
34};
35
36class ParagraphCacheValue {
37public:
38 ParagraphCacheValue(const ParagraphImpl* paragraph)
39 : fKey(ParagraphCacheKey(paragraph))
40 , fRuns(paragraph->fRuns)
41 , fCodeUnitProperties(paragraph->fCodeUnitProperties)
42 , fWords(paragraph->fWords)
43 , fBidiRegions(paragraph->fBidiRegions)
44 , fUTF8IndexForUTF16Index(paragraph->fUTF8IndexForUTF16Index)
45 , fUTF16IndexForUTF8Index(paragraph->fUTF16IndexForUTF8Index) { }
46
47 // Input == key
48 ParagraphCacheKey fKey;
49
50 // Shaped results
51 SkTArray<Run, false> fRuns;
52 // ICU results
53 SkTArray<CodeUnitFlags> fCodeUnitProperties;
54 std::vector<size_t> fWords;
55 std::vector<BidiRegion> fBidiRegions;
56 SkTArray<TextIndex, true> fUTF8IndexForUTF16Index;
57 SkTArray<size_t, true> fUTF16IndexForUTF8Index;
58};
59
60uint32_t ParagraphCache::KeyHash::mix(uint32_t hash, uint32_t data) const {
61 hash += data;
62 hash += (hash << 10);
63 hash ^= (hash >> 6);
64 return hash;
65}
66
67uint32_t ParagraphCache::KeyHash::operator()(const ParagraphCacheKey& key) const {
68 uint32_t hash = 0;
69 for (auto& ph : key.fPlaceholders) {
70 if (ph.fRange.width() == 0) {
71 continue;
72 }
73 hash = mix(hash, SkGoodHash()(ph.fRange.start));
74 hash = mix(hash, SkGoodHash()(ph.fRange.end));
75 hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fHeight)));
76 hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fWidth)));
77 hash = mix(hash, SkGoodHash()(ph.fStyle.fAlignment));
78 hash = mix(hash, SkGoodHash()(ph.fStyle.fBaseline));
79 if (ph.fStyle.fAlignment == PlaceholderAlignment::kBaseline) {
80 hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fBaselineOffset)));
81 }
82 }
83
84 for (auto& ts : key.fTextStyles) {
85 if (ts.fStyle.isPlaceholder()) {
86 continue;
87 }
88 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getLetterSpacing())));
89 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getWordSpacing())));
90 hash = mix(hash, SkGoodHash()(ts.fStyle.getLocale()));
91 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getHeight())));
92 for (auto& ff : ts.fStyle.getFontFamilies()) {
93 hash = mix(hash, SkGoodHash()(ff));
94 }
95 for (auto& ff : ts.fStyle.getFontFeatures()) {
96 hash = mix(hash, SkGoodHash()(ff.fValue));
97 hash = mix(hash, SkGoodHash()(ff.fName));
98 }
99 hash = mix(hash, SkGoodHash()(ts.fStyle.getFontStyle()));
100 hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getFontSize())));
101 hash = mix(hash, SkGoodHash()(ts.fRange));
102 }
103
104 hash = mix(hash, SkGoodHash()(relax(key.fParagraphStyle.getHeight())));
105 hash = mix(hash, SkGoodHash()(key.fParagraphStyle.getTextDirection()));
106
107 auto& strutStyle = key.fParagraphStyle.getStrutStyle();
108 if (strutStyle.getStrutEnabled()) {
109 hash = mix(hash, SkGoodHash()(relax(strutStyle.getHeight())));
110 hash = mix(hash, SkGoodHash()(relax(strutStyle.getLeading())));
111 hash = mix(hash, SkGoodHash()(relax(strutStyle.getFontSize())));
112 hash = mix(hash, SkGoodHash()(strutStyle.getHeightOverride()));
113 hash = mix(hash, SkGoodHash()(strutStyle.getFontStyle()));
114 hash = mix(hash, SkGoodHash()(strutStyle.getForceStrutHeight()));
115 for (auto& ff : strutStyle.getFontFamilies()) {
116 hash = mix(hash, SkGoodHash()(ff));
117 }
118 }
119
120 hash = mix(hash, SkGoodHash()(key.fText));
121 return hash;
122}
123
124bool operator==(const ParagraphCacheKey& a, const ParagraphCacheKey& b) {
125 if (a.fText.size() != b.fText.size()) {
126 return false;
127 }
128 if (a.fPlaceholders.count() != b.fPlaceholders.count()) {
129 return false;
130 }
131 if (a.fText != b.fText) {
132 return false;
133 }
134 if (a.fTextStyles.size() != b.fTextStyles.size()) {
135 return false;
136 }
137
138 // There is no need to compare default paragraph styles - they are included into fTextStyles
139 if (!nearlyEqual(a.fParagraphStyle.getHeight(), b.fParagraphStyle.getHeight())) {
140 return false;
141 }
142 if (a.fParagraphStyle.getTextDirection() != b.fParagraphStyle.getTextDirection()) {
143 return false;
144 }
145
146 if (!(a.fParagraphStyle.getStrutStyle() == b.fParagraphStyle.getStrutStyle())) {
147 return false;
148 }
149
150 for (size_t i = 0; i < a.fTextStyles.size(); ++i) {
151 auto& tsa = a.fTextStyles[i];
152 auto& tsb = b.fTextStyles[i];
153 if (tsa.fStyle.isPlaceholder()) {
154 continue;
155 }
156 if (!(tsa.fStyle.equalsByFonts(tsb.fStyle))) {
157 return false;
158 }
159 if (tsa.fRange.width() != tsb.fRange.width()) {
160 return false;
161 }
162 if (tsa.fRange.start != tsb.fRange.start) {
163 return false;
164 }
165 }
166 for (size_t i = 0; i < a.fPlaceholders.size(); ++i) {
167 auto& tsa = a.fPlaceholders[i];
168 auto& tsb = b.fPlaceholders[i];
169 if (tsa.fRange.width() == 0 && tsb.fRange.width() == 0) {
170 continue;
171 }
172 if (!(tsa.fStyle.equals(tsb.fStyle))) {
173 return false;
174 }
175 if (tsa.fRange.width() != tsb.fRange.width()) {
176 return false;
177 }
178 if (tsa.fRange.start != tsb.fRange.start) {
179 return false;
180 }
181 }
182
183 return true;
184}
185
186struct ParagraphCache::Entry {
187
188 Entry(ParagraphCacheValue* value) : fValue(value) {}
189 std::unique_ptr<ParagraphCacheValue> fValue;
190};
191
192ParagraphCache::ParagraphCache()
193 : fChecker([](ParagraphImpl* impl, const char*, bool){ })
194 , fLRUCacheMap(kMaxEntries)
195 , fCacheIsOn(true)
196#ifdef PARAGRAPH_CACHE_STATS
197 , fTotalRequests(0)
198 , fCacheMisses(0)
199 , fHashMisses(0)
200#endif
201{ }
202
203ParagraphCache::~ParagraphCache() { }
204
205void ParagraphCache::updateTo(ParagraphImpl* paragraph, const Entry* entry) {
206
207 paragraph->fRuns.reset();
208 paragraph->fRuns = entry->fValue->fRuns;
209 paragraph->fCodeUnitProperties = entry->fValue->fCodeUnitProperties;
210 paragraph->fWords = entry->fValue->fWords;
211 paragraph->fBidiRegions = entry->fValue->fBidiRegions;
212 paragraph->fUTF8IndexForUTF16Index = entry->fValue->fUTF8IndexForUTF16Index;
213 paragraph->fUTF16IndexForUTF8Index = entry->fValue->fUTF16IndexForUTF8Index;
214 for (auto& run : paragraph->fRuns) {
215 run.setOwner(paragraph);
216 }
217}
218
219void ParagraphCache::printStatistics() {
220 SkDebugf("--- Paragraph Cache ---\n");
221 SkDebugf("Total requests: %d\n", fTotalRequests);
222 SkDebugf("Cache misses: %d\n", fCacheMisses);
223 SkDebugf("Cache miss %%: %f\n", (fTotalRequests > 0) ? 100.f * fCacheMisses / fTotalRequests : 0.f);
224 int cacheHits = fTotalRequests - fCacheMisses;
225 SkDebugf("Hash miss %%: %f\n", (cacheHits > 0) ? 100.f * fHashMisses / cacheHits : 0.f);
226 SkDebugf("---------------------\n");
227}
228
229void ParagraphCache::abandon() {
230 SkAutoMutexExclusive lock(fParagraphMutex);
231 fLRUCacheMap.foreach([](ParagraphCacheKey*, std::unique_ptr<Entry>* e) {
232 });
233
234 this->reset();
235}
236
237void ParagraphCache::reset() {
238 SkAutoMutexExclusive lock(fParagraphMutex);
239#ifdef PARAGRAPH_CACHE_STATS
240 fTotalRequests = 0;
241 fCacheMisses = 0;
242 fHashMisses = 0;
243#endif
244 fLRUCacheMap.reset();
245}
246
247bool ParagraphCache::findParagraph(ParagraphImpl* paragraph) {
248 if (!fCacheIsOn) {
249 return false;
250 }
251#ifdef PARAGRAPH_CACHE_STATS
252 ++fTotalRequests;
253#endif
254 SkAutoMutexExclusive lock(fParagraphMutex);
255 ParagraphCacheKey key(paragraph);
256 std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
257
258 if (!entry) {
259 // We have a cache miss
260#ifdef PARAGRAPH_CACHE_STATS
261 ++fCacheMisses;
262#endif
263 fChecker(paragraph, "missingParagraph", true);
264 return false;
265 }
266 updateTo(paragraph, entry->get());
267 fChecker(paragraph, "foundParagraph", true);
268 return true;
269}
270
271bool ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
272 if (!fCacheIsOn) {
273 return false;
274 }
275#ifdef PARAGRAPH_CACHE_STATS
276 ++fTotalRequests;
277#endif
278 SkAutoMutexExclusive lock(fParagraphMutex);
279 ParagraphCacheKey key(paragraph);
280 std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
281 if (!entry) {
282 ParagraphCacheValue* value = new ParagraphCacheValue(paragraph);
283 fLRUCacheMap.insert(key, std::make_unique<Entry>(value));
284 fChecker(paragraph, "addedParagraph", true);
285 return true;
286 } else {
287 // We do not have to update the paragraph
288 return false;
289 }
290}
291} // namespace textlayout
292} // namespace skia
293