crates/core/src/driver/unpack_cycles.rs

GitHub
use std::collections::{HashMap, HashSet};

use swc_core::common::{sync::Lrc, Mark, SourceMap, GLOBALS};
use swc_core::ecma::ast::{
    Decl, ImportDecl, ImportSpecifier, Module, ModuleDecl, ModuleItem, Stmt, Str,
};
use swc_core::ecma::transforms::base::resolver;
use swc_core::ecma::visit::VisitMutWith;

use super::diagnostics::collect_duplicate_declaration_warnings;
use super::io::{apply_fixer, parse_js, print_js};
use super::types::{UnpackWarning, UnpackWarningKind};
use super::unpack_cleanup::{
    dedup_duplicate_exports, hoist_late_runtime_helpers, module_export_name_string,
};
use crate::rules::ImportDedup;
use crate::unpacker::module_item_declared_binding_ids;

pub(crate) fn merge_import_cycles(
    modules: Vec<crate::unpacker::UnpackedModule>,
) -> (Vec<crate::unpacker::UnpackedModule>, Vec<UnpackWarning>) {
    const FAST_PREFLIGHT_MIN_MEMBERS: usize = 64;
    const MAX_SAFE_CYCLE_MERGE_MEMBERS: usize = 32;

    let (module_names, graph) = {
        let span = tracing::info_span!("merge_cycles_build_graph");
        let _enter = span.enter();
        let module_pairs: Vec<(String, String)> = modules
            .iter()
            .map(|module| (module.filename.clone(), module.code.clone()))
            .collect();
        let module_names: HashSet<String> = module_pairs
            .iter()
            .map(|(filename, _)| filename.clone())
            .collect();
        let mut graph: HashMap<String, Vec<String>> = HashMap::new();
        for (filename, code) in &module_pairs {
            graph.insert(
                filename.clone(),
                local_import_dependencies(filename, code, &module_names),
            );
        }
        (module_names, graph)
    };

    let index_by_filename: HashMap<String, usize> = modules
        .iter()
        .enumerate()
        .map(|(index, module)| (module.filename.clone(), index))
        .collect();
    let cycle_components: Vec<Vec<String>> = {
        let span = tracing::info_span!("merge_cycles_tarjan");
        let _enter = span.enter();
        tarjan_sccs(&graph)
            .into_iter()
            .filter(|component| {
                component.len() > 1
                    || component
                        .first()
                        .is_some_and(|filename| graph[filename].contains(filename))
            })
            .collect()
    };
    if cycle_components.is_empty() {
        return (modules, Vec::new());
    }

    let mut file_to_component: HashMap<String, usize> = HashMap::new();
    let mut component_members: Vec<Vec<String>> = Vec::new();
    let mut component_representatives: Vec<String> = Vec::new();
    let mut warnings = Vec::new();
    let module_by_filename: HashMap<String, &crate::unpacker::UnpackedModule> = modules
        .iter()
        .map(|module| (module.filename.clone(), module))
        .collect();

    for mut component in cycle_components {
        component.sort_by_key(|filename| index_by_filename[filename]);
        let representative = component
            .iter()
            .find(|filename| filename.as_str() == "entry.js")
            .cloned()
            .unwrap_or_else(|| component[0].clone());
        let preview = component
            .iter()
            .take(8)
            .cloned()
            .collect::<Vec<_>>()
            .join(" -> ");
        let suffix = if component.len() > 8 { " -> ..." } else { "" };
        let member_set: HashSet<String> = component.iter().cloned().collect();
        if component.len() > MAX_SAFE_CYCLE_MERGE_MEMBERS {
            warnings.push(UnpackWarning::new(
                representative.clone(),
                UnpackWarningKind::ImportCycle,
                format!(
                    "local import cycle across {} modules not merged because it exceeds the large-cycle merge limit of {MAX_SAFE_CYCLE_MERGE_MEMBERS}: {preview}{suffix}",
                    component.len()
                ),
            ));
            continue;
        }
        {
            let span = tracing::info_span!(
                "merge_cycles_preflight_component",
                representative = %representative,
                count = component.len()
            );
            let _enter = span.enter();
            let reason = if should_use_fast_cycle_preflight(&component, FAST_PREFLIGHT_MIN_MEMBERS)
            {
                unsafe_merge_member_reason(
                    &component,
                    &module_by_filename,
                    &module_names,
                    &member_set,
                )
            } else {
                unsafe_merged_cycle_candidate_reason(
                    &representative,
                    &component,
                    &module_by_filename,
                    &module_names,
                    &member_set,
                )
            };
            if let Some(reason) = reason {
                warnings.push(UnpackWarning::new(
                    representative.clone(),
                    UnpackWarningKind::ImportCycle,
                    format!(
                        "local import cycle across {} modules not merged because {reason}: {preview}{suffix}",
                        component.len()
                    ),
                ));
                continue;
            }
        }

        let component_index = component_members.len();
        for filename in &component {
            file_to_component.insert(filename.clone(), component_index);
        }
        component_representatives.push(representative);
        component_members.push(component);
    }
    if component_members.is_empty() {
        return (modules, warnings);
    }

    let file_to_merged: HashMap<String, String> = file_to_component
        .iter()
        .map(|(filename, &component_index)| {
            (
                filename.clone(),
                component_representatives[component_index].clone(),
            )
        })
        .collect();
    let mut emitted_components = HashSet::new();
    let mut merged_modules = Vec::new();

    for module in &modules {
        if let Some(&component_index) = file_to_component.get(&module.filename) {
            if !emitted_components.insert(component_index) {
                continue;
            }
            let representative = &component_representatives[component_index];
            let members = &component_members[component_index];
            let member_set: HashSet<String> = members.iter().cloned().collect();
            let (code, is_entry) = {
                let span = tracing::info_span!(
                    "merge_cycles_emit_component",
                    representative = %representative,
                    count = members.len()
                );
                let _enter = span.enter();
                let (code, is_entry) = build_merged_cycle_code(
                    representative,
                    members,
                    &module_by_filename,
                    &module_names,
                    &file_to_merged,
                    &member_set,
                    true,
                );
                (code, is_entry)
            };
            // Provenance: a merged cycle covers the union of its members'
            // ranges, but only when all members came from the same input.
            let member_modules: Vec<_> = members
                .iter()
                .filter_map(|name| module_by_filename.get(name.as_str()))
                .collect();
            let inputs: HashSet<&str> = member_modules
                .iter()
                .map(|m| m.source_input.as_str())
                .collect();
            let (source_ranges, source_input) = if inputs.len() <= 1 {
                let mut ranges: Vec<(u32, u32)> = member_modules
                    .iter()
                    .flat_map(|m| m.source_ranges.iter().copied())
                    .collect();
                ranges.sort_unstable();
                (
                    ranges,
                    inputs.into_iter().next().unwrap_or_default().to_string(),
                )
            } else {
                (Vec::new(), String::new())
            };
            merged_modules.push(crate::unpacker::UnpackedModule {
                id: representative
                    .strip_suffix(".js")
                    .unwrap_or(representative)
                    .to_string(),
                is_entry,
                code,
                filename: representative.clone(),
                source_ranges,
                source_input,
                generated_source_map: Vec::new(),
            });
        } else {
            let code = if module_imports_retargeted_cycle_member(
                &module.filename,
                &graph,
                &file_to_merged,
            ) {
                rewrite_local_imports_for_merge(
                    &module.filename,
                    &module.filename,
                    &module.code,
                    &module_names,
                    &file_to_merged,
                    &HashSet::new(),
                )
            } else {
                module.code.clone()
            };
            merged_modules.push(crate::unpacker::UnpackedModule {
                id: module.id.clone(),
                is_entry: module.is_entry,
                code,
                filename: module.filename.clone(),
                source_ranges: module.source_ranges.clone(),
                source_input: module.source_input.clone(),
                generated_source_map: Vec::new(),
            });
        }
    }

    (merged_modules, warnings)
}

