gdbsupport/observable.h

   1 /* Observers
   2
   3    Copyright (C) 2016-2021 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 template<typename... T>
  66 class observable
  67 {
  68 public:
  69   typedef std::function<void (T...)> func_type;
  70
  71 private:
  72   struct observer
  73   {
  74     observer (const struct token *token, func_type func, const char *name,
  75               const std::vector<const struct token *> &dependencies)
  76       : token (token), func (func), name (name), dependencies (dependencies)
  77     {}
  78
  79     const struct token *token;
  80     func_type func;
  81     const char *name;
  82     std::vector<const struct token *> dependencies;
  83   };
  84
  85 public:
  86   explicit observable (const char *name)
  87     : m_name (name)
  88   {
  89   }
  90
  91   DISABLE_COPY_AND_ASSIGN (observable);
  92
  93   /* Attach F as an observer to this observable.  F cannot be detached or
  94      specified as a dependency.
  95
  96      DEPENDENCIES is a list of tokens of observers to be notified before this
  97      one.
  98
  99      NAME is the name of the observer, used for debug output purposes.  Its
 100      lifetime must be at least as long as the observer is attached.  */
 101   void attach (const func_type &f, const char *name,
 102                const std::vector<const struct token *> &dependencies = {})
 103   {
 104     attach (f, nullptr, name, dependencies);
 105   }
 106
 107   /* Attach F as an observer to this observable.
 108
 109      T is a reference to a token that can be used to later remove F or specify F
 110      as a dependency of another observer.
 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 token &t, const char *name,
 118                const std::vector<const struct token *> &dependencies = {})
 119   {
 120     attach (f, &t, name, dependencies);
 121   }
 122
 123   /* Remove observers associated with T from this observable.  T is
 124      the token that was previously passed to any number of "attach"
 125      calls.  */
 126   void detach (const token &t)
 127   {
 128     auto iter = std::remove_if (m_observers.begin (),
 129                                 m_observers.end (),
 130                                 [&] (const observer &o)
 131                                 {
 132                                   return o.token == &t;
 133                                 });
 134
 135     observer_debug_printf ("Detaching observable %s from observer %s",
 136                            iter->name, m_name);
 137
 138     m_observers.erase (iter, m_observers.end ());
 139   }
 140
 141   /* Notify all observers that are attached to this observable.  */
 142   void notify (T... args) const
 143   {
 144     OBSERVER_SCOPED_DEBUG_START_END ("observable %s notify() called", m_name);
 145
 146     for (auto &&e : m_observers)
 147       {
 148         OBSERVER_SCOPED_DEBUG_START_END ("calling observer %s of observable %s",
 149                                          e.name, m_name);
 150         e.func (args...);
 151       }
 152   }
 153
 154 private:
 155
 156   std::vector<observer> m_observers;
 157   const char *m_name;
 158
 159   /* Use for sorting algorithm, to indicate which observer we have visited.  */
 160   enum class visit_state
 161   {
 162     NOT_VISITED,
 163     VISITING,
 164     VISITED,
 165   };
 166
 167   /* Helper method for topological sort using depth-first search algorithm.
 168
 169      Visit all dependencies of observer at INDEX in M_OBSERVERS (later referred
 170      to as "the observer").  Then append the observer to SORTED_OBSERVERS.
 171
 172      If the observer is already visited, do nothing.  */
 173   void visit_for_sorting (std::vector<observer> &sorted_observers,
 174                           std::vector<visit_state> &visit_states, int index)
 175   {
 176     if (visit_states[index] == visit_state::VISITED)
 177       return;
 178
 179     /* If we are already visiting this observer, it means there's a cycle.  */
 180     gdb_assert (visit_states[index] != visit_state::VISITING);
 181
 182     visit_states[index] = visit_state::VISITING;
 183
 184     /* For each dependency of this observer...  */
 185     for (const token *dep : m_observers[index].dependencies)
 186       {
 187         /* ... find the observer that has token DEP.  If found, visit it.  */
 188         auto it_dep
 189             = std::find_if (m_observers.begin (), m_observers.end (),
 190                             [&] (observer o) { return o.token == dep; });
 191         if (it_dep != m_observers.end ())
 192           {
 193             int i = std::distance (m_observers.begin (), it_dep);
 194             visit_for_sorting (sorted_observers, visit_states, i);
 195           }
 196       }
 197
 198     visit_states[index] = visit_state::VISITED;
 199     sorted_observers.push_back (m_observers[index]);
 200   }
 201
 202   /* Sort the observers, so that dependencies come before observers
 203      depending on them.
 204
 205      Uses depth-first search algorithm for topological sorting, see
 206      https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search .  */
 207   void sort_observers ()
 208   {
 209     std::vector<observer> sorted_observers;
 210     std::vector<visit_state> visit_states (m_observers.size (),
 211                                            visit_state::NOT_VISITED);
 212
 213     for (size_t i = 0; i < m_observers.size (); i++)
 214       visit_for_sorting (sorted_observers, visit_states, i);
 215
 216     m_observers = std::move (sorted_observers);
 217   }
 218
 219   void attach (const func_type &f, const token *t, const char *name,
 220                const std::vector<const struct token *> &dependencies)
 221   {
 222
 223     observer_debug_printf ("Attaching observable %s to observer %s",
 224                            name, m_name);
 225
 226     m_observers.emplace_back (t, f, name, dependencies);
 227
 228     /* The observer has been inserted at the end of the vector, so it will be
 229        after any of its potential dependencies attached earlier.  If the
 230        observer has a token, it means that other observers can specify it as
 231        a dependency, so sorting is necessary to ensure those will be after the
 232        newly inserted observer afterwards.  */
 233     if (t != nullptr)
 234       sort_observers ();
 235   };
 236 };
 237
 238 } /* namespace observers */
 239
 240 } /* namespace gdb */
 241
 242 #endif /* COMMON_OBSERVABLE_H */