path.h

//
// Copyright 2016 Pixar
//
// Licensed under the Apache License, Version 2.0 (the "Apache License")
// with the following modification; you may not use this file except in
// compliance with the Apache License and the following modification to it:
// Section 6. Trademarks. is deleted and replaced with:
//
// 6. Trademarks. This License does not grant permission to use the trade
//    names, trademarks, service marks, or product names of the Licensor
//    and its affiliates, except as required to comply with Section 4(c) of
//    the License and to reproduce the content of the NOTICE file.
//
// You may obtain a copy of the Apache License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the Apache License with the above modification is
// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the Apache License for the specific
// language governing permissions and limitations under the Apache License.
//
#ifndef PXR_USD_SDF_PATH_H
#define PXR_USD_SDF_PATH_H

#include "pxr/pxr.h"
#include "pxr/usd/sdf/api.h"
#include "pxr/usd/sdf/pool.h"
#include "pxr/usd/sdf/tokens.h"
#include "pxr/base/tf/stl.h"
#include "pxr/base/tf/token.h"
#include "pxr/base/vt/traits.h"

#include <boost/intrusive_ptr.hpp>
#include <boost/operators.hpp>

#include <algorithm>
#include <iterator>
#include <set>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

PXR_NAMESPACE_OPEN_SCOPE

class Sdf_PathNode;
class SdfPathAncestorsRange;

// Ref-counting pointer to a path node.
// Intrusive ref-counts are used to keep the size of SdfPath
// the same as a raw pointer.  (shared_ptr, by comparison,
// is the size of two pointers.)

typedef boost::intrusive_ptr<const Sdf_PathNode> Sdf_PathNodeConstRefPtr;

void intrusive_ptr_add_ref(Sdf_PathNode const *);
void intrusive_ptr_release(Sdf_PathNode const *);

// Tags used for the pools of path nodes.
struct Sdf_PathPrimTag;
struct Sdf_PathPropTag;

// These are validated below.
static constexpr size_t Sdf_SizeofPrimPathNode = sizeof(void *) * 3;
static constexpr size_t Sdf_SizeofPropPathNode = sizeof(void *) * 3;

using Sdf_PathPrimPartPool = Sdf_Pool<
    Sdf_PathPrimTag, Sdf_SizeofPrimPathNode, /*regionBits=*/8>;

using Sdf_PathPropPartPool = Sdf_Pool<
    Sdf_PathPropTag, Sdf_SizeofPropPathNode, /*regionBits=*/8>;

using Sdf_PathPrimHandle = Sdf_PathPrimPartPool::Handle;
using Sdf_PathPropHandle = Sdf_PathPropPartPool::Handle;

// This handle class wraps up the raw Prim/PropPartPool handles.
template <class Handle, bool Counted, class PathNode=Sdf_PathNode const>
struct Sdf_PathNodeHandleImpl {
private:
    typedef Sdf_PathNodeHandleImpl this_type;

public:
    static constexpr bool IsCounted = Counted;

    constexpr Sdf_PathNodeHandleImpl() noexcept {};

    explicit
    Sdf_PathNodeHandleImpl(Sdf_PathNode const *p, bool add_ref = true)
        : _poolHandle(Handle::GetHandle(reinterpret_cast<char const *>(p))) {
        if (p && add_ref) {
            _AddRef(p);
        }
    }

