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