package graph

import (
	"sync"
	"sync/atomic"
)

// GraphStats holds summary counts of the graph contents.
type GraphStats struct {
	TotalNodes int            `json:"total_nodes"`
	TotalEdges int            `json:"total_edges"`
	ByKind     map[string]int `json:"by_kind"`
	ByLanguage map[string]int `json:"by_language"`
}

// numShards controls the write-fan-out of the graph. Each shard owns a
// disjoint slice of node IDs (by FNV hash) and its own RWMutex, so
// parallel indexers writing distinct nodes don't contend for a single
// lock. 16 is a good default: even split across typical 8- or 12-core
// machines, small enough that operations which must walk every shard
// (AllNodes, Stats, EvictRepo) stay cheap.
//
// Trade-off: the old graph used one lock per graph; now we have 16, and
// cross-shard operations (AddEdge when source and target are in
// different shards, plus exhaustive reads) lock multiple shards. To
// avoid deadlock we always acquire shards in ascending index order.
const numShards = 16

// edgeKey is the logical identity of an edge — two edges with the same
// key are considered the same edge and dedup to one entry in the
// adjacency lists. Line is part of the key because a caller can hold
// the same target reference at two different call sites and both are
// real call-graph edges (see `foo(); foo();` in the same function).
//
// Both From and To are in the key even though the adjacency lists are
// keyed by one endpoint each — the other endpoint varies within an
// inEdges[to] slice (many From → same To) and within an outEdges[from]
// slice the inverse varies. Without both, property-test graphs with
// several callers to the same callee and no FilePath/Line distinction
// would dedup down to one entry and lose cross-caller traversal.
type edgeKey struct {
	From     string
	To       string
	Kind     EdgeKind
	FilePath string
	Line     int
}

func keyOf(e *Edge) edgeKey {
	return edgeKey{From: e.From, To: e.To, Kind: e.Kind, FilePath: e.FilePath, Line: e.Line}
}

// edgeHash is the stored form of an edge's logical identity. A full
// edgeKey carries four strings plus an int — 72 bytes as a map key or
// sidecar element. Collapsing it to a 128-bit hash shrinks the
// outEdgeIdx / inEdgeIdx maps and the outEdgeKeys / inEdgeKeys sidecars
// by ~4.5×, the single largest line item in cold-warmup resident
// memory. 128 bits keeps a collision between any two distinct edges in
// a graph of realistic size out of reach (~1e-25 at 10M edges), so the
// indexes stay unique-key maps — the dedup and swap-with-last logic is
// byte-for-byte the same as the edgeKey version, only the key type
// changes.
type edgeHash struct{ lo, hi uint64 }

const fnvOffset64 = 1469598103934665603
const fnvPrime64 = 1099511628211

// hashEdgeKey computes the 128-bit identity hash of an edge key. Each
// 64-bit half is an independent FNV-1a pass: distinct seeds plus a
// reversed field order decorrelate the halves so the pair behaves as a
// 128-bit value rather than two views of the same 64-bit hash.
func hashEdgeKey(k edgeKey) edgeHash {
	return edgeHash{
		lo: fnv1aEdge(fnvOffset64, k, false),
		hi: fnv1aEdge(0x9e3779b97f4a7c15, k, true),
	}
}

// fnv1aEdge folds every edgeKey field into one FNV-1a 64-bit hash. A
// 0xff separator after each string keeps "ab"+"c" distinct from
// "a"+"bc"; reversed==true walks the string fields back-to-front.
func fnv1aEdge(seed uint64, k edgeKey, reversed bool) uint64 {
	h := seed
	mix := func(s string) {
		for i := 0; i < len(s); i++ {
			h ^= uint64(s[i])
			h *= fnvPrime64
		}
		h ^= 0xff
		h *= fnvPrime64
	}
	if reversed {
		mix(k.FilePath)
		mix(string(k.Kind))
		mix(k.To)
		mix(k.From)
	} else {
		mix(k.From)
		mix(k.To)
		mix(string(k.Kind))
		mix(k.FilePath)
	}
	h ^= uint64(k.Line)
	h *= fnvPrime64
	return h
}

// hashEdgeIdentity computes the provenance-bearing identity hash of an
// edge: the logical key folded together with Origin. It reuses the
// edgeKey FNV machinery — each 64-bit half is hashEdgeKey's
// corresponding half with the Origin string mixed in as a sixth field
// (same 0xff-separated FNV-1a fold, same reversed-order decorrelation).
//
// This is deliberately distinct from hashEdgeKey: the dedup index
// (outEdgeIdx / inEdgeIdx) stays keyed on the Origin-free logical key
// so an Origin upgrade replaces the slot in place rather than creating
// a parallel edge. The identity hash is the separate value Edge.
// IdentityHash exposes so a provenance change is observable as a
// distinct identity.
func hashEdgeIdentity(k edgeKey, origin string) edgeHash {
	return edgeHash{
		lo: mixOriginInto(fnv1aEdge(fnvOffset64, k, false), origin),
		hi: mixOriginInto(fnv1aEdge(0x9e3779b97f4a7c15, k, true), origin),
	}
}

// mixOriginInto folds the Origin string into an already-computed
// fnv1aEdge hash with the same 0xff-separated FNV-1a step the key
// fields use, so Origin is a first-class sixth field of the identity
// rather than a bolt-on.
func mixOriginInto(h uint64, origin string) uint64 {
	for i := 0; i < len(origin); i++ {
		h ^= uint64(origin[i])
		h *= fnvPrime64
	}
	h ^= 0xff
	h *= fnvPrime64
	return h
}

