<!-- 
Copyright (C) 2020 Apple Inc. All rights reserved.
Copyright (C) 2011 Google Inc. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
-->
<!DOCTYPE html>
<html>
<title>Test Runtimes</title>
<style>
    :root {
        color-scheme: dark light;
        --clickable-link-color: blue;
        --item-highlight-color: red;
        --button-background-color: white;
        --panel-background-color: rgba(255, 255, 255, 0.9);
        --node-background-color: white;
        --node-hover-background-color: #eee;

        --node-border-level0-color: #444;
        --node-border-level1-color: #666;
        --node-border-level2-color: #888;
        --node-border-level3-color: #aaa;
        --node-border-level4-color: #ccc;
        
        --drop-button-text-color: canvastext;
        --drop-button-background-color: rgba(0, 0, 0, 0.1);
        --drop-button-over-background-color: rgba(0, 0, 0, 0.3);
        --drop-button-border-color: rgba(0, 0, 0, 0.3);
        --drop-button-over-border-color: rgba(0, 0, 0, 0.1);
    }

    @media (prefers-color-scheme: dark) {
        :root {
            --item-highlight-color: #F8490A;
            --button-background-color: #666;
            --panel-background-color: rgba(50, 50, 50, 0.9);
            --clickable-link-color: #9e9eff;
            --node-background-color: #222;
            --node-hover-background-color: #333;

            --node-border-level0-color: #ccc;
            --node-border-level1-color: #aaa;
            --node-border-level2-color: #777;
            --node-border-level3-color: #555;
            --node-border-level4-color: #444;

            --drop-button-text-color: canvastext;
            --drop-button-background-color: rgba(128, 128, 128, 0.1);
            --drop-button-over-background-color: rgba(128, 128, 128, 0.3);
            --drop-button-border-color: rgba(128, 128, 128, 0.3);
            --drop-button-over-border-color: rgba(128, 128, 128, 0.1);
        }
        /* Remove when webkit.org/b/209851 is fixed. */
        a:link { color: #9e9eff; }
        a:visited { color: #d0adf0; }
        a:active { color: red; }
    }

    html {
        height: 100%;
    }

    body {
        height: 100%;
        display: flex;
        flex-direction: column;
        font-family: "Helvetica Neue";
    }

    td:first-child {
        text-align: left;
    }

    td {
        text-align: right;
    }
    
    header {
        position: relative;
        height: 4rem;
    }
    
    header a {
        margin-left: 0.25em
    }

    header p {
        font-size: smaller;
    }

    #map {
        position: relative;
        z-index: 0;
        flex-grow: 1;
        cursor: pointer;
        -webkit-user-select: none;
    }

    .extra-dom {
        display: none;
        border: none;
        border-top: 1px dashed;
        padding: 4px;
        margin: 0;
        overflow: auto;
        cursor: auto;
        -webkit-user-select: text;
    }

    .error {
        color: red;
        font-style: italic;
    }

    #dropTarget {
        font-size: 10pt;
        font-weight: bold;
        color: #888;
        position: absolute;
        top: 4px;
        right: 4px;
        border: 2px solid var(--drop-button-border-color);
        background-color: var(--drop-button-background-color);
        padding: 10px;
        border-radius: 10px;
    }

    #dropTarget.dragOver {
        border: 2px solid var(--drop-button-over-border-color);
        background-color: var(--drop-button-over-background-color);
        color: var(--drop-button-text-color);
    }

    .webtreemap-node {
        /* Required attributes. */
        position: absolute;
        overflow: hidden;   /* To hide overlong captions. */
        background: var(--node-background-color);  /* Nodes must be opaque for zIndex layering. */
        border: solid 1px black;  /* Calculations assume 1px border. */

        transition: top    0.3s,
        left   0.3s,
        width  0.3s,
        height 0.3s;
    }

    /* Optional: highlight nodes on mouseover. */
    .webtreemap-node:hover {
        background: var(--node-hover-background-color);
    }

    /* Optional: Different borders depending on level. */
    .webtreemap-level0 {
        border: solid 1px var(--node-border-level0-color);
    }
    .webtreemap-level1 {
        border: solid 1px var(--node-border-level1-color);
    }
    .webtreemap-level2 {
        border: solid 1px var(--node-border-level2-color);
    }
    .webtreemap-level3 {
        border: solid 1px var(--node-border-level3-color);
    }
    .webtreemap-level4 {
        border: solid 1px var(--node-border-level4-color);
    }

    /* Optional: styling on node captions. */
    .webtreemap-caption {
        font-family: sans-serif;
        font-size: 11px;
        padding: 2px;
        text-align: center;
    }
    
    #slow-tests {
        position: absolute;
        z-index: 1;
        top: 10px;
        left: 10px;
        box-sizing: border-box;
        width: calc(100% - 20px);
        background-color: var(--panel-background-color);
        padding: 2em;
        border-radius: 10px;
        border: 1px solid gray;
    }
    
    #slow-tests.hidden {
        display: none;
    }
