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/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/basics/Number.cpp

@@ -222,12 +222,9 @@ Number::Guard::bringIntoRange(
     {
         mantissa *= 10;
         --exponent;
-        std::cout << "bringIntoRange. mantissa*=10: " << mantissa << ", exponent: " << exponent
-                  << std::endl;
     }
     if (exponent < minExponent)
     {
-        std::cout << "bringIntoRange. zero\n";
         constexpr Number zero = Number{};
 
         negative = zero.negative_;
@@ -249,50 +246,13 @@ Number::Guard::doRoundUp(
     auto r = round();
     if (r == 1 || (r == 0 && (mantissa & 1) == 1))
     {
-        std::cout << "doRoundUp. r: " << r << std::endl;
-        if (isFeatureEnabled(fixCleanup3_2_0) || !getCurrentTransactionRules())
+        ++mantissa;
+        // Ensure mantissa after incrementing fits within both the
+        // min/maxMantissa range and is a valid "rep".
+        if (mantissa > maxMantissa || mantissa > maxRep)
         {
-            // Ensure mantissa after incrementing fits within both the
-            // min/maxMantissa range and is a valid "rep".
-            if (mantissa < maxMantissa && mantissa < maxRep)
-            {
-                // Nothing unusual here, just increment the mantissa
-                ++mantissa;
-                std::cout << "\tmantissa++: " << mantissa << std::endl;
-            }
-            else
-            {
-                // Incrementing the mantissa will require dividing, which will require rounding. So
-                // _don't_ increment the mantissa. Instead, divide and round recursively. It should
-                // be impossible to recurse more than once, because once the mantissa is divided by
-                // 10, it will be _well_ under maxMantissa and maxRep, so adding 1 will have no
-                // change of bringing it back over.
-                push(mantissa % 10);
-                mantissa /= 10;
-                ++exponent;
-                XRPL_ASSERT_PARTS(
-                    mantissa < maxMantissa && mantissa < maxRep,
-                    "xrpl::Number::Guard::doRoundUp",
-                    "can't recurse more than once");
-                std::cout << "\tmantissa/=10: " << mantissa << ", exponent: " << exponent
-                          << std::endl;
-                // Here be dragons
-                doRoundUp(negative, mantissa, exponent, minMantissa, maxMantissa, location);
-                return;
-            }
-        }
-        else
-        {
-            // Need to preserve the incorrect behavior until the fix amendment can be retired,
-            // because otherwise would risk an unplanned ledger fork.
-            ++mantissa;
-            // Ensure mantissa after incrementing fits within both the
-            // min/maxMantissa range and is a valid "rep".
-            if (mantissa > maxMantissa || mantissa > maxRep)
-            {
-                mantissa /= 10;
-                ++exponent;
-            }
+            mantissa /= 10;
+            ++exponent;
         }
     }
     bringIntoRange(negative, mantissa, exponent, minMantissa);
@@ -707,8 +667,6 @@ Number::operator*=(Number const& y)
     auto const& minMantissa = range.min;
     auto const& maxMantissa = range.max;
 
-    std::cout << "zn: " << zn << ", zm: " << zm << ", ze: " << ze << std::endl;
-
     while (zm > maxMantissa || zm > maxRep)
     {
         // The following is optimization for:
@@ -717,9 +675,6 @@ Number::operator*=(Number const& y)
         g.push(divu10(zm));
         ++ze;
     }
-
-    std::cout << "zn: " << zn << ", zm: " << zm << ", ze: " << ze << std::endl;
-
     xm = static_cast<internalrep>(zm);
     xe = ze;
     g.doRoundUp(
@@ -832,7 +787,8 @@ Number::operator/=(Number const& y)
     return *this;
 }
 
-Number::operator rep() const
+Number::
+operator rep() const
 {
     rep drops = mantissa();
     int offset = exponent();

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/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)
 {

src/test/basics/Number_test.cpp

@@ -1584,101 +1584,3 @@ public:
 BEAST_DEFINE_TESTSUITE(Number, basics, xrpl);
 
 }  // namespace xrpl
-#include <xrpl/basics/Number.h>
-#include <xrpl/beast/unit_test.h>
-#include <xrpl/protocol/AccountID.h>
-#include <xrpl/protocol/MPTIssue.h>
-#include <xrpl/protocol/STAmount.h>
-
-#include <boost/multiprecision/cpp_int.hpp>
-
-#include <cstdint>
-#include <limits>
-#include <sstream>
-#include <string>
-
-namespace xrpl {
-
-class NumberUpwardWrongDirection_test : public beast::unit_test::suite
-{
-    using BigInt = boost::multiprecision::cpp_int;
-
-    static std::string
-    fmt(BigInt const& value)
-    {
-        std::ostringstream os;
-        os << value;
-        auto s = os.str();
-        std::string out;
-        int count = 0;
-        for (auto it = s.rbegin(); it != s.rend(); ++it)
-        {
-            if (count && count % 3 == 0)
-                out.insert(out.begin(), '_');
-            out.insert(out.begin(), *it);
-            ++count;
-        }
-        return out;
-    }
-
-public:
-    void
-    testUpwardRoundsDown()
-    {
-        testcase << "upward rounding produces a value below exact at maxRep cusp";
-
-        auto const origScale = Number::getMantissaScale();
-        auto const origRound = Number::setround(Number::upward);
-        Number::setMantissaScale(MantissaRange::large);
-
-        constexpr std::int64_t aValue = 1'000'000'000'000'049'863LL;
-        constexpr std::int64_t bValue = 9'223'372'036'854'315'903LL;
-
-        // JSON -> STAmount -> Number
-        AccountID const dummyIssuer = AccountID{42u};
-        MPTIssue const issue(/*sequence=*/1u, dummyIssuer);
-
-        STAmount const amountA{MPTAmount{aValue}, issue};
-        STAmount const amountB{MPTAmount{bValue}, issue};
-
-        // Public conversion operator: STAmount::operator Number() const.
-        Number const a = amountA;
-        Number const b = amountB;
-        Number const product = a * b;
-
-        // Exact reference in BigInt.
-        BigInt const exactProduct = BigInt(aValue) * BigInt(bValue);
-
-        // What Number actually stored.
-        BigInt storedValue = BigInt(product.mantissa());
-        for (int i = 0; i < product.exponent(); ++i)
-            storedValue *= 10;
-
-        BigInt const signedDifference = storedValue - exactProduct;
-
-        log << "\n"
-            << "  a              = " << fmt(BigInt(aValue)) << "\n"
-            << "  b              = " << fmt(BigInt(bValue)) << "\n"
-            << "  exact a*b      = " << fmt(exactProduct) << "\n"
-            << "  stored         = " << fmt(storedValue) << "\n"
-            << "  stored - exact = " << fmt(signedDifference) << "\n"
-            << "  upward         = " << (signedDifference >= 0 ? "held" : "VIOLATED") << "\n";
-
-        BEAST_EXPECT(signedDifference >= 0);
-        BEAST_EXPECT(product.mantissa() == (std::numeric_limits<std::int64_t>::max() /10) + 1);
-        BEAST_EXPECT(product.exponent() == 19);
-
-        Number::setround(origRound);
-        Number::setMantissaScale(origScale);
-    }
-
-    void
-    run() override
-    {
-        testUpwardRoundsDown();
-    }
-};
-
-BEAST_DEFINE_TESTSUITE(NumberUpwardWrongDirection, basics, ripple);
-
-}  // namespace xrpl