Do dependency computation checks for OpenCL and...

software interpreter like in CPU threading.
This patch also reworks the cycle detection
to make it more robust.

Since the dependency computation also does
cycle detection, there is no need to disable
group-calc(threaded/OpenCL/SW Interpreter)
for non-leaf nodes in recursive interpret.

The rework of cycle detection ensures that
it fixes tdf#95748 correctly.

Change-Id: I460addb768eedc0914491a3d24ae7220c3afbb20
Reviewed-on: https://gerrit.libreoffice.org/55665
Reviewed-by: Michael Meeks <michael.meeks@collabora.com>
Tested-by: Jenkins

10 files changed, 141 insertions, 71 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index bff5e621160e..5da349006538 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -576,7 +576,7 @@ public:
     bool ResolveStaticReference( ScMatrix& rMat, SCCOL nMatCol, SCROW nRow1, SCROW nRow2 );
     void FillMatrix( ScMatrix& rMat, size_t nMatCol, SCROW nRow1, SCROW nRow2, svl::SharedStringPool* pPool ) const;
     formula::VectorRefArray FetchVectorRefArray( SCROW nRow1, SCROW nRow2 );
-    bool HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 );
+    bool HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup );
     void SetFormulaResults( SCROW nRow, const double* pResults, size_t nLen );
     void SetFormulaResults( SCROW nRow, const formula::FormulaConstTokenRef* pResults, size_t nLen );
 
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index ad371bd73cd8..86079dd4c7b1 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -2384,7 +2384,7 @@ public:
     formula::FormulaTokenRef ResolveStaticReference( const ScRange& rRange );
 
     formula::VectorRefArray FetchVectorRefArray( const ScAddress& rPos, SCROW nLength );
-    bool HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength );
+    bool HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength, const ScFormulaCellGroupRef& mxGroup );
 
     /**
      * Call this before any operations that might trigger one or more formula
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index 78eb1f6265b8..a9df1a3be625 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -68,6 +68,7 @@ public:
     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;
 
@@ -142,8 +143,13 @@ private:
 
     ScFormulaCell( const ScFormulaCell& ) = delete;
 
-    bool InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope);
-    bool InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope);
+    bool CheckComputeDependencies(sc::FormulaLogger::GroupScope& rScope);
+    bool InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope,
+                                        bool& bDependencyComputed,
+                                        bool& bDependencyCheckFailed);
+    bool InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope,
+                                     bool& bDependencyComputed,
+                                     bool& bDependencyCheckFailed);
     bool InterpretInvariantFormulaGroup();
 
 public:
diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index b8ca1d087509..030e52c04b7c 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -104,6 +104,19 @@ public:
     void PopFormulaGroup();
 };
 
+/** A class to wrap ScRecursionHelper::PushFormulaGroup(),
+    ScRecursionHelper::PopFormulaGroup() and make these calls
+    exception safe. */
+class ScFormulaGroupCycleCheckGuard
+{
+    ScRecursionHelper& mrRecHelper;
+    bool mbShouldPop;
+public:
+    ScFormulaGroupCycleCheckGuard() = delete;
+    ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCellGroup* pGrp);
+    ~ScFormulaGroupCycleCheckGuard();
+};
+
 #endif // INCLUDED_SC_INC_RECURSIONHELPER_HXX
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index e7886b15c6ee..a0978122ca88 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -987,7 +987,7 @@ public:
     formula::FormulaTokenRef ResolveStaticReference( SCCOL nCol, SCROW nRow );
     formula::FormulaTokenRef ResolveStaticReference( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 );
     formula::VectorRefArray FetchVectorRefArray( SCCOL nCol, SCROW nRow1, SCROW nRow2 );
-    bool HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2 );
+    bool HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup );
 
     void SplitFormulaGroups( SCCOL nCol, std::vector<SCROW>& rRows );
     void UnshareFormulaCells( SCCOL nCol, std::vector<SCROW>& rRows );
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 912428f688e1..5ef16b9bf2c6 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -48,6 +48,7 @@
 #include <scmatrix.hxx>
 #include <rowheightcontext.hxx>
 #include <tokenstringcontext.hxx>
+#include <recursionhelper.hxx>
 
 #include <editeng/eeitem.hxx>
 
@@ -2831,7 +2832,7 @@ formula::VectorRefArray ScColumn::FetchVectorRefArray( SCROW nRow1, SCROW nRow2
     return formula::VectorRefArray(formula::VectorRefArray::Invalid);
 }
 
-bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 )
+bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup )
 {
     if (nRow1 > nRow2)
         return false;
@@ -2858,6 +2859,12 @@ bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 )
                 {
                     // Loop inside the formula block.
                     (*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)
+                        return false;
                 }
                 nRow += nEnd - nOffset;
                 break;
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index f970fd44bba7..58777dc19e43 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -1803,13 +1803,13 @@ void ScDocument::UnlockAdjustHeight()
         --nAdjustHeightLock;
 }
 
-bool ScDocument::HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength )
+bool ScDocument::HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength, const ScFormulaCellGroupRef& mxGroup )
 {
     SCTAB nTab = rPos.Tab();
     if (!TableExists(nTab))
         return false;
 
-    return maTabs[nTab]->HandleRefArrayForParallelism(rPos.Col(), rPos.Row(), rPos.Row()+nLength-1);
+    return maTabs[nTab]->HandleRefArrayForParallelism(rPos.Col(), rPos.Row(), rPos.Row()+nLength-1, mxGroup);
 }
 
 bool ScDocument::CanFitBlock( const ScRange& rOld, const ScRange& rNew )
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index 2de28fc8d651..dc13f05a68d9 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -529,6 +529,7 @@ ScFormulaCellGroup::ScFormulaCellGroup() :
     mbInvariant(false),
     mbSubTotal(false),
     mbSeenInPath(false),
+    mbPartOfCycle(false),
     meCalcState(sc::GroupCalcEnabled)
 {
 }
@@ -1474,6 +1475,15 @@ void ScFormulaCell::Interpret()
 {
     ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
 
+    if (mxGroup && mxGroup->mbSeenInPath)
+    {
+        // 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());
+        return;
+    }
+
 #if DEBUG_CALCULATION
     static bool bDebugCalculationInit = true;
     if (bDebugCalculationInit)
@@ -1529,13 +1539,6 @@ void ScFormulaCell::Interpret()
     {
         pDocument->IncInterpretLevel();
 
-        bool bCheckForFGCycle = mxGroup && !pDocument->IsThreadedGroupCalcInProgress() &&
-            mxGroup->meCalcState == sc::GroupCalcEnabled &&
-            ScCalcConfig::isThreadingEnabled();
-        bool bPopFormulaGroup = false;
-        if (bCheckForFGCycle)
-            bPopFormulaGroup = rRecursionHelper.PushFormulaGroup(mxGroup.get());
-
 #if DEBUG_CALCULATION
         aDC.enterGroup();
         bool bGroupInterpreted = InterpretFormulaGroup();
@@ -1547,9 +1550,6 @@ void ScFormulaCell::Interpret()
             InterpretTail( pDocument->GetNonThreadedContext(), SCITP_NORMAL);
 #endif
 
-        if (bPopFormulaGroup)
-            rRecursionHelper.PopFormulaGroup();
-
         pDocument->DecInterpretLevel();
     }
 
@@ -2452,7 +2452,10 @@ void ScFormulaCell::SetDirtyVar()
     bDirty = true;
     mbPostponedDirty = false;
     if (mxGroup && mxGroup->meCalcState == sc::GroupCalcRunning)
+    {
         mxGroup->meCalcState = sc::GroupCalcEnabled;
+        mxGroup->mbPartOfCycle = false;
+    }
 
     // mark the sheet of this cell to be calculated
     //#FIXME do we need to revert this remnant of old fake vba events? pDocument->AddCalculateTable( aPos.Tab() );
@@ -4164,13 +4167,15 @@ struct ScDependantsCalculator
 {
     ScDocument& mrDoc;
     const ScTokenArray& mrCode;
+    const ScFormulaCellGroupRef& mxGroup;
     const SCROW mnLen;
     const ScAddress& mrPos;
 
     ScDependantsCalculator(ScDocument& rDoc, const ScTokenArray& rCode, const ScFormulaCell& rCell, const ScAddress& rPos) :
         mrDoc(rDoc),
         mrCode(rCode),
-        mnLen(rCell.GetCellGroup()->mnLength),
+        mxGroup(rCell.GetCellGroup()),
+        mnLen(mxGroup->mnLength),
         mrPos(rPos)
     {
     }
@@ -4303,16 +4308,6 @@ struct ScDependantsCalculator
 
                         // Trim data array length to actual data range.
                         SCROW nTrimLen = trimLength(aRefPos.Tab(), aRefPos.Col(), aRefPos.Col(), aRefPos.Row(), mnLen);
-                        // Fetch double array guarantees that the length of the
-                        // returned array equals or greater than the requested
-                        // length.
-
-                        formula::VectorRefArray aArray;
-                        if (nTrimLen)
-                            aArray = mrDoc.FetchVectorRefArray(aRefPos, nTrimLen);
-
-                        if (!aArray.isValid())
-                            return false;
 
                         aRangeList.Join(ScRange(aRefPos.Col(), aRefPos.Row(), aRefPos.Tab(),
                                                 aRefPos.Col(), aRefPos.Row() + nTrimLen - 1, aRefPos.Tab()));
@@ -4391,7 +4386,7 @@ struct ScDependantsCalculator
             for (auto nCol = rRange.aStart.Col(); nCol <= rRange.aEnd.Col(); nCol++)
             {
                 if (!mrDoc.HandleRefArrayForParallelism(ScAddress(nCol, rRange.aStart.Row(), rRange.aStart.Tab()),
-                                                        rRange.aEnd.Row() - rRange.aStart.Row() + 1))
+                                                        rRange.aEnd.Row() - rRange.aStart.Row() + 1, mxGroup))
                     return false;
             }
         }
