NodeGraph.cpp

// SPDX-License-Identifier: LGPL-3.0-or-later OR MIT

#include "codex/nodegraph/NodeGraph.h"

#include <algorithm>
#include <exception>
#include <functional>
#include <limits>
#include <stdexcept>
#include <unordered_set>

namespace codexui::nodegraph {
namespace {

template <typename Range, typename ValueType>
bool contains(const Range &range, const ValueType &value) {
  return std::find(range.begin(), range.end(), value) != range.end();
}

bool scalarTextNonEmpty(const Value *value) noexcept {
  if (const std::string *text = value ? value->asString() : nullptr)
    return !text->empty();
  return value && (value->isSigned() || value->isUnsigned());
}

std::string_view exactText(const Value *value) noexcept {
  const std::string *text = value ? value->asString() : nullptr;
  return text ? std::string_view(*text) : std::string_view{};
}

template <typename Range, typename ValueType>
void eraseValue(Range &range, const ValueType &value) {
  range.erase(std::remove(range.begin(), range.end(), value), range.end());
}

template <typename T, typename Projection, typename Equal = std::equal_to<>>
void sortUnique(std::vector<T> &values, Projection projection,
                Equal equal = {}) {
  std::ranges::sort(values, {}, projection);
  values.erase(std::unique(values.begin(), values.end(), equal), values.end());
}

NodeRef pin(Node *node) { return node ? node->shared_from_this() : NodeRef{}; }

void requireRelationTargetKind(RelationKind kind, const NodeRef &target) {
  if (kind == RelationKind::PendingOperation &&
      target->id().kind != NodeKind::Operation)
    throw std::invalid_argument(
        "PendingOperation relations require an Operation target");
  if (kind == RelationKind::PendingInteraction &&
      target->id().kind != NodeKind::Interaction)
    throw std::invalid_argument(
        "PendingInteraction relations require an Interaction target");
}

template <typename T>
void ensureAppendCapacity(std::vector<T> &values, std::size_t additional) {
  if (additional <= values.capacity() - values.size())
    return;
  const std::size_t required = values.size() + additional;
  const std::size_t grown =
      values.capacity() <= values.max_size() / 2
          ? std::max<std::size_t>(1, values.capacity() * 2)
          : values.max_size();
  values.reserve(std::max(required, grown));
}

} // namespace

std::size_t NodeIdHash::operator()(const NodeId &id) const noexcept {
  const std::size_t kind = static_cast<std::size_t>(id.kind);
  const std::size_t value = std::hash<std::string>{}(id.canonical);
  return value ^ (kind + 0x9e3779b9U + (value << 6U) + (value >> 2U));
}

std::string_view statusTextFromValue(const Value *value) {
  if (const Value::Object *object = value ? value->asObject() : nullptr) {
    const auto type = object->find("type");
    value = type == object->end() ? nullptr : &type->second;
  }
  const std::string *status = value ? value->asString() : nullptr;
  return status ? std::string_view(*status) : std::string_view{};
}

NodeStatus nodeStatusFromValue(const Value *value) {
  return nodeStatusFromText(statusTextFromValue(value));
}

NodeStatusView nodeStatusView(const NodeState &state) {
  const std::string_view raw = statusTextFromValue(valueMember(state, "status"));
  return {state.status, state.status == NodeStatus::Unknown ? raw
                                                           : std::string_view{}};
}

NodeStatusView nodeStatusView(const Value *value) {
  const std::string_view raw = statusTextFromValue(value);
  const NodeStatus status = nodeStatusFromText(raw);
  return {status, status == NodeStatus::Unknown ? raw : std::string_view{}};
}

NodeStatusView agentActivityStatus(const NodeState &state) {
  const NodeStatusView published = nodeStatusView(state);
  if (!published.empty())
    return published;
  const std::string kind = scalarTextFromValue(valueMember(state, "kind"));
  if (kind == "completed")
    return {NodeStatus::Completed, {}};
  if (kind == "interrupted")
    return {NodeStatus::Interrupted, {}};
  if (kind == "failed")
    return {NodeStatus::Failed, {}};
  if (kind == "started" || kind == "progress")
    return {NodeStatus::Running, {}};
  return {};
}

bool agentActivityCanCreate(const NodeState &state) {
  const std::string_view type = exactText(valueMember(state, "type"));
  if (type == "subAgentActivity") {
    const std::string_view kind = exactText(valueMember(state, "kind"));
    return kind.empty() || kind == "started";
  }
  if (type != "collabAgentToolCall")
    return false;
  const std::string_view tool = exactText(valueMember(state, "tool"));
  return tool == "spawn_agent" || tool == "spawnAgent" ||
         tool == "spawn_agents_on_csv" || tool == "spawnAgentsOnCsv";
}

InspectorPlanView inspectorPlanView(const NodeState &state) noexcept {
  const Value *plan = valueMember(state, "plan");
  const Value *steps = plan && plan->asArray() ? plan : nullptr;
  const Value *explanation = valueMember(state, "planExplanation");
  if (!scalarTextNonEmpty(explanation))
    explanation = nullptr;
  if (const auto *object = plan ? plan->asObject() : nullptr) {
    steps = valueMember(*object, "steps");
    if (!explanation) {
      const Value *nested = valueMember(*object, "explanation");
      if (scalarTextNonEmpty(nested))
        explanation = nested;
    }
  }
  if (!steps)
    return {};
  const auto *array = steps->asArray();
  std::size_t rows = array ? array->size() : 0;
  if (explanation && rows != std::numeric_limits<std::size_t>::max())
    ++rows;
  return {steps, explanation, rows};
}

const Value::Object *reportedAgentState(const NodeState &state,
                                        std::string_view childId) noexcept {
  const Value *value = valueMember(state, "agentsStates");
  const auto *states = value ? value->asObject() : nullptr;
  if (!states)
    return nullptr;
  const auto found = states->find(childId);
  return found == states->end() ? nullptr : found->second.asObject();
}

NodeStatusView inspectorAgentActivityStatus(const NodeState &state,
                                            const NodeState *turn,
                                            NodeStatusView child,
                                            bool childIdVisible) noexcept {
  NodeStatusView result = agentActivityStatus(state);
  const bool terminalTurn =
      turn && (turn->status == NodeStatus::Completed ||
               turn->status == NodeStatus::Failed ||
               turn->status == NodeStatus::Interrupted);
  if (childIdVisible && result.semantic == NodeStatus::Running &&
      terminalTurn && child.empty())
    return {NodeStatus::NotLoaded, {}};
  return result;
}

Node::Node(NodeId id, NodeState state, std::uint64_t insertionOrder)
    : id_(std::move(id)),
      state_(std::make_shared<const NodeState>(std::move(state))),
      insertionOrder_(insertionOrder) {}

const NodeId &Node::id() const noexcept { return id_; }

bool GraphChange::empty() const noexcept {
  return affected.empty() && removed.empty() && childListsChanged.empty() &&
         providerAuthorityRevision == 0;
}

NodeGraph::WriteAccess NodeGraph::write() {
  return WriteAccess(*this, std::unique_lock<std::shared_mutex>(mutex_));
}

std::optional<NodeGraph::ReadAccess> NodeGraph::tryRead() const {
  std::shared_lock<std::shared_mutex> lock(mutex_, std::try_to_lock);
  if (!lock.owns_lock())
    return std::nullopt;
  return ReadAccess(*this, std::move(lock));
}

std::uint64_t NodeGraph::publishedRevision() const noexcept {
  return publishedRevision_.load(std::memory_order_acquire);
}

std::uint64_t
NodeGraph::publishedStructureRevision(NodeKind kind) const noexcept {
  const std::size_t index = static_cast<std::size_t>(kind);
  if (index >= publishedStructureRevisions_.size())
    return 0;
  return publishedStructureRevisions_[index].load(std::memory_order_acquire);
}

NodeGraph::ReadAccess::ReadAccess(
    const NodeGraph &graph, std::shared_lock<std::shared_mutex> lock) noexcept
    : graph_(&graph), lock_(std::move(lock)) {}

std::uint64_t NodeGraph::ReadAccess::revision() const noexcept {
  return graph_->revision_;
}

std::uint64_t
NodeGraph::ReadAccess::structureRevision(NodeKind kind) const noexcept {
  const std::size_t index = static_cast<std::size_t>(kind);
  return index < graph_->structureRevisions_.size()
             ? graph_->structureRevisions_[index]
             : 0;
}

NodeRef NodeGraph::ReadAccess::find(const NodeId &id) const {
  const auto found = graph_->nodes_.find(id);
  return found == graph_->nodes_.end() ? NodeRef{} : found->second;
}

const std::vector<NodeRef> &
NodeGraph::ReadAccess::orderedNodes() const noexcept {
  return graph_->orderedNodes_;
}

const std::vector<NodeRef> &
NodeGraph::ReadAccess::orderedNodes(NodeKind kind) const noexcept {
  const std::size_t index = static_cast<std::size_t>(kind);
  static const std::vector<NodeRef> empty;
  return index < graph_->orderedNodesByKind_.size()
             ? graph_->orderedNodesByKind_[index]
             : empty;
}

std::size_t NodeGraph::ReadAccess::retiredCount() const noexcept {
  return graph_->retiredNodes_.size();
}

NodeRef NodeGraph::ReadAccess::retiredAt(std::size_t index) const {
  return index < graph_->retiredNodes_.size() ? graph_->retiredNodes_[index]
                                              : NodeRef{};
}

std::uint64_t NodeGraph::ReadAccess::retiredOrderGeneration() const noexcept {
  return graph_->retiredOrderGeneration_;
}

std::uint64_t
NodeGraph::ReadAccess::pendingInteractionOrderRevision() const noexcept {
  return graph_->pendingInteractionOrderRevision_;
}

bool NodeGraph::ReadAccess::live(const NodeRef &node) const noexcept {
  if (!node)
    return false;
  const auto active = graph_->nodes_.find(node->id_);
  return active != graph_->nodes_.end() && active->second == node;
}

bool NodeGraph::ReadAccess::contains(const NodeRef &node) const noexcept {
  if (live(node))
    return true;
  if (!node)
    return false;
  const std::size_t index = node->parentIndex_.load(std::memory_order_relaxed);
  return index < graph_->retiredNodes_.size() &&
         graph_->retiredNodes_[index] == node;
}

std::shared_ptr<const NodeState>
NodeGraph::ReadAccess::state(const NodeRef &node) const {
  if (!node)
    return {};
  requireMember(node);
  return node->state_;
}

std::uint64_t
NodeGraph::ReadAccess::changedRevision(const NodeRef &node) const {
  if (!node)
    return 0;
  requireMember(node);
  return node->changedRevision_;
}

std::uint64_t
NodeGraph::ReadAccess::fieldChangedRevision(const NodeRef &node,
                                            std::string_view field) const {
  if (!node)
    return 0;
  requireMember(node);
  const auto found = node->fieldChangedRevisions_.find(std::string(field));
  return found == node->fieldChangedRevisions_.end() ? 0 : found->second;
}

bool NodeGraph::ReadAccess::fieldsChangedAt(const NodeRef &node,
                                            std::uint64_t revision) const {
  if (!node)
    return false;
  requireMember(node);
  return std::ranges::any_of(node->fieldChangedRevisions_,
                             [revision](const auto &field) {
                               return field.second == revision;
                             });
}

std::uint64_t
NodeGraph::ReadAccess::statusChangedRevision(const NodeRef &node) const {
  if (!node)
    return 0;
  requireMember(node);
  return node->statusChangedRevision_;
}

std::uint64_t
NodeGraph::ReadAccess::structureChangedRevision(const NodeRef &node) const {
  if (!node)
    return 0;
  requireMember(node);
  return node->structureChangedRevision_;
}

NodeRef NodeGraph::ReadAccess::parent(const NodeRef &node) const {
  if (!node)
    return {};
  requireMember(node);
  return pin(node->parent_);
}

std::optional<std::size_t>
NodeGraph::ReadAccess::childIndex(const NodeRef &node) const {
  if (!node)
    return std::nullopt;
  requireMember(node);
  const std::size_t index = node->parentIndex_.load(std::memory_order_relaxed);
  if (!node->parent_ || index >= node->parent_->children_.size() ||
      node->parent_->children_[index] != node.get())
    return std::nullopt;
  return index;
}

std::size_t NodeGraph::ReadAccess::childCount(const NodeRef &node) const {
  if (!node)
    return 0;
  requireMember(node);
  return node->children_.size();
}

NodeRef NodeGraph::ReadAccess::childAt(const NodeRef &node,
                                       std::size_t index) const {
  if (!node)
    return {};
  requireMember(node);
  return index < node->children_.size() ? pin(node->children_[index])
                                        : NodeRef{};
}

std::vector<NodeRef>
NodeGraph::ReadAccess::children(const NodeRef &node) const {
  std::vector<NodeRef> result;
  if (!node)
    return result;
  requireMember(node);
  result.reserve(node->children_.size());
  for (Node *child : node->children_)
    result.emplace_back(pin(child));
  return result;
}

std::size_t NodeGraph::ReadAccess::relatedCount(const NodeRef &node,
                                                RelationKind kind) const {
  if (!node)
    return 0;
  requireMember(node);
  const auto found = node->relations_.find(kind);
  return found == node->relations_.end() ? 0 : found->second.size();
}

NodeRef NodeGraph::ReadAccess::relatedAt(const NodeRef &node, RelationKind kind,
                                         std::size_t index) const {
  if (!node)
    return {};
  requireMember(node);
  const auto found = node->relations_.find(kind);
  if (found == node->relations_.end() || index >= found->second.size())
    return {};
  return pin(found->second[index]);
}

bool NodeGraph::ReadAccess::isRelated(const NodeRef &source,
                                      RelationKind kind,
                                      const NodeRef &target) const {
  if (!source || !target)
    return false;
  requireMember(source);
  requireMember(target);
  return std::ranges::find(target->incomingRelations_,
                           std::pair{source.get(), kind}) !=
         target->incomingRelations_.end();
}

bool NodeGraph::ReadAccess::hasIncomingRelation(const NodeRef &target,
                                                RelationKind kind) const {
  if (!target)
    return false;
  requireMember(target);
  return std::ranges::any_of(
      target->incomingRelations_,
      [kind](const auto &relation) { return relation.second == kind; });
}

std::vector<NodeRef> NodeGraph::ReadAccess::related(const NodeRef &node,
                                                    RelationKind kind) const {
  std::vector<NodeRef> result;
  if (!node)
    return result;
  requireMember(node);
  const auto found = node->relations_.find(kind);
  if (found == node->relations_.end())
    return result;
  result.reserve(found->second.size());
  for (Node *target : found->second)
    result.emplace_back(pin(target));
  return result;
}

const InspectorThreadIndex *
NodeGraph::ReadAccess::inspectorIndex(const NodeRef &thread) const {
  if (!thread)
    return nullptr;
  requireMember(thread);
  const auto found = graph_->inspectorIndexes_.find(thread.get());
  return found == graph_->inspectorIndexes_.end() ? nullptr : &found->second;
}

void NodeGraph::ReadAccess::requireMember(const NodeRef &node) const {
  if (contains(node))
    return;
  throw std::invalid_argument("node does not belong to this graph");
}

NodeGraph::WriteAccess::WriteAccess(
    NodeGraph &graph, std::unique_lock<std::shared_mutex> lock) noexcept
    : graph_(&graph), lock_(std::move(lock)) {}

NodeGraph::WriteAccess::WriteAccess(WriteAccess &&other) noexcept
    : graph_(std::exchange(other.graph_, nullptr)),
      lock_(std::move(other.lock_)), affected_(std::move(other.affected_)),
      affectedIndex_(std::move(other.affectedIndex_)),
      revisionTouches_(std::move(other.revisionTouches_)),
      revisionTouchIndex_(std::move(other.revisionTouchIndex_)),
      pendingStateRevisions_(std::move(other.pendingStateRevisions_)),
      pendingStructureRevisions_(std::move(other.pendingStructureRevisions_)),
      childListsChanged_(std::move(other.childListsChanged_)),
      childListsChangedIndex_(std::move(other.childListsChangedIndex_)),
      inspectorImpacts_(std::move(other.inspectorImpacts_)),
      removed_(std::move(other.removed_)),
      pendingInteractionOrderChanged_(other.pendingInteractionOrderChanged_),
      dirty_(other.dirty_),
      finished_(other.finished_) {
  other.pendingInteractionOrderChanged_ = false;
  other.dirty_ = false;
  other.finished_ = true;
}

NodeGraph::WriteAccess::~WriteAccess() {
  if (graph_ && lock_.owns_lock() && !finished_ && dirty_)
    std::terminate();
}

std::uint64_t NodeGraph::WriteAccess::revision() const noexcept {
  return graph_ ? graph_->revision_ : 0;
}

NodeRef NodeGraph::WriteAccess::find(const NodeId &id) const {
  const auto found = graph_->nodes_.find(id);
  return found == graph_->nodes_.end() ? NodeRef{} : found->second;
}

const std::vector<NodeRef> &
NodeGraph::WriteAccess::orderedNodes() const noexcept {
  return graph_->orderedNodes_;
}

std::uint64_t
NodeGraph::WriteAccess::changedRevision(const NodeRef &node) const {
  requireLive(node);
  return node->changedRevision_;
}

std::uint64_t
NodeGraph::WriteAccess::fieldChangedRevision(const NodeRef &node,
                                             std::string_view field) const {
  requireLive(node);
  const auto found = node->fieldChangedRevisions_.find(std::string(field));
  return found == node->fieldChangedRevisions_.end() ? 0 : found->second;
}

std::uint64_t
NodeGraph::WriteAccess::statusChangedRevision(const NodeRef &node) const {
  requireLive(node);
  return node->statusChangedRevision_;
}

std::uint64_t
NodeGraph::WriteAccess::structureChangedRevision(const NodeRef &node) const {
  requireLive(node);
  return node->structureChangedRevision_;
}

bool NodeGraph::WriteAccess::hasPendingChanges() const noexcept {
  return dirty_;
}

NodeRef NodeGraph::WriteAccess::upsert(NodeId id, NodeState initial) {
  if (NodeRef existing = find(id))
    return existing;
  NodeRef node(
      new Node(std::move(id), std::move(initial), graph_->nextInsertionOrder_));
  PendingStateRevision pending;
  pending.status = node->state_->status != NodeStatus::Unknown;
  for (const auto &[field, value] : node->state_->fields) {
    static_cast<void>(value);
    pending.fields.insert(field);
    node->fieldChangedRevisions_.emplace(field, 0);
  }

  // Allocate every auxiliary slot first. If canonical insertion then fails,
  // roll these transaction-local entries back before propagating the error.
  graph_->nodes_.reserve(graph_->nodes_.size() + 1);
  ensureAppendCapacity(graph_->orderedNodes_, 1);
  const std::size_t kindIndex = static_cast<std::size_t>(node->id_.kind);
  if (kindIndex >= graph_->orderedNodesByKind_.size())
    throw std::invalid_argument("node kind is outside the graph index");
  ensureAppendCapacity(graph_->orderedNodesByKind_[kindIndex], 1);
  pendingStateRevisions_.reserve(pendingStateRevisions_.size() + 1);
  affectedIndex_.reserve(affectedIndex_.size() + 1);
  ensureAppendCapacity(affected_, 1);
  pendingStateRevisions_.emplace(node.get(), std::move(pending));
  try {
    affectedIndex_.insert(node.get());
    try {
      affected_.emplace_back(node);
    } catch (...) {
      affectedIndex_.erase(node.get());
      throw;
    }
    try {
      graph_->nodes_.emplace(node->id_, node);
    } catch (...) {
      affected_.pop_back();
      affectedIndex_.erase(node.get());
      pendingStateRevisions_.erase(node.get());
      throw;
    }
  } catch (...) {
    pendingStateRevisions_.erase(node.get());
    throw;
  }
  graph_->orderedNodes_.emplace_back(node);
  graph_->orderedNodesByKind_[kindIndex].emplace_back(node);
  ++graph_->nextInsertionOrder_;
  dirty_ = true;
  return node;
}

std::shared_ptr<const NodeState>
NodeGraph::WriteAccess::state(const NodeRef &node) const {
  requireLive(node);
  return node->state_;
}

NodeRef NodeGraph::WriteAccess::parent(const NodeRef &node) const {
  requireLive(node);
  return pin(node->parent_);
}

std::vector<NodeRef>
NodeGraph::WriteAccess::children(const NodeRef &node) const {
  requireLive(node);
  std::vector<NodeRef> result;
  result.reserve(node->children_.size());
  for (Node *child : node->children_)
    result.emplace_back(pin(child));
  return result;
}

std::vector<NodeRef> NodeGraph::WriteAccess::related(const NodeRef &node,
                                                     RelationKind kind) const {
  requireLive(node);
  std::vector<NodeRef> result;
  const auto found = node->relations_.find(kind);
  if (found == node->relations_.end())
    return result;
  result.reserve(found->second.size());
  for (Node *target : found->second)
    result.emplace_back(pin(target));
  return result;
}

void NodeGraph::WriteAccess::replaceState(const NodeRef &node,
                                          NodeState state) {
  requireLive(node);
  if (*node->state_ == state)
    return;
  const NodeState &before = *node->state_;
  std::shared_ptr<const NodeState> storage =
      std::make_shared<const NodeState>(std::move(state));
  const NodeState &after = *storage;
  if (node->id_.kind == NodeKind::Interaction &&
      after.status != NodeStatus::Pending && after.status != NodeStatus::Failed &&
      std::ranges::any_of(node->incomingRelations_, [](const auto &edge) {
        return edge.second == RelationKind::PendingInteraction;
      }))
    throw std::invalid_argument(
        "a pending Interaction must be unlinked before it becomes terminal");

  const auto pendingPosition = pendingStateRevisions_.find(node.get());
  const bool hadPending = pendingPosition != pendingStateRevisions_.end();
  PendingStateRevision pending =
      hadPending ? pendingPosition->second : PendingStateRevision{};
  pending.status = pending.status || before.status != after.status;
  for (const auto &[field, value] : before.fields) {
    const auto found = after.fields.find(field);
    if (found == after.fields.end() || found->second != value)
      pending.fields.insert(field);
  }
  for (const auto &[field, value] : after.fields) {
    const auto found = before.fields.find(field);
    if (found == before.fields.end() || found->second != value)
      pending.fields.insert(field);
  }
  auto fieldRevisions = node->fieldChangedRevisions_;
  for (const std::string &field : pending.fields)
    fieldRevisions.try_emplace(field, 0);

  if (hadPending) {
    std::swap(pendingPosition->second, pending);
  } else {
    pendingStateRevisions_.emplace(node.get(), std::move(pending));
  }
  const std::array affected{node};
  try {
    prepareChanges(affected, {});
  } catch (...) {
    if (hadPending)
      std::swap(pendingPosition->second, pending);
    else
      pendingStateRevisions_.erase(node.get());
    throw;
  }
  node->fieldChangedRevisions_.swap(fieldRevisions);
  node->state_ = std::move(storage);
}

void NodeGraph::WriteAccess::setField(const NodeRef &node, std::string key,
                                      Value value) {
  requireLive(node);
  const auto found = node->state_->fields.find(key);
  if (found != node->state_->fields.end() && found->second == value)
    return;
  NodeState next = *node->state_;
  next.fields.insert_or_assign(std::move(key), std::move(value));
  replaceState(node, std::move(next));
}

void NodeGraph::WriteAccess::eraseField(const NodeRef &node,
                                        std::string_view key) {
  requireLive(node);
  if (!node->state_->fields.contains(key))
    return;
  NodeState next = *node->state_;
  next.fields.erase(std::string(key));
  replaceState(node, std::move(next));
}

void NodeGraph::WriteAccess::setStatus(const NodeRef &node, NodeStatus status) {
  requireLive(node);
  if (node->state_->status == status)
    return;
  NodeState next = *node->state_;
  next.status = status;
  replaceState(node, std::move(next));
}

void NodeGraph::WriteAccess::touchRevision(const NodeRef &node) {
  requireLive(node);
  if (affectedIndex_.contains(node.get()))
    return;
  const auto [position, inserted] = revisionTouchIndex_.insert(node.get());
  if (!inserted)
    return;
  try {
    revisionTouches_.emplace_back(node);
  } catch (...) {
    revisionTouchIndex_.erase(position);
    throw;
  }
}

Node *NodeGraph::WriteAccess::inspectorThread(Node *node) const noexcept {
  while (node && node->id_.kind != NodeKind::Thread)
    node = node->parent_;
  return node;
}

std::uint8_t NodeGraph::WriteAccess::inspectorItemSections(Node *item) const {
  if (!item || item->id_.kind != NodeKind::Item)
    return 0;
  const std::string type =
      scalarTextFromValue(valueMember(*item->state_, "type"));
  std::uint8_t sections = type == "plan" ? 1 : 0;
  if (type == "subAgentActivity" || type == "collabAgentToolCall" ||
      type == "agentMessage")
    sections |= 2;
  return sections;
}

std::uint8_t NodeGraph::WriteAccess::inspectorTurnSections(Node *turn) const {
  if (!turn || turn->id_.kind != NodeKind::Turn)
    return 0;
  std::uint8_t sections = inspectorPlanView(*turn->state_) ? 1 : 0;
  for (Node *item : turn->children_)
    sections |= inspectorItemSections(item);
  return sections;
}

std::uint8_t NodeGraph::WriteAccess::inspectorIndexedSections(
    Node *thread, Node *node) const {
  const auto indexed = graph_->inspectorIndexes_.find(thread);
  if (!node || indexed == graph_->inspectorIndexes_.end())
    return 0;
  const InspectorThreadIndex &index = indexed->second;
  std::uint8_t sections = index.planSource.get() == node ? 1 : 0;
  if (index.planSource && index.planSource->id_.kind == NodeKind::Item &&
      index.planSource->parent_ == node)
    sections |= 1;
  if (index.agentDependencies.contains(node) ||
      index.agentMessageOrder.contains(node))
    sections |= 2;
  return sections;
}

void NodeGraph::WriteAccess::markInspectorRebuild(Node *thread,
                                                   std::uint8_t sections) {
  if (!thread || thread->id_.kind != NodeKind::Thread || sections == 0)
    return;
  InspectorImpact &impact = inspectorImpacts_[thread];
  impact.rebuild |= sections;
  if (sections & 2)
    impact.append.reset();
}

bool NodeGraph::WriteAccess::markInspectorAppend(Node *thread, Node *turn,
                                                 std::size_t first) {
  if (!thread || !turn || thread->id_.kind != NodeKind::Thread)
    return false;
  const auto lastTurn = std::ranges::find_if(
      thread->children_.rbegin(), thread->children_.rend(),
      [](Node *node) { return node->id_.kind == NodeKind::Turn; });
  if (lastTurn == thread->children_.rend() || *lastTurn != turn)
    return false;
  InspectorImpact &impact = inspectorImpacts_[thread];
  if (impact.rebuild & 2)
    return true;
  if (!impact.append) {
    impact.append = InspectorImpact::AgentAppend{turn, first};
  } else if (impact.append->turn == turn) {
    impact.append->first = std::min(impact.append->first, first);
  } else {
    impact.rebuild |= 2;
    impact.append.reset();
  }
  return true;
}

void NodeGraph::WriteAccess::noteInspectorChildChange(
    Node *parent, Node *child, std::optional<std::size_t> insertion) {
  if (!parent || !child)
    return;
  if (parent->id_.kind == NodeKind::Turn &&
      child->id_.kind == NodeKind::Item) {
    Node *thread = inspectorThread(parent);
    std::uint8_t sections = inspectorItemSections(child) |
                            inspectorIndexedSections(thread, child);
    if (insertion && child->changedRevision_ == 0 &&
        std::ranges::none_of(
            std::span(parent->children_).subspan(*insertion),
            [this](Node *node) { return inspectorItemSections(node) & 2U; }) &&
        markInspectorAppend(thread, parent, *insertion))
      sections &= static_cast<std::uint8_t>(~2U);
    markInspectorRebuild(thread, sections);
  } else if (parent->id_.kind == NodeKind::Thread &&
             child->id_.kind == NodeKind::Turn) {
    markInspectorRebuild(parent, inspectorTurnSections(child) |
                                     inspectorIndexedSections(parent, child));
  }
}

void NodeGraph::WriteAccess::noteInspectorChildrenReplacement(
    Node *parent, std::span<Node *const> previous,
    std::span<const NodeRef> next) {
  if (!parent)
    return;
  for (const NodeRef &child : next)
    if (child && child->parent_ && child->parent_ != parent)
      noteInspectorChildChange(child->parent_, child.get());

  bool appended = previous.size() <= next.size();
  for (std::size_t index = 0; appended && index < previous.size(); ++index)
    appended = previous[index] == next[index].get();
  for (std::size_t index = previous.size(); appended && index < next.size();
       ++index)
    appended = next[index]->changedRevision_ == 0 && !next[index]->parent_;

  std::uint8_t sections = 0;
  if (parent->id_.kind == NodeKind::Turn) {
    Node *thread = inspectorThread(parent);
    const std::size_t first = appended ? previous.size() : 0;
    if (appended) {
      for (std::size_t index = first; index < next.size(); ++index)
        sections |= inspectorItemSections(next[index].get());
    } else {
      for (Node *child : previous)
        sections |= inspectorItemSections(child) |
                    inspectorIndexedSections(thread, child);
      for (const NodeRef &child : next)
        sections |= inspectorItemSections(child.get());
    }
    if (appended && first < next.size() &&
        markInspectorAppend(thread, parent, first))
      sections &= static_cast<std::uint8_t>(~2U);
    markInspectorRebuild(thread, sections);
  } else if (parent->id_.kind == NodeKind::Thread) {
    for (Node *child : previous)
      sections |= inspectorTurnSections(child) |
                  inspectorIndexedSections(parent, child);
    for (const NodeRef &child : next)
      sections |= inspectorTurnSections(child.get());
    markInspectorRebuild(parent, sections);
  }
}

void NodeGraph::WriteAccess::noteInspectorRelationChange(
    Node *source, RelationKind kind) {
  if (!source || source->id_.kind != NodeKind::Item ||
      kind != RelationKind::AgentChildThread || source->changedRevision_ == 0)
    return;
  markInspectorRebuild(inspectorThread(source), 2);
}

void NodeGraph::WriteAccess::setParent(const NodeRef &parent,
                                       const NodeRef &child,
                                       const NodeRef &before) {
  requireLive(parent);
  requireLive(child);
  if (parent == child)
    throw std::invalid_argument("a node cannot parent itself");
  for (Node *ancestor = parent.get(); ancestor; ancestor = ancestor->parent_) {
    if (ancestor == child.get())
      throw std::invalid_argument("a parent relation cannot form a cycle");
  }
  if (child->parent_ == parent.get())
    return;
  if (before) {
    requireLive(before);
    if (before->parent_ != parent.get())
      throw std::invalid_argument(
          "insertion sibling must belong to the parent");
  }
  parent->children_.reserve(parent->children_.size() + 1);
  NodeRef previousParent = pin(child->parent_);
  const std::size_t position =
      before ? before->parentIndex_.load(std::memory_order_relaxed)
             : parent->children_.size();
  noteInspectorChildChange(previousParent.get(), child.get());
  noteInspectorChildChange(parent.get(), child.get(), position);
  const std::array changed{parent, child, previousParent};
  const std::array childrenChanged{
      ChildListChange{parent, child->id().kind},
      ChildListChange{previousParent, child->id().kind}};
  prepareChanges(changed, changed, childrenChanged);
  if (previousParent) {
    eraseValue(previousParent->children_, child.get());
    for (std::size_t index = 0; index < previousParent->children_.size();
         ++index)
      previousParent->children_[index]->parentIndex_.store(
          index, std::memory_order_relaxed);
  }
  child->parent_ = parent.get();
  parent->children_.insert(parent->children_.begin() + position, child.get());
  for (std::size_t index = position; index < parent->children_.size(); ++index)
    parent->children_[index]->parentIndex_.store(index,
                                                 std::memory_order_relaxed);
}

void NodeGraph::WriteAccess::clearParent(const NodeRef &child) {
  requireLive(child);
  if (!child->parent_)
    return;
  NodeRef parent = pin(child->parent_);
  noteInspectorChildChange(parent.get(), child.get());
  const std::array changed{parent, child};
  const std::array childrenChanged{ChildListChange{parent, child->id().kind}};
  prepareChanges(changed, changed, childrenChanged);
  eraseValue(parent->children_, child.get());
  for (std::size_t index = 0; index < parent->children_.size(); ++index)
    parent->children_[index]->parentIndex_.store(index,
                                                 std::memory_order_relaxed);
  child->parent_ = nullptr;
  child->parentIndex_.store(0, std::memory_order_relaxed);
}

void NodeGraph::WriteAccess::replaceChildren(
    const NodeRef &parent, std::span<const NodeRef> children) {
  requireLive(parent);
  std::vector<NodeRef> next;
  next.reserve(children.size());
  std::unordered_set<const Node *> seen;
  seen.reserve(children.size());
  for (const NodeRef &child : children) {
    requireLive(child);
    if (parent == child)
      throw std::invalid_argument("a node cannot parent itself");
    for (Node *ancestor = parent.get(); ancestor;
         ancestor = ancestor->parent_) {
      if (ancestor == child.get())
        throw std::invalid_argument("a parent relation cannot form a cycle");
    }
    if (seen.insert(child.get()).second)
      next.emplace_back(child);
  }

  bool unchanged = parent->children_.size() == next.size();
  if (unchanged) {
    for (std::size_t index = 0; index < next.size(); ++index) {
      if (parent->children_[index] != next[index].get() ||
          next[index]->parent_ != parent.get()) {
        unchanged = false;
        break;
      }
    }
  }
  if (unchanged)
    return;

  const std::vector<Node *> previous = parent->children_;
  noteInspectorChildrenReplacement(parent.get(), previous, next);
  std::vector<NodeRef> affected{parent};
  std::vector<NodeRef> structureChanged{parent};
  std::array<std::vector<Node *>, NodeGraph::NodeKindCount> previousByKind;
  std::array<std::vector<Node *>, NodeGraph::NodeKindCount> nextByKind;
  for (Node *child : previous)
    previousByKind[static_cast<std::size_t>(child->id().kind)].push_back(child);
  for (const NodeRef &child : next)
    nextByKind[static_cast<std::size_t>(child->id().kind)].push_back(
        child.get());
  std::vector<ChildListChange> childrenChanged;
  for (std::size_t kind = 0; kind < NodeGraph::NodeKindCount; ++kind)
    if (previousByKind[kind] != nextByKind[kind])
      childrenChanged.push_back({parent, static_cast<NodeKind>(kind)});
  affected.reserve(1 + previous.size() + next.size() * 2);
  structureChanged.reserve(1 + previous.size() + next.size() * 2);
  childrenChanged.reserve(childrenChanged.size() + next.size());
  for (Node *oldChildPointer : previous) {
    if (!seen.contains(oldChildPointer)) {
      NodeRef oldChild = pin(oldChildPointer);
      affected.emplace_back(oldChild);
      structureChanged.emplace_back(std::move(oldChild));
    }
  }

  for (const NodeRef &child : next) {
    const bool parentChanged = child->parent_ != parent.get();
    if (child->parent_ && child->parent_ != parent.get()) {
      NodeRef previousParent = pin(child->parent_);
      affected.emplace_back(previousParent);
      structureChanged.emplace_back(previousParent);
      childrenChanged.push_back({std::move(previousParent), child->id().kind});
    }
    affected.emplace_back(child);
    if (parentChanged)
      structureChanged.emplace_back(child);
  }

  parent->children_.reserve(next.size());
  prepareChanges(affected, structureChanged, childrenChanged);