Bug 80715 - Search and replace with over 16k+ replacements halts LibO
Summary: Search and replace with over 16k+ replacements halts LibO
Status: RESOLVED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Writer (show other bugs)
Version:
(earliest affected)
4.2.4.2 release
Hardware: All All
: high major
Assignee: Michael Stahl (allotropia)
URL:
Whiteboard: target:4.5.0
Keywords: bibisected, bisected, regression
: 87909 (view as bug list)
Depends on:
Blocks:
 
Reported: 2014-06-30 14:43 UTC by sivin
Modified: 2015-12-17 08:24 UTC (History)
10 users (show)

See Also:
Crash report or crash signature:


Attachments
attachment-8891-0.html (5.40 KB, text/html)
2014-07-01 12:40 UTC, nsivin
Details
attachment-8891-1.dat (1 bytes, multipart/alternative)
2014-07-01 12:40 UTC, nsivin
Details
Egoist.odt (522.75 KB, application/vnd.oasis.opendocument.text)
2014-07-01 12:40 UTC, nsivin
Details

Note You need to log in before you can comment on or make changes to this bug.
Description sivin 2014-06-30 14:43:43 UTC
I am using Writer 4.2.4.2 in US English under Linux Mint 17 on a fast PC with 4GB of RAM to reformat a downloaded .odt file of about half a megabyte. I tried to do a simple search and replace to convert the carriage returns at the end of each line into spaces (a total of about 5000 replacements). As soon as the change has taken place (and is visible), an error message appears telling me that Writer can’t do the replacements unless I turn off Undo first---although I can see the changed file. No matter how I reply (Yes, No, or Cancel), the screen freezes entirely and I can’t do anything to save the changes. No forced quit works; I have to turn the computer off manually and recover the file (without the changes). For some curious reason, accessing the help file doesn’t explain how to turn Undo off.

My purpose was to reformat a Project Gutenberg book, which has CR's at the end of every line, so that the lines wrap. I first did a search for two CR's, which mark a paragraph, replacing them with a #, which could later be changed back to a paragraph mark.

I am attaching the file, which is at the point where I changed the double CR's to #, and manually changed the single CR's to spaces for the first five pages.
Comment 1 Yousuf Philips (jay) (retired) 2014-07-01 03:18:51 UTC
Hi sivin,

If you can supply us with the file, we can test against it and find out why its crashing.
Comment 2 nsivin 2014-07-01 12:40:39 UTC
Created attachment 102068 [details]
attachment-8891-0.html

Here is the file that keeps crashing. What I do is search for $ and 
replace all with a space. Before doing that, I replaced the double 
paragraph marks (about 500 of them) with #, so that I can restore them 
later.

I get an error message that says I have to turn off Undo.

I succeeded in doing the replacement on the first 50 pages by moving the 
remaining 600 pages to another file. With 100 pages, I still get the 
crash. To get the file I am sending you, I moved the 600 pages back in 
(they are now the top of p. 49 on). It still crashes the system, except 
when I reply in the error message dialog by telling it not to turn off 
Undo. In that case, it tells me it has done the replacement, but 
actually it hasn't changed anything. If I don't do that, I get a 
complete system crash. Sometimes I can terminate it by forcing 
termination of Writer; otherwise I have to turn the machine off and then 
on again manually, and restore the file.

I can't believe that Writer was designed so that one can't do a Replace 
All on 100 pages of text.

Cheers,

Nathan


