chore: Bump version to 3.4.0-b1 (#8102)

Co-authored-by: Cursor <cursoragent@cursor.com>

include/xrpl/shamap/SHAMap.h

@@ -14,7 +14,6 @@
 #include <xrpl/shamap/SHAMapItem.h>
 #include <xrpl/shamap/SHAMapLeafNode.h>
 #include <xrpl/shamap/SHAMapMissingNode.h>
-#include <xrpl/shamap/SHAMapNodeID.h>
 #include <xrpl/shamap/SHAMapTreeNode.h>
 
 #include <condition_variable>
@@ -421,107 +420,7 @@ public:
     invariants() const;
 
 private:
-    /**
-     * A path from the root of the map down to some node, pairing each node with the ID naming its
-     * position.
-     *
-     * The two halves of an entry must agree, and the only way to get that wrong is to compute an ID
-     * from the wrong branch. So this type does not accept an ID at all: every push takes the branch
-     * being descended and derives the ID itself, so a node and its ID cannot disagree. Reads are
-     * exposed through the same accessors a std::stack would offer.
-     */
-    class NodePathStack
-    {
-    public:
-        [[nodiscard]] bool
-        empty() const
-        {
-            return stack_.empty();
-        }
-
-        [[nodiscard]] std::size_t
-        size() const
-        {
-            return stack_.size();
-        }
-
-        [[nodiscard]] std::pair<SHAMapTreeNodePtr, SHAMapNodeID> const&
-        top() const
-        {
-            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::top : non-empty stack");
-            return stack_.top();
-        }
-
-        void
-        pop()
-        {
-            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::pop : non-empty stack");
-            stack_.pop();
-        }
-
-        void
-        clear()
-        {
-            stack_ = {};
-        }
-
-        /**
-         * Start a path at the root of the map, whose ID is the zero-depth ID by definition.
-         */
-        void
-        pushRoot(SHAMapTreeNodePtr node)
-        {
-            XRPL_ASSERT(stack_.empty(), "xrpl::SHAMap::NodePathStack::pushRoot : empty stack");
-            stack_.emplace(std::move(node), SHAMapNodeID{});
-        }
-
-        /**
-         * Extend the path to the child of the current node reached by `branch`.
-         *
-         * A node keeps the depth it was reached at, never a normalized kLeafDepth. Only a leaf may
-         * sit at kLeafDepth, since an inner node there would have no branch left to select.
-         */
-        void
-        pushChild(SHAMapTreeNodePtr node, unsigned int branch)
-        {
-            XRPL_ASSERT(node, "xrpl::SHAMap::NodePathStack::pushChild : non-null node input");
-            XRPL_ASSERT(
-                !stack_.empty(), "xrpl::SHAMap::NodePathStack::pushChild : non-empty stack");
-            auto childID = stack_.top().second.getChildNodeID(branch);
-            XRPL_ASSERT_IF(
-                node->isInner(),
-                childID.getDepth() < kLeafDepth,
-                "xrpl::SHAMap::NodePathStack::pushChild : inner node above leaf depth");
-            XRPL_ASSERT_IF(
-                node->isLeaf(),
-                childID.isPrefixOf(leafKey(*node)),
-                "xrpl::SHAMap::NodePathStack::pushChild : leaf key below branch");
-            stack_.emplace(std::move(node), std::move(childID));
-        }
-
-        /**
-         * Extend the path to a node lying on the path to `target`.
-         *
-         * For nodes not reached by descending a known branch: the walk tracks only the key it is
-         * heading for, or the node is newly created. Either way `target` selects the branch.
-         */
-        void
-        pushNode(SHAMapTreeNodePtr node, uint256 const& target)
-        {
-            if (stack_.empty())
-            {
-                pushRoot(std::move(node));
-            }
-            else
-            {
-                pushChild(std::move(node), selectBranch(stack_.top().second, target));
-            }
-        }
-
-    private:
-        std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>> stack_;
-    };
-
+    using SharedPtrNodeStack = std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>>;
     using DeltaRef =
         std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>;
 
@@ -548,7 +447,7 @@ private:
      * Update hashes up to the root
      */
     void
-    dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr terminal);
+    dirtyUp(SharedPtrNodeStack& stack, uint256 const& target, SHAMapTreeNodePtr terminal);
 
     /**
      * Walk towards the specified id, returning the node.  Caller must check
@@ -556,7 +455,7 @@ private:
      * id
      */
     SHAMapLeafNode*
-    walkTowardsKey(uint256 const& id, NodePathStack* stack = nullptr) const;
+    walkTowardsKey(uint256 const& id, SharedPtrNodeStack* stack = nullptr) const;
     /**
      * Return nullptr if key not found
      */
@@ -583,19 +482,27 @@ private:
     SHAMapTreeNodePtr
     writeNode(NodeObjectType t, SHAMapTreeNodePtr node) const;
 
-    // direction in which a scan walks an inner node's branches
+    // returns the first item at or below this node
+    SHAMapLeafNode*
+    firstBelow(SHAMapTreeNodePtr node, SharedPtrNodeStack& stack, unsigned int branch = 0u) const;
+
+    // returns the last item at or below this node
+    SHAMapLeafNode*
+    lastBelow(
+        SHAMapTreeNodePtr node,
+        SharedPtrNodeStack& stack,
+        unsigned int branch = kBranchFactor) const;
+
+    // direction in which belowHelper scans an inner node's branches
     enum class BelowDirection { First, Last };
 
-    /**
-     * Returns the first or last item at or below the node already on top of `stack`, extending
-     * `stack` with the path walked to reach it.
-     */
+    // helper function for firstBelow and lastBelow
     SHAMapLeafNode*
-    belowHelper(NodePathStack& stack, BelowDirection direction) const;
-
-    // helper function for upperBound and lowerBound
-    ConstIterator
-    boundHelper(uint256 const& id, BelowDirection direction) const;
+    belowHelper(
+        SHAMapTreeNodePtr node,
+        SharedPtrNodeStack& stack,
+        unsigned int branch,
+        BelowDirection direction) const;
 
     // Simple descent
     // Get a child of the specified node
@@ -643,9 +550,9 @@ private:
     hasLeafNode(uint256 const& tag, SHAMapHash const& hash) const;
 
     SHAMapLeafNode const*
-    peekFirstItem(NodePathStack& stack) const;
+    peekFirstItem(SharedPtrNodeStack& stack) const;
     SHAMapLeafNode const*
-    peekNextItem(uint256 const& id, NodePathStack& stack) const;
+    peekNextItem(uint256 const& id, SharedPtrNodeStack& stack) const;
     bool
     walkBranch(
         SHAMapTreeNode* node,
@@ -790,7 +697,7 @@ public:
     using pointer = value_type const*;
 
 private:
-    NodePathStack stack_;
+    SharedPtrNodeStack stack_;
     SHAMap const* map_ = nullptr;
     pointer item_ = nullptr;
 
@@ -816,7 +723,7 @@ public:
 private:
     explicit ConstIterator(SHAMap const* map);
     ConstIterator(SHAMap const* map, std::nullptr_t);
-    ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack);
+    ConstIterator(SHAMap const* map, pointer item, SharedPtrNodeStack&& stack);
 
     friend bool
     operator==(ConstIterator const& x, ConstIterator const& y);
@@ -835,7 +742,10 @@ inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map, std::nullptr_t) :
 {
 }
 
-inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack)
+inline SHAMap::ConstIterator::ConstIterator(
+    SHAMap const* map,
+    pointer item,
+    SharedPtrNodeStack&& stack)
     : stack_(std::move(stack)), map_(map), item_(item)
 {
 }

src/libxrpl/ledger/helpers/RippleStateHelpers.cpp

@@ -584,9 +584,15 @@ requireAuth(ReadView const& view, Issue const& issue, AccountID const& account,
     {
         if (trustLine)
         {
-            return trustLine->isFlag((account > issue.account) ? lsfLowAuth : lsfHighAuth)
-                ? tesSUCCESS
-                : TER{tecNO_AUTH};
+            if (trustLine->isFlag((account > issue.account) ? lsfLowAuth : lsfHighAuth))
+                return tesSUCCESS;
+
+            // A pseudo-account cannot submit transactions and only stores assets for the object
+            // that owns it, so it is implicitly authorized.
+            if (view.rules().enabled(fixCleanup3_4_0) && isPseudoAccount(view, account))
+                return tesSUCCESS;
+
+            return TER{tecNO_AUTH};
         }
         return TER{tecNO_LINE};
     }

src/libxrpl/protocol/BuildInfo.cpp

@@ -23,7 +23,7 @@ namespace {
 //------------------------------------------------------------------------------
 // clang-format off
 // NOLINTNEXTLINE(readability-identifier-naming)
-char const* const versionString = "3.4.0-b0"
+char const* const versionString = "3.4.0-b1"
     // clang-format on
     ;
 

src/libxrpl/shamap/SHAMap.cpp

@@ -97,7 +97,7 @@ SHAMap::snapShot(bool isMutable) const
 }
 
 void
-SHAMap::dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr child)
+SHAMap::dirtyUp(SharedPtrNodeStack& stack, uint256 const& target, SHAMapTreeNodePtr child)
 {
     // walk the tree up from through the inner nodes to the root_
     // update hashes and links
@@ -126,34 +126,29 @@ SHAMap::dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr c
 }
 
 SHAMapLeafNode*
