pathExpressionEval.h

//
// Copyright 2023 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_EXPRESSION_EVAL_H
#define PXR_USD_SDF_PATH_EXPRESSION_EVAL_H
 
#include "pxr/pxr.h"
#include "pxr/usd/sdf/api.h"
#include "pxr/usd/sdf/path.h"
#include "pxr/usd/sdf/pathExpression.h"
#include "pxr/usd/sdf/predicateExpression.h"
#include "pxr/usd/sdf/predicateLibrary.h"
#include "pxr/usd/sdf/predicateProgram.h"
 
#include "pxr/base/arch/regex.h"
#include "pxr/base/tf/functionRef.h"
 
#include <string>
#include <type_traits>
#include <vector>
 
PXR_NAMESPACE_OPEN_SCOPE
 
// fwd decl
template <class DomainType>
class SdfPathExpressionEval;
 
// fwd decl
template <class DomainType>
SdfPathExpressionEval<DomainType>
SdfMakePathExpressionEval(SdfPathExpression const &expr,
                          SdfPredicateLibrary<DomainType> const &lib);
 
// fwd decl
class Sdf_PathExpressionEvalBase;
 
// Helper base class for SdfPathExpressionEval.  This factors out as much
// template-parameter independent code as possible to reduce bloat & compile
// times.
class Sdf_PathExpressionEvalBase
{
public:
    friend SDF_API bool
    Sdf_MakePathExpressionEvalImpl(
        Sdf_PathExpressionEvalBase &eval,
        SdfPathExpression const &expr,
        TfFunctionRef<
        void (SdfPathExpression::PathPattern const &)> translatePattern);
 
    bool IsEmpty() const {
        return _ops.empty();
    }        
 
    explicit operator bool() const {
        return !IsEmpty();
    }
 
protected:
    class _PatternImplBase;
    
    class _PatternIncrSearchState {
        friend class _PatternImplBase;
    public:
        void Pop(int newDepth) {
            while (!_segmentMatchDepths.empty() &&
                   _segmentMatchDepths.back() >= newDepth) {
                _segmentMatchDepths.pop_back();
            }
            if (newDepth <= _constantDepth) {
                _constantDepth = -1;
            }
        }
    private:
        std::vector<int> _segmentMatchDepths;
        int _constantDepth = -1; // 0 means constant at the _prefix level.
        bool _constantValue = false;
    };
 
    class _PatternImplBase {
    protected:
        // This is not a constructor because the subclass wants to invoke this
        // from its ctor, TfFunctionRef currently requires an lvalue, which is
        // hard to conjure in a ctor initializer list.
        SDF_API
        void _Init(SdfPathExpression::PathPattern const &pattern,
                   TfFunctionRef<
                   int (SdfPredicateExpression const &)> linkPredicate);
 
        SDF_API
        SdfPredicateFunctionResult
        _Match(
            SdfPath const &path,
            TfFunctionRef<SdfPredicateFunctionResult (int, SdfPath const &)>
            runNthPredicate) const;
 
        SDF_API
        SdfPredicateFunctionResult
        _Next(_PatternIncrSearchState &searchState,
              SdfPath const &path,
              TfFunctionRef<SdfPredicateFunctionResult (int, SdfPath const &)>
              runNthPredicate) const;
 
        enum _ComponentType {
            ExplicitName,      // an explicit name (not a glob pattern).
            Regex              // a glob pattern (handled via regex).
        };
 
        struct _Component {
            _ComponentType type;
            int patternIndex; // into either _explicitNames or _regexes
            int predicateIndex;  // into _predicates or -1 if no predicate.
        };
 
        struct _Segment {
            // A _Segment is a half-open interval [begin, end) in _components.
            bool IsEmpty() const { return begin == end; }
            bool StartsAt(size_t idx) const { return begin == idx; }
            bool EndsAt(size_t idx) const { return end == idx; }
            size_t GetSize() const { return end - begin; }
            size_t begin, end;
        };
        
        SdfPath _prefix;
        std::vector<_Component> _components;
        std::vector<_Segment> _segments;
        std::vector<std::string> _explicitNames;
        std::vector<ArchRegex> _regexes;
 
        bool _stretchBegin;
        bool _stretchEnd;
        enum : uint8_t {
            // The kind of objects this pattern is capable of matching.
            _MatchPrimOrProp, _MatchPrimOnly, _MatchPropOnly
        } _matchObjType;
    };
 
 
    // The passed \p invokePattern function must do two things: 1, if \p skip is
    // false, test the current pattern for a match (otherwise skip it) and 2,
    // advance to be ready to test the next pattern for a match on the next call
    // to \p invokePattern.
    SDF_API
    SdfPredicateFunctionResult
    _EvalExpr(TfFunctionRef<
              SdfPredicateFunctionResult (bool /*skip*/)> invokePattern) const;
    
    enum _Op { EvalPattern, Not, Open, Close, Or, And };
    
    std::vector<_Op> _ops;
};
 
template <class DomainType>
class SdfPathExpressionEval : public Sdf_PathExpressionEvalBase
{
    // This object implements matching against a single path pattern.
    class _PatternImpl : public _PatternImplBase {
    public:
        _PatternImpl() = default;
 
