Bug Hunting Session
Bug 37341 - Goal Seek hangs indefinitely for too many calculation steps (Formula Cell $F$110)
Summary: Goal Seek hangs indefinitely for too many calculation steps (Formula Cell $F$...
Status: RESOLVED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
3.4.0 Beta5
Hardware: x86 (IA32) All
: medium normal
Assignee: Winfried Donkers (retired)
URL:
Whiteboard: target:4.2.0 target:4.1.2 target:6.2.0
Keywords:
: 43693 (view as bug list)
Depends on:
Blocks: GoalSeek
  Show dependency treegraph
 
Reported: 2011-05-18 19:16 UTC by Christopher M. Penalver
Modified: 2018-06-20 19:38 UTC (History)
11 users (show)

See Also:
Crash report or crash signature:


Attachments
sample.ods (27.95 KB, application/vnd.oasis.opendocument.spreadsheet)
2011-05-18 19:16 UTC, Christopher M. Penalver
Details
Sample Document, see Comment 5 (27.95 KB, application/vnd.oasis.opendocument.spreadsheet)
2011-05-18 23:28 UTC, Rainer Bielefeld Retired
Details
an experimental fix against master (871 bytes, patch)
2011-06-19 08:27 UTC, Takeshi Abe
Details
Simpler example of using GoalSeek to find fixed payment for loan (74.09 KB, application/vnd.oasis.opendocument.spreadsheet)
2011-06-20 10:58 UTC, LeMoyne Castle
Details
calc sheet with the goal seek tests from Junittest_sc_unoapi (8.23 KB, application/vnd.oasis.opendocument.spreadsheet)
2013-08-09 11:03 UTC, Winfried Donkers (retired)
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Christopher M. Penalver 2011-05-18 19:16:15 UTC
Created attachment 46880 [details]
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).
Comment 1 Markus Mohrhard 2011-05-18 19:35:55 UTC
Not reproducible with LibreOffice 3.4RC1 at Linux x64.
Comment 2 Christopher M. Penalver 2011-05-18 20:08:03 UTC
Formula Cell $F$100 should actually be $F$110. Reproducible in LibreOffice 3.4.0 DEV300m103(Build:5).
Comment 3 Rainer Bielefeld Retired 2011-05-18 22:30:22 UTC
[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
Comment 4 Rainer Bielefeld Retired 2011-05-18 22:54:44 UTC
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!
Comment 5 Rainer Bielefeld Retired 2011-05-18 23:27:13 UTC
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.
Comment 6 Rainer Bielefeld Retired 2011-05-18 23:28:55 UTC
Created attachment 46887 [details]
Sample Document, see Comment 5
Comment 7 Kohei Yoshida 2011-05-20 23:10:17 UTC
I'll make this an EasyHack.

Code pointer: ScInterpreter::ScBackSolver() in sc/source/core/tool/interpr2.cxx implements the goal seek algorithm.
Comment 8 LeMoyne Castle 2011-06-17 10:20:24 UTC
Completed EasyHack markers
Comment 9 Takeshi Abe 2011-06-19 08:27:04 UTC
Created attachment 48162 [details]
an experimental fix against master

Let me attach an experimental fix against master, which makes
the depth of recursion lavish.
Comment 10 LeMoyne Castle 2011-06-20 10:58:07 UTC
Created attachment 48199 [details]
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.
Comment 11 Markus Mohrhard 2011-06-24 12:24:54 UTC
Hello Takeshi Abe,

please send all patches to the dev mailing list at libreoffice@lists.freedesktop.org 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.
Comment 12 Takeshi Abe 2011-06-24 21:22:15 UTC
Hi Markus,

Thanks for your suggestion!

(In reply to comment #11)
> please send all patches to the dev mailing list at
> libreoffice@lists.freedesktop.org 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.
Comment 13 Rainer Bielefeld Retired 2011-12-19 22:02:55 UTC
*** Bug 43693 has been marked as a duplicate of this bug. ***
Comment 14 Björn Michaelsen 2011-12-23 18:13:14 UTC
Is the patch still unapplied? Anyway: Setting status back to NEW until clarified.
Comment 15 Thorsten Behrens (CIB) 2012-07-25 18:55:51 UTC
@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?
Comment 16 Winfried Donkers (retired) 2013-07-05 07:30:08 UTC
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.
Comment 17 Winfried Donkers (retired) 2013-07-09 15:18:15 UTC
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.
Comment 18 Winfried Donkers (retired) 2013-07-10 07:02:11 UTC
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.
Comment 19 Winfried Donkers (retired) 2013-08-01 11:55:18 UTC
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 [details] 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).
Comment 20 Commit Notification 2013-08-08 01:00:37 UTC
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.
Comment 21 Kohei Yoshida 2013-08-08 01:02:46 UTC
Marking this fixed.  Good job Winfried!
Comment 22 Stephan Bergmann 2013-08-09 08:57:47 UTC
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.'"
Comment 23 Stephan Bergmann 2013-08-09 09:00:40 UTC
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
Comment 24 Commit Notification 2013-08-09 09:03:24 UTC
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.
Comment 25 Winfried Donkers (retired) 2013-08-09 11:03:24 UTC
Created attachment 83889 [details]
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.
Comment 26 Winfried Donkers (retired) 2013-08-12 06:02:43 UTC
(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.
Comment 27 Commit Notification 2013-08-12 20:26:09 UTC
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.
Comment 28 Commit Notification 2013-08-12 20:35:53 UTC
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.
Comment 29 Eike Rathke 2013-08-12 20:55:39 UTC
@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.
Comment 30 Winfried Donkers (retired) 2013-08-13 05:32:40 UTC
(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.
Comment 31 Commit Notification 2018-06-20 19:38:20 UTC
Zdeněk Crhonek committed a patch related to this issue.
It has been pushed to "master":

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

uitest Calc/Goal seek; tdf#37341 ; tdf#43693

It will be available in 6.2.0.

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.