    explicit
    Sdf_PathNodeHandleImpl(Handle h, bool add_ref = true)
        : _poolHandle(h) {
        if (h && add_ref) {
            _AddRef();
        }
    }

    Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl const &rhs) noexcept
        : _poolHandle(rhs._poolHandle) {
        if (_poolHandle) {
            _AddRef();
        }
    }

    ~Sdf_PathNodeHandleImpl() {
        if (_poolHandle) {
            _DecRef();
        }
    }

    Sdf_PathNodeHandleImpl &
    operator=(Sdf_PathNodeHandleImpl const &rhs) {
        if (Counted && *this == rhs) {
            return *this;
        }
        this_type(rhs).swap(*this);
        return *this;
    }

    Sdf_PathNodeHandleImpl(Sdf_PathNodeHandleImpl &&rhs) noexcept
        : _poolHandle(rhs._poolHandle) {
        rhs._poolHandle = nullptr;
    }

    Sdf_PathNodeHandleImpl &
    operator=(Sdf_PathNodeHandleImpl &&rhs) noexcept {
        this_type(std::move(rhs)).swap(*this);
        return *this;
    }

    Sdf_PathNodeHandleImpl &
    operator=(Sdf_PathNode const *rhs) noexcept {
        this_type(rhs).swap(*this);
        return *this;
    }

    void reset() noexcept {
        _poolHandle = Handle { nullptr };
    }

    inline Sdf_PathNode const *
    get() const noexcept {
        return reinterpret_cast<Sdf_PathNode *>(_poolHandle.GetPtr());
    }

    Sdf_PathNode const &
    operator*() const {
        return *get();
    }

    Sdf_PathNode const *
    operator->() const {
        return get();
    }

    explicit operator bool() const noexcept {
        return static_cast<bool>(_poolHandle);
    }

    void swap(Sdf_PathNodeHandleImpl &rhs) noexcept {
        _poolHandle.swap(rhs._poolHandle);
    }

    inline bool operator==(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
        return _poolHandle == rhs._poolHandle;
    }
    inline bool operator!=(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
        return _poolHandle != rhs._poolHandle;
    }
    inline bool operator<(Sdf_PathNodeHandleImpl const &rhs) const noexcept {
        return _poolHandle < rhs._poolHandle;
    }
private:

    inline void _AddRef(Sdf_PathNode const *p) const {
        if (Counted) {
            intrusive_ptr_add_ref(p);
        }
    }

    inline void _AddRef() const {
        _AddRef(get());
    }

    inline void _DecRef() const {
        if (Counted) {
            intrusive_ptr_release(get());
        }
    }

    Handle _poolHandle { nullptr };
};

using Sdf_PathPrimNodeHandle =
    Sdf_PathNodeHandleImpl<Sdf_PathPrimHandle, /*Counted=*/true>;

using Sdf_PathPropNodeHandle =
    Sdf_PathNodeHandleImpl<Sdf_PathPropHandle, /*Counted=*/false>;


typedef std::set<class SdfPath> SdfPathSet;
typedef std::vector<class SdfPath> SdfPathVector;

// Tell VtValue that SdfPath is cheap to copy.
VT_TYPE_IS_CHEAP_TO_COPY(class SdfPath);

class SdfPath : boost::totally_ordered<SdfPath>
{
public:
    SDF_API static const SdfPath & EmptyPath();

    SDF_API static const SdfPath & AbsoluteRootPath();

    SDF_API static const SdfPath & ReflexiveRelativePath();

    
    SdfPath() noexcept {
        // This generates a single instruction instead of 2 on gcc 6.3.  Seems
        // to be fixed on gcc 7+ and newer clangs.  Remove when we're there!
        memset(this, 0, sizeof(*this));
    }

    //
    // XXX  We may want to revisit the behavior when constructing
    // a path with an empty string ("") to accept it without error and
    // return EmptyPath.
    SDF_API explicit SdfPath(const std::string &path);



    SDF_API size_t GetPathElementCount() const;

    SDF_API bool IsAbsolutePath() const;

    SDF_API bool IsAbsoluteRootPath() const;

    SDF_API bool IsPrimPath() const;

    SDF_API bool IsAbsoluteRootOrPrimPath() const;

    SDF_API bool IsRootPrimPath() const;

    SDF_API bool IsPropertyPath() const;

    SDF_API bool IsPrimPropertyPath() const;

    SDF_API bool IsNamespacedPropertyPath() const;

