// 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),
      duration(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 may_have_duration = (phase == TRACE_EVENT_PHASE_COMPLETE);
  bool require_origin = (phase != TRACE_EVENT_PHASE_METADATA);
  bool require_id = (phase == TRACE_EVENT_PHASE_ASYNC_BEGIN ||
                     phase == TRACE_EVENT_PHASE_ASYNC_STEP_INTO ||
                     phase == TRACE_EVENT_PHASE_ASYNC_STEP_PAST ||
                     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 (may_have_duration) {
    dictionary->GetDouble("dur", &duration);
  }
  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.
  for (base::DictionaryValue::Iterator it(*args); !it.IsAtEnd();
       it.Advance()) {
    std::string str;
    bool boolean = false;
    int int_num = 0;
    double double_num = 0.0;
    if (it.value().GetAsString(&str))
      arg_strings[it.key()] = str;
    else if (it.value().GetAsInteger(&int_num))
      arg_numbers[it.key()] = static_cast<double>(int_num);
    else if (it.value().GetAsBoolean(&boolean))
      arg_numbers[it.key()] = static_cast<double>(boolean ? 1 : 0);
    else if (it.value().GetAsDouble(&double_num))
      arg_numbers[it.key()] = double_num;
    else {
      LOG(WARNING) << "Value type of argument is not supported: " <<
          static_cast<int>(it.value().GetType());
      continue;  // Skip non-supported arguments.
    }
  }

  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 std::string();
}

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_COMPLETE_DURATION:
      if (the_event->phase == TRACE_EVENT_PHASE_COMPLETE) {
        *num = the_event->duration;
        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));

  base::ListValue* root_list = NULL;
  if (!root.get() || !root->GetAsList(&root_list))
    return false;

  for (size_t i = 0; i < root_list->GetSize(); ++i) {
    base::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_INTO) ||
      Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_PAST));
  Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_END) ||
            Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_INTO) ||
            Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_PAST));
  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 =
      sqrt(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