tracked_objects.cc revision c407dc5cd9bdc5668497f21b26b09d988ab439de 
1// Copyright (c) 2006-2008 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/tracked_objects.h"
6
7#include <math.h>
8
9#include "base/format_macros.h"
10#include "base/message_loop.h"
11#include "base/string_util.h"
12
13using base::TimeDelta;
14
15namespace tracked_objects {
16
17// A TLS slot to the TrackRegistry for the current thread.
18// static
19TLSSlot ThreadData::tls_index_(base::LINKER_INITIALIZED);
20
21// A global state variable to prevent repeated initialization during tests.
22// static
23AutoTracking::State AutoTracking::state_ = AutoTracking::kNeverBeenRun;
24
25//------------------------------------------------------------------------------
26// Death data tallies durations when a death takes place.
27
28void DeathData::RecordDeath(const TimeDelta& duration) {
29  ++count_;
30  life_duration_ += duration;
31  int64 milliseconds = duration.InMilliseconds();
32  square_duration_ += milliseconds * milliseconds;
33}
34
35int DeathData::AverageMsDuration() const {
36  return static_cast<int>(life_duration_.InMilliseconds() / count_);
37}
38
39double DeathData::StandardDeviation() const {
40  double average = AverageMsDuration();
41  double variance = static_cast<float>(square_duration_)/count_
42                    - average * average;
43  return sqrt(variance);
44}
45
46
47void DeathData::AddDeathData(const DeathData& other) {
48  count_ += other.count_;
49  life_duration_ += other.life_duration_;
50  square_duration_ += other.square_duration_;
51}
52
53void DeathData::Write(std::string* output) const {
54  if (!count_)
55    return;
56  if (1 == count_)
57    StringAppendF(output, "(1)Life in %dms ", AverageMsDuration());
58  else
59    StringAppendF(output, "(%d)Lives %dms/life ", count_, AverageMsDuration());
60}
61
62void DeathData::Clear() {
63  count_ = 0;
64  life_duration_ = TimeDelta();
65  square_duration_ = 0;
66}
67
68//------------------------------------------------------------------------------
69BirthOnThread::BirthOnThread(const Location& location)
70    : location_(location),
71      birth_thread_(ThreadData::current()) { }
72
73//------------------------------------------------------------------------------
74Births::Births(const Location& location)
75    : BirthOnThread(location),
76      birth_count_(1) { }
77
78//------------------------------------------------------------------------------
79// ThreadData maintains the central data for all births and death.
80
81// static
82ThreadData* ThreadData::first_ = NULL;
83// static
84Lock ThreadData::list_lock_;
85
86// static
87ThreadData::Status ThreadData::status_ = ThreadData::UNINITIALIZED;
88
89ThreadData::ThreadData() : next_(NULL), message_loop_(MessageLoop::current()) {}
90
91// static
92ThreadData* ThreadData::current() {
93  if (!tls_index_.initialized())
94    return NULL;
95
96  ThreadData* registry = static_cast<ThreadData*>(tls_index_.Get());
97  if (!registry) {
98    // We have to create a new registry for ThreadData.
99    bool too_late_to_create = false;
100    {
101      registry = new ThreadData;
102      AutoLock lock(list_lock_);
103      // Use lock to insure we have most recent status.
104      if (!IsActive()) {
105        too_late_to_create = true;
106      } else {
107        // Use lock to insert into list.
108        registry->next_ = first_;
109        first_ = registry;
110      }
111    }  // Release lock.
112    if (too_late_to_create) {
113      delete registry;
114      registry = NULL;
115    } else {
116      tls_index_.Set(registry);
117    }
118  }
119  return registry;
120}
121
122// Do mininimal fixups for searching function names.
123static std::string UnescapeQuery(const std::string& query) {
124  std::string result;
125  for (size_t i = 0; i < query.size(); i++) {
126    char next = query[i];
127    if ('%' == next && i + 2 < query.size()) {
128      std::string hex = query.substr(i + 1, 2);
129      char replacement = '\0';
130      // Only bother with "<", ">", and " ".
131      if (LowerCaseEqualsASCII(hex, "3c"))
132        replacement ='<';
133      else if (LowerCaseEqualsASCII(hex, "3e"))
134        replacement = '>';
135      else if (hex == "20")
136        replacement = ' ';
137      if (replacement) {
138        next = replacement;
139        i += 2;
140      }
141    }
142    result.push_back(next);
143  }
144  return result;
145}
146
147// static
148void ThreadData::WriteHTML(const std::string& query, std::string* output) {
149  if (!ThreadData::IsActive())
150    return;  // Not yet initialized.
151
152  DCHECK(ThreadData::current());
153
154  output->append("<html><head><title>About Objects");
155  std::string escaped_query = UnescapeQuery(query);
156  if (!escaped_query.empty())
157    output->append(" - " + escaped_query);
158  output->append("</title></head><body><pre>");
159
160  DataCollector collected_data;  // Gather data.
161  collected_data.AddListOfLivingObjects();  // Add births that are still alive.
162
163  // Data Gathering is complete. Now to sort/process/render.
164  DataCollector::Collection* collection = collected_data.collection();
165
166  // Create filtering and sort comparison object.
167  Comparator comparator;
168  comparator.ParseQuery(escaped_query);
169
170  // Filter out acceptable (matching) instances.
171  DataCollector::Collection match_array;
172  for (DataCollector::Collection::iterator it = collection->begin();
173       it != collection->end(); ++it) {
174    if (comparator.Acceptable(*it))
175      match_array.push_back(*it);
176  }
177
178  comparator.Sort(&match_array);
179
180  WriteHTMLTotalAndSubtotals(match_array, comparator, output);
181
182  comparator.Clear();  // Delete tiebreaker_ instances.
183
184  output->append("</pre>");
185
186  const char* help_string = "The following are the keywords that can be used to"
187    "sort and aggregate the data, or to select data.<br><ul>"
188    "<li><b>count</b> Number of instances seen."
189    "<li><b>duration</b> Duration in ms from construction to descrution."
190    "<li><b>birth</b> Thread on which the task was constructed."
191    "<li><b>death</b> Thread on which the task was run and deleted."
192    "<li><b>file</b> File in which the task was contructed."
193    "<li><b>function</b> Function in which the task was constructed."
194    "<li><b>line</b> Line number of the file in which the task was constructed."
195    "</ul><br>"
196    "As examples:<ul>"
197    "<li><b>about:tasks/file</b> would sort the above data by file, and"
198    " aggregate data on a per-file basis."
199    "<li><b>about:tasks/file=Dns</b> would only list data for tasks constructed"
200    " in a file containing the text |Dns|."
201    "<li><b>about:tasks/birth/death</b> would sort the above list by birth"
202    " thread, and then by death thread, and would aggregate data for each pair"
203    " of lifetime events."
204    "</ul>"
205    " The data can be reset to zero (discarding all births, deaths, etc.) using"
206    " <b>about:tasks/reset</b>. The existing stats will be displayed, but the"
207    " internal stats will be set to zero, and start accumulating afresh. This"
208    " option is very helpful if you only wish to consider tasks created after"
209    " some point in time.<br><br>"
210    "If you wish to monitor Renderer events, be sure to run in --single-process"
211    " mode.";
212  output->append(help_string);
213  output->append("</body></html>");
214}
215
216// static
217void ThreadData::WriteHTMLTotalAndSubtotals(
218    const DataCollector::Collection& match_array,
219    const Comparator& comparator,
220    std::string* output) {
221  if (!match_array.size()) {
222    output->append("There were no tracked matches.");
223  } else {
224    // Aggregate during printing
225    Aggregation totals;
226    for (size_t i = 0; i < match_array.size(); ++i) {
227      totals.AddDeathSnapshot(match_array[i]);
228    }
229    output->append("Aggregate Stats: ");
230    totals.Write(output);
231    output->append("<hr><hr>");
232
233    Aggregation subtotals;
234    for (size_t i = 0; i < match_array.size(); ++i) {
235      if (0 == i || !comparator.Equivalent(match_array[i - 1],
236                                           match_array[i])) {
237        // Print group's defining characteristics.
238        comparator.WriteSortGrouping(match_array[i], output);
239        output->append("<br><br>");
240      }
241      comparator.WriteSnapshot(match_array[i], output);
242      output->append("<br>");
243      subtotals.AddDeathSnapshot(match_array[i]);
244      if (i + 1 >= match_array.size() ||
245          !comparator.Equivalent(match_array[i],
246                                 match_array[i + 1])) {
247        // Print aggregate stats for the group.
248        output->append("<br>");
249        subtotals.Write(output);
250        output->append("<br><hr><br>");
251        subtotals.Clear();
252      }
253    }
254  }
255}
256
257Births* ThreadData::TallyABirth(const Location& location) {
258  if (!message_loop_)  // In case message loop wasn't yet around...
259    message_loop_ = MessageLoop::current();  // Find it now.
260
261  BirthMap::iterator it = birth_map_.find(location);
262  if (it != birth_map_.end()) {
263    it->second->RecordBirth();
264    return it->second;
265  }
266
267  Births* tracker = new Births(location);
268  // Lock since the map may get relocated now, and other threads sometimes
269  // snapshot it (but they lock before copying it).
270  AutoLock lock(lock_);
271  birth_map_[location] = tracker;
272  return tracker;
273}
274
275void ThreadData::TallyADeath(const Births& lifetimes,
276                             const TimeDelta& duration) {
277  if (!message_loop_)  // In case message loop wasn't yet around...
278    message_loop_ = MessageLoop::current();  // Find it now.
279
280  DeathMap::iterator it = death_map_.find(&lifetimes);
281  if (it != death_map_.end()) {
282    it->second.RecordDeath(duration);
283    return;
284  }
285
286  AutoLock lock(lock_);  // Lock since the map may get relocated now.
287  death_map_[&lifetimes].RecordDeath(duration);
288}
289
290// static
291ThreadData* ThreadData::first() {
292  AutoLock lock(list_lock_);
293  return first_;
294}
295
296const std::string ThreadData::ThreadName() const {
297  if (message_loop_)
298    return message_loop_->thread_name();
299  return "ThreadWithoutMessageLoop";
300}
301
302// This may be called from another thread.
303void ThreadData::SnapshotBirthMap(BirthMap *output) const {
304  AutoLock lock(lock_);
305  for (BirthMap::const_iterator it = birth_map_.begin();
306       it != birth_map_.end(); ++it)
307    (*output)[it->first] = it->second;
308}
309
310// This may be called from another thread.
311void ThreadData::SnapshotDeathMap(DeathMap *output) const {
312  AutoLock lock(lock_);
313  for (DeathMap::const_iterator it = death_map_.begin();
314       it != death_map_.end(); ++it)
315    (*output)[it->first] = it->second;
316}
317
318// static
319void ThreadData::ResetAllThreadData() {
320  ThreadData* my_list = ThreadData::current()->first();
321
322  for (ThreadData* thread_data = my_list;
323       thread_data;
324       thread_data = thread_data->next())
325    thread_data->Reset();
326}
327
328void ThreadData::Reset() {
329  AutoLock lock(lock_);
330  for (DeathMap::iterator it = death_map_.begin();
331       it != death_map_.end(); ++it)
332    it->second.Clear();
333  for (BirthMap::iterator it = birth_map_.begin();
334       it != birth_map_.end(); ++it)
335    it->second->Clear();
336}
337
338#ifdef OS_WIN
339// TODO(jar): This should use condition variables, and be cross platform.
340void ThreadData::RunOnAllThreads(void (*function)()) {
341  ThreadData* list = first();  // Get existing list.
342
343  std::vector<MessageLoop*> message_loops;
344  for (ThreadData* it = list; it; it = it->next()) {
345    if (current() != it && it->message_loop())
346      message_loops.push_back(it->message_loop());
347  }
348
349  ThreadSafeDownCounter* counter =
350    new ThreadSafeDownCounter(message_loops.size() + 1);  // Extra one for us!
351
352  HANDLE completion_handle = CreateEvent(NULL, false, false, NULL);
353  // Tell all other threads to run.
354  for (size_t i = 0; i < message_loops.size(); ++i)
355    message_loops[i]->PostTask(
356        FROM_HERE, new RunTheStatic(function, completion_handle, counter));
357
358  // Also run Task on our thread.
359  RunTheStatic local_task(function, completion_handle, counter);
360  local_task.Run();
361
362  WaitForSingleObject(completion_handle, INFINITE);
363  int ret_val = CloseHandle(completion_handle);
364  DCHECK(ret_val);
365}
366#endif
367
368// static
369bool ThreadData::StartTracking(bool status) {
370#ifndef TRACK_ALL_TASK_OBJECTS
371  return false;  // Not compiled in.
372#endif
373
374  if (!status) {
375    AutoLock lock(list_lock_);
376    DCHECK(status_ == ACTIVE || status_ == SHUTDOWN);
377    status_ = SHUTDOWN;
378    return true;
379  }
380  AutoLock lock(list_lock_);
381  DCHECK(status_ == UNINITIALIZED);
382  CHECK(tls_index_.Initialize(NULL));
383  status_ = ACTIVE;
384  return true;
385}
386
387// static
388bool ThreadData::IsActive() {
389  return status_ == ACTIVE;
390}
391
392#ifdef OS_WIN
393// static
394void ThreadData::ShutdownMultiThreadTracking() {
395  // Using lock, guarantee that no new ThreadData instances will be created.
396  if (!StartTracking(false))
397    return;
398
399  RunOnAllThreads(ShutdownDisablingFurtherTracking);
400
401  // Now the *only* threads that might change the database are the threads with
402  // no messages loops.  They might still be adding data to their birth records,
403  // but since no objects are deleted on those threads, there will be no further
404  // access to to cross-thread data.
405  // We could do a cleanup on all threads except for the ones without
406  // MessageLoops, but we won't bother doing cleanup (destruction of data) yet.
407  return;
408}
409#endif
410
411// static
412void ThreadData::ShutdownSingleThreadedCleanup() {
413  // We must be single threaded... but be careful anyway.
414  if (!StartTracking(false))
415    return;
416  ThreadData* thread_data_list;
417  {
418    AutoLock lock(list_lock_);
419    thread_data_list = first_;
420    first_ = NULL;
421  }
422
423  while (thread_data_list) {
424    ThreadData* next_thread_data = thread_data_list;
425    thread_data_list = thread_data_list->next();
426
427    for (BirthMap::iterator it = next_thread_data->birth_map_.begin();
428         next_thread_data->birth_map_.end() != it; ++it)
429      delete it->second;  // Delete the Birth Records.
430    next_thread_data->birth_map_.clear();
431    next_thread_data->death_map_.clear();
432    delete next_thread_data;  // Includes all Death Records.
433  }
434
435  CHECK(tls_index_.initialized());
436  tls_index_.Free();
437  DCHECK(!tls_index_.initialized());
438  status_ = UNINITIALIZED;
439}
440
441// static
442void ThreadData::ShutdownDisablingFurtherTracking() {
443  // Redundantly set status SHUTDOWN on this thread.
444  if (!StartTracking(false))
445    return;
446}
447
448
449//------------------------------------------------------------------------------
450
451ThreadData::ThreadSafeDownCounter::ThreadSafeDownCounter(size_t count)
452    : remaining_count_(count) {
453  DCHECK_GT(remaining_count_, 0u);
454}
455
456bool ThreadData::ThreadSafeDownCounter::LastCaller() {
457  {
458    AutoLock lock(lock_);
459    if (--remaining_count_)
460      return false;
461  }  // Release lock, so we can delete everything in this instance.
462  delete this;
463  return true;
464}
465
466//------------------------------------------------------------------------------
467#ifdef OS_WIN
468ThreadData::RunTheStatic::RunTheStatic(FunctionPointer function,
469                                       HANDLE completion_handle,
470                                       ThreadSafeDownCounter* counter)
471    : function_(function),
472      completion_handle_(completion_handle),
473      counter_(counter) {
474}
475
476void ThreadData::RunTheStatic::Run() {
477  function_();
478  if (counter_->LastCaller())
479    SetEvent(completion_handle_);
480}
481#endif
482
483//------------------------------------------------------------------------------
484// Individual 3-tuple of birth (place and thread) along with death thread, and
485// the accumulated stats for instances (DeathData).
486
487Snapshot::Snapshot(const BirthOnThread& birth_on_thread,
488                   const ThreadData& death_thread,
489                   const DeathData& death_data)
490    : birth_(&birth_on_thread),
491      death_thread_(&death_thread),
492      death_data_(death_data) {
493}
494
495Snapshot::Snapshot(const BirthOnThread& birth_on_thread, int count)
496    : birth_(&birth_on_thread),
497      death_thread_(NULL),
498      death_data_(DeathData(count)) {
499}
500
501const std::string Snapshot::DeathThreadName() const {
502  if (death_thread_)
503    return death_thread_->ThreadName();
504  return "Still_Alive";
505}
506
507void Snapshot::Write(std::string* output) const {
508  death_data_.Write(output);
509  StringAppendF(output, "%s->%s ",
510                birth_->birth_thread()->ThreadName().c_str(),
511                death_thread_->ThreadName().c_str());
512  birth_->location().Write(true, true, output);
513}
514
515void Snapshot::Add(const Snapshot& other) {
516  death_data_.AddDeathData(other.death_data_);
517}
518
519//------------------------------------------------------------------------------
520// DataCollector
521
522DataCollector::DataCollector() {
523  DCHECK(ThreadData::IsActive());
524
525  // Get an unchanging copy of a ThreadData list.
526  ThreadData* my_list = ThreadData::current()->first();
527
528  count_of_contributing_threads_ = 0;
529  for (ThreadData* thread_data = my_list;
530       thread_data;
531       thread_data = thread_data->next()) {
532    ++count_of_contributing_threads_;
533  }
534
535  // Gather data serially.  A different constructor could be used to do in
536  // parallel, and then invoke an OnCompletion task.
537  // This hackish approach *can* get some slighly corrupt tallies, as we are
538  // grabbing values without the protection of a lock, but it has the advantage
539  // of working even with threads that don't have message loops.  If a user
540  // sees any strangeness, they can always just run their stats gathering a
541  // second time.
542  // TODO(jar): Provide version that gathers stats safely via PostTask in all
543  // cases where thread_data supplies a message_loop to post to.  Be careful to
544  // handle message_loops that are destroyed!?!
545  for (ThreadData* thread_data = my_list;
546       thread_data;
547       thread_data = thread_data->next()) {
548    Append(*thread_data);
549  }
550}
551
552void DataCollector::Append(const ThreadData& thread_data) {
553  // Get copy of data (which is done under ThreadData's lock).
554  ThreadData::BirthMap birth_map;
555  thread_data.SnapshotBirthMap(&birth_map);
556  ThreadData::DeathMap death_map;
557  thread_data.SnapshotDeathMap(&death_map);
558
559  // Use our lock to protect our accumulation activity.
560  AutoLock lock(accumulation_lock_);
561
562  DCHECK(count_of_contributing_threads_);
563
564  for (ThreadData::DeathMap::const_iterator it = death_map.begin();
565       it != death_map.end(); ++it) {
566    collection_.push_back(Snapshot(*it->first, thread_data, it->second));
567    global_birth_count_[it->first] -= it->first->birth_count();
568  }
569
570  for (ThreadData::BirthMap::const_iterator it = birth_map.begin();
571       it != birth_map.end(); ++it) {
572    global_birth_count_[it->second] += it->second->birth_count();
573  }
574
575  --count_of_contributing_threads_;
576}
577
578DataCollector::Collection* DataCollector::collection() {
579  DCHECK(!count_of_contributing_threads_);
580  return &collection_;
581}
582
583void DataCollector::AddListOfLivingObjects() {
584  DCHECK(!count_of_contributing_threads_);
585  for (BirthCount::iterator it = global_birth_count_.begin();
586       it != global_birth_count_.end(); ++it) {
587    if (it->second > 0)
588      collection_.push_back(Snapshot(*it->first, it->second));
589  }
590}
591
592//------------------------------------------------------------------------------
593// Aggregation
594
595void Aggregation::AddDeathSnapshot(const Snapshot& snapshot) {
596  AddBirth(snapshot.birth());
597  death_threads_[snapshot.death_thread()]++;
598  AddDeathData(snapshot.death_data());
599}
600
601void Aggregation::AddBirths(const Births& births) {
602  AddBirth(births);
603  birth_count_ += births.birth_count();
604}
605void Aggregation::AddBirth(const BirthOnThread& birth) {
606  AddBirthPlace(birth.location());
607  birth_threads_[birth.birth_thread()]++;
608}
609
610void Aggregation::AddBirthPlace(const Location& location) {
611  locations_[location]++;
612  birth_files_[location.file_name()]++;
613}
614
615void Aggregation::Write(std::string* output) const {
616  if (locations_.size() == 1) {
617    locations_.begin()->first.Write(true, true, output);
618  } else {
619    StringAppendF(output, "%" PRIuS " Locations. ", locations_.size());
620    if (birth_files_.size() > 1)
621      StringAppendF(output, "%" PRIuS " Files. ", birth_files_.size());
622    else
623      StringAppendF(output, "All born in %s. ",
624                    birth_files_.begin()->first.c_str());
625  }
626
627  if (birth_threads_.size() > 1)
628    StringAppendF(output, "%" PRIuS " BirthingThreads. ",
629                  birth_threads_.size());
630  else
631    StringAppendF(output, "All born on %s. ",
632                  birth_threads_.begin()->first->ThreadName().c_str());
633
634  if (death_threads_.size() > 1) {
635    StringAppendF(output, "%" PRIuS " DeathThreads. ", death_threads_.size());
636  } else {
637    if (death_threads_.begin()->first)
638      StringAppendF(output, "All deleted on %s. ",
639                  death_threads_.begin()->first->ThreadName().c_str());
640    else
641      output->append("All these objects are still alive.");
642  }
643
644  if (birth_count_ > 1)
645    StringAppendF(output, "Births=%d ", birth_count_);
646
647  DeathData::Write(output);
648}
649
650void Aggregation::Clear() {
651  birth_count_ = 0;
652  birth_files_.clear();
653  locations_.clear();
654  birth_threads_.clear();
655  DeathData::Clear();
656  death_threads_.clear();
657}
658
659//------------------------------------------------------------------------------
660// Comparison object for sorting.
661
662Comparator::Comparator()
663    : selector_(NIL),
664      tiebreaker_(NULL),
665      combined_selectors_(0),
666      use_tiebreaker_for_sort_only_(false) {}
667
668void Comparator::Clear() {
669  if (tiebreaker_) {
670    tiebreaker_->Clear();
671    delete tiebreaker_;
672    tiebreaker_ = NULL;
673  }
674  use_tiebreaker_for_sort_only_ = false;
675  selector_ = NIL;
676}
677
678void Comparator::Sort(DataCollector::Collection* collection) const {
679  std::sort(collection->begin(), collection->end(), *this);
680}
681
682
683bool Comparator::operator()(const Snapshot& left,
684                            const Snapshot& right) const {
685  switch (selector_) {
686    case BIRTH_THREAD:
687      if (left.birth_thread() != right.birth_thread() &&
688          left.birth_thread()->ThreadName() !=
689          right.birth_thread()->ThreadName())
690        return left.birth_thread()->ThreadName() <
691            right.birth_thread()->ThreadName();
692      break;
693
694    case DEATH_THREAD:
695      if (left.death_thread() != right.death_thread() &&
696          left.DeathThreadName() !=
697          right.DeathThreadName()) {
698        if (!left.death_thread())
699          return true;
700        if (!right.death_thread())
701          return false;
702        return left.DeathThreadName() <
703             right.DeathThreadName();
704      }
705      break;
706
707    case BIRTH_FILE:
708      if (left.location().file_name() != right.location().file_name()) {
709        int comp = strcmp(left.location().file_name(),
710                          right.location().file_name());
711        if (comp)
712          return 0 > comp;
713      }
714      break;
715
716    case BIRTH_FUNCTION:
717      if (left.location().function_name() != right.location().function_name()) {
718        int comp = strcmp(left.location().function_name(),
719                          right.location().function_name());
720        if (comp)
721          return 0 > comp;
722      }
723      break;
724
725    case BIRTH_LINE:
726      if (left.location().line_number() != right.location().line_number())
727        return left.location().line_number() <
728            right.location().line_number();
729      break;
730
731    case COUNT:
732      if (left.count() != right.count())
733        return left.count() > right.count();  // Sort large at front of vector.
734      break;
735
736    case AVERAGE_DURATION:
737      if (!left.count() || !right.count())
738        break;
739      if (left.AverageMsDuration() != right.AverageMsDuration())
740        return left.AverageMsDuration() > right.AverageMsDuration();
741      break;
742
743    default:
744      break;
745  }
746  if (tiebreaker_)
747    return tiebreaker_->operator()(left, right);
748  return false;
749}
750
751bool Comparator::Equivalent(const Snapshot& left,
752                            const Snapshot& right) const {
753  switch (selector_) {
754    case BIRTH_THREAD:
755      if (left.birth_thread() != right.birth_thread() &&
756          left.birth_thread()->ThreadName() !=
757              right.birth_thread()->ThreadName())
758        return false;
759      break;
760
761    case DEATH_THREAD:
762      if (left.death_thread() != right.death_thread() &&
763          left.DeathThreadName() != right.DeathThreadName())
764        return false;
765      break;
766
767    case BIRTH_FILE:
768      if (left.location().file_name() != right.location().file_name()) {
769        int comp = strcmp(left.location().file_name(),
770                          right.location().file_name());
771        if (comp)
772          return false;
773      }
774      break;
775
776    case BIRTH_FUNCTION:
777      if (left.location().function_name() != right.location().function_name()) {
778        int comp = strcmp(left.location().function_name(),
779                          right.location().function_name());
780        if (comp)
781          return false;
782      }
783      break;
784
785    case COUNT:
786      if (left.count() != right.count())
787        return false;
788      break;
789
790    case AVERAGE_DURATION:
791      if (left.life_duration() != right.life_duration())
792        return false;
793      break;
794
795    default:
796      break;
797  }
798  if (tiebreaker_ && !use_tiebreaker_for_sort_only_)
799    return tiebreaker_->Equivalent(left, right);
800  return true;
801}
802
803bool Comparator::Acceptable(const Snapshot& sample) const {
804  if (required_.size()) {
805    switch (selector_) {
806      case BIRTH_THREAD:
807        if (sample.birth_thread()->ThreadName().find(required_) ==
808            std::string::npos)
809          return false;
810        break;
811
812      case DEATH_THREAD:
813        if (sample.DeathThreadName().find(required_) == std::string::npos)
814          return false;
815        break;
816
817      case BIRTH_FILE:
818        if (!strstr(sample.location().file_name(), required_.c_str()))
819          return false;
820        break;
821
822      case BIRTH_FUNCTION:
823        if (!strstr(sample.location().function_name(), required_.c_str()))
824          return false;
825        break;
826
827      default:
828        break;
829    }
830  }
831  if (tiebreaker_ && !use_tiebreaker_for_sort_only_)
832    return tiebreaker_->Acceptable(sample);
833  return true;
834}
835
836void Comparator::SetTiebreaker(Selector selector, const std::string& required) {
837  if (selector == selector_ || NIL == selector)
838    return;
839  combined_selectors_ |= selector;
840  if (NIL == selector_) {
841    selector_ = selector;
842    if (required.size())
843      required_ = required;
844    return;
845  }
846  if (tiebreaker_) {
847    if (use_tiebreaker_for_sort_only_) {
848      Comparator* temp = new Comparator;
849      temp->tiebreaker_ = tiebreaker_;
850      tiebreaker_ = temp;
851    }
852  } else {
853    tiebreaker_ = new Comparator;
854    DCHECK(!use_tiebreaker_for_sort_only_);
855  }
856  tiebreaker_->SetTiebreaker(selector, required);
857}
858
859bool Comparator::IsGroupedBy(Selector selector) const {
860  return 0 != (selector & combined_selectors_);
861}
862
863void Comparator::SetSubgroupTiebreaker(Selector selector) {
864  if (selector == selector_ || NIL == selector)
865    return;
866  if (!tiebreaker_) {
867    use_tiebreaker_for_sort_only_ = true;
868    tiebreaker_ = new Comparator;
869    tiebreaker_->SetTiebreaker(selector, "");
870  } else {
871    tiebreaker_->SetSubgroupTiebreaker(selector);
872  }
873}
874
875void Comparator::ParseKeyphrase(const std::string& key_phrase) {
876  typedef std::map<const std::string, Selector> KeyMap;
877  static KeyMap key_map;
878  static bool initialized = false;
879  if (!initialized) {
880    initialized = true;
881    // Sorting and aggretation keywords, which specify how to sort the data, or
882    // can specify a required match from the specified field in the record.
883    key_map["count"]    = COUNT;
884    key_map["duration"] = AVERAGE_DURATION;
885    key_map["birth"]    = BIRTH_THREAD;
886    key_map["death"]    = DEATH_THREAD;
887    key_map["file"]     = BIRTH_FILE;
888    key_map["function"] = BIRTH_FUNCTION;
889    key_map["line"]     = BIRTH_LINE;
890
891    // Immediate commands that do not involve setting sort order.
892    key_map["reset"]     = RESET_ALL_DATA;
893  }
894
895  std::string required;
896  // Watch for: "sort_key=value" as we parse.
897  size_t equal_offset = key_phrase.find('=', 0);
898  if (key_phrase.npos != equal_offset) {
899    // There is a value that must be matched for the data to display.
900    required = key_phrase.substr(equal_offset + 1, key_phrase.npos);
901  }
902  std::string keyword(key_phrase.substr(0, equal_offset));
903  keyword = StringToLowerASCII(keyword);
904  KeyMap::iterator it = key_map.find(keyword);
905  if (key_map.end() == it)
906    return;  // Unknown keyword.
907  if (it->second == RESET_ALL_DATA)
908    ThreadData::ResetAllThreadData();
909  else
910    SetTiebreaker(key_map[keyword], required);
911}
912
913bool Comparator::ParseQuery(const std::string& query) {
914  // Parse each keyphrase between consecutive slashes.
915  for (size_t i = 0; i < query.size();) {
916    size_t slash_offset = query.find('/', i);
917    ParseKeyphrase(query.substr(i, slash_offset - i));
918    if (query.npos == slash_offset)
919      break;
920    i = slash_offset + 1;
921  }
922
923  // Select subgroup ordering (if we want to display the subgroup)
924  SetSubgroupTiebreaker(COUNT);
925  SetSubgroupTiebreaker(AVERAGE_DURATION);
926  SetSubgroupTiebreaker(BIRTH_THREAD);
927  SetSubgroupTiebreaker(DEATH_THREAD);
928  SetSubgroupTiebreaker(BIRTH_FUNCTION);
929  SetSubgroupTiebreaker(BIRTH_FILE);
930  SetSubgroupTiebreaker(BIRTH_LINE);
931
932  return true;
933}
934
935bool Comparator::WriteSortGrouping(const Snapshot& sample,
936                                       std::string* output) const {
937  bool wrote_data = false;
938  switch (selector_) {
939    case BIRTH_THREAD:
940      StringAppendF(output, "All new on %s ",
941                    sample.birth_thread()->ThreadName().c_str());
942      wrote_data = true;
943      break;
944
945    case DEATH_THREAD:
946      if (sample.death_thread())
947        StringAppendF(output, "All deleted on %s ",
948                      sample.DeathThreadName().c_str());
949      else
950        output->append("All still alive ");
951      wrote_data = true;
952      break;
953
954    case BIRTH_FILE:
955      StringAppendF(output, "All born in %s ",
956                    sample.location().file_name());
957      break;
958
959    case BIRTH_FUNCTION:
960      output->append("All born in ");
961      sample.location().WriteFunctionName(output);
962      output->push_back(' ');
963      break;
964
965    default:
966      break;
967  }
968  if (tiebreaker_ && !use_tiebreaker_for_sort_only_) {
969    wrote_data |= tiebreaker_->WriteSortGrouping(sample, output);
970  }
971  return wrote_data;
972}
973
974void Comparator::WriteSnapshot(const Snapshot& sample,
975                               std::string* output) const {
976  sample.death_data().Write(output);
977  if (!(combined_selectors_ & BIRTH_THREAD) ||
978      !(combined_selectors_ & DEATH_THREAD))
979    StringAppendF(output, "%s->%s ",
980                  (combined_selectors_ & BIRTH_THREAD) ? "*" :
981                    sample.birth().birth_thread()->ThreadName().c_str(),
982                  (combined_selectors_ & DEATH_THREAD) ? "*" :
983                    sample.DeathThreadName().c_str());
984  sample.birth().location().Write(!(combined_selectors_ & BIRTH_FILE),
985                                  !(combined_selectors_ & BIRTH_FUNCTION),
986                                  output);
987}
988
989}  // namespace tracked_objects
990