    SDF_API bool IsPrimVariantSelectionPath() const;

    SDF_API bool IsPrimOrPrimVariantSelectionPath() const;

    SDF_API bool ContainsPrimVariantSelection() const;
    
    bool ContainsPropertyElements() const {
        return static_cast<bool>(_propPart);
    }

    SDF_API bool ContainsTargetPath() const;

    SDF_API bool IsRelationalAttributePath() const;

    SDF_API bool IsTargetPath() const;

    SDF_API bool IsMapperPath() const;

    SDF_API bool IsMapperArgPath() const;

    SDF_API bool IsExpressionPath() const;

    inline bool IsEmpty() const noexcept {
        // No need to check _propPart, because it can only be non-null if
        // _primPart is non-null.
        return !_primPart; 
    }

    SDF_API TfToken GetAsToken() const;

    SDF_API TfToken const &GetToken() const;

    SDF_API std::string GetAsString() const;

    SDF_API const std::string &GetString() const;

    SDF_API const char *GetText() const;

    SDF_API SdfPathVector GetPrefixes() const;

    SDF_API void GetPrefixes(SdfPathVector *prefixes) const;

    SDF_API SdfPathAncestorsRange GetAncestorsRange() const;

    SDF_API const std::string &GetName() const;

    SDF_API const TfToken &GetNameToken() const;
    
    SDF_API std::string GetElementString() const;

    SDF_API TfToken GetElementToken() const;

    SDF_API SdfPath ReplaceName(TfToken const &newName) const;

    SDF_API const SdfPath &GetTargetPath() const;

    SDF_API void GetAllTargetPathsRecursively(SdfPathVector *result) const;

    SDF_API 
    std::pair<std::string, std::string> GetVariantSelection() const;

    SDF_API bool HasPrefix( const SdfPath &prefix ) const;



    SDF_API SdfPath GetParentPath() const;

    SDF_API SdfPath GetPrimPath() const;

    SDF_API SdfPath GetPrimOrPrimVariantSelectionPath() const;

    SDF_API SdfPath GetAbsoluteRootOrPrimPath() const;

    SDF_API SdfPath StripAllVariantSelections() const;

    SDF_API SdfPath AppendPath(const SdfPath &newSuffix) const;

    SDF_API SdfPath AppendChild(TfToken const &childName) const;

    SDF_API SdfPath AppendProperty(TfToken const &propName) const;

    SDF_API 
    SdfPath AppendVariantSelection(const std::string &variantSet,
                                   const std::string &variant) const;

    SDF_API SdfPath AppendTarget(const SdfPath &targetPath) const;

    SDF_API 
    SdfPath AppendRelationalAttribute(TfToken const &attrName) const;

    SDF_API 
    SdfPath ReplaceTargetPath( const SdfPath &newTargetPath ) const;

    SDF_API SdfPath AppendMapper(const SdfPath &targetPath) const;

    SDF_API SdfPath AppendMapperArg(TfToken const &argName) const;

    SDF_API SdfPath AppendExpression() const;

    SDF_API SdfPath AppendElementString(const std::string &element) const;

    SDF_API SdfPath AppendElementToken(const TfToken &elementTok) const;

    SDF_API 
    SdfPath ReplacePrefix(const SdfPath &oldPrefix,
                          const SdfPath &newPrefix,
                          bool fixTargetPaths=true) const;

    SDF_API SdfPath GetCommonPrefix(const SdfPath &path) const;

    SDF_API 
    std::pair<SdfPath, SdfPath>
    RemoveCommonSuffix(const SdfPath& otherPath,
                       bool stopAtRootPrim = false) const;

    SDF_API SdfPath MakeAbsolutePath(const SdfPath & anchor) const;

    SDF_API SdfPath MakeRelativePath(const SdfPath & anchor) const;



    SDF_API static bool IsValidIdentifier(const std::string &name);

    SDF_API static bool IsValidNamespacedIdentifier(const std::string &name);

