fluidattacks-blends-domain 0.44.1

use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;

use crate::stack::resolve::{PartialPath, PartialPathDatabase, PartialSymbolStack, PathEdge};
use crate::stack::{Definition, StackNode, SymbolPop};
use crate::NodeId;

/// A walk the stitcher built, and the file of the node it ends at.
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct StitchedPath<'a> {
    /// The file of the node the walk ends at.
    pub file: &'a str,
    /// The walk.
    pub path: PartialPath<'a>,
    edge_files: Vec<&'a str>,
}

/// The stored paths a stitcher tries from one reference when no other limit is given.
pub const DEFAULT_MAX_STITCH_WORK: usize = 1_000;

type State<'a> = (NodeId, &'a str, NodeId, PartialSymbolStack<'a>);

/// Extends walks from the references of one file, phase by phase, with the stored partial paths.
#[derive(Debug)]
pub struct ForwardStitcher<'d, 'a> {
    database: &'d PartialPathDatabase<'a>,
    file: &'a str,
    queue: Vec<StitchedPath<'a>>,
    seen: BTreeSet<State<'a>>,
    max_work: usize,
    work: BTreeMap<NodeId, usize>,
    exhausted: BTreeSet<NodeId>,
}

impl<'d, 'a> ForwardStitcher<'d, 'a> {
    /// A stitcher from the `references` of `file`, trying at most `max_work` stored paths from each.
    pub fn from_references(
        database: &'d PartialPathDatabase<'a>,
        file: &'a str,
        references: impl IntoIterator<Item = NodeId>,
        max_work: usize,
    ) -> Self {
        let mut seen = BTreeSet::new();
        let queue = database.graph(file).map_or_else(Vec::new, |graph| {
            references
                .into_iter()
                .filter(|node| graph.nodes.get(node).is_some_and(StackNode::is_reference))
                .flat_map(|node| PartialPath::seed(graph, node))
                .map(|path| StitchedPath {
                    file,
                    path,
                    edge_files: Vec::new(),
                })
                .filter(|seed| seen.insert(state(seed)))
                .collect()
        });
        Self {
            database,
            file,
            queue,
            seen,
            max_work,
            work: BTreeMap::new(),
            exhausted: BTreeSet::new(),
        }
    }

    /// Extends every pending walk by one stored path and returns those that now reach a definition.
    pub fn process_next_phase(&mut self) -> Vec<StitchedPath<'a>> {
        let pending = core::mem::take(&mut self.queue);
        let extensions: Vec<_> = pending.iter().flat_map(|walk| self.extend(walk)).collect();
        let mut complete = Vec::new();
        for walk in extensions {
            if !self.seen.insert(state(&walk)) {
                continue;
            }
            let graph = self.database.graph(walk.file);
            let end = graph.and_then(|graph| graph.nodes.get(&walk.path.end));
            if walk.file != self.file && end.is_some_and(is_private) {
                continue;
            }
            let answers =
                walk.path.post.symbols.is_empty() && end.is_some_and(StackNode::is_definition);
            if answers {
                complete.push(walk.clone());
            }
            if !answers || end.is_some_and(|node| node.import_binding().is_some()) {
                self.queue.push(walk);
            }
        }
        complete
    }

    /// Whether no walk is left to extend.
    #[must_use]
    pub fn is_complete(&self) -> bool {
        self.queue.is_empty()
    }

    /// The references that stopped with stored paths left to try, in id order.
    pub fn exhausted(&self) -> impl Iterator<Item = NodeId> + '_ {
        self.exhausted.iter().copied()
    }

    /// The stored paths tried so far, over every reference.
    #[must_use]
    pub fn work(&self) -> usize {
        self.work.values().sum()
    }

    fn extend(&mut self, walk: &StitchedPath<'a>) -> Vec<StitchedPath<'a>> {
        let Some(graph) = self.database.graph(walk.file) else {
            return Vec::new();
        };
        let candidates: Vec<_> = if matches!(graph.nodes.get(&walk.path.end), Some(StackNode::Root))
        {
            let below_reference = walk.path.post.variable == walk.path.pre.variable;
            let left = PartialSymbolStack {
                symbols: walk.path.post.symbols.clone(),
                variable: walk.path.post.variable.filter(|_| !below_reference),
            };
            let roots = self.database.starting_at_root(&left);
            roots
                .into_iter()
                .map(|(id, path)| (id.file, path))
                .collect()
        } else {
            let here = self.database.starting_at(walk.file, walk.path.end);
            here.map(|(_, path)| (walk.file, path)).collect()
        };
        let mut extended = Vec::new();
        let spent = self.work.entry(walk.path.start).or_default();
        for (file, candidate) in candidates {
            if *spent >= self.max_work {
                self.exhausted.insert(walk.path.start);
                break;
            }
            *spent = spent.saturating_add(1);
            let at_this_end = PartialPath {
                start: walk.path.end,
                ..candidate.clone()
            };
            match walk.path.concatenate(graph, &at_this_end) {
                Ok(path) if path.pre.symbols.is_empty() => {
                    let edge_files = walk
                        .edge_files
                        .iter()
                        .copied()
                        .chain(core::iter::repeat_n(file, candidate.edges.len()))
                        .collect();
                    extended.push(StitchedPath {
                        file,
                        path,
                        edge_files,
                    });
                }
                _ => {}
            }
        }
        extended
    }
}

