tor-browser

observer_list.h (11785B)

---

// Copyright 2011 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_OBSERVER_LIST_H_
#define BASE_OBSERVER_LIST_H_

#include <stddef.h>

#include <algorithm>
#include <iterator>
#include <limits>
#include <ostream>
#include <string>
#include <utility>
#include <vector>

#include "base/check.h"
#include "base/check_op.h"
#include "base/containers/cxx20_erase_vector.h"
#include "base/dcheck_is_on.h"
#include "base/debug/dump_without_crashing.h"
#include "base/notreached.h"
#include "base/observer_list_internal.h"
#include "base/ranges/algorithm.h"
#include "base/sequence_checker.h"
#include "build/build_config.h"

///////////////////////////////////////////////////////////////////////////////
//
// OVERVIEW:
//
//   A list of observers. Unlike a standard vector or list, this container can
//   be modified during iteration without invalidating the iterator. So, it
//   safely handles the case of an observer removing itself or other observers
//   from the list while observers are being notified.
//
//
// WARNING:
//
//   ObserverList is not thread-compatible. Iterating on the same ObserverList
//   simultaneously in different threads is not safe, even when the ObserverList
//   itself is not modified.
//
//   For a thread-safe observer list, see ObserverListThreadSafe.
//
//
// TYPICAL USAGE:
//
//   class MyWidget {
//    public:
//     ...
//
//     class Observer : public base::CheckedObserver {
//      public:
//       virtual void OnFoo(MyWidget* w) = 0;
//       virtual void OnBar(MyWidget* w, int x, int y) = 0;
//     };
//
//     void AddObserver(Observer* obs) {
//       observers_.AddObserver(obs);
//     }
//
//     void RemoveObserver(Observer* obs) {
//       observers_.RemoveObserver(obs);
//     }
//
//     void NotifyFoo() {
//       for (Observer& obs : observers_)
//         obs.OnFoo(this);
//     }
//
//     void NotifyBar(int x, int y) {
//       for (Observer& obs : observers_)
//         obs.OnBar(this, x, y);
//     }
//
//    private:
//     base::ObserverList<Observer> observers_;
//   };
//
//
///////////////////////////////////////////////////////////////////////////////

namespace base {

// Enumeration of which observers are notified by ObserverList.
enum class ObserverListPolicy {
 // Specifies that any observers added during notification are notified.
 // This is the default policy if no policy is provided to the constructor.
 ALL,

 // Specifies that observers added while sending out notification are not
 // notified.
 EXISTING_ONLY,
};

// When check_empty is true, assert that the list is empty on destruction.
// When allow_reentrancy is false, iterating throught the list while already in
// the iteration loop will result in DCHECK failure.
// TODO(oshima): Change the default to non reentrant. https://crbug.com/812109
template <class ObserverType,
         bool check_empty = false,
         bool allow_reentrancy = true,
         class ObserverStorageType = internal::CheckedObserverAdapter>
class ObserverList {
public:
 // Allow declaring an ObserverList<...>::Unchecked that replaces the default
 // ObserverStorageType to use raw pointers. This is required to support legacy
 // observers that do not inherit from CheckedObserver. The majority of new
 // code should not use this, but it may be suited for performance-critical
 // situations to avoid overheads of a CHECK(). Note the type can't be chosen
 // based on ObserverType's definition because ObserverLists are often declared
 // in headers using a forward-declare of ObserverType.
 using Unchecked = ObserverList<ObserverType,
                                check_empty,
                                allow_reentrancy,
                                internal::UncheckedObserverAdapter>;

 // An iterator class that can be used to access the list of observers.
 class Iter {
  public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = ObserverType;
   using difference_type = ptrdiff_t;
   using pointer = ObserverType*;
   using reference = ObserverType&;

   Iter() : index_(0), max_index_(0) {}

   explicit Iter(const ObserverList* list)
       : list_(const_cast<ObserverList*>(list)),
         index_(0),
         max_index_(list->policy_ == ObserverListPolicy::ALL
                        ? std::numeric_limits<size_t>::max()
                        : list->observers_.size()) {
     DCHECK(list);
     // TODO(crbug.com/1423093): Turn into CHECK once very prevalent failures
     // are weeded out.
     DUMP_WILL_BE_CHECK(allow_reentrancy || list_.IsOnlyRemainingNode());
     // Bind to this sequence when creating the first iterator.
     DCHECK_CALLED_ON_VALID_SEQUENCE(list_->iteration_sequence_checker_);
     EnsureValidIndex();
   }

   ~Iter() {
     if (list_.IsOnlyRemainingNode())
       list_->Compact();
   }

   Iter(const Iter& other)
       : index_(other.index_), max_index_(other.max_index_) {
     if (other.list_)
       list_.SetList(other.list_.get());
   }

   Iter& operator=(const Iter& other) {
     if (&other == this)
       return *this;

     if (list_.IsOnlyRemainingNode())
       list_->Compact();

     list_.Invalidate();
     if (other.list_)
       list_.SetList(other.list_.get());

     index_ = other.index_;
     max_index_ = other.max_index_;
     return *this;
   }

   bool operator==(const Iter& other) const {
     return (is_end() && other.is_end()) ||
            (list_.get() == other.list_.get() && index_ == other.index_);
   }

   bool operator!=(const Iter& other) const { return !(*this == other); }

   Iter& operator++() {
     if (list_) {
       ++index_;
       EnsureValidIndex();
     }
     return *this;
   }

   Iter operator++(int) {
     Iter it(*this);
     ++(*this);
     return it;
   }

   ObserverType* operator->() const {
     ObserverType* const current = GetCurrent();
     DCHECK(current);
     return current;
   }

   ObserverType& operator*() const {
     ObserverType* const current = GetCurrent();
     DCHECK(current);
     return *current;
   }

