xrpld
Loading...
Searching...
No Matches
STPathSet.cpp
1#include <xrpl/protocol/STPathSet.h>
2
3#include <xrpl/basics/CountedObject.h>
4#include <xrpl/basics/Log.h>
5#include <xrpl/basics/UnorderedContainers.h>
6#include <xrpl/basics/base_uint.h>
7#include <xrpl/basics/contract.h>
8#include <xrpl/beast/hash/uhash.h>
9#include <xrpl/beast/utility/instrumentation.h>
10#include <xrpl/json/json_value.h>
11#include <xrpl/protocol/AccountID.h>
12#include <xrpl/protocol/SField.h>
13#include <xrpl/protocol/STBase.h>
14#include <xrpl/protocol/Serializer.h>
15#include <xrpl/protocol/UintTypes.h>
16#include <xrpl/protocol/detail/STVar.h>
17#include <xrpl/protocol/jss.h>
18
19#include <algorithm>
20#include <cstddef>
21#include <memory>
22#include <stdexcept>
23#include <utility>
24#include <vector>
25
26namespace xrpl {
27
28std::size_t
30{
31 std::size_t hashAccount = 2654435761;
32 std::size_t hashCurrency = 2654435761;
33 std::size_t hashIssuer = 2654435761;
34
35 // NIKB NOTE: This doesn't have to be a secure hash as speed is more
36 // important. We don't even really need to fully hash the whole
37 // base_uint here, as a few bytes would do for our use.
38 //
39 // The note above is only true because the result of this function reaches
40 // nothing but STPathElement::operator==, where it is a fast-reject
41 // prefilter ahead of the field comparisons that decide the answer. Do not
42 // use it to key a container.
43
44 for (auto const x : element.getAccountID())
45 hashAccount += (hashAccount * 257) ^ x;
46
47 // Check pathAsset type instead of element's type_
48 // In some cases type_ might be account but the asset
49 // is still set to either MPT or currency (see Pathfinder::addLink())
50 element.getPathAsset().visit(
51 [&](MPTID const& mpt) { hashCurrency += beast::Uhash<>{}(mpt); },
52 [&](Currency const& currency) {
53 for (auto const x : currency)
54 hashCurrency += (hashCurrency * 509) ^ x;
55 });
56
57 for (auto const x : element.getIssuerID())
58 hashIssuer += (hashIssuer * 911) ^ x;
59
60 return (hashAccount ^ hashCurrency ^ hashIssuer);
61}
62
63// For guidance on deciding which option to pursue:
64// 1. Try to decrease the size of the STPathSet first. For instance, if a std::optional was
65// injected into the type, could you get the same functionality using a std::unique_ptr instead?
66// 2. If the size of the STPathSet is already as small as it can be, then consider what the cost
67// of increasing STVar::kMaxSize would be on all the other STVar types. Each of those types
68// will carry the additional cost of accommodating the larger STPathSet in their SBO.
69// 3. If the cost of increasing STVar::kMaxSize is too high, then heap allocate the STPathSet and
70// remove this static_assert.
71static_assert(
73 "STPathSet is too large to fit in STVar's small object optimization. Please verify if it "
74 "should, if the kMaxSize should be increased, or if STPathSet should be stored on the heap "
75 "instead of in STVar.");
76
80
82 : STBase{other}
83 , CountedObject<STPathSet>{other}
84 , value_{other.value_}
85 , seen_{
86 other.seen_ != nullptr ? std::make_unique<HardenedHashSet<STPath>>(*other.seen_)
87 : nullptr,
88 }
89{
90}
91
94{
95 if (this == &other)
96 {
97 return *this;
98 }
99 auto newSeen =
100 other.seen_ != nullptr ? std::make_unique<HardenedHashSet<STPath>>(*other.seen_) : nullptr;
101 STBase::operator=(other);
103 value_ = other.value_;
104 seen_ = std::move(newSeen);
105 return *this;
106}
107
109{
111 for (;;)
112 {
113 int const iType = sit.get8();
114
116 {
117 if (path.empty())
118 {
119 JLOG(debugLog().error()) << "Empty path in pathset";
120 Throw<std::runtime_error>("empty path");
121 }
122
123 // Move rather than converting the vector to an STPath by copy.
124 value_.emplace_back(std::move(path));
125 path.clear();
126
127 if (iType == STPathElement::TypeNone)
128 return;
129 }
130 else if ((iType & ~STPathElement::TypeAll) != 0)
131 {
132 JLOG(debugLog().error()) << "Bad path element " << iType << " in pathset";
133 Throw<std::runtime_error>("bad path element");
134 }
135 else
136 {
137 auto const hasAccount = (iType & STPathElement::TypeAccount) != 0u;
138 auto const hasCurrency = (iType & STPathElement::TypeCurrency) != 0u;
139 auto const hasIssuer = (iType & STPathElement::TypeIssuer) != 0u;
140 auto const hasMPT = (iType & STPathElement::TypeMpt) != 0u;
141
142 AccountID account;
143 PathAsset asset;
144 AccountID issuer;
145
146 if (hasAccount)
147 account = sit.get160();
148
149 if (hasCurrency && hasMPT)
150 {
151 JLOG(debugLog().error()) << "Bad path element MPT and Currency in pathset";
152 Throw<std::runtime_error>("bad path element: MPT and Currency");
153 }
154
155 if (hasCurrency)
156 asset = Currency::fromRaw(sit.get160());
157
158 if (hasMPT)
159 asset = sit.get192();
160
161 if (hasIssuer)
162 issuer = sit.get160();
163
164 path.emplace_back(account, asset, issuer, hasCurrency || hasMPT);
165 }
166 }
167}
168
169STBase*
170STPathSet::copy(std::size_t n, void* buf) const
171{
172 return emplace(n, buf, *this);
173}
174
175STBase*
177{
178 return emplace(n, buf, std::move(*this));
179}
180
181bool
183{ // assemble base+tail and add it to the set if it's not a duplicate
184 XRPL_ASSERT(seen_ != nullptr, "xrpl::STPathSet::assembleAdd : DeduplicationTag");
185 STPath combined = base;
186 combined.pushBack(tail);
187 return appendUnique([&](auto& value) { value.push_back(std::move(combined)); });
188}
189
190bool
192{
193 auto const* v = dynamic_cast<STPathSet const*>(&t);
194 return (v != nullptr) && (value_ == v->value_);
195}
196
197bool
199{
200 return value_.empty();
201}
202
203bool
204STPath::hasSeen(AccountID const& account, PathAsset const& asset, AccountID const& issuer) const
205{
206 return std::ranges::any_of(path_, [&](auto& p) {
207 return p.getAccountID() == account && p.getPathAsset() == asset &&
208 p.getIssuerID() == issuer;
209 });
210}
211
214{
216
217 for (auto const& it : path_)
218 {
220 auto const iType = it.getNodeType();
221
222 elem[jss::type] = iType;
223
224 if ((iType & STPathElement::TypeAccount) != 0u)
225 elem[jss::account] = to_string(it.getAccountID());
226
227 XRPL_ASSERT(
228 ((iType & STPathElement::TypeCurrency) == 0u) ||
229 ((iType & STPathElement::TypeMpt) == 0u),
230 "xrpl::STPath::getJson : not type Currency and MPT");
231 if ((iType & STPathElement::TypeCurrency) != 0u)
232 elem[jss::currency] = to_string(it.getCurrency());
233
234 if ((iType & STPathElement::TypeMpt) != 0u)
235 elem[jss::mpt_issuance_id] = to_string(it.getMPTID());
236
237 if ((iType & STPathElement::TypeIssuer) != 0u)
238 elem[jss::issuer] = to_string(it.getIssuerID());
239
240 ret.append(elem);
241 }
242
243 return ret;
244}
245
248{
250 for (auto const& it : value_)
251 ret.append(it.getJson(options));
252
253 return ret;
254}
255
258{
259 return STI_PATHSET;
260}
261
262void
264{
265 XRPL_ASSERT(getFName().isBinary(), "xrpl::STPathSet::add : field is binary");
266 XRPL_ASSERT(getFName().fieldType == STI_PATHSET, "xrpl::STPathSet::add : valid field type");
267 bool first = true;
268
269 for (auto const& spPath : value_)
270 {
271 if (!first)
273
274 for (auto const& speElement : spPath)
275 {
276 int const iType = speElement.getNodeType();
277
278 s.add8(iType);
279
280 if ((iType & STPathElement::TypeAccount) != 0u)
281 s.addBitString(speElement.getAccountID());
282
283 if ((iType & STPathElement::TypeMpt) != 0u)
284 s.addBitString(speElement.getMPTID());
285
286 if ((iType & STPathElement::TypeCurrency) != 0u)
287 s.addBitString(speElement.getCurrency());
288
289 if ((iType & STPathElement::TypeIssuer) != 0u)
290 s.addBitString(speElement.getIssuerID());
291 }
292
293 first = false;
294 }
295
297}
298
299} // namespace xrpl
T any_of(T... args)
Represents a JSON value.
Definition json_value.h:121
Value & append(Value const &value)
Append value to array at the end.
static BaseUInt fromRaw(Container const &c)
Definition base_uint.h:303
CountedObject & operator=(CountedObject const &) noexcept=default
constexpr auto visit(Visitors &&... visitors) const -> decltype(auto)
Definition PathAsset.h:52
Identifies fields.
Definition SField.h:131
A type which can be exported to a well known binary format.
Definition STBase.h:129
SField const & getFName() const
Definition STBase.cpp:120
static STBase * emplace(std::size_t n, void *buf, T &&val)
Definition STBase.h:226
STBase & operator=(STBase const &t)
Definition STBase.cpp:25
static std::size_t getHash(STPathElement const &element)
Definition STPathSet.cpp:29
AccountID const & getAccountID() const
Definition STPathSet.h:483
PathAsset const & getPathAsset() const
Definition STPathSet.h:489
AccountID const & getIssuerID() const
Definition STPathSet.h:507
void add(Serializer &s) const override
STPathSet()=default
bool assembleAdd(STPath const &base, STPathElement const &tail)
assembleAdd adds a path to the set by combining a base path and a tail element.
STBase * copy(std::size_t n, void *buf) const override
json::Value getJson(JsonOptions) const override
std::vector< STPath > value_
Definition STPathSet.h:201
STBase * move(std::size_t n, void *buf) override
bool isEquivalent(STBase const &t) const override
std::unique_ptr< HardenedHashSet< STPath > > seen_
Deduplication index over value_, for pathfinding.
Definition STPathSet.h:210
bool isDefault() const override
SerializedTypeID getSType() const override
STPathSet & operator=(STPathSet const &other)
Definition STPathSet.cpp:93
bool appendUnique(Append &&append)
Append a path via append, then register it in the deduplication index.
Definition STPathSet.h:637
std::vector< STPathElement > path_
Definition STPathSet.h:135
bool hasSeen(AccountID const &account, PathAsset const &asset, AccountID const &issuer) const
void pushBack(STPathElement const &e)
Definition STPathSet.h:538
json::Value getJson(JsonOptions) const
UInt192 get192()
Definition Serializer.h:547
UInt160 get160()
Definition Serializer.h:541
int addBitString(BaseUInt< Bits, Tag > const &v)
Definition Serializer.h:202
int add8(unsigned char byteValue)
static constexpr std::size_t kMaxSize
Definition STVar.h:39
T make_unique(T... args)
@ Array
array value (ordered list)
Definition json_value.h:32
@ Object
object value (collection of name/value pairs).
Definition json_value.h:33
STL namespace.
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
std::unordered_set< Value, Hash, Pred, Allocator > HardenedHashSet
beast::Journal debugLog()
Returns a debug journal.
Definition Log.cpp:399
BaseUInt< 160, detail::CurrencyTag > Currency
Currency is a hash representing a specific currency.
Definition UintTypes.h:42
std::string to_string(BaseUInt< Bits, Tag > const &a)
Definition base_uint.h:658
SerializedTypeID
Definition SField.h:93
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
BaseUInt< 160, detail::AccountIDTag > AccountID
A 160-bit unsigned that uniquely identifies an account.
Definition AccountID.h:34
XRPL_NO_SANITIZE_ADDRESS void Throw(Args &&... args)
Definition contract.h:52
Note, should be treated as flags that can be | and &.
Definition STBase.h:22