</style>

<script>

class WebTreeMap {
    static get borderWidth()
    {
        return 1;
    }

    static get padding()
    {
        return 1;
    }

    constructor(treeData, containerElement)
    {
        this._focusedNode = null;

        let style = getComputedStyle(containerElement, null);
        let width = parseInt(style.width);
        let height = parseInt(style.height);

        this.makeDom(treeData, 0);
        containerElement.appendChild(treeData.dom);
        this.position(treeData.dom, 0, 0, width, height);
        this.layout(treeData, 0, width, height);
    }

    focus(tree)
    {
        this._focusedNode = tree;

        // Hide all visible siblings of all our ancestors by lowering them.
        let level = 0;
        let root = tree;
        while (root.parent) {
            root = root.parent;
            level += 1;
            for (let i = 0, sibling; sibling = root.children[i]; ++i) {
                if (sibling.dom)
                    sibling.dom.style.zIndex = 0;
            }
        }
        let width = root.dom.offsetWidth;
        let height = root.dom.offsetHeight;
        // Unhide (raise) and maximize us and our ancestors.
        for (let t = tree; t.parent; t = t.parent) {
            // Shift off by border so we don't get nested borders.
            // TODO: actually make nested borders work (need to adjust width/height).
            this.position(t.dom, -WebTreeMap.borderWidth, -WebTreeMap.borderWidth, width, height);
            t.dom.style.zIndex = 1;
        }
        // And layout into the topmost box.
        this.layout(tree, level, width, height);
        this.handleFocus(tree);
    }
    
    handleFocus(tree)
    {
        // For delegation.
    }

    makeDom(tree, level)
    {
        let dom = document.createElement('div');
        dom.style.zIndex = 1;
        dom.className = 'webtreemap-node webtreemap-level' + Math.min(level, 4);

        dom.addEventListener('mousedown', e => {
            if (e.button == 0) {
                if (this._focusedNode && tree == this._focusedNode && this._focusedNode.parent)
                    this.focus(this._focusedNode.parent);
                else
                    this.focus(tree);
            }
            e.stopPropagation();
            return true;
        }, false);

        let caption = document.createElement('div');
        caption.className = 'webtreemap-caption';
        caption.innerHTML = tree.name;
        dom.appendChild(caption);

        tree.dom = dom;
        return dom;
    }

    position(dom, x, y, width, height)
    {
        // CSS width/height does not include border.
        width -= WebTreeMap.borderWidth * 2;
        height -= WebTreeMap.borderWidth * 2;

        dom.style.left   = x + 'px';
        dom.style.top    = y + 'px';
        dom.style.width  = Math.max(width, 0) + 'px';
        dom.style.height = Math.max(height, 0) + 'px';
    }

