runtime/tools/graphexplorer/graphexplorer.js

// Copyright (c) 2019, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

// TODO:
//  - starting dominator treemap from a group of nodes instead of only a
//    single node

"use strict";

function Graph() {
  // Create all slots up front to prevent V8 map transitions.

  // We extensively use parallel arrays instead of objects like
  //
  // function Vertex {
  //   this.size = 0;
  //   this.successors = new Array();
  //   this.predecessors = new Array();
  //   this.semi = 0;
  //   this.dom = 0;
  //   this.label = 0;
  //   this.parent = 0;
  //   this.ancestor = 0;
  // }
  //
  // This avoids GC work in V8, and it allows us to release the memory for
  // intermediate values that are only needed while computing the dominators.

  // Inputs.
  this.N_ = 0;  // Number of nodes.
  this.E_ = 0;  // Number of edges.
  this.strings_ = null;
  this.name_ = null;
  this.class_ = null;
  this.shallowSize_ = null;
  this.firstSuccessor_ = null;
  this.successors_ = null;
  this.successorName_ = null;

  // Outputs.
  this.shallowSizeSum_ = 0;
  this.firstPredecessor_ = null;
  this.predecessors_ = null;
  this.predecessorName_ = null;
  this.retainedSize_ = null;
  this.ownedSize_ = null;
  this.successorsOwnedSize_ = null;
  this.dom_ = null;
  this.domHead_ = null;
  this.domNext_ = null;
  this.mergedDomHead_ = null;
  this.mergedDomNext_ = null;

  // Intermediates.
  this.Nconnected_ = 0;  // Number of nodes reachable from root.
  this.vertex_ = null;
  this.semi_ = null;
  this.parent_ = null;
  this.ancestor_ = null;
  this.label_ = null;
  this.bucket_ = null;
}

// Load a graph in V8 heap profile format from parsed JSON `data`.
Graph.prototype.loadV8Profile = function(data) {
  console.log("Building successors...");

  const N = data.snapshot.node_count;
  const E = data.snapshot.edge_count;

  const firstSuccessor = new Uint32Array(N + 2);
  const successors = new Uint32Array(E);
  const successorName = new Uint32Array(E);

  const name = new Uint32Array(N + 1);
  const clazz = new Array(N + 1);
  const shallowSize = new Uint32Array(N + 1);
  let shallowSizeSum = 0;

  const node_stride = data.snapshot.meta.node_fields.length;
  const node_type_offset = data.snapshot.meta.node_fields.indexOf("type");
  const node_name_offset = data.snapshot.meta.node_fields.indexOf("name");
  const node_id_offset = data.snapshot.meta.node_fields.indexOf("id");
  const node_size_offset = data.snapshot.meta.node_fields.indexOf("self_size");
  const node_edge_count_offset = data.snapshot.meta.node_fields.indexOf("edge_count");

  const edge_stride = data.snapshot.meta.edge_fields.length;
  const edge_type_offset = data.snapshot.meta.edge_fields.indexOf("type");
  const edge_name_or_index_offset = data.snapshot.meta.edge_fields.indexOf("name_or_index");
  const edge_target_offset = data.snapshot.meta.edge_fields.indexOf("to_node");
  const edge_type_property = data.snapshot.meta.edge_types[0].indexOf("property");

  let nextSuccessorIndex = 0;
  let edge_cursor = 0;
  let i = 1;
  for (let node_cursor = 0;
       node_cursor < data.nodes.length;
       node_cursor += node_stride) {
    let type = data.nodes[node_cursor + node_type_offset];
    let node_name = data.nodes[node_cursor + node_name_offset];
    let id = data.nodes[node_cursor + node_id_offset];
    let self_size = data.nodes[node_cursor + node_size_offset];
    let edge_count = data.nodes[node_cursor + node_edge_count_offset];

    name[i] = node_name;
    clazz[i] = data.snapshot.meta.node_types[0][type];
    shallowSize[i] = self_size;
    shallowSizeSum += self_size;
    firstSuccessor[i] = nextSuccessorIndex;

    for (let j = 0; j < edge_count; j++) {
      let edge_type = data.edges[edge_cursor + edge_type_offset];
      let edge_name_or_index = data.edges[edge_cursor + edge_name_or_index_offset];
      let edge_to_node = (data.edges[edge_cursor + edge_target_offset] / node_stride) + 1;
      edge_cursor += edge_stride;

      if (edge_to_node < 1 || edge_to_node > N) {
        throw "Invalid edge target";
      }

      successors[nextSuccessorIndex] = edge_to_node;

      if (edge_type == edge_type_property) {
        successorName[nextSuccessorIndex] = edge_name_or_index;
      }

      nextSuccessorIndex++;
    }

    i++;
  }
  firstSuccessor[N + 1] = nextSuccessorIndex;

  if (i != (N + 1)) {
    throw "Incorrect node_count!";
  }
  if (nextSuccessorIndex != E) {
    throw "Incorrect edge_count!";
  }

  this.N_ = N;
  this.E_ = E;
  this.strings_ = data.strings;
  this.firstSuccessor_ = firstSuccessor;
  this.successorName_ = successorName;
  this.successors_ = successors;
  this.name_ = name;
  this.class_ = clazz;
  this.shallowSize_ = shallowSize;
  this.shallowSizeSum_ = shallowSizeSum;
};

// Load a graph in Dart heap snapshot format from ArrayBuffer `data`.
Graph.prototype.loadDartHeapSnapshot = function(data) {
  console.log("Building successors...");

  let stream = new Stream(data);

  for (let i = 0; i < 8; i++) {
    if (stream.byte() != 'dartheap'.charCodeAt(i)) {
      throw "Wrong format identifier."
    }
  }

  stream.uleb128();  // Flags.
  stream.utf8();     // Name.
  stream.uleb128();  // Shallow size (used).
  stream.uleb128();  // Capacity.
  stream.uleb128();  // External size.

  const strings = new Array();
  strings.push("???");

  const classCount = stream.uleb128();
  const classNames = new Uint32Array(classCount + 1);
  classNames[0] = strings.length;
  strings.push("Root");
  const classEdges = new Array(classCount + 1);
  for (let cid = 1; cid <= classCount; cid++) {
    stream.uleb128();  // Flags.
    classNames[cid] = strings.length;
    strings.push(stream.utf8());  // Class name.
    stream.utf8();  // Library name.
    stream.utf8();  // Library name.
    stream.utf8();  // Reserved.
    const fieldCount = stream.uleb128();
    const edgeNames = new Array(fieldCount + 1);
    classEdges[cid] = edgeNames;
    for (let j = 0; j < fieldCount; j++) {
      stream.uleb128();  // Flags.
      const fieldIndex = stream.uleb128();
      const fieldName = stream.utf8();
      stream.utf8();  // Reserved.

      edgeNames[fieldIndex] = strings.length;
      strings.push(fieldName);
    }
  }

  const E = stream.uleb128();  // Reference count.
  const N = stream.uleb128();  // Object count.

  const firstSuccessor = new Uint32Array(N + 2);
  const successors = new Uint32Array(E);
  const successorName = new Uint32Array(E);
  const name = new Uint32Array(N + 1);
  const clazz = new Array(N + 1);
  const shallowSize = new Uint32Array(N + 1);

  name[0] = strings.length;
  strings.push("<omitted-object>");
  clazz[0] = "<omitted-object>";
  const unknownEdge = strings.length;
  strings.push("<unknown>");

  let shallowSizeSum = 0;
  let nextSuccessorIndex = 0;
  for (let i = 1; i <= N; i++) {
    const cid = stream.uleb128();
    clazz[i] = strings[classNames[cid]];
    const objShallowSize = stream.uleb128();
    shallowSize[i] = objShallowSize;
    shallowSizeSum += objShallowSize;

    const tag = stream.uleb128();
    switch (tag) {
      case 0:  // NoData
        name[i] = classNames[cid];
        break;
      case 1:  // NullData
        name[i] = strings.length;
        strings.push("null");
        break;
      case 2:  // BoolData
        name[i] = strings.length;
        strings.push(stream.uleb128() == 0 ? "false" : "true");
        break;
      case 3:  // IntegerData
        name[i] = stream.sleb128();
        break;
      case 4:  // DoubleData
        name[i] = stream.float64();
        break;
      case 5:  // Latin1StringData
        stream.uleb128();  // Full length.
        name[i] = strings.length;
        strings.push(stream.latin1());
        break;
      case 6:  // Utf16StringData
        stream.uleb128();  // Full length.
        name[i] = strings.length;
        strings.push(stream.utf16());
        break;
      case 7:  // LengthData
        name[i] = strings.length;
        strings.push(strings[classNames[cid]] + "(" + stream.uleb128() + ")");
        break;
      case 8:  // NameData
        name[i] = strings.length;
        strings.push(stream.utf8());
        break;
      default:
        throw "Unknown tag " + tag;
    }

    firstSuccessor[i] = nextSuccessorIndex;
    const edge_count = stream.uleb128();
    for (let j = 0; j < edge_count; j++) {
      successors[nextSuccessorIndex] = stream.uleb128();
      successorName[nextSuccessorIndex] = unknownEdge;
      const edgeNames = classEdges[cid];
      if (edgeNames !== undefined) {
        const edgeName = classEdges[cid][j];
        if (edgeName !== undefined) {
          successorName[nextSuccessorIndex] = edgeName;
        }
      }
      nextSuccessorIndex++;
    }
  }
  firstSuccessor[N + 1] = nextSuccessorIndex;

  if (nextSuccessorIndex != E) {
    throw "Incorrect edge_count!";
  }

  const externalPropertyCount = stream.uleb128();
  for (let i = 0; i < externalPropertyCount; i++) {
    let object = stream.uleb128();
    let externalSize = stream.uleb128();
    stream.utf8();  // Name.
    shallowSize[object] += externalSize;
    shallowSizeSum += externalSize;
  }

  this.N_ = N;
  this.E_ = E;
  this.strings_ = strings;
  this.firstSuccessor_ = firstSuccessor;
  this.successorName_ = successorName;
  this.successors_ = successors;
  this.name_ = name;
  this.class_ = clazz;
  this.shallowSize_ = shallowSize;
  this.shallowSizeSum_ = shallowSizeSum;
};

