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.

Reviewed-on: https://gerrit.libreoffice.org/82074
Reviewed-by: Dennis Francis <dennis.francis@collabora.com>
Tested-by: Dennis Francis <dennis.francis@collabora.com>
(cherry picked from commit 0f4ba703038fb8678d4b1e7e6e0fd5e2d3025908)

Change-Id: I57a88bbc88adf177d49768a5d4585b3e53729aea
Reviewed-on: https://gerrit.libreoffice.org/82563
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

4 files changed, 62 insertions, 2 deletions

diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index d91ee0cfbe58..60acb23c2b2d 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -51,6 +51,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.
@@ -107,7 +110,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 d0e54711a5b7..172518888969 100644
--- a/sc/source/core/data/column4.cxx
+++ b/sc/source/core/data/column4.cxx
@@ -1680,7 +1680,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)
+                    {
+                        // 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 48cb55fae27a..942a7d1801e2 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -1521,12 +1521,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;
     }
 
@@ -4517,6 +4520,10 @@ struct ScDependantsCalculator
                     return false;
             }
         }
+
+        if (bHasSelfReferences)
+            mxGroup->mbPartOfCycle = true;
+
         return !bHasSelfReferences;
     }
 };
diff --git a/sc/source/core/tool/recursionhelper.cxx b/sc/source/core/tool/recursionhelper.cxx
index 1375048759e8..0027efc49506 100644
--- a/sc/source/core/tool/recursionhelper.cxx
+++ b/sc/source/core/tool/recursionhelper.cxx
@@ -132,16 +132,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()
@@ -157,6 +185,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 );
@@ -194,10 +230,12 @@ ScFormulaGroupDependencyComputeGuard::ScFormulaGroupDependencyComputeGuard(ScRec
     mrRecHelper(rRecursionHelper)
 {
     mrRecHelper.IncDepComputeLevel();
+    mrRecHelper.SetFormulaGroupDepEvalMode(true);
 }
 
 ScFormulaGroupDependencyComputeGuard::~ScFormulaGroupDependencyComputeGuard()
 {
+    mrRecHelper.SetFormulaGroupDepEvalMode(false);
     mrRecHelper.DecDepComputeLevel();
 }