On 06/30/2014 11:18 PM, bugzilla-daemon@freedesktop.org wrote:
> Jay Philips <mailto:philipz85@hotmail.com> changed bug 80715 
> <https://bugs.freedesktop.org/show_bug.cgi?id=80715>
> What 	Removed 	Added
> Status 	UNCONFIRMED 	NEEDINFO
> CC 		philipz85@hotmail.com
> Ever confirmed 		1
>
> *Comment # 1 <https://bugs.freedesktop.org/show_bug.cgi?id=80715#c1> 
> on bug 80715 <https://bugs.freedesktop.org/show_bug.cgi?id=80715> from 
> Jay Philips <mailto:philipz85@hotmail.com> *
> Hi sivin,
>
> If you can supply us with the file, we can test against it and find out why its
> crashing.
> ------------------------------------------------------------------------
> You are receiving this mail because:
>
>   * You reported the bug.
>
Comment 3 nsivin 2014-07-01 12:40:40 UTC
Created attachment 102069 [details]
attachment-8891-1.dat
Comment 4 nsivin 2014-07-01 12:40:40 UTC
Created attachment 102070 [details]
Egoist.odt
Comment 5 Julien Nabet 2014-07-01 20:40:09 UTC
On pc Debian x86-64 with 4.2.5 LO Debian package, I don't reproduce this.

