Merge branch 'develop' into bthomee/serialize

include/xrpl/protocol/Serializer.h

@@ -24,7 +24,7 @@ private:
     Blob data_;
 
 public:
-    explicit Serializer(int n = 256)
+    explicit Serializer(std::size_t n = 256)
     {
         data_.reserve(n);
     }

include/xrpl/shamap/SHAMapAccountStateLeafNode.h

@@ -45,6 +45,12 @@ public:
         hash_ = SHAMapHash{sha512Half(HashPrefix::LeafNode, item_->slice(), item_->key())};
     }
 
+    std::size_t
+    sizeForWire() const final
+    {
+        return item_->size() + uint256::kBytes + sizeof(std::uint8_t);
+    }
+
     void
     serializeForWire(Serializer& s) const final
     {

include/xrpl/shamap/SHAMapInnerNode.h

@@ -17,6 +17,12 @@ public:
     /** Each inner node has 16 children (the 'radix tree' part of the map) */
     static constexpr unsigned int kBranchFactor = 16;
 
+    /** Branch count below which compressed wire format is used instead of full.
+        Compressed format encodes only populated branches, costing 33 bytes each
+        plus a 1-byte type tag.  Full format always emits all 16 hashes (513
+        bytes). At this threshold, compressed is still smaller than full. */
+    static constexpr unsigned int kCompressedThreshold = 12;
+
 private:
     /** Opaque type that contains the `hashes` array (array of type
        `SHAMapHash`) and the `children` array (array of type
@@ -149,6 +155,9 @@ public:
     void
     updateHashDeep();
 
+    std::size_t
+    sizeForWire() const override;
+
     void
     serializeForWire(Serializer&) const override;
 

include/xrpl/shamap/SHAMapLeafNode.h

@@ -36,6 +36,9 @@ public:
         return false;
     }
 
+    std::size_t
+    sizeForWire() const override = 0;
+
     void
     invariants(bool isRoot = false) const final;
 

include/xrpl/shamap/SHAMapTreeNode.h

@@ -142,6 +142,10 @@ public:
     virtual bool
     isInner() const = 0;
 
+    /** Returns the exact number of bytes that serializeForWire will emit. */
+    virtual std::size_t
+    sizeForWire() const = 0;
+
     /** Serialize the node in a format appropriate for sending over the wire */
     virtual void
     serializeForWire(Serializer&) const = 0;

include/xrpl/shamap/SHAMapTxLeafNode.h

@@ -44,6 +44,12 @@ public:
         hash_ = SHAMapHash{sha512Half(HashPrefix::TransactionId, item_->slice())};
     }
 
+    std::size_t
+    sizeForWire() const final
+    {
+        return item_->size() + sizeof(std::uint8_t);
+    }
+
     void
     serializeForWire(Serializer& s) const final
     {

include/xrpl/shamap/SHAMapTxPlusMetaLeafNode.h

@@ -45,6 +45,12 @@ public:
         hash_ = SHAMapHash{sha512Half(HashPrefix::TxNode, item_->slice(), item_->key())};
     }
 
+    std::size_t
+    sizeForWire() const final
+    {
+        return item_->size() + uint256::kBytes + sizeof(std::uint8_t);
+    }
+
     void
     serializeForWire(Serializer& s) const final
     {

src/libxrpl/shamap/SHAMapInnerNode.cpp

@@ -219,13 +219,22 @@ SHAMapInnerNode::updateHashDeep()
     updateHash();
 }
 
