fdo#78062: Broadcast only on non-empty cells within deleted range.

We don't want to broadcast over the whole selected range, which may be
the whole sheet which is well over 1 billion cells !

Change-Id: I7c139ce5efe09312cf824e35f0efe551184032eb

7 files changed, 155 insertions, 6 deletions

diff --git a/sc/inc/columnspanset.hxx b/sc/inc/columnspanset.hxx
index ef32af7aea29..7c7fdf524010 100644
--- a/sc/inc/columnspanset.hxx
+++ b/sc/inc/columnspanset.hxx
@@ -47,8 +47,10 @@ struct SC_DLLPUBLIC ColRowSpan
  */
 class ColumnSpanSet : boost::noncopyable
 {
+public:
     typedef mdds::flat_segment_tree<SCROW, bool> ColumnSpansType;
 
+private:
     struct ColumnType
     {
         ColumnSpansType maSpans;
@@ -89,6 +91,12 @@ public:
     void set(SCTAB nTab, SCCOL nCol, SCROW nRow1, SCROW nRow2, bool bVal);
     void set(const ScRange& rRange, bool bVal);
 
+    /**
+     * Scan specified range in a specified sheet and mark all non-empty cells
+     * with specified boolean value.
+     */
+    void scan(const ScDocument& rDoc, SCTAB nTab, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, bool bVal);
+
     void executeAction(Action& ac) const;
     void executeColumnAction(ScDocument& rDoc, ColumnAction& ac) const;
 };
diff --git a/sc/source/core/data/columnspanset.cxx b/sc/source/core/data/columnspanset.cxx
index 1aa57ba11c94..b06f9f7ed2c1 100644
--- a/sc/source/core/data/columnspanset.cxx
+++ b/sc/source/core/data/columnspanset.cxx
@@ -21,6 +21,29 @@
 
 namespace sc {
 
+namespace {
+
+class ColumnScanner
+{
+    ColumnSpanSet::ColumnSpansType& mrRanges;
+    bool mbVal;
+public:
+    ColumnScanner(ColumnSpanSet::ColumnSpansType& rRanges, bool bVal) :
+        mrRanges(rRanges), mbVal(bVal) {}
+
+    void operator() (const sc::CellStoreType::value_type& node, size_t nOffset, size_t nDataSize)
+    {
+        if (node.type == sc::element_type_empty)
+            return;
+
+        size_t nRow = node.position + nOffset;
+        size_t nEndRow = nRow + nDataSize; // Last row of current block plus 1
+        mrRanges.insert_back(nRow, nEndRow, mbVal);
+    }
+};
+
+}
+
 RowSpan::RowSpan(SCROW nRow1, SCROW nRow2) : mnRow1(nRow1), mnRow2(nRow2) {}
 
 ColRowSpan::ColRowSpan(SCCOLROW nStart, SCCOLROW nEnd) : mnStart(nStart), mnEnd(nEnd) {}
@@ -97,6 +120,30 @@ void ColumnSpanSet::set(const ScRange& rRange, bool bVal)
     }
 }
 
+void ColumnSpanSet::scan(
+    const ScDocument& rDoc, SCTAB nTab, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, bool bVal)
+{
+    if (!ValidColRow(nCol1, nRow1) || !ValidColRow(nCol2, nRow2))
+        return;
+
+    if (nCol1 > nCol2 || nRow1 > nRow2)
+        return;
+
+    const ScTable* pTab = rDoc.FetchTable(nTab);
+    if (!pTab)
+        return;
+
+    for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
+    {
+        ColumnType& rCol = getColumn(nTab, nCol);
+
+        const CellStoreType& rSrcCells = pTab->aCol[nCol].maCells;
+
+        ColumnScanner aScanner(rCol.maSpans, bVal);
+        ParseBlock(rSrcCells.begin(), rSrcCells, aScanner, nRow1, nRow2);
+    }
+}
+
 void ColumnSpanSet::executeAction(Action& ac) const
 {
     for (size_t nTab = 0; nTab < maDoc.size(); ++nTab)
diff --git a/sc/source/ui/inc/undobase.hxx b/sc/source/ui/inc/undobase.hxx
index 6a2cd94a883c..85726c8a2b1e 100644
--- a/sc/source/ui/inc/undobase.hxx
+++ b/sc/source/ui/inc/undobase.hxx
@@ -24,6 +24,9 @@
 #include "global.hxx"
 #include "address.hxx"
 #include "docsh.hxx"
+#include <columnspanset.hxx>
+
+#include <boost/ptr_container/ptr_map.hpp>
 
 class ScDocument;
 class ScDocShell;
@@ -36,6 +39,8 @@ class ScSimpleUndo: public SfxUndoAction
     ScSimpleUndo(const ScSimpleUndo&); // disabled
 
 public:
+    typedef boost::ptr_map<SCTAB,sc::ColumnSpanSet> DataSpansType;
+
                     TYPEINFO_OVERRIDE();
                     ScSimpleUndo( ScDocShell* pDocSh );
     virtual         ~ScSimpleUndo();
@@ -57,6 +62,14 @@ protected:
 
     void BroadcastChanges( const ScRange& rRange );
 
+    /**
+     * Broadcast changes on specified spans.
+     *
+     * @param rSpans container that specifies all spans whose changes need to
+     *               be broadcasted.
+     */
+    void BroadcastChanges( const DataSpansType& rSpans );
+
     static void     ShowTable( SCTAB nTab );
     static void     ShowTable( const ScRange& rRange );
 };
