observer_list.h 11 KB

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