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;
+    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) {}
 
   // 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),

[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()) {
   ++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 {
+  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_;
+    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>
 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_