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