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 "RequestedLayerState.h" 21 #include "ftl/small_vector.h" 22 23 namespace android::surfaceflinger::frontend { 24 class LayerHierarchyBuilder; 25 26 // LayerHierarchy allows us to navigate the layer hierarchy in z-order, or depth first traversal. 27 // The hierarchy is created from a set of RequestedLayerStates. The hierarchy itself does not 28 // contain additional states. Instead, it is a representation of RequestedLayerStates as a graph. 29 // 30 // Each node in the hierarchy can be visited by multiple parents (making this a graph). While 31 // traversing the hierarchy, a new concept called Variant can be used to understand the 32 // relationship of the layer to its parent. The following variants are possible: 33 // Attached - child of the parent 34 // Detached - child of the parent but currently relative parented to another layer 35 // Relative - relative child of the parent 36 // Mirror - mirrored from another layer 37 // 38 // By representing the hierarchy as a graph, we can represent mirrored layer hierarchies without 39 // cloning the layer requested state. The mirrored hierarchy and its corresponding 40 // RequestedLayerStates are kept in sync because the mirrored hierarchy does not clone any 41 // states. 42 class LayerHierarchy { 43 public: 44 enum Variant : uint32_t { 45 Attached, // child of the parent 46 Detached, // child of the parent but currently relative parented to another layer 47 Relative, // relative child of the parent 48 Mirror, // mirrored from another layer 49 ftl_first = Attached, 50 ftl_last = Mirror, 51 }; 52 // Represents a unique path to a node. 53 // The layer hierarchy is represented as a graph. Each node can be visited by multiple parents. 54 // This allows us to represent mirroring in an efficient way. See the example below: 55 // root 56 // ├─ A {Traversal path id = 1} 57 // ├─ B {Traversal path id = 2} 58 // │ ├─ C {Traversal path id = 3} 59 // │ ├─ D {Traversal path id = 4} 60 // │ └─ E {Traversal path id = 5} 61 // ├─ F (Mirrors B) {Traversal path id = 6} 62 // └─ G (Mirrors F) {Traversal path id = 7} 63 // 64 // C, D and E can be traversed via B or via F then B or via G then F then B. 65 // 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} 70 // - {Traversal path id = 3, mirrorRootId = 6} 71 // - {Traversal path id = 3, mirrorRootId = 7} 72 73 struct TraversalPath { 74 uint32_t id; 75 LayerHierarchy::Variant variant; 76 // Mirrored layers can have a different geometry than their parents so we need to track 77 // the mirror roots in the traversal. 78 uint32_t mirrorRootId = UNASSIGNED_LAYER_ID; 79 // Relative layers can be visited twice, once by their parent and then once again by 80 // their relative parent. We keep track of the roots here to detect any loops in the 81 // hierarchy. If a relative root already exists in the list while building the 82 // TraversalPath, it means that somewhere in the hierarchy two layers are relatively 83 // parented to each other. 84 ftl::SmallVector<uint32_t, 5> relativeRootIds; 85 // First duplicate relative root id found. If this is a valid layer id that means we are 86 // in a loop. 87 uint32_t invalidRelativeRootId = UNASSIGNED_LAYER_ID; 88 // See isAttached() 89 bool detached = false; hasRelZLoopTraversalPath90 bool hasRelZLoop() const { return invalidRelativeRootId != UNASSIGNED_LAYER_ID; } 91 // Returns true if this node is reached via one or more relative parents. isRelativeTraversalPath92 bool isRelative() const { return !relativeRootIds.empty(); } 93 // Returns true if the node or its parents are not Detached. isAttachedTraversalPath94 bool isAttached() const { return !detached; } 95 // Returns true if the node is a clone. isCloneTraversalPath96 bool isClone() const { return mirrorRootId != UNASSIGNED_LAYER_ID; } 97 TraversalPath getMirrorRoot() const; 98 99 bool operator==(const TraversalPath& other) const { 100 return id == other.id && mirrorRootId == other.mirrorRootId; 101 } 102 std::string toString() const; 103 104 static const TraversalPath ROOT; 105 }; 106 107 struct TraversalPathHash { operatorTraversalPathHash108 std::size_t operator()(const LayerHierarchy::TraversalPath& key) const { 109 uint32_t hashCode = key.id * 31; 110 if (key.mirrorRootId != UNASSIGNED_LAYER_ID) { 111 hashCode += key.mirrorRootId * 31; 112 } 113 return std::hash<size_t>{}(hashCode); 114 } 115 }; 116 117 // 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; 127 TraversalPath mParentPath; 128 }; 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. traverse(const Visitor & visitor)139 void traverse(const Visitor& visitor) const { 140 TraversalPath root = TraversalPath::ROOT; 141 if (mLayer) { 142 root.id = mLayer->id; 143 } 144 traverse(visitor, root); 145 } 146 147 // Traverse the hierarchy in z-order, skipping children that have relative parents. traverseInZOrder(const Visitor & visitor)148 void traverseInZOrder(const Visitor& visitor) const { 149 TraversalPath root = TraversalPath::ROOT; 150 if (mLayer) { 151 root.id = mLayer->id; 152 } 153 traverseInZOrder(visitor, root); 154 } 155 156 const RequestedLayerState* getLayer() const; 157 const LayerHierarchy* getRelativeParent() const; 158 const LayerHierarchy* getParent() const; 159 std::string getDebugString(const char* prefix = "") const; 160 std::string getDebugStringShort() const; 161 // Traverse the hierarchy and return true if loops are found. The outInvalidRelativeRoot 162 // will contain the first relative root that was visited twice in a traversal. 163 bool hasRelZLoop(uint32_t& outInvalidRelativeRoot) const; 164 std::vector<std::pair<LayerHierarchy*, Variant>> mChildren; 165 166 private: 167 friend LayerHierarchyBuilder; 168 LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly); 169 void addChild(LayerHierarchy*, LayerHierarchy::Variant); 170 void removeChild(LayerHierarchy*); 171 void sortChildrenByZOrder(); 172 void updateChild(LayerHierarchy*, LayerHierarchy::Variant); 173 void traverseInZOrder(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const; 174 void traverse(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const; 175 176 const RequestedLayerState* mLayer; 177 LayerHierarchy* mParent = nullptr; 178 LayerHierarchy* mRelativeParent = nullptr; 179 }; 180 181 // Given a list of RequestedLayerState, this class will build a root hierarchy and an 182 // offscreen hierarchy. The builder also has an update method which can update an existing 183 // hierarchy from a list of RequestedLayerState and associated change flags. 184 class LayerHierarchyBuilder { 185 public: 186 LayerHierarchyBuilder(const std::vector<std::unique_ptr<RequestedLayerState>>&); 187 void update(const std::vector<std::unique_ptr<RequestedLayerState>>& layers, 188 const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers); 189 LayerHierarchy getPartialHierarchy(uint32_t, bool childrenOnly) const; 190 const LayerHierarchy& getHierarchy() const; 191 const LayerHierarchy& getOffscreenHierarchy() const; 192 std::string getDebugString(uint32_t layerId, uint32_t depth = 0) const; 193 194 private: 195 void onLayerAdded(RequestedLayerState* layer); 196 void attachToParent(LayerHierarchy*); 197 void detachFromParent(LayerHierarchy*); 198 void attachToRelativeParent(LayerHierarchy*); 199 void detachFromRelativeParent(LayerHierarchy*); 200 void attachHierarchyToRelativeParent(LayerHierarchy*); 201 void detachHierarchyFromRelativeParent(LayerHierarchy*); 202 203 void onLayerDestroyed(RequestedLayerState* layer); 204 void updateMirrorLayer(RequestedLayerState* layer); 205 LayerHierarchy* getHierarchyFromId(uint32_t layerId, bool crashOnFailure = true); 206 std::unordered_map<uint32_t, LayerHierarchy*> mLayerIdToHierarchy; 207 std::vector<std::unique_ptr<LayerHierarchy>> mHierarchies; 208 LayerHierarchy mRoot{nullptr}; 209 LayerHierarchy mOffscreenRoot{nullptr}; 210 }; 211 212 } // namespace android::surfaceflinger::frontend 213