1 /* Observers 2 3 Copyright (C) 2016-2024 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 */ 252