// shard is a fragment of the graph's data. Each shard holds the node
// metadata for the subset of IDs that hash to it, plus the outgoing
// edges whose source ID is in this shard and the incoming edges whose
// target ID is in this shard. Secondary indexes (byName, byFile, etc.)
// inside a shard only contain nodes owned by that shard; aggregate
// queries iterate every shard and concatenate.
//
// Each slice-valued secondary index has a paired "Idx" sidecar that
// maps an entry's identity to its position in the slice. Two invariants
// the sidecars enforce:
//
//  1. Idempotent writes. AddNode/AddEdge consult the sidecar; duplicate
//     inserts replace the pointer in place instead of appending.
//     Without this, restart paths that load a snapshot and then re-run
//     IndexCtx (which doesn't evict first) silently double every edge
//     and every secondary-index entry. Fixes bug B1 at the write layer,
//     regardless of which call site forgets to evict first.
//  2. O(1) removal via swap-with-last. Removing a node from a
//     byRepo slice of 50k entries with filterEdge-style scanning was
//     O(N); now it's O(1) — flip the last element into the removed
//     slot and shrink the slice by one. Iteration order changes after a
//     removal, but callers that require stable ordering (snapshot
//     encoding) sort before emitting anyway.
type shard struct {
	mu       sync.RWMutex
	nodes    map[string]*Node
	outEdges map[string][]*Edge
	inEdges  map[string][]*Edge
	byFile   map[string][]*Node
	byName   map[string][]*Node
	byQual   map[string]*Node
	byRepo   map[string][]*Node // repoPrefix → nodes owned by this shard

	// Sidecar position indexes — see comment on shard. Reads are
	// unchanged (callers still iterate the slices); only writes
	// consult these maps.
	byFileIdx  map[string]map[string]int   // filePath   → id   → position
	byNameIdx  map[string]map[string]int   // name       → id   → position
	byRepoIdx  map[string]map[string]int   // repoPrefix → id   → position
	outEdgeIdx map[string]map[edgeHash]int // fromID     → hash → position
	inEdgeIdx  map[string]map[edgeHash]int // toID       → hash → position

	// Reverse-index slices that remember each entry's insertion-time
	// edgeHash, parallel to outEdges / inEdges. Required because keyOf
	// is computed from live Edge fields (To, From, ...) — and the
	// resolver mutates Edge.To when retargeting an unresolved edge.
	// During swap-with-last in removeEdgeFromBucket, computing
	// keyOf(swapped) on a swapped element whose To was just mutated
	// produced a different key than the one it was originally indexed
	// under, leaving a stale sidecar position pointing past the slice
	// (panic: "index out of range [42] with length 41" in
	// addEdgeToBucket on the next insert that collided with the stale
	// key). Storing the original hash here makes the swap update
	// independent of live Edge state.
	outEdgeKeys map[string][]edgeHash // fromID → position → hash
	inEdgeKeys  map[string][]edgeHash // toID   → position → hash

	// Running per-repo memory totals maintained under the shard's
	// existing write lock. Reading them out of RepoMemoryEstimate is
	// O(shard count) instead of the O(repo nodes + total edges) walk
	// the function used to do — and AllRepoMemoryEstimates collapses
	// R repo-by-repo queries into one O(R · S) sum. Edges are charged
	// to the source node's RepoPrefix; the shard owning the source
	// edge bucket owns the counter, so accounting matches what the
	// old AllEdges walk attributed.
	repoNodeBytes map[string]uint64
	repoNodeCount map[string]int
	repoEdgeBytes map[string]uint64
	repoEdgeCount map[string]int
}

func newShard() *shard {
	return &shard{
		nodes:         make(map[string]*Node),
		outEdges:      make(map[string][]*Edge),
		inEdges:       make(map[string][]*Edge),
		byFile:        make(map[string][]*Node),
		byName:        make(map[string][]*Node),
		byQual:        make(map[string]*Node),
		byRepo:        make(map[string][]*Node),
		byFileIdx:     make(map[string]map[string]int),
		byNameIdx:     make(map[string]map[string]int),
		byRepoIdx:     make(map[string]map[string]int),
		outEdgeIdx:    make(map[string]map[edgeHash]int),
		inEdgeIdx:     make(map[string]map[edgeHash]int),
		outEdgeKeys:   make(map[string][]edgeHash),
		inEdgeKeys:    make(map[string][]edgeHash),
		repoNodeBytes: make(map[string]uint64),
		repoNodeCount: make(map[string]int),
		repoEdgeBytes: make(map[string]uint64),
		repoEdgeCount: make(map[string]int),
	}
}

// repoNodeAdd registers a node under its RepoPrefix bucket. Caller
// must hold s.mu.Lock. No-op for nodes without a prefix (single-repo
// mode and synthetic nodes that intentionally skip byRepo accounting).
func (s *shard) repoNodeAdd(n *Node) {
	if n == nil || n.RepoPrefix == "" {
		return
	}
	s.repoNodeBytes[n.RepoPrefix] += nodeBytes(n)
	s.repoNodeCount[n.RepoPrefix]++
}

// repoNodeRemove undoes repoNodeAdd. Clamps to zero on underflow so a
// stale counter cannot wrap a uint64.
func (s *shard) repoNodeRemove(n *Node) {
	if n == nil || n.RepoPrefix == "" {
		return
	}
	b := nodeBytes(n)
	if cur := s.repoNodeBytes[n.RepoPrefix]; cur >= b {
		s.repoNodeBytes[n.RepoPrefix] = cur - b
	} else {
		s.repoNodeBytes[n.RepoPrefix] = 0
	}
	if s.repoNodeCount[n.RepoPrefix] > 0 {
		s.repoNodeCount[n.RepoPrefix]--
	}
	if s.repoNodeBytes[n.RepoPrefix] == 0 && s.repoNodeCount[n.RepoPrefix] == 0 {
		delete(s.repoNodeBytes, n.RepoPrefix)
		delete(s.repoNodeCount, n.RepoPrefix)
	}
}

// repoEdgeAdd attributes an edge to its source repo. repoPrefix is the
// source node's RepoPrefix as resolved at the time the edge is
// inserted; storing it here means a later swap of Edge.To (ReindexEdge)
// doesn't have to walk the source-node lookup again.
func (s *shard) repoEdgeAdd(repoPrefix string, e *Edge) {
	if repoPrefix == "" || e == nil {
		return
	}
	s.repoEdgeBytes[repoPrefix] += edgeBytes(e)
	s.repoEdgeCount[repoPrefix]++
}

// repoEdgeRemove undoes repoEdgeAdd. Same clamp-to-zero discipline as
// repoNodeRemove.
func (s *shard) repoEdgeRemove(repoPrefix string, e *Edge) {
	if repoPrefix == "" || e == nil {
		return
	}
	b := edgeBytes(e)
	if cur := s.repoEdgeBytes[repoPrefix]; cur >= b {
		s.repoEdgeBytes[repoPrefix] = cur - b
	} else {
		s.repoEdgeBytes[repoPrefix] = 0
	}
	if s.repoEdgeCount[repoPrefix] > 0 {
		s.repoEdgeCount[repoPrefix]--
	}
	if s.repoEdgeBytes[repoPrefix] == 0 && s.repoEdgeCount[repoPrefix] == 0 {
		delete(s.repoEdgeBytes, repoPrefix)
		delete(s.repoEdgeCount, repoPrefix)
	}
}

// addNodeToBucket appends n to bucket[key] unless an entry with that id
// is already present, in which case the existing slot is overwritten
// with the new pointer. Returns the position of the entry.
func addNodeToBucket(bucket map[string][]*Node, idx map[string]map[string]int, key, id string, n *Node) {
	if inner, ok := idx[key]; ok {
		if pos, exists := inner[id]; exists {
			bucket[key][pos] = n
			return
		}
	}
	pos := len(bucket[key])
	bucket[key] = append(bucket[key], n)
	inner, ok := idx[key]
	if !ok {
		inner = make(map[string]int)
		idx[key] = inner
	}
	inner[id] = pos
}

// removeNodeFromBucket swap-removes the entry with id from bucket[key],
// updating the sidecar position of the swapped-in element. No-op when
// the entry is absent. Cleans up the bucket + sidecar when the last
// entry for key leaves.
func removeNodeFromBucket(bucket map[string][]*Node, idx map[string]map[string]int, key, id string) {
	inner, ok := idx[key]
	if !ok {
		return
	}
	pos, exists := inner[id]
	if !exists {
		return
	}
	slice := bucket[key]
	last := len(slice) - 1
	if pos != last {
		swapped := slice[last]
		slice[pos] = swapped
		inner[swapped.ID] = pos
	}
	slice = slice[:last]
	delete(inner, id)
	if len(inner) == 0 {
		delete(idx, key)
		delete(bucket, key)
	} else {
		bucket[key] = slice
	}
}

