https://bugs.documentfoundation.org/show_bug.cgi?id=172669
Bug ID: 172669
Summary: SwTextGuess::Guess() — backward language-scan bounded
by paragraph start makes layout of a long unbreakable
run quadratic
Product: LibreOffice
Version: 25.2.7.2 release
Hardware: All
OS: All
Status: UNCONFIRMED
Severity: normal
Priority: medium
Component: Writer
Assignee: [email protected]
Reporter: [email protected]
Description:
A single paragraph containing one long contiguous run of characters with no
line-break opportunity (no space/hyphen/CJK break) makes Writer's text layout
scale ~quadratically with the run length. Confirmed trigger: a corrupted paste
leaving a long run of U+FFFD replacement characters; also reproduces with a
long run of emoji. A ~600k-character run takes minutes; the same length of
space-separated text lays out in ~2s.
Proposed fix — bound the non-field case at the current line start, matching the
getLineBreak() call below (already bounded to rInf.GetLineStart()) and the
trailing-blank trim in the same function:
const TextFrameIndex nDoNotStepOver = CH_TXTATR_BREAKWORD == cFieldChr
? rInf.GetIdx() - m_nFieldDiff - TextFrameIndex(1)
- : TextFrameIndex(0);
+ : rInf.GetLineStart();
By replacing the line beginning with '-' with the line beginning with '+' the
series collapses to ~5s / ~8s / ~18s; a normal document renders
byte-identically apart from its own date field.
Related: tdf#163233 is in the same function but its stacks are the
GetTextSize/HarfBuzz-shaping cost, a different contributor from this
isLetterNumeric scan.
Steps to Reproduce:
1.open the attached REPRODUCER-C_synthetic_600k-ufffd-run.odt (one paragraph,
600,000 × U+FFFD), or soffice --headless --convert-to pdf it
Actual Results:
Opening (or --convert-to pdf converting) a document whose single paragraph is
one long run of ~600,000 U+FFFD characters takes ~130 seconds of 100% CPU
before it finishes; Writer is unresponsive for the whole time. The cost scales
quadratically with the run length: 100,000 chars ≈ 9s, 300,000 ≈ 41s, 600,000 ≈
130s. The same character count as ordinary space-separated text lays out in
~2–3s, so it is specifically the unbroken run length within one paragraph that
is quadratic, not the total character count. gdb sampling of the hung process
shows the time is spent in CharClass::isLetterNumeric under the backward
language-scan loop in SwTextGuess::Guess() (sw/source/core/text/guess.cxx),
which is bounded by paragraph start rather than line start and so re-scans back
to index 0 on every formatted line.
Expected Results:
Layout time should scale close to linearly with the text length, as it does for
ordinary prose — a 600,000-character paragraph should lay out in a few seconds,
not minutes, and Writer should not hang.
Reproducible: Always
User Profile Reset: No
Additional Info:
The root cause for this bug is in sw/source/core/text/guess.cxx,
SwTextGuess::Guess(), the backward scan for the last letter/numeric character
(used for the hanging-punctuation script/language choice) is bounded by
nDoNotStepOver = TextFrameIndex(0) in the non-field case — i.e. the start of
the whole paragraph.
When the paragraph has no letter/numeric character anywhere, this scans back to
index 0 on every formatted line → O(n²). Confirmed by gdb: samples sit in
CharClass::isLetterNumeric / unicode::getScriptClassFromUScriptCode under this
loop.
--
You are receiving this mail because:
You are the assignee for the bug.
