<!DOCTYPE html>
<!--
Copyright (c) 2012 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="/base/ui/color_scheme.html">
<link rel="import" href="/base/quad.html">
<link rel="import" href="/base/range.html">
<link rel="import" href="/importer/importer.html">
<link rel="import" href="/model/attribute.html">
<link rel="import" href="/model/comment_box_annotation.html">
<link rel="import" href="/model/instant_event.html">
<link rel="import" href="/model/flow_event.html">
<link rel="import" href="/model/counter_series.html">
<link rel="import" href="/model/slice_group.html">
<link rel="import" href="/model/global_memory_dump.html">
<link rel="import" href="/model/memory_allocator_dump.html">
<link rel="import" href="/model/process_memory_dump.html">
<link rel="import" href="/model/rect_annotation.html">
<link rel="import" href="/model/x_marker_annotation.html">
<link rel="import" href="/model/model.html">

<script>
'use strict';

/**
 * @fileoverview TraceEventImporter imports TraceEvent-formatted data
 * into the provided model.
 */
tr.exportTo('tr.e.importer', function() {

  var Importer = tr.importer.Importer;

  function deepCopy(value) {
    if (!(value instanceof Object)) {
      if (value === undefined || value === null)
        return value;
      if (typeof value == 'string')
        return value.substring();
      if (typeof value == 'boolean')
        return value;
      if (typeof value == 'number')
        return value;
      throw new Error('Unrecognized: ' + typeof value);
    }

    var object = value;
    if (object instanceof Array) {
      var res = new Array(object.length);
      for (var i = 0; i < object.length; i++)
        res[i] = deepCopy(object[i]);
      return res;
    }

    if (object.__proto__ != Object.prototype)
      throw new Error('Can only clone simple types');
    var res = {};
    for (var key in object) {
      res[key] = deepCopy(object[key]);
    }
    return res;
  }

  function TraceEventImporter(model, eventData) {
    this.importPriority = 1;
    this.model_ = model;
    this.events_ = undefined;
    this.sampleEvents_ = undefined;
    this.stackFrameEvents_ = undefined;
    this.systemTraceEvents_ = undefined;
    this.eventsWereFromString_ = false;
    this.softwareMeasuredCpuCount_ = undefined;
    this.allAsyncEvents_ = [];
    this.allFlowEvents_ = [];
    this.allObjectEvents_ = [];
    this.traceEventSampleStackFramesByName_ = {};

    // Dump ID -> {global: (event | undefined), process: [events]}
    this.allMemoryDumpEvents_ = {};


    if (typeof(eventData) === 'string' || eventData instanceof String) {
      eventData = eventData.trim();
      // If the event data begins with a [, then we know it should end with a ].
      // The reason we check for this is because some tracing implementations
      // cannot guarantee that a ']' gets written to the trace file. So, we are
      // forgiving and if this is obviously the case, we fix it up before
      // throwing the string at JSON.parse.
      if (eventData[0] === '[') {
        eventData = eventData.replace(/\s*,\s*$/, '');
        if (eventData[eventData.length - 1] !== ']')
          eventData = eventData + ']';
      }
      this.events_ = JSON.parse(eventData);
      this.eventsWereFromString_ = true;
    } else {
      this.events_ = eventData;
    }

    this.traceAnnotations_ = this.events_.traceAnnotations;

    // Some trace_event implementations put the actual trace events
    // inside a container. E.g { ... , traceEvents: [ ] }
    // If we see that, just pull out the trace events.
    if (this.events_.traceEvents) {
      var container = this.events_;
      this.events_ = this.events_.traceEvents;

      // Some trace_event implementations put ftrace_importer traces as a
      // huge string inside container.systemTraceEvents. If we see that, pull it
      // out. It will be picked up by extractSubtraces later on.
      this.systemTraceEvents_ = container.systemTraceEvents;

      // Sampling data.
      this.sampleEvents_ = container.samples;
      this.stackFrameEvents_ = container.stackFrames;

      // Any other fields in the container should be treated as metadata.
      for (var fieldName in container) {
        if (fieldName === 'traceEvents' || fieldName === 'systemTraceEvents' ||
            fieldName === 'samples' || fieldName === 'stackFrames' ||
            fieldName === 'traceAnnotations')
          continue;
        this.model_.metadata.push({name: fieldName,
          value: container[fieldName]});
      }
    }
  }

  /**
   * @return {boolean} Whether obj is a TraceEvent array.
   */
  TraceEventImporter.canImport = function(eventData) {
    // May be encoded JSON. But we dont want to parse it fully yet.
    // Use a simple heuristic:
    //   - eventData that starts with [ are probably trace_event
    //   - eventData that starts with { are probably trace_event
    // May be encoded JSON. Treat files that start with { as importable by us.
    if (typeof(eventData) === 'string' || eventData instanceof String) {
      eventData = eventData.trim();
      return eventData[0] == '{' || eventData[0] == '[';
    }

    // Might just be an array of events
    if (eventData instanceof Array && eventData.length && eventData[0].ph)
      return true;

    // Might be an object with a traceEvents field in it.
    if (eventData.traceEvents) {
      if (eventData.traceEvents instanceof Array) {
        if (eventData.traceEvents.length && eventData.traceEvents[0].ph)
          return true;
        if (eventData.samples.length && eventData.stackFrames !== undefined)
          return true;
      }
    }

    return false;
  };

  TraceEventImporter.prototype = {

    __proto__: Importer.prototype,

    extractSubtraces: function() {
      var tmp = this.systemTraceEvents_;
      this.systemTraceEvents_ = undefined;
      return tmp ? [tmp] : [];
    },

    /**
     * Deep copying is only needed if the trace was given to us as events.
     */
    deepCopyIfNeeded_: function(obj) {
      if (obj === undefined)
        obj = {};
      if (this.eventsWereFromString_)
        return obj;
      return deepCopy(obj);
    },

    /**
     * Helper to process an async event.
     */
    processAsyncEvent: function(event) {
      var thread = this.model_.getOrCreateProcess(event.pid).
          getOrCreateThread(event.tid);
      this.allAsyncEvents_.push({
        sequenceNumber: this.allAsyncEvents_.length,
        event: event,
        thread: thread});
    },

    /**
     * Helper to process a flow event.
     */
    processFlowEvent: function(event) {
      var thread = this.model_.getOrCreateProcess(event.pid).
          getOrCreateThread(event.tid);
      this.allFlowEvents_.push({
        refGuid: tr.b.GUID.getLastGuid(),
        sequenceNumber: this.allFlowEvents_.length,
        event: event,
        thread: thread
      });
    },

    /**
     * Helper that creates and adds samples to a Counter object based on
     * 'C' phase events.
     */
    processCounterEvent: function(event) {
      var ctr_name;
      if (event.id !== undefined)
        ctr_name = event.name + '[' + event.id + ']';
      else
        ctr_name = event.name;

      var ctr = this.model_.getOrCreateProcess(event.pid)
          .getOrCreateCounter(event.cat, ctr_name);

      // Initialize the counter's series fields if needed.
      if (ctr.numSeries === 0) {
        for (var seriesName in event.args) {
          ctr.addSeries(new tr.model.CounterSeries(
              seriesName,
              tr.b.ui.getColorIdForGeneralPurposeString(
                  ctr.name + '.' + seriesName)));
        }

        if (ctr.numSeries === 0) {
          this.model_.importWarning({
            type: 'counter_parse_error',
            message: 'Expected counter ' + event.name +
                ' to have at least one argument to use as a value.'
          });

          // Drop the counter.
          delete ctr.parent.counters[ctr.name];
          return;
        }
      }

      var ts = event.ts / 1000;
      ctr.series.forEach(function(series) {
        var val = event.args[series.name] ? event.args[series.name] : 0;
        series.addCounterSample(ts, val);
      });
    },

    processObjectEvent: function(event) {
      var thread = this.model_.getOrCreateProcess(event.pid).
          getOrCreateThread(event.tid);
      this.allObjectEvents_.push({
        sequenceNumber: this.allObjectEvents_.length,
        event: event,
        thread: thread});
    },

    processDurationEvent: function(event) {
      var thread = this.model_.getOrCreateProcess(event.pid)
        .getOrCreateThread(event.tid);
      if (!thread.sliceGroup.isTimestampValidForBeginOrEnd(event.ts / 1000)) {
        this.model_.importWarning({
          type: 'duration_parse_error',
          message: 'Timestamps are moving backward.'
        });
        return;
      }

      if (event.ph == 'B') {
        var slice = thread.sliceGroup.beginSlice(
            event.cat, event.name, event.ts / 1000,
            this.deepCopyIfNeeded_(event.args),
            event.tts / 1000);
        slice.startStackFrame = this.getStackFrameForEvent_(event);
      } else if (event.ph == 'I' || event.ph == 'i') {
        if (event.s !== undefined && event.s !== 't')
          throw new Error('This should never happen');

        thread.sliceGroup.beginSlice(event.cat, event.name, event.ts / 1000,
                                     this.deepCopyIfNeeded_(event.args),
                                     event.tts / 1000);
        var slice = thread.sliceGroup.endSlice(event.ts / 1000,
                                   event.tts / 1000);
        slice.startStackFrame = this.getStackFrameForEvent_(event);
        slice.endStackFrame = undefined;
      } else {
        if (!thread.sliceGroup.openSliceCount) {
          this.model_.importWarning({
            type: 'duration_parse_error',
            message: 'E phase event without a matching B phase event.'
          });
          return;
        }

        var slice = thread.sliceGroup.endSlice(event.ts / 1000,
                                               event.tts / 1000);
        if (event.name && slice.title != event.name) {
          this.model_.importWarning({
            type: 'title_match_error',
            message: 'Titles do not match. Title is ' +
                slice.title + ' in openSlice, and is ' +
                event.name + ' in endSlice'
          });
        }
        slice.endStackFrame = this.getStackFrameForEvent_(event);

        this.mergeArgsInto_(slice.args, event.args, slice.title);
      }
    },

    mergeArgsInto_: function(dstArgs, srcArgs, eventName) {
      for (var arg in srcArgs) {
        if (dstArgs[arg] !== undefined) {
          this.model_.importWarning({
            type: 'arg_merge_error',
            message: 'Different phases of ' + eventName +
                ' provided values for argument ' + arg + '.' +
                ' The last provided value will be used.'
          });
        }
        dstArgs[arg] = this.deepCopyIfNeeded_(srcArgs[arg]);
      }
    },

    processCompleteEvent: function(event) {
      var thread = this.model_.getOrCreateProcess(event.pid)
          .getOrCreateThread(event.tid);
      var slice = thread.sliceGroup.pushCompleteSlice(event.cat, event.name,
          event.ts / 1000,
          event.dur === undefined ? undefined : event.dur / 1000,
          event.tts === undefined ? undefined : event.tts / 1000,
          event.tdur === undefined ? undefined : event.tdur / 1000,
          this.deepCopyIfNeeded_(event.args));
      slice.startStackFrame = this.getStackFrameForEvent_(event);
      slice.endStackFrame = this.getStackFrameForEvent_(event, true);
    },

    processMetadataEvent: function(event) {
      if (event.name == 'process_name') {
        var process = this.model_.getOrCreateProcess(event.pid);
        process.name = event.args.name;
      } else if (event.name == 'process_labels') {
        var process = this.model_.getOrCreateProcess(event.pid);
        var labels = event.args.labels.split(',');
        for (var i = 0; i < labels.length; i++)
          process.addLabelIfNeeded(labels[i]);
      } else if (event.name == 'process_sort_index') {
        var process = this.model_.getOrCreateProcess(event.pid);
        process.sortIndex = event.args.sort_index;
      } else if (event.name == 'thread_name') {
        var thread = this.model_.getOrCreateProcess(event.pid).
            getOrCreateThread(event.tid);
        thread.name = event.args.name;
      } else if (event.name == 'thread_sort_index') {
        var thread = this.model_.getOrCreateProcess(event.pid).
            getOrCreateThread(event.tid);
        thread.sortIndex = event.args.sort_index;
      } else if (event.name == 'num_cpus') {
        var n = event.args.number;
        // Not all render processes agree on the cpu count in trace_event. Some
        // processes will report 1, while others will report the actual cpu
        // count. To deal with this, take the max of what is reported.
        if (this.softwareMeasuredCpuCount_ !== undefined)
          n = Math.max(n, this.softwareMeasuredCpuCount_);
        this.softwareMeasuredCpuCount_ = n;
      } else {
        this.model_.importWarning({
          type: 'metadata_parse_error',
          message: 'Unrecognized metadata name: ' + event.name
        });
      }
    },

    processInstantEvent: function(event) {
      // Thread-level instant events are treated as zero-duration slices.
      if (event.s == 't' || event.s === undefined) {
        this.processDurationEvent(event);
        return;
      }

      var constructor;
      switch (event.s) {
        case 'g':
          constructor = tr.model.GlobalInstantEvent;
          break;
        case 'p':
          constructor = tr.model.ProcessInstantEvent;
          break;
        default:
          this.model_.importWarning({
            type: 'instant_parse_error',
            message: 'I phase event with unknown "s" field value.'
          });
          return;
      }

      var colorId = tr.b.ui.getColorIdForGeneralPurposeString(event.name);
      var instantEvent = new constructor(event.cat, event.name,
          colorId, event.ts / 1000, this.deepCopyIfNeeded_(event.args));

      switch (instantEvent.type) {
        case tr.model.InstantEventType.GLOBAL:
          this.model_.pushInstantEvent(instantEvent);
          break;

        case tr.model.InstantEventType.PROCESS:
          var process = this.model_.getOrCreateProcess(event.pid);
          process.pushInstantEvent(instantEvent);
          break;

        default:
          throw new Error('Unknown instant event type: ' + event.s);
      }
    },

    processTraceSampleEvent: function(event) {
      var thread = this.model_.getOrCreateProcess(event.pid)
        .getOrCreateThread(event.tid);

      var stackFrame = this.getStackFrameForEvent_(event);
      if (stackFrame === undefined) {
        stackFrame = this.traceEventSampleStackFramesByName_[
            event.name];
      }
      if (stackFrame === undefined) {
        var id = 'te-' + tr.b.GUID.allocate();
        stackFrame = new tr.model.StackFrame(
            undefined, id,
            event.cat, event.name,
            tr.b.ui.getColorIdForGeneralPurposeString(event.name));
        this.model_.addStackFrame(stackFrame);
        this.traceEventSampleStackFramesByName_[event.name] = stackFrame;
      }

      var sample = new tr.model.Sample(
          undefined, thread, 'TRACE_EVENT_SAMPLE',
          event.ts / 1000, stackFrame, 1,
          this.deepCopyIfNeeded_(event.args));
      this.model_.samples.push(sample);
    },

    getOrCreateMemoryDumpEvents_: function(dumpId) {
      if (this.allMemoryDumpEvents_[dumpId] === undefined) {
        this.allMemoryDumpEvents_[dumpId] = {
          global: undefined,
          process: []
        };
      }
      return this.allMemoryDumpEvents_[dumpId];
    },

    processMemoryDumpEvent: function(event) {
      if (event.id === undefined) {
        this.model_.importWarning({
          type: 'memory_dump_parse_error',
          message: event.ph + ' phase event without a dump ID.'
        });
        return;
      }
      var events = this.getOrCreateMemoryDumpEvents_(event.id);

      if (event.ph === 'v') {
        // Add a process memory dump.
        events.process.push(event);
      } else if (event.ph === 'V') {
        // Add a global memory dump (unless already present).
        if (events.global !== undefined) {
          this.model_.importWarning({
            type: 'memory_dump_parse_error',
            message: 'Multiple V phase events with the same dump ID.'
          });
          return;
        }
        events.global = event;
      } else {
        throw new Error('Invalid memory dump event phase "' + event.ph + '".');
      }
    },

    /**
     * Walks through the events_ list and outputs the structures discovered to
     * model_.
     */
    importEvents: function() {
      var csr = new tr.ClockSyncRecord('ftrace_importer', 0, {});
      this.model_.clockSyncRecords.push(csr);
      if (this.stackFrameEvents_)
        this.importStackFrames_();

      if (this.traceAnnotations_)
        this.importAnnotations_();

      var events = this.events_;
      for (var eI = 0; eI < events.length; eI++) {
        var event = events[eI];
        if (event.ph === 'B' || event.ph === 'E') {
          this.processDurationEvent(event);

        } else if (event.ph === 'X') {
          this.processCompleteEvent(event);

        } else if (event.ph === 'b' || event.ph === 'e' || event.ph === 'n' ||
                   event.ph === 'S' || event.ph === 'F' || event.ph === 'T' ||
                   event.ph === 'p') {
          this.processAsyncEvent(event);

        // Note, I is historic. The instant event marker got changed, but we
        // want to support loading old trace files so we have both I and i.
        } else if (event.ph == 'I' || event.ph == 'i') {
          this.processInstantEvent(event);

        } else if (event.ph == 'P') {
          this.processTraceSampleEvent(event);

        } else if (event.ph == 'C') {
          this.processCounterEvent(event);

        } else if (event.ph == 'M') {
          this.processMetadataEvent(event);

        } else if (event.ph === 'N' || event.ph === 'D' || event.ph === 'O') {
          this.processObjectEvent(event);

        } else if (event.ph === 's' || event.ph === 't' || event.ph === 'f') {
          this.processFlowEvent(event);

        } else if (event.ph === 'v' || event.ph === 'V') {
          this.processMemoryDumpEvent(event);

        } else {
          this.model_.importWarning({
            type: 'parse_error',
            message: 'Unrecognized event phase: ' +
                event.ph + ' (' + event.name + ')'
          });
        }
      }
    },

    importStackFrames_: function() {
      var m = this.model_;
      var events = this.stackFrameEvents_;

      for (var id in events) {
        var event = events[id];
        var textForColor = event.category ? event.category : event.name;
        var frame = new tr.model.StackFrame(
            undefined, 'g' + id,
            event.category, event.name,
            tr.b.ui.getColorIdForGeneralPurposeString(textForColor));
        m.addStackFrame(frame);
      }
      for (var id in events) {
        var event = events[id];
        if (event.parent === undefined)
          continue;

        var frame = m.stackFrames['g' + id];
        if (frame === undefined)
          throw new Error('omg');
        var parentFrame;
        if (event.parent === undefined) {
          parentFrame = undefined;
        } else {
          parentFrame = m.stackFrames['g' + event.parent];
          if (parentFrame === undefined)
            throw new Error('omg');
        }
        frame.parentFrame = parentFrame;
      }
    },

    importAnnotations_: function() {
      for (var id in this.traceAnnotations_) {
        var annotation = tr.model.Annotation.fromDictIfPossible(
           this.traceAnnotations_[id]);
        if (!annotation) {
          this.model_.importWarning({
            type: 'annotation_warning',
            message: 'Unrecognized traceAnnotation typeName \"' +
                this.traceAnnotations_[id].typeName + '\"'
          });
          continue;
        }
        this.model_.addAnnotation(annotation);
      }
    },

    /**
     * Called by the Model after all other importers have imported their
     * events.
     */
    finalizeImport: function() {
      if (this.softwareMeasuredCpuCount_ !== undefined) {
        this.model_.kernel.softwareMeasuredCpuCount =
            this.softwareMeasuredCpuCount_;
      }
      this.createAsyncSlices_();
      this.createFlowSlices_();
      this.createExplicitObjects_();
      this.createImplicitObjects_();
      this.createMemoryDumps_();
    },

    /* Events can have one or more stack frames associated with them, but
     * that frame might be encoded either as a stack trace of program counters,
     * or as a direct stack frame reference. This handles either case and
     * if found, returns the stackframe.
     */
    getStackFrameForEvent_: function(event, opt_lookForEndEvent) {
      var sf;
      var stack;
      if (opt_lookForEndEvent) {
        sf = event.esf;
        stack = event.estack;
      } else {
        sf = event.sf;
        stack = event.stack;
      }
      if (stack !== undefined && sf !== undefined) {
        this.model_.importWarning({
          type: 'stack_frame_and_stack_error',
          message: 'Event at ' + event.ts +
              ' cannot have both a stack and a stackframe.'
        });
        return undefined;
      }

      if (stack !== undefined)
        return this.model_.resolveStackToStackFrame_(event.pid, stack);
      if (sf === undefined)
        return undefined;

      var stackFrame = this.model_.stackFrames['g' + sf];
      if (stackFrame === undefined) {
        this.model_.importWarning({
          type: 'sample_import_error',
          message: 'No frame for ' + sf
        });
        return;
      }
      return stackFrame;
    },

    resolveStackToStackFrame_: function(pid, stack) {
      // TODO(alph,fmeawad): Add codemap resolution code here.
      return undefined;
    },

    importSampleData: function() {
      if (!this.sampleEvents_)
        return;
      var m = this.model_;

      // If this is the only importer, then fake-create the threads.
      var events = this.sampleEvents_;
      if (this.events_.length === 0) {
        for (var i = 0; i < events.length; i++) {
          var event = events[i];
          m.getOrCreateProcess(event.tid).getOrCreateThread(event.tid);
        }
      }

      var threadsByTid = {};
      m.getAllThreads().forEach(function(t) {
        threadsByTid[t.tid] = t;
      });

      for (var i = 0; i < events.length; i++) {
        var event = events[i];
        var thread = threadsByTid[event.tid];
        if (thread === undefined) {
          m.importWarning({
            type: 'sample_import_error',
            message: 'Thread ' + events.tid + 'not found'
          });
          continue;
        }

        var cpu;
        if (event.cpu !== undefined)
          cpu = m.kernel.getOrCreateCpu(event.cpu);

        var stackFrame = this.getStackFrameForEvent_(event);

        var sample = new tr.model.Sample(
            cpu, thread,
            event.name, event.ts / 1000,
            stackFrame,
            event.weight);
        m.samples.push(sample);
      }
    },

    /**
     * Called by the model to join references between objects, after final model
     * bounds have been computed.
     */
    joinRefs: function() {
      this.joinObjectRefs_();
    },

    createAsyncSlices_: function() {
      if (this.allAsyncEvents_.length === 0)
        return;

      this.allAsyncEvents_.sort(function(x, y) {
        var d = x.event.ts - y.event.ts;
        if (d !== 0)
          return d;
        return x.sequenceNumber - y.sequenceNumber;
      });

      var legacyEvents = [];
      // Group nestable async events by ID. Events with the same ID should
      // belong to the same parent async event.
      var nestableAsyncEventsByKey = {};
      for (var i = 0; i < this.allAsyncEvents_.length; i++) {
        var asyncEventState = this.allAsyncEvents_[i];
        var event = asyncEventState.event;
        if (event.ph === 'S' || event.ph === 'F' || event.ph === 'T' ||
            event.ph === 'p') {
          legacyEvents.push(asyncEventState);
          continue;
        }
        if (event.cat === undefined) {
          this.model_.importWarning({
            type: 'async_slice_parse_error',
            message: 'Nestable async events (ph: b, e, or n) require a ' +
                'cat parameter.'
          });
          continue;
        }

        if (event.name === undefined) {
          this.model_.importWarning({
            type: 'async_slice_parse_error',
            message: 'Nestable async events (ph: b, e, or n) require a ' +
                'name parameter.'
          });
          continue;
        }

        if (event.id === undefined) {
          this.model_.importWarning({
            type: 'async_slice_parse_error',
            message: 'Nestable async events (ph: b, e, or n) require an ' +
                'id parameter.'
          });
          continue;
        }
        var key = event.cat + ':' + event.id;
        if (nestableAsyncEventsByKey[key] === undefined)
           nestableAsyncEventsByKey[key] = [];
        nestableAsyncEventsByKey[key].push(asyncEventState);
      }
      // Handle legacy async events.
      this.createLegacyAsyncSlices_(legacyEvents);

      // Parse nestable async events into AsyncSlices.
      for (var key in nestableAsyncEventsByKey) {
        var eventStateEntries = nestableAsyncEventsByKey[key];
        // Stack of enclosing BEGIN events.
        var parentStack = [];
        for (var i = 0; i < eventStateEntries.length; ++i) {
          var eventStateEntry = eventStateEntries[i];
          // If this is the end of an event, match it to the start.
          if (eventStateEntry.event.ph === 'e') {
            // Walk up the parent stack to find the corresponding BEGIN for
            // this END.
            var parentIndex = -1;
            for (var k = parentStack.length - 1; k >= 0; --k) {
              if (parentStack[k].event.name === eventStateEntry.event.name) {
                parentIndex = k;
                break;
              }
            }
            if (parentIndex === -1) {
              // Unmatched end.
              eventStateEntry.finished = false;
            } else {
              parentStack[parentIndex].end = eventStateEntry;
              // Pop off all enclosing unmatched BEGINs util parentIndex.
              while (parentIndex < parentStack.length) {
                parentStack.pop();
              }
            }
          }
          // Inherit the current parent.
          if (parentStack.length > 0)
            eventStateEntry.parentEntry = parentStack[parentStack.length - 1];
          if (eventStateEntry.event.ph === 'b')
            parentStack.push(eventStateEntry);
        }
        var topLevelSlices = [];
        for (var i = 0; i < eventStateEntries.length; ++i) {
          var eventStateEntry = eventStateEntries[i];
          // Skip matched END, as its slice will be created when we
          // encounter its corresponding BEGIN.
          if (eventStateEntry.event.ph === 'e' &&
              eventStateEntry.finished === undefined) {
            continue;
          }
          var startState = undefined;
          var endState = undefined;
          var sliceArgs = eventStateEntry.event.args || {};
          var sliceError = undefined;
          if (eventStateEntry.event.ph === 'n') {
            startState = eventStateEntry;
            endState = eventStateEntry;
          } else if (eventStateEntry.event.ph === 'b') {
            if (eventStateEntry.end === undefined) {
              // Unmatched BEGIN. End it when last event with this ID ends.
              eventStateEntry.end =
                  eventStateEntries[eventStateEntries.length - 1];
              sliceError =
                  'Slice has no matching END. End time has been adjusted.';
              this.model_.importWarning({
                type: 'async_slice_parse_error',
                message: 'Nestable async BEGIN event at ' +
                    eventStateEntry.event.ts + ' with name=' +
                    eventStateEntry.event.name +
                    ' and id=' + eventStateEntry.event.id + ' was unmatched.'
              });
            } else {
              // Include args for both END and BEGIN for a matched pair.
              var concatenateArguments = function(args1, args2) {
                if (args1.params === undefined || args2.params === undefined)
                  return tr.b.concatenateObjects(args1, args2);
                // Make an argument object to hold the combined params.
                var args3 = {};
                args3.params = tr.b.concatenateObjects(args1.params,
                                                       args2.params);
                return tr.b.concatenateObjects(args1, args2, args3);
              }
              var endArgs = eventStateEntry.end.event.args || {};
              sliceArgs = concatenateArguments(sliceArgs, endArgs);
            }
            startState = eventStateEntry;
            endState = eventStateEntry.end;
          } else {
            // Unmatched END. Start it at the first event with this ID starts.
            sliceError =
                'Slice has no matching BEGIN. Start time has been adjusted.';
            this.model_.importWarning({
              type: 'async_slice_parse_error',
              message: 'Nestable async END event at ' +
                  eventStateEntry.event.ts + ' with name=' +
                  eventStateEntry.event.name +
                  ' and id=' + eventStateEntry.event.id + ' was unmatched.'
            });
            startState = eventStateEntries[0];
            endState = eventStateEntry;
          }

          var isTopLevel = (eventStateEntry.parentEntry === undefined);
          var asyncSliceConstructor =
             tr.model.AsyncSlice.getConstructor(
                eventStateEntry.event.cat,
                eventStateEntry.event.name);

          var thread_start = undefined;
          var thread_duration = undefined;
          if (startState.event.tts && startState.event.use_async_tts) {
            thread_start = startState.event.tts / 1000;
            if (endState.event.tts) {
              var thread_end = endState.event.tts / 1000;
              thread_duration = thread_end - thread_start;
            }
          }

          var slice = new asyncSliceConstructor(
              eventStateEntry.event.cat,
              eventStateEntry.event.name,
              tr.b.ui.getColorIdForGeneralPurposeString(
                  eventStateEntry.event.name),
              startState.event.ts / 1000,
              sliceArgs,
              (endState.event.ts - startState.event.ts) / 1000,
              isTopLevel,
              thread_start,
              thread_duration);

          slice.startThread = startState.thread;
          slice.endThread = endState.thread;
          slice.id = key;
          if (sliceError !== undefined)
            slice.error = sliceError;
          eventStateEntry.slice = slice;
          // Add the slice to the topLevelSlices array if there is no parent.
          // Otherwise, add the slice to the subSlices of its parent.
          if (isTopLevel) {
            topLevelSlices.push(slice);
          } else if (eventStateEntry.parentEntry.slice !== undefined) {
            eventStateEntry.parentEntry.slice.subSlices.push(slice);
          }
        }
        for (var si = 0; si < topLevelSlices.length; si++) {
          topLevelSlices[si].startThread.asyncSliceGroup.push(
              topLevelSlices[si]);
        }
      }
    },

    createLegacyAsyncSlices_: function(legacyEvents) {
      if (legacyEvents.length === 0)
        return;

      legacyEvents.sort(function(x, y) {
        var d = x.event.ts - y.event.ts;
        if (d != 0)
          return d;
        return x.sequenceNumber - y.sequenceNumber;
      });

      var asyncEventStatesByNameThenID = {};

      for (var i = 0; i < legacyEvents.length; i++) {
        var asyncEventState = legacyEvents[i];

        var event = asyncEventState.event;
        var name = event.name;
        if (name === undefined) {
          this.model_.importWarning({
            type: 'async_slice_parse_error',
            message: 'Async events (ph: S, T, p, or F) require a name ' +
                ' parameter.'
          });
          continue;
        }

        var id = event.id;
        if (id === undefined) {
          this.model_.importWarning({
            type: 'async_slice_parse_error',
            message: 'Async events (ph: S, T, p, or F) require an id parameter.'
          });
          continue;
        }

        // TODO(simonjam): Add a synchronous tick on the appropriate thread.

        if (event.ph === 'S') {
          if (asyncEventStatesByNameThenID[name] === undefined)
            asyncEventStatesByNameThenID[name] = {};
          if (asyncEventStatesByNameThenID[name][id]) {
            this.model_.importWarning({
              type: 'async_slice_parse_error',
              message: 'At ' + event.ts + ', a slice of the same id ' + id +
                  ' was alrady open.'
            });
            continue;
          }
          asyncEventStatesByNameThenID[name][id] = [];
          asyncEventStatesByNameThenID[name][id].push(asyncEventState);
        } else {
          if (asyncEventStatesByNameThenID[name] === undefined) {
            this.model_.importWarning({
              type: 'async_slice_parse_error',
              message: 'At ' + event.ts + ', no slice named ' + name +
                  ' was open.'
            });
            continue;
          }
          if (asyncEventStatesByNameThenID[name][id] === undefined) {
            this.model_.importWarning({
              type: 'async_slice_parse_error',
              message: 'At ' + event.ts + ', no slice named ' + name +
                  ' with id=' + id + ' was open.'
            });
            continue;
          }
          var events = asyncEventStatesByNameThenID[name][id];
          events.push(asyncEventState);

          if (event.ph === 'F') {
            // Create a slice from start to end.
            var asyncSliceConstructor =
               tr.model.AsyncSlice.getConstructor(
                  events[0].event.cat,
                  name);
            var slice = new asyncSliceConstructor(
                events[0].event.cat,
                name,
                tr.b.ui.getColorIdForGeneralPurposeString(name),
                events[0].event.ts / 1000,
                tr.b.concatenateObjects(events[0].event.args,
                                      events[events.length - 1].event.args),
                (event.ts - events[0].event.ts) / 1000,
                true);
            slice.startThread = events[0].thread;
            slice.endThread = asyncEventState.thread;
            slice.id = id;

            var stepType = events[1].event.ph;
            var isValid = true;

            // Create subSlices for each step. Skip the start and finish events,
            // which are always first and last respectively.
            for (var j = 1; j < events.length - 1; ++j) {
              if (events[j].event.ph === 'T' || events[j].event.ph === 'p') {
                isValid = this.assertStepTypeMatches_(stepType, events[j]);
                if (!isValid)
                  break;
              }

              if (events[j].event.ph === 'S') {
                this.model_.importWarning({
                  type: 'async_slice_parse_error',
                  message: 'At ' + event.event.ts + ', a slice named ' +
                      event.event.name + ' with id=' + event.event.id +
                      ' had a step before the start event.'
                });
                continue;
              }

              if (events[j].event.ph === 'F') {
                this.model_.importWarning({
                  type: 'async_slice_parse_error',
                  message: 'At ' + event.event.ts + ', a slice named ' +
                      event.event.name + ' with id=' + event.event.id +
                      ' had a step after the finish event.'
                });
                continue;
              }

              var startIndex = j + (stepType === 'T' ? 0 : -1);
              var endIndex = startIndex + 1;

              var subName = events[j].event.name;
              if (events[j].event.ph === 'T' || events[j].event.ph === 'p')
                subName = subName + ':' + events[j].event.args.step;

              var asyncSliceConstructor =
                 tr.model.AsyncSlice.getConstructor(
                    events[0].event.cat,
                    subName);
              var subSlice = new asyncSliceConstructor(
                  events[0].event.cat,
                  subName,
                  tr.b.ui.getColorIdForGeneralPurposeString(subName + j),
                  events[startIndex].event.ts / 1000,
                  this.deepCopyIfNeeded_(events[j].event.args),
                  (events[endIndex].event.ts - events[startIndex].event.ts) /
                      1000);
              subSlice.startThread = events[startIndex].thread;
              subSlice.endThread = events[endIndex].thread;
              subSlice.id = id;

              slice.subSlices.push(subSlice);
            }

            if (isValid) {
              // Add |slice| to the start-thread's asyncSlices.
              slice.startThread.asyncSliceGroup.push(slice);
            }

            delete asyncEventStatesByNameThenID[name][id];
          }
        }
      }
    },

    assertStepTypeMatches_: function(stepType, event) {
      if (stepType != event.event.ph) {
        this.model_.importWarning({
          type: 'async_slice_parse_error',
          message: 'At ' + event.event.ts + ', a slice named ' +
              event.event.name + ' with id=' + event.event.id +
              ' had both begin and end steps, which is not allowed.'
        });
        return false;
      }
      return true;
    },

    createFlowSlices_: function() {
      if (this.allFlowEvents_.length === 0)
        return;

      var that = this;

      function validateFlowEvent() {
        if (event.name === undefined) {
          that.model_.importWarning({
            type: 'flow_slice_parse_error',
            message: 'Flow events (ph: s, t or f) require a name parameter.'
          });
          return false;
        }

        if (event.id === undefined) {
          that.model_.importWarning({
            type: 'flow_slice_parse_error',
            message: 'Flow events (ph: s, t or f) require an id parameter.'
          });
          return false;
        }
        return true;
      }

      function createFlowEvent(thread, event, refGuid) {
        var startSlice = thread.sliceGroup.findSliceAtTs(event.ts / 1000);
        if (startSlice === undefined)
          return undefined;

        var flowEvent = new tr.model.FlowEvent(
            event.cat,
            event.id,
            event.name,
            tr.b.ui.getColorIdForGeneralPurposeString(event.name),
            event.ts / 1000,
            that.deepCopyIfNeeded_(event.args));
        flowEvent.startSlice = startSlice;
        startSlice.outFlowEvents.push(flowEvent);
        return flowEvent;
      }

      function finishFlowEventWith(flowEvent, thread, event,
                                   refGuid, bindToParent) {
        // TODO(nduca): Figure out endSlice from ts and binding point.
        var endSlice;
        if (bindToParent) {
          endSlice = thread.sliceGroup.findSliceAtTs(event.ts / 1000);
        } else {
          endSlice = thread.sliceGroup.findNextSliceAfter(
              event.ts / 1000, refGuid);
        }
        if (endSlice === undefined)
          return false;
        endSlice.inFlowEvents.push(flowEvent);

        // Modify the flowEvent with the new data.
        flowEvent.endSlice = endSlice;
        flowEvent.duration = (event.ts / 1000) - flowEvent.start;
        that.mergeArgsInto_(flowEvent.args, event.args, flowEvent.title);
        return true;
      }

      // Actual import.
      this.allFlowEvents_.sort(function(x, y) {
        var d = x.event.ts - y.event.ts;
        if (d != 0)
          return d;
        return x.sequenceNumber - y.sequenceNumber;
      });

      var flowIdToEvent = {};
      for (var i = 0; i < this.allFlowEvents_.length; ++i) {
        var data = this.allFlowEvents_[i];
        var refGuid = data.refGuid;
        var event = data.event;
        var thread = data.thread;
        if (!validateFlowEvent(event))
          continue;

        var flowEvent;
        if (event.ph === 's') {
          if (flowIdToEvent[event.id]) {
            this.model_.importWarning({
              type: 'flow_slice_start_error',
              message: 'event id ' + event.id + ' already seen when ' +
                  'encountering start of flow event.'});
            continue;
          }
          flowEvent = createFlowEvent(thread, event, refGuid);
          if (!flowEvent) {
            this.model_.importWarning({
              type: 'flow_slice_start_error',
              message: 'event id ' + event.id + ' does not start ' +
                  'at an actual slice, so cannot be created.'});
            continue;
          }
          flowIdToEvent[event.id] = flowEvent;

        } else if (event.ph === 't' || event.ph === 'f') {
          flowEvent = flowIdToEvent[event.id];
          if (flowEvent === undefined) {
            this.model_.importWarning({
              type: 'flow_slice_ordering_error',
              message: 'Found flow phase ' + event.ph + ' for id: ' + event.id +
                  ' but no flow start found.'
            });
            continue;
          }

          var bindToParent = event.ph === 't';

          if (event.ph === 'f') {
            if (event.bp === undefined) {
              // Hack: input latency flow events used to be issued without
              // bp='e' letter in old traces. But, we still want their flow
              // events to parse "properly." This adjusts their binding point
              // so that they parse.
              //
              // TODO(nduca): Removal of this hack is tracked in
              // https://github.com/google/trace-viewer/issues/991.
              if (event.cat.indexOf('input') > -1)
                bindToParent = true;
            } else {
              if (event.bp !== 'e') {
                this.model_.importWarning({
                 type: 'flow_slice_bind_point_error',
                 message: 'Flow event with invalid binding point (event.bp).'
                });
                continue;
              }
              bindToParent = true;
            }
          }

          var ok = finishFlowEventWith(flowEvent, thread, event,
                                       refGuid, bindToParent);
          if (ok) {
            that.model_.flowEvents.push(flowEvent);
          } else {
            this.model_.importWarning({
              type: 'flow_slice_start_error',
              message: 'event id ' + event.id + ' does not end ' +
                  'at an actual slice, so cannot be created.'});
          }

          flowIdToEvent[event.id] = undefined;

          // If this is a step, then create another flow event.
          if (ok && event.ph === 't') {
            flowEvent = createFlowEvent(thread, event);
            flowIdToEvent[event.id] = flowEvent;
          }
        }
      }
    },

    /**
     * This function creates objects described via the N, D, and O phase
     * events.
     */
    createExplicitObjects_: function() {
      if (this.allObjectEvents_.length == 0)
        return;

      function processEvent(objectEventState) {
        var event = objectEventState.event;
        var thread = objectEventState.thread;
        if (event.name === undefined) {
          this.model_.importWarning({
            type: 'object_parse_error',
            message: 'While processing ' + JSON.stringify(event) + ': ' +
                'Object events require an name parameter.'
          });
        }

        if (event.id === undefined) {
          this.model_.importWarning({
            type: 'object_parse_error',
            message: 'While processing ' + JSON.stringify(event) + ': ' +
                'Object events require an id parameter.'
          });
        }
        var process = thread.parent;
        var ts = event.ts / 1000;
        var instance;
        if (event.ph == 'N') {
          try {
            instance = process.objects.idWasCreated(
                event.id, event.cat, event.name, ts);
          } catch (e) {
            this.model_.importWarning({
              type: 'object_parse_error',
              message: 'While processing create of ' +
                  event.id + ' at ts=' + ts + ': ' + e
            });
            return;
          }
        } else if (event.ph == 'O') {
          if (event.args.snapshot === undefined) {
            this.model_.importWarning({
              type: 'object_parse_error',
              message: 'While processing ' + event.id + ' at ts=' + ts + ': ' +
                  'Snapshots must have args: {snapshot: ...}'
            });
            return;
          }
          var snapshot;
          try {
            var args = this.deepCopyIfNeeded_(event.args.snapshot);
            var cat;
            if (args.cat) {
              cat = args.cat;
              delete args.cat;
            } else {
              cat = event.cat;
            }

            var baseTypename;
            if (args.base_type) {
              baseTypename = args.base_type;
              delete args.base_type;
            } else {
              baseTypename = undefined;
            }
            snapshot = process.objects.addSnapshot(
                event.id, cat, event.name, ts,
                args, baseTypename);
            snapshot.snapshottedOnThread = thread;
          } catch (e) {
            this.model_.importWarning({
              type: 'object_parse_error',
              message: 'While processing snapshot of ' +
                  event.id + ' at ts=' + ts + ': ' + e
            });
            return;
          }
          instance = snapshot.objectInstance;
        } else if (event.ph == 'D') {
          try {
            instance = process.objects.idWasDeleted(
                event.id, event.cat, event.name, ts);
          } catch (e) {
            this.model_.importWarning({
              type: 'object_parse_error',
              message: 'While processing delete of ' +
                  event.id + ' at ts=' + ts + ': ' + e
            });
            return;
          }
        }

        if (instance) {
          instance.colorId = tr.b.ui.getColorIdForGeneralPurposeString(
              instance.typeName);
        }
      }

      this.allObjectEvents_.sort(function(x, y) {
        var d = x.event.ts - y.event.ts;
        if (d != 0)
          return d;
        return x.sequenceNumber - y.sequenceNumber;
      });

      var allObjectEvents = this.allObjectEvents_;
      for (var i = 0; i < allObjectEvents.length; i++) {
        var objectEventState = allObjectEvents[i];
        try {
          processEvent.call(this, objectEventState);
        } catch (e) {
          this.model_.importWarning({
            type: 'object_parse_error',
            message: e.message
          });
        }
      }
    },

    createImplicitObjects_: function() {
      tr.b.iterItems(this.model_.processes, function(pid, process) {
        this.createImplicitObjectsForProcess_(process);
      }, this);
    },

    // Here, we collect all the snapshots that internally contain a
    // Javascript-level object inside their args list that has an "id" field,
    // and turn that into a snapshot of the instance referred to by id.
    createImplicitObjectsForProcess_: function(process) {

      function processField(referencingObject,
                            referencingObjectFieldName,
                            referencingObjectFieldValue,
                            containingSnapshot) {
        if (!referencingObjectFieldValue)
          return;

        if (referencingObjectFieldValue instanceof
            tr.model.ObjectSnapshot)
          return null;
        if (referencingObjectFieldValue.id === undefined)
          return;

        var implicitSnapshot = referencingObjectFieldValue;

        var rawId = implicitSnapshot.id;
        var m = /(.+)\/(.+)/.exec(rawId);
        if (!m)
          throw new Error('Implicit snapshots must have names.');
        delete implicitSnapshot.id;
        var name = m[1];
        var id = m[2];
        var res;

        var cat;
        if (implicitSnapshot.cat !== undefined)
          cat = implicitSnapshot.cat;
        else
          cat = containingSnapshot.objectInstance.category;

        var baseTypename;
        if (implicitSnapshot.base_type)
          baseTypename = implicitSnapshot.base_type;
        else
          baseTypename = undefined;

        try {
          res = process.objects.addSnapshot(
              id, cat,
              name, containingSnapshot.ts,
              implicitSnapshot, baseTypename);
        } catch (e) {
          this.model_.importWarning({
            type: 'object_snapshot_parse_error',
            message: 'While processing implicit snapshot of ' +
                rawId + ' at ts=' + containingSnapshot.ts + ': ' + e
          });
          return;
        }
        res.objectInstance.hasImplicitSnapshots = true;
        res.containingSnapshot = containingSnapshot;
        res.snapshottedOnThread = containingSnapshot.snapshottedOnThread;
        referencingObject[referencingObjectFieldName] = res;
        if (!(res instanceof tr.model.ObjectSnapshot))
          throw new Error('Created object must be instanceof snapshot');
        return res.args;
      }

      /**
       * Iterates over the fields in the object, calling func for every
       * field/value found.
       *
       * @return {object} If the function does not want the field's value to be
       * iterated, return null. If iteration of the field value is desired, then
       * return either undefined (if the field value did not change) or the new
       * field value if it was changed.
       */
      function iterObject(object, func, containingSnapshot, thisArg) {
        if (!(object instanceof Object))
          return;

        if (object instanceof Array) {
          for (var i = 0; i < object.length; i++) {
            var res = func.call(thisArg, object, i, object[i],
                                containingSnapshot);
            if (res === null)
              continue;
            if (res)
              iterObject(res, func, containingSnapshot, thisArg);
            else
              iterObject(object[i], func, containingSnapshot, thisArg);
          }
          return;
        }

        for (var key in object) {
          var res = func.call(thisArg, object, key, object[key],
                              containingSnapshot);
          if (res === null)
            continue;
          if (res)
            iterObject(res, func, containingSnapshot, thisArg);
          else
            iterObject(object[key], func, containingSnapshot, thisArg);
        }
      }

      // TODO(nduca): We may need to iterate the instances in sorted order by
      // creationTs.
      process.objects.iterObjectInstances(function(instance) {
        instance.snapshots.forEach(function(snapshot) {
          if (snapshot.args.id !== undefined)
            throw new Error('args cannot have an id field inside it');
          iterObject(snapshot.args, processField, snapshot, this);
        }, this);
      }, this);
    },

    createMemoryDumps_: function() {
      tr.b.iterItems(this.allMemoryDumpEvents_, function(id, events) {
        // Calculate the range of the global memory dump.
        var range = new tr.b.Range();
        if (events.global !== undefined)
          range.addValue(events.global.ts / 1000);
        for (var i = 0; i < events.process.length; i++)
          range.addValue(events.process[i].ts / 1000);

        // Create the global memory dump.
        var globalMemoryDump = new tr.model.GlobalMemoryDump(
            this.model_, range.min);
        globalMemoryDump.duration = range.range;
        this.model_.globalMemoryDumps.push(globalMemoryDump);

        // Create individual process memory dumps.
        if (events.process.length === 0) {
          this.model_.importWarning({
              type: 'memory_dump_parse_error',
              message: 'No process memory dumps associated with global memory' +
                  ' dump ' + id + '.'
          });
        }

        var allMemoryAllocatorDumpsByGuid = {};
        var globalMemoryAllocatorDumpsByFullName = {};

        events.process.forEach(function(processEvent) {
          var pid = processEvent.pid;
          if (pid in globalMemoryDump.processMemoryDumps) {
            this.model_.importWarning({
              type: 'memory_dump_parse_error',
              message: 'Multiple process memory dumps with pid=' + pid +
                  ' for dump id ' + id + '.'
            });
            return;
          }

          var dumps = processEvent.args.dumps;
          if (dumps === undefined) {
            this.model_.importWarning({
                type: 'memory_dump_parse_error',
                message: 'dumps not found in process memory dump for ' +
                    'pid=' + pid + ' and dump id=' + id + '.'
            });
            return;
          }

          var process = this.model_.getOrCreateProcess(pid);
          var processMemoryDump = new tr.model.ProcessMemoryDump(
              globalMemoryDump, process, processEvent.ts / 1000);

          // Parse the totals, which are mandatory.
          if (dumps.process_totals === undefined ||
              dumps.process_totals.resident_set_bytes === undefined) {
            this.model_.importWarning({
                type: 'memory_dump_parse_error',
                message: 'Mandatory field resident_set_bytes not found in' +
                    ' process memory dump for pid=' + pid +
                    ' and dump id=' + id + '.'
            });
            processMemoryDump.totalResidentBytes = undefined;
          } else {
            processMemoryDump.totalResidentBytes = parseInt(
                dumps.process_totals.resident_set_bytes, 16);
          }

          // Populate the vmRegions, if present.
          if (dumps.process_mmaps && dumps.process_mmaps.vm_regions) {
            function parseByteStat(rawValue) {
              if (rawValue === undefined)
                return undefined;
              return parseInt(rawValue, 16);
            }

            processMemoryDump.vmRegions = dumps.process_mmaps.vm_regions.map(
              function(rawRegion) {
                // See //base/trace_event/process_memory_maps.cc in Chromium.
                var byteStats = new tr.model.VMRegionByteStats(
                  parseByteStat(rawRegion.bs.pc),
                  parseByteStat(rawRegion.bs.pd),
                  parseByteStat(rawRegion.bs.sc),
                  parseByteStat(rawRegion.bs.sd),
                  parseByteStat(rawRegion.bs.pss),
                  parseByteStat(rawRegion.bs.sw)
                );
                return new tr.model.VMRegion(
                    parseInt(rawRegion.sa, 16),  // startAddress
                    parseInt(rawRegion.sz, 16),  // sizeInBytes
                    rawRegion.pf,  // protectionFlags
                    rawRegion.mf,  // mappedFile
                    byteStats
                );
              }
            );
          }

          // Gather the process and global memory allocator dumps, if present.
          var processMemoryAllocatorDumpsByFullName = {};
          if (dumps.allocators !== undefined) {
            // Construct the MemoryAllocatorDump objects without parent links
            // and add them to the processMemoryAllocatorDumpsByName and
            // globalMemoryAllocatorDumpsByName indices appropriately.
            tr.b.iterItems(dumps.allocators,
                function(fullName, rawAllocatorDump) {
              // Every memory allocator dump should have a GUID. If not, then
              // it cannot be associated with any edges.
              var guid = rawAllocatorDump.guid;
              if (guid === undefined) {
                this.model_.importWarning({
                  type: 'memory_dump_parse_error',
                  message: 'Memory allocator dump ' + fullName +
                      ' from pid=' + pid + ' does not have a GUID.'
                });
              }

              // Determine if this is a global memory allocator dump (check if
              // it's prefixed with 'global/').
              var GLOBAL_MEMORY_ALLOCATOR_DUMP_PREFIX = 'global/';
              var containerMemoryDump;
              var dstIndex;
              if (fullName.startsWith(GLOBAL_MEMORY_ALLOCATOR_DUMP_PREFIX)) {
                // Global memory allocator dump.
                fullName = fullName.substring(
                    GLOBAL_MEMORY_ALLOCATOR_DUMP_PREFIX.length);
                containerMemoryDump = globalMemoryDump;
                dstIndex = globalMemoryAllocatorDumpsByFullName;
              } else {
                // Process memory allocator dump.
                containerMemoryDump = processMemoryDump;
                dstIndex = processMemoryAllocatorDumpsByFullName;
              }

              // Construct or retrieve a memory allocator dump with the provided
              // GUID.
              var allocatorDump = allMemoryAllocatorDumpsByGuid[guid];
              if (allocatorDump === undefined) {
                if (fullName in dstIndex) {
                  this.model_.importWarning({
                    type: 'memory_dump_parse_error',
                    message: 'Multiple GUIDs provided for' +
                        ' memory allocator dump ' + fullName + ': ' +
                        dstIndex[fullName].guid + ', ' + guid + ' (ignored).'
                  });
                  return;
                }
                allocatorDump = new tr.model.MemoryAllocatorDump(
                    containerMemoryDump, fullName, guid);
                dstIndex[fullName] = allocatorDump;
                if (guid !== undefined)
                  allMemoryAllocatorDumpsByGuid[guid] = allocatorDump;
              } else {
                // A memory allocator dump with this GUID has already been
                // dumped (so we will only add new attributes). Check that it
                // belonged to the same process or was also global.
                if (allocatorDump.containerMemoryDump !== containerMemoryDump) {
                  this.model_.importWarning({
                  type: 'memory_dump_parse_error',
                  message: 'Memory allocator dump ' + fullName +
                      ' (GUID=' + guid + ') dumped in different contexts.'
                  });
                  return;
                }
                // Check that the names of the memory allocator dumps match.
                if (allocatorDump.fullName !== fullName) {
                  this.model_.importWarning({
                  type: 'memory_dump_parse_error',
                  message: 'Memory allocator dump with GUID=' + guid +
                      ' has multiple names: ' + allocatorDump.fullName +
                      ', ' + fullName + ' (ignored).'
                  });
                  return;
                }
              }

              // Add all new attributes to the memory allocator dump.
              var attributes = rawAllocatorDump.attrs;
              tr.b.iterItems(attributes, function(attrName, attrArgs) {
                if (attrName in allocatorDump.attributes) {
                  // Skip existing attributes of the memory allocator dump.
                  this.model_.importWarning({
                  type: 'memory_dump_parse_error',
                  message: 'Multiple values provided for attribute ' +
                      attrName + ' of memory allocator dump ' + fullName +
                      ' (GUID=' + guid + ').'
                  });
                  return;
                }
                var attrValue =
                    tr.model.Attribute.fromDictIfPossible(attrArgs);
                allocatorDump.addAttribute(attrName, attrValue);
              }, this);
            }, this);
          }

          // Find the root allocator dumps and establish the parent links of
          // the process memory dump.
          processMemoryDump.memoryAllocatorDumps =
              this.inferMemoryAllocatorDumpTree_(
                  processMemoryAllocatorDumpsByFullName);

          process.memoryDumps.push(processMemoryDump);
          globalMemoryDump.processMemoryDumps[pid] = processMemoryDump;
        }, this);

        // Find the root allocator dumps and establish the parent links of
        // the global memory dump.
        globalMemoryDump.memoryAllocatorDumps =
            this.inferMemoryAllocatorDumpTree_(
                globalMemoryAllocatorDumpsByFullName);

        // Set up edges between memory allocator dumps.
        events.process.forEach(function(processEvent) {
          var dumps = processEvent.args.dumps;
          if (dumps === undefined)
            return;

          var edges = dumps.edges;
          if (edges === undefined)
            return;

          edges.forEach(function(rawEdge) {
            var sourceGuid = rawEdge.source;
            var sourceDump = allMemoryAllocatorDumpsByGuid[sourceGuid];
            if (sourceDump === undefined) {
              this.model_.importWarning({
                type: 'memory_dump_parse_error',
                message: 'Edge is missing source memory allocator dump (GUID=' +
                    sourceGuid + ')'
              });
              return;
            }

            var targetGuid = rawEdge.target;
            var targetDump = allMemoryAllocatorDumpsByGuid[targetGuid];
            if (targetDump === undefined) {
              this.model_.importWarning({
                type: 'memory_dump_parse_error',
                message: 'Edge is missing target memory allocator dump (GUID=' +
                    targetGuid + ')'
              });
              return;
            }

            var importance = rawEdge.importance;
            var edge = new tr.model.MemoryAllocatorDumpLink(
                sourceDump, targetDump, importance);

            switch (rawEdge.type) {
              case 'ownership':
                if (sourceDump.owns !== undefined) {
                  this.model_.importWarning({
                    type: 'memory_dump_parse_error',
                    message: 'Memory allocator dump ' + sourceDump.fullName +
                        ' (GUID=' + sourceGuid + ') already owns a memory' +
                        ' allocator dump (' +
                        sourceDump.owns.target.fullName + ').'
                  });
                  return;
                }
                sourceDump.owns = edge;
                targetDump.ownedBy.push(edge);
                break;

              case 'retention':
                sourceDump.retains.push(edge);
                targetDump.retainedBy.push(edge);
                break;

              default:
                this.model_.importWarning({
                  type: 'memory_dump_parse_error',
                  message: 'Invalid edge type: ' + rawEdge.type +
                      ' (source=' + sourceGuid + ', target=' + targetGuid +
                      ', importance=' + importance + ').'
                });
            }
          }, this);
        }, this);
      }, this);
    },

    inferMemoryAllocatorDumpTree_: function(memoryAllocatorDumpsByFullName) {
      var rootAllocatorDumps = [];

      var fullNames = Object.keys(memoryAllocatorDumpsByFullName);
      fullNames.sort();
      fullNames.forEach(function(fullName) {
        var allocatorDump = memoryAllocatorDumpsByFullName[fullName];

        // This is a loop because we might need to build implicit
        // ancestors in case they were not present in the trace.
        while (true) {
          var lastSlashIndex = fullName.lastIndexOf('/');
          if (lastSlashIndex === -1) {
            // If the dump is a root, add it to the top-level
            // rootAllocatorDumps list.
            rootAllocatorDumps.push(allocatorDump);
            break;
          }

          // If the dump is not a root, find its parent.
          var parentFullName = fullName.substring(0, lastSlashIndex);
          var parentAllocatorDump =
              memoryAllocatorDumpsByFullName[parentFullName];

          // If the parent dump does not exist yet, we build an implicit
          // one and continue up the ancestor chain.
          var parentAlreadyExisted = true;
          if (parentAllocatorDump === undefined) {
            parentAlreadyExisted = false;
            parentAllocatorDump = new tr.model.MemoryAllocatorDump(
                allocatorDump.containerMemoryDump, parentFullName);
            memoryAllocatorDumpsByFullName[parentFullName] =
                parentAllocatorDump;
          }

          // Setup the parent <-> children relationships
          allocatorDump.parent = parentAllocatorDump;
          parentAllocatorDump.children.push(allocatorDump);

          // If the parent already existed, then its ancestors were/will be
          // constructed in another iteration of the forEach loop.
          if (parentAlreadyExisted)
            break;

          fullName = parentFullName;
          allocatorDump = parentAllocatorDump;
        }
      }, this);

      return rootAllocatorDumps;
    },

    joinObjectRefs_: function() {
      tr.b.iterItems(this.model_.processes, function(pid, process) {
        this.joinObjectRefsForProcess_(process);
      }, this);
    },

    joinObjectRefsForProcess_: function(process) {
      // Iterate the world, looking for id_refs
      var patchupsToApply = [];
      tr.b.iterItems(process.threads, function(tid, thread) {
        thread.asyncSliceGroup.slices.forEach(function(item) {
          this.searchItemForIDRefs_(
              patchupsToApply, process.objects, 'start', item);
        }, this);
        thread.sliceGroup.slices.forEach(function(item) {
          this.searchItemForIDRefs_(
              patchupsToApply, process.objects, 'start', item);
        }, this);
      }, this);
      process.objects.iterObjectInstances(function(instance) {
        instance.snapshots.forEach(function(item) {
          this.searchItemForIDRefs_(
              patchupsToApply, process.objects, 'ts', item);
        }, this);
      }, this);

      // Change all the fields pointing at id_refs to their real values.
      patchupsToApply.forEach(function(patchup) {
        patchup.object[patchup.field] = patchup.value;
      });
    },

    searchItemForIDRefs_: function(patchupsToApply, objectCollection,
                                   itemTimestampField, item) {
      if (!item.args)
        throw new Error('item is missing its args');

      function handleField(object, fieldName, fieldValue) {
        if (!fieldValue || (!fieldValue.id_ref && !fieldValue.idRef))
          return;

        var id = fieldValue.id_ref || fieldValue.idRef;
        var ts = item[itemTimestampField];
        var snapshot = objectCollection.getSnapshotAt(id, ts);
        if (!snapshot)
          return;

        // We have to delay the actual change to the new value until after all
        // refs have been located. Otherwise, we could end up recursing in
        // ways we definitely didn't intend.
        patchupsToApply.push({object: object,
          field: fieldName,
          value: snapshot});
      }
      function iterObjectFieldsRecursively(object) {
        if (!(object instanceof Object))
          return;

        if ((object instanceof tr.model.ObjectSnapshot) ||
            (object instanceof Float32Array) ||
            (object instanceof tr.b.Quad))
          return;

        if (object instanceof Array) {
          for (var i = 0; i < object.length; i++) {
            handleField(object, i, object[i]);
            iterObjectFieldsRecursively(object[i]);
          }
          return;
        }

        for (var key in object) {
          var value = object[key];
          handleField(object, key, value);
          iterObjectFieldsRecursively(value);
        }
      }

      iterObjectFieldsRecursively(item.args);
    }
  };

  tr.importer.Importer.register(TraceEventImporter);

  return {
    TraceEventImporter: TraceEventImporter
  };
});
</script>