// addEdgeToBucket appends e to bucket[key] unless an entry with the
// same logical identity (edgeKey) is already there, in which case the
// existing slot is overwritten. Reports whether this was a new insert
// and, on an in-place replace, whether the replacement carried a
// different Origin than the edge it displaced.
//
// keys is the parallel slice that remembers each slot's insertion-time
// edgeKey so removeEdgeFromBucket can update sidecars without
// recomputing keyOf on a possibly-mutated swapped Edge.
//
// originChanged surfaces the resolver path where an edge is re-added
// (via AddEdge) with upgraded provenance rather than mutated in place:
// the logical key still matches, so the slot is replaced, but the
// edge's identity has changed. AddEdge funnels this into the
// graph-level identity-revision counter so that re-add path is as
// observable as an explicit SetEdgeProvenance call.
func addEdgeToBucket(bucket map[string][]*Edge, keys map[string][]edgeHash, idx map[string]map[edgeHash]int, key string, e *Edge) (inserted, originChanged bool) {
	h := hashEdgeKey(keyOf(e))
	if inner, ok := idx[key]; ok {
		if pos, exists := inner[h]; exists {
			old := bucket[key][pos]
			originChanged = old != nil && old != e && old.Origin != e.Origin
			bucket[key][pos] = e
			// keys[key][pos] already equals h — same logical identity.
			return false, originChanged
		}
	}
	pos := len(bucket[key])
	bucket[key] = append(bucket[key], e)
	keys[key] = append(keys[key], h)
	inner, ok := idx[key]
	if !ok {
		inner = make(map[edgeHash]int)
		idx[key] = inner
	}
	inner[h] = pos
	return true, false
}

// removeEdgeFromBucket removes the entry with key k from bucket[key]
// using swap-with-last, maintaining the sidecar. No-op when absent.
func removeEdgeFromBucket(bucket map[string][]*Edge, keys map[string][]edgeHash, idx map[string]map[edgeHash]int, key string, k edgeHash) bool {
	inner, ok := idx[key]
	if !ok {
		return false
	}
	pos, exists := inner[k]
	if !exists {
		return false
	}
	slice := bucket[key]
	keySlice := keys[key]
	last := len(slice) - 1
	if pos != last {
		slice[pos] = slice[last]
		// Use the swapped slot's STORED insertion-time hash, not
		// hashEdgeKey(keyOf(swapped)). The Edge's To may have been
		// mutated by the resolver between insertion and now, in which
		// case keyOf would yield a different hash than the sidecar
		// entry that actually points at this slot — leaking a stale
		// "last" position that later panics in addEdgeToBucket.
		swappedKey := keySlice[last]
		keySlice[pos] = swappedKey
		inner[swappedKey] = pos
	}
	slice = slice[:last]
	keySlice = keySlice[:last]
	delete(inner, k)
	if len(inner) == 0 {
		delete(idx, key)
		delete(bucket, key)
		delete(keys, key)
	} else {
		bucket[key] = slice
		keys[key] = keySlice
	}
	return true
}

// Graph is a thread-safe in-memory knowledge graph. Internally sharded
// by node-ID hash so writers touching disjoint IDs run in parallel.
//
// resolveMu is a graph-wide lock shared by every resolver.Resolver
// constructed against this Graph. Per-shard locks protect individual
// node/edge writes, but resolution phases (ResolveAll, ResolveFile)
// iterate every shard and mutate edge targets in place — two
// resolvers racing on the same edge produced the data race that
// MultiIndexer.indexMultiRepo triggered when its per-repo goroutines
// each created their own Resolver. Routing every resolver through
// this single mutex serialises those phases without blocking
// ordinary shard-scoped reads and writes.
type Graph struct {
	shards    [numShards]*shard
	resolveMu sync.Mutex
	// edgeIdentityRevisions counts how many times an in-graph edge's
	// provenance-bearing identity changed — i.e. its Origin was
	// upgraded or reverted while its logical (From,To,Kind,FilePath,
	// Line) key stayed fixed. Each such change is conceptually a
	// retirement of the old identity and creation of a new one. Both
	// sanctioned mutation paths feed this counter: SetEdgeProvenance
	// (an explicit in-place change) and addEdgeToBucket's in-place
	// replace branch (a re-add of the same logical edge carrying an
	// upgraded Origin). The count is the tamper-evidence surface:
	// provenance cannot churn without it moving.
	edgeIdentityRevisions atomic.Int64
}

// New creates an empty graph.
func New() *Graph {
	g := &Graph{}
	for i := range g.shards {
		g.shards[i] = newShard()
	}
	return g
}

// ResolveMutex returns the graph-wide mutex resolvers use to
// serialise resolution phases against this graph. Exposed for the
// resolver package; every Resolver built from the same Graph shares
// the same lock.
func (g *Graph) ResolveMutex() *sync.Mutex {
	return &g.resolveMu
}

// shardIdx picks the shard index for an ID using FNV-1a. Inlined to
// avoid the per-call hash-object allocation that the stdlib's
// fnv.New32a() incurs — shardIdx is on the hottest path in the graph
// (every AddNode / AddEdge / GetNode call), and the heap profile shows
// 690 MB/30 s of fnv state allocations during cold-start indexing.
func shardIdx(id string) int {
	var h uint32 = 2166136261
	for i := 0; i < len(id); i++ {
		h ^= uint32(id[i])
		h *= 16777619
	}
	return int(h % numShards)
}

// shardFor returns the shard that owns the given ID.
func (g *Graph) shardFor(id string) *shard {
	return g.shards[shardIdx(id)]
}

// lockTwoWrite locks two shards for write in ascending index order to
// prevent deadlock. If both IDs land in the same shard, the mutex is
// locked exactly once. Returns a closure the caller defers to unlock.
func (g *Graph) lockTwoWrite(idA, idB string) func() {
	a := shardIdx(idA)
	b := shardIdx(idB)
	if a == b {
		s := g.shards[a]
		s.mu.Lock()
		return s.mu.Unlock
	}
	lo, hi := a, b
	if lo > hi {
		lo, hi = hi, lo
	}
	sLo := g.shards[lo]
	sHi := g.shards[hi]
	sLo.mu.Lock()
	sHi.mu.Lock()
	return func() {
		sHi.mu.Unlock()
		sLo.mu.Unlock()
	}
}

// lockThreeWrite locks up to three shards for write in ascending index
// order, deduplicating any that collide. Used by ReindexEdge, which
// mutates the From shard's outEdgeIdx plus both in-edge buckets when a
// resolver step retargets an edge; missing any of the three races with
// concurrent AddEdge on that shard (bug: "concurrent map read and map
// write" in addEdgeToBucket).
func (g *Graph) lockThreeWrite(idA, idB, idC string) func() {
	a, b, c := shardIdx(idA), shardIdx(idB), shardIdx(idC)
	// Sort (a, b, c) ascending without allocating a slice.
	if a > b {
		a, b = b, a
	}
	if b > c {
		b, c = c, b
	}
	if a > b {
		a, b = b, a
	}
	// Dedupe: lock each distinct index once.
	idxs := [3]int{a, -1, -1}
	n := 1
	if b != a {
		idxs[n] = b
		n++
	}
	if c != b && c != a {
		idxs[n] = c
		n++
	}
	for i := 0; i < n; i++ {
		g.shards[idxs[i]].mu.Lock()
	}
	return func() {
		for i := n - 1; i >= 0; i-- {
			g.shards[idxs[i]].mu.Unlock()
		}
	}
}

