diff options
Diffstat (limited to 'src/qml/inlinecomponentutils_p.h')
| -rw-r--r-- | src/qml/inlinecomponentutils_p.h | 161 |
1 files changed, 161 insertions, 0 deletions
diff --git a/src/qml/inlinecomponentutils_p.h b/src/qml/inlinecomponentutils_p.h new file mode 100644 index 0000000000..99b28349cd --- /dev/null +++ b/src/qml/inlinecomponentutils_p.h @@ -0,0 +1,161 @@ +/**************************************************************************** +** +** Copyright (C) 2020 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ +#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/qv4compileddata_p.h> +#include <private/qv4executablecompilationunit_p.h> + +namespace icutils { +struct Node { + 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 index == other.index;} + + Node(std::vector<QV4::CompiledData::InlineComponent>::size_type s) { + index = quint32(s); + temporaryMark = 0; + permanentMark = 0; + } + + union { + quint32_le_bitfield<0, 30> index; + quint32_le_bitfield<30, 1> temporaryMark; + quint32_le_bitfield<31, 1> permanentMark; + }; +}; + +using AdjacencyList = std::vector<std::vector<Node*>>; + +template<typename ObjectContainer, typename InlineComponent> +void fillAdjacencyListForInlineComponents(ObjectContainer *objectContainer, AdjacencyList &adjacencyList, std::vector<Node> &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 && targetTypeRef->type.isInlineComponentType()) { + if (targetTypeRef->type.containingType() == currentICTypeRef->type.containingType()) { + auto icIt = std::find_if(allICs.cbegin(), allICs.cend(), [&](const QV4::CompiledData::InlineComponent &icSearched){ + return int(icSearched.objectIndex) == targetTypeRef->type.inlineComponentObjectId(); + }); + Q_ASSERT(icIt != allICs.cend()); + Node& target = nodes[i]; + adjacencyList[std::distance(allICs.cbegin(), icIt)].push_back(&target); + } + } + }; + 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-> flags & QV4::CompiledData::Object::IsInlineComponentRoot) + && (potentiallyReferencedInICObject-> flags & QV4::CompiledData::Object::InPartOfInlineComponent); + if (!stillInIC) + break; + createEdgeFromTypeRef(objectContainer->resolvedType(potentiallyReferencedInICObject->inheritedTypeNameIndex)); + ++referencedInICObjectIndex; + } + } +}; + +inline void topoVisit(Node *node, AdjacencyList &adjacencyList, bool &hasCycle, std::vector<Node> &nodesSorted) { + if (node->permanentMark) + return; + if (node->temporaryMark) { + hasCycle = true; + return; + } + node->temporaryMark = 1; + + auto const &edges = adjacencyList[node->index]; + for (auto edgeTarget =edges.begin(); edgeTarget != edges.end(); ++edgeTarget) { + topoVisit(*edgeTarget, adjacencyList, hasCycle, nodesSorted); + } + + node->temporaryMark = 0; + node->permanentMark = 1; + nodesSorted.push_back(*node); +}; + +// Use DFS based topological sorting (https://en.wikipedia.org/wiki/Topological_sorting) +inline std::vector<Node> topoSort(std::vector<Node> &nodes, AdjacencyList &adjacencyList, bool &hasCycle) { + std::vector<Node> nodesSorted; + nodesSorted.reserve(nodes.size()); + + hasCycle = false; + auto currentNodeIt = std::find_if(nodes.begin(), nodes.end(), [](const Node& node) { + return node.permanentMark == 0; + }); + // 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.permanentMark == 0; + }); + } + return nodesSorted; +} +} + +#endif // INLINECOMPONENTUTILS_P_H |