/// The answers of each reference that no other answer shadows or walks past, one per definition.
#[must_use]
pub fn select_definitions<'a>(answers: &[StitchedPath<'a>]) -> Vec<StitchedPath<'a>> {
    let mut sorted: Vec<&StitchedPath<'a>> = answers.iter().collect();
    sorted.sort_by_key(|answer| location(answer));
    let mut selected: Vec<StitchedPath<'a>> = sorted
        .chunk_by(|left, right| left.path.start == right.path.start)
        .flat_map(|same| {
            same.iter().filter(|answer| {
                !same
                    .iter()
                    .any(|other| shadows(other, answer) || walks_past(other, answer))
            })
        })
        .map(|answer| (*answer).clone())
        .collect();
    selected.dedup_by_key(|answer| location(answer));
    selected
}

/// What the references of one file resolve to.
#[derive(Clone, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub struct Resolution<'a> {
    /// The selected answers, ordered by reference and then by the file and node of the definition.
    pub definitions: Vec<StitchedPath<'a>>,
    /// The references that ran out of work, in id order.
    pub exhausted: Vec<NodeId>,
    /// The stored paths tried over every reference.
    pub work: usize,
}

/// Resolves every reference of `file` against `database`, trying at most `max_work` stored paths from each.
#[must_use]
pub fn resolve_file<'a>(
    database: &PartialPathDatabase<'a>,
    file: &'a str,
    max_work: usize,
) -> Resolution<'a> {
    let references = database
        .graph(file)
        .into_iter()
        .flat_map(|graph| graph.nodes.keys().copied());
    resolve_references(database, file, references, max_work)
}

/// Resolves the `references` of `file` against `database`, trying at most `max_work` stored paths from each.
#[must_use]
pub fn resolve_references<'a>(
    database: &PartialPathDatabase<'a>,
    file: &'a str,
    references: impl IntoIterator<Item = NodeId>,
    max_work: usize,
) -> Resolution<'a> {
    let mut stitcher = ForwardStitcher::from_references(database, file, references, max_work);
    let mut answers = Vec::new();
    while !stitcher.is_complete() {
        answers.extend(stitcher.process_next_phase());
    }
    Resolution {
        definitions: select_definitions(&answers),
        exhausted: stitcher.exhausted().collect(),
        work: stitcher.work(),
    }
}

fn location<'a>(answer: &StitchedPath<'a>) -> (NodeId, &'a str, NodeId) {
    (answer.path.start, answer.file, answer.path.end)
}

