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   bool result = GetArgAsString(name, &arg_string);
 147   DCHECK(result);
 148   return arg_string;
 149 }
 150
 151 double 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
 158 int 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
 165 bool 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
 174 QueryNode::QueryNode(const Query& query) : query_(query) {
 175 }
 176
 177 QueryNode::~QueryNode() {
 178 }
 179
 180 // Query
 181
 182 Query::Query(TraceEventMember member)
 183     : type_(QUERY_EVENT_MEMBER),
 184       operator_(OP_INVALID),
 185       member_(member),
 186       number_(0),
 187       is_pattern_(false) {
 188 }
 189
 190 Query::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
 199 Query::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
 210 Query::~Query() {
 211 }
 212
 213 Query Query::String(const std::string& str) {
 214   return Query(str);
 215 }
 216
 217 Query Query::Double(double num) {
 218   return Query(num);
 219 }
 220
 221 Query Query::Int(int32 num) {
 222   return Query(static_cast<double>(num));
 223 }
 224
 225 Query Query::Uint(uint32 num) {
 226   return Query(static_cast<double>(num));
 227 }
 228
 229 Query Query::Bool(bool boolean) {
 230   return Query(boolean ? 1.0 : 0.0);
 231 }
 232
 233 Query Query::Phase(char phase) {
 234   return Query(static_cast<double>(phase));
 235 }
 236
 237 Query Query::Pattern(const std::string& pattern) {
 238   Query query(pattern);
 239   query.is_pattern_ = true;
 240   return query;
 241 }
 242
 243 bool 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
 288 bool 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
 317 bool 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
 356 bool 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
 394 bool 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
 408 bool 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
 420 bool 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
 487 bool 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
 528 Query::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
 537 Query::Query(double num)
 538     : type_(QUERY_NUMBER),
 539       operator_(OP_INVALID),
 540       member_(EVENT_INVALID),
 541       number_(num),
 542       is_pattern_(false) {
 543 }
 544 const Query& Query::left() const {
 545   return left_->query();
 546 }
 547
 548 const Query& Query::right() const {
 549   return right_->query();
 550 }
 551
 552 Query Query::operator==(const Query& rhs) const {
 553   return Query(*this, rhs, OP_EQ);
 554 }
 555
 556 Query Query::operator!=(const Query& rhs) const {
 557   return Query(*this, rhs, OP_NE);
 558 }
 559
 560 Query Query::operator<(const Query& rhs) const {
 561   return Query(*this, rhs, OP_LT);
 562 }
 563
 564 Query Query::operator<=(const Query& rhs) const {
 565   return Query(*this, rhs, OP_LE);
 566 }
 567
 568 Query Query::operator>(const Query& rhs) const {
 569   return Query(*this, rhs, OP_GT);
 570 }
 571
 572 Query Query::operator>=(const Query& rhs) const {
 573   return Query(*this, rhs, OP_GE);
 574 }
 575
 576 Query Query::operator&&(const Query& rhs) const {
 577   return Query(*this, rhs, OP_AND);
 578 }
 579
 580 Query Query::operator||(const Query& rhs) const {
 581   return Query(*this, rhs, OP_OR);
 582 }
 583
 584 Query Query::operator!() const {
 585   return Query(*this, OP_NOT);
 586 }
 587
 588 Query Query::operator+(const Query& rhs) const {
 589   return Query(*this, rhs, OP_ADD);
 590 }
 591
 592 Query Query::operator-(const Query& rhs) const {
 593   return Query(*this, rhs, OP_SUB);
 594 }
 595
 596 Query Query::operator*(const Query& rhs) const {
 597   return Query(*this, rhs, OP_MUL);
 598 }
 599
 600 Query Query::operator/(const Query& rhs) const {
 601   return Query(*this, rhs, OP_DIV);
 602 }
 603
 604 Query Query::operator%(const Query& rhs) const {
 605   return Query(*this, rhs, OP_MOD);
 606 }
 607
 608 Query Query::operator-() const {
 609   return Query(*this, OP_NEGATE);
 610 }
 611
 612
 613 Query::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
 623 Query::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
 632 namespace {
 633
 634 // Search |events| for |query| and add matches to |output|.
 635 size_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
 648 bool 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
 675 TraceAnalyzer::TraceAnalyzer()
 676     : ignore_metadata_events_(false),
 677       allow_assocation_changes_(true) {}
 678
 679 TraceAnalyzer::~TraceAnalyzer() {
 680 }
 681
 682 // static
 683 TraceAnalyzer* 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
 690 bool 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
 699 void 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
 712 void 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
 729 void 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
 772 void 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
 792 size_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
 799 const TraceEvent* TraceAnalyzer::FindFirstOf(const Query& query) {
 800   TraceEventVector output;
 801   if (FindEvents(query, &output) > 0)
 802     return output.front();
 803   return NULL;
 804 }
 805
 806 const TraceEvent* TraceAnalyzer::FindLastOf(const Query& query) {
 807   TraceEventVector output;
 808   if (FindEvents(query, &output) > 0)
 809     return output.back();
 810   return NULL;
 811 }
 812
 813 const 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
 819 void 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
 835 bool 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
 888 bool 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
 902 bool 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
 916 bool 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
 953 size_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