Directory_test.cpp

#include <test/jtx.h>
 
#include <xrpl/basics/random.h>
#include <xrpl/ledger/BookDirs.h>
#include <xrpl/ledger/Sandbox.h>
#include <xrpl/ledger/helpers/DirectoryHelpers.h>
#include <xrpl/protocol/Feature.h>
#include <xrpl/protocol/Protocol.h>
#include <xrpl/protocol/TER.h>
#include <xrpl/protocol/jss.h>
 
#include <algorithm>
#include <limits>
 
namespace xrpl {
namespace test {
 
struct Directory_test : public beast::unit_test::suite
{
    // Map [0-15576] into a unique 3 letter currency code
    std::string
    currcode(std::size_t i)
    {
        // There are only 17576 possible combinations
        BEAST_EXPECT(i < 17577);
 
        std::string code;
 
        for (int j = 0; j != 3; ++j)
        {
            code.push_back('A' + (i % 26));
            i /= 26;
        }
 
        return code;
    }
 
    // Insert n empty pages, numbered [0, ... n - 1], in the
    // specified directory:
    static void
    makePages(Sandbox& sb, uint256 const& base, std::uint64_t n)
    {
        for (std::uint64_t i = 0; i < n; ++i)
        {
            auto p = std::make_shared<SLE>(keylet::page(base, i));
 
            p->setFieldV256(sfIndexes, STVector256{});
 
            if (i + 1 == n)
            {
                p->setFieldU64(sfIndexNext, 0);
            }
            else
            {
                p->setFieldU64(sfIndexNext, i + 1);
            }
 
            if (i == 0)
            {
                p->setFieldU64(sfIndexPrevious, n - 1);
            }
            else
            {
                p->setFieldU64(sfIndexPrevious, i - 1);
            }
 
            sb.insert(p);
        }
    }
 
    void
    testDirectoryOrdering()
    {
        using namespace jtx;
 
        auto gw = Account("gw");
        auto USD = gw["USD"];
        auto alice = Account("alice");
        auto bob = Account("bob");
 
        testcase("Directory Ordering (with 'SortedDirectories' amendment)");
 
        Env env(*this);
        env.fund(XRP(10000000), alice, gw);
 
        std::uint32_t const firstOfferSeq{env.seq(alice)};
        for (std::size_t i = 1; i <= 400; ++i)
            env(offer(alice, USD(i), XRP(i)));
        env.close();
 
        // Check Alice's directory: it should contain one
        // entry for each offer she added, and, within each
        // page the entries should be in sorted order.
        {
            auto const view = env.closed();
 
            std::uint64_t page = 0;
 
            do
            {
                auto p = view->read(keylet::page(keylet::ownerDir(alice), page));
 
                // Ensure that the entries in the page are sorted
                auto const& v = p->getFieldV256(sfIndexes);
                BEAST_EXPECT(std::is_sorted(v.begin(), v.end()));
 
                // Ensure that the page contains the correct orders by
                // calculating which sequence numbers belong here.
                std::uint32_t const minSeq = firstOfferSeq + (page * dirNodeMaxEntries);
                std::uint32_t const maxSeq = minSeq + dirNodeMaxEntries;
 
                for (auto const& e : v)
                {
                    auto c = view->read(keylet::child(e));
                    BEAST_EXPECT(c);
                    BEAST_EXPECT(c->getFieldU32(sfSequence) >= minSeq);
                    BEAST_EXPECT(c->getFieldU32(sfSequence) < maxSeq);
                }
 
                page = p->getFieldU64(sfIndexNext);
            } while (page != 0);
        }
 
        // Now check the orderbook: it should be in the order we placed
        // the offers.
        auto book = BookDirs(*env.current(), Book({xrpIssue(), USD.issue(), std::nullopt}));
        int count = 1;
 
        for (auto const& offer : book)
        {
            count++;
            BEAST_EXPECT(offer->getFieldAmount(sfTakerPays) == USD(count));
            BEAST_EXPECT(offer->getFieldAmount(sfTakerGets) == XRP(count));
        }
    }
 
