1/****************************************************************************
2**
3** Copyright (C) 2020 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtQml module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39#ifndef INLINECOMPONENTUTILS_P_H
40#define INLINECOMPONENTUTILS_P_H
41
42//
43// W A R N I N G
44// -------------
45//
46// This file is not part of the Qt API. It exists purely as an
47// implementation detail. This header file may change from version to
48// version without notice, or even be removed.
49//
50// We mean it.
51//
52
53#include <private/qv4compileddata_p.h>
54#include <private/qv4executablecompilationunit_p.h>
55
56namespace icutils {
57struct Node {
58 Node() = default;
59 Node(const Node &) = default;
60 Node(Node &&) = default;
61 Node& operator=(Node const &) = default;
62 Node& operator=(Node &&) = default;
63 bool operator==(Node const &other) const {return index == other.index;}
64
65 Node(std::vector<QV4::CompiledData::InlineComponent>::size_type s)
66 : index{.val: 0}
67 {
68 index = quint32(s);
69 temporaryMark = 0;
70 permanentMark = 0;
71 }
72
73 union {
74 quint32_le_bitfield<0, 30> index;
75 quint32_le_bitfield<30, 1> temporaryMark;
76 quint32_le_bitfield<31, 1> permanentMark;
77 };
78};
79
80using AdjacencyList = std::vector<std::vector<Node*>>;
81
82template<typename ObjectContainer, typename InlineComponent>
83void fillAdjacencyListForInlineComponents(ObjectContainer *objectContainer, AdjacencyList &adjacencyList, std::vector<Node> &nodes, const std::vector<InlineComponent> &allICs) {
84 using CompiledObject = typename ObjectContainer::CompiledObject;
85 // add an edge from A to B if A and B are inline components with the same containing type
86 // and A inherits from B (ignore indirect chains through external types for now)
87 // or if A instantiates B
88 for (typename std::vector<InlineComponent>::size_type i = 0; i < allICs.size(); ++i) {
89 const auto& ic = allICs[i];
90 const CompiledObject *obj = objectContainer->objectAt(ic.objectIndex);
91 QV4::ResolvedTypeReference *currentICTypeRef = objectContainer->resolvedType(ic.nameIndex);
92 auto createEdgeFromTypeRef = [&](QV4::ResolvedTypeReference *targetTypeRef) {
93 if (targetTypeRef && targetTypeRef->type.isInlineComponentType()) {
94 if (targetTypeRef->type.containingType() == currentICTypeRef->type.containingType()) {
95 auto icIt = std::find_if(allICs.cbegin(), allICs.cend(), [&](const QV4::CompiledData::InlineComponent &icSearched){
96 return int(icSearched.objectIndex) == targetTypeRef->type.inlineComponentObjectId();
97 });
98 Q_ASSERT(icIt != allICs.cend());
99 Node& target = nodes[i];
100 adjacencyList[std::distance(allICs.cbegin(), icIt)].push_back(&target);
101 }
102 }
103 };
104 if (obj->inheritedTypeNameIndex != 0) {
105 QV4::ResolvedTypeReference *parentTypeRef = objectContainer->resolvedType(obj->inheritedTypeNameIndex);
106 createEdgeFromTypeRef(parentTypeRef);
107
108 }
109 auto referencedInICObjectIndex = ic.objectIndex + 1;
110 while (int(referencedInICObjectIndex) < objectContainer->objectCount()) {
111 auto potentiallyReferencedInICObject = objectContainer->objectAt(referencedInICObjectIndex);
112 bool stillInIC = !(potentiallyReferencedInICObject-> flags & QV4::CompiledData::Object::IsInlineComponentRoot)
113 && (potentiallyReferencedInICObject-> flags & QV4::CompiledData::Object::InPartOfInlineComponent);
114 if (!stillInIC)
115 break;
116 createEdgeFromTypeRef(objectContainer->resolvedType(potentiallyReferencedInICObject->inheritedTypeNameIndex));
117 ++referencedInICObjectIndex;
118 }
119 }
120};
121
122inline void topoVisit(Node *node, AdjacencyList &adjacencyList, bool &hasCycle, std::vector<Node> &nodesSorted) {
123 if (node->permanentMark)
124 return;
125 if (node->temporaryMark) {
126 hasCycle = true;
127 return;
128 }
129 node->temporaryMark = 1;
130
131 auto const &edges = adjacencyList[node->index];
132 for (auto edgeTarget =edges.begin(); edgeTarget != edges.end(); ++edgeTarget) {
133 topoVisit(node: *edgeTarget, adjacencyList, hasCycle, nodesSorted);
134 }
135
136 node->temporaryMark = 0;
137 node->permanentMark = 1;
138 nodesSorted.push_back(x: *node);
139};
140
141// Use DFS based topological sorting (https://en.wikipedia.org/wiki/Topological_sorting)
142inline std::vector<Node> topoSort(std::vector<Node> &nodes, AdjacencyList &adjacencyList, bool &hasCycle) {
143 std::vector<Node> nodesSorted;
144 nodesSorted.reserve(n: nodes.size());
145
146 hasCycle = false;
147 auto currentNodeIt = std::find_if(first: nodes.begin(), last: nodes.end(), pred: [](const Node& node) {
148 return node.permanentMark == 0;
149 });
150 // Do a topological sort of all inline components
151 // afterwards, nodesSorted contains the nodes for the inline components in reverse topological order
152 while (currentNodeIt != nodes.end() && !hasCycle) {
153 Node& currentNode = *currentNodeIt;
154 topoVisit(node: &currentNode, adjacencyList, hasCycle, nodesSorted);
155 currentNodeIt = std::find_if(first: nodes.begin(), last: nodes.end(), pred: [](const Node& node) {
156 return node.permanentMark == 0;
157 });
158 }
159 return nodesSorted;
160}
161}
162
163#endif // INLINECOMPONENTUTILS_P_H
164

source code of qtdeclarative/src/qml/inlinecomponentutils_p.h