code-moniker-workspace 0.4.0

use std::collections::BTreeMap;
use std::hash::Hash;

use crate::linkage::binding::LinkageMemoryMetrics;
use crate::linkage::binding::{ReferenceLinkageDecision, UnknownReason};
use crate::linkage::catalog::LinkageQuery;
use crate::linkage::catalog::{CandidateCatalog, query_keys};
use crate::linkage::catalog::{
	ReferenceOrdinal, ReferenceSet, SymbolOrdinal, SymbolOrdinalCatalog, SymbolSet,
};
use crate::snapshot::{
	LinkageSnapshot, RecordTable, ReferenceId, ReferenceRecord, ResourceGeneration, SourceId,
};
use crate::source::{CodeIndexMaterial, LocalIdentityResolver};
use code_moniker_core::core::uri::{UriConfig, from_uri};
use rayon::prelude::*;
use rustc_hash::FxHashMap;

#[derive(Clone)]
pub(in crate::linkage) struct LinkageStore {
	generation: ResourceGeneration,
	index_generation: ResourceGeneration,
	decisions: Vec<ReferenceLinkageDecision>,
	pub(in crate::linkage) indexes: LinkageStoreIndexes,
}

pub(in crate::linkage) struct LinkageStoreRefresh<'a> {
	pub(in crate::linkage) generation: ResourceGeneration,
	pub(in crate::linkage) index_generation: ResourceGeneration,
	pub(in crate::linkage) stale_references: &'a ReferenceSet,
	pub(in crate::linkage) changed_decisions: Vec<ReferenceLinkageDecision>,
	pub(in crate::linkage) references: &'a RecordTable<ReferenceRecord>,
	pub(in crate::linkage) material: &'a CodeIndexMaterial,
	pub(in crate::linkage) candidates: &'a CandidateCatalog,
}

impl LinkageStore {
	pub(in crate::linkage) fn new(
		generation: ResourceGeneration,
		index_generation: ResourceGeneration,
		decisions: Vec<ReferenceLinkageDecision>,
		references: &RecordTable<ReferenceRecord>,
		material: &CodeIndexMaterial,
		candidates: &CandidateCatalog,
	) -> Self {
		let mut indexes = LinkageStoreIndexes::new(references, material);
		indexes.rebuild_resolved_target_indexes(ResolvedTargetSourceBuild {
			decisions: &decisions,
			material,
			symbols: candidates.symbols(),
		});
		Self {
			generation,
			index_generation,
			decisions,
			indexes,
		}
	}

	pub(in crate::linkage) fn from_snapshot(
		snapshot: &LinkageSnapshot,
		references: &RecordTable<ReferenceRecord>,
		material: &CodeIndexMaterial,
		candidates: &CandidateCatalog,
	) -> Self {
		Self::new(
			snapshot.generation,
			snapshot.index_generation,
			decisions_from_snapshot(snapshot, references, material, candidates),
			references,
			material,
			candidates,
		)
	}

	pub(in crate::linkage) fn project_snapshot(
		&self,
		references: &RecordTable<ReferenceRecord>,
		identity: &LocalIdentityResolver,
		symbols: &SymbolOrdinalCatalog,
	) -> LinkageSnapshot {
		crate::linkage::binding::project_decisions(&self.decisions, references, identity, symbols)
			.into_snapshot(self.generation, self.index_generation)
	}

	pub(in crate::linkage) fn advance_index_generation(
		&mut self,
		index_generation: ResourceGeneration,
	) {
		self.index_generation = index_generation;
	}

	pub(in crate::linkage) fn apply_refresh(&mut self, refresh: LinkageStoreRefresh<'_>) {
		apply_store_refresh(self, refresh);
	}

	pub(in crate::linkage) fn rebase_reference_ordinals(
		&mut self,
		next_reference_indexes: FxHashMap<ReferenceId, ReferenceOrdinal>,
		reference_id_remaps: &[(ReferenceId, ReferenceId)],
		removed_references: &[ReferenceId],
	) {
		rebase_store_reference_ordinals(
			self,
			next_reference_indexes,
			reference_id_remaps,
			removed_references,
		);
	}

	pub(in crate::linkage) fn missing_resolved_references(
		&self,
		material: &CodeIndexMaterial,
		candidates: &CandidateCatalog,
	) -> Vec<ReferenceId> {
		missing_resolved_references(self, material, candidates)
	}

	pub(in crate::linkage) fn decisions_mut(&mut self) -> &mut [ReferenceLinkageDecision] {
		&mut self.decisions
	}

