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