    // Given a list of rectangles |nodes|, the 1-d space available
    // |space|, and a starting rectangle index |start|, compute an span of
    // rectangles that optimizes a pleasant aspect ratio.
    //
    // Returns [end, sum], where end is one past the last rectangle and sum is the
    // 2-d sum of the rectangles' areas.
    selectSpan(nodes, space, start)
    {
        // Add rectangle one by one, stopping when aspect ratios begin to go
        // bad. Result is [start,end) covering the best run for this span.
        // http://scholar.google.com/scholar?cluster=5972512107845615474
        let node = nodes[start];
        let rmin = node.data['$area'];  // Smallest seen child so far.
        let rmax = rmin;                // Largest child.
        let rsum = 0;                   // Sum of children in this span.
        let last_score = 0;             // Best score yet found.
        let end;
        for (end = start; node = nodes[end]; ++end) {
            let size = node.data['$area'];
            if (size < rmin)
                rmin = size;
            if (size > rmax)
                rmax = size;
            rsum += size;

            // This formula is from the paper, but you can easily prove to
            // yourself it's taking the larger of the x/y aspect ratio or the
            // y/x aspect ratio. The additional magic fudge constant of 5
            // makes us prefer wider rectangles to taller ones.
            let score = Math.max(5 * space * space * rmax / (rsum * rsum), 1 * rsum * rsum / (space * space * rmin));
            if (last_score && score > last_score) {
                rsum -= size;    // Undo size addition from just above.
                break;
            }
            last_score = score;
        }
        return [end, rsum];
    }

    layout(tree, level, width, height)
    {
        if (!('children' in tree))
            return;

        let total = tree.data['$area'];

        // XXX why do I need an extra -1/-2 here for width/height to look right?
        let x1 = 0, y1 = 0, x2 = width - 1, y2 = height - 2;
        x1 += WebTreeMap.padding; y1 += WebTreeMap.padding;
        x2 -= WebTreeMap.padding; y2 -= WebTreeMap.padding;
        y1 += 14; // XXX get first child height for caption spacing

        let pixels_to_units = Math.sqrt(total / ((x2 - x1) * (y2 - y1)));

        for (let start = 0, child; child = tree.children[start]; ++start) {
            if (x2 - x1 < 60 || y2 - y1 < 40) {
                if (child.dom) {
                    child.dom.style.zIndex = 0;
                    this.position(child.dom, -2, -2, 0, 0);
                }
                continue;
            }

            // In theory we can dynamically decide whether to split in x or y based
            // on aspect ratio. In practice, changing split direction with this
            // layout doesn't look very good.
            //   var ysplit = (y2 - y1) > (x2 - x1);
            let ysplit = true;

            let space;  // Space available along layout axis.
            if (ysplit)
                space = (y2 - y1) * pixels_to_units;
            else
                space = (x2 - x1) * pixels_to_units;

            let span = this.selectSpan(tree.children, space, start);
            let end = span[0];
            let rsum = span[1];

            // Now that we've selected a span, lay out rectangles [start,end) in our
            // available space.
            let x = x1;
            let y = y1;
            for (let i = start; i < end; ++i) {
                child = tree.children[i];
                if (!child.dom) {
                    child.parent = tree;
                    child.dom = this.makeDom(child, level + 1);
                    tree.dom.appendChild(child.dom);
                } else {
                    child.dom.style.zIndex = 1;
                }
                let size = child.data['$area'];
                let frac = size / rsum;
                if (ysplit) {
                    width = rsum / space;
                    height = size / width;
                } else {
                    height = rsum / space;
                    width = size / height;
                }
                width /= pixels_to_units;
                height /= pixels_to_units;
                width = Math.round(width);
                height = Math.round(height);
                this.position(child.dom, x, y, width, height);
                if ('children' in child) {
                    this.layout(child, level + 1, width, height);
                }
                if (ysplit)
                    y += height;
                else
                    x += width;
            }

            // Shrink our available space based on the amount we used.
            if (ysplit)
                x1 += Math.round((rsum / space) / pixels_to_units);
            else
                y1 += Math.round((rsum / space) / pixels_to_units);

            // end points one past where we ended, which is where we want to
            // begin the next iteration, but subtract one to balance the ++ in
            // the loop.
            start = end - 1;
        }
    }
};