// Compute the graph's dominator tree and the retained size of each vertex.
//
// If `rewriteForOwners` is true, for each vertex that has an "owner" edge,
// replace all edges to the vertex with an edge from the owner to the vertex.
// This can be the graph more hierarchical and reveal more structure in the
// dominator tree.
Graph.prototype.compute = function(rewriteForOwners) {
  this.computePredecessors();
  if (rewriteForOwners) {
    this.rewriteEdgesForOwners();
  }
  this.computePreorder(1);
  this.computeDominators();
  this.computeOwnedSizes();
  this.computeRetainedSizes();
  this.linkDominatorChildren();
  this.sortDominatorChildren();
  this.mergeDominatorSiblings(1);
};

Graph.prototype.computePredecessors = function() {
  console.log("Building predecessors...");

  const N = this.N_;
  const E = this.E_;
  const firstSuccessor = this.firstSuccessor_;
  const successors = this.successors_;
  const successorName = this.successorName_;
  const firstPredecessor = new Uint32Array(N + 2);
  const predecessors = new Uint32Array(E);
  const predecessorName = new Uint32Array(E);

  const predecessorCount = new Uint32Array(N + 1);
  for (let i = 1; i <= N; i++) {
    let startSuccessorIndex = firstSuccessor[i];
    let limitSuccessorIndex = firstSuccessor[i + 1];
    for (let successorIndex = startSuccessorIndex;
       successorIndex < limitSuccessorIndex;
       successorIndex++) {
      let successor = successors[successorIndex];
      if (successor == 0) continue;  // Omitted object.
      predecessorCount[successor]++;
    }
  }

  let nextPredecessorIndex = 0;
  for (let i = 1; i <= N; i++) {
    firstPredecessor[i] = nextPredecessorIndex;
    nextPredecessorIndex += predecessorCount[i];
  }
  firstPredecessor[N + 1] = nextPredecessorIndex;

  for (let i = 1; i <= N; i++) {
    let startSuccessorIndex = firstSuccessor[i];
    let limitSuccessorIndex = firstSuccessor[i + 1];
    for (let successorIndex = startSuccessorIndex;
       successorIndex < limitSuccessorIndex;
       successorIndex++) {
      let successor = successors[successorIndex];
      if (successor == 0) continue;  // Omitted object.
      let count = --predecessorCount[successor];
      let predecessorIndex = firstPredecessor[successor] + count;
      predecessors[predecessorIndex] = i;
      predecessorName[predecessorIndex] = successorName[successorIndex];
    }
  }

  this.firstPredecessor_ = firstPredecessor;
  this.predecessors_ = predecessors;
  this.predecessorName_ = predecessorName;
};

Graph.prototype.rewriteEdgesForOwners = function() {
  console.log("Rewriting edges for owners...");

  // Rewrite some edges to make the graph more hierarchical.
  // If there is an edge A.owner -> B,
  //   - remove all edges to A, and
  //   - add edge B.<unnamed> -> A.

  const N = this.N_;
  const E = this.E_;
  const firstSuccessor = this.firstSuccessor_;
  const successors = this.successors_;
  const successorName = this.successorName_;
  const firstPredecessor = this.firstPredecessor_;
  const predecessors = this.predecessors_;
  const predecessorName = this.predecessorName_;
  const owners = new Uint32Array(N + 1);
  const owneeCount = new Uint32Array(N + 1);

  // Identify owner.
  for (let i = 1; i <= N; i++) {
    let cls = this.class_[i];
    let ownerEdgeName;

    if (cls == "Class") {  // Dart VM
      ownerEdgeName = "library_";
    } else if (cls == "PatchClass") {  // Dart VM
      ownerEdgeName = "patched_class_";
    } else if (cls == "Function") {  // Dart VM
      ownerEdgeName = "owner_";
    } else if (cls == "Field") {  // Dart VM
      ownerEdgeName = "owner_";
    } else if (cls == "Code") {  // Dart VM
      ownerEdgeName = "owner_";
    } else if (cls == "ICData") {  // Dart VM
      ownerEdgeName = "owner_";
    } else if (cls == "Method") {  // Primordial Soup
      ownerEdgeName = "mixin";
    } else if (cls.startsWith("InstanceMixin`")) {  // Primordial Soup
      ownerEdgeName = "_enclosingMixin";
    } else if (cls.startsWith("ClassMixin`")) {  // Primordial Soup
      ownerEdgeName = "_instanceMixin";
    } else {
      continue;
    }

    let startSuccessorIndex = firstSuccessor[i];
    let limitSuccessorIndex = firstSuccessor[i + 1];
    for (let successorIndex = startSuccessorIndex;
         successorIndex < limitSuccessorIndex;
         successorIndex++) {
      let edge = this.strings_[this.successorName_[successorIndex]];
      if (edge == ownerEdgeName) {
        let owner = successors[successorIndex];
        owners[i] = owner;
        owneeCount[owner]++;
        break;
      }
    }
  }

  // Remove successors if the target has an owner.
  // Allocate space for extra successors added to owners.
  const newSuccessors = new Uint32Array(E);
  const newSuccessorName = new Uint32Array(E);
  let newSuccessorIndex = 0;
  for (let i = 1; i <= N; i++) {
    let startSuccessorIndex = firstSuccessor[i];
    let limitSuccessorIndex = firstSuccessor[i + 1];
    firstSuccessor[i] = newSuccessorIndex;
    for (let successorIndex = startSuccessorIndex;
         successorIndex < limitSuccessorIndex;
         successorIndex++) {
      let successor = successors[successorIndex];
      let name = successorName[successorIndex];

      if (owners[successor] != 0) {
        // Drop successor.
      } else {
        newSuccessors[newSuccessorIndex] = successor;
        newSuccessorName[newSuccessorIndex] = name;
        newSuccessorIndex++;
      }
    }
    newSuccessorIndex += owneeCount[i];
  }
  firstSuccessor[N + 1] = newSuccessorIndex;

  // Remove predecessors if the target has an owner.
  // Add the owner as a predecessor.
  // Add extra successors for owner.
  for (let i = 1; i <= N; i++) {
    let owner = owners[i];
    if (owner == 0) {
      continue;
    }

    let startPredecessorIndex = firstPredecessor[i];
    let limitPredecessorIndex = firstPredecessor[i + 1];
    for (let predecessorIndex = startPredecessorIndex;
         predecessorIndex < limitPredecessorIndex;
         predecessorIndex++) {
      predecessors[predecessorIndex] = 0;
    }
    predecessors[startPredecessorIndex] = owner;

    let nextSuccessorIndex = firstSuccessor[owner + 1] - owneeCount[owner];
    newSuccessors[nextSuccessorIndex] = i;
    owneeCount[owner]--;
  }

  this.successors_ = newSuccessors;
  this.successorName_ = newSuccessorName;
};

// Thomas Lengauer and Robert Endre Tarjan. 1979. A fast algorithm for finding
// dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1, 1 (January
// 1979), 121-141. DOI: https://doi.org/10.1145/357062.357071

Graph.prototype.computePreorder = function(root) {
  console.log("Computing preorder...");

  // Lengauer and Tarjan Step 1.
  const N = this.N_;
  const firstSuccessor = this.firstSuccessor_;
  const successors = this.successors_;

  const semi = new Uint32Array(N + 1);
  const vertex = new Uint32Array(N + 1);
  const ancestor = new Uint32Array(N + 1);
  const parent = new Uint32Array(N + 1);
  const label = new Uint32Array(N + 1);

  let preorderNumber = 0;

  let stackNodes = new Uint32Array(N + 1);
  let stackEdges = new Uint32Array(N + 1);
  let stackTop = 0;

  // Push root.
  preorderNumber++;
  vertex[preorderNumber] = root;
  semi[root] = preorderNumber;
  label[root] = root;
  ancestor[root] = 0;
  stackNodes[stackTop] = root;
  stackEdges[stackTop] = firstSuccessor[root];

  while (stackTop >= 0) {
    let v = stackNodes[stackTop];
    let e = stackEdges[stackTop];

    if (e < firstSuccessor[v + 1]) {
      // Visit next successor.
      let w = successors[e];
      e++;
      stackEdges[stackTop] = e;

      if (w == 0) {
        // Omitted object.
      } else if (semi[w] != 0) {
        // Already visited.
      } else {
        parent[w] = v;

        preorderNumber++;
        vertex[preorderNumber] = w;
        semi[w] = preorderNumber;
        label[w] = w;
        ancestor[w] = 0;

        // Push successor.
        stackTop++;
        stackNodes[stackTop] = w;
        stackEdges[stackTop] = firstSuccessor[w];
      }
    } else {
      // No more successors: pop.
      stackTop--;
    }
  }

  this.Nconnected_ = preorderNumber;
  if (this.Nconnected_ != N) {
    console.log("Graph is not fully connected: " + this.Nconnected_ +
          " nodes are reachable, but graph has " + this.N_ + " nodes");
  }

  this.semi_ = semi;
  this.vertex_ = vertex;
  this.ancestor_ = ancestor;
  this.parent_ = parent;
  this.label_ = label;
};

Graph.prototype.computeDominators = function() {
  console.log("Computing dominator tree...");

  const N = this.N_;
  const Nconnected = this.Nconnected_;
  const firstPredecessor = this.firstPredecessor_;
  const predecessors = this.predecessors_;
  const vertex = this.vertex_;
  const semi = this.semi_;
  const bucket = new Array(N + 1);
  const parent = this.parent_;
  const dom = new Uint32Array(N + 1);
  const stackNode = new Uint32Array(N + 1);
  const stackState = new Uint8Array(N + 1);

  for (let i = Nconnected; i > 1; i--) {
    let w = vertex[i];

    // Lengauer and Tarjan Step 2.
    let startPredecessorIndex = firstPredecessor[w];
    let limitPredecessorIndex = firstPredecessor[w + 1];
    for (let predecessorIndex = startPredecessorIndex;
         predecessorIndex < limitPredecessorIndex;
         predecessorIndex++) {
      let v = predecessors[predecessorIndex];

      if (semi[v] == 0) {
        // The predecessor was not reachable from the root: ignore
        // this edge.
        continue;
      }

      let u = this.forestEval(v, stackNode, stackState);
      if (semi[u] < semi[w]) {
        semi[w] = semi[u]
      }
    }

    let z = vertex[semi[w]];
    let b = bucket[z];
    if (b == null) {
      b = new Array();
      bucket[z] = b;
    }
    b.push(w);
    this.forestLink(parent[w], w);

    // Lengauer and Tarjan Step 3.
    z = parent[w];
    b = bucket[z];
    bucket[z] = null;
    if (b != null) {
      for (let j = 0; j < b.length; j++) {
        let v = b[j];
        let u = this.forestEval(v, stackNode, stackState);
        dom[v] = semi[u] < semi[v] ? u : parent[w];
      }
    }
  }

  this.ancestor_ = null;
  this.label_ = null;
  this.parent_ = null;
  this.bucket_ = null;

  // Lengauer and Tarjan Step 4.
  for (let i = 2; i <= Nconnected; i++) {
    let w = vertex[i];
    if (dom[w] != vertex[semi[w]]) {
      dom[w] = dom[dom[w]];
    }
  }
  dom[vertex[1]] = 0;

  this.semi_ = null;
  this.dom_ = dom;
};

Graph.prototype.forestEval = function(v, stackNode, stackState) {
  if (this.ancestor_[v] == 0) {
    return v;
  } else {
    const ancestor = this.ancestor_;
    const semi = this.semi_;
    const label = this.label_;
    {
      // Inlined 'compress' with an explicit stack to prevent JS stack
      // overflow.
      let top = 0;
      stackNode[top] = v;
      stackState[top] = 0;
      while (top >= 0) {
        let v = stackNode[top];
        let state = stackState[top];
        if (state == 0) {
          if (ancestor[ancestor[v]] != 0) {
            stackState[top] = 1;
            // Recurse with ancestor[v]
            top++;
            stackNode[top] = ancestor[v];
            stackState[top] = 0;
          } else {
            top--;
          }
        } else {
          if (semi[label[ancestor[v]]] < semi[label[v]]) {
            label[v] = label[ancestor[v]];
          }
          ancestor[v] = ancestor[ancestor[v]];
          top--;
        }
      }
    }

    if (semi[label[ancestor[v]]] >= semi[label[v]]) {
      return label[v];
    } else {
      return label[ancestor[v]];
    }
  }
};

Graph.prototype.forestLink = function(v, w) {
  this.ancestor_[w] = v;
};

Graph.prototype.computeOwnedSizes = function() {
  console.log("Computing in-degree(1) groups...");

  const N = this.N_;
  const E = this.E_;
  const Nconnected = this.Nconnected_;
  const shallowSize = this.shallowSize_;
  const vertex = this.vertex_;
  const successors = this.successors_;
  const firstSuccessor = this.firstSuccessor_;
  const predecessors = this.predecessors_;
  const firstPredecessor = this.firstPredecessor_;
  const SENTINEL = 0;
  const ROOT = vertex[1];
  const ownedSize = new Uint32Array(N + 1);
  const successorsOwnedSize = new Uint32Array(E + 1);

  for (let i = 0; i <= N; i++) {
    ownedSize[i] = shallowSize[i];
  }

  for (let i = Nconnected; i > 1; i--) {
    const w = vertex[i];

    let onlyPred = SENTINEL;
    const startPred = firstPredecessor[w];
    const limitPred = firstPredecessor[w + 1];
    for (let predIndex = startPred; predIndex < limitPred; predIndex++) {
      const v = predecessors[predIndex];
      if (v == w) {
        // Ignore self-predecessor.
      } else if (onlyPred == SENTINEL) {
        onlyPred = v;
      } else if (onlyPred == v) {
        // Repeated predecessor.
      } else {
        // Multiple predecessors.
        onlyPred = SENTINEL;
        break;
      }
    }

    if ((onlyPred != SENTINEL) && (onlyPred != ROOT)) {
      let size = ownedSize[w];
      ownedSize[w] = 0;
      ownedSize[onlyPred] += size;

      const startSucc = firstSuccessor[onlyPred];
      const limitSucc = firstSuccessor[onlyPred + 1];
      for (let succIndex = startSucc; succIndex < limitSucc; succIndex++) {
        if (successors[succIndex] == w) {
          successorsOwnedSize[succIndex] = size;
        }
      }
    }
  }

  this.ownedSize_ = ownedSize;
  this.successorsOwnedSize_ = successorsOwnedSize;
};

Graph.prototype.computeRetainedSizes = function() {
  console.log("Computing retained sizes...");

  const N = this.N_;
  const Nconnected = this.Nconnected_;
  const vertex = this.vertex_;
  const dom = this.dom_;
  const shallowSize = this.shallowSize_;
  const retainedSize = new Uint32Array(N + 1);

  let shallowSum = 0;

  for (let i = 1; i <= Nconnected; i++) {
    let w = vertex[i];
    let shallow = shallowSize[w];
    retainedSize[w] = shallow;
    shallowSum += shallow;
  }

  for (let i = Nconnected; i > 1; i--) {
    let w = vertex[i];
    retainedSize[dom[w]] += retainedSize[w];
  }

  if (retainedSize[vertex[1]] != shallowSum) {
    console.log("Retained size mismatch: root retains " + retainedSize[vertex[1]] +
                " but shallow sizes sum to " + shallowSum);
  }

  this.retainedSize_ = retainedSize;
};

Graph.prototype.linkDominatorChildren = function() {
  console.log("Linking dominator tree children...");

  const N = this.N_;
  const Nconnected = this.Nconnected_;

  const vertex = this.vertex_;
  const dom = this.dom_;
  const head = new Uint32Array(N + 1);
  const next = new Uint32Array(N + 1);

  for (let i = 2; i <= Nconnected; i++) {
    let child = vertex[i];
    let parent = dom[child];
    next[child] = head[parent];
    head[parent] = child;
  }

  this.domHead_ = head;
  this.domNext_ = next;
};

// Merge the given lists according to the given key in ascending order.
// Returns the head of the merged list.
function mergeSorted(head1, head2, next, key) {
  let head = head1;
  let beforeInsert = 0;
  let afterInsert = head1;
  let startInsert = head2;

  while (startInsert != 0) {
    while ((afterInsert != 0) &&
           (key[afterInsert] <= key[startInsert])) {
      beforeInsert = afterInsert;
      afterInsert = next[beforeInsert];
    }
    let endInsert = startInsert;
    let peek = next[endInsert];

    while ((peek != 0) && (key[peek] < key[afterInsert])) {
      endInsert = peek;
      peek = next[endInsert];
    }

    if (beforeInsert == 0) {
      head = startInsert;
    } else {
      next[beforeInsert] = startInsert;
    }
    next[endInsert] = afterInsert;

    startInsert = peek;
    beforeInsert = endInsert;
  }

  return head;
}

Graph.prototype.sortDominatorChildren = function() {
  console.log("Sorting dominator tree children...");

  const N = this.N_;
  const Nconnected = this.Nconnected_;
  const cids = this.class_;
  const head = this.domHead_;
  const next = this.domNext_;

  function sort(head) {
    if (head == 0) return 0;
    if (next[head] == 0) return head;

    // Find the middle of the list.
    let head1 = head;
    let slow = head;
    let fast = head;
    while (next[fast] != 0 && next[next[fast]] != 0) {
      slow = next[slow];
      fast = next[next[fast]];
    }

    // Split the list in half.
    let head2 = next[slow];
    next[slow] = 0;

    // Recursively sort the sublists and merge.
    let newHead1 = sort(head1);
    let newHead2 = sort(head2);
    return mergeSorted(newHead1, newHead2, next, cids);
  };

  // Sort all list of dominator tree children by cid.
  for (let parent = 1; parent <= N; parent++) {
    head[parent] = sort(head[parent]);
  }
};

Graph.prototype.mergeDominatorSiblings = function(root) {
  console.log("Merging dominator tree siblings...");

  const N = this.N_;
  const cids = this.class_;
  const head = new Uint32Array(this.domHead_);
  const next = new Uint32Array(this.domNext_);
  const workStack = new Uint32Array(N);
  let workStackTop = 0;

  function mergeChildrenAndSort(parent1, end) {
    if (next[parent1] == end) return;

    // Find the middle of the list.
    let slow = parent1;
    let fast = parent1;
    while (next[fast] != end && next[next[fast]] != end) {
      slow = next[slow];
      fast = next[next[fast]];
    }

    let parent2 = next[slow];

    // Recursively sort the sublists.
    mergeChildrenAndSort(parent1, parent2);
    mergeChildrenAndSort(parent2, end);

    // Merge sorted sublists.
    head[parent1] = mergeSorted(head[parent1], head[parent2], next, cids);

    // Children moved to parent1.
    head[parent2] = 0;
  }

  // Push root.
  workStack[workStackTop++] = root;

  while (workStackTop > 0) {
    let parent = workStack[--workStackTop];

    let child = head[parent];
    while (child != 0) {
      // Push child.
      workStack[workStackTop++] = child;

      // Find next sibling with a different cid.
      let after = child;
      while (after != 0 && cids[after] == cids[child]) {
        after = next[after];
      }

      // From all the siblings between child and after, take their children,
      // merge them and given to child.
      mergeChildrenAndSort(child, after);

      child = after;
    }
  }

  this.mergedDomHead_ = head;
  this.mergedDomNext_ = next;
};

Graph.prototype.getTotalSize = function() {
  return this.shallowSizeSum_;
};

Graph.prototype.getRoot = function() {
  return this.vertex_[1];
};

Graph.prototype.getAll = function() {
  let nodes = new Array();
  for (let v = 1; v <= this.N_; v++) {
    nodes.push(v);
  }
  return nodes;
};

function removeDuplicates(array) {
  let set = new Set(array);
  let result = new Array();
  for (let element of set) {
    result.push(element);
  }
  return result
}

Graph.prototype.successorsOfDo = function(v, action) {
  let cls = this.class_[v];
  let startSuccessorIndex = this.firstSuccessor_[v];
  let limitSuccessorIndex = this.firstSuccessor_[v + 1];
  for (let successorIndex = startSuccessorIndex;
     successorIndex < limitSuccessorIndex;
     successorIndex++) {
    let successor = this.successors_[successorIndex];
    let edgeName = this.strings_[this.successorName_[successorIndex]];
    let edgeOwnedSize = this.successorsOwnedSize_[successorIndex];
    action(successor, cls + "::" + edgeName, edgeOwnedSize);
  }
}

Graph.prototype.predecessorsOfDo = function(v, action) {
  let startPredecessorIndex = this.firstPredecessor_[v];
  let limitPredecessorIndex = this.firstPredecessor_[v + 1];
  for (let predecessorIndex = startPredecessorIndex;
     predecessorIndex < limitPredecessorIndex;
     predecessorIndex++) {
    let predecessor = this.predecessors_[predecessorIndex];
    let cls = this.class_[predecessor];
    let edgeName = this.strings_[this.predecessorName_[predecessorIndex]];
    action(predecessor, cls + "::" + edgeName);
  }
}

Graph.prototype.parentOf = function(v) {
  return this.dom_[v];
};

Graph.prototype.dominatorChildrenOfDo = function(v, action) {
  for (let w = this.domHead_[v]; w != 0; w = this.domNext_[w]) {
    action(w);
  }
};

Graph.prototype.nameOf = function(v) {
  return this.strings_[this.name_[v]];
};

Graph.prototype.classOf = function(v) {
  return this.class_[v];
};

Graph.prototype.shallowSizeOf = function(v) {
  return this.shallowSize_[v];
};

Graph.prototype.retainedSizeOf = function(v) {
  return this.retainedSize_[v];
};

Graph.prototype.setFrom = function(v) {
  return [v];
};

Graph.prototype.shallowSizeOfSet = function(nodes) {
  let sum = 0;
  for (let i = 0; i < nodes.length; i++) {
    sum += this.shallowSize_[nodes[i]];
  }
  return sum;
};

Graph.prototype.ownedSizeOfSet = function(nodes) {
  const ownedSize = this.ownedSize_;
  let sum = 0;
  for (let i = 0; i < nodes.length; i++) {
    let v = nodes[i];
    sum += ownedSize[v];
  }
  return sum;
};

Graph.prototype.toggleMerge = function() {
  return new MergedGraph(this);
};

function MergedGraph(graph) {
  this.graph_ = graph;
}

MergedGraph.prototype.nameOf = function(v) {
  const cids = this.graph_.class_;
  const next = this.graph_.mergedDomNext_;
  let count = 0;
  let sibling = v;
  while (sibling != 0 && cids[sibling] == cids[v]) {
    count++;
    sibling = next[sibling];
  }
  return count.toString() + " instances of " + this.graph_.class_[v];
};

MergedGraph.prototype.classOf = function(v) {
  return this.graph_.class_[v];
};

MergedGraph.prototype.shallowSizeOf = function(v) {
  const cids = this.graph_.class_;
  const shallowSize = this.graph_.shallowSize_;
  const next = this.graph_.mergedDomNext_;
  let size = 0;
  let sibling = v;
  while (sibling != 0 && cids[sibling] == cids[v]) {
    size += shallowSize[sibling];
    sibling = next[sibling];
  }
  return size;
};

MergedGraph.prototype.retainedSizeOf = function(v) {
  const cids = this.graph_.class_;
  const retainedSize = this.graph_.retainedSize_;
  const next = this.graph_.mergedDomNext_;
  let size = 0;
  let sibling = v;
  while (sibling != 0 && cids[sibling] == cids[v]) {
    size += retainedSize[sibling];
    sibling = next[sibling];
  }
  return size;
};

MergedGraph.prototype.setFrom = function(v) {
  const cids = this.graph_.class_;
  const next = this.graph_.mergedDomNext_;
  let set = new Array();
  let sibling = v;
  while (sibling != 0 && cids[sibling] == cids[v]) {
    set.push(sibling);
    sibling = next[sibling];
  }
  return set;
};

MergedGraph.prototype.parentOf = function(v) {
  // N.B.: Not dom_[v], which might not be the representative element of the
  // merged group.
  const N = this.graph_.N_;
  const head = this.graph_.mergedDomHead_;
  const next = this.graph_.mergedDomNext_;
  for (let parent = 1; parent <= N; parent++) {
    for (let child = head[parent]; child != 0; child = next[child]) {
      if (child == v) {
        return parent;
      }
    }
  }
  return 0;
};

MergedGraph.prototype.dominatorChildrenOfDo = function(v, action) {
  const next = this.graph_.mergedDomNext_;
  const cids = this.graph_.class_;
  let prev = 0;
  let child = this.graph_.mergedDomHead_[v];
  // Walk the list of children and look for the representative objects, i.e.
  // the first sibling of each cid.
  while (child != 0) {
    if (prev == 0 || cids[prev] != cids[child]) {
      action(child);
    }
    prev = child;
    child = next[child];
  }
};

MergedGraph.prototype.getTotalSize = function() {
  return this.graph_.shallowSizeSum_;
};

MergedGraph.prototype.toggleMerge = function() {
  return this.graph_;
};

function Stream(bytes) {
  this.bytes_ = new Uint8Array(bytes);
  this.position_ = 0;
}

Stream.prototype.byte = function() {
  const position = this.position_;
  const bytes = this.bytes_;
  if ((position >= 0) && (position < bytes.length)) {
    const result = bytes[position];
    this.position_ = position + 1;
    return result;
  }
  throw "Attempt to read past end of stream";
};

Stream.prototype.uleb128 = function() {
  let result = 0;
  let shift = 0;
  for (;;) {
    const part = this.byte();
    result |= (part & 0x7F) << shift;
    if ((part & 0x80) == 0) {
      break;
    }
    shift += 7;
  }
  return result;
};

Stream.prototype.sleb128 = function() {
  let result = 0;
  let shift = 0;
  for (;;) {
    const part = this.byte();
    result |= (part & 0x7F) << shift;
    shift += 7;
    if ((part & 0x80) == 0) {
      if ((part & 0x40) != 0) {
        result |= (-1 << shift);
      }
      break;
    }
  }
  return result;
};

Stream.prototype.float64 = function() {
  const buffer = new ArrayBuffer(8);
  const bytes = new Uint8Array(buffer);
  for (let i = 0; i < 8; i++) {
    bytes[i] = this.byte();
  }
  return new Float64Array(buffer)[0];
};

Stream.prototype.utf8 = function() {
  const length = this.uleb128();
  let result = '';
  for (let i = 0; i < length; i++) {
    // This is incorrect outside of ASCII, but good enough for our purpose
    // since we're mostly interested in identifiers.
    result += String.fromCharCode(this.byte());
  }
  // Can we force flattening of the rope string?
  return result.toString();
};

Stream.prototype.latin1 = function() {
  const length = this.uleb128();
  let result = '';
  for (let i = 0; i < length; i++) {
    result += String.fromCharCode(this.byte());
  }
  // Can we force flattening of the rope string?
  return result.toString();
};

Stream.prototype.utf16 = function() {
  const length = this.uleb128();
  let result = '';
  for (let i = 0; i < length; i++) {
    const lo = this.byte();
    const hi = this.byte();
    result += String.fromCharCode((hi << 8) | lo);
  }
  // Can we force flattening of the rope string?
  return result.toString();
};

function hash(string) {
  // Jenkin's one_at_a_time.
  let h = string.length;
  for (let i = 0; i < string.length; i++) {
    h += string.charCodeAt(i);
    h += h << 10;
    h ^= h >> 6;
  }
  h += h << 3;
  h ^= h >> 11;
  h += h << 15;
  return h;
}

function color(string) {
  let hue = hash(string) % 360;
  return "hsl(" + hue + ",60%,60%)";
}

function prettySize(size) {
  if (size < 1024) return size + "B";
  size /= 1024;
  if (size < 1024) return size.toFixed(1) + "KiB";
  size /= 1024;
  if (size < 1024) return size.toFixed(1) + "MiB";
  size /= 1024;
  return size.toFixed(1) + "GiB";
}

function prettyPercent(fraction) {
  return (fraction * 100).toFixed(1);
}

function createTreemapTile(graph, v, width, height, depth) {
  let div = document.createElement("div");
  div.className = "treemapTile";
  div.style["background-color"] = color(graph.classOf(v));
  div.ondblclick = function(event) {
    event.stopPropagation();
    if (depth == 0) {
      let dom = graph.parentOf(v);
      if (dom == 0) {
        // Already at root.
      } else {
        showDominatorTree(graph, dom);  // Zoom out.
      }
    } else {
      showDominatorTree(graph, v);  // Zoom in.
    }
  };
  div.oncontextmenu = function(event) {
    event.stopPropagation();
    event.preventDefault();
    showTables(graph.setFrom(v));
  };

  let left = 0;
  let top = 0;

  const kPadding = 5;
  const kBorder = 1;
  left += kPadding - kBorder;
  top += kPadding - kBorder;
  width -= 2 * kPadding;
  height -= 2 * kPadding;

  div.title =
    graph.nameOf(v) +
    " \nclass: " + graph.classOf(v) +
    " \nretained: " + graph.retainedSizeOf(v) +
    " \nshallow: " + graph.shallowSizeOf(v);

  if (width < 10 || height < 10) {
    // Too small: don't render label or children.
    return div;
  }

  let label = graph.nameOf(v) + " [" + prettySize(graph.retainedSizeOf(v)) + "]";
  div.appendChild(document.createTextNode(label));
  const kLabelHeight = 9;
  top += kLabelHeight;
  height -= kLabelHeight;

  if (depth > 2) {
    // Too deep: don't render children.
    return div;
  }
  if (width < 4 || height < 4) {
    // Too small: don't render children.
    return div;
  }

  let children = new Array();
  graph.dominatorChildrenOfDo(v, function(c) {
    // Size 0 children seem to confuse the layout algorithm (accumulating
    // rounding errors?).
    if (graph.retainedSizeOf(c) > 0) {
      children.push(c);
    }
  });
  children.sort(function (a, b) {
    return graph.retainedSizeOf(b) - graph.retainedSizeOf(a);
  });

  const scale = width * height / graph.retainedSizeOf(v);

  // Bruls M., Huizing K., van Wijk J.J. (2000) Squarified Treemaps. In: de
  // Leeuw W.C., van Liere R. (eds) Data Visualization 2000. Eurographics.
  // Springer, Vienna.
  for (let rowStart = 0;  // Index of first child in the next row.
       rowStart < children.length;) {
    // Prefer wider rectangles, the better to fit text labels.
    const GOLDEN_RATIO = 1.61803398875;
    let verticalSplit = (width / height) > GOLDEN_RATIO;

    let space;
    if (verticalSplit) {
      space = height;
    } else {
      space = width;
    }

    let rowMin = graph.retainedSizeOf(children[rowStart]) * scale;
    let rowMax = rowMin;
    let rowSum = 0;
    let lastRatio = 0;

    let rowEnd;  // One after index of last child in the next row.
    for (rowEnd = rowStart; rowEnd < children.length; rowEnd++) {
      let size = graph.retainedSizeOf(children[rowEnd]) * scale;
      if (size < rowMin) rowMin = size;
      if (size > rowMax) rowMax = size;
      rowSum += size;

      let ratio = Math.max((space * space * rowMax) / (rowSum * rowSum),
                           (rowSum * rowSum) / (space * space * rowMin));
      if ((lastRatio != 0) && (ratio > lastRatio)) {
        // Adding the next child makes the aspect ratios worse: remove it and
        // add the row.
        rowSum -= size;
        break;
      }
      lastRatio = ratio;
    }

    let rowLeft = left;
    let rowTop = top;
    let rowSpace = rowSum / space;

    for (let i = rowStart; i < rowEnd; i++) {
      let child = children[i];
      let size = graph.retainedSizeOf(child) * scale;

      let childWidth;
      let childHeight;
      if (verticalSplit) {
        childWidth = rowSpace;
        childHeight = size / childWidth;
      } else {
        childHeight = rowSpace;
        childWidth = size / childHeight;
      }

      let childDiv = createTreemapTile(graph, child, childWidth, childHeight, depth + 1);
      childDiv.style.left = rowLeft + "px";
      childDiv.style.top = rowTop + "px";
      // Oversize the final div by kBorder to make the borders overlap.
      childDiv.style.width = (childWidth + kBorder) + "px";
      childDiv.style.height = (childHeight + kBorder) + "px";
      div.appendChild(childDiv);

      if (verticalSplit)
        rowTop += childHeight;
      else
        rowLeft += childWidth;
    }

    if (verticalSplit) {
      left += rowSpace;
      width -= rowSpace;
    } else {
      top += rowSpace;
      height -= rowSpace;
    }

    rowStart = rowEnd;
  }

  return div;
}

function showDominatorTree(graph, v) {
  let title = document.createElement("span");
  title.textContent = "Dominator Tree";
  title.title =
    "Click title to merge/unmerge by class.\n" +
    "Double click a box to zoom in.\n" +
    "Double click the outermost box to zoom out.\n" +
    "Right click a box to view successor and predecessor tables.";
  title.className = "nameCell actionCell";
  title.onclick = function(event) { showDominatorTree(graph.toggleMerge(), v); };

  let filler = document.createElement("span");
  filler.style["flex-grow"] = 1;

  let totalSize = document.createElement("span");
  totalSize.className = "sizeCell";
  totalSize.textContent = graph ? "" + graph.getTotalSize() : "0";

  let totalPercent = document.createElement("span");
  totalPercent.className = "sizePercentCell";
  totalPercent.textContent = prettyPercent(1.0);

  let header = document.createElement("div");
  header.className = "headerRow";
  header.style["border-bottom"] = "solid 1px";
  header.appendChild(title);
  header.appendChild(filler);
  header.appendChild(totalSize);
  header.appendChild(totalPercent);

  let content = document.createElement("div");
  content.style["flex-basis"] = 0;
  content.style["flex-grow"] = 1;

  let column = document.createElement("div");
  column.style["width"] = "100%";
  column.style["height"] = "100%";
  column.style["border"] = "solid 2px";
  column.style["display"] = "flex";
  column.style["flex-direction"] = "column";
  column.appendChild(header);
  column.appendChild(content);

  setBody(column);

  // Add the content div to the document first so the browser will calculate
  // the available width and height.
  let w = content.offsetWidth;
  let h = content.offsetHeight;

  let topTile = createTreemapTile(graph, v, w, h, 0);
  topTile.style.width = w;
  topTile.style.height = h;
  topTile.style.border = "none";
  content.appendChild(topTile);
}

function Group(edge, cls) {
  this.name = "";
  this.edge = edge;
  this.cls = cls;
  this.shallowSize = 0;
  this.ownedSize = 0;
  this.nodes = new Array();
}

Group.prototype.add = function(v, edge, cls) {
  this.nodes.push(v);
  if (this.edge != edge) {
    this.edge = "<multiple>";
  }
  if (this.cls != cls) {
    this.cls = "<multiple>"
  }
};

function asGroupsByClass(labeledNodes) {
  let map = new Map();
  let groups = new Array();
  for (let i = 0; i < labeledNodes.length; i++) {
    let v = labeledNodes[i].node;
    let edge = labeledNodes[i].name;
    let cls = graph.classOf(v);
    let group = map.get(cls);
    if (group === undefined) {
      group = new Group(edge, cls);
      groups.push(group);
      map.set(cls, group);
    }
    group.add(v, edge, cls);
  }
  for (let i = 0; i < groups.length; i++) {
    let group = groups[i];
    group.shallowSize = graph.shallowSizeOfSet(group.nodes);
    group.ownedSize = graph.ownedSizeOfSet(group.nodes);
    group.name = group.nodes.length + " instances of " + group.cls;
  }
  return groups;
}

function LabeledNode(node, name) {
  this.node = node;
  this.name = name;
}

LabeledNode.prototype.addName = function(name) {
  if (this.name != name) {
    this.name = "<multiple>";
  }
};

function Table(title, labeledNodes, byEdges) {
  const self = this;

  this.title = title;
  this.labeledNodes = labeledNodes;
  this.groupsByEdge = byEdges;
  this.groupsByClass = asGroupsByClass(labeledNodes);
  this.grouping = 0;

  this.nom = document.createElement("span");
  this.nom.onclick = function() {
    self.grouping = (self.grouping + 1) % 3;
    self.refreshRows();
  };
  this.nom.className = "nameCell actionCell"
  this.nom.textContent = title;
  this.nom.title = "Toggle grouping by object, class or edge";

  let edge = document.createElement("span");
  edge.onclick = function() { self.sortByEdge(); };
  edge.className = "edgeCell actionCell";
  edge.textContent = "Edge";
  edge.title = "Sort by edge";

  let cls = document.createElement("span");
  cls.onclick = function() { self.sortByClass(); };
  cls.className = "classCell actionCell";
  cls.textContent = "Class";
  cls.title = "Sort by class";

  let shallowSize = document.createElement("span");
  shallowSize.onclick = function() { self.sortByShallowSize(); };
  shallowSize.className = "sizeCell actionCell";
  shallowSize.textContent = "Size";
  shallowSize.title = "Sort by shallow size";

  let shallowPercent = document.createElement("span");
  shallowPercent.className = "sizePercentCell"

  this.retainedSize = document.createElement("span");
  this.retainedSize.onclick = function() { self.sortByRetainedSize(); };
  this.retainedSize.className = "sizeCell actionCell";

  let retainedPercent = document.createElement("span");
  retainedPercent.className = "sizePercentCell";

  let header = document.createElement("div");
  header.className = "headerRow";
  header.style["border-bottom"] = "solid 1px";
  header.appendChild(this.nom);
  header.appendChild(edge);
  header.appendChild(cls);
  header.appendChild(shallowSize);
  header.appendChild(shallowPercent);
  header.appendChild(this.retainedSize);
  header.appendChild(retainedPercent);

  this.listDiv = document.createElement("div");
  this.listDiv.style["overflow-y"] = "scroll";
  this.listDiv.style["flex-basis"] = "0px";
  this.listDiv.style["flex-grow"] = 1;

  this.div = document.createElement("div");
  this.div.style["border"] = "solid 2px";
  this.div.style["display"] = "flex";
  this.div.style["flex-direction"] = "column";
  this.div.style["background-color"] = "#DDDDDD";

  this.div.appendChild(header);
  this.div.appendChild(this.listDiv);

  this.refreshRows();
}

Table.prototype.sortByEdge = function() {
  this.labeledNodes.sort(function (a, b) {
    return a.name.localeCompare(b.name);
  });
  this.groupsByEdge.sort(function (a, b) {
    return a.edge.localeCompare(b.edge);
  });
  this.groupsByClass.sort(function (a, b) {
    return a.edge.localeCompare(b.edge);
  });
  this.refreshRows();
};

Table.prototype.sortByClass = function() {
  this.labeledNodes.sort(function (a, b) {
    return graph.classOf(a.node).localeCompare(graph.classOf(b.node));
  });
  this.groupsByEdge.sort(function (a, b) {
    return a.cls.localeCompare(b.cls);
  });
  this.groupsByClass.sort(function (a, b) {
    return a.cls.localeCompare(b.cls);
  });
  this.refreshRows();
};

Table.prototype.sortByShallowSize = function() {
  this.labeledNodes.sort(function (a, b) {
    return graph.shallowSizeOf(b.node) - graph.shallowSizeOf(a.node);
  });
  this.groupsByEdge.sort(function (a, b) {
    return b.shallowSize - a.shallowSize;
  });
  this.groupsByClass.sort(function (a, b) {
    return b.shallowSize - a.shallowSize;
  });
  this.refreshRows();
};

Table.prototype.sortByRetainedSize = function() {
  this.labeledNodes.sort(function (a, b) {
    return graph.retainedSizeOf(b.node) - graph.retainedSizeOf(a.node);
  });
  this.groupsByEdge.sort(function (a, b) {
    return b.ownedSize - a.ownedSize;
  });
  this.groupsByClass.sort(function (a, b) {
    return b.ownedSize - a.ownedSize;
  });
  this.refreshRows();
};

Table.prototype.refreshRows = function() {
  while (this.listDiv.firstChild) {
    this.listDiv.removeChild(this.listDiv.firstChild);
  }

  // To prevent rendering lag.
  const MAX_TABLE_ROWS = 500;

  if (this.grouping == 0) {
    let labeledNodes = this.labeledNodes;
    this.nom.textContent = this.title + " (" + labeledNodes.length + " objects)";
    this.retainedSize.textContent = "Retained Size";
    this.retainedSize.title = "Sort by retained size";

    for (let i = 0; i < labeledNodes.length; i++) {
      if (i > MAX_TABLE_ROWS) {
        this.listDiv.appendChild(document.createTextNode((labeledNodes.length - i) + " more objects"));
        break;
      }
      this.listDiv.appendChild(createObjectRow(labeledNodes[i]));
    }
  } else if (this.grouping == 1) {
    let groups = this.groupsByClass;
    this.nom.textContent = this.title + " (" + groups.length + " classes)";
    this.retainedSize.textContent = "Owned Size";
    this.retainedSize.title = "Sort by owned size";

    for (let i = 0; i < groups.length; i++) {
      if (i > MAX_TABLE_ROWS) {
        // Prevent rendering lag.
        this.listDiv.appendChild(document.createTextNode((groups.length - i) + " more classes"));
        break;
      }
      this.listDiv.appendChild(createGroupRow(groups[i]));
    }
  } else {
    let groups = this.groupsByEdge;
    this.nom.textContent = this.title + " (" + groups.length + " edges)";
    this.retainedSize.textContent = "Owned Size";
    this.retainedSize.title = "Sort by owned size";

    for (let i = 0; i < groups.length; i++) {
      if (i > MAX_TABLE_ROWS) {
        // Prevent rendering lag.
        this.listDiv.appendChild(document.createTextNode((groups.length - i) + " more edges"));
        break;
      }
      this.listDiv.appendChild(createGroupRow(groups[i]));
    }
  }
};

function createObjectRow(labeledNode) {
  const v = labeledNode.node;

  let nom = document.createElement("span");
  nom.onclick = function() { showTables([v]); }
  nom.className = "nameCell actionCell";
  nom.textContent = graph.nameOf(v);
  nom.title = "Select this object";

  let edge = document.createElement("span");
  edge.className = "edgeCell";
  edge.textContent = labeledNode.name;

  let cls = document.createElement("span");
  cls.className = "classCell";
  cls.textContent = graph.classOf(v);

  let shallowSize = document.createElement("span");
  shallowSize.className = "sizeCell";
  shallowSize.textContent = graph.shallowSizeOf(v);

  let shallowPercent = document.createElement("span");
  shallowPercent.className = "sizePercentCell";
  shallowPercent.textContent = prettyPercent(graph.shallowSizeOf(v) / graph.getTotalSize());

  function onClickRetained(event) {
    // For the root, default to the merged view for the sake of web browser layout performance.
    showDominatorTree(v == 1 ? graph.toggleMerge() : graph, v);
  }

  let retainedSize = document.createElement("span");
  retainedSize.onclick = onClickRetained;
  retainedSize.className = "sizeCell actionCell";
  retainedSize.textContent = graph.retainedSizeOf(v);
  retainedSize.title = "Show dominator tree";

  let retainedPercent = document.createElement("span");
  retainedPercent.onclick = onClickRetained;
  retainedPercent.className = "sizePercentCell actionCell";
  retainedPercent.textContent = prettyPercent(graph.retainedSizeOf(v) / graph.getTotalSize());
  retainedPercent.title = "Show dominator tree";

  let row = document.createElement("div");
  row.style["display"] = "flex";
  row.style["flex-direction"] = "row";
  row.style["border-bottom"] = "solid 1px";
  row.appendChild(nom);
  row.appendChild(edge);
  row.appendChild(cls);
  row.appendChild(shallowSize);
  row.appendChild(shallowPercent);
  row.appendChild(retainedSize);
  row.appendChild(retainedPercent);
  return row;
}

function createGroupRow(g) {
  let nom = document.createElement("span");
  nom.onclick = function() { showTables(g.nodes); }
  nom.className = "nameCell actionCell";
  nom.textContent = g.name;
  nom.title = "Select these objects";

  let cls = document.createElement("span");
  cls.className = "classCell";
  cls.textContent = g.cls;

  let edge = document.createElement("span");
  edge.className = "edgeCell";
  edge.textContent = g.edge;

  let shallowSize = document.createElement("span");
  shallowSize.className = "sizeCell";
  shallowSize.textContent = g.shallowSize;

  let shallowPercent = document.createElement("span");
  shallowPercent.className = "sizePercentCell";
  shallowPercent.textContent = prettyPercent(g.shallowSize / graph.getTotalSize());

  let ownedSize = document.createElement("span");
  ownedSize.className = "sizeCell";
  ownedSize.textContent = g.ownedSize;

  let ownedPercent = document.createElement("span");
  ownedPercent.className = "sizePercentCell";
  ownedPercent.textContent = prettyPercent(g.ownedSize / graph.getTotalSize());

  let row = document.createElement("div");
  row.style["display"] = "flex";
  row.style["flex-direction"] = "row";
  row.style["border-bottom"] = "solid 1px";
  row.appendChild(nom);
  row.appendChild(edge);
  row.appendChild(cls);
  row.appendChild(shallowSize);
  row.appendChild(shallowPercent);
  row.appendChild(ownedSize);
  row.appendChild(ownedPercent);
  return row;
}

function mapValuesToArray(map) {
  let array = new Array();
  for (let element of map.values()) {
    array.push(element);
  }
  return array;
}

function showTables(nodes) {
  let labeledNodes = new Array();
  let successors = new Map();
  let successorEdges = new Map();
  let successorEdgeGroups = new Array();
  let predecessors = new Map();
  let predecessorEdges = new Map();
  let predecessorEdgeGroups = new Array();
  for (let i = 0; i < nodes.length; i++) {
    let n = nodes[i];
    labeledNodes.push(new LabeledNode(n, "-"));
    graph.successorsOfDo(n, function (child, edgeName, edgeOwnedSize) {
      let e = successors.get(child);
      if (e) {
        e.addName(edgeName);
      } else {
        successors.set(child, new LabeledNode(child, edgeName));
      }
      let cls = graph.classOf(child);
      let g = successorEdges.get(edgeName);
      if (!g) {
        g = new Group(edgeName, cls);
        successorEdgeGroups.push(g);
        successorEdges.set(edgeName, g);
      }
      g.add(child, edgeName, cls);
      g.ownedSize += edgeOwnedSize;
    });
    graph.predecessorsOfDo(n, function (parent, edgeName) {
      let e = predecessors.get(parent);
      if (e) {
        e.addName(edgeName);
      } else {
        predecessors.set(parent, new LabeledNode(parent, edgeName));
      }
      let cls = graph.classOf(parent);
      let g = predecessorEdges.get(edgeName);
      if (!g) {
        g = new Group(edgeName, cls);
        predecessorEdgeGroups.push(g);
        predecessorEdges.set(edgeName, g);
      }
      g.add(parent, edgeName, cls);
    });
  }

  successors = mapValuesToArray(successors);
  for (let i = 0; i < successorEdgeGroups.length; i++) {
    let group = successorEdgeGroups[i];
    group.nodes = removeDuplicates(group.nodes);
    group.shallowSize = graph.shallowSizeOfSet(group.nodes);
    // group.ownedSize is the flow through the edges
    group.name = group.nodes.length + " targets of " + group.edge;
  }
  predecessors = mapValuesToArray(predecessors);
  for (let i = 0; i < predecessorEdgeGroups.length; i++) {
    let group = predecessorEdgeGroups[i];
    group.nodes = removeDuplicates(group.nodes);
    group.shallowSize = graph.shallowSizeOfSet(group.nodes);
    group.ownedSize = graph.ownedSizeOfSet(group.nodes);
    group.name = group.nodes.length + " sources of " + group.edge;
  }

  let rewrite = document.createElement("input");
  rewrite.setAttribute("type", "checkbox");

  let rewriteLabel = document.createElement("span");
  rewriteLabel.textContent = "Owners ";

  let input = document.createElement("input");
  input.setAttribute("type", "file");
  input.setAttribute("multiple", false);
  input.onchange = function(event) {
    let file = event.target.files[0];
    document.title = file.name;
    let reader = new FileReader();
    reader.readAsText(file, 'UTF-8');
    reader.onload = function(event) {
      let data = JSON.parse(event.target.result);
      let g = new Graph();
      g.loadV8Profile(data);
      data = null; // Release memory
      graph = g;
      g.compute(rewrite.checked);
      showTables([graph.getRoot()]);
    };
    reader = new FileReader();
    reader.readAsArrayBuffer(file);
    reader.onload = function(event) {
      let data = event.target.result;
      let g = new Graph();
      g.loadDartHeapSnapshot(data);
      data = null; // Release memory
      graph = g;
      g.compute(rewrite.checked);
      showTables([graph.getRoot()]);
    };
  };

  let selectRoot = document.createElement("button");
  selectRoot.textContent = "Select Root";
  selectRoot.onclick = function(event) {
    showTables([graph.getRoot()]);
  };

  let selectAll = document.createElement("button");
  selectAll.textContent = "Select All";
  selectAll.onclick = function(event) {
    showTables(graph.getAll());
  };

  let filler = document.createElement("span");
  filler.style["flex-grow"] = 1;

  let totalSize = document.createElement("span");
  totalSize.className = "sizeCell";
  totalSize.textContent = graph ? "" + graph.getTotalSize() : "0";

  let totalPercent = document.createElement("span");
  totalPercent.className = "sizePercentCell";
  totalPercent.textContent = prettyPercent(1.0);

  let topBar = document.createElement("div");
  topBar.className = "headerRow";
  topBar.style["border"] = "solid 2px";
  topBar.style["align-items"] = "center";
  topBar.appendChild(rewrite);
  topBar.appendChild(rewriteLabel);
  topBar.appendChild(input);
  if (graph) {
    topBar.appendChild(selectRoot);
    topBar.appendChild(selectAll);
    topBar.appendChild(filler);
    topBar.appendChild(totalSize);
    topBar.appendChild(totalPercent);
  }

  let selectionTable = new Table("Selection", labeledNodes, []).div;
  selectionTable.style["flex-basis"] = "0px";
  selectionTable.style["flex-grow"] = 1;

  let successorsTable = new Table("Successors", successors, successorEdgeGroups).div;
  successorsTable.style["flex-basis"] = "0px";
  successorsTable.style["flex-grow"] = 1;

  let predecessorsTable = new Table("Predecessors", predecessors, predecessorEdgeGroups).div;
  predecessorsTable.style["flex-basis"] = "0px";
  predecessorsTable.style["flex-grow"] = 1;

  let help1 = document.createElement("p");
  help1.textContent =
      "Create a snapshot profile by passing --write_v8_snapshot_profile_to=example.json to gen_snapshot."
  let help2 = document.createElement("p");
  help2.textContent =
      "In Flutter, run flutter build aot --release --extra-gen-snapshot-options=--write-v8-snapshot-profile-to=example.json";

  let column = document.createElement("div");
  column.style["height"] = "100%";
  column.style["display"] = "flex";
  column.style["flex-direction"] = "column";
  column.appendChild(topBar);
  column.appendChild(document.createElement("br"));
  if (graph) {
    column.appendChild(selectionTable);
    column.appendChild(document.createElement("br"));
    column.appendChild(successorsTable);
    column.appendChild(document.createElement("br"));
    column.appendChild(predecessorsTable);
  } else {
    column.appendChild(help1);
    column.appendChild(help2);
  }

  setBody(column);
}

function setBody(div) {
  let body = document.body;
  while (body.firstChild) {
    body.removeChild(body.firstChild);
  }
  body.appendChild(div);
}

let graph = null;
showTables([]);