[PATCH v4 1/2] gdbsupport: Allow to specify dependencies between observers

[Michael Weghorn <m.weghorn@posteo.de>]

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<int> 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<int> 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<int> direct_dependencies;
+    // indices for all dependencies, including transitive ones
+    std::vector<int> all_dependencies;
+};
+
+/* Data for observers to use for dependency tests, using some sample
+   dependencies between the observers.  */
+static std::vector<dependency_observer_data> 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<std::function<void (int)>> 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<int> 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<int> insertion_order) {
+    // reset counters
+    dependency_test_counters = std::vector<int> (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<const gdb::observers::token *> 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<const struct token *> &dependencies)
+      : token (token), func (func), name (name), dependencies (dependencies)
     {}
 
     const struct token *token;
     func_type func;
     const char *name;
+    std::vector<const struct token *> 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<const struct token *> 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<const struct token *> 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<observer> 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<observer> &sorted_elems,
+                          std::vector<mark> &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<observer> sorted_elems;
+    std::vector<mark> 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<const struct token *> 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