topology.h

#pragma once
 
#include <tess/core/assert.h>
#include <tess/core/config.h>
#include <tess/core/fail_fast.h>
#include <tess/core/shape.h>
#include <tess/core/tag_identity.h>
#include <tess/path/request.h>
#include <tess/storage/residency.h>
#include <tess/storage/world.h>
#include <tess/topology/movement_class.h>
#include <tess/topology/transition_model.h>
#include <tess/topology/transition_provider.h>
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <span>
#include <type_traits>
#include <vector>
 
namespace tess {
 
// RegionGraph is a class template on the world residency policy so a sparse
// graph is a distinct type from a dense one (no silent dense indexing). The
// AlwaysResident alias below keeps every existing dense call site unchanged.
template <typename Residency>
class RegionGraphT;
 
// Local region ids are 1-based: 0 is the invalid sentinel
// (`invalid_local_region`). A valid id maps to
// `LocalChunkTopology::regions()[value - 1]`; use
// `LocalChunkTopology::region(id)` for checked access.
struct LocalRegionId {
  std::uint32_t value = 0;
 
  friend constexpr bool operator==(LocalRegionId lhs,
                                   LocalRegionId rhs) noexcept = default;
};

inline constexpr LocalRegionId invalid_local_region{};
 
// Sentinel returned by RegionGraph::region_index for invalid or
// out-of-range region references.
inline constexpr std::uint32_t invalid_region_index =
    std::numeric_limits<std::uint32_t>::max();

enum class BoundaryFace : std::uint8_t {
  NegativeX,
  PositiveX,
  NegativeY,
  PositiveY,
  NegativeZ,
  PositiveZ,
  PositiveXNegativeY,
  NegativeXPositiveY,
};

enum class TopologyStatus : std::uint8_t {
  Built,
  InvalidChunk,
  MissingChunk,
};

struct LocalRegion {
  LocalRegionId id{};
  std::size_t tile_count = 0;
  Box3 bounds{};
  std::size_t boundary_exit_count = 0;
 
  friend constexpr bool operator==(const LocalRegion& lhs,
                                   const LocalRegion& rhs) noexcept = default;
};

struct LocalBoundaryExit {
  LocalRegionId region{};
  LocalTileId local_tile{};
  Coord3 coord{};
  BoundaryFace face = BoundaryFace::NegativeX;
  ChunkKey target_chunk{};
 
  friend constexpr bool operator==(const LocalBoundaryExit& lhs,
                                   const LocalBoundaryExit& rhs) noexcept =
      default;
};

struct RegionGraphBuildResult {
  std::size_t region_count = 0;
  std::size_t passable_tile_count = 0;
  std::size_t boundary_exit_count = 0;
  std::uint64_t topology_version_sum = 0;
};

struct TopologyBuildResult {
  TopologyStatus status = TopologyStatus::Built;
  std::size_t region_count = 0;
  std::size_t passable_tile_count = 0;
  std::size_t boundary_exit_count = 0;
  std::uint64_t topology_version_sum = 0;
};

struct RegionRef {
  ChunkKey chunk{};
  LocalRegionId region{};
 
  friend constexpr bool operator==(RegionRef lhs,
                                   RegionRef rhs) noexcept = default;
};

struct RegionPortal {
  RegionRef from{};
  RegionRef to{};
  Coord3 from_coord{};
  Coord3 to_coord{};
  BoundaryFace face = BoundaryFace::NegativeX;
 
  friend constexpr bool operator==(const RegionPortal& lhs,
                                   const RegionPortal& rhs) noexcept = default;
};

enum class ReachabilityStatus : std::uint8_t {
  Reachable,
  Unreachable,
  InvalidStart,
  InvalidGoal,
  // The query reached the edge of the resident set: a region on the searched
  // side has a boundary exit into a non-resident chunk, so a route through the
  // non-resident region cannot be ruled out. Distinct from Unreachable, which
  // means a route was definitively searched and none exists within the resident
  // set. Only ever returned for sparse worlds. Appended last so existing
  // enumerator values do not shift.
  Indeterminate,
};

struct ReachabilityResult {
  ReachabilityStatus status = ReachabilityStatus::Unreachable;
  std::size_t visited_regions = 0;
};

struct CoarsePathResult {
  ReachabilityStatus status = ReachabilityStatus::Unreachable;
  std::size_t visited_regions = 0;
  std::span<const RegionRef> regions;
  std::span<const RegionPortal> portals;
  std::span<const ChunkKey> chunks;
  Box3 bounds{};
};

class LocalTopologyScratch {
 public:
  void reserve_tiles(std::size_t count) { stack_.reserve(count); }
 
  [[nodiscard]] auto capacity() const noexcept -> std::size_t {
    return stack_.capacity();
  }
 
 private:
  template <typename World, typename PassableTag>
  friend auto build_local_chunk_topology(const World& world, ChunkKey chunk,
                                         LocalTopologyScratch& scratch,
                                         class LocalChunkTopology& topology)
      -> TopologyBuildResult;
 
  std::vector<LocalTileId> stack_;
};

class RegionGraphScratch {
 public:
  void reserve_regions(std::size_t count) {
    frontier_.reserve(count);
    visited_epoch_.reserve(count);
    parent_.reserve(count);
    parent_portal_.reserve(count);
    path_regions_.reserve(count);
    path_portals_.reserve(count);
    corridor_chunks_.reserve(count);
  }
 
  [[nodiscard]] auto capacity() const noexcept -> std::size_t {
    return frontier_.capacity();
  }
 
 private:
  template <typename Shape, typename Residency>
  friend auto reachable(const RegionGraphT<Residency>& graph,
                        PathRequest request, RegionGraphScratch& scratch)
      -> ReachabilityResult;
 
  template <typename Shape, typename Residency>
  friend auto coarse_path(const RegionGraphT<Residency>& graph,
                          PathRequest request, RegionGraphScratch& scratch)
      -> CoarsePathResult;
 
  // Epoch-stamped visited marks: a region index is visited when its
  // generation stamp matches the current epoch, so traversals reset in
  // O(1) instead of clearing the whole vector.
  void begin_traversal(std::size_t region_count) {
    frontier_.clear();
    path_regions_.clear();
    path_portals_.clear();
    corridor_chunks_.clear();
    if (visited_epoch_.size() < region_count) {
      visited_epoch_.resize(region_count, 0);
    }
    ++epoch_;
    if (epoch_ == 0) {
      std::fill(visited_epoch_.begin(), visited_epoch_.end(), 0);
      epoch_ = 1;
    }
  }
 
  [[nodiscard]] auto is_visited(std::uint32_t region_index) const noexcept
      -> bool {
    return visited_epoch_[static_cast<std::size_t>(region_index)] == epoch_;
  }
 
  void visit(std::uint32_t region_index) noexcept {
    visited_epoch_[static_cast<std::size_t>(region_index)] = epoch_;
  }
 
  std::vector<std::uint32_t> frontier_;
  std::vector<std::uint32_t> visited_epoch_;
  std::vector<std::uint32_t> parent_;
  std::vector<std::uint32_t> parent_portal_;
  std::vector<RegionRef> path_regions_;
  std::vector<RegionPortal> path_portals_;
  std::vector<ChunkKey> corridor_chunks_;
  std::uint32_t epoch_ = 0;
};

class LocalChunkTopology {
 public:
  void clear() noexcept {
    chunk_ = ChunkKey{0};
    chunk_coord_ = ChunkCoord3{};
    topology_version_ = {};
    region_ids_.clear();
    regions_.clear();
    boundary_exits_.clear();
  }
 
  [[nodiscard]] auto chunk() const noexcept -> ChunkKey { return chunk_; }
 
  [[nodiscard]] auto chunk_coord() const noexcept -> ChunkCoord3 {
    return chunk_coord_;
  }
 
  [[nodiscard]] auto topology_version() const noexcept -> TopologyVersion {
    return topology_version_;
  }
 
  [[nodiscard]] auto region_ids() const noexcept
      -> std::span<const LocalRegionId> {
    return {region_ids_.data(), region_ids_.size()};
  }
 
  [[nodiscard]] auto regions() const noexcept -> std::span<const LocalRegion> {
    return {regions_.data(), regions_.size()};
  }
 
  // Checked accessor for the 1-based LocalRegionId convention: id N maps to
  // regions()[N - 1]. Returns nullptr for the invalid sentinel and for
  // out-of-range ids.
  [[nodiscard]] auto region(LocalRegionId id) const noexcept
      -> const LocalRegion* {
    if (id.value == 0 || id.value > regions_.size()) {
      return nullptr;
    }
    return &regions_[static_cast<std::size_t>(id.value) - 1];
  }
 
  [[nodiscard]] auto boundary_exits() const noexcept
      -> std::span<const LocalBoundaryExit> {
    return {boundary_exits_.data(), boundary_exits_.size()};
  }
 
  [[nodiscard]] auto region_at(LocalTileId tile) const noexcept
      -> LocalRegionId {
    if (tile.value >= region_ids_.size()) {
      return invalid_local_region;
    }
    return region_ids_[static_cast<std::size_t>(tile.value)];
  }
 
  template <typename Shape>
  [[nodiscard]] auto region_at(LocalCoord3 coord) const noexcept
      -> LocalRegionId {
    return region_at(local_tile_id<Shape>(coord));
  }
 
