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).
Not reproducible with LibreOffice 3.4RC1 at Linux x64.
Formula Cell $F$100 should actually be $F$110. Reproducible in LibreOffice 3.4.0 DEV300m103(Build:5).
[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
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!
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.
Created attachment 46887 [details] Sample Document, see Comment 5
I'll make this an EasyHack. Code pointer: ScInterpreter::ScBackSolver() in sc/source/core/tool/interpr2.cxx implements the goal seek algorithm.
Completed EasyHack markers
Created attachment 48162 [details] an experimental fix against master Let me attach an experimental fix against master, which makes the depth of recursion lavish.
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.
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.
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.
*** Bug 43693 has been marked as a duplicate of this bug. ***
Is the patch still unapplied? Anyway: Setting status back to NEW until clarified.
@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?
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.
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.
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.
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).
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.
Marking this fixed. Good job Winfried!
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.'"
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
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.
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.
(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.
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.
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.
@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.
(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.
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.
The test exist, set status to Verified.