orphanode 0.1.0

Accuracy-first reachability analysis for JavaScript and TypeScript projects, as a library and a CLI
Documentation
use std::collections::VecDeque;

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

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FileGraph {
    outgoing: Vec<Vec<FileId>>,
}

impl FileGraph {
    #[must_use]
    pub fn new(file_count: usize) -> Self {
        Self {
            outgoing: vec![Vec::new(); file_count],
        }
    }

    pub fn add_edge(&mut self, from: FileId, to: FileId) {
        self.outgoing[from.0].push(to);
    }

    pub fn finish(&mut self) {
        for targets in &mut self.outgoing {
            targets.sort_unstable();
            targets.dedup();
        }
    }

    #[must_use]
    pub fn reachable_from(&self, root: FileId) -> Vec<bool> {
        self.reachable_from_many(&[root])
    }

    #[must_use]
    pub fn reachable_from_many(&self, roots: &[FileId]) -> Vec<bool> {
        let mut reachable = vec![false; self.outgoing.len()];
        let mut queue = VecDeque::new();
        for root in roots {
            if !reachable[root.0] {
                reachable[root.0] = true;
                queue.push_back(*root);
            }
        }

        while let Some(file) = queue.pop_front() {
            for target in &self.outgoing[file.0] {
                if !reachable[target.0] {
                    reachable[target.0] = true;
                    queue.push_back(*target);
                }
            }
        }

        reachable
    }

    #[must_use]
    pub fn components_within(&self, included: &[bool]) -> Vec<Vec<FileId>> {
        debug_assert_eq!(self.outgoing.len(), included.len());

        let finishing_order = self.finishing_order(included);
        let reversed = self.reversed();
        let mut assigned = vec![false; self.outgoing.len()];
        let mut components = Vec::new();

        for start in finishing_order.into_iter().rev() {
            if assigned[start.0] || !included[start.0] {
                continue;
            }

            let mut component = Vec::new();
            let mut stack = vec![start];
            assigned[start.0] = true;

            while let Some(file) = stack.pop() {
                component.push(file);
                for source in &reversed[file.0] {
                    if included[source.0] && !assigned[source.0] {
                        assigned[source.0] = true;
                        stack.push(*source);
                    }
                }
            }

            component.sort_unstable();
            components.push(component);
        }

        components.sort_by_key(|component| component[0]);
        components
    }

    fn finishing_order(&self, included: &[bool]) -> Vec<FileId> {
        let mut visited = vec![false; self.outgoing.len()];
        let mut order = Vec::new();

        for start_index in 0..self.outgoing.len() {
            if !included[start_index] || visited[start_index] {
                continue;
            }

            let start = FileId(start_index);
            visited[start_index] = true;
            let mut stack = vec![(start, 0_usize)];

            while let Some((file, next_edge)) = stack.last_mut() {
                let targets = &self.outgoing[file.0];
                if *next_edge < targets.len() {
                    let target = targets[*next_edge];
                    *next_edge += 1;
                    if included[target.0] && !visited[target.0] {
                        visited[target.0] = true;
                        stack.push((target, 0));
                    }
                } else {
                    order.push(*file);
                    stack.pop();
                }
            }
        }

        order
    }

    fn reversed(&self) -> Vec<Vec<FileId>> {
        let mut reversed = vec![Vec::new(); self.outgoing.len()];
        for (source, targets) in self.outgoing.iter().enumerate() {
            for target in targets {
                reversed[target.0].push(FileId(source));
            }
        }
        for sources in &mut reversed {
            sources.sort_unstable();
        }
        reversed
    }
}

#[cfg(test)]
mod tests {
    use super::{FileGraph, FileId};

    struct DeterministicRandom(u64);

    impl DeterministicRandom {
        fn next(&mut self) -> u64 {
            self.0 = self
                .0
                .wrapping_mul(6_364_136_223_846_793_005)
                .wrapping_add(1_442_695_040_888_963_407);
            self.0
        }
    }

    #[test]
    fn reachability_does_not_activate_a_disconnected_cycle() {
        let mut graph = FileGraph::new(4);
        graph.add_edge(FileId(0), FileId(1));
        graph.add_edge(FileId(2), FileId(3));
        graph.add_edge(FileId(3), FileId(2));
        graph.finish();

        assert_eq!(
            graph.reachable_from(FileId(0)),
            vec![true, true, false, false]
        );
    }

    #[test]
    fn components_are_stable_and_group_cycles() {
        let mut graph = FileGraph::new(5);
        graph.add_edge(FileId(0), FileId(1));
        graph.add_edge(FileId(1), FileId(0));
        graph.add_edge(FileId(3), FileId(4));
        graph.finish();

        let components = graph.components_within(&[true, true, true, true, true]);

        assert_eq!(
            components,
            vec![
                vec![FileId(0), FileId(1)],
                vec![FileId(2)],
                vec![FileId(3)],
                vec![FileId(4)],
            ]
        );
    }

    #[test]
    fn reachability_accepts_multiple_roots() {
        let mut graph = FileGraph::new(5);
        graph.add_edge(FileId(0), FileId(1));
        graph.add_edge(FileId(3), FileId(4));
        graph.finish();

        assert_eq!(
            graph.reachable_from_many(&[FileId(3), FileId(0)]),
            vec![true, true, false, true, true]
        );
    }

    #[test]
    fn generated_graphs_match_reference_reachability_and_components() {
        for seed in 0_u64..64 {
            for file_count in 1..=12 {
                let mut random = DeterministicRandom(seed ^ file_count as u64);
                let mut graph = FileGraph::new(file_count);
                let mut adjacency = vec![Vec::new(); file_count];
                for (source, targets) in adjacency.iter_mut().enumerate() {
                    for target in 0..file_count {
                        if random.next().is_multiple_of(4) {
                            graph.add_edge(FileId(source), FileId(target));
                            targets.push(target);
                        }
                    }
                }
                graph.finish();

                let roots = (0..file_count)
                    .filter(|_| random.next().is_multiple_of(3))
                    .map(FileId)
                    .collect::<Vec<_>>();
                assert_eq!(
                    graph.reachable_from_many(&roots),
                    reference_reachable(&adjacency, &roots, &vec![true; file_count]),
                    "reachability mismatch for seed {seed} with {file_count} files"
                );

                let included = (0..file_count)
                    .map(|_| !random.next().is_multiple_of(4))
                    .collect::<Vec<_>>();
                assert_eq!(
                    graph.components_within(&included),
                    reference_components(&adjacency, &included),
                    "component mismatch for seed {seed} with {file_count} files"
                );
            }
        }
    }

    fn reference_reachable(
        adjacency: &[Vec<usize>],
        roots: &[FileId],
        included: &[bool],
    ) -> Vec<bool> {
        let mut reachable = vec![false; adjacency.len()];
        for root in roots {
            if included[root.0] {
                reachable[root.0] = true;
            }
        }
        loop {
            let mut changed = false;
            for (source, targets) in adjacency.iter().enumerate() {
                if !reachable[source] {
                    continue;
                }
                for &target in targets {
                    if included[target] && !reachable[target] {
                        reachable[target] = true;
                        changed = true;
                    }
                }
            }
            if !changed {
                return reachable;
            }
        }
    }

    fn reference_components(adjacency: &[Vec<usize>], included: &[bool]) -> Vec<Vec<FileId>> {
        let mut assigned = vec![false; adjacency.len()];
        let mut components = Vec::new();
        for (source, &source_included) in included.iter().enumerate() {
            if !source_included || assigned[source] {
                continue;
            }
            let forward = reference_reachable(adjacency, &[FileId(source)], included);
            let mut component = Vec::new();
            for (target, &target_included) in included.iter().enumerate() {
                if !target_included || !forward[target] {
                    continue;
                }
                let backward = reference_reachable(adjacency, &[FileId(target)], included);
                if backward[source] {
                    assigned[target] = true;
                    component.push(FileId(target));
                }
            }
            components.push(component);
        }
        components.sort_by_key(|component| component[0]);
        components
    }
}