[Upstream] [hardy] Goal Seek hangs Calc indefinitely

[otto67]

Binary package hint: openoffice.org-calc

1) lsb_release -rd
Description: Ubuntu 11.04
Release: 11.04

2) apt-cache policy libreoffice-calc
libreoffice-calc:
  Installed: 1:3.3.2-1ubuntu5
  Candidate: 1:3.3.2-1ubuntu5
  Version table:
 *** 1:3.3.2-1ubuntu5 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty-updates/main i386 Packages
        500 http://us.archive.ubuntu.com/ubuntu/ natty-proposed/main i386 Packages
        100 /var/lib/dpkg/status
     1:3.3.2-1ubuntu4 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty/main i386 Packages

3) What is expected to happen in LibreOffice Calc via the Terminal:

cd ~/Desktop && wget https://bugs.launchpad.net/ubuntu/+source/libreoffice/+bug/156381/+attachment/167142/+files/sample.ods && localc -nologo sample.ods

Tools -> Goal Seek... -> Formula Cell $F$110 -> Target 0 -> Variable Cell $E$7 -> OK button

and it does so quickly and successfully.

4) What happens instead is it hangs Calc (waited ~10 minutes than killed process).

WORKAROUND: Use Gnumeric as it performs the calculation instantly.

apt-cache policy gnumeric
gnumeric:
  Installed: 1.10.13-1ubuntu1
  Candidate: 1.10.13-1ubuntu1
  Version table:
 *** 1.10.13-1ubuntu1 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty/universe i386 Packages
        100 /var/lib/dpkg/status

Original Reporter Comments: If you use the "Goal Seek" on a spreadsheet that exceeds 105 rows OOO calc hangs completely, taking over 50% of CPU and you have to force the exit.

[Koen (koen-beek)]

I can confirm behaviour on my machine

[Koen (koen-beek)]

I have tried this on openoffice 2.3.0 in windows XP and this results in the same problem

seems this is an openoffice calc problem not directly linked to ubuntu or even linux

it's probably best to have this bug transferred upstream to the openoffice team

[Koen (koen-beek)]

reported bug upstream

http://www.openoffice.org/issues/show_bug.cgi?id=83130

[penalvch (penalvch)]

otto67, thank you for reporting this bug and helping make Ubuntu better. This issue is unreproducible in LibreOffice Writer via the Terminal:

cd ~/Desktop && https://bugs.launchpad.net/ubuntu/+source/libreoffice/+bug/156381/+attachment/167142/+files/sample.ods && localc -nologo sample.ods

Tools -> Goal Seek... -> Formula Cell $F$100 -> Target 0 -> Variable Cell $E$7 -> OK button and notice a second later a window pops up noting:

LibreOffice Calc
Goal Seek not successful.
No exact value found.
Insert closest value (0.00)?

YES button

Does this work for you?

lsb_release -rd
Description: Ubuntu 11.04
Release: 11.04

apt-cache policy libreoffice-calc
libreoffice-calc:
  Installed: 1:3.3.2-1ubuntu5
  Candidate: 1:3.3.2-1ubuntu5
  Version table:
 *** 1:3.3.2-1ubuntu5 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty-proposed/main i386
Packages
        100 /var/lib/dpkg/status
     1:3.3.2-1ubuntu4 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty/main i386 Packages

[sanmiguel9 (againsttcpa84)]

No, it does NOT work on an up-to-date Natty (LibreOffice 3.3.2 OOO330m19 (Build:202))

1) open the sample.ods (do not forget 'wget' in the instructions from comment #4 ;-) )
2) Tools → Goal Seek... Formula Cell $F$100 -> Target 0 -> Variable Cell $E$7
3) as expected, after one second the message appears
4) Tools → Goal Seek... Formula Cell $F$110 -> Target 0 -> Variable Cell $E$7
5) LibreOffice freezes
6) Force quit

N.B.: $F$100 vs $F$110

[penalvch (penalvch)]

otto67, since this bug has enough information provided for a developer to begin work, I'm going to mark it as confirmed and let them handle it from here. Thanks for taking the time to make Ubuntu better!

[penalvch (penalvch)]

Created attachment 46880
sample.ods

1) lsb_release -rd
Description: Ubuntu 11.04
Release: 11.04

