code_moniker_workspace/snapshot/

path.rs

use std::collections::BTreeMap;

use roaring::RoaringBitmap;
use rustc_hash::{FxHashMap, FxHashSet};

use super::{
	CodeIndex, LinkageSnapshot, ReferenceId, SourceId, SymbolId, UnresolvedReason,
	WorkspaceSnapshot,
};

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct BoundedPathEdge {
	pub source: SymbolId,
	pub target: SymbolId,
	pub reference: ReferenceId,
}

#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct BoundedPathCoverage {
	pub total: usize,
	pub decided: usize,
	pub resolved: usize,
	pub external: usize,
	pub candidate: usize,
	pub dynamic: usize,
	pub manifest_blocked: usize,
	pub unresolved: usize,
	pub gap_reasons: BTreeMap<String, usize>,
}

impl BoundedPathCoverage {
	pub fn percent(&self) -> usize {
		self.decided
			.saturating_mul(100)
			.checked_div(self.total)
			.unwrap_or(100)
	}
}

#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct BoundedPathSearch {
	pub path: Vec<BoundedPathEdge>,
	pub coverage: BoundedPathCoverage,
	pub depth_reached: usize,
	pub explored_symbols: usize,
	pub explored_edges: usize,
	pub depth_limit_reached: bool,
	pub symbol_limit_reached: bool,
	pub edge_limit_reached: bool,
}

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct BoundedPathLimits {
	pub max_depth: usize,
	pub max_symbols: usize,
	pub max_edges: usize,
}

#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct BoundedPathScope {
	sources: RoaringBitmap,
}

#[derive(Clone, Copy, Debug)]
pub struct BoundedPathRequest<'a> {
	pub from: SymbolId,
	pub to: SymbolId,
	pub relations: &'a [String],
	pub avoid: &'a [SymbolId],
	pub limits: BoundedPathLimits,
	pub scope: &'a BoundedPathScope,
}

impl BoundedPathScope {
	pub fn from_sources(sources: impl IntoIterator<Item = SourceId>) -> Self {
		Self {
			sources: sources
				.into_iter()
				.map(|source| source.file() as u32)
				.collect(),
		}
	}

	fn contains(&self, symbol: SymbolId) -> bool {
		self.sources.contains(symbol.file() as u32)
	}
}

#[derive(Default)]
struct ReferenceClassifications {
	external: FxHashSet<ReferenceId>,
	candidate: FxHashMap<ReferenceId, &'static str>,
	dynamic: FxHashMap<ReferenceId, &'static str>,
	manifest_blocked: FxHashSet<ReferenceId>,
	unresolved: FxHashMap<ReferenceId, UnresolvedReason>,
}

impl ReferenceClassifications {
	fn from_linkage(linkage: &LinkageSnapshot) -> Self {
		Self {
			external: Self::external(linkage),
			candidate: Self::candidate(linkage),
			dynamic: Self::dynamic(linkage),
			manifest_blocked: Self::manifest_blocked(linkage),
			unresolved: Self::unresolved(linkage),
		}
	}

	fn external(linkage: &LinkageSnapshot) -> FxHashSet<ReferenceId> {
		linkage
			.external
			.iter()
			.map(|reference| reference.reference)
			.collect()
	}

	fn candidate(linkage: &LinkageSnapshot) -> FxHashMap<ReferenceId, &'static str> {
		linkage
			.candidates
			.iter()
			.map(|reference| (reference.reference, reference.reason.as_str()))
			.collect()
	}

	fn dynamic(linkage: &LinkageSnapshot) -> FxHashMap<ReferenceId, &'static str> {
		linkage
			.dynamic
			.iter()
			.map(|reference| (reference.reference, reference.reason.as_str()))
			.collect()
	}

	fn manifest_blocked(linkage: &LinkageSnapshot) -> FxHashSet<ReferenceId> {
		linkage
			.blocked
			.iter()
			.chain(linkage.manifest_blocked.iter())
			.filter(|reference| reference.reason == UnresolvedReason::ManifestBlocked)
			.map(|reference| reference.reference)
			.collect()
	}

	fn unresolved(linkage: &LinkageSnapshot) -> FxHashMap<ReferenceId, UnresolvedReason> {
		linkage
			.unresolved
			.iter()
			.chain(
				linkage
					.blocked
					.iter()
					.filter(|reference| reference.reason != UnresolvedReason::ManifestBlocked),
			)
			.map(|reference| (reference.reference, reference.reason))
			.collect()
	}

	fn tally_gap(&self, reference: ReferenceId, coverage: &mut BoundedPathCoverage) {
		if self.external.contains(&reference) {
			coverage.external += 1;
			coverage.decided += 1;
		} else if let Some(reason) = self.candidate.get(&reference) {
			coverage.candidate += 1;
			tally_reason(&mut coverage.gap_reasons, "candidate", reason);
		} else if let Some(reason) = self.dynamic.get(&reference) {
			coverage.dynamic += 1;
			tally_reason(&mut coverage.gap_reasons, "dynamic", reason);
		} else if self.manifest_blocked.contains(&reference) {
			coverage.manifest_blocked += 1;
			*coverage
				.gap_reasons
				.entry("manifest_blocked".to_string())
				.or_default() += 1;
		} else {
			coverage.unresolved += 1;
			let reason = self
				.unresolved
				.get(&reference)
				.map_or("unclassified", UnresolvedReason::as_str);
			tally_reason(&mut coverage.gap_reasons, "unresolved", reason);
		}
	}
}

