Base ObserverList: Add basic support for standard C++ iterators.

base/observer_list.h

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // 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 <limits>
 #include <vector>
 
+#include "base/gtest_prod_util.h"
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/memory/weak_ptr.h"
 #include "base/stl_util.h"
 
 ///////////////////////////////////////////////////////////////////////////////
 //
 // OVERVIEW:
 //
 //   A container for a list of observers.  Unlike a normal STL vector or list,
@@ skipping 15 matching lines @@
 //
 //     void AddObserver(Observer* obs) {
 //       observer_list_.AddObserver(obs);
 //     }
 //
 //     void RemoveObserver(Observer* obs) {
 //       observer_list_.RemoveObserver(obs);
 //     }
 //
 //     void NotifyFoo() {
-//       FOR_EACH_OBSERVER(Observer, observer_list_, OnFoo(this));
+//       for (auto& observer : observer_list_)
+//         observer.OnFoo(this);
 //     }
 //
 //     void NotifyBar(int x, int y) {
-//       FOR_EACH_OBSERVER(Observer, observer_list_, OnBar(this, x, y));
+//       for (FooList::iterator i = observer_list.begin(),
+//           e = observer_list.end(); i != e; ++i)
+//        i->OnBar(this, x, y);
 //     }
 //
 //    private:
 //     base::ObserverList<Observer> observer_list_;
 //   };
 //
 //
 ///////////////////////////////////////////////////////////////////////////////
 
 namespace base {
 
 template <typename ObserverType>
 class ObserverListThreadSafe;
 
 template <class ObserverType>
 class ObserverListBase
     : public SupportsWeakPtr<ObserverListBase<ObserverType>> {
  public:
   // Enumeration of which observers are notified.
   enum NotificationType {
     // Specifies that any observers added during notification are notified.
     // This is the default type if non type is provided to the constructor.
     NOTIFY_ALL,
 
     // Specifies that observers added while sending out notification are not
     // notified.
     NOTIFY_EXISTING_ONLY
   };
 
-  // An iterator class that can be used to access the list of observers.  See
-  // also the FOR_EACH_OBSERVER macro defined below.
-  class Iterator {
+  // An iterator class that can be used to access the list of observers.
+  template <class ContainerType>
+  class Iter {
    public:
-    explicit Iterator(ObserverListBase<ObserverType>* list);
-    ~Iterator();
+    Iter();
+    explicit Iter(ContainerType* list);
+    ~Iter();
+
+    // Deprecated.
     ObserverType* GetNext();
 
+    // A workaround for C2244. MSVC requires fully qualified type name for
+    // return type on a function definition to match a function declaration.
+    using ThisType =
+        typename ObserverListBase<ObserverType>::template Iter<ContainerType>;
+
+    bool operator==(const Iter& other) const;
+    bool operator!=(const Iter& other) const;
+    ThisType& operator++();
+    ObserverType* operator->() const;
+    ObserverType& operator*() const;
+
    private:
-    WeakPtr<ObserverListBase<ObserverType>> list_;
+    FRIEND_TEST_ALL_PREFIXES(ObserverListTest, BasicStdIterator);
+    FRIEND_TEST_ALL_PREFIXES(ObserverListTest, StdIteratorRemoveFront);
+
+    ObserverType* GetCurrent() const;
+    size_t GetNonNullIndex() const;
+
+    size_t clamped_max_index() const {
+      return std::min(max_index_, list_->observers_.size());
+    }
+
+    bool is_end() const {
+      return !list_ || index_ == clamped_max_index();
+    }
+
+    WeakPtr<ContainerType> 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<ObserverListBase<ObserverType>>;
+
+  using iterator = Iter<ObserverListBase<ObserverType>>;
+  iterator begin() {
+    // An optimization: do not involve weak pointers for empty list.
+    // Note: can't use ?: operator here due to some MSVC bug (unit tests fail)
+    if (observers_.empty())
+      return iterator();
+    return iterator(this);
+  }
+  iterator end() { return iterator(); }
+
+  using const_iterator = Iter<const ObserverListBase<ObserverType>>;
+  const_iterator begin() const {
+    if (observers_.empty())
+      return const_iterator();
+    return const_iterator(this);
+  }
+  const_iterator end() const { return const_iterator(); }
+
   ObserverListBase() : notify_depth_(0), type_(NOTIFY_ALL) {}
   explicit ObserverListBase(NotificationType type)
       : notify_depth_(0), type_(type) {}
 
   // Add an observer to the list.  An observer should not be added to
   // the same list more than once.
   void AddObserver(ObserverType* obs);
 
   // Remove an observer from the list if it is in the list.
   void RemoveObserver(ObserverType* obs);
 
   // Determine whether a particular observer is in the list.
   bool HasObserver(const ObserverType* observer) const;
 
   void Clear();
 
  protected:
   size_t size() const { return observers_.size(); }
 
-  void Compact();
+  // Defragments the list despite const.
+  void Compact() const;
 
  private:
   friend class ObserverListThreadSafe<ObserverType>;
 
   typedef std::vector<ObserverType*> ListType;
 
   ListType observers_;
-  int notify_depth_;
+  mutable int notify_depth_;
   NotificationType type_;
 
-  friend class ObserverListBase::Iterator;
+  template <class ContainerType>
+  friend class Iter;
 
   DISALLOW_COPY_AND_ASSIGN(ObserverListBase);
 };
 
 template <class ObserverType>
-ObserverListBase<ObserverType>::Iterator::Iterator(
-    ObserverListBase<ObserverType>* list)
-    : list_(list->AsWeakPtr()),
+template <class ContainerType>
+ObserverListBase<ObserverType>::Iter<ContainerType>::Iter()
+    : index_(0), max_index_(0) {
+}
+
+template <class ObserverType>
+template <class ContainerType>
+ObserverListBase<ObserverType>::Iter<ContainerType>::Iter(ContainerType* list)
+    : list_(const_cast<ObserverListBase<ObserverType>*>(list)->AsWeakPtr()),
       index_(0),
       max_index_(list->type_ == NOTIFY_ALL ? std::numeric_limits<size_t>::max()
                                            : list->observers_.size()) {
+  index_ = GetNonNullIndex();
   ++list_->notify_depth_;
 }
 
 template <class ObserverType>
-ObserverListBase<ObserverType>::Iterator::~Iterator() {
-  if (list_.get() && --list_->notify_depth_ == 0)
+template <class ContainerType>
+ObserverListBase<ObserverType>::Iter<ContainerType>::~Iter() {
+  if (list_ && --list_->notify_depth_ == 0)
     list_->Compact();
 }
 
 template <class ObserverType>
-ObserverType* ObserverListBase<ObserverType>::Iterator::GetNext() {
-  if (!list_.get())
-    return nullptr;
-  ListType& observers = list_->observers_;
-  // Advance if the current element is null
-  size_t max_index = std::min(max_index_, observers.size());
-  while (index_ < max_index && !observers[index_])
-    ++index_;
-  return index_ < max_index ? observers[index_++] : nullptr;
+template <class ContainerType>
+bool ObserverListBase<ObserverType>::Iter<ContainerType>::operator==(
+    const Iter& other) const {
+  if (is_end() && other.is_end())

[dcheng, 2016/10/07 05:43:16]

Good catch on the is_end() thing! I think with one further tweak, we can make
remove the need to explicitly check is_end().

+    return true;
+  return list_.get() == other.list_.get() && index_ == other.index_;
 }
 
 template <class ObserverType>
+template <class ContainerType>
+bool ObserverListBase<ObserverType>::Iter<ContainerType>::operator!=(
+    const Iter& other) const {
+  return !operator==(other);
+}
+
+template <class ObserverType>
+template <class ContainerType>
+typename ObserverListBase<ObserverType>::template Iter<ContainerType>&
+    ObserverListBase<ObserverType>::Iter<ContainerType>::operator++() {
+  if (list_) {
+    ++index_;
+    index_ = GetNonNullIndex();
+  }
+  return *this;
+}
+
+template <class ObserverType>
+template <class ContainerType>
+ObserverType* ObserverListBase<ObserverType>::Iter<ContainerType>::operator->()
+    const {
+  ObserverType* current = GetCurrent();
+  DCHECK(current);
+  return current;
+}
+
+template <class ObserverType>
+template <class ContainerType>
+ObserverType& ObserverListBase<ObserverType>::Iter<ContainerType>::operator*()
+    const {
+  ObserverType* current = GetCurrent();
+  DCHECK(current);
+  return *current;
+}
+
+template <class ObserverType>
+template <class ContainerType>
+ObserverType* ObserverListBase<ObserverType>::Iter<ContainerType>::GetCurrent()
+    const {
+  if (!list_)
+    return nullptr;
+  return index_ < clamped_max_index() ? list_->observers_[index_] : nullptr;
+}
+
+template <class ObserverType>
+template <class ContainerType>
+size_t ObserverListBase<ObserverType>::Iter<ContainerType>::GetNonNullIndex()
+    const {
+  size_t index = index_;

[dcheng, 2016/10/07 05:43:16]

Let's be a little clever here to remove the need for is_end().

Since GetNonNullIndex() is always assigned to |index_|, we can just directly
mutate |index_|. If we directly mutate |index_|, we can also  reset the iterator
state to match the default constructed iterator when we reach the end by
restructuring the loop slightly:

size_t max_index = clamped_max_index();
do {
  if (list_observers_[index]) return;
} while (++index < max_index);
// No more entries, set internal state to the end.
list_ = nullptr;
index_ = 0;

(We'd probably also want to rename this to EnsureValidState() or something,
since this does return a null index when iteration reaches the end of the list)

Then operator== can be the simple comparison.

+  size_t max_index = clamped_max_index();
+  while (index < max_index && !list_->observers_[index])
+    ++index;
+  return index;
+}
+
+template <class ObserverType>
+template <class ContainerType>
+ObserverType* ObserverListBase<ObserverType>::Iter<ContainerType>::GetNext() {
+  // Make sure index_ is pointing at a non-null element, if the
+  // current index_ has been nulled out.
+  index_ = GetNonNullIndex();
+  ObserverType* current = GetCurrent();
+  operator++();
+  return current;
+}
+
+template <class ObserverType>
 void ObserverListBase<ObserverType>::AddObserver(ObserverType* obs) {
   DCHECK(obs);
   if (ContainsValue(observers_, obs)) {
     NOTREACHED() << "Observers can only be added once!";
     return;
   }
   observers_.push_back(obs);
 }
 
 template <class ObserverType>
@@ skipping 26 matching lines @@
     for (typename ListType::iterator it = observers_.begin();
       it != observers_.end(); ++it) {
       *it = nullptr;
     }
   } else {
     observers_.clear();
   }
 }
 
 template <class ObserverType>
-void ObserverListBase<ObserverType>::Compact() {
-  observers_.erase(
-      std::remove(observers_.begin(), observers_.end(), nullptr),
-      observers_.end());
+void ObserverListBase<ObserverType>::Compact() const {
+  auto& observers = const_cast<ListType&>(observers_);
+  observers.erase(std::remove(observers.begin(), observers.end(), nullptr),
+                  observers.end());
 }
 
 template <class ObserverType, bool check_empty = false>
 class ObserverList : public ObserverListBase<ObserverType> {
  public:
   typedef typename ObserverListBase<ObserverType>::NotificationType
       NotificationType;
 
   ObserverList() {}
   explicit ObserverList(NotificationType type)
       : ObserverListBase<ObserverType>(type) {}
 
   ~ObserverList() {
     // When check_empty is true, assert that the list is empty on destruction.
     if (check_empty) {
       ObserverListBase<ObserverType>::Compact();
       DCHECK_EQ(ObserverListBase<ObserverType>::size(), 0U);
     }
   }
 
   bool might_have_observers() const {
     return ObserverListBase<ObserverType>::size() != 0;
   }
 };
 
-#define FOR_EACH_OBSERVER(ObserverType, observer_list, func)             \
-  do {                                                                   \
-    if ((observer_list).might_have_observers()) {                        \
-      typename base::ObserverListBase<ObserverType>::Iterator            \
-          it_inside_observer_macro(&observer_list);                      \
-      ObserverType* obs;                                                 \
-      while ((obs = it_inside_observer_macro.GetNext()) != nullptr)      \
-        obs->func;                                                       \
-    }                                                                    \
+// Deprecated. Use the range-based for loop instead.
+#define FOR_EACH_OBSERVER(ObserverType, observer_list, func) \
+  do {                                                       \
+    for (ObserverType & o : observer_list)                   \
+      o.func;                                                \
   } while (0)
 
 }  // namespace base
 
 #endif  // BASE_OBSERVER_LIST_H_