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