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 | |
20 | QT_BEGIN_NAMESPACE |
21 | |
22 | namespace icutils { |
23 | struct Node { |
24 | private: |
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 | |
31 | public: |
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 | |
58 | using NodeList = std::vector<Node>; |
59 | using AdjacencyList = std::vector<std::vector<Node*>>; |
60 | |
61 | template<typename ObjectContainer, typename InlineComponent> |
62 | void 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 | |
110 | inline 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) |
131 | inline 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: ¤tNode, 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 | |
153 | QT_END_NAMESPACE |
154 | |
155 | #endif // INLINECOMPONENTUTILS_P_H |
156 | |