# This file is part of the Luau programming language and is licensed under MIT License; see LICENSE.txt for details

class Node:
    def __init__(self):
        self.name = ""
        self.children = {}
        # computed
        self.depth = 0
        self.width = 0
        self.offset = 0

    def child(self, name):
        node = self.children.get(name)
        if not node:
            node = self.__class__()
            node.name = name
            self.children[name] = node
        return node

    def subtree(self):
        result = [self]
        offset = 0

        while offset < len(result):
            p = result[offset]
            offset += 1
            for c in p.children.values():
                result.append(c)

        return result

def escape(s):
    return s.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;")

def layout(root, widthcb):
    for n in reversed(root.subtree()):
        # propagate width to the parent
        n.width = widthcb(n)
        for c in n.children.values():
            n.width += c.width

        # compute offset from parent for every child in width order (layout order)
        offset = 0
        for c in sorted(n.children.values(), key = lambda x: x.width, reverse = True):
            c.offset = offset
            offset += c.width

    for n in root.subtree():
        for c in n.children.values():
            c.depth = n.depth + 1
            c.offset += n.offset

# svg template (stolen from framegraph.pl)
template = r"""<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg version="1.1" width="1200" height="$height" onload="init(evt)" viewBox="0 0 1200 $height" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<!-- Flame graph stack visualization. See https://github.com/brendangregg/FlameGraph for latest version, and http://www.brendangregg.com/flamegraphs.html for examples. -->
<defs>
    <linearGradient id="background" y1="0" y2="1" x1="0" x2="0" >
        <stop stop-color="$gradient-start" offset="5%" />
        <stop stop-color="$gradient-end" offset="95%" />
    </linearGradient>
</defs>
<style type="text/css">
    text { font-family:Verdana; font-size:12px; fill:rgb(0,0,0); }
    #search, #ignorecase { opacity:0.1; cursor:pointer; }
    #search:hover, #search.show, #ignorecase:hover, #ignorecase.show { opacity:1; }
    #subtitle { text-anchor:middle; font-color:rgb(160,160,160); }
    #title { text-anchor:middle; font-size:17px}
    #unzoom { cursor:pointer; }
    #frames > *:hover { stroke:black; stroke-width:0.5; cursor:pointer; }
    .hide { display:none; }
    .parent { opacity:0.5; }
</style>
<script type="text/ecmascript">
<![CDATA[
    "use strict";
    var details, searchbtn, unzoombtn, matchedtxt, svg, searching, currentSearchTerm, ignorecase, ignorecaseBtn;
    function init(evt) {
        details = document.getElementById("details").firstChild;
        searchbtn = document.getElementById("search");
        ignorecaseBtn = document.getElementById("ignorecase");
        unzoombtn = document.getElementById("unzoom");
        matchedtxt = document.getElementById("matched");
        svg = document.getElementsByTagName("svg")[0];
        searching = 0;
        currentSearchTerm = null;
    }

    window.addEventListener("click", function(e) {
        var target = find_group(e.target);
        if (target) {
            if (target.nodeName == "a") {
                if (e.ctrlKey === false) return;
                e.preventDefault();
            }
            if (target.classList.contains("parent")) unzoom();
            zoom(target);
        }
        else if (e.target.id == "unzoom") unzoom();
        else if (e.target.id == "search") search_prompt();
        else if (e.target.id == "ignorecase") toggle_ignorecase();
    }, false)

    // mouse-over for info
    // show
    window.addEventListener("mouseover", function(e) {
        var target = find_group(e.target);
        if (target) details.nodeValue = g_to_text(target);
    }, false)

    // clear
    window.addEventListener("mouseout", function(e) {
        var target = find_group(e.target);
        if (target) details.nodeValue = ' ';
    }, false)

    // ctrl-F for search
    window.addEventListener("keydown",function (e) {
        if (e.keyCode === 114 || (e.ctrlKey && e.keyCode === 70)) {
            e.preventDefault();
            search_prompt();
        }
    }, false)

    // ctrl-I to toggle case-sensitive search
    window.addEventListener("keydown",function (e) {
        if (e.ctrlKey && e.keyCode === 73) {
            e.preventDefault();
            toggle_ignorecase();
        }
    }, false)

    // functions
    function find_child(node, selector) {
        var children = node.querySelectorAll(selector);
        if (children.length) return children[0];
        return;
    }
    function find_group(node) {
        var parent = node.parentElement;
        if (!parent) return;
        if (parent.id == "frames") return node;
        return find_group(parent);
    }
    function orig_save(e, attr, val) {
        if (e.attributes["_orig_" + attr] != undefined) return;
        if (e.attributes[attr] == undefined) return;
        if (val == undefined) val = e.attributes[attr].value;
        e.setAttribute("_orig_" + attr, val);
    }
    function orig_load(e, attr) {
        if (e.attributes["_orig_"+attr] == undefined) return;
        e.attributes[attr].value = e.attributes["_orig_" + attr].value;
        e.removeAttribute("_orig_"+attr);
    }
    function g_to_text(e) {
        var text = find_child(e, "details").firstChild.nodeValue;
        return (text)
    }
    function g_to_func(e) {
        var child = find_child(e, "rawtext");
        return child ? child.textContent : null;
    }
    function update_text(e) {
        var r = find_child(e, "rect");
        var t = find_child(e, "text");
        var w = parseFloat(r.attributes.width.value) -3;
        var txt = find_child(e, "rawtext").textContent.replace(/\([^(]*\)$/,"");
        t.attributes.x.value = parseFloat(r.attributes.x.value) + 3;

        // Smaller than this size won't fit anything
        if (w < 2 * 12 * 0.59) {
            t.textContent = "";
            return;
        }

        t.textContent = txt;
        // Fit in full text width
        if (/^ *$/.test(txt) || t.getSubStringLength(0, txt.length) < w)
            return;

        for (var x = txt.length - 2; x > 0; x--) {
            if (t.getSubStringLength(0, x + 2) <= w) {
                t.textContent = txt.substring(0, x) + "..";
                return;
            }
        }
        t.textContent = "";
    }

    // zoom
    function zoom_reset(e) {
        if (e.attributes != undefined) {
            orig_load(e, "x");
            orig_load(e, "width");
        }
        if (e.childNodes == undefined) return;
        for (var i = 0, c = e.childNodes; i < c.length; i++) {
            zoom_reset(c[i]);
        }
    }
    function zoom_child(e, x, ratio) {
        if (e.attributes != undefined) {
            if (e.attributes.x != undefined) {
                orig_save(e, "x");
                e.attributes.x.value = (parseFloat(e.attributes.x.value) - x - 10) * ratio + 10;
                if (e.tagName == "text")
                    e.attributes.x.value = find_child(e.parentNode, "rect[x]").attributes.x.value + 3;
            }
            if (e.attributes.width != undefined) {
                orig_save(e, "width");
                e.attributes.width.value = parseFloat(e.attributes.width.value) * ratio;
            }
        }

        if (e.childNodes == undefined) return;
        for (var i = 0, c = e.childNodes; i < c.length; i++) {
            zoom_child(c[i], x - 10, ratio);
        }
    }
    function zoom_parent(e) {
        if (e.attributes) {
            if (e.attributes.x != undefined) {
                orig_save(e, "x");
                e.attributes.x.value = 10;
            }
            if (e.attributes.width != undefined) {
                orig_save(e, "width");
                e.attributes.width.value = parseInt(svg.width.baseVal.value) - (10 * 2);
            }
        }
        if (e.childNodes == undefined) return;
        for (var i = 0, c = e.childNodes; i < c.length; i++) {
            zoom_parent(c[i]);
        }
    }
    function zoom(node) {
        var attr = find_child(node, "rect").attributes;
        var width = parseFloat(attr.width.value);
        var xmin = parseFloat(attr.x.value);
        var xmax = parseFloat(xmin + width);
        var ymin = parseFloat(attr.y.value);
        var ratio = (svg.width.baseVal.value - 2 * 10) / width;

        // XXX: Workaround for JavaScript float issues (fix me)
        var fudge = 0.0001;

        unzoombtn.classList.remove("hide");

        var el = document.getElementById("frames").children;
        for (var i = 0; i < el.length; i++) {
            var e = el[i];
            var a = find_child(e, "rect").attributes;
            var ex = parseFloat(a.x.value);
            var ew = parseFloat(a.width.value);
            var upstack;
            // Is it an ancestor
            if ($flip == 1) {
                upstack = parseFloat(a.y.value) > ymin;
            } else {
                upstack = parseFloat(a.y.value) < ymin;
            }
            if (upstack) {
                // Direct ancestor
                if (ex <= xmin && (ex+ew+fudge) >= xmax) {
                    e.classList.add("parent");
                    zoom_parent(e);
                    update_text(e);
                }
                // not in current path
                else
                    e.classList.add("hide");
            }
            // Children maybe
            else {
                // no common path
                if (ex < xmin || ex + fudge >= xmax) {
                    e.classList.add("hide");
                }
                else {
                    zoom_child(e, xmin, ratio);
                    update_text(e);
                }
            }
        }
        search();
    }
    function unzoom() {
        unzoombtn.classList.add("hide");
        var el = document.getElementById("frames").children;
        for(var i = 0; i < el.length; i++) {
            el[i].classList.remove("parent");
            el[i].classList.remove("hide");
            zoom_reset(el[i]);
            update_text(el[i]);
        }
        search();
    }

    // search
    function toggle_ignorecase() {
        ignorecase = !ignorecase;
        if (ignorecase) {
            ignorecaseBtn.classList.add("show");
        } else {
            ignorecaseBtn.classList.remove("show");
        }
        reset_search();
        search();
    }
    function reset_search() {
        var el = document.querySelectorAll("#frames rect");
        for (var i = 0; i < el.length; i++) {
            orig_load(el[i], "fill")
        }
    }
    function search_prompt() {
        if (!searching) {
            var term = prompt("Enter a search term (regexp " +
                "allowed, eg: ^ext4_)"
                + (ignorecase ? ", ignoring case" : "")
                + "\nPress Ctrl-i to toggle case sensitivity", "");
            if (term != null) {
                currentSearchTerm = term;
                search();
            }
        } else {
            reset_search();
            searching = 0;
            currentSearchTerm = null;
            searchbtn.classList.remove("show");
            searchbtn.firstChild.nodeValue = "Search"
            matchedtxt.classList.add("hide");
            matchedtxt.firstChild.nodeValue = ""
        }
    }
    function search(term) {
        if (currentSearchTerm === null) return;
        var term = currentSearchTerm;

        var re = new RegExp(term, ignorecase ? 'i' : '');
        var el = document.getElementById("frames").children;
        var matches = new Object();
        var maxwidth = 0;
        for (var i = 0; i < el.length; i++) {
            var e = el[i];
            var func = g_to_func(e);
            var rect = find_child(e, "rect");
            if (func == null || rect == null)
                continue;

            // Save max width. Only works as we have a root frame
            var w = parseFloat(rect.attributes.width.value);
            if (w > maxwidth)
                maxwidth = w;

            if (func.match(re)) {
                // highlight
                var x = parseFloat(rect.attributes.x.value);
                orig_save(rect, "fill");
                rect.attributes.fill.value = "rgb(230,0,230)";

                // remember matches
                if (matches[x] == undefined) {
                    matches[x] = w;
                } else {
                    if (w > matches[x]) {
                        // overwrite with parent
                        matches[x] = w;
                    }
                }
                searching = 1;
            }
        }
        if (!searching)
            return;

        searchbtn.classList.add("show");
        searchbtn.firstChild.nodeValue = "Reset Search";

        // calculate percent matched, excluding vertical overlap
        var count = 0;
        var lastx = -1;
        var lastw = 0;
        var keys = Array();
        for (k in matches) {
            if (matches.hasOwnProperty(k))
                keys.push(k);
        }
        // sort the matched frames by their x location
        // ascending, then width descending
        keys.sort(function(a, b){
            return a - b;
        });
        // Step through frames saving only the biggest bottom-up frames
        // thanks to the sort order. This relies on the tree property
        // where children are always smaller than their parents.
        var fudge = 0.0001; // JavaScript floating point
        for (var k in keys) {
            var x = parseFloat(keys[k]);
            var w = matches[keys[k]];
            if (x >= lastx + lastw - fudge) {
                count += w;
                lastx = x;
                lastw = w;
            }
        }
        // display matched percent
        matchedtxt.classList.remove("hide");
        var pct = 100 * count / maxwidth;
        if (pct != 100) pct = pct.toFixed(1)
        matchedtxt.firstChild.nodeValue = "Matched: " + pct + "%";
    }
]]>
</script>
<rect x="0.0" y="0" width="1200.0" height="$height.0" fill="url(#background)"  />
<text id="title" x="600.00" y="24" >$title</text>
<text id="unzoom" x="10.00" y="24" class="hide">Reset Zoom</text>
<text id="search" x="1090.00" y="24" >Search</text>
<text id="ignorecase" x="1174.00" y="24" >ic</text>
<text id="matched" x="1090.00" y="$status" > </text>
<text id="details" x="10.00" y="$status" > </text>
<g id="frames">
"""

