[Libreoffice-commits] core.git: sc/source
Winfried
winfrieddonkers at libreoffice.org
Wed Aug 7 17:56:25 PDT 2013
sc/source/core/data/documen4.cxx | 220 +++++++++++++++++++++++++++++++--------
sc/source/core/inc/interpre.hxx | 1
sc/source/core/tool/interpr2.cxx | 198 -----------------------------------
sc/source/core/tool/interpr4.cxx | 1
4 files changed, 179 insertions(+), 241 deletions(-)
New commits:
commit 07112a712245bdcca40bb87e2bd118eec9635848
Author: Winfried <winfrieddonkers at libreoffice.org>
Date: Tue Aug 6 13:08:13 2013 +0200
fdo#37341 dix unending loop in calc with Goal Seek
The combination of a solve process happening in two functions
(ScDocument::Solver() and ScInterpreter::BackSolver) with iterations
and recursive as well as iterative interpreting (ScInterpreter:Interpret()
and ScInterpreter::InterpretTail()) led to improper handling of the
stack, with an unending loop as a result.
Integrating the two solver functions, and so simplifying the code,
results in correct behaviour in all documents attached to the
bug report.
I tested with values for MAXRECURSION of 5 and 400 (standard value)
to have really different combinations of recursion and iteration.
Change-Id: If4cb8926c5e192cd6c764dcdd45a92e285e983bb
Reviewed-on: https://gerrit.libreoffice.org/5292
Reviewed-by: Kohei Yoshida <kohei.yoshida at suse.de>
Tested-by: Kohei Yoshida <kohei.yoshida at suse.de>
diff --git a/sc/source/core/data/documen4.cxx b/sc/source/core/data/documen4.cxx
index 6abc607..308cf89 100644
--- a/sc/source/core/data/documen4.cxx
+++ b/sc/source/core/data/documen4.cxx
@@ -48,18 +48,33 @@
using namespace formula;
// -----------------------------------------------------------------------
+/** (Goal Seek) Find a value of x that is a root of f(x)
-// Nach der Regula Falsi Methode
+ This function is used internally for the goal seek operation. It uses the
+ Regula Falsi (aka false position) algorithm to find a root of f(x). The
+ start value and the target value are to be given by the user in the
+ goal seek dialog. The f(x) in this case is defined as the formula in the
+ formula cell minus target value. This function may also perform additional
+ search in the horizontal directions when the f(x) is discrete in order to
+ ensure a non-zero slope necessary for deriving a subsequent x that is
+ reasonably close to the root of interest.
+
+ @change 24.10.2004 by Kohei Yoshida (kohei at openoffice.org)
+
+ @see #i28955#
+
+ @change 6 Aug 2013, fdo37341
+*/
bool ScDocument::Solver(SCCOL nFCol, SCROW nFRow, SCTAB nFTab,
SCCOL nVCol, SCROW nVRow, SCTAB nVTab,
const OUString& sValStr, double& nX)
{
bool bRet = false;
nX = 0.0;
- if (ValidColRow(nFCol, nFRow) && ValidColRow(nVCol, nVRow) &&
- ValidTab(nFTab) && ValidTab(nVTab) &&
- nFTab < static_cast<SCTAB>(maTabs.size()) && maTabs[nFTab] &&
- nVTab < static_cast<SCTAB>(maTabs.size()) && maTabs[nVTab])
+ if ( ValidColRow( nFCol, nFRow ) && ValidTab( nFTab ) &&
+ ValidColRow( nVCol, nVRow ) && ValidTab( nVTab ) &&
+ nFTab < static_cast<SCTAB>( maTabs.size() ) && maTabs[nFTab] &&
+ nVTab < static_cast<SCTAB>( maTabs.size() ) && maTabs[nVTab] )
{
CellType eFType, eVType;
GetCellType(nFCol, nFRow, nFTab, eFType);
@@ -67,46 +82,169 @@ bool ScDocument::Solver(SCCOL nFCol, SCROW nFRow, SCTAB nFTab,
// CELLTYPE_NOTE: no value, but referenced by formula
// #i108005# convert target value to number using default format,
// as previously done in ScInterpreter::GetDouble
- double nTargetVal = 0.0;
+ double fTargetVal = 0.0;
sal_uInt32 nFIndex = 0;
- if (eFType == CELLTYPE_FORMULA && (eVType == CELLTYPE_VALUE) &&
- GetFormatTable()->IsNumberFormat(sValStr, nFIndex, nTargetVal))
+ if ( eFType == CELLTYPE_FORMULA && eVType == CELLTYPE_VALUE &&
+ GetFormatTable()->IsNumberFormat( sValStr, nFIndex, fTargetVal ) )
{
- ScSingleRefData aRefData;
- aRefData.InitFlags();
- aRefData.SetAbsCol(nVCol);
- aRefData.SetAbsRow(nVRow);
- aRefData.SetAbsTab(nVTab);
-
- ScTokenArray aArr;
- aArr.AddOpCode( ocBackSolver );
- aArr.AddOpCode( ocOpen );
- aArr.AddSingleReference( aRefData );
- aArr.AddOpCode( ocSep );
-
- aRefData.SetAbsCol(nFCol);
- aRefData.SetAbsRow(nFRow);
- aRefData.SetAbsTab(nFTab);
-
- aArr.AddSingleReference( aRefData );
- aArr.AddOpCode( ocSep );
- aArr.AddDouble( nTargetVal );
- aArr.AddOpCode( ocClose );
- aArr.AddOpCode( ocStop );
-
- ScFormulaCell* pCell = new ScFormulaCell( this, ScAddress(), &aArr );
-
- if (pCell)
+ bool bDoneIteration = false;
+ ScAddress aValueAdr( nVCol, nVRow, nVTab );
+ ScAddress aFormulaAdr( nFCol, nFRow, nFTab );
+ double* pVCell = GetValueCell( aValueAdr );
+
+ ScRange aVRange( aValueAdr, aValueAdr ); // for SetDirty
+ // Original value to be restored later if necessary
+ double fSaveVal = *pVCell;
+
+ const sal_uInt16 nMaxIter = 100;
+ const double fEps = 1E-10;
+ const double fDelta = 1E-6;
+
+ double fBestX, fXPrev;
+ double fBestF, fFPrev;
+ fBestX = fXPrev = fSaveVal;
+
+ ScFormulaCell* pFormula = GetFormulaCell( aFormulaAdr );
+ pFormula->Interpret();
+ bool bError = ( pFormula->GetErrCode() != 0 );
+ // bError always corresponds with fF
+
+ fFPrev = pFormula->GetValue() - fTargetVal;
+
+ fBestF = fabs( fFPrev );
+ if ( fBestF < fDelta )
+ bDoneIteration = true;
+
+ double fX = fXPrev + fEps;
+ double fF = fFPrev;
+ double fSlope;
+
+ sal_uInt16 nIter = 0;
+
+ bool bHorMoveError = false;
+ // Conform Regula Falsi Method
+ while ( !bDoneIteration && ( nIter++ < nMaxIter ) && !bError )
+ {
+ *pVCell = fX;
+ SetDirty( aVRange );
+ pFormula->Interpret();
+ bError = ( pFormula->GetErrCode() != 0 );
+ fF = pFormula->GetValue() - fTargetVal;
+
+ if ( fF == fFPrev && !bError )
+ {
+ // HORIZONTAL SEARCH: Keep moving x in both directions until the f(x)
+ // becomes different from the previous f(x). This routine is needed
+ // when a given function is discrete, in which case the resulting slope
+ // may become zero which ultimately causes the goal seek operation
+ // to fail. #i28955#
+
+ sal_uInt16 nHorIter = 0;
+ const double fHorStepAngle = 5.0;
+ const double fHorMaxAngle = 80.0;
+ int nHorMaxIter = static_cast<int>( fHorMaxAngle / fHorStepAngle );
+ bool bDoneHorMove = false;
+
+ while ( !bDoneHorMove && !bHorMoveError && nHorIter++ < nHorMaxIter )
+ {
+ double fHorAngle = fHorStepAngle * static_cast<double>( nHorIter );
+ double fHorTangent = ::rtl::math::tan( fHorAngle * F_PI / 180 );
+
+ sal_uInt16 nIdx = 0;
+ while( nIdx++ < 2 && !bDoneHorMove )
+ {
+ double fHorX;
+ if ( nIdx == 1 )
+ fHorX = fX + fabs( fF ) * fHorTangent;
+ else
+ fHorX = fX - fabs( fF ) * fHorTangent;
+
+ *pVCell = fHorX;
+ SetDirty( aVRange );
+ pFormula->Interpret();
+ bHorMoveError = ( pFormula->GetErrCode() != 0 );
+ if ( bHorMoveError )
+ break;
+
+ fF = pFormula->GetValue() - fTargetVal;
+ if ( fF != fFPrev )
+ {
+ fX = fHorX;
+ bDoneHorMove = true;
+ }
+ }
+ }
+ if ( !bDoneHorMove )
+ bHorMoveError = true;
+ }
+
+ if ( bError )
+ {
+ // move closer to last valid value (fXPrev), keep fXPrev & fFPrev
+ double fDiff = ( fXPrev - fX ) / 2;
+ if ( fabs( fDiff ) < fEps )
+ fDiff = ( fDiff < 0.0 ? - fEps : fEps );
+ fX += fDiff;
+ }
+ else if ( bHorMoveError )
+ break;
+ else if ( fabs(fF) < fDelta )
+ {
+ // converged to root
+ fBestX = fX;
+ bDoneIteration = true;
+ }
+ else
+ {
+ if ( fabs(fF) + fDelta < fBestF )
+ {
+ fBestX = fX;
+ fBestF = fabs( fF );
+ }
+
+ if ( ( fXPrev - fX ) != 0 )
+ {
+ fSlope = ( fFPrev - fF ) / ( fXPrev - fX );
+ if ( fabs( fSlope ) < fEps )
+ fSlope = fSlope < 0.0 ? -fEps : fEps;
+ }
+ else
+ fSlope = fEps;
+
+ fXPrev = fX;
+ fFPrev = fF;
+ fX = fX - ( fF / fSlope );
+ }
+ }
+
+ // Try a nice rounded input value if possible.
+ const double fNiceDelta = ( bDoneIteration && fabs( fBestX ) >= 1e-3 ? 1e-3 : fDelta );
+ nX = ::rtl::math::approxFloor( ( fBestX / fNiceDelta ) + 0.5 ) * fNiceDelta;
+
+ if ( bDoneIteration )
+ {
+ *pVCell = nX;
+ SetDirty( aVRange );
+ pFormula->Interpret();
+ if ( fabs( pFormula->GetValue() - fTargetVal ) > fabs( fF ) )
+ nX = fBestX;
+ bRet = true;
+ }
+ else if ( bError || bHorMoveError )
{
- // FIXME FIXME FIXME this might need to be reworked now that we have formula::FormulaErrorToken and ScFormulaResult, double check !!!
- OSL_FAIL("ScDocument::Solver: -> ScFormulaCell::GetValueAlways might need reimplementation");
- pCell->Interpret();
- sal_uInt16 nErrCode = pCell->GetErrCode();
- nX = pCell->GetValueAlways();
- if (nErrCode == 0) // kein fehler beim Rechnen
- bRet = true;
- delete pCell;
+ nX = fBestX;
}
+ *pVCell = fSaveVal;
+ SetDirty( aVRange );
+ pFormula->Interpret();
+ if ( !bDoneIteration )
+ {
+ SetError( nVCol, nVRow, nVTab, NOTAVAILABLE );
+ }
+ }
+ else
+ {
+ SetError( nVCol, nVRow, nVTab, NOTAVAILABLE );
}
}
return bRet;
diff --git a/sc/source/core/inc/interpre.hxx b/sc/source/core/inc/interpre.hxx
index 3792383..8cf87b0 100644
--- a/sc/source/core/inc/interpre.hxx
+++ b/sc/source/core/inc/interpre.hxx
@@ -649,7 +649,6 @@ void ScKumKapZ();
void ScEffektiv();
void ScNominal();
void ScMod();
-void ScBackSolver();
void ScIntercept();
double ScGetGCD(double fx, double fy);
void ScGCD();
diff --git a/sc/source/core/tool/interpr2.cxx b/sc/source/core/tool/interpr2.cxx
index f5a841e..85e9ed0 100644
--- a/sc/source/core/tool/interpr2.cxx
+++ b/sc/source/core/tool/interpr2.cxx
@@ -1695,204 +1695,6 @@ void ScInterpreter::ScMod()
}
}
-/** (Goal Seek) Find a value of x that is a root of f(x)
-
- This function is used internally for the goal seek operation. It uses the
- Regula Falsi (aka false position) algorithm to find a root of f(x). The
- start value and the target value are to be given by the user in the
- goal seek dialog. The f(x) in this case is defined as the formula in the
- formula cell minus target value. This function may also perform additional
- search in the horizontal directions when the f(x) is discrete in order to
- ensure a non-zero slope necessary for deriving a subsequent x that is
- reasonably close to the root of interest.
-
- @change 24.10.2004 by Kohei Yoshida (kohei at openoffice.org)
-
- @see #i28955#
-*/
-void ScInterpreter::ScBackSolver()
-{
- if ( MustHaveParamCount( GetByte(), 3 ) )
- {
- bool bDoneIteration = false;
- ScAddress aValueAdr, aFormulaAdr;
- double fTargetVal = GetDouble();
- PopSingleRef( aFormulaAdr );
- PopSingleRef( aValueAdr );
-
- if (nGlobalError == 0)
- {
- ScRefCellValue aFCell;
- double* pVCell = pDok->GetValueCell(aValueAdr);
- aFCell.assign(*pDok, aFormulaAdr);
-
- if (pVCell && aFCell.meType == CELLTYPE_FORMULA)
- {
- ScRange aVRange( aValueAdr, aValueAdr ); // fuer SetDirty
- // Original value to be restored later if necessary
- double fSaveVal = *pVCell;
-
- const sal_uInt16 nMaxIter = 100;
- const double fEps = 1E-10;
- const double fDelta = 1E-6;
-
- double fBestX, fXPrev;
- double fBestF, fFPrev;
- fBestX = fXPrev = fSaveVal;
-
- ScFormulaCell* pFormula = aFCell.mpFormula;
-
- pFormula->Interpret();
- bool bError = ( pFormula->GetErrCode() != 0 );
- // bError always corresponds with fF
-
- fFPrev = pFormula->GetValue() - fTargetVal;
-
- fBestF = fabs( fFPrev );
- if ( fBestF < fDelta )
- bDoneIteration = true;
-
- double fX = fXPrev + fEps;
- double fF = fFPrev;
- double fSlope;
-
- sal_uInt16 nIter = 0;
-
- bool bHorMoveError = false;
- // Nach der Regula Falsi Methode
- while ( !bDoneIteration && ( nIter++ < nMaxIter ) )
- {
- *pVCell = fX;
- pDok->SetDirty( aVRange );
- pFormula->Interpret();
- bError = ( pFormula->GetErrCode() != 0 );
- fF = pFormula->GetValue() - fTargetVal;
-
- if ( fF == fFPrev && !bError )
- {
- // HORIZONTAL SEARCH: Keep moving x in both directions until the f(x)
- // becomes different from the previous f(x). This routine is needed
- // when a given function is discrete, in which case the resulting slope
- // may become zero which ultimately causes the goal seek operation
- // to fail. #i28955#
-
- sal_uInt16 nHorIter = 0;
- const double fHorStepAngle = 5.0;
- const double fHorMaxAngle = 80.0;
- int nHorMaxIter = static_cast<int>( fHorMaxAngle / fHorStepAngle );
- bool bDoneHorMove = false;
-
- while ( !bDoneHorMove && !bHorMoveError && nHorIter++ < nHorMaxIter )
- {
- double fHorAngle = fHorStepAngle * static_cast<double>( nHorIter );
- double fHorTangent = ::rtl::math::tan( fHorAngle * F_PI / 180 );
-
- sal_uInt16 nIdx = 0;
- while( nIdx++ < 2 && !bDoneHorMove )
- {
- double fHorX;
- if ( nIdx == 1 )
- fHorX = fX + fabs(fF)*fHorTangent;
- else
- fHorX = fX - fabs(fF)*fHorTangent;
-
- *pVCell = fHorX;
- pDok->SetDirty( aVRange );
- pFormula->Interpret();
- bHorMoveError = ( pFormula->GetErrCode() != 0 );
- if ( bHorMoveError )
- break;
-
- fF = pFormula->GetValue() - fTargetVal;
- if ( fF != fFPrev )
- {
- fX = fHorX;
- bDoneHorMove = true;
- }
- }
- }
- if ( !bDoneHorMove )
- bHorMoveError = true;
- }
-
- if ( bError )
- {
- // move closer to last valid value (fXPrev), keep fXPrev & fFPrev
- double fDiff = ( fXPrev - fX ) / 2;
- if (fabs(fDiff) < fEps)
- fDiff = (fDiff < 0.0) ? - fEps : fEps;
- fX += fDiff;
- }
- else if ( bHorMoveError )
- break;
- else if ( fabs(fF) < fDelta )
- {
- // converged to root
- fBestX = fX;
- bDoneIteration = true;
- }
- else
- {
- if ( fabs(fF) + fDelta < fBestF )
- {
- fBestX = fX;
- fBestF = fabs(fF);
- }
-
- if ( ( fXPrev - fX ) != 0 )
- {
- fSlope = ( fFPrev - fF ) / ( fXPrev - fX );
- if ( fabs( fSlope ) < fEps )
- fSlope = fSlope < 0.0 ? -fEps : fEps;
- }
- else
- fSlope = fEps;
-
- fXPrev = fX;
- fFPrev = fF;
- fX = fX - ( fF / fSlope );
- }
- }
-
- // Try a nice rounded input value if possible.
- const double fNiceDelta = (bDoneIteration && fabs(fBestX) >= 1e-3 ? 1e-3 : fDelta);
- double nX = ::rtl::math::approxFloor((fBestX / fNiceDelta) + 0.5) * fNiceDelta;
-
- if ( bDoneIteration )
- {
- *pVCell = nX;
- pDok->SetDirty( aVRange );
- pFormula->Interpret();
- if ( fabs( pFormula->GetValue() - fTargetVal ) > fabs( fF ) )
- nX = fBestX;
- }
- else if ( bError || bHorMoveError )
- {
- nX = fBestX;
- }
- *pVCell = fSaveVal;
- pDok->SetDirty( aVRange );
- pFormula->Interpret();
- if ( !bDoneIteration )
- SetError(NOTAVAILABLE);
- PushDouble(nX);
- }
- else
- {
- if ( !bDoneIteration )
- SetError(NOTAVAILABLE);
- PushInt(0); // falsche Zelltypen
- }
- }
- else
- {
- if ( !bDoneIteration )
- SetError(NOTAVAILABLE);
- PushInt(0); // nGlobalError
- }
- }
-}
-
void ScInterpreter::ScIntersect()
{
formula::FormulaTokenRef p2nd = PopToken();
diff --git a/sc/source/core/tool/interpr4.cxx b/sc/source/core/tool/interpr4.cxx
index e211d99..c6025d4 100644
--- a/sc/source/core/tool/interpr4.cxx
+++ b/sc/source/core/tool/interpr4.cxx
@@ -4009,7 +4009,6 @@ StackVar ScInterpreter::Interpret()
case ocMatMult : ScMatMult(); break;
case ocMatTrans : ScMatTrans(); break;
case ocMatRef : ScMatRef(); break;
- case ocBackSolver : ScBackSolver(); break;
case ocB : ScB(); break;
case ocNormDist : ScNormDist(); break;
case ocExpDist : ScExpDist(); break;
More information about the Libreoffice-commits
mailing list