    SDF_API static std::vector<std::string> TokenizeIdentifier(const std::string &name);

    SDF_API
    static TfTokenVector TokenizeIdentifierAsTokens(const std::string &name);

    SDF_API 
    static std::string JoinIdentifier(const std::vector<std::string> &names);

    SDF_API 
    static std::string JoinIdentifier(const TfTokenVector& names);

    SDF_API 
    static std::string JoinIdentifier(const std::string &lhs,
                                      const std::string &rhs);

    SDF_API 
    static std::string JoinIdentifier(const TfToken &lhs, const TfToken &rhs);

    SDF_API
    static std::string StripNamespace(const std::string &name);

    SDF_API
    static TfToken StripNamespace(const TfToken &name);

    SDF_API
    static std::pair<std::string, bool> 
    StripPrefixNamespace(const std::string &name, 
                         const std::string &matchNamespace);

    SDF_API
    static bool IsValidPathString(const std::string &pathString,
                                  std::string *errMsg = 0);



    inline bool operator==(const SdfPath &rhs) const {
        return _AsInt() == rhs._AsInt();
    }

    inline bool operator<(const SdfPath &rhs) const {
        if (_AsInt() == rhs._AsInt()) {
            return false;
        }
        if (!_primPart || !rhs._primPart) {
            return !_primPart && rhs._primPart;
        }
        // Valid prim parts -- must walk node structure, etc.
        return _LessThanInternal(*this, rhs);
    }

    template <class HashState>
    friend void TfHashAppend(HashState &h, SdfPath const &path) {
        // The hash function is pretty sensitive performance-wise.  Be
        // careful making changes here, and run tests.
        uint32_t primPart, propPart;
        memcpy(&primPart, &path._primPart, sizeof(primPart));
        memcpy(&propPart, &path._propPart, sizeof(propPart));
        h.Append(primPart);
        h.Append(propPart);
    }

    // For hash maps and sets
    struct Hash {
        inline size_t operator()(const SdfPath& path) const {
            return TfHash()(path);
        }
    };

    inline size_t GetHash() const {
        return Hash()(*this);
    }

    // For cases where an unspecified total order that is not stable from
    // run-to-run is needed.
    struct FastLessThan {
        inline bool operator()(const SdfPath& a, const SdfPath& b) const {
            return a._AsInt() < b._AsInt();
        }
    };



    SDF_API static SdfPathVector
    GetConciseRelativePaths(const SdfPathVector& paths);

    SDF_API static void RemoveDescendentPaths(SdfPathVector *paths);

    SDF_API static void RemoveAncestorPaths(SdfPathVector *paths);


private:

    // This is used for all internal path construction where we do operations
    // via nodes and then want to return a new path with a resulting prim and
    // property parts.

    // Accept rvalues.
    explicit SdfPath(Sdf_PathPrimNodeHandle &&primNode)
        : _primPart(std::move(primNode)) {}

    SdfPath(Sdf_PathPrimNodeHandle &&primPart,
            Sdf_PathPropNodeHandle &&propPart)
        : _primPart(std::move(primPart))
        , _propPart(std::move(propPart)) {}

    // Construct from prim & prop parts.
    SdfPath(Sdf_PathPrimNodeHandle const &primPart,
            Sdf_PathPropNodeHandle const &propPart)
        : _primPart(primPart)
        , _propPart(propPart) {}

    // Construct from prim & prop node pointers.
    SdfPath(Sdf_PathNode const *primPart,
            Sdf_PathNode const *propPart)
        : _primPart(primPart)
        , _propPart(propPart) {}

    friend class Sdf_PathNode;
    friend class Sdfext_PathAccess;
    friend class SdfPathAncestorsRange;

    // converts elements to a string for parsing (unfortunate)
    static std::string
    _ElementsToString(bool absolute, const std::vector<std::string> &elements);

