diff options
| -rw-r--r-- | CMakeLists.txt | 5 | ||||
| -rw-r--r-- | abstractmetabuilder.cpp | 69 | ||||
| -rw-r--r-- | graph.cpp | 130 | ||||
| -rw-r--r-- | graph.h | 68 | ||||
| -rw-r--r-- | tests/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | tests/testabstractmetaclass.cpp | 3 | ||||
| -rw-r--r-- | tests/testtoposort.cpp | 65 | ||||
| -rw-r--r-- | tests/testtoposort.h | 37 |
8 files changed, 333 insertions, 45 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index c46b7b261..0b6fcd8fb 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -2,7 +2,6 @@ project(apiextractor) cmake_minimum_required(VERSION 2.6) -find_package(Boost COMPONENTS graph REQUIRED) find_package(Qt4 4.5.0 REQUIRED) find_package(LibXml2 2.6.32 REQUIRED) @@ -37,6 +36,7 @@ docparser.cpp doxygenparser.cpp qtdocparser.cpp fileout.cpp +graph.cpp reporthandler.cpp typeparser.cpp typesystem.cpp @@ -71,7 +71,7 @@ include_directories(${CMAKE_CURRENT_SOURCE_DIR} ${CMAKE_CURRENT_BINARY_DIR} ${CMAKE_CURRENT_SOURCE_DIR}/parser ${CMAKE_CURRENT_SOURCE_DIR}/parser/rpp - ${QT_INCLUDE_DIR} ${Boost_INCLUDE_DIR} + ${QT_INCLUDE_DIR} ${LIBXSLT_INCLUDE_DIR} ${LIBXML2_INCLUDE_DIR} ) @@ -100,6 +100,7 @@ set(root_HEADERS apiextractormacros.h abstractmetalang.h apiextractor.h +graph.h reporthandler.h typesystem.h fileout.h diff --git a/abstractmetabuilder.cpp b/abstractmetabuilder.cpp index 549548da9..2d43cc2bd 100644 --- a/abstractmetabuilder.cpp +++ b/abstractmetabuilder.cpp @@ -33,22 +33,18 @@ #include "parser/parser.h" #include "parser/tokens.h" -#include <QtCore/QDebug> -#include <QtCore/QFile> -#include <QtCore/QFileInfo> -#include <QtCore/QTextCodec> -#include <QtCore/QTextStream> -#include <QtCore/QVariant> -#include <QtCore/QTime> -#include <QtCore/QQueue> - -// boost graph library -#include <boost/graph/topological_sort.hpp> -#include <boost/graph/adjacency_list.hpp> -#include <boost/graph/graph_traits.hpp> +#include <QDebug> +#include <QFile> +#include <QFileInfo> +#include <QTextCodec> +#include <QTextStream> +#include <QVariant> +#include <QTime> +#include <QQueue> +#include <QDir> #include <cstdio> -#include <QDir> +#include "graph.h" static QString stripTemplateArgs(const QString &name) { @@ -2585,11 +2581,7 @@ void AbstractMetaBuilder::dumpLog() AbstractMetaClassList AbstractMetaBuilder::classesTopologicalSorted(const AbstractMetaClass* cppClass) const { - using namespace boost; - - AbstractMetaClassList result; - QList<int> unmappedResult; - QSet<QPair<int, int> > deps; + QLinkedList<int> unmappedResult; QHash<QString, int> map; QHash<int, AbstractMetaClass*> reverseMap; @@ -2599,6 +2591,8 @@ AbstractMetaClassList AbstractMetaBuilder::classesTopologicalSorted(const Abstra else classList = m_metaClasses; + Graph graph(classList.count()); + int i = 0; foreach (AbstractMetaClass* clazz, classList) { map[clazz->name()] = i; @@ -2620,7 +2614,7 @@ AbstractMetaClassList AbstractMetaBuilder::classesTopologicalSorted(const Abstra clazz->baseClass()->enclosingClass() != clazz->enclosingClass()) { baseClassName = clazz->baseClass()->enclosingClass()->name(); } - deps << qMakePair(map[clazz->name()], map[baseClassName]); + graph.addEdge(map[baseClassName], map[clazz->name()]); } // interfaces... @@ -2639,7 +2633,7 @@ AbstractMetaClassList AbstractMetaBuilder::classesTopologicalSorted(const Abstra } if (!baseClassName.isNull() && baseClassName != clazz->name() && map.contains(baseClassName)) - deps << qMakePair(map[clazz->name()], map[baseClassName]); + graph.addEdge(map[baseClassName], map[clazz->name()]); } foreach (AbstractMetaFunction* func, clazz->functions()) { @@ -2654,33 +2648,22 @@ AbstractMetaClassList AbstractMetaBuilder::classesTopologicalSorted(const Abstra defaultExpression.replace(regex2, ""); } if (!defaultExpression.isEmpty() && defaultExpression != clazz->name() && map.contains(defaultExpression)) - deps << qMakePair(map[clazz->name()], map[defaultExpression]); + graph.addEdge(map[defaultExpression], map[clazz->name()]); } } } - // dot output for debug. -// typedef QPair<int, int> ABC; -// qDebug() << "digraph G { "; -// foreach (ABC p, deps) { -// TypeEntry* typeEntry = TypeDatabase::instance()->findType(reverseMap[p.second]->name()); -// if (typeEntry && !typeEntry->generateCode()) -// continue; -// qDebug() << reverseMap[p.first]->name() << " -> " << reverseMap[p.second]->name(); -// } -// qDebug() << "}"; - - - typedef adjacency_list <vecS, vecS, directedS> Graph; - Graph g(deps.begin(), deps.end(), classList.count()); - topological_sort(g, std::back_inserter(unmappedResult)); - - foreach (int i, unmappedResult) { - Q_ASSERT(reverseMap.contains(i)); - if (!reverseMap[i]->isInterface()) - result << reverseMap[i]; + AbstractMetaClassList result; + unmappedResult = graph.topologicalSort(); + if (unmappedResult.isEmpty()) { + ReportHandler::warning("Cyclic dependency found!"); + } else { + foreach (int i, unmappedResult) { + Q_ASSERT(reverseMap.contains(i)); + if (!reverseMap[i]->isInterface()) + result << reverseMap[i]; + } } - return result; } diff --git a/graph.cpp b/graph.cpp new file mode 100644 index 000000000..7ad7e9931 --- /dev/null +++ b/graph.cpp @@ -0,0 +1,130 @@ +/* +* This file is part of the API Extractor project. +* +* Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +* +* Contact: PySide team <contact@pyside.org> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* version 2 as published by the Free Software Foundation. +* +* 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., 51 Franklin St, Fifth Floor, Boston, MA +* 02110-1301 USA +* +*/ + +#include "graph.h" +#include <QVector> +#include <QDebug> +#include <QLinkedList> +#include <QSet> +#include <iterator> +#include <algorithm> +#include <iostream> +#include <QFile> + +struct Graph::GraphPrivate +{ + enum Color { WHITE, GRAY, BLACK }; + typedef QVector<QSet<int> > Edges; + typedef QSet<int>::const_iterator EdgeIterator; + + Edges edges; + + GraphPrivate(int numNodes) : edges(numNodes) + { + } + + void dfsVisit(int node, QLinkedList<int>& result, QVector<Color>& colors) const + { + colors[node] = GRAY; + EdgeIterator it = edges[node].begin(); + for (; it != edges[node].end(); ++it) { + if (colors[*it] == WHITE) + dfsVisit(*it, result, colors); + else if (colors[*it] == GRAY) // This is not a DAG! + return; + } + colors[node] = BLACK; + result.push_front(node); + } +}; + +Graph::Graph(int numNodes) : m_d(new GraphPrivate(numNodes)) +{ +} + +Graph::~Graph() +{ + delete m_d; +} + +int Graph::nodeCount() const +{ + return m_d->edges.size(); +} + +QLinkedList<int> Graph::topologicalSort() const +{ + int nodeCount = Graph::nodeCount(); + QLinkedList<int> result; + QVector<GraphPrivate::Color> colors(nodeCount, GraphPrivate::WHITE); + + for (int i = 0; i < nodeCount; ++i) { + if (colors[i] == GraphPrivate::WHITE) + m_d->dfsVisit(i, result, colors); + } + + // Not a DAG! + if (result.size() != nodeCount) + return QLinkedList<int>(); + return result; +} + +bool Graph::containsEdge(int from, int to) +{ + return m_d->edges[from].contains(to); +} + +void Graph::addEdge(int from, int to) +{ + Q_ASSERT(to < (int)m_d->edges.size()); + m_d->edges[from].insert(to); +} + +void Graph::removeEdge(int from, int to) +{ + m_d->edges[from].remove(to); +} + +void Graph::dump() const +{ + for (int i = 0; i < m_d->edges.size(); ++i) { + std::cout << i << " -> "; + std::copy(m_d->edges[i].begin(), m_d->edges[i].end(), std::ostream_iterator<int>(std::cout, " ")); + std::cout << std::endl; + } +} + +void Graph::dumpDot(const QHash< int, QString > nodeNames, const QString& fileName) const +{ + QFile output(fileName); + if (!output.open(QIODevice::WriteOnly)) + return; + QTextStream s(&output); + s << "digraph D {\n"; + for (int i = 0; i < m_d->edges.size(); ++i) { + GraphPrivate::EdgeIterator it = m_d->edges[i].begin(); + for (;it != m_d->edges[i].end(); ++it) + s << nodeNames[i] << " -> " << nodeNames[*it] << '\n'; + } + s << "}\n"; +} diff --git a/graph.h b/graph.h new file mode 100644 index 000000000..2cc0a8f43 --- /dev/null +++ b/graph.h @@ -0,0 +1,68 @@ +/* +* This file is part of the API Extractor project. +* +* Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +* +* Contact: PySide team <contact@pyside.org> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* version 2 as published by the Free Software Foundation. +* +* 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., 51 Franklin St, Fifth Floor, Boston, MA +* 02110-1301 USA +* +*/ + +#ifndef GRAPH_H +#define GRAPH_H + +#include <QLinkedList> +#include <QHash> +#include <QString> +#include "apiextractormacros.h" + +/// A graph that can have their nodes topologically sorted. +class APIEXTRACTOR_API Graph +{ +public: + /// Create a new graph with \p numNodes nodes. + Graph(int numNodes); + ~Graph(); + + /// Returns the numbed of nodes in this graph. + int nodeCount() const; + /// Returns true if the graph contains the edge from -> to + bool containsEdge(int from, int to); + /// Adds an edge to this graph. + void addEdge(int from, int to); + /// Removes an edge out of this graph. + void removeEdge(int from, int to); + /// Print this graph to stdout. + void dump() const; + /** + * Dumps a dot graph to a file named \p filename. + * \param nodeNames map used to translate node ids to human readable text. + * \param fileName file name where the output should be written. + */ + void dumpDot(const QHash<int, QString> nodeNames, const QString& fileName) const; + + /** + * Topologically sort this graph. + * \return A collection with all nodes topologically sorted or an empty collection if a ciclic dependency was found. + */ + QLinkedList<int> topologicalSort() const; +private: + + struct GraphPrivate; + GraphPrivate* m_d; +}; + +#endif diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt index 71efb9e90..10cce3fc7 100644 --- a/tests/CMakeLists.txt +++ b/tests/CMakeLists.txt @@ -22,3 +22,4 @@ declare_test(testmultipleinheritance) declare_test(testrefcounttag) declare_test(testremoveimplconv) declare_test(testreverseoperators) +declare_test(testtoposort) diff --git a/tests/testabstractmetaclass.cpp b/tests/testabstractmetaclass.cpp index 19f383c88..244caa0c4 100644 --- a/tests/testabstractmetaclass.cpp +++ b/tests/testabstractmetaclass.cpp @@ -47,6 +47,9 @@ void TestAbstractMetaClass::testClassNameUnderNamespace() TestUtil t(cppCode, xmlCode); AbstractMetaClassList classes = t.builder()->classes(); QCOMPARE(classes.count(), 2); // 1 namespace + 1 class + if (classes.first()->name() != "ClassName") + classes.swap(0, 1); + QCOMPARE(classes[0]->name(), QString("ClassName")); QCOMPARE(classes[0]->qualifiedCppName(), QString("Namespace::ClassName")); QCOMPARE(classes[1]->name(), QString("Namespace")); diff --git a/tests/testtoposort.cpp b/tests/testtoposort.cpp new file mode 100644 index 000000000..d33786720 --- /dev/null +++ b/tests/testtoposort.cpp @@ -0,0 +1,65 @@ +/* +* This file is part of the API Extractor project. +* +* Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +* +* Contact: PySide team <contact@pyside.org> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* version 2 as published by the Free Software Foundation. +* +* 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., 51 Franklin St, Fifth Floor, Boston, MA +* 02110-1301 USA +* +*/ + +#include "testtoposort.h" +#include <QtTest/QTest> +#include "graph.h" +#include <QDebug> + +void TestTopoSort::testTopoSort() +{ + QLinkedList<int> result; + { + Graph g(3); + g.addEdge(1, 2); + g.addEdge(0, 1); + result = g.topologicalSort(); + QCOMPARE(result.size(), 3); + QLinkedList<int>::iterator it = result.begin(); + QCOMPARE(*it, 0); + QCOMPARE(*(++it), 1); + QCOMPARE(*(++it), 2); + } + { + Graph g(2); + result = g.topologicalSort(); + QCOMPARE(result.size(), 2); + QLinkedList<int>::iterator it = result.begin(); + QCOMPARE(*it, 1); + QCOMPARE(*(++it), 0); + } +} + +void TestTopoSort::testCiclicGraph() +{ + Graph g(3); + g.addEdge(0, 1); + g.addEdge(1, 2); + g.addEdge(2, 0); + QLinkedList<int> result = g.topologicalSort(); + QVERIFY(result.isEmpty()); +} + +QTEST_APPLESS_MAIN(TestTopoSort) + +#include "testtoposort.moc" diff --git a/tests/testtoposort.h b/tests/testtoposort.h new file mode 100644 index 000000000..ad6447abd --- /dev/null +++ b/tests/testtoposort.h @@ -0,0 +1,37 @@ +/* +* This file is part of the API Extractor project. +* +* Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +* +* Contact: PySide team <contact@pyside.org> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* version 2 as published by the Free Software Foundation. +* +* 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., 51 Franklin St, Fifth Floor, Boston, MA +* 02110-1301 USA +* +*/ + +#ifndef TESTTOPOSORT_H +#define TESTTOPOSORT_H + +#include <QObject> + +class TestTopoSort : public QObject +{ +Q_OBJECT +private slots: + void testTopoSort(); + void testCiclicGraph(); +}; + +#endif |