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/tf/stl.h"
32 #include "pxr/base/tf/token.h"
33 #include "pxr/base/vt/traits.h"
34 
35 #include <boost/intrusive_ptr.hpp>
36 #include <boost/operators.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 
46 PXR_NAMESPACE_OPEN_SCOPE
47 
48 class 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 
56 typedef boost::intrusive_ptr<const Sdf_PathNode> Sdf_PathNodeConstRefPtr;
57 
58 void intrusive_ptr_add_ref(Sdf_PathNode const *);
59 void intrusive_ptr_release(Sdf_PathNode const *);
60 
61 // Tags used for the pools of path nodes.
62 struct Sdf_PathPrimTag;
63 struct Sdf_PathPropTag;
64 
65 // These are validated below.
66 static constexpr size_t Sdf_SizeofPrimPathNode = sizeof(void *) * 3;
67 static constexpr size_t Sdf_SizeofPropPathNode = sizeof(void *) * 3;
68 
69 using Sdf_PathPrimPartPool = Sdf_Pool<
70  Sdf_PathPrimTag, Sdf_SizeofPrimPathNode, /*regionBits=*/8>;
71 
72 using Sdf_PathPropPartPool = Sdf_Pool<
73  Sdf_PathPropTag, Sdf_SizeofPropPathNode, /*regionBits=*/8>;
74 
75 using Sdf_PathPrimHandle = Sdf_PathPrimPartPool::Handle;
76 using Sdf_PathPropHandle = Sdf_PathPropPartPool::Handle;
77 
78 // This handle class wraps up the raw Prim/PropPartPool handles.
79 template <class Handle, bool Counted, class PathNode=Sdf_PathNode const>
80 struct Sdf_PathNodeHandleImpl {
81 private:
82  typedef Sdf_PathNodeHandleImpl this_type;
83 
84 public:
85  constexpr Sdf_PathNodeHandleImpl() noexcept {};
86 
87  explicit
88  Sdf_PathNodeHandleImpl(Sdf_PathNode const *p, bool add_ref = true)
89  : _poolHandle(Handle::GetHandle(reinterpret_cast<char const *>(p))) {
90  if (p && add_ref) {
91  _AddRef(p);
92  }
93  }
94 
95  explicit
96  Sdf_PathNodeHandleImpl(Handle h, bool add_ref = true)
97  : _poolHandle(h) {
98  if (h && add_ref) {
99  _AddRef();
100  }
101  }
102 
103  Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl const &rhs)
104  : _poolHandle(rhs._poolHandle) {
105  if (_poolHandle) {
106  _AddRef();
107  }
108  }
109 
110  ~Sdf_PathNodeHandleImpl() {
111  if (_poolHandle) {
112  _DecRef();
113  }
114  }
115 
116  Sdf_PathNodeHandleImpl &
117  operator=(Sdf_PathNodeHandleImpl const &rhs) {
118  if (Counted && *this == rhs) {
119  return *this;
120  }
121  this_type(rhs).swap(*this);
122  return *this;
123  }
124 
125  Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl &&rhs) noexcept
126  : _poolHandle(rhs._poolHandle) {
127  rhs._poolHandle = nullptr;
128  }
129 
130  Sdf_PathNodeHandleImpl &
131  operator=(Sdf_PathNodeHandleImpl &&rhs) noexcept {
132  this_type(std::move(rhs)).swap(*this);
133  return *this;
134  }
135 
136  Sdf_PathNodeHandleImpl &
137  operator=(Sdf_PathNode const *rhs) noexcept {
138  this_type(rhs).swap(*this);
139  return *this;
140  }
141 
142  void reset() noexcept {
143  _poolHandle = Handle { nullptr };
144  }
145 
146  Sdf_PathNode const *
147  get() const noexcept {
148  return reinterpret_cast<Sdf_PathNode *>(_poolHandle.GetPtr());
149  }
150 
151  Sdf_PathNode const &
152  operator*() const {
153  return *get();
154  }
155 
156  Sdf_PathNode const *
157  operator->() const {
158  return get();
159  }
160 
161  explicit operator bool() const noexcept {
162  return static_cast<bool>(_poolHandle);
163  }
164 
165  void swap(Sdf_PathNodeHandleImpl &rhs) noexcept {
166  _poolHandle.swap(rhs._poolHandle);
167  }
168 
169  inline bool operator==(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
170  return _poolHandle == rhs._poolHandle;
171  }
172  inline bool operator!=(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
173  return _poolHandle != rhs._poolHandle;
174  }
175  inline bool operator<(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
176  return _poolHandle < rhs._poolHandle;
177  }
178 private:
179 
180  void _AddRef(Sdf_PathNode const *p) const {
181  if (Counted) {
182  intrusive_ptr_add_ref(p);
183  }
184  }
185 
186  void _AddRef() const {
187  _AddRef(get());
188  }
189 
190  void _DecRef() const {
191  if (Counted) {
192  intrusive_ptr_release(get());
193  }
194  }
195 
196  Handle _poolHandle { nullptr };
197 };
198 
199 using Sdf_PathPrimNodeHandle =
200  Sdf_PathNodeHandleImpl<Sdf_PathPrimHandle, /*Counted=*/true>;
201 
202 using Sdf_PathPropNodeHandle =
203  Sdf_PathNodeHandleImpl<Sdf_PathPropHandle, /*Counted=*/false>;
204 
205 
207 typedef std::set<class SdfPath> SdfPathSet;
209 typedef std::vector<class SdfPath> SdfPathVector;
210 
211 // Tell VtValue that SdfPath is cheap to copy.
212 VT_TYPE_IS_CHEAP_TO_COPY(class SdfPath);
213 
288 class SdfPath : boost::totally_ordered<SdfPath>
289 {
290 public:
292  SDF_API static const SdfPath & EmptyPath();
293 
296  SDF_API static const SdfPath & AbsoluteRootPath();
297 
299  SDF_API static const SdfPath & ReflexiveRelativePath();
300 
303 
306  SdfPath() noexcept {
307  // This generates a single instruction instead of 2 on gcc 6.3. Seems
308  // to be fixed on gcc 7+ and newer clangs. Remove when we're there!
309  memset(this, 0, sizeof(*this));
310  }
311 
324  //
325  // XXX We may want to revisit the behavior when constructing
326  // a path with an empty string ("") to accept it without error and
327  // return EmptyPath.
328  SDF_API explicit SdfPath(const std::string &path);
329 
331 
334 
336  SDF_API size_t GetPathElementCount() const;
337 
339  SDF_API bool IsAbsolutePath() const;
340 
342  SDF_API bool IsAbsoluteRootPath() const;
343 
345  SDF_API bool IsPrimPath() const;
346 
348  SDF_API bool IsAbsoluteRootOrPrimPath() const;
349 
354  SDF_API bool IsRootPrimPath() const;
355 
361  SDF_API bool IsPropertyPath() const;
362 
366  SDF_API bool IsPrimPropertyPath() const;
367 
371  SDF_API bool IsNamespacedPropertyPath() const;
372 
375  SDF_API bool IsPrimVariantSelectionPath() const;
376 
379  SDF_API bool IsPrimOrPrimVariantSelectionPath() const;
380 
383  SDF_API bool ContainsPrimVariantSelection() const;
384 
391  return static_cast<bool>(_propPart);
392  }
393 
396  SDF_API bool ContainsTargetPath() const;
397 
401  SDF_API bool IsRelationalAttributePath() const;
402 
405  SDF_API bool IsTargetPath() const;
406 
408  SDF_API bool IsMapperPath() const;
409 
411  SDF_API bool IsMapperArgPath() const;
412 
414  SDF_API bool IsExpressionPath() const;
415 
417  inline bool IsEmpty() const noexcept {
418  // No need to check _propPart, because it can only be non-null if
419  // _primPart is non-null.
420  return !_primPart;
421  }
422 
428  SDF_API TfToken GetAsToken() const;
429 
439  SDF_API TfToken const &GetToken() const;
440 
446  SDF_API std::string GetAsString() const;
447 
457  SDF_API const std::string &GetString() const;
458 
469  SDF_API const char *GetText() const;
470 
478  SDF_API SdfPathVector GetPrefixes() const;
479 
489  SDF_API void GetPrefixes(SdfPathVector *prefixes) const;
490 
497 
508  SDF_API const std::string &GetName() const;
509 
512  SDF_API const TfToken &GetNameToken() const;
513 
531  SDF_API std::string GetElementString() const;
532 
534  SDF_API TfToken GetElementToken() const;
535 
555  SDF_API SdfPath ReplaceName(TfToken const &newName) const;
556 
569  SDF_API const SdfPath &GetTargetPath() const;
570 
578  SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const;
579 
584  SDF_API
585  std::pair<std::string, std::string> GetVariantSelection() const;
586 
589  SDF_API bool HasPrefix( const SdfPath &prefix ) const;
590 
592 
595 
618  SDF_API SdfPath GetParentPath() const;
619 
627  SDF_API SdfPath GetPrimPath() const;
628 
638 
644  SDF_API SdfPath GetAbsoluteRootOrPrimPath() const;
645 
649  SDF_API SdfPath StripAllVariantSelections() const;
650 
658  SDF_API SdfPath AppendPath(const SdfPath &newSuffix) const;
659 
665  SDF_API SdfPath AppendChild(TfToken const &childName) const;
666 
671  SDF_API SdfPath AppendProperty(TfToken const &propName) const;
672 
677  SDF_API
678  SdfPath AppendVariantSelection(const std::string &variantSet,
679  const std::string &variant) const;
680 
685  SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const;
686 
691  SDF_API
692  SdfPath AppendRelationalAttribute(TfToken const &attrName) const;
693 
697  SDF_API
698  SdfPath ReplaceTargetPath( const SdfPath &newTargetPath ) const;
699 
704  SDF_API SdfPath AppendMapper(const SdfPath &targetPath) const;
705 
710  SDF_API SdfPath AppendMapperArg(TfToken const &argName) const;
711 
715  SDF_API SdfPath AppendExpression() const;
716 
726  SDF_API SdfPath AppendElementString(const std::string &element) const;
727 
729  SDF_API SdfPath AppendElementToken(const TfToken &elementTok) const;
730 
740  SDF_API
741  SdfPath ReplacePrefix(const SdfPath &oldPrefix,
742  const SdfPath &newPrefix,
743  bool fixTargetPaths=true) const;
744 
747  SDF_API SdfPath GetCommonPrefix(const SdfPath &path) const;
748 
764  SDF_API
765  std::pair<SdfPath, SdfPath>
766  RemoveCommonSuffix(const SdfPath& otherPath,
767  bool stopAtRootPrim = false) const;
768 
778  SDF_API SdfPath MakeAbsolutePath(const SdfPath & anchor) const;
779 
792  SDF_API SdfPath MakeRelativePath(const SdfPath & anchor) const;
793 
795 
798 
801  SDF_API static bool IsValidIdentifier(const std::string &name);
802 
805  SDF_API static bool IsValidNamespacedIdentifier(const std::string &name);
806 
810  SDF_API static std::vector<std::string> TokenizeIdentifier(const std::string &name);
811 
815  SDF_API
816  static TfTokenVector TokenizeIdentifierAsTokens(const std::string &name);
817 
820  SDF_API
821  static std::string JoinIdentifier(const std::vector<std::string> &names);
822 
825  SDF_API
826  static std::string JoinIdentifier(const TfTokenVector& names);
827 
832  SDF_API
833  static std::string JoinIdentifier(const std::string &lhs,
834  const std::string &rhs);
835 
840  SDF_API
841  static std::string JoinIdentifier(const TfToken &lhs, const TfToken &rhs);
842 
846  SDF_API
847  static std::string StripNamespace(const std::string &name);
848 
852  SDF_API
853  static TfToken StripNamespace(const TfToken &name);
854 
863  SDF_API
864  static std::pair<std::string, bool>
865  StripPrefixNamespace(const std::string &name,
866  const std::string &matchNamespace);
867 
872  SDF_API
873  static bool IsValidPathString(const std::string &pathString,
874  std::string *errMsg = 0);
875 
877 
880 
883  inline bool operator==(const SdfPath &rhs) const {
884  return _AsInt() == rhs._AsInt();
885  }
886 
891  inline bool operator<(const SdfPath &rhs) const {
892  if (_AsInt() == rhs._AsInt()) {
893  return false;
894  }
895  if (!_primPart || !rhs._primPart) {
896  return !_primPart && rhs._primPart;
897  }
898  // Valid prim parts -- must walk node structure, etc.
899  return _LessThanInternal(*this, rhs);
900  }
901 
902  template <class HashState>
903  friend void TfHashAppend(HashState &h, SdfPath const &path) {
904  // The hash function is pretty sensitive performance-wise. Be
905  // careful making changes here, and run tests.
906  uint32_t primPart, propPart;
907  memcpy(&primPart, &path._primPart, sizeof(primPart));
908  memcpy(&propPart, &path._propPart, sizeof(propPart));
909  h.Append(primPart);
910  h.Append(propPart);
911  }
912 
913  // For hash maps and sets
914  struct Hash {
915  inline size_t operator()(const SdfPath& path) const {
916  return TfHash()(path);
917  }
918  };
919 
920  inline size_t GetHash() const {
921  return Hash()(*this);
922  }
923 
924  // For cases where an unspecified total order that is not stable from
925  // run-to-run is needed.
926  struct FastLessThan {
927  inline bool operator()(const SdfPath& a, const SdfPath& b) const {
928  return a._AsInt() < b._AsInt();
929  }
930  };
931 
933 
936 
943  SDF_API static SdfPathVector
944  GetConciseRelativePaths(const SdfPathVector& paths);
945 
949  SDF_API static void RemoveDescendentPaths(SdfPathVector *paths);
950 
953  SDF_API static void RemoveAncestorPaths(SdfPathVector *paths);
954 
956 
957 private:
958 
959  // This is used for all internal path construction where we do operations
960  // via nodes and then want to return a new path with a resulting prim and
961  // property parts.
962 
963  // Accept rvalues.
964  explicit SdfPath(Sdf_PathPrimNodeHandle &&primNode)
965  : _primPart(std::move(primNode)) {}
966 
967  // Construct from prim & prop parts.
968  SdfPath(Sdf_PathPrimNodeHandle const &primPart,
969  Sdf_PathPropNodeHandle const &propPart)
970  : _primPart(primPart)
971  , _propPart(propPart) {}
972 
973  // Construct from prim & prop node pointers.
974  SdfPath(Sdf_PathNode const *primPart,
975  Sdf_PathNode const *propPart)
976  : _primPart(primPart)
977  , _propPart(propPart) {}
978 
979  friend class Sdf_PathNode;
980  friend class Sdfext_PathAccess;
981  friend class SdfPathAncestorsRange;
982 
983  // converts elements to a string for parsing (unfortunate)
984  static std::string
985  _ElementsToString(bool absolute, const std::vector<std::string> &elements);
986 
987  SdfPath _ReplacePrimPrefix(SdfPath const &oldPrefix,
988  SdfPath const &newPrefix) const;
989 
990  SdfPath _ReplaceTargetPathPrefixes(SdfPath const &oldPrefix,
991  SdfPath const &newPrefix) const;
992 
993  SdfPath _ReplacePropPrefix(SdfPath const &oldPrefix,
994  SdfPath const &newPrefix,
995  bool fixTargetPaths) const;
996 
997  // Helper to implement the uninlined portion of operator<.
998  SDF_API static bool
999  _LessThanInternal(SdfPath const &lhs, SdfPath const &rhs);
1000 
1001  inline uint64_t _AsInt() const {
1002  static_assert(sizeof(*this) == sizeof(uint64_t), "");
1003  uint64_t ret;
1004  std::memcpy(&ret, this, sizeof(*this));
1005  return ret;
1006  }
1007 
1008  friend void swap(SdfPath &lhs, SdfPath &rhs) {
1009  lhs._primPart.swap(rhs._primPart);
1010  lhs._propPart.swap(rhs._propPart);
1011  }
1012 
1013  Sdf_PathPrimNodeHandle _primPart;
1014  Sdf_PathPropNodeHandle _propPart;
1015 
1016 };
1017 
1018 
1036 {
1037 public:
1038 
1039  SdfPathAncestorsRange(const SdfPath& path)
1040  : _path(path) {}
1041 
1042  const SdfPath& GetPath() const { return _path; }
1043 
1044  struct iterator {
1045  using iterator_category = std::forward_iterator_tag;
1046  using value_type = SdfPath;
1047  using difference_type = std::ptrdiff_t;
1048  using reference = const SdfPath&;
1049  using pointer = const SdfPath*;
1050 
1051  iterator(const SdfPath& path) : _path(path) {}
1052 
1053  iterator() = default;
1054 
1055  SDF_API
1056  iterator& operator++();
1057 
1058  const SdfPath& operator*() const { return _path; }
1059 
1060  const SdfPath* operator->() const { return &_path; }
1061 
1062  bool operator==(const iterator& o) const { return _path == o._path; }
1063 
1064  bool operator!=(const iterator& o) const { return _path != o._path; }
1065 
1069  SDF_API friend difference_type
1070  distance(const iterator& first, const iterator& last);
1071 
1072  private:
1073  SdfPath _path;
1074  };
1075 
1076  iterator begin() const { return iterator(_path); }
1077 
1078  iterator end() const { return iterator(); }
1079 
1080 private:
1081  SdfPath _path;
1082 };
1083 
1084 
1085 // Overload hash_value for SdfPath. Used by things like boost::hash.
1086 inline size_t hash_value(SdfPath const &path)
1087 {
1088  return path.GetHash();
1089 }
1090 
1092 SDF_API std::ostream & operator<<( std::ostream &out, const SdfPath &path );
1093 
1094 // Helper for SdfPathFindPrefixedRange & SdfPathFindLongestPrefix. A function
1095 // object that returns an SdfPath const & unchanged.
1096 struct Sdf_PathIdentity {
1097  inline SdfPath const &operator()(SdfPath const &arg) const {
1098  return arg;
1099  }
1100 };
1101 
1108 template <class ForwardIterator, class GetPathFn = Sdf_PathIdentity>
1109 std::pair<ForwardIterator, ForwardIterator>
1110 SdfPathFindPrefixedRange(ForwardIterator begin, ForwardIterator end,
1111  SdfPath const &prefix,
1112  GetPathFn const &getPath = GetPathFn()) {
1113  using IterRef =
1114  typename std::iterator_traits<ForwardIterator>::reference;
1115 
1116  struct Compare {
1117  Compare(GetPathFn const &getPath) : _getPath(getPath) {}
1118  GetPathFn const &_getPath;
1119  bool operator()(IterRef a, SdfPath const &b) const {
1120  return _getPath(a) < b;
1121  }
1122  };
1123 
1124  std::pair<ForwardIterator, ForwardIterator> result;
1125 
1126  // First, use lower_bound to find where \a prefix would go.
1127  result.first = std::lower_bound(begin, end, prefix, Compare(getPath));
1128 
1129  // Next, find end of range starting from the lower bound, using the
1130  // prefixing condition to define the boundary.
1131  result.second = TfFindBoundary(result.first, end,
1132  [&prefix, &getPath](IterRef iterRef) {
1133  return getPath(iterRef).HasPrefix(prefix);
1134  });
1135 
1136  return result;
1137 }
1138 
1139 template <class RandomAccessIterator, class GetPathFn>
1140 RandomAccessIterator
1141 Sdf_PathFindLongestPrefixImpl(RandomAccessIterator begin,
1142  RandomAccessIterator end,
1143  SdfPath const &path,
1144  bool strictPrefix,
1145  GetPathFn const &getPath)
1146 {
1147  using IterRef =
1148  typename std::iterator_traits<RandomAccessIterator>::reference;
1149 
1150  struct Compare {
1151  Compare(GetPathFn const &getPath) : _getPath(getPath) {}
1152  GetPathFn const &_getPath;
1153  bool operator()(IterRef a, SdfPath const &b) const {
1154  return _getPath(a) < b;
1155  }
1156  };
1157 
1158  // Search for the path in [begin, end). If present, return it. If not,
1159  // examine prior element in [begin, end). If none, return end. Else, is it
1160  // a prefix of path? If so, return it. Else find common prefix of that
1161  // element and path and recurse.
1162 
1163  // If empty sequence, return.
1164  if (begin == end)
1165  return end;
1166 
1167  Compare comp(getPath);
1168 
1169  // Search for where this path would lexicographically appear in the range.
1170  RandomAccessIterator result = std::lower_bound(begin, end, path, comp);
1171 
1172  // If we didn't get the end, check to see if we got the path exactly if
1173  // we're not looking for a strict prefix.
1174  if (!strictPrefix && result != end && getPath(*result) == path) {
1175  return result;
1176  }
1177 
1178  // If we got begin (and didn't match in the case of a non-strict prefix)
1179  // then there's no prefix.
1180  if (result == begin) {
1181  return end;
1182  }
1183 
1184  // If the prior element is a prefix, we're done.
1185  if (path.HasPrefix(getPath(*--result))) {
1186  return result;
1187  }
1188 
1189  // Otherwise, find the common prefix of the lexicographical predecessor and
1190  // look for its prefix in the preceding range.
1191  SdfPath newPath = path.GetCommonPrefix(getPath(*result));
1192  auto origEnd = end;
1193  do {
1194  end = result;
1195  result = std::lower_bound(begin, end, newPath, comp);
1196 
1197  if (result != end && getPath(*result) == newPath) {
1198  return result;
1199  }
1200  if (result == begin) {
1201  return origEnd;
1202  }
1203  if (newPath.HasPrefix(getPath(*--result))) {
1204  return result;
1205  }
1206  newPath = newPath.GetCommonPrefix(getPath(*result));
1207  } while (true);
1208 }
1209 
1217 template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
1218  class = typename std::enable_if<
1219  std::is_base_of<
1220  std::random_access_iterator_tag,
1221  typename std::iterator_traits<
1222  RandomAccessIterator>::iterator_category
1223  >::value
1224  >::type
1225  >
1226 RandomAccessIterator
1227 SdfPathFindLongestPrefix(RandomAccessIterator begin,
1228  RandomAccessIterator end,
1229  SdfPath const &path,
1230  GetPathFn const &getPath = GetPathFn())
1231 {
1232  return Sdf_PathFindLongestPrefixImpl(
1233  begin, end, path, /*strictPrefix=*/false, getPath);
1234 }
1235 
1243 template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
1244  class = typename std::enable_if<
1245  std::is_base_of<
1246  std::random_access_iterator_tag,
1247  typename std::iterator_traits<
1248  RandomAccessIterator>::iterator_category
1249  >::value
1250  >::type
1251  >
1252 RandomAccessIterator
1253 SdfPathFindLongestStrictPrefix(RandomAccessIterator begin,
1254  RandomAccessIterator end,
1255  SdfPath const &path,
1256  GetPathFn const &getPath = GetPathFn())
1257 {
1258  return Sdf_PathFindLongestPrefixImpl(
1259  begin, end, path, /*strictPrefix=*/true, getPath);
1260 }
1261 
1262 template <class Iter, class MapParam, class GetPathFn = Sdf_PathIdentity>
1263 Iter
1264 Sdf_PathFindLongestPrefixImpl(
1265  MapParam map, SdfPath const &path, bool strictPrefix,
1266  GetPathFn const &getPath = GetPathFn())
1267 {
1268  // Search for the path in map. If present, return it. If not, examine
1269  // prior element in map. If none, return end. Else, is it a prefix of
1270  // path? If so, return it. Else find common prefix of that element and
1271  // path and recurse.
1272 
1273  const Iter mapEnd = map.end();
1274 
1275  // If empty, return.
1276  if (map.empty())
1277  return mapEnd;
1278 
1279  // Search for where this path would lexicographically appear in the range.
1280  Iter result = map.lower_bound(path);
1281 
1282  // If we didn't get the end, check to see if we got the path exactly if
1283  // we're not looking for a strict prefix.
1284  if (!strictPrefix && result != mapEnd && getPath(*result) == path)
1285  return result;
1286 
1287  // If we got begin (and didn't match in the case of a non-strict prefix)
1288  // then there's no prefix.
1289  if (result == map.begin())
1290  return mapEnd;
1291 
1292  // If the prior element is a prefix, we're done.
1293  if (path.HasPrefix(getPath(*--result)))
1294  return result;
1295 
1296  // Otherwise, find the common prefix of the lexicographical predecessor and
1297  // recurse looking for it or its longest prefix in the preceding range. We
1298  // always pass strictPrefix=false, since now we're operating on prefixes of
1299  // the original caller's path.
1300  return Sdf_PathFindLongestPrefixImpl<Iter, MapParam>(
1301  map, path.GetCommonPrefix(getPath(*result)), /*strictPrefix=*/false,
1302  getPath);
1303 }
1304 
1308 SDF_API
1309 typename std::set<SdfPath>::const_iterator
1310 SdfPathFindLongestPrefix(std::set<SdfPath> const &set, SdfPath const &path);
1311 
1315 template <class T>
1316 typename std::map<SdfPath, T>::const_iterator
1317 SdfPathFindLongestPrefix(std::map<SdfPath, T> const &map, SdfPath const &path)
1318 {
1319  return Sdf_PathFindLongestPrefixImpl<
1320  typename std::map<SdfPath, T>::const_iterator,
1321  std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/false,
1322  TfGet<0>());
1323 }
1324 template <class T>
1325 typename std::map<SdfPath, T>::iterator
1326 SdfPathFindLongestPrefix(std::map<SdfPath, T> &map, SdfPath const &path)
1327 {
1328  return Sdf_PathFindLongestPrefixImpl<
1329  typename std::map<SdfPath, T>::iterator,
1330  std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/false,
1331  TfGet<0>());
1332 }
1333 
1337 SDF_API
1338 typename std::set<SdfPath>::const_iterator
1339 SdfPathFindLongestStrictPrefix(std::set<SdfPath> const &set,
1340  SdfPath const &path);
1341 
1345 template <class T>
1346 typename std::map<SdfPath, T>::const_iterator
1347 SdfPathFindLongestStrictPrefix(
1348  std::map<SdfPath, T> const &map, SdfPath const &path)
1349 {
1350  return Sdf_PathFindLongestPrefixImpl<
1351  typename std::map<SdfPath, T>::const_iterator,
1352  std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/true,
1353  TfGet<0>());
1354 }
1355 template <class T>
1356 typename std::map<SdfPath, T>::iterator
1357 SdfPathFindLongestStrictPrefix(
1358  std::map<SdfPath, T> &map, SdfPath const &path)
1359 {
1360  return Sdf_PathFindLongestPrefixImpl<
1361  typename std::map<SdfPath, T>::iterator,
1362  std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/true,
1363  TfGet<0>());
1364 }
1365 
1366 PXR_NAMESPACE_CLOSE_SCOPE
1367 
1368 // Sdf_PathNode is not public API, but we need to include it here
1369 // so we can inline the ref-counting operations, which must manipulate
1370 // its internal _refCount member.
1371 #include "pxr/usd/sdf/pathNode.h"
1372 
1373 PXR_NAMESPACE_OPEN_SCOPE
1374 
1375 static_assert(Sdf_SizeofPrimPathNode == sizeof(Sdf_PrimPathNode), "");
1376 static_assert(Sdf_SizeofPropPathNode == sizeof(Sdf_PrimPropertyPathNode), "");
1377 
1378 PXR_NAMESPACE_CLOSE_SCOPE
1379 
1380 #endif // PXR_USD_SDF_PATH_H
SDF_API SdfPath AppendMapper(const SdfPath &targetPath) const
Creates a path by appending a mapper element for targetPath.
Range representing a path and ancestors, and providing methods for iterating over them.
Definition: path.h:1035
static SDF_API std::string StripNamespace(const std::string &name)
Returns name stripped of any namespaces.
SDF_API bool IsMapperPath() const
Returns whether the path identifies a connection mapper.
SDF_API bool IsAbsoluteRootPath() const
Return true if this path is the AbsoluteRootPath().
SDF_API bool IsPrimPropertyPath() const
Returns whether the path identifies a prim's property.
SDF_API SdfPath AppendPath(const SdfPath &newSuffix) const
Creates a path by appending a given relative path to this path.
SDF_API SdfPathVector GetPrefixes() const
Returns the prefix paths of this path.
SDF_API bool IsPrimPath() const
Returns whether the path identifies a prim.
SDF_API SdfPath StripAllVariantSelections() const
Create a path by stripping all variant selections from all components of 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...
SDF_API bool IsPrimVariantSelectionPath() const
Returns whether the path identifies a variant selection for a prim.
SDF_API TfToken const & GetToken() const
Return the string representation of this path as a TfToken lvalue.
bool operator==(const SdfPath &rhs) const
Equality operator.
Definition: path.h:883
static SDF_API bool IsValidNamespacedIdentifier(const std::string &name)
Returns whether name is a legal namespaced identifier.
SDF_API SdfPathAncestorsRange GetAncestorsRange() const
Return a range for iterating over the ancestors of this path.
SDF_API const char * GetText() const
Returns the string representation of this path as a c string.
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...
static SDF_API TfTokenVector TokenizeIdentifierAsTokens(const std::string &name)
Tokenizes name by the namespace delimiter.
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.
SDF_API SdfPath GetPrimOrPrimVariantSelectionPath() const
Creates a path by stripping all relational attributes, targets, and properties, leaving the nearest p...
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 TfToken GetAsToken() const
Return the string representation of this path as a TfToken.
static SDF_API void RemoveDescendentPaths(SdfPathVector *paths)
Remove all elements of paths that are prefixed by other elements in paths.
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path's namespace parent.
A user-extensible hashing mechanism for use with runtime hash tables.
Definition: hash.h:447
SDF_API bool IsRelationalAttributePath() const
Returns whether the path identifies a relational attribute.
Token for efficient comparison, assignment, and hashing of known strings.
Definition: token.h:87
static SDF_API SdfPathVector GetConciseRelativePaths(const SdfPathVector &paths)
Given some vector of paths, get a vector of concise unambiguous relative paths.
SDF_API bool IsNamespacedPropertyPath() const
Returns whether the path identifies a namespaced property.
SDF_API const std::string & GetName() const
Returns the name of the prim, property or relational attribute identified by the path.
bool operator<(const SdfPath &rhs) const
Comparison operator.
Definition: path.h:891
SDF_API bool IsAbsoluteRootOrPrimPath() const
Returns whether the path identifies a prim or the absolute root.
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 IsExpressionPath() const
Returns whether the path identifies a connection expression.
SDF_API SdfPath MakeRelativePath(const SdfPath &anchor) const
Returns the relative form of this path using anchor as the relative basis.
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
SDF_API SdfPath ReplaceTargetPath(const SdfPath &newTargetPath) const
Replaces the relational attribute's target path.
SDF_API SdfPath MakeAbsolutePath(const SdfPath &anchor) const
Returns the absolute form of this path using anchor as the relative basis.
SDF_API bool IsPrimOrPrimVariantSelectionPath() const
Return true if this path is a prim path or is a prim variant selection path.
SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const
Returns all the relationship target or connection target paths contained in this path,...
SDF_API size_t GetPathElementCount() const
Returns the number of path elements in this path.
static SDF_API const SdfPath & ReflexiveRelativePath()
The relative path representing "self".
SDF_API std::string GetAsString() const
Return the string representation of this path as a std::string.
SdfPath() noexcept
Constructs the default, empty path.
Definition: path.h:306
std::vector< TfToken > TfTokenVector
Convenience types.
Definition: token.h:442
SDF_API const TfToken & GetNameToken() const
Returns the name of the prim, property or relational attribute identified by the path,...
Function object for retrieving the N'th element of a std::pair or std::tuple.
Definition: stl.h:391
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:288
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.
SDF_API const std::string & GetString() const
Return the string representation of this path as a std::string.
SDF_API bool IsAbsolutePath() const
Returns whether the path is absolute.
GF_API std::ostream & operator<<(std::ostream &, const GfBBox3d &)
Output a GfBBox3d using the format [(range) matrix zeroArea].
SDF_API SdfPath GetPrimPath() const
Creates a path by stripping all relational attributes, targets, properties, and variant selections fr...
static SDF_API std::string JoinIdentifier(const std::vector< std::string > &names)
Join names into a single identifier using the namespace delimiter.
SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const
Creates a path by appending an element for targetPath.
SDF_API bool IsMapperArgPath() const
Returns whether the path identifies a connection mapper arg.
SDF_API SdfPath AppendMapperArg(TfToken const &argName) const
Creates a path by appending an element for argName.
SDF_API SdfPath ReplaceName(TfToken const &newName) const
Return a copy of this path with its final component changed to newName.
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
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 AppendExpression() const
Creates a path by appending an expression element.
SDF_API SdfPath AppendProperty(TfToken const &propName) const
Creates a path by appending an element for propName to 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 AppendRelationalAttribute(TfToken const &attrName) const
Creates a path by appending an element for attrName to this path.
SDF_API TfToken GetElementToken() const
Like GetElementString() but return the value as a TfToken.
SDF_API bool IsRootPrimPath() const
Returns whether the path identifies a root prim.
SDF_API SdfPath AppendElementToken(const TfToken &elementTok) const
Like AppendElementString() but take the element as a TfToken.
SDF_API bool IsPropertyPath() const
Returns whether the path identifies a property.
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 std::pair< SdfPath, SdfPath > RemoveCommonSuffix(const SdfPath &otherPath, bool stopAtRootPrim=false) const
Find and remove the longest common suffix from two paths.
VT_API bool operator==(VtDictionary const &, VtDictionary const &)
Equality comparison.
static SDF_API std::vector< std::string > TokenizeIdentifier(const std::string &name)
Tokenizes name by the namespace delimiter.
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:417
SDF_API const SdfPath & GetTargetPath() const
Returns the relational attribute or mapper target path for this path.
static SDF_API const SdfPath & EmptyPath()
The empty path value, equivalent to SdfPath().
SDF_API bool ContainsPrimVariantSelection() const
Returns whether the path or any of its parent paths identifies a variant selection for a prim.
SDF_API std::pair< std::string, std::string > GetVariantSelection() const
Returns the variant selection for this path, if this is a variant selection path.
SDF_API SdfPath AppendChild(TfToken const &childName) const
Creates a path by appending an element for childName to this path.
static SDF_API void RemoveAncestorPaths(SdfPathVector *paths)
Remove all elements of paths that prefix other elements in paths.
TfToken class for efficient string referencing and hashing, plus conversions to and from stl string c...
static SDF_API bool IsValidIdentifier(const std::string &name)
Returns whether name is a legal identifier for any path component.
SDF_API bool IsTargetPath() const
Returns whether the path identifies a relationship or connection target.
SDF_API SdfPath GetAbsoluteRootOrPrimPath() const
Creates a path by stripping all properties and relational attributes from this path,...
bool ContainsPropertyElements() const
Return true if this path contains any property elements, false otherwise.
Definition: path.h:390