// lockAllWrite / lockAllRead take every shard's lock in order. Used by
// operations that have to touch the whole graph (AllNodes, Stats,
// EvictRepo). Callers must match with unlockAllWrite / unlockAllRead.
func (g *Graph) lockAllWrite() {
	for _, s := range g.shards {
		s.mu.Lock()
	}
}

func (g *Graph) unlockAllWrite() {
	for i := len(g.shards) - 1; i >= 0; i-- {
		g.shards[i].mu.Unlock()
	}
}

func (g *Graph) lockAllRead() {
	for _, s := range g.shards {
		s.mu.RLock()
	}
}

func (g *Graph) unlockAllRead() {
	for i := len(g.shards) - 1; i >= 0; i-- {
		g.shards[i].mu.RUnlock()
	}
}

// AddNode inserts or updates a node in the graph and all secondary
// indexes. Idempotent — a second call with the same ID replaces the
// existing Node pointer in place instead of appending duplicates to the
// byFile / byName / byRepo slices. If the new Node's FilePath, Name, or
// RepoPrefix differs from the stored one, the secondary-index entries
// are migrated from the old bucket to the new one atomically under the
// shard lock.
func (g *Graph) AddNode(n *Node) {
	s := g.shardFor(n.ID)
	s.mu.Lock()
	g.addNodeLocked(s, n)
	s.mu.Unlock()
}

// addNodeLocked is AddNode's body, expecting the caller to already hold
// the shard's write lock. Used by AddBatch to amortise lock acquisition
// across many node inserts targeting the same shard.
func (g *Graph) addNodeLocked(s *shard, n *Node) {
	prev, hadPrev := s.nodes[n.ID]
	// Subtract the previous size/count before overwriting; the new
	// node's contribution is re-added after the RepoPrefix-preservation
	// logic below has settled on the final prefix.
	if hadPrev {
		s.repoNodeRemove(prev)
	}
	s.nodes[n.ID] = n

	if hadPrev {
		if prev.FilePath != n.FilePath {
			removeNodeFromBucket(s.byFile, s.byFileIdx, prev.FilePath, n.ID)
		}
		if prev.Name != n.Name {
			removeNodeFromBucket(s.byName, s.byNameIdx, prev.Name, n.ID)
		}
		if prev.QualName != n.QualName && prev.QualName != "" {
			// byQual is a 1:1 index, not a slice — only delete when
			// the stored entry still points at this node ID (a
			// different node may have since taken the slot).
			if cur, ok := s.byQual[prev.QualName]; ok && cur.ID == n.ID {
				delete(s.byQual, prev.QualName)
			}
		}
		if prev.RepoPrefix != n.RepoPrefix && prev.RepoPrefix != "" {
			// Preserve a previously-set RepoPrefix rather than letting
			// an empty-prefix re-add silently strip the node out of its
			// byRepo bucket. The downgrade-to-empty case has no
			// legitimate caller (contract nodes use distinct IDs that
			// never collide with symbol IDs; the parse and IncrementalReindex
			// paths route through applyRepoPrefix which always stamps
			// the active idx.repoPrefix on the new node) and previously
			// caused per-repo `byRepo[prefix]` to drain mid-warmup,
			// breaking RepoStats / RepoMemoryEstimate / GetRepoNodes.
			// Restore the old prefix on the new node so the bucket
			// stays populated. The legitimate RepoPrefix-change case
			// (snapshot prefix → new prefix because config moved) still
			// works because n.RepoPrefix is non-empty there.
			if n.RepoPrefix == "" {
				n.RepoPrefix = prev.RepoPrefix
			} else {
				removeNodeFromBucket(s.byRepo, s.byRepoIdx, prev.RepoPrefix, n.ID)
			}
		}
	}

	addNodeToBucket(s.byFile, s.byFileIdx, n.FilePath, n.ID, n)
	addNodeToBucket(s.byName, s.byNameIdx, n.Name, n.ID, n)
	if n.QualName != "" {
		s.byQual[n.QualName] = n
	}
	if n.RepoPrefix != "" {
		addNodeToBucket(s.byRepo, s.byRepoIdx, n.RepoPrefix, n.ID, n)
	}
	s.repoNodeAdd(n)
}

// AddBatch inserts a set of nodes and edges in shard-grouped passes,
// acquiring each involved shard's write lock at most once across the
// whole batch. Replaces the O(N + 2E) per-item lock acquisitions of
// AddNode / AddEdge with O(distinct_shards) — typically ~16 instead of
// ~450 per per-file worker batch. The contention profile measured 69
// of 102 goroutines blocked on lockTwoWrite during cold-start parsing;
// batching is the throughput fix.
//
// Observable semantics differ slightly from a sequence of AddNode /
// AddEdge calls: for cross-shard edges, the From shard's outEdges
// receives the edge before the To shard's inEdges does. Readers that
// query one side only see the change atomically per shard; readers
// that join both sides may briefly see an outgoing edge whose
// reciprocal in-edge hasn't landed yet. The parser worker path that
// drives this is followed by ResolveAll / global derivation passes
// that take the resolver mutex graph-wide, so no concurrent reader is
// expected to depend on cross-side atomicity during warmup.
func (g *Graph) AddBatch(nodes []*Node, edges []*Edge) {
	if len(nodes) == 0 && len(edges) == 0 {
		return
	}
	var nodesByShard [numShards][]*Node
	var outEdgesByShard [numShards][]*Edge
	var inEdgesByShard [numShards][]*Edge
	for _, n := range nodes {
		if n == nil || n.ID == "" {
			continue
		}
		i := shardIdx(n.ID)
		nodesByShard[i] = append(nodesByShard[i], n)
	}
	for _, e := range edges {
		if e == nil {
			continue
		}
		outEdgesByShard[shardIdx(e.From)] = append(outEdgesByShard[shardIdx(e.From)], e)
		inEdgesByShard[shardIdx(e.To)] = append(inEdgesByShard[shardIdx(e.To)], e)
	}

	for i := 0; i < numShards; i++ {
		if len(nodesByShard[i]) == 0 && len(outEdgesByShard[i]) == 0 && len(inEdgesByShard[i]) == 0 {
			continue
		}
		s := g.shards[i]
		s.mu.Lock()
		for _, n := range nodesByShard[i] {
			g.addNodeLocked(s, n)
		}
		// Out-side writes own the "was this a new insert?" signal that
		// drives the per-repo edge counter and the "did Origin change?"
		// signal that drives the identity-revision counter — the in-side
		// write is bookkeeping only and charges neither (mirrors
		// AddEdge's behaviour).
		for _, e := range outEdgesByShard[i] {
			inserted, originChanged := addEdgeToBucket(s.outEdges, s.outEdgeKeys, s.outEdgeIdx, e.From, e)
			if originChanged {
				g.edgeIdentityRevisions.Add(1)
			}
			if inserted {
				var srcRepo string
				if src, ok := s.nodes[e.From]; ok && src != nil {
					srcRepo = src.RepoPrefix
				}
				s.repoEdgeAdd(srcRepo, e)
			}
		}
		for _, e := range inEdgesByShard[i] {
			addEdgeToBucket(s.inEdges, s.inEdgeKeys, s.inEdgeIdx, e.To, e)
		}
		s.mu.Unlock()
	}
}

