sw: make ODT export of paragraph auto-styles deterministic

If a complex enough document is loaded into Writer and saved as ODT,
then the content.xml's automatic paragraph styles (P<num>) are
re-ordered on each save, which leads to unnecessary noise.

The actual random order is created during import by the time we convert
direct formatting (e.g. from HTML import) to autostyles, as
StylePoolImpl::maRoot stores autostyles in a map that orders autostyle
parents based on their pointer address.

This has benefits like automatic ordering of item sets and fast
comparison, so don't change that, but extend the svl API to also track
the name of those parents.

This way by the time StylePool::createIterator() would iterate over
those autostyles, it can order the parents by their name, so two
import->export runs will result in the same autostyle ordering.

(This appears to be the only indeterminism in content.xml for a test
HTML input, while meta.xml and settings.xml still changes all the time.)

Change-Id: I1cfcae2c664a5c5c3dee48be733046979c1593ed
Reviewed-on: https://gerrit.libreoffice.org/69469
Reviewed-by: Miklos Vajna <vmiklos@collabora.com>
Tested-by: Jenkins

7 files changed, 145 insertions, 16 deletions

diff --git a/include/svl/stylepool.hxx b/include/svl/stylepool.hxx
index 5fe2f2197186..0a22cb1f707e 100644
--- a/include/svl/stylepool.hxx
+++ b/include/svl/stylepool.hxx
@@ -40,9 +40,13 @@ public:
         @param SfxItemSet
         the SfxItemSet to insert
 
+        @param pParentName
+        Name of the parent of rSet. If set, createIterator() can be more deterministic by iterating
+        over item sets ordered by parent names.
+
         @return a shared pointer to the SfxItemSet
     */
