• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
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         // We have a cache miss
311 #ifdef PARAGRAPH_CACHE_STATS
312         ++fCacheMisses;
313 #endif
314         fChecker(paragraph, "missingParagraph", true);
315         return false;
316     }
317     updateTo(paragraph, entry->get());
318     fChecker(paragraph, "foundParagraph", true);
319     return true;
320 }
321 
updateParagraph(ParagraphImpl * paragraph)322 bool ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
323     if (!fCacheIsOn) {
324         return false;
325     }
326 #ifdef PARAGRAPH_CACHE_STATS
327     ++fTotalRequests;
328 #endif
329     SkAutoMutexExclusive lock(fParagraphMutex);
330 
331     ParagraphCacheKey key(paragraph);
332     std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
333     if (!entry) {
334         // isTooMuchMemoryWasted(paragraph) not needed for now
335         if (isPossiblyTextEditing(paragraph)) {
336             // Skip this paragraph
337             return false;
338         }
339         ParagraphCacheValue* value = new ParagraphCacheValue(std::move(key), paragraph);
340         fLRUCacheMap.insert(value->fKey, std::make_unique<Entry>(value));
341         fChecker(paragraph, "addedParagraph", true);
342         fLastCachedValue = value;
343         return true;
344     } else {
345         // We do not have to update the paragraph
346         return false;
347     }
348 }
349 
350 // Special situation: (very) long paragraph that is close to the last formatted paragraph
351 #define NOCACHE_PREFIX_LENGTH 40
isPossiblyTextEditing(ParagraphImpl * paragraph)352 bool ParagraphCache::isPossiblyTextEditing(ParagraphImpl* paragraph) {
353     if (fLastCachedValue == nullptr) {
354         return false;
355     }
356 
357     auto& lastText = fLastCachedValue->fKey.text();
358     auto& text = paragraph->fText;
359 
360     if ((lastText.size() < NOCACHE_PREFIX_LENGTH) || (text.size() < NOCACHE_PREFIX_LENGTH)) {
361         // Either last text or the current are too short
362         return false;
363     }
364 
365     if (std::strncmp(lastText.c_str(), text.c_str(), NOCACHE_PREFIX_LENGTH) == 0) {
366         // Texts have the same starts
367         return true;
368     }
369 
370     if (std::strncmp(lastText.c_str() + lastText.size() - NOCACHE_PREFIX_LENGTH, &text[text.size() - NOCACHE_PREFIX_LENGTH], NOCACHE_PREFIX_LENGTH) == 0) {
371         // Texts have the same ends
372         return true;
373     }
374 
375     // It does not look like editing the text
376     return false;
377 }
378 }  // namespace textlayout
379 }  // namespace skia
380