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

2 files changed, 108 insertions, 16 deletions

diff --git a/gdbsupport/ChangeLog b/gdbsupport/ChangeLog
index 2734731..2b575ea 100644
--- a/gdbsupport/ChangeLog
+++ b/gdbsupport/ChangeLog
@@ -1,3 +1,11 @@
+2021-04-27  Michael Weghorn  <m.weghorn@posteo.de>
+	    Simon Marchi  <simon.marchi@polymtl.ca>
+
+	* 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.
+
 2021-04-24  Simon Marchi  <simon.marchi@polymtl.ca>
 
 	* observable.h (observer_debug_printf,
diff --git a/gdbsupport/observable.h b/gdbsupport/observable.h
index 4ba47bb..8ed5661 100644
--- a/gdbsupport/observable.h
+++ b/gdbsupport/observable.h
@@ -71,13 +71,15 @@ public:
 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:
@@ -88,30 +90,34 @@ public:
 
   DISABLE_COPY_AND_ASSIGN (observable);
 
-  /* Attach F as an observer to this observable.  F cannot be
-     detached.
+  /* Attach F as an observer to this observable.  F cannot be detached or
+     specified as a dependency.
+
+     DEPENDENCIES is a list of tokens of observers to be notified before this
+     one.
 
      NAME is the name of the observer, used for debug output purposes.  Its
      lifetime must be at least as long as the observer is attached.  */
-  void attach (const func_type &f, const char *name)
+  void attach (const func_type &f, const char *name,
+	       const 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.
+  /* Attach F as an observer to this observable.
+
+     T is a reference to a token that can be used to later remove F or specify F
+     as a dependency of another observer.
+
+     DEPENDENCIES is a list of tokens of observers to be notified before this
+     one.
 
      NAME is the name of the observer, used for debug output purposes.  Its
      lifetime must be at least as long as the observer is attached.  */
-  void attach (const func_type &f, const token &t, const char *name)
+  void attach (const func_type &f, const token &t, const char *name,
+	       const 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
@@ -149,6 +155,84 @@ private:
 
   std::vector<observer> m_observers;
   const char *m_name;
+
+  /* Use for sorting algorithm, to indicate which observer we have visited.  */
+  enum class visit_state
+  {
+    NOT_VISITED,
+    VISITING,
+    VISITED,
+  };
+
+  /* Helper method for topological sort using depth-first search algorithm.
+
+     Visit all dependencies of observer at INDEX in M_OBSERVERS (later referred
+     to as "the observer").  Then append the observer to SORTED_OBSERVERS.
+
+     If the observer is already visited, do nothing.  */
+  void visit_for_sorting (std::vector<observer> &sorted_observers,
+                          std::vector<visit_state> &visit_states, int index)
+  {
+    if (visit_states[index] == visit_state::VISITED)
+      return;
+
+    /* If we are already visiting this observer, it means there's a cycle.  */
+    gdb_assert (visit_states[index] != visit_state::VISITING);
+
+    visit_states[index] = visit_state::VISITING;
+
+    /* For each dependency of this observer...  */
+    for (const token *dep : m_observers[index].dependencies)
+      {
+	/* ... find the observer that has token DEP.  If found, visit it.  */
+        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_observers, visit_states, i);
+          }
+      }
+
+    visit_states[index] = visit_state::VISITED;
+    sorted_observers.push_back (m_observers[index]);
+  }
+
+  /* Sort the observers, so that dependencies come before observers
+     depending on them.
+
+     Uses depth-first search algorithm for topological sorting, see
+     https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search .  */
+  void sort_observers ()
+  {
+    std::vector<observer> sorted_observers;
+    std::vector<visit_state> visit_states (m_observers.size (),
+					   visit_state::NOT_VISITED);
+
+    for (size_t i = 0; i < m_observers.size (); i++)
+      visit_for_sorting (sorted_observers, visit_states, i);
+
+    m_observers = std::move (sorted_observers);
+  }
+
+  void attach (const func_type &f, const token *t, const char *name,
+               const 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);
+
+    /* The observer has been inserted at the end of the vector, so it will be
+       after any of its potential dependencies attached earlier.  If the
+       observer has a token, it means that other observers can specify it as
+       a dependency, so sorting is necessary to ensure those will be after the
+       newly inserted observer afterwards.  */
+    if (t != nullptr)
+      sort_observers ();
+  };
 };
 
 } /* namespace observers */