    void
    testDirIsEmpty()
    {
        testcase("dirIsEmpty");
 
        using namespace jtx;
        auto const alice = Account("alice");
        auto const bob = Account("bob");
        auto const charlie = Account("charlie");
        auto const gw = Account("gw");
 
        Env env(*this);
 
        env.fund(XRP(1000000), alice, charlie, gw);
        env.close();
 
        // alice should have an empty directory.
        BEAST_EXPECT(dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
 
        // Give alice a signer list, then there will be stuff in the directory.
        env(signers(alice, 1, {{bob, 1}}));
        env.close();
        BEAST_EXPECT(!dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
 
        env(signers(alice, jtx::none));
        env.close();
        BEAST_EXPECT(dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
 
        std::vector<IOU> const currencies = [this, &gw]() {
            std::vector<IOU> c;
 
            c.reserve((2 * dirNodeMaxEntries) + 3);
 
            while (c.size() != c.capacity())
                c.push_back(gw[currcode(c.size())]);
 
            return c;
        }();
 
        // First, Alice creates a lot of trustlines, and then
        // deletes them in a different order:
        {
            auto cl = currencies;
 
            for (auto const& c : cl)
            {
                env(trust(alice, c(50)));
                env.close();
            }
 
            BEAST_EXPECT(!dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
 
            std::shuffle(cl.begin(), cl.end(), default_prng());
 
            for (auto const& c : cl)
            {
                env(trust(alice, c(0)));
                env.close();
            }
 
            BEAST_EXPECT(dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
        }
 
        // Now, Alice creates offers to buy currency, creating
        // implicit trust lines.
        {
            auto cl = currencies;
 
            BEAST_EXPECT(dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
 
            for (auto const& c : currencies)
            {
                env(trust(charlie, c(50)));
                env.close();
                env(pay(gw, charlie, c(50)));
                env.close();
                env(offer(alice, c(50), XRP(50)));
                env.close();
            }
 
            BEAST_EXPECT(!dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
 
            // Now fill the offers in a random order. Offer
            // entries will drop, and be replaced by trust
            // lines that are implicitly created.
            std::shuffle(cl.begin(), cl.end(), default_prng());
 
            for (auto const& c : cl)
            {
                env(offer(charlie, XRP(50), c(50)));
                env.close();
            }
            BEAST_EXPECT(!dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
            // Finally, Alice now sends the funds back to
            // Charlie. The implicitly created trust lines
            // should drop away:
            std::shuffle(cl.begin(), cl.end(), default_prng());
 
            for (auto const& c : cl)
            {
                env(pay(alice, charlie, c(50)));
                env.close();
            }
 
            BEAST_EXPECT(dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
        }
    }
 
    void
    testRipd1353()
    {
        testcase("RIPD-1353 Empty Offer Directories");
 
        using namespace jtx;
        Env env(*this);
 
        auto const gw = Account{"gateway"};
        auto const alice = Account{"alice"};
        auto const USD = gw["USD"];
 
        env.fund(XRP(10000), alice, gw);
        env.close();
        env.trust(USD(1000), alice);
        env(pay(gw, alice, USD(1000)));
 
        auto const firstOfferSeq = env.seq(alice);
 
        // Fill up three pages of offers
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < dirNodeMaxEntries; ++j)
                env(offer(alice, XRP(1), USD(1)));
        }
        env.close();
 
        // remove all the offers. Remove the middle page last
        for (auto page : {0, 2, 1})
        {
            for (int i = 0; i < dirNodeMaxEntries; ++i)
            {
                env(offer_cancel(alice, firstOfferSeq + (page * dirNodeMaxEntries) + i));
                env.close();
            }
        }
 
        // All the offers have been cancelled, so the book
        // should have no entries and be empty:
        {
            Sandbox const sb(env.closed().get(), tapNONE);
            uint256 const bookBase = getBookBase({xrpIssue(), USD.issue(), std::nullopt});
 
            BEAST_EXPECT(dirIsEmpty(sb, keylet::page(bookBase)));
            BEAST_EXPECT(!sb.succ(bookBase, getQualityNext(bookBase)));
        }
 
        // Alice returns the USD she has to the gateway
        // and removes her trust line. Her owner directory
        // should now be empty:
        {
            env.trust(USD(0), alice);
            env(pay(alice, gw, alice["USD"](1000)));
            env.close();
            BEAST_EXPECT(dirIsEmpty(*env.closed(), keylet::ownerDir(alice)));
        }
    }
 
    void
    testEmptyChain()
    {
        testcase("Empty Chain on Delete");
 
        using namespace jtx;
        Env env(*this);
 
        auto const gw = Account{"gateway"};
        auto const alice = Account{"alice"};
        auto const USD = gw["USD"];
 
        env.fund(XRP(10000), alice);
        env.close();
 
        constexpr uint256 base("fb71c9aa3310141da4b01d6c744a98286af2d72ab5448d5adc0910ca0c910880");
 
        constexpr uint256 item("bad0f021aa3b2f6754a8fe82a5779730aa0bbbab82f17201ef24900efc2c7312");
 
        {
            // Create a chain of three pages:
            Sandbox sb(env.closed().get(), tapNONE);
            makePages(sb, base, 3);
 
            // Insert an item in the middle page:
            {
                auto p = sb.peek(keylet::page(base, 1));
                BEAST_EXPECT(p);
 
                STVector256 v;
                v.push_back(item);
                p->setFieldV256(sfIndexes, v);
                sb.update(p);
            }
 
            // Now, try to delete the item from the middle
            // page. This should cause all pages to be deleted:
            BEAST_EXPECT(sb.dirRemove(keylet::page(base, 0), 1, keylet::unchecked(item), false));
            BEAST_EXPECT(!sb.peek(keylet::page(base, 2)));
            BEAST_EXPECT(!sb.peek(keylet::page(base, 1)));
            BEAST_EXPECT(!sb.peek(keylet::page(base, 0)));
        }
 
        {
            // Create a chain of four pages:
            Sandbox sb(env.closed().get(), tapNONE);
            makePages(sb, base, 4);
 
            // Now add items on pages 1 and 2:
            {
                auto p1 = sb.peek(keylet::page(base, 1));
                BEAST_EXPECT(p1);
 
                STVector256 v1;
                v1.push_back(~item);
                p1->setFieldV256(sfIndexes, v1);
                sb.update(p1);
 
                auto p2 = sb.peek(keylet::page(base, 2));
                BEAST_EXPECT(p2);
 
                STVector256 v2;
                v2.push_back(item);
                p2->setFieldV256(sfIndexes, v2);
                sb.update(p2);
            }
 
            // Now, try to delete the item from page 2.
            // This should cause pages 2 and 3 to be
            // deleted:
            BEAST_EXPECT(sb.dirRemove(keylet::page(base, 0), 2, keylet::unchecked(item), false));
            BEAST_EXPECT(!sb.peek(keylet::page(base, 3)));
            BEAST_EXPECT(!sb.peek(keylet::page(base, 2)));
 
            auto p1 = sb.peek(keylet::page(base, 1));
            BEAST_EXPECT(p1);
            BEAST_EXPECT(p1->getFieldU64(sfIndexNext) == 0);
            BEAST_EXPECT(p1->getFieldU64(sfIndexPrevious) == 0);
 
            auto p0 = sb.peek(keylet::page(base, 0));
            BEAST_EXPECT(p0);
            BEAST_EXPECT(p0->getFieldU64(sfIndexNext) == 1);
            BEAST_EXPECT(p0->getFieldU64(sfIndexPrevious) == 1);
        }
    }
 
    void
    testPreviousTxnID()
    {
        testcase("fixPreviousTxnID");
        using namespace jtx;
 
        auto const gw = Account{"gateway"};
        auto const alice = Account{"alice"};
        auto const USD = gw["USD"];
 
        auto ledger_data = [this](Env& env) {
            Json::Value params;
            params[jss::type] = jss::directory;
            params[jss::ledger_index] = "validated";
            auto const result = env.rpc("json", "ledger_data", to_string(params))[jss::result];
            BEAST_EXPECT(!result.isMember(jss::marker));
            return result;
        };
 
        // fixPreviousTxnID is disabled.
        Env env(*this, testable_amendments() - fixPreviousTxnID);
        env.fund(XRP(10000), alice, gw);
        env.close();
        env.trust(USD(1000), alice);
        env(pay(gw, alice, USD(1000)));
        env.close();
 
        {
            auto const jrr = ledger_data(env);
            auto const& jstate = jrr[jss::state];
            BEAST_EXPECTS(checkArraySize(jstate, 2), jrr.toStyledString());
            for (auto const& directory : jstate)
            {
                BEAST_EXPECT(directory["LedgerEntryType"] == jss::DirectoryNode);  // sanity check
                // The PreviousTxnID and PreviousTxnLgrSeq fields should not be
                // on the DirectoryNode object when the amendment is disabled
                BEAST_EXPECT(!directory.isMember("PreviousTxnID"));
                BEAST_EXPECT(!directory.isMember("PreviousTxnLgrSeq"));
            }
        }
 
        // Now enable the amendment so the directory node is updated.
        env.enableFeature(fixPreviousTxnID);
        env.close();
 
        // Make sure the `PreviousTxnID` and `PreviousTxnLgrSeq` fields now
        // exist
        env(offer(alice, XRP(1), USD(1)));
        auto const txID = to_string(env.tx()->getTransactionID());
        auto const ledgerSeq = env.current()->header().seq;
        env.close();
        // Make sure the fields only exist if the object is touched
        env(noop(gw));
        env.close();
 
        {
            auto const jrr = ledger_data(env);
            auto const& jstate = jrr[jss::state];
            BEAST_EXPECTS(checkArraySize(jstate, 3), jrr.toStyledString());
            for (auto const& directory : jstate)
            {
                BEAST_EXPECT(directory["LedgerEntryType"] == jss::DirectoryNode);  // sanity check
                if (directory[jss::Owner] == gw.human())
                {
                    // gw's directory did not get touched, so it
                    // should not have those fields populated
                    BEAST_EXPECT(!directory.isMember("PreviousTxnID"));
                    BEAST_EXPECT(!directory.isMember("PreviousTxnLgrSeq"));
                }
                else
                {
                    // All of the other directories, including the order
                    // book, did get touched, so they should have those
                    // fields
                    BEAST_EXPECT(
                        directory.isMember("PreviousTxnID") &&
                        directory["PreviousTxnID"].asString() == txID);
                    BEAST_EXPECT(
                        directory.isMember("PreviousTxnLgrSeq") &&
                        directory["PreviousTxnLgrSeq"].asUInt() == ledgerSeq);
                }
            }
        }
    }
 
    void
    testDirectoryFull()
    {
        using namespace test::jtx;
        Account alice("alice");
 
        auto const testCase = [&, this](FeatureBitset features, auto setup) {
            using namespace test::jtx;
 
            Env env(*this, features);
            env.fund(XRP(20000), alice);
            env.close();
 
            auto const [lastPage, full] = setup(env);
 
            // Populate root page and last page
            for (int i = 0; i < 63; ++i)
                env(credentials::create(alice, alice, std::to_string(i)));
            env.close();
 
            // NOTE, everything below can only be tested on open ledger because
            // there is no transaction type to express what bumpLastPage does.
 
            // Bump position of last page from 1 to highest possible
            auto const res = directory::bumpLastPage(
                env,
                lastPage,
                keylet::ownerDir(alice.id()),
                [lastPage, this](ApplyView& view, uint256 key, std::uint64_t page) {
                    auto sle = view.peek({ltCREDENTIAL, key});
                    if (!BEAST_EXPECT(sle))
                        return false;
 
                    BEAST_EXPECT(page == lastPage);
                    sle->setFieldU64(sfIssuerNode, page);
                    // sfSubjectNode is not set in self-issued credentials
                    view.update(sle);
                    return true;
                });
            BEAST_EXPECT(res);
 
            // Create one more credential
            env(credentials::create(alice, alice, std::to_string(63)));
 
            // Not enough space for another object if full
            auto const expected = full ? ter{tecDIR_FULL} : ter{tesSUCCESS};
            env(credentials::create(alice, alice, "foo"), expected);
 
            // Destroy all objects in directory
            for (int i = 0; i < 64; ++i)
                env(credentials::deleteCred(alice, alice, alice, std::to_string(i)));
 
            if (!full)
                env(credentials::deleteCred(alice, alice, alice, "foo"));
 
            // Verify directory is empty.
            auto const sle = env.le(keylet::ownerDir(alice.id()));
            BEAST_EXPECT(sle == nullptr);
 
            // Test completed
            env.close();
        };
 
        testCase(
            testable_amendments() - fixDirectoryLimit,
            [this](Env&) -> std::tuple<std::uint64_t, bool> {
                testcase("directory full without fixDirectoryLimit");
                return {dirNodeMaxPages - 1, true};
            });
        testCase(
            testable_amendments(),  //
            [this](Env&) -> std::tuple<std::uint64_t, bool> {
                testcase("directory not full with fixDirectoryLimit");
                return {dirNodeMaxPages - 1, false};
            });
        testCase(
            testable_amendments(),  //
            [this](Env&) -> std::tuple<std::uint64_t, bool> {
                testcase("directory full with fixDirectoryLimit");
                return {std::numeric_limits<std::uint64_t>::max(), true};
            });
    }
 
    void
    run() override
    {
        testDirectoryOrdering();
        testDirIsEmpty();
        testRipd1353();
        testEmptyChain();
        testPreviousTxnID();
        testDirectoryFull();
    }
};
 
BEAST_DEFINE_TESTSUITE_PRIO(Directory, ledger, xrpl, 1);
 
}  // namespace test
}  // namespace xrpl