ReferenceChainSearch.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Containers/Array.h"
#include "Containers/ContainersFwd.h"
#include "Containers/Map.h"
#include "Containers/Set.h"
#include "Containers/UnrealString.h"
#include "CoreMinimal.h"
#include "CoreTypes.h"
#include "HAL/PlatformCrt.h"
#include "HAL/ThreadHeartBeat.h"
#include "HAL/UnrealMemory.h"
#include "Misc/AssertionMacros.h"
#include "Misc/EnumClassFlags.h"
#include "Templates/TypeHash.h"
#include "UObject/GarbageCollection.h"
#include "UObject/GarbageCollectionHistory.h"
#include "UObject/NameTypes.h"
#include "UObject/ObjectMacros.h"
#include "UObject/UObjectGlobals.h"
#include "UObject/PrintStaleReferencesOptions.h"
 
class FGCObjectInfo;
class FOutputDevice;
class UObject;
struct FGCSnapshot;
template <typename FuncType> class TFunctionRef;
 
enum class EReferenceChainSearchMode
{
    // Returns all reference chains found
    Default = 0,
    // Returns only reference chains from external objects
    ExternalOnly = 1 << 0,
    // Returns only the shortest reference chain for each rooted object
    Shortest = 1 << 1,
    // Returns only the longest reference chain for each rooted object
    Longest = 1 << 2,
    // Returns only the direct referencers
    Direct = 1 << 3,
    // Returns complete chains. (Ignoring non GC objects)
    FullChain = 1 << 4,
    // Returns the shortest path to a garbage object from which the target object is reachable
    ShortestToGarbage = 1 << 5,
    // Attempts to find a plausible path to the target object with minimal memory usage
    // E.g. returns a direct external reference to the target object if one is found 
    //  otherwise returns an external reference to an inner of the target object
    Minimal = 1 << 6,
    // Skips the disregard-for-GC set that will never be GCd and whose outgoing references are not checked during GC
    GCOnly = 1 << 7,
 
    // Print results
    PrintResults = 1 << 16,
    // Print ALL results (in some cases there may be thousands of reference chains)
    PrintAllResults = 1 << 17,
};
 
ENUM_CLASS_FLAGS(EReferenceChainSearchMode);
 
class FReferenceChainSearch
{
    // Reference chain searching is a very slow operation.
    // Suspend the hang and hitch detectors for the lifetime of this instance.
    FSlowHeartBeatScope SuspendHeartBeat;
    FDisableHitchDetectorScope SuspendGameThreadHitch;
 
public:
 
    enum class EReferenceType
    {
        Unknown = 0,
        Property = 1,
        AddReferencedObjects = 2,
        OuterChain = 3,
    };
 
    template<typename T> 
    struct TReferenceInfo
    {
        // Maximum number of stack frames to keep for AddReferencedObjects function calls
        static constexpr uint32 MaxStackFrames = 30;
 
        T* Object = nullptr;
        TArray<uint64> StackFrames;
        EReferenceType Type;
        FString ReferencerName;
 
        TReferenceInfo()
            : Type(EReferenceType::Unknown)
        {
        }
 
        TReferenceInfo(T* InObject)
            : Object(InObject)
            , Type(EReferenceType::Unknown)
        {
        }
 
        TReferenceInfo(
            T* InObject, 
            EReferenceType InType, 
            FString InReferencerName,
            TConstArrayView<uint64> InStackFrames = {}
        )
            : Object(InObject)
            , StackFrames(InStackFrames)
            , Type(InType)
            , ReferencerName(MoveTemp(InReferencerName))
        {
        }
 
        TReferenceInfo(TReferenceInfo&&) = default;
        TReferenceInfo& operator=(TReferenceInfo&&) = default;
 
        bool operator ==(const TReferenceInfo& Other) const
        {
            return Object == Other.Object;
        }
 
        friend uint32 GetTypeHash(const TReferenceInfo& Info)
        {
            return GetTypeHash(Info.Object);
        }
 
