tdf#124270 : improve formula-group cycle detection
When a cycle of formula-groups is detected, do not conclude
that there is a circular dependency of cells. Only mark the
cells with Err:522 when all formula-groups in the cycle have
cleanly backed off from the dependency evaluation mode.
This commit also fixes places where we overlooked to back-off from
dependency evaluation mode on detection of a cycle of formula-groups.
Additionally mark formula-groups with self references as
"part of cycle" by setting mbPartOfCycle.
Unit tests for all these fixes are in a follow-up commit.
Change-Id: I57a88bbc88adf177d49768a5d4585b3e53729aea
Reviewed-on: https://gerrit.libreoffice.org/82074
Reviewed-by: Dennis Francis <dennis.francis@collabora.com>
Tested-by: Dennis Francis <dennis.francis@collabora.com>
diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index 5962f11..cff958f 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -52,6 +52,9 @@ class ScRecursionHelper
ScFormulaRecursionList::iterator aLastIterationStart;
ScRecursionInIterationStack aRecursionInIterationStack;
ScFGList aFGList;
// Flag list corresponding to aFGList to indicate whether each formula-group
// is in a depedency evaluation mode or not.
std::vector< bool > aInDependencyEvalMode;
sal_uInt16 nRecursionCount;
sal_uInt16 nIteration;
// Count of ScFormulaCell::CheckComputeDependencies in current call-stack.
@@ -110,7 +113,9 @@ public:
/** Detects a simple cycle involving formula-groups and singleton formula-cells. */
bool PushFormulaGroup(ScFormulaCell* pCell);
void PopFormulaGroup();
bool AnyCycleMemberInDependencyEvalMode(ScFormulaCell* pCell);
bool AnyParentFGInCycle();
void SetFormulaGroupDepEvalMode(bool bSet);
void AddTemporaryGroupCell(ScFormulaCell* cell);
void CleanTemporaryGroupCells();
diff --git a/sc/source/core/data/column4.cxx b/sc/source/core/data/column4.cxx
index de60329..8e0ae07 100644
--- a/sc/source/core/data/column4.cxx
+++ b/sc/source/core/data/column4.cxx
@@ -1685,7 +1685,17 @@ static bool lcl_InterpretSpan(sc::formula_block::const_iterator& rSpanIter, SCRO
// Evaluate from second cell in non-grouped style (no point in trying group-interpret again).
++itSpanStart;
for (SCROW nIdx = nSpanStart+1; nIdx <= nSpanEnd; ++nIdx, ++itSpanStart)
{
(*itSpanStart)->Interpret(); // We know for sure that this cell is dirty so directly call Interpret().
// Allow early exit like above.
if ((mxParentGroup && mxParentGroup->mbPartOfCycle) || !rRecursionHelper.AreGroupsIndependent())
{
// Set this cell as dirty as this may be interpreted in InterpretTail()
pCellStart->SetDirtyVar();
bAllowThreading = false;
return bAnyDirty;
}
}
}
pCellStart = nullptr; // For next sub span start detection.
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index c2886ed..acfe85b 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -1517,7 +1517,7 @@ bool ScFormulaCell::Interpret(SCROW nStartOffset, SCROW nEndOffset)
ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
bool bGroupInterpreted = false;
if (mxGroup && !rRecursionHelper.CheckFGIndependence(mxGroup.get()))
if ((mxGroup && !rRecursionHelper.CheckFGIndependence(mxGroup.get())) || !rRecursionHelper.AreGroupsIndependent())
return bGroupInterpreted;
static ForceCalculationType forceType = ScCalcConfig::getForceCalculationType();
@@ -1525,12 +1525,15 @@ bool ScFormulaCell::Interpret(SCROW nStartOffset, SCROW nEndOffset)
ScFormulaCell* pTopCell = mxGroup ? mxGroup->mpTopCell : this;
if (pTopCell->mbSeenInPath && rRecursionHelper.GetDepComputeLevel())
if (pTopCell->mbSeenInPath && rRecursionHelper.GetDepComputeLevel() &&
rRecursionHelper.AnyCycleMemberInDependencyEvalMode(pTopCell))
{
// This call arose from a dependency calculation and we just found a cycle.
aResult.SetResultError( FormulaError::CircularReference );
// This will mark all elements in the cycle as parts-of-cycle.
ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, pTopCell);
// Reaching here does not necessarily mean a circular reference, so don't set Err:522 here yet.
// If there is a genuine circular reference, it will be marked so when all groups
// in the cycle get out of dependency evaluation mode.
return bGroupInterpreted;
}
@@ -4547,6 +4550,10 @@ struct ScDependantsCalculator
return false;
}
}
if (bHasSelfReferences)
mxGroup->mbPartOfCycle = true;
return !bHasSelfReferences;
}
};
@@ -4646,7 +4653,10 @@ bool ScFormulaCell::CheckComputeDependencies(sc::FormulaLogger::GroupScope& rSco
// to avoid writing during the calculation
if (bCalcDependencyOnly)
{
ScFormulaGroupDependencyComputeGuard aDepComputeGuard(rRecursionHelper);
// Lets not use "ScFormulaGroupDependencyComputeGuard" here as there is no corresponding
// "ScFormulaGroupCycleCheckGuard" for this formula-group.
// (We can only reach here from a multi-group dependency evaluation attempt).
// (These two have to be in pairs always for any given formula-group)
ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos, fromFirstRow, nStartOffset, nEndOffset);
return aCalculator.DoIt();
}
diff --git a/sc/source/core/tool/recursionhelper.cxx b/sc/source/core/tool/recursionhelper.cxx
index 4bd819a..a13c60e 100644
--- a/sc/source/core/tool/recursionhelper.cxx
+++ b/sc/source/core/tool/recursionhelper.cxx
@@ -134,16 +134,44 @@ bool ScRecursionHelper::PushFormulaGroup(ScFormulaCell* pCell)
pCell->SetSeenInPath(true);
aFGList.push_back(pCell);
aInDependencyEvalMode.push_back(false);
return true;
}
void ScRecursionHelper::PopFormulaGroup()
{
assert(aFGList.size() == aInDependencyEvalMode.size());
if (aFGList.empty())
return;
ScFormulaCell* pCell = aFGList.back();
pCell->SetSeenInPath(false);
aFGList.pop_back();
aInDependencyEvalMode.pop_back();
}
bool ScRecursionHelper::AnyCycleMemberInDependencyEvalMode(ScFormulaCell* pCell)
{
assert(pCell);
if (pCell->GetSeenInPath())
{
// Found a simple cycle of formula-groups.
sal_Int32 nIdx = aFGList.size();
assert(nIdx > 0);
do
{
--nIdx;
assert(nIdx >= 0);
const ScFormulaCellGroupRef& mxGroup = aFGList[nIdx]->GetCellGroup();
// Found a cycle member FG that is in dependency evaluation mode.
if (mxGroup && aInDependencyEvalMode[nIdx])
return true;
} while (aFGList[nIdx] != pCell);
return false;
}
return false;
}
bool ScRecursionHelper::AnyParentFGInCycle()
@@ -159,6 +187,14 @@ bool ScRecursionHelper::AnyParentFGInCycle()
return false;
}
void ScRecursionHelper::SetFormulaGroupDepEvalMode(bool bSet)
{
assert(aFGList.size());
assert(aFGList.size() == aInDependencyEvalMode.size());
assert(aFGList.back()->GetCellGroup());
aInDependencyEvalMode.back() = bSet;
}
void ScRecursionHelper::AddTemporaryGroupCell(ScFormulaCell* cell)
{
aTemporaryGroupCells.push_back( cell );
@@ -207,10 +243,12 @@ ScFormulaGroupDependencyComputeGuard::ScFormulaGroupDependencyComputeGuard(ScRec
mrRecHelper(rRecursionHelper)
{
mrRecHelper.IncDepComputeLevel();
mrRecHelper.SetFormulaGroupDepEvalMode(true);
}
ScFormulaGroupDependencyComputeGuard::~ScFormulaGroupDependencyComputeGuard()
{
mrRecHelper.SetFormulaGroupDepEvalMode(false);
mrRecHelper.DecDepComputeLevel();
}