fn module_imports_retargeted_cycle_member(
    filename: &str,
    graph: &HashMap<String, Vec<String>>,
    file_to_merged: &HashMap<String, String>,
) -> bool {
    graph.get(filename).is_some_and(|dependencies| {
        dependencies.iter().any(|dependency| {
            file_to_merged
                .get(dependency)
                .is_some_and(|target| target != dependency)
        })
    })
}

fn should_use_fast_cycle_preflight(component: &[String], min_members: usize) -> bool {
    component.len() >= min_members
        && component
            .iter()
            .any(|filename| !filename.starts_with("module-"))
}

fn build_merged_cycle_code(
    representative: &str,
    members: &[String],
    module_by_filename: &HashMap<String, &crate::unpacker::UnpackedModule>,
    module_names: &HashSet<String>,
    file_to_merged: &HashMap<String, String>,
    member_set: &HashSet<String>,
    dedup_imports: bool,
) -> (String, bool) {
    let is_entry = members
        .iter()
        .any(|member| module_by_filename[member].is_entry);

    let code = GLOBALS
        .set(&Default::default(), || {
            let cm: Lrc<SourceMap> = Default::default();
            let mut imports = Vec::new();
            let mut body = Vec::new();

            for member in members {
                let member_module = module_by_filename[member];
                let mut module =
                    parse_js(&member_module.code, &member_module.filename, cm.clone())?;
                rewrite_local_imports_in_module(
                    &mut module,
                    &member_module.filename,
                    representative,
                    module_names,
                    file_to_merged,
                    member_set,
                );
                for item in module.body {
                    if matches!(item, ModuleItem::ModuleDecl(ModuleDecl::Import(_))) {
                        imports.push(item);
                    } else {
                        body.push(item);
                    }
                }
            }

            imports.extend(body);
            let mut module = Module {
                span: Default::default(),
                body: imports,
                shebang: None,
            };
            if dedup_imports {
                let unresolved_mark = Mark::new();
                let top_level_mark = Mark::new();
                module.visit_mut_with(&mut resolver(unresolved_mark, top_level_mark, false));
                module.visit_mut_with(&mut ImportDedup);
                dedup_duplicate_exports(&mut module);
                hoist_late_runtime_helpers(&mut module);
            }
            apply_fixer(&mut module)?;
            print_js(&module, cm)
        })
        .unwrap_or_else(|_| {
            let mut code = String::new();
            for member in members {
                let member_module = module_by_filename[member];
                let rewritten = rewrite_local_imports_for_merge(
                    &member_module.filename,
                    representative,
                    &member_module.code,
                    module_names,
                    file_to_merged,
                    member_set,
                );
                if !code.is_empty() {
                    code.push('\n');
                }
                code.push_str(&rewritten);
            }
            code
        });

    (code, is_entry)
}

