#include "rive/semantic/semantic_manager.hpp"

#include "rive/artboard.hpp"
#include "rive/component.hpp"
#include "rive/semantic/semantic_data.hpp"
#include "rive/semantic/semantic_node.hpp"
#include "rive/semantic/semantic_provider.hpp"
#include "rive/semantic/semantic_role.hpp"
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace rive;

namespace
{
// ---------------------------------------------------------------------------
// Label derivation helpers.
//
// Interactive elements (button, toggle, etc.) with no explicit label derive
// their accessible label from child semantic nodes. Children that contribute
// to the derived label are "absorbed" — excluded from the flat accessibility
// output so screen readers don't announce them twice.
// ---------------------------------------------------------------------------

// Trim leading/trailing whitespace and collapse internal runs of whitespace
// to a single space. Preserves logical reading order.
static std::string normalizeLabel(const std::string& input)
{
  std::string result;
  result.reserve(input.size());
  bool lastWasSpace = true; // treats start as whitespace → trims leading
  for (char c : input)
  {
    if (static_cast<unsigned char>(c) <= ' ')
    {
      if (!lastWasSpace && !result.empty())
      {
        result += ' ';
        lastWasSpace = true;
      }
    }
    else
    {
      result += c;
      lastWasSpace = false;
    }
  }
  // Trim trailing space.
  if (!result.empty() && result.back() == ' ')
  {
    result.pop_back();
  }
  return result;
}

// A node the flattened tree leaves out, together with everything under it:
// a SemanticData that is excluded (collapsed, Hidden, or on a hidden
// drawable), or the boundary of an artboard whose host is collapsed. The
// tree itself never changes shape when something hides; every walk that
// produces what the platform sees checks this instead.
static bool isHiddenNode(const SemanticNode* node)
{
  if (node->isBoundaryNode())
  {
    auto* artboard = node->boundaryArtboard();
    return artboard != nullptr && artboard->isHostCollapsed();
  }
  auto* data = node->semanticData();
  return data != nullptr && data->isExcludedFromSemanticTree();
}

// Walks the subtree rooted at `node` in tree order, collecting text and
// image labels. All visited (non-interactive) nodes are added to
// `absorbedIds`. Nested interactive elements are left untouched — they
// are not absorbed and their subtrees are not descended into.
static void collectLabelsFromSubtree(
    const rcp<SemanticNode>& node,
    std::string& textOut,
    std::string& imageTextOut,
    std::unordered_set<uint32_t>& absorbedIds)
{
  if (isHiddenNode(node.get()))
  {
    return;
  }
  auto role = static_cast<SemanticRole>(node->role());

  // Nested interactive element: don't absorb, don't descend.
  if (isInteractiveRole(role))
  {
    return;
  }

  absorbedIds.insert(node->id());

  if (role == SemanticRole::text && !node->label().empty())
  {
    if (!textOut.empty())
    {
      textOut += ' ';
    }
    textOut += node->label();
  }
  else if (role == SemanticRole::image && !node->label().empty())
  {
    // Only keep the first image label as fallback.
    if (imageTextOut.empty())
    {
      imageTextOut = node->label();
    }
  }

  for (const auto& child : node->children())
  {
    collectLabelsFromSubtree(child, textOut, imageTextOut, absorbedIds);
  }
}

// Reusable scratch state for a single deriveLabelForInteractiveNodes pass.
// Allocation buffers are owned here and clear()-ed between interactive
// nodes so capacity is kept across the walk.
struct LabelDerivationScratch
{
  std::string textLabel;
  std::string imageLabel;
  std::unordered_set<uint32_t> absorbed;
};

static void deriveLabelVisit(
    const rcp<SemanticNode>& node,
    std::unordered_map<uint32_t, std::string>& derivedLabels,
    std::unordered_set<uint32_t>& excludedIds,
    LabelDerivationScratch& scratch)
{
  if (isHiddenNode(node.get()))
  {
    return;
  }
  if (isInteractiveRole(node->role()) && node->label().empty())
  {
    scratch.textLabel.clear();
    scratch.imageLabel.clear();
    scratch.absorbed.clear();

    for (const auto& child : node->children())
    {
      collectLabelsFromSubtree(
          child,
          scratch.textLabel,
          scratch.imageLabel,
          scratch.absorbed);
    }

    // Text takes priority; images are fallback only (spec §3.3).
    std::string derived = normalizeLabel(scratch.textLabel);
    if (derived.empty())
    {
      derived = normalizeLabel(scratch.imageLabel);
    }

    if (!derived.empty())
    {
      derivedLabels[node->id()] = std::move(derived);
      excludedIds.insert(scratch.absorbed.begin(), scratch.absorbed.end());
    }
  }

  for (const auto& child : node->children())
  {
    if (excludedIds.count(child->id()) == 0)
    {
      deriveLabelVisit(child, derivedLabels, excludedIds, scratch);
    }
  }
}

// Pre-pass that computes derived labels for interactive nodes and builds
// the set of absorbed (excluded) node IDs.
//
// Rules (from spec):
//   1. Explicit label wins — skip derivation.
//   2. Text children contribute in tree order; images only if no text.
//   3. Hidden nodes and their subtrees are skipped (see isHiddenNode).
//   4. textField never auto-derives (not in isInteractiveRole).
//   5. Nested interactive children are not absorbed.
static void deriveLabelForInteractiveNodes(
    const std::vector<rcp<SemanticNode>>& roots,
    std::unordered_map<uint32_t, std::string>& derivedLabels,
    std::unordered_set<uint32_t>& excludedIds)
{
  LabelDerivationScratch scratch;
  for (const auto& root : roots)
  {
    deriveLabelVisit(root, derivedLabels, excludedIds, scratch);
  }
}

// ---------------------------------------------------------------------------
// Tree flattening.
// ---------------------------------------------------------------------------

// Depth-first pre-order flattening of the SemanticNode tree into a flat
// array of SemanticsDiffNode structs. Nodes in `excludedIds` are skipped
// but their non-excluded children are reparented to the excluded node's
// parent (handles the nested-interactive-inside-absorbed-group case).
// Interactive nodes with entries in `derivedLabels` use the derived label
// instead of their (empty) canonical label.
static void flattenSemanticNode(
    const rcp<SemanticNode>& node,
    int32_t parentId,
    uint32_t& siblingCounter,
    std::vector<SemanticsDiffNode>& out,
    const std::unordered_set<uint32_t>& excludedIds,
    const std::unordered_map<uint32_t, std::string>& derivedLabels)
{
  if (isHiddenNode(node.get()))
  {
    return;
  }
  if (excludedIds.count(node->id()) || node->isBoundaryNode())
  {
    // Node is absorbed or is a structural boundary node — skip it
    // but reparent any non-excluded children to the absorbing parent.
    for (const auto& child : node->children())
    {
      flattenSemanticNode(
          child,
          parentId,
          siblingCounter,
          out,
          excludedIds,
          derivedLabels);
    }
    return;
  }

  SemanticsDiffNode flat;
  flat.id = node->id();
  flat.role = node->role();

  auto derivedIt = derivedLabels.find(node->id());
  flat.label = (derivedIt != derivedLabels.end()) ? derivedIt->second
                                                  : node->label();

  flat.value = node->value();
  flat.hint = node->hint();
  flat.stateFlags = node->stateFlags();
  flat.traitFlags = node->traitFlags();
  flat.headingLevel = node->headingLevel();
  const auto bounds = node->bounds();
  flat.minX = bounds.minX;
  flat.minY = bounds.minY;
  flat.maxX = bounds.maxX;
  flat.maxY = bounds.maxY;
  flat.parentId = parentId;
  flat.siblingIndex = siblingCounter++;
  out.push_back(flat);

  uint32_t childSiblingCounter = 0;
  for (const auto& child : node->children())
  {
    flattenSemanticNode(
        child,
        static_cast<int32_t>(flat.id),
        childSiblingCounter,
        out,
        excludedIds,
        derivedLabels);
  }
}

// Entry point for full-tree flattening. Iterates all root nodes (nodes with
// no semantic parent, i.e. top-level accessible elements). Root nodes have
// parentId = -1. The reserveHint pre-allocates to avoid repeated
// vector reallocation during the walk.
static std::vector<SemanticsDiffNode> flattenFromSemanticNodes(
    const std::vector<rcp<SemanticNode>>& roots,
    size_t reserveHint,
    const std::unordered_set<uint32_t>& excludedIds,
    const std::unordered_map<uint32_t, std::string>& derivedLabels)
{
  std::vector<SemanticsDiffNode> out;
  if (reserveHint != 0)
  {
    out.reserve(reserveHint);
  }
  uint32_t rootSiblingCounter = 0;
  for (const auto& root : roots)
  {
    flattenSemanticNode(
        root,
        -1,
        rootSiblingCounter,
        out,
        excludedIds,
        derivedLabels);
  }
  return out;
}

// Maps parentId → ordered list of child ids.
// Used by buildDiffFromFlats to detect reordering and reparenting.
using ChildrenByParent = std::unordered_map<int32_t, std::vector<uint32_t>>;

// Builds the ChildrenByParent map from a flat snapshot. Groups nodes by
// parentId, then sorts each group by siblingIndex to produce the
// canonical child ordering. This ordering is compared frame-to-frame to
// detect reorder/reparent changes, which are emitted as
// SemanticsChildrenUpdate entries in the diff.
static ChildrenByParent buildChildrenByParent(
    const std::vector<SemanticsDiffNode>& nodes)
{
  // First pass: group (siblingIndex, id) pairs by parent.
  std::unordered_map<int32_t, std::vector<std::pair<uint32_t, uint32_t>>>
      grouped;
  grouped.reserve(nodes.size());
  for (const auto& node : nodes)
  {
    grouped[node.parentId].emplace_back(node.siblingIndex, node.id);
  }

  // Second pass: sort each group by siblingIndex and extract ids
  // in order. The result is a map from parentId to an ordered child list
  // that can be directly compared via == for change detection.
  ChildrenByParent out;
  out.reserve(grouped.size());
  for (auto& entry : grouped)
  {
    auto& nodeList = entry.second;
    std::sort(
        nodeList.begin(),
        nodeList.end(),
        [](const std::pair<uint32_t, uint32_t>& a,
           const std::pair<uint32_t, uint32_t>& b) {
          return a.first < b.first;
        });
    auto& children = out[entry.first];
    children.reserve(nodeList.size());
    for (const auto& n : nodeList)
    {
      children.push_back(n.second);
    }
  }
  return out;
}

// ---------------------------------------------------------------------------
// Visual position ordering.
//
// Screen-reader traversal order is determined by the order of children in
// each SemanticNode's children vector. These helpers sort children by their
// visual position (top-to-bottom, left-to-right) and detect when bounds
// changes have caused siblings to move past each other.
// ---------------------------------------------------------------------------

// Returns true if the children with valid bounds are already in visual
// order (top-to-bottom, left-to-right). Nodes with empty/NaN bounds are
// skipped — they have no visual position to compare.
static bool childrenInVisualOrder(
    const std::vector<rcp<SemanticNode>>& children)
{
  AABB prevBounds;
  bool hasPrev = false;
  for (const auto& child : children)
  {
    const auto b = child->bounds();
    if (b.isEmptyOrNaN())
    {
      continue;
    }
    if (hasPrev)
    {
      if (b.minY < prevBounds.minY ||
          (b.minY == prevBounds.minY && b.minX < prevBounds.minX))
      {
        return false;
      }
    }
    prevBounds = b;
    hasPrev = true;
  }
  return true;
}

// Compares two flat snapshots (current vs. previous) and produces a
// SemanticsDiff with added, removed, moved, updatedSemantic,
// updatedGeometry, and childrenUpdated arrays.
static SemanticsDiff buildDiffFromFlats(
    const std::vector<SemanticsDiffNode>& currentFlat,
    const std::vector<SemanticsDiffNode>& previousFlat,
    uint64_t treeVersion)
{
  SemanticsDiff diff;
  diff.frameNumber = Artboard::frameId();
  diff.treeVersion = treeVersion;

  uint32_t rootCount = 0;
  uint32_t rootId = 0;
  for (const auto& node : currentFlat)
  {
    if (node.parentId != -1)
    {
      continue;
    }
    rootCount++;
    rootId = node.id;
  }
  if (rootCount == 1)
  {
    diff.rootId = rootId;
  }

  // First-frame fast path: no previous snapshot to diff against, so
  // everything is an addition. Also emit the full children ordering map
  // so the platform can set up its tree structure in one pass.
  //
  // Emit childrenUpdated entries in the order parents first appear as
  // parentId in currentFlat (tree pre-order). Consumers applying the diff
  // sequentially see parents attached before their children's orderings.
  if (previousFlat.empty())
  {
    const auto currentChildrenByParent = buildChildrenByParent(currentFlat);
    std::unordered_set<int32_t> seenParents;
    seenParents.reserve(currentChildrenByParent.size());
    for (const auto& node : currentFlat)
    {
      if (!seenParents.insert(node.parentId).second)
      {
        continue;
      }
      auto it = currentChildrenByParent.find(node.parentId);
      if (it == currentChildrenByParent.end())
      {
        continue;
      }
      SemanticsChildrenUpdate update;
      update.parentId = it->first;
      update.childIds = it->second;
      diff.childrenUpdated.push_back(std::move(update));
    }

    diff.added.reserve(currentFlat.size());
    for (const auto& node : currentFlat)
    {
      diff.added.push_back(node);
    }
    return diff;
  }

  // Build O(1) lookup maps for both snapshots. These allow per-node
  // comparisons without scanning the full arrays.
  std::unordered_map<uint32_t, const SemanticsDiffNode*> currentById;
  currentById.reserve(currentFlat.size());
  for (const auto& node : currentFlat)
  {
    currentById[node.id] = &node;
  }

  std::unordered_map<uint32_t, const SemanticsDiffNode*> previousById;
  previousById.reserve(previousFlat.size());
  for (const auto& node : previousFlat)
  {
    previousById[node.id] = &node;
  }

  // Build children-by-parent maps for both snapshots. Used later
  // to detect reordering and reparenting of child lists.
  const auto currentChildrenByParent = buildChildrenByParent(currentFlat);
  const auto previousChildrenByParent = buildChildrenByParent(previousFlat);

  // Removal detection: any node in the previous snapshot that is absent
  // from the current snapshot has been removed. The platform layer uses
  // this to tear down the corresponding accessibility node. Iterate
  // previousFlat (tree pre-order) so removed ids are emitted
  // deterministically.
  for (const auto& previousNode : previousFlat)
  {
    if (currentById.find(previousNode.id) == currentById.end())
    {
      diff.removed.push_back(previousNode.id);
    }
  }

  // Added / moved / content / geometry detection for nodes in current.
  // For each current node:
  //   - If absent from previous → added (new node appeared).
  //   - If present in previous → compare fields:
  //     - parentId or siblingIndex changed → moved (reparent or
  //       reorder within same parent).
  //     - role, label, or stateFlags changed → updatedSemantic. The
  //       platform layer re-reads these to update screen reader properties.
  //     - bounds changed → updatedGeometry. The platform layer updates
  //       the hit-test region and visual position.
  //   A single node can appear in multiple diff arrays (e.g. both moved
  //   and updatedSemantic) if multiple aspects changed simultaneously.
  //
  // Iterate currentFlat (tree pre-order) so parents land in the added/
  // moved arrays before their children, and iteration is deterministic
  // frame-to-frame. currentById/previousById are used for O(1) lookup.
  for (const auto& currentNode : currentFlat)
  {
    auto previousIt = previousById.find(currentNode.id);
    if (previousIt == previousById.end())
    {
      diff.added.push_back(currentNode);
      continue;
    }

    const auto& previousNode = *previousIt->second;

    // Moved detection: parent changed (reparent) or sibling position
    // changed (reorder within the same parent).
    const bool moved = previousNode.parentId != currentNode.parentId ||
                       previousNode.siblingIndex != currentNode.siblingIndex;
    if (moved)
    {
      diff.moved.push_back(currentNode);
    }

    // Semantic content detection: any content field changed. These
    // affect how a screen reader announces the node (e.g. "button,
    // selected" vs "button"). Must cover the same seven fields as the
    // incremental path (patchContentNode): the new snapshot is stored
    // and dirty sets cleared after this, so a missed field is lost
    // permanently, not delayed.
    if (previousNode.role != currentNode.role ||
        previousNode.label != currentNode.label ||
        previousNode.value != currentNode.value ||
        previousNode.hint != currentNode.hint ||
        previousNode.headingLevel != currentNode.headingLevel ||
        previousNode.stateFlags != currentNode.stateFlags ||
        previousNode.traitFlags != currentNode.traitFlags)
    {
      diff.updatedSemantic.push_back(currentNode);
    }

    // Geometry detection: bounds changed. Affects hit-test region and
    // visual overlay positioning.
    if (previousNode.minX != currentNode.minX ||
        previousNode.minY != currentNode.minY ||
        previousNode.maxX != currentNode.maxX ||
        previousNode.maxY != currentNode.maxY)
    {
      diff.updatedGeometry.push_back(
          {currentNode.id,
           currentNode.minX,
           currentNode.minY,
           currentNode.maxX,
           currentNode.maxY});
    }
  }

  // Children ordering updates. Parent ids are collected in currentFlat
  // tree order, then appended with any parents that only exist in
  // previousFlat. This gives a deterministic emission order matching how
  // a consumer would walk the new tree.
  std::vector<int32_t> orderedParents;
  std::unordered_set<int32_t> seenParents;
  orderedParents.reserve(
      currentChildrenByParent.size() + previousChildrenByParent.size());
  seenParents.reserve(orderedParents.capacity());
  for (const auto& node : currentFlat)
  {
    if (seenParents.insert(node.parentId).second)
    {
      orderedParents.push_back(node.parentId);
    }
  }
  for (const auto& node : previousFlat)
  {
    if (seenParents.insert(node.parentId).second)
    {
      orderedParents.push_back(node.parentId);
    }
  }

  for (const auto parentId : orderedParents)
  {
    auto currentIt = currentChildrenByParent.find(parentId);
    auto previousIt = previousChildrenByParent.find(parentId);
    std::vector<uint32_t> empty;
    const auto* currentChildren = currentIt == currentChildrenByParent.end()
                                      ? &empty
                                      : &currentIt->second;
    const auto* previousChildren = previousIt == previousChildrenByParent.end()
                                       ? &empty
                                       : &previousIt->second;
    if (*currentChildren != *previousChildren)
    {
      SemanticsChildrenUpdate update;
      update.parentId = parentId;
      update.childIds = *currentChildren;
      diff.childrenUpdated.push_back(std::move(update));
    }
  }

  return diff;
}

} // namespace

