<!DOCTYPE html>
<!--
Copyright (c) 2015 The Chromium Authors. All rights reserved.
Use of this source code is governed by a BSD-style license that can be
found in the LICENSE file.
-->

<link rel="import" href="/tracing/base/iteration_helpers.html">
<link rel="import" href="/tracing/base/range.html">
<link rel="import" href="/tracing/model/memory_allocator_dump.html">
<link rel="import"
    href="/tracing/ui/analysis/memory_dump_heap_details_pane.html">
<link rel="import" href="/tracing/ui/analysis/memory_dump_sub_view_util.html">
<link rel="import" href="/tracing/ui/analysis/stacked_pane.html">
<link rel="import" href="/tracing/ui/base/dom_helpers.html">
<link rel="import" href="/tracing/ui/base/table.html">
<link rel="import" href="/tracing/value/unit.html">

<polymer-element name="tr-ui-a-memory-dump-allocator-details-pane"
    extends="tr-ui-a-stacked-pane">
  <template>
    <style>
      :host {
        display: flex;
        flex-direction: column;
      }

      #label {
        flex: 0 0 auto;
        padding: 8px;

        background-color: #eee;
        border-bottom: 1px solid #8e8e8e;
        border-top: 1px solid white;

        font-size:  15px;
        font-weight: bold;
      }

      #contents {
        flex: 1 0 auto;
        align-self: stretch;
        font-size: 12px;
      }

      #info_text {
        padding: 8px;
        color: #666;
        font-style: italic;
        text-align: center;
      }

      #table {
        display: none;  /* Hide until memory allocator dumps are set. */
        flex: 1 0 auto;
        align-self: stretch;
      }
    </style>
    <div id="label">Component details</div>
    <div id="contents">
      <div id="info_text">No memory allocator dump selected</div>
      <tr-ui-b-table id="table"></tr-ui-b-table>
    </div>
  </template>
</polymer-element>
<script>
'use strict';