fn tally_reason(reasons: &mut BTreeMap<String, usize>, category: &str, reason: &str) {
	*reasons.entry(format!("{category}:{reason}")).or_default() += 1;
}

pub struct BoundedPathEngine<'a> {
	read_index: &'a super::LinkageReadIndex,
	classifications: ReferenceClassifications,
}

impl<'a> BoundedPathEngine<'a> {
	pub fn new(index: &CodeIndex, linkage: &'a LinkageSnapshot) -> Option<Self> {
		if linkage.index_generation != index.generation {
			return None;
		}
		Some(Self {
			read_index: linkage.read_index.get()?,
			classifications: ReferenceClassifications::from_linkage(linkage),
		})
	}

	pub fn search(&self, request: BoundedPathRequest<'_>) -> Option<BoundedPathSearch> {
		PathTraversal::new(
			self.read_index,
			&self.classifications,
			request.relations,
			request.avoid,
			request.limits,
			request.scope,
		)?
		.run(request.from, request.to)
	}
}

impl WorkspaceSnapshot {
	pub fn bounded_path(
		&self,
		from: SymbolId,
		to: SymbolId,
		relations: &[String],
		limits: BoundedPathLimits,
		scope: &BoundedPathScope,
	) -> Option<BoundedPathSearch> {
		bounded_path(
			&self.index,
			&self.linkage,
			BoundedPathRequest {
				from,
				to,
				relations,
				avoid: &[],
				limits,
				scope,
			},
		)
	}
}

pub fn bounded_path(
	index: &CodeIndex,
	linkage: &LinkageSnapshot,
	request: BoundedPathRequest<'_>,
) -> Option<BoundedPathSearch> {
	BoundedPathEngine::new(index, linkage)?.search(request)
}

struct PathTraversal<'a> {
	read_index: &'a super::LinkageReadIndex,
	relations: Vec<&'a str>,
	scope: &'a BoundedPathScope,
	max_depth: usize,
	max_symbols: usize,
	max_edges: usize,
	classifications: &'a ReferenceClassifications,
	avoided: RoaringBitmap,
	visited: RoaringBitmap,
	predecessors: FxHashMap<u32, (u32, ReferenceId)>,
	search: BoundedPathSearch,
}

impl<'a> PathTraversal<'a> {
	fn new(
		read_index: &'a super::LinkageReadIndex,
		classifications: &'a ReferenceClassifications,
		relations: &'a [String],
		avoid: &'a [SymbolId],
		limits: BoundedPathLimits,
		scope: &'a BoundedPathScope,
	) -> Option<Self> {
		let mut seen_relations = FxHashSet::default();
		let avoided = avoid
			.iter()
			.filter_map(|symbol| read_index.ordinal(symbol))
			.collect();
		Some(Self {
			read_index,
			relations: relations
				.iter()
				.map(String::as_str)
				.filter(|relation| seen_relations.insert(*relation))
				.collect(),
			scope,
			max_depth: limits.max_depth,
			max_symbols: limits.max_symbols,
			max_edges: limits.max_edges,
			classifications,
			avoided,
			visited: RoaringBitmap::new(),
			predecessors: FxHashMap::default(),
			search: BoundedPathSearch::default(),
		})
	}