Did you install any LO specific extensions?
For the test, could you rename your LO directory profile? (see https://wiki.documentfoundation.org/UserProfile)
If you still reproduce this, could you give a try to LO 4.2.5?
Comment 6 nsivin 2014-07-01 23:58:22 UTC
I used LO 4.2.4.2 (installed Writer and Calc only), the current version 
in Linux Mint 17. If you want me to use a more recent version, I will 
need instructions for the best way to update.

Once I hear from you about this, I will first try to reproduce the 
problem with the updated Writer and, if that doesn't work, rename my LO 
directory profile and report the results.

Cheers,
Nathan


On 07/01/2014 04:40 PM, bugzilla-daemon@freedesktop.org wrote:
> Julien Nabet <mailto:serval2412@yahoo.fr> changed bug 80715 
> <https://bugs.freedesktop.org/show_bug.cgi?id=80715>
> What 	Removed 	Added
> CC 		serval2412@yahoo.fr
>
> *Comment # 5 <https://bugs.freedesktop.org/show_bug.cgi?id=80715#c5> 
> on bug 80715 <https://bugs.freedesktop.org/show_bug.cgi?id=80715> from 
> Julien Nabet <mailto:serval2412@yahoo.fr> *
> On pc Debian x86-64 with 4.2.5 LO Debian package, I don't reproduce this.
>
> Did you install any LO specific extensions?
> For the test, could you rename your LO directory profile? (see
> https://wiki.documentfoundation.org/UserProfile)
> If you still reproduce this, could you give a try to LO 4.2.5?
> ------------------------------------------------------------------------
> You are receiving this mail because:
>
>   * You reported the bug.
>
Comment 7 nsivin 2014-07-02 00:18:55 UTC
P. S. No, I didn't install any extensions.

Cheers,
Nathan

On 07/01/2014 04:40 PM, bugzilla-daemon@freedesktop.org wrote:
> Julien Nabet <mailto:serval2412@yahoo.fr> changed bug 80715 
> <https://bugs.freedesktop.org/show_bug.cgi?id=80715>
> What 	Removed 	Added
> CC 		serval2412@yahoo.fr
>
> *Comment # 5 <https://bugs.freedesktop.org/show_bug.cgi?id=80715#c5> 
> on bug 80715 <https://bugs.freedesktop.org/show_bug.cgi?id=80715> from 
> Julien Nabet <mailto:serval2412@yahoo.fr> *
> On pc Debian x86-64 with 4.2.5 LO Debian package, I don't reproduce this.
>
> Did you install any LO specific extensions?
> For the test, could you rename your LO directory profile? (see
> https://wiki.documentfoundation.org/UserProfile)
> If you still reproduce this, could you give a try to LO 4.2.5?
> ------------------------------------------------------------------------
> You are receiving this mail because:
>
>   * You reported the bug.
>
Comment 8 Julien Nabet 2014-07-02 05:37:25 UTC
nsivin: please don't answer directly from your emailer but by using this link:
https://bugs.freedesktop.org/show_bug.cgi?id=80715#

I don't know at all when LO 4.2.5 will be available for Linux Mint, it depends on the distrib.
Comment 9 nsivin 2014-07-02 12:42:59 UTC
Then I suggest you use LO 4.2.4.2 to find out whether the crash is 
reproducible. I suggest the person assigned to this bug report use the 
same OS and LO version.

I should also mention that my installation of Mint 17 uses all of the 
level 1-3 updates so far.

Cheers,
Nathan


On 07/02/2014 01:37 AM, bugzilla-daemon@freedesktop.org wrote:
>
> *Comment # 8 <https://bugs.freedesktop.org/show_bug.cgi?id=80715#c8> 
> on bug 80715 <https://bugs.freedesktop.org/show_bug.cgi?id=80715> from 
> Julien Nabet <mailto:serval2412@yahoo.fr> *
> nsivin: please don't answer directly from your emailer but by using this link:
> https://bugs.freedesktop.org/show_bug.cgi?id=80715  <show_bug.cgi?id=80715>#
>
> I don't know at all when LO 4.2.5 will be available for Linux Mint, it depends
> on the distrib.
> ------------------------------------------------------------------------
> You are receiving this mail because:
>
>   * You reported the bug.
>
Comment 10 Yousuf Philips (jay) (retired) 2014-07-02 16:09:00 UTC
Hi Nathan,

Yes i can reproduce on 4.2.4 and 4.3.0 the system halts while its doing the replacing. This seems to be quite similar to the same find and replace problem in calc, mentioned in bug 79422.
Comment 11 nsivin 2014-07-02 21:33:29 UTC
Dear Jay:

I'm prepared to believe you. I have never made a Calc file large enough 
to encounter this problem.

Cheers,
Nathan

On 07/02/2014 12:09 PM, bugzilla-daemon@freedesktop.org wrote:
> Jay Philips <mailto:philipz85@hotmail.com> changed bug 80715 
> <https://bugs.freedesktop.org/show_bug.cgi?id=80715>
> What 	Removed 	Added
> Status 	NEEDINFO 	NEW
>
> *Comment # 10 <https://bugs.freedesktop.org/show_bug.cgi?id=80715#c10> 
> on bug 80715 <https://bugs.freedesktop.org/show_bug.cgi?id=80715> from 
> Jay Philips <mailto:philipz85@hotmail.com> *
> Hi Nathan,
>
> Yes i can reproduce on 4.2.4 and 4.3.0 the system halts while its doing the
> replacing. This seems to be quite similar to the same find and replace problem
> in calc, mentioned inbug 79422  <show_bug.cgi?id=79422>.
> ------------------------------------------------------------------------
> You are receiving this mail because:
>
>   * You reported the bug.
>
Comment 12 Yousuf Philips (jay) (retired) 2014-07-03 03:01:48 UTC
So i did some further testing and on Windows 7 64-bit with an Intel Core 2 CPU @ 1.83Ghz and 2.5gb, and LibO 3.3.0, 3.6.7, and 4.0.6 took 2 minutes to complete to replace the 16,791 replacements. LibO 4.1 showed the 'turn off undo' dialog and i let it run for 40 minutes before cancelling it. Ran LibO 4.4 for 20 minutes before cancelling it.

@Nathan: Please dont reply to these message by email as it adds unnecessary information into the bug tracking system. Please click on the bug number link provided in the email and you will be taken to this bugzilla page, where you can add your comments.
Comment 13 Joel Madero 2014-08-08 04:40:08 UTC
Incorrectly prioritized: 

Major - since it halts LibreOffice this is fine as it might lead to loss of data when users are forced to exit without saving
High - highest is reserved for MAB which isn't appropriate in this case as this won't affect that many users (most users don't have 16k+ replacements)
Comment 14 Matthew Francis 2014-12-21 14:45:06 UTC
Bibisect results from 43all:

commit 2a9ff869c5638dc5c3aa387d0fe55c3291c86288
Author: Bjoern Michaelsen <bjoern.michaelsen@canonical.com>
Date:   Wed Nov 27 05:01:37 2013 +0000

    source-hash-01b7e04172889cbc9e4ac404b105e18ddc062d6f
    
    commit 01b7e04172889cbc9e4ac404b105e18ddc062d6f
    Author:     Tor Lillqvist <tml@collabora.com>
    AuthorDate: Sun Oct 13 14:04:29 2013 +0300
    Commit:     Tor Lillqvist <tml@collabora.com>
    CommitDate: Sun Oct 13 14:04:29 2013 +0300
    
        Bin unnecessary #include
    
        Change-Id: I9ea868ed5bf6e2e2defbd51d5a0a1e6362c3be8d

# bad: [423a84c4f7068853974887d98442bc2a2d0cc91b] source-hash-c15927f20d4727c3b8de68497b6949e72f9e6e9e
# good: [c2069a369d738078124812312d51f21ea1ce2421] source-hash-f160e4935c474a5293b3d3c11b3d538efb4767a0
git bisect start 'latest' 'last41onmaster'
# bad: [33ac6698e6d90d84f99d784b9553ee87eec27d6a] source-hash-732c0f929fc0229b6da37d4ec4b6de8994fcea46
git bisect bad 33ac6698e6d90d84f99d784b9553ee87eec27d6a
# good: [e3a648fdaa2bb87293750400b70ba590733a804a] source-hash-33526481788137d959f27ae32910127d1436c1a8
git bisect good e3a648fdaa2bb87293750400b70ba590733a804a
# good: [e3a648fdaa2bb87293750400b70ba590733a804a] source-hash-33526481788137d959f27ae32910127d1436c1a8
git bisect good e3a648fdaa2bb87293750400b70ba590733a804a
# bad: [a1bd890a0802bd142798b7b601f370ca9c21426b] source-hash-04532617c7d264411563db24dc359326cc18eda7
git bisect bad a1bd890a0802bd142798b7b601f370ca9c21426b
# bad: [a1bd890a0802bd142798b7b601f370ca9c21426b] source-hash-04532617c7d264411563db24dc359326cc18eda7
git bisect bad a1bd890a0802bd142798b7b601f370ca9c21426b
# good: [560f398ecbc305b65a32a4ba0b9e4444761db889] source-hash-dace560b350346b9f9a102ee602bb129a008bcfe
git bisect good 560f398ecbc305b65a32a4ba0b9e4444761db889
# bad: [e371c174576801a7865420008f494c0d3f153f1b] source-hash-01a13519e2a12e1e9b61bab1437d340e389e44bf
git bisect bad e371c174576801a7865420008f494c0d3f153f1b
# bad: [047d10291c5cd0615c992821829c9153e2f06b13] source-hash-43ccd83d2598256de2193348c0b3c7f85fb4870e
git bisect bad 047d10291c5cd0615c992821829c9153e2f06b13
# skip: [a235cee7729b6eda7f2f6b1cf3347d8eb2a1a49c] source-hash-fa469b2e00d83459faebe4c1fcb3ea1aac5fb20d
git bisect skip a235cee7729b6eda7f2f6b1cf3347d8eb2a1a49c
# bad: [f0f03d19b3f0418cef7eb8c5b3f060266781016f] source-hash-3ad12d1a540eeb54fbb34afc3b7a76bf9e3207c3
git bisect bad f0f03d19b3f0418cef7eb8c5b3f060266781016f
# bad: [2a9ff869c5638dc5c3aa387d0fe55c3291c86288] source-hash-01b7e04172889cbc9e4ac404b105e18ddc062d6f
git bisect bad 2a9ff869c5638dc5c3aa387d0fe55c3291c86288
# first bad commit: [2a9ff869c5638dc5c3aa387d0fe55c3291c86288] source-hash-01b7e04172889cbc9e4ac404b105e18ddc062d6f
Comment 15 Matthew Francis 2014-12-21 14:51:14 UTC
Within the above bibisect range, possibly this commit.

Adding Cc: to mstahl@redhat.com. Could you possibly take a look at this? Thanks
(To recap, before the perf regression of this bug, replacing the 16,000 $ in the attached file with " " takes a few seconds. After, it takes ~forever)


commit b60ce8465c8f01242354abccebe00742d164af60
Author: Michael Stahl <mstahl@redhat.com>
Date:   Sat Oct 12 01:54:37 2013 +0200

    sw: fix regex search/replace of $ in selection
    
    SwView::Replace() nowadays first searches for the to-be-replaced text in
    the current selection, which does not work in the corner case of "$"
    when the selection starts at end of a paragraph, as it will when
    clicking "Find" to look for "$" and then clicking "Replace".
    
    The problem is that there is some antique code in SwPaM::Find() to
    move the cursor forward if it's at the end of a paragraph, which is
    presumably some pointless micro-optimization; the result is that
    "Replace" does not replace the selected paragraph break but the
    one in the following paragraph.
    
    (regression from 68a014dbca8bbd25056f75ef551fb81a0dbfb1b7)
    
    Change-Id: I5aae9c272d102a48166c63e01775dc6322f9f02d
Comment 16 Matthew Francis 2015-01-05 09:21:05 UTC
Confirmed by building the source that it was the above mentioned commit b60ce8465c8f01242354abccebe00742d164af60 which decreased performance
Comment 17 Michael Meeks 2015-01-05 11:32:51 UTC
*** Bug 87909 has been marked as a duplicate of this bug. ***
Comment 18 Michael Stahl (allotropia) 2015-02-16 21:40:26 UTC
this pathological case is changing quite a bit:

4.0.6 asks to disable undo, can do it in 2-3 minutes
 creating 17 paragraphs

4.1.6/4.2.8 asks to disable undo, goes into infinite loop
 because paragraphs cannot be merged due to 64k char limit and
 likely the code removed by the commit in comment #15 was
 somehow handling that corner case

4.3.6/4.4 does not ask to disable undo, but needs 50 minutes to do it,
 creating one > 1 million char paragraph

current master goes into infinite loop because of recent
 Ring boost-ification
 
i have fixed the 4.2 infinite loop bug and the boost-Ring bugs,
but not for the 4.3 big-paragraph slowdown.
Comment 19 Michael Stahl (allotropia) 2015-02-16 22:00:09 UTC
bugzilla commit hook out of order again, these are the commits:
 ddadc1ee95c09eaadb0a1d01e234952b8581694c "tdf#80715: fix infinite loop in find-and-replace if SwTxtNode full"
 54e93460a53629c9428d3ed129a32f052b6bdd7e "(related: tdf#80715) sw: fix Ring::MoveTo() not doing anything..."
 6c92e54a3abcaa1d8f5d83d74dfb0b77415be1d3 "sw: work around buggy boost::intrusive::circular_list_algorithms::unlink()"
Comment 20 Michael Stahl (allotropia) 2015-02-25 22:35:26 UTC
so this is getting confusing,
i've fixed 2 infinite loops with this bug id,
and another inifite loop reported as bug 89105;
there are now no more known infinite loops.

however in 4.3 and later, find-and-replace is still very very slow,
and i've filed bug 89665 and bug 89666 for 2 causes of slowness.

hence resolving this infinite loop bug as fixed.
Comment 21 Yousuf Philips (jay) (retired) 2015-02-26 01:40:41 UTC
Thanks for all the work Michael. Just wondering if this was pushed to 4.3 and 4.4.
Comment 22 Michael Stahl (allotropia) 2015-02-26 12:06:42 UTC
(In reply to Jay Philips from comment #21)
> Just wondering if this was pushed to 4.3 and 4.4.

not for the fixes for this bug, the one infinite loop was
only on master and the other is mostly theoretical
since 4.3 because you'd need 2 billion characters
in a document to trigger it
(fix would help for the 4.2 branch, but that is EOL).
Comment 23 Robinson Tryon (qubit) 2015-12-17 08:24:41 UTC
Migrating Whiteboard tags to Keywords: (bibisected)
[NinjaEdit]