[Shader Graph Gen.] Introduce QShaderGraph::Statement

This is our "byte code" representing a flattened graph. It will be used
as input for the code generation.

Change-Id: Ie02a60d07c035f3d16872e79931eb7cde168a8d1
Reviewed-by: Sean Harmer <sean.harmer@kdab.com>

2 files changed, 170 insertions, 0 deletions

diff --git a/src/gui/util/qshadergraph.cpp b/src/gui/util/qshadergraph.cpp
index 0735c3cfe3..5379e6ed7a 100644
--- a/src/gui/util/qshadergraph.cpp
+++ b/src/gui/util/qshadergraph.cpp
@@ -41,6 +41,101 @@
 
 QT_BEGIN_NAMESPACE
 
+
+namespace
+{
+    QVector<QShaderNode> copyOutputNodes(const QVector<QShaderNode> &nodes)
+    {
+        auto res = QVector<QShaderNode>();
+        std::copy_if(nodes.cbegin(), nodes.cend(),
+                     std::back_inserter(res),
+                     [] (const QShaderNode &node) {
+                         return node.type() == QShaderNode::Output;
+                     });
+        return res;
+    }
+
+    QVector<QShaderGraph::Edge> incomingEdges(const QVector<QShaderGraph::Edge> &edges, const QUuid &uuid)
+    {
+        auto res = QVector<QShaderGraph::Edge>();
+        std::copy_if(edges.cbegin(), edges.cend(),
+                     std::back_inserter(res),
+                     [uuid] (const QShaderGraph::Edge &edge) {
+                         return edge.sourceNodeUuid == uuid;
+                     });
+        return res;
+    }
+
+    QVector<QShaderGraph::Edge> outgoingEdges(const QVector<QShaderGraph::Edge> &edges, const QUuid &uuid)
+    {
+        auto res = QVector<QShaderGraph::Edge>();
+        std::copy_if(edges.cbegin(), edges.cend(),
+                     std::back_inserter(res),
+                     [uuid] (const QShaderGraph::Edge &edge) {
+                         return edge.targetNodeUuid == uuid;
+                     });
+        return res;
+    }
+
+    QShaderGraph::Statement nodeToStatement(const QShaderNode &node, int &nextVarId)
+    {
+        auto statement = QShaderGraph::Statement();
+        statement.node = node;
+
+        const auto ports = node.ports();
+        for (const auto &port : ports) {
+            if (port.direction == QShaderNodePort::Input) {
+                statement.inputs.append(-1);
+            } else {
+                statement.outputs.append(nextVarId);
+                nextVarId++;
+            }
+        }
+        return statement;
+    }
+
+    QShaderGraph::Statement completeStatement(const QHash<QUuid, QShaderGraph::Statement> &idHash,
+                                              const QVector<QShaderGraph::Edge> edges,
+                                              const QUuid &uuid)
+    {
+        auto targetStatement = idHash.value(uuid);
+        for (const auto &edge : edges) {
+            if (edge.targetNodeUuid != uuid)
+                continue;
+
+            const auto sourceStatement = idHash.value(edge.sourceNodeUuid);
+            const auto sourcePortIndex = sourceStatement.portIndex(QShaderNodePort::Output, edge.sourcePortName);
+            const auto targetPortIndex = targetStatement.portIndex(QShaderNodePort::Input, edge.targetPortName);
+
+            if (sourcePortIndex < 0 || targetPortIndex < 0)
+                continue;
+
+            const auto &sourceOutputs = sourceStatement.outputs;
+            auto &targetInputs = targetStatement.inputs;
+            targetInputs[targetPortIndex] = sourceOutputs[sourcePortIndex];
+        }
+        return targetStatement;
+    }
+}
+
+QUuid QShaderGraph::Statement::uuid() const Q_DECL_NOTHROW
+{
+    return node.uuid();
+}
+
+int QShaderGraph::Statement::portIndex(QShaderNodePort::Direction direction, const QString &portName) const Q_DECL_NOTHROW
+{
+    const auto ports = node.ports();
+    int index = 0;
+    for (const auto &port : ports) {
+        if (port.name == portName && port.direction == direction)
+            return index;
+        else if (port.direction == direction)
+            index++;
+    }
+    return -1;
+}
+
 void QShaderGraph::addNode(const QShaderNode &node)
 {
     removeNode(node);
@@ -77,6 +172,52 @@ QVector<QShaderGraph::Edge> QShaderGraph::edges() const Q_DECL_NOTHROW
     return m_edges;
 }
 
