From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) by sourceware.org (Postfix) with ESMTPS id 52819389681E for ; Thu, 22 Apr 2021 15:44:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 52819389681E Received: from submission (posteo.de [89.146.220.130]) by mout02.posteo.de (Postfix) with ESMTPS id B1DCB2400E5 for ; Thu, 22 Apr 2021 17:44:25 +0200 (CEST) Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4FR1tw6b2Zz9rxB; Thu, 22 Apr 2021 17:44:24 +0200 (CEST) From: Michael Weghorn To: gdb-patches@sourceware.org Cc: Michael Weghorn Subject: [PATCH v4 1/2] gdbsupport: Allow to specify dependencies between observers Date: Thu, 22 Apr 2021 15:44:10 +0000 Message-Id: <20210422154411.2788874-2-m.weghorn@posteo.de> In-Reply-To: <20210422154411.2788874-1-m.weghorn@posteo.de> References: <20210210154053.82927-1-m.weghorn@posteo.de> <20210422154411.2788874-1-m.weghorn@posteo.de> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-13.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 Apr 2021 15:44:29 -0000 Previously, the observers attached to an observable were always notified in the order in which they had been attached. However, an observer may require that another observer attached only later is called before itself is. Therefore, extend the 'observable' class to allow explicitly specifying dependencies when attaching observers, by adding the possibility to specify tokens for observers that it depends on. To make sure dependencies are notified before observers depending on them, the vector holding the observers is sorted in a way that dependencies come before observers depending on them. The current implementation for sorting uses the depth-first search algorithm for topological sorting as described at [1]. Extend the observable unit tests to cover this case as well. Check that this works for a few different orders in which the observers are attached. This newly introduced mechanism to explicitly specify dependencies will be used in a follow-up commit. [1] https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search Tested on x86_64-linux (Debian testing). gdb/ChangeLog: * unittests/observable-selftests.c (test_observer_dependency): New function. (struct dependency_observer_data): New struct. (run_dependency_test): New function. (run_tests): Extend by tests for dependencies between observers. gdbsupport/ChangeLog: * gdbsupport/observable.h (class observable): Extend to allow specifying dependencies between observers, keep vector holding observers sorted so that dependencies are notified before observers depending on them. --- gdb/unittests/observable-selftests.c | 102 +++++++++++++++++++++++++++ gdbsupport/observable.h | 96 +++++++++++++++++++++---- 2 files changed, 184 insertions(+), 14 deletions(-) diff --git a/gdb/unittests/observable-selftests.c b/gdb/unittests/observable-selftests.c index 0e3b53f555b..8ece37f2dfd 100644 --- a/gdb/unittests/observable-selftests.c +++ b/gdb/unittests/observable-selftests.c @@ -24,12 +24,64 @@ namespace selftests { namespace observers { +static void test_observer_dependency (size_t index); + static gdb::observers::observable test_notification ("test_notification"); static int test_first_observer = 0; static int test_second_observer = 0; static int test_third_observer = 0; + +/* Counters for observers used for dependency tests. */ +static std::vector dependency_test_counters; + +/* Tokens for observers used for dependency tests. */ +static gdb::observers::token observer_token0 {}; +static gdb::observers::token observer_token1 {}; +static gdb::observers::token observer_token2 {}; +static gdb::observers::token observer_token3 {}; +static gdb::observers::token observer_token4 {}; +static gdb::observers::token observer_token5 {}; +static gdb::observers::token observer_token6 {}; +static gdb::observers::token observer_token7 {}; + +/* Data for one observer used for checking that dependencies work as expected; + dependencies are specified using their indices into the 'test_observers' + vector here for simplicity and mapped to corresponding tokens later. */ +struct dependency_observer_data { + gdb::observers::token *token; + // indices of observers that this one directly depends on + std::vector direct_dependencies; + // indices for all dependencies, including transitive ones + std::vector all_dependencies; +}; + +/* Data for observers to use for dependency tests, using some sample + dependencies between the observers. */ +static std::vector test_observers = { + {&observer_token0, {}, {}}, + {&observer_token1, {0}, {0}}, + {&observer_token2, {1}, {0, 1}}, + {&observer_token3, {1}, {0, 1}}, + {&observer_token4, {2, 3, 5}, {0, 1, 2, 3, 5}}, + {&observer_token5, {0}, {0}}, + {&observer_token6, {4}, {0, 1, 2, 3, 4, 5}}, + {&observer_token7, {0}, {0}} +}; + +/* Function to call for each observer when notified. */ +static std::vector> test_notification_functions = { + [](int) { test_observer_dependency(0); }, + [](int) { test_observer_dependency(1); }, + [](int) { test_observer_dependency(2); }, + [](int) { test_observer_dependency(3); }, + [](int) { test_observer_dependency(4); }, + [](int) { test_observer_dependency(5); }, + [](int) { test_observer_dependency(6); }, + [](int) { test_observer_dependency(7); }, +}; + static void test_first_notification_function (int arg) { @@ -63,6 +115,51 @@ notify_check_counters (int one, int two, int three) SELF_CHECK (three == test_third_observer); } +/* Function for each observer to run when being notified during the + dependency tests. Verifies that dependencies have been notified earlier + by checking their counters, then increases the own counter. */ +static void +test_observer_dependency (size_t index) +{ + // check that dependencies have already been notified + std::vector deps = test_observers.at(index).all_dependencies; + for (int i : deps) { + SELF_CHECK (dependency_test_counters[i] == 1); + } + // increase own counter + dependency_test_counters[index]++; +} + +/* Run a dependency test by attaching the observers in the specified order + then notifying them. */ +static void +run_dependency_test (std::vector insertion_order) { + // reset counters + dependency_test_counters = std::vector (test_observers.size(), 0); + + // attach all observers in the given order, specifying dependencies + for (int i : insertion_order) { + const dependency_observer_data &o = test_observers.at(i); + + // get tokens for dependencies using their indices + std::vector dependency_tokens; + for (int index : o.all_dependencies) { + dependency_tokens.emplace_back (test_observers.at(index).token); + } + + test_notification.attach (test_notification_functions.at (i), + *o.token, "test", dependency_tokens); + } + + // notify observers, they check that their dependencies were notified + test_notification.notify (1); + + // detach all observers again + for (dependency_observer_data &o: test_observers) { + test_notification.detach (*o.token); + } +} + static void run_tests () { @@ -122,6 +219,11 @@ run_tests () /* Remove first observer, no more observers. */ test_notification.detach (token1); notify_check_counters (0, 0, 0); + + /* Run dependency tests with different insertion orders. */ + run_dependency_test ({0, 1, 2, 3, 4, 5, 6, 7}); + run_dependency_test ({7, 6, 5, 4, 3, 2, 1, 0}); + run_dependency_test ({0, 3, 2, 1, 7, 6, 4, 5}); } } /* namespace observers */ diff --git a/gdbsupport/observable.h b/gdbsupport/observable.h index c9b3bb7333e..0e263e49192 100644 --- a/gdbsupport/observable.h +++ b/gdbsupport/observable.h @@ -66,13 +66,15 @@ class observable private: struct observer { - observer (const struct token *token, func_type func, const char *name) - : token (token), func (func), name (name) + observer (const struct token *token, func_type func, const char *name, + const std::vector &dependencies) + : token (token), func (func), name (name), dependencies (dependencies) {} const struct token *token; func_type func; const char *name; + std::vector dependencies; }; public: @@ -84,23 +86,20 @@ class observable DISABLE_COPY_AND_ASSIGN (observable); /* Attach F as an observer to this observable. F cannot be - detached. */ - void attach (const func_type &f, const char *name) + detached or specified as a dependency. */ + void attach (const func_type &f, const char *name, + std::vector dependencies = {}) { - observer_debug_printf ("Attaching observable %s to observer %s", - name, m_name); - - m_observers.emplace_back (nullptr, f, name); + attach (f, nullptr, name, dependencies); } /* Attach F as an observer to this observable. T is a reference to - a token that can be used to later remove F. */ - void attach (const func_type &f, const token &t, const char *name) + a token that can be used to later remove F. Dependencies will be notified + before the observer depending on them. */ + void attach (const func_type &f, const token &t, const char *name, + std::vector dependencies = {}) { - observer_debug_printf ("Attaching observable %s to observer %s", - name, m_name); - - m_observers.emplace_back (&t, f, name); + attach (f, &t, name, dependencies); } /* Remove observers associated with T from this observable. T is @@ -134,6 +133,75 @@ class observable std::vector m_observers; const char *m_name; + + /* Use for sorting algorithm. */ + enum class mark + { + NOT_VISITED, + VISITED, + VISITING + }; + + /* Helper method for topological sort using depth-first search algorithm */ + void visit_for_sorting (std::vector &sorted_elems, + std::vector &marks, int index) + { + if (marks[index] == mark::VISITED) + return; + + /* If we already visited this observer, it means there's a cycle. */ + gdb_assert (marks[index] != mark::VISITING); + + marks[index] = mark::VISITING; + + for (const token *dep : m_observers[index].dependencies) + { + auto it_dep + = std::find_if (m_observers.begin (), m_observers.end (), + [&] (observer o) { return o.token == dep; }); + if (it_dep != m_observers.end ()) + { + int i = std::distance (m_observers.begin (), it_dep); + visit_for_sorting (sorted_elems, marks, i); + } + } + + marks[index] = mark::VISITED; + sorted_elems.push_back (m_observers[index]); + } + + /* Sorts the elements, so that dependencies come before observers + depending on them. + + Currently uses depth-first search algorithm for topological sorting, s. + https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search . */ + void sort_elements () + { + std::vector sorted_elems; + std::vector marks (m_observers.size (), mark::NOT_VISITED); + + for (size_t i = 0; i < m_observers.size (); i++) + visit_for_sorting (sorted_elems, marks, i); + + // assign sorted result + m_observers = std::move (sorted_elems); + } + + void attach (const func_type &f, const token *t, const char *name, + std::vector dependencies) + { + + observer_debug_printf ("Attaching observable %s to observer %s", + name, m_name); + + m_observers.emplace_back (t, f, name, dependencies); + + if (t != nullptr) + { + // other observers might depend on this one -> sort anew + sort_elements (); + } + }; }; } /* namespace observers */ -- 2.30.2