 private:
  template <typename World, typename PassableTag>
  friend auto build_local_chunk_topology(const World& world, ChunkKey chunk,
                                         LocalTopologyScratch& scratch,
                                         LocalChunkTopology& topology)
      -> TopologyBuildResult;
 
  ChunkKey chunk_{};
  ChunkCoord3 chunk_coord_{};
  TopologyVersion topology_version_{};
  std::vector<LocalRegionId> region_ids_;
  std::vector<LocalRegion> regions_;
  std::vector<LocalBoundaryExit> boundary_exits_;
};
 
namespace detail {
 
// Sparse-only companion state for RegionGraphT. Empty (via the explicit
// AlwaysResident specialization) so a dense graph carries zero extra storage
// through the [[no_unique_address]] member.
template <typename Residency>
struct RegionGraphSparseData {
  // Frozen at build, sorted ascending by ChunkKey.value: the resident chunk set
  // this graph was built over. Resolves ChunkKey -> local index by lower_bound,
  // world-free, so eviction after the build cannot invalidate the graph.
  std::vector<ChunkKey> topology_keys_;
  // One flag per global region: the region has a boundary exit into a chunk
  // that was non-resident at build time (a route through it cannot be ruled
  // out).
  std::vector<std::uint8_t> region_reaches_missing_;
  // Per local topology: the residency generation at build, for staleness
  // detection in update_region_graph.
  std::vector<ResidencyGeneration> frozen_generations_;
};
 
template <>
struct RegionGraphSparseData<AlwaysResident> {};
 
// Whether a provider transition emitted for `chunk` really originates there,
// as the TransitionProvider contract requires. Shared so every enumeration
// of a provider rejects a contract violation identically: the portal pass
// dropping a misowned edge while the sparse missing-reach pass still honored
// it would report Indeterminate where the other reports Unreachable.
template <typename Shape>
[[nodiscard]] constexpr bool provider_source_is_owned(Coord3 from,
                                                      ChunkKey chunk) noexcept {
  return contains<Shape>(from) &&
         chunk_key<Shape>(chunk_coord<Shape>(from)).value == chunk.value;
}
 
}  // namespace detail

template <typename Residency>
class RegionGraphT {
 public:
  void clear() noexcept {
    local_topologies_.clear();
    portals_.clear();
    region_offsets_.clear();
    adjacency_starts_.clear();
    adjacency_targets_.clear();
    adjacency_portals_.clear();
    built_chunk_grid_ = Extent3{0, 0, 0};
    built_chunk_extent_ = Extent3{0, 0, 0};
    built_lattice_identity_ = 0;
    built_lattice_version_ = 0;
    built_class_ = 0;
    built_step_policy_identity_ = 0;
    built_cost_scale_ = 0;
    built_provider_ = 0;
    built_provider_instance_ = nullptr;
    built_provider_revision_ = 0;
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      sparse_.topology_keys_.clear();
      sparse_.region_reaches_missing_.clear();
      sparse_.frozen_generations_.clear();
    }
    bump_revision();
  }
 
  [[nodiscard]] auto local_topologies() const noexcept
      -> std::span<const LocalChunkTopology> {
    return {local_topologies_.data(), local_topologies_.size()};
  }
 
  [[nodiscard]] auto portals() const noexcept -> std::span<const RegionPortal> {
    return {portals_.data(), portals_.size()};
  }

  [[nodiscard]] auto revision() const noexcept -> std::uint64_t {
    return revision_;
  }
 
  [[nodiscard]] auto local_topology(ChunkKey chunk) const noexcept
      -> const LocalChunkTopology* {
    if constexpr (std::is_same_v<Residency, AlwaysResident>) {
      if (chunk.value >= local_topologies_.size()) {
        return nullptr;
      }
      return &local_topologies_[static_cast<std::size_t>(chunk.value)];
    } else {
      const auto idx = local_index(chunk);
      if (idx == npos) {
        return nullptr;
      }
      return &local_topologies_[idx];
    }
  }
 
  template <typename Shape>
  [[nodiscard]] auto region_of(Coord3 coord) const noexcept -> RegionRef {
    if (!contains<Shape>(coord)) {
      return RegionRef{ChunkKey{std::numeric_limits<std::uint64_t>::max()},
                       invalid_local_region};
    }
    const auto key = chunk_key<Shape>(chunk_coord<Shape>(coord));
    const auto* local = local_topology(key);
    if (local == nullptr) {
      return RegionRef{key, invalid_local_region};
    }
    return RegionRef{
        key, local->region_at(local_tile_id<Shape>(local_coord<Shape>(coord)))};
  }
 
  // Total region count across all chunks in the dense global region index.
  [[nodiscard]] auto region_count() const noexcept -> std::uint32_t {
    return region_offsets_.empty() ? 0U : region_offsets_.back();
  }
 
  // Maps a region reference to its dense global index:
  // region_offsets_[chunk] + (1-based local id - 1). Returns
  // invalid_region_index for invalid or out-of-range references. The chunk
  // guard compares without +1 (the sentinel ChunkKey region_of returns for
  // out-of-world coordinates would wrap past it) and the offset arithmetic
  // is 64-bit (a region id near 2^32 would wrap back into a valid index).
  [[nodiscard]] auto region_index(RegionRef ref) const noexcept
      -> std::uint32_t {
    if constexpr (std::is_same_v<Residency, AlwaysResident>) {
      if (ref.region == invalid_local_region ||
          ref.chunk.value >= local_topologies_.size()) {
        return invalid_region_index;
      }
      const auto chunk = static_cast<std::size_t>(ref.chunk.value);
      const auto index = static_cast<std::uint64_t>(region_offsets_[chunk]) +
                         ref.region.value - 1;
      if (index >= region_offsets_[chunk + 1]) {
        return invalid_region_index;
      }
      return static_cast<std::uint32_t>(index);
    } else {
      if (ref.region == invalid_local_region) {
        return invalid_region_index;
      }
      const auto li = local_index(ref.chunk);
      if (li == npos || li + 1 >= region_offsets_.size()) {
        return invalid_region_index;
      }
      const auto index = static_cast<std::uint64_t>(region_offsets_[li]) +
                         ref.region.value - 1;
      if (index >= region_offsets_[li + 1]) {
        return invalid_region_index;
      }
      return static_cast<std::uint32_t>(index);
    }
  }
 
  // True iff this graph was built for `ClassOrTag` (normalized, so a raw tag
  // and its UnitCostFieldMovement identity agree). The graph type does not
  // encode the movement class, so a graph labeled for one class must never
  // answer reachability for another: update_region_graph treats a mismatch as
  // "not built for this class" (full rebuild) and is_region_graph_fresh_for
  // reports it as not fresh. False until the first build.
  template <typename ClassOrTag>
  [[nodiscard]] auto matches_class() const noexcept -> bool {
    using Class = movement::movement_class_of<ClassOrTag>;
    using Policy = movement::step_policy_of<Class>;
    return built_class_ == detail::tag_identity<Class>() &&
           built_step_policy_identity_ ==
               static_cast<std::uint32_t>(Policy::identity) &&
           built_cost_scale_ == Policy::cost_scale;
  }
 
  // True iff this graph was built with transition provider `Provider`
  // (AdjacentTransitions for the providerless overloads). Mirrors the class
  // stamp: update_region_graph with a different provider type falls back to
  // a full rebuild rather than patching with mismatched special-transition
  // edges. False until the first build.
  template <typename Provider>
  [[nodiscard]] auto matches_provider() const noexcept -> bool {
    return built_provider_ == detail::tag_identity<Provider>();
  }
 
  // Instance-aware provider match used by incremental updates. The address
  // distinguishes two live stateful providers whose equal local revision
  // counters say nothing about one another. The provider therefore has to
  // remain at an address-stable location for the graph's lifetime; clear or
  // rebuild the graph before ending that lifetime.
  template <typename Provider>
  [[nodiscard]] auto matches_provider(const Provider& provider) const noexcept
      -> bool {
    return matches_provider<Provider>() &&
           built_provider_instance_ ==
               detail::transition_provider_instance_identity(provider) &&
           built_provider_revision_ ==
               detail::transition_provider_revision(provider);
  }
 
 private:
  template <typename World, typename ClassOrTag, typename Provider>
  friend auto build_region_graph(
      const World& world, LocalTopologyScratch& scratch,
      RegionGraphT<typename World::residency_type>& graph,
      const Provider& provider) -> RegionGraphBuildResult;
 
  template <typename World, typename ClassOrTag, typename Provider>
  friend auto update_region_graph(
      const World& world, LocalTopologyScratch& scratch,
      RegionGraphT<typename World::residency_type>& graph,
      std::span<const ChunkKey> dirty_chunks, const Provider& provider)
      -> TopologyBuildResult;
 
  template <typename Shape, typename OtherResidency>
  friend auto reachable(const RegionGraphT<OtherResidency>& graph,
                        PathRequest request, RegionGraphScratch& scratch)
      -> ReachabilityResult;
 
  template <typename Shape, typename OtherResidency>
  friend auto coarse_path(const RegionGraphT<OtherResidency>& graph,
                          PathRequest request, RegionGraphScratch& scratch)
      -> CoarsePathResult;
 
  template <typename OtherWorld>
  friend auto is_region_graph_fresh(
      const OtherWorld& world,
      const RegionGraphT<typename OtherWorld::residency_type>& graph) noexcept
      -> bool;
 
