blob: a1c73c38b07185a60fc99147f249b3c7bd114376 [file] [log] [blame]
Vishnu Nair04f89692022-11-16 23:21:05 +00001/*
2 * Copyright 2022 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#pragma once
18
19#include "FrontEnd/LayerCreationArgs.h"
Vishnu Naira0292282023-12-16 14:32:00 -080020#include "FrontEnd/LayerLifecycleManager.h"
Vishnu Nair04f89692022-11-16 23:21:05 +000021#include "RequestedLayerState.h"
22#include "ftl/small_vector.h"
23
24namespace android::surfaceflinger::frontend {
25class LayerHierarchyBuilder;
26
27// LayerHierarchy allows us to navigate the layer hierarchy in z-order, or depth first traversal.
28// The hierarchy is created from a set of RequestedLayerStates. The hierarchy itself does not
29// contain additional states. Instead, it is a representation of RequestedLayerStates as a graph.
30//
31// Each node in the hierarchy can be visited by multiple parents (making this a graph). While
32// traversing the hierarchy, a new concept called Variant can be used to understand the
33// relationship of the layer to its parent. The following variants are possible:
34// Attached - child of the parent
35// Detached - child of the parent but currently relative parented to another layer
36// Relative - relative child of the parent
37// Mirror - mirrored from another layer
38//
39// By representing the hierarchy as a graph, we can represent mirrored layer hierarchies without
40// cloning the layer requested state. The mirrored hierarchy and its corresponding
41// RequestedLayerStates are kept in sync because the mirrored hierarchy does not clone any
42// states.
43class LayerHierarchy {
44public:
Vishnu Naircfb2d252023-01-19 04:44:02 +000045 enum Variant : uint32_t {
Vishnu Naira02943f2023-06-03 13:44:46 -070046 Attached, // child of the parent
47 Detached, // child of the parent but currently relative parented to another layer
48 Relative, // relative child of the parent
49 Mirror, // mirrored from another layer
Vishnu Naircfb2d252023-01-19 04:44:02 +000050 ftl_first = Attached,
51 ftl_last = Mirror,
Vishnu Nair04f89692022-11-16 23:21:05 +000052 };
53 // Represents a unique path to a node.
Vishnu Nair80a5a702023-02-11 01:21:51 +000054 // The layer hierarchy is represented as a graph. Each node can be visited by multiple parents.
55 // This allows us to represent mirroring in an efficient way. See the example below:
56 // root
57 // ├─ A {Traversal path id = 1}
58 // ├─ B {Traversal path id = 2}
59 // │ ├─ C {Traversal path id = 3}
60 // │ ├─ D {Traversal path id = 4}
Vishnu Nair6f878312023-09-08 11:05:01 -070061 // │ └─ E (Mirrors C) {Traversal path id = 5}
62 // └─ F (Mirrors B) {Traversal path id = 6}
Vishnu Nair80a5a702023-02-11 01:21:51 +000063 //
Vishnu Nair6f878312023-09-08 11:05:01 -070064 // C can be traversed via B or E or F and or via F then E.
Vishnu Nair80a5a702023-02-11 01:21:51 +000065 // Depending on how the node is reached, its properties such as geometry or visibility might be
66 // different. And we can uniquely identify the node by keeping track of the nodes leading up to
67 // it. But to be more efficient we only need to track the nodes id and the top mirror root path.
68 // So C for example, would have the following unique traversal paths:
69 // - {Traversal path id = 3}
Vishnu Nair6f878312023-09-08 11:05:01 -070070 // - {Traversal path id = 3, mirrorRootIds = 5}
71 // - {Traversal path id = 3, mirrorRootIds = 6}
72 // - {Traversal path id = 3, mirrorRootIds = 6, 5}
Vishnu Nair80a5a702023-02-11 01:21:51 +000073
Vishnu Nair04f89692022-11-16 23:21:05 +000074 struct TraversalPath {
75 uint32_t id;
76 LayerHierarchy::Variant variant;
77 // Mirrored layers can have a different geometry than their parents so we need to track
78 // the mirror roots in the traversal.
Vishnu Nair6f878312023-09-08 11:05:01 -070079 ftl::SmallVector<uint32_t, 5> mirrorRootIds;
Vishnu Nair04f89692022-11-16 23:21:05 +000080 // Relative layers can be visited twice, once by their parent and then once again by
81 // their relative parent. We keep track of the roots here to detect any loops in the
82 // hierarchy. If a relative root already exists in the list while building the
83 // TraversalPath, it means that somewhere in the hierarchy two layers are relatively
84 // parented to each other.
85 ftl::SmallVector<uint32_t, 5> relativeRootIds;
86 // First duplicate relative root id found. If this is a valid layer id that means we are
87 // in a loop.
88 uint32_t invalidRelativeRootId = UNASSIGNED_LAYER_ID;
Vishnu Nair8fc721b2022-12-22 20:06:32 +000089 // See isAttached()
90 bool detached = false;
Vishnu Nair04f89692022-11-16 23:21:05 +000091 bool hasRelZLoop() const { return invalidRelativeRootId != UNASSIGNED_LAYER_ID; }
Vishnu Nair8fc721b2022-12-22 20:06:32 +000092 // Returns true if this node is reached via one or more relative parents.
93 bool isRelative() const { return !relativeRootIds.empty(); }
94 // Returns true if the node or its parents are not Detached.
95 bool isAttached() const { return !detached; }
96 // Returns true if the node is a clone.
Vishnu Nair6f878312023-09-08 11:05:01 -070097 bool isClone() const { return !mirrorRootIds.empty(); }
Vishnu Nair04f89692022-11-16 23:21:05 +000098
99 bool operator==(const TraversalPath& other) const {
Vishnu Nair6f878312023-09-08 11:05:01 -0700100 return id == other.id && mirrorRootIds == other.mirrorRootIds;
Vishnu Nair04f89692022-11-16 23:21:05 +0000101 }
102 std::string toString() const;
103
Vishnu Nair8fc721b2022-12-22 20:06:32 +0000104 static const TraversalPath ROOT;
Vishnu Nair04f89692022-11-16 23:21:05 +0000105 };
106
Vishnu Naird0183602023-03-16 18:52:15 +0000107 struct TraversalPathHash {
108 std::size_t operator()(const LayerHierarchy::TraversalPath& key) const {
109 uint32_t hashCode = key.id * 31;
Vishnu Nair6f878312023-09-08 11:05:01 -0700110 for (uint32_t mirrorRootId : key.mirrorRootIds) {
111 hashCode += mirrorRootId * 31;
Vishnu Naird0183602023-03-16 18:52:15 +0000112 }
113 return std::hash<size_t>{}(hashCode);
114 }
115 };
116
Vishnu Nair04f89692022-11-16 23:21:05 +0000117 // Helper class to add nodes to an existing traversal id and removes the
118 // node when it goes out of scope.
119 class ScopedAddToTraversalPath {
120 public:
121 ScopedAddToTraversalPath(TraversalPath& traversalPath, uint32_t layerId,
122 LayerHierarchy::Variant variantArg);
123 ~ScopedAddToTraversalPath();
124
125 private:
126 TraversalPath& mTraversalPath;
Vishnu Nair80a5a702023-02-11 01:21:51 +0000127 TraversalPath mParentPath;
Vishnu Nair04f89692022-11-16 23:21:05 +0000128 };
129 LayerHierarchy(RequestedLayerState* layer);
130
131 // Visitor function that provides the hierarchy node and a traversal id which uniquely
132 // identifies how was visited. The hierarchy contains a pointer to the RequestedLayerState.
133 // Return false to stop traversing down the hierarchy.
134 typedef std::function<bool(const LayerHierarchy& hierarchy,
135 const LayerHierarchy::TraversalPath& traversalPath)>
136 Visitor;
137
138 // Traverse the hierarchy and visit all child variants.
139 void traverse(const Visitor& visitor) const {
Vishnu Nair8fc721b2022-12-22 20:06:32 +0000140 TraversalPath root = TraversalPath::ROOT;
Vishnu Naird47bcee2023-02-24 18:08:51 +0000141 if (mLayer) {
142 root.id = mLayer->id;
143 }
Vishnu Nair8fc721b2022-12-22 20:06:32 +0000144 traverse(visitor, root);
Vishnu Nair04f89692022-11-16 23:21:05 +0000145 }
146
147 // Traverse the hierarchy in z-order, skipping children that have relative parents.
148 void traverseInZOrder(const Visitor& visitor) const {
Vishnu Nair8fc721b2022-12-22 20:06:32 +0000149 TraversalPath root = TraversalPath::ROOT;
Vishnu Naird47bcee2023-02-24 18:08:51 +0000150 if (mLayer) {
151 root.id = mLayer->id;
152 }
Vishnu Nair8fc721b2022-12-22 20:06:32 +0000153 traverseInZOrder(visitor, root);
Vishnu Nair04f89692022-11-16 23:21:05 +0000154 }
155
156 const RequestedLayerState* getLayer() const;
Vishnu Nairea6ff812023-02-27 17:41:39 +0000157 const LayerHierarchy* getRelativeParent() const;
158 const LayerHierarchy* getParent() const;
Vishnu Nair3cc15a42023-06-30 06:20:22 +0000159 friend std::ostream& operator<<(std::ostream& os, const LayerHierarchy& obj) {
160 std::string prefix = " ";
Vishnu Nair6f878312023-09-08 11:05:01 -0700161 obj.dump(os, prefix, LayerHierarchy::Variant::Attached, /*isLastChild=*/false,
162 /*includeMirroredHierarchy*/ false);
Vishnu Nair3cc15a42023-06-30 06:20:22 +0000163 return os;
164 }
Vishnu Nair6f878312023-09-08 11:05:01 -0700165 std::string dump() const {
166 std::string prefix = " ";
167 std::ostringstream os;
168 dump(os, prefix, LayerHierarchy::Variant::Attached, /*isLastChild=*/false,
169 /*includeMirroredHierarchy*/ true);
170 return os.str();
171 }
Vishnu Nair3cc15a42023-06-30 06:20:22 +0000172
Vishnu Nair04f89692022-11-16 23:21:05 +0000173 std::string getDebugStringShort() const;
174 // Traverse the hierarchy and return true if loops are found. The outInvalidRelativeRoot
175 // will contain the first relative root that was visited twice in a traversal.
176 bool hasRelZLoop(uint32_t& outInvalidRelativeRoot) const;
177 std::vector<std::pair<LayerHierarchy*, Variant>> mChildren;
178
179private:
180 friend LayerHierarchyBuilder;
181 LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly);
182 void addChild(LayerHierarchy*, LayerHierarchy::Variant);
183 void removeChild(LayerHierarchy*);
184 void sortChildrenByZOrder();
185 void updateChild(LayerHierarchy*, LayerHierarchy::Variant);
186 void traverseInZOrder(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
187 void traverse(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
Vishnu Nair3cc15a42023-06-30 06:20:22 +0000188 void dump(std::ostream& out, const std::string& prefix, LayerHierarchy::Variant variant,
Vishnu Nair6f878312023-09-08 11:05:01 -0700189 bool isLastChild, bool includeMirroredHierarchy) const;
Vishnu Nair04f89692022-11-16 23:21:05 +0000190
191 const RequestedLayerState* mLayer;
192 LayerHierarchy* mParent = nullptr;
193 LayerHierarchy* mRelativeParent = nullptr;
194};
195
196// Given a list of RequestedLayerState, this class will build a root hierarchy and an
197// offscreen hierarchy. The builder also has an update method which can update an existing
198// hierarchy from a list of RequestedLayerState and associated change flags.
199class LayerHierarchyBuilder {
200public:
Vishnu Naira0292282023-12-16 14:32:00 -0800201 LayerHierarchyBuilder() = default;
202 void update(LayerLifecycleManager& layerLifecycleManager);
Vishnu Nair04f89692022-11-16 23:21:05 +0000203 LayerHierarchy getPartialHierarchy(uint32_t, bool childrenOnly) const;
204 const LayerHierarchy& getHierarchy() const;
205 const LayerHierarchy& getOffscreenHierarchy() const;
206 std::string getDebugString(uint32_t layerId, uint32_t depth = 0) const;
207
208private:
209 void onLayerAdded(RequestedLayerState* layer);
210 void attachToParent(LayerHierarchy*);
211 void detachFromParent(LayerHierarchy*);
212 void attachToRelativeParent(LayerHierarchy*);
213 void detachFromRelativeParent(LayerHierarchy*);
214 void attachHierarchyToRelativeParent(LayerHierarchy*);
215 void detachHierarchyFromRelativeParent(LayerHierarchy*);
Vishnu Naira0292282023-12-16 14:32:00 -0800216 void init(const std::vector<std::unique_ptr<RequestedLayerState>>&);
217 void doUpdate(const std::vector<std::unique_ptr<RequestedLayerState>>& layers,
218 const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers);
Vishnu Nair04f89692022-11-16 23:21:05 +0000219 void onLayerDestroyed(RequestedLayerState* layer);
220 void updateMirrorLayer(RequestedLayerState* layer);
221 LayerHierarchy* getHierarchyFromId(uint32_t layerId, bool crashOnFailure = true);
Vishnu Naira0292282023-12-16 14:32:00 -0800222
Vishnu Nair04f89692022-11-16 23:21:05 +0000223 std::unordered_map<uint32_t, LayerHierarchy*> mLayerIdToHierarchy;
224 std::vector<std::unique_ptr<LayerHierarchy>> mHierarchies;
225 LayerHierarchy mRoot{nullptr};
226 LayerHierarchy mOffscreenRoot{nullptr};
Vishnu Naira0292282023-12-16 14:32:00 -0800227 bool mInitialized = false;
Vishnu Nair04f89692022-11-16 23:21:05 +0000228};
229
230} // namespace android::surfaceflinger::frontend