-SHAMap::walkTowardsKey(uint256 const& id, NodePathStack* stack) const
+SHAMap::walkTowardsKey(uint256 const& id, SharedPtrNodeStack* stack) const
 {
     XRPL_ASSERT(
         stack == nullptr || stack->empty(), "xrpl::SHAMap::walkTowardsKey : empty stack input");
     auto inNode = root_;
     SHAMapNodeID nodeID;
 
-    // Every node on this walk lies on the path to `id`, so the stack can derive each ID from the
-    // branch `id` selects at the node above it.
-    auto pushCurrent = [&] {
-        if (stack != nullptr)
-            stack->pushNode(inNode, id);
-    };
-
     while (inNode->isInner())
     {
-        pushCurrent();
+        if (stack != nullptr)
+            stack->emplace(inNode, nodeID);
 
-        auto& inner = safeDowncast<SHAMapInnerNode&>(*inNode);
+        auto const inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(inNode);
         auto const branch = selectBranch(nodeID, id);
-        if (inner.isEmptyBranch(branch))
+        if (inner->isEmptyBranch(branch))
             return nullptr;
 
-        inNode = descendThrow(inner, branch);
+        inNode = descendThrow(*inner, branch);
         nodeID = nodeID.getChildNodeID(branch);
     }
 
-    pushCurrent();
+    if (stack != nullptr)
+        stack->emplace(inNode, nodeID);
     return safeDowncast<SHAMapLeafNode*>(inNode.get());
 }
 
@@ -433,40 +428,65 @@ SHAMap::unshareNode(intr_ptr::SharedPtr<Node> node, SHAMapNodeID const& nodeID)
 }
 
 SHAMapLeafNode*
-SHAMap::belowHelper(NodePathStack& stack, BelowDirection direction) const
+SHAMap::belowHelper(
+    SHAMapTreeNodePtr node,
+    SharedPtrNodeStack& stack,
+    unsigned int branch,
+    BelowDirection direction) const
 {
-    XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::belowHelper : non-empty stack input");
-    if (auto const& top = stack.top().first; top->isLeaf())
-        return safeDowncast<SHAMapLeafNode*>(top.get());
-
-    // The stack owns the node/ID pairing, so descending is only ever "push the branch we took".
-    // `scanned` counts how many branches of the current node we have examined; the branch we look
-    // at is derived from it, so no index ever goes out of range. `inner` tracks the node on top of
-    // the stack, which keeps it alive, so it only needs recomputing after a push.
-    auto* inner = safeDowncast<SHAMapInnerNode*>(stack.top().first.get());
+    if (node->isLeaf())
+    {
+        auto n = intr_ptr::staticPointerCast<SHAMapLeafNode>(node);
+        stack.push({node, {kLeafDepth, n->peekItem()->key()}});
+        return n.get();
+    }
+    auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
+    if (stack.empty())
+    {
+        stack.emplace(inner, SHAMapNodeID{});
+    }
+    else
+    {
+        stack.emplace(inner, stack.top().second.getChildNodeID(branch));
+    }
+    // `scanned` counts how many branches of `inner` we have examined; the branch we look at is
+    // derived from it, so no index ever goes out of range.
     for (auto scanned = 0u; scanned < kBranchFactor;)
     {
         auto const childBranch =
             (direction == BelowDirection::Last) ? (kBranchFactor - 1u - scanned) : scanned;
 
-        if (inner->isEmptyBranch(childBranch))
+        if (!inner->isEmptyBranch(childBranch))
+        {
+            node.adopt(descendThrow(inner.get(), childBranch));
+            XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::belowHelper : non-empty stack");
+            if (node->isLeaf())
+            {
+                auto n = intr_ptr::staticPointerCast<SHAMapLeafNode>(node);
+                stack.push({n, {kLeafDepth, n->peekItem()->key()}});
+                return n.get();
+            }
+            inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
+            stack.emplace(inner, stack.top().second.getChildNodeID(branch));
+            scanned = 0u;  // descend and restart the scan on the new node
+        }
+        else
         {
             ++scanned;  // scan next branch
-            continue;
         }
-
-        stack.pushChild(descendThrow(*inner, childBranch), childBranch);
-
-        auto const& child = stack.top().first;
-        if (child->isLeaf())
-            return safeDowncast<SHAMapLeafNode*>(child.get());
-
-        inner = safeDowncast<SHAMapInnerNode*>(child.get());
-        scanned = 0u;  // descend and restart the scan on the new node
     }
     return nullptr;
 }
-
+SHAMapLeafNode*
+SHAMap::lastBelow(SHAMapTreeNodePtr node, SharedPtrNodeStack& stack, unsigned int branch) const
+{
+    return belowHelper(node, stack, branch, BelowDirection::Last);
+}
+SHAMapLeafNode*
+SHAMap::firstBelow(SHAMapTreeNodePtr node, SharedPtrNodeStack& stack, unsigned int branch) const
+{
+    return belowHelper(node, stack, branch, BelowDirection::First);
+}
 static boost::intrusive_ptr<SHAMapItem const> const kNoItem;
 
 boost::intrusive_ptr<SHAMapItem const> const&
@@ -509,36 +529,36 @@ SHAMap::onlyBelow(SHAMapTreeNode* node) const
 }
 
 SHAMapLeafNode const*
-SHAMap::peekFirstItem(NodePathStack& stack) const
+SHAMap::peekFirstItem(SharedPtrNodeStack& stack) const
 {
     XRPL_ASSERT(stack.empty(), "xrpl::SHAMap::peekFirstItem : empty stack input");
-    stack.pushRoot(root_);
-    SHAMapLeafNode const* node = belowHelper(stack, BelowDirection::First);
+    SHAMapLeafNode const* node = firstBelow(root_, stack);
     if (node == nullptr)
     {
-        stack.clear();
+        while (!stack.empty())
+            stack.pop();
         return nullptr;
     }
     return node;
 }
 
 SHAMapLeafNode const*
