// Copyright Epic Games, Inc. All Rights Reserved.

#include "callstack_formatter.h"

#include <zencore/fmtutils.h>
#include <zencore/string.h>
#include <zenutil/wildcard.h>

#include <algorithm>

namespace zen::trace_detail {

namespace {

	static bool IsKnownRuntimeModuleName(std::string_view ModuleName)
	{
		std::string LowerName = zen::ToLower(ModuleName);
		return LowerName == "ntdll.dll" || LowerName == "kernel32.dll" || LowerName == "kernelbase.dll" || LowerName == "ucrtbase.dll" ||
			   LowerName == "ucrtbased.dll" || LowerName.starts_with("vcruntime") || LowerName.starts_with("msvcp") ||
			   LowerName.starts_with("api-ms-win-") || LowerName == "libc.so" || LowerName.starts_with("libc.so.") ||
			   LowerName == "libstdc++.so" || LowerName.starts_with("libstdc++.so.") || LowerName == "libgcc_s.so" ||
			   LowerName.starts_with("libgcc_s.so.") || LowerName == "libpthread.so" || LowerName.starts_with("libpthread.so.") ||
			   LowerName == "libm.so" || LowerName.starts_with("libm.so.") || LowerName == "ld-linux.so" ||
			   LowerName.starts_with("ld-linux") || LowerName == "libsystem_kernel.dylib" || LowerName == "libsystem_malloc.dylib" ||
			   LowerName == "libsystem_pthread.dylib" || LowerName == "libdyld.dylib";
	}

	static bool PathLooksThirdParty(std::string_view ModulePath)
	{
		std::string LowerPath = zen::ToLower(ModulePath);
		return LowerPath.find("/thirdparty/") != std::string::npos || LowerPath.find("\\thirdparty\\") != std::string::npos ||
			   LowerPath.find("/third-party/") != std::string::npos || LowerPath.find("\\third-party\\") != std::string::npos ||
			   LowerPath.find("/external/") != std::string::npos || LowerPath.find("\\external\\") != std::string::npos ||
			   LowerPath.find("/extern/") != std::string::npos || LowerPath.find("\\extern\\") != std::string::npos ||
			   LowerPath.find("/engine/binaries/thirdparty/") != std::string::npos ||
			   LowerPath.find("\\engine\\binaries\\thirdparty\\") != std::string::npos ||
			   LowerPath.find("c:\\windows\\system32\\") != std::string::npos ||
			   LowerPath.find("c:\\windows\\syswow64\\") != std::string::npos || LowerPath.starts_with("/usr/lib/") ||
			   LowerPath.starts_with("/lib/") || LowerPath.starts_with("/system/");
	}

	static bool MatchesAnyPattern(std::string_view Text, const std::vector<std::string>& Patterns)
	{
		for (const std::string& Pattern : Patterns)
		{
			if (zen::MatchWildcard(Pattern, Text, /*CaseSensitive=*/false))
			{
				return true;
			}
		}
		return false;
	}

	static bool ShouldSkipFrameByPattern(const CallstackFilterOptions& Options,
										 const TraceModel&			   Model,
										 const ResolvedFrame&		   Frame,
										 std::string_view			   Description)
	{
		if (MatchesAnyPattern(Description, Options.SkipPatterns))
		{
			return true;
		}
		if (Frame.ModuleIndex != ~0u && Frame.ModuleIndex < Model.Modules.size())
		{
			const ModuleInfo& Module = Model.Modules[Frame.ModuleIndex];
			if (MatchesAnyPattern(Module.Name, Options.SkipPatterns) || MatchesAnyPattern(Module.FullPath, Options.SkipPatterns))
			{
				return true;
			}
		}

		static const std::vector<std::string> kDefaultSkipPatterns = {
			"zen::MemoryTrace_*",
			"*mi_*",
			"*_mi_*",
			"*rpmalloc*",
			"*mimalloc*",
			"*je_malloc*",
			"*je_free*",
			"*malloc*",
			"*free*",
			"*realloc*",
		};
		return MatchesAnyPattern(Description, kDefaultSkipPatterns);
	}

