rfnoc: Adding rfnoc_graph utilities

Adding graph_utils to keep rfnoc_graph utilities to contain helper
function and commonly used algorithms for the rfnoc_graph. These
functions aren't core to the rfnoc_graph's functionality, so we'll keep
them out of its API.

4 files changed, 203 insertions, 0 deletions

diff --git a/host/include/uhd/utils/CMakeLists.txt b/host/include/uhd/utils/CMakeLists.txt
index bf367f63d..b70de86ba 100644
--- a/host/include/uhd/utils/CMakeLists.txt
+++ b/host/include/uhd/utils/CMakeLists.txt
@@ -17,6 +17,7 @@ UHD_INSTALL(FILES
     fp_compare_delta.ipp
     fp_compare_epsilon.ipp
     gain_group.hpp
+    graph_utils.hpp
     log.hpp
     log_add.hpp
     math.hpp
diff --git a/host/include/uhd/utils/graph_utils.hpp b/host/include/uhd/utils/graph_utils.hpp
new file mode 100644
index 000000000..b2c61f78f
--- /dev/null
+++ b/host/include/uhd/utils/graph_utils.hpp
@@ -0,0 +1,68 @@
+//
+// Copyright 2019 Ettus Research, a National Instruments Branch
+//
+// SPDX-License-Identifier: GPL-3.0-or-later
+//
+
+#ifndef INCLUDED_UHD_UTILS_GRAPH_UTILS_HPP
+#define INCLUDED_UHD_UTILS_GRAPH_UTILS_HPP
+
+#include <uhd/config.hpp>
+#include <uhd/rfnoc/block_id.hpp>
+#include <uhd/rfnoc/defaults.hpp>
+#include <uhd/rfnoc/graph_edge.hpp>
+#include <uhd/rfnoc_graph.hpp>
+#include <boost/none.hpp>
+#include <boost/optional.hpp>
+#include <vector>
+
+
+namespace uhd { namespace rfnoc {
+
+//! Tuple that stores a block ID, as well as an optional port number
+using block_port_def = std::tuple<std::string, boost::optional<size_t>>;
+
+// TODO: Get rid of magic strings
+/*! List of blocks that can terminate chains. Note that some blocks only terminate at
+ *  some of their ports, so we can optionally include a port number.
+ */
+static const std::vector<block_port_def> TERMINATOR_BLOCKS{
+    {NODE_ID_SEP, boost::none}, {"Radio", boost::none}, {"NullSrcSink", 0}};
+
+/*!
+ *  Get a chain of blocks that statically connect back to a terminating block. This
+ *  vector's first element is `start_block`, and the chain continues from there.
+ *
+ *  This function does not make the connections between blocks, it simply traverses the
+ *  static connections.
+ *
+ *  \param graph The rfnoc_graph that is being examined
+ *  \param start_block The block we begin to build the chain from
+ *  \param port The block port of `src_port` that the path will begin at
+ *  \param source_block Whether or not the `start_block` is a source (or a destination).
+ *                      If true, the chain will start at `start_block`'s output port. If
+ *                      false, the chain will start with `start_block`'s output port.
+ *  \return The edge list representing the data path requested
+ */
+std::vector<graph_edge_t> UHD_API get_block_chain(const rfnoc_graph::sptr graph,
+    const block_id_t start_block,
+    const size_t port,
+    const bool source_chain);
+
+
+/*! Connect desired blocks by whatever path that can be found
+ *
+ *  \param src_blk Source block's ID
+ *  \param src_port Block port where the path starts
+ *  \param dst_blk Destination block's ID
+ *  \param dst_port Block port where the path ends
+ */
+void UHD_API connect_through_blocks(rfnoc_graph::sptr graph,
+    const block_id_t src_blk,
+    const size_t src_port,
+    const block_id_t dst_blk,
+    const size_t dst_port);
+
+}} // namespace uhd::rfnoc
+
+#endif /* INCLUDED_UHD_UTILS_GRAPH_UTILS_HPP */
diff --git a/host/lib/utils/CMakeLists.txt b/host/lib/utils/CMakeLists.txt
index 4369a8f11..5d1d22e9b 100644
--- a/host/lib/utils/CMakeLists.txt
+++ b/host/lib/utils/CMakeLists.txt
@@ -206,6 +206,7 @@ LIBUHD_APPEND_SOURCES(
     ${CMAKE_CURRENT_SOURCE_DIR}/compat_check.cpp
     ${CMAKE_CURRENT_SOURCE_DIR}/eeprom_utils.cpp
     ${CMAKE_CURRENT_SOURCE_DIR}/gain_group.cpp
+    ${CMAKE_CURRENT_SOURCE_DIR}/graph_utils.cpp
     ${CMAKE_CURRENT_SOURCE_DIR}/ihex.cpp
     ${CMAKE_CURRENT_SOURCE_DIR}/load_modules.cpp
     ${CMAKE_CURRENT_SOURCE_DIR}/log.cpp
diff --git a/host/lib/utils/graph_utils.cpp b/host/lib/utils/graph_utils.cpp
new file mode 100644
index 000000000..d6e82f546
--- /dev/null
+++ b/host/lib/utils/graph_utils.cpp
@@ -0,0 +1,133 @@
+//
+// Copyright 2019 Ettus Research, a National Instruments Branch
+//
+// SPDX-License-Identifier: GPL-3.0-or-later
+//
+
+#include <uhd/rfnoc/block_id.hpp>
+#include <uhd/rfnoc/defaults.hpp>
+#include <uhd/rfnoc/graph_edge.hpp>
+#include <uhd/rfnoc/noc_block_base.hpp>
+#include <uhd/utils/graph_utils.hpp>
+#include <uhd/utils/log.hpp>
+#include <boost/format.hpp>
+#include <numeric>
+#include <utility>
+
+
+namespace uhd { namespace rfnoc {
+
+
+//! Returns whether or not a block (and port) is know to to terminate data paths
+bool check_terminator_block(const block_id_t blk_id, const size_t port)
+{
+    const std::string blk_id_str = blk_id.get_block_name();
+    for (auto term_block : TERMINATOR_BLOCKS) {
+        auto optional_port = std::get<1>(term_block);
+        if (blk_id_str == std::get<0>(term_block)
+            && (!optional_port || port == optional_port.get())) {
+            return true;
+        }
+    }
+    return false;
+}
+
+
+std::vector<graph_edge_t> get_block_chain(const rfnoc_graph::sptr graph,
+    const block_id_t start_block,
+    const size_t port,
+    const bool source_chain)
+{
+    // Enumerate blocks in the chain
+    auto edges = graph->enumerate_static_connections();
+
+    std::vector<graph_edge_t> block_chain;
+    std::string current_block = start_block.to_string();
+    size_t current_port       = port;
+    while (true) {
+        UHD_LOG_TRACE("GRAPH_UTILS",
+            "Looking for current block " << current_block << ", port " << current_port);
+        bool next_found = false;
+        for (auto& edge : edges) {
+            if ((source_chain)
+                    ? (edge.src_blockid == current_block && edge.src_port == current_port)
+                    : (edge.dst_blockid == current_block
+                          && edge.dst_port == current_port)) {
+                // If the current block is the edge's source, make the edge's
+                // destination the current block
+                next_found = true;
+                UHD_LOG_TRACE("GRAPH_UTILS", "Found next block: " + edge.dst_blockid);
+
+                block_chain.push_back(edge);
+                current_block = (source_chain) ? edge.dst_blockid : edge.src_blockid;
+                current_port  = (source_chain) ? edge.dst_port : edge.src_port;
+                // Compare our current block and port
+                if (check_terminator_block(current_block, current_port)) {
+                    // If we've found a terminating block, stop iterating through the
+                    // edges
+                    break;
+                }
+            }
+        }
+        if (not next_found) {
+            UHD_LOG_TRACE(
+                "GRAPH_UTILS", "Failed to find current block in static connections");
+            break;
+        }
+        if (check_terminator_block(current_block, current_port)) {
+            // If we've found a terminating block, stop iterating through the edges
+            break;
+        }
+    }
+    return block_chain;
+}
+
+
+void connect_through_blocks(rfnoc_graph::sptr graph,
+    const block_id_t src_blk,
+    const size_t src_port,
+    const block_id_t dst_blk,
+    const size_t dst_port)
+{
+    // First, create a chain from the source block to a stream endpoint
+    auto block_chain = get_block_chain(graph, src_blk, src_port, true);
+    UHD_LOG_TRACE("GRAPH_UTILS", "Found source chain for " + src_blk.to_string());
+    // See if dst_blk is in our block_chain already
+    const bool dst_found = std::accumulate(block_chain.begin(),
+        block_chain.end(),
+        false,
+        [dst_blk, dst_port](bool dst_found, const graph_edge_t edge) {
+            // This is our "accumulator" function that checks if the current_blk's ID and
+            // input port match what we're looking for
+            return dst_found
+                   || (dst_blk.to_string() == edge.dst_blockid
+                          && dst_port == edge.dst_port);
+        });
+    // If our dst_blk is in the chain already, make sure its the last element and continue
+    if (dst_found) {
+        UHD_LOG_TRACE(
+            "GRAPH_UTILS", "Found dst_blk (" + dst_blk.to_string() + ") in source chain");
+        while (dst_blk.to_string() == block_chain.back().dst_blockid
+               && dst_port == block_chain.back().dst_port) {
+            UHD_LOG_TRACE("GRAPH_UTILS",
+                boost::format(
+                    "Last block (%s:%d) doesn't match dst_blk (%s:%d); removing.")
+                    % block_chain.back().dst_blockid % block_chain.back().dst_port
+                    % dst_blk.to_string() % dst_port);
+            block_chain.pop_back();
+        }
+    } else {
+        // If we hadn't found dst_blk, find it now, then merge the two chain
+        auto dest_chain = get_block_chain(graph, dst_blk, dst_port, false);
+        block_chain.insert(block_chain.end(), dest_chain.begin(), dest_chain.end());
+        UHD_LOG_TRACE(
+            "GRAPH_UTILS", "Found destination chain for " + dst_blk.to_string());
+    }
+
+    // Finally, make all of the connections in our chain
+    for (auto edge : block_chain) {
+        graph->connect(edge.src_blockid, edge.src_port, edge.dst_blockid, edge.dst_port);
+    }
+}
+
+}} // namespace uhd::rfnoc