Loading...
Searching...
No Matches
path.h
1//
2// Copyright 2016 Pixar
3//
4// Licensed under the Apache License, Version 2.0 (the "Apache License")
5// with the following modification; you may not use this file except in
6// compliance with the Apache License and the following modification to it:
7// Section 6. Trademarks. is deleted and replaced with:
8//
9// 6. Trademarks. This License does not grant permission to use the trade
10// names, trademarks, service marks, or product names of the Licensor
11// and its affiliates, except as required to comply with Section 4(c) of
12// the License and to reproduce the content of the NOTICE file.
13//
14// You may obtain a copy of the Apache License at
15//
16// http://www.apache.org/licenses/LICENSE-2.0
17//
18// Unless required by applicable law or agreed to in writing, software
19// distributed under the Apache License with the above modification is
20// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21// KIND, either express or implied. See the Apache License for the specific
22// language governing permissions and limitations under the Apache License.
23//
24#ifndef PXR_USD_SDF_PATH_H
25#define PXR_USD_SDF_PATH_H
26
27#include "pxr/pxr.h"
28#include "pxr/usd/sdf/api.h"
29#include "pxr/usd/sdf/pool.h"
30#include "pxr/usd/sdf/tokens.h"
31#include "pxr/base/arch/defines.h"
32#include "pxr/base/tf/stl.h"
33#include "pxr/base/tf/token.h"
34#include "pxr/base/vt/traits.h"
35
36#include <boost/intrusive_ptr.hpp>
37
38#include <algorithm>
39#include <iterator>
40#include <set>
41#include <string>
42#include <type_traits>
43#include <utility>
44#include <vector>
45
46PXR_NAMESPACE_OPEN_SCOPE
47
48class Sdf_PathNode;
50
51// Ref-counting pointer to a path node.
52// Intrusive ref-counts are used to keep the size of SdfPath
53// the same as a raw pointer. (shared_ptr, by comparison,
54// is the size of two pointers.)
55
56typedef boost::intrusive_ptr<const Sdf_PathNode> Sdf_PathNodeConstRefPtr;
57
58void intrusive_ptr_add_ref(Sdf_PathNode const *);
59void intrusive_ptr_release(Sdf_PathNode const *);
60
61// Tags used for the pools of path nodes.
62struct Sdf_PathPrimTag;
63struct Sdf_PathPropTag;
64
65// These are validated below.
66static constexpr size_t Sdf_SizeofPrimPathNode = sizeof(void *) * 3;
67static constexpr size_t Sdf_SizeofPropPathNode = sizeof(void *) * 3;
68
69using Sdf_PathPrimPartPool = Sdf_Pool<
70 Sdf_PathPrimTag, Sdf_SizeofPrimPathNode, /*regionBits=*/8>;
71
72using Sdf_PathPropPartPool = Sdf_Pool<
73 Sdf_PathPropTag, Sdf_SizeofPropPathNode, /*regionBits=*/8>;
74
75using Sdf_PathPrimHandle = Sdf_PathPrimPartPool::Handle;
76using Sdf_PathPropHandle = Sdf_PathPropPartPool::Handle;
77
78// This handle class wraps up the raw Prim/PropPartPool handles.
79template <class Handle, bool Counted, class PathNode=Sdf_PathNode const>
80struct Sdf_PathNodeHandleImpl {
81private:
82 typedef Sdf_PathNodeHandleImpl this_type;
83
84public:
85 static constexpr bool IsCounted = Counted;
86
87 constexpr Sdf_PathNodeHandleImpl() noexcept {};
88
89 explicit
90 Sdf_PathNodeHandleImpl(Sdf_PathNode const *p, bool add_ref = true)
91 : _poolHandle(Handle::GetHandle(reinterpret_cast<char const *>(p))) {
92 if (p && add_ref) {
93 _AddRef(p);
94 }
95 }
96
97 explicit
98 Sdf_PathNodeHandleImpl(Handle h, bool add_ref = true)
99 : _poolHandle(h) {
100 if (h && add_ref) {
101 _AddRef();
102 }
103 }
104
105 Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl const &rhs) noexcept
106 : _poolHandle(rhs._poolHandle) {
107 if (_poolHandle) {
108 _AddRef();
109 }
110 }
111
112 ~Sdf_PathNodeHandleImpl() {
113 if (_poolHandle) {
114 _DecRef();
115 }
116 }
117
118 Sdf_PathNodeHandleImpl &
119 operator=(Sdf_PathNodeHandleImpl const &rhs) {
120 if (Counted && *this == rhs) {
121 return *this;
122 }
123 this_type(rhs).swap(*this);
124 return *this;
125 }
126
127 Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl &&rhs) noexcept
128 : _poolHandle(rhs._poolHandle) {
129 rhs._poolHandle = nullptr;
130 }
131
132 Sdf_PathNodeHandleImpl &
133 operator=(Sdf_PathNodeHandleImpl &&rhs) noexcept {
134 this_type(std::move(rhs)).swap(*this);
135 return *this;
136 }
137
138 Sdf_PathNodeHandleImpl &
139 operator=(Sdf_PathNode const *rhs) noexcept {
140 this_type(rhs).swap(*this);
141 return *this;
142 }
143
144 void reset() noexcept {
145 _poolHandle = Handle { nullptr };
146 }
147
148 inline Sdf_PathNode const *
149 get() const noexcept {
150 return reinterpret_cast<Sdf_PathNode *>(_poolHandle.GetPtr());
151 }
152
153 Sdf_PathNode const &
154 operator*() const {
155 return *get();
156 }
157
158 Sdf_PathNode const *
159 operator->() const {
160 return get();
161 }
162
163 explicit operator bool() const noexcept {
164 return static_cast<bool>(_poolHandle);
165 }
166
167 void swap(Sdf_PathNodeHandleImpl &rhs) noexcept {
168 _poolHandle.swap(rhs._poolHandle);
169 }
170
171 inline bool operator==(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
172 return _poolHandle == rhs._poolHandle;
173 }
174 inline bool operator!=(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
175 return _poolHandle != rhs._poolHandle;
176 }
177 inline bool operator<(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
178 return _poolHandle < rhs._poolHandle;
179 }
180private:
181
182 inline void _AddRef(Sdf_PathNode const *p) const {
183 if (Counted) {
184 intrusive_ptr_add_ref(p);
185 }
186 }
187
188 inline void _AddRef() const {
189 _AddRef(get());
190 }
191
192 inline void _DecRef() const {
193 if (Counted) {
194 intrusive_ptr_release(get());
195 }
196 }
197
198 Handle _poolHandle { nullptr };
199};
200
201using Sdf_PathPrimNodeHandle =
202 Sdf_PathNodeHandleImpl<Sdf_PathPrimHandle, /*Counted=*/true>;
203
204using Sdf_PathPropNodeHandle =
205 Sdf_PathNodeHandleImpl<Sdf_PathPropHandle, /*Counted=*/false>;
206
207
209typedef std::set<class SdfPath> SdfPathSet;
211typedef std::vector<class SdfPath> SdfPathVector;
212
213// Tell VtValue that SdfPath is cheap to copy.
214VT_TYPE_IS_CHEAP_TO_COPY(class SdfPath);
215
291{
292public:
294 SDF_API static const SdfPath & EmptyPath();
295
298 SDF_API static const SdfPath & AbsoluteRootPath();
299
301 SDF_API static const SdfPath & ReflexiveRelativePath();
302
305
308#if defined(ARCH_COMPILER_GCC) && ARCH_COMPILER_GCC_MAJOR <= 6
309 SdfPath() noexcept {
310 // This generates a single instruction instead of 2 on gcc 6.3. Seems
311 // to be fixed on gcc 7+ and newer clangs.
312 memset(this, 0, sizeof(*this));
313 }
314#else
315 SdfPath() noexcept = default;
316#endif
317
330 //
331 // XXX We may want to revisit the behavior when constructing
332 // a path with an empty string ("") to accept it without error and
333 // return EmptyPath.
334 SDF_API explicit SdfPath(const std::string &path);
335
337
340
342 SDF_API size_t GetPathElementCount() const;
343
345 SDF_API bool IsAbsolutePath() const;
346
348 SDF_API bool IsAbsoluteRootPath() const;
349
351 SDF_API bool IsPrimPath() const;
352
354 SDF_API bool IsAbsoluteRootOrPrimPath() const;
355
360 SDF_API bool IsRootPrimPath() const;
361
367 SDF_API bool IsPropertyPath() const;
368
372 SDF_API bool IsPrimPropertyPath() const;
373
377 SDF_API bool IsNamespacedPropertyPath() const;
378
381 SDF_API bool IsPrimVariantSelectionPath() const;
382
386
389 SDF_API bool ContainsPrimVariantSelection() const;
390
397 return static_cast<bool>(_propPart);
398 }
399
402 SDF_API bool ContainsTargetPath() const;
403
407 SDF_API bool IsRelationalAttributePath() const;
408
411 SDF_API bool IsTargetPath() const;
412
414 SDF_API bool IsMapperPath() const;
415
417 SDF_API bool IsMapperArgPath() const;
418
420 SDF_API bool IsExpressionPath() const;
421
423 inline bool IsEmpty() const noexcept {
424 // No need to check _propPart, because it can only be non-null if
425 // _primPart is non-null.
426 return !_primPart;
427 }
428
434 SDF_API TfToken GetAsToken() const;
435
445 SDF_API TfToken const &GetToken() const;
446
452 SDF_API std::string GetAsString() const;
453
463 SDF_API const std::string &GetString() const;
464
475 SDF_API const char *GetText() const;
476
484 SDF_API SdfPathVector GetPrefixes() const;
485
494 SDF_API SdfPathVector GetPrefixes(size_t numPrefixes) const;
495
505 SDF_API void GetPrefixes(SdfPathVector *prefixes) const;
506
515 SDF_API void GetPrefixes(SdfPathVector *prefixes, size_t numPrefixes) const;
516
523
534 SDF_API const std::string &GetName() const;
535
538 SDF_API const TfToken &GetNameToken() const;
539
557 SDF_API std::string GetElementString() const;
558
560 SDF_API TfToken GetElementToken() const;
561
581 SDF_API SdfPath ReplaceName(TfToken const &newName) const;
582
595 SDF_API const SdfPath &GetTargetPath() const;
596
604 SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const;
605
610 SDF_API
611 std::pair<std::string, std::string> GetVariantSelection() const;
612
615 SDF_API bool HasPrefix( const SdfPath &prefix ) const;
616
618
621
644 SDF_API SdfPath GetParentPath() const;
645
653 SDF_API SdfPath GetPrimPath() const;
654
664
671
676
684 SDF_API SdfPath AppendPath(const SdfPath &newSuffix) const;
685
691 SDF_API SdfPath AppendChild(TfToken const &childName) const;
692
697 SDF_API SdfPath AppendProperty(TfToken const &propName) const;
698
703 SDF_API
704 SdfPath AppendVariantSelection(const std::string &variantSet,
705 const std::string &variant) const;
706
711 SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const;
712
717 SDF_API
719
723 SDF_API
724 SdfPath ReplaceTargetPath( const SdfPath &newTargetPath ) const;
725
730 SDF_API SdfPath AppendMapper(const SdfPath &targetPath) const;
731
736 SDF_API SdfPath AppendMapperArg(TfToken const &argName) const;
737
741 SDF_API SdfPath AppendExpression() const;
742
752 SDF_API SdfPath AppendElementString(const std::string &element) const;
753
755 SDF_API SdfPath AppendElementToken(const TfToken &elementTok) const;
756
766 SDF_API
767 SdfPath ReplacePrefix(const SdfPath &oldPrefix,
768 const SdfPath &newPrefix,
769 bool fixTargetPaths=true) const;
770
773 SDF_API SdfPath GetCommonPrefix(const SdfPath &path) const;
774
790 SDF_API
791 std::pair<SdfPath, SdfPath>
792 RemoveCommonSuffix(const SdfPath& otherPath,
793 bool stopAtRootPrim = false) const;
794
804 SDF_API SdfPath MakeAbsolutePath(const SdfPath & anchor) const;
805
818 SDF_API SdfPath MakeRelativePath(const SdfPath & anchor) const;
819
821
824
827 SDF_API static bool IsValidIdentifier(const std::string &name);
828
831 SDF_API static bool IsValidNamespacedIdentifier(const std::string &name);
832
836 SDF_API static std::vector<std::string> TokenizeIdentifier(const std::string &name);
837
841 SDF_API
842 static TfTokenVector TokenizeIdentifierAsTokens(const std::string &name);
843
846 SDF_API
847 static std::string JoinIdentifier(const std::vector<std::string> &names);
848
851 SDF_API
852 static std::string JoinIdentifier(const TfTokenVector& names);
853
858 SDF_API
859 static std::string JoinIdentifier(const std::string &lhs,
860 const std::string &rhs);
861
866 SDF_API
867 static std::string JoinIdentifier(const TfToken &lhs, const TfToken &rhs);
868
872 SDF_API
873 static std::string StripNamespace(const std::string &name);
874
878 SDF_API
879 static TfToken StripNamespace(const TfToken &name);
880
889 SDF_API
890 static std::pair<std::string, bool>
891 StripPrefixNamespace(const std::string &name,
892 const std::string &matchNamespace);
893
898 SDF_API
899 static bool IsValidPathString(const std::string &pathString,
900 std::string *errMsg = 0);
901
903
906
908 inline bool operator==(const SdfPath &rhs) const {
909 return _AsInt() == rhs._AsInt();
910 }
911
913 inline bool operator!=(const SdfPath &rhs) const {
914 return !(*this == rhs);
915 }
916
921 inline bool operator<(const SdfPath &rhs) const {
922 if (_AsInt() == rhs._AsInt()) {
923 return false;
924 }
925 if (!_primPart || !rhs._primPart) {
926 return !_primPart && rhs._primPart;
927 }
928 // Valid prim parts -- must walk node structure, etc.
929 return _LessThanInternal(*this, rhs);
930 }
931
934 inline bool operator>(const SdfPath& rhs) const {
935 return rhs < *this;
936 }
937
940 inline bool operator<=(const SdfPath& rhs) const {
941 return !(rhs < *this);
942 }
943
946 inline bool operator>=(const SdfPath& rhs) const {
947 return !(*this < rhs);
948 }
949
950 template <class HashState>
951 friend void TfHashAppend(HashState &h, SdfPath const &path) {
952 // The hash function is pretty sensitive performance-wise. Be
953 // careful making changes here, and run tests.
954 uint32_t primPart, propPart;
955 memcpy(&primPart, &path._primPart, sizeof(primPart));
956 memcpy(&propPart, &path._propPart, sizeof(propPart));
957 h.Append(primPart);
958 h.Append(propPart);
959 }
960
961 // For hash maps and sets
962 struct Hash {
963 inline size_t operator()(const SdfPath& path) const {
964 return TfHash()(path);
965 }
966 };
967
968 inline size_t GetHash() const {
969 return Hash()(*this);
970 }
971
972 // For cases where an unspecified total order that is not stable from
973 // run-to-run is needed.
974 struct FastLessThan {
975 inline bool operator()(const SdfPath& a, const SdfPath& b) const {
976 return a._AsInt() < b._AsInt();
977 }
978 };
979
981
984
991 SDF_API static SdfPathVector
992 GetConciseRelativePaths(const SdfPathVector& paths);
993
997 SDF_API static void RemoveDescendentPaths(SdfPathVector *paths);
998
1001 SDF_API static void RemoveAncestorPaths(SdfPathVector *paths);
1002
1004
1005private:
1006
1007 // This is used for all internal path construction where we do operations
1008 // via nodes and then want to return a new path with a resulting prim and
1009 // property parts.
1010
1011 // Accept rvalues.
1012 explicit SdfPath(Sdf_PathPrimNodeHandle &&primNode)
1013 : _primPart(std::move(primNode)) {}
1014
1015 SdfPath(Sdf_PathPrimNodeHandle &&primPart,
1016 Sdf_PathPropNodeHandle &&propPart)
1017 : _primPart(std::move(primPart))
1018 , _propPart(std::move(propPart)) {}
1019
1020 // Construct from prim & prop parts.
1021 SdfPath(Sdf_PathPrimNodeHandle const &primPart,
1022 Sdf_PathPropNodeHandle const &propPart)
1023 : _primPart(primPart)
1024 , _propPart(propPart) {}
1025
1026 // Construct from prim & prop node pointers.
1027 SdfPath(Sdf_PathNode const *primPart,
1028 Sdf_PathNode const *propPart)
1029 : _primPart(primPart)
1030 , _propPart(propPart) {}
1031
1032 friend class Sdf_PathNode;
1033 friend class Sdfext_PathAccess;
1034 friend class SdfPathAncestorsRange;
1035
1036 // converts elements to a string for parsing (unfortunate)
1037 static std::string
1038 _ElementsToString(bool absolute, const std::vector<std::string> &elements);
1039
1040 SdfPath _ReplacePrimPrefix(SdfPath const &oldPrefix,
1041 SdfPath const &newPrefix) const;
1042
1043 SdfPath _ReplaceTargetPathPrefixes(SdfPath const &oldPrefix,
1044 SdfPath const &newPrefix) const;
1045
1046 SdfPath _ReplacePropPrefix(SdfPath const &oldPrefix,
1047 SdfPath const &newPrefix,
1048 bool fixTargetPaths) const;
1049
1050 // Helper to implement the uninlined portion of operator<.
1051 SDF_API static bool
1052 _LessThanInternal(SdfPath const &lhs, SdfPath const &rhs);
1053
1054 inline uint64_t _AsInt() const {
1055 static_assert(sizeof(*this) == sizeof(uint64_t), "");
1056 uint64_t ret;
1057 std::memcpy(&ret, this, sizeof(*this));
1058 return ret;
1059 }
1060
1061 friend void swap(SdfPath &lhs, SdfPath &rhs) {
1062 lhs._primPart.swap(rhs._primPart);
1063 lhs._propPart.swap(rhs._propPart);
1064 }
1065
1066 SDF_API friend char const *
1067 Sdf_PathGetDebuggerPathText(SdfPath const &);
1068
1069 Sdf_PathPrimNodeHandle _primPart;
1070 Sdf_PathPropNodeHandle _propPart;
1071
1072};
1073
1074
1092{
1093public:
1094
1095 SdfPathAncestorsRange(const SdfPath& path)
1096 : _path(path) {}
1097
1098 const SdfPath& GetPath() const { return _path; }
1099
1100 struct iterator {
1101 using iterator_category = std::forward_iterator_tag;
1102 using value_type = SdfPath;
1103 using difference_type = std::ptrdiff_t;
1104 using reference = const SdfPath&;
1105 using pointer = const SdfPath*;
1106
1107 iterator(const SdfPath& path) : _path(path) {}
1108
1109 iterator() = default;
1110
1111 SDF_API
1112 iterator& operator++();
1113
1114 const SdfPath& operator*() const { return _path; }
1115
1116 const SdfPath* operator->() const { return &_path; }
1117
1118 bool operator==(const iterator& o) const { return _path == o._path; }
1119
1120 bool operator!=(const iterator& o) const { return _path != o._path; }
1121
1125 SDF_API friend difference_type
1126 distance(const iterator& first, const iterator& last);
1127
1128 private:
1129 SdfPath _path;
1130 };
1131
1132 iterator begin() const { return iterator(_path); }
1133
1134 iterator end() const { return iterator(); }
1135
1136private:
1137 SdfPath _path;
1138};
1139
1140
1141// Overload hash_value for SdfPath. Used by things like boost::hash.
1142inline size_t hash_value(SdfPath const &path)
1143{
1144 return path.GetHash();
1145}
1146
1148SDF_API std::ostream & operator<<( std::ostream &out, const SdfPath &path );
1149
1150// Helper for SdfPathFindPrefixedRange & SdfPathFindLongestPrefix. A function
1151// object that returns an SdfPath const & unchanged.
1152struct Sdf_PathIdentity {
1153 inline SdfPath const &operator()(SdfPath const &arg) const {
1154 return arg;
1155 }
1156};
1157
1164template <class ForwardIterator, class GetPathFn = Sdf_PathIdentity>
1165std::pair<ForwardIterator, ForwardIterator>
1166SdfPathFindPrefixedRange(ForwardIterator begin, ForwardIterator end,
1167 SdfPath const &prefix,
1168 GetPathFn const &getPath = GetPathFn()) {
1169 using IterRef =
1170 typename std::iterator_traits<ForwardIterator>::reference;
1171
1172 struct Compare {
1173 Compare(GetPathFn const &getPath) : _getPath(getPath) {}
1174 GetPathFn const &_getPath;
1175 bool operator()(IterRef a, SdfPath const &b) const {
1176 return _getPath(a) < b;
1177 }
1178 };
1179
1180 std::pair<ForwardIterator, ForwardIterator> result;
1181
1182 // First, use lower_bound to find where \a prefix would go.
1183 result.first = std::lower_bound(begin, end, prefix, Compare(getPath));
1184
1185 // Next, find end of range starting from the lower bound, using the
1186 // prefixing condition to define the boundary.
1187 result.second = TfFindBoundary(result.first, end,
1188 [&prefix, &getPath](IterRef iterRef) {
1189 return getPath(iterRef).HasPrefix(prefix);
1190 });
1191
1192 return result;
1193}
1194
1195template <class RandomAccessIterator, class GetPathFn>
1196RandomAccessIterator
1197Sdf_PathFindLongestPrefixImpl(RandomAccessIterator begin,
1198 RandomAccessIterator end,
1199 SdfPath const &path,
1200 bool strictPrefix,
1201 GetPathFn const &getPath)
1202{
1203 using IterRef =
1204 typename std::iterator_traits<RandomAccessIterator>::reference;
1205
1206 struct Compare {
1207 Compare(GetPathFn const &getPath) : _getPath(getPath) {}
1208 GetPathFn const &_getPath;
1209 bool operator()(IterRef a, SdfPath const &b) const {
1210 return _getPath(a) < b;
1211 }
1212 };
1213
1214 // Search for the path in [begin, end). If present, return it. If not,
1215 // examine prior element in [begin, end). If none, return end. Else, is it
1216 // a prefix of path? If so, return it. Else find common prefix of that
1217 // element and path and recurse.
1218
1219 // If empty sequence, return.
1220 if (begin == end)
1221 return end;
1222
1223 Compare comp(getPath);
1224
1225 // Search for where this path would lexicographically appear in the range.
1226 RandomAccessIterator result = std::lower_bound(begin, end, path, comp);
1227
1228 // If we didn't get the end, check to see if we got the path exactly if
1229 // we're not looking for a strict prefix.
1230 if (!strictPrefix && result != end && getPath(*result) == path) {
1231 return result;
1232 }
1233
1234 // If we got begin (and didn't match in the case of a non-strict prefix)
1235 // then there's no prefix.
1236 if (result == begin) {
1237 return end;
1238 }
1239
1240 // If the prior element is a prefix, we're done.
1241 if (path.HasPrefix(getPath(*--result))) {
1242 return result;
1243 }
1244
1245 // Otherwise, find the common prefix of the lexicographical predecessor and
1246 // look for its prefix in the preceding range.
1247 SdfPath newPath = path.GetCommonPrefix(getPath(*result));
1248 auto origEnd = end;
1249 do {
1250 end = result;
1251 result = std::lower_bound(begin, end, newPath, comp);
1252
1253 if (result != end && getPath(*result) == newPath) {
1254 return result;
1255 }
1256 if (result == begin) {
1257 return origEnd;
1258 }
1259 if (newPath.HasPrefix(getPath(*--result))) {
1260 return result;
1261 }
1262 newPath = newPath.GetCommonPrefix(getPath(*result));
1263 } while (true);
1264}
1265
1273template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
1274 class = typename std::enable_if<
1275 std::is_base_of<
1276 std::random_access_iterator_tag,
1277 typename std::iterator_traits<
1278 RandomAccessIterator>::iterator_category
1279 >::value
1280 >::type
1281 >
1282RandomAccessIterator
1283SdfPathFindLongestPrefix(RandomAccessIterator begin,
1284 RandomAccessIterator end,
1285 SdfPath const &path,
1286 GetPathFn const &getPath = GetPathFn())
1287{
1288 return Sdf_PathFindLongestPrefixImpl(
1289 begin, end, path, /*strictPrefix=*/false, getPath);
1290}
1291
1299template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
1300 class = typename std::enable_if<
1301 std::is_base_of<
1302 std::random_access_iterator_tag,
1303 typename std::iterator_traits<
1304 RandomAccessIterator>::iterator_category
1305 >::value
1306 >::type
1307 >
1308RandomAccessIterator
1309SdfPathFindLongestStrictPrefix(RandomAccessIterator begin,
1310 RandomAccessIterator end,
1311 SdfPath const &path,
1312 GetPathFn const &getPath = GetPathFn())
1313{
1314 return Sdf_PathFindLongestPrefixImpl(
1315 begin, end, path, /*strictPrefix=*/true, getPath);
1316}
1317
1318template <class Iter, class MapParam, class GetPathFn = Sdf_PathIdentity>
1319Iter
1320Sdf_PathFindLongestPrefixImpl(
1321 MapParam map, SdfPath const &path, bool strictPrefix,
1322 GetPathFn const &getPath = GetPathFn())
1323{
1324 // Search for the path in map. If present, return it. If not, examine
1325 // prior element in map. If none, return end. Else, is it a prefix of
1326 // path? If so, return it. Else find common prefix of that element and
1327 // path and recurse.
1328
1329 const Iter mapEnd = map.end();
1330
1331 // If empty, return.
1332 if (map.empty())
1333 return mapEnd;
1334
1335 // Search for where this path would lexicographically appear in the range.
1336 Iter result = map.lower_bound(path);
1337
1338 // If we didn't get the end, check to see if we got the path exactly if
1339 // we're not looking for a strict prefix.
1340 if (!strictPrefix && result != mapEnd && getPath(*result) == path)
1341 return result;
1342
1343 // If we got begin (and didn't match in the case of a non-strict prefix)
1344 // then there's no prefix.
1345 if (result == map.begin())
1346 return mapEnd;
1347
1348 // If the prior element is a prefix, we're done.
1349 if (path.HasPrefix(getPath(*--result)))
1350 return result;
1351
1352 // Otherwise, find the common prefix of the lexicographical predecessor and
1353 // recurse looking for it or its longest prefix in the preceding range. We
1354 // always pass strictPrefix=false, since now we're operating on prefixes of
1355 // the original caller's path.
1356 return Sdf_PathFindLongestPrefixImpl<Iter, MapParam>(
1357 map, path.GetCommonPrefix(getPath(*result)), /*strictPrefix=*/false,
1358 getPath);
1359}
1360
1364SDF_API
1365typename std::set<SdfPath>::const_iterator
1366SdfPathFindLongestPrefix(std::set<SdfPath> const &set, SdfPath const &path);
1367
1371template <class T>
1372typename std::map<SdfPath, T>::const_iterator
1373SdfPathFindLongestPrefix(std::map<SdfPath, T> const &map, SdfPath const &path)
1374{
1375 return Sdf_PathFindLongestPrefixImpl<
1376 typename std::map<SdfPath, T>::const_iterator,
1377 std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/false,
1378 TfGet<0>());
1379}
1380template <class T>
1381typename std::map<SdfPath, T>::iterator
1382SdfPathFindLongestPrefix(std::map<SdfPath, T> &map, SdfPath const &path)
1383{
1384 return Sdf_PathFindLongestPrefixImpl<
1385 typename std::map<SdfPath, T>::iterator,
1386 std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/false,
1387 TfGet<0>());
1388}
1389
1393SDF_API
1394typename std::set<SdfPath>::const_iterator
1395SdfPathFindLongestStrictPrefix(std::set<SdfPath> const &set,
1396 SdfPath const &path);
1397
1401template <class T>
1402typename std::map<SdfPath, T>::const_iterator
1403SdfPathFindLongestStrictPrefix(
1404 std::map<SdfPath, T> const &map, SdfPath const &path)
1405{
1406 return Sdf_PathFindLongestPrefixImpl<
1407 typename std::map<SdfPath, T>::const_iterator,
1408 std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/true,
1409 TfGet<0>());
1410}
1411template <class T>
1412typename std::map<SdfPath, T>::iterator
1413SdfPathFindLongestStrictPrefix(
1414 std::map<SdfPath, T> &map, SdfPath const &path)
1415{
1416 return Sdf_PathFindLongestPrefixImpl<
1417 typename std::map<SdfPath, T>::iterator,
1418 std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/true,
1419 TfGet<0>());
1420}
1421
1422// A helper function for debugger pretty-printers, etc. This function is *not*
1423// thread-safe. It writes to a static buffer and returns a pointer to it.
1424// Subsequent calls to this function overwrite the memory written in prior
1425// calls. If the given path's string representation exceeds the static buffer
1426// size, return a pointer to a message indicating so.
1427SDF_API
1428char const *
1429Sdf_PathGetDebuggerPathText(SdfPath const &);
1430
1431PXR_NAMESPACE_CLOSE_SCOPE
1432
1433// Sdf_PathNode is not public API, but we need to include it here
1434// so we can inline the ref-counting operations, which must manipulate
1435// its internal _refCount member.
1436#include "pxr/usd/sdf/pathNode.h"
1437
1438PXR_NAMESPACE_OPEN_SCOPE
1439
1440static_assert(Sdf_SizeofPrimPathNode == sizeof(Sdf_PrimPathNode), "");
1441static_assert(Sdf_SizeofPropPathNode == sizeof(Sdf_PrimPropertyPathNode), "");
1442
1443PXR_NAMESPACE_CLOSE_SCOPE
1444
1445#endif // PXR_USD_SDF_PATH_H
Range representing a path and ancestors, and providing methods for iterating over them.
Definition: path.h:1092
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:291
SDF_API SdfPath(const std::string &path)
Creates a path from the given string.
SDF_API SdfPath MakeAbsolutePath(const SdfPath &anchor) const
Returns the absolute form of this path using anchor as the relative basis.
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path's namespace parent.
SDF_API const std::string & GetString() const
Return the string representation of this path as a std::string.
SDF_API bool IsPrimVariantSelectionPath() const
Returns whether the path identifies a variant selection for a prim.
static SDF_API std::string JoinIdentifier(const TfTokenVector &names)
Join names into a single identifier using the namespace delimiter.
static SDF_API bool IsValidIdentifier(const std::string &name)
Returns whether name is a legal identifier for any path component.
SDF_API SdfPath ReplaceTargetPath(const SdfPath &newTargetPath) const
Replaces the relational attribute's target path.
SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const
Returns all the relationship target or connection target paths contained in this path,...
SDF_API SdfPath GetPrimOrPrimVariantSelectionPath() const
Creates a path by stripping all relational attributes, targets, and properties, leaving the nearest p...
SDF_API std::pair< SdfPath, SdfPath > RemoveCommonSuffix(const SdfPath &otherPath, bool stopAtRootPrim=false) const
Find and remove the longest common suffix from two paths.
SDF_API SdfPath AppendElementString(const std::string &element) const
Creates a path by extracting and appending an element from the given ascii element encoding.
SDF_API bool IsMapperArgPath() const
Returns whether the path identifies a connection mapper arg.
SDF_API bool IsRelationalAttributePath() const
Returns whether the path identifies a relational attribute.
static SDF_API TfToken StripNamespace(const TfToken &name)
Returns name stripped of any namespaces.
SDF_API bool IsAbsoluteRootOrPrimPath() const
Returns whether the path identifies a prim or the absolute root.
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
SDF_API const char * GetText() const
Returns the string representation of this path as a c string.
static SDF_API SdfPathVector GetConciseRelativePaths(const SdfPathVector &paths)
Given some vector of paths, get a vector of concise unambiguous relative paths.
SDF_API std::pair< std::string, std::string > GetVariantSelection() const
Returns the variant selection for this path, if this is a variant selection path.
bool operator<=(const SdfPath &rhs) const
Less than or equal operator.
Definition: path.h:940
SDF_API SdfPath AppendExpression() const
Creates a path by appending an expression element.
SDF_API SdfPath AppendRelationalAttribute(TfToken const &attrName) const
Creates a path by appending an element for attrName to this path.
SDF_API std::string GetElementString() const
Returns an ascii representation of the "terminal" element of this path, which can be used to reconstr...
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:423
SDF_API bool IsAbsolutePath() const
Returns whether the path is absolute.
SDF_API SdfPath GetAbsoluteRootOrPrimPath() const
Creates a path by stripping all properties and relational attributes from this path,...
SDF_API SdfPath AppendPath(const SdfPath &newSuffix) const
Creates a path by appending a given relative path to this path.
SDF_API SdfPath MakeRelativePath(const SdfPath &anchor) const
Returns the relative form of this path using anchor as the relative basis.
static SDF_API const SdfPath & ReflexiveRelativePath()
The relative path representing "self".
bool operator>(const SdfPath &rhs) const
Greater than operator.
Definition: path.h:934
static SDF_API std::string JoinIdentifier(const std::string &lhs, const std::string &rhs)
Join lhs and rhs into a single identifier using the namespace delimiter.
static SDF_API std::vector< std::string > TokenizeIdentifier(const std::string &name)
Tokenizes name by the namespace delimiter.
SDF_API bool IsPropertyPath() const
Returns whether the path identifies a property.
SDF_API SdfPath AppendMapper(const SdfPath &targetPath) const
Creates a path by appending a mapper element for targetPath.
SDF_API SdfPath AppendElementToken(const TfToken &elementTok) const
Like AppendElementString() but take the element as a TfToken.
SDF_API bool HasPrefix(const SdfPath &prefix) const
Return true if both this path and prefix are not the empty path and this path has prefix as a prefix.
static SDF_API std::string JoinIdentifier(const std::vector< std::string > &names)
Join names into a single identifier using the namespace delimiter.
SDF_API bool IsTargetPath() const
Returns whether the path identifies a relationship or connection target.
SDF_API size_t GetPathElementCount() const
Returns the number of path elements in this path.
SDF_API TfToken GetElementToken() const
Like GetElementString() but return the value as a TfToken.
static SDF_API const SdfPath & EmptyPath()
The empty path value, equivalent to SdfPath().
SDF_API const std::string & GetName() const
Returns the name of the prim, property or relational attribute identified by the path.
SDF_API TfToken GetAsToken() const
Return the string representation of this path as a TfToken.
SDF_API const SdfPath & GetTargetPath() const
Returns the relational attribute or mapper target path for this path.
SDF_API SdfPathVector GetPrefixes() const
Returns the prefix paths of this path.
static SDF_API std::string StripNamespace(const std::string &name)
Returns name stripped of any namespaces.
SDF_API void GetPrefixes(SdfPathVector *prefixes, size_t numPrefixes) const
Fill prefixes with up to numPrefixes prefixes of this path.
static SDF_API TfTokenVector TokenizeIdentifierAsTokens(const std::string &name)
Tokenizes name by the namespace delimiter.
SDF_API bool IsRootPrimPath() const
Returns whether the path identifies a root prim.
static SDF_API bool IsValidNamespacedIdentifier(const std::string &name)
Returns whether name is a legal namespaced identifier.
SDF_API const TfToken & GetNameToken() const
Returns the name of the prim, property or relational attribute identified by the path,...
SDF_API bool IsPrimPath() const
Returns whether the path identifies a prim.
static SDF_API std::pair< std::string, bool > StripPrefixNamespace(const std::string &name, const std::string &matchNamespace)
Returns (name, true) where name is stripped of the prefix specified by matchNamespace if name indeed ...
SDF_API SdfPath AppendVariantSelection(const std::string &variantSet, const std::string &variant) const
Creates a path by appending an element for variantSet and variant to this path.
SDF_API SdfPath AppendProperty(TfToken const &propName) const
Creates a path by appending an element for propName to this path.
SDF_API bool IsExpressionPath() const
Returns whether the path identifies a connection expression.
SDF_API bool IsNamespacedPropertyPath() const
Returns whether the path identifies a namespaced property.
SDF_API SdfPath AppendMapperArg(TfToken const &argName) const
Creates a path by appending an element for argName.
SDF_API TfToken const & GetToken() const
Return the string representation of this path as a TfToken lvalue.
bool operator<(const SdfPath &rhs) const
Comparison operator.
Definition: path.h:921
bool operator>=(const SdfPath &rhs) const
Greater than or equal operator.
Definition: path.h:946
SDF_API SdfPath AppendChild(TfToken const &childName) const
Creates a path by appending an element for childName to this path.
bool ContainsPropertyElements() const
Return true if this path contains any property elements, false otherwise.
Definition: path.h:396
SDF_API bool IsMapperPath() const
Returns whether the path identifies a connection mapper.
static SDF_API void RemoveDescendentPaths(SdfPathVector *paths)
Remove all elements of paths that are prefixed by other elements in paths.
SDF_API SdfPath GetCommonPrefix(const SdfPath &path) const
Returns a path with maximal length that is a prefix path of both this path and path.
static SDF_API std::string JoinIdentifier(const TfToken &lhs, const TfToken &rhs)
Join lhs and rhs into a single identifier using the namespace delimiter.
static SDF_API bool IsValidPathString(const std::string &pathString, std::string *errMsg=0)
Return true if pathString is a valid path string, meaning that passing the string to the SdfPath cons...
SDF_API SdfPath ReplacePrefix(const SdfPath &oldPrefix, const SdfPath &newPrefix, bool fixTargetPaths=true) const
Returns a path with all occurrences of the prefix path oldPrefix replaced with the prefix path newPre...
SDF_API bool IsAbsoluteRootPath() const
Return true if this path is the AbsoluteRootPath().
bool operator==(const SdfPath &rhs) const
Equality operator.
Definition: path.h:908
SDF_API SdfPathAncestorsRange GetAncestorsRange() const
Return a range for iterating over the ancestors of this path.
SDF_API bool ContainsPrimVariantSelection() const
Returns whether the path or any of its parent paths identifies a variant selection for a prim.
SDF_API bool IsPrimPropertyPath() const
Returns whether the path identifies a prim's property.
SDF_API SdfPath StripAllVariantSelections() const
Create a path by stripping all variant selections from all components of this path,...
SDF_API bool ContainsTargetPath() const
Return true if this path is or has a prefix that's a target path or a mapper path.
SDF_API SdfPath ReplaceName(TfToken const &newName) const
Return a copy of this path with its final component changed to newName.
SDF_API void GetPrefixes(SdfPathVector *prefixes) const
Fills prefixes with prefixes of this path.
SDF_API bool IsPrimOrPrimVariantSelectionPath() const
Return true if this path is a prim path or is a prim variant selection path.
SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const
Creates a path by appending an element for targetPath.
SdfPath() noexcept=default
Constructs the default, empty path.
SDF_API SdfPathVector GetPrefixes(size_t numPrefixes) const
Return up to numPrefixes prefix paths of this path.
SDF_API SdfPath GetPrimPath() const
Creates a path by stripping all relational attributes, targets, properties, and variant selections fr...
static SDF_API void RemoveAncestorPaths(SdfPathVector *paths)
Remove all elements of paths that prefix other elements in paths.
bool operator!=(const SdfPath &rhs) const
Inequality operator.
Definition: path.h:913
SDF_API std::string GetAsString() const
Return the string representation of this path as a std::string.
Function object for retrieving the N'th element of a std::pair or std::tuple.
Definition: stl.h:379
A user-extensible hashing mechanism for use with runtime hash tables.
Definition: hash.h:504
Token for efficient comparison, assignment, and hashing of known strings.
Definition: token.h:88
GF_API std::ostream & operator<<(std::ostream &, const GfBBox3d &)
Output a GfBBox3d using the format [(range) matrix zeroArea].
STL namespace.
TfToken class for efficient string referencing and hashing, plus conversions to and from stl string c...
std::vector< TfToken > TfTokenVector
Convenience types.
Definition: token.h:442