tr.exportTo('tr.ui.analysis', function() {

  // Constant representing the context in suballocation rows.
  var SUBALLOCATION_CONTEXT = true;

  // Size numeric info types.
  var MemoryAllocatorDumpInfoType = tr.model.MemoryAllocatorDumpInfoType;
  var PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN =
      MemoryAllocatorDumpInfoType.PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN;
  var PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER =
      MemoryAllocatorDumpInfoType.PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER;

  // Unicode symbols used for memory cell info icons and messages.
  var LEFTWARDS_OPEN_HEADED_ARROW = String.fromCharCode(0x21FD);
  var RIGHTWARDS_OPEN_HEADED_ARROW = String.fromCharCode(0x21FE);
  var EN_DASH = String.fromCharCode(0x2013);
  var CIRCLED_LATIN_SMALL_LETTER_I = String.fromCharCode(0x24D8);

  /** @constructor */
  function AllocatorDumpNameColumn() {
    tr.ui.analysis.TitleColumn.call(this, 'Component');
  }

  AllocatorDumpNameColumn.prototype = {
    __proto__: tr.ui.analysis.TitleColumn.prototype,

    formatTitle: function(row) {
      if (!row.suballocation)
        return row.title;
      return tr.ui.b.createSpan({
        textContent: row.title,
        italic: true,
        tooltip: row.fullNames === undefined ?
            undefined : row.fullNames.join(', ')
      });
    }
  };

  /**
   * Retrieve the entry associated with a given name from a map and increment
   * its count.
   *
   * If there is no entry associated with the name, a new entry is created, the
   * creation callback is called, the entry's count is incremented (from 0 to
   * 1) and the newly created entry is returned.
   */
  function getAndUpdateEntry(map, name, createdCallback) {
    var entry = map.get(name);
    if (entry === undefined) {
      entry = {count: 0};
      createdCallback(entry);
      map.set(name, entry);
    }
    entry.count++;
    return entry;
  }

  /**
   * Helper class for building size and effective size column info messages.
   *
   * @constructor
   */
  function SizeInfoMessageBuilder() {
    this.parts_ = [];
    this.indent_ = 0;
  }

  SizeInfoMessageBuilder.prototype = {
    append: function(/* arguments */) {
      this.parts_.push.apply(
          this.parts_, Array.prototype.slice.apply(arguments));
    },

    /**
     * Append the entries of a map to the message according to the following
     * rules:
     *
     *   1. If the map is empty, append emptyText to the message (if provided).
     *      Examples:
     *
     *                       emptyText=undefined
     *        Hello, World! ====================> Hello, World!
     *
     *                        emptyText='empty'
     *        The bottle is ====================> The bottle is empty
     *
     *   2. If the map contains a single entry, append a space and call
     *      itemCallback on the entry (which is in turn expected to append a
     *      message for the entry). Example:
     *
     *        Please do not ====================> Please do not [item-message]
     *
     *   3. If the map contains multiple entries, append them as a list
     *      with itemCallback called on each entry. If hasPluralSuffix is true,
     *      's' will be appended to the message before the list. Examples:
     *
     *                      hasPluralSuffix=false
     *        I need to buy ====================> I need to buy:
     *                                             - [item1-message]
     *                                             - [item2-message]
     *                                             [...]
     *                                             - [itemN-message]
     *
     *                      hasPluralSuffix=true
     *        Suspected CL  ====================> Suspected CLs:
     *                                             - [item1-message]
     *                                             - [item2-message]
     *                                             [...]
     *                                             - [itemN-message]
     */
    appendMap: function(
        map, hasPluralSuffix, emptyText, itemCallback, opt_this) {
      opt_this = opt_this || this;
      if (map.size === 0) {
        if (emptyText)
          this.append(emptyText);
      } else if (map.size === 1) {
        this.parts_.push(' ');
        var key = map.keys().next().value;
        itemCallback.call(opt_this, key, map.get(key));
      } else {
        if (hasPluralSuffix)
          this.parts_.push('s');
        this.parts_.push(':');
        this.indent_++;
        for (var key of map.keys()) {
          this.parts_.push('\n', ' '.repeat(3 * (this.indent_ - 1)), ' - ');
          itemCallback.call(opt_this, key, map.get(key));
        }
        this.indent_--;
      }
    },

    appendImportanceRange: function(range) {
      this.append(' (importance: ');
      if (range.min === range.max)
        this.append(range.min);
      else
        this.append(range.min, EN_DASH, range.max);
      this.append(')');
    },

    appendSizeIfDefined: function(size) {
      if (size !== undefined)
        this.append(' (', tr.v.Unit.byName.sizeInBytes.format(size), ')');
    },

    appendSomeTimestampsQuantifier: function() {
      this.append(
          ' ', tr.ui.analysis.MemoryColumn.SOME_TIMESTAMPS_INFO_QUANTIFIER);
    },

    build: function() {
      return this.parts_.join('');
    }
  };

  /** @constructor */
  function EffectiveSizeColumn(name, cellPath, aggregationMode) {
    tr.ui.analysis.NumericMemoryColumn.call(
        this, name, cellPath, aggregationMode);
  }

  EffectiveSizeColumn.prototype = {
    __proto__: tr.ui.analysis.NumericMemoryColumn.prototype,

    addInfos: function(numerics, memoryAllocatorDumps, infos) {
      if (memoryAllocatorDumps === undefined)
        return;

      // Quantified name of an owner dump (of the given dump) -> {count,
      // importanceRange}.
      var ownerNameToEntry = new Map();

      // Quantified name of an owned dump (by the given dump) -> {count,
      // importanceRange, sharerNameToEntry}, where sharerNameToEntry is a map
      // from quantified names of other owners of the owned dump to {count,
      // importanceRange}.
      var ownedNameToEntry = new Map();

      for (var i = 0; i < numerics.length; i++) {
        if (numerics[i] === undefined)
          continue;
        var dump = memoryAllocatorDumps[i];
        if (dump === SUBALLOCATION_CONTEXT)
          return;  // No ownership of suballocation internal rows.

        // Gather owners of this dump.
        dump.ownedBy.forEach(function(ownerLink) {
          var ownerDump = ownerLink.source;
          this.getAndUpdateOwnershipEntry_(
              ownerNameToEntry, ownerDump, ownerLink);
        }, this);

        // Gather dumps owned by this dump and other owner dumps sharing them
        // (with this dump).
        var ownedLink = dump.owns;
        if (ownedLink !== undefined) {
          var ownedDump = ownedLink.target;
          var ownedEntry = this.getAndUpdateOwnershipEntry_(ownedNameToEntry,
              ownedDump, ownedLink, true /* opt_withSharerNameToEntry */);
          var sharerNameToEntry = ownedEntry.sharerNameToEntry;
          ownedDump.ownedBy.forEach(function(sharerLink) {
            var sharerDump = sharerLink.source;
            if (sharerDump === dump)
              return;
            this.getAndUpdateOwnershipEntry_(
                sharerNameToEntry, sharerDump, sharerLink);
          }, this);
        }
      }

      // Emit a single info listing all owners of this dump.
      if (ownerNameToEntry.size > 0) {
        var messageBuilder = new SizeInfoMessageBuilder();
        messageBuilder.append('shared by');
        messageBuilder.appendMap(
            ownerNameToEntry,
            false /* hasPluralSuffix */,
            undefined /* emptyText */,
            function(ownerName, ownerEntry) {
              messageBuilder.append(ownerName);
              if (ownerEntry.count < numerics.length)
                messageBuilder.appendSomeTimestampsQuantifier();
              messageBuilder.appendImportanceRange(ownerEntry.importanceRange);
            }, this);
        infos.push({
          message: messageBuilder.build(),
          icon: LEFTWARDS_OPEN_HEADED_ARROW,
          color: 'green'
        });
      }

      // Emit a single info listing all dumps owned by this dump together
      // with list(s) of other owner dumps sharing them with this dump.
      if (ownedNameToEntry.size > 0) {
        var messageBuilder = new SizeInfoMessageBuilder();
        messageBuilder.append('shares');
        messageBuilder.appendMap(
            ownedNameToEntry,
            false /* hasPluralSuffix */,
            undefined /* emptyText */,
            function(ownedName, ownedEntry) {
              messageBuilder.append(ownedName);
              var ownedCount = ownedEntry.count;
              if (ownedCount < numerics.length)
                messageBuilder.appendSomeTimestampsQuantifier();
              messageBuilder.appendImportanceRange(ownedEntry.importanceRange);
            messageBuilder.append(' with');
            messageBuilder.appendMap(
                ownedEntry.sharerNameToEntry,
                false /* hasPluralSuffix */,
                ' no other dumps',
                function(sharerName, sharerEntry) {
                  messageBuilder.append(sharerName);
                  if (sharerEntry.count < ownedCount)
                    messageBuilder.appendSomeTimestampsQuantifier();
                  messageBuilder.appendImportanceRange(
                      sharerEntry.importanceRange);
                }, this);
            }, this);
        infos.push({
          message: messageBuilder.build(),
          icon: RIGHTWARDS_OPEN_HEADED_ARROW,
          color: 'green'
        });
      }
    },

    getAndUpdateOwnershipEntry_: function(
        map, dump, link, opt_withSharerNameToEntry) {
      var entry = getAndUpdateEntry(map, dump.quantifiedName,
          function(newEntry) {
            newEntry.importanceRange = new tr.b.Range();
            if (opt_withSharerNameToEntry)
              newEntry.sharerNameToEntry = new Map();
          });
      entry.importanceRange.addValue(link.importance || 0);
      return entry;
    }
  };

  /** @constructor */
  function SizeColumn(name, cellPath, aggregationMode) {
    tr.ui.analysis.NumericMemoryColumn.call(
        this, name, cellPath, aggregationMode);
  }

  SizeColumn.prototype = {
    __proto__: tr.ui.analysis.NumericMemoryColumn.prototype,

    addInfos: function(numerics, memoryAllocatorDumps, infos) {
      if (memoryAllocatorDumps === undefined)
        return;
      this.addOverlapInfo_(numerics, memoryAllocatorDumps, infos);
      this.addProvidedSizeWarningInfos_(numerics, memoryAllocatorDumps, infos);
    },

    addOverlapInfo_: function(numerics, memoryAllocatorDumps, infos) {
      // Sibling allocator dump name -> {count, size}. The latter field (size)
      // is omitted in multi-selection mode.
      var siblingNameToEntry = new Map();
      for (var i = 0; i < numerics.length; i++) {
        if (numerics[i] === undefined)
          continue;
        var dump = memoryAllocatorDumps[i];
        if (dump === SUBALLOCATION_CONTEXT)
          return;  // No ownership of suballocation internal rows.
        var ownedBySiblingSizes = dump.ownedBySiblingSizes;
        for (var siblingDump of ownedBySiblingSizes.keys()) {
          var siblingName = siblingDump.name;
          getAndUpdateEntry(siblingNameToEntry, siblingName,
              function(newEntry) {
                if (numerics.length === 1 /* single-selection mode */)
                  newEntry.size = ownedBySiblingSizes.get(siblingDump);
              });
        }
      }

      // Emit a single info describing all overlaps with siblings (if
      // applicable).
      if (siblingNameToEntry.size > 0) {
        var messageBuilder = new SizeInfoMessageBuilder();
        messageBuilder.append('overlaps with its sibling');
        messageBuilder.appendMap(
            siblingNameToEntry,
            true /* hasPluralSuffix */,
            undefined /* emptyText */,
            function(siblingName, siblingEntry) {
              messageBuilder.append('\'', siblingName, '\'');
              messageBuilder.appendSizeIfDefined(siblingEntry.size);
              if (siblingEntry.count < numerics.length)
                messageBuilder.appendSomeTimestampsQuantifier();
            }, this);
        infos.push({
          message: messageBuilder.build(),
          icon: CIRCLED_LATIN_SMALL_LETTER_I,
          color: 'blue'
        });
      }
    },

    addProvidedSizeWarningInfos_: function(numerics, memoryAllocatorDumps,
        infos) {
      // Info type (see MemoryAllocatorDumpInfoType) -> {count, providedSize,
      // dependencySize}. The latter two fields (providedSize and
      // dependencySize) are omitted in multi-selection mode.
      var infoTypeToEntry = new Map();
      for (var i = 0; i < numerics.length; i++) {
        if (numerics[i] === undefined)
          continue;
        var dump = memoryAllocatorDumps[i];
        if (dump === SUBALLOCATION_CONTEXT)
          return;  // Suballocation internal rows have no provided size.
        dump.infos.forEach(function(dumpInfo) {
          getAndUpdateEntry(infoTypeToEntry, dumpInfo.type, function(newEntry) {
            if (numerics.length === 1 /* single-selection mode */) {
              newEntry.providedSize = dumpInfo.providedSize;
              newEntry.dependencySize = dumpInfo.dependencySize;
            }
          });
        });
      }

      // Emit a warning info for every info type.
      for (var infoType of infoTypeToEntry.keys()) {
        var entry = infoTypeToEntry.get(infoType);
        var messageBuilder = new SizeInfoMessageBuilder();
        messageBuilder.append('provided size');
        messageBuilder.appendSizeIfDefined(entry.providedSize);
        var dependencyName;
        switch (infoType) {
          case PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN:
            dependencyName = 'the aggregated size of the children';
            break;
          case PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER:
            dependencyName = 'the size of the largest owner';
            break;
          default:
            dependencyName = 'an unknown dependency';
            break;
        }
        messageBuilder.append(' was less than ', dependencyName);
        messageBuilder.appendSizeIfDefined(entry.dependencySize);
        if (entry.count < numerics.length)
          messageBuilder.appendSomeTimestampsQuantifier();
        infos.push(tr.ui.analysis.createWarningInfo(messageBuilder.build()));
      }
    }
  };

  var NUMERIC_COLUMN_RULES = [
    {
      condition: tr.model.MemoryAllocatorDump.EFFECTIVE_SIZE_NUMERIC_NAME,
      importance: 10,
      columnConstructor: EffectiveSizeColumn
    },
    {
      condition: tr.model.MemoryAllocatorDump.SIZE_NUMERIC_NAME,
      importance: 9,
      columnConstructor: SizeColumn
    },
    {
      condition: 'page_size',
      importance: 0,
      columnConstructor: tr.ui.analysis.NumericMemoryColumn
    },
    {
      condition: /size/,
      importance: 5,
      columnConstructor: tr.ui.analysis.NumericMemoryColumn
    },
    {
      // All other columns.
      importance: 0,
      columnConstructor: tr.ui.analysis.NumericMemoryColumn
    }
  ];

  var DIAGNOSTIC_COLUMN_RULES = [
    {
      importance: 0,
      columnConstructor: tr.ui.analysis.StringMemoryColumn
    }
  ];

  Polymer('tr-ui-a-memory-dump-allocator-details-pane', {
    created: function() {
      this.memoryAllocatorDumps_ = undefined;
      this.heapDumps_ = undefined;
      this.aggregationMode_ = undefined;
    },

    ready: function() {
      this.$.table.selectionMode = tr.ui.b.TableFormat.SelectionMode.ROW;
    },

    /**
     * Sets the memory allocator dumps and schedules rebuilding the pane.
     *
     * The provided value should be a chronological list of memory allocator
     * dumps. All dumps are assumed to belong to the same process and have
     * the same full name. Example:
     *
     *   [
     *     tr.model.MemoryAllocatorDump {},  // MAD at timestamp 1.
     *     undefined,  // MAD not provided at timestamp 2.
     *     tr.model.MemoryAllocatorDump {},  // MAD at timestamp 3.
     *   ]
     */
    set memoryAllocatorDumps(memoryAllocatorDumps) {
      this.memoryAllocatorDumps_ = memoryAllocatorDumps;
      this.scheduleRebuildPane_();
    },

    get memoryAllocatorDumps() {
      return this.memoryAllocatorDumps_;
    },

    // TODO(petrcermak): Don't plumb the heap dumps through the allocator
    // details pane. Maybe add support for multiple child panes to stacked pane
    // (view) instead.
    set heapDumps(heapDumps) {
      this.heapDumps_ = heapDumps;
      this.scheduleRebuildPane_();
    },

    set aggregationMode(aggregationMode) {
      this.aggregationMode_ = aggregationMode;
      this.scheduleRebuildPane_();
    },

    get aggregationMode() {
      return this.aggregationMode_;
    },

    rebuildPane_: function() {
      if (this.memoryAllocatorDumps_ === undefined ||
          this.memoryAllocatorDumps_.length === 0) {
        // Show the info text (hide the table).
        this.$.info_text.style.display = 'block';
        this.$.table.style.display = 'none';

        this.$.table.clear();
        this.$.table.rebuild();

        // Hide the heap details pane (if applicable).
        this.childPaneBuilder = undefined;
        return;
      }

      // Show the table (hide the info text).
      this.$.info_text.style.display = 'none';
      this.$.table.style.display = 'block';

      var rows = this.createRows_();
      var columns = this.createColumns_(rows);
      rows.forEach(function(rootRow) {
        tr.ui.analysis.aggregateTableRowCellsRecursively(rootRow, columns,
            function(contexts) {
              // Only aggregate suballocation rows (numerics of regular rows
              // corresponding to MADs have already been aggregated by the
              // model in MemoryAllocatorDump.aggregateNumericsRecursively).
              return contexts !== undefined && contexts.some(function(context) {
                return context === SUBALLOCATION_CONTEXT;
              });
            });
      });

      this.$.table.tableRows = rows;
      this.$.table.tableColumns = columns;
      this.$.table.rebuild();
      tr.ui.analysis.expandTableRowsRecursively(this.$.table);

      // Show/hide the heap details pane.
      if (this.heapDumps_ === undefined) {
        this.childPaneBuilder = undefined;
      } else {
        this.childPaneBuilder = function() {
          var pane =
              document.createElement('tr-ui-a-memory-dump-heap-details-pane');
          pane.heapDumps = this.heapDumps_;
          pane.aggregationMode = this.aggregationMode_;
          return pane;
        }.bind(this);
      }
    },

    createRows_: function() {
      return [
        this.createAllocatorRowRecursively_(this.memoryAllocatorDumps_)
      ];
    },

    createAllocatorRowRecursively_: function(dumps) {
      // Get the name of the memory allocator dumps. We can use any defined
      // dump in dumps since they all have the same name.
      var definedDump = tr.b.findFirstInArray(dumps);
      var title = definedDump.name;
      var fullName = definedDump.fullName;

      // Transform a chronological list of memory allocator dumps into two
      // dictionaries of cells (where each cell contains a chronological list
      // of the values of one of its numerics or diagnostics).
      var numericCells = tr.ui.analysis.createCells(dumps, function(dump) {
        return dump.numerics;
      });
      var diagnosticCells = tr.ui.analysis.createCells(dumps, function(dump) {
        return dump.diagnostics;
      });

      // Determine whether the memory allocator dump is a suballocation. A
      // dump is assumed to be a suballocation if (1) its name starts with
      // two underscores, (2) it has an owner from within the same process at
      // some timestamp, and (3) it is undefined, has no owners, or has the
      // same owner (and no other owners) at all other timestamps.
      var suballocatedBy = undefined;
      if (title.startsWith('__')) {
        for (var i = 0; i < dumps.length; i++) {
          var dump = dumps[i];
          if (dump === undefined || dump.ownedBy.length === 0) {
            // Ignore timestamps where the dump is undefined or doesn't
            // have any owner.
            continue;
          }
          var ownerDump = dump.ownedBy[0].source;
          if (dump.ownedBy.length > 1 ||
              dump.children.length > 0 ||
              ownerDump.containerMemoryDump !== dump.containerMemoryDump) {
            // If the dump has (1) any children, (2) multiple owners, or
            // (3) its owner is in a different process (otherwise, the
            // modified title would be ambiguous), then it's not considered
            // to be a suballocation.
            suballocatedBy = undefined;
            break;
          }
          if (suballocatedBy === undefined) {
            suballocatedBy = ownerDump.fullName;
          } else if (suballocatedBy !== ownerDump.fullName) {
            // The full name of the owner dump changed over time, so this
            // dump is not a suballocation.
            suballocatedBy = undefined;
            break;
          }
        }
      }

      var row = {
        title: title,
        fullNames: [fullName],
        contexts: dumps,
        numericCells: numericCells,
        diagnosticCells: diagnosticCells,
        suballocatedBy: suballocatedBy
      };

      // Child memory dump name (dict key) -> Timestamp (list index) ->
      // Child dump.
      var childDumpNameToDumps = tr.b.invertArrayOfDicts(dumps,
          function(dump) {
            return tr.b.arrayToDict(dump.children, function(child) {
              return child.name;
            });
          });

      // Recursively create sub-rows for children (if applicable).
      var subRows = [];
      var suballocationClassificationRootNode = undefined;
      tr.b.iterItems(childDumpNameToDumps, function(childName, childDumps) {
        var childRow = this.createAllocatorRowRecursively_(childDumps);
        if (childRow.suballocatedBy === undefined) {
          // Not a suballocation row: just append it.
          subRows.push(childRow);
        } else {
          // Suballocation row: classify it in a tree of suballocations.
          suballocationClassificationRootNode =
              this.classifySuballocationRow_(
                  childRow, suballocationClassificationRootNode);
        }
      }, this);

      // Build the tree of suballocations (if applicable).
      if (suballocationClassificationRootNode !== undefined) {
        var suballocationRow = this.createSuballocationRowRecursively_(
            'suballocations', suballocationClassificationRootNode);
        subRows.push(suballocationRow);
      }

      if (subRows.length > 0)
        row.subRows = subRows;

      return row;
    },

    classifySuballocationRow_: function(suballocationRow, rootNode) {
      if (rootNode === undefined) {
        rootNode = {
          children: {},
          row: undefined
        };
      }

      var suballocationLevels = suballocationRow.suballocatedBy.split('/');
      var currentNode = rootNode;
      for (var i = 0; i < suballocationLevels.length; i++) {
        var suballocationLevel = suballocationLevels[i];
        var nextNode = currentNode.children[suballocationLevel];
        if (nextNode === undefined) {
          currentNode.children[suballocationLevel] = nextNode = {
            children: {},
            row: undefined
          };
        }
        var currentNode = nextNode;
      }

      var existingRow = currentNode.row;
      if (existingRow !== undefined) {
        // On rare occasions it can happen that one dump (e.g. sqlite) owns
        // different suballocations at different timestamps (e.g.
        // malloc/allocated_objects/_7d35 and malloc/allocated_objects/_511e).
        // When this happens, we merge the two suballocations into a single row
        // (malloc/allocated_objects/suballocations/sqlite).
        for (var i = 0; i < suballocationRow.contexts.length; i++) {
          var newContext = suballocationRow.contexts[i];
          if (newContext === undefined)
            continue;

          if (existingRow.contexts[i] !== undefined)
            throw new Error('Multiple suballocations with the same owner name');

          existingRow.contexts[i] = newContext;
          ['numericCells', 'diagnosticCells'].forEach(function(cellKey) {
            var suballocationCells = suballocationRow[cellKey];
            if (suballocationCells === undefined)
              return;
            tr.b.iterItems(suballocationCells, function(cellName, cell) {
              if (cell === undefined)
                return;
              var fields = cell.fields;
              if (fields === undefined)
                return;
              var field = fields[i];
              if (field === undefined)
                return;
              var existingCells = existingRow[cellKey];
              if (existingCells === undefined) {
                existingCells = {};
                existingRow[cellKey] = existingCells;
              }
              var existingCell = existingCells[cellName];
              if (existingCell === undefined) {
                existingCell = new tr.ui.analysis.MemoryCell(
                    new Array(fields.length));
                existingCells[cellName] = existingCell;
              }
              existingCell.fields[i] = field;
            });
          });
        }
        existingRow.fullNames.push.apply(
            existingRow.fullNames, suballocationRow.fullNames);
      } else {
        currentNode.row = suballocationRow;
      }

      return rootNode;
    },

    createSuballocationRowRecursively_: function(name, node) {
      var childCount = Object.keys(node.children).length;
      if (childCount === 0) {
        if (node.row === undefined)
          throw new Error('Suballocation node must have a row or children');
        // Leaf row of the suballocation tree: Change the row's title from
        // '__MEANINGLESSHASH' to the name of the suballocation owner.
        var row = node.row;
        row.title = name;
        row.suballocation = true;
        return row;
      }

      // Internal row of the suballocation tree: Recursively create its
      // sub-rows.
      var subRows = tr.b.dictionaryValues(tr.b.mapItems(
          node.children, this.createSuballocationRowRecursively_, this));

      if (node.row !== undefined) {
        // Very unlikely case: Both an ancestor (e.g. 'skia') and one of its
        // descendants (e.g. 'skia/sk_glyph_cache') both suballocate from the
        // same MemoryAllocatorDump (e.g. 'malloc/allocated_objects'). In
        // this case, the suballocation from the ancestor must be mapped to
        // 'malloc/allocated_objects/suballocations/skia/<unspecified>' so
        // that 'malloc/allocated_objects/suballocations/skia' could
        // aggregate the numerics of the two suballocations properly.
        var row = node.row;
        row.title = '<unspecified>';
        row.suballocation = true;
        subRows.unshift(row);
      }

      // An internal row of the suballocation tree is assumed to be defined
      // at a given timestamp if at least one of its sub-rows is defined at
      // the timestamp.
      var contexts = new Array(subRows[0].contexts.length);
      for (var i = 0; i < subRows.length; i++) {
        subRows[i].contexts.forEach(function(subContext, index) {
          if (subContext !== undefined)
            contexts[index] = SUBALLOCATION_CONTEXT;
        });
      }

      return {
        title: name,
        suballocation: true,
        contexts: contexts,
        subRows: subRows
      };
    },

    createColumns_: function(rows) {
      var titleColumn = new AllocatorDumpNameColumn();
      titleColumn.width = '200px';

      var numericColumns = tr.ui.analysis.MemoryColumn.fromRows(
          rows, 'numericCells', this.aggregationMode_, NUMERIC_COLUMN_RULES);
      var diagnosticColumns = tr.ui.analysis.MemoryColumn.fromRows(
          rows, 'diagnosticCells', this.aggregationMode_,
          DIAGNOSTIC_COLUMN_RULES);
      var fieldColumns = numericColumns.concat(diagnosticColumns);
      tr.ui.analysis.MemoryColumn.spaceEqually(fieldColumns);

      var columns = [titleColumn].concat(fieldColumns);
      return columns;
    }
  });

  return {
    // All exports are for testing only.
    SUBALLOCATION_CONTEXT: SUBALLOCATION_CONTEXT,
    AllocatorDumpNameColumn: AllocatorDumpNameColumn,
    EffectiveSizeColumn: EffectiveSizeColumn,
    SizeColumn: SizeColumn
  };
});
</script>