gdbsupport/observable.h

   1 /* Observers
   2
   3    Copyright (C) 2016-2023 Free Software Foundation, Inc.
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef COMMON_OBSERVABLE_H
  21 #define COMMON_OBSERVABLE_H
  22
  23 #include <algorithm>
  24 #include <functional>
  25 #include <vector>
  26
  27 /* Print an "observer" debug statement.  */
  28
  29 #define observer_debug_printf(fmt, ...) \
  30   debug_prefixed_printf_cond (observer_debug, "observer", fmt, ##__VA_ARGS__)
  31
  32 /* Print "observer" start/end debug statements.  */
  33
  34 #define OBSERVER_SCOPED_DEBUG_START_END(fmt, ...) \
  35   scoped_debug_start_end (observer_debug, "observer", fmt, ##__VA_ARGS__)
  36
  37 namespace gdb
  38 {
  39
  40 namespace observers
  41 {
  42
  43 extern bool observer_debug;
  44
  45 /* An observer is an entity which is interested in being notified
  46    when GDB reaches certain states, or certain events occur in GDB.
  47    The entity being observed is called the observable.  To receive
  48    notifications, the observer attaches a callback to the observable.
  49    One observable can have several observers.
  50
  51    The observer implementation is also currently not reentrant.  In
  52    particular, it is therefore not possible to call the attach or
  53    detach routines during a notification.  */
  54
  55 /* The type of a key that can be passed to attach, which can be passed
  56    to detach to remove associated observers.  Tokens have address
  57    identity, and are thus usually const globals.  */
  58 struct token
  59 {
  60   token () = default;
  61
  62   DISABLE_COPY_AND_ASSIGN (token);
  63 };
  64
  65 namespace detail
  66 {
  67   /* Types that don't depend on any template parameter.  This saves a
  68      bit of code and debug info size, compared to putting them inside
  69      class observable.  */
  70
  71   /* Use for sorting algorithm, to indicate which observer we have
  72      visited.  */
  73   enum class visit_state
  74   {
  75     NOT_VISITED,
  76     VISITING,
  77     VISITED,
  78   };
  79 }
  80
  81 template<typename... T>
  82 class observable
  83 {
  84 public:
  85   typedef std::function<void (T...)> func_type;
  86
  87 private:
  88   struct observer
  89   {
  90     observer (const struct token *token, func_type func, const char *name,
  91               const std::vector<const struct token *> &dependencies)
  92       : token (token), func (func), name (name), dependencies (dependencies)
  93     {}
  94
  95     const struct token *token;
  96     func_type func;
  97     const char *name;
  98     std::vector<const struct token *> dependencies;
  99   };
 100
 101 public:
 102   explicit observable (const char *name)
 103     : m_name (name)
 104   {
 105   }
 106
 107   DISABLE_COPY_AND_ASSIGN (observable);
 108
 109   /* Attach F as an observer to this observable.  F cannot be detached or
 110      specified as a dependency.
 111
 112      DEPENDENCIES is a list of tokens of observers to be notified before this
 113      one.
 114
 115      NAME is the name of the observer, used for debug output purposes.  Its
 116      lifetime must be at least as long as the observer is attached.  */
 117   void attach (const func_type &f, const char *name,
 118                const std::vector<const struct token *> &dependencies = {})
 119   {
 120     attach (f, nullptr, name, dependencies);
 121   }
 122
 123   /* Attach F as an observer to this observable.
 124
 125      T is a reference to a token that can be used to later remove F or specify F
 126      as a dependency of another observer.
 127
 128      DEPENDENCIES is a list of tokens of observers to be notified before this
 129      one.
 130
 131      NAME is the name of the observer, used for debug output purposes.  Its
 132      lifetime must be at least as long as the observer is attached.  */
 133   void attach (const func_type &f, const token &t, const char *name,
 134                const std::vector<const struct token *> &dependencies = {})
 135   {
 136     attach (f, &t, name, dependencies);
 137   }
 138
 139   /* Remove observers associated with T from this observable.  T is
 140      the token that was previously passed to any number of "attach"
 141      calls.  */
 142   void detach (const token &t)
 143   {
 144     auto iter = std::remove_if (m_observers.begin (),
 145                                 m_observers.end (),
 146                                 [&] (const observer &o)
 147                                 {
 148                                   return o.token == &t;
 149                                 });
 150
 151     observer_debug_printf ("Detaching observable %s from observer %s",
 152                            iter->name, m_name);
 153
 154     m_observers.erase (iter, m_observers.end ());
 155   }
 156
 157   /* Notify all observers that are attached to this observable.  */
 158   void notify (T... args) const
 159   {
 160     OBSERVER_SCOPED_DEBUG_START_END ("observable %s notify() called", m_name);
 161
 162     for (auto &&e : m_observers)
 163       {
 164         OBSERVER_SCOPED_DEBUG_START_END ("calling observer %s of observable %s",
 165                                          e.name, m_name);
 166         e.func (args...);
 167       }
 168   }
 169
 170 private:
 171
 172   std::vector<observer> m_observers;
 173   const char *m_name;
 174
 175   /* Helper method for topological sort using depth-first search algorithm.
 176
 177      Visit all dependencies of observer at INDEX in M_OBSERVERS (later referred
 178      to as "the observer").  Then append the observer to SORTED_OBSERVERS.
 179
 180      If the observer is already visited, do nothing.  */
 181   void visit_for_sorting (std::vector<observer> &sorted_observers,
 182                           std::vector<detail::visit_state> &visit_states,
 183                           int index)
 184   {
 185     if (visit_states[index] == detail::visit_state::VISITED)
 186       return;
 187
 188     /* If we are already visiting this observer, it means there's a cycle.  */
 189     gdb_assert (visit_states[index] != detail::visit_state::VISITING);
 190
 191     visit_states[index] = detail::visit_state::VISITING;
 192
 193     /* For each dependency of this observer...  */
 194     for (const token *dep : m_observers[index].dependencies)
 195       {
 196         /* ... find the observer that has token DEP.  If found, visit it.  */
 197         auto it_dep
 198           = std::find_if (m_observers.begin (), m_observers.end (),
 199                             [&] (observer o) { return o.token == dep; });
 200         if (it_dep != m_observers.end ())
 201         {
 202           int i = std::distance (m_observers.begin (), it_dep);
 203           visit_for_sorting (sorted_observers, visit_states, i);
 204         }
 205       }
 206
 207     visit_states[index] = detail::visit_state::VISITED;
 208     sorted_observers.push_back (m_observers[index]);
 209   }
 210
 211   /* Sort the observers, so that dependencies come before observers
 212      depending on them.
 213
 214      Uses depth-first search algorithm for topological sorting, see
 215      https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search .  */
 216   void sort_observers ()
 217   {
 218     std::vector<observer> sorted_observers;
 219     std::vector<detail::visit_state> visit_states
 220       (m_observers.size (), detail::visit_state::NOT_VISITED);
 221
 222     for (size_t i = 0; i < m_observers.size (); i++)
 223       visit_for_sorting (sorted_observers, visit_states, i);
 224
 225     m_observers = std::move (sorted_observers);
 226   }
 227
 228   void attach (const func_type &f, const token *t, const char *name,
 229                const std::vector<const struct token *> &dependencies)
 230   {
 231
 232     observer_debug_printf ("Attaching observable %s to observer %s",
 233                            name, m_name);
 234
 235     m_observers.emplace_back (t, f, name, dependencies);
 236
 237     /* The observer has been inserted at the end of the vector, so it will be
 238        after any of its potential dependencies attached earlier.  If the
 239        observer has a token, it means that other observers can specify it as
 240        a dependency, so sorting is necessary to ensure those will be after the
 241        newly inserted observer afterwards.  */
 242     if (t != nullptr)
 243       sort_observers ();
 244   };
 245 };
 246
 247 } /* namespace observers */
 248
 249 } /* namespace gdb */
 250
 251 #endif /* COMMON_OBSERVABLE_H */