All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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;
49 
50 // Ref-counting pointer to a path node.
51 // Intrusive ref-counts are used to keep the size of SdfPath
52 // the same as a raw pointer. (shared_ptr, by comparison,
53 // is the size of two pointers.)
54 
55 typedef boost::intrusive_ptr<const Sdf_PathNode> Sdf_PathNodeConstRefPtr;
56 
57 void intrusive_ptr_add_ref(Sdf_PathNode const *);
58 void intrusive_ptr_release(Sdf_PathNode const *);
59 
60 // Tags used for the pools of path nodes.
61 struct Sdf_PathPrimTag;
62 struct Sdf_PathPropTag;
63 
64 // These are validated below.
65 static constexpr size_t Sdf_SizeofPrimPathNode = sizeof(void *) * 3;
66 static constexpr size_t Sdf_SizeofPropPathNode = sizeof(void *) * 3;
67 
68 using Sdf_PathPrimPartPool = Sdf_Pool<
69  Sdf_PathPrimTag, Sdf_SizeofPrimPathNode, /*regionBits=*/8>;
70 
71 using Sdf_PathPropPartPool = Sdf_Pool<
72  Sdf_PathPropTag, Sdf_SizeofPropPathNode, /*regionBits=*/8>;
73 
74 using Sdf_PathPrimHandle = Sdf_PathPrimPartPool::Handle;
75 using Sdf_PathPropHandle = Sdf_PathPropPartPool::Handle;
76 
77 // This handle class wraps up the raw Prim/PropPartPool handles.
78 template <class Handle, bool Counted, class PathNode=Sdf_PathNode const>
79 struct Sdf_PathNodeHandleImpl {
80 private:
81  typedef Sdf_PathNodeHandleImpl this_type;
82 
83 public:
84  constexpr Sdf_PathNodeHandleImpl() noexcept {};
85 
86  explicit
87  Sdf_PathNodeHandleImpl(Sdf_PathNode const *p, bool add_ref = true)
88  : _poolHandle(Handle::GetHandle(reinterpret_cast<char const *>(p))) {
89  if (p && add_ref) {
90  _AddRef(p);
91  }
92  }
93 
94  explicit
95  Sdf_PathNodeHandleImpl(Handle h, bool add_ref = true)
96  : _poolHandle(h) {
97  if (h && add_ref) {
98  _AddRef();
99  }
100  }
101 
102  Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl const &rhs)
103  : _poolHandle(rhs._poolHandle) {
104  if (_poolHandle) {
105  _AddRef();
106  }
107  }
108 
109  ~Sdf_PathNodeHandleImpl() {
110  if (_poolHandle) {
111  _DecRef();
112  }
113  }
114 
115  Sdf_PathNodeHandleImpl &
116  operator=(Sdf_PathNodeHandleImpl const &rhs) {
117  if (Counted && *this == rhs) {
118  return *this;
119  }
120  this_type(rhs).swap(*this);
121  return *this;
122  }
123 
124  Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl &&rhs) noexcept
125  : _poolHandle(rhs._poolHandle) {
126  rhs._poolHandle = nullptr;
127  }
128 
129  Sdf_PathNodeHandleImpl &
130  operator=(Sdf_PathNodeHandleImpl &&rhs) noexcept {
131  this_type(std::move(rhs)).swap(*this);
132  return *this;
133  }
134 
135  Sdf_PathNodeHandleImpl &
136  operator=(Sdf_PathNode const *rhs) noexcept {
137  this_type(rhs).swap(*this);
138  return *this;
139  }
140 
141  void reset() noexcept {
142  _poolHandle = Handle { nullptr };
143  }
144 
145  Sdf_PathNode const *
146  get() const noexcept {
147  return reinterpret_cast<Sdf_PathNode *>(_poolHandle.GetPtr());
148  }
149 
150  Sdf_PathNode const &
151  operator*() const {
152  return *get();
153  }
154 
155  Sdf_PathNode const *
156  operator->() const {
157  return get();
158  }
159 
160  explicit operator bool() const noexcept {
161  return static_cast<bool>(_poolHandle);
162  }
163 
164  void swap(Sdf_PathNodeHandleImpl &rhs) noexcept {
165  _poolHandle.swap(rhs._poolHandle);
166  }
167 
168  inline bool operator==(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
169  return _poolHandle == rhs._poolHandle;
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 private:
178 
179  void _AddRef(Sdf_PathNode const *p) const {
180  if (Counted) {
181  intrusive_ptr_add_ref(p);
182  }
183  }
184 
185  void _AddRef() const {
186  _AddRef(get());
187  }
188 
189  void _DecRef() const {
190  if (Counted) {
191  intrusive_ptr_release(get());
192  }
193  }
194 
195  Handle _poolHandle { nullptr };
196 };
197 
198 using Sdf_PathPrimNodeHandle =
199  Sdf_PathNodeHandleImpl<Sdf_PathPrimHandle, /*Counted=*/true>;
200 
201 using Sdf_PathPropNodeHandle =
202  Sdf_PathNodeHandleImpl<Sdf_PathPropHandle, /*Counted=*/false>;
203 
204 
206 typedef std::set<class SdfPath> SdfPathSet;
208 typedef std::vector<class SdfPath> SdfPathVector;
209 
210 // Tell VtValue that SdfPath is cheap to copy.
211 VT_TYPE_IS_CHEAP_TO_COPY(class SdfPath);
212 
287 class SdfPath : boost::totally_ordered<SdfPath>
288 {
289 public:
291  SDF_API static const SdfPath & EmptyPath();
292 
295  SDF_API static const SdfPath & AbsoluteRootPath();
296 
298  SDF_API static const SdfPath & ReflexiveRelativePath();
299 
302 
305  constexpr SdfPath() = default;
306 
319  //
320  // XXX We may want to revisit the behavior when constructing
321  // a path with an empty string ("") to accept it without error and
322  // return EmptyPath.
323  SDF_API explicit SdfPath(const std::string &path);
324 
326 
329 
331  SDF_API size_t GetPathElementCount() const;
332 
334  SDF_API bool IsAbsolutePath() const;
335 
337  SDF_API bool IsPrimPath() const;
338 
340  SDF_API bool IsAbsoluteRootOrPrimPath() const;
341 
346  SDF_API bool IsRootPrimPath() const;
347 
353  SDF_API bool IsPropertyPath() const;
354 
358  SDF_API bool IsPrimPropertyPath() const;
359 
363  SDF_API bool IsNamespacedPropertyPath() const;
364 
367  SDF_API bool IsPrimVariantSelectionPath() const;
368 
371  SDF_API bool IsPrimOrPrimVariantSelectionPath() const;
372 
375  SDF_API bool ContainsPrimVariantSelection() const;
376 
383  return static_cast<bool>(_propPart);
384  }
385 
388  SDF_API bool ContainsTargetPath() const;
389 
393  SDF_API bool IsRelationalAttributePath() const;
394 
397  SDF_API bool IsTargetPath() const;
398 
400  SDF_API bool IsMapperPath() const;
401 
403  SDF_API bool IsMapperArgPath() const;
404 
406  SDF_API bool IsExpressionPath() const;
407 
409  inline bool IsEmpty() const noexcept {
410  // No need to check _propPart, because it can only be non-null if
411  // _primPart is non-null.
412  return !_primPart;
413  }
414 
416  SDF_API TfToken const &GetToken() const;
417 
419  SDF_API const std::string &GetString() const;
420 
422  SDF_API const char *GetText() const;
423 
428  SDF_API SdfPathVector GetPrefixes() const;
429 
436  SDF_API void GetPrefixes(SdfPathVector *prefixes) const;
437 
448  SDF_API const std::string &GetName() const;
449 
452  SDF_API const TfToken &GetNameToken() const;
453 
471  SDF_API std::string GetElementString() const;
472 
474  SDF_API TfToken GetElementToken() const;
475 
495  SDF_API SdfPath ReplaceName(TfToken const &newName) const;
496 
509  SDF_API const SdfPath &GetTargetPath() const;
510 
518  SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const;
519 
524  SDF_API
525  std::pair<std::string, std::string> GetVariantSelection() const;
526 
529  SDF_API bool HasPrefix( const SdfPath &prefix ) const;
530 
532 
535 
554  SDF_API SdfPath GetParentPath() const;
555 
563  SDF_API SdfPath GetPrimPath() const;
564 
573  SDF_API SdfPath GetPrimOrPrimVariantSelectionPath() const;
574 
580  SDF_API SdfPath GetAbsoluteRootOrPrimPath() const;
581 
585  SDF_API SdfPath StripAllVariantSelections() const;
586 
594  SDF_API SdfPath AppendPath(const SdfPath &newSuffix) const;
595 
601  SDF_API SdfPath AppendChild(TfToken const &childName) const;
602 
607  SDF_API SdfPath AppendProperty(TfToken const &propName) const;
608 
613  SDF_API
614  SdfPath AppendVariantSelection(const std::string &variantSet,
615  const std::string &variant) const;
616 
621  SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const;
622 
627  SDF_API
628  SdfPath AppendRelationalAttribute(TfToken const &attrName) const;
629 
633  SDF_API
634  SdfPath ReplaceTargetPath( const SdfPath &newTargetPath ) const;
635 
640  SDF_API SdfPath AppendMapper(const SdfPath &targetPath) const;
641 
646  SDF_API SdfPath AppendMapperArg(TfToken const &argName) const;
647 
651  SDF_API SdfPath AppendExpression() const;
652 
662  SDF_API SdfPath AppendElementString(const std::string &element) const;
663 
665  SDF_API SdfPath AppendElementToken(const TfToken &elementTok) const;
666 
676  SDF_API
677  SdfPath ReplacePrefix(const SdfPath &oldPrefix,
678  const SdfPath &newPrefix,
679  bool fixTargetPaths=true) const;
680 
683  SDF_API SdfPath GetCommonPrefix(const SdfPath &path) const;
684 
700  SDF_API
701  std::pair<SdfPath, SdfPath>
702  RemoveCommonSuffix(const SdfPath& otherPath,
703  bool stopAtRootPrim = false) const;
704 
714  SDF_API SdfPath MakeAbsolutePath(const SdfPath & anchor) const;
715 
728  SDF_API SdfPath MakeRelativePath(const SdfPath & anchor) const;
729 
731 
734 
737  SDF_API static bool IsValidIdentifier(const std::string &name);
738 
741  SDF_API static bool IsValidNamespacedIdentifier(const std::string &name);
742 
746  SDF_API static std::vector<std::string> TokenizeIdentifier(const std::string &name);
747 
751  SDF_API
752  static TfTokenVector TokenizeIdentifierAsTokens(const std::string &name);
753 
756  SDF_API
757  static std::string JoinIdentifier(const std::vector<std::string> &names);
758 
761  SDF_API
762  static std::string JoinIdentifier(const TfTokenVector& names);
763 
768  SDF_API
769  static std::string JoinIdentifier(const std::string &lhs,
770  const std::string &rhs);
771 
776  SDF_API
777  static std::string JoinIdentifier(const TfToken &lhs, const TfToken &rhs);
778 
782  SDF_API
783  static std::string StripNamespace(const std::string &name);
784 
788  SDF_API
789  static TfToken StripNamespace(const TfToken &name);
790 
799  SDF_API
800  static std::pair<std::string, bool>
801  StripPrefixNamespace(const std::string &name,
802  const std::string &matchNamespace);
803 
808  SDF_API
809  static bool IsValidPathString(const std::string &pathString,
810  std::string *errMsg = 0);
811 
813 
816 
819  inline bool operator==(const SdfPath &rhs) const {
820  return _AsInt() == rhs._AsInt();
821  }
822 
827  inline bool operator<(const SdfPath &rhs) const {
828  if (_AsInt() == rhs._AsInt()) {
829  return false;
830  }
831  if (!_primPart || !rhs._primPart) {
832  return !_primPart && rhs._primPart;
833  }
834  // Valid prim parts -- must walk node structure, etc.
835  return _LessThanInternal(*this, rhs);
836  }
837 
838  // For hash maps and sets
839  struct Hash {
840  inline size_t operator()(const SdfPath& path) const {
841  // The hash function is pretty sensitive performance-wise. Be
842  // careful making changes here, and run tests.
843  uint32_t primPart, propPart;
844  memcpy(&primPart, &path._primPart, sizeof(primPart));
845  memcpy(&propPart, &path._propPart, sizeof(propPart));
846 
847  // Important considerations here:
848  // - It must be fast to execute.
849  // - It must do well in hash tables that find indexes by taking
850  // the remainder divided by a prime number of buckets.
851  // - It must do well in hash tables that find indexes by taking
852  // just the low-order bits.
853 
854  // This hash function maps the (primPart, propPart) pair to a single
855  // value by using triangular numbers. So the first few path hash
856  // values would look like this, for primPart as X increasing
857  // left-to-right and for propPart as Y increasing top-to-bottom.
858  //
859  // 0 2 5 9 14 20
860  // 1 4 8 13 19 26
861  // 3 7 12 18 25 33
862  // 6 11 17 24 32 41
863  // 10 16 23 31 40 50
864  // 15 22 30 39 49 60
865 
866  uint64_t x = primPart >> 8;
867  uint64_t y = x + (propPart >> 8);
868  return x + (y * (y + 1)) / 2;
869  }
870  };
871 
872  inline size_t GetHash() const {
873  return Hash()(*this);
874  }
875 
876  // For cases where an unspecified total order that is not stable from
877  // run-to-run is needed.
878  struct FastLessThan {
879  inline bool operator()(const SdfPath& a, const SdfPath& b) const {
880  return a._AsInt() < b._AsInt();
881  }
882  };
883 
885 
888 
895  SDF_API static SdfPathVector
896  GetConciseRelativePaths(const SdfPathVector& paths);
897 
901  SDF_API static void RemoveDescendentPaths(SdfPathVector *paths);
902 
905  SDF_API static void RemoveAncestorPaths(SdfPathVector *paths);
906 
908 
909 private:
910 
911  // This is used for all internal path construction where we do operations
912  // via nodes and then want to return a new path with a resulting prim and
913  // property parts.
914 
915  // Accept rvalues.
916  explicit SdfPath(Sdf_PathPrimNodeHandle &&primNode)
917  : _primPart(std::move(primNode)) {}
918 
919  // Construct from prim & prop parts.
920  SdfPath(Sdf_PathPrimNodeHandle const &primPart,
921  Sdf_PathPropNodeHandle const &propPart)
922  : _primPart(primPart)
923  , _propPart(propPart) {}
924 
925  // Construct from prim & prop node pointers.
926  SdfPath(Sdf_PathNode const *primPart,
927  Sdf_PathNode const *propPart)
928  : _primPart(primPart)
929  , _propPart(propPart) {}
930 
931  friend class Sdf_PathNode;
932  friend class Sdfext_PathAccess;
933 
934  // converts elements to a string for parsing (unfortunate)
935  static std::string
936  _ElementsToString(bool absolute, const std::vector<std::string> &elements);
937 
938  SdfPath _ReplacePrimPrefix(SdfPath const &oldPrefix,
939  SdfPath const &newPrefix) const;
940 
941  SdfPath _ReplaceTargetPathPrefixes(SdfPath const &oldPrefix,
942  SdfPath const &newPrefix) const;
943 
944  SdfPath _ReplacePropPrefix(SdfPath const &oldPrefix,
945  SdfPath const &newPrefix,
946  bool fixTargetPaths) const;
947 
948  // Helper to implement the uninlined portion of operator<.
949  SDF_API static bool
950  _LessThanInternal(SdfPath const &lhs, SdfPath const &rhs);
951 
952  inline uint64_t _AsInt() const {
953  static_assert(sizeof(*this) == sizeof(uint64_t), "");
954  uint64_t ret;
955  std::memcpy(&ret, this, sizeof(*this));
956  return ret;
957  }
958 
959  friend void swap(SdfPath &lhs, SdfPath &rhs) {
960  lhs._primPart.swap(rhs._primPart);
961  lhs._propPart.swap(rhs._propPart);
962  }
963 
964  Sdf_PathPrimNodeHandle _primPart;
965  Sdf_PathPropNodeHandle _propPart;
966 
967 };
968 
969 // Overload hash_value for SdfPath. Used by things like boost::hash.
970 inline size_t hash_value(SdfPath const &path)
971 {
972  return path.GetHash();
973 }
974 
976 SDF_API std::ostream & operator<<( std::ostream &out, const SdfPath &path );
977 
978 // Helper for SdfPathFindPrefixedRange & SdfPathFindLongestPrefix. A function
979 // object that returns an SdfPath const & unchanged.
980 struct Sdf_PathIdentity {
981  inline SdfPath const &operator()(SdfPath const &arg) const {
982  return arg;
983  }
984 };
985 
992 template <class ForwardIterator, class GetPathFn = Sdf_PathIdentity>
993 std::pair<ForwardIterator, ForwardIterator>
994 SdfPathFindPrefixedRange(ForwardIterator begin, ForwardIterator end,
995  SdfPath const &prefix,
996  GetPathFn const &getPath = GetPathFn()) {
997  using IterRef =
998  typename std::iterator_traits<ForwardIterator>::reference;
999 
1000  struct Compare {
1001  Compare(GetPathFn const &getPath) : _getPath(getPath) {}
1002  GetPathFn const &_getPath;
1003  bool operator()(IterRef a, SdfPath const &b) const {
1004  return _getPath(a) < b;
1005  }
1006  };
1007 
1008  std::pair<ForwardIterator, ForwardIterator> result;
1009 
1010  // First, use lower_bound to find where \a prefix would go.
1011  result.first = std::lower_bound(begin, end, prefix, Compare(getPath));
1012 
1013  // Next, find end of range starting from the lower bound, using the
1014  // prefixing condition to define the boundary.
1015  result.second = TfFindBoundary(result.first, end,
1016  [&prefix, &getPath](IterRef iterRef) {
1017  return getPath(iterRef).HasPrefix(prefix);
1018  });
1019 
1020  return result;
1021 }
1022 
1023 template <class RandomAccessIterator, class GetPathFn>
1024 RandomAccessIterator
1025 Sdf_PathFindLongestPrefixImpl(RandomAccessIterator begin,
1026  RandomAccessIterator end,
1027  SdfPath const &path,
1028  bool strictPrefix,
1029  GetPathFn const &getPath)
1030 {
1031  using IterRef =
1032  typename std::iterator_traits<RandomAccessIterator>::reference;
1033 
1034  struct Compare {
1035  Compare(GetPathFn const &getPath) : _getPath(getPath) {}
1036  GetPathFn const &_getPath;
1037  bool operator()(IterRef a, SdfPath const &b) const {
1038  return _getPath(a) < b;
1039  }
1040  };
1041 
1042  // Search for the path in [begin, end). If present, return it. If not,
1043  // examine prior element in [begin, end). If none, return end. Else, is it
1044  // a prefix of path? If so, return it. Else find common prefix of that
1045  // element and path and recurse.
1046 
1047  // If empty sequence, return.
1048  if (begin == end)
1049  return end;
1050 
1051  // Search for where this path would lexicographically appear in the range.
1052  RandomAccessIterator result =
1053  std::lower_bound(begin, end, path, Compare(getPath));
1054 
1055  // If we didn't get the end, check to see if we got the path exactly if
1056  // we're not looking for a strict prefix.
1057  if (!strictPrefix && result != end && getPath(*result) == path)
1058  return result;
1059 
1060  // If we got begin (and didn't match in the case of a non-strict prefix)
1061  // then there's no prefix.
1062  if (result == begin)
1063  return end;
1064 
1065  // If the prior element is a prefix, we're done.
1066  if (path.HasPrefix(getPath(*--result)))
1067  return result;
1068 
1069  // Otherwise, find the common prefix of the lexicographical predecessor and
1070  // recurse looking for it or its longest prefix in the preceding range. We
1071  // always pass strictPrefix=false, since now we're operating on prefixes of
1072  // the original caller's path.
1073  RandomAccessIterator final =
1074  Sdf_PathFindLongestPrefixImpl(
1075  begin, result, path.GetCommonPrefix(getPath(*result)),
1076  /*strictPrefix=*/ false, getPath);
1077 
1078  // If the recursion failed, promote the recursive call's end to our end.
1079  return final == result ? end : final;
1080 }
1081 
1089 template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
1090  class = typename std::enable_if<
1091  std::is_base_of<
1092  std::random_access_iterator_tag,
1093  typename std::iterator_traits<
1094  RandomAccessIterator>::iterator_category
1095  >::value
1096  >::type
1097  >
1098 RandomAccessIterator
1099 SdfPathFindLongestPrefix(RandomAccessIterator begin,
1100  RandomAccessIterator end,
1101  SdfPath const &path,
1102  GetPathFn const &getPath = GetPathFn())
1103 {
1104  return Sdf_PathFindLongestPrefixImpl(
1105  begin, end, path, /*strictPrefix=*/false, getPath);
1106 }
1107 
1115 template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
1116  class = typename std::enable_if<
1117  std::is_base_of<
1118  std::random_access_iterator_tag,
1119  typename std::iterator_traits<
1120  RandomAccessIterator>::iterator_category
1121  >::value
1122  >::type
1123  >
1124 RandomAccessIterator
1125 SdfPathFindLongestStrictPrefix(RandomAccessIterator begin,
1126  RandomAccessIterator end,
1127  SdfPath const &path,
1128  GetPathFn const &getPath = GetPathFn())
1129 {
1130  return Sdf_PathFindLongestPrefixImpl(
1131  begin, end, path, /*strictPrefix=*/true, getPath);
1132 }
1133 
1134 template <class Iter, class MapParam, class GetPathFn = Sdf_PathIdentity>
1135 Iter
1136 Sdf_PathFindLongestPrefixImpl(
1137  MapParam map, SdfPath const &path, bool strictPrefix,
1138  GetPathFn const &getPath = GetPathFn())
1139 {
1140  // Search for the path in map. If present, return it. If not, examine
1141  // prior element in map. If none, return end. Else, is it a prefix of
1142  // path? If so, return it. Else find common prefix of that element and
1143  // path and recurse.
1144 
1145  const Iter mapEnd = map.end();
1146 
1147  // If empty, return.
1148  if (map.empty())
1149  return mapEnd;
1150 
1151  // Search for where this path would lexicographically appear in the range.
1152  Iter result = map.lower_bound(path);
1153 
1154  // If we didn't get the end, check to see if we got the path exactly if
1155  // we're not looking for a strict prefix.
1156  if (!strictPrefix && result != mapEnd && getPath(*result) == path)
1157  return result;
1158 
1159  // If we got begin (and didn't match in the case of a non-strict prefix)
1160  // then there's no prefix.
1161  if (result == map.begin())
1162  return mapEnd;
1163 
1164  // If the prior element is a prefix, we're done.
1165  if (path.HasPrefix(getPath(*--result)))
1166  return result;
1167 
1168  // Otherwise, find the common prefix of the lexicographical predecessor and
1169  // recurse looking for it or its longest prefix in the preceding range. We
1170  // always pass strictPrefix=false, since now we're operating on prefixes of
1171  // the original caller's path.
1172  return Sdf_PathFindLongestPrefixImpl<Iter, MapParam>(
1173  map, path.GetCommonPrefix(getPath(*result)), /*strictPrefix=*/false,
1174  getPath);
1175 }
1176 
1180 SDF_API
1181 typename std::set<SdfPath>::const_iterator
1182 SdfPathFindLongestPrefix(std::set<SdfPath> const &set, SdfPath const &path);
1183 
1187 template <class T>
1188 typename std::map<SdfPath, T>::const_iterator
1189 SdfPathFindLongestPrefix(std::map<SdfPath, T> const &map, SdfPath const &path)
1190 {
1191  return Sdf_PathFindLongestPrefixImpl<
1192  typename std::map<SdfPath, T>::const_iterator,
1193  std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/false,
1194  TfGet<0>());
1195 }
1196 template <class T>
1197 typename std::map<SdfPath, T>::iterator
1198 SdfPathFindLongestPrefix(std::map<SdfPath, T> &map, SdfPath const &path)
1199 {
1200  return Sdf_PathFindLongestPrefixImpl<
1201  typename std::map<SdfPath, T>::iterator,
1202  std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/false,
1203  TfGet<0>());
1204 }
1205 
1209 SDF_API
1210 typename std::set<SdfPath>::const_iterator
1211 SdfPathFindLongestStrictPrefix(std::set<SdfPath> const &set,
1212  SdfPath const &path);
1213 
1217 template <class T>
1218 typename std::map<SdfPath, T>::const_iterator
1219 SdfPathFindLongestStrictPrefix(
1220  std::map<SdfPath, T> const &map, SdfPath const &path)
1221 {
1222  return Sdf_PathFindLongestPrefixImpl<
1223  typename std::map<SdfPath, T>::const_iterator,
1224  std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/true,
1225  TfGet<0>());
1226 }
1227 template <class T>
1228 typename std::map<SdfPath, T>::iterator
1229 SdfPathFindLongestStrictPrefix(
1230  std::map<SdfPath, T> &map, SdfPath const &path)
1231 {
1232  return Sdf_PathFindLongestPrefixImpl<
1233  typename std::map<SdfPath, T>::iterator,
1234  std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/true,
1235  TfGet<0>());
1236 }
1237 
1238 PXR_NAMESPACE_CLOSE_SCOPE
1239 
1240 // Sdf_PathNode is not public API, but we need to include it here
1241 // so we can inline the ref-counting operations, which must manipulate
1242 // its internal _refCount member.
1243 #include "pxr/usd/sdf/pathNode.h"
1244 
1245 PXR_NAMESPACE_OPEN_SCOPE
1246 
1247 static_assert(Sdf_SizeofPrimPathNode == sizeof(Sdf_PrimPathNode), "");
1248 static_assert(Sdf_SizeofPropPathNode == sizeof(Sdf_PrimPropertyPathNode), "");
1249 
1250 PXR_NAMESPACE_CLOSE_SCOPE
1251 
1252 #endif // PXR_USD_SDF_PATH_H
SDF_API TfToken const & GetToken() const
Returns the string representation of this path as a TfToken.
SDF_API SdfPathVector GetPrefixes() const
Returns the prefix paths of this path.
SDF_API bool IsMapperPath() const
Returns whether the path identifies a connection mapper.
static SDF_API std::string StripNamespace(const std::string &name)
Returns name stripped of any namespaces.
bool operator<(const SdfPath &rhs) const
Comparison operator.
Definition: path.h:827
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 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 AppendProperty(TfToken const &propName) const
Creates a path by appending an element for propName to this path.
SDF_API bool IsTargetPath() const
Returns whether the path identifies a relationship or connection target.
SDF_API bool ContainsTargetPath() const
Return true if this path is or has a prefix that&#39;s a target path or a mapper path.
SDF_API SdfPath AppendMapperArg(TfToken const &argName) const
Creates a path by appending an element for argName.
bool ContainsPropertyElements() const
Return true if this path contains any property elements, false otherwise.
Definition: path.h:382
SDF_API SdfPath ReplaceTargetPath(const SdfPath &newTargetPath) const
Replaces the relational attribute&#39;s target 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 GetParentPath() const
Return the path that identifies this path&#39;s namespace parent.
SDF_API bool IsPrimPath() const
Returns whether the path identifies a prim.
bool operator==(const SdfPath &rhs) const
Equality operator.
Definition: path.h:819
static SDF_API bool IsValidNamespacedIdentifier(const std::string &name)
Returns whether name is a legal namespaced identifier.
SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const
Creates a path by appending an element for targetPath.
SDF_API SdfPath GetAbsoluteRootOrPrimPath() const
Creates a path by stripping all properties and relational attributes from this path, leaving the path to the containing prim.
SDF_API bool IsAbsolutePath() const
Returns whether the path is absolute.
constexpr SdfPath()=default
Constructs the default, empty path.
static SDF_API TfTokenVector TokenizeIdentifierAsTokens(const std::string &name)
Tokenizes name by the namespace delimiter.
SDF_API const TfToken & GetNameToken() const
Returns the name of the prim, property or relational attribute identified by the path, as a token.
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 AppendChild(TfToken const &childName) const
Creates a path by appending an element for childName to this path.
SDF_API const std::string & GetName() const
Returns the name of the prim, property or relational attribute identified by the path.
SDF_API SdfPath GetPrimPath() const
Creates a path by stripping all relational attributes, targets, properties, and variant selections fr...
SDF_API size_t GetPathElementCount() const
Returns the number of path elements in this path.
static SDF_API void RemoveDescendentPaths(SdfPathVector *paths)
Remove all elements of paths that are prefixed by other elements in paths.
SDF_API bool IsRelationalAttributePath() const
Returns whether the path identifies a relational attribute.
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...
Token for efficient comparison, assignment, and hashing of known strings.
Definition: token.h:89
static SDF_API SdfPathVector GetConciseRelativePaths(const SdfPathVector &paths)
Given some vector of paths, get a vector of concise unambiguous relative paths.
SDF_API bool IsPrimVariantSelectionPath() const
Returns whether the path identifies a variant selection for a prim.
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 AppendElementToken(const TfToken &elementTok) const
Like AppendElementString() but take the element as a TfToken.
SDF_API SdfPath ReplaceName(TfToken const &newName) const
Return a copy of this path with its final component changed to newName.
SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const
Returns all the relationship target or connection target paths contained in this path, and recursively all the target paths contained in those target paths in reverse depth-first order.
static SDF_API const SdfPath & ReflexiveRelativePath()
The relative path representing &quot;self&quot;.
SDF_API TfToken GetElementToken() const
Like GetElementString() but return the value as a TfToken.
std::vector< TfToken > TfTokenVector
Convenience types.
Definition: token.h:433
SDF_API bool IsMapperArgPath() const
Returns whether the path identifies a connection mapper arg.
Function object for retrieving the N&#39;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:287
SDF_API bool IsPropertyPath() const
Returns whether the path identifies a property.
SDF_API const std::string & GetString() const
Returns the string representation of this path as a std::string.
GF_API std::ostream & operator<<(std::ostream &, const GfBBox3d &)
Output a GfBBox3d using the format [(range) matrix zeroArea].
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 IsPrimPropertyPath() const
Returns whether the path identifies a prim&#39;s property.
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 AppendPath(const SdfPath &newSuffix) const
Creates a path by appending a given relative path to this path.
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.
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
SDF_API bool IsAbsoluteRootOrPrimPath() const
Returns whether the path identifies a prim or the absolute root.
SDF_API std::pair< SdfPath, SdfPath > RemoveCommonSuffix(const SdfPath &otherPath, bool stopAtRootPrim=false) const
Find and remove the longest common suffix from two paths.
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 const SdfPath & GetTargetPath() const
Returns the relational attribute or mapper target path for this path.
SDF_API SdfPath MakeAbsolutePath(const SdfPath &anchor) const
Returns the absolute form of this path using anchor as the relative basis.
VT_API bool operator==(VtDictionary const &, VtDictionary const &)
Equality comparison.
SDF_API SdfPath AppendRelationalAttribute(TfToken const &attrName) const
Creates a path by appending an element for attrName to this path.
SDF_API bool IsRootPrimPath() const
Returns whether the path identifies a root prim.
SDF_API std::string GetElementString() const
Returns an ascii representation of the &quot;terminal&quot; element of this path, which can be used to reconstr...
static SDF_API std::vector< std::string > TokenizeIdentifier(const std::string &name)
Tokenizes name by the namespace delimiter.
SDF_API SdfPath AppendExpression() const
Creates a path by appending an expression element.
SDF_API SdfPath AppendElementString(const std::string &element) const
Creates a path by extracting and appending an element from the given ascii element encoding...
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:409
static SDF_API const SdfPath & EmptyPath()
The empty path value, equivalent to SdfPath().
SDF_API SdfPath GetPrimOrPrimVariantSelectionPath() const
Creates a path by stripping all relational attributes, targets, and properties, leaving the nearest p...
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 SdfPath AppendMapper(const SdfPath &targetPath) const
Creates a path by appending a mapper element for targetPath.
static SDF_API void RemoveAncestorPaths(SdfPathVector *paths)
Remove all elements of paths that prefix other elements in paths.
SDF_API const char * GetText() const
Returns the string representation of this path as a c string.
static SDF_API bool IsValidIdentifier(const std::string &name)
Returns whether name is a legal identifier for any path component.
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 StripAllVariantSelections() const
Create a path by stripping all variant selections from all components of this path, leaving a path with no embedded variant selections.