SurfaceFlinger and libgui: Support for child layers.

Add support for parenting Layers in a tree. Layers
follow scene-graph style rules, that is to say:
   1. A child is cropped to the final bounds of the parent.
   2. A child inherits the parent's transform (including position)
   3. A child's Z ordering is relative to the parent and bounded between
      the parents siblings.
   4. A childs lifetime is bounded by it's parents lifetime.

Test: New tests in Transaction_test plus manual testing with later branches.
Change-Id: I96f8ad863665b9a70b6f845561344c297b7e6eff
diff --git a/include/gui/ISurfaceComposerClient.h b/include/gui/ISurfaceComposerClient.h
index 4a4efb6..0a4d35d 100644
--- a/include/gui/ISurfaceComposerClient.h
+++ b/include/gui/ISurfaceComposerClient.h
@@ -60,6 +60,7 @@
     virtual status_t createSurface(
             const String8& name, uint32_t w, uint32_t h,
             PixelFormat format, uint32_t flags,
+            const sp<IBinder>& parent,
             sp<IBinder>* handle,
             sp<IGraphicBufferProducer>* gbp) = 0;
 
diff --git a/include/gui/SurfaceComposerClient.h b/include/gui/SurfaceComposerClient.h
index 4356a58..789dc7c 100644
--- a/include/gui/SurfaceComposerClient.h
+++ b/include/gui/SurfaceComposerClient.h
@@ -105,7 +105,8 @@
             uint32_t w,         // width in pixel
             uint32_t h,         // height in pixel
             PixelFormat format, // pixel-format desired
-            uint32_t flags = 0  // usage flags
+            uint32_t flags = 0,  // usage flags
+            SurfaceControl* parent = nullptr // parent
     );
 
     //! Create a virtual display
diff --git a/libs/gui/ISurfaceComposerClient.cpp b/libs/gui/ISurfaceComposerClient.cpp
index 47cb047..b2036dc 100644
--- a/libs/gui/ISurfaceComposerClient.cpp
+++ b/libs/gui/ISurfaceComposerClient.cpp
@@ -56,7 +56,7 @@
 
     virtual status_t createSurface(const String8& name, uint32_t width,
             uint32_t height, PixelFormat format, uint32_t flags,
-            sp<IBinder>* handle,
+            const sp<IBinder>& parent, sp<IBinder>* handle,
             sp<IGraphicBufferProducer>* gbp) {
         Parcel data, reply;
         data.writeInterfaceToken(ISurfaceComposerClient::getInterfaceDescriptor());
@@ -65,6 +65,9 @@
         data.writeUint32(height);
         data.writeInt32(static_cast<int32_t>(format));
         data.writeUint32(flags);
+        if (parent != nullptr) {
+            data.writeStrongBinder(parent);
+        }
         remote()->transact(CREATE_SURFACE, data, &reply);
         *handle = reply.readStrongBinder();
         *gbp = interface_cast<IGraphicBufferProducer>(reply.readStrongBinder());
@@ -145,10 +148,14 @@
             uint32_t height = data.readUint32();
             PixelFormat format = static_cast<PixelFormat>(data.readInt32());
             uint32_t createFlags = data.readUint32();
+            sp<IBinder> parent = nullptr;
+            if (data.dataAvail() > 0) {
+                parent = data.readStrongBinder();
+            }
             sp<IBinder> handle;
             sp<IGraphicBufferProducer> gbp;
             status_t result = createSurface(name, width, height, format,
-                    createFlags, &handle, &gbp);
+                    createFlags, parent, &handle, &gbp);
             reply->writeStrongBinder(handle);
             reply->writeStrongBinder(IInterface::asBinder(gbp));
             reply->writeInt32(result);
diff --git a/libs/gui/SurfaceComposerClient.cpp b/libs/gui/SurfaceComposerClient.cpp
index 540dbd9..c2be6eb 100644
--- a/libs/gui/SurfaceComposerClient.cpp
+++ b/libs/gui/SurfaceComposerClient.cpp
@@ -610,13 +610,19 @@
         uint32_t w,
         uint32_t h,
         PixelFormat format,
-        uint32_t flags)
+        uint32_t flags,
+        SurfaceControl* parent)
 {
     sp<SurfaceControl> sur;
     if (mStatus == NO_ERROR) {
         sp<IBinder> handle;
+        sp<IBinder> parentHandle;
         sp<IGraphicBufferProducer> gbp;
-        status_t err = mClient->createSurface(name, w, h, format, flags,
+
+        if (parent != nullptr) {
+            parentHandle = parent->getHandle();
+        }
+        status_t err = mClient->createSurface(name, w, h, format, flags, parentHandle,
                 &handle, &gbp);
         ALOGE_IF(err, "SurfaceComposerClient::createSurface error %s", strerror(-err));
         if (err == NO_ERROR) {
diff --git a/services/surfaceflinger/Client.cpp b/services/surfaceflinger/Client.cpp
index e14a59b..7e04fda 100644
--- a/services/surfaceflinger/Client.cpp
+++ b/services/surfaceflinger/Client.cpp
@@ -106,14 +106,22 @@
 status_t Client::createSurface(
         const String8& name,
         uint32_t w, uint32_t h, PixelFormat format, uint32_t flags,
+        const sp<IBinder>& parentHandle,
         sp<IBinder>* handle,
         sp<IGraphicBufferProducer>* gbp)
 {
+    sp<Layer> parent = nullptr;
+    if (parentHandle != nullptr) {
+        parent = getLayerUser(parentHandle);
+        if (parent == nullptr) {
+            return NAME_NOT_FOUND;
+        }
+    }
+
     /*
      * createSurface must be called from the GL thread so that it can
      * have access to the GL context.
      */
-
     class MessageCreateLayer : public MessageBase {
         SurfaceFlinger* flinger;
         Client* client;
@@ -124,26 +132,29 @@
         uint32_t w, h;
         PixelFormat format;
         uint32_t flags;
+        sp<Layer>* parent;
     public:
         MessageCreateLayer(SurfaceFlinger* flinger,
                 const String8& name, Client* client,
                 uint32_t w, uint32_t h, PixelFormat format, uint32_t flags,
                 sp<IBinder>* handle,
-                sp<IGraphicBufferProducer>* gbp)
+                sp<IGraphicBufferProducer>* gbp,
+                sp<Layer>* parent)
             : flinger(flinger), client(client),
               handle(handle), gbp(gbp), result(NO_ERROR),
-              name(name), w(w), h(h), format(format), flags(flags) {
+              name(name), w(w), h(h), format(format), flags(flags),
+              parent(parent) {
         }
         status_t getResult() const { return result; }
         virtual bool handler() {
             result = flinger->createLayer(name, client, w, h, format, flags,
-                    handle, gbp);
+                    handle, gbp, parent);
             return true;
         }
     };
 
     sp<MessageBase> msg = new MessageCreateLayer(mFlinger.get(),
-            name, this, w, h, format, flags, handle, gbp);
+            name, this, w, h, format, flags, handle, gbp, &parent);
     mFlinger->postMessageSync(msg);
     return static_cast<MessageCreateLayer*>( msg.get() )->getResult();
 }
diff --git a/services/surfaceflinger/Client.h b/services/surfaceflinger/Client.h
index 9c7d050..2a9825c 100644
--- a/services/surfaceflinger/Client.h
+++ b/services/surfaceflinger/Client.h
@@ -55,6 +55,7 @@
     virtual status_t createSurface(
             const String8& name,
             uint32_t w, uint32_t h,PixelFormat format, uint32_t flags,
+            const sp<IBinder>& parent,
             sp<IBinder>* handle,
             sp<IGraphicBufferProducer>* gbp);
 
diff --git a/services/surfaceflinger/Layer.cpp b/services/surfaceflinger/Layer.cpp
index 5b61c25..6fd9cd7 100644
--- a/services/surfaceflinger/Layer.cpp
+++ b/services/surfaceflinger/Layer.cpp
@@ -280,6 +280,9 @@
 // it's removed from the drawing state list)
 void Layer::onRemoved() {
     mSurfaceFlingerConsumer->abandon();
+    for (const auto& child : mCurrentChildren) {
+        child->onRemoved();
+    }
 }
 
 // ---------------------------------------------------------------------------
@@ -362,6 +365,40 @@
     return Region(win).subtract(exclude).getBounds();
 }
 
+Rect Layer::computeScreenBounds(bool reduceTransparentRegion) const {
+    const Layer::State& s(getDrawingState());
+    Rect win(s.active.w, s.active.h);
+
+    if (!s.crop.isEmpty()) {
+        win.intersect(s.crop, &win);
+    }
+
+    Transform t = getTransform();
+    win = t.transform(win);
+
+    const sp<Layer>& p = getParent();
+    // Now we need to calculate the parent bounds, so we can clip ourselves to those.
+    // When calculating the parent bounds for purposes of clipping,
+    // we don't need to constrain the parent to its transparent region.
+    // The transparent region is an optimization based on the
+    // buffer contents of the layer, but does not affect the space allocated to
+    // it by policy, and thus children should be allowed to extend into the
+    // parent's transparent region. In fact one of the main uses, is to reduce
+    // buffer allocation size in cases where a child window sits behind a main window
+    // (by marking the hole in the parent window as a transparent region)
+    if (p != nullptr) {
+        Rect bounds = p->computeScreenBounds(false);
+        bounds.intersect(win, &win);
+    }
+
+    if (reduceTransparentRegion) {
+        auto const screenTransparentRegion = t.transform(s.activeTransparentRegion);
+        win = reduce(win, screenTransparentRegion);
+    }
+
+    return win;
+}
+
 Rect Layer::computeBounds() const {
     const Layer::State& s(getDrawingState());
     return computeBounds(s.activeTransparentRegion);
@@ -374,15 +411,25 @@
     if (!s.crop.isEmpty()) {
         win.intersect(s.crop, &win);
     }
+
+    Rect bounds = win;
+    const auto& p = getParent();
+    if (p != nullptr) {
+        bounds = p->computeScreenBounds();
+    }
+
+    Transform t = getTransform();
+    if (p != nullptr) {
+        win = t.transform(win);
+        win.intersect(bounds, &win);
+        win = t.inverse().transform(win);
+    }
+
     // subtract the transparent region and snap to the bounds
     return reduce(win, activeTransparentRegion);
 }
 
-gfx::FloatRect Layer::computeCrop(const sp<const DisplayDevice>& hw) const {
-    // the content crop is the area of the content that gets scaled to the
-    // layer's size.
-    gfx::FloatRect crop = getContentCrop().toFloatRect();
-
+Rect Layer::computeInitialCrop(const sp<const DisplayDevice>& hw) const {
     // the crop is the area of the window that gets cropped, but not
     // scaled in any ways.
     const State& s(getDrawingState());
@@ -399,7 +446,8 @@
         activeCrop = s.crop;
     }
 
-    activeCrop = s.active.transform.transform(activeCrop);
+    Transform t = getTransform();
+    activeCrop = t.transform(activeCrop);
     if (!activeCrop.intersect(hw->getViewport(), &activeCrop)) {
         activeCrop.clear();
     }
@@ -408,7 +456,27 @@
             activeCrop.clear();
         }
     }
-    activeCrop = s.active.transform.inverse().transform(activeCrop);
+    return activeCrop;
+}
+
+gfx::FloatRect Layer::computeCrop(const sp<const DisplayDevice>& hw) const {
+    // the content crop is the area of the content that gets scaled to the
+    // layer's size. This is in buffer space.
+    gfx::FloatRect crop = getContentCrop().toFloatRect();
+
+    // In addition there is a WM-specified crop we pull from our drawing state.
+    const State& s(getDrawingState());
+
+    // Screen space to make reduction to parent crop clearer.
+    Rect activeCrop = computeInitialCrop(hw);
+    const auto& p = getParent();
+    if (p != nullptr) {
+        auto parentCrop = p->computeInitialCrop(hw);
+        activeCrop.intersect(parentCrop, &activeCrop);
+    }
+    Transform t = getTransform();
+    // Back to layer space to work with the content crop.
+    activeCrop = t.inverse().transform(activeCrop);
 
     // This needs to be here as transform.transform(Rect) computes the
     // transformed rect and then takes the bounding box of the result before
@@ -535,9 +603,10 @@
     // apply the layer's transform, followed by the display's global transform
     // here we're guaranteed that the layer's transform preserves rects
     Region activeTransparentRegion(s.activeTransparentRegion);
+    Transform t = getTransform();
     if (!s.crop.isEmpty()) {
         Rect activeCrop(s.crop);
-        activeCrop = s.active.transform.transform(activeCrop);
+        activeCrop = t.transform(activeCrop);
 #ifdef USE_HWC2
         if(!activeCrop.intersect(displayDevice->getViewport(), &activeCrop)) {
 #else
@@ -545,7 +614,7 @@
 #endif
             activeCrop.clear();
         }
-        activeCrop = s.active.transform.inverse().transform(activeCrop, true);
+        activeCrop = t.inverse().transform(activeCrop, true);
         // This needs to be here as transform.transform(Rect) computes the
         // transformed rect and then takes the bounding box of the result before
         // returning. This means
@@ -564,7 +633,8 @@
         activeTransparentRegion.orSelf(Rect(activeCrop.right, activeCrop.top,
                 s.active.w, activeCrop.bottom));
     }
-    Rect frame(s.active.transform.transform(computeBounds(activeTransparentRegion)));
+
+    Rect frame(t.transform(computeBounds(activeTransparentRegion)));
     if (!s.finalCrop.isEmpty()) {
         if(!frame.intersect(s.finalCrop, &frame)) {
             frame.clear();
@@ -625,7 +695,7 @@
      */
 
     const Transform bufferOrientation(mCurrentTransform);
-    Transform transform(tr * s.active.transform * bufferOrientation);
+    Transform transform(tr * t * bufferOrientation);
 
     if (mSurfaceFlingerConsumer->getTransformToDisplayInverse()) {
         /*
@@ -811,7 +881,7 @@
     }
     // Subtract the transparent region and snap to the bounds
     Rect bounds = reduce(win, s.activeTransparentRegion);
-    Rect frame(s.active.transform.transform(bounds));
+    Rect frame(getTransform().transform(bounds));
     frame.intersect(displayDevice->getViewport(), &frame);
     if (!s.finalCrop.isEmpty()) {
         frame.intersect(s.finalCrop, &frame);
@@ -860,7 +930,7 @@
     }
     // subtract the transparent region and snap to the bounds
     Rect bounds = reduce(win, s.activeTransparentRegion);
-    Rect frame(s.active.transform.transform(bounds));
+    Rect frame(getTransform().transform(bounds));
     frame.intersect(hw->getViewport(), &frame);
     if (!s.finalCrop.isEmpty()) {
         frame.intersect(s.finalCrop, &frame);
@@ -903,15 +973,14 @@
 
         // figure out if there is something below us
         Region under;
-        const LayerVector& drawingLayers(
-                mFlinger->mDrawingState.layersSortedByZ);
-        const size_t count = drawingLayers.size();
-        for (size_t i=0 ; i<count ; ++i) {
-            const sp<Layer>& layer(drawingLayers[i]);
-            if (layer.get() == static_cast<Layer const*>(this))
-                break;
+        bool finished = false;
+        mFlinger->mDrawingState.layersSortedByZ.traverseInZOrder([&](Layer* layer) {
+            if (finished || layer == static_cast<Layer const*>(this)) {
+                finished = true;
+                return;
+            }
             under.orSelf( hw->getTransform().transform(layer->visibleRegion) );
-        }
+        });
         // if not everything below us is covered, we plug the holes!
         Region holes(clip.subtract(under));
         if (!holes.isEmpty()) {
@@ -1023,12 +1092,13 @@
      */
     Rect win(computeBounds());
 
+    Transform t = getTransform();
     if (!s.finalCrop.isEmpty()) {
-        win = s.active.transform.transform(win);
+        win = t.transform(win);
         if (!win.intersect(s.finalCrop, &win)) {
             win.clear();
         }
-        win = s.active.transform.inverse().transform(win);
+        win = t.inverse().transform(win);
         if (!win.intersect(computeBounds(), &win)) {
             win.clear();
         }
@@ -1228,25 +1298,21 @@
         bool useIdentityTransform) const
 {
     const Layer::State& s(getDrawingState());
-    const Transform tr(hw->getTransform());
+    const Transform hwTransform(hw->getTransform());
     const uint32_t hw_h = hw->getHeight();
-    Rect win(s.active.w, s.active.h);
-    if (!s.crop.isEmpty()) {
-        win.intersect(s.crop, &win);
-    }
-    // subtract the transparent region and snap to the bounds
-    win = reduce(win, s.activeTransparentRegion);
+    Rect win = computeBounds();
 
     vec2 lt = vec2(win.left, win.top);
     vec2 lb = vec2(win.left, win.bottom);
     vec2 rb = vec2(win.right, win.bottom);
     vec2 rt = vec2(win.right, win.top);
 
+    Transform layerTransform = getTransform();
     if (!useIdentityTransform) {
-        lt = s.active.transform.transform(lt);
-        lb = s.active.transform.transform(lb);
-        rb = s.active.transform.transform(rb);
-        rt = s.active.transform.transform(rt);
+        lt = layerTransform.transform(lt);
+        lb = layerTransform.transform(lb);
+        rb = layerTransform.transform(rb);
+        rt = layerTransform.transform(rt);
     }
 
     if (!s.finalCrop.isEmpty()) {
@@ -1257,10 +1323,10 @@
     }
 
     Mesh::VertexArray<vec2> position(mesh.getPositionArray<vec2>());
-    position[0] = tr.transform(lt);
-    position[1] = tr.transform(lb);
-    position[2] = tr.transform(rb);
-    position[3] = tr.transform(rt);
+    position[0] = hwTransform.transform(lt);
+    position[1] = hwTransform.transform(lb);
+    position[2] = hwTransform.transform(rb);
+    position[3] = hwTransform.transform(rt);
     for (size_t i=0 ; i<4 ; i++) {
         position[i].y = hw_h - position[i].y;
     }
@@ -1542,11 +1608,7 @@
     // that transactions for layers depending on this layer's frames becoming
     // visible are not blocked
     if (c.flags & layer_state_t::eLayerHidden) {
-        Mutex::Autolock lock(mLocalSyncPointMutex);
-        for (auto& point : mLocalSyncPoints) {
-            point->setFrameAvailable();
-        }
-        mLocalSyncPoints.clear();
+        clearSyncPoints();
     }
 
     // Commit the transaction
@@ -1585,6 +1647,18 @@
     return true;
 }
 
+bool Layer::setChildLayer(const sp<Layer>& childLayer, int32_t z) {
+    ssize_t idx = mCurrentChildren.indexOf(childLayer);
+    if (idx < 0) {
+        return false;
+    }
+    if (childLayer->setLayer(z)) {
+        mCurrentChildren.removeAt(idx);
+        mCurrentChildren.add(childLayer);
+    }
+    return true;
+}
+
 bool Layer::setLayer(int32_t z) {
     if (mCurrentState.z == z)
         return false;
@@ -1594,6 +1668,7 @@
     setTransactionFlags(eTransactionNeeded);
     return true;
 }
+
 bool Layer::setSize(uint32_t w, uint32_t h) {
     if (mCurrentState.requested.w == w && mCurrentState.requested.h == h)
         return false;
@@ -1699,6 +1774,14 @@
     return true;
 }
 
+uint32_t Layer::getLayerStack() const {
+    auto p = getParent();
+    if (p == nullptr) {
+        return getDrawingState().layerStack;
+    }
+    return p->getLayerStack();
+}
+
 void Layer::deferTransactionUntil(const sp<IBinder>& handle,
         uint64_t frameNumber) {
     mCurrentState.handle = handle;
@@ -1827,13 +1910,22 @@
 }
 #endif
 
+bool Layer::isHiddenByPolicy() const {
+    const Layer::State& s(mDrawingState);
+    const auto& parent = getParent();
+    if (parent != nullptr && parent->isHiddenByPolicy()) {
+        return true;
+    }
+    return s.flags & layer_state_t::eLayerHidden;
+}
+
 bool Layer::isVisible() const {
     const Layer::State& s(mDrawingState);
 #ifdef USE_HWC2
-    return !(s.flags & layer_state_t::eLayerHidden) && s.alpha > 0.0f
+    return !(isHiddenByPolicy()) && s.alpha > 0.0f
             && (mActiveBuffer != NULL || mSidebandStream != NULL);
 #else
-    return !(s.flags & layer_state_t::eLayerHidden) && s.alpha
+    return !(isHiddenByPolicy()) && s.alpha
             && (mActiveBuffer != NULL || mSidebandStream != NULL);
 #endif
 }
@@ -1878,7 +1970,7 @@
         recomputeVisibleRegions = true;
 
         const State& s(getDrawingState());
-        return s.active.transform.transform(Region(Rect(s.active.w, s.active.h)));
+        return getTransform().transform(Region(Rect(s.active.w, s.active.h)));
     }
 
     Region outDirtyRegion;
@@ -2067,7 +2159,7 @@
     Region dirtyRegion(Rect(s.active.w, s.active.h));
 
     // transform the dirty region to window-manager space
-    outDirtyRegion = (s.active.transform.transform(dirtyRegion));
+    outDirtyRegion = (getTransform().transform(dirtyRegion));
 
     return outDirtyRegion;
 }
@@ -2130,7 +2222,9 @@
             "alpha=0x%02x, flags=0x%08x, tr=[%.2f, %.2f][%.2f, %.2f]\n"
 #endif
             "      client=%p\n",
-            s.layerStack, s.z, s.active.transform.tx(), s.active.transform.ty(), s.active.w, s.active.h,
+            getLayerStack(), s.z,
+            s.active.transform.tx(), s.active.transform.ty(),
+            s.active.w, s.active.h,
             s.crop.left, s.crop.top,
             s.crop.right, s.crop.bottom,
             s.finalCrop.left, s.finalCrop.top,
@@ -2263,6 +2357,90 @@
     return mSurfaceFlingerConsumer->getTransformToDisplayInverse();
 }
 
+void Layer::addChild(const sp<Layer>& layer) {
+    mCurrentChildren.add(layer);
+    layer->setParent(this);
+}
+
+ssize_t Layer::removeChild(const sp<Layer>& layer) {
+    layer->setParent(nullptr);
+    return mCurrentChildren.remove(layer);
+}
+
+void Layer::setParent(const sp<Layer>& layer) {
+    mParent = layer;
+}
+
+void Layer::clearSyncPoints() {
+    for (const auto& child : mCurrentChildren) {
+        child->clearSyncPoints();
+    }
+
+    Mutex::Autolock lock(mLocalSyncPointMutex);
+    for (auto& point : mLocalSyncPoints) {
+        point->setFrameAvailable();
+    }
+    mLocalSyncPoints.clear();
+}
+
+int32_t Layer::getZ() const {
+    return mDrawingState.z;
+}
+
+/**
+ * Negatively signed children are before 'this' in Z-order.
+ */
+void Layer::traverseInZOrder(const std::function<void(Layer*)>& exec) {
+    size_t i = 0;
+    for (; i < mDrawingChildren.size(); i++) {
+        const auto& child = mDrawingChildren[i];
+        if (child->getZ() >= 0)
+            break;
+        child->traverseInZOrder(exec);
+    }
+    exec(this);
+    for (; i < mDrawingChildren.size(); i++) {
+        const auto& child = mDrawingChildren[i];
+        child->traverseInZOrder(exec);
+    }
+}
+
+/**
+ * Positively signed children are before 'this' in reverse Z-order.
+ */
+void Layer::traverseInReverseZOrder(const std::function<void(Layer*)>& exec) {
+    int32_t i = 0;
+    for (i = mDrawingChildren.size()-1; i>=0; i--) {
+        const auto& child = mDrawingChildren[i];
+        if (child->getZ() < 0) {
+            break;
+        }
+        child->traverseInReverseZOrder(exec);
+    }
+    exec(this);
+    for (; i>=0; i--) {
+        const auto& child = mDrawingChildren[i];
+        child->traverseInReverseZOrder(exec);
+    }
+}
+
+Transform Layer::getTransform() const {
+    Transform t;
+    const auto& p = getParent();
+    if (p != nullptr) {
+        t = p->getTransform();
+    }
+    return t * getDrawingState().active.transform;
+}
+
+void Layer::commitChildList() {
+    for (size_t i = 0; i < mCurrentChildren.size(); i++) {
+        const auto& child = mCurrentChildren[i];
+        child->commitChildList();
+    }
+    mDrawingChildren = mCurrentChildren;
+}
+
 // ---------------------------------------------------------------------------
 
 }; // namespace android
diff --git a/services/surfaceflinger/Layer.h b/services/surfaceflinger/Layer.h
index 3959341..bf224ae 100644
--- a/services/surfaceflinger/Layer.h
+++ b/services/surfaceflinger/Layer.h
@@ -42,6 +42,7 @@
 
 #include "FrameTracker.h"
 #include "Client.h"
+#include "LayerVector.h"
 #include "MonitoredProducer.h"
 #include "SurfaceFlinger.h"
 #include "SurfaceFlingerConsumer.h"
@@ -168,6 +169,7 @@
     bool setFinalCrop(const Rect& crop);
     bool setLayerStack(uint32_t layerStack);
     bool setDataSpace(android_dataspace dataSpace);
+    uint32_t getLayerStack() const;
     void deferTransactionUntil(const sp<IBinder>& handle, uint64_t frameNumber);
     bool setOverrideScalingMode(int32_t overrideScalingMode);
 
@@ -219,6 +221,14 @@
     virtual bool isVisible() const;
 
     /*
+     * isHiddenByPolicy - true if this layer has been forced invisible.
+     * just because this is false, doesn't mean isVisible() is true.
+     * For example if this layer has no active buffer, it may not be hidden by
+     * policy, but it still can not be visible.
+     */
+    virtual bool isHiddenByPolicy() const;
+
+    /*
      * isFixedSize - true if content has a fixed size
      */
     virtual bool isFixedSize() const;
@@ -422,6 +432,26 @@
 
     bool getTransformToDisplayInverse() const;
 
+    Transform getTransform() const;
+
+    void traverseInReverseZOrder(const std::function<void(Layer*)>& exec);
+    void traverseInZOrder(const std::function<void(Layer*)>& exec);
+
+    void addChild(const sp<Layer>& layer);
+    // Returns index if removed, or negative value otherwise
+    // for symmetry with Vector::remove
+    ssize_t removeChild(const sp<Layer>& layer);
+    sp<Layer> getParent() const { return mParent.promote(); }
+    bool hasParent() const { return getParent() != nullptr; }
+
+    Rect computeScreenBounds(bool reduceTransparentRegion = true) const;
+    bool setChildLayer(const sp<Layer>& childLayer, int32_t z);
+
+    // Copy the current list of children to the drawing state. Called by
+    // SurfaceFlinger to complete a transaction.
+    void commitChildList();
+
+    int32_t getZ() const;
 protected:
     // constant
     sp<SurfaceFlinger> mFlinger;
@@ -462,7 +492,12 @@
     bool needsFiltering(const sp<const DisplayDevice>& hw) const;
 
     uint32_t getEffectiveUsage(uint32_t usage) const;
+
     gfx::FloatRect computeCrop(const sp<const DisplayDevice>& hw) const;
+    // Compute the initial crop as specified by parent layers and the SurfaceControl
+    // for this layer. Does not include buffer crop from the IGraphicBufferProducer
+    // client, as that should not affect child clipping. Returns in screen space.
+    Rect computeInitialCrop(const sp<const DisplayDevice>& hw) const;
     bool isCropped() const;
     static bool getOpacityForFormat(uint32_t format);
 
@@ -478,6 +513,8 @@
     // Loads the corresponding system property once per process
     static bool latchUnsignaledBuffers();
 
+    void setParent(const sp<Layer>& layer);
+
     // -----------------------------------------------------------------------
 
     class SyncPoint
@@ -532,6 +569,8 @@
     void popPendingState(State* stateToCommit);
     bool applyPendingStates(State* stateToCommit);
 
+    void clearSyncPoints();
+
     // Returns mCurrentScaling mode (originating from the
     // Client) or mOverrideScalingMode mode (originating from
     // the Surface Controller) if set.
@@ -662,6 +701,13 @@
 
     bool mAutoRefresh;
     bool mFreezePositionUpdates;
+
+    // Child list about to be committed/used for editing.
+    LayerVector mCurrentChildren;
+    // Child list used for rendering.
+    LayerVector mDrawingChildren;
+
+    wp<Layer> mParent;
 };
 
 // ---------------------------------------------------------------------------
diff --git a/services/surfaceflinger/LayerDim.cpp b/services/surfaceflinger/LayerDim.cpp
index 4d5b3db..daebf8a 100644
--- a/services/surfaceflinger/LayerDim.cpp
+++ b/services/surfaceflinger/LayerDim.cpp
@@ -59,7 +59,7 @@
 
 bool LayerDim::isVisible() const {
     const Layer::State& s(getDrawingState());
-    return !(s.flags & layer_state_t::eLayerHidden) && s.alpha;
+    return !isHiddenByPolicy() && s.alpha;
 }
 
 
diff --git a/services/surfaceflinger/LayerVector.cpp b/services/surfaceflinger/LayerVector.cpp
index 6ac4b14..7ba6ad3 100644
--- a/services/surfaceflinger/LayerVector.cpp
+++ b/services/surfaceflinger/LayerVector.cpp
@@ -41,15 +41,14 @@
 }
 
 void LayerVector::traverseInZOrder(const std::function<void(Layer*)>& consume) const {
-    const size_t n = size();
-    for (size_t i = 0; i < n; i++) {
-        consume((*this)[i].get());
+    for (size_t i = 0; i < size(); i++) {
+        (*this)[i]->traverseInZOrder(consume);
     }
 }
 
 void LayerVector::traverseInReverseZOrder(const std::function<void(Layer*)>& consume) const {
     for (auto i = static_cast<int64_t>(size()) - 1; i >= 0; i--) {
-        consume((*this)[i].get());
+        (*this)[i]->traverseInReverseZOrder(consume);
      }
 }
 } // namespace android
diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp
index 510a3e1..3480d83 100644
--- a/services/surfaceflinger/SurfaceFlinger.cpp
+++ b/services/surfaceflinger/SurfaceFlinger.cpp
@@ -69,6 +69,7 @@
 #include "EventControlThread.h"
 #include "EventThread.h"
 #include "Layer.h"
+#include "LayerVector.h"
 #include "LayerDim.h"
 #include "SurfaceFlinger.h"
 
@@ -133,6 +134,7 @@
         mTransactionPending(false),
         mAnimTransactionPending(false),
         mLayersRemoved(false),
+        mLayersAdded(false),
         mRepaintEverything(0),
         mRenderEngine(NULL),
         mBootTime(systemTime()),
@@ -158,7 +160,8 @@
         mHasPoweredOff(false),
         mFrameBuckets(),
         mTotalTime(0),
-        mLastSwapTime(0)
+        mLastSwapTime(0),
+        mNumLayers(0)
 {
     ALOGI("SurfaceFlinger is starting");
 
@@ -1340,8 +1343,7 @@
                         opaqueRegion);
 
                 mDrawingState.traverseInZOrder([&](Layer* layer) {
-                    const Layer::State& s(layer->getDrawingState());
-                    if (s.layerStack == displayDevice->getLayerStack()) {
+                    if (layer->getLayerStack() == displayDevice->getLayerStack()) {
                         Region drawRegion(tr.transform(
                                 layer->visibleNonTransparentRegion));
                         drawRegion.andSelf(bounds);
@@ -1409,7 +1411,7 @@
                         displayDevice->getVisibleLayersSortedByZ());
                 bool foundLayerWithoutHwc = false;
                 for (size_t i = 0; i < currentLayers.size(); i++) {
-                    auto const& layer = currentLayers[i];
+                    const auto& layer = currentLayers[i];
                     if (!layer->hasHwcLayer(hwcId)) {
                         auto hwcLayer = mHwc->createLayer(hwcId);
                         if (hwcLayer) {
@@ -1560,8 +1562,6 @@
 
 void SurfaceFlinger::handleTransactionLocked(uint32_t transactionFlags)
 {
-    const LayerVector& currentLayers(mCurrentState.layersSortedByZ);
-
     // Notify all layers of available frames
     mCurrentState.traverseInZOrder([](Layer* layer) {
         layer->notifyAvailableFrames();
@@ -1778,7 +1778,7 @@
             // NOTE: we rely on the fact that layers are sorted by
             // layerStack first (so we don't have to traverse the list
             // of displays for every layer).
-            uint32_t layerStack = layer->getDrawingState().layerStack;
+            uint32_t layerStack = layer->getLayerStack();
             if (first || currentlayerStack != layerStack) {
                 currentlayerStack = layerStack;
                 // figure out if this layerstack is mirrored
@@ -1816,9 +1816,10 @@
     /*
      * Perform our own transaction if needed
      */
-    const LayerVector& layers(mDrawingState.layersSortedByZ);
-    if (currentLayers.size() > layers.size()) {
-        // layers have been added
+
+    if (mLayersAdded) {
+        mLayersAdded = false;
+        // Layers have been added.
         mVisibleRegionsDirty = true;
     }
 
@@ -1828,15 +1829,14 @@
         mLayersRemoved = false;
         mVisibleRegionsDirty = true;
         mDrawingState.traverseInZOrder([&](Layer* layer) {
-            if (currentLayers.indexOf(layer) < 0) {
+            if (mLayersPendingRemoval.indexOf(layer) >= 0) {
                 // this layer is not visible anymore
                 // TODO: we could traverse the tree from front to back and
                 //       compute the actual visible region
                 // TODO: we could cache the transformed region
-                const Layer::State& s(layer->getDrawingState());
-                Region visibleReg = s.active.transform.transform(
-                        Region(Rect(s.active.w, s.active.h)));
-                invalidateLayerStack(s.layerStack, visibleReg);
+                Region visibleReg;
+                visibleReg.set(layer->computeScreenBounds());
+                invalidateLayerStack(layer->getLayerStack(), visibleReg);
             }
         });
     }
@@ -1864,10 +1864,10 @@
 {
     if (!mLayersPendingRemoval.isEmpty()) {
         // Notify removed layers now that they can't be drawn from
-        for (size_t i = 0; i < mLayersPendingRemoval.size(); i++) {
-            recordBufferingStats(mLayersPendingRemoval[i]->getName().string(),
-                    mLayersPendingRemoval[i]->getOccupancyHistory(true));
-            mLayersPendingRemoval[i]->onRemoved();
+        for (const auto& l : mLayersPendingRemoval) {
+            recordBufferingStats(l->getName().string(),
+                    l->getOccupancyHistory(true));
+            l->onRemoved();
         }
         mLayersPendingRemoval.clear();
     }
@@ -1877,6 +1877,9 @@
     mAnimCompositionPending = mAnimTransactionPending;
 
     mDrawingState = mCurrentState;
+    mDrawingState.traverseInZOrder([](Layer* layer) {
+        layer->commitChildList();
+    });
     mTransactionPending = false;
     mAnimTransactionPending = false;
     mTransactionCV.broadcast();
@@ -1899,7 +1902,7 @@
         const Layer::State& s(layer->getDrawingState());
 
         // only consider the layers on the given layer stack
-        if (s.layerStack != layerStack)
+        if (layer->getLayerStack() != layerStack)
             return;
 
         /*
@@ -1935,12 +1938,12 @@
         // handle hidden surfaces by setting the visible region to empty
         if (CC_LIKELY(layer->isVisible())) {
             const bool translucent = !layer->isOpaque(s);
-            Rect bounds(s.active.transform.transform(layer->computeBounds()));
+            Rect bounds(layer->computeScreenBounds());
             visibleRegion.set(bounds);
+            Transform tr = layer->getTransform();
             if (!visibleRegion.isEmpty()) {
                 // Remove the transparent area from the visible region
                 if (translucent) {
-                    const Transform tr(s.active.transform);
                     if (tr.preserveRects()) {
                         // transform the transparent region
                         transparentRegion = tr.transform(s.activeTransparentRegion);
@@ -1952,7 +1955,7 @@
                 }
 
                 // compute the opaque region
-                const int32_t layerOrientation = s.active.transform.getOrientation();
+                const int32_t layerOrientation = tr.getOrientation();
                 if (s.alpha == 1.0f && !translucent &&
                         ((layerOrientation & Transform::ROT_INVALID) == false)) {
                     // the opaque region is the layer's footprint
@@ -2058,8 +2061,7 @@
     for (auto& layer : mLayersWithQueuedFrames) {
         const Region dirty(layer->latchBuffer(visibleRegions, latchTime));
         layer->useSurfaceDamage();
-        const Layer::State& s(layer->getDrawingState());
-        invalidateLayerStack(s.layerStack, dirty);
+        invalidateLayerStack(layer->getLayerStack(), dirty);
     }
 
     mVisibleRegionsDirty |= visibleRegions;
@@ -2281,16 +2283,23 @@
 status_t SurfaceFlinger::addClientLayer(const sp<Client>& client,
         const sp<IBinder>& handle,
         const sp<IGraphicBufferProducer>& gbc,
-        const sp<Layer>& lbc)
+        const sp<Layer>& lbc,
+        const sp<Layer>& parent)
 {
     // add this layer to the current state list
     {
         Mutex::Autolock _l(mStateLock);
-        if (mCurrentState.layersSortedByZ.size() >= MAX_LAYERS) {
+        if (mNumLayers >= MAX_LAYERS) {
             return NO_MEMORY;
         }
-        mCurrentState.layersSortedByZ.add(lbc);
+        if (parent == nullptr) {
+            mCurrentState.layersSortedByZ.add(lbc);
+        } else {
+            parent->addChild(lbc);
+        }
         mGraphicBufferProducerList.add(IInterface::asBinder(gbc));
+        mLayersAdded = true;
+        mNumLayers++;
     }
 
     // attach this layer to the client
@@ -2307,14 +2316,22 @@
         return NO_ERROR;
     }
 
-    ssize_t index = mCurrentState.layersSortedByZ.remove(layer);
-    if (index >= 0) {
-        mLayersPendingRemoval.push(layer);
-        mLayersRemoved = true;
-        setTransactionFlags(eTransactionNeeded);
-        return NO_ERROR;
+    const auto& p = layer->getParent();
+    const ssize_t index = (p != nullptr) ? p->removeChild(layer) :
+        mCurrentState.layersSortedByZ.remove(layer);
+
+    if (index < 0) {
+        ALOGE("Failed to find layer (%s) in layer parent (%s).",
+                layer->getName().string(),
+                (p != nullptr) ? p->getName().string() : "no-parent");
+        return BAD_VALUE;
     }
-    return status_t(index);
+
+    mLayersPendingRemoval.add(layer);
+    mLayersRemoved = true;
+    mNumLayers--;
+    setTransactionFlags(eTransactionNeeded);
+    return NO_ERROR;
 }
 
 uint32_t SurfaceFlinger::peekTransactionFlags() {
@@ -2489,13 +2506,20 @@
         }
         if (what & layer_state_t::eLayerChanged) {
             // NOTE: index needs to be calculated before we update the state
-            ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
-            if (layer->setLayer(s.z) && idx >= 0) {
-                mCurrentState.layersSortedByZ.removeAt(idx);
-                mCurrentState.layersSortedByZ.add(layer);
-                // we need traversal (state changed)
-                // AND transaction (list changed)
-                flags |= eTransactionNeeded|eTraversalNeeded;
+            const auto& p = layer->getParent();
+            if (p == nullptr) {
+                ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
+                if (layer->setLayer(s.z) && idx >= 0) {
+                    mCurrentState.layersSortedByZ.removeAt(idx);
+                    mCurrentState.layersSortedByZ.add(layer);
+                    // we need traversal (state changed)
+                    // AND transaction (list changed)
+                    flags |= eTransactionNeeded|eTraversalNeeded;
+                }
+            } else {
+                if (p->setChildLayer(layer, s.z)) {
+                    flags |= eTransactionNeeded|eTraversalNeeded;
+                }
             }
         }
         if (what & layer_state_t::eSizeChanged) {
@@ -2528,9 +2552,17 @@
                 flags |= eTraversalNeeded;
         }
         if (what & layer_state_t::eLayerStackChanged) {
-            // NOTE: index needs to be calculated before we update the state
             ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
-            if (layer->setLayerStack(s.layerStack) && idx >= 0) {
+            // We only allow setting layer stacks for top level layers,
+            // everything else inherits layer stack from its parent.
+            if (layer->hasParent()) {
+                ALOGE("Attempt to set layer stack on layer with parent (%s) is invalid",
+                        layer->getName().string());
+            } else if (idx < 0) {
+                ALOGE("Attempt to set layer stack on layer without parent (%s) that "
+                        "that also does not appear in the top level layer list. Something"
+                        " has gone wrong.", layer->getName().string());
+            } else if (layer->setLayerStack(s.layerStack)) {
                 mCurrentState.layersSortedByZ.removeAt(idx);
                 mCurrentState.layersSortedByZ.add(layer);
                 // we need traversal (state changed)
@@ -2556,7 +2588,8 @@
         const String8& name,
         const sp<Client>& client,
         uint32_t w, uint32_t h, PixelFormat format, uint32_t flags,
-        sp<IBinder>* handle, sp<IGraphicBufferProducer>* gbp)
+        sp<IBinder>* handle, sp<IGraphicBufferProducer>* gbp,
+        sp<Layer>* parent)
 {
     if (int32_t(w|h) < 0) {
         ALOGE("createLayer() failed, w or h is negative (w=%d, h=%d)",
@@ -2588,7 +2621,7 @@
         return result;
     }
 
-    result = addClientLayer(client, *handle, *gbp, layer);
+    result = addClientLayer(client, *handle, *gbp, layer, *parent);
     if (result != NO_ERROR) {
         return result;
     }
@@ -3085,10 +3118,8 @@
     /*
      * Dump the visible layer list
      */
-    const LayerVector& currentLayers = mCurrentState.layersSortedByZ;
-    const size_t count = currentLayers.size();
     colorizer.bold(result);
-    result.appendFormat("Visible layers (count = %zu)\n", count);
+    result.appendFormat("Visible layers (count = %zu)\n", mNumLayers);
     colorizer.reset(result);
     mCurrentState.traverseInZOrder([&](Layer* layer) {
         layer->dump(result, colorizer);
@@ -3170,10 +3201,9 @@
 
         result.appendFormat("Display %d HWC layers:\n", hwcId);
         Layer::miniDumpHeader(result);
-        for (size_t l = 0; l < count; l++) {
-            const sp<Layer>& layer(currentLayers[l]);
+        mCurrentState.traverseInZOrder([&](Layer* layer) {
             layer->miniDump(result, hwcId);
-        }
+        });
         result.append("\n");
     }
 
@@ -3698,18 +3728,25 @@
     // redraw the screen entirely...
     engine.clearWithColor(0, 0, 0, 1);
 
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
-        const Layer::State& state(layer->getDrawingState());
-        if (state.layerStack == hw->getLayerStack()) {
-            if (state.z >= minLayerZ && state.z <= maxLayerZ) {
-                if (layer->isVisible()) {
-                    if (filtering) layer->setFiltering(true);
-                    layer->draw(hw, useIdentityTransform);
-                    if (filtering) layer->setFiltering(false);
-                }
-            }
+    // We loop through the first level of layers without traversing,
+    // as we need to interpret min/max layer Z in the top level Z space.
+    for (const auto& layer : mDrawingState.layersSortedByZ) {
+        if (layer->getLayerStack() != hw->getLayerStack()) {
+            continue;
         }
-    });
+        const Layer::State& state(layer->getDrawingState());
+        if (state.z < minLayerZ || state.z > maxLayerZ) {
+            continue;
+        }
+        layer->traverseInZOrder([&](Layer* layer) {
+            if (!layer->isVisible()) {
+                return;
+            }
+            if (filtering) layer->setFiltering(true);
+            layer->draw(hw, useIdentityTransform);
+            if (filtering) layer->setFiltering(false);
+        });
+    }
 
     hw->setViewportAndProjection();
 }
@@ -3743,14 +3780,17 @@
     reqHeight = (!reqHeight) ? hw_h : reqHeight;
 
     bool secureLayerIsVisible = false;
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
+    for (const auto& layer : mDrawingState.layersSortedByZ) {
         const Layer::State& state(layer->getDrawingState());
-        if (state.layerStack == hw->getLayerStack() && state.z >= minLayerZ &&
-                state.z <= maxLayerZ && layer->isVisible() &&
-                layer->isSecure()) {
-            secureLayerIsVisible = true;
+        if ((layer->getLayerStack() != hw->getLayerStack()) ||
+                (state.z < minLayerZ || state.z > maxLayerZ)) {
+            continue;
         }
-    });
+        layer->traverseInZOrder([&](Layer *layer) {
+            secureLayerIsVisible = secureLayerIsVisible || (layer->isVisible() &&
+                    layer->isSecure());
+        });
+    }
 
     if (!isLocalScreenshot && secureLayerIsVisible) {
         ALOGW("FB is protected: PERMISSION_DENIED");
@@ -3888,18 +3928,21 @@
         ALOGE("*** we just took a black screenshot ***\n"
                 "requested minz=%d, maxz=%d, layerStack=%d",
                 minLayerZ, maxLayerZ, hw->getLayerStack());
+
         size_t i = 0;
-        mDrawingState.traverseInZOrder([&](Layer* layer) {
+        for (const auto& layer : mDrawingState.layersSortedByZ) {
             const Layer::State& state(layer->getDrawingState());
-            const bool visible = (state.layerStack == hw->getLayerStack())
-                                && (state.z >= minLayerZ && state.z <= maxLayerZ)
-                                && (layer->isVisible());
-            ALOGE("%c index=%zu, name=%s, layerStack=%d, z=%d, visible=%d, flags=%x, alpha=%.3f",
-                    visible ? '+' : '-',
-                    i, layer->getName().string(), state.layerStack, state.z,
+            if (layer->getLayerStack() == hw->getLayerStack() && state.z >= minLayerZ &&
+                    state.z <= maxLayerZ) {
+                layer->traverseInZOrder([&](Layer* layer) {
+                    ALOGE("%c index=%zu, name=%s, layerStack=%d, z=%d, visible=%d, flags=%x, alpha=%.3f",
+                            layer->isVisible() ? '+' : '-',
+                            i, layer->getName().string(), layer->getLayerStack(), state.z,
                             layer->isVisible(), state.flags, state.alpha);
-            i++;
-        });
+                    i++;
+                });
+            }
+        }
     }
 }
 
diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h
index d573f1a..4f3ee74 100644
--- a/services/surfaceflinger/SurfaceFlinger.h
+++ b/services/surfaceflinger/SurfaceFlinger.h
@@ -293,7 +293,8 @@
      */
     status_t createLayer(const String8& name, const sp<Client>& client,
             uint32_t w, uint32_t h, PixelFormat format, uint32_t flags,
-            sp<IBinder>* handle, sp<IGraphicBufferProducer>* gbp);
+            sp<IBinder>* handle, sp<IGraphicBufferProducer>* gbp,
+            sp<Layer>* parent);
 
     status_t createNormalLayer(const sp<Client>& client, const String8& name,
             uint32_t w, uint32_t h, uint32_t flags, PixelFormat& format,
@@ -320,7 +321,8 @@
     status_t addClientLayer(const sp<Client>& client,
             const sp<IBinder>& handle,
             const sp<IGraphicBufferProducer>& gbc,
-            const sp<Layer>& lbc);
+            const sp<Layer>& lbc,
+            const sp<Layer>& parent);
 
     /* ------------------------------------------------------------------------
      * Boot animation, on/off animations and screen capture
@@ -423,6 +425,7 @@
      void enableHardwareVsync();
      void resyncToHardwareVsync(bool makeAvailable);
      void disableHardwareVsync(bool makeUnavailable);
+
 public:
      void resyncWithRateLimit();
 private:
@@ -464,11 +467,12 @@
     Condition mTransactionCV;
     bool mTransactionPending;
     bool mAnimTransactionPending;
-    Vector< sp<Layer> > mLayersPendingRemoval;
+    SortedVector< sp<Layer> > mLayersPendingRemoval;
     SortedVector< wp<IBinder> > mGraphicBufferProducerList;
 
     // protected by mStateLock (but we could use another lock)
     bool mLayersRemoved;
+    bool mLayersAdded;
 
     // access must be protected by mInvalidateLock
     volatile int32_t mRepaintEverything;
@@ -565,6 +569,8 @@
     nsecs_t mTotalTime;
     std::atomic<nsecs_t> mLastSwapTime;
 
+    size_t mNumLayers;
+
     // Double- vs. triple-buffering stats
     struct BufferingStats {
         BufferingStats()
diff --git a/services/surfaceflinger/SurfaceFlinger_hwc1.cpp b/services/surfaceflinger/SurfaceFlinger_hwc1.cpp
index 5bfc10b..1976d2e 100644
--- a/services/surfaceflinger/SurfaceFlinger_hwc1.cpp
+++ b/services/surfaceflinger/SurfaceFlinger_hwc1.cpp
@@ -72,6 +72,7 @@
 #include "EventControlThread.h"
 #include "EventThread.h"
 #include "Layer.h"
+#include "LayerVector.h"
 #include "LayerDim.h"
 #include "SurfaceFlinger.h"
 
@@ -136,6 +137,7 @@
         mTransactionPending(false),
         mAnimTransactionPending(false),
         mLayersRemoved(false),
+        mLayersAdded(false),
         mRepaintEverything(0),
         mRenderEngine(NULL),
         mBootTime(systemTime()),
@@ -161,7 +163,8 @@
         mHasPoweredOff(false),
         mFrameBuckets(),
         mTotalTime(0),
-        mLastSwapTime(0)
+        mLastSwapTime(0),
+        mNumLayers(0)
 {
     ALOGI("SurfaceFlinger is starting");
 
@@ -1236,8 +1239,7 @@
                         opaqueRegion);
 
                 mDrawingState.traverseInZOrder([&](Layer* layer) {
-                    const Layer::State& s(layer->getDrawingState());
-                    if (s.layerStack == hw->getLayerStack()) {
+                    if (layer->getLayerStack() == hw->getLayerStack()) {
                         Region drawRegion(tr.transform(
                                 layer->visibleNonTransparentRegion));
                         drawRegion.andSelf(bounds);
@@ -1468,8 +1470,6 @@
 
 void SurfaceFlinger::handleTransactionLocked(uint32_t transactionFlags)
 {
-    const LayerVector& currentLayers(mCurrentState.layersSortedByZ);
-
     // Notify all layers of available frames
     mCurrentState.traverseInZOrder([](Layer* layer) {
         layer->notifyAvailableFrames();
@@ -1680,7 +1680,7 @@
             // NOTE: we rely on the fact that layers are sorted by
             // layerStack first (so we don't have to traverse the list
             // of displays for every layer).
-            uint32_t layerStack = layer->getDrawingState().layerStack;
+            uint32_t layerStack = layer->getLayerStack();
             if (first || currentlayerStack != layerStack) {
                 currentlayerStack = layerStack;
                 // figure out if this layerstack is mirrored
@@ -1718,9 +1718,10 @@
     /*
      * Perform our own transaction if needed
      */
-    const LayerVector& layers(mDrawingState.layersSortedByZ);
-    if (currentLayers.size() > layers.size()) {
-        // layers have been added
+
+    if (mLayersAdded) {
+        mLayersAdded = false;
+        // Layers have been added.
         mVisibleRegionsDirty = true;
     }
 
@@ -1730,15 +1731,14 @@
         mLayersRemoved = false;
         mVisibleRegionsDirty = true;
         mDrawingState.traverseInZOrder([&](Layer* layer) {
-            if (currentLayers.indexOf(layer) < 0) {
+            if (mLayersPendingRemoval.indexOf(layer) >= 0) {
                 // this layer is not visible anymore
                 // TODO: we could traverse the tree from front to back and
                 //       compute the actual visible region
                 // TODO: we could cache the transformed region
-                const Layer::State& s(layer->getDrawingState());
-                Region visibleReg = s.active.transform.transform(
-                        Region(Rect(s.active.w, s.active.h)));
-                invalidateLayerStack(s.layerStack, visibleReg);
+                Region visibleReg;
+                visibleReg.set(layer->computeScreenBounds());
+                invalidateLayerStack(layer->getLayerStack(), visibleReg);
             }
         });
     }
@@ -1778,10 +1778,10 @@
 {
     if (!mLayersPendingRemoval.isEmpty()) {
         // Notify removed layers now that they can't be drawn from
-        for (size_t i = 0; i < mLayersPendingRemoval.size(); i++) {
-            recordBufferingStats(mLayersPendingRemoval[i]->getName().string(),
-                    mLayersPendingRemoval[i]->getOccupancyHistory(true));
-            mLayersPendingRemoval[i]->onRemoved();
+        for (const auto& l : mLayersPendingRemoval) {
+            recordBufferingStats(l->getName().string(),
+                    l->getOccupancyHistory(true));
+            l->onRemoved();
         }
         mLayersPendingRemoval.clear();
     }
@@ -1791,6 +1791,9 @@
     mAnimCompositionPending = mAnimTransactionPending;
 
     mDrawingState = mCurrentState;
+    mDrawingState.traverseInZOrder([](Layer* layer) {
+        layer->commitChildList();
+    });
     mTransactionPending = false;
     mAnimTransactionPending = false;
     mTransactionCV.broadcast();
@@ -1812,7 +1815,7 @@
         const Layer::State& s(layer->getDrawingState());
 
         // only consider the layers on the given layer stack
-        if (s.layerStack != layerStack)
+        if (layer->getLayerStack() != layerStack)
             return;
 
         /*
@@ -1848,12 +1851,12 @@
         // handle hidden surfaces by setting the visible region to empty
         if (CC_LIKELY(layer->isVisible())) {
             const bool translucent = !layer->isOpaque(s);
-            Rect bounds(s.active.transform.transform(layer->computeBounds()));
+            Rect bounds(layer->computeScreenBounds());
             visibleRegion.set(bounds);
+            Transform tr = layer->getTransform();
             if (!visibleRegion.isEmpty()) {
                 // Remove the transparent area from the visible region
                 if (translucent) {
-                    const Transform tr(s.active.transform);
                     if (tr.preserveRects()) {
                         // transform the transparent region
                         transparentRegion = tr.transform(s.activeTransparentRegion);
@@ -1865,7 +1868,7 @@
                 }
 
                 // compute the opaque region
-                const int32_t layerOrientation = s.active.transform.getOrientation();
+                const int32_t layerOrientation = tr.getOrientation();
                 if (s.alpha==255 && !translucent &&
                         ((layerOrientation & Transform::ROT_INVALID) == false)) {
                     // the opaque region is the layer's footprint
@@ -1971,8 +1974,7 @@
         Layer* layer = layersWithQueuedFrames[i];
         const Region dirty(layer->latchBuffer(visibleRegions, latchTime));
         layer->useSurfaceDamage();
-        const Layer::State& s(layer->getDrawingState());
-        invalidateLayerStack(s.layerStack, dirty);
+        invalidateLayerStack(layer->getLayerStack(), dirty);
     }
 
     mVisibleRegionsDirty |= visibleRegions;
@@ -2188,16 +2190,23 @@
 status_t SurfaceFlinger::addClientLayer(const sp<Client>& client,
         const sp<IBinder>& handle,
         const sp<IGraphicBufferProducer>& gbc,
-        const sp<Layer>& lbc)
+        const sp<Layer>& lbc,
+        const sp<Layer>& parent)
 {
     // add this layer to the current state list
     {
         Mutex::Autolock _l(mStateLock);
-        if (mCurrentState.layersSortedByZ.size() >= MAX_LAYERS) {
+        if (mNumLayers >= MAX_LAYERS) {
             return NO_MEMORY;
         }
-        mCurrentState.layersSortedByZ.add(lbc);
+        if (parent == nullptr) {
+            mCurrentState.layersSortedByZ.add(lbc);
+        } else {
+            parent->addChild(lbc);
+        }
         mGraphicBufferProducerList.add(IInterface::asBinder(gbc));
+        mLayersAdded = true;
+        mNumLayers++;
     }
 
     // attach this layer to the client
@@ -2214,14 +2223,22 @@
         return NO_ERROR;
     }
 
-    ssize_t index = mCurrentState.layersSortedByZ.remove(layer);
-    if (index >= 0) {
-        mLayersPendingRemoval.push(layer);
-        mLayersRemoved = true;
-        setTransactionFlags(eTransactionNeeded);
-        return NO_ERROR;
+    const auto& p = layer->getParent();
+    const ssize_t index = (p != nullptr) ? p->removeChild(layer) :
+             mCurrentState.layersSortedByZ.remove(layer);
+
+    if (index < 0) {
+        ALOGE("Failed to find layer (%s) in layer parent (%s).",
+                layer->getName().string(),
+                (p != nullptr) ? p->getName().string() : "no-parent");
+        return BAD_VALUE;
     }
-    return status_t(index);
+
+    mLayersPendingRemoval.add(layer);
+    mLayersRemoved = true;
+    mNumLayers--;
+    setTransactionFlags(eTransactionNeeded);
+    return NO_ERROR;
 }
 
 uint32_t SurfaceFlinger::peekTransactionFlags() {
@@ -2396,13 +2413,20 @@
         }
         if (what & layer_state_t::eLayerChanged) {
             // NOTE: index needs to be calculated before we update the state
-            ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
-            if (layer->setLayer(s.z) && idx >= 0) {
-                mCurrentState.layersSortedByZ.removeAt(idx);
-                mCurrentState.layersSortedByZ.add(layer);
-                // we need traversal (state changed)
-                // AND transaction (list changed)
-                flags |= eTransactionNeeded|eTraversalNeeded;
+            const auto& p = layer->getParent();
+            if (p == nullptr) {
+                ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
+                if (layer->setLayer(s.z) && idx >= 0) {
+                    mCurrentState.layersSortedByZ.removeAt(idx);
+                    mCurrentState.layersSortedByZ.add(layer);
+                    // we need traversal (state changed)
+                    // AND transaction (list changed)
+                    flags |= eTransactionNeeded|eTraversalNeeded;
+                }
+            } else {
+                if (p->setChildLayer(layer, s.z)) {
+                    flags |= eTransactionNeeded|eTraversalNeeded;
+                }
             }
         }
         if (what & layer_state_t::eSizeChanged) {
@@ -2435,9 +2459,17 @@
                 flags |= eTraversalNeeded;
         }
         if (what & layer_state_t::eLayerStackChanged) {
-            // NOTE: index needs to be calculated before we update the state
             ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
-            if (layer->setLayerStack(s.layerStack) && idx >= 0) {
+            // We only allow setting layer stacks for top level layers,
+            // everything else inherits layer stack from its parent.
+            if (layer->hasParent()) {
+                ALOGE("Attempt to set layer stack on layer with parent (%s) is invalid",
+                        layer->getName().string());
+            } else if (idx < 0) {
+                ALOGE("Attempt to set layer stack on layer without parent (%s) that "
+                        "that also does not appear in the top level layer list. Something"
+                        " has gone wrong.", layer->getName().string());
+            } else if (layer->setLayerStack(s.layerStack)) {
                 mCurrentState.layersSortedByZ.removeAt(idx);
                 mCurrentState.layersSortedByZ.add(layer);
                 // we need traversal (state changed)
@@ -2463,7 +2495,8 @@
         const String8& name,
         const sp<Client>& client,
         uint32_t w, uint32_t h, PixelFormat format, uint32_t flags,
-        sp<IBinder>* handle, sp<IGraphicBufferProducer>* gbp)
+        sp<IBinder>* handle, sp<IGraphicBufferProducer>* gbp,
+        sp<Layer>* parent)
 {
     if (int32_t(w|h) < 0) {
         ALOGE("createLayer() failed, w or h is negative (w=%d, h=%d)",
@@ -2495,7 +2528,7 @@
         return result;
     }
 
-    result = addClientLayer(client, *handle, *gbp, layer);
+    result = addClientLayer(client, *handle, *gbp, layer, *parent);
     if (result != NO_ERROR) {
         return result;
     }
@@ -2989,10 +3022,8 @@
     /*
      * Dump the visible layer list
      */
-    const LayerVector& currentLayers = mCurrentState.layersSortedByZ;
-    const size_t count = currentLayers.size();
     colorizer.bold(result);
-    result.appendFormat("Visible layers (count = %zu)\n", count);
+    result.appendFormat("Visible layers (count = %zu)\n", mNumLayers);
     colorizer.reset(result);
     mCurrentState.traverseInZOrder([&](Layer* layer) {
         layer->dump(result, colorizer);
@@ -3576,18 +3607,25 @@
     // redraw the screen entirely...
     engine.clearWithColor(0, 0, 0, 1);
 
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
-        const Layer::State& state(layer->getDrawingState());
-        if (state.layerStack == hw->getLayerStack()) {
-            if (state.z >= minLayerZ && state.z <= maxLayerZ) {
-                if (layer->isVisible()) {
-                    if (filtering) layer->setFiltering(true);
-                    layer->draw(hw, useIdentityTransform);
-                    if (filtering) layer->setFiltering(false);
-                }
-            }
+    // We loop through the first level of layers without traversing,
+    // as we need to interpret min/max layer Z in the top level Z space.
+    for (const auto& layer : mDrawingState.layersSortedByZ) {
+        if (layer->getLayerStack() != hw->getLayerStack()) {
+            continue;
         }
-    });
+        const Layer::State& state(layer->getDrawingState());
+        if (state.z < minLayerZ || state.z > maxLayerZ) {
+            continue;
+        }
+        layer->traverseInZOrder([&](Layer* layer) {
+            if (!layer->isVisible()) {
+                return;
+            }
+            if (filtering) layer->setFiltering(true);
+            layer->draw(hw, useIdentityTransform);
+            if (filtering) layer->setFiltering(false);
+        });
+    }
 
     // compositionComplete is needed for older driver
     hw->compositionComplete();
@@ -3623,14 +3661,17 @@
     reqHeight = (!reqHeight) ? hw_h : reqHeight;
 
     bool secureLayerIsVisible = false;
-    mDrawingState.traverseInZOrder([&](Layer* layer) {
+    for (const auto& layer : mDrawingState.layersSortedByZ) {
         const Layer::State& state(layer->getDrawingState());
-        if (state.layerStack == hw->getLayerStack() && state.z >= minLayerZ &&
-                state.z <= maxLayerZ && layer->isVisible() &&
-                layer->isSecure()) {
-            secureLayerIsVisible = true;
+        if ((layer->getLayerStack() != hw->getLayerStack()) ||
+                (state.z < minLayerZ || state.z > maxLayerZ)) {
+            continue;
         }
-    });
+        layer->traverseInZOrder([&](Layer *layer) {
+            secureLayerIsVisible = secureLayerIsVisible || (layer->isVisible() &&
+                    layer->isSecure());
+        });
+    }
 
     if (!isLocalScreenshot && secureLayerIsVisible) {
         ALOGW("FB is protected: PERMISSION_DENIED");
@@ -3761,17 +3802,19 @@
                 "requested minz=%d, maxz=%d, layerStack=%d",
                 minLayerZ, maxLayerZ, hw->getLayerStack());
         size_t i = 0;
-        mDrawingState.traverseInZOrder([&](Layer* layer) {
+        for (const auto& layer : mDrawingState.layersSortedByZ) {
             const Layer::State& state(layer->getDrawingState());
-            const bool visible = (state.layerStack == hw->getLayerStack())
-                                && (state.z >= minLayerZ && state.z <= maxLayerZ)
-                                && (layer->isVisible());
-            ALOGE("%c index=%zu, name=%s, layerStack=%d, z=%d, visible=%d, flags=%x, alpha=%x",
-                    visible ? '+' : '-',
-                            i, layer->getName().string(), state.layerStack, state.z,
+            if (layer->getLayerStack() == hw->getLayerStack() && state.z >= minLayerZ &&
+                    state.z <= maxLayerZ) {
+                layer->traverseInZOrder([&](Layer* layer) {
+                    ALOGE("%c index=%zu, name=%s, layerStack=%d, z=%d, visible=%d, flags=%x, alpha=%x",
+                            layer->isVisible() ? '+' : '-',
+                            i, layer->getName().string(), layer->getLayerStack(), state.z,
                             layer->isVisible(), state.flags, state.alpha);
-            i++;
-        });
+                    i++;
+                });
+            }
+        }
     }
 }
 
diff --git a/services/surfaceflinger/SurfaceInterceptor.cpp b/services/surfaceflinger/SurfaceInterceptor.cpp
index 60bc7f3..2d6472a 100644
--- a/services/surfaceflinger/SurfaceInterceptor.cpp
+++ b/services/surfaceflinger/SurfaceInterceptor.cpp
@@ -74,9 +74,11 @@
 
 void SurfaceInterceptor::saveExistingSurfacesLocked(const SortedVector<sp<Layer>>& layers) {
     ATRACE_CALL();
-    for (const auto& layer : layers) {
-        addSurfaceCreationLocked(createTraceIncrementLocked(), layer);
-        addInitialSurfaceStateLocked(createTraceIncrementLocked(), layer);
+    for (const auto& l : layers) {
+        l->traverseInZOrder([this](Layer* layer) {
+            addSurfaceCreationLocked(createTraceIncrementLocked(), layer);
+            addInitialSurfaceStateLocked(createTraceIncrementLocked(), layer);
+        });
     }
 }
 
diff --git a/services/surfaceflinger/tests/Android.mk b/services/surfaceflinger/tests/Android.mk
index 4f1a8e6..f93d918 100644
--- a/services/surfaceflinger/tests/Android.mk
+++ b/services/surfaceflinger/tests/Android.mk
@@ -20,6 +20,7 @@
     libprotobuf-cpp-full \
     libui \
     libutils \
+    liblog
 
 LOCAL_STATIC_LIBRARIES := libtrace_proto
 
diff --git a/services/surfaceflinger/tests/Transaction_test.cpp b/services/surfaceflinger/tests/Transaction_test.cpp
index 79cd245..d9f1438 100644
--- a/services/surfaceflinger/tests/Transaction_test.cpp
+++ b/services/surfaceflinger/tests/Transaction_test.cpp
@@ -84,6 +84,18 @@
         }
     }
 
+    void expectFGColor(uint32_t x, uint32_t y) {
+        checkPixel(x, y, 195, 63, 63);
+    }
+
+    void expectBGColor(uint32_t x, uint32_t y) {
+        checkPixel(x, y, 63, 63, 195);
+    }
+
+    void expectChildColor(uint32_t x, uint32_t y) {
+        checkPixel(x, y, 200, 200, 200);
+    }
+
 private:
     ScreenCapture(const sp<CpuConsumer>& cc) :
         mCC(cc) {
@@ -140,14 +152,14 @@
 
         mComposerClient->setDisplayLayerStack(display, 0);
 
-        ASSERT_EQ(NO_ERROR, mBGSurfaceControl->setLayer(INT_MAX-2));
+        ASSERT_EQ(NO_ERROR, mBGSurfaceControl->setLayer(INT32_MAX-2));
         ASSERT_EQ(NO_ERROR, mBGSurfaceControl->show());
 
-        ASSERT_EQ(NO_ERROR, mFGSurfaceControl->setLayer(INT_MAX-1));
+        ASSERT_EQ(NO_ERROR, mFGSurfaceControl->setLayer(INT32_MAX-1));
         ASSERT_EQ(NO_ERROR, mFGSurfaceControl->setPosition(64, 64));
         ASSERT_EQ(NO_ERROR, mFGSurfaceControl->show());
 
-        ASSERT_EQ(NO_ERROR, mSyncSurfaceControl->setLayer(INT_MAX-1));
+        ASSERT_EQ(NO_ERROR, mSyncSurfaceControl->setLayer(INT32_MAX-1));
         ASSERT_EQ(NO_ERROR, mSyncSurfaceControl->setPosition(displayWidth-2,
                 displayHeight-2));
         ASSERT_EQ(NO_ERROR, mSyncSurfaceControl->show());
@@ -517,4 +529,105 @@
     }
 }
 
+class ChildLayerTest : public LayerUpdateTest {
+protected:
+    void SetUp() override {
+        LayerUpdateTest::SetUp();
+        mChild = mComposerClient->createSurface(
+                String8("Child surface"),
+                10, 10, PIXEL_FORMAT_RGBA_8888,
+                0, mFGSurfaceControl.get());
+        fillSurfaceRGBA8(mChild, 200, 200, 200);
+
+        {
+            SCOPED_TRACE("before anything");
+            ScreenCapture::captureScreen(&mCapture);
+            mCapture->expectChildColor(64, 64);
+        }
+    }
+    void TearDown() override {
+        LayerUpdateTest::TearDown();
+        mChild = 0;
+    }
+
+    sp<SurfaceControl> mChild;
+    sp<ScreenCapture> mCapture;
+};
+
+TEST_F(ChildLayerTest, ChildLayerPositioning) {
+    SurfaceComposerClient::openGlobalTransaction();
+    mChild->show();
+    mChild->setPosition(10, 10);
+    mFGSurfaceControl->setPosition(64, 64);
+    SurfaceComposerClient::closeGlobalTransaction(true);
+
+    {
+        ScreenCapture::captureScreen(&mCapture);
+        // Top left of foreground must now be visible
+        mCapture->expectFGColor(64, 64);
+        // But 10 pixels in we should see the child surface
+        mCapture->expectChildColor(74, 74);
+        // And 10 more pixels we should be back to the foreground surface
+        mCapture->expectFGColor(84, 84);
+    }
+
+    SurfaceComposerClient::openGlobalTransaction();
+    ASSERT_EQ(NO_ERROR, mFGSurfaceControl->setPosition(0, 0));
+    SurfaceComposerClient::closeGlobalTransaction(true);
+
+    {
+        ScreenCapture::captureScreen(&mCapture);
+        // Top left of foreground should now be at 0, 0
+        mCapture->expectFGColor(0, 0);
+        // But 10 pixels in we should see the child surface
+        mCapture->expectChildColor(10, 10);
+        // And 10 more pixels we should be back to the foreground surface
+        mCapture->expectFGColor(20, 20);
+    }
+}
+
+TEST_F(ChildLayerTest, ChildLayerConstraints) {
+    SurfaceComposerClient::openGlobalTransaction();
+    mChild->show();
+    mFGSurfaceControl->setPosition(0, 0);
+    mChild->setPosition(63, 63);
+    SurfaceComposerClient::closeGlobalTransaction(true);
+
+    {
+        ScreenCapture::captureScreen(&mCapture);
+        mCapture->expectFGColor(0, 0);
+        // Last pixel in foreground should now be the child.
+        mCapture->expectChildColor(63, 63);
+        // But the child should be constrained and the next pixel
+        // must be the background
+        mCapture->expectBGColor(64, 64);
+    }
+}
+
+TEST_F(ChildLayerTest, ChildLayerScaling) {
+    SurfaceComposerClient::openGlobalTransaction();
+    mFGSurfaceControl->setPosition(0, 0);
+    SurfaceComposerClient::closeGlobalTransaction(true);
+
+    // Find the boundary between the parent and child
+    {
+        ScreenCapture::captureScreen(&mCapture);
+        mCapture->expectChildColor(9, 9);
+        mCapture->expectFGColor(10, 10);
+    }
+
+    SurfaceComposerClient::openGlobalTransaction();
+    mFGSurfaceControl->setMatrix(2.0, 0, 0, 2.0);
+    SurfaceComposerClient::closeGlobalTransaction(true);
+
+    // The boundary should be twice as far from the origin now.
+    // The pixels from the last test should all be child now
+    {
+        ScreenCapture::captureScreen(&mCapture);
+        mCapture->expectChildColor(9, 9);
+        mCapture->expectChildColor(10, 10);
+        mCapture->expectChildColor(19, 19);
+        mCapture->expectFGColor(20, 20);
+    }
+}
 }