// Recursively sorts each node's children by visual position so that the
// flatten traversal produces siblingIndex values matching screen-reader
// order (top-to-bottom, left-to-right). Nodes with empty/NaN bounds are
// sorted to the end, preserving their relative insertion order via
// stable_sort.
void SemanticManager::sortChildrenByVisualPosition(
    std::vector<rcp<SemanticNode>>& nodes)
{
  if (nodes.size() > 1)
  {
    std::stable_sort(
        nodes.begin(),
        nodes.end(),
        [](const rcp<SemanticNode>& a, const rcp<SemanticNode>& b) {
          const auto ab = a->bounds();
          const auto bb = b->bounds();
          const bool aEmpty = ab.isEmptyOrNaN();
          const bool bEmpty = bb.isEmptyOrNaN();
          // Empty-bounds nodes sort after all valid-bounds nodes.
          if (aEmpty != bEmpty)
          {
            return bEmpty; // a < b when b is empty and a is not
          }
          if (aEmpty)
          {
            return false; // both empty — preserve order
          }
          if (ab.minY != bb.minY)
          {
            return ab.minY < bb.minY;
          }
          return ab.minX < bb.minX;
        });
  }

  for (auto& node : nodes)
  {
    // A hidden subtree is not flattened; showing it marks Structure, which
    // sorts it then.
    if (!isHiddenNode(node.get()))
    {
      sortChildrenByVisualPosition(node->mutableChildren());
    }
  }
}

