1<!DOCTYPE html>
2<!--
3Copyright (c) 2015 The Chromium Authors. All rights reserved.
4Use of this source code is governed by a BSD-style license that can be
5found in the LICENSE file.
6-->
7
8<link rel="import" href="/tracing/base/iteration_helpers.html">
9<link rel="import" href="/tracing/base/range.html">
10<link rel="import" href="/tracing/model/memory_allocator_dump.html">
11<link rel="import"
12    href="/tracing/ui/analysis/memory_dump_heap_details_pane.html">
13<link rel="import" href="/tracing/ui/analysis/memory_dump_sub_view_util.html">
14<link rel="import" href="/tracing/ui/analysis/stacked_pane.html">
15<link rel="import" href="/tracing/ui/base/dom_helpers.html">
16<link rel="import" href="/tracing/ui/base/table.html">
17<link rel="import" href="/tracing/value/unit.html">
18
19<polymer-element name="tr-ui-a-memory-dump-allocator-details-pane"
20    extends="tr-ui-a-stacked-pane">
21  <template>
22    <style>
23      :host {
24        display: flex;
25        flex-direction: column;
26      }
27
28      #label {
29        flex: 0 0 auto;
30        padding: 8px;
31
32        background-color: #eee;
33        border-bottom: 1px solid #8e8e8e;
34        border-top: 1px solid white;
35
36        font-size:  15px;
37        font-weight: bold;
38      }
39
40      #contents {
41        flex: 1 0 auto;
42        align-self: stretch;
43        font-size: 12px;
44      }
45
46      #info_text {
47        padding: 8px;
48        color: #666;
49        font-style: italic;
50        text-align: center;
51      }
52
53      #table {
54        display: none;  /* Hide until memory allocator dumps are set. */
55        flex: 1 0 auto;
56        align-self: stretch;
57      }
58    </style>
59    <div id="label">Component details</div>
60    <div id="contents">
61      <div id="info_text">No memory allocator dump selected</div>
62      <tr-ui-b-table id="table"></tr-ui-b-table>
63    </div>
64  </template>
65</polymer-element>
66<script>
67'use strict';
68
69tr.exportTo('tr.ui.analysis', function() {
70
71  // Constant representing the context in suballocation rows.
72  var SUBALLOCATION_CONTEXT = true;
73
74  // Size numeric info types.
75  var MemoryAllocatorDumpInfoType = tr.model.MemoryAllocatorDumpInfoType;
76  var PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN =
77      MemoryAllocatorDumpInfoType.PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN;
78  var PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER =
79      MemoryAllocatorDumpInfoType.PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER;
80
81  // Unicode symbols used for memory cell info icons and messages.
82  var LEFTWARDS_OPEN_HEADED_ARROW = String.fromCharCode(0x21FD);
83  var RIGHTWARDS_OPEN_HEADED_ARROW = String.fromCharCode(0x21FE);
84  var EN_DASH = String.fromCharCode(0x2013);
85  var CIRCLED_LATIN_SMALL_LETTER_I = String.fromCharCode(0x24D8);
86
87  /** @constructor */
88  function AllocatorDumpNameColumn() {
89    tr.ui.analysis.TitleColumn.call(this, 'Component');
90  }
91
92  AllocatorDumpNameColumn.prototype = {
93    __proto__: tr.ui.analysis.TitleColumn.prototype,
94
95    formatTitle: function(row) {
96      if (!row.suballocation)
97        return row.title;
98      return tr.ui.b.createSpan({
99        textContent: row.title,
100        italic: true,
101        tooltip: row.fullNames === undefined ?
102            undefined : row.fullNames.join(', ')
103      });
104    }
105  };
106
107  /**
108   * Retrieve the entry associated with a given name from a map and increment
109   * its count.
110   *
111   * If there is no entry associated with the name, a new entry is created, the
112   * creation callback is called, the entry's count is incremented (from 0 to
113   * 1) and the newly created entry is returned.
114   */
115  function getAndUpdateEntry(map, name, createdCallback) {
116    var entry = map.get(name);
117    if (entry === undefined) {
118      entry = {count: 0};
119      createdCallback(entry);
120      map.set(name, entry);
121    }
122    entry.count++;
123    return entry;
124  }
125
126  /**
127   * Helper class for building size and effective size column info messages.
128   *
129   * @constructor
130   */
131  function SizeInfoMessageBuilder() {
132    this.parts_ = [];
133    this.indent_ = 0;
134  }
135
136  SizeInfoMessageBuilder.prototype = {
137    append: function(/* arguments */) {
138      this.parts_.push.apply(
139          this.parts_, Array.prototype.slice.apply(arguments));
140    },
141
142    /**
143     * Append the entries of a map to the message according to the following
144     * rules:
145     *
146     *   1. If the map is empty, append emptyText to the message (if provided).
147     *      Examples:
148     *
149     *                       emptyText=undefined
150     *        Hello, World! ====================> Hello, World!
151     *
152     *                        emptyText='empty'
153     *        The bottle is ====================> The bottle is empty
154     *
155     *   2. If the map contains a single entry, append a space and call
156     *      itemCallback on the entry (which is in turn expected to append a
157     *      message for the entry). Example:
158     *
159     *        Please do not ====================> Please do not [item-message]
160     *
161     *   3. If the map contains multiple entries, append them as a list
162     *      with itemCallback called on each entry. If hasPluralSuffix is true,
163     *      's' will be appended to the message before the list. Examples:
164     *
165     *                      hasPluralSuffix=false
166     *        I need to buy ====================> I need to buy:
167     *                                             - [item1-message]
168     *                                             - [item2-message]
169     *                                             [...]
170     *                                             - [itemN-message]
171     *
172     *                      hasPluralSuffix=true
173     *        Suspected CL  ====================> Suspected CLs:
174     *                                             - [item1-message]
175     *                                             - [item2-message]
176     *                                             [...]
177     *                                             - [itemN-message]
178     */
179    appendMap: function(
180        map, hasPluralSuffix, emptyText, itemCallback, opt_this) {
181      opt_this = opt_this || this;
182      if (map.size === 0) {
183        if (emptyText)
184          this.append(emptyText);
185      } else if (map.size === 1) {
186        this.parts_.push(' ');
187        var key = map.keys().next().value;
188        itemCallback.call(opt_this, key, map.get(key));
189      } else {
190        if (hasPluralSuffix)
191          this.parts_.push('s');
192        this.parts_.push(':');
193        this.indent_++;
194        for (var key of map.keys()) {
195          this.parts_.push('\n', ' '.repeat(3 * (this.indent_ - 1)), ' - ');
196          itemCallback.call(opt_this, key, map.get(key));
197        }
198        this.indent_--;
199      }
200    },
201
202    appendImportanceRange: function(range) {
203      this.append(' (importance: ');
204      if (range.min === range.max)
205        this.append(range.min);
206      else
207        this.append(range.min, EN_DASH, range.max);
208      this.append(')');
209    },
210
211    appendSizeIfDefined: function(size) {
212      if (size !== undefined)
213        this.append(' (', tr.v.Unit.byName.sizeInBytes.format(size), ')');
214    },
215
216    appendSomeTimestampsQuantifier: function() {
217      this.append(
218          ' ', tr.ui.analysis.MemoryColumn.SOME_TIMESTAMPS_INFO_QUANTIFIER);
219    },
220
221    build: function() {
222      return this.parts_.join('');
223    }
224  };
225
226  /** @constructor */
227  function EffectiveSizeColumn(name, cellPath, aggregationMode) {
228    tr.ui.analysis.NumericMemoryColumn.call(
229        this, name, cellPath, aggregationMode);
230  }
231
232  EffectiveSizeColumn.prototype = {
233    __proto__: tr.ui.analysis.NumericMemoryColumn.prototype,
234
235    addInfos: function(numerics, memoryAllocatorDumps, infos) {
236      if (memoryAllocatorDumps === undefined)
237        return;
238
239      // Quantified name of an owner dump (of the given dump) -> {count,
240      // importanceRange}.
241      var ownerNameToEntry = new Map();
242
243      // Quantified name of an owned dump (by the given dump) -> {count,
244      // importanceRange, sharerNameToEntry}, where sharerNameToEntry is a map
245      // from quantified names of other owners of the owned dump to {count,
246      // importanceRange}.
247      var ownedNameToEntry = new Map();
248
249      for (var i = 0; i < numerics.length; i++) {
250        if (numerics[i] === undefined)
251          continue;
252        var dump = memoryAllocatorDumps[i];
253        if (dump === SUBALLOCATION_CONTEXT)
254          return;  // No ownership of suballocation internal rows.
255
256        // Gather owners of this dump.
257        dump.ownedBy.forEach(function(ownerLink) {
258          var ownerDump = ownerLink.source;
259          this.getAndUpdateOwnershipEntry_(
260              ownerNameToEntry, ownerDump, ownerLink);
261        }, this);
262
263        // Gather dumps owned by this dump and other owner dumps sharing them
264        // (with this dump).
265        var ownedLink = dump.owns;
266        if (ownedLink !== undefined) {
267          var ownedDump = ownedLink.target;
268          var ownedEntry = this.getAndUpdateOwnershipEntry_(ownedNameToEntry,
269              ownedDump, ownedLink, true /* opt_withSharerNameToEntry */);
270          var sharerNameToEntry = ownedEntry.sharerNameToEntry;
271          ownedDump.ownedBy.forEach(function(sharerLink) {
272            var sharerDump = sharerLink.source;
273            if (sharerDump === dump)
274              return;
275            this.getAndUpdateOwnershipEntry_(
276                sharerNameToEntry, sharerDump, sharerLink);
277          }, this);
278        }
279      }
280
281      // Emit a single info listing all owners of this dump.
282      if (ownerNameToEntry.size > 0) {
283        var messageBuilder = new SizeInfoMessageBuilder();
284        messageBuilder.append('shared by');
285        messageBuilder.appendMap(
286            ownerNameToEntry,
287            false /* hasPluralSuffix */,
288            undefined /* emptyText */,
289            function(ownerName, ownerEntry) {
290              messageBuilder.append(ownerName);
291              if (ownerEntry.count < numerics.length)
292                messageBuilder.appendSomeTimestampsQuantifier();
293              messageBuilder.appendImportanceRange(ownerEntry.importanceRange);
294            }, this);
295        infos.push({
296          message: messageBuilder.build(),
297          icon: LEFTWARDS_OPEN_HEADED_ARROW,
298          color: 'green'
299        });
300      }
301
302      // Emit a single info listing all dumps owned by this dump together
303      // with list(s) of other owner dumps sharing them with this dump.
304      if (ownedNameToEntry.size > 0) {
305        var messageBuilder = new SizeInfoMessageBuilder();
306        messageBuilder.append('shares');
307        messageBuilder.appendMap(
308            ownedNameToEntry,
309            false /* hasPluralSuffix */,
310            undefined /* emptyText */,
311            function(ownedName, ownedEntry) {
312              messageBuilder.append(ownedName);
313              var ownedCount = ownedEntry.count;
314              if (ownedCount < numerics.length)
315                messageBuilder.appendSomeTimestampsQuantifier();
316              messageBuilder.appendImportanceRange(ownedEntry.importanceRange);
317            messageBuilder.append(' with');
318            messageBuilder.appendMap(
319                ownedEntry.sharerNameToEntry,
320                false /* hasPluralSuffix */,
321                ' no other dumps',
322                function(sharerName, sharerEntry) {
323                  messageBuilder.append(sharerName);
324                  if (sharerEntry.count < ownedCount)
325                    messageBuilder.appendSomeTimestampsQuantifier();
326                  messageBuilder.appendImportanceRange(
327                      sharerEntry.importanceRange);
328                }, this);
329            }, this);
330        infos.push({
331          message: messageBuilder.build(),
332          icon: RIGHTWARDS_OPEN_HEADED_ARROW,
333          color: 'green'
334        });
335      }
336    },
337
338    getAndUpdateOwnershipEntry_: function(
339        map, dump, link, opt_withSharerNameToEntry) {
340      var entry = getAndUpdateEntry(map, dump.quantifiedName,
341          function(newEntry) {
342            newEntry.importanceRange = new tr.b.Range();
343            if (opt_withSharerNameToEntry)
344              newEntry.sharerNameToEntry = new Map();
345          });
346      entry.importanceRange.addValue(link.importance || 0);
347      return entry;
348    }
349  };
350
351  /** @constructor */
352  function SizeColumn(name, cellPath, aggregationMode) {
353    tr.ui.analysis.NumericMemoryColumn.call(
354        this, name, cellPath, aggregationMode);
355  }
356
357  SizeColumn.prototype = {
358    __proto__: tr.ui.analysis.NumericMemoryColumn.prototype,
359
360    addInfos: function(numerics, memoryAllocatorDumps, infos) {
361      if (memoryAllocatorDumps === undefined)
362        return;
363      this.addOverlapInfo_(numerics, memoryAllocatorDumps, infos);
364      this.addProvidedSizeWarningInfos_(numerics, memoryAllocatorDumps, infos);
365    },
366
367    addOverlapInfo_: function(numerics, memoryAllocatorDumps, infos) {
368      // Sibling allocator dump name -> {count, size}. The latter field (size)
369      // is omitted in multi-selection mode.
370      var siblingNameToEntry = new Map();
371      for (var i = 0; i < numerics.length; i++) {
372        if (numerics[i] === undefined)
373          continue;
374        var dump = memoryAllocatorDumps[i];
375        if (dump === SUBALLOCATION_CONTEXT)
376          return;  // No ownership of suballocation internal rows.
377        var ownedBySiblingSizes = dump.ownedBySiblingSizes;
378        for (var siblingDump of ownedBySiblingSizes.keys()) {
379          var siblingName = siblingDump.name;
380          getAndUpdateEntry(siblingNameToEntry, siblingName,
381              function(newEntry) {
382                if (numerics.length === 1 /* single-selection mode */)
383                  newEntry.size = ownedBySiblingSizes.get(siblingDump);
384              });
385        }
386      }
387
388      // Emit a single info describing all overlaps with siblings (if
389      // applicable).
390      if (siblingNameToEntry.size > 0) {
391        var messageBuilder = new SizeInfoMessageBuilder();
392        messageBuilder.append('overlaps with its sibling');
393        messageBuilder.appendMap(
394            siblingNameToEntry,
395            true /* hasPluralSuffix */,
396            undefined /* emptyText */,
397            function(siblingName, siblingEntry) {
398              messageBuilder.append('\'', siblingName, '\'');
399              messageBuilder.appendSizeIfDefined(siblingEntry.size);
400              if (siblingEntry.count < numerics.length)
401                messageBuilder.appendSomeTimestampsQuantifier();
402            }, this);
403        infos.push({
404          message: messageBuilder.build(),
405          icon: CIRCLED_LATIN_SMALL_LETTER_I,
406          color: 'blue'
407        });
408      }
409    },
410
411    addProvidedSizeWarningInfos_: function(numerics, memoryAllocatorDumps,
412        infos) {
413      // Info type (see MemoryAllocatorDumpInfoType) -> {count, providedSize,
414      // dependencySize}. The latter two fields (providedSize and
415      // dependencySize) are omitted in multi-selection mode.
416      var infoTypeToEntry = new Map();
417      for (var i = 0; i < numerics.length; i++) {
418        if (numerics[i] === undefined)
419          continue;
420        var dump = memoryAllocatorDumps[i];
421        if (dump === SUBALLOCATION_CONTEXT)
422          return;  // Suballocation internal rows have no provided size.
423        dump.infos.forEach(function(dumpInfo) {
424          getAndUpdateEntry(infoTypeToEntry, dumpInfo.type, function(newEntry) {
425            if (numerics.length === 1 /* single-selection mode */) {
426              newEntry.providedSize = dumpInfo.providedSize;
427              newEntry.dependencySize = dumpInfo.dependencySize;
428            }
429          });
430        });
431      }
432
433      // Emit a warning info for every info type.
434      for (var infoType of infoTypeToEntry.keys()) {
435        var entry = infoTypeToEntry.get(infoType);
436        var messageBuilder = new SizeInfoMessageBuilder();
437        messageBuilder.append('provided size');
438        messageBuilder.appendSizeIfDefined(entry.providedSize);
439        var dependencyName;
440        switch (infoType) {
441          case PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN:
442            dependencyName = 'the aggregated size of the children';
443            break;
444          case PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER:
445            dependencyName = 'the size of the largest owner';
446            break;
447          default:
448            dependencyName = 'an unknown dependency';
449            break;
450        }
451        messageBuilder.append(' was less than ', dependencyName);
452        messageBuilder.appendSizeIfDefined(entry.dependencySize);
453        if (entry.count < numerics.length)
454          messageBuilder.appendSomeTimestampsQuantifier();
455        infos.push(tr.ui.analysis.createWarningInfo(messageBuilder.build()));
456      }
457    }
458  };
459
460  var NUMERIC_COLUMN_RULES = [
461    {
462      condition: tr.model.MemoryAllocatorDump.EFFECTIVE_SIZE_NUMERIC_NAME,
463      importance: 10,
464      columnConstructor: EffectiveSizeColumn
465    },
466    {
467      condition: tr.model.MemoryAllocatorDump.SIZE_NUMERIC_NAME,
468      importance: 9,
469      columnConstructor: SizeColumn
470    },
471    {
472      condition: 'page_size',
473      importance: 0,
474      columnConstructor: tr.ui.analysis.NumericMemoryColumn
475    },
476    {
477      condition: /size/,
478      importance: 5,
479      columnConstructor: tr.ui.analysis.NumericMemoryColumn
480    },
481    {
482      // All other columns.
483      importance: 0,
484      columnConstructor: tr.ui.analysis.NumericMemoryColumn
485    }
486  ];
487
488  var DIAGNOSTIC_COLUMN_RULES = [
489    {
490      importance: 0,
491      columnConstructor: tr.ui.analysis.StringMemoryColumn
492    }
493  ];
494
495  Polymer('tr-ui-a-memory-dump-allocator-details-pane', {
496    created: function() {
497      this.memoryAllocatorDumps_ = undefined;
498      this.heapDumps_ = undefined;
499      this.aggregationMode_ = undefined;
500    },
501
502    ready: function() {
503      this.$.table.selectionMode = tr.ui.b.TableFormat.SelectionMode.ROW;
504    },
505
506    /**
507     * Sets the memory allocator dumps and schedules rebuilding the pane.
508     *
509     * The provided value should be a chronological list of memory allocator
510     * dumps. All dumps are assumed to belong to the same process and have
511     * the same full name. Example:
512     *
513     *   [
514     *     tr.model.MemoryAllocatorDump {},  // MAD at timestamp 1.
515     *     undefined,  // MAD not provided at timestamp 2.
516     *     tr.model.MemoryAllocatorDump {},  // MAD at timestamp 3.
517     *   ]
518     */
519    set memoryAllocatorDumps(memoryAllocatorDumps) {
520      this.memoryAllocatorDumps_ = memoryAllocatorDumps;
521      this.scheduleRebuildPane_();
522    },
523
524    get memoryAllocatorDumps() {
525      return this.memoryAllocatorDumps_;
526    },
527
528    // TODO(petrcermak): Don't plumb the heap dumps through the allocator
529    // details pane. Maybe add support for multiple child panes to stacked pane
530    // (view) instead.
531    set heapDumps(heapDumps) {
532      this.heapDumps_ = heapDumps;
533      this.scheduleRebuildPane_();
534    },
535
536    set aggregationMode(aggregationMode) {
537      this.aggregationMode_ = aggregationMode;
538      this.scheduleRebuildPane_();
539    },
540
541    get aggregationMode() {
542      return this.aggregationMode_;
543    },
544
545    rebuildPane_: function() {
546      if (this.memoryAllocatorDumps_ === undefined ||
547          this.memoryAllocatorDumps_.length === 0) {
548        // Show the info text (hide the table).
549        this.$.info_text.style.display = 'block';
550        this.$.table.style.display = 'none';
551
552        this.$.table.clear();
553        this.$.table.rebuild();
554
555        // Hide the heap details pane (if applicable).
556        this.childPaneBuilder = undefined;
557        return;
558      }
559
560      // Show the table (hide the info text).
561      this.$.info_text.style.display = 'none';
562      this.$.table.style.display = 'block';
563
564      var rows = this.createRows_();
565      var columns = this.createColumns_(rows);
566      rows.forEach(function(rootRow) {
567        tr.ui.analysis.aggregateTableRowCellsRecursively(rootRow, columns,
568            function(contexts) {
569              // Only aggregate suballocation rows (numerics of regular rows
570              // corresponding to MADs have already been aggregated by the
571              // model in MemoryAllocatorDump.aggregateNumericsRecursively).
572              return contexts !== undefined && contexts.some(function(context) {
573                return context === SUBALLOCATION_CONTEXT;
574              });
575            });
576      });
577
578      this.$.table.tableRows = rows;
579      this.$.table.tableColumns = columns;
580      this.$.table.rebuild();
581      tr.ui.analysis.expandTableRowsRecursively(this.$.table);
582
583      // Show/hide the heap details pane.
584      if (this.heapDumps_ === undefined) {
585        this.childPaneBuilder = undefined;
586      } else {
587        this.childPaneBuilder = function() {
588          var pane =
589              document.createElement('tr-ui-a-memory-dump-heap-details-pane');
590          pane.heapDumps = this.heapDumps_;
591          pane.aggregationMode = this.aggregationMode_;
592          return pane;
593        }.bind(this);
594      }
595    },
596
597    createRows_: function() {
598      return [
599        this.createAllocatorRowRecursively_(this.memoryAllocatorDumps_)
600      ];
601    },
602
603    createAllocatorRowRecursively_: function(dumps) {
604      // Get the name of the memory allocator dumps. We can use any defined
605      // dump in dumps since they all have the same name.
606      var definedDump = tr.b.findFirstInArray(dumps);
607      var title = definedDump.name;
608      var fullName = definedDump.fullName;
609
610      // Transform a chronological list of memory allocator dumps into two
611      // dictionaries of cells (where each cell contains a chronological list
612      // of the values of one of its numerics or diagnostics).
613      var numericCells = tr.ui.analysis.createCells(dumps, function(dump) {
614        return dump.numerics;
615      });
616      var diagnosticCells = tr.ui.analysis.createCells(dumps, function(dump) {
617        return dump.diagnostics;
618      });
619
620      // Determine whether the memory allocator dump is a suballocation. A
621      // dump is assumed to be a suballocation if (1) its name starts with
622      // two underscores, (2) it has an owner from within the same process at
623      // some timestamp, and (3) it is undefined, has no owners, or has the
624      // same owner (and no other owners) at all other timestamps.
625      var suballocatedBy = undefined;
626      if (title.startsWith('__')) {
627        for (var i = 0; i < dumps.length; i++) {
628          var dump = dumps[i];
629          if (dump === undefined || dump.ownedBy.length === 0) {
630            // Ignore timestamps where the dump is undefined or doesn't
631            // have any owner.
632            continue;
633          }
634          var ownerDump = dump.ownedBy[0].source;
635          if (dump.ownedBy.length > 1 ||
636              dump.children.length > 0 ||
637              ownerDump.containerMemoryDump !== dump.containerMemoryDump) {
638            // If the dump has (1) any children, (2) multiple owners, or
639            // (3) its owner is in a different process (otherwise, the
640            // modified title would be ambiguous), then it's not considered
641            // to be a suballocation.
642            suballocatedBy = undefined;
643            break;
644          }
645          if (suballocatedBy === undefined) {
646            suballocatedBy = ownerDump.fullName;
647          } else if (suballocatedBy !== ownerDump.fullName) {
648            // The full name of the owner dump changed over time, so this
649            // dump is not a suballocation.
650            suballocatedBy = undefined;
651            break;
652          }
653        }
654      }
655
656      var row = {
657        title: title,
658        fullNames: [fullName],
659        contexts: dumps,
660        numericCells: numericCells,
661        diagnosticCells: diagnosticCells,
662        suballocatedBy: suballocatedBy
663      };
664
665      // Child memory dump name (dict key) -> Timestamp (list index) ->
666      // Child dump.
667      var childDumpNameToDumps = tr.b.invertArrayOfDicts(dumps,
668          function(dump) {
669            return tr.b.arrayToDict(dump.children, function(child) {
670              return child.name;
671            });
672          });
673
674      // Recursively create sub-rows for children (if applicable).
675      var subRows = [];
676      var suballocationClassificationRootNode = undefined;
677      tr.b.iterItems(childDumpNameToDumps, function(childName, childDumps) {
678        var childRow = this.createAllocatorRowRecursively_(childDumps);
679        if (childRow.suballocatedBy === undefined) {
680          // Not a suballocation row: just append it.
681          subRows.push(childRow);
682        } else {
683          // Suballocation row: classify it in a tree of suballocations.
684          suballocationClassificationRootNode =
685              this.classifySuballocationRow_(
686                  childRow, suballocationClassificationRootNode);
687        }
688      }, this);
689
690      // Build the tree of suballocations (if applicable).
691      if (suballocationClassificationRootNode !== undefined) {
692        var suballocationRow = this.createSuballocationRowRecursively_(
693            'suballocations', suballocationClassificationRootNode);
694        subRows.push(suballocationRow);
695      }
696
697      if (subRows.length > 0)
698        row.subRows = subRows;
699
700      return row;
701    },
702
703    classifySuballocationRow_: function(suballocationRow, rootNode) {
704      if (rootNode === undefined) {
705        rootNode = {
706          children: {},
707          row: undefined
708        };
709      }
710
711      var suballocationLevels = suballocationRow.suballocatedBy.split('/');
712      var currentNode = rootNode;
713      for (var i = 0; i < suballocationLevels.length; i++) {
714        var suballocationLevel = suballocationLevels[i];
715        var nextNode = currentNode.children[suballocationLevel];
716        if (nextNode === undefined) {
717          currentNode.children[suballocationLevel] = nextNode = {
718            children: {},
719            row: undefined
720          };
721        }
722        var currentNode = nextNode;
723      }
724
725      var existingRow = currentNode.row;
726      if (existingRow !== undefined) {
727        // On rare occasions it can happen that one dump (e.g. sqlite) owns
728        // different suballocations at different timestamps (e.g.
729        // malloc/allocated_objects/_7d35 and malloc/allocated_objects/_511e).
730        // When this happens, we merge the two suballocations into a single row
731        // (malloc/allocated_objects/suballocations/sqlite).
732        for (var i = 0; i < suballocationRow.contexts.length; i++) {
733          var newContext = suballocationRow.contexts[i];
734          if (newContext === undefined)
735            continue;
736
737          if (existingRow.contexts[i] !== undefined)
738            throw new Error('Multiple suballocations with the same owner name');
739
740          existingRow.contexts[i] = newContext;
741          ['numericCells', 'diagnosticCells'].forEach(function(cellKey) {
742            var suballocationCells = suballocationRow[cellKey];
743            if (suballocationCells === undefined)
744              return;
745            tr.b.iterItems(suballocationCells, function(cellName, cell) {
746              if (cell === undefined)
747                return;
748              var fields = cell.fields;
749              if (fields === undefined)
750                return;
751              var field = fields[i];
752              if (field === undefined)
753                return;
754              var existingCells = existingRow[cellKey];
755              if (existingCells === undefined) {
756                existingCells = {};
757                existingRow[cellKey] = existingCells;
758              }
759              var existingCell = existingCells[cellName];
760              if (existingCell === undefined) {
761                existingCell = new tr.ui.analysis.MemoryCell(
762                    new Array(fields.length));
763                existingCells[cellName] = existingCell;
764              }
765              existingCell.fields[i] = field;
766            });
767          });
768        }
769        existingRow.fullNames.push.apply(
770            existingRow.fullNames, suballocationRow.fullNames);
771      } else {
772        currentNode.row = suballocationRow;
773      }
774
775      return rootNode;
776    },
777
778    createSuballocationRowRecursively_: function(name, node) {
779      var childCount = Object.keys(node.children).length;
780      if (childCount === 0) {
781        if (node.row === undefined)
782          throw new Error('Suballocation node must have a row or children');
783        // Leaf row of the suballocation tree: Change the row's title from
784        // '__MEANINGLESSHASH' to the name of the suballocation owner.
785        var row = node.row;
786        row.title = name;
787        row.suballocation = true;
788        return row;
789      }
790
791      // Internal row of the suballocation tree: Recursively create its
792      // sub-rows.
793      var subRows = tr.b.dictionaryValues(tr.b.mapItems(
794          node.children, this.createSuballocationRowRecursively_, this));
795
796      if (node.row !== undefined) {
797        // Very unlikely case: Both an ancestor (e.g. 'skia') and one of its
798        // descendants (e.g. 'skia/sk_glyph_cache') both suballocate from the
799        // same MemoryAllocatorDump (e.g. 'malloc/allocated_objects'). In
800        // this case, the suballocation from the ancestor must be mapped to
801        // 'malloc/allocated_objects/suballocations/skia/<unspecified>' so
802        // that 'malloc/allocated_objects/suballocations/skia' could
803        // aggregate the numerics of the two suballocations properly.
804        var row = node.row;
805        row.title = '<unspecified>';
806        row.suballocation = true;
807        subRows.unshift(row);
808      }
809
810      // An internal row of the suballocation tree is assumed to be defined
811      // at a given timestamp if at least one of its sub-rows is defined at
812      // the timestamp.
813      var contexts = new Array(subRows[0].contexts.length);
814      for (var i = 0; i < subRows.length; i++) {
815        subRows[i].contexts.forEach(function(subContext, index) {
816          if (subContext !== undefined)
817            contexts[index] = SUBALLOCATION_CONTEXT;
818        });
819      }
820
821      return {
822        title: name,
823        suballocation: true,
824        contexts: contexts,
825        subRows: subRows
826      };
827    },
828
829    createColumns_: function(rows) {
830      var titleColumn = new AllocatorDumpNameColumn();
831      titleColumn.width = '200px';
832
833      var numericColumns = tr.ui.analysis.MemoryColumn.fromRows(
834          rows, 'numericCells', this.aggregationMode_, NUMERIC_COLUMN_RULES);
835      var diagnosticColumns = tr.ui.analysis.MemoryColumn.fromRows(
836          rows, 'diagnosticCells', this.aggregationMode_,
837          DIAGNOSTIC_COLUMN_RULES);
838      var fieldColumns = numericColumns.concat(diagnosticColumns);
839      tr.ui.analysis.MemoryColumn.spaceEqually(fieldColumns);
840
841      var columns = [titleColumn].concat(fieldColumns);
842      return columns;
843    }
844  });
845
846  return {
847    // All exports are for testing only.
848    SUBALLOCATION_CONTEXT: SUBALLOCATION_CONTEXT,
849    AllocatorDumpNameColumn: AllocatorDumpNameColumn,
850    EffectiveSizeColumn: EffectiveSizeColumn,
851    SizeColumn: SizeColumn
852  };
853});
854</script>
855