[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