// Marks a specific node dirty. The global m_dirt flag triggers refresh();
// the per-node sets enable O(K) incremental patching. id == 0 is the
// uninitialized sentinel — we set global dirt but skip per-node.
void SemanticManager::markNodeDirty(uint32_t id, SemanticDirt dirt)
{
  // A node the platform was not given (hidden, or not yet flattened) has
  // nothing to patch: the next structural flatten reads it live. A node
  // absorbed into a parent's derived label still counts, since a change to
  // it re-derives that label. Boundary nodes are never in the snapshot, yet
  // their bounds decide sibling order, so only a hidden one is skipped.
  if (id != 0)
  {
    auto it = m_nodesById.find(id);
    if (it != m_nodesById.end())
    {
      const SemanticNode* node = it->second.get();
      const bool skip = node->isBoundaryNode()
                            ? isHiddenNode(node)
                            : m_snapshotIds.count(id) == 0 &&
                                  m_excludedIds.count(id) == 0;
      if (skip)
      {
        return;
      }
    }
  }
  markDirty(dirt);
  if (id == 0)
  {
    return;
  }

  if (enums::is_flag_set(dirt, SemanticDirt::Content))
  {
    m_dirtyContentNodes.insert(id);
  }
  if (enums::is_flag_set(dirt, SemanticDirt::Bounds))
  {
    m_dirtyBoundsNodes.insert(id);
  }
}

void SemanticManager::markBoundaryDirty(uint32_t boundaryNodeId)
{
  m_dirtyBoundaryIds.insert(boundaryNodeId);
  markDirty(SemanticDirt::Bounds);
}

// Re-read bounds for every node in the subtree rooted at `node`:
// boundary nodes get their artboard rect mapped through rootTransform,
// non-boundary nodes get their component's semanticBounds(). Each node
// whose bounds actually changed is inserted into m_dirtyBoundsNodes.
void SemanticManager::reconcileBoundsForSubtree(SemanticNode* node)
{
  if (node == nullptr)
  {
    return;
  }

  if (node->isBoundaryNode())
  {
    if (auto* ab = node->boundaryArtboard())
    {
      const AABB newBounds = SemanticProvider::rootTransformAABB(
          ab,
          AABB::fromLTWH(0.0f, 0.0f, ab->width(), ab->height()));
      if (newBounds != node->bounds())
      {
        node->bounds(newBounds);
        m_dirtyBoundsNodes.insert(node->id());
      }
    }
  }
  else
  {
    auto* coreOwner = node->coreOwner();
    if (coreOwner != nullptr && coreOwner->is<Component>())
    {
      auto* owner = coreOwner->as<Component>();
      const AABB liveBounds = SemanticProvider::semanticBounds(owner);
      if (liveBounds != node->bounds())
      {
        node->bounds(liveBounds);
        m_dirtyBoundsNodes.insert(node->id());
      }
    }
  }

  for (const auto& child : node->children())
  {
    reconcileBoundsForSubtree(child.get());
  }
}

// Assign a manager-local id to this node, or reconcile the watermark
// for an explicitly-provided id so subsequent auto-assignments don't
// collide. Called from addChild() before the lookup map is updated.
void SemanticManager::ensureNodeId(SemanticNode& node)
{
  if (node.id() == 0)
  {
    // Fresh node: pick the next local id. Skip any id already in
    // the map (can happen when an explicit id was preserved earlier
    // with a value greater than our watermark).
    while (m_nodesById.count(m_nextLocalId) != 0)
    {
      ++m_nextLocalId;
    }
    node.id(m_nextLocalId++);
    return;
  }

  // Explicit id: bump the watermark so future auto-assignments skip it.
  if (node.id() >= m_nextLocalId)
  {
    m_nextLocalId = node.id() + 1;
  }
}

// Registers a SemanticNode in the tree. Appends the child to the
// parent's children (or roots). Assigns a manager-local id if the node
// was constructed without one. If the node's id collides with a
// *different* node already tracked by this manager (nodes migrating from
// another manager's id space), reassign it.
void SemanticManager::addChild(
    rcp<SemanticNode> parentNode,
    rcp<SemanticNode> child)
{
  if (child == nullptr)
  {
    return;
  }

  // Collision with a different node already tracked under this id —
  // reassign the new node to a fresh manager-local id.
  auto existing = m_nodesById.find(child->id());
  if (child->id() != 0 && existing != m_nodesById.end() &&
      existing->second != child)
  {
    child->id(0);
  }

  ensureNodeId(*child);

  if (m_nodesById.find(child->id()) == m_nodesById.end())
  {
    m_nodesById[child->id()] = child;
  }

  child->manager(this);

  // Append to the end — refresh() sorts children by visual position
  // (bounds) before every flatten.
  if (parentNode != nullptr)
  {
    // Parent may have been created by a different artboard's
    // buildSemanticTree and never inserted here directly.
    if (m_nodesById.find(parentNode->id()) == m_nodesById.end())
    {
      m_nodesById[parentNode->id()] = parentNode;
    }
    child->parent(parentNode.get());
    parentNode->mutableChildren().push_back(child);
  }
  else
  {
    child->parent(nullptr);
    m_roots.push_back(child);
  }

  markDirty(SemanticDirt::Structure);
}

// Removes a SemanticNode from the tree. Unlinks from parent (or roots),
// clears the manager back-reference, removes from lookup map, and marks
// Structure dirty so the next refresh() emits a removal diff entry.
void SemanticManager::removeChild(rcp<SemanticNode> node)
{
  if (node == nullptr)
  {
    return;
  }

  auto* parentNode = node->parent();
  if (parentNode != nullptr)
  {
    auto& siblings = parentNode->mutableChildren();
    siblings.erase(
        std::remove_if(
            siblings.begin(),
            siblings.end(),
            [&node](const rcp<SemanticNode>& child) {
              return child.get() == node.get();
            }),
        siblings.end());
    node->parent(nullptr);
  }
  else
  {
    m_roots.erase(
        std::remove_if(
            m_roots.begin(),
            m_roots.end(),
            [&node](const rcp<SemanticNode>& root) {
              return root.get() == node.get();
            }),
        m_roots.end());
  }

  node->manager(nullptr);
  m_nodesById.erase(node->id());
  markDirty(SemanticDirt::Structure);
}

// Incremental bounds patch for a single dirty node. Compares live bounds
// to the snapshot; if different, updates in-place and emits updatedGeometry.
void SemanticManager::patchBoundsNode(
    SemanticsDiffNode& entry,
    SemanticsDiff& diff)
{
  auto nodeIt = m_nodesById.find(entry.id);
  if (nodeIt == m_nodesById.end())
  {
    return;
  }
  const auto b = nodeIt->second->bounds();

  // Only emit an update if bounds actually changed. This avoids no-op
  // diffs when a node is marked dirty but its bounds haven't moved
  // (e.g. a text content change that doesn't affect layout).
  if (entry.minX != b.minX || entry.minY != b.minY || entry.maxX != b.maxX ||
      entry.maxY != b.maxY)
  {
    entry.minX = b.minX;
    entry.minY = b.minY;
    entry.maxX = b.maxX;
    entry.maxY = b.maxY;
    diff.updatedGeometry.push_back(
        {entry.id, entry.minX, entry.minY, entry.maxX, entry.maxY});
  }
}

// Incremental content patch for a single dirty node. Compares role, label,
// stateFlags, and traitFlags to the snapshot; if different, updates in-place
// and emits updatedSemantic. This is how animation/data-binding changes to
// stateFlags (e.g. "Selected" toggling) propagate to the platform layer.
void SemanticManager::patchContentNode(
    SemanticsDiffNode& entry,
    SemanticsDiff& diff)
{
  auto nodeIt = m_nodesById.find(entry.id);
  if (nodeIt == m_nodesById.end())
  {
    return;
  }
  const auto& node = nodeIt->second;

  // Use derived label if this node has one, otherwise the canonical label.
  auto derivedIt = m_derivedLabels.find(entry.id);
  const std::string& effectiveLabel = (derivedIt != m_derivedLabels.end())
                                          ? derivedIt->second
                                          : node->label();

  // Compare all semantic content fields. Even if only one changed,
  // we update all fields to keep the snapshot consistent.
  if (entry.role != node->role() || entry.label != effectiveLabel ||
      entry.value != node->value() || entry.hint != node->hint() ||
      entry.stateFlags != node->stateFlags() ||
      entry.traitFlags != node->traitFlags() ||
      entry.headingLevel != node->headingLevel())
  {
    entry.role = node->role();
    entry.label = effectiveLabel;
    entry.value = node->value();
    entry.hint = node->hint();
    entry.stateFlags = node->stateFlags();
    entry.traitFlags = node->traitFlags();
    entry.headingLevel = node->headingLevel();
    diff.updatedSemantic.push_back(entry);
  }
}

// Core refresh algorithm. Two paths:
// 1. FULL RE-FLATTEN (Structure dirty or first frame): O(N) in tree size.
// 2. INCREMENTAL PATCH (only Bounds/Content dirty): O(K) dirty nodes.
// Before diffing, reconciles live bounds and computes container bounds.
void SemanticManager::refresh()
{
  // Read the current dirt flags.
  const bool structureDirty = enums::is_flag_set(
      m_dirt,
      SemanticDirt::Structure);
  bool boundsDirty = enums::is_flag_set(m_dirt, SemanticDirt::Bounds);
  const bool contentDirty = enums::is_flag_set(m_dirt, SemanticDirt::Content);

  // -------------------------------------------------------------------------
  // Targeted bounds reconciliation via dirty boundary nodes.
  //
  // When a host artboard's transform changes, its boundary node is marked
  // dirty via markBoundaryDirty(). We re-read bounds only for nodes under
  // dirty boundaries — O(K_subtree) instead of O(N_all_nodes).
  // -------------------------------------------------------------------------
  if (!m_dirtyBoundaryIds.empty())
  {
    for (uint32_t boundaryId : m_dirtyBoundaryIds)
    {
      auto it = m_nodesById.find(boundaryId);
      if (it != m_nodesById.end())
      {
        reconcileBoundsForSubtree(it->second.get());
      }
    }
    m_dirtyBoundaryIds.clear();
    if (!m_dirtyBoundsNodes.empty())
    {
      boundsDirty = true;
    }
  }

  // Early exit if nothing is dirty after reconciliation.
  if (!structureDirty && !boundsDirty && !contentDirty)
  {
    return;
  }

  // -------------------------------------------------------------------------
  // Visual-order check.
  //
  // Screen-reader traversal order is visual (top-to-bottom, left-to-right).
  // If a node's bounds changed, its parent's children may have moved past
  // each other and need re-sorting via the full re-flatten path.
  //
  // Only relevant on the incremental path: the full re-flatten always
  // re-sorts children from scratch. Only checks at parents whose direct
  // children actually had a bounds change — parents with no dirty child
  // can't have reordered.
  // -------------------------------------------------------------------------
  bool needsReorder = false;
  if (boundsDirty && !structureDirty && !m_lastFlatSnapshot.empty())
  {
    std::unordered_set<SemanticNode*> parentsToCheck;
    bool anyRootMoved = false;

    for (uint32_t id : m_dirtyBoundsNodes)
    {
      auto it = m_nodesById.find(id);
      if (it == m_nodesById.end())
      {
        continue;
      }
      SemanticNode* parent = it->second->parent();
      if (parent != nullptr)
      {
        parentsToCheck.insert(parent);
      }
      else
      {
        anyRootMoved = true;
      }
    }

    for (auto* parent : parentsToCheck)
    {
      if (parent->children().size() > 1 &&
          !childrenInVisualOrder(parent->children()))
      {
        needsReorder = true;
        break;
      }
    }
    if (!needsReorder && anyRootMoved && m_roots.size() > 1 &&
        !childrenInVisualOrder(m_roots))
    {
      needsReorder = true;
    }
  }

  // -------------------------------------------------------------------------
  // Diff production — two paths depending on what kind of dirt is present.
  // -------------------------------------------------------------------------

  // -------------------------------------------------------------------------
  // Check if any content-dirty node can invalidate the last derivation
  // pass. If so, escalate to a full re-flatten so derivation re-runs:
  //   - an absorbed child changed -> the parent's derived label is stale;
  //   - a node with a derived label changed -> an explicit label set at
  //     runtime must win over the stale derived one (and its children
  //     are no longer absorbed);
  //   - an interactive node's label is now empty -> an explicit label
  //     was cleared, so derivation may apply again.
  // The incremental path cannot handle any of these: patchContentNode
  // reuses m_derivedLabels/m_excludedIds from the previous flatten.
  // -------------------------------------------------------------------------
  bool needsRederivation = false;
  if (contentDirty)
  {
    for (const auto& id : m_dirtyContentNodes)
    {
      if (m_excludedIds.count(id) || m_derivedLabels.count(id))
      {
        needsRederivation = true;
        break;
      }
      auto it = m_nodesById.find(id);
      if (it != m_nodesById.end() && isInteractiveRole(it->second->role()) &&
          it->second->label().empty() && !it->second->children().empty())
      {
        needsRederivation = true;
        break;
      }
    }
  }

  if (structureDirty || needsRederivation || needsReorder ||
      m_lastFlatSnapshot.empty())
  {
    // FULL RE-FLATTEN PATH.
    // The tree topology changed (add/remove/reparent), an absorbed
    // child's content changed (needs re-derivation), children moved
    // past each other (needs re-sort), or this is the first frame.
    // Walk the entire SemanticNode tree to produce a new flat snapshot,
    // then diff it against the previous snapshot.
    //
    // Step 1: Sort children by visual position (bounds) — only needed
    //         when topology or ordering changed, not for rederivation.
    // Step 2: Derive labels for interactive nodes and build exclude set.
    // Step 3: Flatten with derivation applied.
    // Step 4: Diff against previous snapshot.
    if (structureDirty || needsReorder || m_lastFlatSnapshot.empty())
    {
      sortChildrenByVisualPosition(m_roots);
    }

    m_derivedLabels.clear();
    m_excludedIds.clear();
    deriveLabelForInteractiveNodes(m_roots, m_derivedLabels, m_excludedIds);

    auto currentFlat = flattenFromSemanticNodes(
        m_roots,
        m_lastFlatSnapshot.size(),
        m_excludedIds,
        m_derivedLabels);
    auto nextDiff = buildDiffFromFlats(
        currentFlat,
        m_lastFlatSnapshot,
        m_version + 1);
    if (!nextDiff.empty())
    {
      m_version++;
      m_lastDiff = std::move(nextDiff);
      m_lastFlatSnapshot = std::move(currentFlat);
      indexSnapshot();
    }
  }
  else
  {
    // INCREMENTAL PATCH PATH.
    // Only bounds and/or content changed — no structural changes.
    // Iterate m_lastFlatSnapshot, which is already in tree pre-order;
    // for each entry whose id is in the bounds- or content-dirty set,
    // patch the entry in place and emit a diff record. Iterating the
    // dirty sets directly would emit in hash-bucket order, which does
    // not track tree structure; consumers expect diff records in tree
    // pre-order, so the snapshot drives iteration and the sets are
    // used only for O(1) membership checks.
    //
    // This path skips the structural tree walk, child re-sort, label
    // re-derivation, and flat-vs-flat comparison that the full
    // re-flatten path performs.
    SemanticsDiff nextDiff;
    nextDiff.frameNumber = Artboard::frameId();

    if (boundsDirty || contentDirty)
    {
      if (boundsDirty)
      {
        nextDiff.updatedGeometry.reserve(m_dirtyBoundsNodes.size());
      }
      if (contentDirty)
      {
        nextDiff.updatedSemantic.reserve(m_dirtyContentNodes.size());
      }

      for (auto& entry : m_lastFlatSnapshot)
      {
        if (boundsDirty && m_dirtyBoundsNodes.count(entry.id))
        {
          patchBoundsNode(entry, nextDiff);
        }
        if (contentDirty && m_dirtyContentNodes.count(entry.id))
        {
          patchContentNode(entry, nextDiff);
        }
      }
    }

    // Single-root optimization for the incremental path: the root of the
    // snapshot this diff patches.
    nextDiff.rootId = m_rootId;

    // Only bump version and store the diff if something actually changed.
    // The patchBounds/patchContent methods guard against no-op updates,
    // so nextDiff can be empty even when dirty flags were set.
    if (!nextDiff.empty())
    {
      m_version++;
      nextDiff.treeVersion = m_version;
      m_lastDiff = std::move(nextDiff);
    }
  }

  // Clear all dirt flags and per-node dirty sets for the next frame.
  m_dirt = SemanticDirt::None;
  m_dirtyContentNodes.clear();
  m_dirtyBoundsNodes.clear();
}