    SdfPath _ReplacePrimPrefix(SdfPath const &oldPrefix,
                               SdfPath const &newPrefix) const;

    SdfPath _ReplaceTargetPathPrefixes(SdfPath const &oldPrefix,
                                       SdfPath const &newPrefix) const;

    SdfPath _ReplacePropPrefix(SdfPath const &oldPrefix,
                               SdfPath const &newPrefix,
                               bool fixTargetPaths) const;

    // Helper to implement the uninlined portion of operator<.
    SDF_API static bool
    _LessThanInternal(SdfPath const &lhs, SdfPath const &rhs);

    inline uint64_t _AsInt() const {
        static_assert(sizeof(*this) == sizeof(uint64_t), "");
        uint64_t ret;
        std::memcpy(&ret, this, sizeof(*this));
        return ret;
    }

    friend void swap(SdfPath &lhs, SdfPath &rhs) {
        lhs._primPart.swap(rhs._primPart);
        lhs._propPart.swap(rhs._propPart);
    }

    SDF_API friend char const *
    Sdf_PathGetDebuggerPathText(SdfPath const &);

    Sdf_PathPrimNodeHandle _primPart;
    Sdf_PathPropNodeHandle _propPart;

};


class SdfPathAncestorsRange
{
public:

    SdfPathAncestorsRange(const SdfPath& path)
        : _path(path) {}

    const SdfPath& GetPath() const { return _path; }

    struct iterator {
        using iterator_category = std::forward_iterator_tag;
        using value_type = SdfPath;
        using difference_type = std::ptrdiff_t;
        using reference = const SdfPath&;
        using pointer = const SdfPath*;

        iterator(const SdfPath& path) : _path(path) {}

        iterator() = default;

        SDF_API
        iterator& operator++();

        const SdfPath& operator*() const { return _path; }

        const SdfPath* operator->() const { return &_path; }
        
        bool operator==(const iterator& o) const { return _path == o._path; }

        bool operator!=(const iterator& o) const { return _path != o._path; }

        SDF_API friend difference_type  
        distance(const iterator& first, const iterator& last);

    private:
        SdfPath _path;
    };

    iterator begin() const { return iterator(_path); }

    iterator end() const { return iterator(); }

private:
    SdfPath _path;
};


// Overload hash_value for SdfPath.  Used by things like boost::hash.
inline size_t hash_value(SdfPath const &path)
{
    return path.GetHash();
}

SDF_API std::ostream & operator<<( std::ostream &out, const SdfPath &path );

// Helper for SdfPathFindPrefixedRange & SdfPathFindLongestPrefix.  A function
// object that returns an SdfPath const & unchanged.
struct Sdf_PathIdentity {
    inline SdfPath const &operator()(SdfPath const &arg) const {
        return arg;
    }
};

template <class ForwardIterator, class GetPathFn = Sdf_PathIdentity>
std::pair<ForwardIterator, ForwardIterator>
SdfPathFindPrefixedRange(ForwardIterator begin, ForwardIterator end,
                         SdfPath const &prefix,
                         GetPathFn const &getPath = GetPathFn()) {
    using IterRef = 
        typename std::iterator_traits<ForwardIterator>::reference;

    struct Compare {
        Compare(GetPathFn const &getPath) : _getPath(getPath) {}
        GetPathFn const &_getPath;
        bool operator()(IterRef a, SdfPath const &b) const {
            return _getPath(a) < b;
        }
    };

    std::pair<ForwardIterator, ForwardIterator> result;

    // First, use lower_bound to find where \a prefix would go.
    result.first = std::lower_bound(begin, end, prefix, Compare(getPath));

    // Next, find end of range starting from the lower bound, using the
    // prefixing condition to define the boundary.
    result.second = TfFindBoundary(result.first, end,
                                   [&prefix, &getPath](IterRef iterRef) {
                                       return getPath(iterRef).HasPrefix(prefix);
                                   });

    return result;
}