// AddEdge inserts or updates a directed edge in the graph. Locks both
// the From and To shards (same shard locked once if they collide) so
// outEdges and inEdges stay consistent. Idempotent: a second call with
// the same (From, To, Kind, FilePath, Line) replaces the stored *Edge
// pointer in place — newer metadata (Confidence, Origin, etc.) wins,
// adjacency-list length is unchanged. Drops the double-edge problem
// that used to surface after daemon restarts (bug B1).
func (g *Graph) AddEdge(e *Edge) {
	unlock := g.lockTwoWrite(e.From, e.To)
	defer unlock()
	sFrom := g.shardFor(e.From)
	sTo := g.shardFor(e.To)
	// Only charge the source-repo counter on a brand-new insert.
	// Idempotent re-adds (same edgeKey) replace the slot in place and
	// would otherwise double-count. addEdgeToBucket reports inserted ==
	// true only when it actually appended. The out-side write owns both
	// signals: the new-insert flag (per-repo counter) and the origin-
	// changed flag (identity-revision counter). The in-side write is
	// bookkeeping only — charging either counter there would double it.
	inserted, originChanged := addEdgeToBucket(sFrom.outEdges, sFrom.outEdgeKeys, sFrom.outEdgeIdx, e.From, e)
	addEdgeToBucket(sTo.inEdges, sTo.inEdgeKeys, sTo.inEdgeIdx, e.To, e)
	if originChanged {
		// A re-add with the same logical key but an upgraded Origin:
		// the old identity is retired, a new one created.
		g.edgeIdentityRevisions.Add(1)
	}
	if inserted {
		var srcRepo string
		if src, ok := sFrom.nodes[e.From]; ok && src != nil {
			srcRepo = src.RepoPrefix
		}
		sFrom.repoEdgeAdd(srcRepo, e)
	}
}

// SetEdgeProvenance changes the Origin of an edge already in the graph
// and is the only sanctioned way to do so. Conceptually it is a
// delete-then-insert of the edge's identity: because Origin is part of
// IdentityHash, the old provenance-bearing identity is retired and a
// new one created — even though the logical (From,To,Kind,FilePath,
// Line) key, and therefore the adjacency-list slot, is unchanged.
//
// It computes the edge's old and new IdentityHash. When they are equal
// (newOrigin matches the current Origin) nothing changes and it returns
// false. When they differ it applies e.Origin = newOrigin, re-derives
// the Origin-derived Tier label when one was set (Confidence and
// ConfidenceLabel are score-derived, not Origin-derived, so they are
// left intact), increments the graph-level identity-revision counter,
// and returns true.
//
// Mutating Edge.Origin directly on an in-graph edge bypasses the
// counter and is a provenance-tampering bug — route every such change
// here so the churn stays observable via EdgeIdentityRevisions.
func (g *Graph) SetEdgeProvenance(e *Edge, newOrigin string) bool {
	if e == nil {
		return false
	}
	unlock := g.lockTwoWrite(e.From, e.To)
	defer unlock()
	oldIdentity := e.IdentityHash()
	newIdentity := hashEdgeIdentity(keyOf(e), newOrigin)
	if oldIdentity == newIdentity {
		return false
	}
	e.Origin = newOrigin
	// Tier is a pure projection of Origin (graph.ResolvedBy). Re-derive
	// it only when it was already populated — an empty Tier is the
	// in-memory default and re-deriving would silently start stamping
	// it. The same *Edge pointer lives in both the out- and in-edge
	// buckets, so this write is visible from every adjacency view.
	if e.Tier != "" {
		e.Tier = ResolvedBy(newOrigin)
	}
	g.edgeIdentityRevisions.Add(1)
	return true
}

// EdgeIdentityRevisions returns how many times an in-graph edge's
// provenance-bearing identity has changed over this graph's lifetime —
// the running total fed by SetEdgeProvenance and by AddEdge's in-place
// re-add path. It is monotonic and never decremented; a reindex that
// retires and recreates edges does not roll it back. Surfaced through
// graph_stats as the tamper-evidence signal for provenance churn.
func (g *Graph) EdgeIdentityRevisions() int {
	return int(g.edgeIdentityRevisions.Load())
}

// VerifyEdgeIdentities walks every edge and confirms its provenance-
// bearing identity is internally consistent: the edge stored in a
// source node's outEdges bucket and the edge stored in the target
// node's inEdges bucket are the same *Edge pointer and therefore agree
// on IdentityHash. addEdgeToBucket stores one shared pointer in both
// buckets, so a consistent graph always passes; a divergence means
// some code mutated Origin on a copied edge (e.g. a resolver clone)
// and wrote it into only one adjacency view, leaving the two sides
// disagreeing about provenance. Returns nil when every edge is
// consistent, or an error naming the first divergent edge.
//
// This is the assertion a test uses to prove provenance cannot be
// silently changed outside SetEdgeProvenance.
func (g *Graph) VerifyEdgeIdentities() error {
	g.lockAllRead()
	defer g.unlockAllRead()
	for _, s := range g.shards {
		for _, edges := range s.outEdges {
			for _, e := range edges {
				if e == nil {
					continue
				}
				want := e.IdentityHash()
				sTo := g.shardFor(e.To)
				found := false
				for _, in := range sTo.inEdges[e.To] {
					if in == e {
						if in.IdentityHash() != want {
							return &edgeIdentityError{edge: e, reason: "inEdges pointer disagrees on identity hash"}
						}
						found = true
						break
					}
				}
				if !found {
					return &edgeIdentityError{edge: e, reason: "outEdges edge missing from target inEdges bucket"}
				}
			}
		}
	}
	return nil
}

// edgeIdentityError reports the first edge VerifyEdgeIdentities found
// to be inconsistent across the out- and in-edge adjacency views.
type edgeIdentityError struct {
	edge   *Edge
	reason string
}

func (e *edgeIdentityError) Error() string {
	return "edge identity inconsistent (" + e.reason + "): " +
		e.edge.From + " -" + string(e.edge.Kind) + "-> " + e.edge.To
}

