PDGE_Dependency.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.
 *
 * COMMENTS:
 */

#ifndef __PDGE_DEPENDENCY_H__
#define __PDGE_DEPENDENCY_H__

#include "PDGE_API.h"
#include "PDGE_DebugUtils.h"

#include <UT/UT_Array.h>
#include <UT/UT_ArraySet.h>
#include <UT/UT_NonCopyable.h>
#include <UT/UT_StringHolder.h>
#include <UT/UT_TBBSpinLock.h>

#include <SYS/SYS_AtomicInt.h>
#include <SYS/SYS_Types.h>

#include <utility>

class PDGE_DependencyOwner;
class PDGE_Evaluator;
class PDGE_Resolutions;

/**
 * Base class for dependencies types. Stores a Set of dependencies and a vector
 * of dependents. Dependencies are added using the addDependency method, which
 * ensures that no duplicate entries are added and adds back references on the
 * dependent this object.
 *
 * A dependency relationship can optionally be marked as "partial" -- by
 * default the partial flag is false. A partial dependency means that the 
 * dependent/child is interested in partial resolution updates from the 
 * dependency/parent it is attached to. When one of the parent's dependencies
 * is resolved, it passes on that information to all dependents/children that
 * are interested in partial updates.
 *
 * Once a dependency's resolution count reaches 0, it is marked as resolved
 * and all dependents are inspected to see if they too have reached 0. A
 * resolved dependency cannot be put back to the unresolved state unless it
 * is reset. Resetting is not thread safe nor is it safe to do while a
 * graph is being evalauated. It should only be done after an evaluation has
 * completed.
 *
 * If PDGE_DEBUG_ENABLE_NAMES is defined, this class also stores a string
 * name for the dependency for debug output. 
 */
class PDGE_API PDGE_Dependency : UT_NonCopyable
{
public:
    using Set           = UT_ArraySet<PDGE_Dependency*>;
    using Array         = UT_Array<PDGE_Dependency*>;
    using Map           = UT_ArrayMap<PDGE_Dependency*, PDGE_Dependency*>;

    using OwnerArray    = UT_Array<PDGE_DependencyOwner*>;
    using PartialPair   = std::pair<PDGE_Dependency*, OwnerArray>;
    using Partial       = UT_Array<PartialPair>;
    
    /// Dependency resolve state, passed back from the PDGE_DependencyOwner
    /// when doing a full or partial resolve. The state has no impact on the
    /// resolution of the dependency itself, but it propagate to dependents.
    enum State : uint8
    {
        /// The dependency was successfully resolved
        eSucceeded  = 0x00,

        /// The dependency was resolved while evaluation was canceling
        eCanceled   = 0x01,

        /// The dependency encountered a failure during resolution
        eFailed     = 0x02,

        /// The dependency was reset during resolution and should not be
        /// marked as resolved. This can only be used with leaf nodes in the
        /// dependency graph.
        eReset      = 0x04,

        /// The state bits should be cleared before ORing the results from
        /// dependency resolutions
        eClear      = 0x08,
    };

public:
    /// Constructs a new dependency from a name and dependency owner. The
    /// name is only stored if PDGE_DEBUG_ENABLE_NAMES is enabled.
                            PDGE_Dependency(const char* name,
                                            PDGE_DependencyOwner* owner);

    /// Destroys this dependency object
    virtual                 ~PDGE_Dependency();

    /// Returns the memory usage of this object
    int64                   getMemoryUsage(bool inclusive) const;

    /// Adds a dependency if it does not already exist. This method locks both
    /// this object and the dependency. Returns true if the dependency was
    /// added, else false.
    bool                    addDependency(PDGE_Dependency* dependency,
                                          bool partial = false,
                                          PDGE_Dependency* propagate = nullptr,
                                          bool is_any = false);

    /// Returns true if this object has any dependencies
    inline bool             hasDependencies() const
                                { return !myDependencies.empty(); }

    /// Returns true if this object has any dependents
    inline bool             hasDependents() const
                                { return !myDependents.isEmpty(); }

    /// Returns true if this object has the specifed dependency
    inline bool             hasDependency(PDGE_Dependency* dependency) const
                                {
                                    if (!dependency)
                                        return false;
                                    return myDependencies.contains(dependency);
                                }


    /// Returns true if this dependency is a partial source, i.e. it emits
    /// partial resolve calls when one of its dependencies is resolved
    inline bool             isPartialSrc() const
                                { return myPartialSrc; }