	fn run(mut self, from: SymbolId, to: SymbolId) -> Option<BoundedPathSearch> {
		if !self.scope.contains(from) || !self.scope.contains(to) {
			return None;
		}
		let from_ordinal = self.read_index.ordinal(&from)?;
		let to_ordinal = self.read_index.ordinal(&to)?;
		if self.avoided.contains(from_ordinal) || self.avoided.contains(to_ordinal) {
			return None;
		}
		let mut frontier = RoaringBitmap::new();
		self.visited.insert(from_ordinal);
		frontier.insert(from_ordinal);
		if from_ordinal != to_ordinal {
			self.walk(&mut frontier, to_ordinal);
		}
		self.search.explored_symbols = self.visited.len() as usize;
		if self.visited.contains(to_ordinal) {
			self.search.path = reconstruct_path(
				self.read_index,
				&self.predecessors,
				from_ordinal,
				to_ordinal,
			)?;
		}
		Some(self.search)
	}

	fn walk(&mut self, frontier: &mut RoaringBitmap, to_ordinal: u32) {
		'search: for depth in 0..=self.max_depth {
			self.search.depth_reached = depth;
			let mut next = RoaringBitmap::new();
			for source_ordinal in frontier.iter() {
				let relations = self.relations_for(source_ordinal);
				for relation in relations {
					let outgoing_count = self.read_index.outgoing(source_ordinal, &relation).len();
					for reference_index in 0..outgoing_count {
						if self.search.coverage.total >= self.max_edges {
							self.search.edge_limit_reached = true;
							break 'search;
						}
						let reference =
							self.read_index.outgoing(source_ordinal, &relation)[reference_index];
						if self.visit_reference(source_ordinal, reference, depth, &mut next)
							== Some(to_ordinal)
						{
							self.search.depth_reached = depth + 1;
							break 'search;
						}
					}
				}
			}
			if next.is_empty() {
				break;
			}
			*frontier = next;
		}
	}

	fn relations_for(&self, source_ordinal: u32) -> Vec<String> {
		if self.relations.is_empty() {
			self.read_index
				.outgoing_relations(source_ordinal)
				.map(str::to_string)
				.collect()
		} else {
			self.relations
				.iter()
				.map(|relation| (*relation).to_string())
				.collect()
		}
	}

	fn visit_reference(
		&mut self,
		source_ordinal: u32,
		reference: ReferenceId,
		depth: usize,
		next: &mut RoaringBitmap,
	) -> Option<u32> {
		self.search.coverage.total += 1;
		let Some(target) = self.read_index.resolved_target(&reference).copied() else {
			self.classifications
				.tally_gap(reference, &mut self.search.coverage);
			return None;
		};
		let Some(target_ordinal) = self.read_index.ordinal(&target) else {
			self.tally_missing_ordinal();
			return None;
		};
		self.search.coverage.resolved += 1;
		self.search.coverage.decided += 1;
		self.search.explored_edges += 1;
		if !self.scope.contains(target) {
			return None;
		}
		if self.avoided.contains(target_ordinal) {
			return None;
		}
		if depth >= self.max_depth {
			if !self.visited.contains(target_ordinal) {
				self.search.depth_limit_reached = true;
			}
			return None;
		}
		if self.visited.contains(target_ordinal) {
			return None;
		}
		if self.visited.len() as usize >= self.max_symbols {
			self.search.symbol_limit_reached = true;
			return None;
		}
		self.visited.insert(target_ordinal);
		self.predecessors
			.insert(target_ordinal, (source_ordinal, reference));
		next.insert(target_ordinal);
		Some(target_ordinal)
	}

	fn tally_missing_ordinal(&mut self) {
		self.search.coverage.unresolved += 1;
		*self
			.search
			.coverage
			.gap_reasons
			.entry("missing_symbol_ordinal".to_string())
			.or_default() += 1;
	}
}

fn reconstruct_path(
	read_index: &super::LinkageReadIndex,
	predecessors: &FxHashMap<u32, (u32, ReferenceId)>,
	from: u32,
	to: u32,
) -> Option<Vec<BoundedPathEdge>> {
	let mut path = Vec::new();
	let mut current = to;
	while current != from {
		let (previous, reference) = predecessors.get(&current).copied()?;
		path.push(BoundedPathEdge {
			source: read_index.symbol(previous)?,
			target: read_index.symbol(current)?,
			reference,
		});
		current = previous;
	}
	path.reverse();
	Some(path)
}

#[cfg(test)]
mod tests {
	use super::*;
	use crate::snapshot::{
		CandidateReason, CandidateReference, CandidateScope, ChangeOverlay, CodeIndex,
		DynamicReason, DynamicReference, ExternalReference, ExternalReferenceOrigin, LinkageEdge,
		LinkageReadIndexHandle, LinkageSnapshot, ReferenceRecord, ResolutionEvidence,
		ResourceGeneration, SourceCatalog, SymbolRecord, UnresolvedReference, WorkspaceTimings,
	};

