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 <math.h>
      8 
      9 #include <algorithm>
     10 #include <set>
     11 
     12 #include "base/json/json_reader.h"
     13 #include "base/memory/scoped_ptr.h"
     14 #include "base/strings/pattern.h"
     15 #include "base/values.h"
     16 
     17 namespace trace_analyzer {
     18 
     19 // TraceEvent
     20 
     21 TraceEvent::TraceEvent()
     22     : thread(0, 0),
     23       timestamp(0),
     24       duration(0),
     25       phase(TRACE_EVENT_PHASE_BEGIN),
     26       other_event(NULL) {
     27 }
     28 
     29 TraceEvent::~TraceEvent() {
     30 }
     31 
     32 bool TraceEvent::SetFromJSON(const base::Value* event_value) {
     33   if (event_value->GetType() != base::Value::TYPE_DICTIONARY) {
     34     LOG(ERROR) << "Value must be TYPE_DICTIONARY";
     35     return false;
     36   }
     37   const base::DictionaryValue* dictionary =
     38       static_cast<const base::DictionaryValue*>(event_value);
     39 
     40   std::string phase_str;
     41   const base::DictionaryValue* args = NULL;
     42 
     43   if (!dictionary->GetString("ph", &phase_str)) {
     44     LOG(ERROR) << "ph is missing from TraceEvent JSON";
     45     return false;
     46   }
     47 
     48   phase = *phase_str.data();
     49 
     50   bool may_have_duration = (phase == TRACE_EVENT_PHASE_COMPLETE);
     51   bool require_origin = (phase != TRACE_EVENT_PHASE_METADATA);
     52   bool require_id = (phase == TRACE_EVENT_PHASE_ASYNC_BEGIN ||
     53                      phase == TRACE_EVENT_PHASE_ASYNC_STEP_INTO ||
     54                      phase == TRACE_EVENT_PHASE_ASYNC_STEP_PAST ||
     55                      phase == TRACE_EVENT_PHASE_ASYNC_END);
     56 
     57   if (require_origin && !dictionary->GetInteger("pid", &thread.process_id)) {
     58     LOG(ERROR) << "pid is missing from TraceEvent JSON";
     59     return false;
     60   }
     61   if (require_origin && !dictionary->GetInteger("tid", &thread.thread_id)) {
     62     LOG(ERROR) << "tid is missing from TraceEvent JSON";
     63     return false;
     64   }
     65   if (require_origin && !dictionary->GetDouble("ts", &timestamp)) {
     66     LOG(ERROR) << "ts is missing from TraceEvent JSON";
     67     return false;
     68   }
     69   if (may_have_duration) {
     70     dictionary->GetDouble("dur", &duration);
     71   }
     72   if (!dictionary->GetString("cat", &category)) {
     73     LOG(ERROR) << "cat is missing from TraceEvent JSON";
     74     return false;
     75   }
     76   if (!dictionary->GetString("name", &name)) {
     77     LOG(ERROR) << "name is missing from TraceEvent JSON";
     78     return false;
     79   }
     80   if (!dictionary->GetDictionary("args", &args)) {
     81     LOG(ERROR) << "args is missing from TraceEvent JSON";
     82     return false;
     83   }
     84   if (require_id && !dictionary->GetString("id", &id)) {
     85     LOG(ERROR) << "id is missing from ASYNC_BEGIN/ASYNC_END TraceEvent JSON";
     86     return false;
     87   }
     88 
     89   // For each argument, copy the type and create a trace_analyzer::TraceValue.
     90   for (base::DictionaryValue::Iterator it(*args); !it.IsAtEnd();
     91        it.Advance()) {
     92     std::string str;
     93     bool boolean = false;
     94     int int_num = 0;
     95     double double_num = 0.0;
     96     if (it.value().GetAsString(&str)) {
     97       arg_strings[it.key()] = str;
     98     } else if (it.value().GetAsInteger(&int_num)) {
     99       arg_numbers[it.key()] = static_cast<double>(int_num);
    100     } else if (it.value().GetAsBoolean(&boolean)) {
    101       arg_numbers[it.key()] = static_cast<double>(boolean ? 1 : 0);
    102     } else if (it.value().GetAsDouble(&double_num)) {
    103       arg_numbers[it.key()] = double_num;
    104     } else {
    105       LOG(WARNING) << "Value type of argument is not supported: " <<
    106           static_cast<int>(it.value().GetType());
    107       continue;  // Skip non-supported arguments.
    108     }
    109   }
    110 
    111   return true;
    112 }
    113 
    114 double TraceEvent::GetAbsTimeToOtherEvent() const {
    115   return fabs(other_event->timestamp - timestamp);
    116 }
    117 
    118 bool TraceEvent::GetArgAsString(const std::string& name,
    119                                 std::string* arg) const {
    120   std::map<std::string, std::string>::const_iterator i = arg_strings.find(name);
    121   if (i != arg_strings.end()) {
    122     *arg = i->second;
    123     return true;
    124   }
    125   return false;
    126 }
    127 
    128 bool TraceEvent::GetArgAsNumber(const std::string& name,
    129                                 double* arg) const {
    130   std::map<std::string, double>::const_iterator i = arg_numbers.find(name);
    131   if (i != arg_numbers.end()) {
    132     *arg = i->second;
    133     return true;
    134   }
    135   return false;
    136 }
    137 
    138 bool TraceEvent::HasStringArg(const std::string& name) const {
    139   return (arg_strings.find(name) != arg_strings.end());
    140 }
    141 
    142 bool TraceEvent::HasNumberArg(const std::string& name) const {
    143   return (arg_numbers.find(name) != arg_numbers.end());
    144 }
    145 
    146 std::string TraceEvent::GetKnownArgAsString(const std::string& name) const {
    147   std::string arg_string;
    148   bool result = GetArgAsString(name, &arg_string);
    149   DCHECK(result);
    150   return arg_string;
    151 }
    152 
    153 double TraceEvent::GetKnownArgAsDouble(const std::string& name) const {
    154   double arg_double = 0;
    155   bool result = GetArgAsNumber(name, &arg_double);
    156   DCHECK(result);
    157   return arg_double;
    158 }
    159 
    160 int TraceEvent::GetKnownArgAsInt(const std::string& name) const {
    161   double arg_double = 0;
    162   bool result = GetArgAsNumber(name, &arg_double);
    163   DCHECK(result);
    164   return static_cast<int>(arg_double);
    165 }
    166 
    167 bool TraceEvent::GetKnownArgAsBool(const std::string& name) const {
    168   double arg_double = 0;
    169   bool result = GetArgAsNumber(name, &arg_double);
    170   DCHECK(result);
    171   return (arg_double != 0.0);
    172 }
    173 
    174 // QueryNode
    175 
    176 QueryNode::QueryNode(const Query& query) : query_(query) {
    177 }
    178 
    179 QueryNode::~QueryNode() {
    180 }
    181 
    182 // Query
    183 
    184 Query::Query(TraceEventMember member)
    185     : type_(QUERY_EVENT_MEMBER),
    186       operator_(OP_INVALID),
    187       member_(member),
    188       number_(0),
    189       is_pattern_(false) {
    190 }
    191 
    192 Query::Query(TraceEventMember member, const std::string& arg_name)
    193     : type_(QUERY_EVENT_MEMBER),
    194       operator_(OP_INVALID),
    195       member_(member),
    196       number_(0),
    197       string_(arg_name),
    198       is_pattern_(false) {
    199 }
    200 
    201 Query::Query(const Query& query)
    202     : type_(query.type_),
    203       operator_(query.operator_),
    204       left_(query.left_),
    205       right_(query.right_),
    206       member_(query.member_),
    207       number_(query.number_),
    208       string_(query.string_),
    209       is_pattern_(query.is_pattern_) {
    210 }
    211 
    212 Query::~Query() {
    213 }
    214 
    215 Query Query::String(const std::string& str) {
    216   return Query(str);
    217 }
    218 
    219 Query Query::Double(double num) {
    220   return Query(num);
    221 }
    222 
    223 Query Query::Int(int32_t num) {
    224   return Query(static_cast<double>(num));
    225 }
    226 
    227 Query Query::Uint(uint32_t num) {
    228   return Query(static_cast<double>(num));
    229 }
    230 
    231 Query Query::Bool(bool boolean) {
    232   return Query(boolean ? 1.0 : 0.0);
    233 }
    234 
    235 Query Query::Phase(char phase) {
    236   return Query(static_cast<double>(phase));
    237 }
    238 
    239 Query Query::Pattern(const std::string& pattern) {
    240   Query query(pattern);
    241   query.is_pattern_ = true;
    242   return query;
    243 }
    244 
    245 bool Query::Evaluate(const TraceEvent& event) const {
    246   // First check for values that can convert to bool.
    247 
    248   // double is true if != 0:
    249   double bool_value = 0.0;
    250   bool is_bool = GetAsDouble(event, &bool_value);
    251   if (is_bool)
    252     return (bool_value != 0.0);
    253 
    254   // string is true if it is non-empty:
    255   std::string str_value;
    256   bool is_str = GetAsString(event, &str_value);
    257   if (is_str)
    258     return !str_value.empty();
    259 
    260   DCHECK_EQ(QUERY_BOOLEAN_OPERATOR, type_)
    261       << "Invalid query: missing boolean expression";
    262   DCHECK(left_.get());
    263   DCHECK(right_.get() || is_unary_operator());
    264 
    265   if (is_comparison_operator()) {
    266     DCHECK(left().is_value() && right().is_value())
    267         << "Invalid query: comparison operator used between event member and "
    268            "value.";
    269     bool compare_result = false;
    270     if (CompareAsDouble(event, &compare_result))
    271       return compare_result;
    272     if (CompareAsString(event, &compare_result))
    273       return compare_result;
    274     return false;
    275   }
    276   // It's a logical operator.
    277   switch (operator_) {
    278     case OP_AND:
    279       return left().Evaluate(event) && right().Evaluate(event);
    280     case OP_OR:
    281       return left().Evaluate(event) || right().Evaluate(event);
    282     case OP_NOT:
    283       return !left().Evaluate(event);
    284     default:
    285       NOTREACHED();
    286       return false;
    287   }
    288 }
    289 
    290 bool Query::CompareAsDouble(const TraceEvent& event, bool* result) const {
    291   double lhs, rhs;
    292   if (!left().GetAsDouble(event, &lhs) || !right().GetAsDouble(event, &rhs))
    293     return false;
    294   switch (operator_) {
    295     case OP_EQ:
    296       *result = (lhs == rhs);
    297       return true;
    298     case OP_NE:
    299       *result = (lhs != rhs);
    300       return true;
    301     case OP_LT:
    302       *result = (lhs < rhs);
    303       return true;
    304     case OP_LE:
    305       *result = (lhs <= rhs);
    306       return true;
    307     case OP_GT:
    308       *result = (lhs > rhs);
    309       return true;
    310     case OP_GE:
    311       *result = (lhs >= rhs);
    312       return true;
    313     default:
    314       NOTREACHED();
    315       return false;
    316   }
    317 }
    318 
    319 bool Query::CompareAsString(const TraceEvent& event, bool* result) const {
    320   std::string lhs, rhs;
    321   if (!left().GetAsString(event, &lhs) || !right().GetAsString(event, &rhs))
    322     return false;
    323   switch (operator_) {
    324     case OP_EQ:
    325       if (right().is_pattern_)
    326         *result = base::MatchPattern(lhs, rhs);
    327       else if (left().is_pattern_)
    328         *result = base::MatchPattern(rhs, lhs);
    329       else
    330         *result = (lhs == rhs);
    331       return true;
    332     case OP_NE:
    333       if (right().is_pattern_)
    334         *result = !base::MatchPattern(lhs, rhs);
    335       else if (left().is_pattern_)
    336         *result = !base::MatchPattern(rhs, lhs);
    337       else
    338         *result = (lhs != rhs);
    339       return true;
    340     case OP_LT:
    341       *result = (lhs < rhs);
    342       return true;
    343     case OP_LE:
    344       *result = (lhs <= rhs);
    345       return true;
    346     case OP_GT:
    347       *result = (lhs > rhs);
    348       return true;
    349     case OP_GE:
    350       *result = (lhs >= rhs);
    351       return true;
    352     default:
    353       NOTREACHED();
    354       return false;
    355   }
    356 }
    357 
    358 bool Query::EvaluateArithmeticOperator(const TraceEvent& event,
    359                                        double* num) const {
    360   DCHECK_EQ(QUERY_ARITHMETIC_OPERATOR, type_);
    361   DCHECK(left_.get());
    362   DCHECK(right_.get() || is_unary_operator());
    363 
    364   double lhs = 0, rhs = 0;
    365   if (!left().GetAsDouble(event, &lhs))
    366     return false;
    367   if (!is_unary_operator() && !right().GetAsDouble(event, &rhs))
    368     return false;
    369 
    370   switch (operator_) {
    371     case OP_ADD:
    372       *num = lhs + rhs;
    373       return true;
    374     case OP_SUB:
    375       *num = lhs - rhs;
    376       return true;
    377     case OP_MUL:
    378       *num = lhs * rhs;
    379       return true;
    380     case OP_DIV:
    381       *num = lhs / rhs;
    382       return true;
    383     case OP_MOD:
    384       *num = static_cast<double>(static_cast<int64_t>(lhs) %
    385                                  static_cast<int64_t>(rhs));
    386       return true;
    387     case OP_NEGATE:
    388       *num = -lhs;
    389       return true;
    390     default:
    391       NOTREACHED();
    392       return false;
    393   }
    394 }
    395 
    396 bool Query::GetAsDouble(const TraceEvent& event, double* num) const {
    397   switch (type_) {
    398     case QUERY_ARITHMETIC_OPERATOR:
    399       return EvaluateArithmeticOperator(event, num);
    400     case QUERY_EVENT_MEMBER:
    401       return GetMemberValueAsDouble(event, num);
    402     case QUERY_NUMBER:
    403       *num = number_;
    404       return true;
    405     default:
    406       return false;
    407   }
    408 }
    409 
    410 bool Query::GetAsString(const TraceEvent& event, std::string* str) const {
    411   switch (type_) {
    412     case QUERY_EVENT_MEMBER:
    413       return GetMemberValueAsString(event, str);
    414     case QUERY_STRING:
    415       *str = string_;
    416       return true;
    417     default:
    418       return false;
    419   }
    420 }
    421 
    422 bool Query::GetMemberValueAsDouble(const TraceEvent& event,
    423                                    double* num) const {
    424   DCHECK_EQ(QUERY_EVENT_MEMBER, type_);
    425 
    426   // This could be a request for a member of |event| or a member of |event|'s
    427   // associated event. Store the target event in the_event:
    428   const TraceEvent* the_event = (member_ < OTHER_PID) ?
    429       &event : event.other_event;
    430 
    431   // Request for member of associated event, but there is no associated event.
    432   if (!the_event)
    433     return false;
    434 
    435   switch (member_) {
    436     case EVENT_PID:
    437     case OTHER_PID:
    438       *num = static_cast<double>(the_event->thread.process_id);
    439       return true;
    440     case EVENT_TID:
    441     case OTHER_TID:
    442       *num = static_cast<double>(the_event->thread.thread_id);
    443       return true;
    444     case EVENT_TIME:
    445     case OTHER_TIME:
    446       *num = the_event->timestamp;
    447       return true;
    448     case EVENT_DURATION:
    449       if (!the_event->has_other_event())
    450         return false;
    451       *num = the_event->GetAbsTimeToOtherEvent();
    452       return true;
    453     case EVENT_COMPLETE_DURATION:
    454       if (the_event->phase != TRACE_EVENT_PHASE_COMPLETE)
    455         return false;
    456       *num = the_event->duration;
    457       return true;
    458     case EVENT_PHASE:
    459     case OTHER_PHASE:
    460       *num = static_cast<double>(the_event->phase);
    461       return true;
    462     case EVENT_HAS_STRING_ARG:
    463     case OTHER_HAS_STRING_ARG:
    464       *num = (the_event->HasStringArg(string_) ? 1.0 : 0.0);
    465       return true;
    466     case EVENT_HAS_NUMBER_ARG:
    467     case OTHER_HAS_NUMBER_ARG:
    468       *num = (the_event->HasNumberArg(string_) ? 1.0 : 0.0);
    469       return true;
    470     case EVENT_ARG:
    471     case OTHER_ARG: {
    472       // Search for the argument name and return its value if found.
    473       std::map<std::string, double>::const_iterator num_i =
    474           the_event->arg_numbers.find(string_);
    475       if (num_i == the_event->arg_numbers.end())
    476         return false;
    477       *num = num_i->second;
    478       return true;
    479     }
    480     case EVENT_HAS_OTHER:
    481       // return 1.0 (true) if the other event exists
    482       *num = event.other_event ? 1.0 : 0.0;
    483       return true;
    484     default:
    485       return false;
    486   }
    487 }
    488 
    489 bool Query::GetMemberValueAsString(const TraceEvent& event,
    490                                    std::string* str) const {
    491   DCHECK_EQ(QUERY_EVENT_MEMBER, type_);
    492 
    493   // This could be a request for a member of |event| or a member of |event|'s
    494   // associated event. Store the target event in the_event:
    495   const TraceEvent* the_event = (member_ < OTHER_PID) ?
    496       &event : event.other_event;
    497 
    498   // Request for member of associated event, but there is no associated event.
    499   if (!the_event)
    500     return false;
    501 
    502   switch (member_) {
    503     case EVENT_CATEGORY:
    504     case OTHER_CATEGORY:
    505       *str = the_event->category;
    506       return true;
    507     case EVENT_NAME:
    508     case OTHER_NAME:
    509       *str = the_event->name;
    510       return true;
    511     case EVENT_ID:
    512     case OTHER_ID:
    513       *str = the_event->id;
    514       return true;
    515     case EVENT_ARG:
    516     case OTHER_ARG: {
    517       // Search for the argument name and return its value if found.
    518       std::map<std::string, std::string>::const_iterator str_i =
    519           the_event->arg_strings.find(string_);
    520       if (str_i == the_event->arg_strings.end())
    521         return false;
    522       *str = str_i->second;
    523       return true;
    524     }
    525     default:
    526       return false;
    527   }
    528 }
    529 
    530 Query::Query(const std::string& str)
    531     : type_(QUERY_STRING),
    532       operator_(OP_INVALID),
    533       member_(EVENT_INVALID),
    534       number_(0),
    535       string_(str),
    536       is_pattern_(false) {
    537 }
    538 
    539 Query::Query(double num)
    540     : type_(QUERY_NUMBER),
    541       operator_(OP_INVALID),
    542       member_(EVENT_INVALID),
    543       number_(num),
    544       is_pattern_(false) {
    545 }
    546 const Query& Query::left() const {
    547   return left_->query();
    548 }
    549 
    550 const Query& Query::right() const {
    551   return right_->query();
    552 }
    553 
    554 Query Query::operator==(const Query& rhs) const {
    555   return Query(*this, rhs, OP_EQ);
    556 }
    557 
    558 Query Query::operator!=(const Query& rhs) const {
    559   return Query(*this, rhs, OP_NE);
    560 }
    561 
    562 Query Query::operator<(const Query& rhs) const {
    563   return Query(*this, rhs, OP_LT);
    564 }
    565 
    566 Query Query::operator<=(const Query& rhs) const {
    567   return Query(*this, rhs, OP_LE);
    568 }
    569 
    570 Query Query::operator>(const Query& rhs) const {
    571   return Query(*this, rhs, OP_GT);
    572 }
    573 
    574 Query Query::operator>=(const Query& rhs) const {
    575   return Query(*this, rhs, OP_GE);
    576 }
    577 
    578 Query Query::operator&&(const Query& rhs) const {
    579   return Query(*this, rhs, OP_AND);
    580 }
    581 
    582 Query Query::operator||(const Query& rhs) const {
    583   return Query(*this, rhs, OP_OR);
    584 }
    585 
    586 Query Query::operator!() const {
    587   return Query(*this, OP_NOT);
    588 }
    589 
    590 Query Query::operator+(const Query& rhs) const {
    591   return Query(*this, rhs, OP_ADD);
    592 }
    593 
    594 Query Query::operator-(const Query& rhs) const {
    595   return Query(*this, rhs, OP_SUB);
    596 }
    597 
    598 Query Query::operator*(const Query& rhs) const {
    599   return Query(*this, rhs, OP_MUL);
    600 }
    601 
    602 Query Query::operator/(const Query& rhs) const {
    603   return Query(*this, rhs, OP_DIV);
    604 }
    605 
    606 Query Query::operator%(const Query& rhs) const {
    607   return Query(*this, rhs, OP_MOD);
    608 }
    609 
    610 Query Query::operator-() const {
    611   return Query(*this, OP_NEGATE);
    612 }
    613 
    614 
    615 Query::Query(const Query& left, const Query& right, Operator binary_op)
    616     : operator_(binary_op),
    617       left_(new QueryNode(left)),
    618       right_(new QueryNode(right)),
    619       member_(EVENT_INVALID),
    620       number_(0) {
    621   type_ = (binary_op < OP_ADD ?
    622            QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
    623 }
    624 
    625 Query::Query(const Query& left, Operator unary_op)
    626     : operator_(unary_op),
    627       left_(new QueryNode(left)),
    628       member_(EVENT_INVALID),
    629       number_(0) {
    630   type_ = (unary_op < OP_ADD ?
    631            QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
    632 }
    633 
    634 namespace {
    635 
    636 // Search |events| for |query| and add matches to |output|.
    637 size_t FindMatchingEvents(const std::vector<TraceEvent>& events,
    638                           const Query& query,
    639                           TraceEventVector* output,
    640                           bool ignore_metadata_events) {
    641   for (size_t i = 0; i < events.size(); ++i) {
    642     if (ignore_metadata_events && events[i].phase == TRACE_EVENT_PHASE_METADATA)
    643       continue;
    644     if (query.Evaluate(events[i]))
    645       output->push_back(&events[i]);
    646   }
    647   return output->size();
    648 }
    649 
    650 bool ParseEventsFromJson(const std::string& json,
    651                          std::vector<TraceEvent>* output) {
    652   scoped_ptr<base::Value> root = base::JSONReader::Read(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
    970