base/observer_list.h

   1 // Copyright (c) 2011 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 #ifndef BASE_OBSERVER_LIST_H_
   6 #define BASE_OBSERVER_LIST_H_
   7
   8 #include <stddef.h>
   9
  10 #include <algorithm>
  11 #include <iterator>
  12 #include <limits>
  13 #include <utility>
  14 #include <vector>
  15
  16 #include "base/check_op.h"
  17 #include "base/gtest_prod_util.h"
  18 #include "base/macros.h"
  19 #include "base/notreached.h"
  20 #include "base/observer_list_internal.h"
  21 #include "base/sequence_checker.h"
  22 #include "base/stl_util.h"
  23
  24 ///////////////////////////////////////////////////////////////////////////////
  25 //
  26 // OVERVIEW:
  27 //
  28 //   A list of observers. Unlike a standard vector or list, this container can
  29 //   be modified during iteration without invalidating the iterator. So, it
  30 //   safely handles the case of an observer removing itself or other observers
  31 //   from the list while observers are being notified.
  32 //
  33 //
  34 // WARNING:
  35 //
  36 //   ObserverList is not thread-compatible. Iterating on the same ObserverList
  37 //   simultaneously in different threads is not safe, even when the ObserverList
  38 //   itself is not modified.
  39 //
  40 //   For a thread-safe observer list, see ObserverListThreadSafe.
  41 //
  42 //
  43 // TYPICAL USAGE:
  44 //
  45 //   class MyWidget {
  46 //    public:
  47 //     ...
  48 //
  49 //     class Observer : public base::CheckedObserver {
  50 //      public:
  51 //       virtual void OnFoo(MyWidget* w) = 0;
  52 //       virtual void OnBar(MyWidget* w, int x, int y) = 0;
  53 //     };
  54 //
  55 //     void AddObserver(Observer* obs) {
  56 //       observers_.AddObserver(obs);
  57 //     }
  58 //
  59 //     void RemoveObserver(Observer* obs) {
  60 //       observers_.RemoveObserver(obs);
  61 //     }
  62 //
  63 //     void NotifyFoo() {
  64 //       for (Observer& obs : observers_)
  65 //         obs.OnFoo(this);
  66 //     }
  67 //
  68 //     void NotifyBar(int x, int y) {
  69 //       for (Observer& obs : observers_)
  70 //         obs.OnBar(this, x, y);
  71 //     }
  72 //
  73 //    private:
  74 //     base::ObserverList<Observer> observers_;
  75 //   };
  76 //
  77 //
  78 ///////////////////////////////////////////////////////////////////////////////
  79
  80 namespace base {
  81
  82 // Enumeration of which observers are notified by ObserverList.
  83 enum class ObserverListPolicy {
  84   // Specifies that any observers added during notification are notified.
  85   // This is the default policy if no policy is provided to the constructor.
  86   ALL,
  87
  88   // Specifies that observers added while sending out notification are not
  89   // notified.
  90   EXISTING_ONLY,
  91 };
  92
  93 // When check_empty is true, assert that the list is empty on destruction.
  94 // When allow_reentrancy is false, iterating throught the list while already in
  95 // the iteration loop will result in DCHECK failure.
  96 // TODO(oshima): Change the default to non reentrant. https://crbug.com/812109
  97 template <class ObserverType,
  98           bool check_empty = false,
  99           bool allow_reentrancy = true,
 100           class ObserverStorageType = internal::CheckedObserverAdapter>
 101 class ObserverList {
 102  public:
 103   // Allow declaring an ObserverList<...>::Unchecked that replaces the default
 104   // ObserverStorageType to use raw pointers. This is required to support legacy
 105   // observers that do not inherit from CheckedObserver. The majority of new
 106   // code should not use this, but it may be suited for performance-critical
 107   // situations to avoid overheads of a CHECK(). Note the type can't be chosen
 108   // based on ObserverType's definition because ObserverLists are often declared
 109   // in headers using a forward-declare of ObserverType.
 110   using Unchecked = ObserverList<ObserverType,
 111                                  check_empty,
 112                                  allow_reentrancy,
 113                                  internal::UncheckedObserverAdapter>;
 114
 115   // An iterator class that can be used to access the list of observers.
 116   class Iter {
 117    public:
 118     using iterator_category = std::forward_iterator_tag;
 119     using value_type = ObserverType;
 120     using difference_type = ptrdiff_t;
 121     using pointer = ObserverType*;
 122     using reference = ObserverType&;
 123
 124     Iter() : index_(0), max_index_(0) {}
 125
 126     explicit Iter(const ObserverList* list)
 127         : list_(const_cast<ObserverList*>(list)),
 128           index_(0),
 129           max_index_(list->policy_ == ObserverListPolicy::ALL
 130                          ? std::numeric_limits<size_t>::max()
 131                          : list->observers_.size()) {
 132       DCHECK(list);
 133       DCHECK(allow_reentrancy || list_.IsOnlyRemainingNode());
 134       // Bind to this sequence when creating the first iterator.
 135       DCHECK_CALLED_ON_VALID_SEQUENCE(list_->iteration_sequence_checker_);
 136       EnsureValidIndex();
 137     }
 138
 139     ~Iter() {
 140       if (list_.IsOnlyRemainingNode())
 141         list_->Compact();
 142     }
 143
 144     Iter(const Iter& other)
 145         : index_(other.index_), max_index_(other.max_index_) {
 146       if (other.list_)
 147         list_.SetList(other.list_.get());
 148     }
 149
 150     Iter& operator=(const Iter& other) {
 151       if (&other == this)
 152         return *this;
 153
 154       if (list_.IsOnlyRemainingNode())
 155         list_->Compact();
 156
 157       list_.Invalidate();
 158       if (other.list_)
 159         list_.SetList(other.list_.get());
 160
 161       index_ = other.index_;
 162       max_index_ = other.max_index_;
 163       return *this;
 164     }
 165
 166     bool operator==(const Iter& other) const {
 167       return (is_end() && other.is_end()) ||
 168              (list_.get() == other.list_.get() && index_ == other.index_);
 169     }
 170
 171     bool operator!=(const Iter& other) const { return !(*this == other); }
 172
 173     Iter& operator++() {
 174       if (list_) {
 175         ++index_;
 176         EnsureValidIndex();
 177       }
 178       return *this;
 179     }
 180
 181     Iter operator++(int) {
 182       Iter it(*this);
 183       ++(*this);
 184       return it;
 185     }
 186
 187     ObserverType* operator->() const {
 188       ObserverType* const current = GetCurrent();
 189       DCHECK(current);
 190       return current;
 191     }
 192
 193     ObserverType& operator*() const {
 194       ObserverType* const current = GetCurrent();
 195       DCHECK(current);
 196       return *current;
 197     }
 198
 199    private:
 200     friend class ObserverListTestBase;
 201
 202     ObserverType* GetCurrent() const {
 203       DCHECK(list_);
 204       DCHECK_LT(index_, clamped_max_index());
 205       return ObserverStorageType::template Get<ObserverType>(
 206           list_->observers_[index_]);
 207     }
 208
 209     void EnsureValidIndex() {
 210       DCHECK(list_);
 211       const size_t max_index = clamped_max_index();
 212       while (index_ < max_index &&
 213              list_->observers_[index_].IsMarkedForRemoval()) {
 214         ++index_;
 215       }
 216     }
 217
 218     size_t clamped_max_index() const {
 219       return std::min(max_index_, list_->observers_.size());
 220     }
 221
 222     bool is_end() const { return !list_ || index_ == clamped_max_index(); }
 223
 224     // Lightweight weak pointer to the ObserverList.
 225     internal::WeakLinkNode<ObserverList> list_;
 226
 227     // When initially constructed and each time the iterator is incremented,
 228     // |index_| is guaranteed to point to a non-null index if the iterator
 229     // has not reached the end of the ObserverList.
 230     size_t index_;
 231     size_t max_index_;
 232   };
 233
 234   using iterator = Iter;
 235   using const_iterator = Iter;
 236   using value_type = ObserverType;
 237
 238   const_iterator begin() const {
 239     // An optimization: do not involve weak pointers for empty list.
 240     return observers_.empty() ? const_iterator() : const_iterator(this);
 241   }
 242
 243   const_iterator end() const { return const_iterator(); }
 244
 245   explicit ObserverList(ObserverListPolicy policy = ObserverListPolicy::ALL)
 246       : policy_(policy) {
 247     // Sequence checks only apply when iterators are live.
 248     DETACH_FROM_SEQUENCE(iteration_sequence_checker_);
 249   }
 250
 251   ~ObserverList() {
 252     // If there are live iterators, ensure destruction is thread-safe.
 253     if (!live_iterators_.empty())
 254       DCHECK_CALLED_ON_VALID_SEQUENCE(iteration_sequence_checker_);
 255
 256     while (!live_iterators_.empty())
 257       live_iterators_.head()->value()->Invalidate();
 258     if (check_empty) {
 259       Compact();
 260       DCHECK(observers_.empty());
 261     }
 262   }
 263
 264   // Add an observer to this list. An observer should not be added to the same
 265   // list more than once.
 266   //
 267   // Precondition: obs != nullptr
 268   // Precondition: !HasObserver(obs)
 269   void AddObserver(ObserverType* obs) {
 270     DCHECK(obs);
 271     if (HasObserver(obs)) {
 272       NOTREACHED() << "Observers can only be added once!";
 273       return;
 274     }
 275     observers_.emplace_back(ObserverStorageType(obs));
 276   }
 277
 278   // Removes the given observer from this list. Does nothing if this observer is
 279   // not in this list.
 280   void RemoveObserver(const ObserverType* obs) {
 281     DCHECK(obs);
 282     const auto it =
 283         std::find_if(observers_.begin(), observers_.end(),
 284                      [obs](const auto& o) { return o.IsEqual(obs); });
 285     if (it == observers_.end())
 286       return;
 287
 288     if (live_iterators_.empty()) {
 289       observers_.erase(it);
 290     } else {
 291       DCHECK_CALLED_ON_VALID_SEQUENCE(iteration_sequence_checker_);
 292       it->MarkForRemoval();
 293     }
 294   }
 295
 296   // Determine whether a particular observer is in the list.
 297   bool HasObserver(const ObserverType* obs) const {
 298     // Client code passing null could be confused by the treatment of observers
 299     // removed mid-iteration. TODO(https://crbug.com/876588): This should
 300     // probably DCHECK, but some client code currently does pass null.
 301     if (obs == nullptr)
 302       return false;
 303     return std::find_if(observers_.begin(), observers_.end(),
 304                         [obs](const auto& o) { return o.IsEqual(obs); }) !=
 305            observers_.end();
 306   }
 307
 308   // Removes all the observers from this list.
 309   void Clear() {
 310     if (live_iterators_.empty()) {
 311       observers_.clear();
 312     } else {
 313       DCHECK_CALLED_ON_VALID_SEQUENCE(iteration_sequence_checker_);
 314       for (auto& observer : observers_)
 315         observer.MarkForRemoval();
 316     }
 317   }
 318
 319   bool might_have_observers() const { return !observers_.empty(); }
 320
 321  private:
 322   friend class internal::WeakLinkNode<ObserverList>;
 323
 324   // Compacts list of observers by removing those marked for removal.
 325   void Compact() {
 326     // Detach whenever the last iterator is destroyed. Detaching is safe because
 327     // Compact() is only ever called when the last iterator is destroyed.
 328     DETACH_FROM_SEQUENCE(iteration_sequence_checker_);
 329
 330     EraseIf(observers_, [](const auto& o) { return o.IsMarkedForRemoval(); });
 331   }
 332
 333   std::vector<ObserverStorageType> observers_;
 334
 335   base::LinkedList<internal::WeakLinkNode<ObserverList>> live_iterators_;
 336
 337   const ObserverListPolicy policy_;
 338
 339   SEQUENCE_CHECKER(iteration_sequence_checker_);
 340
 341   DISALLOW_COPY_AND_ASSIGN(ObserverList);
 342 };
 343
 344 template <class ObserverType, bool check_empty = false>
 345 using ReentrantObserverList = ObserverList<ObserverType, check_empty, true>;
 346
 347 }  // namespace base
 348
 349 #endif  // BASE_OBSERVER_LIST_H_