brokk_bifrost_python/

usage_index.rs

//! Analyzer-level re-export + importer index for Python, so both usage paths
//! resolve references through analyzer state. Built once from the analyzer's own
//! module index + `export_index_of` / `import_binder_of` and cached on
//! [`PythonAnalyzer`] (dropped on `update`/`update_all` like the other caches).
//!
//! Forward export seeds follow re-export chains
//! ([`PythonUsageIndex::seeds_for_target`]), and the reverse importer index
//! resolves which local names in an importer bind a seed
//! ([`PythonUsageIndex::matching_edges_for_importer`]). Candidate-file narrowing
//! stays in the forward path's scoped import closure (`PythonProjectGraph`), not
//! here. Module resolution reuses the analyzer's existing [`python_module_name`]
//! + [`resolve_python_relative_module`].

use brokk_bifrost_core::analyzer::query_token::QueryToken;
use brokk_bifrost_core::analyzer::usages::local_inference::LocalBindingsSnapshot;
use brokk_bifrost_core::analyzer::usages::model::{
    ExportEntry, ExportIndex, ImportBinder, ImportBinding, ImportKind,
};
use brokk_bifrost_core::analyzer::usages::reexport_seeds;
use brokk_bifrost_core::analyzer::usages::{ImportEdge, ImportEdgeKind};
use brokk_bifrost_core::analyzer::{CodeUnit, Language, ProjectFile};
use brokk_bifrost_core::hash::{HashMap, HashSet};
use std::collections::BTreeSet;
use std::sync::Arc;

use crate::declarations::python_module_name;
use crate::graph_support::{
    PythonModuleSpellings, PythonSource, PythonUsageSource, export_index_from_file_facts,
    import_binder_from_imports, import_bindings_from_imports, python_module_file_under_source_root,
    retain_modules_for_importer,
};
use crate::imports::{
    literal_importlib_modules, module_replacement_of, resolve_python_module_specifier,
};

/// Re-export and reverse-import indices over the Python workspace.
#[derive(Debug, Default)]
pub struct PythonUsageIndex {
    module_index: HashMap<String, Vec<ProjectFile>>,
    module_spellings: Arc<PythonModuleSpellings>,
    exports_by_file: HashMap<ProjectFile, Arc<ExportIndex>>,
    reexport_edges: HashMap<(ProjectFile, String), Vec<(ProjectFile, String)>>,
    star_reexports: HashMap<ProjectFile, Vec<ProjectFile>>,
    importer_reverse: HashMap<ProjectFile, Vec<ImportEdge>>,
    literal_importlib_importers: HashMap<ProjectFile, Vec<ProjectFile>>,
}

pub type ModuleBindingTimeline = HashMap<String, Vec<ModuleBindingEvent>>;
pub type PythonScopeFacts = HashMap<CodeUnit, LocalBindingsSnapshot<String>>;

#[derive(Clone, Debug)]
pub struct ModuleBindingEvent {
    pub visible_from: usize,
    pub conditional: bool,
    pub kind: ModuleBindingEventKind,
}

#[derive(Clone, Debug)]
pub enum ModuleBindingEventKind {
    ImportModule {
        module: String,
        consumed_attributes: usize,
    },
    FromImport {
        module: String,
        imported_name: String,
    },
    Other,
}

/// Keep events from the last unconditional binding through `cutoff`.
pub fn visible_module_binding_suffix(
    events: &[ModuleBindingEvent],
    cutoff: usize,
) -> impl Iterator<Item = &ModuleBindingEvent> {
    let visible: Vec<_> = events
        .iter()
        .filter(|event| event.visible_from <= cutoff)
        .collect();
    let start = visible
        .iter()
        .rposition(|event| !event.conditional)
        .unwrap_or(0);
    visible.into_iter().skip(start)
}

/// Resolve a module specifier to the files defining it: a leading-dot specifier
/// is made absolute against the importing file's package, then looked up in the
/// module index.
fn resolve_module(
    module_index: &HashMap<String, Vec<ProjectFile>>,
    module_spellings: &PythonModuleSpellings,
    importing_file: &ProjectFile,
    module_specifier: &str,
) -> Vec<ProjectFile> {
    let Some(project) = module_spellings.project() else {
        return Vec::new();
    };
    let resolved_module =
        resolve_python_module_specifier(project, importing_file, module_specifier);
    let Some(resolved_module) = resolved_module else {
        return Vec::new();
    };
    let mut files = module_index
        .get(&resolved_module)
        .cloned()
        .unwrap_or_default();
    // Two sibling source roots can index the same module name, so the root
    // that owns the importing file decides which of them its import means.
    retain_modules_for_importer(project, importing_file, &mut files, |file| file);
    if files.is_empty() {
        // No module name in the index spells the specifier, because it is
        // written against a source root the workspace does not state (#3506).
        files.extend(python_module_file_under_source_root(
            module_spellings,
            importing_file,
            &resolved_module,
        ));
    }
    files
}

fn is_sys_namespace_binding(binding: &ImportBinding) -> bool {
    is_namespace_binding_for_module(binding, "sys")
}

fn is_importlib_namespace_binding(binding: &ImportBinding) -> bool {
    is_namespace_binding_for_module(binding, "importlib")
}

fn is_namespace_binding_for_module(binding: &ImportBinding, module: &str) -> bool {
    binding.kind == ImportKind::Namespace
        && binding
            .namespace_imported_module
            .as_deref()
            .unwrap_or(&binding.module_specifier)
            == module
}

impl PythonUsageIndex {
    /// The complete immutable authority. Lazy per-file syntax memos are not part of it.
    pub fn authority_rows(&self) -> Vec<String> {
        let mut rows = self.module_spellings.authority_rows();
        for (name, files) in &self.module_index {
            for file in files {
                rows.push(format!(
                    "module:{name:?}:{:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file)
                ));
            }
        }
        for (file, exports) in &self.exports_by_file {
            rows.push(format!(
                "exports:{:?}:{:?}",
                brokk_bifrost_core::path_utils::rel_path_string(file),
                exports.exports_by_name.is_empty()
            ));
            for (name, export) in &exports.exports_by_name {
                rows.push(format!(
                    "export:{:?}:{name:?}:{export:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file)
                ));
            }
            for star in &exports.reexport_stars {
                rows.push(format!(
                    "star:{:?}:{star:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file)
                ));
            }
        }
        for ((file, name), targets) in &self.reexport_edges {
            for (target, export) in targets {
                rows.push(format!(
                    "reexport:{:?}:{name:?}:{:?}:{export:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file),
                    brokk_bifrost_core::path_utils::rel_path_string(target)
                ));
            }
        }
        for (file, targets) in &self.star_reexports {
            for target in targets {
                rows.push(format!(
                    "star_target:{:?}:{:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file),
                    brokk_bifrost_core::path_utils::rel_path_string(target)
                ));
            }
        }
        for (file, edges) in &self.importer_reverse {
            for edge in edges {
                rows.push(format!(
                    "importer:{:?}:{:?}:{:?}:{:?}:{:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file),
                    brokk_bifrost_core::path_utils::rel_path_string(&edge.importer),
                    edge.local_name,
                    brokk_bifrost_core::path_utils::rel_path_string(&edge.target_file),
                    edge.kind
                ));
            }
        }
        for (file, importers) in &self.literal_importlib_importers {
            for importer in importers {
                rows.push(format!(
                    "literal:{:?}:{:?}",
                    brokk_bifrost_core::path_utils::rel_path_string(file),
                    brokk_bifrost_core::path_utils::rel_path_string(importer)
                ));
            }
        }
        rows.sort();
        rows
    }

