omena_parser/closed_world/

authority.rs

//! Closed-world linking authority: builds sealed bundles from linked-module facts.

use std::collections::{BTreeMap, BTreeSet, VecDeque};

use omena_syntax::ident::{AuthoredPropertyTextV0, CanonicalCustomPropertyNameV0};

use super::contract::{
    ClosedWorldBundleBuildErrorV0, ClosedWorldBundleEvidenceV0, ClosedWorldBundleV0,
    ClosedWorldComposesEdgeV0, ClosedWorldComposesScanStateV0,
    ClosedWorldInterfaceHashAvailabilityV0, ClosedWorldInterfaceHashEntryV0,
    ClosedWorldInterfaceHashSetV0, ClosedWorldLinkedModuleV0, ClosedWorldModuleMetadataV0,
    ClosedWorldModuleReachabilityEvidenceV0, ClosedWorldReachabilityBitsetParityReportV0,
    ClosedWorldSourcePrecisionSummaryV0, ModuleInstanceKeyV0, ModuleQualifiedSymbolSetV0,
    ReachabilityIndexV0,
};

impl ClosedWorldBundleV0 {
    pub fn try_from_linked_modules(
        entrypoints: Vec<ModuleInstanceKeyV0>,
        linked_modules: Vec<ClosedWorldLinkedModuleV0>,
    ) -> Result<Self, ClosedWorldBundleBuildErrorV0> {
        Self::try_from_linked_modules_with_metadata(entrypoints, linked_modules, Vec::new())
    }

    pub fn try_from_linked_modules_with_metadata(
        entrypoints: Vec<ModuleInstanceKeyV0>,
        linked_modules: Vec<ClosedWorldLinkedModuleV0>,
        module_metadata: Vec<ClosedWorldModuleMetadataV0>,
    ) -> Result<Self, ClosedWorldBundleBuildErrorV0> {
        if entrypoints.is_empty() {
            return Err(ClosedWorldBundleBuildErrorV0::EmptyEntrypoints);
        }

        let mut by_instance = BTreeMap::new();
        for module in linked_modules {
            by_instance.insert(module.instance.clone(), module);
        }
        let metadata_by_instance = module_metadata
            .into_iter()
            .map(|metadata| (metadata.module_instance().clone(), metadata))
            .collect::<BTreeMap<_, _>>();

        let reachability = compute_reachability(entrypoints.as_slice(), &by_instance)?;
        let linked_modules = reachability.module_instances().to_vec();
        let interface_hashes =
            interface_hashes_for_reachable_modules(&linked_modules, &metadata_by_instance);
        let source_precision =
            source_precision_for_reachable_modules(&linked_modules, &metadata_by_instance);
        let module_reachability_evidence =
            module_reachability_evidence_for_modules(&by_instance, &metadata_by_instance);
        let composes_edges = composes_edges_for_workspace_modules(&by_instance);
        let composes_scan_state =
            composes_scan_state_for_workspace_modules(&by_instance, &metadata_by_instance);
        let composes_edge_observation_count = by_instance
            .values()
            .map(|module| module.composes_edge_observation_count)
            .sum();
        let composes_origin_class_names = by_instance
            .iter()
            .map(|(instance, module)| {
                (
                    instance.clone(),
                    dedupe_symbol_names(module.class_names.as_slice()),
                )
            })
            .collect();
        let closure_hash = stable_closure_hash(entrypoints.as_slice(), &by_instance, &reachability);
        #[cfg(feature = "test-support")]
        crate::record_closed_world_bundle_construction_for_test();

        Ok(Self::seal(
            entrypoints,
            linked_modules,
            reachability,
            closure_hash,
            ClosedWorldBundleEvidenceV0 {
                interface_hashes,
                source_precision,
                composes_edges,
                composes_scan_state,
                composes_edge_observation_count,
                composes_origin_class_names,
                module_reachability_evidence,
            },
        ))
    }
}

fn composes_scan_state_for_workspace_modules(
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
    metadata_by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleMetadataV0>,
) -> ClosedWorldComposesScanStateV0 {
    if by_instance.keys().all(|instance| {
        metadata_by_instance.get(instance).is_some_and(|metadata| {
            metadata.composes_scan_state() == ClosedWorldComposesScanStateV0::ScannedClosed
        })
    }) {
        ClosedWorldComposesScanStateV0::ScannedClosed
    } else {
        ClosedWorldComposesScanStateV0::SourceSetOpen
    }
}