class Utils {
  
    static humanReadableTime(milliseconds)
    {
        if (milliseconds < 1000)
            return Math.floor(milliseconds) + 'ms';
        else if (milliseconds < 60000)
            return (milliseconds / 1000).toPrecision(2) + 's';

        let minutes = Math.floor(milliseconds / 60000);
        let seconds = Math.floor((milliseconds - minutes * 60000) / 1000);
        return minutes + 'm' + seconds + 's';
    }
};

class DataConverter {

    static convertToWebTreemapFormat(rootNodeName, tree)
    {
        return DataConverter._recursiveConvertNode(rootNodeName, tree);
    }

    static convertToFlatListSortedByRuntime(tree)
    {
        let testList = [];
        DataConverter._recursiveBuildTestList(tree, '', testList);
        
        testList.sort(function(a, b) {
            let aTime = a.runtime;
            let bTime = b.runtime;
            return bTime - aTime;
        });
        
        return testList;
    }
  
    /*
        stats.json looks like:
        {
            "imported": {
                "w3c": {
                    "web-platform-tests": {
                        "IndexedDB": {
                            "idbobjectstore_get4.htm": {
                                "results": [
                                    12,         // worker number
                                    260,        // test number
                                    41632,      // worker pid
                                    50,         // test runtime (ms)
                                    54          // total runtime (ms; includes time to run ref test, do pixel comparison etc.)
                                ],
                                ...
                            }
                        }
                    }
                }
            }
        }    
    */
  
    static _recursiveConvertNode(treename, tree, path)
    {
        let total = 0;
        let childCount = 0;
        let children = [];
        for (let name in tree) {
            let treeNode = tree[name];
            if ('results' in treeNode) {
                let times = treeNode.results;
                if (!times.hasOwnProperty('length'))
                    continue;

                let test_total_time = treeNode.results[4];
                let node = {
                    'data': { '$area': test_total_time },
                    'name': name + " (" + Utils.humanReadableTime(test_total_time) + ")"
                };
                children.push(node);
                total += test_total_time;
                childCount++;
            } else {
                let newPath = path ? path + '/' + name : name;
                let subtree = DataConverter._recursiveConvertNode(name, treeNode, newPath);
                children.push(subtree);
                total += subtree['data']['$area'];
                childCount += subtree['childCount'];
            }
        }

        children.sort(function(a, b) {
            let aTime = a.data['$area']
            let bTime = b.data['$area']
            return bTime - aTime;
        });

        return {
            'data': { '$area': total },
            'name': treename + ' (' + Utils.humanReadableTime(total) + ' - ' + childCount + ' tests)',
            'children': children,
            'childCount': childCount,
            'path': path
        };
    }

    static _recursiveBuildTestList(tree, path, list)
    {
        for (let name in tree) {
            let treeNode = tree[name];
            if ('results' in treeNode) {
                let times = treeNode.results;
                if (!times.hasOwnProperty('length'))
                    continue;

                let test_total_time = treeNode.results[4];
                let node = {
                    'name' : path + '/' + name,
                    'runtime' : test_total_time,
                    'human_readable_runtime' : Utils.humanReadableTime(test_total_time),
                };
                list.push(node);
            } else {
                let newPath = path ? path + '/' + name : name;
                let subtree = DataConverter._recursiveBuildTestList(treeNode, newPath, list);
            }
        }
    }
};

let treeMapController;
class TreeMapController {
  
    constructor(jsonData, containerElement)
    {
        this.treeMapData = DataConverter.convertToWebTreemapFormat('LayoutTests', jsonData);
        this.treeMap = new WebTreeMap(this.treeMapData, containerElement);
    }
    
    resetZoom()
    {
        focus(this.webTreeMap);
    }
};

let slowTestListController;
class SlowTestListController {
  