    /// Takes [`PythonSource`], not [`PythonUsageSource`]: the cell this
    /// build fills is only reachable through the latter, so the narrower
    /// parameter is what stops the build from re-entering it.
    pub fn build(
        python: &dyn PythonSource,
        token: QueryToken<'_>,
        keep_going: &dyn Fn() -> bool,
    ) -> Option<Self> {
        if !keep_going() {
            return None;
        }
        let _scope = brokk_bifrost_core::profiling::scope("PythonUsageIndex::build");
        let mut files: Vec<ProjectFile> = python
            .project()
            .analyzable_files(Language::Python)
            .map(|set| set.into_iter().collect())
            .unwrap_or_default();
        files.sort();
        files.dedup();

        let module_spellings = python.module_spellings();
        let mut module_index: HashMap<String, Vec<ProjectFile>> = HashMap::default();
        let mut exports_by_file: HashMap<ProjectFile, Arc<ExportIndex>> = HashMap::default();
        let mut binders_by_file: HashMap<ProjectFile, Arc<ImportBinder>> = HashMap::default();
        let mut import_bindings_by_file: HashMap<ProjectFile, Vec<(String, ImportBinding)>> =
            HashMap::default();
        let mut literal_importlib_modules_by_file: HashMap<ProjectFile, HashSet<String>> =
            HashMap::default();
        let mut replacement_modules: HashMap<ProjectFile, String> = HashMap::default();
        python.visit_file_facts(&files, keep_going, &mut |file, facts| {
            if !keep_going() {
                return;
            }
            let module_name = facts
                .and_then(|facts| {
                    facts
                        .top_level_declarations()
                        .iter()
                        .find(|unit| unit.is_module())
                })
                .map(|unit| unit.fq_name().to_string())
                .unwrap_or_else(|| python_module_name(python.project(), file));
            module_index
                .entry(module_name.clone())
                .or_default()
                .push(file.clone());
            if let Some(facts) = facts {
                let import_bindings = import_bindings_from_imports(python, file, facts.imports());
                let binder = Arc::new(import_binder_from_imports(python, file, facts.imports()));
                if binder.bindings.values().any(is_importlib_namespace_binding) {
                    literal_importlib_modules_by_file.insert(
                        file.clone(),
                        literal_importlib_modules(facts.source(), &binder.bindings),
                    );
                }
                if binder.bindings.values().any(is_sys_namespace_binding)
                    && let Some(replacement) =
                        module_replacement_of(python, file, facts.source(), facts.imports())
                {
                    replacement_modules.insert(file.clone(), replacement.target_module);
                }
                exports_by_file.insert(
                    file.clone(),
                    Arc::new(export_index_from_file_facts(
                        python,
                        file,
                        facts,
                        &module_name,
                    )),
                );
                import_bindings_by_file.insert(file.clone(), import_bindings);
                binders_by_file.insert(file.clone(), binder);
            } else {
                exports_by_file.insert(file.clone(), python.export_index_of(file));
                let binder = python.import_binder_of(file);
                let imports = python.import_info_of(token, file);
                if let Ok(source) = python.project().read_source(file) {
                    if binder.bindings.values().any(is_importlib_namespace_binding) {
                        literal_importlib_modules_by_file.insert(
                            file.clone(),
                            literal_importlib_modules(&source, &binder.bindings),
                        );
                    }
                    if binder.bindings.values().any(is_sys_namespace_binding)
                        && let Some(replacement) =
                            module_replacement_of(python, file, &source, &imports)
                    {
                        replacement_modules.insert(file.clone(), replacement.target_module);
                    }
                }
                import_bindings_by_file.insert(
                    file.clone(),
                    import_bindings_from_imports(python, file, &imports),
                );
                binders_by_file.insert(file.clone(), binder);
            }
        });
        for resolved in module_index.values_mut() {
            if !keep_going() {
                return None;
            }
            resolved.sort();
            resolved.dedup();
        }

        let mut raw_replacements: HashMap<ProjectFile, ProjectFile> = HashMap::default();
        for (file, target_module) in replacement_modules {
            if !keep_going() {
                return None;
            }
            let mut targets =
                resolve_module(&module_index, &module_spellings, &file, &target_module);
            if targets.len() != 1 {
                continue;
            }
            let target = targets.pop().expect("one module replacement target");
            if target != file {
                raw_replacements.insert(file, target);
            }
        }

        let mut canonical_replacements: HashMap<ProjectFile, ProjectFile> = HashMap::default();
        for file in raw_replacements.keys() {
            if !keep_going() {
                return None;
            }
            if let Some(target) = canonical_module_replacement(file, &raw_replacements) {
                canonical_replacements.insert(file.clone(), target);
            }
        }
        for resolved in module_index.values_mut() {
            if !keep_going() {
                return None;
            }
            let mut seen = HashSet::default();
            resolved.retain_mut(|file| {
                if let Some(canonical) = canonical_replacements.get(file) {
                    *file = canonical.clone();
                }
                seen.insert(file.clone())
            });
        }

        let mut reexport_edges: HashMap<(ProjectFile, String), Vec<(ProjectFile, String)>> =
            HashMap::default();
        let mut star_reexports: HashMap<ProjectFile, Vec<ProjectFile>> = HashMap::default();
        for (file, exports) in &exports_by_file {
            if !keep_going() {
                return None;
            }
            for (exported_name, entry) in &exports.exports_by_name {
                if !keep_going() {
                    return None;
                }
                match entry {
                    ExportEntry::Local { local_name } => {
                        let Some(binder) = binders_by_file.get(file) else {
                            continue;
                        };
                        let Some(binding) = binder.bindings.get(local_name) else {
                            continue;
                        };
                        let Some(imported_name) = binding.imported_name.as_ref() else {
                            continue;
                        };
                        for resolved_file in resolve_module(
                            &module_index,
                            &module_spellings,
                            file,
                            &binding.module_specifier,
                        ) {
                            reexport_edges
                                .entry((resolved_file, imported_name.clone()))
                                .or_default()
                                .push((file.clone(), exported_name.clone()));
                        }
                    }
                    // A re-exported module is a terminal binding: it carries
                    // no member name, so it opens no name-to-name edge.
                    ExportEntry::Default { .. } | ExportEntry::ReexportedModule { .. } => {}
                    ExportEntry::ReexportedNamed {
                        module_specifier,
                        imported_name,
                    } => {
                        for resolved_file in
                            resolve_module(&module_index, &module_spellings, file, module_specifier)
                        {
                            reexport_edges
                                .entry((resolved_file, imported_name.clone()))
                                .or_default()
                                .push((file.clone(), exported_name.clone()));
                        }
                    }
                }
            }
            for star in &exports.reexport_stars {
                for resolved_file in resolve_module(
                    &module_index,
                    &module_spellings,
                    file,
                    &star.module_specifier,
                ) {
                    star_reexports
                        .entry(resolved_file)
                        .or_default()
                        .push(file.clone());
                }
            }
        }

        if !keep_going() {
            return None;
        }
        let importer_reverse = build_importer_reverse(
            &module_index,
            &module_spellings,
            &files,
            &import_bindings_by_file,
            &exports_by_file,
            keep_going,
        )?;
        let mut literal_importlib_importers: HashMap<ProjectFile, Vec<ProjectFile>> =
            HashMap::default();
        for (importer, modules) in literal_importlib_modules_by_file {
            if !keep_going() {
                return None;
            }
            for module in modules {
                for target_file in
                    resolve_module(&module_index, &module_spellings, &importer, &module)
                {
                    literal_importlib_importers
                        .entry(target_file.clone())
                        .or_default()
                        .push(importer.clone());
                }
            }
        }
        for importers in literal_importlib_importers.values_mut() {
            if !keep_going() {
                return None;
            }
            importers.sort();
            importers.dedup();
        }

        if !keep_going() {
            return None;
        }
        Some(Self {
            module_index,
            module_spellings,
            exports_by_file,
            reexport_edges,
            star_reexports,
            importer_reverse,
            literal_importlib_importers,
        })
    }

    pub fn seeds_for_target(
        &self,
        target_file: &ProjectFile,
        target_short: &str,
    ) -> BTreeSet<(ProjectFile, String)> {
        let mut seeds: BTreeSet<(ProjectFile, String)> = BTreeSet::new();

        if let Some(exports) = self.exports_by_file.get(target_file) {
            for (exported_name, entry) in &exports.exports_by_name {
                let local = match entry {
                    ExportEntry::Local { local_name } => Some(local_name.as_str()),
                    ExportEntry::Default { local_name } => local_name.as_deref(),
                    ExportEntry::ReexportedNamed { .. } | ExportEntry::ReexportedModule { .. } => {
                        None
                    }
                };
                if let Some(local_name) = local
                    && local_name == target_short
                {
                    seeds.insert((target_file.clone(), exported_name.clone()));
                }
            }
        }

        reexport_seeds::expand_reexport_seeds(
            seeds,
            &self.reexport_edges,
            &self.star_reexports,
            |name| !name.starts_with('_'),
        )
    }

    pub fn matching_edges_for_importer(
        &self,
        importer: &ProjectFile,
        seeds: &BTreeSet<(ProjectFile, String)>,
    ) -> Vec<ImportEdge> {
        reexport_seeds::matching_edges_for_importer(&self.importer_reverse, importer, seeds)
    }

    pub fn importer_files_for_seeds(
        &self,
        seeds: &BTreeSet<(ProjectFile, String)>,
    ) -> HashSet<ProjectFile> {
        let mut importers = HashSet::default();
        for (target_file, _) in seeds {
            if let Some(edges) = self.importer_reverse.get(target_file) {
                importers.extend(
                    edges
                        .iter()
                        .filter(|edge| reexport_seeds::edge_matches_seed(edge, seeds))
                        .map(|edge| edge.importer.clone()),
                );
            }
            if let Some(dynamic_importers) = self.literal_importlib_importers.get(target_file) {
                importers.extend(dynamic_importers.iter().cloned());
            }
        }
        importers
    }

    pub fn resolve_module_files(
        &self,
        importing_file: &ProjectFile,
        module_specifier: &str,
    ) -> Vec<ProjectFile> {
        resolve_module(
            &self.module_index,
            &self.module_spellings,
            importing_file,
            module_specifier,
        )
    }

    pub(crate) fn relative_module_leaves_workspace(
        &self,
        importing_file: &ProjectFile,
        module_specifier: &str,
    ) -> bool {
        self.module_spellings.project().is_some_and(|project| {
            crate::imports::resolve_python_relative_module(
                project,
                importing_file,
                module_specifier,
            )
            .is_none()
        })
    }
}

fn canonical_module_replacement(
    file: &ProjectFile,
    replacements: &HashMap<ProjectFile, ProjectFile>,
) -> Option<ProjectFile> {
    let mut seen = BTreeSet::new();
    let mut current = file.clone();
    while let Some(target) = replacements.get(&current) {
        if !seen.insert(current) {
            return None;
        }
        current = target.clone();
    }
    Some(current)
}

fn build_importer_reverse(
    module_index: &HashMap<String, Vec<ProjectFile>>,
    module_spellings: &PythonModuleSpellings,
    files: &[ProjectFile],
    bindings_by_file: &HashMap<ProjectFile, Vec<(String, ImportBinding)>>,
    exports_by_file: &HashMap<ProjectFile, Arc<ExportIndex>>,
    keep_going: &dyn Fn() -> bool,
) -> Option<HashMap<ProjectFile, Vec<ImportEdge>>> {
    let mut reverse: HashMap<ProjectFile, Vec<ImportEdge>> = HashMap::default();
    for file in files {
        if !keep_going() {
            return None;
        }
        let Some(bindings) = bindings_by_file.get(file) else {
            continue;
        };
        for (local_name, binding) in bindings {
            let imported_module = binding
                .namespace_imported_module
                .as_deref()
                .unwrap_or(&binding.module_specifier);
            for target_file in resolve_module(module_index, module_spellings, file, imported_module)
            {
                // A glob `from m import *` binds every export of the target file
                // as a named edge, mirroring the graph it replaces.
                if matches!(binding.kind, ImportKind::Glob) {
                    let Some(exports) = exports_by_file.get(&target_file) else {
                        continue;
                    };
                    for export_name in exports.exports_by_name.keys() {
                        if export_name.starts_with('_') {
                            continue;
                        }
                        reverse
                            .entry(target_file.clone())
                            .or_default()
                            .push(ImportEdge {
                                importer: file.clone(),
                                local_name: export_name.clone(),
                                target_file: target_file.clone(),
                                kind: ImportEdgeKind::Named(export_name.clone()),
                            });
                    }
                    continue;
                }
                let kind = match (binding.kind, binding.imported_name.as_deref()) {
                    (ImportKind::Default, _) => ImportEdgeKind::Default,
                    (ImportKind::Namespace, _) => ImportEdgeKind::Namespace,
                    (ImportKind::Named, Some(name)) => ImportEdgeKind::Named(name.to_string()),
                    (ImportKind::Named, None) => ImportEdgeKind::Named(local_name.clone()),
                    // Python binders never emit CommonJsRequire; glob handled above.
                    (ImportKind::CommonJsRequire, _) | (ImportKind::Glob, _) => continue,
                };
                reverse
                    .entry(target_file.clone())
                    .or_default()
                    .push(ImportEdge {
                        importer: file.clone(),
                        local_name: local_name.clone(),
                        target_file,
                        kind,
                    });
            }
        }
    }
    keep_going().then_some(reverse)
}

/// Export seeds for the target, following re-export chains.
pub fn usage_seeds(
    python: &dyn PythonUsageSource,
    target_file: &ProjectFile,
    target_short: &str,
) -> BTreeSet<(ProjectFile, String)> {
    python
        .usage_index()
        .seeds_for_target(target_file, target_short)
}

/// The import edges in `importer` that bind one of the `seeds`.
pub fn usage_matching_edges(
    python: &dyn PythonUsageSource,
    importer: &ProjectFile,
    seeds: &BTreeSet<(ProjectFile, String)>,
) -> Vec<ImportEdge> {
    python
        .usage_index()
        .matching_edges_for_importer(importer, seeds)
}

pub fn usage_importer_files(
    python: &dyn PythonUsageSource,
    seeds: &BTreeSet<(ProjectFile, String)>,
) -> HashSet<ProjectFile> {
    python.usage_index().importer_files_for_seeds(seeds)
}

pub fn usage_resolve_module_files(
    python: &dyn PythonUsageSource,
    importing_file: &ProjectFile,
    module_specifier: &str,
) -> Vec<ProjectFile> {
    python
        .usage_index()
        .resolve_module_files(importing_file, module_specifier)
}

pub fn usage_module_binding_timeline(
    python: &dyn PythonUsageSource,
    file: &ProjectFile,
    build: impl FnOnce() -> ModuleBindingTimeline,
) -> Arc<ModuleBindingTimeline> {
    let mut build = Some(build);
    python.module_binding_timeline(file, &mut || {
        build.take().expect("memo builds at most once")()
    })
}

pub fn usage_scope_facts(
    python: &dyn PythonUsageSource,
    file: &ProjectFile,
    build: impl FnOnce() -> Option<PythonScopeFacts>,
) -> Option<Arc<PythonScopeFacts>> {
    let mut build = Some(build);
    python.scope_facts(file, &mut || {
        build.take().expect("memo builds at most once")()
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use brokk_bifrost_test_macros::hardwon;

    #[test]
    #[hardwon("59dfb80c3bb8: module replacement chains failed to canonicalize or reject cycles")]
    fn module_replacement_chains_canonicalize_and_cycles_are_rejected() {
        let root = tempfile::tempdir().expect("temporary project root");
        let first = ProjectFile::new(root.path(), "first.py");
        let second = ProjectFile::new(root.path(), "second.py");
        let canonical = ProjectFile::new(root.path(), "canonical.py");
        let chain = HashMap::from_iter([
            (first.clone(), second.clone()),
            (second.clone(), canonical.clone()),
        ]);

        assert_eq!(
            canonical_module_replacement(&first, &chain),
            Some(canonical)
        );

        let cycle = HashMap::from_iter([(first.clone(), second.clone()), (second, first.clone())]);
        assert_eq!(canonical_module_replacement(&first, &cycle), None);
    }
}