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