PAGXOptimizer.cpp

/////////////////////////////////////////////////////////////////////////////////////////////////
//
//  Tencent is pleased to support the open source community by making libpag available.
//
//  Copyright (C) 2026 Tencent. All rights reserved.
//
//  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 "pagx/PAGXOptimizer.h"
#include <algorithm>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include "PAGXOptimizerOptions.h"
#include "pagx/nodes/Composition.h"
#include "pagx/nodes/Ellipse.h"
#include "pagx/nodes/Fill.h"
#include "pagx/nodes/Font.h"
#include "pagx/nodes/GlyphRun.h"
#include "pagx/nodes/Group.h"
#include "pagx/nodes/Image.h"
#include "pagx/nodes/ImagePattern.h"
#include "pagx/nodes/Layer.h"
#include "pagx/nodes/LayoutNode.h"
#include "pagx/nodes/Path.h"
#include "pagx/nodes/PathData.h"
#include "pagx/nodes/Rectangle.h"
#include "pagx/nodes/SolidColor.h"
#include "pagx/nodes/Stroke.h"
#include "pagx/nodes/Text.h"
#include "pagx/types/PathVerb.h"
#include "pagx/utils/VerifyUtils.h"

namespace pagx {

// ============================================================================
// Shared layer/element classification predicates — single source-of-truth in
// pagx/utils/VerifyUtils.h, used by verify, resolve, and optimizer. Keeping
// them in one place avoids silent drift when new Layer attributes are introduced.
// ============================================================================

namespace {

// ----------------------------------------------------------------------------
// Forward declarations for every helper defined below. Keeping them together
// here lets any function call any other regardless of definition order, so the
// bodies below can be arranged by topic instead of by topological sort.
// ----------------------------------------------------------------------------

struct PainterSignature;

bool HasUnresolvedImport(const Layer* layer);
bool LayerNeedsKeeping(const Layer* layer, const std::unordered_set<const Layer*>& maskRefs);
bool LayoutNodeHasConstraints(const LayoutNode* node);
bool ElementHasConstraints(Element* element);
bool IsDefaultTransformGroup(const Group* group);
bool IsLayerStructurallyEmpty(const Layer* layer);

void CollectMaskRefsFromLayer(const Layer* layer, std::unordered_set<const Layer*>& refs);
void CollectMaskRefs(const std::vector<Layer*>& layers, std::unordered_set<const Layer*>& refs);

Group* WrapShellLayerAsGroup(PAGXDocument* doc, Layer* layer);

bool TryReadAxisAlignedRect(const PathData* data, float& cx, float& cy, float& w, float& h);
bool TryReadEllipse(const PathData* data, float& cx, float& cy, float& w, float& h);
Element* TryCanonicalizePath(PAGXDocument* doc, Path* path);

bool TryConvertRectMaskToScrollRect(Layer* layer);
bool RectMaskToScrollRectInLayer(Layer* layer);

bool ColorSourcesEqual(const ColorSource* a, const ColorSource* b);
bool FillsEqual(const Fill* a, const Fill* b);
bool StrokesEqual(const Stroke* a, const Stroke* b);
bool PaintersEqual(const Element* a, const Element* b);
PainterSignature ComputePainterSignature(const Group* group);
bool PainterSignaturesEqual(const PainterSignature& a, const PainterSignature& b);

bool PruneEmptyInElements(std::vector<Element*>& elements);
bool PruneEmptyInGroup(Group* group);
bool PruneEmptyInLayer(Layer* layer, const std::unordered_set<const Layer*>& maskRefs);
bool PruneEmptyTopLevel(std::vector<Layer*>& layers, bool parentHasLayout,
                        const std::unordered_set<const Layer*>& maskRefs);

bool CanonicalizePathsInElements(PAGXDocument* doc, std::vector<Element*>& elements);
bool CanonicalizePathsInLayer(PAGXDocument* doc, Layer* layer);

bool DowngradeShellChildrenInLayer(PAGXDocument* doc, Layer* layer,
                                   const std::unordered_set<const Layer*>& maskRefs);
bool DowngradeShellChildren(PAGXDocument* doc, std::vector<Layer*>& layers,
                            const std::unordered_set<const Layer*>& maskRefs);

bool IsMergeableShellLayer(const Layer* layer, const std::unordered_set<const Layer*>& maskRefs);

bool ChildFillsParent(const Layer* parent, const Layer* child);
bool ChildHasNoPaintAffectingEffect(const Layer* child);
bool CanAbsorbFillingChild(const Layer* parent, const Layer* child,
                           const std::unordered_set<const Layer*>& maskRefs);
void AbsorbFillingChild(Layer* parent, Layer* child);
bool CanDropShellParent(const Layer* parent, const Layer* child,
                        const std::unordered_set<const Layer*>& maskRefs);
bool CollapseSingleChildLayersInList(std::vector<Layer*>& layers,
                                     const std::unordered_set<const Layer*>& maskRefs);
template <class T>
void BeginMutation(std::vector<T>& source, std::vector<T>& result, size_t upTo, bool& changed);
bool MergeAdjacentShellLayersInList(PAGXDocument* doc, std::vector<Layer*>& layers,
                                    bool parentHasLayout,
                                    const std::unordered_set<const Layer*>& maskRefs);
bool MergeAdjacentShellLayersRecursive(PAGXDocument* doc, std::vector<Layer*>& layers,
                                       bool parentHasLayout,
                                       const std::unordered_set<const Layer*>& maskRefs);
bool MergeAdjacentShellLayers(PAGXDocument* doc, std::vector<Layer*>& topLevel,
                              const std::unordered_set<const Layer*>& maskRefs);

bool UnwrapRedundantFirstGroupInElements(std::vector<Element*>& elements);
bool UnwrapRedundantFirstGroupRecursive(std::vector<Element*>& elements);
bool UnwrapRedundantFirstGroupInLayer(Layer* layer);

bool MergeAdjacentGroupsInElements(std::vector<Element*>& elements);
bool MergeAdjacentGroupsRecursive(std::vector<Element*>& elements);
bool MergeAdjacentGroupsInLayer(Layer* layer);

void RecomputeMaskRefs(PAGXDocument* doc, std::unordered_set<const Layer*>& refs);

std::string PathDataSignature(const PathData* data);
void RewritePathDataInElements(std::vector<Element*>& elements,
                               const std::unordered_map<PathData*, PathData*>& redirect);
void RewritePathDataInLayer(Layer* layer, const std::unordered_map<PathData*, PathData*>& redirect);
bool DedupPathDataResources(PAGXDocument* doc);

void CollectRefsFromElement(const Element* element, std::unordered_set<std::string>& refs);
void CollectRefsFromLayer(const Layer* layer, std::unordered_set<std::string>& refs);
void CollectReferencedIds(const PAGXDocument* doc, std::unordered_set<std::string>& refs);
bool IsResourceNode(NodeType type);
bool PruneUnreferencedResources(PAGXDocument* doc);

int OptimizeLayerList(PAGXDocument* doc, std::vector<Layer*>& layers,
                      std::unordered_set<const Layer*>& maskRefs,
                      const PAGXOptimizerOptions& options, bool* converged);

// ----------------------------------------------------------------------------
// Helper definitions start here.
// ----------------------------------------------------------------------------

bool HasUnresolvedImport(const Layer* layer) {
  return !layer->importDirective.source.empty() || !layer->importDirective.content.empty();
}

bool LayerNeedsKeeping(const Layer* layer, const std::unordered_set<const Layer*>& maskRefs) {
  if (maskRefs.find(layer) != maskRefs.end()) {
    return true;
  }
  return false;
}

bool LayoutNodeHasConstraints(const LayoutNode* node) {
  if (node == nullptr) {
    return false;
  }
  return node->hasConstraints();
}

bool ElementHasConstraints(Element* element) {
  return LayoutNodeHasConstraints(LayoutNode::AsLayoutNode(element));
}

// Group is a no-op container: identity transform, default alpha, no layout,
// no constraint frame, no padding.
bool IsDefaultTransformGroup(const Group* group) {
  if (group->alpha != 1.0f) {
    return false;
  }
  if (group->position.x != 0 || group->position.y != 0) {
    return false;
  }
  if (group->anchor.x != 0 || group->anchor.y != 0) {
    return false;
  }
  if (group->rotation != 0) {
    return false;
  }
  if (group->scale.x != 1 || group->scale.y != 1) {
    return false;
  }
  if (group->skew != 0) {
    return false;
  }
  if (group->skewAxis != 0) {
    return false;
  }
  if (!std::isnan(group->width) || !std::isnan(group->height)) {
    return false;
  }
  if (!std::isnan(group->percentWidth) || !std::isnan(group->percentHeight)) {
    return false;
  }
  if (!group->padding.isZero()) {
    return false;
  }
  if (!std::isnan(group->left) || !std::isnan(group->right) || !std::isnan(group->top) ||
      !std::isnan(group->bottom) || !std::isnan(group->centerX) || !std::isnan(group->centerY)) {
    return false;
  }
  return true;
}

void CollectMaskRefsFromLayer(const Layer* layer, std::unordered_set<const Layer*>& refs) {
  if (layer == nullptr) {
    return;
  }
  if (layer->mask != nullptr) {
    refs.insert(layer->mask);
    CollectMaskRefsFromLayer(layer->mask, refs);
  }
  CollectMaskRefs(layer->children, refs);
}

void CollectMaskRefs(const std::vector<Layer*>& layers, std::unordered_set<const Layer*>& refs) {
  for (auto* layer : layers) {
    CollectMaskRefsFromLayer(layer, refs);
  }
}

// ----------------------------------------------------------------------------
// Layer -> Group conversion
// ----------------------------------------------------------------------------

// Wraps a downgradable shell Layer's contents in a new Group, transferring customData. Caller
// must have verified the layer is downgradable and is responsible for removing it from the
// owning list. Returns nullptr if the layer is not safely downgradable (callers must check
// IsLayerShell + children.empty() first).
Group* WrapShellLayerAsGroup(PAGXDocument* doc, Layer* layer) {
  auto* group = doc->makeNode<Group>();
  group->elements = std::move(layer->contents);
  layer->contents.clear();
  // Transfer customData and sourceLine so verify diagnostics still point to the right place.
  group->customData = std::move(layer->customData);
  layer->customData.clear();
  if (group->sourceLine == -1) {
    group->sourceLine = layer->sourceLine;
  }
  return group;
}

// ----------------------------------------------------------------------------
// Path canonicalization (mirrors verify's DetectPathToPrimitives).
// ----------------------------------------------------------------------------

bool TryReadAxisAlignedRect(const PathData* data, float& cx, float& cy, float& w, float& h) {
  auto& verbs = data->verbs();
  // Accept two well-formed axis-aligned rectangle encodings:
  //   5 verbs: Move + 3 Line + Close       (SVG `<rect>` / importer canonical form — the Close
  //                                         implicitly draws the fourth edge back to the start).
  //   6 verbs: Move + 4 Line + Close       (SVG `<path d="M... L... L... L... L... Z">` where the
  //                                         author emitted the final edge as an explicit Line
  //                                         before closing — commonly produced by path editors).
  // Any other verb count cannot describe a pure axis-aligned rectangle.
  if (verbs.size() != 5 && verbs.size() != 6) {
    return false;
  }
  if (verbs[0] != PathVerb::Move) {
    return false;
  }
  for (size_t i = 1; i + 1 < verbs.size(); i++) {
    if (verbs[i] != PathVerb::Line) {
      return false;
    }
  }
  if (verbs.back() != PathVerb::Close) {
    return false;
  }
  auto& pts = data->points();
  size_t pointCount = pts.size();
  if (pointCount < 4) {
    return false;
  }
  for (size_t i = 0; i < pointCount; i++) {
    auto& p1 = pts[i];
    auto& p2 = pts[(i + 1) % pointCount];
    float dx = std::abs(p2.x - p1.x);
    float dy = std::abs(p2.y - p1.y);
    if (dx > 0.01f && dy > 0.01f) {
      return false;
    }
  }
  float minX = pts[0].x, maxX = pts[0].x;
  float minY = pts[0].y, maxY = pts[0].y;
  for (size_t i = 1; i < pointCount; i++) {
    minX = std::min(minX, pts[i].x);
    maxX = std::max(maxX, pts[i].x);
    minY = std::min(minY, pts[i].y);
    maxY = std::max(maxY, pts[i].y);
  }
  w = maxX - minX;
  h = maxY - minY;
  if (w < 0.01f || h < 0.01f) {
    return false;
  }
  cx = (minX + maxX) * 0.5f;
  cy = (minY + maxY) * 0.5f;
  return true;
}

bool TryReadEllipse(const PathData* data, float& cx, float& cy, float& w, float& h) {
  auto& verbs = data->verbs();
  if (verbs.size() != 6) {
    return false;
  }
  if (verbs[0] != PathVerb::Move) {
    return false;
  }
  for (int i = 1; i <= 4; i++) {
    if (verbs[i] != PathVerb::Cubic) {
      return false;
    }
  }
  if (verbs[5] != PathVerb::Close) {
    return false;
  }
  auto& pts = data->points();
  if (pts.size() < 13) {
    return false;
  }

  Point onCurve[4];
  onCurve[0] = pts[0];
  onCurve[1] = pts[3];
  onCurve[2] = pts[6];
  onCurve[3] = pts[9];

  float minX = onCurve[0].x, maxX = onCurve[0].x;
  float minY = onCurve[0].y, maxY = onCurve[0].y;
  for (int i = 1; i < 4; i++) {
    minX = std::min(minX, onCurve[i].x);
    maxX = std::max(maxX, onCurve[i].x);
    minY = std::min(minY, onCurve[i].y);
    maxY = std::max(maxY, onCurve[i].y);
  }
  cx = (minX + maxX) * 0.5f;
  cy = (minY + maxY) * 0.5f;
  float rx = (maxX - minX) * 0.5f;
  float ry = (maxY - minY) * 0.5f;
  if (rx < 0.01f || ry < 0.01f) {
    return false;
  }

  bool foundTop = false, foundBottom = false, foundLeft = false, foundRight = false;
  static constexpr float TOLERANCE = 1.0f;
  for (int i = 0; i < 4; i++) {
    float dx = std::abs(onCurve[i].x - cx);
    float dy = std::abs(onCurve[i].y - cy);
    if (dx < TOLERANCE && std::abs(dy - ry) < TOLERANCE) {
      if (onCurve[i].y < cy) {
        foundTop = true;
      } else {
        foundBottom = true;
      }
    } else if (dy < TOLERANCE && std::abs(dx - rx) < TOLERANCE) {
      if (onCurve[i].x < cx) {
        foundLeft = true;
      } else {
        foundRight = true;
      }
    }
  }
  if (!(foundTop && foundBottom && foundLeft && foundRight)) {
    return false;
  }

  // Standard cubic Bezier approximation constant for quarter-circle arcs: 4*(sqrt(2)-1)/3.
  static constexpr float KAPPA = 0.5522847f;
  // Maximum absolute pixel deviation allowed between an actual cubic control point and the ideal
  // KAPPA-derived control point when recognizing an ellipse from a 4-cubic path.
  static constexpr float CP_TOLERANCE = 2.0f;
  float expectedCpOffsetX = rx * KAPPA;
  float expectedCpOffsetY = ry * KAPPA;
  for (int seg = 0; seg < 4; seg++) {
    Point cp1 = pts[1 + seg * 3];
    Point cp2 = pts[2 + seg * 3];
    Point segStart = (seg == 0) ? pts[0] : pts[seg * 3];
    Point segEnd = pts[3 + seg * 3];
    float cp1DistX = std::abs(cp1.x - segStart.x);
    float cp1DistY = std::abs(cp1.y - segStart.y);
    float cp2DistX = std::abs(cp2.x - segEnd.x);
    float cp2DistY = std::abs(cp2.y - segEnd.y);
    bool cp1Valid =
        (cp1DistX < CP_TOLERANCE && std::abs(cp1DistY - expectedCpOffsetY) < CP_TOLERANCE) ||
        (cp1DistY < CP_TOLERANCE && std::abs(cp1DistX - expectedCpOffsetX) < CP_TOLERANCE);
    bool cp2Valid =
        (cp2DistX < CP_TOLERANCE && std::abs(cp2DistY - expectedCpOffsetY) < CP_TOLERANCE) ||
        (cp2DistY < CP_TOLERANCE && std::abs(cp2DistX - expectedCpOffsetX) < CP_TOLERANCE);
    if (!cp1Valid || !cp2Valid) {
      return false;
    }
  }
  w = rx * 2.0f;
  h = ry * 2.0f;
  return true;
}

// Replace `path` in-place with a Rectangle/Ellipse if eligible. Returns the new element to
// substitute (which may be the same path if no rewrite happened).
Element* TryCanonicalizePath(PAGXDocument* doc, Path* path) {
  if (path->data == nullptr || path->data->isEmpty()) {
    return path;
  }
  if (path->reversed) {
    return path;
  }
  if (ElementHasConstraints(path)) {
    return path;
  }
  if (!path->customData.empty()) {
    return path;
  }

  float cx = 0, cy = 0, w = 0, h = 0;
  if (TryReadAxisAlignedRect(path->data, cx, cy, w, h)) {
    auto* rect = doc->makeNode<Rectangle>();
    rect->position = {path->position.x + cx, path->position.y + cy};
    rect->size = {w, h};
    rect->sourceLine = path->sourceLine;
    return rect;
  }
  if (TryReadEllipse(path->data, cx, cy, w, h)) {
    auto* ellipse = doc->makeNode<Ellipse>();
    ellipse->position = {path->position.x + cx, path->position.y + cy};
    ellipse->size = {w, h};
    ellipse->sourceLine = path->sourceLine;
    return ellipse;
  }
  return path;
}

// ----------------------------------------------------------------------------
// Rectangular alpha mask -> scrollRect rewrite.
//
// An alpha mask whose only contents are a single axis-aligned Rectangle painted with an opaque
// Fill is exactly equivalent to clipping the parent layer with that same rectangle. We express
// the result via scrollRect (which lives in the layer's local coordinate space) rather than
// clipToBounds, because clipToBounds requires resolved layer bounds and would shift coordinates
// when the layer doesn't already declare a frame.
// ----------------------------------------------------------------------------

bool TryConvertRectMaskToScrollRect(Layer* layer) {
  if (layer->mask == nullptr) {
    return false;
  }
  if (layer->maskType != MaskType::Alpha) {
    return false;
  }
  if (layer->hasScrollRect) {
    return false;
  }
  auto* m = layer->mask;
  if (m->x != 0 || m->y != 0) {
    return false;
  }
  if (!m->matrix.isIdentity()) {
    return false;
  }
  if (!m->matrix3D.isIdentity()) {
    return false;
  }
  if (m->alpha != 1.0f) {
    return false;
  }
  if (m->blendMode != BlendMode::Normal) {
    return false;
  }
  if (!m->styles.empty() || !m->filters.empty()) {
    return false;
  }
  // `id` / `name` on the mask layer come from SVG <clipPath>'s identifier and don't carry
  // user-meaningful state — the mask layer itself stays in doc->layers (hidden) after we
  // detach the mask reference, so any other consumer can still resolve it. Only customData
  // truly blocks the rewrite.
  if (!m->customData.empty()) {
    return false;
  }
  if (m->contents.size() != 2) {
    return false;
  }
  if (m->contents[0]->nodeType() != NodeType::Rectangle) {
    return false;
  }
  if (m->contents[1]->nodeType() != NodeType::Fill) {
    return false;
  }
  auto* rect = static_cast<Rectangle*>(m->contents[0]);
  if (rect->roundness != 0) {
    return false;
  }
  if (rect->reversed) {
    return false;
  }
  if (LayoutNodeHasConstraints(rect)) {
    return false;
  }
  if (!rect->customData.empty()) {
    return false;
  }
  auto* fill = static_cast<Fill*>(m->contents[1]);
  if (fill->alpha < 0.999f) {
    return false;
  }
  if (fill->blendMode != BlendMode::Normal) {
    return false;
  }
  if (fill->color != nullptr) {
    if (fill->color->nodeType() != NodeType::SolidColor) {
      return false;
    }
    auto* sc = static_cast<const SolidColor*>(fill->color);
    if (sc->color.alpha < 0.999f) {
      return false;
    }
  }
  // tgfx's scrollRect uses (x,y) as a scroll offset (the rect's top-left maps to the layer's
  // local (0,0)). To preserve the original positioning we have to translate the layer by the
  // same (left, top) — which we can only do safely when the user layer has no rotation/scale
  // (any 2x2 distortion would warp that compensation vector), no 3D matrix, and no
  // constraint-based positioning (where x/y are inputs to the layout solver rather than the
  // final translation). A pure-translation matrix is fine: it commutes with the layer-local
  // pre-translation the scrollRect introduces, so adding (left, top) to layer.x/y produces
  // the same parent-space final transform whether the matrix translates first or not. This
  // matters after a PAGX -> SVG -> PAGX round trip, which re-imports the translation we
  // previously baked into x/y as a 2D matrix attribute.
  if (layer->matrix.a != 1.0f || layer->matrix.b != 0.0f || layer->matrix.c != 0.0f ||
      layer->matrix.d != 1.0f) {
    return false;
  }
  if (!layer->matrix3D.isIdentity()) {
    return false;
  }
  if (LayoutNodeHasConstraints(layer)) {
    return false;
  }
  // If the layer already declares an explicit frame size, leave it alone — overwriting an
  // author-supplied width/height could change layout semantics for downstream consumers.
  if (!std::isnan(layer->width) || !std::isnan(layer->height)) {
    return false;
  }
  float left = rect->position.x - rect->size.width * 0.5f;
  float top = rect->position.y - rect->size.height * 0.5f;
  layer->scrollRect = {left, top, rect->size.width, rect->size.height};
  layer->hasScrollRect = true;
  layer->x += left;
  layer->y += top;
  // The displayed area collapses to exactly the scrollRect's size after this rewrite. Pin the
  // layer's frame to those dimensions so layoutBounds() reflects the visible region instead of
  // the (much larger) un-clipped child extent — otherwise verify's child-exceeds-parent check
  // (which only suppresses on the parent's clip, not the child's) would fire false positives.
  layer->width = rect->size.width;
  layer->height = rect->size.height;
  layer->mask = nullptr;
  return true;
}

bool RectMaskToScrollRectInLayer(Layer* layer) {
  bool changed = TryConvertRectMaskToScrollRect(layer);
  for (auto* child : layer->children) {
    changed |= RectMaskToScrollRectInLayer(child);
  }
  return changed;
}

// ----------------------------------------------------------------------------
// Painter signature (used to decide whether two Groups can merge geometry).
//
// The *Equal helpers below intentionally encode the *optimizer's* notion of "safe to treat as the
// same painter when merging adjacent groups": shared resources compare by pointer identity (so two
// references to the same `<gradient id="g1"/>` collapse), inline SolidColor literals compare by
// value, and every other inline color source (gradient, ImagePattern) is treated as opaque unless
// the same pointer is reused. This is more conservative than a generic structural equality, and it
// is not reused anywhere else in the codebase — promoting these to a shared utility would push the
// conservative semantics onto unrelated call sites, so they stay file-local on purpose.
// ----------------------------------------------------------------------------

// A painter's color source can be either a shared resource (compare by pointer identity, since
// resources have meaningful IDs) or an inline literal. Two inline literals are considered equal
// only when both are SolidColor with identical Color values. Anything else (gradients, image
// patterns) is treated as opaque: only equal when the SAME pointer is used.
bool ColorSourcesEqual(const ColorSource* a, const ColorSource* b) {
  if (a == b) {
    return true;
  }
  if (a == nullptr || b == nullptr) {
    return false;
  }
  if (a->nodeType() != b->nodeType()) {
    return false;
  }
  // For shared resource references (i.e. nodes registered in PAGXDocument::nodes by id) the
  // SVG importer reuses the same instance, so a == b will already be true above. For inline
  // SolidColor literals we compare values.
  if (a->nodeType() == NodeType::SolidColor) {
    auto* sa = static_cast<const SolidColor*>(a);
    auto* sb = static_cast<const SolidColor*>(b);
    return sa->color == sb->color;
  }
  return false;
}

bool FillsEqual(const Fill* a, const Fill* b) {
  if (a->alpha != b->alpha) {
    return false;
  }
  if (a->blendMode != b->blendMode) {
    return false;
  }
  if (a->fillRule != b->fillRule) {
    return false;
  }
  if (a->placement != b->placement) {
    return false;
  }
  return ColorSourcesEqual(a->color, b->color);
}

bool StrokesEqual(const Stroke* a, const Stroke* b) {
  if (a->width != b->width) {
    return false;
  }
  if (a->alpha != b->alpha) {
    return false;
  }
  if (a->blendMode != b->blendMode) {
    return false;
  }
  if (a->cap != b->cap) {
    return false;
  }
  if (a->join != b->join) {
    return false;
  }
  if (a->miterLimit != b->miterLimit) {
    return false;
  }
  if (a->dashOffset != b->dashOffset) {
    return false;
  }
  if (a->dashAdaptive != b->dashAdaptive) {
    return false;
  }
  if (a->align != b->align) {
    return false;
  }
  if (a->placement != b->placement) {
    return false;
  }
  if (a->dashes != b->dashes) {
    return false;
  }
  return ColorSourcesEqual(a->color, b->color);
}

bool PaintersEqual(const Element* a, const Element* b) {
  if (a == b) {
    return true;
  }
  if (a == nullptr || b == nullptr) {
    return false;
  }
  if (a->nodeType() != b->nodeType()) {
    return false;
  }
  if (a->nodeType() == NodeType::Fill) {
    return FillsEqual(static_cast<const Fill*>(a), static_cast<const Fill*>(b));
  }
  if (a->nodeType() == NodeType::Stroke) {
    return StrokesEqual(static_cast<const Stroke*>(a), static_cast<const Stroke*>(b));
  }
  return false;
}

struct PainterSignature {
  // Trailing-painter elements; an empty signature means the Group has no painters
  // (so it has no shared painter scope to compare).
  std::vector<Element*> painters;
  bool valid = false;
};

PainterSignature ComputePainterSignature(const Group* group) {
  PainterSignature sig;
  bool foundPainter = false;
  for (auto* el : group->elements) {
    if (IsPainter(el->nodeType())) {
      foundPainter = true;
      sig.painters.push_back(el);
    } else if (foundPainter) {
      // A non-painter after a painter means painters don't form a clean trailing block.
      sig.valid = false;
      sig.painters.clear();
      return sig;
    }
  }
  if (!foundPainter) {
    return sig;
  }
  sig.valid = true;
  return sig;
}

bool PainterSignaturesEqual(const PainterSignature& a, const PainterSignature& b) {
  if (!a.valid || !b.valid) {
    return false;
  }
  if (a.painters.size() != b.painters.size()) {
    return false;
  }
  for (size_t i = 0; i < a.painters.size(); i++) {
    if (!PaintersEqual(a.painters[i], b.painters[i])) {
      return false;
    }
  }
  return true;
}

// ============================================================================
// Rule implementations. Each rule mutates `doc` in place and returns true if
// any change was made.
// ============================================================================

// Recursively prune empty Layers (no contents/children/composition, no constraints, not
// referenced as a mask, not a layout participant) and empty Groups.
bool PruneEmptyInElements(std::vector<Element*>& elements) {
  bool changed = false;
  size_t writeIdx = 0;
  for (size_t i = 0; i < elements.size(); i++) {
    auto* el = elements[i];
    if (el->nodeType() == NodeType::Group) {
      auto* group = static_cast<Group*>(el);
      changed |= PruneEmptyInGroup(group);
      bool empty = group->elements.empty() && std::isnan(group->width) &&
                   std::isnan(group->height) && !LayoutNodeHasConstraints(group) &&
                   group->padding.isZero() && group->customData.empty();
      if (empty) {
        changed = true;
        continue;
      }
    }
    elements[writeIdx++] = el;
  }
  if (writeIdx != elements.size()) {
    elements.resize(writeIdx);
    changed = true;
  }
  return changed;
}

bool PruneEmptyInGroup(Group* group) {
  return PruneEmptyInElements(group->elements);
}

// A Layer is "structurally empty" when it has no contents/children/composition AND no
// size/percent-size/size-dependent constraint that would still let it occupy space (e.g.
// as a backdrop-blur surface). On such a layer every other attribute — filters, styles,
// mask, alpha, blendMode, hasScrollRect, clipToBounds, id, name, etc. — applies to a
// region of zero area and produces no rendering, so dropping the layer is observably
// equivalent. This matches verify's DetectEmptyLayer rule exactly; we intentionally do
// NOT consult HasLayerOnlyFeatures here because that helper conservatively keeps layers
// that carry purely-cosmetic attributes (filter on nothing, mask on nothing, ...) and
// would let the optimizer disagree with verify after a PAGX <-> SVG round trip drops a
// shape leaving behind a shell layer.
bool IsLayerStructurallyEmpty(const Layer* layer) {
  if (!layer->contents.empty() || !layer->children.empty() || layer->composition != nullptr) {
    return false;
  }
  if (!std::isnan(layer->width) || !std::isnan(layer->height)) {
    return false;
  }
  if (!std::isnan(layer->percentWidth) || !std::isnan(layer->percentHeight)) {
    return false;
  }
  // Size-dependent constraints (right/bottom/centerX/centerY) still resolve to a finite
  // box at layout time, so the layer can render via filters / background blur. left/top
  // alone only translate, so an otherwise-empty layer with just left/top is still empty.
  if (!std::isnan(layer->right) || !std::isnan(layer->bottom) || !std::isnan(layer->centerX) ||
      !std::isnan(layer->centerY)) {
    return false;
  }
  if (!layer->customData.empty()) {
    return false;
  }
  if (HasUnresolvedImport(layer)) {
    return false;
  }
  return true;
}

bool PruneEmptyInLayer(Layer* layer, const std::unordered_set<const Layer*>& maskRefs) {
  bool changed = false;
  changed |= PruneEmptyInElements(layer->contents);
  bool layerHasLayout = layer->layout != LayoutMode::None;
  // Recurse into children first so empty subtrees collapse bottom-up.
  size_t writeIdx = 0;
  for (size_t i = 0; i < layer->children.size(); i++) {
    auto* child = layer->children[i];
    changed |= PruneEmptyInLayer(child, maskRefs);
    bool inParentLayout = layerHasLayout && child->includeInLayout;
    if (IsLayerStructurallyEmpty(child) && !inParentLayout && !LayerNeedsKeeping(child, maskRefs)) {
      changed = true;
      continue;
    }
    layer->children[writeIdx++] = child;
  }
  if (writeIdx != layer->children.size()) {
    layer->children.resize(writeIdx);
    changed = true;
  }
  return changed;
}

bool PruneEmptyTopLevel(std::vector<Layer*>& layers, bool parentHasLayout,
                        const std::unordered_set<const Layer*>& maskRefs) {
  bool changed = false;
  size_t writeIdx = 0;
  for (size_t i = 0; i < layers.size(); i++) {
    auto* layer = layers[i];
    changed |= PruneEmptyInLayer(layer, maskRefs);
    bool inParentLayout = parentHasLayout && layer->includeInLayout;
    if (IsLayerStructurallyEmpty(layer) && !inParentLayout && !LayerNeedsKeeping(layer, maskRefs)) {
      changed = true;
      continue;
    }
    layers[writeIdx++] = layer;
  }
  if (writeIdx != layers.size()) {
    layers.resize(writeIdx);
    changed = true;
  }
  return changed;
}

// ----------------------------------------------------------------------------
// Canonicalize Path nodes inside Layers/Groups.
// ----------------------------------------------------------------------------

bool CanonicalizePathsInElements(PAGXDocument* doc, std::vector<Element*>& elements) {
  bool changed = false;
  for (auto& el : elements) {
    if (el->nodeType() == NodeType::Path) {
      auto* path = static_cast<Path*>(el);
      auto* replacement = TryCanonicalizePath(doc, path);
      if (replacement != el) {
        el = replacement;
        changed = true;
      }
    } else if (el->nodeType() == NodeType::Group) {
      auto* group = static_cast<Group*>(el);
      changed |= CanonicalizePathsInElements(doc, group->elements);
    }
  }
  return changed;
}

bool CanonicalizePathsInLayer(PAGXDocument* doc, Layer* layer) {
  bool changed = false;
  changed |= CanonicalizePathsInElements(doc, layer->contents);
  // Mask subtrees carry their own Path children (e.g. SVG <clipPath> typically imports each
  // <rect> as Path data). Rewriting those Paths to Rectangle primitives is the prerequisite
  // for TryConvertRectMaskToScrollRect to recognize the mask as an axis-aligned alpha rect.
  if (layer->mask != nullptr) {
    changed |= CanonicalizePathsInLayer(doc, layer->mask);
  }
  for (auto* child : layer->children) {
    changed |= CanonicalizePathsInLayer(doc, child);
  }
  return changed;
}

// ----------------------------------------------------------------------------
// Downgrade-shell-children: when a parent Layer has no contents, no layout,
// and ALL children are shell+downgradable Layers without further children,
// rewrite each child as a Group inside the parent's contents.
// ----------------------------------------------------------------------------

bool DowngradeShellChildrenInLayer(PAGXDocument* doc, Layer* layer,
                                   const std::unordered_set<const Layer*>& maskRefs) {
  bool changed = false;
  for (auto* child : layer->children) {
    changed |= DowngradeShellChildrenInLayer(doc, child, maskRefs);
  }
  if (layer->layout != LayoutMode::None) {
    return changed;
  }
  if (layer->children.empty()) {
    return changed;
  }
  if (!layer->contents.empty()) {
    return changed;  // mixed: paint order would change
  }

  for (auto* child : layer->children) {
    if (!child->children.empty()) {
      return changed;
    }
    if (!IsLayerShell(child)) {
      return changed;
    }
    if (LayerNeedsKeeping(child, maskRefs)) {
      return changed;
    }
    if (HasUnresolvedImport(child)) {
      return changed;
    }
  }
  // All children are downgradable.
  for (auto* child : layer->children) {
    if (child->contents.empty() && child->customData.empty()) {
      // Empty shell layer with nothing to wrap — drop entirely.
      continue;
    }
    auto* group = WrapShellLayerAsGroup(doc, child);
    layer->contents.push_back(group);
  }
  layer->children.clear();
  return true;
}

bool DowngradeShellChildren(PAGXDocument* doc, std::vector<Layer*>& layers,
                            const std::unordered_set<const Layer*>& maskRefs) {
  bool changed = false;
  for (auto* layer : layers) {
    changed |= DowngradeShellChildrenInLayer(doc, layer, maskRefs);
  }
  return changed;
}

// ----------------------------------------------------------------------------
// Merge-adjacent-shell-layers: in a sibling list, runs of consecutive shell
// Layers (no children, downgradable) are replaced by a single Layer containing
// one Group per source Layer.
//
// The single Layer wrapper is necessary at the top level (and for a child run
// when there are surrounding non-downgradable siblings) so paint order is
// preserved. When the entire sibling list is downgradable inside a parent
// Layer, DowngradeShellChildren handles it earlier (no wrapper needed).
// ----------------------------------------------------------------------------

bool IsMergeableShellLayer(const Layer* layer, const std::unordered_set<const Layer*>& maskRefs) {
  if (!layer->children.empty()) {
    return false;
  }
  return IsLayerShell(layer) && !LayerNeedsKeeping(layer, maskRefs) && !HasUnresolvedImport(layer);
}

// Backfills `result` with the first `upTo` entries of `source` the first time a mutation happens.
// Used by the adjacent-shell/group mergers, whose common case is "no change to the list" — we
// want to avoid allocating a result vector until a mutation is actually detected.
template <class T>
void BeginMutation(std::vector<T>& source, std::vector<T>& result, size_t upTo, bool& changed) {
  if (changed) {
    return;
  }
  changed = true;
  result.reserve(source.size());
  result.insert(result.end(), source.begin(), source.begin() + static_cast<ptrdiff_t>(upTo));
}

bool MergeAdjacentShellLayersInList(PAGXDocument* doc, std::vector<Layer*>& layers,
                                    bool parentHasLayout,
                                    const std::unordered_set<const Layer*>& maskRefs) {
  if (parentHasLayout) {
    return false;
  }
  if (layers.size() < 2) {
    return false;
  }

  std::vector<Layer*> result;
  bool changed = false;
  size_t i = 0;
  while (i < layers.size()) {
    if (!IsMergeableShellLayer(layers[i], maskRefs)) {
      if (changed) {
        result.push_back(layers[i]);
      }
      i++;
      continue;
    }
    size_t j = i + 1;
    while (j < layers.size() && IsMergeableShellLayer(layers[j], maskRefs)) {
      j++;
    }
    if (j - i < 2) {
      if (changed) {
        result.push_back(layers[i]);
      }
      i++;
      continue;
    }
    BeginMutation(layers, result, i, changed);
    // Build a new wrapper layer containing one Group per source.
    auto* wrapper = doc->makeNode<Layer>();
    wrapper->sourceLine = layers[i]->sourceLine;
    for (size_t k = i; k < j; k++) {
      auto* src = layers[k];
      if (src->contents.empty() && src->customData.empty()) {
        continue;  // nothing to wrap, drop
      }
      auto* group = WrapShellLayerAsGroup(doc, src);
      wrapper->contents.push_back(group);
    }
    // If every source was empty, skip the wrapper too.
    if (!wrapper->contents.empty()) {
      result.push_back(wrapper);
    }
    i = j;
  }
  if (!changed) {
    return false;
  }
  layers = std::move(result);
  return true;
}

bool MergeAdjacentShellLayersRecursive(PAGXDocument* doc, std::vector<Layer*>& layers,
                                       bool parentHasLayout,
                                       const std::unordered_set<const Layer*>& maskRefs) {
  bool changed = MergeAdjacentShellLayersInList(doc, layers, parentHasLayout, maskRefs);
  for (auto* layer : layers) {
    bool layerHasLayout = layer->layout != LayoutMode::None;
    changed |= MergeAdjacentShellLayersRecursive(doc, layer->children, layerHasLayout, maskRefs);
  }
  return changed;
}

bool MergeAdjacentShellLayers(PAGXDocument* doc, std::vector<Layer*>& topLevel,
                              const std::unordered_set<const Layer*>& maskRefs) {
  return MergeAdjacentShellLayersRecursive(doc, topLevel, false, maskRefs);
}

// ----------------------------------------------------------------------------
// Unwrap redundant first-child Group: when a Layer/Group's first content child
// is a default-transform Group with no painter that would leak into following
// siblings, splice its elements in place of the Group.
// ----------------------------------------------------------------------------

bool UnwrapRedundantFirstGroupInElements(std::vector<Element*>& elements) {
  if (elements.empty()) {
    return false;
  }
  auto* first = elements[0];
  if (first->nodeType() != NodeType::Group) {
    return false;
  }
  auto* group = static_cast<Group*>(first);
  if (!IsDefaultTransformGroup(group)) {
    return false;
  }
  if (!group->customData.empty()) {
    return false;
  }
  // Painter-leak guard: if the parent has more siblings AND the group contains painters,
  // unwrapping would let those painters bleed into following geometry.
  if (elements.size() > 1 && HasPainter(group->elements)) {
    return false;
  }
  // Layout guard: any direct child element using right/bottom/centerX/centerY needs the group
  // as a constraint frame (this matches verify's CanUnwrapFirstChildGroup).
  for (auto* child : group->elements) {
    auto* layoutNode = LayoutNode::AsLayoutNode(child);
    if (layoutNode == nullptr) {
      continue;
    }
    if (!std::isnan(layoutNode->right) || !std::isnan(layoutNode->bottom) ||
        !std::isnan(layoutNode->centerX) || !std::isnan(layoutNode->centerY)) {
      return false;
    }
  }
  std::vector<Element*> spliced;
  spliced.reserve(elements.size() - 1 + group->elements.size());
  for (auto* gc : group->elements) {
    spliced.push_back(gc);
  }
  for (size_t i = 1; i < elements.size(); i++) {
    spliced.push_back(elements[i]);
  }
  elements = std::move(spliced);
  return true;
}

bool UnwrapRedundantFirstGroupRecursive(std::vector<Element*>& elements) {
  bool changed = UnwrapRedundantFirstGroupInElements(elements);
  // Even without changes at this level, recurse into nested Groups.
  for (auto* el : elements) {
    if (el->nodeType() == NodeType::Group) {
      auto* group = static_cast<Group*>(el);
      changed |= UnwrapRedundantFirstGroupRecursive(group->elements);
    }
  }
  return changed;
}

bool UnwrapRedundantFirstGroupInLayer(Layer* layer) {
  bool changed = UnwrapRedundantFirstGroupRecursive(layer->contents);
  for (auto* child : layer->children) {
    changed |= UnwrapRedundantFirstGroupInLayer(child);
  }
  return changed;
}

// ----------------------------------------------------------------------------
// Merge consecutive Groups that share identical painters (same Fill/Stroke
// trailing block). Geometry from the second Group onwards is folded into the
// first; the duplicate painters of the second Group are dropped.
// ----------------------------------------------------------------------------

bool MergeAdjacentGroupsInElements(std::vector<Element*>& elements) {
  if (elements.size() < 2) {
    return false;
  }
  // Defer allocating `result` until the first merge actually occurs: most sibling lists don't
  // contain a mergeable pair, so in the common case we skip the vector entirely.
  std::vector<Element*> result;
  bool changed = false;
  size_t i = 0;
  while (i < elements.size()) {
    auto* el = elements[i];
    if (el->nodeType() != NodeType::Group) {
      if (changed) {
        result.push_back(el);
      }
      i++;
      continue;
    }
    auto* baseGroup = static_cast<Group*>(el);
    if (!IsDefaultTransformGroup(baseGroup) || !baseGroup->customData.empty()) {
      if (changed) {
        result.push_back(el);
      }
      i++;
      continue;
    }
    auto baseSig = ComputePainterSignature(baseGroup);
    if (!baseSig.valid) {
      if (changed) {
        result.push_back(el);
      }
      i++;
      continue;
    }
    size_t j = i + 1;
    while (j < elements.size()) {
      auto* next = elements[j];
      if (next->nodeType() != NodeType::Group) {
        break;
      }
      auto* nextGroup = static_cast<Group*>(next);
      if (!IsDefaultTransformGroup(nextGroup) || !nextGroup->customData.empty()) {
        break;
      }
      auto nextSig = ComputePainterSignature(nextGroup);
      if (!PainterSignaturesEqual(baseSig, nextSig)) {
        break;
      }

      // Insert nextGroup's geometry (everything before its trailing painters) into baseGroup
      // BEFORE baseGroup's painters. To preserve ordering, splice the new geometry just before
      // the first painter in baseGroup's elements.
      size_t firstPainterIdx = baseGroup->elements.size();
      for (size_t k = 0; k < baseGroup->elements.size(); k++) {
        if (IsPainter(baseGroup->elements[k]->nodeType())) {
          firstPainterIdx = k;
          break;
        }
      }
      // Geometry slice from nextGroup: everything before its painters.
      size_t nextFirstPainterIdx = nextGroup->elements.size();
      for (size_t k = 0; k < nextGroup->elements.size(); k++) {
        if (IsPainter(nextGroup->elements[k]->nodeType())) {
          nextFirstPainterIdx = k;
          break;
        }
      }
      std::vector<Element*> updated;
      updated.reserve(baseGroup->elements.size() + nextFirstPainterIdx);
      for (size_t k = 0; k < firstPainterIdx; k++) {
        updated.push_back(baseGroup->elements[k]);
      }
      for (size_t k = 0; k < nextFirstPainterIdx; k++) {
        updated.push_back(nextGroup->elements[k]);
      }
      for (size_t k = firstPainterIdx; k < baseGroup->elements.size(); k++) {
        updated.push_back(baseGroup->elements[k]);
      }
      baseGroup->elements = std::move(updated);
      // Drop nextGroup entirely (its painters were duplicates of baseGroup's).
      BeginMutation(elements, result, i, changed);
      j++;
    }
    if (changed) {
      result.push_back(baseGroup);
    }
    i = j;
  }
  if (!changed) {
    return false;
  }
  elements = std::move(result);
  return true;
}

bool MergeAdjacentGroupsRecursive(std::vector<Element*>& elements) {
  bool changed = MergeAdjacentGroupsInElements(elements);
  for (auto* el : elements) {
    if (el->nodeType() == NodeType::Group) {
      auto* group = static_cast<Group*>(el);
      changed |= MergeAdjacentGroupsRecursive(group->elements);
    }
  }
  return changed;
}

bool MergeAdjacentGroupsInLayer(Layer* layer) {
  bool changed = MergeAdjacentGroupsRecursive(layer->contents);
  for (auto* child : layer->children) {
    changed |= MergeAdjacentGroupsInLayer(child);
  }
  return changed;
}

// ----------------------------------------------------------------------------
// Collapse redundant single-child Layer nesting.
//
// Importers wrap many leaves in a double Layer: an outer box that positions / sizes / clips, and an
// inner Layer that only carries the payload (an icon's resolved <svg>, a divider's <Path>, a text
// run, ...). When the inner child sits at the outer's content-box origin with the same size, every
// role the outer plays over it (layout, alignment, arrangement, clip) is a no-op, so the two Layers
// render identically whether nested or flattened. Two shapes are collapsed:
//
//   * absorb-child : the child fills the parent and carries no effect of its own -> move the child's
//                    payload up into the parent; the parent keeps its frame / clip / effects.
//   * drop-shell   : the parent is a plain shell (every attribute default, no contents) -> replace
//                    the parent with its only child, which already carries the real attributes.
//
// Both only move existing nodes; neither is applied to a Layer referenced as a mask, and neither
// drops a referenced `id`. Runs bottom-up to a fixed point via the optimizer's iteration loop.
// ----------------------------------------------------------------------------

// The child occupies the parent's whole content box with no offset / transform of its own, so
// flattening it leaves its payload in exactly the same place. A content-sized (NaN) axis is not
// proof of equality: parent and child may measure from different contents, and percentage-sized
// descendants would then resolve against a different box after reparenting. Require each axis to
// be either an exact concrete match or an explicit 100% fill.
bool IsZeroOrUnset(float value) {
  return std::isnan(value) || value == 0.0f;
}

bool AxisFills(float childSize, float parentSize, float childPercent) {
  // Percentage sizing takes precedence over the absolute field in constraint layout, so a
  // programmatically-built node carrying both must be judged by its percentage.
  if (!std::isnan(childPercent)) {
    return childPercent == 100.0f;
  }
  return !std::isnan(childSize) && !std::isnan(parentSize) && childSize == parentSize;
}

bool ChildFillsParent(const Layer* parent, const Layer* child) {
  if (child->x != 0.0f || child->y != 0.0f) {
    return false;
  }
  if (!child->matrix.isIdentity() || !child->matrix3D.isIdentity()) {
    return false;
  }
  if (!IsZeroOrUnset(child->left) || !IsZeroOrUnset(child->top)) {
    return false;
  }
  if (!std::isnan(child->right) || !std::isnan(child->bottom) || !std::isnan(child->centerX) ||
      !std::isnan(child->centerY)) {
    return false;
  }
  // Padding on the parent would inset the child's frame, so only a zero-padding parent qualifies.
  if (!parent->padding.isZero()) {
    return false;
  }
  return AxisFills(child->width, parent->width, child->percentWidth) &&
         AxisFills(child->height, parent->height, child->percentHeight);
}

// The child applies nothing that would change how its payload is painted once it is reparented into
// the (identically-framed) parent. Attributes that describe the child's own frame / layout role
// (size, constraints, flex, includeInLayout) are intentionally not checked here — those are covered
// by ChildFillsParent or are meaningless once the child is dissolved. `layout` must be None because
// a container layout would reposition child layers, and the child keeps none after the merge.
bool ChildHasNoPaintAffectingEffect(const Layer* child) {
  return child->visible && child->alpha == 1.0f && child->blendMode == BlendMode::Normal &&
         child->matrix3D.isIdentity() && !child->preserve3D && child->antiAlias &&
         child->groupOpacity && child->passThroughBackground && !child->hasScrollRect &&
         !child->clipToBounds && child->mask == nullptr && child->composition == nullptr &&
         child->compositionFilePath.empty() && child->externalDoc == nullptr &&
         child->timelines.empty() && child->styles.empty() && child->filters.empty() &&
         child->customData.empty() && child->vmContext.empty() && child->padding.isZero() &&
         child->layout == LayoutMode::None;
}

bool CanAbsorbFillingChild(const Layer* parent, const Layer* child,
                           const std::unordered_set<const Layer*>& maskRefs) {
  if (!child->children.empty()) {
    return false;  // only leaf payload wrappers; child layers would need layout re-parenting
  }
  if (parent->composition != nullptr || !parent->compositionFilePath.empty() ||
      parent->externalDoc != nullptr) {
    return false;  // a composition-backed layer renders its comp, not its own contents/children
  }
  if (LayerNeedsKeeping(child, maskRefs)) {
    return false;  // child is referenced as a mask elsewhere
  }
  // An identified/named layer is externally observable even when no current document node points
  // at it: animations, data binds, host lookups, and later edits may target it. Moving its identity
  // onto the parent changes the scope of those operations (and assigning an id directly would also
  // leave PAGXDocument's id index pointing at the detached child), so only anonymous wrappers may
  // be dissolved.
  if (!child->id.empty() || !child->name.empty()) {
    return false;
  }
  if (!ChildHasNoPaintAffectingEffect(child)) {
    return false;
  }
  if (!ChildFillsParent(parent, child)) {
    return false;
  }
  // An import directive resolves into `contents`, so mixing it with pre-existing content on either
  // layer is unsafe (it can reorder paints), and two imports cannot share one layer.
  bool parentImport = HasUnresolvedImport(parent);
  bool childImport = HasUnresolvedImport(child);
  if (parentImport && childImport) {
    return false;
  }
  if (parentImport && !child->contents.empty()) {
    return false;
  }
  if (childImport && !parent->contents.empty()) {
    return false;
  }
  return true;
}

// Move the filling leaf child's payload into the parent, preserving paint order (any existing
// parent content stays behind the child's). The parent survives with its own frame / clip / effects;
// only the child's now-meaningless container-layout role is reset.
void AbsorbFillingChild(Layer* parent, Layer* child) {
  for (auto* element : child->contents) {
    parent->contents.push_back(element);
  }
  child->contents.clear();
  if (HasUnresolvedImport(child)) {
    parent->importDirective = child->importDirective;
  }
  parent->children.clear();
  parent->layout = LayoutMode::None;
  parent->gap = 0.0f;
  parent->alignment = Alignment::Stretch;
  parent->arrangement = Arrangement::Start;
}

// The parent is a pure shell (all attributes default, no contents), so it contributes nothing and
// can be replaced by its only child. The child must keep the exact flex-item role the shell had
// (flex 0, participating in layout) so a surrounding container's layout is unaffected.
bool CanDropShellParent(const Layer* parent, const Layer* child,
                        const std::unordered_set<const Layer*>& maskRefs) {
  if (!parent->contents.empty()) {
    return false;
  }
  if (!IsLayerShell(parent)) {
    return false;
  }
  // IsLayerShell intentionally ignores these semantic-but-non-geometric fields; dropping the parent
  // would discard them, so a shell carrying any of them is not a pure structural wrapper here.
  if (!parent->compositionFilePath.empty() || parent->externalDoc != nullptr ||
      !parent->timelines.empty() || !parent->vmContext.empty() || !parent->customData.empty()) {
    return false;
  }
  if (LayerNeedsKeeping(parent, maskRefs)) {
    return false;
  }
  if (HasUnresolvedImport(parent)) {
    return false;
  }
  if (child->flex != 0.0f || !child->includeInLayout) {
    return false;
  }
  return true;
}

// Recursively collapse single-child nests in `layers`. Children are processed first (bottom-up), so
// a fully-collapsed child is seen when its parent is considered; the per-layer while-loop then
// collapses multi-level nests in one pass.
bool CollapseSingleChildLayersInList(std::vector<Layer*>& layers,
                                     const std::unordered_set<const Layer*>& maskRefs) {
  bool changed = false;
  for (size_t i = 0; i < layers.size(); i++) {
    Layer* layer = layers[i];
    changed |= CollapseSingleChildLayersInList(layer->children, maskRefs);
    while (layer->children.size() == 1) {
      Layer* child = layer->children[0];
      if (CanDropShellParent(layer, child, maskRefs)) {
        layers[i] = child;
        layer = child;  // child's subtree is already collapsed
        changed = true;
        continue;
      }
      if (CanAbsorbFillingChild(layer, child, maskRefs)) {
        AbsorbFillingChild(layer, child);  // clears layer->children -> loop exits next check
        changed = true;
        continue;
      }
      break;
    }
  }
  return changed;
}

// ============================================================================
// Driver
// ============================================================================

// Recompute the set of mask references reachable from `topLevel` plus all Composition layer
// trees in the document. Some rules (e.g. RectMaskToScrollRect) detach Layer.mask pointers,
// so the maskRefs cache must be refreshed at every iteration.
void RecomputeMaskRefs(PAGXDocument* doc, std::unordered_set<const Layer*>& refs) {
  refs.clear();
  CollectMaskRefs(doc->layers, refs);
  for (auto& node : doc->nodes) {
    if (node->nodeType() == NodeType::Composition) {
      auto* comp = static_cast<Composition*>(node.get());
      CollectMaskRefs(comp->layers, refs);
    }
  }
}

// ----------------------------------------------------------------------------
// Resource dedup / prune passes.
// Run AFTER per-layer rules so any references redirected by canonicalize/simplify
// are reflected here.
// ----------------------------------------------------------------------------

// Build a content-only signature for a PathData (verbs + points). Distinct ids /
// names / sourceLines do not contribute, so structurally equal resources collide.
// Packed binary layout (verb bytes, then raw float bits for each point) is used instead of a
// textual encoding: it is dramatically faster than ostringstream-based formatting and preserves
// exact bit equality, so two paths collide only when every coordinate matches to the last bit.
std::string PathDataSignature(const PathData* data) {
  static_assert(sizeof(Point) == 2 * sizeof(float),
                "Point must be packed {x,y}; signature relies on it");
  const auto& verbs = data->verbs();
  const auto& pts = data->points();
  const size_t pointBytes = pts.size() * sizeof(Point);
  std::string sig;
  sig.resize(verbs.size() + 1 + pointBytes);
  char* out = sig.data();
  for (auto v : verbs) {
    *out++ = static_cast<char>(v);
  }
  *out++ = '|';
  if (pointBytes != 0) {
    std::memcpy(out, pts.data(), pointBytes);
  }
  return sig;
}

void RewritePathDataInLayer(Layer* layer,
                            const std::unordered_map<PathData*, PathData*>& redirect) {
  if (layer == nullptr) {
    return;
  }
  RewritePathDataInElements(layer->contents, redirect);
  for (auto* child : layer->children) {
    RewritePathDataInLayer(child, redirect);
  }
  if (layer->mask != nullptr) {
    RewritePathDataInLayer(layer->mask, redirect);
  }
}

void RewritePathDataInElements(std::vector<Element*>& elements,
                               const std::unordered_map<PathData*, PathData*>& redirect) {
  for (auto* el : elements) {
    auto type = el->nodeType();
    if (type == NodeType::Path) {
      auto* path = static_cast<Path*>(el);
      auto it = redirect.find(path->data);
      if (it != redirect.end()) {
        path->data = it->second;
      }
    } else if (type == NodeType::Group || type == NodeType::TextBox) {
      auto* group = static_cast<Group*>(el);
      RewritePathDataInElements(group->elements, redirect);
    }
  }
}

// Returns true if any duplicate was collapsed. Duplicates have their `id` cleared so the
// subsequent unreferenced-resource pass removes them from the exported document.
bool DedupPathDataResources(PAGXDocument* doc) {
  std::unordered_map<std::string, PathData*> bySig;
  std::unordered_map<PathData*, PathData*> redirect;
  for (auto& nodePtr : doc->nodes) {
    if (nodePtr->nodeType() != NodeType::PathData) {
      continue;
    }
    auto* pd = static_cast<PathData*>(nodePtr.get());
    if (pd->id.empty()) {
      continue;
    }
    auto sig = PathDataSignature(pd);
    if (sig.empty()) {
      continue;
    }
    auto it = bySig.find(sig);
    if (it == bySig.end()) {
      bySig.emplace(std::move(sig), pd);
    } else {
      redirect[pd] = it->second;
    }
  }
  if (redirect.empty()) {
    return false;
  }

  for (auto* layer : doc->layers) {
    RewritePathDataInLayer(layer, redirect);
  }
  for (auto& nodePtr : doc->nodes) {
    if (nodePtr->nodeType() == NodeType::Composition) {
      auto* comp = static_cast<Composition*>(nodePtr.get());
      for (auto* layer : comp->layers) {
        RewritePathDataInLayer(layer, redirect);
      }
    }
  }
  // Drop the duplicates' ids so they will be pruned. Keep them owned in `doc->nodes`
  // (cheap; clearer than juggling unique_ptr lifetimes here).
  for (auto& kv : redirect) {
    kv.first->id.clear();
  }
  return true;
}

// Collect every resource id that is referenced from a Layer, Element, Composition or Font glyph.
void CollectRefsFromElement(const Element* element, std::unordered_set<std::string>& refs) {
  if (element == nullptr) {
    return;
  }
  if (!element->id.empty()) {
    refs.insert(element->id);
  }
  auto type = element->nodeType();
  if (type == NodeType::Group || type == NodeType::TextBox) {
    auto* group = static_cast<const Group*>(element);
    for (auto* child : group->elements) {
      CollectRefsFromElement(child, refs);
    }
  } else if (type == NodeType::Path) {
    auto* path = static_cast<const Path*>(element);
    if (path->data != nullptr && !path->data->id.empty()) {
      refs.insert(path->data->id);
    }
  } else if (type == NodeType::Fill) {
    auto* fill = static_cast<const Fill*>(element);
    if (fill->color != nullptr) {
      if (!fill->color->id.empty()) {
        refs.insert(fill->color->id);
      }
      if (fill->color->nodeType() == NodeType::ImagePattern) {
        auto* pattern = static_cast<const ImagePattern*>(fill->color);
        if (pattern->image != nullptr && !pattern->image->id.empty()) {
          refs.insert(pattern->image->id);
        }
      }
    }
  } else if (type == NodeType::Stroke) {
    auto* stroke = static_cast<const Stroke*>(element);
    if (stroke->color != nullptr) {
      if (!stroke->color->id.empty()) {
        refs.insert(stroke->color->id);
      }
      if (stroke->color->nodeType() == NodeType::ImagePattern) {
        auto* pattern = static_cast<const ImagePattern*>(stroke->color);
        if (pattern->image != nullptr && !pattern->image->id.empty()) {
          refs.insert(pattern->image->id);
        }
      }
    }
  } else if (type == NodeType::Text) {
    auto* text = static_cast<const Text*>(element);
    for (auto* run : text->glyphRuns) {
      if (run != nullptr && run->font != nullptr && !run->font->id.empty()) {
        refs.insert(run->font->id);
      }
    }
  }
}

void CollectRefsFromLayer(const Layer* layer, std::unordered_set<std::string>& refs) {
  if (layer == nullptr) {
    return;
  }
  if (!layer->id.empty()) {
    refs.insert(layer->id);
  }
  if (layer->mask != nullptr) {
    CollectRefsFromLayer(layer->mask, refs);
  }
  if (layer->composition != nullptr && !layer->composition->id.empty()) {
    refs.insert(layer->composition->id);
  }
  for (auto* el : layer->contents) {
    CollectRefsFromElement(el, refs);
  }
  for (auto* child : layer->children) {
    CollectRefsFromLayer(child, refs);
  }
}

void CollectReferencedIds(const PAGXDocument* doc, std::unordered_set<std::string>& refs) {
  for (auto* layer : doc->layers) {
    CollectRefsFromLayer(layer, refs);
  }
  for (auto& nodePtr : doc->nodes) {
    auto type = nodePtr->nodeType();
    if (type == NodeType::Composition) {
      auto* comp = static_cast<const Composition*>(nodePtr.get());
      for (auto* layer : comp->layers) {
        CollectRefsFromLayer(layer, refs);
      }
    } else if (type == NodeType::Font) {
      auto* font = static_cast<const Font*>(nodePtr.get());
      for (auto* glyph : font->glyphs) {
        if (glyph == nullptr) {
          continue;
        }
        if (glyph->path != nullptr && !glyph->path->id.empty()) {
          refs.insert(glyph->path->id);
        }
        if (glyph->image != nullptr && !glyph->image->id.empty()) {
          refs.insert(glyph->image->id);
        }
      }
    }
  }
}

bool IsResourceNode(NodeType type) {
  switch (type) {
    case NodeType::PathData:
    case NodeType::Image:
    case NodeType::Composition:
    case NodeType::SolidColor:
    case NodeType::LinearGradient:
    case NodeType::RadialGradient:
    case NodeType::ConicGradient:
    case NodeType::DiamondGradient:
    case NodeType::ImagePattern:
    case NodeType::Font:
      return true;
    default:
      return false;
  }
}

// Clear `id` on resources that are no longer referenced anywhere. The exporter writes
// a `<Resources>` entry only when `id` is non-empty, so this effectively prunes them.
// The owning unique_ptr stays in `doc->nodes` (negligible cost; safer than mutating that
// vector while other code may still hold raw pointers).
bool PruneUnreferencedResources(PAGXDocument* doc) {
  std::unordered_set<std::string> refs;
  CollectReferencedIds(doc, refs);
  bool changed = false;
  for (auto& nodePtr : doc->nodes) {
    auto* node = nodePtr.get();
    if (node->id.empty()) {
      continue;
    }
    if (!IsResourceNode(node->nodeType())) {
      continue;
    }
    if (refs.find(node->id) == refs.end()) {
      node->id.clear();
      changed = true;
    }
  }
  return changed;
}

// Runs the per-layer-list rule loop until a fixed point or `options.maxIterations` is reached.
// Returns the number of iterations that were actually executed — callers use this to sum up a
// monotonic "iterations used" counter and to detect non-convergence (iteration count exactly
// matches the cap while the last pass still reported changes).
int OptimizeLayerList(PAGXDocument* doc, std::vector<Layer*>& layers,
                      std::unordered_set<const Layer*>& maskRefs,
                      const PAGXOptimizerOptions& options, bool* converged) {
  int iter = 0;
  for (; iter < options.maxIterations; iter++) {
    bool changed = false;

    if (options.canonicalizePaths) {
      for (auto* layer : layers) {
        changed |= CanonicalizePathsInLayer(doc, layer);
      }
    }
    if (options.rectMaskToScrollRect) {
      bool rmChanged = false;
      for (auto* layer : layers) {
        rmChanged |= RectMaskToScrollRectInLayer(layer);
      }
      if (rmChanged) {
        RecomputeMaskRefs(doc, maskRefs);
        changed = true;
      }
    }
    if (options.pruneEmpty) {
      changed |= PruneEmptyTopLevel(layers, false, maskRefs);
    }
    if (options.unwrapRedundantFirstGroup) {
      for (auto* layer : layers) {
        changed |= UnwrapRedundantFirstGroupInLayer(layer);
      }
    }
    if (options.mergeAdjacentGroups) {
      for (auto* layer : layers) {
        changed |= MergeAdjacentGroupsInLayer(layer);
      }
    }
    if (options.downgradeShellChildren) {
      changed |= DowngradeShellChildren(doc, layers, maskRefs);
    }
    if (options.mergeAdjacentShellLayers) {
      changed |= MergeAdjacentShellLayers(doc, layers, maskRefs);
    }
    if (options.collapseSingleChildLayers) {
      changed |= CollapseSingleChildLayersInList(layers, maskRefs);
    }
    if (!changed) {
      return iter + 1;
    }
  }
  *converged = false;
  return iter;
}

}  // namespace

PAGXOptimizer::Result OptimizeWithOptions(PAGXDocument* doc, const PAGXOptimizerOptions& options) {
  PAGXOptimizer::Result result;
  if (doc == nullptr) {
    return result;
  }

  std::unordered_set<const Layer*> maskRefs;
  RecomputeMaskRefs(doc, maskRefs);

  result.iterationsUsed +=
      OptimizeLayerList(doc, doc->layers, maskRefs, options, &result.converged);
  for (auto& node : doc->nodes) {
    if (node->nodeType() == NodeType::Composition) {
      auto* comp = static_cast<Composition*>(node.get());
      result.iterationsUsed +=
          OptimizeLayerList(doc, comp->layers, maskRefs, options, &result.converged);
    }
  }

  // Resource-level cleanup: deduplicate identical PathData resources first (so the prune pass
  // sees the redirected references), then drop anything no longer referenced.
  if (options.dedupPathData) {
    DedupPathDataResources(doc);
  }
  if (options.pruneUnreferencedResources) {
    PruneUnreferencedResources(doc);
  }

  if (!result.converged) {
    doc->errors.push_back("PAGXOptimizer: structural rules did not reach a fixed point within " +
                          std::to_string(options.maxIterations) +
                          " iterations — some simplifications may be missed");
  }
  return result;
}

PAGXOptimizer::Result PAGXOptimizer::Optimize(PAGXDocument* doc) {
  return OptimizeWithOptions(doc, PAGXOptimizerOptions());
}

}  // namespace pagx