	fn path_snapshot(
		symbols: Vec<SymbolRecord>,
		references: Vec<ReferenceRecord>,
		edges: Vec<LinkageEdge>,
		ordinals: Vec<(u32, SymbolId)>,
	) -> WorkspaceSnapshot {
		let generation = ResourceGeneration::new(1);
		let index = CodeIndex::with_references(generation, generation, symbols, references);
		let read_index =
			LinkageReadIndexHandle::from_edges_with_ordinals(&edges, &index.references, ordinals);
		let mut linkage = LinkageSnapshot::new(generation, generation, edges.len(), 0);
		linkage.resolved = edges;
		linkage.read_index = read_index;
		WorkspaceSnapshot {
			generation,
			catalog: SourceCatalog::new(generation, Vec::new()),
			index,
			linkage,
			changes: ChangeOverlay::new(generation, generation, generation, Vec::new()),
			timings: WorkspaceTimings::default(),
		}
	}

	#[test]
	fn selected_source_scope_blocks_cross_root_detours_with_sparse_ordinals() {
		let first_source = SourceId::at(0);
		let other_source = SourceId::at(1);
		let from = SymbolId::at(0, 0);
		let to = SymbolId::at(0, 1);
		let bridge = SymbolId::at(1, 0);
		let first = ReferenceId::at(0, 0);
		let second = ReferenceId::at(1, 0);
		let snapshot = path_snapshot(
			vec![
				SymbolRecord::new(from, first_source, "from", "fn"),
				SymbolRecord::new(to, first_source, "to", "fn"),
				SymbolRecord::new(bridge, other_source, "bridge", "fn"),
			],
			vec![
				ReferenceRecord::new(first, first_source, from, bridge.to_string(), "calls", None),
				ReferenceRecord::new(second, other_source, bridge, to.to_string(), "calls", None),
			],
			vec![
				LinkageEdge::new(first, bridge),
				LinkageEdge::new(second, to),
			],
			vec![(7, from), (2_000_000, bridge), (u32::MAX - 1, to)],
		);
		let limits = BoundedPathLimits {
			max_depth: 4,
			max_symbols: 10,
			max_edges: 10,
		};
		let selected = BoundedPathScope::from_sources([first_source]);
		let scoped = snapshot
			.bounded_path(from, to, &["calls".to_string()], limits, &selected)
			.expect("scoped path search");
		assert!(scoped.path.is_empty(), "{scoped:?}");
		assert_eq!(scoped.coverage.resolved, 1, "{scoped:?}");
		assert_eq!(scoped.coverage.decided, 1, "{scoped:?}");

		let all_sources = BoundedPathScope::from_sources([first_source, other_source]);
		let unscoped = snapshot
			.bounded_path(from, to, &["calls".to_string()], limits, &all_sources)
			.expect("all-roots path search");
		assert_eq!(unscoped.path.len(), 2, "{unscoped:?}");
		assert_eq!(
			snapshot
				.linkage
				.read_index
				.get()
				.expect("path read index")
				.active_symbol_slots(),
			3,
			"sparse stable ordinals must not allocate historical holes"
		);
	}

	#[test]
	fn coverage_counts_every_unlinked_reference_category() {
		let source = SourceId::at(0);
		let from = SymbolId::at(0, 0);
		let to = SymbolId::at(0, 1);
		let ids = (0..5)
			.map(|index| ReferenceId::at(0, index))
			.collect::<Vec<_>>();
		let references = ids
			.iter()
			.enumerate()
			.map(|(index, id)| {
				ReferenceRecord::new(*id, source, from, format!("missing:{index}"), "calls", None)
			})
			.collect();
		let mut snapshot = path_snapshot(
			vec![
				SymbolRecord::new(from, source, "from", "fn"),
				SymbolRecord::new(to, source, "to", "fn"),
			],
			references,
			Vec::new(),
			vec![(11, from), (97, to)],
		);
		snapshot.linkage.external.push(ExternalReference::new(
			ids[0],
			"external",
			ExternalReferenceOrigin::Dependency,
		));
		snapshot.linkage.candidates.push(CandidateReference::new(
			ids[1],
			vec![to],
			CandidateReason::MultipleTargets,
			CandidateScope::Local,
			ResolutionEvidence::NameMatch,
		));
		snapshot.linkage.dynamic.push(DynamicReference::new(
			ids[2],
			"dynamic",
			DynamicReason::RuntimeMutation,
			Vec::new(),
		));
		snapshot.linkage.blocked.push(UnresolvedReference::new(
			ids[3],
			"blocked",
			UnresolvedReason::ManifestBlocked,
		));
		snapshot.linkage.unresolved.push(UnresolvedReference::new(
			ids[4],
			"missing",
			UnresolvedReason::NoCandidate,
		));

		let search = snapshot
			.bounded_path(
				from,
				to,
				&["calls".to_string()],
				BoundedPathLimits {
					max_depth: 4,
					max_symbols: 10,
					max_edges: 10,
				},
				&BoundedPathScope::from_sources([source]),
			)
			.expect("coverage path search");
		assert_eq!(search.coverage.total, 5, "{search:?}");
		assert_eq!(search.coverage.decided, 1, "{search:?}");
		assert_eq!(search.coverage.external, 1, "{search:?}");
		assert_eq!(search.coverage.candidate, 1, "{search:?}");
		assert_eq!(search.coverage.dynamic, 1, "{search:?}");
		assert_eq!(search.coverage.manifest_blocked, 1, "{search:?}");
		assert_eq!(search.coverage.unresolved, 1, "{search:?}");
	}