-SHAMap::peekNextItem(uint256 const& id, NodePathStack& stack) const
+SHAMap::peekNextItem(uint256 const& id, SharedPtrNodeStack& stack) const
 {
     XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::peekNextItem : non-empty stack input");
     XRPL_ASSERT(stack.top().first->isLeaf(), "xrpl::SHAMap::peekNextItem : stack starts with leaf");
     stack.pop();
     while (!stack.empty())
     {
-        auto const [node, nodeID] = stack.top();
+        auto [node, nodeID] = stack.top();
         XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::peekNextItem : another node is not leaf");
-        auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
+        auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
         for (auto i = selectBranch(nodeID, id) + 1; i < kBranchFactor; ++i)
         {
-            if (!inner.isEmptyBranch(i))
+            if (!inner->isEmptyBranch(i))
             {
-                stack.pushChild(descendThrow(inner, i), i);
-                auto leaf = belowHelper(stack, BelowDirection::First);
+                node = descendThrow(*inner, i);
+                auto leaf = firstBelow(node, stack, i);
                 if (leaf == nullptr)
                     Throw<SHAMapMissingNode>(type_, id);
                 XRPL_ASSERT(leaf->isLeaf(), "xrpl::SHAMap::peekNextItem : leaf is valid");
@@ -575,59 +595,72 @@ SHAMap::peekItem(uint256 const& id, SHAMapHash& hash) const
 }
 
 SHAMap::ConstIterator
-SHAMap::boundHelper(uint256 const& id, BelowDirection direction) const
+SHAMap::upperBound(uint256 const& id) const
 {
-    // Walk back up the path to `id` looking for the nearest leaf on the requested side. At each
-    // inner node the branches beyond the one `id` takes hold the candidates; the first non-empty
-    // one is the closest, and the extreme leaf below it is the answer.
-    auto const searchingForward = direction == BelowDirection::First;
-
-    NodePathStack stack;
+    SharedPtrNodeStack stack;
     walkTowardsKey(id, &stack);
     while (!stack.empty())
     {
-        auto const [node, nodeID] = stack.top();
+        auto [node, nodeID] = stack.top();
         if (node->isLeaf())
         {
-            auto const& item = safeDowncast<SHAMapLeafNode const&>(*node).peekItem();
-            if (searchingForward ? (item->key() > id) : (item->key() < id))
-                return ConstIterator(this, item.get(), std::move(stack));
+            auto leaf = safeDowncast<SHAMapLeafNode*>(node.get());
+            if (leaf->peekItem()->key() > id)
+                return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
         }
         else
         {
-            auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
-            auto const taken = selectBranch(nodeID, id);
-            auto const remaining = searchingForward ? (kBranchFactor - 1u - taken) : taken;
-
-            for (auto scanned = 0u; scanned < remaining; ++scanned)
+            auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
+            for (auto branch = selectBranch(nodeID, id) + 1; branch < kBranchFactor; ++branch)
             {
-                auto const branch =
-                    searchingForward ? (taken + 1u + scanned) : (taken - 1u - scanned);
-                if (inner.isEmptyBranch(branch))
-                    continue;
-
-                stack.pushChild(descendThrow(inner, branch), branch);
-                auto const leaf = belowHelper(stack, direction);
-                if (leaf == nullptr)
-                    Throw<SHAMapMissingNode>(type_, id);
-                return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
+                if (!inner->isEmptyBranch(branch))
+                {
+                    node = descendThrow(*inner, branch);
+                    auto leaf = firstBelow(node, stack, branch);
+                    if (leaf == nullptr)
+                        Throw<SHAMapMissingNode>(type_, id);
+                    return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
+                }
             }
         }
         stack.pop();
     }
     return end();
 }
-
-SHAMap::ConstIterator
-SHAMap::upperBound(uint256 const& id) const
-{
-    return boundHelper(id, BelowDirection::First);
-}
-
 SHAMap::ConstIterator
 SHAMap::lowerBound(uint256 const& id) const
 {
-    return boundHelper(id, BelowDirection::Last);
+    SharedPtrNodeStack stack;
+    walkTowardsKey(id, &stack);
+    while (!stack.empty())
+    {
+        auto [node, nodeID] = stack.top();
+        if (node->isLeaf())
+        {
+            auto leaf = safeDowncast<SHAMapLeafNode*>(node.get());
+            if (leaf->peekItem()->key() < id)
+                return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
+        }
+        else
+        {
+            auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
+            for (auto branch = selectBranch(nodeID, id); branch > 0u;)
+            {
+                --branch;
+                if (!inner->isEmptyBranch(branch))
+                {
+                    node = descendThrow(*inner, branch);
+                    auto leaf = lastBelow(node, stack, branch);
+                    if (leaf == nullptr)
+                        Throw<SHAMapMissingNode>(type_, id);
+                    return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
+                }
+            }
+        }
+        stack.pop();
+    }
+    // TODO: what to return here?
+    return end();
 }
 
 bool
@@ -642,7 +675,7 @@ SHAMap::delItem(uint256 const& id)
     // delete the item with this ID
     XRPL_ASSERT(state_ != SHAMapState::Immutable, "xrpl::SHAMap::delItem : not immutable");
 
-    NodePathStack stack;
+    SharedPtrNodeStack stack;
     walkTowardsKey(id, &stack);
 
     if (stack.empty())
@@ -728,7 +761,7 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
     // add the specified item, does not update
     uint256 const tag = item->key();
 
-    NodePathStack stack;
+    SharedPtrNodeStack stack;
     walkTowardsKey(tag, &stack);
 
     if (stack.empty())
@@ -768,7 +801,7 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
 
         while ((b1 = selectBranch(nodeID, tag)) == (b2 = selectBranch(nodeID, otherItem->key())))
         {
-            stack.pushNode(node, tag);
+            stack.emplace(node, nodeID);
 
             // we need a new inner node, since both go on same branch at this
             // level
@@ -815,7 +848,7 @@ SHAMap::updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem cons
 
     XRPL_ASSERT(state_ != SHAMapState::Immutable, "xrpl::SHAMap::updateGiveItem : not immutable");
 
-    NodePathStack stack;
+    SharedPtrNodeStack stack;
     walkTowardsKey(tag, &stack);
 
     if (stack.empty())
@@ -1137,7 +1170,7 @@ SHAMap::invariants() const
     auto node = root_.get();
     XRPL_ASSERT(node, "xrpl::SHAMap::invariants : non-null root node");
     XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::invariants : root node is not leaf");
-    NodePathStack stack;
+    SharedPtrNodeStack stack;
     for (auto leaf = peekFirstItem(stack); leaf != nullptr;
          leaf = peekNextItem(leaf->peekItem()->key(), stack))
         ;

src/libxrpl/shamap/SHAMapNodeID.cpp

@@ -6,7 +6,6 @@
 #include <xrpl/protocol/Serializer.h>
 #include <xrpl/shamap/SHAMap.h>
 
-#include <algorithm>
 #include <cstddef>
 #include <optional>
 #include <stdexcept>
@@ -41,39 +40,9 @@ depthMask(unsigned int depth)
     return kMasks.entry[depth];
 }
 
-// The prefix of `key` at `depth`: the leading nibbles naming the subtree a node at that depth
-// identifies, with the remainder of the key masked off.
-static uint256
-maskedToDepth(uint256 const& key, unsigned int depth)
-{
-    return key & depthMask(depth);
-}
-
-// Whether `id` at `depth` is what `key` looks like once masked down to that depth, i.e.
-// whether an ID with this depth and id names a subtree that `key` falls under.
-static bool
-isPrefixOfAtDepth(uint256 const& id, unsigned int depth, uint256 const& key)
-{
-    return maskedToDepth(key, depth) == id;
-}
-
 // canonicalize the hash to a node ID for this depth
 SHAMapNodeID::SHAMapNodeID(unsigned int depth, uint256 const& hash) : id_(hash), depth_(depth)
 {
-    // Every SHAMapNodeID's depth is stored here, so this is the one place that can stop an
-    // out-of-range one from being kept: a depth past kLeafDepth would go on to index depthMask
-    // out of bounds, and getRawString would narrow it to a byte, silently renaming the node.
-    // Clamp rather than throw, since node IDs are built from peer-supplied depths on the ledger
-    // data path, where no caller catches an exception before it reaches a thread boundary.
-    if (depth_ > SHAMap::kLeafDepth)
-    {
-        // LCOV_EXCL_START
-        UNREACHABLE("xrpl::SHAMapNodeID::SHAMapNodeID : depth within tree");
-        depth_ = SHAMap::kLeafDepth;
-        id_ = maskedToDepth(id_, depth_);
-        // LCOV_EXCL_STOP
-    }
-
     XRPL_ASSERT(
         depth <= SHAMap::kLeafDepth, "xrpl::SHAMapNodeID::SHAMapNodeID : maximum depth input");
     XRPL_ASSERT(
@@ -120,7 +89,7 @@ SHAMapNodeID::getChildNodeID(unsigned int branch) const
 bool
 SHAMapNodeID::isPrefixOf(uint256 const& key) const
 {
-    return isPrefixOfAtDepth(id_, depth_, key);
+    return (key & depthMask(depth_)) == id_;
 }
 
 [[nodiscard]] std::optional<SHAMapNodeID>
@@ -133,9 +102,9 @@ deserializeSHAMapNodeID(void const* data, std::size_t size)
         unsigned int const depth = *(static_cast<unsigned char const*>(data) + 32);
         if (depth <= SHAMap::kLeafDepth)
         {
-            // Reject a serialized ID carrying bits below its own depth. Checked before
-            // constructing, since the constructor asserts that same property.
-            if (auto const id = uint256::fromVoid(data); isPrefixOfAtDepth(id, depth, id))
+            auto const id = uint256::fromVoid(data);
+
+            if (id == (id & depthMask(depth)))
                 ret.emplace(depth, id);
         }
     }
@@ -146,11 +115,7 @@ deserializeSHAMapNodeID(void const* data, std::size_t size)
 [[nodiscard]] unsigned int
 selectBranch(SHAMapNodeID const& id, uint256 const& hash)
 {
-    XRPL_ASSERT(id.getDepth() < SHAMap::kLeafDepth, "xrpl::selectBranch : depth below leaf depth");
-
-    // A depth-64 ID has no nibble left to select. Callers must not ask, but clamp anyway to keep
-    // the read below the end of the 32-byte key.
-    auto const depth = std::min(id.getDepth(), SHAMap::kLeafDepth - 1u);
+    auto const depth = id.getDepth();
     auto branch = static_cast<unsigned int>(*(hash.begin() + (depth / 2)));
 
     if ((depth & 1) != 0u)
@@ -169,18 +134,8 @@ selectBranch(SHAMapNodeID const& id, uint256 const& hash)
 SHAMapNodeID
 SHAMapNodeID::createID(unsigned int depth, uint256 const& key)
 {
-    // The mask is chosen here, before the constructor runs, so the clamp there cannot cover this
-    // call: an out-of-range depth would index depthMask's table while still evaluating this
-    // argument. A public factory has to hold its own bound.
-    if (depth > SHAMap::kLeafDepth)
-    {
-        // LCOV_EXCL_START
-        UNREACHABLE("xrpl::SHAMapNodeID::createID : depth within tree");
-        depth = SHAMap::kLeafDepth;
-        // LCOV_EXCL_STOP
-    }
-
-    return SHAMapNodeID(depth, maskedToDepth(key, depth));
+    XRPL_ASSERT(depth <= SHAMap::kLeafDepth, "xrpl::SHAMapNodeID::createID : valid depth");
+    return SHAMapNodeID(depth, key & depthMask(depth));
 }
 
 }  // namespace xrpl

src/libxrpl/shamap/SHAMapSync.cpp

@@ -793,7 +793,7 @@ SHAMap::hasLeafNode(uint256 const& tag, SHAMapHash const& targetNodeHash) const
 std::optional<std::vector<Blob>>
 SHAMap::getProofPath(uint256 const& key) const
 {
-    NodePathStack stack;
+    SharedPtrNodeStack stack;
     walkTowardsKey(key, &stack);
 
     if (stack.empty())

src/libxrpl/tx/transactors/lending/LoanPay.cpp

@@ -620,7 +620,12 @@ LoanPay::doApply()
         ? STAmount{asset, 0}
         : conservationBalance(view, brokerPayee, asset, j_);
 
-    if (totalPaidToVaultRounded != beast::kZero)
+    // Only ledgers without the rule below reach these payee checks. Once it is in force
+    // requireAuth can no longer reject a pseudo-account, so the whole block goes away with the
+    // gate.
+    bool const skipPayeeAuth = view.rules().enabled(fixCleanup3_4_0);
+
+    if (!skipPayeeAuth && totalPaidToVaultRounded != beast::kZero)
     {
         if (auto const ter = requireAuth(view, asset, vaultPseudoAccount, AuthType::StrongAuth))
             return ter;
@@ -644,8 +649,11 @@ LoanPay::doApply()
                 return ter;
             }
         }
-        if (auto const ter = requireAuth(view, asset, brokerPayee, AuthType::StrongAuth))
-            return ter;
+        if (!skipPayeeAuth)
+        {
+            if (auto const ter = requireAuth(view, asset, brokerPayee, AuthType::StrongAuth))
+                return ter;
+        }
     }
 
     if (auto const ter = accountSendMulti(

src/test/app/AMMExtended_test.cpp

@@ -1303,6 +1303,78 @@ private:
         BEAST_EXPECT(expectHolding(env, bob_, USD(0)));
     }
 
+    // Same shape as testRequireAuth, except the issuer never authorizes the AMM's own trust line.
+    // An AMM holds the asset for its liquidity providers and cannot sign a TrustSet for itself, so
+    // once pseudo-accounts are implicitly authorized the pool keeps trading. Before that the offer
+    // stream drops it and the taker's offer stays on the book.
+    void
+    testPseudoAccountRequireAuth(FeatureBitset features)
+    {
+        testcase("lsfRequireAuth, unauthorized AMM pseudo-account");
+
+        using namespace jtx;
+
+        bool const pseudoExempt = features[fixCleanup3_4_0];
+
+        Env env{*this, features};
+
+        auto const aliceUSD = alice_["USD"];
+        auto const bobUSD = bob_["USD"];
+
+        env.fund(XRP(400'000), gw_, alice_, bob_);
+        env.close();
+
+        env(fset(gw_, asfRequireAuth));
+        env.close();
+
+        env(trust(gw_, bobUSD(100)), Txflags(tfSetfAuth));
+        env(trust(bob_, USD(100)));
+        env(trust(gw_, aliceUSD(100)), Txflags(tfSetfAuth));
+        env(trust(alice_, USD(2'000)));
+        env(pay(gw_, alice_, USD(1'000)));
+        env.close();
+
+        AMM const ammAlice(env, alice_, USD(1'000), XRP(1'050));
+
+        // The pool's own line stays unauthorized: AMMCreate opens it without the flag, and the
+        // pseudo-account has no key to ask for one.
+        auto const ammLineAuthorized = [&]() -> bool {
+            auto const line =
+                env.le(keylet::trustLine(ammAlice.ammAccount(), USD.issue().account, USD.currency));
+            if (!BEAST_EXPECT(line))
+                return false;
+            return line->isFlag(
+                ammAlice.ammAccount() > USD.issue().account ? lsfLowAuth : lsfHighAuth);
+        };
+        BEAST_EXPECT(!ammLineAuthorized());
+
+        env(pay(gw_, bob_, USD(50)));
+        env.close();
+        BEAST_EXPECT(expectHolding(env, bob_, USD(50)));
+
+        // Bob sells USD into the pool, so the pool is the side that has to be authorized to hold
+        // the asset.
+        env(offer(bob_, XRP(50), USD(50)));
+        env.close();
+
+        if (pseudoExempt)
+        {
+            BEAST_EXPECT(ammAlice.expectBalances(USD(1'050), XRP(1'000), ammAlice.tokens()));
+            BEAST_EXPECT(expectOffers(env, bob_, 0));
+            BEAST_EXPECT(expectHolding(env, bob_, USD(0)));
+        }
+        else
+        {
+            // The pool is skipped, so nothing crosses and the offer rests on the book.
+            BEAST_EXPECT(ammAlice.expectBalances(USD(1'000), XRP(1'050), ammAlice.tokens()));
+            BEAST_EXPECT(expectOffers(env, bob_, 1));
+            BEAST_EXPECT(expectHolding(env, bob_, USD(50)));
+        }
+
+        // Either way the exemption skips the check rather than setting the flag.
+        BEAST_EXPECT(!ammLineAuthorized());
+    }
+
     void
     testMissingAuth(FeatureBitset features)
     {
@@ -1400,6 +1472,8 @@ private:
         testDirectToDirectPath(all_);
         testDirectToDirectPath(all_ - fixAMMv1_1 - fixAMMv1_3);
         testRequireAuth(all_);
+        testPseudoAccountRequireAuth(all_);
+        testPseudoAccountRequireAuth(all_ - fixCleanup3_4_0);
         testMissingAuth(all_);
     }
 

src/test/app/lending/LoanPay_test.cpp

@@ -4,6 +4,7 @@
 #include <test/jtx/TestHelpers.h>
 #include <test/jtx/amount.h>
 #include <test/jtx/fee.h>
+#include <test/jtx/flags.h>
 #include <test/jtx/jtx_json.h>
 #include <test/jtx/noop.h>
 #include <test/jtx/pay.h>
@@ -15,9 +16,11 @@
 #include <xrpl/beast/utility/Zero.h>
 #include <xrpl/json/json_value.h>
 #include <xrpl/ledger/helpers/LendingHelpers.h>
+#include <xrpl/protocol/AccountID.h>
 #include <xrpl/protocol/Feature.h>
 #include <xrpl/protocol/Indexes.h>
 #include <xrpl/protocol/Issue.h>
+#include <xrpl/protocol/LedgerFormats.h>
 #include <xrpl/protocol/Protocol.h>
 #include <xrpl/protocol/SField.h>
 #include <xrpl/protocol/STAmount.h>
@@ -730,6 +733,200 @@ private:
         }
     }
 
+    // Which pseudo-account is left holding an unauthorized trust line when the
+    // repayment lands.
+    enum class UnauthorizedPayee {
+        // The vault's own line, as VaultCreate leaves it.
+        Vault,
+        // Same vault, but the issuer authorized the line by hand first.
+        VaultAuthorized,
+        // Vault line authorized, broker owner unable to take the fee, so the
+        // fee goes to the loan broker's pseudo-account instead.
+        Broker,
+    };
+
+    // A vault holding an IOU whose issuer requires authorization ends up with
+    // its own trust line unauthorized: VaultCreate opens the line without the
+    // auth flag, and the pseudo-account has no key to sign a TrustSet for
+    // itself. Neither deposits nor loan origination look at that line, so the
+    // vault appears to work right up to the first repayment, which is the only
+    // step that has to credit the vault back.
+    //
+    // The loan broker's pseudo-account has the same defect for the same reason,
+    // and LoanPay reaches it whenever the broker owner cannot take the fee.
+    //
+    // The issuer can still repair either line by hand, because TrustSet accepts
+    // a line that already exists even when its owner is a pseudo-account.
+    void
+    testRepayIntoUnauthorizedVault()
+    {
+        using namespace jtx;
+
+        Account const issuer{"issuer"};
+        Account const lender{"lender"};
+        Account const borrower{"borrower"};
+
+        auto runTestCases = [&](FeatureBitset features, UnauthorizedPayee payee) {
+            bool const pseudoExempt = features[fixCleanup3_4_0];
+            // With the vault's line repaired by the issuer, the only remaining
+            // unauthorized payee is the broker's pseudo-account.
+            bool const expectSuccess = pseudoExempt || payee == UnauthorizedPayee::VaultAuthorized;
+
+            auto const payeeLabel = [payee]() -> char const* {
+                switch (payee)
+                {
+                    case UnauthorizedPayee::Vault:
+                        return "vault";
+                    case UnauthorizedPayee::VaultAuthorized:
+                        return "vault authorized by the issuer";
+                    case UnauthorizedPayee::Broker:
+                        return "loan broker";
+                }
+                return "";  // LCOV_EXCL_LINE
+            }();
+
+            testcase << "LoanPay crediting an unauthorized " << payeeLabel << ": pseudo-account "
+                     << (pseudoExempt ? "exempt" : "not exempt");
+
+            Env env{*this, features};
+
+            env.fund(XRP(1'000'000), issuer, lender, borrower);
+            env.close();
+
+            env(fset(issuer, asfRequireAuth));
+            env.close();
+
+            PrettyAsset const asset = issuer[iouCurrency_];
+            env(trust(lender, asset(100'000'000)));
+            env(trust(borrower, asset(100'000'000)));
+            env.close();
+
+            // Authorize the two participants. Nothing asks the issuer to also
+            // authorize the vault, which is the whole point of this test.
+            env(trust(issuer, asset(0), lender, tfSetfAuth));
+            env(trust(issuer, asset(0), borrower, tfSetfAuth));
+            env.close();
+
+            env(pay(issuer, lender, asset(10'000'000)));
+            env(pay(issuer, borrower, asset(10'000)));
+            env.close();
+
+            // Creating the vault and funding it with deposits succeeds even
+            // though the vault cannot be authorized to hold the asset.
+            BrokerInfo const broker{createVaultAndBroker(env, asset, lender)};
+
+            auto const vaultSle = env.le(broker.vaultKeylet());
+            auto const brokerSle = env.le(broker.brokerKeylet());
+            if (!BEAST_EXPECT(vaultSle && brokerSle))
+                return;
+
+            Account const vaultPseudo{"vault pseudo-account", vaultSle->at(sfAccount)};
+            Account const brokerPseudo{"broker pseudo-account", brokerSle->at(sfAccount)};
+
+            auto const lineIsAuthorized = [&](Account const& holder) -> bool {
+                auto const line = env.le(keylet::trustLine(holder, asset.raw().get<Issue>()));
+                if (!BEAST_EXPECT(line))
+                    return false;
+                return line->isFlag(holder.id() > issuer.id() ? lsfLowAuth : lsfHighAuth);
+            };
+
+            BEAST_EXPECT(!lineIsAuthorized(vaultPseudo));
+            BEAST_EXPECT(!lineIsAuthorized(brokerPseudo));
+
+            if (payee != UnauthorizedPayee::Vault)
+            {
+                env(trust(issuer, asset(0), vaultPseudo, tfSetfAuth));
+                env.close();
+                BEAST_EXPECT(lineIsAuthorized(vaultPseudo));
+            }
+
+            using namespace loan;
+
+            // The service fee guarantees the broker is owed something on the
+            // first payment, so the broker leg of the transfer is exercised.
+            Number const serviceFee = asset(2).value();
+            auto const loanKeylet = nextLoanKeylet(env, broker);
+            env(set(borrower, broker.brokerID, asset(1'000).value()),
+                Sig(sfCounterpartySignature, lender),
+                kLoanServiceFee(serviceFee),
+                kInterestRate(percentageToTenthBips(12)),
+                kPaymentTotal(12),
+                kPaymentInterval(600),
+                Fee(env.current()->fees().base * 2));
+            env.close();
+
+            // Paying the principal out of the vault never needed authorization.
+            BEAST_EXPECT(env.le(loanKeylet));
+
+            if (payee == UnauthorizedPayee::Broker)
+            {
+                // A deep-frozen owner cannot take the fee, so LoanPay pays it
+                // into the broker's pseudo-account instead.
+                env(trust(issuer, asset(0), lender, tfSetFreeze | tfSetDeepFreeze));
+                env.close();
+            }
+
+            auto const state = getCurrentState(env, broker, loanKeylet);
+            STAmount const payment{
+                broker.asset,
+                roundPeriodicPayment(
+                    broker.asset, state.periodicPayment + serviceFee, state.loanScale)};
+
+            // Repayment turns an outstanding loan back into cash the vault can
+            // lend again, so AssetsAvailable is what moves. AssetsTotal already
+            // counted the loan.
+            auto const assetsAvailable = [&]() -> Number {
+                auto const sle = env.le(broker.vaultKeylet());
+                if (!BEAST_EXPECT(sle))
+                    return Number{};
+                return sle->at(sfAssetsAvailable);
+            };
+
+            auto const borrowerBefore = env.balance(borrower, asset).number();
+            auto const vaultBefore = env.balance(vaultPseudo, asset).number();
+            auto const brokerBefore = env.balance(brokerPseudo, asset).number();
+            auto const assetsAvailableBefore = assetsAvailable();
+
+            env(pay(borrower, loanKeylet.key, payment),
+                Ter(expectSuccess ? TER{tesSUCCESS} : TER{tecNO_AUTH}));
+            env.close();
+
+            if (expectSuccess)
+            {
+                BEAST_EXPECT(env.balance(borrower, asset).number() < borrowerBefore);
+                BEAST_EXPECT(env.balance(vaultPseudo, asset).number() > vaultBefore);
+                BEAST_EXPECT(assetsAvailable() > assetsAvailableBefore);
+                // Confirms the broker variant really did route the fee to the
+                // pseudo-account rather than to the owner.
+                BEAST_EXPECT(
+                    (env.balance(brokerPseudo, asset).number() > brokerBefore) ==
+                    (payee == UnauthorizedPayee::Broker));
+
+                // The payee is skipped by the check, not authorized by it: the line that just
+                // took the credit is still missing its auth flag.
+                if (payee == UnauthorizedPayee::Vault)
+                    BEAST_EXPECT(!lineIsAuthorized(vaultPseudo));
+                if (payee == UnauthorizedPayee::Broker)
+                    BEAST_EXPECT(!lineIsAuthorized(brokerPseudo));
+            }
+            else
+            {
+                // A rejected repayment must leave every balance untouched.
+                BEAST_EXPECT(env.balance(borrower, asset).number() == borrowerBefore);
+                BEAST_EXPECT(env.balance(vaultPseudo, asset).number() == vaultBefore);
+                BEAST_EXPECT(env.balance(brokerPseudo, asset).number() == brokerBefore);
+                BEAST_EXPECT(assetsAvailable() == assetsAvailableBefore);
+            }
+        };
+
+        for (auto const& features : {all_, all_ - fixCleanup3_4_0})
+        {
+            runTestCases(features, UnauthorizedPayee::Vault);
+            runTestCases(features, UnauthorizedPayee::VaultAuthorized);
+            runTestCases(features, UnauthorizedPayee::Broker);
+        }
+    }
+
     void
     testLoanPayFundsConservedPayeeBelowReserve(FeatureBitset features)
     {
@@ -838,6 +1035,7 @@ private:
     runAmendmentIndependent()
     {
         testLoanSetNearZeroInterestRateSucceeds();
+        testRepayIntoUnauthorizedVault();
     }
 
     // Tests run under each entry in amendmentCombinations().

src/tests/libxrpl/shamap/SHAMap.cpp

@@ -272,413 +272,6 @@ INSTANTIATE_TEST_SUITE_P(
     ::testing::Values(kBackedMode, kUnbackedMode),
     shamapBackingModeName);
 
-// Exercises the traversal stacks built by firstBelow/lastBelow. Each stack entry pairs a node with
-// the ID naming its position, and SHAMap asserts that pairing on every push, so these traversals
-// fail loudly in a Debug build if a node ID is ever derived from the wrong branch.
-class SHAMapTraversal : public ::testing::Test
-{
-protected:
-    beast::Journal const j_{TestSink::instance()};
-
-    // Keys that share a long prefix and then fan out across distinct branches, so the deeper inner
-    // nodes have several children and traversal must descend many levels.
-    static std::vector<uint256>
-    deepFanOutKeys()
-    {
-        std::vector<uint256> keys;
-        for (unsigned int branch = 0; branch < SHAMap::kBranchFactor; ++branch)
-        {
-            // Vary the 6th nibble, keeping the first five identical.
-            auto text = std::string("abcde") + "0123456789abcdef"[branch];
-            text.append(64 - text.size(), '7');
-            keys.emplace_back(std::string_view{text});
-        }
-        return keys;
-    }
-
-    // Keys that share all 63 leading nibbles and fan out only at the last one, so the tree is a
-    // chain of single-child inner nodes down to depth 63 with the leaves as siblings at depth 64.
-    // This exercises kLeafDepth directly, unlike deepFanOutKeys() above, whose fan-out at the 6th
-    // nibble keeps the tree only about 6 levels deep.
-    static std::vector<uint256>
-    deepFanOutKeysAtLeafDepth()
-    {
-        std::vector<uint256> keys;
-        for (unsigned int branch = 0; branch < SHAMap::kBranchFactor; ++branch)
-        {
-            auto text = std::string(63, 'a') + "0123456789abcdef"[branch];
-            keys.emplace_back(std::string_view{text});
-        }
-        return keys;
-    }
-
-    static void
-    fillMap(SHAMap& map, std::vector<uint256> const& keys)
-    {
-        map.setUnbacked();
-        for (auto const& k : keys)
-        {
-            Buffer vuc{32};
-            std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
-            EXPECT_TRUE(
-                map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(k, std::move(vuc))));
-            map.invariants();
-        }
-    }
-};
-
-TEST_F(SHAMapTraversal, forward_iteration_visits_every_key_in_order)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeys();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-
-    std::ranges::sort(keys);
-    std::vector<uint256> visited;
-    for (auto const& item : map)
-        visited.push_back(item.key());
-
-    EXPECT_EQ(visited, keys);
-}
-
-TEST_F(SHAMapTraversal, upper_bound_walks_the_whole_map)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeys();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // upperBound from each key must land on its successor, driving firstBelow across every subtree.
-    for (std::size_t k = 0; k + 1 < keys.size(); ++k)
-    {
-        auto it = map.upperBound(keys[k]);
-        ASSERT_NE(it, map.end()) << "no successor for key " << k;
-        EXPECT_EQ(it->key(), keys[k + 1]) << "wrong successor for key " << k;
-    }
-    EXPECT_EQ(map.upperBound(keys.back()), map.end());
-}
-
-TEST_F(SHAMapTraversal, lower_bound_walks_the_whole_map)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeys();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // lowerBound is the lastBelow counterpart: it descends to the greatest key below a subtree.
-    for (std::size_t k = 1; k < keys.size(); ++k)
-    {
-        auto it = map.lowerBound(keys[k]);
-        ASSERT_NE(it, map.end()) << "no predecessor for key " << k;
-        EXPECT_EQ(it->key(), keys[k - 1]) << "wrong predecessor for key " << k;
-    }
-    EXPECT_EQ(map.lowerBound(keys.front()), map.end());
-}
-
-TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeys();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // Probe keys that are not in the map, so the traversal starts mid-tree rather than at a leaf.
-    for (unsigned char const c : {0x00, 0x40, 0x80, 0xc0, 0xff})
-    {
-        uint256 probe;
-        std::fill_n(probe.begin(), probe.size(), c);
-
-        auto const expectedUpper = std::ranges::upper_bound(keys, probe);
-        auto const upper = map.upperBound(probe);
-        if (expectedUpper == keys.end())
-        {
-            EXPECT_EQ(upper, map.end()) << "probe " << static_cast<unsigned>(c);
-        }
-        else
-        {
-            ASSERT_NE(upper, map.end()) << "probe " << static_cast<unsigned>(c);
-            EXPECT_EQ(upper->key(), *expectedUpper) << "probe " << static_cast<unsigned>(c);
-        }
-
-        auto const lowerCount = std::ranges::lower_bound(keys, probe) - keys.begin();
-        auto const lower = map.lowerBound(probe);
-        if (lowerCount == 0)
-        {
-            EXPECT_EQ(lower, map.end()) << "probe " << static_cast<unsigned>(c);
-        }
-        else
-        {
-            ASSERT_NE(lower, map.end()) << "probe " << static_cast<unsigned>(c);
-            EXPECT_EQ(lower->key(), keys[lowerCount - 1]) << "probe " << static_cast<unsigned>(c);
-        }
-    }
-}
-
-TEST_F(SHAMapTraversal, bounds_on_empty_map_return_end)
-{
-    tests::TestNodeFamily f{j_};
-    SHAMap map{SHAMapType::FREE, f};
-    map.setUnbacked();
-
-    // The root is a childless inner node, so boundHelper's inner-node branch scans every branch on
-    // the requested side of the one id selects, finds them all empty, and falls through to end()
-    // rather than dereference a child.
-    EXPECT_EQ(map.upperBound(uint256{}), map.end());
-    EXPECT_EQ(map.lowerBound(uint256{}), map.end());
-
-    uint256 probe;
-    std::fill_n(probe.begin(), probe.size(), std::uint8_t{0xff});
-    EXPECT_EQ(map.upperBound(probe), map.end());
-    EXPECT_EQ(map.lowerBound(probe), map.end());
-}
-
-TEST_F(SHAMapTraversal, bounds_on_single_item_map_use_the_leaf_root)
-{
-    tests::TestNodeFamily f{j_};
-    SHAMap map{SHAMapType::FREE, f};
-
-    auto const key = deepFanOutKeys().front();
-    fillMap(map, {key});
-
-    // root_ can be a leaf, but only after syncing a single-item map from a peer (addRootNode);
-    // fillMap builds this map in-process via addItem, which always leaves root_ as the inner node
-    // it was constructed with, with the single leaf one level below it. So here the stack holds
-    // that inner root plus the leaf, and boundHelper's leaf branch, examined first, decides the
-    // outcome before root_'s own inner-node scan would ever run.
-    uint256 below = key;
-    --below;
-    uint256 above = key;
-    ++above;
-
-    EXPECT_EQ(map.upperBound(below)->key(), key);
-    EXPECT_EQ(map.upperBound(key), map.end());
-    EXPECT_EQ(map.upperBound(above), map.end());
-
-    EXPECT_EQ(map.lowerBound(above)->key(), key);
-    EXPECT_EQ(map.lowerBound(key), map.end());
-    EXPECT_EQ(map.lowerBound(below), map.end());
-}
-
-TEST_F(SHAMapTraversal, iteration_survives_deletions)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeys();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // Deleting every other key drops the fan-out node's branch count from 16 to 8, never the 1
-    // that would make delItem collapse it into a leaf. So this pins that iteration survives
-    // deletions that reshape the map without collapsing any inner node; the case that does
-    // collapse one is iteration_survives_a_collapsed_inner_node below.
-    for (std::size_t k = 0; k < keys.size(); k += 2)
-    {
-        ASSERT_TRUE(map.delItem(keys[k]));
-        map.invariants();
-    }
-
-    std::vector<uint256> expected;
-    for (std::size_t k = 1; k < keys.size(); k += 2)
-        expected.push_back(keys[k]);
-
-    std::vector<uint256> visited;
-    for (auto const& item : map)
-        visited.push_back(item.key());
-    EXPECT_EQ(visited, expected);
-
-    for (std::size_t k = 0; k + 1 < expected.size(); ++k)
-    {
-        auto it = map.upperBound(expected[k]);
-        ASSERT_NE(it, map.end());
-        EXPECT_EQ(it->key(), expected[k + 1]);
-    }
-}
-
-TEST_F(SHAMapTraversal, iteration_survives_a_collapsed_inner_node)
-{
-    tests::TestNodeFamily f{j_};
-    SHAMap map{SHAMapType::FREE, f};
-
-    // One key in a separate subtree, diverging from the fan-out group at the very first nibble, so
-    // it survives untouched while the fan-out group below is collapsed.
-    auto const sentinel = uint256{std::string_view{std::string(64, '0')}};
-
-    auto fanOutKeys = deepFanOutKeysAtLeafDepth();
-    fillMap(map, fanOutKeys);
-    Buffer vuc{32};
-    std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
-    ASSERT_TRUE(
-        map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(sentinel, std::move(vuc))));
-    map.invariants();
-
-    std::ranges::sort(fanOutKeys);
-
-    // Delete all but the last fan-out key. The fan-out node's branch count drops to 1 on the final
-    // delete, which delItem collapses by pulling the sole remaining leaf up in its place; every
-    // ancestor above it has exactly one child by construction, so each of those also drops to
-    // branch count 1 and collapses in turn, all the way up to (but not including) the root. That
-    // final delete replaces the entire 63-level chain with the root pointing straight at the one
-    // remaining leaf, so the surviving traversal stack is rebuilt over a drastically different tree
-    // shape, not just missing one inner node.
-    for (std::size_t k = 0; k + 1 < fanOutKeys.size(); ++k)
-    {
-        ASSERT_TRUE(map.delItem(fanOutKeys[k]));
-        map.invariants();
-    }
-
-    std::vector<uint256> const expected{sentinel, fanOutKeys.back()};
-    std::vector<uint256> visited;
-    for (auto const& item : map)
-        visited.push_back(item.key());
-    EXPECT_EQ(visited, expected);
-
-    auto it = map.upperBound(sentinel);
-    ASSERT_NE(it, map.end());
-    EXPECT_EQ(it->key(), fanOutKeys.back());
-    EXPECT_EQ(map.upperBound(fanOutKeys.back()), map.end());
-}
-
-// The tests below mirror the ones above but use deepFanOutKeysAtLeafDepth(), whose keys share all
-// 63 leading nibbles and fan out only at the last one. That puts the leaves at depth
-// SHAMap::kLeafDepth, so these traversals walk a chain of single-child inner nodes all the way down
-// and exercise the kLeafDepth guards that deepFanOutKeys() alone (fanning out at the 6th nibble)
-// never reaches.
-
-TEST_F(SHAMapTraversal, forward_iteration_visits_every_key_in_order_at_leaf_depth)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeysAtLeafDepth();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-
-    std::ranges::sort(keys);
-    std::vector<uint256> visited;
-    for (auto const& item : map)
-        visited.push_back(item.key());
-
-    EXPECT_EQ(visited, keys);
-}
-
-TEST_F(SHAMapTraversal, upper_bound_walks_the_whole_map_at_leaf_depth)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeysAtLeafDepth();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // upperBound from each key must land on its successor, driving firstBelow down to depth
-    // kLeafDepth for every subtree.
-    for (std::size_t k = 0; k + 1 < keys.size(); ++k)
-    {
-        auto it = map.upperBound(keys[k]);
-        ASSERT_NE(it, map.end()) << "no successor for key " << k;
-        EXPECT_EQ(it->key(), keys[k + 1]) << "wrong successor for key " << k;
-    }
-    EXPECT_EQ(map.upperBound(keys.back()), map.end());
-}
-
-TEST_F(SHAMapTraversal, lower_bound_walks_the_whole_map_at_leaf_depth)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeysAtLeafDepth();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // lowerBound is the lastBelow counterpart: it descends to depth kLeafDepth to find the greatest
-    // key below a subtree.
-    for (std::size_t k = 1; k < keys.size(); ++k)
-    {
-        auto it = map.lowerBound(keys[k]);
-        ASSERT_NE(it, map.end()) << "no predecessor for key " << k;
-        EXPECT_EQ(it->key(), keys[k - 1]) << "wrong predecessor for key " << k;
-    }
-    EXPECT_EQ(map.lowerBound(keys.front()), map.end());
-}
-
-TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys_at_leaf_depth)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeysAtLeafDepth();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // The keys fill all 16 branches of the last nibble, so an absent key must diverge from the
-    // shared 'a' prefix earlier than that. Diverging at increasingly deep nibbles forces
-    // walkTowardsKey to descend through more single-child inner nodes before it finds the empty
-    // branch, right up to the one just above kLeafDepth.
-    for (unsigned int const divergeAt : {0u, 31u, 61u, 62u})
-    {
-        auto text = std::string(divergeAt, 'a') + "b";
-        text.append(64 - text.size(), '0');
-        uint256 const probe{std::string_view{text}};
-
-        auto const expectedUpper = std::ranges::upper_bound(keys, probe);
-        auto const upper = map.upperBound(probe);
-        if (expectedUpper == keys.end())
-        {
-            EXPECT_EQ(upper, map.end()) << "divergeAt " << divergeAt;
-        }
-        else
-        {
-            ASSERT_NE(upper, map.end()) << "divergeAt " << divergeAt;
-            EXPECT_EQ(upper->key(), *expectedUpper) << "divergeAt " << divergeAt;
-        }
-
-        auto const lowerCount = std::ranges::lower_bound(keys, probe) - keys.begin();
-        auto const lower = map.lowerBound(probe);
-        if (lowerCount == 0)
-        {
-            EXPECT_EQ(lower, map.end()) << "divergeAt " << divergeAt;
-        }
-        else
-        {
-            ASSERT_NE(lower, map.end()) << "divergeAt " << divergeAt;
-            EXPECT_EQ(lower->key(), keys[lowerCount - 1]) << "divergeAt " << divergeAt;
-        }
-    }
-}
-
-TEST_F(SHAMapTraversal, iteration_survives_deletions_at_leaf_depth)
-{
-    tests::TestNodeFamily f{j_};
-    auto keys = deepFanOutKeysAtLeafDepth();
-    SHAMap map{SHAMapType::FREE, f};
-    fillMap(map, keys);
-    std::ranges::sort(keys);
-
-    // Deleting every other key drops the fan-out node's branch count from 16 to 8, the same
-    // non-collapsing case as iteration_survives_deletions above, but reached by descending through
-    // a chain of single-child inner nodes down to kLeafDepth instead of a shallow one.
-    for (std::size_t k = 0; k < keys.size(); k += 2)
-    {
-        ASSERT_TRUE(map.delItem(keys[k]));
-        map.invariants();
-    }
-
-    std::vector<uint256> expected;
-    for (std::size_t k = 1; k < keys.size(); k += 2)
-        expected.push_back(keys[k]);
-
-    std::vector<uint256> visited;
-    for (auto const& item : map)
-        visited.push_back(item.key());
-    EXPECT_EQ(visited, expected);
-
-    for (std::size_t k = 0; k + 1 < expected.size(); ++k)
-    {
-        auto it = map.upperBound(expected[k]);
-        ASSERT_NE(it, map.end());
-        EXPECT_EQ(it->key(), expected[k + 1]);
-    }
-}
-
 class SHAMapPathProof : public ::testing::Test
 {
 protected:

src/tests/libxrpl/shamap/SHAMapNodeID.cpp

@@ -1,193 +0,0 @@
-#include <xrpl/shamap/SHAMapNodeID.h>
-
-#include <xrpl/basics/base_uint.h>
-#include <xrpl/protocol/Serializer.h>
-#include <xrpl/shamap/SHAMap.h>
-
-#include <gtest/gtest.h>
-
-#include <stdexcept>
-
-namespace xrpl::tests {
-
-// An arbitrary 32-byte key reused across tests below that don't care about its specific value,
-// only that it is a well-formed key.
-constexpr uint256 kTestKey("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
-
-TEST(SHAMapNodeIDTest, root_is_prefix_of_every_key)
-{
-    SHAMapNodeID const root;
-    EXPECT_EQ(root.getDepth(), 0u);
-    EXPECT_TRUE(root.isPrefixOf(uint256{}));
-    EXPECT_TRUE(root.isPrefixOf(kTestKey));
-}
-
-TEST(SHAMapNodeIDTest, child_id_is_prefix_of_keys_in_that_branch)
-{
-    // Walking the branches spelled by the key's own nibbles must keep every
-    // intermediate ID a prefix of that key.
-    SHAMapNodeID id;
-    for (auto depth = 0u; depth < SHAMap::kLeafDepth; ++depth)
-    {
-        id = id.getChildNodeID(selectBranch(id, kTestKey));
-        EXPECT_EQ(id.getDepth(), depth + 1);
-        EXPECT_TRUE(id.isPrefixOf(kTestKey)) << "depth " << id.getDepth();
-    }
-}
-
-TEST(SHAMapNodeIDTest, wrong_branch_is_not_prefix_of_key)
-{
-    SHAMapNodeID const root;
-    auto const correct = selectBranch(root, kTestKey);
-    ASSERT_EQ(correct, 0xbu);
-
-    // An ID built from the wrong branch still has a valid depth and a self-consistent mask, so
-    // isPrefixOf(kTestKey) below is what actually distinguishes the correct branch from the rest.
-    for (auto branch = 0u; branch < SHAMap::kBranchFactor; ++branch)
-    {
-        auto const child = root.getChildNodeID(branch);
-        EXPECT_EQ(child.getDepth(), 1u);
-        EXPECT_EQ(child.isPrefixOf(kTestKey), branch == correct) << "branch " << branch;
-    }
-}
-
-TEST(SHAMapNodeIDTest, prefix_check_is_depth_sensitive)
-{
-    // kTestKey and kOther agree on the first two nibbles ("b9") and then diverge.
-    constexpr uint256 kOther("b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
-
-    auto id = SHAMapNodeID{}.getChildNodeID(selectBranch(SHAMapNodeID{}, kTestKey));
-    EXPECT_TRUE(id.isPrefixOf(kTestKey));
-    EXPECT_TRUE(id.isPrefixOf(kOther)) << "shared first nibble";
-
-    id = id.getChildNodeID(selectBranch(id, kTestKey));
-    EXPECT_TRUE(id.isPrefixOf(kTestKey));
-    EXPECT_TRUE(id.isPrefixOf(kOther)) << "shared second nibble";
-
-    // Third nibble differs, so the deeper ID no longer covers kOther.
-    id = id.getChildNodeID(selectBranch(id, kTestKey));
-    EXPECT_TRUE(id.isPrefixOf(kTestKey));
-    EXPECT_FALSE(id.isPrefixOf(kOther));
-}
-
-TEST(SHAMapNodeIDTest, leaf_id_from_key_is_prefix_of_that_key)
-{
-    SHAMapNodeID const leaf{SHAMap::kLeafDepth, kTestKey};
-    EXPECT_TRUE(leaf.isPrefixOf(kTestKey));
-
-    // At full depth the prefix is the whole key, so nothing else matches.
-    constexpr uint256 kOther("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca9");
-    EXPECT_FALSE(leaf.isPrefixOf(kOther));
-}
-
-TEST(SHAMapNodeIDTest, create_id_masks_key_to_depth)
-{
-    for (auto depth = 0u; depth <= SHAMap::kLeafDepth; ++depth)
-    {
-        auto const id = SHAMapNodeID::createID(depth, kTestKey);
-        EXPECT_EQ(id.getDepth(), depth);
-        EXPECT_TRUE(id.isPrefixOf(kTestKey)) << "depth " << depth;
-    }
-}
-
-// The guards below must hold with XRPL_ASSERT compiled out (NDEBUG), so each one
-// has to be a real runtime check rather than an assert.
-
-TEST(SHAMapNodeIDTest, child_of_leaf_depth_id_throws)
-{
-    auto const leafDepthID = SHAMapNodeID::createID(SHAMap::kLeafDepth, kTestKey);
-    ASSERT_EQ(leafDepthID.getDepth(), SHAMap::kLeafDepth);
-    EXPECT_THROW((void)leafDepthID.getChildNodeID(0), std::logic_error);
-}
-
-TEST(SHAMapNodeIDTest, out_of_range_depth_is_clamped)
-{
-    // A depth past kLeafDepth has no mask in depthMask's 65-entry table, so both the constructor
-    // and createID clamp it. createID needs its own clamp: it picks the mask while evaluating the
-    // constructor's argument, so the constructor's clamp cannot cover that read.
-    //
-    // Both clamps are marked UNREACHABLE, which is an assert and therefore fatal wherever asserts
-    // are live. Only a build with them compiled out (or routed to Antithesis's non-fatal handler)
-    // reaches the clamp itself, so that is the only configuration that can assert on the result.
-#if defined(NDEBUG) || defined(ENABLE_VOIDSTAR)
-    for (auto const depth : {SHAMap::kLeafDepth + 1u, 100u, 255u, 256u, 320u})
-    {
-        auto const id = SHAMapNodeID::createID(depth, kTestKey);
-
-        // Clamped to a real depth, not the depth asked for, and not a byte-narrowed version of it:
-        // 256 would otherwise become 0 and name the root, 320 would become 64.
-        EXPECT_EQ(id.getDepth(), SHAMap::kLeafDepth) << "depth " << depth;
-
-        // id_ and depth_ still agree, so the object is usable rather than merely non-crashing.
-        EXPECT_TRUE(id.isPrefixOf(kTestKey)) << "depth " << depth;
-        EXPECT_EQ(id, SHAMapNodeID::createID(SHAMap::kLeafDepth, kTestKey)) << "depth " << depth;
-
-        // The clamp holds through the wire format too, which encodes the depth in one byte.
-        auto const roundTripped = deserializeSHAMapNodeID(id.getRawString());
-        ASSERT_TRUE(roundTripped.has_value()) << "depth " << depth;
-        EXPECT_EQ(roundTripped->getDepth(), SHAMap::kLeafDepth) << "depth " << depth;
-    }
-
-    // The constructor clamps on its own, for the paths that do not go through createID.
-    SHAMapNodeID const direct{SHAMap::kLeafDepth + 1u, uint256{}};
-    EXPECT_EQ(direct.getDepth(), SHAMap::kLeafDepth);
-#else
-    EXPECT_DEATH(
-        (void)SHAMapNodeID::createID(SHAMap::kLeafDepth + 1u, kTestKey), "depth within tree");
-#endif
-}
-
-TEST(SHAMapNodeIDTest, select_branch_clamps_leaf_depth)
-{
-    // selectBranch's own precondition is depth < kLeafDepth: a depth-64 ID has no nibble left
-    // to select. That makes it unlike the guards above, which have a throw/return reachable
-    // even with XRPL_ASSERT compiled out; selectBranch has no such path, so the two build
-    // configurations have to be tested differently.
-    //
-    // Under ENABLE_VOIDSTAR, XRPL_ASSERT routes to Antithesis's assert_impl, which only records
-    // the hit and returns rather than aborting, even though NDEBUG is undefined there (voidstar
-    // requires a Debug build). So the assert is live in name but never fatal, the same as the
-    // NDEBUG case below.
-    auto const leafDepthID = SHAMapNodeID::createID(SHAMap::kLeafDepth, kTestKey);
-
-#if defined(NDEBUG) || defined(ENABLE_VOIDSTAR)
-    // With the assert compiled out or routed to a non-fatal handler, the clamp is what stands
-    // between this call and reading past the end of the 32-byte key. Clamping means it reads the
-    // same byte, and returns the same branch, as the deepest ID that still has one: depth 63.
-    auto const deepestWithBranchID = SHAMapNodeID::createID(SHAMap::kLeafDepth - 1u, kTestKey);
-    auto const branch = selectBranch(leafDepthID, kTestKey);
-    EXPECT_LT(branch, SHAMap::kBranchFactor);
-    EXPECT_EQ(branch, selectBranch(deepestWithBranchID, kTestKey));
-#else
-    // In a debug build the assert is live and must reject this call outright, in a forked
-    // process so a failure here cannot take down the rest of the suite.
-    EXPECT_DEATH((void)selectBranch(leafDepthID, kTestKey), "depth below leaf depth");
-#endif
-}
-
-TEST(SHAMapNodeIDTest, deserialize_rejects_out_of_range_depth)
-{
-    // getRawString() only serializes a depth already accepted by the constructor's own
-    // assertion, so an out-of-range depth here is built by hand instead.
-    auto serializeWithRawDepth = [](unsigned int depth) {
-        Serializer s;
-        s.addBitString(uint256{});
-        s.add8(static_cast<unsigned char>(depth));
-        return s.getString();
-    };
-
-    for (auto const depth : {65u, 100u, 255u})
-    {
-        EXPECT_FALSE(deserializeSHAMapNodeID(serializeWithRawDepth(depth)).has_value())
-            << "depth " << depth;
-    }
-
-    // A depth-64 ID is legal, since leaves live there, but it has no children.
-    auto const id =
-        deserializeSHAMapNodeID(SHAMapNodeID{SHAMap::kLeafDepth, uint256{}}.getRawString());
-    ASSERT_TRUE(id.has_value());
-    // NOLINTNEXTLINE(bugprone-unchecked-optional-access) has_value checked above
-    EXPECT_THROW((void)id->getChildNodeID(0), std::logic_error);
-}
-
-}  // namespace xrpl::tests