From 69c88d165dfd3bf373a708d19bfedaa7672acec5 Mon Sep 17 00:00:00 2001 From: Carl Hetherington Date: Wed, 9 Nov 2011 17:44:39 +0000 Subject: Alert the user if a connection is made which causes feedback, and preserve the route graph in the state that it was in before the feedback was introduced. The intent being to simplify the code, reduce the number of areas of code which must consider feedback, and fix a few bugs. git-svn-id: svn://localhost/ardour2/branches/3.0@10510 d708f5d6-7413-0410-9779-e7cbd77b26cf --- libs/ardour/ardour/graph.h | 3 +- libs/ardour/ardour/route.h | 13 ++- libs/ardour/ardour/route_dag.h | 58 ---------- libs/ardour/ardour/route_graph.h | 78 +++++++++++++ libs/ardour/ardour/session.h | 14 ++- libs/ardour/graph.cc | 86 ++++---------- libs/ardour/route.cc | 20 ++-- libs/ardour/route_dag.cc | 199 -------------------------------- libs/ardour/route_graph.cc | 241 +++++++++++++++++++++++++++++++++++++++ libs/ardour/session.cc | 101 +++++++++++----- libs/ardour/session_process.cc | 12 +- libs/ardour/wscript | 2 +- 12 files changed, 459 insertions(+), 368 deletions(-) delete mode 100644 libs/ardour/ardour/route_dag.h create mode 100644 libs/ardour/ardour/route_graph.h delete mode 100644 libs/ardour/route_dag.cc create mode 100644 libs/ardour/route_graph.cc (limited to 'libs/ardour') diff --git a/libs/ardour/ardour/graph.h b/libs/ardour/ardour/graph.h index 14ef353853..f1ebba698a 100644 --- a/libs/ardour/ardour/graph.h +++ b/libs/ardour/ardour/graph.h @@ -46,6 +46,7 @@ class Graph; class Route; class Session; +class GraphEdges; typedef boost::shared_ptr node_ptr_t; @@ -61,7 +62,7 @@ public: void prep(); void trigger (GraphNode * n); - void rechain (boost::shared_ptr r); + void rechain (boost::shared_ptr, GraphEdges const &); void dump (int chain); void process(); diff --git a/libs/ardour/ardour/route.h b/libs/ardour/ardour/route.h index bc84fd9470..6df6934517 100644 --- a/libs/ardour/ardour/route.h +++ b/libs/ardour/ardour/route.h @@ -310,9 +310,17 @@ class Route : public SessionObject, public Automatable, public RouteGroupMember, /** * return true if this route feeds the first argument directly, via - * either its main outs or a send. + * either its main outs or a send. This is checked by the actual + * connections, rather than by what the graph is currently doing. */ - bool direct_feeds (boost::shared_ptr, bool* via_send_only = 0); + bool direct_feeds_according_to_reality (boost::shared_ptr, bool* via_send_only = 0); + + /** + * return true if this route feeds the first argument directly, via + * either its main outs or a send, according to the graph that + * is currently being processed. + */ + bool direct_feeds_according_to_graph (boost::shared_ptr, bool* via_send_only = 0); struct FeedRecord { boost::weak_ptr r; @@ -334,7 +342,6 @@ class Route : public SessionObject, public Automatable, public RouteGroupMember, const FedBy& fed_by() const { return _fed_by; } void clear_fed_by (); bool add_fed_by (boost::shared_ptr, bool sends_only); - bool not_fed() const { return _fed_by.empty(); } /* Controls (not all directly owned by the Route */ diff --git a/libs/ardour/ardour/route_dag.h b/libs/ardour/ardour/route_dag.h deleted file mode 100644 index c9ce08ba71..0000000000 --- a/libs/ardour/ardour/route_dag.h +++ /dev/null @@ -1,58 +0,0 @@ -/* - Copyright (C) 2011 Paul Davis - Author: Carl Hetherington - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - -*/ - -#include -#include - -namespace ARDOUR { - -typedef boost::shared_ptr DAGVertex; - -/** A list of edges for a directed acyclic graph for routes */ -class DAGEdges -{ -public: - typedef std::map > EdgeMap; - - void add (DAGVertex from, DAGVertex to); - std::set from (DAGVertex r) const; - void remove (DAGVertex from, DAGVertex to); - bool has_none_to (DAGVertex to) const; - bool empty () const; - void dump () const; - -private: - void insert (EdgeMap& e, DAGVertex a, DAGVertex b); - - /* Keep a map in both directions to speed lookups */ - - /** map of edges with from as `first' and to as `second' */ - EdgeMap _from_to; - /** map of the same edges with to as `first' and from as `second' */ - EdgeMap _to_from; -}; - -boost::shared_ptr topological_sort ( - boost::shared_ptr, - DAGEdges - ); - -} - diff --git a/libs/ardour/ardour/route_graph.h b/libs/ardour/ardour/route_graph.h new file mode 100644 index 0000000000..0b0af6c7dd --- /dev/null +++ b/libs/ardour/ardour/route_graph.h @@ -0,0 +1,78 @@ +/* + Copyright (C) 2011 Paul Davis + Author: Carl Hetherington + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + +*/ + +#ifndef __ardour_route_graph_h__ +#define __ardour_route_graph_h__ + +#include +#include + +namespace ARDOUR { + +typedef boost::shared_ptr GraphVertex; + +/** A list of edges for a directed graph for routes. + * + * It keeps the same data in a few different ways, with add() adding edges + * to all different representations, remove() removing similarly, and the + * lookup method using whichever representation is most efficient for + * that particular lookup. + * + * This may be a premature optimisation... + */ +class GraphEdges +{ +public: + typedef std::map > EdgeMap; + + void add (GraphVertex from, GraphVertex to, bool via_sends_only); + bool has (GraphVertex from, GraphVertex to, bool* via_sends_only); + std::set from (GraphVertex r) const; + void remove (GraphVertex from, GraphVertex to); + bool has_none_to (GraphVertex to) const; + bool empty () const; + void dump () const; + +private: + void insert (EdgeMap& e, GraphVertex a, GraphVertex b); + + typedef std::multimap > EdgeMapWithSends; + + EdgeMapWithSends::iterator find_in_from_to_with_sends (GraphVertex, GraphVertex); + + /** map of edges with from as `first' and to as `second' */ + EdgeMap _from_to; + /** map of the same edges with to as `first' and from as `second' */ + EdgeMap _to_from; + /** map of edges with via-sends information; first part of the map is + the `from' vertex, second is the `to' vertex and a flag which is + true if the edge is via a send only. + */ + EdgeMapWithSends _from_to_with_sends; +}; + +boost::shared_ptr topological_sort ( + boost::shared_ptr, + GraphEdges + ); + +} + +#endif diff --git a/libs/ardour/ardour/session.h b/libs/ardour/ardour/session.h index ad42ee768b..c0e9e304fc 100644 --- a/libs/ardour/ardour/session.h +++ b/libs/ardour/ardour/session.h @@ -56,6 +56,7 @@ #include "ardour/session_event.h" #include "ardour/location.h" #include "ardour/interpolation.h" +#include "ardour/route_graph.h" #ifdef HAVE_JACK_SESSION #include @@ -826,6 +827,12 @@ class Session : public PBD::StatefulDestructible, public PBD::ScopedConnectionLi std::list unknown_processors () const; + /** Emitted when a feedback cycle has been detected within Ardour's signal + processing path. Until it is fixed (by the user) some (unspecified) + routes will not be run. + */ + static PBD::Signal0 FeedbackDetected; + /* handlers can return an integer value: 0: config.set_audio_search_path() or config.set_midi_search_path() was used to modify the search path and we should try to find it again. @@ -1206,7 +1213,7 @@ class Session : public PBD::StatefulDestructible, public PBD::ScopedConnectionLi /* routes stuff */ - boost::shared_ptr route_graph; + boost::shared_ptr _process_graph; SerializedRCUManager routes; @@ -1500,6 +1507,11 @@ class Session : public PBD::StatefulDestructible, public PBD::ScopedConnectionLi boost::shared_ptr _speakers; void load_nested_sources (const XMLNode& node); + + /** The directed graph of routes that is currently being used for audio processing + and solo/mute computations. + */ + GraphEdges _current_route_graph; }; } // namespace ARDOUR diff --git a/libs/ardour/graph.cc b/libs/ardour/graph.cc index 8658d30828..7d75738e0b 100644 --- a/libs/ardour/graph.cc +++ b/libs/ardour/graph.cc @@ -276,45 +276,18 @@ Graph::restart_cycle() // starting with waking up the others. } -static bool -is_feedback (boost::shared_ptr routelist, Route* from, boost::shared_ptr to) -{ - for (RouteList::iterator ri=routelist->begin(); ri!=routelist->end(); ri++) { - if ((*ri).get() == from) { - return false; - } - if ((*ri) == to) { - return true; - } - } - - return false; -} - -static bool -is_feedback (boost::shared_ptr routelist, boost::shared_ptr from, Route* to) -{ - for (RouteList::iterator ri=routelist->begin(); ri!=routelist->end(); ri++) { - if ((*ri).get() == to) { - return true; - } - if ((*ri) == from) { - return false; - } - } - - return false; -} +/** Rechain our stuff using a list of routes (which can be in any order) and + * a directed graph of their interconnections, which is guaranteed to be + * acyclic. + */ void -Graph::rechain (boost::shared_ptr routelist) +Graph::rechain (boost::shared_ptr routelist, GraphEdges const & edges) { - node_list_t::iterator ni; Glib::Mutex::Lock ls (_swap_mutex); int chain = _setup_chain; DEBUG_TRACE (DEBUG::Graph, string_compose ("============== setup %1\n", chain)); - // set all refcounts to 0; /* This will become the number of nodes that do not feed any other node; once we have processed this number of those nodes, we have finished. @@ -337,53 +310,38 @@ Graph::rechain (boost::shared_ptr routelist) // now add refs for the connections. - for (ni=_nodes_rt[chain].begin(); ni!=_nodes_rt[chain].end(); ni++) { - - /* We will set this to true if the node *ni is directly or - indirectly fed by anything (without feedback) - */ - bool has_input = false; - - /* We will set this to true if the node *ni directly feeds - anything (without feedback) - */ - bool has_output = false; + for (node_list_t::iterator ni = _nodes_rt[chain].begin(); ni != _nodes_rt[chain].end(); ni++) { - /* We will also set up *ni's _activation_set to contain any nodes - that it directly feeds. - */ + boost::shared_ptr r = boost::dynamic_pointer_cast (*ni); - boost::shared_ptr rp = boost::dynamic_pointer_cast( *ni); + /* The routes that are directly fed by r */ + set fed_from_r = edges.from (r); - for (RouteList::iterator ri=routelist->begin(); ri!=routelist->end(); ri++) { - if (rp->direct_feeds (*ri)) { - if (is_feedback (routelist, rp.get(), *ri)) { - continue; - } + /* Hence whether r has an output */ + bool const has_output = !fed_from_r.empty (); - has_output = true; - (*ni)->_activation_set[chain].insert (*ri); - } - } + /* Set up r's activation set */ + for (set::iterator i = fed_from_r.begin(); i != fed_from_r.end(); ++i) { + r->_activation_set[chain].insert (*i); + } - for (Route::FedBy::iterator fi=rp->fed_by().begin(); fi!=rp->fed_by().end(); fi++) { - if (boost::shared_ptr r = fi->r.lock()) { - if (!is_feedback (routelist, r, rp.get())) { - has_input = true; - } - } - } + /* r has an input if there are some incoming edges to r in the graph */ + bool const has_input = !edges.has_none_to (r); /* Increment the refcount of any route that we directly feed */ - for (node_set_t::iterator ai=(*ni)->_activation_set[chain].begin(); ai!=(*ni)->_activation_set[chain].end(); ai++) { + for (node_set_t::iterator ai = r->_activation_set[chain].begin(); ai != r->_activation_set[chain].end(); ai++) { (*ai)->_init_refcount[chain] += 1; } if (!has_input) { + /* no input, so this node needs to be triggered initially to get things going */ _init_trigger_list[chain].push_back (*ni); } if (!has_output) { + /* no output, so this is one of the nodes that we can count off to decide + if we've finished + */ _init_finished_refcount[chain] += 1; } } diff --git a/libs/ardour/route.cc b/libs/ardour/route.cc index 0b5ccdc53d..d07faf506c 100644 --- a/libs/ardour/route.cc +++ b/libs/ardour/route.cc @@ -81,7 +81,7 @@ PBD::Signal0 Route::RemoteControlIDChange; Route::Route (Session& sess, string name, Flag flg, DataType default_type) : SessionObject (sess, name) , Automatable (sess) - , GraphNode (sess.route_graph) + , GraphNode (sess._process_graph) , _active (true) , _signal_latency (0) , _initial_delay (0) @@ -744,7 +744,7 @@ Route::set_solo_isolated (bool yn, void *src) } bool sends_only; - bool does_feed = direct_feeds (*i, &sends_only); // we will recurse anyway, so don't use ::feeds() + bool does_feed = direct_feeds_according_to_graph (*i, &sends_only); // we will recurse anyway, so don't use ::feeds() if (does_feed && !sends_only) { (*i)->set_solo_isolated (yn, (*i)->route_group()); @@ -2644,14 +2644,14 @@ Route::feeds (boost::shared_ptr other, bool* via_sends_only) } bool -Route::direct_feeds (boost::shared_ptr other, bool* only_send) +Route::direct_feeds_according_to_reality (boost::shared_ptr other, bool* via_send_only) { DEBUG_TRACE (DEBUG::Graph, string_compose ("Feeds? %1\n", _name)); if (_output->connected_to (other->input())) { DEBUG_TRACE (DEBUG::Graph, string_compose ("\tdirect FEEDS %2\n", other->name())); - if (only_send) { - *only_send = false; + if (via_send_only) { + *via_send_only = false; } return true; @@ -2665,8 +2665,8 @@ Route::direct_feeds (boost::shared_ptr other, bool* only_send) if ((iop = boost::dynamic_pointer_cast(*r)) != 0) { if (iop->feeds (other)) { DEBUG_TRACE (DEBUG::Graph, string_compose ("\tIOP %1 does feed %2\n", iop->name(), other->name())); - if (only_send) { - *only_send = true; + if (via_send_only) { + *via_send_only = true; } return true; } else { @@ -2682,6 +2682,12 @@ Route::direct_feeds (boost::shared_ptr other, bool* only_send) return false; } +bool +Route::direct_feeds_according_to_graph (boost::shared_ptr other, bool* via_send_only) +{ + return _session._current_route_graph.has (shared_from_this (), other, via_send_only); +} + /** Called from the (non-realtime) butler thread when the transport is stopped */ void Route::nonrealtime_handle_transport_stopped (bool /*abort_ignored*/, bool did_locate, bool can_flush_processors) diff --git a/libs/ardour/route_dag.cc b/libs/ardour/route_dag.cc deleted file mode 100644 index 3b13cf9415..0000000000 --- a/libs/ardour/route_dag.cc +++ /dev/null @@ -1,199 +0,0 @@ -/* - Copyright (C) 2011 Paul Davis - Author: Carl Hetherington - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - -*/ - -#include "ardour/route.h" -#include "ardour/route_dag.h" - -#include "i18n.h" - -using namespace std; -using namespace ARDOUR; - -void -DAGEdges::add (DAGVertex from, DAGVertex to) -{ - insert (_from_to, from, to); - insert (_to_from, to, from); - - EdgeMap::iterator i = _from_to.find (from); - if (i != _from_to.end ()) { - i->second.insert (to); - } else { - set v; - v.insert (to); - _from_to.insert (make_pair (from, v)); - } - -} - -set -DAGEdges::from (DAGVertex r) const -{ - EdgeMap::const_iterator i = _from_to.find (r); - if (i == _from_to.end ()) { - return set (); - } - - return i->second; -} - -void -DAGEdges::remove (DAGVertex from, DAGVertex to) -{ - EdgeMap::iterator i = _from_to.find (from); - assert (i != _from_to.end ()); - i->second.erase (to); - if (i->second.empty ()) { - _from_to.erase (i); - } - - EdgeMap::iterator j = _to_from.find (to); - assert (j != _to_from.end ()); - j->second.erase (from); - if (j->second.empty ()) { - _to_from.erase (j); - } -} - -/** @param to `To' route. - * @return true if there are no edges going to `to'. - */ - -bool -DAGEdges::has_none_to (DAGVertex to) const -{ - return _to_from.find (to) == _to_from.end (); -} - -bool -DAGEdges::empty () const -{ - assert (_from_to.empty () == _to_from.empty ()); - return _from_to.empty (); -} - -void -DAGEdges::dump () const -{ - for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) { - cout << "FROM: " << i->first->name() << " "; - for (set::const_iterator j = i->second.begin(); j != i->second.end(); ++j) { - cout << (*j)->name() << " "; - } - cout << "\n"; - } - - for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) { - cout << "TO: " << i->first->name() << " "; - for (set::const_iterator j = i->second.begin(); j != i->second.end(); ++j) { - cout << (*j)->name() << " "; - } - cout << "\n"; - } -} - -void -DAGEdges::insert (EdgeMap& e, DAGVertex a, DAGVertex b) -{ - EdgeMap::iterator i = e.find (a); - if (i != e.end ()) { - i->second.insert (b); - } else { - set v; - v.insert (b); - e.insert (make_pair (a, v)); - } -} - -struct RouteRecEnabledComparator -{ - bool operator () (DAGVertex r1, DAGVertex r2) const - { - if (r1->record_enabled()) { - if (r2->record_enabled()) { - /* both rec-enabled, just use signal order */ - return r1->order_key(N_("signal")) < r2->order_key(N_("signal")); - } else { - /* r1 rec-enabled, r2 not rec-enabled, run r2 early */ - return false; - } - } else { - if (r2->record_enabled()) { - /* r2 rec-enabled, r1 not rec-enabled, run r1 early */ - return true; - } else { - /* neither rec-enabled, use signal order */ - return r1->order_key(N_("signal")) < r2->order_key(N_("signal")); - } - } - } -}; - -/** Perform a topological sort of a list of routes using a directed graph representing connections. - * @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops). - */ -boost::shared_ptr -ARDOUR::topological_sort ( - boost::shared_ptr routes, - DAGEdges edges - ) -{ - boost::shared_ptr sorted_routes (new RouteList); - - /* queue of routes to process */ - RouteList queue; - - /* initial queue has routes that are not fed by anything */ - for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) { - if ((*i)->not_fed ()) { - queue.push_back (*i); - } - } - - /* Sort the initial queue so that non-rec-enabled routes are run first. - This is so that routes can record things coming from other routes - via external connections. - */ - queue.sort (RouteRecEnabledComparator ()); - - /* Do the sort: algorithm is Kahn's from Wikipedia. - `Topological sorting of large networks', Communications of the ACM 5(11):558-562. - */ - - while (!queue.empty ()) { - DAGVertex r = queue.front (); - queue.pop_front (); - sorted_routes->push_back (r); - set e = edges.from (r); - for (set::iterator i = e.begin(); i != e.end(); ++i) { - edges.remove (r, *i); - if (edges.has_none_to (*i)) { - queue.push_back (*i); - } - } - } - - if (!edges.empty ()) { - /* There are cycles in the graph, so we can't do a topological sort */ - return boost::shared_ptr (); - } - - return sorted_routes; -} diff --git a/libs/ardour/route_graph.cc b/libs/ardour/route_graph.cc new file mode 100644 index 0000000000..fbf406fd92 --- /dev/null +++ b/libs/ardour/route_graph.cc @@ -0,0 +1,241 @@ +/* + Copyright (C) 2011 Paul Davis + Author: Carl Hetherington + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + +*/ + +#include "ardour/route.h" +#include "ardour/route_graph.h" + +#include "i18n.h" + +using namespace std; +using namespace ARDOUR; + +void +GraphEdges::add (GraphVertex from, GraphVertex to, bool via_sends_only) +{ + insert (_from_to, from, to); + insert (_to_from, to, from); + + EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to); + if (i != _from_to_with_sends.end ()) { + i->second.second = via_sends_only; + } else { + _from_to_with_sends.insert ( + make_pair (from, make_pair (to, via_sends_only)) + ); + } +} + +/** Find a from/to pair in the _from_to_with_sends map. + * @return iterator to the edge, or _from_to_with_sends.end(). + */ +GraphEdges::EdgeMapWithSends::iterator +GraphEdges::find_in_from_to_with_sends (GraphVertex from, GraphVertex to) +{ + typedef EdgeMapWithSends::iterator Iter; + pair r = _from_to_with_sends.equal_range (from); + for (Iter i = r.first; i != r.second; ++i) { + if (i->second.first == to) { + return i; + } + } + + return _from_to_with_sends.end (); +} + +/** @param via_sends_only if non-0, filled in with true if the edge is a + * path via a send only. + * @return true if the given edge is present. + */ +bool +GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only) +{ + EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to); + if (i == _from_to_with_sends.end ()) { + return false; + } + + if (via_sends_only) { + *via_sends_only = i->second.second; + } + + return true; +} + +/** @return the vertices that are fed from `r' */ +set +GraphEdges::from (GraphVertex r) const +{ + EdgeMap::const_iterator i = _from_to.find (r); + if (i == _from_to.end ()) { + return set (); + } + + return i->second; +} + +void +GraphEdges::remove (GraphVertex from, GraphVertex to) +{ + EdgeMap::iterator i = _from_to.find (from); + assert (i != _from_to.end ()); + i->second.erase (to); + if (i->second.empty ()) { + _from_to.erase (i); + } + + EdgeMap::iterator j = _to_from.find (to); + assert (j != _to_from.end ()); + j->second.erase (from); + if (j->second.empty ()) { + _to_from.erase (j); + } + + EdgeMapWithSends::iterator k = find_in_from_to_with_sends (from, to); + assert (k != _from_to_with_sends.end ()); + _from_to_with_sends.erase (k); +} + +/** @param to `To' route. + * @return true if there are no edges going to `to'. + */ + +bool +GraphEdges::has_none_to (GraphVertex to) const +{ + return _to_from.find (to) == _to_from.end (); +} + +bool +GraphEdges::empty () const +{ + assert (_from_to.empty () == _to_from.empty ()); + return _from_to.empty (); +} + +void +GraphEdges::dump () const +{ + for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) { + cout << "FROM: " << i->first->name() << " "; + for (set::const_iterator j = i->second.begin(); j != i->second.end(); ++j) { + cout << (*j)->name() << " "; + } + cout << "\n"; + } + + for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) { + cout << "TO: " << i->first->name() << " "; + for (set::const_iterator j = i->second.begin(); j != i->second.end(); ++j) { + cout << (*j)->name() << " "; + } + cout << "\n"; + } +} + +/** Insert an edge into one of the EdgeMaps */ +void +GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b) +{ + EdgeMap::iterator i = e.find (a); + if (i != e.end ()) { + i->second.insert (b); + } else { + set v; + v.insert (b); + e.insert (make_pair (a, v)); + } +} + +struct RouteRecEnabledComparator +{ + bool operator () (GraphVertex r1, GraphVertex r2) const + { + if (r1->record_enabled()) { + if (r2->record_enabled()) { + /* both rec-enabled, just use signal order */ + return r1->order_key(N_("signal")) < r2->order_key(N_("signal")); + } else { + /* r1 rec-enabled, r2 not rec-enabled, run r2 early */ + return false; + } + } else { + if (r2->record_enabled()) { + /* r2 rec-enabled, r1 not rec-enabled, run r1 early */ + return true; + } else { + /* neither rec-enabled, use signal order */ + return r1->order_key(N_("signal")) < r2->order_key(N_("signal")); + } + } + } +}; + +/** Perform a topological sort of a list of routes using a directed graph representing connections. + * @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops). + */ +boost::shared_ptr +ARDOUR::topological_sort ( + boost::shared_ptr routes, + GraphEdges edges + ) +{ + boost::shared_ptr sorted_routes (new RouteList); + + /* queue of routes to process */ + RouteList queue; + + /* initial queue has routes that are not fed by anything */ + for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) { + if (edges.has_none_to (*i)) { + queue.push_back (*i); + } + } + + /* Sort the initial queue so that non-rec-enabled routes are run first. + This is so that routes can record things coming from other routes + via external connections. + */ + queue.sort (RouteRecEnabledComparator ()); + + /* Do the sort: algorithm is Kahn's from Wikipedia. + `Topological sorting of large networks', Communications of the ACM 5(11):558-562. + */ + + while (!queue.empty ()) { + GraphVertex r = queue.front (); + queue.pop_front (); + sorted_routes->push_back (r); + set e = edges.from (r); + for (set::iterator i = e.begin(); i != e.end(); ++i) { + edges.remove (r, *i); + if (edges.has_none_to (*i)) { + queue.push_back (*i); + } + } + } + + if (!edges.empty ()) { + edges.dump (); + /* There are cycles in the graph, so we can't do a topological sort */ + return boost::shared_ptr (); + } + + return sorted_routes; +} diff --git a/libs/ardour/session.cc b/libs/ardour/session.cc index 9aed414b1c..e940009e94 100644 --- a/libs/ardour/session.cc +++ b/libs/ardour/session.cc @@ -86,7 +86,7 @@ #include "ardour/recent_sessions.h" #include "ardour/region_factory.h" #include "ardour/return.h" -#include "ardour/route_dag.h" +#include "ardour/route_graph.h" #include "ardour/route_group.h" #include "ardour/send.h" #include "ardour/session.h" @@ -129,6 +129,7 @@ PBD::Signal0 Session::AutoBindingOff; PBD::Signal2 Session::Exported; PBD::Signal1 > Session::AskAboutPlaylistDeletion; PBD::Signal0 Session::Quit; +PBD::Signal0 Session::FeedbackDetected; static void clean_up_session_event (SessionEvent* ev) { delete ev; } const SessionEvent::RTeventCallback Session::rt_cleanup (clean_up_session_event); @@ -149,7 +150,7 @@ Session::Session (AudioEngine &eng, , _post_transport_work (0) , _send_timecode_update (false) , _all_route_group (new RouteGroup (*this, "all")) - , route_graph (new Graph(*this)) + , _process_graph (new Graph (*this)) , routes (new RouteList) , _total_free_4k_blocks (0) , _bundles (new BundleList) @@ -1293,7 +1294,7 @@ Session::resort_routes () /* writer goes out of scope and forces update */ } - //route_graph->dump(1); + //_process_graph->dump(1); #ifndef NDEBUG boost::shared_ptr rl = routes.reader (); @@ -1313,51 +1314,95 @@ Session::resort_routes () } +/** This is called whenever we need to rebuild the graph of how we will process + * routes. + * @param r List of routes, in any order. + */ + void Session::resort_routes_using (boost::shared_ptr r) { - DAGEdges edges; - + /* We are going to build a directed graph of our routes; + this is where the edges of that graph are put. + */ + + GraphEdges edges; + + /* Go through all routes doing two things: + * + * 1. Collect the edges of the route graph. Each of these edges + * is a pair of routes, one of which directly feeds the other + * either by a JACK connection or by an internal send. + * + * 2. Begin the process of making routes aware of which other + * routes directly or indirectly feed them. This information + * is used by the solo code. + */ + for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { + /* Clear out the route's list of direct or indirect feeds */ (*i)->clear_fed_by (); for (RouteList::iterator j = r->begin(); j != r->end(); ++j) { - /* although routes can feed themselves, it will - cause an endless recursive descent if we - detect it. so don't bother checking for - self-feeding. - */ - - if (*j == *i) { - continue; - } - bool via_sends_only; - if ((*j)->direct_feeds (*i, &via_sends_only)) { - edges.add (*j, *i); + /* See if this *j feeds *i according to the current state of the JACK + connections and internal sends. + */ + if ((*j)->direct_feeds_according_to_reality (*i, &via_sends_only)) { + /* add the edge to the graph (part #1) */ + edges.add (*j, *i, via_sends_only); + /* tell the route (for part #2) */ (*i)->add_fed_by (*j, via_sends_only); } } } - for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { - trace_terminal (*i, *i); - } - + /* Attempt a topological sort of the route graph */ boost::shared_ptr sorted_routes = topological_sort (r, edges); - route_graph->rechain (sorted_routes); + + if (sorted_routes) { + /* We got a satisfactory topological sort, so there is no feedback; + use this new graph. + + Note: the process graph rechain does not require a + topologically-sorted list, but hey ho. + */ + _process_graph->rechain (sorted_routes, edges); + _current_route_graph = edges; + + /* Complete the building of the routes' lists of what directly + or indirectly feeds them. + */ + for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { + trace_terminal (*i, *i); + } + + r = sorted_routes; #ifndef NDEBUG - DEBUG_TRACE (DEBUG::Graph, "Routes resorted, order follows:\n"); - for (RouteList::iterator i = sorted_routes->begin(); i != sorted_routes->end(); ++i) { - DEBUG_TRACE (DEBUG::Graph, string_compose ("\t%1 signal order %2\n", - (*i)->name(), (*i)->order_key ("signal"))); - } + DEBUG_TRACE (DEBUG::Graph, "Routes resorted, order follows:\n"); + for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { + DEBUG_TRACE (DEBUG::Graph, string_compose ("\t%1 signal order %2\n", + (*i)->name(), (*i)->order_key ("signal"))); + } #endif + } else { + /* The topological sort failed, so we have a problem. Tell everyone + and stick to the old graph; this will continue to be processed, so + until the feedback is fixed, what is played back will not quite + reflect what is actually connected. Note also that we do not + do trace_terminal here, as it would fail due to an endless recursion, + so the solo code will think that everything is still connected + as it was before. + */ + + FeedbackDetected (); /* EMIT SIGNAL */ + } + } /** Find a route name starting with \a base, maybe followed by the @@ -2174,7 +2219,7 @@ Session::remove_route (boost::shared_ptr route) */ resort_routes (); - route_graph->clear_other_chain (); + _process_graph->clear_other_chain (); /* get rid of it from the dead wood collection in the route list manager */ diff --git a/libs/ardour/session_process.cc b/libs/ardour/session_process.cc index 2384dd5fb3..33c4e5621c 100644 --- a/libs/ardour/session_process.cc +++ b/libs/ardour/session_process.cc @@ -107,9 +107,9 @@ Session::no_roll (pframes_t nframes) _click_io->silence (nframes); } - if (route_graph->threads_in_use() > 0) { + if (_process_graph->threads_in_use() > 0) { DEBUG_TRACE(DEBUG::ProcessThreads,"calling graph/no-roll\n"); - route_graph->routes_no_roll( nframes, _transport_frame, end_frame, non_realtime_work_pending(), declick); + _process_graph->routes_no_roll( nframes, _transport_frame, end_frame, non_realtime_work_pending(), declick); } else { for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { @@ -148,9 +148,9 @@ Session::process_routes (pframes_t nframes, bool& need_butler) using 1 thread. its needed because otherwise when we remove tracks, the graph never gets updated. */ - if (1 || route_graph->threads_in_use() > 0) { + if (1 || _process_graph->threads_in_use() > 0) { DEBUG_TRACE(DEBUG::ProcessThreads,"calling graph/process-routes\n"); - route_graph->process_routes (nframes, start_frame, end_frame, declick, need_butler); + _process_graph->process_routes (nframes, start_frame, end_frame, declick, need_butler); } else { for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { @@ -185,8 +185,8 @@ Session::silent_process_routes (pframes_t nframes, bool& need_butler) using 1 thread. its needed because otherwise when we remove tracks, the graph never gets updated. */ - if (1 || route_graph->threads_in_use() > 0) { - route_graph->silent_process_routes (nframes, start_frame, end_frame, need_butler); + if (1 || _process_graph->threads_in_use() > 0) { + _process_graph->silent_process_routes (nframes, start_frame, end_frame, need_butler); } else { for (RouteList::iterator i = r->begin(); i != r->end(); ++i) { diff --git a/libs/ardour/wscript b/libs/ardour/wscript index 9bde8abab2..5836af03ee 100644 --- a/libs/ardour/wscript +++ b/libs/ardour/wscript @@ -170,7 +170,7 @@ libardour_sources = [ 'return.cc', 'reverse.cc', 'route.cc', - 'route_dag.cc', + 'route_graph.cc', 'route_group.cc', 'route_group_member.cc', 'rb_effect.cc', -- cgit v1.2.3