@@ -4407,12 +4402,9 @@ bool ScFormulaCell::InterpretFormulaGroup()
     auto aScope = sc::FormulaLogger::get().enterGroup(*pDocument, *this);
     ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
 
-    if (rRecursionHelper.GetRecursionCount())
+    if (mxGroup->mbPartOfCycle)
     {
-        // Do not attempt to interpret a group when calculations are already
-        // running, otherwise we may run into a circular reference hell. See
-        // tdf#95748
-        aScope.addMessage("group calc disabled during recursive calculation.");
+        aScope.addMessage("This formula-group is part of a cycle");
         return false;
     }
 
@@ -4444,58 +4436,86 @@ bool ScFormulaCell::InterpretFormulaGroup()
     // ScFormulaCell::InterpretTail()
     RecursionCounter aRecursionCounter( rRecursionHelper, this);
 
+    bool bDependencyComputed = false;
+    bool bDependencyCheckFailed = false;
+
     // Preference order:
     // First try OpenCL, but only if actual OpenCL is available (i.e. no SwInterpreter).
     // Then try threading and as the last one try SwInterpreter.
     if( ScCalcConfig::isOpenCLEnabled())
-        if( InterpretFormulaGroupOpenCL(aScope))
+        if( InterpretFormulaGroupOpenCL(aScope, bDependencyComputed, bDependencyCheckFailed))
             return true;
 
-    if( InterpretFormulaGroupThreading(aScope))
+    if( InterpretFormulaGroupThreading(aScope, bDependencyComputed, bDependencyCheckFailed))
         return true;
 
-    return InterpretFormulaGroupOpenCL(aScope);
+    return InterpretFormulaGroupOpenCL(aScope, bDependencyComputed, bDependencyCheckFailed);
 }
 
-
-// To be called only from InterpretFormulaGroup().
-bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope)
+bool ScFormulaCell::CheckComputeDependencies(sc::FormulaLogger::GroupScope& rScope)
 {
-    static const bool bThreadingProhibited = std::getenv("SC_NO_THREADED_CALCULATION");
-    if (!bThreadingProhibited &&
-        pCode->IsEnabledForThreading() &&
-        ScCalcConfig::isThreadingEnabled())
-    {
-        // iterate over code in the formula ...
-        // ensure all input is pre-calculated -
-        // to avoid writing during the calculation
-        ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos);
-
-        // Disable or hugely enlarge subset for S/W group
-        // threading interpreter
-
-        bool bOKToThread = aCalculator.DoIt();
+    ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
+    // iterate over code in the formula ...
+    // ensure all input is pre-calculated -
+    // to avoid writing during the calculation
 
-        if (pDocument->GetRecursionHelper().IsInRecursionReturn())
+    bool bOKToParallelize = false;
+    {
+        ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, mxGroup.get());
+        if (mxGroup->mbPartOfCycle)
         {
             mxGroup->meCalcState = sc::GroupCalcDisabled;
-            aScope.addMessage("Recursion limit reached, cannot thread this formula group now");
+            rScope.addMessage("found circular formula-group dependencies");
             return false;
         }
 
-        if (!bOKToThread)
-        {
-            mxGroup->meCalcState = sc::GroupCalcDisabled;
-            aScope.addMessage("could not do new dependencies calculation thing");
-            return false;
-        }
+        ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos);
+        bOKToParallelize = aCalculator.DoIt();
+    }
 