	#[test]
	fn edge_budget_stops_inside_a_large_indexed_adjacency() {
		let source = SourceId::at(0);
		let from = SymbolId::at(0, 0);
		let sink = SymbolId::at(0, 1);
		let to = SymbolId::at(0, 2);
		let references = (0..2_048)
			.map(|index| {
				let id = ReferenceId::at(0, index);
				ReferenceRecord::new(id, source, from, sink.to_string(), "calls", None)
			})
			.collect::<Vec<_>>();
		let edges = references
			.iter()
			.map(|reference| LinkageEdge::new(reference.id, sink))
			.collect();
		let snapshot = path_snapshot(
			vec![
				SymbolRecord::new(from, source, "from", "fn"),
				SymbolRecord::new(sink, source, "sink", "fn"),
				SymbolRecord::new(to, source, "to", "fn"),
			],
			references,
			edges,
			vec![(1, from), (2, sink), (3, to)],
		);

		let search = snapshot
			.bounded_path(
				from,
				to,
				&["calls".to_string()],
				BoundedPathLimits {
					max_depth: 4,
					max_symbols: 10,
					max_edges: 3,
				},
				&BoundedPathScope::from_sources([source]),
			)
			.expect("budgeted path search");
		assert_eq!(search.coverage.total, 3, "{search:?}");
		assert_eq!(search.explored_edges, 3, "{search:?}");
		assert!(search.edge_limit_reached, "{search:?}");
	}

	#[test]
	fn prepared_engine_reuses_linkage_classifications_across_searches() {
		let source = SourceId::at(0);
		let from = SymbolId::at(0, 0);
		let middle = SymbolId::at(0, 1);
		let to = SymbolId::at(0, 2);
		let first = ReferenceId::at(0, 0);
		let second = ReferenceId::at(0, 1);
		let snapshot = path_snapshot(
			vec![
				SymbolRecord::new(from, source, "from", "fn"),
				SymbolRecord::new(middle, source, "middle", "fn"),
				SymbolRecord::new(to, source, "to", "fn"),
			],
			vec![
				ReferenceRecord::new(first, source, from, middle.to_string(), "calls", None),
				ReferenceRecord::new(second, source, middle, to.to_string(), "calls", None),
			],
			vec![
				LinkageEdge::new(first, middle),
				LinkageEdge::new(second, to),
			],
			vec![(1, from), (2, middle), (3, to)],
		);
		let scope = BoundedPathScope::from_sources([source]);
		let relations = vec!["calls".to_string()];
		let limits = BoundedPathLimits {
			max_depth: 4,
			max_symbols: 10,
			max_edges: 10,
		};
		let engine =
			BoundedPathEngine::new(&snapshot.index, &snapshot.linkage).expect("path engine");

		let first_search = engine
			.search(BoundedPathRequest {
				from,
				to: middle,
				relations: &relations,
				avoid: &[],
				limits,
				scope: &scope,
			})
			.expect("first search");
		let second_search = engine
			.search(BoundedPathRequest {
				from,
				to,
				relations: &relations,
				avoid: &[],
				limits,
				scope: &scope,
			})
			.expect("second search");
		let avoided_search = engine
			.search(BoundedPathRequest {
				from,
				to,
				relations: &relations,
				avoid: &[middle],
				limits,
				scope: &scope,
			})
			.expect("search avoiding the mandatory boundary");

		assert_eq!(first_search.path.len(), 1);
		assert_eq!(second_search.path.len(), 2);
		assert!(avoided_search.path.is_empty(), "{avoided_search:?}");
	}
}