base/observer_list.h

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