Initial version of dynamic grouping of formula cells.

And tests to go along with it.

Change-Id: Idf5ff3b819aa557a1ae31dfb4d0b2c3a8216ed75

6 files changed, 279 insertions, 29 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 8a938e955636..322d7a60fb73 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -494,7 +494,7 @@ private:
 
     sc::CellStoreType::iterator GetPositionToInsert( SCROW nRow );
     sc::CellStoreType::iterator GetPositionToInsert( const sc::CellStoreType::iterator& it, SCROW nRow );
-    void ActivateNewFormulaCell( ScFormulaCell* pCell );
+    void ActivateNewFormulaCell( const sc::CellStoreType::iterator& itPos, SCROW nRow, ScFormulaCell& rCell );
     void BroadcastNewCell( SCROW nRow );
     bool UpdateScriptType( sc::CellTextAttr& rAttr, SCROW nRow );
 
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index 2ac841266405..b724d0278ce2 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -292,7 +292,7 @@ public:
     void                   SetCellGroup( const ScFormulaCellGroupRef &xRef )
         { xGroup = xRef; }
 
-    CompareState CompareByTokenArray( ScFormulaCell *pOther ) const;
+    CompareState CompareByTokenArray( ScFormulaCell& rOther ) const;
 
     bool InterpretFormulaGroup();
     bool InterpretInvariantFormulaGroup();
@@ -303,6 +303,11 @@ public:
     void EndListeningTo(
         ScDocument* pDoc, ScTokenArray* pArr = NULL, ScAddress aPos = ScAddress() );
     void EndListeningTo( sc::EndListeningContext& rCxt );
+
+    bool IsShared() const;
+    bool IsSharedInvariant() const;
+    SCROW GetSharedTopRow() const;
+    SCROW GetSharedLength() const;
 };
 
 #endif
diff --git a/sc/inc/mtvelements.hxx b/sc/inc/mtvelements.hxx
index 0ebf8be9635f..2c589974e32d 100644
--- a/sc/inc/mtvelements.hxx
+++ b/sc/inc/mtvelements.hxx
@@ -15,7 +15,7 @@
 #include "svl/broadcast.hxx"
 #include "editeng/editobj.hxx"
 
-#define DEBUG_COLUMN_STORAGE 0
+#define DEBUG_COLUMN_STORAGE 1
 
 #if DEBUG_COLUMN_STORAGE
 #ifdef NDEBUG
diff --git a/sc/qa/unit/ucalc.cxx b/sc/qa/unit/ucalc.cxx
index 462087a4a0f2..5286965c0eeb 100644
--- a/sc/qa/unit/ucalc.cxx
+++ b/sc/qa/unit/ucalc.cxx
@@ -236,6 +236,7 @@ public:
     void testMergedCells();
     void testUpdateReference();
     void testSearchCells();