+std::size_t
+SHAMapInnerNode::sizeForWire() const
+{
+    auto const n = getBranchCount();
+    if (n < kCompressedThreshold)
+        return (n * (uint256::kBytes + sizeof(std::uint8_t))) + sizeof(std::uint8_t);
+    return (kBranchFactor * uint256::kBytes) + sizeof(std::uint8_t);
+}
+
 void
 SHAMapInnerNode::serializeForWire(Serializer& s) const
 {
     XRPL_ASSERT(!isEmpty(), "xrpl::SHAMapInnerNode::serializeForWire : is non-empty");
 
     // If the node is sparse, then only send non-empty branches:
-    if (getBranchCount() < 12)
+    if (getBranchCount() < kCompressedThreshold)
     {
         // compressed node
         auto hashes = hashesAndChildren_.getHashes();

src/libxrpl/shamap/SHAMapSync.cpp

@@ -449,17 +449,14 @@ SHAMap::getNodeFat(
     std::stack<std::tuple<SHAMapTreeNode*, SHAMapNodeID, int>> stack;
     stack.emplace(node, nodeID, depth);
 
-    Serializer s(8192);
-
     while (!stack.empty())
     {
         std::tie(node, nodeID, depth) = stack.top();
         stack.pop();
 
-        // Add this node to the reply
-        s.erase();
+        Serializer s(node->sizeForWire());
         node->serializeForWire(s);
-        data.emplace_back(nodeID, s.getData());
+        data.emplace_back(nodeID, std::move(s.modData()));
 
         if (node->isInner())
         {
@@ -487,9 +484,9 @@ SHAMap::getNodeFat(
                         else if (childNode->isInner() || fatLeaves)
                         {
                             // Just include this node
-                            s.erase();
-                            childNode->serializeForWire(s);
-                            data.emplace_back(childID, s.getData());
+                            Serializer cs(childNode->sizeForWire());
+                            childNode->serializeForWire(cs);
+                            data.emplace_back(childID, std::move(cs.modData()));
                         }
                     }
                 }
@@ -794,7 +791,7 @@ SHAMap::getProofPath(uint256 const& key) const
     path.reserve(stack.size());
     while (!stack.empty())
     {
-        Serializer s;
+        Serializer s(stack.top().first->sizeForWire());
         stack.top().first->serializeForWire(s);
         path.emplace_back(std::move(s.modData()));
         stack.pop();

src/tests/libxrpl/CMakeLists.txt

@@ -27,6 +27,7 @@ set(test_modules
     basics
     crypto
     json
+    shamap
     tx
     protocol_autogen
 )

src/tests/libxrpl/shamap/SHAMapNodeSize.cpp

@@ -0,0 +1,83 @@
+#include <xrpl/basics/IntrusivePointer.h>
+#include <xrpl/basics/IntrusivePointer.ipp>  // IWYU pragma: keep
+#include <xrpl/basics/Slice.h>
+#include <xrpl/basics/base_uint.h>
+#include <xrpl/protocol/Serializer.h>
+#include <xrpl/shamap/SHAMapAccountStateLeafNode.h>
+#include <xrpl/shamap/SHAMapInnerNode.h>
+#include <xrpl/shamap/SHAMapItem.h>
+#include <xrpl/shamap/SHAMapTreeNode.h>
+#include <xrpl/shamap/SHAMapTxLeafNode.h>
+#include <xrpl/shamap/SHAMapTxPlusMetaLeafNode.h>
+
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+namespace xrpl {
+
+// Build an inner node with exactly n populated branches via the full wire format round-trip so we
+// get a properly initialized SHAMapInnerNode.
+static SHAMapTreeNodePtr
+makeInnerWithBranches(unsigned int n)
+{
+    std::vector<std::uint8_t> buf(SHAMapInnerNode::kBranchFactor * uint256::kBytes, 0);
+    for (unsigned int i = 0; i < n; ++i)
+    {
+        std::uint8_t* p = buf.data() + (i * uint256::kBytes);
+        std::fill(p, p + uint256::kBytes, static_cast<std::uint8_t>(i + 1));
+    }
+
+    return SHAMapInnerNode::makeFullInner(Slice(buf.data(), buf.size()), SHAMapHash{}, false);
+}
+
+// Verifies sizeForWire() for every branch count from 1 to 16, which covers the compressed format
+// (< kCompressedThreshold), the threshold boundary, and the full format (>= kCompressedThreshold).
+TEST(SHAMapNodeSize, InnerNode)
+{
+    for (unsigned int n = 1; n <= SHAMapInnerNode::kBranchFactor; ++n)
+    {
+        auto const node = makeInnerWithBranches(n);
+        Serializer s(node->sizeForWire());
+        node->serializeForWire(s);
+        EXPECT_EQ(node->sizeForWire(), s.size()) << "branch count: " << n;
+    }
+}
+
+// Verifies sizeForWire() for each leaf node type across a range of payload sizes.
+TEST(SHAMapNodeSize, LeafNodes)
+{
+    for (std::size_t const payloadSize : {12u, 64u, 256u})
+    {
+        uint256 const key{};
+        std::vector<std::uint8_t> const payload(payloadSize, 0xAB);
+        Slice const data(payload.data(), payload.size());
+        auto item = makeShamapitem(key, data);
+
+        {
+            auto const tx = intr_ptr::makeShared<SHAMapTxLeafNode>(item, 1);
+            Serializer s(tx->sizeForWire());
+            tx->serializeForWire(s);
+            EXPECT_EQ(tx->sizeForWire(), s.size()) << "payload: " << payloadSize;
+        }
+
+        {
+            auto const txMeta = intr_ptr::makeShared<SHAMapTxPlusMetaLeafNode>(item, 1);
+            Serializer s(txMeta->sizeForWire());
+            txMeta->serializeForWire(s);
+            EXPECT_EQ(txMeta->sizeForWire(), s.size()) << "payload: " << payloadSize;
+        }
+
+        {
+            auto const acct = intr_ptr::makeShared<SHAMapAccountStateLeafNode>(item, 1);
+            Serializer s(acct->sizeForWire());
+            acct->serializeForWire(s);
+            EXPECT_EQ(acct->sizeForWire(), s.size()) << "payload: " << payloadSize;
+        }
+    }
+}
+
+}  // namespace xrpl