SF: Introduce LayerHierarchy and LayerHierarchyBuilder
LayerHierarchy allows us to navigate the layer tree in
z-order, or depth first traversal. The hierarchy is created
from a set of requested layer states and the structure
itself does not contain additional layer states.
This is in contrast to the existing model where the Layer
class contained information about the hierarchy it belonged to.
By breaking out of this model, we can make the layer class
(now called RequestedLayerState) simpler and separate client
states from the hierarchy.
This also allows us to construct more flexible hierarchies that
handles mirroring and relative parents more efficiently.
When traversing the hierarchy, each node can be visited multiple
times. For example, it could be visited as a child, a relative child,
or a mirrored child. The class introduces the concept of variants
to distinguish the traversal path.
In the upcoming cl, this traversal will be used to compute the final
composition state in z-order.
Bug: 238781169
Test: presubmit
Change-Id: I9902e521df2d47556e3a671e2134d5be8cd2a73f
diff --git a/services/surfaceflinger/Android.bp b/services/surfaceflinger/Android.bp
index b1bd705..9f7a687 100644
--- a/services/surfaceflinger/Android.bp
+++ b/services/surfaceflinger/Android.bp
@@ -157,6 +157,7 @@
"EventLog/EventLog.cpp",
"FrontEnd/LayerCreationArgs.cpp",
"FrontEnd/LayerHandle.cpp",
+ "FrontEnd/LayerHierarchy.cpp",
"FrontEnd/LayerLifecycleManager.cpp",
"FrontEnd/RequestedLayerState.cpp",
"FrontEnd/TransactionHandler.cpp",
diff --git a/services/surfaceflinger/FrontEnd/LayerHierarchy.cpp b/services/surfaceflinger/FrontEnd/LayerHierarchy.cpp
new file mode 100644
index 0000000..db4e8af
--- /dev/null
+++ b/services/surfaceflinger/FrontEnd/LayerHierarchy.cpp
@@ -0,0 +1,472 @@
+/*
+ * Copyright 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define ATRACE_TAG ATRACE_TAG_GRAPHICS
+#undef LOG_TAG
+#define LOG_TAG "LayerHierarchy"
+
+#include "LayerHierarchy.h"
+#include "SwapErase.h"
+
+namespace android::surfaceflinger::frontend {
+
+namespace {
+auto layerZCompare = [](const std::pair<LayerHierarchy*, LayerHierarchy::Variant>& lhs,
+ const std::pair<LayerHierarchy*, LayerHierarchy::Variant>& rhs) {
+ auto lhsLayer = lhs.first->getLayer();
+ auto rhsLayer = rhs.first->getLayer();
+ if (lhsLayer->layerStack != rhsLayer->layerStack) {
+ return lhsLayer->layerStack.id < rhsLayer->layerStack.id;
+ }
+ if (lhsLayer->z != rhsLayer->z) {
+ return lhsLayer->z < rhsLayer->z;
+ }
+ return lhsLayer->id < rhsLayer->id;
+};
+
+void insertSorted(std::vector<std::pair<LayerHierarchy*, LayerHierarchy::Variant>>& vec,
+ std::pair<LayerHierarchy*, LayerHierarchy::Variant> value) {
+ auto it = std::upper_bound(vec.begin(), vec.end(), value, layerZCompare);
+ vec.insert(it, std::move(value));
+}
+} // namespace
+
+LayerHierarchy::LayerHierarchy(RequestedLayerState* layer) : mLayer(layer) {}
+
+LayerHierarchy::LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly) {
+ mLayer = (childrenOnly) ? nullptr : hierarchy.mLayer;
+ mChildren = hierarchy.mChildren;
+}
+
+void LayerHierarchy::traverse(const Visitor& visitor,
+ LayerHierarchy::TraversalPath& traversalPath) const {
+ if (mLayer) {
+ bool breakTraversal = !visitor(*this, traversalPath);
+ if (breakTraversal) {
+ return;
+ }
+ }
+ if (traversalPath.hasRelZLoop()) {
+ LOG_ALWAYS_FATAL("Found relative z loop layerId:%d", traversalPath.invalidRelativeRootId);
+ }
+ for (auto& [child, childVariant] : mChildren) {
+ ScopedAddToTraversalPath addChildToTraversalPath(traversalPath, child->mLayer->id,
+ childVariant);
+ child->traverse(visitor, traversalPath);
+ }
+}
+
+void LayerHierarchy::traverseInZOrder(const Visitor& visitor,
+ LayerHierarchy::TraversalPath& traversalPath) const {
+ bool traverseThisLayer = (mLayer != nullptr);
+ for (auto it = mChildren.begin(); it < mChildren.end(); it++) {
+ auto& [child, childVariant] = *it;
+ if (traverseThisLayer && child->getLayer()->z >= 0) {
+ bool breakTraversal = !visitor(*this, traversalPath);
+ if (breakTraversal) {
+ return;
+ }
+ traverseThisLayer = false;
+ }
+ if (childVariant == LayerHierarchy::Variant::Detached) {
+ continue;
+ }
+ ScopedAddToTraversalPath addChildToTraversalPath(traversalPath, child->mLayer->id,
+ childVariant);
+ child->traverseInZOrder(visitor, traversalPath);
+ }
+
+ if (traverseThisLayer) {
+ visitor(*this, traversalPath);
+ }
+}
+
+void LayerHierarchy::addChild(LayerHierarchy* child, LayerHierarchy::Variant variant) {
+ insertSorted(mChildren, {child, variant});
+}
+
+void LayerHierarchy::removeChild(LayerHierarchy* child) {
+ auto it = std::find_if(mChildren.begin(), mChildren.end(),
+ [child](const std::pair<LayerHierarchy*, Variant>& x) {
+ return x.first == child;
+ });
+ if (it == mChildren.end()) {
+ LOG_ALWAYS_FATAL("Could not find child!");
+ }
+ mChildren.erase(it);
+}
+
+void LayerHierarchy::sortChildrenByZOrder() {
+ std::sort(mChildren.begin(), mChildren.end(), layerZCompare);
+}
+
+void LayerHierarchy::updateChild(LayerHierarchy* hierarchy, LayerHierarchy::Variant variant) {
+ auto it = std::find_if(mChildren.begin(), mChildren.end(),
+ [hierarchy](std::pair<LayerHierarchy*, Variant>& child) {
+ return child.first == hierarchy;
+ });
+ if (it == mChildren.end()) {
+ LOG_ALWAYS_FATAL("Could not find child!");
+ } else {
+ it->second = variant;
+ }
+}
+
+const RequestedLayerState* LayerHierarchy::getLayer() const {
+ return mLayer;
+}
+
+std::string LayerHierarchy::getDebugStringShort() const {
+ std::string debug = "LayerHierarchy{";
+ debug += ((mLayer) ? mLayer->getDebugStringShort() : "root") + " ";
+ if (mChildren.empty()) {
+ debug += "no children";
+ } else {
+ debug += std::to_string(mChildren.size()) + " children";
+ }
+ return debug + "}";
+}
+
+std::string LayerHierarchy::getDebugString(const char* prefix) const {
+ std::string debug = prefix + getDebugStringShort();
+ for (auto& [child, childVariant] : mChildren) {
+ std::string childPrefix = " " + std::string(prefix) + " " + std::to_string(childVariant);
+ debug += "\n" + child->getDebugString(childPrefix.c_str());
+ }
+ return debug;
+}
+
+bool LayerHierarchy::hasRelZLoop(uint32_t& outInvalidRelativeRoot) const {
+ outInvalidRelativeRoot = UNASSIGNED_LAYER_ID;
+ traverse([&outInvalidRelativeRoot](const LayerHierarchy&,
+ const LayerHierarchy::TraversalPath& traversalPath) -> bool {
+ if (traversalPath.hasRelZLoop()) {
+ outInvalidRelativeRoot = traversalPath.invalidRelativeRootId;
+ return false;
+ }
+ return true;
+ });
+ return outInvalidRelativeRoot != UNASSIGNED_LAYER_ID;
+}
+
+LayerHierarchyBuilder::LayerHierarchyBuilder(
+ const std::vector<std::unique_ptr<RequestedLayerState>>& layers) {
+ mHierarchies.reserve(layers.size());
+ mLayerIdToHierarchy.reserve(layers.size());
+ for (auto& layer : layers) {
+ mHierarchies.emplace_back(std::make_unique<LayerHierarchy>(layer.get()));
+ mLayerIdToHierarchy[layer->id] = mHierarchies.back().get();
+ }
+ for (const auto& layer : layers) {
+ onLayerAdded(layer.get());
+ }
+ detachHierarchyFromRelativeParent(&mOffscreenRoot);
+}
+
+void LayerHierarchyBuilder::attachToParent(LayerHierarchy* hierarchy) {
+ auto layer = hierarchy->mLayer;
+ LayerHierarchy::Variant type = layer->hasValidRelativeParent()
+ ? LayerHierarchy::Variant::Detached
+ : LayerHierarchy::Variant::Attached;
+
+ LayerHierarchy* parent;
+
+ if (layer->parentId != UNASSIGNED_LAYER_ID) {
+ parent = getHierarchyFromId(layer->parentId);
+ } else if (layer->canBeRoot) {
+ parent = &mRoot;
+ } else {
+ parent = &mOffscreenRoot;
+ }
+ parent->addChild(hierarchy, type);
+ hierarchy->mParent = parent;
+}
+
+void LayerHierarchyBuilder::detachFromParent(LayerHierarchy* hierarchy) {
+ hierarchy->mParent->removeChild(hierarchy);
+ hierarchy->mParent = nullptr;
+}
+
+void LayerHierarchyBuilder::attachToRelativeParent(LayerHierarchy* hierarchy) {
+ auto layer = hierarchy->mLayer;
+ if (!layer->hasValidRelativeParent() || hierarchy->mRelativeParent) {
+ return;
+ }
+
+ if (layer->relativeParentId != UNASSIGNED_LAYER_ID) {
+ hierarchy->mRelativeParent = getHierarchyFromId(layer->relativeParentId);
+ } else {
+ hierarchy->mRelativeParent = &mOffscreenRoot;
+ }
+ hierarchy->mRelativeParent->addChild(hierarchy, LayerHierarchy::Variant::Relative);
+ hierarchy->mParent->updateChild(hierarchy, LayerHierarchy::Variant::Detached);
+}
+
+void LayerHierarchyBuilder::detachFromRelativeParent(LayerHierarchy* hierarchy) {
+ if (hierarchy->mRelativeParent) {
+ hierarchy->mRelativeParent->removeChild(hierarchy);
+ }
+ hierarchy->mRelativeParent = nullptr;
+ hierarchy->mParent->updateChild(hierarchy, LayerHierarchy::Variant::Attached);
+}
+
+void LayerHierarchyBuilder::attachHierarchyToRelativeParent(LayerHierarchy* root) {
+ if (root->mLayer) {
+ attachToRelativeParent(root);
+ }
+ for (auto& [child, childVariant] : root->mChildren) {
+ if (childVariant == LayerHierarchy::Variant::Detached ||
+ childVariant == LayerHierarchy::Variant::Attached) {
+ attachHierarchyToRelativeParent(child);
+ }
+ }
+}
+
+void LayerHierarchyBuilder::detachHierarchyFromRelativeParent(LayerHierarchy* root) {
+ if (root->mLayer) {
+ detachFromRelativeParent(root);
+ }
+ for (auto& [child, childVariant] : root->mChildren) {
+ if (childVariant == LayerHierarchy::Variant::Detached ||
+ childVariant == LayerHierarchy::Variant::Attached) {
+ detachHierarchyFromRelativeParent(child);
+ }
+ }
+}
+
+void LayerHierarchyBuilder::onLayerAdded(RequestedLayerState* layer) {
+ LayerHierarchy* hierarchy = getHierarchyFromId(layer->id);
+ attachToParent(hierarchy);
+ attachToRelativeParent(hierarchy);
+
+ if (layer->mirrorId != UNASSIGNED_LAYER_ID) {
+ LayerHierarchy* mirror = getHierarchyFromId(layer->mirrorId);
+ hierarchy->addChild(mirror, LayerHierarchy::Variant::Mirror);
+ }
+}
+
+void LayerHierarchyBuilder::onLayerDestroyed(RequestedLayerState* layer) {
+ LayerHierarchy* hierarchy = getHierarchyFromId(layer->id, /*crashOnFailure=*/false);
+ if (!hierarchy) {
+ // Layer was never part of the hierarchy if it was created and destroyed in the same
+ // transaction.
+ return;
+ }
+ // detach from parent
+ detachFromRelativeParent(hierarchy);
+ detachFromParent(hierarchy);
+
+ // detach children
+ for (auto& [child, variant] : hierarchy->mChildren) {
+ if (variant == LayerHierarchy::Variant::Attached ||
+ variant == LayerHierarchy::Variant::Detached) {
+ mOffscreenRoot.addChild(child, LayerHierarchy::Variant::Attached);
+ child->mParent = &mOffscreenRoot;
+ } else if (variant == LayerHierarchy::Variant::Relative) {
+ mOffscreenRoot.addChild(child, LayerHierarchy::Variant::Attached);
+ child->mRelativeParent = &mOffscreenRoot;
+ }
+ }
+
+ swapErase(mHierarchies, [hierarchy](std::unique_ptr<LayerHierarchy>& layerHierarchy) {
+ return layerHierarchy.get() == hierarchy;
+ });
+ mLayerIdToHierarchy.erase(layer->id);
+}
+
+void LayerHierarchyBuilder::updateMirrorLayer(RequestedLayerState* layer) {
+ LayerHierarchy* hierarchy = getHierarchyFromId(layer->id);
+ auto it = hierarchy->mChildren.begin();
+ while (it != hierarchy->mChildren.end()) {
+ if (it->second == LayerHierarchy::Variant::Mirror) {
+ hierarchy->mChildren.erase(it);
+ break;
+ }
+ it++;
+ }
+
+ if (layer->mirrorId != UNASSIGNED_LAYER_ID) {
+ hierarchy->addChild(getHierarchyFromId(layer->mirrorId), LayerHierarchy::Variant::Mirror);
+ }
+}
+
+void LayerHierarchyBuilder::update(
+ const std::vector<std::unique_ptr<RequestedLayerState>>& layers,
+ const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers) {
+ // rebuild map
+ for (auto& layer : layers) {
+ if (layer->changes.test(RequestedLayerState::Changes::Created)) {
+ mHierarchies.emplace_back(std::make_unique<LayerHierarchy>(layer.get()));
+ mLayerIdToHierarchy[layer->id] = mHierarchies.back().get();
+ }
+ }
+
+ for (auto& layer : layers) {
+ if (layer->changes.get() == 0) {
+ continue;
+ }
+ if (layer->changes.test(RequestedLayerState::Changes::Created)) {
+ onLayerAdded(layer.get());
+ continue;
+ }
+ LayerHierarchy* hierarchy = getHierarchyFromId(layer->id);
+ if (layer->changes.test(RequestedLayerState::Changes::Parent)) {
+ detachFromParent(hierarchy);
+ attachToParent(hierarchy);
+ }
+ if (layer->changes.test(RequestedLayerState::Changes::RelativeParent)) {
+ detachFromRelativeParent(hierarchy);
+ attachToRelativeParent(hierarchy);
+ }
+ if (layer->changes.test(RequestedLayerState::Changes::Z)) {
+ hierarchy->mParent->sortChildrenByZOrder();
+ if (hierarchy->mRelativeParent) {
+ hierarchy->mRelativeParent->sortChildrenByZOrder();
+ }
+ }
+ if (layer->changes.test(RequestedLayerState::Changes::Mirror)) {
+ updateMirrorLayer(layer.get());
+ }
+ }
+
+ for (auto& layer : destroyedLayers) {
+ onLayerDestroyed(layer.get());
+ }
+ // When moving from onscreen to offscreen and vice versa, we need to attach and detach
+ // from our relative parents. This walks down both trees to do so. We can optimize this
+ // further by tracking onscreen, offscreen state in LayerHierarchy.
+ detachHierarchyFromRelativeParent(&mOffscreenRoot);
+ attachHierarchyToRelativeParent(&mRoot);
+}
+
+const LayerHierarchy& LayerHierarchyBuilder::getHierarchy() const {
+ return mRoot;
+}
+
+const LayerHierarchy& LayerHierarchyBuilder::getOffscreenHierarchy() const {
+ return mOffscreenRoot;
+}
+
+std::string LayerHierarchyBuilder::getDebugString(uint32_t layerId, uint32_t depth) const {
+ if (depth > 10) return "too deep, loop?";
+ if (layerId == UNASSIGNED_LAYER_ID) return "";
+ auto it = mLayerIdToHierarchy.find(layerId);
+ if (it == mLayerIdToHierarchy.end()) return "not found";
+
+ LayerHierarchy* hierarchy = it->second;
+ if (!hierarchy->mLayer) return "none";
+
+ std::string debug =
+ "[" + std::to_string(hierarchy->mLayer->id) + "] " + hierarchy->mLayer->name;
+ if (hierarchy->mRelativeParent) {
+ debug += " Relative:" + hierarchy->mRelativeParent->getDebugStringShort();
+ }
+ if (hierarchy->mParent) {
+ debug += " Parent:" + hierarchy->mParent->getDebugStringShort();
+ }
+ return debug;
+}
+
+LayerHierarchy LayerHierarchyBuilder::getPartialHierarchy(uint32_t layerId,
+ bool childrenOnly) const {
+ auto it = mLayerIdToHierarchy.find(layerId);
+ if (it == mLayerIdToHierarchy.end()) return {nullptr};
+
+ LayerHierarchy hierarchy(*it->second, childrenOnly);
+ return hierarchy;
+}
+
+LayerHierarchy* LayerHierarchyBuilder::getHierarchyFromId(uint32_t layerId, bool crashOnFailure) {
+ auto it = mLayerIdToHierarchy.find(layerId);
+ if (it == mLayerIdToHierarchy.end()) {
+ if (crashOnFailure) {
+ LOG_ALWAYS_FATAL("Could not find hierarchy for layer id %d", layerId);
+ }
+ return nullptr;
+ };
+
+ return it->second;
+}
+
+LayerHierarchy::TraversalPath LayerHierarchy::TraversalPath::ROOT_TRAVERSAL_ID =
+ {.id = UNASSIGNED_LAYER_ID, .variant = LayerHierarchy::Attached};
+
+std::string LayerHierarchy::TraversalPath::toString() const {
+ std::string debugString = "TraversalPath{.id = " + std::to_string(id);
+
+ if (!mirrorRootIds.empty()) {
+ debugString += ", .mirrorRootIds=";
+ for (auto rootId : mirrorRootIds) {
+ debugString += std::to_string(rootId) + ",";
+ }
+ }
+
+ if (!relativeRootIds.empty()) {
+ debugString += ", .relativeRootIds=";
+ for (auto rootId : relativeRootIds) {
+ debugString += std::to_string(rootId) + ",";
+ }
+ }
+
+ if (hasRelZLoop()) {
+ debugString += ", hasRelZLoop=true invalidRelativeRootId=";
+ debugString += std::to_string(invalidRelativeRootId) + ",";
+ }
+
+ debugString += "}";
+ return debugString;
+}
+
+// Helper class to update a passed in TraversalPath when visiting a child. When the object goes out
+// of scope the TraversalPath is reset to its original state.
+LayerHierarchy::ScopedAddToTraversalPath::ScopedAddToTraversalPath(TraversalPath& traversalPath,
+ uint32_t layerId,
+ LayerHierarchy::Variant variant)
+ : mTraversalPath(traversalPath),
+ mParentId(traversalPath.id),
+ mParentVariant(traversalPath.variant) {
+ // Update the traversal id with the child layer id and variant. Parent id and variant are
+ // stored to reset the id upon destruction.
+ traversalPath.id = layerId;
+ traversalPath.variant = variant;
+ if (variant == LayerHierarchy::Variant::Mirror) {
+ traversalPath.mirrorRootIds.emplace_back(layerId);
+ }
+ if (variant == LayerHierarchy::Variant::Relative) {
+ if (std::find(traversalPath.relativeRootIds.begin(), traversalPath.relativeRootIds.end(),
+ layerId) != traversalPath.relativeRootIds.end()) {
+ traversalPath.invalidRelativeRootId = layerId;
+ }
+ traversalPath.relativeRootIds.emplace_back(layerId);
+ }
+}
+LayerHierarchy::ScopedAddToTraversalPath::~ScopedAddToTraversalPath() {
+ // Reset the traversal id to its original parent state using the state that was saved in
+ // the constructor.
+ if (mTraversalPath.variant == LayerHierarchy::Variant::Mirror) {
+ mTraversalPath.mirrorRootIds.pop_back();
+ }
+ if (mTraversalPath.variant == LayerHierarchy::Variant::Relative) {
+ mTraversalPath.relativeRootIds.pop_back();
+ }
+ if (mTraversalPath.invalidRelativeRootId == mTraversalPath.id) {
+ mTraversalPath.invalidRelativeRootId = UNASSIGNED_LAYER_ID;
+ }
+ mTraversalPath.id = mParentId;
+ mTraversalPath.variant = mParentVariant;
+}
+
+} // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/LayerHierarchy.h b/services/surfaceflinger/FrontEnd/LayerHierarchy.h
new file mode 100644
index 0000000..f83a859
--- /dev/null
+++ b/services/surfaceflinger/FrontEnd/LayerHierarchy.h
@@ -0,0 +1,163 @@
+/*
+ * Copyright 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include "FrontEnd/LayerCreationArgs.h"
+#include "RequestedLayerState.h"
+#include "ftl/small_vector.h"
+
+namespace android::surfaceflinger::frontend {
+class LayerHierarchyBuilder;
+
+// LayerHierarchy allows us to navigate the layer hierarchy in z-order, or depth first traversal.
+// The hierarchy is created from a set of RequestedLayerStates. The hierarchy itself does not
+// contain additional states. Instead, it is a representation of RequestedLayerStates as a graph.
+//
+// Each node in the hierarchy can be visited by multiple parents (making this a graph). While
+// traversing the hierarchy, a new concept called Variant can be used to understand the
+// relationship of the layer to its parent. The following variants are possible:
+// Attached - child of the parent
+// Detached - child of the parent but currently relative parented to another layer
+// Relative - relative child of the parent
+// Mirror - mirrored from another layer
+//
+// By representing the hierarchy as a graph, we can represent mirrored layer hierarchies without
+// cloning the layer requested state. The mirrored hierarchy and its corresponding
+// RequestedLayerStates are kept in sync because the mirrored hierarchy does not clone any
+// states.
+class LayerHierarchy {
+public:
+ enum Variant {
+ Attached,
+ Detached,
+ Relative,
+ Mirror,
+ };
+ // Represents a unique path to a node.
+ struct TraversalPath {
+ uint32_t id;
+ LayerHierarchy::Variant variant;
+ // Mirrored layers can have a different geometry than their parents so we need to track
+ // the mirror roots in the traversal.
+ ftl::SmallVector<uint32_t, 5> mirrorRootIds;
+ // Relative layers can be visited twice, once by their parent and then once again by
+ // their relative parent. We keep track of the roots here to detect any loops in the
+ // hierarchy. If a relative root already exists in the list while building the
+ // TraversalPath, it means that somewhere in the hierarchy two layers are relatively
+ // parented to each other.
+ ftl::SmallVector<uint32_t, 5> relativeRootIds;
+ // First duplicate relative root id found. If this is a valid layer id that means we are
+ // in a loop.
+ uint32_t invalidRelativeRootId = UNASSIGNED_LAYER_ID;
+ bool hasRelZLoop() const { return invalidRelativeRootId != UNASSIGNED_LAYER_ID; }
+ bool isRelative() { return !relativeRootIds.empty(); }
+
+ bool operator==(const TraversalPath& other) const {
+ return id == other.id && mirrorRootIds == other.mirrorRootIds;
+ }
+ std::string toString() const;
+
+ static TraversalPath ROOT_TRAVERSAL_ID;
+ };
+
+ // Helper class to add nodes to an existing traversal id and removes the
+ // node when it goes out of scope.
+ class ScopedAddToTraversalPath {
+ public:
+ ScopedAddToTraversalPath(TraversalPath& traversalPath, uint32_t layerId,
+ LayerHierarchy::Variant variantArg);
+ ~ScopedAddToTraversalPath();
+
+ private:
+ TraversalPath& mTraversalPath;
+ uint32_t mParentId;
+ LayerHierarchy::Variant mParentVariant;
+ };
+ LayerHierarchy(RequestedLayerState* layer);
+
+ // Visitor function that provides the hierarchy node and a traversal id which uniquely
+ // identifies how was visited. The hierarchy contains a pointer to the RequestedLayerState.
+ // Return false to stop traversing down the hierarchy.
+ typedef std::function<bool(const LayerHierarchy& hierarchy,
+ const LayerHierarchy::TraversalPath& traversalPath)>
+ Visitor;
+
+ // Traverse the hierarchy and visit all child variants.
+ void traverse(const Visitor& visitor) const {
+ traverse(visitor, TraversalPath::ROOT_TRAVERSAL_ID);
+ }
+
+ // Traverse the hierarchy in z-order, skipping children that have relative parents.
+ void traverseInZOrder(const Visitor& visitor) const {
+ traverseInZOrder(visitor, TraversalPath::ROOT_TRAVERSAL_ID);
+ }
+
+ const RequestedLayerState* getLayer() const;
+ std::string getDebugString(const char* prefix = "") const;
+ std::string getDebugStringShort() const;
+ // Traverse the hierarchy and return true if loops are found. The outInvalidRelativeRoot
+ // will contain the first relative root that was visited twice in a traversal.
+ bool hasRelZLoop(uint32_t& outInvalidRelativeRoot) const;
+ std::vector<std::pair<LayerHierarchy*, Variant>> mChildren;
+
+private:
+ friend LayerHierarchyBuilder;
+ LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly);
+ void addChild(LayerHierarchy*, LayerHierarchy::Variant);
+ void removeChild(LayerHierarchy*);
+ void sortChildrenByZOrder();
+ void updateChild(LayerHierarchy*, LayerHierarchy::Variant);
+ void traverseInZOrder(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
+ void traverse(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
+
+ const RequestedLayerState* mLayer;
+ LayerHierarchy* mParent = nullptr;
+ LayerHierarchy* mRelativeParent = nullptr;
+};
+
+// Given a list of RequestedLayerState, this class will build a root hierarchy and an
+// offscreen hierarchy. The builder also has an update method which can update an existing
+// hierarchy from a list of RequestedLayerState and associated change flags.
+class LayerHierarchyBuilder {
+public:
+ LayerHierarchyBuilder(const std::vector<std::unique_ptr<RequestedLayerState>>&);
+ void update(const std::vector<std::unique_ptr<RequestedLayerState>>& layers,
+ const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers);
+ LayerHierarchy getPartialHierarchy(uint32_t, bool childrenOnly) const;
+ const LayerHierarchy& getHierarchy() const;
+ const LayerHierarchy& getOffscreenHierarchy() const;
+ std::string getDebugString(uint32_t layerId, uint32_t depth = 0) const;
+
+private:
+ void onLayerAdded(RequestedLayerState* layer);
+ void attachToParent(LayerHierarchy*);
+ void detachFromParent(LayerHierarchy*);
+ void attachToRelativeParent(LayerHierarchy*);
+ void detachFromRelativeParent(LayerHierarchy*);
+ void attachHierarchyToRelativeParent(LayerHierarchy*);
+ void detachHierarchyFromRelativeParent(LayerHierarchy*);
+
+ void onLayerDestroyed(RequestedLayerState* layer);
+ void updateMirrorLayer(RequestedLayerState* layer);
+ LayerHierarchy* getHierarchyFromId(uint32_t layerId, bool crashOnFailure = true);
+ std::unordered_map<uint32_t, LayerHierarchy*> mLayerIdToHierarchy;
+ std::vector<std::unique_ptr<LayerHierarchy>> mHierarchies;
+ LayerHierarchy mRoot{nullptr};
+ LayerHierarchy mOffscreenRoot{nullptr};
+};
+
+} // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp
index 1108246..d869ab5 100644
--- a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp
+++ b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp
@@ -42,10 +42,10 @@
it->second.owner.getDebugString().c_str());
}
- linkLayer(layer.parentId, layer.id);
- linkLayer(layer.relativeParentId, layer.id);
- linkLayer(layer.mirrorId, layer.id);
- linkLayer(layer.touchCropId, layer.id);
+ layer.parentId = linkLayer(layer.parentId, layer.id);
+ layer.relativeParentId = linkLayer(layer.relativeParentId, layer.id);
+ layer.mirrorId = linkLayer(layer.mirrorId, layer.id);
+ layer.touchCropId = linkLayer(layer.touchCropId, layer.id);
mLayers.emplace_back(std::move(newLayer));
}
@@ -83,10 +83,10 @@
RequestedLayerState& layer = it->second.owner;
- unlinkLayer(layer.parentId, layer.id);
- unlinkLayer(layer.relativeParentId, layer.id);
- unlinkLayer(layer.mirrorId, layer.id);
- unlinkLayer(layer.touchCropId, layer.id);
+ layer.parentId = unlinkLayer(layer.parentId, layer.id);
+ layer.relativeParentId = unlinkLayer(layer.relativeParentId, layer.id);
+ layer.mirrorId = unlinkLayer(layer.mirrorId, layer.id);
+ layer.touchCropId = unlinkLayer(layer.touchCropId, layer.id);
auto& references = it->second.references;
for (uint32_t linkedLayerId : references) {
@@ -195,15 +195,15 @@
if (oldParentId != layer->parentId) {
unlinkLayer(oldParentId, layer->id);
- linkLayer(layer->parentId, layer->id);
+ layer->parentId = linkLayer(layer->parentId, layer->id);
}
if (oldRelativeParentId != layer->relativeParentId) {
unlinkLayer(oldRelativeParentId, layer->id);
- linkLayer(layer->relativeParentId, layer->id);
+ layer->relativeParentId = linkLayer(layer->relativeParentId, layer->id);
}
if (oldTouchCropId != layer->touchCropId) {
unlinkLayer(oldTouchCropId, layer->id);
- linkLayer(layer->touchCropId, layer->id);
+ layer->touchCropId = linkLayer(layer->touchCropId, layer->id);
}
mGlobalChanges |= layer->changes &
@@ -283,26 +283,28 @@
return &it->second.references;
}
-void LayerLifecycleManager::linkLayer(uint32_t layerId, uint32_t layerToLink) {
- if (layerToLink && layerId != UNASSIGNED_LAYER_ID) {
- std::vector<uint32_t>* linkedLayers = getLinkedLayersFromId(layerId);
- if (!linkedLayers) {
- LOG_ALWAYS_FATAL("Could not find layer id %d to link %d", layerId, layerToLink);
- return;
- }
- linkedLayers->emplace_back(layerToLink);
+uint32_t LayerLifecycleManager::linkLayer(uint32_t layerId, uint32_t layerToLink) {
+ if (layerId == UNASSIGNED_LAYER_ID) {
+ return UNASSIGNED_LAYER_ID;
}
-}
-
-void LayerLifecycleManager::unlinkLayer(uint32_t& inOutLayerId, uint32_t linkedLayer) {
- uint32_t layerId = inOutLayerId;
- inOutLayerId = UNASSIGNED_LAYER_ID;
std::vector<uint32_t>* linkedLayers = getLinkedLayersFromId(layerId);
if (!linkedLayers) {
- return;
+ ALOGV("Could not find layer id %d to link %d. Parent is probably destroyed", layerId,
+ layerToLink);
+ return UNASSIGNED_LAYER_ID;
+ }
+ linkedLayers->emplace_back(layerToLink);
+ return layerId;
+}
+
+uint32_t LayerLifecycleManager::unlinkLayer(uint32_t layerId, uint32_t linkedLayer) {
+ std::vector<uint32_t>* linkedLayers = getLinkedLayersFromId(layerId);
+ if (!linkedLayers) {
+ return UNASSIGNED_LAYER_ID;
}
swapErase(*linkedLayers, linkedLayer);
+ return UNASSIGNED_LAYER_ID;
}
std::string LayerLifecycleManager::References::getDebugString() const {
@@ -314,4 +316,16 @@
return debugInfo;
}
+void LayerLifecycleManager::fixRelativeZLoop(uint32_t relativeRootId) {
+ auto it = mIdToLayer.find(relativeRootId);
+ if (it == mIdToLayer.end()) {
+ return;
+ }
+ RequestedLayerState& layer = it->second.owner;
+ layer.relativeParentId = unlinkLayer(layer.relativeParentId, layer.id);
+ layer.changes |=
+ RequestedLayerState::Changes::Hierarchy | RequestedLayerState::Changes::RelativeParent;
+ mGlobalChanges |= RequestedLayerState::Changes::Hierarchy;
+}
+
} // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h
index ad70d3f..63a7afc 100644
--- a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h
+++ b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h
@@ -42,6 +42,12 @@
void applyTransactions(const std::vector<TransactionState>&);
void onHandlesDestroyed(const std::vector<uint32_t>&);
+ // Detaches the layer from its relative parent to prevent a loop in the
+ // layer hierarchy. This overrides the RequestedLayerState and leaves
+ // the system in an invalid state. This is always a client error that
+ // needs to be fixed but overriding the state allows us to fail gracefully.
+ void fixRelativeZLoop(uint32_t relativeRootId);
+
// Destroys RequestedLayerStates that are marked to be destroyed. Invokes all
// ILifecycleListener callbacks and clears any change flags from previous state
// updates. This function should be called outside the hot path since it's not
@@ -72,8 +78,8 @@
RequestedLayerState* getLayerFromId(uint32_t);
std::vector<uint32_t>* getLinkedLayersFromId(uint32_t);
- void linkLayer(uint32_t layerId, uint32_t layerToLink);
- void unlinkLayer(uint32_t& inOutLayerId, uint32_t linkedLayer);
+ uint32_t linkLayer(uint32_t layerId, uint32_t layerToLink);
+ uint32_t unlinkLayer(uint32_t layerId, uint32_t linkedLayer);
struct References {
// Lifetime tied to mLayers
diff --git a/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp b/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp
index 45058d9..e2a4ed1 100644
--- a/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp
+++ b/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp
@@ -40,7 +40,7 @@
}
std::string layerIdToString(uint32_t layerId) {
- return layerId == UNASSIGNED_LAYER_ID ? std::to_string(layerId) : "none";
+ return layerId == UNASSIGNED_LAYER_ID ? "none" : std::to_string(layerId);
}
} // namespace
@@ -147,13 +147,17 @@
static const mat4 identityMatrix = mat4();
hasColorTransform = colorTransform != identityMatrix;
}
- if (clientState.what & layer_state_t::eLayerChanged) {
+ if (clientState.what & (layer_state_t::eLayerChanged | layer_state_t::eRelativeLayerChanged)) {
changes |= RequestedLayerState::Changes::Z;
}
if (clientState.what & layer_state_t::eReparent) {
changes |= RequestedLayerState::Changes::Parent;
parentId = getLayerIdFromSurfaceControl(clientState.parentSurfaceControlForChild);
parentSurfaceControlForChild = nullptr;
+ // Once a layer has be reparented, it cannot be placed at the root. It sounds odd
+ // but thats the existing logic and until we make this behavior more explicit, we need
+ // to maintain this logic.
+ canBeRoot = false;
}
if (clientState.what & layer_state_t::eRelativeLayerChanged) {
changes |= RequestedLayerState::Changes::RelativeParent;
@@ -254,7 +258,7 @@
",relativeParent=" + layerIdToString(relativeParentId) +
",isRelativeOf=" + std::to_string(isRelativeOf) +
",mirrorId=" + layerIdToString(mirrorId) +
- ",handleAlive=" + std::to_string(handleAlive);
+ ",handleAlive=" + std::to_string(handleAlive) + ",z=" + std::to_string(z);
}
std::string RequestedLayerState::getDebugStringShort() const {
@@ -355,4 +359,13 @@
return Region(win).subtract(exclude).getBounds();
}
+// Returns true if the layer has a relative parent that is not its own parent. This is an input
+// error from the client, and this check allows us to handle it gracefully. If both parentId and
+// relativeParentId is unassigned then the layer does not have a valid relative parent.
+// If the relative parentid is unassigned, the layer will be considered relative but won't be
+// reachable.
+bool RequestedLayerState::hasValidRelativeParent() const {
+ return isRelativeOf && parentId != relativeParentId;
+}
+
} // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/RequestedLayerState.h b/services/surfaceflinger/FrontEnd/RequestedLayerState.h
index 0ddf5e2..6891fbc 100644
--- a/services/surfaceflinger/FrontEnd/RequestedLayerState.h
+++ b/services/surfaceflinger/FrontEnd/RequestedLayerState.h
@@ -62,13 +62,14 @@
std::string getDebugString() const;
std::string getDebugStringShort() const;
aidl::android::hardware::graphics::composer3::Composition getCompositionType() const;
+ bool hasValidRelativeParent() const;
// Layer serial number. This gives layers an explicit ordering, so we
// have a stable sort order when their layer stack and Z-order are
// the same.
const uint32_t id;
const std::string name;
- const bool canBeRoot = false;
+ bool canBeRoot = false;
const uint32_t layerCreationFlags;
const uint32_t textureName;
// The owner of the layer. If created from a non system process, it will be the calling uid.
diff --git a/services/surfaceflinger/tests/unittests/Android.bp b/services/surfaceflinger/tests/unittests/Android.bp
index 26c0d8e..914c5f9 100644
--- a/services/surfaceflinger/tests/unittests/Android.bp
+++ b/services/surfaceflinger/tests/unittests/Android.bp
@@ -92,6 +92,7 @@
"LayerHistoryTest.cpp",
"LayerInfoTest.cpp",
"LayerMetadataTest.cpp",
+ "LayerHierarchyTest.cpp",
"LayerLifecycleManagerTest.cpp",
"LayerTest.cpp",
"LayerTestUtils.cpp",
diff --git a/services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp b/services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp
new file mode 100644
index 0000000..8560902
--- /dev/null
+++ b/services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp
@@ -0,0 +1,728 @@
+/*
+ * Copyright 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include "FrontEnd/LayerHandle.h"
+#include "FrontEnd/LayerHierarchy.h"
+#include "FrontEnd/LayerLifecycleManager.h"
+#include "Layer.h"
+#include "gui/SurfaceComposerClient.h"
+
+#define UPDATE_AND_VERIFY(HIERARCHY) \
+ ({ \
+ SCOPED_TRACE(""); \
+ updateAndVerify((HIERARCHY)); \
+ })
+
+namespace android::surfaceflinger::frontend {
+
+namespace {
+LayerCreationArgs createArgs(uint32_t id, bool canBeRoot, wp<IBinder> parent, wp<IBinder> mirror) {
+ LayerCreationArgs args(nullptr, nullptr, "testlayer", 0, {}, std::make_optional(id));
+ args.addToRoot = canBeRoot;
+ args.parentHandle = parent;
+ args.mirrorLayerHandle = mirror;
+ return args;
+}
+} // namespace
+
+// To run test:
+/**
+ mp :libsurfaceflinger_unittest && adb sync; adb shell \
+ /data/nativetest/libsurfaceflinger_unittest/libsurfaceflinger_unittest \
+ --gtest_filter="LayerHierarchyTest.*" --gtest_repeat=100 \
+ --gtest_shuffle \
+ --gtest_brief=1
+*/
+
+class LayerHierarchyTest : public testing::Test {
+protected:
+ LayerHierarchyTest() {
+ // tree with 3 levels of children
+ // ROOT
+ // ├── 1
+ // │ ├── 11
+ // │ │ └── 111
+ // │ ├── 12
+ // │ │ ├── 121
+ // │ │ └── 122
+ // │ │ └── 1221
+ // │ └── 13
+ // └── 2
+
+ createRootLayer(1);
+ createRootLayer(2);
+ createLayer(11, 1);
+ createLayer(12, 1);
+ createLayer(13, 1);
+ createLayer(111, 11);
+ createLayer(121, 12);
+ createLayer(122, 12);
+ createLayer(1221, 122);
+ mLifecycleManager.commitChanges();
+ }
+ std::vector<uint32_t> getTraversalPath(const LayerHierarchy& hierarchy) const {
+ std::vector<uint32_t> layerIds;
+ hierarchy.traverse([&layerIds = layerIds](const LayerHierarchy& hierarchy,
+ const LayerHierarchy::TraversalPath&) -> bool {
+ layerIds.emplace_back(hierarchy.getLayer()->id);
+ return true;
+ });
+ return layerIds;
+ }
+
+ std::vector<uint32_t> getTraversalPathInZOrder(const LayerHierarchy& hierarchy) const {
+ std::vector<uint32_t> layerIds;
+ hierarchy.traverseInZOrder(
+ [&layerIds = layerIds](const LayerHierarchy& hierarchy,
+ const LayerHierarchy::TraversalPath&) -> bool {
+ layerIds.emplace_back(hierarchy.getLayer()->id);
+ return true;
+ });
+ return layerIds;
+ }
+
+ void createRootLayer(uint32_t id) {
+ sp<LayerHandle> handle = sp<LayerHandle>::make(id);
+ mHandles[id] = handle;
+ std::vector<std::unique_ptr<RequestedLayerState>> layers;
+ layers.emplace_back(std::make_unique<RequestedLayerState>(
+ createArgs(/*id=*/id, /*canBeRoot=*/true, /*parent=*/nullptr, /*mirror=*/nullptr)));
+ mLifecycleManager.addLayers(std::move(layers));
+ }
+
+ void createLayer(uint32_t id, uint32_t parentId) {
+ sp<LayerHandle> handle = sp<LayerHandle>::make(id);
+ mHandles[id] = handle;
+ std::vector<std::unique_ptr<RequestedLayerState>> layers;
+ layers.emplace_back(std::make_unique<RequestedLayerState>(
+ createArgs(/*id=*/id, /*canBeRoot=*/false, /*parent=*/mHandles[parentId],
+ /*mirror=*/nullptr)));
+ mLifecycleManager.addLayers(std::move(layers));
+ }
+
+ void reparentLayer(uint32_t id, uint32_t newParentId) {
+ std::vector<TransactionState> transactions;
+ transactions.emplace_back();
+ transactions.back().states.push_back({});
+
+ if (newParentId == UNASSIGNED_LAYER_ID) {
+ transactions.back().states.front().state.parentSurfaceControlForChild = nullptr;
+ } else {
+ auto parentHandle = mHandles[newParentId];
+ transactions.back().states.front().state.parentSurfaceControlForChild =
+ sp<SurfaceControl>::make(SurfaceComposerClient::getDefault(), parentHandle,
+ static_cast<int32_t>(newParentId), "Test");
+ }
+ transactions.back().states.front().state.what = layer_state_t::eReparent;
+ transactions.back().states.front().state.surface = mHandles[id];
+ mLifecycleManager.applyTransactions(transactions);
+ }
+
+ void reparentRelativeLayer(uint32_t id, uint32_t relativeParentId) {
+ std::vector<TransactionState> transactions;
+ transactions.emplace_back();
+ transactions.back().states.push_back({});
+
+ if (relativeParentId == UNASSIGNED_LAYER_ID) {
+ transactions.back().states.front().state.what = layer_state_t::eLayerChanged;
+ } else {
+ auto parentHandle = mHandles[relativeParentId];
+ transactions.back().states.front().state.relativeLayerSurfaceControl =
+ sp<SurfaceControl>::make(SurfaceComposerClient::getDefault(), parentHandle,
+ static_cast<int32_t>(relativeParentId), "test");
+ transactions.back().states.front().state.what = layer_state_t::eRelativeLayerChanged;
+ }
+ transactions.back().states.front().state.surface = mHandles[id];
+ mLifecycleManager.applyTransactions(transactions);
+ }
+
+ void mirrorLayer(uint32_t id, uint32_t parent, uint32_t layerToMirror) {
+ auto parentHandle = (parent == UNASSIGNED_LAYER_ID) ? nullptr : mHandles[parent];
+ auto mirrorHandle =
+ (layerToMirror == UNASSIGNED_LAYER_ID) ? nullptr : mHandles[layerToMirror];
+
+ sp<LayerHandle> handle = sp<LayerHandle>::make(id);
+ mHandles[id] = handle;
+ std::vector<std::unique_ptr<RequestedLayerState>> layers;
+ layers.emplace_back(std::make_unique<RequestedLayerState>(
+ createArgs(/*id=*/id, /*canBeRoot=*/false, /*parent=*/parentHandle,
+ /*mirror=*/mHandles[layerToMirror])));
+ mLifecycleManager.addLayers(std::move(layers));
+ }
+
+ void updateBackgroundColor(uint32_t id, half alpha) {
+ std::vector<TransactionState> transactions;
+ transactions.emplace_back();
+ transactions.back().states.push_back({});
+ transactions.back().states.front().state.what = layer_state_t::eBackgroundColorChanged;
+ transactions.back().states.front().state.bgColorAlpha = alpha;
+ transactions.back().states.front().state.surface = mHandles[id];
+ mLifecycleManager.applyTransactions(transactions);
+ }
+
+ void destroyLayerHandle(uint32_t id) { mLifecycleManager.onHandlesDestroyed({id}); }
+
+ void updateAndVerify(LayerHierarchyBuilder& hierarchyBuilder) {
+ if (mLifecycleManager.getGlobalChanges().test(RequestedLayerState::Changes::Hierarchy)) {
+ hierarchyBuilder.update(mLifecycleManager.getLayers(),
+ mLifecycleManager.getDestroyedLayers());
+ }
+ mLifecycleManager.commitChanges();
+
+ // rebuild layer hierarchy from scratch and verify that it matches the updated state.
+ LayerHierarchyBuilder newBuilder(mLifecycleManager.getLayers());
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()),
+ getTraversalPath(newBuilder.getHierarchy()));
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()),
+ getTraversalPathInZOrder(newBuilder.getHierarchy()));
+ EXPECT_FALSE(
+ mLifecycleManager.getGlobalChanges().test(RequestedLayerState::Changes::Hierarchy));
+ }
+
+ void setZ(uint32_t id, int32_t z) {
+ std::vector<TransactionState> transactions;
+ transactions.emplace_back();
+ transactions.back().states.push_back({});
+
+ transactions.back().states.front().state.what = layer_state_t::eLayerChanged;
+ transactions.back().states.front().state.layerId = static_cast<int32_t>(id);
+ transactions.back().states.front().state.z = z;
+ mLifecycleManager.applyTransactions(transactions);
+ }
+ LayerLifecycleManager mLifecycleManager;
+ std::unordered_map<uint32_t, sp<LayerHandle>> mHandles;
+};
+
+// reparenting tests
+TEST_F(LayerHierarchyTest, addLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+ createRootLayer(3);
+ createLayer(112, 11);
+ createLayer(12211, 1221);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+ expectedTraversalPath = {1, 11, 111, 112, 12, 121, 122, 1221, 12211, 13, 2, 3};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentLayer(2, 11);
+ reparentLayer(111, 12);
+ reparentLayer(1221, 1);
+ reparentLayer(1221, 13);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 2, 12, 111, 121, 122, 13, 1221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentLayerToNull) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ reparentLayer(2, UNASSIGNED_LAYER_ID);
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ reparentLayer(1221, 13);
+ reparentLayer(1221, UNASSIGNED_LAYER_ID);
+
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 13};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {2, 11, 111, 1221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentLayerToNullAndDestroyHandles) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentLayer(2, UNASSIGNED_LAYER_ID);
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ reparentLayer(1221, UNASSIGNED_LAYER_ID);
+
+ destroyLayerHandle(2);
+ destroyLayerHandle(11);
+ destroyLayerHandle(1221);
+
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 13};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, destroyHandleThenDestroyParentLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ destroyLayerHandle(111);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ // handle is destroyed but layer is kept alive and reachable by parent
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+ // destroy parent layer and the child gets destroyed
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ destroyLayerHandle(11);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, layerSurvivesTemporaryReparentToNull) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ reparentLayer(11, 1);
+
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// offscreen tests
+TEST_F(LayerHierarchyTest, layerMovesOnscreen) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ reparentLayer(11, 1);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, addLayerToOffscreenParent) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ createLayer(112, 11);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {11, 111, 112};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// rel-z tests
+TEST_F(LayerHierarchyTest, setRelativeParent) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2, 11, 111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2, 11, 111};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentFromRelativeParentWithSetLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ reparentRelativeLayer(11, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentToRelativeParent) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ reparentLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2, 11, 111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, setParentAsRelativeParent) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ reparentRelativeLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2, 11, 111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, relativeChildMovesOffscreenIsNotTraversable) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(11, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ reparentLayer(2, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 12, 121, 122, 1221, 13};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {2, 11, 111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// mirror tests
+TEST_F(LayerHierarchyTest, canTraverseMirrorLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122,
+ 1221, 13, 14, 11, 111, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, canMirrorOffscreenLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ reparentLayer(11, UNASSIGNED_LAYER_ID);
+ mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 14, 11, 111, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {11, 111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, newChildLayerIsUpdatedInMirrorHierarchy) {
+ mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+ mLifecycleManager.commitChanges();
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ createLayer(1111, 111);
+ createLayer(112, 11);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 1111, 112, 12, 121, 122,
+ 1221, 13, 14, 11, 111, 1111, 112, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// mirror & relatives tests
+TEST_F(LayerHierarchyTest, mirrorWithRelativeOutsideMirrorHierarchy) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(111, 12);
+ mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+
+ // ROOT
+ // ├── 1
+ // │ ├── 11
+ // │ │ └── 111
+ // │ ├── 12
+ // │ │ ├── 121
+ // │ │ ├── 122
+ // │ │ │ └── 1221
+ // │ │ └ - 111 (relative)
+ // │ ├── 13
+ // │ └── 14
+ // │ └ * 11 (mirroring)
+ // └── 2
+
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 111, 121, 122,
+ 1221, 13, 14, 11, 111, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ // 111 is not reachable in the mirror
+ expectedTraversalPath = {1, 11, 12, 111, 121, 122, 1221, 13, 14, 11, 2};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, mirrorWithRelativeInsideMirrorHierarchy) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(1221, 12);
+ mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 12);
+
+ // ROOT
+ // ├── 1
+ // │ ├── 11
+ // │ │ └── 111
+ // │ ├── 12
+ // │ │ ├── 121
+ // │ │ ├── 122
+ // │ │ │ └── 1221
+ // │ │ └ - 1221 (relative)
+ // │ ├── 13
+ // │ └── 14
+ // │ └ * 12 (mirroring)
+ // └── 2
+
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 1221,
+ 13, 14, 12, 121, 122, 1221, 1221, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ // relative layer 1221 is traversable in the mirrored hierarchy as well
+ expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 14, 12, 121, 122, 1221, 2};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, childMovesOffscreenWhenRelativeParentDies) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ reparentRelativeLayer(11, 2);
+ reparentLayer(2, UNASSIGNED_LAYER_ID);
+ destroyLayerHandle(2);
+
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 12, 121, 122, 1221, 13};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {11, 111};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+ // remove relative parent so layer becomes onscreen again
+ reparentRelativeLayer(11, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, offscreenLayerCannotBeRelativeToOnscreenLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentRelativeLayer(1221, 2);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ // verify relz path
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2, 1221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 11, 111, 12, 121, 122, 13, 2, 1221};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+ // offscreen layer cannot be reached as a relative child
+ reparentLayer(12, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ expectedTraversalPath = {1, 11, 111, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {12, 121, 122, 1221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+ // layer when onscreen can be reached as a relative child again
+ reparentLayer(12, 1);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2, 1221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 11, 111, 12, 121, 122, 13, 2, 1221};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, backgroundLayersAreBehindParentLayer) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ updateBackgroundColor(1, 0.5);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 1222, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1222, 1, 11, 111, 12, 121, 122, 1221, 13, 2};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// cycle tests
+TEST_F(LayerHierarchyTest, ParentBecomesTheChild) {
+ // remove default hierarchy
+ mLifecycleManager = LayerLifecycleManager();
+ createRootLayer(1);
+ createLayer(11, 1);
+ reparentLayer(1, 11);
+ mLifecycleManager.commitChanges();
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ std::vector<uint32_t> expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, RelativeLoops) {
+ // remove default hierarchy
+ mLifecycleManager = LayerLifecycleManager();
+ createRootLayer(1);
+ createRootLayer(2);
+ createLayer(11, 1);
+ reparentRelativeLayer(11, 2);
+ reparentRelativeLayer(2, 11);
+ mLifecycleManager.commitChanges();
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ // fix loop
+ uint32_t invalidRelativeRoot;
+ bool hasRelZLoop = hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot);
+ EXPECT_TRUE(hasRelZLoop);
+ mLifecycleManager.fixRelativeZLoop(invalidRelativeRoot);
+ hierarchyBuilder.update(mLifecycleManager.getLayers(), mLifecycleManager.getDestroyedLayers());
+ EXPECT_EQ(invalidRelativeRoot, 11u);
+ EXPECT_FALSE(hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot));
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 2, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {11, 2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, IndirectRelativeLoops) {
+ // remove default hierarchy
+ mLifecycleManager = LayerLifecycleManager();
+ createRootLayer(1);
+ createRootLayer(2);
+ createLayer(11, 1);
+ createLayer(111, 11);
+ createLayer(21, 2);
+ createLayer(22, 2);
+ createLayer(221, 22);
+ reparentRelativeLayer(22, 111);
+ reparentRelativeLayer(11, 221);
+ mLifecycleManager.commitChanges();
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+ // fix loop
+ uint32_t invalidRelativeRoot;
+ bool hasRelZLoop = hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot);
+ EXPECT_TRUE(hasRelZLoop);
+ mLifecycleManager.fixRelativeZLoop(invalidRelativeRoot);
+ hierarchyBuilder.update(mLifecycleManager.getLayers(), mLifecycleManager.getDestroyedLayers());
+ EXPECT_FALSE(hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot));
+
+ std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 22, 221, 2, 21, 22, 221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 2, 21};
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {11, 111, 22, 221};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, ReparentRootLayerToNull) {
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ reparentLayer(1, UNASSIGNED_LAYER_ID);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {2};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, AddRemoveLayerInSameTransaction) {
+ // remove default hierarchy
+ mLifecycleManager = LayerLifecycleManager();
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ createRootLayer(1);
+ destroyLayerHandle(1);
+ UPDATE_AND_VERIFY(hierarchyBuilder);
+
+ std::vector<uint32_t> expectedTraversalPath = {};
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+ EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// traversal path test
+TEST_F(LayerHierarchyTest, traversalPathId) {
+ setZ(122, -1);
+ LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+ auto checkTraversalPathIdVisitor =
+ [](const LayerHierarchy& hierarchy,
+ const LayerHierarchy::TraversalPath& traversalPath) -> bool {
+ EXPECT_EQ(hierarchy.getLayer()->id, traversalPath.id);
+ return true;
+ };
+ hierarchyBuilder.getHierarchy().traverse(checkTraversalPathIdVisitor);
+ hierarchyBuilder.getHierarchy().traverseInZOrder(checkTraversalPathIdVisitor);
+}
+
+} // namespace android::surfaceflinger::frontend