template <class RandomAccessIterator, class GetPathFn>
RandomAccessIterator
Sdf_PathFindLongestPrefixImpl(RandomAccessIterator begin,
                              RandomAccessIterator end,
                              SdfPath const &path,
                              bool strictPrefix,
                              GetPathFn const &getPath)
{
    using IterRef = 
        typename std::iterator_traits<RandomAccessIterator>::reference;

    struct Compare {
        Compare(GetPathFn const &getPath) : _getPath(getPath) {}
        GetPathFn const &_getPath;
        bool operator()(IterRef a, SdfPath const &b) const {
            return _getPath(a) < b;
        }
    };

    // Search for the path in [begin, end).  If present, return it.  If not,
    // examine prior element in [begin, end).  If none, return end.  Else, is it
    // a prefix of path?  If so, return it.  Else find common prefix of that
    // element and path and recurse.

    // If empty sequence, return.
    if (begin == end)
        return end;

    Compare comp(getPath);

    // Search for where this path would lexicographically appear in the range.
    RandomAccessIterator result = std::lower_bound(begin, end, path, comp);

    // If we didn't get the end, check to see if we got the path exactly if
    // we're not looking for a strict prefix.
    if (!strictPrefix && result != end && getPath(*result) == path) {
        return result;
    }

    // If we got begin (and didn't match in the case of a non-strict prefix)
    // then there's no prefix.
    if (result == begin) {
        return end;
    }

    // If the prior element is a prefix, we're done.
    if (path.HasPrefix(getPath(*--result))) {
        return result;
    }

    // Otherwise, find the common prefix of the lexicographical predecessor and
    // look for its prefix in the preceding range.
    SdfPath newPath = path.GetCommonPrefix(getPath(*result));
    auto origEnd = end;
    do {
        end = result;
        result = std::lower_bound(begin, end, newPath, comp);

        if (result != end && getPath(*result) == newPath) {
            return result;
        }
        if (result == begin) {
            return origEnd;
        }
        if (newPath.HasPrefix(getPath(*--result))) {
            return result;
        }
        newPath = newPath.GetCommonPrefix(getPath(*result));
    } while (true);
}

template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
          class = typename std::enable_if<
              std::is_base_of<
                  std::random_access_iterator_tag,
                  typename std::iterator_traits<
                      RandomAccessIterator>::iterator_category
                  >::value
              >::type
          >
RandomAccessIterator
SdfPathFindLongestPrefix(RandomAccessIterator begin,
                         RandomAccessIterator end,
                         SdfPath const &path,
                         GetPathFn const &getPath = GetPathFn())
{
    return Sdf_PathFindLongestPrefixImpl(
        begin, end, path, /*strictPrefix=*/false, getPath);
}

template <class RandomAccessIterator, class GetPathFn = Sdf_PathIdentity,
          class = typename std::enable_if<
              std::is_base_of<
                  std::random_access_iterator_tag,
                  typename std::iterator_traits<
                      RandomAccessIterator>::iterator_category
                  >::value
              >::type
          >
RandomAccessIterator
SdfPathFindLongestStrictPrefix(RandomAccessIterator begin,
                               RandomAccessIterator end,
                               SdfPath const &path,
                               GetPathFn const &getPath = GetPathFn())
{
    return Sdf_PathFindLongestPrefixImpl(
        begin, end, path, /*strictPrefix=*/true, getPath);
}