    /// Returns true if this dependency is interested in receiving partial
    /// resolve calls, when one of its dependencies is partially resolved.
    inline bool             isPartialDst() const
                                { return myPartialDst; }

    /// Returns true if this dependency has been resolved. Resolves dependencies
    /// can only go back to being unresolved when calling reset().
    inline bool             isResolved() const
                                { return myIsResolved; }

    /// Returns true if this dependency has a heavy-weight evaluation routine
    inline bool             isHeavy() const
                                { return myIsHeavy; }


    /// Returns the current state value of the dependency
    inline uint8            state() const
                                { return myState; }

    /// Returns true if the current state value is set
    inline bool             hasState(State state) const
                                { return (myState & state); }

    /// ORs the state value into the current state
    inline void             updateState(State state)
                                { myState |= state; }


    /// Returns the object that owns this dependency.
    inline PDGE_DependencyOwner*
                            owner() const
                                { return myOwner; }

    /// Returns the set of all dependencies
    inline const Set&       dependencies() const
                                { return myDependencies; }

    /// Returns the array of all dependents
    inline const Array&     dependents() const
                                { return myDependents; }

    /// Returns the edge lock for this dependency object
    inline UT_TBBSpinLock&  edgeLock() const
                                { return myEdgeLock; }


    /// Resets this dependecy object back to its default state. The initial
    /// count determines the starting value of the unresolved counter.
    void                    reset(int initial_count=0,
                                  bool is_heavy=false);

    /// Unresolves a dependency and all of its dependents. This is different
    /// than a reset because its non-destructive, and propgates state to
    /// dependents. It is also threadsafe with other internal operations and
    /// will interrupt and clear any resolutions that are already in progress.
    /// It will not, however, be able to interrupt calls into the dependency
    /// owner that may be changing state on that object.
    void                    unresolve();

    /// Decrements the ref count on this dependency by one. Should be used 
    /// when this dependency is reset with a non-0 initial count, for adding
    /// an N+1 dependency.
    inline bool             tryResolve(int count=1)
                                { return tryResolve(count, 0); }

    /// Increments the ref count on this dependency by one, for manual contorl
    /// over the ref count
    void                    increment(int count=1);

    /// Returns the debug full name, which includes the name of this object
    /// and its owner. The as_dot argument indicates whether or not the name is
    /// going to be used for dot graph output.
    UT_StringHolder         debugName(bool as_dot=false) const;

private:
    friend class PDGE_Resolutions;

    void                    unresolve(int unresolve_count, Set& visited);
    void                    resolve(PDGE_Evaluator& evaluator,
                                    PDGE_Resolutions& resolutions);
    void                    partial(PDGE_Evaluator& evaluator,
                                    PDGE_Resolutions& resolutions,
                                    const OwnerArray& owner_array);
    bool                    partialPairs(Partial& partial_pairs,
                                         const OwnerArray& owner_array,
                                         bool ascending) const;

private:
    inline bool             tryResolve(int count, uint8 state)
                                {
                                    if (state != 0)
                                    {
                                        UT_TBBSpinLock::Scope lock(myEdgeLock);
                                        myState |= state;
                                    }

                                    return (myUnresolvedCount.add(-count) == 0);
                                }

    inline void             incrementInternal(int count)
                                { myUnresolvedCount.add(count); }

private:
    class EvaluationScope
    {
    public:
                            EvaluationScope(
                                PDGE_Dependency* dependency,
                                bool is_partial);
                            ~EvaluationScope();

        bool                tryUnresolve(
                                PDGE_Resolutions& resolutions) const;

    private:
        PDGE_Dependency*    myDependency;
        uint8               myUnresolveDepth;
        bool                myIsPartial;
    };

private:
    Set                     myDependencies;
    Array                   myDependents;

    PDGE_DependencyOwner*   myOwner;
    SYS_AtomicInt32         myUnresolvedCount;

    uint8                   myState;
    uint8                   myUnresolveDepth;
    uint8                   myEvaluationDepth;

    mutable UT_TBBSpinLock  myEdgeLock;

    bool                    myPartialSrc        : 1;
    bool                    myPartialDst        : 1;
    bool                    myIsResolved        : 1;
    bool                    myIsHeavy           : 1;
    bool                    myIsAny             : 1;

#ifdef PDGE_DEBUG_ENABLE_NAMES
    UT_StringHolder         myDebugName;
#endif

#ifdef PDGE_DEBUG_ENABLE_IDS
    int                     myId;
#endif
};

#endif