fn composes_edges_for_workspace_modules(
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
) -> Vec<ClosedWorldComposesEdgeV0> {
    let mut edges = by_instance
        .values()
        .flat_map(|module| module.composes_edges.iter().cloned())
        .collect::<Vec<_>>();
    edges.sort_by(|left, right| {
        (
            &left.from_module,
            &left.from_symbol,
            &left.to_module,
            &left.to_symbol,
        )
            .cmp(&(
                &right.from_module,
                &right.from_symbol,
                &right.to_module,
                &right.to_symbol,
            ))
    });
    edges.dedup();
    edges
}

fn module_reachability_evidence_for_modules(
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
    metadata_by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleMetadataV0>,
) -> BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleReachabilityEvidenceV0> {
    by_instance
        .keys()
        .cloned()
        .map(|instance| {
            let evidence = metadata_by_instance
                .get(&instance)
                .map(ClosedWorldModuleMetadataV0::reachability_evidence)
                .unwrap_or_default();
            (instance, evidence)
        })
        .collect()
}

fn interface_hashes_for_reachable_modules(
    reachable: &[ModuleInstanceKeyV0],
    metadata_by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleMetadataV0>,
) -> ClosedWorldInterfaceHashSetV0 {
    ClosedWorldInterfaceHashSetV0::new(
        reachable
            .iter()
            .map(|instance| ClosedWorldInterfaceHashEntryV0 {
                module_instance: instance.clone(),
                availability: metadata_by_instance
                    .get(instance)
                    .and_then(|metadata| metadata.interface_hash())
                    .map_or(
                        ClosedWorldInterfaceHashAvailabilityV0::Absent,
                        |interface_hash| ClosedWorldInterfaceHashAvailabilityV0::Known {
                            interface_hash: interface_hash.to_string(),
                        },
                    ),
            })
            .collect(),
    )
}

fn source_precision_for_reachable_modules(
    reachable: &[ModuleInstanceKeyV0],
    metadata_by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldModuleMetadataV0>,
) -> Option<ClosedWorldSourcePrecisionSummaryV0> {
    let mut aggregate = ClosedWorldSourcePrecisionSummaryV0::default();
    let mut observed = false;
    for instance in reachable {
        if let Some(source_precision) = metadata_by_instance
            .get(instance)
            .and_then(ClosedWorldModuleMetadataV0::source_precision)
        {
            aggregate.merge(source_precision);
            observed = true;
        }
    }
    observed.then_some(aggregate)
}

pub fn summarize_closed_world_reachability_bitset_parity_v0(
    entrypoints: Vec<ModuleInstanceKeyV0>,
    linked_modules: Vec<ClosedWorldLinkedModuleV0>,
) -> Result<ClosedWorldReachabilityBitsetParityReportV0, ClosedWorldBundleBuildErrorV0> {
    if entrypoints.is_empty() {
        return Err(ClosedWorldBundleBuildErrorV0::EmptyEntrypoints);
    }

    let mut by_instance = BTreeMap::new();
    for module in linked_modules {
        by_instance.insert(module.instance.clone(), module);
    }

    let btreeset_reachability = compute_reachability(entrypoints.as_slice(), &by_instance)?;
    let bitset_reachability = compute_reachability_bitset(entrypoints.as_slice(), &by_instance)?;
    let btreeset_closure_hash =
        stable_closure_hash(entrypoints.as_slice(), &by_instance, &btreeset_reachability);
    let bitset_closure_hash =
        stable_closure_hash(entrypoints.as_slice(), &by_instance, &bitset_reachability);
    let symbol_name_count = bitset_reachability
        .class_names()
        .len()
        .saturating_add(bitset_reachability.keyframe_names().len())
        .saturating_add(bitset_reachability.value_names().len())
        .saturating_add(bitset_reachability.custom_property_names().len());

    Ok(ClosedWorldReachabilityBitsetParityReportV0 {
        schema_version: "0",
        product: "omena-parser.closed-world-reachability-bitset-parity",
        module_instance_count: bitset_reachability.module_instances().len(),
        symbol_name_count,
        module_qualified_symbols: btreeset_reachability.module_qualified_symbols().to_vec(),
        reachability_equal: btreeset_reachability == bitset_reachability,
        closure_hash_equal: btreeset_closure_hash == bitset_closure_hash,
        btreeset_closure_hash,
        bitset_closure_hash,
    })
}

fn compute_reachability(
    entrypoints: &[ModuleInstanceKeyV0],
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
) -> Result<ReachabilityIndexV0, ClosedWorldBundleBuildErrorV0> {
    let mut queue = VecDeque::new();
    let mut seen = BTreeSet::new();
    for entrypoint in entrypoints {
        if !by_instance.contains_key(entrypoint) {
            return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint {
                module: entrypoint.clone(),
            });
        }
        queue.push_back(entrypoint.clone());
    }

    while let Some(instance) = queue.pop_front() {
        if !seen.insert(instance.clone()) {
            continue;
        }
        let Some(module) = by_instance.get(&instance) else {
            return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint { module: instance });
        };
        for dependency in &module.dependencies {
            if !by_instance.contains_key(dependency) {
                return Err(ClosedWorldBundleBuildErrorV0::MissingDependency {
                    module: instance.clone(),
                    dependency: dependency.clone(),
                });
            }
            queue.push_back(dependency.clone());
        }
    }

    reachability_index_from_seen(&seen, by_instance)
}

fn compute_reachability_bitset(
    entrypoints: &[ModuleInstanceKeyV0],
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
) -> Result<ReachabilityIndexV0, ClosedWorldBundleBuildErrorV0> {
    for entrypoint in entrypoints {
        if !by_instance.contains_key(entrypoint) {
            return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint {
                module: entrypoint.clone(),
            });
        }
    }
    let dense_index = DenseModuleInstanceIndexV0::from_modules(entrypoints, by_instance);
    let mut seen = DenseModuleInstanceBitsetV0::new(dense_index.len());
    let mut queue = entrypoints
        .iter()
        .filter_map(|entrypoint| dense_index.index_of(entrypoint))
        .collect::<VecDeque<_>>();

    while let Some(instance_index) = queue.pop_front() {
        if !seen.insert(instance_index) {
            continue;
        }
        let instance = dense_index.instance(instance_index);
        let Some(module) = by_instance.get(instance) else {
            return Err(ClosedWorldBundleBuildErrorV0::MissingEntrypoint {
                module: instance.clone(),
            });
        };
        for dependency in &module.dependencies {
            if !by_instance.contains_key(dependency) {
                return Err(ClosedWorldBundleBuildErrorV0::MissingDependency {
                    module: instance.clone(),
                    dependency: dependency.clone(),
                });
            }
            if let Some(dependency_index) = dense_index.index_of(dependency) {
                queue.push_back(dependency_index);
            }
        }
    }

    let seen_instances = dense_index.instances_for_bitset(&seen);
    reachability_index_from_seen(&seen_instances, by_instance)
}

fn reachability_index_from_seen(
    seen: &BTreeSet<ModuleInstanceKeyV0>,
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
) -> Result<ReachabilityIndexV0, ClosedWorldBundleBuildErrorV0> {
    let mut class_names = BTreeSet::new();
    let mut keyframe_names = BTreeSet::new();
    let mut value_names = BTreeSet::new();
    let mut custom_property_names = BTreeMap::new();
    let mut module_qualified_symbols = Vec::with_capacity(by_instance.len());

    for (instance, module) in by_instance {
        let reachable = seen.contains(instance);
        if reachable {
            class_names.extend(module.class_names.iter().cloned());
            keyframe_names.extend(module.keyframe_names.iter().cloned());
            value_names.extend(module.value_names.iter().cloned());
            extend_custom_property_names(
                &mut custom_property_names,
                module.custom_property_names.iter().cloned(),
            );
        }
        let qualified_class_names = if reachable {
            dedupe_symbol_names(&module.class_names)
        } else {
            Vec::new()
        };
        let qualified_keyframe_names = if reachable {
            dedupe_symbol_names(&module.keyframe_names)
        } else {
            Vec::new()
        };
        let qualified_value_names = if reachable {
            dedupe_symbol_names(&module.value_names)
        } else {
            Vec::new()
        };
        let qualified_custom_property_names = if reachable {
            dedupe_custom_property_names(&module.custom_property_names)
        } else {
            Vec::new()
        };
        module_qualified_symbols.push(ModuleQualifiedSymbolSetV0::new(
            instance.clone(),
            reachable,
            qualified_class_names,
            qualified_keyframe_names,
            qualified_value_names,
            qualified_custom_property_names,
        ));
    }

    Ok(ReachabilityIndexV0::from_parts(
        seen.iter().cloned().collect(),
        module_qualified_symbols,
        class_names.into_iter().collect(),
        keyframe_names.into_iter().collect(),
        value_names.into_iter().collect(),
        custom_property_names.into_values().collect(),
    ))
}

fn dedupe_symbol_names(names: &[String]) -> Vec<String> {
    names
        .iter()
        .cloned()
        .collect::<BTreeSet<_>>()
        .into_iter()
        .collect()
}

fn dedupe_custom_property_names(names: &[AuthoredPropertyTextV0]) -> Vec<AuthoredPropertyTextV0> {
    let mut by_identity = BTreeMap::new();
    extend_custom_property_names(&mut by_identity, names.iter().cloned());
    by_identity.into_values().collect()
}

fn extend_custom_property_names(
    by_identity: &mut BTreeMap<CanonicalCustomPropertyNameV0, AuthoredPropertyTextV0>,
    names: impl IntoIterator<Item = AuthoredPropertyTextV0>,
) {
    for authored in names {
        by_identity
            .entry(authored.to_custom_key())
            .or_insert(authored);
    }
}

#[derive(Debug, Clone)]
struct DenseModuleInstanceIndexV0 {
    instances: Vec<ModuleInstanceKeyV0>,
    positions: BTreeMap<ModuleInstanceKeyV0, usize>,
}

impl DenseModuleInstanceIndexV0 {
    fn from_modules(
        entrypoints: &[ModuleInstanceKeyV0],
        by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
    ) -> Self {
        let mut instances = BTreeSet::new();
        instances.extend(entrypoints.iter().cloned());
        for (instance, module) in by_instance {
            instances.insert(instance.clone());
            instances.extend(module.dependencies.iter().cloned());
        }
        let instances = instances.into_iter().collect::<Vec<_>>();
        let positions = instances
            .iter()
            .enumerate()
            .map(|(index, instance)| (instance.clone(), index))
            .collect::<BTreeMap<_, _>>();
        Self {
            instances,
            positions,
        }
    }

    fn len(&self) -> usize {
        self.instances.len()
    }

    fn index_of(&self, instance: &ModuleInstanceKeyV0) -> Option<usize> {
        self.positions.get(instance).copied()
    }

    fn instance(&self, index: usize) -> &ModuleInstanceKeyV0 {
        &self.instances[index]
    }

    fn instances_for_bitset(
        &self,
        bitset: &DenseModuleInstanceBitsetV0,
    ) -> BTreeSet<ModuleInstanceKeyV0> {
        self.instances
            .iter()
            .enumerate()
            .filter(|(index, _)| bitset.contains(*index))
            .map(|(_, instance)| instance.clone())
            .collect()
    }
}

#[derive(Debug, Clone)]
struct DenseModuleInstanceBitsetV0 {
    words: Vec<u64>,
}

impl DenseModuleInstanceBitsetV0 {
    fn new(len: usize) -> Self {
        Self {
            words: vec![0; len.div_ceil(64)],
        }
    }

    fn insert(&mut self, index: usize) -> bool {
        let word_index = index / 64;
        let mask = 1u64 << (index % 64);
        let word = &mut self.words[word_index];
        let was_empty = *word & mask == 0;
        *word |= mask;
        was_empty
    }

    fn contains(&self, index: usize) -> bool {
        self.words
            .get(index / 64)
            .is_some_and(|word| word & (1u64 << (index % 64)) != 0)
    }
}

fn stable_closure_hash(
    entrypoints: &[ModuleInstanceKeyV0],
    by_instance: &BTreeMap<ModuleInstanceKeyV0, ClosedWorldLinkedModuleV0>,
    reachability: &ReachabilityIndexV0,
) -> String {
    let mut hash = StableFnv64::new();
    hash.piece("omena-parser.closed-world-bundle");
    for entrypoint in entrypoints {
        hash.instance(entrypoint);
    }
    for instance in reachability.module_instances() {
        hash.instance(instance);
        if let Some(module) = by_instance.get(instance) {
            for dependency in &module.dependencies {
                hash.instance(dependency);
            }
        }
    }
    for edge in composes_edges_for_workspace_modules(by_instance) {
        hash.piece("composes");
        hash.instance(&edge.from_module);
        hash.piece(&edge.from_symbol);
        hash.instance(&edge.to_module);
        hash.piece(&edge.to_symbol);
    }
    for name in reachability.class_names() {
        hash.piece("class");
        hash.piece(name);
    }
    for name in reachability.keyframe_names() {
        hash.piece("keyframe");
        hash.piece(name);
    }
    for name in reachability.value_names() {
        hash.piece("value");
        hash.piece(name);
    }
    for name in reachability.custom_property_names() {
        hash.piece("custom-property");
        hash.piece(name.to_custom_key().as_str());
    }
    hash.finish_hex()
}

struct StableFnv64(u64);

impl StableFnv64 {
    fn new() -> Self {
        Self(0xcbf2_9ce4_8422_2325)
    }

    fn piece(&mut self, value: &str) {
        for byte in value.as_bytes().iter().copied().chain([0]) {
            self.0 ^= u64::from(byte);
            self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
        }
    }

    fn instance(&mut self, instance: &ModuleInstanceKeyV0) {
        self.piece(instance.module().as_str());
        self.piece(instance.configuration().as_str());
    }

    fn finish_hex(self) -> String {
        format!("{:016x}", self.0)
    }
}