src/base/test/trace_event_analyzer.cc

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