SemanticsDiff SemanticManager::drainDiff()
{
  refresh();
  return consumeDiff();
}

uint32_t SemanticManager::rootId() const { return m_rootId; }

// Records which nodes the snapshot holds and its single root, if it has one.
// Called whenever m_lastFlatSnapshot is replaced.
void SemanticManager::indexSnapshot()
{
  m_snapshotIds.clear();
  m_rootId = 0;
  int roots = 0;
  for (const auto& node : m_lastFlatSnapshot)
  {
    m_snapshotIds.insert(node.id);
    if (node.parentId == -1)
    {
      m_rootId = node.id;
      roots++;
    }
  }
  if (roots != 1)
  {
    m_rootId = 0;
  }
}

bool SemanticManager::isInTree(const SemanticNode* node) const
{
  return node != nullptr && node->manager() == this &&
         m_snapshotIds.count(node->id()) != 0;
}

std::vector<SemanticsBoundsUpdate> SemanticManager::boundsSnapshot() const
{
  std::vector<SemanticsBoundsUpdate> bounds;
  bounds.reserve(m_lastFlatSnapshot.size());
  for (const auto& node : m_lastFlatSnapshot)
  {
    bounds.push_back({node.id, node.minX, node.minY, node.maxX, node.maxY});
  }
  return bounds;
}

// Returns the diff produced by the most recent refresh() and clears it.
// Subsequent calls return an empty diff until the next dirty refresh.
//
// The move + replace pattern ensures the caller gets ownership of the diff
// data and the manager's internal storage is reset to empty.
SemanticsDiff SemanticManager::consumeDiff()
{
  SemanticsDiff result = std::move(m_lastDiff);
  m_lastDiff = SemanticsDiff();
  return result;
}

bool SemanticManager::requestFocus(uint32_t semanticNodeId)
{
  auto* semanticNode = nodeById(semanticNodeId);
  if (semanticNode == nullptr || !isInTree(semanticNode))
  {
    return false;
  }
  auto* data = semanticNode->semanticData();
  return data != nullptr && data->requestFocus();
}