Merge branch 'develop' into ximinez/directory

* XRPLF/develop:
  Explicitly trim the heap after cache sweeps (6022)
  ci: Update prepare-runner action to fix macOS build environment (empty)
  Disable featureBatch and fixBatchInnerSigs amendments (6402)
  chore: Add nix development environment (6314)

include/xrpl/beast/rfc2616.h

@@ -10,7 +10,6 @@
 #include <cctype>
 #include <iterator>
 #include <string>
-#include <string_view>
 #include <vector>
 
 namespace beast {
@@ -182,7 +181,7 @@ split_commas(FwdIt first, FwdIt last)
 
 template <class Result = std::vector<std::string>>
 Result
-split_commas(std::string_view const& s)
+split_commas(boost::beast::string_view const& s)
 {
     return split_commas(s.begin(), s.end());
 }

include/xrpl/json/Output.h

@@ -1,19 +1,20 @@
 #pragma once
 
+#include <boost/beast/core/string.hpp>
+
 #include <functional>
 #include <string>
-#include <string_view>
 
 namespace Json {
 
 class Value;
 
-using Output = std::function<void(std::string_view const&)>;
+using Output = std::function<void(boost::beast::string_view const&)>;
 
 inline Output
 stringOutput(std::string& s)
 {
-    return [&](std::string_view const& b) { s.append(b.data(), b.size()); };
+    return [&](boost::beast::string_view const& b) { s.append(b.data(), b.size()); };
 }
 
 /** Writes a minimal representation of a Json value to an Output in O(n) time.

include/xrpl/protocol/detail/features.macro

@@ -16,6 +16,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   (PermissionedDomainInvariant, Supported::yes, VoteBehavior::DefaultNo)
 XRPL_FIX    (ExpiredNFTokenOfferRemoval, Supported::yes, VoteBehavior::DefaultNo)
 XRPL_FIX    (BatchInnerSigs,             Supported::no, VoteBehavior::DefaultNo)

include/xrpl/server/detail/BaseWSPeer.h

@@ -17,7 +17,6 @@
 
 #include <functional>
 #include <list>
-#include <string_view>
 
 namespace xrpl {
 
@@ -49,7 +48,8 @@ private:
     bool ping_active_ = false;
     boost::beast::websocket::ping_data payload_;
     error_code ec_;
-    std::function<void(boost::beast::websocket::frame_type, std::string_view)> control_callback_;
+    std::function<void(boost::beast::websocket::frame_type, boost::beast::string_view)>
+        control_callback_;
 
 public:
     template <class Body, class Headers>
@@ -137,7 +137,7 @@ protected:
     on_ping(error_code const& ec);
 
     void
-    on_ping_pong(boost::beast::websocket::frame_type kind, std::string_view payload);
+    on_ping_pong(boost::beast::websocket::frame_type kind, boost::beast::string_view payload);
 
     void
     on_timer(error_code ec);
@@ -414,11 +414,11 @@ template <class Handler, class Impl>
 void
 BaseWSPeer<Handler, Impl>::on_ping_pong(
     boost::beast::websocket::frame_type kind,
-    std::string_view payload)
+    boost::beast::string_view payload)
 {
     if (kind == boost::beast::websocket::frame_type::pong)
     {
-        std::string_view p(payload_.begin(), payload_.size());
+        boost::beast::string_view p(payload_.begin());
         if (payload == p)
         {
             close_on_timer_ = false;

src/libxrpl/json/Writer.cpp

@@ -8,7 +8,6 @@
 #include <set>
 #include <stack>
 #include <string>
-#include <string_view>
 #include <utility>
 #include <vector>
 
@@ -88,14 +87,14 @@ public:
     }
 
     void
-    output(std::string_view const& bytes)
+    output(boost::beast::string_view const& bytes)
     {
         markStarted();
         output_(bytes);
     }
 
     void
-    stringOutput(std::string_view const& bytes)
+    stringOutput(boost::beast::string_view const& bytes)
     {
         markStarted();
         std::size_t position = 0, writtenUntil = 0;

src/libxrpl/ledger/ApplyView.cpp

@@ -10,6 +10,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,
@@ -111,7 +119,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:
@@ -133,12 +143,8 @@ insertPage(
     // 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);
 
@@ -154,7 +160,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)
     {
@@ -164,6 +170,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/xrpld/overlay/detail/ProtocolVersion.cpp

@@ -59,7 +59,7 @@ to_string(ProtocolVersion const& p)
 }
 
 std::vector<ProtocolVersion>
-parseProtocolVersions(std::string_view const& value)
+parseProtocolVersions(boost::beast::string_view const& value)
 {
     static boost::regex re(
         "^"                        // start of line
@@ -130,7 +130,7 @@ negotiateProtocolVersion(std::vector<ProtocolVersion> const& versions)
 }
 
 std::optional<ProtocolVersion>
-negotiateProtocolVersion(std::string_view const& versions)
+negotiateProtocolVersion(boost::beast::string_view const& versions)
 {
     auto const them = parseProtocolVersions(versions);
 

src/xrpld/overlay/detail/ProtocolVersion.h

@@ -1,9 +1,10 @@
 #pragma once
 
+#include <boost/beast/core/string.hpp>
+
 #include <cstdint>
 #include <optional>
 #include <string>
-#include <string_view>
 #include <utility>
 #include <vector>
 
@@ -38,7 +39,7 @@ to_string(ProtocolVersion const& p);
           no duplicates and will be sorted in ascending protocol order.
 */
 std::vector<ProtocolVersion>
-parseProtocolVersions(std::string_view const& s);
+parseProtocolVersions(boost::beast::string_view const& s);
 
 /** Given a list of supported protocol versions, choose the one we prefer. */
 std::optional<ProtocolVersion>
@@ -46,7 +47,7 @@ negotiateProtocolVersion(std::vector<ProtocolVersion> const& versions);
 
 /** Given a list of supported protocol versions, choose the one we prefer. */
 std::optional<ProtocolVersion>
-negotiateProtocolVersion(std::string_view const& versions);
+negotiateProtocolVersion(boost::beast::string_view const& versions);
 
 /** The list of all the protocol versions we support. */
 std::string const&

src/xrpld/rpc/detail/ServerHandler.cpp

@@ -34,7 +34,6 @@
 #include <algorithm>
 #include <memory>
 #include <stdexcept>
-#include <string_view>
 
 namespace xrpl {
 
@@ -231,7 +230,7 @@ ServerHandler::onHandoff(
 static inline Json::Output
 makeOutput(Session& session)
 {
-    return [&](std::string_view const& b) { session.write(b.data(), b.size()); };
+    return [&](boost::beast::string_view const& b) { session.write(b.data(), b.size()); };
 }
 
 static std::map<std::string, std::string>
@@ -528,14 +527,11 @@ ServerHandler::processSession(
         makeOutput(*session),
         coro,
         forwardedFor(session->request()),
-        [&]() -> std::string_view {
+        [&] {
             auto const iter = session->request().find("X-User");
             if (iter != session->request().end())
-            {
-                auto const val = iter->value();
-                return std::string_view(val.data(), val.size());
-            }
-            return std::string_view{};
+                return iter->value();
+            return boost::beast::string_view{};
         }());
 
     if (beast::rfc2616::is_keep_alive(session->request()))