blob: 3c009e23157b3f72231a55472d04fbc439132544 [file] [log] [blame]
// Copyright 2019 Google LLC.
#include <memory>
#include "modules/skparagraph/include/FontArguments.h"
#include "modules/skparagraph/include/ParagraphCache.h"
#include "modules/skparagraph/src/ParagraphImpl.h"
namespace skia {
namespace textlayout {
namespace {
SkScalar relax(SkScalar a) {
// This rounding is done to match Flutter tests. Must be removed..
if (SkScalarIsFinite(a)) {
auto threshold = SkIntToScalar(1 << 12);
return SkScalarRoundToScalar(a * threshold)/threshold;
} else {
return a;
}
}
bool exactlyEqual(SkScalar x, SkScalar y) {
return x == y || (x != x && y != y);
}
} // namespace
class ParagraphCacheKey {
public:
ParagraphCacheKey(const ParagraphImpl* paragraph)
: fText(paragraph->fText.c_str(), paragraph->fText.size())
, fPlaceholders(paragraph->fPlaceholders)
, fTextStyles(paragraph->fTextStyles)
, fParagraphStyle(paragraph->paragraphStyle()) {
fHash = computeHash();
}
ParagraphCacheKey(const ParagraphCacheKey& other) = default;
ParagraphCacheKey(ParagraphCacheKey&& other)
: fText(std::move(other.fText))
, fPlaceholders(std::move(other.fPlaceholders))
, fTextStyles(std::move(other.fTextStyles))
, fParagraphStyle(std::move(other.fParagraphStyle))
, fHash(other.fHash) {
other.fHash = 0;
}
bool operator==(const ParagraphCacheKey& other) const;
uint32_t hash() const { return fHash; }
const SkString& text() const { return fText; }
private:
static uint32_t mix(uint32_t hash, uint32_t data);
uint32_t computeHash() const;
SkString fText;
SkTArray<Placeholder, true> fPlaceholders;
SkTArray<Block, true> fTextStyles;
ParagraphStyle fParagraphStyle;
uint32_t fHash;
};
class ParagraphCacheValue {
public:
ParagraphCacheValue(ParagraphCacheKey&& key, const ParagraphImpl* paragraph)
: fKey(std::move(key))
, fRuns(paragraph->fRuns)
, fClusters(paragraph->fClusters)
, fClustersIndexFromCodeUnit(paragraph->fClustersIndexFromCodeUnit)
, fCodeUnitProperties(paragraph->fCodeUnitProperties)
, fWords(paragraph->fWords)
, fBidiRegions(paragraph->fBidiRegions)
, fUTF8IndexForUTF16Index(paragraph->fUTF8IndexForUTF16Index)
, fUTF16IndexForUTF8Index(paragraph->fUTF16IndexForUTF8Index)
, fHasLineBreaks(paragraph->fHasLineBreaks)
, fHasWhitespacesInside(paragraph->fHasWhitespacesInside)
, fTrailingSpaces(paragraph->fTrailingSpaces) { }
// Input == key
ParagraphCacheKey fKey;
// Shaped results
SkTArray<Run, false> fRuns;
SkTArray<Cluster, true> fClusters;
SkTArray<size_t, true> fClustersIndexFromCodeUnit;
// ICU results
SkTArray<CodeUnitFlags> fCodeUnitProperties;
std::vector<size_t> fWords;
std::vector<SkUnicode::BidiRegion> fBidiRegions;
SkTArray<TextIndex, true> fUTF8IndexForUTF16Index;
SkTArray<size_t, true> fUTF16IndexForUTF8Index;
bool fHasLineBreaks;
bool fHasWhitespacesInside;
TextIndex fTrailingSpaces;
};
uint32_t ParagraphCacheKey::mix(uint32_t hash, uint32_t data) {
hash += data;
hash += (hash << 10);
hash ^= (hash >> 6);
return hash;
}
uint32_t ParagraphCacheKey::computeHash() const {
uint32_t hash = 0;
for (auto& ph : fPlaceholders) {
if (ph.fRange.width() == 0) {
continue;
}
hash = mix(hash, SkGoodHash()(ph.fRange.start));
hash = mix(hash, SkGoodHash()(ph.fRange.end));
hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fHeight)));
hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fWidth)));
hash = mix(hash, SkGoodHash()(ph.fStyle.fAlignment));
hash = mix(hash, SkGoodHash()(ph.fStyle.fBaseline));
if (ph.fStyle.fAlignment == PlaceholderAlignment::kBaseline) {
hash = mix(hash, SkGoodHash()(relax(ph.fStyle.fBaselineOffset)));
}
}
for (auto& ts : fTextStyles) {
if (ts.fStyle.isPlaceholder()) {
continue;
}
hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getLetterSpacing())));
hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getWordSpacing())));
hash = mix(hash, SkGoodHash()(ts.fStyle.getLocale()));
hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getHeight())));
hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getBaselineShift())));
for (auto& ff : ts.fStyle.getFontFamilies()) {
hash = mix(hash, SkGoodHash()(ff));
}
for (auto& ff : ts.fStyle.getFontFeatures()) {
hash = mix(hash, SkGoodHash()(ff.fValue));
hash = mix(hash, SkGoodHash()(ff.fName));
}
hash = mix(hash, std::hash<std::optional<FontArguments>>()(ts.fStyle.getFontArguments()));
hash = mix(hash, SkGoodHash()(ts.fStyle.getFontStyle()));
hash = mix(hash, SkGoodHash()(relax(ts.fStyle.getFontSize())));
hash = mix(hash, SkGoodHash()(ts.fRange));
}
hash = mix(hash, SkGoodHash()(relax(fParagraphStyle.getHeight())));
hash = mix(hash, SkGoodHash()(fParagraphStyle.getTextDirection()));
auto& strutStyle = fParagraphStyle.getStrutStyle();
if (strutStyle.getStrutEnabled()) {
hash = mix(hash, SkGoodHash()(relax(strutStyle.getHeight())));
hash = mix(hash, SkGoodHash()(relax(strutStyle.getLeading())));
hash = mix(hash, SkGoodHash()(relax(strutStyle.getFontSize())));
hash = mix(hash, SkGoodHash()(strutStyle.getHeightOverride()));
hash = mix(hash, SkGoodHash()(strutStyle.getFontStyle()));
hash = mix(hash, SkGoodHash()(strutStyle.getForceStrutHeight()));
for (auto& ff : strutStyle.getFontFamilies()) {
hash = mix(hash, SkGoodHash()(ff));
}
}
hash = mix(hash, SkGoodHash()(fText));
return hash;
}
uint32_t ParagraphCache::KeyHash::operator()(const ParagraphCacheKey& key) const {
return key.hash();
}
bool ParagraphCacheKey::operator==(const ParagraphCacheKey& other) const {
if (fText.size() != other.fText.size()) {
return false;
}
if (fPlaceholders.count() != other.fPlaceholders.count()) {
return false;
}
if (fText != other.fText) {
return false;
}
if (fTextStyles.size() != other.fTextStyles.size()) {
return false;
}
// There is no need to compare default paragraph styles - they are included into fTextStyles
if (!exactlyEqual(fParagraphStyle.getHeight(), other.fParagraphStyle.getHeight())) {
return false;
}
if (fParagraphStyle.getTextDirection() != other.fParagraphStyle.getTextDirection()) {
return false;
}
if (!(fParagraphStyle.getStrutStyle() == other.fParagraphStyle.getStrutStyle())) {
return false;
}
for (size_t i = 0; i < fTextStyles.size(); ++i) {
auto& tsa = fTextStyles[i];
auto& tsb = other.fTextStyles[i];
if (tsa.fStyle.isPlaceholder()) {
continue;
}
if (!(tsa.fStyle.equalsByFonts(tsb.fStyle))) {
return false;
}
if (tsa.fRange.width() != tsb.fRange.width()) {
return false;
}
if (tsa.fRange.start != tsb.fRange.start) {
return false;
}
}
for (size_t i = 0; i < fPlaceholders.size(); ++i) {
auto& tsa = fPlaceholders[i];
auto& tsb = other.fPlaceholders[i];
if (tsa.fRange.width() == 0 && tsb.fRange.width() == 0) {
continue;
}
if (!(tsa.fStyle.equals(tsb.fStyle))) {
return false;
}
if (tsa.fRange.width() != tsb.fRange.width()) {
return false;
}
if (tsa.fRange.start != tsb.fRange.start) {
return false;
}
}
return true;
}
struct ParagraphCache::Entry {
Entry(ParagraphCacheValue* value) : fValue(value) {}
std::unique_ptr<ParagraphCacheValue> fValue;
};
ParagraphCache::ParagraphCache()
: fChecker([](ParagraphImpl* impl, const char*, bool){ })
, fLRUCacheMap(kMaxEntries)
, fCacheIsOn(true)
, fLastCachedValue(nullptr)
#ifdef PARAGRAPH_CACHE_STATS
, fTotalRequests(0)
, fCacheMisses(0)
, fHashMisses(0)
#endif
{ }
ParagraphCache::~ParagraphCache() { }
void ParagraphCache::updateTo(ParagraphImpl* paragraph, const Entry* entry) {
paragraph->fRuns.reset();
paragraph->fRuns = entry->fValue->fRuns;
paragraph->fClusters = entry->fValue->fClusters;
paragraph->fClustersIndexFromCodeUnit = entry->fValue->fClustersIndexFromCodeUnit;
paragraph->fCodeUnitProperties = entry->fValue->fCodeUnitProperties;
paragraph->fWords = entry->fValue->fWords;
paragraph->fBidiRegions = entry->fValue->fBidiRegions;
paragraph->fUTF8IndexForUTF16Index = entry->fValue->fUTF8IndexForUTF16Index;
paragraph->fUTF16IndexForUTF8Index = entry->fValue->fUTF16IndexForUTF8Index;
paragraph->fHasLineBreaks = entry->fValue->fHasLineBreaks;
paragraph->fHasWhitespacesInside = entry->fValue->fHasWhitespacesInside;
paragraph->fTrailingSpaces = entry->fValue->fTrailingSpaces;
for (auto& run : paragraph->fRuns) {
run.setOwner(paragraph);
}
for (auto& cluster : paragraph->fClusters) {
cluster.setOwner(paragraph);
}
}
void ParagraphCache::printStatistics() {
SkDebugf("--- Paragraph Cache ---\n");
SkDebugf("Total requests: %d\n", fTotalRequests);
SkDebugf("Cache misses: %d\n", fCacheMisses);
SkDebugf("Cache miss %%: %f\n", (fTotalRequests > 0) ? 100.f * fCacheMisses / fTotalRequests : 0.f);
int cacheHits = fTotalRequests - fCacheMisses;
SkDebugf("Hash miss %%: %f\n", (cacheHits > 0) ? 100.f * fHashMisses / cacheHits : 0.f);
SkDebugf("---------------------\n");
}
void ParagraphCache::abandon() {
this->reset();
}
void ParagraphCache::reset() {
SkAutoMutexExclusive lock(fParagraphMutex);
#ifdef PARAGRAPH_CACHE_STATS
fTotalRequests = 0;
fCacheMisses = 0;
fHashMisses = 0;
#endif
fLRUCacheMap.reset();
fLastCachedValue = nullptr;
}
bool ParagraphCache::findParagraph(ParagraphImpl* paragraph) {
if (!fCacheIsOn) {
return false;
}
#ifdef PARAGRAPH_CACHE_STATS
++fTotalRequests;
#endif
SkAutoMutexExclusive lock(fParagraphMutex);
ParagraphCacheKey key(paragraph);
std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
if (!entry) {
// We have a cache miss
#ifdef PARAGRAPH_CACHE_STATS
++fCacheMisses;
#endif
fChecker(paragraph, "missingParagraph", true);
return false;
}
updateTo(paragraph, entry->get());
fChecker(paragraph, "foundParagraph", true);
return true;
}
bool ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
if (!fCacheIsOn) {
return false;
}
#ifdef PARAGRAPH_CACHE_STATS
++fTotalRequests;
#endif
SkAutoMutexExclusive lock(fParagraphMutex);
ParagraphCacheKey key(paragraph);
std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
if (!entry) {
// isTooMuchMemoryWasted(paragraph) not needed for now
if (isPossiblyTextEditing(paragraph)) {
// Skip this paragraph
return false;
}
ParagraphCacheValue* value = new ParagraphCacheValue(std::move(key), paragraph);
fLRUCacheMap.insert(value->fKey, std::make_unique<Entry>(value));
fChecker(paragraph, "addedParagraph", true);
fLastCachedValue = value;
return true;
} else {
// We do not have to update the paragraph
return false;
}
}
// Special situation: (very) long paragraph that is close to the last formatted paragraph
#define NOCACHE_PREFIX_LENGTH 40
bool ParagraphCache::isPossiblyTextEditing(ParagraphImpl* paragraph) {
if (fLastCachedValue == nullptr) {
return false;
}
auto& lastText = fLastCachedValue->fKey.text();
auto& text = paragraph->fText;
if ((lastText.size() < NOCACHE_PREFIX_LENGTH) || (text.size() < NOCACHE_PREFIX_LENGTH)) {
// Either last text or the current are too short
return false;
}
if (std::strncmp(lastText.c_str(), text.c_str(), NOCACHE_PREFIX_LENGTH) == 0) {
// Texts have the same starts
return true;
}
if (std::strncmp(lastText.c_str() + lastText.size() - NOCACHE_PREFIX_LENGTH, &text[text.size() - NOCACHE_PREFIX_LENGTH], NOCACHE_PREFIX_LENGTH) == 0) {
// Texts have the same ends
return true;
}
// It does not look like editing the text
return false;
}
} // namespace textlayout
} // namespace skia