1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
// 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
#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) {
const auto targetType = targetTypeRef->type();
if (targetType.isInlineComponentType()
&& containedInSameType(targetType, currentICTypeRef->type())) {
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());
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->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);
};
// Use DFS based topological sorting (https://en.wikipedia.org/wiki/Topological_sorting)
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
|