	pub(in crate::linkage) fn memory_metrics(
		&self,
		symbols: &SymbolOrdinalCatalog,
	) -> LinkageMemoryMetrics {
		store_memory_metrics(self, symbols)
	}

	pub(in crate::linkage) fn refresh_resolved_target_index(
		&mut self,
		references: &ReferenceSet,
		material: &CodeIndexMaterial,
		symbols: &SymbolOrdinalCatalog,
	) {
		refresh_resolved_target_index(self, references, material, symbols);
	}

	pub(in crate::linkage) fn ensure_resolved_target_index(
		&mut self,
		material: &CodeIndexMaterial,
		symbols: &SymbolOrdinalCatalog,
	) {
		if self.indexes.resolved_by_target_source.is_some() {
			return;
		}
		self.indexes
			.rebuild_resolved_target_indexes(ResolvedTargetSourceBuild {
				decisions: &self.decisions,
				material,
				symbols,
			});
	}
}

fn apply_store_refresh(store: &mut LinkageStore, refresh: LinkageStoreRefresh<'_>) {
	let LinkageStoreRefresh {
		generation,
		index_generation,
		stale_references,
		changed_decisions,
		references,
		material,
		candidates,
	} = refresh;
	store.generation = generation;
	store.index_generation = index_generation;
	store.indexes.remove_stale_references(stale_references);
	remove_stale_decisions(store, stale_references);
	let _ = candidates;
	add_changed_decisions(
		store,
		ChangedDecisionBatch {
			decisions: changed_decisions,
			references,
			material,
		},
	);
}

struct ChangedDecisionBatch<'a> {
	decisions: Vec<ReferenceLinkageDecision>,
	references: &'a RecordTable<ReferenceRecord>,
	material: &'a CodeIndexMaterial,
}

fn missing_resolved_references(
	store: &LinkageStore,
	material: &CodeIndexMaterial,
	candidates: &CandidateCatalog,
) -> Vec<ReferenceId> {
	store
		.decisions
		.iter()
		.filter(|decision| {
			!store
				.indexes
				.reference_indexes
				.contains_key(decision.reference())
				|| decision.resolved_targets().is_some_and(|targets| {
					targets.iter().any(|target| {
						resolved_target_missing_or_retargeted(material, candidates, target)
					})
				})
		})
		.map(|decision| *decision.reference())
		.collect()
}

fn resolved_target_missing_or_retargeted(
	material: &CodeIndexMaterial,
	candidates: &CandidateCatalog,
	target: SymbolOrdinal,
) -> bool {
	let Some(expected_identity) = candidates.symbols().identity(target) else {
		return true;
	};
	if candidates
		.symbols()
		.ordinal_by_identity(expected_identity)
		.is_some()
	{
		return false;
	}
	let Some(id) = candidates.symbols().id(target) else {
		return true;
	};
	let Some(current_moniker) = material.symbol_moniker(id) else {
		return true;
	};
	material.identity.moniker_uri(current_moniker) != expected_identity
}

pub(in crate::linkage) fn insert_reference_ordinals(
	store: &mut LinkageStore,
	changed_references: &[ReferenceId],
	references: &RecordTable<ReferenceRecord>,
	material: &CodeIndexMaterial,
) {
	if changed_references.is_empty() {
		return;
	}
	let mut prefix = Vec::with_capacity(material.files.len() + 1);
	let mut total = 0usize;
	prefix.push(0usize);
	for slot in 0..material.files.len() {
		total += references.file_records(slot).len();
		prefix.push(total);
	}
	for reference in changed_references {
		let Some((slot, ref_idx)) = material.identity.reference_location(reference) else {
			continue;
		};
		let Some(base) = prefix.get(slot) else {
			continue;
		};
		store
			.indexes
			.reference_indexes
			.insert(*reference, ReferenceOrdinal::from_index(base + ref_idx));
	}
}

fn rebase_store_reference_ordinals(
	store: &mut LinkageStore,
	next_reference_indexes: FxHashMap<ReferenceId, ReferenceOrdinal>,
	reference_id_remaps: &[(ReferenceId, ReferenceId)],
	removed_references: &[ReferenceId],
) {
	let removed_references = removed_references
		.iter()
		.collect::<std::collections::HashSet<_>>();
	let rebase = ReferenceOrdinalRebase::new(
		&store.indexes.reference_indexes,
		&next_reference_indexes,
		reference_id_remaps,
		&removed_references,
	);
	store.indexes.rebase_reference_ordinals(&rebase);
	rebase_decision_references(
		store,
		&next_reference_indexes,
		reference_id_remaps,
		&removed_references,
	);
	store.indexes.reference_indexes = next_reference_indexes;
}