        FString ToString() const
        {
            if (Type == EReferenceType::Property)
            {
                return FString::Printf(TEXT("->%s"), *ReferencerName);
            }
            else if (Type == EReferenceType::AddReferencedObjects)
            {
                if (!ReferencerName.IsEmpty())
                {
                    return FString::Printf(TEXT("::AddReferencedObjects(): %s"), *ReferencerName);
                }
                else
                {
                    return TEXT("::AddReferencedObjects()");
                }
            }
            return FString();
        }
    };
    
    struct FGraphNode;
 
    typedef TReferenceInfo<FGCObjectInfo> FObjectReferenceInfo;
    typedef TReferenceInfo<FGraphNode> FNodeReferenceInfo;
 
    struct FGraphNode
    {
        UE_DEPRECATED(5.0, "Direct Object reference has been deprecated. Use ObjectInfo member variable instead.")
        UObject* Object = nullptr;
        FGCObjectInfo* ObjectInfo = nullptr;
        TSet<FNodeReferenceInfo> ReferencedObjects;
        TSet<FGraphNode*> ReferencedByObjects;
        int32 Visited = 0;
 
        int64 GetAllocatedSize() const
        {
            return ReferencedObjects.GetAllocatedSize() + ReferencedByObjects.GetAllocatedSize();
        }
    };
 
 
    class FReferenceChain
    {
        friend class FReferenceChainSearch;
 
        FGraphNode* TargetNode = nullptr;
 
        TArray<FGraphNode*> Nodes;
        TArray<const FNodeReferenceInfo*> ReferenceInfos;
 
        void FillReferenceInfo();
 
    public:
        FReferenceChain() {}
        FReferenceChain(int32 ReserveDepth)
        {
            Nodes.Reserve(ReserveDepth);
        }
 
        FReferenceChain(FGraphNode* InTargetNode, TArray<FGraphNode*> InNodes, TArray<const FNodeReferenceInfo*> InReferenceInfos)
            : TargetNode(InTargetNode)
            , Nodes(MoveTemp(InNodes))
            , ReferenceInfos(MoveTemp(InReferenceInfos))
        {
        }
 
        int64 GetAllocatedSize() const
        {
            return Nodes.GetAllocatedSize() + ReferenceInfos.GetAllocatedSize();
        }
 
        void AddNode(FGraphNode* InNode)
        {
            Nodes.Add(InNode);
        }
        void InsertNode(FGraphNode* InNode)
        {
            Nodes.Insert(InNode, 0);
        }
        FGraphNode* GetNode(int32 NodeIndex) const
        {
            return Nodes[NodeIndex];
        }
        FGraphNode* GetRootNode(FGraphNode* Exclude) const
        {
            if (Nodes.Last() == Exclude && Nodes.Num() > 2)
            {
                return Nodes[Nodes.Num()-2];
            }
 
            return Nodes.Last();
        }
        FGraphNode* GetRootNode() const
        {
            return Nodes.Last();
        }
        int32 Num() const
        {
            return Nodes.Num();
        }
        FReferenceChain* Split()
        {
            FReferenceChain* NewChain = new FReferenceChain(*this);
            return NewChain;
        }
        bool Contains(const FGraphNode* InNode) const
        {
            return Nodes.Contains(InNode);
        }
        const FNodeReferenceInfo* GetReferenceInfo(int32 NodeIndex) const
        {
            return ReferenceInfos[NodeIndex];
        }
        bool IsExternal() const;
    };
 
    struct FCallbackParams
    {
        FGCObjectInfo* Object = nullptr;
        FGCObjectInfo* Referencer = nullptr;
        const FNodeReferenceInfo* ReferenceInfo = nullptr;
        int32 Indent = 0;
        FOutputDevice* Out = nullptr;
    };
 