  // Rebuilds the dense region index and the CSR portal adjacency. The CSR
  // fill preserves portal order within each from-region bucket so
  // traversal remains deterministic.
  void rebuild_region_index() {
    region_offsets_.assign(local_topologies_.size() + 1, 0);
    for (std::size_t i = 0; i < local_topologies_.size(); ++i) {
      region_offsets_[i + 1] =
          region_offsets_[i] +
          static_cast<std::uint32_t>(local_topologies_[i].regions().size());
    }
 
    adjacency_starts_.assign(static_cast<std::size_t>(region_count()) + 1, 0);
    for (const auto& portal : portals_) {
      ++adjacency_starts_[static_cast<std::size_t>(region_index(portal.from)) +
                          1];
    }
    for (std::size_t i = 1; i < adjacency_starts_.size(); ++i) {
      adjacency_starts_[i] += adjacency_starts_[i - 1];
    }
 
    adjacency_targets_.resize(portals_.size());
    adjacency_portals_.resize(portals_.size());
    auto cursor = adjacency_starts_;
    for (std::size_t portal_index = 0; portal_index < portals_.size();
         ++portal_index) {
      const auto& portal = portals_[portal_index];
      const auto from = static_cast<std::size_t>(region_index(portal.from));
      const auto edge = static_cast<std::size_t>(cursor[from]++);
      adjacency_targets_[edge] = region_index(portal.to);
      adjacency_portals_[edge] = static_cast<std::uint32_t>(portal_index);
    }
 
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      // Flag every region with a boundary exit into a non-resident chunk. The
      // membership test (has_chunk) -- not portal absence -- is what separates
      // "unknown, non-resident" from "a real wall in a resident neighbor".
      // Keyed by the same global region index the BFS/CSR use, so reachable
      // reads it directly.
      sparse_.region_reaches_missing_.assign(
          static_cast<std::size_t>(region_count()), 0);
      for (const auto& topology : local_topologies_) {
        for (const auto& exit : topology.boundary_exits()) {
          if (has_chunk(exit.target_chunk)) {
            continue;
          }
          const auto idx =
              region_index(RegionRef{topology.chunk(), exit.region});
          if (idx != invalid_region_index) {
            sparse_.region_reaches_missing_[static_cast<std::size_t>(idx)] = 1;
          }
        }
      }
    }
  }
 
  // Shape binding captured at build time. The graph type is templated on
  // residency only, so two Shapes with equal chunk counts share it; the
  // chunk-grid and per-chunk tile extents recorded here tell them apart.
  // update_region_graph treats a mismatch as "not built for this world" (full
  // rebuild); is_region_graph_fresh reports it as not fresh.
  template <typename Shape>
  [[nodiscard]] auto matches_shape() const noexcept -> bool {
    using Traits = ShapeTraits<Shape>;
    return built_chunk_grid_ == Extent3{Traits::chunk_count_x,
                                        Traits::chunk_count_y,
                                        Traits::chunk_count_z} &&
           built_chunk_extent_ == Traits::chunk &&
           built_lattice_identity_ ==
               static_cast<std::uint32_t>(Traits::lattice_identity) &&
           built_lattice_version_ == Traits::lattice_version;
  }
 
  template <typename Shape>
  void bind_shape() noexcept {
    using Traits = ShapeTraits<Shape>;
    built_chunk_grid_ = Extent3{Traits::chunk_count_x, Traits::chunk_count_y,
                                Traits::chunk_count_z};
    built_chunk_extent_ = Traits::chunk;
    built_lattice_identity_ =
        static_cast<std::uint32_t>(Traits::lattice_identity);
    built_lattice_version_ = Traits::lattice_version;
  }
 
  // Movement-class and provider bindings captured at build time, mirroring
  // the shape stamp (see the public matches_class / matches_provider).
  template <typename ClassOrTag>
  void bind_class() noexcept {
    using Class = movement::movement_class_of<ClassOrTag>;
    using Policy = movement::step_policy_of<Class>;
    built_class_ = detail::tag_identity<Class>();
    built_step_policy_identity_ = static_cast<std::uint32_t>(Policy::identity);
    built_cost_scale_ = Policy::cost_scale;
  }
 
  template <typename Provider>
  void bind_provider(const Provider& provider) noexcept {
    built_provider_ = detail::tag_identity<Provider>();
    built_provider_instance_ =
        detail::transition_provider_instance_identity(provider);
    built_provider_revision_ = detail::transition_provider_revision(provider);
  }
 
  void bump_revision() noexcept {
    ++revision_;
    if (revision_ == 0) {
      ++revision_;
    }
  }
 
  // Sparse only: flags every region owning a provider transition that lands
  // in a NON-RESIDENT chunk, so reachability answers Indeterminate rather
  // than a wrong Unreachable across a non-resident special transition. Must run
  // after rebuild_region_index, which reassigns the flags from boundary
  // exits alone.
  template <typename Shape, typename World, typename Provider>
  void mark_provider_missing_reaches(
      [[maybe_unused]] const World& world,
      [[maybe_unused]] const Provider& provider) {
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      for (const auto& topology : local_topologies_) {
        provider.for_each_transition(
            world, topology.chunk(), [&](Coord3 from, Coord3 to) {
              // Same ownership rejection the portal pass applies. Without
              // it a misowned edge creates no portal yet still marks its
              // source region as reaching missing topology, so reachable()
              // answers Indeterminate where the portal pass implies
              // Unreachable.
              if (!detail::provider_source_is_owned<Shape>(from,
                                                           topology.chunk())) {
                return;
              }
              if (!contains<Shape>(to) ||
                  has_chunk(chunk_key<Shape>(chunk_coord<Shape>(to)))) {
                return;
              }
              const auto source = this->template region_of<Shape>(from);
              if (source.region == invalid_local_region) {
                return;
              }
              const auto idx = region_index(source);
              if (idx != invalid_region_index) {
                sparse_.region_reaches_missing_[static_cast<std::size_t>(idx)] =
                    1;
              }
            });
      }
    }
  }
 
  static constexpr std::size_t npos = static_cast<std::size_t>(-1);
 
  // Sparse only: resolve a ChunkKey to its position in the frozen sorted key
  // set, or npos if the chunk was not resident when this graph was built.
  [[nodiscard]] auto local_index(ChunkKey chunk) const noexcept -> std::size_t {
    const auto& keys = sparse_.topology_keys_;
    const auto it = std::lower_bound(
        keys.begin(), keys.end(), chunk,
        [](ChunkKey lhs, ChunkKey rhs) { return lhs.value < rhs.value; });
    if (it == keys.end() || it->value != chunk.value) {
      return npos;
    }
    return static_cast<std::size_t>(it - keys.begin());
  }
 
  [[nodiscard]] auto has_chunk(ChunkKey chunk) const noexcept -> bool {
    return local_index(chunk) != npos;
  }
 
  [[nodiscard]] auto region_ref(std::uint32_t index) const noexcept
      -> RegionRef {
    if (index >= region_count()) {
      return RegionRef{ChunkKey{std::numeric_limits<std::uint64_t>::max()},
                       invalid_local_region};
    }
    const auto upper =
        std::upper_bound(region_offsets_.begin(), region_offsets_.end(), index);
    const auto local = static_cast<std::size_t>(
        std::distance(region_offsets_.begin(), upper) - 1);
    const auto chunk = [&] {
      if constexpr (std::is_same_v<Residency, AlwaysResident>) {
        return ChunkKey{static_cast<std::uint64_t>(local)};
      } else {
        return sparse_.topology_keys_[local];
      }
    }();
    return RegionRef{chunk, LocalRegionId{index - region_offsets_[local] +
                                          std::uint32_t{1}}};
  }
 
  std::vector<LocalChunkTopology> local_topologies_;
  std::vector<RegionPortal> portals_;
  std::vector<std::uint32_t> region_offsets_;
  std::vector<std::uint32_t> adjacency_starts_;
  std::vector<std::uint32_t> adjacency_targets_;
  std::vector<std::uint32_t> adjacency_portals_;
  // Zero until the first build, so an unbuilt graph never matches any shape,
  // movement class, or transition provider.
  Extent3 built_chunk_grid_{0, 0, 0};
  Extent3 built_chunk_extent_{0, 0, 0};
  std::uint32_t built_lattice_identity_ = 0;
  std::uint32_t built_lattice_version_ = 0;
  std::uintptr_t built_class_ = 0;
  std::uint32_t built_step_policy_identity_ = 0;
  std::uint32_t built_cost_scale_ = 0;
  std::uintptr_t built_provider_ = 0;
  const void* built_provider_instance_ = nullptr;
  std::uint64_t built_provider_revision_ = 0;
  std::uint64_t revision_ = 0;
  [[no_unique_address]] detail::RegionGraphSparseData<Residency> sparse_;
};

using RegionGraph = RegionGraphT<AlwaysResident>;
using SparseRegionGraph = RegionGraphT<SparseResident>;
 
namespace detail {
 
template <typename Shape>
[[nodiscard]] constexpr auto local_tile_coord(LocalTileId id) noexcept
    -> LocalCoord3 {
  const auto chunk = ShapeTraits<Shape>::chunk;
  const auto xy = chunk.x * chunk.y;
  const auto z = id.value / xy;
  const auto remainder = id.value % xy;
  return LocalCoord3{
      remainder % chunk.x,
      remainder / chunk.x,
      z,
  };
}
 
template <typename Shape>
constexpr void add_boundary_exit(std::vector<LocalBoundaryExit>& exits,
                                 LocalRegion& region, LocalTileId local_tile,
                                 Coord3 coord, BoundaryFace face,
                                 ChunkCoord3 target_chunk) {
  exits.push_back(LocalBoundaryExit{
      region.id,
      local_tile,
      coord,
      face,
      chunk_key<Shape>(target_chunk),
  });
  ++region.boundary_exit_count;
}
 
template <typename Shape>
constexpr void add_boundary_exits(std::vector<LocalBoundaryExit>& exits,
                                  ChunkCoord3 chunk_coord, LocalRegion& region,
                                  LocalTileId local_tile, LocalCoord3 local,
                                  Coord3 coord) {
  const auto chunk = ShapeTraits<Shape>::chunk;
 
  if constexpr (std::is_same_v<typename ShapeTraits<Shape>::lattice_type,
                               lattice::HexAxial>) {
    detail::for_each_regular_candidate<Shape, movement::DefaultSteps>(
        coord, [&](detail::RegularTransitionCandidate candidate) {
          const auto target = tess::chunk_coord<Shape>(candidate.to);
          if (target == chunk_coord) {
            return;
          }
          auto face = BoundaryFace::NegativeX;
          if (candidate.to.x > coord.x && candidate.to.y < coord.y) {
            face = BoundaryFace::PositiveXNegativeY;
          } else if (candidate.to.x < coord.x && candidate.to.y > coord.y) {
            face = BoundaryFace::NegativeXPositiveY;
          } else if (candidate.to.x > coord.x) {
            face = BoundaryFace::PositiveX;
          } else if (candidate.to.x < coord.x) {
            face = BoundaryFace::NegativeX;
          } else if (candidate.to.y > coord.y) {
            face = BoundaryFace::PositiveY;
          } else {
            face = BoundaryFace::NegativeY;
          }
          add_boundary_exit<Shape>(exits, region, local_tile, coord, face,
                                   target);
        });
    return;
  }
 
  if (local.x == 0 && chunk_coord.x > 0) {
    auto target = chunk_coord;
    --target.x;
    add_boundary_exit<Shape>(exits, region, local_tile, coord,
                             BoundaryFace::NegativeX, target);
  }
  if (local.x + 1 == chunk.x &&
      chunk_coord.x + 1 < ShapeTraits<Shape>::chunk_count_x) {
    auto target = chunk_coord;
    ++target.x;
    add_boundary_exit<Shape>(exits, region, local_tile, coord,
                             BoundaryFace::PositiveX, target);
  }
  if (local.y == 0 && chunk_coord.y > 0) {
    auto target = chunk_coord;
    --target.y;
    add_boundary_exit<Shape>(exits, region, local_tile, coord,
                             BoundaryFace::NegativeY, target);
  }
  if (local.y + 1 == chunk.y &&
      chunk_coord.y + 1 < ShapeTraits<Shape>::chunk_count_y) {
    auto target = chunk_coord;
    ++target.y;
    add_boundary_exit<Shape>(exits, region, local_tile, coord,
                             BoundaryFace::PositiveY, target);
  }
  if (local.z == 0 && chunk_coord.z > 0) {
    auto target = chunk_coord;
    --target.z;
    add_boundary_exit<Shape>(exits, region, local_tile, coord,
                             BoundaryFace::NegativeZ, target);
  }
  if (local.z + 1 == chunk.z &&
      chunk_coord.z + 1 < ShapeTraits<Shape>::chunk_count_z) {
    auto target = chunk_coord;
    ++target.z;
    add_boundary_exit<Shape>(exits, region, local_tile, coord,
                             BoundaryFace::PositiveZ, target);
  }
}
 
template <typename Shape, typename Fn>
constexpr void for_each_local_axis_neighbor(LocalCoord3 coord, Fn&& fn) {
  const auto chunk = ShapeTraits<Shape>::chunk;
  if (coord.x + 1 < chunk.x) {
    fn(LocalCoord3{coord.x + 1, coord.y, coord.z});
  }
  if (coord.x > 0) {
    fn(LocalCoord3{coord.x - 1, coord.y, coord.z});
  }
  if (coord.y + 1 < chunk.y) {
    fn(LocalCoord3{coord.x, coord.y + 1, coord.z});
  }
  if (coord.y > 0) {
    fn(LocalCoord3{coord.x, coord.y - 1, coord.z});
  }
  if constexpr (std::is_same_v<typename ShapeTraits<Shape>::lattice_type,
                               lattice::HexAxial>) {
    if (coord.x + 1 < chunk.x && coord.y > 0) {
      fn(LocalCoord3{coord.x + 1, coord.y - 1, 0});
    }
    if (coord.x > 0 && coord.y + 1 < chunk.y) {
      fn(LocalCoord3{coord.x - 1, coord.y + 1, 0});
    }
    return;
  }
  if (coord.z + 1 < chunk.z) {
    fn(LocalCoord3{coord.x, coord.y, coord.z + 1});
  }
  if (coord.z > 0) {
    fn(LocalCoord3{coord.x, coord.y, coord.z - 1});
  }
}
 
constexpr void include_coord_in_bounds(LocalRegion& region,
                                       Coord3 coord) noexcept {
  if (region.tile_count == 0) {
    region.bounds = Box3{coord, Extent3{1, 1, 1}};
    return;
  }
 
  const auto end = [](std::int64_t origin, std::uint64_t extent) {
    // Same saturation as detail::box_axis_end in storage/chunk_meta.h: an
    // extent >= 2^63 would flip the int64 cast negative and corrupt bounds.
    constexpr auto max = std::numeric_limits<std::int64_t>::max();
    if (extent > static_cast<std::uint64_t>(max)) {
      return max;
    }
    const auto delta = static_cast<std::int64_t>(extent);
    return origin > max - delta ? max : origin + delta;
  };
  const auto min = [](std::int64_t lhs, std::int64_t rhs) {
    return lhs < rhs ? lhs : rhs;
  };
  const auto max = [](std::int64_t lhs, std::int64_t rhs) {
    return lhs < rhs ? rhs : lhs;
  };
  const auto min_x = min(region.bounds.origin.x, coord.x);
  const auto min_y = min(region.bounds.origin.y, coord.y);
  const auto min_z = min(region.bounds.origin.z, coord.z);
  const auto max_x =
      max(end(region.bounds.origin.x, region.bounds.extent.x), coord.x + 1);
  const auto max_y =
      max(end(region.bounds.origin.y, region.bounds.extent.y), coord.y + 1);
  const auto max_z =
      max(end(region.bounds.origin.z, region.bounds.extent.z), coord.z + 1);
 
  region.bounds = Box3{
      Coord3{min_x, min_y, min_z},
      // max >= min on every axis; abs_delta subtracts in unsigned space, so a
      // saturated end paired with a negative origin cannot overflow int64.
      Extent3{
          abs_delta(max_x, min_x),
          abs_delta(max_y, min_y),
          abs_delta(max_z, min_z),
      },
  };
}
 
[[nodiscard]] constexpr auto neighbor_coord(Coord3 coord,
                                            BoundaryFace face) noexcept
    -> Coord3 {
  switch (face) {
    case BoundaryFace::NegativeX:
      return Coord3{coord.x - 1, coord.y, coord.z};
    case BoundaryFace::PositiveX:
      return Coord3{coord.x + 1, coord.y, coord.z};
    case BoundaryFace::NegativeY:
      return Coord3{coord.x, coord.y - 1, coord.z};
    case BoundaryFace::PositiveY:
      return Coord3{coord.x, coord.y + 1, coord.z};
    case BoundaryFace::NegativeZ:
      return Coord3{coord.x, coord.y, coord.z - 1};
    case BoundaryFace::PositiveZ:
      return Coord3{coord.x, coord.y, coord.z + 1};
    case BoundaryFace::PositiveXNegativeY:
      return Coord3{coord.x + 1, coord.y - 1, coord.z};
    case BoundaryFace::NegativeXPositiveY:
      return Coord3{coord.x - 1, coord.y + 1, coord.z};
  }
  return coord;
}
 
template <typename Shape, typename Fn>
constexpr void for_each_face_neighbor_chunk(ChunkCoord3 coord, Fn&& fn) {
  using Traits = ShapeTraits<Shape>;
  if (coord.x > 0) {
    auto target = coord;
    --target.x;
    fn(target);
  }
  if (coord.x + 1 < Traits::chunk_count_x) {
    auto target = coord;
    ++target.x;
    fn(target);
  }
  if (coord.y > 0) {
    auto target = coord;
    --target.y;
    fn(target);
  }
  if (coord.y + 1 < Traits::chunk_count_y) {
    auto target = coord;
    ++target.y;
    fn(target);
  }
  if (coord.z > 0) {
    auto target = coord;
    --target.z;
    fn(target);
  }
  if (coord.z + 1 < Traits::chunk_count_z) {
    auto target = coord;
    ++target.z;
    fn(target);
  }
  if constexpr (std::is_same_v<typename Traits::lattice_type,
                               lattice::HexAxial>) {
    if (coord.x + 1 < Traits::chunk_count_x && coord.y > 0) {
      auto target = coord;
      ++target.x;
      --target.y;
      fn(target);
    }
    if (coord.x > 0 && coord.y + 1 < Traits::chunk_count_y) {
      auto target = coord;
      --target.x;
      ++target.y;
      fn(target);
    }
  }
}
 
// Face reported for a provider transition: the dominant axis of the delta
// (ties fall to x, then y, then z). Reachability reads only the CSR
// adjacency, so the face is diagnostic labeling for special transitions.
[[nodiscard]] inline auto transition_face(Coord3 from, Coord3 to) noexcept
    -> BoundaryFace {
  const auto dx = to.x - from.x;
  const auto dy = to.y - from.y;
  const auto dz = to.z - from.z;
  const auto ax = dx < 0 ? -dx : dx;
  const auto ay = dy < 0 ? -dy : dy;
  const auto az = dz < 0 ? -dz : dz;
  if (ax >= ay && ax >= az) {
    return dx < 0 ? BoundaryFace::NegativeX : BoundaryFace::PositiveX;
  }
  if (ay >= az) {
    return dy < 0 ? BoundaryFace::NegativeY : BoundaryFace::PositiveY;
  }
  return dz < 0 ? BoundaryFace::NegativeZ : BoundaryFace::PositiveZ;
}
 
// True iff the two coordinates' chunks are identical or regular-step
// neighbors. For axial hexes that includes the two diagonal chunk seams.
// Keeping this definition shared with invalidation prevents provider portals
// from surviving an edit in their landing chunk.
template <typename Shape>
[[nodiscard]] auto same_or_face_neighbor_chunk(Coord3 from, Coord3 to) noexcept
    -> bool {
  const auto a = chunk_coord<Shape>(from);
  const auto b = chunk_coord<Shape>(to);
  if (a == b) {
    return true;
  }
  auto is_neighbor = false;
  for_each_face_neighbor_chunk<Shape>(a, [&](ChunkCoord3 neighbor) {
    is_neighbor = is_neighbor || neighbor == b;
  });
  return is_neighbor;
}
 
// Appends one directed portal per provider transition originating in this
// chunk whose endpoints both resolve to labeled regions, in enumeration
// order. Out-of-shape or unlabeled endpoints contribute nothing; a sparse
// non-resident landing is handled by the builder's reaches-missing pass.
template <typename Shape, typename World, typename Residency, typename Provider>
void append_provider_portals(const World& world,
                             const RegionGraphT<Residency>& graph,
                             const LocalChunkTopology& topology,
                             const Provider& provider,
                             std::vector<RegionPortal>& portals) {
  provider.for_each_transition(
      world, topology.chunk(), [&](Coord3 from, Coord3 to) {
        // Enforced, not asserted. The incremental erase keys removal on
        // `portal.from.chunk`, so a portal whose source lies outside the
        // enumerated chunk is never erased, while every update touching that
        // chunk appends it again. A provider violating the documented
        // ownership contract would therefore grow `portals_` without bound
        // and make incremental output diverge from a full rebuild -- and
        // only in builds with assertions compiled out, which is where it is
        // hardest to notice. Dropping the transition keeps the graph
        // well-formed in every build, and makes the behaviour testable
        // rather than an abort.
        if (!detail::provider_source_is_owned<Shape>(from, topology.chunk())) {
          return;
        }
        if (!contains<Shape>(to)) {
          return;
        }
        TESS_ASSERT((same_or_face_neighbor_chunk<Shape>(from, to)));
        const auto source = graph.template region_of<Shape>(from);
        if (source.region == invalid_local_region) {
          return;
        }
        const auto target = graph.template region_of<Shape>(to);
        if (target.region == invalid_local_region) {
          return;
        }
        portals.push_back(
            RegionPortal{source, target, from, to, transition_face(from, to)});
      });
}
 
// Derives directed portals for every boundary exit of one chunk topology,
// in exit order, appending only exits whose neighbor tile maps to a
// passable region.
template <typename Shape, typename Residency>
void append_chunk_portals(const RegionGraphT<Residency>& graph,
                          const LocalChunkTopology& topology,
                          std::vector<RegionPortal>& portals) {
  for (const auto& exit : topology.boundary_exits()) {
    const auto to_coord = neighbor_coord(exit.coord, exit.face);
    const auto target = graph.template region_of<Shape>(to_coord);
    if (target.region == invalid_local_region) {
      continue;
    }
    portals.push_back(RegionPortal{
        RegionRef{topology.chunk(), exit.region},
        target,
        exit.coord,
        to_coord,
        exit.face,
    });
  }
}
 
}  // namespace detail

template <typename World, typename ClassOrTag>
[[nodiscard]] auto build_local_chunk_topology(const World& world,
                                              ChunkKey chunk,
                                              LocalTopologyScratch& scratch,
                                              LocalChunkTopology& topology)
    -> TopologyBuildResult {
  using Shape = typename World::shape_type;
  using Traits = ShapeTraits<Shape>;
  using Class = movement::movement_class_of<ClassOrTag>;
 
  topology.clear();
  if (chunk.value >= Traits::chunk_count) {
    return TopologyBuildResult{TopologyStatus::InvalidChunk, 0, 0, 0, 0};
  }
  if constexpr (std::is_same_v<typename World::residency_type,
                               SparseResident>) {
    if (!world.is_resident(chunk)) {
      return TopologyBuildResult{TopologyStatus::MissingChunk, 0, 0, 0, 0};
    }
  }
 
  topology.chunk_ = chunk;
  topology.chunk_coord_ = chunk_coord<Shape>(chunk);
  topology.topology_version_ = world.meta(chunk).topology_version;
  topology.region_ids_.assign(
      static_cast<std::size_t>(Traits::local_tile_count), invalid_local_region);
  scratch.stack_.clear();
 
  // Identity classes flood the raw field span exactly as the legacy
  // single-tag build did (byte-identical labels and codegen); composed
  // classes evaluate their predicate on the resolved page per tile.
  const auto& page = world.chunk(chunk);
  [[maybe_unused]] const auto passable = [&] {
    if constexpr (movement::HasPassableSpan<Class>) {
      return Class::passable_span(page);
    } else {
      return nullptr;
    }
  }();
  const auto tile_passable = [&](LocalTileId id) -> bool {
    if constexpr (movement::HasPassableSpan<Class>) {
      return static_cast<bool>(passable[static_cast<std::size_t>(id.value)]);
    } else {
      return Class::passable(page, id);
    }
  };
  std::size_t passable_tiles = 0;
 
  for (std::uint64_t raw_id = 0; raw_id < Traits::local_tile_count; ++raw_id) {
    const auto tile = LocalTileId{raw_id};
    const auto offset = static_cast<std::size_t>(raw_id);
    if (!tile_passable(tile) ||
        topology.region_ids_[offset] != invalid_local_region) {
      continue;
    }
 
    const auto region_id =
        LocalRegionId{static_cast<std::uint32_t>(topology.regions_.size() + 1)};
    topology.regions_.push_back(LocalRegion{region_id});
    scratch.stack_.push_back(tile);
    topology.region_ids_[offset] = region_id;
 
    while (!scratch.stack_.empty()) {
      const auto current = scratch.stack_.back();
      scratch.stack_.pop_back();
      const auto local = detail::local_tile_coord<Shape>(current);
      const auto coord = tess::coord<Shape>(topology.chunk_coord_, current);
      auto& region = topology.regions_.back();
      detail::include_coord_in_bounds(region, coord);
      ++region.tile_count;
      ++passable_tiles;
      detail::add_boundary_exits<Shape>(topology.boundary_exits_,
                                        topology.chunk_coord_, region, current,
                                        local, coord);
 
      detail::for_each_local_axis_neighbor<Shape>(
          local, [&](LocalCoord3 neighbor_coord) {
            const auto neighbor = local_tile_id<Shape>(neighbor_coord);
            const auto neighbor_offset =
                static_cast<std::size_t>(neighbor.value);
            if (!tile_passable(neighbor) ||
                topology.region_ids_[neighbor_offset] != invalid_local_region) {
              return;
            }
            topology.region_ids_[neighbor_offset] = region_id;
            scratch.stack_.push_back(neighbor);
          });
    }
  }
 
  return TopologyBuildResult{
      TopologyStatus::Built,
      topology.regions_.size(),
      passable_tiles,
      topology.boundary_exits_.size(),
      topology.topology_version_.value,
  };
}
 
namespace detail {
inline void add_topology_version_sum(std::uint64_t& sum,
                                     std::uint64_t value) noexcept {
  if (value > std::numeric_limits<std::uint64_t>::max() - sum) {
    fail_fast("topology version sum exhausted");
  }
  sum += value;
}
 
// A full rebuild cannot fail, so an update that falls back to one always
// reports Built. Spelled once here rather than at each of the three
// fallback sites.
[[nodiscard]] constexpr auto as_topology_build_result(
    RegionGraphBuildResult built) noexcept -> TopologyBuildResult {
  return TopologyBuildResult{
      TopologyStatus::Built,      built.region_count,
      built.passable_tile_count,  built.boundary_exit_count,
      built.topology_version_sum,
  };
}
 
}  // namespace detail
 
template <typename World, typename ClassOrTag,
          typename Provider = AdjacentTransitions>
auto build_region_graph(const World& world, LocalTopologyScratch& scratch,
                        RegionGraphT<typename World::residency_type>& graph,
                        const Provider& provider = {})
    -> RegionGraphBuildResult {
  static_assert(TransitionProviderFor<Provider, World>,
                "build_region_graph's provider must satisfy "
                "TransitionProviderFor (see transition_provider.h).");
  using Shape = typename World::shape_type;
  using Traits = ShapeTraits<Shape>;
  using Class = movement::movement_class_of<ClassOrTag>;
 
  graph.clear();
  graph.template bind_shape<Shape>();
  graph.template bind_class<Class>();
  graph.bind_provider(provider);
  auto result = RegionGraphBuildResult{};
 
#if TESS_HAS_EXCEPTIONS
  try {
#endif
    if constexpr (std::is_same_v<typename World::residency_type,
                                 AlwaysResident>) {
      graph.local_topologies_.resize(
          static_cast<std::size_t>(Traits::chunk_count));
      for (std::uint64_t raw_chunk = 0; raw_chunk < Traits::chunk_count;
           ++raw_chunk) {
        auto& topology =
            graph.local_topologies_[static_cast<std::size_t>(raw_chunk)];
        const auto local_result = build_local_chunk_topology<World, Class>(
            world, ChunkKey{raw_chunk}, scratch, topology);
        if (local_result.status != TopologyStatus::Built) {
          // Unreachable: raw_chunk < chunk_count rules out InvalidChunk and
          // MissingChunk does not exist under AlwaysResident. If it ever
          // fires, the residency assumptions this function rests on have
          // changed, and continuing would publish a half-built graph.
          detail::fail_fast(
              "build_region_graph: dense local build reported a failure");
        }
        result.region_count += local_result.region_count;
        result.passable_tile_count += local_result.passable_tile_count;
        result.boundary_exit_count += local_result.boundary_exit_count;
        detail::add_topology_version_sum(result.topology_version_sum,
                                         local_result.topology_version_sum);
      }
    } else {
      // Sparse: build only over the resident set, sized by resident_count,
      // never chunk_count. Freeze the resident keys sorted ascending so a local
      // index equals chunk order; portals then append in chunk order exactly as
      // the dense build does, keeping "incremental == fresh" trivially.
      auto& keys = graph.sparse_.topology_keys_;
      const auto resident = world.resident_chunk_keys();
      keys.assign(resident.begin(), resident.end());
      std::sort(keys.begin(), keys.end(), [](ChunkKey lhs, ChunkKey rhs) {
        return lhs.value < rhs.value;
      });
      const auto count = keys.size();
      graph.local_topologies_.resize(count);
      graph.sparse_.frozen_generations_.resize(count);
      for (std::size_t i = 0; i < count; ++i) {
        const auto local_result = build_local_chunk_topology<World, Class>(
            world, keys[i], scratch, graph.local_topologies_[i]);
        // Unreachable: resident keys are in-world and resident by
        // construction, so neither InvalidChunk nor MissingChunk can arise.
        if (local_result.status != TopologyStatus::Built) {
          detail::fail_fast(
              "build_region_graph: sparse local build reported a failure");
        }
        result.region_count += local_result.region_count;
        result.passable_tile_count += local_result.passable_tile_count;
        result.boundary_exit_count += local_result.boundary_exit_count;
        detail::add_topology_version_sum(result.topology_version_sum,
                                         local_result.topology_version_sum);
        graph.sparse_.frozen_generations_[i] =
            world.residency_generation(keys[i]);
      }
    }
 
    for (const auto& topology : graph.local_topologies_) {
      detail::append_chunk_portals<Shape>(graph, topology, graph.portals_);
      detail::append_provider_portals<Shape>(world, graph, topology, provider,
                                             graph.portals_);
    }
    graph.rebuild_region_index();
    graph.template mark_provider_missing_reaches<Shape>(world, provider);
 
    return result;
#if TESS_HAS_EXCEPTIONS
  } catch (...) {
    // Full builds publish directly into caller storage for locality. If any
    // allocation fails after clear(), discard all partial labels and derived
    // indices so freshness checks cannot bless a torn graph.
    graph.clear();
    throw;
  }
#endif
}
 
// Incrementally patches an already-built region graph after passability
// edits confined to `dirty_chunks`. Rebuilds local topology for each dirty
// chunk, re-derives portals for dirty chunks and their face neighbors, and
// restores the canonical full-build portal order, so the resulting graph is
// identical to a fresh build_region_graph over the edited world. An empty
// dirty set leaves the graph untouched. Returns the aggregate
// TopologyBuildResult over all chunks, mirroring build_region_graph. If the
// graph was not built for this world shape, falls back to a full build.
template <typename World, typename ClassOrTag,
          typename Provider = AdjacentTransitions>
[[nodiscard]] auto update_region_graph(
    const World& world, LocalTopologyScratch& scratch,
    RegionGraphT<typename World::residency_type>& graph,
    std::span<const ChunkKey> dirty_chunks, const Provider& provider = {})
    -> TopologyBuildResult {
  static_assert(TransitionProviderFor<Provider, World>,
                "update_region_graph's provider must satisfy "
                "TransitionProviderFor (see transition_provider.h).");
  using Shape = typename World::shape_type;
  using Traits = ShapeTraits<Shape>;
  using Class = movement::movement_class_of<ClassOrTag>;
 
  if constexpr (std::is_same_v<typename World::residency_type,
                               AlwaysResident>) {
    const auto chunk_count = static_cast<std::size_t>(Traits::chunk_count);
    if (graph.local_topologies_.size() != chunk_count ||
        !graph.template matches_shape<Shape>() ||
        !graph.template matches_class<Class>() ||
        !graph.matches_provider(provider)) {
      return detail::as_topology_build_result(
          build_region_graph<World, Class>(world, scratch, graph, provider));
    }
    for (const auto chunk : dirty_chunks) {
      if (chunk.value >= Traits::chunk_count) {
        return TopologyBuildResult{TopologyStatus::InvalidChunk, 0, 0, 0, 0};
      }
    }
 
    if (!dirty_chunks.empty()) {
      // Mark dirty chunks, then widen to every face neighbor: those are the
      // only chunks whose outgoing portals can reference a dirty chunk.
      std::vector<std::uint8_t> dirty(chunk_count, 0);
      std::vector<std::uint8_t> affected(chunk_count, 0);
      for (const auto chunk : dirty_chunks) {
        const auto offset = static_cast<std::size_t>(chunk.value);
        dirty[offset] = 1;
        affected[offset] = 1;
      }
      for (std::size_t raw_chunk = 0; raw_chunk < chunk_count; ++raw_chunk) {
        if (dirty[raw_chunk] == 0) {
          continue;
        }
        detail::for_each_face_neighbor_chunk<Shape>(
            chunk_coord<Shape>(ChunkKey{raw_chunk}), [&](ChunkCoord3 neighbor) {
              const auto key = chunk_key<Shape>(neighbor);
              affected[static_cast<std::size_t>(key.value)] = 1;
            });
      }
 
#if TESS_HAS_EXCEPTIONS
      try {
#endif
        for (std::size_t raw_chunk = 0; raw_chunk < chunk_count; ++raw_chunk) {
          if (dirty[raw_chunk] == 0) {
            continue;
          }
          // Discarded deliberately. Neither failure status is reachable
          // here: we are inside `if constexpr (AlwaysResident)`, where
          // build_local_chunk_topology never reports MissingChunk -- that
          // status is returned only under SparseResident -- and
          // InvalidChunk is ruled out by the dirty-chunk bounds check
          // above. The incremental sparse branch discards it too, on a
          // different argument (see the matching comment there); the two
          // full rebuilds do propagate it.
          static_cast<void>(build_local_chunk_topology<World, Class>(
              world, ChunkKey{raw_chunk}, scratch,
              graph.local_topologies_[raw_chunk]));
        }
 
        // Every invalidated portal originates from an affected chunk, because
        // portals only span face-adjacent chunks. Drop them in one filtered
        // pass, re-derive all portals of affected chunks in exit order, then
        // stable-sort by from-chunk to restore the canonical build order.
        std::erase_if(graph.portals_, [&](const RegionPortal& portal) {
          return affected[static_cast<std::size_t>(portal.from.chunk.value)] !=
                 0;
        });
        for (std::size_t raw_chunk = 0; raw_chunk < chunk_count; ++raw_chunk) {
          if (affected[raw_chunk] == 0) {
            continue;
          }
          detail::append_chunk_portals<Shape>(
              graph, graph.local_topologies_[raw_chunk], graph.portals_);
          detail::append_provider_portals<Shape>(
              world, graph, graph.local_topologies_[raw_chunk], provider,
              graph.portals_);
        }
        std::stable_sort(graph.portals_.begin(), graph.portals_.end(),
                         [](const RegionPortal& lhs, const RegionPortal& rhs) {
                           return lhs.from.chunk.value < rhs.from.chunk.value;
                         });
        graph.rebuild_region_index();
        graph.bump_revision();
#if TESS_HAS_EXCEPTIONS
      } catch (...) {
        // Incremental locality matters on this performance-sensitive path, so
        // do not copy every unchanged tile label merely for rollback. Clear is
        // allocation-free and revision-invalidates all consumers, providing a
        // safe basic guarantee: never expose mixed labels, portals, or CSR.
        graph.clear();
        throw;
      }
#endif
    }
  } else {
    // Sparse: any residency change since build forces a full rebuild (the graph
    // is frozen to a residency snapshot). Exact set-equality via resident_count
    // plus per-key generation: an evicted key reads generation 0, a
    // rematerialized key gets a strictly greater monotonic generation, so equal
    // count with all frozen keys still at their frozen generation forces set
    // identity. Generations are per-WORLD clocks: a graph must only ever be
    // updated against the world it was built from (see is_region_graph_fresh).
    const auto count = graph.local_topologies_.size();
    if (count != world.resident_count() ||
        graph.sparse_.frozen_generations_.size() != world.resident_count() ||
        !graph.template matches_shape<Shape>() ||
        !graph.template matches_class<Class>() ||
        !graph.matches_provider(provider)) {
      return detail::as_topology_build_result(
          build_region_graph<World, Class>(world, scratch, graph, provider));
    }
    for (std::size_t i = 0; i < count; ++i) {
      if (world.residency_generation(graph.sparse_.topology_keys_[i]) !=
          graph.sparse_.frozen_generations_[i]) {
        return detail::as_topology_build_result(
            build_region_graph<World, Class>(world, scratch, graph, provider));
      }
    }
    for (const auto chunk : dirty_chunks) {
      if (chunk.value >= Traits::chunk_count) {
        return TopologyBuildResult{TopologyStatus::InvalidChunk, 0, 0, 0, 0};
      }
    }
 
    if (!dirty_chunks.empty()) {
      // dirty/affected live in local-index space (size N = resident_count),
      // never chunk_count. A dirty chunk that is not resident holds no topology
      // in the frozen graph, so it is skipped.
      std::vector<std::uint8_t> dirty(count, 0);
      std::vector<std::uint8_t> affected(count, 0);
      for (const auto chunk : dirty_chunks) {
        const auto li = graph.local_index(chunk);
        if (li == graph.npos) {
          continue;
        }
        dirty[li] = 1;
        affected[li] = 1;
      }
      for (std::size_t i = 0; i < count; ++i) {
        if (dirty[i] == 0) {
          continue;
        }
        detail::for_each_face_neighbor_chunk<Shape>(
            chunk_coord<Shape>(graph.sparse_.topology_keys_[i]),
            [&](ChunkCoord3 neighbor) {
              const auto li = graph.local_index(chunk_key<Shape>(neighbor));
              if (li != graph.npos) {
                affected[li] = 1;
              }
            });
      }
 
#if TESS_HAS_EXCEPTIONS
      try {
#endif
        for (std::size_t i = 0; i < count; ++i) {
          if (dirty[i] == 0) {
            continue;
          }
          // Discarded deliberately, and sound for a different reason than
          // the dense branch above. MissingChunk would mean a frozen key
          // is no longer resident, but the generation loop at the top of
          // this branch already returned to a full rebuild in that case:
          // an absent key reads residency_generation 0, every frozen
          // generation is non-zero because the keys were resident when
          // frozen, so any eviction fails the equality check. InvalidChunk
          // is ruled out by the dirty-chunk bounds check above. Built is
          // therefore the only reachable status.
          static_cast<void>(build_local_chunk_topology<World, Class>(
              world, graph.sparse_.topology_keys_[i], scratch,
              graph.local_topologies_[i]));
        }
 
        std::erase_if(graph.portals_, [&](const RegionPortal& portal) {
          const auto li = graph.local_index(portal.from.chunk);
          return li != graph.npos && affected[li] != 0;
        });
        for (std::size_t i = 0; i < count; ++i) {
          if (affected[i] == 0) {
            continue;
          }
          detail::append_chunk_portals<Shape>(graph, graph.local_topologies_[i],
                                              graph.portals_);
          detail::append_provider_portals<Shape>(world, graph,
                                                 graph.local_topologies_[i],
                                                 provider, graph.portals_);
        }
        std::stable_sort(graph.portals_.begin(), graph.portals_.end(),
                         [](const RegionPortal& lhs, const RegionPortal& rhs) {
                           return lhs.from.chunk.value < rhs.from.chunk.value;
                         });
        graph.rebuild_region_index();
        graph.template mark_provider_missing_reaches<Shape>(world, provider);
        graph.bump_revision();
#if TESS_HAS_EXCEPTIONS
      } catch (...) {
        // Clear also drops frozen residency and missing-region state, so a
        // retry cannot mistake a partly rebuilt sparse snapshot for fresh.
        graph.clear();
        throw;
      }
#endif
    }
  }
 
  auto result = TopologyBuildResult{};
  for (const auto& topology : graph.local_topologies_) {
    result.region_count += topology.regions().size();
    for (const auto& region : topology.regions()) {
      result.passable_tile_count += region.tile_count;
    }
    result.boundary_exit_count += topology.boundary_exits().size();
    detail::add_topology_version_sum(result.topology_version_sum,
                                     topology.topology_version().value);
  }
  return result;
}

template <typename Shape, typename Residency>
[[nodiscard]] auto reachable(const RegionGraphT<Residency>& graph,
                             PathRequest request, RegionGraphScratch& scratch)
    -> ReachabilityResult {
  if (!contains<Shape>(request.start)) {
    return ReachabilityResult{ReachabilityStatus::InvalidStart, 0};
  }
  if (!contains<Shape>(request.goal)) {
    return ReachabilityResult{ReachabilityStatus::InvalidGoal, 0};
  }
 
  const auto start_region = graph.template region_of<Shape>(request.start);
  if (start_region.region == invalid_local_region) {
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      // A non-resident endpoint cannot be answered: its region is unknown,
      // distinct from a resident-but-walled tile (InvalidStart below).
      if (!graph.has_chunk(
              chunk_key<Shape>(chunk_coord<Shape>(request.start)))) {
        return ReachabilityResult{ReachabilityStatus::Indeterminate, 0};
      }
    }
    return ReachabilityResult{ReachabilityStatus::InvalidStart, 0};
  }
  const auto goal_region = graph.template region_of<Shape>(request.goal);
  if (goal_region.region == invalid_local_region) {
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      if (!graph.has_chunk(
              chunk_key<Shape>(chunk_coord<Shape>(request.goal)))) {
        return ReachabilityResult{ReachabilityStatus::Indeterminate, 0};
      }
    }
    return ReachabilityResult{ReachabilityStatus::InvalidGoal, 0};
  }
  if (start_region == goal_region) {
    return ReachabilityResult{ReachabilityStatus::Reachable, 1};
  }
 
  const auto start_index = graph.region_index(start_region);
  if (start_index == invalid_region_index) {
    return ReachabilityResult{ReachabilityStatus::InvalidStart, 0};
  }
  const auto goal_index = graph.region_index(goal_region);
  if (goal_index == invalid_region_index) {
    return ReachabilityResult{ReachabilityStatus::InvalidGoal, 0};
  }
 
  scratch.begin_traversal(static_cast<std::size_t>(graph.region_count()));
  scratch.visit(start_index);
  std::size_t visited_count = 1;
  scratch.frontier_.push_back(start_index);
 
  // Sparse: track whether the searched component touches a region that exits
  // into a non-resident chunk, so an exhausted BFS that never reached goal
  // returns Indeterminate rather than a wrong Unreachable.
  [[maybe_unused]] bool touched_missing = false;
  if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
    touched_missing =
        graph.sparse_
            .region_reaches_missing_[static_cast<std::size_t>(start_index)] !=
        0;
  }
 
  while (!scratch.frontier_.empty()) {
    const auto current = scratch.frontier_.back();
    scratch.frontier_.pop_back();
 
    const auto begin = static_cast<std::size_t>(
        graph.adjacency_starts_[static_cast<std::size_t>(current)]);
    const auto end = static_cast<std::size_t>(
        graph.adjacency_starts_[static_cast<std::size_t>(current) + 1]);
    for (std::size_t edge = begin; edge < end; ++edge) {
      const auto target = graph.adjacency_targets_[edge];
      if (scratch.is_visited(target)) {
        continue;
      }
      if (target == goal_index) {
        return ReachabilityResult{ReachabilityStatus::Reachable,
                                  visited_count + 1};
      }
      scratch.visit(target);
      ++visited_count;
      scratch.frontier_.push_back(target);
      if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
        touched_missing =
            touched_missing ||
            graph.sparse_.region_reaches_missing_[static_cast<std::size_t>(
                target)] != 0;
      }
    }
  }
 
  if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
    if (touched_missing) {
      return ReachabilityResult{ReachabilityStatus::Indeterminate,
                                visited_count};
    }
  }
  return ReachabilityResult{ReachabilityStatus::Unreachable, visited_count};
}

template <typename Shape, typename Residency>
[[nodiscard]] auto coarse_path(const RegionGraphT<Residency>& graph,
                               PathRequest request, RegionGraphScratch& scratch)
    -> CoarsePathResult {
  const auto region_count = static_cast<std::size_t>(graph.region_count());
  scratch.begin_traversal(region_count);
  const auto result = [&](ReachabilityStatus status,
                          std::size_t visited) -> CoarsePathResult {
    return CoarsePathResult{
        status,
        visited,
        std::span<const RegionRef>{scratch.path_regions_},
        std::span<const RegionPortal>{scratch.path_portals_},
        std::span<const ChunkKey>{scratch.corridor_chunks_},
        {},
    };
  };
  if (!contains<Shape>(request.start)) {
    return result(ReachabilityStatus::InvalidStart, 0);
  }
  if (!contains<Shape>(request.goal)) {
    return result(ReachabilityStatus::InvalidGoal, 0);
  }
 
  const auto start_region = graph.template region_of<Shape>(request.start);
  if (start_region.region == invalid_local_region) {
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      if (!graph.has_chunk(
              chunk_key<Shape>(chunk_coord<Shape>(request.start)))) {
        return result(ReachabilityStatus::Indeterminate, 0);
      }
    }
    return result(ReachabilityStatus::InvalidStart, 0);
  }
  const auto goal_region = graph.template region_of<Shape>(request.goal);
  if (goal_region.region == invalid_local_region) {
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      if (!graph.has_chunk(
              chunk_key<Shape>(chunk_coord<Shape>(request.goal)))) {
        return result(ReachabilityStatus::Indeterminate, 0);
      }
    }
    return result(ReachabilityStatus::InvalidGoal, 0);
  }
 
  const auto start_index = graph.region_index(start_region);
  const auto goal_index = graph.region_index(goal_region);
  if (start_index == invalid_region_index) {
    return result(ReachabilityStatus::InvalidStart, 0);
  }
  if (goal_index == invalid_region_index) {
    return result(ReachabilityStatus::InvalidGoal, 0);
  }
 
  scratch.parent_.resize(region_count, invalid_region_index);
  scratch.parent_portal_.resize(region_count, invalid_region_index);
  scratch.visit(start_index);
  scratch.parent_[start_index] = start_index;
  scratch.frontier_.push_back(start_index);
  auto visited_count = std::size_t{1};
  auto found = start_index == goal_index;
  [[maybe_unused]] auto touched_missing = false;
  if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
    touched_missing = graph.sparse_.region_reaches_missing_[start_index] != 0;
  }
 
  for (std::size_t head = 0; head < scratch.frontier_.size() && !found;
       ++head) {
    const auto current = scratch.frontier_[head];
    const auto begin = static_cast<std::size_t>(
        graph.adjacency_starts_[static_cast<std::size_t>(current)]);
    const auto end = static_cast<std::size_t>(
        graph.adjacency_starts_[static_cast<std::size_t>(current) + 1]);
    for (auto edge = begin; edge < end; ++edge) {
      const auto target = graph.adjacency_targets_[edge];
      if (scratch.is_visited(target)) {
        continue;
      }
      scratch.visit(target);
      scratch.parent_[target] = current;
      scratch.parent_portal_[target] = graph.adjacency_portals_[edge];
      scratch.frontier_.push_back(target);
      ++visited_count;
      if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
        touched_missing = touched_missing ||
                          graph.sparse_.region_reaches_missing_[target] != 0;
      }
      if (target == goal_index) {
        found = true;
        break;
      }
    }
  }
 
  if (!found) {
    if constexpr (!std::is_same_v<Residency, AlwaysResident>) {
      if (touched_missing) {
        return result(ReachabilityStatus::Indeterminate, visited_count);
      }
    }
    return result(ReachabilityStatus::Unreachable, visited_count);
  }
 
  auto current = goal_index;
  scratch.path_regions_.push_back(graph.region_ref(current));
  while (current != start_index) {
    const auto portal_index = scratch.parent_portal_[current];
    TESS_ASSERT(portal_index < graph.portals_.size());
    scratch.path_portals_.push_back(graph.portals_[portal_index]);
    current = scratch.parent_[current];
    scratch.path_regions_.push_back(graph.region_ref(current));
  }
  std::reverse(scratch.path_regions_.begin(), scratch.path_regions_.end());
  std::reverse(scratch.path_portals_.begin(), scratch.path_portals_.end());
  for (const auto region : scratch.path_regions_) {
    if (std::find(scratch.corridor_chunks_.begin(),
                  scratch.corridor_chunks_.end(),
                  region.chunk) == scratch.corridor_chunks_.end()) {
      scratch.corridor_chunks_.push_back(region.chunk);
    }
  }
 
  using Traits = ShapeTraits<Shape>;
  auto minimum = Coord3{std::numeric_limits<std::int64_t>::max(),
                        std::numeric_limits<std::int64_t>::max(),
                        std::numeric_limits<std::int64_t>::max()};
  auto maximum = Coord3{};
  for (const auto chunk_key_value : scratch.corridor_chunks_) {
    const auto chunk = chunk_coord<Shape>(chunk_key_value);
    const auto begin = Coord3{
        static_cast<std::int64_t>(chunk.x * Traits::chunk.x),
        static_cast<std::int64_t>(chunk.y * Traits::chunk.y),
        static_cast<std::int64_t>(chunk.z * Traits::chunk.z),
    };
    const auto end = Coord3{
        static_cast<std::int64_t>(
            std::min((chunk.x + 1) * Traits::chunk.x, Traits::size.x)),
        static_cast<std::int64_t>(
            std::min((chunk.y + 1) * Traits::chunk.y, Traits::size.y)),
        static_cast<std::int64_t>(
            std::min((chunk.z + 1) * Traits::chunk.z, Traits::size.z)),
    };
    minimum.x = std::min(minimum.x, begin.x);
    minimum.y = std::min(minimum.y, begin.y);
    minimum.z = std::min(minimum.z, begin.z);
    maximum.x = std::max(maximum.x, end.x);
    maximum.y = std::max(maximum.y, end.y);
    maximum.z = std::max(maximum.z, end.z);
  }
 
  auto output = result(ReachabilityStatus::Reachable, visited_count);
  output.bounds = Box3{
      minimum,
      Extent3{static_cast<std::uint64_t>(maximum.x - minimum.x),
              static_cast<std::uint64_t>(maximum.y - minimum.y),
              static_cast<std::uint64_t>(maximum.z - minimum.z)},
  };
  return output;
}
 
// Reports whether `graph` still matches `world` -- i.e. whether a reachability
// query on it would reflect the world's current topology. A precheck MUST
// consult this and fall back to A* when it returns false: a STALE graph can
// return a definitive (but wrong) Unreachable from an outdated snapshot. Const
// and non-mutating -- it recomputes the same staleness test update_region_graph
// applies, WITHOUT triggering a rebuild. Allocation-free; O(chunk_count) dense,
// O(resident_count) sparse (never scans non-resident chunks).
//
// One-graph-per-world contract (sparse): the staleness test reads per-WORLD
// residency-generation clocks, so a graph built on world A can validate as
// fresh against a same-shape world B whose chunks were loaded in the same
// order -- the same cross-world collision class documented at
// storage/sparse_world.h residency_fingerprint(). Keep each graph paired
// with the world it was built from; this check does not detect world swaps.
template <typename World>
[[nodiscard]] auto is_region_graph_fresh(
    const World& world,
    const RegionGraphT<typename World::residency_type>& graph) noexcept
    -> bool {
  using Residency = typename World::residency_type;
  using Shape = typename World::shape_type;
  if constexpr (std::is_same_v<Residency, AlwaysResident>) {
    // Dense: every chunk's stored topology version must still be current. A
    // graph that was never built -- or built for a different shape, detected
    // via the shape binding even when chunk counts coincide -- is not fresh.
    if (graph.local_topologies_.size() != World::chunk_count ||
        !graph.template matches_shape<Shape>()) {
      return false;
    }
    for (std::uint64_t c = 0; c < World::chunk_count; ++c) {
      if (graph.local_topologies_[static_cast<std::size_t>(c)]
              .topology_version() != world.meta(ChunkKey{c}).topology_version) {
        return false;
      }
    }
    return true;
  } else {
    // Sparse: the frozen residency snapshot must still hold (resident_count
    // plus per-key generation -- an evicted key reads generation 0, a
    // rematerialized key a strictly greater one), AND every resident chunk's
    // topology version must still be current (an in-place edit). The generation
    // is checked first so metadata and topology-version reads touch only
    // resident keys.
    const auto count = graph.local_topologies_.size();
    if (count != world.resident_count() ||
        graph.sparse_.frozen_generations_.size() != world.resident_count() ||
        !graph.template matches_shape<Shape>()) {
      return false;
    }
    for (std::size_t i = 0; i < count; ++i) {
      const auto key = graph.sparse_.topology_keys_[i];
      // One directory probe for both facts; the by-key accessors would probe
      // twice per chunk on this per-pathing-tick check. A non-resident key
      // reads generation 0 (meta null),
      // failing the generation compare before meta is touched.
      const auto ref = world.resident_ref(key);
      if (ref.generation != graph.sparse_.frozen_generations_[i]) {
        return false;
      }
      if (graph.local_topologies_[i].topology_version() !=
          ref.meta->topology_version) {
        return false;
      }
    }
    return true;
  }
}
 
// Class-aware freshness: additionally requires the graph's movement-class
// stamp to match `ClassOrTag` (normalized, so a raw tag and its
// UnitCostFieldMovement identity agree). A graph labeled for another class is
// NOT fresh for this one even when every topology version is current -- its
// labels answer a different passability question. The class is the explicit
// first template argument; `World` stays deduced.
template <typename ClassOrTag, typename World>
[[nodiscard]] auto is_region_graph_fresh_for(
    const World& world,
    const RegionGraphT<typename World::residency_type>& graph) noexcept
    -> bool {
  return graph.template matches_class<ClassOrTag>() &&
         is_region_graph_fresh(world, graph);
}
 
}  // namespace tess