1<!DOCTYPE html>
2<!--
3Copyright (c) 2012 The Chromium Authors. All rights reserved.
4Use of this source code is governed by a BSD-style license that can be
5found in the LICENSE file.
6-->
7
8<link rel="import" href="/tracing/base/base64.html">
9<link rel="import" href="/tracing/base/color_scheme.html">
10<link rel="import" href="/tracing/base/range.html">
11<link rel="import" href="/tracing/base/utils.html">
12<link rel="import" href="/tracing/extras/importer/trace_code_entry.html">
13<link rel="import" href="/tracing/extras/importer/trace_code_map.html">
14<link rel="import" href="/tracing/extras/importer/v8/codemap.html">
15<link rel="import" href="/tracing/importer/importer.html">
16<link rel="import" href="/tracing/model/clock_sync_record.html">
17<link rel="import" href="/tracing/model/comment_box_annotation.html">
18<link rel="import" href="/tracing/model/constants.html">
19<link rel="import" href="/tracing/model/counter_series.html">
20<link rel="import" href="/tracing/model/flow_event.html">
21<link rel="import" href="/tracing/model/global_memory_dump.html">
22<link rel="import" href="/tracing/model/heap_dump.html">
23<link rel="import" href="/tracing/model/instant_event.html">
24<link rel="import" href="/tracing/model/memory_allocator_dump.html">
25<link rel="import" href="/tracing/model/model.html">
26<link rel="import" href="/tracing/model/process_memory_dump.html">
27<link rel="import" href="/tracing/model/rect_annotation.html">
28<link rel="import" href="/tracing/model/scoped_id.html">
29<link rel="import" href="/tracing/model/slice_group.html">
30<link rel="import" href="/tracing/model/vm_region.html">
31<link rel="import" href="/tracing/model/x_marker_annotation.html">
32<link rel="import" href="/tracing/value/numeric.html">
33<link rel="import" href="/tracing/value/unit.html">
34
35<script>
36'use strict';
37
38/**
39 * @fileoverview TraceEventImporter imports TraceEvent-formatted data
40 * into the provided model.
41 */
42tr.exportTo('tr.e.importer', function() {
43  var Base64 = tr.b.Base64;
44  var deepCopy = tr.b.deepCopy;
45  var ColorScheme = tr.b.ColorScheme;
46
47  function getEventColor(event, opt_customName) {
48    if (event.cname)
49      return ColorScheme.getColorIdForReservedName(event.cname);
50    else if (opt_customName || event.name) {
51      return ColorScheme.getColorIdForGeneralPurposeString(
52          opt_customName || event.name);
53    }
54  }
55
56  var timestampFromUs = tr.v.Unit.timestampFromUs;
57  var maybeTimestampFromUs = tr.v.Unit.maybeTimestampFromUs;
58
59  var PRODUCER = 'producer';
60  var CONSUMER = 'consumer';
61  var STEP = 'step';
62
63  var MEMORY_DUMP_LEVELS_OF_DETAIL = [undefined, 'light', 'detailed'];
64  var GLOBAL_MEMORY_ALLOCATOR_DUMP_PREFIX = 'global/';
65
66  // Map from raw memory dump byte stat names to model byte stat names. See
67  // //base/trace_event/process_memory_maps.cc in Chromium.
68  var BYTE_STAT_NAME_MAP = {
69    'pc': 'privateCleanResident',
70    'pd': 'privateDirtyResident',
71    'sc': 'sharedCleanResident',
72    'sd': 'sharedDirtyResident',
73    'pss': 'proportionalResident',
74    'sw': 'swapped'
75  };
76
77  // See tr.model.MemoryAllocatorDump 'weak' field and
78  // base::trace_event::MemoryAllocatorDump::Flags::WEAK in the Chromium
79  // codebase.
80  var WEAK_MEMORY_ALLOCATOR_DUMP_FLAG = 1 << 0;
81
82  // Object type name patterns for various compilers.
83  var OBJECT_TYPE_NAME_PATTERNS = [
84    {
85      // Clang.
86      prefix: 'const char *WTF::getStringWithTypeName() [T = ',
87      suffix: ']'
88    },
89    {
90      // GCC.
91      prefix: 'const char* WTF::getStringWithTypeName() [with T = ',
92      suffix: ']'
93    },
94    {
95      // Microsoft Visual C++
96      prefix: 'const char *__cdecl WTF::getStringWithTypeName<',
97      suffix: '>(void)'
98    }
99  ];
100
101  function TraceEventImporter(model, eventData) {
102    this.importPriority = 1;
103    this.model_ = model;
104    this.events_ = undefined;
105    this.sampleEvents_ = undefined;
106    this.stackFrameEvents_ = undefined;
107    this.systemTraceEvents_ = undefined;
108    this.battorData_ = undefined;
109    this.eventsWereFromString_ = false;
110    this.softwareMeasuredCpuCount_ = undefined;
111
112    this.allAsyncEvents_ = [];
113    this.allFlowEvents_ = [];
114    this.allObjectEvents_ = [];
115
116    this.traceEventSampleStackFramesByName_ = {};
117
118    this.v8ProcessCodeMaps_ = {};
119    this.v8ProcessRootStackFrame_ = {};
120    this.v8SamplingData_ = [];
121
122    // Dump ID -> PID -> [process memory dump events].
123    this.allMemoryDumpEvents_ = {};
124
125    // PID -> Object type ID -> Object type name.
126    this.objectTypeNameMap_ = {};
127
128    if (typeof(eventData) === 'string' || eventData instanceof String) {
129      eventData = eventData.trim();
130      // If the event data begins with a [, then we know it should end with a ].
131      // The reason we check for this is because some tracing implementations
132      // cannot guarantee that a ']' gets written to the trace file. So, we are
133      // forgiving and if this is obviously the case, we fix it up before
134      // throwing the string at JSON.parse.
135      if (eventData[0] === '[') {
136        eventData = eventData.replace(/\s*,\s*$/, '');
137        if (eventData[eventData.length - 1] !== ']')
138          eventData = eventData + ']';
139      }
140
141      this.events_ = JSON.parse(eventData);
142      this.eventsWereFromString_ = true;
143    } else {
144      this.events_ = eventData;
145    }
146
147    this.traceAnnotations_ = this.events_.traceAnnotations;
148
149    // Some trace_event implementations put the actual trace events
150    // inside a container. E.g { ... , traceEvents: [ ] }
151    // If we see that, just pull out the trace events.
152    if (this.events_.traceEvents) {
153      var container = this.events_;
154      this.events_ = this.events_.traceEvents;
155
156      // Some trace_event implementations put ftrace_importer traces as a
157      // huge string inside container.systemTraceEvents. If we see that, pull it
158      // out. It will be picked up by extractSubtraces later on.
159      this.systemTraceEvents_ = container.systemTraceEvents;
160
161      // Some trace_event implementations put battor power traces as a
162      // huge string inside container.powerTraceAsString. If we see that, pull
163      // it out. It will be picked up by extractSubtraces later on.
164      this.battorData_ = container.powerTraceAsString;
165
166      // Sampling data.
167      this.sampleEvents_ = container.samples;
168      this.stackFrameEvents_ = container.stackFrames;
169
170      // Some implementations specify displayTimeUnit
171      if (container.displayTimeUnit) {
172        var unitName = container.displayTimeUnit;
173        var unit = tr.v.TimeDisplayModes[unitName];
174        if (unit === undefined) {
175          throw new Error('Unit ' + unitName + ' is not supported.');
176        }
177        this.model_.intrinsicTimeUnit = unit;
178      }
179
180      var knownFieldNames = {
181        powerTraceAsString: true,
182        samples: true,
183        stackFrames: true,
184        systemTraceEvents: true,
185        traceAnnotations: true,
186        traceEvents: true
187      };
188      // Any other fields in the container should be treated as metadata.
189      for (var fieldName in container) {
190        if (fieldName in knownFieldNames)
191          continue;
192        this.model_.metadata.push({name: fieldName,
193          value: container[fieldName]});
194        if (fieldName === 'metadata' && container[fieldName]['highres-ticks']) {
195          this.model_.isTimeHighResolution =
196              container[fieldName]['highres-ticks'];
197        }
198      }
199    }
200  }
201
202  /**
203   * @return {boolean} Whether obj is a TraceEvent array.
204   */
205  TraceEventImporter.canImport = function(eventData) {
206    // May be encoded JSON. But we dont want to parse it fully yet.
207    // Use a simple heuristic:
208    //   - eventData that starts with [ are probably trace_event
209    //   - eventData that starts with { are probably trace_event
210    // May be encoded JSON. Treat files that start with { as importable by us.
211    if (typeof(eventData) === 'string' || eventData instanceof String) {
212      eventData = eventData.trim();
213      return eventData[0] === '{' || eventData[0] === '[';
214    }
215
216    // Might just be an array of events
217    if (eventData instanceof Array && eventData.length && eventData[0].ph)
218      return true;
219
220    // Might be an object with a traceEvents field in it.
221    if (eventData.traceEvents) {
222      if (eventData.traceEvents instanceof Array) {
223        if (eventData.traceEvents.length && eventData.traceEvents[0].ph)
224          return true;
225        if (eventData.samples.length && eventData.stackFrames !== undefined)
226          return true;
227      }
228    }
229
230    return false;
231  };
232
233  TraceEventImporter.prototype = {
234    __proto__: tr.importer.Importer.prototype,
235
236    get importerName() {
237      return 'TraceEventImporter';
238    },
239
240    extractSubtraces: function() {
241      var systemEventsTmp = this.systemTraceEvents_;
242      var battorDataTmp = this.battorData_;
243      this.systemTraceEvents_ = undefined;
244      this.battorData_ = undefined;
245      var subTraces = systemEventsTmp ? [systemEventsTmp] : [];
246      if (battorDataTmp)
247        subTraces.push(battorDataTmp);
248       return subTraces;
249    },
250
251    /**
252     * Deep copying is only needed if the trace was given to us as events.
253     */
254    deepCopyIfNeeded_: function(obj) {
255      if (obj === undefined)
256        obj = {};
257      if (this.eventsWereFromString_)
258        return obj;
259      return deepCopy(obj);
260    },
261
262    /**
263     * Always perform deep copying.
264     */
265    deepCopyAlways_: function(obj) {
266      if (obj === undefined)
267        obj = {};
268      return deepCopy(obj);
269    },
270
271    /**
272     * Helper to process an async event.
273     */
274    processAsyncEvent: function(event) {
275      var thread = this.model_.getOrCreateProcess(event.pid).
276          getOrCreateThread(event.tid);
277      this.allAsyncEvents_.push({
278        sequenceNumber: this.allAsyncEvents_.length,
279        event: event,
280        thread: thread
281      });
282    },
283
284    /**
285     * Helper to process a flow event.
286     */
287    processFlowEvent: function(event, opt_slice) {
288      var thread = this.model_.getOrCreateProcess(event.pid).
289          getOrCreateThread(event.tid);
290      this.allFlowEvents_.push({
291        refGuid: tr.b.GUID.getLastGuid(),
292        sequenceNumber: this.allFlowEvents_.length,
293        event: event,
294        slice: opt_slice,  // slice for events that have flow info
295        thread: thread
296      });
297    },
298
299    /**
300     * Helper that creates and adds samples to a Counter object based on
301     * 'C' phase events.
302     */
303    processCounterEvent: function(event) {
304      var ctr_name;
305      if (event.id !== undefined)
306        ctr_name = event.name + '[' + event.id + ']';
307      else
308        ctr_name = event.name;
309
310      var ctr = this.model_.getOrCreateProcess(event.pid)
311          .getOrCreateCounter(event.cat, ctr_name);
312      var reservedColorId = event.cname ? getEventColor(event) : undefined;
313
314      // Initialize the counter's series fields if needed.
315      if (ctr.numSeries === 0) {
316        for (var seriesName in event.args) {
317          var colorId = reservedColorId ||
318              getEventColor(event, ctr.name + '.' + seriesName);
319          ctr.addSeries(new tr.model.CounterSeries(seriesName, colorId));
320        }
321
322        if (ctr.numSeries === 0) {
323          this.model_.importWarning({
324            type: 'counter_parse_error',
325            message: 'Expected counter ' + event.name +
326                ' to have at least one argument to use as a value.'
327          });
328
329          // Drop the counter.
330          delete ctr.parent.counters[ctr.name];
331          return;
332        }
333      }
334
335      var ts = timestampFromUs(event.ts);
336      ctr.series.forEach(function(series) {
337        var val = event.args[series.name] ? event.args[series.name] : 0;
338        series.addCounterSample(ts, val);
339      });
340    },
341
342    processObjectEvent: function(event) {
343      var thread = this.model_.getOrCreateProcess(event.pid).
344          getOrCreateThread(event.tid);
345      this.allObjectEvents_.push({
346        sequenceNumber: this.allObjectEvents_.length,
347        event: event,
348        thread: thread});
349    },
350
351    processDurationEvent: function(event) {
352      var thread = this.model_.getOrCreateProcess(event.pid)
353        .getOrCreateThread(event.tid);
354      var ts = timestampFromUs(event.ts);
355      if (!thread.sliceGroup.isTimestampValidForBeginOrEnd(ts)) {
356        this.model_.importWarning({
357          type: 'duration_parse_error',
358          message: 'Timestamps are moving backward.'
359        });
360        return;
361      }
362
363      if (event.ph === 'B') {
364        var slice = thread.sliceGroup.beginSlice(
365            event.cat, event.name, timestampFromUs(event.ts),
366            this.deepCopyIfNeeded_(event.args),
367            timestampFromUs(event.tts), event.argsStripped,
368            getEventColor(event));
369        slice.startStackFrame = this.getStackFrameForEvent_(event);
370      } else if (event.ph === 'I' || event.ph === 'i' || event.ph === 'R') {
371        if (event.s !== undefined && event.s !== 't')
372          throw new Error('This should never happen');
373
374        thread.sliceGroup.beginSlice(event.cat, event.name,
375                                     timestampFromUs(event.ts),
376                                     this.deepCopyIfNeeded_(event.args),
377                                     timestampFromUs(event.tts),
378                                     event.argsStripped,
379                                     getEventColor(event));
380        var slice = thread.sliceGroup.endSlice(timestampFromUs(event.ts),
381                                   timestampFromUs(event.tts));
382        slice.startStackFrame = this.getStackFrameForEvent_(event);
383        slice.endStackFrame = undefined;
384      } else {
385        if (!thread.sliceGroup.openSliceCount) {
386          this.model_.importWarning({
387            type: 'duration_parse_error',
388            message: 'E phase event without a matching B phase event.'
389          });
390          return;
391        }
392
393        var slice = thread.sliceGroup.endSlice(timestampFromUs(event.ts),
394                                               timestampFromUs(event.tts),
395                                               getEventColor(event));
396        if (event.name && slice.title != event.name) {
397          this.model_.importWarning({
398            type: 'title_match_error',
399            message: 'Titles do not match. Title is ' +
400                slice.title + ' in openSlice, and is ' +
401                event.name + ' in endSlice'
402          });
403        }
404        slice.endStackFrame = this.getStackFrameForEvent_(event);
405
406        this.mergeArgsInto_(slice.args, event.args, slice.title);
407      }
408    },
409
410    mergeArgsInto_: function(dstArgs, srcArgs, eventName) {
411      for (var arg in srcArgs) {
412        if (dstArgs[arg] !== undefined) {
413          this.model_.importWarning({
414            type: 'arg_merge_error',
415            message: 'Different phases of ' + eventName +
416                ' provided values for argument ' + arg + '.' +
417                ' The last provided value will be used.'
418          });
419        }
420        dstArgs[arg] = this.deepCopyIfNeeded_(srcArgs[arg]);
421      }
422    },
423
424    processCompleteEvent: function(event) {
425      // Preventing the overhead slices from making it into the model. This
426      // only applies to legacy traces, as the overhead traces have been
427      // removed from the chromium code.
428      if (event.cat !== undefined &&
429          event.cat.indexOf('trace_event_overhead') > -1)
430        return undefined;
431
432      var thread = this.model_.getOrCreateProcess(event.pid)
433          .getOrCreateThread(event.tid);
434
435      if (event.flow_out) {
436        if (event.flow_in)
437          event.flowPhase = STEP;
438        else
439          event.flowPhase = PRODUCER;
440      } else if (event.flow_in) {
441        event.flowPhase = CONSUMER;
442      }
443
444      var slice = thread.sliceGroup.pushCompleteSlice(event.cat, event.name,
445          timestampFromUs(event.ts),
446          maybeTimestampFromUs(event.dur),
447          maybeTimestampFromUs(event.tts),
448          maybeTimestampFromUs(event.tdur),
449          this.deepCopyIfNeeded_(event.args),
450          event.argsStripped,
451          getEventColor(event),
452          event.bind_id);
453      slice.startStackFrame = this.getStackFrameForEvent_(event);
454      slice.endStackFrame = this.getStackFrameForEvent_(event, true);
455
456      return slice;
457    },
458
459    processJitCodeEvent: function(event) {
460      if (this.v8ProcessCodeMaps_[event.pid] === undefined)
461        this.v8ProcessCodeMaps_[event.pid] = new tr.e.importer.TraceCodeMap();
462      var map = this.v8ProcessCodeMaps_[event.pid];
463
464      var data = event.args.data;
465      // TODO(dsinclair): There are _a lot_ of JitCode events so I'm skipping
466      // the display for now. Can revisit later if we want to show them.
467      // Handle JitCodeMoved and JitCodeAdded event.
468      if (event.name === 'JitCodeMoved')
469        map.moveEntry(data.code_start, data.new_code_start, data.code_len);
470      else  // event.name === 'JitCodeAdded'
471        map.addEntry(data.code_start, data.code_len, data.name, data.script_id);
472    },
473
474    processMetadataEvent: function(event) {
475      // V8 JIT events are currently logged as phase 'M' so we need to
476      // separate them out and handle specially.
477      if (event.name === 'JitCodeAdded' || event.name === 'JitCodeMoved') {
478        this.v8SamplingData_.push(event);
479        return;
480      }
481
482      // The metadata events aren't useful without args.
483      if (event.argsStripped)
484        return;
485
486      if (event.name === 'process_name') {
487        var process = this.model_.getOrCreateProcess(event.pid);
488        process.name = event.args.name;
489      } else if (event.name === 'process_labels') {
490        var process = this.model_.getOrCreateProcess(event.pid);
491        var labels = event.args.labels.split(',');
492        for (var i = 0; i < labels.length; i++)
493          process.addLabelIfNeeded(labels[i]);
494      } else if (event.name === 'process_sort_index') {
495        var process = this.model_.getOrCreateProcess(event.pid);
496        process.sortIndex = event.args.sort_index;
497      } else if (event.name === 'thread_name') {
498        var thread = this.model_.getOrCreateProcess(event.pid).
499            getOrCreateThread(event.tid);
500        thread.name = event.args.name;
501      } else if (event.name === 'thread_sort_index') {
502        var thread = this.model_.getOrCreateProcess(event.pid).
503            getOrCreateThread(event.tid);
504        thread.sortIndex = event.args.sort_index;
505      } else if (event.name === 'num_cpus') {
506        var n = event.args.number;
507        // Not all render processes agree on the cpu count in trace_event. Some
508        // processes will report 1, while others will report the actual cpu
509        // count. To deal with this, take the max of what is reported.
510        if (this.softwareMeasuredCpuCount_ !== undefined)
511          n = Math.max(n, this.softwareMeasuredCpuCount_);
512        this.softwareMeasuredCpuCount_ = n;
513      } else if (event.name === 'stackFrames') {
514        var stackFrames = event.args.stackFrames;
515        if (stackFrames === undefined) {
516          this.model_.importWarning({
517            type: 'metadata_parse_error',
518            message: 'No stack frames found in a \'' + event.name +
519                '\' metadata event'
520          });
521        } else {
522          this.importStackFrames_(stackFrames, 'p' + event.pid + ':');
523        }
524      } else if (event.name === 'typeNames') {
525        var objectTypeNameMap = event.args.typeNames;
526        if (objectTypeNameMap === undefined) {
527          this.model_.importWarning({
528            type: 'metadata_parse_error',
529            message: 'No mapping from object type IDs to names found in a \'' +
530                event.name + '\' metadata event'
531          });
532        } else {
533          this.importObjectTypeNameMap_(objectTypeNameMap, event.pid);
534        }
535      } else {
536        this.model_.importWarning({
537          type: 'metadata_parse_error',
538          message: 'Unrecognized metadata name: ' + event.name
539        });
540      }
541    },
542
543    processInstantEvent: function(event) {
544      // V8 JIT events were logged as phase 'I' in the old format,
545      // so we need to separate them out and handle specially.
546      if (event.name === 'JitCodeAdded' || event.name === 'JitCodeMoved') {
547        this.v8SamplingData_.push(event);
548        return;
549      }
550
551      // Thread-level instant events are treated as zero-duration slices.
552      if (event.s === 't' || event.s === undefined) {
553        this.processDurationEvent(event);
554        return;
555      }
556
557      var constructor;
558      switch (event.s) {
559        case 'g':
560          constructor = tr.model.GlobalInstantEvent;
561          break;
562        case 'p':
563          constructor = tr.model.ProcessInstantEvent;
564          break;
565        default:
566          this.model_.importWarning({
567            type: 'instant_parse_error',
568            message: 'I phase event with unknown "s" field value.'
569          });
570          return;
571      }
572
573      var instantEvent = new constructor(event.cat, event.name,
574          getEventColor(event), timestampFromUs(event.ts),
575          this.deepCopyIfNeeded_(event.args));
576
577      switch (instantEvent.type) {
578        case tr.model.InstantEventType.GLOBAL:
579          this.model_.instantEvents.push(instantEvent);
580          break;
581
582        case tr.model.InstantEventType.PROCESS:
583          var process = this.model_.getOrCreateProcess(event.pid);
584          process.instantEvents.push(instantEvent);
585          break;
586
587        default:
588          throw new Error('Unknown instant event type: ' + event.s);
589      }
590    },
591
592    processV8Sample: function(event) {
593      var data = event.args.data;
594
595      // As-per DevTools, the backend sometimes creates bogus samples. Skip it.
596      if (data.vm_state === 'js' && !data.stack.length)
597        return;
598
599      var rootStackFrame = this.v8ProcessRootStackFrame_[event.pid];
600      if (!rootStackFrame) {
601        rootStackFrame = new tr.model.StackFrame(
602            undefined /* parent */, 'v8-root-stack-frame' /* id */,
603            'v8-root-stack-frame' /* title */, 0 /* colorId */);
604        this.v8ProcessRootStackFrame_[event.pid] = rootStackFrame;
605      }
606
607      function findChildWithEntryID(stackFrame, entryID) {
608        return tr.b.findFirstInArray(stackFrame.children, function(child) {
609          return child.entryID === entryID;
610        });
611      }
612
613      var model = this.model_;
614      function addStackFrame(lastStackFrame, entry) {
615        var childFrame = findChildWithEntryID(lastStackFrame, entry.id);
616        if (childFrame)
617          return childFrame;
618
619        var frame = new tr.model.StackFrame(
620            lastStackFrame, tr.b.GUID.allocate(), entry.name,
621            ColorScheme.getColorIdForGeneralPurposeString(entry.name),
622            entry.sourceInfo);
623
624        frame.entryID = entry.id;
625        model.addStackFrame(frame);
626        return frame;
627      }
628
629      var lastStackFrame = rootStackFrame;
630
631      // There are several types of v8 sample events, gc, native, compiler, etc.
632      // Some of these types have stacks and some don't, we handle those two
633      // cases differently. For types that don't have any stack frames attached
634      // we synthesize one based on the type of thing that's happening so when
635      // we view all the samples we'll see something like 'external' or 'gc'
636      // as a fraction of the time spent.
637      if (data.stack.length > 0 && this.v8ProcessCodeMaps_[event.pid]) {
638        var map = this.v8ProcessCodeMaps_[event.pid];
639
640        // Stacks have the leaf node first, flip them around so the root
641        // comes first.
642        data.stack.reverse();
643
644        for (var i = 0; i < data.stack.length; i++) {
645          var entry = map.lookupEntry(data.stack[i]);
646          if (entry === undefined) {
647            entry = {
648              id: 'unknown',
649              name: 'unknown',
650              sourceInfo: undefined
651            };
652          }
653
654          lastStackFrame = addStackFrame(lastStackFrame, entry);
655        }
656      } else {
657        var entry = {
658          id: data.vm_state,
659          name: data.vm_state,
660          sourceInfo: undefined
661        };
662        lastStackFrame = addStackFrame(lastStackFrame, entry);
663      }
664
665      var thread = this.model_.getOrCreateProcess(event.pid)
666        .getOrCreateThread(event.tid);
667
668      var sample = new tr.model.Sample(
669          undefined /* cpu */, thread, 'V8 Sample',
670          timestampFromUs(event.ts), lastStackFrame, 1 /* weight */,
671          this.deepCopyIfNeeded_(event.args));
672      this.model_.samples.push(sample);
673    },
674
675    processTraceSampleEvent: function(event) {
676      if (event.name === 'V8Sample') {
677        this.v8SamplingData_.push(event);
678        return;
679      }
680
681      var stackFrame = this.getStackFrameForEvent_(event);
682      if (stackFrame === undefined) {
683        stackFrame = this.traceEventSampleStackFramesByName_[
684            event.name];
685      }
686      if (stackFrame === undefined) {
687        var id = 'te-' + tr.b.GUID.allocate();
688        stackFrame = new tr.model.StackFrame(
689            undefined, id, event.name,
690            ColorScheme.getColorIdForGeneralPurposeString(event.name));
691        this.model_.addStackFrame(stackFrame);
692        this.traceEventSampleStackFramesByName_[event.name] = stackFrame;
693      }
694
695      var thread = this.model_.getOrCreateProcess(event.pid)
696        .getOrCreateThread(event.tid);
697
698      var sample = new tr.model.Sample(
699          undefined, thread, 'Trace Event Sample',
700          timestampFromUs(event.ts), stackFrame, 1,
701          this.deepCopyIfNeeded_(event.args));
702      this.model_.samples.push(sample);
703    },
704
705    processMemoryDumpEvent: function(event) {
706      if (event.ph !== 'v')
707        throw new Error('Invalid memory dump event phase "' + event.ph + '".');
708
709      var dumpId = event.id;
710      if (dumpId === undefined) {
711        this.model_.importWarning({
712          type: 'memory_dump_parse_error',
713          message: 'Memory dump event (phase \'' + event.ph +
714              '\') without a dump ID.'
715        });
716        return;
717      }
718
719      var pid = event.pid;
720      if (pid === undefined) {
721        this.model_.importWarning({
722          type: 'memory_dump_parse_error',
723          message: 'Memory dump event (phase\'' + event.ph + '\', dump ID \'' +
724              dumpId + '\') without a PID.'
725        });
726        return;
727      }
728
729      // Dump ID -> PID -> [process memory dump events].
730      var allEvents = this.allMemoryDumpEvents_;
731
732      // PID -> [process memory dump events].
733      var dumpIdEvents = allEvents[dumpId];
734      if (dumpIdEvents === undefined)
735        allEvents[dumpId] = dumpIdEvents = {};
736
737      // [process memory dump events].
738      var processEvents = dumpIdEvents[pid];
739      if (processEvents === undefined)
740        dumpIdEvents[pid] = processEvents = [];
741
742      processEvents.push(event);
743    },
744
745    processClockSyncEvent: function(event) {
746      if (event.ph !== 'c')
747        throw new Error('Invalid clock sync event phase "' + event.ph + '".');
748
749      var syncId = event.args.sync_id;
750      var issueStartTs = event.args.issue_ts;
751      var issueEndTs = event.ts;
752
753      if (syncId === undefined) {
754        this.model_.importWarning({
755          type: 'clock_sync_parse_error',
756          message: 'Clock sync at time ' + issueEndTs + ' without an ID.'
757        });
758        return;
759      }
760
761      if (issueStartTs === undefined) {
762        this.model_.importWarning({
763          type: 'clock_sync_parse_error',
764          message: 'Clock sync at time ' + issueEndTs + ' with ID ' + syncId +
765              ' without a start timestamp.'
766        });
767        return;
768      }
769
770      this.model_.clockSyncRecords.push(new tr.model.PingPongClockSyncRecord(
771          syncId, timestampFromUs(issueStartTs),
772          timestampFromUs(issueEndTs - issueStartTs)));
773    },
774
775    // Because the order of Jit code events and V8 samples are not guaranteed,
776    // We store them in an array, sort by timestamp, and then process them.
777    processV8Events: function() {
778      this.v8SamplingData_.sort(function(a, b) {
779        if (a.ts !== b.ts)
780          return a.ts - b.ts;
781        if (a.ph === 'M' || a.ph === 'I')
782          return -1;
783        else if (b.ph === 'M' || b.ph === 'I')
784          return 1;
785        return 0;
786      });
787      var length = this.v8SamplingData_.length;
788      for (var i = 0; i < length; ++i) {
789        var event = this.v8SamplingData_[i];
790        if (event.ph === 'M' || event.ph === 'I') {
791          this.processJitCodeEvent(event);
792        } else if (event.ph === 'P') {
793          this.processV8Sample(event);
794        }
795      }
796    },
797
798    /**
799     * Walks through the events_ list and outputs the structures discovered to
800     * model_.
801     */
802    importEvents: function() {
803      var csr = new tr.model.InstantClockSyncRecord('ftrace_importer', 0, {});
804      this.model_.clockSyncRecords.push(csr);
805      if (this.stackFrameEvents_)
806        this.importStackFrames_(this.stackFrameEvents_, 'g');
807
808      if (this.traceAnnotations_)
809        this.importAnnotations_();
810
811      var importOptions = this.model_.importOptions;
812      var trackDetailedModelStats = importOptions.trackDetailedModelStats;
813
814      var modelStats = this.model_.stats;
815
816      var events = this.events_;
817      for (var eI = 0; eI < events.length; eI++) {
818        var event = events[eI];
819
820        if (event.args === '__stripped__') {
821          event.argsStripped = true;
822          event.args = undefined;
823        }
824
825        var eventSizeInBytes;
826        if (trackDetailedModelStats)
827          eventSizeInBytes = JSON.stringify(event).length;
828        else
829          eventSizeInBytes = undefined;
830
831        if (event.ph === 'B' || event.ph === 'E') {
832          modelStats.willProcessBasicTraceEvent(
833              'begin_end (non-compact)', event.cat, event.name, event.ts,
834              eventSizeInBytes);
835          this.processDurationEvent(event);
836
837        } else if (event.ph === 'X') {
838          modelStats.willProcessBasicTraceEvent(
839              'begin_end (compact)', event.cat, event.name, event.ts,
840              eventSizeInBytes);
841          var slice = this.processCompleteEvent(event);
842          // TODO(yuhaoz): If Chrome supports creating other events with flow,
843          // we will need to call processFlowEvent for them also.
844          // https://github.com/catapult-project/catapult/issues/1259
845          if (slice !== undefined && event.bind_id !== undefined)
846            this.processFlowEvent(event, slice);
847
848        } else if (event.ph === 'b' || event.ph === 'e' || event.ph === 'n' ||
849                   event.ph === 'S' || event.ph === 'F' || event.ph === 'T' ||
850                   event.ph === 'p') {
851          modelStats.willProcessBasicTraceEvent(
852              'async', event.cat, event.name, event.ts, eventSizeInBytes);
853          this.processAsyncEvent(event);
854
855        // Note, I is historic. The instant event marker got changed, but we
856        // want to support loading old trace files so we have both I and i.
857        } else if (event.ph === 'I' || event.ph === 'i' || event.ph === 'R') {
858          modelStats.willProcessBasicTraceEvent(
859              'instant', event.cat, event.name, event.ts, eventSizeInBytes);
860          this.processInstantEvent(event);
861
862        } else if (event.ph === 'P') {
863          modelStats.willProcessBasicTraceEvent(
864              'samples', event.cat, event.name, event.ts, eventSizeInBytes);
865          this.processTraceSampleEvent(event);
866        } else if (event.ph === 'C') {
867          modelStats.willProcessBasicTraceEvent(
868              'counters', event.cat, event.name, event.ts, eventSizeInBytes);
869          this.processCounterEvent(event);
870        } else if (event.ph === 'M') {
871          modelStats.willProcessBasicTraceEvent(
872              'metadata', event.cat, event.name, event.ts, eventSizeInBytes);
873          this.processMetadataEvent(event);
874
875        } else if (event.ph === 'N' || event.ph === 'D' || event.ph === 'O') {
876          modelStats.willProcessBasicTraceEvent(
877              'objects', event.cat, event.name, event.ts, eventSizeInBytes);
878          this.processObjectEvent(event);
879
880        } else if (event.ph === 's' || event.ph === 't' || event.ph === 'f') {
881          modelStats.willProcessBasicTraceEvent(
882              'flows', event.cat, event.name, event.ts, eventSizeInBytes);
883          this.processFlowEvent(event);
884
885        } else if (event.ph === 'v') {
886          modelStats.willProcessBasicTraceEvent(
887              'memory_dumps', event.cat, event.name, event.ts,
888              eventSizeInBytes);
889          this.processMemoryDumpEvent(event);
890
891        } else if (event.ph === 'c') {
892          modelStats.willProcessBasicTraceEvent(
893              'clock_sync', event.cat, event.name, event.ts, eventSizeInBytes);
894          this.processClockSyncEvent(event);
895        } else {
896          modelStats.willProcessBasicTraceEvent(
897              'unknown', event.cat, event.name, event.ts, eventSizeInBytes);
898          this.model_.importWarning({
899            type: 'parse_error',
900            message: 'Unrecognized event phase: ' +
901                event.ph + ' (' + event.name + ')'
902          });
903        }
904      }
905      this.processV8Events();
906
907      // Remove all the root stack frame children as they should
908      // already be added.
909      tr.b.iterItems(this.v8ProcessRootStackFrame_, function(name, frame) {
910        frame.removeAllChildren();
911      });
912    },
913
914    importStackFrames_: function(rawStackFrames, idPrefix) {
915      var model = this.model_;
916
917      for (var id in rawStackFrames) {
918        var rawStackFrame = rawStackFrames[id];
919        var fullId = idPrefix + id;
920        var textForColor = rawStackFrame.category ?
921            rawStackFrame.category : rawStackFrame.name;
922        var stackFrame = new tr.model.StackFrame(
923            undefined /* parentFrame */, fullId, rawStackFrame.name,
924            ColorScheme.getColorIdForGeneralPurposeString(textForColor));
925        model.addStackFrame(stackFrame);
926      }
927
928      for (var id in rawStackFrames) {
929        var fullId = idPrefix + id;
930        var stackFrame = model.stackFrames[fullId];
931        if (stackFrame === undefined)
932          throw new Error('Internal error');
933
934        var rawStackFrame = rawStackFrames[id];
935        var parentId = rawStackFrame.parent;
936        var parentStackFrame;
937        if (parentId === undefined) {
938          parentStackFrame = undefined;
939        } else {
940          var parentFullId = idPrefix + parentId;
941          parentStackFrame = model.stackFrames[parentFullId];
942          if (parentStackFrame === undefined) {
943            this.model_.importWarning({
944              type: 'metadata_parse_error',
945              message: 'Missing parent frame with ID ' + parentFullId +
946                  ' for stack frame \'' + stackFrame.name + '\' (ID ' + fullId +
947                  ').'
948            });
949          }
950        }
951        stackFrame.parentFrame = parentStackFrame;
952      }
953    },
954
955    importObjectTypeNameMap_: function(rawObjectTypeNameMap, pid) {
956      if (pid in this.objectTypeNameMap_) {
957        this.model_.importWarning({
958          type: 'metadata_parse_error',
959          message: 'Mapping from object type IDs to names provided for pid=' +
960              pid + ' multiple times.'
961        });
962        return;
963      }
964
965      var objectTypeNamePrefix = undefined;
966      var objectTypeNameSuffix = undefined;
967      var objectTypeNameMap = {};
968      for (var objectTypeId in rawObjectTypeNameMap) {
969        var rawObjectTypeName = rawObjectTypeNameMap[objectTypeId];
970
971        // If we haven't figured out yet which compiler the object type names
972        // come from, we try to do it now.
973        if (objectTypeNamePrefix === undefined) {
974          for (var i = 0; i < OBJECT_TYPE_NAME_PATTERNS.length; i++) {
975            var pattern = OBJECT_TYPE_NAME_PATTERNS[i];
976            if (rawObjectTypeName.startsWith(pattern.prefix) &&
977                rawObjectTypeName.endsWith(pattern.suffix)) {
978              objectTypeNamePrefix = pattern.prefix;
979              objectTypeNameSuffix = pattern.suffix;
980              break;
981            }
982          }
983        }
984
985        if (objectTypeNamePrefix !== undefined &&
986            rawObjectTypeName.startsWith(objectTypeNamePrefix) &&
987            rawObjectTypeName.endsWith(objectTypeNameSuffix)) {
988          // With compiler-specific prefix and suffix (automatically annotated
989          // object types).
990          objectTypeNameMap[objectTypeId] = rawObjectTypeName.substring(
991               objectTypeNamePrefix.length,
992               rawObjectTypeName.length - objectTypeNameSuffix.length);
993        } else {
994          // Without compiler-specific prefix and suffix (manually annotated
995          // object types and '[unknown]').
996          objectTypeNameMap[objectTypeId] = rawObjectTypeName;
997        }
998      }
999
1000      this.objectTypeNameMap_[pid] = objectTypeNameMap;
1001    },
1002
1003    importAnnotations_: function() {
1004      for (var id in this.traceAnnotations_) {
1005        var annotation = tr.model.Annotation.fromDictIfPossible(
1006           this.traceAnnotations_[id]);
1007        if (!annotation) {
1008          this.model_.importWarning({
1009            type: 'annotation_warning',
1010            message: 'Unrecognized traceAnnotation typeName \"' +
1011                this.traceAnnotations_[id].typeName + '\"'
1012          });
1013          continue;
1014        }
1015        this.model_.addAnnotation(annotation);
1016      }
1017    },
1018
1019    /**
1020     * Called by the Model after all other importers have imported their
1021     * events.
1022     */
1023    finalizeImport: function() {
1024      if (this.softwareMeasuredCpuCount_ !== undefined) {
1025        this.model_.kernel.softwareMeasuredCpuCount =
1026            this.softwareMeasuredCpuCount_;
1027      }
1028      this.createAsyncSlices_();
1029      this.createFlowSlices_();
1030      this.createExplicitObjects_();
1031      this.createImplicitObjects_();
1032      this.createMemoryDumps_();
1033    },
1034
1035    /* Events can have one or more stack frames associated with them, but
1036     * that frame might be encoded either as a stack trace of program counters,
1037     * or as a direct stack frame reference. This handles either case and
1038     * if found, returns the stackframe.
1039     */
1040    getStackFrameForEvent_: function(event, opt_lookForEndEvent) {
1041      var sf;
1042      var stack;
1043      if (opt_lookForEndEvent) {
1044        sf = event.esf;
1045        stack = event.estack;
1046      } else {
1047        sf = event.sf;
1048        stack = event.stack;
1049      }
1050      if (stack !== undefined && sf !== undefined) {
1051        this.model_.importWarning({
1052          type: 'stack_frame_and_stack_error',
1053          message: 'Event at ' + event.ts +
1054              ' cannot have both a stack and a stackframe.'
1055        });
1056        return undefined;
1057      }
1058
1059      if (stack !== undefined)
1060        return this.model_.resolveStackToStackFrame_(event.pid, stack);
1061      if (sf === undefined)
1062        return undefined;
1063
1064      var stackFrame = this.model_.stackFrames['g' + sf];
1065      if (stackFrame === undefined) {
1066        this.model_.importWarning({
1067          type: 'sample_import_error',
1068          message: 'No frame for ' + sf
1069        });
1070        return;
1071      }
1072      return stackFrame;
1073    },
1074
1075    resolveStackToStackFrame_: function(pid, stack) {
1076      // TODO(alph,fmeawad): Add codemap resolution code here.
1077      return undefined;
1078    },
1079
1080    importSampleData: function() {
1081      if (!this.sampleEvents_)
1082        return;
1083      var m = this.model_;
1084
1085      // If this is the only importer, then fake-create the threads.
1086      var events = this.sampleEvents_;
1087      if (this.events_.length === 0) {
1088        for (var i = 0; i < events.length; i++) {
1089          var event = events[i];
1090          m.getOrCreateProcess(event.tid).getOrCreateThread(event.tid);
1091        }
1092      }
1093
1094      var threadsByTid = {};
1095      m.getAllThreads().forEach(function(t) {
1096        threadsByTid[t.tid] = t;
1097      });
1098
1099      for (var i = 0; i < events.length; i++) {
1100        var event = events[i];
1101        var thread = threadsByTid[event.tid];
1102        if (thread === undefined) {
1103          m.importWarning({
1104            type: 'sample_import_error',
1105            message: 'Thread ' + events.tid + 'not found'
1106          });
1107          continue;
1108        }
1109
1110        var cpu;
1111        if (event.cpu !== undefined)
1112          cpu = m.kernel.getOrCreateCpu(event.cpu);
1113
1114        var stackFrame = this.getStackFrameForEvent_(event);
1115
1116        var sample = new tr.model.Sample(
1117            cpu, thread,
1118            event.name,
1119            timestampFromUs(event.ts),
1120            stackFrame,
1121            event.weight);
1122        m.samples.push(sample);
1123      }
1124    },
1125
1126    createAsyncSlices_: function() {
1127      if (this.allAsyncEvents_.length === 0)
1128        return;
1129
1130      this.allAsyncEvents_.sort(function(x, y) {
1131        var d = x.event.ts - y.event.ts;
1132        if (d !== 0)
1133          return d;
1134        return x.sequenceNumber - y.sequenceNumber;
1135      });
1136
1137      var legacyEvents = [];
1138      // Group nestable async events by ID. Events with the same ID should
1139      // belong to the same parent async event.
1140      var nestableAsyncEventsByKey = {};
1141      var nestableMeasureAsyncEventsByKey = {};
1142      for (var i = 0; i < this.allAsyncEvents_.length; i++) {
1143        var asyncEventState = this.allAsyncEvents_[i];
1144        var event = asyncEventState.event;
1145        if (event.ph === 'S' || event.ph === 'F' || event.ph === 'T' ||
1146            event.ph === 'p') {
1147          legacyEvents.push(asyncEventState);
1148          continue;
1149        }
1150        if (event.cat === undefined) {
1151          this.model_.importWarning({
1152            type: 'async_slice_parse_error',
1153            message: 'Nestable async events (ph: b, e, or n) require a ' +
1154                'cat parameter.'
1155          });
1156          continue;
1157        }
1158
1159        if (event.name === undefined) {
1160          this.model_.importWarning({
1161            type: 'async_slice_parse_error',
1162            message: 'Nestable async events (ph: b, e, or n) require a ' +
1163                'name parameter.'
1164          });
1165          continue;
1166        }
1167
1168        if (event.id === undefined) {
1169          this.model_.importWarning({
1170            type: 'async_slice_parse_error',
1171            message: 'Nestable async events (ph: b, e, or n) require an ' +
1172                'id parameter.'
1173          });
1174          continue;
1175        }
1176
1177        if (event.cat === 'blink.user_timing') {
1178          var matched = /([^\/:]+):([^\/:]+)\/?(.*)/.exec(event.name);
1179          if (matched !== null) {
1180            var key = matched[1] + ':' + event.cat;
1181            event.args = JSON.parse(Base64.atob(matched[3]) || '{}');
1182            if (nestableMeasureAsyncEventsByKey[key] === undefined)
1183              nestableMeasureAsyncEventsByKey[key] = [];
1184            nestableMeasureAsyncEventsByKey[key].push(asyncEventState);
1185            continue;
1186          }
1187        }
1188
1189        var key = event.cat + ':' + event.id;
1190        if (nestableAsyncEventsByKey[key] === undefined)
1191           nestableAsyncEventsByKey[key] = [];
1192        nestableAsyncEventsByKey[key].push(asyncEventState);
1193      }
1194      // Handle legacy async events.
1195      this.createLegacyAsyncSlices_(legacyEvents);
1196
1197      // Parse nestable measure async events into AsyncSlices.
1198      this.createNestableAsyncSlices_(nestableMeasureAsyncEventsByKey);
1199
1200      // Parse nestable async events into AsyncSlices.
1201      this.createNestableAsyncSlices_(nestableAsyncEventsByKey);
1202    },
1203
1204    createLegacyAsyncSlices_: function(legacyEvents) {
1205      if (legacyEvents.length === 0)
1206        return;
1207
1208      legacyEvents.sort(function(x, y) {
1209        var d = x.event.ts - y.event.ts;
1210        if (d != 0)
1211          return d;
1212        return x.sequenceNumber - y.sequenceNumber;
1213      });
1214
1215      var asyncEventStatesByNameThenID = {};
1216
1217      for (var i = 0; i < legacyEvents.length; i++) {
1218        var asyncEventState = legacyEvents[i];
1219
1220        var event = asyncEventState.event;
1221        var name = event.name;
1222        if (name === undefined) {
1223          this.model_.importWarning({
1224            type: 'async_slice_parse_error',
1225            message: 'Async events (ph: S, T, p, or F) require a name ' +
1226                ' parameter.'
1227          });
1228          continue;
1229        }
1230
1231        var id = event.id;
1232        if (id === undefined) {
1233          this.model_.importWarning({
1234            type: 'async_slice_parse_error',
1235            message: 'Async events (ph: S, T, p, or F) require an id parameter.'
1236          });
1237          continue;
1238        }
1239
1240        // TODO(simonjam): Add a synchronous tick on the appropriate thread.
1241
1242        if (event.ph === 'S') {
1243          if (asyncEventStatesByNameThenID[name] === undefined)
1244            asyncEventStatesByNameThenID[name] = {};
1245          if (asyncEventStatesByNameThenID[name][id]) {
1246            this.model_.importWarning({
1247              type: 'async_slice_parse_error',
1248              message: 'At ' + event.ts + ', a slice of the same id ' + id +
1249                  ' was alrady open.'
1250            });
1251            continue;
1252          }
1253          asyncEventStatesByNameThenID[name][id] = [];
1254          asyncEventStatesByNameThenID[name][id].push(asyncEventState);
1255        } else {
1256          if (asyncEventStatesByNameThenID[name] === undefined) {
1257            this.model_.importWarning({
1258              type: 'async_slice_parse_error',
1259              message: 'At ' + event.ts + ', no slice named ' + name +
1260                  ' was open.'
1261            });
1262            continue;
1263          }
1264          if (asyncEventStatesByNameThenID[name][id] === undefined) {
1265            this.model_.importWarning({
1266              type: 'async_slice_parse_error',
1267              message: 'At ' + event.ts + ', no slice named ' + name +
1268                  ' with id=' + id + ' was open.'
1269            });
1270            continue;
1271          }
1272          var events = asyncEventStatesByNameThenID[name][id];
1273          events.push(asyncEventState);
1274
1275          if (event.ph === 'F') {
1276            // Create a slice from start to end.
1277            var asyncSliceConstructor =
1278               tr.model.AsyncSlice.getConstructor(
1279                  events[0].event.cat,
1280                  name);
1281            var slice = new asyncSliceConstructor(
1282                events[0].event.cat,
1283                name,
1284                getEventColor(events[0].event),
1285                timestampFromUs(events[0].event.ts),
1286                tr.b.concatenateObjects(events[0].event.args,
1287                                      events[events.length - 1].event.args),
1288                timestampFromUs(event.ts - events[0].event.ts),
1289                true, undefined, undefined, events[0].event.argsStripped);
1290            slice.startThread = events[0].thread;
1291            slice.endThread = asyncEventState.thread;
1292            slice.id = id;
1293
1294            var stepType = events[1].event.ph;
1295            var isValid = true;
1296
1297            // Create subSlices for each step. Skip the start and finish events,
1298            // which are always first and last respectively.
1299            for (var j = 1; j < events.length - 1; ++j) {
1300              if (events[j].event.ph === 'T' || events[j].event.ph === 'p') {
1301                isValid = this.assertStepTypeMatches_(stepType, events[j]);
1302                if (!isValid)
1303                  break;
1304              }
1305
1306              if (events[j].event.ph === 'S') {
1307                this.model_.importWarning({
1308                  type: 'async_slice_parse_error',
1309                  message: 'At ' + event.event.ts + ', a slice named ' +
1310                      event.event.name + ' with id=' + event.event.id +
1311                      ' had a step before the start event.'
1312                });
1313                continue;
1314              }
1315
1316              if (events[j].event.ph === 'F') {
1317                this.model_.importWarning({
1318                  type: 'async_slice_parse_error',
1319                  message: 'At ' + event.event.ts + ', a slice named ' +
1320                      event.event.name + ' with id=' + event.event.id +
1321                      ' had a step after the finish event.'
1322                });
1323                continue;
1324              }
1325
1326              var startIndex = j + (stepType === 'T' ? 0 : -1);
1327              var endIndex = startIndex + 1;
1328
1329              var subName = events[j].event.name;
1330              if (!events[j].event.argsStripped &&
1331                  (events[j].event.ph === 'T' || events[j].event.ph === 'p'))
1332                subName = subName + ':' + events[j].event.args.step;
1333
1334              var asyncSliceConstructor =
1335                 tr.model.AsyncSlice.getConstructor(
1336                    events[0].event.cat,
1337                    subName);
1338              var subSlice = new asyncSliceConstructor(
1339                  events[0].event.cat,
1340                  subName,
1341                  getEventColor(event, subName + j),
1342                  timestampFromUs(events[startIndex].event.ts),
1343                  this.deepCopyIfNeeded_(events[j].event.args),
1344                  timestampFromUs(
1345                    events[endIndex].event.ts - events[startIndex].event.ts),
1346                      undefined, undefined,
1347                      events[startIndex].event.argsStripped);
1348              subSlice.startThread = events[startIndex].thread;
1349              subSlice.endThread = events[endIndex].thread;
1350              subSlice.id = id;
1351
1352              slice.subSlices.push(subSlice);
1353            }
1354
1355            if (isValid) {
1356              // Add |slice| to the start-thread's asyncSlices.
1357              slice.startThread.asyncSliceGroup.push(slice);
1358            }
1359
1360            delete asyncEventStatesByNameThenID[name][id];
1361          }
1362        }
1363      }
1364    },
1365
1366    createNestableAsyncSlices_: function(nestableEventsByKey) {
1367      for (var key in nestableEventsByKey) {
1368        var eventStateEntries = nestableEventsByKey[key];
1369        // Stack of enclosing BEGIN events.
1370        var parentStack = [];
1371        for (var i = 0; i < eventStateEntries.length; ++i) {
1372          var eventStateEntry = eventStateEntries[i];
1373          // If this is the end of an event, match it to the start.
1374          if (eventStateEntry.event.ph === 'e') {
1375            // Walk up the parent stack to find the corresponding BEGIN for
1376            // this END.
1377            var parentIndex = -1;
1378            for (var k = parentStack.length - 1; k >= 0; --k) {
1379              if (parentStack[k].event.name === eventStateEntry.event.name) {
1380                parentIndex = k;
1381                break;
1382              }
1383            }
1384            if (parentIndex === -1) {
1385              // Unmatched end.
1386              eventStateEntry.finished = false;
1387            } else {
1388              parentStack[parentIndex].end = eventStateEntry;
1389              // Pop off all enclosing unmatched BEGINs util parentIndex.
1390              while (parentIndex < parentStack.length) {
1391                parentStack.pop();
1392              }
1393            }
1394          }
1395          // Inherit the current parent.
1396          if (parentStack.length > 0)
1397            eventStateEntry.parentEntry = parentStack[parentStack.length - 1];
1398          if (eventStateEntry.event.ph === 'b') {
1399            parentStack.push(eventStateEntry);
1400          }
1401        }
1402        var topLevelSlices = [];
1403        for (var i = 0; i < eventStateEntries.length; ++i) {
1404          var eventStateEntry = eventStateEntries[i];
1405          // Skip matched END, as its slice will be created when we
1406          // encounter its corresponding BEGIN.
1407          if (eventStateEntry.event.ph === 'e' &&
1408              eventStateEntry.finished === undefined) {
1409            continue;
1410          }
1411          var startState = undefined;
1412          var endState = undefined;
1413          var sliceArgs = eventStateEntry.event.args || {};
1414          var sliceError = undefined;
1415          if (eventStateEntry.event.ph === 'n') {
1416            startState = eventStateEntry;
1417            endState = eventStateEntry;
1418          } else if (eventStateEntry.event.ph === 'b') {
1419            if (eventStateEntry.end === undefined) {
1420              // Unmatched BEGIN. End it when last event with this ID ends.
1421              eventStateEntry.end =
1422                eventStateEntries[eventStateEntries.length - 1];
1423              sliceError =
1424                'Slice has no matching END. End time has been adjusted.';
1425              this.model_.importWarning({
1426                type: 'async_slice_parse_error',
1427                message: 'Nestable async BEGIN event at ' +
1428                  eventStateEntry.event.ts + ' with name=' +
1429                  eventStateEntry.event.name +
1430                  ' and id=' + eventStateEntry.event.id + ' was unmatched.'
1431              });
1432            } else {
1433              // Include args for both END and BEGIN for a matched pair.
1434              function concatenateArguments(args1, args2) {
1435                if (args1.params === undefined || args2.params === undefined)
1436                  return tr.b.concatenateObjects(args1, args2);
1437                // Make an argument object to hold the combined params.
1438                var args3 = {};
1439                args3.params = tr.b.concatenateObjects(args1.params,
1440                                                       args2.params);
1441                return tr.b.concatenateObjects(args1, args2, args3);
1442              }
1443              var endArgs = eventStateEntry.end.event.args || {};
1444              sliceArgs = concatenateArguments(sliceArgs, endArgs);
1445            }
1446            startState = eventStateEntry;
1447            endState = eventStateEntry.end;
1448          } else {
1449            // Unmatched END. Start it at the first event with this ID starts.
1450            sliceError =
1451              'Slice has no matching BEGIN. Start time has been adjusted.';
1452            this.model_.importWarning({
1453              type: 'async_slice_parse_error',
1454              message: 'Nestable async END event at ' +
1455                eventStateEntry.event.ts + ' with name=' +
1456                eventStateEntry.event.name +
1457                ' and id=' + eventStateEntry.event.id + ' was unmatched.'
1458            });
1459            startState = eventStateEntries[0];
1460            endState = eventStateEntry;
1461          }
1462
1463          var isTopLevel = (eventStateEntry.parentEntry === undefined);
1464          var asyncSliceConstructor =
1465              tr.model.AsyncSlice.getConstructor(
1466                eventStateEntry.event.cat,
1467                eventStateEntry.event.name);
1468
1469          var thread_start = undefined;
1470          var thread_duration = undefined;
1471          if (startState.event.tts && startState.event.use_async_tts) {
1472            thread_start = timestampFromUs(startState.event.tts);
1473            if (endState.event.tts) {
1474              var thread_end = timestampFromUs(endState.event.tts);
1475              thread_duration = thread_end - thread_start;
1476            }
1477          }
1478
1479          var slice = new asyncSliceConstructor(
1480            eventStateEntry.event.cat,
1481            eventStateEntry.event.name,
1482            getEventColor(endState.event),
1483            timestampFromUs(startState.event.ts),
1484            sliceArgs,
1485            timestampFromUs(endState.event.ts - startState.event.ts),
1486            isTopLevel,
1487            thread_start,
1488            thread_duration,
1489            startState.event.argsStripped);
1490
1491          slice.startThread = startState.thread;
1492          slice.endThread = endState.thread;
1493
1494          slice.startStackFrame = this.getStackFrameForEvent_(startState.event);
1495          slice.endStackFrame = this.getStackFrameForEvent_(endState.event);
1496
1497          slice.id = key;
1498          if (sliceError !== undefined)
1499            slice.error = sliceError;
1500          eventStateEntry.slice = slice;
1501          // Add the slice to the topLevelSlices array if there is no parent.
1502          // Otherwise, add the slice to the subSlices of its parent.
1503          if (isTopLevel) {
1504            topLevelSlices.push(slice);
1505          } else if (eventStateEntry.parentEntry.slice !== undefined) {
1506            eventStateEntry.parentEntry.slice.subSlices.push(slice);
1507          }
1508        }
1509        for (var si = 0; si < topLevelSlices.length; si++) {
1510          topLevelSlices[si].startThread.asyncSliceGroup.push(
1511            topLevelSlices[si]);
1512        }
1513      }
1514    },
1515
1516    assertStepTypeMatches_: function(stepType, event) {
1517      if (stepType != event.event.ph) {
1518        this.model_.importWarning({
1519          type: 'async_slice_parse_error',
1520          message: 'At ' + event.event.ts + ', a slice named ' +
1521              event.event.name + ' with id=' + event.event.id +
1522              ' had both begin and end steps, which is not allowed.'
1523        });
1524        return false;
1525      }
1526      return true;
1527    },
1528
1529    createFlowSlices_: function() {
1530      if (this.allFlowEvents_.length === 0)
1531        return;
1532
1533      var that = this;
1534
1535      function validateFlowEvent() {
1536        if (event.name === undefined) {
1537          that.model_.importWarning({
1538            type: 'flow_slice_parse_error',
1539            message: 'Flow events (ph: s, t or f) require a name parameter.'
1540          });
1541          return false;
1542        }
1543
1544        // Support Flow API v1.
1545        if (event.ph === 's' || event.ph === 'f' || event.ph === 't') {
1546          if (event.id === undefined) {
1547            that.model_.importWarning({
1548              type: 'flow_slice_parse_error',
1549              message: 'Flow events (ph: s, t or f) require an id parameter.'
1550            });
1551            return false;
1552          }
1553          return true;
1554        }
1555
1556        // Support Flow API v2.
1557        if (event.bind_id) {
1558          if (event.flow_in === undefined && event.flow_out === undefined) {
1559            that.model_.importWarning({
1560              type: 'flow_slice_parse_error',
1561              message: 'Flow producer or consumer require flow_in or flow_out.'
1562            });
1563            return false;
1564          }
1565          return true;
1566        }
1567
1568        return false;
1569      }
1570
1571      function createFlowEvent(thread, event, opt_slice) {
1572        var startSlice, flowId, flowStartTs;
1573
1574        if (event.bind_id) {
1575          // Support Flow API v2.
1576          startSlice = opt_slice;
1577          flowId = event.bind_id;
1578          flowStartTs = timestampFromUs(event.ts + event.dur);
1579        } else {
1580          // Support Flow API v1.
1581          var ts = timestampFromUs(event.ts);
1582          startSlice = thread.sliceGroup.findSliceAtTs(ts);
1583          if (startSlice === undefined)
1584            return undefined;
1585          flowId = event.id;
1586          flowStartTs = ts;
1587        }
1588
1589        var flowEvent = new tr.model.FlowEvent(
1590            event.cat,
1591            flowId,
1592            event.name,
1593            getEventColor(event),
1594            flowStartTs,
1595            that.deepCopyAlways_(event.args));
1596        flowEvent.startSlice = startSlice;
1597        flowEvent.startStackFrame = that.getStackFrameForEvent_(event);
1598        flowEvent.endStackFrame = undefined;
1599        startSlice.outFlowEvents.push(flowEvent);
1600        return flowEvent;
1601      }
1602
1603      function finishFlowEventWith(flowEvent, thread, event,
1604                                   refGuid, bindToParent, opt_slice) {
1605        var endSlice;
1606
1607        if (event.bind_id) {
1608          // Support Flow API v2.
1609          endSlice = opt_slice;
1610        } else {
1611          // Support Flow API v1.
1612          var ts = timestampFromUs(event.ts);
1613          if (bindToParent) {
1614            endSlice = thread.sliceGroup.findSliceAtTs(ts);
1615          } else {
1616            endSlice = thread.sliceGroup.findNextSliceAfter(ts, refGuid);
1617          }
1618          if (endSlice === undefined)
1619            return false;
1620        }
1621
1622        endSlice.inFlowEvents.push(flowEvent);
1623        flowEvent.endSlice = endSlice;
1624        flowEvent.duration = timestampFromUs(event.ts) - flowEvent.start;
1625        flowEvent.endStackFrame = that.getStackFrameForEvent_(event);
1626        that.mergeArgsInto_(flowEvent.args, event.args, flowEvent.title);
1627        return true;
1628      }
1629
1630      function processFlowConsumer(flowIdToEvent, sliceGuidToEvent, event,
1631          slice) {
1632        var flowEvent = flowIdToEvent[event.bind_id];
1633        if (flowEvent === undefined) {
1634          that.model_.importWarning({
1635              type: 'flow_slice_ordering_error',
1636              message: 'Flow consumer ' + event.bind_id + ' does not have ' +
1637                  'a flow producer'});
1638          return false;
1639        } else if (flowEvent.endSlice) {
1640          // One flow producer can have more than one flow consumers.
1641          // In this case, create a new flow event using the flow producer.
1642          var flowProducer = flowEvent.startSlice;
1643          flowEvent = createFlowEvent(undefined,
1644              sliceGuidToEvent[flowProducer.guid], flowProducer);
1645        }
1646
1647        var ok = finishFlowEventWith(flowEvent, undefined, event,
1648                                     refGuid, undefined, slice);
1649        if (ok) {
1650          that.model_.flowEvents.push(flowEvent);
1651        } else {
1652          that.model_.importWarning({
1653              type: 'flow_slice_end_error',
1654              message: 'Flow consumer ' + event.bind_id + ' does not end ' +
1655                  'at an actual slice, so cannot be created.'});
1656          return false;
1657        }
1658
1659        return true;
1660      }
1661
1662      function processFlowProducer(flowIdToEvent, flowStatus, event, slice) {
1663        if (flowIdToEvent[event.bind_id] &&
1664            flowStatus[event.bind_id]) {
1665          // Can't open the same flow again while it's still open.
1666          // This is essentially the multi-producer case which we don't support
1667          that.model_.importWarning({
1668              type: 'flow_slice_start_error',
1669              message: 'Flow producer ' + event.bind_id + ' already seen'});
1670          return false;
1671        }
1672
1673        var flowEvent = createFlowEvent(undefined, event, slice);
1674        if (!flowEvent) {
1675          that.model_.importWarning({
1676              type: 'flow_slice_start_error',
1677              message: 'Flow producer ' + event.bind_id + ' does not start' +
1678                  'a flow'});
1679          return false;
1680        }
1681        flowIdToEvent[event.bind_id] = flowEvent;
1682
1683        return;
1684      }
1685
1686      // Actual import.
1687      this.allFlowEvents_.sort(function(x, y) {
1688        var d = x.event.ts - y.event.ts;
1689        if (d != 0)
1690          return d;
1691        return x.sequenceNumber - y.sequenceNumber;
1692      });
1693
1694      var flowIdToEvent = {};
1695      var sliceGuidToEvent = {};
1696      var flowStatus = {}; // true: open; false: closed.
1697      for (var i = 0; i < this.allFlowEvents_.length; ++i) {
1698        var data = this.allFlowEvents_[i];
1699        var refGuid = data.refGuid;
1700        var event = data.event;
1701        var thread = data.thread;
1702        if (!validateFlowEvent(event))
1703          continue;
1704
1705        // Support for Flow API v2.
1706        if (event.bind_id) {
1707          var slice = data.slice;
1708          sliceGuidToEvent[slice.guid] = event;
1709
1710          if (event.flowPhase === PRODUCER) {
1711            if (!processFlowProducer(flowIdToEvent, flowStatus, event, slice))
1712              continue;
1713            flowStatus[event.bind_id] = true; // open the flow.
1714          }
1715          else {
1716            if (!processFlowConsumer(flowIdToEvent, sliceGuidToEvent,
1717                event, slice))
1718              continue;
1719            flowStatus[event.bind_id] = false; // close the flow.
1720
1721            if (event.flowPhase === STEP) {
1722              if (!processFlowProducer(flowIdToEvent, flowStatus,
1723                  event, slice))
1724                continue;
1725              flowStatus[event.bind_id] = true; // open the flow again.
1726            }
1727          }
1728          continue;
1729        }
1730
1731        // Support for Flow API v1.
1732        var flowEvent;
1733        if (event.ph === 's') {
1734          if (flowIdToEvent[event.id]) {
1735            this.model_.importWarning({
1736              type: 'flow_slice_start_error',
1737              message: 'event id ' + event.id + ' already seen when ' +
1738                  'encountering start of flow event.'});
1739            continue;
1740          }
1741          flowEvent = createFlowEvent(thread, event);
1742          if (!flowEvent) {
1743            this.model_.importWarning({
1744              type: 'flow_slice_start_error',
1745              message: 'event id ' + event.id + ' does not start ' +
1746                  'at an actual slice, so cannot be created.'});
1747            continue;
1748          }
1749          flowIdToEvent[event.id] = flowEvent;
1750
1751        } else if (event.ph === 't' || event.ph === 'f') {
1752          flowEvent = flowIdToEvent[event.id];
1753          if (flowEvent === undefined) {
1754            this.model_.importWarning({
1755              type: 'flow_slice_ordering_error',
1756              message: 'Found flow phase ' + event.ph + ' for id: ' + event.id +
1757                  ' but no flow start found.'
1758            });
1759            continue;
1760          }
1761
1762          var bindToParent = event.ph === 't';
1763
1764          if (event.ph === 'f') {
1765            if (event.bp === undefined) {
1766              // TODO(yuhaoz): In flow V2, there is no notion of binding point.
1767              // Removal of binding point is tracked in
1768              // https://github.com/google/trace-viewer/issues/991.
1769              if (event.cat.indexOf('input') > -1)
1770                bindToParent = true;
1771              else if (event.cat.indexOf('ipc.flow') > -1)
1772                bindToParent = true;
1773            } else {
1774              if (event.bp !== 'e') {
1775                this.model_.importWarning({
1776                 type: 'flow_slice_bind_point_error',
1777                 message: 'Flow event with invalid binding point (event.bp).'
1778                });
1779                continue;
1780              }
1781              bindToParent = true;
1782            }
1783          }
1784
1785          var ok = finishFlowEventWith(flowEvent, thread, event,
1786                                       refGuid, bindToParent);
1787          if (ok) {
1788            that.model_.flowEvents.push(flowEvent);
1789          } else {
1790            this.model_.importWarning({
1791              type: 'flow_slice_end_error',
1792              message: 'event id ' + event.id + ' does not end ' +
1793                  'at an actual slice, so cannot be created.'});
1794          }
1795          flowIdToEvent[event.id] = undefined;
1796
1797          // If this is a step, then create another flow event.
1798          if (ok && event.ph === 't') {
1799            flowEvent = createFlowEvent(thread, event);
1800            flowIdToEvent[event.id] = flowEvent;
1801          }
1802        }
1803      }
1804    },
1805
1806    /**
1807     * This function creates objects described via the N, D, and O phase
1808     * events.
1809     */
1810    createExplicitObjects_: function() {
1811      if (this.allObjectEvents_.length === 0)
1812        return;
1813
1814      function processEvent(objectEventState) {
1815        var event = objectEventState.event;
1816        var scopedId = new tr.model.ScopedId(
1817            event.scope || tr.model.OBJECT_DEFAULT_SCOPE, event.id);
1818        var thread = objectEventState.thread;
1819        if (event.name === undefined) {
1820          this.model_.importWarning({
1821            type: 'object_parse_error',
1822            message: 'While processing ' + JSON.stringify(event) + ': ' +
1823                'Object events require an name parameter.'
1824          });
1825        }
1826
1827        if (scopedId.id === undefined) {
1828          this.model_.importWarning({
1829            type: 'object_parse_error',
1830            message: 'While processing ' + JSON.stringify(event) + ': ' +
1831                'Object events require an id parameter.'
1832          });
1833        }
1834        var process = thread.parent;
1835        var ts = timestampFromUs(event.ts);
1836        var instance;
1837        if (event.ph === 'N') {
1838          try {
1839            instance = process.objects.idWasCreated(
1840                scopedId, event.cat, event.name, ts);
1841          } catch (e) {
1842            this.model_.importWarning({
1843              type: 'object_parse_error',
1844              message: 'While processing create of ' +
1845                  scopedId + ' at ts=' + ts + ': ' + e
1846            });
1847            return;
1848          }
1849        } else if (event.ph === 'O') {
1850          if (event.args.snapshot === undefined) {
1851            this.model_.importWarning({
1852              type: 'object_parse_error',
1853              message: 'While processing ' + scopedId + ' at ts=' + ts + ': ' +
1854                  'Snapshots must have args: {snapshot: ...}'
1855            });
1856            return;
1857          }
1858          var snapshot;
1859          try {
1860            var args = this.deepCopyIfNeeded_(event.args.snapshot);
1861            var cat;
1862            if (args.cat) {
1863              cat = args.cat;
1864              delete args.cat;
1865            } else {
1866              cat = event.cat;
1867            }
1868
1869            var baseTypename;
1870            if (args.base_type) {
1871              baseTypename = args.base_type;
1872              delete args.base_type;
1873            } else {
1874              baseTypename = undefined;
1875            }
1876            snapshot = process.objects.addSnapshot(
1877                scopedId, cat, event.name, ts, args, baseTypename);
1878            snapshot.snapshottedOnThread = thread;
1879          } catch (e) {
1880            this.model_.importWarning({
1881              type: 'object_parse_error',
1882              message: 'While processing snapshot of ' +
1883                  scopedId + ' at ts=' + ts + ': ' + e
1884            });
1885            return;
1886          }
1887          instance = snapshot.objectInstance;
1888        } else if (event.ph === 'D') {
1889          try {
1890            process.objects.idWasDeleted(scopedId, event.cat, event.name, ts);
1891            var instanceMap = process.objects.getOrCreateInstanceMap_(scopedId);
1892            instance = instanceMap.lastInstance;
1893          } catch (e) {
1894            this.model_.importWarning({
1895              type: 'object_parse_error',
1896              message: 'While processing delete of ' +
1897                  scopedId + ' at ts=' + ts + ': ' + e
1898            });
1899            return;
1900          }
1901        }
1902
1903        if (instance)
1904          instance.colorId = getEventColor(event, instance.typeName);
1905      }
1906
1907      this.allObjectEvents_.sort(function(x, y) {
1908        var d = x.event.ts - y.event.ts;
1909        if (d != 0)
1910          return d;
1911        return x.sequenceNumber - y.sequenceNumber;
1912      });
1913
1914      var allObjectEvents = this.allObjectEvents_;
1915      for (var i = 0; i < allObjectEvents.length; i++) {
1916        var objectEventState = allObjectEvents[i];
1917        try {
1918          processEvent.call(this, objectEventState);
1919        } catch (e) {
1920          this.model_.importWarning({
1921            type: 'object_parse_error',
1922            message: e.message
1923          });
1924        }
1925      }
1926    },
1927
1928    createImplicitObjects_: function() {
1929      tr.b.iterItems(this.model_.processes, function(pid, process) {
1930        this.createImplicitObjectsForProcess_(process);
1931      }, this);
1932    },
1933
1934    // Here, we collect all the snapshots that internally contain a
1935    // Javascript-level object inside their args list that has an "id" field,
1936    // and turn that into a snapshot of the instance referred to by id.
1937    createImplicitObjectsForProcess_: function(process) {
1938
1939      function processField(referencingObject,
1940                            referencingObjectFieldName,
1941                            referencingObjectFieldValue,
1942                            containingSnapshot) {
1943        if (!referencingObjectFieldValue)
1944          return;
1945
1946        if (referencingObjectFieldValue instanceof
1947            tr.model.ObjectSnapshot)
1948          return null;
1949        if (referencingObjectFieldValue.id === undefined)
1950          return;
1951
1952        var implicitSnapshot = referencingObjectFieldValue;
1953
1954        var rawId = implicitSnapshot.id;
1955        var m = /(.+)\/(.+)/.exec(rawId);
1956        if (!m)
1957          throw new Error('Implicit snapshots must have names.');
1958        delete implicitSnapshot.id;
1959        var name = m[1];
1960        var id = m[2];
1961        var res;
1962
1963        var cat;
1964        if (implicitSnapshot.cat !== undefined)
1965          cat = implicitSnapshot.cat;
1966        else
1967          cat = containingSnapshot.objectInstance.category;
1968
1969        var baseTypename;
1970        if (implicitSnapshot.base_type)
1971          baseTypename = implicitSnapshot.base_type;
1972        else
1973          baseTypename = undefined;
1974
1975        var scope = containingSnapshot.objectInstance.scopedId.scope;
1976
1977        try {
1978          res = process.objects.addSnapshot(
1979              new tr.model.ScopedId(scope, id), cat,
1980              name, containingSnapshot.ts,
1981              implicitSnapshot, baseTypename);
1982        } catch (e) {
1983          this.model_.importWarning({
1984            type: 'object_snapshot_parse_error',
1985            message: 'While processing implicit snapshot of ' +
1986                rawId + ' at ts=' + containingSnapshot.ts + ': ' + e
1987          });
1988          return;
1989        }
1990        res.objectInstance.hasImplicitSnapshots = true;
1991        res.containingSnapshot = containingSnapshot;
1992        res.snapshottedOnThread = containingSnapshot.snapshottedOnThread;
1993        referencingObject[referencingObjectFieldName] = res;
1994        if (!(res instanceof tr.model.ObjectSnapshot))
1995          throw new Error('Created object must be instanceof snapshot');
1996        return res.args;
1997      }
1998
1999      /**
2000       * Iterates over the fields in the object, calling func for every
2001       * field/value found.
2002       *
2003       * @return {object} If the function does not want the field's value to be
2004       * iterated, return null. If iteration of the field value is desired, then
2005       * return either undefined (if the field value did not change) or the new
2006       * field value if it was changed.
2007       */
2008      function iterObject(object, func, containingSnapshot, thisArg) {
2009        if (!(object instanceof Object))
2010          return;
2011
2012        if (object instanceof Array) {
2013          for (var i = 0; i < object.length; i++) {
2014            var res = func.call(thisArg, object, i, object[i],
2015                                containingSnapshot);
2016            if (res === null)
2017              continue;
2018            if (res)
2019              iterObject(res, func, containingSnapshot, thisArg);
2020            else
2021              iterObject(object[i], func, containingSnapshot, thisArg);
2022          }
2023          return;
2024        }
2025
2026        for (var key in object) {
2027          var res = func.call(thisArg, object, key, object[key],
2028                              containingSnapshot);
2029          if (res === null)
2030            continue;
2031          if (res)
2032            iterObject(res, func, containingSnapshot, thisArg);
2033          else
2034            iterObject(object[key], func, containingSnapshot, thisArg);
2035        }
2036      }
2037
2038      // TODO(nduca): We may need to iterate the instances in sorted order by
2039      // creationTs.
2040      process.objects.iterObjectInstances(function(instance) {
2041        instance.snapshots.forEach(function(snapshot) {
2042          if (snapshot.args.id !== undefined)
2043            throw new Error('args cannot have an id field inside it');
2044          iterObject(snapshot.args, processField, snapshot, this);
2045        }, this);
2046      }, this);
2047    },
2048
2049    createMemoryDumps_: function() {
2050      for (var dumpId in this.allMemoryDumpEvents_)
2051        this.createGlobalMemoryDump_(this.allMemoryDumpEvents_[dumpId], dumpId);
2052    },
2053
2054    createGlobalMemoryDump_: function(dumpIdEvents, dumpId) {
2055      // 1. Create a GlobalMemoryDump for the provided process memory dump
2056      // the events, all of which have the same dump ID.
2057
2058      // Calculate the range of the global memory dump.
2059      var globalRange = new tr.b.Range();
2060      for (var pid in dumpIdEvents) {
2061        var processEvents = dumpIdEvents[pid];
2062        for (var i = 0; i < processEvents.length; i++)
2063          globalRange.addValue(timestampFromUs(processEvents[i].ts));
2064      }
2065      if (globalRange.isEmpty)
2066        throw new Error('Internal error: Global memory dump without events');
2067
2068      // Create the global memory dump.
2069      var globalMemoryDump = new tr.model.GlobalMemoryDump(
2070          this.model_, globalRange.min);
2071      globalMemoryDump.duration = globalRange.range;
2072      this.model_.globalMemoryDumps.push(globalMemoryDump);
2073
2074      var globalMemoryAllocatorDumpsByFullName = {};
2075      var levelOfDetailIndices = {};
2076      var allMemoryAllocatorDumpsByGuid = {};
2077
2078      // 2. Create a ProcessMemoryDump for each PID in the provided process
2079      // memory dump events. Everything except for edges between memory
2080      // allocator dumps is parsed from the process memory dump trace events at
2081      // this step.
2082      for (var pid in dumpIdEvents) {
2083        this.createProcessMemoryDump_(globalMemoryDump,
2084            globalMemoryAllocatorDumpsByFullName, levelOfDetailIndices,
2085            allMemoryAllocatorDumpsByGuid, dumpIdEvents[pid], pid, dumpId);
2086      }
2087
2088      // 3. Set the level of detail and memory allocator dumps of the
2089      // GlobalMemoryDump, which come from the process memory dump trace
2090      // events parsed in the prebvious step.
2091      globalMemoryDump.levelOfDetail =
2092          MEMORY_DUMP_LEVELS_OF_DETAIL[levelOfDetailIndices.global];
2093
2094      // Find the root allocator dumps and establish the parent links of
2095      // the global memory dump.
2096      globalMemoryDump.memoryAllocatorDumps =
2097          this.inferMemoryAllocatorDumpTree_(
2098              globalMemoryAllocatorDumpsByFullName);
2099
2100      // 4. Finally, parse the edges between all memory allocator dumps within
2101      // the GlobalMemoryDump. This can only be done once all memory allocator
2102      // dumps have been parsed (i.e. it is necessary to iterate over the
2103      // process memory dump trace events once more).
2104      this.parseMemoryDumpAllocatorEdges_(allMemoryAllocatorDumpsByGuid,
2105          dumpIdEvents, dumpId);
2106    },
2107
2108    createProcessMemoryDump_: function(globalMemoryDump,
2109        globalMemoryAllocatorDumpsByFullName, levelOfDetailIndices,
2110        allMemoryAllocatorDumpsByGuid, processEvents, pid, dumpId) {
2111      // Calculate the range of the process memory dump.
2112      var processRange = new tr.b.Range();
2113      for (var i = 0; i < processEvents.length; i++)
2114        processRange.addValue(timestampFromUs(processEvents[i].ts));
2115      if (processRange.isEmpty)
2116        throw new Error('Internal error: Process memory dump without events');
2117
2118      // Create the process memory dump.
2119      var process = this.model_.getOrCreateProcess(pid);
2120      var processMemoryDump = new tr.model.ProcessMemoryDump(
2121          globalMemoryDump, process, processRange.min);
2122      processMemoryDump.duration = processRange.range;
2123      process.memoryDumps.push(processMemoryDump);
2124      globalMemoryDump.processMemoryDumps[pid] = processMemoryDump;
2125
2126      var processMemoryAllocatorDumpsByFullName = {};
2127
2128      // Parse all process memory dump trace events for the newly created
2129      // ProcessMemoryDump.
2130      for (var i = 0; i < processEvents.length; i++) {
2131        var processEvent = processEvents[i];
2132
2133        var dumps = processEvent.args.dumps;
2134        if (dumps === undefined) {
2135          this.model_.importWarning({
2136            type: 'memory_dump_parse_error',
2137            message: '\'dumps\' field not found in a process memory dump' +
2138                ' event for PID=' + pid + ' and dump ID=' + dumpId + '.'
2139          });
2140          continue;
2141        }
2142
2143        // Totals, VM regions, and heap dumps for the newly created
2144        // ProcessMemoryDump should be present in at most one event, so they
2145        // can be added to the ProcessMemoryDump immediately.
2146        this.parseMemoryDumpTotals_(processMemoryDump, dumps, pid, dumpId);
2147        this.parseMemoryDumpVmRegions_(processMemoryDump, dumps, pid, dumpId);
2148        this.parseMemoryDumpHeapDumps_(processMemoryDump, dumps, pid, dumpId);
2149
2150        // All process memory dump trace events for the newly created
2151        // ProcessMemoryDump must be processed before level of detail and
2152        // allocator dumps can be added to it.
2153        this.parseMemoryDumpLevelOfDetail_(levelOfDetailIndices, dumps, pid,
2154            dumpId);
2155        this.parseMemoryDumpAllocatorDumps_(processMemoryDump, globalMemoryDump,
2156            processMemoryAllocatorDumpsByFullName,
2157            globalMemoryAllocatorDumpsByFullName,
2158            allMemoryAllocatorDumpsByGuid, dumps, pid, dumpId);
2159      }
2160
2161      processMemoryDump.levelOfDetail =
2162          MEMORY_DUMP_LEVELS_OF_DETAIL[levelOfDetailIndices.process];
2163      delete levelOfDetailIndices.process;  // Reused for all process dumps.
2164
2165      // Find the root allocator dumps and establish the parent links of
2166      // the process memory dump.
2167      processMemoryDump.memoryAllocatorDumps =
2168          this.inferMemoryAllocatorDumpTree_(
2169              processMemoryAllocatorDumpsByFullName);
2170    },
2171
2172    parseMemoryDumpTotals_: function(processMemoryDump, dumps, pid, dumpId) {
2173      var rawTotals = dumps.process_totals;
2174      if (rawTotals === undefined)
2175        return;
2176
2177      if (processMemoryDump.totals !== undefined) {
2178        this.model_.importWarning({
2179          type: 'memory_dump_parse_error',
2180          message: 'Process totals provided multiple times for' +
2181              ' process memory dump for PID=' + pid +
2182              ' and dump ID=' + dumpId + '.'
2183        });
2184        return;
2185      }
2186
2187      var totals = {};
2188      var platformSpecificTotals = undefined;
2189
2190      for (var rawTotalName in rawTotals) {
2191        var rawTotalValue = rawTotals[rawTotalName];
2192        if (rawTotalValue === undefined)
2193          continue;
2194
2195        // Total resident bytes.
2196        if (rawTotalName === 'resident_set_bytes') {
2197          totals.residentBytes = parseInt(rawTotalValue, 16);
2198          continue;
2199        }
2200
2201        // Peak resident bytes.
2202        if (rawTotalName === 'peak_resident_set_bytes') {
2203          totals.peakResidentBytes = parseInt(rawTotalValue, 16);
2204          continue;
2205        }
2206        if (rawTotalName === 'is_peak_rss_resetable') {
2207          totals.arePeakResidentBytesResettable = !!rawTotalValue;
2208          continue;
2209        }
2210
2211        // OS-specific totals (e.g. private resident on Mac).
2212        if (platformSpecificTotals === undefined) {
2213          platformSpecificTotals = {};
2214          totals.platformSpecific = platformSpecificTotals;
2215        }
2216        platformSpecificTotals[rawTotalName] = parseInt(rawTotalValue, 16);
2217      }
2218
2219      // Either both peak_resident_set_bytes and is_peak_rss_resetable should
2220      // be present in the trace, or neither.
2221      if (totals.peakResidentBytes === undefined &&
2222          totals.arePeakResidentBytesResettable !== undefined) {
2223        this.model_.importWarning({
2224            type: 'memory_dump_parse_error',
2225            message: 'Optional field peak_resident_set_bytes found' +
2226                ' but is_peak_rss_resetable not found in' +
2227                ' process memory dump for PID=' + pid +
2228                ' and dump ID=' + dumpId + '.'
2229        });
2230      }
2231      if (totals.arePeakResidentBytesResettable !== undefined &&
2232          totals.peakResidentBytes === undefined) {
2233        this.model_.importWarning({
2234            type: 'memory_dump_parse_error',
2235            message: 'Optional field is_peak_rss_resetable found' +
2236                ' but peak_resident_set_bytes not found in' +
2237                ' process memory dump for PID=' + pid +
2238                ' and dump ID=' + dumpId + '.'
2239        });
2240      }
2241
2242      processMemoryDump.totals = totals;
2243    },
2244
2245    parseMemoryDumpVmRegions_: function(processMemoryDump, dumps, pid, dumpId) {
2246      var rawProcessMmaps = dumps.process_mmaps;
2247      if (rawProcessMmaps === undefined)
2248        return;
2249
2250      var rawVmRegions = rawProcessMmaps.vm_regions;
2251      if (rawVmRegions === undefined)
2252        return;
2253
2254      if (processMemoryDump.vmRegions !== undefined) {
2255        this.model_.importWarning({
2256          type: 'memory_dump_parse_error',
2257          message: 'VM regions provided multiple times for' +
2258              ' process memory dump for PID=' + pid +
2259              ' and dump ID=' + dumpId + '.'
2260        });
2261        return;
2262      }
2263
2264      // See //base/trace_event/process_memory_maps.cc in Chromium.
2265      var vmRegions = new Array(rawVmRegions.length);
2266      for (var i = 0; i < rawVmRegions.length; i++) {
2267        var rawVmRegion = rawVmRegions[i];
2268
2269        var byteStats = {};
2270        var rawByteStats = rawVmRegion.bs;
2271        for (var rawByteStatName in rawByteStats) {
2272          var rawByteStatValue = rawByteStats[rawByteStatName];
2273          if (rawByteStatValue === undefined) {
2274            this.model_.importWarning({
2275              type: 'memory_dump_parse_error',
2276              message: 'Byte stat \'' + rawByteStatName + '\' of VM region ' +
2277                  i + ' (' + rawVmRegion.mf + ') in process memory dump for ' +
2278                  'PID=' + pid + ' and dump ID=' + dumpId +
2279                  ' does not have a value.'
2280            });
2281            continue;
2282          }
2283          var byteStatName = BYTE_STAT_NAME_MAP[rawByteStatName];
2284          if (byteStatName === undefined) {
2285            this.model_.importWarning({
2286              type: 'memory_dump_parse_error',
2287              message: 'Unknown byte stat name \'' + rawByteStatName + '\' (' +
2288                  rawByteStatValue + ') of VM region ' + i + ' (' +
2289                  rawVmRegion.mf + ') in process memory dump for PID=' + pid +
2290                  ' and dump ID=' + dumpId + '.'
2291            });
2292            continue;
2293          }
2294          byteStats[byteStatName] = parseInt(rawByteStatValue, 16);
2295        }
2296
2297        vmRegions[i] = new tr.model.VMRegion(
2298            parseInt(rawVmRegion.sa, 16),  // startAddress
2299            parseInt(rawVmRegion.sz, 16),  // sizeInBytes
2300            rawVmRegion.pf,  // protectionFlags
2301            rawVmRegion.mf,  // mappedFile
2302            byteStats);
2303      }
2304
2305      processMemoryDump.vmRegions =
2306          tr.model.VMRegionClassificationNode.fromRegions(vmRegions);
2307    },
2308
2309    parseMemoryDumpHeapDumps_: function(processMemoryDump, dumps, pid, dumpId) {
2310      var rawHeapDumps = dumps.heaps;
2311      if (rawHeapDumps === undefined)
2312        return;
2313
2314      if (processMemoryDump.heapDumps !== undefined) {
2315        this.model_.importWarning({
2316          type: 'memory_dump_parse_error',
2317          message: 'Heap dumps provided multiple times for' +
2318              ' process memory dump for PID=' + pid +
2319              ' and dump ID=' + dumpId + '.'
2320        });
2321        return;
2322      }
2323
2324      var model = this.model_;
2325      var idPrefix = 'p' + pid + ':';
2326      var heapDumps = {};
2327
2328      var objectTypeNameMap = this.objectTypeNameMap_[pid];
2329      if (objectTypeNameMap === undefined) {
2330        this.model_.importWarning({
2331          type: 'memory_dump_parse_error',
2332          message: 'Missing mapping from object type IDs to names.'
2333        });
2334      }
2335
2336      for (var allocatorName in rawHeapDumps) {
2337        var entries = rawHeapDumps[allocatorName].entries;
2338        if (entries === undefined || entries.length === 0) {
2339          this.model_.importWarning({
2340            type: 'memory_dump_parse_error',
2341            message: 'No heap entries in a ' + allocatorName +
2342                ' heap dump for PID=' + pid + ' and dump ID=' + dumpId + '.'
2343          });
2344          continue;
2345        }
2346
2347        // The old format always starts with a {size: <total>} entry.
2348        // See https://goo.gl/WYStil
2349        // TODO(petrcermak): Remove support for the old format once the new
2350        // format has been around long enough.
2351        var isOldFormat = entries[0].bt === undefined;
2352        if (!isOldFormat && objectTypeNameMap === undefined) {
2353          // Mapping from object type IDs to names must be provided in the new
2354          // format.
2355          continue;
2356        }
2357
2358        var heapDump = new tr.model.HeapDump(processMemoryDump, allocatorName);
2359
2360        for (var i = 0; i < entries.length; i++) {
2361          var entry = entries[i];
2362          var leafStackFrameIndex = entry.bt;
2363          var leafStackFrame;
2364
2365          // There are two possible mappings from leaf stack frame indices
2366          // (provided in the trace) to the corresponding stack frames
2367          // depending on the format.
2368          if (isOldFormat) {
2369            // Old format:
2370            //   Undefined index        -> / (root)
2371            //   Defined index for /A/B -> /A/B/<self>
2372            if (leafStackFrameIndex === undefined) {
2373              leafStackFrame = undefined /* root */;
2374            } else {
2375              // Get the leaf stack frame corresponding to the provided index.
2376              var leafStackFrameId = idPrefix + leafStackFrameIndex;
2377              if (leafStackFrameIndex === '') {
2378                leafStackFrame = undefined /* root */;
2379              } else {
2380                leafStackFrame = model.stackFrames[leafStackFrameId];
2381                if (leafStackFrame === undefined) {
2382                  this.model_.importWarning({
2383                    type: 'memory_dump_parse_error',
2384                    message: 'Missing leaf stack frame (ID ' +
2385                        leafStackFrameId + ') of heap entry ' + i + ' (size ' +
2386                        size + ') in a ' + allocatorName +
2387                        ' heap dump for PID=' + pid + '.'
2388                  });
2389                  continue;
2390                }
2391              }
2392
2393              // Inject an artificial <self> leaf stack frame.
2394              leafStackFrameId += ':self';
2395              if (model.stackFrames[leafStackFrameId] !== undefined) {
2396                // The frame might already exist if there are multiple process
2397                // memory dumps (for the same process) in the trace.
2398                leafStackFrame = model.stackFrames[leafStackFrameId];
2399              } else {
2400                leafStackFrame = new tr.model.StackFrame(
2401                    leafStackFrame, leafStackFrameId, '<self>',
2402                    undefined /* colorId */);
2403                model.addStackFrame(leafStackFrame);
2404              }
2405            }
2406          } else {
2407            // New format:
2408            //   Undefined index        -> (invalid value)
2409            //   Defined index for /A/B -> /A/B
2410            if (leafStackFrameIndex === undefined) {
2411              this.model_.importWarning({
2412                type: 'memory_dump_parse_error',
2413                message: 'Missing stack frame ID of heap entry ' + i +
2414                    ' (size ' + size + ') in a ' + allocatorName +
2415                    ' heap dump for PID=' + pid + '.'
2416              });
2417              continue;
2418            }
2419
2420            // Get the leaf stack frame corresponding to the provided index.
2421            var leafStackFrameId = idPrefix + leafStackFrameIndex;
2422            if (leafStackFrameIndex === '') {
2423              leafStackFrame = undefined /* root */;
2424            } else {
2425              leafStackFrame = model.stackFrames[leafStackFrameId];
2426              if (leafStackFrame === undefined) {
2427                this.model_.importWarning({
2428                  type: 'memory_dump_parse_error',
2429                  message: 'Missing leaf stack frame (ID ' + leafStackFrameId +
2430                      ') of heap entry ' + i + ' (size ' + size + ') in a ' +
2431                      allocatorName + ' heap dump for PID=' + pid + '.'
2432                });
2433                continue;
2434              }
2435            }
2436          }
2437
2438          var objectTypeId = entry.type;
2439          var objectTypeName;
2440          if (objectTypeId === undefined) {
2441            objectTypeName = undefined /* total over all types */;
2442          } else if (objectTypeNameMap === undefined) {
2443            // This can only happen when the old format is used.
2444            continue;
2445          } else {
2446            objectTypeName = objectTypeNameMap[objectTypeId];
2447            if (objectTypeName === undefined) {
2448              this.model_.importWarning({
2449                type: 'memory_dump_parse_error',
2450                message: 'Missing object type name (ID ' + objectTypeId +
2451                    ') of heap entry ' + i + ' (size ' + size + ') in a ' +
2452                    allocatorName + ' heap dump for pid=' + pid + '.'
2453              });
2454              continue;
2455            }
2456          }
2457
2458          var size = parseInt(entry.size, 16);
2459          heapDump.addEntry(leafStackFrame, objectTypeName, size);
2460        }
2461
2462        // Throw away heap dumps with no entries. This can happen if all raw
2463        // entries in the trace are skipped for some reason (e.g. invalid leaf
2464        // stack frame ID).
2465        if (heapDump.entries.length > 0)
2466          heapDumps[allocatorName] = heapDump;
2467      }
2468
2469      if (Object.keys(heapDumps).length > 0)
2470        processMemoryDump.heapDumps = heapDumps;
2471    },
2472
2473    parseMemoryDumpLevelOfDetail_: function(levelOfDetailIndices, dumps, pid,
2474        dumpId) {
2475      var rawLevelOfDetail = dumps.level_of_detail;
2476
2477      // Determine the index of the level of detail of the dump.
2478      var index = MEMORY_DUMP_LEVELS_OF_DETAIL.indexOf(rawLevelOfDetail);
2479      if (index < 0) {
2480        this.model_.importWarning({
2481          type: 'memory_dump_parse_error',
2482          message: 'unknown level of detail \'' + rawLevelOfDetail +
2483              '\' of process memory dump for PID=' + pid +
2484              ' and dump ID=' + dumpId + '.'
2485        });
2486        return;
2487      }
2488
2489      // If the process memory dump events have different levels of detail
2490      // (for the particular process and/or globally), show a warning and use
2491      // the highest level.
2492
2493      if (levelOfDetailIndices.process === undefined) {
2494        levelOfDetailIndices.process = index;
2495      } else if (index !== levelOfDetailIndices.process) {
2496        this.model_.importWarning({
2497          type: 'memory_dump_parse_error',
2498          message: 'diffent levels of detail provided for process memory' +
2499              ' dump for PID=' + pid + ' (dump ID=' + dumpId + ').'
2500        });
2501        levelOfDetailIndices.process =
2502            Math.max(levelOfDetailIndices.process, index);
2503      }
2504
2505      if (levelOfDetailIndices.global === undefined) {
2506        levelOfDetailIndices.global = index;
2507      } else if (index !== levelOfDetailIndices.global) {
2508        this.model_.importWarning({
2509          type: 'memory_dump_parse_error',
2510          message: 'diffent levels of detail provided for global memory' +
2511              ' dump (dump ID=' + dumpId + ').'
2512        });
2513        levelOfDetailIndices.global =
2514            Math.max(levelOfDetailIndices.global, index);
2515      }
2516    },
2517
2518    parseMemoryDumpAllocatorDumps_: function(processMemoryDump,
2519        globalMemoryDump, processMemoryAllocatorDumpsByFullName,
2520        globalMemoryAllocatorDumpsByFullName, allMemoryAllocatorDumpsByGuid,
2521        dumps, pid, dumpId) {
2522      var rawAllocatorDumps = dumps.allocators;
2523      if (rawAllocatorDumps === undefined)
2524        return;
2525
2526      // Construct the MemoryAllocatorDump objects without parent links
2527      // and add them to the processMemoryAllocatorDumpsByName and
2528      // globalMemoryAllocatorDumpsByName indices appropriately.
2529      for (var fullName in rawAllocatorDumps) {
2530        var rawAllocatorDump = rawAllocatorDumps[fullName];
2531
2532        // Every memory allocator dump should have a GUID. If not, then
2533        // it cannot be associated with any edges.
2534        var guid = rawAllocatorDump.guid;
2535        if (guid === undefined) {
2536          this.model_.importWarning({
2537            type: 'memory_dump_parse_error',
2538            message: 'Memory allocator dump ' + fullName + ' for PID=' + pid +
2539                ' and dump ID=' + dumpId + ' does not have a GUID.'
2540          });
2541        }
2542
2543        // A memory allocator dump can have optional flags.
2544        var flags = rawAllocatorDump.flags || 0;
2545        var isWeakDump = !!(flags & WEAK_MEMORY_ALLOCATOR_DUMP_FLAG);
2546
2547        // Determine if this is a global memory allocator dump (check if
2548        // it's prefixed with 'global/').
2549        var containerMemoryDump;
2550        var dstIndex;
2551        if (fullName.startsWith(GLOBAL_MEMORY_ALLOCATOR_DUMP_PREFIX)) {
2552          // Global memory allocator dump.
2553          fullName = fullName.substring(
2554              GLOBAL_MEMORY_ALLOCATOR_DUMP_PREFIX.length);
2555          containerMemoryDump = globalMemoryDump;
2556          dstIndex = globalMemoryAllocatorDumpsByFullName;
2557        } else {
2558          // Process memory allocator dump.
2559          containerMemoryDump = processMemoryDump;
2560          dstIndex = processMemoryAllocatorDumpsByFullName;
2561        }
2562
2563        // Construct or retrieve a memory allocator dump with the provided
2564        // GUID.
2565        var allocatorDump = allMemoryAllocatorDumpsByGuid[guid];
2566        if (allocatorDump === undefined) {
2567          if (fullName in dstIndex) {
2568            this.model_.importWarning({
2569              type: 'memory_dump_parse_error',
2570              message: 'Multiple GUIDs provided for' +
2571                  ' memory allocator dump ' + fullName + ': ' +
2572                  dstIndex[fullName].guid + ', ' + guid + ' (ignored) for' +
2573                  ' PID=' + pid + ' and dump ID=' + dumpId + '.'
2574            });
2575            continue;
2576          }
2577          allocatorDump = new tr.model.MemoryAllocatorDump(
2578              containerMemoryDump, fullName, guid);
2579          allocatorDump.weak = isWeakDump;
2580          dstIndex[fullName] = allocatorDump;
2581          if (guid !== undefined)
2582            allMemoryAllocatorDumpsByGuid[guid] = allocatorDump;
2583        } else {
2584          // A memory allocator dump with this GUID has already been
2585          // dumped (so we will only add new attributes). Check that it
2586          // belonged to the same process or was also global.
2587          if (allocatorDump.containerMemoryDump !== containerMemoryDump) {
2588            this.model_.importWarning({
2589            type: 'memory_dump_parse_error',
2590            message: 'Memory allocator dump ' + fullName +
2591                ' (GUID=' + guid + ') for PID=' + pid + ' and dump ID=' +
2592                dumpId + ' dumped in different contexts.'
2593            });
2594            continue;
2595          }
2596          // Check that the names of the memory allocator dumps match.
2597          if (allocatorDump.fullName !== fullName) {
2598            this.model_.importWarning({
2599            type: 'memory_dump_parse_error',
2600            message: 'Memory allocator dump with GUID=' + guid + ' for PID=' +
2601                pid + ' and dump ID=' + dumpId + ' has multiple names: ' +
2602                allocatorDump.fullName + ', ' + fullName + ' (ignored).'
2603            });
2604            continue;
2605          }
2606          if (!isWeakDump) {
2607            // A MemoryAllocatorDump is non-weak if at least one process dumped
2608            // it without WEAK_MEMORY_ALLOCATOR_DUMP_FLAG.
2609            allocatorDump.weak = false;
2610          }
2611        }
2612
2613        // Add all new attributes to the memory allocator dump.
2614        var attributes = rawAllocatorDump.attrs;
2615        if (attributes === undefined) {
2616          this.model_.importWarning({
2617            type: 'memory_dump_parse_error',
2618            message: 'Memory allocator dump ' + fullName + ' (GUID=' + guid +
2619                ') for PID=' + pid + ' and dump ID=' + dumpId +
2620                ' does not have attributes.'
2621          });
2622          attributes = {};
2623        }
2624
2625        for (var attrName in attributes) {
2626          var attrArgs = attributes[attrName];
2627          var attrType = attrArgs.type;
2628          var attrValue = attrArgs.value;
2629
2630          switch (attrType) {
2631            case 'scalar':
2632              if (attrName in allocatorDump.numerics) {
2633                this.model_.importWarning({
2634                type: 'memory_dump_parse_error',
2635                message: 'Multiple values provided for scalar attribute ' +
2636                    attrName + ' of memory allocator dump ' + fullName +
2637                    ' (GUID=' + guid + ') for PID=' + pid + ' and dump ID=' +
2638                    dumpId + '.'
2639                });
2640                break;
2641              }
2642              var unit = attrArgs.units === 'bytes' ?
2643                  tr.v.Unit.byName.sizeInBytes_smallerIsBetter :
2644                  tr.v.Unit.byName.unitlessNumber_smallerIsBetter;
2645              var value = parseInt(attrValue, 16);
2646              allocatorDump.addNumeric(attrName,
2647                  new tr.v.ScalarNumeric(unit, value));
2648              break;
2649
2650            case 'string':
2651              if (attrName in allocatorDump.diagnostics) {
2652                this.model_.importWarning({
2653                type: 'memory_dump_parse_error',
2654                message: 'Multiple values provided for string attribute ' +
2655                    attrName + ' of memory allocator dump ' + fullName +
2656                    ' (GUID=' + guid + ') for PID=' + pid + ' and dump ID=' +
2657                    dumpId + '.'
2658                });
2659                break;
2660              }
2661              allocatorDump.addDiagnostic(attrName, attrValue);
2662              break;
2663
2664            default:
2665              this.model_.importWarning({
2666              type: 'memory_dump_parse_error',
2667              message: 'Unknown type provided for attribute ' + attrName +
2668                  ' of memory allocator dump ' + fullName + ' (GUID=' + guid +
2669                  ') for PID=' + pid + ' and dump ID=' + dumpId + ': ' +
2670                  attrType
2671              });
2672              break;
2673          }
2674        }
2675      }
2676    },
2677
2678    inferMemoryAllocatorDumpTree_: function(memoryAllocatorDumpsByFullName) {
2679      var rootAllocatorDumps = [];
2680
2681      var fullNames = Object.keys(memoryAllocatorDumpsByFullName);
2682      fullNames.sort();
2683      for (var i = 0; i < fullNames.length; i++) {
2684        var fullName = fullNames[i];
2685        var allocatorDump = memoryAllocatorDumpsByFullName[fullName];
2686
2687        // This is a loop because we might need to build implicit
2688        // ancestors in case they were not present in the trace.
2689        while (true) {
2690          var lastSlashIndex = fullName.lastIndexOf('/');
2691          if (lastSlashIndex === -1) {
2692            // If the dump is a root, add it to the top-level
2693            // rootAllocatorDumps list.
2694            rootAllocatorDumps.push(allocatorDump);
2695            break;
2696          }
2697
2698          // If the dump is not a root, find its parent.
2699          var parentFullName = fullName.substring(0, lastSlashIndex);
2700          var parentAllocatorDump =
2701              memoryAllocatorDumpsByFullName[parentFullName];
2702
2703          // If the parent dump does not exist yet, we build an implicit
2704          // one and continue up the ancestor chain.
2705          var parentAlreadyExisted = true;
2706          if (parentAllocatorDump === undefined) {
2707            parentAlreadyExisted = false;
2708            parentAllocatorDump = new tr.model.MemoryAllocatorDump(
2709                allocatorDump.containerMemoryDump, parentFullName);
2710            if (allocatorDump.weak !== false) {
2711              // If we are inferring a parent dump (e.g. 'root/parent') of a
2712              // current dump (e.g. 'root/parent/current') which is weak (or
2713              // was also inferred and we don't know yet whether it's weak or
2714              // not), then we clear the weak flag on the parent dump because
2715              // we don't know yet whether it should be weak or non-weak:
2716              //
2717              //   * We can't mark the parent as non-weak straightaway because
2718              //     the parent might have no non-weak descendants (in which
2719              //     case we want the inferred parent to be weak, so that it
2720              //     would be later removed like the current dump).
2721              //   * We can't mark the parent as weak immediately either. If we
2722              //     did and later encounter a non-weak child of the parent
2723              //     (e.g. 'root/parent/another_child'), then we couldn't
2724              //     retroactively mark the inferred parent dump as non-weak
2725              //     because we couldn't tell whether the parent dump was
2726              //     dumped in the trace as weak (in which case it should stay
2727              //     weak and be subsequently removed) or whether it was
2728              //     inferred as weak (in which case it should be changed to
2729              //     non-weak).
2730              //
2731              // Therefore, we defer marking the inferred parent as
2732              // weak/non-weak. If an inferred parent dump does not have any
2733              // non-weak child, it will be marked as weak at the end of this
2734              // method.
2735              //
2736              // Note that this should not be confused with the recursive
2737              // propagation of the weak flag from parent dumps to their
2738              // children and from owned dumps to their owners, which is
2739              // performed in GlobalMemoryDump.prototype.removeWeakDumps().
2740              parentAllocatorDump.weak = undefined;
2741            }
2742            memoryAllocatorDumpsByFullName[parentFullName] =
2743                parentAllocatorDump;
2744          }
2745
2746          // Setup the parent <-> children relationships
2747          allocatorDump.parent = parentAllocatorDump;
2748          parentAllocatorDump.children.push(allocatorDump);
2749
2750          // If the parent already existed, then its ancestors were/will be
2751          // constructed in another iteration of the forEach loop.
2752          if (parentAlreadyExisted) {
2753            if (!allocatorDump.weak) {
2754              // If the current dump is non-weak, then we must ensure that all
2755              // its inferred ancestors are also non-weak.
2756              while (parentAllocatorDump !== undefined &&
2757                     parentAllocatorDump.weak === undefined) {
2758                parentAllocatorDump.weak = false;
2759                parentAllocatorDump = parentAllocatorDump.parent;
2760              }
2761            }
2762            break;
2763          }
2764
2765          fullName = parentFullName;
2766          allocatorDump = parentAllocatorDump;
2767        }
2768      }
2769
2770      // All inferred ancestor dumps that have a non-weak child have already
2771      // been marked as non-weak. We now mark the rest as weak.
2772      for (var fullName in memoryAllocatorDumpsByFullName) {
2773        var allocatorDump = memoryAllocatorDumpsByFullName[fullName];
2774        if (allocatorDump.weak === undefined)
2775          allocatorDump.weak = true;
2776      }
2777
2778      return rootAllocatorDumps;
2779    },
2780
2781    parseMemoryDumpAllocatorEdges_: function(allMemoryAllocatorDumpsByGuid,
2782        dumpIdEvents, dumpId) {
2783      for (var pid in dumpIdEvents) {
2784        var processEvents = dumpIdEvents[pid];
2785
2786        for (var i = 0; i < processEvents.length; i++) {
2787          var processEvent = processEvents[i];
2788
2789          var dumps = processEvent.args.dumps;
2790          if (dumps === undefined)
2791            continue;
2792
2793          var rawEdges = dumps.allocators_graph;
2794          if (rawEdges === undefined)
2795            continue;
2796
2797          for (var j = 0; j < rawEdges.length; j++) {
2798            var rawEdge = rawEdges[j];
2799
2800            var sourceGuid = rawEdge.source;
2801            var sourceDump = allMemoryAllocatorDumpsByGuid[sourceGuid];
2802            if (sourceDump === undefined) {
2803              this.model_.importWarning({
2804                type: 'memory_dump_parse_error',
2805                message: 'Edge for PID=' + pid + ' and dump ID=' + dumpId +
2806                    ' is missing source memory allocator dump (GUID=' +
2807                    sourceGuid + ').'
2808              });
2809              continue;
2810            }
2811
2812            var targetGuid = rawEdge.target;
2813            var targetDump = allMemoryAllocatorDumpsByGuid[targetGuid];
2814            if (targetDump === undefined) {
2815              this.model_.importWarning({
2816                type: 'memory_dump_parse_error',
2817                message: 'Edge for PID=' + pid + ' and dump ID=' + dumpId +
2818                    ' is missing target memory allocator dump (GUID=' +
2819                    targetGuid + ').'
2820              });
2821              continue;
2822            }
2823
2824            var importance = rawEdge.importance;
2825            var edge = new tr.model.MemoryAllocatorDumpLink(
2826                sourceDump, targetDump, importance);
2827
2828            switch (rawEdge.type) {
2829              case 'ownership':
2830                if (sourceDump.owns !== undefined) {
2831                  this.model_.importWarning({
2832                    type: 'memory_dump_parse_error',
2833                    message: 'Memory allocator dump ' + sourceDump.fullName +
2834                        ' (GUID=' + sourceGuid + ') already owns a memory' +
2835                        ' allocator dump (' +
2836                        sourceDump.owns.target.fullName + ').'
2837                  });
2838                } else {
2839                  sourceDump.owns = edge;
2840                  targetDump.ownedBy.push(edge);
2841                }
2842                break;
2843
2844              case 'retention':
2845                sourceDump.retains.push(edge);
2846                targetDump.retainedBy.push(edge);
2847                break;
2848
2849              default:
2850                this.model_.importWarning({
2851                  type: 'memory_dump_parse_error',
2852                  message: 'Invalid edge type: ' + rawEdge.type +
2853                      ' (PID=' + pid + ', dump ID=' + dumpId +
2854                      ', source=' + sourceGuid + ', target=' + targetGuid +
2855                      ', importance=' + importance + ').'
2856                });
2857            }
2858          }
2859        }
2860      }
2861    }
2862  };
2863
2864  tr.importer.Importer.register(TraceEventImporter);
2865
2866  return {
2867    TraceEventImporter: TraceEventImporter
2868  };
2869});
2870</script>
2871