diff --git a/sc/source/ui/inc/undoblk.hxx b/sc/source/ui/inc/undoblk.hxx
index 40af6cc415b4..257c470e5615 100644
--- a/sc/source/ui/inc/undoblk.hxx
+++ b/sc/source/ui/inc/undoblk.hxx
@@ -25,7 +25,6 @@
 #include "spellparam.hxx"
 #include "cellmergeoption.hxx"
 #include "paramisc.hxx"
-#include <columnspanset.hxx>
 
 #include <boost/shared_ptr.hpp>
 #include <boost/scoped_ptr.hpp>
@@ -274,7 +273,11 @@ public:
 
     virtual OUString GetComment() const SAL_OVERRIDE;
 
+    void SetDataSpans( const boost::shared_ptr<DataSpansType>& pSpans );
+
 private:
+    boost::shared_ptr<DataSpansType> mpDataSpans; // Spans of non-empty cells.
+
     ScRange         aRange;
     ScMarkData      aMarkData;
     ScDocument*     pUndoDoc;       // Block mark and deleted data
diff --git a/sc/source/ui/undo/undobase.cxx b/sc/source/ui/undo/undobase.cxx
index 28daae102aad..8d7cff26203b 100644
--- a/sc/source/ui/undo/undobase.cxx
+++ b/sc/source/ui/undo/undobase.cxx
@@ -32,8 +32,8 @@
 #include "bcaslot.hxx"
 #include "globstr.hrc"
 #include <rowheightcontext.hxx>
+#include <column.hxx>
 
-// STATIC DATA -----------------------------------------------------------
 
 TYPEINIT1(ScSimpleUndo,     SfxUndoAction);
 TYPEINIT1(ScBlockUndo,      ScSimpleUndo);
@@ -150,6 +150,48 @@ void ScSimpleUndo::BroadcastChanges( const ScRange& rRange )
     pDoc->BroadcastCells(rRange, SC_HINT_DATACHANGED);
 }
 
+namespace {
+
+class SpanBroadcaster : public sc::ColumnSpanSet::ColumnAction
+{
+    ScDocument& mrDoc;
+    SCTAB mnCurTab;
+    SCCOL mnCurCol;
+
+public:
+    SpanBroadcaster( ScDocument& rDoc ) : mrDoc(rDoc), mnCurTab(-1), mnCurCol(-1) {}
+
+    virtual void startColumn( ScColumn* pCol )
+    {
+        mnCurTab = pCol->GetTab();
+        mnCurCol = pCol->GetCol();
+    }
+
+    virtual void execute( SCROW nRow1, SCROW nRow2, bool bVal )
+    {
+        if (!bVal)
+            return;
+
+        ScRange aRange(mnCurTab, mnCurCol, nRow1, mnCurTab, mnCurCol, nRow2);
+        mrDoc.BroadcastCells(aRange, SC_HINT_DATACHANGED);
+    };
+};
+
+}
+
+void ScSimpleUndo::BroadcastChanges( const DataSpansType& rSpans )
+{
+    ScDocument* pDoc = pDocShell->GetDocument();
+    SpanBroadcaster aBroadcaster(*pDoc);
+
+    DataSpansType::const_iterator it = rSpans.begin(), itEnd = rSpans.end();
+    for (; it != itEnd; ++it)
+    {
+        const sc::ColumnSpanSet& rSet = *it->second;
+        rSet.executeColumnAction(*pDoc, aBroadcaster);
+    }
+}
+
 void ScSimpleUndo::ShowTable( SCTAB nTab )
 {
     ScTabViewShell* pViewShell = ScTabViewShell::GetActiveViewShell();
diff --git a/sc/source/ui/undo/undoblk3.cxx b/sc/source/ui/undo/undoblk3.cxx
index 437a9e189594..03edabff1fba 100644
--- a/sc/source/ui/undo/undoblk3.cxx
+++ b/sc/source/ui/undo/undoblk3.cxx
@@ -106,6 +106,11 @@ OUString ScUndoDeleteContents::GetComment() const
     return ScGlobal::GetRscString( STR_UNDO_DELETECONTENTS );    // "Delete"
 }
 
