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

base/observer_list.h

Index: base/observer_list.h
diff --git a/base/observer_list.h b/base/observer_list.h
index afe1f46cd6e31bfaa0456cec8614fd73f3cd0e1e..4d4f6eb8654b74f89f0de47e4f0916d6c79ff4ec 100644
--- a/base/observer_list.h
+++ b/base/observer_list.h
@@ -11,6 +11,7 @@
 #include <limits>
 #include <vector>
 
+#include "base/gtest_prod_util.h"
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/memory/weak_ptr.h"
@@ -46,11 +47,14 @@
 //     }
 //
 //     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:
@@ -80,20 +84,65 @@ class ObserverListBase
     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;
+    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);
+
+    // TODO(loyso): Clean it up once GetNext is removed.
+    ObserverType* GetNonNullCurrent() const;
+    ObserverType* GetCurrent() const;
+
+    size_t GetNonNullIndex() const;
+
+    size_t clamped_max_index() const {
+      return std::min(max_index_, list_->observers_.size());
+    }
+    WeakPtr<ContainerType> list_;
     size_t index_;

[dcheng, 2016/10/05 07:08:24]

Let's add a comment to document the invariants for |index_|:

Something like:

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.

[loyso (OOO), 2016/10/05 07:24:42]

What do you mean by "incremented"? This invariant isn't true for GetNext
increment, for example. Many observers can be unsubscribe at one time. Also, new
observers can subscribe. I'll check this tomorrow.

[loyso (OOO), 2016/10/07 03:45:08]

Done.

     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) {}
@@ -113,7 +162,8 @@ class ObserverListBase
  protected:
   size_t size() const { return observers_.size(); }
 
-  void Compact();
+  // Defragments the list despite const.
+  void Compact() const;
 
  private:
   friend class ObserverListThreadSafe<ObserverType>;
@@ -121,18 +171,24 @@ class ObserverListBase
   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),

[dcheng, 2016/10/05 07:08:23]

Then to guarantee the invariant, initialize this to GetNonNullIndex()

[loyso (OOO), 2016/10/07 03:45:07]

Done.

       max_index_(list->type_ == NOTIFY_ALL ? std::numeric_limits<size_t>::max()
                                            : list->observers_.size()) {
@@ -140,21 +196,90 @@ ObserverListBase<ObserverType>::Iterator::Iterator(
 }
 
 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_])
+template <class ContainerType>
+bool ObserverListBase<ObserverType>::Iter<ContainerType>::operator!=(
+    const Iter& other) const {
+  return GetNonNullCurrent() != other.GetNonNullCurrent();

[dcheng, 2016/10/05 07:08:23]

Hmm.

Given this observer list:

{ nullptr, nullptr, &foo, &bar }

If iterator A has index_ == 0, and iterator B has index_ == 1, they'll compare
equal. In some sense they are... and in some sense they aren't.

Perhaps this check could be:

return list_ == other_.list && index_ == other_.index_;

[loyso (OOO), 2016/10/07 03:45:07]

Done.

+}
+
+template <class ObserverType>
+template <class ContainerType>
+typename ObserverListBase<ObserverType>::template Iter<ContainerType>&
+    ObserverListBase<ObserverType>::Iter<ContainerType>::operator++() {
+  if (list_) {
     ++index_;
-  return index_ < max_index ? observers[index_++] : nullptr;
+    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>
+ObserverType*
+ObserverListBase<ObserverType>::Iter<ContainerType>::GetNonNullCurrent() const {
+  if (!list_)
+    return nullptr;
+  size_t index = GetNonNullIndex();
+  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_;
+  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() {
+  if (!list_)
+    return nullptr;
+
+  ObserverType* current = GetNonNullCurrent();

[dcheng, 2016/10/05 07:08:24]

With the previously mentioned invariant in place, would it be possible to
simplify this to:

ObserverType* current = GetCurrent();
++(*this);
return current;

[dcheng, 2016/10/05 21:01:15]

You're right, this has to be tweaked a bit.

But this can also be written:

// Make sure index_ is pointing at a non-null element, if the
// current index_ has been nulled out.
index_ = GetNonNullIndex();
ObserverType* current = GetCurrent();
++(*this);
return current;

And we won't need GetNonNullCurrent(). I'm OK with slight inaccuracy (or
explicitly calling out GetNext()) in the invariant documentation previously
mentioned.

+
+  index_ = GetNonNullIndex();
+  ++index_;
+
+  return current;
 }
 
 template <class ObserverType>
@@ -204,10 +329,10 @@ void ObserverListBase<ObserverType>::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>
@@ -233,15 +358,12 @@ class ObserverList : public ObserverListBase<ObserverType> {
   }
 };
 
-#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