xrpld
Loading...
Searching...
No Matches
Pathfinder.cpp
1#include <xrpld/rpc/detail/Pathfinder.h>
2
3#include <xrpld/app/main/Application.h>
4#include <xrpld/rpc/detail/AssetCache.h>
5#include <xrpld/rpc/detail/PathfinderUtils.h>
6#include <xrpld/rpc/detail/TrustLine.h>
7
8#include <xrpl/basics/Log.h>
9#include <xrpl/basics/base_uint.h>
10#include <xrpl/basics/join.h>
11#include <xrpl/beast/utility/Zero.h>
12#include <xrpl/beast/utility/instrumentation.h>
13#include <xrpl/core/Job.h>
14#include <xrpl/core/JobQueue.h>
15#include <xrpl/json/to_string.h> // IWYU pragma: keep
16#include <xrpl/ledger/ApplyView.h>
17#include <xrpl/ledger/OrderBookDB.h>
18#include <xrpl/ledger/PaymentSandbox.h>
19#include <xrpl/ledger/helpers/MPTokenHelpers.h>
20#include <xrpl/protocol/AccountID.h>
21#include <xrpl/protocol/Asset.h>
22#include <xrpl/protocol/Indexes.h>
23#include <xrpl/protocol/LedgerFormats.h>
24#include <xrpl/protocol/MPTIssue.h>
25#include <xrpl/protocol/PathAsset.h>
26#include <xrpl/protocol/SField.h>
27#include <xrpl/protocol/STAmount.h>
28#include <xrpl/protocol/STPathSet.h>
29#include <xrpl/protocol/TER.h>
30#include <xrpl/protocol/UintTypes.h>
31#include <xrpl/tx/paths/RippleCalc.h>
32
33#include <algorithm>
34#include <cstddef>
35#include <cstdint>
36#include <exception>
37#include <functional>
38#include <map>
39#include <memory>
40#include <optional>
41#include <ostream>
42#include <string>
43#include <vector>
44
45namespace xrpl {
48{
49 return os << static_cast<int>(t);
50}
53{
54 return os << static_cast<int>(t);
55}
56} // namespace xrpl
57
58/*
59
60Core Pathfinding Engine
61
62The pathfinding request is identified by category, XRP to XRP, XRP to
63non-XRP, non-XRP to XRP, same currency non-XRP to non-XRP, cross-currency
64non-XRP to non-XRP. For each category, there is a table of paths that the
65pathfinder searches for. Complete paths are collected.
66
67Each complete path is then rated and sorted. Paths with no or trivial
68liquidity are dropped. Otherwise, paths are sorted based on quality,
69liquidity, and path length.
70
71Path slots are filled in quality (ratio of out to in) order, with the
72exception that the last path must have enough liquidity to complete the
73payment (assuming no liquidity overlap). In addition, if no selected path
74is capable of providing enough liquidity to complete the payment by itself,
75an extra "covering" path is returned.
76
77The selected paths are then tested to determine if they can complete the
78payment and, if so, at what cost. If they fail and a covering path was
79found, the test is repeated with the covering path. If this succeeds, the
80final paths and the estimated cost are returned.
81
82The engine permits the search depth to be selected and the paths table
83includes the depth at which each path type is found. A search depth of zero
84causes no searching to be done. Extra paths can also be injected, and this
85should be used to preserve previously-found paths across invocations for the
86same path request (particularly if the search depth may change).
87
88*/
89
90namespace xrpl {
91
92namespace {
93
94// This is an arbitrary cutoff, and it might cause us to miss other
95// good paths with this arbitrary cut off.
96constexpr std::size_t kPathfinderMaxCompletePaths = 1000;
97
98struct AccountCandidate
99{
100 int priority;
101 AccountID account;
102
103 static int const kHighPriority = 10000;
104};
105
106bool
107compareAccountCandidate(
108 std::uint32_t seq,
109 AccountCandidate const& first,
110 AccountCandidate const& second)
111{
112 // Primary sort key: priority descending
113 if (first.priority != second.priority)
114 return first.priority > second.priority;
115
116 // Secondary sort key: account descending
117 if (first.account != second.account)
118 return first.account > second.account;
119
120 // Tertiary sort key (tie-breaker): (priority ^ seq) ascending
121 // Note: The primary and secondary keys are equal here.
122 return (first.priority ^ seq) < (second.priority ^ seq);
123}
124
125using AccountCandidates = std::vector<AccountCandidate>;
126
127struct CostedPath
128{
129 int searchLevel;
131};
132
133using CostedPathList = std::vector<CostedPath>;
134
135using PathTable = std::map<Pathfinder::PaymentType, CostedPathList>;
136
137struct PathCost
138{
139 int cost;
140 char const* path;
141};
142using PathCostList = std::vector<PathCost>;
143
144PathTable gPathTable;
145
146std::string
147pathTypeToString(Pathfinder::PathType const& type)
148{
149 std::string ret;
150
151 for (auto const& node : type)
152 {
153 switch (node)
154 {
156 ret.append("s");
157 break;
159 ret.append("a");
160 break;
162 ret.append("b");
163 break;
165 ret.append("x");
166 break;
168 ret.append("f");
169 break;
171 ret.append("d");
172 break;
173 }
174 }
175
176 return ret;
177}
178
179// Return the smallest amount of useful liquidity for a given amount, and the
180// total number of paths we have to evaluate.
182smallestUsefulAmount(STAmount const& amount, int maxPaths)
183{
184 return divide(amount, STAmount(maxPaths + 2), amount.asset());
185}
186
188amountFromPathAsset(
189 PathAsset const& pathAsset,
190 std::optional<AccountID> const& srcIssuer,
191 AccountID const& srcAccount)
192{
193 return pathAsset.visit(
194 [&](Currency const& currency) {
195 auto const& account = srcIssuer.value_or(isXRP(currency) ? xrpAccount() : srcAccount);
196 return STAmount(Issue{currency, account}, 1u, 0, true);
197 },
198 [](MPTID const& mpt) { return STAmount(mpt, 1u, 0, true); });
199}
200
201Asset
202assetFromPathAsset(PathAsset const& pathAsset, AccountID const& account)
203{
204 return pathAsset.visit(
205 [&](Currency const& currency) { return Asset{Issue{currency, account}}; },
206 [](MPTID const& mpt) { return Asset{mpt}; });
207}
208
209} // namespace
210
212 std::shared_ptr<AssetCache> const& cache,
213 AccountID const& uSrcAccount,
214 AccountID const& uDstAccount,
215 PathAsset const& uSrcPathAsset,
216 std::optional<AccountID> const& uSrcIssuer,
217 STAmount const& saDstAmount,
218 std::optional<STAmount> const& srcAmount,
219 std::optional<UInt256> const& domain,
220 Application& app)
221 : srcAccount_(uSrcAccount)
222 , dstAccount_(uDstAccount)
223 , effectiveDst_(isXRP(saDstAmount.getIssuer()) ? uDstAccount : saDstAmount.getIssuer())
224 , dstAmount_(saDstAmount)
225 , srcPathAsset_(uSrcPathAsset)
226 , srcIssuer_(uSrcIssuer)
227 , srcAmount_(srcAmount.value_or(amountFromPathAsset(uSrcPathAsset, uSrcIssuer, uSrcAccount)))
229 , domain_(domain)
230 , ledger_(cache->getLedger())
231 , rLCache_(cache)
232 , app_(app)
233 , j_(app.getJournal("Pathfinder"))
234{
235 XRPL_ASSERT(
236 !uSrcIssuer || uSrcPathAsset.isXRP() == isXRP(uSrcIssuer.value()),
237 "xrpl::Pathfinder::Pathfinder : valid inputs");
238}
239
240bool
241Pathfinder::findPaths(int searchLevel, std::function<bool()> const& continueCallback)
242{
243 JLOG(j_.trace()) << "findPaths start";
245 {
246 // No need to send zero money.
247 JLOG(j_.debug()) << "Destination amount was zero.";
248 ledger_.reset();
249 return false;
250
251 // TODO(tom): why do we reset the ledger just in this case and the one
252 // below - why don't we do it each time we return false?
253 }
254
256 srcPathAsset_ == dstAmount_.asset())
257 {
258 // No need to send to same account with same currency.
259 JLOG(j_.debug()) << "Tried to send to same issuer";
260 ledger_.reset();
261 return false;
262 }
263
265 {
266 // Default path might work, but any path would loop
267 return true;
268 }
269
270 loadEvent_ = app_.getJobQueue().makeLoadEvent(JtPathFind, "FindPath");
271 auto const currencyIsXRP = isXRP(srcPathAsset_);
272
273 bool const useIssuerAccount = srcIssuer_ && !currencyIsXRP && !isXRP(*srcIssuer_);
274 auto const& account = useIssuerAccount ? *srcIssuer_ : srcAccount_;
275 auto const issuer = currencyIsXRP ? AccountID() : account;
276 source_ = STPathElement(account, srcPathAsset_, issuer);
277 auto const issuerString = srcIssuer_ ? to_string(*srcIssuer_) : std::string("none");
278 JLOG(j_.trace()) << "findPaths>"
279 << " srcAccount_=" << srcAccount_ << " dstAccount_=" << dstAccount_
280 << " dstAmount_=" << dstAmount_.getFullText()
281 << " srcPathAsset_=" << srcPathAsset_ << " srcIssuer_=" << issuerString;
282
283 if (!ledger_)
284 {
285 JLOG(j_.debug()) << "findPaths< no ledger";
286 return false;
287 }
288
289 bool const bSrcXrp = isXRP(srcPathAsset_);
290 bool const bDstXrp = isXRP(dstAmount_.asset());
291
292 if (!ledger_->exists(keylet::account(srcAccount_)))
293 {
294 // We can't even start without a source account.
295 JLOG(j_.debug()) << "invalid source account";
296 return false;
297 }
298
300 {
301 JLOG(j_.debug()) << "Non-existent gateway";
302 return false;
303 }
304
305 if (!ledger_->exists(keylet::account(dstAccount_)))
306 {
307 // Can't find the destination account - we must be funding a new
308 // account.
309 if (!bDstXrp)
310 {
311 JLOG(j_.debug()) << "New account not being funded in XRP ";
312 return false;
313 }
314
315 auto const reserve = STAmount(ledger_->fees().reserve);
316 if (dstAmount_ < reserve)
317 {
318 JLOG(j_.debug()) << "New account not getting enough funding: " << dstAmount_ << " < "
319 << reserve;
320 return false;
321 }
322 }
323
324 // Now compute the payment type from the types of the source and destination
325 // currencies.
327 if (bSrcXrp && bDstXrp)
328 {
329 // XRP -> XRP
330 JLOG(j_.debug()) << "XRP to XRP payment";
331 paymentType = PaymentType::XrpToXrp;
332 }
333 else if (bSrcXrp)
334 {
335 // XRP -> non-XRP
336 JLOG(j_.debug()) << "XRP to non-XRP payment";
337 paymentType = PaymentType::XrpToNonXrp;
338 }
339 else if (bDstXrp)
340 {
341 // non-XRP -> XRP
342 JLOG(j_.debug()) << "non-XRP to XRP payment";
343 paymentType = PaymentType::NonXrpToXrp;
344 }
345 else if (srcPathAsset_ == dstAmount_.asset())
346 {
347 // non-XRP -> non-XRP - Same currency
348 JLOG(j_.debug()) << "non-XRP to non-XRP - same currency";
349 paymentType = PaymentType::NonXrpToSame;
350 }
351 else
352 {
353 // non-XRP to non-XRP - Different currency
354 JLOG(j_.debug()) << "non-XRP to non-XRP - cross currency";
355 paymentType = PaymentType::NonXrpToNonXrp;
356 }
357
358 // Now iterate over all paths for that paymentType.
359 for (auto const& costedPath : gPathTable[paymentType])
360 {
361 if (continueCallback && !continueCallback())
362 return false;
363 // Only use paths with at most the current search level.
364 if (costedPath.searchLevel <= searchLevel)
365 {
366 JLOG(j_.trace()) << "findPaths trying payment type " << paymentType;
367 addPathsForType(costedPath.type, continueCallback);
368
369 if (completePaths_.size() > kPathfinderMaxCompletePaths)
370 break;
371 }
372 }
373
374 JLOG(j_.debug()) << completePaths_.size() << " complete paths found";
375
376 // Even if we find no paths, default paths may work, and we don't check them
377 // currently.
378 return true;
379}
380
381TER
383 STPath const& path, // IN: The path to check.
384 STAmount const& minDstAmount, // IN: The minimum output this path must
385 // deliver to be worth keeping.
386 STAmount& amountOut, // OUT: The actual liquidity along the path.
387 uint64_t& qualityOut) const // OUT: The returned initial quality
388{
389 STPathSet pathSet;
390 pathSet.pushBack(path);
391
393 rcInput.defaultPathsAllowed = false;
394
395 PaymentSandbox sandbox(&*ledger_, TapNone);
396
397 try
398 {
399 // Compute a path that provides at least the minimum liquidity.
400 if (convertAll_)
401 rcInput.partialPaymentAllowed = true;
402
404 sandbox,
406 minDstAmount,
409 pathSet,
410 domain_,
411 app_,
412 &rcInput);
413 // If we can't get even the minimum liquidity requested, we're done.
414 if (!isTesSuccess(rc.result()))
415 return rc.result();
416
417 qualityOut = getRate(rc.actualAmountOut, rc.actualAmountIn);
418 amountOut = rc.actualAmountOut;
419
420 if (!convertAll_)
421 {
422 // Now try to compute the remaining liquidity.
423 rcInput.partialPaymentAllowed = true;
425 sandbox,
427 dstAmount_ - amountOut,
430 pathSet,
431 domain_,
432 app_,
433 &rcInput);
434
435 // If we found further liquidity, add it into the result.
436 if (rc.result() == tesSUCCESS)
437 amountOut += rc.actualAmountOut;
438 }
439
440 return tesSUCCESS;
441 }
442 catch (std::exception const& e)
443 {
444 JLOG(j_.info()) << "checkpath: exception (" << e.what() << ") "
446 return tefEXCEPTION;
447 }
448}
449
450void
451Pathfinder::computePathRanks(int maxPaths, std::function<bool()> const& continueCallback)
452{
454
455 // Must subtract liquidity in default path from remaining amount.
456 try
457 {
458 PaymentSandbox sandbox(&*ledger_, TapNone);
459
461 rcInput.partialPaymentAllowed = true;
462 auto const rc = path::RippleCalc::rippleCalculate(
463 sandbox,
468 STPathSet(),
469 domain_,
470 app_,
471 &rcInput);
472
473 if (rc.result() == tesSUCCESS)
474 {
475 JLOG(j_.debug()) << "Default path contributes: " << rc.actualAmountIn;
476 remainingAmount_ -= rc.actualAmountOut;
477 }
478 else
479 {
480 JLOG(j_.debug()) << "Default path fails: " << transToken(rc.result());
481 }
482 }
483 catch (std::exception const&)
484 {
485 JLOG(j_.debug()) << "Default path causes exception";
486 }
487
488 rankPaths(maxPaths, completePaths_, pathRanks_, continueCallback);
489}
490
491static bool
493{
494 // FIXME: default paths can consist of more than just an account:
495 //
496 // JoelKatz writes:
497 // So the test for whether a path is a default path is incorrect. I'm not
498 // sure it's worth the complexity of fixing though. If we are going to fix
499 // it, I'd suggest doing it this way:
500 //
501 // 1) Compute the default path, probably by using 'expandPath' to expand an
502 // empty path. 2) Chop off the source and destination nodes.
503 //
504 // 3) In the pathfinding loop, if the source issuer is not the sender,
505 // reject all paths that don't begin with the issuer's account node or match
506 // the path we built at step 2.
507 return path.size() == 1;
508}
509
510static STPath
512{
513 // This path starts with the issuer, which is already implied
514 // so remove the head node
515 STPath ret;
516
517 for (auto it = path.begin() + 1; it != path.end(); ++it)
518 ret.pushBack(*it);
519
520 return ret;
521}
522
523// For each useful path in the input path set,
524// create a ranking entry in the output vector of path ranks
525void
527 int maxPaths,
528 STPathSet const& paths,
529 std::vector<PathRank>& rankedPaths,
530 std::function<bool()> const& continueCallback)
531{
532 JLOG(j_.trace()) << "rankPaths with " << paths.size() << " candidates, and " << maxPaths
533 << " maximum";
534 rankedPaths.clear();
535 rankedPaths.reserve(paths.size());
536
537 auto const saMinDstAmount = [&] -> STAmount {
538 if (!convertAll_)
539 {
540 // Ignore paths that move only very small amounts.
541 return smallestUsefulAmount(dstAmount_, maxPaths);
542 }
543
544 // On convert_all_ partialPaymentAllowed will be set to true
545 // and requiring a huge amount will find the highest liquidity.
547 }();
548
549 for (int i = 0; i < paths.size(); ++i)
550 {
551 if (continueCallback && !continueCallback())
552 return;
553 auto const& currentPath = paths[i];
554 if (!currentPath.empty())
555 {
556 STAmount liquidity;
557 uint64_t uQuality = 0;
558 auto const resultCode =
559 getPathLiquidity(currentPath, saMinDstAmount, liquidity, uQuality);
560 if (!isTesSuccess(resultCode))
561 {
562 JLOG(j_.debug()) << "findPaths: dropping : " << transToken(resultCode) << ": "
563 << currentPath.getJson(JsonOptions::Values::None);
564 }
565 else
566 {
567 JLOG(j_.debug()) << "findPaths: quality: " << uQuality << ": "
568 << currentPath.getJson(JsonOptions::Values::None);
569
570 rankedPaths.push_back({
571 .quality = uQuality,
572 .length = currentPath.size(),
573 .liquidity = liquidity,
574 .index = i,
575 });
576 }
577 }
578 }
579
580 // Sort paths by:
581 // cost of path (when considering quality)
582 // width of path
583 // length of path
584 // A better PathRank is lower, best are sorted to the beginning.
586 rankedPaths, [&](Pathfinder::PathRank const& a, Pathfinder::PathRank const& b) {
587 // 1) Higher quality (lower cost) is better
588 if (!convertAll_ && a.quality != b.quality)
589 return a.quality < b.quality;
590
591 // 2) More liquidity (higher volume) is better
592 if (a.liquidity != b.liquidity)
593 return a.liquidity > b.liquidity;
594
595 // 3) Shorter paths are better
596 if (a.length != b.length)
597 return a.length < b.length;
598
599 // 4) Tie breaker
600 return a.index > b.index;
601 });
602}
603
606 int maxPaths,
607 STPath& fullLiquidityPath,
608 STPathSet const& extraPaths,
609 AccountID const& srcIssuer,
610 std::function<bool()> const& continueCallback)
611{
612 JLOG(j_.debug()) << "findPaths: " << completePaths_.size() << " paths and " << extraPaths.size()
613 << " extras";
614
615 if (completePaths_.empty() && extraPaths.empty())
616 return completePaths_;
617
618 XRPL_ASSERT(
619 fullLiquidityPath.empty(), "xrpl::Pathfinder::getBestPaths : first empty path result");
620 bool const issuerIsSender = isXRP(srcPathAsset_) || (srcIssuer == srcAccount_);
621
622 std::vector<PathRank> extraPathRanks;
623 rankPaths(maxPaths, extraPaths, extraPathRanks, continueCallback);
624
625 STPathSet bestPaths;
626
627 // The best PathRanks are now at the start. Pull off enough of them to
628 // fill bestPaths, then look through the rest for the best individual
629 // path that can satisfy the entire liquidity - if one exists.
630 STAmount remaining = remainingAmount_;
631
632 auto pathsIterator = pathRanks_.begin();
633 auto extraPathsIterator = extraPathRanks.begin();
634
635 while (pathsIterator != pathRanks_.end() || extraPathsIterator != extraPathRanks.end())
636 {
637 if (continueCallback && !continueCallback())
638 break;
639 bool usePath = false;
640 bool useExtraPath = false;
641
642 if (pathsIterator == pathRanks_.end())
643 {
644 useExtraPath = true;
645 }
646 else if (extraPathsIterator == extraPathRanks.end())
647 {
648 usePath = true;
649 }
650 else if (extraPathsIterator->quality != pathsIterator->quality)
651 {
652 // Prefer the lower (better) quality value
653 useExtraPath = extraPathsIterator->quality < pathsIterator->quality;
654 usePath = !useExtraPath;
655 }
656 else if (extraPathsIterator->liquidity != pathsIterator->liquidity)
657 {
658 // Equal quality: prefer the higher liquidity
659 useExtraPath = extraPathsIterator->liquidity > pathsIterator->liquidity;
660 usePath = !useExtraPath;
661 }
662 else
663 {
664 // Risk is high they have identical liquidity
665 useExtraPath = true;
666 usePath = true;
667 }
668
669 auto const& pathRank = usePath ? *pathsIterator : *extraPathsIterator;
670
671 auto const& path = usePath ? completePaths_[pathRank.index] : extraPaths[pathRank.index];
672
673 if (useExtraPath)
674 ++extraPathsIterator;
675
676 if (usePath)
677 ++pathsIterator;
678
679 auto iPathsLeft = maxPaths - bestPaths.size();
680 if (iPathsLeft <= 0 && !fullLiquidityPath.empty())
681 break;
682
683 if (path.empty())
684 {
685 // LCOV_EXCL_START
686 UNREACHABLE("xrpl::Pathfinder::getBestPaths : path not found");
687 continue;
688 // LCOV_EXCL_STOP
689 }
690
691 bool startsWithIssuer = false;
692
693 if (!issuerIsSender && usePath)
694 {
695 // Need to make sure path matches issuer constraints
696 if (isDefaultPath(path) || path.front().getAccountID() != srcIssuer)
697 {
698 continue;
699 }
700
701 startsWithIssuer = true;
702 }
703
704 if (iPathsLeft > 1 || (iPathsLeft > 0 && pathRank.liquidity >= remaining))
705 // last path must fill
706 {
707 --iPathsLeft;
708 remaining -= pathRank.liquidity;
709 bestPaths.pushBack(startsWithIssuer ? removeIssuer(path) : path);
710 }
711 else if (iPathsLeft == 0 && pathRank.liquidity >= dstAmount_ && fullLiquidityPath.empty())
712 {
713 // We found an extra path that can move the whole amount.
714 fullLiquidityPath = (startsWithIssuer ? removeIssuer(path) : path);
715 JLOG(j_.debug()) << "Found extra full path: "
716 << fullLiquidityPath.getJson(JsonOptions::Values::None);
717 }
718 else
719 {
720 JLOG(j_.debug()) << "Skipping a non-filling path: "
722 }
723 }
724
725 if (remaining > beast::kZero)
726 {
727 XRPL_ASSERT(
728 fullLiquidityPath.empty(), "xrpl::Pathfinder::getBestPaths : second empty path result");
729 JLOG(j_.info()) << "Paths could not send " << remaining << " of " << dstAmount_;
730 }
731 else
732 {
733 JLOG(j_.debug()) << "findPaths: RESULTS: " << bestPaths.getJson(JsonOptions::Values::None);
734 }
735 return bestPaths;
736}
737
738bool
740{
741 bool const matchingAsset = (asset == srcPathAsset_);
742 bool const matchingAccount = isXRP(asset) || (srcIssuer_ && asset.getIssuer() == srcIssuer_) ||
743 asset.getIssuer() == srcAccount_;
744
745 return matchingAsset && matchingAccount;
746}
747
748int
750 PathAsset const& pathAsset,
751 AccountID const& account,
752 LineDirection direction,
753 bool isDstAsset,
754 AccountID const& dstAccount,
755 std::function<bool()> const& continueCallback)
756{
757 Asset const asset = assetFromPathAsset(pathAsset, account);
758
759 auto [it, inserted] = pathsOutCountMap_.emplace(asset, 0);
760
761 // If it was already present, return the stored number of paths
762 if (!inserted)
763 return it->second;
764
765 auto const sleAccount = ledger_->read(keylet::account(account));
766
767 if (!sleAccount)
768 return 0;
769
770 auto const aFlags = sleAccount->getFieldU32(sfFlags);
771 bool const bAuthRequired = [&] {
772 if (pathAsset.holds<Currency>())
773 return (aFlags & lsfRequireAuth) != 0;
774 return !isTesSuccess(requireAuth(*ledger_, asset.get<MPTIssue>(), account));
775 }();
776 bool const bFrozen = [&] {
777 if (pathAsset.holds<Currency>())
778 return (aFlags & lsfGlobalFreeze) != 0;
779 return isGlobalFrozen(*ledger_, asset.get<MPTIssue>());
780 }();
781
782 int count = 0;
783
784 if (!bFrozen)
785 {
786 count = app_.getOrderBookDB().getBookSize(asset, domain_);
787
788 asset.visit(
789 [&](Issue const&) {
790 if (auto const lines = rLCache_->getRippleLines(account, direction))
791 {
792 for (auto const& rspEntry : *lines)
793 {
794 if (pathAsset.get<Currency>() != rspEntry.getLimit().get<Issue>().currency)
795 continue;
796 if (rspEntry.getBalance() <= beast::kZero &&
797 (!rspEntry.getLimitPeer() ||
798 -rspEntry.getBalance() >= rspEntry.getLimitPeer() ||
799 (bAuthRequired && !rspEntry.getAuth())))
800 continue;
801 if (isDstAsset && dstAccount == rspEntry.getAccountIDPeer())
802 {
803 count += 10000; // count a path to the destination extra
804 continue;
805 }
806 if (rspEntry.getNoRipplePeer())
807 continue; // This probably isn't a useful path out
808 if (rspEntry.getFreezePeer())
809 continue; // Not a useful path out
810 ++count;
811 }
812 }
813 },
814 [&](MPTIssue const&) {
815 if (auto const mpts = rLCache_->getMPTs(account))
816 {
817 for (auto const& mpt : *mpts)
818 {
819 if (pathAsset.get<MPTID>() != mpt.getMptID() || !mpt.canSend(account) ||
820 bAuthRequired)
821 continue;
822 if (isDstAsset && dstAccount == getMPTIssuer(mpt))
823 {
824 count += 10000;
825 continue;
826 }
827 if (isIndividualFrozen(*ledger_, account, MPTIssue{mpt.getMptID()}))
828 continue;
829 ++count;
830 }
831 }
832 });
833 }
834 it->second = count;
835 return count;
836}
837
838void
840 STPathSet const& currentPaths, // The paths to build from
841 STPathSet& incompletePaths, // The set of partial paths we add to
842 int addFlags,
843 std::function<bool()> const& continueCallback)
844{
845 JLOG(j_.debug()) << "addLink< on " << currentPaths.size() << " source(s), flags=" << addFlags;
846 for (auto const& path : currentPaths)
847 {
848 if (continueCallback && !continueCallback())
849 return;
850 addLink(path, incompletePaths, addFlags, continueCallback);
851 }
852}
853
855Pathfinder::addPathsForType(PathType const& pathType, std::function<bool()> const& continueCallback)
856{
857 JLOG(j_.debug()) << "addPathsForType " << CollectionAndDelimiter(pathType, ", ");
858 // See if the set of paths for this type already exists.
859 auto const it = paths_.find(pathType);
860 if (it != paths_.end())
861 return it->second;
862
863 // Otherwise, if the type has no nodes, return the empty path.
864 if (pathType.empty() || (continueCallback && !continueCallback()))
865 {
866 static auto const kEmptyPath = PathType{};
867 return paths_.try_emplace(kEmptyPath, STPathSet::DeduplicationTag{}).first->second;
868 }
869
870 // Otherwise, get the paths for the parent PathType by calling
871 // addPathsForType recursively.
872 PathType parentPathType = pathType;
873 parentPathType.pop_back();
874
875 STPathSet const& parentPaths = addPathsForType(parentPathType, continueCallback);
876 STPathSet& pathsOut = paths_.try_emplace(pathType, STPathSet::DeduplicationTag{}).first->second;
877
878 JLOG(j_.debug()) << "getPaths< adding onto '" << pathTypeToString(parentPathType)
879 << "' to get '" << pathTypeToString(pathType) << "'";
880
881 int const initialSize = completePaths_.size();
882
883 // Add the last NodeType to the lists.
884 auto const nodeType = pathType.back();
885 switch (nodeType)
886 {
887 case NodeType::Source:
888 // Source must always be at the start, so pathsOut has to be empty.
889 XRPL_ASSERT(pathsOut.empty(), "xrpl::Pathfinder::addPathsForType : empty paths");
890 pathsOut.pushBack(STPath());
891 break;
892
894 addLinks(parentPaths, pathsOut, kAfAddAccounts, continueCallback);
895 break;
896
897 case NodeType::Books:
898 addLinks(parentPaths, pathsOut, kAfAddBooks, continueCallback);
899 break;
900
902 addLinks(parentPaths, pathsOut, kAfAddBooks | kAfObXrp, continueCallback);
903 break;
904
906 addLinks(parentPaths, pathsOut, kAfAddBooks | kAfObLast, continueCallback);
907 break;
908
910 // FIXME: What if a different issuer was specified on the
911 // destination amount?
912 // TODO(tom): what does this even mean? Should it be a JIRA?
913 addLinks(parentPaths, pathsOut, kAfAddAccounts | kAfAcLast, continueCallback);
914 break;
915 }
916
917 if (completePaths_.size() != initialSize)
918 {
919 JLOG(j_.debug()) << (completePaths_.size() - initialSize) << " complete paths added";
920 }
921
922 JLOG(j_.debug()) << "getPaths> " << pathsOut.size() << " partial paths found";
923 return pathsOut;
924}
925
926bool
928 AccountID const& fromAccount,
929 AccountID const& toAccount,
930 Currency const& currency)
931{
932 auto const sleRipple = ledger_->read(keylet::trustLine(toAccount, fromAccount, currency));
933
934 auto const flag((toAccount > fromAccount) ? lsfHighNoRipple : lsfLowNoRipple);
935
936 return sleRipple && sleRipple->isFlag(flag);
937}
938
939// Does this path end on an account-to-account link whose last account has
940// set "no ripple" on the link?
941bool
943{
944 // Must have at least one link.
945 if (currentPath.empty())
946 return false;
947
948 // Last link must be an account.
949 STPathElement const& endElement = currentPath.back();
950 if ((endElement.getNodeType() & STPathElement::TypeAccount) == 0u)
951 return false;
952
953 // If there's only one item in the path, return true if that item specifies
954 // no ripple on the output. A path with no ripple on its output can't be
955 // followed by a link with no ripple on its input.
956 auto const& fromAccount =
957 (currentPath.size() == 1) ? srcAccount_ : (currentPath.end() - 2)->getAccountID();
958 auto const& toAccount = endElement.getAccountID();
959 return endElement.hasCurrency() && isNoRipple(fromAccount, toAccount, endElement.getCurrency());
960}
961
962void
964 STPath const& currentPath, // The path to build from
965 STPathSet& incompletePaths, // The set of partial paths we add to
966 int addFlags,
967 std::function<bool()> const& continueCallback)
968{
969 auto const& pathEnd = currentPath.empty() ? source_ : currentPath.back();
970 auto const& uEndPathAsset = pathEnd.getPathAsset();
971 auto const& uEndIssuer = pathEnd.getIssuerID();
972 auto const& uEndAccount = pathEnd.getAccountID();
973 bool const bOnXRP = isXRP(uEndPathAsset);
974
975 // Does pathfinding really need to get this to
976 // a gateway (the issuer of the destination amount)
977 // rather than the ultimate destination?
978 bool const hasEffectiveDestination = effectiveDst_ != dstAccount_;
979
980 JLOG(j_.trace()) << "addLink< flags=" << addFlags << " onXRP=" << bOnXRP
981 << " completePaths size=" << completePaths_.size();
982 JLOG(j_.trace()) << currentPath.getJson(JsonOptions::Values::None);
983
984 if ((addFlags & kAfAddAccounts) != 0u)
985 {
986 // add accounts
987 if (bOnXRP)
988 {
989 if (dstAmount_.native() && !currentPath.empty())
990 { // non-default path to XRP destination
991 JLOG(j_.trace()) << "complete path found ax: "
992 << currentPath.getJson(JsonOptions::Values::None);
993 completePaths_.pushBack(currentPath);
994 }
995 }
996 else
997 {
998 // search for accounts to add
999 auto const sleEnd = ledger_->read(keylet::account(uEndAccount));
1000
1001 if (sleEnd)
1002 {
1003 bool const bRequireAuth(sleEnd->isFlag(lsfRequireAuth));
1004 bool const bIsEndAsset(uEndPathAsset == dstAmount_.asset());
1005 bool const bIsNoRippleOut(isNoRippleOut(currentPath));
1006 bool const bDestOnly((addFlags & kAfAcLast) != 0u);
1007
1008 AccountCandidates candidates;
1009
1010 auto forAssets = [&]<typename AssetType>(AssetType const& assets) {
1011 candidates.reserve(assets.size());
1012
1013 static constexpr bool kIsLine =
1015 static constexpr bool kIsMpt =
1017
1018 for (auto const& asset : assets)
1019 {
1020 if (continueCallback && !continueCallback())
1021 return;
1022 auto const& acct = [&] constexpr {
1023 if constexpr (kIsLine)
1024 return asset.getAccountIDPeer();
1025 // Unlike trustline, MPT is not bidirectional
1026 if constexpr (kIsMpt)
1027 return getMPTIssuer(asset);
1028 }();
1029 auto const direction = [&] constexpr -> LineDirection {
1030 if constexpr (kIsLine)
1031 return asset.getDirectionPeer();
1032 // incoming for MPT since MPT doesn't support
1033 // rippling (see LineDirection comments)
1035 }();
1036
1037 if (hasEffectiveDestination && (acct == dstAccount_))
1038 {
1039 // We skipped the gateway
1040 continue;
1041 }
1042
1043 bool const bToDestination = acct == effectiveDst_;
1044
1045 if (bDestOnly && !bToDestination)
1046 {
1047 continue;
1048 }
1049
1050 auto const correctAsset = [&] {
1051 if constexpr (kIsLine)
1052 {
1053 return uEndPathAsset.get<Currency>() ==
1054 asset.getLimit().template get<Issue>().currency;
1055 }
1056 if constexpr (kIsMpt)
1057 {
1058 return uEndPathAsset.get<MPTID>() == asset.getMptID();
1059 }
1060 }();
1061 auto const checkAsset = [&] {
1062 if constexpr (kIsLine)
1063 {
1064 return (
1065 (asset.getBalance() <= beast::kZero &&
1066 (!asset.getLimitPeer() ||
1067 -asset.getBalance() >= asset.getLimitPeer() ||
1068 (bRequireAuth && !asset.getAuth()))) ||
1069 (bIsNoRippleOut && asset.getNoRipple()));
1070 }
1071 if constexpr (kIsMpt)
1072 {
1073 // `asset` came from uEndAccount's cached MPTs.
1074 // `acct` is the next issuer hop, not the
1075 // account whose balance is being tested.
1076 return !asset.canSend(uEndAccount) ||
1077 requireAuth(*ledger_, MPTIssue{asset}, acct);
1078 }
1079 };
1080
1081 if (correctAsset && !currentPath.hasSeen(acct, uEndPathAsset, acct))
1082 {
1083 // path is for correct currency and has not been
1084 // seen
1085 if (checkAsset())
1086 {
1087 // Can't leave on this path
1088 continue;
1089 }
1090 if (bToDestination)
1091 {
1092 // destination is always worth trying
1093 if (uEndPathAsset == dstAmount_.asset())
1094 {
1095 // this is a complete path
1096 if (!currentPath.empty())
1097 {
1098 JLOG(j_.trace())
1099 << "complete path found ae: "
1100 << currentPath.getJson(JsonOptions::Values::None);
1101 completePaths_.pushBack(currentPath);
1102 }
1103 }
1104 else if (!bDestOnly)
1105 {
1106 // this is a high-priority candidate
1107 candidates.push_back({AccountCandidate::kHighPriority, acct});
1108 }
1109 }
1110 else if (acct == srcAccount_)
1111 {
1112 // going back to the source is bad
1113 }
1114 else
1115 {
1116 // save this candidate
1117 int const out = getPathsOut(
1118 uEndPathAsset,
1119 acct,
1120 direction,
1121 bIsEndAsset,
1123 continueCallback);
1124 if (out != 0)
1125 candidates.push_back({out, acct});
1126 }
1127 }
1128 }
1129 };
1130
1131 uEndPathAsset.visit(
1132 [&](Currency const&) {
1133 if (auto const lines = rLCache_->getRippleLines(
1134 uEndAccount,
1136 {
1137 forAssets(*lines);
1138 }
1139 },
1140 [&](MPTID const&) {
1141 if (auto const mpts = rLCache_->getMPTs(uEndAccount))
1142 {
1143 forAssets(*mpts);
1144 }
1145 });
1146
1147 if (!candidates.empty())
1148 {
1150 candidates,
1151 [seq = ledger_->seq()](
1152 AccountCandidate const& first, AccountCandidate const& second) {
1153 return compareAccountCandidate(seq, first, second);
1154 });
1155
1156 int count = candidates.size();
1157 // allow more paths from source
1158 if ((count > 10) && (uEndAccount != srcAccount_))
1159 {
1160 count = 10;
1161 }
1162 else if (count > 50)
1163 {
1164 count = 50;
1165 }
1166
1167 auto it = candidates.begin();
1168 while (count-- != 0)
1169 {
1170 if (continueCallback && !continueCallback())
1171 return;
1172 // Add accounts to incompletePaths
1173 STPathElement const pathElement(
1174 STPathElement::TypeAccount, it->account, uEndPathAsset, it->account);
1175 incompletePaths.assembleAdd(currentPath, pathElement);
1176 ++it;
1177 }
1178 }
1179 }
1180 else
1181 {
1182 JLOG(j_.warn()) << "Path ends on non-existent issuer";
1183 }
1184 }
1185 }
1186 if ((addFlags & kAfAddBooks) != 0u)
1187 {
1188 // add order books
1189 if ((addFlags & kAfObXrp) != 0u)
1190 {
1191 // to XRP only
1192 if (!bOnXRP &&
1193 app_.getOrderBookDB().isBookToXRP(
1194 assetFromPathAsset(uEndPathAsset, uEndIssuer), domain_))
1195 {
1196 STPathElement const pathElement(
1198 incompletePaths.assembleAdd(currentPath, pathElement);
1199 }
1200 }
1201 else
1202 {
1203 bool const bDestOnly = (addFlags & kAfObLast) != 0;
1204 auto const books = app_.getOrderBookDB().getBooksByTakerPays(
1205 assetFromPathAsset(uEndPathAsset, uEndIssuer), domain_);
1206 JLOG(j_.trace()) << books.size() << " books found from this currency/issuer";
1207
1208 for (auto const& book : books)
1209 {
1210 if (continueCallback && !continueCallback())
1211 return;
1212 if (!currentPath.hasSeen(xrpAccount(), book.out, book.out.getIssuer()) &&
1213 !issueMatchesOrigin(book.out) &&
1214 (!bDestOnly || equalTokens(book.out, dstAmount_.asset())))
1215 {
1216 STPath newPath(currentPath);
1217
1218 if (isXRP(book.out))
1219 { // to XRP
1220
1221 // add the order book itself
1222 newPath.emplaceBack(
1224
1225 if (isXRP(dstAmount_.asset()))
1226 {
1227 // destination is XRP, add account and path is
1228 // complete
1229 JLOG(j_.trace()) << "complete path found bx: "
1230 << currentPath.getJson(JsonOptions::Values::None);
1231 completePaths_.pushBack(newPath);
1232 }
1233 else
1234 {
1235 [[maybe_unused]] auto const result = incompletePaths.pushBack(newPath);
1236 XRPL_ASSERT(result, "xrpl::Pathfinder::addLink : unique path");
1237 }
1238 }
1239 else if (!currentPath.hasSeen(
1240 book.out.getIssuer(), book.out, book.out.getIssuer()))
1241 {
1242 auto const assetType = book.out.holds<Issue>() ? STPathElement::TypeCurrency
1244 // Don't want the book if we've already seen the issuer
1245 // book -> account -> book
1246 if ((newPath.size() >= 2) && newPath.back().isAccount() &&
1247 newPath[newPath.size() - 2].isOffer())
1248 {
1249 // replace the redundant account with the order book
1250 newPath[newPath.size() - 1] = STPathElement(
1251 assetType | STPathElement::TypeIssuer,
1252 xrpAccount(),
1253 book.out,
1254 book.out.getIssuer());
1255 }
1256 else
1257 {
1258 // add the order book
1259 newPath.emplaceBack(
1260 assetType | STPathElement::TypeIssuer,
1261 xrpAccount(),
1262 book.out,
1263 book.out.getIssuer());
1264 }
1265
1266 if (hasEffectiveDestination && book.out.getIssuer() == dstAccount_ &&
1267 equalTokens(book.out, dstAmount_.asset()))
1268 {
1269 // We skipped a required issuer
1270 }
1271 else if (
1272 book.out.getIssuer() == effectiveDst_ &&
1273 equalTokens(book.out, dstAmount_.asset()))
1274 { // with the destination account, this path is
1275 // complete
1276 JLOG(j_.trace()) << "complete path found ba: "
1277 << currentPath.getJson(JsonOptions::Values::None);
1278 completePaths_.pushBack(newPath);
1279 }
1280 else
1281 {
1282 // add issuer's account, path still incomplete
1283 incompletePaths.assembleAdd(
1284 newPath,
1287 book.out.getIssuer(),
1288 book.out,
1289 book.out.getIssuer()));
1290 }
1291 }
1292 }
1293 }
1294 }
1295 }
1296}
1297
1298namespace {
1299
1301makePath(char const* string)
1302{
1304
1305 while (true)
1306 {
1307 // NOLINTNEXTLINE(bugprone-switch-missing-default-case)
1308 switch (*string++)
1309 {
1310 case 's': // source
1312 break;
1313
1314 case 'a': // accounts
1316 break;
1317
1318 case 'b': // books
1320 break;
1321
1322 case 'x': // xrp book
1324 break;
1325
1326 case 'f': // book to final currency
1328 break;
1329
1330 case 'd':
1331 // Destination (with account, if required and not already
1332 // present).
1334 break;
1335
1336 case 0:
1337 return ret;
1338 }
1339 }
1340}
1341
1342void
1343fillPaths(Pathfinder::PaymentType type, PathCostList const& costs)
1344{
1345 auto& list = gPathTable[type];
1346 XRPL_ASSERT(list.empty(), "xrpl::fillPaths : empty paths");
1347 for (auto& cost : costs)
1348 list.push_back({.searchLevel = cost.cost, .type = makePath(cost.path)});
1349}
1350
1351} // namespace
1352
1353// Costs:
1354// 0 = minimum to make some payments possible
1355// 1 = include trivial paths to make common cases work
1356// 4 = normal fast search level
1357// 7 = normal slow search level
1358// 10 = most aggressive
1359
1360void
1362{
1363 // CAUTION: Do not include rules that build default paths
1364
1365 gPathTable.clear();
1366 fillPaths(PaymentType::XrpToXrp, {});
1367 /* cspell: disable */
1368
1369 fillPaths(
1371 {
1372 {.cost = 1, .path = "sfd"}, // source -> book -> gateway
1373 {.cost = 3, .path = "sfad"}, // source -> book -> account -> destination
1374 {.cost = 5, .path = "sfaad"}, // source -> book -> account -> account -> destination
1375 {.cost = 6, .path = "sbfd"}, // source -> book -> book -> destination
1376 {.cost = 8, .path = "sbafd"}, // source -> book -> account -> book -> destination
1377 {.cost = 9, .path = "sbfad"}, // source -> book -> book -> account -> destination
1378 {.cost = 10, .path = "sbafad"},
1379 });
1380
1381 fillPaths(
1383 {
1384 {.cost = 1, .path = "sxd"}, // gateway buys XRP
1385 {.cost = 2, .path = "saxd"}, // source -> gateway -> book(XRP) -> dest
1386 {.cost = 6, .path = "saaxd"},
1387 {.cost = 7, .path = "sbxd"},
1388 {.cost = 8, .path = "sabxd"},
1389 {.cost = 9, .path = "sabaxd"},
1390 });
1391
1392 // non-XRP to non-XRP (same currency)
1393 fillPaths(
1395 {
1396 {.cost = 1, .path = "sad"}, // source -> gateway -> destination
1397 {.cost = 1, .path = "sfd"}, // source -> book -> destination
1398 {.cost = 4, .path = "safd"}, // source -> gateway -> book -> destination
1399 {.cost = 4, .path = "sfad"},
1400 {.cost = 5, .path = "saad"},
1401 {.cost = 5, .path = "sbfd"},
1402 {.cost = 6, .path = "sxfad"},
1403 {.cost = 6, .path = "safad"},
1404 {.cost = 6, .path = "saxfd"}, // source -> gateway -> book to XRP -> book ->
1405 // destination
1406 {.cost = 6, .path = "saxfad"},
1407 {.cost = 6, .path = "sabfd"}, // source -> gateway -> book -> book -> destination
1408 {.cost = 7, .path = "saaad"},
1409 });
1410
1411 // non-XRP to non-XRP (different currency)
1412 fillPaths(
1414 {
1415 {.cost = 1, .path = "sfad"},
1416 {.cost = 1, .path = "safd"},
1417 {.cost = 3, .path = "safad"},
1418 {.cost = 4, .path = "sxfd"},
1419 {.cost = 5, .path = "saxfd"},
1420 {.cost = 5, .path = "sxfad"},
1421 {.cost = 5, .path = "sbfd"},
1422 {.cost = 6, .path = "saxfad"},
1423 {.cost = 6, .path = "sabfd"},
1424 {.cost = 7, .path = "saafd"},
1425 {.cost = 8, .path = "saafad"},
1426 {.cost = 9, .path = "safaad"},
1427 });
1428 /* cspell: enable */
1429}
1430
1431} // namespace xrpl
T append(T... args)
T back(T... args)
T begin(T... args)
constexpr auto visit(Visitors &&... visitors) const -> decltype(auto)
Definition Asset.h:117
constexpr TIss const & get() const
AccountID const & getIssuer() const
Definition Asset.cpp:21
A currency issued by an account.
Definition Issue.h:18
Currency currency
Definition Issue.h:20
constexpr bool isXRP() const
Definition PathAsset.h:99
constexpr bool holds() const
Definition PathAsset.h:78
T const & get() const
STAmount dstAmount_
Definition Pathfinder.h:193
static std::uint32_t const kAfObLast
Definition Pathfinder.h:229
TER getPathLiquidity(STPath const &path, STAmount const &minDstAmount, STAmount &amountOut, uint64_t &qualityOut) const
int getPathsOut(PathAsset const &pathAsset, AccountID const &account, LineDirection direction, bool isDestPathAsset, AccountID const &dest, std::function< bool()> const &continueCallback)
bool issueMatchesOrigin(Asset const &)
STAmount srcAmount_
Definition Pathfinder.h:196
static std::uint32_t const kAfAddAccounts
Definition Pathfinder.h:220
AccountID dstAccount_
Definition Pathfinder.h:191
PathAsset srcPathAsset_
Definition Pathfinder.h:194
void computePathRanks(int maxPaths, std::function< bool()> const &continueCallback={})
Compute the rankings of the paths.
std::vector< NodeType > PathType
Definition Pathfinder.h:92
std::unique_ptr< LoadEvent > loadEvent_
Definition Pathfinder.h:206
STPathSet & addPathsForType(PathType const &type, std::function< bool()> const &continueCallback)
HashMap< Asset, int > pathsOutCountMap_
Definition Pathfinder.h:214
bool findPaths(int searchLevel, std::function< bool()> const &continueCallback={})
AccountID srcAccount_
Definition Pathfinder.h:190
static std::uint32_t const kAfObXrp
Definition Pathfinder.h:226
std::optional< AccountID > srcIssuer_
Definition Pathfinder.h:195
std::map< PathType, STPathSet > paths_
Definition Pathfinder.h:212
static std::uint32_t const kAfAcLast
Definition Pathfinder.h:232
std::shared_ptr< AssetCache > rLCache_
Definition Pathfinder.h:207
STPathSet completePaths_
Definition Pathfinder.h:210
Pathfinder(std::shared_ptr< AssetCache > const &cache, AccountID const &srcAccount, AccountID const &dstAccount, PathAsset const &uSrcPathAsset, std::optional< AccountID > const &uSrcIssuer, STAmount const &dstAmount, std::optional< STAmount > const &srcAmount, std::optional< UInt256 > const &domain, Application &app)
Construct a pathfinder without an issuer.
STPathElement source_
Definition Pathfinder.h:209
void addLinks(STPathSet const &currentPaths, STPathSet &incompletePaths, int addFlags, std::function< bool()> const &continueCallback)
void addLink(STPath const &currentPath, STPathSet &incompletePaths, int addFlags, std::function< bool()> const &continueCallback)
bool isNoRipple(AccountID const &fromAccount, AccountID const &toAccount, Currency const &currency)
STPathSet getBestPaths(int maxPaths, STPath &fullLiquidityPath, STPathSet const &extraPaths, AccountID const &srcIssuer, std::function< bool()> const &continueCallback={})
Application & app_
Definition Pathfinder.h:216
void rankPaths(int maxPaths, STPathSet const &paths, std::vector< PathRank > &rankedPaths, std::function< bool()> const &continueCallback)
bool isNoRippleOut(STPath const &currentPath)
beast::Journal const j_
Definition Pathfinder.h:217
std::optional< UInt256 > domain_
Definition Pathfinder.h:203
static void initPathTable()
STAmount remainingAmount_
The amount remaining from srcAccount_ after the default liquidity has been removed.
Definition Pathfinder.h:201
static std::uint32_t const kAfAddBooks
Definition Pathfinder.h:223
AccountID effectiveDst_
Definition Pathfinder.h:192
std::vector< PathRank > pathRanks_
Definition Pathfinder.h:211
std::shared_ptr< ReadView const > ledger_
Definition Pathfinder.h:205
A wrapper which makes credits unavailable to balances.
Asset const & asset() const
Definition STAmount.h:496
std::uint32_t getNodeType() const
Definition STPathSet.h:427
AccountID const & getAccountID() const
Definition STPathSet.h:483
Currency const & getCurrency() const
Definition STPathSet.h:495
bool hasCurrency() const
Definition STPathSet.h:457
bool assembleAdd(STPath const &base, STPathElement const &tail)
assembleAdd adds a path to the set by combining a base path and a tail element.
std::vector< STPath >::size_type size() const
Definition STPathSet.h:624
json::Value getJson(JsonOptions) const override
bool pushBack(STPath const &e)
pushBack adds a path to the set.
Definition STPathSet.h:669
bool empty() const
Definition STPathSet.h:630
std::vector< STPathElement >::size_type size() const
Definition STPathSet.h:526
bool hasSeen(AccountID const &account, PathAsset const &asset, AccountID const &issuer) const
bool empty() const
Definition STPathSet.h:532
void pushBack(STPathElement const &e)
Definition STPathSet.h:538
std::vector< STPathElement >::const_iterator end() const
Definition STPathSet.h:557
void emplaceBack(Args &&... args)
Definition STPathSet.h:545
std::vector< STPathElement >::const_reference back() const
Definition STPathSet.h:569
json::Value getJson(JsonOptions) const
static Output rippleCalculate(PaymentSandbox &view, STAmount const &saMaxAmountReq, STAmount const &saDstAmountReq, AccountID const &uDstAccountID, AccountID const &uSrcAccountID, STPathSet const &spsPaths, std::optional< UInt256 > const &domainID, ServiceRegistry &registry, Input const *const pInputs=nullptr)
T clear(T... args)
T empty(T... args)
T end(T... args)
T is_same_v
constexpr Zero kZero
Definition Zero.h:30
Keylet account(AccountID const &id) noexcept
AccountID root.
Definition Indexes.cpp:233
Keylet trustLine(AccountID const &id0, AccountID const &id1, Currency const &currency) noexcept
The index of a trust line for a given currency.
Definition Indexes.cpp:287
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
STAmount divide(STAmount const &amount, Rate const &rate)
Definition Rate2.cpp:69
STAmount convertAmount(STAmount const &amt, bool all)
bool isXRP(AccountID const &c)
Definition AccountID.h:84
bool isIndividualFrozen(ReadView const &view, AccountID const &account, MPTIssue const &mptIssue)
Returns true if account's MPToken for mptIssue carries the individual-lock flag (lsfMPTLocked).
T get(Section const &section, std::string const &name, T const &defaultValue=T{})
Retrieve a key/value pair from a section.
STAmount largestAmount(STAmount const &amt)
@ tefEXCEPTION
Definition TER.h:166
BaseUInt< 160, detail::CurrencyTag > Currency
Currency is a hash representing a specific currency.
Definition UintTypes.h:42
std::ostream & operator<<(std::ostream &out, BaseUInt< Bits, Tag > const &u)
Definition base_uint.h:673
static STPath removeIssuer(STPath const &path)
AccountID getMPTIssuer(MPTID const &mptid)
Definition MPTIssue.h:95
std::string transToken(TER code)
Definition TER.cpp:259
Currency const & xrpCurrency()
XRP currency.
Definition UintTypes.cpp:99
std::string to_string(BaseUInt< Bits, Tag > const &a)
Definition base_uint.h:658
bool isGlobalFrozen(ReadView const &view, AccountID const &issuer)
Check if the issuer has the global freeze flag set.
static bool isDefaultPath(STPath const &path)
LineDirection
Describes how an account was found in a path, and how to find the next set of paths.
Definition TrustLine.h:27
@ JtPathFind
Definition Job.h:70
BaseUInt< 192 > MPTID
MPTID is a 192-bit value representing MPT Issuance ID, which is a concatenation of a 32-bit sequence ...
Definition UintTypes.h:54
std::uint64_t getRate(STAmount const &offerOut, STAmount const &offerIn)
bool convertAllCheck(STAmount const &a)
@ TapNone
Definition ApplyView.h:28
BaseUInt< 160, detail::AccountIDTag > AccountID
A 160-bit unsigned that uniquely identifies an account.
Definition AccountID.h:34
bool isTesSuccess(TER x) noexcept
Definition TER.h:686
TERSubset< CanCvtToTER > TER
Definition TER.h:657
TER requireAuth(ReadView const &view, MPTIssue const &mptIssue, AccountID const &account, AuthType authType=AuthType::Legacy, std::uint8_t depth=0)
Check if the account lacks required authorization for MPT.
AccountID const & xrpAccount()
Compute AccountID from public key.
@ tesSUCCESS
Definition TER.h:253
constexpr bool equalTokens(Asset const &lhs, Asset const &rhs)
Definition Asset.h:286
T pop_back(T... args)
T push_back(T... args)
T reserve(T... args)
T sort(T... args)
T value(T... args)
T value_or(T... args)
T what(T... args)