+QVector<QShaderGraph::Statement> QShaderGraph::createStatements() const
+{
+    const auto idHash = [this] {
+        auto nextVarId = 0;
+        auto res = QHash<QUuid, Statement>();
+        for (const auto &node : qAsConst(m_nodes))
+            res.insert(node.uuid(), nodeToStatement(node, nextVarId));
+        return res;
+    }();
+
+    auto result = QVector<Statement>();
+    auto currentEdges = m_edges;
+    auto currentUuids = [this] {
+        const auto inputs = copyOutputNodes(m_nodes);
+        auto res = QVector<QUuid>();
+        std::transform(inputs.cbegin(), inputs.cend(),
+                       std::back_inserter(res),
+                       [](const QShaderNode &node) { return node.uuid(); });
+        return res;
+    }();
+
+    // Implements Kahn's algorithm to flatten the graph
+    // https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
+    //
+    // We implement it with a small twist though, we follow the edges backward
+    // because we want to track the dependencies from the output nodes and not the
+    // input nodes
+    while (!currentUuids.isEmpty()) {
+        const auto uuid = currentUuids.takeFirst();
+        result.append(completeStatement(idHash, m_edges, uuid));
+
+        const auto outgoing = outgoingEdges(currentEdges, uuid);
+        for (const auto &outgoingEdge : outgoing) {
+            currentEdges.removeAll(outgoingEdge);
+            const QUuid nextUuid = outgoingEdge.sourceNodeUuid;
+            const auto incoming = incomingEdges(currentEdges, nextUuid);
+            if (incoming.isEmpty()) {
+                currentUuids.append(nextUuid);
+            }
+        }
+    }
+
+    std::reverse(result.begin(), result.end());
+    return result;
+}
+
 bool operator==(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &rhs) Q_DECL_NOTHROW
 {
     return lhs.sourceNodeUuid == rhs.sourceNodeUuid
@@ -85,4 +226,11 @@ bool operator==(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &rhs) Q_
         && lhs.targetPortName == rhs.targetPortName;
 }
 
+bool operator==(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) Q_DECL_NOTHROW
+{
+    return lhs.inputs == rhs.inputs
+        && lhs.outputs == rhs.outputs
+        && lhs.node.uuid() == rhs.node.uuid();
+}
+
 QT_END_NAMESPACE
diff --git a/src/gui/util/qshadergraph_p.h b/src/gui/util/qshadergraph_p.h
index c582dcd18b..fd8ddf6e05 100644
--- a/src/gui/util/qshadergraph_p.h
+++ b/src/gui/util/qshadergraph_p.h
@@ -69,6 +69,17 @@ public:
         QString targetPortName;
     };
 
+    class Statement
+    {
+    public:
+        Q_GUI_EXPORT QUuid uuid() const Q_DECL_NOTHROW;
+        Q_GUI_EXPORT int portIndex(QShaderNodePort::Direction direction, const QString &portName) const Q_DECL_NOTHROW;
+
+        QShaderNode node;
+        QVector<int> inputs;
+        QVector<int> outputs;
+    };
+
     Q_GUI_EXPORT void addNode(const QShaderNode &node);
     Q_GUI_EXPORT void removeNode(const QShaderNode &node);
     Q_GUI_EXPORT QVector<QShaderNode> nodes() const Q_DECL_NOTHROW;
@@ -77,6 +88,8 @@ public:
     Q_GUI_EXPORT void removeEdge(const Edge &edge);
     Q_GUI_EXPORT QVector<Edge> edges() const Q_DECL_NOTHROW;
 
+    Q_GUI_EXPORT QVector<Statement> createStatements() const;
+
 private:
     QVector<QShaderNode> m_nodes;
     QVector<Edge> m_edges;
@@ -89,12 +102,21 @@ inline bool operator!=(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &
     return !(lhs == rhs);
 }
 
+Q_GUI_EXPORT bool operator==(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) Q_DECL_NOTHROW;
+
+inline bool operator!=(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) Q_DECL_NOTHROW
+{
+    return !(lhs == rhs);
+}
+
 Q_DECLARE_TYPEINFO(QShaderGraph, Q_MOVABLE_TYPE);
 Q_DECLARE_TYPEINFO(QShaderGraph::Edge, Q_MOVABLE_TYPE);
+Q_DECLARE_TYPEINFO(QShaderGraph::Statement, Q_MOVABLE_TYPE);
 
 QT_END_NAMESPACE
 
 Q_DECLARE_METATYPE(QShaderGraph)
 Q_DECLARE_METATYPE(QShaderGraph::Edge)
+Q_DECLARE_METATYPE(QShaderGraph::Statement)
 
 #endif // QSHADERGRAPH_P_H