Merge remote-tracking branch 'XRPLF/develop' into ximinez/directory

* XRPLF/develop:
  feat: Create new transaction testing framework `TxTest` (6537)
  feat: Add cleanup amendment for 3.2.0 (7037)
  fix: Fix ubsan flagged issues (6151)

include/xrpl/ledger/Ledger.h

@@ -229,6 +229,19 @@ public:
         std::shared_ptr<Serializer const> const& txn,
         std::shared_ptr<Serializer const> const& metaData) override;
 
+    // Insert the transaction, and return the hash of the SHAMap leaf node
+    // holding the transaction. The hash can be used to fetch the transaction
+    // directly, instead of traversing the SHAMap
+    // @param key transaction ID
+    // @param txn transaction
+    // @param metaData transaction metadata
+    // @return hash of SHAMap leaf node that holds the transaction
+    uint256
+    rawTxInsertWithHash(
+        uint256 const& key,
+        std::shared_ptr<Serializer const> const& txn,
+        std::shared_ptr<Serializer const> const& metaData);
+
     //--------------------------------------------------------------------------
 
     void

include/xrpl/ledger/helpers/NFTokenHelpers.h

@@ -20,6 +20,10 @@ removeTokenOffersWithLimit(
     Keylet const& directory,
     std::size_t maxDeletableOffers);
 
+/** Returns tesSUCCESS if NFToken has few enough offers that it can be burned */
+TER
+notTooManyOffers(ReadView const& view, uint256 const& nftokenID);
+
 /** Finds the specified token in the owner's token directory. */
 std::optional<STObject>
 findToken(ReadView const& view, AccountID const& owner, uint256 const& nftokenID);

include/xrpl/protocol/detail/features.macro

@@ -15,6 +15,7 @@
 // Add new amendments to the top of this list.
 // Keep it sorted in reverse chronological order.
 
+XRPL_FEATURE(DefragDirectories,          Supported::no,  VoteBehavior::DefaultNo)
 XRPL_FIX    (Cleanup3_2_0,                Supported::no, VoteBehavior::DefaultNo)
 XRPL_FEATURE(MPTokensV2,                  Supported::no, VoteBehavior::DefaultNo)
 XRPL_FIX    (Security3_1_3,               Supported::no, VoteBehavior::DefaultNo)

src/libxrpl/ledger/ApplyView.cpp