-    std::shared_ptr<SfxItemSet> insertItemSet( const SfxItemSet& rSet );
+    std::shared_ptr<SfxItemSet> insertItemSet( const SfxItemSet& rSet, const OUString* pParentName = nullptr );
 
     /** Create an iterator
 
diff --git a/svl/CppunitTest_svl_items.mk b/svl/CppunitTest_svl_items.mk
index c8e5e0699635..28e8772d71ad 100644
--- a/svl/CppunitTest_svl_items.mk
+++ b/svl/CppunitTest_svl_items.mk
@@ -15,6 +15,7 @@ $(eval $(call gb_CppunitTest_use_sdk_api,svl_items))
 
 $(eval $(call gb_CppunitTest_add_exception_objects,svl_items, \
 	svl/qa/unit/items/test_IndexedStyleSheets \
+	svl/qa/unit/items/stylepool \
 ))
 
 $(eval $(call gb_CppunitTest_use_libraries,svl_items, \
diff --git a/svl/qa/unit/items/stylepool.cxx b/svl/qa/unit/items/stylepool.cxx
new file mode 100644
index 000000000000..5f37dc929aa7
--- /dev/null
+++ b/svl/qa/unit/items/stylepool.cxx
@@ -0,0 +1,84 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <unotest/bootstrapfixturebase.hxx>
+
+#include <svl/itempool.hxx>
+#include <svl/itemset.hxx>
+#include <svl/stylepool.hxx>
+#include <svl/stritem.hxx>
+#include <sal/log.hxx>
+
+namespace
+{
+/// Tests svl StylePool.
+class StylePoolTest : public CppUnit::TestFixture
+{
+};
+
+CPPUNIT_TEST_FIXTURE(StylePoolTest, testIterationOrder)
+{
+    // Set up a style pool with multiple parents.
+    SfxStringItem aDefault1(1);
+    std::vector<SfxPoolItem*> aDefaults{ &aDefault1 };
+    SfxItemInfo const aItems[] = { { 1, false } };
+
+    SfxItemPool* pPool = new SfxItemPool("test", 1, 1, aItems);
+    pPool->SetDefaults(&aDefaults);
+    {
+        // Set up parents in mixed order to make sure we do not sort by pointer address.
+        SfxItemSet aParent1(*pPool, svl::Items<1, 1>{});
+        SfxItemSet aChild1(*pPool, svl::Items<1, 1>{});
+        aChild1.SetParent(&aParent1);
+        SfxStringItem aItem1(1, "Item1");
+        aChild1.Put(aItem1);
+
+        SfxItemSet aParent3(*pPool, svl::Items<1, 1>{});
+        SfxItemSet aChild3(*pPool, svl::Items<1, 1>{});
+        aChild3.SetParent(&aParent3);
+        SfxStringItem aItem3(1, "Item3");
+        aChild3.Put(aItem3);
+
+        SfxItemSet aParent2(*pPool, svl::Items<1, 1>{});
+        SfxItemSet aChild2(*pPool, svl::Items<1, 1>{});
+        aChild2.SetParent(&aParent2);
+        SfxStringItem aItem2(1, "Item2");
+        aChild2.Put(aItem2);
+
+        // Insert item sets in alphabetical order.
+        StylePool aStylePool;
+        OUString aChild1Name("Child1");
+        aStylePool.insertItemSet(aChild1, &aChild1Name);
+        OUString aChild3Name("Child3");
+        aStylePool.insertItemSet(aChild3, &aChild3Name);
+        OUString aChild2Name("Child2");
+        aStylePool.insertItemSet(aChild2, &aChild2Name);
+        std::unique_ptr<IStylePoolIteratorAccess> pIter = aStylePool.createIterator();
+        std::shared_ptr<SfxItemSet> pStyle1 = pIter->getNext();
+        CPPUNIT_ASSERT(pStyle1.get());
+        const SfxStringItem* pItem1 = static_cast<const SfxStringItem*>(pStyle1->GetItem(1));
+        CPPUNIT_ASSERT_EQUAL(OUString("Item1"), pItem1->GetValue());
+        std::shared_ptr<SfxItemSet> pStyle2 = pIter->getNext();
+        CPPUNIT_ASSERT(pStyle2.get());
+        const SfxStringItem* pItem2 = static_cast<const SfxStringItem*>(pStyle2->GetItem(1));
+        // Without the accompanying fix in place, this test would have failed with 'Expected: Item2;
+        // Actual: Item3'. The iteration order depended on the pointer address on the pointer
+        // address of the parents.
+        CPPUNIT_ASSERT_EQUAL(OUString("Item2"), pItem2->GetValue());
+        std::shared_ptr<SfxItemSet> pStyle3 = pIter->getNext();
+        CPPUNIT_ASSERT(pStyle3.get());
+        const SfxStringItem* pItem3 = static_cast<const SfxStringItem*>(pStyle3->GetItem(1));
+        CPPUNIT_ASSERT_EQUAL(OUString("Item3"), pItem3->GetValue());
+        CPPUNIT_ASSERT(!pIter->getNext());
+    }
+    SfxItemPool::Free(pPool);
+}
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/svl/source/items/stylepool.cxx b/svl/source/items/stylepool.cxx
index d6dbe619df82..33e8fddbce11 100644
--- a/svl/source/items/stylepool.cxx
+++ b/svl/source/items/stylepool.cxx
@@ -242,29 +242,62 @@ namespace {
         Node* mpNode;
         const bool mbSkipUnusedItemSets;
         const bool mbSkipIgnorable;
+        /// List of item set parents, ordered by their name.
+        std::vector<const SfxItemSet*> maParents;
+        /// The iterator's current position.
+        std::vector<const SfxItemSet*>::iterator mpCurrParent;
     public:
         // #i86923#
         Iterator( std::map< const SfxItemSet*, Node >& rR,
                   const bool bSkipUnusedItemSets,
-                  const bool bSkipIgnorable )
+                  const bool bSkipIgnorable,
+                  const std::map< const SfxItemSet*, OUString>& rParentNames )
             : mrRoot( rR ),
-              mpCurrNode( rR.begin() ),
               mpNode(nullptr),
               mbSkipUnusedItemSets( bSkipUnusedItemSets ),
               mbSkipIgnorable( bSkipIgnorable )
-        {}
+        {
+            // Collect the parent pointers into a vector we can sort.
+            for (const auto& rParent : mrRoot)
+                maParents.push_back(rParent.first);
+
+            // Sort the parents using their name, if they have one.
+            if (!rParentNames.empty())
+            {
+                std::sort(maParents.begin(), maParents.end(),
+                          [&rParentNames](const SfxItemSet* pA, const SfxItemSet* pB) {
+                              OUString aA;
+                              OUString aB;
+                              auto it = rParentNames.find(pA);
+                              if (it != rParentNames.end())
+                                  aA = it->second;
+                              it = rParentNames.find(pB);
+                              if (it != rParentNames.end())
+                                  aB = it->second;
+                              return aA < aB;
+                          });
+            }
+
+            // Start the iteration.
+            mpCurrParent = maParents.begin();
+            if (mpCurrParent != maParents.end())
+                mpCurrNode = mrRoot.find(*mpCurrParent);
+        }
         virtual std::shared_ptr<SfxItemSet> getNext() override;
     };
 
     std::shared_ptr<SfxItemSet> Iterator::getNext()
     {
         std::shared_ptr<SfxItemSet> pReturn;
-        while( mpNode || mpCurrNode != mrRoot.end() )
+        while( mpNode || mpCurrParent != maParents.end() )
         {
             if( !mpNode )
             {
                 mpNode = &mpCurrNode->second;
-                ++mpCurrNode;
+                // Perform the actual increment.
+                ++mpCurrParent;
+                if (mpCurrParent != maParents.end())
+                    mpCurrNode = mrRoot.find(*mpCurrParent);
                 // #i86923#
                 if ( mpNode->hasItemSet( mbSkipUnusedItemSets ) )
                 {
@@ -309,6 +342,8 @@ class StylePoolImpl
 {
 private:
     std::map< const SfxItemSet*, Node > maRoot;
+    /// Names of maRoot keys.
+    std::map< const SfxItemSet*, OUString> maParentNames;
     // #i86923#
     std::unique_ptr<SfxItemSet> mpIgnorableItems;
 #ifdef DEBUG
@@ -331,7 +366,7 @@ public:
                     "<StylePoolImpl::StylePoolImpl(..)> - <SfxItemSet::Clone( sal_False )> does not work as excepted - <mpIgnorableItems> is not empty." );
     }
 
-    std::shared_ptr<SfxItemSet> insertItemSet( const SfxItemSet& rSet );
+    std::shared_ptr<SfxItemSet> insertItemSet( const SfxItemSet& rSet, const OUString* pParentName = nullptr );
 
     // #i86923#
     std::unique_ptr<IStylePoolIteratorAccess> createIterator( bool bSkipUnusedItemSets,
@@ -339,10 +374,12 @@ public:
 };
 
 
-std::shared_ptr<SfxItemSet> StylePoolImpl::insertItemSet( const SfxItemSet& rSet )
+std::shared_ptr<SfxItemSet> StylePoolImpl::insertItemSet( const SfxItemSet& rSet, const OUString* pParentName )
 {
     bool bNonPoolable = false;
     Node* pCurNode = &maRoot[ rSet.GetParent() ];
+    if (pParentName)
+        maParentNames[ rSet.GetParent() ] = *pParentName;
     SfxItemIter aIter( rSet );
     const SfxPoolItem* pItem = aIter.GetCurItem();
     // Every SfxPoolItem in the SfxItemSet causes a step deeper into the tree,
@@ -410,7 +447,7 @@ std::shared_ptr<SfxItemSet> StylePoolImpl::insertItemSet( const SfxItemSet& rSet
 std::unique_ptr<IStylePoolIteratorAccess> StylePoolImpl::createIterator( bool bSkipUnusedItemSets,
                                                          bool bSkipIgnorableItems )
 {
-    return std::make_unique<Iterator>( maRoot, bSkipUnusedItemSets, bSkipIgnorableItems );
+    return std::make_unique<Iterator>( maRoot, bSkipUnusedItemSets, bSkipIgnorableItems, maParentNames );
 }
 // Ctor, Dtor and redirected methods of class StylePool, nearly inline ;-)
 
@@ -419,8 +456,8 @@ StylePool::StylePool( SfxItemSet const * pIgnorableItems )
     : pImpl( new StylePoolImpl( pIgnorableItems ) )
 {}
 
-std::shared_ptr<SfxItemSet> StylePool::insertItemSet( const SfxItemSet& rSet )
-{ return pImpl->insertItemSet( rSet ); }
+std::shared_ptr<SfxItemSet> StylePool::insertItemSet( const SfxItemSet& rSet, const OUString* pParentName )
+{ return pImpl->insertItemSet( rSet, pParentName ); }
 
 // #i86923#
 std::unique_ptr<IStylePoolIteratorAccess> StylePool::createIterator( const bool bSkipUnusedItemSets,
diff --git a/sw/inc/istyleaccess.hxx b/sw/inc/istyleaccess.hxx
index 88de8512a7ad..7bb832f08cdb 100644
--- a/sw/inc/istyleaccess.hxx
+++ b/sw/inc/istyleaccess.hxx
@@ -36,7 +36,8 @@ public:
     virtual ~IStyleAccess() {}
 
     virtual std::shared_ptr<SfxItemSet> getAutomaticStyle( const SfxItemSet& rSet,
-                                                               SwAutoStyleFamily eFamily ) = 0;
+                                                               SwAutoStyleFamily eFamily,
+                                                               const OUString* pParentName = nullptr ) = 0;
     virtual void getAllStyles( std::vector<std::shared_ptr<SfxItemSet>> &rStyles,
                                                                SwAutoStyleFamily eFamily ) = 0;
     /** It's slow to iterate through a stylepool looking for a special name, but if
diff --git a/sw/source/core/doc/swstylemanager.cxx b/sw/source/core/doc/swstylemanager.cxx
index 43bad5d40ca8..22a3e99da1ea 100644
--- a/sw/source/core/doc/swstylemanager.cxx
+++ b/sw/source/core/doc/swstylemanager.cxx
@@ -67,7 +67,8 @@ public:
           aAutoParaPool( pIgnorableParagraphItems )
     {}
     virtual std::shared_ptr<SfxItemSet> getAutomaticStyle( const SfxItemSet& rSet,
-                                                               IStyleAccess::SwAutoStyleFamily eFamily ) override;
+                                                               IStyleAccess::SwAutoStyleFamily eFamily,
+                                                               const OUString* pParentName = nullptr ) override;
     virtual std::shared_ptr<SfxItemSet> getByName( const OUString& rName,
                                                                IStyleAccess::SwAutoStyleFamily eFamily ) override;
     virtual void getAllStyles( std::vector<std::shared_ptr<SfxItemSet>> &rStyles,
@@ -89,10 +90,11 @@ void SwStyleManager::clearCaches()
 }
 
 std::shared_ptr<SfxItemSet> SwStyleManager::getAutomaticStyle( const SfxItemSet& rSet,
-                                                                   IStyleAccess::SwAutoStyleFamily eFamily )
+                                                                   IStyleAccess::SwAutoStyleFamily eFamily,
+                                                                   const OUString* pParentName )
 {
     StylePool& rAutoPool = eFamily == IStyleAccess::AUTO_STYLE_CHAR ? aAutoCharPool : aAutoParaPool;
-    return rAutoPool.insertItemSet( rSet );
+    return rAutoPool.insertItemSet( rSet, pParentName );
 }
 
 std::shared_ptr<SfxItemSet> SwStyleManager::cacheAutomaticStyle( const SfxItemSet& rSet,
diff --git a/sw/source/core/txtnode/ndtxt.cxx b/sw/source/core/txtnode/ndtxt.cxx
index 2fbf5a71e60b..d384ce19b7d1 100644
--- a/sw/source/core/txtnode/ndtxt.cxx
+++ b/sw/source/core/txtnode/ndtxt.cxx
@@ -1164,7 +1164,7 @@ void SwTextNode::NewAttrSet( SwAttrPool& rPool )
     aNewAttrSet.Put( aFormatColl );
 
     aNewAttrSet.SetParent( &pAnyFormatColl->GetAttrSet() );
-    mpAttrSet = GetDoc()->GetIStyleAccess().getAutomaticStyle( aNewAttrSet, IStyleAccess::AUTO_STYLE_PARA );
+    mpAttrSet = GetDoc()->GetIStyleAccess().getAutomaticStyle( aNewAttrSet, IStyleAccess::AUTO_STYLE_PARA, &sVal );
 }
 
 // override SwIndexReg::Update => text hints do not need SwIndex for start/end!