UT_PathPattern.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 */

#ifndef __UT_PathPattern_h__
#define __UT_PathPattern_h__

#include "UT_API.h"
#include "UT_Array.h"
#include "UT_IntArray.h"
#include "UT_IntrusivePtr.h"
#include "UT_StringHolder.h"
#include "UT_StringArray.h"
#include "UT_UniquePtr.h"

class UT_SpecialTokenData : public UT_IntrusiveRefCounter<UT_SpecialTokenData>
{
public:
                         UT_SpecialTokenData()
                         { }
    virtual             ~UT_SpecialTokenData()
                         { }
};
typedef UT_IntrusivePtr<UT_SpecialTokenData> UT_SpecialTokenDataPtr;

// Optional opaque payload carried alongside the boolean result of a pattern
// match. The base class never creates these, so base-class matching stays
// purely boolean. Subclasses (e.g. the USD path pattern) use them to carry and
// combine per-match data, such as the set of matched point instancer
// instances, according to the pattern's set operators. See the matches()
// overload that takes a match_data argument.
class UT_PathPatternMatchData
    : public UT_IntrusiveRefCounter<UT_PathPatternMatchData>
{
public:
                         UT_PathPatternMatchData()
                         { }
    virtual             ~UT_PathPatternMatchData()
                         { }
};
typedef UT_IntrusivePtr<UT_PathPatternMatchData> UT_PathPatternMatchDataPtr;

// Matches a pattern against a USD path. The pattern uses roughly rsync style
// matching, where "*" only matches within a path component, and "**" matches
// across path components. Also supports standard Houdini "^" operator to
// exclude paths. In addition, "-" will also exclude paths, "&" will perform
// intersections between two sets of paths, and "~" can be used to quickly
// prune branches during a full traversal of the path hierarchy.
class UT_API UT_PathPattern
{
public:
                         UT_PathPattern(const UT_StringRef &pattern,
                                 bool case_sensitive = true,
                                 bool assume_wildcards = false,
                                 bool allow_instance_indices = false);
    virtual             ~UT_PathPattern();

    bool                 matches(const UT_StringRef &path,
                                bool *excludes_branch = nullptr) const;
    // As above, but also returns an optional opaque payload describing the
    // match. Subclasses use this to carry a per-match instance selection that
    // is combined according to the pattern's set operators (union, intersect,
    // difference). For the base class, match_data is always cleared to null
    // and this behaves exactly like the plain matches() above.
    bool                 matches(const UT_StringRef &path,
                                bool *excludes_branch,
                                UT_PathPatternMatchDataPtr &match_data) const;
    bool                 getExplicitList(UT_StringArray &tokens) const;
    bool                 getExplicitListWithInstanceIds(
                                 UT_StringArray &paths,
                                 UT_StringArray &instance_patterns) const;

    bool                 getCaseSensitive() const
                         { return myCaseSensitive; }
    bool                 getAssumeWildcardsAroundPlainTokens() const
                         { return myAssumeWildcardsAroundPlainTokens; }
    bool                 getAllowInstanceIndices() const
                         { return myAllowInstanceIndices; }
    const UT_StringHolder &getPatternError() const
                         { return myPatternError; }

protected:
    class Token
    {
    public:
                         Token(const UT_StringHolder &str,
                                 bool do_path_matching,
                                 bool has_wildcards)
                            : myString(str),
                              myDoPathMatching(do_path_matching),
                              myHasWildcards(has_wildcards),
                              myIsSpecialToken(false)
                         { }

        UT_StringHolder          myString;
        UT_StringHolder          myInstanceIdPattern;
        UT_SpecialTokenDataPtr   mySpecialTokenDataPtr;
        bool                     myDoPathMatching;
        bool                     myHasWildcards;
        bool                     myIsSpecialToken;
    };

    // Default constructor, only to be used by createEmptyClone, which is used
    // by create* functions to build a new patterns from pieces of the current
    // pattern.
                         UT_PathPattern(bool case_sensitive,
                                 bool assume_wildcards,
                                 bool allow_instance_indices);

    UT_PathPattern      *createPruningPattern(int tokenidx);
    UT_PathPattern      *createPrecedingGroupPattern(int tokenidx);
    virtual UT_PathPattern *createEmptyClone() const
                         {
                             return new UT_PathPattern(myCaseSensitive,
                                 myAssumeWildcardsAroundPlainTokens,
                                 myAllowInstanceIndices);
                         }
    virtual bool         matchSpecialToken(
                                const UT_StringRef &path,
                                const Token &token,
                                bool *excludes_branch) const;

    // Set operations used when combining match payloads from the left and
    // right sides of a pattern operator.
    enum MatchOp
    {
        MATCH_ADD,              // union (space, "+")
        MATCH_SUBTRACT,         // difference ("-", "^")
        MATCH_INTERSECT,        // intersection ("&")
        MATCH_PRUNE             // pruning ("~"); payload passes through unchanged
    };

