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