struct ReferenceOrdinalRebase {
	next_by_old: Vec<Option<ReferenceOrdinal>>,
}

impl ReferenceOrdinalRebase {
	fn new(
		previous: &FxHashMap<ReferenceId, ReferenceOrdinal>,
		next: &FxHashMap<ReferenceId, ReferenceOrdinal>,
		reference_id_remaps: &[(ReferenceId, ReferenceId)],
		removed_references: &std::collections::HashSet<&ReferenceId>,
	) -> Self {
		let max_old = previous
			.values()
			.map(|reference| reference.index())
			.max()
			.unwrap_or(0);
		let mut next_by_old = vec![None; max_old + 1];
		let reference_id_remaps = reference_id_remaps
			.iter()
			.cloned()
			.collect::<FxHashMap<ReferenceId, ReferenceId>>();
		for (reference, previous_ordinal) in previous {
			if removed_references.contains(reference) {
				continue;
			}
			let next_reference = reference_id_remaps.get(reference).unwrap_or(reference);
			if let Some(next_ordinal) = next.get(next_reference) {
				next_by_old[previous_ordinal.index()] = Some(*next_ordinal);
			}
		}
		Self { next_by_old }
	}

	fn map(&self, previous: ReferenceOrdinal) -> Option<ReferenceOrdinal> {
		self.next_by_old.get(previous.index()).copied().flatten()
	}
}

fn rebase_decision_references(
	store: &mut LinkageStore,
	next_reference_indexes: &FxHashMap<ReferenceId, ReferenceOrdinal>,
	reference_id_remaps: &[(ReferenceId, ReferenceId)],
	removed_references: &std::collections::HashSet<&ReferenceId>,
) {
	let reference_id_remaps = reference_id_remaps
		.iter()
		.cloned()
		.collect::<FxHashMap<ReferenceId, ReferenceId>>();
	store.decisions.retain_mut(|decision| {
		let current_reference = *decision.reference();
		if removed_references.contains(&current_reference) {
			return false;
		}
		let next_reference = reference_id_remaps
			.get(&current_reference)
			.unwrap_or(&current_reference);
		let Some(next_reference_idx) = next_reference_indexes.get(next_reference) else {
			return false;
		};
		if next_reference == &current_reference {
			decision.set_reference_idx(next_reference_idx.index());
		} else {
			decision.set_reference(*next_reference, next_reference_idx.index());
		}
		true
	});
}

fn remove_stale_decisions(store: &mut LinkageStore, stale_references: &ReferenceSet) {
	let reference_indexes = &store.indexes.reference_indexes;
	store.decisions.retain_mut(|decision| {
		if let Some(reference_idx) = reference_indexes.get(decision.reference()) {
			if stale_references.contains(*reference_idx) {
				return false;
			}
			decision.set_reference_idx(reference_idx.index());
			return true;
		}
		false
	});
}

fn add_changed_decisions(store: &mut LinkageStore, batch: ChangedDecisionBatch<'_>) {
	for decision in batch.decisions {
		let Some(reference) = batch.references.get(decision.reference_idx()) else {
			continue;
		};
		add_reference_indexes(&mut store.indexes, reference, batch.material);
		store.decisions.push(decision);
	}
}

fn add_reference_indexes(
	indexes: &mut LinkageStoreIndexes,
	reference: &ReferenceRecord,
	material: &CodeIndexMaterial,
) {
	let Some(reference_ordinal) = indexes.reference_indexes.get(&reference.id).copied() else {
		return;
	};
	if let Some(source_root) = reference_source_root(reference, material) {
		indexes
			.references_by_source_root
			.entry(source_root)
			.or_default()
			.insert(reference_ordinal);
	}
	let Some(query) = LinkageQuery::new(reference, material) else {
		return;
	};
	for key in query_keys(&query) {
		indexes
			.references_by_name
			.entry(key)
			.or_default()
			.insert(reference_ordinal);
	}
}

fn refresh_resolved_target_index(
	store: &mut LinkageStore,
	references: &ReferenceSet,
	material: &CodeIndexMaterial,
	symbols: &SymbolOrdinalCatalog,
) {
	store.ensure_resolved_target_index(material, symbols);
	store.indexes.remove_resolved_references(references);
	for decision in &store.decisions {
		if store
			.indexes
			.reference_indexes
			.get(decision.reference())
			.is_some_and(|reference| references.contains(*reference))
		{
			store
				.indexes
				.add_resolved_target_indexes(decision, material, symbols);
		}
	}
}

fn store_memory_metrics(
	store: &LinkageStore,
	symbols: &SymbolOrdinalCatalog,
) -> LinkageMemoryMetrics {
	let mut metrics = LinkageMemoryMetrics {
		symbol_catalog_entries: symbols.len(),
		decisions: store.decisions.len(),
		..LinkageMemoryMetrics::default()
	};
	record_reference_sets(
		store.indexes.references_by_source_root.values(),
		&mut metrics,
	);
	record_reference_sets(store.indexes.references_by_name.values(), &mut metrics);
	if let Some(index) = &store.indexes.resolved_by_target_source {
		index.record_memory(&mut metrics);
	}
	for decision in &store.decisions {
		if let Some(targets) = decision.resolved_targets() {
			metrics.add_symbol_set(targets.len(), targets.serialized_size());
		}
	}
	metrics
}

fn record_reference_sets<'a>(
	sets: impl IntoIterator<Item = &'a ReferenceSet>,
	metrics: &mut LinkageMemoryMetrics,
) {
	for set in sets {
		metrics.add_reference_set(set.len(), set.serialized_size());
	}
}

fn decisions_from_snapshot(
	snapshot: &LinkageSnapshot,
	references: &RecordTable<ReferenceRecord>,
	material: &CodeIndexMaterial,
	candidates: &CandidateCatalog,
) -> Vec<ReferenceLinkageDecision> {
	let reference_indexes = reference_indexes(references);
	let mut decisions = Vec::new();
	decisions.extend(resolved_decisions_from_snapshot(
		snapshot,
		&reference_indexes,
		candidates.symbols(),
	));
	decisions.extend(external_decisions_from_snapshot(
		snapshot,
		&reference_indexes,
		material,
	));
	decisions.extend(
		snapshot
			.manifest_blocked
			.iter()
			.filter_map(|blocked| reference_indexes.get(&blocked.reference).copied())
			.map(|reference_idx| {
				ReferenceLinkageDecision::manifest_blocked(
					reference_idx.index(),
					references[reference_idx.index()].id,
				)
			}),
	);
	decisions.extend(
		snapshot
			.unresolved
			.iter()
			.filter_map(|unresolved| reference_indexes.get(&unresolved.reference).copied())
			.map(|reference_idx| {
				ReferenceLinkageDecision::unknown(
					UnknownReason::NoCandidate,
					reference_idx.index(),
					references[reference_idx.index()].id,
				)
			}),
	);
	decisions
}

fn resolved_decisions_from_snapshot(
	snapshot: &LinkageSnapshot,
	reference_indexes: &FxHashMap<ReferenceId, ReferenceOrdinal>,
	symbols: &SymbolOrdinalCatalog,
) -> Vec<ReferenceLinkageDecision> {
	let mut targets_by_reference = BTreeMap::<ReferenceId, SymbolSet>::new();
	for edge in &snapshot.resolved {
		let Some(target) = symbols.ordinal(&edge.target) else {
			continue;
		};
		targets_by_reference
			.entry(edge.reference)
			.or_default()
			.insert(target);
	}
	targets_by_reference
		.into_iter()
		.filter_map(|(reference, targets)| {
			reference_indexes.get(&reference).map(|reference_idx| {
				ReferenceLinkageDecision::resolved(
					crate::linkage::binding::ResolutionScope::Global,
					reference_idx.index(),
					reference,
					targets,
				)
			})
		})
		.collect()
}

fn external_decisions_from_snapshot(
	snapshot: &LinkageSnapshot,
	reference_indexes: &FxHashMap<ReferenceId, ReferenceOrdinal>,
	material: &CodeIndexMaterial,
) -> Vec<ReferenceLinkageDecision> {
	snapshot
		.external
		.iter()
		.filter_map(|external| {
			let reference_idx = reference_indexes.get(&external.reference)?.index();
			let target = from_uri(
				external.target_identity.as_ref(),
				&UriConfig {
					scheme: material.identity.scheme(),
				},
			)
			.ok();
			Some(match target {
				Some(target) => ReferenceLinkageDecision::external_target(
					external.origin,
					reference_idx,
					external.reference,
					target,
				),
				None => ReferenceLinkageDecision::external(
					external.origin,
					reference_idx,
					external.reference,
				),
			})
		})
		.collect()
}

#[derive(Clone)]
pub(in crate::linkage) struct LinkageStoreIndexes {
	pub(in crate::linkage) reference_indexes: FxHashMap<ReferenceId, ReferenceOrdinal>,
	pub(in crate::linkage) references_by_source_root: FxHashMap<usize, ReferenceSet>,
	pub(in crate::linkage) references_by_name: FxHashMap<Vec<u8>, ReferenceSet>,
	pub(in crate::linkage) resolved_by_target_source: Option<ResolvedTargetSourceIndex>,
}

impl LinkageStoreIndexes {
	fn new(references: &RecordTable<ReferenceRecord>, material: &CodeIndexMaterial) -> Self {
		Self::from_references(references, material)
	}

	fn from_references(
		references: &RecordTable<ReferenceRecord>,
		material: &CodeIndexMaterial,
	) -> Self {
		Self {
			reference_indexes: reference_indexes(references),
			references_by_source_root: references_by_source_root(references, material),
			references_by_name: references_by_name(references, material),
			resolved_by_target_source: None,
		}
	}

	fn add_resolved_target_indexes(
		&mut self,
		decision: &ReferenceLinkageDecision,
		material: &CodeIndexMaterial,
		symbols: &SymbolOrdinalCatalog,
	) {
		let Some(index) = &mut self.resolved_by_target_source else {
			return;
		};
		add_resolved_target_decision(
			index,
			decision,
			ResolvedTargetSourceContext { material, symbols },
		);
	}

	fn rebase_reference_ordinals(&mut self, rebase: &ReferenceOrdinalRebase) {
		rebase_reference_maps(&mut self.references_by_source_root, rebase);
		rebase_reference_maps(&mut self.references_by_name, rebase);
		if let Some(index) = &mut self.resolved_by_target_source {
			index.rebase_reference_ordinals(rebase);
		}
	}

	fn remove_stale_references(&mut self, stale_references: &ReferenceSet) {
		remove_references(&mut self.references_by_source_root, stale_references);
		remove_references(&mut self.references_by_name, stale_references);
		self.remove_resolved_references(stale_references);
	}

	fn remove_resolved_references(&mut self, stale_references: &ReferenceSet) {
		if let Some(index) = &mut self.resolved_by_target_source {
			index.remove_references(stale_references);
		}
	}

	fn rebuild_resolved_target_indexes(&mut self, input: ResolvedTargetSourceBuild<'_>) {
		let mut index = ResolvedTargetSourceIndex::default();
		index.collect_decisions(input);
		self.resolved_by_target_source = Some(index);
	}
}

#[derive(Clone, Copy)]
struct ResolvedTargetSourceBuild<'a> {
	decisions: &'a [ReferenceLinkageDecision],
	material: &'a CodeIndexMaterial,
	symbols: &'a SymbolOrdinalCatalog,
}

impl<'a> ResolvedTargetSourceBuild<'a> {
	fn context(self) -> ResolvedTargetSourceContext<'a> {
		ResolvedTargetSourceContext {
			material: self.material,
			symbols: self.symbols,
		}
	}
}

#[derive(Clone, Copy)]
struct ResolvedTargetSourceContext<'a> {
	material: &'a CodeIndexMaterial,
	symbols: &'a SymbolOrdinalCatalog,
}

#[derive(Clone, Default)]
pub(in crate::linkage) struct ResolvedTargetSourceIndex {
	references_by_source: FxHashMap<SourceId, ReferenceSet>,
	references_by_symbol: FxHashMap<SymbolOrdinal, ReferenceSet>,
}

impl ResolvedTargetSourceIndex {
	pub(in crate::linkage) fn get(&self, source: &SourceId) -> Option<&ReferenceSet> {
		self.references_by_source.get(source)
	}

	pub(in crate::linkage) fn get_symbol(&self, symbol: SymbolOrdinal) -> Option<&ReferenceSet> {
		self.references_by_symbol.get(&symbol)
	}

	fn record_memory(&self, metrics: &mut LinkageMemoryMetrics) {
		record_reference_sets(self.references_by_source.values(), metrics);
		record_reference_sets(self.references_by_symbol.values(), metrics);
	}

	fn collect_decisions(&mut self, input: ResolvedTargetSourceBuild<'_>) {
		let context = input.context();
		for decision in input.decisions {
			add_resolved_target_decision(self, decision, context);
		}
	}

	fn remove_references(&mut self, stale_references: &ReferenceSet) {
		remove_references(&mut self.references_by_source, stale_references);
		remove_references(&mut self.references_by_symbol, stale_references);
	}

	fn rebase_reference_ordinals(&mut self, rebase: &ReferenceOrdinalRebase) {
		rebase_reference_maps(&mut self.references_by_source, rebase);
		rebase_reference_maps(&mut self.references_by_symbol, rebase);
	}
}

fn add_resolved_target_decision(
	index: &mut ResolvedTargetSourceIndex,
	decision: &ReferenceLinkageDecision,
	context: ResolvedTargetSourceContext<'_>,
) {
	let Some(targets) = decision.resolved_targets() else {
		return;
	};
	for target in targets.iter() {
		index
			.references_by_symbol
			.entry(target)
			.or_default()
			.insert(ReferenceOrdinal::from_index(decision.reference_idx()));
		let Some(symbol_id) = context.symbols.id(target) else {
			continue;
		};
		let Some(source) = context.material.symbol_source(symbol_id) else {
			continue;
		};
		index
			.references_by_source
			.entry(source)
			.or_default()
			.insert(ReferenceOrdinal::from_index(decision.reference_idx()));
	}
}

pub(in crate::linkage) fn reference_indexes(
	references: &RecordTable<ReferenceRecord>,
) -> FxHashMap<ReferenceId, ReferenceOrdinal> {
	references
		.iter()
		.enumerate()
		.map(|(idx, reference)| (reference.id, ReferenceOrdinal::from_index(idx)))
		.collect()
}

fn remove_references<K: Eq + Hash>(
	index: &mut FxHashMap<K, ReferenceSet>,
	references: &ReferenceSet,
) {
	index.retain(|_, indexed_references| {
		indexed_references.remove_all(references);
		!indexed_references.is_empty()
	});
}

fn rebase_reference_maps<K: Eq + Hash>(
	index: &mut FxHashMap<K, ReferenceSet>,
	rebase: &ReferenceOrdinalRebase,
) {
	index.retain(|_, references| {
		*references = references
			.iter()
			.filter_map(|reference| rebase.map(reference))
			.collect();
		!references.is_empty()
	});
}

fn references_by_source_root(
	references: &RecordTable<ReferenceRecord>,
	material: &CodeIndexMaterial,
) -> FxHashMap<usize, ReferenceSet> {
	(0..references.len())
		.into_par_iter()
		.map(|reference_idx| (reference_idx, &references[reference_idx]))
		.fold(
			FxHashMap::<usize, ReferenceSet>::default,
			|mut index, item| {
				let (reference_idx, reference) = item;
				if let Some(source_root) = reference_source_root(reference, material) {
					index
						.entry(source_root)
						.or_default()
						.insert(ReferenceOrdinal::from_index(reference_idx));
				}
				index
			},
		)
		.reduce(
			FxHashMap::<usize, ReferenceSet>::default,
			merge_reference_set_maps,
		)
}

fn references_by_name(
	references: &RecordTable<ReferenceRecord>,
	material: &CodeIndexMaterial,
) -> FxHashMap<Vec<u8>, ReferenceSet> {
	(0..references.len())
		.into_par_iter()
		.map(|reference_idx| (reference_idx, &references[reference_idx]))
		.fold(
			FxHashMap::<Vec<u8>, ReferenceSet>::default,
			|mut index, item| {
				let (reference_idx, reference) = item;
				let Some(query) = LinkageQuery::new(reference, material) else {
					return index;
				};
				for key in query_keys(&query) {
					index
						.entry(key)
						.or_default()
						.insert(ReferenceOrdinal::from_index(reference_idx));
				}
				index
			},
		)
		.reduce(
			FxHashMap::<Vec<u8>, ReferenceSet>::default,
			merge_reference_set_maps,
		)
}

fn merge_reference_set_maps<K: Eq + Hash>(
	mut left: FxHashMap<K, ReferenceSet>,
	right: FxHashMap<K, ReferenceSet>,
) -> FxHashMap<K, ReferenceSet> {
	for (key, references) in right {
		left.entry(key).or_default().union_with(&references);
	}
	left
}

fn reference_source_root(
	reference: &ReferenceRecord,
	material: &CodeIndexMaterial,
) -> Option<usize> {
	let (file_idx, _) = material.identity.reference_location(&reference.id)?;
	material.files.get(file_idx).map(|file| file.source_root)
}