+    void testSharedFormulas();
 
     /**
      * Make sure the sheet streams are invalidated properly.
@@ -352,6 +353,7 @@ public:
     CPPUNIT_TEST(testMergedCells);
     CPPUNIT_TEST(testUpdateReference);
     CPPUNIT_TEST(testSearchCells);
+    CPPUNIT_TEST(testSharedFormulas);
     CPPUNIT_TEST(testJumpToPrecedentsDependents);
     CPPUNIT_TEST(testSetBackgroundColor);
     CPPUNIT_TEST(testRenameTable);
@@ -6295,6 +6297,81 @@ void Test::testSearchCells()
     m_pDoc->DeleteTab(0);
 }
 
+void Test::testSharedFormulas()
+{
+    m_pDoc->InsertTab(0, "Test");
+
+    ScAddress aPos(1, 9, 0); // B10
+    m_pDoc->SetString(aPos, "=A10*2"); // Insert into B10.
+    const ScFormulaCell* pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("Expected to be a non-shared cell.", pFC && !pFC->IsShared());
+
+    aPos.SetRow(10); // B11
+    m_pDoc->SetString(aPos, "=A11*2");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(9, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(2, pFC->GetSharedLength());
+
+    aPos.SetRow(8); // B9
+    m_pDoc->SetString(aPos, "=A9*2");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(8, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(3, pFC->GetSharedLength());
+
+    aPos.SetRow(12); // B13
+    m_pDoc->SetString(aPos, "=A13*2");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This formula cell shouldn't be shared yet.", pFC && !pFC->IsShared());
+
+    // Insert a formula to B12, and B9:B13 should be shared.
+    aPos.SetRow(11); // B12
+    m_pDoc->SetString(aPos, "=A12*2");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(8, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(5, pFC->GetSharedLength());
+
+    // Insert formulas to B15:B16.
+    aPos.SetRow(14); // B15
+    m_pDoc->SetString(aPos, "=A15*2");
+    aPos.SetRow(15); // B16
+    m_pDoc->SetString(aPos, "=A16*2");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(14, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(2, pFC->GetSharedLength());
+
+    // Insert a formula to B14, and B9:B16 should be shared.
+    aPos.SetRow(13); // B14
+    m_pDoc->SetString(aPos, "=A14*2");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(8, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(8, pFC->GetSharedLength());
+
+    // Insert an incompatible formula to B12, to split the shared range to B9:B11 and B13:B16.
+    aPos.SetRow(11); // B12
+    m_pDoc->SetString(aPos, "=$A$1*4");
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell shouldn't be shared.", pFC && !pFC->IsShared());
+
+    aPos.SetRow(8); // B9
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(8, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(3, pFC->GetSharedLength());
+
+    aPos.SetRow(12); // B13
+    pFC = m_pDoc->GetFormulaCell(aPos);
+    CPPUNIT_ASSERT_MESSAGE("This cell is expected to be a shared formula cell.", pFC && pFC->IsShared());
+    CPPUNIT_ASSERT_EQUAL(12, pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(4, pFC->GetSharedLength());
+
+    m_pDoc->DeleteTab(0);
+}
+
 namespace {
 
 bool hasRange(const std::vector<ScTokenRef>& rRefTokens, const ScRange& rRange)
diff --git a/sc/source/core/data/column3.cxx b/sc/source/core/data/column3.cxx
index 303ddaed5cfa..c66e9d5e85af 100644
--- a/sc/source/core/data/column3.cxx
+++ b/sc/source/core/data/column3.cxx
@@ -332,17 +332,172 @@ sc::CellStoreType::iterator ScColumn::GetPositionToInsert( const sc::CellStoreTy
     // See if we are overwriting an existing formula cell.
     sc::CellStoreType::position_type aRet = maCells.position(it, nRow);
     sc::CellStoreType::iterator itRet = aRet.first;
-    if (itRet->type == sc::element_type_formula && !pDocument->IsClipOrUndo())
+    if (itRet->type == sc::element_type_formula)
     {
-        ScFormulaCell* pCell = sc::formula_block::at(*itRet->data, aRet.second);
-        pCell->EndListeningTo(pDocument);
+        ScFormulaCell& rCell = *sc::formula_block::at(*itRet->data, aRet.second);
+        if (!pDocument->IsClipOrUndo())
+            // Have the dying formula cell stop listening.
+            rCell.EndListeningTo(pDocument);
+
+        if (rCell.IsShared())
+        {
+            // This formula cell is shared. Adjust the shared group.
+            if (rCell.aPos.Row() == rCell.GetSharedTopRow())
+            {
+                // Top of the shared range.
+                ScFormulaCellGroupRef xGroup = rCell.GetCellGroup();
+                if (xGroup->mnLength == 2)
+                {
+                    // Group consists only only two cells. Mark the second one non-shared.
+#if DEBUG_COLUMN_STORAGE
+                    if (aRet.second+1 >= aRet.first->size)
+                    {
+                        cerr << "ScColumn::GetPositionToInsert: There is no next formula cell but there should be!" << endl;
+                        cerr.flush();
+                        abort();
+                    }
+#endif
+                    ScFormulaCellGroupRef xNone;
+                    ScFormulaCell& rNext = *sc::formula_block::at(*itRet->data, aRet.second+1);
+                    rNext.SetCellGroup(xNone);
+                }
+                else
+                {
+                    // Move the top cell to the next formula cell down.
+                    --xGroup->mnLength;
+                    ++xGroup->mnStart;
+                }
+            }
+            else if (rCell.aPos.Row() == rCell.GetSharedTopRow() + rCell.GetSharedLength() - 1)
+            {
+                // Bottom of the shared range.
+                ScFormulaCellGroupRef xGroup = rCell.GetCellGroup();
+                if (xGroup->mnLength == 2)
+                {
+                    // Mark the top cell non-shared.
+#if DEBUG_COLUMN_STORAGE
+                    if (aRet.second == 0)
+                    {
+                        cerr << "ScColumn::GetPositionToInsert: There is no previous formula cell but there should be!" << endl;
+                        cerr.flush();
+                        abort();
+                    }
+#endif
+                    ScFormulaCellGroupRef xNone;
+                    ScFormulaCell& rPrev = *sc::formula_block::at(*itRet->data, aRet.second-1);
+                    rPrev.SetCellGroup(xNone);
+                }
+                else
+                {
+                    // Just shortern the shared range length by one.
+                    --xGroup->mnLength;
+                }
+            }
+            else
+            {
+                // In the middle of the shared range. Split it into two groups.
+                ScFormulaCellGroupRef xGroup = rCell.GetCellGroup();
+                SCROW nEndRow = xGroup->mnStart + xGroup->mnLength - 1;
+                xGroup->mnLength = rCell.aPos.Row() - xGroup->mnStart; // Shorten the top group.
+
+                ScFormulaCellGroupRef xGroup2(new ScFormulaCellGroup);
+                xGroup2->mnStart = rCell.aPos.Row() + 1;
+                xGroup2->mnLength = nEndRow - rCell.aPos.Row();
+#if DEBUG_COLUMN_STORAGE
+                if (xGroup2->mnStart + xGroup2->mnLength > itRet->position + itRet->size)
+                {
+                    cerr << "ScColumn::GetPositionToInsert: Shared formula region goes beyond the formula block. Not good." << endl;
+                    cerr.flush();
+                    abort();
+                }
+#endif
+                sc::formula_block::iterator itCell = sc::formula_block::begin(*itRet->data);
+                std::advance(itCell, aRet.second+1);
+                sc::formula_block::iterator itCellEnd = itCell;
+                std::advance(itCellEnd, xGroup2->mnLength);
+                for (; itCell != itCellEnd; ++itCell)
+                {
+                    ScFormulaCell& rCell2 = **itCell;
+                    rCell2.SetCellGroup(xGroup2);
+                }
+            }
+        }
     }
 
     return itRet;
 }
 
-void ScColumn::ActivateNewFormulaCell( ScFormulaCell* pCell )
+namespace {
+
+void joinFormulaCells(SCROW nRow, ScFormulaCell& rCell1, ScFormulaCell& rCell2)
 {
+    ScFormulaCell::CompareState eState = rCell1.CompareByTokenArray(rCell2);
+    if (eState == ScFormulaCell::NotEqual)
+        return;
+
+    // Formula tokens equal those of the previous formula cell.
+    ScFormulaCellGroupRef xGroup1 = rCell1.GetCellGroup();
+    ScFormulaCellGroupRef xGroup2 = rCell2.GetCellGroup();
+    if (xGroup1)
+    {
+        if (xGroup2)
+        {
+            // Both cell1 and cell2 are shared. Merge them together.
+            xGroup1->mnLength += xGroup2->mnLength;
+            rCell2.SetCellGroup(xGroup1);
+        }
+        else
+        {
+            // cell1 is shared but cell2 is not.
+            rCell2.SetCellGroup(xGroup1);
+            ++xGroup1->mnLength;
+        }
+    }
+    else
+    {
+        if (xGroup2)
+        {
+            // cell1 is not shared, but cell2 is already shared.
+            rCell1.SetCellGroup(xGroup2);
+            xGroup2->mnStart = nRow;
+            ++xGroup2->mnLength;
+        }
+        else
+        {
+            // neither cells are shared.
+            xGroup1.reset(new ScFormulaCellGroup);
+            xGroup1->mnStart = nRow;
+            xGroup1->mbInvariant = (eState == ScFormulaCell::EqualInvariant);
+            xGroup1->mnLength = 2;
+
+            rCell1.SetCellGroup(xGroup1);
+            rCell2.SetCellGroup(xGroup1);
+        }
+    }
+}
+
+}
+
+void ScColumn::ActivateNewFormulaCell(
+    const sc::CellStoreType::iterator& itPos, SCROW nRow, ScFormulaCell& rCell )
+{
+    // See if this new formula cell can join an existing shared formula group.
+    sc::CellStoreType::position_type aPos = maCells.position(itPos, nRow);
+
+    // Check the previous row position for possible grouping.
+    if (aPos.first->type == sc::element_type_formula && aPos.second > 0)
+    {
+        ScFormulaCell& rPrev = *sc::formula_block::at(*aPos.first->data, aPos.second-1);
+        joinFormulaCells(nRow-1, rPrev, rCell);
+    }
+
+    // Check the next row position for possible grouping.
+    if (aPos.first->type == sc::element_type_formula && aPos.second+1 < aPos.first->size)
+    {
+        ScFormulaCell& rNext = *sc::formula_block::at(*aPos.first->data, aPos.second+1);
+        joinFormulaCells(nRow, rCell, rNext);
+    }
+
     // When we insert from the Clipboard we still have wrong (old) References!
     // First they are rewired in CopyBlockFromClip via UpdateReference and the
     // we call StartListeningFromClip and BroadcastFromClip.
@@ -350,9 +505,9 @@ void ScColumn::ActivateNewFormulaCell( ScFormulaCell* pCell )
     // After Import we call CalcAfterLoad and in there Listening.
     if (!pDocument->IsClipOrUndo() && !pDocument->IsInsertingFromOtherDoc())
     {
-        pCell->StartListeningTo(pDocument);
+        rCell.StartListeningTo(pDocument);
         if (!pDocument->IsCalcingAfterLoad())
-            pCell->SetDirty();
+            rCell.SetDirty();
     }
 }
 
@@ -1597,12 +1752,11 @@ void ScColumn::SetFormula( SCROW nRow, const ScTokenArray& rArray, formula::Form
     sal_uInt32 nCellFormat = GetNumberFormat(nRow);
     if( (nCellFormat % SV_COUNTRY_LANGUAGE_OFFSET) != 0)
         pCell->SetNeedNumberFormat(true);
-    maCells.set(it, nRow, pCell);
+    it = maCells.set(it, nRow, pCell);
     maCellTextAttrs.set(nRow, sc::CellTextAttr());
-    RegroupFormulaCells(nRow);
     CellStorageModified();
 
-    ActivateNewFormulaCell(pCell);
+    ActivateNewFormulaCell(it, nRow, *pCell);
 }
 
 void ScColumn::SetFormula( SCROW nRow, const OUString& rFormula, formula::FormulaGrammar::Grammar eGram )
@@ -1614,24 +1768,21 @@ void ScColumn::SetFormula( SCROW nRow, const OUString& rFormula, formula::Formul
     sal_uInt32 nCellFormat = GetNumberFormat(nRow);
     if( (nCellFormat % SV_COUNTRY_LANGUAGE_OFFSET) != 0)
         pCell->SetNeedNumberFormat(true);
-    maCells.set(it, nRow, pCell);
+    it = maCells.set(it, nRow, pCell);
     maCellTextAttrs.set(nRow, sc::CellTextAttr());
-    RegroupFormulaCells(nRow);
     CellStorageModified();
 
-    ActivateNewFormulaCell(pCell);
+    ActivateNewFormulaCell(it, nRow, *pCell);
 }
 
 ScFormulaCell* ScColumn::SetFormulaCell( SCROW nRow, ScFormulaCell* pCell )
 {
     sc::CellStoreType::iterator it = GetPositionToInsert(nRow);
-    maCells.set(it, nRow, pCell);
+    it = maCells.set(it, nRow, pCell);
     maCellTextAttrs.set(nRow, sc::CellTextAttr());
-    RegroupFormulaCells(nRow);
     CellStorageModified();
 
-    ActivateNewFormulaCell(pCell);
-
+    ActivateNewFormulaCell(it, nRow, *pCell);
     return pCell;
 }
 
@@ -1641,11 +1792,9 @@ ScFormulaCell* ScColumn::SetFormulaCell( sc::ColumnBlockPosition& rBlockPos, SCR
     rBlockPos.miCellPos = maCells.set(rBlockPos.miCellPos, nRow, pCell);
     rBlockPos.miCellTextAttrPos = maCellTextAttrs.set(
         rBlockPos.miCellTextAttrPos, nRow, sc::CellTextAttr());
-    RegroupFormulaCells(nRow);
     CellStorageModified();
 
-    ActivateNewFormulaCell(pCell);
-
+    ActivateNewFormulaCell(rBlockPos.miCellPos, nRow, *pCell);
     return pCell;
 }
 
@@ -2032,12 +2181,12 @@ void ScColumn::SetError( SCROW nRow, const sal_uInt16 nError)
     pCell->SetErrCode(nError);
 
     sc::CellStoreType::iterator it = GetPositionToInsert(nRow);
-    maCells.set(it, nRow, pCell);
+    it = maCells.set(it, nRow, pCell);
     maCellTextAttrs.set(nRow, sc::CellTextAttr());
     RegroupFormulaCells(nRow);
     CellStorageModified();
 
-    ActivateNewFormulaCell(pCell);
+    ActivateNewFormulaCell(it, nRow, *pCell);
 }
 
 void ScColumn::SetRawString( SCROW nRow, const OUString& rStr, bool bBroadcast )
@@ -2575,7 +2724,7 @@ public:
             if (!pPrev)
                 continue;
 
-            ScFormulaCell::CompareState eCompState = pPrev->CompareByTokenArray(pCur);
+            ScFormulaCell::CompareState eCompState = pPrev->CompareByTokenArray(*pCur);
             if (eCompState == ScFormulaCell::NotEqual)
             {
                 // different formula tokens.
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index ae3cb2d90095..81cd26d3b886 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -2844,20 +2844,20 @@ void ScFormulaCell::CompileColRowNameFormula()
     }
 }
 
-ScFormulaCell::CompareState ScFormulaCell::CompareByTokenArray( ScFormulaCell *pOtherCell ) const
+ScFormulaCell::CompareState ScFormulaCell::CompareByTokenArray( ScFormulaCell& rOther ) const
 {
     // no Matrix formulae yet.
     if ( GetMatrixFlag() != MM_NONE )
         return NotEqual;
 
     // are these formule at all similar ?
-    if ( GetHash() != pOtherCell->GetHash() )
+    if ( GetHash() != rOther.GetHash() )
         return NotEqual;
 
     FormulaToken **pThis = pCode->GetCode();
     sal_uInt16     nThisLen = pCode->GetCodeLen();
-    FormulaToken **pOther = pOtherCell->pCode->GetCode();
-    sal_uInt16     nOtherLen = pOtherCell->pCode->GetCodeLen();
+    FormulaToken **pOther = rOther.pCode->GetCode();
+    sal_uInt16     nOtherLen = rOther.pCode->GetCodeLen();
 
     if ( !pThis || !pOther )
     {
@@ -3400,4 +3400,23 @@ void ScFormulaCell::EndListeningTo( sc::EndListeningContext& rCxt )
     }
 }
 
+bool ScFormulaCell::IsShared() const
+{
+    return xGroup.get() != NULL;
+}
+
+bool ScFormulaCell::IsSharedInvariant() const
+{
+    return xGroup ? xGroup->mbInvariant : false;
+}
+
+SCROW ScFormulaCell::GetSharedTopRow() const
+{
+    return xGroup ? xGroup->mnStart : -1;
+}
+SCROW ScFormulaCell::GetSharedLength() const
+{
+    return xGroup ? xGroup->mnLength : 0;
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */