services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp

/*
 * 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