fn shadows(winner: &StitchedPath<'_>, loser: &StitchedPath<'_>) -> bool {
    edges_by_file(winner)
        .zip(edges_by_file(loser))
        .find(|(left, right)| left != right)
        .is_some_and(|((winner_file, winner_edge), (loser_file, loser_edge))| {
            winner_file == loser_file
                && winner_edge.source == loser_edge.source
                && winner_edge.precedence > loser_edge.precedence
        })
}

fn walks_past(walk: &StitchedPath<'_>, answer: &StitchedPath<'_>) -> bool {
    walk.path.edges.len() > answer.path.edges.len()
        && edges_by_file(walk)
            .zip(edges_by_file(answer))
            .all(|(left, right)| left == right)
}

fn edges_by_file<'p, 'a>(
    walk: &'p StitchedPath<'a>,
) -> impl Iterator<Item = (&'a str, PathEdge)> + 'p {
    walk.edge_files
        .iter()
        .copied()
        .zip(walk.path.edges.iter().copied())
}

fn is_private(node: &StackNode) -> bool {
    matches!(
        node,
        StackNode::PopSymbol(SymbolPop {
            definition: Some(Definition {
                is_private: true,
                ..
            }),
            ..
        })
    )
}

fn state<'a>(walk: &StitchedPath<'a>) -> State<'a> {
    (
        walk.path.start,
        walk.file,
        walk.path.end,
        walk.path.post.clone(),
    )
}

#[cfg(test)]
mod tests {
    use super::{
        resolve_file, resolve_references, select_definitions, ForwardStitcher,
        DEFAULT_MAX_STITCH_WORK,
    };
    use crate::stack::resolve::{PartialPathDatabase, DEFAULT_MAX_WORK};
    use crate::stack::{
        Definition, ImportBinding, StackGraph, StackNode, StackScope, SymbolPop, SymbolPush,
    };
    use crate::NodeId;
    use alloc::borrow::ToOwned;
    use alloc::vec::Vec;

    const ROOT: NodeId = NodeId(1);
    const REFERENCE: NodeId = NodeId(2);
    const SCOPE: NodeId = NodeId(3);
    const DEFINITION: NodeId = NodeId(4);
    const RELAY: NodeId = NodeId(5);
    const MODULE: NodeId = NodeId(6);
    const MODULE_DEFINITION: NodeId = NodeId(7);
    const IMPORT: NodeId = NodeId(8);
    const ORIGIN: NodeId = NodeId(9);
    const MODULE_REFERENCE: NodeId = NodeId(10);
    const LOCAL_REFERENCE: NodeId = NodeId(11);
    const INNER: NodeId = NodeId(12);
    const OUTER_SCOPE: NodeId = NodeId(13);
    const OUTER_DEFINITION: NodeId = NodeId(14);
    const PRIVATE_IMPORT: NodeId = NodeId(15);
    const LIBRARY_RELAY: NodeId = NodeId(16);
    const LIBRARY_MODULE: NodeId = NodeId(17);
    const ALL_PHASES: usize = 16;
    const LIBRARY: (&str, &[(NodeId, NodeId)]) = ("m.py", &[(ROOT, MODULE), (MODULE, DEFINITION)]);

    type Edges = &'static [(NodeId, NodeId)];

    fn push(symbol: &str, is_reference: bool) -> StackNode {
        StackNode::PushSymbol(SymbolPush {
            symbol: symbol.to_owned(),
            precedence: 0,
            is_reference,
        })
    }

    fn pop(symbol: &str, definition: bool, import: bool) -> StackNode {
        StackNode::PopSymbol(SymbolPop {
            symbol: symbol.to_owned(),
            precedence: 0,
            definition: definition.then(Definition::default),
            import: import.then(|| ImportBinding {
                module_stem: "m".to_owned(),
                source_symbol: None,
                relative_level: 0,
                binds_module: false,
            }),
        })
    }

    fn node(id: NodeId) -> StackNode {
        match id {
            ROOT => StackNode::Root,
            REFERENCE | LOCAL_REFERENCE => push("x", true),
            MODULE_REFERENCE => push("m", true),
            ORIGIN => push("x", false),
            RELAY => push("m", false),
            DEFINITION | OUTER_DEFINITION => pop("x", true, false),
            PRIVATE_IMPORT => private(pop("x", true, true)),
            LIBRARY_RELAY => push("lib", false),
            LIBRARY_MODULE => pop("lib", false, false),
            IMPORT => pop("x", true, true),
            MODULE => pop("m", false, false),
            MODULE_DEFINITION => pop("m", true, false),
            INNER => pop("x", false, false),
            _ => StackNode::Scope(StackScope::default()),
        }
    }

    fn private(mut node: StackNode) -> StackNode {
        if let StackNode::PopSymbol(SymbolPop {
            definition: Some(definition),
            ..
        }) = &mut node
        {
            definition.is_private = true;
        }
        node
    }

    fn graph(edges: Edges) -> StackGraph {
        let mut graph = StackGraph::new();
        for (source, sink) in edges {
            graph.add_node(*source, node(*source));
            graph.add_node(*sink, node(*sink));
            graph.add_edge(*source, *sink, i64::from(node(*sink).is_definition()));
        }
        graph
    }

