tools/binary_size/template/D3SymbolTreeMap.js

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // TODO:
   6 // 1. Visibility functions: base on boxPadding.t, not 15
   7 // 2. Track a maxDisplayDepth that is user-settable:
   8 //    maxDepth == currentRoot.depth + maxDisplayDepth
   9 function D3SymbolTreeMap(mapWidth, mapHeight, levelsToShow) {
  10   this._mapContainer = undefined;
  11   this._mapWidth = mapWidth;
  12   this._mapHeight = mapHeight;
  13   this.boxPadding = {'l': 5, 'r': 5, 't': 20, 'b': 5};
  14   this.infobox = undefined;
  15   this._maskContainer = undefined;
  16   this._highlightContainer = undefined;
  17   // Transition in this order:
  18   // 1. Exiting items go away.
  19   // 2. Updated items move.
  20   // 3. New items enter.
  21   this._exitDuration=500;
  22   this._updateDuration=500;
  23   this._enterDuration=500;
  24   this._firstTransition=true;
  25   this._layout = undefined;
  26   this._currentRoot = undefined;
  27   this._currentNodes = undefined;
  28   this._treeData = undefined;
  29   this._maxLevelsToShow = levelsToShow;
  30   this._currentMaxDepth = this._maxLevelsToShow;
  31 }
  32
  33 /**
  34  * Make a number pretty, with comma separators.
  35  */
  36 D3SymbolTreeMap._pretty = function(num) {
  37   var asString = String(num);
  38   var result = '';
  39   var counter = 0;
  40   for (var x = asString.length - 1; x >= 0; x--) {
  41     counter++;
  42     if (counter === 4) {
  43       result = ',' + result;
  44       counter = 1;
  45     }
  46     result = asString.charAt(x) + result;
  47   }
  48   return result;
  49 }
  50
  51 /**
  52  * Express a number in terms of KiB, MiB, GiB, etc.
  53  * Note that these are powers of 2, not of 10.
  54  */
  55 D3SymbolTreeMap._byteify = function(num) {
  56   var suffix;
  57   if (num >= 1024) {
  58     if (num >= 1024 * 1024 * 1024) {
  59       suffix = 'GiB';
  60       num = num / (1024 * 1024 * 1024);
  61     } else if (num >= 1024 * 1024) {
  62       suffix = 'MiB';
  63       num = num / (1024 * 1024);
  64     } else if (num >= 1024) {
  65       suffix = 'KiB'
  66       num = num / 1024;
  67     }
  68     return num.toFixed(2) + ' ' + suffix;
  69   }
  70   return num + ' B';
  71 }
  72
  73 D3SymbolTreeMap._NM_SYMBOL_TYPE_DESCRIPTIONS = {
  74   // Definitions concisely derived from the nm 'man' page
  75   'A': 'Global absolute (A)',
  76   'B': 'Global uninitialized data (B)',
  77   'b': 'Local uninitialized data (b)',
  78   'C': 'Global uninitialized common (C)',
  79   'D': 'Global initialized data (D)',
  80   'd': 'Local initialized data (d)',
  81   'G': 'Global small initialized data (G)',
  82   'g': 'Local small initialized data (g)',
  83   'i': 'Indirect function (i)',
  84   'N': 'Debugging (N)',
  85   'p': 'Stack unwind (p)',
  86   'R': 'Global read-only data (R)',
  87   'r': 'Local read-only data (r)',
  88   'S': 'Global small uninitialized data (S)',
  89   's': 'Local small uninitialized data (s)',
  90   'T': 'Global code (T)',
  91   't': 'Local code (t)',
  92   'U': 'Undefined (U)',
  93   'u': 'Unique (u)',
  94   'V': 'Global weak object (V)',
  95   'v': 'Local weak object (v)',
  96   'W': 'Global weak symbol (W)',
  97   'w': 'Local weak symbol (w)',
  98   '@': 'Vtable entry (@)', // non-standard, hack.
  99   '-': 'STABS debugging (-)',
 100   '?': 'Unrecognized (?)',
 101 };
 102 D3SymbolTreeMap._NM_SYMBOL_TYPES = '';
 103 for (var symbol_type in D3SymbolTreeMap._NM_SYMBOL_TYPE_DESCRIPTIONS) {
 104   D3SymbolTreeMap._NM_SYMBOL_TYPES += symbol_type;
 105 }
 106
 107 /**
 108  * Given a symbol type code, look up and return a human-readable description
 109  * of that symbol type. If the symbol type does not match one of the known
 110  * types, the unrecognized description (corresponding to symbol type '?') is
 111  * returned instead of null or undefined.
 112  */
 113 D3SymbolTreeMap._getSymbolDescription = function(type) {
 114   var result = D3SymbolTreeMap._NM_SYMBOL_TYPE_DESCRIPTIONS[type];
 115   if (result === undefined) {
 116     result = D3SymbolTreeMap._NM_SYMBOL_TYPE_DESCRIPTIONS['?'];
 117   }
 118   return result;
 119 }
 120
 121 // Qualitative 12-value pastel Brewer palette.
 122 D3SymbolTreeMap._colorArray = [
 123   'rgb(141,211,199)',
 124   'rgb(255,255,179)',
 125   'rgb(190,186,218)',
 126   'rgb(251,128,114)',
 127   'rgb(128,177,211)',
 128   'rgb(253,180,98)',
 129   'rgb(179,222,105)',
 130   'rgb(252,205,229)',
 131   'rgb(217,217,217)',
 132   'rgb(188,128,189)',
 133   'rgb(204,235,197)',
 134   'rgb(255,237,111)'];
 135
 136 D3SymbolTreeMap._initColorMap = function() {
 137   var map = {};
 138   var numColors = D3SymbolTreeMap._colorArray.length;
 139   var count = 0;
 140   for (var key in D3SymbolTreeMap._NM_SYMBOL_TYPE_DESCRIPTIONS) {
 141     var index = count++ % numColors;
 142     map[key] = d3.rgb(D3SymbolTreeMap._colorArray[index]);
 143   }
 144   D3SymbolTreeMap._colorMap = map;
 145 }
 146 D3SymbolTreeMap._initColorMap();
 147
 148 D3SymbolTreeMap.getColorForType = function(type) {
 149   var result = D3SymbolTreeMap._colorMap[type];
 150   if (result === undefined) return d3.rgb('rgb(255,255,255)');
 151   return result;
 152 }
 153
 154 D3SymbolTreeMap.prototype.init = function() {
 155   this.infobox = this._createInfoBox();
 156   this._mapContainer = d3.select('body').append('div')
 157       .style('position', 'relative')
 158       .style('width', this._mapWidth)
 159       .style('height', this._mapHeight)
 160       .style('padding', 0)
 161       .style('margin', 0)
 162       .style('box-shadow', '5px 5px 5px #888');
 163   this._layout = this._createTreeMapLayout();
 164   this._setData(tree_data); // TODO: Don't use global 'tree_data'
 165 }
 166
 167 /**
 168  * Sets the data displayed by the treemap and layint out the map.
 169  */
 170 D3SymbolTreeMap.prototype._setData = function(data) {
 171   this._treeData = data;
 172   console.time('_crunchStats');
 173   this._crunchStats(data);
 174   console.timeEnd('_crunchStats');
 175   this._currentRoot = this._treeData;
 176   this._currentNodes = this._layout.nodes(this._currentRoot);
 177   this._currentMaxDepth = this._maxLevelsToShow;
 178   this._doLayout();
 179 }
 180
 181 /**
 182  * Recursively traverses the entire tree starting from the specified node,
 183  * computing statistics and recording metadata as it goes. Call this method
 184  * only once per imported tree.
 185  */
 186 D3SymbolTreeMap.prototype._crunchStats = function(node) {
 187   var stack = [];
 188   stack.idCounter = 0;
 189   this._crunchStatsHelper(stack, node);
 190 }
 191
 192 /**
 193  * Invoke the specified visitor function on all data elements currently shown
 194  * in the treemap including any and all of their children, starting at the
 195  * currently-displayed root and descening recursively. The function will be
 196  * passed the datum element representing each node. No traversal guarantees
 197  * are made.
 198  */
 199 D3SymbolTreeMap.prototype.visitFromDisplayedRoot = function(visitor) {
 200   this._visit(this._currentRoot, visitor);
 201 }
 202
 203 /**
 204  * Helper function for visit functions.
 205  */
 206 D3SymbolTreeMap.prototype._visit = function(datum, visitor) {
 207   visitor.call(this, datum);
 208   if (datum.children) for (var i = 0; i < datum.children.length; i++) {
 209     this._visit(datum.children[i], visitor);
 210   }
 211 }
 212
 213 D3SymbolTreeMap.prototype._crunchStatsHelper = function(stack, node) {
 214   // Only overwrite the node ID if it isn't already set.
 215   // This allows stats to be crunched multiple times on subsets of data
 216   // without breaking the data-to-ID bindings. New nodes get new IDs.
 217   if (node.id === undefined) node.id = stack.idCounter++;
 218   if (node.children === undefined) {
 219     // Leaf node (symbol); accumulate stats.
 220     for (var i = 0; i < stack.length; i++) {
 221       var ancestor = stack[i];
 222       if (!ancestor.symbol_stats) ancestor.symbol_stats = {};
 223       if (ancestor.symbol_stats[node.t] === undefined) {
 224         // New symbol type we haven't seen before, just record.
 225         ancestor.symbol_stats[node.t] = {'count': 1,
 226                                          'size': node.value};
 227       } else {
 228         // Existing symbol type, increment.
 229         ancestor.symbol_stats[node.t].count++;
 230         ancestor.symbol_stats[node.t].size += node.value;
 231       }
 232     }
 233   } else for (var i = 0; i < node.children.length; i++) {
 234     stack.push(node);
 235     this._crunchStatsHelper(stack, node.children[i]);
 236     stack.pop();
 237   }
 238 }
 239
 240 D3SymbolTreeMap.prototype._createTreeMapLayout = function() {
 241   var result = d3.layout.treemap()
 242       .padding([this.boxPadding.t, this.boxPadding.r,
 243                 this.boxPadding.b, this.boxPadding.l])
 244       .size([this._mapWidth, this._mapHeight]);
 245   return result;
 246 }
 247
 248 D3SymbolTreeMap.prototype.resize = function(width, height) {
 249   this._mapWidth = width;
 250   this._mapHeight = height;
 251   this._mapContainer.style('width', width).style('height', height);
 252   this._layout.size([this._mapWidth, this._mapHeight]);
 253   this._currentNodes = this._layout.nodes(this._currentRoot);
 254   this._doLayout();
 255 }
 256
 257 D3SymbolTreeMap.prototype._zoomDatum = function(datum) {
 258   if (this._currentRoot === datum) return; // already here
 259   this._hideHighlight(datum);
 260   this._hideInfoBox(datum);
 261   this._currentRoot = datum;
 262   this._currentNodes = this._layout.nodes(this._currentRoot);
 263   this._currentMaxDepth = this._currentRoot.depth + this._maxLevelsToShow;
 264   console.log('zooming into datum ' + this._currentRoot.n);
 265   this._doLayout();
 266 }
 267
 268 D3SymbolTreeMap.prototype.setMaxLevels = function(levelsToShow) {
 269   this._maxLevelsToShow = levelsToShow;
 270   this._currentNodes = this._layout.nodes(this._currentRoot);
 271   this._currentMaxDepth = this._currentRoot.depth + this._maxLevelsToShow;
 272   console.log('setting max levels to show: ' + this._maxLevelsToShow);
 273   this._doLayout();
 274 }
 275
 276 /**
 277  * Clone the specified tree, returning an independent copy of the data.
 278  * Only the original attributes expected to exist prior to invoking
 279  * _crunchStatsHelper are retained, with the exception of the 'id' attribute
 280  * (which must be retained for proper transitions).
 281  * If the optional filter parameter is provided, it will be called with 'this'
 282  * set to this treemap instance and passed the 'datum' object as an argument.
 283  * When specified, the copy will retain only the data for which the filter
 284  * function returns true.
 285  */
 286 D3SymbolTreeMap.prototype._clone = function(datum, filter) {
 287   var trackingStats = false;
 288   if (this.__cloneState === undefined) {
 289     console.time('_clone');
 290     trackingStats = true;
 291     this.__cloneState = {'accepted': 0, 'rejected': 0,
 292                          'forced': 0, 'pruned': 0};
 293   }
 294
 295   // Must go depth-first. All parents of children that are accepted by the
 296   // filter must be preserved!
 297   var copy = {'n': datum.n, 'k': datum.k};
 298   var childAccepted = false;
 299   if (datum.children !== undefined) {
 300     for (var i = 0; i < datum.children.length; i++) {
 301       var copiedChild = this._clone(datum.children[i], filter);
 302       if (copiedChild !== undefined) {
 303         childAccepted = true; // parent must also be accepted.
 304         if (copy.children === undefined) copy.children = [];
 305         copy.children.push(copiedChild);
 306       }
 307     }
 308   }
 309
 310   // Ignore nodes that don't match the filter, when present.
 311   var accept = false;
 312   if (childAccepted) {
 313     // Parent of an accepted child must also be accepted.
 314     this.__cloneState.forced++;
 315     accept = true;
 316   } else if (filter !== undefined && filter.call(this, datum) !== true) {
 317     this.__cloneState.rejected++;
 318   } else if (datum.children === undefined) {
 319     // Accept leaf nodes that passed the filter
 320     this.__cloneState.accepted++;
 321     accept = true;
 322   } else {
 323     // Non-leaf node. If no children are accepted, prune it.
 324     this.__cloneState.pruned++;
 325   }
 326
 327   if (accept) {
 328     if (datum.id !== undefined) copy.id = datum.id;
 329     if (datum.lastPathElement !== undefined) {
 330       copy.lastPathElement = datum.lastPathElement;
 331     }
 332     if (datum.t !== undefined) copy.t = datum.t;
 333     if (datum.value !== undefined && datum.children === undefined) {
 334       copy.value = datum.value;
 335     }
 336   } else {
 337     // Discard the copy we were going to return
 338     copy = undefined;
 339   }
 340
 341   if (trackingStats === true) {
 342     // We are the fist call in the recursive chain.
 343     console.timeEnd('_clone');
 344     var totalAccepted = this.__cloneState.accepted +
 345                         this.__cloneState.forced;
 346     console.log(
 347         totalAccepted + ' nodes retained (' +
 348         this.__cloneState.forced + ' forced by accepted children, ' +
 349         this.__cloneState.accepted + ' accepted on their own merits), ' +
 350         this.__cloneState.rejected + ' nodes (and their children) ' +
 351                                      'filtered out,' +
 352         this.__cloneState.pruned + ' nodes pruned because because no ' +
 353                                    'children remained.');
 354     delete this.__cloneState;
 355   }
 356   return copy;
 357 }
 358
 359 D3SymbolTreeMap.prototype.filter = function(filter) {
 360   // Ensure we have a copy of the original root.
 361   if (this._backupTree === undefined) this._backupTree = this._treeData;
 362   this._mapContainer.selectAll('div').remove();
 363   this._setData(this._clone(this._backupTree, filter));
 364 }
 365
 366 D3SymbolTreeMap.prototype._doLayout = function() {
 367   console.time('_doLayout');
 368   this._handleInodes();
 369   this._handleLeaves();
 370   this._firstTransition = false;
 371   console.timeEnd('_doLayout');
 372 }
 373
 374 D3SymbolTreeMap.prototype._highlightElement = function(datum, selection) {
 375   this._showHighlight(datum, selection);
 376 }
 377
 378 D3SymbolTreeMap.prototype._unhighlightElement = function(datum, selection) {
 379   this._hideHighlight(datum, selection);
 380 }
 381
 382 D3SymbolTreeMap.prototype._handleInodes = function() {
 383   console.time('_handleInodes');
 384   var thisTreeMap = this;
 385   var inodes = this._currentNodes.filter(function(datum){
 386     return (datum.depth <= thisTreeMap._currentMaxDepth) &&
 387             datum.children !== undefined;
 388   });
 389   var cellsEnter = this._mapContainer.selectAll('div.inode')
 390       .data(inodes, function(datum) { return datum.id; })
 391       .enter()
 392       .append('div').attr('class', 'inode').attr('id', function(datum){
 393           return 'node-' + datum.id;});
 394
 395
 396   // Define enter/update/exit for inodes
 397   cellsEnter
 398       .append('div')
 399       .attr('class', 'rect inode_rect_entering')
 400       .style('z-index', function(datum) { return datum.id * 2; })
 401       .style('position', 'absolute')
 402       .style('left', function(datum) { return datum.x; })
 403       .style('top', function(datum){ return datum.y; })
 404       .style('width', function(datum){ return datum.dx; })
 405       .style('height', function(datum){ return datum.dy; })
 406       .style('opacity', '0')
 407       .style('border', '1px solid black')
 408       .style('background-image', function(datum) {
 409         return thisTreeMap._makeSymbolBucketBackgroundImage.call(
 410                thisTreeMap, datum);
 411       })
 412       .style('background-color', function(datum) {
 413         if (datum.t === undefined) return 'rgb(220,220,220)';
 414         return D3SymbolTreeMap.getColorForType(datum.t).toString();
 415       })
 416       .on('mouseover', function(datum){
 417         thisTreeMap._highlightElement.call(
 418             thisTreeMap, datum, d3.select(this));
 419         thisTreeMap._showInfoBox.call(thisTreeMap, datum);
 420       })
 421       .on('mouseout', function(datum){
 422         thisTreeMap._unhighlightElement.call(
 423             thisTreeMap, datum, d3.select(this));
 424         thisTreeMap._hideInfoBox.call(thisTreeMap, datum);
 425       })
 426       .on('mousemove', function(){
 427           thisTreeMap._moveInfoBox.call(thisTreeMap, event);
 428       })
 429       .on('dblclick', function(datum){
 430         if (datum !== thisTreeMap._currentRoot) {
 431           // Zoom into the selection
 432           thisTreeMap._zoomDatum(datum);
 433         } else if (datum.parent) {
 434           console.log('event.shiftKey=' + event.shiftKey);
 435           if (event.shiftKey === true) {
 436             // Back to root
 437             thisTreeMap._zoomDatum(thisTreeMap._treeData);
 438           } else {
 439             // Zoom out of the selection
 440             thisTreeMap._zoomDatum(datum.parent);
 441           }
 442         }
 443       });
 444   cellsEnter
 445       .append('div')
 446       .attr('class', 'label inode_label_entering')
 447       .style('z-index', function(datum) { return (datum.id * 2) + 1; })
 448       .style('position', 'absolute')
 449       .style('left', function(datum){ return datum.x; })
 450       .style('top', function(datum){ return datum.y; })
 451       .style('width', function(datum) { return datum.dx; })
 452       .style('height', function(datum) { return thisTreeMap.boxPadding.t; })
 453       .style('opacity', '0')
 454       .style('pointer-events', 'none')
 455       .style('-webkit-user-select', 'none')
 456       .style('overflow', 'hidden') // required for ellipsis
 457       .style('white-space', 'nowrap') // required for ellipsis
 458       .style('text-overflow', 'ellipsis')
 459       .style('text-align', 'center')
 460       .style('vertical-align', 'top')
 461       .style('visibility', function(datum) {
 462         return (datum.dx < 15 || datum.dy < 15) ? 'hidden' : 'visible';
 463       })
 464       .text(function(datum) {
 465         var sizeish = ' [' + D3SymbolTreeMap._byteify(datum.value) + ']'
 466         var text;
 467         if (datum.k === 'b') { // bucket
 468           if (datum === thisTreeMap._currentRoot) {
 469             text = thisTreeMap.pathFor(datum) + ': '
 470                 + D3SymbolTreeMap._getSymbolDescription(datum.t)
 471           } else {
 472             text = D3SymbolTreeMap._getSymbolDescription(datum.t);
 473           }
 474         } else if (datum === thisTreeMap._currentRoot) {
 475           // The top-most level should always show the complete path
 476           text = thisTreeMap.pathFor(datum);
 477         } else {
 478           // Anything that isn't a bucket or a leaf (symbol) or the
 479           // current root should just show its name.
 480           text = datum.n;
 481         }
 482         return text + sizeish;
 483       }
 484   );
 485
 486   // Complicated transition logic:
 487   // For nodes that are entering, we want to fade them in in-place AFTER
 488   // any adjusting nodes have resized and moved around. That way, new nodes
 489   // seamlessly appear in the right spot after their containers have resized
 490   // and moved around.
 491   // To do this we do some trickery:
 492   // 1. Define a '_entering' class on the entering elements
 493   // 2. Use this to select only the entering elements and apply the opacity
 494   //    transition.
 495   // 3. Use the same transition to drop the '_entering' suffix, so that they
 496   //    will correctly update in later zoom/resize/whatever operations.
 497   // 4. The update transition is achieved by selecting the elements without
 498   //    the '_entering_' suffix and applying movement and resizing transition
 499   //    effects.
 500   this._mapContainer.selectAll('div.inode_rect_entering').transition()
 501       .duration(thisTreeMap._enterDuration).delay(
 502           this._firstTransition ? 0 : thisTreeMap._exitDuration +
 503               thisTreeMap._updateDuration)
 504       .attr('class', 'rect inode_rect')
 505       .style('opacity', '1')
 506   this._mapContainer.selectAll('div.inode_label_entering').transition()
 507       .duration(thisTreeMap._enterDuration).delay(
 508           this._firstTransition ? 0 : thisTreeMap._exitDuration +
 509               thisTreeMap._updateDuration)
 510       .attr('class', 'label inode_label')
 511       .style('opacity', '1')
 512   this._mapContainer.selectAll('div.inode_rect').transition()
 513       .duration(thisTreeMap._updateDuration).delay(thisTreeMap._exitDuration)
 514       .style('opacity', '1')
 515       .style('background-image', function(datum) {
 516         return thisTreeMap._makeSymbolBucketBackgroundImage.call(
 517             thisTreeMap, datum);
 518       })
 519       .style('left', function(datum) { return datum.x; })
 520       .style('top', function(datum){ return datum.y; })
 521       .style('width', function(datum){ return datum.dx; })
 522       .style('height', function(datum){ return datum.dy; });
 523   this._mapContainer.selectAll('div.inode_label').transition()
 524       .duration(thisTreeMap._updateDuration).delay(thisTreeMap._exitDuration)
 525       .style('opacity', '1')
 526       .style('visibility', function(datum) {
 527         return (datum.dx < 15 || datum.dy < 15) ? 'hidden' : 'visible';
 528       })
 529       .style('left', function(datum){ return datum.x; })
 530       .style('top', function(datum){ return datum.y; })
 531       .style('width', function(datum) { return datum.dx; })
 532       .style('height', function(datum) { return thisTreeMap.boxPadding.t; })
 533       .text(function(datum) {
 534         var sizeish = ' [' + D3SymbolTreeMap._byteify(datum.value) + ']'
 535         var text;
 536         if (datum.k === 'b') {
 537           if (datum === thisTreeMap._currentRoot) {
 538             text = thisTreeMap.pathFor(datum) + ': ' +
 539                 D3SymbolTreeMap._getSymbolDescription(datum.t)
 540           } else {
 541             text = D3SymbolTreeMap._getSymbolDescription(datum.t);
 542           }
 543         } else if (datum === thisTreeMap._currentRoot) {
 544           // The top-most level should always show the complete path
 545           text = thisTreeMap.pathFor(datum);
 546         } else {
 547           // Anything that isn't a bucket or a leaf (symbol) or the
 548           // current root should just show its name.
 549           text = datum.n;
 550         }
 551         return text + sizeish;
 552       });
 553   var exit = this._mapContainer.selectAll('div.inode')
 554       .data(inodes, function(datum) { return 'inode-' + datum.id; })
 555       .exit();
 556   exit.selectAll('div.inode_rect').transition().duration(
 557       thisTreeMap._exitDuration).style('opacity', 0);
 558   exit.selectAll('div.inode_label').transition().duration(
 559       thisTreeMap._exitDuration).style('opacity', 0);
 560   exit.transition().delay(thisTreeMap._exitDuration + 1).remove();
 561
 562   console.log(inodes.length + ' inodes layed out.');
 563   console.timeEnd('_handleInodes');
 564 }
 565
 566 D3SymbolTreeMap.prototype._handleLeaves = function() {
 567   console.time('_handleLeaves');
 568   var color_fn = d3.scale.category10();
 569   var thisTreeMap = this;
 570   var leaves = this._currentNodes.filter(function(datum){
 571     return (datum.depth <= thisTreeMap._currentMaxDepth) &&
 572         datum.children === undefined; });
 573   var cellsEnter = this._mapContainer.selectAll('div.leaf')
 574       .data(leaves, function(datum) { return datum.id; })
 575       .enter()
 576       .append('div').attr('class', 'leaf').attr('id', function(datum){
 577         return 'node-' + datum.id;
 578       });
 579
 580   // Define enter/update/exit for leaves
 581   cellsEnter
 582       .append('div')
 583       .attr('class', 'rect leaf_rect_entering')
 584       .style('z-index', function(datum) { return datum.id * 2; })
 585       .style('position', 'absolute')
 586       .style('left', function(datum){ return datum.x; })
 587       .style('top', function(datum){ return datum.y; })
 588       .style('width', function(datum){ return datum.dx; })
 589       .style('height', function(datum){ return datum.dy; })
 590       .style('opacity', '0')
 591       .style('background-color', function(datum) {
 592         if (datum.t === undefined) return 'rgb(220,220,220)';
 593         return D3SymbolTreeMap.getColorForType(datum.t)
 594             .darker(0.3).toString();
 595       })
 596       .style('border', '1px solid black')
 597       .on('mouseover', function(datum){
 598         thisTreeMap._highlightElement.call(
 599             thisTreeMap, datum, d3.select(this));
 600         thisTreeMap._showInfoBox.call(thisTreeMap, datum);
 601       })
 602       .on('mouseout', function(datum){
 603         thisTreeMap._unhighlightElement.call(
 604             thisTreeMap, datum, d3.select(this));
 605         thisTreeMap._hideInfoBox.call(thisTreeMap, datum);
 606       })
 607       .on('mousemove', function(){ thisTreeMap._moveInfoBox.call(
 608         thisTreeMap, event);
 609       });
 610   cellsEnter
 611       .append('div')
 612       .attr('class', 'label leaf_label_entering')
 613       .style('z-index', function(datum) { return (datum.id * 2) + 1; })
 614       .style('position', 'absolute')
 615       .style('left', function(datum){ return datum.x; })
 616       .style('top', function(datum){ return datum.y; })
 617       .style('width', function(datum) { return datum.dx; })
 618       .style('height', function(datum) { return datum.dy; })
 619       .style('opacity', '0')
 620       .style('pointer-events', 'none')
 621       .style('-webkit-user-select', 'none')
 622       .style('overflow', 'hidden') // required for ellipsis
 623       .style('white-space', 'nowrap') // required for ellipsis
 624       .style('text-overflow', 'ellipsis')
 625       .style('text-align', 'center')
 626       .style('vertical-align', 'middle')
 627       .style('visibility', function(datum) {
 628         return (datum.dx < 15 || datum.dy < 15) ? 'hidden' : 'visible';
 629       })
 630       .text(function(datum) { return datum.n; });
 631
 632   // Complicated transition logic: See note in _handleInodes()
 633   this._mapContainer.selectAll('div.leaf_rect_entering').transition()
 634       .duration(thisTreeMap._enterDuration).delay(
 635           this._firstTransition ? 0 : thisTreeMap._exitDuration +
 636               thisTreeMap._updateDuration)
 637       .attr('class', 'rect leaf_rect')
 638       .style('opacity', '1')
 639   this._mapContainer.selectAll('div.leaf_label_entering').transition()
 640       .duration(thisTreeMap._enterDuration).delay(
 641           this._firstTransition ? 0 : thisTreeMap._exitDuration +
 642               thisTreeMap._updateDuration)
 643       .attr('class', 'label leaf_label')
 644       .style('opacity', '1')
 645   this._mapContainer.selectAll('div.leaf_rect').transition()
 646       .duration(thisTreeMap._updateDuration).delay(thisTreeMap._exitDuration)
 647       .style('opacity', '1')
 648       .style('left', function(datum){ return datum.x; })
 649       .style('top', function(datum){ return datum.y; })
 650       .style('width', function(datum){ return datum.dx; })
 651       .style('height', function(datum){ return datum.dy; });
 652   this._mapContainer.selectAll('div.leaf_label').transition()
 653       .duration(thisTreeMap._updateDuration).delay(thisTreeMap._exitDuration)
 654       .style('opacity', '1')
 655       .style('visibility', function(datum) {
 656           return (datum.dx < 15 || datum.dy < 15) ? 'hidden' : 'visible';
 657       })
 658       .style('left', function(datum){ return datum.x; })
 659       .style('top', function(datum){ return datum.y; })
 660       .style('width', function(datum) { return datum.dx; })
 661       .style('height', function(datum) { return datum.dy; });
 662   var exit = this._mapContainer.selectAll('div.leaf')
 663       .data(leaves, function(datum) { return 'leaf-' + datum.id; })
 664       .exit();
 665   exit.selectAll('div.leaf_rect').transition()
 666       .duration(thisTreeMap._exitDuration)
 667       .style('opacity', 0);
 668   exit.selectAll('div.leaf_label').transition()
 669       .duration(thisTreeMap._exitDuration)
 670       .style('opacity', 0);
 671   exit.transition().delay(thisTreeMap._exitDuration + 1).remove();
 672
 673   console.log(leaves.length + ' leaves layed out.');
 674   console.timeEnd('_handleLeaves');
 675 }
 676
 677 D3SymbolTreeMap.prototype._makeSymbolBucketBackgroundImage = function(datum) {
 678   if (!(datum.t === undefined && datum.depth == this._currentMaxDepth)) {
 679     return 'none';
 680   }
 681   var text = '';
 682   var lastStop = 0;
 683   for (var x = 0; x < D3SymbolTreeMap._NM_SYMBOL_TYPES.length; x++) {
 684     symbol_type = D3SymbolTreeMap._NM_SYMBOL_TYPES.charAt(x);
 685     var stats = datum.symbol_stats[symbol_type];
 686     if (stats !== undefined) {
 687       if (text.length !== 0) {
 688         text += ', ';
 689       }
 690       var percent = 100 * (stats.size / datum.value);
 691       var nowStop = lastStop + percent;
 692       var tempcolor = D3SymbolTreeMap.getColorForType(symbol_type);
 693       var color = d3.rgb(tempcolor).toString();
 694       text += color + ' ' + lastStop + '%, ' + color + ' ' +
 695           nowStop + '%';
 696       lastStop = nowStop;
 697     }
 698   }
 699   return 'linear-gradient(' + (datum.dx > datum.dy ? 'to right' :
 700                                'to bottom') + ', ' + text + ')';
 701 }
 702
 703 D3SymbolTreeMap.prototype.pathFor = function(datum) {
 704   if (datum.__path) return datum.__path;
 705   parts=[];
 706   node = datum;
 707   while (node) {
 708     if (node.k === 'p') { // path node
 709       if(node.n !== '/') parts.unshift(node.n);
 710     }
 711     node = node.parent;
 712   }
 713   datum.__path = '/' + parts.join('/');
 714   return datum.__path;
 715 }
 716
 717 D3SymbolTreeMap.prototype._createHighlight = function(datum, selection) {
 718   var x = parseInt(selection.style('left'));
 719   var y = parseInt(selection.style('top'));
 720   var w = parseInt(selection.style('width'));
 721   var h = parseInt(selection.style('height'));
 722   datum.highlight = this._mapContainer.append('div')
 723       .attr('id', 'h-' + datum.id)
 724       .attr('class', 'highlight')
 725       .style('pointer-events', 'none')
 726       .style('-webkit-user-select', 'none')
 727       .style('z-index', '999999')
 728       .style('position', 'absolute')
 729       .style('top', y-2)
 730       .style('left', x-2)
 731       .style('width', w+4)
 732       .style('height', h+4)
 733       .style('margin', 0)
 734       .style('padding', 0)
 735       .style('border', '4px outset rgba(250,40,200,0.9)')
 736       .style('box-sizing', 'border-box')
 737       .style('opacity', 0.0);
 738 }
 739
 740 D3SymbolTreeMap.prototype._showHighlight = function(datum, selection) {
 741   if (datum === this._currentRoot) return;
 742   if (datum.highlight === undefined) {
 743     this._createHighlight(datum, selection);
 744   }
 745   datum.highlight.transition().duration(200).style('opacity', 1.0);
 746 }
 747
 748 D3SymbolTreeMap.prototype._hideHighlight = function(datum, selection) {
 749   if (datum.highlight === undefined) return;
 750   datum.highlight.transition().duration(750)
 751       .style('opacity', 0)
 752       .each('end', function(){
 753         if (datum.highlight) datum.highlight.remove();
 754         delete datum.highlight;
 755       });
 756 }
 757
 758 D3SymbolTreeMap.prototype._createInfoBox = function() {
 759   return d3.select('body')
 760       .append('div')
 761       .attr('id', 'infobox')
 762       .style('z-index', '2147483647') // (2^31) - 1: Hopefully safe :)
 763       .style('position', 'absolute')
 764       .style('visibility', 'hidden')
 765       .style('background-color', 'rgba(255,255,255, 0.9)')
 766       .style('border', '1px solid black')
 767       .style('padding', '10px')
 768       .style('-webkit-user-select', 'none')
 769       .style('box-shadow', '3px 3px rgba(70,70,70,0.5)')
 770       .style('border-radius', '10px')
 771       .style('white-space', 'nowrap');
 772 }
 773
 774 D3SymbolTreeMap.prototype._showInfoBox = function(datum) {
 775   this.infobox.text('');
 776   var numSymbols = 0;
 777   var sizeish = D3SymbolTreeMap._pretty(datum.value) + ' bytes (' +
 778       D3SymbolTreeMap._byteify(datum.value) + ')';
 779   if (datum.k === 'p' || datum.k === 'b') { // path or bucket
 780     if (datum.symbol_stats) { // can be empty if filters are applied
 781       for (var x = 0; x < D3SymbolTreeMap._NM_SYMBOL_TYPES.length; x++) {
 782         symbol_type = D3SymbolTreeMap._NM_SYMBOL_TYPES.charAt(x);
 783         var stats = datum.symbol_stats[symbol_type];
 784         if (stats !== undefined) numSymbols += stats.count;
 785       }
 786     }
 787   } else if (datum.k === 's') { // symbol
 788     numSymbols = 1;
 789   }
 790
 791   if (datum.k === 'p' && !datum.lastPathElement) {
 792     this.infobox.append('div').text('Directory: ' + this.pathFor(datum))
 793     this.infobox.append('div').text('Size: ' + sizeish);
 794   } else {
 795     if (datum.k === 'p') { // path
 796       this.infobox.append('div').text('File: ' + this.pathFor(datum))
 797       this.infobox.append('div').text('Size: ' + sizeish);
 798     } else if (datum.k === 'b') { // bucket
 799       this.infobox.append('div').text('Symbol Bucket: ' +
 800           D3SymbolTreeMap._getSymbolDescription(datum.t));
 801       this.infobox.append('div').text('Count: ' + numSymbols);
 802       this.infobox.append('div').text('Size: ' + sizeish);
 803       this.infobox.append('div').text('Location: ' + this.pathFor(datum))
 804     } else if (datum.k === 's') { // symbol
 805       this.infobox.append('div').text('Symbol: ' + datum.n);
 806       this.infobox.append('div').text('Type: ' +
 807           D3SymbolTreeMap._getSymbolDescription(datum.t));
 808       this.infobox.append('div').text('Size: ' + sizeish);
 809       this.infobox.append('div').text('Location: ' + this.pathFor(datum))
 810     }
 811   }
 812   if (datum.k === 'p') {
 813     this.infobox.append('div')
 814         .text('Number of symbols: ' + D3SymbolTreeMap._pretty(numSymbols));
 815     if (datum.symbol_stats) { // can be empty if filters are applied
 816       var table = this.infobox.append('table')
 817           .attr('border', 1).append('tbody');
 818       var header = table.append('tr');
 819       header.append('th').text('Type');
 820       header.append('th').text('Count');
 821       header.append('th')
 822           .style('white-space', 'nowrap')
 823           .text('Total Size (Bytes)');
 824       for (var x = 0; x < D3SymbolTreeMap._NM_SYMBOL_TYPES.length; x++) {
 825         symbol_type = D3SymbolTreeMap._NM_SYMBOL_TYPES.charAt(x);
 826         var stats = datum.symbol_stats[symbol_type];
 827         if (stats !== undefined) {
 828           var tr = table.append('tr');
 829           tr.append('td')
 830               .style('white-space', 'nowrap')
 831               .text(D3SymbolTreeMap._getSymbolDescription(
 832                   symbol_type));
 833           tr.append('td').text(D3SymbolTreeMap._pretty(stats.count));
 834           tr.append('td').text(D3SymbolTreeMap._pretty(stats.size));
 835         }
 836       }
 837     }
 838   }
 839   this.infobox.style('visibility', 'visible');
 840 }
 841
 842 D3SymbolTreeMap.prototype._hideInfoBox = function(datum) {
 843   this.infobox.style('visibility', 'hidden');
 844 }
 845
 846 D3SymbolTreeMap.prototype._moveInfoBox = function(event) {
 847   var element = document.getElementById('infobox');
 848   var w = element.offsetWidth;
 849   var h = element.offsetHeight;
 850   var offsetLeft = 10;
 851   var offsetTop = 10;
 852
 853   var rightLimit = window.innerWidth;
 854   var rightEdge = event.pageX + offsetLeft + w;
 855   if (rightEdge > rightLimit) {
 856     // Too close to screen edge, reflect around the cursor
 857     offsetLeft = -1 * (w + offsetLeft);
 858   }
 859
 860   var bottomLimit = window.innerHeight;
 861   var bottomEdge = event.pageY + offsetTop + h;
 862   if (bottomEdge > bottomLimit) {
 863     // Too close ot screen edge, reflect around the cursor
 864     offsetTop = -1 * (h + offsetTop);
 865   }
 866
 867   this.infobox.style('top', (event.pageY + offsetTop) + 'px')
 868       .style('left', (event.pageX + offsetLeft) + 'px');
 869 }
 870
 871 D3SymbolTreeMap.prototype.biggestSymbols = function(maxRecords) {
 872   var result = undefined;
 873   var smallest = undefined;
 874   var sortFunction = function(a,b) {
 875     var result = b.value - a.value;
 876     if (result !== 0) return result; // sort by size
 877     var pathA = treemap.pathFor(a); // sort by path
 878     var pathB = treemap.pathFor(b);
 879     if (pathA > pathB) return 1;
 880     if (pathB > pathA) return -1;
 881     return a.n - b.n; // sort by symbol name
 882   };
 883   this.visitFromDisplayedRoot(function(datum) {
 884     if (datum.children) return; // ignore non-leaves
 885     if (!result) { // first element
 886       result = [datum];
 887       smallest = datum.value;
 888       return;
 889     }
 890     if (result.length < maxRecords) { // filling the array
 891       result.push(datum);
 892       return;
 893     }
 894     if (datum.value > smallest) { // array is already full
 895       result.push(datum);
 896       result.sort(sortFunction);
 897       result.pop(); // get rid of smallest element
 898       smallest = result[maxRecords - 1].value; // new threshold for entry
 899     }
 900   });
 901   result.sort(sortFunction);
 902   return result;
 903 }
 904
 905 D3SymbolTreeMap.prototype.biggestPaths = function(maxRecords) {
 906   var result = undefined;
 907   var smallest = undefined;
 908   var sortFunction = function(a,b) {
 909     var result = b.value - a.value;
 910     if (result !== 0) return result; // sort by size
 911     var pathA = treemap.pathFor(a); // sort by path
 912     var pathB = treemap.pathFor(b);
 913     if (pathA > pathB) return 1;
 914     if (pathB > pathA) return -1;
 915     console.log('warning, multiple entries for the same path: ' + pathA);
 916     return 0; // should be impossible
 917   };
 918   this.visitFromDisplayedRoot(function(datum) {
 919     if (!datum.lastPathElement) return; // ignore non-files
 920     if (!result) { // first element
 921       result = [datum];
 922       smallest = datum.value;
 923       return;
 924     }
 925     if (result.length < maxRecords) { // filling the array
 926       result.push(datum);
 927       return;
 928     }
 929     if (datum.value > smallest) { // array is already full
 930       result.push(datum);
 931       result.sort(sortFunction);
 932       result.pop(); // get rid of smallest element
 933       smallest = result[maxRecords - 1].value; // new threshold for entry
 934     }
 935   });
 936   result.sort(sortFunction);
 937   return result;
 938 }