text: // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #include "base/test/trace_event_analyzer.h"
  
  #include <algorithm>
  #include <math.h>
  #include <set>
  
  #include "base/json/json_reader.h"
  #include "base/memory/scoped_ptr.h"
  #include "base/values.h"
  
  namespace trace_analyzer {
  
  // TraceEvent
  
  TraceEvent::TraceEvent()
      : thread(0, 0),
        timestamp(0),
        phase(TRACE_EVENT_PHASE_BEGIN),
        other_event(NULL) {
  }
  
  TraceEvent::~TraceEvent() {
  }
  
  bool TraceEvent::SetFromJSON(const base::Value* event_value) {
    if (event_value->GetType() != base::Value::TYPE_DICTIONARY) {
      LOG(ERROR) << "Value must be TYPE_DICTIONARY";
      return false;
    }
    const base::DictionaryValue* dictionary =
        static_cast<const base::DictionaryValue*>(event_value);
  
    std::string phase_str;
    const base::DictionaryValue* args = NULL;
  
    if (!dictionary->GetString("ph", &phase_str)) {
      LOG(ERROR) << "ph is missing from TraceEvent JSON";
      return false;
    }
  
    phase = *phase_str.data();
  
    bool require_origin = (phase != TRACE_EVENT_PHASE_METADATA);
    bool require_id = (phase == TRACE_EVENT_PHASE_ASYNC_BEGIN ||
                       phase == TRACE_EVENT_PHASE_ASYNC_STEP ||
                       phase == TRACE_EVENT_PHASE_ASYNC_END);
  
    if (require_origin && !dictionary->GetInteger("pid", &thread.process_id)) {
      LOG(ERROR) << "pid is missing from TraceEvent JSON";
      return false;
    }
    if (require_origin && !dictionary->GetInteger("tid", &thread.thread_id)) {
      LOG(ERROR) << "tid is missing from TraceEvent JSON";
      return false;
    }
    if (require_origin && !dictionary->GetDouble("ts", &timestamp)) {
      LOG(ERROR) << "ts is missing from TraceEvent JSON";
      return false;
    }
    if (!dictionary->GetString("cat", &category)) {
      LOG(ERROR) << "cat is missing from TraceEvent JSON";
      return false;
    }
    if (!dictionary->GetString("name", &name)) {
      LOG(ERROR) << "name is missing from TraceEvent JSON";
      return false;
    }
    if (!dictionary->GetDictionary("args", &args)) {
      LOG(ERROR) << "args is missing from TraceEvent JSON";
      return false;
    }
    if (require_id && !dictionary->GetString("id", &id)) {
      LOG(ERROR) << "id is missing from ASYNC_BEGIN/ASYNC_END TraceEvent JSON";
      return false;
    }
  
    // For each argument, copy the type and create a trace_analyzer::TraceValue.
    base::DictionaryValue::key_iterator keyi = args->begin_keys();
    for (; keyi != args->end_keys(); ++keyi) {
      std::string str;
      bool boolean = false;
      int int_num = 0;
      double double_num = 0.0;
      const Value* value = NULL;
      if (args->GetWithoutPathExpansion(*keyi, &value)) {
        if (value->GetAsString(&str))
          arg_strings[*keyi] = str;
        else if (value->GetAsInteger(&int_num))
          arg_numbers[*keyi] = static_cast<double>(int_num);
        else if (value->GetAsBoolean(&boolean))
          arg_numbers[*keyi] = static_cast<double>(boolean ? 1 : 0);
        else if (value->GetAsDouble(&double_num))
          arg_numbers[*keyi] = double_num;
        else {
          LOG(ERROR) << "Value type of argument is not supported: " <<
                        static_cast<int>(value->GetType());
          return false;  // Invalid trace event JSON format.
        }
      }
    }
  
    return true;
  }
  
  double TraceEvent::GetAbsTimeToOtherEvent() const {
    return fabs(other_event->timestamp - timestamp);
  }
  
  bool TraceEvent::GetArgAsString(const std::string& name,
                                  std::string* arg) const {
    std::map<std::string, std::string>::const_iterator i = arg_strings.find(name);
    if (i != arg_strings.end()) {
      *arg = i->second;
      return true;
    }
    return false;
  }
  
  bool TraceEvent::GetArgAsNumber(const std::string& name,
                                  double* arg) const {
    std::map<std::string, double>::const_iterator i = arg_numbers.find(name);
    if (i != arg_numbers.end()) {
      *arg = i->second;
      return true;
    }
    return false;
  }
  
  bool TraceEvent::HasStringArg(const std::string& name) const {
    return (arg_strings.find(name) != arg_strings.end());
  }
  
  bool TraceEvent::HasNumberArg(const std::string& name) const {
    return (arg_numbers.find(name) != arg_numbers.end());
  }
  
  std::string TraceEvent::GetKnownArgAsString(const std::string& name) const {
    std::string arg_string;
    if (GetArgAsString(name, &arg_string))
      return arg_string;
    NOTREACHED();
    return "";
  }
  
  double TraceEvent::GetKnownArgAsDouble(const std::string& name) const {
    double arg_double;
    if (GetArgAsNumber(name, &arg_double))
      return arg_double;
    NOTREACHED();
    return 0;
  }
  
  int TraceEvent::GetKnownArgAsInt(const std::string& name) const {
    double arg_double;
    if (GetArgAsNumber(name, &arg_double))
      return static_cast<int>(arg_double);
    NOTREACHED();
    return 0;
  }
  
  bool TraceEvent::GetKnownArgAsBool(const std::string& name) const {
    double arg_double;
    if (GetArgAsNumber(name, &arg_double))
      return (arg_double != 0.0);
    NOTREACHED();
    return false;
  }
  
  // QueryNode
  
  QueryNode::QueryNode(const Query& query) : query_(query) {
  }
  
  QueryNode::~QueryNode() {
  }
  
  // Query
  
  Query::Query(TraceEventMember member)
      : type_(QUERY_EVENT_MEMBER),
        operator_(OP_INVALID),
        member_(member),
        number_(0),
        is_pattern_(false) {
  }
  
  Query::Query(TraceEventMember member, const std::string& arg_name)
      : type_(QUERY_EVENT_MEMBER),
        operator_(OP_INVALID),
        member_(member),
        number_(0),
        string_(arg_name),
        is_pattern_(false) {
  }
  
  Query::Query(const Query& query)
      : type_(query.type_),
        operator_(query.operator_),
        left_(query.left_),
        right_(query.right_),
        member_(query.member_),
        number_(query.number_),
        string_(query.string_),
        is_pattern_(query.is_pattern_) {
  }
  
  Query::~Query() {
  }
  
  Query Query::String(const std::string& str) {
    return Query(str);
  }
  
  Query Query::Double(double num) {
    return Query(num);
  }
  
  Query Query::Int(int32 num) {
    return Query(static_cast<double>(num));
  }
  
  Query Query::Uint(uint32 num) {
    return Query(static_cast<double>(num));
  }
  
  Query Query::Bool(bool boolean) {
    return Query(boolean ? 1.0 : 0.0);
  }
  
  Query Query::Phase(char phase) {
    return Query(static_cast<double>(phase));
  }
  
  Query Query::Pattern(const std::string& pattern) {
    Query query(pattern);
    query.is_pattern_ = true;
    return query;
  }
  
  bool Query::Evaluate(const TraceEvent& event) const {
    // First check for values that can convert to bool.
  
    // double is true if != 0:
    double bool_value = 0.0;
    bool is_bool = GetAsDouble(event, &bool_value);
    if (is_bool)
      return (bool_value != 0.0);
  
    // string is true if it is non-empty:
    std::string str_value;
    bool is_str = GetAsString(event, &str_value);
    if (is_str)
      return !str_value.empty();
  
    DCHECK(type_ == QUERY_BOOLEAN_OPERATOR)
        << "Invalid query: missing boolean expression";
    DCHECK(left_.get() && (right_.get() || is_unary_operator()));
  
    if (is_comparison_operator()) {
      DCHECK(left().is_value() && right().is_value())
          << "Invalid query: comparison operator used between event member and "
             "value.";
      bool compare_result = false;
      if (CompareAsDouble(event, &compare_result))
        return compare_result;
      else if (CompareAsString(event, &compare_result))
        return compare_result;
      return false;
    }
    // It's a logical operator.
    switch (operator_) {
      case OP_AND:
        return left().Evaluate(event) && right().Evaluate(event);
      case OP_OR:
        return left().Evaluate(event) || right().Evaluate(event);
      case OP_NOT:
        return !left().Evaluate(event);
      default:
        NOTREACHED();
    }
  
    NOTREACHED();
    return false;
  }
  
  bool Query::CompareAsDouble(const TraceEvent& event, bool* result) const {
    double lhs, rhs;
    if (!left().GetAsDouble(event, &lhs) || !right().GetAsDouble(event, &rhs))
      return false;
    switch (operator_) {
      case OP_EQ:
        *result = (lhs == rhs);
        return true;
      case OP_NE:
        *result = (lhs != rhs);
        return true;
      case OP_LT:
        *result = (lhs < rhs);
        return true;
      case OP_LE:
        *result = (lhs <= rhs);
        return true;
      case OP_GT:
        *result = (lhs > rhs);
        return true;
      case OP_GE:
        *result = (lhs >= rhs);
        return true;
      default:
        NOTREACHED();
        return false;
    }
    return true;
  }
  
  bool Query::CompareAsString(const TraceEvent& event, bool* result) const {
    std::string lhs, rhs;
    if (!left().GetAsString(event, &lhs) || !right().GetAsString(event, &rhs))
      return false;
    switch (operator_) {
      case OP_EQ:
        if (right().is_pattern_)
          *result = MatchPattern(lhs, rhs);
        else if (left().is_pattern_)
          *result = MatchPattern(rhs, lhs);
        else
          *result = (lhs == rhs);
        return true;
      case OP_NE:
        if (right().is_pattern_)
          *result = !MatchPattern(lhs, rhs);
        else if (left().is_pattern_)
          *result = !MatchPattern(rhs, lhs);
        else
          *result = (lhs != rhs);
        return true;
      case OP_LT:
        *result = (lhs < rhs);
        return true;
      case OP_LE:
        *result = (lhs <= rhs);
        return true;
      case OP_GT:
        *result = (lhs > rhs);
        return true;
      case OP_GE:
        *result = (lhs >= rhs);
        return true;
      default:
        NOTREACHED();
        return false;
    }
    return true;
  }
  
  bool Query::EvaluateArithmeticOperator(const TraceEvent& event,
                                         double* num) const {
    DCHECK(type_ == QUERY_ARITHMETIC_OPERATOR);
    DCHECK(left_.get() && (right_.get() || is_unary_operator()));
  
    double lhs = 0, rhs = 0;
    if (!left().GetAsDouble(event, &lhs))
      return false;
    if (!is_unary_operator() && !right().GetAsDouble(event, &rhs))
      return false;
  
    switch (operator_) {
      case OP_ADD:
        *num = lhs + rhs;
        return true;
      case OP_SUB:
        *num = lhs - rhs;
        return true;
      case OP_MUL:
        *num = lhs * rhs;
        return true;
      case OP_DIV:
        *num = lhs / rhs;
        return true;
      case OP_MOD:
        *num = static_cast<double>(static_cast<int64>(lhs) %
                                   static_cast<int64>(rhs));
        return true;
      case OP_NEGATE:
        *num = -lhs;
        return true;
      default:
        NOTREACHED();
        return false;
    }
  }
  
  bool Query::GetAsDouble(const TraceEvent& event, double* num) const {
    switch (type_) {
      case QUERY_ARITHMETIC_OPERATOR:
        return EvaluateArithmeticOperator(event, num);
      case QUERY_EVENT_MEMBER:
        return GetMemberValueAsDouble(event, num);
      case QUERY_NUMBER:
        *num = number_;
        return true;
      default:
        return false;
    }
  }
  
  bool Query::GetAsString(const TraceEvent& event, std::string* str) const {
    switch (type_) {
      case QUERY_EVENT_MEMBER:
        return GetMemberValueAsString(event, str);
      case QUERY_STRING:
        *str = string_;
        return true;
      default:
        return false;
    }
  }
  
  bool Query::GetMemberValueAsDouble(const TraceEvent& event,
                                     double* num) const {
    DCHECK(type_ == QUERY_EVENT_MEMBER);
  
    // This could be a request for a member of |event| or a member of |event|'s
    // associated event. Store the target event in the_event:
    const TraceEvent* the_event = (member_ < OTHER_PID) ?
        &event : event.other_event;
  
    // Request for member of associated event, but there is no associated event.
    if (!the_event)
      return false;
  
    switch (member_) {
      case EVENT_PID:
      case OTHER_PID:
        *num = static_cast<double>(the_event->thread.process_id);
        return true;
      case EVENT_TID:
      case OTHER_TID:
        *num = static_cast<double>(the_event->thread.thread_id);
        return true;
      case EVENT_TIME:
      case OTHER_TIME:
        *num = the_event->timestamp;
        return true;
      case EVENT_DURATION:
        if (the_event->has_other_event()) {
          *num = the_event->GetAbsTimeToOtherEvent();
          return true;
        }
        return false;
      case EVENT_PHASE:
      case OTHER_PHASE:
        *num = static_cast<double>(the_event->phase);
        return true;
      case EVENT_HAS_STRING_ARG:
      case OTHER_HAS_STRING_ARG:
        *num = (the_event->HasStringArg(string_) ? 1.0 : 0.0);
        return true;
      case EVENT_HAS_NUMBER_ARG:
      case OTHER_HAS_NUMBER_ARG:
        *num = (the_event->HasNumberArg(string_) ? 1.0 : 0.0);
        return true;
      case EVENT_ARG:
      case OTHER_ARG: {
        // Search for the argument name and return its value if found.
        std::map<std::string, double>::const_iterator num_i =
            the_event->arg_numbers.find(string_);
        if (num_i == the_event->arg_numbers.end())
          return false;
        *num = num_i->second;
        return true;
      }
      case EVENT_HAS_OTHER:
        // return 1.0 (true) if the other event exists
        *num = event.other_event ? 1.0 : 0.0;
        return true;
      default:
        return false;
    }
  }
  
  bool Query::GetMemberValueAsString(const TraceEvent& event,
                                     std::string* str) const {
    DCHECK(type_ == QUERY_EVENT_MEMBER);
  
    // This could be a request for a member of |event| or a member of |event|'s
    // associated event. Store the target event in the_event:
    const TraceEvent* the_event = (member_ < OTHER_PID) ?
        &event : event.other_event;
  
    // Request for member of associated event, but there is no associated event.
    if (!the_event)
      return false;
  
    switch (member_) {
      case EVENT_CATEGORY:
      case OTHER_CATEGORY:
        *str = the_event->category;
        return true;
      case EVENT_NAME:
      case OTHER_NAME:
        *str = the_event->name;
        return true;
      case EVENT_ID:
      case OTHER_ID:
        *str = the_event->id;
        return true;
      case EVENT_ARG:
      case OTHER_ARG: {
        // Search for the argument name and return its value if found.
        std::map<std::string, std::string>::const_iterator str_i =
            the_event->arg_strings.find(string_);
        if (str_i == the_event->arg_strings.end())
          return false;
        *str = str_i->second;
        return true;
      }
      default:
        return false;
    }
  }
  
  Query::Query(const std::string& str)
      : type_(QUERY_STRING),
        operator_(OP_INVALID),
        member_(EVENT_INVALID),
        number_(0),
        string_(str),
        is_pattern_(false) {
  }
  
  Query::Query(double num)
      : type_(QUERY_NUMBER),
        operator_(OP_INVALID),
        member_(EVENT_INVALID),
        number_(num),
        is_pattern_(false) {
  }
  const Query& Query::left() const {
    return left_->query();
  }
  
  const Query& Query::right() const {
    return right_->query();
  }
  
  Query Query::operator==(const Query& rhs) const {
    return Query(*this, rhs, OP_EQ);
  }
  
  Query Query::operator!=(const Query& rhs) const {
    return Query(*this, rhs, OP_NE);
  }
  
  Query Query::operator<(const Query& rhs) const {
    return Query(*this, rhs, OP_LT);
  }
  
  Query Query::operator<=(const Query& rhs) const {
    return Query(*this, rhs, OP_LE);
  }
  
  Query Query::operator>(const Query& rhs) const {
    return Query(*this, rhs, OP_GT);
  }
  
  Query Query::operator>=(const Query& rhs) const {
    return Query(*this, rhs, OP_GE);
  }
  
  Query Query::operator&&(const Query& rhs) const {
    return Query(*this, rhs, OP_AND);
  }
  
  Query Query::operator||(const Query& rhs) const {
    return Query(*this, rhs, OP_OR);
  }
  
  Query Query::operator!() const {
    return Query(*this, OP_NOT);
  }
  
  Query Query::operator+(const Query& rhs) const {
    return Query(*this, rhs, OP_ADD);
  }
  
  Query Query::operator-(const Query& rhs) const {
    return Query(*this, rhs, OP_SUB);
  }
  
  Query Query::operator*(const Query& rhs) const {
    return Query(*this, rhs, OP_MUL);
  }
  
  Query Query::operator/(const Query& rhs) const {
    return Query(*this, rhs, OP_DIV);
  }
  
  Query Query::operator%(const Query& rhs) const {
    return Query(*this, rhs, OP_MOD);
  }
  
  Query Query::operator-() const {
    return Query(*this, OP_NEGATE);
  }
  
  
  Query::Query(const Query& left, const Query& right, Operator binary_op)
      : operator_(binary_op),
        left_(new QueryNode(left)),
        right_(new QueryNode(right)),
        member_(EVENT_INVALID),
        number_(0) {
    type_ = (binary_op < OP_ADD ?
             QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
  }
  
  Query::Query(const Query& left, Operator unary_op)
      : operator_(unary_op),
        left_(new QueryNode(left)),
        member_(EVENT_INVALID),
        number_(0) {
    type_ = (unary_op < OP_ADD ?
             QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
  }
  
  namespace {
  
  // Search |events| for |query| and add matches to |output|.
  size_t FindMatchingEvents(const std::vector<TraceEvent>& events,
                            const Query& query,
                            TraceEventVector* output) {
    for (size_t i = 0; i < events.size(); ++i) {
      if (query.Evaluate(events[i]))
        output->push_back(&events[i]);
    }
    return output->size();
  }
  
  bool ParseEventsFromJson(const std::string& json,
                           std::vector<TraceEvent>* output) {
    scoped_ptr<base::Value> root;
    root.reset(base::JSONReader::Read(json));
  
    ListValue* root_list = NULL;
    if (!root.get() || !root->GetAsList(&root_list))
      return false;
  
    for (size_t i = 0; i < root_list->GetSize(); ++i) {
      Value* item = NULL;
      if (root_list->Get(i, &item)) {
        TraceEvent event;
        if (event.SetFromJSON(item))
          output->push_back(event);
        else
          return false;
      }
    }
  
    return true;
  }
  
  }  // namespace
  
  // TraceAnalyzer
  
  TraceAnalyzer::TraceAnalyzer() : allow_assocation_changes_(true) {
  }
  
  TraceAnalyzer::~TraceAnalyzer() {
  }
  
  // static
  TraceAnalyzer* TraceAnalyzer::Create(const std::string& json_events) {
    scoped_ptr<TraceAnalyzer> analyzer(new TraceAnalyzer());
    if (analyzer->SetEvents(json_events))
      return analyzer.release();
    return NULL;
  }
  
  bool TraceAnalyzer::SetEvents(const std::string& json_events) {
    raw_events_.clear();
    if (!ParseEventsFromJson(json_events, &raw_events_))
      return false;
    std::stable_sort(raw_events_.begin(), raw_events_.end());
    ParseMetadata();
    return true;
  }
  
  void TraceAnalyzer::AssociateBeginEndEvents() {
    using trace_analyzer::Query;
  
    Query begin(Query::EventPhaseIs(TRACE_EVENT_PHASE_BEGIN));
    Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_END));
    Query match(Query::EventName() == Query::OtherName() &&
                Query::EventCategory() == Query::OtherCategory() &&
                Query::EventTid() == Query::OtherTid() &&
                Query::EventPid() == Query::OtherPid());
  
    AssociateEvents(begin, end, match);
  }
  
  void TraceAnalyzer::AssociateAsyncBeginEndEvents() {
    using trace_analyzer::Query;
  
    Query begin(
        Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_BEGIN) ||
        Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP));
    Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_END) ||
              Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP));
    Query match(Query::EventName() == Query::OtherName() &&
                Query::EventCategory() == Query::OtherCategory() &&
                Query::EventId() == Query::OtherId());
  
    AssociateEvents(begin, end, match);
  }
  
  void TraceAnalyzer::AssociateEvents(const Query& first,
                                      const Query& second,
                                      const Query& match) {
    DCHECK(allow_assocation_changes_) << "AssociateEvents not allowed after "
                                        "FindEvents";
  
    // Search for matching begin/end event pairs. When a matching end is found,
    // it is associated with the begin event.
    std::vector<TraceEvent*> begin_stack;
    for (size_t event_index = 0; event_index < raw_events_.size();
         ++event_index) {
  
      TraceEvent& this_event = raw_events_[event_index];
  
      if (second.Evaluate(this_event)) {
        // Search stack for matching begin, starting from end.
        for (int stack_index = static_cast<int>(begin_stack.size()) - 1;
             stack_index >= 0; --stack_index) {
          TraceEvent& begin_event = *begin_stack[stack_index];
  
          // Temporarily set other to test against the match query.
          const TraceEvent* other_backup = begin_event.other_event;
          begin_event.other_event = &this_event;
          if (match.Evaluate(begin_event)) {
            // Found a matching begin/end pair.
            // Erase the matching begin event index from the stack.
            begin_stack.erase(begin_stack.begin() + stack_index);
            break;
          }
  
          // Not a match, restore original other and continue.
          begin_event.other_event = other_backup;
        }
      }
      // Even if this_event is a |second| event that has matched an earlier
      // |first| event, it can still also be a |first| event and be associated
      // with a later |second| event.
      if (first.Evaluate(this_event)) {
        begin_stack.push_back(&this_event);
      }
    }
  }
  
  void TraceAnalyzer::MergeAssociatedEventArgs() {
    for (size_t i = 0; i < raw_events_.size(); ++i) {
      // Merge all associated events with the first event.
      const TraceEvent* other = raw_events_[i].other_event;
      // Avoid looping by keeping set of encountered TraceEvents.
      std::set<const TraceEvent*> encounters;
      encounters.insert(&raw_events_[i]);
      while (other && encounters.find(other) == encounters.end()) {
        encounters.insert(other);
        raw_events_[i].arg_numbers.insert(
            other->arg_numbers.begin(),
            other->arg_numbers.end());
        raw_events_[i].arg_strings.insert(
            other->arg_strings.begin(),
            other->arg_strings.end());
        other = other->other_event;
      }
    }
  }
  
  size_t TraceAnalyzer::FindEvents(const Query& query, TraceEventVector* output) {
    allow_assocation_changes_ = false;
    output->clear();
    return FindMatchingEvents(raw_events_, query, output);
  }
  
  const TraceEvent* TraceAnalyzer::FindFirstOf(const Query& query) {
    TraceEventVector output;
    if (FindEvents(query, &output) > 0)
      return output.front();
    return NULL;
  }
  
  const TraceEvent* TraceAnalyzer::FindLastOf(const Query& query) {
    TraceEventVector output;
    if (FindEvents(query, &output) > 0)
      return output.back();
    return NULL;
  }
  
  const std::string& TraceAnalyzer::GetThreadName(
      const TraceEvent::ProcessThreadID& thread) {
    // If thread is not found, just add and return empty string.
    return thread_names_[thread];
  }
  
  void TraceAnalyzer::ParseMetadata() {
    for (size_t i = 0; i < raw_events_.size(); ++i) {
      TraceEvent& this_event = raw_events_[i];
      // Check for thread name metadata.
      if (this_event.phase != TRACE_EVENT_PHASE_METADATA ||
          this_event.name != "thread_name")
        continue;
      std::map<std::string, std::string>::const_iterator string_it =
          this_event.arg_strings.find("name");
      if (string_it != this_event.arg_strings.end())
        thread_names_[this_event.thread] = string_it->second;
    }
  }
  
  // TraceEventVector utility functions.
  
  bool GetRateStats(const TraceEventVector& events,
                    RateStats* stats,
                    const RateStatsOptions* options) {
    CHECK(stats);
    // Need at least 3 events to calculate rate stats.
    const size_t kMinEvents = 3;
    if (events.size() < kMinEvents) {
      LOG(ERROR) << "Not enough events: " << events.size();
      return false;
    }
  
    std::vector<double> deltas;
    size_t num_deltas = events.size() - 1;
    for (size_t i = 0; i < num_deltas; ++i) {
      double delta = events.at(i + 1)->timestamp - events.at(i)->timestamp;
      if (delta < 0.0) {
        LOG(ERROR) << "Events are out of order";
        return false;
      }
      deltas.push_back(delta);
    }
  
    std::sort(deltas.begin(), deltas.end());
  
    if (options) {
      if (options->trim_min + options->trim_max > events.size() - kMinEvents) {
        LOG(ERROR) << "Attempt to trim too many events";
        return false;
      }
      deltas.erase(deltas.begin(), deltas.begin() + options->trim_min);
      deltas.erase(deltas.end() - options->trim_max, deltas.end());
    }
  
    num_deltas = deltas.size();
    double delta_sum = 0.0;
    for (size_t i = 0; i < num_deltas; ++i)
      delta_sum += deltas[i];
  
    stats->min_us = *std::min_element(deltas.begin(), deltas.end());
    stats->max_us = *std::max_element(deltas.begin(), deltas.end());
    stats->mean_us = delta_sum / static_cast<double>(num_deltas);
  
    double sum_mean_offsets_squared = 0.0;
    for (size_t i = 0; i < num_deltas; ++i) {
      double offset = fabs(deltas[i] - stats->mean_us);
      sum_mean_offsets_squared += offset * offset;
    }
    stats->standard_deviation_us =
        sum_mean_offsets_squared / static_cast<double>(num_deltas - 1);
  
    return true;
  }
  
  bool FindFirstOf(const TraceEventVector& events,
                   const Query& query,
                   size_t position,
                   size_t* return_index) {
    CHECK(return_index);
    for (size_t i = position; i < events.size(); ++i) {
      if (query.Evaluate(*events.at(i))) {
        *return_index = i;
        return true;
      }
    }
    return false;
  }
  
  bool FindLastOf(const TraceEventVector& events,
                  const Query& query,
                  size_t position,
                  size_t* return_index) {
    CHECK(return_index);
    if (events.empty())
      return false;
    position = (position < events.size()) ? position : events.size() - 1;
    for (;;) {
      if (query.Evaluate(*events.at(position))) {
        *return_index = position;
        return true;
      }
      if (position == 0)
        return false;
      --position;
    }
    return false;
  }
  
  bool FindClosest(const TraceEventVector& events,
                   const Query& query,
                   size_t position,
                   size_t* return_closest,
                   size_t* return_second_closest) {
    CHECK(return_closest);
    if (events.empty() || position >= events.size())
      return false;
    size_t closest = events.size();
    size_t second_closest = events.size();
    for (size_t i = 0; i < events.size(); ++i) {
      if (!query.Evaluate(*events.at(i)))
        continue;
      if (closest == events.size()) {
        closest = i;
        continue;
      }
      if (fabs(events.at(i)->timestamp - events.at(position)->timestamp) <
          fabs(events.at(closest)->timestamp - events.at(position)->timestamp)) {
        second_closest = closest;
        closest = i;
      } else if (second_closest == events.size()) {
        second_closest = i;
      }
    }
  
    if (closest < events.size() &&
        (!return_second_closest || second_closest < events.size())) {
      *return_closest = closest;
      if (return_second_closest)
        *return_second_closest = second_closest;
      return true;
    }
  
    return false;
  }
  
  size_t CountMatches(const TraceEventVector& events,
                      const Query& query,
                      size_t begin_position,
                      size_t end_position) {
    if (begin_position >= events.size())
      return 0u;
    end_position = (end_position < events.size()) ? end_position : events.size();
    size_t count = 0u;
    for (size_t i = begin_position; i < end_position; ++i) {
      if (query.Evaluate(*events.at(i)))
        ++count;
    }
    return count;
  }
  
  }  // namespace trace_analyzer
  