code_moniker_workspace/snapshot/inventory/

mod.rs

mod catalog;
mod facets;
mod set;

use std::collections::BTreeSet;
use std::hash::{Hash, Hasher};
use std::sync::Arc;

use code_moniker_core::core::shape::Shape;
use code_moniker_core::core::uri::{UriConfig, from_uri};
use rustc_hash::FxHashMap;

use super::{RecordTable, ResourceGeneration, SourceFileRecord, SourceId, SymbolId, SymbolRecord};

pub use catalog::SymbolOrdinalCatalog;
pub use facets::SymbolInventoryFacets;
pub use set::SymbolSet;

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct SymbolOrdinal(u32);

impl SymbolOrdinal {
	pub fn from_index(value: usize) -> Self {
		assert!(
			u32::try_from(value).is_ok(),
			"symbol index exceeds u32 range"
		);
		Self(value as u32)
	}

	pub fn as_usize(self) -> usize {
		self.0 as usize
	}

	pub fn raw(self) -> u32 {
		self.0
	}
}

#[derive(Clone, Debug, Eq, Hash, PartialEq)]
pub struct InventorySegment {
	pub kind: Arc<str>,
	pub name: Arc<str>,
}

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct InventorySymbol {
	pub id: SymbolId,
	pub source: SourceId,
	pub identity: Arc<str>,
	pub name: Arc<str>,
	pub kind: Arc<str>,
	pub shape: Arc<str>,
	pub visibility: Arc<str>,
	pub language: Arc<str>,
	pub source_path: Arc<str>,
	pub source_root: usize,
	pub srcset: Arc<str>,
	pub line_range: Option<(u32, u32)>,
	pub parent: Option<SymbolId>,
	pub segments: Arc<[InventorySegment]>,
}

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct SymbolInventoryIndex {
	generation: ResourceGeneration,
	catalog: Arc<SymbolOrdinalCatalog>,
	records: FxHashMap<SymbolOrdinal, InventorySymbol>,
	all_symbols: SymbolSet,
	facets: SymbolInventoryFacets,
	compact_identities: FxHashMap<u64, SymbolOrdinal>,
	compact_identity_collisions: FxHashMap<u64, Vec<SymbolOrdinal>>,
}

impl Default for SymbolInventoryIndex {
	fn default() -> Self {
		Self::empty(ResourceGeneration::new(0))
	}
}

impl SymbolInventoryIndex {
	pub(crate) fn estimated_heap_bytes(&self) -> usize {
		let mut strings = std::collections::HashSet::<(usize, usize)>::new();
		let mut string_bytes = 0usize;
		let mut segment_bytes = 0usize;
		for record in self.records.values() {
			for value in [
				&record.identity,
				&record.name,
				&record.kind,
				&record.shape,
				&record.visibility,
				&record.language,
				&record.source_path,
				&record.srcset,
			] {
				if strings.insert((value.as_ptr() as usize, value.len())) {
					string_bytes += value.len();
				}
			}
			segment_bytes += record.segments.len() * std::mem::size_of::<InventorySegment>();
			for segment in record.segments.iter() {
				for value in [&segment.kind, &segment.name] {
					if strings.insert((value.as_ptr() as usize, value.len())) {
						string_bytes += value.len();
					}
				}
			}
		}
		self.records.capacity()
			* (std::mem::size_of::<SymbolOrdinal>() + std::mem::size_of::<InventorySymbol>())
			+ self.catalog.estimated_heap_bytes()
			+ self.all_symbols.estimated_heap_bytes()
			+ self.facets.estimated_heap_bytes()
			+ self.compact_identities.capacity()
				* (std::mem::size_of::<u64>() + std::mem::size_of::<SymbolOrdinal>())
			+ self
				.compact_identity_collisions
				.values()
				.map(|ordinals| ordinals.capacity() * std::mem::size_of::<SymbolOrdinal>())
				.sum::<usize>()
			+ self.compact_identity_collisions.capacity()
				* (std::mem::size_of::<u64>() + std::mem::size_of::<Vec<SymbolOrdinal>>())
			+ segment_bytes
			+ string_bytes
	}

	pub fn empty(generation: ResourceGeneration) -> Self {
		Self {
			generation,
			catalog: Arc::new(SymbolOrdinalCatalog::default()),
			records: FxHashMap::default(),
			all_symbols: SymbolSet::new(),
			facets: SymbolInventoryFacets::default(),
			compact_identities: FxHashMap::default(),
			compact_identity_collisions: FxHashMap::default(),
		}
	}

	pub fn build(
		generation: ResourceGeneration,
		sources: &[SourceFileRecord],
		symbols: &RecordTable<SymbolRecord>,
	) -> Self {
		let mut inventory = Self::empty(generation);
		for symbol in symbols.iter() {
			let fallback = missing_source(symbol.source);
			let source = sources.get(symbol.source.file()).unwrap_or(&fallback);
			index_record(&mut inventory, symbol, source, None);
		}
		inventory
	}

	pub fn refresh(
		&self,
		generation: ResourceGeneration,
		sources: &[SourceFileRecord],
		symbols: &RecordTable<SymbolRecord>,
		changed_files: &BTreeSet<usize>,
	) -> Self {
		refresh_inventory(self, generation, sources, symbols, changed_files)
	}

	pub fn generation(&self) -> ResourceGeneration {
		self.generation
	}

	pub fn catalog(&self) -> &Arc<SymbolOrdinalCatalog> {
		&self.catalog
	}

	pub fn all_symbols(&self) -> &SymbolSet {
		&self.all_symbols
	}

	pub fn record(&self, ordinal: SymbolOrdinal) -> Option<&InventorySymbol> {
		self.records.get(&ordinal)
	}

	pub fn record_by_id(&self, id: &SymbolId) -> Option<&InventorySymbol> {
		self.catalog
			.ordinal(id)
			.and_then(|ordinal| self.record(ordinal))
	}

	pub fn symbol_ids_by_identity(&self, identity: &str) -> Vec<SymbolId> {
		self.facets
			.symbols_by_identity(identity)
			.into_iter()
			.flat_map(SymbolSet::iter)
			.filter_map(|ordinal| self.catalog.id(ordinal).copied())
			.collect()
	}

	pub fn symbol_ids_by_compact_identity(&self, compact: &str) -> Vec<SymbolId> {
		let hash = compact_identity_hash(compact);
		let candidates = self
			.compact_identity_collisions
			.get(&hash)
			.map(Vec::as_slice)
			.or_else(|| self.compact_identities.get(&hash).map(std::slice::from_ref))
			.unwrap_or_default();
		candidates
			.iter()
			.copied()
			.filter_map(|ordinal| self.record(ordinal))
			.filter(|record| {
				compact_record_identity(record.identity.as_ref()).as_deref() == Some(compact)
			})
			.map(|record| record.id)
			.collect()
	}

	pub fn facets(&self) -> &SymbolInventoryFacets {
		&self.facets
	}
}

fn index_record(
	inventory: &mut SymbolInventoryIndex,
	symbol: &SymbolRecord,
	source: &SourceFileRecord,
	preferred_ordinal: Option<SymbolOrdinal>,
) {
	let catalog = Arc::make_mut(&mut inventory.catalog);
	let ordinal = match preferred_ordinal {
		Some(ordinal) => {
			catalog.bind_id(ordinal, symbol.id);
			ordinal
		}
		None => catalog.push(symbol.id),
	};
	if inventory.records.contains_key(&ordinal) {
		unindex_record(inventory, ordinal);
	}
	let record = inventory_record(symbol, source);
	inventory.all_symbols.insert(ordinal);
	facets::insert_facets(&mut inventory.facets, &record, ordinal);
	if let Some(compact) = compact_record_identity(record.identity.as_ref()) {
		index_compact_identity(inventory, compact_identity_hash(&compact), ordinal);
	}
	inventory.records.insert(ordinal, record);
}

fn inventory_record(symbol: &SymbolRecord, source: &SourceFileRecord) -> InventorySymbol {
	let segments = parse_segments(&symbol.identity);
	let srcset = segments
		.iter()
		.filter(|segment| segment.kind.as_ref() == "srcset")
		.map(|segment| segment.name.as_ref())
		.collect::<Vec<_>>()
		.join(".");
	InventorySymbol {
		id: symbol.id,
		source: symbol.source,
		identity: Arc::clone(&symbol.identity),
		name: Arc::from(symbol.name.as_str()),
		kind: Arc::from(symbol.kind.as_str()),
		shape: Arc::from(Shape::for_kind(symbol.kind.as_bytes()).as_str()),
		visibility: Arc::from(symbol.visibility.as_str()),
		language: Arc::from(source.language.as_str()),
		source_path: Arc::from(source.path.as_str()),
		source_root: source.source_root,
		srcset: Arc::from(srcset),
		line_range: symbol.line_range,
		parent: symbol.parent,
		segments: Arc::from(segments),
	}
}

fn parse_segments(identity: &str) -> Vec<InventorySegment> {
	let marker = "+moniker://";
	let scheme_end = identity.find(marker).map(|index| index + marker.len());
	let Some(scheme) = scheme_end.and_then(|end| identity.get(..end)) else {
		return Vec::new();
	};
	let Ok(moniker) = from_uri(identity, &UriConfig { scheme }) else {
		return Vec::new();
	};
	moniker
		.as_view()
		.segments()
		.filter_map(|segment| {
			Some(InventorySegment {
				kind: Arc::from(std::str::from_utf8(segment.kind).ok()?),
				name: Arc::from(std::str::from_utf8(segment.name).ok()?),
			})
		})
		.collect()
}

fn unindex_record(inventory: &mut SymbolInventoryIndex, ordinal: SymbolOrdinal) {
	let Some(record) = inventory.records.remove(&ordinal) else {
		return;
	};
	inventory.all_symbols.remove(ordinal);
	facets::remove_facets(&mut inventory.facets, &record, ordinal);
	if let Some(compact) = compact_record_identity(record.identity.as_ref()) {
		let hash = compact_identity_hash(&compact);
		unindex_compact_identity(inventory, hash, ordinal);
	}
}

fn index_compact_identity(inventory: &mut SymbolInventoryIndex, hash: u64, ordinal: SymbolOrdinal) {
	let Some(existing) = inventory.compact_identities.get(&hash).copied() else {
		inventory.compact_identities.insert(hash, ordinal);
		return;
	};
	let collisions = inventory
		.compact_identity_collisions
		.entry(hash)
		.or_insert_with(|| vec![existing]);
	if !collisions.contains(&ordinal) {
		collisions.push(ordinal);
	}
}

fn unindex_compact_identity(
	inventory: &mut SymbolInventoryIndex,
	hash: u64,
	ordinal: SymbolOrdinal,
) {
	if let Some(collisions) = inventory.compact_identity_collisions.get_mut(&hash) {
		collisions.retain(|candidate| *candidate != ordinal);
		match collisions.as_slice() {
			[] => {
				inventory.compact_identities.remove(&hash);
				inventory.compact_identity_collisions.remove(&hash);
			}
			[remaining] => {
				inventory.compact_identities.insert(hash, *remaining);
				inventory.compact_identity_collisions.remove(&hash);
			}
			_ => {}
		}
	} else if inventory.compact_identities.get(&hash) == Some(&ordinal) {
		inventory.compact_identities.remove(&hash);
	}
}

fn compact_identity_hash(compact: &str) -> u64 {
	let mut hasher = rustc_hash::FxHasher::default();
	compact.hash(&mut hasher);
	hasher.finish()
}

fn compact_record_identity(identity: &str) -> Option<String> {
	let scheme_end = identity.find("://")? + 3;
	let scheme = &identity[..scheme_end];
	crate::code::compact_identity(identity, scheme)
}

fn refresh_inventory(
	previous: &SymbolInventoryIndex,
	generation: ResourceGeneration,
	sources: &[SourceFileRecord],
	symbols: &RecordTable<SymbolRecord>,
	changed_files: &BTreeSet<usize>,
) -> SymbolInventoryIndex {
	let mut inventory = previous.clone();
	inventory.generation = generation;
	let pending_retire = changed_ordinals(&inventory, changed_files);
	let mut reusable_ordinals = FxHashMap::<(SourceId, Arc<str>), Vec<SymbolOrdinal>>::default();
	for ordinal in &pending_retire {
		if let Some(record) = inventory.record(*ordinal) {
			reusable_ordinals
				.entry((record.source, Arc::clone(&record.identity)))
				.or_default()
				.push(*ordinal);
		}
	}
	for ordinal in &pending_retire {
		unindex_record(&mut inventory, *ordinal);
		Arc::make_mut(&mut inventory.catalog).unbind_id(*ordinal);
	}
	for file in changed_files {
		for symbol in symbols.file_records(*file) {
			let fallback = missing_source(symbol.source);
			let source = sources.get(*file).unwrap_or(&fallback);
			let key = (symbol.source, Arc::clone(&symbol.identity));
			let preferred = reusable_ordinals.get_mut(&key).and_then(Vec::pop);
			index_record(&mut inventory, symbol, source, preferred);
		}
	}
	for ordinal in pending_retire {
		if inventory.catalog.id(ordinal).is_none() {
			Arc::make_mut(&mut inventory.catalog).retire(ordinal);
		}
	}
	inventory
}

fn missing_source(source: SourceId) -> SourceFileRecord {
	SourceFileRecord {
		id: source,
		uri: String::new(),
		source_root: 0,
		path: String::new(),
		rel_path: String::new(),
		anchor: String::new(),
		language: String::new(),
		text: String::new(),
	}
}

fn changed_ordinals(
	inventory: &SymbolInventoryIndex,
	changed_files: &BTreeSet<usize>,
) -> Vec<SymbolOrdinal> {
	let mut changed = SymbolSet::new();
	for file in changed_files {
		if let Some(symbols) = inventory.facets.symbols_by_source(SourceId::at(*file)) {
			changed.union_with(symbols);
		}
	}
	changed.iter().collect()
}

#[cfg(test)]
mod tests;