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