    COREUOBJECT_API explicit FReferenceChainSearch(UObject* InObjectToFindReferencesTo,
        EReferenceChainSearchMode Mode = EReferenceChainSearchMode::PrintResults,
        ELogVerbosity::Type InVerbosityForPrint = ELogVerbosity::Log);
    COREUOBJECT_API explicit FReferenceChainSearch(TConstArrayView<UObject*> InObjectsToFindReferencesTo,
        EReferenceChainSearchMode Mode = EReferenceChainSearchMode::PrintResults,
        ELogVerbosity::Type InVerbosityForPrint = ELogVerbosity::Log);
 
    COREUOBJECT_API explicit FReferenceChainSearch(EReferenceChainSearchMode Mode);
 
    COREUOBJECT_API ~FReferenceChainSearch();
 
#if ENABLE_GC_HISTORY
    COREUOBJECT_API void PerformSearchFromGCSnapshot(UObject* InObjectToFindReferencesTo, FGCSnapshot& InSnapshot);
    COREUOBJECT_API void PerformSearchFromGCSnapshot(TConstArrayView<UObject*> InObjectsToFindReferencesTo, FGCSnapshot& InSnapshot);
#endif //ENABLE_GC_HISTORY
 
    COREUOBJECT_API int32 PrintResults(bool bDumpAllChains = false, UObject* TargetObject = nullptr, ELogVerbosity::Type VerbosityForPrint = ELogVerbosity::Log) const;
    COREUOBJECT_API void SetVerbosityForPrint(ELogVerbosity::Type Verbosity);
 
    COREUOBJECT_API int32 PrintResults(TFunctionRef<bool(FCallbackParams& Params)> ReferenceCallback, bool bDumpAllChains = false, UObject* TargetObject = nullptr, ELogVerbosity::Type VerbosityForPrint = ELogVerbosity::Log) const;
 
    COREUOBJECT_API FString GetRootPath(UObject* TargetObject = nullptr) const;
 
    COREUOBJECT_API FString GetRootPath(TFunctionRef<bool(FCallbackParams& Params)> ReferenceCallback, UObject* TargetObject = nullptr) const;
 
    const TArray<FReferenceChain*>& GetReferenceChains() const
    {
        return ReferenceChains;
    }
 
    int64 GetAllocatedSize() const;
 
    COREUOBJECT_API static FString FindAndPrintStaleReferencesToObject(UObject* ObjectToFindReferencesTo, EPrintStaleReferencesOptions Options);
    COREUOBJECT_API static TArray<FString> FindAndPrintStaleReferencesToObjects(TConstArrayView<UObject*> ObjectsToFindReferencesTo, EPrintStaleReferencesOptions Options);
private:
 
    TArray<FGCObjectInfo*> ObjectInfosToFindReferencesTo;
 
    EReferenceChainSearchMode SearchMode = EReferenceChainSearchMode::Default;
 
    TArray<FReferenceChain*> ReferenceChains;
 
    TMap<FGCObjectInfo*, FGraphNode*> AllNodes;
    TMap<const UObject*, FGCObjectInfo*> ObjectToInfoMap;
 
    ELogVerbosity::Type VerbosityForPrint = ELogVerbosity::Log;
 
    void Cleanup();
 
    void LinkNodes(
        UObject* From,
        UObject* To,
        EReferenceType ReferenceType,
        FName PropertyName,
        TConstArrayView<uint64> StackFrames = {});
    void LinkNodes(
        FGCObjectInfo* From,
        FGCObjectInfo* To,
        EReferenceType ReferenceType,
        FName PropertyName,
        TConstArrayView<uint64> StackFrames = {});
 
public:
    static FString GetObjectFlags(const FGCObjectInfo& InObject);
private:
 
    static void DumpChain(FReferenceChainSearch::FReferenceChain* Chain, TFunctionRef<bool(FCallbackParams& Params)> ReferenceCallback,
        TMap<uint64, FString>& CallstackCache, FOutputDevice& Out, ELogVerbosity::Type InVerbosityForPrint);
};