3#include <xrpl/basics/Log.h>
4#include <xrpl/basics/Number.h>
5#include <xrpl/basics/base_uint.h>
6#include <xrpl/beast/utility/Journal.h>
7#include <xrpl/beast/utility/Zero.h>
8#include <xrpl/beast/utility/instrumentation.h>
9#include <xrpl/ledger/PaymentSandbox.h>
10#include <xrpl/ledger/helpers/AMMHelpers.h>
11#include <xrpl/ledger/helpers/OfferHelpers.h>
12#include <xrpl/protocol/Concepts.h>
13#include <xrpl/protocol/Feature.h>
14#include <xrpl/protocol/IOUAmount.h>
15#include <xrpl/protocol/Indexes.h>
16#include <xrpl/protocol/MPTAmount.h>
17#include <xrpl/protocol/Quality.h>
18#include <xrpl/protocol/QualityFunction.h>
19#include <xrpl/protocol/STAmount.h>
20#include <xrpl/protocol/TER.h>
21#include <xrpl/protocol/XRPAmount.h>
22#include <xrpl/tx/paths/detail/FlatSets.h>
23#include <xrpl/tx/paths/detail/Steps.h>
24#include <xrpl/tx/transactors/dex/AMMContext.h>
26#include <boost/container/flat_set.hpp>
44template <
class TInAmt,
class TOutAmt>
70 boost::container::flat_set<UInt256> ofrsToRemoveMember,
82 StrandResult(Strand
const& strand, boost::container::flat_set<UInt256> ofrsToRemoveMember)
99template <
class TInAmt,
class TOutAmt>
100StrandResult<TInAmt, TOutAmt>
103 Strand
const& strand,
111 JLOG(j.
warn()) <<
"Empty strand passed to Liquidity";
115 boost::container::flat_set<UInt256> ofrsToRm;
117 if (isDirectXrpToXrp<TInAmt, TOutAmt>(strand))
119 return Result{strand, std::move(ofrsToRm)};
135 for (
auto i = s; i--;)
137 auto r = strand[i]->rev(*sb, *afView, ofrsToRm, stepOut);
138 if (strand[i]->isZero(r.second))
140 JLOG(j.
trace()) <<
"Strand found dry in rev";
141 return Result{strand, std::move(ofrsToRm)};
144 if (i == 0 && maxIn && *maxIn <
get<TInAmt>(r.first))
152 r = strand[i]->fwd(*sb, *afView, ofrsToRm,
EitherAmount(*maxIn));
155 if (strand[i]->isZero(r.second))
157 JLOG(j.
trace()) <<
"First step found dry";
158 return Result{strand, std::move(ofrsToRm)};
167 <<
"Re-executed limiting step failed. r.first: "
170 "xrpl::flow : first step re-executing the "
171 "limiting step failed");
172 return Result{strand, std::move(ofrsToRm)};
176 else if (!strand[i]->equalOut(r.second, stepOut))
186 r = strand[i]->rev(*sb, *afView, ofrsToRm, stepOut);
189 if (strand[i]->isZero(r.second))
193 JLOG(j.
trace()) <<
"Limiting step found dry";
194 return Result{strand, std::move(ofrsToRm)};
196 if (!strand[i]->equalOut(r.second, stepOut))
204 <<
"Re-executed limiting step failed. r.second: " << r.second
205 <<
" stepOut: " << stepOut;
207 JLOG(j.
fatal()) <<
"Re-executed limiting step failed";
210 "xrpl::flow : limiting step re-executing the "
211 "limiting step failed");
212 return Result{strand, std::move(ofrsToRm)};
224 for (
auto i = limitingStep + 1; i < s; ++i)
226 auto const r = strand[i]->fwd(*sb, *afView, ofrsToRm, stepIn);
227 if (strand[i]->isZero(r.second))
231 JLOG(j.
trace()) <<
"Non-limiting step found dry";
232 return Result{strand, std::move(ofrsToRm)};
234 if (!strand[i]->equalIn(r.first, stepIn))
241 JLOG(j.
fatal()) <<
"Re-executed forward pass failed. r.first: " << r.first
242 <<
" stepIn: " << stepIn;
244 JLOG(j.
fatal()) <<
"Re-executed forward pass failed";
247 "xrpl::flow : non-limiting step re-executing the "
248 "forward pass failed");
249 return Result{strand, std::move(ofrsToRm)};
258 auto const strandIn = *strand.front()->cachedIn();
259 auto const strandOut = *strand.back()->cachedOut();
269 *strand[0]->cachedIn());
270 for (
auto i = 0; i < s; ++i)
273 std::tie(
valid, stepIn) = strand[i]->validFwd(checkSB, checkAfView, stepIn);
276 JLOG(j.
warn()) <<
"Strand re-execute check failed. Step: " << i;
283 bool const inactive =
285 return step->inactive();
296 catch (FlowException
const&)
298 return Result{strand, std::move(ofrsToRm)};
303template <
class TInAmt,
class TOutAmt>
309 boost::container::flat_set<UInt256> removableOffers;
310 TER ter = temUNKNOWN;
312 FlowResult() =
default;
317 PaymentSandbox&& sandbox,
318 boost::container::flat_set<UInt256> ofrsToRm)
321 , sandbox(
std::move(sandbox))
322 , removableOffers(
std::move(ofrsToRm))
327 FlowResult(TER ter, boost::container::flat_set<UInt256> ofrsToRm)
328 : removableOffers(std::
move(ofrsToRm)), ter(ter)
336 boost::container::flat_set<UInt256> ofrsToRm)
337 : in(in), out(out), removableOffers(std::
move(ofrsToRm)), ter(ter)
344inline std::optional<Quality>
345qualityUpperBound(
ReadView const& v, Strand
const& strand)
348 std::optional<Quality> stepQ;
350 for (
auto const& step : strand)
352 if (
std::tie(stepQ, dir) = step->qualityUpperBound(v, dir); stepQ)
375template <StepAmount TOutAmt>
379 Strand
const& strand,
380 TOutAmt
const& remainingOut,
383 std::optional<QualityFunction> stepQualityFunc;
384 std::optional<QualityFunction> qf;
386 for (
auto const& step : strand)
388 if (
std::tie(stepQualityFunc, dir) = step->getQualityFunc(v, dir); stepQualityFunc)
392 qf = stepQualityFunc;
396 qf->combine(*stepQualityFunc);
406 if (!qf || qf->isConst())
409 auto const out = [&] {
410 auto const out = qf->outFromAvgQ(limitQuality);
415 auto const roundedOut = TOutAmt{*out};
420 if (v.rules().enabled(featureMPTokensV2) && roundedOut > *out &&
421 !qf->satisfiesAvgQ(limitQuality, roundedOut))
424 return TOutAmt{*out};
435 static_assert(kAlwaysFalse,
"Unhandled StepAmount type");
457 std::vector<Strand const*> cur_;
459 std::vector<Strand const*> next_;
462 ActiveStrands(std::vector<Strand>
const& strands)
466 for (
auto& strand : strands)
473 activateNext(ReadView
const& v, std::optional<Quality>
const& limitQuality)
480 std::vector<std::pair<Quality, Strand const*>> strandQualities;
482 if (next_.
size() > 1)
484 for (Strand
const* strand : next_)
486 if (strand ==
nullptr)
491 if (
auto const qual = qualityUpperBound(v, *strand))
493 if (limitQuality && *qual < *limitQuality)
511 [](
auto const& lhs,
auto const& rhs) {
513 return std::get<Quality>(lhs) > std::get<Quality>(rhs);
516 next_.reserve(strandQualities.
size());
517 for (
auto const& sq : strandQualities)
519 next_.push_back(std::get<Strand const*>(sq));
526 [[nodiscard]] Strand
const*
529 if (i >= cur_.
size())
532 UNREACHABLE(
"xrpl::ActiveStrands::get : input out of range");
540 push(Strand
const* s)
547 pushRemainingCurToNext(
size_t i)
549 if (i >= cur_.
size())
581template <StepAmount TInAmt, StepAmount TOutAmt>
582FlowResult<TInAmt, TOutAmt>
586 TOutAmt
const& outReq,
601 Strand
const& strand;
608 Strand
const& strand,
610 : in(in), out(out), sb(std::move(sb)), strand(strand), quality(quality)
630 TOutAmt remainingOut(outReq);
635 ActiveStrands activeStrands(strands);
640 boost::container::flat_multiset<TInAmt> savedIns;
641 savedIns.reserve(maxTries);
642 boost::container::flat_multiset<TOutAmt> savedOuts;
643 savedOuts.reserve(maxTries);
651 TResult total = *col.begin();
652 for (
auto it = col.begin() + 1; it != col.end(); ++it)
654 auto const next = checkedStepAddOpt(total, *it);
664 boost::container::flat_set<UInt256> ofrsToRmOnFail;
669 if (curTry >= maxTries)
674 activeStrands.activateNext(sb, limitQuality);
679 auto const limitRemainingOut = [&] {
680 if (activeStrands.size() == 1 && limitQuality)
682 if (
auto const strand = activeStrands.get(0))
683 return limitOut(sb, *strand, remainingOut, *limitQuality);
687 auto const adjustedRemOut = limitRemainingOut != remainingOut;
689 boost::container::flat_set<UInt256> ofrsToRm;
691 for (
size_t strandIndex = 0, sie = activeStrands.size(); strandIndex != sie; ++strandIndex)
693 Strand
const* strand = activeStrands.get(strandIndex);
705 auto const strandQ = qualityUpperBound(sb, *strand);
706 if (!strandQ || *strandQ < *limitQuality)
714 offersConsidered += f.ofrsUsed;
720 f.out <= remainingOut && f.sandbox && (!remainingIn || f.in <= *remainingIn),
721 "xrpl::flow : remaining constraints");
725 JLOG(j.
trace()) <<
"New flow iter (iter, in, out): " << curTry - 1 <<
" "
731 if (limitQuality && q < *limitQuality &&
734 JLOG(j.
trace()) <<
"Path rejected by limitQuality"
735 <<
" limit: " << *limitQuality <<
" path q: " << q;
739 XRPL_ASSERT(!best,
"xrpl::flow : best is unset");
741 activeStrands.push(strand);
742 best.
emplace(f.in, f.out, std::move(*f.sandbox), *strand, q);
743 activeStrands.pushRemainingCurToNext(strandIndex + 1);
747 bool const shouldBreak = !best || offersConsidered >= maxOffersToConsider;
751 savedIns.insert(best->in);
752 savedOuts.insert(best->out);
753 auto const sumOut =
sum(savedOuts);
756 remainingOut = outReq - *sumOut;
759 auto const sumIn =
sum(savedIns);
762 remainingIn = *sendMax - *sumIn;
767 <<
" remainingOut: " <<
to_string(remainingOut);
774 JLOG(j.
trace()) <<
"All strands dry.";
778 if (!ofrsToRm.empty())
781 for (
auto const& o : ofrsToRm)
792 auto const actualOutOpt =
sum(savedOuts);
793 auto const actualInOpt =
sum(savedIns);
794 if (!actualOutOpt || !actualInOpt)
796 auto const actualOut = *actualOutOpt;
797 auto const actualIn = *actualInOpt;
812 if (actualOut != outReq)
814 if (actualOut > outReq)
830 return {
tecPATH_PARTIAL, actualIn, actualOut, std::move(ofrsToRmOnFail)};
842 XRPL_ASSERT(remainingIn,
"xrpl::flow : nonzero remainingIn");
844 return {
tecPATH_PARTIAL, actualIn, actualOut, std::move(ofrsToRmOnFail)};
847 return {actualIn, actualOut, std::move(sb), std::move(ofrsToRmOnFail)};
A generic endpoint for log messages.
Stream trace() const
Severity stream access functions.
Maintains AMM info per overall payment engine execution and individual iteration.
void setMultiPath(bool fs)
void clear()
Strand execution may fail.
Floating point representation of amounts with high dynamic range.
Number is a floating point type that can represent a wide range of values.
A wrapper which makes credits unavailable to balances.
Represents the logical ratio of output currency to input currency.
static std::uint64_t const kURateOne
SLE::pointer peek(Keylet const &k) override
Prepare to modify the SLE associated with key.
T emplace_back(T... args)
T make_optional(T... args)
TER valid(STTx const &tx, ReadView const &view, AccountID const &src, beast::Journal j)
Keylet offer(AccountID const &id, SeqProxy const &seq) noexcept
An offer from an account.
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
static auto sum(TCollection const &col)
TER offerDelete(ApplyView &view, SLE::Ref sle, beast::Journal j)
Delete an offer.
static void limitStepOut(Offer const &offer, TAmounts< TIn, TOut > &ofrAmt, TAmounts< TIn, TOut > &stpAmt, TOut &ownerGives, std::uint32_t transferRateIn, std::uint32_t transferRateOut, TOut const &limit)
T get(Section const §ion, std::string const &name, T const &defaultValue=T{})
Retrieve a key/value pair from a section.
void setUnion(boost::container::flat_set< T > &dst, boost::container::flat_set< T > const &src)
Given two flat sets dst and src, compute dst = dst union src.
boost::outcome_v2::result< T, std::error_code > Result
std::string to_string(BaseUInt< Bits, Tag > const &a)
T toAmount(STAmount const &amt)=delete
StrandResult< TInAmt, TOutAmt > flow(PaymentSandbox const &baseView, Strand const &strand, std::optional< TInAmt > const &maxIn, TOutAmt const &out, beast::Journal j)
Request out amount from a strand.
bool withinRelativeDistance(Quality const &calcQuality, Quality const &reqQuality, Number const &dist)
Check if the relative distance between the qualities is within the requested distance.
Quality composedQuality(Quality const &lhs, Quality const &rhs)
Calculate the quality of a two-hop path given the two hops.
Result of flow() execution of a single Strand.
TOutAmt out
Currency amount out.
StrandResult(Strand const &strand, TInAmt const &in, TOutAmt const &out, PaymentSandbox &&sandbox, boost::container::flat_set< UInt256 > ofrsToRemoveMember, bool inactive)
std::optional< PaymentSandbox > sandbox
Resulting Sandbox state.
bool success
Strand succeeded.
StrandResult()=default
Strand result constructor.
boost::container::flat_set< UInt256 > ofrsToRm
Offers to remove.
StrandResult(Strand const &strand, boost::container::flat_set< UInt256 > ofrsToRemoveMember)
TInAmt in
Currency amount in.
bool inactive
Strand should not considered as a further source of liquidity (dry).