Function toposort_classes

src/toposort.rs:111–196

Topologically sort class-like declarations by their dependencies. # Arguments `classes` — iterator of `(FQN, &ClassInfo)` pairs covering every known class-like declaration (from `uri_classes_index`, stubs, etc.). # Returns A `Vec ` of FQNs in dependency order: every class appears after all of its dependencies. Classes involved in cycles appear in an unspecified but safe order (the cycl

(
    classes: impl Iterator<Item = (String, &'a ClassInfo)>,
)

/// `populator::sorter::sort_class_likes`, but uses O(1) stack space
/// per class regardless of hierarchy depth.
pub(crate) fn toposort_classes<'a>(
    classes: impl Iterator<Item = (String, &'a ClassInfo)>,
) -> Vec<String> {
    // Build a map from FQN → dependency list.
    let mut dep_map: HashMap<String, Vec<String>> = HashMap::new();
    let mut all_fqns: Vec<String> = Vec::new();

    for (fqn, class) in classes {
        let deps = class_dependencies(class);
        all_fqns.push(fqn.clone());
        dep_map.insert(fqn, deps);
    }

    // Sort the starting FQNs so that the DFS visitation order is
    // deterministic regardless of HashMap iteration order in the
    // caller (e.g. `toposort_from_uri_classes_index` iterates a HashMap whose
    // order varies between runs due to random hashing seeds).
    // Without this, classes at the same topological level can be
    // processed in different orders across runs, which causes the
    // recursion guard in `resolve_class_fully_inner` to break
    // implicit cycles differently — leading to non-deterministic
    // cache contents and flaky diagnostics (see B28).
    all_fqns.sort();

    let mut visited: HashSet<String> = HashSet::with_capacity(all_fqns.len());
    let mut visiting: HashSet<String> = HashSet::new();
    let mut sorted: Vec<String> = Vec::with_capacity(all_fqns.len());

    for start_fqn in &all_fqns {
        if visited.contains(start_fqn) {
            continue;
        }

        // Iterative DFS starting from `start_fqn`.
        let start_deps = dep_map.get(start_fqn).cloned().unwrap_or_default();

        visiting.insert(start_fqn.clone());

        let mut stack = vec![DfsFrame {
            fqn: start_fqn.clone(),
            dep_index: 0,
            deps: start_deps,
        }];

        while let Some(frame) = stack.last_mut() {
            if frame.dep_index < frame.deps.len() {
                let dep = frame.deps[frame.dep_index].clone();
                frame.dep_index += 1;

                // Skip dependencies not in our input set (external/unloaded classes).
                if !dep_map.contains_key(&dep) {
                    continue;
                }

                // Already fully processed — nothing to do.
                if visited.contains(&dep) {
                    continue;
                }