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 #include "pxr/pxr.h"
25 #include "pxr/usd/sdf/path.h"
26 #include "pxr/usd/sdf/pathNode.h"
27 #include "pxr/usd/sdf/pathParser.h"
28
29 #include "pxr/base/vt/value.h"
30
31 #include "pxr/base/arch/hints.h"
32 #include "pxr/base/tf/iterator.h"
33 #include "pxr/base/tf/staticData.h"
34 #include "pxr/base/tf/stringUtils.h"
35 #include "pxr/base/tf/mallocTag.h"
36 #include "pxr/base/tf/stl.h"
37 #include "pxr/base/tf/type.h"
38
39 #include "pxr/base/trace/trace.h"
40
41 #include <algorithm>
42 #include <ostream>
43
44 using std::pair;
45 using std::string;
46 using std::vector;
47
48 PXR_NAMESPACE_OPEN_SCOPE
49
50 static inline bool _IsValidIdentifier(TfToken const &name);
51
52 // XXX: Enable this define to make bad path strings
53 // cause runtime errors. This can be useful when trying to track down cases
54 // of bad path strings originating from python code.
55 // #define PARSE_ERRORS_ARE_ERRORS
56
TF_REGISTRY_FUNCTION(TfType)57 TF_REGISTRY_FUNCTION(TfType)
58 {
59 TfType::Define<SdfPath>();
60 TfType::Define< vector<SdfPath> >()
61 .Alias(TfType::GetRoot(), "vector<SdfPath>");
62 }
63
SdfPath(const std::string & path)64 SdfPath::SdfPath(const std::string &path) {
65 TfAutoMallocTag2 tag("Sdf", "SdfPath::SdfPath(string)");
66 TRACE_FUNCTION();
67
68 Sdf_PathParserContext context;
69
70 // Initialize the scanner, allowing it to be reentrant.
71 pathYylex_init(&context.scanner);
72
73 yy_buffer_state *b = pathYy_scan_bytes(path.c_str(), path.size(),
74 context.scanner);
75 if( pathYyparse(&context) != 0 ) {
76 #ifdef PARSE_ERRORS_ARE_ERRORS
77 TF_RUNTIME_ERROR("Ill-formed SdfPath <%s>: %s",
78 path.c_str(), context.errStr.c_str());
79 #else
80 TF_WARN("Ill-formed SdfPath <%s>: %s",
81 path.c_str(), context.errStr.c_str());
82 #endif
83 } else {
84 *this = std::move(context.path);
85 }
86
87 // Clean up.
88 pathYy_delete_buffer(b, context.scanner);
89 pathYylex_destroy(context.scanner);
90 }
91
92 const SdfPath &
EmptyPath()93 SdfPath::EmptyPath()
94 {
95 static SdfPath theEmptyPath;
96 return theEmptyPath;
97 }
98
99 const SdfPath &
AbsoluteRootPath()100 SdfPath::AbsoluteRootPath()
101 {
102 static SdfPath *theAbsoluteRootPath =
103 new SdfPath(Sdf_PathNode::GetAbsoluteRootNode(), nullptr);
104 return *theAbsoluteRootPath;
105 }
106
107 const SdfPath &
ReflexiveRelativePath()108 SdfPath::ReflexiveRelativePath()
109 {
110 static SdfPath *theReflexiveRelativePath =
111 new SdfPath(Sdf_PathNode::GetRelativeRootNode(), nullptr);
112 return *theReflexiveRelativePath;
113 }
114
115 size_t
GetPathElementCount() const116 SdfPath::GetPathElementCount() const
117 {
118 size_t primElems = _primPart ? _primPart->GetElementCount() : 0;
119 size_t propElems = _propPart ? _propPart->GetElementCount() : 0;
120 return primElems + propElems;
121 }
122
123 bool
IsAbsolutePath() const124 SdfPath::IsAbsolutePath() const
125 {
126 return _primPart && _primPart->IsAbsolutePath();
127 }
128
129 bool
IsAbsoluteRootPath() const130 SdfPath::IsAbsoluteRootPath() const
131 {
132 return !_propPart && _primPart && _primPart->IsAbsoluteRoot();
133 }
134
135 bool
IsPrimPath() const136 SdfPath::IsPrimPath() const
137 {
138 return !_propPart && _primPart &&
139 (_primPart->GetNodeType() == Sdf_PathNode::PrimNode ||
140 *this == ReflexiveRelativePath());
141 }
142
143 bool
IsAbsoluteRootOrPrimPath() const144 SdfPath::IsAbsoluteRootOrPrimPath() const
145 {
146 return !_propPart && _primPart &&
147 (_primPart->GetNodeType() == Sdf_PathNode::PrimNode ||
148 *this == AbsoluteRootPath() ||
149 *this == ReflexiveRelativePath());
150 }
151
152 bool
IsRootPrimPath() const153 SdfPath::IsRootPrimPath() const {
154 if (_propPart)
155 return false;
156 Sdf_PathNode const *primNode = _primPart.get();
157 return primNode && primNode->IsAbsolutePath() &&
158 primNode->GetElementCount() == 1;
159 }
160
161 bool
IsPropertyPath() const162 SdfPath::IsPropertyPath() const
163 {
164 if (Sdf_PathNode const *propNode = _propPart.get()) {
165 auto nodeType = propNode->GetNodeType();
166 return nodeType == Sdf_PathNode::PrimPropertyNode ||
167 nodeType == Sdf_PathNode::RelationalAttributeNode;
168 }
169 return false;
170 }
171
172 bool
IsPrimPropertyPath() const173 SdfPath::IsPrimPropertyPath() const
174 {
175 if (Sdf_PathNode const *propNode = _propPart.get()) {
176 return propNode->GetNodeType() == Sdf_PathNode::PrimPropertyNode;
177 }
178 return false;
179 }
180
181 bool
IsNamespacedPropertyPath() const182 SdfPath::IsNamespacedPropertyPath() const
183 {
184 if (Sdf_PathNode const *propNode = _propPart.get()) {
185 return propNode->IsNamespaced() &&
186 // Currently this subexpression is always true if IsNamespaced() is.
187 ((propNode->GetNodeType() ==
188 Sdf_PathNode::PrimPropertyNode) ||
189 (propNode->GetNodeType() ==
190 Sdf_PathNode::RelationalAttributeNode));
191 }
192 return false;
193 }
194
195 bool
IsPrimVariantSelectionPath() const196 SdfPath::IsPrimVariantSelectionPath() const
197 {
198 if (_propPart)
199 return false;
200 if (Sdf_PathNode const *primNode = _primPart.get()) {
201 return primNode->GetNodeType() ==
202 Sdf_PathNode::PrimVariantSelectionNode;
203 }
204 return false;
205 }
206
207 bool
IsPrimOrPrimVariantSelectionPath() const208 SdfPath::IsPrimOrPrimVariantSelectionPath() const
209 {
210 if (_propPart)
211 return false;
212 if (Sdf_PathNode const *primNode = _primPart.get()) {
213 auto nodeType = primNode->GetNodeType();
214 return
215 nodeType == Sdf_PathNode::PrimNode ||
216 nodeType == Sdf_PathNode::PrimVariantSelectionNode ||
217 *this == ReflexiveRelativePath();
218 }
219 return false;
220 }
221
222 bool
ContainsPrimVariantSelection() const223 SdfPath::ContainsPrimVariantSelection() const
224 {
225 if (Sdf_PathNode const *primNode = _primPart.get()) {
226 return primNode->ContainsPrimVariantSelection();
227 }
228 return false;
229 }
230
231 bool
ContainsTargetPath() const232 SdfPath::ContainsTargetPath() const
233 {
234 if (Sdf_PathNode const *propNode = _propPart.get()) {
235 return propNode->ContainsTargetPath();
236 }
237 return false;
238 }
239
240 bool
IsRelationalAttributePath() const241 SdfPath::IsRelationalAttributePath() const {
242 if (Sdf_PathNode const *propNode = _propPart.get()) {
243 return propNode->GetNodeType() == Sdf_PathNode::RelationalAttributeNode;
244 }
245 return false;
246 }
247
248 bool
IsTargetPath() const249 SdfPath::IsTargetPath() const {
250 if (Sdf_PathNode const *propNode = _propPart.get()) {
251 return propNode->GetNodeType() == Sdf_PathNode::TargetNode;
252 }
253 return false;
254 }
255
256 bool
IsMapperPath() const257 SdfPath::IsMapperPath() const {
258 if (Sdf_PathNode const *propNode = _propPart.get()) {
259 return propNode->GetNodeType() == Sdf_PathNode::MapperNode;
260 }
261 return false;
262 }
263
264 bool
IsMapperArgPath() const265 SdfPath::IsMapperArgPath() const {
266 if (Sdf_PathNode const *propNode = _propPart.get()) {
267 return propNode->GetNodeType() == Sdf_PathNode::MapperArgNode;
268 }
269 return false;
270 }
271
272 bool
IsExpressionPath() const273 SdfPath::IsExpressionPath() const {
274 if (Sdf_PathNode const *propNode = _propPart.get()) {
275 return propNode->GetNodeType() == Sdf_PathNode::ExpressionNode;
276 }
277 return false;
278 }
279
280 TfToken
GetAsToken() const281 SdfPath::GetAsToken() const
282 {
283 if (_primPart) {
284 return Sdf_PathNode::GetPathAsToken(_primPart.get(), _propPart.get());
285 }
286 return TfToken();
287 }
288
289 std::string
GetAsString() const290 SdfPath::GetAsString() const
291 {
292 return GetAsToken().GetString();
293 }
294
295 TfToken const &
GetToken() const296 SdfPath::GetToken() const
297 {
298 if (_primPart) {
299 return Sdf_PathNode::GetPathToken(_primPart.get(), _propPart.get());
300 }
301 return SdfPathTokens->empty;
302 }
303
304 const std::string &
GetString() const305 SdfPath::GetString() const
306 {
307 return GetToken().GetString();
308 }
309
310 const char *
GetText() const311 SdfPath::GetText() const
312 {
313 return GetToken().GetText();
314 }
315
316 SdfPathVector
GetPrefixes() const317 SdfPath::GetPrefixes() const {
318 SdfPathVector result;
319 GetPrefixes(&result);
320 return result;
321 }
322
323 void
GetPrefixes(SdfPathVector * prefixes) const324 SdfPath::GetPrefixes(SdfPathVector *prefixes) const
325 {
326 Sdf_PathNode const *prop = _propPart.get();
327 Sdf_PathNode const *prim = _primPart.get();
328
329 size_t elemCount = GetPathElementCount();
330 prefixes->resize(elemCount);
331
332 SdfPathVector::reverse_iterator iter = prefixes->rbegin();
333 while (prop && elemCount--) {
334 *iter++ = SdfPath(prim, prop);
335 prop = prop->GetParentNode();
336 }
337 while (prim && elemCount--) {
338 *iter++ = SdfPath(prim, prop);
339 prim = prim->GetParentNode();
340 }
341 }
342
343 SdfPathAncestorsRange
GetAncestorsRange() const344 SdfPath::GetAncestorsRange() const
345 {
346 return SdfPathAncestorsRange(*this);
347 }
348
349 const std::string &
GetName() const350 SdfPath::GetName() const
351 {
352 return GetNameToken().GetString();
353 }
354
355 const TfToken &
GetNameToken() const356 SdfPath::GetNameToken() const
357 {
358 if (_propPart) {
359 return _propPart.get()->GetName();
360 }
361 return _primPart ? _primPart.get()->GetName() : SdfPathTokens->empty;
362 }
363
364 string
GetElementString() const365 SdfPath::GetElementString() const
366 {
367 return GetElementToken().GetString();
368 }
369
370 TfToken
GetElementToken() const371 SdfPath::GetElementToken() const
372 {
373 if (_propPart)
374 return _propPart.get()->GetElement();
375 return _primPart ? _primPart.get()->GetElement() : TfToken();
376 }
377
378 SdfPath
ReplaceName(TfToken const & newName) const379 SdfPath::ReplaceName(TfToken const &newName) const
380 {
381 if (IsPrimPath())
382 return GetParentPath().AppendChild(newName);
383 else if (IsPrimPropertyPath())
384 return GetParentPath().AppendProperty(newName);
385 else if (IsRelationalAttributePath())
386 return GetParentPath().AppendRelationalAttribute(newName);
387
388 TF_CODING_ERROR("%s is not a prim, property, "
389 "or relational attribute path", GetText());
390 return SdfPath();
391 }
392
393 static Sdf_PathNode const *
_GetNextTargetNode(Sdf_PathNode const * curNode)394 _GetNextTargetNode(Sdf_PathNode const *curNode)
395 {
396 if (!curNode || !curNode->ContainsTargetPath())
397 return nullptr;
398
399 // Find nearest target or mapper node.
400 while (curNode
401 && curNode->GetNodeType() != Sdf_PathNode::TargetNode
402 && curNode->GetNodeType() != Sdf_PathNode::MapperNode) {
403 curNode = curNode->GetParentNode();
404 }
405 return curNode;
406 }
407
408 const SdfPath &
GetTargetPath() const409 SdfPath::GetTargetPath() const
410 {
411 if (!_propPart)
412 return EmptyPath();
413 Sdf_PathNode const *targetNode = _GetNextTargetNode(_propPart.get());
414 return targetNode ? targetNode->GetTargetPath() : EmptyPath();
415 }
416
417 void
GetAllTargetPathsRecursively(SdfPathVector * result) const418 SdfPath::GetAllTargetPathsRecursively(SdfPathVector *result) const
419 {
420 if (!_propPart)
421 return;
422 for (Sdf_PathNode const *targetNode = _GetNextTargetNode(_propPart.get());
423 targetNode;
424 targetNode = _GetNextTargetNode(targetNode->GetParentNode())) {
425 SdfPath const &targetPath = targetNode->GetTargetPath();
426 result->push_back(targetPath);
427 targetPath.GetAllTargetPathsRecursively(result);
428 }
429 }
430
431 pair<string, string>
GetVariantSelection() const432 SdfPath::GetVariantSelection() const
433 {
434 pair<string, string> result;
435 if (IsPrimVariantSelectionPath()) {
436 const Sdf_PathNode::VariantSelectionType& sel =
437 _primPart.get()->GetVariantSelection();
438 result.first = sel.first.GetString();
439 result.second = sel.second.GetString();
440 }
441 return result;
442 }
443
444 bool
HasPrefix(const SdfPath & prefix) const445 SdfPath::HasPrefix(const SdfPath &prefix) const
446 {
447 if (prefix.IsEmpty() || IsEmpty())
448 return false;
449
450 if (prefix._propPart) {
451 // The prefix is a property-like path, in order for it to be a prefix of
452 // this path, we must also have a property part, and our prim part must
453 // be the same as the prefix's prim part.
454 if (_primPart != prefix._primPart || !_propPart) {
455 return false;
456 }
457
458 // Now walk up property parts until we hit prefix._propPart or we
459 // recurse above its depth.
460 Sdf_PathNode const *propNode = _propPart.get();
461 Sdf_PathNode const *prefixPropNode = prefix._propPart.get();
462 while (propNode && propNode != prefixPropNode) {
463 propNode = propNode->GetParentNode();
464 }
465 return propNode == prefixPropNode;
466 }
467 else {
468 // The prefix is a prim-like path. Walk up nodes until we achieve the
469 // same depth as the prefix, then just check for equality.
470 Sdf_PathNode const *primNode = _primPart.get();
471
472 if (primNode->IsAbsolutePath() &&
473 prefix == SdfPath::AbsoluteRootPath()) {
474 return true;
475 }
476
477 Sdf_PathNode const *prefixPrimNode = prefix._primPart.get();
478
479 int prefixDepth = prefixPrimNode->GetElementCount();
480 int curDepth = primNode->GetElementCount();
481
482 if (curDepth < prefixDepth) {
483 return false;
484 }
485 while (curDepth > prefixDepth) {
486 primNode = primNode->GetParentNode();
487 --curDepth;
488 }
489 return primNode == prefixPrimNode;
490 }
491 }
492
493 SdfPath
GetParentPath() const494 SdfPath::GetParentPath() const {
495 if (IsEmpty()) {
496 return *this;
497 }
498
499 // If this is a property-like path, trim that first.
500 if (_propPart) {
501 Sdf_PathNode const *propNode = _propPart.get()->GetParentNode();
502 return SdfPath(_primPart, Sdf_PathPropNodeHandle(propNode));
503 }
504
505 // This is a prim-like path. If this is an absolute path (most common case)
506 // then it's just the parent path node. On the other hand if this path is a
507 // relative path, and is '.' or ends with '..', the logical parent path is
508 // made by appending a '..' component.
509 //
510 // XXX: NOTE that this is NOT the way that that Sdf_PathNode::GetParentNode
511 // works, and note that most of the code in SdfPath uses GetParentNode
512 // intentionally.
513 Sdf_PathNode const *primNode = _primPart.get();
514 if (ARCH_LIKELY(
515 primNode->IsAbsolutePath() ||
516 (primNode != Sdf_PathNode::GetRelativeRootNode() &&
517 primNode->GetName() != SdfPathTokens->parentPathElement))) {
518 return SdfPath(primNode->GetParentNode(), nullptr);
519 }
520 // Is relative root, or ends with '..'.
521 return SdfPath(Sdf_PathNode::FindOrCreatePrim(
522 primNode, SdfPathTokens->parentPathElement),
523 Sdf_PathPropNodeHandle());
524 }
525
526 SdfPath
GetPrimPath() const527 SdfPath::GetPrimPath() const {
528
529 Sdf_PathNode const *primNode = _primPart.get();
530 // Walk up looking for a prim node.
531 while (primNode && primNode->GetNodeType() != Sdf_PathNode::PrimNode) {
532 primNode = primNode->GetParentNode();
533 }
534 return SdfPath(primNode, nullptr);
535 }
536
537 SdfPath
GetPrimOrPrimVariantSelectionPath() const538 SdfPath::GetPrimOrPrimVariantSelectionPath() const
539 {
540 Sdf_PathNode const *primNode = _primPart.get();
541 // Walk up looking for a prim or prim variant selection node.
542 while (primNode &&
543 (primNode->GetNodeType() != Sdf_PathNode::PrimNode &&
544 primNode->GetNodeType() != Sdf_PathNode::PrimVariantSelectionNode)){
545 primNode = primNode->GetParentNode();
546 }
547 return SdfPath(primNode, nullptr);
548 }
549
550 SdfPath
GetAbsoluteRootOrPrimPath() const551 SdfPath::GetAbsoluteRootOrPrimPath() const {
552 return (*this == AbsoluteRootPath()) ? *this : GetPrimPath();
553 }
554
555 static inline SdfPath
_AppendNode(const SdfPath & path,Sdf_PathNode const * node)556 _AppendNode(const SdfPath &path, Sdf_PathNode const *node) {
557
558 switch (node->GetNodeType()) {
559 case Sdf_PathNode::PrimNode:
560 return path.AppendChild(node->GetName());
561 case Sdf_PathNode::PrimPropertyNode:
562 return path.AppendProperty(node->GetName());
563 case Sdf_PathNode::PrimVariantSelectionNode:
564 {
565 const Sdf_PathNode::VariantSelectionType& selection =
566 node->GetVariantSelection();
567 return path.AppendVariantSelection(selection.first.GetString(),
568 selection.second.GetString());
569 }
570 case Sdf_PathNode::TargetNode:
571 return path.AppendTarget( node->GetTargetPath());
572 case Sdf_PathNode::RelationalAttributeNode:
573 return path.AppendRelationalAttribute(node->GetName());
574 case Sdf_PathNode::MapperNode:
575 return path.AppendMapper(node->GetTargetPath());
576 case Sdf_PathNode::MapperArgNode:
577 return path.AppendMapperArg(node->GetName());
578 case Sdf_PathNode::ExpressionNode:
579 return path.AppendExpression();
580 default:
581 // CODE_COVERAGE_OFF
582 // Should never get here. All reasonable cases are
583 // handled above.
584 TF_CODING_ERROR("Unexpected node type %i", node->GetNodeType());
585 return SdfPath::EmptyPath();
586 // CODE_COVERAGE_ON
587 }
588 }
589
590 SdfPath
StripAllVariantSelections() const591 SdfPath::StripAllVariantSelections() const {
592 if (!ContainsPrimVariantSelection())
593 return *this;
594 TRACE_FUNCTION();
595 std::vector<Sdf_PathNode const *> primNodes;
596 Sdf_PathNode const *curNode = _primPart.get();
597 while (curNode) {
598 if (curNode->GetNodeType() != Sdf_PathNode::PrimVariantSelectionNode)
599 primNodes.push_back(curNode);
600 curNode = curNode->GetParentNode();
601 }
602
603 SdfPath stripPath(*(primNodes.rbegin()), nullptr);
604 // Step through all primNodes except the last (which is the root node):
605 for (auto it = ++(primNodes.rbegin()); it != primNodes.rend(); ++it) {
606 stripPath = _AppendNode(stripPath, *it);
607 }
608 // Tack on any property portion.
609 stripPath._propPart = _propPart;
610 return stripPath;
611 }
612
613
614 SdfPath
AppendPath(const SdfPath & newSuffix) const615 SdfPath::AppendPath(const SdfPath &newSuffix) const {
616 if (*this == EmptyPath()) {
617 TF_CODING_ERROR("Cannot append to invalid path");
618 return EmptyPath();
619 }
620 if (newSuffix == EmptyPath()) {
621 TF_CODING_ERROR("Cannot append invalid path to <%s>",
622 GetAsString().c_str());
623 return EmptyPath();
624 }
625 if (newSuffix.IsAbsolutePath()) {
626 TF_WARN("Cannot append absolute path <%s> to another path <%s>.",
627 newSuffix.GetAsString().c_str(), GetAsString().c_str());
628 return EmptyPath();
629 }
630 if (newSuffix == ReflexiveRelativePath()) {
631 return *this;
632 }
633
634 Sdf_PathNode::NodeType primNodeType = _primPart->GetNodeType();
635 if (_propPart || (primNodeType != Sdf_PathNode::RootNode &&
636 primNodeType != Sdf_PathNode::PrimNode &&
637 primNodeType != Sdf_PathNode::PrimVariantSelectionNode)) {
638 TF_WARN("Cannot append a path to another path that is not "
639 "a root or a prim path.");
640 return EmptyPath();
641 }
642
643 // This list winds up in reverse order to what one might at first expect.
644 vector<Sdf_PathNode const *> tailNodes;
645
646 // Walk up to top of newSuffix.
647 Sdf_PathNode const *curNode = newSuffix._propPart.get();
648 while (curNode) {
649 tailNodes.push_back(curNode);
650 curNode = curNode->GetParentNode();
651 }
652 curNode = newSuffix._primPart.get();
653 while (curNode != Sdf_PathNode::GetRelativeRootNode()) {
654 tailNodes.push_back(curNode);
655 curNode = curNode->GetParentNode();
656 }
657
658 if ((tailNodes.back()->GetNodeType() == Sdf_PathNode::PrimPropertyNode) &&
659 *this == AbsoluteRootPath()) {
660 TF_WARN("Cannot append a property path to the absolute root path.");
661 return EmptyPath();
662 }
663
664 SdfPath result = *this;
665
666 // We have a list of new nodes (in reverse order) to append to our node.
667 for (auto it = tailNodes.rbegin();
668 (it != tailNodes.rend()) && (result != EmptyPath()); ++it) {
669 result = _AppendNode(result, *it);
670 }
671 return result;
672 }
673
674 // Use a simple per-thread cache for appending children to prim paths. This
675 // lets us avoid hitting the global table, reducing thread contention, for
676 // appending children repeatedly to a node.
677 namespace {
678 struct _PerThreadPrimPathCache
679 {
680 static constexpr unsigned Shift = 14;
681 static constexpr unsigned Size = 1 << Shift;
682 static constexpr unsigned ProbeShift = 1;
683 static constexpr unsigned Probes = 1 << ProbeShift;
684
685 struct _Entry {
686 Sdf_PathPrimNodeHandle parent;
687 Sdf_PathPrimNodeHandle primPart;
688 TfToken childName;
689 };
690
691 inline Sdf_PathPrimNodeHandle
Find__anon2d62f9890111::_PerThreadPrimPathCache692 Find(Sdf_PathPrimNodeHandle const &parent, TfToken const &childName,
693 int *outIndex) const {
694 // Hash and shift to find table index.
695 size_t h = childName.Hash();
696 uint32_t parentAsInt;
697 memcpy(&parentAsInt, &parent, sizeof(uint32_t));
698 boost::hash_combine(h, parentAsInt >> 8);
699 unsigned index = (h & (Size-1));
700
701 for (unsigned probe = 0; probe != Probes; ++probe) {
702 _Entry const &e = cache[(index + probe) & (Size - 1)];
703 if (e.parent == parent && e.childName == childName) {
704 // Cache hit.
705 return e.primPart;
706 }
707 if (!e.parent)
708 break;
709 }
710
711 // Not found -- arrange to replace original hash index.
712 *outIndex = index;
713 return Sdf_PathPrimNodeHandle();
714 }
715
716 inline void
Store__anon2d62f9890111::_PerThreadPrimPathCache717 Store(Sdf_PathPrimNodeHandle const &parent, TfToken const &childName,
718 Sdf_PathPrimNodeHandle primPart, int index) {
719 cache[index] = { parent, primPart, childName };
720 }
721
722 _Entry cache[Size];
723 };
724 }
725
726 namespace {
727 // XXX: Workaround for Windows issue USD-5306 -- this avoids destroying the
728 // per-thread caches to deal with static destruction order problems.
729 template <class T>
730 struct _FastThreadLocalBase
731 {
Get__anon2d62f9890211::_FastThreadLocalBase732 static T &Get() {
733 static thread_local T *theTPtr = nullptr;
734 if (ARCH_LIKELY(theTPtr)) {
735 return *theTPtr;
736 }
737 static thread_local
738 typename std::aligned_storage<sizeof(T)>::type storage;
739 void *addr = &storage;
740 T *p = new (addr) T;
741 theTPtr = p;
742 return *p;
743 }
744 };
745 }
746 using _PrimPathCache = _FastThreadLocalBase<_PerThreadPrimPathCache>;
747 static _PrimPathCache _primPathCache;
748
749 SdfPath
AppendChild(TfToken const & childName) const750 SdfPath::AppendChild(TfToken const &childName) const {
751 if (ARCH_UNLIKELY(_propPart)) {
752 TF_WARN("Cannot append child '%s' to path '%s'.",
753 childName.GetText(), GetText());
754 return EmptyPath();
755 }
756 auto &cache = _primPathCache.Get();
757 int storeIndex = 0;
758 Sdf_PathPrimNodeHandle primPart =
759 cache.Find(_primPart, childName, &storeIndex);
760 SdfPath ret { primPart, {} };
761 if (primPart) {
762 return ret;
763 }
764 if (!IsAbsoluteRootOrPrimPath()
765 && !IsPrimVariantSelectionPath()
766 && (*this != ReflexiveRelativePath())) {
767 TF_WARN("Cannot append child '%s' to path '%s'.",
768 childName.GetText(), GetText());
769 return EmptyPath();
770 }
771 if (ARCH_UNLIKELY(childName == SdfPathTokens->parentPathElement)) {
772 return GetParentPath();
773 } else {
774 if (ARCH_UNLIKELY(!_IsValidIdentifier(childName))) {
775 TF_WARN("Invalid prim name '%s'", childName.GetText());
776 return EmptyPath();
777 }
778 ret._primPart =
779 Sdf_PathNode::FindOrCreatePrim(_primPart.get(), childName);
780 cache.Store(_primPart, childName, ret._primPart, storeIndex);
781 return ret;
782 }
783 }
784
785
786 // Use a simple per-thread cache for appending prim properties. This lets us
787 // avoid hitting the global table, reducing thread contention and increasing
788 // speed. We don't do this for the other property-type paths, like target paths
789 // or relational attribute paths because those operations are done much less
790 // frequently than appending properties to prim paths.
791 namespace {
792 struct _PerThreadPropertyPathCache
793 {
794 static constexpr unsigned Shift = 10;
795 static constexpr unsigned Size = 1 << Shift;
796 static constexpr unsigned ProbeShift = 1;
797 static constexpr unsigned Probes = 1 << ProbeShift;
798
799 struct _Entry {
800 TfToken propName;
801 Sdf_PathPropNodeHandle propPart;
802 };
803
804 inline Sdf_PathPropNodeHandle
Find__anon2d62f9890311::_PerThreadPropertyPathCache805 Find(TfToken const &propName, int *outIndex) const {
806 // Hash and shift to find table index.
807 size_t h = propName.Hash();
808 unsigned index = (h >> (8*sizeof(h) - Shift));
809
810 for (unsigned probe = 0; probe != Probes; ++probe) {
811 _Entry const &e = cache[(index + probe) & (Size - 1)];
812 if (e.propName == propName) {
813 // Cache hit.
814 return e.propPart;
815 }
816 if (e.propName.IsEmpty())
817 break;
818 }
819
820 // Not found -- arrange to replace original hash index.
821 *outIndex = index;
822 return Sdf_PathPropNodeHandle();
823 }
824
825 inline void
Store__anon2d62f9890311::_PerThreadPropertyPathCache826 Store(TfToken const &propName, Sdf_PathPropNodeHandle propPart, int index) {
827 cache[index] = { propName, propPart };
828 }
829
830 _Entry cache[Size];
831 };
832 }
833
834 using _PropPathCache = Sdf_FastThreadLocalBase<_PerThreadPropertyPathCache>;
835 static _PropPathCache _propPathCache;
836
837 SdfPath
AppendProperty(TfToken const & propName) const838 SdfPath::AppendProperty(TfToken const &propName) const {
839 if (ARCH_UNLIKELY(_propPart)) {
840 TF_WARN("Can only append a property '%s' to a prim path (%s)",
841 propName.GetText(), GetText());
842 return EmptyPath();
843 }
844 auto &cache = _propPathCache.Get();
845 int storeIndex = 0;
846 Sdf_PathPropNodeHandle propPart = cache.Find(propName, &storeIndex);
847 SdfPath ret { _primPart, propPart };
848 if (propPart) {
849 return ret;
850 }
851 if (!IsValidNamespacedIdentifier(propName.GetString())) {
852 //TF_WARN("Invalid property name.");
853 return EmptyPath();
854 }
855 if (!IsPrimVariantSelectionPath() &&
856 !IsPrimPath() && (*this != ReflexiveRelativePath())) {
857 TF_WARN("Can only append a property '%s' to a prim path (%s)",
858 propName.GetText(), GetText());
859 return EmptyPath();
860 }
861 ret._propPart =
862 Sdf_PathNode::FindOrCreatePrimProperty(_primPart.get(), propName);
863 cache.Store(propName, ret._propPart, storeIndex);
864 return ret;
865 }
866
867 SdfPath
AppendVariantSelection(const string & variantSet,const string & variant) const868 SdfPath::AppendVariantSelection(const string &variantSet,
869 const string &variant) const
870 {
871 if (!IsPrimOrPrimVariantSelectionPath()) {
872 TF_CODING_ERROR("Cannot append variant selection %s = %s to <%s>; "
873 "can only append a variant selection to a prim or "
874 "prim variant selection path.",
875 variantSet.c_str(), variant.c_str(),
876 GetText());
877 return EmptyPath();
878 }
879 return SdfPath(Sdf_PathNode::
880 FindOrCreatePrimVariantSelection(_primPart.get(),
881 TfToken(variantSet),
882 TfToken(variant)));
883 }
884
885 SdfPath
AppendTarget(const SdfPath & targetPath) const886 SdfPath::AppendTarget(const SdfPath &targetPath) const {
887 if (!IsPropertyPath()) {
888 TF_WARN("Can only append a target to a property path.");
889 return EmptyPath();
890 }
891 if (targetPath == EmptyPath()) {
892 TF_WARN("Target path cannot be invalid.");
893 return EmptyPath();
894 }
895 return SdfPath(_primPart, Sdf_PathNode::
896 FindOrCreateTarget(_propPart.get(), targetPath));
897 }
898
899 SdfPath
AppendRelationalAttribute(TfToken const & attrName) const900 SdfPath::AppendRelationalAttribute(TfToken const &attrName) const {
901 if (!IsValidNamespacedIdentifier(attrName)) {
902 TF_WARN("Invalid property name.");
903 return EmptyPath();
904 }
905 if (!IsTargetPath()) {
906 TF_WARN("Can only append a relational attribute to a target path.");
907 return EmptyPath();
908 }
909 return SdfPath(_primPart,
910 Sdf_PathNode::FindOrCreateRelationalAttribute(
911 _propPart.get(), attrName));
912 }
913
914 SdfPath
AppendMapper(const SdfPath & targetPath) const915 SdfPath::AppendMapper(const SdfPath &targetPath) const {
916 if (!IsPropertyPath()) {
917 TF_WARN("Cannnot append mapper '%s' to non-property path <%s>.",
918 targetPath.GetAsString().c_str(), GetAsString().c_str());
919 return EmptyPath();
920 }
921 if (targetPath == EmptyPath()) {
922 TF_WARN("Cannot append an empty mapper target path to <%s>",
923 GetAsString().c_str());
924 return EmptyPath();
925 }
926 return SdfPath { _primPart,
927 Sdf_PathNode::FindOrCreateMapper(_propPart.get(), targetPath) };
928 }
929
930 SdfPath
AppendMapperArg(TfToken const & argName) const931 SdfPath::AppendMapperArg(TfToken const &argName) const {
932 if (!_IsValidIdentifier(argName)) {
933 TF_WARN("Invalid arg name.");
934 return EmptyPath();
935 }
936 if (!IsMapperPath()) {
937 TF_WARN("Can only append a mapper arg to a mapper path.");
938 return EmptyPath();
939 }
940 return SdfPath { _primPart,
941 Sdf_PathNode::FindOrCreateMapperArg(_propPart.get(), argName) };
942 }
943
944 SdfPath
AppendExpression() const945 SdfPath::AppendExpression() const {
946 if (!IsPropertyPath()) {
947 TF_WARN("Can only append an expression to a property path.");
948 return EmptyPath();
949 }
950 return SdfPath { _primPart,
951 Sdf_PathNode::FindOrCreateExpression(_propPart.get()) };
952 }
953
954 SdfPath
AppendElementString(const std::string & element) const955 SdfPath::AppendElementString(const std::string &element) const
956 {
957 return AppendElementToken(TfToken(element));
958 }
959
960 SdfPath
AppendElementToken(const TfToken & elementTok) const961 SdfPath::AppendElementToken(const TfToken &elementTok) const
962 {
963 std::string const &element = elementTok.GetString();
964
965 if (ARCH_UNLIKELY(IsEmpty() || element.empty())) {
966 if (IsEmpty()) {
967 TF_CODING_ERROR("Cannot append element \'%s\' to the EmptyPath.",
968 element.c_str());
969 }
970 else {
971 TF_CODING_ERROR("Cannot append EmptyPath as a path element.");
972 }
973 return EmptyPath();
974 }
975 /* This is a somewhat unfortunate replication of a subset of the
976 * logic contained in the full-path-parser. We can't invoke the
977 * parser on just a single element out of context (and probably
978 * wouldn't want to for cost reasons if we could). Can't think of
979 * a more elegant way to do this. 1/13 */
980 char const *txt = element.c_str();
981 // No static tokens for variant chars...
982 if (txt[0] == '{') {
983
984 vector<string> tokens = TfStringTokenize(element, "{=}");
985 TfToken variantSel;
986 if (tokens.size() == 2){
987 variantSel = TfToken(tokens[1]);
988 }
989 else if (tokens.size() != 1){
990 return EmptyPath();
991 }
992 return AppendVariantSelection(TfToken(tokens[0]),
993 variantSel);
994
995 }
996 else if (txt[0] == SdfPathTokens->relationshipTargetStart.GetString()[0]) {
997 SdfPath target(element.substr(1, element.length()-2));
998 return AppendTarget(target);
999 }
1000 else if (txt[0] == SdfPathTokens->propertyDelimiter.GetString()[0]) {
1001 // This is the ambiguous one. First check for the special symbols,
1002 // and if it looks like a "plain old property", consult parent type
1003 // to determine what the property sub-type should be.
1004 static string mapperStr = SdfPathTokens->propertyDelimiter.GetString() +
1005 SdfPathTokens->mapperIndicator.GetString() +
1006 SdfPathTokens->relationshipTargetStart.GetString();
1007 static string expressionStr =
1008 SdfPathTokens->propertyDelimiter.GetString()
1009 + SdfPathTokens->expressionIndicator.GetString();
1010
1011 if ( element == expressionStr ){
1012 return IsPropertyPath() ? AppendExpression() :
1013 AppendProperty(SdfPathTokens->expressionIndicator);
1014 }
1015 else if (TfStringStartsWith(element, mapperStr)){
1016 const size_t prefixSz(mapperStr.length());
1017 SdfPath target(element.substr(prefixSz,
1018 element.length()-(prefixSz+1)));
1019 return AppendMapper(target);
1020 }
1021 else {
1022 TfToken property(element.substr(1));
1023
1024 if (IsMapperPath()){
1025 return AppendMapperArg(property);
1026 }
1027 else if (IsTargetPath()){
1028 return AppendRelationalAttribute(property);
1029 }
1030 else {
1031 return AppendProperty(property);
1032 }
1033 }
1034 }
1035 else {
1036 return AppendChild(elementTok);
1037 }
1038
1039 }
1040
1041 SdfPath
_ReplacePrimPrefix(SdfPath const & oldPrefix,SdfPath const & newPrefix) const1042 SdfPath::_ReplacePrimPrefix(SdfPath const &oldPrefix,
1043 SdfPath const &newPrefix) const
1044 {
1045 using Sdf_PathNodeConstPtr = Sdf_PathNode const *;
1046
1047 // Walk up the prim part of this path until we have the same depth as
1048 // oldPrefix, recording tail elements along the way. If we find oldPrefix
1049 // is in fact a prefix, then tack the tail elements onto newPrefix and
1050 // return the resulting path with our property element (if any). Otherwise
1051 // return this path unchanged.
1052
1053 Sdf_PathNodeConstPtr primNode = _primPart.get();
1054 Sdf_PathNodeConstPtr prefixPrimNode = oldPrefix._primPart.get();
1055
1056 int prefixDepth = prefixPrimNode->GetElementCount();
1057 int curDepth = primNode->GetElementCount();
1058
1059 if (curDepth < prefixDepth) {
1060 return *this;
1061 }
1062
1063 // Make space for temporary tail nodes. Use stack if small enough.
1064 constexpr size_t MaxLocalNodes = 16;
1065 Sdf_PathNodeConstPtr localNodes[MaxLocalNodes];
1066 std::unique_ptr<Sdf_PathNodeConstPtr []> remoteNodes;
1067 Sdf_PathNodeConstPtr *tmpNodes = localNodes;
1068 size_t requiredTmpNodes = curDepth - prefixDepth;
1069 if (requiredTmpNodes > MaxLocalNodes) {
1070 remoteNodes.reset(new Sdf_PathNodeConstPtr[requiredTmpNodes]);
1071 tmpNodes = remoteNodes.get();
1072 }
1073
1074 size_t i = 0;
1075 while (curDepth > prefixDepth) {
1076 tmpNodes[i++] = primNode;
1077 primNode = primNode->GetParentNode();
1078 --curDepth;
1079 }
1080
1081 if (primNode != prefixPrimNode) {
1082 return *this;
1083 }
1084
1085 // Tack the prim elements onto newPrefix.
1086 SdfPath newPath = newPrefix;
1087 while (i--) {
1088 switch (tmpNodes[i]->GetNodeType()) {
1089 case Sdf_PathNode::PrimNode:
1090 newPath._primPart = Sdf_PathNode::FindOrCreatePrim(
1091 newPath._primPart.get(), tmpNodes[i]->GetName());
1092 break;
1093 default:
1094 newPath = _AppendNode(newPath, tmpNodes[i]);
1095 }
1096 }
1097
1098 // Add our property element.
1099 newPath._propPart = _propPart;
1100
1101 return newPath;
1102 }
1103
1104 SdfPath
_ReplaceTargetPathPrefixes(SdfPath const & oldPrefix,SdfPath const & newPrefix) const1105 SdfPath::_ReplaceTargetPathPrefixes(SdfPath const &oldPrefix,
1106 SdfPath const &newPrefix) const
1107 {
1108 using Sdf_PathNodeConstPtr = Sdf_PathNode const *;
1109
1110 // Go through all the target paths in this path, and replace their prefixes.
1111 Sdf_PathNode const *propNode = _propPart.get();
1112 if (!propNode->ContainsTargetPath()) {
1113 return *this;
1114 }
1115
1116 // Make space for temporary tail nodes. Use stack if small enough.
1117 constexpr size_t MaxLocalNodes = 16;
1118 Sdf_PathNodeConstPtr localNodes[MaxLocalNodes];
1119 std::unique_ptr<Sdf_PathNodeConstPtr []> remoteNodes;
1120 Sdf_PathNodeConstPtr *tmpNodes = localNodes;
1121 size_t requiredTmpNodes = propNode->GetElementCount();
1122 if (requiredTmpNodes > MaxLocalNodes) {
1123 remoteNodes.reset(new Sdf_PathNodeConstPtr[requiredTmpNodes]);
1124 tmpNodes = remoteNodes.get();
1125 }
1126
1127 size_t i = 0;
1128 while (propNode && propNode->ContainsTargetPath()) {
1129 tmpNodes[i++] = propNode;
1130 propNode = propNode->GetParentNode();
1131 }
1132
1133 // Tack the prop elements onto newPrefix's prop part.
1134 SdfPath newPath(_primPart.get(), propNode);
1135 while (i--) {
1136 switch (tmpNodes[i]->GetNodeType()) {
1137 case Sdf_PathNode::PrimPropertyNode:
1138 newPath._propPart = Sdf_PathNode::FindOrCreatePrimProperty(
1139 nullptr, tmpNodes[i]->GetName());
1140 break;
1141 case Sdf_PathNode::TargetNode:
1142 newPath = newPath.AppendTarget(
1143 tmpNodes[i]->GetTargetPath().ReplacePrefix(
1144 oldPrefix, newPrefix, /*fixTargetPaths=*/true));
1145 break;
1146 case Sdf_PathNode::MapperNode:
1147 newPath = newPath.AppendMapper(
1148 tmpNodes[i]->GetTargetPath().ReplacePrefix(
1149 oldPrefix, newPrefix, /*fixTargetPaths=*/true));
1150 break;
1151 default:
1152 newPath = _AppendNode(newPath, tmpNodes[i]);
1153 }
1154 }
1155
1156 return newPath;
1157 }
1158
1159 SdfPath
_ReplacePropPrefix(SdfPath const & oldPrefix,SdfPath const & newPrefix,bool fixTargetPaths) const1160 SdfPath::_ReplacePropPrefix(SdfPath const &oldPrefix,
1161 SdfPath const &newPrefix,
1162 bool fixTargetPaths) const
1163 {
1164 using Sdf_PathNodeConstPtr = Sdf_PathNode const *;
1165
1166 // Walk up the prop part of this path until we have the same depth as
1167 // oldPrefix's prop part, recording tail elements along the way. If we find
1168 // oldPrefix is in fact a prefix, then tack the tail elements onto newPrefix
1169 // (replacing prefixes in target paths if \p fixTargetPaths is true). If
1170 // oldPrefix is not found, then just replace target paths in all the
1171 // elements.
1172
1173 Sdf_PathNodeConstPtr propNode = _propPart.get();
1174 Sdf_PathNodeConstPtr prefixPropNode = oldPrefix._propPart.get();
1175
1176 int prefixDepth = prefixPropNode->GetElementCount();
1177 int curDepth = propNode->GetElementCount();
1178
1179 if (curDepth < prefixDepth) {
1180 return (fixTargetPaths && propNode->ContainsTargetPath()) ?
1181 _ReplaceTargetPathPrefixes(oldPrefix, newPrefix) : *this;
1182 }
1183
1184 // Make space for temporary tail nodes. Use stack if small enough.
1185 constexpr size_t MaxLocalNodes = 16;
1186 Sdf_PathNodeConstPtr localNodes[MaxLocalNodes];
1187 std::unique_ptr<Sdf_PathNodeConstPtr []> remoteNodes;
1188 Sdf_PathNodeConstPtr *tmpNodes = localNodes;
1189 size_t requiredTmpNodes = curDepth - prefixDepth;
1190 if (requiredTmpNodes > MaxLocalNodes) {
1191 remoteNodes.reset(new Sdf_PathNodeConstPtr[requiredTmpNodes]);
1192 tmpNodes = remoteNodes.get();
1193 }
1194
1195 size_t i = 0;
1196 while (curDepth > prefixDepth) {
1197 tmpNodes[i++] = propNode;
1198 propNode = propNode->GetParentNode();
1199 --curDepth;
1200 }
1201
1202 if (propNode != prefixPropNode) {
1203 return (fixTargetPaths && ContainsTargetPath()) ?
1204 _ReplaceTargetPathPrefixes(oldPrefix, newPrefix) : *this;
1205 }
1206
1207 // Tack the prop elements onto newPrefix's prop part.
1208 SdfPath newPath = newPrefix;
1209 while (i--) {
1210 switch (tmpNodes[i]->GetNodeType()) {
1211 case Sdf_PathNode::PrimPropertyNode:
1212 newPath._propPart = Sdf_PathNode::FindOrCreatePrimProperty(
1213 nullptr, tmpNodes[i]->GetName());
1214 break;
1215 case Sdf_PathNode::TargetNode:
1216 if (fixTargetPaths) {
1217 newPath = newPath.AppendTarget(
1218 tmpNodes[i]->GetTargetPath().ReplacePrefix(
1219 oldPrefix, newPrefix, fixTargetPaths));
1220 } else {
1221 newPath = _AppendNode(newPath, tmpNodes[i]);
1222 }
1223 break;
1224 case Sdf_PathNode::MapperNode:
1225 if (fixTargetPaths) {
1226 newPath = newPath.AppendMapper(
1227 tmpNodes[i]->GetTargetPath().ReplacePrefix(
1228 oldPrefix, newPrefix, fixTargetPaths));
1229 } else {
1230 newPath = _AppendNode(newPath, tmpNodes[i]);
1231 }
1232 break;
1233 default:
1234 newPath = _AppendNode(newPath, tmpNodes[i]);
1235 }
1236 }
1237
1238 return newPath;
1239 }
1240
1241
1242 SdfPath
ReplacePrefix(const SdfPath & oldPrefix,const SdfPath & newPrefix,bool fixTargetPaths) const1243 SdfPath::ReplacePrefix(const SdfPath &oldPrefix, const SdfPath &newPrefix,
1244 bool fixTargetPaths) const
1245 {
1246 // Perhaps surprisingly, this path need not have oldPrefix as a prefix. For
1247 // example, '/a.rel[/target]'.ReplacePrefix('/target', '/other/target') ->
1248 // '/a.rel[/other/target]' when fixTargetPaths == true.
1249
1250 TRACE_FUNCTION();
1251
1252 if (IsEmpty() || oldPrefix == newPrefix) {
1253 return *this;
1254 }
1255 if (oldPrefix.IsEmpty() || newPrefix.IsEmpty()) {
1256 return EmptyPath();
1257 }
1258 if (*this == oldPrefix) {
1259 return newPrefix;
1260 }
1261
1262 using Sdf_PathNodeConstPtr = Sdf_PathNode const *;
1263
1264 Sdf_PathNodeConstPtr primNode = _primPart.get();
1265 Sdf_PathNodeConstPtr propNode = _propPart.get();
1266
1267 SdfPath newPath;
1268
1269 if (!oldPrefix._propPart) {
1270 // oldPrefix is a prim-like path. Replace the prefix in the prim part,
1271 // if it has oldPrefix as a prefix.
1272 newPath = _ReplacePrimPrefix(oldPrefix, newPrefix);
1273
1274 if (fixTargetPaths && propNode && propNode->ContainsTargetPath()) {
1275 // This path is property-like and contains targets that we need to
1276 // fix, so fix them up.
1277 newPath = newPath._ReplaceTargetPathPrefixes(oldPrefix, newPrefix);
1278 }
1279 }
1280 else {
1281 // oldPrefix is a property-like path. If this path is a prim-like path
1282 // then oldPrefix cannot be a prefix of this path and we do not have
1283 // targets to fix.
1284 if (!propNode) {
1285 return *this;
1286 }
1287
1288 // Both oldPrefix and this are property-like paths. If the prim parts
1289 // do not match, then we just replace targets (or do nothing). If they
1290 // do match, then we walk up prop nodes to same depth (or as long as we
1291 // need to fix targets) and replace. But crucially, we have to search
1292 // for the property part of oldPrefix as a prefix of this path's
1293 // property part. If we find it then the resulting path has newPrefix's
1294 // prim part, otherwise it has this path's prim part.
1295
1296 if (primNode != oldPrefix._primPart.get()) {
1297 if (fixTargetPaths && propNode->ContainsTargetPath()) {
1298 newPath = _ReplaceTargetPathPrefixes(oldPrefix, newPrefix);
1299 }
1300 else {
1301 return *this;
1302 }
1303 }
1304 else {
1305 newPath = _ReplacePropPrefix(oldPrefix, newPrefix, fixTargetPaths);
1306 }
1307 }
1308
1309 return newPath;
1310 }
1311
1312 SdfPath
GetCommonPrefix(const SdfPath & path2) const1313 SdfPath::GetCommonPrefix(const SdfPath &path2) const {
1314
1315 if (path2.IsEmpty()) {
1316 TF_WARN("GetCommonPrefix(): invalid path.");
1317 return SdfPath();
1318 }
1319
1320 SdfPath const &path1 = *this;
1321
1322 // Skip as much as we can based on whether or not the paths have property
1323 // elements, etc. We either start in the prim area (if one or both paths
1324 // have no property elements, or if they both do but the leafmost prim
1325 // elements differ) or we stay fully in the property area (up to the
1326 // leafmost prim element).
1327 Sdf_PathNode const *path1Node;
1328 Sdf_PathNode const *path2Node;
1329
1330 bool isPrimLike = true;
1331 if (ARCH_LIKELY(!path1._propPart || !path2._propPart ||
1332 (path1._primPart != path2._primPart))) {
1333 path1Node = path1._primPart.get();
1334 path2Node = path2._primPart.get();
1335 }
1336 else {
1337 isPrimLike = false;
1338 path1Node = path1._propPart.get();
1339 path2Node = path2._propPart.get();
1340 }
1341
1342 size_t count1 = path1Node->GetElementCount();
1343 size_t count2 = path2Node->GetElementCount();
1344
1345 while (count1 > count2) {
1346 path1Node = path1Node->GetParentNode();
1347 --count1;
1348 }
1349 while (count2 > count1) {
1350 path2Node = path2Node->GetParentNode();
1351 --count2;
1352 }
1353
1354 while (path1Node != path2Node) {
1355 path1Node = path1Node->GetParentNode();
1356 path2Node = path2Node->GetParentNode();
1357 }
1358
1359 SdfPath ret;
1360 if (ARCH_LIKELY(isPrimLike)) {
1361 ret._primPart = path1Node;
1362 }
1363 else {
1364 ret._primPart = path1._primPart;
1365 ret._propPart = path1Node;
1366 }
1367 return ret;
1368 }
1369
1370 namespace {
1371 struct _NodeEqual
1372 {
1373 template <class T>
operator ()__anon2d62f9890411::_NodeEqual1374 inline bool operator()(T const &a, T const &b) const {
1375 return a == b;
1376 }
1377 };
1378 }
1379
1380 std::pair<SdfPath, SdfPath>
RemoveCommonSuffix(const SdfPath & otherPath,bool stopAtRootPrim) const1381 SdfPath::RemoveCommonSuffix(const SdfPath& otherPath,
1382 bool stopAtRootPrim) const {
1383
1384 if (IsEmpty() || otherPath.IsEmpty() ||
1385 (static_cast<bool>(_propPart) ^
1386 static_cast<bool>(otherPath._propPart))) {
1387 return std::make_pair(*this, otherPath);
1388 }
1389
1390 // Scan upwards until we find a difference or a root node or child of
1391 // a root node. Root nodes have element counts of 0 and their children
1392 // elements counts of 1.
1393
1394 if (_propPart) {
1395 Sdf_PathNode const *thisProp = _propPart.get();
1396 Sdf_PathNode const *otherProp = otherPath._propPart.get();
1397 while (thisProp && otherProp) {
1398 if (!thisProp->Compare<_NodeEqual>(*otherProp)) {
1399 return std::make_pair(
1400 SdfPath(_primPart,
1401 Sdf_PathPropNodeHandle(thisProp)),
1402 SdfPath(otherPath._primPart,
1403 Sdf_PathPropNodeHandle(otherProp)));
1404 }
1405 thisProp = thisProp->GetParentNode();
1406 otherProp = otherProp->GetParentNode();
1407 }
1408 if (thisProp || otherProp) {
1409 return std::make_pair(
1410 SdfPath(_primPart, Sdf_PathPropNodeHandle(thisProp)),
1411 SdfPath(otherPath._primPart,
1412 Sdf_PathPropNodeHandle(otherProp)));
1413 }
1414 }
1415
1416 Sdf_PathNode const *thisPrim = _primPart.get();
1417 Sdf_PathNode const *otherPrim = otherPath._primPart.get();
1418
1419 while (thisPrim->GetElementCount() > 1 &&
1420 otherPrim->GetElementCount() > 1) {
1421 if (!thisPrim->Compare<_NodeEqual>(*otherPrim)) {
1422 return std::make_pair(SdfPath(thisPrim, nullptr),
1423 SdfPath(otherPrim, nullptr));
1424 }
1425 thisPrim = thisPrim->GetParentNode();
1426 otherPrim = otherPrim->GetParentNode();
1427 }
1428
1429 // If stopAtRootPrim is not true and neither path is a root then we
1430 // can scan upwards one more level.
1431 if (!stopAtRootPrim &&
1432 thisPrim->GetElementCount() >= 1 &&
1433 otherPrim->GetElementCount() >= 1 &&
1434 thisPrim->Compare<_NodeEqual>(*otherPrim)) {
1435 thisPrim = thisPrim->GetParentNode();
1436 otherPrim = otherPrim->GetParentNode();
1437 }
1438 return std::make_pair(SdfPath(thisPrim, nullptr),
1439 SdfPath(otherPrim, nullptr));
1440 }
1441
1442 SdfPath
ReplaceTargetPath(const SdfPath & newTargetPath) const1443 SdfPath::ReplaceTargetPath(const SdfPath &newTargetPath) const {
1444
1445 if (IsEmpty()) {
1446 return SdfPath();
1447 }
1448
1449 if (newTargetPath == SdfPath()) {
1450 TF_WARN("ReplaceTargetPath(): invalid new target path.");
1451 return SdfPath();
1452 }
1453
1454 if (_propPart) {
1455 Sdf_PathNode const *propNode = _propPart.get();
1456 Sdf_PathNode::NodeType type = _propPart->GetNodeType();
1457 if (type == Sdf_PathNode::TargetNode) {
1458 return GetParentPath().AppendTarget(newTargetPath);
1459 } else if (type == Sdf_PathNode::RelationalAttributeNode) {
1460 return GetParentPath().ReplaceTargetPath(newTargetPath).
1461 AppendRelationalAttribute(propNode->GetName());
1462 } else if (type == Sdf_PathNode::MapperNode) {
1463 return GetParentPath().AppendMapper(newTargetPath);
1464 } else if (type == Sdf_PathNode::MapperArgNode) {
1465 return GetParentPath().ReplaceTargetPath(newTargetPath).
1466 AppendMapperArg(propNode->GetName());
1467 } else if (type == Sdf_PathNode::ExpressionNode) {
1468 return GetParentPath().ReplaceTargetPath(newTargetPath).
1469 AppendExpression();
1470 }
1471 }
1472
1473 // no target to replace
1474 // return path unchanged
1475 return *this;
1476 }
1477
1478 SdfPath
MakeAbsolutePath(const SdfPath & anchor) const1479 SdfPath::MakeAbsolutePath(const SdfPath & anchor) const {
1480
1481 SdfPath result;
1482
1483 if (anchor == SdfPath()) {
1484 TF_WARN("MakeAbsolutePath(): anchor is the empty path.");
1485 return result;
1486 }
1487
1488 // Check that anchor is an absolute path
1489 if (!anchor.IsAbsolutePath()) {
1490 TF_WARN("MakeAbsolutePath() requires an absolute path as an argument.");
1491 return result;
1492 }
1493
1494 // Check that anchor is a prim-like path
1495 if (!anchor.IsAbsoluteRootOrPrimPath() &&
1496 !anchor.IsPrimVariantSelectionPath()) {
1497 TF_WARN("MakeAbsolutePath() requires a prim path as an argument.");
1498 return result;
1499 }
1500
1501 // If we're empty, just return empty.
1502 if (IsEmpty()) {
1503 return result;
1504 }
1505
1506 // If we're not already absolute, do our own path using anchor as the
1507 // relative base.
1508 if (ARCH_LIKELY(!IsAbsolutePath())) {
1509
1510 // Collect all the ancestral path nodes.
1511 Sdf_PathNode const *curNode = _primPart.get();
1512 size_t numNodes = curNode->GetElementCount();
1513 vector<Sdf_PathNode const *> relNodes(numNodes);
1514 while (numNodes--) {
1515 relNodes[numNodes] = curNode;
1516 curNode = curNode->GetParentNode();
1517 }
1518
1519 // Now append all the nodes to the anchor to produce the absolute path.
1520 result = anchor;
1521 for (Sdf_PathNode const *node: relNodes) {
1522 result = _AppendNode(result, node);
1523 if (result.IsEmpty()) {
1524 break;
1525 }
1526 }
1527 }
1528 else {
1529 result = *this;
1530 }
1531
1532 // If we failed to produce a path, return empty. This happens in cases
1533 // where we try to make paths like '../../..' absolute with anchors that are
1534 // shorter, causing us to try to go "outside the root".
1535 if (result.IsEmpty()) {
1536 return result;
1537 }
1538
1539 // Tack on any property path.
1540 result._propPart = _propPart;
1541
1542 // Now make target paths absolute (recursively) if we need to.
1543 // We need to use result's prim path as the anchor for the target path.
1544 SdfPath const &targetPath = result.GetTargetPath();
1545 if (!targetPath.IsEmpty()) {
1546 SdfPath primPath = result.GetPrimPath();
1547 SdfPath newTargetPath = targetPath.MakeAbsolutePath(primPath);
1548 result = result.ReplaceTargetPath(newTargetPath);
1549 }
1550
1551 return result;
1552 }
1553
1554 SdfPath
MakeRelativePath(const SdfPath & anchor) const1555 SdfPath::MakeRelativePath(const SdfPath & anchor) const
1556 {
1557 TRACE_FUNCTION();
1558
1559 // Check that anchor is a valid path
1560 if ( anchor == SdfPath() ) {
1561 TF_WARN("MakeRelativePath(): anchor is the invalid path.");
1562 return SdfPath();
1563 }
1564
1565 // Check that anchor is an absolute path
1566 if (!anchor.IsAbsolutePath()) {
1567 TF_WARN("MakeRelativePath() requires an absolute path as an argument.");
1568 return SdfPath();
1569 }
1570
1571 // Check that anchor is a prim-like path
1572 if (!anchor.IsAbsoluteRootOrPrimPath() &&
1573 !anchor.IsPrimVariantSelectionPath()) {
1574 TF_WARN("MakeRelativePath() requires a prim, prim variant selection, "
1575 "or absolute root path as an anchor (got '%s').",
1576 anchor.GetAsString().c_str());
1577 return SdfPath();
1578 }
1579
1580 // If we're invalid, just return a copy of ourselves.
1581 if (IsEmpty()) {
1582 return SdfPath();
1583 }
1584
1585 if (!IsAbsolutePath()) {
1586 // Canonicalize... make sure the relative path has the
1587 // fewest possible dot-dots.
1588 SdfPath absPath = MakeAbsolutePath(anchor);
1589 return absPath.MakeRelativePath(anchor);
1590 }
1591
1592 // We are absolute, we want to be relative
1593
1594 // This list winds up in reverse order to what one might at first expect.
1595 vector<Sdf_PathNode const *> relNodes;
1596
1597 // We need to crawl up the this path until we are the same length as
1598 // the anchor.
1599 // Then we crawl up both till we find the matching nodes.
1600 // As we crawl, we build the relNodes vector.
1601 size_t thisCount = _primPart->GetElementCount();
1602 size_t anchorCount = anchor._primPart->GetElementCount();
1603
1604 Sdf_PathNode const *curThisNode = _primPart.get();
1605 Sdf_PathNode const *curAnchorNode = anchor._primPart.get();
1606
1607 // walk to the same depth
1608 size_t dotdotCount = 0;
1609
1610 while (thisCount > anchorCount) {
1611 relNodes.push_back(curThisNode);
1612 curThisNode = curThisNode->GetParentNode();
1613 --thisCount;
1614 }
1615
1616 while (thisCount < anchorCount) {
1617 ++dotdotCount;
1618 curAnchorNode = curAnchorNode->GetParentNode();
1619 --anchorCount;
1620 }
1621
1622 // now we're at the same depth
1623 TF_AXIOM(thisCount == anchorCount);
1624
1625 // walk to a common prefix
1626 while (curThisNode != curAnchorNode) {
1627 ++dotdotCount;
1628 relNodes.push_back(curThisNode);
1629 curThisNode = curThisNode->GetParentNode();
1630 curAnchorNode = curAnchorNode->GetParentNode();
1631 }
1632
1633 // Now relNodes the nodes of this path after the prefix
1634 // common to anchor and this path.
1635 SdfPath result = ReflexiveRelativePath();
1636
1637 // Start by adding dotdots
1638 while (dotdotCount--) {
1639 result = result.GetParentPath();
1640 }
1641
1642 // Now add nodes similar to relNodes to the ReflexiveRelativePath()
1643 // relNodes needs to be iterated in reverse since the closest ancestor
1644 // node was pushed on last.
1645 for (auto it = relNodes.rbegin(); it != relNodes.rend(); ++it) {
1646 result = _AppendNode(result, *it);
1647 }
1648
1649 // Tack on any property part.
1650 result._propPart = _propPart;
1651
1652 return result;
1653 }
1654
_IsValidIdentifier(TfToken const & name)1655 static inline bool _IsValidIdentifier(TfToken const &name)
1656 {
1657 return TfIsValidIdentifier(name.GetString());
1658 }
1659
1660 bool
IsValidIdentifier(const std::string & name)1661 SdfPath::IsValidIdentifier(const std::string &name)
1662 {
1663 return TfIsValidIdentifier(name);
1664 }
1665
1666 // We use our own _IsAlpha and _IsAlnum here for two reasons. One, we want to
1667 // ensure that they follow C/Python identifier rules and are not subject to
1668 // various locale differences. And two, since we are not consulting a locale,
1669 // it is faster.
_IsAlpha(int x)1670 static constexpr bool _IsAlpha(int x) {
1671 return ('a' <= (x|32)) && ((x|32) <= 'z');
1672 }
_IsAlnum(int x)1673 static constexpr bool _IsAlnum(int x) {
1674 return _IsAlpha(x) || (('0' <= x) && (x <= '9'));
1675 }
1676
1677 bool
IsValidNamespacedIdentifier(const std::string & name)1678 SdfPath::IsValidNamespacedIdentifier(const std::string &name)
1679 {
1680 // A valid C/Python identifier except we also allow the namespace delimiter
1681 // and if we tokenize on that delimiter then all tokens are valid C/Python
1682 // identifiers. That means following a delimiter there must be an '_' or
1683 // alphabetic character.
1684 constexpr char delim = SDF_PATH_NS_DELIMITER_CHAR;
1685 for (char const *p = name.c_str(); *p; ++p) {
1686 if (!_IsAlpha(*p) && *p != '_') {
1687 return false;
1688 }
1689 for (++p; _IsAlnum(*p) ||*p == '_'; ++p) {
1690 /* consume identifier */
1691 }
1692 if (*p != delim) {
1693 return !*p;
1694 }
1695 }
1696 return false;
1697 }
1698
1699 std::vector<std::string>
TokenizeIdentifier(const std::string & name)1700 SdfPath::TokenizeIdentifier(const std::string &name)
1701 {
1702 std::vector<std::string> result;
1703
1704 // This code currently assumes the namespace delimiter is one character.
1705 const char namespaceDelimiter =
1706 SdfPathTokens->namespaceDelimiter.GetText()[0];
1707
1708 std::string::const_iterator first = name.begin();
1709 std::string::const_iterator last = name.end();
1710
1711 // Not empty and first character is alpha or '_'.
1712 if (first == last || !(isalpha(*first) || (*first == '_')))
1713 return result;
1714 // Last character is not the namespace delimiter.
1715 if (*(last - 1) == namespaceDelimiter)
1716 return result;
1717
1718 // Count delimiters and reserve space in result.
1719 result.reserve(1 + std::count(first, last, namespaceDelimiter));
1720
1721 std::string::const_iterator anchor = first;
1722 for (++first; first != last; ++first) {
1723 // Allow a namespace delimiter.
1724 if (*first == namespaceDelimiter) {
1725 // Record token.
1726 result.push_back(std::string(anchor, first));
1727
1728 // Skip delimiter. We know we will not go beyond the end of
1729 // the string because we checked before the loop that the
1730 // last character was not the delimiter.
1731 anchor = ++first;
1732
1733 // First character.
1734 if (!(isalpha(*first) || (*first == '_'))) {
1735 TfReset(result);
1736 return result;
1737 }
1738 }
1739 else {
1740 // Next character
1741 if (!(isalnum(*first) || (*first == '_'))) {
1742 TfReset(result);
1743 return result;
1744 }
1745 }
1746 }
1747
1748 // Record the last token.
1749 result.push_back(std::string(anchor, first));
1750
1751 return result;
1752 }
1753
1754 TfTokenVector
TokenizeIdentifierAsTokens(const std::string & name)1755 SdfPath::TokenizeIdentifierAsTokens(const std::string &name)
1756 {
1757 std::vector<std::string> tmp = TokenizeIdentifier(name);
1758 TfTokenVector result(tmp.size());
1759 for (size_t i = 0, n = tmp.size(); i != n; ++i) {
1760 TfToken(tmp[i]).Swap(result[i]);
1761 }
1762 return result;
1763 }
1764
1765 std::string
JoinIdentifier(const std::vector<std::string> & names)1766 SdfPath::JoinIdentifier(const std::vector<std::string> &names)
1767 {
1768 if (std::any_of(names.begin(), names.end(),
1769 [](const std::string &s){return s.empty();}))
1770 {
1771 // Create a new vector with just the non-empty names.
1772 std::vector<std::string> nonEmptyNames;
1773 nonEmptyNames.reserve(names.size());
1774 std::copy_if(names.begin(), names.end(),
1775 std::back_inserter(nonEmptyNames),
1776 [](const std::string &s){return !s.empty();});
1777 return TfStringJoin(nonEmptyNames,
1778 SdfPathTokens->namespaceDelimiter.GetText());
1779 }
1780 return TfStringJoin(names, SdfPathTokens->namespaceDelimiter.GetText());
1781 }
1782
1783 std::string
JoinIdentifier(const TfTokenVector & names)1784 SdfPath::JoinIdentifier(const TfTokenVector& names)
1785 {
1786 std::vector<std::string> tmp;
1787 tmp.reserve(names.size());
1788 for (size_t i = 0, n = names.size(); i != n; ++i) {
1789 if (!names[i].IsEmpty()) {
1790 tmp.push_back(names[i].GetString());
1791 }
1792 }
1793 return TfStringJoin(tmp, SdfPathTokens->namespaceDelimiter.GetText());
1794 }
1795
1796 std::string
JoinIdentifier(const std::string & lhs,const std::string & rhs)1797 SdfPath::JoinIdentifier(const std::string &lhs, const std::string &rhs)
1798 {
1799 if (lhs.empty()) {
1800 return rhs;
1801 }
1802 else if (rhs.empty()) {
1803 return lhs;
1804 }
1805 else {
1806 return lhs + SdfPathTokens->namespaceDelimiter.GetText() + rhs;
1807 }
1808 }
1809
1810 std::string
JoinIdentifier(const TfToken & lhs,const TfToken & rhs)1811 SdfPath::JoinIdentifier(const TfToken &lhs, const TfToken &rhs)
1812 {
1813 return JoinIdentifier(lhs.GetString(), rhs.GetString());
1814 }
1815
1816 std::string
StripNamespace(const std::string & name)1817 SdfPath::StripNamespace(const std::string &name)
1818 {
1819 // This code currently assumes the namespace delimiter is one character.
1820 const char namespaceDelimiter =
1821 SdfPathTokens->namespaceDelimiter.GetText()[0];
1822 const std::string::size_type n = name.rfind(namespaceDelimiter);
1823 return n == std::string::npos ? name : name.substr(n + 1);
1824 }
1825
1826 TfToken
StripNamespace(const TfToken & name)1827 SdfPath::StripNamespace(const TfToken &name)
1828 {
1829 return TfToken(StripNamespace(name.GetString()));
1830 }
1831
1832 std::pair<std::string, bool>
StripPrefixNamespace(const std::string & name,const std::string & matchNamespace)1833 SdfPath::StripPrefixNamespace(const std::string &name,
1834 const std::string &matchNamespace)
1835 {
1836 static const char namespaceDelimiter =
1837 SdfPathTokens->namespaceDelimiter.GetText()[0];
1838
1839 if (matchNamespace.empty()) {
1840 return std::make_pair(name, false);
1841 }
1842
1843 if (TfStringStartsWith(name, matchNamespace)) {
1844
1845 size_t matchNamespaceLen = matchNamespace.size();
1846
1847 // Now check to make sure the next character is the namespace delimiter
1848 if (matchNamespace[matchNamespaceLen - 1] == namespaceDelimiter) {
1849
1850 // The matched namespace already contained the end delimiter,
1851 // nothing more to do.
1852 return std::make_pair(name.substr(matchNamespaceLen), true);
1853
1854 } else {
1855
1856 // The matched namespace needs an extra delimiter ':' so check for
1857 // it now.
1858 if (name[matchNamespaceLen] == namespaceDelimiter) {
1859 return std::make_pair(name.substr(matchNamespaceLen + 1), true);
1860 }
1861
1862 }
1863 }
1864
1865 return std::make_pair(name, false);
1866 }
1867
1868 bool
IsValidPathString(const std::string & pathString,std::string * errMsg)1869 SdfPath::IsValidPathString(const std::string &pathString,
1870 std::string *errMsg)
1871 {
1872 Sdf_PathParserContext context;
1873
1874 // Initialize the scanner, allowing it to be reentrant.
1875 pathYylex_init(&context.scanner);
1876
1877 yy_buffer_state *b =
1878 pathYy_scan_bytes(pathString.c_str(), pathString.size(),
1879 context.scanner);
1880
1881 bool valid = (pathYyparse(&context) == 0);
1882
1883 if (!valid && errMsg)
1884 *errMsg = context.errStr;
1885
1886 // Clean up.
1887 pathYy_delete_buffer(b, context.scanner);
1888 pathYylex_destroy(context.scanner);
1889
1890 return valid;
1891 }
1892
1893 // Caller ensures both absolute or both relative. We need to crawl up the
1894 // longer path until both are the same length. Then we crawl up both until we
1895 // find the nodes whose parents match. Then we can compare those nodes.
1896 static inline bool
_LessThanCompareNodes(Sdf_PathNode const * l,Sdf_PathNode const * r)1897 _LessThanCompareNodes(Sdf_PathNode const *l, Sdf_PathNode const *r)
1898 {
1899 // Internally element counts are 'short', so this cast is safe.
1900 int lCount = static_cast<int>(l->GetElementCount());
1901 int rCount = static_cast<int>(r->GetElementCount());
1902
1903 // Since caller ensures both absolute or both relative, then if either has
1904 // no elements, it's the root node. l is less than r if l is the root and r
1905 // is not.
1906 if (!lCount || !rCount) {
1907 return !lCount && rCount;
1908 }
1909
1910 int diff = rCount - lCount;
1911
1912 // walk up to the same depth
1913 while (diff < 0) {
1914 l = l->GetParentNode();
1915 ++diff;
1916 }
1917 while (diff > 0) {
1918 r = r->GetParentNode();
1919 --diff;
1920 }
1921
1922 // Now the cur nodes are at the same depth in the node tree
1923 if (l == r) {
1924 // They differ only in the tail. If r has the tail, then this is
1925 // less, otherwise r is less.
1926 return lCount < rCount;
1927 }
1928
1929 Sdf_PathNode const *lp = l->GetParentNode();
1930 Sdf_PathNode const *rp = r->GetParentNode();
1931 while (lp != rp) {
1932 l = lp, r = rp;
1933 lp = l->GetParentNode(), rp = r->GetParentNode();
1934 }
1935
1936 // Now parents are equal, compare the current child nodes.
1937 return l->Compare<Sdf_PathNode::LessThan>(*r);
1938 }
1939
1940 bool
_LessThanInternal(SdfPath const & lhs,SdfPath const & rhs)1941 SdfPath::_LessThanInternal(SdfPath const &lhs, SdfPath const &rhs)
1942 {
1943 Sdf_PathNode const *lNode = lhs._primPart.get();
1944 Sdf_PathNode const *rNode = rhs._primPart.get();
1945
1946 bool lIsAbs = lNode->IsAbsolutePath();
1947 bool rIsAbs = rNode->IsAbsolutePath();
1948
1949 // Absolute paths are less than all relative paths.
1950 if (lIsAbs != rIsAbs) {
1951 return lIsAbs;
1952 }
1953
1954 // If there is a difference in prim part, it's more significant than the
1955 // property part.
1956 if (ARCH_LIKELY(lNode != rNode)) {
1957 return _LessThanCompareNodes(lNode, rNode);
1958 }
1959
1960 lNode = lhs._propPart.get(), rNode = rhs._propPart.get();
1961 if (!lNode || !rNode) {
1962 return !lNode;
1963 }
1964 return _LessThanCompareNodes(lNode, rNode);
1965 }
1966
operator <<(std::ostream & out,const SdfPath & path)1967 std::ostream & operator<<( std::ostream &out, const SdfPath &path ) {
1968 return out << path.GetString();
1969 }
1970
1971 SdfPathVector
GetConciseRelativePaths(const SdfPathVector & paths)1972 SdfPath::GetConciseRelativePaths(const SdfPathVector& paths) {
1973
1974 SdfPathVector primPaths;
1975 SdfPathVector anchors;
1976 SdfPathVector labels;
1977
1978 // initialize the vectors
1979 TF_FOR_ALL(iter, paths) {
1980
1981 if(!iter->IsAbsolutePath()) {
1982 TF_WARN("argument to GetConciseRelativePaths contains a relative path.");
1983 return paths;
1984 }
1985
1986 // first, get the prim paths
1987 SdfPath primPath = iter->GetPrimPath();
1988 SdfPath anchor = primPath.GetParentPath();
1989
1990 primPaths.push_back(primPath);
1991 anchors.push_back(anchor);
1992
1993 // we have to special case root anchors, since MakeRelativePath can't handle them
1994 if(anchor == SdfPath::AbsoluteRootPath())
1995 labels.push_back(primPath);
1996 else
1997 labels.push_back(primPath.MakeRelativePath(anchor));
1998
1999 }
2000
2001 // each ambiguous path must be raised to its parent
2002 bool ambiguous;
2003 do {
2004
2005 ambiguous = false;
2006
2007 // the next iteration of labels
2008 SdfPathVector newAnchors;
2009 SdfPathVector newLabels;
2010
2011 // find ambiguous labels
2012 for(size_t i=0;i<labels.size();++i) {
2013
2014 int ok = true;
2015
2016 // search for some other path that makes this one ambiguous
2017 for(size_t j=0;j<labels.size();++j) {
2018 if(i != j && labels[i] == labels[j] && primPaths[i] != primPaths[j]) {
2019 ok = false;
2020 break;
2021 }
2022 }
2023
2024 if(!ok) {
2025
2026 // walk the anchor up one node
2027 SdfPath newAnchor = anchors[i].GetParentPath();
2028
2029 newAnchors.push_back(newAnchor);
2030 newLabels.push_back( newAnchor == SdfPath::AbsoluteRootPath() ? primPaths[i]
2031 : primPaths[i].MakeRelativePath( newAnchor ) );
2032 ambiguous = true;
2033
2034 } else {
2035 newAnchors.push_back(anchors[i]);
2036 newLabels.push_back(labels[i]);
2037 }
2038
2039 }
2040
2041 anchors = newAnchors;
2042 labels = newLabels;
2043
2044 } while(ambiguous);
2045
2046 // generate the final set from the anchors
2047 SdfPathVector result;
2048
2049 for(size_t i=0; i<anchors.size();++i) {
2050
2051 if(anchors[i] == SdfPath::AbsoluteRootPath()) {
2052 result.push_back( paths[i] );
2053 } else {
2054 result.push_back( paths[i].MakeRelativePath( anchors[i] ));
2055 }
2056
2057 }
2058
2059 return result;
2060
2061 }
2062
2063 void
RemoveDescendentPaths(SdfPathVector * paths)2064 SdfPath::RemoveDescendentPaths(SdfPathVector *paths)
2065 {
2066 // To remove descendents, first partition paths into prefix-related groups
2067 // via sort.
2068 std::sort(paths->begin(), paths->end());
2069
2070 // Now unique and erase all descendents. The equivalence predicate returns
2071 // true if rhs has lhs as a prefix.
2072 paths->erase(std::unique(paths->begin(), paths->end(),
2073 [](SdfPath const &l, SdfPath const &r) {
2074 return r.HasPrefix(l);
2075 }),
2076 paths->end());
2077 }
2078
2079 void
RemoveAncestorPaths(SdfPathVector * paths)2080 SdfPath::RemoveAncestorPaths(SdfPathVector *paths)
2081 {
2082 // To remove ancestors, first parition paths into prefix-related groups
2083 // via sort.
2084 std::sort(paths->begin(), paths->end());
2085
2086 // Now unique and erase ancestors. The equivalence predicate returns true
2087 // if lhs has rhs as a prefix.
2088 paths->erase(paths->begin(),
2089 std::unique(paths->rbegin(), paths->rend(),
2090 [](SdfPath const &l, SdfPath const &r) {
2091 return l.HasPrefix(r);
2092 }).base());
2093 }
2094
2095 typename std::set<SdfPath>::const_iterator
SdfPathFindLongestPrefix(std::set<SdfPath> const & set,SdfPath const & path)2096 SdfPathFindLongestPrefix(std::set<SdfPath> const &set, SdfPath const &path)
2097 {
2098 return Sdf_PathFindLongestPrefixImpl<
2099 typename std::set<SdfPath>::const_iterator,
2100 std::set<SdfPath> const &>(set, path, /*strictPrefix=*/false);
2101 }
2102
2103 typename std::set<SdfPath>::const_iterator
SdfPathFindLongestStrictPrefix(std::set<SdfPath> const & set,SdfPath const & path)2104 SdfPathFindLongestStrictPrefix(std::set<SdfPath> const &set,
2105 SdfPath const &path)
2106 {
2107 return Sdf_PathFindLongestPrefixImpl<
2108 typename std::set<SdfPath>::const_iterator,
2109 std::set<SdfPath> const &>(set, path, /*strictPrefix=*/true);
2110 }
2111
2112 SdfPathAncestorsRange::iterator&
operator ++()2113 SdfPathAncestorsRange::iterator::operator++()
2114 {
2115 if (!_path.IsEmpty()) {
2116 const Sdf_PathNode* propPart = nullptr;
2117 const Sdf_PathNode* primPart = nullptr;
2118 if (ARCH_UNLIKELY(_path._propPart)) {
2119 propPart = _path._propPart->GetParentNode();
2120 primPart = _path._primPart.get();
2121 } else if (_path._primPart && _path._primPart->GetElementCount() > 1) {
2122 primPart = _path._primPart->GetParentNode();
2123 }
2124 _path = SdfPath(primPart, propPart);
2125 }
2126 return *this;
2127 }
2128
2129 SDF_API std::ptrdiff_t
distance(const SdfPathAncestorsRange::iterator & first,const SdfPathAncestorsRange::iterator & last)2130 distance(const SdfPathAncestorsRange::iterator& first,
2131 const SdfPathAncestorsRange::iterator& last)
2132 {
2133 return (static_cast<std::ptrdiff_t>(first->GetPathElementCount()) -
2134 static_cast<std::ptrdiff_t>(last->GetPathElementCount()));
2135 }
2136
2137
2138 PXR_NAMESPACE_CLOSE_SCOPE
2139