2) apt-cache policy libreoffice-calc
libreoffice-calc:
  Installed: 1:3.3.2-1ubuntu5
  Candidate: 1:3.3.2-1ubuntu5
  Version table:
 *** 1:3.3.2-1ubuntu5 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty-updates/main i386 Packages
        500 http://us.archive.ubuntu.com/ubuntu/ natty-proposed/main i386 Packages
        100 /var/lib/dpkg/status
     1:3.3.2-1ubuntu4 0
        500 http://us.archive.ubuntu.com/ubuntu/ natty/main i386 Packages

3) What is expected to happen in LibreOffice Calc via the Terminal:

cd ~/Desktop && wget https://bugs.launchpad.net/ubuntu/+source/libreoffice/+bug/156381/+attachment/167142/+files/sample.ods && localc -nologo sample.ods

Tools -> Goal Seek... -> Formula Cell $F$100 -> Target 0 -> Variable Cell $E$7 -> OK button

and it does so quickly and successfully.

4) What happens instead is it hangs Calc (waited ~10 minutes than killed process).

[Markus Mohrhard (moggi)]

Not reproducible with LibreOffice 3.4RC1 at Linux x64.

[penalvch (penalvch)]

Formula Cell $F$100 should actually be $F$110. Reproducible in LibreOffice 3.4.0 DEV300m103(Build:5).

[Libreoffice-z (libreoffice-z)]

[Reproducible] with reporter's sample and "LibreOffice 3.4Beta5 – WIN7 Home Premium (64bit) German UI [DEV300m103 (Build:5)]". I terminated with task manager after 10 Minutes.

Steps to reproduce:
0. Open reporter's sample
1. Menu 'Tools > Options > Calc > Calculate' Precision as shown unchecked <ok>
2. Click 'F110'
3. Menu 'Tools > Boal seek ... >
4. Use cell picker to insert "$F$110" into Pane "Formula Cell" if not
   already visible
5. Insert "0" Into "Target Value"
6. Use cell picker to insert "$E$7" into Pane "Variable Cell" <ok>
   Expected: Mattching value should be found
   Actual: LibO hangs, I killed with task manager after 10, I can't tell if it might have found a result afer longer time.

Pre-condition is

[Libreoffice-z (libreoffice-z)]

Sorry, wrong key, so comment posted before my results were complete ...

Pre-condition is NOT setting "Precision as shown" unchecked, the result seemed to be arbitrary. I was no able to find any influence of those settings.

My first test did not show the hang, all further tests with any settings for Calculation showed the hang. I did the modifications in the calculation settings after my first test without hang.

I can't confirm the hang as a general problem, a simple test with "'B1' =A1^2" and various goals did not show any problem.

I will try to let LibO calc some longer now.

@Christopher M. Penalver:
Your sample seems to suggest that Pane "Formula Cell" should be $F$111, but in your report I read "$F$100". Any reasons for that or only accident? With "$F$100" I can't reproduce the bug, but I can with "$F$110" or "$F$110".

@Kohei:
Please feel free to reassign if it's not your area!

[Libreoffice-z (libreoffice-z)]

Works fine until Formula Cell "$F$106", rest as reported, Hang starts for "$F$107" or higher row No.

It seems that number of calculations steps that Goal Seek can do is limited? I created a more simple test document myownsample.ods to check what happens when I want to reach result "1000" in a cell in Column 'A' wiht start value in 'A1'.

Goal seek worked fine for result in A400, hanged in A500, critical limit seems to be between those 2 cells.

[Libreoffice-z (libreoffice-z)]

Created attachment 46887
Sample Document, see Comment 5

[Kohei Yoshida (kohei-yoshida)]

I'll make this an EasyHack.

Code pointer: ScInterpreter::ScBackSolver() in sc/source/core/tool/interpr2.cxx implements the goal seek algorithm.

[Lemoyne-castle (lemoyne-castle)]

Completed EasyHack markers

[Takeshi Abe (tabe-fixedpoint)]

Created attachment 48162
an experimental fix against master

Let me attach an experimental fix against master, which makes
the depth of recursion lavish.

[Lemoyne-castle (lemoyne-castle)]

Created attachment 48199
Simpler example of using GoalSeek to find fixed payment for loan

Attached a simpler example of using GoalSeek to find fixed payment for a fixed term loan with compound interest.
The fact that changing the MAXRECURSION limit delays the onset of the busy hang -- http://opengrok.libreoffice.org/xref/calc/sc/source/core/data/cell.cxx#69 --
this strongly implies that the real bug here is in ScFormulaCell::Interpret() where different interpreter stack management routines kick in when there are more than MAXRECURSION pending cell/formula interpret calls.
Also GoalSeek in myownsample.ods often creates a zero payment answer which causes the principal goal cell value to move away from the goal of zero instead of closer. This looks like a problem with an error condition causing a zero return instead of returning 'best value so far'. This can be seen in conjunction with the stack depth problem (before hang) and separately.
Upshot: removed EasyHack markers.