template <class Iter, class MapParam, class GetPathFn = Sdf_PathIdentity>
Iter
Sdf_PathFindLongestPrefixImpl(
    MapParam map, SdfPath const &path, bool strictPrefix,
    GetPathFn const &getPath = GetPathFn())
{
    // Search for the path in map.  If present, return it.  If not, examine
    // prior element in map.  If none, return end.  Else, is it a prefix of
    // path?  If so, return it.  Else find common prefix of that element and
    // path and recurse.

    const Iter mapEnd = map.end();

    // If empty, return.
    if (map.empty())
        return mapEnd;

    // Search for where this path would lexicographically appear in the range.
    Iter result = map.lower_bound(path);

    // If we didn't get the end, check to see if we got the path exactly if
    // we're not looking for a strict prefix.
    if (!strictPrefix && result != mapEnd && getPath(*result) == path)
        return result;

    // If we got begin (and didn't match in the case of a non-strict prefix)
    // then there's no prefix.
    if (result == map.begin())
        return mapEnd;

    // If the prior element is a prefix, we're done.
    if (path.HasPrefix(getPath(*--result)))
        return result;

    // Otherwise, find the common prefix of the lexicographical predecessor and
    // recurse looking for it or its longest prefix in the preceding range.  We
    // always pass strictPrefix=false, since now we're operating on prefixes of
    // the original caller's path.
    return Sdf_PathFindLongestPrefixImpl<Iter, MapParam>(
        map, path.GetCommonPrefix(getPath(*result)), /*strictPrefix=*/false,
        getPath);
}

SDF_API
typename std::set<SdfPath>::const_iterator
SdfPathFindLongestPrefix(std::set<SdfPath> const &set, SdfPath const &path);

template <class T>
typename std::map<SdfPath, T>::const_iterator
SdfPathFindLongestPrefix(std::map<SdfPath, T> const &map, SdfPath const &path)
{
    return Sdf_PathFindLongestPrefixImpl<
        typename std::map<SdfPath, T>::const_iterator,
        std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/false,
                                      TfGet<0>());
}
template <class T>
typename std::map<SdfPath, T>::iterator
SdfPathFindLongestPrefix(std::map<SdfPath, T> &map, SdfPath const &path)
{
    return Sdf_PathFindLongestPrefixImpl<
        typename std::map<SdfPath, T>::iterator,
        std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/false,
                                TfGet<0>());
}

SDF_API
typename std::set<SdfPath>::const_iterator
SdfPathFindLongestStrictPrefix(std::set<SdfPath> const &set,
                               SdfPath const &path);

template <class T>
typename std::map<SdfPath, T>::const_iterator
SdfPathFindLongestStrictPrefix(
    std::map<SdfPath, T> const &map, SdfPath const &path)
{
    return Sdf_PathFindLongestPrefixImpl<
        typename std::map<SdfPath, T>::const_iterator,
        std::map<SdfPath, T> const &>(map, path, /*strictPrefix=*/true,
                                      TfGet<0>());
}
template <class T>
typename std::map<SdfPath, T>::iterator
SdfPathFindLongestStrictPrefix(
    std::map<SdfPath, T> &map, SdfPath const &path)
{
    return Sdf_PathFindLongestPrefixImpl<
        typename std::map<SdfPath, T>::iterator,
        std::map<SdfPath, T> &>(map, path, /*strictPrefix=*/true,
                                TfGet<0>());
}

// A helper function for debugger pretty-printers, etc.  This function is *not*
// thread-safe.  It writes to a static buffer and returns a pointer to it.
// Subsequent calls to this function overwrite the memory written in prior
// calls.  If the given path's string representation exceeds the static buffer
// size, return a pointer to a message indicating so.
SDF_API
char const *
Sdf_PathGetDebuggerPathText(SdfPath const &);

PXR_NAMESPACE_CLOSE_SCOPE

// Sdf_PathNode is not public API, but we need to include it here
// so we can inline the ref-counting operations, which must manipulate
// its internal _refCount member.
#include "pxr/usd/sdf/pathNode.h"

PXR_NAMESPACE_OPEN_SCOPE

static_assert(Sdf_SizeofPrimPathNode == sizeof(Sdf_PrimPathNode), "");
static_assert(Sdf_SizeofPropPathNode == sizeof(Sdf_PrimPropertyPathNode), "");

PXR_NAMESPACE_CLOSE_SCOPE

#endif // PXR_USD_SDF_PATH_H