    fn select(files: &[(&'static str, Edges)], copies: usize) -> Vec<(&'static str, NodeId)> {
        let graphs: Vec<StackGraph> = files.iter().map(|(_, edges)| graph(edges)).collect();
        let mut database = PartialPathDatabase::default();
        for ((file, _), graph) in files.iter().zip(&graphs) {
            database.add_file(file, graph, DEFAULT_MAX_WORK);
        }
        let mut stitcher = ForwardStitcher::from_references(
            &database,
            "a.py",
            [REFERENCE],
            DEFAULT_MAX_STITCH_WORK,
        );
        let answers: Vec<_> = (0..ALL_PHASES)
            .flat_map(|_| stitcher.process_next_phase())
            .collect();
        let repeated: Vec<_> = (0..copies).flat_map(|_| answers.iter().cloned()).collect();
        select_definitions(&repeated)
            .into_iter()
            .filter_map(|walk| {
                Some((
                    files.iter().find(|(file, _)| *file == walk.file)?.0,
                    walk.path.end,
                ))
            })
            .collect()
    }

    fn resolve(files: &[(&'static str, Edges)], max_work: usize) -> Run {
        let graphs: Vec<StackGraph> = files.iter().map(|(_, edges)| graph(edges)).collect();
        let mut database = PartialPathDatabase::default();
        for ((file, _), graph) in files.iter().zip(&graphs) {
            database.add_file(file, graph, DEFAULT_MAX_WORK);
        }
        let resolution = resolve_file(&database, "a.py", max_work);
        Run {
            answers: resolution
                .definitions
                .iter()
                .filter_map(|walk| {
                    Some((
                        files.iter().find(|(file, _)| *file == walk.file)?.0,
                        walk.path.end,
                    ))
                })
                .collect(),
            complete: true,
            exhausted: resolution.exhausted,
            work: resolution.work,
        }
    }

    #[derive(PartialEq, Debug)]
    struct Run {
        answers: Vec<(&'static str, NodeId)>,
        complete: bool,
        exhausted: Vec<NodeId>,
        work: usize,
    }

    fn stitch(
        files: &[(&'static str, Edges)],
        reference: NodeId,
        phases: usize,
    ) -> (Vec<(&'static str, NodeId)>, bool) {
        let run = stitch_within(files, &[reference], phases, DEFAULT_MAX_STITCH_WORK);
        (run.answers, run.complete)
    }

    fn stitch_within(
        files: &[(&'static str, Edges)],
        references: &[NodeId],
        phases: usize,
        max_work: usize,
    ) -> Run {
        let graphs: Vec<StackGraph> = files.iter().map(|(_, edges)| graph(edges)).collect();
        let mut database = PartialPathDatabase::default();
        for ((file, _), graph) in files.iter().zip(&graphs) {
            database.add_file(file, graph, DEFAULT_MAX_WORK);
        }
        let mut stitcher = ForwardStitcher::from_references(
            &database,
            "a.py",
            references.iter().copied(),
            max_work,
        );
        let answers = (0..phases)
            .flat_map(|_| stitcher.process_next_phase())
            .filter_map(|walk| {
                Some((
                    files.iter().find(|(file, _)| *file == walk.file)?.0,
                    walk.path.end,
                ))
            })
            .collect();
        Run {
            answers,
            complete: stitcher.is_complete(),
            exhausted: stitcher.exhausted().collect(),
            work: stitcher.work(),
        }
    }

    #[test]
    fn a_reference_reaches_a_definition_of_its_own_file() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        assert_eq!(stitch(&[own], REFERENCE, 1).0, [("a.py", DEFINITION)]);
    }

    #[test]
    fn a_node_that_is_not_a_reference_starts_no_walk() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        assert_eq!(stitch(&[own], SCOPE, 0), (Vec::new(), true));
    }

    #[test]
    fn a_reference_reaches_a_definition_of_another_file_through_the_root() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let answers = stitch(&[importer, LIBRARY], REFERENCE, ALL_PHASES).0;
        assert_eq!(answers, [("m.py", DEFINITION)]);
    }

    #[test]
    fn a_reference_that_reaches_an_import_also_reaches_what_it_imports() {
        let edges = &[
            (REFERENCE, IMPORT),
            (IMPORT, ORIGIN),
            (ORIGIN, RELAY),
            (RELAY, ROOT),
        ];
        let answers = stitch(&[("a.py", edges), LIBRARY], REFERENCE, ALL_PHASES).0;
        assert_eq!(answers, [("a.py", IMPORT), ("m.py", DEFINITION)]);
    }

    #[test]
    fn a_definition_reached_with_symbols_left_to_find_is_walked_past() {
        let edges = &[
            (REFERENCE, RELAY),
            (RELAY, MODULE_DEFINITION),
            (MODULE_DEFINITION, DEFINITION),
        ];
        let answers = stitch(&[("a.py", edges)], REFERENCE, ALL_PHASES).0;
        assert_eq!(answers, [("a.py", DEFINITION)]);
    }

    #[test]
    fn a_walk_that_needs_symbols_the_reference_did_not_push_is_dropped() {
        let importer = ("a.py", &[(MODULE_REFERENCE, ROOT)][..]);
        assert_eq!(
            stitch(&[importer, LIBRARY], MODULE_REFERENCE, 2),
            (Vec::new(), true)
        );
    }

    #[test]
    fn a_walk_back_to_a_state_already_seen_is_not_extended_again() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let looping = (
            "m.py",
            &[(ROOT, MODULE), (MODULE, RELAY), (RELAY, ROOT)][..],
        );
        assert!(stitch(&[importer, looping], REFERENCE, ALL_PHASES).1);
    }

    #[test]
    fn a_reference_with_no_work_left_is_reported_as_exhausted() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        let run = stitch_within(&[own], &[REFERENCE], ALL_PHASES, 0);
        assert_eq!(
            (run.answers, run.exhausted),
            (Vec::new(), Vec::from([REFERENCE]))
        );
    }

    #[test]
    fn a_reference_with_work_for_every_stored_path_is_not_exhausted() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let run = stitch_within(&[importer, LIBRARY], &[REFERENCE], ALL_PHASES, 2);
        assert_eq!(
            (run.answers, run.exhausted),
            (Vec::from([("m.py", DEFINITION)]), Vec::new())
        );
    }

    #[test]
    fn the_work_counts_every_stored_path_tried() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let run = stitch_within(&[importer, LIBRARY], &[REFERENCE], ALL_PHASES, 2);
        assert_eq!(run.work, 2);
    }

    #[test]
    fn a_reference_that_runs_out_of_work_leaves_the_answers_of_the_others() {
        let edges = &[
            (REFERENCE, RELAY),
            (RELAY, ROOT),
            (LOCAL_REFERENCE, SCOPE),
            (SCOPE, DEFINITION),
        ];
        let references = [REFERENCE, LOCAL_REFERENCE];
        let run = stitch_within(&[("a.py", edges), LIBRARY], &references, ALL_PHASES, 1);
        assert_eq!(run.answers, [("a.py", DEFINITION)]);
    }

    #[test]
    fn a_walk_whose_stack_grows_without_end_stops_at_the_work_limit() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let growing = ("m.py", &[(ROOT, RELAY), (RELAY, ROOT)][..]);
        let run = stitch_within(&[importer, growing], &[REFERENCE], ALL_PHASES, 8);
        assert_eq!(
            (run.complete, run.exhausted),
            (true, Vec::from([REFERENCE]))
        );
    }

    #[test]
    fn a_walk_at_the_root_tries_no_path_that_needs_symbols_below_the_reference() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let deeper = (
            "n.py",
            &[(ROOT, MODULE), (MODULE, INNER), (INNER, MODULE_DEFINITION)][..],
        );
        let run = stitch_within(
            &[importer, LIBRARY, deeper],
            &[REFERENCE],
            ALL_PHASES,
            DEFAULT_MAX_STITCH_WORK,
        );
        assert_eq!(run.work, 2);
    }

    #[test]
    fn an_inner_definition_shadows_an_outer_definition_of_the_same_name() {
        let edges = &[
            (REFERENCE, SCOPE),
            (SCOPE, DEFINITION),
            (SCOPE, OUTER_SCOPE),
            (OUTER_SCOPE, OUTER_DEFINITION),
        ];
        assert_eq!(select(&[("a.py", edges)], 1), [("a.py", DEFINITION)]);
    }

    #[test]
    fn definitions_reached_by_edges_of_equal_precedence_are_all_selected() {
        let edges = &[
            (REFERENCE, SCOPE),
            (SCOPE, OUTER_DEFINITION),
            (SCOPE, DEFINITION),
        ];
        assert_eq!(
            select(&[("a.py", edges)], 1),
            [("a.py", DEFINITION), ("a.py", OUTER_DEFINITION)]
        );
    }

    #[test]
    fn an_answer_given_twice_is_selected_once() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        assert_eq!(select(&[own], 2), [("a.py", DEFINITION)]);
    }

