Revision control
Copy as Markdown
// Copyright (C) 2020 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant
#ifndef INLINECOMPONENTUTILS_P_H
#define INLINECOMPONENTUTILS_P_H
//
// W A R N I N G
// -------------
//
// This file is not part of the Qt API. It exists purely as an
// implementation detail. This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
#include <private/qqmlmetatype_p.h>
#include <private/qv4compileddata_p.h>
#include <private/qv4resolvedtypereference_p.h>
QT_BEGIN_NAMESPACE
namespace icutils {
struct Node {
private:
using IndexType = std::vector<QV4::CompiledData::InlineComponent>::size_type;
using IndexField = quint32_le_bitfield_member<0, 30, IndexType>;
using TemporaryMarkField = quint32_le_bitfield_member<30, 1>;
using PermanentMarkField = quint32_le_bitfield_member<31, 1>;
quint32_le_bitfield_union<IndexField, TemporaryMarkField, PermanentMarkField> m_data;
public:
Node() = default;
Node(const Node &) = default;
Node(Node &&) = default;
Node& operator=(Node const &) = default;
Node& operator=(Node &&) = default;
bool operator==(Node const &other) const {return m_data.data() == other.m_data.data(); }
Node(IndexType s) : m_data(QSpecialIntegerBitfieldZero) { m_data.set<IndexField>(s); }
bool hasPermanentMark() const { return m_data.get<PermanentMarkField>(); }
bool hasTemporaryMark() const { return m_data.get<TemporaryMarkField>(); }
void setPermanentMark()
{
m_data.set<TemporaryMarkField>(0);
m_data.set<PermanentMarkField>(1);
}
void setTemporaryMark()
{
m_data.set<TemporaryMarkField>(1);
}
IndexType index() const { return m_data.get<IndexField>(); }
};
using NodeList = std::vector<Node>;
using AdjacencyList = std::vector<std::vector<Node*>>;
inline bool containedInSameType(const QQmlType &a, const QQmlType &b)
{
return QQmlMetaType::equalBaseUrls(a.sourceUrl(), b.sourceUrl());
}
template<typename ObjectContainer, typename InlineComponent>
void fillAdjacencyListForInlineComponents(ObjectContainer *objectContainer,
AdjacencyList &adjacencyList, NodeList &nodes,
const std::vector<InlineComponent> &allICs)
{
using CompiledObject = typename ObjectContainer::CompiledObject;
// add an edge from A to B if A and B are inline components with the same containing type
// and A inherits from B (ignore indirect chains through external types for now)
// or if A instantiates B
for (typename std::vector<InlineComponent>::size_type i = 0; i < allICs.size(); ++i) {
const auto& ic = allICs[i];
const CompiledObject *obj = objectContainer->objectAt(ic.objectIndex);
QV4::ResolvedTypeReference *currentICTypeRef = objectContainer->resolvedType(ic.nameIndex);
auto createEdgeFromTypeRef = [&](QV4::ResolvedTypeReference *targetTypeRef) {
if (!targetTypeRef)
return;
const QQmlType targetType = targetTypeRef->type();
if (!targetType.isInlineComponent()
|| !containedInSameType(targetType, currentICTypeRef->type())) {
return;
}
const auto icIt =
std::find_if(allICs.cbegin(), allICs.cend(),
[&](const QV4::CompiledData::InlineComponent &icSearched) {
return objectContainer->stringAt(icSearched.nameIndex)
== targetType.elementName();
});
Q_ASSERT(icIt != allICs.cend());
adjacencyList[std::distance(allICs.cbegin(), icIt)].push_back(&nodes[i]);
};
if (obj->inheritedTypeNameIndex != 0) {
QV4::ResolvedTypeReference *parentTypeRef = objectContainer->resolvedType(obj->inheritedTypeNameIndex);
createEdgeFromTypeRef(parentTypeRef);
}
auto referencedInICObjectIndex = ic.objectIndex + 1;
while (int(referencedInICObjectIndex) < objectContainer->objectCount()) {
auto potentiallyReferencedInICObject = objectContainer->objectAt(referencedInICObjectIndex);
bool stillInIC
= !potentiallyReferencedInICObject->hasFlag(
QV4::CompiledData::Object::IsInlineComponentRoot)
&& potentiallyReferencedInICObject->hasFlag(
QV4::CompiledData::Object::IsPartOfInlineComponent);
if (!stillInIC)
break;
createEdgeFromTypeRef(objectContainer->resolvedType(potentiallyReferencedInICObject->inheritedTypeNameIndex));
++referencedInICObjectIndex;
}
}
};
inline void topoVisit(Node *node, AdjacencyList &adjacencyList, bool &hasCycle,
NodeList &nodesSorted)
{
if (node->hasPermanentMark())
return;
if (node->hasTemporaryMark()) {
hasCycle = true;
return;
}
node->setTemporaryMark();
auto const &edges = adjacencyList[node->index()];
for (auto edgeTarget =edges.begin(); edgeTarget != edges.end(); ++edgeTarget) {
topoVisit(*edgeTarget, adjacencyList, hasCycle, nodesSorted);
}
node->setPermanentMark();
nodesSorted.push_back(*node);
};
inline NodeList topoSort(NodeList &nodes, AdjacencyList &adjacencyList, bool &hasCycle)
{
NodeList nodesSorted;
nodesSorted.reserve(nodes.size());
hasCycle = false;
auto currentNodeIt = std::find_if(nodes.begin(), nodes.end(), [](const Node& node) {
return !node.hasPermanentMark();
});
// Do a topological sort of all inline components
// afterwards, nodesSorted contains the nodes for the inline components in reverse topological order
while (currentNodeIt != nodes.end() && !hasCycle) {
Node& currentNode = *currentNodeIt;
topoVisit(¤tNode, adjacencyList, hasCycle, nodesSorted);
currentNodeIt = std::find_if(nodes.begin(), nodes.end(), [](const Node& node) {
return !node.hasPermanentMark();
});
}
return nodesSorted;
}
}
QT_END_NAMESPACE
#endif // INLINECOMPONENTUTILS_P_H