[Libreoffice-commits] core.git: sc/inc sc/source
Dennis Francis
dennis.francis at collabora.co.uk
Fri Jul 6 12:11:19 UTC 2018
sc/inc/formulacell.hxx | 4 +
sc/inc/recursionhelper.hxx | 24 ++++++++--
sc/source/core/data/column2.cxx | 18 +++++++
sc/source/core/data/formulacell.cxx | 74 ++++++++++++++++++++++++--------
sc/source/core/tool/recursionhelper.cxx | 67 +++++++++++++++++++++++-----
5 files changed, 152 insertions(+), 35 deletions(-)
New commits:
commit 24afa5ddbecf54b545b6ff966af1521b8c1b8984
Author: Dennis Francis <dennis.francis at collabora.co.uk>
Date: Fri Jul 6 04:37:01 2018 +0530
Generalize FG cycle detection for...
...cycles involving a mix of formula-groups and plain
formula-cells which are not grouped.
This fixes a crash in tdf#104213/1
Change-Id: I63b8b7379e4e5eaf322a3318f061a9e5fbc931ef
Reviewed-on: https://gerrit.libreoffice.org/57031
Tested-by: Jenkins
Reviewed-by: Michael Meeks <michael.meeks at collabora.com>
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index a9df1a3be625..34c578076d97 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -67,7 +67,6 @@ public:
SvNumFormatType mnFormatType;
bool mbInvariant:1;
bool mbSubTotal:1;
- bool mbSeenInPath:1; // For detecting cycle of formula groups
bool mbPartOfCycle:1; // To flag FG's part of a cycle
sal_uInt8 meCalcState;
@@ -134,6 +133,7 @@ private:
number formats as hard number format */
bool mbPostponedDirty : 1; // if cell needs to be set dirty later
bool mbIsExtRef : 1; // has references in ScExternalRefManager; never cleared after set
+ bool mbSeenInPath : 1; // For detecting cycle involving formula groups and singleton formulacells
/**
* Update reference in response to cell copy-n-paste.
@@ -453,6 +453,8 @@ public:
bool IsPostponedDirty() const { return mbPostponedDirty;}
void SetIsExtRef() { mbIsExtRef = true; }
+ bool GetSeenInPath() { return mbSeenInPath; }
+ void SetSeenInPath(bool bSet) { mbSeenInPath = bSet; }
#if DUMP_COLUMN_STORAGE
void Dump() const;
diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index 030e52c04b7c..b2d21daa378b 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -46,7 +46,7 @@ typedef ::std::list< ScFormulaRecursionEntry > ScFormulaRecursionList;
class ScRecursionHelper
{
typedef ::std::stack< ScFormulaCell* > ScRecursionInIterationStack;
- typedef ::std::vector< ScFormulaCellGroup* > ScFGList;
+ typedef ::std::vector< ScFormulaCell* > ScFGList;
ScFormulaRecursionList aRecursionFormulas;
ScFormulaRecursionList::iterator aInsertPos;
ScFormulaRecursionList::iterator aLastIterationStart;
@@ -54,6 +54,8 @@ class ScRecursionHelper
ScFGList aFGList;
sal_uInt16 nRecursionCount;
sal_uInt16 nIteration;
+ // Count of ScFormulaCell::CheckComputeDependencies in current call-stack.
+ sal_uInt16 nDependencyComputationLevel;
bool bInRecursionReturn;
bool bDoingRecursion;
bool bInIterationReturn;
@@ -68,6 +70,9 @@ public:
sal_uInt16 GetRecursionCount() const { return nRecursionCount; }
void IncRecursionCount() { ++nRecursionCount; }
void DecRecursionCount() { --nRecursionCount; }
+ sal_uInt16 GetDepComputeLevel() { return nDependencyComputationLevel; }
+ void IncDepComputeLevel() { ++nDependencyComputationLevel; }
+ void DecDepComputeLevel() { --nDependencyComputationLevel; }
/// A pure recursion return, no iteration.
bool IsInRecursionReturn() const { return bInRecursionReturn &&
!bInIterationReturn; }
@@ -99,9 +104,10 @@ public:
void Clear();
- /** Detects whether the formula-group is part of a simple cycle of formula-groups. */
- bool PushFormulaGroup(ScFormulaCellGroup* pGrp);
+ /** Detects a simple cycle involving formula-groups and singleton formula-cells. */
+ bool PushFormulaGroup(ScFormulaCell* pCell);
void PopFormulaGroup();
+ bool AnyParentFGInCycle();
};
/** A class to wrap ScRecursionHelper::PushFormulaGroup(),
@@ -113,8 +119,18 @@ class ScFormulaGroupCycleCheckGuard
bool mbShouldPop;
public:
ScFormulaGroupCycleCheckGuard() = delete;
- ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCellGroup* pGrp);
+ ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCell* pCell);
~ScFormulaGroupCycleCheckGuard();
+
+};
+
+class ScFormulaGroupDependencyComputeGuard
+{
+ ScRecursionHelper& mrRecHelper;
+public:
+ ScFormulaGroupDependencyComputeGuard() = delete;
+ ScFormulaGroupDependencyComputeGuard(ScRecursionHelper& rRecursionHelper);
+ ~ScFormulaGroupDependencyComputeGuard();
};
#endif // INCLUDED_SC_INC_RECURSIONHELPER_HXX
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 5ef16b9bf2c6..21f38f54711d 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -2855,16 +2855,32 @@ bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2, const ScF
size_t nEnd = std::min(it->size, nOffset+nRowsToRead); // last row + 1
sc::formula_block::const_iterator itCell = sc::formula_block::begin(*it->data);
std::advance(itCell, nOffset);
+ // Loop inside the formula block.
for (size_t i = nOffset; i < nEnd; ++itCell, ++i)
{
- // Loop inside the formula block.
+ // Check if itCell is already in path.
+ // If yes use a cycle guard to mark all elements of the cycle
+ // and return false
+ const ScFormulaCellGroupRef& mxGroupChild = (*itCell)->GetCellGroup();
+ ScFormulaCell* pChildTopCell = mxGroupChild ? mxGroupChild->mpTopCell : *itCell;
+ if (pChildTopCell->GetSeenInPath())
+ {
+ ScRecursionHelper& rRecursionHelper = GetDoc()->GetRecursionHelper();
+ ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, pChildTopCell);
+ return false;
+ }
+
(*itCell)->MaybeInterpret();
// child cell's Interpret could result in calling dependency calc
// and that could detect a cycle involving mxGroup
// and do early exit in that case.
if (mxGroup->mbPartOfCycle)
+ {
+ // Set itCell as dirty as itCell may be interpreted in InterpretTail()
+ (*itCell)->SetDirtyVar();
return false;
+ }
}
nRow += nEnd - nOffset;
break;
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index 5c79b1780adb..e370deaacb6c 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -526,7 +526,6 @@ ScFormulaCellGroup::ScFormulaCellGroup() :
mnFormatType(SvNumFormatType::NUMBER),
mbInvariant(false),
mbSubTotal(false),
- mbSeenInPath(false),
mbPartOfCycle(false),
meCalcState(sc::GroupCalcEnabled)
{
@@ -628,6 +627,7 @@ ScFormulaCell::ScFormulaCell( ScDocument* pDoc, const ScAddress& rPos ) :
mbAllowNumberFormatChange(false),
mbPostponedDirty(false),
mbIsExtRef(false),
+ mbSeenInPath(false),
aPos(rPos)
{
}
@@ -659,6 +659,7 @@ ScFormulaCell::ScFormulaCell( ScDocument* pDoc, const ScAddress& rPos,
mbAllowNumberFormatChange(false),
mbPostponedDirty(false),
mbIsExtRef(false),
+ mbSeenInPath(false),
aPos(rPos)
{
Compile( rFormula, true, eGrammar ); // bNoListening, Insert does that
@@ -693,6 +694,7 @@ ScFormulaCell::ScFormulaCell(
mbAllowNumberFormatChange(false),
mbPostponedDirty(false),
mbIsExtRef(false),
+ mbSeenInPath(false),
aPos(rPos)
{
assert(pArray); // Never pass a NULL pointer here.
@@ -742,6 +744,7 @@ ScFormulaCell::ScFormulaCell(
mbAllowNumberFormatChange(false),
mbPostponedDirty(false),
mbIsExtRef(false),
+ mbSeenInPath(false),
aPos(rPos)
{
// RPN array generation
@@ -790,6 +793,7 @@ ScFormulaCell::ScFormulaCell(
mbAllowNumberFormatChange(false),
mbPostponedDirty(false),
mbIsExtRef(false),
+ mbSeenInPath(false),
aPos(rPos)
{
if (bSubTotal)
@@ -821,6 +825,7 @@ ScFormulaCell::ScFormulaCell(const ScFormulaCell& rCell, ScDocument& rDoc, const
mbAllowNumberFormatChange(false),
mbPostponedDirty(false),
mbIsExtRef(false),
+ mbSeenInPath(false),
aPos(rPos)
{
pCode = rCell.pCode->Clone();
@@ -1474,12 +1479,11 @@ void ScFormulaCell::Interpret()
{
ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
- if (mxGroup && mxGroup->mbSeenInPath)
+ ScFormulaCell* pTopCell = mxGroup ? mxGroup->mpTopCell : this;
+
+ if (pTopCell->mbSeenInPath && rRecursionHelper.GetDepComputeLevel())
{
- // This call arose from a dependency calculation and
- // we just found a cycle.
- // This will mark all elements in the cycle as parts-of-cycle
- ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, mxGroup.get());
+ ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, pTopCell);
return;
}
@@ -1541,15 +1545,25 @@ void ScFormulaCell::Interpret()
#if DEBUG_CALCULATION
aDC.enterGroup();
#endif
-
+ bool bPartOfCycleBefore = mxGroup && mxGroup->mbPartOfCycle;
bool bGroupInterpreted = InterpretFormulaGroup();
+ bool bPartOfCycleAfter = mxGroup && mxGroup->mbPartOfCycle;
#if DEBUG_CALCULATION
aDC.leaveGroup();
#endif
if (!bGroupInterpreted)
{
- ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, mxGroup.get());
+ // Dependency calc inside InterpretFormulaGroup() failed due to
+ // detection of a cycle and there are parent FG's in the cycle.
+ // Skip InterpretTail() in such cases, only run InterpretTail for the "cycle-starting" FG
+ if (!bPartOfCycleBefore && bPartOfCycleAfter && rRecursionHelper.AnyParentFGInCycle())
+ {
+ pDocument->DecInterpretLevel();
+ return;
+ }
+
+ ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, this);
InterpretTail( pDocument->GetNonThreadedContext(), SCITP_NORMAL);
}
@@ -4331,6 +4345,7 @@ struct ScDependantsCalculator
// Partially from ScGroupTokenConverter::convert in sc/source/core/data/grouptokenconverter.cxx
ScRangeList aRangeList;
+ bool bHasSelfReferences = false;
for (auto p: mrCode.RPNTokens())
{
switch (p->GetType())
@@ -4346,7 +4361,10 @@ struct ScDependantsCalculator
if (aRef.IsRowRel())
{
if (isSelfReferenceRelative(aRefPos, aRef.Row()))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
// Trim data array length to actual data range.
SCROW nTrimLen = trimLength(aRefPos.Tab(), aRefPos.Col(), aRefPos.Col(), aRefPos.Row(), mnLen);
@@ -4357,7 +4375,10 @@ struct ScDependantsCalculator
else
{
if (isSelfReferenceAbsolute(aRefPos))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
aRangeList.Join(ScRange(aRefPos.Col(), aRefPos.Row(), aRefPos.Tab()));
}
@@ -4377,22 +4398,37 @@ struct ScDependantsCalculator
if (bIsRef1RowRel)
{
if (isSelfReferenceRelative(aAbs.aStart, aRef.Ref1.Row()))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
}
else if (isSelfReferenceAbsolute(aAbs.aStart))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
bool bIsRef2RowRel = aRef.Ref2.IsRowRel();
if (bIsRef2RowRel)
{
if (isSelfReferenceRelative(aAbs.aEnd, aRef.Ref2.Row()))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
}
else if (isSelfReferenceAbsolute(aAbs.aEnd))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
if (isDoubleRefSpanGroupRange(aAbs, bIsRef1RowRel, bIsRef2RowRel))
- return false;
+ {
+ bHasSelfReferences = true;
+ continue;
+ }
// Row reference is relative.
bool bAbsLast = !aRef.Ref2.IsRowRel();
@@ -4421,6 +4457,9 @@ struct ScDependantsCalculator
}
}
+ // Compute dependencies irrespective of the presence of any self references.
+ // These dependencies would get computed via InterpretTail anyway when we disable group calc, so lets do it now.
+ // The advantage is that the FG's get marked for cycles early if present, and can avoid lots of complications.
for (size_t i = 0; i < aRangeList.size(); ++i)
{
const ScRange & rRange = aRangeList[i];
@@ -4432,7 +4471,7 @@ struct ScDependantsCalculator
return false;
}
}
- return true;
+ return !bHasSelfReferences;
}
};
@@ -4503,7 +4542,7 @@ bool ScFormulaCell::CheckComputeDependencies(sc::FormulaLogger::GroupScope& rSco
bool bOKToParallelize = false;
{
- ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, mxGroup.get());
+ ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, this);
if (mxGroup->mbPartOfCycle)
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
@@ -4511,6 +4550,7 @@ bool ScFormulaCell::CheckComputeDependencies(sc::FormulaLogger::GroupScope& rSco
return false;
}
+ ScFormulaGroupDependencyComputeGuard aDepComputeGuard(rRecursionHelper);
ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos);
bOKToParallelize = aCalculator.DoIt();
}
diff --git a/sc/source/core/tool/recursionhelper.cxx b/sc/source/core/tool/recursionhelper.cxx
index 8cfef9776e35..dd5be99c7155 100644
--- a/sc/source/core/tool/recursionhelper.cxx
+++ b/sc/source/core/tool/recursionhelper.cxx
@@ -13,6 +13,7 @@
void ScRecursionHelper::Init()
{
nRecursionCount = 0;
+ nDependencyComputationLevel = 0;
bInRecursionReturn = bDoingRecursion = bInIterationReturn = false;
aInsertPos = GetIterationEnd();
ResetIteration();
@@ -96,12 +97,22 @@ void ScRecursionHelper::Clear()
Init();
}
-bool ScRecursionHelper::PushFormulaGroup(ScFormulaCellGroup* pGrp)
+static ScFormulaCell* lcl_GetTopCell(ScFormulaCell* pCell)
{
- if (!pGrp)
- return false;
+ if (!pCell)
+ return nullptr;
+
+ const ScFormulaCellGroupRef& mxGroup = pCell->GetCellGroup();
+ if (!mxGroup)
+ return pCell;
+ return mxGroup->mpTopCell;
+}
+
+bool ScRecursionHelper::PushFormulaGroup(ScFormulaCell* pCell)
+{
+ assert(pCell);
- if (pGrp->mbSeenInPath)
+ if (pCell->GetSeenInPath())
{
// Found a simple cycle of formula-groups.
// Disable group calc for all elements of this cycle.
@@ -111,14 +122,16 @@ bool ScRecursionHelper::PushFormulaGroup(ScFormulaCellGroup* pGrp)
{
--nIdx;
assert(nIdx >= 0);
- aFGList[nIdx]->mbPartOfCycle = true;
- } while (aFGList[nIdx] != pGrp);
+ const ScFormulaCellGroupRef& mxGroup = aFGList[nIdx]->GetCellGroup();
+ if (mxGroup)
+ mxGroup->mbPartOfCycle = true;
+ } while (aFGList[nIdx] != pCell);
return false;
}
- pGrp->mbSeenInPath = true;
- aFGList.push_back(pGrp);
+ pCell->SetSeenInPath(true);
+ aFGList.push_back(pCell);
return true;
}
@@ -126,15 +139,34 @@ void ScRecursionHelper::PopFormulaGroup()
{
if (aFGList.empty())
return;
- ScFormulaCellGroup* pGrp = aFGList.back();
- pGrp->mbSeenInPath = false;
+ ScFormulaCell* pCell = aFGList.back();
+ pCell->SetSeenInPath(false);
aFGList.pop_back();
}
-ScFormulaGroupCycleCheckGuard::ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCellGroup* pGrp) :
+bool ScRecursionHelper::AnyParentFGInCycle()
+{
+ sal_Int32 nIdx = aFGList.size() - 1;
+ while (nIdx >= 0)
+ {
+ const ScFormulaCellGroupRef& mxGroup = aFGList[nIdx]->GetCellGroup();
+ if (mxGroup)
+ return mxGroup->mbPartOfCycle;
+ --nIdx;
+ };
+ return false;
+}
+
+ScFormulaGroupCycleCheckGuard::ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCell* pCell) :
mrRecHelper(rRecursionHelper)
{
- mbShouldPop = mrRecHelper.PushFormulaGroup(pGrp);
+ if (pCell)
+ {
+ pCell = lcl_GetTopCell(pCell);
+ mbShouldPop = mrRecHelper.PushFormulaGroup(pCell);
+ }
+ else
+ mbShouldPop = false;
}
ScFormulaGroupCycleCheckGuard::~ScFormulaGroupCycleCheckGuard()
@@ -143,4 +175,15 @@ ScFormulaGroupCycleCheckGuard::~ScFormulaGroupCycleCheckGuard()
mrRecHelper.PopFormulaGroup();
}
+ScFormulaGroupDependencyComputeGuard::ScFormulaGroupDependencyComputeGuard(ScRecursionHelper& rRecursionHelper) :
+ mrRecHelper(rRecursionHelper)
+{
+ mrRecHelper.IncDepComputeLevel();
+}
+
+ScFormulaGroupDependencyComputeGuard::~ScFormulaGroupDependencyComputeGuard()
+{
+ mrRecHelper.DecDepComputeLevel();
+}
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
More information about the Libreoffice-commits
mailing list