    constructor(jsonData, containerElement)
    {
        this.numTestsToShow = 200;
        this.testList = DataConverter.convertToFlatListSortedByRuntime(jsonData);
        this.containerElement = containerElement;
        this.contentsElement = containerElement.querySelector('.content');
        this.contentsElement.innerHTML = '';
        this._buildTestListTable();
    }
    
    show()
    {
        this.containerElement.classList.remove('hidden');
    }
    
    hide()
    {
        this.containerElement.classList.add('hidden');
    }
    
    _buildTestListTable()
    {
        let tableContainer = document.createElement('div');
        
        tableContainer.innerHTML = `<table>
                 <tr><th>Test</th><th>Runtime</th></tr>
            </table>
        `;
        
        let table = tableContainer.firstChild;
        let testList = this.testList.slice(0, this.numTestsToShow);
        
        for (let test of testList) {
            let tr = document.createElement('tr');
            let labelCell = document.createElement('td');
            let dataCell = document.createElement('td');
            
            labelCell.textContent = test['name'];
            dataCell.textContent = test['human_readable_runtime'];
            
            tr.appendChild(labelCell);
            tr.appendChild(dataCell);
            table.appendChild(tr);
        }
        
        this.contentsElement.appendChild(tableContainer);
    }
};

if (window.testRunner) {
    testRunner.dumpAsText();
    testRunner.waitUntilDone();
}

function setupControllers(jsonString)
{
    let jsonData = JSON.parse(jsonString);
    treeMapController = new TreeMapController(jsonData, document.getElementById('map'));
    slowTestListController = new SlowTestListController(jsonData, document.getElementById('slow-tests'));
}

function setupInterface()
{
    // See if we have a file to load specified in the query string.
    let query_parameters = {};
    let pairs = window.location.href.slice(window.location.href.indexOf('?') + 1).split('&');
    let filename = 'stats.json';

    for (let i = 0; i < pairs.length; i++) {
        let pair = pairs[i].split('=');
        query_parameters[pair[0]] = decodeURIComponent(pair[1]);
    }

    if ('filename' in query_parameters)
        filename = query_parameters['filename'];

    // This is used for local files, so we can't use fetch().
    var request = new XMLHttpRequest();
    request.open("GET", filename, true);
    request.addEventListener('load', () => {
        setupControllers(request.responseText);
        if (window.testRunner)
            testRunner.notifyDone();
    });
    request.addEventListener('error', () => {
        console.log('Failed to load stats.json');
    });
    request.send();

    let drop_target = document.getElementById('dropTarget');

    drop_target.addEventListener('dragenter', function (e) {
        drop_target.className = 'dragOver';
        e.stopPropagation();
        e.preventDefault();
    }, false);

    drop_target.addEventListener('dragover', function (e) {
        e.stopPropagation();
        e.preventDefault();
    }, false);

    drop_target.addEventListener('dragleave', function (e) {
        drop_target.className = '';
        e.stopPropagation();
        e.preventDefault();
    }, false);

    drop_target.addEventListener('drop', function (e) {
        drop_target.className = '';
        e.stopPropagation();
        e.preventDefault();

        for (let i = 0; i < e.dataTransfer.files.length; ++i) {
            let file = e.dataTransfer.files[i];

            let reader = new FileReader();
            reader.filename = file.name;
            reader.onload = function(e) {
                setupControllers(reader.result);
            };

            reader.readAsText(file);
            document.title = 'Test result times: ' + reader.filename;
        }
    }, false);
}

window.addEventListener('load', setupInterface, false);
</script>
<body>
<header>
    <div id="dropTarget">Drop stats.json file here to load.</div>
    <p>Click on a box to zoom in. Click on the outermost box to zoom out. <a href="" onclick="treeMapController.resetZoom()">Reset</a> <button onclick="slowTestListController.show()">Show Slowest Tests</button></p>
    </div>
</header>
<section id='map'></section>
<section id='slow-tests' class="hidden">
    <button class='close' onclick="slowTestListController.hide()">Close</button>
    <div class="content"></div>
</section>
</body>
</html>
