using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Text.RegularExpressions;

static class TracepointAnalysis
{
    /// <summary>
    /// Reads in a file that contains the text from the debugger's output window and analyises the tracepoint callstacks
    /// </summary>
    /// <param name="path">Path to a file containing the saved output window text</param>
    /// <param name="filter">Optional delegate to filter out callstacks that are uninteresting</param>
    /// <param name="stacks">Returns a list of all the callstacks in the output with their hit count</param>
    /// <param name="callTreeRoots">Returns the roots of the tracepoint call trees</param>
    static public void ReadFile(string path, CallstackFilter filter, out List<Callstack> stacks, out List<CallTreeNode> callTreeRoots)
    {
        Dictionary<string, CallTreeNode> callTreeRootMap = new Dictionary<string, CallTreeNode>();
        Dictionary<CallstackKey, Callstack> callstackMap = new Dictionary<CallstackKey, Callstack>();
        stacks = new List<Callstack>();
        
        StreamReader inputFile = File.OpenText(path);

        List<string> currentCallstack = null;
        Regex callstackStartLineFormat = new Regex(@"CSTACK: \t.+\!.+\(.*\).*");

        while (!inputFile.EndOfStream)
        {
            string line = inputFile.ReadLine();

            if (currentCallstack == null)
            {
                Match match = callstackStartLineFormat.Match(line);

                if (match.Success && match.Index == 0)
                {
                    currentCallstack = new List<string>();
                    string s = line.Substring(line.IndexOf('\t') + 1);
                    currentCallstack.Add(s);
                }
            }
            else
            {
                if (string.IsNullOrEmpty(line) || (line.Length == 1 && line[0] == '\t'))
                {
                    string[] frames = currentCallstack.ToArray();
                    CallstackKey key = new CallstackKey(frames);
                    
                    if (filter == null || filter(key))
                    {
                        Callstack.AddCallstack(stacks, callstackMap, key);
                        CallTreeNode.AddCallstack(callTreeRootMap, key);
                    }

                    currentCallstack = null;
                }
                else if (line.Length > 1 && line[0] == '\t')
                {
                    string s = line.Substring(1);

                    currentCallstack.Add(s);
                }
            }
        }

        callTreeRoots = new List<CallTreeNode>(callTreeRootMap.Values);
            
    }
}

/// <summary>
/// Allows filtering the tracepoint callstacks that are interesting.
/// </summary>
/// <param name="stack">Callstack that was read from the input file</param>
/// <returns>true if the callstack should be included in the stack database / call tree roots</returns>
delegate bool CallstackFilter(CallstackKey stack);

class CallstackKey : IEquatable<CallstackKey>, IComparable<CallstackKey>
{
    public readonly string[] Frames;
    int m_hashCode;

    internal CallstackKey(string[] frames)
    {
        this.Frames = frames;

        // Using the default string array implementation of GetHashCode doesn't produce the desired effect
        foreach (string line in this.Frames)
        {
            m_hashCode ^= line.GetHashCode();
        }
    }

    public override int GetHashCode()
    {
        return m_hashCode;
    }

    public int CompareTo(CallstackKey other)
    {
        int result = this.Frames.Length - other.Frames.Length;
        if (result != 0)
            return result;

        for (int i = 0; i < this.Frames.Length; i++)
        {
            result = string.CompareOrdinal(this.Frames[i], other.Frames[i]);
            if (result != 0)
                return result;
        }

        return 0;
    }

    // The default dictionary comparison will call this
    public bool Equals(CallstackKey other)
    {
        return (CompareTo(other) == 0);
    }

    public int IndexOf(string function)
    {
        int index = 0;

        foreach (string f in this.Frames)
        {
            if (f.Contains(function))
                return index;

            index++;
        }

        return -1;
    }

    public bool Contains(string function)
    {
        return (IndexOf(function) >= 0);
    }
};

class Callstack : CallstackKey
{
    private int m_hitCount;
    public int HitCount
    {
        get { return m_hitCount; }
    }

    public Callstack(string[] frames)
        : base(frames)
    {
        m_hitCount = 1;
    }

    internal static Callstack AddCallstack(List<Callstack> stacks, Dictionary<CallstackKey, Callstack> callstackMap, CallstackKey key)
    {
        Callstack callstackObj;
        if (callstackMap.TryGetValue(key, out callstackObj))
        {
            callstackObj.m_hitCount++;
        }
        else
        {
            callstackObj = new Callstack(key.Frames);

            callstackMap.Add(callstackObj, callstackObj);
            stacks.Add(callstackObj);
        }

        return callstackObj;
    }

    public void Dump()
    {
        Console.WriteLine("Count = {0}", this.HitCount);
        foreach (string s in this.Frames)
        {
            Console.WriteLine(s);
        }
        Console.WriteLine();
    }
};

class CallTreeNode
{
    public readonly string Function;
    public readonly Dictionary<string, CallTreeNode> Children;

    private int m_hitCount;
    public int HitCount
    {
        get { return m_hitCount; }
    }

    private CallTreeNode(string function)
    {
        this.Function = function;
        this.Children = new Dictionary<string, CallTreeNode>();
        this.m_hitCount = 1;
    }

    static public CallTreeNode AddNode(Dictionary<string, CallTreeNode> dict, string function)
    {
        CallTreeNode node;
        if (dict.TryGetValue(function, out node))
        {
            node.m_hitCount++;
            return node;
        }
        else
        {
            node = new CallTreeNode(function);
            dict.Add(function, node);

            return node;
        }
    }

    public void Dump(int indent)
    {
        for (int i = 0; i < indent; i++)
            Console.Write("  ");

        Console.WriteLine("{0} ({1})", this.Function, this.m_hitCount);

        foreach (CallTreeNode child in this.Children.Values)
        {
            child.Dump(indent + 1);
        }
    }

    internal static void AddCallstack(Dictionary<string, CallTreeNode> callTreeRootMap, CallstackKey key)
    {
        Dictionary<string, CallTreeNode> map = callTreeRootMap;

        foreach (string function in key.Frames)
        {
            CallTreeNode node = AddNode(map, function);

            map = node.Children;
        }
    }
}