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/qv4compileddata_p.h>
18#include <private/qv4resolvedtypereference_p.h>
19
20QT_BEGIN_NAMESPACE
21
22namespace icutils {
23struct Node {
24private:
25 using IndexType = std::vector<QV4::CompiledData::InlineComponent>::size_type;
26 using IndexField = quint32_le_bitfield_member<0, 30, IndexType>;
27 using TemporaryMarkField = quint32_le_bitfield_member<30, 1>;
28 using PermanentMarkField = quint32_le_bitfield_member<31, 1>;
29 quint32_le_bitfield_union<IndexField, TemporaryMarkField, PermanentMarkField> m_data;
30
31public:
32 Node() = default;
33 Node(const Node &) = default;
34 Node(Node &&) = default;
35 Node& operator=(Node const &) = default;
36 Node& operator=(Node &&) = default;
37 bool operator==(Node const &other) const {return m_data.data() == other.m_data.data(); }
38
39 Node(IndexType s) : m_data(QSpecialIntegerBitfieldZero) { m_data.set<IndexField>(s); }
40
41 bool hasPermanentMark() const { return m_data.get<PermanentMarkField>(); }
42 bool hasTemporaryMark() const { return m_data.get<TemporaryMarkField>(); }
43
44 void setPermanentMark()
45 {
46 m_data.set<TemporaryMarkField>(0);
47 m_data.set<PermanentMarkField>(1);
48 }
49
50 void setTemporaryMark()
51 {
52 m_data.set<TemporaryMarkField>(1);
53 }
54
55 IndexType index() const { return m_data.get<IndexField>(); }
56};
57
58using NodeList = std::vector<Node>;
59using AdjacencyList = std::vector<std::vector<Node*>>;
60
61template<typename ObjectContainer, typename InlineComponent>
62void fillAdjacencyListForInlineComponents(ObjectContainer *objectContainer,
63 AdjacencyList &adjacencyList, NodeList &nodes,
64 const std::vector<InlineComponent> &allICs)
65{
66 using CompiledObject = typename ObjectContainer::CompiledObject;
67 // add an edge from A to B if A and B are inline components with the same containing type
68 // and A inherits from B (ignore indirect chains through external types for now)
69 // or if A instantiates B
70 for (typename std::vector<InlineComponent>::size_type i = 0; i < allICs.size(); ++i) {
71 const auto& ic = allICs[i];
72 const CompiledObject *obj = objectContainer->objectAt(ic.objectIndex);
73 QV4::ResolvedTypeReference *currentICTypeRef = objectContainer->resolvedType(ic.nameIndex);
74 auto createEdgeFromTypeRef = [&](QV4::ResolvedTypeReference *targetTypeRef) {
75 if (targetTypeRef) {
76 const auto targetType = targetTypeRef->type();
77 if (targetType.isInlineComponentType()
78 && targetType.containingType() == currentICTypeRef->type().containingType()) {
79 auto icIt = std::find_if(allICs.cbegin(), allICs.cend(), [&](const QV4::CompiledData::InlineComponent &icSearched){
80 return objectContainer->stringAt(icSearched.nameIndex)
81 == targetType.elementName();
82 });
83 Q_ASSERT(icIt != allICs.cend());
84 Node& target = nodes[i];
85 adjacencyList[std::distance(allICs.cbegin(), icIt)].push_back(&target);
86 }
87 }
88 };
89 if (obj->inheritedTypeNameIndex != 0) {
90 QV4::ResolvedTypeReference *parentTypeRef = objectContainer->resolvedType(obj->inheritedTypeNameIndex);
91 createEdgeFromTypeRef(parentTypeRef);
92
93 }
94 auto referencedInICObjectIndex = ic.objectIndex + 1;
95 while (int(referencedInICObjectIndex) < objectContainer->objectCount()) {
96 auto potentiallyReferencedInICObject = objectContainer->objectAt(referencedInICObjectIndex);
97 bool stillInIC
98 = !potentiallyReferencedInICObject->hasFlag(
99 QV4::CompiledData::Object::IsInlineComponentRoot)
100 && potentiallyReferencedInICObject->hasFlag(
101 QV4::CompiledData::Object::IsPartOfInlineComponent);
102 if (!stillInIC)
103 break;
104 createEdgeFromTypeRef(objectContainer->resolvedType(potentiallyReferencedInICObject->inheritedTypeNameIndex));
105 ++referencedInICObjectIndex;
106 }
107 }
108};
109
110inline void topoVisit(Node *node, AdjacencyList &adjacencyList, bool &hasCycle,
111 NodeList &nodesSorted)
112{
113 if (node->hasPermanentMark())
114 return;
115 if (node->hasTemporaryMark()) {
116 hasCycle = true;
117 return;
118 }
119 node->setTemporaryMark();
120
121 auto const &edges = adjacencyList[node->index()];
122 for (auto edgeTarget =edges.begin(); edgeTarget != edges.end(); ++edgeTarget) {
123 topoVisit(node: *edgeTarget, adjacencyList, hasCycle, nodesSorted);
124 }
125
126 node->setPermanentMark();
127 nodesSorted.push_back(x: *node);
128};
129
130// Use DFS based topological sorting (https://en.wikipedia.org/wiki/Topological_sorting)
131inline NodeList topoSort(NodeList &nodes, AdjacencyList &adjacencyList, bool &hasCycle)
132{
133 NodeList nodesSorted;
134 nodesSorted.reserve(n: nodes.size());
135
136 hasCycle = false;
137 auto currentNodeIt = std::find_if(first: nodes.begin(), last: nodes.end(), pred: [](const Node& node) {
138 return !node.hasPermanentMark();
139 });
140 // Do a topological sort of all inline components
141 // afterwards, nodesSorted contains the nodes for the inline components in reverse topological order
142 while (currentNodeIt != nodes.end() && !hasCycle) {
143 Node& currentNode = *currentNodeIt;
144 topoVisit(node: &currentNode, adjacencyList, hasCycle, nodesSorted);
145 currentNodeIt = std::find_if(first: nodes.begin(), last: nodes.end(), pred: [](const Node& node) {
146 return !node.hasPermanentMark();
147 });
148 }
149 return nodesSorted;
150}
151}
152
153QT_END_NAMESPACE
154
155#endif // INLINECOMPONENTUTILS_P_H
156

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