Add searching features to new TraceEventVector class for tests.

Review URL: http://codereview.chromium.org/8900001

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@114504 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 335 insertions, 41 deletions

diff --git a/base/test/trace_event_analyzer.cc b/base/test/trace_event_analyzer.cc
index 183f29a..a60250a 100644
--- a/base/test/trace_event_analyzer.cc
+++ b/base/test/trace_event_analyzer.cc
@@ -615,7 +615,7 @@ namespace {
 // Search |events| for |query| and add matches to |output|.
 size_t FindMatchingEvents(const std::vector<TraceEvent>& events,
                           const Query& query,
-                          TraceAnalyzer::TraceEventVector* output) {
+                          TraceEventVector* output) {
   for (size_t i = 0; i < events.size(); ++i) {
     if (query.Evaluate(events[i]))
       output->push_back(&events[i]);
@@ -739,6 +739,19 @@ void TraceAnalyzer::AssociateEvents(const Query& first,
   }
 }
 
+void TraceAnalyzer::MergeAssociatedEventArgs() {
+  for (size_t i = 0; i < raw_events_.size(); ++i) {
+    if (raw_events_[i].other_event) {
+      raw_events_[i].arg_numbers.insert(
+          raw_events_[i].other_event->arg_numbers.begin(),
+          raw_events_[i].other_event->arg_numbers.end());
+      raw_events_[i].arg_strings.insert(
+          raw_events_[i].other_event->arg_strings.begin(),
+          raw_events_[i].other_event->arg_strings.end());
+    }
+  }
+}
+
 size_t TraceAnalyzer::FindEvents(const Query& query, TraceEventVector* output) {
   allow_assocation_changes_ = false;
   output->clear();
@@ -758,7 +771,24 @@ const std::string& TraceAnalyzer::GetThreadName(
   return thread_names_[thread];
 }
 
-bool TraceAnalyzer::GetRateStats(const TraceEventVector& events, Stats* stats) {
+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) {
+  CHECK(stats);
   // Need at least 3 events to calculate rate stats.
   if (events.size() < 3) {
     LOG(ERROR) << "Not enough events: " << events.size();
@@ -769,7 +799,7 @@ bool TraceAnalyzer::GetRateStats(const TraceEventVector& events, Stats* stats) {
   double delta_sum = 0.0;
   size_t num_deltas = events.size() - 1;
   for (size_t i = 0; i < num_deltas; ++i) {
-    double delta = events[i + 1]->timestamp - events[i]->timestamp;
+    double delta = events.at(i + 1)->timestamp - events.at(i)->timestamp;
     if (delta < 0.0) {
       LOG(ERROR) << "Events are out of order";
       return false;
@@ -793,18 +823,90 @@ bool TraceAnalyzer::GetRateStats(const TraceEventVector& events, Stats* stats) {
   return true;
 }
 
-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")
+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;
-    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;
+    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
diff --git a/base/test/trace_event_analyzer.h b/base/test/trace_event_analyzer.h
index 5e40a06..8f25cd8 100644
--- a/base/test/trace_event_analyzer.h
+++ b/base/test/trace_event_analyzer.h
@@ -170,6 +170,8 @@ struct TraceEvent {
   const TraceEvent* other_event;
 };
 
+typedef std::vector<const TraceEvent*> TraceEventVector;
+
 // Pass these values to Query to compare with the corresponding member of a
 // TraceEvent. Unless otherwise specfied, the usage is Query(ENUM_MEMBER).
 enum TraceEventMember {
@@ -418,15 +420,6 @@ class QueryNode : public base::RefCounted<QueryNode> {
 // TraceAnalyzer helps tests search for trace events.
 class TraceAnalyzer {
  public:
-  typedef std::vector<const TraceEvent*> TraceEventVector;
-
-  struct Stats {
-    double min_us;
-    double max_us;
-    double mean_us;
-    double standard_deviation_us;
-  };
-
   ~TraceAnalyzer();
 
   // Use trace events from JSON string generated by tracing API.
@@ -474,6 +467,10 @@ class TraceAnalyzer {
                        const Query& second,
                        const Query& match);
 
+  // For each event, copy its arguments to the other_event argument map. If
+  // argument name already exists, it will not be overwritten.
+  void MergeAssociatedEventArgs();
+
   // Find all events that match query and replace output vector.
   size_t FindEvents(const Query& query, TraceEventVector* output);
 
@@ -482,10 +479,6 @@ class TraceAnalyzer {
 
   const std::string& GetThreadName(const TraceEvent::ProcessThreadID& thread);
 
-  // Calculate min/max/mean and standard deviation from the times between
-  // adjacent events.
-  static bool GetRateStats(const TraceEventVector& events, Stats* stats);
-
  private:
   TraceAnalyzer();
 
@@ -501,6 +494,56 @@ class TraceAnalyzer {
   DISALLOW_COPY_AND_ASSIGN(TraceAnalyzer);
 };
 
+// Utility functions for TraceEventVector.
+
+struct RateStats {
+  double min_us;
+  double max_us;
+  double mean_us;
+  double standard_deviation_us;
+};
+
+// Calculate min/max/mean and standard deviation from the times between
+// adjacent events.
+bool GetRateStats(const TraceEventVector& events, RateStats* stats);
+
+// Starting from |position|, find the first event that matches |query|.
+// Returns true if found, false otherwise.
+bool FindFirstOf(const TraceEventVector& events,
+                 const Query& query,
+                 size_t position,
+                 size_t* return_index);
+
+// Starting from |position|, find the last event that matches |query|.
+// Returns true if found, false otherwise.
+bool FindLastOf(const TraceEventVector& events,
+                const Query& query,
+                size_t position,
+                size_t* return_index);
+
+// Find the closest events to |position| in time that match |query|.
+// return_second_closest may be NULL. Closeness is determined by comparing
+// with the event timestamp.
+// Returns true if found, false otherwise. If both return parameters are
+// requested, both must be found for a successful result.
+bool FindClosest(const TraceEventVector& events,
+                 const Query& query,
+                 size_t position,
+                 size_t* return_closest,
+                 size_t* return_second_closest);
+
+// Count matches, inclusive of |begin_position|, exclusive of |end_position|.
+size_t CountMatches(const TraceEventVector& events,
+                    const Query& query,
+                    size_t begin_position,
+                    size_t end_position);
+
+// Count all matches.
+static inline size_t CountMatches(const TraceEventVector& events,
+                                  const Query& query) {
+  return CountMatches(events, query, 0u, events.size());
+}
+
 }  // namespace trace_analyzer
 
 #endif  // BASE_TEST_TRACE_EVENT_ANALYZER_H_
diff --git a/base/test/trace_event_analyzer_unittest.cc b/base/test/trace_event_analyzer_unittest.cc
index 96f8045..602f139 100644
--- a/base/test/trace_event_analyzer_unittest.cc
+++ b/base/test/trace_event_analyzer_unittest.cc
@@ -65,7 +65,7 @@ TEST_F(TraceEventAnalyzerTest, NoEvents) {
   ASSERT_TRUE(analyzer.get());
 
   // Search for all events and verify that nothing is returned.
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
   analyzer->FindEvents(Query::Bool(true), &found);
   EXPECT_EQ(0u, found.size());
 }
@@ -221,7 +221,7 @@ TEST_F(TraceEventAnalyzerTest, BooleanOperators) {
       analyzer(TraceAnalyzer::Create(output_.json_output));
   ASSERT_TRUE(!!analyzer.get());
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
 
   // ==
 
@@ -308,7 +308,7 @@ TEST_F(TraceEventAnalyzerTest, ArithmeticOperators) {
       analyzer(TraceAnalyzer::Create(output_.json_output));
   ASSERT_TRUE(analyzer.get());
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
 
   // Verify that arithmetic operators function:
 
@@ -364,7 +364,7 @@ TEST_F(TraceEventAnalyzerTest, StringPattern) {
       analyzer(TraceAnalyzer::Create(output_.json_output));
   ASSERT_TRUE(analyzer.get());
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
 
   analyzer->FindEvents(Query(EVENT_NAME) == Query::Pattern("name?"), &found);
   ASSERT_EQ(2u, found.size());
@@ -410,7 +410,7 @@ TEST_F(TraceEventAnalyzerTest, Duration) {
   ASSERT_TRUE(analyzer.get());
   analyzer->AssociateBeginEndEvents();
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
   analyzer->FindEvents(Query::MatchBeginWithEnd() &&
                       Query(EVENT_DURATION) > Query::Int(duration_cutoff_us) &&
                       (Query(EVENT_CATEGORY) == Query::String("cat1") ||
@@ -440,12 +440,41 @@ TEST_F(TraceEventAnalyzerTest, BeginEndAssocations) {
   ASSERT_TRUE(analyzer.get());
   analyzer->AssociateBeginEndEvents();
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
   analyzer->FindEvents(Query::MatchBeginWithEnd(), &found);
   ASSERT_EQ(1u, found.size());
   EXPECT_STREQ("name2", found[0]->name.c_str());
 }
 
+// Test MergeAssociatedEventArgs
+TEST_F(TraceEventAnalyzerTest, MergeAssociatedEventArgs) {
+  using namespace trace_analyzer;
+  ManualSetUp();
+
+  const char* arg_string = "arg_string";
+  BeginTracing();
+  {
+    TRACE_EVENT1("cat1", "name1", "arg", arg_string);
+  }
+  EndTracing();
+
+  scoped_ptr<TraceAnalyzer>
+      analyzer(TraceAnalyzer::Create(output_.json_output));
+  ASSERT_TRUE(analyzer.get());
+  analyzer->AssociateBeginEndEvents();
+
+  TraceEventVector found;
+  analyzer->FindEvents(Query(EVENT_NAME) == Query::String("name1") &&
+      Query(EVENT_PHASE) == Query::Phase(TRACE_EVENT_PHASE_END), &found);
+  ASSERT_EQ(1u, found.size());
+  std::string arg_actual;
+  EXPECT_FALSE(found[0]->GetArgAsString("arg", &arg_actual));
+
+  analyzer->MergeAssociatedEventArgs();
+  EXPECT_TRUE(found[0]->GetArgAsString("arg", &arg_actual));
+  EXPECT_STREQ(arg_string, arg_actual.c_str());
+}
+
 // Test AssociateStartFinishEvents
 TEST_F(TraceEventAnalyzerTest, StartFinishAssocations) {
   using namespace trace_analyzer;
@@ -469,7 +498,7 @@ TEST_F(TraceEventAnalyzerTest, StartFinishAssocations) {
   ASSERT_TRUE(analyzer.get());
   analyzer->AssociateStartFinishEvents();
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
   analyzer->FindEvents(Query::MatchStartWithFinish(), &found);
   ASSERT_EQ(2u, found.size());
   EXPECT_STRCASEEQ("B", found[0]->id.c_str());
@@ -504,7 +533,7 @@ TEST_F(TraceEventAnalyzerTest, CustomAssociations) {
   Query match(Query(EVENT_ARG, "id") == Query(OTHER_ARG, "id"));
   analyzer->AssociateEvents(begin, end, match);
 
-  TraceAnalyzer::TraceEventVector found;
+  TraceEventVector found;
 
   // cat1 has no other_event.
   analyzer->FindEvents(Query(EVENT_CATEGORY) == Query::String("cat1") &&
@@ -570,12 +599,12 @@ TEST_F(TraceEventAnalyzerTest, RateStats) {
 
   std::vector<TraceEvent> events;
   events.reserve(100);
-  TraceAnalyzer::TraceEventVector event_ptrs;
+  TraceEventVector event_ptrs;
   TraceEvent event;
   event.timestamp = 0.0;
   double little_delta = 1.0;
   double big_delta = 10.0;
-  TraceAnalyzer::Stats stats;
+  RateStats stats;
 
   for (int i = 0; i < 10; ++i) {
     event.timestamp += little_delta;
@@ -583,7 +612,7 @@ TEST_F(TraceEventAnalyzerTest, RateStats) {
     event_ptrs.push_back(&events.back());
   }
 
-  ASSERT_TRUE(TraceAnalyzer::GetRateStats(event_ptrs, &stats));
+  ASSERT_TRUE(GetRateStats(event_ptrs, &stats));
   EXPECT_EQ(little_delta, stats.mean_us);
   EXPECT_EQ(little_delta, stats.min_us);
   EXPECT_EQ(little_delta, stats.max_us);
@@ -593,18 +622,138 @@ TEST_F(TraceEventAnalyzerTest, RateStats) {
   events.push_back(event);
   event_ptrs.push_back(&events.back());
 
-  ASSERT_TRUE(TraceAnalyzer::GetRateStats(event_ptrs, &stats));
+  ASSERT_TRUE(GetRateStats(event_ptrs, &stats));
   EXPECT_LT(little_delta, stats.mean_us);
   EXPECT_EQ(little_delta, stats.min_us);
   EXPECT_EQ(big_delta, stats.max_us);
   EXPECT_LT(0.0, stats.standard_deviation_us);
 
-  TraceAnalyzer::TraceEventVector few_event_ptrs;
+  TraceEventVector few_event_ptrs;
   few_event_ptrs.push_back(&event);
   few_event_ptrs.push_back(&event);
-  ASSERT_FALSE(TraceAnalyzer::GetRateStats(few_event_ptrs, &stats));
+  ASSERT_FALSE(GetRateStats(few_event_ptrs, &stats));
   few_event_ptrs.push_back(&event);
-  ASSERT_TRUE(TraceAnalyzer::GetRateStats(few_event_ptrs, &stats));
+  ASSERT_TRUE(GetRateStats(few_event_ptrs, &stats));
+}
+
+// Test FindFirstOf and FindLastOf.
+TEST_F(TraceEventAnalyzerTest, FindOf) {
+  using namespace trace_analyzer;
+
+  size_t num_events = 100;
+  size_t index = 0;
+  TraceEventVector event_ptrs;
+  EXPECT_FALSE(FindFirstOf(event_ptrs, Query::Bool(true), 0, &index));
+  EXPECT_FALSE(FindFirstOf(event_ptrs, Query::Bool(true), 10, &index));
+  EXPECT_FALSE(FindLastOf(event_ptrs, Query::Bool(true), 0, &index));
+  EXPECT_FALSE(FindLastOf(event_ptrs, Query::Bool(true), 10, &index));
+
+  std::vector<TraceEvent> events;
+  events.resize(num_events);
+  for (size_t i = 0; i < events.size(); ++i)
+    event_ptrs.push_back(&events[i]);
+  size_t bam_index = num_events/2;
+  events[bam_index].name = "bam";
+  Query query_bam = Query(EVENT_NAME) == Query::String(events[bam_index].name);
+
+  // FindFirstOf
+  EXPECT_FALSE(FindFirstOf(event_ptrs, Query::Bool(false), 0, &index));
+  EXPECT_TRUE(FindFirstOf(event_ptrs, Query::Bool(true), 0, &index));
+  EXPECT_EQ(0u, index);
+  EXPECT_TRUE(FindFirstOf(event_ptrs, Query::Bool(true), 5, &index));
+  EXPECT_EQ(5u, index);
+
+  EXPECT_FALSE(FindFirstOf(event_ptrs, query_bam, bam_index + 1, &index));
+  EXPECT_TRUE(FindFirstOf(event_ptrs, query_bam, 0, &index));
+  EXPECT_EQ(bam_index, index);
+  EXPECT_TRUE(FindFirstOf(event_ptrs, query_bam, bam_index, &index));
+  EXPECT_EQ(bam_index, index);
+
+  // FindLastOf
+  EXPECT_FALSE(FindLastOf(event_ptrs, Query::Bool(false), 1000, &index));
+  EXPECT_TRUE(FindLastOf(event_ptrs, Query::Bool(true), 1000, &index));
+  EXPECT_EQ(num_events - 1, index);
+  EXPECT_TRUE(FindLastOf(event_ptrs, Query::Bool(true), num_events - 5,
+                         &index));
+  EXPECT_EQ(num_events - 5, index);
+
+  EXPECT_FALSE(FindLastOf(event_ptrs, query_bam, bam_index - 1, &index));
+  EXPECT_TRUE(FindLastOf(event_ptrs, query_bam, num_events, &index));
+  EXPECT_EQ(bam_index, index);
+  EXPECT_TRUE(FindLastOf(event_ptrs, query_bam, bam_index, &index));
+  EXPECT_EQ(bam_index, index);
+}
+
+// Test FindClosest.
+TEST_F(TraceEventAnalyzerTest, FindClosest) {
+  using namespace trace_analyzer;
+
+  size_t index_1 = 0;
+  size_t index_2 = 0;
+  TraceEventVector event_ptrs;
+  EXPECT_FALSE(FindClosest(event_ptrs, Query::Bool(true), 0,
+                           &index_1, &index_2));
+
+  size_t num_events = 5;
+  std::vector<TraceEvent> events;
+  events.resize(num_events);
+  for (size_t i = 0; i < events.size(); ++i) {
+    // timestamps go up exponentially so the lower index is always closer in
+    // time than the higher index.
+    events[i].timestamp = static_cast<double>(i) * static_cast<double>(i);
+    event_ptrs.push_back(&events[i]);
+  }
+  events[0].name = "one";
+  events[2].name = "two";
+  events[4].name = "three";
+  Query query_named = Query(EVENT_NAME) != Query::String("");
+  Query query_one = Query(EVENT_NAME) == Query::String("one");
+
+  // Only one event matches query_one, so two closest can't be found.
+  EXPECT_FALSE(FindClosest(event_ptrs, query_one, 0, &index_1, &index_2));
+
+  EXPECT_TRUE(FindClosest(event_ptrs, query_one, 3, &index_1, NULL));
+  EXPECT_EQ(0u, index_1);
+
+  EXPECT_TRUE(FindClosest(event_ptrs, query_named, 1, &index_1, &index_2));
+  EXPECT_EQ(0u, index_1);
+  EXPECT_EQ(2u, index_2);
+
+  EXPECT_TRUE(FindClosest(event_ptrs, query_named, 4, &index_1, &index_2));
+  EXPECT_EQ(4u, index_1);
+  EXPECT_EQ(2u, index_2);
+
+  EXPECT_TRUE(FindClosest(event_ptrs, query_named, 3, &index_1, &index_2));
+  EXPECT_EQ(2u, index_1);
+  EXPECT_EQ(0u, index_2);
+}
+
+// Test CountMatches.
+TEST_F(TraceEventAnalyzerTest, CountMatches) {
+  using namespace trace_analyzer;
+
+  TraceEventVector event_ptrs;
+  EXPECT_EQ(0u, CountMatches(event_ptrs, Query::Bool(true), 0, 10));
+
+  size_t num_events = 5;
+  size_t num_named = 3;
+  std::vector<TraceEvent> events;
+  events.resize(num_events);
+  for (size_t i = 0; i < events.size(); ++i)
+    event_ptrs.push_back(&events[i]);
+  events[0].name = "one";
+  events[2].name = "two";
+  events[4].name = "three";
+  Query query_named = Query(EVENT_NAME) != Query::String("");
+  Query query_one = Query(EVENT_NAME) == Query::String("one");
+
+  EXPECT_EQ(0u, CountMatches(event_ptrs, Query::Bool(false)));
+  EXPECT_EQ(num_events, CountMatches(event_ptrs, Query::Bool(true)));
+  EXPECT_EQ(num_events - 1, CountMatches(event_ptrs, Query::Bool(true),
+                                         1, num_events));
+  EXPECT_EQ(1u, CountMatches(event_ptrs, query_one));
+  EXPECT_EQ(num_events - 1, CountMatches(event_ptrs, !query_one));
+  EXPECT_EQ(num_named, CountMatches(event_ptrs, query_named));
 }