// ReindexEdge updates the inEdges index after an edge's To field has
// been mutated (e.g., by the resolver changing "unresolved::X" to a
// real target). oldTo is the previous value of e.To before mutation.
//
// Three sidecar entries change: the outEdgeIdx key for From (since the
// edgeKey depends on To), the inEdgeIdx entry on the old target bucket
// (removed), and the inEdgeIdx entry on the new target bucket (added).
func (g *Graph) ReindexEdge(e *Edge, oldTo string) {
	if oldTo == e.To {
		return
	}
	// Must lock the From shard too — we mutate sFrom.outEdgeIdx below,
	// and without its lock a concurrent AddEdge on From panics the
	// runtime with "concurrent map read and map write".
	unlock := g.lockThreeWrite(e.From, oldTo, e.To)
	defer unlock()

	// Old identity uses oldTo; the current edge struct already has the
	// new To set, so we reconstruct the key before mutation.
	oldKey := hashEdgeKey(edgeKey{From: e.From, To: oldTo, Kind: e.Kind, FilePath: e.FilePath, Line: e.Line})
	newKey := hashEdgeKey(keyOf(e))

	sFrom := g.shardFor(e.From)
	// outEdges slot position doesn't move — only the key under which
	// the sidecar records it changes. Avoid a churn of slice growth by
	// swapping the sidecar entry in place.
	//
	// The parallel outEdgeKeys slice MUST be updated alongside
	// outEdgeIdx. removeEdgeFromBucket reads outEdgeKeys[pos] to
	// learn the swapped slot's insertion-time key during swap-with-
	// last; leaving outEdgeKeys stale here would re-insert the old
	// key into outEdgeIdx pointing at a swapped position, and the
	// next swap on that key would compute a pos past the (now
	// shorter) slice — the exact index-out-of-range panic that
	// surfaces during evictEdgesLocked when warmup retargets a lot
	// of edges via ReindexEdge.
	if fromIdx, ok := sFrom.outEdgeIdx[e.From]; ok {
		if pos, exists := fromIdx[oldKey]; exists {
			delete(fromIdx, oldKey)
			fromIdx[newKey] = pos
			if keys, ok := sFrom.outEdgeKeys[e.From]; ok && pos < len(keys) {
				keys[pos] = newKey
			}
		}
	}

	// Move from the old target's inEdges bucket to the new one.
	sOld := g.shardFor(oldTo)
	removeEdgeFromBucket(sOld.inEdges, sOld.inEdgeKeys, sOld.inEdgeIdx, oldTo, oldKey)
	sNew := g.shardFor(e.To)
	addEdgeToBucket(sNew.inEdges, sNew.inEdgeKeys, sNew.inEdgeIdx, e.To, e)
}

// GetNode returns a node by ID, or nil if not found.
func (g *Graph) GetNode(id string) *Node {
	s := g.shardFor(id)
	s.mu.RLock()
	defer s.mu.RUnlock()
	return s.nodes[id]
}

// GetNodeByQualName returns a node by fully-qualified name, or nil.
// The qual name index is partitioned across shards (each shard owns the
// qual names of the nodes it stores), so we ask every shard.
func (g *Graph) GetNodeByQualName(qualName string) *Node {
	for _, s := range g.shards {
		s.mu.RLock()
		if n, ok := s.byQual[qualName]; ok {
			s.mu.RUnlock()
			return n
		}
		s.mu.RUnlock()
	}
	return nil
}

// FindNodesByName returns all nodes matching the short name.
func (g *Graph) FindNodesByName(name string) []*Node {
	var out []*Node
	for _, s := range g.shards {
		s.mu.RLock()
		if src := s.byName[name]; len(src) > 0 {
			out = append(out, src...)
		}
		s.mu.RUnlock()
	}
	return out
}

// GetFileNodes returns all nodes defined in the given file.
func (g *Graph) GetFileNodes(filePath string) []*Node {
	var out []*Node
	for _, s := range g.shards {
		s.mu.RLock()
		if src := s.byFile[filePath]; len(src) > 0 {
			out = append(out, src...)
		}
		s.mu.RUnlock()
	}
	return out
}

// GetOutEdges returns outgoing edges for a node.
func (g *Graph) GetOutEdges(nodeID string) []*Edge {
	s := g.shardFor(nodeID)
	s.mu.RLock()
	defer s.mu.RUnlock()
	src := s.outEdges[nodeID]
	out := make([]*Edge, len(src))
	copy(out, src)
	return out
}

// GetInEdges returns incoming edges for a node.
func (g *Graph) GetInEdges(nodeID string) []*Edge {
	s := g.shardFor(nodeID)
	s.mu.RLock()
	defer s.mu.RUnlock()
	src := s.inEdges[nodeID]
	out := make([]*Edge, len(src))
	copy(out, src)
	return out
}

// EvictFile removes all nodes and edges belonging to the given file
// path. Nodes for one file can span many shards (different IDs hash
// differently), so we lock all shards for this multi-shard operation.
func (g *Graph) EvictFile(filePath string) (nodesRemoved, edgesRemoved int) {
	g.lockAllWrite()
	defer g.unlockAllWrite()

	// Gather nodes across shards.
	var nodes []*Node
	for _, s := range g.shards {
		nodes = append(nodes, s.byFile[filePath]...)
	}
	if len(nodes) == 0 {
		return 0, 0
	}
	// id → source-repo captured BEFORE we delete the node from
	// s.nodes; evictEdgesLocked needs the repo to debit per-repo
	// edge counters and the live node would already be gone.
	evictedIDs := make(map[string]string, len(nodes))
	for _, n := range nodes {
		evictedIDs[n.ID] = n.RepoPrefix
	}

	for _, n := range nodes {
		s := g.shardFor(n.ID)
		s.repoNodeRemove(n)
		delete(s.nodes, n.ID)
		if n.QualName != "" {
			if cur, ok := s.byQual[n.QualName]; ok && cur.ID == n.ID {
				delete(s.byQual, n.QualName)
			}
		}
		removeNodeFromBucket(s.byName, s.byNameIdx, n.Name, n.ID)
		removeNodeFromBucket(s.byFile, s.byFileIdx, filePath, n.ID)
		if n.RepoPrefix != "" {
			removeNodeFromBucket(s.byRepo, s.byRepoIdx, n.RepoPrefix, n.ID)
		}
	}
	nodesRemoved = len(nodes)

	edgesRemoved = g.evictEdgesLocked(evictedIDs)
	return nodesRemoved, edgesRemoved
}

// evictEdgesLocked is the shared edge-removal core used by EvictFile
// and EvictRepo. Callers must hold every shard's write lock.
//
// For each evicted node we remove its outEdges and inEdges entries. To
// clean the reverse index on non-evicted endpoints we do a swap-with-
// last removal via sidecar, which is O(1) per edge instead of the
// O(slice-size) filterEdge scan the older implementation used.
func (g *Graph) evictEdgesLocked(evictedIDs map[string]string) int {
	removed := 0

	// Phase 1: remove outgoing edges from every evicted node. Use the
	// parallel outEdgeKeys slice to look up each entry's insertion-time
	// edgeKey rather than recomputing keyOf — the latter races with
	// resolver-driven Edge.To mutations elsewhere in the graph and
	// can yield a key that doesn't match the inEdges sidecar.
	for id, srcRepo := range evictedIDs {
		s := g.shardFor(id)
		edges := s.outEdges[id]
		keys := s.outEdgeKeys[id]
		removed += len(edges)
		for i, e := range edges {
			s.repoEdgeRemove(srcRepo, e)
			if _, evicted := evictedIDs[e.To]; !evicted {
				sTo := g.shardFor(e.To)
				removeEdgeFromBucket(sTo.inEdges, sTo.inEdgeKeys, sTo.inEdgeIdx, e.To, keys[i])
			}
		}
		delete(s.outEdges, id)
		delete(s.outEdgeKeys, id)
		delete(s.outEdgeIdx, id)
	}

	// Phase 2: remove incoming edges to every evicted node (from
	// non-evicted sources — same-direction edges were already handled
	// in phase 1 and counted). Each surviving source's repo is read
	// from its live node — sFrom.nodes[e.From] is still present in
	// this phase because that source wasn't evicted.
	for id := range evictedIDs {
		s := g.shardFor(id)
		edges := s.inEdges[id]
		keys := s.inEdgeKeys[id]
		for i, e := range edges {
			if _, evicted := evictedIDs[e.From]; !evicted {
				removed++
				sFrom := g.shardFor(e.From)
				var srcRepo string
				if src, ok := sFrom.nodes[e.From]; ok && src != nil {
					srcRepo = src.RepoPrefix
				}
				removeEdgeFromBucket(sFrom.outEdges, sFrom.outEdgeKeys, sFrom.outEdgeIdx, e.From, keys[i])
				sFrom.repoEdgeRemove(srcRepo, e)
			}
		}
		delete(s.inEdges, id)
		delete(s.inEdgeKeys, id)
		delete(s.inEdgeIdx, id)
	}

	return removed
}

// RemoveEdge removes a specific edge by from, to, and kind. Returns
// true if the edge was found and removed. When multiple edges match
// (same from/to/kind but different file/line — rare but possible),
// removes the first one encountered.
func (g *Graph) RemoveEdge(from, to string, kind EdgeKind) bool {
	unlock := g.lockTwoWrite(from, to)
	defer unlock()

	sFrom := g.shardFor(from)
	outList := sFrom.outEdges[from]
	outKeys := sFrom.outEdgeKeys[from]
	targetIdx := -1
	for i, e := range outList {
		if e.To == to && e.Kind == kind {
			targetIdx = i
			break
		}
	}
	if targetIdx < 0 {
		return false
	}

	// Snapshot the edge plus its source-repo before mutating the
	// buckets — once removeEdgeFromBucket swaps the tail in, outList[i]
	// is no longer the edge we're removing.
	removed := outList[targetIdx]
	var srcRepo string
	if src, ok := sFrom.nodes[from]; ok && src != nil {
		srcRepo = src.RepoPrefix
	}

	// Use the stored insertion-time key rather than keyOf(target) so
	// removal is robust against in-flight Edge.To mutations.
	k := outKeys[targetIdx]
	removeEdgeFromBucket(sFrom.outEdges, sFrom.outEdgeKeys, sFrom.outEdgeIdx, from, k)
	sTo := g.shardFor(to)
	removeEdgeFromBucket(sTo.inEdges, sTo.inEdgeKeys, sTo.inEdgeIdx, to, k)
	sFrom.repoEdgeRemove(srcRepo, removed)
	return true
}

// NodeCount returns the total number of nodes.
func (g *Graph) NodeCount() int {
	total := 0
	for _, s := range g.shards {
		s.mu.RLock()
		total += len(s.nodes)
		s.mu.RUnlock()
	}
	return total
}

// EdgeCount returns the total number of edges.
func (g *Graph) EdgeCount() int {
	total := 0
	for _, s := range g.shards {
		s.mu.RLock()
		for _, edges := range s.outEdges {
			total += len(edges)
		}
		s.mu.RUnlock()
	}
	return total
}

// AllNodes returns a snapshot of all nodes. Locks every shard for read
// to produce a coherent view — callers use this for snapshots,
// contracts extraction, etc. where a consistent crop matters.
func (g *Graph) AllNodes() []*Node {
	g.lockAllRead()
	defer g.unlockAllRead()
	total := 0
	for _, s := range g.shards {
		total += len(s.nodes)
	}
	out := make([]*Node, 0, total)
	for _, s := range g.shards {
		for _, n := range s.nodes {
			out = append(out, n)
		}
	}
	return out
}

// AllEdges returns a snapshot of all edges.
func (g *Graph) AllEdges() []*Edge {
	g.lockAllRead()
	defer g.unlockAllRead()
	var out []*Edge
	for _, s := range g.shards {
		for _, edges := range s.outEdges {
			out = append(out, edges...)
		}
	}
	return out
}

// Stats returns summary counts by kind and language.
func (g *Graph) Stats() GraphStats {
	g.lockAllRead()
	defer g.unlockAllRead()

	byKind := make(map[string]int)
	byLang := make(map[string]int)
	totalNodes := 0
	for _, s := range g.shards {
		totalNodes += len(s.nodes)
		for _, n := range s.nodes {
			byKind[string(n.Kind)]++
			if n.Language != "" {
				byLang[n.Language]++
			}
		}
	}

	edgeCount := 0
	for _, s := range g.shards {
		for _, edges := range s.outEdges {
			edgeCount += len(edges)
		}
	}

	return GraphStats{
		TotalNodes: totalNodes,
		TotalEdges: edgeCount,
		ByKind:     byKind,
		ByLanguage: byLang,
	}
}

// GetRepoNodes returns all nodes belonging to the given repository
// prefix. Each shard holds a byRepo slice for nodes it owns; we
// aggregate across shards.
func (g *Graph) GetRepoNodes(repoPrefix string) []*Node {
	var out []*Node
	for _, s := range g.shards {
		s.mu.RLock()
		if src := s.byRepo[repoPrefix]; len(src) > 0 {
			out = append(out, src...)
		}
		s.mu.RUnlock()
	}
	return out
}

// EvictRepo removes all nodes with matching RepoPrefix and all edges
// referencing those nodes. Returns counts of removed nodes and edges.
func (g *Graph) EvictRepo(repoPrefix string) (nodesRemoved, edgesRemoved int) {
	g.lockAllWrite()
	defer g.unlockAllWrite()

	var nodes []*Node
	for _, s := range g.shards {
		nodes = append(nodes, s.byRepo[repoPrefix]...)
	}
	if len(nodes) == 0 {
		return 0, 0
	}
	evictedIDs := make(map[string]string, len(nodes))
	for _, n := range nodes {
		evictedIDs[n.ID] = repoPrefix
	}

	for _, n := range nodes {
		s := g.shardFor(n.ID)
		s.repoNodeRemove(n)
		delete(s.nodes, n.ID)
		if n.QualName != "" {
			if cur, ok := s.byQual[n.QualName]; ok && cur.ID == n.ID {
				delete(s.byQual, n.QualName)
			}
		}
		removeNodeFromBucket(s.byName, s.byNameIdx, n.Name, n.ID)
		removeNodeFromBucket(s.byFile, s.byFileIdx, n.FilePath, n.ID)
		removeNodeFromBucket(s.byRepo, s.byRepoIdx, repoPrefix, n.ID)
	}
	nodesRemoved = len(nodes)

	edgesRemoved = g.evictEdgesLocked(evictedIDs)
	return nodesRemoved, edgesRemoved
}