+void ScUndoDeleteContents::SetDataSpans( const boost::shared_ptr<DataSpansType>& pSpans )
+{
+    mpDataSpans = pSpans;
+}
+
 void ScUndoDeleteContents::SetChangeTrack()
 {
     ScChangeTrack* pChangeTrack = pDocShell->GetDocument()->GetChangeTrack();
@@ -184,8 +189,13 @@ void ScUndoDeleteContents::Undo()
     EndUndo();
 
     if (nFlags & IDF_CONTENTS)
+    {
         // Broadcast only when the content changes. fdo#74687
-        BroadcastChanges(aRange);
+        if (mpDataSpans)
+            BroadcastChanges(*mpDataSpans);
+        else
+            BroadcastChanges(aRange);
+    }
 
     HelperNotifyChanges::NotifyIfChangesListeners(*pDocShell, aRange);
 }
diff --git a/sc/source/ui/view/viewfunc.cxx b/sc/source/ui/view/viewfunc.cxx
index b1c3fc408217..7c66d9c9044d 100644
--- a/sc/source/ui/view/viewfunc.cxx
+++ b/sc/source/ui/view/viewfunc.cxx
@@ -1846,6 +1846,9 @@ void ScViewFunc::DeleteContents( sal_uInt16 nFlags, bool bRecord )
                                        aFuncMark );
     }
 
+    // To keep track of all non-empty cells within the deleted area.
+    boost::shared_ptr<ScSimpleUndo::DataSpansType> pDataSpans;
+
     if ( bRecord )
     {
         pUndoDoc = new ScDocument( SCDOCMODE_UNDO );
@@ -1872,6 +1875,26 @@ void ScViewFunc::DeleteContents( sal_uInt16 nFlags, bool bRecord )
         // do not copy note captions to undo document
         nUndoDocFlags |= IDF_NOCAPTIONS;
         pDoc->CopyToDocument( aCopyRange, nUndoDocFlags, bMulti, pUndoDoc, &aFuncMark );
+
+        pDataSpans.reset(new ScSimpleUndo::DataSpansType);
+
+        for (itr = aFuncMark.begin(); itr != itrEnd; ++itr)
+        {
+            nTab = *itr;
+
+            SCCOL nCol1 = aCopyRange.aStart.Col(), nCol2 = aCopyRange.aEnd.Col();
+            SCROW nRow1 = aCopyRange.aStart.Row(), nRow2 = aCopyRange.aEnd.Row();
+
+            std::pair<ScSimpleUndo::DataSpansType::iterator,bool> r =
+                pDataSpans->insert(nTab, new sc::ColumnSpanSet(false));
+
+            if (r.second)
+            {
+                ScSimpleUndo::DataSpansType::iterator it = r.first;
+                sc::ColumnSpanSet* pSet = it->second;
+                pSet->scan(*pDoc, nTab, nCol1, nRow1, nCol2, nRow2, true);
+            }
+        }
     }
 
     HideAllCursors();   // for if summary is cancelled
@@ -1886,9 +1909,12 @@ void ScViewFunc::DeleteContents( sal_uInt16 nFlags, bool bRecord )
 
     if ( bRecord )
     {
-        pDocSh->GetUndoManager()->AddUndoAction(
-            new ScUndoDeleteContents( pDocSh, aFuncMark, aExtendedRange,
-                                      pUndoDoc, bMulti, nFlags, bDrawUndo ) );
+        ScUndoDeleteContents* pUndo =
+            new ScUndoDeleteContents(
+                pDocSh, aFuncMark, aExtendedRange, pUndoDoc, bMulti, nFlags, bDrawUndo);
+        pUndo->SetDataSpans(pDataSpans);
+
+        pDocSh->GetUndoManager()->AddUndoAction(pUndo);
     }
 
     if (!AdjustRowHeight( aExtendedRange.aStart.Row(), aExtendedRange.aEnd.Row() ))