src/third_party/trace-viewer/trace_viewer/tracing/importer/trace_event_importer.js

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 'use strict';
   6
   7 /**
   8  * @fileoverview TraceEventImporter imports TraceEvent-formatted data
   9  * into the provided model.
  10  */
  11 tvcm.require('tvcm.quad');
  12 tvcm.require('tracing.trace_model');
  13 tvcm.require('tracing.color_scheme');
  14 tvcm.require('tracing.importer.importer');
  15 tvcm.require('tracing.trace_model.instant_event');
  16 tvcm.require('tracing.trace_model.flow_event');
  17 tvcm.require('tracing.trace_model.counter_series');
  18
  19 tvcm.exportTo('tracing.importer', function() {
  20
  21   var Importer = tracing.importer.Importer;
  22
  23   function deepCopy(value) {
  24     if (!(value instanceof Object)) {
  25       if (value === undefined || value === null)
  26         return value;
  27       if (typeof value == 'string')
  28         return value.substring();
  29       if (typeof value == 'boolean')
  30         return value;
  31       if (typeof value == 'number')
  32         return value;
  33       throw new Error('Unrecognized: ' + typeof value);
  34     }
  35
  36     var object = value;
  37     if (object instanceof Array) {
  38       var res = new Array(object.length);
  39       for (var i = 0; i < object.length; i++)
  40         res[i] = deepCopy(object[i]);
  41       return res;
  42     }
  43
  44     if (object.__proto__ != Object.prototype)
  45       throw new Error('Can only clone simple types');
  46     var res = {};
  47     for (var key in object) {
  48       res[key] = deepCopy(object[key]);
  49     }
  50     return res;
  51   }
  52
  53   function TraceEventImporter(model, eventData) {
  54     this.importPriority = 1;
  55     this.model_ = model;
  56     this.events_ = undefined;
  57     this.sampleEvents_ = undefined;
  58     this.stackFrameEvents_ = undefined;
  59     this.systemTraceEvents_ = undefined;
  60     this.eventsWereFromString_ = false;
  61     this.allAsyncEvents_ = [];
  62     this.allFlowEvents_ = [];
  63     this.allObjectEvents_ = [];
  64
  65     if (typeof(eventData) === 'string' || eventData instanceof String) {
  66       // If the event data begins with a [, then we know it should end with a ].
  67       // The reason we check for this is because some tracing implementations
  68       // cannot guarantee that a ']' gets written to the trace file. So, we are
  69       // forgiving and if this is obviously the case, we fix it up before
  70       // throwing the string at JSON.parse.
  71       if (eventData[0] === '[') {
  72         eventData = eventData.replace(/[\r|\n]*$/, '')
  73                              .replace(/\s*,\s*$/, '');
  74         if (eventData[eventData.length - 1] !== ']')
  75           eventData = eventData + ']';
  76       }
  77       this.events_ = JSON.parse(eventData);
  78       this.eventsWereFromString_ = true;
  79     } else {
  80       this.events_ = eventData;
  81     }
  82
  83     // Some trace_event implementations put the actual trace events
  84     // inside a container. E.g { ... , traceEvents: [ ] }
  85     // If we see that, just pull out the trace events.
  86     if (this.events_.traceEvents) {
  87       var container = this.events_;
  88       this.events_ = this.events_.traceEvents;
  89
  90       // Some trace_event implementations put linux_perf_importer traces as a
  91       // huge string inside container.systemTraceEvents. If we see that, pull it
  92       // out. It will be picked up by extractSubtraces later on.
  93       this.systemTraceEvents_ = container.systemTraceEvents;
  94
  95       // Sampling data.
  96       this.sampleEvents_ = container.samples;
  97       this.stackFrameEvents_ = container.stackFrames;
  98
  99       // Any other fields in the container should be treated as metadata.
 100       for (var fieldName in container) {
 101         if (fieldName === 'traceEvents' || fieldName === 'systemTraceEvents' ||
 102             fieldName === 'samples' || fieldName === 'stackFrames')
 103           continue;
 104         this.model_.metadata.push({name: fieldName,
 105           value: container[fieldName]});
 106       }
 107     }
 108   }
 109
 110   /**
 111    * @return {boolean} Whether obj is a TraceEvent array.
 112    */
 113   TraceEventImporter.canImport = function(eventData) {
 114     // May be encoded JSON. But we dont want to parse it fully yet.
 115     // Use a simple heuristic:
 116     //   - eventData that starts with [ are probably trace_event
 117     //   - eventData that starts with { are probably trace_event
 118     // May be encoded JSON. Treat files that start with { as importable by us.
 119     if (typeof(eventData) === 'string' || eventData instanceof String) {
 120       return eventData[0] == '{' || eventData[0] == '[';
 121     }
 122
 123     // Might just be an array of events
 124     if (eventData instanceof Array && eventData.length && eventData[0].ph)
 125       return true;
 126
 127     // Might be an object with a traceEvents field in it.
 128     if (eventData.traceEvents) {
 129       if (eventData.traceEvents instanceof Array) {
 130         if (eventData.traceEvents.length && eventData.traceEvents[0].ph)
 131           return true;
 132         if (eventData.samples.length && eventData.stackFrames !== undefined)
 133           return true;
 134       }
 135     }
 136
 137     return false;
 138   };
 139
 140   TraceEventImporter.prototype = {
 141
 142     __proto__: Importer.prototype,
 143
 144     extractSubtraces: function() {
 145       var tmp = this.systemTraceEvents_;
 146       this.systemTraceEvents_ = undefined;
 147       return tmp ? [tmp] : [];
 148     },
 149
 150     /**
 151      * Deep copying is only needed if the trace was given to us as events.
 152      */
 153     deepCopyIfNeeded_: function(obj) {
 154       if (obj === undefined)
 155         obj = {};
 156       if (this.eventsWereFromString_)
 157         return obj;
 158       return deepCopy(obj);
 159     },
 160
 161     /**
 162      * Helper to process an async event.
 163      */
 164     processAsyncEvent: function(event) {
 165       var thread = this.model_.getOrCreateProcess(event.pid).
 166           getOrCreateThread(event.tid);
 167       this.allAsyncEvents_.push({
 168         sequenceNumber: this.allAsyncEvents_.length,
 169         event: event,
 170         thread: thread});
 171     },
 172
 173     /**
 174      * Helper to process a flow event.
 175      */
 176     processFlowEvent: function(event) {
 177       var thread = this.model_.getOrCreateProcess(event.pid).
 178           getOrCreateThread(event.tid);
 179       this.allFlowEvents_.push({
 180         sequenceNumber: this.allFlowEvents_.length,
 181         event: event,
 182         thread: thread
 183       });
 184     },
 185
 186     /**
 187      * Helper that creates and adds samples to a Counter object based on
 188      * 'C' phase events.
 189      */
 190     processCounterEvent: function(event) {
 191       var ctr_name;
 192       if (event.id !== undefined)
 193         ctr_name = event.name + '[' + event.id + ']';
 194       else
 195         ctr_name = event.name;
 196
 197       var ctr = this.model_.getOrCreateProcess(event.pid)
 198           .getOrCreateCounter(event.cat, ctr_name);
 199
 200       // Initialize the counter's series fields if needed.
 201       if (ctr.numSeries === 0) {
 202         for (var seriesName in event.args) {
 203           ctr.addSeries(new tracing.trace_model.CounterSeries(seriesName,
 204               tvcm.ui.getStringColorId(ctr.name + '.' + seriesName)));
 205         }
 206
 207         if (ctr.numSeries === 0) {
 208           this.model_.importWarning({
 209             type: 'counter_parse_error',
 210             message: 'Expected counter ' + event.name +
 211                 ' to have at least one argument to use as a value.'
 212           });
 213
 214           // Drop the counter.
 215           delete ctr.parent.counters[ctr.name];
 216           return;
 217         }
 218       }
 219
 220       var ts = event.ts / 1000;
 221       ctr.series.forEach(function(series) {
 222         var val = event.args[series.name] ? event.args[series.name] : 0;
 223         series.addCounterSample(ts, val);
 224       });
 225     },
 226
 227     processObjectEvent: function(event) {
 228       var thread = this.model_.getOrCreateProcess(event.pid).
 229           getOrCreateThread(event.tid);
 230       this.allObjectEvents_.push({
 231         sequenceNumber: this.allObjectEvents_.length,
 232         event: event,
 233         thread: thread});
 234     },
 235
 236     processDurationEvent: function(event) {
 237       var thread = this.model_.getOrCreateProcess(event.pid)
 238         .getOrCreateThread(event.tid);
 239       if (!thread.sliceGroup.isTimestampValidForBeginOrEnd(event.ts / 1000)) {
 240         this.model_.importWarning({
 241           type: 'duration_parse_error',
 242           message: 'Timestamps are moving backward.'
 243         });
 244         return;
 245       }
 246
 247       if (event.ph == 'B') {
 248         thread.sliceGroup.beginSlice(event.cat, event.name, event.ts / 1000,
 249                                      this.deepCopyIfNeeded_(event.args),
 250                                      event.tts / 1000);
 251       } else {
 252         if (!thread.sliceGroup.openSliceCount) {
 253           this.model_.importWarning({
 254             type: 'duration_parse_error',
 255             message: 'E phase event without a matching B phase event.'
 256           });
 257           return;
 258         }
 259
 260         var slice = thread.sliceGroup.endSlice(event.ts / 1000,
 261                                                event.tts / 1000);
 262         if (event.name && slice.title != event.name) {
 263           this.model_.importWarning({
 264             type: 'title_match_error',
 265             message: 'Titles do not match. Title is ' +
 266                 slice.title + ' in openSlice, and is ' +
 267                 event.name + ' in endSlice'
 268           });
 269         }
 270         for (var arg in event.args) {
 271           if (slice.args[arg] !== undefined) {
 272             this.model_.importWarning({
 273               type: 'duration_parse_error',
 274               message: 'Both the B and E phases of ' + slice.name +
 275                   ' provided values for argument ' + arg + '.' +
 276                   ' The value of the E phase event will be used.'
 277             });
 278           }
 279           slice.args[arg] = this.deepCopyIfNeeded_(event.args[arg]);
 280         }
 281       }
 282     },
 283
 284     processCompleteEvent: function(event) {
 285       var thread = this.model_.getOrCreateProcess(event.pid)
 286           .getOrCreateThread(event.tid);
 287       thread.sliceGroup.pushCompleteSlice(event.cat, event.name,
 288           event.ts / 1000,
 289           event.dur === undefined ? undefined : event.dur / 1000,
 290           event.tts === undefined ? undefined : event.tts / 1000,
 291           event.tdur === undefined ? undefined : event.tdur / 1000,
 292           this.deepCopyIfNeeded_(event.args));
 293     },
 294
 295     processMetadataEvent: function(event) {
 296       if (event.name == 'process_name') {
 297         var process = this.model_.getOrCreateProcess(event.pid);
 298         process.name = event.args.name;
 299       } else if (event.name == 'process_labels') {
 300         var process = this.model_.getOrCreateProcess(event.pid);
 301         var labels = event.args.labels.split(',');
 302         for (var i = 0; i < labels.length; i++)
 303           process.addLabelIfNeeded(labels[i]);
 304       } else if (event.name == 'process_sort_index') {
 305         var process = this.model_.getOrCreateProcess(event.pid);
 306         process.sortIndex = event.args.sort_index;
 307       } else if (event.name == 'thread_name') {
 308         var thread = this.model_.getOrCreateProcess(event.pid).
 309             getOrCreateThread(event.tid);
 310         thread.name = event.args.name;
 311       } else if (event.name == 'thread_sort_index') {
 312         var thread = this.model_.getOrCreateProcess(event.pid).
 313             getOrCreateThread(event.tid);
 314         thread.sortIndex = event.args.sort_index;
 315       } else {
 316         this.model_.importWarning({
 317           type: 'metadata_parse_error',
 318           message: 'Unrecognized metadata name: ' + event.name
 319         });
 320       }
 321     },
 322
 323     // Treat an Instant event as a duration 0 slice.
 324     // SliceTrack's redraw() knows how to handle this.
 325     processInstantEvent: function(event) {
 326       var constructor;
 327       switch (event.s) {
 328         case 'g':
 329           constructor = tracing.trace_model.GlobalInstantEvent;
 330           break;
 331         case 'p':
 332           constructor = tracing.trace_model.ProcessInstantEvent;
 333           break;
 334         case 't':
 335           // fall through
 336         default:
 337           // Default to thread to support old style input files.
 338           constructor = tracing.trace_model.ThreadInstantEvent;
 339           break;
 340       }
 341
 342       var colorId = tvcm.ui.getStringColorId(event.name);
 343       var instantEvent = new constructor(event.cat, event.name,
 344           colorId, event.ts / 1000, this.deepCopyIfNeeded_(event.args));
 345
 346       switch (instantEvent.type) {
 347         case tracing.trace_model.InstantEventType.GLOBAL:
 348           this.model_.pushInstantEvent(instantEvent);
 349           break;
 350
 351         case tracing.trace_model.InstantEventType.PROCESS:
 352           var process = this.model_.getOrCreateProcess(event.pid);
 353           process.pushInstantEvent(instantEvent);
 354           break;
 355
 356         case tracing.trace_model.InstantEventType.THREAD:
 357           var thread = this.model_.getOrCreateProcess(event.pid)
 358               .getOrCreateThread(event.tid);
 359           thread.sliceGroup.pushInstantEvent(instantEvent);
 360           break;
 361         default:
 362           throw new Error('Unknown instant event type: ' + event.s);
 363       }
 364     },
 365
 366     processTraceSampleEvent: function(event) {
 367       var thread = this.model_.getOrCreateProcess(event.pid)
 368         .getOrCreateThread(event.tid);
 369
 370       var id = 'te-' + tvcm.GUID.allocate();
 371       var stackFrame = new tracing.trace_model.StackFrame(
 372           undefined, id,
 373           event.cat, event.name,
 374           tvcm.ui.getStringColorId(event.name));
 375       this.model_.addStackFrame(stackFrame);
 376
 377       var sample = new tracing.trace_model.Sample(
 378           undefined, thread, 'TRACE_EVENT_SAMPLE',
 379           event.ts / 1000, stackFrame, 1,
 380           this.deepCopyIfNeeded_(event.args));
 381       this.model_.samples.push(sample);
 382     },
 383
 384     /**
 385      * Walks through the events_ list and outputs the structures discovered to
 386      * model_.
 387      */
 388     importEvents: function() {
 389       var events = this.events_;
 390       for (var eI = 0; eI < events.length; eI++) {
 391         var event = events[eI];
 392         if (event.ph === 'B' || event.ph === 'E') {
 393           this.processDurationEvent(event);
 394
 395         } else if (event.ph === 'X') {
 396           this.processCompleteEvent(event);
 397
 398         } else if (event.ph === 'S' || event.ph === 'F' || event.ph === 'T' ||
 399                    event.ph === 'p') {
 400           this.processAsyncEvent(event);
 401
 402         // Note, I is historic. The instant event marker got changed, but we
 403         // want to support loading old trace files so we have both I and i.
 404         } else if (event.ph == 'I' || event.ph == 'i') {
 405           this.processInstantEvent(event);
 406
 407         } else if (event.ph == 'P') {
 408           this.processTraceSampleEvent(event);
 409
 410         } else if (event.ph == 'C') {
 411           this.processCounterEvent(event);
 412
 413         } else if (event.ph == 'M') {
 414           this.processMetadataEvent(event);
 415
 416         } else if (event.ph === 'N' || event.ph === 'D' || event.ph === 'O') {
 417           this.processObjectEvent(event);
 418
 419         } else if (event.ph === 's' || event.ph === 't' || event.ph === 'f') {
 420           this.processFlowEvent(event);
 421
 422         } else {
 423           this.model_.importWarning({
 424             type: 'parse_error',
 425             message: 'Unrecognized event phase: ' +
 426                 event.ph + ' (' + event.name + ')'
 427           });
 428         }
 429       }
 430
 431       if (this.stackFrameEvents_)
 432         this.importStackFrames_();
 433     },
 434
 435     importStackFrames_: function() {
 436       var m = this.model_;
 437       var events = this.stackFrameEvents_;
 438       for (var id in events) {
 439         var event = events[id];
 440         var textForColor = event.category ? event.category : event.name;
 441         var frame = new tracing.trace_model.StackFrame(
 442             undefined, id,
 443             event.category, event.name,
 444             tvcm.ui.getStringColorId(textForColor));
 445         m.addStackFrame(frame);
 446       }
 447       for (var id in events) {
 448         var event = events[id];
 449         if (event.parent === undefined)
 450           continue;
 451
 452         var frame = m.stackFrames[id];
 453         if (frame === undefined)
 454           throw new Error('omg');
 455         var parentFrame;
 456         if (event.parent === undefined) {
 457           parentFrame = undefined;
 458         } else {
 459           parentFrame = m.stackFrames[event.parent];
 460           if (parentFrame === undefined)
 461             throw new Error('omg');
 462         }
 463         frame.parentFrame = parentFrame;
 464       }
 465     },
 466
 467     /**
 468      * Called by the Model after all other importers have imported their
 469      * events.
 470      */
 471     finalizeImport: function() {
 472       this.createAsyncSlices_();
 473       this.createFlowSlices_();
 474       this.createExplicitObjects_();
 475       this.createImplicitObjects_();
 476     },
 477
 478     importSampleData: function() {
 479       if (!this.sampleEvents_)
 480         return;
 481       var m = this.model_;
 482
 483       // If this is the only importer, then fake-create the threads.
 484       var events = this.sampleEvents_;
 485       if (this.events_.length === 0) {
 486         for (var i = 0; i < events.length; i++) {
 487           var event = events[i];
 488           m.getOrCreateProcess(event.tid).getOrCreateThread(event.tid);
 489         }
 490       }
 491
 492       var threadsByTid = {};
 493       m.getAllThreads().forEach(function(t) {
 494         threadsByTid[t.tid] = t;
 495       });
 496
 497       for (var i = 0; i < events.length; i++) {
 498         var event = events[i];
 499         var thread = threadsByTid[event.tid];
 500         if (thread === undefined) {
 501           m.importWarning({
 502             type: 'sample_import_error',
 503             message: 'Thread ' + events.tid + 'not found'
 504           });
 505           continue;
 506         }
 507
 508         var cpu;
 509         if (event.cpu !== undefined)
 510           cpu = m.kernel.getOrCreateCpu(event.cpu);
 511
 512         var stackFrame = m.stackFrames[event.sf];
 513         if (stackFrame === undefined) {
 514           m.importWarning({
 515             type: 'sample_import_error',
 516             message: 'No frame for ' + event.sf
 517           });
 518           continue;
 519         }
 520
 521         var sample = new tracing.trace_model.Sample(
 522             cpu, thread,
 523             event.name, event.ts / 1000,
 524             stackFrame,
 525             event.weight);
 526         m.samples.push(sample);
 527       }
 528     },
 529
 530     /**
 531      * Called by the model to join references between objects, after final model
 532      * bounds have been computed.
 533      */
 534     joinRefs: function() {
 535       this.joinObjectRefs_();
 536     },
 537
 538     createAsyncSlices_: function() {
 539       if (this.allAsyncEvents_.length === 0)
 540         return;
 541
 542       this.allAsyncEvents_.sort(function(x, y) {
 543         var d = x.event.ts - y.event.ts;
 544         if (d != 0)
 545           return d;
 546         return x.sequenceNumber - y.sequenceNumber;
 547       });
 548
 549       var asyncEventStatesByNameThenID = {};
 550
 551       var allAsyncEvents = this.allAsyncEvents_;
 552       for (var i = 0; i < allAsyncEvents.length; i++) {
 553         var asyncEventState = allAsyncEvents[i];
 554
 555         var event = asyncEventState.event;
 556         var name = event.name;
 557         if (name === undefined) {
 558           this.model_.importWarning({
 559             type: 'async_slice_parse_error',
 560             message: 'Async events (ph: S, T, p, or F) require a name ' +
 561                 ' parameter.'
 562           });
 563           continue;
 564         }
 565
 566         var id = event.id;
 567         if (id === undefined) {
 568           this.model_.importWarning({
 569             type: 'async_slice_parse_error',
 570             message: 'Async events (ph: S, T, p, or F) require an id parameter.'
 571           });
 572           continue;
 573         }
 574
 575         // TODO(simonjam): Add a synchronous tick on the appropriate thread.
 576
 577         if (event.ph === 'S') {
 578           if (asyncEventStatesByNameThenID[name] === undefined)
 579             asyncEventStatesByNameThenID[name] = {};
 580           if (asyncEventStatesByNameThenID[name][id]) {
 581             this.model_.importWarning({
 582               type: 'async_slice_parse_error',
 583               message: 'At ' + event.ts + ', a slice of the same id ' + id +
 584                   ' was alrady open.'
 585             });
 586             continue;
 587           }
 588           asyncEventStatesByNameThenID[name][id] = [];
 589           asyncEventStatesByNameThenID[name][id].push(asyncEventState);
 590         } else {
 591           if (asyncEventStatesByNameThenID[name] === undefined) {
 592             this.model_.importWarning({
 593               type: 'async_slice_parse_error',
 594               message: 'At ' + event.ts + ', no slice named ' + name +
 595                   ' was open.'
 596             });
 597             continue;
 598           }
 599           if (asyncEventStatesByNameThenID[name][id] === undefined) {
 600             this.model_.importWarning({
 601               type: 'async_slice_parse_error',
 602               message: 'At ' + event.ts + ', no slice named ' + name +
 603                   ' with id=' + id + ' was open.'
 604             });
 605             continue;
 606           }
 607           var events = asyncEventStatesByNameThenID[name][id];
 608           events.push(asyncEventState);
 609
 610           if (event.ph === 'F') {
 611             // Create a slice from start to end.
 612             var slice = new tracing.trace_model.AsyncSlice(
 613                 events[0].event.cat,
 614                 name,
 615                 tvcm.ui.getStringColorId(name),
 616                 events[0].event.ts / 1000);
 617
 618             slice.duration = (event.ts / 1000) - (events[0].event.ts / 1000);
 619
 620             slice.startThread = events[0].thread;
 621             slice.endThread = asyncEventState.thread;
 622             slice.id = id;
 623             slice.args = this.deepCopyIfNeeded_(events[0].event.args);
 624             slice.subSlices = [];
 625
 626             var stepType = events[1].event.ph;
 627             var isValid = true;
 628
 629             // Create subSlices for each step.
 630             for (var j = 1; j < events.length; ++j) {
 631               var subName = name;
 632               if (events[j].event.ph == 'T' || events[j].event.ph == 'p') {
 633                 isValid = this.assertStepTypeMatches_(stepType, events[j]);
 634                 if (!isValid)
 635                   break;
 636               }
 637
 638               var targetEvent;
 639               if (stepType == 'T') {
 640                 targetEvent = events[j - 1];
 641               } else {
 642                 targetEvent = events[j];
 643               }
 644
 645               var subName = events[0].event.name;
 646               if (targetEvent.event.ph == 'T' || targetEvent.event.ph == 'p')
 647                 subName = subName + ':' + targetEvent.event.args.step;
 648
 649               var subSlice = new tracing.trace_model.AsyncSlice(
 650                   events[0].event.cat,
 651                   subName,
 652                   tvcm.ui.getStringColorId(subName + j),
 653                   events[j - 1].event.ts / 1000);
 654
 655               subSlice.duration =
 656                   (events[j].event.ts / 1000) - (events[j - 1].event.ts / 1000);
 657
 658               subSlice.startThread = events[j - 1].thread;
 659               subSlice.endThread = events[j].thread;
 660               subSlice.id = id;
 661               subSlice.args = tvcm.concatenateObjects(events[0].event.args,
 662                                                       targetEvent.event.args);
 663
 664               slice.subSlices.push(subSlice);
 665
 666               if (events[j].event.ph == 'F' && stepType == 'T') {
 667                 // The args for the finish event go in the last subSlice.
 668                 var lastSlice = slice.subSlices[slice.subSlices.length - 1];
 669                 lastSlice.args = tvcm.concatenateObjects(lastSlice.args,
 670                                                          event.args);
 671               }
 672             }
 673
 674             if (isValid) {
 675               // Add |slice| to the start-thread's asyncSlices.
 676               slice.startThread.asyncSliceGroup.push(slice);
 677             }
 678
 679             delete asyncEventStatesByNameThenID[name][id];
 680           }
 681         }
 682       }
 683     },
 684
 685     assertStepTypeMatches_: function(stepType, event) {
 686       if (stepType != event.event.ph) {
 687         this.model_.importWarning({
 688           type: 'async_slice_parse_error',
 689           message: 'At ' + event.event.ts + ', a slice named ' +
 690               event.event.name + ' with id=' + event.event.id +
 691               ' had both begin and end steps, which is not allowed.'
 692         });
 693         return false;
 694       }
 695       return true;
 696     },
 697
 698     createFlowSlices_: function() {
 699       if (this.allFlowEvents_.length === 0)
 700         return;
 701
 702       this.allFlowEvents_.sort(function(x, y) {
 703         var d = x.event.ts - y.event.ts;
 704         if (d != 0)
 705           return d;
 706         return x.sequenceNumber - y.sequenceNumber;
 707       });
 708
 709       var flowIdToEvent = {};
 710       for (var i = 0; i < this.allFlowEvents_.length; ++i) {
 711         var data = this.allFlowEvents_[i];
 712         var event = data.event;
 713         var thread = data.thread;
 714
 715         if (event.name === undefined) {
 716           this.model_.importWarning({
 717             type: 'flow_slice_parse_error',
 718             message: 'Flow events (ph: s, t or f) require a name parameter.'
 719           });
 720           continue;
 721         }
 722
 723         if (event.id === undefined) {
 724           this.model_.importWarning({
 725             type: 'flow_slice_parse_error',
 726             message: 'Flow events (ph: s, t or f) require an id parameter.'
 727           });
 728           continue;
 729         }
 730
 731         var slice = new tracing.trace_model.FlowEvent(
 732             event.cat,
 733             event.id,
 734             event.name,
 735             tvcm.ui.getStringColorId(event.name),
 736             event.ts / 1000,
 737             this.deepCopyIfNeeded_(event.args));
 738         thread.sliceGroup.pushSlice(slice);
 739
 740         if (event.ph === 's') {
 741           if (flowIdToEvent[event.id] !== undefined) {
 742             this.model_.importWarning({
 743               type: 'flow_slice_start_error',
 744               message: 'event id ' + event.id + ' already seen when ' +
 745                   'encountering start of flow event.'});
 746           }
 747           flowIdToEvent[event.id] = slice;
 748
 749         } else if (event.ph === 't' || event.ph === 'f') {
 750           var flowPosition = flowIdToEvent[event.id];
 751           if (flowPosition === undefined) {
 752             this.model_.importWarning({
 753               type: 'flow_slice_ordering_error',
 754               message: 'Found flow phase ' + event.ph + ' for id: ' + event.id +
 755                   ' but no flow start found.'
 756             });
 757             continue;
 758           }
 759           this.model_.flowEvents.push([flowPosition, slice]);
 760
 761           if (flowPosition)
 762             flowPosition.nextFlowEvent = slice;
 763           if (slice)
 764             slice.previousFlowEvent = flowPosition;
 765
 766           if (event.ph === 'f') {
 767             flowIdToEvent[event.id] = undefined;
 768           } else {
 769             // Make this slice the next start event in this flow.
 770             flowIdToEvent[event.id] = slice;
 771           }
 772         }
 773       }
 774     },
 775
 776     /**
 777      * This function creates objects described via the N, D, and O phase
 778      * events.
 779      */
 780     createExplicitObjects_: function() {
 781       if (this.allObjectEvents_.length == 0)
 782         return;
 783
 784       function processEvent(objectEventState) {
 785         var event = objectEventState.event;
 786         var thread = objectEventState.thread;
 787         if (event.name === undefined) {
 788           this.model_.importWarning({
 789             type: 'object_parse_error',
 790             message: 'While processing ' + JSON.stringify(event) + ': ' +
 791                 'Object events require an name parameter.'
 792           });
 793         }
 794
 795         if (event.id === undefined) {
 796           this.model_.importWarning({
 797             type: 'object_parse_error',
 798             message: 'While processing ' + JSON.stringify(event) + ': ' +
 799                 'Object events require an id parameter.'
 800           });
 801         }
 802         var process = thread.parent;
 803         var ts = event.ts / 1000;
 804         var instance;
 805         if (event.ph == 'N') {
 806           try {
 807             instance = process.objects.idWasCreated(
 808                 event.id, event.cat, event.name, ts);
 809           } catch (e) {
 810             this.model_.importWarning({
 811               type: 'object_parse_error',
 812               message: 'While processing create of ' +
 813                   event.id + ' at ts=' + ts + ': ' + e
 814             });
 815             return;
 816           }
 817         } else if (event.ph == 'O') {
 818           if (event.args.snapshot === undefined) {
 819             this.model_.importWarning({
 820               type: 'object_parse_error',
 821               message: 'While processing ' + event.id + ' at ts=' + ts + ': ' +
 822                   'Snapshots must have args: {snapshot: ...}'
 823             });
 824             return;
 825           }
 826           var snapshot;
 827           try {
 828             var args = this.deepCopyIfNeeded_(event.args.snapshot);
 829             var cat;
 830             if (args.cat) {
 831               cat = args.cat;
 832               delete args.cat;
 833             } else {
 834               cat = event.cat;
 835             }
 836
 837             var baseTypename;
 838             if (args.base_type) {
 839               baseTypename = args.base_type;
 840               delete args.base_type;
 841             } else {
 842               baseTypename = undefined;
 843             }
 844             snapshot = process.objects.addSnapshot(
 845                 event.id, cat, event.name, ts,
 846                 args, baseTypename);
 847           } catch (e) {
 848             this.model_.importWarning({
 849               type: 'object_parse_error',
 850               message: 'While processing snapshot of ' +
 851                   event.id + ' at ts=' + ts + ': ' + e
 852             });
 853             return;
 854           }
 855           instance = snapshot.objectInstance;
 856         } else if (event.ph == 'D') {
 857           try {
 858             instance = process.objects.idWasDeleted(
 859                 event.id, event.cat, event.name, ts);
 860           } catch (e) {
 861             this.model_.importWarning({
 862               type: 'object_parse_error',
 863               message: 'While processing delete of ' +
 864                   event.id + ' at ts=' + ts + ': ' + e
 865             });
 866             return;
 867           }
 868         }
 869
 870         if (instance)
 871           instance.colorId = tvcm.ui.getStringColorId(instance.typeName);
 872       }
 873
 874       this.allObjectEvents_.sort(function(x, y) {
 875         var d = x.event.ts - y.event.ts;
 876         if (d != 0)
 877           return d;
 878         return x.sequenceNumber - y.sequenceNumber;
 879       });
 880
 881       var allObjectEvents = this.allObjectEvents_;
 882       for (var i = 0; i < allObjectEvents.length; i++) {
 883         var objectEventState = allObjectEvents[i];
 884         try {
 885           processEvent.call(this, objectEventState);
 886         } catch (e) {
 887           this.model_.importWarning({
 888             type: 'object_parse_error',
 889             message: e.message
 890           });
 891         }
 892       }
 893     },
 894
 895     createImplicitObjects_: function() {
 896       tvcm.iterItems(this.model_.processes, function(pid, process) {
 897         this.createImplicitObjectsForProcess_(process);
 898       }, this);
 899     },
 900
 901     // Here, we collect all the snapshots that internally contain a
 902     // Javascript-level object inside their args list that has an "id" field,
 903     // and turn that into a snapshot of the instance referred to by id.
 904     createImplicitObjectsForProcess_: function(process) {
 905
 906       function processField(referencingObject,
 907                             referencingObjectFieldName,
 908                             referencingObjectFieldValue,
 909                             containingSnapshot) {
 910         if (!referencingObjectFieldValue)
 911           return;
 912
 913         if (referencingObjectFieldValue instanceof
 914             tracing.trace_model.ObjectSnapshot)
 915           return null;
 916         if (referencingObjectFieldValue.id === undefined)
 917           return;
 918
 919         var implicitSnapshot = referencingObjectFieldValue;
 920
 921         var rawId = implicitSnapshot.id;
 922         var m = /(.+)\/(.+)/.exec(rawId);
 923         if (!m)
 924           throw new Error('Implicit snapshots must have names.');
 925         delete implicitSnapshot.id;
 926         var name = m[1];
 927         var id = m[2];
 928         var res;
 929
 930         var cat;
 931         if (implicitSnapshot.cat !== undefined)
 932           cat = implicitSnapshot.cat;
 933         else
 934           cat = containingSnapshot.objectInstance.category;
 935
 936         var baseTypename;
 937         if (implicitSnapshot.base_type)
 938           baseTypename = implicitSnapshot.base_type;
 939         else
 940           baseTypename = undefined;
 941
 942         try {
 943           res = process.objects.addSnapshot(
 944               id, cat,
 945               name, containingSnapshot.ts,
 946               implicitSnapshot, baseTypename);
 947         } catch (e) {
 948           this.model_.importWarning({
 949             type: 'object_snapshot_parse_error',
 950             message: 'While processing implicit snapshot of ' +
 951                 rawId + ' at ts=' + containingSnapshot.ts + ': ' + e
 952           });
 953           return;
 954         }
 955         res.objectInstance.hasImplicitSnapshots = true;
 956         res.containingSnapshot = containingSnapshot;
 957         referencingObject[referencingObjectFieldName] = res;
 958         if (!(res instanceof tracing.trace_model.ObjectSnapshot))
 959           throw new Error('Created object must be instanceof snapshot');
 960         return res.args;
 961       }
 962
 963       /**
 964        * Iterates over the fields in the object, calling func for every
 965        * field/value found.
 966        *
 967        * @return {object} If the function does not want the field's value to be
 968        * iterated, return null. If iteration of the field value is desired, then
 969        * return either undefined (if the field value did not change) or the new
 970        * field value if it was changed.
 971        */
 972       function iterObject(object, func, containingSnapshot, thisArg) {
 973         if (!(object instanceof Object))
 974           return;
 975
 976         if (object instanceof Array) {
 977           for (var i = 0; i < object.length; i++) {
 978             var res = func.call(thisArg, object, i, object[i],
 979                                 containingSnapshot);
 980             if (res === null)
 981               continue;
 982             if (res)
 983               iterObject(res, func, containingSnapshot, thisArg);
 984             else
 985               iterObject(object[i], func, containingSnapshot, thisArg);
 986           }
 987           return;
 988         }
 989
 990         for (var key in object) {
 991           var res = func.call(thisArg, object, key, object[key],
 992                               containingSnapshot);
 993           if (res === null)
 994             continue;
 995           if (res)
 996             iterObject(res, func, containingSnapshot, thisArg);
 997           else
 998             iterObject(object[key], func, containingSnapshot, thisArg);
 999         }
1000       }
1001
1002       // TODO(nduca): We may need to iterate the instances in sorted order by
1003       // creationTs.
1004       process.objects.iterObjectInstances(function(instance) {
1005         instance.snapshots.forEach(function(snapshot) {
1006           if (snapshot.args.id !== undefined)
1007             throw new Error('args cannot have an id field inside it');
1008           iterObject(snapshot.args, processField, snapshot, this);
1009         }, this);
1010       }, this);
1011     },
1012
1013     joinObjectRefs_: function() {
1014       tvcm.iterItems(this.model_.processes, function(pid, process) {
1015         this.joinObjectRefsForProcess_(process);
1016       }, this);
1017     },
1018
1019     joinObjectRefsForProcess_: function(process) {
1020       // Iterate the world, looking for id_refs
1021       var patchupsToApply = [];
1022       tvcm.iterItems(process.threads, function(tid, thread) {
1023         thread.asyncSliceGroup.slices.forEach(function(item) {
1024           this.searchItemForIDRefs_(
1025               patchupsToApply, process.objects, 'start', item);
1026         }, this);
1027         thread.sliceGroup.slices.forEach(function(item) {
1028           this.searchItemForIDRefs_(
1029               patchupsToApply, process.objects, 'start', item);
1030         }, this);
1031       }, this);
1032       process.objects.iterObjectInstances(function(instance) {
1033         instance.snapshots.forEach(function(item) {
1034           this.searchItemForIDRefs_(
1035               patchupsToApply, process.objects, 'ts', item);
1036         }, this);
1037       }, this);
1038
1039       // Change all the fields pointing at id_refs to their real values.
1040       patchupsToApply.forEach(function(patchup) {
1041         patchup.object[patchup.field] = patchup.value;
1042       });
1043     },
1044
1045     searchItemForIDRefs_: function(patchupsToApply, objectCollection,
1046                                    itemTimestampField, item) {
1047       if (!item.args)
1048         throw new Error('item is missing its args');
1049
1050       function handleField(object, fieldName, fieldValue) {
1051         if (fieldValue === undefined ||
1052             (!fieldValue.id_ref && !fieldValue.idRef))
1053           return;
1054
1055         var id = fieldValue.id_ref || fieldValue.idRef;
1056         var ts = item[itemTimestampField];
1057         var snapshot = objectCollection.getSnapshotAt(id, ts);
1058         if (!snapshot)
1059           return;
1060
1061         // We have to delay the actual change to the new value until after all
1062         // refs have been located. Otherwise, we could end up recursing in
1063         // ways we definitely didn't intend.
1064         patchupsToApply.push({object: object,
1065           field: fieldName,
1066           value: snapshot});
1067       }
1068       function iterObjectFieldsRecursively(object) {
1069         if (!(object instanceof Object))
1070           return;
1071
1072         if ((object instanceof tracing.trace_model.ObjectSnapshot) ||
1073             (object instanceof Float32Array) ||
1074             (object instanceof tvcm.Quad))
1075           return;
1076
1077         if (object instanceof Array) {
1078           for (var i = 0; i < object.length; i++) {
1079             handleField(object, i, object[i]);
1080             iterObjectFieldsRecursively(object[i]);
1081           }
1082           return;
1083         }
1084
1085         for (var key in object) {
1086           var value = object[key];
1087           handleField(object, key, value);
1088           iterObjectFieldsRecursively(value);
1089         }
1090       }
1091
1092       iterObjectFieldsRecursively(item.args);
1093     }
1094   };
1095
1096   tracing.TraceModel.registerImporter(TraceEventImporter);
1097
1098   return {
1099     TraceEventImporter: TraceEventImporter
1100   };
1101 });