xref: /aosp_15_r20/frameworks/native/services/surfaceflinger/FrontEnd/LayerHierarchy.h (revision 38e8c45f13ce32b0dcecb25141ffecaf386fa17f)
1*38e8c45fSAndroid Build Coastguard Worker /*
2*38e8c45fSAndroid Build Coastguard Worker  * Copyright 2022 The Android Open Source Project
3*38e8c45fSAndroid Build Coastguard Worker  *
4*38e8c45fSAndroid Build Coastguard Worker  * Licensed under the Apache License, Version 2.0 (the "License");
5*38e8c45fSAndroid Build Coastguard Worker  * you may not use this file except in compliance with the License.
6*38e8c45fSAndroid Build Coastguard Worker  * You may obtain a copy of the License at
7*38e8c45fSAndroid Build Coastguard Worker  *
8*38e8c45fSAndroid Build Coastguard Worker  *      http://www.apache.org/licenses/LICENSE-2.0
9*38e8c45fSAndroid Build Coastguard Worker  *
10*38e8c45fSAndroid Build Coastguard Worker  * Unless required by applicable law or agreed to in writing, software
11*38e8c45fSAndroid Build Coastguard Worker  * distributed under the License is distributed on an "AS IS" BASIS,
12*38e8c45fSAndroid Build Coastguard Worker  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13*38e8c45fSAndroid Build Coastguard Worker  * See the License for the specific language governing permissions and
14*38e8c45fSAndroid Build Coastguard Worker  * limitations under the License.
15*38e8c45fSAndroid Build Coastguard Worker  */
16*38e8c45fSAndroid Build Coastguard Worker 
17*38e8c45fSAndroid Build Coastguard Worker #pragma once
18*38e8c45fSAndroid Build Coastguard Worker 
19*38e8c45fSAndroid Build Coastguard Worker #include "FrontEnd/LayerCreationArgs.h"
20*38e8c45fSAndroid Build Coastguard Worker #include "FrontEnd/LayerLifecycleManager.h"
21*38e8c45fSAndroid Build Coastguard Worker #include "RequestedLayerState.h"
22*38e8c45fSAndroid Build Coastguard Worker #include "ftl/small_vector.h"
23*38e8c45fSAndroid Build Coastguard Worker 
24*38e8c45fSAndroid Build Coastguard Worker namespace android::surfaceflinger::frontend {
25*38e8c45fSAndroid Build Coastguard Worker class LayerHierarchyBuilder;
26*38e8c45fSAndroid Build Coastguard Worker 
27*38e8c45fSAndroid Build Coastguard Worker // LayerHierarchy allows us to navigate the layer hierarchy in z-order, or depth first traversal.
28*38e8c45fSAndroid Build Coastguard Worker // The hierarchy is created from a set of RequestedLayerStates. The hierarchy itself does not
29*38e8c45fSAndroid Build Coastguard Worker // contain additional states. Instead, it is a representation of RequestedLayerStates as a graph.
30*38e8c45fSAndroid Build Coastguard Worker //
31*38e8c45fSAndroid Build Coastguard Worker // Each node in the hierarchy can be visited by multiple parents (making this a graph). While
32*38e8c45fSAndroid Build Coastguard Worker // traversing the hierarchy, a new concept called Variant can be used to understand the
33*38e8c45fSAndroid Build Coastguard Worker // relationship of the layer to its parent. The following variants are possible:
34*38e8c45fSAndroid Build Coastguard Worker // Attached - child of the parent
35*38e8c45fSAndroid Build Coastguard Worker // Detached - child of the parent but currently relative parented to another layer
36*38e8c45fSAndroid Build Coastguard Worker // Relative - relative child of the parent
37*38e8c45fSAndroid Build Coastguard Worker // Mirror - mirrored from another layer
38*38e8c45fSAndroid Build Coastguard Worker // Detached_Mirror - mirrored from another layer, ignoring local transform
39*38e8c45fSAndroid Build Coastguard Worker //
40*38e8c45fSAndroid Build Coastguard Worker // By representing the hierarchy as a graph, we can represent mirrored layer hierarchies without
41*38e8c45fSAndroid Build Coastguard Worker // cloning the layer requested state. The mirrored hierarchy and its corresponding
42*38e8c45fSAndroid Build Coastguard Worker // RequestedLayerStates are kept in sync because the mirrored hierarchy does not clone any
43*38e8c45fSAndroid Build Coastguard Worker // states.
44*38e8c45fSAndroid Build Coastguard Worker class LayerHierarchy {
45*38e8c45fSAndroid Build Coastguard Worker public:
46*38e8c45fSAndroid Build Coastguard Worker     enum Variant : uint32_t {
47*38e8c45fSAndroid Build Coastguard Worker         Attached,        // child of the parent
48*38e8c45fSAndroid Build Coastguard Worker         Detached,        // child of the parent but currently relative parented to another layer
49*38e8c45fSAndroid Build Coastguard Worker         Relative,        // relative child of the parent
50*38e8c45fSAndroid Build Coastguard Worker         Mirror,          // mirrored from another layer
51*38e8c45fSAndroid Build Coastguard Worker         Detached_Mirror, // mirrored from another layer, ignoring local transform
52*38e8c45fSAndroid Build Coastguard Worker         ftl_first = Attached,
53*38e8c45fSAndroid Build Coastguard Worker         ftl_last = Detached_Mirror,
54*38e8c45fSAndroid Build Coastguard Worker     };
isMirror(Variant variant)55*38e8c45fSAndroid Build Coastguard Worker     static inline bool isMirror(Variant variant) {
56*38e8c45fSAndroid Build Coastguard Worker         return ((variant == Mirror) || (variant == Detached_Mirror));
57*38e8c45fSAndroid Build Coastguard Worker     }
58*38e8c45fSAndroid Build Coastguard Worker 
59*38e8c45fSAndroid Build Coastguard Worker     // Represents a unique path to a node.
60*38e8c45fSAndroid Build Coastguard Worker     // The layer hierarchy is represented as a graph. Each node can be visited by multiple parents.
61*38e8c45fSAndroid Build Coastguard Worker     // This allows us to represent mirroring in an efficient way. See the example below:
62*38e8c45fSAndroid Build Coastguard Worker     // root
63*38e8c45fSAndroid Build Coastguard Worker     // ├─ A {Traversal path id = 1}
64*38e8c45fSAndroid Build Coastguard Worker     // ├─ B {Traversal path id = 2}
65*38e8c45fSAndroid Build Coastguard Worker     // │  ├─ C {Traversal path id = 3}
66*38e8c45fSAndroid Build Coastguard Worker     // │  ├─ D {Traversal path id = 4}
67*38e8c45fSAndroid Build Coastguard Worker     // │  └─ E (Mirrors C) {Traversal path id = 5}
68*38e8c45fSAndroid Build Coastguard Worker     // └─ F (Mirrors B) {Traversal path id = 6}
69*38e8c45fSAndroid Build Coastguard Worker     //
70*38e8c45fSAndroid Build Coastguard Worker     // C can be traversed via B or E or F and or via F then E.
71*38e8c45fSAndroid Build Coastguard Worker     // Depending on how the node is reached, its properties such as geometry or visibility might be
72*38e8c45fSAndroid Build Coastguard Worker     // different. And we can uniquely identify the node by keeping track of the nodes leading up to
73*38e8c45fSAndroid Build Coastguard Worker     // it. But to be more efficient we only need to track the nodes id and the top mirror root path.
74*38e8c45fSAndroid Build Coastguard Worker     // So C for example, would have the following unique traversal paths:
75*38e8c45fSAndroid Build Coastguard Worker     //  - {Traversal path id = 3}
76*38e8c45fSAndroid Build Coastguard Worker     //  - {Traversal path id = 3, mirrorRootIds = 5}
77*38e8c45fSAndroid Build Coastguard Worker     //  - {Traversal path id = 3, mirrorRootIds = 6}
78*38e8c45fSAndroid Build Coastguard Worker     //  - {Traversal path id = 3, mirrorRootIds = 6, 5}
79*38e8c45fSAndroid Build Coastguard Worker 
80*38e8c45fSAndroid Build Coastguard Worker     struct TraversalPath {
81*38e8c45fSAndroid Build Coastguard Worker         uint32_t id;
82*38e8c45fSAndroid Build Coastguard Worker         LayerHierarchy::Variant variant;
83*38e8c45fSAndroid Build Coastguard Worker         // Mirrored layers can have a different geometry than their parents so we need to track
84*38e8c45fSAndroid Build Coastguard Worker         // the mirror roots in the traversal.
85*38e8c45fSAndroid Build Coastguard Worker         ftl::SmallVector<uint32_t, 5> mirrorRootIds;
86*38e8c45fSAndroid Build Coastguard Worker         // Relative layers can be visited twice, once by their parent and then once again by
87*38e8c45fSAndroid Build Coastguard Worker         // their relative parent. We keep track of the roots here to detect any loops in the
88*38e8c45fSAndroid Build Coastguard Worker         // hierarchy. If a relative root already exists in the list while building the
89*38e8c45fSAndroid Build Coastguard Worker         // TraversalPath, it means that somewhere in the hierarchy two layers are relatively
90*38e8c45fSAndroid Build Coastguard Worker         // parented to each other.
91*38e8c45fSAndroid Build Coastguard Worker         ftl::SmallVector<uint32_t, 5> relativeRootIds;
92*38e8c45fSAndroid Build Coastguard Worker         // First duplicate relative root id found. If this is a valid layer id that means we are
93*38e8c45fSAndroid Build Coastguard Worker         // in a loop.
94*38e8c45fSAndroid Build Coastguard Worker         uint32_t invalidRelativeRootId = UNASSIGNED_LAYER_ID;
95*38e8c45fSAndroid Build Coastguard Worker         // See isAttached()
96*38e8c45fSAndroid Build Coastguard Worker         bool detached = false;
hasRelZLoopTraversalPath97*38e8c45fSAndroid Build Coastguard Worker         bool hasRelZLoop() const { return invalidRelativeRootId != UNASSIGNED_LAYER_ID; }
98*38e8c45fSAndroid Build Coastguard Worker         // Returns true if this node is reached via one or more relative parents.
isRelativeTraversalPath99*38e8c45fSAndroid Build Coastguard Worker         bool isRelative() const { return !relativeRootIds.empty(); }
100*38e8c45fSAndroid Build Coastguard Worker         // Returns true if the node or its parents are not Detached.
isAttachedTraversalPath101*38e8c45fSAndroid Build Coastguard Worker         bool isAttached() const { return !detached; }
102*38e8c45fSAndroid Build Coastguard Worker         // Returns true if the node is a clone.
isCloneTraversalPath103*38e8c45fSAndroid Build Coastguard Worker         bool isClone() const { return !mirrorRootIds.empty(); }
104*38e8c45fSAndroid Build Coastguard Worker 
105*38e8c45fSAndroid Build Coastguard Worker         bool operator==(const TraversalPath& other) const {
106*38e8c45fSAndroid Build Coastguard Worker             return id == other.id && mirrorRootIds == other.mirrorRootIds;
107*38e8c45fSAndroid Build Coastguard Worker         }
108*38e8c45fSAndroid Build Coastguard Worker         std::string toString() const;
109*38e8c45fSAndroid Build Coastguard Worker 
110*38e8c45fSAndroid Build Coastguard Worker         static const TraversalPath ROOT;
111*38e8c45fSAndroid Build Coastguard Worker     };
112*38e8c45fSAndroid Build Coastguard Worker 
113*38e8c45fSAndroid Build Coastguard Worker     struct TraversalPathHash {
operatorTraversalPathHash114*38e8c45fSAndroid Build Coastguard Worker         std::size_t operator()(const LayerHierarchy::TraversalPath& key) const {
115*38e8c45fSAndroid Build Coastguard Worker             uint32_t hashCode = key.id * 31;
116*38e8c45fSAndroid Build Coastguard Worker             for (uint32_t mirrorRootId : key.mirrorRootIds) {
117*38e8c45fSAndroid Build Coastguard Worker                 hashCode += mirrorRootId * 31;
118*38e8c45fSAndroid Build Coastguard Worker             }
119*38e8c45fSAndroid Build Coastguard Worker             return std::hash<size_t>{}(hashCode);
120*38e8c45fSAndroid Build Coastguard Worker         }
121*38e8c45fSAndroid Build Coastguard Worker     };
122*38e8c45fSAndroid Build Coastguard Worker 
123*38e8c45fSAndroid Build Coastguard Worker     // Helper class to add nodes to an existing traversal id and removes the
124*38e8c45fSAndroid Build Coastguard Worker     // node when it goes out of scope.
125*38e8c45fSAndroid Build Coastguard Worker     class ScopedAddToTraversalPath {
126*38e8c45fSAndroid Build Coastguard Worker     public:
127*38e8c45fSAndroid Build Coastguard Worker         ScopedAddToTraversalPath(TraversalPath& traversalPath, uint32_t layerId,
128*38e8c45fSAndroid Build Coastguard Worker                                  LayerHierarchy::Variant variantArg);
129*38e8c45fSAndroid Build Coastguard Worker         ~ScopedAddToTraversalPath();
130*38e8c45fSAndroid Build Coastguard Worker 
131*38e8c45fSAndroid Build Coastguard Worker     private:
132*38e8c45fSAndroid Build Coastguard Worker         TraversalPath& mTraversalPath;
133*38e8c45fSAndroid Build Coastguard Worker         TraversalPath mParentPath;
134*38e8c45fSAndroid Build Coastguard Worker     };
135*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy(RequestedLayerState* layer);
136*38e8c45fSAndroid Build Coastguard Worker 
137*38e8c45fSAndroid Build Coastguard Worker     // Visitor function that provides the hierarchy node and a traversal id which uniquely
138*38e8c45fSAndroid Build Coastguard Worker     // identifies how was visited. The hierarchy contains a pointer to the RequestedLayerState.
139*38e8c45fSAndroid Build Coastguard Worker     // Return false to stop traversing down the hierarchy.
140*38e8c45fSAndroid Build Coastguard Worker     typedef std::function<bool(const LayerHierarchy& hierarchy,
141*38e8c45fSAndroid Build Coastguard Worker                                const LayerHierarchy::TraversalPath& traversalPath)>
142*38e8c45fSAndroid Build Coastguard Worker             Visitor;
143*38e8c45fSAndroid Build Coastguard Worker 
144*38e8c45fSAndroid Build Coastguard Worker     // Traverse the hierarchy and visit all child variants.
traverse(const Visitor & visitor)145*38e8c45fSAndroid Build Coastguard Worker     void traverse(const Visitor& visitor) const {
146*38e8c45fSAndroid Build Coastguard Worker         TraversalPath root = TraversalPath::ROOT;
147*38e8c45fSAndroid Build Coastguard Worker         if (mLayer) {
148*38e8c45fSAndroid Build Coastguard Worker             root.id = mLayer->id;
149*38e8c45fSAndroid Build Coastguard Worker         }
150*38e8c45fSAndroid Build Coastguard Worker         traverse(visitor, root, /*depth=*/0);
151*38e8c45fSAndroid Build Coastguard Worker     }
152*38e8c45fSAndroid Build Coastguard Worker 
153*38e8c45fSAndroid Build Coastguard Worker     // Traverse the hierarchy in z-order, skipping children that have relative parents.
traverseInZOrder(const Visitor & visitor)154*38e8c45fSAndroid Build Coastguard Worker     void traverseInZOrder(const Visitor& visitor) const {
155*38e8c45fSAndroid Build Coastguard Worker         TraversalPath root = TraversalPath::ROOT;
156*38e8c45fSAndroid Build Coastguard Worker         if (mLayer) {
157*38e8c45fSAndroid Build Coastguard Worker             root.id = mLayer->id;
158*38e8c45fSAndroid Build Coastguard Worker         }
159*38e8c45fSAndroid Build Coastguard Worker         traverseInZOrder(visitor, root);
160*38e8c45fSAndroid Build Coastguard Worker     }
161*38e8c45fSAndroid Build Coastguard Worker 
162*38e8c45fSAndroid Build Coastguard Worker     const RequestedLayerState* getLayer() const;
163*38e8c45fSAndroid Build Coastguard Worker     const LayerHierarchy* getRelativeParent() const;
164*38e8c45fSAndroid Build Coastguard Worker     const LayerHierarchy* getParent() const;
165*38e8c45fSAndroid Build Coastguard Worker     friend std::ostream& operator<<(std::ostream& os, const LayerHierarchy& obj) {
166*38e8c45fSAndroid Build Coastguard Worker         std::string prefix = " ";
167*38e8c45fSAndroid Build Coastguard Worker         obj.dump(os, prefix, LayerHierarchy::Variant::Attached, /*isLastChild=*/false,
168*38e8c45fSAndroid Build Coastguard Worker                  /*includeMirroredHierarchy*/ false);
169*38e8c45fSAndroid Build Coastguard Worker         return os;
170*38e8c45fSAndroid Build Coastguard Worker     }
dump()171*38e8c45fSAndroid Build Coastguard Worker     std::string dump() const {
172*38e8c45fSAndroid Build Coastguard Worker         std::string prefix = " ";
173*38e8c45fSAndroid Build Coastguard Worker         std::ostringstream os;
174*38e8c45fSAndroid Build Coastguard Worker         dump(os, prefix, LayerHierarchy::Variant::Attached, /*isLastChild=*/false,
175*38e8c45fSAndroid Build Coastguard Worker              /*includeMirroredHierarchy*/ true);
176*38e8c45fSAndroid Build Coastguard Worker         return os.str();
177*38e8c45fSAndroid Build Coastguard Worker     }
178*38e8c45fSAndroid Build Coastguard Worker 
179*38e8c45fSAndroid Build Coastguard Worker     std::string getDebugStringShort() const;
180*38e8c45fSAndroid Build Coastguard Worker     // Traverse the hierarchy and return true if loops are found. The outInvalidRelativeRoot
181*38e8c45fSAndroid Build Coastguard Worker     // will contain the first relative root that was visited twice in a traversal.
182*38e8c45fSAndroid Build Coastguard Worker     bool hasRelZLoop(uint32_t& outInvalidRelativeRoot) const;
183*38e8c45fSAndroid Build Coastguard Worker     std::vector<std::pair<LayerHierarchy*, Variant>> mChildren;
184*38e8c45fSAndroid Build Coastguard Worker 
185*38e8c45fSAndroid Build Coastguard Worker private:
186*38e8c45fSAndroid Build Coastguard Worker     friend LayerHierarchyBuilder;
187*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly);
188*38e8c45fSAndroid Build Coastguard Worker     void addChild(LayerHierarchy*, LayerHierarchy::Variant);
189*38e8c45fSAndroid Build Coastguard Worker     void removeChild(LayerHierarchy*);
190*38e8c45fSAndroid Build Coastguard Worker     void sortChildrenByZOrder();
191*38e8c45fSAndroid Build Coastguard Worker     void updateChild(LayerHierarchy*, LayerHierarchy::Variant);
192*38e8c45fSAndroid Build Coastguard Worker     void traverseInZOrder(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
193*38e8c45fSAndroid Build Coastguard Worker     void traverse(const Visitor& visitor, LayerHierarchy::TraversalPath& parent,
194*38e8c45fSAndroid Build Coastguard Worker                   uint32_t depth = 0) const;
195*38e8c45fSAndroid Build Coastguard Worker     void dump(std::ostream& out, const std::string& prefix, LayerHierarchy::Variant variant,
196*38e8c45fSAndroid Build Coastguard Worker               bool isLastChild, bool includeMirroredHierarchy) const;
197*38e8c45fSAndroid Build Coastguard Worker 
198*38e8c45fSAndroid Build Coastguard Worker     const RequestedLayerState* mLayer;
199*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy* mParent = nullptr;
200*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy* mRelativeParent = nullptr;
201*38e8c45fSAndroid Build Coastguard Worker };
202*38e8c45fSAndroid Build Coastguard Worker 
203*38e8c45fSAndroid Build Coastguard Worker // Given a list of RequestedLayerState, this class will build a root hierarchy and an
204*38e8c45fSAndroid Build Coastguard Worker // offscreen hierarchy. The builder also has an update method which can update an existing
205*38e8c45fSAndroid Build Coastguard Worker // hierarchy from a list of RequestedLayerState and associated change flags.
206*38e8c45fSAndroid Build Coastguard Worker class LayerHierarchyBuilder {
207*38e8c45fSAndroid Build Coastguard Worker public:
208*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchyBuilder() = default;
209*38e8c45fSAndroid Build Coastguard Worker     void update(LayerLifecycleManager& layerLifecycleManager);
210*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy getPartialHierarchy(uint32_t, bool childrenOnly) const;
211*38e8c45fSAndroid Build Coastguard Worker     const LayerHierarchy& getHierarchy() const;
212*38e8c45fSAndroid Build Coastguard Worker     const LayerHierarchy& getOffscreenHierarchy() const;
213*38e8c45fSAndroid Build Coastguard Worker     std::string getDebugString(uint32_t layerId, uint32_t depth = 0) const;
214*38e8c45fSAndroid Build Coastguard Worker     void dumpLayerSample(const LayerHierarchy& layerHierarchy) const;
215*38e8c45fSAndroid Build Coastguard Worker 
216*38e8c45fSAndroid Build Coastguard Worker private:
217*38e8c45fSAndroid Build Coastguard Worker     void logSampledChildren(const LayerHierarchy& hierarchy) const;
218*38e8c45fSAndroid Build Coastguard Worker 
219*38e8c45fSAndroid Build Coastguard Worker     void onLayerAdded(RequestedLayerState* layer);
220*38e8c45fSAndroid Build Coastguard Worker     void attachToParent(LayerHierarchy*);
221*38e8c45fSAndroid Build Coastguard Worker     void detachFromParent(LayerHierarchy*);
222*38e8c45fSAndroid Build Coastguard Worker     void attachToRelativeParent(LayerHierarchy*);
223*38e8c45fSAndroid Build Coastguard Worker     void detachFromRelativeParent(LayerHierarchy*);
224*38e8c45fSAndroid Build Coastguard Worker     std::vector<LayerHierarchy*> getDescendants(LayerHierarchy*);
225*38e8c45fSAndroid Build Coastguard Worker     void attachHierarchyToRelativeParent(LayerHierarchy*);
226*38e8c45fSAndroid Build Coastguard Worker     void detachHierarchyFromRelativeParent(LayerHierarchy*);
227*38e8c45fSAndroid Build Coastguard Worker     void init(const std::vector<std::unique_ptr<RequestedLayerState>>&);
228*38e8c45fSAndroid Build Coastguard Worker     void doUpdate(const std::vector<std::unique_ptr<RequestedLayerState>>& layers,
229*38e8c45fSAndroid Build Coastguard Worker                   const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers);
230*38e8c45fSAndroid Build Coastguard Worker     void onLayerDestroyed(RequestedLayerState* layer);
231*38e8c45fSAndroid Build Coastguard Worker     void updateMirrorLayer(RequestedLayerState* layer);
232*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy* getHierarchyFromId(uint32_t layerId, bool crashOnFailure = true);
233*38e8c45fSAndroid Build Coastguard Worker 
234*38e8c45fSAndroid Build Coastguard Worker     std::unordered_map<uint32_t, LayerHierarchy*> mLayerIdToHierarchy;
235*38e8c45fSAndroid Build Coastguard Worker     std::vector<std::unique_ptr<LayerHierarchy>> mHierarchies;
236*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy mRoot{nullptr};
237*38e8c45fSAndroid Build Coastguard Worker     LayerHierarchy mOffscreenRoot{nullptr};
238*38e8c45fSAndroid Build Coastguard Worker     bool mInitialized = false;
239*38e8c45fSAndroid Build Coastguard Worker };
240*38e8c45fSAndroid Build Coastguard Worker 
241*38e8c45fSAndroid Build Coastguard Worker } // namespace android::surfaceflinger::frontend
242