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#include "base/test/trace_event_analyzer.h"
6
7#include <algorithm>
8#include <math.h>
9#include <set>
10
11#include "base/json/json_reader.h"
12#include "base/memory/scoped_ptr.h"
13#include "base/values.h"
14
15namespace trace_analyzer {
16
17// TraceEvent
18
19TraceEvent::TraceEvent()
20    : thread(0, 0),
21      timestamp(0),
22      duration(0),
23      phase(TRACE_EVENT_PHASE_BEGIN),
24      other_event(NULL) {
25}
26
27TraceEvent::~TraceEvent() {
28}
29
30bool TraceEvent::SetFromJSON(const base::Value* event_value) {
31  if (event_value->GetType() != base::Value::TYPE_DICTIONARY) {
32    LOG(ERROR) << "Value must be TYPE_DICTIONARY";
33    return false;
34  }
35  const base::DictionaryValue* dictionary =
36      static_cast<const base::DictionaryValue*>(event_value);
37
38  std::string phase_str;
39  const base::DictionaryValue* args = NULL;
40
41  if (!dictionary->GetString("ph", &phase_str)) {
42    LOG(ERROR) << "ph is missing from TraceEvent JSON";
43    return false;
44  }
45
46  phase = *phase_str.data();
47
48  bool may_have_duration = (phase == TRACE_EVENT_PHASE_COMPLETE);
49  bool require_origin = (phase != TRACE_EVENT_PHASE_METADATA);
50  bool require_id = (phase == TRACE_EVENT_PHASE_ASYNC_BEGIN ||
51                     phase == TRACE_EVENT_PHASE_ASYNC_STEP_INTO ||
52                     phase == TRACE_EVENT_PHASE_ASYNC_STEP_PAST ||
53                     phase == TRACE_EVENT_PHASE_ASYNC_END);
54
55  if (require_origin && !dictionary->GetInteger("pid", &thread.process_id)) {
56    LOG(ERROR) << "pid is missing from TraceEvent JSON";
57    return false;
58  }
59  if (require_origin && !dictionary->GetInteger("tid", &thread.thread_id)) {
60    LOG(ERROR) << "tid is missing from TraceEvent JSON";
61    return false;
62  }
63  if (require_origin && !dictionary->GetDouble("ts", &timestamp)) {
64    LOG(ERROR) << "ts is missing from TraceEvent JSON";
65    return false;
66  }
67  if (may_have_duration) {
68    dictionary->GetDouble("dur", &duration);
69  }
70  if (!dictionary->GetString("cat", &category)) {
71    LOG(ERROR) << "cat is missing from TraceEvent JSON";
72    return false;
73  }
74  if (!dictionary->GetString("name", &name)) {
75    LOG(ERROR) << "name is missing from TraceEvent JSON";
76    return false;
77  }
78  if (!dictionary->GetDictionary("args", &args)) {
79    LOG(ERROR) << "args is missing from TraceEvent JSON";
80    return false;
81  }
82  if (require_id && !dictionary->GetString("id", &id)) {
83    LOG(ERROR) << "id is missing from ASYNC_BEGIN/ASYNC_END TraceEvent JSON";
84    return false;
85  }
86
87  // For each argument, copy the type and create a trace_analyzer::TraceValue.
88  for (base::DictionaryValue::Iterator it(*args); !it.IsAtEnd();
89       it.Advance()) {
90    std::string str;
91    bool boolean = false;
92    int int_num = 0;
93    double double_num = 0.0;
94    if (it.value().GetAsString(&str)) {
95      arg_strings[it.key()] = str;
96    } else if (it.value().GetAsInteger(&int_num)) {
97      arg_numbers[it.key()] = static_cast<double>(int_num);
98    } else if (it.value().GetAsBoolean(&boolean)) {
99      arg_numbers[it.key()] = static_cast<double>(boolean ? 1 : 0);
100    } else if (it.value().GetAsDouble(&double_num)) {
101      arg_numbers[it.key()] = double_num;
102    } else {
103      LOG(WARNING) << "Value type of argument is not supported: " <<
104          static_cast<int>(it.value().GetType());
105      continue;  // Skip non-supported arguments.
106    }
107  }
108
109  return true;
110}
111
112double TraceEvent::GetAbsTimeToOtherEvent() const {
113  return fabs(other_event->timestamp - timestamp);
114}
115
116bool TraceEvent::GetArgAsString(const std::string& name,
117                                std::string* arg) const {
118  std::map<std::string, std::string>::const_iterator i = arg_strings.find(name);
119  if (i != arg_strings.end()) {
120    *arg = i->second;
121    return true;
122  }
123  return false;
124}
125
126bool TraceEvent::GetArgAsNumber(const std::string& name,
127                                double* arg) const {
128  std::map<std::string, double>::const_iterator i = arg_numbers.find(name);
129  if (i != arg_numbers.end()) {
130    *arg = i->second;
131    return true;
132  }
133  return false;
134}
135
136bool TraceEvent::HasStringArg(const std::string& name) const {
137  return (arg_strings.find(name) != arg_strings.end());
138}
139
140bool TraceEvent::HasNumberArg(const std::string& name) const {
141  return (arg_numbers.find(name) != arg_numbers.end());
142}
143
144std::string TraceEvent::GetKnownArgAsString(const std::string& name) const {
145  std::string arg_string;
146  bool result = GetArgAsString(name, &arg_string);
147  DCHECK(result);
148  return arg_string;
149}
150
151double TraceEvent::GetKnownArgAsDouble(const std::string& name) const {
152  double arg_double = 0;
153  bool result = GetArgAsNumber(name, &arg_double);
154  DCHECK(result);
155  return arg_double;
156}
157
158int TraceEvent::GetKnownArgAsInt(const std::string& name) const {
159  double arg_double = 0;
160  bool result = GetArgAsNumber(name, &arg_double);
161  DCHECK(result);
162  return static_cast<int>(arg_double);
163}
164
165bool TraceEvent::GetKnownArgAsBool(const std::string& name) const {
166  double arg_double = 0;
167  bool result = GetArgAsNumber(name, &arg_double);
168  DCHECK(result);
169  return (arg_double != 0.0);
170}
171
172// QueryNode
173
174QueryNode::QueryNode(const Query& query) : query_(query) {
175}
176
177QueryNode::~QueryNode() {
178}
179
180// Query
181
182Query::Query(TraceEventMember member)
183    : type_(QUERY_EVENT_MEMBER),
184      operator_(OP_INVALID),
185      member_(member),
186      number_(0),
187      is_pattern_(false) {
188}
189
190Query::Query(TraceEventMember member, const std::string& arg_name)
191    : type_(QUERY_EVENT_MEMBER),
192      operator_(OP_INVALID),
193      member_(member),
194      number_(0),
195      string_(arg_name),
196      is_pattern_(false) {
197}
198
199Query::Query(const Query& query)
200    : type_(query.type_),
201      operator_(query.operator_),
202      left_(query.left_),
203      right_(query.right_),
204      member_(query.member_),
205      number_(query.number_),
206      string_(query.string_),
207      is_pattern_(query.is_pattern_) {
208}
209
210Query::~Query() {
211}
212
213Query Query::String(const std::string& str) {
214  return Query(str);
215}
216
217Query Query::Double(double num) {
218  return Query(num);
219}
220
221Query Query::Int(int32 num) {
222  return Query(static_cast<double>(num));
223}
224
225Query Query::Uint(uint32 num) {
226  return Query(static_cast<double>(num));
227}
228
229Query Query::Bool(bool boolean) {
230  return Query(boolean ? 1.0 : 0.0);
231}
232
233Query Query::Phase(char phase) {
234  return Query(static_cast<double>(phase));
235}
236
237Query Query::Pattern(const std::string& pattern) {
238  Query query(pattern);
239  query.is_pattern_ = true;
240  return query;
241}
242
243bool Query::Evaluate(const TraceEvent& event) const {
244  // First check for values that can convert to bool.
245
246  // double is true if != 0:
247  double bool_value = 0.0;
248  bool is_bool = GetAsDouble(event, &bool_value);
249  if (is_bool)
250    return (bool_value != 0.0);
251
252  // string is true if it is non-empty:
253  std::string str_value;
254  bool is_str = GetAsString(event, &str_value);
255  if (is_str)
256    return !str_value.empty();
257
258  DCHECK_EQ(QUERY_BOOLEAN_OPERATOR, type_)
259      << "Invalid query: missing boolean expression";
260  DCHECK(left_.get());
261  DCHECK(right_.get() || is_unary_operator());
262
263  if (is_comparison_operator()) {
264    DCHECK(left().is_value() && right().is_value())
265        << "Invalid query: comparison operator used between event member and "
266           "value.";
267    bool compare_result = false;
268    if (CompareAsDouble(event, &compare_result))
269      return compare_result;
270    if (CompareAsString(event, &compare_result))
271      return compare_result;
272    return false;
273  }
274  // It's a logical operator.
275  switch (operator_) {
276    case OP_AND:
277      return left().Evaluate(event) && right().Evaluate(event);
278    case OP_OR:
279      return left().Evaluate(event) || right().Evaluate(event);
280    case OP_NOT:
281      return !left().Evaluate(event);
282    default:
283      NOTREACHED();
284      return false;
285  }
286}
287
288bool Query::CompareAsDouble(const TraceEvent& event, bool* result) const {
289  double lhs, rhs;
290  if (!left().GetAsDouble(event, &lhs) || !right().GetAsDouble(event, &rhs))
291    return false;
292  switch (operator_) {
293    case OP_EQ:
294      *result = (lhs == rhs);
295      return true;
296    case OP_NE:
297      *result = (lhs != rhs);
298      return true;
299    case OP_LT:
300      *result = (lhs < rhs);
301      return true;
302    case OP_LE:
303      *result = (lhs <= rhs);
304      return true;
305    case OP_GT:
306      *result = (lhs > rhs);
307      return true;
308    case OP_GE:
309      *result = (lhs >= rhs);
310      return true;
311    default:
312      NOTREACHED();
313      return false;
314  }
315}
316
317bool Query::CompareAsString(const TraceEvent& event, bool* result) const {
318  std::string lhs, rhs;
319  if (!left().GetAsString(event, &lhs) || !right().GetAsString(event, &rhs))
320    return false;
321  switch (operator_) {
322    case OP_EQ:
323      if (right().is_pattern_)
324        *result = MatchPattern(lhs, rhs);
325      else if (left().is_pattern_)
326        *result = MatchPattern(rhs, lhs);
327      else
328        *result = (lhs == rhs);
329      return true;
330    case OP_NE:
331      if (right().is_pattern_)
332        *result = !MatchPattern(lhs, rhs);
333      else if (left().is_pattern_)
334        *result = !MatchPattern(rhs, lhs);
335      else
336        *result = (lhs != rhs);
337      return true;
338    case OP_LT:
339      *result = (lhs < rhs);
340      return true;
341    case OP_LE:
342      *result = (lhs <= rhs);
343      return true;
344    case OP_GT:
345      *result = (lhs > rhs);
346      return true;
347    case OP_GE:
348      *result = (lhs >= rhs);
349      return true;
350    default:
351      NOTREACHED();
352      return false;
353  }
354}
355
356bool Query::EvaluateArithmeticOperator(const TraceEvent& event,
357                                       double* num) const {
358  DCHECK_EQ(QUERY_ARITHMETIC_OPERATOR, type_);
359  DCHECK(left_.get());
360  DCHECK(right_.get() || is_unary_operator());
361
362  double lhs = 0, rhs = 0;
363  if (!left().GetAsDouble(event, &lhs))
364    return false;
365  if (!is_unary_operator() && !right().GetAsDouble(event, &rhs))
366    return false;
367
368  switch (operator_) {
369    case OP_ADD:
370      *num = lhs + rhs;
371      return true;
372    case OP_SUB:
373      *num = lhs - rhs;
374      return true;
375    case OP_MUL:
376      *num = lhs * rhs;
377      return true;
378    case OP_DIV:
379      *num = lhs / rhs;
380      return true;
381    case OP_MOD:
382      *num = static_cast<double>(static_cast<int64>(lhs) %
383                                 static_cast<int64>(rhs));
384      return true;
385    case OP_NEGATE:
386      *num = -lhs;
387      return true;
388    default:
389      NOTREACHED();
390      return false;
391  }
392}
393
394bool Query::GetAsDouble(const TraceEvent& event, double* num) const {
395  switch (type_) {
396    case QUERY_ARITHMETIC_OPERATOR:
397      return EvaluateArithmeticOperator(event, num);
398    case QUERY_EVENT_MEMBER:
399      return GetMemberValueAsDouble(event, num);
400    case QUERY_NUMBER:
401      *num = number_;
402      return true;
403    default:
404      return false;
405  }
406}
407
408bool Query::GetAsString(const TraceEvent& event, std::string* str) const {
409  switch (type_) {
410    case QUERY_EVENT_MEMBER:
411      return GetMemberValueAsString(event, str);
412    case QUERY_STRING:
413      *str = string_;
414      return true;
415    default:
416      return false;
417  }
418}
419
420bool Query::GetMemberValueAsDouble(const TraceEvent& event,
421                                   double* num) const {
422  DCHECK_EQ(QUERY_EVENT_MEMBER, type_);
423
424  // This could be a request for a member of |event| or a member of |event|'s
425  // associated event. Store the target event in the_event:
426  const TraceEvent* the_event = (member_ < OTHER_PID) ?
427      &event : event.other_event;
428
429  // Request for member of associated event, but there is no associated event.
430  if (!the_event)
431    return false;
432
433  switch (member_) {
434    case EVENT_PID:
435    case OTHER_PID:
436      *num = static_cast<double>(the_event->thread.process_id);
437      return true;
438    case EVENT_TID:
439    case OTHER_TID:
440      *num = static_cast<double>(the_event->thread.thread_id);
441      return true;
442    case EVENT_TIME:
443    case OTHER_TIME:
444      *num = the_event->timestamp;
445      return true;
446    case EVENT_DURATION:
447      if (!the_event->has_other_event())
448        return false;
449      *num = the_event->GetAbsTimeToOtherEvent();
450      return true;
451    case EVENT_COMPLETE_DURATION:
452      if (the_event->phase != TRACE_EVENT_PHASE_COMPLETE)
453        return false;
454      *num = the_event->duration;
455      return true;
456    case EVENT_PHASE:
457    case OTHER_PHASE:
458      *num = static_cast<double>(the_event->phase);
459      return true;
460    case EVENT_HAS_STRING_ARG:
461    case OTHER_HAS_STRING_ARG:
462      *num = (the_event->HasStringArg(string_) ? 1.0 : 0.0);
463      return true;
464    case EVENT_HAS_NUMBER_ARG:
465    case OTHER_HAS_NUMBER_ARG:
466      *num = (the_event->HasNumberArg(string_) ? 1.0 : 0.0);
467      return true;
468    case EVENT_ARG:
469    case OTHER_ARG: {
470      // Search for the argument name and return its value if found.
471      std::map<std::string, double>::const_iterator num_i =
472          the_event->arg_numbers.find(string_);
473      if (num_i == the_event->arg_numbers.end())
474        return false;
475      *num = num_i->second;
476      return true;
477    }
478    case EVENT_HAS_OTHER:
479      // return 1.0 (true) if the other event exists
480      *num = event.other_event ? 1.0 : 0.0;
481      return true;
482    default:
483      return false;
484  }
485}
486
487bool Query::GetMemberValueAsString(const TraceEvent& event,
488                                   std::string* str) const {
489  DCHECK_EQ(QUERY_EVENT_MEMBER, type_);
490
491  // This could be a request for a member of |event| or a member of |event|'s
492  // associated event. Store the target event in the_event:
493  const TraceEvent* the_event = (member_ < OTHER_PID) ?
494      &event : event.other_event;
495
496  // Request for member of associated event, but there is no associated event.
497  if (!the_event)
498    return false;
499
500  switch (member_) {
501    case EVENT_CATEGORY:
502    case OTHER_CATEGORY:
503      *str = the_event->category;
504      return true;
505    case EVENT_NAME:
506    case OTHER_NAME:
507      *str = the_event->name;
508      return true;
509    case EVENT_ID:
510    case OTHER_ID:
511      *str = the_event->id;
512      return true;
513    case EVENT_ARG:
514    case OTHER_ARG: {
515      // Search for the argument name and return its value if found.
516      std::map<std::string, std::string>::const_iterator str_i =
517          the_event->arg_strings.find(string_);
518      if (str_i == the_event->arg_strings.end())
519        return false;
520      *str = str_i->second;
521      return true;
522    }
523    default:
524      return false;
525  }
526}
527
528Query::Query(const std::string& str)
529    : type_(QUERY_STRING),
530      operator_(OP_INVALID),
531      member_(EVENT_INVALID),
532      number_(0),
533      string_(str),
534      is_pattern_(false) {
535}
536
537Query::Query(double num)
538    : type_(QUERY_NUMBER),
539      operator_(OP_INVALID),
540      member_(EVENT_INVALID),
541      number_(num),
542      is_pattern_(false) {
543}
544const Query& Query::left() const {
545  return left_->query();
546}
547
548const Query& Query::right() const {
549  return right_->query();
550}
551
552Query Query::operator==(const Query& rhs) const {
553  return Query(*this, rhs, OP_EQ);
554}
555
556Query Query::operator!=(const Query& rhs) const {
557  return Query(*this, rhs, OP_NE);
558}
559
560Query Query::operator<(const Query& rhs) const {
561  return Query(*this, rhs, OP_LT);
562}
563
564Query Query::operator<=(const Query& rhs) const {
565  return Query(*this, rhs, OP_LE);
566}
567
568Query Query::operator>(const Query& rhs) const {
569  return Query(*this, rhs, OP_GT);
570}
571
572Query Query::operator>=(const Query& rhs) const {
573  return Query(*this, rhs, OP_GE);
574}
575
576Query Query::operator&&(const Query& rhs) const {
577  return Query(*this, rhs, OP_AND);
578}
579
580Query Query::operator||(const Query& rhs) const {
581  return Query(*this, rhs, OP_OR);
582}
583
584Query Query::operator!() const {
585  return Query(*this, OP_NOT);
586}
587
588Query Query::operator+(const Query& rhs) const {
589  return Query(*this, rhs, OP_ADD);
590}
591
592Query Query::operator-(const Query& rhs) const {
593  return Query(*this, rhs, OP_SUB);
594}
595
596Query Query::operator*(const Query& rhs) const {
597  return Query(*this, rhs, OP_MUL);
598}
599
600Query Query::operator/(const Query& rhs) const {
601  return Query(*this, rhs, OP_DIV);
602}
603
604Query Query::operator%(const Query& rhs) const {
605  return Query(*this, rhs, OP_MOD);
606}
607
608Query Query::operator-() const {
609  return Query(*this, OP_NEGATE);
610}
611
612
613Query::Query(const Query& left, const Query& right, Operator binary_op)
614    : operator_(binary_op),
615      left_(new QueryNode(left)),
616      right_(new QueryNode(right)),
617      member_(EVENT_INVALID),
618      number_(0) {
619  type_ = (binary_op < OP_ADD ?
620           QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
621}
622
623Query::Query(const Query& left, Operator unary_op)
624    : operator_(unary_op),
625      left_(new QueryNode(left)),
626      member_(EVENT_INVALID),
627      number_(0) {
628  type_ = (unary_op < OP_ADD ?
629           QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
630}
631
632namespace {
633
634// Search |events| for |query| and add matches to |output|.
635size_t FindMatchingEvents(const std::vector<TraceEvent>& events,
636                          const Query& query,
637                          TraceEventVector* output,
638                          bool ignore_metadata_events) {
639  for (size_t i = 0; i < events.size(); ++i) {
640    if (ignore_metadata_events && events[i].phase == TRACE_EVENT_PHASE_METADATA)
641      continue;
642    if (query.Evaluate(events[i]))
643      output->push_back(&events[i]);
644  }
645  return output->size();
646}
647
648bool ParseEventsFromJson(const std::string& json,
649                         std::vector<TraceEvent>* output) {
650  scoped_ptr<base::Value> root;
651  root.reset(base::JSONReader::Read(json));
652
653  base::ListValue* root_list = NULL;
654  if (!root.get() || !root->GetAsList(&root_list))
655    return false;
656
657  for (size_t i = 0; i < root_list->GetSize(); ++i) {
658    base::Value* item = NULL;
659    if (root_list->Get(i, &item)) {
660      TraceEvent event;
661      if (event.SetFromJSON(item))
662        output->push_back(event);
663      else
664        return false;
665    }
666  }
667
668  return true;
669}
670
671}  // namespace
672
673// TraceAnalyzer
674
675TraceAnalyzer::TraceAnalyzer()
676    : ignore_metadata_events_(false),
677      allow_assocation_changes_(true) {}
678
679TraceAnalyzer::~TraceAnalyzer() {
680}
681
682// static
683TraceAnalyzer* TraceAnalyzer::Create(const std::string& json_events) {
684  scoped_ptr<TraceAnalyzer> analyzer(new TraceAnalyzer());
685  if (analyzer->SetEvents(json_events))
686    return analyzer.release();
687  return NULL;
688}
689
690bool TraceAnalyzer::SetEvents(const std::string& json_events) {
691  raw_events_.clear();
692  if (!ParseEventsFromJson(json_events, &raw_events_))
693    return false;
694  std::stable_sort(raw_events_.begin(), raw_events_.end());
695  ParseMetadata();
696  return true;
697}
698
699void TraceAnalyzer::AssociateBeginEndEvents() {
700  using trace_analyzer::Query;
701
702  Query begin(Query::EventPhaseIs(TRACE_EVENT_PHASE_BEGIN));
703  Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_END));
704  Query match(Query::EventName() == Query::OtherName() &&
705              Query::EventCategory() == Query::OtherCategory() &&
706              Query::EventTid() == Query::OtherTid() &&
707              Query::EventPid() == Query::OtherPid());
708
709  AssociateEvents(begin, end, match);
710}
711
712void TraceAnalyzer::AssociateAsyncBeginEndEvents() {
713  using trace_analyzer::Query;
714
715  Query begin(
716      Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_BEGIN) ||
717      Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_INTO) ||
718      Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_PAST));
719  Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_END) ||
720            Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_INTO) ||
721            Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_PAST));
722  Query match(Query::EventName() == Query::OtherName() &&
723              Query::EventCategory() == Query::OtherCategory() &&
724              Query::EventId() == Query::OtherId());
725
726  AssociateEvents(begin, end, match);
727}
728
729void TraceAnalyzer::AssociateEvents(const Query& first,
730                                    const Query& second,
731                                    const Query& match) {
732  DCHECK(allow_assocation_changes_)
733      << "AssociateEvents not allowed after FindEvents";
734
735  // Search for matching begin/end event pairs. When a matching end is found,
736  // it is associated with the begin event.
737  std::vector<TraceEvent*> begin_stack;
738  for (size_t event_index = 0; event_index < raw_events_.size();
739       ++event_index) {
740
741    TraceEvent& this_event = raw_events_[event_index];
742
743    if (second.Evaluate(this_event)) {
744      // Search stack for matching begin, starting from end.
745      for (int stack_index = static_cast<int>(begin_stack.size()) - 1;
746           stack_index >= 0; --stack_index) {
747        TraceEvent& begin_event = *begin_stack[stack_index];
748
749        // Temporarily set other to test against the match query.
750        const TraceEvent* other_backup = begin_event.other_event;
751        begin_event.other_event = &this_event;
752        if (match.Evaluate(begin_event)) {
753          // Found a matching begin/end pair.
754          // Erase the matching begin event index from the stack.
755          begin_stack.erase(begin_stack.begin() + stack_index);
756          break;
757        }
758
759        // Not a match, restore original other and continue.
760        begin_event.other_event = other_backup;
761      }
762    }
763    // Even if this_event is a |second| event that has matched an earlier
764    // |first| event, it can still also be a |first| event and be associated
765    // with a later |second| event.
766    if (first.Evaluate(this_event)) {
767      begin_stack.push_back(&this_event);
768    }
769  }
770}
771
772void TraceAnalyzer::MergeAssociatedEventArgs() {
773  for (size_t i = 0; i < raw_events_.size(); ++i) {
774    // Merge all associated events with the first event.
775    const TraceEvent* other = raw_events_[i].other_event;
776    // Avoid looping by keeping set of encountered TraceEvents.
777    std::set<const TraceEvent*> encounters;
778    encounters.insert(&raw_events_[i]);
779    while (other && encounters.find(other) == encounters.end()) {
780      encounters.insert(other);
781      raw_events_[i].arg_numbers.insert(
782          other->arg_numbers.begin(),
783          other->arg_numbers.end());
784      raw_events_[i].arg_strings.insert(
785          other->arg_strings.begin(),
786          other->arg_strings.end());
787      other = other->other_event;
788    }
789  }
790}
791
792size_t TraceAnalyzer::FindEvents(const Query& query, TraceEventVector* output) {
793  allow_assocation_changes_ = false;
794  output->clear();
795  return FindMatchingEvents(
796      raw_events_, query, output, ignore_metadata_events_);
797}
798
799const TraceEvent* TraceAnalyzer::FindFirstOf(const Query& query) {
800  TraceEventVector output;
801  if (FindEvents(query, &output) > 0)
802    return output.front();
803  return NULL;
804}
805
806const TraceEvent* TraceAnalyzer::FindLastOf(const Query& query) {
807  TraceEventVector output;
808  if (FindEvents(query, &output) > 0)
809    return output.back();
810  return NULL;
811}
812
813const std::string& TraceAnalyzer::GetThreadName(
814    const TraceEvent::ProcessThreadID& thread) {
815  // If thread is not found, just add and return empty string.
816  return thread_names_[thread];
817}
818
819void TraceAnalyzer::ParseMetadata() {
820  for (size_t i = 0; i < raw_events_.size(); ++i) {
821    TraceEvent& this_event = raw_events_[i];
822    // Check for thread name metadata.
823    if (this_event.phase != TRACE_EVENT_PHASE_METADATA ||
824        this_event.name != "thread_name")
825      continue;
826    std::map<std::string, std::string>::const_iterator string_it =
827        this_event.arg_strings.find("name");
828    if (string_it != this_event.arg_strings.end())
829      thread_names_[this_event.thread] = string_it->second;
830  }
831}
832
833// TraceEventVector utility functions.
834
835bool GetRateStats(const TraceEventVector& events,
836                  RateStats* stats,
837                  const RateStatsOptions* options) {
838  DCHECK(stats);
839  // Need at least 3 events to calculate rate stats.
840  const size_t kMinEvents = 3;
841  if (events.size() < kMinEvents) {
842    LOG(ERROR) << "Not enough events: " << events.size();
843    return false;
844  }
845
846  std::vector<double> deltas;
847  size_t num_deltas = events.size() - 1;
848  for (size_t i = 0; i < num_deltas; ++i) {
849    double delta = events.at(i + 1)->timestamp - events.at(i)->timestamp;
850    if (delta < 0.0) {
851      LOG(ERROR) << "Events are out of order";
852      return false;
853    }
854    deltas.push_back(delta);
855  }
856
857  std::sort(deltas.begin(), deltas.end());
858
859  if (options) {
860    if (options->trim_min + options->trim_max > events.size() - kMinEvents) {
861      LOG(ERROR) << "Attempt to trim too many events";
862      return false;
863    }
864    deltas.erase(deltas.begin(), deltas.begin() + options->trim_min);
865    deltas.erase(deltas.end() - options->trim_max, deltas.end());
866  }
867
868  num_deltas = deltas.size();
869  double delta_sum = 0.0;
870  for (size_t i = 0; i < num_deltas; ++i)
871    delta_sum += deltas[i];
872
873  stats->min_us = *std::min_element(deltas.begin(), deltas.end());
874  stats->max_us = *std::max_element(deltas.begin(), deltas.end());
875  stats->mean_us = delta_sum / static_cast<double>(num_deltas);
876
877  double sum_mean_offsets_squared = 0.0;
878  for (size_t i = 0; i < num_deltas; ++i) {
879    double offset = fabs(deltas[i] - stats->mean_us);
880    sum_mean_offsets_squared += offset * offset;
881  }
882  stats->standard_deviation_us =
883      sqrt(sum_mean_offsets_squared / static_cast<double>(num_deltas - 1));
884
885  return true;
886}
887
888bool FindFirstOf(const TraceEventVector& events,
889                 const Query& query,
890                 size_t position,
891                 size_t* return_index) {
892  DCHECK(return_index);
893  for (size_t i = position; i < events.size(); ++i) {
894    if (query.Evaluate(*events[i])) {
895      *return_index = i;
896      return true;
897    }
898  }
899  return false;
900}
901
902bool FindLastOf(const TraceEventVector& events,
903                const Query& query,
904                size_t position,
905                size_t* return_index) {
906  DCHECK(return_index);
907  for (size_t i = std::min(position + 1, events.size()); i != 0; --i) {
908    if (query.Evaluate(*events[i - 1])) {
909      *return_index = i - 1;
910      return true;
911    }
912  }
913  return false;
914}
915
916bool FindClosest(const TraceEventVector& events,
917                 const Query& query,
918                 size_t position,
919                 size_t* return_closest,
920                 size_t* return_second_closest) {
921  DCHECK(return_closest);
922  if (events.empty() || position >= events.size())
923    return false;
924  size_t closest = events.size();
925  size_t second_closest = events.size();
926  for (size_t i = 0; i < events.size(); ++i) {
927    if (!query.Evaluate(*events.at(i)))
928      continue;
929    if (closest == events.size()) {
930      closest = i;
931      continue;
932    }
933    if (fabs(events.at(i)->timestamp - events.at(position)->timestamp) <
934        fabs(events.at(closest)->timestamp - events.at(position)->timestamp)) {
935      second_closest = closest;
936      closest = i;
937    } else if (second_closest == events.size()) {
938      second_closest = i;
939    }
940  }
941
942  if (closest < events.size() &&
943      (!return_second_closest || second_closest < events.size())) {
944    *return_closest = closest;
945    if (return_second_closest)
946      *return_second_closest = second_closest;
947    return true;
948  }
949
950  return false;
951}
952
953size_t CountMatches(const TraceEventVector& events,
954                    const Query& query,
955                    size_t begin_position,
956                    size_t end_position) {
957  if (begin_position >= events.size())
958    return 0u;
959  end_position = (end_position < events.size()) ? end_position : events.size();
960  size_t count = 0u;
961  for (size_t i = begin_position; i < end_position; ++i) {
962    if (query.Evaluate(*events.at(i)))
963      ++count;
964  }
965  return count;
966}
967
968}  // namespace trace_analyzer
969