[Markus Mohrhard (moggi)]

Hello Takeshi Abe,

please send all patches to the dev mailing list at <email address hidden> otherwise the patches might get lost. Please add [PATCH] in the subject line.

Now to your patch. I don't like the way you tried to solve it. I think it is better to try to eliminate the underlying problem than moving it a bit further. Your patch will only increase the iterations before the problem arise but will not remove the underlying problem.

Feel free to ask for help on the dev list or on IRC if you need some help.

[Takeshi Abe (tabe-fixedpoint)]

Hi Markus,

Thanks for your suggestion!

(In reply to comment #11)
> please send all patches to the dev mailing list at
> <email address hidden> otherwise the patches might get lost. Please
> add [PATCH] in the subject line.
So is the previous mail
http://lists.freedesktop.org/archives/libreoffice/2011-June/013962.html
not sufficient for that purpose?

>
> Now to your patch. I don't like the way you tried to solve it. I think it is
> better to try to eliminate the underlying problem than moving it a bit further.
The main intension of the patch is to share my observation that the undelying program is not in ScBackSolver but in the iteration process itself, and moreover
we may need so many iterations to reach the sample formula's root.

[Björn Michaelsen (bjoern-michaelsen)]

[This is an automated message.]
There are no new official OpenOffice.org releases in Ubuntu packaging anymore => Won't Fix

If the problem persists, please mark this bug as "also affects project Libreoffice" or "also affects distribution Libreoffice (Ubuntu)" if that has not happened already.

Please leave references to upstream OpenOffice.org bugs in place to allow cross pollination.

[Libreoffice-z (libreoffice-z)]

*** Bug 43693 has been marked as a duplicate of this bug. ***

[Björn Michaelsen (bjoern-michaelsen)]

Is the patch still unapplied? Anyway: Setting status back to NEW until clarified.

[Tbehrens-u (tbehrens-u)]

@kohei, @moggi - any input on how to move this ahead? I notice that easyhack status got lost or removed meanwhile - or can you suggest Takeshi Abe some more directions to look into?

[Winfrieddonkers (winfrieddonkers)]

I confirm problem -as described in comment 3 and comment 4 - still exists on master.

I will look into the code and see if i can find the cause and a fix.

[Winfrieddonkers (winfrieddonkers)]

I also confirm what Takeshi Abe reported, i.e. that the cause is not in ScInterpreter::ScBackSolver(), but in SCFormulaCell::Interpret().

At some point the result is no longer calculated but equal to the previous result, causing an infinite loop in ScBacksolver() since changing the start value does not alter the result.

I'll continue digging (at my own pace, this is not a critical or even blocking bug) and report my progress.

[Winfrieddonkers (winfrieddonkers)]

I have a dirty fix:
The MAXRECURSION (/core/sc/source/core/data/formulacell.cxx) value of 400 is reached; increasing it 'solves' the problem.

However, there will always be a case where the MAXRECURSION value is reached, so a proper handling of this situation is required.
Also, a 'best' value for MAXRECUSION will be arbitrary matter, given that the current value is already arbitrary.

I'll work on a proper fix.

[Winfrieddonkers (winfrieddonkers)]

A proper fix will take some time as the problem is deep inside the code, hidden in a maze of recursive and iterative code.

Also, the chances are that when fixed, calc will no longer hang, but neither give a solution. The reason for this is that in attachment 46880 the formula in every cell depends on the formula-result in other cells. And as the root is searched by starting to calculate the final cell (F110), the goal seeking code has to call itself too often (i.e. for every formula cell a new call is needed).
A more efficient formula (e.g. using TVM-functions) would solve this (and prevent the hanging as long as the problem is not yet fixed).

[Libreoffice-commits (libreoffice-commits)]

Winfried committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=07112a712245bdcca40bb87e2bd118eec9635848

fdo#37341 dix unending loop in calc with Goal Seek

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.

[Kohei-yoshida-w (kohei-yoshida-w)]

Marking this fixed. Good job Winfried!

[Sbergman (sbergman)]

The fix broke JunitTest_sc_unoapi, so I unfortunately had to revert it for now with <http://cgit.freedesktop.org/libreoffice/core/commit/?id=bcbdf6763944dcc53c2667bf829a005ff0b9223a> "Revert 'fdo#37341 dix unending loop in calc with Goal Seek.'"

[Sbergman (sbergman)]

excerpt from workdir/*/JunitTest/sc_unoapi/done.log:

> checking: [sc.ScModelObj::com::sun::star::sheet::XGoalSeek] is iface: [com.sun.star.sheet.XGoalSeek] testcode: [ifc.sheet._XGoalSeek]
> LOG> Execute: seekGoal()
> LOG> Goal Result: 16.0 Divergence: 0.0
> LOG> Goal Result: 9.0 Divergence: 1.7976931348623157E308
> LOG> Goal Result: 0.8 Divergence: 1.7976931348623157E308
> Method seekGoal() finished with state FAILED
> LOG> seekGoal(): PASSED.FAILED

[Libreoffice-commits (libreoffice-commits)]

Stephan Bergmann committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=bcbdf6763944dcc53c2667bf829a005ff0b9223a

Revert "fdo#37341 dix unending loop in calc with Goal Seek"

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.

[Winfrieddonkers (winfrieddonkers)]

Created attachment 83889
calc sheet with the goal seek tests from Junittest_sc_unoapi

I've put the data form the Junittest on a calc sheet, with the outcomes as I would expect them.
Presently, I don know whether the Junittest is wrong, or the patch.

I could add a unittest to core/sc/qa/unit/ucalc.cxx, I'm not familiar with unoapi-tests.

[Winfrieddonkers (winfrieddonkers)]

(In reply to comment #23)
> excerpt from workdir/*/JunitTest/sc_unoapi/done.log:
>
> > checking: [sc.ScModelObj::com::sun::star::sheet::XGoalSeek] is iface: [com.sun.star.sheet.XGoalSeek] testcode: [ifc.sheet._XGoalSeek]
> > LOG> Execute: seekGoal()
> > LOG> Goal Result: 16.0 Divergence: 0.0
> > LOG> Goal Result: 9.0 Divergence: 1.7976931348623157E308
> > LOG> Goal Result: 0.8 Divergence: 1.7976931348623157E308
> > Method seekGoal() finished with state FAILED
> > LOG> seekGoal(): PASSED.FAILED

The java test expects tests 1,2 3 to succeed, fail, succeed. The first 2 tests pass, the 3rd doesn't.

The third test going wrong is a special case. The one 'real' root (1) is invalid because of divide by zero, so goal seek must find the an approximate that give an error within the allowable delta (1E-6 in the case of goal seek).
With a start value of 0, goal seek succeeds, but with a start value of 0.8 (the java test) it does not with the patched code and does succeed with unpatched code.
I will try to trace the goal seek process of the patched code to find out what goes wrong.

[Libreoffice-commits (libreoffice-commits)]

Winfried committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=416d10b5f91047f0dcfbcc233c60322810bfc8d0

fdo#37341 fix unending loop in calc with Goal Seek

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.

[Libreoffice-commits (libreoffice-commits)]

Winfried committed a patch related to this issue.
It has been pushed to "libreoffice-4-1":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=a3cbb8e2526a61a2b10e3663f5971f0441f605a9&h=libreoffice-4-1

fdo#37341 fix unending loop in calc with Goal Seek

It will be available in LibreOffice 4.1.2.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.

[Eike Rathke (erack)]

@Winfried:
Master's 416d10b5f91047f0dcfbcc233c60322810bfc8d0 could be backported to 4-0 as well but additionally to resolving some merge conflicts would also need some adaption as there the ScDocument:GetValueCell() and ScDocument::GetFormulaCell() methods don't exist yet.

[Winfrieddonkers (winfrieddonkers)]

(In reply to comment #29)
> @Winfried:
> Master's 416d10b5f91047f0dcfbcc233c60322810bfc8d0 could be backported to 4-0
> as well but additionally to resolving some merge conflicts would also need
> some adaption as there the ScDocument:GetValueCell() and
> ScDocument::GetFormulaCell() methods don't exist yet.

@Eike,
Thank you for your help (removing the 'dead' bPrevError line and cherry-picking the patch to 4.1)
Given the not so common conditions for this error to ocuur (stack full, i.e. 400 recursive calls to ScInterpreter::Interpret(), I dare leave 4.0 as it is.
Unless of course one or more users ask for it, then I will try to build and patch and commit 4.0.

[Bryan Quigley (bryanquigley)]

This is fixed in Libreoffice 4.1+ (in 14.04, etc).
Closing.