  private:
   friend class ObserverListTestBase;

   ObserverType* GetCurrent() const {
     DCHECK(list_);
     DCHECK_LT(index_, clamped_max_index());
     return ObserverStorageType::template Get<ObserverType>(
         list_->observers_[index_]);
   }

   void EnsureValidIndex() {
     DCHECK(list_);
     const size_t max_index = clamped_max_index();
     while (index_ < max_index &&
            list_->observers_[index_].IsMarkedForRemoval()) {
       ++index_;
     }
   }

   size_t clamped_max_index() const {
     return std::min(max_index_, list_->observers_.size());
   }

   bool is_end() const { return !list_ || index_ == clamped_max_index(); }

   // Lightweight weak pointer to the ObserverList.
   internal::WeakLinkNode<ObserverList> list_;

   // When initially constructed and each time the iterator is incremented,
   // |index_| is guaranteed to point to a non-null index if the iterator
   // has not reached the end of the ObserverList.
   size_t index_;
   size_t max_index_;
 };

 using iterator = Iter;
 using const_iterator = Iter;
 using value_type = ObserverType;

 const_iterator begin() const {
   // An optimization: do not involve weak pointers for empty list.
   return observers_.empty() ? const_iterator() : const_iterator(this);
 }

 const_iterator end() const { return const_iterator(); }

 explicit ObserverList(ObserverListPolicy policy = ObserverListPolicy::ALL)
     : policy_(policy) {
   // Sequence checks only apply when iterators are live.
   DETACH_FROM_SEQUENCE(iteration_sequence_checker_);
 }
 ObserverList(const ObserverList&) = delete;
 ObserverList& operator=(const ObserverList&) = delete;
 ~ObserverList() {
   // If there are live iterators, ensure destruction is thread-safe.
   if (!live_iterators_.empty())
     DCHECK_CALLED_ON_VALID_SEQUENCE(iteration_sequence_checker_);

   while (!live_iterators_.empty())
     live_iterators_.head()->value()->Invalidate();
   if (check_empty) {
     Compact();
     // TODO(crbug.com/1423093): Turn into a CHECK once very prevalent failures
     // are weeded out.
     DUMP_WILL_BE_CHECK(observers_.empty())
         << "\n"
         << GetObserversCreationStackString();
   }
 }

 // Add an observer to this list. An observer should not be added to the same
 // list more than once.
 //
 // Precondition: obs != nullptr
 // Precondition: !HasObserver(obs)
 void AddObserver(ObserverType* obs) {
   DCHECK(obs);
   // TODO(crbug.com/1423093): Turn this into a CHECK once very prevalent
   // failures are weeded out.
   if (HasObserver(obs)) {
     NOTREACHED() << "Observers can only be added once!";
     return;
   }
   observers_count_++;
   observers_.emplace_back(ObserverStorageType(obs));
 }

 // Removes the given observer from this list. Does nothing if this observer is
 // not in this list.
 void RemoveObserver(const ObserverType* obs) {
   DCHECK(obs);
   const auto it = ranges::find_if(
       observers_, [obs](const auto& o) { return o.IsEqual(obs); });
   if (it == observers_.end())
     return;
   if (!it->IsMarkedForRemoval())
     observers_count_--;
   if (live_iterators_.empty()) {
     observers_.erase(it);
   } else {
     DCHECK_CALLED_ON_VALID_SEQUENCE(iteration_sequence_checker_);
     it->MarkForRemoval();
   }
 }

 // Determine whether a particular observer is in the list.
 bool HasObserver(const ObserverType* obs) const {
   // Client code passing null could be confused by the treatment of observers
   // removed mid-iteration. TODO(https://crbug.com/876588): This should
   // probably DCHECK, but some client code currently does pass null.
   if (obs == nullptr)
     return false;
   return ranges::find_if(observers_, [obs](const auto& o) {
            return o.IsEqual(obs);
          }) != observers_.end();
 }

 // Removes all the observers from this list.
 void Clear() {
   if (live_iterators_.empty()) {
     observers_.clear();
   } else {
     DCHECK_CALLED_ON_VALID_SEQUENCE(iteration_sequence_checker_);
     for (auto& observer : observers_)
       observer.MarkForRemoval();
   }
   observers_count_ = 0;
 }

 bool empty() const { return !observers_count_; }

private:
 friend class internal::WeakLinkNode<ObserverList>;

 // Compacts list of observers by removing those marked for removal.
 void Compact() {
   // Detach whenever the last iterator is destroyed. Detaching is safe because
   // Compact() is only ever called when the last iterator is destroyed.
   DETACH_FROM_SEQUENCE(iteration_sequence_checker_);

   base::EraseIf(observers_,
                 [](const auto& o) { return o.IsMarkedForRemoval(); });
 }

 std::string GetObserversCreationStackString() const {
#if DCHECK_IS_ON()
   std::string result;
#if BUILDFLAG(IS_IOS)
   result += "Use go/observer-list-empty to interpret.\n";
#endif
   for (const auto& observer : observers_) {
     result += observer.GetCreationStackString();
     result += "\n";
   }
   return result;
#else
   return "For observer stack traces, build with `dcheck_always_on=true`.";
#endif  // DCHECK_IS_ON()
 }

 std::vector<ObserverStorageType> observers_;

 base::LinkedList<internal::WeakLinkNode<ObserverList>> live_iterators_;

 size_t observers_count_{0};

 const ObserverListPolicy policy_;

 SEQUENCE_CHECKER(iteration_sequence_checker_);
};

template <class ObserverType, bool check_empty = false>
using ReentrantObserverList = ObserverList<ObserverType, check_empty, true>;

}  // namespace base

#endif  // BASE_OBSERVER_LIST_H_