Home | History | Annotate | Download | only in test 
      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
    969