def namehash(s):
    # FNV-1a
    hval = 0x811c9dc5
    for ch in s:
        hval = hval ^ ord(ch)
        hval = hval * 0x01000193
        hval = hval % (2 ** 32)
    return (hval % 31337) / 31337.0

def display(root, title, colors, flip = False):
    if colors == "cold":
        gradient_start = "#eef2ee"
        gradient_end = "#e0ffe0"
    else:
        gradient_start = "#eeeeee"
        gradient_end = "#eeeeb0"

    maxdepth = 0
    for n in root.subtree():
        maxdepth = max(maxdepth, n.depth)

    svgheight = maxdepth * 16 + 3 * 16 + 2 * 16

    print(template
        .replace("$title", title)
        .replace("$gradient-start", gradient_start)
        .replace("$gradient-end", gradient_end)
        .replace("$height", str(svgheight))
        .replace("$status", str(svgheight - 16 + 3))
        .replace("$flip", str(int(flip)))
    )

    framewidth = 1200 - 20

    def pixels(x):
        return float(x) / root.width * framewidth if root.width > 0 else 0

    for n in root.subtree():
        if pixels(n.width) < 0.1:
            continue

        x = 10 + pixels(n.offset)
        y = (maxdepth - 1 - n.depth if flip else n.depth) * 16 + 3 * 16
        width = pixels(n.width)
        height = 15

        if colors == "cold":
            fillr = 0
            fillg = int(190 + 50 * namehash(n.name))
            fillb = int(210 * namehash(n.name[::-1]))
        else:
            fillr = int(205 + 50 * namehash(n.name))
            fillg = int(230 * namehash(n.name[::-1]))
            fillb = int(55 * namehash(n.name[::-2]))

        fill = "rgb({},{},{})".format(fillr, fillg, fillb)
        chars = width / (12 * 0.59)

        text = n.text()

        if chars >= 3:
            if chars < len(text):
                text = text[:int(chars-2)] + ".."
        else:
            text = ""

        print("<g>")
        print("<title>{}</title>".format(escape(n.title())))
        print("<details>{}</details>".format(escape(n.details(root))))
        print("<rect x='{}' y='{}' width='{}' height='{}' fill='{}' rx='2' ry='2' />".format(x, y, width, height, fill))
        print("<text x='{}' y='{}'>{}</text>".format(x + 3, y + 10.5, escape(text)))
        print("<rawtext>{}</rawtext>".format(escape(n.text())))
        print("</g>")

    print("</g>\n</svg>\n")