Disable hyphenation for unreasonably long words

Very long words cause O(n^2) behavior. These are unlikely to happen in
real text, but do happen with synthetic strings, so in those cases we
just disable hyphenation.

Bug: 20790394
Change-Id: Idf957dd40b24efe1476f619f17093a48b5bc56f7

1 files changed, 7 insertions, 1 deletions

diff --git a/libs/minikin/LineBreaker.cpp b/libs/minikin/LineBreaker.cpp
index 5eb077c..dbd6ea8 100644
--- a/libs/minikin/LineBreaker.cpp
+++ b/libs/minikin/LineBreaker.cpp
@@ -37,6 +37,12 @@ const float SCORE_INFTY = std::numeric_limits<float>::max();
 const float SCORE_OVERFULL = 1e12f;
 const float SCORE_DESPERATE = 1e10f;
 
+// Very long words trigger O(n^2) behavior in hyphenation, so we disable hyphenation for
+// unreasonably long words. This is somewhat of a heuristic because extremely long words
+// are possible in some languages. This does mean that very long real words can get
+// broken by desperate breaks, with no hyphens.
+const size_t LONGEST_HYPHENATED_WORD = 45;
+
 // When the text buffer is within this limit, capacity of vectors is retained at finish(),
 // to avoid allocation.
 const size_t MAX_TEXT_BUF_RETAIN = 32678;
@@ -145,7 +151,7 @@ float LineBreaker::addStyleRun(MinikinPaint* paint, const FontCollection* typefa
             if (c != CHAR_SOFT_HYPHEN) {
                 if (paint != nullptr && mHyphenator != nullptr &&
                         mHyphenationFrequency != kHyphenationFrequency_None &&
-                        wordEnd > lastBreak) {
+                        wordEnd > lastBreak && wordEnd - lastBreak <= LONGEST_HYPHENATED_WORD) {
                     mHyphenator->hyphenate(&mHyphBuf, &mTextBuf[lastBreak], wordEnd - lastBreak);
     #if VERBOSE_DEBUG
                     std::string hyphenatedString;