fn dedup_merged_cycle_imports(filename: &str, code: &str) -> Option<String> {
    GLOBALS.set(&Default::default(), || {
        let cm: Lrc<SourceMap> = Default::default();
        let mut module = parse_js(code, filename, cm.clone()).ok()?;
        let unresolved_mark = Mark::new();
        let top_level_mark = Mark::new();
        module.visit_mut_with(&mut resolver(unresolved_mark, top_level_mark, false));
        module.visit_mut_with(&mut ImportDedup);
        dedup_duplicate_exports(&mut module);
        hoist_late_runtime_helpers(&mut module);
        apply_fixer(&mut module).ok()?;
        print_js(&module, cm).ok()
    })
}

fn unsafe_merged_cycle_candidate_reason(
    representative: &str,
    members: &[String],
    module_by_filename: &HashMap<String, &crate::unpacker::UnpackedModule>,
    module_names: &HashSet<String>,
    member_set: &HashSet<String>,
) -> Option<String> {
    let no_retargets = HashMap::new();
    let (candidate_code, _) = build_merged_cycle_code(
        representative,
        members,
        module_by_filename,
        module_names,
        &no_retargets,
        member_set,
        false,
    );
    let Some(candidate_code) = dedup_merged_cycle_imports(representative, &candidate_code) else {
        return Some("the merged module would not parse".to_string());
    };

    unsafe_merged_cycle_reason(representative, &candidate_code)
}

fn unsafe_merged_cycle_reason(filename: &str, code: &str) -> Option<String> {
    GLOBALS.set(&Default::default(), || {
        let cm: Lrc<SourceMap> = Default::default();
        let Ok(module) = parse_js(code, filename, cm) else {
            return Some("the merged module would not parse".to_string());
        };
        let duplicates = collect_duplicate_declaration_warnings(&module, filename);
        if duplicates.is_empty() {
            return None;
        }

        let preview = duplicates
            .iter()
            .take(5)
            .map(|warning| warning.message.clone())
            .collect::<Vec<_>>()
            .join(", ");
        let suffix = if duplicates.len() > 5 { ", ..." } else { "" };
        Some(format!(
            "the merged module would create duplicate declarations ({preview}{suffix})"
        ))
    })
}

#[derive(Clone)]
enum MergeBindingOrigin {
    Decl,
    Import(String),
}

pub(crate) fn unsafe_merge_member_reason(
    members: &[String],
    module_by_filename: &HashMap<String, &crate::unpacker::UnpackedModule>,
    module_names: &HashSet<String>,
    member_set: &HashSet<String>,
) -> Option<String> {
    GLOBALS.set(&Default::default(), || {
        let cm: Lrc<SourceMap> = Default::default();
        let mut seen = HashMap::new();
        let mut duplicates = Vec::new();

        for member in members {
            let member_module = module_by_filename[member];
            let Ok(module) = parse_js(&member_module.code, &member_module.filename, cm.clone())
            else {
                return Some("the merged module would not parse".to_string());
            };

            for item in &module.body {
                if let ModuleItem::ModuleDecl(ModuleDecl::Import(import)) = item {
                    let Some(specifier) = import.src.value.as_str() else {
                        continue;
                    };
                    if resolve_local_module_specifier(&member_module.filename, specifier)
                        .filter(|resolved| {
                            module_names.contains(resolved) && member_set.contains(resolved)
                        })
                        .is_some()
                    {
                        continue;
                    }

                    for (name, key) in import_binding_keys(import) {
                        record_merge_binding(
                            &mut seen,
                            &mut duplicates,
                            name,
                            MergeBindingOrigin::Import(key),
                        );
                    }
                    continue;
                }

                for name in unsafe_merge_declared_names(item) {
                    record_merge_binding(
                        &mut seen,
                        &mut duplicates,
                        name,
                        MergeBindingOrigin::Decl,
                    );
                }
            }
        }

        if duplicates.is_empty() {
            return None;
        }

        let preview = duplicates
            .iter()
            .take(5)
            .map(|name| format!("duplicate lexical declaration `{name}`"))
            .collect::<Vec<_>>()
            .join(", ");
        let suffix = if duplicates.len() > 5 { ", ..." } else { "" };
        Some(format!(
            "the merged module would create duplicate declarations ({preview}{suffix})"
        ))
    })
}

fn unsafe_merge_declared_names(item: &ModuleItem) -> Vec<String> {
    let is_var_decl = match item {
        ModuleItem::Stmt(Stmt::Decl(Decl::Var(var))) => {
            var.kind == swc_core::ecma::ast::VarDeclKind::Var
        }
        ModuleItem::ModuleDecl(ModuleDecl::ExportDecl(export)) => match &export.decl {
            Decl::Var(var) => var.kind == swc_core::ecma::ast::VarDeclKind::Var,
            _ => false,
        },
        _ => false,
    };
    if is_var_decl {
        return Vec::new();
    }

    module_item_declared_binding_ids(item)
        .into_iter()
        .map(|(sym, _)| sym.to_string())
        .collect()
}

fn record_merge_binding(
    seen: &mut HashMap<String, MergeBindingOrigin>,
    duplicates: &mut Vec<String>,
    name: String,
    origin: MergeBindingOrigin,
) {
    if let Some(existing) = seen.get(&name) {
        if let (MergeBindingOrigin::Import(existing), MergeBindingOrigin::Import(next)) =
            (existing, &origin)
        {
            if existing == next {
                return;
            }
        }
        if !duplicates.contains(&name) {
            duplicates.push(name);
        }
        return;
    }

    seen.insert(name, origin);
}

fn import_binding_keys(import: &ImportDecl) -> Vec<(String, String)> {
    let source = import.src.value.as_str().unwrap_or("").to_string();
    import
        .specifiers
        .iter()
        .map(|specifier| match specifier {
            ImportSpecifier::Named(named) => {
                let imported = named
                    .imported
                    .as_ref()
                    .map(module_export_name_string)
                    .unwrap_or_else(|| named.local.sym.to_string());
                (
                    named.local.sym.to_string(),
                    format!("{source}:named:{imported}:{}", named.local.sym),
                )
            }
            ImportSpecifier::Default(default) => (
                default.local.sym.to_string(),
                format!("{source}:default:{}", default.local.sym),
            ),
            ImportSpecifier::Namespace(namespace) => (
                namespace.local.sym.to_string(),
                format!("{source}:namespace:{}", namespace.local.sym),
            ),
        })
        .collect()
}

fn rewrite_local_imports_for_merge(
    source_filename: &str,
    output_filename: &str,
    code: &str,
    module_names: &HashSet<String>,
    file_to_merged: &HashMap<String, String>,
    drop_imports_from: &HashSet<String>,
) -> String {
    GLOBALS.set(&Default::default(), || {
        let cm: Lrc<SourceMap> = Default::default();
        let Ok(mut module) = parse_js(code, source_filename, cm.clone()) else {
            return code.to_string();
        };

        rewrite_local_imports_in_module(
            &mut module,
            source_filename,
            output_filename,
            module_names,
            file_to_merged,
            drop_imports_from,
        );

        print_js(&module, cm).unwrap_or_else(|_| code.to_string())
    })
}

fn rewrite_local_imports_in_module(
    module: &mut Module,
    source_filename: &str,
    output_filename: &str,
    module_names: &HashSet<String>,
    file_to_merged: &HashMap<String, String>,
    drop_imports_from: &HashSet<String>,
) {
    module.body.retain_mut(|item| {
        let ModuleItem::ModuleDecl(ModuleDecl::Import(import)) = item else {
            return true;
        };
        let Some(specifier) = import.src.value.as_str() else {
            return true;
        };
        let Some(resolved) = resolve_local_module_specifier(source_filename, specifier) else {
            return true;
        };
        if !module_names.contains(&resolved) {
            return true;
        }
        if drop_imports_from.contains(&resolved) {
            return false;
        }

        let target = file_to_merged.get(&resolved).cloned().unwrap_or(resolved);
        let rewritten = relative_import_specifier(output_filename, &target);
        *import.src = Str {
            span: Default::default(),
            value: rewritten.into(),
            raw: None,
        };
        true
    });
}

pub(crate) fn collect_import_cycle_warnings(modules: &[(String, String)]) -> Vec<UnpackWarning> {
    let module_names: HashSet<String> = modules
        .iter()
        .map(|(filename, _)| filename.clone())
        .collect();
    let mut graph: HashMap<String, Vec<String>> = HashMap::new();
    for (filename, code) in modules {
        let deps = local_import_dependencies(filename, code, &module_names);
        graph.insert(filename.clone(), deps);
    }

    tarjan_sccs(&graph)
        .into_iter()
        .filter(|component| {
            component.len() > 1
                || component
                    .first()
                    .is_some_and(|filename| graph[filename].contains(filename))
        })
        .map(|mut component| {
            component.sort();
            let filename = component[0].clone();
            let preview = component
                .iter()
                .take(8)
                .cloned()
                .collect::<Vec<_>>()
                .join(" -> ");
            let suffix = if component.len() > 8 { " -> ..." } else { "" };
            UnpackWarning::new(
                filename,
                UnpackWarningKind::ImportCycle,
                format!(
                    "local import cycle across {} modules: {preview}{suffix}",
                    component.len()
                ),
            )
        })
        .collect()
}

fn local_import_dependencies(
    filename: &str,
    code: &str,
    module_names: &HashSet<String>,
) -> Vec<String> {
    if !filename.starts_with("module-") {
        if let Some(deps) = scan_local_import_dependencies(filename, code, module_names) {
            return deps;
        }
    }

    GLOBALS.set(&Default::default(), || {
        let cm: Lrc<SourceMap> = Default::default();
        let Ok(module) = parse_js(code, filename, cm) else {
            return vec![];
        };
        let mut deps: Vec<String> = module
            .body
            .iter()
            .filter_map(|item| {
                let ModuleItem::ModuleDecl(ModuleDecl::Import(import)) = item else {
                    return None;
                };
                import
                    .src
                    .value
                    .as_str()
                    .and_then(|specifier| resolve_local_module_specifier(filename, specifier))
            })
            .filter(|dep| module_names.contains(dep))
            .collect();
        deps.sort();
        deps.dedup();
        deps
    })
}

pub(crate) fn scan_local_import_dependencies(
    filename: &str,
    code: &str,
    module_names: &HashSet<String>,
) -> Option<Vec<String>> {
    let mut deps = Vec::new();
    let mut statement = String::new();
    let mut in_import = false;

    for line in code.lines() {
        let trimmed = line.trim_start();
        if !in_import {
            if trimmed.is_empty() || trimmed.starts_with("//") {
                continue;
            }
            if line != trimmed || !is_static_import_start(trimmed) {
                continue;
            }
            statement.clear();
            statement.push_str(trimmed);
            in_import = !trimmed.contains(';');
        } else {
            statement.push(' ');
            statement.push_str(trimmed);
            in_import = !trimmed.contains(';');
        }

        if !in_import {
            let specifier = extract_static_import_specifier(&statement)?;
            if let Some(dep) = resolve_local_module_specifier(filename, specifier)
                .filter(|d| module_names.contains(d))
            {
                deps.push(dep);
            }
        }
    }

    if in_import {
        return None;
    }

    deps.sort();
    deps.dedup();
    Some(deps)
}

fn is_static_import_start(line: &str) -> bool {
    line == "import" || line.starts_with("import ") || line.starts_with("import{")
}

fn extract_static_import_specifier(statement: &str) -> Option<&str> {
    let import_tail = statement.strip_prefix("import")?.trim_start();
    let specifier_start = if import_tail.starts_with('"') || import_tail.starts_with('\'') {
        import_tail
    } else {
        let from_index = statement.rfind(" from ")?;
        statement[from_index + " from ".len()..].trim_start()
    };
    let mut chars = specifier_start.char_indices();
    let (_, quote) = chars.next()?;
    if quote != '"' && quote != '\'' {
        return None;
    }
    let start = quote.len_utf8();
    for (index, ch) in chars {
        if ch == quote {
            return Some(&specifier_start[start..index]);
        }
    }
    None
}

fn resolve_local_module_specifier(filename: &str, specifier: &str) -> Option<String> {
    if !specifier.starts_with("./") && !specifier.starts_with("../") {
        return None;
    }

    let mut parts: Vec<&str> = filename.split('/').collect();
    parts.pop();
    for part in specifier.split('/') {
        match part {
            "." | "" => {}
            ".." => {
                parts.pop()?;
            }
            other => parts.push(other),
        }
    }
    Some(parts.join("/"))
}

fn relative_import_specifier(from_filename: &str, to_filename: &str) -> String {
    let from_dir: Vec<&str> = from_filename
        .rsplit_once('/')
        .map(|(dir, _)| dir.split('/').collect())
        .unwrap_or_default();
    let to_parts: Vec<&str> = to_filename.split('/').collect();
    let to_file = *to_parts.last().unwrap_or(&to_filename);
    let to_dir = &to_parts[..to_parts.len().saturating_sub(1)];

    let mut common = 0;
    while common < from_dir.len() && common < to_dir.len() && from_dir[common] == to_dir[common] {
        common += 1;
    }

    let mut parts = Vec::new();
    for _ in common..from_dir.len() {
        parts.push("..".to_string());
    }
    for part in &to_dir[common..] {
        parts.push((*part).to_string());
    }
    parts.push(to_file.to_string());

    let specifier = parts.join("/");
    if specifier.starts_with('.') {
        specifier
    } else {
        format!("./{specifier}")
    }
}

fn tarjan_sccs(graph: &HashMap<String, Vec<String>>) -> Vec<Vec<String>> {
    struct Tarjan<'a> {
        graph: &'a HashMap<String, Vec<String>>,
        index: usize,
        stack: Vec<String>,
        on_stack: HashSet<String>,
        indices: HashMap<String, usize>,
        lowlinks: HashMap<String, usize>,
        components: Vec<Vec<String>>,
    }

    impl Tarjan<'_> {
        fn strong_connect(&mut self, node: String) {
            self.indices.insert(node.clone(), self.index);
            self.lowlinks.insert(node.clone(), self.index);
            self.index += 1;
            self.stack.push(node.clone());
            self.on_stack.insert(node.clone());

            for dep in self.graph.get(&node).into_iter().flatten() {
                if !self.indices.contains_key(dep) {
                    self.strong_connect(dep.clone());
                    let low = self.lowlinks[&node].min(self.lowlinks[dep]);
                    self.lowlinks.insert(node.clone(), low);
                } else if self.on_stack.contains(dep) {
                    let low = self.lowlinks[&node].min(self.indices[dep]);
                    self.lowlinks.insert(node.clone(), low);
                }
            }

            if self.lowlinks[&node] == self.indices[&node] {
                let mut component = Vec::new();
                while let Some(member) = self.stack.pop() {
                    self.on_stack.remove(&member);
                    let done = member == node;
                    component.push(member);
                    if done {
                        break;
                    }
                }
                self.components.push(component);
            }
        }
    }

    let mut tarjan = Tarjan {
        graph,
        index: 0,
        stack: Vec::new(),
        on_stack: HashSet::new(),
        indices: HashMap::new(),
        lowlinks: HashMap::new(),
        components: Vec::new(),
    };
    let mut nodes: Vec<String> = graph.keys().cloned().collect();
    nodes.sort();
    for node in nodes {
        if !tarjan.indices.contains_key(&node) {
            tarjan.strong_connect(node);
        }
    }
    tarjan.components
}