aboutsummaryrefslogtreecommitdiffstats
path: root/sources
diff options
context:
space:
mode:
authorFriedemann Kleint <Friedemann.Kleint@qt.io>2024-12-05 12:58:20 +0100
committerFriedemann Kleint <Friedemann.Kleint@qt.io>2024-12-09 15:08:12 +0100
commit3da05cc765ab16b3622e2262022a40aa92fc0334 (patch)
tree247aa30bb678a8a3330e1bd60e7021a8452182e7 /sources
parentc76ffbfaf1e9257b9585ff935a33d334e3772892 (diff)
shiboken6: Prepare the graph used for topological for sorting classes without operator==()
The graph used an array of Node to represent edges, which is suitable only for small classes that have operator==(). Change the internal representation to use indexes for edges instead of the node classes and add an API for adding edges by index. Rewrite the visit() algorithm to create an index list instead of a node list. Move the Node from NodeEntry to a separate node list, which allows for copying it directly from the node list passed in. Task-number: PYSIDE-2946 Task-number: PYSIDE-454 Pick-to: 6.8 Change-Id: I7becd5caef226f50b77f5def2a62a2620d39ef8e Reviewed-by: Cristian Maureira-Fredes <cristian.maureira-fredes@qt.io>
Diffstat (limited to 'sources')
-rw-r--r--sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp2
-rw-r--r--sources/shiboken6/ApiExtractor/graph.h145
2 files changed, 89 insertions, 58 deletions
diff --git a/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp b/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp
index 45fa93906..b1b6fa764 100644
--- a/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp
+++ b/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp
@@ -3543,7 +3543,7 @@ static QList<std::shared_ptr<MetaClass> >
topologicalSortHelper(const QList<std::shared_ptr<MetaClass> > &classList,
const Dependencies &additionalDependencies)
{
- Graph<std::shared_ptr<MetaClass> > graph(classList.cbegin(), classList.cend());
+ Graph<std::shared_ptr<MetaClass> > graph(classList);
for (const auto &dep : additionalDependencies) {
if (!graph.addEdge(dep.parent, dep.child)) {
diff --git a/sources/shiboken6/ApiExtractor/graph.h b/sources/shiboken6/ApiExtractor/graph.h
index fa617dc1e..22936c201 100644
--- a/sources/shiboken6/ApiExtractor/graph.h
+++ b/sources/shiboken6/ApiExtractor/graph.h
@@ -34,14 +34,28 @@ struct GraphSortResult
template <class Node>
class Graph
{
+ using IndexList = QList<qsizetype>;
+
public:
using NodeList = QList<Node>;
Graph() = default;
- // Construct from a sequence of nodes
+ // Construct from a QList of nodes (unchecked, does not require operator==())
+ explicit Graph(const NodeList &list) : m_nodes(list)
+ {
+ m_nodeEntries.resize(list.size());
+ }
+
+ // Construct from a sequence of nodes (checks for duplicated nodes using operator==())
template<class It>
- explicit Graph(It i1, It i2) { setNodes(i1, i2); }
+ explicit Graph(It i1, It i2)
+ {
+ const auto size = std::distance(i1, i2);
+ m_nodes.reserve(size);
+ m_nodeEntries.reserve(size);
+ setNodes(i1, i2);
+ }
template<class It>
void setNodes(It i1, It i2)
@@ -53,22 +67,29 @@ public:
bool addNode(Node n);
/// Returns whether node was registered
- bool hasNode(Node node) { return indexOfNode(node) != -1; }
+ bool hasNode(Node node) { return m_nodes.contains(node); }
/// Returns the numbed of nodes in this graph.
qsizetype nodeCount() const { return m_nodeEntries.size(); }
/// Returns true if the graph contains the edge from -> to
bool containsEdge(Node from, Node to) const;
+ bool containsEdgeByIndexes(qsizetype fromIndex, qsizetype toIndex) const;
/// Returns true if the graph has any edges
bool hasEdges() const;
/// Adds an edge to this graph.
bool addEdge(Node from, Node to);
+ bool addEdgeByIndexes(qsizetype fromIndex, qsizetype toIndex);
/// Removes an edge from this graph.
bool removeEdge(Node from, Node to);
+ bool removeEdgeByIndexes(qsizetype fromIndex, qsizetype toIndex);
/// Clears the graph
- void clear() { m_nodeEntries.clear(); }
+ void clear()
+ {
+ m_nodes.clear();
+ m_nodeEntries.clear();
+ }
/// Dumps a dot graph to a file named \p filename.
/// \param fileName file name where the output should be written.
@@ -94,45 +115,33 @@ private:
struct NodeEntry
{
- Node node;
- NodeList targets;
- mutable Color color;
+ IndexList targets;
+ mutable Color color = WHITE;
};
Color colorAt(qsizetype i) const { return m_nodeEntries.at(i).color; }
- qsizetype indexOfNode(Node n) const;
- void depthFirstVisit(qsizetype i, NodeList &result) const;
+ void depthFirstVisit(qsizetype i, IndexList *result) const;
+ NodeList m_nodes;
QList<NodeEntry> m_nodeEntries;
};
template <class Node>
-qsizetype Graph<Node>::indexOfNode(Node n) const
-{
- for (qsizetype i = 0, size = m_nodeEntries.size(); i < size; ++i) {
- if (m_nodeEntries.at(i).node == n)
- return i;
- }
- return -1;
-}
-
-template <class Node>
bool Graph<Node>::addNode(Node n)
{
if (hasNode(n))
return false;
- m_nodeEntries.append({n, {}, WHITE});
+ m_nodes.append(n);
+ m_nodeEntries.append(NodeEntry{});
return true;
}
template <class Node>
-void Graph<Node>::depthFirstVisit(qsizetype i, NodeList &result) const
+void Graph<Node>::depthFirstVisit(qsizetype i, IndexList *result) const
{
m_nodeEntries[i].color = GRAY;
- for (auto to : m_nodeEntries[i].targets) {
- const qsizetype toIndex = indexOfNode(to);
- Q_ASSERT(toIndex != -1);
+ for (qsizetype toIndex : m_nodeEntries.at(i).targets) {
switch (colorAt(toIndex)) {
case WHITE:
depthFirstVisit(toIndex, result);
@@ -146,7 +155,7 @@ void Graph<Node>::depthFirstVisit(qsizetype i, NodeList &result) const
m_nodeEntries[i].color = BLACK;
- result.append(m_nodeEntries.at(i).node);
+ result->append(i);
}
template <class Node>
@@ -155,29 +164,29 @@ GraphSortResult<Node> Graph<Node>::topologicalSort() const
const qsizetype size = m_nodeEntries.size();
GraphSortResult<Node> result;
- result.result.reserve(size);
if (size > 1 && hasEdges()) {
+ result.result.reserve(size);
+ IndexList indexList;
+ indexList.reserve(size);
for (qsizetype i = 0; i < size; ++i)
m_nodeEntries[i].color = WHITE;
for (qsizetype i = 0; i < size; ++i) {
if (colorAt(i) == WHITE) // recursive calls may have set it to black
- depthFirstVisit(i, result.result);
+ depthFirstVisit(i, &indexList);
}
- } else { // no edges, shortcut
- std::transform(m_nodeEntries.cbegin(), m_nodeEntries.cend(),
- std::back_inserter(result.result),
- [](const NodeEntry &ne) { return ne.node; });
- }
-
- if (result.result.size() == size) {
- std::reverse(result.result.begin(), result.result.end());
- } else {
- for (const auto &nodeEntry : m_nodeEntries) {
- if (!result.result.contains(nodeEntry.node))
- result.cyclic.append(nodeEntry.node);
+ if (indexList.size() == size) { // Succeeded, all traversed
+ for (qsizetype i = size - 1; i >= 0; --i)
+ result.result.append(m_nodes.at(indexList.at(i)));
+ } else { // Cyclic, Not a DAG!
+ for (qsizetype i = 0; i < size; ++i) {
+ if (!indexList.contains(i))
+ result.cyclic.append(m_nodes.at(i));
+ }
}
- result.result.clear(); // Not a DAG!
+ } else { // no edges, shortcut. Legacy behavior: Also reverse in this case.
+ result.result = m_nodes;
+ std::reverse(result.result.begin(), result.result.end());
}
return result;
}
@@ -185,8 +194,14 @@ GraphSortResult<Node> Graph<Node>::topologicalSort() const
template <class Node>
bool Graph<Node>::containsEdge(Node from, Node to) const
{
- const qsizetype i = indexOfNode(from);
- return i != -1 && m_nodeEntries.at(i).targets.contains(to);
+ return containsEdgeByIndexes(m_nodes.indexOf(from), m_nodes.indexOf(to));
+}
+
+template <class Node>
+bool Graph<Node>::containsEdgeByIndexes(qsizetype fromIndex, qsizetype toIndex) const
+{
+ return fromIndex >= 0 && fromIndex < m_nodeEntries.size()
+ && m_nodeEntries.at(fromIndex).targets.contains(toIndex);
}
template <class Node>
@@ -199,24 +214,39 @@ bool Graph<Node>::hasEdges() const
template <class Node>
bool Graph<Node>::addEdge(Node from, Node to)
{
- const qsizetype i = indexOfNode(from);
- if (i == -1 || !hasNode(to) || m_nodeEntries.at(i).targets.contains(to))
+ return addEdgeByIndexes(m_nodes.indexOf(from), m_nodes.indexOf(to));
+}
+
+template <class Node>
+bool Graph<Node>::addEdgeByIndexes(qsizetype fromIndex, qsizetype toIndex)
+{
+ if (fromIndex < 0 || fromIndex >= m_nodeEntries.size()
+ || toIndex < 0 || toIndex >= m_nodeEntries.size()
+ || m_nodeEntries.at(fromIndex).targets.contains(toIndex)) {
return false;
- m_nodeEntries[i].targets.append(to);
+ }
+ m_nodeEntries[fromIndex].targets.append(toIndex);
return true;
}
template <class Node>
bool Graph<Node>::removeEdge(Node from, Node to)
{
- const qsizetype i = indexOfNode(from);
- if (i == -1)
+ return removeEdgeByIndexes(m_nodes.indexOf(from), m_nodes.indexOf(to));
+}
+
+template <class Node>
+bool Graph<Node>::removeEdgeByIndexes(qsizetype fromIndex, qsizetype toIndex)
+{
+ if (fromIndex < 0 || fromIndex >= m_nodeEntries.size()
+ || toIndex < 0 || toIndex >= m_nodeEntries.size()) {
return false;
- auto &targets = m_nodeEntries[i].targets;
- const qsizetype toIndex = targets.indexOf(to);
- if (toIndex == -1)
+ }
+ auto &targets = m_nodeEntries[fromIndex].targets;
+ const qsizetype toPos = targets.indexOf(toIndex);
+ if (toPos == -1)
return false;
- targets.removeAt(toIndex);
+ targets.removeAt(toPos);
return true;
}
@@ -239,11 +269,12 @@ void Graph<Node>::formatDot(QTextStream &s,
NameFunction nameFunction) const
{
s << "digraph D {\n";
- for (const auto &nodeEntry : m_nodeEntries) {
+ for (qsizetype i = 0, size = m_nodes.size(); i < size; ++i) {
+ const auto &nodeEntry = m_nodeEntries.at(i);
if (!nodeEntry.targets.isEmpty()) {
- const QString fromName = nameFunction(nodeEntry.node);
- for (const Node &to : nodeEntry.targets)
- s << '"' << fromName << "\" -> \"" << nameFunction(to) << "\"\n";
+ const QString fromName = nameFunction(m_nodes.at(i));
+ for (qsizetype i : nodeEntry.targets)
+ s << '"' << fromName << "\" -> \"" << nameFunction(m_nodes.at(i)) << "\"\n";
}
}
s << "}\n";
@@ -268,13 +299,13 @@ void Graph<Node>::format(QDebug &debug) const
const auto &nodeEntry = m_nodeEntries.at(i);
if (i)
debug << ", ";
- debug << nodeEntry.node;
+ debug << m_nodes.at(i);
if (!nodeEntry.targets.isEmpty()) {
debug << " -> [";
for (qsizetype t = 0, tsize = nodeEntry.targets.size(); t < tsize; ++t) {
if (t)
debug << ", ";
- debug << nodeEntry.targets.at(t);
+ debug << m_nodes.at(nodeEntry.targets.at(t));
}
debug << ']';
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-11 07:29:31 +0000