        _PatternImpl(SdfPathExpression::PathPattern const &pattern,
                     SdfPredicateLibrary<DomainType> const &predLib) {
            auto linkPredicate =
                [this, &predLib](SdfPredicateExpression const &predExpr) {
                    _predicates.push_back(
                        SdfLinkPredicateExpression(predExpr, predLib));
                    return _predicates.size()-1;
                };
            _Init(pattern, linkPredicate);
        }
 
        // Check objPath for a match against this pattern.
        template <class PathToObject>
        SdfPredicateFunctionResult
        Match(SdfPath const &objPath,
              PathToObject const &pathToObj) const {
            auto runNthPredicate =
                [this, &pathToObj](int i, SdfPath const &path) {
                    return _predicates[i](pathToObj(path));
                };
            return _Match(objPath, runNthPredicate);
        }
 
        // Perform the next incremental search step against this pattern.
        template <class PathToObject>
        SdfPredicateFunctionResult
        Next(SdfPath const &objPath,
             _PatternIncrSearchState &search,
             PathToObject const &pathToObj) const {
            auto runNthPredicate =
                [this, &pathToObj](int i, SdfPath const &path) {
                    return _predicates[i](pathToObj(path));
                };
            return _Next(search, objPath, runNthPredicate);
        }
        
    private:
        std::vector<SdfPredicateProgram<DomainType>> _predicates;
    };
 
public:
    friend SdfPathExpressionEval
    SdfMakePathExpressionEval<DomainType>(
        SdfPathExpression const &expr,
        SdfPredicateLibrary<DomainType> const &lib);
 
    bool IsEmpty() const {
        return _patternImpls.empty();
    }
 
    template <class PathToObject>
    SdfPredicateFunctionResult
    Match(SdfPath const &objPath,
          PathToObject const &pathToObj) const {
        if (IsEmpty()) {
            return SdfPredicateFunctionResult::MakeConstant(false);
        }
        auto patternImplIter = _patternImpls.cbegin();
        auto evalPattern = [&](bool skip) {
            return skip ? (++patternImplIter, SdfPredicateFunctionResult()) :
                (*patternImplIter++).Match(objPath, pathToObj);
        };
        return _EvalExpr(evalPattern);
    }
 
    template <class PathToObject>
    class IncrementalSearcher {
    public:
        IncrementalSearcher() : _eval(nullptr), _lastPathDepth(0) {}
        
        IncrementalSearcher(SdfPathExpressionEval const *eval,
                            PathToObject const &p2o)
            : _eval(eval)
            , _incrSearchStates(_eval->_patternImpls.size())
            , _pathToObj(p2o)
            , _lastPathDepth(0) {}
 
        IncrementalSearcher(SdfPathExpressionEval const *eval,
                            PathToObject &&p2o)
            : _eval(eval)
            , _incrSearchStates(_eval->_patternImpls.size())
            , _pathToObj(std::move(p2o))
            , _lastPathDepth(0) {}
 
        SdfPredicateFunctionResult
        Next(SdfPath const &objPath) {
            auto patternImplIter = _eval->_patternImpls.begin();
            auto stateIter = _incrSearchStates.begin();
            int newDepth = objPath.GetPathElementCount();
            const int popLevel = (newDepth <= _lastPathDepth) ? newDepth : 0;
            auto patternStateNext = [&](bool skip) {
                if (popLevel) {
                    stateIter->Pop(popLevel);
                }
                return skip
                    ? (++patternImplIter, SdfPredicateFunctionResult())
                    : (*patternImplIter++).Next(objPath, *stateIter++,
                                                _pathToObj);
            };
            _lastPathDepth = newDepth;
            return _eval->_EvalExpr(patternStateNext);
        }
 
        void Reset() {
            *this = IncrementalSearcher { _eval, std::move(_pathToObj) };
        }
        
    private:
        SdfPathExpressionEval const *_eval;
        std::vector<_PatternIncrSearchState> _incrSearchStates;
        
        PathToObject _pathToObj;
 
        int _lastPathDepth;
    };
 
    template <class PathToObject>
    IncrementalSearcher<std::decay_t<PathToObject>>
    MakeIncrementalSearcher(PathToObject &&pathToObj) const {
        return IncrementalSearcher<std::decay_t<PathToObject>>(
            this, std::forward<PathToObject>(pathToObj));
    }
 
private:
    std::vector<_PatternImpl> _patternImpls;
};
 
template <class DomainType>
SdfPathExpressionEval<DomainType>
SdfMakePathExpressionEval(SdfPathExpression const &expr,
                          SdfPredicateLibrary<DomainType> const &lib)
{
    using Expr = SdfPathExpression;
    using Eval = SdfPathExpressionEval<DomainType>;
 
    Eval eval;
 
    auto translatePattern = [&](Expr::PathPattern const &pattern) {
        // Add a _PatternImpl object that tests a DomainType object against
        // pattern.
        eval._patternImpls.emplace_back(pattern, lib);
        eval._ops.push_back(Eval::EvalPattern);
    };
 
    if (!Sdf_MakePathExpressionEvalImpl(eval, expr, translatePattern)) {
        eval = {};
    }
 
    return eval;
}
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif // PXR_USD_SDF_PATH_EXPRESSION_EVAL_H