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