FlameGraph.java

/*
 * Copyright 2018 Andrei Pangin
 *
 * This is a specialized Java port of the FlameGraph script available at
 * https://github.com/brendangregg/FlameGraph/blob/master/flamegraph.pl
 *
 * Copyright 2016 Netflix, Inc.
 * Copyright 2011 Joyent, Inc.  All rights reserved.
 * Copyright 2011 Brendan Gregg.  All rights reserved.
 *
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at docs/cddl1.txt or
 * http://opensource.org/licenses/CDDL-1.0.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at docs/cddl1.txt.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
package flamegraph;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.Reader;
import java.lang.reflect.Field;
import java.util.Locale;
import java.util.TreeMap;
import java.util.concurrent.ThreadLocalRandom;

public class FlameGraph {
    public String titletext = "Flame Graph";
    public int imagewidth = 1200;
    public int imageheight = 0;
    public int xpad = 10;
    public int frameheight = 16;
    public double minwidth = 0.1;
    public String fonttype = "Verdana";
    public int fontsize = 12;
    public double fontwidth = 0.59;
    public String nametype = "Function:";
    public boolean inverted = false;
    public String bgcolor = "rgb(240,240,220)";
    public String searchcolor = "rgb(230,0,230)";

    private final Frame root = new Frame("all");
    private int depth;
    private double scale;
    private double pct;

    public FlameGraph(String... args) throws IOException {
        String fileName = null;

        for (int i = 0; i < args.length; i++) {
            switch (args[i]) {
                case "--title":
                    titletext = args[++i];
                    break;
                case "--width":
                    imagewidth = Integer.parseInt(args[++i]);
                    break;
                case "--height":
                    frameheight = Integer.parseInt(args[++i]);
                    break;
                case "--minwidth":
                    minwidth = Double.parseDouble(args[++i]);
                    break;
                case "--fonttype":
                    fonttype = args[++i];
                    break;
                case "--fontsize":
                    fontsize = Integer.parseInt(args[++i]);
                    break;
                default:
                    if (!args[i].startsWith("--")) {
                        fileName = args[i];
                    }
            }
        }

        if (fileName != null) {
            parse(new InputStreamReader(new FileInputStream(fileName), "UTF-8"));
        }
    }

    public void parse(Reader in) throws IOException {
        try (BufferedReader br = new BufferedReader(in)) {
            for (String line; (line = br.readLine()) != null; ) {
                int space = line.lastIndexOf(' ');
                String[] trace = line.substring(0, space).split(";");
                long ticks = Long.parseLong(line.substring(space + 1));

                depth = Math.max(depth, trace.length);

                Frame frame = root;
                for (String title : trace) {
                    frame.samples += ticks;
                    frame = frame.children.computeIfAbsent(title, Frame::new);
                }
                frame.samples += ticks;
                frame.self += ticks;
            }
        }
    }

    public void dump(PrintStream out) {
        scale = (imagewidth - xpad * 2) / (double) root.samples;
        pct = 10000 / (double) root.samples;
        imageheight = Math.max(imageheight, frameheight * (depth + 1) + fontsize * 5 + 10);

        out.print(applyReplacements(SVG_HEADER));
        printText(out, imagewidth / 2, fontsize * 2, titletext, "text-anchor=\"middle\" style=\"font-size:" + (fontsize + 5) + "px\"");
        printText(out, xpad, imageheight - (fontsize + 5), " ", "id=\"details\"");
        printText(out, xpad, fontsize * 2, "Reset Zoom", "id=\"unzoom\" onclick=\"unzoom()\" style=\"opacity:0.0;cursor:pointer\"");
        printText(out, imagewidth - xpad - 100, fontsize * 2, "Search", "id=\"search\" onmouseover=\"searchover()\" onmouseout=\"searchout()\" onclick=\"search_prompt()\" style=\"opacity:0.1;cursor:pointer\"");
        printText(out, imagewidth - xpad - 100, imageheight - (fontsize + 5), " ", "id=\"matched\"");

        printFrame(out, root, xpad, imageheight - frameheight - fontsize * 3);
        out.print("</svg>\n");
    }

    // Replace $variables in the given string with field values
    private String applyReplacements(String s) {
        StringBuilder result = new StringBuilder(s.length() + 256);
        Field[] publicFields = getClass().getFields();

        int start = 0;
        for (int p = 0; (p = s.indexOf('$', p)) >= 0; p++) {
            for (Field f : publicFields) {
                String var = f.getName();
                if (s.regionMatches(p + 1, var, 0, var.length())) {
                    try {
                        result.append(s, start, p).append(f.get(this));
                    } catch (IllegalAccessException e) {
                        throw new AssertionError("Should not happen");
                    }
                    p += var.length();
                    start = p + 1;
                    break;
                }
            }
        }

        result.append(s, start, s.length());
        return result.toString();
    }

    private void printText(PrintStream out, double x, double y, String text, String attr) {
        out.printf(Locale.US, "<text x=\"%.1f\" y=\"%.1f\" %s>%s</text>\n", x, y, attr, text);
    }

    private double printFrame(PrintStream out, Frame frame, double x, double y) {
        double framewidth = frame.samples * scale;
        if (framewidth >= minwidth) {
            String title = stripSuffix(frame.title);
            int color = paletteFor(frame.title).color(ThreadLocalRandom.current().nextFloat());

            // Round to 1 digit and compensate width for rounding error
            double xr = Math.round(x * 10) / 10.0;
            double wr = (Math.round((x + framewidth) * 10) - Math.round(x * 10)) / 10.0;

            // Do not use printf in hot code since it is way too slow
            out.print("<g class=\"func_g\" onmouseover=\"s(this)\" onmouseout=\"c()\" onclick=\"zoom(this)\">\n<title>" +
                    escape(title) + " (" + toStringWithCommas(frame.samples) + " samples, " +
                    Math.round(frame.samples * pct) / 100.0 + "%)</title><rect x=\"" + xr + "\" y=\"" + y +
                    "\" width=\"" + wr + "\" height=\"" + (frameheight - 1) +
                    "\" fill=\"" + toColorString(color) + "\" rx=\"2\" ry=\"2\"/>\n" +
                    "<text x=\"" + (xr + 3) + "\" y=\"" + (y + 3 + frameheight * 0.5) + "\">" +
                    escape(trim(title, wr)) + "</text>\n</g>\n");

            x += frame.self * scale;
            y -= frameheight;

            for (Frame child : frame.children.values()) {
                x += printFrame(out, child, x, y);
            }
        }
        return framewidth;
    }

    private String stripSuffix(String title) {
        int len = title.length();
        if (len >= 4 && title.charAt(len - 1) == ']' && title.regionMatches(len - 4, "_[", 0, 2)) {
            return title.substring(0, len - 4);
        }
        return title;
    }

    // Cut the long tail that does not fit into rectangle
    private String trim(String title, double framewidth) {
        int maxLength = (int) (framewidth / (fontsize * fontwidth));
        if (maxLength < 3) {
            return "";
        } else if (title.length() > maxLength) {
            return title.substring(0, maxLength - 2) + "..";
        }
        return title;
    }

    // Escape special XML characters
    private String escape(String title) {
        if (title.indexOf('&') >= 0) title = title.replace("&", "&amp;");
        if (title.indexOf('<') >= 0) title = title.replace("<", "&lt;");
        if (title.indexOf('>') >= 0) title = title.replace(">", "&gt;");
        if (title.indexOf('"') >= 0) title = title.replace("\"", "&quot;");
        return title;
    }

    // Return a number with thousand separators, e.g. 10,023,456,007
    private String toStringWithCommas(long value) {
        char[] chars = new char[27];
        int p = 27;
        do {
            chars[--p] = (char) (value % 10 + '0');
        } while ((value /= 10) > 0 && ((p & 3) != 0 || (chars[--p] = ',') != 0));
        return new String(chars, p, 27 - p);
    }

    private static final char[] hex = "0123456789abcdef".toCharArray();

    // Convert color to a string like #80ccff
    private static String toColorString(int color) {
        return "#" +
                hex[(color >>> 20) & 15] +
                hex[(color >>> 16) & 15] +
                hex[(color >>> 12) & 15] +
                hex[(color >>> 8) & 15] +
                hex[(color >>> 4) & 15] +
                hex[color & 15];
    }

    // Choose color scheme depending on a function name
    private Palette paletteFor(String title) {
        if (title.endsWith("_[j]")) {
            return Palette.green;
        } else if (title.endsWith("_[i]")) {
            return Palette.aqua;
        } else if (title.endsWith("_[k]")) {
            return Palette.orange;
        } else if (title.contains("::")) {
            return Palette.yellow;
        } else if (title.indexOf('/') > 0 || title.indexOf('.') > 0 && Character.isUpperCase(title.charAt(0))) {
            return Palette.green;
        } else {
            return Palette.red;
        }
    }

    public static void main(String[] args) throws IOException {
        new FlameGraph(args).dump(System.out);
    }

    static class Frame {
        final String title;
        final TreeMap<String, Frame> children = new TreeMap<>();
        long samples;
        long self;

        Frame(String title) {
            this.title = title;
        }
    }

    enum Palette {
        red(0xc83232, 55, 80, 80),
        green(0x32c832, 60, 55, 60),
        yellow(0xafaf32, 55, 55, 20),
        aqua(0x32a5a5, 60, 55, 55),
        orange(0xbe5a00, 65, 65, 0);

        final int base;
        final int r, g, b;

        Palette(int base, int r, int g, int b) {
            this.base = base;
            this.r = r;
            this.g = g;
            this.b = b;
        }

        int color(float value) {
            return base + ((int) (r * value) << 16 | (int) (g * value) << 8 | (int) (b * value));
        }
    }

    private static final String SVG_HEADER = "<?xml version=\"1.0\" standalone=\"no\"?>\n" +
            "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n" +
            "<svg version=\"1.1\" width=\"$imagewidth\" height=\"$imageheight\" onload=\"init(evt)\" viewBox=\"0 0 $imagewidth $imageheight\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n" +
            "<style type=\"text/css\">\n" +
            "    text { font-family:$fonttype; font-size:$fontsizepx; fill:#000; }\n" +
            "\t.func_g:hover { stroke:black; stroke-width:0.5; cursor:pointer; }\n" +
            "</style>\n" +
            "<script type=\"text/ecmascript\">\n" +
            "<![CDATA[\n" +
            "\tvar details, searchbtn, matchedtxt, svg;\n" +
            "\tfunction init(evt) {\n" +
            "\t\tdetails = document.getElementById(\"details\").firstChild;\n" +
            "\t\tsearchbtn = document.getElementById(\"search\");\n" +
            "\t\tmatchedtxt = document.getElementById(\"matched\");\n" +
            "\t\tsvg = document.getElementsByTagName(\"svg\")[0];\n" +
            "\t\tsearching = 0;\n" +
            "\t}\n" +
            "\n" +
            "\t// mouse-over for info\n" +
            "\tfunction s(node) {\t\t// show\n" +
            "\t\tinfo = g_to_text(node);\n" +
            "\t\tdetails.nodeValue = \"$nametype \" + info;\n" +
            "\t}\n" +
            "\tfunction c() {\t\t\t// clear\n" +
            "\t\tdetails.nodeValue = ' ';\n" +
            "\t}\n" +
            "\n" +
            "\t// ctrl-F for search\n" +
            "\twindow.addEventListener(\"keydown\",function (e) {\n" +
            "\t\tif (e.keyCode === 114 || (e.ctrlKey && e.keyCode === 70)) {\n" +
            "\t\t\te.preventDefault();\n" +
            "\t\t\tsearch_prompt();\n" +
            "\t\t}\n" +
            "\t})\n" +
            "\n" +
            "\t// functions\n" +
            "\tfunction find_child(parent, name, attr) {\n" +
            "\t\tvar children = parent.childNodes;\n" +
            "\t\tfor (var i=0; i<children.length;i++) {\n" +
            "\t\t\tif (children[i].tagName == name)\n" +
            "\t\t\t\treturn (attr != undefined) ? children[i].attributes[attr].value : children[i];\n" +
            "\t\t}\n" +
            "\t\treturn;\n" +
            "\t}\n" +
            "\tfunction orig_save(e, attr, val) {\n" +
            "\t\tif (e.attributes[\"_orig_\"+attr] != undefined) return;\n" +
            "\t\tif (e.attributes[attr] == undefined) return;\n" +
            "\t\tif (val == undefined) val = e.attributes[attr].value;\n" +
            "\t\te.setAttribute(\"_orig_\"+attr, val);\n" +
            "\t}\n" +
            "\tfunction orig_load(e, attr) {\n" +
            "\t\tif (e.attributes[\"_orig_\"+attr] == undefined) return;\n" +
            "\t\te.attributes[attr].value = e.attributes[\"_orig_\"+attr].value;\n" +
            "\t\te.removeAttribute(\"_orig_\"+attr);\n" +
            "\t}\n" +
            "\tfunction g_to_text(e) {\n" +
            "\t\tvar text = find_child(e, \"title\").firstChild.nodeValue;\n" +
            "\t\treturn (text)\n" +
            "\t}\n" +
            "\tfunction g_to_func(e) {\n" +
            "\t\tvar func = g_to_text(e);\n" +
            "\t\t// if there's any manipulation we want to do to the function\n" +
            "\t\t// name before it's searched, do it here before returning.\n" +
            "\t\treturn (func);\n" +
            "\t}\n" +
            "\tfunction update_text(e) {\n" +
            "\t\tvar r = find_child(e, \"rect\");\n" +
            "\t\tvar t = find_child(e, \"text\");\n" +
            "\t\tvar w = parseFloat(r.attributes[\"width\"].value) -3;\n" +
            "\t\tvar txt = find_child(e, \"title\").textContent.replace(/\\([^(]*\\)$/,\"\");\n" +
            "\t\tt.attributes[\"x\"].value = parseFloat(r.attributes[\"x\"].value) +3;\n" +
            "\n" +
            "\t\t// Smaller than this size won't fit anything\n" +
            "\t\tif (w < 2*$fontsize*$fontwidth) {\n" +
            "\t\t\tt.textContent = \"\";\n" +
            "\t\t\treturn;\n" +
            "\t\t}\n" +
            "\n" +
            "\t\tt.textContent = txt;\n" +
            "\t\t// Fit in full text width\n" +
            "\t\tif (/^ *$/.test(txt) || t.getSubStringLength(0, txt.length) < w)\n" +
            "\t\t\treturn;\n" +
            "\n" +
            "\t\tfor (var x=txt.length-2; x>0; x--) {\n" +
            "\t\t\tif (t.getSubStringLength(0, x+2) <= w) {\n" +
            "\t\t\t\tt.textContent = txt.substring(0,x) + \"..\";\n" +
            "\t\t\t\treturn;\n" +
            "\t\t\t}\n" +
            "\t\t}\n" +
            "\t\tt.textContent = \"\";\n" +
            "\t}\n" +
            "\n" +
            "\t// zoom\n" +
            "\tfunction zoom_reset(e) {\n" +
            "\t\tif (e.attributes != undefined) {\n" +
            "\t\t\torig_load(e, \"x\");\n" +
            "\t\t\torig_load(e, \"width\");\n" +
            "\t\t}\n" +
            "\t\tif (e.childNodes == undefined) return;\n" +
            "\t\tfor(var i=0, c=e.childNodes; i<c.length; i++) {\n" +
            "\t\t\tzoom_reset(c[i]);\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\tfunction zoom_child(e, x, ratio) {\n" +
            "\t\tif (e.attributes != undefined) {\n" +
            "\t\t\tif (e.attributes[\"x\"] != undefined) {\n" +
            "\t\t\t\torig_save(e, \"x\");\n" +
            "\t\t\t\te.attributes[\"x\"].value = (parseFloat(e.attributes[\"x\"].value) - x - $xpad) * ratio + $xpad;\n" +
            "\t\t\t\tif(e.tagName == \"text\") e.attributes[\"x\"].value = find_child(e.parentNode, \"rect\", \"x\") + 3;\n" +
            "\t\t\t}\n" +
            "\t\t\tif (e.attributes[\"width\"] != undefined) {\n" +
            "\t\t\t\torig_save(e, \"width\");\n" +
            "\t\t\t\te.attributes[\"width\"].value = parseFloat(e.attributes[\"width\"].value) * ratio;\n" +
            "\t\t\t}\n" +
            "\t\t}\n" +
            "\n" +
            "\t\tif (e.childNodes == undefined) return;\n" +
            "\t\tfor(var i=0, c=e.childNodes; i<c.length; i++) {\n" +
            "\t\t\tzoom_child(c[i], x-$xpad, ratio);\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\tfunction zoom_parent(e) {\n" +
            "\t\tif (e.attributes) {\n" +
            "\t\t\tif (e.attributes[\"x\"] != undefined) {\n" +
            "\t\t\t\torig_save(e, \"x\");\n" +
            "\t\t\t\te.attributes[\"x\"].value = $xpad;\n" +
            "\t\t\t}\n" +
            "\t\t\tif (e.attributes[\"width\"] != undefined) {\n" +
            "\t\t\t\torig_save(e, \"width\");\n" +
            "\t\t\t\te.attributes[\"width\"].value = parseInt(svg.width.baseVal.value) - ($xpad*2);\n" +
            "\t\t\t}\n" +
            "\t\t}\n" +
            "\t\tif (e.childNodes == undefined) return;\n" +
            "\t\tfor(var i=0, c=e.childNodes; i<c.length; i++) {\n" +
            "\t\t\tzoom_parent(c[i]);\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\tfunction zoom(node) {\n" +
            "\t\tvar attr = find_child(node, \"rect\").attributes;\n" +
            "\t\tvar width = parseFloat(attr[\"width\"].value);\n" +
            "\t\tvar xmin = parseFloat(attr[\"x\"].value);\n" +
            "\t\tvar xmax = parseFloat(xmin + width);\n" +
            "\t\tvar ymin = parseFloat(attr[\"y\"].value);\n" +
            "\t\tvar ratio = (svg.width.baseVal.value - 2*$xpad) / width;\n" +
            "\n" +
            "\t\t// XXX: Workaround for JavaScript float issues (fix me)\n" +
            "\t\tvar fudge = 0.0001;\n" +
            "\n" +
            "\t\tvar unzoombtn = document.getElementById(\"unzoom\");\n" +
            "\t\tunzoombtn.style[\"opacity\"] = \"1.0\";\n" +
            "\n" +
            "\t\tvar el = document.getElementsByTagName(\"g\");\n" +
            "\t\tfor(var i=0;i<el.length;i++){\n" +
            "\t\t\tvar e = el[i];\n" +
            "\t\t\tvar a = find_child(e, \"rect\").attributes;\n" +
            "\t\t\tvar ex = parseFloat(a[\"x\"].value);\n" +
            "\t\t\tvar ew = parseFloat(a[\"width\"].value);\n" +
            "\t\t\t// Is it an ancestor\n" +
            "\t\t\tif ($inverted == 0) {\n" +
            "\t\t\t\tvar upstack = parseFloat(a[\"y\"].value) > ymin;\n" +
            "\t\t\t} else {\n" +
            "\t\t\t\tvar upstack = parseFloat(a[\"y\"].value) < ymin;\n" +
            "\t\t\t}\n" +
            "\t\t\tif (upstack) {\n" +
            "\t\t\t\t// Direct ancestor\n" +
            "\t\t\t\tif (ex <= xmin && (ex+ew+fudge) >= xmax) {\n" +
            "\t\t\t\t\te.style[\"opacity\"] = \"0.5\";\n" +
            "\t\t\t\t\tzoom_parent(e);\n" +
            "\t\t\t\t\te.onclick = function(e){unzoom(); zoom(this);};\n" +
            "\t\t\t\t\tupdate_text(e);\n" +
            "\t\t\t\t}\n" +
            "\t\t\t\t// not in current path\n" +
            "\t\t\t\telse\n" +
            "\t\t\t\t\te.style[\"display\"] = \"none\";\n" +
            "\t\t\t}\n" +
            "\t\t\t// Children maybe\n" +
            "\t\t\telse {\n" +
            "\t\t\t\t// no common path\n" +
            "\t\t\t\tif (ex < xmin || ex + fudge >= xmax) {\n" +
            "\t\t\t\t\te.style[\"display\"] = \"none\";\n" +
            "\t\t\t\t}\n" +
            "\t\t\t\telse {\n" +
            "\t\t\t\t\tzoom_child(e, xmin, ratio);\n" +
            "\t\t\t\t\te.onclick = function(e){zoom(this);};\n" +
            "\t\t\t\t\tupdate_text(e);\n" +
            "\t\t\t\t}\n" +
            "\t\t\t}\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\tfunction unzoom() {\n" +
            "\t\tvar unzoombtn = document.getElementById(\"unzoom\");\n" +
            "\t\tunzoombtn.style[\"opacity\"] = \"0.0\";\n" +
            "\n" +
            "\t\tvar el = document.getElementsByTagName(\"g\");\n" +
            "\t\tfor(i=0;i<el.length;i++) {\n" +
            "\t\t\tel[i].style[\"display\"] = \"block\";\n" +
            "\t\t\tel[i].style[\"opacity\"] = \"1\";\n" +
            "\t\t\tzoom_reset(el[i]);\n" +
            "\t\t\tupdate_text(el[i]);\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\n" +
            "\t// search\n" +
            "\tfunction reset_search() {\n" +
            "\t\tvar el = document.getElementsByTagName(\"rect\");\n" +
            "\t\tfor (var i=0; i < el.length; i++) {\n" +
            "\t\t\torig_load(el[i], \"fill\")\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\tfunction search_prompt() {\n" +
            "\t\tif (!searching) {\n" +
            "\t\t\tvar term = prompt(\"Enter a search term (regexp \" +\n" +
            "\t\t\t    \"allowed, eg: ^ext4_)\", \"\");\n" +
            "\t\t\tif (term != null) {\n" +
            "\t\t\t\tsearch(term)\n" +
            "\t\t\t}\n" +
            "\t\t} else {\n" +
            "\t\t\treset_search();\n" +
            "\t\t\tsearching = 0;\n" +
            "\t\t\tsearchbtn.style[\"opacity\"] = \"0.1\";\n" +
            "\t\t\tsearchbtn.firstChild.nodeValue = \"Search\"\n" +
            "\t\t\tmatchedtxt.style[\"opacity\"] = \"0.0\";\n" +
            "\t\t\tmatchedtxt.firstChild.nodeValue = \"\"\n" +
            "\t\t}\n" +
            "\t}\n" +
            "\tfunction search(term) {\n" +
            "\t\tvar re = new RegExp(term);\n" +
            "\t\tvar el = document.getElementsByTagName(\"g\");\n" +
            "\t\tvar matches = new Object();\n" +
            "\t\tvar maxwidth = 0;\n" +
            "\t\tfor (var i = 0; i < el.length; i++) {\n" +
            "\t\t\tvar e = el[i];\n" +
            "\t\t\tif (e.attributes[\"class\"].value != \"func_g\")\n" +
            "\t\t\t\tcontinue;\n" +
            "\t\t\tvar func = g_to_func(e);\n" +
            "\t\t\tvar rect = find_child(e, \"rect\");\n" +
            "\t\t\tif (rect == null) {\n" +
            "\t\t\t\t// the rect might be wrapped in an anchor\n" +
            "\t\t\t\t// if nameattr href is being used\n" +
            "\t\t\t\tif (rect = find_child(e, \"a\")) {\n" +
            "\t\t\t\t    rect = find_child(r, \"rect\");\n" +
            "\t\t\t\t}\n" +
            "\t\t\t}\n" +
            "\t\t\tif (func == null || rect == null)\n" +
            "\t\t\t\tcontinue;\n" +
            "\n" +
            "\t\t\t// Save max width. Only works as we have a root frame\n" +
            "\t\t\tvar w = parseFloat(rect.attributes[\"width\"].value);\n" +
            "\t\t\tif (w > maxwidth)\n" +
            "\t\t\t\tmaxwidth = w;\n" +
            "\n" +
            "\t\t\tif (func.match(re)) {\n" +
            "\t\t\t\t// highlight\n" +
            "\t\t\t\tvar x = parseFloat(rect.attributes[\"x\"].value);\n" +
            "\t\t\t\torig_save(rect, \"fill\");\n" +
            "\t\t\t\trect.attributes[\"fill\"].value =\n" +
            "\t\t\t\t    \"$searchcolor\";\n" +
            "\n" +
            "\t\t\t\t// remember matches\n" +
            "\t\t\t\tif (matches[x] == undefined) {\n" +
            "\t\t\t\t\tmatches[x] = w;\n" +
            "\t\t\t\t} else {\n" +
            "\t\t\t\t\tif (w > matches[x]) {\n" +
            "\t\t\t\t\t\t// overwrite with parent\n" +
            "\t\t\t\t\t\tmatches[x] = w;\n" +
            "\t\t\t\t\t}\n" +
            "\t\t\t\t}\n" +
            "\t\t\t\tsearching = 1;\n" +
            "\t\t\t}\n" +
            "\t\t}\n" +
            "\t\tif (!searching)\n" +
            "\t\t\treturn;\n" +
            "\n" +
            "\t\tsearchbtn.style[\"opacity\"] = \"1.0\";\n" +
            "\t\tsearchbtn.firstChild.nodeValue = \"Reset Search\"\n" +
            "\n" +
            "\t\t// calculate percent matched, excluding vertical overlap\n" +
            "\t\tvar count = 0;\n" +
            "\t\tvar lastx = -1;\n" +
            "\t\tvar lastw = 0;\n" +
            "\t\tvar keys = Array();\n" +
            "\t\tfor (k in matches) {\n" +
            "\t\t\tif (matches.hasOwnProperty(k))\n" +
            "\t\t\t\tkeys.push(k);\n" +
            "\t\t}\n" +
            "\t\t// sort the matched frames by their x location\n" +
            "\t\t// ascending, then width descending\n" +
            "\t\tkeys.sort(function(a, b){\n" +
            "\t\t\treturn a - b;\n" +
            "\t\t});\n" +
            "\t\t// Step through frames saving only the biggest bottom-up frames\n" +
            "\t\t// thanks to the sort order. This relies on the tree property\n" +
            "\t\t// where children are always smaller than their parents.\n" +
            "\t\tvar fudge = 0.0001;\t// JavaScript floating point\n" +
            "\t\tfor (var k in keys) {\n" +
            "\t\t\tvar x = parseFloat(keys[k]);\n" +
            "\t\t\tvar w = matches[keys[k]];\n" +
            "\t\t\tif (x >= lastx + lastw - fudge) {\n" +
            "\t\t\t\tcount += w;\n" +
            "\t\t\t\tlastx = x;\n" +
            "\t\t\t\tlastw = w;\n" +
            "\t\t\t}\n" +
            "\t\t}\n" +
            "\t\t// display matched percent\n" +
            "\t\tmatchedtxt.style[\"opacity\"] = \"1.0\";\n" +
            "\t\tpct = 100 * count / maxwidth;\n" +
            "\t\tif (pct == 100)\n" +
            "\t\t\tpct = \"100\"\n" +
            "\t\telse\n" +
            "\t\t\tpct = pct.toFixed(1)\n" +
            "\t\tmatchedtxt.firstChild.nodeValue = \"Matched: \" + pct + \"%\";\n" +
            "\t}\n" +
            "\tfunction searchover(e) {\n" +
            "\t\tsearchbtn.style[\"opacity\"] = \"1.0\";\n" +
            "\t}\n" +
            "\tfunction searchout(e) {\n" +
            "\t\tif (searching) {\n" +
            "\t\t\tsearchbtn.style[\"opacity\"] = \"1.0\";\n" +
            "\t\t} else {\n" +
            "\t\t\tsearchbtn.style[\"opacity\"] = \"0.1\";\n" +
            "\t\t}\n" +
            "\t}\n" +
            "]]>\n" +
            "</script>\n" +
            "<rect x=\"0\" y=\"0\" width=\"$imagewidth\" height=\"$imageheight\" fill=\"$bgcolor\"/>\n";
}