Skip to content

Fix: AbstractMetaBuilder::classesTopologicalSorted #148

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
mrbean-bremen merged 2 commits into from
Nov 10, 2023
Merged

Fix: AbstractMetaBuilder::classesTopologicalSorted #148

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
246ba52
Fix: AbstractMetaBuilder::classesTopologicalSorted
jbowler Nov 9, 2023
55e22c0
Fix for Qt5 compat, comment update
jbowler Nov 10, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
153 changes: 105 additions & 48 deletions generator/abstractmetabuilder.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2480,55 +2480,112 @@ void AbstractMetaBuilder::dumpLog()

AbstractMetaClassList AbstractMetaBuilder::classesTopologicalSorted() const
{
AbstractMetaClassList res;

AbstractMetaClassList classes = m_meta_classes;
classes.sort();

QSet<AbstractMetaClass*> noDependency;
QHash<AbstractMetaClass*, QSet<AbstractMetaClass* >* > hash;
for (AbstractMetaClass *cls : classes) {
QSet<AbstractMetaClass* > *depends = new QSet<AbstractMetaClass* >();
/* This function is the standard topological sort of a Directed Acyclic
* Graph (a DAG). It outputs a partially ordered list of the nodes in the
* graph such that a node is output after all of its children.
*
* In the previous implementation it seemed to account for around 68-69% of
* the entire run time of pythonqt_generator however this might be an
* artefact of the profiling technique used as these changes make not
* significant difference to the run time of the generator.
*
* However the previous implementation also leaked memory and modified a
* QHash while iterating over it with a QHashIterator; a potentially fatal
* "use after free".
*
* This version is somewhat like the python equivalent using list
* comprehensions.
*/

/* Build a hash list of QSet<class> for each class. 'class' is represented
* by a pointer to the AbstractMetaClass from m_meta_classes.
*/
ReportHandler::debugSparse(QString("TSORT: %1 meta classes")
.arg(m_meta_classes.count()));
QHash<AbstractMetaClass*, QSet<AbstractMetaClass*>> classes;
classes.reserve(m_meta_classes.count());

for (auto cls : m_meta_classes) {
Comment thread
mrbean-bremen marked this conversation as resolved.
/* Add the baseClass and the interfaces the class uses. The latter
* are stored in an AbstractMetaClassList which is uses a QList, so:
*/
auto entry(classes.insert(cls,
# if QT_VERSION < QT_VERSION_CHECK(5,14,0)
QSet<AbstractMetaClass*>::fromList(cls->interfaces())
# else
QSet<AbstractMetaClass*>(cls->interfaces().cbegin(),
cls->interfaces().cend())
# endif
));

if (cls->baseClass())
depends->insert(cls->baseClass());

for (AbstractMetaClass *interface : cls->interfaces()) {
AbstractMetaClass *impl = interface->primaryInterfaceImplementor();
if (impl == cls)
continue;
depends->insert(impl);
}

if (depends->empty()) {
noDependency.insert(cls);
} else {
hash.insert(cls, depends);
}
}

while (!noDependency.empty()) {
for (AbstractMetaClass *cls : noDependency.values()) {
if(!cls->isInterface())
res.append(cls);
noDependency.remove(cls);
QHashIterator<AbstractMetaClass*, QSet<AbstractMetaClass* >* > i(hash);
while (i.hasNext()) {
i.next();
i.value()->remove(cls);
if (i.value()->empty()) {
AbstractMetaClass *key = i.key();
noDependency.insert(key);
hash.remove(key);
delete(i.value());
}
}
}
}

if (!noDependency.empty() || !hash.empty()) {
qWarning("dependency graph was cyclic.");
}
entry.value().insert(cls->baseClass());
entry.value().remove(cls); // may come from interfaces
}

/* This and the qFatals below are fatal internal errors in the code of
* pythonqt_generator.
*/
if (m_meta_classes.count() != classes.count())
qFatal("TOPO SORT: duplicate meta classes (%lld != %lld)",
static_cast<long long>(m_meta_classes.count()),
static_cast<long long>(classes.count()));

/* Loop: output all the classes with no remaining dependencies to the
* result and then also remove those now output classes from the remaining
* classes in the hash table.
*/
AbstractMetaClassList result;
result.reserve(classes.count());
QSet<AbstractMetaClass *> handled;
handled.reserve(classes.count());
int interfaceClasses(0), depthFromLeaf(0);

while (!classes.empty()) {
handled.clear();
int iFCount(0);

/* Output classes where all children have already been output (initially
* the leaf nodes):
*/
for (auto i(classes.cbegin()); i != classes.cend(); ++i)
if (i.value().empty())
handled.insert(i.key());

return res;
/* Something must have been done; if not this is not a DAG because
* there is a cycle.
*/
if (handled.empty())
qFatal("TOPOSORT: %lld cyclic meta classes @depth %d.",
static_cast<long long>(classes.count()), depthFromLeaf);

/* Remove all 'handled' from the hash table. */
for (auto cls : handled)
if (!classes.remove(cls))
qFatal("TOPO SORT: class remove failed @depth %d.",
depthFromLeaf);

/* Then remove the 'handled' set from the classes values: */
for (QSet<AbstractMetaClass*> &set : classes)
set -= handled;

/* Output only those handled classes there are not interfaces: */
for (auto cls : handled) {
if (!cls->isInterface())
result.append(cls);
else
++iFCount;
}

ReportHandler::debugSparse(
QString("TSORT: depth %1: %2 classes (%3 interface)")
.arg(depthFromLeaf).arg(handled.count()).arg(iFCount));
interfaceClasses += iFCount;
++depthFromLeaf;
}

ReportHandler::debugSparse(QString(
"TSORT: %1 result classes, %2 interface classes)")
.arg(result.count()).arg(interfaceClasses));
return result;
}