// RepoStats returns per-repository node and edge counts.
func (g *Graph) RepoStats() map[string]GraphStats {
	g.lockAllRead()
	defer g.unlockAllRead()

	// Aggregate byRepo across shards first.
	repoNodes := make(map[string][]*Node)
	for _, s := range g.shards {
		for prefix, nodes := range s.byRepo {
			repoNodes[prefix] = append(repoNodes[prefix], nodes...)
		}
	}

	stats := make(map[string]GraphStats, len(repoNodes))
	repoByKind := make(map[string]map[string]int)
	repoByLang := make(map[string]map[string]int)
	repoNodeCount := make(map[string]int)
	for prefix, nodes := range repoNodes {
		repoNodeCount[prefix] = len(nodes)
		byKind := make(map[string]int)
		byLang := make(map[string]int)
		for _, n := range nodes {
			byKind[string(n.Kind)]++
			if n.Language != "" {
				byLang[n.Language]++
			}
		}
		repoByKind[prefix] = byKind
		repoByLang[prefix] = byLang
	}

	// Count edges per repo by the From node's repo. Need to look up the
	// From node in whichever shard owns it.
	repoEdgeCount := make(map[string]int)
	for _, s := range g.shards {
		for _, edges := range s.outEdges {
			for _, e := range edges {
				fromShard := g.shardFor(e.From)
				if fromNode, ok := fromShard.nodes[e.From]; ok && fromNode.RepoPrefix != "" {
					repoEdgeCount[fromNode.RepoPrefix]++
				}
			}
		}
	}

	for prefix := range repoNodes {
		stats[prefix] = GraphStats{
			TotalNodes: repoNodeCount[prefix],
			TotalEdges: repoEdgeCount[prefix],
			ByKind:     repoByKind[prefix],
			ByLanguage: repoByLang[prefix],
		}
	}

	return stats
}

// RepoMemoryEstimate is an approximate breakdown of how many bytes a
// single repository's graph contribution occupies. It covers the
// sharded node/edge maps only — search and vector indexes are
// orthogonal and computed elsewhere.
type RepoMemoryEstimate struct {
	NodeBytes uint64 `json:"node_bytes"`
	EdgeBytes uint64 `json:"edge_bytes"`
	NodeCount int    `json:"node_count"`
	EdgeCount int    `json:"edge_count"`
}

// Total returns the sum of NodeBytes and EdgeBytes.
func (e RepoMemoryEstimate) Total() uint64 { return e.NodeBytes + e.EdgeBytes }

// per-node fixed overhead: the struct header plus the amortised cost
// of the pointers held by byRepo/byFile/byName/byQual secondary
// indexes inside each shard (4 maps × ~24 bytes for map bucket + slice
// element ≈ 100 bytes). Tuned against runtime.ReadMemStats deltas on a
// 50k-node repo; within ~10% of actual.
const nodeStructOverhead = 240

// per-edge fixed overhead: two string pointers, kind, filepath, line,
// plus slice-header and adjacency-map amortisation for outEdges AND
// inEdges (every edge is stored once as a struct but is referenced from
// both the source's out-adjacency list and the target's in-adjacency
// list, so the amortised overhead is ~2× slice-element + map-bucket).
const edgeStructOverhead = 144

// RepoMemoryEstimate sums the running per-shard counters maintained
// by AddNode / AddEdge / RemoveEdge / EvictFile / EvictRepo. O(shard
// count) instead of the O(repo nodes + total edges) walk this used to
// do — relevant because daemon-status queries call this once per
// tracked repo, and on a 488-repo / 1.9M-edge graph the old
// implementation was the single biggest source of writer contention
// during warmup.
func (g *Graph) RepoMemoryEstimate(repoPrefix string) RepoMemoryEstimate {
	g.lockAllRead()
	defer g.unlockAllRead()

	var est RepoMemoryEstimate
	for _, s := range g.shards {
		est.NodeBytes += s.repoNodeBytes[repoPrefix]
		est.NodeCount += s.repoNodeCount[repoPrefix]
		est.EdgeBytes += s.repoEdgeBytes[repoPrefix]
		est.EdgeCount += s.repoEdgeCount[repoPrefix]
	}
	return est
}

// AllRepoMemoryEstimates returns the per-repo estimate for every
// repo with a tracked counter — one pass across shards, one read lock
// acquisition. Callers driving a per-repo loop (daemon status) should
// prefer this over the single-repo variant.
func (g *Graph) AllRepoMemoryEstimates() map[string]RepoMemoryEstimate {
	g.lockAllRead()
	defer g.unlockAllRead()

	out := make(map[string]RepoMemoryEstimate)
	for _, s := range g.shards {
		for prefix, bytes := range s.repoNodeBytes {
			est := out[prefix]
			est.NodeBytes += bytes
			est.NodeCount += s.repoNodeCount[prefix]
			out[prefix] = est
		}
		for prefix, bytes := range s.repoEdgeBytes {
			est := out[prefix]
			est.EdgeBytes += bytes
			est.EdgeCount += s.repoEdgeCount[prefix]
			out[prefix] = est
		}
	}
	return out
}

// nodeBytes estimates the memory footprint of a single graph.Node.
func nodeBytes(n *Node) uint64 {
	if n == nil {
		return 0
	}
	b := uint64(nodeStructOverhead)
	b += uint64(len(n.ID) + len(n.Name) + len(n.QualName) + len(n.FilePath) + len(n.Language) + len(n.RepoPrefix))
	b += metaBytes(n.Meta)
	return b
}

// edgeBytes estimates the memory footprint of a single graph.Edge.
func edgeBytes(e *Edge) uint64 {
	if e == nil {
		return 0
	}
	b := uint64(edgeStructOverhead)
	b += uint64(len(e.From) + len(e.To) + len(e.Kind) + len(e.FilePath))
	return b
}

// metaBytes approximates the size of a Node.Meta map. Only handles the
// kinds of values we actually produce (string, bool, numeric, nested
// map, []string) — more exotic types fall back to a conservative
// constant rather than reflecting recursively.
func metaBytes(m map[string]any) uint64 {
	if m == nil {
		return 0
	}
	// map header + bucket amortisation for small maps.
	b := uint64(48 + 8*len(m))
	for k, v := range m {
		b += uint64(len(k)) + 16 // key entry overhead
		switch val := v.(type) {
		case string:
			b += uint64(len(val)) + 16
		case bool:
			b += 1 + 16
		case int, int32, int64, uint, uint32, uint64, float32, float64:
			b += 8 + 16
		case []string:
			b += 24 // slice header
			for _, s := range val {
				b += uint64(len(s)) + 16
			}
		case map[string]any:
			b += metaBytes(val)
		default:
			b += 32 // unknown — leave a sensible estimate
		}
	}
	return b
}

// RepoPrefixes returns a list of unique repository prefixes in the
// graph.
func (g *Graph) RepoPrefixes() []string {
	seen := make(map[string]struct{})
	for _, s := range g.shards {
		s.mu.RLock()
		for prefix := range s.byRepo {
			seen[prefix] = struct{}{}
		}
		s.mu.RUnlock()
	}
	prefixes := make([]string, 0, len(seen))
	for prefix := range seen {
		prefixes = append(prefixes, prefix)
	}
	return prefixes
}