    #[test]
    fn walks_into_different_files_do_not_shadow_each_other_whatever_their_node_ids() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let nested = (
            "n.py",
            &[
                (ROOT, MODULE),
                (MODULE, OUTER_SCOPE),
                (OUTER_SCOPE, DEFINITION),
            ][..],
        );
        assert_eq!(
            select(&[importer, LIBRARY, nested], 1),
            [("m.py", DEFINITION), ("n.py", DEFINITION)]
        );
    }

    #[test]
    fn a_private_definition_of_another_file_answers_nothing_and_leads_nowhere() {
        let importer = ("a.py", &[(REFERENCE, RELAY), (RELAY, ROOT)][..]);
        let reexporter = (
            "m.py",
            &[
                (ROOT, MODULE),
                (MODULE, PRIVATE_IMPORT),
                (PRIVATE_IMPORT, ORIGIN),
                (ORIGIN, LIBRARY_RELAY),
                (LIBRARY_RELAY, ROOT),
            ][..],
        );
        let library = (
            "lib.py",
            &[(ROOT, LIBRARY_MODULE), (LIBRARY_MODULE, DEFINITION)][..],
        );
        assert_eq!(
            stitch(&[importer, reexporter, library], REFERENCE, ALL_PHASES),
            (Vec::new(), true)
        );
    }

    #[test]
    fn a_private_definition_of_the_reference_file_is_an_answer() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, PRIVATE_IMPORT)][..]);
        assert_eq!(
            stitch(&[own], REFERENCE, ALL_PHASES).0,
            [("a.py", PRIVATE_IMPORT)]
        );
    }

    #[test]
    fn an_import_that_leads_to_its_definition_is_left_out() {
        let edges = &[
            (REFERENCE, IMPORT),
            (IMPORT, ORIGIN),
            (ORIGIN, RELAY),
            (RELAY, ROOT),
        ];
        assert_eq!(
            select(&[("a.py", edges), LIBRARY], 1),
            [("m.py", DEFINITION)]
        );
    }

    #[test]
    fn an_import_that_leads_nowhere_is_selected() {
        let edges = &[
            (REFERENCE, IMPORT),
            (IMPORT, ORIGIN),
            (ORIGIN, RELAY),
            (RELAY, ROOT),
        ];
        assert_eq!(select(&[("a.py", edges)], 1), [("a.py", IMPORT)]);
    }

    #[test]
    fn an_import_given_twice_that_leads_nowhere_is_selected_once() {
        let edges = &[
            (REFERENCE, IMPORT),
            (IMPORT, ORIGIN),
            (ORIGIN, RELAY),
            (RELAY, ROOT),
        ];
        assert_eq!(select(&[("a.py", edges)], 2), [("a.py", IMPORT)]);
    }

    #[test]
    fn a_file_resolves_every_reference_it_holds() {
        let own = (
            "a.py",
            &[
                (REFERENCE, SCOPE),
                (LOCAL_REFERENCE, SCOPE),
                (SCOPE, DEFINITION),
            ][..],
        );
        assert_eq!(
            resolve(&[own], DEFAULT_MAX_STITCH_WORK).answers,
            [("a.py", DEFINITION), ("a.py", DEFINITION)]
        );
    }

    #[test]
    fn a_file_resolves_a_reference_to_what_its_import_names_in_another_file() {
        let edges = &[
            (REFERENCE, IMPORT),
            (IMPORT, ORIGIN),
            (ORIGIN, RELAY),
            (RELAY, ROOT),
        ];
        assert_eq!(
            resolve(&[("a.py", edges), LIBRARY], DEFAULT_MAX_STITCH_WORK).answers,
            [("m.py", DEFINITION)]
        );
    }

    #[test]
    fn a_file_missing_from_the_database_resolves_nothing() {
        let own = ("b.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        let run = resolve(&[own], DEFAULT_MAX_STITCH_WORK);
        assert_eq!(
            (run.answers, run.exhausted, run.work),
            (Vec::new(), Vec::new(), 0)
        );
    }

    #[test]
    fn a_resolution_reports_the_references_that_ran_out_of_work() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        let run = resolve(&[own], 0);
        assert_eq!(
            (run.answers, run.exhausted),
            (Vec::new(), [REFERENCE].to_vec())
        );
    }

    #[test]
    fn a_resolution_counts_the_stored_paths_tried() {
        let own = ("a.py", &[(REFERENCE, SCOPE), (SCOPE, DEFINITION)][..]);
        assert_eq!(resolve(&[own], DEFAULT_MAX_STITCH_WORK).work, 1);
    }

    #[test]
    fn resolving_some_references_leaves_the_others_of_the_file_unresolved() {
        let own = (
            "a.py",
            &[
                (REFERENCE, SCOPE),
                (LOCAL_REFERENCE, OUTER_SCOPE),
                (SCOPE, DEFINITION),
                (OUTER_SCOPE, OUTER_DEFINITION),
            ][..],
        );
        let graph = graph(own.1);
        let mut database = PartialPathDatabase::default();
        database.add_file("a.py", &graph, DEFAULT_MAX_WORK);
        let resolution = resolve_references(
            &database,
            "a.py",
            [LOCAL_REFERENCE],
            DEFAULT_MAX_STITCH_WORK,
        );
        let answers: Vec<_> = resolution
            .definitions
            .iter()
            .map(|walk| (walk.path.start, walk.path.end))
            .collect();
        assert_eq!(answers, [(LOCAL_REFERENCE, OUTER_DEFINITION)]);
    }
}