gdbsupport: allow to specify dependencies between observers

Previously, the observers attached to an observable were always notified
in the order in which they had been attached.  That order is not easily
controlled, because observers are typically attached in _initialize_*
functions, which are called in an undefined order.

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 (dependency_test_counters):
	New.
	(observer_token0, observer_token1, observer_token2,
	observer_token3, observer_token4, observer_token5): New.
	(struct dependency_observer_data): New struct.
	(observer_dependency_test_callback): New function.
	(test_observers): New.
	(run_dependency_test): New function.
	(test_dependency): New.
	(_initialize_observer_selftest): Register dependency test.

gdbsupport/ChangeLog:

	* 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.

Change-Id: I5399def1eeb69ca99e28c9f1fdf321d78b530bdb

1 files changed, 113 insertions, 0 deletions

diff --git a/gdb/unittests/observable-selftests.c b/gdb/unittests/observable-selftests.c
index 0e3b53f..b41a01e 100644
--- a/gdb/unittests/observable-selftests.c
+++ b/gdb/unittests/observable-selftests.c
@@ -30,6 +30,60 @@ 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;
+
+/* 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;
+
+  /* Name of the observer to use on attach.  */
+  const char *name;
+
+  /* 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;
+
+  /* Function to attach to the observable for this observer.  */
+  std::function<void (int)> callback;
+};
+
+static void observer_dependency_test_callback (size_t index);
+
+/* 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, "test0", {}, {},
+   [] (int) { observer_dependency_test_callback (0); }},
+  {&observer_token1, "test1", {0}, {0},
+   [] (int) { observer_dependency_test_callback (1); }},
+  {&observer_token2, "test2", {1}, {0, 1},
+   [] (int) { observer_dependency_test_callback (2); }},
+  {&observer_token3, "test3", {1}, {0, 1},
+   [] (int) { observer_dependency_test_callback (3); }},
+  {&observer_token4, "test4", {2, 3, 5}, {0, 1, 2, 3, 5},
+   [] (int) { observer_dependency_test_callback (4); }},
+  {&observer_token5, "test5", {0}, {0},
+   [] (int) { observer_dependency_test_callback (5); }},
+  {nullptr, "test6", {4}, {0, 1, 2, 3, 4, 5},
+   [] (int) { observer_dependency_test_callback (6); }},
+  {nullptr, "test7", {0}, {0},
+   [] (int) { observer_dependency_test_callback (7); }},
+};
+
 static void
 test_first_notification_function (int arg)
 {
@@ -63,6 +117,63 @@ 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.  Verify that the observer's dependencies have been notified before the
+   observer itself by checking their counters, then increase the observer's own
+   counter.  */
+static void
+observer_dependency_test_callback (size_t index)
+{
+  /* Check that dependencies have already been notified.  */
+  for (int i : test_observers[index].all_dependencies)
+    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)
+{
+  gdb::observers::observable<int> dependency_test_notification
+    ("dependency_test_notification");
+
+  /* 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[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[index].token);
+
+      if (o.token != nullptr)
+	dependency_test_notification.attach
+	  (o.callback, *o.token, o.name, dependency_tokens);
+      else
+	dependency_test_notification.attach (o.callback, o.name,
+					     dependency_tokens);
+    }
+
+  /* Notify observers, they check that their dependencies were notified.  */
+  dependency_test_notification.notify (1);
+}
+
+static void
+test_dependency ()
+{
+  /* 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});
+}
+
 static void
 run_tests ()
 {
@@ -133,4 +244,6 @@ _initialize_observer_selftest ()
 {
   selftests::register_test ("gdb::observers",
 			    selftests::observers::run_tests);
+  selftests::register_test ("gdb::observers dependency",
+			    selftests::observers::test_dependency);
 }