@@ -26,6 +26,14 @@ namespace xrpl {
 
 namespace directory {
 
+struct Gap
+{
+    uint64_t const page;
+    SLE::pointer node;
+    uint64_t const nextPage;
+    SLE::pointer next;
+};
+
 std::uint64_t
 createRoot(
     ApplyView& view,
@@ -126,7 +134,9 @@ insertPage(
     if (page == 0)
         return std::nullopt;
     if (!view.rules().enabled(fixDirectoryLimit) && page >= dirNodeMaxPages)  // Old pages limit
+    {
         return std::nullopt;
+    }
 
     // We are about to create a new node; we'll link it to
     // the chain first:
@@ -147,12 +157,8 @@ insertPage(
     // Save some space by not specifying the value 0 since it's the default.
     if (page != 1)
         node->setFieldU64(sfIndexPrevious, page - 1);
-    XRPL_ASSERT_PARTS(!nextPage, "xrpl::directory::insertPage", "nextPage has default value");
-    /* Reserved for future use when directory pages may be inserted in
-     * between two other pages instead of only at the end of the chain.
     if (nextPage)
         node->setFieldU64(sfIndexNext, nextPage);
-    */
     describe(node);
     view.insert(node);
 
@@ -168,7 +174,7 @@ ApplyView::dirAdd(
     uint256 const& key,
     std::function<void(std::shared_ptr<SLE> const&)> const& describe)
 {
-    auto root = peek(directory);
+    auto const root = peek(directory);
 
     if (!root)
     {
@@ -178,6 +184,43 @@ ApplyView::dirAdd(
 
     auto [page, node, indexes] = directory::findPreviousPage(*this, directory, root);
 
+    if (rules().enabled(featureDefragDirectories))
+    {
+        // If there are more nodes than just the root, and there's no space in
+        // the last one, walk backwards to find one with space, or to find one
+        // missing.
+        std::optional<directory::Gap> gapPages;
+        while (page && indexes.size() >= dirNodeMaxEntries)
+        {
+            // Find a page with space, or a gap in pages.
+            auto [prevPage, prevNode, prevIndexes] =
+                directory::findPreviousPage(*this, directory, node);
+            if (!gapPages && prevPage != page - 1)
+                gapPages.emplace(prevPage, prevNode, page, node);
+            page = prevPage;
+            node = prevNode;
+            indexes = prevIndexes;
+        }
+        // We looped through all the pages back to the root.
+        if (!page)
+        {
+            // If we found a gap, use it.
+            if (gapPages)
+            {
+                return directory::insertPage(
+                    *this,
+                    gapPages->page,
+                    gapPages->node,
+                    gapPages->nextPage,
+                    gapPages->next,
+                    key,
+                    directory,
+                    describe);
+            }
+            std::tie(page, node, indexes) = directory::findPreviousPage(*this, directory, root);
+        }
+    }
+
     // If there's space, we use it:
     if (indexes.size() < dirNodeMaxEntries)
     {

src/libxrpl/ledger/Ledger.cpp

@@ -14,6 +14,7 @@
 #include <xrpl/nodestore/NodeObject.h>
 #include <xrpl/protocol/Feature.h>
 #include <xrpl/protocol/Fees.h>
+#include <xrpl/protocol/HashPrefix.h>
 #include <xrpl/protocol/Indexes.h>
 #include <xrpl/protocol/KeyType.h>
 #include <xrpl/protocol/Keylet.h>
@@ -30,6 +31,7 @@
 #include <xrpl/protocol/Seed.h>
 #include <xrpl/protocol/Serializer.h>
 #include <xrpl/protocol/SystemParameters.h>
+#include <xrpl/protocol/digest.h>
 #include <xrpl/shamap/Family.h>
 #include <xrpl/shamap/SHAMap.h>
 #include <xrpl/shamap/SHAMapItem.h>
@@ -41,6 +43,7 @@
 #include <exception>
 #include <memory>
 #include <optional>
+#include <stdexcept>
 #include <utility>
 #include <vector>
 
@@ -490,14 +493,14 @@ void
 Ledger::rawErase(std::shared_ptr<SLE> const& sle)
 {
     if (!stateMap_.delItem(sle->key()))
-        LogicError("Ledger::rawErase: key not found");
+        Throw<std::logic_error>("Ledger::rawErase: key not found");
 }
 
 void
 Ledger::rawErase(uint256 const& key)
 {
     if (!stateMap_.delItem(key))
-        LogicError("Ledger::rawErase: key not found");
+        Throw<std::logic_error>("Ledger::rawErase: key not found");
 }
 
 void
@@ -507,7 +510,7 @@ Ledger::rawInsert(std::shared_ptr<SLE> const& sle)
     sle->add(ss);
     if (!stateMap_.addGiveItem(
             SHAMapNodeType::tnACCOUNT_STATE, make_shamapitem(sle->key(), ss.slice())))
-        LogicError("Ledger::rawInsert: key already exists");
+        Throw<std::logic_error>("Ledger::rawInsert: key already exists");
 }
 
 void
@@ -517,7 +520,7 @@ Ledger::rawReplace(std::shared_ptr<SLE> const& sle)
     sle->add(ss);
     if (!stateMap_.updateGiveItem(
             SHAMapNodeType::tnACCOUNT_STATE, make_shamapitem(sle->key(), ss.slice())))
-        LogicError("Ledger::rawReplace: key not found");
+        Throw<std::logic_error>("Ledger::rawReplace: key not found");
 }
 
 void
@@ -533,7 +536,27 @@ Ledger::rawTxInsert(
     s.addVL(txn->peekData());
     s.addVL(metaData->peekData());
     if (!txMap_.addGiveItem(SHAMapNodeType::tnTRANSACTION_MD, make_shamapitem(key, s.slice())))
-        LogicError("duplicate_tx: " + to_string(key));
+        Throw<std::logic_error>("duplicate_tx: " + to_string(key));
+}
+
+uint256
+Ledger::rawTxInsertWithHash(
+    uint256 const& key,
+    std::shared_ptr<Serializer const> const& txn,
+    std::shared_ptr<Serializer const> const& metaData)
+{
+    XRPL_ASSERT(metaData, "xrpl::Ledger::rawTxInsertWithHash : non-null metadata input");
+
+    // low-level - just add to table
+    Serializer s(txn->getDataLength() + metaData->getDataLength() + 16);
+    s.addVL(txn->peekData());
+    s.addVL(metaData->peekData());
+    auto item = make_shamapitem(key, s.slice());
+    auto hash = sha512Half(HashPrefix::txNode, item->slice(), item->key());
+    if (!txMap_.addGiveItem(SHAMapNodeType::tnTRANSACTION_MD, std::move(item)))
+        Throw<std::logic_error>("duplicate_tx: " + to_string(key));
+
+    return hash;
 }
 
 bool

src/libxrpl/ledger/helpers/NFTokenHelpers.cpp

@@ -621,6 +621,33 @@ removeTokenOffersWithLimit(ApplyView& view, Keylet const& directory, std::size_t
     return deletedOffersCount;
 }
 
+TER
+notTooManyOffers(ReadView const& view, uint256 const& nftokenID)
+{
+    std::size_t totalOffers = 0;
+
+    {
+        Dir const buys(view, keylet::nft_buys(nftokenID));
+        for (auto iter = buys.begin(); iter != buys.end(); iter.next_page())
+        {
+            totalOffers += iter.page_size();
+            if (totalOffers > maxDeletableTokenOfferEntries)
+                return tefTOO_BIG;
+        }
+    }
+
+    {
+        Dir const sells(view, keylet::nft_sells(nftokenID));
+        for (auto iter = sells.begin(); iter != sells.end(); iter.next_page())
+        {
+            totalOffers += iter.page_size();
+            if (totalOffers > maxDeletableTokenOfferEntries)
+                return tefTOO_BIG;
+        }
+    }
+    return tesSUCCESS;
+}
+
 bool
 deleteTokenOffer(ApplyView& view, std::shared_ptr<SLE> const& offer)
 {