-        if (mxGroup->meCalcState == sc::GroupCalcDisabled)
+    if (rRecursionHelper.IsInRecursionReturn())
+    {
+        mxGroup->meCalcState = sc::GroupCalcDisabled;
+        rScope.addMessage("Recursion limit reached, cannot thread this formula group now");
+        return false;
+    }
+
+    if (mxGroup->mbPartOfCycle)
+    {
+        mxGroup->meCalcState = sc::GroupCalcDisabled;
+        rScope.addMessage("found circular formula-group dependencies");
+        return false;
+    }
+
+    if (!bOKToParallelize)
+    {
+        mxGroup->meCalcState = sc::GroupCalcDisabled;
+        rScope.addMessage("could not do new dependencies calculation thing");
+        return false;
+    }
+
+    return true;
+}
+
+// To be called only from InterpretFormulaGroup().
+bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope,
+                                                   bool& bDependencyComputed,
+                                                   bool& bDependencyCheckFailed)
+{
+    static const bool bThreadingProhibited = std::getenv("SC_NO_THREADED_CALCULATION");
+    if (!bDependencyCheckFailed && !bThreadingProhibited &&
+        pCode->IsEnabledForThreading() &&
+        ScCalcConfig::isThreadingEnabled())
+    {
+        if(!bDependencyComputed && !CheckComputeDependencies(aScope))
         {
-            aScope.addMessage("found circular formula-group dependencies");
+            bDependencyComputed = true;
+            bDependencyCheckFailed = true;
             return false;
         }
 
+        bDependencyComputed = true;
+
         const static bool bHyperThreadingActive = tools::cpuid::hasHyperThreading();
 
         // Then do the threaded calculation
@@ -4584,7 +4604,9 @@ bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope
 }
 
 // To be called only from InterpretFormulaGroup().
-bool ScFormulaCell::InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope)
+bool ScFormulaCell::InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope,
+                                                bool& bDependencyComputed,
+                                                bool& bDependencyCheckFailed)
 {
     bool bCanVectorize = pCode->IsEnabledForOpenCL();
     switch (pCode->GetVectorState())
@@ -4622,6 +4644,18 @@ bool ScFormulaCell::InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& a
         return false;
     }
 
+    if (bDependencyCheckFailed)
+        return false;
+
+    if(!bDependencyComputed && !CheckComputeDependencies(aScope))
+    {
+        bDependencyComputed = true;
+        bDependencyCheckFailed = true;
+        return false;
+    }
+
+    bDependencyComputed = true;
+
     // TODO : Disable invariant formula group interpretation for now in order
     // to get implicit intersection to work.
     if (mxGroup->mbInvariant && false)
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 3129eff669a0..76cd876e1d49 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2309,7 +2309,7 @@ formula::VectorRefArray ScTable::FetchVectorRefArray( SCCOL nCol, SCROW nRow1, S
     return aCol[nCol].FetchVectorRefArray(nRow1, nRow2);
 }
 
-bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2 )
+bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup )
 {
     if (nRow2 < nRow1)
         return false;
@@ -2317,7 +2317,7 @@ bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2
     if ( !IsColValid( nCol ) || !ValidRow( nRow1 ) || !ValidRow( nRow2 ) )
         return false;
 
-    return aCol[nCol].HandleRefArrayForParallelism(nRow1, nRow2);
+    return aCol[nCol].HandleRefArrayForParallelism(nRow1, nRow2, mxGroup);
 }
 
 ScRefCellValue ScTable::GetRefCellValue( SCCOL nCol, SCROW nRow )
diff --git a/sc/source/core/tool/recursionhelper.cxx b/sc/source/core/tool/recursionhelper.cxx
index 665ee2ae7aeb..0c185dba3c6b 100644
--- a/sc/source/core/tool/recursionhelper.cxx
+++ b/sc/source/core/tool/recursionhelper.cxx
@@ -109,9 +109,7 @@ bool ScRecursionHelper::PushFormulaGroup(ScFormulaCellGroup* pGrp)
         {
             --nIdx;
             assert(nIdx >= 0);
-            auto& eCalcState = aFGList[nIdx]->meCalcState;
-            if (eCalcState == sc::GroupCalcEnabled)
-                eCalcState = sc::GroupCalcDisabled;
+            aFGList[nIdx]->mbPartOfCycle = true;
         } while (aFGList[nIdx] != pGrp);
 
         return false;
@@ -131,4 +129,16 @@ void ScRecursionHelper::PopFormulaGroup()
     aFGList.pop_back();
 }
 
+ScFormulaGroupCycleCheckGuard::ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCellGroup* pGrp) :
+    mrRecHelper(rRecursionHelper)
+{
+    mbShouldPop = mrRecHelper.PushFormulaGroup(pGrp);
+}
+
+ScFormulaGroupCycleCheckGuard::~ScFormulaGroupCycleCheckGuard()
+{
+    if (mbShouldPop)
+        mrRecHelper.PopFormulaGroup();
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */