dhat/dh_view.js

   1
   2 //--------------------------------------------------------------------*/
   3 //--- DHAT: a Dynamic Heap Analysis Tool                dh_view.js ---*/
   4 //--------------------------------------------------------------------*/
   5
   6 /*
   7    This file is part of DHAT, a Valgrind tool for profiling the
   8    heap usage of programs.
   9
  10    Copyright (C) 2018 Mozilla Foundation
  11
  12    This program is free software; you can redistribute it and/or
  13    modify it under the terms of the GNU General Public License as
  14    published by the Free Software Foundation; either version 2 of the
  15    License, or (at your option) any later version.
  16
  17    This program is distributed in the hope that it will be useful, but
  18    WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20    General Public License for more details.
  21
  22    You should have received a copy of the GNU General Public License
  23    along with this program; if not, see <http://www.gnu.org/licenses/>.
  24
  25    The GNU General Public License is contained in the file COPYING.
  26 */
  27
  28 /*
  29    Parts of this file are derived from Firefox, copyright Mozilla Foundation,
  30    and may be redistributed under the terms of the Mozilla Public License
  31    Version 2.0, as well as under the license of this project.  A copy of the
  32    Mozilla Public License Version 2.0 is available at at
  33    https://www.mozilla.org/en-US/MPL/2.0/.
  34 */
  35
  36 // Test this file by loading dh_view.html?test=1. That runs the tests in
  37 // dh_test.js and gives pass/fail indicators.
  38
  39 "use strict";
  40
  41 //------------------------------------------------------------//
  42 //--- Globals                                              ---//
  43 //------------------------------------------------------------//
  44
  45 // Important HTML elements.
  46 let gInput;
  47 let gSelect;
  48 let gHeaderDiv, gTestingDiv, gMainDiv, gLegendDiv, gTimingsDiv;
  49
  50 // The name of the loaded file.
  51 let gFilename;
  52
  53 // The object extracted from the JSON input.
  54 let gData;
  55
  56 // The root of the radix tree build from gData. A radix tree is a
  57 // space-optimized prefix tree in which each node that is the only child is
  58 // merged with its parent.
  59 let gRoot;
  60
  61 // Data relating to the sort metrics.
  62 //
  63 // - isDefault: True for the default sort metric.
  64 // - label: Used in the drop-down menu.
  65 // - bolds: Which fields to highlight in the output.
  66 // - cmpField: Field used to sort the radix tree.
  67 // - sig: Significance function used to determine aggregate nodes.
  68 // - sigLabel: Significance threshold description function.
  69 //
  70 const gSelectData = [
  71   {
  72     label: "Total (bytes)",
  73     bolds: { "totalTitle": 1, "totalBytes": 1 },
  74     cmpField: "_totalBytes",
  75     sig: (aT) => aT._totalBytes >= 0.01 * gRoot._totalBytes,
  76     sigLabel: () => `\
  77 total >= ${bytesAndPerc(0.01 * gRoot._totalBytes, gRoot._totalBytes)}`
  78   },
  79   {
  80     isDefault: true,
  81     label: "Total (blocks)",
  82     bolds: { "totalTitle": 1, "totalBlocks": 1 },
  83     cmpField: "_totalBlocks",
  84     sig: (aT) => aT._totalBlocks >= 0.01 * gRoot._totalBlocks,
  85     sigLabel: () => `\
  86 total >= ${blocksAndPerc(0.01 * gRoot._totalBlocks, gRoot._totalBlocks)}`
  87   },
  88   // No "Total (bytes), tiny" because it's extremely unlikely that an AP with a
  89   // tiny average size will take up a significant number of bytes.
  90   {
  91     label: "Total (blocks), tiny",
  92     bolds: { "totalTitle": 1, "totalBlocks": 1, "totalAvgSizeBytes": 1 },
  93     cmpField: "_totalBlocks",
  94     sig: (aT) => aT._totalBlocks >= 0.005 * gRoot._totalBlocks &&
  95                  aT._totalAvgSizeBytes() <= 16,
  96     sigLabel: () => `\
  97 (total >= ${blocksAndPerc(0.005 * gRoot._totalBlocks, gRoot._totalBlocks)}) && \
  98 (total avg size <= ${bytes(16)})`
  99   },
 100   // No "Total (bytes), short-lived", because an AP with few large, short-lived
 101   // blocks is unlikely. (In contrast, "Total (blocks), short-lived" is useful,
 102   // because an AP with many small, short-lived blocks *is* likely.) And if
 103   // such an AP existed, it'll probably show up in "Total (bytes), zero reads
 104   // or zero writes" or "Total (bytes), low-access" anyway, because there's
 105   // little time for accesses in 500 instructions.
 106   {
 107     label: "Total (blocks), short-lived",
 108     bolds: { "totalTitle": 1, "totalBlocks": 1, "totalAvgLifetimeInstrs": 1 },
 109     cmpField: "_totalBlocks",
 110     sig: (aT) => aT._totalBlocks >= 0.005 * gRoot._totalBlocks &&
 111                  aT._totalAvgLifetimeInstrs() <= 500,
 112     sigLabel: () => `\
 113 (total >= ${blocksAndPerc(0.005 * gRoot._totalBlocks, gRoot._totalBlocks)}) && \
 114 (total avg lifetime <= ${instrs(500)})`
 115   },
 116   {
 117     label: "Total (bytes), zero reads or zero writes",
 118     bolds: { "totalTitle": 1, "totalBytes": 1,
 119              "readsTitle": 1, "readsBytes": 1,
 120              "writesTitle": 1, "writesBytes": 1,
 121            },
 122     cmpField: "_totalBytes",
 123     sig: (aT) => aT._totalBytes >= 0.005 * gRoot._totalBytes &&
 124                  (aT._readsBytes === 0 || aT._writesBytes === 0),
 125     sigLabel: () => `\
 126 (total >= ${bytesAndPerc(0.005 * gRoot._totalBytes, gRoot._totalBytes)}) && \
 127 ((reads == ${bytes(0)}) || (writes == ${bytes(0)}))`
 128   },
 129   {
 130     label: "Total (blocks), zero reads or zero writes",
 131     bolds: { "totalTitle": 1, "totalBlocks": 1,
 132              "readsTitle": 1, "readsBytes": 1,
 133              "writesTitle": 1, "writesBytes": 1,
 134            },
 135     cmpField: "_totalBlocks",
 136     sig: (aT) => aT._totalBlocks >= 0.005 * gRoot._totalBlocks &&
 137                  (aT._readsBytes === 0 || aT._writesBytes === 0),
 138     sigLabel: () => `\
 139 (total >= ${blocksAndPerc(0.005 * gRoot._totalBlocks, gRoot._totalBlocks)}) && \
 140 ((reads == ${bytes(0)}) || (writes == ${bytes(0)}))`
 141   },
 142   {
 143     label: "Total (bytes), low-access",
 144     bolds: { "totalTitle": 1, "totalBytes": 1,
 145              "readsTitle": 1, "readsAvgPerByte": 1,
 146              "writesTitle": 1, "writesAvgPerByte": 1,
 147            },
 148     cmpField: "_totalBytes",
 149     sig: (aT) => aT._totalBytes >= 0.005 * gRoot._totalBytes &&
 150                  aT._readsBytes !== 0 &&
 151                  aT._writesBytes !== 0 &&
 152                  (aT._readsAvgPerByte() <= 0.4 ||
 153                   aT._writesAvgPerByte() <= 0.4),
 154     sigLabel: () => `\
 155 (total >= ${bytesAndPerc(0.005 * gRoot._totalBytes, gRoot._totalBytes)}) && \
 156 (reads != ${bytes(0)}) && \
 157 (writes != ${bytes(0)}) && \
 158 ((reads <= ${perByte(0.4)}) || (writes <= ${perByte(0.4)}))`
 159   },
 160   {
 161     label: "Total (blocks), low-access",
 162     bolds: { "totalTitle": 1, "totalBlocks": 1,
 163              "readsTitle": 1, "readsAvgPerByte": 1,
 164              "writesTitle": 1, "writesAvgPerByte": 1,
 165            },
 166     cmpField: "_totalBlocks",
 167     sig: (aT) => aT._totalBlocks >= 0.005 * gRoot._totalBlocks &&
 168                  aT._readsBytes !== 0 &&
 169                  aT._writesBytes !== 0 &&
 170                  (aT._readsAvgPerByte() <= 0.4 ||
 171                   aT._writesAvgPerByte() <= 0.4),
 172     sigLabel: () => `\
 173 (total >= ${blocksAndPerc(0.005 * gRoot._totalBlocks, gRoot._totalBlocks)}) && \
 174 (reads != ${bytes(0)}) && \
 175 (writes != ${bytes(0)}) && \
 176 ((reads <= ${perByte(0.4)}) || (writes <= ${perByte(0.4)}))`
 177   },
 178   // No "Total (avg size bytes)": not interesting.
 179   // No "Total (avg lifetime instrs)": covered by "Total (blocks), short-lived".
 180   // No "Max (bytes)": not interesting, and unclear how to sort.
 181   // No "Max (blocks)": not interesting, and unclear how to sort.
 182   // No "Max (avg size bytes)": not interesting, and unclear how to sort.
 183   {
 184     label: "At t-gmax (bytes)",
 185     bolds: { "atTGmaxTitle": 1, "atTGmaxBytes": 1 },
 186     cmpField: "_atTGmaxBytes",
 187     sig: (aT) => aT._atTGmaxBytes >= 0.01 * gRoot._atTGmaxBytes,
 188     sigLabel: () => `\
 189 at-t-gmax >= ${bytesAndPerc(0.01 * gRoot._atTGmaxBytes, gRoot._atTGmaxBytes)}`
 190   },
 191   // No "At t-gmax (blocks)": not interesting.
 192   // No "At t-gmax (avg size bytes)": not interesting.
 193   {
 194     label: "At t-end (bytes)",
 195     bolds: { "atTEndTitle": 1, "atTEndBytes": 1 },
 196     cmpField: "_atTEndBytes",
 197     sig: (aT) => aT._atTEndBytes >= 0.01 * gRoot._atTEndBytes,
 198     sigLabel: () => `\
 199 at-t-end >= ${bytesAndPerc(0.01 * gRoot._atTEndBytes, gRoot._atTEndBytes)}`
 200   },
 201   // No "At t-end (blocks)": not interesting.
 202   // No "At t-end (avg size bytes)": not interesting.
 203   {
 204     label: "Reads (bytes)",
 205     bolds: { "readsTitle": 1, "readsBytes": 1 },
 206     cmpField: "_readsBytes",
 207     sig: (aT) => aT._readsBytes >= 0.01 * gRoot._readsBytes,
 208     sigLabel: () => `\
 209 reads >= ${bytesAndPerc(0.01 * gRoot._readsBytes, gRoot._readsBytes)}`
 210   },
 211   {
 212     label: "Reads (bytes), high-access",
 213     bolds: { "readsTitle": 1, "readsBytes": 1, "readsAvgPerByte": 1 },
 214     cmpField: "_readsBytes",
 215     sig: (aT) => aT._readsBytes >= 0.005 * gRoot._readsBytes &&
 216                  (aT._readsAvgPerByte() >= 1000 ||
 217                   aT._writesAvgPerByte() >= 1000),
 218     sigLabel: () => `\
 219 (reads >= ${bytesAndPerc(0.005 * gRoot._readsBytes, gRoot._readsBytes)}) && \
 220 ((reads >= ${perByte(1000)}) || (writes >= ${perByte(1000)}))`
 221   },
 222   // No "Reads (avg per byte)": covered by other access-related ones.
 223   {
 224     label: "Writes (bytes)",
 225     bolds: { "writesTitle": 1, "writesBytes": 1 },
 226     cmpField: "_writesBytes",
 227     sig: (aT) => aT._writesBytes >= 0.01 * gRoot._writesBytes,
 228     sigLabel: () => `\
 229 writes >= ${bytesAndPerc(0.01 * gRoot._writesBytes, gRoot._writesBytes)}`
 230   },
 231   {
 232     label: "Writes (bytes), high-access",
 233     bolds: { "writesTitle": 1, "writesBytes": 1, "writesAvgPerByte": 1 },
 234     cmpField: "_writesBytes",
 235     sig: (aT) => aT._writesBytes >= 0.005 * gRoot._writesBytes &&
 236                  (aT._readsAvgPerByte() >= 1000 ||
 237                   aT._writesAvgPerByte() >= 1000),
 238     sigLabel: () => `\
 239 (writes >= ${bytesAndPerc(0.005 * gRoot._writesBytes, gRoot._writesBytes)}) && \
 240 ((reads >= ${perByte(1000)}) || (writes >= ${perByte(1000)}))`
 241   }
 242   // No "Writes (avg per byte)": covered by other access-related ones.
 243 ];
 244
 245 //------------------------------------------------------------//
 246 //--- Utilities                                            ---//
 247 //------------------------------------------------------------//
 248
 249 // Assertion. Fails if aMsg is missing.
 250 function assert(aCond, aMsg) {
 251   if (!aCond || !aMsg) {
 252     throw new Error(`assertion failed: ${aMsg}`);
 253   }
 254 }
 255
 256 // Division function that returns 0 instead of NaN for 0/0, which is what we
 257 // always want.
 258 function div(aNum, aDenom) {
 259   return aNum === 0 && aDenom === 0 ? 0 : aNum / aDenom;
 260 }
 261
 262 // Execute a function, printing any exception to the page.
 263 function tryFunc(aFunc) {
 264   try {
 265     aFunc();
 266   } catch (ex) {
 267     // Clear gRoot, so that any old or partially-built new value doesn't hang
 268     // around if after this exception is thrown.
 269     gRoot = undefined;
 270     clearMainDivWithText(ex.toString(), "error");
 271     throw ex;
 272   }
 273 }
 274
 275 // Put some text in a div at the bottom of the page. Useful for debugging.
 276 function debug(x) {
 277   let section = appendElement(document.body, "div", "section");
 278   appendElementWithText(section, "div", JSON.stringify(x), "debug noselect");
 279 }
 280
 281 //------------------------------------------------------------//
 282 //--- Radix tree building                                  ---//
 283 //------------------------------------------------------------//
 284
 285 // Notes about the TreeNode kinds:
 286 //
 287 // --------------------------------------------------------------------
 288 //                              Leaf          Internal        Aggregate
 289 // --------------------------------------------------------------------
 290 // Has this._kids?              No            Yes             No
 291 // Has this._max*?              Yes           No              No
 292 // Has this._accesses?          Maybe         Maybe           No
 293 // Allowed this._sig values?    Self,None     Self,Desc,None  None
 294 // How many this._add() calls?  1             1+              1+
 295 // --------------------------------------------------------------------
 296 //
 297 const kLeaf     = 1;
 298 const kInternal = 2;
 299 const kAgg      = 3;
 300
 301 function TreeNode(aKind, aFrames) {
 302   this._kind = aKind;
 303
 304   this._totalBytes = 0;
 305   this._totalBlocks = 0;
 306
 307   this._totalLifetimesInstrs = 0;
 308
 309   // These numbers only make sense for leaf nodes. Unlike total stats, which
 310   // can be summed, _maxBytes/_maxBlocks for two APs can't be easily combined
 311   // because the maxes may have occurred at different times.
 312   if (this._kind === kLeaf) {
 313     this._maxBytes = 0;
 314     this._maxBlocks = 0;
 315   }
 316
 317   this._atTGmaxBytes = 0;
 318   this._atTGmaxBlocks = 0;
 319
 320   this._atTEndBytes = 0;
 321   this._atTEndBlocks = 0;
 322
 323   this._readsBytes = 0;
 324   this._writesBytes = 0;
 325
 326   // this._accesses is left undefined. It will be added if necessary.
 327   // The possible values have the following meanings:
 328   // - undefined means "unset accesses" (i.e. new node, never been set)
 329   // - length==0 means "no accesses" (i.e. some kids have accesses and some
 330   //   don't, or all kids have accesses but in different sizes)
 331   // - length>0 means "accesses" (i.e. all kids have accesses and all the same
 332   //   size)
 333
 334   // If a node would only have a single child, we instead effectively inline it
 335   // in the parent. Therefore a node can have multiple frames.
 336   this._frames = aFrames;
 337
 338   // this._kids is left undefined. It will be added if necessary.
 339
 340   // this._sig is added later, by sigTree().
 341 }
 342
 343 TreeNode.prototype = {
 344   _add(aTotalBytes, aTotalBlocks, aTotalLifetimesInstrs, aMaxBytes,
 345        aMaxBlocks, aAtTGmaxBytes, aAtTGmaxBlocks, aAtTEndBytes,
 346        aAtTEndBlocks, aReadsBytes, aWritesBytes, aAccesses) {
 347
 348     // We ignore this._kind, this._frames, and this._kids.
 349
 350     this._totalBytes += aTotalBytes;
 351     this._totalBlocks += aTotalBlocks;
 352     this._totalLifetimesInstrs += aTotalLifetimesInstrs;
 353
 354     if (this._kind === kLeaf) {
 355       // Leaf nodes should only be added to once, because DHAT currently
 356       // produces records with unique locations. If we remove addresses from
 357       // frames in the future then something must be done here to sum non-zero
 358       // _maxBytes and _maxBlocks values, but it's unclear exactly what. Range
 359       // arithmetic is a (complicated) possibility.
 360       assert(this._maxBytes === 0, "bad _maxBytes: " + this._maxBytes);
 361       assert(this._maxBlocks === 0, "bad _maxBlocks: " + this._maxBlocks);
 362       this._maxBytes += aMaxBytes;
 363       this._maxBlocks += aMaxBlocks;
 364     }
 365
 366     this._atTGmaxBytes += aAtTGmaxBytes;
 367     this._atTGmaxBlocks += aAtTGmaxBlocks;
 368
 369     this._atTEndBytes += aAtTEndBytes;
 370     this._atTEndBlocks += aAtTEndBlocks;
 371
 372     this._readsBytes += aReadsBytes;
 373     this._writesBytes += aWritesBytes;
 374
 375     if (this._kind !== kAgg) {
 376       if (!this._accesses && aAccesses) {
 377         // unset accesses += accesses --> has accesses (must clone the array)
 378         this._accesses = aAccesses.slice();
 379       } else if (this._accesses && aAccesses &&
 380                  this._accesses.length === aAccesses.length) {
 381         // accesses += accesses (with matching lengths) --> accesses
 382         for (let i = 0; i < this._accesses.length; i++) {
 383           this._accesses[i] += aAccesses[i];
 384         }
 385       } else {
 386         // any other combination --> no accesses
 387         this._accesses = [];
 388       }
 389     } else {
 390       assert(!this._accesses, "agg nodes cannot have accesses");
 391     }
 392   },
 393
 394   _addAP(aAP) {
 395     this._add(aAP.tb, aAP.tbk, aAP.tli, aAP.mb, aAP.mbk, aAP.gb, aAP.gbk,
 396               aAP.fb, aAP.fbk, aAP.rb, aAP.wb, aAP.acc);
 397   },
 398
 399   // This is called in two cases.
 400   // - Splitting a node, where we are adding to a fresh node (i.e. effectively
 401   //   cloning a node).
 402   // - Aggregating multiple nodes.
 403   _addNode(aT) {
 404     this._add(aT._totalBytes, aT._totalBlocks, aT._totalLifetimesInstrs,
 405               aT._maxBytes, aT._maxBlocks, aT._atTGmaxBytes, aT._atTGmaxBlocks,
 406               aT._atTEndBytes, aT._atTEndBlocks,
 407               aT._readsBytes, aT._writesBytes, aT._accesses);
 408   },
 409
 410   // Split the node after the aTi'th internal frame. The inheriting kid will
 411   // get the post-aTi frames; the new kid will get aNewFrames.
 412   _split(aTi, aAP, aNewFrames) {
 413     // kid1 inherits t's kind and values.
 414     let inheritedFrames = this._frames.splice(aTi + 1);
 415     let kid1 = new TreeNode(this._kind, inheritedFrames);
 416     if (this._kids) {
 417       kid1._kids = this._kids;
 418     }
 419     kid1._addNode(this);
 420
 421     // Put all remaining frames into kid2.
 422     let kid2 = new TreeNode(kLeaf, aNewFrames);
 423     kid2._addAP(aAP);
 424
 425     // Update this.
 426     if (this._kind === kLeaf) {
 427       // Convert to an internal node.
 428       this._kind = kInternal;
 429       assert(this.hasOwnProperty("_maxBytes"), "missing _maxBytes");
 430       assert(this.hasOwnProperty("_maxBlocks"), "missing _maxBlocks");
 431       delete this._maxBytes;
 432       delete this._maxBlocks;
 433     }
 434     this._kids = [kid1, kid2];
 435     this._addAP(aAP);
 436   },
 437
 438   _totalAvgSizeBytes() {
 439     return div(this._totalBytes, this._totalBlocks);
 440   },
 441
 442   _totalAvgLifetimeInstrs() {
 443     return div(this._totalLifetimesInstrs, this._totalBlocks);
 444   },
 445
 446   _maxAvgSizeBytes() {
 447     assert(this._kind === kLeaf, "non-leaf node");
 448     return div(this._maxBytes, this._maxBlocks);
 449   },
 450
 451   _atTGmaxAvgSizeBytes() {
 452     return div(this._atTGmaxBytes, this._atTGmaxBlocks);
 453   },
 454
 455   _atTEndAvgSizeBytes() {
 456     return div(this._atTEndBytes, this._atTEndBlocks);
 457   },
 458
 459   _readsAvgPerByte() {
 460     return div(this._readsBytes, this._totalBytes);
 461   },
 462
 463   _writesAvgPerByte() {
 464     return div(this._writesBytes, this._totalBytes);
 465   }
 466 }
 467
 468 // Check if the fields in `aFields` are present in `aObj`.
 469 function checkFields(aObj, aFields) {
 470   for (let f of aFields) {
 471     if (!aObj.hasOwnProperty(f)) {
 472       throw new Error(`data file is missing a field: ${f}`);
 473     }
 474   }
 475 }
 476
 477 // Do basic checking of an AP read from file.
 478 function checkAP(aAP) {
 479   let fields = ["tb", "tbk", "tli",
 480                 "mb", "mbk",
 481                 "gb", "gbk",
 482                 "fb", "fbk",
 483                 "rb", "wb",
 484                 "fs"];
 485   checkFields(aAP, fields);
 486 }
 487
 488 // Access counts latch as 0xffff. Treating 0xffff as Infinity gives us exactly
 489 // the behaviour we want, e.g. Infinity + 1 = Infinity.
 490 function normalizeAccess(aAcc) {
 491   if (aAcc < 0xffff) {
 492     return aAcc;
 493   }
 494   if (aAcc === 0xffff) {
 495     return Infinity;
 496   }
 497   assert(false, "too-large access value");
 498 }
 499
 500 const kExpectedFileVersion = 1;
 501
 502 // Build gRoot from gData.
 503 function buildTree() {
 504   // Check global values.
 505   let fields = ["dhatFileVersion",
 506                 "cmd", "pid",
 507                 "mi", "ei",
 508                 "aps", "ftbl"];
 509   checkFields(gData, fields);
 510   if (gData.dhatFileVersion != kExpectedFileVersion) {
 511       throw Error(`data file has version number ${gData.dhatFileVersion}, ` +
 512                   `expected version number ${kExpectedFileVersion}`);
 513   }
 514
 515   // Build the radix tree. Nodes are in no particular order to start with. The
 516   // algorithm is tricky because we need to use internal frames when possible.
 517   gRoot = new TreeNode(kLeaf, [0]);   // Frame 0 is always "[root]".
 518
 519   for (let [i, ap] of gData.aps.entries()) {
 520     checkAP(ap);
 521
 522     // Decompress the run-length encoding in `acc`, if present.
 523     if (ap.acc) {
 524       let acc = [];
 525       for (let i = 0; i < ap.acc.length; i++) {
 526         if (ap.acc[i] < 0) {
 527           // A negative number encodes a repeat count. The following entry has
 528           // the value to be repeated.
 529           let reps = -ap.acc[i++];
 530           let val = ap.acc[i];
 531           for (let j = 0; j < reps; j++) {
 532             acc.push(normalizeAccess(val));
 533           }
 534         } else {
 535           acc.push(normalizeAccess(ap.acc[i]));
 536         }
 537       }
 538       ap.acc = acc;
 539     }
 540
 541     // The first AP is a special case, because we have to build gRoot.
 542     if (i === 0) {
 543       gRoot._frames.push(...ap.fs);
 544       gRoot._addAP(ap);
 545       continue;
 546     }
 547
 548     let t = gRoot;  // current node
 549     let ti = 0;     // current frame index within t
 550     let done = false;
 551
 552     // In the examples below, tree nodes have the form `abcd:N-Xs`, where
 553     // `abcd` is a frame sequence (and `-` is an empty sequence), `N` is a node
 554     // value, and `Xs` are the node's children.
 555
 556     for (let [j, kidFrame] of ap.fs.entries()) {
 557
 558       // Search for kidFrame among internal frames.
 559       if (ti + 1 < t._frames.length) {
 560         // t has an internal frame at the right index.
 561
 562         if (t._frames[ti + 1] === kidFrame) {
 563           // The internal frame matches. Move to t's next internal frame.
 564           ti++;
 565         } else {
 566           // The internal frame doesn't match. Split the node.
 567           //
 568           // E.g. abcd:20-[] + abef:10 => ab:30-[cd:20-[], ef:10-[]]
 569           t._split(ti, ap, ap.fs.slice(j));
 570           done = true;
 571           break;
 572         }
 573
 574       } else {
 575         // We've run out of internal frames in t. Consider t's kids.
 576
 577         if (!t._kids) {
 578           // No kids; this must be a supersequence of an existing sequence.
 579           // Split t; the inheriting kid will get no frames, the new kid will
 580           // get the leftover frames.
 581           //
 582           // E.g. ab:20-[] + abcd:10 => ab:30-[-:20-[], cd:10-[]]
 583           t._split(ti, ap, ap.fs.slice(j));
 584           done = true;
 585           break;
 586         }
 587
 588         t._addAP(ap);
 589
 590         // Search for the frame among the kids.
 591         let kid;
 592         for (let k of t._kids) {
 593           if (k._frames[0] === kidFrame) {
 594             kid = k;
 595             break;
 596           }
 597         }
 598         if (kid) {
 599           // Found it. Move to it.
 600           t = kid;
 601           ti = 0;
 602         } else {
 603           // Didn't find it. Put all remaining frames into a new leaf node.
 604           //
 605           // E.g. ab:20-[c:10-Xs, d:10-Ys] + abef:10 =>
 606           //      ab:30-[c:10-Xs, d:10-Ys, ef:10-[]]
 607           kid = new TreeNode(kLeaf, ap.fs.slice(j));
 608           kid._addAP(ap);
 609           t._kids.push(kid);
 610           done = true;
 611           break;
 612         }
 613       }
 614     }
 615
 616     if (!done) {
 617       // If we reach here, either:
 618       // - ap's frames match an existing frame sequence, in which case we
 619       //   just need to _addAP(); or
 620       // - ap's frames are a subsequence of an existing sequence, in which
 621       //   case we must split.
 622
 623       if (ti + 1 < t._frames.length) {
 624         // A subsequence of an existing sequence that ends within t's internal
 625         // frames. Split, creating an empty node.
 626         //
 627         // E.g. abcd:20-Xs + ab:10 => ab:30-[cd:20-Xs, -:10-[]]
 628         t._split(ti, ap, []);
 629
 630       } else if (!t._kids) {
 631         // This is impossible because DHAT currently produces records with
 632         // unique locations. If we remove addresses from frames in the future
 633         // then duplicate locations will occur, and the following code is how
 634         // it must be handled.
 635         throw Error(`data file contains a repeated location`);
 636
 637         // Matches an existing sequence that doesn't end in node with empty
 638         // frames. Add the AP.
 639         //
 640         // E.g. ab:20-[] + ab:10 => ab:30-[]
 641         t._addAP(ap);
 642
 643       } else {
 644         // Look for a kid with empty frames.
 645         let emptyKid;
 646         for (let k of t._kids) {
 647           if (k._frames.length === 0) {
 648             emptyKid = k;
 649             break;
 650           }
 651         }
 652
 653         if (emptyKid) {
 654           // This is impossible because DHAT currently produces records with
 655           // unique locations. If we remove addresses from frames in the future
 656           // then duplicate locations will occur, and the following code is how
 657           // it must be handled.
 658           throw Error(`data file contains a repeated location`);
 659
 660           // Matches an existing sequence that ends in a node with empty
 661           // frames. Add the AP.
 662           //
 663           // E.g. ab:20-[c:10-Xs, -:10-[]] + ab:10 => ab:30-[c:10-Xs, -:20-[]]
 664           t._addAP(ap);
 665           emptyKid._addAP(ap);
 666
 667         } else {
 668           // A subsequence of an existing sequence that ends at the end of t's
 669           // internal frames. Append an empty node.
 670           //
 671           // E.g. ab:20-[c:10-Xs, d:10-Ys] + ab:10 =>
 672           //      ab:30-[c:10-Xs, d:10-Ys, -:10-[]]
 673           let newKid = new TreeNode(kLeaf, []);
 674           newKid._addAP(ap);
 675
 676           t._kids.push(newKid);
 677           t._addAP(ap);
 678         }
 679       }
 680     }
 681
 682   }
 683 }
 684
 685 //------------------------------------------------------------//
 686 //--- Pretty printers                                      ---//
 687 //------------------------------------------------------------//
 688
 689 // Using Intl.NumberFormat makes things faster than using toLocaleString()
 690 // repeatedly.
 691 const kPFormat = new Intl.NumberFormat(undefined, { maximumFractionDigits: 2, style: "percent" });
 692 const kDFormat = new Intl.NumberFormat(undefined, { maximumFractionDigits: 2 }); // decimal
 693 const kTFormat = new Intl.NumberFormat(); // time
 694
 695 function perc(aNum, aDenom) {
 696   return kPFormat.format(div(aNum, aDenom));
 697 }
 698
 699 function perMinstr(aN) {
 700   return `${kDFormat.format(div(1000000 * aN, gData.ei))}/Minstr`;
 701 }
 702
 703 function bytes(aN) {
 704   return `${kDFormat.format(aN)} bytes`;
 705 }
 706
 707 function bytesAndPerc(aN, aTotalN) {
 708   return `${bytes(aN)} (${perc(aN, aTotalN)})`;
 709 }
 710
 711 function bytesAndPercAndRate(aN, aTotalN) {
 712   return `${bytes(aN)} (${perc(aN, aTotalN)}, ${perMinstr(aN)})`;
 713 }
 714
 715 function blocks(aN) {
 716   return `${kDFormat.format(aN)} blocks`;
 717 }
 718
 719 function blocksAndPerc(aN, aTotalN) {
 720   return `${blocks(aN)} (${perc(aN, aTotalN)})`;
 721 }
 722
 723 function blocksAndPercAndRate(aN, aTotalN) {
 724   return `${blocks(aN)} (${perc(aN, aTotalN)}, ${perMinstr(aN)})`;
 725 }
 726
 727 function avgSizeBytes(aN) {
 728   return `avg size ${bytes(aN)}`;
 729 }
 730
 731 function perByte(aN) {
 732   return `${kDFormat.format(aN)}/byte`;
 733 }
 734
 735 function instrs(aN) {
 736   return `${kDFormat.format(aN)} instrs`;
 737 }
 738
 739 function avgLifetimeInstrs(aN) {
 740   return `avg lifetime ${instrs(aN)}`;
 741 }
 742
 743 function accesses(aAccesses) {
 744   // Make zero stand out.
 745   if (aAccesses === 0) {
 746     return "-";
 747   }
 748
 749   if (aAccesses === Infinity) {
 750     return "∞";
 751   }
 752
 753   // Don't use toLocaleString() -- in this case the values rarely reach
 754   // 100,000, and the grid formatting means the separators tend to make the
 755   // numbers harder to read. (And locales such as fr-FR use ' ' as the
 756   // separator, which conflicts with our use of ' ' between values!)
 757   return aAccesses.toString();
 758 }
 759
 760 function ms(aNum) {
 761   // This function is called only a handful of times, so there is no need to
 762   // use Intl.NumberFormat.
 763   return aNum !== undefined ? `${kTFormat.format(aNum)}ms` : "n/a";
 764 }
 765
 766 //------------------------------------------------------------//
 767 //--- DOM manipulation                                     ---//
 768 //------------------------------------------------------------//
 769
 770 const kDocumentTitle = "DHAT Viewer";
 771
 772 document.title = kDocumentTitle;
 773
 774 function appendElement(aP, aTagName, aClassName) {
 775   let e = document.createElement(aTagName);
 776   if (aClassName) {
 777     e.className = aClassName;
 778   }
 779   aP.appendChild(e);
 780   return e;
 781 }
 782
 783 function appendElementWithText(aP, aTagName, aText, aClassName) {
 784   let e = appendElement(aP, aTagName, aClassName);
 785   e.textContent = aText;
 786   return e;
 787 }
 788
 789 function appendText(aP, aText) {
 790   let e = document.createTextNode(aText);
 791   aP.appendChild(e);
 792   return e;
 793 }
 794
 795 function clearDiv(aDiv) {
 796   // Replace aDiv with an empty node.
 797   assert(aDiv, "no div given");
 798   let tmp = aDiv.cloneNode(/* deep = */ false);
 799   aDiv.parentNode.replaceChild(tmp, aDiv);
 800   return tmp;
 801 }
 802
 803 function clearMainDiv() {
 804   gMainDiv = clearDiv(gMainDiv);
 805 }
 806
 807 function clearTimingsDiv() {
 808   gTimingsDiv = clearDiv(gTimingsDiv);
 809 }
 810
 811 function clearMainDivWithText(aText, aClassName) {
 812   clearMainDiv();
 813   appendElementWithText(gMainDiv, "span", aText, aClassName);
 814 }
 815
 816 function appendInvocationAndTimes(aP) {
 817   let v, v1, v2;
 818
 819   v = "Invocation {\n";
 820   v += `  Command: ${gData.cmd}\n`;
 821   v += `  PID:     ${gData.pid}\n`;
 822   v += "}\n\n";
 823
 824   appendElementWithText(aP, "span", v, "invocation");
 825
 826   v = "Times {\n";
 827
 828   v1 = perc(gData.mi, gData.ei);
 829   v += `  t-gmax: ${instrs(gData.mi)} (${v1} of program duration)\n`;
 830   v += `  t-end:  ${instrs(gData.ei)}\n`;
 831
 832   v += "}\n\n";
 833
 834   appendElementWithText(aP, "span", v, "times");
 835 }
 836
 837 // Arrows indicating what state a node is in.
 838 const kNoKidsArrow      = "─ ";     // cannot change
 839 const kHidingKidsArrow  = "▶ ";     // expandible
 840 const kShowingKidsArrow = "▼ ";     // collapsible
 841
 842 // HTML doesn't have a tree element, so we fake one with text. One nice
 843 // consequence is that you can copy and paste the output. The non-ASCII chars
 844 // used (for arrows and tree lines) usually reproduce well when pasted into
 845 // textboxes.
 846 //
 847 // - aT: The sub-tree to append.
 848 // - aP: Parent HTML element to append to.
 849 // - aBolds: Which fields to highlight in the output.
 850 // - aPc: The percentage function.
 851 // - aCmp: The comparison function.
 852 // - aSig: The significance function.
 853 // - aNodeIdNums: The node ID numbers, e.g. [1,2,3], which is printed "1.2.3".
 854 // - aNumSibs: The number of siblings that aT has.
 855 // - aOldFrames: Frames preceding this node's frames.
 856 // - aTlFirst: Treeline for the first line of the node.
 857 // - aTlRest: Treeline for the other lines of the node, and its kids.
 858 //
 859 function appendTreeInner(aT, aP, aBolds, aCmp, aPc, aSig, aNodeIdNums,
 860                          aNumSibs, aOldFrames, aTlFirst, aTlRest) {
 861   // The primary element we'll be appending to.
 862   let p;
 863
 864   // We build up text fragments in up to seven groups:
 865   // - pre-Bold1 (multiple)
 866   // - Bold1 (single)
 867   // - post-Bold1 (multiple)
 868   // - Bold2 (single)
 869   // - post-Bold2 (multiple)
 870   // - Bold3 (single)
 871   // - post-Bold3 (multiple)
 872   //
 873   // This is so that up to 3 bold sequences can be highlighted per line.
 874   let frags, fi;
 875
 876   // Clear the text fragments.
 877   function clear() {
 878     frags = [[], undefined, [], undefined, [], undefined, []];
 879     fi = 0;
 880   }
 881
 882   // Add a fragment.
 883   // - aShowIfInsig: should we show this even in an insignificant node?
 884   // - aIsBold: if this is shown, should it be bold? If undefined (as is
 885   //   common) it takes the same value as aShowIfInsig.
 886   function fr(aStr, aShowIfInsig, aIsBold) {
 887     if (!aShowIfInsig && aT._sig !== kSigSelf) {
 888       return;
 889     }
 890
 891     if (aIsBold === undefined) {
 892       aIsBold = aShowIfInsig;
 893     }
 894
 895     if (aIsBold) {
 896       assert(fi === 0 || fi === 2 || fi === 4, "bad fragIndex (1)");
 897       assert(frags[fi + 1] === undefined, "bold already here");
 898       frags[fi + 1] = aStr;
 899       fi += 2;
 900     } else {
 901       assert(fi === 0 || fi === 2 || fi === 4 || fi === 6, "bad fragIndex (2)");
 902       frags[fi].push(aStr);
 903     }
 904   }
 905
 906   // Add a newline fragment (with a following treeline, unless aIsLast==true).
 907   // - aShowIfInsig: should we show this even in an insignificant node?
 908   // - aIsLast: is this the last newline for the node?
 909   function nl(aShowIfInsig, aIsLast) {
 910     assert(fi === 0 || fi === 2 || fi === 4 || fi === 6, "bad fragIndex (3)");
 911     if (!aShowIfInsig && aT._sig !== kSigSelf) {
 912       return;
 913     }
 914
 915     frags[fi].push("\n");
 916
 917     // Alternate the non-bold fragments (each in a text node) and bold
 918     // fragments (each in a span).
 919     if (frags[0].length > 0) {
 920       appendText(p, frags[0].join(""));
 921     }
 922     if (frags[1] !== undefined) {
 923       appendElementWithText(p, "span", frags[1], "bold");
 924     }
 925     if (frags[2].length > 0) {
 926       appendText(p, frags[2].join(""));
 927     }
 928     if (frags[3] !== undefined) {
 929       appendElementWithText(p, "span", frags[3], "bold");
 930     }
 931     if (frags[4].length > 0) {
 932       appendText(p, frags[4].join(""));
 933     }
 934     if (frags[5] !== undefined) {
 935       appendElementWithText(p, "span", frags[5], "bold");
 936     }
 937     if (frags[6].length > 0) {
 938       appendText(p, frags[6].join(""));
 939     }
 940
 941     if (!aIsLast) {
 942       appendElementWithText(p, "span", aTlRest, "treeline");
 943       clear();
 944     }
 945   }
 946
 947   clear();
 948
 949   // Traverse the kids, aggregating insignificant nodes.
 950   let kids;
 951   if (aT._kids) {
 952     kids = [];
 953     let agg, nAgg = 0;
 954
 955     for (let kid of aT._kids) {
 956       assert(kid._sig === kSigSelf || kid._sig === kSigDesc ||
 957              kid._sig === kSigNone, "kid _sig not set");
 958
 959       if (kid._sig !== kSigNone) {
 960         // `kid` is at least partially significant. Just push it as-is.
 961         kids.push(kid);
 962       } else {
 963         // `kid` is insignificant. Aggregate it.
 964         if (!agg) {
 965           // We fill in ._frames below, once we know how many kids were
 966           // aggregated.
 967           agg = new TreeNode(kAgg, undefined);
 968           agg._sig = kSigNone;
 969           kids.push(agg);
 970         }
 971         nAgg++;
 972         agg._addNode(kid);
 973       }
 974     }
 975
 976     if (agg) {
 977       // Fill in agg._frames.
 978       let insigFrame = `[${nAgg} insignificant]`;
 979       agg._frames = [insigFrame];
 980     }
 981
 982     kids.sort(aCmp);
 983   }
 984   // Note: need to use `kids` for the rest of this function, not `aT._kids`.
 985
 986   // Put the percentage into a colour band. The obvious way to do this is
 987   // with equal-sized bands (e.g. 0--20%, 20--40%, ...) but that doesn't work
 988   // well because in practice we have few nodes with mid-to-high percentages,
 989   // and many nodes with small percentages. So we use a logarithmic
 990   // distribution instead, so small values are better distinguished. (This is
 991   // reasonable in a way: a 2% node is twice as important as a 1%, a 4% node
 992   // is twice as important as a 2% node, etc.)
 993   let pc = aPc(aT);
 994   let lt = (aT._sig !== kSigSelf) ? "insig" // insignificant nodes
 995          : (pc <  1) ? "lt1"                //  0% to   0.999%
 996          : (pc <  2) ? "lt2"                //  1% to   1.999%
 997          : (pc <  4) ? "lt4"                //  2% to   3.999%
 998          : (pc <  8) ? "lt8"                //  4% to   7.999%
 999          : (pc < 16) ? "lt16"               //  8% to  15.999%
1000          : (pc < 32) ? "lt32"               // 16% to  31.999%
1001          :             "lt100";             // 32% to 100%
1002
1003   // Append the primary element.
1004   let arrow;
1005   if (kids) {
1006     p = appendElement(aP, "span", lt + " internal expanded");
1007     p.onclick = toggleClass;
1008     arrow = kShowingKidsArrow;
1009   } else {
1010     p = appendElement(aP, "span", lt + " leaf");
1011     arrow = kNoKidsArrow;
1012   }
1013
1014   // Node start: treeline and arrow.
1015   appendElementWithText(p, "span", aTlFirst, "treeline");
1016   appendElementWithText(p, "span", arrow, "arrow");
1017
1018   let v1, v2, v3, v4, v5;
1019
1020   // "AP" + node ID + kid count.
1021   v1 = aNodeIdNums.join('.');
1022   v2 = aNumSibs + 1;
1023   v3 = kids ? `(${kids.length} children) ` : "";
1024   fr(`AP ${v1}/${v2} ${v3}{`, true, false);
1025   nl(true);
1026
1027   // "Total".
1028   v1 = bytesAndPercAndRate(aT._totalBytes, gRoot._totalBytes);
1029   v2 = blocksAndPercAndRate(aT._totalBlocks, gRoot._totalBlocks);
1030   v3 = avgSizeBytes(aT._totalAvgSizeBytes());
1031   v4 = avgLifetimeInstrs(aT._totalAvgLifetimeInstrs());
1032   v5 = perc(aT._totalAvgLifetimeInstrs(), gData.ei);
1033   fr("  Total:     ", aBolds.totalTitle);
1034   fr(v1, aBolds.totalBytes);
1035   fr(" in ");
1036   fr(v2, aBolds.totalBlocks);
1037   fr(", ", aBolds.totalAvgSizeBytes, false);
1038   fr(v3, aBolds.totalAvgSizeBytes);
1039   fr(", ", aBolds.totalAvgLifetimeInstrs, false);
1040   fr(`${v4} (${v5} of program duration)`, aBolds.totalAvgLifetimeInstrs);
1041   nl(aBolds.totalTitle);
1042
1043   // "Max".
1044   if (aT !== gRoot && aT._kind === kLeaf) {
1045     assert(!kids, "leaf node has children");
1046     // These percentages are relative to the local totals, not the root
1047     // totals.
1048     v1 = bytes(aT._maxBytes);
1049     v2 = blocks(aT._maxBlocks);
1050     v3 = avgSizeBytes(aT._maxAvgSizeBytes());
1051     fr(`  Max:       ${v1} in ${v2}, ${v3}`);
1052     nl();
1053   }
1054
1055   // "At t-gmax".
1056   v1 = bytesAndPerc(aT._atTGmaxBytes, gRoot._atTGmaxBytes);
1057   v2 = blocksAndPerc(aT._atTGmaxBlocks, gRoot._atTGmaxBlocks);
1058   v3 = avgSizeBytes(aT._atTGmaxAvgSizeBytes());
1059   fr("  At t-gmax: ", aBolds.atTGmaxTitle);
1060   fr(v1, aBolds.atTGmaxBytes);
1061   fr(` in ${v2}, ${v3}`);
1062   nl(aBolds.atTGmaxTitle);
1063
1064   // "At t-end".
1065   v1 = bytesAndPerc(aT._atTEndBytes, gRoot._atTEndBytes);
1066   v2 = blocksAndPerc(aT._atTEndBlocks, gRoot._atTEndBlocks);
1067   v3 = avgSizeBytes(aT._atTEndAvgSizeBytes());
1068   fr("  At t-end:  ", aBolds.atTEndTitle);
1069   fr(v1, aBolds.atTEndBytes);
1070   fr(` in ${v2}, ${v3}`);
1071   nl(aBolds.atTEndTitle);
1072
1073   // "Reads".
1074   v1 = bytesAndPercAndRate(aT._readsBytes, gRoot._readsBytes);
1075   v2 = perByte(aT._readsAvgPerByte());
1076   fr("  Reads:     ", aBolds.readsTitle);
1077   fr(v1, aBolds.readsBytes);
1078   fr(", ", aBolds.readsBytes && aBolds.readsAvgPerByte, false);
1079   fr(v2, aBolds.readsAvgPerByte);
1080   nl(aBolds.readsTitle);
1081
1082   // "Writes".
1083   v1 = bytesAndPercAndRate(aT._writesBytes, gRoot._writesBytes);
1084   v2 = perByte(aT._writesAvgPerByte());
1085   fr("  Writes:    ", aBolds.writesTitle);
1086   fr(v1, aBolds.writesBytes);
1087   fr(", ", aBolds.writesBytes && aBolds.writesAvgPerByte, false);
1088   fr(v2, aBolds.writesAvgPerByte);
1089   nl(aBolds.writesTitle);
1090
1091   // "Accesses". We show 32 per line (but not on aggregate nodes).
1092   if (aT._accesses && aT._accesses.length > 0) {
1093     let v = "  Accesses: {";
1094     let prevN;
1095     for (let [i, n] of aT._accesses.entries()) {
1096       if ((i % 32) === 0) {
1097         fr(v);
1098         nl();
1099         v1 = i.toString().padStart(3, ' ');
1100         v = `    [${v1}]  `;
1101         v += `${accesses(n)} `;
1102       } else {
1103         // Use a ditto mark for repeats.
1104         v += (n === prevN && n !== 0) ? "〃 " : `${accesses(n)} `;
1105       }
1106       prevN = n;
1107     }
1108     fr(v);
1109     nl();
1110
1111     fr("  }");
1112     nl();
1113   }
1114
1115   // "Allocated at".
1116   fr("  Allocated at {", true, false);
1117   nl(true);
1118   if (aT._kind === kAgg) {
1119     // Don't print ancestor frames; just print the "insignificant" frame.
1120     let isInsigFrame = (aFrm) => aFrm.indexOf(" insignificant]") >= 0;
1121     assert(aT._frames.length === 1 && isInsigFrame(aT._frames[0]),
1122            "bad aggregate node");
1123     fr(`    ${aT._frames[0]}`, true, false);
1124     nl(true);
1125   } else {
1126     // Start numbering frames from #1, unless it's the root node, in which case
1127     // we show "#0: [root]".
1128     let i = (aT === gRoot) ? 0 : 1;
1129
1130     // Maybe show frames from ancestor nodes, excluding "[root]" (by starting
1131     // at j=1).
1132     for (let j = 1; j < aOldFrames.length; j++, i++) {
1133       fr(`    ^${i}: ${gData.ftbl[aOldFrames[j]]}`);
1134       nl(false);
1135     }
1136     // Show frames from this node.
1137     for (let j = 0; j < aT._frames.length; j++, i++) {
1138       fr(`    #${i}: ${gData.ftbl[aT._frames[j]]}`, true, false);
1139       nl(true);
1140     }
1141   }
1142   fr("  }", true, false);
1143   nl(true);
1144
1145   // End of node.
1146   fr(`}`, true, false);
1147   nl(true, true);
1148
1149   // Do the kids.
1150   if (kids) {
1151     assert(aT._kind !== kLeaf, "leaf node has children");
1152
1153     p = appendElement(aP, "span", "kids");
1154
1155     // tlFirstFor{Most,Last} are shorter than tlRestFor{Most,Last} to allow
1156     // space for the arrow.
1157     let tlFirstForMost;
1158     let tlRestForMost;
1159     if (kids.length > 1) {
1160       tlFirstForMost = aTlRest + "├─";
1161       tlRestForMost  = aTlRest + "│   ";
1162     }
1163     let tlFirstForLast = aTlRest + "└─";
1164     let tlRestForLast  = aTlRest + "    ";
1165
1166     for (let [i, kid] of kids.entries()) {
1167       let n = aT._frames.length;
1168       aOldFrames.push(...aT._frames); // append aT._frames to aOldFrames
1169       aNodeIdNums.push(i + 1);
1170       let isLast = i === kids.length - 1;
1171       appendTreeInner(kid, p, aBolds, aCmp, aPc, aSig, aNodeIdNums,
1172                       kids.length - 1, aOldFrames,
1173                       !isLast ? tlFirstForMost : tlFirstForLast,
1174                       !isLast ? tlRestForMost : tlRestForLast);
1175       aNodeIdNums.pop(i);
1176       aOldFrames.splice(-n);         // remove aT._frames from aOldFrames
1177     }
1178   }
1179 }
1180
1181 // Node significance.
1182 // - kSigSelf: the node itself is significant. It will be shown in full.
1183 // - kSigDesc: the node itself is insignificant, but it has one or more
1184 //   significant descendants. (This is not possible for the straightforward
1185 //   additive sort metrics like total-bytes, but it is possible for the
1186 //   non-additive ones like "Total (bytes), short-lived", "Total (bytes),
1187 //   low-access", etc.) It will be shown abbreviated.
1188 // - kSigNone: the node itself is insignificant, and it has no significant
1189 //   descendants. It will be aggregated.
1190 const kSigSelf = 3;
1191 const kSigDesc = 2;
1192 const kSigNone = 1;
1193
1194 // Fill in the ._sig field of all tree nodes.
1195 function sigTree(aT, aSig) {
1196   let sig = false;
1197   if (aT._kids) {
1198     for (let kid of aT._kids) {
1199       sig |= sigTree(kid, aSig);
1200     }
1201   }
1202
1203   if (aSig(aT)) {
1204     aT._sig = kSigSelf;
1205     return true;
1206   }
1207   if (sig) {
1208     aT._sig = kSigDesc;
1209     return true;
1210   }
1211   aT._sig = kSigNone;
1212   return false;
1213 }
1214
1215 function appendTree(aP, aBolds, aCmp, aPc, aSig) {
1216   sigTree(gRoot, aSig);
1217
1218   appendTreeInner(gRoot, aP, aBolds, aCmp, aPc, aSig, [1], 0, [], "", "  ");
1219 }
1220
1221 function appendSignificanceThreshold(aP, aSigLabel) {
1222   let v = `\nAP significance threshold: ${aSigLabel()}\n`;
1223   appendElementWithText(aP, "span", v, "threshold");
1224 }
1225
1226 // Check that aElem's class list contains at least one name from aClassNames.
1227 function classListContains(aElem, aClassNames) {
1228   for (let className of aClassNames) {
1229     if (aElem.classList.contains(className)) {
1230       return true;
1231     }
1232   }
1233   return false;
1234 }
1235
1236 function assertClassListContains(aElem, aClassNames) {
1237   assert(aElem, "undefined elem");
1238   assert(classListContains(aElem, aClassNames),
1239          `none of ${JSON.stringify(aClassNames)} found in class list`);
1240 }
1241
1242 // Called when a node with kids is clicked on.
1243 function toggleClass(aEvent) {
1244   let clickedNode = aEvent.target;
1245   let hasKidsNode;
1246   if (classListContains(clickedNode, ["expanded", "collapsed"])) {
1247     // The click must have been on a text node, so clickedNode is the node
1248     // to toggle.
1249     hasKidsNode = clickedNode;
1250   } else {
1251     // The click must have been on a span element, so the parent node is
1252     // the node to toggle.
1253     hasKidsNode = clickedNode.parentNode;
1254     assertClassListContains(hasKidsNode, ["expanded", "collapsed"]);
1255   }
1256   hasKidsNode.classList.toggle("expanded");
1257   hasKidsNode.classList.toggle("collapsed");
1258
1259   // Element order: 0: treeline span, 1: arrow span, ...
1260   let arrowSpan = hasKidsNode.childNodes[1];
1261   assertClassListContains(arrowSpan, ["arrow"]);
1262   if (arrowSpan.textContent === kHidingKidsArrow) {
1263     arrowSpan.textContent = kShowingKidsArrow;
1264   } else if (arrowSpan.textContent === kShowingKidsArrow) {
1265     arrowSpan.textContent = kHidingKidsArrow;
1266   } else {
1267     assert(false, `bad arrowSpan textContent`);
1268   }
1269
1270   // Toggle visibility of the span containing this node's kids.
1271   let kidsSpan = hasKidsNode.nextSibling;
1272   assertClassListContains(kidsSpan, ["kids"]);
1273   kidsSpan.classList.toggle("hidden");
1274 }
1275
1276 //------------------------------------------------------------//
1277 //--- Top-level stuff                                      ---//
1278 //------------------------------------------------------------//
1279
1280 // These arguments will be `undefined` when displayTree() is called without
1281 // having read a file (e.g. when redisplaying with a different sort metric).
1282 function displayTree(aTRead, aTParse, aTBuild) {
1283   let tRead = aTRead === undefined ? 0 : aTRead;
1284   let tParse = aTParse === undefined ? 0 : aTParse;
1285   let tBuild = aTBuild === undefined ? 0 : aTBuild;
1286
1287   // Get details relating to the chosen sort metrics.
1288   let data = gSelectData[gSelect.selectedIndex];
1289   let bolds = data.bolds;
1290   let label = data.label;
1291   let cmpField = data.cmpField;
1292   let sig = data.sig;
1293   let sigLabel = data.sigLabel;
1294   let cmp = (aT1, aT2) => {
1295     // Try the specified sort metric. If that doesn't distinguish them, sort by
1296     // _totalBytes.
1297     let s1 = aT2[cmpField] - aT1[cmpField];
1298     return (s1 !== 0) ? s1 : aT2._totalBytes - aT1._totalBytes;
1299   };
1300   let pc = (aT) => div(aT[cmpField], gRoot[cmpField]) * 100;
1301
1302   // Update the page title.
1303   document.title = `${kDocumentTitle} - ${gFilename} - ${label}`;
1304
1305   // Build the main part of the page.
1306   let now = performance.now();
1307   clearMainDiv();
1308   let pre = appendElement(gMainDiv, "pre");
1309   appendInvocationAndTimes(pre);
1310   appendTree(pre, bolds, cmp, pc, sig);
1311   appendSignificanceThreshold(pre, sigLabel);
1312   let tDisplay = performance.now() - now;
1313
1314   let tTotal = tRead + tParse + tBuild + tDisplay;
1315   clearTimingsDiv();
1316   let timings = `\
1317 Processing time: \
1318 read:${ms(aTRead)} + \
1319 parse:${ms(aTParse)} + \
1320 build:${ms(aTBuild)} + \
1321 display:${ms(tDisplay)} = \
1322 total:${ms(tTotal)}\
1323 `;
1324   appendElementWithText(gTimingsDiv, "p", timings);
1325 }
1326
1327 function loadFile() {
1328   clearMainDivWithText("Loading...");
1329
1330   let now = performance.now();
1331   let file = gInput.files[0];
1332   gFilename = file.name;
1333
1334   // Update the title. This will likely be overwritten very shortly, unless
1335   // there's a file loading problem, in which case it's nice to have the
1336   // correct filename in the title.
1337   document.title = `${kDocumentTitle} - ${gFilename}`;
1338
1339   let reader = new FileReader();
1340   reader.onload = function(aEvent) {
1341     tryFunc(() => {
1342       let tRead = performance.now() - now;
1343
1344       let data = aEvent.target.result;
1345
1346       now = performance.now();
1347       gData = JSON.parse(data);
1348       let tParse = performance.now() - now;
1349
1350       now = performance.now();
1351       buildTree();
1352       let tBuild = performance.now() - now;
1353
1354       displayTree(tRead, tParse, tBuild);
1355     });
1356   };
1357
1358   reader.onerror = function(aEvent) {
1359     clearMainDivWithText("Error loading file", "error");
1360   };
1361
1362   reader.readAsText(file);
1363 }
1364
1365 function changeSortMetric() {
1366   // If we have a tree, redisplay it for the new sort metric.
1367   if (gRoot) {
1368     tryFunc(() => {
1369       displayTree();
1370     });
1371   }
1372 }
1373
1374 // Top-level setup when the page is first loaded.
1375 function onLoad() {
1376   // Check if tests should be run.
1377   let params = new URLSearchParams(document.location.search.substring(1));
1378   let test = params.get("test");
1379
1380   // The header div.
1381   gHeaderDiv = appendElement(document.body, "div", "section");
1382
1383   // The (hidden) input element.
1384   let inputDiv = appendElement(gHeaderDiv, "div", "header");
1385   appendElementWithText(inputDiv, "div", "File");
1386   gInput = appendElement(inputDiv, "input", "hidden");
1387   gInput.type = "file";
1388   gInput.onchange = loadFile;
1389
1390   // The button that triggers the hidden input element.
1391   let b = appendElementWithText(inputDiv, "button", "Load…");
1392   b.onclick = () => gInput.click();
1393
1394   // The sort metric menu.
1395   let selectDiv = appendElement(gHeaderDiv, "div", "header");
1396   appendElementWithText(selectDiv, "div", "Sort metric");
1397   gSelect = appendElement(selectDiv, "select");
1398   gSelect.onchange = changeSortMetric;
1399   for (let [i, data] of gSelectData.entries()) {
1400     let option = appendElementWithText(gSelect, "option", data.label);
1401     option.value = i;
1402     if (data.isDefault) {
1403       option.selected = true;
1404     }
1405   }
1406
1407   // The testing div, if necessary.
1408   if (test) {
1409     gTestingDiv = appendElement(document.body, "div", "testing");
1410   }
1411
1412   // The main div.
1413   gMainDiv = appendElement(document.body, "div", "section");
1414   appendElementWithText(gMainDiv, "span", "Load a DHAT data file to begin");
1415
1416   // The legend div. We show it even before loading a file so that new users
1417   // are immediately aware that it exists.
1418   gLegendDiv = appendElement(document.body, "div", "legend noselect");
1419   let p = appendElementWithText(gLegendDiv, "p", "Legend:");
1420   let ul = appendElement(p, "ul");
1421   appendElementWithText(ul, "li", "'t-gmax': time of global heap maximum " +
1422                                   "(as measured in bytes)");
1423   appendElementWithText(ul, "li", "'t-end': time of program end");
1424   appendElementWithText(ul, "li", "'instrs': instructions");
1425   appendElementWithText(ul, "li", "'Minstr': mega-instruction, i.e. one " +
1426                                   "million instructions");
1427   appendElementWithText(ul, "li", "'AP': allocation point");
1428   appendElementWithText(ul, "li", "'avg': average");
1429   appendElementWithText(ul, "li", "'-' (in accesses): zero");
1430   appendElementWithText(ul, "li", "'∞' (in accesses): leaf AP counts max out " +
1431                                   "at 65534; larger counts are treated as " +
1432                                   "infinity");
1433   appendElementWithText(ul, "li", "'〃' (in accesses): same as previous entry");
1434
1435   // The timings div.
1436   gTimingsDiv = appendElement(document.body, "div", "timings noselect");
1437
1438   if (test) {
1439     appendElementWithText(gHeaderDiv, "div", "TEST MODE", "header");
1440     var script = document.createElement("script");
1441     script.src = "dh_test.js";
1442     document.body.appendChild(script);
1443   }
1444 }
1445