1// Copyright (C) 2020 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3#ifndef INLINECOMPONENTUTILS_P_H
4#define INLINECOMPONENTUTILS_P_H
5
6//
7// W A R N I N G
8// -------------
9//
10// This file is not part of the Qt API. It exists purely as an
11// implementation detail. This header file may change from version to
12// version without notice, or even be removed.
13//
14// We mean it.
15//
16
17#include <private/qqmlmetatype_p.h>
18#include <private/qv4compileddata_p.h>
19#include <private/qv4resolvedtypereference_p.h>
20
21QT_BEGIN_NAMESPACE
22
23namespace icutils {
24struct Node {
25private:
26 using IndexType = std::vector<QV4::CompiledData::InlineComponent>::size_type;
27 using IndexField = quint32_le_bitfield_member<0, 30, IndexType>;
28 using TemporaryMarkField = quint32_le_bitfield_member<30, 1>;
29 using PermanentMarkField = quint32_le_bitfield_member<31, 1>;
30 quint32_le_bitfield_union<IndexField, TemporaryMarkField, PermanentMarkField> m_data;
31
32public:
33 Node() = default;
34 Node(const Node &) = default;
35 Node(Node &&) = default;
36 Node& operator=(Node const &) = default;
37 Node& operator=(Node &&) = default;
38 bool operator==(Node const &other) const {return m_data.data() == other.m_data.data(); }
39
40 Node(IndexType s) : m_data(QSpecialIntegerBitfieldZero) { m_data.set<IndexField>(s); }
41
42 bool hasPermanentMark() const { return m_data.get<PermanentMarkField>(); }
43 bool hasTemporaryMark() const { return m_data.get<TemporaryMarkField>(); }
44
45 void setPermanentMark()
46 {
47 m_data.set<TemporaryMarkField>(0);
48 m_data.set<PermanentMarkField>(1);
49 }
50
51 void setTemporaryMark()
52 {
53 m_data.set<TemporaryMarkField>(1);
54 }
55
56 IndexType index() const { return m_data.get<IndexField>(); }
57};
58
59using NodeList = std::vector<Node>;
60using AdjacencyList = std::vector<std::vector<Node*>>;
61
62inline bool containedInSameType(const QQmlType &a, const QQmlType &b)
63{
64 return QQmlMetaType::equalBaseUrls(aUrl: a.sourceUrl(), bUrl: b.sourceUrl());
65}
66
67template<typename ObjectContainer, typename InlineComponent>
68void fillAdjacencyListForInlineComponents(ObjectContainer *objectContainer,
69 AdjacencyList &adjacencyList, NodeList &nodes,
70 const std::vector<InlineComponent> &allICs)
71{
72 using CompiledObject = typename ObjectContainer::CompiledObject;
73 // add an edge from A to B if A and B are inline components with the same containing type
74 // and A inherits from B (ignore indirect chains through external types for now)
75 // or if A instantiates B
76 for (typename std::vector<InlineComponent>::size_type i = 0; i < allICs.size(); ++i) {
77 const auto& ic = allICs[i];
78 const CompiledObject *obj = objectContainer->objectAt(ic.objectIndex);
79 QV4::ResolvedTypeReference *currentICTypeRef = objectContainer->resolvedType(ic.nameIndex);
80 auto createEdgeFromTypeRef = [&](QV4::ResolvedTypeReference *targetTypeRef) {
81 if (targetTypeRef) {
82 const auto targetType = targetTypeRef->type();
83 if (targetType.isInlineComponentType()
84 && containedInSameType(a: targetType, b: currentICTypeRef->type())) {
85 auto icIt = std::find_if(allICs.cbegin(), allICs.cend(), [&](const QV4::CompiledData::InlineComponent &icSearched){
86 return objectContainer->stringAt(icSearched.nameIndex)
87 == targetType.elementName();
88 });
89 Q_ASSERT(icIt != allICs.cend());
90 Node& target = nodes[i];
91 adjacencyList[std::distance(allICs.cbegin(), icIt)].push_back(&target);
92 }
93 }
94 };
95 if (obj->inheritedTypeNameIndex != 0) {
96 QV4::ResolvedTypeReference *parentTypeRef = objectContainer->resolvedType(obj->inheritedTypeNameIndex);
97 createEdgeFromTypeRef(parentTypeRef);
98
99 }
100 auto referencedInICObjectIndex = ic.objectIndex + 1;
101 while (int(referencedInICObjectIndex) < objectContainer->objectCount()) {
102 auto potentiallyReferencedInICObject = objectContainer->objectAt(referencedInICObjectIndex);
103 bool stillInIC
104 = !potentiallyReferencedInICObject->hasFlag(
105 QV4::CompiledData::Object::IsInlineComponentRoot)
106 && potentiallyReferencedInICObject->hasFlag(
107 QV4::CompiledData::Object::IsPartOfInlineComponent);
108 if (!stillInIC)
109 break;
110 createEdgeFromTypeRef(objectContainer->resolvedType(potentiallyReferencedInICObject->inheritedTypeNameIndex));
111 ++referencedInICObjectIndex;
112 }
113 }
114};
115
116inline void topoVisit(Node *node, AdjacencyList &adjacencyList, bool &hasCycle,
117 NodeList &nodesSorted)
118{
119 if (node->hasPermanentMark())
120 return;
121 if (node->hasTemporaryMark()) {
122 hasCycle = true;
123 return;
124 }
125 node->setTemporaryMark();
126
127 auto const &edges = adjacencyList[node->index()];
128 for (auto edgeTarget =edges.begin(); edgeTarget != edges.end(); ++edgeTarget) {
129 topoVisit(node: *edgeTarget, adjacencyList, hasCycle, nodesSorted);
130 }
131
132 node->setPermanentMark();
133 nodesSorted.push_back(x: *node);
134};
135
136// Use DFS based topological sorting (https://en.wikipedia.org/wiki/Topological_sorting)
137inline NodeList topoSort(NodeList &nodes, AdjacencyList &adjacencyList, bool &hasCycle)
138{
139 NodeList nodesSorted;
140 nodesSorted.reserve(n: nodes.size());
141
142 hasCycle = false;
143 auto currentNodeIt = std::find_if(first: nodes.begin(), last: nodes.end(), pred: [](const Node& node) {
144 return !node.hasPermanentMark();
145 });
146 // Do a topological sort of all inline components
147 // afterwards, nodesSorted contains the nodes for the inline components in reverse topological order
148 while (currentNodeIt != nodes.end() && !hasCycle) {
149 Node& currentNode = *currentNodeIt;
150 topoVisit(node: &currentNode, adjacencyList, hasCycle, nodesSorted);
151 currentNodeIt = std::find_if(first: nodes.begin(), last: nodes.end(), pred: [](const Node& node) {
152 return !node.hasPermanentMark();
153 });
154 }
155 return nodesSorted;
156}
157}
158
159QT_END_NAMESPACE
160
161#endif // INLINECOMPONENTUTILS_P_H
162

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