	static bool IsThirdPartyFrame(const TraceModel& Model, const ResolvedFrame& Frame, std::string_view Description)
	{
		if (Description.starts_with("std::"))
		{
			return true;
		}
		if (Frame.ModuleIndex == ~0u || Frame.ModuleIndex >= Model.Modules.size())
		{
			return false;
		}

		const ModuleInfo& Module = Model.Modules[Frame.ModuleIndex];
		return IsKnownRuntimeModuleName(Module.Name) || PathLooksThirdParty(Module.FullPath);
	}

}  // namespace

CallstackFormatter::CallstackFormatter(const TraceModel& InModel, const SymbolResolver* InSymbols) : m_Model(InModel), m_Symbols(InSymbols)
{
}

const CallstackEntry*
CallstackFormatter::FindCallstackEntry(uint32_t CallstackId) const
{
	auto It =
		eastl::lower_bound(m_Model.Callstacks.begin(), m_Model.Callstacks.end(), CallstackId, [](const CallstackEntry& E, uint32_t Id) {
			return E.Id < Id;
		});
	if (It == m_Model.Callstacks.end() || It->Id != CallstackId)
	{
		return nullptr;
	}
	return &*It;
}

const std::string&
CallstackFormatter::Describe(const ResolvedFrame& Frame)
{
	auto It = m_Cache.find(Frame.Address);
	if (It != m_Cache.end())
	{
		return It->second;
	}

	std::string Result = m_Symbols ? m_Symbols->Resolve(Frame.Address) : std::string{};
	if (Result.empty())
	{
		if (Frame.ModuleIndex != ~0u && Frame.ModuleIndex < m_Model.Modules.size())
		{
			Result = fmt::format("{} + 0x{:X}", m_Model.Modules[Frame.ModuleIndex].Name, Frame.Offset);
		}
		else
		{
			Result = fmt::format("0x{:X}", Frame.Address);
		}
	}

	auto [InsertedIt, Inserted] = m_Cache.emplace(Frame.Address, std::move(Result));
	ZEN_UNUSED(Inserted);
	return InsertedIt->second;
}

FilteredCallstackView
CallstackFormatter::BuildView(const CallstackEntry& Entry, const CallstackFilterOptions& Options)
{
	FilteredCallstackView Result;
	Result.Frames.reserve(Entry.Frames.size());
	if (Entry.Frames.empty())
	{
		return Result;
	}

	eastl::vector<bool> ExplicitSkip;
	eastl::vector<bool> ThirdParty;
	ExplicitSkip.reserve(Entry.Frames.size());
	ThirdParty.reserve(Entry.Frames.size());

	for (const ResolvedFrame& Frame : Entry.Frames)
	{
		const std::string& Description = Describe(Frame);
		ExplicitSkip.push_back(ShouldSkipFrameByPattern(Options, m_Model, Frame, Description));
		ThirdParty.push_back(IsThirdPartyFrame(m_Model, Frame, Description));
	}

	eastl::vector<size_t> VisibleFrameIndices;
	VisibleFrameIndices.reserve(Entry.Frames.size());

	if (!Options.EnableHeuristic)
	{
		for (size_t Index = 0; Index < Entry.Frames.size(); ++Index)
		{
			if (!ExplicitSkip[Index])
			{
				VisibleFrameIndices.push_back(Index);
			}
		}
		if (VisibleFrameIndices.empty())
		{
			VisibleFrameIndices.push_back(0);
		}
	}
	else
	{
		size_t FirstProgramIndex	   = Entry.Frames.size();
		size_t BoundaryThirdPartyIndex = Entry.Frames.size();
		for (size_t Index = 0; Index < Entry.Frames.size(); ++Index)
		{
			if (ExplicitSkip[Index])
			{
				continue;
			}
			if (ThirdParty[Index])
			{
				BoundaryThirdPartyIndex = Index;
				continue;
			}
			FirstProgramIndex = Index;
			break;
		}

		if (FirstProgramIndex == Entry.Frames.size())
		{
			for (size_t Index = 0; Index < Entry.Frames.size(); ++Index)
			{
				if (!ExplicitSkip[Index])
				{
					VisibleFrameIndices.push_back(Index);
				}
			}
			if (VisibleFrameIndices.empty())
			{
				VisibleFrameIndices.push_back(0);
			}
		}
		else
		{
			if (BoundaryThirdPartyIndex < Entry.Frames.size())
			{
				VisibleFrameIndices.push_back(BoundaryThirdPartyIndex);
				Result.IncludedThirdPartyBoundary = true;
			}
			for (size_t Index = FirstProgramIndex; Index < Entry.Frames.size(); ++Index)
			{
				if (!ExplicitSkip[Index])
				{
					VisibleFrameIndices.push_back(Index);
				}
			}
			if (VisibleFrameIndices.empty())
			{
				VisibleFrameIndices.push_back(FirstProgramIndex);
			}
		}
	}

	Result.HiddenPrefixCount = uint32_t(VisibleFrameIndices.front());
	for (size_t FrameIndex : VisibleFrameIndices)
	{
		Result.Frames.push_back(
			{.OriginalIndex = FrameIndex, .Frame = &Entry.Frames[FrameIndex], .Display = Describe(Entry.Frames[FrameIndex])});
	}
	return Result;
}

}  // namespace zen::trace_detail