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 | |
56 | namespace icutils { |
57 | struct 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 | |
80 | using AdjacencyList = std::vector<std::vector<Node*>>; |
81 | |
82 | template<typename ObjectContainer, typename InlineComponent> |
83 | void 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 | |
122 | inline 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) |
142 | inline 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: ¤tNode, 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 | |