    // Hooks allowing a subclass to carry an opaque payload through the match
    // evaluation. The base implementations produce no payload, so base-class
    // matching is purely boolean and entirely unchanged. The USD subclasses
    // use these to carry and combine the set of matched point instancer
    // instances for a given path. These are only invoked during a match when
    // the caller requested a payload (the matches() overload above).
    virtual bool         matchSpecialTokenWithData(
                                const UT_StringRef &path,
                                const Token &token,
                                bool *excludes_branch,
                                UT_PathPatternMatchDataPtr &match_data) const
                         {
                             return matchSpecialToken(path, token,
                                 excludes_branch);
                         }
    virtual UT_PathPatternMatchDataPtr makeLeafMatchData(
                                const UT_StringRef &path,
                                const Token &token) const
                         { return UT_PathPatternMatchDataPtr(); }
    virtual UT_PathPatternMatchDataPtr combineMatchData(
                                MatchOp op,
                                const UT_PathPatternMatchDataPtr &lhs,
                                const UT_PathPatternMatchDataPtr &rhs) const
                         { return UT_PathPatternMatchDataPtr(); }
    virtual bool         matchDataIsEmpty(
                                const UT_PathPatternMatchDataPtr &match_data)
                                const
                         { return !match_data; }

    void                 testForExplicitList();
    void                 patternInterrupted();

    UT_Array<Token>      myTokens;

private:
    // This class is used to represent the parsed expression tree generated
    // from a string search pattern.
    class PatternOp
    {
    public:
        enum Operator
        {
            GROUP,
            NOOP,
            VALUES,
            ADD,
            SUBTRACT,
            PRUNE,
            INTERSECT
        };

                         PatternOp(const UT_PathPattern &owner)
                             : myOwner(owner),
                               myOp(GROUP),
                               myParent(nullptr)
                         { }
                         PatternOp(PatternOp &parent, Operator op)
                             : myOwner(parent.myOwner),
                               myOp(op),
                               myParent(&parent)
                         { }

        PatternOp       *push(Operator op);
        PatternOp       *insertGroup();
        bool             containsOnlyAddOperations() const;

        PatternOp       *leftOp() { return myLeftOp.get(); }
        const PatternOp *leftOp() const { return myLeftOp.get(); }
        PatternOp       *rightOp() { return myRightOp.get(); }
        const PatternOp *rightOp() const { return myRightOp.get(); }

        const UT_PathPattern    &myOwner;
        Operator                 myOp;
        PatternOp               *myParent;
        UT_UniquePtr<PatternOp>  myLeftOp;
        UT_UniquePtr<PatternOp>  myRightOp;
        UT_IntArray              myValues;
    };

    class PatternOpStep
    {
    public:
        PatternOpStep(PatternOp *op = nullptr)
            : myPatternOp(op), myFollowLeftChild(false) { }

        PatternOp               *myPatternOp;
        bool                     myFollowLeftChild;
    };

    typedef UT_Array<PatternOpStep> PatternOpPath;

    void                         init(const UT_StringArray &pattern_tokens);
    bool                         matches(const UT_StringRef &path,
                                        const PatternOp *op,
                                        bool *excludes_branch,
                                        UT_PathPatternMatchDataPtr *match_data
                                            = nullptr) const;
    // Combine left/right payloads for a binary operator and derive the new
    // boolean result. When a payload is produced (instance-relevant paths),
    // membership follows whether the combined set is non-empty; otherwise the
    // supplied boolean result is kept unchanged.
    bool                         combineAndUpdateMatchData(MatchOp op,
                                        const UT_PathPatternMatchDataPtr &lhs,
                                        const UT_PathPatternMatchDataPtr &rhs,
                                        bool boolean_matched,
                                        UT_PathPatternMatchDataPtr &out) const;
    void                         printPattern(const PatternOp *patternop,
                                        int indent);
    static bool                  findToken(int tokenidx,
                                        PatternOpPath &oppath);
    static UT_UniquePtr<PatternOp> duplicatePatternOp(
                                        const UT_PathPattern &pattern,
                                        const PatternOp *patternop,
                                        PatternOp *parent);
    static bool                  patternOpPathContains(
                                        const PatternOpPath &oppath,
                                        const PatternOp *patternop);
    static bool                  patternOpPathIntersects(
                                        const PatternOpPath &oppath,
                                        const PatternOp *patternop);
    static void                  makePruningPatternOp(
                                        PatternOp *patternop,
                                        const PatternOpPath &oppath);
    static void                  makePrecedingGroupPatternOp(
                                        PatternOp *patternop,
                                        const PatternOpPath &oppath,
                                        bool &found_token);
    static bool                  parsePattern(const char *&pattern,
                                        UT_StringArray &tokens,
                                        PatternOp *groupop,
                                        UT_String &error);

    UT_UniquePtr<PatternOp>      myPatternOp;
    UT_StringHolder              myPatternError;
    bool                         myIsExplicitList;
    // These values can't change after the constructor, because the
    // constructor can cause evaluation of the pattern or parts of it.
    const bool                   myCaseSensitive;
    const bool                   myAssumeWildcardsAroundPlainTokens;
    const bool                   myAllowInstanceIndices;
};

#endif